Socialist Standard digitization blog

OCR on GNU/Linux: A survey

noreply@blogger.com (Tristan Miller) — Sun, 16 Oct 2011 20:55:00 +0000

Today was spent checking out options for optical character recognition (OCR) on GNU/Linux. There are apparently the following basic engines for OCR:

Engine	Version	Licence
OpenOCR (Cuneiform)	1.0.0	BSD-style
GOCR	0.49	GPLv2
Ocrad	0.20	GPLv3
Tesseract	2.04	Apache 2.0
ABBYY OCR	9.0	proprietary
OCR Shop XTR	5.6	proprietary

In June of last year Andreas Gohr did a short experiment where he compared the first five above-listed GNU/Linux OCR engines and found that ABBYY OCR had the highest accuracy, with 100% for proportionally spaced serif and sans-serif text; Tesseract was the best-performing Free Software package, with accuracy in the 92–98% range. GOCR and Ocrad were significantly worse, with accuracy as low as 76% and 82%, respectively.

The non-proprietary engines usually just have bare-bones command-line interfaces with a very limited feature set. There are a number of higher-level tools, often with graphical interfaces and allowing more sophisticated pre- and post-processing of the data. These tools include the following:

Front end	Version	Licence	Back ends	Notes
easy-ocr	3.4	BSD-style	Cuneiform, GOCR, Ocrad, OCRopus, Tesseract	apparently available only as a Debian binary package
gImageReader	0.9	GPLv3	Tesseract	—
OCRFeeder	0.6.6	GPLv3	GOCR, Ocrad, Tesseract	—
ocrodjvu	0.7.5	GPLv2	Cuneiform, GOCR, Ocrad, OCRopus, Tesseract	—
OCRopus	0.4	Apache 2.0	Tesseract	—
pdfocr	0.1.2	BSD-style	Cuneiform	—
WatchOCR	0.8	GPL	Cuneiform	available only as a Debian binary package or Knoppix LiveCD

Since it's my intention to use Free Software wherever possible for this project, I installed Tesseract and a GPLv3-licensed graphical front end, gImageReader. (Rather than compiling from source, I used Malcolm Lewis's openSUSE RPMs. These RPMs fail to specify all the dependencies; they require the presence of the python-imaging and python-enchant packages.) I then tried processing a couple pages from the Standard as test runs: the front page of the September 1904 issue, and the third page of the July 1961 issue. The former is a relatively poor-quality scan, and the latter is quite clean and has a simple layout. You can see the results in the screenshots below: the text OCR'd from the 1904 issue is almost complete gibberish, whereas the text for the 1961 issue is mostly correct (though still with lots of mistakes).

gImageReader and the September 1904 Standard

gImageReader and the July 1961 Standard

Unfortunately, the gImageReader interface produces only plain text as its output, which is useless for my purposes. What I need is for there to be a mapping of selectable, searchable text to the position it appears at in the original scan. Apparently, there is an open standard, hOCR, for representing text layout, recognition confidence, style, and other OCR information. Tesseract, Cuneiform, and other OCR packages can output to hOCR. The problem is that the hOCR file doesn't itself contain the original scanned image; for this you need some extra software to produce (say) a PDF which combines the text information and the original image. Only then will you have a searchable PDF.

It turns out that only some of the engines and front ends support hOCR, and of the Free Software front ends, only two of them add text layers to PDFs: WatchOCR and pdfocr. The ocrodjvu wrapper produces DjVu files instead of PDFs. My next task will therefore be to install and test WatchOCR, pdfocr, and ocrodjvu. I may also try out some proprietary packages for purposes of comparison.

January 1968 and 1969

noreply@blogger.com (Tristan Miller) — Thu, 29 Sep 2011 19:06:00 +0000

I first reported in March 2010 that the microfiche scans provided by LSE are missing the cover pages for the January 1968 and 1969 issues. Before I left London I visited the Socialist Party of Great Britain headquarters and picked up a copy of the January 1969 issue. The archive had no more loose January 1968 issues, so I had to photocopy it from a bound volume. Unfortunately, this meant that the page was cropped along the binding edge, but it's better than no page at all.

I had also mentioned in March 2010 that the aspect ratio of the actual printed issues doesn't seem to correspond to that of the LSE scans. This is something I had forgotten about when I finally scanned these issues in yesterday, and it caused me no end of confusion when I saw the discrepancy between what I had scanned myself and what all the other scans looked like. Below are two images for comparison: the left shows my scan of the January 1969 issue cover, and the right is the same image stretched to fit the aspect ratio of the LSE scans.

Since all the other scans are distorted in this manner, I'm faced with the choice of similarly distorting my scans to match them, or else disproportionately scaling all the LSE scans to match the physical page size. Much as I would like my archive to be as faithful as possible a copy of the printed issues, I am going to have to go with the first option, at least for now. The LSE scans aren't at a high enough resolution to withstand too much image manipulation, and besides that altering them would necessitate another careful inspection of each page to ensure that there are no further unpaper anomalies.

jbig2enc seeks a new maintainer

noreply@blogger.com (Tristan Miller) — Wed, 28 Sep 2011 20:21:00 +0000

I just received the following message from Adam Langley, maintainer of jbig2enc:

I wrote jbig2enc many years ago and I'm aware that it's been very useful to some people, for which I'm glad. But I'm afraid that I simply don't have the time to maintain it any more. Please feel free to fork it in the usual open source style. If you think you have a sufficiently well maintained fork, let me know and I'll start directing people to it.

As someone who has found jbig2enc quite valuable, I just want to say thanks to Adam, and hope that someone reading this blog might decide to take over the good work he's been doing!

Upsampling results

noreply@blogger.com (Tristan Miller) — Sun, 25 Sep 2011 18:33:00 +0000

In June I thought I had completed cropping, but upon reviewing the covers I spotted a further three with problems. It's possible that some of the inner pages were likewise overlooked, though I'll leave that rather tedious inspection for later (or perhaps to eagle-eyed volunteers, if I can get any!)…

