Skip to Main content Skip to Navigation

Connected component tree construction for embedded systems

Abstract : The aim of this work is to enable construction of embedded digital image processing systems, which are both flexible and powerful. The thesis proposal explores the possibility of using an image representation called connected component tree (CCT) as the basis for implementation of the entire image processing chain. This is possible, because the CCT is both simple and general, as CCT-based implementations of operators spanning from filtering to segmentation and recognition exist. A typical CCT-based image processing chain consists of CCT construction from an input image, a cascade of CCT transformations, which implement the individual operators, and image restitution, which generates the output image from the modified CCT. The most time-demanding step is the CCT construction and this work focuses on it. It introduces the CCT and its possible representations in computer memory, shows some of its applications and analyzes existing CCT construction algorithms. A new parallel CCT construction algorithm producing the parent point tree representation of the CCT is proposed. The algorithm is suitable for an embedded system implementation due to its low memory requirements. The algorithm consists of many building and merging tasks. A building task constructs the CCT of a single image line, which is treated as a one-dimensional signal. Merging tasks fuse the CCTs together. Three different task scheduling strategies are developed and evaluated. Performance of the algorithm is evaluated on multiple parallel computers. A throughput 83 Mpx/s at speedup 13.3 is achieved on a 16-core machine with Opteron 885 CPUs. Next, the new algorithm is further adapted for hardware implementation and implemented as a new parallel hardware architecture. The architecture contains 16 basic blocks, each dedicated to processing of an image partition and consisting of execution units and memory. A special interconnection switch is designed to allow some executions units to access memory in other basic blocks. The algorithm requires this for the final merging of the CCTs constructed by different basic blocks together. The architecture is implemented in VHDL and its functional simulation shows performance 145 Mpx/s at clock frequency 120 MHz
Document type :
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Wednesday, April 1, 2015 - 5:12:05 PM
Last modification on : Saturday, January 15, 2022 - 3:56:11 AM
Long-term archiving on: : Thursday, July 2, 2015 - 3:26:43 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01138336, version 1


Petr Matas. Connected component tree construction for embedded systems. Computer science. Université Paris-Est; Západočeská univerzita (Pilsen, République tchèque), 2014. English. ⟨NNT : 2014PEST1116⟩. ⟨tel-01138336⟩



Record views


Files downloads