Abstract
A new structure for representing binary images, called the Interpolation-Based Bintree is introduced. This structure combines the features of some existing representations such as linear quadtrees, binary trees, and interpolation-based codes, to improve the performance of operations manipulating graphics images. The implementation of this method is performed on both randomly generated and actual images and is shown to be very simple and efficient. It is also shown to compare favorably with several popular techniques in both storage and processing requirement. Although this structure is mainly for binary images, it can also be utilized for a class of “color-coded” images, where the color-code has a nominal value, the difference between two codes has no meaning, and where areas of uniform code value are larger with respect to resolution.
Research supported by NSF IRI-9010365.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. R. Dyer. The space efficiency of quadtrees. Computer Graphics and Image Processing, 19(4):335–348, 1982.
H. Freeman. Computer processing of line-drawing images. ACM Comput. Surv., 6(1):57–97, 1974.
I. Gargantini. Detection of connectivity for regions represented by linear qaudtrees. Computer and Mathematics with Applications, 8(0):319–327, 1982.
I. Gargantini. An effective way to represent quadtrees. Commun. ACM, 25(12):905–910, 1982.
I. Gargantini. Translation, rotation, and superposition of linear quadtrees. International Journal of Man-Machine Studies, 18(3):253–263, 1983.
E. Kawaguchi and T. Endo. On a method of binary picture representation and its application to data compression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2(1):27–35, 1980.
K. Knowlton. Progressive transmission of gray-scale and binary pictures. In Proceedings of IEEE 68, July 1980. 885–896.
J. P. Lauzon and L. Mark. Two dimensional run-encoding for quadtree. Computer Graphics, Vision and Image Processing, 30(1):56–69, 1985.
S. Li and M. Loew. Adjacency detection using quadcodes. Image Processing and Computer Vision, 30, 1987.
M. A. Ouksel. The interpolation-based grid file. In Proc. 4th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 1985. pages 20–27, Portland, OR.
H. Samet. The quadtree and related hierarchical data structures. ACM Comput. Surv., 16(2):817–860, 1984.
M. Tamminen. Encoding pixel trees. Computer Graphics, Vision and Image Processing, 28(1):44–57, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ouksel, M.A., Yaagoub, A. (1991). The Interpolation-Based Bintree and its application to graphics. In: Dehne, F., Fiala, F., Koczkodaj, W.W. (eds) Advances in Computing and Information — ICCI '91. ICCI 1991. Lecture Notes in Computer Science, vol 497. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54029-6_156
Download citation
DOI: https://doi.org/10.1007/3-540-54029-6_156
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54029-8
Online ISBN: 978-3-540-47359-6
eBook Packages: Springer Book Archive