[Corner Detection] #1 Define of Corner

 

이번 시간의 주제는 Corner Detection 입니다.

공부함에 있어서 가장 중요한 것은 우리가 이것을 왜 배워야 하는가 입니다.

막상 배우기만 하는 입장에서는 왜 이를 배워야 하는지 모르면 막상 흥미가 떨어지기 때문입니다.

 

 

 

그렇다면 먼저 Corner Detection 이게 뭔지부터 알아야겠죠?

영어로 Corner Detection

한글로는 코너 검출 입니다.

한마디로 코너 점들을 찾는다는 거죠

아래 다각형 도형에서 그림을 찾는 것입니다.

 

 

 

그렇다면 우리는 이 Corner Detection을 배워야 할 가요?

영상처리 및 인식 분야에 있어서

코너(Corner) 정보는 모양(Shape) 이나 추적(Tracking) 등의 분야에 있어서

중요한 기준점이 되기 때문입니다.

 

예를 들어서 설명하면

1. 필기체 나 문자 인식을 할 때 글자의 윤곽을 따내어 개수와 각도 등으로 판별을 할 때 Corner를 사용하곤 합니다.

 

2. AR(Augmented Reality) 분야에서도 마커(Marker)를 검출하기 위해서 사용합니다.

 

 

3. 2D 바코드나 이미지 코드를 인식하는데 있어서도 사용됩니다.  

 

4. 복잡한 배경 영상 내에서 Corner를 빠르고 정확하게 찾는 것이 알고리즘의 성능을 평가하는 척도로도 사용됩니다.

 

이밖에 다양한 방법으로 Corner Detection이 사용되고 있는데 공부를 하지 않을 수 없겠죠?

그리고 마지막으로

Digital 영상이 라는 특징과 영상의 왜곡 흐림 등의 이유로 Corner를 찾는 일이 쉽지 않기 때문입니다.

Corner Detection에 대해서 자세히 알아보겠습니다.

 

 

 

그럼 Corner 란?

Corner의 정의는 다음과 같이 2가지로 나누어 집니다.

1. 갑자기 객체가 변하는 경계 지점의 점

    

2. 두 개 또는 두 개 이상의 변의 교차점

두 개의 교차점                                 두 개 이상의 교차점

 

이러한 Corner를 찾아내는 게 이번에 공부할  코너 검출기(Corner Detector) 입니다.

 

 

 

그럼 코너검출기 Corner Detector가 Corner를 검출하기 위해서는 어떠한 조건을 만족해야 하죠?

• 검출기를 통하여 찾아낸 코너는 정확한 코너.  
• 잘못된 코너를 찾아서는 안됩니다.
• 특징점은 매우 국부적(Localized)이어야 합니다. (전체가 아닌 한 부분에 만)
• 특징점 검출에 있어서 잡음에 강건(Robust)해야 한다.
• 효율적이어야 한다 (속도, 연산량 등, 알고리즘적이어야 한다.)

참 당연한 거죠?

 

 

그럼 이러한 코너 검출하는 방법은 어떤 것들이 있을가요?

첫 번째로 이미지의 밝기 값에 결정하는 알고리즘이 있습니다.

이는 보통적으로 그레이 레벨 또는 컬러 이미지에서 미분계수 이론에 기반을 두고 있습니다.

회전(Orientation)이나 크기(magnitude)등을 고려하는 방법입니다.

 

두 번째로는 객체의 경계(boundaries)를 뽑아 내고 그리고 나중에 이 모양을 분석하는 알고리즘이 있습니다.

이는 어떠한 객체(Object)를 표현하는데 있어서는 점과 선이 필요합니다.

점들은 특징 점이 되고

이 특징 점을 이은 게 선분이 될 것입니다.

 

그렇습니다. 이 선분을 찾고 이 선분의 끝과 끝을 찾으면 우리가 찾으려는 특징점이 된다는 거죠

그래서 이 선분들 즉 최소한의 선들을 찾아내고자 선분 근사화(Line Approximation)를 하는 것입니다.

선분을 근사화하는 방법으로는 곡률(Curvature), Strip Algorithm 방법이 있습니다.

 

참 산으로 가고 있습니다. 무슨 말인지 ㅋ

우선은 위의 2가지 찾는 방법을 알고 있으면 됩니다.

1. 이미지의 밝기를 통하여
2. 선분을 찾고 선분을 이용하여

 

 

그리고 여기서 잠깐!

여기서 중요한 점은 용어를 알아야 한다는 것입니다.

대다수의 논문은 영어로 되어 있어서 영어로 해석하다 보면 영어로 이해를 하고 알고 넘어가는 게 편합니다.

한국어로 번역된걸 보면 더 헷갈리게 됩니다. 예를 들면 곡률? 넌 뭐니?

그냥 Curvature 하면 쉽게 이해가 갈건 데

그러니 영어로 이해하는 태도를 가집시다.

 

 

위의 방법론과 같이 많은 알고리즘이 있을 거 같은데 어떤 게 있나요?

많이 들어봤을 해리스 코너(Harris Corner) 알고리즘

SUSAN, CSS, SIFT, SURF 등 다양한 알고리즘이 있습니다.

