数学前沿（新增 数字如潮人如水）

数字图像的压缩与恢复/奥卡姆剃刀
http://songshuhui.net/archives/38054


2009年早春，斯坦福大学露西尔·帕卡德儿童医院的一组医生把一名两岁男孩送进磁共振成像[f1] 扫描仪。这个将被我称为布赖斯的男孩身处巨洞般的金属仪器中，看上去是那么弱小无助。他被施以全身麻醉，一根弯弯曲曲的管子从他的咽喉联接到扫描仪傍的呼吸机上。十个月前， 布赖斯接受了肝脏移植术，来自捐献者的部分肝脏取代了他自己的已坏死的肝脏。他的康复情况一度不错。但是，最近的实验室测试结果令人担忧，他的身体出现了问题——可能一条或者全部的两条胆管被堵住了。
帕卡德医院的儿童放射科医生施里亚斯（校对者注：这个first name有多种翻译方法，请编辑注意）·瓦萨纳瓦拉需要高精度的扫描结果来告诉他问题出在哪，但是这将意味着他的小病人在扫描过程中不得不保持绝对静止。哪怕布赖斯只是呼吸了一次，成像结果都会变得模糊。要避免上述情况，就需要进行足够深的麻醉让病人停止呼吸。进行一次标准的磁共振成像检测需要两分钟时间，但如果麻醉师真的让布赖斯在这么长时间里停止呼吸，那么带来的问题将远远超过他肝脏的小毛病。
不过，瓦萨纳瓦拉和他的电子工程师同事迈克尔·勒斯蒂格打算使用一种快得多的新扫描方法，名曰“压缩感知”。这种技术可能是当今应用数学界最热门的话题了。未来，它可能会改变我们寻找遥远星系的方式。而现在，这种技术使得瓦萨纳瓦拉和勒斯蒂格只需要40秒就可以采集到精确重建布赖斯肝脏图像所需的数据。
压缩感知的发现纯属偶然。2004年2月，伊曼纽尔·坎迪斯正在自己的电脑上看着Shepp-Logan图像（译注：这是医学图像处理领域用来进行仿真测试的标准模拟图像，由一些大大小小的椭圆模拟生物器官）打发时间。这幅通常被计算机科学家和工程师用于测试成像算法的标准图像，看起来就像《第三类接触》里那个搞笑地将眉毛扬起的外星人。坎迪斯，斯坦福大学教授，曾在加州理工学院工作过，打算用一个严重失真的模型图像作为磁共振成像仪不能精确扫描而产生的非清晰图像来进行实验。他想到一种名为L1（校对注：这里虽然原文用的是小写，但是在中文上下文中用小写则极易同11混淆，而数学上这里大小写都可以用）范数极小化的数学技术可能有助于清除小部分斑痕。他按下一个键，算法运行起来了。
坎迪斯希望屏幕上的模型图像变得稍微清晰一些。但是，他突然发现用残缺的数据渲染出来的图像是那么细腻完美，对每个细节而言都是如此，这简直就像变魔术一样。太不可思议了，他认为。“这就好像，你给了我十位银行账号的前三位，然后我能够猜出接下来的七位数字。”他说。他尝试在不同类型的模型图像上重新进行这个实验，结果都非常好。
在博士后贾斯廷·龙伯格的帮助下，坎迪斯提出了一个粗略的理论。之后，他在黑板上向加州大学洛杉矶分校的同事陶哲轩介绍了自己的理论。坎迪斯在结束讨论离开的时候觉得陶哲轩对此持怀疑态度，毕竟，图像清晰度的提高也太离谱了。然而，第二天晚上，陶哲轩给坎迪斯送去关于他们之前讨论的问题的一叠笔记。这叠笔记为他们共同发表的第一篇论文奠定了基础。在随后的两年中，他们写了更多文章。
上面介绍的是压缩感知技术的开端，这个数学界的全新领域改变了人们处理大规模数据集的方式。仅仅六年时光，它为上千篇论文提供了灵感，吸引了数百万美元的联邦基金。2006年，坎迪斯在这一领域内的工作为他赢得了奖金值50万美元的沃特曼奖，这是美国国家科学基金授予研究者的最高荣誉。其原因是显而易见的。想象一下，磁共振成像仪可以在几秒钟的时间里生成原本需要花费一个小时才能生成的图像；军用软件截获敌方通信的能力得到极大加强；传感器能够解析遥远星际的无线电波。突然之间，数据的采集、操作以及解析都变得容易了。
压缩感知的原理是这样的：你有一张图片，假设是总统的肾脏图片，这不是关键。图片由一百万个像素构成。对传统成像来说，你不得不进行一百万次量度。而采用压缩感知技术，你只需要量度一小部分，好比说从图像的不同部分随机抽取十万个像素。从这里开始，有大量的实际上是无穷多的方式填充那剩余的九十万个像素点。
寻找那个唯一正确的表示方式的关键在于一种叫稀疏度的概念。所谓稀疏度，是描述图像的复杂性或者其中所缺的一种数学方法。一幅由少数几个简单、可理解的元素（例如色块或者波浪线构成的图片）是稀疏的；满屏随机、散乱的点阵则不是稀疏的。原来在无限多的可能性中，最简单、最稀疏的那幅图像往往就是正解，至少很接近正解。
但是，怎样进行数字运算，才能快速获得最稀疏的图像呢？分析所有可能的情况太费时间。然而，坎迪斯和陶哲轩知道最稀疏的图像是用最少的成分构成的，并且，他们可以用L1范数极小化技术迅速找到它。
这样，在输入不完整的图像后，算法开始试着用大色块来填充空白区。如果有一团绿色的像素点聚集在一起，算法可能会用一个大的绿色矩形填充它们之间的空间;而如果是一团黄色的像素点，那么就用黄色的矩形来填充。在不同颜色交错散布的区域，算法会使用越来越小的矩形或其他形状填充各种颜色之间的空间。算法会重复这样的过程，最终，得到一幅由最少的可能的色块构成的图像，它的一百万像素都已被彩色填满。
并不能绝对保证这样的图像就是最稀疏的，或者正是你所试图重建的那个。但是坎迪斯和陶哲轩已经从数学上证明了，它的错误率是无穷小的。算法运行可能还是需要几个小时，但是，让电脑多跑一个小时，总好过让孩子在额外的一分钟里停止呼吸。
压缩感知已经产生了令人惊叹的科学影响。这是因为每一个有趣的信号都是稀疏的，只要你能够正确定义它的稀疏性。例如，钢琴和弦的乐音是一小组不超过五个纯音符的组合。在所演奏的音频中，只有少部分频率包含有效的音乐信息，而其余大部分频段是一片无声地带。因此，你可以用压缩感知技术从“欠采样”的老旧唱片中重建出当时的乐章，而不用担心失去了由特定频率构成的声波的信息。只需要你手头的材料，就可以用L1范数极小化法以稀疏方式填补空白，从而获得与原音一般无二的旋律。
带着建筑师式的眼睛，顶着略显蓬松的头发，坎迪斯散发着时尚极客的气息。这个39岁的法国人语气温和，但是面对他认为不达标的事情绝不妥协。“不，不，他说的没有道理。”当我提到压缩感知领域某个和他有些观点有着细小差别的专家的工作时，他如是说，“不，不，不，不。那没有道理，没道理，是错的。”
坎迪斯曾经预见，将来会有大量应用技术是以他的研究成果作为理论基础的。他举例说道，在未来，这项技术不会仅仅用在磁共振成像仪上。例如，数码相机收集了大量信息，然后压缩图像。但是，至少在压缩感知技术可用的情况下，压缩是一种极大的浪费。如果你的相机记录了大量的数据，却在压缩时丢弃了其中的90%，那么为什么不在一开始就只记录10%的数据从而节省电池电量和内存？对于您的孩子的数码快照，费电可能没什么大不了，你只要插上电源为相机充电就可以了。“但是，当废电池多到可以环绕木星，”坎迪斯说，“结果就不是那么简单了”。同样，如果你希望自己的相机能够拍摄万亿像素的照片而不是几百万像素，你就必须使用压缩感知技术。
从信息的小样本中收集有用数据的能力也引起了军方的重视：比如，敌方通信可能从一个频率跳到另一个频率。但是，还没有一种硬件设备能以足够快的速度扫描整个频域。但是无论在什么情况下，对手的信号都是稀疏的，是由频段内极少数的某种简单信号构成的，出现在一些相对较小却未知的频段。这意味着压缩感知可以用来从“噼啵”声中区分来自任意波段的敌人的交谈。所以不出意外的，美国国防部先进计划研究署正在支持压缩感知技术的研究。
压缩感知不仅可以用于解决现在的技术难题。将来，它还将帮助我们处理已存储的大量信息。每天，全世界都要产生数不清的数据，我们希望这些数据安全、有效、可恢复地保存起来。目前，我们大部分的视听信息都是用复杂的压缩格式存储起来的。如果有一天，这种格式被淘汰了，你不得不进行痛苦的格式转换。但是坎迪斯相信，在拥有压缩感知技术的未来，对于采用高成本红外技术拍摄的天文图像，只需要拍摄到20％的像素就可以了。因为我们一开始就只记录了极少部分的数据，所以不需要再进行压缩。那么我们只需要逐步改进数据的解析算法，而不是数据的压缩算法，就可以精确地恢复出原始图像了。
上面说的都是将来的事情。今天，压缩感知技术已经改写了我们获取医学信息的方式。在GE医疗集团的参与下，威斯康辛大学的一个研究小组正在把压缩感知技术与HYPR和VIPR技术结合，以提高特定种类磁共振扫描的速度，在某种情况下可以达到原来的几千倍。（我是这所大学的教员，但是没有参与这项研究。）GE医疗集团还在实验一种新的方法，有希望利用压缩感知技术大大改善对癌症病人代谢动力学的观测。同时，帕卡德医院应用了压缩感知技术，使磁共振成像仪的图像记录速度提升为传统扫描仪的三倍。
这对于两岁的布赖斯来说恰好够用。瓦萨纳瓦拉在控制室发出工作信号，麻醉师给男孩注射了一点镇静剂，然后关掉了呼吸机。男孩的呼吸立刻停止了。瓦萨纳瓦拉开始扫描，而麻醉师监视着布赖斯的心率和血氧水平。40秒钟之后，扫描结束，布赖斯没有出现明显的缺氧情况。当天晚些时候，压缩感知算法从粗略的扫描中生成了清晰的图像，能让瓦萨纳瓦拉看清双侧胆管的堵塞情况。一名介入放射科医生将一根弯曲的导线依次插入双侧胆管中，轻轻清除淤塞，并为男孩安装了让胆汁恰当流出的细小导管。正是数学与医学的结合，才使得布赖斯的检测结果又恢复了正常。
原文作者：
Jordan Ellenberg (ellenber@math.wisc.edu), 是威斯康辛大学的数学副教授。原文发表在《连线》杂志三月号上。
数学怎样得出那些颗粒：压缩感知技术是一种从低分辨率样本中重建高精度数据的数学工具。它可以用来重现古老的音乐录音、寻找敌人的无线电信号，并更加迅速地完成磁共振成像。这里展示的是它如何处理照片。

