For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Linear-Time Normalization of One-Dimensional Quadtrees
Akira ITO Katsushi INOUE Yue WANG
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/03/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
quadtree, normalization, binary string, linear time,
Full Text: PDF(548.1KB)>>
Given a binary picture represented by a region quadtree, it is desirable to identify the amount of (rightward and downward) shifts of the foreground components such that it gives the minimum number of nodes of its quadtree. This problem is called "quadtree normalization. " For this problem, it is unknown whether there exists a linear time algorithm with respect to the size of given images (i. e. , the number of pixels). In this study, we investigate the "one-dimensional version" of the quadtree normalization problem, i. e. , given a binary string represented by a regional binary tree, the task is to identify the amount of (rightward) shift of the foreground components such that it gives the minimum number of nodes of its binary tree. We show that there exists a linear time algorithm for this version.