Problem 287 「4分木符号化(シンプルな圧縮アルゴリズム)」

4分木による符号化を用いて, 2&sup{N};×2&sup{N}; の白黒の画像を(0 と 1 の)ビット列で表すことができる. このビット列は左から右へ以下のようにして解読する:

下の 4×4 の画像について考える(色のついた印はどこで分割が起こるかを表す)

p287_quadtree.gif

この画像はいくつかの文字列で表すことができる, 例えば:
"001010101001011111011010101010" は長さ 30 であり, または
"0100101111101110", は長さ 16 であり, これはこの画像を表す最短のビット列である.

正の整数 N に対し, D&sub{N}; を次の条件を満たす 2&sup{N};×2&sup{N}; の画像と定義する:

D&sub{24}; を表す最短のビット列の長さを求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-04-10 (土) 18:14:16