Ultra-fast basic geometrical transformations on linear image data structure

- Ultra-fast architecture for geometrical image transformations is presented.
- The mathematical background of the proposed architecture is presented in detail.
- The highly-optimized low-level machine code implementations are provided.
- A large set of empiric results prove performance of the proposed implementations.

This paper presents a general, ultra-fast approach for geometrical image transformations, based on the usage of linear lookup hash tables. The new method is developed to fix distortions on document images as part of a real-time optical character recognition (OCR) system. The approach is generalized and uses linear image representation combined with pre-computed lookup tables. Backward mapping is used for generation of lookup tables, while forward mapping is presented as an alternative and more efficient mapping model for specific cases. Also, a theoretical space and time complexity analysis of the proposed method is provided. To achieve maximal computational performance, pointer arithmetic and highly-optimized low-level machine code implementations are provided, including the specialized implementations for horizontal mirror, vertical mirror, and 90° rotation. Also, a modified variant of the approach, based on auto-generated machine code is presented. Very high computational performances are achieved at the expense of memory usage. The performances from the perspective of time complexity are analyzed and compared with classical implementation, FPGA implementation, and other implementations of the image rotation. Numerical results are given for a set of different PC specifications to provide full insight into the implementation performances. The processing time for very large images are below 200 ms for backward mapping and below 100 ms for forward mapping for most machines, which is 30-60 times faster than the classical implementation, 5-20 times faster than the FPGA implementation, and up to 6 times faster than other implementations of image rotation. Original documents belonging to Nikola Tesla are used for visual demonstration of performance.