Bagaimana PNG lossless mengingat bahwa ia memiliki parameter kompresi?

File PNG dikatakan menggunakan kompresi lossless. Namun, setiap kali saya berada di editor gambar, seperti GIMP dan mencoba untuk menyimpan gambar sebagai file PNG, ia meminta parameter kompresi, yang berkisar antara 0 dan 9. Jika memiliki parameter kompresi yang mempengaruhi presisi visual dari gambar terkompresi, bagaimana cara membuat PNG lossless?

Apakah saya mendapatkan perilaku lossless hanya ketika saya mengatur parameter kompresi ke 9?

PNG tidak rugi. GIMP kemungkinan besar tidak menggunakan kata terbaik dalam hal ini. Anggap saja sebagai "kualitas kompresi", atau dengan kata lain, "tingkat kompresi". Dengan kompresi yang lebih rendah, Anda mendapatkan file yang lebih besar, tetapi membutuhkan waktu lebih sedikit untuk menghasilkan, sedangkan dengan kompresi yang lebih tinggi, Anda mendapatkan file yang lebih kecil yang membutuhkan waktu lebih lama untuk diproduksi. Biasanya Anda mendapatkan pengembalian yang berkurang (yaitu, tidak terlalu banyak penurunan ukuran dibandingkan dengan peningkatan waktu yang diperlukan) ketika naik ke tingkat kompresi tertinggi, tetapi terserah Anda.

PNG dikompresi, tetapi tanpa kehilangan

Level kompresi adalah pertukaran antara ukuran file dan kecepatan encoding / decoding. Untuk terlalu menggeneralisasi, bahkan format non-gambar, seperti FLAC, memiliki konsep serupa.

Level kompresi berbeda, output dekode yang sama

Meskipun ukuran file berbeda, karena tingkat kompresi yang berbeda, output yang didekode sebenarnya akan identik.

Anda dapat membandingkan hash MD5 dari output yang diterjemahkan dengan ffmpegmenggunakan muxer MD5 .

Ini paling baik ditunjukkan dengan beberapa contoh:

Buat file PNG:

$ ffmpeg -i input -vframes 1 -compression_level 0 0.png
$ ffmpeg -i input -vframes 1 -compression_level 100 100.png

• Secara default ffmpegakan digunakan -compression_level 100untuk output PNG.

Bandingkan ukuran file:

$ du -h *.png
  228K    0.png
  4.0K    100.png

Dekode file PNG dan tampilkan hash MD5:

$ ffmpeg -loglevel error -i 0.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

$ ffmpeg -loglevel error -i 100.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

Karena kedua hash adalah sama, Anda dapat yakin bahwa output yang di-decode (video mentah yang tidak dikompresi) persis sama.

Kompresi PNG terjadi dalam dua tahap.

1. Pra-kompresi mengatur ulang data gambar sehingga akan lebih kompresibel oleh algoritma kompresi tujuan umum.
2. Kompresi aktual dilakukan oleh DEFLATE, yang mencari, dan menghilangkan urutan byte duplikat dengan menggantinya dengan token pendek.

Karena langkah 2 adalah tugas yang sangat intensif waktu / sumber daya, pustaka zlib yang mendasarinya (enkapsulasi DEFLATE mentah) mengambil parameter kompresi mulai dari 1 = kompresi tercepat, 9 = kompresi terbaik, 0 = tidak ada kompresi. Di situlah rentang 0-9 berasal, dan GIMP hanya melewatkan parameter itu ke zlib. Perhatikan bahwa pada level 0 png Anda sebenarnya akan sedikit lebih besar dari bitmap yang setara.

Namun, level 9 hanyalah "terbaik" yang akan dicoba zlib, dan masih merupakan solusi kompromi .
Untuk benar-benar merasakan hal ini, jika Anda ingin menghabiskan daya pemrosesan 1000x lebih banyak pada pencarian yang lengkap, Anda bisa mendapatkan kepadatan data 3-8% lebih tinggi menggunakan zopfli bukan zlib.
Kompresi masih lossless, itu hanya representasi data DEFLATE yang lebih optimal. Ini mendekati batas pustaka yang kompatibel dengan zlib, dan karenanya merupakan kompresi "terbaik" sesungguhnya yang mungkin dicapai menggunakan PNG.

Motivasi utama untuk format PNG adalah untuk menciptakan pengganti GIF yang tidak hanya gratis tetapi juga perbaikan di atasnya dalam semua hal. Akibatnya, kompresi PNG benar-benar lossless - yaitu, data gambar asli dapat direkonstruksi dengan tepat, sedikit demi sedikit - sama seperti pada GIF dan sebagian besar bentuk TIFF.

PNG menggunakan proses kompresi 2-tahap:

1. Pra-kompresi: pemfilteran (prediksi)
2. Kompresi: DEFLATE (lihat wikipedia )

Langkah precompression disebut filtering, yang merupakan metode mengubah data gambar secara reversibel sehingga mesin kompresi utama dapat beroperasi lebih efisien.

