Dilation algorithm for a linear quadtree

摘要

A dilation algorithm for a linear quadtree is presented. This can be used to expand the black regions of a region quadtree by a user-specified amount. The algorithm requires two traversals through the ordered quadtree leaf set, the second traversal being in the opposite direction to the first. No explicit neighbour finding is required. Timings are compared with those obtained using an existing one-pass algorithm. The two-pass algorithm is faster than the one-pass for expansions of typical real images, and this speed increase becomes more pronounced as the expansion and the complexity of the image increase.