几年前，我为学生作业编写了一个非常简单的分形图像压缩实现，并将代码发布在github上 。

令我惊讶的是，该存储库竟然很受欢迎，因此我决定更新代码并写一篇文章解释它和理论。

理论

这一部分是理论上的，如果您仅对代码文档感兴趣，则可以跳过。

压缩映射

让 $$$（E，d）$ 是完整的度量空间 ，并且 $$$f：E \ rightarrow E$ -从映射 $$$E$ 在 $$$E$ 。

我们说 $$$f$ 是压缩映射（如果存在） $$$0 <s <1$ 这样：

$$

$$\ forall x，y \ in E，d（f（x），f（y））\ leq sd（x，y）$$

基于此， $$$f$ 将表示具有压缩率的压缩映射 $$$s$ 。

压缩映射有两个重要的定理： Banach不动点 定理和拼贴定理 。

不动点定理 ： $$$f$ 有一个独特的固定点 $$$x_0$ 。


进一步我们将表示为 $$$x_0$ 定点 $$$f$ 。

拼贴定理 ：如果 $$$d（x，f（x））<\ epsilon$ 然后 $$$d（x，x_0）<\ frac {\ epsilon} {1-s}$ 。


第二个定理告诉我们，如果我们找到一个收缩图 $$$f$ 这样 $$$f（x）$ 接近 $$$x$ ，那么我们可以确定不动点 $$$f$ 也接近 $$$x$ 。

这一结果将成为我们未来工作的基础。 实际上，对于保存图像的固定点而言，仅保存图像就足够了，而不是保存图像。

图像压缩显示

在这一部分中，我将展示如何创建这样的压缩显示，以使固定点靠近图像。

首先，让我们设置图像集和距离。 我们会选择 $$$E = [0，1] ^ {h \次数w}$ 。 $$$E$ 是很多矩阵 $$$h$ 成排 $$$w$ 列和区间中的系数 $$$[0，1]$ 。 然后我们将 $$$d（x，y）= \左（\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {（x_ {ij} -y_ {ij}）^ 2}} \ right）^ {0.5}$ 。 $$$d$ 是从Frobenius范数获得的距离。

让 $$$x \在E$ 是我们要压缩的图像。

我们将图像分成两次块：

• 首先，我们将图像分为有限或间隔块 $$$R_1，...，R_L$ 。 这些块是分开的，并覆盖了整个图像。
• 然后，我们将图像分为来源或领域块 $$$D_1，...，D_K$ 。 这些块不必分开，也不必覆盖整个图像。

例如，我们可以按以下方式分割图像：


然后对于每个间隔块 $$$R_l$ 我们选择一个域块 $$$D_ {k_l}$ 和映射 $$$f_l：[0，1] ^ {D_ {k_l}} \ rightarrow [0，1] ^ {R_ {l}}$ 。

接下来我们可以定义一个函数 $$$f$ 像：

$$

$$f（x）_ {ij} = f_1（x_ {D_ {k_l}}）_ {ij} \文本{if}（i，j）\ in R_1$$

批准 ：如果 $$$f_l$ 是收缩映射，然后和 $$$f$ 还有压缩映射。


还有一个问题需要回答：如何选择 $$$D_ {k_l}$ 和 $$$f_l$ ？

拼贴定理提供了一种选择它们的方法： $$$x_ {R_l}$ 接近 $$$f（x_ {D_ {k_l}}）$ 对于所有 $$$l$ 然后 $$$x$ 接近 $$$f（x）$ 并根据拼贴定理 $$$x$ 和 $$$x_0$ 也很近。

所以我们对每个人都是独立的 $$$l$ 我们可以从每个构建一组挤压映射 $$$D_ {k}$ 在 $$$R_l$ 并选择最好的。 在下一节中，我们将显示此操作的所有详细信息。

实作

在每个部分中，我将复制有趣的代码片段，并且可以在此处找到整个脚本。

隔断

我选择了一种非常简单的方法。 如上图所示，源块和叶块将图像分割在网格上。

块的大小等于2的幂，因此大大简化了工作。 源块为8 x 8，端块为4 x 4。

有更复杂的分区方案。 例如，我们可以使用四叉树来更强地分解具有很多细节的区域。

转换次数

在本节中，我将展示如何从中创建压缩映射 $$$D_ {k}$ 在 $$$R_l$ 。

请记住，我们要生成这样的映射 $$$f_l$ 到 $$$f（x_ {D_k}）$ 接近 $$$x_ {R_l}$ 。 也就是说，我们生成的映射越多，找到一个好的映射的可能性就越大。

但是，压缩的质量取决于存储所需的位数 $$$f_l$ 。 也就是说，如果许多函数太大，那么压缩将很糟糕。 这里需要折衷。

我决定 $$$f_l$ 看起来像这样：

$$

$$f_l（x_ {D_k}）= s \旋转_ {\ theta}（flip_d（reduce（x_ {D_k}）））+ b$$

在哪里 $$$减少$ -此功能可从块8到8移动到块4到4， $$$翻转$ 和 $$$旋转$ -仿射变换， $$$s$ 改变对比度，并且 $$$b$ -亮度。

reduce功能通过平均周围环境来缩小图像的尺寸：

 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 

rotate功能将图像旋转给定角度：

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

保持像角形状 $$$\ theta$ 只能取值 $$$\ {0 ^ {\ circ}，90 ^ {\ circ}，180 ^ {\ circ}，270 ^ {\ circ} \}$ 。

如果direction为-1，则flip功能会镜像图像；如果值为1，则不会反映图像：

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

完全转换由apply_transformation函数执行：

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

如果需要镜像，我们需要1位来记住，旋转角度需要2位。 而且，如果我们保存 $$$s$ 和 $$$b$ 每个值使用8位，我们只需要11位就可以保存转换。

另外，我们应该检查这些功能是否为压缩映射。 这样的证明有点无聊，并不是我们真正需要的。 也许以后我将其添加为本文的附录。

压缩方式

压缩算法很简单。 首先，我们使用generate_all_transformed_blocks函数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 

然后，对于每个最终块，我们检查所有先前生成的转换后的源块。 对于每种方法，我们都使用find_contrast_and_brightness2方法优化对比度和亮度，如果经过测试的转换是迄今为止找到的最好的转换，则保存它：

 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 

为了找到最佳的对比度和亮度， find_contrast_and_brightness2方法只是解决最小二乘问题：

 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] 

开箱

解压缩算法甚至更简单。 我们从一个完全随机的图像开始，然后多次应用挤压图像 $$$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 

该算法之所以有效，是因为压缩图具有唯一的固定点，并且无论我们选择哪种源图像，我们都将努力。

我认为现在是一个小例子了。 我将尝试压缩和解压缩猴子图像：


test_greyscale函数加载图像，对其进行压缩，对其进行解压缩，并显示解压缩的每次迭代：


这样简单的实现一点都不差！

RGB图像

一种非常幼稚的压缩RGB图像的方法是分别压缩所有三个通道：

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

对于解压缩，我们只需分别解压缩三个通道的数据并将它们收集在三个图像通道中：

 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) 

另一个非常简单的解决方案是对所有三个通道使用相同的压缩显示，因为它们通常非常相似。

如果要检查其工作原理，请运行test_rgb函数：


神器出现了。 此方法可能太幼稚而无法产生良好的结果。

接下来要去哪里

如果您想了解有关分形图像压缩的更多信息，我建议您阅读Stephen Welsted的文章“ 分形和小波图像压缩技术” 。 易于阅读并介绍了更复杂的技术。