Sebagai contoh sederhana, pertimbangkan urutan byte meningkat secara seragam dari 1 menjadi 255:

1, 2, 3, 4, 5, .... 255

Karena tidak ada pengulangan dalam urutan, itu memampatkan sangat buruk atau tidak sama sekali. Namun modifikasi sepele dari urutan - yaitu, meninggalkan byte pertama saja tetapi mengganti setiap byte berikutnya dengan perbedaan antara itu dan pendahulunya - mengubah urutan menjadi set yang sangat kompresibel:

1, 1, 1, 1, 1, .... 1

Transformasi di atas adalah lossless, karena tidak ada byte yang dihilangkan, dan sepenuhnya reversibel. Ukuran terkompresi dari seri ini akan jauh berkurang, tetapi seri asli masih dapat disusun kembali dengan sempurna.

Gambar-data aktual jarang sesempurna itu, tetapi pemfilteran memang meningkatkan kompresi dalam gambar skala abu-abu dan warna, dan dapat membantu pada beberapa gambar palet juga. PNG mendukung lima jenis filter, dan pembuat enkode dapat memilih untuk menggunakan filter yang berbeda untuk setiap baris piksel dalam gambar:

Algoritma ini bekerja pada byte, tetapi untuk piksel besar (misalnya, 24-bit RGB atau 64-bit RGBA) hanya byte yang sesuai yang dibandingkan, artinya komponen merah dari warna-piksel ditangani secara terpisah dari komponen piksel hijau dan biru.

Untuk memilih filter terbaik untuk setiap baris, pembuat enkode harus menguji semua kemungkinan kombinasi. Ini jelas tidak mungkin, karena bahkan gambar 20-baris akan membutuhkan pengujian lebih dari 95 triliun kombinasi, di mana "pengujian" akan melibatkan penyaringan dan kompresi seluruh gambar.

Tingkat kompresi biasanya didefinisikan sebagai angka antara 0 (tidak ada) dan 9 (terbaik). Ini merujuk pada pengorbanan antara kecepatan dan ukuran, dan berkaitan dengan berapa banyak kombinasi filter baris yang akan dicoba. Tidak ada standar mengenai tingkat kompresi ini, sehingga setiap editor gambar dapat memiliki algoritma sendiri untuk berapa banyak filter untuk mencoba ketika mengoptimalkan ukuran gambar.

Level kompresi 0 berarti filter tidak digunakan sama sekali, yang cepat tetapi boros. Level yang lebih tinggi berarti semakin banyak kombinasi yang dicoba pada baris gambar dan hanya yang terbaik yang dipertahankan.

Saya akan menebak bahwa pendekatan paling sederhana untuk kompresi terbaik adalah secara bertahap menguji-kompres setiap baris dengan setiap filter, simpan hasil terkecil, dan ulangi untuk baris berikutnya. Ini sama dengan menyaring dan mengompresi seluruh gambar lima kali, yang mungkin merupakan trade-off yang wajar untuk gambar yang akan dikirim dan didekodekan berkali-kali. Nilai kompresi yang lebih rendah akan melakukan lebih sedikit, sesuai kebijakan pengembang alat.

Selain filter, level kompresi juga dapat memengaruhi level kompresi zlib yang merupakan angka antara 0 (tanpa Deflate) dan 9 (Deflate maksimum). Bagaimana level 0-9 yang ditentukan memengaruhi penggunaan filter, yang merupakan fitur optimisasi utama PNG, masih bergantung pada pengembang alat.

Kesimpulannya adalah bahwa PNG memiliki parameter kompresi yang dapat mengurangi ukuran file dengan sangat signifikan, semua tanpa kehilangan bahkan satu piksel pun.

Sumber:

Dokumentasi Wikipedia Portable Network Graphics
libpng Bab 9 - Kompresi dan Penyaringan

OK, saya terlambat untuk hadiah itu, tapi ini jawaban saya.

PNG selalu lossless . Menggunakan algoritma Deflate / Inflate, mirip dengan yang digunakan dalam program zip.

Algoritma Deflate mencari urutan byte berulang dan menggantikannya dengan tag. Pengaturan level kompresi menentukan berapa banyak upaya yang digunakan program untuk menemukan kombinasi optimal dari urutan byte, dan berapa banyak memori yang disediakan untuk itu. Ini adalah kompromi antara waktu dan penggunaan memori vs ukuran file terkompresi. Namun, komputer modern sangat cepat dan memiliki cukup memori sehingga jarang perlu menggunakan selain pengaturan kompresi tertinggi.

Banyak implementasi PNG menggunakan pustaka zlib untuk kompresi. Zlib memiliki sembilan level kompresi, 1-9. Saya tidak tahu bagian dalam Gimp, tetapi karena memiliki pengaturan tingkat kompresi 0-9 (0 = tanpa kompresi), saya akan menganggap pengaturan ini hanya memilih tingkat kompresi zlib.

