計測自動制御学会東北支部 第 211 回研究集会 (2003.10.11)
資料番号 211-15

MDL基準を用いた３次元形状の記述手法
A Method For 3D Shape Description Based On MDL Criterion○萩野谷紀行 ∗ ，古閑敏夫 ∗，本谷秀堅 ∗○ Toshiyuki Haginoya∗ ，Toshio Koga∗ ，Hidekata Hontani∗*山形大学*Yamagata University
キーワード : MDL 基準 (Minimum Description Length Criterion)，階層構造 (Hierarchical Structure)，
ノイズレベル (Noise Level)，記述長 (Description Length)

連絡先 : 〒 992-0038 米沢市城南５丁目山形大学大学院

理工学研究科

電子情報工学専攻

萩野谷紀行，E-mail: g02565@dipfr.dip.yz.yamagata-u.ac.jp

1.

はじめに局所的形状に基づく細部の比較までを効率良く行うことが不可欠である．

Fig. 1 のようなレンジデータについて考えた時，主に二つの捉え方があるように思われる，一つは細かい階段状，もう一つは斜め一枚の平面であるというものである．前者は，このデータの局所的構造に，後者は大局的構造に注目した捉え方に他ならない．この対象の捉え方を総じたものが階層構造である．本稿ではこの階層構造の抽出にMDL原理 (Minimum Description Length principle) を応

Fig. 1

大局的には斜め１枚の平面，局所的には用する．
提案手法はMDL原理を形状特徴の抽出へと応用

階段状と捉えることのできるレンジデータの例することにより，特徴抽出に本質的な閾値を人手
本稿では物体の３次元形状の階層構造を記述する手法を提案する．ここでいう階層構造の記述とは，物体の形状特徴を大局的構造から局所的構造に至るまで，大きさの違いに基づき陽に区別して表現したものである．人間の視覚系のように多種により調整することなく，階層の数を自動的に決定し各階層における形状を記述する．特徴抽出に本質的な閾値を物体自身のみに基づき決定できるため，多種多様な物体形状を記述することを可能としている．

多様な物体を認識するビジョンシステムを実現するためには，大局的構造に基づいた大分類 から，–1–

MDL原理とは，データをモデルとそのモデルからの偏差を用いて記述したとき，その記述長が最できるのである

小となるときが最良の記述で，そのときのモデルの形状がデータにおいて本質的構造であるとする

2.2

３次元データの記述長考え方である．大局的な形状特徴は，細かな局所Z的形状を抑制することにより抽出される．ここで，range finder

どの程度の大きさの形までを「局所的」とみなし無視するかを定める量を，ノイズレベルと呼ぶことにする．ノイズレベルを定めると，MDL原理に基づき，形状モデルが一つ選択される．ノイズレ
ベルを連続的に大きくしていくことにより，次第に大局的形状を記述するモデルが選択されること，YX

また，選択されるモデルは離散的にしか変化しないことを実験により確認した．実際に本手法を３次元レンジデータに応用し物体の３次元形状の階Fig. 2 X-Y 平面は撮影面に並行で，Z 軸は撮影面に直行する層構造を記述した結果も示す．

Fig. 2 のような座標系を考え，３次元データの2.

提案手法の原理

2.1

MDL 原理記述長を考える．
仮に，C画素 ×D 画素×E階調の３次元空間(M =C × D × E) であったとすると，この時，この空間

まず，記述長とは，ある与えられたデータに対内の１点はlog2 (M )[bit] で記述できる．また，デーし何らかのモデルを仮定し，データをそのモデルタの総数を n0 とし，モデルの平面数を n，その空との偏差で記述したときの符号の数である．

間内に存在する平面の最大枚数をNmax ，データのそして MDL 原理とは，モデル自身の記述，モデルとデータの偏差の記述，また，モデルと偏差か内，偏差で記述されるものの数を m0 ，偏差 e の生起確率を p(e)，とするとその記述長はらデータを復元するために必要な最低限の記述の全てを合わせた物の記述長に関して，その長さを記述長=評価基準のMDL基準とし，その記述長は短い程良+いとする．