---

[f1]坚持用‘磁共振’的原因：1）MRI直译就是磁共振成像；2）现代人谈‘核’色变，而传统‘核磁共振’中的‘核’其实指的是原子核。因为‘核磁共振’这个名字让我们在招募fMRI实验被试时困难重重……赶明儿打算写个磁共振成像原理给大家做科普，希望以后招被试容易些……

强悍的，看这个比研究国学中的格致之学有意思多了

数学的问题是怎么来的，这篇文章做了非常好的诠释。

数字图像的压缩与恢复http://songshuhui.net/archives/37945

| Tags 标签：原创, 数字化    奥卡姆剃刀 发表于 2010-05-15 11:54

一个图像是如何数字化的呢？不妨从一张玩具鸭子图片说起。

首先要把图片打格子分成若干小块，每块用一个数字来表示一种颜色。如果图像是纯黑白两色的，那每块只用1或0表示即可。若图像是16色的，每块用4位二进数表示，因为2^4=16，即4位二进制有16种组合，每种组合表示一种颜色就行了。真彩色位图的每个小块，都是由不同等级的红绿蓝三种色彩组合的，如图所示，每种颜色有2^8个等级，所以共有2^24种颜色， 因此每小块需要24位二进制数来表示。

可见，数字图像越艳丽，则需要记录的二进制数就越多越长。除此之外，打的格子越密，则一副图的总数据量就越大，此例中鸭子图片分成了11×14=154块，按真彩色位图来计算，则总数据量为154×24=3696比特。这些小格子显然是太大了，不能表现图片的细节，实际中的格子要密得多，例如1024×768，这是大家都熟悉的显示分辩率。

