Berdasarkan tantangan penyandian gambar Twitter yang sangat sukses di Stack Overflow.
Jika suatu gambar bernilai 1000 kata, berapa banyak gambar yang bisa Anda masukkan dalam 114,97 byte?
Saya menantang Anda untuk membuat metode tujuan umum untuk memampatkan gambar menjadi komentar Twitter standar yang hanya berisi teks ASCII yang dapat dicetak .
Aturan:
- Anda harus menulis sebuah program yang dapat mengambil gambar dan menampilkan teks yang disandikan.
- Teks yang dibuat oleh program harus paling panjang 140 karakter dan hanya boleh berisi karakter yang titik kodenya berada dalam kisaran 32-126, inklusif.
- Anda harus menulis sebuah program (mungkin program yang sama) yang dapat mengambil teks yang disandikan dan mengeluarkan versi foto yang diterjemahkan.
- Program Anda dapat menggunakan perpustakaan dan file eksternal, tetapi tidak dapat memerlukan koneksi internet atau koneksi ke komputer lain.
- Proses decoding tidak dapat mengakses atau memuat gambar asli dengan cara apa pun.
- Program Anda harus menerima gambar dalam setidaknya satu dari format ini (tidak harus lebih): Bitmap, JPEG, GIF, TIFF, PNG. Jika beberapa atau semua gambar sampel tidak dalam format yang benar, Anda dapat mengonversinya sendiri sebelum kompresi oleh program Anda.
Menilai:
Ini adalah tantangan yang agak subyektif, jadi pemenangnya (pada akhirnya) akan dinilai oleh saya. Saya akan memfokuskan penilaian saya pada beberapa faktor penting, yang tercantum di bawah ini dalam penurunan pentingnya:
- Kemampuan untuk melakukan pekerjaan yang wajar untuk mengompresi berbagai gambar, termasuk yang tidak terdaftar sebagai sampel gambar
- Kemampuan untuk mempertahankan garis besar elemen utama dalam suatu gambar
- Kemampuan untuk mengompresi warna elemen utama dalam suatu gambar
- Kemampuan untuk mempertahankan garis besar dan warna detail kecil dalam suatu gambar
- Waktu kompresi. Meskipun tidak sepenting seberapa baik gambar dikompresi, program yang lebih cepat lebih baik daripada program yang lebih lambat yang melakukan hal yang sama.
Kiriman Anda harus menyertakan gambar yang dihasilkan setelah dekompresi, bersama dengan komentar Twitter yang dihasilkan. Jika memungkinkan, Anda juga bisa memberikan tautan ke kode sumber.
Contoh gambar:
The Hindenburg , Pemandangan Pegunungan , Mona Lisa , Bentuk 2D
Jawaban:
Saya telah meningkatkan metode saya dengan menambahkan kompresi yang sebenarnya. Sekarang beroperasi dengan iteratif melakukan hal berikut:
Perkecil gambar yang mempertahankan rasio aspek (jika gambar berwarna, kroma diambil sampelnya 1/3 lebar & tinggi pencahayaan)
Kurangi kedalaman bit hingga 4 bit per sampel
Terapkan prediksi median ke gambar, membuat distribusi sampel lebih seragam
Terapkan kompresi rentang adaptif ke gambar.
Lihat apakah ukuran gambar yang dikompresi adalah <= 112
Gambar terbesar yang sesuai dengan 112 byte kemudian digunakan sebagai gambar akhir, dengan sisa dua byte digunakan untuk menyimpan lebar & tinggi gambar yang dikompresi, ditambah bendera yang menunjukkan apakah gambar tersebut berwarna. Untuk decoding, prosesnya terbalik, dan gambar ditingkatkan sehingga dimensi yang lebih kecil adalah 128.
Ada beberapa ruang untuk perbaikan, yaitu tidak semua byte yang tersedia digunakan secara khas, tapi saya merasa saya pada titik pengembalian menurun secara signifikan untuk downsampling + kompresi lossless.
Sumber C ++ cepat & kotor
Windows exe
Mona Lisa (pencahayaan 13x20, kroma 4x6)
Hindenburg (pencahayaan 21x13)
Pegunungan (pencahayaan 19x14, 6x4 kroma)
Bentuk 2D (pencahayaan 21x15, kroma 7x5)
sumber
Pergi
Bekerja dengan membagi gambar menjadi daerah secara rekursif. Saya mencoba membagi wilayah dengan konten informasi tinggi, dan memilih garis pemisah untuk memaksimalkan perbedaan warna antara kedua wilayah.
Setiap divisi dikodekan menggunakan beberapa bit untuk mengkodekan garis pemisah. Setiap daerah daun dikodekan sebagai satu warna.
Gambar Hindenburg terlihat sangat jelek, tetapi yang lain saya suka.
sumber
Python
Pengkodean membutuhkan numpy , SciPy dan scikit-image .
Decoding hanya membutuhkan PIL .
Ini adalah metode berdasarkan interpolasi superpixel. Untuk memulai, masing-masing gambar dibagi menjadi 70 daerah berukuran sama dengan warna yang sama. Misalnya, gambar lanskap dibagi dengan cara berikut:
Centroid masing-masing daerah terletak (ke titik raster terdekat pada kisi yang berisi tidak lebih dari 402 titik), serta warna rata-rata (dari palet warna 216), dan masing-masing daerah ini dikodekan sebagai angka dari 0 ke 86832 , mampu disimpan dalam 2,5 karakter ascii yang dapat dicetak (sebenarnya 2,497 , hanya menyisakan cukup ruang untuk disandikan untuk bit skala abu-abu).
Jika Anda perhatian, Anda mungkin telah memperhatikan bahwa 140 / 2.5 = 56 wilayah, dan bukan 70 seperti yang saya sebutkan sebelumnya. Perhatikan, bagaimanapun, bahwa masing-masing daerah ini adalah objek yang unik dan dapat dibandingkan, yang dapat dicantumkan dalam urutan apa pun. Karena itu, kita dapat menggunakan permutasi dari 56 daerah pertama untuk menyandikan 14 lainnya , serta memiliki beberapa bit yang tersisa untuk menyimpan aspek rasio.
Lebih khusus lagi, masing-masing dari 14 wilayah tambahan dikonversi ke angka, dan kemudian masing-masing angka ini digabungkan menjadi satu (mengalikan nilai saat ini dengan 86832 , dan menambahkan yang berikutnya). Angka (raksasa) ini kemudian dikonversi menjadi permutasi pada 56 objek.
Sebagai contoh:
akan menampilkan:
Permutasi yang dihasilkan kemudian diterapkan ke 56 daerah asli. Angka asli (dan dengan demikian 14 daerah tambahan ) juga dapat diekstraksi dengan mengubah permutasi dari 56 daerah yang disandikan menjadi representasi numeriknya.
Ketika
--greyscale
opsi ini digunakan dengan encoder, 94 wilayah digunakan sebagai gantinya (dipisahkan 70 , 24 ), dengan 558 titik raster, dan 16 nuansa abu-abu.Ketika decoding, masing-masing daerah diperlakukan sebagai kerucut 3D yang diperluas hingga tak terbatas, dengan simpulnya di pusat massa daerah, seperti yang dilihat dari atas (alias Diagram Voronoi). Perbatasan kemudian dicampur bersama untuk membuat produk akhir.
Perbaikan di Masa Depan
Dimensi Mona Lisa agak sedikit berbeda, karena cara saya menyimpan aspek rasio. Saya harus menggunakan sistem yang berbeda.Tetap, dengan mengasumsikan bahwa rasio aspek asli berada di antara 1:21 dan 21: 1, yang menurut saya merupakan asumsi yang masuk akal.Hindenburg bisa ditingkatkan banyak. Palet warna yang saya gunakan hanya memiliki 6 warna abu-abu. Jika saya memperkenalkan mode skala abu-abu saja, saya bisa menggunakan informasi tambahan untuk meningkatkan kedalaman warna, jumlah wilayah, jumlah titik raster, atau kombinasi ketiganya.Saya telah menambahkan--greyscale
opsi ke enkoder, yang melakukan ketiganya.Bentuk 2d mungkin akan terlihat lebih baik dengan blending dimatikan. Saya mungkin akan menambahkan bendera untuk itu.Menambahkan opsi encoder untuk mengontrol rasio segmentasi, dan opsi decoder untuk mematikan blending.dan
Yang kedua dikodekan dengan
--greyscale
opsi.Disandikan dengan
--greyscale
opsi.Dikodekan dengan
--ratio 60
, dan diterjemahkan dengan--no-blending
opsi.encoder.py
decoder.py
my_geom.py
sumber
PHP
OK, perlu waktu sebentar, tapi ini dia. Semua gambar dalam skala abu-abu. Warna mengambil terlalu banyak bit untuk dikodekan untuk metode saya: P
Mona Lisa
47 Warna Monokrom string
101 byte.
2D Shapes
36 Colors Monochrome String
105 byte.
Hindenburg
62 Warna Monokrom
112 karakter.
Gunung
63 Warna Monokrom
122 karakter.
Metode saya
Saya menyandikan bitstream saya dengan jenis pengkodean base64. Sebelum disandikan menjadi teks yang dapat dibaca, inilah yang terjadi.
Saya memuat gambar sumber dan mengubah ukurannya ke ketinggian atau lebar maksimum (tergantung pada orientasi, potret / lanskap) dari 20 piksel.
Selanjutnya saya mewarnai ulang setiap piksel gambar baru untuk pencocokan terdekat pada palet abu-abu 6 warna.
Setelah itu selesai, saya membuat string dengan setiap warna piksel diwakili oleh huruf [AF].
Saya kemudian menghitung distribusi 6 huruf berbeda dalam string dan memilih pohon biner yang paling optimal untuk pengkodean berdasarkan frekuensi huruf. Ada 15 kemungkinan pohon biner.
Saya memulai bit stream saya dengan satu bit,
[1|0]
tergantung pada apakah gambarnya tinggi atau lebar. Saya kemudian menggunakan 4 bit berikutnya dalam aliran untuk menginformasikan decoder pohon biner mana yang harus digunakan untuk mendekode gambar.Berikut ini adalah aliran bit yang mewakili gambar. Setiap piksel dan warnanya diwakili oleh 2 atau 3 bit. Ini memungkinkan saya untuk menyimpan setidaknya 2 dan hingga 3 piksel nilai informasi untuk setiap karakter ascii yang dicetak. Berikut ini contoh pohon biner
1110
, yang digunakan oleh Mona Lisa:Huruf E
00
dan F10
adalah warna yang paling umum di Mona Lisa. A010
, B011
, C110
, dan D111
adalah yang paling jarang.Pohon biner bekerja seperti ini: Dari sedikit ke sedikit,
0
berarti ke kiri,1
berarti ke kanan. Terus sampai Anda menabrak daun di pohon, atau jalan buntu. Daun yang Anda dapatkan adalah karakter yang Anda inginkan.Bagaimanapun, saya menyandikan sengatan biner ke dalam karakter base64. Ketika decoding string, proses dilakukan secara terbalik, menugaskan semua piksel ke warna yang sesuai, dan kemudian gambar diskalakan dua kali ukuran disandikan (maksimum 40 piksel baik X atau Y, mana yang lebih besar) dan kemudian matriks konvolusi adalah diterapkan pada semuanya untuk menghaluskan warna.
Bagaimanapun, inilah kode saat ini: " tautan pastebin "
Ini jelek, tetapi jika Anda melihat ada ruang untuk perbaikan, beri tahu saya. Saya meretasnya bersama seperti yang saya inginkan. Saya BELAJAR BANYAK DARI TANTANGAN INI. Terima kasih OP untuk mempostingnya!
sumber
Upaya pertama saya. Ini memiliki ruang untuk perbaikan. Saya pikir format itu sendiri benar-benar berfungsi, masalahnya ada di encoder. Itu, dan saya kehilangan bit individual dari output saya ... file saya (kualitas sedikit lebih tinggi di sini) berakhir di 144 karakter, ketika seharusnya ada beberapa yang tersisa. (dan saya benar-benar berharap ada - perbedaan antara ini dan yang terlihat). Saya belajar, tidak pernah melebih-lebihkan seberapa besar 140 karakter ...
Saya membawanya ke versi modifikasi dari palet RISC-OS - pada dasarnya, karena saya membutuhkan 32 palet warna, dan itu sepertinya tempat yang cukup baik untuk memulai. Ini bisa dilakukan dengan beberapa perubahan juga saya pikir.
Saya memecahnya menjadi bentuk berikut: dan membagi gambar menjadi blok palet (dalam hal ini, 2x2 piksel) dari warna depan dan belakang.
Hasil:
Berikut adalah tweet, aslinya, dan bagaimana tweet itu diterjemahkan
Saya tahu warnanya salah, tapi saya sebenarnya suka Monalisa. Jika saya menghapus blur (yang tidak akan terlalu sulit), itu kesan cubist yang masuk akal: hal
Saya perlu bekerja
Saya akan memberikan beberapa pekerjaan lagi nanti untuk mencoba memperbaikinya, dan meningkatkan encoder. Tambahan 20 karakter atau lebih membuat perbedaan besar. Saya ingin mereka kembali.
Sumber C # dan palet warna ada di https://dl.dropboxusercontent.com/u/46145976/Base96.zip - meskipun, jika dipikir-pikir, mungkin tidak berfungsi dengan sempurna saat dijalankan secara terpisah (karena ruang dalam argumen untuk program tidak berjalan begitu) baik).
Encoder membutuhkan waktu kurang dari beberapa detik pada mesin saya yang cukup rata-rata.
sumber
Saya menyerah untuk mencoba mempertahankan warna dan menjadi hitam dan putih, karena semua yang saya coba dengan warna tidak dapat dikenali.
Pada dasarnya yang dilakukannya adalah membagi piksel menjadi 3 bagian yang kira-kira sama: hitam, abu-abu dan putih. Itu juga tidak menjaga ukuran.
Hindenburg
Mona lisa
Pegunungan
Bentuk
Inilah programnya.
python compress.py -c img.png
kompresimg.png
dan cetak tweet.python compress.py -d img.png
mengambil tweet dari stdin dan menyimpan gambar keimg.png
.sumber
Kontribusi sederhana saya di R:
Idenya adalah hanya untuk mengurangi raster (file harus dalam png) ke matriks yang jumlah selnya lebih rendah dari 140, tweet kemudian merupakan serie warna (dalam 64 warna) didahului oleh dua karakter yang mengindikasikan jumlah baris dan kolom raster.
sumber
Bukan solusi lengkap, hanya menempatkan metode di luar sana. (Matlab)
Saya menggunakan 16 palet warna dan 40 posisi untuk membuat diagram voronoi tertimbang . Algoritma genetik yang digunakan dan algoritma mendaki bukit sederhana agar sesuai dengan gambar.
Album dengan gambar asli dan saya juga memiliki versi 16 byte dengan 4 warna dan posisi tetap di sana. :)
(Bisakah saya mengubah ukuran gambar di sini?)
sumber
C #
Perbarui - Versi 2
Saya melakukan upaya lain dalam hal ini, sekarang menggunakan MagickImage.NET ( https://magick.codeplex.com/ ) untuk menyandikan data JPEG, saya juga menulis beberapa kode dasar untuk memproses data header JPEG yang lebih baik (seperti yang disarankan), saya juga GuassianBlur digunakan pada output yang membantu melunakkan beberapa kompresi JPEG. Karena versi baru lebih baik, saya telah memperbarui posting saya untuk mencerminkan metode baru.
metode
Saya telah mencoba sesuatu yang unik (semoga), daripada mencoba memanipulasi kedalaman warna, atau identifikasi tepi, atau mencoba menggunakan berbagai cara untuk mengurangi ukuran gambar sendiri. Saya telah menggunakan algoritma JPEG pada kompresi maksimum pada versi skala yang diperkecil dari gambar, kemudian dengan menghilangkan semuanya kecuali "StartOfScan" ( http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure ) dan beberapa elemen header utama saya bisa mendapatkan ukuran ke jumlah yang dapat diterima. Hasilnya sebenarnya cukup mengesankan untuk 140 karakter, memberi saya rasa hormat yang baru ditemukan untuk JPEG:
Hindenburg
Pegunungan
Mona lisa
Bentuk
Kode
Versi 2 - http://pastebin.com/Tgr8XZUQ
Saya benar-benar mulai ketinggalan ReSharper + Saya memiliki banyak hal untuk diperbaiki, masih banyak pengodean yang sulit terjadi di sini, menarik untuk diacaukan (ingat Anda perlu MagickImage dll untuk menjalankan ini di VS)
Asli (Usang) - http://pastebin.com/BDPT0BKT
Masih sedikit berantakan.
sumber
Python 3
metode
Apa yang pertama-tama dilakukan program adalah memperkecil ukuran gambar, sangat mengurangi ukurannya.
Kedua, ia mengubah nilai rgb menjadi biner, dan memotong beberapa digit terakhir.
Kemudian mengkonversi data base 2 menjadi basis 10, di mana ia menambahkan dimensi gambar.
Kemudian mengkonversi data dalam basis 10 ke basis 95, menggunakan semua ascii yang bisa saya temukan. Namun, saya tidak bisa menggunakan / x01 dan sejenisnya karena kemampuannya untuk meniadakan fungsi yang menulis file teks.
Dan (untuk menambahkan ambiguitas), fungsi decode melakukannya secara terbalik.
kompres.py
decode.py
Jeritan
Mona lisa
Bola
sumber