불변특징 SIFT와 응용 제5회 컴퓨터비전 및 패턴인식 겨울학교, 2011년 2월 21-22일, 전북대학교

Presentation on theme: "불변특징 SIFT와 응용 제5회 컴퓨터비전 및 패턴인식 겨울학교, 2011년 2월 21-22일, 전북대학교"— Presentation transcript:

1 불변특징 SIFT와 응용 제5회 컴퓨터비전 및 패턴인식 겨울학교, 2011년 2월 21-22일, 전북대학교
2011년 2월 22일 오일석 전북대학교 컴퓨터공학부

2 차례 동기 SIFT 특징 추출 특징 매칭 성능 응용 참고 자료

3 동기 - 장면의 다양성

4 동기 -과업의 다양성 차량 번호를 인식하라. 검색하라. 무슨 식물? 한글로 번역하라. 이상 징후를 찾아라. 뭐 하는 상점?
내일 날씨는? BigDog 몇 명인가? 문을 열어줄까? 웅덩이를 피하라. 전투 로봇 공습 목표물은 어디에?

5 찾는 물체가 영상 속에 있나? 그렇다면 어떤 포즈(pose)인가?
동기 - 물체 인식 찾는 물체가 영상 속에 있나? 그렇다면 어떤 포즈(pose)인가? 물체 인식은 전형적인 문제 (이걸 풀면 다른 문제도 풀린다.) 가림(occlusion)이 있고 clutter된 상황에서의 물체 인식

6 동기 - 인간 시각과 기계 시각 인간 시각 기계 시각 매우 강인
선택적 주의 집중 (selective attention) 뛰어남 기계 시각 특정 상황의 특정 목적에서만 쓸모 있는 성능 State of the art Computer vision is a diverse and relatively new field of study. In the early days of computing, it was difficult to process even moderately large sets of image data. It was not until the late 1970s that a more focused study of the field emerged. Computer vision covers a wide range of topics which are often related to other disciplines, and consequently there is no standard formulation of "the computer vision problem". Moreover, there is no standard formulation of how computer vision problems should be solved. Instead, there exists an abundance of methods for solving various well-defined computer vision tasks, where the methods often are very task specific and seldom can be generalised over a wide range of applications. Many of the methods and applications are still in the state of basic research, but more and more methods have found their way into commercial products, where they often constitute a part of a larger system which can solve complex tasks (e.g., in the area of medical images, or quality control and measurements in industrial processes). In most practical computer vision applications, the computers are pre-programmed to solve a particular task, but methods based on learning are now becoming increasingly common. (Wikipedia)

7 동기 - 어려움을 일으키는 한 가지 요인 실제 영상에는 다양한 변화가 나타난다. 조명 조명+크기 조명+크기+회전
조명+크기+회전+어파인

8 지역특징(local feature)의 조건
동기 - 고성능 특징이 필수적이다. 지역특징(local feature)의 조건 불변성 (invariant) 변화된 환경에서도 반복하여 나타나는 특성 (재현성 (repeatability)) 조명 불변 크기 불변 회전 불변 잡음 불변 풍부한 정보 (rich description) 강한 분별력 (distinctiveness) 계산 효율 (추출, 매칭)

9 동기 - SIFT의 등장 SIFT의 창안 등장 배경
Lowe, David G. (1999). "Object recognition from local scale-invariant features". Proceedings of the International Conference on Computer Vision. pp. 1150–1157. 불변성이 강한 지역 특징 (local feature) 등장 배경 Scale-space theory [Lindeberg94] ‘deep structure’ (feature structure between different scales)

10 위키피디아 정의 Scale-invariant feature transform (or SIFT) is an algorithm in computer vision to detect and describe local features in images. The algorithm was published by David Lowe in 1999. Applications include object recognition, robotic mapping and navigation, image stitching, 3D modeling, gesture recognition, video tracking, and match moving. The algorithm is patented in the US; the owner is the University of British Columbia. …. David Lowe Computer Science Department University of British Columbia

11 SIFT 특징 추출 추출 과정 키포인트 탐지 (keypoints detection) Scale-space에서 극점 탐지
잡음 극점 제거 기술자 추출 (descriptor extraction) 방향 결정 그라디언트 히스토그램 계산

