“Contour filling in raster graphics” by Pavlidis

  • ©Theo Pavlidis




    Contour filling in raster graphics



    The paper discusses algorithms for filling contours in raster graphics. Its major feature is the use of the line adjacency graph for the contour in order to fill correctly nonconvex and multiply connected regions, while starting from a “seed.” Because the same graph is used for a “parity check” filling algorithm, the two types of algorithms can be combined into one. This combination is useful for either finding a seed through a parity check, or for resolving ambiguities in parity on the basis of connectivity.


    1. Newman, W. M. and Sproull, R. F. Principles of Interactive Graphics, second edition, McGraw-Hill, 1979.
    2. Brassel, K. E. and R. Fegeas “An Algorithm for Shading of Regions on Vector Display Devices,” Proc. SIGGRAPH 79, pp. 126-133.
    3. Pavlidis T., “Filling algorithms for raster graphics,” Comput, Graphics Image Proc. 10, 1979, pp. 126-141. Also in preliminary form in Proc. SIGGRAPH 78, pp. 161-166.
    4. Sproull, R. F. Review of {3} in Computing Reviews November 1979, p. 500. (Review No.35, 467.)
    5. Ackland, B.D. and Weste, N. “The Edge Flag Algorithm – A Fill Method for Raster Scan Displays,” IEEE Trans. Computers, C-30 (1980), pp. 41-48.
    6. Lieberman, M. “How to color in a coloring book,” Proc. SIGGRAPH 78, pp. 111-116.
    7. Smith, A. R. “Tint fill,” Proc. SIGGRAPH 79, pp. 276-283.
    8. Caspers, B. E. and Denes, P. B. “An Interactive Terminal for the Design of Advertisements,” Bell System Technical Journal, 58 (1979), pp. 2189-2216.
    9. Shani, U. “Filling regions in binary raster images – a graphtheoretic approach,” Proc. SIGGRAPH 80, pp. 321-327.
    10. Aho, A. V., J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms Addison-Wesley, 1974.
    11. Pavlidis, T. Structural Pattern Recognition, Springer Verlag, Berlin-Heidelberg-New York, 1977.
    12. Pavlidis, T. and Steiglitz, K. “The Automatic Counting of Asbestos Fibers in Air Samples,” IEEE Trans. Computers, C-27, 1978, pp. 258-261.
    13. Shapiro, L. “Data Structures for Picture Processing,” Proc. SIGGRAPH 78, pp. 140-146.
    14. Rosenfeld, A. and Kak, A. C. Digital Picture Processing, Academic Press, New York, 1976.
    15. Pavlidis, T. Algorithms for Graphics and Image Processing, Computer Science Press, Maryland, 1981 (in press).

ACM Digital Library Publication:

Overview Page: