Beberapa tahun yang lalu saya menulis implementasi kompresi fraktal gambar yang sangat sederhana untuk pekerjaan siswa dan memposting kode di github .

Yang mengejutkan saya, repositori ternyata cukup populer, jadi saya memutuskan untuk memperbarui kode dan menulis artikel yang menjelaskannya dan teorinya.

Teori

Bagian ini cukup teoretis, dan jika Anda hanya tertarik pada dokumentasi kode, Anda dapat melewatinya.

Pemetaan Kompresi

Biarkan $$$(E, d)$ Apakah ruang metrik penuh , dan $$$f: E \ rightarrow E$ - pemetaan dari $$$E$ pada $$$E$ .

Kami mengatakan itu $$$f$ adalah pemetaan kompresif jika ada $$$0 <s <1$ sedemikian rupa sehingga:

$$

$$\ forall x, y \ dalam E, d (f (x), f (y)) \ leq sd (x, y)$$

Berdasarkan ini, $$$f$ akan menunjukkan pemetaan kompresi dengan rasio kompresi $$$s$ .

Ada dua teorema penting tentang pembuatan peta kontrak: teorema titik tetap Banach dan teorema kolase .

Teorema titik tetap : $$$f$ memiliki titik tetap yang unik $$$x_0$ .


Selanjutnya kami akan menyatakan sebagai $$$x_0$ titik tetap $$$f$ .

Teorema kolase : jika $$$d (x, f (x)) <\ epsilon$ lalu $$$d (x, x_0) <\ frac {\ epsilon} {1 - s}$ .


Teorema kedua memberi tahu kita bahwa jika kita menemukan peta kontraksi $$$f$ sedemikian rupa $$$f (x)$ dekat dengan $$$x$ , maka bisa dipastikan titik itu tetap $$$f$ juga dekat dengan $$$x$ .

Hasil ini akan menjadi dasar untuk pekerjaan kami di masa depan. Dan pada kenyataannya, alih-alih menyimpan gambar, itu sudah cukup bagi kita untuk menyimpan tampilan kompresif, titik tetap yang dekat dengan gambar.

Tampilan kompresi untuk gambar

Pada bagian ini saya akan menunjukkan cara membuat tampilan kompresif sehingga titik tetap dekat dengan gambar.

Pertama, mari kita atur set gambar dan jarak. Kami akan memilih $$$E = [0, 1] ^ {h \ kali w}$ . $$$E$ Apakah banyak matriks dengan $$$h$ dalam baris $$$w$ kolom dan dengan koefisien dalam interval $$$[0, 1]$ . Maka kita akan ambil $$$d (x, y) = \ kiri (\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {(x_ {ij} -y_ {ij}) ^ 2}} \ kanan) ^ {0,5}$ . $$$d$ Apakah jarak yang didapat dari norma Frobenius .

Biarkan $$$x \ dalam E$ Apakah gambar yang ingin kita kompres.

Kami akan membagi gambar menjadi blok dua kali:

• Pertama, kami membagi gambar menjadi blok terbatas atau interval $$$R_1, ..., R_L$ . Blok-blok ini dipisahkan dan menutupi seluruh gambar.
• Lalu kami membagi gambar menjadi blok sumber atau domain $$$D_1, ..., D_K$ . Blok-blok ini tidak harus dipisahkan dan tidak harus mencakup seluruh gambar.

Misalnya, kita dapat mengelompokkan gambar sebagai berikut:


Kemudian untuk setiap blok interval $$$R_l$ kami memilih blok domain $$$D_ {k_l}$ dan pemetaan $$$f_l: [0, 1] ^ {D_ {k_l}} \ rightarrow [0, 1] ^ {R_ {l}}$ .

Selanjutnya kita dapat mendefinisikan suatu fungsi $$$f$ seperti:

$$

$$f (x) _ {ij} = f_l (x_ {D_ {k_l}}) _ {ij} \ text {if} (i, j) \ dalam R_l$$

Persetujuan : jika $$$f_l$ membuat kontrak pemetaan, lalu dan $$$f$ juga pemetaan kompresif.


Masih ada satu pertanyaan yang perlu dijawab: bagaimana memilih $$$D_ {k_l}$ dan $$$f_l$ ?

Teorema kolase menawarkan cara untuk memilihnya: jika $$$x_ {R_l}$ dekat dengan $$$f (x_ {D_ {k_l}})$ untuk semua $$$l$ lalu $$$x$ dekat dengan $$$f (x)$ dan oleh teorema kolase $$$x$ dan $$$x_0$ juga dekat.

