Archive for the ‘OpenCV’ Category

Xcode4でつくるOpenCV環境

月曜日, 5月 21st, 2012
このエントリーを含むはてなブックマークはてなブックマーク - Xcode4でつくるOpenCV環境


 
ここでは、Xcode4を用いてOpenCVのプログラムを組むために必要な環境の整え方を紹介します。用いるXcodeはXcode4.3、OpenCVのバージョンは2.3です。また、動作はMacOSX 10.7 Lionで確認しています。

 Xcodeのインストール

まずはじめに、Xcode4.3をApp Storeからダウンロードします。以前はiOS developper centerからダウンロードしていましたが、最近はApp Storeから入手できるようです。
 

 gccのインストール

コマンドライン用のgccがインストールされていない場合はXcodeのPreferenceからDownloadsタブへとすすみ、Command Line Toolsをインストールしておいて下さい。コマンドラインで使えるgccがない場合、homebrewでOpenCVをインストールしようとしてもエラーで停止してしまいます。
 

  

 homebrewのインストール

つぎに、OpenCVをインストールするため、パッケージ管理システムのhomebrewをインストールします。まずは本家からhomebrewをダウンロードします。
 

/usr/bin/ruby -e "$(/usr/bin/curl -fsSL https://raw.github.com/mxcl/homebrew/master/Library/Contributions/install_homebrew.rb)"

 

 OpenCVのインストール

homebrewがインストールできたら、つぎは以下のコマンドでOpenCVをインストールします。2012年5月現在では問題なくインストールできます。パッケージのインストールが完了すると、/usr/local/Cellar/opencv以下にOpenCVの実行に必要なインクルードファイルとライブラリファイルがインストールされます。
 

sudo /usr/local/bin/brew install opencv 

 

 Xcodeの設定

ここまでで、OpenCVはインストールできたので、次はXcodeからOpenCVを使う設定を行います。新規プロジェクトをCommand Line Toolとして作成します。プロジェクトが作成できたら、先ほどインストールしたOpenCVのインクルードファイルとライブラリファイルの場所をXcodeに教えてやる必要があります。


 
まずは、各ファイルの場所を指定します。Xcodeの左側に配置されているProject navigator上でプロジェクトファイルを選択し、TARGETS、Build Settingタブへとすすみ、Header Search PathsとLibrary Search Pathsの項目にどちらも/usr/local/Cellar/opencvと入力します。この際、入力欄の左側にあるチェックボックスにチェックを入れてリカーシブルにファイルが検索されるようにします。
 

 
最後にライブラリをリンクします。Build Settingsの横にあるBuild Phasesタブをクリックし、その中にあるLink Binary With Libraryesの行にOpenCVのライブラリをD&Dします。今回インストールしたOpenCVのライブラリは/usr/local/Cellar/opencv/2.3.1a/libにあるため、このフォルダに移動し(Finderで移動->フォルダへ移動を選択)必要なライブラリをXcodeにドラックして下さい。今回は以下の3ファイルをリンクしました。
 
・libopencv_core.dylib
・libopencv_highgui.dylib
・libopencv_imgproc.dylib
 

 
 
 

 OpenCV実験

実際にOpenCVがXcodeから使えるかどうか以下のサンプルプログラムを使って実験してみてください。うまくOpenCVがインストールできていれば、今流行の金環日食が見れることでしょう(笑)
 

#include <cv.h>
#include <highgui.h>

int main ()
{
    IplImage *img = cvCreateImage(cvSize(256, 256), IPL_DEPTH_8U, 3);
    cvZero(img);
    cvCircle(img, cvPoint(128, 128), 128, cvScalar(170,255,255), 3);
    
    cvNamedWindow("test");
    cvShowImage("test", img);
    
    cvWaitKey(0);
    return 0;
}

 
 

10分で学ぶOpenCV超入門

日曜日, 3月 27th, 2011
このエントリーを含むはてなブックマークはてなブックマーク - 10分で学ぶOpenCV超入門


 
 
C言語を勉強した人がOpenCVを始める取っ掛かりとして使ってもらえれば嬉しいです。配列とか関数は分かるけど、ポインタはちょっと・・・というくらいの人から読めるように書いてみました。
 

OpenCVとは

 
OpenCVとは画像処理で使える関数がたくさん用意されている関数群(フレームワーク)です。例えばC言語でファイルを読み込むのにfgets()という関数が用意されているように、OpenCVでは画像を読み込むcvLoadImage()という関数が用意されています。勿論、用意されている関数はこれだけではなく、画像をグレースケール化したり画像中から四角形を検出したり、顔を検出したりする関数まで用意されています。

 

OpenCVでの処理の流れ

