[CV] Edge Detection(3) - Hough Transform

Hough 변환(Hough Transform)은 이미지에서 직선이나 원과 같은 기하학적 형태를 검출하는 방법으로, 특히 에지 검출 후 추출된 에지 점들을 기반으로 원하는 형태를 찾는 데 널리 사용된다.

일반적으로 에지 검출 기법(Sobel, Canny 등)은 경계선 위치를 찾을 수 있지만, 그 경계선이 어떤 직선이나 원의 일부인지는 판단하지 못한다. Hough 변환은 이러한 에지 점들을 매개변수 공간(Parameter space)으로 변환하여, 동일한 기하학적 형태 위에 있는 점들이 하나의 공통 해(peak)로 모이도록 한다.

기본 아이디어
1. 에지 검출

• Sobel, Canny 등으로 에지를 검출하여 에지 맵을 생성한다.
• 이 에지 맵에서 각 픽셀은 어떤 객체의 경계일 가능성이 있다.

2. 에지 점들로부터 직선 찾기

• 주어진 에지 점들이 직선 위에 있다고 가정했을 때, 그 직선의 방정식은 무엇인지, 몇 개의 직선이 있는지, 각 직선에 속하는 점은 무엇인지 결정해야 한다.

3. 투표(Voting) 메커니즘

• 각 에지 점에 대해, 해당 점이 위치할 수 있는 모든 직선을 가정하고, 매개변수 공간(parameter space)에서 투표를 기록한다.
• 많은 표를 받는 매개변수 조합이 실제 직선에 해당한다.

Finding lines in an image: Hough space

직선 검출은 다양한 응용 분야에서 중요한 역할을 한다. 예를 들어, 자율 주행 자동차의 차선 인식은 도로 영상 속에서 직선을 안정적으로 찾아내는 문제와 직결된다. 이러한 직선 검출을 위한 대표적인 도구가 바로 허프 변환(Hough Transform)이다.

허프 변환은 2차원의 영상 좌표 공간(x,y)에서 표현되는 직선의 방정식을 파라미터 공간(parameter space)으로 변환하여 직선을 검출하는 방법이다.

영상 좌표에서 직선은 보통 다음과 같이 표현된다.

이 식을 변형하면 파라미터 공간에서는 다음과 같이 표현된다.

즉, 영상 공간의 한 점 $(x_0, y_0)$은 파라미터 공간에서는 하나의 직선으로 변환된다.

반대로, 영상 공간의 여러 점이 같은 직선 위에 있다면, 이들이 변환된 직선들은 파라미터 공간에서 한 점에서 교차하게 된다. 이 교차점이 바로 해당 직선을 정의하는 파라미터 $(a,b)$가 된다.

왼쪽 그림과 같이, xy공간(Image space)에 $(x_i, y_i)$, $(x_j, y_j)$ 2개의 점이 있다고 가정해보자. 이 두 점을 지나는 직선을 $y=a'x + b'$라고 했을 때, ab 공간에는 xy공간에서 각 점을 지날 수 있는 모든 직선의, 기울기 a와 y절편 b에 대한 직선의 방정식 2개가 그려진다.

이때 두 직선의 방정식은 하나의 교점이 생기는데 그 교점의 좌표는 $(a',b')$가 된다.

즉, 두 직선의 방정식의 교점 좌표 $(a',b')$는 2개의 점 $(x_i, y_i)$, $(x_j, y_j)$을 동시에 지나는 직선의 $(기울기, y절편)$을 의미한다.

Accumulation Array를 통한 검출

실제 영상에서는 수많은 에지 픽셀들이 존재한다. 각 픽셀을 파라미터 공간으로 변환하면 여러 직선이 생기고, 이 직선들이 서로 만나는 지점을 찾아야 한다. 이를 위해 누적 배열(Accumulation Array)을 사용한다.

• 먼저 초기값이 0인 2차원 배열을 준비한다.
  
• 각 에지 픽셀이 변환된 파라미터 공간에서 직선을 그릴 때, 해당 직선을 지나는 배열 원소 값을 1씩 증가 시킨다.
  
• 겹치는 부분은 계속해서 누적하여 1을 더해준다.
  
• 최종적으로 누적 배열에서 값이 큰 지점이 곧 영상 공간에서 직선이 존재할 가능성이 높은 위치를 의미한다.
  

즉, 교차가 많이 일어나는 지점을 찾아 직선으로 검출하는 것이다.

위 개요에서 말했듯이, 허프 변환에서의 "투표"는 에지 픽셀들이 자기 자신이 속할 수 있는 직선 후보에 대해 누적 배열값(카운트)을 증가시키는 과정이고, 누적 배열에서 가장 많이 투표받은 곳이 곧 직선이 되는 것이다.

수직선 문제

$y=ax+b$ 형태는 한 가지 문제를 가진다. 영상에서 수직선의 경우 기울기 $a$가 무한대가 되기 때문에 파라미터 공간에서 올바르게 표현할 수 없다.

이를 해결하기 위해 허프 변환에서는 직선을 다음과 같은 극좌표계 형태로 표현한다.

• $ρ$ : 원점에서 직선까지의 최소 거리

• $\theta$ : 이 거리를 측정할 때의 직각 방향 각도

  

이 방식은 수직선까지 안정적으로 표현할 수 있다는 장점이 있다. 따라서 실제 허프 변환 구현에서는 대부분 $(ρ, \theta)$ 형태를 사용한다.

실제 프로그래밍에서 OpenCV는 HoughLines() 함수를 제공하여 허프 변환 기반의 직선 검출을 수행한다.

이 함수는 에지 영상(Canny 결과)을 입력으로 받아, 축적 배열을 통해 얻어진 직선의 파라미터 $(ρ, \theta)$를 반환한다.

여기서 임계값(threshold)을 적절히 설정하는 것이 중요한데, 값이 낮으면 많은 직선이 검출되지만 잡음까지 포함될 수 있고, 값이 높으면 중요한 직선을 놓칠 수 있다.

실제 영상에 있는 물체는 모서리 부분에 직선이 존재한다. 아래의 오른쪽 그림은 실제 영상을 허프 공간 $(ρ-\theta 공간)$으로 변환한 결과이다.

우측 이미지의 밝은 곡선 하나하나가 영상의 한 에지 픽셀이 허프 공간에 그린 곡선이다.

즉, "이 픽셀이 속할 수 있는 모든 직선 후보들"이 파라미터 공간에서 곡선으로 표현된 것이다.

노란색 원으로 표시된 교차점은 여러 곡선이 한 점에서 만나는 곳을 의미한다. 즉, 이 좌표 $(ρ, \theta)$가 바로 영상에서의 실제 직선을 나타내는 파라미터가 되는 것이다.

따라서 허프 변환은 "에지 픽셀 $\to$ 허프 공간 곡선 $\to$ 곡선들이 만나는 교차점 = 직선"이라는 흐름으로 작동한다.