Bagaimana saya membuat filter yang tidak merusak gambar bahkan setelah jutaan berjalan - bagian 2

Pada bagian pertama dari posting ini, saya berbicara tentang bagaimana berulang kali menggunakan filter halfpel standar membuat gambar terdistorsi, dan kemudian menunjukkan filter baru yang tidak memiliki masalah ini.

Itu sedikit lebih buram dan ini tidak cocok untuk semua orang. Namun, itu lebih baik daripada alternatifnya - pada kenyataannya, filter ini digunakan dalam versi asli Bink 2 . Karena beban kerja terus-menerus, saya tidak pernah berhasil kembali kepadanya dan memeriksanya secara lebih rinci.

Tetapi sekarang setelah saya menemukan waktu untuk kembali ke filter ini dan menulis artikel tentang itu, saya akhirnya harus bertanya: apakah ada filter yang kurang buram yang masih mempertahankan properti "stabilitas tak terbatas"?

Peringatan spoiler: jawaban yang benar adalah "mungkin tidak" dan "pasti ada." Tetapi sebelum kita sampai pada mengapa ada dua jawaban untuk pertanyaan ini dan apa artinya, mari kita siapkan bangku tes.

Penyesuaian offset

Ketika saya awalnya menangani masalah ini, saya tidak tahu apa yang saya cari. Saya bahkan tidak tahu bahwa ada yang namanya filter halfpel "sangat stabil", jadi saya tidak membuat sistem dalam pencariannya. Saya hanya mencari sesuatu yang akan menahan iterasi filter "banyak" tanpa distorsi gambar. Semua gambar dari bagian pertama mencerminkan metodologi ini: gambar digeser dari kanan ke kiri setengah piksel pada suatu waktu, yaitu, jika Anda menerapkan filter 100 kali, gambar yang dihasilkan akan bergeser 50 piksel.

Sekarang kita tahu apa yang sebenarnya kita cari, kita bisa menjadi sedikit lebih tepat. Menerapkan filter halfpel dua kali, kami menggeser gambar tepat satu piksel. Artinya, jika kita hanya memindahkan gambar satu piksel ke belakang , maka gambar itu akan tetap berada di ruang yang sama. Berkat ini, pengujian akan terlihat jauh lebih indah, karena kita tidak hanya akan dapat menerapkan filter beberapa kali, tanpa takut bahwa gambar akan "merayap" dari layar, tetapi kita juga akan dapat menemukan perbedaan gambar dengan versi sebelumnya dan aslinya.

Ini akan memungkinkan kami untuk menguji filter secara otomatis. Kami cukup menerapkan filter berkali-kali dan melihat salah satu dari dua hal: baik konvergensi ke gambar yang tidak berubah, menunjukkan bahwa filter stabil sangat jauh, atau penyimpangan yang sangat besar dari gambar asli, menunjukkan bahwa filter "rusak". Untuk pengujian ini, saya memilih kesalahan rata-rata per saluran 64 (dari 255), atau kesalahan maksimum pada salah satu saluran ke 255 penuh, sebagai "sangat besar". Jika salah satu dari kondisi ini benar, kami akan menganggap bahwa filter "pecah" ".

Tes ulang filter dari bagian pertama

Jadi, sekarang kita lebih memahami cara menguji filter ini, jadi mari kita lihat filter baru dari bagian pertama. Mari kita mulai dengan bilinear, yang tentu saja tidak terlalu menarik:


Ini adalah gambar setelah 244 iterasi. Seperti yang Anda harapkan, gambar secara bertahap "pecah" karena rata-rata piksel yang konstan. Tetapi bahkan secara bertahap mencapai batas kesalahan rata-rata.

Inilah h.264:


Untuk memecahkan gambar, 78 iterasi sudah cukup baginya. Filter HEVC dengan 8 sampel berperilaku sedikit lebih baik, tetapi masih rusak setelah 150 iterasi:


Lanczos dengan 6 sampel istirahat setelah 166 iterasi:


Itu semua filter kami yang rusak. Yang tersisa hanyalah filter integer saya:


Seperti yang diharapkan, dia bukan satu - satunya yang hancur. Ini konvergen ke gambar yang tak terhingga stabil setelah 208 iterasi.

Apa yang kita ketahui cukup luar biasa di sini: setidaknya untuk berbagai gambar uji, filter ini sangat stabil , yaitu, ia tidak akan pernah membuat artefak, tidak peduli berapa kali itu digunakan.

Ini membawa kita kembali ke pertanyaan awal: apakah dia benar-benar yang terbaik? Dan Anda sudah tahu jawabannya, karena di awal artikel saya juga menulis: "mungkin tidak" dan "pasti, ya".