OpenCVを使ったプログラムの基本的な流れは


 
といった流れになっています。以下では、まず始めにstep1とstep3だけを行うプログラムを作成したあとに徐々に複雑なプログラムを作成していきます。どんなに複雑なプログラムでも、基本の流れは上のようになっているので、これを見失わないようにしてください。
 
 

OpenCVを使ったプログラム

 
1. 画像を読み込み表示する

単純に画像ファイルから画像データを読み込み、それを表示するプログラムです。最初ですのでプログラムについて細かく説明していきます。

まずはじめに、OpenCVにはIplImage型という画像を格納する型が用意されています。C言語では整数をいれるint型や小数をいれるdouble型が用意されていましたが、これと同様に画像を入れるIplImage型があるわけです。
 
3行目ではIplImage*型のimgという変数を宣言しています。ポインタ型で宣言されていますが、とりあえずは無視して普通の変数と同じように考えても大丈夫です(^^;;)このimg変数にcvLoadImage関数を使って画像を読み込んでいます。

4行目から7行目まではエラー処理です。画像が読み込めなかった場合には変数の中身がNULLになることを利用してエラー検出をしています。

9行目と10行目が画像の表示処理です。9行目でImageという名前のウインドウを作成し、10行目で作成したImageウインドウに画像を表示しています。

13行目と14行目は後始末です。ポインタ型を使った場合には必ず確保したメモリを開放する必要があるのでプログラムの最後で開放しています。iPhoneなどの環境ではメモリ制限が厳しいのでこの処理は忘れないようにしましょう。

int main()
{
	IplImage *img = cvLoadImage("test.jpg", CV_LOAD_IMAGE_ANYCOLOR);
	if( img == NULL ){
		fprintf(stderr, "no such file or directory\n");
		exit(-1);
	}
	
	cvNamedWindow("Image",CV_WINDOW_AUTOSIZE);
	cvShowImage("Image",img);
	cvWaitKey(0); 
	
	cvReleaseImage(&img); 
	cvDestroyWindow("Image");
	
	return 0;
}

 
 
 
2. 画像のサイズを変更する
 
 
 
 
読み込んだ画像のサイズを縦横1/2にして表示するプログラムです。プログラムとしては上記のものと大半が同じですので、違うところだけ説明していきたいと思います。

1行目ではimg変数に画像を読み込んでいます。2行目ではリサイズ後の画像を格納する変数resizedを定義してから、直後にcvCreateImage()関数で画像の大きさや種類などを指定して、どれくらいのメモリが必要かを記述しています。

このように、IplImage*型を使う場合には、cvCreateImage関数を使って画像の大きさ、1pxのビットデプス、レイヤ数の3つを指定する必要があります。この3つについて以下に説明します。

画像の大きさはcvSize(幅,高さ)、またはcvGetSize(画像)を使って指定します。今回は縦横1/2の大きさにするので、先ほどimgに読み込んだ画像の高さと幅の半分を指定します。img画像の幅と高さはそれぞれimg->width, img->heighで取得できます(C言語のポインタ型で宣言された構造体のメンバにアクセスする際の記述です)

次にビットデプスですが、1pxの明度は大抵の場合0から255で表すのでビットデプスは8bitになります。今回もIPL_DEPTH_8Uを指定しています。

最後のレイヤ数ですが下図に示すように、グレースケール画像の場合には1レイヤ、RGB画像(カラー画像)の場合には3レイヤ、RGBA画像(透明部分を含んだ画像)の場合には4レイヤが必要になります。今回は単純なカラー画像なので3レイヤを指定しています。

11行目では処理の本体であるリサイズを行っています。といっても、複雑な処理を記述する必要はなくcvResize関数に元画像imgと結果を格納する画像resizedと補間方法を渡しているだけです。CV_INTER_CUBICはバイキュービック法を用いて画像を補間します。このアルゴリズムは結果画像が綺麗な代わりに、処理時間が遅くなります。一方、CV_INTER_LINIERを指定すると結果画像は雑になるけれども高速な処理が可能なアルゴリズムが適応されます。

このように、引数によってアルゴリズムを差し替えられるのがOpenCVの強みの1つではないでしょうか?

int main()
{
	IplImage *img = cvLoadImage( "test.jpg", CV_LOAD_IMAGE_ANYCOLOR);
	IplImage *resized = cvCreateImage(cvSize(img->width/2, img->height/2), IPL_DEPTH_8U, 3);
	
	if( img == NULL ){
		fprintf(stderr, "no such file or directory\n");
		exit(-1);
	}
	
	cvResize(img, resized, CV_INTER_CUBIC);
	
	cvNamedWindow("Image",CV_WINDOW_AUTOSIZE);
	cvShowImage("Image",resized);
	cvWaitKey(0); 
	
	cvReleaseImage(&img); 
	cvReleaseImage(&resized); 	
	cvDestroyWindow("Image");
	
	return 0;
}

 
 
 
3. 画像をグレースケール化する
 

 
次のプログラムは画像をカラー画像からグレースケールに変換するものです。4行目でグレースケール化した画像を格納する変数grayを宣言し、直後でcvCreateImageを用いて大きさ・ビットデプス・レイヤ数を指定しています。

