質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.75%

  • アルゴリズム

    380questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

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

解決済

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 375

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

つまり、↓のような状況です。(図では凸になっていますが、実際には凸とは限りません。)
イメージ説明


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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/20 14:31

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

    キャンセル

checkベストアンサー

0

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

厳密な領域判定

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

曖昧な領域判定

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.75%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • アルゴリズム

    380questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。