PDF explained (part 1): Overall Structure

I finally have my code generating PDF and wanted to take the opportunity while this is still fresh in my mind to write it down.  Maybe it will help someone else generate PDF directly.

To refresh, this is a project to re-publish an existing book from 1953.  The idea is to scan the book, at reasonably high resolution (600 dpi), and then extract from the scan the font that was used to print it, and then re-generate the book from that font.  Everything is raster or pixel based since it is all from the scan; there are no vector fonts or anything involved.

After the scan and processing, I have a data file that describes, in 600 dpi units, exactly where each character is to be put on each page.  The format is derived from the "box" format of the OCR program that I used (tesseract).  The book pages were scanned into separate files in a TIFF format, then coverted to GIF and OCR'ed to get the text and locations, then processed into a format like:

c p17.gif 629 1260 666 1295 n
c p17.gif 676 1234 713 1295 d
s p17.gif 714 1233 741 1234 space
c p17.gif 742 1236 767 1295 1 italic
c p17.gif 780 1236 816 1295 6 italic
s p17.gif 817 1235 844 1236 space
c p17.gif 845 1260 880 1312 p
c p17.gif 889 1260 925 1295 o
c p17.gif 931 1235 946 1295 i
n f02.gif 2174 2701 2174 2745 new-line
i f02.gif 409 3002 2402 3432 figures/f02b.gif

The first character on each line identifies the type of line.  The most common is the "c" or "character" line.  The first character is following by the name of the page that has the character, followed by a bounding box which contains the character -- start x, start y, end x, end y.  These are in 600 dpi units with the upper left corner of the page being 0,0.  Page sizes varied slightly, but most were 2800 x 3920 (which at 600 dpi would be 4.66 inch by 6.53 inch).  I think, actually this was after I added a 400 pixel margin on all four edges, so the actual non-blank text would be in a 2000 x 3120 pixel box.

After the page and bounding box, we have the actual character which is to be found there.  Mostly this is a single letter, representing the character but sometimes we have a "name" -- for example "odq" and "cdq" for open and closed double quotes, and "ff", "fi", "fl", "ffi", and "ffl" for ligatures.  There also may be font information -- point size and font face -- if need be.  The sizes are sort of arbitrary -- we don't know what the original font was -- but it says it was "set in 10-point Caslon Old Style", so the default is set as 10 points, and we defined new size for larger (12, 28) and smaller (6, 8) size characters.  And we can see that some characters are italic.  In theory, we could have bold or serif and sans-serif fonts, and other sizes.  But most of the text is just plain old 10-point regular font; out of 42,660 characters, 40254 were 10-point regular.

We wrote a program to read the original GIF files, and the list of bounding boxes and from that to generate little images of each of the characters used, separated by size and font face.  These were written out in BDF format as a font description.  For example, here is a generated BDF representation of a
6 point comma:

STARTCHAR ,
ENCODING 44
SWIDTH 138 166
DWIDTH 10 0
BBX 10 12 0 -5
BITMAP
1800
7E00
7F00
FF80
FF80
7FC0
7FC0
3FC0
0F80
0780
0780
0300
ENDCHAR

I could then use an old font editor I wrote to modify the characters slightly, to clean them up.  Once the fonts were cleaned up, I could use the same list of characters to generate a new output page with the cleaned-up idealized characters placed where they were supposed to be put.  The same file could be used to find the characters and then to replace the original characters by a new image.  All the uses of "T" in the book are now represented by an idealized version of a perfect "T" instead of slightly different versions of the same basic image.

I could compute on the box definitions, and adjust the positions slightly, to, for example, make the baseline of each line of text perfectly horizontal, and to smooth out the horizontal spacing between characters.  To do this, it helps to know where the lines of text are, and where the spaces between words are.  So two additional lines start not with "c" but with "s", for the spaces between words, and "n" for the new-lines at the end of a line of text.  For spaces, the bounding box is the size of the space between words (really only the horizontal positions are relevant), and for a new-line, the bounding box is the position just after the last character (only the horizontal position really matters).

Lines with "s" and "n" generate no output on the page, but are useful hints when we adjust character positions.  For example, we want (a) all characters to sit on a horizontal baseline, (b) the spaces between words in a line to be roughly the same size, and (c) the space between characters in a word to be roughly the same.  We thought about adding (d) the space between lines should be roughly the same and (e) the space between characters in a word should be roughly the same for all characters in all words in the same line, but decided that was probably too much.