看这张滑雪图，人体的色彩变化比较大，而天空和雪的色彩却非常单调，可以想象，代表每个小格颜色的数值也应该非常接近，图右下的原始数据是8个相邻格子的色彩数据，由于两个相邻格子的数据差异很小，所以可以用第一个格式数据当作第二个格子数据的预测值，经实际测量后，把真实值与预测值的差值求出来，并用这个差值来表示第二个格子的色彩。那么，实际记录下的就是第三行差值。但恢复数据时，用前面一个值加上差值，就是当前的色彩值，只要有第一位的基础值，后面的色彩值就可以滚雪球式的一个个求出来。
用差值来记录色彩，只是简单地进行了很多个减法运算，在还原时再加回来，数据并没有一丁点的损失，因此被称为无损压缩，如果把很少的差值彻底丢弃，在还原时把一个格子的色彩信息代表了周围很多格子的色彩，则压缩率更高，但格子之间的微小差别就丢失了，这种方法属于有损压缩。

位图是每个格子都独立记录的，因此数据量很大，这就是bmp格式，而经过了上述的预测差值运算后，就变成了有损压缩格式，jpg格式就是其中之一。画质基本相同的两幅图，jpg格式的数据量要比bmp小得多。jpg是有损压缩的，但画质的损失非常小。Jpg格式是很智能的，例如对上面有大面积相似色彩的山水照给予较大的压缩率，而对非常热闹的人群照给予较小的压缩率。
上面说的只是静态的图像，而视频图像压缩得更大，一秒钟视频会切换几十张画面，而这些画面的绝大部分都是相同的，采集是每幅都是独立采的，生成的avi格式的数据量是很大的，不仅每幅画面本身可以压缩，更重要的是幅与幅之间也可以压缩，这就形成了数据量小得多的mpeg格式。也可以采用压缩率更高的rm格式，rm格式的画质比mpeg差得不多，但数据量却小了很多倍，更方便在网上传输。

