Feature detection의 역사

전종원·2022년 10월 1일

1. Line detection(~1980)

line detection
sobel operator -> gradiant operation을 이용한 line detection
hough transform -> 안정적인 라인들만 검출하는 기법.
canny edge detection -> 사용자가 원하는 edge의 strength를 지정가능. but 계산량이 많음.

여기서 생긴 의문: 멀리서 서로 다른 각도에서 찍은 물체를 어떻게 같은 물체로 인식할 수 있을까?
gradiant?
line&line dot product->point
line&line cross product->plane

이중 point를 이용한 연구가 활발히 이루어져왔다.

2. Point Feature

2.1. 용어정리

keypoint detector

pixel location of interesting point

Descriptor extractor

describing the patch around key point

Correspondence matcher

finding similarity between descriptors between 2 images

local feature

features in local scale

2.2. Corner detection by Moravec(1980)

Moravec은 코너검출을 성공적으로 했던 사람입니다. 1980년에 나온 Moravec의 박사논문에서는 검출된 코너들을 이용하여 연속된 프레임에서 로보스이 움직임을 감지하는 기법을 소개했습니다. 픽셀들을 기준으로 상,하,좌,우의 gradient를 계산하여 코너여부를 판단하도록 하는 알고리즘을 사용하였습니다.

2.3. Harris Corner(1988)

Moravec의 4방향 gradient 분석기법 대신 x방향과 y방향의 gradient만 분석하고 이 정보를 이용하여 코너의 방향성을 나타낼 수 있는 행렬을 만들었습니다. 만들어진 행렬의 고윳값이 곧 해당 코너의 방향성으로 표현되었습니다. 여기에 수학적으로 flat/edge/corner 여부를 판단하는 기술인 corner-ness score가 더해져 기존 Moravec의 방법보다 더 robust한 코너검출이 가능해졌습니다. Harris Corner는 이미지 내에서 제대로된 코너검출이 가능하다는 것이 증명된 셈입니다.

2.4. SIFT(2002)

SIFT는 딥러닝 기반 feature detection 기법이 등장하기 전까지 가장 좋은 성능을 보였던 코너검출방식입니다. 심지어 딥러닝을 기반 코너검출을 제안하는 논문들에서 SIFT 방식을 성능평가지표로 자주 사용하는 것을 보 수 있습니다. SIFT는 이미지피라미드에 가우시안블러처리를하고 가우시안 블러 처리를 한 이미지들 사이의 차이(Difference of Gaussian: DOG)를 이용하여 scale-invariant, rotation-invarient한 코너검출을 가능하게 했습니다. SIFT는 descriptor 또한 제공합니다. 16x16의 패치를 만들어 탐색 후 패치안에 있는 픽셀들의 gradient를 계산하고 이 gradient로 히스토그램을 생성해 descriptor를 생성합니다. 이는 많은 연산량을 요구합니다.

2.5. FAST(2006)

Harris코너검출방식보다 17배, SIFT보다 42배 빠른 스피드를 자랑하는 코너검출방식입니다. descriptor가 없어 매칭은 진행하지 않지만 keypoit detection만 하더라도 굉장히 빠른 속도를 자랑하여 현재까지 널리 쓰이고 있습니다. 연산속도가 빠르므로 빠른동작과 방향전환에 robust한 특징을 가집니다. FAST는 픽셀 주변의 16개의 픽셀을 확인하여 그중 10개의 연속된 픽셀들의 픽셀값이 나머지 6개의 픽셀값보다 밝거나 어두우면 코너로 인식합니다.

2.6. BRIEF descriptor(2010)

2010년에 Calonder는 SIFT가 굉장히 많은 연산량을 요구한다는 점을 지적하며 바이너리 데이터로만 이루어진 descriptor를 제안하였습니다. 이와 동시에 다양한 descriptor들 간 유사도를 측정해 가장 비슷한 descriptor를 찾아 매칭시켜주는 FLANN 라이브러리가 소개되었습니다.

2.7. ORB(2011)

FAST는 scale-invarient하지 않다는 문제가 있었고 BRIEF descriptor는 Rotation-invarient하지 않다는 문제가 있었습니다. ORB는 FAST 코너검출을 사용하고 BRIEF descriptor를 사용하여 scale-invarient하고 rotation-invarient하면서 실시간으로 작동되도록 하였습니다. ORB의 동작방식은 다음과 같습니다.
이미지피라미드를 만들어 각 scale별로 FAST 코너검출을 시행하여 scale-invarience를 잡았습니다. 코너를 추출할 때 keypoint 주변 픽셀들의 gradient를 계산해 코너의 방향성을 추측하고 그 방향에 맞춰 BRIEF를 뽑아냄으로써 rotation-invarience를 가지도록 하였습니다.