Yang merupakan batas data kompresi lossless? (jika ada batas seperti itu)

Akhir-akhir ini saya telah berurusan dengan algoritma yang berhubungan dengan kompresi, dan saya bertanya-tanya mana yang merupakan rasio kompresi terbaik yang dapat dicapai dengan kompresi data lossless.

Sejauh ini, satu-satunya sumber yang dapat saya temukan tentang topik ini adalah Wikipedia:

Kompresi data digital yang tanpa kehilangan seperti video, film digital, dan audio menjaga semua informasi, tetapi jarang dapat melakukan jauh lebih baik daripada kompresi 1: 2 karena entropi intrinsik data.

Sayangnya, artikel Wikipedia tidak mengandung referensi atau kutipan untuk mendukung klaim ini. Saya bukan ahli kompresi data, jadi saya menghargai informasi apa pun yang dapat Anda berikan tentang masalah ini, atau jika Anda dapat mengarahkan saya ke sumber yang lebih andal daripada Wikipedia.

Saya tidak yakin apakah ada yang belum menjelaskan mengapa angka ajaib tampaknya tepat 1: 2 dan tidak, misalnya, 1: 1.1 atau 1:20.

Salah satu alasannya adalah bahwa dalam banyak kasus hampir setengah dari data digital adalah noise , dan noise (menurut definisi) tidak dapat dikompres.

Saya melakukan percobaan yang sangat sederhana:

• Saya mengambil kartu abu - abu . Bagi mata manusia, itu terlihat seperti selembar karton abu-abu yang polos dan netral. Secara khusus, tidak ada informasi .

• Dan kemudian saya mengambil pemindai normal - persis jenis perangkat yang mungkin digunakan orang untuk mendigitalkan foto mereka.

• Saya memindai kartu abu-abu. (Sebenarnya, saya memindai kartu abu-abu bersama-sama dengan kartu pos. Kartu pos itu ada untuk memeriksa kewarasan sehingga saya bisa memastikan perangkat lunak pemindai tidak melakukan sesuatu yang aneh, seperti secara otomatis menambah kontras ketika melihat kartu abu-abu yang tidak berguna.)

• Saya memotong bagian 1000x1000 piksel kartu abu-abu, dan mengubahnya menjadi abu-abu (8 bit per piksel).

Apa yang kita miliki sekarang harus menjadi contoh yang cukup baik tentang apa yang terjadi ketika Anda mempelajari bagian tanpa fitur dari foto hitam putih yang dipindai , misalnya, langit cerah. Pada prinsipnya, seharusnya tidak ada yang terlihat.

Namun, dengan perbesaran yang lebih besar, sebenarnya terlihat seperti ini:

Tidak ada pola yang terlihat jelas, tetapi tidak memiliki warna abu-abu yang seragam. Bagian dari itu kemungkinan besar disebabkan oleh ketidaksempurnaan kartu abu-abu, tetapi saya akan berasumsi bahwa sebagian besar itu hanyalah noise yang dihasilkan oleh pemindai (noise termal di sel sensor, amplifier, konverter A / D, dll.). Terlihat sangat mirip suara Gaussian; di sini adalah histogram (dalam skala logaritmik ):

Sekarang jika kita mengasumsikan bahwa setiap piksel memiliki warna yang dipilih dari distribusi ini, berapa banyak entropi yang kita miliki? Skrip Python saya memberi tahu saya bahwa kami memiliki entropi sebanyak 3,3 bit per piksel . Dan itu banyak kebisingan.

Jika ini benar-benar kasusnya, itu akan menyiratkan bahwa tidak peduli algoritma kompresi yang kita gunakan, bitmap 1000x1000 piksel akan dikompresi, dalam kasus terbaik, menjadi file 412500-byte. Dan apa yang terjadi dalam praktek: Saya mendapat file PNG 432018-byte, cukup dekat.

Jika kita menggeneralisasi sedikit, tampaknya tidak peduli foto hitam putih mana yang saya pindai dengan pemindai ini, saya akan mendapatkan jumlah berikut ini:

• informasi "berguna" (jika ada),
• kebisingan, kira-kira. 3 bit per piksel.

Sekarang bahkan jika algoritma kompresi Anda meremas informasi yang berguna menjadi << 1 bit per piksel, Anda masih akan memiliki sebanyak 3 bit per pixel dari kebisingan yang tidak dapat dikompres. Dan versi terkompresi adalah 8 bit per piksel. Jadi rasio kompresi akan menjadi rata-rata 1: 2, apa pun yang Anda lakukan.

Contoh lain, dengan upaya untuk menemukan kondisi yang terlalu ideal:

• Kamera DSLR modern, menggunakan pengaturan sensitivitas terendah (paling sedikit noise).
• Bidikan kartu abu-abu yang tidak fokus (bahkan jika ada beberapa informasi yang terlihat dalam kartu abu-abu, itu akan kabur).
• Konversi file RAW menjadi gambar abu-abu 8-bit, tanpa menambahkan kontras. Saya menggunakan pengaturan khas dalam konverter RAW komersial. Konverter mencoba mengurangi noise secara default. Selain itu, kami menyimpan hasil akhir sebagai file 8-bit - pada dasarnya, kami membuang bit urutan terendah dari pembacaan sensor mentah!

