Vor ein paar Jahren habe ich eine sehr einfache Implementierung der fraktalen Bildkomprimierung für Studenten geschrieben und den Code auf Github gepostet.

Zu meiner Überraschung stellte sich heraus, dass das Repository sehr beliebt war, und ich entschied mich, den Code zu aktualisieren und einen Artikel zu schreiben, der ihn und die Theorie erklärt.

Theorie

Dieser Teil ist ziemlich theoretisch, und wenn Sie nur an der Codedokumentation interessiert sind, können Sie ihn überspringen.

Komprimierungszuordnungen

Lassen $$$(E, d)$ Ist der gesamte metrische Raum und $$$f: E \ rightarrow E$ - Zuordnung von $$$E$ auf $$$E$ .

Wir sagen das $$$f$ ist eine komprimierte Zuordnung, falls vorhanden $$$0 <s <1$ so dass:

$$

$$\ für alle x, y \ in E, d (f (x), f (y)) \ leq sd (x, y)$$

Darauf aufbauend $$$f$ bezeichnet eine Komprimierungszuordnung mit einem Komprimierungsverhältnis $$$s$ .

Es gibt zwei wichtige Sätze zu Kontraktionsabbildungen: den Banach-Fixpunktsatz und den Collagensatz .

Fixpunktsatz : $$$f$ hat einen eindeutigen Fixpunkt $$$x_0$ .


Weiter werden wir als bezeichnen $$$x_0$ fester Punkt $$$f$ .

Collagensatz : wenn $$$d (x, f (x)) <\ epsilon$ dann $$$d (x, x_0) <\ frac {\ epsilon} {1 - s}$ .


Der zweite Satz sagt uns, dass wir eine Kontraktionskarte finden $$$f$ so dass $$$f (x)$ in der Nähe von $$$x$ Dann können wir sicher sein, dass der Fixpunkt $$$f$ auch in der Nähe von $$$x$ .

Dieses Ergebnis wird die Grundlage für unsere zukünftige Arbeit sein. Anstatt das Bild zu speichern, reicht es für uns, die komprimierte Anzeige zu speichern, deren fester Punkt nahe am Bild liegt.

Komprimierungsanzeigen für Bilder

In diesem Teil werde ich zeigen, wie man solche Druckanzeigen erstellt, damit der Fixpunkt nahe am Bild liegt.

Stellen wir zuerst den Bildsatz und die Entfernung ein. Wir werden wählen $$$E = [0, 1] ^ {h \ times w}$ . $$$E$ Ist eine Menge Matrizen mit $$$h$ in Reihen $$$w$ Spalten und mit Koeffizienten im Intervall $$$[0, 1]$ . Dann nehmen wir $$$d (x, y) = \ left (\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {(x_ {ij} -y_ {ij}) ^ 2}} \ right) ^ {0.5}$ . $$$d$ Ist der Abstand von der Frobenius-Norm erhalten .

Lassen $$$x \ in E$ Ist das Bild, das wir komprimieren möchten.

Wir werden das Bild zweimal in Blöcke aufteilen:

• Zunächst unterteilen wir das Bild in endliche oder Intervallblöcke $$$R_1, ..., R_L$ . Diese Blöcke sind getrennt und bedecken das gesamte Bild.
• Dann teilen wir das Bild in Blöcke von Quellen oder Domänen $$$D_1, ..., D_K$ . Diese Blöcke sind nicht notwendigerweise getrennt und bedecken nicht notwendigerweise das gesamte Bild.

Zum Beispiel können wir das Bild wie folgt segmentieren:


Dann für jeden Intervallblock $$$R_l$ Wir wählen einen Domain-Block $$$D_ {k_l}$ und Zuordnung $$$f_l: [0, 1] ^ {D_ {k_l}} \ rightarrow [0, 1] ^ {R_ {l}}$ .

Als nächstes können wir eine Funktion definieren $$$f$ wie:

$$

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

Genehmigung : wenn $$$f_l$ sind Vertragszuordnungen, dann und $$$f$ auch komprimiertes Mapping.


Es bleibt noch eine Frage zu beantworten: Wie soll man wählen? $$$D_ {k_l}$ und $$$f_l$ ?

Der Collagensatz bietet eine Möglichkeit, sie auszuwählen: if $$$x_ {R_l}$ ist in der Nähe von $$$f (x_ {D_ {k_l}})$ für alle $$$l$ dann $$$x$ ist in der Nähe von $$$f (x)$ und nach dem Collagensatz $$$x$ und $$$x_0$ sind auch nah.

Wir sind also für alle unabhängig $$$l$ wir können aus jedem einen Satz von Quetschzuordnungen konstruieren $$$D_ {k}$ auf $$$R_l$ und wähle das Beste. Im nächsten Abschnitt zeigen wir alle Details dieser Operation.

Implementierung

In jedem Abschnitt werden interessante Codefragmente kopiert. Das gesamte Skript finden Sie hier .

Partitionen

Ich habe einen sehr einfachen Ansatz gewählt. Quellblöcke und Blattblöcke segmentieren das Bild in einem Raster, wie im obigen Bild gezeigt.

Die Größe der Blöcke entspricht der Potenz von zwei, was die Arbeit erheblich vereinfacht. Quellblöcke sind 8 mal 8 und Endblöcke sind 4 mal 4.

