| Title: | Adaptable Intelligent Sensor |
| Other Titles: | Connected Component Tree Construction for Embedded Systems |
| Authors: | Matas, Petr |
| Advisor: | Georgiev, Vjačeslav Poupa, Martin Akil, Mohamed |
| Referee: | Weber, Serge Matula, Petr Vavřička, Vlastimil |
| Issue Date: | 2014 |
| Publisher: | Západočeská univerzita v Plzni |
| Document type: | disertační práce |
| URI: | http://hdl.handle.net/11025/12811 |
| Keywords: | strom souvislých komponent;parent point tree;konstrukce;graf;atributy;stavění;slučování;algoritmus;plánování;zpracování obrazu;hardware;VHDL;FPGA |
| Keywords in different language: | connected component tree;parent point tree;construction;graph;attributes;building;merger;algorithm;scheduling;image processing;hardware;VHDL;FPGA |
| Abstract: | Cílem této práce je umožnit konstrukci vestavěných systémů pro zpracování digitalizovaného obrazu, které jsou zároveň flexibilní a výkonné. Zkoumá se možnost použití reprezentace snímku zvané strom souvislých komponent (connected component tree, CCT) jako základu pro implementaci celého řetězce pro zpracování obrazu. Toto je možné, protože CCT je zároveň jednoduchý i obecný. Existují totiž na CCT založené implementace operátorů od filtrování až po segmentaci a rozpoznávání. Typický řetězec zpracování obrazu založený na CCT sestává z konstrukce CCT ze vstupního snímku, kaskády transformací CCT, které implementují jednotlivé operátory, a restituce obrazu, která generuje výstupní snímek z modifikovaného CCT. Časově nejnáročnějším krokem je konstrukce CCT a tato práce se na ni zaměřuje. Práce představuje CCT a jeho možné reprezentace v počítačové paměti, ukazuje některé jeho aplikace a analyzuje existující algoritmy konstrukce CCT. Je navržen nový paralelní algoritmus konstrukce CCT, jehož výstupem je reprezentace CCT zvaná parent point tree. Tento algoritmus je vhodný k implementaci ve vestavěných systémech díky malým paměťovým nárokům. Algoritmus se skládá z mnoha úloh stavění a slučování. Z jednoho řádku snímku, se kterým se zachází jako s jednorozměrným signálem, stavění vytvoří CCT a slučování spojují tyto CCT dohromady. Tři různé strategie plánování úloh jsou vyvinuty a zhodnoceny. Výkonnost algoritmu je otestována na několika paralelních počítačích. Na 16jádrovém stroji s procesory Opteron 885 je dosaženo propustnosti 83 Mpx/s při 13,3násobném zrychlení paralelizací. Následně je algoritmus dále adaptován pro hardwarovou implementaci a implementován jako nová paralelní hardwarová architektura. Ta obsahuje 16 základních bloků, z nichž každý zpracovává část snímku a skládá se z výkonných jednotek a pamětí. Je navržen speciální propojovací přepínač, aby některé výkonné jednotky mohly přistupovat k paměti v ostatních základních blocích. Algoritmus toto vyžaduje pro závěrečné slučování CCT vytvořených různými základními bloky dohromady. Architektura je implementována ve VHDL a její funkční simulace dává výkonnost 145 Mpx/s při frekvenci hodin 120 MHz. |
| Abstract in different language: | 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. |
| Rights: | Plný text práce je přístupný bez omezení. |
| Appears in Collections: | Disertační práce / Dissertations (KAE) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Dissertation.pdf | Plný text práce | 5,41 MB | Adobe PDF | View/Open |
| matas publ.pdf | Posudek vedoucího práce | 481,31 kB | Adobe PDF | View/Open |
| matas opon.pdf | Posudek oponenta práce | 2,55 MB | Adobe PDF | View/Open |
| matas zapis.pdf | Průběh obhajoby práce | 669,43 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/12811Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.