Mengapa menormalkan set data sebelum menerapkan Direct Linear Transform

9

Direct Linear Transform (DLT) adalah metode estimasi homografi, ini memecahkan sistem linear overdetermined melalui SVD untuk menemukan solusi bawah kendala . Sebenarnya ia menemukan solusi kuadrat terkecil yang meminimalkan \ | Ah - b \ | .

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

Saya mengerti ide dasar dari algoritma ini, tetapi direkomendasikan untuk menormalkan set data sebelum menerapkan DLT di atasnya, dan di sini adalah pengantar tentang bagaimana melakukan normalisasi. Diketahui bahwa normalisasi data penting untuk DLT, tanpa normalisasi hasil dari DLT tidak stabil.

Kenapa ya? Hanya karena DLT melibatkan penyelesaian sistem linear menggunakan SVD dan A mungkin tunggal?

image-processing homography normalization alpukat
sumber

Jawaban:

12

Normalisasi pada dasarnya merupakan prasyarat untuk menurunkan angka kondisi dari matriks A (semakin besar angka kondisi, semakin dekat matriks tersebut dengan matriks singular).

Transformasi normalisasi juga diwakili oleh sebuah matriks dalam hal estimasi homografi, dan ini dapat digunakan sebagai matriks prekondisier yang baik. Alasan mengapa hal itu lebih rumit dan dijelaskan secara singkat dalam buku H&Z (4.4.4, hlm. 107: Mengapa normalisasi itu penting? ) Atau lebih rinci dalam makalah " Dalam Pertahanan Algoritma Delapan Poin ".

Sederhananya, matriks terdiri dari produk-produk koordinat gambar yang dapat memiliki skala yang berbeda. Jika skala berbeda dengan faktor , produk berbeda dengan faktor .A10102

Sumber dan target data koordinat biasanya berisik . Tanpa normalisasi, data dari sumber akan dapat memiliki dua urutan besarnya lebih besar daripada dari target (atau sebaliknya).

Estimasi homografi biasanya menemukan parameter dalam arti kuadrat-terkecil - maka estimasi statistik terbaik hanya ditemukan jika varian parameternya sama (atau diketahui sebelumnya, tetapi lebih praktis hanya dengan menormalkan input).

Pemecah langsung tidak menyukai masalah yang berskala buruk karena ketidakstabilan numerik muncul (misalnya, membagi angka yang sangat besar dengan angka yang sangat kecil dengan mudah menyebabkan luapan numerik).

Pemecah berulang berjuang dengan matriks yang dikondisikan dengan buruk membutuhkan lebih banyak iterasi.

Jadi normalisasi sangat penting tidak hanya untuk stabilitas numerik, tetapi juga untuk estimasi yang lebih akurat dengan adanya noise dan solusi yang lebih cepat (dalam hal solver berulang).

Libor
sumber
Dan lebih jauh saya bertanya-tanya mengapa matriks prekondisi kurang unik daripada sebelumnya? Dengan standarisasi , jumlah kondisi dari matriks prekondisi akan berkurang?
alpukat
1
Karena kesalahan dalam data tidak akan mempengaruhi hasil sebanyak itu. Bayangkan memperkirakan posisi tangan pada jam dengan dua poin di permukaan jam. Jika satu titik sangat dekat pusat dan yang lainnya di perbatasan, fluktuasi posisi titik dekat pusat mempengaruhi hasil secara signifikan sedangkan titik di perbatasan mempengaruhi posisi tangan dengan ringan. Normalisasi pada dasarnya menempatkan kedua titik di perbatasan yang membuat solusi lebih stabil dan menempatkannya lebih jauh dari pusat permukaan jam (titik singularitas).
Libor
2

Artikel Wikipedia menyatakan:

"Apa yang membedakan masalah transformasi linear langsung..adalah fakta bahwa sisi kiri [X] dan kanan [AY] dari definisi persamaan [X = AY] dapat berbeda dengan faktor multiplikatif yang tidak diketahui yang bergantung pada k"

Dalam X di atas, A, Y adalah matriks.

Jadi untuk menghindari keharusan memperkirakan faktor, Anda cukup menormalkan semua data yang Anda miliki.

Tom Kealy
sumber
Ini kedengarannya tidak benar ... Jika kita bisa menormalkan untuk membuat faktor itu tidak penting, masalahnya bisa diselesaikan dengan menggunakan metode reguler . A=XYT(YYT)−1
Michael Litvin
1

Ini masalah akurasi numerik. Dengan menormalkan set data, Anda memusatkan data Anda dan memberikan varians unit. Kondisi ini lebih baik ditangani oleh solbver.

sansuiso
sumber
Dengan lebih baik ditangani oleh solver , maksud Anda ketika saya memecahkan sistem linear semacam ini melalui SVD , saya harus selalu menormalkan set data?
alpukat
Perhatikan bahwa normalisasi memengaruhi bahkan perhitungan SVD (moe stable). Anda kemudian harus mendapatkan rasio yang lebih kecil antara nilai singular. Juga perhatikan bahwa kumpulan data biasanya berisik dan lebih baik memiliki varian yang sama untuk semua poin untuk mendapatkan perkiraan yang lebih akurat.
Libor