허프 변환

컴퓨터 그래픽스 수치해석 마지막 수정: 2026-08-28 04:53:44

1. 개요[편집]

허프 변환 Hough Transform
원안	Paul V. C. Hough, 미국 특허 3,069,654 (1962) — 거품상자 비적 검출
현대형	Duda & Hart (1972) — 법선형 $\rho = x\cos\theta + y\sin\theta$
발상	영상공간의 점 ↔ 파라미터공간의 곡선 (쌍대성)
자료구조	누적기 배열 $A[\theta_j,\rho_i]$ — 투표 후 피크 탐색
비용	직선 $O(N N_\theta)$, 원 $O(N N_a N_b)$ — 차원의 저주
확장	원 허프 · 일반화 허프(GHT, R-테이블) · 확률적 허프(PPHT)

어느 직선이 정답인지 모르겠으면, 모든 직선에게 투표를 시켜라.

허프 변환(Hough transform)은 영상 공간의 각 특징점이 「자신을 지날 수 있는 모든 도형」에 한 표씩 던지게 하고, 파라미터 공간에 쌓인 표를 세어 가장 많은 지지를 받은 도형을 검출하는 기법이다. 1962년 폴 허프가 거품상자 사진에서 하전입자 궤적을 자동으로 찾으려고 낸 특허가 원조이고,¹ 오늘날 쓰이는 형태는 두다와 하트가 1972년에 매개변수화를 바꾸면서 완성됐다.

에지 검출이 남기는 것은 켜진 화소들의 집합일 뿐, “이 화소들이 한 직선 위에 있다”는 사실은 아무도 말해 주지 않는다. 게다가 에지 지도는 늘 끊겨 있고 잡음 화소가 섞여 있다. 허프 변환의 미덕은 끊김에 강하고 이상점에 강하다는 것이다. 직선 위 화소가 중간중간 빠져도 남은 표가 여전히 같은 칸에 쌓이고, 엉뚱한 잡음 화소들은 표를 파라미터 공간 전체에 흩뿌려 아무 봉우리도 만들지 못한다. 데이터를 모형에 맞추는 것이 아니라 모형이 데이터의 지지를 받는 구조라, 최소자승 맞춤이 이상점 하나에 무너지는 것과 정반대의 성격을 갖는다.

2. 쌍대성 — 점이 곡선이 된다[편집]

기본 아이디어는 관점 뒤집기다. 직선 $y = mx + c$ 를 보는 방법이 둘 있다.

영상 공간: $(m,c)$ 를 고정하고 $(x,y)$ 를 훑으면 → 점들의 집합, 즉 직선 하나.
파라미터 공간: $(x_0,y_0)$ 를 고정하고 $(m,c)$ 를 훑으면 → $c = -x_0 m + y_0$ , 역시 직선 하나.

즉 영상의 한 점은 파라미터 공간의 한 곡선에 대응하고, 그 역도 성립한다. 그리고 결정적으로, 영상에서 한 직선 위에 놓인 여러 점들은 파라미터 공간에서 한 점에서 만나는 여러 곡선이 된다. 그 교점의 좌표가 곧 직선의 파라미터다. 「공선(collinear) 여부 판정」이라는 조합적 문제가 「곡선들의 교점 찾기」라는 기하 문제로, 다시 「배열에서 최댓값 찾기」라는 아주 싼 문제로 번역된다.

3. 기울기-절편은 왜 못 쓰는가[편집]

원 특허가 쓴 $(m,c)$ 매개변수화에는 치명적 결함이 있다. 수직선의 기울기가 무한대다. $m\in(-\infty,\infty)$ 이므로 누적기 배열을 잡을 수가 없고, 억지로 자르면 가파른 직선들의 표가 배열 밖으로 새어 나간다. 더 나쁜 것은 분해능이 불균일하다는 점이다. $m$ 을 등간격으로 자르면 45° 근처에서는 촘촘하고 80° 근처에서는 성기다 — 같은 각도 오차가 $m$ 공간에서는 전혀 다른 칸 수로 환산된다.

두다와 하트의 처방이 법선형(normal form) 이다. 원점에서 직선까지의 부호 있는 거리 $\rho$ 와 그 수선의 방향 $\theta$ 로 직선을 적는다.

\rho = x\cos\theta + y\sin\theta

이러면 두 파라미터가 모두 유계다. $\theta \in [0,\pi)$ , $\rho \in [-D, D]$ 이고 $D$ 는 영상의 대각 길이다.² 그리고 이 매개변수화에서 영상의 한 점 $(x_0,y_0)$ 이 그리는 궤적은 직선이 아니라 사인 곡선이다.

