허프 변환 (Hough Transform)

점들이 흩어져 있을 때, 그 사이를 지나는 직선을 어떻게 자동으로 찾을까? 노이즈가 섞여 있어도 끄떡없는 방법이 있다 — 모든 점이 "내가 속할 수 있는 모든 직선"에 투표하게 만들고, 표를 가장 많이 받은 직선을 고르는 것이다.

1. 핵심 아이디어 — 좌표계를 뒤집는다

보통 이미지 좌표 (x, y) 공간에서 "이 점들을 지나는 직선은?"이라고 묻는다. 허프 변환은 반대로 생각한다. 직선을 기울기·절편 y = ax + b 대신, 원점에서 직선까지의 수직 거리 ρ(rho)와 그 수직선의 각도 θ(theta)로 표현한다.

기울기 a가 수직선(세로선)에서 무한대로 발산하는 문제를 피할 수 있어서, 모든 직선을 (θ, ρ) 단 두 값으로 표현할 수 있다.

2. 점 하나 → 곡선 하나, 여러 점 → 교차점 하나

점 (x, y) 하나를 고정하고 θ를 0°~180°까지 돌려보면, 그 점을 지나는 모든 가능한 직선의 (θ, ρ) 값이 하나의 사인 곡선을 그린다. 같은 직선 위에 있는 점들은 서로 다른 사인 곡선을 그리지만, 그 직선에 해당하는 (θ, ρ) 한 점에서 모두 교차한다. 그 교차점에 표를 많이 모아주는 것 — 그게 바로 "직선을 찾았다"는 뜻이다.

3. 직접 해보기 — 점을 찍고 직선을 찾아라

캔버스를 클릭해 점을 추가하거나, 아래 버튼으로 노이즈 섞인 직선 데이터를 자동 생성해보자. "허프 변환 실행"을 누르면 오른쪽에 (θ, ρ) 투표 공간이 히트맵으로 그려지고, 가장 밝은 지점(최다 득표)이 왼쪽 캔버스에 빨간 직선으로 표시된다.

4. 왜 노이즈에 강할까?

노이즈 점 하나도 자기 사인 곡선을 그리며 투표하지만, 그 곡선이 다른 노이즈 점들과 우연히 같은 (θ, ρ)에서 만날 확률은 낮다. 반면 진짜 직선 위의 점들은 항상 정확히 같은 (θ, ρ)에서 만나 표를 쌓는다. 점이 많을수록 진짜 직선의 봉우리는 점점 더 뾰족해지고, 노이즈는 투표 공간 전체에 옅게 흩뿌려질 뿐이다.

5. 코드로 보는 허프 변환

import numpy as np

def hough_transform(points, theta_steps=180):
    thetas = np.deg2rad(np.arange(-90, 90))
    diag = int(np.hypot(480, 340))
    rho_max = diag
    accumulator = np.zeros((2 * rho_max + 1, theta_steps))

    for (x, y) in points:
        # 이 점을 지나는 모든 직선의 (theta, rho) 곡선을 그린다
        for t_idx, theta in enumerate(thetas):
            rho = x * np.cos(theta) + y * np.sin(theta)
            r_idx = int(round(rho)) + rho_max
            accumulator[r_idx, t_idx] += 1  # 투표

    # 가장 표를 많이 받은 (theta, rho) = 검출된 직선
    r_idx, t_idx = np.unravel_index(np.argmax(accumulator), accumulator.shape)
    return thetas[t_idx], r_idx - rho_max

6. 확장 — 원도 찾을 수 있다

파라미터를 (중심 x, 중심 y, 반지름 r) 3개로 늘리면 원(Circle Hough Transform)도 같은 원리로 검출할 수 있다. 파라미터가 늘어날수록 투표 공간의 차원이 늘어나 계산량이 커지지만, "여러 점이 같은 파라미터에 투표하면 그게 정답"이라는 핵심 아이디어는 동일하다.