UBC Theses and Dissertations
A non-recursive border finding algorithm for linear quadtree based images Tang, Shao Kang
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).
Item Citations and Data