04-(1). Local Feature Detection

Computer Vision (오일석) Chapter 04

Contents

1. 지역 특징 검출의 기초

2. 이동과 회전에 불변한 특징점 검출 

3. 위치 찾기 알고리즘

4. 스케일에 불변한 특징점 검출

---

1. 지역 특징 검출의 기초

Q. 무엇을 특징점으로 쓸 것인가?

후보 1. Edge  →  3장의 Edge detection에서 공부하였다.

하지만, 에지가 갖고 있는 정보는 edge magnitude(에지 강도)와 edge direction(에지 방향)밖에 없기 때문에 특징점에 매칭하기에는 빈약하다.

 

따라서, 풍부한 정보를 지닌 특징점을 검출하는 새로운 접근 방식이 필요.

 

Local Feature(지역 특징)은 edge에 의존하는 대신, 명암 영상(gray scale)에서 직접 특징점을 검출한다.

기존의 Corner의 물리적인 의미를 중요하게 보았던 방법과 달리, 이런 새로운 대안은 검출된 특징의 물리적 의미에 신경쓰지 않고 대신 한 영상에서 검출된 특징이 다른 영상에서도 검출되기만 하면 된다는 입장이다. 

특징점☞ 물리적 의미 X, 반복성(Repeatability) 중요

 

Local Feature의 정보 구성 = <위치, 스케일, 방향, 특징 벡터>

(1) 검출 단계 = 위치, 스케일 확인

▷변환이 일어나도 같은 점에서 항상 같은 특징이 검출되어야 하기 때문에, 변환(e.g.물체의 이동, 회전, 스케일 변경)에 covariant(공변)이어야 함

▷하지만 물체 입장에서 보면 같은 곳이므로 불변이다.

▷공변과 불변 용어 혼동 주의. 특별한 경우를 제외하고 불변이라고 하자.

 

(2) 기술 단계 = 방향, 특징벡터 계산

▷특징 벡터를 추출하는 것이므로 불변이어야 한다.

 

지역 특징의 몇 가지 특성은 다음과 같다.

• 반복성 : 한 영상에서 검출된 특징은 다른 영상의 같은 물체에서도 동일한 속성값으로 검출되어야 한다. 이 특징이 만족되어야만 영상 사이의 대응점을 찾을 수 있고, object detection같은 과업도 달성할 수 있다.
• 분별력 : 다른 곳과 충분히 구분될 수 있을 정도로 두드러진 속성값
• 지역성 : 그 점을 중심으로 작은 크기의 주변 영역만 보고 특징 검출과 검출 기술이 수행되어야 한다.
• 정확성 : 정확한 위치
• 적당한 양 : 어떤 물체의 pose(위치, 방향)를 계산하기 위해서는 이론적으로 3개의 대응점만 있으면 된다. 하지만 대응점이 3개보다 많아지면 더 정확하게 pose추정 가능하다. 특징은 원천적으로 충분한 양을 얻어야 한다. 이러한 양을 적절하게 조절하기 위한 매개변수를 갖고 있다.
• 계산 효율 : 충분히 빠른 시간 안에 특징 정보를 추출해야 한다.

일반적으로 어느 응용에서든지 '반복성'이 가장 중요한 기준이지만, 실시간 처리가 필수적인 응용에서 높은 '반복성'이 '계산 효율'을 크게 떨어뜨린다면, 길항 관계에 의해 어느정도 반복성을 희생하는 것이 현명하다.

 

 

위 사진의 a,b,c중에 어떤 위치가 특징점으로 표시하기 좋을까?

☞ a에서 여러 방향으로 밝기 변화가 발생하기 때문에 a가 가장 유리할 것이고, c는 모든 방향으로 밝기 변화가 비슷하여 찾기 어렵다.

☞ b는 수직방향으로는 밝기 변화가 크지만 에지 방향(건물의 벽면)으로 변화가 적어서 검출하기 어렵다.

 

 

2. 이동과 회전에 불변한 특징점 검출

1절에서 특징점이 무엇인지, 그리고 어떻게 찾을지 기초적인 생각을 공유했다. 본격적으로 '어떻게' 찾을 것인지 여러 방법론을 알아보자.

0. Corner란?

Corner : point where two edges meet(서로 다른 두 엣지 선분이 만나는 지점)

 

1. Moravec 알고리즘

• 제곱차의 합, SSD(Sum of Squared Difference)을 이용한다.

SSD 연산

f(..) = 입력 영상

w(..) = 마스크(kernel처럼 역할) → w(y,x) : 현재 화소에 씌운 박스형 마스크

계산결과 생성되는 S(v, u) = (v,u)를 변화시켜가며 마스크 화소 각각에 대해 계산을 수행하여 얻어진 맵(map)

 

ex)

 

ㄴ 왼쪽 12x12 영상이 입력 영상(f)이다. 현재 시점의 조사 화소는 b(f(y,x))이다. 마스크는 3x3 box kernel(w(y,x))이다.

b에서 SSD연산을 통해 얻어진 S(0,1) 맵

▷a와 같은 코너에서는 모든 방향으로 변화가 심함

▷b와 같은 에지에서는 에지 방향으로 변화 적지만, 에지에 수직 방향(그래디언트 방향과 같다)으로 변화 심함

▷c와 같은 곳은 모든 방향으로 변화 적음

=> a에 높은 값, c는 아주 낮은 값, b는 그 사이 값을 부여하는 함수를 만들면 됨

 

