“Filling regions in binary raster images: A graph-theoretic approach” by Shani

Filling regions in raster images is the term given to the problem of extracting a connected region (that contains some preselected seed pixel) and filling it with some color. A connected region is formally defined as the collection of all pixels that are in the transitive closure of a pixel-connectivity operator that is applied to the seed. For example, the 4-pixel-connectivity operator selects all pixels that are (spatially) 4-connected to the pixel operand, and have the same color. This problem can be solved relatively easily if the fill color is distinguishable so that every pixel, once colored (i.e. flagged OLD) will not be considered again. In binary images, the fill “color” is usually a binary pattern and therefore, a “colored” pixel may still have its previous (e.g., black or white) color. This fact makes the problem non-trivial. In this paper, a region to be filled is represented as a connected directed a-cyclic planar graph in which nodes are regular regions (defined below) that are easy to handle. An arc connects a regular region to its neighbor below which shares a common horizontal sub-boundary. Based on this abstract representation of a region, a formulation of the filling problem is developed as a variant of graph traversing. The difficulties imposed by filling with a binary pattern, and the avoidance of an explicit description of the graph are explored and a solution is presented. This solution utilizes the frame buffer (that is used to display the image) for improved efficiency of a graph traversal algorithm. This method turns out to be similar to [Lieberman-78], that is shown here to be incorrect. The complexity of the new algorithm is 0(N*L+ N*Log N), compared to 0(N*L*Log N) there, where N is the number of nodes in the graph and L is the average composite degree of each node. A proof of correctness for the new algorithm is given too.

1. Aho, A.V. et al. The Design and Analysis of Computer Algorithms, Addison Wesley, (1976).
2. Berge, C. Graphs and Hyper Graphs, North Holland/American Alsevier, (1976).
3. Guttag, S. Abstract data types and the development of data structures, CACM, 20(6), (June 1977), 396-404.
4. Kay, A.L. Microelectronics and the personal computer, Scientific American 273(3), (September 1977), 231-244.
5. Knuth, D.E. The Art of Computer Programming, vol 1, section 2.2.1.
6. Lieberman, H. How to color in a coloring book, Proceedings SIGGRAPH’78, (August 1978), 111-116.
7. Smith, A.R. Tint fill, Proc. SIGGRAPH’79, (August 1979), 276-283.