4. Methodology: Mobilizing assemblage thinking for empirical work
4.4 Accessing practices through texts
ou de formas.
1 seleção-de-vértices-baseada-valores-de-extinção(Árvore Tf, Parâmetro tI
M AX)
2 para cadavértice L∈ Folhas(Tf) faça
3 para cadavértice NLdo caminho (C1= Pai(L), C2, . . . , Cn= Raiz(Tf)) faça 4 se|Filhos(NL)| > 1 então
5 para cadavértice CL∈ Filhos(NL) faça
6 seC∈ Filhos(NL) tal que κ(C) > κ(CL) então
// κ(C) é o valor de extinção da folha L
7 ∀C ∈ Filhos(NL) tal que κ(C) ≤ tI
M AX define-se: Γ(C) ← é verdadeiro
1 seleção-de-vértices-baseada-transições-graduais(Árvore Tf, Parâmetro ∆, Parâmetro tI
M AX)
2 para cadavértice C deTf faça
3 seκ(Pai(C)) − κ(C) > ∆ E κ(C) ≤ tI
M AX então
4 Γ(C) ← é verdadeiro
Note que os vértices que correspondem as pequenas transições graduais de níveis de cinza ao longo da borda não são selecionados. Na Figura 7.4 é reapresentada a evolução residual usando duas famílias de primitivas baseada em valores de extinções.
Na Figura7.5são apresentados exemplos de entrada e saída para as seleções dos vértices a serem podados por estratégias de escolha de famílias de primitivas com base em (1) atributo de área, (2) transições graduais com parâmetro ∆ = 90 para o atributo de área e (3) valores de extinção usando o atributo de área.
7.1.2 Primitivas baseadas em imagens marcadoras
Como apresentado na Seção 5.3.2, um espaço de escala pode ser derivado a partir de uma fa- mília de imagens marcadoras (g1, g2, ..., gIM AX). Dessa forma, conforme apresentado na Seção5.3.2,
deriva-se da versão estendida de uma árvore Tf uma sequência de árvores podadas sucessivamente
(T0
f ,Tf1, . . . ,T IM AX
7.1 ESTRATÉGIAS PARA ESCOLHER A FAMÍLIA DE PRIMITIVAS 89 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 380 20 40 60 80 100 120 140
atributo de área atributo de altura
primitivas nív el de cinza do pixel selecionado
fechamento por área (resíduos nulos) fechamento por área (resíduos negativos)
fechamento por altura (resíduos nulos) fechamento por altura (resíduos negativos)
Figura 7.4: Análise da evolução residual para o pixel marcado de vermelho da imagem de entrada.
imagem de entrada (suavizada) UAC com atributo de área UAC com transições graduais UAC com valores de extinção
Árvore da imagem de entrada (podas baseadas em atributo de área)
Árvore da imagem de entrada (podas baseadas transições graduais de valor ∆ = 90 para o atributo de área)
Árvore da imagem de entrada (podas baseadas valores de extinção para o atributo de área)
Figura 7.5:Exemplos de entrada e saída dos processamentos baseados em transições graduais e valores de
extinção.
de Tf é selecionado pelo critério Γ se,
Γ(C) é verdadeiro ⇐⇒ ∃j tal que o vértice C foi removido e
90 ESTRATÉGIAS PARA CONSTRUÇÕES DE ÚLTIMOS LEVELINGS 7.2 O uso de família de primitivas construídas usando imagens marcadoras pode prover mais li- berdade ao operador, pois é possível adicionar informações a priori na construção da família de marcadores. Mas o uso dessas primitivas aumenta substancialmente o custo computacional dos úl- timos levelings. Por este motivo, sempre recomendamos o uso de primitivas baseadas em atributos e, se houver informações à priori, então pode-se aplicá-las através de estratégias de filtragens dos valores residuais indesejáveis (ver Seção7.2).
7.2 Estratégias para filtrar resíduos indesejáveis
Os últimos levelings são operadores definidos como o supremo de resíduos consecutivos extraí- dos ao longo de uma família de primitivas. Durante este processo de extração residual é comum a extração de valores residuais de regiões indesejáveis da imagem. Por conta disso, muitas vezes esses valores residuais indesejáveis se sobrepõem aos valores residuais extraídos de regiões desejá- veis, devido a própria concepção dos últimos levelings que consideram sempre os máximos valores residuais extraídos ao longo da família de primitivas. Esse problema de concepção dos últimos leve- lings, é chamado porRetornaz (2007) como miopia, que é normalmente produzido por estruturas aninhadas ou por transições graduais. Nesta direção,Hernandez e Marcotegui (2011) propuseram uma solução para este problema usando informação de formas no processo de extração residual, mas o inconveniente dessa abordagem é que os valores residuais podem ser modificados devido uma função de similaridade que multiplica com os valores residuais e com isso as propriedade dos últimos levelings acabam sendo anuladas.
Por outro lado, nesta tese propõe-se preservar os valores residuais extraídos ao longo da família de primitivas e informações sobre regiões indesejáveis são adicionadas por meio de um processo de filtragem. Assim, o resultado do último leveling é melhorado quando se filtram os resíduos ri
extraídos de regiões indesejáveis, como pode ser observado na Figura 7.6, a qual exemplifica o cálculo do último leveling somente dos i-ésimos resíduos ri que satisfazem um critério de filtragem
Ω :P(D) → {verdadeiro, falso}.
ψ0(f ) ψ1(f ) ψ2(f ) ... ... ψIM AX−1(f ) ψIM AX(f )
r1(f ) r2(f ) r3(f ) ... rIM AX−2(f ) rIM AX−1(f )
filtrar os resíduos ri(f ) que não satisfazem Ω Rθ(f ) = sup{ri(f ) : ri(f ) satisfaz Ω}
Figura 7.6:Esquema para filtrar os i-ésimos resíduos ri extraídos de regiões indesejáveis.
Este procedimento de filtragem pode ser implementado de diversas maneiras, mas todas elas partem do mesmo princípio. Para decidir se um resíduo r+
i (f ) (respectivamente, ri−(f )) é filtrado
ou não filtrado, basta verificar se algum vértice C ∈ N r(i) satisfaz o critério de filtragem e assim os i-ésimos resíduos rΩ+
i (f ) e r Ω−
i (f ) podem ser redefinidos com o critério de filtragem Ω por
[riΩ+(f )](p) = r+Ti f (SC(Ti
f, p)), se SC(Tfi, p)∈ N r(i) e ∃C ∈ N r(i), Ω(C) é falso,
7.2 ESTRATÉGIAS PARA FILTRAR RESÍDUOS INDESEJÁVEIS 91 [rΩ−i (f )](p) = r−Ti f (SC(Ti
f, p)), se SC(Tfi, p)∈ N r(i) e ∃C ∈ N r(i), Ω(C) é falso,
0, caso contrário, (7.2)
e consequentemente, os últimos levelings com critério de filtragem Ω podem ser redefinidos como R+Ω(f ) = supi∈I{rΩ+i (f )}, R−Ω(f ) = supi∈I{rΩ−i (f )} e RΩ(f ) =R+Ω(f )∨ R−Ω(f ). (7.3)
A seguir, são apresentadas duas estratégias de filtragens de resíduos indesejáveis. Uma com base em um vetor de atributos (Urbach et al.,2007,2005) similar ao trabalho deHernandez e Marcotegui
(2011) e a outra baseada em regiões estáveis (Matas et al.,2004). 7.2.1 Filtragem com base em vetor de atributos
O reconhecimento de formas é um dos problemas fundamentais na área de análise de imagens e diversas abordagens têm sido propostas ao longo dos últimos anos. Um dos subproblemas de re- conhecimento de formas, denominado problema de decisão (Veltkamp e Hagedoorn,2000), consiste em comparar dois padrões A e B com uma medida de similaridade d por meio de um dado limiar α, ou seja, decidir se similaridade é maior do que o limiar. No contexto desta tese, os padrões são vetores de atributos extraídos dos vértices das árvores ou dos CCs dos conjunto de níveis (que podem estar saturados). Então, a medida de similaridade d é uma função definida como segue: Definição 7.1 (Medida de similaridade (Veltkamp,2001)). Uma medida de similaridade entre os padrões A e B em P(D), é definida por uma função d : P(D) × P(D) → [0, 1] ∈ R verificando as seguinte condições:
1. Identidade: d(A, A) = 1;
2. Unicidade: d(A, B) = 1 implica em A = B; 3. Simétrica: d(A, B) = d(B, A).
Assim, pretende-se construir um classificador Ω para decidir os rótulos (filtrar ou não filtrar) para os vértice de N r(i), de acordo com um determinado critério construído por uma medida de similaridade entre a forma representada por um vértice e uma forma de um padrão de referência Ωref ∈ P(D). Desse modo, o classificador é construído para todo vértice C ∈ P(D) da seguinte
forma:
Ω(C) = (
filtrar, se d(C, Ωref)≤ α,
não filtrar, caso contrário, (7.4)
Uma forma simples de construir Ω é por meio dos tradicionais descritores sobre a geometria do CC (área, largura, altura, perímetro, etc) e as suas relações (circularidade, retangularidade, momentos, etc). Por exemplo:
• Classificar vértices com formatos retangulares
Ωretangularidade(C) =
não filtrar, , se LarguraÁrea(C)
θ(C)×Alturaθ(C) ≤ α,
92 ESTRATÉGIAS PARA CONSTRUÇÕES DE ÚLTIMOS LEVELINGS 7.2 onde Área(C) é a área de C, Larguraθ(C) e Alturaθ(C) são as medidas de largura e a altura
do retângulo envolvente sobre C rotacionado na direção do maior eixo. • Classificar vértices com formatos circulares
Ωcircularidade(C) =
não filtrar, , se 4πPerímetroÁrea(C)
(C)2 ≤ α,
filtrar, , caso contrário, onde Área(C) é a área do CC C e Perímetro(C) é o perímetro do CC C. • Classificar vértices com formatos de estruturas alongadas.
Ωalongamento(C) =
não filtrar, , se Área(C)
π×Maior eixo(C)2 ≤ α,
filtrar, , caso contrário.
onde Área(C) é a área do CC C e Maior eixo(C) é o comprimento do maior eixo de C (Xu et al.
,2013).
Além disso, outros descritores de formas mais complexos, tais como shape context, casamento de template, modelos deformáveis, entre outros podem ser utilizados. Apesar de todas estas possi- bilidades para filtrar resíduos indesejáveis durante o processo de extração de resíduos. No entanto, é necessário ter cuidado com a escolha destes descritores para preservar as propriedades de inva- riâncias (translação, rotação e escala) dos últimos levelings. Além disso, dependendo da aplicação pode ser que o tempo computacional seja relevante, neste caso, é melhor dar preferência aos des- critores computáveis incrementalmente na árvore (Matas e Zimmermann, 2005). Estes descritores referem-se aos atributos que podem ser computados por meio dos atributos dos seus filhos e o con- junto de pixels canônicos presentes nos vértices. Em outras palavras, não é necessário reconstruir o CC representado pelo vértice para fazer a computação do atributo. Um procedimento simples (ver Algoritmo7.3), para fazer esta computação é por meio de um percurso em profundidade, em que ao visitar um vértice em pré-ordem pode-se inicializar o seu atributo e em uma visita em pós-ordem pode-se atualizar o seu atributo com os atributos dos seus filhos já computados anteriormente.