Limitations and recommendations for future research

Métodos de clustering tem aplicações em qualquer área que necessite agrupar dados em classes específicas. Em particular, o método proposto neste trabalho foi testado em três aplicações bem distintas: Análise de dados de microscopia eletrônica, Segmentação e vetorização de imagens e Reconstrução 3D de superfícies. Os detalhes sobre a utilização do método para cada uma das aplicações encontram- se nos apêndices no final deste trabalho. A seguir será feito um breve resumo sobre a utilização do método nas aplicações descritas.

3.10.1

Análise de dados de microscopia eletrônica

Nesta aplicação, são captados dados de um microscópio de varredura eletrônica sobre amostras de minerais (em particular amostras de cimento). Estes dados correspondem às concentrações de átomos analisados no material. O conjunto é formado por pontos ou vetores cujas dimensões representam as concentrações dos átomos. Cada ponto consiste das concentrações em um determinado local no espaço na amostra em questão. Por exemplo na primeira dimensão podemos ter a concentração de cálcio, na segunda de oxigênio, etc. Este procedimento denomina-se na literatura de ZAP [26].

O problema consiste em classificar as regiões do material analisado em classes de acordo com as concentrações dos átomos neste material. A partir do conjunto de pontos amostrados de um certo material, aplicamos o método utilizando a abordagem da escolha do número de classes. Escolhe-se inicialmente um número Nw

de classes e seleciona-se o limiar até que este número seja atingido, segmentando em seguida o conjunto todo. Uma vez segmentado o conjunto, obtemos o modelo estatístico do mesmo. Com o modelo estatístico em mãos, procede-se a classificação de todos os pontos varridos pelo microscópio, formando assim uma imagem onde cada ponto representa a classe selecionada pelo algoritmo para aquele local da amostra. A imagem resultante consiste de uma imagem com regiões que

correspondem aos diferentes tipos de minerais presentes na amostra do material. A classificação química dos materiais ou minerais presentes nas amostras não é, obviamente, realizada pelo método de clustering. O método apenas separa o material em classes de 1 a Nw que devem ser posteriormente analisadas pelo especialista

da área. Mais detalhes sobre o procedimento para esta aplicação encontram-se no apêndice A.

3.10.2

Segmentação de imagens

Esta aplicação consiste em segmentar uma imagem digital de acordo com a textura. Segmentar uma imagem significa separá-la em regiões não sobrepostas onde os píxeis nestas regiões possuam atributos semelhantes [27]. Pela definição de segmentação, podemos tratar o problema como sendo um problema de clustering. Para isto, devemos considerar os pixeis da imagem como sendo os pontos que formarão o conjunto a ser agrupado. Os atributos são obtidos baseados nas componentes R, G e B de cada pixel, que são as componentes vermelho, verde e azul que formam as cores na imagem. Cada pondo do conjunto tem portanto três dimensões, correspondendo cada uma a uma componente de cor (R, G e B).

O objetivo é agrupar os pontos amostrados da imagem em classes que irão corresponder às regiões de texturas diferentes na mesma. Nesta aplicação, tanto a abordagem da escolha do limiar quanto da escolha do número de classes pode ser escolhida. Uma vez agrupados os pontos e gerado o modelo dos dados, cada pixel da imagem é classificado e a imagem segmentada é gerada. Cada pixel na imagem segmentada possui o rótulo da classe que foi designada pelo classificador.

3.10.3

Vetorização de imagens

Uma imagem digital é uma representação rasterizada de uma cena real. Sua representação mais comum é através de matrizes bidimensionais, onde a posição de cada elemento da matriz representa uma posição espacial relativa e ao valor do elemento naquela posição é associada uma intensidade de cor. Vetorizar uma imagem significa representar os desenhos existentes na mesma de forma vetorial, ou

seja, ao invés do mapa de bits convencional (matriz de pontos), utilizar primitivas geométricas, tais como retas, polígonos, círculos, elipses, etc para representar as regiões de coloração semelhante nesta imagem [69].