Dan apa hasil akhirnya? Terlihat jauh lebih baik daripada yang saya dapatkan dari pemindai; kebisingan kurang diucapkan, dan tidak ada yang terlihat. Namun demikian, suara Gaussian ada di sana:

Dan entropinya? 2,7 bit per piksel . Ukuran file dalam praktek? 344923 byte untuk 1M piksel. Dalam skenario kasus terbaik, dengan beberapa kecurangan, kami mendorong rasio kompresi menjadi 1: 3.

Tentu saja semua ini tidak ada hubungannya dengan penelitian TCS, tapi saya pikir baik untuk mengingat apa yang sebenarnya membatasi kompresi data digital dunia nyata. Kemajuan dalam desain algoritma kompresi yang lebih canggih dan daya CPU mentah tidak akan membantu; jika Anda ingin menyimpan semua kebisingan tanpa kehilangan, Anda tidak dapat melakukan jauh lebih baik daripada 1: 2.

Apakah Anda sudah tahu tentang teorema pengkodean berisik dari Shannon ? Teorema ini menetapkan batas teoritis pada kompresi lossless. Beberapa komentar dari yang lain tampaknya menganggap Anda tahu tentang teorema ini, tetapi dari pertanyaan, saya pikir itu mungkin jawaban yang Anda cari.

$n>0$

1. $n$

2. Solusi praktis yang umum adalah menggunakan 8 bit, jika satu-satunya bilangan bulat yang akan Anda encode adalah semua antara 1 dan 256 (digeneralisasi menjadi 16, 32 dan 64 bit jika Anda mau).

3. $n+1$$n$$n$

4. $\lceil\log_2 n\rceil$$\lceil\log_2 n\rceil+1$$n$$\lceil\log_2 n\rceil-1$ (Anda tidak perlu bit paling kiri, yang selalu satu, karena Anda sudah tahu nilainya $\lceil\log_2 n\rceil$). Pengkodean ini digunakan secara total$2\lceil\log_2 n\rceil-1$ bit, dan merupakan kompresi berguna $n$, sering digunakan dalam latihan. (Perhatikan bahwa dalam literatur Anda akan menemukan hasil-hasil tersebut dicatat$\lg n=\max(1,\lceil\log_2 n\rceil)$ untuk membuat notasi lebih pendek.)

5. Kode gamma tidak optimal , dalam arti ada kode lain yang menggunakan lebih sedikit ruang untuk banyak bilangan bulat, dan lebih banyak hanya untuk jumlah yang terbatas. Bacaan yang sangat baik tentang topik ini adalah "Algoritma yang hampir optimal untuk pencarian tanpa batas" oleh Jon Louis Bentley dan Andrew Chi-Chih Yao dari tahun 1976 (Saya suka khususnya hubungan mereka antara kompleksitas algoritma pencarian dan ukuran pengkodean bilangan bulat: I temukan salah satu hasil TCS paling sederhana dan indah yang saya tahu). Intinya adalah itu$2\lceil\log_2 n\rceil-1$ bit berada dalam faktor dua yang optimal, yang sebagian besar cukup dalam praktiknya mengingat kompleksitas dari solusi yang lebih baik.

6. Namun, dengan mengambil pendekatan "oportunistik" hingga batasnya, ada sejumlah skema kompresi yang memanfaatkan berbagai hipotesis. Salah satu cara untuk berurusan dengan penyandian oportunistik tak terhingga ini (yaitu skema kompresi) adalah dengan meminta penyandian hipotesis itu sendiri, dan untuk memperhitungkan ukuran penyandian hipotesis dalam ukuran kompresi total. Secara formal, ini sesuai untuk menyandikan data terkompresi dan dekoder , atau lebih umum untuk menyandikan program yang, ketika dieksekusi, mengeluarkan objek yang tidak terkompresi: ukuran terkecil dari program semacam itu disebut kompleksitas Kolmogorov $K$. Ini adalah konstruksi yang sangat teoretis dalam arti bahwa, tanpa terikat pada waktu pelaksanaan program,$K$tidak dapat dihitung. Sebuah solusi yang mudah di sekitar gagasan ini diberikan oleh program pembatasan diri Levin , di mana Anda hanya mempertimbangkan program dengan waktu eksekusi yang dibatasi (misalnya, dalam faktor konstan dari panjang instance asli, yang merupakan batas bawah pada kompleksitas algoritma yang perlu ditulis setiap simbol).

