Fast operations on binary images using interpolation-based bintrees

摘要

The Interpolation-Based Bintree (IBB) is a new encoding scheme for representing binary images. This encoding scheme combines the features of linear quadtrees, binary trees, and interpolation-based codes. The implementation of the IBB is shown to be very simple and storage-saving. Based on the IBB structure, this paper presents some fast sequential algorithms for set operations (intersection, union, and complement), 4-neighbors finding, and diagonal neighbors finding, respectively. Given two sets of bincodes, B1, and B2, with respect to two images, the set operations can be performed in O(n + m) time, where n is the size of B1 and m is the size of B2; the complement operation for B1(B2) can be performed in O(n)(O(m)) time; and the 4-neighbors finding and the diagonal neighbors finding for B1(B2) can be accomplished in O(n log n)(O(m log m)) time.