Filling Contours on the Linear QuadtreeDomain by Insertion and TraversalbyLars Martin WilkeB.A.Sc., The University of Waterloo, 1986A thesis submitted in partial fulfillmentof the requirements for the degree ofMaster of Applied ScienceinThe Faculty of Graduate Studies(Department of Electrical Engineering)The University of British ColumbiaDecember 1993© Lars Martin Wilke, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature)_____Department of L-EC A—),The University of British ColumbiaVancouver, CanadaDate ( /iQ icr3DE-6 (2/88)AbstractAn algorithm is presented which fills contours described by a set of pixels whose locations are givenin unsorted linear quadtree (LQT) form. Each pixel requires an associated blocking code whichindicates locally in which direction the region should grow. The technique takes advantage of certaincharacteristics of LQT location codes to determine if the boundary pixels fall on the edges or verticesof lower resolution LQT cells. This information allows for the automatic determination of boundarycells after the pixels have been inserted into a regular quadtree. Remaining uncoloured cells arecoloured using conventional techniques. The algorithm compares favourably with existing LQT fillingalgorithms both in time and space complexity. The technique avoids explicit sorting of the inputpixels or output cells by location code, and no condensation of cells is required. Traversing theregular quadtree in preorder generates the sorted output cells as an LQT.IITable of ContentsAbstract iiList ofTables ivList of Figures vAcknowledgements vi1 Intmduction 11.1 Regular and Linear Quadtrees 11.2 Filling in the LQT Domain 22 Useful Properties ofLocation Codes 43 Filling by Insertion and Traversal 73.1 Insertion Phase 832 Traversal Phase 103.3 Saving Time and Space 133.4 Finding Missing Pixels 143.5 Input Data 154 Runtime Analysis 165 Verification 176 Algorithm Assessment and Comparison 177 Extension to Octrees 198 Conclusions 24Bibliography 25Al Discrete Rotations and Reflections in the LQT Domain 28A2 Converting from Chain Code to Boundary Pixels and Blocking Codes 32A3 Scan Converting Lines and Circles in the Quadiree Domain 35A4 Converting from Runs to LQT Cells 38UIList of TablesTable Al - Truth Table for Bits of Quaternary Digits 29Table A2 - Boolean Expressions for Bits of Quaternary Digits 29Table A3 - Look-up table to convert freeman codes to blocking codes (NWSE) 34ivList of FiguresFigure 1 - LQT domain r=4 with filled region 6Figure 2 - Quadtree node 8Figure 3 - Insertion sequence 9Figure 4 - Insertion pseudocode 10Figure 5 - Boundary cells 11Figure 6 - Example of cell with invalid blocking code 12Figure 7 - Traversal pseudocode 13Figure 8 - Boundary pixels which must be pruned 14Figure 9 - Runtime comparison of algorithms 18Figure 10 - Memory requirements of algorithms 19Figure 11 - Octree insertion pseudocode 22Figure 12 - Traversal pseudocode 23Figure Al - Eight discrete transformations of the LQT domain r = 1 31Figure A2 - Rotating cells by 270w 32Figure A3 - Regions defined by chain codes 33Figure A4 - Freeman chain to blocking code conversion 34Figure A5 - Scan conversion of a line 36Figure A6 - Scan conversion pseudocode for line in LQT domain 37Figure A7 - Scan conversion pseudocode for circle in LQT domain 39Figure A8 - Run To LQT conversion algorithm 40VAcknowledgmentsI would like to thank the following individuals for their support and guidance while completing myMaster’s thesis. Dr. Schrack, whose enthusiasm and open door policy made work with him a pleasure,and whose funding helped to support my research. Many thanks to Sang Mah, who originallyconvinced me of the value of returning to university and whose initial encouragement helped me pastself doubt. The calm friendship of Angela Berlin was much appreciated, and made my time as aMaster’s student an enjoyable one. Most importantly I wish to thank my family, whose unquestioningsupport, both emotional and material, has been with me through all of the endeavors of my life.vi1.0 Introduction1.1 Regular and Linear QuadtreesQuadtrees are a data structure commonly used to represent objects according to their spatialoccupancy on a (2 x 2) raster or quadtree domain. As such, they are commonly used in rastergraphics for image compression, and in geographic information systems as a spatial indexingtechnique. r is the called the resolution of the raster and corresponds to the maximum depth of thequadtree. It is normally fixed for a given application.The quadtree is constructed by dividing the raster (represented by the root node of the quadtree) intofour quadrants, and successively dividing each quadrant by four if it is only partially contained by theobject. This subdivision continues until either the quadrant is completely contained or not contained,or until the maximum depth of the quadtree has been reached (pixel level).Each node of the quadtree represents a subquadrant on the raster, and is either black (occupied),white (unoccupied) or grey (further subdivided). The size of the quadrant represented by the nodedepends on the node-depth in the quadtree.By labeling each branch of a quadtree node with a quaternary digit, (e.g. O:SW, I :SE, 2:NW, 3:NE), apointerless representation of the quadtree can be created. A quaternary number is formed byconcatenating the branch label digits as the quadtree is traversed from the root to a black node. If theblack node is not at the pixel level, the least significant digits are assigned the value 0 such that thenumber of digits is equal to the resolution number of the domain. This quaternary number is called alocation code, and it is associated with a number indicating the level of the black node inside thequadtree. In practical applications, the location code and level can be stored in a four-byte computerword. The sequence of location codes for all pixels in the quadtree domain is equivalent to theMorton sequence [1] when the location code is given in decimal form.A sorted list of location codes with associated node levels, representing an object is referred to as a1linear quadtree (LQT). Besides being a more space efficient representation than the regular quadtree,many of the most common operations on objects such as rotation, reflection [2], neighbour finding [3],union and intersection [4], can be performed efficiently on linear quadtrees since explicit traversal ofthe quadtree can be avoided. Simple manipulations of the location codes are used instead.Location codes have the very useful property that they can be formed by interleaving the bits of the xand y coordinates of any pixel in the quadtree domain. This property, first pointed out by Gargantini[5], greatly simplifies the task of encoding (insertion into quadtree), decoding, and neighbour finding.It has also lead to a new area of investigation called location code arithmetic 121, which exploitspatterns and symmetries of the Morton sequence to derive faster operations on LQT objects.1.2 Filling in the LQT DomainTwo-dimensional region filling is a problem which is as old as computer graphics itself. Thealgorithms which have been developed are usually specific to the region representations used, andcomparisons between algorithms must be made in this context.For quadtree representations, many filling algorithms have been developed. They are particularlyimportant since they provide the means for converting between traditional image representations suchas polygons or boundary chains to the region quadtree. As quadtrees find wider acceptance incomputer cartography and computer graphics, the efficiency of the conversion algorithms will becomemore critical.Samet presents an algorithm for regular quadtrees that fills regions whose boundaries are representedby chain codes [6, 7]. The algorithm first builds a partial quadtree by inserting boundary pixels asblack leaves as they are derived from the chain code. Intermediate nodes in the tree initially haveundefined colours (they are called uncoloured) which are determined in the second phase of thealgorithm. New boundary pixels are generated in the first phase by using neighbour finding operationsas the boundary chain is traversed. A blocking code is produced for each pixel, which stores2information regarding which edges of the pixel are shared with pixels exterior to the filled region. Theblocking code consists of four bits, one for each edge of a node. A bit is set if the corresponding edgeof the node forms the boundary of the region. The second phase of Samets algorithm traverses thequadtree, colouring each intermediate node encountered, based on the configuration and blockingcodes of the children of the node. Note that the concept of blocking codes defined here is common toother quadtree filling algorithms [8, 9, 10], and is indeed used in the algorithm presented in this thesis.Algorithms to fill regions whose perimeters are described by pixels located by LQT location codeshave been published by Gargantini, Atkinson and Walsh [8, 9] and by Mark and Abel [101. In theGargantini algorithms, the input is a sorted list of LQT location codes of the boundary pixels alongwith their associated blocking codes. The algorithms use the blocking codes to find missing pixels,and later, as the algorithms progress up the virtual quadtree, blocking codes propagated up from lowerlevels are used to find missing qUadrants.In both of the Gargantini algorithms, the input must be sorted, although in [8] a bucket sort isincorporated as part of the recursive filling routine. Here, the initial pixel list is split into four sublistsdepending on which quadrant of the image each boundary pixel is in. The procedure is reinvoked foreach sublist, which are again subdivided according to the subquadrant of the image that each listelement appears in. After r subdivisions for a 2r x 2r raster, each sublist contains at most four pixelscorresponding to the children of a 2 x 2 cell in the image. The arrangement of these siblings, alongwith their blocking codes, can be used to find any missing black siblings. If four black siblings exist,they can be merged to form a single black cell. The resulting sublist of black nodes is passed back asthe recursion unwinds, allowing larger and larger missing black nodes to be found, and if possible,larger siblings to be merged. The output of this algorithm is only partially sorted, but by adding aspecial output data structure, and some minimal algorithmic complexity, the output can be sorted.The second phase of the algorithm presented by Mark and Abel also takes a sorted list of boundarypixels with blocking codes to derive the region quadtree. The main theorem underlying the second3phase states that, given a sorted list of boundary pixels, the absent pixels between two consecutivepixels in the list must either be all the same colour, or can change colours at most one time. In thesecond case, two distinctly coloured sets of pixels are derived. The location of the pixel whichfollows the change of colour between sets can be derived by finding the nearest common ancestor ofthe two consecutive pixels in the boundary list. The first pixel of one of the quadrants of the ancestorwill be that pixel which follows the colour change. The correct quadrant is chosen by examining theblocking codes of the current consecutive boundary pixel pair. The final output of the algorithm is aset of Morton sequence runs of white and black pixels. Translation from runs of pixels to LQT cells isrelatively straightforward.The purpose of this thesis is to present a new region filling algorithm for boundary pixels presented asLQT location codes. The algorithm avoids sorting the input or output location codes, and does notcondense smaller quadtree nodes to form larger ones when filling regions. It achieves an 0(B) timecomplexity similar to the algorithms described above, where B is the number of boundary pixels. Inpractical comparisons, the proposed algorithm fills faster without an increase in space requirements.2.0 Useful Properties of Location CodesBy inspecting the quaternary location code of an individual pixel, it is possible to determine therelationships between that pixel and the lower resolution cells which contain it (i.e., lie on the pathbetween it and the root of the quadtree). These relationships are formalized in the following set ofrules (the examples are for a resolution r = 4. See Figure 1).4Rule 1. Given the number k of trailing quaternary zeros of a location code m,the size of the cell which m can represent is not larger than (2k x 2k), k 0e.g. m = 21004 can represent:(2100, 4) of size 1 x 1 (pixel)(2100, 3) of size 2 x 2(2100, 2) of size 4 x 4Rule 2. Given the number k of identical trailing quaternary digits of a locationcode m, the size of the cell for which m can form one of the vertices isnot larger than (2k x 2k), k 1e.g. m = 21114 forms the SE vertex of:(2110,3) of size 2 x 2(2100, 2) of size 4 x 4(2000, 1) of size 8 x 8The value of the trailing digit indicates which vertex of the cell m forms0:SW, 1:SE, 2:NW, 3:NETo find the location codes of the cells, substitute the k digits by 0 fromright to left and use rule 1 to get the size of the cell.Rule 3. Given the number k of trailing quaternary digits of a location code mwhere the set of trailing digits comprise two distinct quaternary digitsthe size of the cell for which m can form the edge or diagonal of is notlarger than (2k x 2k), k 2e.g. m = 23234 forms part of the N edge of:(2300, 2) of size 4 x 4(2000, 1) of size 8 x 8(0000, 0) of size 16 x 16or m = 32024 forms part of the W edge of:(3200, 2) of size 4 x 4(3000, 1) of size 8 x 8or m = 13304 forms part of the main diagonal of:(1300, 2) of size 4 x 4(1000,1) of size 8 x 8The two values of the trailing digits indicate which edge or diagonal ofthe cell m forms(0,1):S, (0,2):VV, (2,3):N, (1,3) E(0,3) main diag. (1,2) cross diag.To find the location codes of the cells, substitute the digits by 0 from right toleft and use rule 1 to get the size of the cell.5—. .. —.1022:1123 113211011 221212323 2332j2331 mimI 212mI 323323ti2220 mi 3230 323’ 2120 [2121 2210 ° 32 1330 3321 3330nl4221fl33&n03Th1nI3: ot 2210 2211 2101112201 2210 3211 1203 3201 3211 33001 3301 3310:321!—1--- — I —. ..:.. ( i. — —4—I 3032 3011 212212122 2112,2122 3022,1022 3011 1122 3132 3122 l3133....___J___.I .,.!.. I I I ...::2021 10 303! 2120 22 2110 2111 30301 I 3011 3310 lII 1110:111!—4--- — : —i— - -4—2001 hOd 3313 2101 12103 2112 :2113 100113003 10 1101 Ili1 3312 hIll---.--- , . 1-— —-1-- ---i-—-. ;.2003 1001 1010 1011 2101 2101 2110: 2111 3001: 300! 130 1101 110’ 3110 3111—. — 1 —4— -0113 0212 0213 013210111 033110333 122211211 1212:1 132211322 I132: 1333I ..,... . I I I I ‘: I ‘1 1 jI:.1 0221 0110 033) 0110 1032 0230 0311 210 1221 1210 1310 11121 113011311-.. —4— —4 - —4—0303 10203 0112 0113 2301 111101 0312:0311 120111201 1212:1 11021 1303 1312: 1313______. ;•.•. .1I • :.. I . . I I1l 031 0111 01f11030l 0110:0311 1200 1201 1210: 1211 1001 1301 1310: 1311— I I I -10023 013210133 0122 [0121 0112{OI11 1222 1021 3012 hOll 112211122 1122:1133II:1:::12;, 1;; ;1; ;;-34;;;0011210003 011210313 11102101113 0112 1 01)3 1002 horn 1012 :1011 1101:1103 11121 tIll-—— I I I -I010010001 001010111 0103:0101 011010111 3:toot iotoi.ii 1101:1101 1110:1111I I I I I I ITo get a better understanding of the rules listed above, consider the LQT domain in Figure 1 (r = 4)as a meta-cell of size 2 x 2 within a larger domain of resolution r’. Setting r’ = 7 for this example,the quaternary location codes for the pixels in the cell will have the form dddnnnn4,where the digitsddd give the location of the cell within the encompassing domain, and the digits nnnn give thelocation of the pixels within the cell, and are identical to the quaternary location codes shown inFigure 1. Recall that the location codes are formed by bit interleaving the X and Y coordinates of thepixels: each quaternary digit of the location code corresponds to two bits, an X and a Y bit, with the Xbit in the least significant position.In the example, the SW vertex of the meta-cell has the local coordinate (0, 0) within the cell andmust therefore have the location code ddd00004. Applying rule 1 to this location code, k = 4 and thesize of cell represented by this code is 2 x 2, which is the size of the cell in Figure 1.The SE, NW, and NE vertices of the cell have local coordinates (2’-1, 0), (0, 2rl) and (2r1, 2r.4)Figure 1 - LQT domain r=4 with filled region6respectively, which when interleaved, form the location codes dddllll4,ddd22224,and ddd33334.Applying rule 2 to these location codes, k = 4, and the size of cell having these locations as verticesis also 2 x 2.Consider now a pixel along the edge of the meta-cell. Since either the X or Y coordinate along aparticular edge is fixed, only one bit in each quaternary digit can change and therefore each digit cantake on only one of two values. The allowed values of the digits along an edge will be fixed by thevalues of the digits of the quaternary location codes forming the vertices of that edge. The southernedge of the cell in Figure 1, for example, lies between ddd00004 and ddd 11114, and the locationcodes of the pixels along the edge joining them have the form dddnnnn where the digit n can only bequaternary 0 or 1. A similar observation can be made about the location codes of the pixels lyingalong the diagonal between two vertices of a cell. In this case, the X and Y coordinates change at thesame rate along the diagonal, and therefore both bits of any quaternary digit will change at the sametime, also allowing only one of two values for the digits.Applying rule 3 to the location code ddd 10104, for instance, k = 4 and therefore the size of cell whichit forms the edge of is 2 x 2 which agrees with Figure 1.3.0 Filling by Insertion and TraversalThe proposed filling algorithm consists of two phases. In the first phase, the boundary pixels areinserted into a regular quadtree. As the pixels are inserted, the non-pixel nodes are marked eitherblack or grey depending on the spatial and blocking relationship between the pixel being inserted andthe node being traversed. After the insertion phase, the quadtree contains black and grey nodes.Uncoloured nodes are represented by null branches in the tree. The black nodes in the quadtreecorrespond to the largest LQT cells forming the boundary of the filled region (Figure 5).The second phase of the algorithm traverses the quadtree created in the first. When a black node isencountered, its location and level are output to the region LQT. When a null-branch is encountered,7the colour of the cell it represents is determined. If the cell is found to be black, its location and levelare also output to the region LQT. If a grey node is encountered its children are traversed.The resulting LQT represents the filled region, and the list of location codes are in sorted order, aresult of traversing the quadtree in preorder.3.1 Insertion PhaseThe data structure used to store the input boundary pixels is a simple regular quadtree. Figure 2(a)shows the structure for a single node. Since the quaternary location code of the boundary pixeldescribes the path through the regular quadtree from root to leaf, insertion is straightforward. The taskconsists of following the branch indicated by the next significant quaternary digit of the location code,and creating new nodes where necessary.Child 0 Child I Child 2 Child 3 Blocking(a),1 f \ \ Colour(b) N W S E BlockingFigure 2 - Quadtree nodeUsing the rules given in Section 2, it is possible to determine before insertion the cells which containthe boundary pixel as an edge pixel or vertex, pixel. Such cells are represented by nodes which liealong the path between the root of the quadtree and the leaf representing the boundary pixel. Theblocking code of the boundary pixel being inserted indicates which side(s) of the pixel is exterior tothe region. This information must also be used to determine if the non-leaf nodes must be grey, or arepotentially black.80000)0) 0000(0) 0000(0)When a quadtree node is created, it is initially marked black. As a node is traversed during theinsertion process, it will be marked grey if the pixel being inserted does not fall on the edge or cornerof the cell represented by the node. Similarly, if the pixel being inserted does lie on the edge orvertex of the cell being traversed, the blocking code of the pixel may exclude that cell from beingblack, in which case it is also marked grey. Referring to the example boundary in Figure 1, supposethat boundary pixels are inserted starting in the order 23334, 23324, 23214. Pixel 23334 is blockedonly on its northern side, and it sits on the northern edge of cell (0000, 0) and on the NE vertex ofcells (2000, 1), (2300, 2), (2330, 3). This means, without knowing any additional information aboutother boundary pixels, that all four cells could potentially be black.Therefore, the nodes representing these cells are created and coloured black as the pixel is inserted(Figure 3(a)). From the location code of the second pixel, 23324, it can be determined that it sits onthe northern edge of cells of level 0, 1, 2 and at the NW vertex of a cell of level 3. Also, it is blockedon the west, and therefore all of the cells that the pixel forms the northern edge of must be markedgrey. The cell which it forms the vertex of remains marked black (Figure 3(b)). The third pixel,23214, does not form the edge of a larger cell. It does form the SE vertex of a cell of level 3, butsince it is blocked in the north and west directions, the level-3 cell must also be grey (Figure 3(c)).Figure 4 gives the complete pseudocode for the insertion process.2000)1)2300(2)2000)1)(a)2333)4) 2332)4)(b)Figure 3 - Insertion sequence• 2320)2)2333)0)(c)9Quadtree Insert fin pbcel location, m bloddng code)AND vertex and maximum vertex cell size GIVEN location codeAND edge and mairn edge ceil size Gft’EN locatlon codeDETERMINE if pixel is a valid vertex GIVEN blocking code and vertexDETERMINE if pixel is a valid edge GIVEN blocking code and edgelevel:=Onode := rootWHILE (level <maximum vertex ceO levee DOIF (level <maximum edge ceO level) OR (pixel not valid edge) ThENnode colour := greyB’J) Fnode block code := node block code I pixel block codechild := next significant quatemary digit of pixel location codeIF (chiki node does not exist) 11-EN create black child nodenode := dud nodeEN)WHILEWHILE (level < quadtiee depth)node block code := node block code I pixel block codeIF (pixel is not valki vertex) THEN node colour := greychild next sqthcant quaternary digit of pixel location codeIF (did node does not exist) THEN create black did nodenode :=child nodeENDWHLEFigure 4 - Insertion pseudocode3.2 Traversal PhaseOnce all of the boundary pixels of a region have been inserted into the quadtree, the resultingstructure is traversed in preorder. Each time a black node is encountered, its location code and levelare output as part of the LQT representing the filled region. Any children of a black node are ignored.If a grey node is encountered, then its children are visited. Note that the LQT location code of eachcell can be generated from the current position in the quadtree traversal.The linear quadtree generated by the traversal described above is the sorted list of all of the largestcells forming the boundary of the region. Figure 5 shows the result for the original example. Cellswhich are left uncoloured correspond to branches of the quadtree which were left null after theinsertion phase. The problem remaining is to determine their colour.10To facilitate cell colouring, a field is included in each quadtree node (Figure 2a) which contains thecomposite blocking code of all boundary pixels contained by that node. The blocking code consists offour bits, one for each direction (Figure 2b). When a bit in the blocking code is set, it indicates thatthe corresponding edge of the associated cell or pixel forms the perimeter of the region.During the insertion phase, the blocking code of a pixel is bitwise ORed with the composite blockingcodes of the nodes it traverses as it is inserted. Thus if a pixel contained by a node has a blocking bitset for a particular direction, the composite blocking code will also have that bit set. When insertionis complete, grey nodes may contain blocking codes which are not valid since the boundary may beconcave within the cell. Such a case is illustrated in Figure 6 where the composite blocking codeindicates that the cell is blocked on all sides whereas, the cell is only blocked on the north and westsides. Therefore, only the black nodes are considered to have valid blocking codes after insertion.Figure 5 - Boundary cells11The colour of an uncoloured cell (null pointer in the quadtree) can be determined from the blockingcode of its black or grey siblings. If the cell lies to the outside of its black or grey sibling then itscolour must be white, otherwise, it must be black, and its location code and level can be recorded inthe output LQT. Since a grey sibling node does not have a valid composite blocking code, thesubtree rooted at that node must be searched until a black node (having by definition a valid blockingcode) is found. The search is carried out so that the node finally arrived at is as close as possible tothe shared edge of the grey and uncoloured siblings. The blocking code of the black node found in thesearch is used to determine if the uncoloured node lies to the inside or outside of the grey sibling.If more than one uncoloured node belong to the same parent node, it is only necessary to find thecolour of one of these siblings. The colours of the other siblings can be inferred from the colourassigned to the first sibling. When two uncoloured siblings are edge neighbours of one another, theycannot be separated by the region boundary and therefore must be assigned the same colour. Whenneighbours are located across a vertex, however, it is possible for the two uncoloured siblings to beseparated by the boundary and they will be assigned the opposite colours. Cells (2200, 2) and (2100,2) in Figure 1 are an example. The condition can be detected since there will be two grey or blacksiblings which are neighbours of each other across a vertex. Figure 7 gives the pseudocode for therecursive traversal process.Figure 6 - Example of cell with invalid blocking code12Quadtiee Traveie (in Quadhe, in level, in cunent location code)BBIF (level = quactree depth) THEN RETURNFOR (child = 0 TO 3) DODERIVE child location code GIVEN cunent location code and child nirnberIF (child node exists) THENIF(chikinodegey)THENQuadtiee Traveree (child node, level+1, child location code)BSEOUTPtf child location code and level to LQTBUFELSE (child node must be cdouiecIF (sllng has been odourecO THENIF (coloured sbhng is edge neighbour) AND (is black) THENOIJPUT child location code and level to LQTELSE IF (coloured sillng s vertex neighbour) AND (is white) AND(other two srdrige exist) THENOUTPUT child location code and level to LQTEl’.DFDETERMINE colour of child GIVEN blocking code of edge neitourIF (colour is black) THEN OUTPUT child location code and level to LQTB’JD FEi’IJ FB\DFORE’l)Figure 7 - Traversal pseudocode3.3 Saving Time and SpaceThe traversal phase of the filling algorithm described in the previous section checks for the colour ofnon-null nodes. Since pixel nodes have no children, and can only take the colours black or white,they do not need to be explicitly stored. It is sufficient that a non-null pointer (dummy pointer) existsin the parent of the pixel node to indicate the presence of a black pixel. The space that would berequired for a quadtree node for each boundary pixel can thereby be saved. For a complete quadtree,the amount of storage required by the pixels would be 4’ units, while the space required by all otherr-1 k 4r1 .nodes in the tree would be 4 = —i—. In this best case there is a 75% saving in space byeliminating the pixel nodes, while in more realistic cases, as determined experimentally for randomlygenerated boundaries, the space saving is on average better than 50%.Therefore, the quadtree traversal algorithm is modified to output an LQT cell not only when a black13node is encountered, but also when a dummy pointer is encountered at the parent of pixel level in thequadtree.The algorithm for colouring an uncoloured cell searches the subtree rooted at the grey sibling, until anode with a valid blocking code is found. In the previous section, cells with valid blocking codesafter the insertion phase were defined only as those that were coloured black. Since the search for ablack cell can no longer reach the pixel level, given the new storage scheme, the definition of cellwith valid blocking code must be redefined to include all cells which are parents of boundary pixels.In order to guarantee that the parent of a pixel node does indeed have valid composite blocking codes,there can be no conflicting blocking codes in the pixels inserted through them. Blocking codesconflict when two neighbouring pixels with the same parent are blocked along the edge that they havein common. Since, from the definition of the valid input data, a boundary cannot double back onitself in a concave bend (see section 4.5 and Figure 8(a),(b)) all conflicting blocking codes areavoided in the parent of pixel cells.Exterior Interior Exterior Interior— hI1 I I II(a) (b)Figure 8 - Boundary pixels which must be pruned3.4 Finding Missing PixelsIn the new quadtree storage scheme, boundary pixel nodes are represented by dummy pointers at theparent of pixel level. Since the pixel nodes are represented differently than other nodes in thequadtree, the colouring algorithm described earlier will not work for uncoloured pixels. The colourmust therefore be determined as the boundary pixels are inserted, rather than during the quadtree14traversal phase.The colour of uncoloured pixels will only need to be determined if the parent is coloured grey, sinceotherwise they would not be visited in the traversal. An uncoloured internal pixel will occur in a greyparent only if two boundary pixels contained by that parent are vertex neighbours of each other. Inthis case, the uncoloured pixels will also be vertex neighbours of one another, and their colours willbe opposite. Pixel set 31204, 31234 of Figure 1 is an example. To determine which of the two isblack, the blocking code of the second boundary pixel is examined as it is inserted. The uncolouredpixel on the side of the newly inserted pixel which is unblocked is coloured black by setting thecorresponding pointer in the parent to the dummy value.3.5 Input DataThe input data comprises a set of pixels which define the boundary of a given region on a quadtreedomain. Each pixel is stored as an LQT location code with an associated blocking code. The order ofthe pixels may be arbitrary, but the entire group must form one or more closed ioops which do notintersect each other.Data can be generated in many different ways but in all cases the input data must meet the followingcriteria.1 - The boundary is not self intersecting unless the blocking codes are set such thatthe outsides of loops which are formed have the same parity.2 - A boundary does not double back on itself in a concave corner (Figure8). In 8(a), internal pixels are blocked along an edge shared withanother internal pixel. In 8(b), internal pixels are blocked on both thenorth and south edges. In both cases, since the pixels are interior to thefilled region, they are not real boundary pixels, and their blocking codesshould be zero, or the pixels should be eliminated.3 - Pixels may be repeated, but may not have contradicting blocking codes.The second criterion implies that a certain amount of preprocessing is necessary to ensure the validityof the boundary. The preprocessor must prune all of those boundary pixels which are completely15contained by the filled region, that is, all internal appendages (Figure 8a,b). An equivalent step is toset their blocking codes to zero. Preprocessing is necessary for instance when the boundary pixels aregenerated from concave polygons where internal angles exceed a certain threshold causing internalappendages to be formed.Note that the requirement to prune the boundary is common to all other algorithms using blockingcodes. Some of the algorithms, such as Gargantini’s, are robust enough to handle the cases shown inFigure 8.4.0 Runtime AnalysisThe execution time of the boundary filling depends on the number of nodes visited in each phase ofthe algorithm.During the boundary pixel insertion phase, each pixel which is inserted must visit one node perresolution level of the quadtree. At each level, it must be determined whether the appropriate childnode exists. If it does not, then a new node must be created. The cost of node creation can bedistributed among all of the boundary pixels inserted into the tree. In general, the number of nodescreated per pixel insert becomes progressively less as more pixels are created.For a quadtree of resolution r, a pixel must visit r nodes as it is inserted into the tree. Insertionoccurs once per boundary pixel, so given n boundary pixels, the insertion process is 0(m) or simply0(n), since r is constant for a given application.During the quadtree traversal phase, the quadtree is traversed in preorder. If a black node isencountered, the cell represented by that node is output, and all of the children of that node areignored. Since black nodes correspond to the largest cells adjoining the boundary of the region(Figure 5), there are at worst 0(n) black nodes, and the cost of visiting them is also 0(n).Encountering a null node means that its colour must be determined. This is achieved by searchingdown the levels of the subtree rooted at a non-null sibling such that the first black node is found which16is as close as possible to the shared boundary of the non-null and uncoloured siblings. The search willvisit at most r nodes. Since the number of uncoloured nodes is proportional to the number of blacknodes, the cost of finding colours will also be 0(n).5.0 VerificationThe proposed filling algorithm was verified primarily with a random boundary generating tool. Theresulting filled regions were displayed on a raster monitor, where any holes were immediately obvious.As a double check, the output LQTs were compared with those generated by the competing algorithmsfor the same boundaries and were found to be identical.6.0 Algorithm Assessment and Comparison1In order to test the merits of the filling algorithm described in this thesis, it was compared with tworecently published algorithms that operate on the same type of boundary descriptions to derive filledregions expressed as linear quadtrees.The first of these algorithms is that of Atkinson, Gargantini and Walsh [8] which is a refinement of analgorithm published earlier by Gargantini and Atkinson [9]. It uses blocking codes to find missingcells, starting at the pixel level of the quadtree, working toward the root, propagating blocking codesfrom children to parent. The effect is to grow the region inward from the boundary to the centre. Thisalgorithm requires as data structures a linked list to store the input boundary pixels and blocking codesand a linked list to store the output LQT which stores location codes and levels.The algorithm presented by Mark and Abel [10] operates on a sorted list of boundary pixels to deriveruns of black and white pixels. The black runs are easily converted into LQT cells. In order to keepthe execution time of the overall algorithm linear, a bucket sort was used to sort the input data. Thetime to sort the input and the time to convert from runs to LQT cells were included in the measuredtime of execution. The algorithm requires two arrays, one to store the input boundary pixels, and the1 The algorithms were implemented in ANS11 C, and compiled with the gcc compiler using theoptimizer flag (-0). The tests were run on a Sun IPX.17other to store the runs of black pixels (defined by start and stop pixel location codes).Figure 9 gives a graphical comparison of the three algorithms in terms of execution time vs. boundarylength for 100 randomly generated boundaries. Clearly, all three algorithms are linear. The proposedalgorithm is, on average, 40% faster than the Gargantini algorithm, which has the second best timeperformance.More detailed timing measurements of the two competing algorithms show that sorting the input datacomprises the largest single time expense. The rearranging of data during a sort requires many readand write accesses to memory, which slows the overall performance. By avoiding a sort, the proposedalgorithm achieves its superior runtime performance.Figure 10 shows the total memory in bytes allocated to each algorithm vs. the boundary length. In thiscase, the proposed algorithm uses slightly less memory than the Gargantini algorithm, but slightlymore than the Mark and Abel algorithm. The chief difference here is that the Mark and Abelalgorithm does not require storage for pointers since the data are stored contiguously in arrays.Runtime vs Boundary Length1080.00 1.00 1.50 2.00 2.50 8.00 8.501’,, 10Figure 9 - Runtime comparison of algorithms18The relationship between memory requirements for the first two algorithms can change slightly,depending on the compiler and system used. The results for the Gargantini algorithm would beslightly better if the data could be stored on other than four byte boundaries, since the input blockingcode only requires a single byte.7.0 Extension to OctreesThe algorithm described in the previous sections can be easily extended to work in the octree domain.The changes to the algorithm are all related to the addition of a third dimension. Instead of fillingregions defined by boundary pixels, as for the quadtree case, the task becomes one of filling a volumedefined by a set of surface voxels.Several analogies can be formed between the quadtree and octree domains. A cell in the quadtreedomain is represented by a node within the quadtree. It corresponds to a square subdivision of theentire two-dimensional domain. Similarly, a cell in the octree domain is also represented as a nodewithin the octree, and corresponds to a cubic subdivision of the three-dimensional domain. The octreenode has eight rather than four children, each child corresponding to one of the eight equalRequired Memory100.50 1.00 1.50 2.00 2.50 2.00 3.50 4.00 x 10Figure 10 - Memory requirements of algorithms19subdivisions of the cubic volume represented by the node. Octree cells can also be represented by alocation code and level within the octree, just as in the case for quadtrees. For octrees, the locationcode is also formed by interleaving the coordinates of the domain, in this case X, Y, and Z. Whenexpressed as an octal number, each digit of the location code corresponds to the next branch of thetree, when traversing the tree from root to leaf, serving the same role as quaternary location codes inlinear quadtrees.The three rules presented in section 2 relating pixels to the quadtree cells which contain them canstand almost unchanged as the relationship between cells and voxels in octrees. References toquaternary digits and numbers must simply be substituted with references to octal digits and numbersand references to the size of cells must include the third dimension (i.e. 21c x x 2k rather than 2k x2k). A fourth rule can be formulated, which relates the voxel to the octree cells which it forms theface of. Changing the context to the octree domain then, the rules are as follows. Note that in theexamples here, the X and Y axis still fall along the east west and north south directions, and that the Zaxis falls along the up-down (U/D) axis.Rule 1. Given the number k of trailing octal zeros of a location code m, the size ofthe cell which m can represent is not larger than (2k x 2k x 2k), k 0e.g. m = 21008 r = 4 can represent:(2100, 4) of size 1 x 1 x 1 (voxel)(2100, 3) of size 2 x 2 x 2(2100, 2) of size 4 x 4 x 4Rule 2. Given the number k of identical trailing octal digits of a location code m,the size of the cell for which m can form one of the vertices is not largerthan (2k x 2k x 2k), k 1e.g. m=21118r=4forms the DSE vertex of:(2110, 3) of size 2 x 2x 2(2100, 2) of size 4 x 4 x 4(2000, 1) of size 8X8x8The value of the trailing digit indicates which vertex of the cell m forms0:DSW, 1:DSE, 2:DNW, 3:DNE4:USW, 5:USE, 6:UNW, 7:UNETo find the location codes of the cells, substitute the k digits by 0 fromright to left and use rule 1 to get the size of the cell.20Rule 3. Given the number k of trailing octal digits of a location code mwhere the set of trailing digits comprise two distinct octal digitsthe size of cell for which m can form the edge, face diagonal, orinternal diagonal of is not larger than (2’ x x 2k), k 2e.g. m = 23238 r=4 forms part of the DN edge of:(2300, 2) of size 4 x 4 x 4(2000, 1) of size 8 x 8 x 8(0000, 0) of size 16 x 16 x 16or m = 76468 r=4 forms part of the 13W edge of:(7600, 2) of size 4 x 4 x 4(7000, 1) of size 8 x 8 x 8or m = 15508 r=4 forms part of the main diagonal of the S face of:(1500, 2) of size 4 x 4 x 4(1000, 1) of size8x8x8The two values of the trailing digits indicate which edge or diagonal of thecell m forms(0,1):DS, (0,2):DW, (2,3):DN, (1,3) DE(4,5):US, (4,6):UW, (6,7):UN, (5,7) UE(0,4):SW, (1,5):SE, (2,6):NW, (3,7) NE(0,3) main diag. (1,2) cross diag D face(4,7) main diag. (5,6) cross diag U face(0,5) main diag. (1,4) cross diag S face(2,7) main diag. (3,6) cross diag N face(0,6) main diag. (2,4) cross diag W face(1,7) main diag. (3,5) cross diag E face(0,7), (1,6), (3,4) internal diagonalsTo find the location codes of the cells, substitute the digits by 0 from right toleft and use rule 1 to get the size of thç cell.Rule 4. Given the number k of trailing octal digits of a location code mwhere the set of trailing digits comprise three or four distinct octaldigits the size of cell for which m can form the face of is not largerthan (2’x2’cx2k),k3e.g. m = 5710238 r=6 forms part of the D face of:(571000, 3) of size 8 x 8 x 8(570000, 2) of size 16 x 16 x 16or m = 5720468 r=4 forms part of the W face of:(572000, 3) of size 8 x 8 x 8(570000,2) of size 16 x 16 x 16The values of the trailing digits indicate which face of the cellm forms(0,1,2,3): D, (4,5,6,7): U(0,1,4,5): N, (2,3,6,7): S(0,2,4,6): W, (1,3,5,7): ETo find the location codes of the cells, substitute the digits by 0 from right toleft and use rule I to get the size of the cell.21Octree Insert (in voxel location, in blocking code)FIND vertex and merernum vertex cdl size GIVEN location codeFiND edge aid madnixn edge cell size GIVEN location codeFIND face and maxirrixn fae cell size GIVEN location codeDETERMINE if pixel is a valid vertex GIVEN blocking code and vertexDETERMINE if pixel is availd edge GIVEN blocking code and edgeDETERMINE if pocel is a valid face GIVEN blocking code and facelevel =0node := lootWHILE (level < ma’drnizn edge cell levee DOIF (level < maximum face cell level) OR (pixel is not vald face) THENnode colour := greyB’UFnode block code node block code I pixel block codechild next significant quaternary digit of pixel location codeIF (child node does not exist) ThEN create black child nodenode:=childnodeEND WHILEWHILE (level <madmum vertex cell level) DOnode block code := node block code I pixel block codeIF (pixel is not valid edge) node colour := greychild := next significant quaternary digit of pixel location codeIF (child node does not exist) THEN create black child nodenode := child nodeEND WHILEWHILE Qevel<quadtreedepth)node block code := node block code I pixel block codeIF (pixel is not valid vertex) THEN node colour := greychild := next significan quatemaly digit of pixel location codeIF (child node does not exist) THEN create black child nodenode := child nodeEND WHILEBDFigure 11 - Octree insertion pseudocodeThe algorithm for insertion described in section 3.1 must be modified to check if the surface voxelbeing inserted into the octree forms part of the face of some of the cells which contain it. It must thenexamine the blocking code of the voxel, to see if the cells which the pixel forms the face of mayremain black, or mus be marked grey. The rest of the algorithm rcmains essentially unchanged and isshown in Figure 11. After the insertion phase, the largest cells forming the surface of the object, areall marked black in the octree.22The traversal algorithm described in section 3.2 also remains essentially unchanged. Colouringuncoloured cells becomes more complex in that colouring based on the juxtaposition of uncolouredsiblings is not straightforward. Given that an uncoloured cell has been assigned a colour aftersearching a black or grey sibling for a valid blocking code, other uncoloured neighbours may beassigned the same colour provided that they are not separated by the surface of the object. This is thecase for instance when the uncoloured siblings are neighbours across a face. Determining whether twouncoloured siblings are or are not separated by the surface when they are not neighbours across a faceis done by examining the black or grey siblings, to see if they contain surface voxels which separatethem. Alternatively, uncoloured cells which are not face neighbours with one another can be assignedcolours using the search technique used to assign colour to the first uncoloured sibling. Figure 12shows the pseudocode for the modified traversal algorithm.Octiee Traverse (in Ocbee, in level, in cunent location code)IF (level =oe depth) 11-lEN RETURNFOR (child = 0 TO 7) DODERIVE child location code GIVEN cununt location code and did nunterIF (did node edsts) ThENIF(diiIdnodegi,)ThENOchee Traverse (child node, level÷1, child location code)OUTPUT child location code and level to LOTB’.J) FELSE (child node must be assiçjed colour)IF (sblln have been assiçjed colour) THENIF (colourad sbfrrg is face neicibour) AND s black) THENOIJ1PUT child location code and level to LOTDETERMINE colour of child GIVEN block code of face neibourIF (colour black) THEN OUTPLfl child location and level to LOTEY’IJFDETERMINE colour of child GIVEN blocking code of face neigitourIF (colour is black) THEN OUTPUT child location code and level to LOTB”ID FBID FBDFORBDFigure 12 - Traversal pseudocode238.0 ConclusionsThe algorithm presented in this thesis marries the advantages of linear and regular quadtrees to derivean algorithm for filling boundaries defined by closed loops of pixels whose exterior is consistentlydefined by associated blocking codes. The normal space disadvantages of quadtrees is partiallyovercome by not explicitly storing the boundary pixels in the quadtree. White and non-boundary cellsare also not stored. By traversing the quadtree formed from inserting the boundary pixels in preorder,sorting of the data is avoided, a step which has been shown to slow other similar filling algorithms.The thesis introduces the concept of using the boundary pixel location codes to establish therelationship between those pixels, and the quadtree cells which contain them (i.e., whether they lie ontheir edges or vertices). This information is used in conjunction with the pixel blocking codes tocolour the quadtree cells black or grey as the boundary pixels are inserted. The resulting quadtree hasall of the boundary cells marked black and condensing cells in the filling process is thereby avoided.The resulting filling algorithm is a two-phase algorithm which first inserts the boundary pixels into aregular quadtree and later traverses the tree, searching for black nodes, and colouring uncolouredsiblings of the black nodes.Other filling algorithms operating on boundaries in the LQT domain exist. The most recent of these[11, 12] also require the input boundary pixels to be sorted. Since the sorting process requires themajority of the runtime in both the Gargantini and the Mark and Abel algorithms, the timeperformance of the newer algorithms is not expected to be better than the proposed algorithm.Like the Gargantini algorithm, the proposed algorithm is easily extensible to the octree domain. Themain problem, unrelated to filling algorithms, lies in generating the surface voxels and blocking codesfrom the vertices of a polyhedron.24References[1] Morton, G. M., ‘A computer-oriented geodetic data base and a new technique in file sequencing”,Technical Report, IBM Ltd., Ottawa, Canada, March 1966.[2] G. Schrack, and I. Gargantini, ‘Mirroring and rotating images in linear quadtree form with fewmachine instructions”, Image Vision and Computing, vol. 11, no. 2, pp. 112-118, March 1993.[3] G. Schrack, “Finding neighbours of equal size in linear quadtrees and octrees in constant time”,CVGIP: Image Understanding, vol. 55, no.3, pp. 221-230, May 1992.[4] I. Gargantini, “Translation, rotation and superposition of linear quadtrees”, Tnt. 3. Man-MachineStudies, vol. 8, no.3, pp. 253-263, March 1983.[5] I. Gargantini, “An effective way to represent quadtrees”, Communications of ACM, vol 25, pp.905-910, 1982.[61 H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA,1990.[7] H. Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS,Addison-Wesley, Reading, MA, 1990.[8] H. H. Atkinson, I. Gargantini, and T.R. Walsh, “Filling by quadrants and octants”, ComputerVision, Graphics, and Image Processing, vol. 33, pp. 138-135, 1986.[9] I. Gargantini, and H. H. Atkinson, “Linear quadtrees: A blocking technique for contour filling”,Pattern Recognition, vol. 17, no. 3, pp. 258-293, 1984.[10] D. Mark, and D. Abel, “Linear quadtrees from vector representations of polygons”, IEEE Trans. onPattern Analysis and Machine Intelligence, vol PAMI-7, no. 3, pp. 344-349, May 1985.[11] M. R. Lattanzi and C.A. Shaffer, “An optimal boundary to quadtree conversion algorithm’,Computer Vision, Graphics, and Image Processing, vol. 53, no. 3, pp. 303-3 12, 1991.[12] Shi-Nine Yang and Tsong-Wuu Lin, ‘A new linear octree construction by filling algorithms”,IEEE Tenth Annual International Phoenix Conference on Computers and Communications, pp740-746, 1991.25[13] M. L. V. Pitteway, ‘Algorithm for drawing ellipses or hyperbolae with a digital plotter”, ComputerJ., vol. 10, no. 3, pp. 282-289, November 1967.[14] J. Foley, A. van Dam, S. Feiner and 3. Hughes, Computer Graphics: Principals and Practice,Second Edition, Addison-Wesley, Reading, MA, 1990.26Appendix ASome Useful Results27Al Discrete Rotations and Reflections in the LQT DomainA useful result to emerge from research into the patterns and symmetries of LQT location codes is anew method of performing a limited set of transformations on objects defined as LQTs. This set oftransformations entails: (a) the identity transformation, (b) mirroring about the X axis, (c) mirroringabout the Y axis, (d) rotation of 180 degrees (about the centre of the LQT domain), (e) mirroringabout the main diagonal, (I) mirroring about the cross diagonal, (g) rotation of 90 degrees (CCW),and (h) rotation of 270 degrees (CCW). The expressions derived below for these transformations takefewer machine instructions than previously developed algorithms performing the same functions [2],and the methodology used provides a new view of LQT location codes.The common feature of the transformation set is that the transformations can be expressed as amapping of one LQT domain onto another. In these transformations, the location codes of each pixelin one domain are changed into the location codes of the new domain, in other words, there is a 1:1mapping between pixels. Equally important to note is that the changes to each quaternary digit of thelocation code will be the same for a particular transformation. For example, referring to the LQTdomain in Figure 1, a mirroring about the X-axis will change Os to 2’s, 2’s to 0’s, l’s to 3’s and 3’s tol’s. There is no interaction between the digits inside the location codes. Thus, to derive anexpression for the transformations, one needs only consider the changes required for a singlequaternary digit inside the location code.With this in mind, consider the simplified LQT domain of r=1, and all of its transformations (FigureAl). To find an expression for each case, a truth-table is constructed relating the transformed to theuntransformed digit (Table Al) where the binary representation is used for the location code digit.From the truth-table, the boolean expression for each bit can be derived for a particulartransformation, as shown in Table A2. Here dxT indicates bit x of the transformed digit, and dindicates the complement of bit x of the untransformed digit.28d10 a b c d e f h00 00 10 01 11 00 11 10 0101 01 11 00 10 10 01 00 1110 10 00 11 01 01 10 11 0011 11 01 10 00 11 00 01 10Table Al - Truth Table for Bits of Quaternary DigitsIt is clear from the boolean equations that all transformations can be expressed in terms of swappingand complementing the original bits. In order to implement these functions, individual bits of thelocation code must be selectively complemented. This becomes possible by taking advantage of thefollowing useful properties of the boolean exclusive OR function:A0 =AAl =A’Thus, for the single digit example for mirroring about the X-axis, we can simplify the expression givenin Table A2b to:dT=d2where the operator A is the C notation for bitwise exclusive OR. Bit swapping can be achieved byselecting the most and least significant bits of the quaternary digit using bitwise AND, shifting the bitsone position right and left respectively, and bitwise ORing the results. Thus the bit swap required forthe transformation shown in Table A2e used to mirror about the main diagonal can be expressed as:dT = ((d&l)<<l) I ((d&2)>>l)where the operators& and I are the C notations for bitwise AND and OR, and >>x and <<x are thenotations for arithmetic shift right and left respectively.Table A2 - Boolean Expressions for Bits of Quaternary Digits29In order to extend the results derived above to location codes of arbitrary length, the bit masks t, t and t,are introduced (as defined in [21), where:tx=Z/221 =(O0...Ol0l..Ol),= (t << 1) = (00...l0l0..10), andt=(tIt) =(OO...llll..ll)Now, for example, complementing the most significant bits of each quaternary digit in a location codecan be expressed as (bc A tv), selecting the least significant bits of the quaternary digits as (bc & t)and complementing all bits of the location code as (bc A ta).Using these bit masks, the expressions for all of the transformations of Table A2 for location codes ofarbitrary length can now be written as follows:(a) bocT=boc(b) bocT = bc A(c) bocT=boc/%tx(d) bocT=loc/%tn(e) locT = ((bc & t) << 1)1 ((bc & t) >> 1)(f) locT = (((bc & t) << 1)1 ((bc & t) >> 1)) A(g) beT = (((bc & t) << 1)1 ((bc & t) >> 1)) A(h) bcT = (((bc & t) << 1)1 ((bc & t) >> 1)) AFrom the above expressions, it becomes clear that some transformations can be expressed as simplecombinations of other transformations. A rotation of 270 degrees (h) for instance, is simply a mirroringabout the main diagonal (e) followed by a mirroring about the X-axis (b). Mirroring about the crossdiagonal (f) consists likewise of a mirroring about the main diagonal (e), followed by a rotation of 180degrees (d).In order to transform a cell of lower than pixel resolution (i.e. non-pixel leaf node), the location codeof the cell is transfonned using one of the above formulae as for a pixel. The least significant (rlevel) quaternary digits are then set to zero, where level is the depth of the cell in the quadtree. InFigure 1, for example, if the cell (3030, 3) is to be mirrored about the Y axis, transform (b) is appliedto 3030 giving 2121. The least significant digit is then set to zero, the result being the location codefor the transformed cell, (2120, 3).301 30 2(e) Mirror (f) MirrorMain Cross3 1 0 22 0 1 3(g) Rot. 900 (h) Rot. 270°transformations of the LQT domain r = 1Since each quadrant and subquadrant of the LQT domain is also an LQT domain of lower resolution,the formulae for the transformations can be applied within a quadrant. To do this we simply redefinethe mask t such that t = where r’ = r-level. and t, are still defined the same way interms of t. Applying the redefined formulae to location codes will leave the first r-level mostsignificant digits unchanged thus allowing the transformations to occur at cell level. Figure A2 showsan LQT object which is transformed at cell-level = 1.23 0 10 1 2 3(a) Identity (b) Mirror X3 2 1 01 0 3 2(c) Mirror Y (d) Rot. 180°230 1Figure Al - Eight discrete31•1 11111—:::i:i. I.A2 Converting from Chain Code to Boundary Pixels and Blocking CodesA chain code or Freeman chain consists of a series of numbers, each representing edges of unit lengthand discrete direction, which is used to describe a single closed ioop on a raster. Using the analogy ofa driver navigating a car through city streets, the chain code can be thought of as a list of directionalinstructions to be followed by the driver such that a new instruction is taken from the top of the list ateach intersection encountered (e.g. go left, go right, go straight, go back). The area enclosed by theloop is defined as being either to the left or the right of the boundary (depending on convention) as itis traversed in the order defined by the chain code. (In mathematics, convention normally defines theinterior as lying to the left.)The chain code is used in one of two complementary ways. The first type of chain code is used torepresent a series of raster edges which separate pixels interior to the region from pixels exterior to it.There are four possible directions (E N S W) each of which is assigned a code number (e.g. E:O, N: I,W:2, S:3). Figure A3(a) shows an area defined by this method. The location of a pixel on the rastermust be given as the starting point for the loop.The second type of chain code, often called a Freeman chain, is such that each element of the chainrepresents the direction from the current pixel to the next pixel along the boundary. Since, on a raster,II.,..::::::::: iii:::. II I IIFigure A2 - Rotating cells by 27W32the next pixel is necessarily a neighbour of the current, there are eight possible directions, which forthe purpose of the example in figure A3(b) are numbered E:O, NE: 1, N:2, NW:3, W:4, SW:5, S:6,SE:7. The Freeman chain also requires the specification of a pixel which defines the start of the loop.E-&-::s:±: _zThe first type of chain code was not used to define boundary pixels in the research done for this thesis.A method for converting chain codes of this type to boundary pixels and blocking codes is presentedby Samet in [6, 7]. Note that the method for finding neighbours used in Samets algorithm can besubstituted by Schrack’s method [3] when working with linear rather than regular quadtrees.startChain code ={23233233030300101011121221}2O(a)startFreeman chain ={56567701 122343}*(b)Figure A3 - Regions defined by chain codes33Conversion of chain codes of the second type into boundary pixels is trivial since each element of thechain code i.ndicates which pixel relative to the current one forms the next pixel along the boundary.By successively applying a neighbour finding algorithm for each new boundary pixel generated, all ofthe boundary pixels can be found. Schracks neighbour finding algorithm is an obvious choice, since itworks in constant time, and can be implemented as a register function (i.e. it is very fast).Finding the blocking code for each boundary pixel is accomplished using a two dimensional look-uptable (LUT). The indices of the LUT are the values of the current and previous chain code values foreach new pixel found. These values indicate which neighbours of the current pixel form the boundaryof the region from which can be inferred which sides of that pixel border on the exterior of the region.Table A3 shows the LUT and Figure A4 gives an example of it’s use.0 1 2 3 4 5 6 70 0010 0010 0000 0000 1110 1110 0110 01100011 0011 0001 0001 0000 0000 0111 01112 0011 0011 0001 0001 0000 0000 0111 01113 lOll loll 1001 1001 1000 1000 0000 00004 1011 1011 1001 1001 1000 1000 0000 00005 0000 0000 1101 1101 1100 1100 0100 01006 0000 0000 1101 1101 1100 1100 0100 01007 0010 0010 0000 0000 1110 1110 0110 0110Table A3 Look-up table to convert freeman codes to blocking codes (NWSE)row indices = previous code I column indices = current codeNSNWSEblocldngcode=LUT(5, 7) = (1110)Figure A4 - Freeman chain to blocking code conversion34A3 Scan Converting Lines and Circles in the Quadtree DomainIn computer graphics, the most common representation of objects is by polygons defined by theCartesian coordinates of their vertices. Finding the pixels which comprise the edges is achieved byscan converting the lines defined by successive vertex pairs of the polygon. Such a conversion isnecessary, for instance, when the proposed filling algorithm is used to fill a region defined by apolygon, since the required input for the algorithm is the set of all boundary pixels of the region.Many scan conversion algorithms for lines on the standard Cartesian raster are known. One inparticular is well suited to be adapted to the LQT domain such that the location codes of pixels alongthe line being scan-converted are derived directly without the need to encode the coordinates of thepixels. This algorithm is called the Midpoint Line Algorithm and was first published by Pitteway in1967 [13]. A thorough description of this algorithm is presented in [14], a summary of which is givenbelow, along with the details for implementing it in the LQT domain.For the discussion which ensues, assume that lines have a slope between 0 and 1 and that other slopescan be handled by appropriate reflections about the principal axis. The lower left endpoint is called(xo, o) and the upper right endpoint (xj, yj).Figure A5 shows a line in the process of scan conversion. Here, (Xp, Yp) is the pixel P which has justbeen selected as part of the scan converted line, and the next pixel must be either the eastern (E) orthe northeastern (NE) neighbour. Let Q be the intersection of the line being scan converted with theline x = Xp + 1. If the midpoint M between the eastern and northeastern neighbours lies above Q thenthe eastern neighbour must be the next pixel in the scan converted line , otherwise the northeasternneighbour will be the next pixel.By writing the equation of the line in implicit form, and substituting the coordinates for the nextmidpoint, a decision variable d can be defined which will determine which neighbour (E or NE) willform the next scan converted pixel. Thus if the function for the line being converted is35F(x,y)=ax+by+c=0, thend=F(M)=a(x+1)+b(y+)+cIf d >0 then the next scan converted pixel is the NE neighbour otherwise if d<0 the B neighbour willbe chosen as the next pixel. Note that if the line has the explicit form y = + B , a = dy, b=-dxand c = B•dx.It is possible to express the decision variable for the current pixel dnew in terms of the previousdecision variable d0ld. For example, if an eastern neighbour was just chosen as the current scanconverted pixel thendnew = a(xp+2)+ b(y+) + c, anddold = a(xp+l) + b(y+) +CW)d dnew = d0ld + a. Similarly, if a NE neighbour was chosen,3dnew = a(xp-i-2) + b(y+ j) + cand dnew = d0ld + a.+ b. Thus only the original decision variable dstart needs to be explicitlyevaluated.P = (Xp, Yp)Previous Choices for Choices forpixel current pixel next pixelFigure AS - Scan conversion of a line36dstart = F(x0+1, yo4)= a(xo+l) + b(yo+) + c= F(x, y) + a +=a+b, sinceF(x,y)=OIn order keep to integer arithmetic, we multiply dstart by 2 when evaluating it, since only the sign ofthe decision variable is important. As a consequence, we must multiply the increments to thedecision variable by 2. also. Figure A6 gives the complete algorithm for scan converting a line ofslope between 0 and 1 in the LQT domain. Note that Schrack’s neighbour finding algorithm [3] can beused here since it is fast, and requires no encoding or decoding. If the vertices of the line are given aslocation code, then no initial encode is required, however, a decode would be required in order tocalculate dx and dy.Line to LQT pixels (in vertexo, in vertexi, out LQT_pixels)BEGINdx = vertexi .x - vertexo.xdy = vertexi .y- vertexrj.yd =2*dydxIncrE =2*dyIncrNE = 2 * (dy - dx)location = encode(vertex0)OUTPUT (location)WHILE (location encode(vertexi)) DOIF(dO)THENd = d + IncrElocation = neighbour(location, E)ELSEd = d + lncrNElocation = neighbour(location, NE)END IFOUTPUT(location)END WHILEENDFigure A6 Scan conversion pseudocode for line in LQT domain37Finding the blocking code for the pixels generated by the scan conversion is trivial. Assuming thatthe interior of the region lies to the left of the line, the pixel will be blocked on the south if it waschosen as an eastern neighbour, and will be blocked on the east and south if it was chosen as a northeastern neighbour.A similar set of decision variables as those described above can be derived for the scan conversion ofcircles. The resulting scan conversion algorithm uses only integer arithmetic and avoidsmultiplications while generating pixels. A discussion of this technique can be found in [14] by theinterested reader. Important to note here is that by use of an LQT neighbour finding algorithm, thescan conversion algorithm can be modified to generate the location codes of the circle’s boundarypixels directly (without encoding individual pixels). Figure A7(a) gives the modified version of thealgorithm. It takes advantage of the symmetry of the circle by generating the pixels for only one 45degree segment. The other symmetrical pixels are derived by using the mifforing and rotationtechniques described in Appendix Al. Figure A7(b) gives the algorithm for generating 8 symmetricalpixels given one input pixel. Note that the circle generated is centred on the origin. To shift thecentre of the circle, the LQT pixels can be translated as they are generated by using the dilatedinteger arithmetic presented in [3].A4 Converting from Runs to LQT CellsIt is sometimes convenient to express objects in the LQT domain as a number of runs of black orwhite pixels in Morton sequence order. A run of pixels is defined by a start and an end pixel, whoselocations are given as LQT location codes. Such object descriptions are used as the output from theMark and Abel filling algorithm [10]. To convert a run of black pixels into LQT cells for comparisonwith output from the proposed filling algorithm, an method was developed which operates on thelocation codes of the start and end pixels of the runs.38Circle to LQT pixels (in radius)BEGINd =1-radiusdelE =3delSE = -2 * radius + 5location = encode(0, radius)Write Circle Pixels(Iocation)WHILE (location & t < ((location & t) <<1 )) DOIF (d 0) THENd=d+delEdelE = delE + 2delSE = del SE + 2location = neighbour(location, E)ELSEd = d + deISEdelE=delE÷2delSE = del SE + 4location = neighbour(location, SE)END IFWrite Circle Pixels(Iocation)END WHILEEND(a)Write Circle Pixels (in location)BEGINOUTPUT(Iocation)OUTPUT(Mirror X (location))OUTPUT(Mirror Y (location))OUTPUT(Rotate 180 (location))OUTPUT(Mirror Main Diagonal (location))OUTPUT(Mirror Cross Diagonal (location))OUTPUT(Rotate 90 (location))OUTPUT(Rotate 270 (location))END(b)Figure A7 Scan conversion pseudocode for circle in LQT domainTo understand the conversion algorithm, it is useful to know how to convert an LQT cell into a Mortonsequence run of pixels. Recall that an LQT cell is described by the location code of its SW corner (inthe convention used in this thesis) and by its level within the quadtree measured from the root of thetree. The start pixel of the run is thus trivially the location code of the LQT cell. The last pixel of the39LQT cell when following the Morton sequence is the NE corner which, according to rule 2 of section 2will have a quaternary location code formed by substituting trailing zeros of the cell location code bytrailing threes such that the number of zeros substituted is equal to the resolution of the quadtreedomain minus the level of the LQT cell (r-level). For example the NE corner pixel of (21000, 3) is210334, where r=5 in this case.Run To LQT (in blackrun, out LQTcells)BEGINnewstart := 0start := run.start=0WHILE (newstart run.end) DOFind Largest Cell (start, run.end, cellsize, newstart)LQTcelIs.location_code := startLQTcells1Jev := ceilsizestart := newstartincrement iEND WHILEENDFind Largest Cell (in start, in end, out cellsize, out newstart)BEGIN=0NE corner := startWHILE (NE corner < stop) DOIF (next least significant quaternary digit of NE corner is zero) THENsubstitute quaternary 0 with the digit 3increment iELSEEXIT WHILEEND IFEND WHILEnewstart NE corner + 1cellsize := r-iENDFigure A8 Run To LQT conversion algorithmGiven a run of black pixels in Morton sequence order, the task of converting to LQT cells consists offinding the largest LQT cell having the same location code as the starting pixel of the run, but whoseNE corner pixel has a location code which is not greater than the end pixel of the run. Having found40this cell, the black run is shortened such that the new start pixel of the run has a location code onegreater than that of the NE corner of the cell just found. The process is repeated until the new run haszero length, and all of the LQT cells contained in the run have been found. Figure A8 gives thepseudocode for the algorithm.41
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Filling contours on the linear quadtree domain by insertion...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Filling contours on the linear quadtree domain by insertion and traversal Wilke, Lars Martin 1993
pdf
Page Metadata
Item Metadata
Title | Filling contours on the linear quadtree domain by insertion and traversal |
Creator |
Wilke, Lars Martin |
Date Issued | 1993 |
Description | An algorithm is presented which fills contours described by a set of pixels whose locations are given in unsorted linear quadtree (LQT) form. Each pixel requires an associated blocking code which indicates locally in which direction the region should grow. The technique takes advantage of certain characteristics of LQT location codes to determine if the boundary pixels fall on the edges or vertices of lower resolution LQT cells. This information allows for the automatic determination of boundary cells after the pixels have been inserted into a regular quadtree. Remaining uncoloured cells are coloured using conventional techniques. The algorithm compares favourably with existing LQT filling algorithms both in time and space complexity. The technique avoids explicit sorting of the input pixels or output cells by location code, and no condensation of cells is required. Traversing the regular quadtree in preorder generates the sorted output cells as an LQT. |
Extent | 791067 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-02-23 |
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. |
IsShownAt | 10.14288/1.0065012 |
URI | http://hdl.handle.net/2429/4926 |
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-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-0071.pdf [ 772.53kB ]
- Metadata
- JSON: 831-1.0065012.json
- JSON-LD: 831-1.0065012-ld.json
- RDF/XML (Pretty): 831-1.0065012-rdf.xml
- RDF/JSON: 831-1.0065012-rdf.json
- Turtle: 831-1.0065012-turtle.txt
- N-Triples: 831-1.0065012-rdf-ntriples.txt
- Original Record: 831-1.0065012-source.json
- Full Text
- 831-1.0065012-fulltext.txt
- Citation
- 831-1.0065012.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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065012/manifest