영상 특징점(keypoint) 추출방법

영상처리 2014.04.10 23:17

영상 특징점이 무엇이고 어떻게 뽑는지, 그리고 대표적인 방법에는 어떤 것들이 있는지 정리해 봅니다.


1. 영상 특징점이란?

2. Harris corner [1988]

3. Shi & Tomasi [1994]

4. SIFT - DoG [2004]

5. FAST [2006]

6. AGAST [2010]

7. 주요 불변 특징량(SURF, BRIEF, ORB 등) 방법에서 사용하는 특징점



1. 영상 특징점이란?


영상에서 물체를 추적하거나 인식할 때, 영상과 영상을 매칭할 때 가장 일반적인 방법은 영상에서 주요 특징점(keypoint)을 뽑아서 매칭하는 것입니다. 특징점을 영어로는 보통 keypoint 또는 interesting point라 부릅니다.


<그림 1>


위 그림에서 첫번째 이미지와 대응되는 지점을 두번째 이미지에서 찾는다고 했을 때, A는 쉽게 찾을 수 있지만 B는 찾기가 어렵습니다. 이와 같이 영상을 매칭하는데 있어서 A처럼 주위 배경과 구분되면서 식별이 용이한 지점을 특징점으로 잡는게 유리함은 누구나 쉽게 알 수 있을 것입니다.


좋은 영상 특징점(keypoint)이 되기 위한 조건을 적어보면 다음과 같습니다.

  • 물체의 형태나 크기, 위치가 변해도 쉽게 식별이 가능할 것
  • 카메라의 시점, 조명이 변해도 영상에서 해당 지점을 쉽게 찾아낼 수 있을 것


영상에서 이러한 조건을 만족하는 가장 좋은 특징점은 바로 코너점(corner point)입니다. 그리고 대부분의 특징점(keypoint) 추출 알고리즘들은 이러한 코너점 검출을 바탕으로 하고 있습니다.



2. Harris Corner [1988]

[Harris88] C. Harris and M. Stephens, "A combined corner and edge detector", Alvey Vision Conference, 1988


영상에서 코너점, 특징점(keypoint)을 찾는 가장 대표적인 방법은 1988년에 발표된 Harris corner detector 입니다.


영상에서 코너(corner)를 찾는 기본적인 아이디어는 아래 그림과 같이 영상에서 작은 윈도우를 조금씩 이동(shift)시켰을 때, 코너점의 경우는 모든 방향으로 영상변화가 커야 한다는 점입니다.


<그림 2> 출처: Matching with Invariant Features, Lecture Notes 2004


위 아이디어는 원래 1980년 Moravec's corner detector (Moravec, H, "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover", Tech Report CMU-RI-TR-3, Carnegie-Mellon University, Robotics Institute, September 1980)에 나온 내용입니다. Moravec은 이 아이디어를 구현하기 위해 영상의 각 픽셀 위치에 대해 윈도우를 수직, 수평, 좌대각선, 우대각선 이렇게 4개 방향으로 1 픽셀씩 이동시켰을 때의 영상변화량(SSD) E를 계산한 후,  E의 최소값을 해당 픽셀의 영상변화량 값으로 설정, 설정된 min(E) 값이 지역적으로 극대가 되는 지점을 코너점으로 찾는 방법을 사용했습니다.


Harris corner detector는 Moravec의 방법을 수정 보완한 것으로서, Harris 방법에서 사용한 구현 과정을 이해하기 위해서는 어느정도 수학적 지식을 필요로 합니다 (저도 다 이해가 되는건 아니지만 되는 대로 적어보겠습니다).


먼저, (△x, △y)만큼 윈도우를 이동시켰을 때 영상의 SSD(sum of squared difference) 변화량 E는 다음과 같습니다 (W: 로컬 윈도우).


 --- (1)


이 때, shift값 (△x,△y)이 매우 작다고 가정하고 그레디언트(gradient)를 이용하여 I를 선형 근사하면 (1차 테일러 근사),


 --- (2)


가 됩니다.


이 때, 2×2 행렬 M의 두 eigenvalue를 λ1, λ2 (λ1≥λ2)라 하면 영상 변화량 E는 윈도우를 λ1의 고유벡터(eigenvector) 방향으로 shift 시킬 때 최대가 되고, λ2의 고유벡터 방향으로 shift시킬 때 최소가 됩니다 (why? 그렇다고 합니다 ㅠ.ㅠ). 또한 두 고유값(eigenvalue) λ1, λ2는 해당 고유벡터 방향으로의 실제 영상 변화량(E) 값이 됩니다 (단, 윈도우의 shift 크기가 1일 경우).


따라서, M의 두 고유값 λ1, λ2를 구했을 때, 두 값이 모두 큰 값이면 코너점(corner point), 모두 작은값이면 'flat'한 지역, 하나는 크고 다른 하나는 작은 값이면 'edge' 영역으로 판단할 수 있습니다.


실제 Harris 방법에서는 M의 고유값을 직접 구하지 않고 det(M)=λ1λ2, tr(M)=λ1+λ2 임을 이용하여 다음 수식의 부호로 코너점 여부를 결정합니다.


 --- (3)


즉, R>0면 코너점, R<0면 edge, |R|이 매우 작은 값이면 R 부호에 관계없이 flat으로 판단 (단, k는 경험적 상수로서 0.04 ~ 0.06 사이의 값).


<그림 3> 출처: Matching with Invariant Features, Lecture Notes 2004


Harris 코너 검출 방법의 특징을 살펴보면, Harris detector는 영상의 평행이동, 회전변화에는 불변(invariant)이고 affine 변화, 조명(illumination) 변화에도 어느 정도는 강인성을 가지고 있습니다. 하지만 영상의 크기(scale) 변화에는 영향을 받기 때문에 응용에 따라서는 여러 영상 스케일에서 특징점을 뽑을 필요가 있습니다.


<그림 4> 출처: Matching with Invariant Features, Lecture Notes 2004


