• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
10.11606/D.45.2018.tde-12112015-150044
Document
Author
Full name
Alexandre Morimitsu
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2015
Supervisor
Committee
Hashimoto, Ronaldo Fumio (President)
Lotufo, Roberto de Alencar
Miranda, Paulo Andre Vechiatto de
Title in Portuguese
Computação incremental e eficiente de sequências de árvores de componentes
Keywords in Portuguese
Árvore de componentes
Componente conexo
Conectividade de segunda geração
Operador conexo
Abstract in Portuguese
Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional.
Title in English
Incremental and efficient computation of sequences of component trees
Keywords in English
Component tree
Connected component
Connected operator
Second-generation connectivity
Abstract in English
Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
dissertacao.pdf (1.86 Mbytes)
Publishing Date
2018-11-26
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.