不同的视频，幅与幅之间的相似度是不同的，韩剧的相似度很大，甭说一秒了，甚至几分钟内演员都坐在沙发上聊，除了嘴巴外每幅画面都基本一样，对这种视频可以采用较大的压缩率，而对动感性很强的武打片，则采用较小的压缩率，这种格式就是rmvb。跟rm格式不同的是，它的压缩率是可变的，vb就是可变比特率的意思。rmvb比rm更先进，相同数据量的rmvb视频会比rm视频清晰，而相同清晰度的视频，rmvb格式的数据量会更小。
一旦进行了有损压缩，数据缺失了，画质就很难复原了，但这也并不是不可能，这里面有个关键的概念--先验信息。例如这张民国美女黑白照片的嘴唇，要压缩成这个灰度，右侧的彩色图例中有五种可能，但通过先验信息（先验信息也就是我们以前已经知道了的知识）知道，美女的嘴唇不可能是绿的、蓝的和紫的，只能是右下的红色，把它还原成红色就对了。

钢琴和弦的每一小组乐音都是由不超过五个纯音符的组合，这些排列组合的总数还是不少的，但好在根据先验信息我们知道，只有极少数的组合是经常出现的，绝大多数的组合是基本不会出现的，如果我们得到了一组模糊不清的组合，它跟经常出现的某个组合与基本不会出现的某个组合的相似度一样，那我们就毫不犹豫地认定它就是那个经常出现的组合。
当然，实际上它不是那个经常出现的组合，而是那个基本不会出现的组合，这种可能性也是不能排除的，就好比那个民国美女真的长了一副蓝嘴唇一样，我们依靠先验信息做的判断就杯具了，但这是没办法的事。
现在的核磁共振技术在短时间内只能获得比较粗糙的图像，但我们知道被照器官的每一小块部分与相邻部分的相关性是很强的，而且我们对这些器官也具有很多先验信息，这就可以帮助我们像还原民国美女图那样，在粗糙的图像上还原出高画质的图像，可信度还可以做得非常高。