\rho(\theta) = x_0\cos\theta + y_0\sin\theta = r\cos(\theta - \phi), \qquad r = \sqrt{x_0^2+y_0^2},\;\; \phi = \operatorname{atan2}(y_0,x_0)

진폭이 원점으로부터의 거리, 위상이 방위각이다. 그래서 허프 공간 그림을 보면 사인 곡선들이 겹쳐진 무늬가 나오고, 공선인 점들의 사인 곡선은 정확히 한 점에서 만난다. 이 그림 자체가 상당히 예뻐서, 허프 변환을 처음 배울 때 대개 여기서 감탄한다.

4. 누적기와 투표[편집]

구현은 놀랄 만큼 짧다.

$N_\theta \times N_\rho$ 크기의 정수 배열 $A$ 를 0으로 초기화한다.
에지 화소 $(x,y)$ 마다, 모든 $\theta_j$ 에 대해 $\rho = x\cos\theta_j + y\sin\theta_j$ 를 계산하고 해당 칸을 1 증가시킨다.
$A$ 에서 값이 큰 칸들을 찾는다. 그 $(\theta,\rho)$ 가 검출된 직선이다.

비용은 에지 화소 수 $N$ 과 각도 칸 수 $N_\theta$ 의 곱, $O(N N_\theta)$ 다. $\cos\theta_j,\sin\theta_j$ 는 미리 표로 만들어 두므로 안쪽 루프는 곱셈 두 번과 덧셈 한 번이 전부고, 메모리는 $N_\theta N_\rho$ 정수. 512×512 영상에 $\Delta\theta=1^\circ$ , $\Delta\rho=1$ 화소면 누적기가 $180 \times 1449 \approx 26$ 만 칸이니 부담도 없다.

투표를 이진(1표씩)으로 할 필요도 없다. 기울기 크기 $|\nabla I|$ 를 가중치로 주면 강한 에지가 더 큰 발언권을 갖고, 부화소 위치를 알면 인접한 두 $\rho$ 칸에 선형 보간으로 나눠 던져 양자화 잡음을 줄일 수 있다. 후자를 “소프트 투표”라 부르며, 아래에서 볼 피크 뭉개짐을 상당히 완화한다.

영상 150×100 px 의 에지 점들이 각자 사인 곡선 하나로 (θ, ρ) 누적기 180×361 = 64,980칸에 투표하고, 같은 직선 위 점들의 곡선이 한 칸에서 교차해 봉우리가 된다. 그 봉우리를 되쏘면 직선이 복원된다. 지터 σ 를 0 으로 놓아 점이 정확히 직선 위에 있어도 오차는 0 으로 내려가지 않는다 — 300 실현 실측 rms Δρ = 0.47 px, rms Δθ = 0.34°, 격자 Δρ = 1 px·Δθ = 1° 가 만드는 바닥이다.

5. 양자화 — 어디에도 정답이 없는 저울[편집]

허프 변환에서 사람이 실제로 고민하는 것은 알고리즘이 아니라 $\Delta\rho$ 와 $\Delta\theta$ 를 얼마로 잡을 것인가 하나다. 그리고 이 저울은 딱딱하다.

너무 곱게 자르면: 실제로는 한 직선인데 화소 위치의 이산화·잡음 때문에 표가 이웃한 여러 칸으로 흩어진다(피크 뭉개짐). 봉우리 높이가 낮아져 임계값에 걸리지 않고, 하나였어야 할 직선이 여러 개로 검출된다. 게다가 누적기가 커져 메모리와 피크 탐색 비용이 늘어난다.
너무 거칠게 자르면: 가까운 두 직선이 한 칸에 합쳐져 구분되지 않고, 검출된 파라미터의 정밀도가 칸 크기로 제한된다. 각도가 1° 틀어지면 500화소 길이 직선의 끝점은 4화소 넘게 어긋난다.

바로 그 마지막 문장이 실무 규칙을 준다. 길이 $L$ 인 선분에서 각도 오차 $\Delta\theta$ 는 끝점을 대략 $(L/2)\Delta\theta$ 만큼 밀어낸다. 이 값이 $\Delta\rho$ 를 넘지 않게 하려면

\Delta\theta \;\lesssim\; \frac{2\,\Delta\rho}{L}

이다. $\Delta\rho = 1$ 화소, $L = 500$ 화소면 $\Delta\theta \lesssim 0.004\,\text{rad} \approx 0.23^\circ$ — 관례적인 1°는 긴 선분에는 너무 거칠다. 반대로 짧은 선분만 찾을 거면 1°로도 넘친다. 즉 양자화는 “기본값”이 있을 수 없고 찾으려는 선분의 길이에 맞춰 정해야 하는 값이다.

