「誰の顔でも作れる「ジガゾーパズル」が面白いらしい」記事へのコメント

グラデーションパーツ

[Anonymous Coward]

ありきたりな商品企画の発想だと白・黒・グレーのベタ塗りパーツのみの構成になりそうなものだけど、
グラデーションパーツの存在が、完成状態をそれらしく見せるのにかなり貢献している気がします。
どうやって着想したんだろうか。

Re:グラデーションパーツ

[dustcatcher (19652)]

本家のコメント
http://entertainment.slashdot.org/comments.pl?sid=1474488&cid=30396686 [slashdot.org]
がビンゴなのではと思います。JPEGと同じように120x160の画像を8x8のチャンクにしてそれぞれをcosine gradientで近似するとちょうど15x20ピースになるということです。
おそらく核の部分はそのままJPEGのアルゴリズムを使っているのではないでしょうか？
そうだとしても，それに着目したアイデアはすごいですね。

Re:グラデーションパーツ

[taka2 (14791)]

> JPEGと同じように120x160の画像を8x8のチャンクにしてそれぞれをcosine gradientで近似するとちょうど15x20ピースになるということです。

いや、細かいとこを見るとJPEGと全然違うというか「JPEG アルゴリズムを使う」なんてオーバースペックもいいとこですよ。

ジガゾーパズルのピースには、白黒を繰り返すようなピースはありません。四隅の色から、内部は単純に線形補間している感じです。 [nifty.com]

一方、JPEGの基本となるDCTの基底テーブル [iwate-u.ac.jp]を見れば分かりますが、DCTの基底は、基本的に白と黒を何度か繰り返してます。繰り返しが無いのは、DC成分(一番左上)の右隣と下隣の2つだけ。
つまり、DCTを応用するとなると、この2つの8x8の64のパターンのうち、2パターンだけを使ってピースを表現するってことになります。
そんなことのためにわざわざDCTを処理しなくても、画像を30x40に縮小して、それを15x20の「2×2ピクセルなブロック」に分けて考え、その四色をピース四隅の色に対応させるって処理で十分。

処理の流れとしてはこんな感じかな?

1. 画像解像度を30x40に縮小する
2. 画像のコントラスト正規化、ヒストグラム平滑化を行う
3. (2x2ピクセルで構成される)各ブロックをピースに割り当てていく。
　ピースの種類が有限なため、誤差が最小になるように最適化問題を解く。

この3の処理は、JPEG圧縮よりも「パレットを割り当てて誤差拡散で減色する」処理の方が近いような気がします。

Re:グラデーションパーツ

[dustcatcher (19652)]

おー、ほんとですね。ピース内の濃淡の繰り返しは全くないのですね。
参考になりました。
…となると、うまくやればもっと良いパズルを作ることもできそうですね。
アイデアもいろいろわいてきます。

Re:

[Anonymous Coward]

通常はパレットの種類だけの制限だけど（例えば16色のうちならどの色を
何回使っても良い）、この場合は使用回数に制限がありますね。

Re:

[Anonymous Coward]

> 画像を30x40に縮小して、それを15x20の「2×2ピクセルなブロック」に分けて考え、その四色をピース四隅の色に対応させるって処理で十分。

ピクセルベースの発想ではなく、輝度勾配でマッチングさせているように思える。つまり輪郭をピースで書いている。
(たいした根拠なし)