+MDL 原理によれば，この基準に基づいて様々なlog2 (Nmax ) + n · 3 log2 (M )
1m0 × log2 (C × D) + log2+ log2 (n)p(e)(n0 − m0 ) · log2 (M )モデルを評価し選択することで得られるモデル，となる．単位は [bit] である．(1)式について，第つまり，記述長を最小とするようなモデルこそが，１項は，上で仮定された平面の枚数は既知である

その捉え方で見出されるデータに内在する構造をと言う仮定より生じる項である．この項の存在に最も良く説明する最良の解であるということがでより我々は，解の探索を行う際にこの枚数以下のきる．2)モデルを仮定すれば良いことになる．しかし，こMDL 原理を用いることで，例えば Fig.1 についの項は，常に一定となるので記述長の比較に関して，細かい階段状，あるいは，斜め１枚の平面等て影響しない．そのため記述長を実際に計算すると主張することに関して，その根拠を得ることが–2–(1)場合には省略する．1

によって記述されるデータの数を引いたものとな

第２項はモデル平面数 n 枚を記述するのに必要るので，(n0 − m0 ) となり，そのデータは前述の通な，記述長である．この空間上の１点を表すのにり独立に，直接記述するためその記述長はlog2 (M )必要な記述長はlog2 (M )である，そして，１枚の平となるので，まとめて，(n0 −m0 )·log2 (M ) となる．

面を表すのに３点が必要であるのでその記述長は3 · log2 (M )となり，それがn枚あるので3n · log2 (M )2.3となる．

階層性の抽出

前節で述べた記述長に関して偏差 e の生起確率

第３項はモデルとの偏差によって記述する場合の記述長である．

を p(e) としたが，偏差の記述長の期待値を最小とするためにp としてガウス分布を考える．そして，偏差の記述長について考えると，データをそのまま空間上の１点として記述するのに必要な記述長は log2 M である．もし偏差の記述長が，この値どの程度の大きさまでの形状特徴を無視するかを，ノイズレベルつまりガウス分布の分散値によって操作する．2より大きくなるなら，その点はそのまま空間上の１点として記述した方が良い事になる．つまり，モデル平面との偏差で記述されるのはその記述長がlog2 M より小さいときである Fig. 3

Fig. 1 について具体的に考えてみると，抽出したい形状は局所的にはFig. 4 ，大局的にはFig. 5 のようなものである．ガウス分布の分散値つまり，ノイズレベルを操作することで，階層構造を抽出すoutsideることを考えてみる．

model planeerror

error range

Fig. 3X-Y 平面は撮影面に並行で，Z 軸は撮影面に直行するここで，m0 は偏差によって記述されるべきデータの数である．まず，はじめのlog2 C × D は X-Y平面でのデータ１点を指定するのに必要な記述長で1はその指定されたデータのz 方ある．次のlog2 p(e)Fig. 4 局所的な特徴を記述するモデル，５段の階段が５枚の平面各々と重なる部分との偏差で記述されるようなモデル．

向の値とモデルとの偏差を e とし，その偏差 e が確率密度関数 p(e) に従うものとした時の記述長であガウス分布の分散値に対する記述長の変化を示る．最後は，その偏差が n 枚のモデル平面のうち，したものがFig. 6 である，これを見れば分かるようどのモデル平面との偏差であるかということを指に分散値を大きくしていくと，偏差が大きくなっ定するために必要な記述長である．ても記述長はあまり長くならない．これはノイズ第４項はモデルとの偏差で記述しない場合の記レベルを大きくすると，より大きい偏差までを許述長であり，その数は当然データの総数から，偏差容するということであり，細かい構造を無視する

1 実際には平面の枚数は MDL によって自動的に決定可能でことに対応する．逆に分散値を小さい値にすると，あり，その場合この記述長を考える必要はない．

–3–

