Il y a quelques années, j'ai écrit une implémentation très simple de la compression d'image fractale pour le travail des étudiants et publié le code sur github .

À ma grande surprise, le référentiel s'est avéré être très populaire, j'ai donc décidé de mettre à jour le code et d'écrire un article l'expliquant ainsi que la théorie.

Théorie

Cette partie est assez théorique, et si vous n'êtes intéressé que par la documentation du code, vous pouvez la sauter.

Mappages de compression

Soit $$$(E, d)$ Est l' espace métrique complet , et $$$f: E \ rightarrow E$ - cartographie à partir de $$$E$ sur $$$E$ .

Nous disons que $$$f$ est un mappage compressif s'il existe $$ de telle sorte que:

$$

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

Sur cette base, $$$f$ dénotera un mappage de compression avec un taux de compression $$$s$ .

Il existe deux théorèmes importants sur les contrats de cartographie: le théorème du point fixe de Banach et le théorème du collage .

Théorème du point fixe : $$$f$ a un point fixe unique $$$x_0$ .


De plus, nous désignerons comme $$$x_0$ point fixe $$$f$ .

Théorème du collage : si $$$d (x, f (x)) <\ epsilon$ alors $$$d (x, x_0) <\ frac {\ epsilon} {1 - s}$ .


Le deuxième théorème nous dit que si nous trouvons une carte de contraction $$$f$ tel que $$$f (x)$ près de $$$x$ , alors nous pouvons être sûrs que le point fixe $$$f$ aussi proche de $$$x$ .

Ce résultat sera le fondement de nos travaux futurs. Et en fait, au lieu de sauvegarder l'image, il nous suffit de sauvegarder l'affichage compressif, dont le point fixe est proche de l'image.

Écrans de compression pour les images

Dans cette partie, je vais montrer comment créer de tels affichages compressifs afin que le point fixe soit proche de l'image.

Tout d'abord, définissons l'ensemble d'images et la distance. Nous choisirons $$$E = [0, 1] ^ {h \ fois w}$ . $$$E$ Est-ce que beaucoup de matrices avec $$$h$ en rangées $$$w$ colonnes et avec des coefficients dans l'intervalle $$$[0, 1]$ . Ensuite, nous prendrons $$$d (x, y) = \ left (\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {(x_ {ij} -y_ {ij}) ^ 2}} \ droite) ^ {0,5}$ . $$$d$ Est la distance obtenue à partir de la norme Frobenius .

Soit $$$x \ in E$ Est-ce l'image que nous voulons compresser.

Nous allons diviser l'image en blocs deux fois:

• Tout d'abord, nous divisons l'image en blocs finis ou à intervalles $$$R_1, ..., R_L$ . Ces blocs sont séparés et couvrent toute l'image.
• Ensuite, nous divisons l'image en blocs de sources ou de domaines $$$D_1, ..., D_K$ . Ces blocs ne sont pas nécessairement séparés et ne couvrent pas nécessairement l'image entière.

Par exemple, nous pouvons segmenter l'image comme suit:


Puis pour chaque bloc d'intervalle $$$R_l$ nous sélectionnons un bloc de domaine $$$D_ {k_l}$ et cartographie $$$f_l: [0, 1] ^ {D_ {k_l}} \ rightarrow [0, 1] ^ {R_ {l}}$ .

Ensuite, nous pouvons définir une fonction $$$f$ comme:

$$

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

Approbation : si $$$f_l$ contractent des mappages, puis et $$$f$ également cartographie compressive.


Il reste une question à laquelle il faut répondre: comment choisir $$$D_ {k_l}$ et $$$f_l$ ?

Le théorème du collage offre un moyen de les choisir: si $$$x_ {R_l}$ est proche de $$$f (x_ {D_ {k_l}})$ pour tous $$$l$ alors $$$x$ est proche de $$$f (x)$ et par le théorème du collage $$$x$ et $$$x_0$ sont également proches.

Nous sommes donc indépendants pour tout le monde $$$l$ nous pouvons construire un ensemble de mappages de compression de chaque $$$D_ {k}$ sur $$$R_l$ et choisissez le meilleur. Dans la section suivante, nous montrons tous les détails de cette opération.

Implémentation

Dans chaque section, je vais copier des fragments de code intéressants, et le script complet peut être trouvé ici .

Cloisons

J'ai choisi une approche très simple. Les blocs source et les blocs feuilles segmentent l'image sur une grille, comme illustré dans l'image ci-dessus.

La taille des blocs est égale aux puissances de deux, ce qui simplifie considérablement le travail. Les blocs source sont 8 par 8 et les blocs de fin sont 4 par 4.

Il existe des schémas de partitionnement plus complexes. Par exemple, nous pouvons utiliser l'arbre à quatre arbres pour diviser plus fortement les zones avec beaucoup de détails.

Conversions

Dans cette section, je vais montrer comment créer des mappages de compression à partir de $$$D_ {k}$ sur $$$R_l$ .

N'oubliez pas que nous voulons générer une telle cartographie $$$f_l$ à $$$f (x_ {D_k})$ était proche de $$$x_ {R_l}$ . Autrement dit, plus nous générons de mappages, plus il est probable qu'il en trouve un bon.

Cependant, la qualité de la compression dépend du nombre de bits requis pour stocker $$$f_l$ . Autrement dit, si de nombreuses fonctions sont trop grandes, la compression sera mauvaise. Un compromis est nécessaire ici.

J'ai décidé que $$$f_l$ ressemblera à ceci:

$$

$$f_l (x_ {D_k}) = s \ fois tourner _ {\ theta} (flip_d (réduire (x_ {D_k})))) + b$$

où $$$réduire$ - il s'agit d'une fonction permettant de passer des blocs 8 à 8 aux blocs 4 à 4, $$$flip$ et $$$faire pivoter$ - transformations affines, $$$s$ change le contraste, et $$$b$ - luminosité.

La fonction de reduce réduit la taille de l'image en faisant la moyenne de l'environnement:

 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 

La fonction de rotation fait pivoter l'image d'un angle donné:

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

Pour conserver la forme de l'angle de l'image $$$\ theta$ ne peut prendre que des valeurs $$$\ {0 ^ {\ circ}, 90 ^ {\ circ}, 180 ^ {\ circ}, 270 ^ {\ circ} \}$ .

La fonction d' flip reflète l'image si la direction est -1 et ne reflète pas si la valeur est 1:

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

La conversion complète est effectuée par la fonction apply_transformation :

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

Nous avons besoin d'un bit pour se souvenir si la mise en miroir est nécessaire et de 2 bits pour l'angle de rotation. De plus, si nous économisons $$$s$ et $$$b$ En utilisant 8 bits pour chaque valeur, nous n'aurons besoin que de 11 bits pour enregistrer la conversion.

De plus, nous devons vérifier si ces fonctions sont des mappages de contraction. La preuve en est un peu ennuyeuse, et pas vraiment ce dont nous avons besoin. Peut-être que je l'ajouterai plus tard en annexe à l'article.

La compression

L'algorithme de compression est simple. Tout d'abord, nous générons toutes les transformations affines possibles de tous les blocs source en utilisant la fonction 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 

Ensuite, pour chaque bloc final, nous vérifions tous les blocs source transformés générés précédemment. Pour chacun, nous optimisons le contraste et la luminosité à l'aide de la méthode find_contrast_and_brightness2 , et si la conversion testée est la meilleure trouvée jusqu'à présent, alors enregistrez-la:

 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 

Pour trouver le meilleur contraste et luminosité, la méthode find_contrast_and_brightness2 résout simplement le problème des moindres carrés:

 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] 

Déballage

L'algorithme de décompression est encore plus simple. Nous commençons avec une image complètement aléatoire, puis appliquons une image compressée plusieurs fois $$$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 

Cet algorithme fonctionne parce que la carte de compression a un point fixe unique, et quelle que soit l'image source que nous choisissons, nous nous efforcerons de le faire.

Je pense que le moment est venu pour un petit exemple. Je vais essayer de compresser et de décompresser l'image du singe:


La fonction test_greyscale charge l'image, la compresse, la décompresse et affiche chaque itération de la décompression:


Pas mal du tout pour une implémentation aussi simple!

Images RVB

Une approche très naïve de la compression d'images RVB consiste à compresser les trois canaux individuellement:

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

Et pour le déballage, nous déballons simplement les données de trois canaux séparément et les collectons dans trois canaux d'image:

 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) 

Une autre solution très simple consiste à utiliser le même affichage de compression pour les trois canaux, car ils sont souvent très similaires.

Si vous souhaitez vérifier comment cela fonctionne, exécutez la fonction test_rgb :


Des artefacts sont apparus. Cette méthode est probablement trop naïve pour produire de bons résultats.

Où aller ensuite

Si vous voulez en savoir plus sur la compression d'images fractales, je peux vous recommander de lire l'article Techniques de compression d'images fractales et ondelettes de Stephen Welsted. Il est facile à lire et explique des techniques plus sophistiquées.