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, B-1 and B-2, with respect to two images, the set operations can be performed in O(n + m) time, where n is the size of B-1 and in is the size of B-2,; the complement operation for B-1(B-2) can be performed in O(n)(O(m)) time; and the 4-neighbors finding and the diagonal neighbors finding for B-1(B-2) can be accomplished in O(n log n)(O(m log m)) time.