【Python】基于动态规划和K聚类的彩色图片压缩算法

python · 浏览次数 : 24

小编点评

本文介绍了一种彩色图像压缩方法，主要包括颜色聚类和动态规划量化两个核心原理。通过对图像中的颜色进行聚类和量化，实现了对图像数据的有效压缩。 1. **颜色聚类**：该方法首先使用KMeans聚类算法将图像中的颜色值聚类为较少数量的颜色簇。通过调整聚类数量和颜色数量，可以在降低存储需求的同时保持图像质量。 2. **动态规划量化**：通过动态规划量化算法进一步减少颜色的数量，同时尽量保持图像质量。该算法会根据原始图像的颜色分布，选择最接近的颜色进行保留。 3. **类结构介绍**：本文提出了一种名为'ColorfulImageCompressor'的类，该类包含了四个主要函数：`__init__`, `compress`, `decompress`, 和 `_dynamic_programming_quantization`。这些函数分别负责初始化压缩器对象、压缩图像、解压缩图像和执行动态规划量化。 4. **使用说明**：通过创建一个彩色图像压缩类的实例，设置聚类数、颜色数量和缩放因子等参数，即可对彩色图像进行压缩和解压缩操作。 5. **测试结果**：文章还提供了使用不同聚类数量和颜色数量的测试结果，展示了该方法在不同条件下的压缩性能。总体而言，本文提出的彩色图像压缩方法通过结合颜色聚类和动态规划量化技术，实现了对图像数据的有效压缩，同时在保持图像质量的同时显著降低了存储需求。

正文

引言

当想要压缩一张彩色图像时，彩色图像通常由数百万个颜色值组成，每个颜色值都由红、绿、蓝三个分量组成。因此，如果我们直接对图像的每个像素进行编码，会导致非常大的数据量。为了减少数据量，我们可以尝试减少颜色的数量，从而降低存储需求。

1.主要原理

（一）颜色聚类（Color Clustering）：

首先，使用 KMeans 聚类算法将图像中的颜色值聚类为较少数量的颜色簇。聚类的数量由 n_clusters 参数指定。每个像素被归类到与其最接近的聚类中心所代表的颜色簇。颜色聚类的过程大致如下：

图像转换： 首先，彩色图像被转换为一个包含所有像素颜色值的数据集。每个像素的颜色通常由红、绿、蓝三个分量组成，因此数据集中的每个样本都是一个三维向量，表示一个像素的颜色。
选择聚类数量： 在应用 KMeans 算法之前，需要确定聚类的数量。这个数量通常由用户指定，通过参数 n_clusters 控制。
应用 KMeans 算法： 将 KMeans 算法应用于颜色数据集，将颜色值聚类为指定数量的簇。每个簇的质心代表了该簇的平均颜色。
像素映射： 每个像素的颜色被映射到最接近的簇的质心所代表的颜色。这样，整个图像被转换为由较少数量的颜色值表示的压缩图像。

通过颜色聚类，彩色图像的颜色数量得以减少，从而实现了数据的压缩。压缩后的图像仍然能够保持视觉上的相似性，同时大大降低了存储空间的需求。

（二）动态规划量化（Dynamic Programming Quantization）：

接下来，通过动态规划量化算法对颜色进行压缩。这个算法会进一步减少颜色的数量，并尽可能保持图像的质量。参数 max_colors 指定了压缩后图像中的最大颜色数量。算法会尽量选择与原始图像相似的颜色进行保留，以最大程度地保持图像的质量。而在这部分动态规划量化过程大致如下：

初始化： 首先，初始化状态数组，表示不同颜色数量下的最优颜色组合。通常，初始状态可以是一个空数组或者包含少量颜色的数组。
状态转移： 根据动态规划的思想，从初始状态开始逐步扩展，计算每个状态下的最优颜色组合。这个过程通常涉及到对每种可能的颜色组合进行评估，并根据优化准则选择最优的组合。
选择最优解： 最终，选择最优的颜色组合作为压缩后的图像的颜色集合。这个颜色集合将用于替换原始图像中的颜色，从而实现图像的压缩。
压缩数据保存： 压缩后的图像数据以及相关信息（如原始图像的尺寸、选择的颜色集合等）被保存为 NumPy 数组，并通过 np.savez_compressed() 函数保存到指定路径。