함수S는 어떤 점이 다른 곳과 얼마나 두드러지게 다른지 측정해주는 역할을 한다. 여기서 a에 높은 값을 부여함으로써 S를 코너일 가능성 정보로 해석한다.

 

▶즉 어떤 점이 a와 같은 코너라면, S(0,1), S(0,-1), S(1,0), S(-1,0) 동서남북 네 방향으로 한 화소만큼 이동시켜 얻은 4개의 값 모두 값이 커야 한다고 보고, 이 네 값의 최솟값을 Local Feature(지역 특징)일 가능성 값으로 간주하였다.

모라벡이 정의한 지역 특징일 '특징 가능성'값

 

모리벡 방법으로 얻은 특징점은 여러 방향으로 변화가 커야 한다는 기본 원칙은 지켰으나, 실제 세계에서 획득되는 영상은

이 사진과같이 한 화소만큼 이동시켜 얻는 S값만으로는 특징점을 검출하기에 충분하지 않다. (여러 화소에 걸쳐 그래디언트가 발생하는 경우가 있기 때문이다)

 

2. Harris Corner

위와 같은 상황의 잡음에 대처하기 위해 박스형 마스크에서 중심으로부터 멀어질수록 서서히 값을 작게 하는 가우시안 마스크[G(y,x)]로 변경

• 가중치 제곱차의 합(WSSD, Weighted Sum of Squared Difference)을 이용한 함수로 확장(1로 구성된 박스형마스크가 아니기 떄문에 가중치의 역할)
• 이를 통해 특징이 될 가능성을 좀 더 정밀하게 측정 가능

WSSD 연산

 

모라벡 알고리즘에서는 한 화소씩만 이동시켜서 동서남북 방향으로만 조사했기 때문에 360도 모든 방향을 동등하게 취급하는 '등방성'을 만족하지 못하는 문제가 발생한다.

▷ 미분을 도입하여 문제를 해결

Taylor's expansion

테일러 확장(4.4)를 (4.3)식에 대입하여 얻는다 -> 모라벡의 식이 헤리스의 식으로 진화

 

식 (4.5)의 헤리스 식이 '특징일 가능성'을 계산하는 과정은 다음과 같이 유도된다.

S(v,u)의 재구성

 

이 때, 가운데 행렬 A의 모든 원소는 convolution연산으로 계산되는 값이므로 아래와 같이 최종적으로 표현할 수 있다

S(v,u) = uAu'로 표현됨

가운데 행렬 A를 '자가 공관계 행렬' 또는 '2차 모멘트 행렬'로 부르기도 한다.

[2차 모멘트 행렬이 갖는 의의]

▷A를 (v,u) 무관하게 계산할 수 있음 (∵ S가 u와 A의 곱으로 인수 분해되어 있으므로)

▷(v,u)는 정수뿐만 아니라 실수도 가능

▷A자체가 영상의 구조를 나타낸다. 따라서 A를 잘 분석하면 특징의 여부를 판정할 수 있다.

    영상 구조 = 명암 변화의 모양. 즉, 변화의 형태와 정도 따위를 의미

 

람다1, 람다2 = 2차 모멘트 행렬 A의 고유값

k는 보통 0.04값을 이용한다고 알려짐

'특징 가능성 값' 측정

cf)

아래의 C 계산 식은 A행렬의 고유값 계산을 피함으로써 속도를 향상할 수 있다.

어쨌든 위의 C를 통해 (y,x)가 Corner일 가능성을 측정하는 수치를 계산할 수 있다.

참고. <2023.2학기 패턴인식 교과목 수업자료 중>

 

C를 threshold T와 비교해서 C>T인 지점을 corner로 판정하게 된다.

이렇게 검출된 특징점은 변화가 심한 곳이고, 특히 변화가 심한 곳은 한 점으로 집중되지 않고  점들이 여러 개로 퍼져서 검출되었음을 관찰할 수 있다.

이런 여러 점들을 한 점으로 지정하는 'Localization'문제가 대두되는데, 이전에 배운 NMS(Non-Maximum-Suppression)방법으로 해결할 수 있다.

참고. <2023.2학기 패턴인식 교과목 수업자료 중>

참고로, Corner는 점차적으로 코너라는 용어보다 '특징점(feature point)' 또는 '관심점(interest point)'라는 용어를 주로 사용하게 된다.

 

3. 2차 미분을 사용한 방법

헤리스 코너 방법은 1차 도함수로 정의되는 2차 모멘트 행렬 A를 이용한 방법이지만, 2차 도함수를 이용해 특징점 검출하는 방법도 있다.

• 헤시안 행렬 H

하지만 미분은 잡음을 증폭시키고, 2차 미분은 noise 문제가 더 심각해지기 때문에 이것을 그대로 사용하지 않는다.

Gaussian kernel로 먼저 Smoothing을 진행한 후, 2차 미분을 수행한다.

 

가우시안을 포함한(스무딩 적용후 미분) H행렬

위의 행렬 H에서 행렬식(determinant)값 & 가우시안 라플라시안(Laplacian of Gaussian)값 두 가지를 계산하여 '특징 가능성 값'으로 사용한다.

이때 LoG는 엣지 검출할 때 ㅆ쓰였던 연산자와 같은 것이다. 이 연산자는 edge에 민감하게 반응하므로, edge를 걸러주는 후처리가 필요하다. 

 

4. SUSAN

= Smallest Univalue Segment Assimilating