Por que normalizar o conjunto de dados antes de aplicar a Transformação Linear Direta

9

A Transformação Linear Direta (DLT para abreviar) é um método de estimativa de homografia; resolve o sistema linear sobredeterminado via SVD para encontrar uma solução sob restrição . Na verdade, ele encontra a solução menos quadrada que minimiza \ | Ah - b \ | .

Ah=b
h‖h‖=1‖Ah−b‖

Entendo a idéia básica desse algoritmo, mas é recomendável normalizar o conjunto de dados antes de aplicar o DLT, e aqui está uma introdução sobre como fazer a normalização. É ensinado que a normalização de dados é importante para o DLT, sem normalização os resultados do DLT não são estáveis.

Eu quero saber porque? Só porque o DLT envolve resolver o sistema linear usando SVD e A pode ser singular?

image-processing homography normalization abacate
fonte

Respostas:

12

A normalização é basicamente um pré - condicionamento para diminuir o número de condições da matriz A (quanto maior o número de condições, mais próxima a matriz está da matriz singular).

A transformação de normalização também é representada por uma matriz no caso de estimativa de homografia, e isso pode ser usado como uma boa matriz de pré-condicionador. A razão pela qual isso é mais elaborado e é explicada brevemente no livro H&Z (4.4.4, p. 107: Por que a normalização é essencial? ) Ou em mais detalhes no artigo " Em Defesa do Algoritmo de Oito Pontos ".

Simplificando, a matriz consiste em produtos de coordenadas de imagem que podem ter diferentes escalas. Se a escala diferir por um fator de , os produtos diferem por um fator de .A10102

Os dados das coordenadas de origem e de destino geralmente são barulhentos . Sem normalização, os dados da origem podem ter duas ordens de magnitude de variação maior que a do destino (ou vice-versa).

A estimativa da homografia geralmente encontra parâmetros no sentido de mínimos quadrados - portanto, a melhor estimativa estatística é encontrada apenas se as variações dos parâmetros forem as mesmas (ou conhecidas de antemão, mas é mais prático apenas normalizar a entrada).

Os solucionadores diretos não gostam de problemas mal dimensionados porque aparecem instabilidades numéricas (por exemplo, dividir um número muito grande por um número muito pequeno leva facilmente ao estouro numérico).

Os solucionadores iterativos lutam com matrizes mal condicionadas, necessitando de mais iterações.

Portanto, a normalização é essencial não apenas para a estabilidade numérica, mas também para uma estimativa mais precisa na presença de ruído e solução mais rápida (no caso de solucionador iterativo).

Libor
fonte
E ainda me pergunto por que a matriz pré-condicionada é menos singular do que antes? Ao padronizar , o número de condição da matriz pré-condicionada reduzirá?
abacate
1
Porque os erros nos dados não afetarão tanto os resultados. Imagine estimar a posição do ponteiro do relógio em dois pontos no mostrador do relógio. Se um ponto estiver muito próximo do centro e o outro estiver na borda, as flutuações na posição do ponto próximo ao centro afetam significativamente o resultado, enquanto o ponto na borda afeta suavemente a posição da mão. A normalização é basicamente colocar os dois pontos na borda, o que torna a solução mais estável e a afasta do centro do mostrador do relógio (o ponto de singularidade).
Libor
2

O artigo da Wikipedia afirma:

"O que diferencia o problema da transformação linear direta. É o fato de que os lados esquerdo [X] e direito [AY] da equação definidora [X = AY] podem diferir por um fator multiplicativo desconhecido, dependente de k"

No X acima, A, Y são matrizes.

Portanto, para evitar a estimativa do fator, basta normalizar todos os dados que você possui.

Tom Kealy
fonte
Isso não parece certo ... Se pudéssemos normalizar para tornar o fator sem importância, o problema poderia ser resolvido usando o método regular de . A=XYT(YYT)−1
Michael Litvin
1

É uma questão de precisão numérica. Ao normalizar o conjunto de dados, você centraliza seus dados e fornece variação de unidade. Essas condições são melhor tratadas pelo solbver.

sansuiso
fonte
Por melhor tratado pelo solucionador , você quer dizer que quando eu resolver esse tipo de sistema linear via SVD , sempre devo normalizar o conjunto de dados?
abacate
Observe que a normalização afeta até mesmo a computação SVD (moe stable). Você deve obter proporções menores entre valores singulares. Observe também que o conjunto de dados geralmente é barulhento e é melhor ter a mesma variação para todos os pontos para obter uma estimativa mais precisa.
Libor