Produto Imagem-Template
Introdução
Vamos tratar agora de operações que combinam imagens com templates e templates com templates, como correlação e convolução.
Definições Preliminares
Operações Binárias
Sejam \( \gamma \) e \( \circ \) duas operações binárias em \( \mathbb{F} \), sendo que:
- \( \gamma \) é associativa e comutativa
- \( \circ \) distribui sobre \( \gamma \)
Template e Imagem
Seja então o template \( \mathbf{t} \in (\mathbb{F}^{\mathbf{X}})^{\mathbf{Y}} \), i.e., para cada \( \mathbf{y} \in \mathbf{Y} \), \( \mathbf{t}_{\mathbf{y}} \in \mathbb{F}^{\mathbf{X}} \).
Seja ainda a imagem \( \mathbf{a} \in \mathbb{F}^{\mathbf{X}} \), com \( \mathbf{X} \) finito.
Operação Produto
Para cada \( \mathbf{y} \), podemos operar:
E ainda fazer a operação de redução global induzida por \( \gamma \):
Operação Binária Induzida
Chegamos assim à seguinte operação binária induzida:
expressa por:
definida por:
Convolução
Se \( \mathbf{X} = \{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\} \):
expressão esta chamada de convolução à direita de \( \mathbf{a} \) com \( \mathbf{t} \).
Mudança de Domínio
Note que o domínio da imagem de saída é \( \mathbf{Y} \) e não mais \( \mathbf{X} \) como na original.
Produto Linear Imagem-Template
Se o grupo \( (\mathbb{F}, \gamma, \circ) \) em questão for \( (\mathbb{R}, +, \cdot) \), então:
é o chamado produto linear imagem-template ou simplesmente convolução de \( \mathbf{a} \) com \( \mathbf{t} \), tal que:
Resumo
| Conceito | Definição |
|---|---|
| Operação genérica | \( \mathbf{b}(\mathbf{y}) = \Gamma_{\mathbf{x}}[\mathbf{a}(\mathbf{x}) \circ \mathbf{t}_{\mathbf{y}}(\mathbf{x})] \) |
| Convolução | Caso especial com \( (\mathbb{R}, +, \cdot) \) |
| Fórmula da convolução | \( \mathbf{b}(\mathbf{y}) = \sum_{\mathbf{x}} \mathbf{a}(\mathbf{x}) \cdot \mathbf{t}_{\mathbf{y}}(\mathbf{x}) \) |
| Domínio de saída | \( \mathbf{Y} \) (não \( \mathbf{X} \)) |
Template Transposto
Um template \( \mathbf{s} \in (\mathbb{F}^{\mathbf{Y}})^{\mathbf{X}} \) tem seu transposto \( \mathbf{s}' \) definido por:
Exemplo (Invariante a Escala)
Considere um template onde os pesos originais são:
| Pesos originais | ||
|---|---|---|
| \( \mathbf{t}_{(1,1)}(1, 1) = 1 \) | \( \mathbf{t}_{(1,1)}(1, 2) = 2 \) | \( \mathbf{t}_{(1,1)}(2, 1) = 3 \) |
| \( \mathbf{t}_{(1,2)}(1, 2) = 1 \) | \( \mathbf{t}_{(1,2)}(1, 3) = 2 \) | \( \mathbf{t}_{(1,2)}(2, 2) = 3 \) |
| \( \mathbf{t}_{(2,1)}(2, 1) = 1 \) | \( \mathbf{t}_{(2,1)}(2, 2) = 2 \) | \( \mathbf{t}_{(2,1)}(3, 1) = 3 \) |
| \( \mathbf{t}_{(2,2)}(2, 2) = 1 \) | \( \mathbf{t}_{(2,2)}(2, 3) = 2 \) | \( \mathbf{t}_{(2,2)}(3, 2) = 3 \) |
Transposto
| Pesos transpostos | ||
|---|---|---|
| \( \mathbf{t}_{(1,1)}(1, 1) = 1 \) | \( \mathbf{t}_{(1,2)}(1, 1) = 2 \) | \( \mathbf{t}_{(2,1)}(1, 1) = 3 \) |
| \( \mathbf{t}_{(1,2)}(1, 2) = 1 \) | \( \mathbf{t}_{(1,3)}(1, 2) = 2 \) | \( \mathbf{t}_{(2,2)}(1, 2) = 3 \) |
| \( \mathbf{t}_{(2,1)}(2, 1) = 1 \) | \( \mathbf{t}_{(2,2)}(2, 1) = 2 \) | \( \mathbf{t}_{(3,1)}(2, 1) = 3 \) |
| \( \mathbf{t}_{(2,2)}(2, 2) = 1 \) | \( \mathbf{t}_{(2,3)}(2, 2) = 2 \) | \( \mathbf{t}_{(3,2)}(2, 2) = 3 \) |
Convolução à Esquerda
Assim, \( \mathbf{s}'_{\mathbf{y}} \circ \mathbf{a} \in \mathbb{F}^{\mathbf{X}} \) e \( \Gamma(\mathbf{s}'_{\mathbf{y}}(\mathbf{a})) \in \mathbb{F} \) gerando a operação induzida:
sendo:
definida por:
\( \mathbf{s} \textcircled{$\gamma$} \mathbf{a} \) é o produto de convolução à esquerda de \( \mathbf{a} \) com \( \mathbf{s} \).
Também pode ser escrito sem usar transposto:
Extensão com Monoides
Seja agora \( (\mathbb{F}, \gamma) \) um monoide: operação binária associativa \( \gamma \) com um elemento identidade denotado por 0.
Seja a imagem \( \mathbf{a} \in \mathbb{F}^{\mathbf{X}} \) e o template \( \mathbf{t} \in (\mathbb{F}^{\mathbf{Z}})^{\mathbf{Y}} \), em que \( \mathbf{X} \) e \( \mathbf{Z} \) são subconjuntos do mesmo espaço.
Como \( \mathbb{F} \) é monoide podemos estender o operador \( \textcircled{$\gamma$} \):
em que \( \mathbf{b} = \mathbf{a} \textcircled{$\gamma$} \mathbf{t} \) é definido por:
Otimização Computacional
Semelhantemente, podemos reduzir cálculos computacionais nestas operações se \( (\mathbb{F}, \gamma, \circ) \) for um semi-anel comutativo (não exige inverso aditivo para todos os elementos).
Recordando a noção de suporte de um template podemos escrever:
Complexidade
Isto implica que o cálculo do novo valor para o pixel \( \mathbf{b}(\mathbf{y}) \) não depende do tamanho de \( \mathbf{X} \), mas sim de \( S(\mathbf{t}_{\mathbf{y}}) \).
Se \( k = \text{card}(\mathbf{X} \cap S(\mathbf{t}_{\mathbf{y}})) \), então o cálculo de \( \mathbf{b}(\mathbf{y}) \) envolve \( 2k - 1 \) operações de \( \gamma \) e \( \circ \).
Variedade de Transformações
A substituição de \( (\mathbb{F}, \gamma, \circ) \) por diferentes conjuntos de valores e operações binárias gera uma grande variedade de transformações de imagens.
Operadores Morfológicos
Estrutura
O anel \( (\mathbb{R}, +, \cdot) \) se generaliza para a estrutura \( (\mathbb{R}_{\pm\infty}, \vee, \wedge, +, +') \) gerando os dois produtos de reticulados seguintes.
Operador de Convolução Max Morfológico
em que:
Operador de Convolução Min Morfológico
em que:
Operações Morfológicas à Esquerda
Temos ainda as operações max e min morfológicos à esquerda:
Dualidade
Estas operações se relacionam por dualidade:
Máximo e Mínimo Multiplicativo
A estrutura \( (\mathbb{R}^{\geq 0}_{\infty}, \vee, \wedge, \times, \times') \) também provê operações correspondentes, chamadas de máximo e mínimo multiplicativo:
Máximo Multiplicativo
em que:
Mínimo Multiplicativo
em que:
Multiplicativo à Esquerda
Temos também o max e min multiplicativo à esquerda:
Dualidade
as quais se relacionam por dualidade:
em que \( r^* \) é o conjugado de \( r \) em \( \mathbb{R}^{\geq 0}_{\infty} \).