3 일에 만드는 고속 특정 물체 인식 시스템 (6) 선형 탐색을 이용한 특정 물체 인식

http://aidiary.hatenablog.com/entry/20091122/1258853886 

3日で作る高速特定物体認識システム (5) 物体モデルデータベースの作成（2009/11/14）のつづきです。

今回は、クエリを与えたときに物体モデルデータベースの中から一番似ている物体を探し出してクエリが何かを認識する部分（いわゆる、特定物体認識）を作ります。一番似ている物体を探し出す方法として、一番簡単な線形探索というアルゴリズムを使います。線形探索は遅いですが実装も簡単です。

キーポイントの最近傍点投票

クエリと一番似ている物体を検索するにはキーポイントの特徴量同士を比較します。各画像は数百から数千個の128次元の特徴ベクトルを持っているので単純に2つのベクトルを比較するという方法は使えません*1。代わりに最近傍点の投票方式を使います。クエリの各特徴ベクトルに一番近い（最近傍）特徴ベクトルを物体モデルデータベースから探し出しその特徴ベクトルを含む物体IDに対して投票します。たとえば、上の例では、クエリの特徴ベクトル(0)の最近傍を探して特徴ベクトル(1152)が見つかったとします。その特徴ベクトルを持つ物体はイルカなので物体ID=4に投票します（正の字で表してます）。クエリの残りの特徴ベクトルも同様です。例では物体ID=4のイルカへの投票が一番多いのでクエリの物体は物体ID=4のイルカと判定されます。

最近傍を探すのには線形探索を使います。これは、クエリの1つの特徴ベクトルの最近傍を求めるために物体モデルデータベースのすべての特徴ベクトルとの間でユークリッド距離を計算し、一番距離が小さいものを最近傍とします。なのでクエリ側に800個特徴ベクトルがあって、物体モデルデータベース側に300000個特徴ベクトルがあったら、投票が完了するまでに800x300000回距離計算が必要です。

クエリと物体モデルデータベースの画像が同じだったらまったく同じ特徴ベクトルが存在することになるので得票は1箇所に集中することになります。クエリ画像が少し変形していると得票は多少ばらつきますが一番得票数が多い物体を認識結果とすればOKです。特徴点のマッチング（2009/11/2）も参照してください。

プログラムリスト

ちょっと長いですが全プログラムリストです。

linear_recognition.cpp

#include <cv.h>
#include <highgui.h>
#include <iostream>
#include <fstream>
#include <map>

using namespace std;

const int DIM = 128;
const double DIST_THRESHOLD = 0.25;
const double VOTE_THRESHOLD = 50;
const int SURF_PARAM = 400;

const char* IMAGE_DIR = "caltech101_10";
const char* OBJID_FILE = "object.txt";
const char* DESC_FILE = "description.txt";

// プロトタイプ宣言
bool loadObjectId(const char *filename, map<int, string>& id2name);
bool loadDescription(const char *filename, vector<int> &labels, vector<int> &laplacians, CvMat* &objMat);
double euclideanDistance(float *vec, float *mvec, int length);
int searchNN(float *vec, int lap, vector<int> &labels, vector<int> &laplacians, CvMat* objMat);

