Image Deskew Tool

A page goes onto the glass a hair off square, the lid comes down, and the file that comes out leans. A person reads it without noticing. Software notices, because software reads in rows.

The repair is usually spoken of as one step, deskewing, and offered as one slider in an image editor. It is really two jobs with very different characters. The first is measurement: how far has this page turned, and which way? That question has a clean answer, and arithmetic no harder than addition will find it. The second job is rotation, and rotation is not free. Every pixel of the corrected picture has to be made up from its neighbors, the picture stops fitting its own frame, and somebody must decide what happens in the corners. So the argument here is short. Measure always. Rotate once. Better still, square the page at the glass.

Why a page leans, and why it matters

The federal guidelines for digitizing cultural heritage materials, edited at the Library of Congress with the National Archives, separate two faults that everyday speech runs together. Rotation keeps opposite sides parallel and every corner at 90 degrees, and it is introduced at capture by improper alignment of the content. Skew, in their vocabulary, is the fault in which the corners stop being right angles, usually because camera and platen were not parallel.

Scanner and OCR software uses the word skew for the first fault, the plain turn. This essay follows that habit, with one warning: the second fault cannot be cured by turning anything.

The turn matters most to machines that read. The documentation for the Tesseract OCR engine says the quality of its line segmentation drops significantly when a page is too skewed, which severely affects the recognition, and its advice is to rotate the image until the text lines are horizontal. The Library of Congress puts a number on it in the rules for its newspaper digitization program: images whose text blocks show more than 3 degrees of skew should be deskewed, because greater skew leads to less accurate OCR. The same rules want the correction made before recognition, since every recognized word carries coordinates that must match the delivered image.

Scanner software treats the fix as routine. Windows defines a driver property whose whole purpose is to say whether a device should use automatic skew correction, and the federal guidelines note that automated deskew functions are common in scanning and OCR applications.

Finding the tilt from the lines

Printed text is stripes. Each line of type is a dark band and each gap between lines a pale one. Count the dark pixels along every row of a straight page and the counts swing between high and low like the teeth of a comb. Tilt the page, and each row cuts through several lines and several gaps at once, so the counts blur toward an average. That is the whole idea. Try an angle, add up the ink along lines at that angle, and ask how sharply the sums change from one line to the next. The angle that gives the sharpest comb is the angle of the text.

Wolfgang Postl of Siemens set this down in a United States patent filed in 1985 and granted in 1988. His circuit summed the scan values along oblique lines and, for each candidate direction, added up the squares of the differences between one sum and the next. The patent has long since expired. The open source Leptonica library scores pages the same way, and the comments in its source code explain why the differences serve better than the sums themselves.

The differential signal, those comments say, rejects the background that comes from the sheer number of black pixels, and takes its largest contributions from the baselines and x-height lines of the type. It works on pages with several columns whose lines do not match across the gutter. It needs surprisingly little material: a couple of text lines will do. Its accuracy is set by geometry, at an angle in radians of roughly one over the width of the image in pixels.

The search runs in stages to save work. Leptonica sweeps coarsely over a reduced copy of the page to find the peak within half a degree or so, then halves the interval at higher resolution until the answer is good to a twentieth of a degree or better. The tool on this page makes three passes, at steps of 0.25, 0.05 and 0.01 degree, across 20 degrees either side of level.

Before any of that, the picture has to be divided into ink and paper. The usual instrument is Otsu’s method, which chooses the gray level that maximizes the variance between the two classes of pixels it separates. Tesseract uses it internally and warns that the result can be poor when the background of a page is unevenly dark, which describes most pages photographed under a desk lamp.

A score always comes out. A blank sheet has a best angle. So does a photograph of clouds. What matters is whether the best angle stands well clear of the rest.

Leptonica answers with a confidence, the ratio of its highest score to its lowest, and returns the page untouched when that ratio is under 3 or the angle is under a tenth of a degree. ImageMagick asks for a threshold with its deskew option and suggests that 40 percent works for most images. The tool here compares the best score with the best one at least two degrees away. When the winner is not clearly ahead it reports low confidence and leaves the picture alone. A picture with one strong straight edge, a horizon or a rooftop, can still fool a method of this kind.