One last type of line is the "i" line which defines an "image" to be put on the page.  An "i" line defines the bounding box on the page where the image should be, and the name of a image file (a GIF file for our work) to hold the image.  During the first phase of processing, the image is extracted from the page image and written to the file; during the second phase, we want to use the file image to create the image on the paper -- or at least in the image file that represents the piece of paper.

So we have a program which can read a file describing a page, plus a set of fonts, and will generate an image file with each character and image put in the right place.  Thus we can generate a new image of each scanned page where every character and image is "cleaned-up" and there are no extraneous bits of dust or marks on the page image.  This page image can then be printed, or whatever, as an image.  Although it is constructed of glyphs representing specific characters and copies of bit-map images, the output is just an image file -- a sequence of black and white dots (possibly grey scale or even color bits in the images) with no concept of why a particular bit is white or black.

We can then create a PDF file, using traditional programs like Word or LibreOffice, which is just a sequence of pages, each page being a full-page GIF image.  This was our first take at generating a PDF file of our newly re-formatted book.  But a PDF file has an ability to have fonts and then put characters from that font (and images) on a page of paper; that is what PDF is for.  So we should be able to translate directly from our representation into a PDF file without having to go to a full-page image.

PDF was defined by Adobe Systems as a follow-on to PostScript, but was then offered up as an open standard. It was picked up by ISO (International Organization for Standardization) and made into an open standard ISO 32000-1:2008 Document management — Portable document format.  The first thing I did was read that. That defines things, but really does not show how they are used, particularly not the parts that I figured I needed: a different unit of measurement (600 dpi), representing my own bit-mapped glyphs for fonts, and images.

I also read Developing with PDF by Leonard Rosenthol (O'Reilly Media) from our local City Library,  That helped on some points, particularly hinting at how to represent images in Chapter 3 but leaving out the critical details (like how to represent the actual image -- it just says "image data goes here"  even for small examples).  Much of the book seems to be just copied from the ISO standard (although he does at least correct his Example 4-7 which makes much more sense than the same Figure 46 in the ISO standard).

A more useful book was PDF Explained by John Whitington (O'Reilly Media) which I found on-line at http://issuu.com/wangzuo/docs/pdf_explained_2011-1 although the ability to read it was limited by having to go thru it one page at a time from the front.  Chapter 6 on Text and Fonts (pages 71 to 88) does not really say anything more than Rosenthol did; maybe it just seemed to make more sense because it was the second or third time I had read it.  But it did give me another reference to Fonts and Encodings by Yannis Haralambous (O'Reilly Media) which is a truly fascinating combination of theory and practice, but, while interesting, we are beginning to get a bit far afield.

It was pretty difficult, if not impossible, to find the information I wanted by just searching with Google, or at least it seemed that way to me.  If I mentioned that I wanted to know about PDF, I started to get PDF documents, not information about PDF.  So mostly, I muddled thru, trying this and that until I found the (apparent) key to generating my own PDF.   PDF is a strange mixture of general things (objects) and specific things that are apparently there to support someone's specific idea of how documents will be structured (and ours is not structured like that).

A PDF file is a collection of objects.  Each object is mainly a list of key/value pairs, with occasional data.  An object is defined by the keyword "obj"; the definition ends with the keyword "endobj".  For example:

548 0 obj % page object for cover.gif
<<
 /Type /Page
 /Parent 545 0 R
 /Resources 544 0 R
 /MediaBox [ 0 0 765.36 454.56 ]
 /Contents 546 0 R
>>
endobj

is the definition of an object (object 548) which has a number of properties given by the key/value pairs.  Some of the values are constants (like /Page), others are references to other objects (545 0 R, 544 0 R, and 546 0 R), and one is an array of numeric values (the /MediaBox).

The overall PDF file structure has a header, a body, a cross-reference table, and a trailer.

The file, in general, is all in ASCII, with the exception of some binary data streams (we will talk about that later).

The header is one line

%PDF-1.6

which defines the file as a PDF, and gives the version of the language that is used.  PDF files can be version 1.0, 1.1, ... 1.7.  Different features of the language have been introduced in different versions, and you need to specify the largest version for any features you use.  For example, we tried to use "UserUnit" which was introduced with PDF 1.6; Resources come from PDF 1.2.  I think these are all upward-compatible.

Notice that the "%" character is also the "comment" character for PDF -- everything after a "%" until the end of the line is a comment, and ignored.  So in some sense, this first line is a comment.

The Standard (and other sources) say that if the PDF has binary data, then by convention, the second line of a PDF file is a comment line with at least one binary character.  The idea is that if a program tries to determine if a file is ASCII or binary, it will look at a small number of it's initial characters.  If they are all just ASCII, it will assume the rest of the file is ASCII; if it sees any non-ASCII (binary) characters, it will assume the file is binary.  So this second line is for those file classification programs, not for PDF itself -- it's a comment started by a "%", so the line is ignored.  We decided to make the entire file ASCII, so we don't bother with this second line.

The trailer is used for two things:

1. To find the cross reference table, and
2. To find the "Root" object.

The cross reference table says, for each object, where in the file that object is, allowing direct access to a particular object.  The Root object is the one that defines the content of the PDF file.  The trailer defines what object it is, and then the cross reference table tells you where in the file it is.

The trailer uses the same syntactic structure as the rest of a PDF file: a list of key/value pairs:

trailer
  <<
      key-1  value-1
      key-2  value-2
           ...
      key-n  value-n
  >>
startxref
Byte_offset_of_cross-reference_table
%%EOF

We only need two keys in the trailer section:  the Root and the total number of objects (Size).

The "Byte_offset_of_cross-reference_table" is just what it says -- the byte offset, from the beginning of the file, of the start of the cross-reference table.  So if the entire PDF file is 3,382,705 bytes long, and the cross-reference table starts at byte 3,372,180  then the end of the PDF file is:

startxref
3372180
%%EOF

This allows a program that wants to read a PDF file to first read the tail end of it, back up over the "%%EOF" and the numeric digits before it to the "startxref" keyword and then compute where the cross reference table is in the PDF file.

The trailer itself always has at least two entries:

Size -- which is the number of objects in the file, and

Root -- which defines the root object.

So, for example, we could have a PDF file that ends with:

trailer
<<
 /Size 550
 /Root 549 0 R
>>
startxref
3372180
%%EOF

which says there are 550 objects altogether, and the Root object is number 549.

A couple of comments about syntax.  Blank spaces do not matter.  Numbers are represented as numbers, in decimal, in ASCII (with a possible plus or minus sign); numbers may have fractional parts (again in decimal). 

Boolean values can be true and false.  I'm not sure if case is important.

The "<<" and ">>" tokens define a "dictionary" object.  Dictionary objects are a list of key/value pairs.

Strings are surrounded by "(" and ")", so (foo) is a string consisting of the three characters "f", "o", and "o".  In a string, if you want a right parenthesis, you need to escape it with a back-slash (\). If you want a back-slash, you have to escape it with a back-slash (\\).  You can also represent some white-space characters using a back-slash, as you would expect from C: \n, \r, \t, ...  You can also represent any character in a string with \ooo, where ooo is a 3-digit octal ASCII character code.  So a right parenthesis is both \) and \051.

