画像輪郭追跡プログラムと　塗りつぶし
画像輪郭追跡プログラム

　ここでは、最初に簡単な２値画像の輪郭追跡プログラムを紹介します。
インターネットで探せば、輪郭追跡プログラムは、簡単に見つかります。
　ここのでは、データーは、$FF（白）を画像の無い部分とし、$00（黒）の部分を画像として取り扱います。
　 配列を利用して、追跡する場合と、アルゴリズムにより計算して追跡する場合についてプログラムを作成してみました。
まずは、配列の利用ですが、これは馬鹿馬鹿しくプログラムが大きくなりますが、プログラムの練習と思ってください。

最初に、輪郭追跡の手順です。
 追跡手順図　まず最初に図の上側左から右へ、画像点を探します、無かったら下の並びに移動して、左から右へスキャンし、画像点が見つかるまで探します。
最初の画像点が見つかったら、その点の左下、下、右下、右、右上と検索し、
画像点が見つかったら、その見つかった点に、画像検出中心点を移動します。
　図の例ではまず最初に、下で見つかったので、画像検出中心点を下へ移動します。
　次は、又、左下、下と検索しますが、左下で見つかるので、画像検出中心点を左下へ移動します。
　今度は、左上、左、左下、下、右下、右と検出をし、検出した点に移動して、移動します。
　この様な作業を繰り返し、一周して元へ戻ったら、輪郭抽出の終了です。


　移動した方向によって、検索する開始点が違います。

検出点図検出点を図にしてみると、左図、左側の様になります。
移動した方向によって、検出開始点が異なります。

１．上と、左上に移動した場合は、移動した点の右上から左回りに検出します。
２．左と、左下へ移動した場合は、左上、左、左下、下、右下、右、右上となります。
３．下と、右下へ移動した場合は、左下、下、右下、右、右上、上、左上、です。
４．右と、右上に移動した場合は、右下、右、右上、上、左上、左、左下となります。
　移動方向は、８方向ですが、検出の順番は、４通りです。

それを、右上の表にまとめてあります。

　配列にすると、右下のようになります。
配列の値は、現在の座標に対して、検出する時、加算するＸ座標とＹ座標の値です。

　移動方向を図にしてみました。
移動方向番号
移動した方向、上を　１　にして左回りに番号を振ってあります。
上１と、左上２へ移動した場合は、配列 cpt0 を使用して、検出を行います。
左３と、左下４へ移動した場合は、配列 cpt1 を使用して、検出を行います。
下５と、右下６へ移動した場合は、配列 cpt2 を使用して、検出を行います。
右７と、右上８へ移動した場合は、配列 cpt3 を使用して、検出を行います。
下の表は、検出に使用した配列に対する、移動番号を示すものです。
アウトラインNopos
　配列cpt0を使用して周囲の画像点を検出した場合は、cptN0 を使用して次の移動方向Noを設定します。
　配列cpt1を使用して周囲の画像点を検出した場合は、cptN1 を使用します。

配列cpt0のインデックス番号が　１　だったら　移動方向は、cptN0のインデックス番号１の値　８　右上になります。

画像データーを上からスキャンして、画像が見つかった場合、最初の検索は、移動方向　下　５　として検索を開始します。

アルゴリズムによる方法
　今までの内容から、簡単な法則が見つかります。
まず、検出する周囲の場所に、左回りに８箇所連番を付けます、連番であれば、何処からでも構いません。
水平　及び　垂直方向に移動した場合は、移動した方向の番号に対して、一つ　マイナスした場所から、検索を開始します。
斜め方向へ移動した場合は、移動した番号の方向に対して、二つ　マイナスした場所から検索を開始すれば目的を達成することが出来ます。

　更によく検討をすると、水平、垂直に移動した場合の、　二つ　マイナスした場所には、画像がありません。
それで、何時でも、移動した番号の方向に対して、二つ　マイナスした場所から検索を開始すれば、良いことが分かります。

ここでダウンロード出来るプログラム例では、配列 cpt0 を一つを利用し、周囲検索を行っていますが、 case 文　を使用しても良いと思います。
しかし、周囲検索は配列を使用した方が、プログラムはすっきりします。

輪郭追跡の特異点