Nor can the lines say which way is up. An upside-down page scores exactly like an upright one, and a page fed sideways offers the profile columns of type where it expects rows. The OCRmyPDF documentation draws the boundary neatly: a page that is “just a little off horizontal” calls for its deskew option, while its rotate-pages option “is for when the cardinal angle is wrong,” and that one leans on an OCR engine to judge orientation. Hence the quarter-turn buttons in the tool, which leave that decision to someone who can read.

What turning costs

A quarter turn costs nothing. ImageMagick’s guide files it with the operations that only rearrange pixels, losing no information, so the picture could be turned back unharmed. Any other angle is different in kind. The same guide explains the trouble for resizing, and it applies here unchanged: the picture is stored on one grid of pixels and must be fitted to another, the two grids do not match, and the image data has to be altered to fit. The usual result is a slight blurring. Doing it again only makes it worse.

How the data is altered is a choice among three familiar filters. Pillow, the Python imaging library, describes them plainly. Nearest neighbor picks one input pixel and ignores all the others, which the GIMP manual says often results in aliasing, the stair-step effect. Bilinear interpolation works from a 2 by 2 neighborhood, and the same manual calls it a good compromise between speed and quality. Bicubic interpolation weighs a 4 by 4 neighborhood and takes longer. Robert Keys gave that cubic method its full derivation in 1981 and showed that one setting of its free parameter makes the error shrink with the cube of the sample spacing.

Sharper filters carry a price of their own. A cubic kernel has negative lobes, so beside a hard edge it overshoots, drawing a faint halo that reads as extra crispness and can clip at pure black or white. The setting Keys favored overshoots less than the stronger ones some software uses. No setting brings the original pixels back.

That is the practical point. Work from the scan, apply the whole correction in one pass, and keep the original. The Library of Congress asks that its master images stay as close to the scanner’s output as possible, with no image processing at all except deskewing.

Crop it or pad it

A turned rectangle does not fit inside a rectangle of the same size. ImageMagick’s answer is to enlarge the result just enough to hold the whole rotated image, so that nothing is lost, and to paint the new corners with a background color. Pillow offers the same thing as an expand flag with a fill color, and scikit-image as a resize option that is off unless asked for. GIMP adds another choice, crop to result, which cuts inward until no empty corner is left.

The sample page in the tool makes the trade concrete. It is a page of 720 by 960 pixels that was tilted 3.2 degrees clockwise on a white bed, which makes a scan of 773 by 999. The tool measures the tilt at about 3.2 degrees with high confidence. Kept whole, the straightened picture grows to 828 by 1,041 pixels, and roughly a tenth of that area is fill. Cropped to the largest upright rectangle that holds no fill, it comes out at 720 by 960, exactly the page that went in. Keeping everything is right when the scan holds something worth having near its edges. Cropping is right when the edges were only ever scanner bed.

Margins are a separate decision. ImageMagick’s trim removes edges that match the color of the corner pixels, with a fuzz setting because a scanned background is never one exact color. Tesseract’s documentation wants dark scanner borders gone, since they can be picked up as extra characters, yet it also warns that text cropped with no border at all gives the engine trouble. The newspaper program crops to the edge of the page, not to the block of text.

One trap waits for anyone who types an angle. Pillow and scikit-image count degrees counter-clockwise. The browser canvas counts clockwise, and so does ImageMagick, whose guide admits this may seem illogical until you recall that image coordinates start at the top left. GIMP sidesteps the question with a corrective mode: line the tool up with the crooked thing and it applies the opposite turn. The tool on this page states its rule under the slider. A positive tilt means the page leans clockwise, and the picture is turned back by the same amount.

Better at the glass

All of this can be avoided where it starts. The federal guidelines trace rotation to how the content was aligned at capture and ask that master images be straight in relation to their contents. A sheet pushed against the corner guide needs no arithmetic afterward. Resolution helps the reading too: Tesseract’s documentation says the engine works best from at least 300 dpi, and the newspaper program sets its floor at the same figure.

When a page leans anyway, measure it, turn it once from the original with the gentlest filter that keeps the type crisp, and save the result beside the scan, not over it.