A Non-Recursive Border Finding Algorithm for Linear Quadtree Based Images by Shao Kang Tang B.A.Sc, The University of Waterloo, 1992 A thesis submitted in partial fulfillment of the requirements for the degree of Master of Applied Science in The Faculty of Graduate Studies Department of Electrical Engineering We accept this thesis as conforming to„the required standard The University of British Columbia July 1994 © Shao Kang Tang, 1994 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. (Signature) Department of The University of British Columbia Vancouver, Canada Date August 2, 1994 DE-6 (2/88) Abstract Given a digital binary image represented in a linear quadtree, its border is to be found as another linear quadtree. A new algorithm is proposed that can generate the border in sorted order. A pattern is found for the order of the edge pixels of a node. The differences of the location codes for the edge pixels of a node with grouping factor g is stored in a lookup table. The lookup table also provides the information about which edge a given pixel is on. Through a probabilistic analysis, the new algorithm is able to avoid recursion which reduces the number of neighbour finding operations significantly. The algorithm performs better, when compared to the one by Yang & Lin, in both the run time (40% improvement) and the number of neighbour finding operations incurred (60% reduction). ii Contents Abstract ii Contents iii List of Tables v List of Figures vi Acknowledgement viii 1 Introduction 1 1.1 Problem definition 1 1.2 Literature review 5 2 Algorithm Description 11 2.1 Overview of the algorithm 11 2.1.1 Algorithm by Yang & Lin 12 2.2 Generation of sorted edge pixels of a node 14 2.2.1 Difference LUT for the lower edge pixels of a node . . 16 2.2.2 Difference LUT for the upper edge pixels of a node . . 19 iii 2.2.3 Incorporating side information into the difference LUT 21 2.3 Probabilistic analysis leading to non-recursion 24 2.4 The complete algorithm 41 2.4.1 The main routines 43 2.4.2 The routines for setting the snt bit vector 44 2.4.3 The routines for checking nodes larger than size 2 x 2 45 2.4.4 The routine for checking 2 x 2 nodes 48 2.5 Further acceleration 49 3 Algorithm Correctness 51 3.1 Applicability of the algorithm 51 3.2 Verification of the algorithm 51 3.3 Experimental verification . 54 4 Algorithm Performance 67 4.1 Time complexity analysis 67 4.2 Runtime and profile 68 4.2.1 The implementation and run-time environment . . . . 68 4.2.2 The results 69 4.2.3 Confidence interval 74 5 Conclusion & Future Directions 77 6 Glossary 79 Bibliography 83 A Program Listing 84 iv List of Tables 1.1 Characteristics of border finding algorithms 9 1.2 Characteristics of lqt/lot border finding algorithms 10 2.1 Node size statistics for sample quadtrees 35 2.2 The effective E2 - E\ using data from sample quadtrees . . . 38 4.1 Performance of the program yl 71 4.2 Performance of the program tang 72 4.3 Performance of the program atang 73 4.4 Percentage improvement of tang over yl 73 4.5 Percentage improvement of atang over yl 74 v List of Figures 1.1 Linear quadtree domain of resolution 4 4 2.1 Lookup table for lower edge pixels of a node of g = 4 17 2.2 Lookup table for upper edge pixels of a node of g = 4 . . . . 20 2.3 A sample node P and its neighbours 25 2.4 Quadtree F with edge pixels shown 29 2.5 Quadtree slantF with edge pixels shown 30 2.6 Quadtree distortF with edge pixels shown 31 2.7 Quadtree randoml with edge pixels shown 32 2.8 Quadtree random2 with edge pixels shown 33 2.9 Quadtree random3 with edge pixels shown 34 2.10 Sections of the edge of a node 40 2.11 The snt vector of the node P in Figure 2.3 42 3.1 Quadtree F 55 3.2 Borders of quadtree F 56 3.3 Quadtree slantF 57 3.4 Borders of quadtree slantF 58 3.5 Quadtree distortF 59 vi 3.6 Borders of quadtree d is tor tF 60 3.7 Quadtree randoml 61 3.8 Borders of quadtree randoml 62 3.9 Quadtree random2 63 3.10 Borders of quadtree random2 64 3.11 Quadtree random3 65 3.12 Borders of quadtree random3 66 4.1 A 2 x 2 node where yl fails to condense 70 4.2 A case that a tang performs poorer than yl 75 vn Acknowledgement I am grateful to Dr. Schrack for his guidance and patience, and I am indebted to the financial support from NSERC of Canada. I also wish to express my sincere thanks to my parents, relatives and friends for their support. viii Chapter 1 Introduction 1.1 Problem definition Finding the borders of an image is a well-studied problem in image processing If black pixels represent the objects in the image and white pixels represent the background, a binary image is obtained. It is a relatively easy task to find borders of a digital binary image because the criterion is simple: a pixel is on the border if one of its neighbours is white. However, there have been few algorithms designed specifically for linear quadtree based images. A linear quadtree is a variation of the (regular) quadtree data struc-tures [Same 90]. Quadtrees are used in areas of computer vision, computer graphics, image processing, spatial databases, cartography, and geographic information systems (GIS). Border finding is a common operation in these applications. For example, the query "find all streets on the border of Van-couver" would require a GIS perform the following operations: find the *It is termed edge detection in the image processing literature. 1 border of a map representing Vancouver and then intersect the result with a map storing the streets of Vancouver. The quadtree is constructed by dividing a 2r x 2 r raster domain into four quadrants, where r is the resolution. If a quadrant is only partially contained in an object in the image, that quadrant is subdivided recursively into its four subquadrants. The above process continues until either the subquadrant is completely contained within an object, completely outside all objects, or the pixel level has been reached. A quadtree is usually implemented as a pointer-based hierarchical data structure where the root node represents the whole raster domain. Each node represents a subquadrant on the raster, and is either black (completely contained within an object), white (completely outside all objects), or grey (partially contained by an object). If a node is grey, then it has four pointers for its four children representing the subquadrants. Since pointers occupy much space, a variation called linear quadtree is introduced that stores only the black nodes in a list or an array [Garg 82]. Each black node is represented by a location code and its associated grouping factor or level. A location code is obtained by traversing the links of the quadtree. Each link is represented by a quaternary digit: • 0 for the south-west child, • 1 for the south-east child, • 2 for the north-west child, and • 3 for the north-east child. The location code (loc) of a black node is the concatenation of the quaternary 2 digits on the path from the root to the node itself. If the node is not a pixel, O's are appended to fill the location code to r digits. The grouping factor (g) represents the size of the node: g = 0 means a pixel, g = 1 means a 2 x 2 node, . . . , g = k means a 2k x 2k node. The level of a node is the resolution minus its corresponding grouping factor; it represents the depth of the node in the quadtree. For example, consider Figure 1.1 , the node consisting of the pixels {48,49,50,51} is represented by the pair (/oc,g')=(03004,l)=(48io,l). A linear quadtree consists of the set of (loc,g) pairs representing the black nodes of the objects in the image. It is also required that the pairs be sorted in ascending order by the location code. A useful property of the location code of a pixel is that it contains (x,y) values of the pixel in the Cartesian coordinate system. Specifically, each location code is the interleaving of the bits of the x and y coordinates. For example, the location code 49io = 03014 is OOHOOOI2 in binary. If the bits are separated alternately, starting with the first bit as the most significant bit of the y coordinate, one obtains y = OIOO2 = 4 and x = OIOI2 = 5, which are precisely the coordinates of the pixel 49 in Figure 1.1. The terms 4-connected and 8-connected define the adjacency relation-ship between any two pixels. If two pixels are adjacent, meaning they are neighbours in one of the four directions east, south, west, or north, then they are 4-connected. If two pixels are adjacent in one of the eight directions east, south, west, north, south-east, south-west, north-west, or north-east, then they are 8-connected. The border pixels are those that have at least a white neighbour, be it 4- or 8-connected; however, in this thesis, only 8-connected border will be considered. The edge pixels of a node are distinguished from the border pixels. A 3 1 3 1 11 1 3 1 170 168 162 160 138 136 130 128 42 40 34 32 10 8 2 0 171 169 163 161 139 137 131 129 43 41 35 33 11 9 3 1 174 172 166 164 142 140 134 132 46 44 38 36 14 12 6 4 175 173 167 165 143 141 135 133 47 45 39 37 15 13 7 5 186 184 178 176 154 152 146 144 58 56 50 48 26 24 18 16 187 185 179 177 155 153 147 145 59 57 51 49 27 25 19 17 190 188 182 180 158 156 150 148 62 60 54 52 30 28 22 20 191 189 183 181 159 157 151 149 63 61 55 53 31 29 23 21 234 232 226 224 202 200 194 192 106 104 98 96 74 72 66 64 235 233 227 225 203 201 195 193 107 105 99 97 75 73 67 65 238 236 230 228 206 204 198 196 110 108 102 100 78 76 70 68 239 237 231 229 207 205 199 197 111 109 103 101 79 77 71 69 250 248 242 240 218 216 210 208 122 120 114 112 90 88 82 80 251 249 243 241 219 217 211 209 123 121 115 113 91 89 83 81 254 252 246 244 222 220 214 212 126 124 118 116 94 92 86 84 255 253 247 245 223 221 215 213 127 125 119 117 95 93 87 85 Figure 1.1: Linear quadtree domain of resolution 4 4 pixel is an edge pixel if it is on an edge of a node. A border pixel must be an edge pixel of a node; an edge pixel need not be a border pixel when all of its neighbours are black. 1.2 Literature review There have been several definitive algorithms for finding borders of a raster image. For example, the algorithm by Pavlidis [Pavl 82] follows the con-tour of an object and generates the borders as chain codes. Rosenfeld & Kak [Rose 82] find borders by translating the reverse of the image in four directions and then intersect with the original image. However, the first al-gorithm specifically designed for quadtree-base images seems to be the one by Dyer et al. [Dyer 80]. It adopts the paradigm of contour following as documented in [Pavl 82] with a few rules designed for quadtrees. Li and Loew [Li 84] also use the idea of contour following but they first convert a quadtree to a raster image before proceeding to find the borders. Atkinson et al. [Atki 84] and [Atki 85] discovered a completely differ-ent approach for finding borders. They achieved the result by repeatedly eliminating internal black nodes. Although the algorithms were presented as linear octree algorithms, they were really simple extensions of the corre-sponding linear quadtree algorithms. Dillencourt and Samet [Dill 88] invented yet another paradigm which was based on the concept of active borders. While traversing the nodes of a linear quadtree in order, they kept a set of active borders that define the boundary between the nodes that have been visited and those that have not. Borders of the objects are recorded by checking neighbouring 5 nodes of the active borders. Qian and Bhattacharya [Qian 89] adapted an algebraic approach to this problem. They converted a quadtree to a picture polynomial which can then be multiplied by another polynomial representing the operation of border finding. Franciosa and Nardelli [Fran 91] used a guaranteed approximation algorithm which was mainly designed for on-line computing a quadtree border. They generated the approximated borders of a quadtree and then successively refined the approximations. Yang and Lin [Yang 90] returned to the approach of Atkinson et al. [Atki 85] and improved upon it by utilizing a new neighbour finding al-gorithm and some rules to avoid most of the sorting required. The new algorithm presented in this thesis improves that of Yang and Lin [Yang 90] by avoiding sorting and by removing the need for recursion. The characteristics of the algorithms discussed above are summarized in Tables 1.1 and 1.2. To make the tables more compact, the following synonyms are introduced. Paradigm: cf Contour following t i Translations and intersections ab Active borders alg Algebraic (polynomial) approach ga Guaranteed approximations re Repeated elimination 6 Input: r Raster rqt Regular quadtree rqt2r Regular quadtree converted to raster lqtw Linear quadtree with white nodes as input as well rqt2pp Regular quadtree converted to picture polynomial rqta Regular quadtree with adjacency information embedded lot Linear octree lqt Linear quadtree Output: cc Chain codes rp Random pixels pv Polygonal vertices pp2rqte Picture polynomial converted to regular quadtree with border en-larged rqtn Regular quadtree with possibly non-pixel nodes lot Linear octree lqt Linear quadtree 7 Adjacency: 8 8-connectedness 4 4-connectedness fv8 Face- and vertex-connectedness (corresponding to 8-connectedness in 2D) Applicability; eism External and internal borders of singly and multiply connected regions es External border of a singly connected region Time complexity; P Perimeter of the object N Number of nodes in the tree G Total number of grey nodes at all levels M Number of border voxels (or pixels in 2D) in the tree k Maximum node grouping n Resolution As one can see from the tables, the various algorithms assume different input and output conditions, therefore, it is difficult to compare them. The new algorithm is listed in Table 1.2 and is compared to the one by Yang & Lin [Yang 90]. 8 Table 1.1: Characteristics of border finding algorithms Paradigm Input Output Adjacency Recursive? Sorting? Neighbour finding? Applicability Complexity [Pavl 82] cf r cc 8 no no no eism N/A [Rose 82], ti r rp 8 no no no eism N/A [Dyer 80] cf rqt cc 4 yes no yes es O(P) average [Li 84] cf rqt2r cc 4 no no no es N/A Paradigm Input Output Adjacency Recursive? Sorting? Neighbour finding? Applicability Complexity [Dill 88] ab lqtw pv N/A no no no eism N/A [Qian 89] alg rqt2pp pp2rqte N/A no no no N/A N/A [Fran 91] ga rqt a rqtn 4 no no no N/A 0(G) worst 9 Table 1.2: Characteristics of lqt/lot border finding algorithms Paradigm Input Output Adjacency Recursive? Sorting? Neighbour finding? Applicability Complexity [Atki 84] re lot lot fv8 yes no yes eism 0(kn(N+M)) worst [Atki 85] re lot lot fv8 yes yes yes eism N/A [Yang 90] re lot lot fv8 yes few yes eism O(N) average new re lqt lqt 8 no no yes eism O(N) average 10 Chapter 2 Algorithm Description There are two novelties in the proposed algorithm: • The edge pixels of a quadtree node can be generated in sorted order. • A probabilistic analysis leads to the non-recursive nature of the algo-rithm. The above two points will be described in sections 2.2 and 2.3 respectively before the complete algorithm is presented in Section 2.4. However, the overview of the algorithm will ensue first. 2.1 Overview of the algorithm The new algorithm adapts the paradigm of repeated elimination. This paradigm was first proposed by [Atki 84] and [Atki 85]. It facilitates border finding by eliminating internal nodes. The method of determining whether a node is internal is neighbour finding. If all four neighbours, i.e. east, south, west, and north neighbours, of the current node are black, then it is 11 an internal node. Otherwise, the current node is sub-divided into its four children and the elimination process continues recursively to the pixel level where the border of the original quadtree is determined. The new algorithm, however, is closer in spirit to the one by Yang & Lin [Yang 90]. Their algorithm is described first, with the reasons for the two novelties of the new algorithm indicated. 2.1.1 Algor i thm by Yang & Lin Yang & Lin [Yang 90] noted that there are two major disadvantages in [Atki 85]: 1. The resulting border pixels are not sorted as required by the linear quadtree representation. 2. The input data need to be dispatched into different sub-arrays accord-ing to the grouping factor. To avoid these shortcomings, Yang & Lin formulated a few rules that helped categorize a node into one of three types: internal, PB-quadrant1, or undetermined. • An internal node is characterized by having neither grey nor white neighbours, that is, all neighbours are black. • A node is a PB-quadrant if it has no grey neighbour but has at least one white neighbour. PB stands for proper border. Some of the edge pixels of a PB-quadrant lie on the border of the original quadtree. 'Actually, the term used in [Yang 90] is PB-octant. Their paper discusses octree bor-ders; however, it is also applicable to quadtrees. 12 • A node is undetermined if it is neither internal nor a PB-quadrant, that is, it has at least one grey neighbour. In contrast to [Atki 85] which sub-divides a node recursively to the pixel level for any non-internal node, the algorithm by Yang & Lin only sub-divides the undetermined nodes. Avoiding unnecessary subdivisions reduces the number of neighbour finding operations. They also introduced the notion of predict-binary search which, as claimed, reduces the time complexity of a binary search from O(log N) to 0(1) on average. The algorithm can thus proceed by examining each input node in order. If the current node is internal, discard it. If the current node is a PB-quadrant, the edge pixels of this quadrant are examined to output those that are on the border. Otherwise, as the current node is undetermined, sub-divide the node into its four children and continue the process recursively. The proposed algorithm follows basically the same process but avoids the need for recursion. Non-recursion further reduces the number of neighbour finding operations which in many cases are the bottleneck operations in finding the border using repeated elimination. See also the discussion in Section 2.3. Since the input nodes are examined in sorted order, the border pixels are output in sorted order, consequently, no sorting is required. The only disadvantage is that the border pixels of a PB-quadrant also need to be output in sorted order. Currently, the algorithm of Yang & Lin inserts each border pixel into its sorted position. The approach is in essence an insertion sort on the border pixels of any PB-quadrant. The new algorithm strives to produce the PB-quadrant border pixels in sorted order without sorting, but at the expense of auxiliary data structures and preprocessing. The idea is 13 discussed in Section 2.2. 2.2 Generation of sorted edge pixels of a node To output the border pixels of a PB-quadrant in sorted order, it is considered beneficial to be able to first generate the edge pixels of a PB-quadrant in sorted order. After the neighbour types have been determined for the PB-quadrant, i.e. whether the neighbours are black or white, one can in principle traverse the edge pixels in sequence and output as border pixels only those with at least one white neighbour. The idea used in the new algorithm for generating sorted edge pixels of a PB-quadrant, and thus of any node, is to find a certain pattern for the differences of the location codes of the edge pixels and to use lookup tables. A lookup table diff.border.LUT[g] points to an array that contains the differences of the location codes of the edge pixels of a node with grouping factor g. Since the grouping factor can be anywhere in the range [0, res], res + 1 such lookup tables are potentially needed. For example, referring to Figure 1.1, the node (96,2) has the following edge pixels, in sorted order: 96 97 98 100 101 103 104 106 107 109 110 111 Thus diff_border_LUT[2] points to an array with the following entries: 1 1 2 1 2 1 2 1 2 1 1 which are precisely the differences in the first sequence. As another example, diff_border_LUT[3] points to the array: 1 1 2 1 3 2 6 1 3 1 2 6 2 1 2 6 2 1 3 1 6 2 3 1 2 1 1 14 which can be used to generate the edge pixels of a node with grouping factor 3, given the location code of its south-west corner pixel. For example, to generate the edge pixels of the node (192,3), the following calculations utilizing diff_border_LUT[3] will find them in the desired order: 192 192 + diff_border_LUT[3][0] = 192 + 1 = 193 193 + diff_border_LUT[3][l] = 193 + 1 = 194 194 + diff_border.LUT[3][2] = 194 + 2 = 196 254 + diff_border_LUT[3][26] = 254 + 1 = 255 The difference sequences of a given grouping factor are all the same and independent of the south-west corner pixel. Therefore, the difference sequence diff_border_LUT[2] also applies to any node of grouping factor 2, for example, the node (0,2), or (224,2). This is the direct consequence of the fact that location codes of the pixels of a node are offset by the location code of its south-west corner pixel from the node of the same grouping factor but located with 0 as its south-west corner. For example, in Figure 1.1, if the location codes of the pixels of the node (224,2) are all subtracted by 224, then they correspond to the location codes of the pixels of the node (0,2). Since the resolution of an input quadtree is a variable and since not all grouping factors will always appear in the input quadtree, it is not feasible to pre-calculate the differences for diff_border_LUT[2], difLborder_LUT[3],..., 15 diff_border_LUT[re.s]2) and then hard-code them into the program. There-fore, these lookup tables are generated dynamically. To facilitate the dynamic generation of the difference LUT's, a pattern is sought. The above examples of difference sequences on first glance appear to consist of random sequences; however, further investigation leads to a pattern. To see the pattern more clearly, a node of grouping factor 4 will be analyzed. The edge pixels are separated into a lower portion and an upper portion which will be considered separately. 2.2.1 Difference LUT for the lower edge pixels of a node The lower edge pixels of the node (0,4) will be listed together with their differences in Figure 2.1. The symbols SW, SI etc. will be discussed in Section 2.2.3. The edge pixels are separated into various lines and are called the e-lines. The differences are also separated into various lines and are called the d-lines. The number at the end of each d-line is the difference between the last number of the preceding e-line and the first number of the following e-line. For example, the number 6 of the d-line (d3) is 16 minus 10, where 10 is the last number of the e-line (e3) and 16 is the first number of the e-line (e4). The other numbers of the d-lines are the differences of the numbers of the preceding e-lines. For example, consider e-line (e3) and d-line (d3): 5 - 4 = 1 , 8 - 5 = 3 , 1 0 - 8 = 2. The d-line (dl) always contains the number 1. For the d-lines (d2) to (d5), the following pattern emerges. The numbers 2 Note that for nodes of grouping factors 0 and 1, the differences of their edge pixels are trivial. Thus, these differences will not be stored but the program using the lookup tables has to handle these two cases separately. 16 (el) 0 SW (d1) 1 SW (e2) 1 2 S1 W1 m 1 S1 (e3) 4 5 8 10 S1 S1 W1 W1 (d3) 1 3 S1 S1 (e4) 16 17 20 21 S1 S1 S1 S1 (d4) 1 3 1 11 S1 S1 S1 S1 (e5) 64 65 68 69 S2 S2 S2 S2 (d5) 1 3 1 11 1 S2 S2 S2 S2 S2 (e6) 127 E1 32 W1 80 S2 3 S2 34 W1 81 S2 1 S2 40 W1 84 S2 42 W1 85 SE 2 W1 2 6 W1 W1 2 6 2 W1 W1 W1 87 93 95 E1 E1 E1 2 6 2 SE E1 E1 22 W1 117 E1 22 E1 119 125 E1 E1 2 6 2 E1 E1 E1 Figure 2.1: Lookup table for lower edge pixels of a node of g = 4 17 on the d-lines are divided into two groups: the h-group and the v-group. The h-group consists of the numbers in the first half of a d-line; the v-group consists of those in the second half. Each number in the v-group is exactly twice that of the corresponding h-group on any particular d-line. For example on (d4), 2 6 2 22 is twice as much as 1 3 1 11 respectively. The h-groups of d-lines consist of the same set of numbers as the differ-ences of the location codes across the horizontal axis of the domain. The numbers across the top of Figure 1.1 indicate the differences3. The d-line (d{) has 2'~2 entries in its h-group, except the last d-line which has 2 5 _ 1 - 1 entries. For example, • (d2) has 2 2 - 2 = 2° = 1 entry, the number 1; • (d3) has 2 3 - 2 = 21 = 2 entries : 1 3; • (d4) has 24~2 = 22 = 4 entries : 1 3 1 11; • (d5) has 29-1 - 1 = 24"1 - 1 = 7 entries : 1 3 1 11 1 3 1 in the h-group, where the entries, 1, 1 3, 1 3 1 11, or 1 3 1 11 1 3 1, are the numbers across the top of Figure 1.1. There are hence 1 + 2 x [2° + 21 + ... + 29~2 + (2S _ 1 - 1)] = 29+1 - 3 (2.1) number of entries in the lower portion of diff_border_LUT[g], where the 1 at the beginning accounts for (dl), the summation inside [...] accounts for the h-group on the rest of the d-lines, and the multiplication by 2 accounts for the v-group. 3The numbers in the v-group consist of the differences of location codes along the vertical axis of the domain. Thus the designations v and h. 18 The above observation can be generalized to a node of any grouping factor in the range [2, res]. Thus to generate diff_border_LUT for lower edge pixels of the nodes, 2res~1 — 1 number of differences of the location codes across the horizontal axis are calculated first. Then the above observations are used to generate each d-line in turn. The concatenation of the d-lines gives the differences for the lower edge pixels of the current node. 2.2.2 Difference LUT for the upper edge pixels of a node Now consider the upper edge pixels of the node (0,4). The edge pixels and their differences are listed in Figure 2.2 and in a format similar to the one in the previous section; however, the differences are now called the d'-lines. The number at the beginning of each d'-line is the difference between the last number of the second preceding e-line and the first number of the preceding e-line. For example, the number 22 of the d'-line (d'9) is 213 minus 191, where 191 is the last number of the e-line (e8) and 213 is the first number of the e-line (e9). The other numbers of the d'-lines are the differences of the numbers of the preceding e-lines. For example, consider e-line (e9) and d'-line (d'9): 215 - 213 = 2,221 - 215 = 6,223 - 221 = 2, 234 - 223 = 11,235 - 234 = 1,238 - 235 = 3,239 - 238 = 1. It is noticed that the d'-lines are the reverse of the d-lines. For example, (d'10) consists of 6 2 3 1, which is the reverse of 1 3 2 6, the sequence of (d3). Similarly for (d'9) and (d4), or (d'8) and (d5) etc. Therefore, to generate the differences for the upper edge pixels, i.e. the d'-lines, simply generate those of the lower edge pixels, i.e. the d-lines, and reverse the entries. The difference between the last location code of the lower edge pixels and the first location code of the upper edge pixels is always one. Thus, to 19 (e7) 128 W2 (e8) 130 W2 (d'8) 2 W2 (e9) 213 E2 (d'9) 22 E2 (e10) 245 E2 (d'10) 6 E2 (e11) 253 E2 (d'11) 2 E2 (e12) 255 NE (d'12) 1 NE 136 W2 6 2 W2 W2 215 E2 2 6 E2 E2 247 E2 2 E2 254 N2 138 W2 22 W2 221 E2 2 E2 250 N2 160 W2 2 6 W2 W2 223 E2 251 N2 162 W2 2 NW 234 N2 168 W2 235 N2 170 NW 238 N2 171 N1 1 N1 239 N2 11 N2 3 N2 1 N2 174 175 N1 N1 3 1 11 N1 N1 N1 1 3 1 N2 N2 N2 1 N2 186 N1 1 N1 187 190 N1 N1 3 1 N1 N1 191 N1 Figure 2.2: Lookup table for upper edge pixels of a node of g = 4 20 get the number 128 on (e7), simply add 1 to the number 127 on (e6). From the above discussions, diff_border_LUT[4] can be generated by con-catenating (dl) to (d5), the number 1, and then (d'8) to (d'12). The number of entries of diff_border_LUT[g] is thus, from Equation 2.1, 2 x (2^+1 - 3) + 1 , or 2^+2 - 5. 2.2.3 Incorporating side information into the difference LUT Now that the edge pixels of a node can be generated in sorted order, how can one determine whether these edge pixels are on the border of the original input quadtree? A natural idea is to visit each edge pixel and check its neighbours. If one of the edge pixel's four neighbours is white, then that edge pixel belongs to the border of the quadtree. However, there is no need to check all four but only at most two neighbours for each of these edge pixels. For example, if the edge pixel visited is at the north-west corner of the current node, then it is guaranteed that its east and south neighbours are black because these neighbours belong to the current node. Therefore, it is only necessary to check the north and west neighbours of an edge pixel at the north-west corner of the current node. Similarly, it is only necessary to check • the north and east neighbours of an edge pixel at the north-east corner of the current node; • the south and east neighbours of an edge pixel at the south-east corner of the current node; • the south and west neighbours of an edge pixel at the south-west corner of the current node. 21 For the edge pixels not at the corners of the current node, only one neighbour check is needed. For example, if the edge pixel is on the south side of the current node, then it is guaranteed that its east, west, and north neighbours are black because the east and west neighbours are also on the edge of the current node while the north neighbour is internal to the current node. Therefore, it is only necessary to check the south neighbour of an edge pixel on the south side of the current node. Similarly, it is only necessary to check • the east neighbour of an edge pixel on the east side of the current node; • the north neighbour of an edge pixel on the north side of the current node; • the west neighbour of an edge pixel on the west side of the current node. Since diff_border_LUT is used for generating the edge pixels of a node, it is convenient that the LUT's will also store the above side information so that appropriate neighbour finding operations can be performed. Due to reasons that will be explained in Section 2.3, the side information will be divided into twelve directions: #define SW 1 #define SI 2 *define Wl 3 #define S2 4 #define SE 5 22 #define El 6 #define W2 7 #define NW 8 #define Nl 9 #define E2 10 #define N2 11 #define NE 12 instead of the usual eight directions: E (east), S (south), W (west), N (north), SE (south-east), SW (south-west), NW (north-west), NE (north-east). From Figure 2.1, the pattern for the side information can be deduced. For example, there are one SI on (d2), two SI on (d3), four Si on (d4), and seven S2 on (d5). The one, two, four, and seven are exactly the number of entries in each h-group. Therefore, it is possible to store the side information into the lower portion of diff_border_LUT as well. By examining Figure 2.2, it is noticed that the directions of the upper portion of diff_border_LUT are opposite to the directions of the lower portion. For example, NE of (d'12) is the opposite of SW of (dl); N2 of (d'9) is the opposite of SI of (d4). Therefore, by defining the directions to be the numbers as shown above, the side information of the upper diff_border_LUT can be generated by thirteen minus the corresponding number representing the direction in the lower portion of diff.borderJLUT. For example, 13 - SW = 13 - 1 = 12 = NE as expected. 23 2.3 Probabilistic analysis leading to non-recursion As neighbour finding is usually the bottleneck operation in border finding algorithms using repeated elimination, an effort was made to reduce the number of such operations. Examining the edge pixels of the input nodes and finding one or two neighbours for each of the pixels may not be efficient in certain cases. For example, consider node P in Figure 2.3, • finding one neighbour will suffice instead of finding eight neighbours in the south direction; • finding two neighbours will suffice instead of finding eight neighbours in the east direction. Since there is no prior knowledge on the size of the neighbours, one possibility is to use recursion as suggested by [Yang 90]. For example, finding one neighbour in the east direction shows that the east neighbour is grey, therefore, the node is subdivided and two neighbour finding operations are performed on neighbours of the size one fourth of the original. The above process continues recursively until the neighbours are no longer grey. Of course, for recursive subdivisions, neighbours must be found in all four directions. Hence, to resolve the east neighbour for the example in Figure 2.3, 1 + 4 x 2 = 9 potential neighbours must be found, where the factor 4 accounts for checking all four neighbours of the south-east and north-east children of the original node. The naive method, on the other hand, only requires 8 neighbour finding operations. Since neither checking directly all the edge pixels nor using recursion is satisfactory, a hybrid algorithm is devised that incorporates the two. The 24 w E w F w F w F Q black P black white black white Figure 2.3: A sample node P and its neighbours 25 hybrid method always finds one neighbour in each of the four directions first. If some of the neighbours found are grey, the algorithm will wait until a certain number of recursive subdivisions are performed before possibly checking all edge pixels. The question is: how many recursive subdivisions should be performed, zero, one, or maybe more? A break-even point in the number of recursive subdivisions is therefore sought that will make the hybrid method a viable approach. A probabilistic analysis will be used to help determine the break-even point. To simplify the analysis, only the neighbour in one particular direc-tion will be considered. Let g denote the grouping factor. Consider a node with g — k. Let the probabilities of its neighbour being of size g = k — 1 be Pk-i, of size g = k — 2 be Pk-2, and so on, to po for g = 0, i.e. the pixel level. Neighbours with g > k need not be considered because the neighbour finding operation that is always performed first will resolve such cases. Let the number of neighbour finding operations required to resolve the type, i.e. black or white, of a neighbour with g = 1,1 < k, using only recursive subdivisions, be //. Then / , = 21 + 22 + ... + 2k~l = 2fc~'+1 - 2 (2.2) The factor 4 accounting for the four neighbours of each child node is not included because only a particular direction is considered. Let E\ be the expected value of the number of neighbour finding opera-tions needed to resolve the type of a neighbour, using recursive subdivisions 26 only. Then fc-i «=0 Let E2 denote the expected value of the number of neighbour finding op-erations needed to resolve the type of a neighbour using the hybrid method. Let m be the break-even point of the number of recursive subdivisions, then the hybrid method will always subdivide m times before possibly checking the 2k edge pixels. Then k—\ k—m — 1 E2= £ Pifi + (fk-m + 2k) £ Pi i=k—m t =0 The first term of E2 is for the case where the grouping factor g of the neighbour is such that k — m<g<k — 1, i.e. the cases that are taken care of by the m subdivisions. The second term of E2 accounts for the case where the g of the neighbour is such that 0 < g < k — m — 1. Then, after fk-m neighbour finding operations have been carried out by means of m subdivisions, the neighbour is still not resolved, hence additional 2k neighbour finding operations for the edge pixels are included. This occurs with a probability Ylk=o~l Pi-Substituting Equation 2.2 into E2 and after some algebra, the following relationship is obtained. k—m — l k—m—l—i E2 = Ex + 2m+1 £ p^-"1-1- £ 2j) t=0 j=0 It is required that E2 < E\ for the hybrid method to achieve better, or at least the same, efficiency on average. That is, k—m—l k—m — l—i E2-Ex = 2m+1 £ Pi{2k-m-x - J2 2J) ^ ° «=o j=0 27 or k—m—l k—m—l—i £ Pi(2k-m-1- £ 2>')<0 (2.3) t'=0 j=Q Provided the probabilities are known, Equation 2.3 allows to solve for the break-even point m. A pragmatic approach is used to provide the prob-ability values. Four typical input quadtrees are processed which give a first approximation for the probabilities p,. These sample quadtrees are shown in Figures 2.4 to 2.9 where the edge pixels of each node are displayed4. The statistics for the sizes of the nodes are summarized in Table 2.1 together with the percentages of occurrences of each node size. The per-centages will be used as the approximated pi in each tree. Comparing Figures 2.4 to 2.9 with Table 2.1, it is intuitively obvious that half of the input nodes are of size g = 0, i.e. pixels. The pixels are primarily distributed along the border of the quadtrees. Now with the percentage of g = i in Table 2.1 as pi, Equation 2.3 is examined to find a suitable m. Consider Figure 2.4, the input quadtree with the shape of a large F. For k = 0, the obvious choice is m = 0, that is, no subdivision is neces-sary for pixel level nodes, Equation 2.3 does not apply. For k = 1, the left hand side of Equation 2.3, i.e. the effective E2 — El, becomes Po(2° - f > ' ) = Po(2° - 2°) = 0 (2.4) j=o which satisfies the inequality. A node of grouping factor 1 is a 2 x 2 node where a simple subdivision results in the same number of neighbour finding 4A utility progiam was written for this purpose. It used the algorithm developed in Section 2.2. 28 1 lull 1 illll 1 1 1 1 1 1 1 1 1 1 1 I l l l l ^ 1 • 1 • Figure 2.4: Quadtree F with edge pixels shown 29 3B3B be Figure 2.5: Quadtree slanfF with edge pixels shown 30 Figure 2.6: Quadtree distortF with edge pixels shown 31 Figure 2.7: Quadtree randoml with edge pixels shown 32 Figure 2.8: Quadtree random2 with edge pixels shown 33 Figure 2.9: Quadtree random3 with edge pixels shown 34 Table 2.1: Node size statistics for sample quadtrees g 8 7 6 5 4 3 2 1 0 F # o f nodes 0 0 0 0 28 24 48 96 384 % 0 0 0 0 4.8 4.1 8.3 16.6 66.2 slantF # o f nodes 0 0 0 0 30 27 87 135 354 % 0 0 0 0 4.8 4.3 13.7 21.3 55.9 distortF # o f nodes 0 0 0 2 24 69 152 309 618 % 0 0 0 0.2 2.0 5.9 13.0 26.3 52.6 g 10 9 8 7 6 5 4 3 2 1 0 randoml # o f nodes 0 0 0 3 36 82 174 429 821 % 0 0 0 0.2 2.3 5.3 11.3 27.8 53.1 random2 # o f nodes 0 0 0 9 30 89 181 438 957 1836 3845 % 0 0 0 0.1 0.4 1.2 2.4 5.9 13.0 24.9 52.1 random3 # o f nodes 0 0 0 5 37 155 338 949 1613 % 0 0 0 0.2 1.2 5.0 10.9 30.6 52.1 35 operations as that of checking all edge pixels, hence there is no need to perform subdivision, i.e. choose m = 0. For k = 2, the left hand side of Equation 2.3 becomes 1 —TO 1—TO—t 5X21"™- £ V) i=0 j=o If m = 1, then the above expression becomes Equation 2.4 and results in 0. If m = 0, then the above expression becomes Po(2x - 2° - 21) + Pl (21 - 2°) = Pl - po (2.5) Substituting the percentages from Table 2.1, pi - Po — 0.166 - 0.662 = —0.496. Both m = 1 and m = 0 satisfy the inequality of Equation 2.3. For k = 3, the left hand side of Equation 2.3 becomes 2—771 2—m—i £>(2 2 - r o - j ; y) i=0 j=0 If m = 2, then the above expression becomes Equation 2.4 and results in 0. If m = 1, then the above expression becomes Equation 2.5 and results in —0.496. If m = 0, then the above expression becomes po(22 - 2° - 21 - 22) + Pi(22 - 2° - 21) + p2{22 - 2°) = 3p2 +Pi - 3po (2.6) Substituting the percentages from Table 2.1, 3p2 + P\ — 3po = 3 x 0.083 + 0.166 - 3 X 0.662 = -1.571. All three cases m = 2 , m = l , r a = 0 satisfy the inequality of Equation 2.3. For k = 4, the left hand side of Equation 2.3 becomes 3 — 771 3 —TO —I EM23""1- £ *') t=0 j=0 36 If m = 3, then the above expression becomes Equation 2.4 and results in 0. If m = 2, then the above expression becomes Equation 2.5 and results in —0.496. If m = 1, then the above expression becomes Equation 2.6 and results in —1.571. If m = 0, then the above expression becomes p o ( 2 3 - 2 0 - 2 1 - 2 2 - 2 3 ) + p 1 ( 2 3 - 2 0 - 2 1 - 2 2 ) + p 2 ( 2 3 - 2 0 - 2 1 ) + p 3 ( 2 3 - 2 0 ) which, after simplification, is 7#3 + 5p2 +Pi~ 7P0 (2.7) Substituting the percentages from Table 2.1, 7p3 + 5p2 + Pi — 7po = 7 x 0.041 + 5 x 0.083 + 0.166 - 7 x 0.662 = -3.766. All four cases m = 3, m = 2, m = 1, m = 0 satisfy the inequality of Equation 2.3. Similar calculations were carried out for the other three sample quadtrees. The results of the left hand side of Equation 2.3, i.e. the effective E2 — E\, are summarized in Table 2.2. From Table 2.2, it is seen that the effective Ei — E\ are non-positive in all cases, that is, Equation 2.3 is satisfied for 0 < m < 4. Therefore, any integer value in [0,4] can be chosen as the break-even point m. Theoretically, the value of m that yields the most negative effective E2 — E\, i.e. m = 0 in Table 2.2, should be chosen because it represents the greatest margin of improvement of the hybrid method over the recursive method. If m = 0 is chosen as the break-even point, no recursive subdivi-sions are needed; consequently it is sufficient to check the neighbours of the edge pixels only. However, examining the edge pixels of each node without taking advan-tage of the hierarchical nature of the quadtree structure is considered a naive 37 Table 2.2: The effective E2 — E\ using data from sample quadtrees node of g=k 1 2 3 4 5 6 7 possible m 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0 Effective E2 - Ex F 0 0 -0.496 0 -0.496 -1.571 0 -0.496 -1.571 -3.766 slantF 0 0 -0.346 0 -0.346 -1.052 0 -0.346 -1.052 -2.715 distortF 0 0 -0.263 0 -0.263 -0.928 0 -0.263 -0.928 -2.363 0 -0.263 -0.928 -2.363 -5.397 randoml 0 0 -0.254 0 -0.254 -0.979 0 -0.254 -0.979 -2.507 0 -0.254 -0.979 -2.507 -5.640 random2 0 0 -0.272 0 -0.272 -0.925 0 -0.272 -0.925 -2.333 0 -0.272 -0.925 -2.333 -5.257 0 -0.272 -0.925 -2.333 -5.257 -11.1218 0 -0.272 -0.925 -2.333 -5.257 -11.122 -22.980 randoms 0 0 -0.214 0 -0.214 -0.928 0 -0.214 -0.928 -2.444 0 -0.214 -0.928 -2.444 -5.695 38 or brute-force approach. It is therefore decided that m = 1 be chosen for the hybrid algorithm with the m = 0 case as a possibility for future research. Choosing m = 1 for the present investigation involves the following ra-tionales. First of all, the percentages from Table 2.1 merely approximate the p,'s. The percentages for g = i'm Table 2.1 only indicate the probability of finding a node of grouping factor i if a random position of the image is picked. On the other hand, p,- is the probability of finding a neighbour of grouping factor i for a node with g > i. Considering locations of the nodes within an image is important in estimating the p^s. Secondly, as can be seen from Figures 2.4 to 2.9, frequently nodes have neighbours of equal size or quarter of the size. For neighbours of equal size, the first neighbour finding operation that is always performed will take care of the case. For neighbours quarter of the size, one recursive subdivision, which corresponds to m = 1, suffices. Lastly, Table 2.2 shows that m = 1 yields the second most negative effective E2 — E\, only behind the m = 0 case. Since m = 1 is chosen, no subdivision is really necessary. With a specially designed data structure, recursion can be eliminated altogether. Besides the four corners SW (south-west corner), SE (south-east corner), NE (north-east corner), and NW (west-west corner), the edge pixels of a node are divided into eight sections: Si (part 1 of south edge), S2 (part 2 of south edge), E l (part 1 of east edge), E2 (part 2 of east edge), Nl (part 1 of north edge), N2 (part 2 of north edge), Wl (part 1 of west edge), W2 (part 2 of west edge), as shown in Figure 2.10. The neighbour types of a node for each of these eight edge sections are stored in an auxiliary data structure. For example, referring to the node P in Figure 2.3, 39 NW W2 Wl SW Nl N2 SI S2 NE E2 El SE Figure 2.10: Sections of the edge of a node 40 • both SI and S2 have white neighbours; • both Nl and N2 have black neighbours; • El has a white neighbour and E2 has a black neighbour; • both Wl and W2 have grey neighbours. A particular corner of a node inherits the neighbour types from those of the adjacent edge sections. For example, the types of the north and west neighbours of the corner NW are the same as the neighbour types of Nl and W2 respectively. A bit vector, named snt, short for sub-neighbour type, is used as the auxiliary data structure for the purpose of storing the neighbour type in-formation. Two bits are allocated for each of the eight sections, thus an unsigned 16-bit integer is sufficient for storage. The binary values assigned for the neighbour types are: • 00 for unset; • 01 for white; • 10 for grey; • 11 for black. Figure 2.11 shows snt for the node P in Figure 2.3. 2.4 The complete algorithm After the ideas of an ordered generation of the edge pixels and non-recursion have been explained in the previous sections, the complete new algorithm 41 N2 N1 W2 W1 S2 S1 E2 E1 11 11 10 10 01 01 11 01 where 00 - unset 01 - white 10 - grey 11 -- black Figure 2.11: The snt vector of the node P in Figure 2.3 42 will now be described. Pseudocodes and/or descriptions for the various routines of the new algorithm are presented. The C codes are listed in Appendix A. 2.4.1 T h e main routines The main() routine performs the disk I/O. Its major role is to invoke the routine BorderFind( ) for each of the input nodes and to initialize all snt bit vectors to zero. Borde rF ind( ) : /* Purpose: find the border pixels of the current node */ FOR the four directions of current node DO IF snt is unset THEN CALL SetsntO ENDIF ENDFOR IF the current node is a pixel THEN IF all fields of snt are black THEN /* the current node is an internal pixel, ignore it */ RETURN ELSE /* the current node is a border pixel */ copy the current node into the output array 43 ENDIF ELSE IF the current node i s a 2x2 node THEN CALL TwoByTwoBorderO ELSE CALL NonTrivialBorderO ENDIF :end of BorderF indQ 2.4.2 The routines for sett ing the snt bit vector The section contains the routines that find neighbours and set the snt bit vector accordingly. Setsnt ( ) : /* Purpose: set snt according to neighbour types */ CALL Neighbour() CALL NeighbourCheckO set the fields of snt to black, white, or grey :end of Setsnt() Neighbour(): calculate the location code of the neighbour of equal size :end of Neighbour() 44 The method of calculating the location code of the neighbour of equal size is that of dilated integer arithmetic [Schr 92], see Appendix A. Neighbour C heck( ): determine the type of the neighbour: black/white/grey :end of NeighbourCheck() The implementation of NeighbourCheck() is based on the binary search and the rules stated in [Yang 90], see Appendix A. 2.4.3 T h e routines for checking nodes larger than size 2 x 2 Any nodes larger than 2 x 2 require careful processing and are considered nontrivial. NonTrivialBorder( ): CALL SWBorderO CALL SEBorderQ CALL NWBorderO CALL NEBorderO :end of NonTrivialBorder() SWBorde r ( ) : /* Purpose: find the border pixels in the south-west quarter of the current node */ 45 IF SI and Wl fields of snt are both black THEN /* the edge pixels in the south-west quarter are all internal */ RETURN ELSE /* traverse the edge pixels of the south-west quarter */ IF diff.border.LUTCg] is null THEN /* the first time a node of grouping factor g is encountered */ initialize diff.border_LUT[g] ENDIF FOR each edge pixel in the SW quarter of current node DO IF OnBorderO THEN copy this pixel into the output array ENDIF ENDFOR ENDIF :end of SWBorder() OnBorder(): /* Purpose: determine whether the current edge pixel 'cepix' is on the border */ 46 IF snt for cepix indicates at least one white neighbour THEN RETURN TRUE ELSE IF snt for cepix indicates all neighbours are black THEN RETURN FALSE ELSE /* cepix is on the part of edge/corner that has grey neighbour(s) */ CALL Neighbour() CALL NeighbourCheckO IF the particular neighbour of cepix is white THEN RETURN TRUE ELSE RETURN FALSE ENDIF ENDIF :end of OnBorder ( ) Note that the check of the Si and Wl fields essentially replaces recursion. The lookup table diff_border_LUT[g] is used to generate the edge pixels of the south-west quarter. It is also used to determine on which side, SI, Wl , or SW, the current edge pixel lies. The other three routines SEBorder() , N W B o r d e r ( ) , and NEBor -der() follow basically the same procedure as that of SWBorde r ( ) . The differences lie in which portions of the snt bit vector and the lookup table diff_border_LUT[g] are used. 47 2.4.4 T h e routine for checking 2 x 2 nodes This section contains the routine that handles 2 x 2 nodes as a special case. It is treated as a special case because 1. examining the pixels of a 2 x 2 node is trivial and there is no need to use diff_border_LUT[l]; 2. if all four pixels of the 2 x 2 node are on the border, they should be output as a single node instead of four individual pixels. T woBy T woBorder( ) : /* Purpose: find the border pixels of the current 2x2 node using the information in snt */ IF all four pixels are on the border THEN copy the current node into the output array ELSE FOR each pixel in the current node DO IF the pixel is on the border THEN copy the pixel into the output array ENDIF ENDFOR ENDIF :end of TwoByTwoBorder() To determine whether a pixel is on the border, the information previously acquired in snt is used. For example, if the pixel examined is at the north-48 east corner, then the N2 and E2 fields of snt are checked. If both of these two fields are black, that means the north and the east neighbours of the north-east corner pixel are black and hence the pixel is not on the border. 2.5 Further acceleration The new algorithm is superior to the one by [Yang 90] in two aspects: 1. The border pixels of a PB-quadrant can be generated in sorted order without the need for an insertion sort. 2. The number of neighbour finding operations is reduced by avoiding recursion. Since there is no recursion involved, the overhead associated with han-dling recursive calls is eliminated. Unnecessary neighbour finding operations in the recursive method are avoided as well. For example, while checking the type of the east neighbour for the node P in Figure 2.3, the first neighbour finding operation determines that the east neighbour of equal size is grey. The recursive algorithm hence subdivides the node into its four children. The children involved in deter-mining the east neighbour type are the south-east quarter and the north-east quarter. Each of these two child nodes will incur four more neighbour find-ing operations for the four directions. However, the west and the south neighbour checks for the north-east child node are unnecessary because its siblings are always black5. Similarly, the north and west neighbour checks for the south-east child node are not necessary. 5 Recall that the current node considered is an input node and thus is black by definition. 49 The above improvements are obtained at the expense of auxiliary data structures and information keeping, e.g. the snt bit vector and the lookup tables diff_border_LUT. Further acceleration is possible. Consider again the node P in Figure 2.3. When the north neighbour Q is checked and determined to be black, the Nl and N2 fields of the snt of P are set to black. But it is also clear that the south neighbour of Q is black. If the SI and S2 fields of the snt of Q are set to black while examing P, there is no need to check the south neighbour of Q later on. 50 Chapter 3 Algorithm Correctness 3.1 Applicability of the algorithm The new algorithm accepts as input a linear quadtree and outputs the border pixels as a linear quadtree. The border pixels produced are 8-connected. An input image may consist of a single region or of multiply connected regions. Holes in an image are also allowed. 3.2 Verification of the algorithm The routine BorderFind() examines each input node in turn, thus all pos-sible border pixels will be visited. Holes in the image are therefore found as well in contrast to contour tracing algorithms such as the one of [Dyer 80] which cannot process holes and multiply-connected regions unless a seed is given for each border. A border pixel must be an edge pixel (the converse is not necessarily true), hence, it is only necessary to examine the edge pixels of the input 51 nodes. An invariant is established to verify the correctness of the algorithm: Invariant An edge pixel is on the border of the input quadtree if it has at least a white neighbour in one of its four directions: east, south, west, and north. Each input node is associated with a snt bit vector, storing the types of the sub-neighbours in the four directions as shown in Figures 2.10 and 2.11. There are eight sections representing the eight sub-neighbours, two for each direction. For example, SI faces the sub-neighbour which is the north-west child of the south neighbour; N2 faces the sub-neighbour which is the south-east child of the north neighbour. The values of snt provide the information for determining the neighbour types of the edge pixels. The correctness of the routines for setting snt is based on the rules described in [Yang 90] (see Appendix A) and the binary search algorithm. After the snt fields are properly set, the input nodes are classified into three classes and are checked separately. They are: • pixel nodes, • 2 X 2 nodes, and • non-trivial nodes, i.e. those that are larger than 2 x 2 . For pixel nodes, the only edge pixel is the node itself. Any two adjacent sections of the snt vector on the same side of the node contain the same value. For example, if the node in Figure 2.10 represents a pixel node, then the SI and S2 sections contain the same value, either black or white. It is impossible for SI and S2 to contain different snt values because a pixel cannot have a grey neighbour. 52 For the 2 x 2 class, the edge pixels are its four pixels; there are no non-edge pixels in the node. The width of each of the eight edge sections in a 2 x 2 node is that of a pixel, therefore El and E2, for example, can contain black and white respectively, meaning that the east neighbour is grey. However, no grey neighbour is possible for any of the eight sub-neighbours, i.e. El cannot contain grey value, neither can E2, since they are of pixel width. The invariant is therefore not violated for the first two classes by checking the snt vector of each node. There will be no unresolved cases, i.e. grey sub-neighbours. The sub-neighbour types of black or white are sufficient to determine whether a pixel of a node is a border pixel. For example, if the W2 section of the snt vector of a 2 x 2 node contains the value 01, it means that the W2 sub-neighbour, which is the north-east child of the west neighbour, is white. Thus, the north-west pixel of the 2 x 2 node is a border pixel. For nodes larger than 2 x 2 , four subroutines will handle the edge pixels of the node. It is only necessary to consider the subroutine handling the south-west quarter for the correctness of the algorithm for the non-trivial class since the other three quarters (south-east, north-west, and north-east) have a structure similar to that of the south-west subroutine. The south-west subroutine SWBorder() uses the values in the Si and Wl sections of the snt vector. If both SI and Wl contain the value 11, then all the edge pixels in the south-west quarter have black neighbours, no further processing is necessary. Otherwise, the individual edge pix-els are traversed, using the lookup table diff_border_LUT[g], to determine whether they are adjacent to black, grey, or white neighbours. If the cur-rent edge pixel traversed is on the section Si, say, where its corresponding 53 sub-neighbour is • black, then the current edge pixel is not a border pixel; • white, then the current edge pixel is a border pixel; • grey, then neighbour finding in the south direction is invoked for the current edge pixel to determine whether its south neighbour is white. 3.3 Experimental verification Various linear-quadtree images were used as input test data; six of them and their borders are shown in Figures 3.1 to 3.12. Careful examination of the figures shows the correctness of the algorithm. 54 Figure 3.1: Quadtree F 55 Figure 3.2: Borders of Quadtree F 56 Figure 3.3: Quadtree slantF 57 Figure 3.4: Borders of quadtree slantF 58 Figure 3.5: Quadtree distortF 59 9S Figure 3.6: Borders of quadtree distortF Figure 3.7: Quadtree randoml 61 Figure 3.8: Borders of quadtree randoml 62 Figure 3.9: Quadtree random2 63 Figure 3.10: Borders of quadtree random2 64 Figure 3.11: Quadtree random3 65 Figure 3.12: Borders of quadtree random3 66 Chapter 4 Algorithm Performance 4.1 Time complexity analysis Based on the analysis of their algorithm in [Yang 90], Yang & Lin stated that the average number of neighbour finding operations for any given node is a constant. Each neighbour finding operation requires a binary search which is O(log N) where N is the number of nodes in the input quadtree. Thus, the algorithm would run in time 0(N log N) on average. However, if predict-binary search, which is 0(1) on average, is used instead of binary search, then their algorithm runs in 0(N) on average. The new algorithm also visits each of the N nodes. From the proba-bilistic analysis of Section 2.3, the new algorithm requires, on average, a smaller number of recursive subdivisions, and hence less neighbour finding operations, for a given node. Theoretically, the new algorithm also runs in O(N) on average if predict-binary search is used. 67 4.2 Runtime and profile 4.2.1 The implementation and run-time environment The competing algorithm is that of Yang & Lin [Yang 90]. In order to compare the two algorithms, both were implemented in C and compiled using gcc with the optimization flag set. They were run on a SPARC IPX using the Unix system call t imes() for the timing results1 and the command gprof for profiling the number of neighbour finding operations incurred. There are two implementation details which are unclear in [Yang 90]. 1. How is the predict-binary search implemented? 2. How are the border pixels of a PB-quadrant inserted, in sorted order, into the output linear quadtree? Binary search, instead of predict-binary search, was used in both algo-rithms for the purpose of finding neighbours. Thus for comparison purposes, especially if the focus is in reducing the number of neighbour finding oper-ations, the search method used is irrelevant. A quick-sort routine was implemented for the second question because an insertion-sort routine would be too costly to use for an array implemen-tation of the linear quadtree. However, which sorting method is used for the problem does not affect the number of neighbour finding operations in-curred because outputting the border pixels of a PB-quadrant occurs after all neighbours have been found. Besides, the new algorithm does not require any kind of insertion or sorting, which is in principle an advantage. 1For a comprehensive illustration of the use of t imes( ) , see Section 8.16 of [Stev 92]. 68 It is also noted that there is an error in the [Yang 90] algorithm. Consider the 2 x 2 node (60,1) with its black neighbours shown in Figure 4.1. The node is not considered a PB-quadrant and hence its four pixels are processed individually. The four pixels are all border pixels; however, they are not output as a single node, i.e. there is a need for condensation. Such an input node is handled correctly by the TwoByTwoBorder() routine in the new algorithm. The new algorithm has been implemented in two versions, one with the additional acceleration of setting some fields of snt of the opposite black node, as described in Section 2.5. The other, tang, is without the additional acceleration. The first implementation is referred to as atang. The reason for the separate implementation is to isolate the non-recursive feature of the new algorithm in tang in order to determine clearly that the improvement, in terms of reducing the number of neighbour finding operations, stems mainly from the probabilistic analysis that leads to non-recursion. The implementation of the algorithm in [Yang 90] will be called yl. 4.2.2 The results Tables 4.1 to 4.3 show the performance of each program. Note that the symbol g represents the term grouping factor and NB is short for neighbour finding operations. Tables 4.4 and 4.5 show the percentage improvements of the new algo-rithm over the one in [Yang 90]. 69 57 148 60 55 106 Figure 4.1: A 2 x 2 node where yl fails to condense 70 Table 4.1: Performance of the program yl resolution # of input nodes # of border nodes max. g user CPU (sec.) sys CPU (sec.) # o f N B F 8 580 697 4 0.15 0.02 8112 slantF 8 633 719 4 0.17 0.03 9236 distortF 8 1174 900 5 0.32 0.02 16888 randoml 8 1545 1472 5 0.40 0.01 21204 random2 10 7385 8513 7 2.33 0.12 108923 random3 8 3097 2766 5 0.78 0.03 37892 Table 4.2: Performance of the program tang resolution # of input nodes # of border nodes max. g user CPU (sec.) sys CPU (sec.) # o f NB F 8 580 697 4 0.09 0.01 3115 slantF 8 633 719 4 0.10 0.02 3617 distortF 8 1174 900 5 0.19 0.01 6904 randoml 8 1545 1466 5 0.27 0.01 8890 random2 10 7385 8507 7 1.40 0.05 45615 random3 8 3097 2739 5 0.48 0.03 16597 Table 4.3: Performance of the program atang resolution # of input nodes # of border nodes max. g user CPU (sec.) sys CPU (sec.) # o f N B F 8 580 697 4 0.08 0.01 2324 slantF 8 633 719 4 0.09 0.02 2729 distortF 8 1174 900 5 0.17 0.01 5440 randoml 8 1545 1466 5 0.22 0.02 6923 random2 10 7385 8507 7 1.25 0.05 36268 random3 8 3097 2739 5 0.42 0.03 12353 Table 4.4: Percentage improvement of tang over yl CPU (user & sys) # o f N B F 41% 62% slantF 40% 61% distortF 41% 59% randoml 32% 58% random2 41% 58% random3 37% 56% 73 Table 4.5: Percentage improvement of atang over yl CPU (user & sys) # o f NB F 47% 71% slantF 45% 70% distortF 47% 68% randoml 41% 67% random2 47% 67% random3 44% 67% 4.2.3 Confidence interval It would require more than 400 sample linear quadtrees for a 95% confidence interval on the performance comparison to reach a sampling error of ±5% [Kell 89], which is beyond the time frame for the current research. Therefore, a plot of the run-time or number of neighbour finding operations versus resolution is not appropriate. From Tables 4.1 to 4.5, it is clear that the new algorithm has reached the goal which was set out to achieve: reducing the number of neighbour finding operations. From Tables 4.4 and 4.5, it can be seen that the tang implementation achieves over 50% reduction in the number of neighbour finding operations, while the atang implementation achieves over 60%. The additional accel-eration thus yields approximately a 10% advantage. It is also clear from the tables that the overhead of auxiliary data struc-tures does pay off as the run times of the new algorithm, in either implemen-tation, is better than the one by Yang & Lin, viz. 30% to 40% improvement. There are cases for which the new algorithm incurs more neighbour find-74 Figure 4.2: A case that atang performs poorer than yl ing operations than that of Yang & Lin. Consider the quadtree with reso-lution 7 in Figure 4.2, the number of neighbour finding operations is 74 for both atang and tang, whereas yl only incurs 51. However, the same con-figuration but with resolution 6 produces the opposite result: 42 neighbour finding operations for tang and atang and 51 for yl. A worst case for the new algorithm, as suggested by Figure 4.2, is when a node of grouping factor 6 or larger has neighbour nodes of grouping factor 2 less (not 1 less, not 3 less). The new algorithm prevails when an image has more pixels in general, which is also apparent from Equations 2.5 to 2.7 in that po is larger with more pixels in the image. From the sample random 75 quadtrees, this favorable case seems to be common. 76 Chapter 5 Conclusion &; Future Directions A new border finding algorithm for linear quadtree based images is pre-sented. It is able to generate the border pixels in sorted order and avoids sorting and recursion. By avoiding recursion, the new algorithm succeeds in reducing the number of neighbour finding operations when compared to the Yang & Lin algorithm which is based on recursion. The overhead incurred pays off as the run time of the new algorithm is also better in the sample test cases. Future directions for the research could include 1. More sample quadtrees shall be used for testing, which would require a more robust and versatile random border generator. 2. Implement an algorithm with m = 0 as discussed in Section 2.3. With m = 0, there is no need for the snt bit vector. Thus both the program space and the heap space can be reduced; however, whether it will be 77 faster is still unknown. 3. Extend the new algorithm to linear octree based 3D images. The idea of snt and thus non-recursion is directly applicable to linear octrees. However, generating the edge pixels in sorted order would require a 3D model of a node with grouping factor 4 to help visualize the edge pixels. 4. Extend the new algorithm to grey scale or colour images. 5. Consider the possibility of converting the algorithm for parallel pro-cessing. 78 Chapter 6 Glossary E l The first section of east, see Figure 2.10 E2 The second section of east, see Figure 2.10 g Grouping factor LUT Lookup table loc Location code N l The first section of north, see Figure 2.10 N2 The second section of north, see Figure 2.10 N E North-east N W North-west P B Proper border Pi Probability of finding a neighbour with grouping factor i. 79 51 The first section of south, see Figure 2.10 52 The second section of south, see Figure 2.10 SE South-east S W South-west snt Sub-neighbour type, see Figure 2.11 W l The first section of west, see Figure 2.10 W 2 The second section of west, see Figure 2.10 80 Bibliography [Atki 84] Atkinson, H.H., I. Gargantini, M.V.S. Ramanath. Determina-tion of the 3D border by repeated elimination of internal surfaces, Computing, 32, 4, pp. 279-295 (October 1984). [Atki 85] Atkinson, H.H., I. Gargantini, M.V.S. Ramanath. Improve-ments to a recent 3D-border algorithm, Pattern Recognition, 18, 3-4, pp. 215-226 (March 1985). [Dill 88] Dillencourt, M.B., H. Samet. Extracting region boundaries from maps stored as linear quadtrees, Proceedings Third In-ternational Symposium on Spatial Data Handling, Sydney, Aus-tralia, pp. 65-77 (August 1988). [Dyer 80] Dyer, C.R., A. Rosenfeld, H. Samet. Region representation: boundary codes from quadtrees, Communications of ACM, 23, 3, pp. 171-179 (March 1980). [Fran 91] Franciosa, P.G., E. Nardelli. A guaranteed approximation algorithm for on-line computing quadtree border, Geo-graphic Database Management Systems, Workshop Proceedings, Capri, Italy, pp. 245-257 (May 1991). 81 [Garg 82] Gargantini, I. An effective way to represent quadtrees, Communications of ACM, 25, pp. 905-910 (1982). [Kell 89] Kelly, B., B. Alexander, P. Atkinson, J. Swift. Mathematics 11, British Columbia Edition, Addison-Wesley (1989). [Li 84] Li, S.-H., M.H. Loew. Boundary chain codes from quadcode-trees, Proceedings IEEE Workshop on Computer Vision, Repre-sentation and Control, Annapolis, MA, pp. 178-182 (April 1984). [Pavl 82] Pavlidis, T. Algorithms for Graphics and Image Processing, Com-puter Press (1982). [Qian 89] Qian, K., P. Bhattacharya. A polynomial approach to image processing and quadtrees, IEEE Eighth Annual International Phoenix Conference Proceedings of Computers and Communica-tions, pp. 596-600 (1989). [Rose 82] Rosenfeld, A., A.C. Kak. Digital Picture Processing, 2nd ed., Aca-demic Press (1982). [Same 90] Samet, H. Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading, MA (1990). [Schr 92] Schrack, G.F. Finding neighbours of equal size in linear quadtrees and octrees in constant time, CVGIP: Image Un-derstanding, 55, 3, pp. 221-230 (May 1992). [Stev 92] Stevens, W.R. Advanced Programming in the UNIX Environment, Addison-Wesley (1992). 82 [Yang 90] Yang, S.-N., T.-W. Lin. A new 3D border algorithm by neighbour finding, Proceedings Fourteenth Annual International Computer Software and Applications Conference, Chicago, IL, pp. 353-358 (October 1990). Appendix A Program Listing The complete program listing for the new border finding algorithm is in-cluded in the appendix. However, the main ideas used to implement the routines NeighbourCheck() and Neighbour() are explained first. Let LQT be the set of all linear quadtree nodes. Define the d-edge of a quadrant Q to be the unique edge of Q in the direction d 6 {N,S,E,W}. The quadrant Qd is the d-neighbour of quadrant Q if it has the same size as Q and the d-edge of Q is shared by the d-edge of Qd, where d is the opposite direction of d in usual sense. If Qd is white, then Q has a white neighbour Qd and therefore its d-edge is a border edge. If Qd is grey, then Qd contains at least one proper sub-quadrant Q* in the linear quadtree. Therefore in this case, Q has a grey neighbour Qd and Q has a sub-neighbour Q*. If Qd is black then either Qd is a linear quadtree node or Qd is properly contained in a super-quadrant Q* of the linear quadtree. For the former case Qd is called an exact neighbour of quadrant Q and the latter case Q* is called a super-neighbour of quadrant Q. The least upper bound of a quadrant Q is 84 defined to be lub(Q) = min{B € LQT : Q < B}. The greatest lower bound of Q is defined to be glb(Q) = max{B G LQT :B<Q}. Yang & Lin made a few observations in [Yang 90] that help determine the type of a neighbour and facilitate the implementation of the routine NeighbourCheck( ). 1. Let Q € LQT and its d-neighbour be Qd- Then glb(Qd) is a super-neighbour if and only if glb(Qd) ^ Qd and glb(Qd) ^Qdi1 4>-2. Let Q € LQT and its d-neighbour be Qd- Then lub(Qd) is a sub-neighbour if and only if Qd is a grey node. 3. Let the grouping factors of quadrants Q\ and Q2 be g\ and g2 respec-tively. Then Qi C Q2 if (a) g\ < 02, and (b) loc\ © /0C2 < 452, where loc\ and /0C2 are the location codes of Q\ and Q2 respectively, and © is the exclusive OR operator. Schrack formulated a few theorems in [Schr 92] that allow efficient calcu-lation of neighbour codes of equal size and thus facilitate the implementation of the routine Neighbour(). Theorem 1 Let quad location addition ©? be the separate addition of the x- and y-components of a linear quadtree node nq and of a translation incre-ment (relative coordinates) Anq, and the recombination of the results into a location code. Then nq ®q An, = (((nq \ ty) + (Ang A tx)) A tx) \ (((n, | tx) + (Anq A ty)) A ty), 85 where tx = X ^ o ^ S ty = tx <£. 1, and <C, |, A are the machine left shift, OR, AND operators respectively. Theorem 2 Given a location code nq and its level I, the eight neighbours of equal size (level I) are given by mq = nq ®q (An; < (2(r - 1))), * = 0 , . . . , 7, where ©? is the quad location addition operator, An,- are the eight basic direction increments that are encoded as location codes, <C is the machine left shift operator, and r is the (fixed) resolution. 86 Jul 21 199413:39:11 program-listing »*** qutil.h ************************** * Header file for quadtree-related problems * Date By * 1994Febll S.K.Tang V /* dimer •define slon is 2D for DIM 2 quadtree /* default number of nodes for tdefine •define DEFAULT_NUM_IN _NODES DEFADLT_NUM_ODT_NODES /* location code type typedef long int /* boolean type */ typedef •define •define /* node typedef typedef char TRUE 1 FALSE 0 of a quadtree unsigned int struct { LocCode int int snt_type ) QtNode; /* values for snt_type •define •define •define •define •define tdefine •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define •define E1_WHITE E1_GRAY E1_BLACK E2_WHITE E2_GRAY E2_BLACK S1_WHITE S1_GRAT S1_BLAC!C S2_WHITE S2_GRAY S2_BLACK H1_WHITE W1_GRAY W1_BLACK W2_WHITE W2_GRAY W2_BLACK N1_WHITE N1_GRAY N1_BLACK N2 WHITE N2_GRAY N2_BLACK ONSET MATCH_COLOR(t, ALL_HHITE(t) ALL_BLACK(t) /* a quadtree */ typedef struct { QtNode '/ LocCode Boolean V Comment Created */ Input and output quadtrees */ 2000 1000 snt_type; loc; lev; gf; snt; /* location code */ /* level: lev-resolution for pixel, lev-0 for root */ /* grouping factor: gf-0 for pixel, gf-resolution for root */ /* bit vector for sub-neighbour type*/ (see 4/1/94 research note) */ 0x0001 0x0002 0x0003 0x0004 0x0008 0x000c 0x0010 0x0020 0x0030 0x0040 0x0080 OxOOcO 0x0100 0x0200 0x0300 0x0400 0x0800 OxOcOO 0x1000 0x2000 0x3000 0x4000 0x8000 OxcOOO 0x0000 /* does m,c) the m portion of snt t matches color c */ (((t) £ (m)) -- (c)) /* is snt t all WHITE */ ((t) -- 0x5555) /* Is snt t all BLACK */ •node; ((t) ~ Oxffff) /* nodes of the quadtree. Pagel Jul 21 199413:39:11 long int size; program-listing should be pointer to array of QtNode */ /* t of QtNode in quadtree */ long int allocated; /* I of QtNode allocated */ ) Qt; /* integral Cartesian point */ typedef struct ( long int v[DIH] ) Point; /* neighbour directions */ typedef int DlrType; •define EAST 0 •define NORTH_EAST 1 •define NORTH 2 tdefine NORTH_WEST 3 •define WEST 4 tdefine SOOTH WEST 5 tdefine SOOTH 6 tdefine SO0TH_EAST 7 /* neighbour types */ typedef int NeiType; tdefine BLACKJEXACT 0 tdefine BLACK_NOTEXACT 1 tdefine WHITE 2 tdefine GRAY 3 /» is tdefine ISJBLACK(nt) (((nt) — /* black and exact neighbour */ /* black and not exact neighbour */ /* white neighbour */ /* gray neighbour */ the neighbour type nt black */ 8LACK_EXACT ) II ( ( nt) ~BLACK_NOTEXACT ) ) /* sub-border sections (see 4/1/94 research note) */ typedef Int SubBorderType; •define E1W2 0 tdefine SW 1 tdefine SI 2 tdefine Wl 3 tdefine S2 4 tdefine SE 5 tdefine El 6 tdefine W2 7 tdefine NW 8 tdefine Nl 9 tdefine E2 10 tdefine N2 11 tdefine NE 12 tdefine SIZE_OF_SubBorderType /* an edge pixel of a node */ typedef struct { LocCode loc; SubBorderType sb; 1 BorPix; / f t * * * * * * * * * * * * * * * * * * * * * * * * * * * * 13 /* loc. code of this edge pixel */ /* sub-border direction of this pixel */ newborder. c *************************** * A new border finding algorithm by Tang and Schrack * Date by * 1994Apr5 tang * 1994May26 tang */ •include <stdio.h> • include <sys/times. h> • include * . ./header/qutil.h" /* externals */ extern long int res; extern LocCode *pow4; Comment Created Use PrTimes() for timing /* resolution */ /* pow4[l] - 4-(res-i) */ /* differences of loc. codes of node edge */ extern BorPix **dlff_border_LOT; Page 2 Jul 21 199413:39:11 program-listing Page 3 extern QtNode Neighbour!); extern NeiType NeighbourCheck(); extern void PrTimes(); void Init( inp, outp, in_fp, out_fp ) Qt *inp; /* input quadtree */ Qt *outp; /* output quadtree */ FILE *in_fp; /• input file pointer »/ FILE *out_fp;/* output file pointer */ /* --- -* Reading input quadtree and initialize various data structures ( ] */ GetInputOt( inp, in_fp ); AllocOutputQt( outp, out_fp ); InitPow4(); InitMask(); InitCoding(); InltNeighbourLOT<); InitBorder(); void SetNeighboursntBLACK( dir, DirType dir; long int npos; Qt *inp; /* npos, inp ) /* neighbour direction */ /* current neighbour position */ /* input quadtree */ Set be the sub-neighbour type opposite to the direction dir to BLACK for the neighbour node inp->node[npos] switch( dir ) ( case EAST: if ( MATCH_COLOR(inp->node(npos).snt, W1_BLACK,ONSET) ) { inp->node[npos].snt |-W1_BLACK; lnp->node[npos).snt |-W2_BLACK; } break; case SOUTH: if ( MATCH_COLOR(inp->node(npos].snt, N1JBLACK,ONSET) ) { lnp->node[npos].snt |- N1_BLACK; inp->node[npos].snt j- N2_BLACK; 1 break; case WEST: if ( MATCH_COLOR(inp->nodetnpos).snt, E1_BLACK, ONSET) ) { inp->node[npos].snt I- E1_BLACK; inp->nodejnpos].snt I- E2_BLACK; } break; case NORTH: if ( MATCH_COLOR(inp->node[npos] .snt, S1_BLACK, ONSET) ) { inp->node(npos].snt |- S1_BLACK; inp->node[npos].snt j- S2_BLACK; } break; void SetsntBLACK( dir. DirType long int Qt unsigned int cip. dlr; cip; *inp sub; inp, sub ) /* neighbour direction */ /* current input position */ ; /* input quadtree */ /• sub-segment 1 or 2 (other # for both) */ * Set sub-neighbour type in direction dir to be BLACK * for the current node inp->node[cip] Jul 21199413:39:11 program-listing switch( dir ) t case EAST: if ( sub -- 1 ) { inp->node[cip].snt ) else if ( sub ~ 2 ) { inp->node[cip].snt J else [ inp->node[cip].snt inp->node[cip].snt } break; case SOOTH: if ( sub — 1 ) { inp->node[cip].snt ] else if ( sub — 2 ) { inp->node[cip).snt ) else { inp->nodetcip].snt inp->node[cip].snt ] break; case WEST: if ( sub — 1 ) { inp->node[clp].snt ] else if ( sub -- 2 ) [ inp->node[cip].snt ] else { inp->node[cip].snt inp->node[cip].snt ) break; case NORTH: if ( sub — 1 ) { inp->node[cip].snt ) else if ( sub — 2 ) ( inp->node[cip].snt ] else t inp->node[cip].snt inp->node[cip].snt ) break; ] ) void SetsntGRAT( dir, cip, inp, sub ) |- E1_BLACK; - E2_BLACK; I- El BLACK; - E2_BLACK; |- S1_BLACK; |- S2_BLACK; I- S1_BLACK; |- S2_BLACK; |- W1_BLACK; I- W2_BLACK; |- W1_BLACK; |- W2_BLACK; |- N1_BLACK; |- N2_BLACK; I- N1_BLACK; |- N2_BLACK; DirType dir; /* neighbour direction */ long int cip; /* current input position */ Qt *inp; /* input quadtree * unsigned int sub; /* sub-segment 1 or / 2 (other • for both) */ yt * Set sub-neighbour type in direction dir to be GRAT * for the current node inp->node[cip] */ { switch! dir ) { case EAST: if ( sub — 1 ) t inp->node[cip].snt } else if ( sub ~ 2 ) { inp->node[cip].snt ) else ( inp->node[cip].snt inp->node(cip].snt ] break; case SOOTH: if ( sub — 1 ) { inp->nodefcip].snt } else if ( sub — 2 ) ( . inp->node[cip).snt ) else ( |- E1_GRAT; 1- E2_GRAT; I- E1_GRAT; |- E2_GRAY; |- S1_GRAY; 1- S2_GRAT; Page 4 Jul 21199413:39:11 program-listing Page5 inp->node(cipl.snt |- S1_GRAY; inp->node[cipl.snt I- S2_GRAY; ) break; case WEST: if ( sub — 1 ) t inp->node[cip].snt |-W1_GRAY; } else If ( sub — 2 ) { inp->node[cip].snt |-W2_GRAY; ) else ( lnp->node[cip].snt |-W1_GRAY; inp->node[cip].snt |-W2_GRAY; ) break; case NORTH: if ( sub ™ 1 ) { lnp->node[cip].snt I- N1_GRAY; ] else If ( sub — 2 ) [ inp->node[cipj.snt I- N2_GRAY; } else ( inp->node[clp).snt I- N1_GRAY; inp->node[cip].snt |- N2_GRAY; ) break; ) void SetsntWHITE( dir, cip, lnp, sub ) DirType dir; /* neighbour direction */ long int cip; /* current input position */ Qt *inp; /* Input quadtree */ unsigned int sub; /* sub-segment 1 or 2 (other t for both) */ /* " " - -* Set sub-neighbour type in direction dir to be WHITE * for the current node inp->node(cipl <° ( ' switch; dlr ) { case EAST: if ( sub — 1 ) ( inp->node[cip].snt |- E1_WHITE; } else if ( sub — 2 ) ( inp->node{cip).snt I- E2_WHITE; } else { inp->node(cip].snt I- E1_WHITE; inp->node[cip).snt |- E2_WHITE; } break; case SOOTH: if ( sub — 1 ) ( inp->node(cip].snt |- S1_WHITE; } else if ( sub — 2 ) ( inp->node[cip].snt |- S2_WHITE; } else ( lnp->node[cip].snt |- S1_WHITE; inp->node[cip].snt I- S2_WHITE; } break; case WEST: if ( sub ~ 1 ) { inp->node[cipl.snt |- W1_WHITE; ) else if ( sub ~ 2 ) { inp->node(cip].snt I- W2_WHITE; } else ( inp->node[cip).snt |-W1_WHITE; inp->node[cip].snt I- W2_WHITE; } break; case NORTH: if ( sub — 1 ) { inp->node[clpl.snt |- N1_WHITE; ) else If ( sub « 2 ) ( Jul 21 199413:39:11 program-listing Page 6 } else ( inp->node[cipl.snt |- N2_WHITE; t inp->node[clpl.snt |-N1_WHITE; inp->node[cip].snt |-N2_WHITE; old SetChildsnt( dir. DirType long int Qt QtNode unsigned int cip, lnp dir; cip; *inp; q; sub; . q /* /* /* /* /* sub ) neighbour direction */ current input position */ input quadtree */ a child node */ sub-segment 1 or 2 (other t for both) */ * Set the sub-neighbour type for child q in the direction dir * (which correspond to sub-segment sub in direction dir) QtNode NeiType long int n; nt; npos } /* neighbour node */ /* neighbour type */ /* index position of neighbour if in inp */ n - Neighbour ( q, dir ); nt - NeighbourCheck( q, n, dir, inp, &npos ); switch( nt ) ( case WHITE: SetsntWHITE( dir, cip, inp, sub ); break; case GRAY: SetsntGRAY( dir, cip, inp, sub ); break; case BLACK_EXACT: SetNeighboursntBLACK( dir, npos, inp ); case BLACK_NOTEXACT: SetsntBLACK( dir, cip, inp, sub ); break; } void CheckSubNeighbours( dir, cip, DirType dir; /< long Int cip; /< Qt *inp; /< /* inp ) neighbour direction */ current input position input quadtree */ * Check the sub-neighbours of current node inp->node{cip] to * set their sub-neighbour types */ { LocCode QtNode loc; q; location code of current node a child node */ loc - inp->nodetcip].loc; q.lev - inp->node[cip].lev + 1; q.gf - inp->node[cip].gf - 1; switch( dir ) t case EAST: q.loc - loc + pow4(q.lev]; SetChildsntf dir, cip, inp, q, 1 ); q.loc - loc + 3*pow4[q.lev]; SetChildsnt( dir, cip, inp, q, 2 ); break; case SOUTH: q.loc - loc; SetChildsnt( dir, cip, lnp, q, 1 ); q.loc - loc + pow4 [q.lev]; SetChildsnt( dir, cip, inp, q, 2 ); break; case WEST: q.loc - loc; Jul 21 1994 13:39:11 program-listing Page 7 SetChlldsnt( dir, cip, inp, q, 1 ),-q.loc - loc + 2*pow4[q.lev]; SetChildsnt( dir, cip, inp, q, 2 ); break; case NORTH: q.loc - loc + 2*pow4[q.lev]; SetChildsnt( dir, cip, inp, q, 1 ); q.loc - loc + 3*pow4[q.lev]; SetChildsntf dir, cip, inp, q, 2 ); break; } ) void Setsnt( dir, cip, inp ) DirType dir; /* neighbour direction */ long int cip; /* current input position */ Qt *inp; /* input quadtree */ /*-- - -* Set sub-neighbour type in direction dir for the current node * inp->node[cip) */ ( QtNode n; /* neighbour node */ NeiType nt; /* neighbour type */ long int npos; /* index position of neighbour if in inp */ n - Neighbour( inp->node[cip], dir ); nt - NeighbourCheck( inp->node[cipl, n, dir, inp, Snpos ) ,-switch ( nt ) { case WHITE: SetsntHHITE( dir, cip, inp, 3 ); break; case GRAY: CheckSubNeighbours( dir, cip, inp ); break; case BLACK_EXACT: SetNeighboursntBLACK( dir, npos, inp ); case BLACK_NOTEXACT: SetsntBLACK( dir, cip, inp, 3 ); break; 1 } Boolean OnABorder( bpix, cip, inp, dir, white, black ) BorPix bpix; /* an edge pixel of a node */ long int cip; /« current input position »/ Qt *inp; /* input quadtree */ DirType dir; /« direction */ snt_type white; /* white snt */ snt_type black; /• black snt */ /* - -- -* Determine whether bpix is on the border of quadtree inp. * bpix is on a side or vertex of node edge of inp->node[cip) * in the direction dir with white or black (or gray) snt V { QtNode bqpix; /* the same as bpix, but put as QtNode */ QtNode n; /• neighbour node */ NeiType nt; /* neighbour type •/ long int npos; /* index position of neighbour if in inp «/ bqpix.loc - bpix.loc; bqpix.lev - res; bqpix.gf - 0; if ( MATCH_COLOR(inp->node[cip).snt,black,white) ) { return TRUE; ) else if ( MATCH_COLOR(inp->node[cip).snt,black,black) ) { return FALSE; ) else { /* it is on gray, determine the neighbour Jul 21199413:39:11 program-listing type of bpix only */ n - Neighbour( bqpix, dir ); nt - NeighbourCheck( bqpix, n, dir, inp, Snpos ); switch( nt ) { case WHITE: return TRUE; case GRAY: fprintf( stderr, "OnABorder( )\n' ); exit( -4 ); case BLACK_EXACT: SetNeighboursntBLACK( dir, npos, inp); case BLACK_NOTEXACT: return FALSE; 1 } ) Boolean OnBorder( bpix, cip, inp ) BorPix bpix; /* an edge pixel of a node */ long int cip; /* current input position */ Qt *inp; /* input quadtree */ * Determine whether bpix (part of node edge of inp->node[cip]) * is on the border of quadtree inp */ [ DirType dir; /* direction »/ snt_type white; /* white snt */ snt_type black; /* black snt */ switch( bpix.sb ) ( case SI: dir - SOOTH; white - S1_WHITE; black - S1_BLACK; return OnABorder( bpix, cip, inp, dir, white, black ); case Wl: dir - WEST; white - W1_WHITE; black - W1JBLACK; return OnABorder( bpix, cip, inp, dir, white, black ); case SW: dir - SOOTH; white - S1_WHITE; black - S1_BLACK; if ( OnABorderf bpix, cip, inp, dir, white. black ) ) ( return TROE; } else ( dir - WEST; white - Wl WHITE; black - W1_BLACK; return OnABorder( bpix, cip, inp. dir, white, black ); } case S2: dir - SOOTH; White - S2_WHITE; black - S2_BLACK; return OnABorder( bpix, cip, inp, dir, white, black ); case El: dir - EAST; white - E1_WHITE; black - E1_BLACK; return OnABorder( bpix, cip, inp, dir, white. black ); case SE: dir - SOOTH; white - S2_WHITE; black - S2_BLACK; Page 8 Jul 21199413:39:11 program-listing if ( OnABorder( bpix, cip, inp, dir, white. black ) ) ( return TRUE; ) else ( dir - EAST; white - E1_WHITE; black - E1_BLACK; return OnABorder( bpix, cip, inp, dir, white, black ); ) case W2: dir - WEST; white - W2_WHITE; black - W2JBLACK; return OnABorder( bpix, cip, inp, dir, white, black ); case Nl: dir - NORTH; white - N1_WHITE; black - N1_BLACK; return OnABorder( bpix, cip, inp, dir, white, black ); case NW: dir - WEST; white - W2_WHITE; black - W2_BLACK; if ( OnABorder( bpix, cip, inp, dir, white. black ) ) { return TRUE; ) else ( dir - NORTH; white - N1_WHITE; black - N1_BLACK; return OnABorder( bpix, cip, inp, dir, white, black ); ) case E2: dir - EAST; white - E2_WHITE; black - E2_BLACK; return OnABorder( bpix, cip, inp, dir, white. black ); case N2: dir - NORTH; white - N2_WHITE; black - N2_BLACK; return OnABorder( bpix, cip, inp, dir, white. black ); case NE: dir - EAST; white - E2_WHITE; black - E2_BLACK; if ( OnABorder( bpix, cip, inp, dir, white. black ) ) { return TRUE; ) else ( dir - NORTH; white - N2 WHITE; black - N2_BLACK; return OnABorder( bpix, cip, inp, dir, white, black ); ) ) } void SWBorder( cip, inp, outp, quarter_size ) long int cip; /* current input position */ Qt *inp; /* input quadtree */ Ot *outp; /* output quadtree */ long int quarter_size; /* 1/4 • of edge pixels */ * Find the south-west border pixels of the current non-pixel * node inp->node(cipl (whose sub-neighbour types have been set) Page 9 Jul 21 1994 13:39:11 program-listing Page 10 * and store them */ int QtNode long int long int BorPix in outp 9t; oq; diff_ i; bpix. .size; /* grouping factor of this node */ /* output pixel */ /* size of this dlffJborder_LUT /* counter */ /* an edge pixel of the node */ if ( MATCH_COLOR(inp->node[cip].snt,Sl_BLACK,Sl_BLACK) «& MATCH_COLOR(inp->node[cip] .Snt,Wl_BLACK,Wl_BLACK) ) ( /* internal */ return,; ) else { gf - lnp->node[cip].gf; oq.lev - res; oq.gf - 0; if ( diff_border_LUT[gf] -- NULL ) { /* the first time a node of this * gf is encountered */ InitDiffBorderLUT( gf, «diff_size ); for each pixel on the SW edge of this node determine whether it is on the border of inp */ bpix.loc - lnp->node[cipJ.loc; bpix.sb - SW; if ( OnBorder( bpix, cip, inp ) ) { oq.loc - bpix.loc; UpdateOutputQt( outp, soq ); ) for ) void SEBorder( cip, long int Qt Qt long int /* ( i - 1; i < quarter_size; i++ ) { bpix.loc +- diff_border_LUTtgf]ti-1]-loc; bpix.sb - diff_border_LUT(gf]ti).sb; if ( OnBorder( bpix, cip, inp ) ) ( oq.loc - bpix.loc; UpdateOutputQt( outp, Soq ); } inp, outp, quarter_size ) cip; /* current input position » *inp; /* input quadtree */ *outp; /* output quadtree */ quarter_size; /* 1/4 # of edge pixels */ Find the south-east border pixels of the current non-pixel node lnp->node[cip] (whose sub-neighbour types have been set) and store them in outp V int QtNode long int long int BorPix gf; oq; diff_size; i; bpix; /* /• /• /* /* grouping factor of this node •/ output pixel */ size of this dlffJ>order_LUT counter */ an edge pixel of the node */ if ( MATCH_COLOR(lnp->node[cip] .snt,S2_BLACK,S2_BLACK) as MATCH_COLOR(inp->node[Cip] .snt,El_BLACK,El_BLACK) ) ( /* internal */ return; ) else { gf - inp->node[cip].gf; oq.lev - res; Jul 21 199413:39:11 program-listing Page 11 oq.gf - 0; if ( diff_border_LOT[gf) — NULL ) { /* the first time a node of this * gf is encountered V InitDiffBorderLUTt gf, sdiff_size ); ) /* for each pixel on the SE edge of this node * determine whether it is on the border of inp V bpix.loc - inp->node[cip].loc + pow4Ires-gf+l]; bpix.sb - S2; if ( OnBorder( bpix, cip, inp ) ) { oq.loc - bpix.loc; OpdateOutputQt( outp, Soq ) ; ) for ( i - quarter_size+l; i < 2*quarter_size; i++ ) { bpix.loc +- diff_border_LUT[gf1[i-1].loc; bpix.sb - diff_border_LOT[gf][1].sb; if ( bpix.sb — E1W2 ) ( /* the last pixel on SE edge */ bpix.sb - El; 1 if ( OnBorder( bpix, cip, inp ) ) { oq.loc - bpix.loc; OpdateOutputQt( outp, soq ); ) ) ) ) void NWBorder( cip, inp, outp, quarter_size ) long int cip; /* current input position */ ^ Qt *inp; /* input quadtree */ to Qt *outp; /* output quadtree */ long int quarter_size; /* 1/4 t of edge pixels */ /* * Find the north-west border pixels of the current non-pixel * node inp->node[cip] (whose sub-neighbour types have been set) * and store them in outp */ { int QtNode long int long int BorPix gf; oq; dlff_size; 1; bpix; /* grouping factor of this node */ /* output pixel */ /* size of this diff border LOT */ /* counter */ /* an edge pixel of the node */ if ( MATCH_COLOR(inp->node[cip].snt,Nl_BLACK,Nl_BLACK) SS MATCH_COLOR(lnp->node[cipl .Snt,W2_BLACK,W2_BLACK) ) { /* internal */ return; ) else ( gf - lnp->nodetcip].gf; oq. lev - res; oq.gf - 0; if ( diff_border_LUTIgf) — NULL ) { /* the first time a node of this * gf is encountered */ InitDiffBorderLOT( gf, sdiff_size ); } /* for each pixel on the NW edge of this node * determine whether it is on the border of inp */ bpix.loc - inp->node[cip].loc + 2*pow4tres-gf+1]; bpix.sb - W2; if ( OnBorder( bpix, cip, inp ) ) ( oq.loc - bpix.loc; Jul 21 199413:39:11 program-listing Page 12 OpdateOutputQt( outp, soq ); 1 for ( i - 2*quarter_size+l; i < 3*quarter_size; i++) { bpix.loc +- diff_border_LOT[gf][i-11.loc; bpix.sb - diff_border_LOT[gf][i-11.sb; if ( OnBorder( bpix, cip, inp ) ) ( oq.loc - bpix.loc; OpdateOutputQt( outp, Soq ); } ) 1 1 LocCode FirstPixOfE2( cip, inp ) long int cip; /* current input position */ Qt *inp; /* input quadtree */ /* " • Calculate the first pixel of E2 edge of the input node * inp->node[cip] */ } int gf; /* grouping factor of this node */ LocCode first_of_W2; /* the 1st pixel of W2 edge */ QtNode last_of_El; /* the last pixel of El edge */ DirType dir; QtNode first_of_E2; gf - inp->node[cip).gf; first_of_W2 - inp->node[cipl.loc + 2*pow4[res-gf+1]; last_of_E1. loc - first_of_W2 - 1; last_of_E1 .lev - res; last_of_El.gf - 0; /• the NORTH neighbour of last_of_El will be the first_of_E2 */ dir - NORTH; first_of_E2 - Neighbour ( last_of_El, dir ) ; return first_of_E2.1oc; void NEBorder( cip, inp, outp, quarter_size ) long int cip; /* current input position */ Qt *inp; /» input quadtree */ Qt *outp; /* output quadtree */ long int quarter_size; /* 1/4 t of edge pixels */ /" * Find the north-node inp->node * and store them V [ int QtNode long int long int BorPix LocCode east cip] border pixels of the current non- pixel (whose sub-neighbour types have been set) in outp gf; oq; diff_size; i; bpix; mask; /* grouping factor of this node */ /* output pixel */ /* size of this diff border LOT * /* counter */ /* an edge pixel of the node */ /* mask to find SE corner if ( MATCH_COLOR(inp->node[cip] .Snt,N2_BLACK,N2_BLACK) SS MATCH_COLOR(inp->node[cip] .snt,E2_BLACK,E2_BLACK) ) { /* internal »/ return; ) else [ gf - inp->node[cip].gf; oq.lev - res; oq.gf - 0; if ( diff_border_LOT[gf) -- NOLL ) { /* the first time a node of this * gf is encountered V Jul 21 199413:39:11 program-listing Page 13 InitDiffBorderLOT( gf, sdiff_size ) ; for each pixel on the NE edge of this node determine whether It Is on the border of inp */ bpix.loc - PlrstPix0fE2( cip, Inp ); bpix.sb - E2; If ( OnBorder( bplx, clp, inp ) ) { oq.loc - bplx.loc; OpdateOutputQt( outp, soq ); 1 for ( - 3*quarter_slze+l; 1 < 4*quarter_size; 1++) bpix.loc +- dlff_border_LUT[gf][i-lj.loc; bpix.sb - diff_border_LDT[gf][1-1].sb; if ( OnBorder( bpix, cip, inp ) ) ( oq.loc - bpix.loc; UpdateOutputQt( outp, Soq ) ; ) J void NonTrivlalBorder( cip, Inp, outp ) long int cip; /* current input position Qt *inp; /* input quadtree */ Qt *outp; /* output quadtree */ /* CO * Find the border pixels of the current non-trivial (meaning * node larger than 2x2) node inp->node[cip] (whose sub-neighbour * types have been set) and store them in outp V ( long int quarter_size; /* 1/4 • of node edge pixels */ ) quarter_slze - (11 « (inp->nodeIcip].gf)) SWBorder( cip, inp, outp, quarter_size ); SEBorder( cip, inp, outp, quarter_size ); NWBorderj clp, inp, outp, quarter_size ); NEBorderj cip, inp, outp, quarter_size ); void TwoByTwoBorder( cip, inp, long int cip; Qt *inp; Qt «outp; /* outp ) /* current input position */ /* input quadtree */ /* output quadtree »/ * Find the border pixels of the current 2x2 node inp->node[cip) * (whose sub-neighbour types have been set) and store them in outp */ ( Boolean sw_onborder; /* Boolean se_onborder; /* Boolean nw_onborder; /* Boolean ne_onborder; /• QtNode oq; /* SW corner is on border */ SE corner is on border */ NW corner is on border */ NE corner is on border »/ output pixel */ /* SW */ if ( MATCH. MATCH. ) else { ,COLOR(inp->node(cip) .snt,Sl_BLACK,Sl_BLACK) SS .COLOR(inp->node[cip] .snt,Wl_BLACK,Wl_BLACK) ) { .onborder - FALSE; sw_onborder - TRUE; .COLOR(inp->node[cip] .snt,S2_BLACK,S2_BLACK) SS .C0LOR(inp->node[cip].Snt,El_BLACK,El_BLACK) ) [ .onborder - FALSE; } /* SE */ if ( MATCH. MATCH. se_ ) else ( se_onborder - TRUE; ) /* NW */ if ( MATCH_COLOR(inp->node(cip).snt,Nl_BLACK,Nl_BLACK) SS Jul 21 199413:39:11 program-listing Page 14 MATCH_COLOR(inp->node(cip].snt,W2_BLACK,W2_BLACK) ) { nw_onborder - FALSE; } else { nw_onborder - TRUE; ) /* NE */ if ( MATCH_COLOR(lnp->node[cip].snt,N2_BLACK,N2_BLACK) SS MATCH_COLOR(inp->node[cip] .snt,E2_BLACK,E2_BLACK) ) t ne_onborder - FALSE; ) else { ne_onborder - TROE; 1 if ( sw_onborder SS se_onborder && nw_onborder SS ne_onborder ) ( /* all four pixels are on border, output as a node * to avoid condensation V oq.lev - res - 1; oq.gf - 1; oq.loc - inp->nodetcip].loc; UpdateOutputQt( outp, soq ); ) else { /* check each pixel in turn */ oq.lev - res; oq.gf - 0; if ( sw_onborder ) { oq.loc - inp->node[cip],loc; OpdateOutputQt( outp, soq ); } if ( se_onborder ) { oq.loc - inp->node[cip].loc + 1; OpdateOutputQt( outp, soq ); ) if ( nw_onborder ) { oq.loc - inp->node[cip]-loc + 2; OpdateOutputQt( outp, Soq ); ) if ( ne_onborder ) { oq.loc - inp->node[cip].loc + 3; UpdateOutputQt ( outp, soq ); } ] } void BorderFind( cip, Inp, outp ) long int cip; /* current input position */ Qt *inp; /* input quadtree */ Qt *outp; /* output quadtree */ /* " " — " " * Find the border pixels of the current node inp->node[cip] and * store them in outp V { DirType dir; /* direction */ QtNode oq; /» output pixel */ /* set sub-neighbour types in each directions */ if ( MATCH_COLOR(inp->node[cip] .snt,El_BLACK,ONSET) ) { dir - EAST; Setsnt( dir, cip, inp ); } if ( MATCH_COLOR(inp->nodetcip] .snt,SlJBLACK,ONSET) ) { dir - SOOTH; Setsnt( dir, cip, inp ); } if ( MATCH_COLOR(inp->node[cip] .snt,Wl_BLACK,ONSET) ) { dir - WEST; Setsnt( dir, cip, inp ); ] if ( MATCH_COLOR(inp->node[cip] .snt,N1_BLACK,ONSET) ) ( dir - NORTH; Setsnt( dir, cip, inp ); } Jul 21 199413:39:11 program-listing Page 15 /* output border pixels depending on sub-neighbour types if ( inp->node[cip).lev ~ res ) ( /* pixel */ if ( ALL_BLACK( inp->node[cip].snt ) ) { /* internal pixel */ return ; 1 else { /* border pixel */ oq.lev - res; oq.gf - 0; oq.loc - inp->nodeIcip].loc; 0pdateOutputQt( outp, soq ); 1 ] else if ( inp->node[cip).gf — 1 ) ( /* 2x2 node */ TwoByTwoBorder( cip, inp, outp ); } else { NonTrivialBorder( cip, inp, outp ); ) main( */ ( argn, argc ) int char FILE FILE char char Qt Qt long argn; •argct) int struct tins ; «in_fp; *out fp; in fn[64); out_fn[64] inp; outp; cur_ipos; tmsstart. /* input file pointer */ /* output file pointer */ /* input file name */ ; /* output file name */ /* input quadtree */ /* output quadtree */ /* current input position /* for timing */ tmsend; to /* check command line */ CheckNumArg( argn, 3, "nevborder <input file> <output file>" ); strcpy( in_fn, argc[l) ); strcpyj out_fn, argc(2] ); Checklnfile( sin_fp, in_fn ); CheckOutfile( sout_fp, out_fn ); if ( times( stmsstart ) — -1 ) { /* start timing */ fprintf( stderr, 'XntimesO error\n' ); exit( -4 ); ) Init( sinp, Soutp, in_fp, out_fp ); for ( cur_ipos - 0; cur_ipos < inp.size; cur_ipos++ ) { ) BorderFind( cur_ipos, Slnp, soutp ); if ( times( *tmsend ) — fprintf( stderr, exlt( -4 ); ) PrTlines( Stmsstart, itmsend ); PrtOutputQt( soutp, out_fp ); CleanBLOTO; ClosePow4(); CloseIO{ Sinp, Soutp, in_fp, out_fp ); -1 ) { /* end timing •\ntimes() error\n" ),-/* print timing */ /****************************• node-border.c ************************* * Otllity routines for generating the edge pixels of a quadtree * node * Dser should call, in sequence, InitBorder(), GenNodeBorder(), * CleanBorder(), CleanBLOTO . * Date By Comment * __ * 1994Marl5 S. It. Tang Created */ •include <stdio.h> Jul 21 199413:39:11 program-listing Page 16 • include • . . /header/qutil. h" /* externals */ extern long int res; /* resolution */ extern LocCode QtEncode(); /* globals */ LocCode *border_L0T; /* differences of loc. codes along x axis */ BorPix **diff_border_LOT; /* differences of loc. codes of node edge */ void InitBorder() /*- "- " - " --* Allocate memory and initialize border_L0T and diff_border_LUT • Note: global res must be initialized */ { long int size; long int 1; Point tmpp; LocCode current, last; /* current and last encoded x */ /* allocate border _L0T */ size - (11 « (res-1)) -1; border_L0T - (LocCode *)calloc( size, slzeof(LocCode) ); if ( border_L0T -- NOLL ) { MemErr( •border_LOT' ); } /* lnlt border_LOT */ last - 0; for ( i - 0; i < size; i++ ) { tmpp.v(0] - i+1; tmpp.vtl] - 0; current - QtEncode( tmpp ); border_LOT[i] - current - last; last - current; ) /* allocate diff_border_LOT */ size - res + 1 ; /* diff_border_LOT[0] is unused since gf-0 means pixel */ diff_border_LOT - (BorPix «*)calloc( size, sizeof(BorPix *) ); if ( diff_border_LOT — NOLL ) { MemErrt 'diff_border_LOT' ); ) / * i n l t dlff_i>order_LOT */ for ( i - 0; i < s ize ; i++ ) { diff_border_LOTUl - NOLL; ) ) void InitDiffBorderLOT( gf, diff_size ) int gf; /* grouping factor */ long int *diff_size; /* size of this LOT */ /* - " " -"- " * Initialize diff_border_LOT[gf] for node of grouping factor gf. * * Note: InitBorder() should have been invoked «/ I long Int size; /* * of differences for this gf */ long int r,last; /* running index */ long int j,m; int i; /* avoid creating garbage *'/ if ( diff_border_LOT[gf] !- NOLL ) { free( diff_border_LOT[gf] ); } /* special cases if gf-0 or gf-1 */ if ( gf — 0 ) { *dlff_size - 0; Jul 21199413:39:11 program-listing Page 17 return; ) if ( gf -- 1 ) { diff_border_LDTIgf] - (BorPix •)calloc( 3, sizeof(BorPix) ); If ( diff_border_LOT(gfl — NOLL ) { fprintf( stderr, "\nFor gf-»d\n", gf ); MemErr( •diff_border_LOT(gf]• ); ) diff_border_LOT[gf][0].loc - 1; diff_border_LOT[gf][0].sb - SW; dlff_border_LOT[gfl(l].loc - 1; diff_border_LUT[gf)[l).sb - E1W2; diff_border_L0T[gf)[2).loc - 1; diff_border_LOT[gf][2].sb - NE; *diff_size - 3; return; ) /* allocate memory for LOT of this gf (see 3/11/94 research note) */ size - 2 « ((11 « (gf+1)) - 3) + 1; diff_border_LOTtgf] - (BorPix *)calloc( size, sizeof(BorPix) ); if ( diff_border_LOT[gf) — NOLL ) ( fprintf( stderr, *\nFor gf-%d\n', gf ); MemErr( •dlff_border_LOT[gf]" ) ; } /* for the lower south and west edge */ dlff_border_LOT(gf1[0].loc - 1; diff_border_LOT(gf][0J.sb - SW; r - 1; for ( 1 - 0; i <- gf-2; i++ ) { J - 11 « i; last - r; for ( m - 0; m < j; m++ ) ( diff_Jborder_LOT[gf J [r] .loc - border_LOT[m]; diff_border_LOT[gf]tr].sb - SI; r++; ) for ( m - 0; m < j; m++ ) ( diff_border_LOT[gf)(r).loc -2 « diff_border_LOTIgf][last+m].loc; diff_border_LOT[gf][r].sb - Wl; r++; ) } /* for the lower south and east edge */ j - (11 « (gf-1)) - 1; last - r; for ( m - 0; m < j; m++ ) { diff_border_LOT[gfj[rl.loc - border_LOT[m]; dlff_border_LOT[gf][r].sb - S2; r++; } dlff_border_LOT[gf][r).loc -2 » diff_border_LOT[gf)(last).loc; diff_border_LOT[gf][rl.sb - SE; r++; for ( m - 1; m < J; m++ ) { diff_border_LOTIgf][r].loc -2 * diff_border_LOT[gf][last+m].loc; dlff_border_LOT(gf][rl.sb - El; r++; ] /* just between lower and upper edge */ diff_border_LOT[gf)[r].loc - 1; diff_border_LOT[gf](rl.sb - E1W2; r++; /* for upper edge */ for ( m - size/2-1; m >- 0; m-- ) ( diff_border_LOT[gf)(r).loc -diff_border_LOT[gf ] [m] .loc; diff_border_LOT[gf][r].sb - SIZE_OF_SubBorderType -Jul 21 199413:39:11 program-listing Page 18 diff_border_LOT[gf][m).sb; r++; ) *diff_size - r; } void GenNodeBorder( q, bp, size ) QtNode q; /* a quadtree node */ BorPix **bp; /* addr of pointer to the edge pixels of q »/ long int *size; /* ptr to t of edge pixels */ /* " " - " * Given a node q, return its edge pixels through bp, * along with size * Note: InitBorder() should be invoked first * Note: on entry bp should be NOLL; user should call CleanBorderf) * after using bp */ [ int gf; /* group factor */ long int half_size; /* half t of edge pixels */ long int diff_size; /* size of this diff LOT */ long int 1; gf - q.gf; /* avoid creating garbage */ if ( *bp I- NOLL ) { free( *bp ); ) /* if q is a pixel */ if ( gf -- 0 ) { •size - 1 ; *bp - (BorPix *)calloc( 1, sizeof(BorPix) ); if ( *bp ~ NOLL ) [ MemErr( "«bp" ); } (*bp)[0].loc - q.loc; (*bp)[0].sb - E1W2; return; ) /* q is not a pixel, allocate memory to store the edge */ half_size - (11 « (gf+1)) - 2; •size - 2 • half_size; *bp - (BorPix *)calloc( *size, sizeof(BorPix) ); if ( »bp ~ NOLL ) t MemErr( "*bp' ); ! /* if first time node of gf size is encountered */ if ( diff_border_LOT[gf] — NOLL ) { InitDiffBorderLOT( gf, *diff_size ); 1 /* generate the lower edge */ (*bp)[0].loc - q.loc; (*bp)[0].sb - diff^border_LOT[gf](OJ.sb; for ( 1 - 1 ; i < half_size; i++ ) [ (*bp)[i].loc - diff_border_LOT[gf][i-l].loc + (*bp)[1-1].loc; (*bp)[i].sb - diff_borderJ,OT[gf] [i].sb; > (*bp)[half_size-l) .sb - El; / * generate the upper edge * / (*bp)[half_size]. loc - (*bp)[half_size-l] . loc + 1; (*bp)(half_size].sb - H2; for ( i - half_size+l; 1 < *size; i++ ) ( (*bp)[ i ] . loc - diff_border_LOT[gf][i-l).loc + (*bp)[ i - l ] . loc ; (*bp)[i] .sb - diffJtx>rder_LOT[gf] [ i -1] .sb; J ) void CleanBorderf bp ) BorPix *bp; /* pointer to the edge pixels of q */ /* -Jul 21 199413:39:11 program-listing Page 19 * Free memory used by bp free( bp ); void CleanBLOT() /* * Free memory used by LOT * * Note: global res must be Initialized ( */ int 1; free( border_LUT ); for ( i - 0; i <- res; i++ ) ( free( diff_border_LDT1i] ); ) free( diff_border_L0T ); *** quad.c (qdsvlp-ha.h) *** A collection of relevant *** Method used for encoding -*** for decoding 93/02/18 GFS *** procedures for quadtree programs. *** two-part double-vector encoding, *** one-part single-vector hash-decoding.*** This file contains encoding and decoding procedures for the quad domains of resolution 2 <- res <- 12. NOTES: (1) The variable 'res' to hold the resolution of the quad-domain is declared in this file. It must be defined (e.g., by reading it in). It is the only global variable. (2) After 'res' has been defined, invoke the procedure 'initialise' by: initialised; (3) All variables have been declared to be of data type 'long int'; in particular, declare the coordinates and the location code as datatypes 'long inf. (4) In the body of the application program, use the following procedures. For decoding, use the procedure call decode(loc, sx, «y); for encoding, use the procedure call loc - encode(x,y); The algorithms assume and check that the coordinates x, y are not negative (i.e., both x and y must be positive or zero). If it is desired that negative coordinates are encoded, use the following formula (which will result in wrap-around of the coordinates): long int mask2; mask2 - (1 « 2) - 1; loc - encode(x & mask2, y & mask2); (5) For timing purposes, calls to encode and decode should be replaced by in-line statements by copying the statements in the body of these two procedures. - */ •define RBAT 6 •define TRUE 1 •define FALSE 0 tinclude <stdio.h> void exit(int status); /* void *calloc(slze_t nitems, size_t size); */ long int res; static long int tx, tn, k2, tlpx, kshx; static long int *qevx, *qevy, *qdvx; long int qdilate(long int k) ( Jul 21 199413:39:11 program-listing Page 20 long int 1, t; t - k & 1; for (i - 1; i < res; ++i) t I- ((k S (l«i)) « i); return t; ) long int encode(long int i.long int j) t /* static external long int qevx, qevy, RHAT, tn, k2; */ return ( (qevx [ i & tn ] | qevy (J 6 tn ]) I ((qevx[i»RHAT) | qe vy f J »RHAT)) « k 2 ) ) ; } void decode(long int loc, long int *x, long int *y) { /* static external long int qdvx, tx, tlpx, kshx */ *x - qdvxt (loc S tlpx) I ( (loc S tx) » kshx)]; *y - qdvx[((loc » 1) s tlpx) I (((loc » 1) S tx) » kshx)]; ) void initialise(void) { long int m, i, restmp; if (res < 2) ( printf(" ERROR: resolution is too low. Initialise the'); printf(' variable 'res' before\n invoking 'initiallse'V*); exit(l); } if (res > 2*RHAT) t printff ERROR: resolution is too high I • ) ; printfC Max resolution is res - %ld\n', (2*RHAT)); exit (1); ) restmp - res; /* temporary redefinition of res in order to */ res - RHAT; /* invoke qdilate for initialisation of the */ tn - (11«RHAT); /* the encode vectors */ qevx - (long int *) calloc(tn, sizeofflong int)); qevy - (long int *) callocjtn, sizeof(long int)); tn - tn - 11; for ( 1 - 0 ; i <- tn; ++i) t qevx[i] -qdilate(i); qevyfi] - qevx(i] « 1; ) res - restmp; /* reset resolution */ k2 - RHAT « 1; /* constants */ tx - qdilate((ll « res) - 11); tlpx - qdilate((ll « ((res + 11) / 21)) - 11); if (res t 11) kshx - res; else kshx - res - 11; qdvx - (long int *) calloc((l « res), sizeof(long int)); for (i - 0; i < (11 « res); ++i) { m - qdilate(i); qdvxt(m £ tlpx) I (m » kshx)] - i; } } /ft**************************** out11.c ******************************* * Utility routines for quadtree-related problems * Date By Comment * 1994Febll S.K.Tang Created */ tinclude <stdio.h> •include •../header/qutil.h* Jul 21 199413:39:11 program-listing Page 21 /* externals */ extern long int res; /* resolution */ /* globals */ LocCode ncode_L0T[81; /* neighbour code lookup table */ LocCode «pow4; /• pow4[i] - 4"(res-i) */ LocCode *pow4ml; /* pow4ml[1] - pow4[i]-1 */ LocCode Tx; /• mask for dilated x •/ LocCode Ty; /* mask for dilated y */ I/O A*****************************/ void GetlnputOtf inp, in_fp ) Qt *inp; /* input quadtree •/ FILE *in_fp; /« input file pointer */ /* "- - -* Allocate and get input quadtree * Note: initialize global res in this routine */ ( ] QtNode tn; /* a quadtree node «/ long int inp_alloc; /* allocated size */ long int inps; /* running input size */ /* read resolution */ fscanf( in_fp, •%ld*, Sres ); /* allocate memory for input qt */ lnp_alloc - DEFAULT_NUM_IN_NODES; inp->node - (QtNode *}calloc( inp_alloc, sizeof(QtNode) ); if ( inp->node -- NOLL ) ( MemErrf "inp" ); ] inps - 0; /* read input qt and calculate input size */ while ( fscanf( ln_fp, "%ld %d", & to. loc, &tn.lev ) !- EOF ) { tn.gf - res - tn.lev; if ( inps >- inp_alloc ) ( /* input size is larger than allocated size «/ inp_alloc « - 1;/* try twice as much memory */ inp->node - (QtNode *) realloc( inp->node, inp_alloc*sizeof(QtNode) ) ; if ( inp->node ~ NOLL ) { MemErr( "inp again" ); } } inp->node[inps].loc - tn.loc; inp->node(inps).lev - tn.lev; inp->node[inps1.gf - tn.gf; inp->node(inps].snt - UNSET; inps++; ) /* free unnecessary memory for input qt */ if ( inps < lnp_alloc ) ( inp->node - (QtNode *) realloc( inp->node, lnps*sizeof(QtNode) ); if ( inp->node — NOLL ) { MemErr( "inp just fit" ); } } inp->size - inps; inp->allocated - inps; vold AllocOutputQt( outp, out_fp ) Qt *outp; /* output quadtree */ FILE *out_fp; /* output file pointer */ /* -- " " * Allocate output quadtree */ I long int outp_alloc; /* allocated size */ Jul 21 199413:39:11 program-listing Page 22 /* allocate default memory */ outp_alloc - DEFAOLT_NUM_OOT_NODES; outp->node - (QtNode *) calloc( outp_alloc, sizeof(QtNode) ); if ( outp->node — NOLL ) { MemErrf "outp" ); ) /* init current size to 0 */ outp->size - 0; outp->allocated - outp_alloc; ) void OpdateOutputQt( outp, q ) Qt *outp; /* output quadtree */ QtNode *q; /* node to be stored */ /* " " * Opdate output quadtree by storing a node q into it */ { long int outp_alloc; /* » of node allocated */ outp_alloc - outp->allocated; if ( outp->size >- outp_alloc ) ( /* output quadtree is larger than current memory allocated */ outp_alloc « - 1;/* try twice as much memory */ outp->node - (QtNode *) realloc( outp->node, outp_alloc»sizeof(QtNode) ); if ( outp->node — NOLL ) { HemErr( "outp again" ); } outp->allocated - outp_alloc; } outp->node[outp->size].loc - q->loc; outp->node[outp->slzej.lev - q->lev; outp->node[outp->size).gf - q->gf; (outp->size)++; ) void PrtOutputQt( outp, out_fp ) Qt *outp; /* output quadtree */ FILE *out_fp; /* output file pointer */ /* " " " "- — — * Print output quadtree • Note: global res must be initialized V { long int ii; /* print resolution */ fprintf( out_fp, "%ld\n", res ); /* print nodes */ for ( ii - 0; ii < outp->size; ii++ ) ( fprintff out_fp, "%ld %d\n", outp->node[ii].loc, outp->node[li].lev )i ) void CloseIO( inp, outp, in_fp, out_fp ) Qt *inp; /* input quadtree */ Qt *outp; /* output quadtree */ FILE *in_fp; /* input file pointer */ FILE *out_fp;/» output file pointer */ /* * Free memory related to I/O V { free( inp->node ); free{ outp->node ) ; fclose( in_fp ); fclose( out_fp ); ) void Prtsnt( cip, inp ) Jul 21 199413:39:11 program-listing Page 23 long int cip; /* current input node position */ Qt *lnp; /» input quadtree */ /* " " " - - " * Print the sub-neighbour type for current input node * This is mainly for debugging, thus output to stdout V ( printf( "%ld *d 0x»x\n', inp->node[cipl.loc, inp->node(cip).lev, inp->node[cip].snt ); ) /•••••••.•«•»*.••».«•»•»•». encode/decode ••*****»•••**»****»•*«***••/ void InitPow4() /•-- " " " " --- -* Initialize global3 pow4(i] - 4~(res-i) and pow4ml[i] - pow4(il-l */ { int i; /* loop counter */ LocCode temp-11; /* temporary */ pow4 - (LocCode •) calloc( (res+1), sizeof(int) ); if ( pow4 — MULL ) { MemErr( *pow4" ); } pow4ml - (LocCode *) calloc( (res+1), sizeof(int) ); if ( pow4ml — NULL ) ( MemErr( "pow4ml' ); } for ( i - res; i >- 0; --i ) ( pow4[i) - temp; pow4ml[il - temp - 1; temp « - 2; ] ] void ClosePow4() /« - " -* Free memory used by globals pow4 and pow4ml */ t free( pow4 ); free ( pow4ml ) ; } void InitMasM) /* -- - - -* Initialize globals TX-01...01 (there are res l's) and Ty * Note: global res must be initialized first * Note: InitPow4() must be invoked first */ I int 1; /* loop counter */ Tx - 11; for ( i - res-1; 1 > 0; 1-- ) { Tx +- pow4(i); } Ty - Tx « 1; ) void InitCoding() /* " " " -* Initialize LUT for encoding/decoding * Use algorithm in quad.c * Note: global res must be initialized first */ [ initialised; ) LocCode QtBncode( pt ) Point pt; /* the cartesian point to be encoded */ /* - - "- " Jul 21 199413:39:11 program-listing Page 24 * Encode a cartesian point into a location code * Use algorithm in quad.c * Note: InitCodingO must be invoked first V { return encode; pt.v(01, pt.v[l] ); ] Point QtDecode( n ) LocCode n; /* the location code to be decoded */ /* " - - " * Decode a location code into a cartesian point * Use algoritm in quad.c * Note: InitCodingf) must be invoked first V { Point p; /* temporaries */ decode) n, &(p.v[0]), s(p.v[l]) ); return p; ) /*#*#*********#*##*****#*#* arithmetic **********************•*****/ LocCode LocAdd( nl, n2 ) LocCode nl; /* location code 1 */ LocCode n2; /* location code 2 */ /* -- " " " * Compute nl + n2 using location code arithmetic * * Note: InitMask() must be invoked first */ { LocCode tmpl,tmp2; /* temporaries */ tmpl - ((nl I Ty) + (n2 « Tx)) t Tx; tmp2 - ((nl I Tx) + (n2 & Ty)) s Ty; return ( tmpl I tmp2 ); } LocCode LowerRightPixel( q ) QtNode q; /* " " * Compute the location code of the lower right pixel of node q V { LocCode mask; int i; mask - 01; for ( i - 0; i < q.gf; 1++ ) { mask - (mask « 2) I 11; ) return (q.loc I mask); } LocCode UpperLeftPixel( q ) QtNode q; /*- -" * Compute the location code of the upper left pixel of node q */ { LocCode mask; int i; mask - 01; for ( 1 - 0; 1 < q.gf; i++ ) ( mask - (mask « 2) | 21; } return (q.loc I mask); } LocCode UpperRightPlxeH q ) Jul 21 199413:39:11 program-listing Page 25 QtNode q; /• " * Compute the location code of the upper right pixel of node q */ { LocCode mask; int i; mask - 01; for ( i - 0; 1 < q.gf; 1++ ) { mask - (mask « 2) | 31; ) return (q.loc | mask); ) /ft************************* neighbour ****•***********************/ void InitNeighbourLOTO /* " - -* Set up lookup table for neighbour code * Note: global res must be initialized first */ ( long int mask2; /* mask for -ve numbers */ Point tp; /* temporary */ DirType dir; /* neighbour direction */ mask2 - (1 « res) - 1; dlr - EAST; tp.v[0J - 1; tp.v[l) - 0; ncode_LUTIdirJ - QtEncode( tp ); dir - NORTH_EAST; tp.v[ll - 1; ncode_LOT[dir] - OtEncode( tp ); dir - NORTH; tp.v[0] - 0; ncode_LDT[dir] - QtEncode( tp ); dir - NORTH_WEST; tp.v[0) - -1 i mask2; ncode_LOT[dir] - OtEncode( tp ); dir - WEST; tp.v[l] - 0; neode_LDT[dir] - QtEncode< tp ); dir - SO0TH_WEST; tp.v(l] - -1 s mask2; ncode_LOT[dir) - QtEncode( tp ); dir - SOUTH; tp.v(O) - 0; ncode_LUT[dir] - QtEncode; tp ); dir - SOOTHJEAST; tp.v[0] - 1; ncode_LOT[dlrl - QtEncode( tp ); ) QtNode Neighbour( q, dir ) QtNode q; /* the current quad node */ DirType dir; /» neighbour direction »/ /* " - .- -* Calculate neighbour code of equal size using location * code addition « Note: InitNeighbourLDTO must be invoked first */ { LocCode delta_n; /* delta location code to add on «/ QtNode n; /* neighbour of q */ delta_n - ncode_LOTtdir]; delta_n « - 2 * q.gf; /* accounts for neighbour of same size */ n.loc - LocAdd( q.loc, delta_n ); n.lev - q.lev; n.gf - q.gf; return n; Jul 21199413:39:11 program-listing Page 26 Boolean NeighbourFinding( n, predecessor, successor, inp, position ) QtNode n; /* the neighbour to be sought after */ QtNode "predecessor;/* not found, return predecessor */ QtNode *"successor;/* not found, return successor •/ Qt *inp; /* the input quadtree */ long int "position; /• index position if found */ /. * Find the neighbour n in the input quadtree * If found, return TRUE * If not found, return FALSE and assign the predecessor and successor * as defined in [Tang S Lin, 1990) * Note: Ose binary search. { */ long int l,r; /* left and right index */ long int m; /* middle index */ 1 - 0; r - inp->size - 1; m - ( 1 + r ) / 2; while ( 1 < r ) [ if ( n.loc < inp->node[m].loc ) { r - m; } else if ( inp->node[ml.loc < n.loc ) { 1 - m + 1; ) else t if ( inp->node[m).lev -- n.lev ) ( /•»•** FOUND •••••/ •position - m; return TROE; ) else { break; } } m - ( 1 + r ) / 2; I if ( inp->node[m).loc ~ n.loc 6& inp->node[m].lev « n.lev) { /* boundary case 1-r-m and just found */ •position - m; return TRUE; ) else if ( inp->node[m).loc <- n.loc SS inp->node[m].lev < n.lev ) [ •predecessor - *(inp->node[m)); •successor - &(inp->node[m+l]); ) else [ if ( m > 0 ) C •predecessor - S(lnp->node[m-ll) ,-} else { •predecessor - &(inp->node[m]); } •successor - S{inp->node[m]); ) return FALSE; } NeiType NeighbourCheck( q, n, dir, inp, position ) QtNode q; /* the current node */ QtNode n; /* the neighbour of q to be checked */ DirType dir; /* direction of n relative to q */ Qt *inp; /* the input quadtree */ long int *positlon;/* index position if n is in inp */ /* -"-* Determine the type of the neighbour node n •/ f /• whether n is in inp •/ /* predecessor of n in inp */ /* successor of n in inp */ /* temporary •/ /• check whether n is wrapped around »/ Boolean QtNode QtNode int found; •pre; •sue; range; Jul 21 199413:39:11 program-listing Page 27 /« i.e. whether q is on the edge of the domain «/ switch ( dir ) { case EAST: case NORTH: if ( n.loc <- q.loc ) [ /* n is wrapped around */ return WHITE; ) break; case SOOTH: case WEST: if ( n.loc >- q.loc ) t /* n is wrapped around */ return WHITE; } break; default: fprintf( stderr, • Neighbour-Check: cannot happen\n" ); break; ] /* n is not wrapped around */ found - NeighbourFinding( n, &pre, ssuc, inp, position ); if ( found ) { return BLACK_EXACT; ) if ( n.gf < pre->gf ) { range - 1 « (2 * pre->gf); /* pow(4, pre->gf) */ if ( (n.loc * pre->loc) < range ) { /* pre is super-neighbour of q */ return BLACK_NOTEXACT; } } if ( suc->gf < n.gf ) ( range - 1 « (2 * n.gf); /* pow(4, n.gf) */ if ( (suc->loc " n.loc) < range ) { /* sue is sub-neighbour of q */ return GRAY; } ) return WHITE; /ft***************************** util.c ******************************* * General utility routines * Date By Comment » 1994Feb25 S.K.Tang Created * 1994May26 S.K.Tang Add PrTimesO »/ •include <stdio.h> •include <sys/times.h> •include <unistd.h> void MemErr( obj ) char *obj; /* pointer to object to be allocated memory »/ /*--- " - -- --* Print memory allocation error */ I fprintf( stderr, *\nCannot allocate memory for %s\n*, obj ),-exit( -1 ); } void CheckNumArg( argn, n, syntax ) int argn; int n ; char "syntax; /* - " * Check number of command line arguments */ [ Jul 21 1994 13:39:11 program-listing Page 28 if ( argn I- n ) ( fprintf{ stderr, 'Osage: %s\n', syntax ); exit( 1 ); 1 } void Checklnfile( fp, fn ) FILE «*fp; /* address of input file pointer */ char *fn; /* input file name */ /*-- " " " " " * Check existence of input file V c *fp - fopen( fn, 'r' ); if ( *fp — NOLL ) { fprintf( stderr, "Input file \*»s\" does not exist\n", fn ); exit( 1 ); } 1 void CheckOutfile( fp, fn ) FILE **fp; /* address of output file pointer */ char *fn; /* output file name */ /*--- " -- -* Check existence of output file */ t *fp - fopen( fn, "r' ); if ( *fp I- NOLL ) { fprintff stderr, 'file \'%s\' already exist, ', fn ); fprintf( stderr, *OK to overwrite? (y/n): • ); if ( getchar() ~ 'n' ) { fprintf( stderr, •\n\tRe-enter with new output filename\n* ); exit( 2 ); ) ) *fp - fopen( fn, 'w' ); } void PrTimes( tmsstart, tmsend ) struct tins "tmsstart; /* starting CPO time */ struct tms *tmsend; /* ending CPO time */ /* - — — * Print CPO times. * Adapted from 'Advanced Programming in the UNIX Environment* by * W. Richard Stevens, pp.234, Addison-Wesley 1992 V { static long elktek - 0; if ( elktek — 0 ) { /* fetch clock ticks per second first time */ if ( (elktek - sysconf(_SC_CLK_TCK)) < 0 ) { fprintf( stderr, *\nError from sysconf" ); exit( -4 ); } ) fprintf( stderr, *\tuser: »7.2f\n', (tmsend->tms_utime - tmsstart->tms_utime) / (double) elktek ); fprintf( stderr, '\tsys: »7.2f\n*, (tmsend->tms_stime - tmsstart->tms_stime) / (double) elktek ) ; fprintf( stderr, "\tchlld user: »7.2f\n", (tmsend->tms_cutime' - tmsstart->tms_cutime) / (double) elktek ); fprintf( stderr, *\tchild sys: %7.2f\n', (tmsend->tms_cstiine - tmsstart->tms_cstlme) / (double) elktek ); )
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A non-recursive border finding algorithm for linear...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A non-recursive border finding algorithm for linear quadtree based images Tang, Shao Kang 1994
pdf
Page Metadata
Item Metadata
Title | A non-recursive border finding algorithm for linear quadtree based images |
Creator |
Tang, Shao Kang |
Date Issued | 1994 |
Description | Given a digital binary image represented in a linear quadtree, its border is to be found as another linear quadtree. A new algorithm is proposed that can generate the border in sorted order. A pattern is found for the order of the edge pixels of a node. The differences of the location codes for the edge pixels of a node with grouping factor g is stored in a lookup table. The lookup table also provides the information about which edge a given pixel is on. Through a probabilistic analysis, the new algorithm is able to avoid recursion which reduces the number of neighbour finding operations significantly. The algorithm performs better, when compared to the one by Yang & Lin, in both the run time (40% improvement) and the number of neighbour finding operations incurred (60% reduction). |
Extent | 2679856 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-03-05 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0064800 |
URI | http://hdl.handle.net/2429/5545 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1994-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-0628.pdf [ 2.56MB ]
- Metadata
- JSON: 831-1.0064800.json
- JSON-LD: 831-1.0064800-ld.json
- RDF/XML (Pretty): 831-1.0064800-rdf.xml
- RDF/JSON: 831-1.0064800-rdf.json
- Turtle: 831-1.0064800-turtle.txt
- N-Triples: 831-1.0064800-rdf-ntriples.txt
- Original Record: 831-1.0064800-source.json
- Full Text
- 831-1.0064800-fulltext.txt
- Citation
- 831-1.0064800.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0064800/manifest