이 문제를 우회하는 표준 기법이 둘 있다. 하나는 거친 격자로 한 번 돌려 후보 영역을 좁힌 뒤 그 영역만 곱게 다시 투표하는 계층적(coarse-to-fine) 허프. 다른 하나는 표를 점이 아니라 커널로 던지는 것으로, 공선 화소 뭉치의 불확실성을 타원형 가우스 커널로 모형화해 투표하면 누적기가 매끄러워져 피크가 안정된다(커널 기반 허프 변환).

6. 피크 검출 — 사실 여기가 진짜 어려운 부분[편집]

“최댓값 찾으면 되잖아”로 끝나지 않는다. 누적기에는 병리적인 구조가 몇 가지 항상 있다.

봉우리는 나비 모양이다. 유한 길이 선분이 만드는 누적기 국소 구조는 점이 아니라 $\theta$ 방향으로 퍼진 나비(butterfly) 무늬다. 퍼진 폭이 선분 길이에 반비례하므로 무늬 모양에서 길이를 역산할 수도 있지만, 순진하게 임계값을 걸면 나비 한 마리가 여러 개의 봉우리로 검출된다.

그래서 비최대 억제가 필수다. 흔한 절차는 (1) 누적기를 살짝 평활하고, (2) 임계값 이상인 칸 중 국소 최대만 남기고, (3) 큰 순서로 뽑되 이미 뽑은 봉우리 주변 창(예: $\pm 3$ 칸)을 지운다. 에지 검출의 비최대 억제와 이름은 같지만 무대가 파라미터 공간이라는 점만 다르다.

더 정직한 방법은 표를 회수하는 것이다. 봉우리 하나를 뽑았으면 그 직선에 표를 던진 화소들을 찾아 투표를 취소(unvote)하고 다음 봉우리를 찾는다. 이러면 한 화소가 여러 직선에 중복 기여해 유령 직선을 만드는 일이 사라진다. 비용은 화소→직선 대응을 기억해야 한다는 것.

임계값은 절댓값으로 박지 마라. 표 수는 영상 크기·에지 밀도에 비례한다. 실무 기준은 “최댓값의 몇 %” 또는 “찾고자 하는 최소 선분 길이(화소 수)“로 두는 것이고, 후자가 물리적 의미가 있어 낫다.

7. 경사 방향으로 투표를 깎는다[편집]

기본형은 각 화소가 $N_\theta$ 개 칸 전부에 투표하는데, 이건 사실 정보를 버리고 있는 것이다. 에지 화소는 방향을 가지고 있다. 소벨이나 샤르로 얻은 기울기 방향 $\phi$ 는 곧 그 지점 에지의 법선 방향이고, 직선의 법선 방향이 바로 $\theta$ 다. 그러니

\theta \in [\phi - \Delta,\; \phi + \Delta]

범위에만 투표하면 된다. $\Delta$ 를 $\pm 10^\circ$ 로 잡으면 투표 수가 $180/20 = 9$ 배 줄고, 부수 효과로 유령 봉우리가 크게 감소한다 — 무관한 방향의 표가 아예 쌓이지 않기 때문이다. 대가는 기울기 방향 추정 오차에 민감해진다는 것. 3탭 소벨의 방향 오차는 대각선 근처에서 수 도에 이르므로 $\Delta$ 를 너무 좁히면 진짜 직선을 놓친다. 방향이 중요한 이 용도에서 샤르 마스크를 권하는 이유가 이것이다.

8. 원과 일반화 허프[편집]

원. $(x-a)^2 + (y-b)^2 = r^2$ 은 파라미터가 셋이라 누적기가 3차원이다. $r$ 을 모르면 비용이 $O(N N_a N_b)$ 로 뛰고 메모리도 세제곱으로 늘어난다. 차원의 저주가 여기서 바로 터진다.

살길은 역시 경사 방향이다. 원 위의 점에서 중심은 법선 방향 위 거리 $r$ 인 지점에 있으므로, $r$ 을 알면 각 에지 화소는 단 두 칸(안쪽·바깥쪽)에만 투표하면 된다. $r$ 을 모르면 2차원 중심 누적기에 법선 직선을 따라 투표한 뒤, 봉우리로 중심을 먼저 확정하고 그 중심으로부터의 거리 히스토그램에서 반지름을 따로 뽑는다. 3차원 문제를 2차원 + 1차원으로 쪼개는 이 방식이 OpenCV HoughCircles 의 기본 모드다.