Jadi kami independen untuk semua orang $$$l$ kita dapat membuat satu set pemetaan dari masing-masing $$$D_ {k}$ pada $$$R_l$ dan pilih yang terbaik. Di bagian selanjutnya, kami menunjukkan semua detail operasi ini.

Implementasi

Di setiap bagian saya akan menyalin fragmen kode yang menarik, dan seluruh skrip dapat ditemukan di sini .

Partisi

Saya memilih pendekatan yang sangat sederhana. Blok sumber dan blok daun mengelompokkan gambar pada kisi, seperti yang ditunjukkan pada gambar di atas.

Ukuran balok sama dengan kekuatan dua dan ini sangat menyederhanakan pekerjaan. Blok sumber adalah 8 oleh 8 dan blok akhir adalah 4 oleh 4.

Ada skema partisi yang lebih kompleks. Sebagai contoh, kita dapat menggunakan pohon quadtree untuk memecah area dengan banyak detail lebih kuat.

Konversi

Di bagian ini, saya akan menunjukkan cara membuat pemetaan kompresi $$$D_ {k}$ pada $$$R_l$ .

Ingatlah bahwa kami ingin membuat pemetaan seperti itu $$$f_l$ untuk $$$f (x_ {D_k})$ dekat $$$x_ {R_l}$ . Artinya, semakin banyak pemetaan yang kami hasilkan, semakin besar kemungkinan untuk menemukan yang baik.

Namun, kualitas kompresi tergantung pada jumlah bit yang diperlukan untuk menyimpan $$$f_l$ . Artinya, jika banyak fungsi terlalu besar, maka kompresi akan buruk. Dibutuhkan kompromi di sini.

Saya memutuskan itu $$$f_l$ akan terlihat seperti ini:

$$

$$f_l (x_ {D_k}) = s \ kali rotate _ {\ theta} (flip_d (kurangi (x_ {D_k}))) + b$$

dimana $$$kurangi$ - ini adalah fungsi untuk bergerak dari blok 8 ke 8 ke blok 4 ke 4, $$$flip$ dan $$$rotate$ - transformasi affine, $$$s$ mengubah kontras, dan $$$b$ - kecerahan.

