“Rectangular convolution for fast filtering of characters” by Naiman and Fournier

While the race towards higher-resolution bitmap displays is still on, many grayscale displays have appeared on the scene. To fully utilize their capabilities, grayscale fonts are needed, and these can be produced by filtering bi-level masters. Most of the efficient filtering techniques cannot directly be applied. For example, prefiltering is impractical, due to the number of character masters and the requirement of sub-pixel positioning. Furthermore, we would like to impose as few restrictions as possible on the characteristics of the filter, in order to facilitate exploration into the quality of various filters.We describe a fast filtering technique especially adapted to this task. The characters are decomposed into rectangles, and a summed-area representation of the filter is efficiently convolved with each individual rectangle to construct the grayscale character. For a given filter, the number of operations is O (linear size of the grayscale character), which is optimal.We give an analysis of the efficiency of this technique, and examples of its implementation applied to various families of fonts and point sizes. The performance of the implementation is such that filtering characters for grayscale displays is feasible in realtime on personal workstations.

1. Bigelow, C. and D. Day, “Digital Typography,” Scientific American, Volume 249, Number 2, August 1983, pp. 106-119.
2. Blackwell, H. R., “Contrast Thresholds of the Human Eye,” Journal of the Optical Society of America, Volume 36, 1946, pp. 642-643.
3. Bruckstein, A. M., “On Optimal Image Digitization,” Electrical Engineering Publication Number 577, Faculty of Electrical Engineering, Technion Israel Institute of Technology, Haifa, Israel, February 1986.
4. Cornsweet, T. N., Visual Perception, Academic Press, New York, 1970.
5. Catmull, E., “A Tutorial on Compensation Tables,” Computer Graphics, Volume 13, Number 2, August 1979, pp. 1-7. SIGGRAPH 1979 Proceedings.
6. Crow, F. C., “The Use of Grayscale for Improved Raster Display of Vectors and Characters,” Computer Graphics, Volume 12, Number 3, August 1978, pp. 1-6. SIGGRAPH 1978 Proceedings.
7. Crow, F. C., “Summed-Area Tables for Texture Mapping,” Computer Graphics, Volume 18, Number 3, July 1984, pp. 207-212. SIGGRAPH 1984 Proceedings.
8. Ferrari, L. A. and J. Sklansky, “A Fast Recursive Algorithm for Binary-Valued Two-Dimensional Filters,” Computer Vision, Graphics, and Image Processing, Volume 26, 1984, pp. 292-302.
9. Fuchs, D. R. and D. E. Knuth, “Optimal Font Caching,” STAN-CS-82-901, Department of Computer Science, Stanford University, Stanford, California, March 1982.
10. Gould, J. D. and N. Grischkowsky, “Doing the Same Work with Hard Copy and with Cathode-Ray Tube (CRT) Computer Terminals,” Human Factors, Volume 26, Number 3, June 1984, pp. 323- 337.
11. Guibas, L. J. and J. Stolfi, “A Language for Bitmap Manipulation”, ACM Transaction on Graphics, Volume 1, Number 3, July 1982, pp. 191-214.
12. Heckbert, P. S., “Filtering by Repeated Integration,” Computer Graphics, Volume 20, Number 4, August 1986, pp. 315-321. SIGGRAPH 1986 Proceedings.
13. Kajiya, J. and M. Ullner, “Filtering High Quality Text for Display on Raster Scan Devices,” Computer Graphics, Volume 15, Number 3 August 1981, pp. 7-15. SIGGRAPH 1981 Proceedings.
14. Kobayashi, S. C., “Optimization Algorithms for Grayscale Fonts,” B. Sc. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, June 1980.
15. Kou, L., G. Markowski and L. Berman, “A Fast Algorithm for Steiner Trees,” Acta lnformatica, Volume 15, 1981.
16. Leler, W. J., “Human Vision, Anti-Aliasing, and the Cheap 4000 Line Display,” Computer Graphics, Volume 14, Number 3, July 1980, pp. 308-313. SIGGRAPH 1980 Proceedings.
17. Lingas, A., R. Pinter, R. Rivest, and A. Shamir, “Minimum Edge Length Decompositions of Rectilinear Figures,” Proceedings of the 12th Annual Allerton Conference on Communication, Control, and Computing, Illinois, 1982.
18. Lingas, A., “Heuristics for Minimum Edge Length Rectangular Partitions of Rectilinear Figures,” in Theoretical Computer Science, Edited by A. B. Cremers and H. P. Kriegel, Springer-Verlag, Berlin, January 1983, pp. 199-219.
19. Naiman, A. C., “High-Quality Text for Raster Displays,” M. Sc. Thesis, Department of Computer Science, University of Toronto, Toronto, Ontario, 1985.
20. Negroponte, N., “Soft Fonts,” Proceedings, Society for Information Display, 1980.
21. Pratt, W. K., Digital Image Processing, John Wiley and Sons, New York, 1978.
22. Schmandt, C., “Fuzzy Fonts,” Proceedings of the National Computer Graphics Association, 1983.
23. Seitz, C., et al., “Digital Video Display System with a Plurality of Gray-Scale Levels,” United States Patent Number 4,158,200.
24. Sholtz, P. N., “Making High-Quality Colored Images on Raster Displays,” Computer Science Research Report RC9632 (#42528), IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, October 1982.
25. Shurtleff, D. A., How to Make Displays Legible, Human Interface Design, La Mirada, California, 1980.
26. Warnock, J. E., “The display of Characters Using Gray Level Sample Arrays,” Computer Graphics, Volume 14, Number 3, July 1980, pp. 302-307. SIGGRAPH 1980 Proceedings.
27. Williams, L., “Pyramidal Parametrics,” Computer Graphics, Volume 17, Number 3, July 1983, pp. 1- 11. SIGGRAPH t983 Proceedings.