크기 불변 특징과 SIFT 알고리즘

크기 불변 특징

  • 오른쪽의 큰 이미지에서 왼쪽에 있는 박스 이미지가 어디에 어떻게 놓여있는지 매칭한 결과를 보여주고 있음
  • 오른쪽의 큰 이미지에서 책이 살짝 가려져있음에도 크기를 잘 인식하는것을 확인할 수 있음

image

영상의 특징 중에서 코너의 특징

  • 평탄한 영역, 에지 영역에 비해 변별력이 높음
  • 이동, 회전 변환에 강인

  • 크기 변환에 취약

  • 코너는 객체를 보는 Scale에 따라 코너가 아닌 것 처럼 검출될 가능성이 높음
    • 여전히 코너로 검출하기 위해서는 다양한 크기 관점에서 특징을 검출할 필요가 있음
    • 코너를 검출하려고 하는 사각형의 크기를 키움
    • 그렇게 되면 이동, 회전, 크기 변환 모든 면에서 강인한 형태로 동작하는 효과적인 특징으로 사용할 수 있음

image

크기 불변 특징점

  • 스케일 스페이스(scale-space) 또는 이미지 피라미드(image pyramid)를 구성하여 영상의 크기가 바뀌더라도 반복적으로 검출될 수 있는 특징점을 찾으면 매칭 등의 응용에서 사용할 수 있음
    • 스케일 스페이스 : 다양한 크기와 좀 더 블러링된 여러가지 형태의 이미지 세트를 만들어 사용하는 것
    • 이미지 피라미드 : 다양한 크기의 이미지를 만들어서 이미지 세트를 사용하는 것

image

  • 주요 크기 불변 특징점 알고리즘 SIFT, SURF, KAZE, AKAZE, ORB 등
  • 특징점(feature point) ≈ 키포인트(keypoint) ≈ 관심점(interest point)
  • 기술자(descriptor) ≈ 특징 벡터(feature vector)

SIFT

  • Scale Invariant Feature Transform

  • 총 4가지 단계로 구성되있음

    • 1,2번은 keypoint를 이미지에서 검출하는 단계
    • 3,4번은 위에서 검출된 keypoint 위치에서 근방의 부분영상을 추출하여 부분영상으로부터의 특징벡터를 추출하는 단게

image

Detector
  • 스케일 스페이스 구성하기
    • 맨 밑에 있는 원본영상을 블러링을 진행함
    • 원본 영상 크기의 가로, 세로를 반으로 줄여 1/4 영상을 만들어 또 블러링을 진행함
    • 블러링 된 하나의 세트를 octave라고 표현함
    • 블러링된 영상과 블러링 전의 영상의 차인 차영상(Difference of Gaussian, DOG)을 만듬

image

  • DOG 중 회색으로 된 부분은 차이가 없는 부분이고 검정색 부분이나 조금 밝은 부분이 차이가 있는 곳

image

  • 키 포인트 찾기(keypoint localization)
    • LOG 대신 DOG 영상의 모든 점에서 local maxima 또는 local minima를 선택
    • 동일 스케일 DOG 영상에서 주변 8개 점과 상/하 스케일 DOG 영상에서 18개 점, 총 26개 점을 비교하며 지역 최솟값 또는 지역 최댓값을 선택

image

  • 코너 부근쪽의 키포인트들로 다시 찾기

    • 실수 단위의 좀 더 정확한 위치에서의 코너점을 찾는 서브픽셀 정확도 추가

    • 평탄한 지역들의 Contrast가 낮은 극점을 제거

    • 엣지보다 코너가 변별력이 높으므로, 엣지에 가까운 키포인트는 제거

    • 작업을 거친 키포인트 점들은 회전이 되거나 이미지의 스케일 변환을 해도 다시 검출될 가능성이 높음

image

Descriptor
  • 방향 불변 특성을 위한 주 방향 성분 추출
    • 키포인트 근방의 부분 영상을 추출
    • 부분 영상의 모든 픽셀에서 그래디언트 성분(크기 & 방향)을 계산
      • 방향 성분에 대한 히스토그램을 생성(360도에 대해 36개 빈)
    • 히스토그램 최댓값 방향과 최댓값의 80% 이상 크기를 갖는 빈 방향을 설정
      • 하나의 좌표에서 여러 개의 키포인트 표현 가능

