[CV] 4. Boundary Detection

Week 4-1. Boundary Detection

1. Boundaries of Objects

edge detection, multi-scale edge detection, sometimes hard for humans

2. Hough Transform for Line Detection

Edges need not be connected, need not visible
Edges VOTE for the possible models

• Image and Parameter Space
  y = mx + b -> parameter space: b = -mx + y
  각 점(1,1),...을 지날 수 있는 모든 직선의 기울기 m과 y절편 b를 나타내는 직선이 그려짐
  교점 좌표는 두 점을 동시에 지나는 유일한 직선의 (기울기 m, y절편 b)를 의미
  parameter space의 직선들이 많이 교차되는 지점으로 직선 검출 가능

• Algorithm
  직선들이 많이 교차하는 점을 찾기 위해 축적 배열 A 사용
  0으로 초기화된 2차원 배열에서 직선이 지나가는 위치의 배열 원소 값을 1씩 증가시켜 생성
  일정 임계값 이상인 점의 m,c(기울기, y절편)로 직선 검출

1. Quantize parameter space (m,c)
2. Create accumulator array A(m,c) 축적자
3. Set A(m,c) = 0 $\forall m,c$
4. for each image edge $(x_i,y_i)$ 증가
   A(m,c) = A(m,c) + 1 if (m,c) on the line $c = -x_im + y_i$
5. find local maxima in A(m,c)

Better Parameterization
$-\infty \leq m \leq \infty$
-> improvement: finite accumulator size
극좌표계의 직선 방정식 사용
Line equation: $\rho = xcos\theta + ysin\theta$ $rho$: perpendicular distance to line from origin 수직 거리
$where 0 \leq \theta \leq 2\pi, 0 \leq \rho \leq \rho_{max}$ image space is limited
Given a point $(x_i,y_i), \rho = x_icos\theta + y_isin\theta$
image space -> parameter space, $\rho, \theta$의 공간으로 변환
곡선들이 많이 교차되는 점을 축적 배열로 찾음, 직선 검출

Image and Parameter Space

Mechanics of the Hough Transform

• line 수: Hough array의 peak 세기, 인접한 피크는 하나로 취급
• line에 속한 points: line에 가까운 points 찾기
• Quantization error- cell 크기:
  too big: 다른 line을 합침
  too small: line 못 찾음, large vote가 없음
• difficulties of noise
  noise 크면, fewer votes land in the single bin, false peaks
  clutter: 혼란

3. Hough Transform for Circle Detection

Imae and Parameter Space

radius is unknown
surface of a cone
use Accumulator array A(a,b,r)
save computation: Gradient information

assume radius is known- increment only one point in accumulator

Finding Coins
Pennie 주황 동전, quarter 나머지 동전 size: 27, 34.5 pixels
Pennie Hough detector, Quarter Hough detector

4. Generalized Hough Transform

Model Shape NOT described by equation, Silhouette only
Goal: Find the object center $(x_0,y_0)$
1. Pick a reference point $(x_c.y_c)$
2. For each point $(x_i.y_i)$ obtain $(r_i,\alpha_i,\phi_i)$
$\vec{r_i}$: a vector form from boundary point to reference $\vec{r_i}= (r_i,\alpha_i)$
$\phi_i$: gradient orientation 방향

Finding object center $(x_0,y_0)$ given edges $(x_i,y_i,\phi_i)$
Initialize Accumulator Array $A(x_c,y_c) for \forall(x_c,y_c)$
For each edge point $(x_i,y_i,\phi_i)$, compute:
$x_c = x_i + r^i_kcos\alpha^i_k$
$y_c = x_i + r^i_ksin\alpha^i_k$
increment accumulator: $A(x_c,y_c) = A(x_c,y_c) + 1$
Find local maxima in $A(x_c,y_c)$

Comments
good:Deals with occlusion well 폐색
Detects multiple instances
Robust to noise
Bad: Bad computational complexity
Difficult to set parameters