图像压缩

Question

我一直在计算图像的未压缩和压缩文件大小。这对我来说总是导致压缩图像比我预期的未压缩图像小。如果图像包含大量不同的颜色，则存储调色板会占用大量空间，还需要更多位来存储每个代码。然而，我的问题是，压缩方法是否可能导致比未压缩的RGB图像更大的文件。对于这种压缩方法仍然有用的、总共包含k种不同颜色的最小正方形RGB图像，其大小（像素）是多少？因此，我们想要找到，对于给定的k值，找到最小整数n，对于该整数，大小为n×n的图像在压缩后比原始RGB图像占用更少的存储空间。

Answer 1

一般来说没有，但你的问题不准确。

如果我们压缩普通文件，它们可能会更大。例如，如果您压缩随机生成的字节序列，则没有太多要压缩的，因此您会得到压缩程序的标头，它告诉您使用了哪种压缩方法，以及一些版本控制。这将放大文件，甚至。一些转义。好的压缩程序会看到压缩不会缩小大小，因此他们不应该压缩，并在标头中告诉它是一个平面文件。这可能是按程序区域完成的。

但是你的问题是关于图像的。压缩是在文件内部完成的，通常不是所有文件，而是图像位。在这种情况下，程序会看到不需要压缩，所以他们会保持文件未压缩。但是因为图像标题总是存在，所以这只改变了一个标志，所以没有增加大小。

但这也可能取决于文件格式。你写过关于“调色板”的文章，但现在很少使用：压缩是在文件中找到类似的模式。不过，这取决于图像格式。如果你在维基百科中查找特定的文件格式，你可能会看到一个带有标题参数的表格（例如位深度或颜色数（调色板）、颜色定义和压缩方法）。

然后，对于类似调色板的图像，Dan Mašek的答案是(https://stackoverflow.com/a/58683948/2758823)有一些很好的数学解释，但人们不应该忘记，压缩是非常有启发性的，并且是对真实示例的测试：真实图像有模式。

Answer 2

让我们先做一个小的简化——编码输出的大小取决于像素的数量（宽度与高度的实际比例并不重要）。因此，让我们将问题推广到像素数N，从中我们可以通过平方根计算N。

为了进一步简化问题，我们还将忽略任何图像头/元数据的开销，例如宽度、高度、调色板的大小等。在实践中，这通常是一些相对较小的常数。

考虑到我们有

• N表示图像中的像素数

我们的目标是解决以下不等式

就N。

RGB图像只是N个像素的数组，每个像素占用RGB编码给定的固定位数。因此，

调色板图像由两部分组成：调色板和像素。

调色板是k种颜色的数组，每种颜色占用RGB编码给出的固定位数。因此，

在这种情况下，每个像素持有调色板条目的索引，而不是实际的RGB颜色。表示k值所需的位数为

然而，除非我们可以对分数位进行编码（我认为这超出了这个问题的范围），否则我们需要对其进行取整。因此，编码调色板索引所需的位数为

由于存在N个这样的调色板索引，因此像素数据的大小为

调色板图像的总大小为

而最后

在Python中，我们可以用以下方式表示：

import math

def limit_size(k):
    return (k * 24.) / (24. - math.ceil(math.log(k, 2)))

def size_rgb(N):
    return (N * 24.)

def size_pal(N, k):
    return (N * math.ceil(math.log(k, 2))) + (k * 24.)