各ピクセルベクトルをマッチングする

[kawaemon]

No description provided.

[MikuroXina]

案1: 左上の断片画像から始めて, 上下左右に別の断片画像をくっつけて伸ばしながら探索する. ただし, 結合したときに全体の幅と高さが元画像を超えないようにする.

相似な断片画像があった場合でも正しく最短の移動先座標を求める必要アリ

[kawaemon]

左上がどの断片なのか最初わからないので、どれか一つから結合作業をはじめて、最終的に一番左上に来たやつに回転を合わせるしかない...?

[MikuroXina]

@kawaemon 募集要項より,

回転させる角度および断片画像数に制限はなく，各々の断片画像の回転角度に関係性はありません。ただし，問題画像の座標00の断片画像は全体の向きの基準とするため，回転させません。

となっているので, 入力画像における最も左上の断片が向きの基準であるというだけです.

[kawaemon]

問題ミスリードしてました。失礼しました。。。

[MikuroXina]

O((W^2 + H^2 + WH) log WH) のアルゴリズムを思いついたのでメモしておきます.

1. 最初の座標 00 の断片画像から, 縦に H 個の最適な断片画像を探してくっつける. この列の中で座標 00 を置く位置は H 通りあるので, このパターンを探索する. 最適な断片画像を探すには, 予め辺の画素値でソートしておき, 最も近い辺を二分法で探せばよい. O(H^2 log WH)
2. 同じように座標 00 の断片画像から, 横に W 個の最適な断片画像を探してくっつける. O(W^2 log WH)
3. 残りの空いている部分を同様に埋めていく. O(WH log WH)

O((W^2 + H^2 + WH) log WH) は高々 3 * 256 * 8 = 6144 回の計算となり, 十分間に合います.

[MikuroXina]

以下のようなケースで,

A -[近い]- B
|          |
[近い]    [遠い]
|          |
C -[近い]- D

近いと遠いの矛盾を解消するように自動でブラックリストへ追加するといいかもしれません.

[kawaemon]

todo:

• 'F' の undo
• 'F' のビジュアライズ？