Archive for the ‘研究’ Category

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

画像修復プログラムを作った

金曜日, 12月 17th, 2010
このエントリーを含むはてなブックマークはてなブックマーク - 画像修復プログラムを作った

OpenCVを使って、欠損領域を含む画像に対して画像修復を行うプログラムを作成しました。参考にした論文はこちらです。かなりGreedyで時間のかかるアルゴリズムですが、結果画像のクオリティは高いです。

Y. Wexler, E. Shechtman and M. Irani, Space-Time Video Completion. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Washington, June 2004.

入力画像がこちら。
赤色正方形の部分を欠損領域として指定しています。
inpainting1

修復結果がこちら
inpainting

かなりのクオリティで修復できているのが分かりますね。アルゴリズムとしては、先日紹介した4種類のうち4番目の「テクスチャの全体最適化による画像修復」に相当します。

このアルゴリズムの基本的なアイデアは、欠損領域と似たようなテクスチャを持つ領域を画像中から探して、欠損領域を1pxずつ埋めて行こうというものです。では具体的にどのような処理を行っているのかを説明します。

[Step 1]
まずは、欠損領域を含む小さな領域をテンプレート画像として指定します。具体的には、まず左上の欠損領域を含むようなテンプレート画像を作成します。
inapinting3

[Step 2]
Step1で作成したテンプレートを元に、テンプレートマッチングを行います。今回はSSD(Sum of Suquared Difference)を使用しました。テンプレートマッチングの際、欠損領域付近はマッチング対象としません。
inpainting4

[Step 3]
次に、マッチした領域の中央のピクセル値を使って、欠損領域左上のピクセルを修復します。コレでようやく欠損領域1pxぶんが修復できたことになります。

[Step 4]
あとは、テンプレートの位置を1pxぶん右に移動させ、欠損領域が全て修復されるまでstep1からstep4を繰り返します。論文では、このstep1から4までをオールオーバで許容解までループしているようですが、時間とクオリティのトレードオフで、今回はone pathで終了させています。
inpainting6

さて、最後に主要部分のプログラムを掲載しておきます。Step2で欠損領域を除く領域からのテンプレートマッチングが必要なのですが、任意形状のROI(region of interest)を指定する手段がOpenCVにはありませんので、ROIを指定できるテンプレートマッチング関数ROItemplateMatchは自作しました。下にサンプルプロジェクトを置いておきますので、そちらも合わせて参考にしてみてください。