変数grayはグレースケール画像を格納するものであり、画像のサイズはimgと同じものなのでcvGetSizeを使ってimgと同じサイズを指定しています。また、グレースケールのレイヤ数は1枚なのでcvCreateImageの3つめの引数には1を指定しました。

グレースケール変換の本体は11行目に記述しています。こちらもリサイズと同じく、cvCvtColorという関数だけ処理することが可能です。関数の引数に元画像img、変換画像gray、変換方法CV_RGB2GRAYを渡しています。

3つめの引数にCV_RGB2GRAYを指定することでRGB画像からGRAY画像に変換することが可能です。(RGB2GRAYの2はtoの略記です)他にもHSV画像やRGBA画像など、かなり自由に変換することができるので非常に重宝する関数です。

自分でグレースケール変換処理を記述する場合、RGBからグレースケールに変換する場合にはRGB各レイヤの明度に対して、以下の式で変換を行う必要があります。
 

 
このような変換を知らなくても記述できてしまうのがOpenCVの強みでもあります。(まぁ、問題でもあるんですけどね・・・)

int main()
{
	IplImage *img = cvLoadImage( "test.jpg", CV_LOAD_IMAGE_ANYCOLOR);
	IplImage *gray = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 1);
	
	if( img == NULL ){
		fprintf(stderr, "no such file or directory\n");
		exit(-1);
	}
	
	cvCvtColor(img, gray, CV_RGB2GRAY);
	
	cvNamedWindow("Image",CV_WINDOW_AUTOSIZE);
	cvShowImage("Image",gray);
	cvWaitKey(0); 
	
	cvReleaseImage(&img); 
	cvReleaseImage(&gray);	 
	cvDestroyWindow("Image");
	
	return 0;
}

 
 
 
4. 画像を2値化する
 
 
 
超入門編の最後として、画像を白と黒の2値化するプログラムを紹介します。まずは、読み込んだ画像をグレースケール化し、その後グレースケール値を閾値に基づいて白か黒に振り分けます。具体的には各ピクセルのグレースケール値が閾値以上のなら白色(明度:255)に、閾値以下なら黒色(明度:0)に変換します。


 
まずは4, 5行目でグレースケール画像を格納するgrayと2値化画像を格納するbinを宣言しています。サイズは読み込んだ画像と同じものなので、どちらもcvGetSizeで指定、レイヤ数は1レイヤを指定しています。

また、12行目でグレースケール化、13行目で2値化を行っています。cvThreshold関数の引数には元画像、結果画像、閾値、最大値、変換方法を指定しています。3つめの引数である閾値の値を変化させることで画像の白部分と黒部分の割合が変化します。
 

int main()
{
	IplImage *img = cvLoadImage( "test.jpg", CV_LOAD_IMAGE_ANYCOLOR);
	IplImage *gray = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 1);	
	IplImage *bin = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 1);
	
	if( img == NULL ){
		fprintf(stderr, "no such file or directory\n");
		exit(-1);
	}
	
	cvCvtColor(img, gray, CV_RGB2GRAY);
	cvThreshold(gray, bin, 128, 255, CV_THRESH_BINARY);
	
	cvNamedWindow("Image",CV_WINDOW_AUTOSIZE);
	cvShowImage("Image",bin);
	cvWaitKey(0); 
	
	cvReleaseImage(&img); 
	cvReleaseImage(&bin);	 
	cvDestroyWindow("Image");
	
	return 0;
}

 
このように、OpenCVを使えば非常に簡単に画像処理が行えます。用意されている関数を上手く使うことで、QRコードの読み取りや顔の特徴点検出など、さらに高度な処理が可能となります。次回はlplimageのピクセルにアクセスする方法を中心に解説していきたいと思います。
 
 

参考書籍

 
「OpenCVプログラミングブック」
OpenCVを1から始めるのなら、一番わかり易い参考書は本書でしょう。画像処理の基礎的なアルゴリズムをOpenCVで実装している例が多数掲載されているため、画像処理の勉強にも最適です。

