차근차근/OpenCV

3 일에 만드는 고속 특정 물체 인식 시스템 (7) 가장 가까운 이웃 탐색의 고​​속화

예쁜꽃이피었으면 2014. 7. 30. 10:11

http://aidiary.hatenablog.com/entry/20091212/1260624075


3 일에 만드는 고속 특정 물체 인식 시스템 (6) 선형 탐색을 이용한 특정 물체 인식 (2009-11-22)의 연속이다. 이번이 시리즈의 최종회입니다.

이전의 선형 탐색은 너무 느려 때문에 가장 근접 검색을 빠르게합니다. 이제 제목 초고속 특정 물체 인식 시스템이 완성됩니다. 가속에는 여러 가지 방법이 있지만, 물체 모델 데이터베이스를 어떤 데이터 구조에 미리 저장해두면 라는 것이 포인트입니다. 이번에는 문서에서 언급 된 kd-tree 와 Locality Sensitive Hashing (LSH) 이라는 기술을 시도합니다. kd-tree는 나무 구조, LSH는 해시 데이터를 구조화 (인덱싱)합니다. kd-tree는 엄격한 최단 입점을 원하지만 LSH는 근사 최단 입점 검색이라고 강력한 가까운 이웃은 요구되지 않는 대신 계산을 크게 향상시킬 수 있습니다.

문서에서는 ANN (Approximate Nearest Neighbor)라는 라이브러리 kd-tree를 사용하고 있습니다. ANN의 kd-tree는 대략 가까운 이웃 탐색도 할 수 있도록 확장하는 것입니다. OpenCV에는 kd-tree (강력한 버전)과 LSH 구현되어 있습니다. OpenCV의 kd-tree와 LSH 함수 API 가 비슷한 형태로 정비되어 있기 때문에 사용하기 쉽습니다.

kd-tree

kdtree_recognition.cpp

우선 kd-tree입니다. 어, kd-tree는 · · ·라고하는 것은 귀찮아서 그 그는주세요. 고차원 데이터를 효율적으로 검색하는 나무 구조입니다. 일반적으로 수십 차원 정도까지 빠르게 검색 할 수 있다고되어 있습니다 만, 그 이상이 될 것으로 次元の呪い 통해 검색 효율성은 떨어집니다. 이번에는 국소 특징 량 128 차원인데 선형 탐색에 비해 크게 향상시킬 수있었습니다.

    / / 키포인트의 특징 벡터를 objMat 행렬에로드 
    cout << "물체 모델 데이터베이스를로드합니다 ..." << flush;
    vector < int > labels;      / / 키 포인트 레이블 (objMat에 해당) 
    vector < int > laplacians;   / / 키 포인트 라플라시안 
    CvMat * objMat;            / / 각 행이 물체의 키포인트의 특징 벡터 
    if (! loadDescription (DESC_FILE , labels, laplacians, objMat)) {
        cerr << "cannot load description file" << endl;
         return  1 ;
    }
    cout << "OK" << endl;

    / / 물체 모델 데이터베이스를 인덱싱 
    cout << "물체 모델 데이터베이스를 인덱싱합니다 ..." << flush;
    CvFeatureTree * ft = cvCreateKDTree (objMat);   / / objMat는 복사되지 않기 때문에 해제는 안 
    cout << "OK" << endl;

kd-tree를 만들기 위해 cvCreateKDTree () 함수를 사용합니다. 인수는 한 줄에 한 데이터의 행렬입니다. 물체 모델 데이터베이스의 모든 특징 량을 objMat (모든 특징 량 수 x128 차원 행렬)에 전개하고 있습니다. objMat 데이터는 복사되지 않고 포인터를 kd-tree에 저장하고 있기 때문에 objMat 끝까지 풀어 놓고는 안됩니다.

    / / 쿼리의 키포인트의 특징 벡터를 CvMat에 배포
    CvMat * queryMat = cvCreateMat (queryDescriptors-> total, DIM, CV_32FC1);
    CvSeqReader reader;
    float * ptr = queryMat-> data.fl;
    cvStartReadSeq (queryDescriptors & reader);
    for ( int I = 0 ; i <queryDescriptors-> total; i + +) {
         float * descriptor = ( float *) reader.ptr;
        CV_NEXT_SEQ_ELEM (reader.seq-> elem_size, reader);
        memcpy (ptr, descriptor, DIM * sizeof ( float ));   / / DIM 차원의 특징 벡터를 복사
        ptr + = DIM;
    }

    / / kd-tree에서 1-NN의 키 포인트 인덱스 검색 
    int K = 1 ;   / / k-NN의 K 
    CvMat * indices = cvCreateMat (queryKeypoints-> total, k CV_32SC1);    / / 1-NN의 인덱스 
    CvMat * dists = cvCreateMat (queryKeypoints-> total, k CV_64FC1);      / / 그 거리 
    cvFindFeatures (ft, queryMat, indices, dists, k, 250 );

쿼리의 특징 벡터들을 행렬 (CvMat)에 배포하여 각 특징 벡터의 가까운 이웃을 kd-tree에서 검색하는 부분입니다.cvFindFeatures () 함수를 사용합니다. 첫 번째 인수는 kd-tree입니다. 두번째는 쿼리 행렬 (각 행은 쿼리 화상의 국소 특징 량 벡터)입니다. 쿼리 행렬을주고 각 특징 벡터의 k-NN을 함께 계산할 수 있도록되어 있습니다. 쿼리가 하나의 특징 벡터의 경우에도 일단 CvMat에 배포하지 않으면 안되는 것 같네요. indices와 dists 쿼리 행렬과 같은 행수를 가지는 행렬에서 쿼리의 각 특징 벡터의 k-NN의 인덱스와 쿼리의 거리가 각각 저장됩니다. 이번에는 k = 1에서 1-NN (최근 옆) 탐색이므로 열 수는 1 세로로 긴 행렬입니다. k-NN 탐색 할 경우, k 열 수 있습니다. 작은 데이터로 시험해 보았는데 거리는 유클리드 거리로 계산 된 것 같습니다.

LSH

lsh_recognition.cpp

다음 LSH을 시도합니다. 사실 LSH의 구현은 OpenCV2.0에서 추가 된 것처럼 설명서에도 설명이 적혀 있지 않았습니다. 그런 이유로 조금 시간이 지남에 OpenCV2.0/src/cv/cvlsh.cpp를 해독하고 사용하는 방법을 알아 보았습니다.

    / / 키포인트의 특징 벡터를 objMat 행렬에로드 
    cout << "물체 모델 데이터베이스를로드합니다 ..." << flush;
    vector < int > labels;       / / 키 포인트 레이블 (objMat에 해당) 
    vector < int > laplacians;   / / 키 포인트 라플라시안 
    CvMat * objMat;            / / 각 행이 물체의 키포인트의 특징 벡터 
    if (! loadDescription (DESC_FILE , labels, laplacians, objMat)) {
        cerr << "cannot load description file" << endl;
         return  1 ;
    }
    cout << "OK" << endl;

    / / 물체 모델 데이터베이스를 인덱싱 
    cout << "물체 모델 데이터베이스를 인덱싱합니다 ..." << flush;
    CvLSH * lsh = cvCreateMemoryLSH (DIM, 100000 , 5 , 64 , CV_32FC1);
    cvLSHAdd (lsh, objMat);
    cout << "OK" << endl;
    cout << "LSH Size :" << LSHSize (lsh) << endl;

    / / 이후는 LSH에 저장된 데이터를 사용하므로 원본은 필요 없다
    cvReleaseMat (& objMat);

LSH 만들기는 cvCreateMemoryLSH () 함수를 사용합니다.

    CvLSH * cvCreateMemoryLSH ( int D, int N, int L, int K, int type, Double r, int64 seed)

