1A2.2
ICICS-PCM 2003 15-18 December 2003 Singapore
Block Image Retrieval Based on a Compressed Linear Quadtree Yung-Kuan Chan*; Chin-Chen Chang** Department of Management Information System, National Chung Hsing University, Taichung, Taiwan, R.O.C.* email:
[email protected] Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan, Taiwan, R.O.C.** e-mail:
[email protected] attain its lossless data compression. Furthermore discussion will be deliberately skipped for any description about how a color image with its three color components — red, green, and blue — will be stored in the quadtree proposed. In computer-aided design, medical image archiving system, and geographical information system, expectation keeps rising — how to cast a complete big image on the screen for a better demonstration effect. For the screen sizes considered, a compacted image seems to be the only option. When details of a certain block are desired, a clicking of the mouse on that block helps project a fine resolution image on the screen. We call it block image retrieval. Unfortunately, image compression schemes share a common defect that straight forward processing from compressed data is still difficult. However, this limitation does not exist for a quadtree, since the strict constraint on its structure that may smooth out in its block image retrieval. Now there is another concern that a linear quadtree does not share this advantage of smooth processing. Any direct detailed retrieval of a certain block image in a linear quadtree is made difficult by taking a long time reading everything of this quadtree. How to merely pluck out a small part of a tree is a major challenge which is addressed in this paper.
Abstract Based on a compressed linear quad tree, a data structure is proposed which is more than a structure to compress a gray-level or color image, but a structure, which can be applied to retrieve a block image. This compressed linear quadtree may directly extract a detailed block image without decompressing the compressed data of the original image.
Keywords: quadtree, linear quadtree, image compression, image retrieval
1. Introduction The quadtree, often used to depict a binary image with 2n×2n resolution, is a four-degree tree with a height less than n [1-6, 8-11]. In this tree, every node corresponds to a quadrant of the image. A root node represents the whole image. A leaf node matches a quadrant with the same pixel color. This quadrant, if black, indicates its leaf node as a black node; if not, a white node. An internal node maps to a gray quadrant, which represents mixed black and white pixels. This gray quadrant will be repeatedly divided into four equal subquadrants: NW (northwest), NE (northeast), SW (southwest) and SE (southeast), until every subquadrant has the same pixel color inside. Figure 1 is a 28×28 binary image; Figure 2 shows its corresponding quadtree.
2. Compressed Linear Quadtree
7375 7375 7474 7675 0 2 0 2 1 1 3 2 7676 7374 7377 7474 3 3 0 1 0 4 1 1 7574 7575 7478 7677 2 1 2 2 1 5 3 4 v1 7776 7677 7679 7876 4 3 3 4 3 6 5 3 7674 7576 7577 7879 3 1 2 3 2 4 5 6 7675 7476 7675 7677 3 2 1 3 3 2 3 4 7778 7573 7476 7579 4 5 2 0 1 3 2 6 1 3 4 2 5 4 5 7 7476 7775 7877 7880 Figure 1. A binary image Figure 2: The corresponding quadtree Figure 3. A gray-level image Figure 4. The color differences of the pixels in Figure 3 with 28×28 pixels of the image in Figure 1 In this paper, a compressed linear quadtree is presented to In order to effectively present a gray-level or color image, compress a gray-level or color image, and at the same time this paper proposes a compressed linear quadtree. Rather it may be applied to retrieve a block image. As is known, in than being similar to a general quadtree, where a quadrant is a gray-level or color image block, most adjacent pixel decomposed repeatedly, this compressed linear quadtree colors have small differences, so that the smallest color stops subquadrant segmentation the moment the colors of value and the color difference between pixels are it’s pixels become similar to one another. For quadrants with meaningful in terms of data compression. In other words, shared similar pixel color, this compressed linear quadtree the difference between pixel colors demands a very small focuses on the adjacent color difference to signify number of bits to store, and that means a great deal of compression. Since image segmentation has greatly memory space is saved as a consequence saved. influenced the size of data storage of a quadtree, criteria Figure 3 describes a gray-level block image with its will be also set of how to best to decompose an image. minimal color value 73. As usual, a byte will be sufficient This compressed linear quadtree can be applied to a for a pixel color, and 64 bytes may be used to represent the gray-level or color image without data loss. However, this given block image. Figure 4 presents the pixel color values paper will merely illustrate how a gray-level image may and color difference between 0 and 7. Since the color 1
0-7803-8185-8/03/$17.00 © 2003 IEEE
difference may be kept in 3 bits, the whole block image may be placed in a 25-byte storage space. Let max and min be the greatest and the smallest values of pixel colors in a block image. The least number of bits required to hold each color difference in the block image is log 2 (max min ) . When the max-min difference increases, the color difference also grows in size. Thus, memory space is greatly wasted in this block compression. In short, the compression is limited functionally to a block image where pixel colors are close to each other. In order to make block compression more active in all images, this paper, based on the distribution of pixel colors in an image, gives a clue that a block can be decomposed into smaller ones with pixel colors closer to one another in value, with each block subsequently compressed to store its data. A compressed linear quadtree is used to perform decomposition, and therefore, satisfies block image retrieval. A binary string is used to store the tree structure of the compressed linear quadtree. In this binary string, every bit 0 stands for a leaf node; every bit 1, internal node. Each quadrant, decomposed from a quadtree, may or may not be divided into quadrants for further decomposition. A quadrant without further more decomposition is called a basic quadrant, in which pixel colors are similar. But, in a mixed quadrant, colors are sufficiently different to cognize further decomposition. Thus, every bit 0 and 1 in the compressed linear quadtree corresponds to a basic quadrant and a mixed quadrant respectively. In a compressed linear quadtree, a basic quadrant corresponding to one 0-bit in its tree structure uses a byte to memorize the smallest color value. If there is more than one pixel in the basic quadrant, another 3 bits are employed to indicate the number of bits describing the color difference. Generally speaking, each pixel in a gray-level image takes 8 bits for its color value; hence, three bits are sufficient for stating the size of the color difference. In terms of memory space, a mixed quadrant, apart from its four subquadrants, still takes an extract 1-bit as a mark in its three structures.
There are two steps to constructing a compressed linear quadtree, starting with building a tree structure, followed by block compression for its basic blocks. Responsible for building the tree structure, algorithm Decide_LQ refers to four coordinates — l(eft), r(ight), u(p), and d(own) — for four corners of a current quadrant. Parameter h defines the number of leaves between the root node and the node mapping to the current quadrant. Parameter Q is loaded with the structure describing the compressed linear quadtree. Q.max and Q.min stand for the greatest and smallest color value of the pixels in the current quadrant, respectively. Q.size marks the necessary memory space of a quadrant. Q.dsize gives the size of the color difference. Q.treelist represents the binary string of the tree structure. The output of Decide_LQ is Q.treelist, Q.size, and Q.min. The parenthesized text on the right is for comment only. Image is the two-dimensional input image. The operation A||B returns the concatenation of A and B.
Procedure Decide_LQ(l, r, u, d, Q, h) 1. if l=r then {a quadrant containing only one pixel} 2. Q.max = Q.min = Image[l][u] 3. Q.size = 8 + 1 4. Q.treelist = ‘0’ 5. Q.dsize = 0 (l + r ) (u + d ) 6. Else Decide_LQ( +1,r, +1,d,Q1,h+1) 2 2 {The NW quadrant} (l + r ) (u + d ) 7. Decide_LQ(l, , +1, d,Q2,h+1) 2 2 {The NE quadrant} (l + r ) (u + d ) 8. Decide_LQ( +1, r, u, , Q3,h+1) 2 2 {The SW quadrant} (l + r ) (u + d ) 9. Decide_LQ(l, , u, , Q4,h+1) 2 2 {The SE quadrant} 10. Q.max = MAX(Q1.max, Q2.max, Q3.max, Q4.max) 11. Q.min = MIN(Q1.min, Q2.min, Q3.min, Q4.min) 12. Q.size = 8+3+ log 2 (max min) ×2n-h×2n-h+1 13. If Q.size < (Q1.size + Q2.size + Q3.size + Q4.size) then {combine four quadrants into one basis quadrant} 14 Q.treelist = ‘0’ 15 Q.dsize = log 2 (max min) 16. Else {combine four quadrants into one mixed quadrant} 17. Q.size = Q1.size+Q2.size+Q3.size+Q4.size+1 18. Q.treelist=1||Q1.treelist||Q2.treelist||Q3.treelist|| Q4.treelist 19 Q.dsize=Q1.dsize||Q2.dsize||Q3.dsize||Q4.dsize 20 Q.min=Q.min||Q1.min||Q2.min||Q3.min||Q4.min
Figure 5. Morton Order Scanning When a linear quadtree undergoes compression, the current status of a quadrant is at once determined — either a basic quadrant without decomposition, or a mixed quadrant requiring further decomposition. The tree structure will follow the line to be determined by the basic or mixed quadrant to achieve lower memory space. This bottom-up approach, using Morton Order Scanning [7], reads the image pixels directly from the original image with a plan to construct a corresponded compressed linear quadtree. Figure 5 illustrates Morton Order Scanning, starting from the upper left and zigzagging across every pixel to repeat ths scan pattern over the whole image in a recursive fashion.
In Decide_LQ, Steps 1 to 5 are dealing with a basic quadrant with one pixel only. Steps 6 to 9 are coping with four subquadrants: NW, NE, SW, and SE. Step 13 serves to determine whether the current quadrant should be a basic quadrant without being decomposed, or should be segmented into four subquadrants. If a basic quadrant is the result, then Steps 14 and 15 will be taken. If four subquadrants are the better conclusion, Steps 17 to 20 will 2
be followed.
(l + r ) (u + d ) ,u, ,Q,h+1) {get the 2 2 Quad.dval of NW quadrant} (l + r ) (u + d ) CLQ( +1,r,u, ,Q,h+1) {get the 2 2 Quad.dval of NE quadrant} (l + r ) (u + d ) CLQ(l, , +1, d,Q,h+1) {get the 2 2 Quad.dval of SW quadrant} (l + r ) (u + d ) CLQ( +1,r, +1,d,Q,h+1) {get the 2 2 Quad.dval of SE quadrant} CLQ(l,
34 33 36 34 36 33 39 38
35 32 35 36 35 36 44 43
36 37 34 34 37 42 76 77
35 35 36 35 38 44 80 79
34 35 32 42 48 50 88 91
32 33 44 43 51 89 90 90
47 46 47 44 49 98 100 107
46 45 46 47 50 110 109 104
Figure 6. An 8×8 gray-level image Once the tree structure determined, algorithm CLQ is the stage to perform the data compression of basic quadrants. Quad, the last compressed linear quadtree structure, contains Quad.treelist, Quad.dsize, and Quad.dval. Now, Quad.treelist and Quad.dsize are mirrors of Q.treelist, and Q.dsize in what they hold. Quad.dval indicates the smallest color values, and color differences of all basic quadrants. Since Quad.treelist and Quad.dsize can be visible through reproduction, CLD merely interprets how to reach the value of Quad.dval.
Treelist:10 01 0
0
0 011 0 0 0 01 0 0 0 0
Dsize: 011 100 010 011 011 011
Dval: 32 0010 0000 0011 0001 1111 1110 1110 1101 0000 1100 1010 1011 1111 32 010 011 001 000 100 011 101 011 100 011 010 100 010 100 010 011
76 000 100 001 011 38 001 110 000 101 37 000 001 101 111 33 11 10 00 11
0
Figure 6 shows a gray-level image with 8×8 resolution. Figure 7 shows its corresponded compressed linear quadtree along with the corresponding data. In this example, in element dval, the first item of data in every block holds the smallest color value (indicated by an 8-bit) of its corresponding basic quadrant, and the rest of the data are the numbers with binary representation.
3. Block Image Retrieval
0
010 100
48
50 51
49 89
98 50
110
88 00 10 11 10 100 0000 1001 0111 0100
Figure 7.The compressed linear quadtree of the image in Figure 6. Procedure CLQ(l, r, u, d, Q, h) If the first bit of Q.treelist is ‘0’ then {compress the data in a basic quadrant} Remove the first bit of Q.treelist Move the first value min of Q.min to Q.diffval, and remove it from Q.min If h 3 n then {The basic quadrant contains over one pixel} Move the differences between min and the color values of all the pixels in the current quadrant to Quad.dval Else Remove the first bit of Quad.treelist 3
Block image retrieval may give more details for a specific block image. Without decompressing the compressed data, this section will shed light on how to directly retrieve a query block for more detailed information from a compressed linear quadtree. Given a query block with the left up most and right down most corners at the coordinates (x1, y1) and (x2, y2), a query block in question may quite possibly cover more than one subquadrant. Figure 8 has a list of six possibilities covering all eventualities. In Figure 8 (a), a query block is completely contained within a subquadrant. Figures 8 (b) to (e) show the query block spanning 2 subquadrants, and the query block in Figure 8 (f) covers a part of each of four subquadrants. A compressed linear quadtree, with reference to depth first traversal for data storage, at first encode the NW subquadrant, then the NE, SW, and SE subquadrants, subsequently. Since the corresponding NW subtree structure is placed at the front of Quad.treelist, after the corresponding subtree structure of NW subquadrant is scanned first, then the subtree structure of NE subquadrant can be read. In Figure 8 (a), therefore, the subtree structure and the size of color differences in the NW quarant are scanned first, but the corresponded data in Quad.dval are not. Then this query is repeated and concluded in the NE subquadrant. In short, if any query process is similar to that of Figure 8 (a), the other subquadrants prior to the subquadrants containing the query block are scanned first for their subtree structure and sizes of color differences for a matching result in the desired subquadrant where the query block is located. As regard to Figure 8 (b), one needs to retrieve the specified block image only from the NE and NW subquadrants. The query in Figure 8(c) repeats itself to seek the part of the query block image in the NW subquadrant first, then scans the NE subquadrant for its subtree structure and sizes of color differences. The SW subquadrant waits
for the retrieval of the part in it. In Figure 8 (d), the NE and SE subquadrants are checked, while in the NW and SW subquadrants only their subtree structures and sizes of color differences need attention. In Figure 8 (e), the SW and SE subquadrants are in question after taking the subtree structures and sizes of color differences of the NW and NE subquadrants. Figure 8 (f) tells a different story: its four subquadrants are challenged. The subquadrants containing a part of query block can be classified into two types. The first type of subquadrant contains the pixel of (x2, y2), such as the NE subquadrant in Figure 8 (a) and (b), and the SW subquadrant in Figure 8 (c). Query processing needs to retrieve data only from the left upper area of (x2, y2), and may ignore the rest. The second type of subquadrant is one not holding the pixel (x2, y2). Its corresponding tree structure and sizes of color differences are read, such as the NW subquadrants in Figure 8 (b) and (c). If the current quadrant contains the pixel (x2, y2), the retrieval can be solved by the method mentioned above. When the pixel (x2, y2) is not in the current quadrant, the tree structure and the sizes of color differences need to be read, but the smallest colors and color differences does not, except that the current quadrant is a basic quadrant and covers the query block. (x1, y1) (x1, y1)
(x2, y2)
(a)
right, up and down — of a current quadrant. The queries blocks in Figure 8 (b) and (e) are divided into two smaller (l + r ) ones with their boundary as (x1, , y1, y2) and 2
(l + r ) +1, x2, y1, y2). The query blocks of Figure 8 (c) 2 and (d) will fall into two smaller ones with boundary as (x1, (l + r ) (u + d ) x 2, y 1, ) and (x1, x2, +1, y2). The query 2 2 block in Figure 8 (f) decomposed into four smaller query (l + r ) blocks with their boundaries as (x1, , y 1, 2 (
(u + d ) ), ( 2 (l + r ) 2
(b) (x1, y1) (x2, y2)
(x2, y2)
(c)
(d) (x1, y1)
(x1, y1)
(x2, y2) (x2, y2)
(e)
(u + d ) 2
+1, y2), and (
(u + d ) 2
(l + r ) 2
), (x1,
+1, x2,
(u + d ) +1, y2). 2 The following Bsearch algorithm is designed to perform block image retrieval. Parameters CB and QB all have l, r, u, and d values, the boundary values of a current quadrant that keeps the query block. If the current quadrant is a basic one, parameter skip will give the instruction of the exact position of pixel color in Quad.dval: where to start. In every basic quadrant, there are 8 bits instructing for the minimal pixel color in the quadrant. In addition, 2h×2h×(the size of color difference) bits are employed to describe the differences of pixel colors. The first three bits of Quad.dsize suggest the size of color difference of the first basic quadrant. In this case, CB, QB, skip, Quad.size, and Quad.dval may help continue step (2). In step (5), when a certain part P of a subquadrant is desired for query, the query block is segmented and P as a query block in that subquadrant. Procedure BSearch(CB, QB, Quad, h, skip) If the first bit of Quad.treelist is ‘0’ then {a basic block} If QB is in CB then Recover the original image of the current quadrant indicated by CB Extract the original image of the query quadrant indicated by QB skip = skip + 8 + 2h×2h×Quad.dsize Remove the first 3 bits of Quad.dsize indicating the size of color difference in CB Else {The first bit of Quad.treelist is ‘1’ a mixed block} If CB contains x2, y2 then According to the different cases shown in Fig. 6, search the query block from some subquadrants of CB If CB does not contains x2, y2 then search the query block from all the subquadrants of CB Remove the first bit of Quad.treelist Algorithm Bsearch reads the data of the smallest color and color differences of the current quadrant only if the current quadrant is a basic quadrant and covers the query
(x2, y2)
(x1, y1)
,
(l + r ) +1, x2, y1, 2
(f)
Figure 8. Six possibilities for the query block spanning the four subquadrants When a query block spans more than one subquadrant, decomposition is required into smaller query blocks and then the smaller query blocks will be spotted for detailed data from the subquadrants which hold the smaller query blocks. Let (l, r, u, d) be the boundary positions — left, 4
block. Although Bsearch may also read some quadrants, without containing the query block, through their tree structures and sizes of color differences, fortunately, the latter two take a very small part of the whole compressed linear quadtree. In other words, processing time is greatly saved.
a query block. Ratio of Processing Data suggests the ratio of memory space taken for the amount of data read in query in proportion to that required by the compressed linear quadtree.
5. Conclusions The data structure of quadtree is more than often used to compress a binary image. In a gray-level or color image, although adjacent pixel colors are similar to each other, pixel color difference cannot be ignored, so that a general quadtree disqualifies itself for a gray-level or color image. This paper proposes a compressed linear quadtree, which effectively describes another data structure in gray-level or color image. Although experiments have shown the compression rate, which is not very high, the block image, however, may be straightforwardly retrieved from the compressed image without decompression. Furthermore, only a minor part of data needs processing in block image retrieval.
4. Experiments
(a) lena
(c) airplane
References
(b) pepper
[1] Y. K. Chan and C. C. Chang, “An efficient data structure for storing similar binary images,” In Proceedings of the 5th International Conference on Foundations of Data Organization (FODO’98), Kobe, Japan, Nov. 1998, pp. 268-275. [2] H. K. C. Chang, P. M. Chen and L. L. Cheng, “Overlapping representation of similar images using linear quadtrees codes,” In Proceedings of the 8th IPPR Conference on Computer Vision, Graphics and Image Processing, Tao-Yuang, Taiwan, R.O.C., August 1995, pp. 122-129. [3] C. Dyer, “The space efficiency of quadtrees,” Computing Graphics Image Process, Vol. 19, No. 4, 1982, pp. 335-348. [4] I. Gargantini, “An effective way to represent quadtrees,” Communications of ACM, Vol. 25, No. 12, 1982, pp. 905-910. [5] T. W. Lin, “Set operations on constant bit-length linear quadtrees,” Pattern Recognition, Vol. 30, No. 7, 1997, pp. 1239-1249. [6] T. W. Lin, “Compressed quadtree representations for storing similar images,” Image and Vision Computing, Vol. 15, 1997, pp. 883-843. [7] G. M. Morton, “A computer oriented geodetic database and a new technique in file sequencing,” IBM Ltd., Ottawa, Canada, 1966. [8] H. Samet, “The quadtree and related hierarchical data structures,” Computing Survey, Vol. 16, No. 2, 1984, pp. 187-260. [9] I. P. Stewart, “Quadtrees: storage and scan conversion,” Computer Journal, Vol. 29, 1986, pp. 60-75. [10] M. Vassilakopoulos, Y. Manolopoulos, and K. Economou, “Overlapping quadtrees for the representation of similar images,” Image and Vision Computing, Vol. 11, No. 5, 1993, pp. 257-262. [11] M. Vassilakopoulos, Y. Manolopoulos, and B. Kroll, ”Efficiency analysis of overlapped quadtrees,” Nordic Journal of Computing, Vol. 2, No. 1, 1995, pp. 70-84.
(d) baboon Figure 9. Four test images
Table 1. The results of the first experiment Image lena pepper airplane baboon Storage space (bits) 1469606 1351036 1272089 1745745 Table 1. The results of the second experiment (x1, y1) (x2, y2) Ratio of Processed Storage space (321, 65) (448, 192) 0. 094 (193, 65) (320, 192) 0.088 (65, 193) (192, 320) 0.097 (193, 321) (320, 448) 0.108 (321, 193) (448, 320) 0.103 (193, 193) (320, 320) 0.102 The first experiment investigates the compression ratio of the compressed linear quadtree. In these experiments, the four images in Figure 9 are used as the test images. Each image has a resolution of 512×512 pixels, with a result that each original image contains 262144-byte memory space. Table 1 describes how much memory space is required to display each of the images through a compressed linear quadtree. The second experiment performs block image retrieval based on the six possibilities of Figure 8, through testing the image “lena”. Table 2 demonstrates the extent and result of the desired query, in which (x1, y1) and (x2, y2) respectively represent the left up most and right down most positions of 5
