Computing the Euler Number of an Image from Its Quadtree

摘要

An algorithm is presented which computes the Euler number, ie., the number of components minus the number of holes, of a binary image represented by the quadtree. The local property counting techniques used with an array representation are generalized to counting local node configurations in a quadtree. The average worst case running time of the algorithm is proportional to the product of the number of nodes representing the components and the logarithm of the image diameter. (Author)