3. Hough Transform

Hough Transform

Finding boundaries

edge에 노이즈가 많으면 boundary가 제대로 나오지 않음

Line Fitting

Problems

1. 가장 잘 표현한 선인데도 너무 큰 오차가 생겨버림.
   

2. 가장 오차가 적은 선이 데이터를 잘 표현 못함
   

3. 이상치 (outliers)가 있을때
   

Line Parameterizations

Slope intercept form (기울기-절편 형태)

Double intercept form (절편-2개 형태)

절편 2개로 직선을 표현

• a : x절편, b : y절편
  

Normal form

(원점에서 직선에 이르는 수직거리) & (수직선의 방향)을 사용하여 표현

• $\theta$ : x축과 수직선의 방향 각도
• $\rho$ : 원점에서 직선까지의 수직거리
  

Hough Transform

Problems
1. edge들은 꼭 연결되어있지 않을 수 있다.
2. line은 가려져있을 수 있다.

Key Idea
각 edge들이 적합한 모델에 '투표'

Image & parameter space

Q.
측정 과정에서 발생하는 노이즈에 잘 대처합니까?

A.
네. noise는 만나는 점이 적어서 받는 투표가 적습니다.

Q.
이상치 (outliers)에 잘 대처합니까?

A.
네.

Line Detection by Hough Transformation

Algorithm:

1. 파라미터 공간 (m,c) 양자화하여 가능한 모든 선분의 기울기(m)와 절편(c)에 대한 이산적인 값 구함
2. 각 (m,c)쌍에 대해 누산기 배열 A를 생성
3. 배열의 모든 요소 0으로 초기화
4. for 모든 이미지 edge (x_{i}, y_{i})에 대해서
    for 배열 A(m,c)의 모든 요소에 대해서
        if (m,c)쌍이 edge 픽셀을 지나는 직선의 방정식을 만족하면,
            해당 (m,c) 쌍에 대한 누산기 값을 1 증가시킴
5. A(m,c) 배열에서 국소 최댓값을 찾음

문제점
누산기 배열 m과 c의 공간이 너무 크다
$- \infty \leq m, c \leq \infty$

Better Parameterization

아래 Normal form 사용

$(x_{i}, y_{i})$가 주어졌을때, $(\rho, \theta)$ 구하기

범위:
$0 \leq \theta \leq 2\pi$
$0 \leq \rho \leq \rho_{max}$
따라서, 누산기 배열이 한정적이다.

$\rho_{max} = \sqrt {(height)^2 + (weight)^2}$

negative $\rho$

positive $\rho$ version:
$x cos \theta + y sin \theta = \rho$
negative $\rho$ version:
$x cos (\theta + pi) + y sin (\theta + pi) = -\rho$

recall:
$sin(\theta) = -sin(\theta + \pi)$
$cos(\theta) = -cos(\theta + \pi)$

Image & parameter space

Implementation

Basic shapes

문제점

측정 오차가 존재

Hough Circles

반지름을 알고 있다고 가정할때,

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

파라미터: $a, b$ (→ 2차원)
변수: $x, y$

반지름을 모른다고 가정할때,

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

파라미터: $a, b, r$ (→ 2차원)
변수: $x, y$

누산기 배열 $A(a,b,r)$ 사용

edge 먼저 검출하고 시작

Traits of Hough transform

1. 가려진 것도 잘 찾는가?
   yes
2. 여러개를 동시에 처리 가능한가?
   yes
3. 노이즈에 잘 대처하는가?
   yes
4. 계산 복잡도가 좋은가?
   no
5. 파라미터 설정이 쉬운가?
   no ($\theta, \rho$ 몇개나? & 간격을 얼마나?)
6. line & circle 외의 object에도 사용 가능?
   yes
7. edge 검출을 해야하는가?
   yes (edge point를 가지고 Hough Transform 진행)

Application of Hough Transforms

스케일 변화와 배경이나 주변환경에서 발생하는 노이즈 (=이미지 내의 불필요한 정보)에 더 잘 대처함

Corner Detection

corner: 2개 (혹은 그 이상)의 edge의 각도가 significantly 다를때

Visualizing quadratics

can be written in matrix form like...

results of Singular Value Decomposition (SVD)

Harris corner detector

corner는 small window를 통해 쉽게 발견 가능

Finding corners

1. 구간별로 이미지의 기울기 계산
2. 각 기울기에서 평균값 빼기
3. 공분산 행렬 계산
4. eigen-vector & eigen-value 계산
5. eigen-value 임계점을 사용해 corner 검출

visualization of gradients

Compute the covariance matrix

Error function

Visualization of a quadratic

Compute eigen-values & eigen-vectors

Visualization as an ellipse

M이 대칭이니,

interpreting eigen-values

Use threshold on eigen-values to detect corners

Harris Detector

1. compute x and y derivatives of image
2. compute products of derivatives at every pixel
3. compute the sums of the products of derivatives at each pixel
4. define the matrix at each pixel
5. compute the response of the detector at each pixel
6. threshold on value of R; compute non-max suppression

Traits of Harris corner response

1. rotation에 영향받지 않음
2. intensity에 영향받지 않음 (brightness / contrast)
3. scale에는 영향받음

Multi-scale detection