Ultra-fast basic geometrical transformations on linear image data structure

Vladan Vučković, Boban Arizanović, Simon Le Blond

Research output: Contribution to journalArticle

2 Citations (Scopus)
42 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)322-346
Number of pages25
JournalExpert Systems with Applications
Volume91
Early online date9 Sep 2017
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Affine transformations
  • Linear transformations
  • LUT
  • Machine optimization
  • Rotation
  • Spatial transformations

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Ultra-fast basic geometrical transformations on linear image data structure'. Together they form a unique fingerprint.

  • Cite this