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

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

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

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

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

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

最初の図の輪郭は

０→０→１→０→２→３→４→３→２→５→５→６→４→０→６→５

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