Is there an imposed limit to accuracy?

[gtoal]

I have a document which is about 3000 pixels tall, which deskew does straighten - but the straightened document, although the horizontal lines are very level, exhibits a horizontal shear of 7 pixels between the top rows and the bottom rows. Since the application I'm using this for is segmenting fixed-pitch text into a grid in order to extract characters for OCR, a 7-pixel offset at the foot of the document causes a noticeable grid misalignment when the characters themselves are only something like 20 pixels wide. I was able to manually detect the shear needed to correct this, and apply it with the pnmshear command, but it would have been preferable if deskew had straightened the document completely rather than 99.8% or whatever. If deskew has some accuracy parameter beyond which it doesn't attempt to be more accurate, then an option for accuracy down to a single pixel would be appreciated, even if the runtime overhead is significantly higher.

[galfar]

Yes there is indeed an "angle step" value now fixed at 0.1 degrees when doing Hough transformation. Deskew can detect skew angle at "higher resolution" that this - however, the accuracy is limited by this. The reason is simple - time needed for skew detection goes up rapidly with smaller step.

Nevertheless, it can be a user option.
Also this #18 could be helpful when/if done.

[gtoal]

On a document that is 3000 pixels tall, an angle of 0.1 degrees is equivalent to a shear of 5 pixels over the height of the document. Admittedly that is close to being ignorable in my particular application but it would be nice to specify a step that permits exact accuracy, which for the scans I'm working with would be, I presume, 0.02 degrees. But again that's arbitrary and specific to the size of scans I'm working with. But the point I want to make is that I'm willing to put up with slow processing speeds if it avoids having to then examine the output by hand and have a subsequent stage of applying a final shear of a few pixels in order to get a perfect result.
As for the suggestion in #18 - a variation of that should work quite well - it's what I did when I wrote my own deskewing program some years ago (before switching to your code which is faster and more accurate in some cases - my code was somewhat naive in that I detected the rotation angle (actually, skew angle) by running a DDA across the page at the various test angles, while summing the square of the number of black and white pixels that the path ran through, for all y positions within the page. It appears that your Hough transform is a better algorithm), and that was to scan for the rotation angle at an initial angle step until a bracket was found around the best orientation, then divide those bounding angles by the number of steps per test (8, 10 , 16 - whatever) - except instead of being a 2-level operation, the bracketing and subdividing step can be repeated as often as necessary until the absolute error is less than 1 pixel. So the time taken increased linearly with each subdivision. In my code I was using shears to approximate the rotation, so detecting the end state was as simple as testing the difference in the number of pixels being sheared against 0. The hardest part of the algorithm was deciding which angle was barely clockwise and which was barely anticlockwise of the desired exact angle - there were some edge cases in there that you had to be careful with. Summary: instead of dividing your test range linearly using the smallest step, use a fixed number of larger steps across the same range, and then a divide-and-conquer stage that's repeated until you get to the accuracy that you find acceptable. I.e. like a binary chop but with more than 2 steps.

[galfar]

Ok, as a first step I'll expose the angle step value as a user option so it can be set as command line argument.

[gtoal]

Perhaps also add a parameter for the limits as well (ie what is currently +/- 10 I believe?) I can see how I could automate this by running your code once with default parameters (+/- 10 with step of 0.1), getting the angle at default resolution, then rerunning with a narrower range and smaller step... (eg +/- 1 with step of 0.01)