Template Transposto

Operações Binárias em Templates

Operações binárias

Qualquer operação binária $ \gamma $ em $ \mathbb{F} $ induz uma operação em $ (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} $ de modo que se $ \mathbf{s}, \mathbf{t} \in (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} $, então:

\[ (\mathbf{s} \gamma \mathbf{t})_{\mathbf{y}} \equiv \mathbf{s}_{\mathbf{y}} \gamma \mathbf{t}_{\mathbf{y}}, \quad \forall \mathbf{y} \in \mathbf{Y} \]

Exemplo com Soma

Por exemplo, se $ \mathbb{F} = \mathbb{R} $, $ \mathbf{s}, \mathbf{t} \in (\mathbb{R}^{\mathbf{X}})^{\mathbf{Y}} $ e $ \gamma = + $:

\[ (\mathbf{s} + \mathbf{t})_{\mathbf{y}} = \mathbf{s}_{\mathbf{y}} + \mathbf{t}_{\mathbf{y}} \]

ou seja, a operação corresponde à soma pontual entre as imagens $ \mathbf{s}_{\mathbf{y}} \in \mathbb{R}^{\mathbf{X}} $ e $ \mathbf{t}_{\mathbf{y}} \in \mathbb{R}^{\mathbf{X}} $.

Operações Unárias: Redução Global

Já entre as operações unárias temos a redução global. Se $ \mathbf{Y} = \{\mathbf{y}_1, \ldots, \mathbf{y}_n\} $ é um conjunto finito de pontos e $ \mathbf{t} \in (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} $, então a operação $ \gamma $ em $ \mathbb{F} $ induz:

\[ \Gamma : (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} \rightarrow \mathbb{F}^{\mathbf{X}} \]

definida por:

\[ \Gamma \mathbf{t} = \Gamma_{\mathbf{y} \in \mathbf{Y}} \mathbf{t}_{\mathbf{y}} = \mathbf{t}_{\mathbf{y}_1} \gamma \ldots \gamma \mathbf{t}_{\mathbf{y}_n} \]

Exemplo: Soma de Imagens

Soma de imagens

Exemplificando com $ \mathbb{F} = \mathbb{R} $ e $ \gamma = + $ temos:

\[ \sum \mathbf{t} = \mathbf{t}_{\mathbf{y}_1} + \cdots + \mathbf{t}_{\mathbf{y}_n} \]

correspondendo à soma de um número finito de imagens.

Produto de Convolução entre Templates

Convolução entre templates

Já no caso em que temos $ (\mathbb{F}, \gamma, \circ) $ como um anel (ou semi-anel) podemos definir o produto de convolução entre templates:

\[ \textcircled{$\gamma$} : (\mathbb{F}^{\mathbf{Z}})^{\mathbf{X}} \times (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} \rightarrow (\mathbf{F}^{\mathbf{Z}})^{\mathbf{Y}} \]

definida de modo que dado $ \mathbf{s} \in (\mathbb{F}^{\mathbf{Z}})^{\mathbf{X}} $, $ \mathbf{t} \in (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} $ e $ \mathbf{X} $ um conjunto finito de pontos, então $ \mathbf{r} = \mathbf{s} \textcircled{$\gamma$} \mathbf{t} $ é definido por:

\[ \mathbf{r}_{\mathbf{y}}(\mathbf{z}) = \Gamma_{\mathbf{x} \in \mathbf{X}}(\mathbf{s}_{\mathbf{x}}(\mathbf{z}) \circ \mathbf{t}_{\mathbf{y}}(\mathbf{x})), \quad \forall \mathbf{y} \in \mathbf{Y} \text{ e } \forall \mathbf{z} \in \mathbf{Z} \]

Caso Linear

No exemplo em que $ \mathbb{F} = \mathbb{R} $, temos $ \mathbf{r} = \mathbf{s} \oplus \mathbf{t} $ dada por:

\[ \mathbf{r}_{\mathbf{y}}(\mathbf{z}) = \sum_{\mathbf{x} \in \mathbf{X}} \mathbf{s}_{\mathbf{x}}(\mathbf{z}) \cdot \mathbf{t}_{\mathbf{y}}(\mathbf{x}) \]

Caso Max Morfológico

O produto de reticulado $ \mathbf{r} = \mathbf{s} \boxed{\vee} \mathbf{t} $ se define similarmente para $ \mathbf{s} \in (\mathbb{R}^{\mathbf{Z}}_{\pm\infty})^{\mathbf{X}} $ e $ \mathbf{t} \in (\mathbb{R}^{\mathbf{X}}_{\pm\infty})^{\mathbf{Y}} $:

\[ \mathbf{r}_{\mathbf{y}}(\mathbf{z}) = \bigvee_{\mathbf{x} \in \mathbf{X}} [\mathbf{s}_{\mathbf{x}}(\mathbf{z}) + \mathbf{t}_{\mathbf{y}}(\mathbf{x})] \]

Exemplo: Produto entre Templates

