John D. Hobby
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.
- 1 ~ADOBE SYSTEMS INCORPORATED. Adobe type 1 font format, 1990. Google Scholar
- 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.Google Scholar
- 3 ~APPLE COMPUTER, INC. Technical Introduction to the Macintosh Family. Addison-Wesley, ~Reading, Mass., 1987. Google Scholar
- 4 ~BABAI, L. On Lovftsz' lattice reduction and the nearest lattice point problem. Combtnatortca ~6, 1 (1986), 1 13. Google Scholar
- 5 ~BLUM, H., AND NAGEL, R.N. Shape description using weighted symmetric axis features. ~Pattern Recogmtion 10, 3 (1978), 167-{80.Google Scholar
- 6 ~FORTUNE, $. Sweepline algorithms for voronoi diagrams. Algorithmica 2 (1987), 153-174.Google Scholar
- 7 ~GR(STSCHEL, M., LOVASZ, L., AND SHRIJVER, h. Relaxation of vertex packing. J. Combinat. ~Theoly, Series B 40, 3 (1986), 330-343. Google Scholar
- 8 ~HERSCH, R.D. Character generation under grid constraints. Computer Graphics 21, 4 (1987), ~243-25 I. Google Scholar
- 9 ~HOBBY, J.D. Dtgtttzed Brush Trajectories. Ph.D. dissertation. Dept. of Computcr Science, ~Stanford Univ., Stanford, Calif., 1985.Google Scholar
- 10 ~HOBBY, J.D. Rasterizing curved lines of constant width. J. ACM36, 2 (Apr. 1989), 209-229. Google Scholar
- 11 KNUTH, D.E. MET,~FONT the Program. (Vol. D of Computers and T3pesetting.) Addison- ~Wesley, Reading, Mass. 1986. Google Scholar
- 12 ~LEE, D.T. Medial axis transformation of a planar shape. 1EEE Trans. Patter~ ,4nal. Mach. ~hzt. PAMI-4 (1982), 363-369.Google Scholar
- 13 ~LENSTRA, A. K., LENSTRA, H. W., JR., AND LOVASZ, L. Factoring polynomials with rational ~coefficients. Math. Ann. 261 (1982), 515-534.Google Scholar
- 14 ~MONTANAm, U. Continuous skeletons from digital images. J. ACM 16, 4 (Oct. 1969), ~534-549. Google Scholar
- 15 ~PAVLIDIS, T., AND VAN WYK, C.J. An automatic beautifier for drawings and illustrations. ~Comput. Graphics 19, 3 (July 1985), 225-234. Google Scholar
- 16 ~PLASS, M. F., AND HOCHSCHILD, P. H. Optimal rendering of characters and images on ~discrete devices. ACM Tratls. Graphtcs, to appear.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- Generating automatically tuned bitmaps from outlines
Recommendations
Two template matching approaches to Arabic, Amharic and Latin isolated characters recognition
With the establishment of commercial OCR systems for Latin text, recent research efforts have been directed at the design of recognition systems for non-Latin scripts, such as Japanese, Cyrillic, Chinese, Hindi, Tibetan, and in particular Arabic. The ...
Automatic generation of large-scale handwriting fonts via style learning
SA '16: SIGGRAPH ASIA 2016 Technical BriefsGenerating personal handwriting fonts with large amounts of characters is a boring and time-consuming task. Take Chinese fonts as an example, the official standard GB18030-2000 for commercial font products contains 27533 simplified Chinese characters. ...
Automatic script identification from images using cluster-based templates
ICDAR '95: Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 1) - Volume 1We describe a system that automatically identifies the script used in documents stored electronically in image form. The system can learn to distinguish any number of scripts. It develops a set of representative symbols (templates) for each script by ...
Comments