d는 원본 데이터의 차수입니다. 이번에는 SURF 특징 량이므로 d = 128 네요. n은 해시 테이블의 크기입니다. 이것은 매우 미묘한 매개 변수이지만 적당히 100000 해 보았습니다. 값이 클수록 메모리는 먹고 있지만 충돌이 일어나 어려워 지므로 검색이 빠를 것 같습니다. L와 k는 LSH의 핵심 매개 변수입니다 . L은 해시 테이블의 수 k는 해싱 키의 차수입니다 (k-NN의 k와 까다로운이지만 무관). d 차원 데이터는 k 차원의 해시 키에 변환되어 L 개의 해시 테이블에 저장됩니다 (구현에서는 L 개의 해시 테이블을 만들지 않고, 크기 n의 해시 테이블을 하나 준비하고 데이터를 저장하기 L 번 반복하는 것 같습니다.) LSH 자세한 설명은 참고 자료를 살펴보세요. 이번 예제에서는 L = 5, k = 64으로하고 있습니다. 무언가 최적의 L와 k식이 논문에 써있는 만 그대로 였으면 잘되지 않았습니다. 이번에는 여러가지 파라미터 시행 착오 L와 k를 결정합니다. 이 근처는 좀 더 추구하고 싶다.

LSH에 데이터를 저장하는 것이 cvLSHAdd () 함수입니다.

    void cvLSHAdd (CvLSH * lsh, const CvMat * data, CvMat * indices)

lsh는 cvCreateMemoryLSH가 돌려 준 LSH입니다. data는 저장해야 할 데이터입니다. 한 줄당 데이터 매트릭스 (CvMat)에 배포하고 정리해 Add 수 있습니다. 이번 예라고 data는 국소 특징점 수 xSURF의 차수 (= 128)의 행렬입니다. kd-tree와 달리, objMat의 데이터를 복사하여 LSH에 저장하고 있기 때문에 lsh을 만든 후에는 objMat 들어 가지 않기 때문에 해제합니다. objMat이 거대하다고 objMat과 lsh 모두에서 2 배의 메모리를 사용하기 때문에 데이터 전부를 objMat에 배포하지 않고 조금씩 디스크에서로드하는 cvLSHAdd ()를 반복하는 것이 메모리 효율은 좋은 것 같습니다.

        / / 쿼리의 키포인트의 특징 벡터를 CvMat에 배포
        CvMat * queryMat = cvCreateMat (queryDescriptors-> total, DIM, CV_32FC1);
        CvSeqReader reader;
        float * ptr = queryMat-> data.fl;
        cvStartReadSeq (queryDescriptors & reader);
        for ( int I = 0 ; i <queryDescriptors-> total; i + +) {
             float * descriptor = ( float *) reader.ptr;
            CV_NEXT_SEQ_ELEM (reader.seq-> elem_size, reader);
            memcpy (ptr, descriptor, DIM * sizeof ( float ));   / / DIM 차원의 특징 벡터를 복사
            ptr + = DIM;
        }

        / / kd-tree에서 1-NN의 키 포인트 인덱스 검색 
        int K = 1 ;   / / k-NN의 K 
        CvMat * indices = cvCreateMat (queryKeypoints-> total, k CV_32SC1);    / / 1-NN의 인덱스 
        CvMat * dists = cvCreateMat (queryKeypoints-> total, k CV_64FC1);      / / 그 거리 
        cvLSHQuery (lsh, queryMat, indices, dists, k, 100 );

쿼리의 특징 벡터들을 행렬 (CvMat)에 배포하여 각 특징 벡터의 가까운 이웃을 kd-tree에서 검색하는 부분입니다.cvLSHQuery () 함수를 사용합니다. 인터페이스는 kd-tree의 cvFindFeatures ()와 거의 동일합니다. LSH 저자가 맞추어 준군요. LSH의 소스 코드 를 읽고 보았습니다 만, 유클리드 거리 공간 의 LSH를 사용했습니다. 구현은 Andoni 씨의 E2LSH 처럼입니다.

실행 시간 비교

시험 삼아 실험 해 보겠습니다. 환경이지만 CPU는 Corei7 2.67GHz 메모리 3GB입니다. 이전의 선형 탐색과 같은 Caltech101의 하위 집합을 사용합니다.

