4分木の線形時間正規化
書誌事項
- タイトル別名
-
- Quadtree Normalization in Linear-Time
この論文をさがす
説明
2値画像が与えられたとき, それを表現する領域4分木の葉数を最小にするような前景画素の移動量を求める問題を4分木の正規化という. この問題に対する知られている最良のアルゴリズムの時間計算量は O(N^2logN) である. ここに, Nは画像の一辺の長さである (従って, N^2は画素数). 本論文では, (N^2) 時間のアルゴリズムが存在することを示す. これは, 与えられた画像を座標軸に平行な長方形に分解し, 個々の長方形の寄与分を足し合わせることによって達成される. このため, 4分木の葉に対する移動不偏な包含と排除の原理という形で, 任意の分解に対する要十分な条件を導く. この条件により, 各分解要素は互いにある一定量ずつ重なり合わなければならないことになる.
Given d binary image of square size, the problem to identify the amount of shift of the fore-ground pixels such that it minimizes the total number of leaves of the region quadtree that represents the image is called quadtree normalization. For this problem, the best known algorithms have time complexities O(N^2logN) in the worst case, where N is the side length of given images (N^2 is the number of pixels). In this paper, we show that there exists an optimal O(N^2) time algorithm. This is achieved by decomposing the given image into axis-parallel rectangles at first and summing up contributions of individual rectangles at last. To do this, we derive the necessary and sufficient condition on any decomposition scheme, in terms of shift-invariant Inclusion-Exclusion Principle for quadtree leaves, which turns out that each primitive must be 'strictly overlapped' each other to some extent.
収録刊行物
-
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
-
電子情報通信学会技術研究報告. COMP, コンピュテーション 97 (125), 1-8, 1997-06-20
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1573105977191072512
-
- NII論文ID
- 110003191285
-
- NII書誌ID
- AN10013152
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles