Vizinhanças

Template Unitário

Template unitário

Um template $ \mathbf{t} \in (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} $ definido de modo que para cada $ \mathbf{y} \in \mathbf{Y} $ todos os valores no suporte de $ \mathbf{t}_{\mathbf{y}} $ correspondem à unidade para a operação em $ \mathbb{F} $ é chamado de template unitário.

Vizinhança de Moore

Por exemplo, o template invariante abaixo (chamado de Moore) $ \mathbf{t} \in (\mathbb{R}^{\mathbb{Z}^2})^{\mathbb{Z}^2} $ é unitário em relação a $ \mathbb{R}, +, \cdot $ já que 1 é o elemento unitário da multiplicação.

\[ \mathbf{t} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & \boxed{1} & 1 \\ 1 & 1 & 1 \end{bmatrix} \]

Vizinhança de Von Neumann

Já o template $ \mathbf{r} \in (\mathbb{R}^{\mathbb{Z}^2}_{-\infty})^{\mathbb{Z}^2} $ a seguir (chamado template de Von Neumann) é unitário em relação a $ (\mathbb{R}_{-\infty}, \vee, +) $, já que 0 é unitário em relação a +.

\[ \mathbf{t} = \begin{bmatrix} & 0 & \\ 0 & \boxed{0} & 0 \\ & 0 & \end{bmatrix} \]

Aplicação: Soma de Vizinhança

Soma de vizinhança

Se $ \mathbf{X} \subset \mathbb{Z}^2 $ é uma matriz de $ m \times n $ pontos, $ \mathbf{a} \in \mathbb{R}^{\mathbf{X}} $ e $ \mathbf{t} \in (\mathbb{R}^{\mathbb{Z}^2})^{\mathbb{Z}^2} $ é um template de Moore $ 3 \times 3 $, então a imagem b obtida pela operação $ \mathbf{b} := \mathbf{a} \oplus \mathbf{t} $ é dada por:

\[ \mathbf{b}(\mathbf{y}) = \sum_{\mathbf{x} \in \mathbf{X} \cap S(\mathbf{t}_{\mathbf{y}})} \mathbf{a}(\mathbf{x}) \cdot \mathbf{t}_{\mathbf{y}}(\mathbf{x}) = \sum_{\mathbf{x} \in \mathbf{X} \cap S(\mathbf{t}(\mathbf{y}))} \mathbf{a}(\mathbf{x}) \cdot 1 \]

Igualdade vs. Atribuição

Aqui precisamos enfatizar a diferença entre a igualdade matemática $ \mathbf{b} = \mathbf{a} \oplus \mathbf{t} $ e a atribuição $ \mathbf{b} := \mathbf{a} \oplus \mathbf{t} $. Esta última realiza cálculos apenas em pontos $ \mathbf{y} $ para os quais $ \mathbf{X} \cap S(\mathbf{t}_{\mathbf{y}}) \neq \emptyset $ (suporte).

Podemos também escrever a expressão acima como:

\[ \mathbf{b}(\mathbf{y}) = \sum_{\mathbf{x} \in \mathbf{X} \cap M(\mathbf{y})} \mathbf{a}(\mathbf{x}) \]

em que $ M(\mathbf{y}) $ é a vizinhança de Moore de $ \mathbf{y} $. Isso nos leva ao conceito de redução de vizinhança.

Redução de Vizinhança

Redução de vizinhança

Dada a operação binária $ \gamma $ em $ \mathbb{F} $ podemos definir a redução de vizinhança:

\[ \Gamma : \mathbb{F}^{\mathbf{X}}|_N \rightarrow \mathbb{F} \]

em que $ N \in (2^{\mathbf{X}})^{\mathbf{Y}} $ é a função de vizinhança e $ \mathbb{F}^{\mathbf{X}}|_N = \{\mathbf{a}|_{N(\mathbf{y})} : \mathbf{a} \in \mathbb{F}^{\mathbf{X}}, \mathbf{y} \in \mathbf{Y}\} $.

Exemplo: Soma de Vizinhança

Por exemplo, se $ \mathbb{F}^{\mathbf{X}} = \mathbb{R}^{\mathbf{X}} $, $ \mathbf{X} \subset \mathbf{Z} $ é uma grade de $ m \times n $ pontos e $ N \in (2^{\mathbf{X}})^{(\mathbb{Z}^2)} $, então a partir da função $ \Sigma : \mathbb{R}^{\mathbf{X}}_N \rightarrow \mathbb{R} $ definimos:

\[ \sum(\mathbf{a}|_{N(y)}) = \sum_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) \]

Média de Vizinhança

ou ainda a média de vizinhança por:

\[ \Gamma(\mathbf{a}|_{N(y)}) = \frac{1}{\text{card}(N(\mathbf{y}))} \sum_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) \]

Convolução Imagem-Vizinhança

Convolução imagem-vizinhança

Seja agora $ \mathbf{X} \subset \mathbb{Z} $, $ \mathbf{t} \in (\mathbb{F}^{\mathbf{Z}})^{\mathbf{Y}} $ um template unitário em relação a $ \circ $ no semianel $ (\mathbb{F}, \gamma, \circ) $, $ N : \mathbf{Y} \rightarrow 2^{\mathbf{Z}} $ uma vizinhança definida por $ N(\mathbf{y}) = S(\mathbf{t}_{\mathbf{y}}) $ e $ \mathbf{a} \in \mathbb{F}^{\mathbf{X}} $.

Segue então que $ \mathbf{b} := \mathbf{a} \textcircled{$\gamma$} \mathbf{t} $ se define por:

\[ \mathbf{b}(\mathbf{y}) = \Gamma_{\mathbf{x} \in \mathbf{X} \cap S(\mathbf{t}_{\mathbf{y}})}(\mathbf{a}(\mathbf{x}) \circ \mathbf{t}_{\mathbf{y}}(\mathbf{x})) = \Gamma_{\mathbf{x} \in \mathbf{X} \cap N(\mathbf{y})} \mathbf{a}(\mathbf{x}) \]

Produto de Convolução Imagem-Vizinhança

Com base nisso, se $ \mathbf{X} \subset \mathbf{Z} $, $ \mathbf{a} \in \mathbb{F}^{\mathbf{X}} $, $ N : \mathbf{Y} \rightarrow 2^{\mathbf{Z}} $ é uma vizinhança (ou seja, $ N \in (2^{\mathbf{Z}})^{\mathbf{Y}} $), e $ \Gamma : \mathbb{F}^{\mathbf{X}}_N \rightarrow \mathbb{F} $ é uma função de redução, então definimos o produto de convolução imagem-vizinhança $ \mathbf{b} := \mathbf{a} \textcircled{$\Gamma$} N $ por:

\[ \mathbf{b}(\mathbf{y}) = \Gamma(\mathbf{a}|_{\mathbf{X} \cap N(\mathbf{y})}), \quad \forall \mathbf{y} \in \mathbf{Y} \]

Equivalência Template-Vizinhança

Equivalência

Se $ \mathbf{a} \in \mathbb{R}^{\mathbf{X}} $, $ M : \mathbb{Z}^2 \rightarrow \mathbb{Z}^2 $ é a vizinhança de Moore e $ \mathbf{t} \in (\mathbb{R}^2)^{(\mathbb{R}^2)} $ é o template $ 3 \times 3 $ unitário na multiplicação já apresentado, então:

\[ \mathbf{a} \oplus \mathbf{t} = \mathbf{a} \oplus M \]

Vizinhança de Von Neumann

Similarmente se $ \mathbf{r} \in (\mathbb{Z}^2_{-\infty})^{(\mathbb{Z}^2)} $ é o template de Von Neumann unitário na soma e $ N $ é a vizinhança de Von Neumann, então:

\[ \mathbf{a} \boxed{\vee} \mathbf{r} = \mathbf{a} \boxed{\vee} N \]

Fórmula Geral

Em geral, para todo $ \mathbf{x} \in \mathbf{X} \cap S_{-\infty}(\mathbf{r}_{\mathbf{y}}) $:

\[ \mathbf{b}(\mathbf{y}) = \bigvee_{\mathbf{x} \in \mathbf{X} \cap S_{-\infty}(\mathbf{r}_{\mathbf{y}})} \mathbf{a}(\mathbf{x}) + \mathbf{r}_{\mathbf{y}}(\mathbf{x}) = \bigvee_{\mathbf{x} \in \mathbf{X} \cap N(\mathbf{y})} \mathbf{a}(\mathbf{x}) = \mathbf{c}(\mathbf{y}) \]

Resumo