■ kd-tree 결과
물체 ID-> 물체 이름의 해시를 만듭니다 ... OK
물체 모델 데이터베이스를로드합니다 ... OK
물체 모델 데이터베이스를 인덱싱합니다 ... OK
물체 모델 데이터베이스의 물체 회 990
데이터베이스의 키 포인트 : 321935
Loading Models Time = 78036.5ms
query?> dolphin_image_0001.jpg
../dataset/caltech101_10/dolphin_image_0001.jpg
쿼리의 키 포인트 : 183
확인 결과 : dolphin_image_0001.jpg
Recognition Time = 269.143ms
query?> butterfly_image_0001.jpg
../dataset/caltech101_10/butterfly_image_0001.jpg
쿼리의 키 포인트 : 423
확인 결과 : butterfly_image_0001.jpg
Recognition Time = 216.022ms
query?> 
■ LSH 결과
물체 ID-> 물체 이름의 해시를 만듭니다 ... OK
물체 모델 데이터베이스를로드합니다 ... OK
물체 모델 데이터베이스를 인덱싱합니다 ... OK
LSH Size : 321935
물체 모델 데이터베이스의 물체 회 990
데이터베이스의 키 포인트 : 321935
Loading Models Time = 72197.6ms
query?> dolphin_image_0001.jpg
../dataset/caltech101_10/dolphin_image_0001.jpg
쿼리의 키 포인트 : 203
확인 결과 : dolphin_image_0001.jpg
Recognition Time = 51.9376ms
query?> butterfly_image_0001.jpg
../dataset/caltech101_10/butterfly_image_0001.jpg
쿼리의 키 포인트 : 453
확인 결과 : butterfly_image_0001.jpg
Recognition Time = 92.3854ms
query?>

모두 쿼리와 동일한 이미지를 식별 결과로 반환되기 때문에 정답 이군요. 선형 탐색과 마찬가지로 쿼리 이미지를 좀 많이 변형 되어도 올바르게 인식 할 수 있습니다. 계산 시간은 선형 탐색은 23 초와 52 초 이었기 때문에 kd-tree와 LSH는 현격 한 차이에 빠른 것을 알 수 있습니다. kd-tree와 LSH을 비교하면 LSH 쪽이 몇 배 빠릅니다. 더 큰 데이터이라 더 차이가 가해질 것입니다. 모두 200MB 정도의 메모리를 사용합니다 (LSH는 objMat을 해제 할 때까지 x2 배 달려 있습니다). 실시간 인식도 일반 PC에서도 할 수있었습니다.

끝에

바로 지난번 Google 이 Google Goggles 라는 물체 인식을 이용한 검색 시스템을 공개했습니다. 이것은 예상입니다 만, 이번 만든 것 같은 고속 특정 물체 인식이 기반이되고있는 것은 아닐까 생각합니다. 물체 인식 정확도 개선 및 대규모 데이터에의 대응 등 실용화에 있어서는 어려운 과제도 있지만, 간단한 물체 인식 시스템은 초보자도 3 일에서 만들 수 있군요!

덧붙여서 동쪽의 에덴 의 실현은 매우 힘들다고 생각합니다. 이번 시스템은 시바와 타키자와 아키라의 실시간 인식은 도저히 할 수 없습니다 (웃음)

참고 문헌


반응형
저작자표시 비영리

'차근차근 > OpenCV' 카테고리의 다른 글

3 일에 만드는 고속 특정 물체 인식 시스템 (5) 물체 모델 데이터베이스 만들기  (0) 2014.07.30
3 일에 만드는 고속 특정 물체 인식 시스템 (6) 선형 탐색을 이용한 특정 물체 인식  (0) 2014.07.30
openCV 2.4.6 설치  (0) 2014.07.30
Windows7 에서 minGW 설치하기  (0) 2014.07.30
openCV한글매뉴얼  (0) 2014.07.30

'차근차근/OpenCV'의 다른글

  • 현재글3 일에 만드는 고속 특정 물체 인식 시스템 (7) 가장 가까운 이웃 탐색의 고​​속화

관련글

댓글

티스토리툴바