Interpolasi dan diskritisasi, mengapa mereka diperlukan untuk konversi gambar proyektif?

Halo, Habr! Hari ini kita akan berbicara dengan sangat rinci tentang hal-hal yang tidak jelas dalam operasi yang tampaknya sederhana: memperbaiki distorsi proyektif pada gambar. Seperti yang sering terjadi dalam kehidupan, kami harus memilih mana yang lebih penting: kualitas atau kecepatan. Dan untuk mencapai keseimbangan tertentu, kami mengingat algoritma yang kami pelajari secara aktif di tahun 80-90-an sebagai bagian dari tugas membuat struktur, dan sejak itu kami jarang mengingat dalam konteks pemrosesan gambar. Jika tertarik, lihat di bawah kucing!




Model kamera lubang jarum, yang dalam praktiknya juga membawa kamera close-up ponsel dengan cukup baik, memberi tahu kita bahwa ketika kamera berputar, gambar-gambar objek datar saling terkait oleh transformasi projektif. Pandangan umum dari transformasi proyektif adalah sebagai berikut:

$$

$$x = \frac{t_{11} u + t_{12} v + t_{13}}{t_{31} u + t_{32} v + t_{33}}, \ \ \ y = \frac{t_{21} u + t_{22} v + t_{23}}{t_{31} u + t_{32} v + t_{33}},$$

Dimana $$$T = (t_{ij}), \ \ i \in \{1, 2, 3\}, \ \ j \in \{1, 2, 3\}$matriks transformasi proyektif, $$$(u, v)$dan $$$(x, y)$koordinat pada sumber dan gambar yang dikonversi.

Konversi Gambar Geometris

Transformasi gambar projektif adalah salah satu transformasi geometris yang mungkin dari gambar (transformasi seperti di mana titik-titik gambar asli pergi ke titik-titik gambar akhir sesuai dengan hukum tertentu).

Untuk memahami bagaimana menyelesaikan masalah transformasi geometrik gambar digital, Anda perlu mempertimbangkan model pembentukannya dari gambar optik pada matriks kamera. Menurut G. Wahlberg [1], algoritma kami harus mendekati proses berikut:

1. Pulihkan gambar optik dari digital.
2. Transformasi geometris dari gambar optik.
3. Pengambilan sampel dari gambar yang dikonversi.

Gambar optik adalah fungsi dari dua variabel yang didefinisikan pada set titik kontinu. Proses ini sulit untuk direproduksi secara langsung, karena kita harus secara analitis mengatur jenis gambar optik dan memprosesnya. Untuk menyederhanakan proses ini, metode pemetaan terbalik biasanya digunakan:

1. Pada bidang gambar akhir, grid pengambilan sampel dipilih - titik di mana kami akan mengevaluasi nilai piksel dari gambar akhir (ini mungkin merupakan pusat dari setiap piksel, atau mungkin beberapa poin per piksel).
2. Menggunakan transformasi geometri terbalik, kisi ini ditransfer ke ruang gambar asli.
3. Untuk setiap sampel kisi, nilainya diperkirakan. Karena itu tidak selalu muncul pada suatu titik dengan koordinat bilangan bulat, kita perlu beberapa interpolasi dari nilai gambar, misalnya, interpolasi oleh piksel tetangga.
4. Menurut laporan kisi, kami memperkirakan nilai piksel dari gambar akhir.

Di sini, langkah 3 berhubungan dengan pemulihan gambar optik, dan langkah 1 dan 4 berhubungan dengan pengambilan sampel.

Interpolasi

Di sini kita akan mempertimbangkan hanya jenis interpolasi sederhana - yang dapat direpresentasikan sebagai konvolusi gambar dengan inti interpolasi. Dalam konteks pemrosesan gambar, algoritma interpolasi adaptif yang mempertahankan batas-batas objek yang jelas akan lebih baik, tetapi kompleksitas komputasinya jauh lebih tinggi dan oleh karena itu kami tidak tertarik.

Kami akan mempertimbangkan metode interpolasi berikut:

• oleh piksel terdekat
• bilinear
• bikubik
• b-spline kubik
• hermitian spline kubik, 36 poin.

Interpolasi juga memiliki parameter penting seperti akurasi. Jika kita mengasumsikan bahwa gambar digital diperoleh dari metode optik dengan pengambilan sampel spot di tengah piksel dan percaya bahwa gambar asli kontinu, maka filter low-pass dengan frekuensi ½ akan menjadi fungsi rekonstruksi yang ideal (lihat teorema Kotelnikov ).

Oleh karena itu, kami membandingkan spektrum Fourier inti interpolasi kami dengan filter low-pass (dalam gambar disajikan untuk kasus satu dimensi).



Dan apa, Anda bisa menggunakan kernel dengan spektrum yang cukup bagus dan mendapatkan hasil yang relatif akurat? Sebenarnya tidak, karena kami membuat dua asumsi di atas: bahwa ada nilai piksel gambar dan kontinuitas gambar ini. Pada saat yang sama, tidak satu atau yang lain merupakan bagian dari model pembentukan gambar yang baik, karena sensor pada matriks kamera tidak seperti titik, dan pada gambar banyak informasi membawa batasan objek - celah. Oleh karena itu, sayangnya, harus dipahami bahwa hasil interpolasi akan selalu berbeda dari gambar optik asli.

