给定一个 100x100 的画布，制作一张占 K 数最大的图片

[hzlzh]

突然想到一个小题，反向去推算固定尺寸图片的存储K数上限，大家什么思路？
例如：jpg png（除去额外的图片配色预设或软件信息）

[kurtrossel]

嘿嘿，有意思
等高人

[xxr3376]

可以认为jpg压缩接近压缩上线，做一张熵最大的图片就好了。。。也就是说rgb值全部随机即可。

[hzlzh]

@xxr3376 思路不错，但考虑到随机算法的不可控，可能无法达到理论极限，逆一个最大占用算法去填充点阵如何？

[xxr3376]

@hzlzh 实际上，评测一个随机算法好不好的评判标准之一就是用来做一张图片然后jpg压缩比大小。。。

[zoudm]

首先最大的文件大小应该是24位色100*100的bmp（bmp最常见的是不压缩的）。

然后因为jpg png都会进行有损压缩，所以多小都是可能的。

最难压缩的情况应该是矩阵的秩为100时，这样任何的压缩应该都是有损的。其他情况（秩不满时）可以用其他的列的线性组合来表示某些列。具体的压缩算法我不是很清楚。

[xxr3376]

@hzlzh 所有有规律的图片都比纯随机图片小，一套非随机算法生成的图片一般都是有规律的，也就是说应该很难直接用一套算法达到理论极限。

当然排除你专门针对某种压缩算法做逆向工程。。。

[xxr3376]

@zoudm 一个单位矩阵也是秩为100，但是压缩算法绝对可以进一步压缩。。

[zoudm]

@xxr3376
你说的有道理。
我对压缩算法确实了解的很少。

这样看来的话随机生成确实是一个很好的办法。

[iscraft]

包含颜色数量越多 体积越大
100x100如果是10000个像素点 每个像素点分配一种颜色 填充10000种颜色 并且不规则排列

应该最大了

[hzlzh]

@xxr3376 那这样考虑：
* 100x100 的点阵是固定数量的，
* 去填充的方案有有限的固定数目种，
* 在这里面去找K数最大的一张不否可行？
如果考虑压缩损耗，可以限定某个压缩比，或者先考虑PNG的情形。

[imn1]

这个要先指定什么格式
bmp的话，只要颜色位数和尺寸固定，字节数都一样，不管什么内容

[learnshare]

这是要反压缩啊，去探索一下压缩算法就好了。

[hzlzh]

@imn1 可以先把变量定下来，仅考虑本身这个思路本身
@learnshare 可以分享下你的思路

[kokdemo]

@iscraft 我同意你的看法，但是怎么排布才能让它的不规则性最高呢？

[hzlzh]

@kokdemo @iscraft 其实比较期待实践下，做张PNG发上来，然后比大小。

[learnshare]

@hzlzh 楼上大概都是在猜测压缩的方法，比如 “相邻的两个相同像素可以压缩” 等等。

@iscraft 的方法或许是比较合理的了。

但要实现这种占空间最大的图像，必须要看压缩算法的思路，然后完全避开 “可以被压缩” 这个条件。举个栗子：

1. 如果 “相邻的两个相同像素可以压缩”，那就让相邻的像素都不同；
2. 如果 “相同颜色的像素可以压缩”，那就让所有像素的颜色都不同。

肯定不止这两个条件，对吧。

[learnshare]

@zoudm 考虑到有损压缩，就太不确定结果了。

所以还是先考虑 *反压缩*，然后再考虑 *反有损* 比较好。

[iscraft]

@kokdemo 按照颜色过渡有序排列至10000 然后由程序随机乱序填充 比人为的干预排布效果好

@learnshare jpg或者png图片源码本身是否会包含一些颜色配置信息?如果有且可读取 那么在压缩过程中的颜色丢弃损耗是有一定百分比的 能否根据这个值判断未压缩前的大小

[abelyao]

100 x 100 既是 10000 个像素点咯，假设RGB分别都是 256 个颜色，总共就有 16777216 色。
那么从第1个像素点，到第10000个像素点，分别从 #000000 取值，然后每个像素间隔 1600 个色，也就是说第2个像素是 #000640 （十六进制），这样分配到第10000个像素点，也就没有重复，并且每个像素点之间的颜色差距保持最大化，压缩的话也不算相近颜色。
剩下的就是图片保存算法的问题了，无损保存之类的。
纯属猜测~ 下班回家我也来做一张出来试试看 :)

[66450146]

有损压缩和无损压缩完全是两码事

在有损压缩里面，由于大多数有损压缩都是为了给人类看的，而人眼并不是对所有的颜色都是同样的敏感程度，所以人类捣鼓出了一个视觉注意计算模型，专门用来处理这个问题。一些有损的图像压缩算法里面，除了颜色之外甚至还包含了轮廓等信息，就是利用了人眼对不同图像信息的处理上有不同的权重。但是生理模型这个东西因人而异，没有一个绝对正确的标准。从这个角度来看，标题上说的是完全不可能的。

再说还有 pifs 这种蛋疼的东西……
https://github.com/philipl/pifs

[est]

不错的面试题

[hzlzh]

@66450146 设：结果是给机器验证的，排除人的视觉主观感受。

[jedyu]

文件尾可以塞无限数据

[hzlzh]

@jedyu 不要作弊哟

[learnshare]

@iscraft 我没有什么图像处理方面的编程经验，更别谈读过压缩算法了...

我认为使画质降低的处理（有损压缩），应该是为了达到我在 #16 谈到的两个条件。比如有两个相邻的像素，颜色比较接近，就可以优化成同一个颜色。（用 PS 做过径向过渡效果的同学，应该会发现导出的图如果质量不高的话，就会有波纹状效果）

当然，@66450146 谈到的这种针对视觉效果的处理，就更复杂了。

[icyalala]

这个主要是涉及信息论的"熵"的概念吧。。
知乎有个类似的问题，可以看一下： http://www.zhihu.com/question/22539777

针对LZ的问题，固定大小的图片，理论上如果其中的数据最无序(熵最大)，那它的压缩比也应该是上最小的。

在具体到文件格式上：
-----------------------------
PNG格式是无损压缩，压缩算法是deflate，实际上就是用Haffman编码来压缩，符合信息熵的理论，那最简单的方法就是每个像素都用随机数填充，随机数函数质量越好，熵越大。

简单做个实验：
BMP文件用这个生成:https://github.com/esneider/bmp
随机数是从设备的噪声数据熵池中取的:http://zh.wikipedia.org/wiki//dev/random
生成一张100x100 24bit的bmp文件，大小是30KB。

这张是手动填写的数据，虽然没有相同颜色的像素，但是数据比较有序。压缩成PNG后只有6KB。


这张是用随机数填充的，压缩成PNG后有32KB(几乎没有压缩效果)。


如果非要精确的生成一张理论压缩比最小的PNG，可以尝试看下PNG的压缩过程，针对实际算法来一步步填充。

-----------------------------
JPG格式是有损压缩，所以要先看一下这个压缩算法。JPG是用人类的视觉模型来进行压缩的，颜色模型是YCbCr，所以BMP转JPG时，第一步要把RGB颜色转换为YCbCr，然后再用离散余弦变换转换到频域，之后可以压缩掉一些频域上人眼不敏感的数据，最后才用Haffman编码来处理数据。

这个过程来说，根据视觉模型压缩这一步不好分析。。生成一个"最小压缩比"的图片，理论上很困难。。感觉。。

[luo362722353]

raw格式图片才是不压缩的...
你可以试试