☞ 참고로, 이러한 스케일 문제를 보완하기 위한 한 방법으로 2001년도에 발표된 Harris-Laplacian 방법(K. Mikolajczyk and C. Schmid, "Indexing based on scale invariant interest points", in ICCV 2001)에서는 여러 영상 스케일에서 Harris 코너를 뽑은 후, 이들 중 스케일 변화에 대해 Laplacian이 극대인 점을 선택하는 방식이 사용되었습니다.



3. Shi & Tomasi [1994]

[Shi94] J. Shi and C. Tomasi, "Good features to track", in CVPR 1994


Shi-Tomasi 특징점 추출 방법은 goodFeaturesToTrack() 이라는 함수명으로 opencv에 구현되어 있으며 흔히 optical flow 등을 계산할 때 사용할 특징점을 추출하는 용도 등으로 사용됩니다. 논문에 보면, 기존의 방법들은 코너점 등 직관에 의지하여 특징점을 찾았는데 자신들 생각에는 좋은 특징점이란 추적 알고리즘에 최적화되도록(추적이 용이하도록) 뽑아야 하며 따라서 기존 방법처럼 단순한 평행이동(translation) 만을 가정해서는 안되고 affine 변화까지 고려해서 특징점을 선택해야 한다는 등의 설명이 나옵니다.


Shi-Tomasi의 결론은 Harris 방법처럼 M의 두 eigenvalue를 같이 고려하는 것보다는 λ1, λ2 중 최소값만을 고려하는 것이 더 좋다는 것입니다. 즉, Shi-Tomasi 특징점은 다음 수식을 만족하는 점들로 주어집니다.


 --- (4)


단, k는 미리 정의된 threshold, λ1, λ2는 Harris corner의 식(2)에 행렬 M의 두 eigenvalue.


즉, Harris corner와 Shi-Tomasi corner를 비교해 보면 Harris는 λ1, λ2가 모두 비슷하게 큰 경우에 corner점으로 식별하고, Shi-Tomasi는 λ1, λ2 중 최소값만 임계치보다 크면 corner점으로 식별하는 방식입니다.


☞ 그런데, 저는 Harris가 더 좋은 방법이라고 생각합니다. 왜냐하면 최소값이 임계값보다 크더라도 다른 한 값이 월등히 더 크면 코너점이라기 보다는 edge로 보는 것이 더 타당하기 때문입니다 (물론 픽셀의 밝기값은 한계(최대255)가 있기 때문에 최소값만 고려해도 결과적으로는 큰 차이가 없습니다). 또한 Harris 방법은 eigenvalue를 직접 구할 필요없이 M에서 바로 식 (3)의 R을 계산하여 코너점을 판단하기 때문에 속도면에서도 이득입니다.



4. SIFT - DoG [2004]

[Lowe04] Lowe, D.G., "Distinctive image features from scale-invariant keypoints", IJCV 2004.


널리 알려진 SIFT(Scale Invariant Feature Transform)에서 사용하는 특징점 추출 방법입니다. SIFT에서는 기존의 Harris 코너가 영상의 스케일 변화에 민감한 문제를 해결하기 위하여 DoG(Difference of Gaussian)를 기반으로 이미지 내에서 뿐만 아니라 스케일 축으로도 코너성이 극대인 점을 찾습니다.


SIFT에서 사용한 특징점 추출 방법을 이해하기 위해서는 먼저 스케일에 불변인 즉, scale invariant한 특징점을 추출한다는 말의 의미를 이해할 필요가 있습니다. 어떤 입력 이미지 I가 있을 때, I의 크기를 단계적으로 축소시켜서 일련의 축소된 이미지들을 생성할 수 있습니다 (이렇게 생성된 이미지들의 집합을 보통 이미지 피라미드라고 부릅니다). 이 때, 각 스케일의 영상마다 코너성을 조사해서 코너점(코너성이 로컬하게 극대이면서 임계값 이상)들을 찾습니다. 그러면 각 스케일 이미지마다 코너점들이 검출될 터인데, 대부분의 경우 인접한 여러 영상 스케일에 걸쳐서 동일한 지점이 코너점으로 검출될 것입니다. 동일한 지점이 여러 영상 스케일에 걸쳐 코너점으로 검출된 경우, 그중 스케일 축을 따라서도 코너성이 극대인 점을 찾으면 스케일에 불변인 특징점이 됩니다.


<그림 5> image pyramid


여기서, 스케일에 불변인 특징점이란 의미는 입력 이미지의 스케일이 어떻게 주어지더라도 해당 특징점을 찾아낼 수 있다는 의미입니다. 서로 다른 스케일의 입력 영상 I1, I2가 있다고 하겠습니다. 이 때, I1에서 특징점을 찾을 때 I1의 입력 스케일에서만 특징점을 찾는게 아니라 I1으로부터 이미지 피라미드를 구축한 후에 여러 스케일에 걸쳐서 특징점을 찾습니다(각각의 스케일 이미지 내에서 코너성이 극대일 뿐만 아니라 스케일 축으로도 코너성이 극대인 점들). I2에서도 마찬가지로 여러 스케일에 걸쳐 특징점을 찾아냅니다. 이렇게 특징점을 찾으면 입력 이미지의 스케일에 관계없이 동일한 특징점을 찾을 수 있게 됩니다. 또한 해당 특징점이 I1의 어떤 스케일에서 찾아졌는지와 I2의 어떤 스케일에서 발견된 것인지는 서로 다를 수 있지만 I1, I2에서 계산된 코너성은 거의 동일할 것입니다.


SIFT 방법으로 돌아가서, SIFT에서 특징점을 추출하는 기본적인 원리는 위와 같지만 코너성을 측정하기 위해 Harris 방법과는 달리 Laplacian 함수값을 사용합니다. 즉, SIFT에서는 각 영상 스케일마다 Laplacian 값을 계산하되 그 값이 이미지 내에서 뿐만 아니라 스케일 축으로도 극대(또는 극소)인 점들을 특징점으로 선택합니다. 참고로, Laplacian은 이미지의 밝기 변화에 대한 2차 미분값으로서 다음과 같이 계산되며


 --- (5)


