Bagaimana cara memproyeksikan segiempat ke dalam persegi panjang?

tl; dr: Masalah matematika dalam geometri projektif: Bagaimana cara menemukan beberapa matriks kamera 4x4 yang memberikan proyeksi seperti yang diilustrasikan di bawah ini, sehingga titik A, B, C, D berada di suatu tempat di tepi kotak unit (misalnya perangkat yang dinormalisasi OpenGL Koordinat), dan sudut-sudut kotak unit jatuh di suatu tempat yang masuk akal sepanjang sinar EA, EB, EC, ED?

(Ini mungkin kasus khusus yang mungkin menyangkut homografi, perspektif, dan / atau collineation. Tidak akrab dengan terminologi.)

elaborasi

Dengan ABCD segiempat di dalam viewport, saya pikir ada transformasi (?) Unik yang memetakannya kembali ke persegi panjang. Seperti terlihat pada gambar di bawah ini: ABCD segiempat di viewport bertindak sebagai 'jendela' fisik, dan jika kita memetakannya kembali ke persegi panjang itu akan tampak terdistorsi.

(kotak di sebelah kanan mewakili NDC, yang akan saya bicarakan nanti)

Tujuannya adalah untuk cepat mendapatkan gambar di sebelah kanan. Kita dapat melacak setiap titik untuk mendapatkan gambar (yang telah saya lakukan), tetapi saya lebih suka menggunakan OpenGL atau teknik proyektif lainnya karena saya ingin mengambil keuntungan dari hal-hal seperti blending, primitif, dll.

percobaan pertama

Saya percaya saya dapat menyelesaikan masalah menemukan matriks kamera 3x4 yang membuat koordinat homogen 3 + 1-dimensi dalam 3-ruang (di sebelah kiri) dan memproyeksikannya ke koordinat homogen 2 + 1 dimensi dalam 2-ruang (pada hak). Seseorang dapat menyelesaikan ini menggunakan transformasi linear langsung untuk mendapatkan sistem persamaan Ba=0untuk entri yang tidak diketahui adari matriks kamera, dan menyelesaikan sistem menggunakan dekomposisi nilai singular(SVD). Saya akan mengambil vektor EA, EB, EC, ED (di mana E adalah mata fisik Anda atau kamera di dunia-ruang) sebagai titik dalam gambar-pra, dan (0,0), (1,0), (1) , 1), (0,1) atau sesuatu sebagai titik-titik dalam gambar-pos, dan setiap pasangan poin akan memberikan beberapa persamaan linear untuk dihubungkan ke SVD. Matriks yang dihasilkan akan memetakan EA -> (0,0) dll. (Dengan asumsi ada derajat kebebasan yang cukup yaitu jika solusinya unik, yang saya tidak yakin, lihat catatan [a].)

Tapi sayangnya saya ini bukan cara kerja OpenGL. OpenGL tidak secara langsung memproyeksikan 3d ke 2d dengan matriks 3x4. OpenGL membutuhkan "koordinat perangkat dinormalisasi" (NDC), yang merupakan titik tiga dimensi. Setelah diproyeksikan ke NDC, semua yang ada di kotak 'unit' dari (-1, -1, -1,1) hingga (1,1,1,1) ditarik; segala sesuatu di luar terpotong (karena kita berurusan dengan koordinat yang homogen: titik mana pun (x, y, z, w) hanya akan muncul di layar jika tiga koordinat pertama dari (x / w, y / w, z / w , 1) berada dalam kotak unit -1 hingga 1).

Jadi pertanyaannya menjadi: apakah ada beberapa transformasi masuk akal yang memetakan beberapa berbentuk kubus aneh di koordinat homogen (khususnya berbentuk kubus digambar di sebelah kiri, dengan ABCD (poin depan) dan A'B'C'D '(titik belakang, tersembunyi di belakang poin depan)) ke unit cube, mis. menggunakan matriks 4x4? Bagaimana cara melakukannya?

apa yang saya coba

