#260 Rotation exhibits clipping/shearing errors for short wide images at some angles

[Troy Patteson]

Rotating the attached postnet barcode image (postnet.png) between 30 and 45 degrees generates an output that is either slightly clipped (postnet_rot30.png) or actually exhibits some form of shearing error (postnet_rot45.png). Output images were generated with:

gm convert postnet.png -rotate 30 postnet_rot30.png #Cropped
gm convert postnet.png -rotate 45 postnet_rot45.png #Sheared

I have tested by cropping other images to generate different aspect ratios. Problems appear to start when the aspect ratio (width/height) exceeds around 7.52. Limiting the thread count to 1 did not change the result.

Troy Patteson

[Bob Friesenhahn]

I am able to reproduce this problem here. Must be some sort of a math problem. I will of course investigate.

  gm convert -monitor postnet.png  -rotate 30 null:
    100% [postnet.png] Rotate: 0 degrees...
    100% [postnet.png] Frame: 1221x1155+89+533 bevel inner 0 outer 0...
    100% [postnet.png] X Shear: -0.267949 degrees, region 1043x89+89+533...
    100% [postnet.png] Y Shear: +0.5 degrees, region 1067x89+77+533...
    100% [postnet.png] X Shear: -0.267949 degrees, region 1067x1155+77+0...
    100% [postnet.png] Crop: 948x599+137+278...

  gm convert -monitor postnet.png  -rotate 45 null:
    100% [postnet.png] Rotate: 0 degrees...
    100% [postnet.png] Frame: 1295x1617+126+764 bevel inner 0 outer 0...
    100% [postnet.png] X Shear: -0.414214 degrees, region 1043x89+126+764...
    100% [postnet.png] Y Shear: +0.707107 degrees, region 1080x89+107+764...
    100% [postnet.png] X Shear: -0.414214 degrees, region 1080x1617+107+0...
    100% [postnet.png] Crop: 800x800+247+408...

[Troy Patteson]

I have had a look at the source code and identified the problem to be within the XShearImage() function in shear.c. This function incorrectly handles the situation where pixel displacement would be outside the image by simply skipping translation of any pixels on that row rather than actually translating the pixels in that row that would appear in the output image. As YShearImage() was based on XShearImage() it has the same issue.

Attached is a patch to address this problem. The patch also renames the y variable in YShearImage to be x as it is used to loop across the x-axis of the image. I have added a few asserts to indicate limitations on the input parameters as bad input values could cause a buffer overflow.

I tested the patch by generating rotated images of the postnet barcode for angles between 0 and 359. I have also tested with other portrait and landscape images in a smilar fashion and everything seems to be working.

I also noticed that the RotateImage() function seemed to create a much larger border around the original image than is strictly necessary so I have included a second patch to use the minimum border possible. This patch must be applied after the first patch. The y_width variable has been renamed to shear1_width and corresponds to the width of the image after the first X shear. New variables shear2_height and shear3_width correspond to the height after the Y shear and width after the second X shear respectively. The bordered image width is chosen as the maximum of shear1_width and shear3_width. The bordered image height is shear2_height. Two additional pixels in each dimension are required to account for possible fractional displacement. I needed to fix an off-by-one error in both XShearImage() and YShearImage() which is only exercised when the pixel step exceeds the image boundary.

I tested this second patch as above and found that the images appear almost identical to those generated above. However, 168 of the 360 generated images had file sizes that differed to those generated via the first patch. Image compare shows that the differences are around the edges of the bars of the barcode. The original algorithm used the height of the entire bordered image rather than computing the actual height needed to be sheared. As the height affects the displacement calculation I believe that difference causes the slight variation.

I tested rotating the postnet barcode image 360 times in memory. The image was read once and then rotated and the rotated image discarded for each degree between 0 and 359. I ran the test 3 times using both patches. I also tested a second larger image. The times were:

1. X-shear bug fix:
   • Image 1 (postnet.png: 1043x89)
     • Run 1: 6.186485
     • Run 2: 5.843305
     • Run 3: 6.156400
     • Avg: 6.062063
   • Image 2 (ironman.png: 1920x960)
     • Run 1: 42.453647
     • Run 2: 42.560042
     • Run 3: 42.568016
     • Avg: 42.527235
2. With Rotation optimisation:
   • Image 1 (postnet.png: 1043x89)
     • Run 1: 4.610360
     • Run 2: 4.337294
     • Run 3: 4.206784
     • Avg: 4.384813
   • Image 2 (ironman.png: 1920x960)
     • Run 1: 30.226109
     • Run 2: 30.371276
     • Run 3: 30.403477
     • Avg: 30.333621

The second patch improves performance of rotation by around 40%. However, it will no doubt cause your shear/rotate test suite to fail as a result of the slight differences in the generated images and therefore may be too risky to use.

Cheers,

Troy Patteson

[Bob Friesenhahn]

Your patches are now applied to Mercurial as two separate commits and are in the latest development snapshot. Thank you for submitting such clean patches and thank you very much for investigating and fixing this yourself since I rather dreaded digging into it.

With your performance patch (I see the same boost that you do), the output seems close enough to simply warrant a change to the test suite reference image. I will make note of this as possibly changing the output in the NEWS file for the next release.