2 以下ノイズレベルと分散値読み替えて差し支えない

のとき記述長が最小となることが保証されるのである．つまり，記述長によって自動的に最良なモデルの枚数が決定可能である．

123Fig. 5

大局的な特徴を記述するモデル，５段の階段が１枚の平面との偏差で記述されるようなモデル．
偏差が大きくなると記述長が非常に長くなる．このことはノイズレベルを小さくすると，小さい偏差しか許容されないということになる．つまり，分Fig. 6 Gauss 分布を考えたときの偏差の記述長，偏差が大きい程記述長は長くなる．図中の数字は対応するグラフの分散値を表す．

散の値が小さいときには，Fig. 4 のようにデータ全てがぴったりと接するようなモデルが必要となり，分散の値が大きいと Fig. 5 のような大きな偏2.4差が発生するようなモデルの方が選択されるようになる．分散の値を連続的に大きくしていくとある値で Fig. 4 のようなモデルの記述長と Fig. 5 のようなモデルとの記述長の交点が生じる．この交点の前後でモデルが Fig. 4 と Fig. 5 のようなものとで切り替わるため，モデルの変化は離散的におアルゴリズム解を求めるアルゴリズムとして，多峰性のある問題に対して有効であり，最小単位であるモデルの組み合わせで最良の解が構成できるため，GAの交叉という操作が有効に機能し得るなどの理由から，ここではGA(Genetic Algorithms，遺伝的アルゴリズム) を用いた．1)

こる．
次にモデルの枚数について考えてみる．ある値にノイズレベルを設定すると，モデルが選択され3.

実験結果

る．ここで Fig. 4 のようなモデルが選択されたとデータとしてFig. 1 を考える．この空間は，縦５する，このとき，このデータの記述にとって最良０画素，横５０画素，画素値 (高さ) ２５６階調のななモデル(平面)の枚数は５枚である．もし，ここ空間である．そこに幅１０画素，奥行き５０画素に１枚モデルが増えても偏差の記述長にはほとんの平面が，画素値０から画素値３０の段差を持っど影響を与えない，しかし，モデルが１枚増えるて画素値１２０まで，５枚存在している．

ことで，モデル自身の記述長が増えてしまう．また枚数が４枚に減った場合，５段の段のうち一つ3.1は偏差が非常に大きくなってしまうため，モデル自身の記述長は短くなるが，それ以上に偏差の記述長が長くなってしまう．よって，この場合５枚分散を小さく見積り局所的構造に注目する

ここで，分散の値を十分に小さい値，具体的には段差は段差と見なし，ノイズはノイズと見なす–4–

デル平面ごとに色分けしたものを次に図 7 としてTable 1関係

分散１のときの平面 の枚数と記述長の示す．

平面数

記述長 (noise 無し)

記述長 (noise 有り)-[bit][bit]

12344940.01
42660.75
40758.93

45277.73
43362.0741925.76

456739102.22
37627.78
38343.23
38957.08

40907.02
39821.9940417.96
40848.02

Fig. 7

分散１で得られた構造，５枚の平面で記述されている程度の値とすればMDL原理により局所的構造を表散を１として，モデル平面の枚数を１枚から７枚分散を大きく見積り大局的構造に注目するまでの各々について記述長を最小とするようなモ

次に，分散の値を十分に大きい値，具体的にはすモデルが選択されるはずである．具体的には分デルを探した．

3.2

段差もノイズもノイズと見なしてしまうような値

以下に，１枚から５枚まで最終的に得られたモとすれば大局的構造を表すモデルが選択されるはデル平面を各々original dataとともにFig. 8 に，まずである．具体的には分散を１０として，モデルた，各々の場合の記述長を Table. 1 に示す．

平面の枚数を１枚から５枚までの各々について記

次に，データに分散１のGaussian noiseを付加し述長を最小とするようなモデルを探した．て同様の実験を行った．その結果見つかった，平以下に，１枚から５枚まで最終的に得られたモ面を original data とともに，Fig. 9 に，また，各々デル平面を各々original dataとともにFig. 10 に，まの記述長を Table. 1 に示す．