按照这样的理论，我只要用50w像素的相机拍摄，但是可以根据数学推算变成超过1000w像素的照片？
那日本人不是白忙了

sour 发表于 2011-6-12 17:50
按照这样的理论，我只要用50w像素的相机拍摄，但是可以根据数学推算变成超过1000w像素的照片？
那日本人不是白忙了

同样的道理，可以运用到音乐文件当中，这个比mp3厉害，不知道能不能行。

我看到其他部门的人在销售监视器画面清晰化的软件，不知道是不是一个原理的。

茉莉清茶 发表于 2011-6-13 10:48
我看到其他部门的人在销售监视器画面清晰化的软件，不知道是不是一个原理的。

应该也是一种算法，这个有专利，应该不是一样的算法

sour 发表于 2011-6-13 10:57
应该也是一种算法，这个有专利，应该不是一样的算法

以前看电影，不是经常有这种镜头。
就是警察分析监视器画面，本来很模糊的，一按键罪犯的面孔就特别清晰地刷新出来了。
我以前总是想，很牛啊，像素那么低，怎么会变清晰的呢，依据是什么呢？

茉莉清茶 发表于 2011-6-13 11:09
以前看电影，不是经常有这种镜头。
就是警察分析监视器画面，本来很模糊的，一按键罪犯的面孔就特别清晰地刷新出来了。
我以前总是想，很牛啊，像素那么低，怎么会变清晰的呢，依据是什么呢？

说老实话，我看了这个文章才真的弄明白，以前只知道是去推算，不知道怎么算的

数字如潮人如水同人于野http://www.geekonomics10000.com/463

                                 结果这篇文章被CCTV2《第1时间》报道了：