Ada seluruh komunitas yang bekerja tentang kompleksitas Kolmogorov dan variannya, dan komunitas lain yang bekerja pada kompresi loss-less (contoh pada bilangan bulat yang saya gunakan setara dengan banyak tipe data lainnya), saya nyaris tidak menggaruk permukaan, dan yang lain mungkin menambahkan precision (Kolmogorov benar-benar bukan keahlian saya), tapi saya harap ini dapat membantu Anda mengklarifikasi pertanyaan Anda, jika tidak selalu memberi Anda jawaban yang Anda harapkan :)

(hanya perpanjangan dari komentar saya)

(Seperti yang ditunjukkan oleh Joe dalam jawabannya) Shannon - dalam makalahnya tahun 1948, " Teori Komunikasi Matematika " merumuskan teori kompresi data dan menetapkan bahwa ada batas mendasar untuk kompresi data lossless. Batas ini, yang disebut tingkat entropi, dilambangkan dengan H. Nilai tepat H bergantung pada sumber informasi --- lebih khusus lagi, sifat statistik dari sumber tersebut. Dimungkinkan untuk mengompresi sumber, dengan cara lossless, dengan laju kompresi mendekati H. Secara matematis tidak mungkin dilakukan lebih baik daripada H.

Namun beberapa kelas gambar (misalnya gambar skala medis) tanpa tepi kontras tinggi dan dengan transisi level halus dapat dikompresi (tidak begitu efisien).

JPEG-LS dan JPEG2000 tampaknya menjadi standar untuk penyimpanan gambar medis yang tidak hilang. Lihat tabel ini untuk perbandingan rasio kompresi (JPEG-LS mencapai kompresi yang sedikit lebih baik).

Menggunakan "kompresi gambar medis lossless" saya menemukan artikel berikut yang dapat membantu Anda:

Survei terbaru (2011) tentang teknik kompresi gambar medis: Teknik Kompresi Gambar Medis Dua Dimensi - Survei

... Makalah ini menyajikan ikhtisar dari berbagai teknik kompresi berdasarkan DCT, DWT, ROI dan Neural Networks untuk gambar medis dua dimensi (2D).

Presentasi terperinci dari dua algoritma kompresi lossless standar: JPEG-LS dan JPG2000 dalam mode lossless: Kompresi Lossless dari Gambar Medis Grayscale - Keefektifan Pendekatan Tradisional dan Seni.

... Tiga ribu, enam ratus tujuh puluh sembilan (3.679) gambar grayscale bingkai tunggal dari berbagai wilayah anatomi, modalitas dan vendor, diuji. ...

Survei lain: Survei Teknik Kompresi Gambar Medis Kontemporer

EDIT

Mungkin Anda masih bertanya-tanya, "Apa entropi sebuah gambar?" ... OK, jumlah informasi yang terkandung dalam gambar ... tetapi untuk lebih memahaminya, Anda harus membaca sesuatu tentang 3 fase yang biasanya digunakan dalam kompresi gambar :

• transformasi (misalnya Transformasi Wavelet Diskrit)
• kuantisasi
• pengkodean entropi

Anda dapat menggunakan Google untuk mencari tutorial atau buku tentang kompresi Gambar (misalnya tutorial singkat ), atau mencoba menonton video teknis online (misalnya Kuliah 16 - Pengantar Pengkodean Gambar dan Video ).

Pikirkan file sebagai string.

Anda tidak akan pernah bisa lebih baik daripada kompleksitas string Kolmogorov (ini adalah definisi kompleksitas Komogorov).

Perbaiki panjang string. Jadi sekarang kita hanya melihat untaian panjang n.

Setengah dari semua string semacam itu dapat dikompresi paling banyak 1 bit. 1/4 dari semua string dapat dikompresi paling banyak 2 bit. 1/8 dari semua string semacam itu dapat dikompresi paling banyak 3 bit.

Jadi, fraksi string apa (gambar, file, dll.) Dapat dikompres dengan rasio 2: 1 - sangat, sangat sedikit. Jadi mengapa kompresi pernah berhasil? Karena hampir semua data yang benar-benar orang coba kompres sangat terstruktur - itu tidak terlihat seperti file acak. Semakin acak mencari data, semakin sulit untuk kompres. Mereka berjalan beriringan. Sebagian besar string terlihat acak.

Untuk melihat ini dalam tindakan, buat file acak menggunakan beberapa proses acak. Maksud saya file yang benar-benar acak. Sekarang coba kompres dengan menggunakan algoritma kompresi favorit Anda. Ukurannya akan tetap sama atau semakin besar, hampir sepanjang waktu.

Di sisi lain, ada string yang sangat kompresif. Ambil string berikut: 100000..000 (1 diikuti oleh satu juta nol). Deskripsi itu cocok dengan kalimat sebelumnya, dan komputer dapat merekonstruksi dari deskripsi itu (atau yang sangat mirip). Namun, deskripsi itu sama sekali tidak memiliki jutaan angka.

Faktanya adalah string dengan properti itu (karena sangat kompresibel) sangat jarang di antara semua string yang mungkin. Fakta sekunder adalah bahwa hampir semua data yang dihasilkan manusia adalah super, super kompresibel karena sangat terstruktur.