int main(int argc, char** argv) {
    double tt = (double)cvGetTickCount();

    // 物体ID->物体ファイル名のハッシュを作成
    cout << "物体ID->物体名のハッシュを作成します ... " << flush;
    map<int, string> id2name;
    if (!loadObjectId(OBJID_FILE, id2name)) {
        cerr << "cannot load object id file" << endl;
        return 1;
    }
    cout << "OK" << endl;

    // キーポイントの特徴ベクトルを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 << "物体モデルデータベースの物体数: " << id2name.size() << endl;
    cout << "データベース中のキーポイント数: " << objMat->rows << endl;
    tt = (double)cvGetTickCount() - tt;
    cout << "Loading Models Time = " << tt / (cvGetTickFrequency() * 1000.0) << "ms" << endl;

    while (1) {
        // クエリファイルの入力
        char input[1024];
        cout << "query? > ";
        cin >> input;

        char queryFile[1024];
        snprintf(queryFile, sizeof queryFile, "%s/%s", IMAGE_DIR, input);

        cout << queryFile << endl;

        tt = (double)cvGetTickCount();

        // クエリ画像をロード
        IplImage *queryImage = cvLoadImage(queryFile, CV_LOAD_IMAGE_GRAYSCALE);
        if (queryImage == NULL) {
            cerr << "cannot load image file: " << queryFile << endl;
            continue;
        }

        // クエリからSURF特徴量を抽出
        CvSeq *queryKeypoints = 0;
        CvSeq *queryDescriptors = 0;
        CvMemStorage *storage = cvCreateMemStorage(0);
        CvSURFParams params = cvSURFParams(SURF_PARAM, 1);
        cvExtractSURF(queryImage, 0, &queryKeypoints, &queryDescriptors, storage, params);
        cout << "クエリのキーポイント数: " << queryKeypoints->total << endl;

        // クエリの各キーポイントの1-NNの物体IDを検索して投票
        int numObjects = (int)id2name.size();  // データベース中の物体数
        int votes[numObjects];  // 各物体の集めた得票数
        for (int i = 0; i < numObjects; i++) {
            votes[i] = 0;
        }
        for (int i = 0; i < queryDescriptors->total; i++) {
            CvSURFPoint *p = (CvSURFPoint *)cvGetSeqElem(queryKeypoints, i);
            float *vec = (float *)cvGetSeqElem(queryDescriptors, i);
            int lap = p->laplacian;
            int nnId = searchNN(vec, lap, labels, laplacians, objMat);
            votes[nnId]++;
        }

        for (int i = 0; i < numObjects; i++) {
            cout << votes[i] << endl;
        }

        // 投票数が最大の物体IDを求める
        int maxId = -1;
        int maxVal = -1;
        for (int i = 0; i < numObjects; i++) {
            if (votes[i] > maxVal) {
                maxId = i;
                maxVal = votes[i];
            }
        }

        // 物体IDを物体ファイル名に変換
        string name = id2name[maxId];
        cout << "識別結果: " << name << endl;

        tt = (double)cvGetTickCount() - tt;
        cout << "Recognition Time = " << tt / (cvGetTickFrequency() * 1000.0) << "ms" << endl;

        // 後始末
        cvReleaseImage(&queryImage);
        cvClearSeq(queryKeypoints);
        cvClearSeq(queryDescriptors);
        cvReleaseMemStorage(&storage);
        cvDestroyAllWindows();
    }

    // 後始末
    cvReleaseMat(&objMat);

    return 0;
}

/**
 * 物体ID->物体名のmapを作成して返す
 *
 * @param[in]  filename  物体ID->物体名の対応を格納したファイル
 * @param[out] id2name   物体ID->物体名のmap
 *
 * @return 成功ならtrue、失敗ならfalse
 */
bool loadObjectId(const char *filename, map<int, string>& id2name) {
    // 物体IDと物体名を格納したファイルを開く
    ifstream objFile(filename);
    if (objFile.fail()) {
        cerr << "cannot open file: " << filename << endl;
        return false;
    }

    // 1行ずつ読み込み、物体ID->物体名のmapを作成
    string line;
    while (getline(objFile, line, '\n')) {
        // タブで分割した文字列をldataへ格納
        vector<string> ldata;
        istringstream ss(line);
        string s;
        while (getline(ss, s, '\t')) {
            ldata.push_back(s);
        }

        // 物体IDと物体名を抽出してmapへ格納
        int objId = atol(ldata[0].c_str());
        string objName = ldata[1];
        id2name.insert(map<int, string>::value_type(objId, objName));
    }

    // 後始末
    objFile.close();

    return true;
}

/**
 * キーポイントのラベル（抽出元の物体ID）とラプラシアンと特徴ベクトルをロードしlabelsとobjMatへ格納
 *
 * @param[in]  filename         特徴ベクトルを格納したファイル
 * @param[out] labels           特徴ベクトル抽出元の物体ID
 * @param[out] laplacianss      特徴ベクトルのラプラシアン
 * @param[out] objMat           特徴量を格納した行列（各行に1つの特徴ベクトル）
 *
 * @return 成功ならtrue、失敗ならfalse
 */
