O restante deste trabalho está organizado em três partes, compreendendo: conceitos, metodo- logias e aplicações. A primeira parte da tese é dedicada às apresentações de conceitos, notações, algoritmos e propriedades relacionadas com: imagens e operadores morfológicos (Capítulo 2); ope- radores conexos e suas especializações como os levelings e os monotone planing (Capítulo3); repre- sentações hierárquicas de conjuntos de níveis, incluindo árvores de componentes e árvores de formas (Capítulo 4). A segunda parte é dedicada às principais contribuições originais desta pesquisa, as quais incluem: (i) uma representação compacta e eficiente de um espaço de escalas baseado em levelings por meio de árvores (Capítulo5); (ii) apresentação da classe dos últimos levelings, isto é, definições, conceitos, algoritmos, propriedades e relações com operadores conhecidos na literatura (Capítulo6); (iii) estratégias para construção de operadores últimos levelings (Capítulo 7). A ter- ceira parte é dedicada as aplicações dos últimos levelings em problemas de análise e processamento
1ImageJ é um software livre, desenvolvido em Java, para análise e processamento de imagens. Ele pode ser
6 INTRODUÇÃO 1.4 de imagens, incluindo: a segmentação de vasos sanguíneos em imagens de retinas (Capítulo 8), a binarização de texto em imagens de documentos históricos (Capítulo9) e a localização de textos em imagens de cenas (Capítulo10). Por fim, no Capítulo11são apresentadas as conclusões e trabalhos futuros.
Parte I
Conceitos sobre imagens, operadores e
representações
Resumo
Esta primeira parte da tese é dedicada a apresentações de conceitos, notações, algoritmos e propriedades relacionados com:
1. Imagens, como por exemplo: definições e notações de componentes conexos, zonas planas, extremas regionais, partições sobre domínio da imagem e perfis de intensi- dade;
2. Operadores morfológicos, como por exemplo: propriedades relacionadas aos operado- res morfológicos e, definições e notações sobre elemento estruturante, erosão, dila- tação, abertura, fechamento, reconstrução por dilatação e reconstrução por erosão; 3. Operadores conexos e suas especializações como os levelings e os monotone planing,
incluindo: definições, notações, propriedades relacionados a estes operadores e cons- trução de espaço de escala baseado em levelings;
4. Representações hierarquias de conjuntos de níveis, incluindo: definições, notações, algoritmos e propriedades relacionadas as árvores construídas a partir de conjuntos parcialmente ordenados, como por exemplo: árvores de componentes e árvores de formas.
Vale salientar, que todos os conceitos, notações, algoritmos e propriedades apresenta- das nesta primeira parte da tese são úteis para o entendimento dos conceitos discutidos nas duas próximas partes desta tese e mais, também são assumidas definições usuais de conjuntos, relações, funções, grafos, conjuntos ordenados, reticulados e espaços topológi- cos que podem ser encontradas em um livro introdutório sobre topologia geral, como por exemplo Lipschutz (1971) e Newman (1992). Também vale lembrar que muitas funções apresentadas ao longo do texto são representadas por meio de tabelas, como por exemplo as funções que representam imagens. Assim, em diversos algoritmos apresentados, tabe- las que representam funções são construídas e a notação usada para atribuir um valor a função é a seguinte: f (x)← y, onde f é a função, x um elemento do domínio da função e y é a imagem de x em f e este valor y é atribuído a tabela que representa a função f .
Capítulo 2
Conceitos sobre imagens e operadores
morfológicos
Resumo do capítulo
Neste capítulo são apresentados conceitos, definições e notações relacionadas com ima- gens e operadores morfológicos que serão úteis ao longo do texto. Vale salientar, que neste texto, são assumidas definições usuais de conjuntos, relações, funções, grafos, reti- culados e espaços topológicos que podem ser encontradas em um livro introdutório sobre topologia geral, como por exemplo Lipschutz (1971);Newman (1992).
2.1 Definições básicas sobre imagens
Como definido na Seção 1.1, neste trabalho trata-se uma imagem f ∈ F(D) como um mapea-
mento de uma grade retangular e finita D ⊂ Z×Z em um conjunto discreto K = {0, ..., K} de níveis de cinza (isto é, f : D → K), onde K = 2b− 1 representa o nível de cinza máximo possível para
uma imagem de b > 0 bits de profundidade. Uma imagem binária, quando b = 1, pode ter somente valores 0 ou 1, e por este motivo é frequentemente representada como um subconjunto X ⊆ D contendo os elementos de D cujos os valores são 1, ou seja, X = {x ∈ D : f(x) = 1} ∈ P(D). Por outro lado, uma imagem multibanda pode ser vista como um vetor de imagens (fA, fB, ..., fZ),
onde fA, fB, ..., fZ fazem referências às bandas A, B, ..., Z da imagem multibanda. Um elemento
do domínio da imagem é chamado de pixel, ou seja, p = (px, py)∈ D é um pixel cujo os valores px
e py são os valores das coordenadas horizontal e vertical de p. Também, chama-se por f(p) o valor
do nível de cinza da imagem no pixel p. Além do mais, o pixel p está conectado a outros pixels em seu entorno em D e esta noção de conectividade entre os pixels leva à definir uma relação de adjacência, denominada A, sobre D.
Definição 2.1 (Relação de adjacência). Uma relação de adjacência A sobre D é uma relação binária entre os pixels de D, ou seja, A ⊆ D × D. Assim, se (p, q) ∈ A então é dito que p é adjacente a q ou alternativamente, p é vizinho de q.
Em particular, neste trabalho são utilizadas somente relações de adjacências circulares e simétri- cas, ou seja, (p, q) ∈ A se, e somente se, p, q ∈ D, d(p, q) ≤ ρ, onde d(p, q) =p(px− qx)2+ (py− qy)2
é a distância euclidiana entre p e q, e ρ é um fator de escala. Dessa forma, se ρ = 1, temos a relação de adjacência, denotada por A4c, que define a conhecida vizinhança-4 entre os pixels e
analogamente se ρ = √2, temos o caso da vizinhança-8, denotada por A8c, entre os pixels (ver
10 CONCEITOS SOBRE IMAGENS E OPERADORES MORFOLÓGICOS 2.1 Figura 2.1). Também, denotaremos o conjunto de pixels adjacentes a um dado pixel p ∈ D por
AD(p) ={q ∈ D : p é adjacente a q} ou simplesmente por A(p) quando não existir ambiguidade.
q3 q2 p q4 q1 q4 q5 q6 q3 p q7 q2 q1 q8 q11 q4 q5 q6 q10 q3 p q7 q12 q2 q1 q8 q9 ρ = 1 ρ =√2 ρ = 2
Figura 2.1:Exemplos de relações de adjacências para um dado pixel p.
Note que, uma relação binária E sobre um conjunto V dá origem a um grafo direcionado G = (V, E), onde o conjunto V é chamado de conjunto de vértices de G e E é chamado de conjunto de arestas de G. Assim, a relação de adjacência A sobre D, dá origem ao grafo da imagem Gf = (D, A),
onde os vértices são os próprios pixels e as arestas são definidas por A. Com base nesta noção de conectividade entre os pixels, define-se:
Definição 2.2 (Caminho). Sejam x e y dois pixels de X ⊆ D. Diz-se que existe um caminho de x até y em X , denotado por π(x, y) se, e somente se, existir uma n-tupla de pixels distintos (p1, p2, ..., pn) tal que p1= x, pn= y e pi+1∈ AX(pi), para 1≤ i ≤ n − 1.
Definição 2.3 (Componente conexo). Um componente conexo (CC) C é um subconjunto maximal de pixels de X ⊆ D, tal que para quaisquer dois pixels p e q ∈ C, existe um caminho de p até q em C. Denota-se por CC(X , A) o conjunto dos CCs presentes em X definidos com a relação de adjacência A ou simplesmente por CC(X ) quando A está bem definida. Na Figura2.2é apresentado um exemplo de extração de CCs para um dado conjunto X onde os CCs estão rotulados pelas cores: vermelho, verde e azul.
q3 q2 p q4 q1 A4c X D CC(X , A4c)
Figura 2.2:Exemplo de extração dos CCs do conjunto X ⊆ D sobre a adjacência A4c.
Definição 2.4 (Zona plana). Uma zona plana C de uma imagem f ∈ F(D) é um subconjunto maximal de pixels de D, tal que para quaisquer dois pixels p e q ∈ C, existe uma n-tupla de pixels (p1 = p, p2, ..., pn = q), satisfazendo pi+1 ∈ A(pi) e f (pi) = f (pi+1), para 1≤ i ≤ n − 1. Denota-se
por ZP(f, A) o conjunto das zonas planas presentes em uma imagem f definidas com a relação de adjacência A, ou simplesmente por ZP(f) quando A está bem definida. Na Figura2.3é apresentado um exemplo de extração de zonas planas para uma dada imagem f ∈ F(D), onde as zonas planas estão rotuladas pelas cores: vermelha, verde, azul, amarela, laranja, ciano, violeta e cinza.
2.2 OPERADORES MORFOLÓGICOS 11