Also in June I indicated that I had used jbig2enc to produce three PDFs for each of the issues I have up to the end of 1969: one with no upsampling, one with 2× upsampling, and one with 4× upsampling. The size of the collections are as follows:

upsampling	size (MB)
none	427
2×	733
4×	1257

So even at the greatest upsampling the collection is still easily small enough to fit on a DVD-ROM. However, from browsing the PDF covers, it seems a lot of the 4× upsampled issues are missing text (similar to how unpaper sometimes omits text on pages with low contrast or a close black border). I figure this could be fixed by playing with jbig2enc's threshold settings, though that could take several hours or days of experimentation and careful checking of the output.

The PDFs with 2× upsampling seem to be of good quality—much better than the non-upsampled ones, and not obviously worse than the 4× upsampled ones. And none of the covers had any obviously missing text; I hope this holds for the inside pages as well. I think, then, that it will be best to go with 2× upsampling. You can see some comparisons below.

No upsampling

2× upsampling

4× upsampling

My next steps will therefore be as follows:

Locate and scan the missing covers of the January 1968 and January 1969 issues. I got photocopies of these pages before I left London; I hope they didn't get lost in the move to Darmstadt!
Start investigating OCR software so that the final collection can have full-text search.
Start investigating DjVu to compare it with the PDFs.

A series of unfortunate events

noreply@blogger.com (Tristan Miller) — Sun, 25 Sep 2011 10:03:00 +0000

This spring I accepted a new job in Darmstadt, with a starting date in July, so in late May I quit my old job in London, hoping to use the time (except for that spent moving) to finish the digitization of at least the 1904–1970 issues. Unfortunately, this plan was thwarted by a series of unfortunate events. June saw one legal, one medical, and one veterinary emergency, which together consumed all my available time. When I finally arrived in Darmstadt, it took nearly two months after signing up for Internet access before they came to install the cables. And to top it all off, shortly after we got wired, my laptop became irreparably damaged, so I had to procure a new computer on short notice and transfer all my data onto it.

The new computer is all set up, now, and the Internet is the fastest I've ever had. Here's a comparison of the specs of my old machine and the new one I'll be working with:

	sable (old machine)	ferret (new machine)
CPU	Intel Core2 Duo T8300 @ 2.4 GHz	AMD Athlon II X2 260 @ 3.2 GHz
RAM	4 GB DDR2	4 GB DDR3
Hard disk	250 GB SATA	500 GB SATA II
Display	39 cm TFT @ 1440×900 (WSXGA)	61 cm TFT @ 1920×1080 (1080p)
Graphics	Intel 965 GM	AMD Radeon HD3000
OS	openSUSE 11.3	openSUSE 11.4

So as you can see, the new machine is a modest improvement on the old one in every respect: it's got a faster CPU and faster memory, a larger and faster hard drive, a larger and higher-resolution display, a better graphics card (not that that matters much for the 2D imaging work this project is concerned with), and a newer operating system.

Because the machine's architecture is slightly different, and because it's a completely new install of the operating system, I'm going to have to recompile jbig2enc, Leptonica, and some various support utilities I've written myself. After that I can get back to work, so watch this space for updates in the hopefully very near future…

Cropping complete

noreply@blogger.com (Tristan Miller) — Sun, 05 Jun 2011 21:04:00 +0000

As reported in March 2010, the microfiche images omit the cover pages for the January 1968 and January 1969 issues. I attended the Socialist Party of Great Britain's head office yesterday and picked up a spare copy of the January 1969 issue. There were no extra January 1968 issues remaining, but the issue did appear in the bound volumes in the archive, so I took a photocopy. The binding obscures about a centimetre of the left edge of the page, but my copy is better than nothing, I guess. Now my only problem is getting these two pages digitized, as I no longer have access to a scanner. I'll either have to find someone with a scanner, or see if I can photograph the covers myself.

With most of the pages now in place, it's time to start thinking again about how to "bind" them into PDF or DjVu documents. Since it's been a year since I last experimented with this, I downloaded the latest version of jbig2enc and its dependency, Leptonica. I discovered that jbig2enc doesn't compile with Leptonica 1.68, but only because the parameters to the findFileFormat() function have changed. This function is referenced once, in jbig2.cc, where it's used to check something involving multi-page TIFFs. I don't use jbig2enc to process TIFFs so I just commented out these lines, and then jbig2enc compiled fine.

My computer is now whirring away, generating three PDFs for each of the issues that I have up to the end of 1969: one with no upsampling, one with 2× upsampling, and one with 4× upsampling. It will probably be busy doing this all night. Once it's done, I'll examine the results to see what looks the best and what the file sizes are like. Watch this space for further analysis of the results…

unpaper revisited

noreply@blogger.com (Tristan Miller) — Thu, 02 Jun 2011 13:20:00 +0000

The last few days have been spent reviewing and revising the results I obtained with unpaper in March of last year. After double-checking the image output, I found I had missed some cases where unpaper had failed to properly process the images. After applying the appropriate command-line options discussed previously, I was able to get unpaper to correctly process most of these; the rest I added to the list of images which unpaper cannot process. I also double-checked this list, which originally had 142 images; I found that many of them were able to be processed successfully with a little more command-line option experimentation.

In the end, there was a net increase of seven images to the list, so it now contains 149 images. These cases are almost exclusively pages with illustrations (usually cover pages). I will now have to do some preliminary tests to determine whether it would be more efficient to crop these images manually or use my autocrop tool.

PDF viewing woes: update

noreply@blogger.com (Tristan Miller) — Tue, 31 May 2011 10:47:00 +0000

In March 2010 I reported on a couple problems viewing PDFs. The first problem was that my file manager, Dolphin, was unable to generate previews of some PDFs due to an arbitrary limit on file sizes. The second problem was slow rendering of the PDFs in my viewer, Okular. I'm pleased to report that the first of these issues has been fixed, and the second is due to be fixed in the next stable release series of Poppler (the PDF rendering library used by Okular).