O procedimento de vetorização com o método proposto aproveita o conceito de ligação dos clusters auxiliares desenvolvido neste trabalho e não utiliza a técnica de clustering em si. O dado de entrada para o algoritmo de vetorização é uma imagem previamente segmentada, ou seja, com as regiões de coloração semelhante rotuladas com identificadores específicos.

Para utilizar o método proposto neste trabalho, um conjunto de dados é gerado a partir da imagem segmentada. A imagem deve conter apenas duas regiões; uma região de “fundo” e uma região que representa o objeto a ser vetorizado. O conjunto é formado por vetores bi-dimensionais em que cada vetor corresponde às coordenadas (x, y) dos pixeis que fazem parte da região do objeto. Se a imagem contiver mais de dois tipos de regiões segmentadas, basta executar o algoritmo para cada tipo região de modo individual para cada uma.

Uma vez extraído o conjunto da imagem, é realizada a quantização vetorial do mesmo, separando-o em Na pequenos clusters. Estes clusters corresponderão

a pequenas regiões de pixeis pertencentes aos objetos segmentados na imagem. Em seguida, um limiar é escolhido e os clusters auxiliares são ligados de acordo com o algoritmo já apresentado. Neste ponto, não interessa a classificação ou o agrupamento das regiões. A informação desejada será obtida das ligações realizadas entre os clusters. Cada ligação corresponde a um vetor na imagem vetorizada. Este vetor é calculado observando-se os centros de cada par de cluster ligados.

3.10.4

Reconstrução 3D

A reconstrução de uma superfície é um procedimento que converte um conjunto de pontos no espaço ou seções transversais em uma representação de superfície, identificando-a e representando-a através de primitivas geométricas [43], tais como polígonos, triângulos, ou superfícies contínuas.

Neste tipo de aplicação, os dados são fornecidos, em geral, por scanners 3D. Estes equipamentos são capazes de realizar varreduras tridimensionais em um

objeto e capturar as posições espaciais de pontos de sua superfície. Um algoritmo de reconstrução utiliza estas posições amostradas como espaço de entradas para obtenção da superfície representativa do objeto escaneado.

O método proposto neste trabalho é capaz de obter, para um dado conjunto de posições espaciais, um conjunto de arestas interligando os vértices de polígonos candidatos à realizar a reconstrução completa da superfície.

Inicialmente o conjunto é quantizado em Na pequenos clusters, que serão

compostos por pontos da superfície do objeto (já adquiridos com o scanner ou outro equipamento). Em seguida, um limiar é definido e os clusters são ligados com base neste limiar. Como na vetorização de imagens, as “ligações” darão origens a vetores. Os vetores gerados a partir do conjunto de dados são as arestas dos polígonos candidatos. Operações posteriores de filtragem e seleção de elementos permitirão obter representações poligonais adequadas para a superfície reconstruída.

3.11

Sumário

Neste capítulo foi descrito e desenvolvido o método proposto neste trabalho. Foram descritas as métricas utilizadas bem como o algoritmo final de clustering e classificação. Sobre as métricas utilizadas, procurou-se explorar o conceito de invariância a transformações lineares, com o objetivo de validar seu uso no algoritmo de clustering proposto. Foi proposta uma nova métrica de divergência baseada no conceito de negentropia utilizando a entropia de Rényi. Uma forma analítica para o cálculo da divergência proposta foi desenvolvido, sendo possível com a utilização da entropia de Rényi. Foram analisados também os aspectos sobre o custo computacional envolvido e, ao final, um resumo sobre algumas aplicações foi apresentado.

Testes e Resultados

4.1

Introdução

Neste capítulo serão apresentados alguns testes e resultados obtidos com o método desenvolvido neste trabalho. Os testes realizados destinam-se a ilustrar o comportamento de cada ítem ou etapa apresentada no capítulo 3. Em seguida serão apresentados alguns resultados juntamente com uma análise qualitativa sobre o comportamento do método em cada situação apresentada. Ao final, serão feitas análises comparativas com outros métodos de clustering.