空間充填曲線と画像処理応用

全文

(1)2004−CG−117 (5) 2004／11／26. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 空間充填曲線と画像処理応用鎌田清一郎早稲田大学大学院情報生産システム研究科あらましペアノは

(2) 年『平面領域内の全ての点を通過するような曲線』を発見しその存在を明らかにした現在線分を単位超立方体全体へ移すこのような連続曲線は空間充填曲線あるいはペアノ曲線と呼ばれている空間充填曲線の中で応用研究の最も多い曲線はヒルベルト曲線である例えばヒルベルト曲線の応用としては画像圧縮スペクトル画像分類データベース情報検索計算機ホログラムなど様々な分野に及ぶ本論文では空間充填曲線について定義とつの例を紹介し次にヒルベルト曲線を中心とした画像処理への応用研究を幾つか概観する.

(3) . .

(4)

(5) .

(6) . . ! . "# $% &' . (. ! ! # . )! . &'* ! # +# . # % ! ! . (. &' !. &' " +# . . はじめに. 工学的には無数に存在するような平面内の点を. カントール在』を発見し数学会を驚かせたしかしネットはこの写像が必ず不連続となることを証明したのであるその結果数学者の関心は連続素朴的集合論を提唱した. は，『線分上の点と正方形内の点との対対応の存. . 考える必要がないので有限個の点を辿る曲線を考. . . えればよい空間充填曲線の中で応用研究の最も. . 多い曲線はヒルベルト曲線である例えば. % 次元. となる全射写像が存在するかという点に移っていっ. のように画像の空間 & 分割表現になっているしたがってこの場合ヒルベルト曲線に沿った画像走査ヒルベルト走査順の & 分木表現を用いて画像を表現するまたヒ. た一般にある区間から平面への連続写像が曲線. ルベルト走査により画像の１次元データが得られる. と呼ばれることからこの問題は『平面領域内の全. がこの周波数スペクトルを見るとラスタ走査よ. . . . ての点を通過するような曲線は存在するのか？』ということになる. . これに対し. ペアノ . ! 年この曲線を発見しその存在を明らかにした "#$ 現在線分を単位超立方体全体へ移すこのような連続曲線は空間充填曲線あるいはペアノ曲線と呼ばれている. は. の場合のヒルベルト曲線は図. . . り低域にエネルギーがより集中することがわかる. . この近傍保存性の良さから画像圧縮に利用した研究. . . . が数多くなされている本論文ではまず空間充. 線シェルピンスキー曲線の例を紹介し次にその画像処理の応用研究を幾つか概観する. 填曲線についての定義とヒルベルト曲線ペアノ曲. −25−.

(7) . 空間充填曲線. 空間充填曲線の定義. . 本節では空間充填曲線の定義について述べるま. . ず順像を定義定義 . に示す. が次元ユークリッド空間. の部分内へ. 図. 集合から次元ユークリッド空間の関数であれば. ある . による. 次に定義定義. における. ' . . を. . . . の順像と呼ぶここで. . は各々関数. の定義域および値域で図. を用いて曲線を次のように定義する. ( . . が連続であるときその像を曲線と呼ぶまた. . . を曲線. ' . . . . ' の媒介変数表示と呼ぶ. と定義 % より空間充填曲線を表す連続写は次のように定義される. 定義像. (

