Harris corner detection

Harris corner detection

Harris corner detection은 corner point를 찾기 위한 방법으로, 기존의 Moravec 방법을 개선해서 고안되었습니다.

Moravec coner's detector은 Local window를 사용하여 window를 shifting해 가면서 이미지의 평균 변화값을 측정하는 방법입니다.  Moravec corner detector은 다음과 같은 3가지 문제점이 있었습니다. (Moravec 방법은 여기서 자세히 다루지는 않겠습니다)

1. Response가 비등방성이고, 45도의 shift밖에 고려하지 못한다.

2. Binary, Rectangular window를 사용하기에 Response에 Noise가 많다.

3. Moravec 방법은 minimum Energy만 고려하기에 Operator가 edge에 너무 쉽게 반응한다.

 

Harris corner detector은 어떻게 3가지를 개선하였을까요?

1. 모든 작은 shift들도 고려하여 SSD영상 변화량을 계산. 

Image change는 I, shift에 의한 변화량은 E라고 할 때 Taylor전개에 의해 다음과 같이 전개가 됩니다.

$E_{x,y} =\sum_{u,v} w_{u,v} {\left\lbrack I_{x+u,y+v} -I_{u,v} \right\rbrack }^2$

$=\sum_{u,v} w_{u,v} {\left\lbrack \mathrm{xX}+\mathrm{yY}+O\left(x^2 +y^2 \right)\right\rbrack }^2$

$I\left(x+u,y+v\right)=I\left(u,v\right)+x\frac{\delta I}{\delta x}+y\frac{\delta I}{\delta y}+O\left(x^2 +y^2 \right)$

$=\sum_{u,v} w\left(u,v\right){|x\frac{\delta I}{\delta x}+y\frac{\delta I}{\delta y}|}^2$

 small shift E는 다음과 같이 나타낼 수 있습니다.

$E\left(x,y\right)=Ax^2 +2\mathrm{Cxy}+By^2$

A,B,C coefficient는 I의 gradient x, gradient y, gradient xy 와 Gaussian filter을 convolution한 값입니다.

$A={\left(\frac{\delta I}{\delta x}\right)}^2 \otimes w$

$B={\left(\frac{\delta I}{\delta y}\right)}^2 \otimes w$

$C=\left(\frac{\delta I}{\delta x}\cdot \frac{\delta I}{\delta y}\right)\otimes w$

2. Gaussian filter를 사용해 Noise를 줄여준다.

Gaussian filter을 사용함으로써 smooth한 circular window를 사용합니다. 

$w_{u,v} =\mathrm{exp}-\frac{\left(u^2 +v^2 \right)}{2\sigma^2 }$

3. Shift방향에 맞는 E의 variation을 고려한다.

$E\left(x,y\right)=\left(x,y\right)M{\left(x,y\right)}^T$

$M=\left\lbrack \begin{array}{cc} A & C\\ C & B \end{array}\right\rbrack$

$\alpha$와 $\beta$를 M의 Eigen value라고 할 때 3가지 region이 존재하며 Corner region 의 point를 detect하는 것이 목적입니다.

• Flat region : $\alpha$와 $\beta$가 모두 작을 때
• Corner region : $\alpha$와 $\beta$가 모두 큰 값을 가질 때
• Edge region : $\alpha$와 $\beta$ 중 한 값은 작은 값을 가지고 다른 한 값은 큰 값을 가질 때

Region detection

다음과 같이 R함수를 정의할 때 R>0 이면 corner region, R<0 이면 edge region, R이 작을 경우는 flat region으로 정의됩니다.

$T_r \left(M\right)=\alpha +\beta$

$\mathrm{Det}\left(M\right)=\alpha \beta =\mathrm{AB}-C^2$

$R=\mathrm{Det}-k\cdot T_r^2$

 

출처 : A combined corner and edge detector - Chriss Haris & Mike Stephens (1988)