Es gibt komplexere Partitionsschemata. Zum Beispiel können wir den Quadtree-Baum verwenden, um Bereiche mit vielen Details stärker aufzuteilen.

Conversions

In diesem Abschnitt werde ich zeigen, wie Sie aus Komprimierungszuordnungen erstellen $$$D_ {k}$ auf $$$R_l$ .

Denken Sie daran, dass wir ein solches Mapping generieren möchten $$$f_l$ zu $$$f (x_ {D_k})$ war in der Nähe von $$$x_ {R_l}$ . Das heißt, je mehr Zuordnungen wir generieren, desto wahrscheinlicher ist es, eine gute zu finden.

Die Qualität der Komprimierung hängt jedoch von der Anzahl der zum Speichern erforderlichen Bits ab $$$f_l$ . Das heißt, wenn viele Funktionen zu groß sind, ist die Komprimierung schlecht. Hier ist ein Kompromiss erforderlich.

Ich habe das entschieden $$$f_l$ wird so aussehen:

$$

$$f_l (x_ {D_k}) = s \ mal drehen _ {\ theta} (flip_d (verkleinern (x_ {D_k}))) + b$$

wo $$$reduzieren$ - Dies ist eine Funktion zum Verschieben von den Blöcken 8 bis 8 zu den Blöcken 4 bis 4. $$$flip$ und $$$drehen$ - affine Transformationen, $$$s$ ändert den Kontrast und $$$b$ - Helligkeit.

Die reduce reduziert die Größe des Bildes, indem die Umgebung gemittelt wird:

 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 

Die rotate dreht das Bild um einen bestimmten Winkel:

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

Beibehaltung der Form des Bildwinkels $$$\ theta$ kann nur Werte annehmen $$$\ {0 ^ {\ circ}, 90 ^ {\ circ}, 180 ^ {\ circ}, 270 ^ {\ circ} \}$ .

Die flip Funktion spiegelt das Bild, wenn die direction -1 ist, und spiegelt nicht, wenn der Wert 1 ist:

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

Die vollständige Konvertierung wird von der Funktion apply_transformation :

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

Wir benötigen 1 Bit, um uns zu erinnern, ob eine Spiegelung erforderlich ist, und 2 Bit für den Drehwinkel. Außerdem, wenn wir sparen $$$s$ und $$$b$ Bei Verwendung von 8 Bits für jeden Wert werden nur 11 Bits benötigt, um die Konvertierung zu speichern.

Außerdem sollten wir prüfen, ob es sich bei diesen Funktionen um Kontraktionszuordnungen handelt. Der Beweis dafür ist etwas langweilig und nicht wirklich das, was wir brauchen. Vielleicht füge ich es später als Anhang zum Artikel hinzu.

Kompression

Der Komprimierungsalgorithmus ist einfach. Zunächst generieren wir alle möglichen affinen Transformationen aller Quellblöcke mit der Funktion 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 

Dann prüfen wir für jeden letzten Block alle zuvor erzeugten transformierten Quellblöcke. Für jedes find_contrast_and_brightness2 optimieren wir Kontrast und Helligkeit mit der Methode find_contrast_and_brightness2 Wenn die getestete Konvertierung die bisher beste ist, speichern Sie sie:

 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 

Um den besten Kontrast und die beste Helligkeit zu finden, löst die Methode find_contrast_and_brightness2 einfach das Problem der kleinsten Quadrate:

 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] 

Auspacken

Der Dekomprimierungsalgorithmus ist noch einfacher. Wir beginnen mit einem völlig zufälligen Bild und wenden dann mehrmals ein Quetschbild an $$$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 

Dieser Algorithmus funktioniert, weil die Komprimierungszuordnung einen eindeutigen festen Punkt hat und wir unabhängig davon, welches Quellbild wir auswählen, danach streben werden.

Ich denke, es ist Zeit für ein kleines Beispiel. Ich werde versuchen, das Affenbild zu komprimieren und zu entpacken:


Die Funktion test_greyscale lädt das Bild, komprimiert es, dekomprimiert es und zeigt jede Iteration der Dekomprimierung an:


Gar nicht so schlecht für eine so einfache Implementierung!

RGB-Bilder

Ein sehr naiver Ansatz zum Komprimieren von RGB-Bildern besteht darin, alle drei Kanäle einzeln zu komprimieren:

 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)] 

Und zum Auspacken packen wir einfach die Daten von drei Kanälen getrennt aus und sammeln sie in drei Bildkanälen:

 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) 

Eine andere sehr einfache Lösung besteht darin, für alle drei Kanäle dieselbe Komprimierungsanzeige zu verwenden, da sie sich häufig sehr ähnlich sind.

Wenn Sie überprüfen möchten, wie dies funktioniert, führen Sie die Funktion test_rgb aus:


Artefakte erschienen. Diese Methode ist wahrscheinlich zu naiv, um gute Ergebnisse zu erzielen.

Wohin als nächstes?

Wenn Sie mehr über die fraktale Bildkomprimierung erfahren möchten, kann ich Ihnen den Artikel Fractal and Wavelet Image Compression Techniques von Stephen Welsted empfehlen. Es ist leicht zu lesen und erklärt anspruchsvollere Techniken.