Cleaning up the scanned images

Having scanned the pages at 600 dpi, gray scale, and then converted them to pure black and white, we need to look at each image to see that it is good enough for printing.  Experience tells us that there will be stray black and white bits where they should not be.

So the first step is to try to clean up those little bits.  We have a program that looks for a single black bit in a field of white, or a single white bit in a field of black.  At 600 dpi, you cannot see something that small.  And once we have that, we can expand it to a small set of bits in a field of other bits.  The question becomes: At what point does a small set of bits become part of the image, instead of just extraneous bits?  My original thought was maybe 40 bits.  Any clump of 40 bits or less, surrounded by a field of the opposite color can be erased without changing the image.

But working on that premise, I noticed the following panel (page 9):

The nose on this person is:

So the right nostril is 10 pixels in a 5x3 rectangle.  The left nostril is less than 35 pixels.  And if either of them was "cleaned up" as random noise, it would change the image significantly.  So it would seem that Arriola's drawings are meaningful at a very small number of bits.

Of course that is in the actual drawings -- the strips.  Outside the strips, any stray bits would be safely considered extraneous, and can be cleaned up.  Which leads us to another approach.  If we identify the "background" white paper regions that are not part of the strips, then we can clean up larger spurious black bits.  Which leads us to write  a program to identify the background of the page.  This is simply starting at the upper left corner and "flooding" the page until we come to a barrier, a set of black bits that surround the comic strips themselves.  If we turn these background bits to green to make it easy to see what we are classifying as background we get pages like:

The smallest group of meaningful bits that are not background would be individual panels, or letters, or the page numbers.  But even a page number, like the "1" on this page, is 100x300 pixels.

The smallest meaning character would be a period, which would be 40x40 pixels.  But in the background areas, we could reasonably clean up anything under, say 15x15 pixels.

At the same time, we ran across several pages where the holes for the binding went through part of the drawing -- some 20 pages had problems with the holes.  We used a bit editor (GIMP) to go in and fix up those pages.  For example,  page 89 was scanned as:

but using the bit editor, by hand, we restored it to

Black and White Gordo

The Gordo books are black and white, except for the covers.  There is some text on the introductory pages, but once we get to the actual comic strips, they are all just black and white.  Or maybe shades of gray?  When we scanned the images, we told the scanner program "Gray", but what did we actually get?

First we convert from TIFF to GIF, since most of our software works on GIF images.  Both formats are loss-less so  we can easily convert from one to the other.  For GIF images, we have a 256 entry color table of (R,G,B) values and each pixel in the image is an index into this table.  So any given image has no more than 256 different colors.  Different images, of course, might have different color tables, in which case the total number of colors may exceed 256, but for one image we have only 256.  TIFF files can hold up to 24 bits of color data (8 bits for each of R, G, B) for each pixel.

But of course, if we actually have gray scale, then the value of R is the same as the value of G and the value of B for each pixel, since gray is the result of equal R, G, B values.  So even with 24 bits, we still only have 256 different levels of gray.

We have a program that will read a GIF file and produce a list of all the different colors in the file, and the number of times each color is used.  If we run that on all the GIF files for both books, we find there are only 256 different colors, in all the files for all the pages, and each of those colors is a gray level, with R = G = B. 

If we plot the number of occurrences of each color in a file, for example p135.gif, we get a plot like:

where we see a number of black pixels on the left of the plot, a very small number of gray pixels, followed by a whole bunch of white pixels at the right of the plot. The minimum number of a color is 11,339 (90,90,90) and the maximum is 21,667,543 for (255,255,255) (white).  This is out of a total of 33,660,000 which is an 8.5 x 11 inch image at 600 dpi (5100 x 6600 pixels).  So for this image 64% of the pixels are pure white.

The second largest number of pixels (2,194,373) are for (248,248,248).  I suggest that for our purposes, the difference between (248,248,248) and (255,255,255) is not meaningful -- a person can not tell the difference between these two colors.  Both are effectively "white".  Similarly the next two most common colors are (14,14,14) and (9,9,9), both of which are effectively "black".  

If we create a similar graph for all the pixels in all the pages, we have the following:

which again has a small cluster of black pixels at the left, and a very high cluster of white pixels at the right, with a vast sequence of gray colors in-between which are almost never used. There is that unusual spike just to the left of the white spike.  We believe that is in fact caused by the scanning of the rectangular holes for the GBC binding.  If we take just the blank pages, which have nothing other than the holes and random variation from a white surface, and plot the colors from that we get:

Thus, I think if we collapse all the colors above from around 150 to be 255 (mapping all those really light greys to white), we will both get rid of the scanning artifact of the GBC holes, and get a much brighter, whiter, background white color.

Similarly, if we map all the colors from about 100 down to be 0 (black), we will get a solid black for the images.  That leaves a small number of gray level colors (between 100 and 150 to be considered.

If we try this on a sample from p135.gif, we start with

 and converting the range 0 to 100 to black (0) and 150 to 255 to white (255), we get

Notice that the GBC holes are gone.  Otherwise, the only change I can see is that the lamp shade is somewhat lighter.

This still leaves gray colors from 102 to 145 (for this image).  Where are those gray colors?  If we zoom in further, and convert all those gray level colors to red,

we can see that these gray colors are in the transition from black to white (or white to black).  If we convert all these to white, it will "thin" the strokes that make up the image; converting them all to black will make them "thicker".

However, about half way between these two numbers is 128.  If we use 128 as the dividing line between black and white, we would get something like:

where green represents all the colors above 128, and red all the colors below 128. It looks roughly equal, so that should not make the strokes thicker or thinner.

Gordo Books

I found a website (https://gordocomics.com/) that had most of the comic strips for Gordo.  Gordo was a comic strip by Gustavo "Gus" Arriola from 1941 to 1985.  There were a number of printed compilations of the strip, including "Gordo's Critters", "Gordo's Cat", and "Accidental Ambassador Gordo: The Comic Strip Art of Gus Arriola".

The website mentions an unpublished collection "Gordo Redux".  

 

After corresponding with Jim Guida who put the website together, we thought we could use modern print-on-demand printing to get this unpublished collection into print, so he mailed me the proof that Arriola had put together.

When the package arrived, it had the proof for "Gordo Redux" but also another unpublished collection "Gordo Galore".

The proof books were 8.5 x 11 inch paper, bound with a plastic GBC binding spine.  The binding involves punching a series of rectangular holes along the edge of the paper and inserting a special piece of plastic to hold things together.

The first order of business was to remove the binder and then scan the pages.  The covers are in color, so they were scanned first and separately.  The pages themselve are printed on both sides.  We used our Canon Pixma TR7020a scanner driven by xsane on our Linux computer to do the scanning.  The Pixma has an automatic document feeder, which saved a lot of work.  We scanned them as "Gray" at 600 dots per inch (dpi) with an 8.5 by 11 inch paper in TIFF format.  We started with a file p000.tiff and increased the file name by +2 to scan the front (right hand side) of the pages, and then increased the file name by one, changed the increment to -2 and fed the pages back in to get the back (left hand side) of the pages.  That gives us files p000.tiff to p147.tiff for Redux and p000.tiff to p153.tiff for Galore.

As we were scanning the pages, we noticed a number of at least potential issues to be considered.

1. It looked like one page scanned at a slight angle (skew), so we will need to check the images for skew and if need be, rescan those pages by hand.

2. There were, of course, some completely blank pages.  These provide a clear representation showing that the rectangular holes for the GBC binding will need to be removed.  The image of the holes is faint, but clearly there.

On some of these otherwise blank pages, there seems to be some bleed thru of image from the page on the other side of the paper.

3. It appears that the proof copies we have were produced by a photocopying process.  Some of the pages, particularly for Galore seem to have horizontal stripes where the printing process fails in black areas.

4. It also seems that the back side (which would be the right hand pages) of the Galore printing is not as vibrant as the front sides.  The black is not as black and the white seems to have more of a touch of gray.  But at this point that is subjective, at best.

5. Also note that the GBC holes on this page got "close" to the actual image.  On some pages it appears to actually go thru the image.

6. There appears to be faint pencil writings on some pages.  This might be a date?

The scanning process went pretty well.  There was one instance where the ADF apparently fed two pages, instead of one, thru the scanner, and as a result one page was skipped.  That required me to stop the process, scan the missing page, move a bunch of files down two in the file naming scheme and restart the scanning.

The result is two large directories of TIFF files representing the two books at 600 dpi.  We can now start processing them to try to correct the known problems we listed above.  Once we have a full set of "clean" images, we can consider the problem of how to turn them into a PDF document.

My High School Literary Magazine

While going thru all of my old papers, I found a copy of my High School literary magazine.

While the title appears to be Greek, it's really a trans-language pun.  The first character, for example, is a Phi, which is pronounced like an F.  The next character, while it looks like a P is a Rho, pronounced like an R. And so on.  The theory is that if a person who knew Greek read it it would come out as "Fractured Fairytales".  

Why it is Volume II? I don't know.  Was there a Volume I, or was that another joke?

As I remember, we solicited stories from the students at the high school, selected a set of them, typed them up in typing class, and then had it printed, and bound, and sold as a fund raiser.  Printing probably meant photo-copying.  A couple of students did drawings to accompany some of the stories. 

 

We also had a set of ads.  We sold ads to local merchants to help pay the cost of publishing the magazine.

The idea is to bring this back into print, using print-on-demand.  So basically we want to create a PDF file of the magazine, using the same techniques as we used for the Oak Island book and the Petri Net book.

The main problem is the poor quality of the printed images.  Remember that the original image was from a typewriter.  Probably with a cloth ribbon.  So the characters are not very well defined.

We were able to get around this, in part by writing code that "knew" we were dealing with a fixed-width typewriter font, so we could predict where the character boxes would be, once we had started a line -- each character was about 50 x 80 pixels, aligned vertically and horizontally.

Or it would be if things were not skewed.  Several pages however had significant skew -- the lines were not parallel to the sides of the paper.  Specifically, pages 18, 62, 13, 47, 32, 38, 22, 67, 63, 37 all had significant skew.  So I wrote a program to try to detect the skew and correct for it.

We had run into this problem before on one of the books, and had a program that computed the left and right margins, which should be aligned and both parallel to each other and to the left and right edges of the paper.  But with this book, since it was written with a typewriter, the right margins are not aligned, so that didn't work. Even the left margins are not really aligned.  An "m" character and an "i" character are centered in their box, rather than being aligned to the left margin, so even the left margin varies too much to be used to find skew.

We tried to divide each line into 5 parts, computing the average base line position of the characters in the first fifth and the last fifth.  For a proper line, there would be no difference; for a skewed line, one end would be higher (or lower) than the other.  But this approach is more difficult for lines with lots of characters that have descenders, (like g,j,p,q,y).

So the approach we ended up with was to pick a character which is a simple box with no descender, like an n or x, and find the first and last one on a line.  These should have the same vertical position.  If they are significantly offset, that defines the skew.  Compute the difference for each line, and average to get the skew for a page.  Once we have the skew, we can adjust the boxes up (or down) as defined by the skew, to put them all on the same base line.

Once the skew was corrected, and we could then define lines of characters, we could check the quality of the OCR.  To do that, we wrote a short shell script that would search our box files for a given character and then use the positioning information for that character to go extract the bits that had been identified and create a small image file of just those bits and a bit of its surrounding (for context).  For example, here is one of the files that were created when we looked for all capital K characters.

Apparently something has mislabeled the C as a K; we can then go correct the box file.  

We did this for every character, to make sure that the OCR work was correct.

We also extracted all the text words and ran those thru a spelling checker, finding another 69 OCR errors and a number of typos in the original printed book.

From our box files, listing where each character image is located, plus the actual scanned images, we can build a font to match our scanned characters, then use a font editor to clean up the font images making the size of all characters consistent. 

That allows us to recreate the typed text of the magazine almost exactly as it originally was.  Then we add in the images, and finally the ad pages.  

We use our box file representation of the book to create a PDF of the complete book, plus a cover and upload it to Kindle Direct Publishing.  From that we print a proof copy, and after correcting some minor problems, it is now online and available from Amazon.

Creating PDF for the Petri Net book

Much of the coding for creating the PDF representation of the Petri Net book was already done in the Oak Island project.  This was just a much larger version of the same problem -- more pages, more figures, more fonts, ...  But we were producing PDF pretty quickly and then resolving the problems that came up.

Many of the problems were simple and immediately obvious.  Running the pdfbuild program would create a PDF file.  Looking at the PDF file using the local Linux PDF viewer (evince) would show any problems.  Correct the code for that case, rerun it until it looked right.

Then I went to Amazon to create the book project, and upload the PDF file for the book.  Big file (1.18 gigabytes), but with compression it came down to only about 12 megabytes.

But after a long time, Amazon rejected the file.  But without really saying why.  A short note to the Amazon (actually "Kindle Direct Publishing") people and I got back a note that the file showed an error when opened with Acrobat Reader (a standard Adobe program for viewing PDF files on Windows and Mac computers).  Acrobat Reader said "Cannot extract the embedded font 'T3Font_33'.  Some characters may not display or print correctly."  But this did not show up on evince on my Linux computer.  But it was clear that Amazon would not take my file if it did not work with Acrobat Reader.

Googling the error message didn't help much, but did reveal the presence of a set of forums run by Adobe -- the Adobe Community.  I registered for that and searched to see if I could find suggestions of what was wrong with my files.  There were two people MikelKlink and Leonard_Rosenthol who gave good comments in the PDF Language and Specification Forum.  They helped with scaling my 600 dpi fonts to make the numbers smaller.  The PDF spec suggests units of 1/1000 of a point (1/72 inch), while my units are 1/600 inch (600 dpi).  The least common multiple of 1/72 and 1/600 is 1/1800 (25*72 = 3*600), so I could use those units instead of 1/1000.  They also pointed out that I was short one byte in my xref at the end of the file -- xref entries have to be exactly 20 bytes; despite having potentially either just a newline (NL) or both a carriage return and newline (CR/NL) for an end-of-line marker.

But that did not resolve the problem with the fonts.  I thought it might be a problem with the /Resource objects, but no one picked up on that.  Searching for other ways to "debug" a PDF file, I tried using Adobe Acrobat Pro, but it did not give useful error messages either.  Eventually I saw a reference to a "PDF repair tool" and found one at ILovePDF.com.  I could upload a sample chapter to their site and then download a "repaired" version.  The repaired version had no errors with Acrobat Reader, but appeared to be the same image as my file.

So then the problem came down to comparing the two files -- my buggy PDF and the repaired PDF file from ILovePDF.   I have a program that reads a PDF and then outputs a human-readable version of it, but the two files still had lots of differences.  Some minor (they always use "1 0 0 1 x y Tm" to move to position (x,y) while I use the shorter "x y Td") but the major problem is that they renumbered all the objects.  It appeared that they read the entire document into memory, build the object tree and then renumbered the objects starting at the root, and working down, breadth-first. So the root object for their file is object 1 and the first object in the file. My code numbers objects from the bottom of the tree, working up, so the root object is the last object in the file and the highest object number.

So the problem then became one of identifying the corresponding objects in the two files and comparing them, knowing that the important difference must be down in the fonts somewhere.

And after some time, I found a difference.

Some characters, particularly in small point sizes, are very small images -- the period, the single quote, the center dot, and so on.  A center dot for example, in a 7 point font is (in my font definition) just 7 bits by 7 bits.  Each row has to be rounded up to a multiple of 8 bits, so this becomes an 8 bit by 7 bit image. which is then 7 bytes of data.  But compressed data has at least a little bit of overhead, and while a couple of bytes of overhead does not matter when 100K of data is compressed to 7K (plus the couple of bytes of overhead), it does matter when you only have 7 bytes to start with.  The "compressed" version of the 7 bytes takes 12 bytes of data.  Plus you then have to add "/Filter /FlateDecode" to the description of the object, losing another 20 bytes or so.

So my code was checking to see if the output of compression was bigger than the input, and skipping the compression in that case.  But it was doing it wrong.  I was not interpreting the return codes from zlib  correctly, so that I was adding the /Filter /FlateDecode to the description of the font  character image, but not actually compressing the bits.  Somehow evince was handling that okay, but Acrobat Reader was not.

But fixing my compression code and using zlib properly solved that problem and got my PDF files accepted by Acrobat Reader (and evince).  Which then allowed me to upload the files to Amazon/Kindle and move the book along in the process of getting it available as a print-on-demand book.

Hough Transform

A search for how to recognize straight lines in an image leads me to the Hough Transform.  This is a technique to find straight lines in an image.  The idea is to transform the bits in the image space into a "feature space" which reveals the lines.

The idea is fairly straightforward.  For each point in the image, we assume that it is on a line.  What would the line be?  Well, every line thru the point (x,y) is described by the standard linear equation y = ax+b for a slope a and intercept b. If we range over all possible slopes (a), we can then solve for the intercept b: b= y-ax.  So if we step a from 0 (horizontal) line to infinity (vertical line), then we get a set of points (a,b) and can plot those in feature space.  If we do this for all the points, then for an actual line, with slope A and intercept B, there will be a bunch of points at (A,B) in the feature space.  Think of the feature space as an and accumulator array, which starts at all 0, and for each (a,b) corresponding to a point (x,y), we add 1 to that index in the accumulator array.  Then the largest value in the accumulator corresponds to the longest line in the image, and gives you the slope and intercept.

The main problem with this, of course, is the slope going to infinity, for a vertical line.  So the standard solution is to replace the description of a line as ax+b by a representation as r = x cos a + y sin a, for an angle a and radius r.  If we step thru the angles, a, from 90 degrees to -90 degrees, we can solve for r and get a point (a,r) where a is limited from -90 to 90, and r is limited from 0 to the longest distance in the image (which would be the square root of the sum of w squared and h squared for an image of size w by h.)  Again, we can use the accumulator array and look for the maximum to find the longest line.  Of course, it's not as easy to map the maximum point (A,R) in the feature space back to the actual line in the image space.  We solved that by finding the maximum, and then running over the image array a second time, computing (a,r) and marking the image whenever they equal (A,R).

 We coded that up, and applying it to Figure 3.34.

and, marking the line found in red

This looks pretty good, but notice the little red parts on the circles:

The algorithm finds a line, but it's the abstract line that goes from one end of the image to the other, not just the line segments that are in the image. But we can probably use other code to find the segments, and keep only the longest ones.

Also notice that the section on the circle (and the little black part on the line below it, shows that it isn't just a line (a one-dimensional mathematical concept), but a line with width.  The width is determined by the size of the accumulator array.  While we step thru the angles from -90 to +90, we can do that in steps of 1 degree, or 5 degrees, or 1/10th of a degree, defining a different size accumulator array.    If the accumulator array is too small, the line found is really wide.  Plus, it looks like there may be more than one line mapping into an accumulator cell.  So stepping by 2 degrees, recognizes a much wider area as being part of the "line":

Look at the amount of red on the top circle, or on the width of the cross lines.

If we increase the number of steps, increasing the size of the array, for example to 1/10 of a degree, we get a much smaller line being recognized.

This line is only 4 pixels wide.  Increasing the size of the array by another factor of 4 (steps of 0.025 degrees) reduces this to one pixel wide.  Of course it also runs much slower, because of the larger accumulator array, which must be set to zero and then searched for the largest value after the transform.

Plus, the line that is found is not centered, but seems to go from the right edge of the actual line at the top to the left edge at the bottom, which seems a bit strange.  I'm guessing it's something to do with the "angle" part of the description of the line.

And I don't really understand why we have to switch to the angle,distance representation of a line -- Wikipedia calls this the Hesse normal form.  I can see the difficulty of an infinite slope for a vertical line, but this is a computer program.  We can easily constrain our transformation to slopes between say 45 degrees and -45 degrees (a slope of 1 to -1).  That will find all "mostly horizontal" lines, then transpose the image and run it again.  Transposing the image will make a vertical line into a horizontal line.  We run the algorithm, and then transpose the results back.  So first we find all the "mostly horizontal lines", then all the "mostly vertical lines".  As long as this partitions the possible slopes we consider, we will get all the lines (since we cover all slopes this way).  No need for sines and cosines, and we get the lines in the form of a slope and intercept.

But the Hough transform has another advantage -- it can be used for circles.  For circle detection, we use the equation (i - a)² + (j - b)² = r² where (a,b) is the center of a circle of radius r, and (i,j) is a point on that circle.  We need accumulator cells for a 3-dimensional array, (a,b,r), in general.  If the radius is known, this is just another 2-dimensional accumulator array.  A limited sampling of our figures suggests all the circles are about 200 pixels in diameter.  Our experience with the linear Hough transform suggests that a larger array means that our diameter has to be more accurate, while a smaller array will compensate for variation in diameter, and noise in the scanning.

And after coding it up, it seems that is the case.  The Wikipedia article for the Circle Hough Transform makes it quite clear how to run the code (look down for "The algorithm" and "The voting" for "Find circle parameter with unknown radius"). In our case, since the diameters seem to be about 200 pixels, the radius is assumed to be about 100 pixels, so we run the loop for the radius from 80 to 120.  This ends up being a bit problematic for finding circles, since each point now takes 40 loops for the radius, and then 360 for the angle, so the time for computation increases substantially.  But for test purposes, we cut out just the circle part of a Figure, and use it to develop our code:

Our first run at recognizing the circle says it is a success, but the result, with the circle in red, looks to be the same as what we started with:

There is just the hint of a red section at the bottom, and enlarging the image, we see, at the pixel level,

The code found the circle, and from the position of the maximum in the array, we know it is a circle with radius 100 and center (158,119) which certainly looks right, but what we see is a circle 9 pixels thick, while the algorithm finds only a 1-pixel wide circle.

Further experimenting with the program and our code reveals a couple of things.  Notice how in the image above, while the red codes do define a circle, they are not continuous.  A circle with radius 100 would have a circumference of roughly 628 (2πr).  But our loop runs from 0 to 360 degrees, so we will notice only up to 360 of these points.  For the example above, that's roughly half the points (which looks roughly correct).  This suggests we can easily tell a circle from a non-circle -- a circle will have (roughly) 360 points in the accumulator array; significantly less than this means no circle.  A short set of tests suggests that 350 or more is a circle (Or we could increase or decrease the number of points around a circle that we test, which would directly impact performance.)

If we use 350 as a cut-off, notice that we are no longer looking for the maximum value, just one that is "high enough".  That means we can recognize multiple circles in one run.  So if we have 15 circles in an image, we will find 15 peaks above 350, each of which defines the center of one of the circles.  In fact, we find peaks both for the maximum radius (as above), but also for all the slightly smaller radii for the width of the circle line.  And also maximums for all the slightly off-center circles that use some inner bits and some outer bits of the circle line.  So a line with a width of n points creates at least n circles with the same center, and varying diameters, plus circles where the center varies by at most n in both x and y directions.  We will need code to consolidate all of these into one wide-line circle.

That turns out to work well, so we can use the Hough Transform for Circles to find all the circles, record them, remove them from the figures and be able to put them back in later.  Once the circles are gone, the lines are a bit easier, since (for Petri nets) the lines go from place (circle) to transition (perpendicular line) to place (circle).  So almost all our lines are now broken into much smaller pieces.

We did some simple pixel level clean-up of the images.  Things like saying any instance of bits that look like

can have the little "pimple" of a bit removed.  At 600 dpi, you really can't see that  individual bit; you just get a sort of a feeling that the line is not "crisp".

Then the program looked explicitly for horizontal lines.  Just horizontal lines.  It would check each bit to see if it might be part of a horizontal line, and if so, try to expand it, both left and right to see how long it could be.  And also up and down to get a "height" for the line.  It would allow a certain amount of "mess" -- the wrong color bit, but not too much.  Then the image was rotated 180 degrees, and the vertical lines were found.  These were all removed and replaced later.

This meant that the "background" image was just the arrow heads, and non-vertical/horizontal or non-straight lines.  Those I cleaned up by hand, put the circles and lines and text back on top of, and the figures were in pretty good shape.  The code helped, but it wasn't (isn't) perfect.  The figures aren't perfect either.  But they are "good enough".

The Figures for the Petri Net book

The Petri net book has a lot of Figures.  152 of them, at least.  Some of the Figures are really just tables, so they can be typeset like the rest of the book, but Petri nets are basically a graphical representation of information or computation flow, so it makes sense there would be a lot of Figures.

The Figures are mainly line drawings, lines and circles, with labels attached to the lines and circles.  The labels are text, and can be typeset like the text of the book.  We have a "line" type in our representation, but it's really only for either horizontal or vertical lines.  It uses the same "box" notation we have for the character boxes -- start and end of x and y coordinates, 4 numbers -- so it's really a black box, not a black line.  But if the box is very thin in one dimension or the other, it becomes a line (horizontal or vertical).

But the lines in the Figures are not horizontal or vertical, in general, and most of them actually have arrow heads on them, being directional lines.  And then there are the circles.

But we have "images" in our representation.  Normally an "image" is used to represent the Figures.  In the text, we leave a blank space for the Figure, and place the text above and below it.

However, we can also use the same approach to defining the Figures themselves.  So we have a two level structure.  First we have a set of files that represent the Figures.  These are used to produce GIF images of the Figures.  Then we have the set of files for the book, which include the images for the Figures.

For the representation of the Figures, we have two basic parts -- the text which are the labels and the actual drawing.  If we create a GIF file which is just the drawing part (the circles and arrows) with no text labels, and include it as an image that covers the entire "page" of the Figure, then we can then list the characters which are the text of the labels and they will be placed on top of the background line drawing.  So we can represent each Figure by a background image and a box file with the text.

As an example, consider page 132.  The box file for it contains both the text and the image:

...
c gif/p132.gif 1682 314 1698 361 l 8pt i
c gif/p132.gif 1697 318 1710 361 i 8pt i
c gif/p132.gif 1714 323 1732 361 t 8pt i
c gif/p132.gif 1730 328 1765 372 y 8pt i
n gif/p132.gif 371 313 1765 373 newline
i gif/p132.gif 1339 532 2066 1353 figures/gif/5_7.gif
n gif/p132.gif 1339 532 2066 1353 newline
c gif/p132.gif 914 1404 949 1451 F 8pt b
c gif/p132.gif 953 1404 970 1451 i 8pt b
c gif/p132.gif 975 1418 1003 1462 g 8pt b
c gif/p132.gif 1010 1418 1045 1451 u 8pt b
...

We have first the boxes that define where the characters go for the page heading (which is in 8 point italic), followed by the image, which takes up all the space from row 532 to row 1353, so it is (1353 - 532 + 1 =) 822 pixels tall.  Then after the Figure, we have it's caption, which starts with "Figu..." in 8pt bold.

This looks like:

where if you look at the full image, the various parts have boxes drawn around them to show where each box is.  One box around the trailing italic "y" and then a bigger box around the image, and another box for the bold capital "F", and so on.

The description of the Figure itself, is the same sort of thing, but consists in its entirety as

v 2
i gif/5_7.gif 0 0 727 821 back/5_7.gif
c gif/5_7.gif 6 76 40 119 p 8pt i
c gif/5_7.gif 54 91 64 126 1 6pt sub
c gif/5_7.gif 33 382 51 420 t 8pt i
c gif/5_7.gif 63 404 73 439 1 6pt sub
c gif/5_7.gif 678 382 696 420 t 8pt i
c gif/5_7.gif 705 404 724 439 2 6pt sub
c gif/5_7.gif 1 710 35 753 p 8pt i
c gif/5_7.gif 46 725 65 760 2 6pt sub

This is a version two file (v 2).  Then the backing image, which takes up the entire size of the Figure.  We computed above that the Figure should be 822 pixels tall, and the backing image goes from row 0 to row 821, 822 pixels.  Then it is overlaid with the various labels (p sub 1, t sub 1, t sub 2, p sub 2).


The backing image is just the part without the labels:

So now the problem comes down to cleaning up the line drawings.  These are scanned (at 600 dpi) just like the text, and just like the text, are not perfect.  If you look at it at a high enough level of magnification, you see the bits are:

It seems like it should be easy enough to write some code to clean up the various lines and circles and such and make them "better", less "fuzzy".

The problem is how to recognize the lines (and circles), so that we know what should be a straight edge, and where it starts and stops, and so on.  One option would be to just use a bit map editor and clean them up by hand -- that's what we did with the fonts -- but that seems like a lot of work.  It seems a program would be better -- it could run over all the figures and do them all the same.

Let's start with the lines -- how do we recognize a line from a set of pixels?  Horizontal or Vertical lines for a start, then straight lines at any angle, then maybe curved lines and arcs.  You would think that someone has already done this.