perpet

surf

스터디/C++,CLI,C#2011. 5. 14. 00:13

 

 http://en.wikipedia.org/wiki/SURF

 

여기서 설명하는 SURF 알고리즘 opencv 에 있는 find_obj 소스코드를 기반으로 만들어졌다.

 

1.특징점 추출

( octave , layer , wavelet, hessian 을 이용해 크기와 회전에 강한 특징점을 찾아낸다)

 

 1-1 소스 이미지 integral(적분) 한다.

 개요 : wavelet 정보를 뽑을때 적분영상이 있어야 빠른 wavelet 정보를 만들수있음

 참고자료 :

 http://www.codeproject.com/KB/audio-video/haar_detection.aspx

 http://aisitei.tistory.com/174

 입력 : 입력영상

 처리 : x 축 y 축을 증가시키면서 누적된 픽셀정보를 저장한다

 출력 : 적분을 표현(representation) 한 영상

 

1-2 wavelet 정보 추출

 개요: wavelet mask 를 이용해 wavelet 정보를 octave *  layer 갯수 만큼 만든다

 octave: 이미지의 샘풀링 갯수를 지정 : ( 참고자료 : sift 의 의도와 비슷한 뜻)

              만약 3 이라면

               원본이미지 -> 원본이미지/2 -> 원본이미지 /4   의 이미지를 가짐

 layer : 해당 octave 이미지에 몇개의 layer(size) 로 wavelet 정보를 만들지 결정

            만약 3이라면

             wavelet size   ->  wavelet size  / 2 -> wavelet size/4

 

참고자료:

 http://www.cs.ucf.edu/~mali/haar/

http://www.codeproject.com/KB/graphics/edge_detection.aspx?msg=2331630

 입력 :

적분 영상

Wavelet data

    const int dx_s[NX][5] = { {0, 2, 3, 7, 1}, {3, 2, 6, 7, -2}, {6, 2, 9, 7, 1} };
    const int dy_s[NY][5] = { {2, 0, 7, 3, 1}, {2, 3, 7, 6, -2}, {2, 6, 7, 9, 1} };
    const int dxy_s[NXY][5] = { {1, 1, 4, 4, 1}, {5, 1, 8, 4, -1}, {1, 5, 4, 8, -1}, {5, 5, 8, 8, 1} };

x                                                                     y                                                  xy

Wavelet(1).png 

 

 처리 :  

dx  = icvCalcHaarPattern( s_ptr, Dx, 3 );
dy  = icvCalcHaarPattern( s_ptr, Dy, 3 );
dxy = icvCalcHaarPattern( s_ptr, Dxy, 4 );


각각의 (x , y xy)  wavelet data 를 이용해 x,y,xy 값을 추출

출력 : layer 별 각각의 x,y,xy 정보를 추출

 

 1-3  헤시안 연산

 개요:  x,y,xy 의 wavelet 정보를 바탕으로 헤시안 연산을 하여 hessianThreshold 값이 넘으면 이웃 헤시안 값을 비교 하여 layer 을 포함한 이웃 26 개 정보와 비교후 가장 값이 크면 interpolation 후 특지점으로 추가한다

 입력 : layer 별 wavelet (x,y,xy) 정보

 처리 :

  *det_ptr++ = (float)(dx*dy - 0.81*dxy*dxy);
 *trace_ptr++ = (float)(dx + dy);

연산후 

 

 /* Non-maxima suppression. val0 is at N9[1][4]*/
                        if( val0 > N9[0][0] && val0 > N9[0][1] && val0 > N9[0][2] &&
                            val0 > N9[0][3] && val0 > N9[0][4] && val0 > N9[0][5] &&
                            val0 > N9[0][6] && val0 > N9[0][7] && val0 > N9[0][8] &&
                            val0 > N9[1][0] && val0 > N9[1][1] && val0 > N9[1][2] &&
                            val0 > N9[1][3]                    && val0 > N9[1][5] &&
                            val0 > N9[1][6] && val0 > N9[1][7] && val0 > N9[1][8] &&
                            val0 > N9[2][0] && val0 > N9[2][1] && val0 > N9[2][2] &&
                            val0 > N9[2][3] && val0 > N9[2][4] && val0 > N9[2][5] &&
                            val0 > N9[2][6] && val0 > N9[2][7] && val0 > N9[2][8] )

 

이웃중 가장 큰값인지 확인을 한후 보간을 통해 더 정확한 값을 얻어와서 특지점 리스트에 추가한다.

여기서 보간의 의미는 opencv 게시판에 누군가 잘설명한 것이 있는데 차후 주소를 알게되면 링크추가 예정

 

//////////////////////////////////////////////////////////////////////////////

 2.디스크립터 만들기

찾아낸 특징점에 고유영역을 표현할수있는 디스크립터를 만든다.

 

2-1 orientation 가우시안 웨이트를 만든다.

아래 링크에 있는 이미지와같은 정보를 얻음

http://retina.anatomy.upenn.edu/~lance/modelmath/gaussian.html