特異点 　輪郭追跡を行う場合、左図の赤の場所が追跡開始点だったとすると、図で直ぐに分かるとおり、追跡開始点を２度通ることになります。
単純に、元へ戻ったら、追跡終了とすると、追跡が不完全なものになってしまいます。
　これを避けるために、少し工夫が必要です。
追跡開始点を２度通る条件の時には、開始点の下には、画像が無い、開始点の右下か、右から、開始点に戻ると言うことです。
開始点の下に画像があると、開始点は２度通らないが、右に画像があれば、必ずそこを通って開始点に戻り、右に無く、右下に画像があれば、必ずそこを通って開始点に戻ります。
　そこで、開始点の左下と、右に着目します。
開始点を２度通る通らないに限らず、開始点の右に画像がある場合は、必ずそこを通って開始点に戻ります。
開始点の右に画像が無く、右下にある場合は、右下から開始点に戻ると言う法則です。
　輪郭追跡に先立って、この２箇所を調べます。
右下に画像があったら、まず、最初に、その座標を通って戻ることを条件にします。
次に右を調べます、ここに画像があったら、前の座標を取り消し、右の座標を通ることを条件にします。
右、及び　右下に画像が無い場合は、開始点を２度通ることはありません。

塗りつぶし

画像元データー　輪郭追跡プログラムは、画像データーの中に、複数の画像がある場合、最初に検出した画像で、郭追跡を終了してしまいます。
その場合、最初に検出した画像を消去し、輪郭追跡を行い、全ての画像が無くなったら、輪郭追跡終了とします。
　輪郭検出した画像を消去するために、塗りつぶしを利用して行います。

　輪郭追跡をする時、フルカラーモードで行うと、プログラムが煩雑となるので、ここでは、単純な２値データーに変換して行う事にします。
左図は、複数の画像がある画像データーです。

グレイ化画像まず、フルカラー画像を８ビットグレー画像に変換します。
単純に、Ｒ、Ｇ、Ｂ　のを加算し、３で割って平均値にしています。
色に明度に対する係数を使用する場合もありますが、ここでは単純に平均値の値を採用しています。

２値化画像　２値化画像処理をします。
背景に淡いハーフトーンのような画像が無ければ、２値化の処理は不要です。
ここでの画像データーは８ビットデーターなので、０～２５５の値の中間の値を設定し、それ以下だったら、＄００　それ以上だったら、＄ＦＦ（２５５）に全て変換します。

最初の輪郭追跡　輪郭追跡を行います。

輪郭追跡を行うと、最初に実行されるのは、一番上の位置の画像です。


塗りつぶし画像　輪郭画像の外側を塗りつぶします。
画像の外側に、＄００、＄ＦＦ以外の値を書き込んで埋め尽くして塗りつぶしします。

塗りつぶした場所は、左図ではグリーンになっています。
単に表示だけの為なので、何色で表示しても良いでしょう。

実際の塗りつぶしは、輪郭画像の中を塗りつぶした方が、面積が小さいので、早く塗りつぶし出来ますが、輪郭画像は複雑で、輪郭の中と判断するアルゴリズムが見つからなかったので、外側を塗りつぶすことにしました。


最初の画像消去　左図では赤丸の中の四角い画像が消えています。
　画像の２値化データーの値から、塗りつぶしのデーターのある場所を残し、塗りつぶしデーターの無い場所を消去します。（＄ＦＦの値を書き込みます。）

次の輪郭追跡　消去作業が済んだら、再度輪郭追跡をから実行します。
２値化画像なくなるまで、繰り返して行います。

輪郭追跡完了画像　左図は、全ての画像の輪郭追跡が終了した画像です。

　画像処理は、二次元の配列を使用しているので、Delphiの中の　塗りつぶし（FloodFill）関数は使用できません。
ここでは、簡単な、シード・フィル アルゴリズムを使用します。
　塗りつぶしに、配列のPｏｐ Ｐｕｓｈを利用しますが、この関数はＤｅｌｐｈｉに無いため、作ることにします。
これは簡単で、動的配列を宣言します。
最初に長さ０で配列を作成します。
Push は、配列の長さを一つ追加して、その中にデーターを書き込みます。
Ｐｏｐは、配列の末尾からデーターを読み出し、読み出したら、配列の長さを一つ短くします。

 ArPosi : integer; 			// 配列長さ
PushPopAryX : array of cardinal; 	// X座標用配列
PushPopAryY : array of cardinal; 	// y座標用配列

