Quadtree decomposition of binary structuring elements
Kenji Shoji · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1991
In order to efficiently perform morphological binary operations by relatively large structuring elements, we propose to decompose each structuring element into squares with 2 X 2 pixels by the quadtree approach. There are two types of decomposition--the dilation decomposition and the union decomposition. The first type decomposition is very efficient, but it is not necessarily always possible. The decomposition of second type is available for any structuring element, but the time cost of computation is proportional to the area of the structuring element. The quadtree decomposition proposed here is the combination of these two types of decomposition, and exists for any structuring element. When the Minkowski addition A (direct sum) B or the Minkowski subtraction A - B is computed, the number of times of the union/intersection of translations of the binary image is about the number of leaves of the quadtree representation of the structuring element B, which is roughly proportional to the square root of the area of B. In this paper, an algorithm for quadtree decomposition is described, and experimental results of this decomposition for some structuring elements are shown.