Detecção de objetos é um problema clássico em visão computacional, presente em aplicações como vigilância automatizada, análise de imagens médicas e recuperação de informação. Dentre as abordagens existentes na literatura para resolver esse problema, destacam-se métodos baseados em reconhecimento de pontos-chave que podem ser interpretados como diferentes implementações de um mesmo arcabouço. O objetivo desta pesquisa de doutorado é desenvolver e avaliar uma versão generalizada desse arcabouço, na qual reconhecimento de pontos-chave é substituído por reconhecimento de grafos-chave. O potencial da pesquisa reside na riqueza de informação que um grafo pode apresentar antes e depois de ser reconhecido. A dificuldade da pesquisa reside nos problemas que podem ser causados por essa riqueza, como maldição da dimensionalidade e complexidade computacional. Três contribuições serão incluídas na tese: a descrição detalhada de um arcabouço para detecção de objetos baseado em grafos-chave, implementações fiéis que demonstram sua viabilidade e resultados experimentais que demonstram seu desempenho. / Object detection is a classic problem in computer vision, present in applications such as automated surveillance, medical image analysis and information retrieval. Among the existing approaches in the literature to solve this problem, we can highlight methods based on keypoint recognition that can be interpreted as different implementations of a same framework. The objective of this PhD thesis is to develop and evaluate a generalized version of this framework, on which keypoint recognition is replaced by keygraph recognition. The potential of the research resides in the information richness that a graph can present before and after being recognized. The difficulty of the research resides in the problems that can be caused by this richness, such as curse of dimensionality and computational complexity. Three contributions are included in the thesis: the detailed description of a keygraph-based framework for object detection, faithful implementations that demonstrate its feasibility and experimental results that demonstrate its performance.

Detecção de objetos é um problema clássico em visão computacional, presente em aplicações como vigilância automatizada, análise de imagens médicas e recuperação de informação. Dentre as abordagens existentes na literatura para resolver esse problema, destacam-se métodos baseados em reconhecimento de pontos-chave que podem ser interpretados como diferentes implementações de um mesmo arcabouço. O objetivo desta pesquisa de doutorado é desenvolver e avaliar uma versão generalizada desse arcabouço, na qual reconhecimento de pontos-chave é substituído por reconhecimento de grafos-chave. O potencial da pesquisa reside na riqueza de informação que um grafo pode apresentar antes e depois de ser reconhecido. A dificuldade da pesquisa reside nos problemas que podem ser causados por essa riqueza, como maldição da dimensionalidade e complexidade computacional. Três contribuições serão incluídas na tese: a descrição detalhada de um arcabouço para detecção de objetos baseado em grafos-chave, implementações fiéis que demonstram sua viabilidade e resultados experimentais que demonstram seu desempenho. / Object detection is a classic problem in computer vision, present in applications such as automated surveillance, medical image analysis and information retrieval. Among the existing approaches in the literature to solve this problem, we can highlight methods based on keypoint recognition that can be interpreted as different implementations of a same framework. The objective of this PhD thesis is to develop and evaluate a generalized version of this framework, on which keypoint recognition is replaced by keygraph recognition. The potential of the research resides in the information richness that a graph can present before and after being recognized. The difficulty of the research resides in the problems that can be caused by this richness, such as curse of dimensionality and computational complexity. Three contributions are included in the thesis: the detailed description of a keygraph-based framework for object detection, faithful implementations that demonstrate its feasibility and experimental results that demonstrate its performance.

