Generalized N-way iterative scanline fill algorithm for real-time applications

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

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)

Abstract

A generalized iterative scanline fill algorithm intended for use in real-time applications and its highly optimized machine code implementation are presented in this paper. The algorithm uses the linear image representation in order to achieve the fast memory access to the pixel intensity values. The usage of the linear image representation is crucial for achieving the highly optimized low-level machine code implementation. A few generalization features are also proposed, and discussion about the possible real-time applications is given. The proposed efficient machine code implementation is tested on several PC machines, and a set of numerical results is provided. The machine routine is compared with standard and optimized implementations of the 4-way flood fill algorithm and scanline fill algorithm. The machine code implementation performs approximately 2 times faster than the optimized scanline fill algorithm implementation and 6 times faster than standard iterative scanline fill algorithm implementation on two-dimensional image data structure. Furthermore, the machine routine proved to perform even more than 15 times faster than the optimized flood fill algorithm implementations. Provided results prove the efficiency of the proposed generalized scanline fill algorithm and its advantage over the state-of-the-art algorithms, and clearly show that optimized machine routine is capable of performing the real-time tasks.

Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalJournal of Real-Time Image Processing
Early online date6 Nov 2017
DOIs
Publication statusE-pub ahead of print - 6 Nov 2017

Keywords

  • Boundary fill
  • Flood fill
  • Image processing
  • Machine optimization
  • Region filling
  • Scanline fill

ASJC Scopus subject areas

  • Information Systems

Fingerprint

Dive into the research topics of 'Generalized N-way iterative scanline fill algorithm for real-time applications'. Together they form a unique fingerprint.

Cite this