Conceito	Definição
Template unitário	Todos os valores no suporte são a unidade da operação
Vizinhança de Moore	3×3, pesos = 1, unitário para multiplicação
Vizinhança de Von Neumann	Cruz, pesos = 0, unitário para soma
Redução de vizinhança	( \Gamma : \mathbb{F}^{\mathbf{X}}
Média de vizinhança	$ \frac{1}{\text{card}(N(\mathbf{y}))} \sum_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) $
Produto imagem-vizinhança	( \mathbf{b}(\mathbf{y}) = \Gamma(\mathbf{a}

Aplicação Prática

Templates unitários permitem simplificar a notação usando vizinhanças em vez de templates completos. Isso é especialmente útil em operações como filtros de média, dilatação e erosão morfológica.

Função Característica

Função característica

Note que em geral templates unitários agem como uma função característica, já que eles não atribuem pesos aos pixels, mas simplesmente informam quais pixels estão no suporte do template e quais não.

Tratamento de Bordas

Além de ser uma alternativa mais simples à operação de template, quando cabível, é no tratamento nas bordas de uma imagem. Lá o uso de um template $ \mathbf{t} $ $ 3 \times 3 $ de Moore para a média local seria:

\[ \mathbf{b} := \frac{1}{9}(\mathbf{a} \oplus \mathbf{b}) \]

No ponto $ (1, 1) $ teríamos:

\[ \mathbf{b}(1, 1) = \frac{1}{9}(\mathbf{a}(1, 1) + \mathbf{a}(1, 2) + \mathbf{a}(2, 1) + \mathbf{a}(2, 2)) \]

que obviamente não é a média correta. O uso de uma função $ m $ de média e a operação induzida na vizinhança $ \mathbf{a} \textcircled{$m$} M $ resolveria a questão com elegância.

Dilatação entre Vizinhanças

Dilatação

Outra operação interessante é a dilatação entre vizinhanças. Dadas duas funções de vizinhança $ N_1, N_2 : \mathbb{R}^n \rightarrow 2^{\mathbb{R}^n} $, a dilatação de $ N_1 $ por $ N_2 $, denotada $ N_1 \oplus N_2 $ é dada por:

\[ N(\mathbf{y}) = \bigcup_{\mathbf{p} \in N_2(\mathbf{y})} (N_1(\mathbf{y}) + (\mathbf{p} - \mathbf{y})) \]

em que $ N(\mathbf{y}) + \mathbf{q} \equiv \{\mathbf{x} + \mathbf{q} : \mathbf{x} \in N(\mathbf{y})\} $.

Exemplo: Moore ⊕ Von Neumann

Por exemplo, seja $ N_1 $ a vizinhança de Moore e $ N_2 $ a de Von Neumann, ambas em $ \mathbb{Z}^2 $ em torno de $ (0, 0) $. Vamos dividir em partes, começando por $ (-1, -1) \in N_1(\mathbf{y}) $:

[ N(0, 0)_{(-1,-1)} = {(-1, -1) + (-1, 0) - (0, 0), (-1, -1) + (0, -1) - (0, 0), ] [ (-1, -1) + (0, 1) - (0, 0), (-1, -1) + (1, 0) - (0, 0)} = ] [ {(-2, -1), (-1, -2), (-1, 0), (0, -1)} ]

Visualização da Dilatação

Visualização

Vamos ilustrar também para $ (1, 0) \in N_1(\mathbf{y}) $:

[ N(0, 0)_{(1,0)} = {(1, 0) + (-1, 0) - (0, 0), (1, 0) + (0, -1) - (0, 0), ] [ (1, 0) + (0, 1) - (0, 0), (1, 0) + (1, 0) - (0, 0)} = ] [ {(0, 0), (1, -1), (1, 1), (2, 0)} ]

A figura abaixo mostra a vizinhança resultante:


		■
	■	■	■
■	■	■	■	■
	■	■	■
		■

Iteração de Vizinhança

Iteração

Para $ k \in \mathbb{N} $ definimos também a k-ésima iteração da vizinhança $ N : \mathbb{R}^n \rightarrow 2^{\mathbb{R}^n} $ indutivamente por:

\[ N^k = N^{k-1} \oplus N \]

dado que $ N_0(\mathbf{y}) = \{\mathbf{y}\}, \forall \mathbf{y} \in \mathbb{R}^n $.

Invariância a Translação

Uma função de vizinhança $ N : \mathbb{R}^n \rightarrow 2^{\mathbb{R}^n} $ é invariante a translação se:

\[ N(\mathbf{y} + \mathbf{p}) = N(\mathbf{y}) + \mathbf{p}, \quad \forall \mathbf{p} \in \mathbb{R}^n \]

Reflexão (Conjugado)

Se a vizinhança $ N $ é invariante a translação, então definimos a reflexão ou conjugado $ N^* $ por:

\[ N^*(\mathbf{y}) = N^*(\mathbf{0}) + \mathbf{y} \]

em que $ N^*(\mathbf{0}) = \{-\mathbf{x} : \mathbf{x} \in N(\mathbf{0})\} $, sendo $ \mathbf{0} = (0, 0, \ldots, 0) \in \mathbb{R}^n $.

Exemplo: Vizinhança Não-Simétrica

Não-simétrica

Por exemplo, para a vizinhança não-simétrica abaixo temos o conjugado na figura:

Vizinhança Original


-1,-1	-1,0
0,-1	0,0	0,1
	1,0	1,2

Conjugado (Reflexão)


-1,-2		-1,0
0,-1	0,0	0,1
	1,0	1,1
0,-2

Simetria

Para vizinhanças simétricas (como Moore e Von Neumann), o conjugado é igual à vizinhança original: $ N^* = N $.

Resumo das Operações de Vizinhança

Resumo

Podemos finalmente resumir as operações de vizinhança:

Vizinhança Reduzida Genérica

\[ \mathbf{a} \textcircled{$\Gamma$} N = \{(\mathbf{y}, \mathbf{b}(\mathbf{y})) : \mathbf{b}(\mathbf{y}) = \Gamma(\mathbf{a}|_{N(\mathbf{y})}), \mathbf{y} \in \mathbf{Y}\} \]

Soma de Vizinhança

\[ \mathbf{a} \oplus N = \{(\mathbf{y}, \mathbf{b}(\mathbf{y})) : \mathbf{b}(\mathbf{y}) = \sum_{\mathbf{x} \in \mathbf{X} \cap N(\mathbf{y})} \mathbf{a}(\mathbf{x}), \mathbf{y} \in \mathbf{Y}\} \]

Máximo de Vizinhança

\[ \mathbf{a} \boxed{\vee} N = \{(\mathbf{y}, \mathbf{b}(\mathbf{y})) : \mathbf{b}(\mathbf{y}) = \bigvee_{\mathbf{x} \in \mathbf{X} \cap N(\mathbf{y})} \mathbf{a}(\mathbf{x}), \mathbf{y} \in \mathbf{Y}\} \]

Mínimo de Vizinhança

\[ \mathbf{a} \boxed{\wedge} N = \{(\mathbf{y}, \mathbf{b}(\mathbf{y})) : \mathbf{b}(\mathbf{y}) = \bigwedge_{\mathbf{x} \in \mathbf{X} \cap N(\mathbf{y})} \mathbf{a}(\mathbf{x}), \mathbf{y} \in \mathbf{Y}\} \]

Equivalência Morfológica

Equivalência

Vale notar que neste caso o máximo e mínimo simples e suas versões morfológicas coincidem, isto é:

\[ \mathbf{a} \textcircled{$\vee$} N = \mathbf{a} \boxed{\vee} N \quad \text{e} \quad \mathbf{a} \textcircled{$\wedge$} N = \mathbf{a} \boxed{\wedge} N \]

Nota

Esta equivalência ocorre porque em vizinhanças unitárias os pesos são todos iguais à unidade da operação, então a operação morfológica (soma + max) se reduz apenas ao max.

Tabela Final de Operações

Operação	Notação	Fórmula
Redução genérica	$ \mathbf{a} \textcircled{$\Gamma$} N $	( \Gamma(\mathbf{a}
Soma	$ \mathbf{a} \oplus N $	$ \sum_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) $
Máximo	$ \mathbf{a} \boxed{\vee} N $	$ \bigvee_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) $
Mínimo	$ \mathbf{a} \boxed{\wedge} N $	$ \bigwedge_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) $
Dilatação	$ N_1 \oplus N_2 $	$ \bigcup_{\mathbf{p} \in N_2} (N_1 + (\mathbf{p} - \mathbf{y})) $
Iteração	$ N^k $	$ N^{k-1} \oplus N $
Reflexão	$ N^* $	$ \{-\mathbf{x} : \mathbf{x} \in N(\mathbf{0})\} + \mathbf{y} $

Operação	Notação	Fórmula
Redução genérica	\( \mathbf{a} \textcircled{$\Gamma$} N \)	( \Gamma(\mathbf{a}
Soma	\( \mathbf{a} \oplus N \)	\( \sum_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) \)
Máximo	\( \mathbf{a} \boxed{\vee} N \)	\( \bigvee_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) \)
Mínimo	\( \mathbf{a} \boxed{\wedge} N \)	\( \bigwedge_{\mathbf{x} \in N(\mathbf{y})} \mathbf{a}(\mathbf{x}) \)
Dilatação	\( N_1 \oplus N_2 \)	\( \bigcup_{\mathbf{p} \in N_2} (N_1 + (\mathbf{p} - \mathbf{y})) \)
Iteração	\( N^k \)	\( N^{k-1} \oplus N \)
Reflexão	\( N^* \)	\( \{-\mathbf{x} : \mathbf{x} \in N(\mathbf{0})\} + \mathbf{y} \)