An algorithm is presented for computing the total perimeter of a binary image represented by a quadtree. The algorithm explores each segment of the border once and only once. Analysis of the algorithm shows that its worst- case average execution time is proportional to the product of the log of the image diameter and the number of nodes in the tree.