그 특징은 영상의 밝기 변화가 일정(constant velocity)한 곳에서는 0에 가까운 값, 영역의 경계와 같이 밝기 변화가 급격한 곳에서는 높은 값(절대값)을 나타냅니다.


(이후의 내용은 SIFT에서 Laplacian을 DoG를 이용하여 근사적으로 계산한 방법에 관한 것으로서 건너뛰어도 무방합니다)


실제 SIFT에서는 속도 문제로 인해 Laplacian을 직접 계산하지는 않고 DoG(Difference of Gaussian)를 이용하여 각 스케일별 Laplacian을 근사적으로 계산합니다. DoG는 입력영상에 Gaussian 필터를 점진적으로 적용하여 블러링(blurring)시킨 이미지들에서 인접 이미지들간의 차(subtraction) 영상을 의미하며 이론적으로는 LoG(Laplacian of Gaussian) 필터를 적용한 것과 거의 동일한 결과를 갖습니다.


<그림 6> SIFT의 DoG 계산


그리고 이렇게 얻어진 DoG 피라미드에서 극대 또는 극소점을 찾으면 SIFT의 특징점이 됩니다.


☞ 위에서 Gaussian 필터를 적용하여 영상을 blurring 시키는 것은 영상의 스케일을 확대시키는 의미를 갖습니다. 이러한 원리 및 DoG, LoG 등에 대해 이해하기 위해서는 'scale space' 이론에 대해 어느정도 알고 있어야 합니다. Scale space 이론에 대해서는 조만간 별도로 포스팅을 하겠습니다. 일단 여기서는, SIFT에서는 이미지 피라미드 상에서 Laplacian 값이 극대 또는 극소가 되는 점들을 특징점으로 잡는다 정도로만 이해해도 무방하리라 생각됩니다. =>Scale Space와 이미지 피라미드(image pyramid)



5. FAST [2006]

[Rosten06] E. Rosten and T. Drummond, "Machine learning for high-speed corner detection", in ECCV 2006


FAST(Features from Accelerated Segment Test)는 영국 캠브리지 대학의 Edward Rosten이 개발한 방법으로 FAST라는 이름에서 알 수 있듯이 극도의 빠름을 추구한 특징점 추출 방법입니다. 하지만 FAST가 정말 뛰어난 점은 FAST가 속도에 최적화되어 설계된 기술임에도 불구하고 그 특징점의 품질(repeatability: 다양한 영상 변화에서도 동일한 특징점이 반복되어 검출되는 정도) 또한 기존의 방법들(Harris, DoG, ...)을 상회한다는 점에 있습니다.


FAST 또한 코너점을 찾는 방법중 하나로서 그 기본 방법은 다음과 같습니다.


<그림 7> FAST corner detector


FAST에서는 위 그림과 같이 어떤 점 p가 코너(corner)인지 여부를 p를 중심으로 하는 반지름 3인 원 상의 16개 픽셀값을 보고 판단합니다. 그래서 p보다 일정값 이상 밝은(>p+t) 픽셀들이 n개 이상 연속되어 있거나 또는 일정값 이상 어두운(<p-t) 픽셀들이 n개 이상 연속되어 있으면 p를 코너점으로 판단합니다.


FAST 알고리즘은 n을 어떻게 잡느냐에 따라서 FAST-9, FAST-10, FAST-11, FAST-12, ..., FAST-16과 같이 다양한 버전이 가능합니다. 즉, FAST-9는 p보다 일정값 이상 밝거나 어두운 픽셀들이 원을 따라서 연속적으로 9개 이상 존재하는 경우를 코너점으로 검출하는 알고리즘이고, FAST-12는 12개 이상의 점들이 연속적으로 모두 p보다 충분히 밝거나 모두 p보다 충분히 어두운 경우를 찾아주는 알고리즘입니다.


FAST 알고리즘에서는 어떤 점 p가 코너점인지 여부를 판단하기 위해 같은 유형의 연속된 점들의 개수를 직접 세는 대신에 decision tree를 이용하여 코너점 여부를 빠르게 판단하는 방법을 사용합니다. 이를 위해 픽셀의 밝기값을 p보다 훨씬 밝은 경우, p보다 훨씬 어두운 경우, p와 유사한 경우의 3가지 값으로 분류하고 이를 이용하여 원주 상의 픽셀들의 밝기분포를 16차원의 ternary 벡터로 표현합니다. 그리고 이를 decision tree에 입력하여 코너점 여부를 분류합니다 (decision tree를 학습시키는 방법은 논문 참조).


FAST 코너의 한가지 문제점은 어떤 점 p가 코너점으로 인식되면 p와 인접한 주변 점들도 같이 코너점으로 검출되는 경우가 많다는 점입니다. FAST에서는 이 문제를 해결하기 위해 non-maximal suppression라 불리는 추가적인 후처리 단계를 적용합니다.


Non-maximal suppression의 목적은 인접한 여러 점들이 코너점으로 검출된 경우 그중 코너성이 극대인 점만을 남기고 나머지를 제거하는 것입니다. 그런데, 앞서 설명한 decision tree 방식은 코너점 여부를 On/Off 방식으로 결정할 뿐, 코너 정도를 수치화하지는 못하기 때문에 FAST 논문에서는 다음과 같은 별도의 수치화 함수를 정의합니다.


 --- (6)


Non-maximal suppression 단계에서는 decision tree를 통해 검출된 코너점들에 대해 각각 식 (6)의 V를 계산한 후, 인접한 코너점들 중 자신보다 높은 V값을 갖는 코너점이 있으면 해당 코너점을 제거하는 방식으로 코너성이 극대인 점들을 찾아냅니다.


