Real-time optimal-memory image rotation for embedded systems

Skew-corrected document images are necessary for subsequent downstream operations such as archiving, printing or improving OCR performance. Image rotation is a necessary and more expensive step in achieving skew correction of document images. Other applications of rotation include, image registration and orientation correction. Traditional image rotation algorithms [2-4] such as three-shear rotation [1] require three separable shears of the image. The embedded use of such techniques in scanners/printers presents technical challenges, since the memory available is limited and/or the document image is only available progressively in chunks of say 32 or 64 rows (swaths). Traditional image rotation algorithms require the entire image to be available before commencing the rotation operation. This paper presents an approach that allows image rotation using swaths of the image thus minimizing the overall memory requirement. We theoretically prove that the number of image swaths that are to be buffered is independent of the image size and depends only on the rotation angle. This approach enables rotation of any arbitrary sized image on memory constrained devices. The memory savings realized is at least 80%, for an A4-sized document image rotated 15°. Our progressive approach demonstrates real-time image rotation and hence improves on the state-of-the-art approaches for reduction of rotation complexity [5-10].