Exemplo produto

Exemplos: Sejam $ \mathbf{s}, \mathbf{t} \in (\mathbb{R}^{\mathbb{Z}^2})^{\mathbb{Z}^2} $ com valores:

Templates

\[ \mathbf{s}_{\mathbf{y}} = \begin{bmatrix} 1 & \underline{2} & 1 \end{bmatrix} \qquad \mathbf{t}_{\mathbf{y}} = \begin{bmatrix} 1 \\ \underline{3} \\ -1 \end{bmatrix} \]

(valores sublinhados indicam o pixel central)

Vamos calcular o produto $ \mathbf{r} = \mathbf{s} \oplus \mathbf{t} $ lembrando que:

\[ \mathbf{r}_{\mathbf{y}}(\mathbf{z}) = \sum_{\mathbf{x} \in \mathbf{X}} \mathbf{s}_{\mathbf{x}}(\mathbf{z}) \cdot \mathbf{t}_{\mathbf{y}}(\mathbf{x}) \]

Cálculo de $ r_{(2,2)}(1, 1) $

[ r_{(2,2)}(1, 1) = s_{(1,1)}(1, 1) \cdot t_{(2,2)}(1, 1) + s_{(1,2)}(1, 1) \cdot t_{(2,2)}(1, 2) + s_{(1,3)}(1, 1) \cdot t_{(2,2)}(1, 3) + ] [ s_{(2,1)}(1, 1) \cdot t_{(2,2)}(2, 1) + s_{(2,2)}(1, 1) \cdot t_{(2,2)}(2, 2) + s_{(2,3)}(1, 1) \cdot t_{(2,2)}(2, 3) + ] [ s_{(3,1)}(1, 1) \cdot t_{(2,2)}(3, 1) + s_{(3,2)}(1, 1) \cdot t_{(2,2)}(3, 2) + s_{(3,3)}(1, 1) \cdot t_{(2,2)}(3, 3) ] [ = 2 \cdot 0 + 1 \cdot 1 + 0 \cdot 0 + 0 \cdot 0 + 0 \cdot 3 + 0 \cdot 0 + 0 \cdot 0 + 0 \cdot (-1) + 0 \cdot 0 = 1 ]

Resultado do Produto

Resultado

Cálculo de $ r_{(2,2)}(2, 2) $

[ r_{(2,2)}(2, 2) = s_{(1,1)}(2, 2) \cdot t_{(2,2)}(1, 1) + s_{(1,2)}(2, 2) \cdot t_{(2,2)}(1, 2) + s_{(1,3)}(2, 2) \cdot t_{(2,2)}(1, 3) + ] [ s_{(2,1)}(2, 2) \cdot t_{(2,2)}(2, 1) + s_{(2,2)}(2, 2) \cdot t_{(2,2)}(2, 2) + s_{(2,3)}(2, 2) \cdot t_{(2,2)}(2, 3) + ] [ s_{(3,1)}(2, 2) \cdot t_{(2,2)}(3, 1) + s_{(3,2)}(2, 2) \cdot t_{(2,2)}(3, 2) + s_{(3,3)}(2, 2) \cdot t_{(2,2)}(3, 3) ] [ = 0 \cdot 0 + 0 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 + 2 \cdot 3 + 1 \cdot 0 + 0 \cdot 0 + 0 \cdot (-1) + 0 \cdot 0 = 6 ]

Resultado Final

No final o produto $ \mathbf{r} = \mathbf{s} \oplus \mathbf{t} $ será:

\[ \mathbf{r}_{\mathbf{y}} = \begin{bmatrix} 1 & 2 & 1 \\ 3 & \underline{6} & 3 \\ -1 & -2 & -1 \end{bmatrix} \]

Interpretação

O produto de convolução entre templates gera um novo template que combina as características de ambos. Neste exemplo, o template horizontal $ \mathbf{s} $ combinado com o template vertical $ \mathbf{t} $ produz um template 3×3.

Resumo

Conceito	Definição
Operação binária	$ (\mathbf{s} \gamma \mathbf{t})_{\mathbf{y}} = \mathbf{s}_{\mathbf{y}} \gamma \mathbf{t}_{\mathbf{y}} $
Redução global	$ \Gamma \mathbf{t} = \mathbf{t}_{\mathbf{y}_1} \gamma \ldots \gamma \mathbf{t}_{\mathbf{y}_n} $
Produto linear	$ \mathbf{r}_{\mathbf{y}}(\mathbf{z}) = \sum_{\mathbf{x}} \mathbf{s}_{\mathbf{x}}(\mathbf{z}) \cdot \mathbf{t}_{\mathbf{y}}(\mathbf{x}) $
Produto max	$ \mathbf{r}_{\mathbf{y}}(\mathbf{z}) = \bigvee_{\mathbf{x}} [\mathbf{s}_{\mathbf{x}}(\mathbf{z}) + \mathbf{t}_{\mathbf{y}}(\mathbf{x})] $

Exemplo: Produto Max Morfológico

