人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

3日で作る高速特定物体認識システム (5) 物体モデルデータベースの作成

3日で作る高速特定物体認識システム (4) 特徴点のマッチング(2009/11/2)のつづきです。

今回は、高速特定物体認識システムの物体モデルデータベースを作成してみます。クエリとして与えた画像が何かはこの物体モデルデータベースを検索することで認識できるようになります。特定物体認識では、クエリとして与えた画像が物体モデルデータベースにあらかじめ登録されていないとまず認識できません(局所特徴量を用いるので多少のスケール変化や回転などには対応できますが)。忘れてしまった方は物体認識システムの構成(2009/10/18)を参照してください。

画像データセットの準備

自分で撮影した画像を登録できるようにしてもよかったのですが、大量の画像を撮影するのは面倒なのでおなじみのCaltech101の画像セットを用いて物体モデルを作成します。

類似画像検索システムを作ろう(2009/10/3)の画像データセットを用意を参考にcaltech101フォルダに画像ファイルだけコピーしたデータを用意します。少し多すぎるので各カテゴリから10枚ずつ画像を抜き出して(IDが0001から0010まで)caltech101_10というデータを作ります。caltech101_10というフォルダを作成して以下のスクリプトを実行すると990枚の画像データができます。

#coding:utf-8
import os
import shutil

IMAGE_DIR = "caltech101"
OUT_DIR = "caltech101_10"

for file in os.listdir(IMAGE_DIR):
    id = int(file[-8:-4])
    if id <= 10:
        print file
        shutil.copy("%s/%s" % (IMAGE_DIR, file), "%s/%s" % (OUT_DIR, file))

物体モデルデータベースの作成

caltech101_10という990枚の画像から特徴量を抽出して物体モデルデータベースに格納していきます。各画像から抽出したキーポイントの特徴量は物体IDとひもづけて保存する必要があります。そこで、物体IDと特徴量を保存するテーブルが必要になります。

物体IDテーブル:物体ID 画像ファイル名
特徴量テーブル:物体ID ラプラシアン キーポイントの特徴量

SQLiteなどでデータベースを作ってもよいのですが、コードが複雑になるのでここでは簡単のためファイルにテキスト形式でデータを保存してみました。物体IDファイル(object.txt)特徴量ファイル(description.txt)です。

物体IDファイルは以下のようなタブ区切りの書式です。登録した順番に物体IDが自動で割り当てられます。

0    accordion_image_0001.jpg
1    ant_image_0001.jpg
2    bonsai_image_0001.jpg
3    butterfly_image_0001.jpg
4    dolphin_image_0001.jpg

特徴量ファイルは以下のようなタブ区切りの書式です。すべての画像の特徴量は1つのファイルに保存しています。各物体は複数のキーポイントを持つ点に注意が必要です。なのでデータベースを使う場合は物体IDを主キーにできません。

0    1    0.03    0.05    ....   # 物体ID=0の1つ目のキーポイント
0    1    0.28    0.14    ....   # 物体ID=0の2つ目のキーポイント
0   -1    0.31    0.01    ....   # 物体ID=0の3つ目のキーポイント
....
1   -1    0.24    0.31    ....   # 物体ID=1の1つ目のキーポイント
1    1    0.15    0.22    ....   # 物体ID=1の2つ目のキーポイント
1    1    0.01    0.03    ....   # 物体ID=1の3つ目のキーポイント
....

caltech101_10の全画像ファイルから上記の物体IDファイルと特徴量ファイルを抽出するプログラムです。局所特徴量にはSURFを使っています。詳しくは、SURFの抽出(2009/10/30)を参照してください。ディレクトリのファイルスキャンにopendir()を使っています。これは、MinGWのg++では使えますが、もしかしたらVisual C++では使えないかも・・・もしエラーが出たらここらを参考に書き換えてください。

#include <cv.h>
#include <highgui.h>
#include <iostream>
#include <fstream>
#include <sys/types.h>
#include <dirent.h>

using namespace std;

const char *IMAGE_DIR = "caltech101_10";
const char *OBJ_FILE = "object.txt";        // 物体ID格納ファイル
const char *DESC_FILE = "description.txt";  // 特徴量格納ファイル

const double SURF_PARAM = 400;  // SURFのパラメータ
const int DIM = 128;            // SURF特徴量の次元数

/**
 * SURF特徴量を抽出する
 *
 * @param[in]  filename         画像ファイル名
 * @param[out] imageKeypoints   キーポイント(出力のため参照渡し)
 * @param[out] imageDescriptors 各キーポイントのSURF特徴量(出力のため参照渡し)
 * @param[out] storage          Memory Storage(出力のため参照渡し)
 *
 * @return 成功なら0、失敗なら1
 */
int extractSURF(char *filename, CvSeq* &imageKeypoints, CvSeq* &imageDescriptors, CvMemStorage* &storage) {
    // グレースケールで画像をロードする
    IplImage *img = cvLoadImage(filename, CV_LOAD_IMAGE_GRAYSCALE);
    if (img == NULL) {
        cerr << "cannot load image file: " << filename << endl;
        return 1;
    }

    storage = cvCreateMemStorage(0);
    CvSURFParams params = cvSURFParams(SURF_PARAM, 1);
    cvExtractSURF(img, 0, &imageKeypoints, &imageDescriptors, storage, params);

    return 0;
}