bool loadDescription(const char *filename, vector<int> &labels, vector<int> &laplacians, CvMat* &objMat) {
    // 物体IDと特徴ベクトルを格納したファイルを開く
    ifstream descFile(filename);
    if (descFile.fail()) {
        cerr << "cannot open file: " << filename << endl;
        return false;
    }

    // 行列のサイズを決定するためキーポイントの総数をカウント
    int numKeypoints = 0;
    string line;
    while (getline(descFile, line, '\n')) {
        numKeypoints++;
    }
    objMat = cvCreateMat(numKeypoints, DIM, CV_32FC1);

    // ファイルポインタを先頭に戻す
    descFile.clear();
    descFile.seekg(0);

    // データを読み込んで行列へ格納
    int cur = 0;
    while (getline(descFile, line, '\n')) {
        // タブで分割した文字列をldataへ格納
        vector<string> ldata;
        istringstream ss(line);
        string s;
        while (getline(ss, s, '\t')) {
            ldata.push_back(s);
        }
        // 物体IDを取り出して特徴ベクトルのラベルとする
        int objId = atol(ldata[0].c_str());
        labels.push_back(objId);
        // ラプラシアンを取り出して格納
        int laplacian = atoi(ldata[1].c_str());
        laplacians.push_back(laplacian);
        // DIM次元ベクトルの要素を行列へ格納
        for (int j = 0; j < DIM; j++) {
            float val = atof(ldata[j+2].c_str());  // 特徴ベクトルはldata[2]から
            CV_MAT_ELEM(*objMat, float, cur, j) = val;
        }
        cur++;
    }

    descFile.close();

    return true;
}

/**
 * 2つのベクトルのユークリッド距離を計算して返す
 *
 * @param[in] vec     ベクトル1の配列
 * @param[in] mvec    ベクトル2の配列
 * @param[in] length  ベクトルの長さ
 *
 * @return ユークリッド距離
 */
double euclideanDistance(float *vec, float *mvec, int length) {
    double dist = 0.0;

    for (int i = 0; i < length; i++) {
        dist += (vec[i] - mvec[i]) * (vec[i] - mvec[i]);
    }
    dist = sqrt(dist);

    return dist;
}

/**
 * クエリのキーポイントの1-NNキーポイントを物体モデルデータベースから探してその物体IDを返す
 *
 * @param[in] vec          クエリキーポイントの特徴ベクトル
 * @param[in] lap          クエリキーポイントのラプラシアン
 * @param[in] labels       物体モデルデータベースの各キーポイントの物体ID
 * @param[in] laplacians   物体モデルデータベースの各キーポイントのラプラシアン
 * @param[in] objMat       物体モデルデータベースの各キーポイントの特徴ベクトル
 *
 * @return 指定したキーポイントにもっとも近いキーポイントの物体ID
 */
int searchNN(float *vec, int lap, vector<int> &labels, vector<int> &laplacians, CvMat* objMat) {
    int neighborObj = -1;
    double minDist = 1e6;
    for (int i = 0; i < objMat->rows; i++) {
        // クエリのキーポイントとラプラシアンが異なるキーポイントは無視
        if (lap != laplacians[i]) {
            continue;
        }
        // i行目の先頭データのポインタ（ここから128個がi行目の特徴ベクトル）
        float *mvec = (float *)(objMat->data.fl + i * DIM);
        double d = euclideanDistance(vec, mvec, DIM);
        if (d < minDist) {
            neighborObj = labels[i];  // NNキーポイントの物体IDを更新
            minDist = d;           // 最小の距離を更新
        }
    }
    return neighborObj;
}