12 SIFT는 scale space에서 작업함으로써 크기 불변성 달성
갈수록 큰 σ의 Gaussian으로 컨볼루션 Resampling으로 pyramid 구성 DOG (Difference of Gaussian)

13 SIFT 특징 추출 – 키포인트 탐지 수식으로 써 보면, 스케일 σ인 가우션으로 컨볼루션된 영상 L DOG 영상

14 SIFT 특징 추출 – 키포인트 탐지 키포인트 탐지
모든 DOG의 모든 점에 대해 극점 (maxima 또는 minima) 조건 검사 통과한 점은 후보 키포인트가 됨 인근 8개와 위 아래 영상의 18개 (총 26개) 점과 비교

15 SIFT 특징 추출 – 키포인트 탐지 잡음 극점 제거 낮은 대비(contrast) 극점 제거 에지에 놓인 극점 제거 극점
낮은 대비 극점 제거 에지 극점 제거

16 SIFT 특징 추출 – 기술자 추출 Dominant한 방향 결정
키포인트에 대해, 방향 히스토그램을 구하고, 가장 강한 방향을 키포인트의 방향으로 결정 가장 강한 것 대비 80% 이내의 방향을 위한 별도의 키포인트 생성 이제 키포인트는 위치, 스케일, 그리고 방향을 가지고 있다. 이후 모든 정보는 이들 값을 기준으로 추출한다.  방향 불변성 달성

17 SIFT 특징 추출 – 기술자 추출 또 다른 예

18 SIFT 특징 추출 – 기술자 추출 그라디언트 히스토그램
키포인트 주위에서 4*4 크기의 영역을 n2개 (n*n) 만듦 (아래 그림에서 n=2) 각 영역에 대해 8-방향 계산하고 (이때 키포인트 방향을 기준으로 계산하여, 방향 불변성 달성) 히스토그램 구함 오른쪽과 같이 n=2인 경우, 4 영역 각각이 8 방향의 히스토그램을 가지므로, 기술자는 32개의 특징을 갖는 특징벡터로 표현된다. n=4이면, 4*4*8=128개의 특징.

19 SIFT 특징 추출 – 기술자 추출 키포인트 기술자 정보 위치, 스케일, 방향
그라디언트 히스토그램 (아래 경우 4*4*8 특징벡터)

20 특징 매칭 특징 매칭은 물체 인식의 핵심 연산 물체 모델 영상 (training image)에서 SIFT특징을 추출하여 데이터베이스에 저장 (오프라인 과정) 테스트 영상이 입력되면, 거기에서 SIFT특징을 추출하고, 데이터베이스의 특징과 매칭 (온라인 과정) 특징 데이터베이스 Test image Object model (train image) 오프라인으로 이루어짐 온라인으로 이루어짐

21 특징 매칭 매칭 과정 최근접 이웃 탐색 (nearest-neighbor search)
Hough 변환을 이용하여, 매칭된 키포인트 클러스터 찾기 Linear least squares로 검증 Outlier 처리

22 키포인트 매칭을 어떻게 할 것인가? – 계산 효율이 핵심
특징 매칭 – 최근접 이웃 탐색 키포인트 매칭을 어떻게 할 것인가? – 계산 효율이 핵심 m과 n은 보통 수천~수만 개 n개 각각에 대해, m개 중에서 최근접 이웃을 탐색해야함 O(mn) 계산 복잡도 특징 데이터베이스 Test image Object model (train image) n개의 키포인트 m개의 키포인트

23 특징 매칭 – 최근접 이웃 탐색 k-d tree 사용
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key. … (wiki) “Exact” solution method A 3-dimensional kd-tree. The first split (red) cuts the root cell (white) into two subcells, each of which is then split (green) into two subcells. Finally, each of those four is split (blue) into two subcells. Since there is no more splitting, the final eight are called leaf cells.

24 BBF (best-bin first) 방법
특징 매칭 – 최근접 이웃 탐색 BBF (best-bin first) 방법 ‘Approximate’ solution method Heap을 사용하여 효율적인 탐색 순서 결정 5% 가량의 손실(틀린 매칭)을 희생하여 수백 배 빠르게 작동함

25 성능 - 어파인 변화에 대한 민감도 분석

26 성능 – 다른 지역 기술자와 비교 아주 많은 다른 기술자들 성능 비교 작업 [Mikolajczyk2005]
SURF, RIFT, PCA-SIFT, ASIFT, GLOH 등 성능 비교 작업 [Mikolajczyk2005] “… we observe that the ranking of the descriptors is mostly independent of the interest region detector and that the SIFT-based descriptors perform best. …”