Pertama-tama mari kita lihat bagian "mungkin bukan".

Filter integer

Jadi, di bagian pertama posting, saya menyebutkan bahwa inti filter yang saya temukan adalah "yang terbaik dari yang terdeteksi", dan ini adalah kekhasannya. Dan inilah fiturnya:

Ketika saya mencari filter ini, sebenarnya saya tidak mencari filter terbaik . Saya mencari filter terbaik yang dapat diekspresikan dengan sejumlah kecil bilangan bulat, penambahan, dan pengurangan bilangan bulat . Ini mungkin terlihat aneh, tetapi luangkan waktu Anda.

Anda mungkin telah memperhatikan bahwa ketika saya menunjukkan koefisien h.264, HEVC, dan filter bilinear, serta filter saya, saya menuliskannya sebagai pembilang bilangan bulat di atas penyebut bilangan bulat, seperti ini:

MyKernel[] = {1.0/32.0, -4.0/32.0, 19.0/32.0, 19.0/32.0, -4.0/32.0, 1.0/32.0}; 

Tetapi dalam kasus windowed sinc, saya bertindak berbeda dan menulisnya seperti ini:

 LanczosKernel[] = {0.02446, -0.13587, 0.61141, 0.61141, -0.13587, 0.02446}; 

Alasannya adalah karena windowed sinc sebenarnya disimpulkan dari fungsi matematika kontinu yang tidak ada hubungannya dengan pecahan bilangan bulat biasa. Saat menggunakan filter ini, angka floating point (seakurat mungkin) digunakan yang sesuai dengan nilai fungsi sinc. Jika Anda berusaha untuk menerapkannya secara akurat, maka Anda tidak harus membulatkannya ke fraksi biasa, karena ini akan menambah kesalahan.

Codec video biasanya tidak mampu melakukan operasi seperti itu. Operasi titik apung pada tugas "berat" seperti kompensasi gerak tidak mungkin digunakan pada daya rendah atau peralatan khusus. Ini terutama benar jika kita berbicara tentang codec standar industri yang harus dijalankan pada berbagai perangkat, termasuk chip tertanam berbiaya rendah dan murah.

Selain itu, bahkan jika Anda mengeksekusi mereka pada CPU, set instruksi modern didasarkan pada SIMD, yaitu, operasi integer pada CPU masih dapat dilakukan lebih cepat: Anda dapat memasukkan dua integer 16-bit ke dalam ruang satu float 32-bit, pada dasarnya menggandakan kinerja operasi, oleh karena itu, jika kita mempertimbangkan jumlah pasti siklus per operasi, maka titik apung tidak selalu merupakan pilihan tercepat.

Sekarang Anda tahu mengapa fitur ini penting. Karena saya hanya membutuhkan operasi integer 16-bit yang sederhana, saya mencari kernel yang dapat dinyatakan sebagai integer kecil di atas pembagi dengan kekuatan dua hingga 64 dan tidak lebih. Ini adalah set filter yang jauh lebih terbatas dibandingkan dengan jika saya mempertimbangkan set 6 koefisien floating point.

Demikian pula, untuk alasan efisiensi, saya tidak mempertimbangkan jumlah sampel lain. Satu-satunya pilihan adalah 6 atau kurang, jadi saya bahkan tidak menguji versi dengan 8 atau 10 sampel.

Jadi kami sampai pada jawaban pertama: "mungkin tidak." Jika kita mematuhi batasan-batasan ini, maka kemungkinan besar kita tidak akan menemukan filter yang lebih baik yang dapat diterapkan berkali-kali tanpa degradasi. Inti filter dari bagian pertama mungkin adalah yang terbaik yang bisa kita temukan, walaupun saya harus mengakui bahwa saya tidak dapat membuktikannya secara mendalam.

Tetapi bagaimana jika kita tidak perlu mematuhi batasan seperti itu?

Versi titik mengambang

Jika kita menyingkirkan batasan khusus untuk versi asli Bink 2 (yang sekarang sudah ketinggalan zaman - banyak revisi telah dirilis) dan menggunakan koefisien floating-point yang sewenang-wenang, lalu seberapa banyak hasilnya dapat ditingkatkan?

Yah, karena kita tahu bahwa kernel integer saya tidak pernah mengalami degradasi, dan kita tahu bahwa Lanczos lebih tajam, tetapi terdegradasi, masuk akal bahwa kita dapat menemukan tempat di antara dua set koefisien tempat degradasi dimulai. Jadi saya menulis sebuah program yang membantu saya menemukan poin ini, dan inilah kernel yang saya temukan:

 MyFloatKernel6[] = {0.027617, -0.130815, 0.603198, 0.603198, -0.130815, 0.027617}; 

