Wishlist: Compute more preicse angles to deskew

[AlMa1r]

While experimenting with pixFindSkewAndDeskew, I found out that only certain angles are returned. Here is an exemplary list of the angles that occur during deskewing 18 different scanned pages of mine (kept private):

 0.109375
 0.453125
 1.21875
-0.15625
 0.015625
-0.765625
-0.015625
-0.296875
-0.046875
-0.140625
-0.296875
 0.34375
-0.375
 0.140625
-0.40625
 0.546875
-0.765625
 0.328125

Notice that all are of the form integer · 0.000125. Remark that IEEE 754 allows for more precision in 32 bits.

This may or may not constitue a bug, but in any case we express a wishlist item: compute more precise angles to deskew.

[DanBloomberg]

From the documentation in skew.c, we state that we typically try to get the skew angle within 1/20 of a degree, which is about 0.001 radian. An image 1000 pixels wide will then be within 1 pixel of having no skew, so this is a reasonable goal.

The precision of the output angle as you note is nearly 10x higher, namely 0.000125 radians, about 0.007 degree. For an image 10000 pixels wide, this represents a skew angle of about 1 pixel, which is well beyond what is needed for these applications.

[AlMa1r]

I see “1/20 degree” only in the textual comments but not in the code. If you refer to DefaultMinbsDelta = 0.01f; /* degrees */ (= 1/100 degree), or the minbsdelta parameter of the function pixFindSkewSweepAndSearch, or 0.05 (= 1/20) in pixFindDifferentialSquareSum, they are all not adjustable by the caller of pixFindSkewAndDeskew. I have not gone deeply into the details of the particular binary search, but the binary search algorithms I know can get (with some care to avoid infinite looping) close enough to the most precise value representable in a given floating-point bitwidth. So there is no point in stopping very early, as the modern computers are fast.

I don't get your computation. To rotate an image around the center by 1 full pixel on the left or right margin, we should take the angle arctg((1 pixel)/((image width in pixels)/2)). Arcsin instead of arctg would do as well for such small angles. I don't know how precisely Leptonica does it, but the color of a pixel in the target image should be computed from the colors of the rotated pixels in the rotated image that overlap it. As, say, for gray PNG, it's possible to have 256 pixel values, it makes sense to distinguish the rotations by at most 1/256 of a pixel. For this, you need an angle of arctg((1 pixel)/256/((image width in pixels)/2)).

Every once in a while, we scan documents at 1200 dpi so that we can deskew them later and downscale after deskewing (as at resolutions 600 dpi and lower, certain details in the rotated image are sometimes visibly blurrier than in the original). At 1200 dpi, a full A4 page is ≈ 9921 pixels × 14031 pixels (swap the numbers for landscape); you do notice even small-angle rotations. For an image of width 14031 pixels, the aforementioned angle would be arctg(1/256/(14031/2)) = 0,000031902° < 0.000125°.

Even at 600 dpi, we sometimes notice that the deskewed text is not ideally straight. As there may be more than one potential source of imprecision (e.g., in float, 27.f * deg2rad is less precise than (27.f * π) / 180.f), it'd be better (as a wishlist item) to remove or alleviate at least one source of imprecision – in this particular report, the coarseness of the degree to deskew.

[DanBloomberg]

I appreciate your attention to such details. In my experience, a 1 or 2 pixel skew over a typical width of 2500 pixels (300 ppi) is unimportant, and the algorithm in Leptonica, which uses a binarized version of the image, should keep the skew under 1 pixel.

Two of the guidelines I used in writing Leptonica are to emphasize speed and simplicity. For that reason, for example, when we upscale images, the most accurate method uses linear interpolation. For some purposes this isn't sufficiently accurate, but for most it is, and it is simple and fast. If someone needs more accuracy they can use/write an upscaler that uses quadratic interpolation.

As for the widespread use of float instead of double, it was a choice in early days when memory was expensive and 32 bit computers were standard. If I were to implement leptonica today, I'd likely use double in most places.

[AlMa1r]

I understand your taste or choice of allowing for a skew by 1 or 2 pixels over a width of 2500 pixels. At 300 ppi, 1 pixel would probably not matter to me. At 600 dpi, it would be 2 pixels; I notice it. It's on the border between acceptable and inacceptable for me; if it gets worse, I definitely rotate such images. Again, this source of imprecision (coarse angles of the integer multiples of 0.000125°) is orthogonal to some others.

Though today I'd use double, too, or even long double, I don't object to the use of float per se. One of my points was that within a given bitwidth, it was possible to obtain a more precise result by cleverly choosing of the order of operations.

To keep the matters separate:
The wishlist item in this issue report refers only to the coarseness of the angles.