// ブッファ末尾追加
procedure Push(X1, Y1: integer);
begin
  ArPosi := ArPosi + 1; 		// 配列長さ１加算 inc(ArPosi)
  SetLength(PushPopAryX, ArPosi); 	// x配列長さセット
  SetLength(PushPopAryY, ArPosi); 	// y配列長さセット
  PushPopAryX[ArPosi - 1] := X1; 	// 配列の最後にX位置書き込み
  PushPopAryY[ArPosi - 1] := Y1; 	// 配列の最後にY位置書き込み
end;

// ブッファ末尾抜き出し
procedure PoP(var X, Y: integer);
begin
  X := PushPopAryX[ArPosi - 1]; 	// X最後の位置のデーター取り出し
  Y := PushPopAryY[ArPosi - 1]; 	// Y最後の位置のデーター取り出し
  if ArPosi > 0 then ArPosi := ArPosi - 1; 	// 配列長さ１減算 dec(ArPosi)
  SetLength(PushPopAryX, ArPosi); 	// x配列長さセット
  SetLength(PushPopAryY, ArPosi); 	// y配列長さセット
end;

　塗りつぶしは、最初にどこか、塗りつぶし座標　Ｘ，Ｙ　を指定します。
１．指定された座標　Ｘ，Ｙ　を塗りつぶし色に変更します

２．指定された座標の、左、右、上、下の座標が塗りつぶされていなかったら、その座標を、Ｐｕｓｈ　します。
３．配列の長さを確認します、配列の長さがゼロだったら、塗りつぶし終了です。
４．Ｐｏｐして、その座標　Ｘ，Ｙ　を塗りつぶし色に変更します。
５．Ｘ，Ｙ　を指定座標として　手順　２．から繰り返します。

// 塗りつぶしが必要か確認　塗りつぶしが必要だったら　True　を返します。
function OnPaint(X2, Y2: integer): boolean;
begin
  Result := False;
  if PaintData[X2, Y2] = $FF then Result := True;
end;

// 塗りつぶし場所検索
procedure pushPixel(X, Y: integer);
begin
  if X - 1 >= 0      then if OnPaint(X - 1, Y) then Push(X - 1, Y);
  if X + 1 < BWidth  then if OnPaint(X + 1, Y) then Push(X + 1, Y);
  if Y - 1 >= 0     then if OnPaint(X, Y - 1) then Push(X, Y - 1);
  if Y + 1 < Bheight then if OnPaint(X, Y + 1) then Push(X, Y + 1);
end;

// X, Y を指定して塗りつぶしを開始します。
procedure Fill(X, Y: integer);
begin
  PaintData[X, Y] := $02; 		// 最初の位置塗りつぶし色に変更
　While True do begin 			// 塗りつぶしルーチン
    // 塗りつぶしの対象の検索
    pushPixel(X, Y); 			// ４箇所周囲検索配列データー末尾に追加
    // 塗りつぶし対象が無いなら終了
    if Length(PushPopAryX) = 0 then break;
    // バッファから塗りつぶし指定場所取り出し
    Pop(X, Y); 				// 配列データー末尾から抜き出し
    // 塗りつぶし
    if PaintData[X, Y] <> $02 then  	// 塗られていなかったら
                PaintData[X, Y] := $02; 	// 塗りつぶし色に変更
  end;
end;

 　この方法は、塗りつぶしていない座標をＰｕｓｈして、メモリーへ追加しますが、そのメモリーへ追加した座標をそのままにして、同じ座標を塗りつぶすと言う行程が発生します。
Ｐｏｐして、再度検索に行ったとき、全て塗りつぶされていれば、次々とＰｏｐされることになりますが、作業としては、かなり無駄が多いことは確かです。
しかし、アルゴリズムが単純なので、プログラムミス無く完全に塗りつぶすことが出来ます。

　輪郭追跡結果画像の外側塗りつぶし方法

図形外側塗りつぶし　輪郭追跡画像のある図形のふちに沿って、画像の無い部分を検索します。
まず、どこか、図形の隅を開始点とします。
単純に、座標　０，　０　から開始します。
　もし、塗りつぶしも無く、画像も無かったら、その座標を塗りつぶし開始点として塗りつぶし行程を実施します。
検索が一周して戻ったら、塗りつぶし完了です。

　プログラムの詳細は、プログラムリストをダウロードして、参照して下さい。
サンプルのビットマップファイルもありますので、実行しテストしてみて下さい。

ボタン類　各ボタンの機能について説明をします。

