9.2 직선 검출과 원 검출

추출한 에지 정보를 이용하여 영상에서 직선 또는 원을 검출

허프 변환 기법

9.2.1 허프 변환 직선 검출

영상에서 직선 성분을 찾기 위해서는 우선 에지를 찾아내고, 에지 픽셀들이 일직선상에 배열 되어있는지를 확인해야한다

직선을 찾는 용도로 허프 변환(hough transform) 기법이 사용된다

2차원 xy좌표에서 직선의 방정식을 파라미터 공간으로 변환하여 직선을 찾는 알고리즘이다

$y= ax +b$를 변형해

$b = -ax +y$로 변경하면

ab좌표 공간에서 기울기가 -x이고 y절편이 y인 직선의 방정식처럼 보인다

xy공간에서 직선은 ab 공간에서 한점으로 표현되고, 반대로 xy공간에서 한점은 ab 공간에서 직선의 형태로 나타난다

허프 변환을 이용하여 직선의 방정식을 찾으려면 xy공간에서 에지로 판별된 모든 점을 이용하여 ab 파라미터 공간에 직선을 표현하고, 직선이 많이 교차되는 좌표를 모두 찾아야한다

이때 직선이 많이 교차하는 점을 찾기 위해서 보통 축적 배열(accumulation array)을 사용한다

축적 배열은 0으로 초기화된 2차원 배열에서 직선이 지나가는 위치의 배열 원소 값을 1씩 증가시켜 생성한다

$y=ax+b$ 형태의 직선의 방정식을 사용할 경우 모든 형태의 직선을 표현하기 어렵다는 단점이 있다

대표적으로 $y = ax +b$ 수식은 y축과 평행한 수직선을 표현할 수 없다

수직선을 표현하려면 기울기 a 값이 무한대가 되어야하기 때문

극좌표계 형식의 직선의 방정식을 사용한다

$xcosθ + y sin θ = p$

p는 원점에서 직선가지의 수직 거리, θ는 원점에서 직선에 수직선을 내렸을 때 x축과 이루는 각도

이 경우 xy 공간에서 한점은 pθ 공간에서는 삼각함수 그래프 형태의 곡선으로 표현되고, pθ공간에서 한점은 xy 공간에서 직선으로 나타나게 된다

극좌표계 형식의 직선의 방정식을 사용하여 허프변환을 할때도 축적배열을 사용하고,

축적 배열에서 국지적 최댓값이 발생하는 위치에서의 p와 θ값을 찾아 직선의 방정식을 구할 수 있다

• 확률적 허프 변환(probabilistic Hough transform)

  직선의 방정식 파라미터 p와 θ를 반환하는 것이 아니라

  직선의 시작점과 끝점 좌표를 반환한다

  즉, 확률적 허프 변환 방법은 선분을 찾는 방법이다

  
  

  9.2.2 허프 변환 원 검출

  중심좌표가 (a,b)이고 반지름이 r인 원의 방정식

  $(x-a)^2 +(y-b)^2 = r^2$

  원의 방정식은 세개의 파라미터를 가지고 있으므로, 허프 변환을 그대로 적용하려면 3차원 파라미터 공간에서 축적 배열을 정의하고 가장 누적이 많은 위치를 찾아야한다

  그러나 3차원 파라미터 공간에서 많은 메모리와 연산시간을 필요로하다

  그래서 openCV에서 제공하는게

  허프 그래디언트 방법(Hough gradient method)
  

1. 영상에 존재하는 모든 원의 중심 좌표를 찾고,

2. 검출된 원의 중심으로부터 원에 적합한 반지름을 구한다

   
   

   원의 중심좌표를 찾는 과정에서 축적 배열이 사용된다

   허프 그래디언트 방법에서 사용하는 축적배열은 파라미터 공간에서 만드는것이 아니라 입력 영상과 동일한 xy 좌표공간에서 2차원 배열로 만든다

   원의 중심을 찾기 위해 허프 그래디언트 방법은 입력 영상의 모든 에지 픽셀에서 그래디언트를 구하고, 그래디언트 방향을 따르는 직선상의 축적 배열 값을 1씩 증가 시킨다

   원주상의 모든 점에 대해 그래디언트 방향의 직선을 그리고, 직선상의 축적 배열 값을 증가시키민 결과적으로 원의 중심 위치에서 축적 배열 값이 크게 나타나게 된다

   원의 중심을 찾은 후에는 다양한 반지름의 원에 대해 원주상에 충분히 많은 에지 픽셀이 존재하는지 확인하여 적절한 반지름을 선택한다