일반화 허프 변환(GHT). 배러드가 1981년에 해석적 수식이 없는 임의 형상으로 확장했다. 학습 단계에서 형상 위 모든 점에 대해 기준점까지의 변위 벡터를 재고, 기울기 방향 $\phi$ 를 열쇠로 하는 표(R-테이블) 에 저장한다. 검출 단계에서는 각 에지 화소의 $\phi$ 로 표를 조회해 나온 변위들을 더한 위치에 투표하면, 형상이 실제로 있는 자리에서 기준점 표가 몰린다. 회전과 축척까지 허용하려면 누적기가 $(x_c, y_c, s, \vartheta)$ 의 4차원이 되어 비용이 폭발하고, 그래서 실무에서는 회전·축척을 고정하거나 좁은 범위로 제한한다. 오늘날 이 자리는 대부분 특징점 검출 기반 정합이나 학습 기반 검출기에 넘어갔지만, GHT의 “부분이 전체의 위치에 투표한다”는 구조는 암묵적 형상 모형(implicit shape model)이나 자세 추정의 투표 방식으로 계속 살아남았다.

9. 확률적 허프 — 모든 화소가 투표할 필요는 없다[편집]

에지 화소가 5만 개인데 5만 개 전부의 표를 세어야 봉우리를 알 수 있을까? 없다. 표본만으로도 충분히 큰 봉우리는 드러난다.

무작위 허프 변환(RHT). 점 하나가 곡선 하나에 투표하는 대신, 점 두 개를 무작위로 뽑아 직선 파라미터를 딱 하나 계산하고 그 칸에만 한 표를 던진다. 일대다 사상이 다대일 사상으로 바뀌므로 표가 흩어지지 않고, 누적기를 해시 테이블로 두어 메모리를 아낄 수 있다.
점진적 확률 허프(PPHT). 오늘날 HoughLinesP 로 널리 쓰이는 방식이다. 남은 에지 화소 중 하나를 무작위로 뽑아 표준 투표를 하고, 그 화소가 갱신한 칸이 임계값을 넘으면 즉시 해당 직선을 따라 걸어가며 실제 선분(허용 간격 이하로 이어지고 최소 길이 이상인 구간)을 추출한다. 그리고 그 선분에 속한 화소들의 표를 회수하고 목록에서 제거한다. 임계값은 남은 화소 수에 맞춰 오경보 확률을 억제하도록 조정한다.

PPHT의 이득이 두 가지인데, 속도(대개 수 배~열 배)보다도 선분의 끝점을 준다는 점이 실무에서 더 크다. 표준 허프는 “무한 직선”만 돌려주므로 어디서 시작해 어디서 끝나는지, 심지어 하나인지 여러 조각인지도 알려 주지 않는다. 그 정보를 얻으려면 어차피 사후에 직선을 따라 걸어야 하고, PPHT는 그 걷기를 알고리즘 안으로 넣은 것이다.

10. RANSAC과의 비교[편집]

같은 문제를 푸는 두 철학이라 나란히 놓고 보면 성격이 선명해진다. RANSAC은 최소 표본(직선이면 두 점)으로 모형을 하나 세우고 지지자 수를 세는 것을 반복해 최다 지지 모형을 남긴다. 허프는 파라미터 공간을 격자로 잘라 전수 조사한다.

탐색 방식: 허프 = 양자화된 파라미터 공간의 밀도 추정 + 최빈값 찾기(결정적). RANSAC = 같은 밀도를 무작위 표본으로 탐색(확률적). 성공 확률로 반복 횟수를 정한다.
차원 확장성: 허프는 파라미터 차원에 대해 메모리가 지수적으로 늘어 3~~4차원이 현실적 한계다. RANSAC은 누적기를 안 만들므로 기본행렬(7~~8차원)·호모그래피(8차원) 같은 곳까지 그대로 간다. 고차원이면 사실상 RANSAC 말고 선택지가 없다.
다중 모형: 허프는 봉우리 여러 개를 한 번에 준다. 이게 큰 장점이다. RANSAC은 원래 하나만 찾는 구조라, 여러 개를 찾으려면 찾고 제거하고 다시 돌리는 순차 방식을 쓰는데 뒤로 갈수록 열화한다.
정밀도: 허프의 답은 칸 해상도에 묶인다. RANSAC의 답은 최소 표본으로 만든 것이라 역시 거칠다. 그래서 양쪽 다 마지막에 내부점만 모아 최소자승법으로 재적합하는 단계가 사실상 필수다. 이 단계를 빼먹고 “허프가 부정확하다”고 결론 내리는 것이 흔한 오해다.
파라미터: 허프는 $\Delta\rho,\Delta\theta$ 와 임계값. RANSAC은 내부점 허용오차와 반복 횟수. 어느 쪽도 공짜는 아니다.