通过动态规划量化，我们能够选择一组颜色，使得压缩后的图像在尽可能减少颜色数量的情况下，仍然能够保持与原始图像相似的视觉效果。这样就实现了对图像数据的进一步压缩。

（三）压缩数据保存：

压缩后的图像数据以及相关信息（如原始图像的尺寸、聚类数、最大颜色数、聚类中心颜色等）被保存为 NumPy 数组，并通过 np.savez_compressed() 函数保存到指定路径。

（四）解压缩过程：

解压缩过程与压缩过程相反。首先加载压缩后的图像数据，然后根据聚类中心颜色替换像素颜色，最后将重构后的图像数据重塑为原始形状，并恢复图像的原始尺寸。

2.彩色图像压缩类

（一）类结构介绍

将上面所述的一个彩色图像的压缩功能整合为一个名为’ColorfulImageCompressor’的类，在这个类中有四个函数，它们的函数名称、接受参数以及介绍如下：

ColorfulImageCompressor类

__init__(self, n_clusters, max_colors, resize_factor=0.5): 初始化彩色图像压缩器对象。
compress(self, image_path, compressed_file_path): 压缩彩色图像并保存到指定路径。
decompress(self, compressed_file_path): 解压缩彩色图像并返回解压缩后的图像对象。
_dynamic_programming_quantization(self, image_array): 动态规划量化，将彩色图像颜色量化为指定数量的颜色。

（二）初始化参数

在创建一个彩色图像压缩类的时候需要传入以下三个参数，进行参数的初始化。

n_clusters：聚类数，用于 KMeans 算法，指定图像中的颜色数量。
max_colors：最大颜色数，用于动态规划量化，指定压缩后图像中的最大颜色数量。
resize_factor：缩放因子，用于调整图像尺寸，默认为 0.5，表示将图像尺寸缩小到原始的一半。

（三）函数介绍

(1)compress(self, image_path, compressed_file_path)

介绍：
该函数的作用是压缩彩色图像并保存到指定路径。
参数：
image_path：原始图像文件路径。
compressed_file_path：压缩后的图像文件路径。
函数体：

    def compress(self, image_path, compressed_file_path):
        """
        压缩彩色图像并保存到指定路径。

        参数：
        - image_path：原始图像文件路径。
        - compressed_file_path：压缩后的图像文件路径。
        """
        # 打开图像并转换为 RGB 模式
        image = Image.open(image_path)
        image = image.convert('RGB')

        # 根据缩放因子调整图像大小
        new_size = (int(image.width * self.resize_factor), int(image.height * self.resize_factor))
        image = image.resize(new_size)

        # 将图像转换为 NumPy 数组并重塑为二维数组
        np_image = np.array(image)
        original_shape = np_image.shape
        np_image = np_image.reshape(-1, 3)

        # 使用动态规划量化对图像进行压缩
        compressed_data = self._dynamic_programming_quantization(np_image)

        # 保存压缩后的图像数据到指定路径
        np.savez_compressed(compressed_file_path, np_image=compressed_data['np_image'], original_shape=original_shape, n_clusters=self.n_clusters, max_colors=self.max_colors, center_colors=compressed_data['center_colors'])

(2)decompress(self, compressed_file_path)

介绍：
解压缩彩色图像并返回解压缩后的图像对象。
参数：
compressed_file_path：压缩后的图像文件路径。
返回：
reconstructed_image：解压缩后的图像对象。
函数体：

    def decompress(self, compressed_file_path):
        """
        解压缩彩色图像并返回解压缩后的图像对象。

        参数：
        - compressed_file_path：压缩后的图像文件路径。

        返回：
        - reconstructed_image：解压缩后的图像对象。
        """
        # 加载压缩后的图像数据
        compressed_data = np.load(compressed_file_path)
        np_image = compressed_data['np_image'].reshape(-1, 3)
        center_colors = compressed_data['center_colors']

        # 根据聚类中心替换像素颜色
        for i in range(self.n_clusters):
            np_image[np_image[:, 0] == i] = center_colors[i]

        # 将重构后的图像数据重塑为原始形状
        original_shape = compressed_data['original_shape']
        reconstructed_image = np_image.reshape(*original_shape).astype('uint8')
        reconstructed_image = Image.fromarray(reconstructed_image, 'RGB')

        # 恢复图像原始尺寸
        original_size = (int(reconstructed_image.width / self.resize_factor), int(reconstructed_image.height / self.resize_factor))
        reconstructed_image = reconstructed_image.resize(original_size)

        return reconstructed_image