FAST의 성능: 저자의 실험에 의하면 여러 FAST 버전들 중 FAST-9의 성능이 가장 좋으며 기존 방법에 비해 10배 이상의 속도 증가를 가져온다고 합니다. 특징점의 품질(repeatability) 또한 기존 방법들을 상회하는 결과를 보여줍니다.



<그림 8> FAST의 속도 성능


<그림 9> FAST의 repeatability 성능


☞ 개발자 홈페이지(http://www.edwardrosten.com/work/fast.html)에 가면 FAST에 대한 다양한 소스코드, FAQ 및 관련자료를 얻을 수 있습니다.



6. AGAST [2010]

[Mair10] E. Mair, G. Hager, D. Burschka, M. Suppa, and G. Hirzinger, "Adaptive and generic corner detection based on the accelerated segment test," in ECCV 2010


FAST의 성능을 좀더 빠르게 개선한 방법이라고 합니다. 논문을 조금 읽어봤지만 당체 무슨 말인지.. 어쨌든 논문의 주장에 따르면 AGAST 방법이 FAST에 비해 20 ~ 30% 정도 속도가 더 빠르다고 합니다.



7. 주요 불변 특징량 방법에서 사용하는 특징점


SIFT, SURF, BRIEF, ORB, FREAK 등과 같은 지역적 불변 특징량 (local invariant feature descriptor) 방법들에서 사용하는 특징점(keypoint)이 어떤 것인지 간단히 살펴 보고자 합니다.


먼저, 지역 불변 특징량(descriptor)과 특징점(keypoint)을 서로 구분할 필요가 있는데 keypoint는 특징이 되는 점의 영상좌표 (x,y)를 의미하고(scale space까지 고려한다면 (x,y,s)), descriptor는 해당 keypoint 위치에서 추출한 지역적 영상 특징 정보(ex. gradient 분포 히스토그램 등)를 의미합니다.


대표적인 지역 불변 특징량(descriptor)들로는 SIFT, SURF, ORB 등이 있는데, descriptor 계산을 위해서는 일단은 keypoint를 뽑아야 하기 때문에 이들 지역 불변 특징량 방법들도 나름의 특징점 추출 방법을 가지고 있습니다. 사실 지역 불변 특징량과 특징점은 서로 별개의 얘기이기 때문에 임의의 keypoint + descriptor 조합이 가능합니다. 예를 들어, FAST로 특징점을 뽑은 후 SIFT로 descriptor를 계산하는 것도 가능합니다.


SIFT의 경우는 앞서 DoG를 이용하여 특징점을 추출한다고 설명한 바 있는데, 그외 다른 지역 불변 특징량 방법들에서는 어떤 특징점 추출 방법들이 사용되는지 간단히 살펴보겠습니다.


SURF [Bay06]

: Bay, H., Tuytelaars, T., and Van Gool, L., "Surf: Speeded up robust features," in ECCV 2006

=> Scale space 상에서 Hessian 행렬의 행렬식(determinant)이 극대인 점들을 특징점으로 검출. SURF에서 사용한 특징점 추출 방법을 Fast Hessian이라 부름.


Ferns [Ozuysal07]

: Ozuysal, M., Fua, P., and Lepetit, V., "Fast Keypoint Recognition in Ten Lines of Code," in CVPR 2007

=> Scale space 상에서 Laplacian이 극대인 점들을 특징점으로 검출 (단 3개의 scale로만 구성된 이미지 피라미드에서 Laplacian 극대점을 찾은 점에서 모든 스케일에 대해서 특징점을 찾은 SIFT와 차이가 있음)


BRIEF [Calonder10]

: Calonder, M., Lepetit, V., Strecha, C., and Fua, P, "Brief: Binary robust independent elementary features," in ECCV 2010

=> BRIEF에는 별도의 특징점 추출 방법이 포함되어 있지 않음 (SURF의 특징점을 그대로 사용하여 SURF와 성능을 비교하거나 Star(CenSurE) 특징점을 이용하여 성능을 비교)


ORB [Rublee11]

: Rublee, E., Rabaud, V., Konolige, K., and Bradski, G., "ORB: an efficient alternative to SIFT or SURF," in ICCV 2011

=> FAST-9 을 이용하여 특징점을 검출한 후 나름의 방법(Intensity Centroid)으로 특징점의 방향(orientation)을 계산


BRISK [Leutenegger11]

: Leutenegger, S., Chli, M., and Siegwart, R. Y., "BRISK: Binary robust invariant scalable keypoints," in ICCV 2011

=> Scale space 상에서 FAST-9을 이용하여 FAST score가 극대인 점을 특징점으로 검출


FREAK [Alahi12]

: A. Alahi, R. Ortiz, and P. Vandergheynst, "FREAK: Fast Retina Keypoint," in CVPR 2012

=> 별도의 특징점 추출 방법을 제공하지 않고 BRISK에서 사용한 특징점 추출 방법을 그대로 사용



☞ 이상으로 주요 영상 특징점(keypoint) 추출 방법들에 대해 정리를 해 보았습니다. SIFT, SURF, BRIEF, ORB, FREAK 등 주요 불변 영상 특징량(descriptor) 방법들에 대해서는 별도 글로 포스팅할 예정입니다.


by 다크 프로그래머


  • 이전 댓글 더보기
  • Open 2017.04.05 10:31 신고 ADDR 수정/삭제 답글

    안녕하세요 서프알고리즘 공부하고 있는 학생입니다 다름이아니라 속도면에서 특징점알고리즘중 가장 빠른 알고리즘은 어떤건가요??

    • BlogIcon 다크pgmr 2017.04.05 12:56 신고 수정/삭제

      글쎄요. 어떤게 가장 빠를지는 모르겠지만 surf도 빠르고 orb, brief, freak 등과 같은 binary feature들도 빠릅니다.

  • 안녕하세요 2017.04.07 22:11 신고 ADDR 수정/삭제 답글

    안녕하세요! 영상처리를 공부하고 있는 학생입니다.
    공부하면서 다크프로그래머 님이 올려주신 글이 많은 도움이 되는거 같습니다
    다름이 아니라 Harris corner를 opencv없이 c로 구현해 보려고 하는데요
    제가 제대로 이론을 이해를 못한건지 구현이 너무 힘드네요 ㅠㅠ

    영상에서 덮을 윈도우 크기는 정해져 있는게 있나요?
    받아오는 영상은 640 * 480 크기인데, 윈도우는 3x3이나 5x5나 상관이 없을까요?

    그리고 Ix는 5x5 마스크를 x축으로 1만큼 움직였을때 안에 들어있는 25픽셀들의 [밝기값 합]의 변화량
    Iy는 y축으로 1만큼 움직였을때 25픽셀의 밝기값 합의 변화량으로 이해하면 될까요?

    OPENCV를 사용하지 않고 C로만 코딩하려는데 개념이 잘 이해가 안되네요
    윈도우 크기를 설명해놓은 곳도 없고요 ㅠㅠ
    윈도우 크기는 상관이없는걸까요?

    예를들자면
    3x3 마스크라고 가정했을때
    [5,5] 점에 대해 harris corner 방법을 사용하려면
    [3,3] [4,3] .... [6,7][7,7] 이렇게 주변에 9픽셀을 정한다음
    9픽셀의 값이 100이였다가
    3x3 마스크를 x축으로 1칸 옮기고,[4,3][5,3] .... [7,7][8,7]
    그 9필셀의 밝기값 합이 90이면
    Ix는 -10이 되는 이런식인가요?? ㅠㅠ
    제가 이해한게 맞는건가요?


    영상전체에 HARRIS CORNER를 사용하는건 아니고, ORB 알고리즘에서 FAST로 키포인트 잡은후에 그 키포인트들에 HARRIS CORNER 방법으로 키포인트 중에 상위 N개를 선별해내는 과정입니다 !

    • BlogIcon 다크pgmr 2017.04.08 23:01 신고 수정/삭제

      안녕하세요. 말씀하신 것처럼 당연히 마스크 크기에 영향을 받을 것이고 opencv 에서도 사용한 마스크 크기가 정해져 있을 것으로 생각됩니다. 구체적인 구현은 opencv는 소스코드가 공개되어 있으니 Harris corner 구현 부분을 한번 살펴보시면 어떨까 싶습니다. 그리고 Ix, Iy 구하는 것은 말씀하신 바데로 하시면 됩니다. 하지만 Ix, Iy를 구해서 E를 구하는 방식은 글에서도 설명하였듯이 Moravec의 방식이었고 Harris 방식은 이를 수정하여 식 (2)와 같이 행렬 M을 계산한 후, M의 eigenvalue를 이용합니다. opencv에 구현된 Harris corner는 M을 이용한 방식이 구현되어 있을 것으로 생각됩니다. 하지만, 지금 하고계신 Ix, Iy를 이용한 방식도 큰 문제는 없을 것으로 생각됩니다.

  • 고맙습니다. 2017.05.05 14:00 신고 ADDR 수정/삭제 답글

    좋은글 잘 봤습니다. Harris Corner 공부 중입니다...
    2. Harris Corner 의 식 (1)에서....

    (△x, △y)만큼 윈도우를 이동시켰을 때 영상의 SSD(sum of squared difference) 변화량 E는 다음과 같습니다 (W: 로컬 윈도우). 라는 말씀을 해주셨습니다......결국 변화량 E에 따라서 이놈이 모서리인지, edge인지 flat한 지역인지 알 수 있다는 말씀 같은데요....

    저기 식(1)에 써있는 전체 의미가 궁금하긴 합니다. W는 무엇인지, 대문자 I는 무엇인지 등이요..답변 해주시면 진심으로 감사하겠습니다!!!

    • BlogIcon 다크pgmr 2017.05.07 15:30 신고 수정/삭제

      I는 이미지, I(x, y)는 (x, y) 위치에서의 이미지의 픽셀값(밝기)입니다. W는 윈도우(window) 영역입니다. 픽셀 p(x, y)가 코너점인지 여부를 판단하기 위해서 p를 센터(center)로 p 주변의 사각형 영역에 대해 E를 계산하게 되는데 이 부분 영역이 W입니다.

  • 감사합니다 2017.05.12 16:13 신고 ADDR 수정/삭제 답글

    안녕하세요. 좋은글 감사합니다!
    저는 opencv로 윤곽선과 그안에 불규칙하게 찍혀있는 마크점을 추출하고싶은데요. 어떤 알고리즘을 이용해야하는지 모르겠습니다.. 어떤 알고리즘을 사용하는것이 좋을까요??

    • BlogIcon 다크pgmr 2017.05.12 19:07 신고 수정/삭제

      이진화와 contour 추출을 통해 blob들을 추출한 후 검출한 각 blob들을 분석해야 하지 않나 싶습니다.

    • 감사합니다 2017.05.18 13:56 신고 수정/삭제

      답변을 지금봤네요!!감사합니다!!

  • 신지수 2017.05.12 20:50 신고 ADDR 수정/삭제 답글

    안녕하세요 영상처리를 공부하는 학생입니다!
    클라이밍 할때 색깔돌을 하나하나의 객체로
    인식하고싶은데 좋은방법이 있을까요?

    적당한방법으로 돌들을 선으로 이을려고 합니다!
    검출한 돌들을 하나하나의 객체로 인식하는부분에서 막혔어요 ㅠㅠ

    • BlogIcon 다크pgmr 2017.05.13 00:13 신고 수정/삭제

      안녕하세요. 연결성분 분석을 말씀하시는 것이라면 opencv의 findContours 함수를 이용하시면 됩니다.

  • 신지수 2017.05.13 01:38 신고 ADDR 수정/삭제 답글

    답변해주셔서 감사합니다 질문을잘못한거 같아 송구스럽게도 다시 질문드립니다....
    회색배경의 같은색깔의 돌을 골라 ( 빨,파,초 라 가정) 이진화 해서
    검은색 배경의 다양한 모양의 흰색 돌(홀드)를 추출하려고합니다. 문제는
    여기서 모든 돌들을 이으려하는게 아니라 적당한기준( 되도록 수직방향) 으로 선으로 이으려하는데
    하나 하나의 돌들을 변수로 인식하고 싶습니다. 검출이 문제가아니라 하나하나의 돌들을 하나의 객체로 인식해야하는데 방도가 있을까요?

    • BlogIcon 다크pgmr 2017.05.13 13:14 신고 수정/삭제

      네. findContours 함수를 이용하면 개체들을 분리해서 반환해줍니다.

  • BlogIcon 톈진난만 2017.05.27 18:09 신고 ADDR 수정/삭제 답글

    SIFT에 대해서 공부하고 있는데, 스케일에 불변인 특징점이 대체 무슨 뜻인가 했는데 이 글을 통해 이해할 수 있게 되었습니다. ㅎㅎ 혹시 그러면 회전에 불변인 특징점은 무슨 뜻이죠?? 특징점마다 방향을 할당해주는 것과 회전에 불변인 특성을 갖게 되는 것과 어떤 상관성이 있는지 잘 모르겠어서요..ㅜㅜ

    • BlogIcon 다크pgmr 2017.05.28 16:00 신고 수정/삭제

      네.. 불변이란 의미는 동일한 특징점에 대해서는 동일한 특징값이 추출된다는 의미입니다. 특징점마다 주(main) 방향을 계산한 후 주 방향이 (예를 들어) 0도가 되도록 특징점 주변의 이미지를 회전시킨 후에 특징값을 계산하면 입력 이미지가 어떻게 회전이 되든 동일 특징점에 대해서는 동일한 특징값이 추출될 것입니다.

    • BlogIcon 톈진난만 2017.05.29 09:51 신고 수정/삭제

      아 그런 의미군요!! 감사합니다 ㅎㅎ

  • 컴퓨터비젼 초년생 2017.06.04 13:55 신고 ADDR 수정/삭제 답글

    안녕하세요 영상처리에 대해서 공부하고있는 학부생입니다.
    간단하지만 제가 생각한 알고리즘으로 특징점 아닌 특징점을 뽑아 다음 프레임에서 매칭을 해보려고
    opencv에 나오는 소스들을 보고있는데 matcher들은 특징점까지 같이 뽑아서 매칭까지 시도하기에 어떤 알고리즘에 적용해야할지 감이 잘 오지 않습니다. 부족하지만 답변 부탁드립니다. ㅠㅠ

    • BlogIcon 다크pgmr 2017.06.05 12:04 신고 수정/삭제

      특징점(keypoint), 특징량(descriptor), 매칭(matcher) 이렇게 3 가지는 서로 조합적으로 선택하여 사용할 수 있습니다. opencv에서 제공하는 특징점 매칭 예제들을 참고하시기 바랍니다(opencv/samples/cpp/matchmethod_orb_akaze_brisk.cpp)

  • 잘봤습니다 2017.06.29 17:28 신고 ADDR 수정/삭제 답글

    안녕하세요 항상 알기 쉽게 설명해 주셔서 영상처리 공부하면서 언제나 많은 배움을 얻어가고 있습니다. 감사합니다.
    글의 마지막에 descriptor를 별도로 포스팅하신다고 하셨는데 제가 잘못본 것이 아니라면 아직인것 같네요. 조만간 포스팅 하실 예정이 있으신가요?

    • BlogIcon 다크pgmr 2017.06.30 16:11 신고 수정/삭제

      네, 아직 작성하진 못했습니다.. 일부 feature에 대한 글(http://darkpgmr.tistory.com/116)이 있긴 하지만 surf, orb, ... 등의 local descriptor에 대한 글은 아직 없습니다. 글이란 것이 그
      때 그때 관심사와 마음이 흘러가는대로 쓰는 것이라서 장담을 하긴 힘들지만 아마도 조만간에 쓰기는 힘들 것 같습니다.

  • 영상처리공부중 2017.07.18 14:32 신고 ADDR 수정/삭제 답글

    안녕하세요 제가 우분투리눅스에서 opencv3.2 로 컬러인식이 아닌 특정 타겟만 인식해서 추적하는 코드를 짜려고 하는데요
    opencv3.0 이후에선 SURF SIFT ORB 를 이용한 xfeatures2d 쪽 기능을 쓰기 힘들어졌다고 하더라구요
    대략적인 함수를 써야하는부분이나 소스를 인터넷에서 찾아봐도 파이썬이나 비주얼스튜디오 기준으로 적힌 설명이 대부분이라 감을 못잡고있습니다. 대략적으로 필요한 함수나 코드 또는 도움이 될만한 링크좀 부탁드려도될까요 ㅠㅠ

    • BlogIcon 다크pgmr 2017.07.18 20:16 신고 수정/삭제

      글쎄요.. 특별히 달라진 것은 없는데요. opencv의 samples 폴더에 있는 matchmethod_orb_akaze_brisk.cpp 샘플코드를 참조하시면 어렵지 않게 feature들을 사용할 수 있을 것으로 생각됩니다.

  • 케리 2017.09.08 02:32 신고 ADDR 수정/삭제 답글

    http://www.freeiconspng.com/img/4534

    이미지처리 초보임에도 불구하고 다크님의 넓은 식견의 도움을 받고자 감히 무식을 무릅쓰고 여쭤보려합니다. 다름이 아니오라 위에 링크 걸어논 타겟이미지를 증강현실로 입력받아(이미지를 프린팅한 후 폰으로 촬영) 그 위에 가상의 오브젝트를 올리고 싶습니다. 일종의 사격 게임 같은게 목표입니다. 그럴려면 기존의 특징점 기법(sift, surf) 등에서 사용 가능한 기법이 있을까요? 제가 저 이미지를 퀄컴의 Vuforia나 국산 T-real 등 여러가지 버전으로 적용해 보았으나 가상의 오브젝트를 띄우진 못하였습니다. 그 이유를 분석해본 결과 기존 엔진에서 특징점을 뽑는 기능은 동작하지만 특징점의 방향성이 확보되지 못하여 가상의 오브젝트 방향을 결정하지 못한게 아닌가 싶었습니다. 즉, 사슴이 저 타겟위에 올리고 싶어도 어느 방향으로 사슴을 바라보게 해야 할지를 알 수가 없는게 아닌가 싶었습니다. 결론적으로 말씀드리면 제가 opencv + android로 구현하고 싶은 결과물은 저런 이미지 타겟을 인식하고 폰 화면에서 가상의 사슴 오브젝트를 임의의 방향으로 배치만 하여도 충분한 것이지요. 다크님의 도움이 절실한 상황이네요 어떻게 하면 해결 가능할런지 알려주시면 감사하겠습니다..^^;;

    • BlogIcon 다크pgmr 2017.09.08 14:18 신고 수정/삭제

      안녕하세요. 말씀하신 이미지를 보았습니다만 2가지 문제점이 있는 것 같습니다. 가장 큰 문제점은 마커 자체가 방향성이 없기 때문에 인식을 하더라도 방향을 결정할 수 없습니다. 마커에 방향성을 부여하기 위해 삼각형을 추가하는 등의 변형이 필요한 것 같습니다. 그리고 두번째 문제점은 과녁 이미지와 같은 단순한 도형 형태에는 sift, surf 등의 특징점 기법은 적합하지 않습니다. 특징점 기법은 사진, 그림 등과 같이 복잡한 패턴이 있는 경우에 적합합니다. 과녁을 찾기 위해서는 경계를 추출하여 원을 찾거나 패턴을 그대로 매칭하는 방법 등이 좋을 것 같습니다.

    • 케리 2017.09.13 00:24 신고 수정/삭제

      다크님 답변 정말 감사드립니다
      애초에 저런 이미지와 같은 마커에 방향성이 없다는건 잘 알고 있습니다. 저는 방향성보다는 타겟 이미지를 영상에서 2D 좌표로만 찾을 수 있으면 되는 상황이구요 대신에 그 타겟이 위와 같은 원형이 유지되진 못하고 상하로 찌그러져서 타원형태로 나오는 경우가 많은 상황입니다. 제안해주신 경계 추출후 원을 찾는다고 말씀하셨는데 경계선이 이미지와 같은 경우엔 2~3개의 타원이 중첩되어 보여질거 같습니다 여하튼 좀 더 검색을 해서 답을 찾도록 해볼께요 감사합니다. 구글링에서 원찾기나 패턴찾기를 해보면 답을 찾을 수 있겠죠? ㅎㅎ

    • BlogIcon 다크pgmr 2017.09.13 08:07 신고 수정/삭제

      네. 저도 딱히 다른 좋은 방법이 떠오르는건 없습니다..

  • tlwkrgoqhfrk 2017.10.09 06:03 신고 ADDR 수정/삭제 답글

    다크프로그래머님 안녕하세요 ,
    개재하신 포스터를 정말 잘 읽고 유익한 정보를 얻었습니다.
    특징점(Key-point) 방법과 특징량(Key-descriptor) 방법이 있다고 말씀해주셨습니다.
    FAST는 특징점(Key-point) 방법이라고 하셨는데, FAST를 사용하여 특징량(Key-descriptor)을 얻을 수는 없나요?
    위에서 언급해주신 것처럼 "FAST로 특징점을 뽑은 후 SIFT로 descriptor를 계산"하여 특징량을 얻어야 하는 것인가요?

    • BlogIcon 다크pgmr 2017.10.09 15:21 신고 수정/삭제

      네, FAST에서는 따로 특징량을 제공하지 않기 때문에 특징량은 다른 방법들과 결합하여 사용해야 합니다.

  • 공기팡 2017.10.10 00:50 신고 ADDR 수정/삭제 답글

    안녕하세요 지금 대학원 진학 고려중인 학생입니다. 영상처리 관련 궁금한 점이 생겼는데 마침 이 블로그를 지나가게 되었네요ㅎㅎ 요즘 영상처리는 거진 다 딥러닝기반으로 돌아가는것 같습니다. 영상 인식이나 압축은 수학적, 통계적 사실을 기반으로 추상화 알고리즘을 짜 구현하는걸로 알고있는데 요즘 딥러닝으로 극도의 추상화를 진행하다보면 학부생의 짧은 지식으로는 영상처리 관련 연구는 사실상 거의 축소된것 같아 고민중입니다.. 진학하려는 교수님 연세가 좀 있으시다보니 딥러닝으로 깊게 연구하시진 않는 것 같아보입니다.. 간혹 인더스트리에서는 영상처리 이슈에 대해선 다 끝났다는 말을 듣기도 해서 혼란이 오네요. 혹시 먼저 영상처리를 배우신 선배님 입장에서 이 분야로 연구 가능성, 발전성에 어떻게 생각하시나요? 영상처리자체보다는 상대적 얕은 영상지식에 딥러닝 지식을 갈고 닦는게 나을까요? 질문 받아주셔서 감사합니다! 지금 간절기 시즌 조심하세요~

    • BlogIcon 다크pgmr 2017.10.10 10:00 신고 수정/삭제

      안녕하세요. 저도 혼란스러운 부분을 물으시니 답변을 잘 드릴 수 있을지 모르겠습니다 (http://darkpgmr.tistory.com/170 글 참조). 어쨌든 딥러닝은 학습기법이니 도메인(domain) 중 하나인 영상처리와는 구분이 필요할 것 같습니다. 딥러닝 자체에 관한 연구는 AI에 대한 연구이기 때문에 앞으로도 계속 발전할 것으로 생각됩니다. 최근에 나오는 세계적 수준의 영상처리 연구들도 도메인이 영상일 뿐 사실은 딥러닝에 대한 연구라고 볼 수 있습니다. 결국 시스템을 만드느냐 이용하느냐의 문제인데 워낙 시스템이 좋다보니 대부분 시스템을 잘 이용하는 쪽으로 공부가 진행되는 것 같습니다. 시스템을 잘 이용하는 것도 실제로는 유용하고 의미가 있다고 생각합니다. 하지만 가능하다면 시스템 안으로 들어가는 것도 학생으로서는 필요한 일이고 그러기 위해서는 추상화가 심해진 만큼 기본적인 공부가 더 중요해진 것 같습니다. 저는 영상처리 연구가 끝났다기 보다는 오히려 강력한 도구로 인해 전에 없던 많은 가능성이 새로 열렸다고 생각합니다.

  • 썬드래곤 2017.11.05 20:38 신고 ADDR 수정/삭제 답글

    항상 감사합니다..

  • 준자갓 2017.11.07 11:27 신고 ADDR 수정/삭제 답글

    이해하기 쉽게 잘 설명해주셔서 많은 도움을 얻고 갑니다. 감사합니다.^^

  • python 기반으로 다시 opencv 공부를 해 보고 있습니다. 뭐 좀 이론적인 내용이 잘 이해 안될때는 믿고찾는 '다크프로그래머'님 블로그~ FAST에 대해서도 설명 감사합니다. SIFT에서 좀 좌절먹고 건너뛰었는데 여기 올려주신 자료를 다시 꼽씹어봐야겠네요.

  • BlogIcon 감사합니다 2018.01.09 18:45 신고 ADDR 수정/삭제 답글

    지금까지 봐왔던 다양한 사람들의 블로그/포스트 중에서도 손꼽히는 수준의 포스트 같습니다. 우연히 오게 되었는데 이해하는데 큰 도움이 되었네요. 올 한 해 항상 건강하시고 자주와서 배우도록하겠습니다.

  • Machine 2018.01.14 16:32 신고 ADDR 수정/삭제 답글

    안녕하세요. 네모 물체를 고정된 카메라에서 사진을 찍고 해당 꼭지점의 좌표를 얻고자 합니다. ( 네모가 Tilt 되었을 경우 네모가 있어야 할 원래 자리에 회전 보정을 하여 제대로 만들려고 하는데요 이미지를.. 가장 적합한 알고리즘이 뭘까요 Harris가 좋을거 같기도 한데.. 속도면에서 문제가 될 수도 있을거 같아서 .. 답변 부탁드리겠습니다 !

    • BlogIcon 다크pgmr 2018.01.15 08:54 신고 수정/삭제

      정보의 양 및 구분력 면에서 꼭지점만 찾는 것보다는 선(경계선)을 찾는 것이 좋고, 선만 찾는 것보다는 면을 찾는 것이 좋다고 생각됩니다. 속도는.. Harris가 느린 알고리즘은 아닙니다.

    • Machine 2018.01.15 18:40 신고 수정/삭제

      네 면까지 구하는것이 맞다고 생각도 하긴 했는데요.
      제가 현재 Tilt된 영상의 꼭지점 좌표를 구했을 경우, 제가 원래 놓고자 하는 위치의 꼭지점은 제가 이미 알고 있으므로
      검출하는 관심영역만 (Tilt 영상 꼭지점 좌표 - 레퍼런스 꼭지점) 만큼의 좌표를 빼면 검출이 수월하게 되지 않을까 싶어서요.
      혹시... 꼭지점 -> 선 -> 면을 말씀하심은 Harris 처리도하고 Edge 영상도 구하고 하라는 말씀이신가요 ..? 영상처리를 많이 안해봐서 혹시 추천해주실만한 알고리즘이 있으신가요..

      그리고 마지막으로 배경과 물체( 네모)간의 색상에 서로 어둡기 때문에 네모 검출에 어려움이 있는데.. 이러한 경우에도 혹시 추천해주실만한 알고리즘이 있으실지 부탁드립니다.

    • BlogIcon 다크pgmr 2018.01.16 07:54 신고 수정/삭제

      그냥 정보의 표현력, 구분력 측면에서 말씀드린 것이구요, 꼭지점만 찾을 경우에는 노이즈 등이 꼭지점으로 검출될 경우 구분이 힘드니까요.. 구체적인 알고리즘은 문제에 따라 달라질 수 있는 것이라서 뭐라 말씀드리기 힘듭니다. opencv의 카메라 캘리브레이션 부분의 관련 함수들을 보면 체커보드(checker board)에서 격자 꼭지점을 찾아주는 함수가 있습니다. 그 함수의 소스코드 구현을 참고하면 도움이 될지 모르겠습니다.

  • 쿠크바사삭 2018.04.03 13:38 신고 ADDR 수정/삭제 답글

    안녕하세요 포스트글 잘읽었습니다. ㅎㅎ
    이런 물체 인식 알고리즘들 중에 SIFT가 가장 성능이 좋다고 알고있는데, 혹시 그 이유가 특징점을 가장 잘 찾아내서라고 봐도 될까요? 입문한지 얼마 안되어서 여러글 찾아보다가 이곳에 글 남기고 가요!

    • BlogIcon 다크pgmr 2018.04.03 18:59 신고 수정/삭제

      이유를 딱히 설명하긴 어렵지만 실험적으로 또는 경험적으로 특징점들 중에서는 SIFT가 대체적으로 성능이 좋다고들 말합니다. 그런데, SIFT는 인식 알고리즘이 아니라 영상 특징점(local feature)의 한 종류로서 다양한 인식 알고리즘에 사용될 수 있습니다.

    • 2018.04.03 19:42 수정/삭제

      비밀댓글입니다

  • ㅇㅇ 2018.04.21 15:36 신고 ADDR 수정/삭제 답글

    opencv에 관련된 국내 블로그 중 오랜만에 수준 높은 글을 본 것 같아서 기분 좋습니다.
    앞으로도 좋은 글 많이 써주셨으면 합니다!
    감사합니다!!