Saya telah mencoba sesuatu yang lebih kuat: Saya membuat ABCD dan A'B'C'D 'terlihat seperti frustrum piramidal biasa (misalnya gl frustrum) (yaitu dalam pengaturan hipotetis ini, gambar di sebelah kiri hanya akan memiliki persegi panjang hitam yang dipasangkan pada itu, bukan segiempat), dan kemudian menggunakan DLT / transformasi linear langsung untuk menyelesaikan untuk dugaan matriks 4x4. Namun ketika saya mencobanya, sepertinya tidak ada derajat kebebasan yang cukup ... matriks 4x4 yang dihasilkan tidak memetakan setiap vektor input ke setiap vektor output. Saat menggunakan A, B, C, D, A '(5 pasang vektor pra-transformasi dan pasca-transformasi), saya / hampir / mendapatkan hasil yang saya inginkan ... vektor dipetakan dengan benar, tetapi misalnya B', C ', D' memetakan ke (3,3,1,1) alih-alih (-1, -1,1,1) dan terpotong oleh OpenGL. Jika saya mencoba menambahkan titik keenam (6 pasang poin untuk matriks 4x4 ke proyek), solusi saya tampaknya merosot (nol, tak terhingga). Berapa derajat kebebasan yang saya hadapi di sini, dan apakah ini mungkin dengan matriks 4x4 memetakan 4 vektor biasa (3 + 1 dimensi vektor koordinat homogen) yang kita kenal dan cintai?

pikiran kecil acak

Saya menduga bahwa tidak mungkin untuk memetakan sembarang kubus sewenang-wenang ke sembarang kubus sewenang-wenang dengan matriks 4x4, meskipun saya bingung karena saya pikir itu mungkin untuk memetakan setiap segiempat cembung ke setiap segiempat cembung lainnya dalam 2d dengan beberapa matriks seperti pada , katakanlah, Photoshop? ... tidak bisakah ini dilakukan dengan transformasi projektif? Dan bagaimana cara generalisasi ke 3d? ...... Juga mengingat upaya yang gagal untuk menemukan matriks 4x4, aljabar linier mengatakan kita seharusnya tidak mengharapkan matriks NxN untuk memetakan lebih dari titik N bebas linear ke titik target N dalam kasus terbaik, tapi saya merasa entah bagaimana homogen Koordinat menipu ini karena ada beberapa colinearity tersembunyi yang terjadi? Saya rasa tidak?

solusi lain?

Saya kira orang juga mungkin bisa melakukan hal buruk berikut, di mana Anda menggunakan matriks proyeksi kamera frustrum khas, menemukan titik 2d yang sesuai dengan sudut, kemudian melakukan perspektif 2d mendistorsi homografi, tetapi jika itu terjadi setelah piksel diberikan (misalnya photoshop) maka akan ada masalah dengan resolusi ... mungkin secara hipotetis orang dapat mengetahui matriks untuk melakukan transformasi ini pada bidang XY dalam ruang NDC, kemudian menyusunnya dengan matriks berbasis frustrasi normal?

(catatan [a]: Tingkat kebebasan: ABCD dapat lebih dibatasi menjadi post-image dari transformasi proyektif yang bekerja pada sebuah persegi panjang, jika itu diperlukan ... itu adalah persegi panjang hitam di sebelah kiri dapat dikatakan sebagai hasil memproyeksikan model clipart bingkai foto)

Saya pikir solusinya adalah mencari transformasi proyektif yang benar mengubah empat poin.

yaitu

$x' = [x_0, x_1, 1]$$y = [\frac{y'_0}{y'_2}, \frac{y'_1}{y'_2}]$

$P$

Sekarang Anda dapat menggunakan aljabar untuk melakukan ini, atau cukup gunakan OpenCV getPerspectiveTransform:).

Lihat juga koordinat homogen di wikipedia untuk mengenal konsep ini.

Saya memecahkan pertanyaan saya sendiri dengan menerapkan Direct Linear Transformation . Bagian contoh di Wikipedia adalah kasus penggunaan saya.

Untuk mendapatkan persamaan, [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]masukkan matriks (misalnya ) ke dalam sistem aljabar komputer favorit Anda seperti SageMath, lalu selesaikan persamaan matriks yang diperlukan seperti yang diilustrasikan, salin-tempelkan solusi dalam hal variabel ke dalam kode Anda, dan sesuaikan pemformatan.

Seseorang kemudian dapat menyesuaikan solusi untuk kasus penggunaan seseorang dengan menskalakan atau mengabaikan dimensi tertentu yang sesuai (misalnya mengabaikan koordinat kedalaman / z dalam matriks Koordinat Perangkat yang Dinormalisasi sesuai dengan kasus penggunaan).

Anda akan memerlukan fungsi dekomposisi SVD atau pustaka dalam bahasa Anda.