image

  • 각 키포인트에 대해 기준 방향 성분을 설정
    • 각 키포인트는 위치, 스케일, 기준 방향 정보를 가지는데 이를 토대로 크기, 방향에 불변한 특징 벡터를 추출
      • 스케일은 화살표의 길이와 연관

image

  • 키포인트 기술자(descriptor, feature vector)

    • 각 키 포인트 위치에서 스케일과 기준 방향을 고려하여 사각형 영역을 선택
    • 사각형 영역을 4 x 4 구역으로 분할하고, 각 구역에서 8방향의 방향 성분 히스토그램을 구함
      • 4 x 4 x 8 = 128 차원의 벡터 (float 자료형)
    • 128 개의 방향 히스토그램을 이용해서 키포인트 근방의 부분 영상 1 개의 정보를 128 개의 실수 값으로 표현
    • 128 x 4byte(float) = 512byte를 사용
    • 어떤 이미지에서 1000개의 키포인트가 검출되면, 512Kbyte가 키포인트의 기술자를 표현하는데 사용됨

image

  • 레나 영상에서 구한 SIFT 기술자의 예
    • 각자의 특징점에서 주된 방향 성분이 1개, 2개, 3개등으로 표현될 수 있음

image

  • SIFT 사용 예#1
    • 다른 이미지에서 왼쪽의 기차와 개구리가 다른 물건에 가려져 있어도 잘 찾아줌

image

  • SIFT 사용 예#2
    • 파노라마 이미지(영상 이어붙이기)

image

SIFT 사용 예#3

  • 화성 탐사 로봇이 자신의 위치를 파악하기 위해 사용

image

기타 특징점 알고리즘

  • SURF(Speed-Up Robust Features)
    • SIFT를 기반으로 속도를 향상시킨 크기 불변 특징점 검출 방법
    • DOG(Derivative of Gaussian) 함수를 단순한 이진 패턴으로 근사화
    • 적분 영상(integral image)를 이용하여 속도 향상
  • KAZE
    • KAZE(바람) : 비선형 스케일 스페이스에서 공기의 흐름
    • 가우시안 함수 대신 비선형 확산 필터(nonlinear diffusion filter)를 이용하여 특징점을 검출
    • SURF 보다는 느리지만 SIFT보다 빠르고 동등한 성능

  • BRIEF(Binary Robust Independent Elementary Features)

    • 이진 기술자를 이용한 빠른 키포인트 기술 방법 (Not detector!)

    • 키포인트 주변 픽셀 쌍을 미리 정하고, 픽셀 값의 크기를 비교하여 0 또는 1로 특징을 기술

    • 매칭시 해밍 거리(Hamming distance) 사용
      • 해밍 거리 : 2개의 이진수의 나열이 있을 때 서로 다른 비트가 몇 개인지 count
  • ORB(Oriented Fast and Rotated BRIEF)
    • Corner detection인 FAST 방법으로 키포인트를 찾고 Harris 코너 방식으로 순위를 매김
    • 피라미드 영상에 적용하여 크기 불변성 확보
    • 키포인트의 방향 성분을 이용하여 BRIEF 방법에서 픽셀 쌍의 좌표를 회전하여 특징 벡터를 추출(이진 기술자)
    • 피라미드 영상을 사용하여 스케일 스페이스를 사용하는 다른 알고리즘보다 훨씬 빠르고 거기에 엄청나게 빠른 Corner Detection인 FAST 방법을 사용하고 좀 더 간단한 형태의 이진 기술자를 사용해서 기존에 나온 특징점 알고리즘 보다 월등히 빠르고 성능도 나쁘지 않음
    • OpenCV에도 최적화 되어있음
  • AKAZE(Accelerated KAZE)
    • KAZE 알고리즘의 속도 향상 버전으로 이진 기술자를 사용
    • 비선형 공간에서 피라미드를 구축