7

私は何の役にも立たず、次のようなジグソーパズルで遊んでいました：

代替テキスト http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg

そして、それを組み立てるのを支援するプログラムを作ることができるかどうか疑問に思っていました.

4x3 ピースのような小さなパズルを想像してみてください。しかし、小さなタブとブランクは均一ではありません。ピースごとに、これらのタブの高さ、形状、サイズが異なります。私がやりたいことは、これらすべての部分の写真を撮り、プログラムにそれらを分析させて、それらの属性をどこかに保存することです. 次に、ピースを手に取ったときに、どのピースが「隣り合う」べきかをプログラムに教えてもらうことができます。または、空白を埋める必要がある場合は、必要なパズルのピースがどのようになっているのかを教えてくれます。見る。

残念ながら、私は画像処理とパターン認識について何もしたことがないので、いくつかの指針をお願いしたいと思います -どうすればジグソー ピース(基本的にタブと穴のある四角形)を写真で認識できますか?

次に、適切な位置になるように回転させ、ある程度の比率にスケーリングしてから、両側のタブ/空白を測定し、存在する場合は両側の勾配も測定する必要があります。

1000 ピースのパズルをスキャン/写真撮影して使用するには時間がかかりすぎることはわかっています。

4

2 に答える 2

4

データ収集

(これは、クロマ キー、ブルー スクリーン、または背景色方式として知られています)

  1. 部屋全体の照明の変化が最も少なく、明るい部屋を見つけます。
  2. パズル/絵全体でめったに使用されない色 (色相) を見つけます。
  3. まったく同じ色のカラーペーパーを入手してください。
  4. カラーペーパーに収まる数のパズルピースを置きます。
    • パズルをバッチに分類して、後でコンピューターのヒントとして使用できます。
    • ピース同士が重なったり、触れたりしないように注意してください。
    • オリエンテーションについてはまだ心配しないでください。
  5. 写真を撮ってパソコンにダウンロード。
    • クロマ キーの背景がデジタル カメラの内蔵カラー バランスを崩している可能性があるため、カラー キャリブレーションが必要になる場合があります。

取得データ処理

  1. コンピューター ビジョン ソフトウェアを入手する
    • OpenCV、MATLAB、C++、Java、Python Imaging Library など
  2. 画像上のクロマキーカラーに対して連結成分を実行します。
    • パズルのピースである接続されたコンポーネントの穴の輪郭を尋ねます。
  3. 検出されたリストのエラーを修正します。
  4. 索引語彙を選択し(Ira Baxter の投稿を参照)、ピースを測定します。
    • ピースが長方形の場合は、最初に角を見つけます。
    • ピースがわずかに四角形である場合、辺の長さ (角から角までを測定) も貴重な特徴です。
    • SO、 Google、またはこちらで「Shape Context」を検索してください。
    • 最後に、ピースのカラー ヒストグラムを取得して、後でピースを色別にクエリできるようにします。
  5. それらを検索可能にするには、それらをデータベースに入れて、索引語彙の任意の組み合わせで部分を照会できるようにします。
于 2010-07-03T19:27:26.603 に答える
2

問題自体に戻ります。パズルを組み立てる問題は、ピースが隣の 1 つだけに収まるか、複数に収まるかによって、簡単 (P) または難しい (NP) になる可能性があります。各エッジに 1 つしか適合しない場合は、ピース/サイドごとにその隣を見つけるだけで完了です (O(#pieces*#sides))。一部のピースが異なる隣人に複数の適合を可能にする場合、パズル全体を完成させるためにバックトラックが必要になる場合があります (選択を間違えて行き詰まるため)。

ただし、最初に解決すべき問題は、ピースをどのように表現するかです。任意の形状を表現したい場合は、おそらく透明度またはマスクを使用して、タイルのどの領域が実際にピースの一部であるかを表すことができます。正方形を使用すると、問題がより簡単になる可能性があります。後者の場合、正方形の各辺にあるピクセルの最後の行を考慮し、他のすべての部分で見つかった最も類似したピクセルの行と一致させることができます。

正方形のタイルを使用しているにもかかわらず、2 番目のアプローチを使用して実際のパズルを解くことができます。実際のパズルは通常、NxM グリッドのピースで構築されます。ボックスから画像をスキャンするとき、それを同じ NxM グリッドの正方形タイルに分割し、システムにそれを解決させます。問題は、手に持っている実際のくねくねした部分を、システム内のタイルと視覚的にマッピングすることです (それらが小さく、均一に色付けされている場合)。しかし、内部で任意の形状を表現すると、同じ問題が発生します。

于 2010-06-26T18:03:48.273 に答える