[转载]压缩传感——陶哲轩作者： 杨明 YY
最近有不少人问我究竟”压缩感知”是什么意思，所谓“单像素相机”又是怎样工作的。这个课题已经有了大量文献，不过对于这么一个相对比较新的领域，还没有一篇优秀的非技术性介绍。所以笔者在此小做尝试，希望能够对非数学专业的读者有所帮助。
相机的用途，自然是记录图像。为了简化论述，我们把图像假设成一个长方形阵列，比如说一个1024×2048像素的阵列（这样就总共是二百万像素）。为了省略彩色的问题（这个比较次要），我们就假设只需要黑白图像，那么每个像素就可以用一个整型的灰度值来计量其亮度（例如用八位整型数表示0到 255，16位表示0到65535）。
接下来，按照最最简化的说法，传统相机会测量每一个像素的亮度（在上述例子中就是二百万个测量值），结果得到的图片文件就比较大（用8位灰度值就是2MB，16位灰度就是4MB）。数学上就认为这个文件是用超高维矢量值描绘的（在本例中就是约二百万维）。
在我开始讲“压缩感知”这个新故事之前，必须先快速回顾一下“老式压缩”的旧故事。（已经了解图像压缩算法的读者可以跳过这几段。）
上述的图片会占掉相机的很多存储空间（上传到计算机里还占磁盘空间），在各种介质之间传输的时候也要浪费时间。于是，相机带有显著压缩图像的功能就顺理成章了（通常能从2MB那么大压缩到十分之一——200KB的一小坨）。关键是尽管“所有图片”所构成的空间要占用2MB的“自由度”或者说“熵”，由“有意义的图片”所构成的空间其实要小得多，尤其是如果人们愿意降低一点图像质量的话。（实际上，如果一个人真的利用所有的自由度随机生成一幅图片，他不大可能得到什么有意义的图像，而是得到相当于电视荧屏上的静电雪花那样的随机噪声之类。）
怎么样压缩图像？方式多种多样，其中有些非常先进，不过我来试试用一种不太高科技的（而且也不太精确的）说法来描述一下这些先进技术。图像通常都含有大片无细节部分–比如在风景照里面，将近一半的画面都可能被单色的天空背景占据。我们假设提取一个大方块，比方说100×100像素，其中完全是同一颜色的——假设是全白的吧。无压缩时，这个方块要占10000字节存储空间（按照8位灰度算）；但是我们可以只记录这个方块的维度和坐标，还有填充整个方块的单一颜色；这样总共也只要记录四五个字节，省下了可观的空间。不过在现实中，压缩效果没有这么好，因为表面看来没有细节的地方其实是有着细微的色差的。所以，给定一个无细节方块，我们记录其平均色值，就把图片中这一块区域抽象成了单色色块，只留下微小的残余误差。接下来就可以继续选取更多色彩可见的方块，抽象成单色色块。最后剩下的是亮度（色彩强度）很小的，肉眼无法察觉的细节。于是就可以抛弃这些剩余的细节，只需要记录那些“可见”色块的大小，位置和亮度。日后则可以反向操作，重建出比原始图像质量稍低一些，占空间却小得多的复制图片。
其实上述的算法并不适合处理颜色剧烈变动的情况，所以在实际应用中不很有效。事实上，更好的办法不是用均匀色块，而是用“不均匀”的色块——比方说右半边色彩强度平均值大于左半边这样的色块。这种情况可以用（二维）Haar小波系统来描述。后来人们又发现一种”更平滑的”小波系统更能够避免误差，不过这都是技术细节，我们就不深入讨论了。然而所有这些系统的原理都是相同的：把原始图像表示为不同“小波（类似于上文中的色块）”的线性叠加，记录显著的（高强度的）小波的系数，放弃掉（或者用阈值排除掉）剩下的小波系数。这种“小波系数硬阈值”压缩算法没有实际应用的算法（比如JPEG 2000标准中所定义的）那么精细，不过多少也能描述压缩的普遍原理。
总体来讲（也是非常简化的说法），原始的1024×2048图像可能含有两百万自由度，想要用小波来表示这个图像的人需要两百万个不同小波才能完美重建。但是典型的有意义的图像，从小波理论的角度看来是非常稀疏的，也就是可压缩的：可能只需要十万个小波就已经足够获取图像所有的可见细节了，其余一百九十万小波只贡献很少量的，大多数观测者基本看不见的“随机噪声”。（这也不是永远适用：含有大量纹理的图像–比如毛发、毛皮的图像——用小波算法特别难压缩，也是图像压缩算法的一大挑战。不过这是另一个故事了。）
接下来呢，如果我们（或者不如说是相机）事先知道两百万小波系数里面哪十万个是重要的，那就可以只计量这十万个系数，别的就不管了。（在图像上设置一种合适的“过滤器”或叫“滤镜”，然后计量过滤出来的每个像素的色彩强度，是一种可行的系数计量方法。）但是，相机是不会知道哪个系数是重要的，所以它只好计量全部两百万个像素，把整个图像转换成基本小波，找出需要留下的那十万个主导基本小波，再删掉其余的。（这当然只是真正的图像压缩算法的一个草图，不过为了便于讨论我们还是就这么用吧。）
那么，如今的数码相机当然已经很强大了，没什么问题干吗还要改进？事实上，上述的算法，需要收集大量数据，但是只需要存储一部分，在消费摄影中是没有问题的。尤其是随着数据存储变得很廉价，现在拍一大堆完全不压缩的照片也无所谓。而且，尽管出了名地耗电，压缩所需的运算过程仍然算得上轻松。但是，在非消费领域的某些应用中，这种数据收集方式并不可行，特别是在传感器网络中。如果打算用上千个传感器来收集数据，而这些传感器需要在固定地点呆上几个月那么长的时间，那么就需要尽可能地便宜和节能的传感器——这首先就排除了那些有强大运算能力的传感器（然而——这也相当重要——我们在接收处理数据的接收端仍然需要现代科技提供的奢侈的运算能力）。在这类应用中，数据收集方式越“傻瓜”越好（而且这样的系统也需要很强壮，比如说，能够忍受10%的传感器丢失或者各种噪声和数据缺损）。
这就是压缩传感的用武之地了。其理论依据是：如果只需要10万个分量就可以重建绝大部分的图像，那何必还要做所有的200万次测量，只做10万次不就够了吗？（在实际应用中，我们会留一个安全余量，比如说测量30万像素，以应付可能遭遇的所有问题，从干扰到量化噪声，以及恢复算法的故障。）这样基本上能使节能上一个数量级，这对消费摄影没什么意义，对传感器网络而言却有实实在在的好处。
不过，正像我前面说的，相机自己不会预先知道两百万小波系数中需要记录哪十万个。要是相机选取了另外10万（或者30万），反而把图片中所有有用的信息都扔掉了怎么办？
解决的办法简单但是不太直观。就是用非小波的算法来做30万个测量——尽管我前面确实讲过小波算法是观察和压缩图像的最佳手段。实际上最好的测量其实应该是（伪）随机测量——比如说随机生成30万个“滤镜”图像并测量真实图像与每个滤镜的相关程度。这样，图像与滤镜之间的这些测量结果（也就是“相关性”）很有可能是非常小非常随机的。但是——这是关键所在——构成图像的2百万种可能的小波函数会在这些随机的滤镜的测量下生成自己特有的“特征”，它们每一个都会与某一些滤镜成正相关，与另一些滤镜成负相关，但是与更多的滤镜不相关。可是（在极大的概率下）2百万个特征都各不相同；更有甚者，其中任意十万个的线性组合仍然是各不相同的（以线性代数的观点来看，这是因为一个30万维线性子空间中任意两个10万维的子空间极有可能互不相交）。因此，基本上是有可能从这30万个随机数据中恢复图像的（至少是恢复图像中的10万个主要细节）。简而言之，我们是在讨论一个哈希函数的线性代数版本。
然而这种方式仍然存在两个技术问题。首先是噪声问题：10万个小波系数的叠加并不能完全代表整幅图像，另190万个系数也有少许贡献。这些小小贡献有可能会干扰那10万个小波的特征，这就是所谓的“失真”问题。第二个问题是如何运用得到的30万测量数据来重建图像。
我们先来关注后一个问题。如果我们知道了2百万小波中哪10万个是有用的，那就可以使用标准的线性代数方法（高斯消除法，最小二乘法等等）来重建信号。（这正是线性编码最大的优点之一——它们比非线性编码更容易求逆。大多数哈希变换实际上是不可能求逆的——这在密码学上是一大优势，在信号恢复中却不是。）可是，就像前面说的那样，我们事前并不知道哪些小波是有用的。怎么找出来呢？一个单纯的最小二乘近似法会得出牵扯到全部2百万系数的可怕结果，生成的图像也含有大量颗粒噪点。要不然也可以代之以一种强力搜索，为每一组可能的10万关键系数都做一次线性代数处理，不过这样做的耗时非常恐怖（总共要考虑大约10的17万次方个组合！），而且这种强力搜索通常是NP完备的（其中有些特例是所谓的“子集合加总”问题）。不过还好，还是有两种可行的手段来恢复数据：
• 匹配追踪：找到一个其标记看上去与收集到的数据相关的小波；在数据中去除这个标记的所有印迹；不断重复直到我们能用小波标记“解释”收集到的所有数据。
• 基追踪（又名L1模最小化）：在所有与录得数据匹配的小波组合中，找到一个“最稀疏的”，也就是其中所有系数的绝对值总和越小越好。（这种最小化的结果趋向于迫使绝大多数系数都消失了。）这种最小化算法可以利用单纯形法之类的凸规划算法，在合理的时间内计算出来。
需要注意到的是，这类图像恢复算法还是需要相当的运算能力的（不过也还不是太变态），不过在传感器网络这样的应用中这不成问题，因为图像恢复是在接收端（这端有办法连接到强大的计算机）而不是传感器端（这端就没办法了）进行的。
现在已经有严密的结果显示，对原始图像设定不同的压缩率或稀疏性，这两种算法完美或近似完美地重建图像的成功率都很高。匹配追踪法通常比较快，而基追踪算法在考虑到噪声时则显得比较准确。这些算法确切的适用范围问题在今天仍然是非常热门的研究领域。（说来遗憾，目前还没有出现对P不等于NP问题的应用；如果一个重建问题（在考虑到测量矩阵时）是NP完备的，那它刚好就不能用上述算法解决。）
由于压缩传感还是一个相当新的领域（尤其是严密的数学结果刚刚出现），现在就期望这个技术应用到实用的传感器上还为时尚早。不过已经有概念验证模型出现了，其中最著名的是Rice大学研制的单像素相机。
最后必须提到的是，压缩传感技术是一种抽象的数学概念，而不是具体的操作方案，它可以应用到成像以外的许多领域。以下只是其中几个例子：
• 磁共振成像(MRI)。在医学上，磁共振的工作原理是做许多次（但次数仍是有限的）测量（基本上就是对人体图像进行离散拉东变换（也叫X光变换）），再对数据进行加工来生成图像（在这里就是人体内水的密度分布图像）。由于测量次数必须很多，整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数，加快成像（甚至有可能做到实时成像，也就是核磁共振的视频而非静态图像）。此外我们还可以以测量次数换图像质量，用与原来一样的测量次数可以得到好得多的图像分辨率。
• 天文学。许多天文现象（如脉冲星）具有多种频率震荡特性，使其在频域上是高度稀疏也就是可压缩的。压缩传感技术将使我们能够在时域内测量这些现象（即记录望远镜数据）并能够精确重建原始信号，即使原始数据不完整或者干扰严重（原因可能是天气不佳，上机时间不够，或者就是因为地球自传使我们得不到全时序的数据）。
• 线性编码。压缩传感技术提供了一个简单的方法，让多个传送者可以将其信号带纠错地合并传送，这样即使输出信号的一大部分丢失或毁坏，仍然可以恢复出原始信号。例如，可以用任意一种线性编码把1000比特信息编码进一个3000比特的流；那么，即使其中300位被（恶意）毁坏，原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号（只集中在3000比特中的300位）。
许多这种应用都还只停留在理论阶段，可是这种算法能够影响测量和信号处理中如此之多的领域，其潜力实在是振奋人心。笔者自己最有成就感的就是能看到自己在纯数学领域的工作（例如估算傅立叶子式的行列式或单数值）最终具备造福现实世界的前景。
相机的用途，自然是记录图像。为了简化论述，我们把图像假设成一个长方形阵列，比如说一个1024×2048像素的阵列（这样就总共是二百万像素）。为了省略彩色的问题（这个比较次要），我们就假设只需要黑白图像，那么每个像素就可以用一个整型的灰度值来计量其亮度（例如用八位整型数表示0到 255，16位表示0到65535）。
接下来，按照最最简化的说法，传统相机会测量每一个像素的亮度（在上述例子中就是二百万个测量值），结果得到的图片文件就比较大（用8位灰度值就是2MB，16位灰度就是4MB）。数学上就认为这个文件是用超高维矢量值描绘的（在本例中就是约二百万维）。
在我开始讲“压缩感知”这个新故事之前，必须先快速回顾一下“老式压缩”的旧故事。（已经了解图像压缩算法的读者可以跳过这几段。）
上述的图片会占掉相机的很多存储空间（上传到计算机里还占磁盘空间），在各种介质之间传输的时候也要浪费时间。于是，相机带有显著压缩图像的功能就顺理成章了（通常能从2MB那么大压缩到十分之一——200KB的一小坨）。关键是尽管“所有图片”所构成的空间要占用2MB的“自由度”或者说“熵”，由“有意义的图片”所构成的空间其实要小得多，尤其是如果人们愿意降低一点图像质量的话。（实际上，如果一个人真的利用所有的自由度随机生成一幅图片，他不大可能得到什么有意义的图像，而是得到相当于电视荧屏上的静电雪花那样的随机噪声之类。）
怎么样压缩图像？方式多种多样，其中有些非常先进，不过我来试试用一种不太高科技的（而且也不太精确的）说法来描述一下这些先进技术。图像通常都含有大片无细节部分–比如在风景照里面，将近一半的画面都可能被单色的天空背景占据。我们假设提取一个大方块，比方说100×100像素，其中完全是同一颜色的——假设是全白的吧。无压缩时，这个方块要占10000字节存储空间（按照8位灰度算）；但是我们可以只记录这个方块的维度和坐标，还有填充整个方块的单一颜色；这样总共也只要记录四五个字节，省下了可观的空间。不过在现实中，压缩效果没有这么好，因为表面看来没有细节的地方其实是有着细微的色差的。所以，给定一个无细节方块，我们记录其平均色值，就把图片中这一块区域抽象成了单色色块，只留下微小的残余误差。接下来就可以继续选取更多色彩可见的方块，抽象成单色色块。最后剩下的是亮度（色彩强度）很小的，肉眼无法察觉的细节。于是就可以抛弃这些剩余的细节，只需要记录那些“可见”色块的大小，位置和亮度。日后则可以反向操作，重建出比原始图像质量稍低一些，占空间却小得多的复制图片。
其实上述的算法并不适合处理颜色剧烈变动的情况，所以在实际应用中不很有效。事实上，更好的办法不是用均匀色块，而是用“不均匀”的色块——比方说右半边色彩强度平均值大于左半边这样的色块。这种情况可以用（二维）Haar小波系统来描述。后来人们又发现一种”更平滑的”小波系统更能够避免误差，不过这都是技术细节，我们就不深入讨论了。然而所有这些系统的原理都是相同的：把原始图像表示为不同“小波（类似于上文中的色块）”的线性叠加，记录显著的（高强度的）小波的系数，放弃掉（或者用阈值排除掉）剩下的小波系数。这种“小波系数硬阈值”压缩算法没有实际应用的算法（比如JPEG 2000标准中所定义的）那么精细，不过多少也能描述压缩的普遍原理。
总体来讲（也是非常简化的说法），原始的1024×2048图像可能含有两百万自由度，想要用小波来表示这个图像的人需要两百万个不同小波才能完美重建。但是典型的有意义的图像，从小波理论的角度看来是非常稀疏的，也就是可压缩的：可能只需要十万个小波就已经足够获取图像所有的可见细节了，其余一百九十万小波只贡献很少量的，大多数观测者基本看不见的“随机噪声”。（这也不是永远适用：含有大量纹理的图像–比如毛发、毛皮的图像——用小波算法特别难压缩，也是图像压缩算法的一大挑战。不过这是另一个故事了。）
接下来呢，如果我们（或者不如说是相机）事先知道两百万小波系数里面哪十万个是重要的，那就可以只计量这十万个系数，别的就不管了。（在图像上设置一种合适的“过滤器”或叫“滤镜”，然后计量过滤出来的每个像素的色彩强度，是一种可行的系数计量方法。）但是，相机是不会知道哪个系数是重要的，所以它只好计量全部两百万个像素，把整个图像转换成基本小波，找出需要留下的那十万个主导基本小波，再删掉其余的。（这当然只是真正的图像压缩算法的一个草图，不过为了便于讨论我们还是就这么用吧。）
那么，如今的数码相机当然已经很强大了，没什么问题干吗还要改进？事实上，上述的算法，需要收集大量数据，但是只需要存储一部分，在消费摄影中是没有问题的。尤其是随着数据存储变得很廉价，现在拍一大堆完全不压缩的照片也无所谓。而且，尽管出了名地耗电，压缩所需的运算过程仍然算得上轻松。但是，在非消费领域的某些应用中，这种数据收集方式并不可行，特别是在传感器网络中。如果打算用上千个传感器来收集数据，而这些传感器需要在固定地点呆上几个月那么长的时间，那么就需要尽可能地便宜和节能的传感器——这首先就排除了那些有强大运算能力的传感器（然而——这也相当重要——我们在接收处理数据的接收端仍然需要现代科技提供的奢侈的运算能力）。在这类应用中，数据收集方式越“傻瓜”越好（而且这样的系统也需要很强壮，比如说，能够忍受10%的传感器丢失或者各种噪声和数据缺损）。
这就是压缩传感的用武之地了。其理论依据是：如果只需要10万个分量就可以重建绝大部分的图像，那何必还要做所有的200万次测量，只做10万次不就够了吗？（在实际应用中，我们会留一个安全余量，比如说测量30万像素，以应付可能遭遇的所有问题，从干扰到量化噪声，以及恢复算法的故障。）这样基本上能使节能上一个数量级，这对消费摄影没什么意义，对传感器网络而言却有实实在在的好处。
不过，正像我前面说的，相机自己不会预先知道两百万小波系数中需要记录哪十万个。要是相机选取了另外10万（或者30万），反而把图片中所有有用的信息都扔掉了怎么办？
解决的办法简单但是不太直观。就是用非小波的算法来做30万个测量——尽管我前面确实讲过小波算法是观察和压缩图像的最佳手段。实际上最好的测量其实应该是（伪）随机测量——比如说随机生成30万个“滤镜”图像并测量真实图像与每个滤镜的相关程度。这样，图像与滤镜之间的这些测量结果（也就是“相关性”）很有可能是非常小非常随机的。但是——这是关键所在——构成图像的2百万种可能的小波函数会在这些随机的滤镜的测量下生成自己特有的“特征”，它们每一个都会与某一些滤镜成正相关，与另一些滤镜成负相关，但是与更多的滤镜不相关。可是（在极大的概率下）2百万个特征都各不相同；更有甚者，其中任意十万个的线性组合仍然是各不相同的（以线性代数的观点来看，这是因为一个30万维线性子空间中任意两个10万维的子空间极有可能互不相交）。因此，基本上是有可能从这30万个随机数据中恢复图像的（至少是恢复图像中的10万个主要细节）。简而言之，我们是在讨论一个哈希函数的线性代数版本。
然而这种方式仍然存在两个技术问题。首先是噪声问题：10万个小波系数的叠加并不能完全代表整幅图像，另190万个系数也有少许贡献。这些小小贡献有可能会干扰那10万个小波的特征，这就是所谓的“失真”问题。第二个问题是如何运用得到的30万测量数据来重建图像。
我们先来关注后一个问题。如果我们知道了2百万小波中哪10万个是有用的，那就可以使用标准的线性代数方法（高斯消除法，最小二乘法等等）来重建信号。（这正是线性编码最大的优点之一——它们比非线性编码更容易求逆。大多数哈希变换实际上是不可能求逆的——这在密码学上是一大优势，在信号恢复中却不是。）可是，就像前面说的那样，我们事前并不知道哪些小波是有用的。怎么找出来呢？一个单纯的最小二乘近似法会得出牵扯到全部2百万系数的可怕结果，生成的图像也含有大量颗粒噪点。要不然也可以代之以一种强力搜索，为每一组可能的10万关键系数都做一次线性代数处理，不过这样做的耗时非常恐怖（总共要考虑大约10的17万次方个组合！），而且这种强力搜索通常是NP完备的（其中有些特例是所谓的“子集合加总”问题）。不过还好，还是有两种可行的手段来恢复数据：
• 匹配追踪：找到一个其标记看上去与收集到的数据相关的小波；在数据中去除这个标记的所有印迹；不断重复直到我们能用小波标记“解释”收集到的所有数据。
• 基追踪（又名L1模最小化）：在所有与录得数据匹配的小波组合中，找到一个“最稀疏的”，也就是其中所有系数的绝对值总和越小越好。（这种最小化的结果趋向于迫使绝大多数系数都消失了。）这种最小化算法可以利用单纯形法之类的凸规划算法，在合理的时间内计算出来。
需要注意到的是，这类图像恢复算法还是需要相当的运算能力的（不过也还不是太变态），不过在传感器网络这样的应用中这不成问题，因为图像恢复是在接收端（这端有办法连接到强大的计算机）而不是传感器端（这端就没办法了）进行的。
现在已经有严密的结果显示，对原始图像设定不同的压缩率或稀疏性，这两种算法完美或近似完美地重建图像的成功率都很高。匹配追踪法通常比较快，而基追踪算法在考虑到噪声时则显得比较准确。这些算法确切的适用范围问题在今天仍然是非常热门的研究领域。（说来遗憾，目前还没有出现对P不等于NP问题的应用；如果一个重建问题（在考虑到测量矩阵时）是NP完备的，那它刚好就不能用上述算法解决。）
由于压缩传感还是一个相当新的领域（尤其是严密的数学结果刚刚出现），现在就期望这个技术应用到实用的传感器上还为时尚早。不过已经有概念验证模型出现了，其中最著名的是Rice大学研制的单像素相机。
最后必须提到的是，压缩传感技术是一种抽象的数学概念，而不是具体的操作方案，它可以应用到成像以外的许多领域。以下只是其中几个例子：
• 磁共振成像(MRI)。在医学上，磁共振的工作原理是做许多次（但次数仍是有限的）测量（基本上就是对人体图像进行离散拉东变换（也叫X光变换）），再对数据进行加工来生成图像（在这里就是人体内水的密度分布图像）。由于测量次数必须很多，整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数，加快成像（甚至有可能做到实时成像，也就是核磁共振的视频而非静态图像）。此外我们还可以以测量次数换图像质量，用与原来一样的测量次数可以得到好得多的图像分辨率。
• 天文学。许多天文现象（如脉冲星）具有多种频率震荡特性，使其在频域上是高度稀疏也就是可压缩的。压缩传感技术将使我们能够在时域内测量这些现象（即记录望远镜数据）并能够精确重建原始信号，即使原始数据不完整或者干扰严重（原因可能是天气不佳，上机时间不够，或者就是因为地球自传使我们得不到全时序的数据）。
• 线性编码。压缩传感技术提供了一个简单的方法，让多个传送者可以将其信号带纠错地合并传送，这样即使输出信号的一大部分丢失或毁坏，仍然可以恢复出原始信号。例如，可以用任意一种线性编码把1000比特信息编码进一个3000比特的流；那么，即使其中300位被（恶意）毁坏，原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号（只集中在3000比特中的300位）。
许多这种应用都还只停留在理论阶段，可是这种算法能够影响测量和信号处理中如此之多的领域，其潜力实在是振奋人心。笔者自己最有成就感的就是能看到自己在纯数学领域的工作（例如估算傅立叶子式的行列式或单数值）最终具备造福现实世界的前景。
No comments:
Post a Comment