OpenCV プログラミングブック 第2版 OpenCV 1.1対応
奈良先端科学技術大学院大学 OpenCVプログラミングブック制作チーム
毎日コミュニケーションズ
売り上げランキング: 66050

 
「詳解OpenCV」
ただ、どの大概の入門書がそうであるように、画像処理の踏み込んだ話までは書かれていません。(例えばフーリエ領域での計算とか計算コストの話、などなど)そこで役に立つのがオライリーの「詳解OpenCV」です。OpenCVの参考書というよりも、画像処理の中級書といった方が正しいかもしれません。高度な内容まで網羅されているので、画像処理をやるなら、手元に一冊置いておいて絶対損はありませんよ!

詳解 OpenCV ―コンピュータビジョンライブラリを使った画像処理・認識
Gary Bradski Adrian Kaehler
オライリージャパン
売り上げランキング: 29059

 
 

コラム
 
「plImage*型を使う場合には、必ず画像の大きさ・デプス・レイヤ数を必ず指定」といっておきながら、変数imgを宣言したときにはcvLoadImageを使っているぢゃん!!と思われる方もいたかと思います。

はい、仰るとおりです(笑)実はファイルを読み込んだ際に、ファイルに埋め込まれた情報からcvLoadImage関数の中で内部的に指定してくれています。なので、例外的にcvCreateImageでメモリ確保を明示的に行う必要がないのです。(勿論、cvReleaseImageでメモリの開放は必要です)

cvLoadImageの他には、cvCloneImageという関数もありまして、こちらも明示的に宣言する必要はありません。まぁ、例外的なのはこの2つくらいなので、入門編ではちょこっと説明を端折ってしまいました。
 

 
 

DFTでガウシアンフィルタを高速化する

木曜日, 1月 27th, 2011
このエントリーを含むはてなブックマークはてなブックマーク - DFTでガウシアンフィルタを高速化する

 
 
DFTを使って、ガウシアンフィルタ(Gaussian Filter)を高速化する方法を説明します。基本的なアイデアは、対象画像を一旦フーリエ変換し、フーリエ領域(Fourie domain)でマスク処理を行うことで、計算量を減らそうというものです。

ガウシアンフィルタとは?

ガウシアンフィルタでは、対象画素に近い画素に大きな重みをつけ、遠い画素には小さい重みを付けた加重平均を取ることで、自然なぼかしを実現しています。この重みづけを下のガウス関数を用いて行っているのでガウシアンフィルタと呼ばれます。

この式からも分かるようにσの値が小さいとぼかし効果は小さく、σの値が大きくなるとそれに従ってぼかし効果も大きくなります。
 
 
ガウシアンフィルタはボックスフィルタに比べて非常にきれいなぼかしが可能です。ボックスフィルタの場合、ぼかしを強くしたとき画質劣化がひどいのに対して、ガウシアンフィルタでは自然なぼかしを実現しています。


 
 
 

高速化のアイデア

ガウシアンフィルタを高速化する方基本的なアイデアは、上にも書いたように、時間のかかる畳み込み演算の部分をフーリエ領域に持ち込んで、計算量をへらそうというものです。図示するとこんな感じ。

cvtemplatematch5

 
空間領域(spatial domain)での畳み込み演算がフーリエ領域(fourie domain)では乗算に帰着できる理論はこの辺の論文を参考にしてみてください。

  • P. M. Morse and H. Feshbach, “Fourier transforms,” in Methods of Theoretical Physics (Part I, pp. 453–471), New York: McGraw-Hill, 1953.
  • R. Bracewell, “Convolution” and “Two-dimensional convolution,” in The Fourier Transform and Its Applications (pp. 25–50 and 243–244), New York: McGraw-Hill, 1965.

 
 
 

ガウシアンフィルタの高速化

1. たたみ込み積分での処理

畳み込み演算をした場合には、下の図のようにガウシアンフィルタのカーネルと、対象画像の画素との畳み込み演算( convolution )を行うことで処理を行います。

ガウシアンフィルタのカーネルサイズをMxM、対象の画像サイズをNxNとした場合、たたみ込み積分を行うと計算量は O(N2M2)になります。このように、畳み込み演算では、ガウシアンフィルタのカーネルサイズが大きくなればなるほど処理時間がかかるという問題があります。
 
 
 
2. フーリエ変換を用いた処理

一方で、DFTを用いて処理した場合の処理の流れは下のようになります。対象画像をDFTでフーリエ変換し、その結果に対して高周波部分を全て0にするようなマスクをかけます(乗算処理)。こうすることで高周波部分が除去され、ローパスフィルタをかけたのと同じ効果が得られます。
 

DFTを用いた場合の計算量はO(N2logN)に比例します。このように、DFTを用いることでガウシアンフィルタのカーネルサイズにかかわらず一定時間で処理できるようになるのです。
 
 
 

高速ガウシアンフィルタのプログラム