Kernel ini membutuhkan 272 iterasi untuk konvergen, tetapi ini sangat stabil dan terlihat jauh lebih tajam daripada filter integer saya:


Bahkan, hampir tidak bisa dibedakan dari aslinya:


Hampir ... tetapi tidak cukup. Jika Anda melihat lebih dekat, Anda masih bisa melihat buram dan atenuasi di area kontras tinggi. Cara termudah untuk melihat ini adalah di mata "dinosaurus" oranye dan di daerah terang di balik bambu.

Yaitu, filter titik-mengambang 6-sampel jelas lebih baik, tetapi itu tidak sempurna. Apakah masih bisa diperbaiki?

Tambah lebar filter

Awalnya, filter dengan 6 sampel dipilih untuk alasan yang sama dengan fraksi dengan bilangan bulat kecil: Saya mencari filter yang sangat efisien. Tetapi sekarang kami sedang melakukan penelitian dan telah beralih ke angka floating point, jadi mengapa tidak mempertimbangkan filter yang lebih luas?

Menggabungkan filter integer 6-sampel kami dengan Lanczos 6-sampel, kami mendapatkan filter yang sangat baik. Mengapa kita tidak memasangkan Lanczos 8 sampel?

8-sampel Lanczos terlihat seperti ini:

 Lanczos8[] = {-0.01263, 0.05976, -0.16601, 0.61888, 0.61888, -0.16601, 0.05976, -0.01263}; 

Seperti Lanczos 6-sampel, sangat tidak stabil dan runtuh setelah 178 iterasi:


Jika kami mencari filter yang lebih baik antara filter integer 6-sampel dan Lanczos 8-sampel, kami menemukan filter 8-sampel yang agak luar biasa ini:

 MyFloatKernel8[] = {-0.010547, 0.052344, -0.156641, 0.614844, 0.614844, -0.156641, 0.052344, -0.010547}; 

Sebagai filter yang sangat stabil, kinerjanya sangat baik. Ia menyatu setelah 202 iterasi (konvergensi lebih cepat dari dua filter saya), dan sangat mirip dengan aslinya sehingga sulit untuk mengetahui yang mana di antaranya:


Ini yang asli sebagai referensi lagi:


Dibandingkan dengan filter integer asli saya, ada peningkatan yang signifikan.

Bagaimana cara kerja filter yang sangat stabil?

Saya akan mengakhiri tulisan ini seperti ini:

“Saya tidak tahu persis bagaimana cara kerjanya. Di daerah lain di mana saya telah bekerja dengan transformasi yang berlaku tak terbatas, saya tahu bagaimana matematika batas dilakukan dan analisis yang berguna dibuat. Pertama-tama, ia datang ke analisis permukaan batas untuk permukaan subdivisi, di mana nilai eigen dan vektor eigen dari matriks subdivisi dihitung, setelah itu dimungkinkan untuk secara tepat mengambil batas ke tingkat yang tak terbatas. Tapi saya tidak punya pengalaman dalam melakukan analisis seperti itu untuk filter halfpel, karena mereka tidak meninggalkan piksel di tempat, tetapi menggeser mereka ke samping. "

Itu rencanaku. Tetapi di antara penulisan bagian pertama dan kedua, saya mengirimkan hasil filter yang ditingkatkan ke Fabien Giessen dan Charles Bloom . Tidak mengherankan bahwa mereka tahu matematika yang diperlukan untuk studi analitis masalah ini. Ternyata untuk filter benar-benar ada analisis nilai eigen dan vektor, tetapi tidak cukup berhasil seperti itu.

Tapi itu dapat dengan mudah dieksekusi - pada kenyataannya, ini dibangun ke dalam program CAM sebagai proses satu langkah sepele dan kita benar-benar dapat melihat nilai eigen untuk filter. Dia tidak memberi kita jawaban lengkap, karena di sini fakta pembulatan (atau pemotongan) menjadi 8 bit (atau 10 bit, atau 12 bit) setelah setiap penyaringan adalah penting, karena pemotongan mempengaruhi metode akumulasi kesalahan dibandingkan dengan aljabar yang sangat akurat.

Sayangnya, karena ini sama sekali bukan bidang keahlian saya, saya bahkan tidak bisa mendapatkan gambaran umum dari analisis ini. Saya bertanya kepada Fabien dan Charles apakah mereka dapat menulis posting dengan informasi bagus yang mereka kirimkan kepada saya melalui pos (mereka berdua memiliki blog teknis - blog ryg dan cbloom rants ), dan Fabien menulis serangkaian artikel yang bagus tentang dasar matematika dari filter stabil . Jika Anda tertarik pada struktur teoritis tentang apa yang terjadi di dua posting saya, maka saya sarankan membaca seri ini!