Since I discovered the world of TeX, and a little later, that of MetaFONT, I’ve been interested in font design. Particularly, I’ve been intrigued by the problem of creating high-quality outline fonts. It seems to me that the quality of the programs that produce the Computer Modern fonts are just a little(?) beyond the dedication and skill levels of amateurs like me. Since the only other way of producing outline fonts is to directly create the outlines, I’ve been interested in the problems involved in turning physical sketches of characters into their mathematical representations. All of this feeding back into my interest in math and curves, of course :). Here are the results of my preliminary research:
The Problem Defined
The main problem encountered in turning physical sketches into fonts is that of fitting the various functions used (splines, bezier curves, quadratic curves, etc.) to the bitmap images. In turn, the primary problem involved in fitting these curves is determining the edges of the bitmaps.
Edge-finding
Originally, this was my stumbling block: how to determine the edges of the individual glyphs, without human guidance. There are algorithms, like Hough Transforms, convolution filtering, and others, but these require too much mathematical sophistication, and essentially are only capable of transforming one image into another image, albeit the second image is a monochrome image, and has ‘less’ information than the first. But, what we want ideally, is a method that not only finds edges, but also determines the connectivity of these edges. In other words, we want to determine not just edges, but also contours. This makes sense, considering the problem: it is important that the counters of the font, for example, are closed contours. General algorithms exist for this also, but all IMO are ad hoc, and require even more mathematical sophistication. But, we don’t want a general solution, we want one that will work under the conditions we assume the characters will be scanned: the input will be grayscale bitmaps, with high contrast, and there will be no gaps in the characters that the algorithm will need to bridge.
Considered from this light, we can find the edges and contours in one fell-swoop, if we make the reasonable assumption that all edges occur at a given level of gray; anything above this threshold value is within the character, and anything below it is outside of the character. Essentially, the question of edge finding is reduced to determing transition points around this threshold. Here is the basic algorithm for identifying the contours:
1. Locate an adjacent pair of pixels, where one has a value above, and one below, this threshold value. Mark the location of these pixels in a ‘visited matrix’
2. Use the inverse function G’ to determine where between the two pixels the edge lies.
3. Proceed in a clockwise fashion along the edge, using a pair of pixels with high contrast adjacent to, and possibly sharing one pixel with the current pair. Mark this pair in the visited matrix.
4. When you return to pixels already visited, the contour has been closed.
5. Repeat this process until all pair of high contrast pixels have been visited, ensuring all contours have been located
Curve-fitting
The first step in the process of fitting curves to each contour is to generate a polygonal frame for the contour. Basically, a tolerance is chosen for the fitting, and a line is extended from the current point to the last such subsequent point such that the distance from the line to the true edge is less than the tolerance. This eliminates unnecessary points from the fitting process, and makes it easier to fit the character with less curves.
Fitting the actual curves is done in an analogous process: depending on the type of curve being fitted, a cost function and a tolerance are chosen (e.g., in the case of the quadratic curves, a squared error cost function is chosen so least-error optimization can be used). Each curve is fitted to as many lines as it can without exceeding the threshold.
Later
As is, the algorithm described doesn’t account for sharp corners, but later I will describe the method used for determining the presence of corners, then recap the entire algorithm. When I have finished writing a program illustrating the algorithm, I will post it.
Possibly relevant posts: