Fisher Vector を用いた類似画像検索
ということで，ちょっと時間がかかってますが類似画像検索まで来ました！
X. 類似画像検索
類似画像検索とは何か？という話なんですが，Googleの画像検索のように，クエリ画像に対して「よく似ている」画像を検索することです．
「類似画像検索がなぜSFMに必要なのか？」という話なんですが，SFMを実行する場合，ペアとなる写真には同じ物体が写っている必要があります．例えば東京タワーを３次元復元したい場合，東京タワーが写っていない写真を使っても意味がありません．もし手持ちの写真に東京タワーが写っていない写真も含まれているとしたら，これを除く必要があります．下記の例では，スカイツリーの写真を除外しています．
復元したい物体のスケールが「東京タワー」とか「奈良の大仏」程度なら，頑張れば一枚の写真に全てを収めることができます．が，「ローマの町並み」とか「国際通り」とかになってくると，写真一枚に全てを収めることは当然できないので，オーバーラップのある写真をペアとして繋いでいく必要があります．
上の写真は国際通りのお菓子御殿（笑）ですが，３つの写真を使ってお菓子御殿を復元したい場合，左の写真は少なくとも中央の写真と，右の写真も少なくとも中央の写真とペアにならなければ３枚の写真間につながりができません．ということで，類似している画像を検索することによって，クエリ画像とペアになる写真を見つけていきます．（※写真が時系列に並んでいる場合，おそらく直近の数枚の写真がペアになるので，類似検索は必ずしも必要無いです．）
X. Fisher Vector とは
いつもの如く TheiaSfM で使われていた方法を参考に， Fisher Vector による方法を用いました．Fisher Vector の原理を理解するには，統計とか情報幾何学とかをかじる必要があって，数学力の低い私は今頭を抱えているのですが．．．このへんもある程度理解できたらまたエントリを残せればと思います．
原理は難しいものの，ライブラリを使えば処理フローはそれほど複雑ではなかったので，簡単に書き留めておきます．大まかに４つの処理からなっていまして，
１．全画像の全SIFT特徴量を用いて，GMM（混合ガウスモデル）を生成．
ー＞生成過程では，全画像のSIFT特徴量を入力してやればOKです．多すぎる場合，間引いた方がいいかもしれません．この混合ガウスモデルが特徴量の生成モデルになります．
２．生成した GMM を用いて，個々の画像を Fisher Vector に変換．
ー＞一つ一つの画像データを Fisher Vector に変換します．ここではFisher Vector が一つの画像を表現しています．今回の設定では一つの画像から大体15000個位の SIFT 特徴量が生成されたのですが，各識別子の次元が 128 なので，SIFT を用いて一つの画像を表現すると，15000 x 128 = 1920000 位の次元のベクトルになります．が，これでは大きいので，生成した GMM のパラメータ（の勾配）空間を使って次元削減してやります．この次元削減によって，今回のケースだと一枚の画像が 8000 次元くらいのベクトル（= Fisher Vector）で表現できるようになりました．
３．全画像ペア間の Fisher Vector の距離を計算します．
ー＞「２つの画像が似ている」＝「２つの画像の Fisher Vector が似ている」ということになります．あとは，全ペアの Fisher Vector の距離を総当り計算して行列として保持しておけば，画像間の類似関係をいつでも参照することができます．
４．クエリ画像とその他画像の距離チェックし，距離が近いものを類似画像とする．
ー＞ クエリ画像のインデックスをもつ Matching Matrix の列（もしくは行）を取り出せば，クエリ画像とその他全画像の距離がわかります．
X. 生成した SIFT 識別子による GMM のトレーニング
下記，ほぼ VLFeat ライブラリの呼び出しをしただけですが，，，
void FisherVectorEncoder::TrainGMM(uint64_t max_itr, const std::vector<Eigen::VectorXf>& train_data) { // X. Create GMM object. LOG(INFO) << "vl_gmm_new : "; VlGMM* gmm = vl_gmm_new(VL_TYPE_FLOAT, num_dimension_, num_clusters_); // X. Set the maximum number of EM iterations to 100. LOG(INFO) << "vl_gmm_set_max_num_iterations : "; vl_gmm_set_max_num_iterations(gmm, max_itr); // X. Set the initialization to random selection. LOG(INFO) << "vl_gmm_set_initialization : "; vl_gmm_set_initialization(gmm, VlGMMRand); // X. Cluster the data. (Train the GMM). num_data_ = train_data.size(); LOG(INFO) << "Converting to MatrixXf : "; Eigen::MatrixXf mat_data = ConvertVectorOfFeaturesToMatrix(train_data); LOG(INFO) << "Data count for training is : " << num_data_; vl_gmm_cluster(gmm, mat_data.data(), num_data_); LOG(INFO) << "Training is Done! Now storing data!"; LOG(INFO) << "means copied!"; means_.resize(num_dimension_ * num_clusters_); std::memcpy(means_.data(), vl_gmm_get_means(gmm), sizeof(float) * num_dimension_ * num_clusters_); LOG(INFO) << "covariances copied!"; covariances_.resize(num_dimension_ * num_clusters_); std::memcpy(covariances_.data(), vl_gmm_get_covariances(gmm), sizeof(float) * num_dimension_ * num_clusters_); LOG(INFO) << "priors copied!"; priors_.resize(num_clusters_); std::memcpy(priors_.data(), vl_gmm_get_priors(gmm), sizeof(float) * num_clusters_); LOG(INFO) << "posteriors copied!"; posteriors_.resize(num_clusters_ * num_data_); std::memcpy(posteriors_.data(), vl_gmm_get_posteriors(gmm), sizeof(float) * num_clusters_ * num_data_); LOG(INFO) << "Deleting gmm"; vl_gmm_delete(gmm); LOG(INFO) << "gmm deleted."; }
X. 画像間距離マトリクスの作成
全画像間の距離を計算しています．ここも結構時間がかかります．
void CreateMatchingMatrix(const std::string& gmm_file_path, const std::string& matching_matrix_path, std::unordered_map<std::string, ImageInfo>& image_info_map) { FisherVectorEncoder fisher_encoder(gmm_file_path); // X. LOG(INFO) << "Create filename index map."; std::unordered_map<std::string, int> filenames_indices; std::unordered_map<int, std::string> indices_filemanes; int index = 0; for (auto citr = image_info_map.cbegin(); citr != image_info_map.cend(); ++citr) { std::filesystem::path p(citr->first); std::string filename = p.replace_extension("").filename().string(); filenames_indices[filename] = index; indices_filemanes[index] = filename; index++; } LOG(INFO) << "Matching matrix computation starts!"; int size = image_info_map.size(); Eigen::MatrixXf matching_matrix(size, size); int cnt = 0; int total_size = image_info_map.size(); for (const auto& [filename1, value] : image_info_map) { int idx1 = filenames_indices[filename1]; matching_matrix(idx1, idx1) = 0.0; LOG(INFO) << "Image Distance... " << cnt << " / " << total_size; cnt++; for (int idx2 = idx1 + 1; idx2 < size; idx2++) { Eigen::VectorXf feature1 = fisher_encoder.ComputeFisherVector(image_info_map[filename1].descriptors_); std::string filename2 = indices_filemanes[idx2]; Eigen::VectorXf feature2 = fisher_encoder.ComputeFisherVector(image_info_map[filename2].descriptors_); float score = (feature1 - feature2).squaredNorm(); matching_matrix(idx1, idx2) = score; matching_matrix(idx2, idx1) = score; } } std::cout << matching_matrix << std::endl; std::ofstream writer(matching_matrix_path, std::ios::out | std::ios::binary); cereal::PortableBinaryOutputArchive output_archive(writer); output_archive(filenames_indices, matching_matrix); }
X. 実行結果！
ということで，類似画像検索をやってみました！使った画像セットは，SIFTのエントリのときにリンクを貼った下記の画像セットです．
・https://research.cs.cornell.edu/1dsfm/
上記サイトの Gendarmenmarkt images (tar, 1.0 GB) をダウンロードして使いました．
クエリ画像としては，下記の画像を使いました．
で結果ですが，スコアの低い（類似度が高い）画像から順に上位１０枚の画像が下記のようになりました．下記の結果を見てもわかるのですが，やっぱり天候とか昼夜の条件によってスコアに開きが出てしまうのは仕方ないのかもしれませんね．．．この辺の影響を抑える方法があれば，つくばチャレンジにも使えるようになるかも．
スコアの分布は下記のようになります．最低スコア（類似度が高い）0.516687を皮切りに，上限2.3くらいまで連続的に分布していきます．
X. 実験に使ったコード
VLFeat & Cereal も Submodule として取り込んであるので，下記のコマンドを叩いて貰えれば動くとこまでは行きます．
git clone --recurse-submodules git@github.com:koichiHik/blog_vlfeat_image_compare.git cd blog_vlfeat_image_compare/ sh build.sh
で，今回は実行ファイルが３つありまして，順を追って実行する必要があります．
１．作成済のSIFT特徴量を用いて，GMMの生成
（flagfile.txt に SIFT 特徴量，画像ファイルのディレクトリパスを指定し，生成した GMM モデルのパラメータファイルの出力パスを指定します．）
./build/train_gmm_model --flagfile=./flagfiles/train_gmm_model.txt
２．生成したGMMを用いて，全画像の Fisher Vector を計算．各画像間の距離マトリクスを作成する．
（flagfile.txt に SIFT 特徴量のディレクトリパス，生成した GMM のパラメータファイルパスを指定し．生成するマッチングマトリクスの出力ファイルパスを指定します．）
./build/create_matching_matrix --flagfile=./flagfiles/train_gmm_model.txt
３．クエリ画像のファイル名を指定すると，類似している上位画像を出力します．
（flagfile.txt に SIFT 特徴量，画像ファイルのディレクトリパス，マッチングマトリクスのファイルパスと，ターゲット画像のファイル名を指定します．）
./build/show_similar_images --flagfile=./flagfiles/show_similar_images.txt
X. 参考文献
- Exploiting generative models in discriminative classifiers.
- Fisher Kernels on Visual Vocabularies for Image Categorization.
- Image Classification with the Fisher Vector : Theory and Practice.