Hexadecimal strings are an arbrarity long sequence of hexadecimal digits (using either A-F or a-f or a mixture), surrounded by "<" and ">", so something like <4E6F20>.  I don't think we use any of these.

Arrays are delimited by "[" and "]", and are just a sequence of things, not necessarily all the same.

Symbols can be keywords, or constants (true and false, for example), or occasionally names.  To differentiate from a "thing" from a "name", names are prefixed with a slash, like /Size.

So the characters "<", ">","(", ")", "[", "]" have special value for hexadecimal strings, dictionaries, strings, and arrays.  Plus "%" starts a comment.  And "/" defines a name.  So if we need to use these characters, as characters and not as syntactic tokens, we need a way to quote them.  This is done by representing the character by a hash-sign "#" followed by the two digit hexadecimal ASCII code for that character.  So if you want a "%", you represent it as #23.  A right parenthesis is #29.

PDF then has these two different quoting mechanisms -- one for strings and a different one for names.


The object cross-reference table is a list of  n entries, where n is given by the /Size value in the trailer dictionary.  The cross-reference table begins with the keyword "xref".  This is then followed by the number of entries in the cross reference table (which should be exactly equal to the /Size in the trailer). This is given as a pair of number which is the range of object numbers.  This range is always from zero (0) to n (the number of the last object, which is the number of objects).  The zero object is reserved, so objects start at 1 and go up from there.

After "xref" and "0 n", we have a list of n lines each describing the location of one object in the PDF file.   Each line is exactly of the same format:

nnnnnnnnnn ggggg n

where nnnnnnnnnn is a 10-digit decimal byte offset to the i-th object and ggggg is the 5-digit generation number (always zero for us), and n is the literal character "n" (for "in-use").