Max morfológico

Já se $ \mathbf{s}, \mathbf{t} \in (\mathbb{R}^{\mathbb{Z}^2}_{\pm\infty})^{\mathbb{Z}^2} $ são definidos com $ -\infty $ fora do suporte, podemos obter o produto $ \mathbf{r} = \mathbf{s} \boxed{\vee} \mathbf{t} $:

\[ \mathbf{r}_{\mathbf{y}} = \begin{bmatrix} 2 & 3 & 2 \\ 4 & \underline{5} & 4 \\ 0 & 1 & 0 \end{bmatrix} \]

Associatividade e Separabilidade

Associatividade

Vamos agora redefinir $ \mathbf{t} $ para um template $ \mathbb{R}^{\geq 0}_{\infty} $-valorado:

\[ \mathbf{t}_{\mathbf{y}} = \begin{bmatrix} 1 \\ \underline{3} \\ 1 \end{bmatrix} \]

Assim podemos calcular $ \mathbf{r} = \mathbf{s} \boxed{\vee} \mathbf{t} $:

\[ \mathbf{r}_{\mathbf{y}} = \begin{bmatrix} 1 & 2 & 1 \\ 3 & \underline{6} & 3 \\ 1 & 2 & 1 \end{bmatrix} \]

Propriedade Fundamental

A grande utilidade de produtos de templates resulta da seguinte igualdade válida em semi-anéis:

\[ \mathbf{a} \gamma (\mathbf{s} \gamma \mathbf{t}) = (\mathbf{a} \gamma \mathbf{s}) \gamma \mathbf{t} \]

o que permite, por exemplo, transformar uma convolução bidimensional no produto de duas unidimensionais, e assim reduzir cálculos.

Exemplo: Templates Cruz

Templates cruz

Considere os templates a seguir:

Template s


	3
-1	2	1

Template t


	1
2	3	1
	-1

(Valores em negrito indicam o pixel central)

Soma de Templates

Soma

Vamos calcular a soma $ \mathbf{r} = \mathbf{s} + \mathbf{t} $ usando um sistema de coordenadas centrado no template:

$ \mathbf{r}_{(0,0)}(0, 0) = \mathbf{s}_{(0,0)}(0, 0) + \mathbf{t}_{(0,0)}(0, 0) = 2 + 3 = 5 $
$ \mathbf{r}_{(0,0)}(1, 0) = \mathbf{s}_{(0,0)}(1, 0) + \mathbf{t}_{(0,0)}(1, 0) = 0 + (-1) = -1 $
$ \mathbf{r}_{(0,0)}(-1, 0) = \mathbf{s}_{(0,0)}(-1, 0) + \mathbf{t}_{(0,0)}(-1, 0) = 3 + 1 = 4 $
$ \mathbf{r}_{(0,0)}(0, 1) = \mathbf{s}_{(0,0)}(0, 1) + \mathbf{t}_{(0,0)}(0, 1) = 1 + 1 = 2 $
$ \mathbf{r}_{(0,0)}(0, -1) = \mathbf{s}_{(0,0)}(0, -1) + \mathbf{t}_{(0,0)}(0, -1) = -1 + 2 = 1 $

Resultado da Soma


	4
1	5	2
	-1

Convolução de Templates Cruz

Convolução

Outra operação é a convolução $ \mathbf{r} = \mathbf{s} \oplus \mathbf{t} $:

Cálculos

r(0,0)(0, 0): [ \mathbf{r}{(0,0)}(0, 0) = \mathbf{s}}(0, 0) \cdot \mathbf{t{(0,0)}(0, 0) + \mathbf{s}}(0, 0) \cdot \mathbf{t{(0,0)}(1, 0) + ] [ \mathbf{s}}(0, 0) \cdot \mathbf{t{(0,0)}(0, -1) + \mathbf{s}(0, 1) ] [ = 6 - 3 + 2 - 1 = 4 ]}(0, 0) \cdot \mathbf{t}_{(0,0)

r(0,0)(1, 0): [ \mathbf{r}{(0,0)}(1, 0) = \mathbf{s}(1, 0) = -2 ]}(1, 0) \cdot \mathbf{t}_{(0,0)

r(0,0)(-1, 0): [ \mathbf{r}{(0,0)}(-1, 0) = \mathbf{s}}(-1, 0) \cdot \mathbf{t{(0,0)}(-1, 0) + \mathbf{s}(0, 0) = 2 + 9 = 11 ]}(-1, 0) \cdot \mathbf{t}_{(0,0)

r(0,0)(1, 1): [ \mathbf{r}{(0,0)}(1, 1) = \mathbf{s}(1, 0) = -1 ]}(1, 1) \cdot \mathbf{t}_{(0,0)

Resultado da Convolução


		3
	5	11	2
-2	1	4	5	1
	1	-2	-1

Expansão do Suporte

Note que a convolução de dois templates cruz resulta em um template com suporte expandido (5×5 em vez de 3×3 na soma).