Fungsi pengurangan mengurangi ukuran gambar dengan rata-rata lingkungan:

 def reduce(img, factor): result = np.zeros((img.shape[0] // factor, img.shape[1] // factor)) for i in range(result.shape[0]): for j in range(result.shape[1]): result[i,j] = np.mean(img[i*factor:(i+1)*factor,j*factor:(j+1)*factor]) return result 

Fungsi rotate memutar gambar dengan sudut tertentu:

 def rotate(img, angle): return ndimage.rotate(img, angle, reshape=False) 

Untuk mempertahankan bentuk sudut gambar $$$\ theta$ hanya bisa mengambil nilai $$$\ {0 ^ {\ circ}, 90 ^ {\ circ}, 180 ^ {\ circ}, 270 ^ {\ circ} \}$ .

Fungsi flip mencerminkan gambar jika direction -1 dan tidak mencerminkan jika nilainya 1:

 def flip(img, direction): return img[::direction,:] 

Konversi lengkap dilakukan oleh fungsi apply_transformation :

 def apply_transformation(img, direction, angle, contrast=1.0, brightness=0.0): return contrast*rotate(flip(img, direction), angle) + brightness 

Kita perlu 1 bit untuk mengingat jika mirroring diperlukan, dan 2 bit untuk sudut rotasi. Apalagi jika kita menabung $$$s$ dan $$$b$ Menggunakan 8 bit untuk setiap nilai, kita hanya perlu 11 bit untuk menyimpan konversi.

Selain itu, kita harus memeriksa apakah fungsi-fungsi ini adalah pemetaan kontraksi. Buktinya sedikit membosankan, dan tidak terlalu yang kita butuhkan. Mungkin nanti saya akan menambahkannya sebagai lampiran artikel.

Kompresi

Algoritma kompresi sederhana. Pertama, kami membuat semua transformasi affine yang mungkin dari semua blok sumber menggunakan fungsi generate_all_transformed_blocks :

 def generate_all_transformed_blocks(img, source_size, destination_size, step): factor = source_size // destination_size transformed_blocks = [] for k in range((img.shape[0] - source_size) // step + 1): for l in range((img.shape[1] - source_size) // step + 1): # Extract the source block and reduce it to the shape of a destination block S = reduce(img[k*step:k*step+source_size,l*step:l*step+source_size], factor) # Generate all possible transformed blocks for direction, angle in candidates: transformed_blocks.append((k, l, direction, angle, apply_transform(S, direction, angle))) return transformed_blocks 

Kemudian, untuk setiap blok terakhir, kami memeriksa semua blok sumber yang diubah sebelumnya dibuat. Untuk masing-masing, kami mengoptimalkan kontras dan kecerahan menggunakan metode find_contrast_and_brightness2 , dan jika konversi yang diuji adalah yang terbaik dari yang sejauh ini ditemukan, maka simpanlah:

 def compress(img, source_size, destination_size, step): transformations = [] transformed_blocks = generate_all_transformed_blocks(img, source_size, destination_size, step) for i in range(img.shape[0] // destination_size): transformations.append([]) for j in range(img.shape[1] // destination_size): print(i, j) transformations[i].append(None) min_d = float('inf') # Extract the destination block D = img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] # Test all possible transformations and take the best one for k, l, direction, angle, S in transformed_blocks: contrast, brightness = find_contrast_and_brightness2(D, S) S = contrast*S + brightness d = np.sum(np.square(D - S)) if d < min_d: min_d = d transformations[i][j] = (k, l, direction, angle, contrast, brightness) return transformations 

Untuk menemukan kontras dan kecerahan terbaik, metode find_contrast_and_brightness2 cukup memecahkan masalah kuadrat terkecil:

 def find_contrast_and_brightness2(D, S): # Fit the contrast and the brightness A = np.concatenate((np.ones((S.size, 1)), np.reshape(S, (S.size, 1))), axis=1) b = np.reshape(D, (D.size,)) x, _, _, _ = np.linalg.lstsq(A, b) return x[1], x[0] 

Membongkar

Algoritma dekompresi bahkan lebih sederhana. Kami mulai dengan gambar yang benar-benar acak, dan kemudian menerapkan gambar pemerasan beberapa kali $$$f$ :

 def decompress(transformations, source_size, destination_size, step, nb_iter=8): factor = source_size // destination_size height = len(transformations) * destination_size width = len(transformations[0]) * destination_size iterations = [np.random.randint(0, 256, (height, width))] cur_img = np.zeros((height, width)) for i_iter in range(nb_iter): print(i_iter) for i in range(len(transformations)): for j in range(len(transformations[i])): # Apply transform k, l, flip, angle, contrast, brightness = transformations[i][j] S = reduce(iterations[-1][k*step:k*step+source_size,l*step:l*step+source_size], factor) D = apply_transformation(S, flip, angle, contrast, brightness) cur_img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] = D iterations.append(cur_img) cur_img = np.zeros((height, width)) return iterations 

Algoritma ini berfungsi karena peta kompresi memiliki titik tetap yang unik, dan apa pun sumber gambar yang kita pilih, kami akan berusaha keras untuk itu.

Saya pikir waktunya telah tiba untuk contoh kecil. Saya akan mencoba mengompres dan membuka ritsleting gambar monyet:


Fungsi test_greyscale memuat gambar, mengompresnya, mendekompresinya, dan menunjukkan setiap iterasi dari dekompresi:


Tidak buruk sama sekali untuk implementasi yang begitu sederhana!

Gambar RGB

Pendekatan yang sangat naif untuk mengompresi gambar RGB adalah dengan mengompresi ketiga saluran secara terpisah:

 def compress_rgb(img, source_size, destination_size, step): img_r, img_g, img_b = extract_rgb(img) return [compress(img_r, source_size, destination_size, step), \ compress(img_g, source_size, destination_size, step), \ compress(img_b, source_size, destination_size, step)] 

Dan untuk membongkar, kami cukup membongkar data tiga saluran secara terpisah dan mengumpulkannya dalam tiga saluran gambar:

 def decompress_rgb(transformations, source_size, destination_size, step, nb_iter=8): img_r = decompress(transformations[0], source_size, destination_size, step, nb_iter)[-1] img_g = decompress(transformations[1], source_size, destination_size, step, nb_iter)[-1] img_b = decompress(transformations[2], source_size, destination_size, step, nb_iter)[-1] return assemble_rbg(img_r, img_g, img_b) 

Solusi lain yang sangat sederhana adalah dengan menggunakan tampilan kompresi yang sama untuk ketiga saluran, karena mereka seringkali sangat mirip.

Jika Anda ingin memeriksa cara kerjanya, maka jalankan fungsi test_rgb :


Artefak muncul. Metode ini mungkin terlalu naif untuk menghasilkan hasil yang baik.

Ke mana harus pergi selanjutnya

Jika Anda ingin tahu lebih banyak tentang kompresi gambar fraktal, saya dapat merekomendasikan Anda membaca artikel Teknik Kompresi Gambar Fraktal dan Wavelet oleh Stephen Welsted. Mudah dibaca dan menjelaskan teknik yang lebih canggih.