Editing Quadtree (section)

==Image processing using quadtrees==
Quadtrees, particularly the [[#Region_quadtree|region quadtree]], have lent themselves well to image processing applications. We will limit our discussion to binary image data, though region quadtrees and the image processing operations performed on them are just as suitable for colour images.<ref name="Aluru2004" /><ref name=":0" />

===Image union / intersection===
One of the advantages of using quadtrees for image manipulation is that the set operations of union and intersection can be done simply and quickly.<ref name="Aluru2004" /><ref>{{Cite book|title=Efficient Computation and Data Structures for Graphics|last=Hunter|first=G. M.|publisher=Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University|year=1978}}</ref><ref>{{Cite journal|last1=Hunter|first1=G. M.|last2=Steiglitz|first2=K.|year=1979|title=Operations on images using quad trees|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=2|issue=2|pages=145–153|doi=10.1109/tpami.1979.4766900|pmid=21868843|s2cid=2544535}}</ref><ref>{{Cite journal|last=Schneier|first=M.|year=1981|title=Calculations of geometric properties using quadtrees|journal=Computer Graphics and Image Processing|volume=16 | issue = 3 |pages=296–302|doi=10.1016/0146-664X(81)90042-3}}</ref>
<ref>{{Cite book|title=Handbook of Data Structures and Applications|last=Mehta|first=Dinesh|publisher=Chapman and Hall/CRC Press|year=2007|pages=397}}</ref>
Given two binary images, the image union (also called ''overlay'') produces an image wherein a pixel is black if either of the input images has a black pixel in the same location. That is, a pixel in the output image is white only when the corresponding pixel in ''both'' input images is white, otherwise the output pixel is black. Rather than do the operation pixel by pixel, we can compute the union more efficiently by leveraging the quadtree's ability to represent multiple pixels with a single node. For the purposes of discussion below, if a subtree contains both black and white pixels we will say that the root of that subtree is coloured grey.

The algorithm works by traversing the two input quadtrees (<math>T_1</math> and <math>T_2</math>) while building the output quadtree <math>T</math>. Informally, the algorithm is as follows. Consider the nodes <math>v_1 \in T_1</math> and  <math>v_2 \in T_2</math> corresponding to the same region in the images.
* If <math>v_1</math> or <math>v_2</math> is black, the corresponding node is created in <math>T</math> and is colored black. If only one of them is black and the other is gray, the gray node will contain a subtree underneath. This subtree need not be traversed.
* If <math>v_1</math> (respectively, <math>v_2</math>) is white, <math>v_2</math> (respectively, <math>v_1</math>) and the subtree underneath it (if any) is copied to <math>T</math> .
* If both <math>v_1</math> and <math>v_2</math> are gray, then the corresponding children of <math>v_1</math> and <math>v_2</math> are considered.

While this algorithm works, it does not by itself guarantee a minimally sized quadtree. For example, consider the result if we were to union a checkerboard (where every tile is a pixel) of size  <math>2^{k} \times 2^{k}</math> with its complement. The result is a giant black square which should be represented by a quadtree with just the root node (coloured black), but instead the algorithm produces a full 4-ary tree of depth <math>k</math>. To fix this, we perform a bottom-up traversal of the resulting quadtree where we check if the four children nodes have the same colour, in which case we replace their  parent with a leaf of the same colour.<ref name="Aluru2004" />

The intersection of two images is almost the same algorithm. One way to think about the intersection of the two images is that we are doing a union with respect to the ''white'' pixels. As such, to  perform the intersection we swap the mentions of black and white in the union algorithm.

===Connected component labelling===
Consider two neighbouring black pixels in a binary image. They are ''adjacent'' if they share a bounding horizontal or vertical edge. In general, two black pixels are ''connected'' if one can be  reached from the other by moving only to adjacent pixels (i.e. there is a path of black pixels between them where each consecutive pair is adjacent). Each maximal set of connected black pixels  is a ''connected component''. Using the quadtree representation of images, [[Hanan Samet|Samet]]<ref>{{Cite journal|last=Samet|first=H.|year=1981|title=Connected component labeling using quadtrees|journal=Journal of the ACM|volume=28 | issue = 3 |pages=487–501|doi=10.1145/322261.322267|author-link=Hanan Samet|citeseerx=10.1.1.77.2573|s2cid=17485118}}</ref>  showed how we can find and label these connected components in time proportional to the size of the  quadtree.<ref name="Aluru2004" /><ref name=":1" /> This algorithm can also be used for polygon colouring.

The algorithm works in three steps: 
# establish the adjacency relationships between black pixels 
# process the equivalence relations from the first step to obtain one unique label for each  connected component 
# label the black pixels with the label associated with their connected component
To simplify the discussion, let us assume the children of a node in the quadtree follow the [[Z-order curve|''Z''-order]] (SW, NW, SE, NE). Since we can count on this structure, for any cell we know how to navigate the quadtree to find the adjacent cells in the different levels of the hierarchy.

Step one is accomplished with a [[Tree traversal#Post-order|post-order traversal]] of the quadtree. For each black leaf <math>v</math> we look at the node or nodes representing cells that are Northern neighbours and Eastern neighbours (i.e. the Northern and Eastern cells that share edges with the cell of <math>v</math>). Since the tree is organized in ''Z''-order, we have  the invariant that the Southern and Western neighbours have already been taken care of and accounted for. Let the Northern or Eastern neighbour currently under consideration be <math>u</math>. If <math>u</math> represents black pixels:
* If only one of <math>u</math> or <math>v</math> has a label, assign that label to the other cell
* If neither of them have labels, create one and assign it to both of them
* If <math>u</math> and <math>v</math> have different labels, record this label equivalence and move on
Step two can be accomplished using the [[disjoint-set data structure|union-find data structure]].<ref>{{Cite journal|last=Tarjan|first=R. E.|year=1975|title=Efficiency of a good but not linear set union algorithm|url=http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/p215-tarjan.pdf|journal=Journal of the ACM|volume=22 | issue = 2 |pages=215–225|doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free}}</ref> We start with each unique label as a separate set. For every equivalence relation noted in the first step, we union the  corresponding sets. Afterwards, each distinct remaining set will be associated with a distinct connected component in the image.

Step three performs another post-order traversal. This time, for each black node <math>v</math> we use the union-find's ''find'' operation (with the old label of <math>v</math>) to find and assign <math>v</math> its new label (associated  with the connected component of which <math>v</math> is part).