Diversos problemas práticos envolvendo sistemas de visão computacional, tais como vigilância automatizada, pesquisas de conteúdo específico em bancos de dados multimídias ou edição de vídeo, requerem a localização e o reconhecimento de objetos dentro de seqüências de imagens ou vídeos digitais. Mais formalmente, denomina-se rastreamento o processo de determinação da posição de certo(s) objeto(s) ao longo do tempo numa seqüência de imagens. Já a tarefa de reconhecimento caracteriza-se pela classificação desses objetos de acordo com algum rótulo pré-estabelecido ou apoiada em conhecimento prévio tipicamente introduzido através de um modelo dos objetos de interesse. No entanto, rastrear e classificar objetos em vídeo digital são tarefas desafiadoras, tanto pelas dificuldades inerentes a esse tipo de elemento pictórico, quanto pelo variável grau de complexidade que os quadros sob análise podem apresentar. Este documento apresenta uma metodologia baseada em modelo para rastrear e reconhecer objetos em vídeo digital através de uma representação por grafos relacionais com atributos (ARGs). Tais estruturas surgiram dentro do paradigma de reconhecimento estrutural de padrões e têm se mostrado bastante flexíveis e poderosas para modelar problemas diversos, pois podem transmitir dados quantitativos, relacionais, estruturais e simbólicos. Como modelo e entrada são descritos através desses grafos, a questão de reconhecimento é interpretada como um problema de casamento inexato entre grafos, que consiste em mapear os vértices do ARG de entrada nos vértices do ARG modelo. Em seguida, é realizado o rastreamento dos objetos de acordo com uma transformação afim derivada de parâmetros obtidos da etapa de reconhecimento. Para validar a metodologia proposta, resultados sobre seqüências de imagens digitais, sintéticas e reais, são apresentados e discutidos. / Several practical problems involving computer vision systems, such as automated surveillance, content-based queries in multimedia databases or video editing require the location and recognition of objects within image sequences or digital video. More formally, the process of determining the position of certain objects in an image sequence throughout time is called tracking, whereas the recognition task is characterized by the classification of such objects according to pre-defined labels or a priori knowledge, typically introduced by means of a model of the target objects. However, tracking and recognition of objects in digital video are not simple tasks, either because of the inherent difficulties of such a pictorial element, or due to the variable level of complexity that the frames under consideration might present. This document presents a model-based methodology for tracking and recognizing objects represented by attributed relational graphs (ARGs) in digital video. These structures have arisen from the paradigm of structural pattern recognition and have proven to be very flexible and powerful for modeling various problems, as they can hold many sorts of data (e.g: quantitative, relational, structural and symbolic). Since both model and input data are described through these graphs, the recognition matter may be interpreted as an inexact graph matching problem, which consists in finding a correspondence between the set of vertices of the input ARG and that of the model ARG. In the next step, object tracking is performed according to an affine transform derived from parameters extracted from the recognition phase. To validate the proposed methodology, results obtained from real and synthetic digital image sequences are presented and discussed.

Diversos problemas práticos envolvendo sistemas de visão computacional, tais como vigilância automatizada, pesquisas de conteúdo específico em bancos de dados multimídias ou edição de vídeo, requerem a localização e o reconhecimento de objetos dentro de seqüências de imagens ou vídeos digitais. Mais formalmente, denomina-se rastreamento o processo de determinação da posição de certo(s) objeto(s) ao longo do tempo numa seqüência de imagens. Já a tarefa de reconhecimento caracteriza-se pela classificação desses objetos de acordo com algum rótulo pré-estabelecido ou apoiada em conhecimento prévio tipicamente introduzido através de um modelo dos objetos de interesse. No entanto, rastrear e classificar objetos em vídeo digital são tarefas desafiadoras, tanto pelas dificuldades inerentes a esse tipo de elemento pictórico, quanto pelo variável grau de complexidade que os quadros sob análise podem apresentar. Este documento apresenta uma metodologia baseada em modelo para rastrear e reconhecer objetos em vídeo digital através de uma representação por grafos relacionais com atributos (ARGs). Tais estruturas surgiram dentro do paradigma de reconhecimento estrutural de padrões e têm se mostrado bastante flexíveis e poderosas para modelar problemas diversos, pois podem transmitir dados quantitativos, relacionais, estruturais e simbólicos. Como modelo e entrada são descritos através desses grafos, a questão de reconhecimento é interpretada como um problema de casamento inexato entre grafos, que consiste em mapear os vértices do ARG de entrada nos vértices do ARG modelo. Em seguida, é realizado o rastreamento dos objetos de acordo com uma transformação afim derivada de parâmetros obtidos da etapa de reconhecimento. Para validar a metodologia proposta, resultados sobre seqüências de imagens digitais, sintéticas e reais, são apresentados e discutidos. / Several practical problems involving computer vision systems, such as automated surveillance, content-based queries in multimedia databases or video editing require the location and recognition of objects within image sequences or digital video. More formally, the process of determining the position of certain objects in an image sequence throughout time is called tracking, whereas the recognition task is characterized by the classification of such objects according to pre-defined labels or a priori knowledge, typically introduced by means of a model of the target objects. However, tracking and recognition of objects in digital video are not simple tasks, either because of the inherent difficulties of such a pictorial element, or due to the variable level of complexity that the frames under consideration might present. This document presents a model-based methodology for tracking and recognizing objects represented by attributed relational graphs (ARGs) in digital video. These structures have arisen from the paradigm of structural pattern recognition and have proven to be very flexible and powerful for modeling various problems, as they can hold many sorts of data (e.g: quantitative, relational, structural and symbolic). Since both model and input data are described through these graphs, the recognition matter may be interpreted as an inexact graph matching problem, which consists in finding a correspondence between the set of vertices of the input ARG and that of the model ARG. In the next step, object tracking is performed according to an affine transform derived from parameters extracted from the recognition phase. To validate the proposed methodology, results obtained from real and synthetic digital image sequences are presented and discussed.

Esta tese de doutorado aborda os tópicos de modelagem e de reconhecimento de objetos estruturados, ou sistemas estruturados de objetos, em imagens. Um objeto ou sistema estruturado é aquele que pode ser descrito através de elementos primitivos que o compõem e pelas relações existentes entre esses elementos. Por exemplo, uma aeronave pode ser descrita pelos seguintes elementos primitivos: asas direita e esquerda, fuselagem e cockpit. O aspecto relacional de um objeto estruturado direciona sua representação computacional e seu reconhecimento em imagens ao paradigma estrutural de reconhecimento de padrões. Contudo, a variabilidade das características dos seus elementos primitivos é melhor representada através do paradigma estatístico de reconhecimento de padrões. Devido à complementaridade dos paradigmas, a conjunção dessas abordagens é um tema de pesquisa de interesse atual. Para conjugar esses dois aspectos, esta tese propôs uma metodologia que combina o conhecimento a priori das relações que caracterizam um objeto estruturado com dados estatísticos coletados de amostras desse objeto, num modelo híbrido denominado grafo estatístico-relacional (GER). Segundo essa representação, foi estudada uma abordagem probabilística para reconhecer um objeto estruturado em imagens. Nesse cenário, o GER modelo é considerado uma variável aleatória, enquanto uma rotulação de uma imagem de entrada é interpretada como uma potencial observação do modelo. A tarefa de reconhecimento foi então formulada como um problema de otimização, que busca maximizar a probabilidade da observação de acordo com o modelo. O método foi aplicado à modelagem de órgãos abdominais em imagens de ressonância magnética não-contrastadas. Esses órgãos apresentam um arranjo espacial consistente em imagens distintas, além de propriedades de aparência e anatômicas variáveis, o que vem ao encontro da proposta da representação por GER e da abordagem probabilística para o reconhecimento dos órgãos em novas imagens. / The purpose of this thesis was to propose a formalism for the problems of modeling and recognition of a structured object, or a system of structured objects, in images. A structured object is one that may be described in terms of its compound primitive elements and their inherent relations. For instance, an aircraft may be described in terms of the following primitives: right and left wings, fuselage, and cockpit. The relational aspect of structured objects leads these problems to solutions in structural pattern recognition, which describes patterns as primitives and relations. Nevertheless, the variability of primitive elements and of their relations is better modeled by traditional statistical pattern recognition methods. Because of the complementary capabilities of these approaches, the fusion of both has recently been pointed out as a trend in computer vision. To consider these sources of information, the methodology presented herein combines relational cues inherent to a structured object with statistical information learned from a set of object samples. A hybrid model of a structured object is represented by means of a statistical relational graph (SRG). The SRG is a prototype attributed relational graph (ARG) in which nodes represent primitive elements and arcs link nodes representing related primitives. Each node or arc is associated with attributes which are parameters of probability distributions that describe random variables representing primitive or relational attributes. Based on this representation, a probabilistic approach was proposed to tackle the problem of recognizing a structured object in an input image. The model SRG is interpreted as a random variable, whereas a labeling of the input image is considered a potential observation of the model. The recognition task was formulated as the optimization of an objective-function that is actually a probability measure to be maximized. The proposed approach was applied to the modeling of abdominal organs in non-contrasted magnetic resonance images. These organs present consistent spatial arrangement in distinct images, as well as varying appearance and anatomical properties, which meet the principle of the SRG representation and the associated probabilistic recognition scenario.