Final results with unpaper

noreply@blogger.com (Tristan Miller) — Wed, 31 Mar 2010 16:53:00 +0000

I've finished processing the LSE JPEGs with unpaper, at least for the time being. The vast majority of the images were successfully processed using the following command lines.

September 1904 to August 1918: unpaper --layout double --output-pages 2 --pre-wipe 0,2898,4263,3102 --sheet-size 3500,2700 in.pgm out%d.pgm
September 1918 to August 1932: unpaper --layout double --output-pages 2 --pre-wipe 0,2898,4263,3102 --sheet-size 3700,2600 in.pgm out%d.pgm
September 1932 to December 1950: unpaper --layout double --output-pages 2 --pre-wipe 0,2898,4263,3102 --sheet-size 4000,2660 in.pgm out%d.pgm
January 1951 to December 1969: unpaper --layout double --output-pages 2 --pre-wipe 0,2898,4263,3102 --sheet-size 3450,2700 in.pgm out%d.pgm

As you can see, the only difference in the command lines was the sheet size, which varied over the course of the Standard's print run. The --layout double and --output-pages 2 options simply specify that we are working with 2-up sheets that need to be split into two separate files, one for each page. The --pre-wipe option deletes the ex libris banner LSE inserted at the bottom of the image.

Overall, 5445 of the 6078 sheets (90%) were processed more or less correctly with these default settings. In some of these cases unpaper failed to properly deskew the page, and sometimes a small portion of the page header was cut off, but no significant amount of article text or graphics is missing. A further 491 images (8%) required some additional options to correct the following processing errors:

folded columns

Unpaper's grey filter seemed to get confused with certain multicolumn layouts, especially if the column layout wasn't identical on both pages of a sheet. It would end up deleting a column down the side or middle and then squeezing the two edges together, as if it had folded the page onto itself. About 5% of sheets were so affected. The problem was solved by using the --no-grayfilter option.

folded column

fixed with --no-grayfilter

missing text

About 4% of the sheets, mostly from 1921 and the 1960s, had blocks of text missing due to unpaper's grey filter misidentifying an area of a particularly dark scan. The issue was fixed by using --black-threshold to adjust the luminance value under which unpaper considers a pixel to be black.

missing text

fixed with --black-threshold

In a further five cases, the missing text was due to a hair or other anomalous dark line leading to the black border area; unpaper then considered the text block to be part of the border and deleted it. These cases were solved by adjusting --blackfilter-intensity.

missing text

fixed with --blackfilter-intensity

misaligned pages

Sometimes unpaper would split a sheet off centre, so that the rightmost edge of the left-hand page spilled over into the leftmost edge of the right-hand page. Using --pre-shift -100,0 solved this problem, which affected nearly 3% of the images.

misaligned page

fixed with --pre-shift

There were 142 images (just over 2%) which could not be easily fixed at all. Nearly all of these failures were due to unpaper's black filter erasing images with large dark patches, or images or headlines which lay too close to the edge of the page. I was unable to find any combination of options which would preserve the desired text and images while still erasing the black border around the page. I may write to the author of unpaper to see if he has any suggestions; if this proves fruitless then I will have to take a different approach to these images. Possibly I could use my own autocrop tool on them to eliminate the black border, and then pass the result to unpaper for deskewing, grey filtering, and noise filtering.

The following stacked bar chart shows the number of successfully and unsuccessfully processed JPEGs for each volume of issues from 1904 to 1969.

As can be seen, the number of failures increases significantly in the 1960s—this is due to the increased use of photographs, particularly on the cover pages. The 1970s issues used so many photographs that there were more failures than I cared to correct. Since I scanned those images from paper myself, I will use my own much better scans instead of trying to unpaper the microfiche photos.

First results with unpaper

noreply@blogger.com (Tristan Miller) — Sun, 28 Mar 2010 15:36:00 +0000

The last few days have been spent figuring out how to get unpaper to work. Unlike my autocrop tool, the sheet size needs to be specified, which makes it a bit trickier to use with the LSE scans (see my earlier post "Page and image size analysis"). It also handles only uncompressed PNM files, which for some strange reason the author thinks of as a feature rather than a shortcoming. So now my corpus has ballooned by another 74 GB. Good thing I bought that 1.5 TB drive.

Anyway, I've run unpaper on the September 1904 through August 1918 issues (whose pages are all 242 mm × 460 mm). Of the 836 uncropped JPEGs for these issues, unpaper seems to have processed 779 of them (93%) correctly with the following command line:

unpaper --overwrite --layout double --output-pages 2 --pre-wipe 0,2898,4263,3102 --sheet-size 3500,2700 in.pgm out%d.pgm

Of the remaining 57 JPEGs, all but 6 were correctly processed with some extra options to modify the behaviour of the black or grey filters. The remaining 6 images I will have to deskew and crop by hand, or just use my autocrop tool.

Finding out the correct unpaper options for the 57 anomalous JPEGs was somewhat tedious. I would run unpaper with various command-line options on the files, wait several seconds for it to process, launch an image viewer on the output files, and then if the output was not acceptable, I would have to quit the image viewer and start again with a different set of command-line options. It would have been much easier if I could have just kept the image viewer open and set it to automatically refresh the images whenever they changed on disk. Unfortunately, neither of the viewers I tried (Gwenview and Kuickshow) have a "watch file" option. Gwenview does have a manual "refresh" command, but it does not refresh thumbnails. I've therefore created and/or voted for these "watch file" and "refresh" feature requests on the KDE bug tracker:

In the meantime, does anyone know of a fast, lightweight image viewer for X11 which has a "watch file" feature? It should be able to view PNM and PNG files.

PDFs: JPEG vs PNG vs JBIG2

noreply@blogger.com (Tristan Miller) — Tue, 23 Mar 2010 13:45:00 +0000

