シルエットパズルに対する解析のアプローチは様々なものが考えられる。
以前の記事https://pzdc.hatenablog.com/entry/2021/10/06/003237で書いていた輪郭追跡のアプローチに関しては調べてみるとActive Contour法やLevel set法、Snakes、グラフカットなどの手法が存在していた。これらについても検討したいが、今回は少し趣向を変えて特徴点からのアプローチを試してみたい。
特徴点としては、
- シルエットの頂点(コーナー)を求める。
- シルエットの辺(エッジ)を求める。
- 満遍なく配置(dense sampling)する。
といった方針が存在する。
得られた特徴点の扱い方として、頂点なら角度を出すというのが(パズラー的には)わかりやすい。ただ、角度を出すならば輪郭追跡からのアプローチの方がよさそうである。今回はせっかく特徴点にするので、少し趣向を変えたいところ。気持ちとしては、特徴量をなんらかのベクトルにして、クラスタリングなどがしたい。
何はともあれ、まずは特徴点の検出が必要になる。ハリスコーナー検出器でコーナーを出してみる。
図1が入力画像(例)である。ハリスコーナー検出器のスコア画像で、最小値と最大値の間の30%の値を閾値として点を得る。得られた点の総数が100よりも多い場合は上位100点に絞り込む処理を書いている。図2が結果である(見やすさのためシルエットは薄くしている)。残念ながら検出されていないコーナーがある。ハリスコーナー検出器は傾向として鋭利なコーナーのスコアが高く、鈍くなるにつれて検出精度が下がる傾向にあるようだ。鈍角のコーナーの検出の難しさは本質的な問題ではあるが、図2で検出できていない(3つの)コーナーに関しては、135度のコーナーであり、これくらいは検出してほしいところである。ノイズの影響かと考えてガウシアン平滑化を試したがうまくいっていない。
コーナー判定の閾値のパラメータを下げるとコーナーが増えると考えられるが、現状の閾値で、エッジや平坦領域が検出されてしまっているシルエットも存在しているため、コーナーだけをピンポイントで検出できていない。「上位100点」の制約はこのために加えていた制約だが、次の2つの理由からうまくいっていない。
- ひとつのコーナーの近傍から複数のコーナーが検出されてしまっている(多重検出)。
- ひとつのシルエットに含まれるコーナーの数は、一般には事前に予測できない。
このうち、1. の多重検出に関しては、近接コーナーの禁則で解消できる可能性がある。少し多めに検出させておいて、DBSCANのようなクラスタリング後処理で消しても良いかもしれない。あるいはキャニーエッジ検出器のような高度な判定(連結性等を見る判定)をすれば良いかもしれない。いずれにせよ少々込み入った調整が必要になりそうである。
閾値を画像から自動で決定することができれば、うまくいくようにも思う。ヒストグラムを作成して谷を検出すれば良いかもしれない。これも少し調整が難しそうである(問題の難しさが元の問題の難しさを上回っているようにも思う)。
他のコーナー検出器を試しても良いだろうが、そもそもコーナー検出器は検出される(正解の)点の数が少なく、扱いづらいように思う。エッジからのアプローチの方が強力ではないかと考えている。
キャニーエッジ検出器を用いるとエッジ上の点を明確に抽出することができる。コーナー検出器と比べて検出点が多いため、選択肢が増える。図3では、検出された点の内、100点をランダムサンプリングしている。例えば点群のアプローチが使えると思われる。Shape Context FeatureをBoVWにしたり、パーシステントホモロジーを用いたりして解析することができるのではと睨んでいる。