iint main(int argc, char* argv[])
{
cvNamedWindow (“src”, CV_WINDOW_AUTOSIZE);
cvNamedWindow (“result”, CV_WINDOW_AUTOSIZE);

IplImage* src = cvLoadImage(“small.jpg”, CV_LOAD_IMAGE_ANYCOLOR);
IplImage* mask = cvCreateImage(cvGetSize(src), IPL_DEPTH_8U, 1);
IplImage* maskForInpaint = cvCreateImage(cvGetSize(src), IPL_DEPTH_8U, 1);

cvSet(mask, cvScalarAll(255));
cvZero(maskForInpaint);

// 欠損領域およびROIマスクの作成
CvPoint pos = cvPoint(330, 120);
CvSize sz = cvSize(25, 25);
cvRectangle(src, pos, cvPoint(pos.x+sz.width, pos.y+sz.height), CV_RGB(255,0,0), CV_FILLED, 8, 0);
cvRectangle(maskForInpaint, cvPoint(pos.x, pos.y), cvPoint(pos.x+sz.width, pos.y+sz.height), CV_RGB(255,255,255), CV_FILLED, 8, 0);
cvRectangle(mask, cvPoint(pos.x-TMPSZ, pos.y-TMPSZ), cvPoint(pos.x+sz.width+TMPSZ, pos.y+sz.height+TMPSZ), CV_RGB(0,0,0), CV_FILLED, 8, 0);

cvShowImage (“src”, src);

// 初期値の決定
cvInpaint(src, maskForInpaint, src, 10.0, CV_INPAINT_NS);
cvReleaseImage(&maskForInpaint);

// 画像修復本体
IplImage* dst = cvCloneImage(src);
int tmpr[TMPSZ*TMPSZ];
int tmpg[TMPSZ*TMPSZ];
int tmpb[TMPSZ*TMPSZ];

// 欠損領域内探索
for(int i = 0; i < 7; ++i){ for(int x = pos.x; x <= pos.x + sz.width; x++){ for(int y = pos.y; y <= pos.y + sz.height; y++){ // テンプレート配列を作成する int c = 0; for(int tx = x; tx < x + TMPSZ; ++tx){ for(int ty = y; ty < y + TMPSZ; ++ty){ tmpr[c] = PIXVALR(src, tx, ty); tmpg[c] = PIXVALG(src, tx, ty); tmpb[c] = PIXVALB(src, tx, ty); c++; } } CvPoint rpos = ROItemplateMatch(src, mask, tmpr, tmpg, tmpb); PIXVALR(dst, x, y) = PIXVALR(src, rpos.x, rpos.y); PIXVALG(dst, x, y) = PIXVALG(src, rpos.x, rpos.y); PIXVALB(dst, x, y) = PIXVALB(src, rpos.x, rpos.y); } } cvCopy(dst, src, NULL); } cvShowImage ("result", dst); cvWaitKey (0); return 0; } [/cpp] 実行時間はMacbook Pro, Core2Duo, 4GB上で、コンパイラ最適化した状態で、大体5秒程度です。ただ、テンプレートマッチングをサボっているので、まともにやると2分程度かかります。さてさて、やはりこのアルゴリズムじゃぁiPhoneでは動作しませんねぇ。どうしたものか・・・(笑) 最後に、サンプルプロジェクトをココにいおいておきます。 画像修復サンプルプログラム

TouchRetouchのアルゴリズム

水曜日, 12月 15th, 2010
このエントリーを含むはてなブックマークはてなブックマーク - TouchRetouchのアルゴリズム

画像修復(inpainting)とは画像中の欠損領域を、何らかの方法で修復することを指します。iPhoneアプリとしてはTouchRetouchが有名ですね。

touchretouch

基本的に、画像修復はマルチコアのCPUを使っても2・3分は余裕でかかる処理なのに、TouchRetouchでは、iPhoneという非力なプラットフォームにもかかわらず10秒程度で処理が終了しています。このTouchRetouchがどのようなアルゴリズムで修復を行っているのかが気になったので、少し調べてみました。

画像修復とひとくちにいっても、

1. 輝度値の連続性を考慮した画像修復
2 .特徴空間での補間による画像修復
3. テクスチャの逐次合成による画像修復
4. テクスチャの全体最適化による画像修復

といったものがあるようです。

ここらへんはこちらの論文を参考にさせていただきました。

輝度値の変化と画像の局所性を考慮したパターン類似度に基づくエネルギー最小化による画像修復”,奈良先端科学技術大学院大学 修士論文 NAIST-IS-MT0551036 , March 2007. e

さて、ここでこのTouchRetouchのアプリはどのアルゴリズムを使用しているのでしょうか?実際に処理を行い検証してみました。入力画像と出力画像を下図に示します。

retouch1 retouch3

この処理がiPhone上で10秒程度で終わることから考えても4番のアルゴリズムではなさそうです。また、背景の柵のテクスチャが綺麗に再現されていることから1番のアルゴリズムでもなさそうです。となると、2番目か3番目のアルゴリズム(もしくは未だ見ぬアルゴリズム笑)だと思うのですが・・

ここで、TouchRetouchの本家のHPにヒントとなる一文が載っていたので引用。オリジナルはこちら

3. How does TouchRetouch work?

TouchRetouch uses background recovery algorithm based on image inpainting and texture synthesis. Marked image part is considered to be unknown and is being recovered on the base of known image parts.

texture synthesisと書いてあることからも分かるように、やはり3番の「テクスチャの逐次合成による画像修復」が用いられているようです。このアルゴリズムを提案した代表的な論文がこちら。

P. Harrison: “A NON-HIERARCHICAL PROCEDURE FOR RE-SYNTHESIS OF COMPLEX TEXTURES” Proc. Int. Conf. in Central Europe Computer Graphics, Visualization and Computer Vision, pp. 190-197, 2001.

この論文、メインは小さなテクスチャから如何にして大きなテクスチャを生成するかがのようですが、3.1章の終わりに少しだけ画像修復に付いても言及されていますね。まずは、このアルゴリズムから理解していくところから始めたいと思います。

画像のベクトル化

金曜日, 11月 26th, 2010
このエントリーを含むはてなブックマークはてなブックマーク - 画像のベクトル化

ビットマップ画像をベクトル画像に変換するアルゴリズムをいろいろ調べていました。画像をベクトル化するということは、すべてのエッジを曲線の方程式で近似するということです。その変換方法としては、Potraceというアルゴリズムが有名なようですね。

論文は、ここから入手できます。

Potrace: a polygon-based tracing algorithm. Peter Selinger. September 20, 2003

基本的には、

1. 輪郭座標の抽出
2. ポリゴン化
3. ベジェ曲線で近似

という流れのようです。ぼちぼち、iPhoneに実装していきたいです。ただ、このアルゴリズム、そのままだと重すぎて動かない気がする(笑)まぁ、行き詰ってから考えよっと。

フーリエ変換の本質

水曜日, 11月 24th, 2010
このエントリーを含むはてなブックマークはてなブックマーク - フーリエ変換の本質

工学系の大学生なら、2回生ぐらいで習うフーリエ変換。フーリエ級数やらフーリエ展開やらの式だけ覚えさせられて、フーリエ変換の意味を理解してない人が多いようです。

そこで、フーリエ変換とは何か?をサクっと説明してみましょう。

fourier1

全ての信号は、上図のようにsin波の足しあわせで表現することが出来ます。

具体的には、周波数が1のsinxと周波数が2のsin2xと周波数が3のsin3xと・・・周波数がnのsinnxを足し合わせることで、あらゆる信号を表現することが出来るのです。

しかし、ただ単にy=sinx+sin2x+sin3x+・・・としたのでは1種類の信号しか表現できません。そこで、各周波数の振幅を変化させることで、あらゆる信号を表現するのです。

上記の信号の場合、y=4*sinx+0.5*sin2x+2*sin3x+sin4xと表現できます。

fourier2

さて、先程の図を用いて、周波数を横軸に、振幅の大きさ(パワー値)を縦軸にとってグラフを書きなおしてみます。周波数が1の波(sinx)の振幅は4なので、f=1ではパワー値が4になります。同様に、f=2でP=0.5、f=3でP=2、f=4でP=1をとると上図の右のグラフのようになります。

これこそが、フーリエ変換の結果なのです。

fourier3

さて、ではこの結果は何を意味しているのでしょうか?この結果は、左図の信号に周波数1の波が大きさ4で含まれていること、周波数2の波が大きさ0.5で含まれていること、周波数3の波が・・・ということを意味しています。

要するに、フーリエ変換を行えば、「信号に含まれる周波数の成分比」を得ることが出来ます。本質はこれだけです。
 
 

参考図書

 
 
「フーリエの冒険」
フーリエ変換についてゼロから勉強するなら、まずは本書がとってもお薦めです。この本では難しい数学や数式を使うこと無く、かみ砕いてフーリエ変換の本質を説明してくれています。微積や三角関数の説明も丁寧にしてくれていて、作者の「フーリエ変換の本質を伝えたい」という気持ちが伝わってくるような一冊です。

フーリエの冒険
フーリエの冒険
posted with amazlet at 11.06.14
ヒッポファミリークラブ
売り上げランキング: 18159

 
 
「今日から使えるフーリエ変換」
上記の参考書と同様、フーリエ変換の本質についてサックリ明解に説明してくれている参考書です。もちろん、フーリエ変換の本質だけでなく、数学的な話から実用的な話までカバーしているので、工学系にいる人には必須の一冊です。入門書と中級書をつないでくれる非常に良書だと思います。
 

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

 
「これなら分かる応用数学教室」
この本は絶対に「買い」です!理由不要です(笑)本書では最小二乗からフーリエ変換、顔認識、ウェーブレットまでを説明しています。この何も関係なさそうなカテゴリが本書を読めば一本の糸で繋がります。とにかく、知的感動を味わいたいならぜひ!
 

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

 
 
あと・・・
僕の作ったアプリもよろしく(笑)
iPhoneで一眼レフカメラで撮影したような画像を作れます!