The goal of today's exercise is to see how to make the smallest possible PDF from the scans I have. To this end, I experimented with the September 1954 issue, which is a good candidate because it is fairly long and contains both text and images. The following table and graph summarizes four approaches and the results.

process	PDF creation command	PDF size (KB)
join the JPEGs into a PDF with ImageMagick	`convert *.jpg JPEG.pdf`	43 777
convert the JPEGs to bilevel PNGs, then join them into a PDF with ImageMagick	`convert *.png PNG.pdf`	6 907
convert the JPEGs to bilevel JBIG2s, then join them into a PDF with jbig2enc	`jbig2 -b J -d -p -s *.jpg; pdf.py J > JBIG2.pdf`	947
upscale and convert the JPEGs to bilevel JBIG2s, then join them into a PDF with jbig2enc	`jbig2 -b J -d -p -s -2 *.jpg; pdf.py J > 2xJBIG2.pdf`	1 451

So the clear winner here is JBIG2. The 2× upscaled version is actually much easier to read than the unscaled JBIG2 or PNG images, which are sometimes too faint. If I were to use the 2× upscaled JBIG2 method to produce PDFs for all the 1904–1972 issues, the total would be about 450 MB in size, which would easily fit on a single CD-ROM.

However, I know that much better compression ratios can be achieved using DjVu—pages can typically be reduced to just a few kilobytes each. The problem is that creating DjVu documents is a bit more involved. I tried using pdf2djvu, but the DjVu files it created were even larger than the PDFs; clearly what I really need to do is to use the individual DjVuLibre tools to properly segment and compress the original cropped JPEGs. Fortunately there appear to be some guidance and scripts on Wikisource. The Wikisource guide also pointed me towards unpaper, which apparently does a better job of autocropping scans than my own tool, and also deskews the pages. So the next few days will probably be spent investigating these resources.

jbig2enc

noreply@blogger.com (Tristan Miller) — Mon, 22 Mar 2010 23:27:00 +0000

Today, on the recommendation of one of the readers of this blog, I decided to install jbig2enc to see how it might be useful for my digitization project. Unfortunately, it didn't seem to compile out of the box:

[psy@sable:~/src/agl-jbig2enc-edebc5a]$ make
g++ -c jbig2enc.cc -I../leptonlib-1.64/src -Wall -I/usr/include -L/usr/lib -O3 
g++ -c jbig2arith.cc -I../leptonlib-1.64/src -Wall -I/usr/include -L/usr/lib -O3 
g++ -c jbig2sym.cc -DUSE_EXT -I../leptonlib-1.64/src -Wall -I/usr/include -L/usr/lib -O3 
ar -rcv libjbig2enc.a jbig2enc.o jbig2arith.o jbig2sym.o
a - jbig2enc.o
a - jbig2arith.o
a - jbig2sym.o
g++ -o jbig2 jbig2.cc -L. -ljbig2enc ../leptonlib-1.64/src/liblept.a -I../leptonlib-1.64/src -Wall -I/usr/include -L/usr/lib -O3  -lpng -ljpeg -ltiff -lm
../leptonlib-1.64/src/liblept.a(gifio.o): In function `pixWriteStreamGif':
gifio.c:(.text+0x15c): undefined reference to `MakeMapObject'
gifio.c:(.text+0x21d): undefined reference to `EGifOpenFileHandle'
gifio.c:(.text+0x258): undefined reference to `EGifPutScreenDesc'
gifio.c:(.text+0x26f): undefined reference to `FreeMapObject'
gifio.c:(.text+0x277): undefined reference to `EGifCloseFile'
gifio.c:(.text+0x2b0): undefined reference to `FreeMapObject'
gifio.c:(.text+0x2df): undefined reference to `FreeMapObject'
gifio.c:(.text+0x2ff): undefined reference to `EGifPutImageDesc'
gifio.c:(.text+0x31a): undefined reference to `EGifCloseFile'
gifio.c:(.text+0x502): undefined reference to `EGifPutLine'
gifio.c:(.text+0x537): undefined reference to `EGifPutComment'
gifio.c:(.text+0x569): undefined reference to `EGifCloseFile'
gifio.c:(.text+0x582): undefined reference to `FreeMapObject'
gifio.c:(.text+0x5e0): undefined reference to `EGifCloseFile'
gifio.c:(.text+0x653): undefined reference to `EGifCloseFile'
gifio.c:(.text+0x682): undefined reference to `EGifCloseFile'
../leptonlib-1.64/src/liblept.a(gifio.o): In function `pixReadStreamGif':
gifio.c:(.text+0x6ce): undefined reference to `DGifOpenFileHandle'
gifio.c:(.text+0x6e6): undefined reference to `DGifSlurp'
gifio.c:(.text+0x878): undefined reference to `DGifCloseFile'
gifio.c:(.text+0x884): undefined reference to `DGifCloseFile'
gifio.c:(.text+0x9bc): undefined reference to `DGifCloseFile'
gifio.c:(.text+0xa2c): undefined reference to `DGifCloseFile'
gifio.c:(.text+0xa55): undefined reference to `DGifCloseFile'
../leptonlib-1.64/src/liblept.a(gifio.o):gifio.c:(.text+0xa86): more undefined references to `DGifCloseFile' follow
collect2: ld returned 1 exit status
make: *** [jbig2] Error 1
[psy@sable:~/src/agl-jbig2enc-edebc5a]$

It seems there were a few things wrong with the Makefile. The showstopper was that Leptonica, the library upon which jbig2enc depends, is expecting to link to giflib, but the Makefile doesn't specify this library. This was solved by adding -lgif to the command which compiles jbig2. The other problems were not fatal but somewhat irritating:

it is assumed that Leptonica isn't installed in a standard location;
there are no install and uninstall targets for (un)installing the package;
the program is written in C++, but the compiler is invoked with a redefined $(CC) rather than the standard $(CXX);
ar is invoked directly rather than through the standard $(AR); and
the clean target uses wildcards somewhat dangerously.

So here's an updated Makefile for jbig2enc 0.27. It should work with little or no modification on most *nix systems. On 64-bit systems which use lib64 directories, the libdir variable should be changed appropriately, or else it should be overriden on the command line.

# Improved Makefile for jbig2enc by Tristan Miller, 2010-03-22

prefix=/usr/local
exec_prefix=$(prefix)
bindir=$(exec_prefix)/bin
libdir=$(exec_prefix)/lib
CFLAGS=-I/usr/local/include/liblept -I/usr/include/liblept -Wall -O3 ${EXTRA}

jbig2: libjbig2enc.a jbig2.cc
 $(CXX) -o jbig2 jbig2.cc -L. -ljbig2enc $(CFLAGS) -lpng -ljpeg -ltiff -lm -llept -lgif

libjbig2enc.a: jbig2enc.o jbig2arith.o jbig2sym.o
 $(AR) -rcv libjbig2enc.a jbig2enc.o jbig2arith.o jbig2sym.o

jbig2enc.o: jbig2enc.cc jbig2arith.h jbig2sym.h jbig2structs.h jbig2segments.h
 $(CXX) -c jbig2enc.cc $(CFLAGS)

jbig2arith.o: jbig2arith.cc jbig2arith.h
 $(CXX) -c jbig2arith.cc $(CFLAGS)

jbig2sym.o: jbig2sym.cc jbig2arith.h
 $(CXX) -c jbig2sym.cc -DUSE_EXT $(CFLAGS)

clean:
 rm -f jbig2enc.o jbig2arith.o jbig2sym.o jbig2 libjbig2enc.a

install:
 install -s jbig2 $(bindir)
 install pdf.py $(bindir)
 install -s libjbig2enc.a $(libdir)

uninstall:
 rm $(bindir)/jbig2
 rm $(bindir)/pdf.py
 rm $(libdir)/libjbig2enc.a

Manual cropping

noreply@blogger.com (Tristan Miller) — Sun, 21 Mar 2010 18:10:00 +0000

This afternoon I used GIMP to find cropping coordinates for the 18 pages my autocrop program didn't successfully process. Having passed these to jpegtran, I'm now in possession of 13 020 properly cropped JPEG images, of which 11 164 are unique pages of the Socialist Standard (and the 1967 supplement) and the remaining 1856 are blank pages, microfiche title slides, indices, or duplicates.

Having cropped the images and discarded the irrelevant pages has brought the size of the corpus down from 17.58 GB to 15.13 GB, a savings of 13.94%. Of course, if LSE had properly scanned them as high-resolution bilevel images rather than JPEGs in the first place, the size would have been about a third of this. I am wondering if there is some way to convert the JPEGs to bilevel images, but given the relatively poor quality of the photographs and low resolution of the scans, this may not be possible. I'll have a go at batch-converting them with ImageMagick and examine the results, but I am not optimistic that they will be acceptable.

At any rate, the next step will be to assemble the individual pages into PDFs or DjVus, one issue per file. I shall have to look around to see what software is available for this. The only one I'm aware of is the pdfpages package for pdfTeX, though I'm sure there are others more suitable for my task.

Autocrop

noreply@blogger.com (Tristan Miller) — Sat, 20 Mar 2010 17:26:00 +0000

I have solved the problem of cropping the LSE images.

First, a quick recap: The microfiche scans of the Socialist Standard from the London School of Economics Library were provided as 6510 DCT images embedded into 69 PDF files. The images are unsuitable for use as-is for several reasons. First, each image depicts a spread of two physical pages—unless one has a particularly enormous, high-resolution monitor, it's not possible to read the text without doing a lot of tiresome scrolling. Second, the images are uncropped photographs of bound volumes of the Standard; they include a very thick and uneven black margin all around the page spread, which besides being ugly also reduces the resolution of the text when the images are displayed in a viewer at full width or height. Third, LSE has unhelpfully tacked a rather garish ex libris banner at the bottom of each page. You can see a scaled-down copy of one of these DCT images below.

My task, then, is to crop the DCT images in such a way as to remove the black border and banner, and then to cut the image down the middle to isolate the two physical pages. I was afraid that, since the width of the DCT image and the position of the page spread therein varies from image to image, I would have to do the cropping manually. Assuming it takes two minutes to crop an image manually, it would have taken about 217 hours to do the entire microfiche collection.

Fortunately, I was able to devise an image processing algorithm, realized in the libjpeg-based C program below, which suggests the cropping region automatically. It examines successive rows from the top of the image and calculates their average brightness; once it discovers a row with a brightness above a certain threshold, it has found the upper crop line. It finds the bottom crop line similarly, but this time working upwards from just before the LSE banner. The left and right crop lines are handled similary, except that the algorithm examines columns instead of rows, working inwards from the left and right edges. The cropping region is then passed to jpegtran for lossless cropping, as shown in the shell script which follows.

#include <stdio.h>
#include <stdlib.h>
#include <jpeglib.h>

#define THRESHOLD 15
#define MIN_X 65
#define MIN_Y 5
#define MAX_Y 2850

int main(int argc, char *argv[]) {

  struct jpeg_error_mgr jerr;
  struct jpeg_decompress_struct cinfo;
  FILE *infile;
  JSAMPARRAY buffer;
  int arg = 0;
  size_t row_stride;
  long x, y, top = 0 , bottom = 0, left = 0, right = 0;
  unsigned long v;

  /* Print usage information */
  if (argc <= 1) {
    fputs("Usage: autocrop file.jpg ...\n", stderr);
    return EXIT_FAILURE;
  }

  /* For each filename on the command line */
  while (++arg < argc) {

    /* Open the file */
    if ((infile = fopen(argv[arg], "rb")) == NULL) {
      fprintf(stderr, "can't open %s\n", argv[arg]);
      return EXIT_FAILURE;
    }

    /* Initialize JPEG decompression */
    cinfo.err = jpeg_std_error(&jerr);
    jpeg_create_decompress(&cinfo);
    jpeg_stdio_src(&cinfo, infile);
    (void) jpeg_read_header(&cinfo, TRUE);
    (void) jpeg_start_decompress(&cinfo);
    row_stride = cinfo.output_width * cinfo.output_components;

    /* Slurp JPEG into memory */
    buffer = (*cinfo.mem->alloc_sarray)
      ((j_common_ptr) &cinfo, JPOOL_IMAGE, row_stride, cinfo.output_height); 
    if (buffer == NULL) {
      fprintf(stderr, "autocrop: out of memory\n");
      return EXIT_FAILURE;
    }
    while (cinfo.output_scanline < cinfo.output_height)
      jpeg_read_scanlines(&cinfo, &buffer[cinfo.output_scanline], 
                          cinfo.output_height);

    /* Find top crop */
    for (y = MIN_Y; y <= MAX_Y; y++) {
      v = 0;
      for (x = MIN_X * cinfo.output_components; x < row_stride; x++)
        v += buffer[y][x];
      if (v / row_stride > THRESHOLD) {
        top = y;
        break;
      }
    }

    /* Find bottom crop */
    for (y = MAX_Y; y >= MIN_Y; y--) {
      v = 0;
      for (x = MIN_X * cinfo.output_components; x < row_stride; x++)
        v += buffer[y][x];
      if (v / row_stride > THRESHOLD) {
        bottom = y;
        break;
      }
    }

    /* Find left crop */
    for (x = MIN_X * cinfo.output_components; x < row_stride; x++) {
      v = 0;
      for (y = MIN_Y; y <= MAX_Y; y++)
        v += buffer[y][x];
      if (v / row_stride > THRESHOLD) {
        left = x / cinfo.output_components;
        break;
      }
    }

    /* Find right crop */
    for (x = row_stride - 1; x >= MIN_X * cinfo.output_components; x--) {
      v = 0;
      for (y = MIN_Y; y <= MAX_Y; y++)
        v += buffer[y][x];
      if (v / row_stride > THRESHOLD) {
        right = x / cinfo.output_components;
        break;
      }
    }

    /* Print the crop width, height, and upper left coordinates */
    printf("%s\t%ld\t%ld\t%ld\t%ld\n", argv[arg], 
           right - left, bottom - top, left, top);

    /* Clean up */
    (void) jpeg_finish_decompress(&cinfo);
    jpeg_destroy_decompress(&cinfo);
    fclose(infile);
  }

  return EXIT_SUCCESS;
}

for p in */*.jpg; do
    w=-1
    pbase=$(basename $p .jpg)
    pdir=$(dirname $p)
    if [ ! -e ../LSE_JPEG_cropped/$pdir/${pbase}a.jpg ]; then
        read filename w h x y < <(echo $(../bin/autocrop $p))
        echo jpegtran -grayscale -crop $((w / 2))x$h+$x+$y $p
        jpegtran -grayscale -crop $((w / 2))x$h+$x+$y $p \
            > ../LSE_JPEG_cropped/$pdir/${pbase}a.jpg
    fi
    if [ ! -e ../LSE_JPEG_cropped/$pdir/${pbase}b.jpg ]; then
        if [ $w -eq -1 ];then
            read filename w h x y < <(echo $(../bin/autocrop $p))
        fi
        echo jpegtran -grayscale -crop $((w / 2))x$h+$((x + w / 2))+$y $p
        jpegtran -grayscale -crop $((w / 2))x$h+$((x + w / 2))+$y $p \
            > ../LSE_JPEG_cropped/$pdir/${pbase}b.jpg
    fi
done

This process is remarkably effective for these images. Below you can see how it properly cropped the page spread shown above into two separate pages.

Out of the 11 168 Socialist Standard pages, the autocrop algorithm cropped only 18 of them incorrectly, giving an error rate of just 0.161%. Of these 18 failures, 7 were due to the page being overly skewed, 10 were due to a particularly dark cover image, and 1 was due to noise in the bottom margin. Below are a couple examples of improperly cropped images. As there are only 18 of them, I don't mind redoing these manually.

Page inventory

noreply@blogger.com (Tristan Miller) — Fri, 19 Mar 2010 20:17:00 +0000

I've completed an inventory of the pages in the 69 LSE PDFs. That is, for each page in the PDF (or more specifically, for each of the two logical pages on every physical page), I noted whether it was a microfiche title slide, a regular Socialist Standard page, a blank page, or something else. Creating such an inventory was necessary so that I can later split up the pages by issue; I need to know where each issue starts and ends within the PDF.

Below is a chart showing the 13 020 logical pages as they appear in sequence in each PDF. The pages have been colour-coded as follows: white, a blank page; grey, a microfiche title slide; green, a regular Socialist Standard page; red, a "special supplement" that appears to have been distributed with the August or September 1967 issue; and blue, the official Socialist Standard index which was included in some bound volumes.

As can be seen, the length of the Standard varies a great deal, sometimes even within a single month (often due to special anniversary issues, but sometimes for no apparent reason). Indices were included only from 1940–1952 and 1969–1971. Every PDF except for 1915 starts with a title page, and further title pages appear in the middle of the 1922, 1927, and 1933 volumes. The January issues for 1968, 1969, and 1971 are missing their covers; for the first two I will have to contact the Party to get a physical copy to scan myself. Finally, the December 1966 issue appears twice.

Page and image size analysis

noreply@blogger.com (Tristan Miller) — Wed, 17 Mar 2010 15:28:00 +0000

I have just discovered two anomalies regarding the page and image sizes; it remains to be seen how they will affect the cropping task.

The Socialist Standard has used at least five different page sizes throughout its print run. However, as shown in the table below, the page dimension ratios don't seem to correspond with those of the scanned versions in the LSE PDFs.

period	physical page		scanned page		apparent DPI
period	dimensions (mm)	ratio	dimensions (px)	ratio	horizontal	vertical
1904-09 – 1918-08	242 × 460	0.526	1715 × 2670	0.642	180	147
1918-09 – 1932-08	180 × 239	0.753	1815 × 2555	0.710	256	272
1932-09 – 1950-12	208 × 276	0.754	1965 × 2625	0.749	240	242
1951-01 – 1969-12	212 × 270	0.785	1715 × 2625	0.653	205	247
1970-01 – 1972-12	210 × 297	0.707	1725 × 2825	0.611	209	242

I'm at a loss as to what might account for the discrepancy, especially since the scanned aspect ratio is sometimes greater and sometimes lesser than the original. Keeping in mind that the microfiche was produced from photographs of bound collections of the Socialist Standard, here are some possible causes:

The Standard's sheets may have been cropped to a different size for binding.
The Standard was reprinted on paper of a different size for binding.
Portions of the physical sheets were obscured during photography (for instance, to hold the book open and in place for the camera), resulting in a cropped photo.
The paper is much wider than it appears in the two-dimensional photographs due to the binding gutter.
The horizontal and vertical DPI settings used for scanning the microfiche were not equal.

Not only are the page ratios different, but the dimensions of the entire scans (including the margins around the book and the LSE banner at the bottom) vary inexplicably. The height is always 3102 pixels but, as can be seen in the graph below, the width varies from 3405 to 4263 pixels. There is no obvious reason for this.

To automatically extract the image dimensions, I wrote the following C program using libjpeg:

#include <stdio.h>
#include <stdlib.h>
#include <jpeglib.h>

int main(int argc, char *argv[]) {

  struct jpeg_error_mgr jerr;
  struct jpeg_decompress_struct cinfo;
  FILE *infile;
  int arg = 0, status = EXIT_SUCCESS;

  /* Print usage information */
  if (argc <= 1) {
    fputs("Usage: jpegdims file.jpg ...\n", stderr);
    return EXIT_FAILURE;
  }

  /* For each filename on the command line */
  while (++arg < argc) {

    /* Open the file */
    if ((infile = fopen(argv[arg], "rb")) == NULL) {
      fprintf(stderr, "jpegdims: can't open %s\n", argv[arg]);
      status = EXIT_FAILURE;
      continue;
    }

    /* Initialize JPEG decompression */
    cinfo.err = jpeg_std_error(&jerr);
    jpeg_create_decompress(&cinfo);
    jpeg_stdio_src(&cinfo, infile);
    (void) jpeg_read_header(&cinfo, TRUE);
    (void) jpeg_start_decompress(&cinfo);

    printf("%7lu\t%7u\t%s\n", cinfo.output_width, 
                              cinfo.output_height, argv[arg]);

    /* Clean up */
    jpeg_destroy_decompress(&cinfo);
    fclose(infile);
  }

  return status;
}

