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)
27 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

Fingerprint

Data structures
Table lookup
Field programmable gate arrays (FPGA)
Mirrors
Optical character recognition
Demonstrations
Specifications
Data storage equipment
Processing

Keywords

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

ASJC Scopus subject areas

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

Cite this

Ultra-fast basic geometrical transformations on linear image data structure. / Vučković, Vladan; Arizanović, Boban; Blond, Simon Le.

In: Expert Systems with Applications, Vol. 91, 01.01.2018, p. 322-346.

Research output: Contribution to journalArticle

Vučković, Vladan ; Arizanović, Boban ; Blond, Simon Le. / Ultra-fast basic geometrical transformations on linear image data structure. In: Expert Systems with Applications. 2018 ; Vol. 91. pp. 322-346.
@article{69867ef686fc46708ee073bf1b338566,
title = "Ultra-fast basic geometrical transformations on linear image data structure",
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.",
keywords = "Affine transformations, Linear transformations, LUT, Machine optimization, Rotation, Spatial transformations",
author = "Vladan Vučković and Boban Arizanović and Blond, {Simon Le}",
year = "2018",
month = "1",
day = "1",
doi = "10.1016/j.eswa.2017.09.011",
language = "English",
volume = "91",
pages = "322--346",
journal = "Expert Systems with Applications",
issn = "0957-4174",
publisher = "Elsevier",

}

TY - JOUR

T1 - Ultra-fast basic geometrical transformations on linear image data structure

AU - Vučković, Vladan

AU - Arizanović, Boban

AU - Blond, Simon Le

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Affine transformations

KW - Linear transformations

KW - LUT

KW - Machine optimization

KW - Rotation

KW - Spatial transformations

UR - http://www.scopus.com/inward/record.url?scp=85029413462&partnerID=8YFLogxK

U2 - 10.1016/j.eswa.2017.09.011

DO - 10.1016/j.eswa.2017.09.011

M3 - Article

AN - SCOPUS:85029413462

VL - 91

SP - 322

EP - 346

JO - Expert Systems with Applications

JF - Expert Systems with Applications

SN - 0957-4174

ER -