　FileOpen ボタンは、ビットマップファイルを指定して開きます。
ファイルの種類は、24ビットカラー　以外は開くことが出来ません、JPEGファイルの場合は、ペイントブラシで、開いて、24ビットカラーで保存しなおすか、
Ｄｅlｐｈｉで、ＪＰＥＧファイルを読み込んで、ＴＢｉｔｍａｐに変換が出来るので、ファイルオープンに、そのルーチンを追加して下さい。
　Grayボタンは、単にグレー変換されたデーターを表示する為の物です。
　binarizationボタンは、２値化するためのもので、スレッシュホールド(threshhold)の値によって、　$FF　と、 $0の値に変換しますが、threshholdの値を、変更する為の入力はありません。
必要であったら追加して下さい。
　Outline ボタンは、輪郭追跡実行ボタンです。
　Direction ボタンは、単に追跡した方向を、色で参考表示するもので、計算とは一切関係ありません。
　FillPaint は、輪郭追跡した図形の外側を塗りつぶします。
　Erase ボタンは、塗りつぶし作業で、塗りつぶされた部分の画像を残して、輪郭追跡した画像部分を消去する作業を行います。
　OutLineDsp は、輪郭追跡の最終結果の表示をします。
　Auto ボタンは、ビットマップファイル図形の中に、複数の画像があった場合、自動的に、全ての画像の輪郭追跡を行うものです。
Auto ボタンをクリックすると、ファイルオープン窓が開くので、２４ビット　ビットマップファイルを指定して開くます。
その後は、①②③④の作業を、全ての画像に対して自動的に実行します。

　各チェックボックスの機能説明です。

　アウトライン追跡表示　は、追跡状況を画面に表示します。
　塗りつぶし参考表示　は、塗りつぶしていく様子を、表示するものです。

　トレース方法変更　は、チェックを入れていない場合は、配列データーにより追跡し、チェックを入れた場合は、アルゴリズムの利用により追跡します。
　終了ボタンは、その名のとおり、プログラムを終了するためのものです、演算中に終了すると、メモリーリークが発生するので、演算中は、終了出来ないようにしています。

　白抜き画像の外側追跡

今度は、白抜き画像の画像外側縁に沿って追跡するモードについて取り上げます。
白抜きモード　白部アウトラインとは違うので注意が必要です
白抜きのスキャンなので、白抜きの外側は、全て画像である事が必要条件です。
画像を左上からスキャンし、最初の白を検出したら、その一つ上側の画像から検索を開始します。
検索プログラムのアルゴリズム自体は、画像輪郭追跡と同じですが、最初の開始点の、検索開始位置が違います。
この場合は、検索開始は、中心位置の真下からとなります。
　輪郭追跡の最初の検索位置が、５　左下だとすると、６　下　になり、１つ進ませた位置から検索をします。
そうすると、検索は、図の様に画像の外側に沿って、今度は右周りに検索されます。

白抜き追跡結果　結果は輪郭追跡と同じ様ですが、白抜き部の外側のラインとなります。
このモードの利用は、輪郭追跡した画像の中に、白抜き部があった場合、その白抜き部の形状を追跡するためのものです。
サンプルプログラムでは、個別のプログラムとなっています。
二つを組み合わせたプログラムを作成すれば、画像の輪郭追跡として完全なものになります。

白抜きが複数ある場合の処理手順

ビットマップの読み込みグレイ処理２値化

反転　此処までの処理は、サンプル画像を読み込むためのもので、輪郭追跡した画像の中の白抜きを追跡する場合は、
左図のような画像から開始することになります。
実際には、輪郭追跡時、輪郭の外側を塗りつぶした画像と、元画像の　ＯＲ　を取ることにより、輪郭追跡した画像の白抜き画像を取得することになります。


内側追跡１最初の内側縁追跡を行うと、追跡画像として左図のような結果が得られます。


塗りつぶし内側縁追跡開始時の、白画像検出座標から塗りつぶしを実行します。

白抜き追跡二回目内側追跡を再度実行すると、今度は、最初の白抜き点が下側の画像となるので、
左図のような結果となります。

又、塗りつぶしを行います。
白抜き画像が無くなったら、白抜き画像の追跡処理は終了です。
再度塗りつぶし白抜き追跡結果


画像の輪郭追跡結果と、白抜き画像の追跡処理結果を合成すれば、完全な画像の輪郭線を得ることが出来ますが、複雑な画像の場合、処理に時間が掛かります。
又、此処での処理は２値化した画像でしか出来ません。
複雑な画像の場合は、輪郭抽出プログラムの方が良いでしょう。

　　　　　　download OutLineTrack.zip

画像処理一覧へ戻る

　　　　　　最初に戻る