27 응용 – panorama stitching [Brown2003]

28 응용 – panorama stitching
… We have used local invariant features to allow panorama matching to be fully automated without assuming any ordering of the images or any restriction on focal lengths, orientations, or exposures. The matching time is linear in the number of images, so all panoramas can be automatically detected in large sets of images. We have also developed approaches for seamlessly blending images even when illumination changes or there are small misregistrations. 

29 응용 – 로봇 localization and mapping [Se2001]
SLAM (Simultaneous Localization and mapping) 달성

30 응용 – 로봇 localization and mapping [Se2001]

31 응용 – 증강현실 [Gordon2006]

32 응용 – 스마트폰 증강현실 [Wagner2010] PhonySIFT 모바일 폰을 위해 개조된 SIFT 계산 속도 향상 방법
계산량이 많은 DOG 대신 corner 사용 4*4영역*8bins=128개 특징 대신, 3*3영역*4bins=36개 특징 사용 (10%미만의 성능 저하) 매칭에 k-d 트리 대신 spill 트리 사용

33 FBM (Feature-based morphometry)
응용 – 의료 영상 [Toews2010] FBM (Feature-based morphometry) 기존 모델 기반 방법의 한계 극복 (모델 기반 방법은 개인의 특성을 잘 반영하지 못함)

34 응용 – 의료 영상 [Toews2010] 적용 예) 알츠하이머 환자 자동 그룹핑

35 응용 – 사람 행위 인식 [Laptev2004] 3-D sift (x-y-t)

36 응용 – 사람 행위 인식 [Laptev2004]

37 응용 – 간판 인식 전주 한옥마을 간판 영상 데이터베이스
50종류의 간판 각각에 대해 50장씩의 영상 (총 2500장, 480*640해상도)

38 응용 – 간판 인식 실험 결과 매칭된 키포인트 수가 가장 많은 간판 부류로 분류하는 간단한 규칙으로 98%인식률

39 참고 자료 오픈소스 Rob Hess (School of EECS, Oregon State University)
“My Open-Source SIFT Library just won second place at the ACM Multimedia 2010 Open-Source Software Competition.  The competition was stiff, …” (Lowe의 데모 프로그램)

40 참고 자료 문헌들 Lowe가 SIFT를 제안 D.G. Lowe, "Object recognition from local scale-invariant features," Proceedings of the International Conference on Computer Vision, pp. 1150–1157, 1999. D.G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, Vol.60, No.2, pp , 2004. Scale-space와 지역 기술자 튜토리얼 Tony Lindeberg “Scale-space theory: A basic tool for analysing structures at different scales,” J. of Applied Statistics, vol.21, No.2, pp. 224–270, 1994. T. Tuytelaars and K. Mikolajczyk, “Local invariant feature detectors,” Foundations and Trends in Computer Graphics and Vision, Vol.3, No.3, pp , 2007. 지역 기술자의 성능 비교 K. Mikolajczyk, and C. Schmid, "A performance evaluation of local descriptors", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp , 2005. 응용 D. Wagner, G. Reitmayr, A. Mulloni, T. Drummond, D. Schmalstieg, “Real-time detection and tracking for augmented reality on mobile phones ,” IEEE Transactions on Visualization and Computer Graphics, 2010. S. Se, D.G. Lowe, J. Little, "Vision-based mobile robot localization and mapping using scale-invariant features," Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp.2051, 2001. M. Brown, D.G. Lowe, "Recognising panoramas," Proceedings of the ninth IEEE International Conference on Computer Vision, pp.1218–1225, 2003. Iryna Gordon and D.G. Lowe, "What and where: 3D object recognition with accurate pose," in Toward Category-Level Object Recognition, Springer-Verlag, pp , 2006. I. Laptev and T. Lindeberg, "Local descriptors for spatio-temporal recognition". ECCV'04 Workshop on Spatial Coherence for Visual Motion Analysis, (LNCS Volume 3667), pp. 91–103, 2004. Matthew Toews, William M. Wells III, D. Louis Collins, Tal Arbel, "Feature-based morphometry: discovering group-related anatomical patterns," NeuroImage, Vol.49, No.3, pp.2318–2327, 2010.