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

Slides:



Advertisements
Similar presentations
Computer Science and Engineering. 컴퓨터는 미래 지식 사회의 핵심 요인  지식 사회의 도래 : 매 50 년 마다 큰 기술, 사회적 변화 발생.
Advertisements

소프트웨어 프로세스. 1 내용  소프트웨어 프로세스  생명주기의 의미  생명주기 모델 –Waterfall Model –prototyping model –Spiral Model –Iteration Model.
현재 시제 과거 시제 2-1. 한국어의 과거시제 : 영어 과거시제 + 현재완료 한국어의 과거시제는 영어의 과거 시제와 현재완료의 개념을 포함한다. I hate him. He is rich 현재의 일 I enjoy listening to music. I take.
2012 Knowledge Service Engineering Knowledge Service Engineering.
인공지능 소개 부산대학교 인공지능연구실. 인공 + 지능 인공지능이란 ? 2.
김예슬 김원석 김세환. Info Northcutt Bikes Northcutt Bikes The Forecasting problem The Forecasting problem The solution 1~6 The.
도 입 Introduction 여러분 중에 부모인 분 손들어보세요. How many of you are parents? 여러분의 아이가 태어난 날부터 아이의 성장을 위해 어떤 방법으로 아이를 키우시겠습니까 ? What specific ways are you concerned.
School of Computer Science and Engineering Seoul National University
Master Thesis Progress
Award winning Business database
Automated Target Tracking & Pan-tilt Camera Tutor : 고형화 손채봉 Studied by : 오재도 최재형 이희웅 정종윤 2008 Capstone Project.
Computer Graphics 한신대학교 컴퓨터공학부 류승택 2015년 2학기.
4강 10번 The entrepreneurial journey brings with it ______ .
Development and Initial Validation of Quality-of-Life Questionnaires for Intermittent Exotropia Ophthalmology 2010;117:163–168 Pf. 임혜빈 / R2 정병주.
Snake : Active Contour Model Computer Vision & Pattern Recognition
IC DESIGN LAB SOGANG UNIVERSITY 서강대학교 집적회로설계 연구실 2013
강좌 개요 2009년 1학기 컴퓨터의 개념 및 실습.
분자 동역학 컴퓨팅 전승준 (고려대학교 화학과).
REINFORCEMENT LEARNING
Internet Computing KUT Youn-Hee Han
International Marketing: STP 전략
SIFT & SURF.
분자 동역학 컴퓨팅 전승준 (고려대학교 화학과).
EPS Based Motion Recognition algorithm Comparison
외국인과 대화를~~ 대학에서 교환학생을~~
On the computation of multidimensional Aggregates
포항공과대학교 COMPUTER VISION LAB. 석박통합과정 여동훈
Accelerometer Data Collection and Preprocessing
6장. 물리적 데이터베이스 설계 물리적 데이터베이스 설계
Computational Finance
Genetic Algorithm 신희성.
3D Vision Lecture 7 동작 이해 (광류).
제 14 장 거시경제학의 개관 PowerPoint® Slides by Can Erbil
1 도시차원의 쇠퇴실태와 경향 Trends and Features of Urban Decline in Korea
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
for Robust Facial Landmark Localization
Xen and the Art of Virtualization
4-1 Gaussian Distribution
Parallel software Lab. 박 창 규
PCA Lecture 9 주성분 분석 (PCA)
Structural Dynamics & Vibration Control Lab., KAIST
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
패러다임과 과학혁명.
Past, Present, and Future Trends
1장. 소개.
정보 추출기술 (Data Mining Techniques ) : An Overview
Course Guide - Algorithms and Practice -
Bioinformatics and Biomedical Imagining 연구회
9. Do You Have a Scientific Mind?
시스템 분석 및 설계 글로컬 IT 학과 김정기.
정보처리학회논문지 B 제10-B권 제1호(2003.2) 김만선, 이상용
Data Analytics for Healthcare
이산수학(Discrete Mathematics)
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
점화와 응용 (Recurrence and Its Applications)
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
1. 관계 데이터 모델 (1) 관계 데이터 모델 정의 ① 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key) 와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델 ② 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)
이산수학(Discrete Mathematics)
소프트웨어 종합설계 (Software Capstone Design)
The general form of 0-1 programming problem based on DNA computing
The R&D Boundaries of the Firm: An Empirical Analysis
Bug Localization Based on Code Change Histories and Bug Reports
Hongik Univ. Software Engineering Laboratory Jin Hyub Lee
[CPA340] Algorithms and Practice Youn-Hee Han
Progress Seminar 신희안.
Progress Seminar 이준녕.
Fifth theme Superhero powers
Chapter 4. Energy and Potential
Chapter 7: Deadlocks.
Speaking -여섯 번째 강의 (Review ) RACHEL 선생님
Presentation transcript:

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

차례 동기 SIFT 특징 추출 특징 매칭 성능 응용 참고 자료 2018-12-26

동기 - 장면의 다양성 2018-12-26

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

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

동기 - 인간 시각과 기계 시각 인간 시각 기계 시각 매우 강인 선택적 주의 집중 (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)

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

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

동기 - 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) 2018-12-26

위키피디아 정의 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 2018-12-26

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

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

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

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

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

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

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

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

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

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

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

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

특징 매칭 – 최근접 이웃 탐색 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. 2018-12-26

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

성능 - 어파인 변화에 대한 민감도 분석 2018-12-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. …” 2018-12-26

응용 – panorama stitching [Brown2003] 2018-12-26

응용 – 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.  2018-12-26

응용 – 로봇 localization and mapping [Se2001] SLAM (Simultaneous Localization and mapping) 달성 2018-12-26

응용 – 로봇 localization and mapping [Se2001] 2018-12-26

응용 – 증강현실 [Gordon2006] 2018-12-26

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

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

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

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

응용 – 사람 행위 인식 [Laptev2004] 2018-12-26

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

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

참고 자료 오픈소스 Rob Hess (School of EECS, Oregon State University) http://blogs.oregonstate.edu/hess/ https://web.engr.oregonstate.edu/~hess/publications/siftlib-acmmm10.pdf “My Open-Source SIFT Library just won second place at the ACM Multimedia 2010 Open-Source Software Competition.  The competition was stiff, …” http://www.cs.ubc.ca/~lowe/keypoints/ (Lowe의 데모 프로그램) 2018-12-26

참고 자료 문헌들 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.91-110, 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, pp177-280, 2007. 지역 기술자의 성능 비교 K. Mikolajczyk, and C. Schmid, "A performance evaluation of local descriptors", IEEE Transactions on Pattern Analysis and Machine Intelligence, pp.1615-1630, 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. 67-82, 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. 2018-12-26