上に書いたように、DFTを用いた高速ガウシアンフィルタのプログラムのコア部分を載せます。このプログラムはこの本を参考させて頂きました。

詳解 OpenCV ―コンピュータビジョンライブラリを使った画像処理・認識
Gary Bradski Adrian Kaehler
オライリージャパン
売り上げランキング: 15137

この関数の引数、srcとfilterがそれぞれ元画像とガウシアンフィルタのカーネルに相当します。まずは、それぞれの行列をcvDFT()関数を用いてフーリエ変換し、その結果どおしをcvMulSpectrums()関数で乗算し、最後に逆フーリエ変換することで、ぼかしのかかった画像を作成しています。
 

void speedy_conv (
	 const CvMat* src, 
	 const CvMat* filter,
	 CvMat*	dst
 ){
	int dft_M = cvGetOptimalDFTSize( src->rows+dst->rows-1 ); 
	int dft_N = cvGetOptimalDFTSize( src->cols+dst->cols-1 );
	CvMat* dft_A = cvCreateMat( dft_M, dft_N, CV_32F ); 
	CvMat* dft_B = cvCreateMat( dft_M, dft_N, CV_32F); 
	CvMat tmp;

	// copy A to dft_A and pad dft_A with zeros 
	// 
	cvGetSubRect( dft_A, &tmp, cvRect(0,0,src->cols,src->rows)); 
	cvCopy( src, &tmp );
	cvGetSubRect( dft_A, &tmp, cvRect( src->cols, 0, dft_A->cols-src->cols, src->rows));
	cvZero( &tmp );

	// no need to pad bottom part of dft_A with zeros because of 
	// use nonzero_rows parameter in cvDFT() call below 
	// 
	cvDFT( dft_A, dft_A, CV_DXT_FORWARD, src->rows );
	
	// repeat the same with the second array 
	// 
	cvGetSubRect( dft_B, &tmp, cvRect(0,0,filter->cols,filter->rows) ); 
	cvCopy( filter, &tmp ); 
	cvGetSubRect(dft_B, &tmp, cvRect( filter->cols, 0, dft_B->cols-filter->cols, filter->rows ));
	cvZero( &tmp );
	
	// no need to pad bottom part of dft_B with zeros because of 
	// use nonzero_rows parameter in cvDFT() call below 
	// 
	cvDFT( dft_B, dft_B, CV_DXT_FORWARD, filter->rows );
	
	// or CV_DXT_MUL_CONJ to get correlation rather than convolution 
	//
	cvMulSpectrums( dft_A, dft_B, dft_A, 0 );
	
	// calculate only the top part 
	// 
	cvDFT( dft_A, dft_A, CV_DXT_INV_SCALE, dst->rows ); 
	cvGetSubRect( dft_A, &tmp, cvRect(0,0,dst->cols,dst->rows) );
	cvCopy( &tmp, dst );
	cvReleaseMat( &dft_A );
	cvReleaseMat( &dft_B );
}

ドライバプログラムも含めたソースファイルをここに置いておきます。参考にしてみてください。

高速ガウシアンフィルタプログラム
 
 

OpenCVでQRコード検出器を書く

木曜日, 1月 20th, 2011
このエントリーを含むはてなブックマークはてなブックマーク - OpenCVでQRコード検出器を書く

qrcodedetector0
 
 
OpenCVを使ってQRコードを検出するプログラムを作成したので、その手順をまとめてみた。このプログラムはlibdecodeqrを参考にさせていただきました。(本家のサイトは閉鎖してしまっているようです)

作成したプログラム+ドライバプログラムを置いておきますので参考にしてください。このプログラムを用いて下記にQRコード検出アルゴリズムを紹介していきます。
 
QRコード検出器プログラム
 
 
 

1. 画像中から正方形の部分を検出する

qrcodedetector1
 
まずは、ファインダパタン(3隅にある目玉画像)を検出するために、画像中から輪郭を抽出し、抽出された輪郭から正方形の輪郭のみを保存します。
 
具体的には、まずcvFindContoursメソッドを用いて輪郭情報をcont変数に格納します。次に格納された輪郭情報のうち正方形のもののみを検出するため、面積と縦横比をチェックし、そのチェックに通ったもののみcandidates変数に保存します。
 
 