た，各々の場合の記述長を Table. 2 に示す．

得られたモデル平面は，予想した通りノイズが次に，データに分散１のGaussian noiseを付加し有る場合でも無い場合でも水平な平面で見つかって同様の実験を行った．その結果見つかった，平ている．Table. 1 ，より記述長もモデル平面数が面をoriginal dataとともに，Fig 11 に，また，各々１枚から５枚へと増えるに従い短くなり，５枚かの記述長を Table. 2 に示す．

らは増えるごとに長くなる．つまり，分散１では，得られたモデル平面は，予想した通りノイズがモデル平面５枚が original data の５枚の平面各々有る場合でも無い場合でも斜めの平面で見つかっと重なるようなモデルが最も良い物であると言うている．Table 2 より記述長も５枚から１枚へと減ことができる．つまりこれは，分散１と言う捉えるに従い短くなっている．つまり，分散１０では，方で original data を見ると言うことは，５段の階モデル平面１枚がoriginal dataの５枚の平面各々の段上の構造として見ていると言うことである．こX 方向の中心を貫くようなモデルが最も良い物でれは，このデータについての，局所的構造が５段あるということができる．つまりこれは，分散１の階段状の構造であるということを表していると０という捉え方で original data を見るということもいうことができる．最終的に得られた構造をモが，斜め１枚の平面として捉えることに他ならな–5–

Table 2関係

分散１０のときの平面の枚数と記述長の平面数

記述長 (noise 無し)

記述長 (noise 有り)-[bit][bit]

12
341184.45
42795.34
44137.20

41190.1042789.19
44137.424545205.22
46019.58

45170.18
46012.58

い．この立場では，もはや，original data 中の段差はただのノイズに過ぎないということができる．

4.

おわりに以上の結果より，ノイズレベルを操作することで３次元レンジデータからデータに固有な階層構造全てを自動的に決定できることを示した．また，ノイズレベルを連続的に大きくしていくとき次第に大局的形状を記述するモデルが選択されることが確認され，さらに，選択されるモデルは離散的にしか変化しないことが以上の実験により分かった．
本稿の中では記述長に関してモデルとの偏差で記述するより，データをそのまま記述する方が記述長が短くなるとき，データをそのまま記述するとしていたが，考える空間が本稿においては必要な形状が含まれる最低限の空間しか考えていない
ため，固定長の記述長を短く見積もりすぎている事になり直観にそぐわない形状が抽出される場合のあることを確認している，今後この点についてさらに検討していきたいと考えている．

参考文献
1) 窪田 進，出口 光一郎，最小記述長原理に基づく輪郭線図形の記述と認識について，画像の認識・理解のシンポジウム(MIRU ’94)pp.I-249-I-256 (1994)
2) 韓 太舜，小林風館 (1999)

欣吾，情報と符号化の数理，培3) 山西太舜，MDL入門：情報理論の立場

健司，韓–6–から，人工知能学会誌，Vol.7，No.3，pp.427-434(1992) May

4) 長尾 淳平，韓 太舜，かく乱母数を含む場合のMDL基準の構築と空間図形モデル推定問題への応用，電子情報通信学会論文誌，A Vol.J83-A No.1
pp.83-95 (2000)

Fig. 8 分散１で１枚から５枚までそれぞれで見つかったモデル平面 (noise 無し)，上から１枚，２枚，３枚，４枚，５枚

Fig. 9 分散１で１枚から５枚までそれぞれで見つかったモデル平面 (noise 有り)，上から１枚，２枚，３枚，４枚，５枚–7–Fig. 10 分散１０で１枚から５枚までそれぞれで見つかったモデル平面 (noise 無し), 上から１枚，２枚，３枚，４枚，５枚

Fig. 11 分散１０で１枚から５枚までそれぞれで見つかったモデル平面 (noise 有り), 上から１枚，２枚，３枚，４枚，５枚–8–