These provide an elegant and useful method of encoding a spatial occupancy array and are a natural consequence of the splitting of the ``split-and-merge'' approach to image segmentation which was introduced earlier. They can give a compact representation sometimes described as a pyramid or tree. The technique is most easily applied if the image dimensions are 2n by 2n where n is an integer. Figure 1 illustrates a quad tree in which each leaf of the tree defines a homogeneous region as defined by a relevant common pixel property. An algorithm for quad tree generation may be expressed recursively,

Procedure Quad_Tree ( pyramid: array of integer; x,y,level: integer);
(* NW, NE, SW, SE are the subnodes of size 2n-1 of a node of size 2n *)
begin
Newnode(P);
TYPE(P):= Index(pyramid(x,y,level));
if TYPE(P) is HOMOGENEOUS then return P
else
	 begin
 		 SW(P):=Quad_Tree(pyramid,2*x,2*y,level+1);
 		 SE(P):=Quad_Tree(pyramid,2*x+2*level,2*y,level+1);
 		 NW(P):=Quad_Tree(pyramid,2*x,2*y+2*level,level+1);
 		 NE(P):=Quad_Tree(pyramid,2*x+2*level,2*y+2*level,level+1);
 		 return(P);
	 end;
end;

In this example, Index is an indexing function which extracts the appropriate homogeneity property P, of the region provided it is homogeneous. Several elegant algorithms have been proposed to compute properties of quad trees. However, the quad tree and it's associated resolution pyramid have several disadvantages as a representation. Once a grid size is fixed it cannot be extended to finer resolution so information can be lost. Operations are only easy if the same grid is used; shift, rotation or scale alterations lead to the need for cumbersome conversion routines.