cvFindContours(tmp,
				   _stor_tmp,&cont,sizeof(CvContour),
				   CV_RETR_LIST,CV_CHAIN_APPROX_NONE,cvPoint(0,0));
	
	// for marker candidates list
	CvSeq *candidates=cvCreateSeq(CV_SEQ_ELTYPE_GENERIC,
								  sizeof(CvSeq),sizeof(ImageReaderCandidate),
								  _stor_tmp);
	//
	// check each block
	//
	CvSeq *cont_head = cont;
	for(; cont; cont = cont->h_next ){
		CvRect feret = cvBoundingRect(cont);
		double area = fabs(cvContourArea(cont));
		double area_ratio = area/(double)(feret.width*feret.height);
		double feret_ratio = ((feret.width<feret.height)?
							(double)feret.width/(double)feret.height:
							(double)feret.height/(double)feret.width);
		
		//
		// search square(正方形を探索)
		//
		if(area>=MIN_AREA && area_ratio>=MIN_AREA_RATIO && feret_ratio>=MIN_FERET_RATIO){
			ImageReaderCandidate c;
			c.feret.x=feret.x;
			c.feret.y=feret.y;
			c.feret.width=feret.width;
			c.feret.height=feret.height;
			c.contour=cont;
			cvSeqPush(candidates, &c);
		}
		else{
			cvClearSeq(cont);
		}
	}

 
 
 

2. ファインダパタンの検出

qrcodedetector2
 
Step1で検出された正方形の中から、ファインダパタンを見つけるため、正方形の中にもう一つ正方形が含まれている箇所を検出し、seq_finder_patternに追加します。
 
ファインダパタンの位置を示す型としてCvBox2D型を使用しています。このCvBox2D型はCvRect型と同様、長方形を表す型ですが、CvBox2D型では回転まで考慮できるため傾いた長方形にも対応できるのがCvRect型との違いです。
 
 

	for(i = 0; i < candidates->total; i++){
		ImageReaderCandidate *cand1= (ImageReaderCandidate *)cvGetSeqElem(candidates,i);
		
		int inner_contour=0;
		int j;
		for(j = 0; j < candidates->total; j++){
			if(i == j) continue;
			
			ImageReaderCandidate *cand2 = (ImageReaderCandidate *)cvGetSeqElem(candidates,j);
			CvRect max_rect=cvMaxRect(&(cand1->feret),&(cand2->feret));
			if(cand1->feret.x==max_rect.x&&
			   cand1->feret.y==max_rect.y&&
			   cand1->feret.width==max_rect.width&&
			   cand1->feret.height==max_rect.height)
				inner_contour++;
		}
		
		//
		// There were 2 squires (white and black) inside a squire,
		// the most outer squire assumed as position marker.
		//
		if(inner_contour==2){
			CvBox2D box = cvMinAreaRect2(cand1->contour);
			cvSeqPush(seq_finder_pattern, &box);			
		}
	}

 
 
 

3. QRコードの輪郭を抽出する

 qrcodedetector3
 
検出された3つのファインダパタンを用いてQRコードの輪郭を抽出します。ここではQRコードの輪郭を、ファインダパタンをすべて含むような矩形として定義しています。
 
具体的には、cvBoxPoints関数を用いて、ファインダパタンを示すCvBox2D型の変数から4つの頂点座標を取得し、合計12個の頂点座標を含むような矩形をcvMinAreaRect2関数で作成します。最後に再びcvBoxPoints関数を使って頂点座標を検出することでQRコードの4つの頂点座標を取得しています。
 
 

	int c = seq_finder_pattern->total, i;
	for(i = 0; i < c; i++){
		
		box = *(CvBox2D *)cvGetSeqElem(seq_finder_pattern,i);
		_finderpattern_boxes&#91;i&#93; = box;

		cvBoxPoints(box, pt_32f);
		for(int j = 0; j < 4; j++){
			CvPoint p = cvPointFrom32f(pt_32f&#91;j&#93;);
			cvSeqPush(markers_vertex,&p);
		}
	}
	
	//
	// create Minimal-area bounding rectangle which condist
	// every position makers
	// 点列を包含する最小矩形をboxに格納
	//
	box = cvMinAreaRect2(markers_vertex);
	cvRelease((void **)&markers_vertex);
	
	//
	// create code area mask
	// pointsに四隅の座標がはいる
	//
	cvBoxPoints(box, pt_32f);
	CvPoint *points=new CvPoint&#91;4&#93;;
	for(i = 0; i < 4; i++){
		//squarePoints&#91;i&#93;=cvPointFrom32f(pt_32f&#91;i&#93;);
		points&#91;i&#93; = cvPointFrom32f(pt_32f&#91;i&#93;);	
	}

&#91;/cpp&#93;
 
 
 
<span style="font-size:large;color:RoyalBlue"><strong>
4. QRコード部分のみをトリミングする
</strong></span>
<a href="http://iphone.moo.jp/app/wp-content/uploads/g4.jpg"><img src="http://iphone.moo.jp/app/wp-content/uploads/g4.jpg" alt="qrcodedetector4" title="qrcodedetector4" width="150" height="150" class="alignnone size-full wp-image-919" /></a>
 
最後に、検出されたQRコードの4頂点から正方形への射影変換を行います。OpenCVを使った射影変換のコードはここを参考にさせていただきました。
 
<a href="http://chihara.naist.jp/opencv/?%BC%CD%B1%C6%CA%D1%B4%B9">射影変換 | OpenCV@Chihara-Lab.</a>
 
[cpp]
	for(int i = 0; i < 4; ++i){
		a&#91;j++&#93; = p&#91;i&#93;.x;
		a&#91;j++&#93; = p&#91;i&#93;.y;		
	}
    src_point = cvMat( 4, 2, CV_64FC1, a );
	
    CvMat    dst_point;
    double    b&#91;&#93; = {
        0, 0,
        0, dst->height - 1,
        dst->width - 1, dst->height - 1,
        dst->width - 1, 0
    };
    dst_point = cvMat( 4, 2, CV_64FC1, b );
	
    CvMat    *h = cvCreateMat( 3, 3, CV_64FC1 );	
    cvFindHomography( &src_point, &dst_point, h );
    cvWarpPerspective( src, dst, h );

 
 
 