여기서 중요한 게 이 알고리즘이 어떻게 나왔느냐 하는 변천사가 중요한 것입니다.

 

 

 

그럼 변천사에 대해서 알고 싶어요 알려주세요?

 

그림을 보면 처음 Moravec을 시초로 시작하여 다양한 알고리즘이 나타났습니다.

하지만 이러한 알고리즘은 항상 아래와 같은 문제가 발생하였습니다.

1. 강건성 (Robustness)        - 조명, 크기, 회전, 원근 변화의 불변성
2. 국부성(Locality)            - 잡음과 변화에 강건
3. 독특성(Distinctiveness)        - 객체의 커다란 데이터 베이스와 쉽게 매칭
4. 다량성(Quantity)        - 작은 객체에서도 많은 점 검출
5. 능률성(Efficiency)        - 계산적으로 비용이 적고 실시간에 적합

    

초기에 가장 중요한 것은 강건성과 국부성 이었습니다.

항상 조명 크기 회전 원근 잡음 변화에도 항상 정확한 점이 나와야 한다는 거죠

그때 이를 해결했던 게 2004년에 Lowe에 의해서 발표된 SIFT(Scale Invariant Feature Transform) 입니다.

이는 정확한 특징을 찾을 수 있었던 혁명이었죠

하지만 엄청난 계산 량이 오랜 수행시간을 초래하였습니다.

그래서 실시간에는 적합하지 못하게 되죠

그리고 이 논문은 특허로 지정하면서 라이센스가 붙게 되죠

 

 

그래서 이를 보완한 PCA-SIFT등등 논문들이 많이 나오게 됩니다.

하지만 Bay에 의해 제안된 SURF(Speeded Up Robust Feature)가 또 한번의 혁명을 만듭니다.

SURF 같은 경우 OpenCV에서는 제공하고 있습니다. 그리고 속도 면에서 실시간 시스템에 적합하도록

병렬처리를 이용하든지 GPU 를 이용한다든지 속도를 향상시키는

OpenCV 버전이 업그레이드가 진행되고 있습니다.

 

 

그럼 이후에는 다른 방법은 없나요?

이후에도 많은 다양한 방법들이 나오게 됩니다.

유명한 컨퍼런스에 나오는 논문은 다음과 같습니다. (다음은 OpenCV 코리아에서 참고하였습니다.)

 

1. OSID(Ordinal Spatial Intensity Distribution)
   Feng Tang, Suk Hwan Lim, Nelson L. Chang, Hai Tao: A novel feature descriptor invariant to complex brightness changes. 2631-2638, CVPR 2009.
2. WLD(Weber Local Descriptor)
   Jie Chen; Shiguang Shan; Chu He; Guoying Zhao; Pietikainen, M.; Xilin Chen; Wen Gao; Dept. of Electr. & Inf. Eng., Univ. of Oulu, Oulu, Finland, WLD: A Robust Local Image Descriptor, PAMI 2009.
3. CHoG(Compressed Histogram of Gradients)
   V. Chandrasekhar, G. Takacs, D. Chen, S. Tsai, R. Grzeszczuk, and B. Girod, "CHoG: compressed histogram of gradients", IEEE International Conference on Computer Vision and Pattern Recognition, June 2009.
4. BRIEF(Binary Robust Independent Elementary Features)
   M. Calonder, V. Lepetit, C. Strecha, and P. Fua, BRIEF: Binary Robust Independent Elementary Features, European Conference on Computer Vision, Heraklion, Greece, 2010.
5. RIFF(Rotation Invariant Fast Features)
   G. Takacs, V. Chandrasekhar, S. Tsai, D. Chen, R. Grzeszczuk, and B. Girod, "Unified real-time tracking and recognition with rotation-invariant fast features", IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), June 2010.
6. RIFF-Polar((Rotation Invariant Fast Features-Polar)
   G. Takacs, V. Chandrasekhar, H. Chen, D. Chen, S. Tsai, R. Grzeszczuk, and B. Girod, "Permutable descriptors for orientation-invariant image matching", SPIE Workshop on Applications of Digital Image Processing (ADIP), August 2010.
7. DAISY
   E. Tola, V. Lepetit, and P. Fua. Daisy: An efficient dense descriptor applied to wide-baseline stereo. PAMI, 2010.
8. ORB(Oriented FAST and Rotated BRIEF)
   ORB: an efficient alternative to SIFT or SURF, Ethan Rublee (Willow Garage), Vincent Rabaud (willowgarage), Kurt Konolige, Gary Bradski Hiroshi Ishiguro, Osaka University ICCV 2011.
9. DaLI(Deformation and Light Invariant)

 Deformation and Illumination Invariant Feature Point Descriptor, Francesc Moreno(Institut de Robotica i Informatica Industrial (UPC/CSIC)), CVPR 2011.

<출처> OpenCV Korea 대한민국 최고의 컴퓨터비젼 커뮤니티 - neverabandon 님의 글

 

 

 

도움이 되셨다면 리플 하나 달아주는 센스 ^^

리플 하나가 큰 힘이 된답니다 *^^*