FIT（情報科学技術フォーラム）2002

LA-2
地形図からの最適ピラミッドの構成アルゴリズム
How to reform a terrain into a pyramid
全 眞嬉 ∗
Jinhee Chun

1加藤直樹†
Naoki Katoh

はじめに地形図が与えられた時に、この地形図を近似する最適な「山」を計算する事を考えよう。具体的には、各地点の高度を表す 2 変数関数 ρ(x, y) が与えられた時、これを、単峰関数、即ち極大点を一つだけ持つ関数 f (x, y) で近似する。
本論文では、この問題を一般化し、最適化問題として定式化して考察する。この一般化した問題は、データマイニングや画像処理への応用を持っている。定式化された最適化問題
は 2 変数の場合ですら NP 完全問題となるが、出力関数に制限を与えることにより、様々な場合に効率の良いアルゴリズムを与える。

1.1

図 1: 1 変数最適ピラミッド構築の入力と出力問題の背景画像処理やデータマイニングにおいて、データの分布から特徴部分を切り出す事が重要な問題となる [1, 4, 5]。画像処理において、n × n のピクセルグリッド G 上のグレイスケー
ル画像を考えた時、点 (x, y) が入る画素の濃淡度を ρ(x, y)とすると、画像は 2 変数関数 ρ(x, y) と思うことができる。
画像が背景とオブジェクトの重なりである時、オブジェクト部分を切り取る事を考える。一般の画像切り出しでは、オブジェクトを G の部分領域 R として取り出す。すなわち、出力は、f (x, y) = 1 if (x, y) ∈ R, else 0 という関数 f と思うことができる。 一方、オブジェクトを領域として捉えず、ある良い性質を持った関数 f として捉える試みがファジー
画像処理では行われている [2]。この場合、オブジェクトを領域としてではなく、関数として切り出す必要がある．さらに、データマイニングで領域切り分けを用いて結合ルールの生成を行う試みが福田らによって提案されているが [4]、ここ
では、切り取るものは多次元正規分布のような特徴をもったデータ分布であり、発見したルールを既知ルールとして取り除いて更に解析（さらに小さいルールの発見）を行うためにも，領域として切り取るより、関数として捉える事が望ましい。これはまた、ルールの可視化への助けとなると共に、結合ルールを部品とした決定木の構築 [5] の時、切り出された関数に従って決定を確率的に行うやわらかいシステム構成を可能にし、過学習の回避に用いる事ができると期待される。

2徳山 豪 ∗
Takeshi Tokuyama

図 2: 画像に対する最適ピラミッド

