輪郭追跡アルゴリズムの改良

全文

(1)情報処理学会第 80 回全国大会. 3E-07. 輪郭郭追跡アアルゴリズムの改改良小林郁郁典. 大政政雄照. 徳島文理大大学大学院工工学研究科. １. はじめめに. 2 値画像像に対して，同じセル値で構成されるる領域の輪郭をを抽出するこことを輪郭追追跡処理といいう。輪郭追跡処処理には，境境界の捉え方方によって，画素追跡型，辺追跡型，頂点追跡型型の３種類がが存在する[1]がが，本研究ででは，このううちの頂点追追跡型の輪郭追追跡処理に注注目する。ここれは，図 1 に示すようなな比較的大ききなセルからら構成されるる２値画像かららポリゴン（を描くためめの頂点座標標リスト）を求求めることをを最終的な目目標としていいるからである。. る輪輪郭交点に注注目し，そのの周囲にあるる 4 つのセルのの状態（パタターン）から次の輪郭交点が存在在するる方向を求めめ，この方向向に 1 セルル分移動する。これれを繰り返すすことで輪郭郭交点のリストを獲得得するる。周囲にあある 4 つのセルの組合合せは，図 2 に示示す 16 種類類である。ここのうち 0 と 15 番目のパタターンは輪郭郭交点ではなないために除外すると，次のの輪郭交点をを見つけるたためには 14 種類のパタる。このとき，次の隣ーンン照合をするる必要がある隣接交交点が存在すする方向を決決めるためにに平均 7.5 回の照照合が必要ととなる。またた，アルゴリズムの性性質上上，通過したたすべての輪輪郭交点の座標が出力ば，目的とするポリゴされれる。これをを利用すればゴンをを描くことがができるが，，その中には描画にははの）情報が含まれる場なくくてもよい（輪郭交点の場合ががある。もちちろん，これれらは事後に削除可能能であある。. 図 1 ２値値画像(左)と求めるポリゴン(右)の例例頂点追跡跡型輪郭追跡跡の代表的ななアルゴリズズムとして，李李ら[2]が提案案されたもののが挙げられれる。接する輪郭交交点の存在すする方向図 2 隣接り高われわれははこのアルゴゴリズムを改改良し，より速に結果がが得られるよようなものをを考案した。。本 2.2 2 重みによるる頂点追跡型型輪郭追跡報告では，この改良アアルゴリズムムについて報報告われわれが提わ提案する改良良手法の要点は，重みみする。なおお，本報告ででは，ポリゴゴン上の「交交点」の頂点が存在する（隣によよる頂点の抽抽出と，次の隣を表１のよように区分すする。向を効率よく求めるこ接すするとは限ららない）方向とのの 2 つであるる。表 1 ポリゴン上の交点のの区分（１１）重みによよる頂点の抽抽出メッシュ交交点ポリゴゴンに内包される交点上述の通り，上李らのアルルゴリズムは周辺セルル輪郭交点点ポリゴゴンの輪郭上上にある交点点のパパターンとのの照合により解を求めるものであ頂点ポリゴゴンを描画すするために必必要るがが，われわれれのアルゴリズムは，メッシュ交交な交点点（かど）点のの周囲にあるる 4 つのセルの状態かから求められれ接点他のポポリゴンと接接する交点る重重み（交点値値）により解解を求めるものである。 4 つのセルがすつすべて 0 の場場合が交点値値 0，すべて２頂点追追跡型輪郭郭追跡アルゴゴリズム 1 の場合が交点の点値 4 であるる。従って，交点値は 0 2.1 代表的的な頂点追跡跡型輪郭追跡からら 4 の整数数値を取る。交点値と対対応する交点点李らが示示す頂点追跡跡型輪郭追跡跡アルゴリズズムの種種類を表 2 に示す。こここで，交点値値 2 の輪郭郭の基本的なな考え方は次次の通りであある。まず，あ交点点か接点の区区分は，周囲囲 4 セルの 1 の位置関関 Improvemen nt of contour tracking t algoriithm 係かから判断するる。 Ikunori KOB BAYASHI† andd Kazuaki OOM MASA （２２）次の頂点点が存在するる方向 Graduate Schhool of Engineeering, 図 3 左のように，左上上からラスタスキャンし Tokushima B Bunri Universitty 769-2101, K Kagawa, Japan, [email protected] unri-u.ac.jp た場場合，最初にに出会う交点点値 1 の交交点がポリゴゴ. 4-13. Copyright 2018 Information Processing Society of Japan. All Rights Reserved..

