画像処理画像処理アルゴリズム

輪郭追跡処理アルゴリズム

二値化された画像において、各連結部分の境界部分を求める事を輪郭追跡といいます。
この輪郭追跡を行う事で周囲長や連結領域の高さなどを求めることが出来ます。

 

以下、この輪郭追跡の処理アルゴリズムを紹介します。

 

まず、左上からラスタスキャンを行い、白の部分を見つけます。

 

輪郭追跡処理アルゴリズム

 

最初の白の部分(上図の赤丸の部分)をスタート地点として、反時計回りに輪郭の部分を検出します。
最初の白の部分は左上からラスタスキャンしたため、スタート地点の右上、上、左上、左には白の部分が無い事が確定しているので、最初に左下の部分から反時計回りに白の部分を検索し、白の部分が見つかったら次の輪郭へ検索を続けます。
最後にスタート地点に戻ったら処理は終了です。

 

この時、輪郭の向きを下図のように定義しておくと、

輪郭追跡処理アルゴリズム

 

最初の図の輪郭は

 

0→0→1→0→2→3→4→3→2→5→5→6→4→0→6→5

 

の順で変化しています。(この番号はチェインコードといいます。)
ここにちょっとした規則があります。
例えば、の次に5、1の次に6、・・・などは絶対に来ません。(なぜかは、ちょっと考えると分かります。)
一般的に表現すると、
一つ前の輪郭の向きから時計回りに3つ分の向きには輪郭が存在しない。
という事になります。
この性質を利用して、輪郭を検索するときは、
一つ前の輪郭の向きの値をVold
輪郭の検索を開始する向きの値を Vnew
とすると、
Vnew = (Vold + 6) % 8; (%は8で割った時の余りの計算)
となるVnew の向きから輪郭を検索すれば効率的に輪郭を検索することが可能となります。

 

また、輪郭の周囲長を求める時、縦、横方向の輪郭は長さ、斜め方向の輪郭は√2 として
長さを足していくと、周囲長が求まります。

 

そして、ここからがあまり書かれていない注意点!
スタート地点の白の画素のパターンが以下のパターンとなる場合、スタート地点を2回通る事になるので、ご注意下さい。

輪郭追跡処理アルゴリズム

※グレーの部分は白でも黒でもよい部分

 

画像処理アルゴリズムへ戻る

 

コメント

  1. […] 輪郭追跡を行うと周囲長を求めることができますが、この周囲長を用いた代表的な特徴量の円形度を紹介します。 […]

タイトルとURLをコピーしました