(8) % が連続かつであればは空間充填曲線と呼ばれる. 定義 . で述べたようにこれは全射写像ではあるが全単射写像ではないつまり空間充填曲線は重複点媒介変数の相異なる値に対応する同一の点が無数にあることも許されるとして作った曲線である従って重複点を含まないジョルダン曲線単純閉曲線は空間充填曲線になりえないことが分かる % 次元の場合を例にとれば空間充填曲線とはユークリッド平面上の連続曲線すなわち線分 ' "! $ からへの連続写像による像で正方形全体をうめつくすものであるこれは像が正のジョルダン測度 % 次元であれば面積 ) 次元であれば体積に相当する量をもつ連続写像と言い替えることができるただし. . . ( ヒルベルト曲線の例. が空間充填曲線を生成するならば前節. %( ペアノの空間充填曲線. ' "! $ から ' "! $ への写像を以下のように定義しこれが連続な全射写像であることを示した ! ! ' ! ここではを回繰り返し適用することを意味するこれがペアノが発見した空間充填曲線であるしかし ! 年のペアノの論文では，この解. を使い. 析的な表現に対する幾何学的な解釈は与えていなかった. * ムーア +. の言葉を借りると. 「曲面充填曲線の現象を幾何的なイメージとして明. , ヒルベル. らかにしたのはヒルベルトであった」. トは初めて空間充填曲線をつくり出す幾何的な生成. "&$ 彼によって示された空間充填曲線を図に示すこの曲線がヒルベルト曲線と呼ばれる空間充填曲線であるさらに彼は式に示されるペアノの空間充填曲線に対する幾何的解釈を与えているその曲線は図 % に示されるものであるこの他にも図 ) に示されるようなシェルピンスキーにより示された空間充填曲線があるこれまでに ) つの空間充填曲線の例を示したが共通する性質として次の性質があげられる手順を示したのである. 性質上述の三つの曲線の座標関数はいずれもいたるところ微分不可能である. 空間充填曲線の例. ペアノは演算子 . ' % ' ! %. . , ヒルベルトの言葉を借りればこれらの写像は「いたるところ連続で同時にいたるところ微分不可能な写像の簡単な例」であるこれ以外. ここで. % −26−.

(9) 0101 0111 1101 1111. 01 11. 0100 0110 1100 1110 0001 0011 1001 1011. 図. 00 10. 0000 0010 1000 1010. (a). (b). )( シェルピンスキーの空間充填曲線図. . にもいくつかの空間充填曲線が存在するがここで. . . は省略する参考文献. . "&$. &( ４分割領域のアドレス割当. γ=1. γ=2. γ=3. γ=4. 画像処理応用. # 年以降急速に多く例にとると画像圧縮スペクトル画像分類データベース情報検索計算機ホログラムなどへの応用がある "- $ 画像処理への応用研究は. なっており様々な分野に及ぶヒルベルト曲線を. 画像走査. . 図. #( 分割領域の走査パターン. . . 空間充填曲線の計算方法は応用数学の分野で主. 号である各分割領域でのアドレスと曲線番号は. として研究されてきた本節では画像を空間充填. 分割前の領域の走査パターン分割後の４領域の接. . 曲線に沿って走査することを考え画像走査として. . . . 続情報と分割領域での走査の順番何番目に走査. テーブル化しておき必要な情報を逐次参照し再. のヒルベルト走査と一般化ヒルベルト走査を紹介. する画素かを示す順序情報から決定できるそこ. する. でこの２つの情報アドレスと走査順序を予め. . ヒルベルト走査. 帰的な計算を除去するのがルックアップテーブル参. 次元のヒルベルト曲線を生成するアルゴリズ. ./ の方法 ")$ と 01 の方法 "2$ の % 種類のみがあったしかし 3 "!$ は. ムは. グレイコードの概念を用いた新たなアルゴリズムを. . . . . "

(10) $" $ は. 番とするとアドレス参照用のターミナルテーブル. "$ ' "!! ! !$ "%$ ' "!! ! !$ ")$ ' " ! !! !$ "&$ ' " ! !! !$. 見い出したこれは従来の２種類の方法よりも高. % 次元正方形領域を対象とし % 種類のルックアップテーブルターミナルテーブルインダクションテーブルを利用した非再帰的なヒルベルト走査 "# 2$ について簡単に述べるサイズ % % の正方形領域に対し図 & に示すようなアドレス割当を行なう図 & では４分割後の領域に対して左下 !! 左上 ! 右下 ! 左上のアドレスを割り当てる２回目の４分割後のアドレス割当は同図 4 のように下位２ビットが付加される従って回の分割操作後のの画素のアドレスは % ビットの２進数表現によって表すことができるまた分割後の走査パターンとしては図 # に示す & 種類を考えるここで

(11) は曲線番. . 照による計算法の基本的な考え方である

(12) を回分割時の曲線番号を回分割時の走査の順. . 速計算が可能である本項では. "

(13) $" $ は次のようになる "$ ' "% &$ "%$ ' " % % )$ ")$ ' "& ) ) %$ "&$ ' ") & & $. となり曲線番号参照用のインダクションテーブル. . ルックアップテーブル参照によるヒルベルト曲線生成の具体的アルゴリズムは次のようになる. ) −27−. .