ORI_RADIUS = 6

ORI_RADIUS * ORI_RADIUS  방향에 따른 가우시안 웨이트 생성

 

2-2 patch 정보에 대한 가우시안 웨이트를 만든다.

 PATCH_SZ = 20

 PATCH_SZ * PATCH_SZ 영역에 대한 가우시안 웨이트 생성

 

2-3 각방향에 대한 orientation 정보 생성

 개요 : 특징점 주위 6 *6  사이즈안에 있는 모든 포인트에대해서 wavelet 수치를 얻는다.

입력 : 적분이미지

 

처리 :

                        

                 Untitled(3).png

 

black : 특징점

 red : ORI_RADIUS * ORI_RADIUS 방향 안에 있는 점들

green : PATCH_SZ 사이즈 박스 * 특지정에 포함된 사이즈 정보( 소스 100% 분석 안함)

 

green 박스와 아래 wavelet data  연산을 하여 orientation 정보를 만듬

 wavelet2.png

 

 각도에 따른 모든 wavelet 수치를 합산하여 가장 큰 각도 값을 얻는다. 가령 위에서는 파란색이 가장 큰 각도라 판단함

 

 출력 : 가장 수치가 높은 각도를 얻음( 회전에 강한 정보를 얻기위한 초기단계)

 

 2-4 디스크립터 생성

개요 : 크기와 회전에 강한 정보를 만듬

 입력 :  입력 이미지, 윗단계에서 얻은 가장 반응성있는 각도 정보

처리 :

descriptor2.png 

 입력된 방향정보를 기반으로 이미지정보의 gradients 값을 계산한다.

gradients 값을 기반으로 64bin 또는 128 bin  디스크립트 정보를 생성한다.

출력 :  디스크립터 정보 생성

 

3 정합 (matching)

새로운 이미지와 기존에 인식된 이미지정보의 디스크립터를 분석하여 같은 정보인지를 판별하는 작업

FLANN(Fast Library for Approximate Nearest Neighbors)

속도를 개선하기위해 정확도에 따라 근접하였다고 판단되면 해당 인덱스 값을 리턴한다.(내부적인 알고리즘 방식은 아직 분석안했음)

참고자료:

 http://people.cs.ubc.ca/~mariusm/

 http://people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN

입력 : 인식된 기술자 와 새로입력된 기술자 정보

처리 : 

 

cv::flann::Index flann_index(m_image, cv::flann::KDTreeIndexParams(4));  // using 4 randomized kdtrees

새로 들어온 이미지에대한 디스크립 정보를 kdtree 구조를 기반으로 인덱스를 만든다.

 

flann_index.knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const SearchParams& params);

 // queries 비교할 원본이지의 디스크립터 정보

//  indices  queries 요청한 정보와 가장 근사한 인덱스 정보를 뽑아준다.

//  dists       뽑아준 인덱스 정보(거리값)을 리턴해준다.

//  knn       가장 근사한 후보인덱스 갯수 요청

 

인식되여있는 기술자정보를 queries 값으로 주면 해당하는  가장 비슷하다고 판단된 새로운기술자정보의 인덱스를 knn  갯수만큼 

평가된 dits 정보와 같이 준다

여기서 knn 이 2 값을 사용하여 가장 가깝다고 생각하는 인덱스 2개를 뽑는다.

dists_ptr[2*i]<0.6*dists_ptr[2*i+1]

이두개의 인덱스 평가값이 거의 비슷한 수치가 나오면 같은 기술자정보로 인식한다.

이것이 의미하는것은 하나의 입력이미지에 octave 마다  기술자 정보가 있기 때문에 octave 갯수만큼 기술자가 검색되여지는 특징을 이용한 것이다.

 

출력 : 같은 기술자 정보라고 인식되여진 페어 정보

 

 cvFindHomography 이용하여 객체의 정확한 범위?를 측정

 

 

 

 

 

이 글은 스프링노트에서 작성되었습니다.

Comment +6

  • perpet 2011.05.14 00:17

    예전에 surf 를 분석했을때 정리하던 자료
    몇년전부터느끼지만 비젼처리 하는쪽 소스를 보면서 수학적지식뿐아니라
    문제를 푸는 사고가 넓어지는것 같다.

  • 좋은 자료 설명, 감사합니다.

  • ugg 2013.07.14 18:24

    창밖을 봐 바람에 나뭇가지가 살며시 흔들리면 네가 사랑하는 사람이 널 사랑하고 있는거야.

  • 창밖을 봐 바람에 나뭇가지가 살며시 흔들리면 네가 사랑하는 사람이 널 사랑하고 있는거야.

  • 좋으면 좋고 싫으면 싫은 거지, 뭐가 이렇게 어렵고 복잡하냐구

  • ama3208 2018.03.16 11:51

    opencv 에 있는 find_obj 소스코드를 기반으로 만들어졌다는 말씀은 opencv를 이용해서 짠 알고리즘이라는건가요 ??