Generating automatically tuned bitmaps from outlines

ABSTRACT

Consider the problem of generating bitmaps from character shapes given as outlines. The obvious scan-conversion process does not produce acceptable results unless important features such as stem widths are carefully controlled during the scan-conversion process. This paper describes a method for automatically extracting the necessary feature information and generating high-quality bitmaps without resorting to hand editing. Almost all of the work is done in a preprocessing step, the result of which is an intermediate form that can be quickly converted into bitmaps once the font size and device resolution are known. A heuristically defined system of linear equations describes how the ideal outlines should be distorted in order to produce the best possible results when scan converted in a straightforward manner. The Lova´sz basis reduction algorithm then reduces the system of equations to a form that makes it easy to find an approximate solution subject to the constraint that some variables must be integers. The heuristic information is of such a general nature that it applies equally well to Roman fonts and Japanese Kanji.

REFERENCES

• 1: Adobe Press, Adobe Type 1 Font Format, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 2: ~APLEY, P. G. Automatic generation of digital typographic images from outline masters. ~Coarse note of ACM SIGGRAPH 88, Coarse 14: Digital Typography. ACM, New York, 1988.
• 3: CORPORATE Apple Computer, Inc., Technical introduction to the Apple IIGS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
• 5: ~BLUM, H., AND NAGEL, R.N. Shape description using weighted symmetric axis features. ~Pattern Recogmtion 10, 3 (1978), 167-{80.
• 6: ~FORTUNE, $. Sweepline algorithms for voronoi diagrams. Algorithmica 2 (1987), 153-174.
• 7: M Grötschel , L Lovász , A Schrijver, Relaxations of vertex packing, Journal of Combinatorial Theory Series B, v.40 n.3, p.330-343, June 1986 [doi>10.1016/0095-8956(86)90087-0]
• 8: Roger D. Hersch, Character generation under grid constraints, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.243-252, July 1987
• 9: ~HOBBY, J.D. Dtgtttzed Brush Trajectories. Ph.D. dissertation. Dept. of Computcr Science, ~Stanford Univ., Stanford, Calif., 1985.
• 10: John D. Hobby, Rasterizing curves of constant width, Journal of the ACM (JACM), v.36 n.2, p.209-229, April 1989 [doi>10.1145/62044.62045]
• 11: Donald Ervin Knuth, Metafont: The Program, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 12: ~LEE, D.T. Medial axis transformation of a planar shape. 1EEE Trans. Patter~ ,4nal. Mach. ~hzt. PAMI-4 (1982), 363-369.
• 13: ~LENSTRA, A. K., LENSTRA, H. W., JR., AND LOVASZ, L. Factoring polynomials with rational ~coefficients. Math. Ann. 261 (1982), 515-534.
• 14: Ugo Montanari, Continuous Skeletons from Digitized Images, Journal of the ACM (JACM), v.16 n.4, p.534-549, Oct. 1969 [doi>10.1145/321541.321543]
• 15: Theo Pavlidis , Christopher J. Van Wyk, An automatic beautifier for drawings and illustrations, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.225-234, Jul. 1985
• 16: ~PLASS, M. F., AND HOCHSCHILD, P. H. Optimal rendering of characters and images on ~discrete devices. ACM Tratls. Graphtcs, to appear.
• 17: ~VAN EMDE BOAS, P. Anothe~ NP-complete partition problem and the complexity of comput- ~ing short vectors in a lattice. Report 81-04, Math. Institute. Univ. of Amsterdam, Amsterdam, ~The Netherlands, 1981.
• 18: ~YAP, C. K. An O(nlog tz) algorithm for the voronoi diagram of a set of simple curve ~segments. Disc. Comput. Geom. 2 (1987), 365-393.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Bitmap and framebuffer operations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Digitizing and scanning
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Performance

Keywords:
Lova´sz basis reduction, feature recognition, fonts, scan-conversion