loadObjectId()とloadDescription()は、物体モデルデータベースの作成（2009/11/14）で作ったobject.txtとdescripion.txtをロードする関数です。両ファイルと画像フォルダはプログラムと同じフォルダに置いてください。loadObjectId()は、物体ID->ファイル名のmapを作成します。認識結果を表示するときに「クエリの物体IDは3です。」とか言われても分かりにくいので名前を表示するために使います。loadDescription()は、特徴量ファイルを読み込んで特徴ベクトルの物体IDをlabelsにラプラシアンをlaplaciansに特徴ベクトルをobjMatにロードします。searchNN()は、vecとlapにクエリの特徴ベクトルとラプラシアンを指定すると物体モデルデータベースを線形探索して一番近い特徴ベクトルを検索し、その<strong>物 idを="IDを">< strong="">返します。main()ではクエリ画像のファイル名を与えるとその画像から特徴量を抽出、クエリの各特徴ベクトルの最近傍を検索して物体IDの得票数を計算し、得票数がもっとも多い物体IDのファイル名を認識結果として表示してます。</strong物><>

実行例

以下、プログラムの実行例です。クエリに

• dolphin_image_0001.jpg
• butterfly_image_0001.jpg

を与えてみました。170MBくらいメモリを使うので少ない人は気をつけてください。もっとサイズが小さいデータセットで試してみるとよいかも。

物体ID->物体名のハッシュを作成します ... OK
物体モデルデータベースをロードします ... OK
物体モデルデータベースの物体数: 990
データベース中のキーポイント数: 321935
Loading Models Time = 64689.6ms
query? > dolphin_image_0001.jpg
../dataset/caltech101_10/dolphin_image_0001.jpg
クエリのキーポイント数: 203
識別結果: dolphin_image_0001.jpg
Recognition Time = 23301.2ms
query? > butterfly_image_0001.jpg
../dataset/caltech101_10/butterfly_image_0001.jpg
クエリのキーポイント数: 453
識別結果: butterfly_image_0001.jpg
Recognition Time = 52065.9ms
query? > 

ちゃんと認識結果がクエリと同じファイルになることがわかると思います。でもこれは物体モデルデータベースに登録された画像と同じ画像をクエリにしているので当たり前の結果です。実はクエリ画像を少し変形して（回転、縮小、拡大、隠蔽など）与えてもちゃんと認識できます。線形探索なので計算はかなり遅いです。クエリを与えてから認識結果を返すまで23秒と52秒かかってます。こんなに遅くては到底リアルタイムで認識させられませんねー。

これでやっと3日で作る高速特定物体認識システムのうち1日目の課題が終わたってことですね。今回使った線形探索は遅すぎるので、物体モデルデータベースの局所特徴量をkd-treeやLocality Sensitive Hashing（LSH）でインデキシングして最近傍探索を高速化することを考えていきます。線形探索とは比べ物にならないくらい計算が速くなります。

3日で作る高速特定物体認識システム (7) 最近傍探索の高速化（2009/12/12）へつづきます。次回でこのレポート最終回の予定です。

 

(2009-11-14)의 연속이다.

이번에는 쿼리를 줄 때 물체 모델 데이터베이스 중에서 가장 비슷한 물체를 찾아 쿼리가 무언가를 인식하는부분 (소위 특정 물체 인식)을 만듭니다. 가장 비슷한 물체를 찾아내는 방법으로 가장 간단한 선형 탐색 하는 알고리즘을 사용합니다. 선형 탐색은 느리지 만 구현도 간단합니다.

키포인트 최근 방점 투표

쿼리와 가장 비슷한 물체를 검색하려면 키 포인트의 특징 량끼리를 비교합니다. 각 이미지는 수백에서 수천 개의 128 차원의 특징 벡터를 가지고 있기 때문에 단순히 두 벡터를 비교하는 방법을 사용할 수 없습니다 * 1 . 대신 최근 방점 투표 방식을 사용합니다. 쿼리의 각 특징 벡터에 가장 가까운 (가장 가까운 이웃) 특징 벡터를 물체 모델 데이터베이스에서 찾아 그 특징 벡터를 포함 물체 ID에 대해 투표합니다. 예를 들어 위의 예에서는 쿼리의 특징 벡터 (0) 최근 곁을 찾고 특징 벡터 (1152)가 발견되었다고합니다. 그 특징 벡터를 가진 물체는 돌고래이므로 물체 ID = 4에 투표합니다 (양수 글씨로 표시합니다). 쿼리의 나머지 특징 벡터도 마찬가지입니다. 예를 들어 물체 ID = 4 돌고래의 투표가 가장 많기 때문에 쿼리의 물체는 물체 ID = 4의 돌고래와 판정됩니다.

가까운 이웃을 찾는 데 선형 검색을 사용합니다. 이것은 쿼리 하나의 특징 벡터의 가까운 이웃을 구하기 위해 물체 모델 데이터베이스의 모든 특징 벡터 사이의 유클리드 거리를 계산하여 가장 거리가 작은 것을 가장 근접합니다.그래서 쿼리 측에 800 개의 특징 벡터가 있고, 물체 모델 데이터베이스 측에 300000 개의 특징 벡터가 있으면, 투표가 완료 될 때까지 800x300000 회 거리 계산이 필요합니다.

쿼리와 물체 모델 데이터베이스의 이미지가 같다면 똑같은 특징 벡터가 존재하게되기 때문에 투표는 1 개소에 집중하게됩니다. 쿼리 이미지가 조금 변형하고 있다고 득표는 다소 차이 있지만 가장 득표 수가 많은 물체를 인식 결과면 OK입니다. 특징점의 매칭 (2009/11/2)도 참조하십시오.

프로그램 목록

조금 긴하지만 모든 프로그램 목록입니다.

linear_recognition.cpp

# include <cv.h> 
# include <highgui.h> 
# include <iostream> 
# include <fstream> 
# include <map>

using  namespace Std;

const  int DIM = 128 ;
 const  Double DIST_THRESHOLD = 0.25 ;
 const  Double VOTE_THRESHOLD = 50 ;
 const  int SURF_PARAM = 400 ;

const  char * IMAGE_DIR = "caltech101_10" ;
 const  char * OBJID_FILE = "object.txt" ;
 const  char * DESC_FILE = "description.txt" ;

/ / 프로토 타입 
bool loadObjectId ( const  char * filename, map < int , string> & id2name);
 bool loadDescription ( const  char * filename, vector < int > & labels, vector < int > & laplacians, CvMat * & objMat);
 Double euclideanDistance ( float * vec, float * mvec, int Length);
 int searchNN ( float * vec, int Lap, vector < int > & labels, vector < int > & laplacians, CvMat * objMat);