/**
 * 物体モデルをファイルに保存する
 *
 * @param[in]   objId              オブジェクトID
 * @param[in]   filename           画像ファイル名
 * @param[in]   imageKeypoints     キーポイント
 * @param[in]   imageDescriptors   各キーポイントの特徴量
 * @param[in]   objFile            物体IDファイルのハンドラ
 * @param[in]   descFile           特徴量ファイルのハンドラ
 *
 * @return 成功なら0、失敗なら1
 */
int saveFile(int objId, char *filename, CvSeq* imageKeypoints, CvSeq* imageDescriptors, ofstream& objFile, ofstream& descFile) {
    cout << objId << " " << filename << " " << imageDescriptors->total << endl;

    // 物体IDファイルへ登録
    objFile << objId << "\t" << filename << endl;

    // オブジェクトID, ラプラシアン, 128個の数字をタブ区切りで出力
    for (int i = 0; i < imageDescriptors->total; i++) {  // 各キーポイントの特徴量に対し
        // オブジェクトID
        descFile << objId << "\t";

        // 特徴点のラプラシアン(SURF特徴量ではベクトルの比較時に使用)
        const CvSURFPoint* kp = (const CvSURFPoint*)cvGetSeqElem(imageKeypoints, i);
        int laplacian = kp->laplacian;
        descFile << laplacian << "\t";

        // 128次元ベクトル
        const float *descriptor = (const float *)cvGetSeqElem(imageDescriptors, i);
        for (int d = 0; d < DIM; d++) {
            descFile << descriptor[d] << "\t";
        }

        descFile << endl;
    }

    return 0;
}

int main(int argc, char **argv) {
    int ret;

    // 物体IDファイルを開く
    ofstream objFile(OBJ_FILE);
    if (objFile.fail()) {
        cerr << "cannot open file: " << OBJ_FILE << endl;
        return 1;
    }

    // 特徴量ファイルを開く
    ofstream descFile(DESC_FILE);
    if (descFile.fail()) {
        cerr << "cannot open file: " << DESC_FILE << endl;
        return 1;
    }

    // IMAGE_DIRの画像ファイル名を走査
    DIR *dp = opendir(IMAGE_DIR);
    if (dp == NULL) {
        cerr << "cannot open directory: " << IMAGE_DIR << endl;
        return 1;
    }

    int objId = 0;  // オブジェクトID
    struct dirent *entry;
    while (1) {
        entry = readdir(dp);

        if (entry == NULL) {
            break;
        }

        // .と..は無視する
        if (strncmp(entry->d_name, ".", 1) == 0 || strncmp(entry->d_name, "..", 2) == 0) {
            continue;
        }

        char *filename = entry->d_name;

        // SURFを抽出
        char buf[1024];
        snprintf(buf, sizeof buf, "%s/%s", IMAGE_DIR, filename);
        CvSeq *imageKeypoints = 0;
        CvSeq *imageDescriptors = 0;
        CvMemStorage *storage = 0;
        ret = extractSURF(buf, imageKeypoints, imageDescriptors, storage);
        if (ret != 0) {
            cerr << "cannot extract surf description" << endl;
            return 1;
        }

        // ファイルへ出力
        ret = saveFile(objId, filename, imageKeypoints, imageDescriptors, objFile, descFile);
        if (ret != 0) {
            cerr << "cannot save surf description" << endl;
            return 1;
        }

        // 後始末
        cvClearSeq(imageKeypoints);
        cvClearSeq(imageDescriptors);
        cvReleaseMemStorage(&storage);

        objId++;
    }

    objFile.close();
    descFile.close();
    closedir(dp);

    return 0;
}

上記のプログラムで990枚の画像から物体IDファイルと特徴量ファイルの作成にはうちの環境で5分くらいかかりました。description.txtはかなりでかくて420MBもあります。うかつにメモ帳とかで開かないようにしないと(笑)サイズがでかいのは浮動小数点数をテキストで保存してるからですが、バイナリで格納すればもっと小さくなりますね。大規模な画像を対象にする場合は工夫が必要です。990枚の画像の合計キーポイント数は321932個ありました。1枚あたり平均325個という計算です。Caltech101の画像はサイズが小さいので少ないです。

物体モデルデータベースを特定物体認識にどう使うか?

今回作成したobject.txtとdescription.txtをここでは物体モデルデータベースと呼びます。これを特定物体認識システムにどう使うかですが下の図のような感じです。

f:id:aidiary:20091114125457p:plain

今回は990枚の画像を格納した図右側の物体モデルデータベースを作成しました。特定物体認識ではクエリ画像(左のイルカ)を与えてこれが物体モデルデータベースのどの画像かを言い当てるという処理です。上の例の場合、オブジェクトID=4と認識できれば大正解です。

この認識方法は、すでにご紹介している特徴点のマッチング(2009/11/2)とほとんど同じ方法です。特徴点のマッチングでは画像対画像でしたが、特定物体認識では画像対物体モデルデータベースで比較するという違いがあるだけです。

物体モデルデータベースには大量のキーポイントが含まれているため特徴点のマッチングより高速な最近傍計算手法が必要になります。特徴点のマッチングでは画像1のキーポイント数が800、画像2のキーポイント数が800だとすると全部で800x800=640000回程度の距離計算で画像1の各キーポイントの最近傍点が見つかります。ここで画像2を物体モデルデータベースに置き換えると全部で800x321932=257545600回もの距離計算になります。効率の悪い線形探索では時間がかかりすぎるわけです。とはいうもののどれくらいかかるのか確かめるため次回は線形探索を用いた特定物体認識を行ってみます。

3日で作る高速特定物体認識システム (6) 線形探索を用いた特定物体認識へつづきます。