“Tint fill” by Smith

To fill a connected area of a digital image is to change the color of all and only those pixels in the area. Fill algorithms for areas defined by sharp boundaries (e.g., a white area surrounded by a black curve) have been implemented at several color computer graphics installations. This paper presents an algorithm for the more difficult problem of filling areas with shaded boundaries (e.g., a white area surrounded by a curve consisting of several shades of gray). These images may arise from digitizing photographs or line drawings with a scanning video camera, or they may be generated by programs which produce antialiased line segments or dekink black-and-white images. When an area in such an image is to be filled with a new color, it is desirable to have the fill algorithm understand the shaded edges and maintain the shading with shades of the new color instead of the old. The tint fill algorithm presented here accomplishes this task. Its name arises from its ability to change only the tint (hue and saturation) of a pixel, leaving the value (blackness) unchanged. Although the algorithm was motivated by and is written in terms of color, it has a more general interpretation, which is also presented.

1. Kenneth C. Knowlton, “The Beflix Movie Language”, in Proceedings of the Spring Joint Computer Conference, 1964. (See also, Kenneth C. Knowlton and Lorinda L. Cherry, “Fortran IV Beflix”, in Proceedings of the UAIDE Annual Convention, San Diego, 1969.)
2. W. J. Kubitz and W.J. Poppelbaum, “The Tricolor Cartograph: A Display System with Automatic Coloring Capabilities”, in Information Display, November/December, 1969, pp.76-79.
3. Henry Lieberman, “How to Color in a Coloring Book”, in Proceedings of the Fifth Annual Conference on Computer Graphics and Interactive Techniques (Siggraph 78) August 21-25, 1978, pp. 111-116.
4. Joan E. Miller, personal communication, Bell Labs, Murray Hill, N.J., July 1978.
5. Theodosios Pavlidis, “Filling Algorithms for Raster Graphics”, in Proceedings of the Fifth Annual Conference on Computer Graphics and Interactive Techniques (Siggraph 78), August 21-25, 1978, pp. 161-166.
6. Craig Reynolds, “Filling Polygons”, in Architecture Machinations, Department of Architecture, Massachusetts Institute of Technology, Room 9-518, May 3, 1977.
7. Azriel Rosenfeld, “Connectivity in Digital Pictures”, in JACM 17:146-160, January 1970.
8. Alvy Ray Smith, “Color Gamut Transform Pairs”, in Proceedings of the Fifth Annual Conference on Computer Graphics and Interactive Techniques (Siggraph 78), August 21-25, 1978, pp. 12-19.
9. Alvy Ray Smith, “Paint”, Technical Memo No. 7, Computer Graphics Lab, NYIT, Old Westbury, NY 11568, July 1978.
10. Garland Stern, “SoftCel – An Application of Raster Scan Graphics to Conventional Cel Animation”, in these Proceedings.