The one exception to this is the first entry in the object table, which is for object 0, which is not used.  So it's entry in the cross-reference table is

0000000000 65535 f

The "f" means "free".

So a small PDF file, with 4 objects might have a cross reference table and trailer that looks like:

xref
0 4
0000000000 65535 f
0000000009 00000 n
0000000088 00000 n
0000000114 00000 n
0000000525 00000 n
trailer
<<
 /Size 4
 /Root 1 0 R
>>
startxref
680
%%EOF

Generation numbers have to do with being able to modify PDF files after they are written; in our work they will always be zero since we are not modifying existing PDF files, but writing new ones.

Notice how the /Root, in the example above is "1 0 R".  That is a reference to object 1 (generation 0).  This is called  an "indirect" object.  The idea is that, in general, when you are building an object and you need another object, you can either put it's value directly in place, or you can make an indirect reference to it.  (The /Root is always an indirect reference; some other things have to be indirect references.)  An indirect reference is an object number followed by a generation number (0 as we've said) followed by R.

Objects, as we showed earlier, are defined by the keyword "obj", and then a dictionary of key/value pairs, followed by "endobj". Almost all objects have a /Type, and the content of the object depends on its type. We will go over all of those that we care about, but here is a really simple case.

The content objects that define what goes on a page are of the form:

k 0 obj
<<
     /Length n
>>
stream
...
endstream
endobj