둘 사이의 다리가 앞 절의 RHT다 — 최소 표본으로 모형을 세운다는 점은 RANSAC이고, 세운 모형을 격자에 누적한다는 점은 허프다. 실제로 “허프냐 RANSAC이냐”는 대립이 아니라 파라미터 차원과 모형 개수가 정하는 선택이다. 직선·원 몇 개를 한 번에 찾는다면 허프, 고차원 변환 하나를 강건하게 추정한다면 RANSAC.

11. 라돈 변환과의 관계, 그리고 해석 파이프라인[편집]

허프 변환은 라돈 변환의 희소·이산 사촌이다. 라돈 변환은 영상 밝기를 모든 직선을 따라 적분해 $(\theta,\rho)$ 함수를 만드는 연속 연산으로, CT 재구성의 사이노그램이 바로 그것이다. 허프는 밝기 전체가 아니라 에지 화소들만 세고, 적분 대신 이산 누적을 한다. 그래서 계산은 훨씬 싸지만 결과는 이진화 임계값에 의존한다. 반대로 흐릿한 저대비 선을 찾을 때는 에지 검출을 거치지 않는 라돈 쪽이 유리하다.

해석·계측 쪽에서 허프 변환을 만나는 자리는 대체로 정해져 있다.

카메라 보정. 체커보드·원 격자 타겟의 격자선과 원 검출. 왜곡 보정 전 단계라 직선성이 깨져 있어도 견뎌야 하는데, 투표 방식이라 잘 견딘다.
구조광·레이저 시트. PIV·형상 계측에서 투영된 레이저 선을 잡아내는 첫 단계.
재료·검사 영상. 복합재 단면의 섬유 배향, 결정립계 방향 분포, 균열의 주 방향 추정. 여기서는 봉우리 하나가 아니라 $\theta$ 방향 누적 히스토그램 전체가 결과물이 된다 — 방향 분포 함수를 그냥 누적기에서 읽는 셈.
형상 추출 전처리. 슬라이스 영상에서 원형 관·볼트 구멍을 찾아 CAD 파라미터로 되돌리는 리버스 엔지니어링. 검출된 원의 중심·반지름이 곧 메시 생성의 입력 형상이 된다.

마지막으로 실무 감각 몇 줄. 에지 지도를 먼저 손봐라 — 허프는 입력 화소를 그대로 믿으므로, 두꺼운 에지는 세선화하고 잡음 화소는 수학적 형태학 연산으로 걷어내는 편이 어떤 파라미터 조정보다 효과가 크다. $\rho$ 의 원점은 영상 중심으로 잡아라 — 좌상단으로 두면 $\rho$ 범위가 두 배로 넓어지고 오차 특성이 비대칭이 된다. 그리고 누적기를 한 번은 그림으로 봐라. 봉우리가 안 보이면 임계값 문제가 아니라 입력 문제이고, 봉우리가 열 개 보이는데 하나만 나온다면 비최대 억제 창이 너무 넓은 것이다. 파라미터를 손으로 흔들기 전에 누적기 그림 한 장이 대개 답을 준다.³

12. 관련 문서[편집]

특허 제목이 “Method and Means for Recognizing Complex Patterns”인데, 정작 도면은 거품상자 사진 위의 입자 궤적이다. 브룩헤이븐에서 물리학자들이 사진을 눈으로 보며 궤적을 세던 시절이라, 이 발명의 원래 동기는 “사람이 사진 판독에 갈려 나가는 것을 막자”였다. 영상처리 교과서에 실릴 줄은 본인도 몰랐을 것이다. ↩
$\theta$ 를 $[0,2\pi)$ 로 잡으면 같은 직선이 $(\theta,\rho)$ 와 $(\theta+\pi,-\rho)$ 두 칸에 중복 표현되어 표가 반씩 갈린다. $[0,\pi)$ 로 잡고 $\rho$ 에 부호를 허용하는 것이 표준이며, 이걸 헷갈려 봉우리 높이가 기대의 절반으로 나오는 버그가 허프 구현의 통과의례다. ↩
누적기를 이미지로 저장해 보는 습관은 디버깅 도구 이상의 값어치를 한다. 사인 곡선들이 어디서 만나는지, 나비 무늬가 얼마나 퍼졌는지, 임계값 선이 어디를 지나는지가 한눈에 보인다. “일단 돌려” 놓고 결과 직선만 노려보면 영원히 파라미터 미신에서 못 벗어난다. V&V 정신은 영상처리에서도 똑같이 적용된다. ↩