int Main ( int argc, char ** argv) {
     Double tt = ( double ) cvGetTickCount ();

    / / 물체 ID-> 물체 파일 이름의 해시를 생성 
    cout << "물체 ID-> 물체 이름의 해시를 만듭니다 ..." << flush;
    map < int , string> id2name;
     if (! loadObjectId (OBJID_FILE, id2name)) {
        cerr << "cannot load object id file" << endl;
         return  1 ;
    }
    cout << "OK" << endl;

    / / 키포인트의 특징 벡터를 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 << "물체 모델 데이터베이스의 물체 회" << id2name.size () << endl;
    cout << "데이터베이스의 키 포인트 :" << objMat-> rows << endl;
    tt = ( double ) cvGetTickCount () - tt;
    cout << "Loading Models Time =" << tt / (cvGetTickFrequency () * 1000.0 ) << "ms" << endl;

    while ( 1 ) {
         / / 쿼리 파일의 입력 
        char input [ 1024 ];
        cout << "query?>" ;
        cin >> input;

        char queryfile [ 1024 ];
        snprintf (queryFile, sizeof queryfile, " % s / % s " , IMAGE_DIR, input);

        cout << queryFile << endl;

        tt = ( double ) cvGetTickCount ();

        / / 쿼리 이미지를로드
        IplImage * queryImage = cvLoadImage (queryFile, CV_LOAD_IMAGE_GRAYSCALE);
        if (queryImage == NULL ) {
            cerr << "cannot load image file :" << queryFile << endl;
             continue ;
        }

        / / 쿼리에서 SURF 특징 량을 추출 
        CvSeq * queryKeypoints = 0 ;
        CvSeq * queryDescriptors = 0 ;
        CvMemStorage * storage = cvCreateMemStorage ( 0 );
        CvSURFParams params = cvSURFParams (SURF_PARAM, 1 );
        cvExtractSURF (queryImage, 0 , & queryKeypoints & queryDescriptors, storage, params);
        cout << "쿼리의 키 포인트 :" << queryKeypoints-> total << endl;

        / / 쿼리의 각 키포인트 1-NN 물체 ID를 검색하여 투표 
        int numObjects = ( int ) id2name.size ();   / / 데이터베이스의 물체 수 
        int votes [numObjects];   / / 각 물체의 수집 득표 수 
        for ( int I = 0 ; i <numObjects; i + +) {
            votes [i] = 0 ;
        }
        for ( int I = 0 ; i <queryDescriptors-> total; i + +) {
            CvSURFPoint * p = (CvSURFPoint *) cvGetSeqElem (queryKeypoints, i);
            float * vec = ( float *) cvGetSeqElem (queryDescriptors, i);
             int Lap = p-> laplacian;
             int nnId = searchNN (vec, lap, labels, laplacians, objMat);
            votes [nnId] + +;
        }

        for ( int I = 0 ; i <numObjects; i + +) {
            cout << votes [i] << endl;
        }

        / / 투표 수가 최대 물체 ID를 요구 
        int maxId = - 1 ;
         int maxVal = - 1 ;
         for ( int I = 0 ; i <numObjects; i + +) {
             if (votes [i]> maxVal) {
                maxId = i;
                maxVal = votes [i];
            }
        }

        / / 물체 ID를 물체 파일명으로 변환
        string name = id2name [maxId];
        cout << "확인 결과 :" << name << endl;

        tt = ( double ) cvGetTickCount () - tt;
        cout << "Recognition Time =" << tt / (cvGetTickFrequency () * 1000.0 ) << "ms" << endl;

        / / 뒤처리
        cvReleaseImage (& queryImage);
        cvClearSeq (queryKeypoints);
        cvClearSeq (queryDescriptors);
        cvReleaseMemStorage (& storage);
        cvDestroyAllWindows ();
    }

    / / 뒤처리
    cvReleaseMat (& objMat);

    return  0 ;
}

/ ** 
* 물체 ID-> 물체 이름의 map을 만들고 반환 
* 
* @ param [in] filename 물체 ID-> 물체 이름의 대응을 저장 한 파일 
* @ param [out] id2name 물체 ID-> 물체 이름 의 map 
* 
* @ return 성공하면 true, 실패하면 false 
* / 
bool loadObjectId ( const  char * filename, map < int , string> & id2name) {
     / / 물체 ID와 물체 이름을 저장 한 파일 열기
    ifstream objFile (filename);
    if (objFile.fail ()) {
        cerr << "cannot open file :" << filename << endl;
         return  false ;
    }

    / / 한 줄씩 읽어 들여, 물체 ID-> 물체 이름의 map을 만들
    string line;
    while (getline (objFile, line, '\ n' )) {
         / / 탭으로 구분 된 문자열을 ldata에 저장
        vector <string> ldata;
        istringstream ss (line);
        string s;
        while (getline (ss, s '\ t' )) {
            ldata.push_back (s);
        }

        / / 물체 ID와 물체 이름을 추출하여 map에 저장 
        int Objid = atol (ldata [ 0 ]. c_str ());
        string objName = ldata [ 1 ];
        id2name.insert (map < int , string> :: value_type (objId, objName));
    }

    / / 뒤처리
    objFile.close ();

    return  true ;
}