where the contents of the stream (between the keywords "stream" and "endstream" define what goes on the page.  The only key/value pair (for our purposes) is the /Length of the stream -- the number of bytes that it takes up.  My image of a PDF viewer is that it finds a content object, finds the /Length and the beginning of the stream and then reads and processes exactly /Length bytes and then expects to see the keyword "endstream".  So we need to know the length of the stream before we put it into the PDF file.

Our basic approach is to just generate the content stream as we read thru our character description input file, moving to the right spot on the page, outputting characters and images, until we are done with this page.  So we don't know, in advance, how long the content stream will be.  One option would be to run thru our code twice, once to compute the length, and then once to compute the output.  Another would be to buffer the content stream in memory (or a file) until it is complete, then compute the length, and copy the buffered contents into the PDF file.

Both of these are possible but tedious or error prone coding.  But indirect objects give us another possibility.  We generate the object header, but instead of giving a value to /Length, we give it an indirect reference to the next object:

546 0 obj
<<
/Length 547 0 R
>>
stream
...
endstream
endobj

As we generate the stream, we remember the byte offset in the file (ftell() will give us that) of the first byte of the stream, and then after we generate the last byte, before we write out the "endstream", we get the byte offset of the last byte of the stream, and compute the length.  Then we finish the definition of that object and add another one right after it which gives the length:

547 0 obj
15998
endobj

This increase the number of objects, but simplifies our programming.  Now when the PDF viewer looks at our file, and goes to object 546, it sees that the /Length of the stream is an indirect reference to object 547, goes to the cross-reference table to find where object 547 is (a simple indexing operation into the table), goes to that part of the PDF file, and gets the value (15,998), pops back up to object 546 with the correct /Length.

This Posting is getting long.  Let's stop at this point and we will cover the content of our objects in the next posting.

The physical size of the book

The original book was 5.125 x 6.3125.  (This is a width/height ratio = .81)  The inner margin was 1.18 (1 3/16) inch; the outer margin was .625  (5/8) inch.  The top margin was 5/8 inch also (.625) and the bottom margin was 3/8 inch (.375).  This leaves a text area with a line length of 3 5/16 inch and a height of 5 5/16 inch.

The closest "standard book size" is then 5.25 x 8.  Notice that since the width is about right, the height of the actual text is about the same as the original book (5.3125 inches of text, plus margins to make the 6.3125).  But we have an 8 inch page, so this leaves about 2 inches of unused vertical space.   I put this at the bottom -- I could put it at top and bottom equally, but, in my opinion, it's just too much unused space, no matter where it is.

The basic problem is that the shape of a 5.25/8.00 book is not the same as the shape of a 5.125/6.3125 book -- it's too long.  A 5.125/6.3125 book is .81/1 ratio, while a 5.25/8.00 book is .65/1.

Looking at standard book sizes (at least those that CreateSpace (Amazon's Print-on-Demand), the closest to a .81 ratio is a 7.5 x 9.25 book (also 8x10 or 8.5x11 but those are even larger).  This is 1.46 times the size of the original book -- so almost 50% larger.  But things fit nicely.

We have the same number of pages in both cases -- 52 pages.  It's just that in one case (book3.pdf) the page is smaller, the text is smaller, and there is 2 inches of blank space at the bottom  of the page, and with the other, the page is larger, the text is larger, and there is no extra space.  The smaller book is "closer" to the size of the original; the larger is the same shape as the original, everything is just larger.

Or we can try to make it a non-standard size.  It looks like the primary result of doing that is to limit where it can be sold: '"Enter my own size" trim sizes can be sold on Amazon.com and your eStore, but are ineligible for the bookstores and Online Retailers channel within Expanded Distribution.'

But there also is a comment that "Books with cream paper must be one of  the following trim sizes: 5" x 8", 5.25" x 8", 5.5" x 8.5", or 6" x 9" in order to enroll in Expanded Distribution.", so we may be limited already by the use of cream paper, so maybe the loss of "Expanded Distribution" is just going to happen, in which case we could just make our book the same size as the original.

So three options:

1. 5.25 x 8 book -- with two inches of blank space on each page.

2. 7 x 9 book -- same shape, but 46% larger than the original.

3. 5.125 x 6.3125 book -- original size, custom size. Limited distribution.

(but with "cream paper", we seem to have limited distribution anyway).

Problems with PDF

It will not be easy to generate PDF.  I am working for the ISO standard document defining PDF PDF 32000-1:2008.  But it is not at all clear how PDF works, or rather, how to make it work.

I have all the gross structure in place -- the objects, the object reference table, the document structure, the pages, and so on.  The problem comes down just to putting the characters where they are supposed to be.

The main problem is the units.  The space we are working with is 600 dots per inch, with the origin of the page in the upper left hand corner (positive x goes to the right, positive y goes down).   The space for PDF has the origin at the lower left hand corner (positive y goes up).  I can deal with that.  But defining the units of the numbers is not working.

PDF uses its default units as 1/72 of an inch.  So if we move to (100,100) that is 100/72 inches in each direction. So our 600 dpi resolution needs to be converted to put it in PDF 72 dpi resolution.  I could do that.  Actually PDF has a property UserUnit that appears to do this automatically.  UserUnit is defined as:

 A positive number that shall give the size of default user space units, in multiples of 1⁄72 inch. 

So I should be able to define my UserUnit as 72/600 (or 0.12) which is the multiple of 1/72 inch which is the size of my user space units.  But doing so has no effect.  I can add it to my PDF or not and the resulting PDF image is identical. I've even looked at the source code of code to read PDF files; the code recognizes this property, read the value in, stores the value in a variable, and never uses that variable at all.

This is compounded by several places where the size of the user unit seems to be arbitrarily changed.   For example, the TJ command allows characters to be put down, one after another, with possible adjustments between each character. After a character is placed, the position where the next character will be placed is automatically increased by the width of the last character.  So we put down an "A" and automatically move over the width of an "A", to be ready for the next character.

In our case, we have the position of each character in absolute terms, so we know that "A" goes at "416,2654", and the following "B" goes at "474,2654".  Since an "A" is 58 units wide, that works perfectly.  But later we have an "A" at "1853,882", and a following "d" at "1912,882".  After the "A", we will be at 1911, not 1912, so we need to move one more unit to the right.  The TJ command lets us do this, but the units for the "adjustment" to the position "shall be expressed in thousandths of a unit of text space".  So we don't move by "1", but by "1000"?  But this does not appear to work either.

Another approach to the units problem is to scale using the text matrix.  The text matrix defines how to scale (and translate) text.  I should be able to define the scaling as 72/600 to convert from 600 dpi to 72 dpi units.

The same problem comes up when defining Type 3 fonts.  With Type 3 fonts, we define a small graphic function for each character that defines what that character looks like.  The units for these functions are defined by the FontMatrix which defines the scaling between glyph space and the text space.  Since all our numbers are in units of 600 dpi, we don't need these two spaces to have different units, so we define the scaling to be 1, but this does not appear to work -- the resulting glyphs are much much too large.  The standard says: 

A common practice is to define glyphs in terms of a 1000-unit glyph coordinate system, in which case the font matrix is [ 0.001 0 0 0.001 0 0 ]. 

and we suspect that the 1000 multiple is there even tho I don't want it.  (I suspect the 1000 for the glyph coordinate system is related to the 1000 multiple in the TJ command.)

In theory, I should be able to code around these problems and just express my number in the standard 72 dpi units, particularly since I can use real numbers.  So my "1853,882" would be "1853*72/600,882*72/600" or "222.36,105.84" and then moving 1 pixel to the right between an "A" and a following "d" would be not 1 unit but 1*72/600*1000 = 120 units (and probably -120 since the standard says that this adjustment is subtracted from the current position).

But the PDF seems to be particularly screwy in terms of its commands.  For example, remember that our representation of a document gives the x,y position of each character.  Mostly, we can keep track of the position of the last character, and position the next one relative to it.  But in general, we may just need to move to a fixed location.  For example, the first character on the page, or a character at the beginning of a new paragraph, or after an in-line image.  PDF provides a Td operator that moves to an (x,y) position, but not an absolute (x,y) position.  Rather the (x,y) parameters are relative.  And not relative to the previous position, but "offset from the start of the current line".  What is the meaning of the "start of the current line"?  It appears that is the result of the last Td command, but that is not really clear, and does not seem to really work.

By applying "fudge" factors in various places, I can mostly get a document that comes close to what I want, but I have no explanation for these fudge factors, and the result is not close enough for actual publication.

It may be possible to work around these issues, but it will take time and experimentation.  Rather than delay publication trying to work these things out, it seems more expeditious to use my existing code to generate a 600 dpi GIF image and then use existing software to convert these into a PDF file where each page is simply an embedded image.  This should take more bits (larger file size), but it should produce exactly the result that I want.

Generating a PDF

Our current format for the book is a file that indicates where each character goes:

c p03.gif 1822 885 1832 923 l 8pt
c p03.gif 1839 900 1855 923 s 8pt
c p03.gif 1862 884 1886 898 cdq 8pt
n p03.gif 1888 882 1888 934 new-line
i p03.gif 400 1000 2399 1007 figures/line.gif
c p03.gif 407 1086 591 1274 O 28pt
c p03.gif 616 1106 650 1142 n
c p03.gif 658 1105 689 1142 e
s p03.gif 691 1108 726 1145 space
c p03.gif 729 1106 760 1142 a
c p03.gif 769 1106 803 1142 u

The first character (c,i,s,n) indicates what the line represents:

• c -- a character to be printed
• i -- an image
• s -- a space between two words
• n -- the end of a line

The next item is the page name -- the name of the file that represents a particular page of the book (each page is a separate file).  Then we have 4 numbers defining the bounding box of the item.  These numbers are locations on the page, in 600 dots-per-inch, first the x,y coordinates of the upper left corner of the box, and then the x,y coordinates of the lower right corner of the box.

The next item depends upon the type of line:

• For a character (c), it is the name of the character, possibly with the point size (6pt, 8pt, 10pt, 12pt, 28pt)  and/or font face (italic) of the character.  Most characters have a single character name, but some (like ff, fi, fl, ffi, ffl, cdq, odq) have names that are more than just one character.
• For an image (i), we have the name of the file which is the image to place in the bounding box.
• For a space (s), it is the word "space".
• For a new-line, it is the word "new-line".

We want a PDF file of this same information.

One approach, which we have used, is to create an HTML file which is just a list of each page in the document, in order, as a sequence of images.  We can then import this HTML file into a browser or word processor and ask that it be saved as a PDF file.

Another approach would be to generate a PDF file directly from this format.  A PDF file can do lots of things, but we only have 3 main things to represent:

1. Text
2. Fonts
3. Images 

Text  is represented as a sequence of strings, with location information:

BT
      /F13 12 Tf
      407 1086 Td
   (One) Tj
ET

The first line is "Begin Text"; the last line is "End Text".  The Tf command selects a font (font F13 in 12-point size).  The Td defines where to put the next character.  The Tj shows a string, in the example above "One".

We want to be able to define the position of each character.  Normally, PDF will show the first character ("O") and then space over the width of that character and output the next ("n"), space over the width of that character and output the next ("e").  If the font defines the width of the characters as being the same as what we want to do, this will work fine.  If not, we can output each character and then move, output the next character, and then move, and so on.  In fact, PDF has a TJ operator (instead of Tj), that takes, instead of a string like (One), an array of strings (generally one character strings) and integers, where we output the string, and then advance an extra amount to move:

    [ (O) 17 (n) 5 (e) ] TJ


With this in mind, we would define our font spacing as the minimum amount after any occurrence of a character, and then indicate the extra amount to move after that as necessary.  For example, if we look at the 10-point "O", the distance from the O to the next character varies from 65 to 68 pixels:

  6 occurrences of 65 pixels,
 28 occurrences of 66 pixels,
 22 occurrences of 67 pixels,
  6 occurrences of 68 pixels,


If we define the width of the O, in the font, as being 66 pixels, then we can adjust that by -1, +1, or +2 as necessary.  We can pick the width for the character that minimizes the number of times we need to adjust the width.

To match our input, it would be best if we define all numbers in the PDF file to be in units of 600 dpi.  By default, PDF uses 1/72 inch as the size of a unit, but we can define the "UserUnit" value to be what we want.  Presumably, the "units" for UserUnit is the default 1/72 (1.0 point), so we would define it to be 72/600 of those units (0.12 points).

Our input images are GIF images; we could convert those to other formats, but it appears that PDF does not support many image formats directly.  Rather it allows several different ways to represent images.  Some examples we have seen are in FlateDecode (zlib/decode).  It also looks like JBIG2 or LZWDecode are possibilities.  Wikipedia says that FlateDecode may be related to PNG or TIFF.

If we represent the text of the book as text, we need to also define the fonts that will be used to represent those characters on the page.  All of the print-on-demand services stress that the fonts need to be embedded in the PDF file.  We have our fonts in BDF format, and can read and understand that format.  PDF files can represent several different types of fonts, but basically they are either Type 1, Type 3, or TrueType.  Type 1 is an outline font format, as is TrueType.  Type 3 allows the glyphs of the font to be defined by PostScript programs.

I think we could translate our bitmap raster fonts into little PostScript programs by tracing the outlines of the outside and inside of each character and then filling the area between them. We could start at the origin of each character and define a path along the outside of the glyph.  In the PDF graphics language this would be something like:

  0 0 m
  0 36 l
  8 36 l
  8 0 l
  0 0 l
  0 52 m
  0 54 l
  2 54 l
  2 52 l
  0 52 l
  b*

to draw a simple low-res "i".  Units are, as always, in 600 dpi, relative to the origin of the i.  ("m" is a command to move, "l" draws a straight line from the previous position to a new position, and "b*" is a PDF graphics command to close the paths, and fill it with the background color (black, I assume).

PDF files represent the various parts of the document by "objects".  A font is an object; an image is an object; text is an object, and so on.  The overall PDF file format is a header, a body, a table of objects, and a trailer.  The file is meant to be read from the end, so the trailer indicates the number of objects and where in the file (byte offset) the start of the object table is.  The object table is a list of all the objects, consisting mainly of the byte-offset in the file of the start of that object.  The header is pretty minimal, consisting of bytes to identify it as a PDF file, and what version of PDF.  The body contains the definitions of the objects.

So to create a PDF file, we would first run thru our input file and create an internal list of all the objects we have -- the fonts, the images, and the text pages.  We could generate them in that order.  Then output the object table, and the trailer.


  

Lulu or Createspace

To generate a print-on-demand hard-copy of the book, we can use several services.  Lulu.com is the largest print-on-demand service, but Amazon provides its own as Createspace.com.  After trying to evaluate which of these would be best, it became apparent that we do not need to choose one or the other -- we can do both!

The basic file provided for print-on-demand is a PDF file.  PDF is a page-ready format used for documents.   PDF files can include text and images.  In our case, we can generate our text as images and so have a PDF file that simply contains the correct size and content of images.

An alternative would be to generate a PDF file directly from our representation of the book.  Our representation says where each character should be placed.  By combining that with the representation of each character in the font definition, we know what image to generate.  We can encode this information, in this way, to create a PDF file.  PDF files can have embedded fonts, images, and text.

Getting a Font to Print with

The last blog posting (How to process the scanned images to create a new book) took the scanned images and showed how they can be "merged" to create an ideal image which then replaces the individual characters to create an "ideal" representation of the original book.  This process takes many steps:

1. We first scanned the book, at high resolution (600 dpi) to get images of each page.
2. We applied OCR (Optical Character Recognition) to these pages to get the actual characters on the page.  In fact, we used tesseract, an open-source OCR program, to produce both the characters and where on the page they are.  The location on the page is given by a "bounding box" which says where it starts and where it ends, in both the horizontal and vertical dimensions.  The locations are given in pixels. (Each page is about 2000 x 3120 pixels.  At 600 dpi that is 3.3 x 5.2 inches, not the 6x9 expected).
3. Some editing and a lot of error checking then produces a file that lists both each character and where it is on the page. We added by hand information about the size and font-face where necessary. 

The result of this processing is a file which can be used to reproduce the book as it originally was:

c p17.gif 510 1234 538 1295 f
c p17.gif 536 1259 572 1295 o
c p17.gif 581 1259 615 1295 u
c p17.gif 627 1259 661 1295 n
c p17.gif 674 1235 710 1295 d
s p17.gif 711 1235 742 1293 space
c p17.gif 743 1235 768 1293 1 italic
c p17.gif 781 1237 817 1295 6 italic
s p17.gif 818 1259 844 1295 space
c p17.gif 845 1259 880 1312 p
c p17.gif 889 1259 925 1295 o
c p17.gif 932 1234 945 1295 i
c p17.gif 955 1259 989 1295 n

(We added the "space" character to represent the space between words.)

Generating a new version of the book then requires only a representation of each of the characters used in the book.  So we know that the "f" of the first line above goes horizontally from pixels 510 to 538 and vertically from pixels 1234 to 1295 on page "p17.gif" (so we know it is 29 pixels wide and 62 pixels high), but we still need to know exactly what bits form the "f".

The particular bits to represent an "f" is defined by the font.  Different fonts represent characters with different images -- they look different.  We can reproduce the book, from our file, in different fonts.  As long as an "f" is (no more than) 29x62 pixels, we can place it in the right spot on the (image) page to re-create the book.

So the problem is to find the "right" font.  The book itself says " This book was hand-set in 10 point Caslon Old Style".  A quick Google search on "Caslon" shows that William Caslon was a typeface designer in England from about 1730.  Unfortunately, there are a lot of "Caslon" fonts, and it is not clear what "Caslon Old Style" specifically is.

However, to some degree, we don't need a formal definition of the font -- we have it in front of us in the book.  Unfortunately, as we have seen in the previous posting, each instance of the characters, being a particular metal slug in 1953, printed on a particular piece of paper, and then scanned at 600 dpi, appears to be slightly different. Of the 42,272 different character instances we scanned, no more than a dozen are exactly the same as some other character instance.

So we have two options:

1. We can try to find an existing well-defined font that looks close to what we have in the current printed copy, or
2. We can try to make a representation of the font from the character images that we have.

We've tried both.  We can "merge" all the characters together, and from that have produced an approximate font.  But it clearly needs to be "cleaned" up by hand, to make straight lines of the same size.  This requires some skill and design capability.  The result of this is a set of font files that can be used to create a version of the book that approximates the printed version.  For example, the "The" used in the last blog post looks like:

We have also found something called LibreCaslonText which is an open-source representation that looks a lot like the original text.  (The representation of "Q" and "J" seem particularly to vary from font to font.) The main problem with this is that it is in "True Type" format, which is a vector representation of the font, rather than the bitmap format that we are using. One advantage for the True Type format is that it represents all sizes (point sizes) in one form, rather than having different bitmaps for the various sizes, as we have.  This looks like it will work for approach 1.  Converting the True Type format to a BDF format, we can then produce the following for the "The" of the last blog:

The differences are subtle.

How to process the scanned images to create a new book

We want to get the book back into publication.  Print-on-demand provides this capability.  So the problem is how to create the Print-on-demand input.

We have a scanned image of the original book.  We have both 300 dpi and 600 dpi scanned images, from Copy No. 23.  So one approach would be just to reprint these scanned images.  But these images are not very good.  We would like to clean them up first.

The first problem is that the pages are aging.  It appears that the paper that was used for the 1953 printing was not "acid-free", and so the paper is changing color and deteriorating.  The scans show a marked change in the paper to a brown, pink, salmon color.  If we use a black/white scan, instead of color, it's a dull grey over everything.

And then there are imperfections in the printed text itself.  For example, we have isolated the 5 occurrences of "The" on page 3 of the book, and we get:

Notice that the characters are all subtlety different.  This is a property of the inherent analog nature of the 1953 printing process.  Each instance of each character is slightly different.  Of course, some of this variation might also be the result of the scanning process.  We want to replace each of these different characters with one "ideal" image, a perfect "T" followed by a perfect "h" followed by a perfect "e".

But what is a perfect image? One approach would be to go back to 1953 and look at the definition of these characters then, but I can't do that.  What I can do is "merge" these 5 instances of these characters into one "average" character.  If we do that, we get:

We can then use a font editor to clean these up, and re-run the replacement of the characters with these newer clean copies to get:

Notice that this requires a certain amount of design skill.  Does the "e" in the cleaned-up version look too fat?  Or are the "T" and "h" too thin?

 There are other issues that need to be fixed too.  Some of the pages are scanned slightly off of horizontal, and we will want to re-level the lines, so that they are perfectly horizontal.