最適ピラミッド構築問題: 領域を値に持つ写像
Ψ : [0, ∞) → F で、単調条件[ Ψ(t) ⊆ Ψ(t ) if t > t ] を満たし、利得の総和∞{ρ(Ψ(t)) − t · µ(Ψ(t))}dt を最大にするもの
t=0を求めよ。
本論文では 1 変数、2 変数の場合の最適ピラミッド構築問
題とその計算時間を述べる。
ピラミッド構築問題の例として、µ が一様分布 µ ≡ 1 である場合で 2 変数の場合、関数 ρ を地形の標高図を思おう。地形で、高さ t で切った図形が Ψ(t) になるものを考えよう。単調条件と F の領域の連結性から、地形は単峰である。 例えば、F が軸方向正方形の集合であれば、ピラミッドのような形になる。この地形の標高を表す関数 fΨ (x) = sup{t : x ∈ Ψ(t)}を考えると、fΨ (x) は高いところから低いところへの土の移動を行なって地形 ρ から構築する事が出来，上記積分の最大
条件は、fΨ (x) の位置ポテンシャル x (fΨ (x))2 dx の最大化に対応する。即ち、できるだけ位置ポテンシャルを失わずに地形を (横断図が F に入るような）単峰地形に変更する問題となる。図 1,2(標高は濃度に対応）にこの場合の例を図示する。
単一の t に対して ρ(R) − t · µ(R) を最大にする R ∈ F を求める問題は特に 2 変数の場合、画像処理やデータマイニングで研究されており、一般の F での NP 困難性と、様々な F での多項式アルゴリズムが知られている [1, 4]。 更問題の定式化

d 次元の立方体 [0, n]d 上の d 変数非負実数値関数の対
ρ(x), µ(x) を考える。領域 R に対し、ρ(R), µ(R) は、R 内での ρ, µ の積分値とする。さらに、立方体を N = nd 個の単位立方体に分割し、ピクセルグリッドを考える。ピクセルグリッドの連結領域の族（ピクセルたちの集まりで出来た領域たち）F を固定する。パラメタ t ≥ 0 に対し、ρ(R) − t · µ(R)を、領域 R ∈ F でのパラメタ t で正規化した（ρ の µ に対する）利得（Gain) と言う。本稿では簡単のため、µ を正値実数値関数、F は空集合を含むと仮定する。
∗ 東北大学大学院情報科学研究科システム情報科学専攻† 京都大学大学院工学研究科建築学専攻

3

FIT（情報科学技術フォーラム）2002
定義 6.1 2 次元ピクセル平面 G = [0, n]2 内で、適当な関数
y = h(x) より真に下にあるピクセル全体の和になっている領域を下半切断領域と呼ぶ。に、この手法をパラメトリックに用いることにより、エントロピー最大化領域切り出しなどの非線形最適化切り出し問題の解法が与えられている。データマイニングでの応用では、µ と ρ は変数に対応する数値属性の組を条件節に持つ数値結合ルールの条件節サポートとルールサポートに対応する。

3

定義 6.2 2 次元ピクセル平面 G = [0, n]2 内の 1 点 p に対し、p を含む長方形たちの和集合を p を中心にする矩形和楕円型領域（rectilinear ellipsoid）と呼ぶ。

閉集合族に対する考察

ある集合族 S が G = [0, n]d の閉集合族であるとは、G ∈S, ∅ ∈ S, [X, Y ∈ S → X ∪ Y ∈ S] かつ [X, Y ∈ S →X ∩ Y ∈ S] である事を言う。

矩形和楕円型領域の族は軸方向楕円の離散化を含む広い領域族であり、指数個の領域を持つ。例として，単調減少関数の下半切断領域は原点を中心とする矩形和楕円型領域となる。

定理 3.1 F が閉集合族であれば、各々の t に対し ρ(R) −t · µ(R) を最大にする領域 R ∈ F を Ψ(t) とすると、Ψ は単調条件を満たし、従って、最適ピラミッドになる。

補題 6.1 下半切断領域全体の集合と、点 p を中心とする矩形和楕円型領域全体の集合は共に閉集合族である。

4

定理 6.1 下半切断領域全体の集合に関する最適ピラミッドは O(N ) （即ち O(n2 )）時間で計算される。連結な下半切断領域全体の集合に関する最適ピラミッドは O(N 3/2 log N )時間で計算される。（証明略）。

1 変数の場合

1 変数の場合、G = [0, n] であり、F として、整数端点を持つ区間全体の集合 I を取ることが自然である。区間族 Iは閉集合族ではない (2 つの区間の和集合は一般に区間ではない）。しかし，ある固定した i ∈ [0, n] を含む区間全体（+空集合）I(i) は閉集合族であり、I に関する最適ピラミッドは、ある I(i) に関する最適ピラミッド (i はピラミッドの頂点に対応する）となる。一方、ρ(I) − t · µ(I) を最適にする区
間 I ∈ I(i) が変化する t をトレースする事は、計算幾何学での凸包上のトレースを (正確には左右 2 つの凸包で）行う計算に対応する [3]。ソートされた点の凸包計算は線形時間でできるので、この手法を用いると、O(n2 ) の時間で I に対する最適ピラミッドを求める事ができる。
更に、i = 0, 1, 2, . . . , n で現れる 2n 個の凸包の上側包た
ちは凸包木 (正確には左右 2 つの凸包木）と呼ばれる O(n)のサイズのデータ構造で表現できる。左右の凸包木でのトレースの順序をプライオリティーキューで管理し、t に関する走査法を用いてピラミッドの頂点の候補の絞込みを行う事
で、O(n log n) 時間で計算可能である。詳細省略。

定理 6.2 指 定 さ れ た 一 点 p を 中 心 と す る 矩 形 和 楕 円型 領域 全 体 の 集 合に 関 す る 最 適ピ ラ ミッド（ 図 2）は 、O(min{N log n log nΓ, N 3/2 log n}) 時間で計算される。ここで Γ は問題の出力精度であり、1/Γ の近似精度で最大な積分値を持つ解が出力される。（従って、Γ が入力精度以上なら最適解を出力する）。
略証: 閉集合族なので、各 t に関して、利得を最大にする領域を求めればよい。これは O(N ) 時間でできる。更に、あるt での最適領域を計算した時に、これが G を領域の内部と外部に分割する。この分割がバランスしている（即ち双方のピクセル数が G のピクセル数の定数フラクション以上）場合には、各部分を独立に、対応する部分に問題を縮小して解ける。従って分割統治が可能である。バランスした分割を与える t を求めるために、2 分探索もしくはパラメトリック探索を用いる事により計算時間を得る。
✷参考文献

定理 4.1 与えられた ρ, µ に対し、I に関する最適ピラミッドは O(n log n) 時間で計算する事ができる。

5[1] T. Asano, D. Chen, N. Katoh, and T. Tokuyama,Eﬃcient Algorithms for Optimization-Based Image
Segmentation, International Journal of Computational Geometry and Applications 11 (2001) 145-166.

小さい領域族の場合のアルゴリズム

一般の次元において、領域族 F が M 個の領域を含むとき、ピクセル数 N = nd と M に関する多項式アルゴリズムの構成が可能である。

[2] I. Bloch, Spatial Relationship between Objects andFuzzy Objects using Mathematical Morphology, inGeometry, Morphology and Computational Imaging,
11th Dagsthul Workshop on Theoretical Foundationsof Computer Vision, April 2002.

定理 5.1 最適ピラミッドは O(M 2 N ) 時間で構築できる。
略証: F の領域族を頂点とする DAG で領域間の包含関係を記述しておく (含む方を起点にする）。さらに、DAG の各辺に対し、その両端での領域の Gain の大小関係が逆転するt の値を計算しておく。DAG 上のパスで、パス上の辺での tの値が単調に増加するものを許容パスという。ピラミッドは許容パスに対応し、許容パスでかつ積分値を最大にするものを動的計画法で計算する。
✷6[3] T. Fukuda, Y. Morimoto, S. Morishita, and T.
Tokuyama, Mining Optimized Association Rules for
Numeric Attributes, Journal of Computer and System Sciences 58 (1999) 1-12.
[4] T. Fukuda, Y. Morimoto, S. Morishita, and T.
Tokuyama, Data Mining with Optimized TwoDimensional Association Rules, ACM Transaction ofDatabase Systems 26 (2001) 179-213.

2 次元での実用的な領域族[5] Y. Morimoto, T. Fukuda, S. Morishita, and T.
Tokuyama, Implementation and Evaluation of Decision Trees with Range and Region Splitting, Constraints (1997) 402-427.

前節の汎用的なアルゴリズムは 2 次元の軸方向長方形の族の場合ですら O(N 5 ) = O(n10 ) の計算時間になり、更に実用的な多くの領域族は指数個の領域を持つので、個別の領域族に対し、より効率的な手法の開発が必要である。

4