New hard drive

noreply@blogger.com (Tristan Miller) — Wed, 17 Mar 2010 12:33:00 +0000

My new 1.5 TB external hard drive arrived today! Considering I placed the order with standard 3–5 day shipping, I'm rather impressed that it was dispatched and delivered in less than two days. I'm currently in the process of moving my files over; it will be nice to be able to work now without constantly scrounging for free space.

LSE PDF cropping

noreply@blogger.com (Tristan Miller) — Mon, 15 Mar 2010 16:23:00 +0000

Using the pdfimages tool from Poppler, I've confirmed that all the LSE PDFs consist of full-page RGB DCT images. There are a couple problems with this:

This format is lossy and thus the quality of the images could suffer if I transform them.
The files are needlessly large, since they are stored in full colour even though the scans are only in shades of grey.

Now, it is possible to extract the images as JPEGs and crop them losslessly using jpegtran, but only when the upper left corner of the cropped region falls on an iMCU boundary. Fortunately, the images are scanned at a high enough resolution that increasing the dimensions of the region by a few extra pixels to ensure boundary alignment shouldn't be a problem. It's also possible to losslessly convert RGB JPEGs to greyscale, though the reduction in file size is negligible (for these images about 3.4%).

So the next order of business is to extract the images from all the LSE PDFs and crop them. It's possible that the exact coordinates for the cropped regions may vary across the images, depending on the paper size (which changed throughout the Standard's run) and the positioning of the paper when the issues were originally photographed for microfiche. I am hoping, though, that large runs of issues will use the same cropping coordinates, allowing me to do most of the work automatically rather than manually.

I used the following bash script extract all the DCT images from the LSE PDFs as JPEGs:

for year in {1904..1972}
do
  pdfimages -f 2 -j LSE_SocialistStandard_$year.pdf $year
done

I'll then have to examine the resulting JPEG files manually to determine the cropping region for the left- and right-hand pages. Once I have these, I can do batch greyscaling and cropping using the following script, where W and H are the pixel width and height of the region, respectively, and X+Y is the offset from the upper left corner of the original image:

for f in *
do
  jpegtran -grayscale -crop W1xH1+X1+Y1 $f >left-$f
  jpegtran -grayscale -crop W2xH2+X2+Y2 $f >right-$f
done

Given the amount of data I have, the above scripts can take about an hour to complete. They also create a large amount of data, and I've found I'm running out of disk space. I've therefore ordered a Samsung Story Station 1.5 TB USB 2.0 external hard drive.

PDF software inventory

noreply@blogger.com (Tristan Miller) — Mon, 15 Mar 2010 13:32:00 +0000

Here's an inventory of the PDF manipulation software I have at my disposal for the project. All of these packages are Free Software in the sense that the user has the freedom to run, study, modify, and redistribute the program.