(14) O. E. E. 01. 11. 010. 110. 011. 111. 0011 0111 1011 1111. 00. 10. 001. 101. 010. 110. 0010 0110 1010 1110. 2 x 2 (p = 1). 000. 100. 001. 101. 0001 0101 1001 1101. 000. 100. 0000 0100 1000 1100. 2 x 3 (p = 2). E. 2 x 4 (p = 3). O2. E2. 001 000. E1. 図. E2. E1. 0010 0110 1010 1011. 010. 100. 110. 0001 0101 1001 1101. 2( 長方形領域の分割規則. (p = 4). 図. (p = 6). 0000 0100 1000 1100. (p = 5). -( 2 種類の長方形プレート . ように偶数長と偶数長の辺で分割 . . 奇数長の辺：分割点が中点に最も近くなる. . ように奇数長を偶数長の辺で分割 . . % の線分は回の % 分割により辺長の % 個の線分に分割されるこのことから線辺長 . 分長が. "!$ を参照されたい. 一般化ヒルベルト走査. . 本項ではヒルベルト曲線の走査領域を超立方体領域から超直方体領域に拡張した一般化ヒルベルト. "%$ について紹介するただし次元の場合は説明が複雑になるので % 次元の場合について簡単に説明する長方形領域へ拡張した擬似ヒルベルト走査は分割及びその後の連結が図 2 8 は各辺における画素数が各々偶数及び奇数個であることを表すに示す形式に従うものとするこれは次のような分割規則である走査. . 111. 4 x 3. 次元空間における具体的なアルゴリズムは文. . 101. E2. * 455

(15)

(16) ' % ) & ' "

(17) $" $6

(18) ' "

(19) $" $6

(20) ' % ) & ' "

(21) $" $6

(22) ' "

(23) $" $6

(24) ' % ) & ' "

(25) $"$6

(26) ' "

(27) $"$6

(28) ' % ) & ' "

(29) $" $6

(30) ' "

(31) $" $6

(32) ' % ) & ' "

(33) $"$6. 7 6 献. 011. 4 x 2. E1. E1. 4 x 4. 偶数長の辺：分割点が中点に最も近くなる. % % & % であれば回の % 分割の結果は線分長 % ) & の組合せから成る % 個の線分に分割される縦横の線分長において % % & % % % % & % を満たす長方形領域では回の & 分割の結果 % ) & の線分長をもつ 2 種類の長方形プレート図参照が生成されることが分かるそこで図 - に示すアドレス割当を行ない各アドレスをプレート毎のターミナルテーブル "$"

(34) $"$ に格納する例えば "$"$"$ ' !! ")$"$"$ ' !! のように参照するここでは長方形プレート番号であるしたがって正方形の場合と同様の & 分割操作を回行なった後にプレート毎のターミナルテーブルによるアドレス割当を加えることで長方形領域に対応したアドレス割当が可能となる . 画像圧縮応用. 9 %!!! や + & などに代表される画像圧縮技術には ,: あるいはウェーブレット変換などの変換符号化が主流である空間充填曲線の画像圧縮への応用研究は ! 年代後半から論文発表が多くなり空間充填曲線をその要素. & −28−. 国際標準化された.

(35) 技術へ適用するための試みがいくつかなされてい. . . た本節では可逆圧縮と非可逆圧縮に分けて説明する. . 可逆圧縮手法静止画像の可逆圧縮では. ;7 < "%$ が. 最初にヒルベルト曲線の応用を理論的に検討したのである. . また. + ")$ は予測符号化に. 空間充填曲線を適用した場合の圧縮効率について理. . . 論的に検討した近年小林他. . "$ は走査方法に. 着目し予めテンプレートとして与えられた複数の走査法を利用して予測符号化を改良した新たな可逆. 画像を対象とし図のように，画像を複数の領域. 図. 圧縮手法を提案したこれは人工画像を含む静止. （例えば，正方形領域）に分割し，各領域において画像の性質に見合った走査方法を適応的に見つけて効率的な画像圧縮を行うものである．国際標準化方. 9 9 5; 9 %!!! の可逆圧縮方式と比較し実時間処理でこれらの圧縮性能を上回る結果を得た式. . ある近年コンピュータグラフィックスへの応用. 非可逆圧縮手法. 静止画像の非可逆圧縮では. "$ が. ) 次元ヒルベルト曲線を用いてカラー画像圧縮への適用を検討したヒルベルト走査等により画像の１次元データが得られるがその周波数スペクトルを見るとラスタ走査より低域にエネルギーがより集中することがわかるこの近傍保存性の良さから非可逆圧縮への応用研究が盛んになったのである. " $. このような立場からの論文発表が数多くあ. るのでここでは省略する. . 動画像の非可逆圧縮では. "-$ が. 可変ブロックサイズのブロックマッチングによる動き推定にヒルベルト走査に基づく４分木表現を利用. . = " $ は動き推定におけるブロックマッチングをヒルベルト走査後の次元系列に対して行う方式を検討したがいずれも動き補償の計算量削減が目的であるしたまた. まとめ本論文では空間充填曲線について定義とペアノ. . . ヒルベルトシェルピンスキーらによる空間充填曲. 幾つか概観した空間充填曲線はフラクタルと同じように扱われるが数学的には全く異なった概念で線の例を紹介し次にその画像処理への応用研究を. . 研究が多くなっておりこれらについても今後研究報告としてまとめる予定である. . 謝辞. . . 本論で紹介した研究の一部は財団法人北九州産業学術推進機構（. . . . ( 走査方法に着目した画像圧縮. >? ）のヒューマンテクノクラ. スター推進センターの研究プロジェクトの援助を受. . けたここに感謝の意を表す. . 参考文献. "$ 坂東幸浩西修功鎌田清一郎 @ヒルベルト走査を用いた時空間領域分割による高速動画像圧縮法映像情報メディア学会誌 . A & 77 ## B#2& "%$ 坂東幸浩鎌田清一郎 @ 次元空間における一般化ヒルベルト走査の一計算法A 電子情報通信学会論文誌 ? C % 77 )2B ) %!!! ")$ ?D ./@ = E * 4F 7 G = A

