Setelah menyelesaikan pembuatan arsitektur web untuk komik web baru kami
Meow the Infinite , saya memutuskan sudah waktunya untuk menulis beberapa artikel teknis yang sudah lama tertunda. Artikel ini akan fokus pada filter yang saya kembangkan beberapa tahun yang lalu. Ini belum pernah dibahas di bidang kompresi video, meskipun bagi saya itu layak dilakukan.
Pada 2011, saya mengembangkan "filter setengah-pel". Ini adalah jenis filter khusus yang mengambil gambar yang masuk dan paling meyakinkan menampilkan bagaimana gambar akan terlihat ketika bergeser
tepat setengah piksel .
Anda mungkin bertanya-tanya mengapa filter semacam itu mungkin diperlukan sama sekali. Bahkan, mereka cukup umum di codec video modern. Codec video menggunakan filter serupa untuk mengambil fragmen dari frame sebelumnya dan menggunakannya dalam frame berikutnya. Codec yang lebih lama hanya memindahkan data bingkai satu piksel pada satu waktu, tetapi codec yang baru bergerak lebih jauh dan memungkinkan pergeseran setengah atau bahkan seperempat piksel untuk mentransmisikan gerakan kecil dengan lebih baik.
Ketika menganalisis perilaku algoritma kompensasi gerak dalam filter halfpel tradisional,
Jeff Roberts menemukan bahwa ketika diterapkan berulang kali pada frame sekuensial, mereka dengan cepat menurunkan, memaksa bagian lain dari kompresor video untuk menggunakan lebih banyak data daripada yang diperlukan untuk memperbaiki artefak. Jika Anda menonaktifkan koreksi ini dan melihat hasil "mentah" dari filter halfpel, maka ini adalah gambar aslinya:
berubah menjadi ini:
hanya satu detik kemudian videonya. Seperti seharusnya, itu digeser ke samping, karena setiap frame menggeser gambar dengan setengah piksel. Tetapi hasilnya tidak terlihat seperti versi yang dipindahkan dari gambar asli, itu benar-benar terdistorsi.
Selama filter "satu video kedua" sebenarnya diterapkan berkali-kali - 60 jika video diputar pada frekuensi 60 frame per detik. Namun idealnya, kita membutuhkan filter yang tahan terhadap distorsi semacam itu. Jika kami memilikinya, gulir video dengan lancar tidak akan dikodekan dengan begitu banyak koreksi artefak, yang akan membuatnya lebih sedikit, atau lebih baik, atau keduanya.
Jika Anda terbiasa dengan bidang kompresi video, Anda mungkin bertanya-tanya mengapa kita bahkan perlu menggunakan filter halfpel lebih dari sekali. Pada akhirnya, jika kita menerapkan filter halfpel dua kali, maka kita sudah akan memindahkan satu piksel penuh, jadi mengapa tidak hanya menggunakan data dari
dua frame kembali dan hanya mengambilnya?
Jawabannya tidak begitu sederhana. Pertama, semakin banyak data yang kita butuhkan untuk menyandikan data, semakin sedikit kompresi yang kita dapatkan. Karena itu, jika kita mulai menyandikan tanpa perlu terlalu banyak data seperti "dari frame mana untuk mengambil data", video tidak akan dikompresi dengan baik.
Tapi ini bukan yang terpenting. Masalah utama adalah bahwa jika kita perlu mengambil informasi dari frame sebelumnya, kita
harus menyimpannya . Untuk mempertahankan dua frame sebelumnya, alih-alih satu, Anda harus menebak bahwa Anda memiliki memori dua kali lebih banyak. Untuk CPU modern, ini bukan masalah khusus, mereka memiliki banyak memori dan hal sepele seperti itu tidak mengganggu mereka. Tetapi ini adalah
masalah bagi Anda jika Anda ingin membuat format video yang cepat, portabel, dan banyak digunakan yang harus bekerja di perangkat dengan sedikit memori (ponsel, elektronik bawaan, dll.).
Kami benar-benar tidak ingin menyimpan beberapa frame untuk mengkompensasi pergerakan hanya agar tidak menggunakan filter halfpel. Oleh karena itu, saya diperintahkan untuk mencari tahu apa sebenarnya yang terjadi di sini dan untuk mencari tahu apakah saya dapat membuat filter yang tidak memiliki masalah seperti itu.
Sebelum itu, saya tidak pernah bekerja dengan filter dan tidak tahu bagaimana mereka biasanya dikembangkan. Anehnya, ternyata menguntungkan saya, karena saya harus melihat masalah ini tanpa prasangka.
Dasar-dasarnya
Saya segera menyadari bahwa filter halfpel paling populer memiliki struktur yang serupa: untuk setiap piksel dalam gambar output, 2 hingga 8 piksel dari gambar input diambil, yang disampel dan dicampur dengan koefisien tertentu. Filter yang berbeda hanya berbeda dalam jumlah piksel sumber sampel (sering kali dalam jargon pengembang filter disebut ketuk) dan faktor pencampuran piksel. Koefisien ini sering disebut "filter kernel" dan hanya itu yang diperlukan untuk menggambarkan filter sepenuhnya.
Jika Anda terbiasa dengan pengambilan sampel atau resampling gambar (misalnya, menskala gambar), maka ini harus jelas bagi Anda. Pada dasarnya, filter melakukan hal yang sama. Karena kompresi video adalah area yang luas di mana berbagai studi sedang dilakukan, jelas bahwa ada banyak cara
lain untuk mengimbangi gerakan selain penyaringan sederhana. Tetapi codec umum biasanya menggunakan prosedur kompensasi gerak dengan filter halfpel, yang pada dasarnya identik dengan filter penskalaan gambar: mereka hanya mengambil piksel asli, mengalikannya dengan beberapa bobot, menambahkannya dan mendapatkan piksel keluaran.
Kebutuhan akan "ketajaman"
Jadi, kita perlu menggeser gambar hingga setengah piksel. Jika Anda seorang programmer grafis, tetapi tidak terlalu terbiasa dengan filtering, Anda mungkin berpikir: "Saya juga punya masalah, cukup gunakan filter bilinear." Ini adalah proses standar dalam bekerja dengan grafik, ketika kita perlu menghitung nilai antara antara dua elemen data yang masuk, seperti yang terjadi di sini.
Filter bilinear untuk memindahkan tepat setengah piksel dapat dengan mudah dijelaskan oleh inti filter berikut:
Ini akan berhasil, tetapi bukan tanpa masalah. Jika sasaran Anda adalah gambar berkualitas tinggi, dan dalam hal kompresi video, tujuannya hanya itu, maka filter bilinear bukan solusi terbaik, karena itu menambah lebih banyak blur pada hasil daripada yang diperlukan. Ini tidak begitu
banyak , tetapi
lebih dari yang dibuat oleh filter lain.
Untuk menunjukkan ini dengan jelas, berikut ini adalah gambar perkiraan mata walrus dari gambar asli setelah satu aplikasi filter yang paling umum:
Di sebelah kiri adalah yang asli, di sebelah kanan adalah penyaringan bilinear. Di antara mereka adalah filter halfpel codec video yang paling banyak digunakan. Jika Anda melihat lebih dekat, Anda dapat melihat bahwa hampir semua gambar terlihat serupa,
kecuali yang bilinear, yang sedikit lebih buram. Meskipun tidak ada banyak kekaburan, jika tujuan utama Anda adalah kualitas gambar, maka ini sudah cukup untuk memilih filter yang berbeda daripada filter bilinear.
Jadi, bagaimana filter lain “mempertahankan” ketajaman dan menghindari pengaburan? Mari kita ingat seperti apa inti dari bilinear blur:
BilinearKernel[] = {1.0/2.0, 1.0/2.0};
Ini sangat sederhana. Untuk menggeser gambar setengah piksel, kami mengambil piksel dan mencampurnya 50% dengan tetangganya. Itu saja. Orang dapat membayangkan bagaimana ini "mengaburkan" gambar, karena di tempat-tempat di mana piksel putih terang berdekatan dengan hitam gelap, dua piksel ini dirata-rata selama penyaringan bilinear, menciptakan piksel abu-abu yang "melembutkan" perbatasan. Ini terjadi pada setiap piksel, sehingga secara harfiah setiap area di mana terdapat perbedaan warna atau kecerahan yang jelas. dihaluskan.
Itulah sebabnya dalam codec bilinear filtering berkualitas tinggi tidak digunakan untuk kompensasi gerak (meskipun dapat digunakan dalam kasus lain). Alih-alih, filter digunakan yang menjaga ketajaman, misalnya, seperti:
Seperti yang Anda lihat, di mana penyaringan bilinear hanya memperhitungkan dua piksel, filter ini memperhitungkan enam (h.264) atau bahkan delapan (HEVC) piksel. Selain itu, mereka tidak hanya menghitung nilai rata-rata tertimbang biasa dari piksel ini, tetapi menggunakan bobot
negatif untuk beberapa piksel untuk
mengurangi piksel ini dari nilai lain.
Mengapa mereka melakukan ini?
Sebenarnya tidak sulit untuk memahami ini: menggunakan nilai positif dan negatif, dan juga mempertimbangkan "jendela" yang lebih luas, filter dapat memperhitungkan
perbedaan antara piksel yang berdekatan dan mensimulasikan ketajaman dua piksel terdekat relatif terhadap tetangga terjauh mereka. Ini memungkinkan Anda untuk mempertahankan ketajaman hasil gambar di tempat-tempat di mana piksel berbeda secara signifikan dari tetangga mereka, sementara rata-rata masih digunakan untuk membuat nilai yang dapat dipercaya dari pergeseran "setengah piksel", yang harus mencerminkan kombinasi piksel dari gambar yang masuk.
Pemfilteran tidak stabil
Jadi, apakah masalahnya teratasi? Ya, itu mungkin, tetapi jika Anda hanya perlu melakukan offset satu setengah piksel. Namun, filter "mengasah" ini (dan saya sengaja menggunakan istilah ini di sini) sebenarnya melakukan sesuatu yang berbahaya,
pada dasarnya mirip dengan apa yang dilakukan penyaringan bilinear. Mereka lebih baik tahu cara menyembunyikannya.
Di mana penyaringan bilinear
mengurangi ketajaman gambar, filter standar ini
meningkatkannya , seperti operasi pertajam di beberapa program grafis. Jumlah penajaman sangat kecil, jadi jika kita menjalankan filter hanya sekali, kita tidak akan melihat ini. Tetapi jika penyaringan dilakukan beberapa kali, maka ini bisa menjadi sangat nyata.
Dan, sayangnya, karena penajaman ini bersifat prosedural dan tergantung pada perbedaan antara piksel, itu
menciptakan loop umpan balik yang akan terus mempertajam perbatasan yang sama lagi dan lagi sampai merusak gambar. Anda dapat menunjukkan ini dengan contoh spesifik.
Di atas - gambar asli, di bawah ini - dengan penyaringan bilinear, menampilkan lebih dari 60 frame:
Seperti yang Anda harapkan, kabur hanya terus mengurangi ketajaman gambar hingga menjadi cukup buram. Sekarang yang asli akan berada di atas, dan filter halfpel codec h.264 yang akan berjalan untuk 60 frame di bagian bawah:
Lihat semua sampah ini? Filter melakukan hal yang sama sebagai efek "blur" dari penyaringan bilinear, tetapi
sebaliknya - itu "meningkatkan ketajaman gambar" sehingga semua bagian di mana detail berubah menjadi pola cahaya / gelap yang sangat terdistorsi.
Apakah codec HEVC menggunakan 8 piksel berperilaku lebih baik? Yah, itu pasti lebih baik daripada h.264:
tetapi jika kita menambah waktu dari 60 frame (1 detik) menjadi 120 frame (2 detik), kita masih akan melihat bahwa ada umpan balik dan gambar dihancurkan:
Demi mereka yang menyukai pemrosesan sinyal, saya akan menambahkan filter windowed-sinc (disebut filter Lanczos) untuk referensi:
Saya tidak akan menjelaskan dalam artikel ini mengapa seseorang mungkin tertarik pada "windowed sinc", tetapi cukup untuk mengatakan bahwa filter ini populer karena alasan teoretis, jadi lihat tampilannya saat memproses 60 frame (1 detik):
dan saat memproses 120 frame (2 detik):
Lebih baik daripada h.264, dan hampir sama dengan HEVC.
Penyaringan stabil
Bagaimana kita bisa mencapai hasil yang lebih baik daripada h.264, HEVC dan windowed sinc? Dan seberapa jauh mereka bisa lebih baik?
Saya
berharap untuk melihat pertanyaan serupa dalam literatur tentang kompresi video dan mereka harus diketahui oleh spesialis kompresi, tetapi pada kenyataannya (setidaknya untuk 2011) saya tidak menemukan siapa pun yang setidaknya menyatakan bahwa ini adalah masalah. Jadi saya harus mencari solusi sendiri.
Untungnya, pernyataan masalahnya sangat sederhana: buat filter yang dapat diterapkan sebanyak mungkin sehingga gambar terlihat hampir sama dengan di awal.
Saya menyebut definisi ini "pemfilteran stabil" karena, menurut pendapat saya, ini dapat dianggap sebagai properti filter. Filter "stabil" jika tidak jatuh ke loop umpan baliknya, yaitu, ia dapat diterapkan berulang kali tanpa membuat artefak. Filter "tidak stabil" jika membuat artefak yang diperkuat dengan penggunaan berulang dan akhirnya menghancurkan gambar.
Saya ulangi, saya tidak mengerti mengapa topik ini tidak dipertimbangkan dalam literatur tentang codec video atau pemrosesan gambar. Mungkin menggunakan terminologi yang berbeda, tetapi saya belum pernah bertemu. Konsep "umpan balik" sudah mapan di bidang bekerja dengan suara. tapi bukan masalah penting dalam pemrosesan gambar. Mungkin karena biasanya filter harus diterapkan hanya sekali?
Jika saya adalah seorang spesialis dalam bidang ini, maka kemungkinan besar saya memiliki pendapat tentang hal ini, dan mungkin saya bahkan akan tahu sudut-sudut literatur khusus di mana sudah ada solusi untuk masalah ini, yang diketahui hanya sedikit. Tetapi, seperti yang saya katakan di awal artikel, saya tidak pernah bisa membuat filter sebelumnya, jadi saya mencari hanya di artikel terkenal (walaupun perlu dicatat bahwa setidaknya ada satu orang yang terkenal dalam literatur yang juga belum pernah mendengar hal seperti ini) )
Jadi, di pagi hari mereka memberi tahu saya bahwa kami membutuhkan filter ini, dan sepanjang hari saya mencoba membuatnya. Pendekatan saya sederhana: Saya membuat program yang mengeksekusi filter ratusan kali dan pada akhirnya menghasilkan gambar sehingga saya bisa melihat hasil dari proses yang panjang. Kemudian saya bereksperimen dengan koefisien filter yang berbeda dan mengamati hasilnya. Itu benar-benar proses percobaan dan kesalahan terarah.
Sekitar satu jam kemudian, saya mengambil koefisien filter terbaik yang cocok untuk tugas ini (tetapi mereka memiliki satu kelemahan, yang akan saya bahas di bagian kedua artikel):
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};
Inti ini berada di ambang penajaman dan pengaburan. Karena penajaman selalu mengarah pada umpan balik yang menciptakan artefak yang jelas dan jelas, inti filter ini lebih memilih sedikit blur sehingga gambar hanya terlihat sedikit lebih “membosankan”.
Ini adalah tampilannya setelah 60 frame. Untuk referensi, saya menunjukkan semua filter dalam urutan ini: gambar asli (tanpa filter), filter saya, bilinear, Lanczos, h.264, HEVC:
Seperti yang Anda lihat, filter saya memberikan hasil yang sedikit lebih buram daripada mempertajam filter, tetapi tidak memiliki artefak ketajaman yang tidak dapat diterima setelah 60 frame. Namun, Anda dapat memilih blur artefak untuk mempertajam artefak, sehingga Anda dapat memilih di antara filter penajam terbaik (Lanczos) dan tambang. Namun, jika kami menambah jumlahnya menjadi 120 bingkai, maka filter saya keluar dari persaingan:
Setelah 300 bingkai, semua filter, kecuali milikku, menjadi seperti lelucon buruk:
Setelah 600 frame, lelucon itu menjadi lebih kejam:
Anda bahkan tidak perlu mengatakan apa yang terjadi setelah 900 frame:
Seberapa stabil itu?
Pada tahap ini, secara alami akan bertanya-tanya: apakah filter saya
benar-benar stabil, atau itu hanya blur yang sangat lambat, jauh lebih lambat daripada filter bilinear? Mungkin setelah ribuan pengulangan, filter saya
secara bertahap akan mengaburkan gambar?
Anehnya, jawabannya tampaknya negatif. Meskipun sedikit blur ditambahkan selama sekitar seratus overlay pertama, sepertinya filter
menyatu dengan representasi gambar yang stabil, yang kemudian
tidak pernah mengalami degradasi. Berikut ini gambar lain yang diperbesar dari mata burung walrus:
Dari kiri ke kanan: gambar asli, filter saya diterapkan 60 kali, 120 kali, 300 kali, 600 dan 900 kali. Seperti yang Anda lihat, keburaman menyatu ke kondisi stabil, yang tidak lagi menurun bahkan setelah ratusan hamparan filter. Sebagai kontras, bandingkan ini dengan sinkronisasi berjendela untuk jumlah sampel yang sama (ketuk), dan lihat seberapa buruk (dan cepat!) Artefak membentuk umpan balik dan membuat hasil yang tidak berguna:
Filter saya tampaknya sangat stabil, dan dibandingkan dengan semua filter yang saya lihat, ini menciptakan hasil terbaik setelah penggunaan berulang. Tampaknya ia memiliki properti "asimptotik" tertentu, di mana data dengan cepat menyatu dengan gambar yang dihaluskan (terbatas), dan kemudian gambar yang dihaluskan ini disimpan dan tidak melakukan degradasi tanpa batas untuk menyelesaikan sampah.
Saya bahkan mencoba menerapkan filter
sejuta kali, dan tampaknya setelah beberapa ratus overlay pertama, itu tidak menurun lebih jauh. Tanpa analisis matematis yang lebih baik (dan saya belum menemukan solusi matematika yang dapat membuktikannya dengan tepat, tetapi saya tahu pasti bahwa itu ada di suatu tempat), saya tidak dapat mengatakan dengan pasti bahwa di suatu tempat setelah miliaran atau triliunan lapisan yang -itu tidak akan rusak. Dalam pengujian yang wajar, saya tidak dapat mendeteksi degradasi lebih lanjut.
Apakah ini merupakan filter Halfpel stabil terbaik untuk enam ketuk?
Pada tahap ini, masuk akal untuk mengajukan pertanyaan: apakah ini benar-benar yang terbaik yang dapat ditemukan? Intuition memberi tahu kami bahwa itu bukan, karena saya sama sekali tidak memiliki pengetahuan tentang pengembangan filter dan hampir tidak melihat literatur, saya mengambil filter ini hanya dalam satu jam. Paling tidak dapat
diasumsikan bahwa setelah studi singkat seperti itu, saya tidak akan menemukan filter definitif-best-all-conquering-great.
Apakah asumsi ini benar? Dan jika benar,
apa yang akan menjadi filter terbaik akhir? Saya akan membahas ini secara lebih rinci di bagian kedua artikel ini.