Okular: PDF viewer (GUI)
GNU gv: PDF viewer (GUI)
pdftk: merges and splits PDFs, rotates pages, edits metadata (command-line; GUI via pdftk-qgui)
PDFjam: merges, rotates, and n-ups PDFs (command-line)
PdfMod: adds, reorders, rotates, and removes pages; exports images; edits metadata (GUI)
poppler-tools: lists fonts; extracts images; prints metadata; converts PDF to HTML, PPM, PostScript, or text (command-line)
QPDF: linearizes (web-optimizes) PDFs, various other low-level transformations (command-line)
pspdftool: rearranges, deletes, scales, flips, numbers, crops, rotates, n-ups pages (command-line)
pstoedit: scales, shifts, splits, rotates, and resizes pages; converts PDF to other vector formats (command-line)
Ghostscript: PDF language interpreter; can do pretty much everything, though not necessarily easily (command-line)

PDF viewing woes

noreply@blogger.com (Tristan Miller) — Mon, 15 Mar 2010 11:53:00 +0000

I've been running into problems with the programs I use to view the LSE PDFs. For one thing, these PDFs are an average of 261 MB in size, whereas my file manager, Dolphin, won't generate previews for files larger than 100 MB. This is a rather annoying and arbitrary upper limit, especially considering that it takes only a few milliseconds to generate thumbnails for 100 MB PDFs. I've accordingly filed a bug report asking that the limit be removed.

The other problem is that my usual PDF viewer, Okular, is phenomenally slow at rendering the pages of the LSE PDFs—it takes between 10 and 25 seconds per page. (By comparison, the proprietary Adobe Reader renders them almost instantly.) Okular, like many other Free Software document viewers, renders PDFs using the FreeDesktop project's Poppler library, and it is there that the problem lies. Most likely this is due to a known issue, Bug 13518. For now, then, I will be using GNU gv, which isn't based on Poppler and is able to render the LSE PDFs quickly.

The state of things

noreply@blogger.com (Tristan Miller) — Sun, 14 Mar 2010 23:59:00 +0000

My project to digitize the Standard began in 2005. On 25 and 26 December of that year, Norbert Sanden and I, who possessed all issues dating back to February 1970, manually scanned them on a pair of high-end Ricoh office MFPs in Kaiserslautern. To save scanning time, and to avoid destroying the originals, we scanned two-page spreads into multi-page black-and-white TIFFs, usually one issue per file. This means that in these scans, all the pages are in order, except for the front and back pages. Additionally, from about April 1986 onwards, the cover sheet (including the front and back cover) was printed in spot colour (black plus one or two coloured inks), so the covers for these issues were scanned separately as colour JPEGs. In total I have 2.3 GB in 1-bit 600 dpi TIFF files, and a further 2.6 GB in 300 dpi JPEGs.

The TIFF scans as shown in my file browser

The JPEG scans as shown in my file browser

I moved to London in January 2006 and, with access to the Party's archives, intended to continue manually scanning issues back to 1904. The Party informed me that the 1904 to 1972 issues of the Standard had been microfiched by a third party, and that it might be easier to arrange for scanning directly from the microfiche. I set about calling various libraries to see if I could obtain a copy of the microfiche, and various document archiving companies to inquire about microfiche scanning costs. The first library I called, that of the London School of Economics, informed me that they were actually in the process of scanning much of their microfilm and microfiche collections anyway, and offered to include the Standard in this project and provide the Party with a copy for a small fee (about £20). I agreed to this as this was far cheaper than arranging for the scanning through a company, and far less effort than manually scanning the printed issues. However, the scanning project at LSE proceeded very slowly, and the scans weren't made available to me until several years later—namely, a few weeks ago.

I just got around to looking at the LSE scans yesterday. They're on 6 DVD-ROMs, and comprise 18 GB in 69 PDF files, one for each year from 1904 to 1972. The PDFs consist of two-page spreads scanned at 200 dpi greyscale; unlike the images I scanned, the front and back covers are in the correct order. The scans have not been OCR'd, and I haven't yet determined how the PDFs encode the image data; possibly it is JPEG. Each file includes a title page identifying the year of the archive, and some also include the index published in bound volumes of the Standard. All pages also include a banner at the bottom with the text, "London School of Economics & Political Science 2007 / Socialist Standard xxxx", where xxxx is the year.

Sample pages from one of the LSE PDFs

Issues from 1998 onwards have been typeset digitally and are available as PDFs. I should be able to obtain these directly from the Party's Socialist Standard production team. The Party also has a basic electronic index for the Standard (probably including only title and author data, but possibly also subjects) which I hope to obtain later. The index wasn't professionally produced, so I doubt it will be of much use when it comes to looking for specific subjects. Since making a proper subject index would be a tremendous undertaking, I hope that OCR plus full text search will serve as a reasonable substitute for the time being.

The next step will be to determine how best to crop the LSE scans such that there is a single physical page per image and no LSE footer. This will be the subject of an upcoming post.

Goals

noreply@blogger.com (Tristan Miller) — Sun, 14 Mar 2010 16:31:00 +0000

The goal of this project is to produce a digital archive of the Socialist Standard which includes all issues from 1904 to the present, and which will be made available on DVD-ROM and online. The archive will include a user-friendly interface for finding and viewing the issues, and should be accessible with any modern computer.

In practice, this means that the issues will be provided in an accessible document archive format, such as PDF or DjVu. Older issues will need to be scanned and OCR'd. The interface will most likely take the form of a set of HTML pages viewed with a web browser, as this is the easiest way to ensure cross-platform compatibility. The index will list the issues by date and cover image. Ideally there will also be an index of article titles, authors, and subjects, and also a searchable full-text index.

Some of the goals, such as full-text searching, may not be achievable in the short term, so I plan to create various editions of the archive. The first edition may include just the non-OCR'd issues and a simple index; later editions can add other features as work on them is completed.

An introduction

noreply@blogger.com (Tristan Miller) — Sun, 14 Mar 2010 15:45:00 +0000

The Socialist Party of Great Britain has been publishing its journal, the Socialist Standard, without interruption since 1904. This blog documents my project to produce a complete digital archive of the Standard. By doing so I hope to help myself and others track my progress, and to provide insight for fellow would-be amateur archivists into the process and challenges of digitizing a large newspaper archive.