Computer Vision - Corner Detection

1. Corner Detection

- 위의 5가지 요구조건을 만족시키기 위해서 코너검출기는 시대에 따라 발전해왔다.

- sliding window를 사용한다.

- edge를 탐색했던 알고리즘은 한 방향으로의 intensity 차이에 주목했지만 corner는 any direction에서 intensity차이를 주목한다.

- "edge"의 경우 윈도우를 위아래로 shift시켰을때 intensity차이는 없고 좌우로 sift시켰을때 intensity차이가 크다. 

- "corner"의 경우 모든 방향에서 shift시켰을때 intensity차이가 크다.

- 이렇게 corner라고 판정하자는 관점을 Moravec이라는 분이 초창기에 제안했다.

- 마스크를 u,v만큼 shift한 결과와 원본 마스크의 차이를 구한다. 

- x,y는 마스크의 크기, w는 마스크의 모양을 나타낸다. 마스크의 모양, window function은 box 혹은 gaussian을 사용할 수 있다.

- a,b,c지점에서 변화량의 결과를 살펴보면 특징이 더 두드러진다.

- c같은 경우는 어디로 shift해도 변화량이 작다.

- b는 위아래는 변화량이 작은데 좌우는 크다. 즉 에지라고 볼수 있다.

- a의 경우는 모든 방향으로 shift했을때 변화량이 크다.

2. 테일러 변환을 통한 근사

- 어떤 함수 f(x)에 대해서 f(xi)는 알고 있는데 f(xi+1)를 구하기 어려울때, 미분을 통해 함수값을 근사하는 방법이다. 

- 이를 활용하면 f(x)를 다항식으로 근사하는것도 가능하다. 이를 taylor series라고 한다.

- f(x)가 누구인지는 모르지만 미분을 활용해 다항식 꼴을 만들어 근사한다.

- 2차 항까지만 고려하면 f(x)근사 결과는 위와 같다.

- 그럼 다시 corner detection으로 돌아와보자.

- 결국은 shift를 했을때 차이를 구해야하지만. shift를 실제로 하지는 않고 미분을 활용하여 shift했을때 픽셀값을 예측하면 E(u,v)를 아래처럼 표현할 수 있다.

- (0,0)을 중심으로 미분을 통해 근사하면 E(u,v)는 위와 같다.

- 참고로 Euv(0,0)은 0,0에서 u,v방향으로의 gradient를 나타낸다.

- 정리하면 E(u,v), u,v방향으로 slide했을 때, 픽셀값들의 차이를 approximation하는 것.

- Ix는 dI/dx, Iy는 dl/dy이다. 이렇게 M을 구하면 된다.

- 결국 E(u,v)는 [u v] M [u v] 로 근사된다. 

3. Eigenvalue, Eigenvector

- window function까지 고려해서 M을 나타내면 위와 같다.  그럼 이 M의 의미를 기하학적으로 이해해보자.

- [u v] M [u v] 이 형태는 quadradtic form을 이룬다고 한다. 그래서 이 M을 second moment matrix라고 한다.

- eigenvalue를 구하면 위처럼 표현 가능하다. M이 대칭행렬이기 때문에 eigenvalue는 실수이고 서로 직교(eigenvector가 orthogonal)한다.

*참고로 어떤 선현 변환 후에도 방향이 변하지 않는 벡터를 eigenvector(고유벡터), 변환후 eigenvector가 변하는 비

율을 eigenvalue(고유값, 람다)라고 한다.

*위 수식에서는 x가 eigenvector, 람다가 eigenvalue가 된다.

- edge, flat, corner 패치들에 대한 x, y 미분값들을 살펴보면 그 특징이 잘 보인다.

- Ix는 dI/dx, Iy는 dl/dy이다. 

- eigenvalue값이 둘다 작으면 변화량이 거의 없다는 뜻이고 모두 크면 corner 하나만 크면 edge라고 판단할 수 있다.

- 즉 타원이 그려지고 람다1, 람다2에 따라 모양이 달라진다.

- eigenvalue값이 둘다 작으면 변화량이 거의 없다는 뜻이고 모두 크면 corner 하나만 크면 edge라고 판단할 수 있다.

4. Harris Detector

- 고유벡터를 구하는게 오래걸리니 그냥 determiant와 trace만으로 코너를 판별할 R을 구한다.

1. Gaussian 을 1차 미분한 mask를 각 픽셀에 대해 계산(convolution)하여 noise를 없앤다.

2. M을 구한다. 

2. R을 구한다. (수식의 증명은 생략, harris corner detector는 람다(고유벡터)를 구하지 않고 M의 determinant와 trace만으로 R을 구한다.)

3. R값에 따라서 corner인지 edge인지 판단한다.

- determinant와 trace는 위처럼 구한다.

 

5. Source Code

- 단순히 변화량만 조사해서 가장 큰 극점을 코너로 판단한다.

- eigenvalue를 구해서 corner, edge, flat 판단을 한다.

- eigenvalue를 직접구하지 않고 determinant와 trace만으로 corner를 검출하는 harris corner detector이다.