/ ** 
* 키 포인트 레이블 (추출 물체 ID) 및 라플라시안과 특징 벡터를로드 labels과 objMat에 저장 
* 
* @ param [in] filename 특징 벡터를 저장 한 파일 
* @ param [out] labels 특징 벡터 추출 물체 ID 
* @ param [out] laplacianss 특징 벡터 라플라시안 
* @ param [out] objMat 특징 량을 포함하는 행렬 (행 당 하나의 특징 벡터) 
* 
* @ return 성공하면 true, 실패하면 false 
* / 
bool loadDescription ( const  char * filename, vector < int > & labels, vector < int > & laplacians, CvMat * & objMat) {
     / / 물체 ID와 특징 벡터를 저장 한 파일 열기
    ifstream descFile (filename);
    if (descFile.fail ()) {
        cerr << "cannot open file :" << filename << endl;
         return  false ;
    }

    / / 행렬의 크기를 결정하는 키 포인트의 수를 계산 
    int numKeypoints = 0 ;
    string line;
    while (getline (descFile, line, '\ n' )) {
        numKeypoints + +;
    }
    objMat = cvCreateMat (numKeypoints, DIM, CV_32FC1);

    / / 파일 포인터를 위로 축소
    descFile.clear ();
    descFile.seekg ( 0 );

    / / 데이터를 읽어 들여 행렬에 저장 
    int cur = 0 ;
     while (getline (descFile, line, '\ n' )) {
         / / 탭으로 구분 된 문자열을 ldata에 저장
        vector <string> ldata;
        istringstream ss (line);
        string s;
        while (getline (ss, s '\ t' )) {
            ldata.push_back (s);
        }
        / / 물체 ID를 꺼내 특징 벡터 레이블로하는 
        int Objid = atol (ldata [ 0 ]. c_str ());
        labels.push_back (objId);
        / / 라플라시안을 꺼내 들어 
        int Laplacian = atoi (ldata [ 1 ]. c_str ());
        laplacians.push_back (laplacian);
        / / DIM 차원 벡터의 요소를 행렬에 저장 
        for ( int J = 0 ; j <DIM; j + +) {
             float Val = atof (ldata [j + 2 ]. c_str ());   / / 특징 벡터 ldata [2] 에서 
            CV_MAT_ELEM (* objMat, float , cur, j) = val;
        }
        cur + +;
    }

    descFile.close ();

    return  true ;
}

/ ** 
* 두 벡터의 유클리드 거리를 계산하여 반환 
* 
* @ param [in] vec 벡터 1의 배열 
* @ param [in] mvec 벡터 2의 배열 
* @ param [in] length 벡터의 길이 
* 
* @ return 유클리드 거리 
* / 
Double euclideanDistance ( float * vec, float * mvec, int Length) {
     Double dist = 0.0 ;

    for ( int I = 0 ; i <length; i + +) {
        dist + = (vec [i] - mvec [i]) * (vec [i] - mvec [i]);
    }
    dist = sqrt (dist);

    return dist;
}

/ ** 
* 쿼리의 키포인트 1-NN 키 포인트를 물체 모델 데이터베이스에서 찾고 그 물체 ID를 반환 
* 
* @ param [in] vec 쿼리 키포인트의 특징 벡터 
* @ param [in] lap 쿼리 키 포인트 의 라플라시안 
* @ param [in] labels 물체 모델 데이터베이스의 각 키포인트 물체 ID 
* @ param [in] laplacians 물체 모델 데이터베이스의 각 키 포인트 라플라시안 
* @ param [in] objMat 물체 모델 데이터베이스의 각 키 포인트 특징 벡터 
* 
* @ return 지정된 키 포인트에 가장 가까운 키 포인트 물체 ID 
* / 
int searchNN ( float * vec, int Lap, vector < int > & labels, vector < int > & laplacians, CvMat * objMat) {
     int neighborObj = - 1 ;
     Double minDist = 1e6 ;
     for ( int I = 0 ; i <objMat-> rows; i + +) {
         / / 쿼리의 키 포인트와 라플라시안이 다른 키포인트는 무시 
        if (lap! = laplacians [i]) {
             continue ;
        }
        / / i 번째 행의 선두 데이터의 포인터 (여기에서 128 개가 i 번째 행의 특징 벡터) 
        float * mvec = ( float *) (objMat-> data.fl + i * DIM);
         Double D = euclideanDistance (vec , mvec, DIM);
         if (d <minDist) {
            neighborObj = labels [i];   / / NN 키포인트 물체 ID를 업데이트 
            minDist = d;            / / 최소 거리를 업데이트
        }
    }
    return neighborObj;
}

