(赤色の位置が照合が行われた位置)
あらかじめ用意していたテンプレート画像を参照画像中から探索するためのテンプレートマッチングの例です。テンプレートマッチングは、テンプレート画素と参照画素の両画素を総当りで比較することとなるため、非常に処理に時間が掛かってしまいます。そこでそのような総当り計算を極力間引くことができるように提案された手法がアクティブ探索法です。
アクティブ探索法は、順次テンプレート画像をずらして参照画像中の位置を探索する際、次回の探索位置における照合が必要かどうかを判断するための上限値を計算し、現在の位置におけるテンプレート画像・参照画像の類似値と次回位置の上限値を比較し、上限値が類似値より低いものであれば次回位置の照合を省くというものです。このアルゴリズムにより、総当り的な探索に比べ10〜1000倍程度に時間が短縮されたと言う報告がされています。
プログラム内では、アクティブ探索法に関しても探索の間引きを考慮できるようになっていますが、間引きをしない状態の総当り的な計算でも上記のような速度が得られるようです。
照合の方法に関しては、RGBのそれぞれの画素を比較する方法、グレースケールに変換してから比較する方法、ヒストグラムを作成し比較する方法（ヒストグラムインタセクション）等があります。アクティブ探索法では、画像の遮蔽やサイズの伸縮、ノイズの影響等も考慮し、一般的にはヒストグラムインタセクションによる照合が行われます。
| 元画像 | テンプレート画像 | テンプレート探索例 | アクティブ探索法：照合間引きの例 (赤色の位置が照合が行われた位置) |
|||
|
|
|
|
実行ファイルのダウンロード： tmpl_match.exe
//----------------------------------------------------------------- // tmpl_match.cpp: // テンプレートマッチング // Last Update: <2004/12/18 22:40:35 A.Murakami> //----------------------------------------------------------------- #include <windows.h> #include <stdio.h> #include <sys/time.h> #include "wingui.h" #include "ipcommon.h" #include "ip_tmatch.h" //----------------------------------------------------------------- LPBYTE iTemp = NULL; UINT lflg = FALSE; UINT t_xsize,t_ysize; struct timeval ts,te; //----------------------------------------------------------------- void toOrg(); void iLoadTemp(); void iTempMatch(); void iHistMatch(); void iActive(); void set_ptime(int opt); double get_ptime(); //----------------------------------------------------------------- // メニューへの追加内容 //----------------------------------------------------------------- MenuInfo MI[] = { {"元画像",toOrg}, {"テンプレート画像読込み",iLoadTemp}, {"テンプレートマッチング",iTempMatch}, {"ヒストグラムインタセクション",iHistMatch}, {"アクティブ探索法" ,iActive}, {NULL,NULL} }; //----------------------------------------------------------------- // 初期化関数 //----------------------------------------------------------------- void IP_init() {} //----------------------------------------------------------------- // 処理時間の計測 //----------------------------------------------------------------- void set_ptime(int opt) { if(opt) gettimeofday(&ts,NULL); else gettimeofday(&te,NULL); } double get_ptime() { return ((te.tv_sec-ts.tv_sec)+(te.tv_usec-ts.tv_usec)/1000000.); } //----------------------------------------------------------------- // 元画像の表示 //----------------------------------------------------------------- void toOrg() { CopyMemory(lpBMP,lpOrgBMP,sizeof(BYTE)*biSize); } //----------------------------------------------------------------- // テンプレート画像の読込み //----------------------------------------------------------------- void iLoadTemp() { if(iTemp!=NULL) GlobalFree(iTemp); //------------------------------------------------------- // テンプレート画像の読込み //------------------------------------------------------- iTemp=Load_template(t_xsize,t_ysize); if(iTemp==NULL) return; lflg = TRUE; } //----------------------------------------------------------------- // テンプレートマッチング //----------------------------------------------------------------- void iTempMatch() { if(lflg==FALSE) return; //------------------------------------------------------- // 元画像の読込み //------------------------------------------------------- toOrg(); //------------------------------------------------------- // マッチングパラメータの設定 //------------------------------------------------------- TCHAR msg[512]; int i,match_n; POINT schp; int tm_type = TM_NORMAL; // マッチングの種類[TM_HIST,...] double find_rate = 0.10; // 一致率 int find_max = 1024; // 検索打ち切り数 int sstep = 4,tstep = 4; // スキップ幅[元画像,テンプレート] // 画像設定 int col_type = COLOR_RGB; // 表色系[COLOR_GRAY,COLOR_R,..] int tm_threshold = 5; // 濃淡値[色]の許容検索幅 double image_mag = 0.50; // 画像サイズの縮小率(<=1) int cbit_n = 4; // 表示ビット数[max 8] // テンプレート設定 CTMatchInfo ctmi(tm_type,t_xsize,t_ysize,find_rate, find_max,sstep,tstep); ctmi.set_matching(tm_threshold); ctmi.set_image(col_type,image_mag,cbit_n); set_ptime(1); match_n = template_match(lpBMP,iTemp,ctmi); set_ptime(0); sprintf(msg,"processing time: %lg[sec]\r\nfound n = %d", get_ptime(),match_n); MessageBox(NULL,msg,0,0); for(i=0;i<match_n;i++){ schp = ctmi.get_matchpos(i); mark_template_area(lpBMP,schp,t_xsize,t_ysize); } } //----------------------------------------------------------------- // ヒストグラムインタセクションによるマッチング[全画素] //----------------------------------------------------------------- void iHistMatch() { if(lflg==FALSE) return; //------------------------------------------------------- // 元画像の読込み //------------------------------------------------------- toOrg(); //------------------------------------------------------- // マッチングパラメータの設定 //------------------------------------------------------- TCHAR msg[512]; int i,match_n; POINT schp; int tm_type = TM_HIST; // マッチングの種類[TM_HIST,...] double find_rate = 0.50; // 一致率 int find_max = 1024; // 検索打ち切り数 int sstep = 4, tstep = 4; // スキップ幅[元画像,テンプレート] // 画像設定 int col_type = COLOR_RGB; // 表色系[COLOR_GRAY,COLOR_R,..] double image_mag = 0.50; // 画像サイズの縮小率(<=1) int cbit_n = 4; // 表示ビット数[max 8] // テンプレート設定 CTMatchInfo ctmi(tm_type,t_xsize,t_ysize,find_rate,find_max, sstep,tstep); ctmi.set_image(col_type,image_mag,cbit_n); set_ptime(1); match_n = template_match(lpBMP,iTemp,ctmi); set_ptime(0); sprintf(msg,"processing time: %lg[sec]\r\nfound n = %d", get_ptime(),match_n); MessageBox(NULL,msg,0,0); for(i=0;i<match_n;i++){ schp = ctmi.get_matchpos(i); mark_template_area(lpBMP,schp,t_xsize,t_ysize); } } //----------------------------------------------------------------- // アクティブ探索法 //----------------------------------------------------------------- void iActive() { if(lflg==FALSE) return; //------------------------------------------------------- // 元画像の読込み //------------------------------------------------------- toOrg(); //------------------------------------------------------- // テンプレートマッチング //------------------------------------------------------- TCHAR msg[512]; int i,match_n; POINT schp; int tm_type = TM_ACTIVE; // マッチングの種類[TM_HIST,...] double find_rate = 0.80; // 一致率 int find_max = 1024; // 検索打ち切り数 int sstep = 1, tstep = 1; // スキップ幅[元画像,テンプレート] // 画像設定 double image_mag = 0.50; // 画像サイズの縮小率(<=1) int col_type = COLOR_RGB; // 表色系[COLOR_GRAY,COLOR_R,..] int cbit_n = 4; // 表示ビット数[max 8] // アクティブ探索 double upl_mag = 0.75; // アクティブ探索上限値の倍率[max 1.0] // テンプレート設定 CTMatchInfo ctmi(tm_type,t_xsize,t_ysize,find_rate,find_max, sstep,tstep); ctmi.set_image(col_type,image_mag,cbit_n); ctmi.set_active(upl_mag); set_ptime(1); match_n = template_match(lpBMP,iTemp,ctmi); set_ptime(0); sprintf(msg,"processing time: %lg[sec]\r\nfound n = %d", get_ptime(),match_n); MessageBox(NULL,msg,0,0); for(i=0;i<match_n;i++){ schp = ctmi.get_matchpos(i); mark_template_area(lpBMP,schp,t_xsize,t_ysize); } } |