(3)_dynamic_programming_quantization(self, image_array)

介绍：
动态规划量化，将彩色图像颜色量化为指定数量的颜色。
参数：
image_array：图像数据的 NumPy 数组表示。
返回：
compressed_data：包含压缩后图像数据及相关信息的字典。
函数体：

    def _dynamic_programming_quantization(self, image_array):
        """
        动态规划量化，将彩色图像颜色量化为指定数量的颜色。

        参数：
        - image_array：图像数据的 NumPy 数组表示。

        返回：
        - compressed_data：包含压缩后图像数据及相关信息的字典。
        """
        # 使用 KMeans 进行聚类
        kmeans = KMeans(n_clusters=self.n_clusters)
        labels = kmeans.fit_predict(image_array)
        quantized_image = np.zeros_like(image_array)

        # 遍历每个聚类簇
        for i in range(self.n_clusters):
            # 获取当前簇的像素颜色及其出现次数
            cluster_pixels = image_array[labels == i]
            unique_colors, color_counts = np.unique(cluster_pixels, axis=0, return_counts=True)
            
            # 选取出现次数最多的前 max_colors 个颜色作为量化后的颜色
            color_indices = np.argsort(color_counts)[::-1][:self.max_colors]
            quantized_colors = unique_colors[color_indices]

            # 计算聚类中像素与量化后颜色的距离
            distances = np.linalg.norm(cluster_pixels[:, None] - quantized_colors, axis=2)
            quantized_indices = np.argmin(distances, axis=1)

            # 使用量化后颜色替换聚类中的像素颜色
            quantized_image[labels == i] = quantized_colors[quantized_indices]

        # 存储聚类中心颜色
        center_colors = kmeans.cluster_centers_.astype('uint8')

        return {'np_image': quantized_image, 'n_clusters': self.n_clusters, 'max_colors': self.max_colors, 'center_colors': center_colors}

(四)使用说明

# 创建压缩器对象  
compressor = ColorfulImageCompressor(n_clusters=4, max_colors=2, resize_factor=0.5)  
  
# 压缩彩色图像  
image_path = "./img/image2.jpg"  
compressed_file_path = "./npz/compressed_image2_n4_c2.npz"  
compressor.compress(image_path, compressed_file_path)  
  
# 解压缩图像并显示  
reconstructed_image = compressor.decompress(compressed_file_path)  
reconstructed_image.show()  
reconstructed_image.save("./img/reconstructed_image2_n4_c2.jpg")

3.测试结果

测试图片我们使用的采用的一张818*818分辨率，大小为79.49KB的彩色图片。分别使用不同的聚类数量和颜色数量来进行测试。


原始图片	聚类数为8，颜色为2的压缩图片

详细运行数据如下表（下面文件名中的n为聚类数，而c为颜色数）：

文件名	原始大小（KB）	压缩后的中间文件大小（KB）	解压缩后的图片大小 (KB)
reconstructed_image2_n4_c2	79.49	29.5	41.7
reconstructed_image2_n4_c4	79.49	49.3	45.2
reconstructed_image2_n4_c8	79.49	70.9	51.3
reconstructed_image2_n4_c16	79.49	94.3	59.3
reconstructed_image2_n8_c2	79.49	48.3	48.7
reconstructed_image2_n8_c4	79.49	73.3	52.5
reconstructed_image2_n8_c8	79.49	101	59.1
reconstructed_image2_n8_c16	79.49	125	61.1

结束语

如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？你们的认可是我最大的分享动力！