エッジの２値画像から閉じている四角形を探す

質問

エッジの情報の２値画像があります。閉じている四角形を探して、さらに各頂点の座標を調べる方法を考えています。
いったんラベリングしてから同じラベルの画素の隣接を追跡して最初の地点に戻ってきたら閉じているみたいな方法でやろうかなと考えています。
もっとよい方法をご存知でしたら参考図書やURL、論文なんかを教えてもらえるとうれしいです。

頂点を探す方法は見当もつかないので、ヒントとなることを何でも教えていただけないでしょうか？
よろしくお願いします。

回答No.1

tatsumi01 · ベストアンサー

エッジ画像と輪郭を区別して下さい。
輪郭とは、周囲の白領域とエッジの黒部分との境界で、時計回り（または反時計回り）に一周することができます。エッジ画像は境界付近に複数の黒画素があって、どこが真の境界か判然としません。言ってみれば、輪郭は１次元の画素系列で、エッジ画像は単なる２次元画像です。
エッジ画像（でなくても元の２値画像）があれば、その輪郭を追跡するアルゴリズムはあります。恐らく詳細を書いた公開文献はなく、メーカーなどのノーハウでしょう。
輪郭画素を時計回り（反時計回り）に追跡して輪郭点系列ができれば、輪郭を一周し、各点Ｘについて前方向に３戻った点Ａと後方向に３行った点Ｂ（３でなくて５だって構いません）をもとめ、ＡＸを結ぶ線分、ＸＢを結ぶ線分を作り、二つの線分のなす角度が９０°に近ければ頂点となります（実際には、さらに修正が必要です）。

回答No.3

tatsumi01

No. 1 ですが、前のコメントが言葉足らずでした。
エッジ画像は２次元画像です。輪郭と見たところは同じですが、画素相互の関係がないところが違います。エッジ画像そのままではその上を一周することができません。
輪郭は座標系列のリストで、いわば１次元情報です。輪郭の上の画素には順番がついているので一周することができます。
エッジ画像の上を一周するように工夫することはできますが、結局それは輪郭抽出していることになります。

回答No.2

tatsumi01

No. 1 ですが、輪郭を求めるアルゴリズムを簡単に書いておきます。
（０）対象画像を左上から右に向かって走査し、最初にぶつかる黒画素をスタート画素Ｓとします（ある走査線が全部白画素だったら次の走査線に移る）。Ｓの座標を記録します。
（１）Ｓの回りには８画素ありますが、左の画素（白の筈）から始めて時計回りに一周し、黒画素を探します。見つからなければ孤立点です。
（２）見つかった黒画素の座標を記録します
（３）その画素をＳとして（１）と同じことをします。ただし、周辺８画素の中の開始点は左ではなく、前の一周での最後の白画素からです。
（４）最初のＳと同じ座標に戻れば終わり。
このアルゴリズムにはいろいろな変種が考えられます。
なお、このアルゴリズムで求められる輪郭は１個です。２個以上の輪郭を探したいならいろいろな工夫が必要です。
輪郭追跡のプログラムはバグが出やすいので頑張って下さい。
輪郭が求まったあと、頂点を探す方法はいろいろ考えられますが、とりあえず No. 1 で書いた方法が良いでしょう。

お礼

回答ありがとうございます。
質問でエッジと書いていたのは、輝度をあらかじめ２値化したもののエッジなのでtatsumi01さんのおっしゃられる輪郭というものに当てはまりますね。
輪郭というキーワードは、調べていなかったのであたらしいヒントになりました。ありがとうございます