4分木の線形時間正規化

14 References
  • ITO Akira
    Department of Computer Science and Systems Engineering Faculty of Engineering, Yamaguchi University
  • INOUE Katsushi
    Department of Computer Science and Systems Engineering Faculty of Engineering, Yamaguchi University
  • WANG Yue
    Department of Computer Science and Systems Engineering Faculty of Engineering, Yamaguchi University

Bibliographic Information

Other Title
  • Quadtree Normalization in Linear-Time

Search this article

Description

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.

Journal

References(14)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1573105977191072512
  • NII Article ID
    110003191285
  • NII Book ID
    AN10013152
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top