Tetapi Anda masih perlu melakukan sesuatu, jadi kami akan menjelaskan secara singkat kelebihan dan kekurangan dari masing-masing metode yang dipertimbangkan dari sudut pandang praktis. Cara termudah untuk melihat ini adalah ketika Anda memperbesar gambar (dalam contoh ini, 10 kali).

Interpolasi Pixel Terdekat

Yang paling sederhana dan tercepat, bagaimanapun, itu mengarah ke artefak yang kuat.

Interpolasi bilinear

Lebih baik dalam kualitas, tetapi membutuhkan lebih banyak perhitungan dan juga mengaburkan batas objek.

Interpolasi bisubik

Bahkan lebih baik di area kontinu, tetapi di perbatasan ada efek halo (strip lebih gelap di sepanjang tepi gelap perbatasan dan cahaya di sepanjang cahaya). Untuk menghindari efek ini, Anda perlu menggunakan kernel konvolusi non-negatif seperti b-spline kubik.

Interpolasi B-spline

B-spline memiliki spektrum yang sangat sempit, yang berarti gambar "blur" yang kuat (tetapi juga pengurangan noise yang baik, yang dapat berguna).

Interpolasi berdasarkan pada spline Hermite kubik

Spline seperti itu membutuhkan perkiraan turunan parsial di setiap piksel gambar. Jika untuk perkiraan kita memilih skema perbedaan 2-titik, maka kita mendapatkan inti interpolasi bikubik, jadi di sini kita menggunakan yang 4-poin.


Kami juga membandingkan metode ini dalam hal jumlah akses memori (jumlah piksel dari gambar asli untuk interpolasi pada satu titik) dan jumlah penggandaan demi titik.

Dapat dilihat bahwa 3 metode terakhir secara signifikan lebih mahal secara komputasi daripada 2 metode pertama.

Contoh

Ini adalah langkah yang sangat sedikit perhatian telah dibayarkan cukup baru-baru ini. Cara termudah untuk melakukan transformasi gambar proyektif adalah dengan mengevaluasi nilai setiap piksel dari gambar akhir dengan nilai yang diperoleh dengan membalik pusatnya ke bidang gambar asli (dengan mempertimbangkan metode interpolasi yang dipilih). Kami menyebutnya pendekatan piksel demi diskritisasi piksel . Namun, di area di mana gambar dikompresi, ini dapat menyebabkan artefak signifikan yang disebabkan oleh masalah tumpang tindih spektrum pada frekuensi sampling yang tidak mencukupi.

Kami akan dengan jelas mendemonstrasikan artefak kompresi pada sampel paspor Rusia dan bidang individualnya - tempat kelahiran (kota Arkhangelsk), dikompresi menggunakan pengambilan sampel piksel demi piksel atau algoritme CEPAT, yang akan kami pertimbangkan di bawah ini.



Dapat dilihat bahwa teks pada gambar kiri menjadi tidak dapat dibaca. Itu benar, karena kita hanya mengambil satu titik dari seluruh wilayah gambar sumber!

Karena kami tidak dapat memperkirakan satu piksel, lalu mengapa tidak memilih lebih banyak sampel per piksel, dan rata-rata nilai yang diperoleh? Pendekatan ini disebut supersampling . Ini benar-benar meningkatkan kualitas, tetapi pada saat yang sama, kompleksitas komputasi meningkat secara proporsional dengan jumlah sampel per piksel.

Metode komputasi yang lebih efisien ditemukan pada akhir abad terakhir, ketika grafik komputer memecahkan masalah rendering tekstur yang ditumpangkan pada objek datar. Salah satu metode ini adalah konversi menggunakan mip-mapstruktur. Mip-map adalah piramida gambar yang terdiri dari gambar asli itu sendiri, serta salinannya dikurangi 2, 4, 8 dan seterusnya. Untuk setiap piksel, kami mengevaluasi tingkat karakteristik kompresi itu, dan sesuai dengan tingkat ini kami memilih tingkat yang diinginkan dari piramida, sebagai gambar sumber. Ada berbagai cara untuk mengevaluasi tingkat mip-map yang sesuai (lihat detail [2]). Di sini kita akan menggunakan metode berdasarkan estimasi derivatif parsial sehubungan dengan matriks transformasi projektif yang terkenal. Namun, untuk menghindari artefak di area gambar akhir di mana satu tingkat struktur peta-mip pergi ke yang lain, interpolasi linier biasanya digunakan antara dua tingkat piramida yang berdekatan (ini tidak terlalu meningkatkan kompleksitas komputasi, karena koordinat titik-titik di tingkat tetangga terhubung secara unik).

Namun, mip-map tidak memperhitungkan fakta bahwa kompresi gambar dapat bersifat anisotropik (memanjang sepanjang beberapa arah). Masalah ini sebagian dapat diselesaikan dengan rip-map . Struktur tempat gambar dikompresi$$$2^m$ waktu secara horizontal dan $$$2^n$kali secara vertikal. Dalam hal ini, setelah menentukan koefisien kompresi horizontal dan vertikal pada titik tertentu pada gambar akhir, interpolasi dilakukan di antara hasil 4 salinan gambar asli yang dikompres pada jumlah yang diinginkan beberapa kali. Tetapi metode ini tidak ideal, karena tidak memperhitungkan bahwa arah anisotropi berbeda dari arah yang sejajar dengan batas-batas gambar asli.

Sebagian, masalah ini dapat diselesaikan dengan algoritma FAST (Footprint Area Sampled Texturing) [3]. Ini menggabungkan ide mip-map dan supersampling. Kami memperkirakan tingkat kompresi berdasarkan sumbu paling sedikit anisotropi dan memilih jumlah sampel secara proporsional dengan rasio panjang sumbu terkecil ke terbesar.

Sebelum membandingkan pendekatan ini dalam hal kompleksitas komputasi, kami membuat reservasi bahwa untuk mempercepat perhitungan transformasi projektif invers, adalah rasional untuk melakukan perubahan berikut:

$$$q(x, y) = \frac{1}{f_3(x) + g_3(y)},$
$$$u(x, y) = q(x, y)(f_1(x) + g_1(y)),$
$$$v(x, y) = q(x, y)(f_3(x) + g_3(y)),$

Dimana $$$f_i(x) = p_{i1} x, g_i(y) = p_{i2} y + p_{i3}, P = (p_{ij}) = T ^ {-1}, i \in \{1, 2, 3\}, j \in \{1, 2, 3\}$, $$$P$Adalah matriks dari transformasi proyektif terbalik. Sebagai$$$f(x)$ dan $$$g(y)$fungsi satu argumen, kita dapat pra-menghitungnya untuk waktu yang sebanding dengan ukuran linier gambar. Kemudian, untuk menghitung koordinat dari gambar terbalik dari satu titik dari gambar akhir$$$(u, v)$, hanya 1 divisi dan 2 perkalian yang diperlukan. Trik serupa dapat dilakukan dengan turunan parsial, yang digunakan untuk menentukan level dalam struktur mip-map atau rip-map.

Sekarang kami siap untuk membandingkan hasil dalam hal kompleksitas komputasi.

Dan bandingkan secara visual (dari kiri ke kanan pengambilan sampel piksel demi piksel, supersampling sebanyak 49 sampel, mip-peta, rip-peta, FAST).

Percobaan

Sekarang, mari kita bandingkan hasil kami secara eksperimental. Kami menyusun algoritma transformasi proyektif yang menggabungkan masing-masing dari 5 metode interpolasi dan 5 metode diskritisasi (total 25 opsi). Ambil 20 gambar dokumen yang dipangkas menjadi 512x512 piksel, buat 10 set 3 matriks transformasi projektif, sehingga setiap set umumnya setara dengan transformasi yang identik, dan kami akan membandingkan PSNR antara gambar asli dan yang dikonversi. Ingat bahwa PSNR adalah$$$10 \log \frac{MAX^2}{MSE}$dimana $$$MAX$ini adalah maksimum dalam gambar asli a $$$MSE$- standar deviasi final dari aslinya. Semakin banyak PSNR semakin baik. Kami juga akan mengukur waktu operasi konversi proyektif pada ODROID-XU4 dengan prosesor ARM Cortex-A15 (2000 MHz dan 2GB RAM).

Tabel mengerikan dengan hasil:

Kesimpulan apa yang bisa ditarik?

• Penggunaan interpolasi oleh pixel terdekat atau sampling pixel demi pixel menghasilkan kualitas yang buruk (itu jelas dari contoh di atas).
• 36 — .
• b- , , .
• Rip-map FAST , 9 ( , ?).
• mip-map b- PSNR , .

Jika Anda menginginkan kualitas yang baik dengan kecepatan yang tidak terlalu rendah, Anda harus mempertimbangkan interpolasi bilinear dalam kombinasi dengan diskritisasi menggunakan mip-map atau FAST. Namun, jika diketahui dengan pasti bahwa distorsi proyektif sangat lemah, untuk meningkatkan kecepatan, Anda dapat menggunakan diskritisasi piksel demi piksel yang dipasangkan dengan interpolasi bilinear atau bahkan interpolasi oleh piksel terdekat. Dan jika Anda membutuhkan kualitas tinggi dan jangka waktu yang tidak terbatas, Anda dapat menggunakan interpolasi bikubik atau adaptif yang dipasangkan dengan supersampling moderat (misalnya, juga adaptif, tergantung pada rasio kompresi lokal).

PS Publikasi ini didasarkan pada laporan: A. Trusov dan E. Limonova, "Analisis algoritma transformasi proyektif untuk pengenalan gambar pada perangkat seluler," ICMV 2019, edisi 11433., Wolfgang Osten, Dmitry Nikolaev, Jianhong Zhou, Ed., SPIE , Jan. 2020, vol. 11433, ISSN 0277-786X, ISBN 978-15-10636-43-9, vol. 11433, 11433 0Y, hlm. 1-8, 2020, DOI: 10.1117 / 12.2559732.