(36)

(37)

(38)

(39) 77 %B&2 2 "&$ , * 4 @H 4 = ?44 = ;

(40) > H HIA 77 &# B&2! "#$ 鎌田清一郎ペレス・アーノルフォ河口英二 @% ) 次元空間におけるヒルベルト曲線の一計算法A 電子情報通信学会論文誌 ,5

(41) 77 %-B%%2 "2$ 3 D8 3E= @? 7

(42) * 4 = 5 = 77 75. # −29−.

(43) A

(44)

(45) & 77 &%!B&% ) "-$ 鎌田清一郎新見道治河口英二( @ヒルベルト曲線を利用した多次元画像の対話型解析法A 電子情報通信学会論文誌 ,5 .

(46) - 77 %##B%2& & "$ 鎌田清一郎 @ヒルベルト走査を利用した濃淡画像の情報圧縮に関する考察A 電子情報通信学会論文誌 ,5

(47) % 77 &%2B &)) - " $ 3 J . A. 5 = 7 = * 4 A . " $ = J = J 3 * A ? 4 I = =

(48) A ) 77 #-#B## .

(49)

(50)

(51)

(52)

(53)

(54)

(55) 77 #-#B#- . "!$ 3 D J . @? E =

(56) B * 4 =A

(57)

(58) - 77 2&B -) "$ 小林正明鎌田清一郎 @複数走査を用いた自然画像の可逆圧縮方法A 電子情報通信学会論文誌 ,5 C

(59) 77 2!)B2% %!!& "%$ ? ;7 9 < @ 7

(60) E 5 A

(61) 77 %B 2 ")$ + , K @8 5 = 1

(62) = = E L 77 A

(63)

(64) "&$ * = @7 G = A

(65)

(66) J & 鎌田清一郎訳 @空間充填曲線とフラクタルA シュプリンガー・フェアラーク東京 "#$ @ 4 1 7 5 7 A ! "2$ 9 01 + . ( @? 7 = = A

(67)

(68) & 77 &!)B&% "-$ + 3== ?3 A ? . 7 E 7 4 5 = = 5 A

(69)

(70) 2 77 &-B#!% - "$ D9 ?> ; >* 5 @+7 7

(71) 5 = = 7 A

(72)

(73) 77 #%!B#%2 ) 2 −30−.

(74)