5. まとめ

OpenCVでQRコードの検出器を実装してみました。検出の流れとしては以下のようになります。

  • 画像中かの輪郭情報を取得し
  • 得られた輪郭情報から正方形を探索
  • 正方形が2重になっているものがファインダパタン
  • ファインダパタンから4頂点を決定
  • その頂点座標を用いて射影変換

 
 
その他の検出方法
 
QRコードを機械学習から検出しちゃおうという面白いサイトがありましたので、ここに紹介しておきます。Haar cascadeも公開されているので一度試してみてはいかがでしょうか?

QRコード検出 | CanI’s Diary

cvMatchTemplateの実装を解読してみた

木曜日, 12月 30th, 2010
このエントリーを含むはてなブックマークはてなブックマーク - cvMatchTemplateの実装を解読してみた

OpenCVでテンプレートマッチングを行う場合、cvMatchTemplateメソッドを使用するのですが、一体どういうアルゴリズムでこの関数が実装されているのか気になったので、ソースを解読してみた。


 
案の定、cvMatchTemplateの実装に関するサイトがあったので、先にそちらを紹介します。

OpenCVのcvMatchTemplate実装について調べてみた

こちらのサイトでは、cvMatchTemplateの頭から、エラー処理までの部分を非常に詳しく説明されていました。
 
cvMatchTemplate調査メモ

また、こちらのサイトではテンプレートマッチングのコアアルゴリズムであるDFTの計算について触れられていました。

これらの情報を元に、cvMatchTemplate関数では何が行われているのかを解読してみました。解読に当たって使用したオリジナルのソースコードと、CV_TM_CCOEFFに限定して、ソースコードをバッサバッサ削ったバージョンのファイルを下に置いておきます。以下ではCV_TM_CCOEFFアルゴリズムに限定して説明を進めたいと思います。

オリジナルソースコード
CV_TM_CCOEFF用ソースコード

 

まずは、cvMatchTemplateのコアとなる部分を掲載します。分かりやすいように、数カ所にコメントを書き加えています
 
cvMatchTemplate関数

	// 元画像とテンプレ画像の相関を求める
    CV_CALL( icvCrossCorr( img, templ, result, cvPoint(0,0) ));

    CV_CALL( sum = cvCreateMat( img->rows + 1, img->cols + 1,
							   CV_MAKETYPE( CV_64F, 1 )));

	// 相関係数を求めるための準備
    CV_CALL( cvIntegral( img, sum, 0, 0 ));
    CV_CALL( templ_mean = cvAvg( templ ));
	p0 = (double*)sum->data.ptr;
    p1 = p0 + templ->cols;
    p2 = (double*)(sum->data.ptr + templ->rows*sum->step);
    p3 = p2 + templ->cols;
	
    sum_step = sum ? sum->step / sizeof(double) : 0;
    sqsum_step = sqsum ? sqsum->step / sizeof(double) : 0;

    for( i = 0; i < result->rows; i++ )
    {
        float* rrow = (float*)(result->data.ptr + i*result->step);
        idx = i * sum_step;
 	
        for( j = 0; j < result->cols; j++, idx++)
        {
			// rrow[j]に座標(i, j)の相関が入っている
            double num = rrow[j], t;

			// 相関係数を求める
			t = p0[idx] - p1[idx] - p2[idx] + p3[idx];
			num -= t*templ_mean.val[0];
			
            rrow[j] = (float)num;
        }
    }

cvMatchTemplateの本質は、icvCrossCorr関数に集約されており、残りの部分は全てオマケ程度な感じです・・・。

