V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hzlzh
V2EX  ›  程序员

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

  •  1
     
  •   hzlzh ·
    hzlzh · 2014-07-24 16:13:11 +08:00 · 4605 次点击
    这是一个创建于 3760 天前的主题,其中的信息可能已经有所发展或是发生改变。
    突然想到一个小题,反向去推算固定尺寸图片的存储K数上限,大家什么思路?
    例如:jpg png(除去额外的图片配色预设或软件信息)
    27 条回复    2014-07-25 01:06:12 +08:00
    kurtrossel
        1
    kurtrossel  
       2014-07-24 16:16:29 +08:00   ❤️ 1
    嘿嘿,有意思
    等高人
    xxr3376
        2
    xxr3376  
       2014-07-24 16:19:43 +08:00   ❤️ 3
    可以认为jpg压缩接近压缩上线,做一张熵最大的图片就好了。。。也就是说rgb值全部随机即可。
    hzlzh
        3
    hzlzh  
    OP
       2014-07-24 16:22:31 +08:00
    @xxr3376 思路不错,但考虑到随机算法的不可控,可能无法达到理论极限,逆一个最大占用算法去填充点阵如何?
    xxr3376
        4
    xxr3376  
       2014-07-24 16:23:29 +08:00   ❤️ 2
    @hzlzh 实际上,评测一个随机算法好不好的评判标准之一就是用来做一张图片然后jpg压缩比大小。。。
    zoudm
        5
    zoudm  
       2014-07-24 16:24:40 +08:00   ❤️ 2
    首先最大的文件大小应该是24位色100*100的bmp(bmp最常见的是不压缩的)。

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

    最难压缩的情况应该是矩阵的秩为100时,这样任何的压缩应该都是有损的。其他情况(秩不满时)可以用其他的列的线性组合来表示某些列。具体的压缩算法我不是很清楚。
    xxr3376
        6
    xxr3376  
       2014-07-24 16:25:41 +08:00   ❤️ 1
    @hzlzh 所有有规律的图片都比纯随机图片小,一套非随机算法生成的图片一般都是有规律的,也就是说应该很难直接用一套算法达到理论极限。

    当然排除你专门针对某种压缩算法做逆向工程。。。
    xxr3376
        7
    xxr3376  
       2014-07-24 16:27:27 +08:00   ❤️ 1
    @zoudm 一个单位矩阵也是秩为100,但是压缩算法绝对可以进一步压缩。。
    zoudm
        8
    zoudm  
       2014-07-24 16:30:41 +08:00   ❤️ 1
    @xxr3376
    你说的有道理。
    我对压缩算法确实了解的很少。

    这样看来的话随机生成确实是一个很好的办法。
    iscraft
        9
    iscraft  
       2014-07-24 16:37:12 +08:00   ❤️ 2
    包含颜色数量越多 体积越大
    100x100如果是10000个像素点 每个像素点分配一种颜色 填充10000种颜色 并且不规则排列

    应该最大了
    hzlzh
        10
    hzlzh  
    OP
       2014-07-24 16:37:46 +08:00
    @xxr3376 那这样考虑:
    * 100x100 的点阵是固定数量的,
    * 去填充的方案有有限的固定数目种,
    * 在这里面去找K数最大的一张不否可行?
    如果考虑压缩损耗,可以限定某个压缩比,或者先考虑PNG的情形。
    imn1
        11
    imn1  
       2014-07-24 16:38:01 +08:00   ❤️ 1
    这个要先指定什么格式
    bmp的话,只要颜色位数和尺寸固定,字节数都一样,不管什么内容
    learnshare
        12
    learnshare  
       2014-07-24 16:38:20 +08:00   ❤️ 1
    这是要反压缩啊,去探索一下压缩算法就好了。
    hzlzh
        13
    hzlzh  
    OP
       2014-07-24 16:40:41 +08:00
    @imn1 可以先把变量定下来,仅考虑本身这个思路本身
    @learnshare 可以分享下你的思路
    kokdemo
        14
    kokdemo  
       2014-07-24 17:00:55 +08:00   ❤️ 1
    @iscraft 我同意你的看法,但是怎么排布才能让它的不规则性最高呢?
    hzlzh
        15
    hzlzh  
    OP
       2014-07-24 17:05:28 +08:00
    @kokdemo @iscraft 其实比较期待实践下,做张PNG发上来,然后比大小。
    learnshare
        16
    learnshare  
       2014-07-24 17:12:01 +08:00   ❤️ 1
    @hzlzh 楼上大概都是在猜测压缩的方法,比如 “相邻的两个相同像素可以压缩” 等等。

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

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

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

    肯定不止这两个条件,对吧。
    learnshare
        17
    learnshare  
       2014-07-24 17:14:55 +08:00   ❤️ 1
    @zoudm 考虑到有损压缩,就太不确定结果了。

    所以还是先考虑 *反压缩*,然后再考虑 *反有损* 比较好。
    iscraft
        18
    iscraft  
       2014-07-24 17:25:23 +08:00   ❤️ 1
    @kokdemo 按照颜色过渡有序排列至10000 然后由程序随机乱序填充 比人为的干预排布效果好

    @learnshare jpg或者png图片源码本身是否会包含一些颜色配置信息?如果有且可读取 那么在压缩过程中的颜色丢弃损耗是有一定百分比的 能否根据这个值判断未压缩前的大小
    abelyao
        19
    abelyao  
       2014-07-24 17:34:22 +08:00   ❤️ 1
    100 x 100 既是 10000 个像素点咯,假设RGB分别都是 256 个颜色,总共就有 16777216 色。
    那么从第1个像素点,到第10000个像素点,分别从 #000000 取值,然后每个像素间隔 1600 个色,也就是说第2个像素是 #000640 (十六进制),这样分配到第10000个像素点,也就没有重复,并且每个像素点之间的颜色差距保持最大化,压缩的话也不算相近颜色。
    剩下的就是图片保存算法的问题了,无损保存之类的。
    纯属猜测~ 下班回家我也来做一张出来试试看 :)
    66450146
        20
    66450146  
       2014-07-24 17:39:37 +08:00   ❤️ 1
    有损压缩和无损压缩完全是两码事

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

    再说还有 pifs 这种蛋疼的东西……
    https://github.com/philipl/pifs
    est
        21
    est  
       2014-07-24 18:16:32 +08:00 via Android   ❤️ 1
    不错的面试题
    hzlzh
        22
    hzlzh  
    OP
       2014-07-24 19:11:29 +08:00
    @66450146 设:结果是给机器验证的,排除人的视觉主观感受。
    jedyu
        23
    jedyu  
       2014-07-24 19:14:48 +08:00   ❤️ 1
    文件尾可以塞无限数据
    hzlzh
        24
    hzlzh  
    OP
       2014-07-24 19:24:55 +08:00
    @jedyu 不要作弊哟
    learnshare
        25
    learnshare  
       2014-07-24 19:26:54 +08:00   ❤️ 1
    @iscraft 我没有什么图像处理方面的编程经验,更别谈读过压缩算法了...

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

    当然,@66450146 谈到的这种针对视觉效果的处理,就更复杂了。
    icyalala
        26
    icyalala  
       2014-07-25 00:16:24 +08:00   ❤️ 1
    这个主要是涉及信息论的"熵"的概念吧。。
    知乎有个类似的问题,可以看一下: 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
        27
    luo362722353  
       2014-07-25 01:06:12 +08:00
    raw格式图片才是不压缩的...
    你可以试试
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2856 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 02:26 · PVG 10:26 · LAX 18:26 · JFK 21:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.