Esta tese de doutorado aborda os tópicos de modelagem e de reconhecimento de objetos estruturados, ou sistemas estruturados de objetos, em imagens. Um objeto ou sistema estruturado é aquele que pode ser descrito através de elementos primitivos que o compõem e pelas relações existentes entre esses elementos. Por exemplo, uma aeronave pode ser descrita pelos seguintes elementos primitivos: asas direita e esquerda, fuselagem e cockpit. O aspecto relacional de um objeto estruturado direciona sua representação computacional e seu reconhecimento em imagens ao paradigma estrutural de reconhecimento de padrões. Contudo, a variabilidade das características dos seus elementos primitivos é melhor representada através do paradigma estatístico de reconhecimento de padrões. Devido à complementaridade dos paradigmas, a conjunção dessas abordagens é um tema de pesquisa de interesse atual. Para conjugar esses dois aspectos, esta tese propôs uma metodologia que combina o conhecimento a priori das relações que caracterizam um objeto estruturado com dados estatísticos coletados de amostras desse objeto, num modelo híbrido denominado grafo estatístico-relacional (GER). Segundo essa representação, foi estudada uma abordagem probabilística para reconhecer um objeto estruturado em imagens. Nesse cenário, o GER modelo é considerado uma variável aleatória, enquanto uma rotulação de uma imagem de entrada é interpretada como uma potencial observação do modelo. A tarefa de reconhecimento foi então formulada como um problema de otimização, que busca maximizar a probabilidade da observação de acordo com o modelo. O método foi aplicado à modelagem de órgãos abdominais em imagens de ressonância magnética não-contrastadas. Esses órgãos apresentam um arranjo espacial consistente em imagens distintas, além de propriedades de aparência e anatômicas variáveis, o que vem ao encontro da proposta da representação por GER e da abordagem probabilística para o reconhecimento dos órgãos em novas imagens. / The purpose of this thesis was to propose a formalism for the problems of modeling and recognition of a structured object, or a system of structured objects, in images. A structured object is one that may be described in terms of its compound primitive elements and their inherent relations. For instance, an aircraft may be described in terms of the following primitives: right and left wings, fuselage, and cockpit. The relational aspect of structured objects leads these problems to solutions in structural pattern recognition, which describes patterns as primitives and relations. Nevertheless, the variability of primitive elements and of their relations is better modeled by traditional statistical pattern recognition methods. Because of the complementary capabilities of these approaches, the fusion of both has recently been pointed out as a trend in computer vision. To consider these sources of information, the methodology presented herein combines relational cues inherent to a structured object with statistical information learned from a set of object samples. A hybrid model of a structured object is represented by means of a statistical relational graph (SRG). The SRG is a prototype attributed relational graph (ARG) in which nodes represent primitive elements and arcs link nodes representing related primitives. Each node or arc is associated with attributes which are parameters of probability distributions that describe random variables representing primitive or relational attributes. Based on this representation, a probabilistic approach was proposed to tackle the problem of recognizing a structured object in an input image. The model SRG is interpreted as a random variable, whereas a labeling of the input image is considered a potential observation of the model. The recognition task was formulated as the optimization of an objective-function that is actually a probability measure to be maximized. The proposed approach was applied to the modeling of abdominal organs in non-contrasted magnetic resonance images. These organs present consistent spatial arrangement in distinct images, as well as varying appearance and anatomical properties, which meet the principle of the SRG representation and the associated probabilistic recognition scenario.