(2) 情報処理学会第 80 回全国大会. ンの最初のの頂点であるる。この次のの頂点は右方方向に存在するる。ここで，図 3 中央のの図に示す通通り，上下左右のの 4 方向を 0 から 3 までの整数で表表現目すすると，ここの右方向はは 0 で表現さされる。注目る頂点からら右方向の交交点をたどれれば必ず次のの頂点が存在すする。次の頂頂点の交点値が 1 か 2 のの場合には，そその次の頂点点方向は時計計回りに 90° °回転した下（（方向を表すす数値に対しして+1 を適用用する）に存在在する。次のの頂点の交点点値が 3 の場場合には次頂点点方向は反時時計回りに 90°回転した 9 た方向（方向をを表す数値にに対して-1 を適用する）を）に存在する。この手順をを適用し続けけると注目すする頂点は必ずず開始頂点ままで戻り，ポポリゴン（をを形成する頂点点リスト）をを抽出できるる。この様子子を示したもののが図 3 右でである。以上上がポリゴンンの外郭（外周周）の輪郭をを得る手順でであるが，内内郭輪郭の場合合も基本的にに同様な手順順で抽出が可可能である（表表 3）。表 2 交点値と対対応する交点点の種類交点値値交点の種種類 0 メッシュュ交点 1 頂点点 2 輪郭交点か接点 3 頂点点 4 メッシュュ交点. うももので，これれは，ラスタタスキャンをを 1 回で終終えるることができきる。両者のの処理時間の比較をした場場合，1 回ののスキャンでで終えることができる後の抽出を終えることが者のの方が高速ににポリゴンのでききるが，前者者の方は 1 度目のスキャン終了時時に 2 値画像内に存在するポリゴンの形状特性を把握握することがができるのでで，状況によってはポポリゴゴンの抽出をを中止することができるという利利点ががある。具体体的には，1 回目のスキキャンで得られるる表 2 の各交交点値から判判断する。. ４おわりにに改良アルゴリ改リズムの評価価をするため，国土地地理院院が公表してている数値標標高（50m メッシュ）の浸水予測エリアをポデーータを用い，ある領域のポリゴゴンで抽出すする時間を計計測した。李らのアルルゴリリズムとわれれわれのアルルゴリズム（（2 回スキャン）を比較したた場合，われれわれの方が平均で約約 25% %（n=10）高高速であったた。また，同じデータも 1 回スキに対対し 2 回スキャンよりもキャンの方が約 30%高速であった。これらの結果果は，2 値画画像中中に置かれてているポリゴゴンの状況や形状の複複雑ささに依存するる。. 参考考文献. 表3. 外郭と内郭による追跡方方法の違い外郭追跡跡内郭追追跡最初の頂点点の交点値 1 3 最初のの方向 0 1 反時計方方向向次の頂点交点値:1,22 時計方向反時計方向の方向交点値:3 時計方方向. [1] 鳥脇純一郎郎, 画像理解解のためのディジタルル画像像処理（Ⅱ），昭晃堂(11988) [2] 李志広,他, 交差点記述述法による 2 値画像の輪輪郭追追跡と復元, 電子情報通通信学会論文文誌 D, Vol. J65 5-D No.10, pp.1203-121 p 0 (1982). 図 3 交点値に基づく頂点点追跡. ３. 実装方方法によるる違い. われわれれのアルゴリリズムでは，交点値を求求めるタイミンングによってて 2 種類の実実装方法が考考えられる。1 つめの方法法は，最初のラスタスキャャン時にすべててのメッシュュ交点の交点点値を求めなながら頂点候補補を絞り込み，2 回目のラスタスキャャンでポリゴンンを抽出するものである。。2 つめの方方法は，交点値値の算出とポポリゴンの抽抽出を同時にに行. 4-14. Copyright 2018 Information Processing Society of Japan. All Rights Reserved..

(3)