2010/08/27

ジグソーパズルプログラム 苦戦中

むずい、、むずいよ ジグソーパズル解答プログラム (ノД`)


Googleで答えを探しても文献が見当たらず、ようやく見つけたのが
A Global Approach to Automatic Solution of Jigsaw Puzzles という論文。
この論文では、輪郭同士を直接マッチングさせるのではなく、出っ張っている部分やへこんでいる部分の位置や大きさを比較して、その後で輪郭情報を使用してマッチングさせているようです。

論文の中では「巡回セールスマン問題を解くことで、自動的にパズルを解かすことに成功した」的なことが書かれていたのですが、巡回セールスマン問題は難しそうなのでパス。
フルオートで解答させるのはあきらめて、まずはセミオートで解答するものを作ることにしました。

処理手順(新)

・輪郭を抽出します。(ピースの数だけ輪郭が出力されます)
・輪郭1個ずつに対し、下記の処理を行います。
・輪郭に外接する四角形をcvMinAreaRect2を使って求めます。
・外接する四角形のサイズ、中心点、角度がわかったので、1ピースごとに回転が0度になるようにcvGetQuadrangleSubPixを使って回転させます。
・この時点で1ピースの向きは、45度傾いているか、整列されているかのどちらかになります。(ピースの4方向に出っ張りがある場合、出っ張りに外接する四角形が計算されてしまうため、45度傾いてしまいます)
・ピースの出っ張り・へこみではなく、ピースの四隅を探します。見つからない場合は、45度画像を回転させてもう一度探します。
LaplacianフィルタCannyフィルタをかければ四隅を検出できそうです)
 ・四隅がわかれば、ピースの輪郭を上下左右の4つに分けて、輪郭の区分と出っ張り・へこみの位置、大きさを計算します。これが輪郭の識別子となります。


 ・輪郭が直線の場合はコーナーピースもしくはラインピースになるので、コーナーピースの場合は下と右が直線部分になるように回転させます。
 ・ラインピースは下が直線部分になるように回転させます。


ここまでで、各ピースは整列され、上下左右の輪郭がどんな種類なのかが決まります。




あとはこの情報を元にマッチングさせていきます。


マッチング
1.四隅のピースのうち、どれか1つを適当に選び、完成図の左上(XY座標にすると0,0)に配置します。
2.  配置したピースの右(1,0)にはラインピースが必ず来るので、右に来るラインピースを探します。
3.さらにもうひとつ右(2,0)のラインピース、その隣のラインピース(3,0)と探していきます。
4.いつかは四隅の残り3ピースのうちのどれかに隣り合うので、四隅のピースになったらピースの探す方向を変えます。(右に探していた場合は下、下に探していた場合は左、左に探していたら上)
5.ラインピースと四隅のピースで配置されていないものがなくなれば、一番外側のピースが完成したことになります。
6.その先も同じように、左上から螺旋を描くように埋めていけばできあがる・・・かも。


本家と違うところは、ピースを探すときに人間の手を借りる、というところです。
たとえば、ピースの左側がへこんでいるピースはたくさんあるので、その中の候補を順番に表示させていき、人間に「当てはまる」「当てはまらない」と判断してもらいます。
この辺がセミオートな理由。セミオートが完成したらフルオートにも挑戦します。




完成までは結構時間がかかりそうな感じではありますが、
とりあえず今週末でピースの切り分けと分類までやってみようと思います。


ではまた。

1 件のコメント:

  1. いま、自分がやろうとしていることとほぼ同じ記事にたどり着けてとてもうれしく思っています。ぜひ、フルオートVer.ができることを期待してます。頑張ってください。

    返信削除