欢迎来到数字时代。很可能你已经有了能够随时随地上网的手机，玩3D网络游戏，想看任何电影都能在几小时甚至几秒钟之内下载到高清版本。十五年前尼葛洛庞 帝的《数字化生存》中描写的那个无限带宽，一千多个电视频道外加无处不在的界面友好的计算机的世界，正在慢慢变成现实。然而相对于我们正在经历的另一场静 悄悄的数字革命来说，这个把数字化等同于玩电脑的境界已经过时了。
有这么一位富有的美国老太太，她的业余爱好是赌博。她经常抱着小赌怡情 的态度光顾赌场，输点小钱从不放在心上。可是如果有一晚上输得太多，她也有可能会痛定思痛从此戒赌。有一个下午她总是输，当她输的钱接近900美元的时 候，一个服务员笑容可掬地走了过来。“看来您今天运气不太好啊。不如就玩到这吧，我们的牛排很不错，要不您跟您先生去吃顿晚饭？算我们请客！”
这 位老太太可能连手机都不会用，但是她正在经历另一种数字化生存：她本人被数字化了。这家赌场实时地知道每一位顾客的赌博记录，他们根据这位顾客的年龄，收 入和住址等个人信息以及赌博习惯，可以计算该顾客的  “疼痛点”：一晚上最多输多少钱下次还能再来玩。赌场一旦发现某位顾客今天输的钱接近疼痛点，免费牛排之类的节目就出场了。
其实我们每个 人都正在被数字化。网上书店会根据你以往买书的记录向你推荐你可能感兴趣的书，这个算法的准确性可以超过任何专家或朋友。世界最大的在线影片租赁服务商 Netflix超过三分之二的DVD是通过这种关联推荐被租借的。而正因为这个推荐系统，90%的电影每个月至少会被租借一次，实现所谓的“长尾”现象。
这 仅仅是冰山一角。据耶鲁大学法学院教授 Ian Ayres 的 Super Crunchers  一书介绍，每个人的各种个人信息，经常在哪个商店购物，常买哪个牌子的衣服，甚至每一次消费的记录，收到的每一张超速罚单，都正在被商业公司收集利用。根 据这些信息，使用统计回归算法，商家可以知道你的很多事情。以前航空公司的原则是你飞得越多就对你越好，而现在则利用你的所有数据来计算你的“忠诚度”。 一次航班误点或者行李丢失事件发生之后，如果数字算法判断某个长期顾客有可能要因此从此不飞这个公司了，这位客户就会得到特别好的照顾。类似地，租车公司 可能会拒绝为信用历史差的人服务，因为数据分析显示信用分数差的人更容易出车祸。而政客则可以根据你的一揽子数据判断你支持哪个党，可能捐多少钱，从而实 现精确募捐。商家甚至知道连你自己都不知道的事情，比如 DVD 出租店可以预测你不能按时还片的可能性。
最可怕的是商家可以精确估算每 一个顾客的价格敏感度，从而实现自古以来所有商店的梦想：给每个人看一个不同的定价。据说亚马逊就做过，同样一个商品，那些花钱大手大脚的顾客在网站看到 的价格比精打细算的顾客看到的高。在顾客的抗议下亚马逊保证永远都不再这么做了 — 但商家有更好的办法，比如给对价格敏感的顾客寄减价券。
在 这场数字化革命中，每个人都是一大堆数字，而数字有价。Acxiom 号称是“你所没听说过的最大的公司之一”，它拥有几乎所有美国家庭的消费信息。根据这些记录，该公司把所有人按消费习惯分为70类，知道比如那些人爱出国 旅游，哪些人喜欢呆在家里。实际上，它不但知道你现在属于哪种类型，而且可以预测你明年将会属于哪种类型。Teradata  则是一个专门给企业提供数据分析服务的公司，它可以根据货架上剩下商品的实时信息来预测沃尔玛是否需要立即增加库存。
这些公司获得个人数 据的一个渠道是政府和容易得到的公开信息，比如婚姻状况，车辆和房产注册，当然还包括信用记录。更重要的数字来源则是直接从零售商买。消费者在亚马逊和沃 尔玛的所有记录都被当成一种重要资源出售给了 Acxiom  这样的数据集成公司。另一方面，零售商对各种数字的收集则达到了惊人的程度：比如说超市会精确记录一个品牌的牙膏在货架的摆放位置，因为摆放位置可能会影 响到牙膏的销量，而牙膏放在第几层最好卖这个知识是有人愿意花钱买的。
除了获得已有的数据之外，商业公司还可以在原本没有数据的地方“采 集”数据，这就是随机试验方法。比如说有个公司想搞个促销活动，有两种可供选择的促销手段无法定夺。这个公司可以随机地选择一小部分顾客分为两组，把两种 促销手段分别作为广告寄给这两个组。这样一来，被当成小白鼠的这些顾客对广告的反映，可以告诉公司哪种手段值得推广到所有顾客。有了随机测试这个办法，商 业公司在采取新策略的时候会变得更加大胆，从而有一些意想不到的成功。
在网上书店买过几本书，书店就会经常向你推荐类似的书。刚刚找到一 份好工作，高档消费品的广告就寄到家里来了。走进一家从没去过的餐馆，服务员居然知道你喜欢哪种啤酒。这种生活看上去相当不错 —  可是事情还有另一面。书店知道你对喜欢的书根本不在乎多花10%的钱。服装店知道没必要让你这种顾客知道最近正在打折。餐馆服务员知道什么啤酒能让你多喝 几瓶。
如果一个人在什么时间买了一双价值多少钱的鞋这样的信息可以直接影响她将来消费要面临的价格水平，那么买鞋算不算需要保护的个人隐 私？如果人脸识别技术成熟以后，我们随便上趟街都会被记录在案，那么这个记录是否应该允许被商业公司拥有？
但是消费者也可以利用数字反 击。2008 年，微软收购了 Farecast  公司，这个公司干的事儿是帮助消费者对各个航空公司进行数字分析。它使用一大堆数字指标，实时地监测机票价格，然后预测票价的走向。我们都知道买机票并不 是越早买越便宜，但是什么时候最便宜？ Farecast  知道。实际上，它甚至可以卖给你一个价格保险，如果到时候机票价格没降下来，它承担损失。去年，Farecast 已经被集成在 Bing 之中。
在 这个新数字时代，人是一堆数字。我们到底是数字的主人，还是数字的奴隶？也许第一步是要知道数字的重要性。如果你不想被数字玩，你最好学会玩数字。
（此文发表于5月1日的《新知客》，杂志应该已经上市了。我还没看到最终版本，上面也许还会有对四个玩数字的公司的介绍。）