曖昧な塗りつぶしのアルゴリズムについて

Question

画像の中の閉曲線で囲まれた領域を塗りつぶしたいのですが、どのような手法で塗りつぶしたらよいでしょうか？
なお、閉曲線はあくまで曖昧なもので、少しぐらい開いてても構わないとします。
また、閉曲線の色も一色とは限らない状況です。
さらに、閉曲線は凸とも限りません。

つまり、↓のような状況です。（図では凸になっていますが、実際には凸とは限りません。）

---

どなたか、アルゴリズムをご存知の方がいらっしゃいましたら、ご教示ください。

Answer 1

下記の方法でどうでしょうか？

①対象領域を細線化アルゴリズムで細線化し、幅1pxにする。
②対象領域のピクセルを全スキャンし、巡回セールスマン問題の高速解法（2-opt法）などでつなげるピクセルの座標および順番を決定する。
③つなげる順番と座標は配列などにリスト化しておく。
④エルミート補間などの補間法を用いて、補完した曲線を描く。この補完したピクセルもリスト化しておく。
⑤　③と④のピクセルの重複度を調べる。
⑥重複度は一定値以上なら塗りつぶし、一定値以下なら塗りつぶさない。

Comments

[LaLaLand]

なるほどです
ちょっと難しそうですが、このやり方もチャレンジしてみたいと思います

Answer 2

閉曲線の内側を塗りつぶすという処理を考えるならば、まずは与えられた点や線から閉曲線を定義できるかを考えられるとよいかと思います。
閉曲線が得られるならば、あとは通常の塗りつぶし処理を実行する形になります。
実装イメージは与えられるのがビットマップなのか閉曲線候補となる各点の情報のみなのかといった入力にもよりますので、回答に含めるのは難しいです。

Answer 3

ポイントは、ある点が塗りつぶし対象領域に含まれるかどうかの判定だと思います。塗りつぶし領域を定めるために、適当に決めた初期ピクセルの画素値をPV0としますと・・・

###厳密な領域判定
判定は「テスト対象のピクセルの画素値がPV0と一致しているか？」になるかと思います。

###曖昧な領域判定
アイデアとしては、テスト対象のピクセルPおよび近傍のピクセル(そのようなピクセル集合をPsetと呼ぶことにします)の画素値も考慮する方法が考えられると思います。例えば判定方法を以下のようにするなど。

(1) Psetの全てのピクセルの画素値がPV0に一致
(2) Psetの全てのピクセルの画素値の平均とPV0の差が許容誤差内

ちなみに、(1)、(2)いずれにせよ、境界線ぎりぎりまでの領域ではなく、少し内側の領域が塗りつぶされます。人間が行うように「境界線が破れている部分を補完して、その境界線ぎりぎりまで塗りつぶす」ということがしたい場合はもう一工夫必要だと思います。