Visual Studio (VC++) 応用編 （その5）
− 画像の高速テンプレートマッチングによる速度計測手法 −
信州大学工学部 井澤裕司
(H18.3.8)
課 題 5
|
前章の「
応用編A（その4）
」では，Visual C++を用いて，「
画像のテンプレートマッチングによる類似領域の抽出
」を行うプログラムを作成しました． 「 静止した背景 」の手前で「 剛体の対象物が移動 」するとき，「 一定の条件 」が整えば，その対象物の一部をテンプレートに設定することにより， 「 対象物の動き 」を計測することが可能です． また，「 静止した対象物 」をUSBカメラを動かしながら撮影する場合は， 「 カメラの動き 」を計測することができます． これらは，2枚の画像を用いて，特徴点の移動量を計測するものであり， 「 オプティカルフロー 」と呼ばれることがあります． 本章では，前章のプログラムをベースに改良を加え，「 静止した対象物 」を撮影したとき，「 カメラの動き 」を連続的に計測するプログラムを作成します． この課題では，以下のような問題点があります． (1) 1回のテンプレートマッチング処理に，時間を要すること． （ノート型パソコンで，4秒程度）これらについては，以下の手法により対応します． (1) 画像のピラミッド構造化による「 階層的マッチング法 」と，「 残差逐次検定法 」により，テンプレートマッチングの高速化を実現する．最後に，作成したプログラムを評価し，残された問題点について検討します． |
|
１．はじめに
前章の「 応用編A（その4） 」では，Visual C++を用いて，「 画像のテンプレートマッチングによる類似領域の抽出 」を行うプログラムを作成しました．
「 静止した背景 」の手前で「 剛体の対象物が移動 」するとき，「 一定の条件 」が整えば，その対象物の一部をテンプレートに設定することにより， 「 対象物の動き 」を計測することが可能です．
また，「 静止した対象物 」をUSBカメラを動かしながら撮影する場合は， 「 カメラの動き 」を計測することができます．
これらは，2枚の画像を用いて，特徴点の移動量を計測するものであり， 「 オプティカルフロー 」と呼ばれることがあります．
本章では，前章のプログラムをベースに改良を加え，「 静止した対象物 」を撮影したときの「 カメラの動き 」を連続的に計測するプログラムを作成します．
この課題では，以下のような問題点があります．
(1) 1回のテンプレートマッチング処理に，時間を要すること． （ノート型パソコンで，4秒程度）これらについては，以下の手法により対応します．
(2) 画像の中心にテンプレートとして設定した領域が単調な場合， 計測精度が低下すること．
(1) 画像のピラミッド構造化による「 階層的マッチング法 」と，「 残差逐次検定法 」により，テンプレートマッチングの高速化を実現する．最後に，作成したプログラムを評価し，残された問題点について検討します．
(2) 画面の中央付近から，複雑な画像となる領域を探索し， これをテンプレートに設定する．
それでは，具体的な手法について説明しましょう．
前章では，類似領域を抽出する手法として「 テンプレートマッチング 」を用いました．
この手法の原理は単純ですが，計測する画像やテンプレートの画素数が大きくなると，演算量もそれに比例して増大します．
テンプレートマッチングを高速化するためには，実質的な演算量を低減する必要があります．
例えば，「 計測する画像 」の画素数を「 320×240 」から，縦横半分の「 160×120 」にすると，演算量は「 1/4 」に低減されます．
同様に「 テンプレート画像 」の画素数を，「 32×32 」 から「 16×16 」にした場合も，演算量は「 1/4 」になります．
「 計測する画像 」と「 テンプレート画像 」の画素数を同時に「 1/4 」 にすれば，全体の演算量は「 1/16 」となり，1桁以上低減できます．
そこで，下の図に示すような「 ピラミッド構造化 」により，画像を「 階層的に表現 」することを考えます．
すなわち，「 テンプレート画像 」に似ている画像を，「 低解像度 」の画像を用いて探索し，その「 最適解 」を求めます．
この最適解の精度は低いので，次に「 高解像度 」の画像を用いて，粗い最適解の周辺を「 再探索 」して，本来の最適解を求めます．
「 再探索 」は部分的に行えばよいので，実質的な演算量を大幅に低減することが可能です．
なお，「 ピラミッド構造 」の解像度は通常，「 1/2 」や「 1/4 」のような「 ２のべき乗 」に設定します．
なお，画像の縮小処理には，一般に「 近傍の（2×2）画素の平均値 」が用いられます．
「 ピラミッド構造化 」の階層数を増やすほど演算量は減りますが，低解像度での最適値の精度が低下し，プログラムも複雑になるので，この課題では「 1階層 」とします．
すなわち，「 計測する画像 」と「 テンプレート画像 」の画素数を，それぞれ縦横半分の「 160×120 」と「 16×16 」に間引いた縮小画像を用います．
これにより，1桁近い演算量の低減が実現されます．
ここでは，「 テンプレートマッチング 」の実質的な演算量を減らす手法である「 残差逐次検定法 」について説明します．
難しそうな名前がついていますが，この手法自体は極めて単純な考えに基づいています．
「 テンプレート画像 」に最も類似した「 計測画像のエリア 」を求める計算の途中で，「 類似度が低い 」と判断された段階で計算を中断し，「 次のエリア 」に進むというものです．
たとえば「 相違度 」を用いて計算する場合，「 その最小値 」と「 場所（エリア） 」が重要なのであって，「 相違度の分布 」を求める必要はありません．
相違度の値が「 それまでの最小値 」を超えたときは，それ以上の計算を中止し，「 次のエリアの探索 」に進むというのは自然な流れです．
第4章のまとめでも述べたように，対象物や背景に特徴がなく，「 平坦な画像 」 や「 縞模様 」等の場合は，どのように高度で複雑な計算を繰り返しても，その移動量を求めることは本質的にできません．
すなわち，「 テンプレート画像 」は，画像の他のエリアには決して現れることのない「 ユニークで複雑なパターン 」である必要があります．
より正確に言うならば，「 テンプレート画像 」の「 自己相関関数 」は，「 ラプラス分布 」のような単位インパルスに近い形状になることが要求されます．
第4章では，「 テンプレート画像 」を「 リファレンス画像 」の中心に設定していました．
しかし，その中心部は上で述べた「 ユニークで複雑なパターン 」となる保証はありません．
そこで，「 画像の中心周辺 」のエリアから，「 ユニークで複雑なテンプレート画像 」を探索し，設定することを考えます．
「 画像の中心周辺 」とする理由は，カメラの移動を考慮しているためです．
境界付近に設定すると画像の外側に，はみ出てしまう確率が高くなります．
次に，「 ユニークで複雑なパターン 」の決定方法について説明します．
「 テンプレート画像 」の「 自己相関関数 」から決定するのが理想ですが，計算が複雑になるため，この課題では「 画像の周波数成分 」を利用します．
はじめに，画像信号を2次元の周波数成分に変換します．
単純で平坦な画像は，「 低域成分 」に電力が集中し，「 中高域成分の絶対値総和 」は小さな値となります．
一方，低域以外の成分，すなわち「 中高域成分の絶対値総和 」が大きな値となるとき，「 複雑な画像 」となります．
そこで，「 中高域成分の絶対値総和 」が最大値となる「 テンプレート画像 」を探索するのです．
画像を2次元の周波数成分に変換する手法には，一般に「 離散フーリエ変換 」が用いられますが，「 複素数の加算と乗算 」が必要となります．
そこで，今回は「 JPEG 」などに用いられ，「 実数の演算 」で実現できる「 離散コサイン変換（DCT） 」を用いることにします．
この「 離散コサイン変換 」の詳細について，このコンテンツの中で説明することはできません．
筆者が担当している大学院の講義「 情報システム特論第1 」の補助教材としてWEB上に用意したコンテンツ「 ディジタル信号処理（応用編） 」等を参照して下さい．
http://laputa.cs.shinshu-u.ac.jp/~yizawa/InfSys1/index.htm
以下，簡単に2次元の「 離散コサイン変換 」について説明します．
縮小した「 テンプレート 」は「 16×16画素 」となり，これを「 離散コサイン変換 」すると，同数の変換係数が得られます．
画像信号を「 16×16 」の「 行列G 」，変換係数を「 行列C 」を用いて表すとき，「 離散コサイン変換 」は，次のような行列の積の形で表現されます．
なお，「 tT 」は，Tの行と列を入れ替えた「 転置行列 」です．
ここで，「 行列T 」は「 離散コサイン変換 」に対応し，その要素は次のようになります．
なお，「 n = 16 」であり，「 i, j = 0, 1, ‥ ,15 」とします．
次に，下の図を用いて「 離散コサイン変換 」のイメージについて補足しましょう．
この変換は，任意の画像信号を，同数の変換係数に対応する「 画像成分の重ね合わせ」 により表現していることになります．
この考えは，「 フーリエ級数展開 」，すなわち，「 任意の周期関数 」は，その整数倍の周波数をもつ「 サイン（sin） 」と「 コサイン（cos） 」の「 重ね合わせ 」により表現できるという原理に基づいています．
下の図の「 16×16 」の小さな画像は，各周波数成分に対応する画像（基底）であり，変換係数の値は，その「 成分の大きさ 」を表しています．
左上が「 水平・垂直の直流成分 」，すなわち，画像の「 平均値 」に対応し，右に行くほど「 水平方向の周波数 」が高くなります．
同様に，下になるほど「 垂直方向の周波数 」が高くなります．
「 変換係数 」の値が負の場合は，対応する成分の「 明るい部分 」と「 暗い部分 」が反転していることを示しています．
すなわち，「 離散コサイン変換 」の「 変換係数 」の「 右 」もしくは「 下 」の領域は，周波数の「 中高域成分 」に対応します．
したがって，この「 中高域成分 」に対応する「 変換係数の絶対値総和 」が最大となるエリアが，「 複雑な画像 」になることが分かります．
２．主な手順
手順のおおまかな流れは，「 第4章 」と変わりません．
変更する部分は，「 ビットマップの追加 」と「 ソースコードの編集部 」です．
先を急ぐ場合は，第4章で作成した「 プロジェクト 」 を「 コピー 」して修正して下さい．
主な 「 手順 」 は，以下の通りです．
(1) リソースの 「 メニュー 」 の追加「 テンプレートマッチング 」 について， 不明な点が残っている場合は， 「 応用編（その4） 」 に戻って復習して下さい．
(2) リソースの 「 ビットマップ 」 の追加
(3) ソースコード 「 Cimg_tmpltmatchView() 」の追加・修正
(4) 「 ライブラリ (vfw32.lib) 」 のリンク設定
(5) 「 ビルド 」 の実行とデバッグ
(6) 完成した 「 プロジェクト 」 の実行
３．メニューの追加
これまでのように，新しいプロジェクトとして 「 img_tmpltmatch 」 を生成し， 以下の表に示すように，「 新規メニュー 」 を追加して下さい．
次に，「 イベントハンドラ 」 を用いて，「 img_tmpltmatchView() 」 の中に関数を追加します
メニュー サブメニュー ID 関数名 初期設定 解像度 ID_INIT OnInit() テンプレート ID_TMPLT_IMAGE OnTmpltImage 画像解析 テンプレートマッチング ID_TMPLT_MATCH OnTmpltMatch
４．ビットマップの追加
次の表のように，新しく 「 ビットマップ 」 を作成します．
ID 位置 (Height) 位置 (Width)
Colors IDB_BITMAP1 240 320 Trueカラー IDB_BITMAP2 120 160 Trueカラー
５．ソースコードの追加・修正
Viewクラス 「 Cimg_tmpltmatchView() 」 の最初に，ヘッダーファイルをインクルードし， 画像表示を行うための 「 変数群 」 を追加します．
‥（略）‥
#include "img_tmpltmatchView.h"
#include "vfw.h" // Video for Windows用ヘッダーファイル
#include "winbase.h" // 〃
#include "math.h" // 数値演算ライブラリ用ヘッダーファイル
#define X_SIZE 320 // 水平画素数
#define Y_SIZE 240 // 垂直画素数
#define TMP_SIZE 32 // テンプレートの画素数 （縦横同数）
#define COLOR 4 // 色（RGB(A) 4 Byte）
#define SRCH_SIZE 32 // 探索範囲（縦横の画素数）
#define PI 3.1415927 // 円周率
#define MAX_TIMES 100 // 移動量の計算回数
#define DIFF_TH_DISP 15000 // 移動量の線種（青，灰）を決める閾値
static unsigned char ref_img[Y_SIZE][X_SIZE][COLOR]; // リファレンス画像 （テンプレート用）
static unsigned char image[Y_SIZE][X_SIZE][COLOR]; // 計測画像
static unsigned char tmp_img[TMP_SIZE][TMP_SIZE]; // テンプレート画像 （モノクローム）
static unsigned char ref_img_s[Y_SIZE / 2][X_SIZE / 2][COLOR];
// 縮小したリファレンス画像 （テンプレート用）
static unsigned char image_s[Y_SIZE / 2][X_SIZE / 2][COLOR];
// 縮小した計測画像
static unsigned char tmp_img_s[TMP_SIZE / 2][TMP_SIZE / 2];
// 縮小したテンプレート画像 （モノクローム）
double dct[TMP_SIZE / 2][TMP_SIZE / 2];
// 離散コサイン変換(DCT)の変換マトリクス
int x_tmplt; // 最適テンプレートの水平座標
int y_tmplt; // 最適テンプレートの垂直座標
int x_tmplt_s; // 縮小画像の最適テンプレート水平座標
int y_tmplt_s; // 縮小画像の最適テンプレート垂直座標
int max_cmplx; // 縮小テンプレート画像の複雑度
CDC m_memDC; // メモリDC
HBITMAP m_hBitmap = NULL; // DIB Section
BITMAPINFOHEADER* m_lpImage = NULL;
static BYTE* m_lpData = NULL; // RGBデータ
HWND m_hCapWnd = NULL;
inｔ size; // データサイズ
BOOL dispFlag = FALSE;
BITMAPINFOHEADER* GetDIBHeader(){ // DIB(Device Independent BMP)のヘッダ
return m_lpImage;
}
BOOL CreateDIBHeader(int size){ // DIB(Device Independent BMP)のヘッダ作成
m_lpImage = (BITMAPINFOHEADER*)malloc(size);
return (m_lpImage != NULL);
}
以下にその編集画面を示します．
5-[b]
デストラクタ「 Cimg_tmpltmatchView::~Cimg_tmpltmatchView() 」 の内部に，後処理用（リソースの解放）のコードを追加します．
Cimg_tmpltmatchView::~Cimg_tmpltmatchView()
{
capDriverDisconnect( m_hCapWnd );
::DestroyWindow( m_hCapWnd );
m_lpData = NULL;
free( m_lpImage );
m_lpImage = NULL;
DeleteDC( m_memDC );
DeleteObject( m_hBitmap );
以下にその編集画面を示します．
5-[c]
デストラクタ「 Cimg_tmpltmatchView::~Cimg_tmpltmatchView() 」 の後に，画像キャプチャ終了時に起動するコードを追加します．
static LRESULT FAR PASCAL CaptureImage(HWND hWnd，LPVIDEOHDR lpVHdr)
{
memcpy(m_lpData， (LPSTR)lpVHdr->lpData， m_lpImage->biSizeImage);
dispFlag = TRUE;
return (LRESULT)TRUE;
}
以下にその編集画面を示します．
5-[d]
「 Cimg_tmpltmatchView::PreCreateWindow(CREATESTRUCT& cs) 」 の内部に，描画準備用のコードを追加します．
BOOL Cimage_fileView::PreCreateWindow(CREARESTRCT& cs)
{
int i;
dispFlag = FALSE;
m_hCapWnd = capCreateCaptureWindowA("img_tmpltmatch",
WS_OVERLAPPEDWINDOW, 0， 0， X_SIZE， Y_SIZE， NULL， NULL);
capDriverConnect(m_hCapWnd， 0);
capSetCallbackOnFrame( m_hCapWnd， CaptureImage);
size = capGetVideoFormatSize(m_hCapWnd);
CreateDIBHeader(size);
m_lpImage = GetDIBHeader();
capGetVideoFormat(m_hCapWnd， m_lpImage， size);
// DIBsectionの確保
m_hBitmap = CreateDIBSection( m_memDC.GetSafeHdc()，
(BITMAPINFO*)m_lpImage，
DIB_RGB_COLORS， (void**)&m_lpData， NULL，0 );
for ( i = 0 ; i < 5; i++){
capGrabFrame( m_hCapWnd ); // 立ち上げ時のキャプチャ命令無応答の一時的対策
}
return CView::PreCreateWindow(cs);
}
以下にその編集画面を示します．
5-[e]
・「 OnDraw() 」 の引数のコメントを除去し，次のように修正します．
void Cimg_tmpltmatchView::OnDraw( CDC* pDC )
・次に，以下に示す描画用のコードを追加します．
CDC pM;
CBitmap pB， *pOld;
CBitmap pB2， *pOld2;
CPen redPen(PS_SOLID, 1, RGB(255, 0, 0)); // 赤色ペンの設定
CPen* pOldPen; // ペンの保存
char buf[30];
// リファレンス画像の表示
pB.LoadBitmap( IDB_BITMAP1 );
pM.CreateCompatibleDC( pDC );
SetBitmapBits( pB， X_SIZE * Y_SIZE * COLOR， &ref_img);
// 配列（ref_img）のセット
pOld = pM.SelectObject ( &pB );
pDC->BitBlt (50， 50， X_SIZE， Y_SIZE， &pM， 0， 0， SRCCOPY);
// 画像の表示 （画面左側）
pDC->TextOutW (150， 20， (CString)"リファレンス画像");
// リファレンス画像のテンプレートを表示
pOldPen = pDC->SelectObject(&redPen); // 赤色を設定 （枠の表示）
pDC->MoveTo(50 + x_tmplt_s * 2 , 50 + y_tmplt_s * 2 );
pDC->LineTo (50 + x_tmplt_s * 2 + TMP_SIZE - 1, 50 + y_tmplt_s * 2 );
pDC->LineTo (50 + x_tmplt_s * 2 + TMP_SIZE - 1, 50 + y_tmplt_s * 2 + TMP_SIZE - 1);
pDC->LineTo (50 + x_tmplt_s * 2 , 50 + y_tmplt_s * 2 + TMP_SIZE - 1);
pDC->LineTo (50 + x_tmplt_s * 2 , 50 + y_tmplt_s * 2 );
pM.SelectObject( pOld );
// 計測する画像の表示
SetBitmapBits(pB, X_SIZE * Y_SIZE * COLOR, &image); // 配列（image）のセット
pOld = pM.SelectObject(&pB);
pDC->BitBlt(400, 50, X_SIZE, Y_SIZE, &pM, 0, 0, SRCCOPY);
// 画像の表示 （画面右側）
pM.SelectObject( pOld );
pDC->TextOutW (510， 20， (CString)"計測画像");
// リファレンス縮小画像の表示
pB2.LoadBitmap( IDB_BITMAP2 );
SetBitmapBits( pB2， X_SIZE * Y_SIZE * COLOR / 4， &ref_img_s);
// 配列（ref_img_s）のセット
pOld2 = pM.SelectObject ( &pB2 );
pDC->BitBlt (50， 320， X_SIZE / 2， Y_SIZE / 2， &pM， 0， 0，SRCCOPY);
// 画像の表示 （画面左側）
pM.SelectObject ( pOld2 );
// リファレンス縮小画像のテンプレートを表示
pDC->MoveTo(50 + x_tmplt_s , 320 + y_tmplt_s );
pDC->LineTo (50 + x_tmplt_s + TMP_SIZE / 2 - 1, 320 + y_tmplt_s );
pDC->LineTo (50 + x_tmplt_s + TMP_SIZE / 2 - 1, 320 + y_tmplt_s + TMP_SIZE / 2 - 1);
pDC->LineTo (50 + x_tmplt_s , 320 + y_tmplt_s + TMP_SIZE / 2 - 1);
pDC->LineTo (50 + x_tmplt_s , 320 + y_tmplt_s );
sprintf( buf, "複雑度 = %d", max_cmplx / 10); // 縮小テンプレートの複雑度
pDC->TextOutW( 100, 480, (CString)buf); // ⇒ 表示
以下にその編集画面を示します．
5-[f]
メニューの「解像度」に対応する「 OnInit() 」 の内部に，以下に示す描画用のコードを追加します．
void Cimg_tmpltmatchView::OnInit()
{
capDlgVideoFormat(m_hCapWnd);
size = capGetVideoFormatSize(m_hCapWnd);
CreateDIBHeader(size);
m_lpImage = GetDIBHeader();
capGetVideoFormat(m_hCapWnd， m_lpImage， size);
m_hBitmap = CreateDIBSection( m_memDC.GetSafeHdc()，
(BITMAPINFO*)m_lpImage,
DIB_RGB_COLORS，
(void**)&m_lpData， NULL， 0 );
}
以下にその編集画面を示します．
5-[g]
「 OnTmpltImage() 」と「 OnTmpltMatch() 」 で使用する以下の関数を追加します．
void set_dct( void )
{
int i, j;
for(i = 0; i < TMP_SIZE / 2; i++){
dct[0][i] = 1.0 / sqrt((double)TMP_SIZE / 2.0); // DCT行列の直流成分の設定
}
for(i = 0; i < TMP_SIZE / 2; i++){
for( j = 0; j < TMP_SIZE / 2; j++){
dct[i][j] = sqrt(2.0) * cos(PI * i * (2 * j + 1) / (TMP_SIZE)) / sqrt(TMP_SIZE / 2.0);
// DCT行列の直流を除く成分の設定
}
}
}
int iabs( int a)
{
if ( a >= 0 ) return a; // 正かゼロならば，その値を返す
else return -a; // 負ならば，反転して絶対値を返す
}
int imax( int a, int b)
{
if ( a > b ) return a; // 整数 a が整数 b より大きければ，a の値を返す
else return b; // それ以外は，b の値を返す
}
int imin( int a, int b)
{
if ( a > b ) return b; // 整数 a が整数 b より大きければ，b の値を返す
else return a; // それ以外は，a の値を返す
}
以下にその編集画面を示します．
5-[h]
自動生成された「 OnTmpltImage() 」 の内部に，以下に示す描画用のコードを追加します．
int ix, iy, iz;
int kx, ky;
BYTE *m_lpData2;
unsigned char r, g, b;
unsigned char y;
int itmp;
int cmplx;
double coef[TMP_SIZE / 2][TMP_SIZE / 2];
double tmp[TMP_SIZE / 2][TMP_SIZE / 2];
// 画像のキャプチャ
dispFlag = FALSE;
capGrabFrame( m_hCapWnd ); // 1フレーム（1枚）を取得するコマンド
while( dispFlag == FALSE) { } // フレームの読み込みが終了するまで待つ
m_lpData2 = (BYTE*)m_lpData; // 画像メモリのポインタ
// リファレンス画像の作成
for( iy = 0; iy < Y_SIZE; iy++){
for( ix = 0; ix < X_SIZE; ix++){
b = *m_lpData2; m_lpData2++; // Blue （青）
g = *m_lpData2; m_lpData2++; // Green （緑）
r = *m_lpData2; m_lpData2++; // Red （赤）
y = (unsigned char)(0.299 * (double)r + 0.587 * (double)g + 0.114 * (double)b);
// Y（輝度）信号
ref_img[ Y_SIZE-iy-1 ][ ix ][ 0 ] = ｙ; // データは上下が反転している
ref_img[ Y_SIZE-iy-1 ][ ix ][ 1 ] = y; // このため上下を入れ替える
ref_img[ Y_SIZE-iy-1 ][ ix ][ 2 ] = y; // モノクローム画像
}
}
// 縮小リファレンス画像の作成
for( iy = 0; iy < Y_SIZE / 2; iy++){
for( ix = 0; ix < X_SIZE / 2; ix++){
itmp = 0;
for( ｋy = 0; ky < 2; ky++){ // 近傍(2×2)の総和
for( ｋx = 0; kx < 2; kx++){
itmp = itmp + ref_img[iy * 2 + ky][ix * 2 + kx][0];
}
}
ref_img_s[iy][ix][0] = itmp / 4; // 近傍(2×2)の平均値をRGBに代入
ref_img_s[iy][ix][1] = itmp / 4; // モノクローム画像
ref_img_s[iy][ix][2] = itmp / 4;
}
}
// DCTマトリクス（ユニタリ行列）の設定
set_dct();
// DCTによる周波数成分への変換処理
max_cmplx = 0; // 画像の複雑度を表す指標
for( ky = -SRCH_SIZE; ky < SRCH_SIZE; ky++){ // 画面中心付近から複雑な縮小テンプレート画像を探索
for( kx = -SRCH_SIZE; kx < SRCH_SIZE; kx++){ // 探索範囲 = ±SRCH_SIZE
for( iy = 0; iy < TMP_SIZE / 2; iy++){
for( ix = 0; ix < TMP_SIZE / 2; ix++){
tmp_img[iy][ix] // 縮小テンプレート画像の生成
= ref_img_s[(Y_SIZE - TMP_SIZE) / 4 + iy + ky - 1][(X_SIZE - TMP_SIZE) / 4 + ix + kx - 1][0];
}
}
for( iy = 0; iy < TMP_SIZE / 2; iy++){ // 水平方向の変換(DCT)
for( ix = 0; ix < TMP_SIZE / 2; ix++){
tmp[iy][ix] = 0.0;
for( iz = 0; iz < TMP_SIZE / 2; iz++){
tmp[iy][ix] = tmp[iy][ix] + dct[iy][iz] * tmp_img[iz][ix];
}
}
}
for( iy = 0; iy < TMP_SIZE / 2; iy++){ // 垂直方向の変換(DCT)
for( ix = 0; ix < TMP_SIZE / 2; ix++){
coef[iy][ix] = 0.0;
for( iz = 0; iz < TMP_SIZE / 2; iz++){
coef[iy][ix] = coef[iy][ix] + tmp[iy][iz] * dct[ix][iz];
}
}
}
cmplx = 0; // 縮小テンプレートの複雑度を現す指標
for( iy = 2; iy < TMP_SIZE / 2; iy++){ // 中高域周波数成分（2〜15次）
for( ix = 2; ix < TMP_SIZE / 2; ix++){
cmplx = cmplx + iabs( (int)coef[iy][ix]);
// 中高域周波数成分の絶対値総和
}
}
if ( cmplx > max_cmplx ) { // 絶対値総和が最大値より大きいとき
max_cmplx = cmplx; // ⇒ 複雑なパターン
x_tmplt_s = kx + ( X_SIZE - TMP_SIZE ) / 4 - 1;
// 縮小テンプレートのx座標を保存
y_tmplt_s = ky + ( Y_SIZE - TMP_SIZE ) / 4 - 1;
// 縮小テンプレートのy座標を保存
}
}
}
// 縮小テンプレート画像の生成
for( iy = 0; iy < TMP_SIZE / 2; iy++){
for( ix = 0; ix < TMP_SIZE / 2; ix++){
tmp_img_s[iy][ix] = ref_img_s[ y_tmplt_s + iy][ x_tmplt_s + ix][0];
}
}
// テンプレート画像の生成
for( iy = 0; iy < TMP_SIZE; iy++){
for( ix = 0; ix < TMP_SIZE; ix++){
tmp_img[iy][ix] = ref_img[ y_tmplt_s * 2 - 1 + iy][ x_tmplt_s * 2 - 1 + ix][0];
}
}
// 画像の表示（OnDrawの起動）
InvalidateRect( NULL, FALSE );
以下にその編集画面を示します．
5-[i]
自動生成された「 OnTmpltMatch() 」 の内部に，以下に示す描画用のコードを追加します．
CClientDC dc(this);
CDC pM;
CBitmap pB， *pOld;
CBitmap pB2， *pOld2;
int i;
int it;
int ix， iy;
int kx， ky;
int dx， dy;
BYTE *m_lpData2;
unsigned char r, g, b;
unsigned char y; // 輝度信号
int diff; // 差分の絶対値総和
int diff_min_s; // 差分の絶対値総和の最小値（縮小画像）
int diff_min[MAX_TIMES]; // 差分の絶対値総和の最小値
int x_min[MAX_TIMES]; // エリア左上の水平座標
int y_min[MAX_TIMES]; // エリア左上の垂直座標
int x_min_s; // エリア左上の水平座標（縮小画像）
int y_min_s; // エリア左上の垂直座標（縮小画像）
int itmp;
char buf[30]; // 文章表示用のバッファ
CPen redPen(PS_SOLID, 1, RGB(255, 0, 0)); // 赤色ペンの設定
CPen bluePen(PS_SOLID, 1, RGB( 0, 0, 255)); // 青色ペンの設定
CPen grayPen(PS_SOLID, 1, RGB(192,192,192)); // 灰色ペンの設定
CPen* pOldPen; // ペンの保存
pM.CreateCompatibleDC( &dc );
pB.LoadBitmap( IDB_BITMAP1 );
pB2.LoadBitmap( IDB_BITMAP2 );
// テンプレートマッチングによる計測を繰り返す
for( it = 0; it < MAX_TIMES; it++){
// 画像のキャプチャ
dispFlag = FALSE;
capGrabFrame( m_hCapWnd ); // 1フレーム（1枚）を取得するコマンド
while( dispFlag == FALSE) { } // フレームの読み込みが終了するまで待つ
m_lpData2 = (BYTE*)m_lpData; // 画像メモリのポインタ
// 計測画像の生成
for( iy = 0; iy < Y_SIZE; iy++){
for( ix = 0; ix < X_SIZE; ix++){
b = *m_lpData2; m_lpData2++; // Blue （青）
g = *m_lpData2; m_lpData2++; // Green （緑）
r = *m_lpData2; m_lpData2++; // Red （赤）
y = (unsigned char)(0.299 * (double)r + 0.587 * (double)g + 0.114 * (double)b);
// Y（輝度）信号
image[Y_SIZE-iy-1][ix][0] = ｙ; // データは上下反転している
image[Y_SIZE-iy-1][ix][1] = y; // このため上下を入れ替える
image[Y_SIZE-iy-1][ix][2] = y; // モノクローム画像
}
}
// 縮小画像の生成
for( iy = 0; iy < Y_SIZE / 2; iy++){
for( ix = 0; ix < X_SIZE / 2; ix++){
itmp = 0;
for( ｋy = 0; ky < 2; ky++){ // 近傍(2×2)の総和
for( ｋx = 0; kx < 2; kx++){
itmp = itmp + image[iy * 2 + ky][ix * 2 + kx][0];
}
}
image_s[iy][ix][0] = itmp / 4; // 近傍(2×2)の平均値をRGBに代入
image_s[iy][ix][1] = itmp / 4; // モノクローム画像
image_s[iy][ix][2] = itmp / 4;
}
}
// 縮小画像の最適エリアを探索
diff_min_s = 10000000; // エリア内差分の最小値を初期設定
for( iy = 0; iy < (Y_SIZE - TMP_SIZE) / 2; iy++){
for( ix = 0; ix < (X_SIZE - TMP_SIZE) / 2; ix++){
diff = 0; // 差分のクリア
for( ky = 0; ky < TMP_SIZE / 2; ky++){
for( kx = 0; kx < TMP_SIZE / 2; kx++){
diff = diff + iabs(image_s[iy + ky][ix + kx][0] - tmp_img_s[ky][kx]);
// 差分の絶対値総和
if(diff > diff_min_s) break; // 無駄な計算を省いて高速化
}
}
if(diff_min_s > diff){ // エリア内差分の絶対値総和が最小値より小さいとき
diff_min_s = diff; // 最小値の保存
x_min_s = ix; // 縮小画像のテンプレート左上の水平座標を保存
y_min_s = iy; // 縮小画像のテンプレート左上の垂直座標を保存
}
}
}
// 縮小画像の最適エリアの近傍で，計測画像を再探索
diff_min[it] = 10000000; // エリア内差分の最小値を初期設定
for( iy = imax( y_min_s * 2 - 3, 0) ; iy < imin( y_min_s * 2 + 3, Y_SIZE - TMP_SIZE - 1); iy++){
for( ix = imax(x_min_s * 2 - 3, 0); ix < imin( x_min_s * 2 + 3, X_SIZE - TMP_SIZE - 1); ix++){
// 探索エリアが計測画像の範囲を越えないよう
diff = 0; // 差分のクリア
for( ky = 0; ky < TMP_SIZE; ky++){
for( kx = 0; kx < TMP_SIZE; kx++){
diff = diff + iabs(image[iy + ky][ix + kx][0] - tmp_img[ky][kx]);
// 差分の絶対値総和
}
}
if(diff_min[it] > diff){ // エリア内差分の絶対値総和が最小値より小さいとき
diff_min[it] = diff; // 最小値の保存
x_min[it] = ix; // 計測画像のテンプレート左上の水平座標を保存
y_min[it] = iy; // 計測画像のテンプレート左上の垂直座標を保存
}
}
}
// 計測画像の表示
SetBitmapBits(pB, X_SIZE * Y_SIZE * COLOR, &image);
// 配列（image）のセット
pOld = pM.SelectObject(&pB);
dc.BitBlt(400, 50, X_SIZE, Y_SIZE, &pM, 0, 0, SRCCOPY);
// 画像の表示 （画面右側）
pM.SelectObject( pOld );
// 縮小した計測画像の表示
SetBitmapBits( pB2, X_SIZE * Y_SIZE * COLOR / 4, &image_s );
// 配列（image_s）のセット
pOld2 = pM.SelectObject(&pB2);
dc.BitBlt(400, 320, X_SIZE / 2, Y_SIZE / 2, &pM, 0, 0, SRCCOPY);
// 画像の表示 （画面右下）
pM.SelectObject( pOld2 );
// 赤色の枠で縮小画像の最適エリアを表示
pOldPen = dc.SelectObject(&redPen); // 赤色に設定 （枠の表示）
dc.MoveTo(400 + x_min_s , 320 + y_min_s );
// 最も類似度の高いエリアの表示
dc.LineTo (400 + x_min_s + TMP_SIZE / 2, 320 + y_min_s );
// 水平・垂直の幅（TMP_SIZE / 2）
dc.LineTo (400 + x_min_s + TMP_SIZE / 2, 320 + y_min_s + TMP_SIZE / 2);
dc.LineTo (400 + x_min_s , 320 + y_min_s + TMP_SIZE / 2);
dc.LineTo (400 + x_min_s , 320 + y_min_s );
// 赤色の枠で計測画像の最適エリアを表示
dc.MoveTo(400 + x_min[it] , 50 + y_min[it] );
// 最も類似度の高いエリアの表示
dc.LineTo (400 + x_min[it] + TMP_SIZE , 50 + y_min[it] );
// 水平・垂直の幅（TMP_SIZE）
dc.LineTo (400 + x_min[it] + TMP_SIZE , 50 + y_min[it] + TMP_SIZE);
dc.LineTo (400 + x_min[it] , 50 + y_min[it] + TMP_SIZE);
dc.LineTo (400 + x_min[it] , 50 + y_min[it] );
// 最適エリアの移動を連続直線で描画
dc.FillSolidRect(400, 450, 400, 200, RGB(255, 255, 255));
// 表示画面のクリア
pOldPen = dc.SelectObject(&grayPen); // 灰色に設定
dc.MoveTo(400 , 550); // 移動量表示の水平座標軸
dc.LineTo (800 , 550);
dc.MoveTo(600 , 450); // 移動量表示の垂直座標軸
dc.LineTo (600 , 650);
dc.TextOutW( 605, 548, (CString)"0"); // 原点"0"の表示
dc.MoveTo(600 , 550); // 原点への移動
for( i = 0 ; i < it ; i++){ // 移動量を連続する直線で描画
if ( diff_min[i] < DIFF_TH_DISP){
pOldPen = dc.SelectObject(&bluePen); // 差分が小さいとき青色に設定
} else {
pOldPen = dc.SelectObject(&grayPen); // 差分が大きいとき灰色に設定
}
dx = x_min[i] - x_tmplt * 2 + 1; // 水平移動量の算出
dy = y_min[i] - y_tmplt * 2 + 1; // 垂直移動量の算出
if ( iabs(dx) < 200 && iabs(dy) < 100 ){ // 移動量が一定の範囲内にあるとき
dc.LineTo(600 + dx, 550 + dy); // 移動量を決められた線で描画
}
}
dx = x_min[it] - x_tmplt * 2 + 1; // 水平移動量の算出
dy = y_min[it] - y_tmplt * 2 + 1; // 垂直移動量の算出
if ( iabs(dx) < 200 && iabs(dy) < 100 ){ // 移動量が一定の範囲内にあるとき
pOldPen = dc.SelectObject(&bluePen); // 赤色に設定
dc.LineTo(600 + dx - 1, 550 + dy - 1); // 赤色の四角の点を描画
dc.LineTo(600 + dx + 1, 550 + dy - 1);
dc.LineTo(600 + dx + 1, 550 + dy + 1);
dc.LineTo(600 + dx - 1, 550 + dy + 1);
dc.LineTo(600 + dx - 1, 550 + dy - 1);
}
// 移動量を数値で表示
dc.FillSolidRect(100, 520, 200, 40, RGB(255, 255, 255));
// 表示画面のクリア
sprintf( buf, "複雑度 = %d", max_cmplx / 10); // 縮小テンプレートの複雑度⇒バッファ
dc.TextOutW( 100, 480, (CString)buf); // ⇒ 表示
sprintf(buf, "times = %d", it); // 表示回数の表示
dc.TextOutW(100, 500, (CString)buf);
sprintf(buf, "x_delta = %d", x_min[it] - x_tmplt_s * 2 + 1);
dc.TextOutW(100, 520, (CString)buf); // 水平方向の移動量表示
sprintf(buf, "y_delta = %d", y_min[it] - y_tmplt_s * 2 + 1);
dc.TextOutW(100, 540, (CString)buf); // 垂直方向移動量の表示
sprintf(buf, "diff = %6d ", diff_min[it]);
dc.TextOutW(100, 560, (CString)buf); // 差分絶対値総和の表示
}
以下にその編集画面を示します．（画像サイズが大きいため，上下4つに分けています）．
６．ライブラリ［vfw32.lib] のリンク設定
メニュー「 表示 」の「 プロパティマネージャ 」をクリックして，「 構成プロパティ 」を開き，「 リンカ 」，「 入力 」を選択します．
右側の「 追加の依存ファイル 」の欄に「 vfw32.lib 」と入力します．
７．ビルドとデバッグ
「 ビルド 」を実行して，エラーメッセージがなくなるまで，「 デバッグ 」を繰り返します．
８．プロジェクトの実行
「 実行結果 」の一例を以下に示します．
画面の左下に，「 相違度 」等の情報が表示され，画面右下に「 移動の履歴 」が「 折れ線グラフ 」により表現されています．
９．まとめ
本章では，USBカメラで撮影した「 静止した対象物 」の画像信号を，「 テンプレートマッチング手法 」を用いて解析することにより，「 カメラの動き 」を連続的に計測するプログラムを作成しました．
「 テンプレートマッチングの高速化 」を実現するため， 画像のピラミッド構造化による「 階層的マッチング法 」と，「 残差逐次検定法 」を導入しました．
さらに「 計測の精度 」や「 信頼性 」を改善するため，「 テンプレート 」に「 複雑な画像 」を探索して設定する方法を実装しました．
ここで作成したプログラムを用いて，「 様々な対象物 」を撮影し， その計測結果を評価して下さい．
上記の対策を施したにもかかわらず，「 正しい移動量 」が得られる場合と，「 誤った結果 」が検出される場合があることが分かります．
「 精度が低下 」する原因として，例えば以下のような項目が挙げられます．
(1) 「 対象物や背景 」 の問題今回は，「 画像の周波数成分 」 を解析することにより，「 複雑なテンプレート 」を探索する機能を実装しましたが，複雑ではあっても，「 ユニーク 」である保障はありません．(2) 「 カメラの動き 」 の問題
「 テンプレート 」 に似ている部分が，「 同じリファレンス画像 」の中に存在しないことを検証する手順が，別途必要になります．
なお，対象物や背景に特徴がなく，「 平坦な画像 」 や「 縞模様 」等の場合は，本質的に計測できません．
「 複雑なテンプレート 」が見つからなかった場合は，「 測定不能 」のメッセージを出力して，測定条件が満たされるまで待機するしかありません．
対象物周辺の照度が低い場合，「 カメラの動き 」 により「 ボケ 」 が生じ，計測の精度が低下します．(3) 「 画面の明るさ 」 の問題
また対象物が「 完全に停止 」している場合であっても ，カメラの動き方によっては，「 テンプレート画像 」もしくは，「 計測画像 」の一方について，「 拡大・縮小 」あるいは，「 回転 」等の処理が必要となる場合が想定されます．
その場合，「 実質的な演算量 」をどのように低減できるかが鍵となります．
具体的な手法として，例えば「 遺伝的アルゴリズム 」等が文献等で提案されています．
背景が静止していても，「 カメラの向き 」 が変化すれば，撮影した「 画面の明るさ 」が変化する場合があります．(4) 「 カメラのレンズ 」の問題
画面の明るさの変化は，市販のカメラに内蔵されている「 自動ゲイン制御（AGC） 」の性能にも影響を受けます．
「 テンプレートマッチング 」を行う場合，この「 AGC 」の機能をオフにした方が，好ましい結果が得られることが多いようです．
「 レンズ 」の「 コマ収差 」や「 ボケ 」なども精度低下の要因となりえます．このように， 「 カメラの画像信号 」 を用いて「 計測 」 や「 解析 」 を行う場合，その「 使用環境 」 を明確にすることが極めて重要であり，
それらを 「 定量的 」に抑える必要があります．
「 信号の解析手法 」 にどのようなものを選ぼうとも，それらの土台がなければ，無力であることを理解して下さい．