loadObjectId ()와 loadDescription ()는 물체 모델 데이터베이스 만들기 (2009-11-14)로 만든 object.txt과 descripion.txt을로드하는 함수입니다. 두 파일과 사진 폴더는 프로그램과 동일한 폴더에 보관하십시오.loadObjectId ()는 물체 ID-> 파일 이름의 map을 만듭니다. 인식 결과를 볼 때 "쿼리 물체 ID는 3입니다."라고 말 해져도 알기 어렵 기 때문에 이름을 표시하는 데 사용합니다. loadDescription ()는 특징 량 파일을로드 특징 벡터의 물체 ID를 labels에 라플라시안 을 laplacians 특징 벡터를 objMat에로드합니다. searchNN ()는 vec 및 lap 쿼리의 특징 벡터와 라플라시안 을 지정하면 물체 모델 데이터베이스를 선형 탐색하여 가장 가까운 특징 벡터를 검색하고<strong>物 idを="IDを">< strong="">반환합니다. main ()에서 쿼리 이미지의 파일 이름을 주면 그 이미지에서 특징 량을 추출 쿼리의 각 특징 벡터의 가까운 이웃을 검색하여 물체 ID의 득표 수를 계산하고 득표 수가 가장 많은 물체 ID 파일 이름을 인식 결과로 표시하고 있습니다.</strong物><>

실행 예

다음 프로그램의 실행 예입니다. 쿼리에

• dolphin_image_0001.jpg
• butterfly_image_0001.jpg

을주고 보았습니다. 170MB 정도 메모리를 사용하므로 적은 사람은 조심하십시오. 더 작은 크기 데이 대용량 데이터 세트 에서 시험해 보면 좋을지도.

물체 ID-> 물체 이름의 해시를 만듭니다 ... OK
물체 모델 데이터베이스를로드합니다 ... OK
물체 모델 데이터베이스의 물체 회 990
데이터베이스의 키 포인트 : 321935
Loading Models Time = 64689.6ms
query?> dolphin_image_0001.jpg
../dataset/caltech101_10/dolphin_image_0001.jpg
쿼리의 키 포인트 : 203
확인 결과 : dolphin_image_0001.jpg
Recognition Time = 23301.2ms
query?> butterfly_image_0001.jpg
../dataset/caltech101_10/butterfly_image_0001.jpg
쿼리의 키 포인트 : 453
확인 결과 : butterfly_image_0001.jpg
Recognition Time = 52065.9ms
query?> 

제대로 인식 결과가 쿼리와 동일한 파일이되는 것을 알 수 있다고 생각합니다. 하지만 이것은 물체 모델 데이터베이스에 등록 된 이미지와 같은 이미지를 쿼리하고 있기 때문에 당연한 결과입니다. 실은 쿼리 이미지를 조금 변형 (회전, 축소, 확대, 은폐 등) 주어도 제대로 인식 할 수 있습니다. 선형 탐색이므로 계산은 상당히 느립니다. 쿼리를 부여한 후 인식 결과를 반환 할 때까지 23 초와 52 초 걸려 있습니다. 이렇게 늦게 도저히 실시간으로 인식시킬 수 없습니다 이군요.

이제 겨우 3 일에 만드는 고속 특정 물체 인식 시스템 중 1 일째의 과제 가 끝날 떨어진 될거야. 이번 사용한 선형 탐색은 너무 느려 때문에 물체 모델 데이터베이스의 국소 특징 량을 kd-tree와 Locality Sensitive Hashing (LSH)에서 인덱싱하여 가까운 이웃 탐색 속도를 생각해서갑니다. 선형 탐색과는 비교도되지 않을 정도 계산이 빨라집니다.

3 일에 만드는 고속 특정 물체 인식 시스템 (7) 가장 가까운 이웃 탐색의 고속화 (2009-12-12)에 계속됩니다. 다음으로이 보고서 최종회 예정이다.