Algoritma Deflate adalah algoritma kompresi tujuan umum , belum dirancang untuk mengompresi gambar. Tidak seperti kebanyakan format file gambar lossless lainnya, format PNG tidak terbatas pada itu. Kompresi PNG mengambil keuntungan dari pengetahuan bahwa kita mengompresi gambar 2D . Ini dicapai dengan filter yang disebut .

(Filter sebenarnya adalah istilah yang agak menyesatkan di sini. Itu sebenarnya tidak mengubah konten gambar, itu hanya kode itu berbeda. Nama yang lebih akurat akan menjadi delta encoder.)

Spesifikasi PNG menentukan 5 filter berbeda (termasuk 0 = tidak ada). Filter menggantikan nilai piksel absolut dengan perbedaan dari piksel sebelumnya ke kiri, atas, diagonal, atau kombinasi keduanya. Ini secara signifikan dapat meningkatkan rasio kompresi. Setiap garis pindai pada gambar dapat menggunakan filter yang berbeda. Encoder dapat mengoptimalkan kompresi dengan memilih filter terbaik untuk setiap baris.

Untuk detail format file PNG, lihat Spesifikasi PNG .

Karena jumlah kombinasi yang hampir tak terbatas, tidak mungkin untuk mencoba semuanya. Oleh karena itu, berbagai jenis strategi telah dikembangkan untuk menemukan kombinasi yang efektif. Kebanyakan editor gambar mungkin bahkan tidak mencoba untuk mengoptimalkan filter baris demi baris tetapi hanya menggunakan filter tetap (kemungkinan besar Paeth).

Program command line pngcrush mencoba beberapa strategi untuk menemukan hasil terbaik. Ini dapat secara signifikan mengurangi ukuran file PNG yang dibuat oleh program lain, tetapi mungkin butuh sedikit waktu pada gambar yang lebih besar. Lihat Sumber Forge - pngcrush .

Tingkat kompresi dalam hal lossless selalu hanya memperdagangkan sumber daya enkode (biasanya waktu, terkadang juga RAM) vs. bitrate. Kualitas selalu 100%.

Tentu saja, kompresor lossless TIDAK PERNAH dapat menjamin kompresi yang sebenarnya. Data acak tidak dapat dimampatkan, tidak ada pola untuk ditemukan dan tidak ada kesamaan. Teori informasi Shannon dan semua itu. Inti dari kompresi data lossless adalah bahwa manusia biasanya bekerja dengan data yang sangat non-acak, tetapi untuk transmisi dan penyimpanan, kita dapat memampatkannya menjadi bit sesedikit mungkin. Semoga sampai sedekat mungkin dengan kompleksitas Kolmogorov yang asli.

Apakah itu zip atau data generik 7z, gambar png, audio flac, atau video h.264 (dalam mode lossless), itu adalah hal yang sama. Dengan beberapa algoritma kompresi, seperti lzma (7zip) dan bzip2, memiringkan pengaturan kompresi akan meningkatkan waktu CPU DECODER (bzip2) atau lebih sering hanya jumlah RAM yang dibutuhkan (lzma dan bzip2, dan h.264 dengan lebih banyak frame referensi) . Seringkali decoder harus menyimpan lebih banyak keluaran yang didekodekan dalam RAM karena mendekode byte berikutnya dapat merujuk ke byte yang diterjemahkan banyak megabita yang lalu (mis. Frame video yang paling mirip dengan satu dari setengah detik yang lalu akan dikodekan dengan referensi ke 12 frame kembali ). Hal yang sama dengan bzip2 dan memilih ukuran blok besar, tetapi itu juga lebih lambat terurai. lzma memiliki kamus ukuran variabel, dan Anda dapat membuat file yang membutuhkan 1.

Pertama, PNG selalu lossless. Paradoks yang jelas adalah karena fakta bahwa ada dua jenis kompresi yang mungkin (untuk semua jenis data): lossy dan lossless.

Kompresi lossless meremas data (yaitu ukuran file) menggunakan berbagai trik, menjaga semuanya dan tanpa membuat perkiraan apa pun. Akibatnya, ada kemungkinan kompresi lossless tidak akan benar-benar dapat mengompres semuanya. (Secara teknis data dengan entropi tinggi bisa sangat sulit atau bahkan tidak mungkin untuk dikompresi untuk metode lossless.) Kompresi lossy mendekati data nyata, tetapi perkiraannya tidak sempurna, tetapi "membuang" presisi ini memungkinkan biasanya kompresi yang lebih baik.

Berikut ini adalah contoh sepele dari kompresi lossless: jika Anda memiliki gambar yang terbuat dari 1.000 piksel hitam, alih-alih menyimpan nilai hitam 1.000 kali, Anda dapat menyimpan hitungan (1000) dan nilai (hitam) sehingga mengompresi 1000 piksel " image "menjadi hanya dua angka. (Ini adalah bentuk kasar dari metode kompresi lossless yang disebut run-length encoding).