そのicvCrossCorr関数では、元画像とテンプレート画像の相関を計算しています。この関数に引数として元画像(img)とテンプレート画像(templ)を渡せば、結果をresultに詰めて返してくれます。icvCrossCorrの詳しい処理は以下で説明するので、その前に2行目移行の処理を見ていきましょう。

CV_TM_CCOEFFアルゴリズムを使用した場合、相関係数は以下の式で得られます。

cvmatchtemplatee1
ここで

cvmatchtemplatee2

相関値自体はicvCrossCorrで計算するのですが、相関係数を求めるためには、T’とI’のそれぞれ2項目に当たる部分も計算しておかなければいけません。それを行っているのが上記プログラムの2行目以下になります。

T’の2項目はテンプレート画像の明度の平均値なので、cvAvg関数を用いて計算しています。また、I’の2項目は任意座標の明度平均値なので、cvIntegral関数を使って積分画像を作っています。

ここで、積分画像とは(インテグラルイメージとは)下図のように左上の明度から特定の座標までの明度を積分した画像のことをいいます。例えば、2行2列目の積分画像の値は3+4+3+1=11になっています。

この積分画像が計算できると何が嬉しいかというと、任意矩形で囲まれる明度の積分値を定数時間で求めることが出来るようになります。例えば青枠で囲った部分(左図)の明度の和が欲しい場合には、積分画像(右図)から下に書いたような加減算のみで、答えを得ることが出来ます。なぜ?という方はぜひ手計算してみてください!

cvmatchtemplate3

プログラムでは28行目で積分画像の計算を行っています。32行目では、この計算で得られた元画像の平均値とテンプレート画像の平均値、icvCrossCorrで得られた相関値を利用することで相関係数を算出し、結果画像に保存しています。

cvmatchtemplate4

最後に、テンプレートマッチングのコアとなるicvCrossCorr関数の説明をします。さっき書いたように、この関数では元画像とテンプレート画像の相関係数を計算しています。

通常、この演算は元画像とテンプレート画像の畳み込み演算で行うのですが、畳み込み演算では計算量が膨大になるという問題があります。そこでOpenCVの実装では、元画像とテンプレート画像を離散フーリエ変換(Discreate Fourie Transformation, DFT)し、フーリエ空間で積算してから元空間に戻す、という方法をとっています。

このあたりの話は、下記の2冊に詳しく説明されていましたので参考にしてみて下さい。

これなら分かる応用数学教室―最小二乗法からウェーブレットまで
金谷 健一
共立出版
売り上げランキング: 8161

 

今日から使えるフーリエ変換 (今日から使えるシリーズ)
三谷 政昭
講談社
売り上げランキング: 240150

簡単に説明すると、計算量の必要な畳み込み演算をするよりも、(フーリエ変換・逆変換は必要ですが)乗算だけで済む下側のパスをとろうというのが基本アイデアです。

cvtemplatematch5

このアイデア自体は難しい話ではなく、例えば画像にぼかしフィルタをかける場合、画像空間でフィルタをかけると、畳み込み演算が必要になるのに対して、フーリエ変換した画像に対してフィルタをかける場合には、マスク処理(要するにマスクとの乗算)だけで処理が完了するという話と同じ内容です。

さて、この処理を行なっている部分のプログラムを載せておきます。こちらも分かりやすいように、少しコメントを足しています。

icvCrossCorr関数

			// 元画像に対してDFTを実行
			cvDFT( _dft_img, _dft_img, CV_DXT_FORWARD, isz.height );
			cvGetSubRect( dft_templ, dst,
						 cvRect(0,0,dftsize.width,dftsize.height) );
			
			// フーリエ空間にて、元画像とテンプレ画像の畳み込みを行う
			cvMulSpectrums( _dft_img, dst, _dft_img, CV_DXT_MUL_CONJ );

			// 座標空間に戻す
			cvDFT( _dft_img, _dft_img, CV_DXT_INVERSE, csz.height );
			

 
 
cvDFTで元画像とテンプレート画像をそれぞれ離散フーリエ変換し、その結果をcvMulSpectrums関数でかけ合わせています。この関数の引数にCV_DXT_MUL_CONJを指定することで、相関係数を算出しています。最後にその結果を逆DFTすることで画像空間上に再マッピングしています。

 
cvmatchtemplate6 
以上がcvMatchTemplate実装の解読結果になります。もう一度処理の流れをまとめると

  • まず元画像とテンプレート画像をフーリエ変換し、
  • フーリエ空間で両者を乗算したのち、逆フーリエ変換すると
  • 元画像とテンプレート画像の各座標の相関値が得られるので
  • その結果を用いて、相関係数を計算し
  • 相関係数が最大に部分が最も一致度が高い部分になる

    こんな感じになります。