新宿駅8番線

从今天开始的《图像压缩原理基础》将会以大约每周一篇的速度，用浅显易懂的语言讲述静态图像以及动态图像压缩的原理。这个系列的文章既是我在向大家讲述视频压缩的基础知识，同时也是我在学习这些知识的“学习笔记”。
* 本文（包含其插图）严禁转载，并且不会同意您的转载请求。如有需要引用或介绍本文，您可以提供本文的连接。

本节以JPEG为例，讲解静态图像压缩的原理。JPEG图像压缩主要分为下面四个过程，离散余弦变换、量化、编码以及组成位数据流。下面通过一个简单的例子说明各步骤的原理。
1.离散余弦变换
(1)通过离散余弦变换（DCT变换，下略），可以将能量集中在矩阵左上角的少数几个系数上。简单地说，我们可以将DCT看作用一个8行8列的二维数组产生另一个8行8列的二维数组的函数。也就是说，把一个数组通过某种变换，变成另一个数组。
首先将一幅图像划分成一个个8*8像素的图像块。比如，原图的尺寸是640*480，那么将会被划分成80行60列的图像块。如果图像只包含灰度，那么每个象素都会用一个8bit的数字表示。因此可以将每个图像块表示成一个8行8列的二维数组，这个数组中每个元素都是0~255的8bit整数。DCT变换就是作用在这个数组上。再看一下彩色的情况。如果图像是彩色的，那么每个象素都可以用24bit、相当于3个8bit的组合来表示。因此可以用3个8行8列的数组来表示这个8*8的图像块。DCT变换作用于每一个数组。
(2)用f表示像素值的数组，f(i,j)表示第i行第j列的值，则DCT变换之后定义一个新的数组F(u,v)表示第u行v列的值。

DCT变换通过下面公式完成：

逆DCT变换公式：

在上面两公式中，当u,v=0时，，其他情况下，C(u),C(v)=1。
下面举例说明。下面矩阵表示一个8*8的图像样本的原始数组。

为了便于计算，在进行变换之前先对原始图像中的每个样本数据减去128。然后再按照公式计算出数组中每个元素的值。举F(0,0)的值的计算过程如下：

按照这样，继续计算其他值：

f(i,j)经过DCT变换之后得到了F(i,j)，其中F(0,0)是直流系数，称为DC系数，其他的为交流系数，称为AC系数。

2.量化
为了达到压缩的目的，我们需要对经过DCT变换的DCT系数进行量化，目的是减小非0系数的幅度以增加0值系数的数目。在一定的主观保真的前提下，丢掉那些对视觉效果影响不大的数据。量化是压缩过程中造成质量下降的最主要原因。
因为人眼对于亮度的感知能力高于色度，JPEG压缩时使用了两个量化表——色度量化表和亮度量化表。

对于上面的例子，我们使用亮度量化表对其进行量化，得到数组Q(i,j)。量化的公式是：

其中U(i,j)为量化表中第i行j列的值。也就是说，要用数组F中的每一个元素除以量化表中起对应位置的值。按照这个公式，我们对上面例子中的数组F进行量化后得到如下结果Q：

我们很高兴地看到，呃……基本上都变成了0。

3.编码
z形排列：对图像块进行DCT变换后，能量集中在矩阵左上角的少数几个系数上。所以一般左上角的数值比较大，而0则主要集中在矩阵右下角。为了增加连续的0的个数，我们采用z形排列（zigzag），以便更好地压缩数据。这样，我们就能把一个8*8的矩阵转换成一个1*64的矢量。我们将上面经过量化的结果Q进行z形排列，如下所示：

经过z形排列之后，结果变成了：15 0 -2 -1 -1 -1 0 0 -1 0 0 ……后面全部是连续的0，这样一来，连续0的个数变多了。
DC系数编码：8*8图块经过DCT变换后得到的DC系数有两个特点，一个是数值很大，另一个是相邻两个图块之间的DC系数很相近。因此，JPEG采用取DPCM编码对DC系数差进行编码。公式如下：

其中Delta为差值，即差值为当前图块DC系数减去上一个图块的DC系数。
AC系数的编码：经过量化的AC系数的特点是有很多连续的0。所以可以使用非常简单和直观的RLE编码对其进行编码。
霍夫曼编码（[size=-1]*注1 注2）：在JPEG有损压缩中，使用霍夫曼编码来减少熵（读Shang，1声）。压缩数据符号的时候，霍夫曼编码器对出现频率较高的符号使用较短的代码，对于出现频率较低的符号使用较长的代码，最终使得编码的平均码字最短。

4.组成数据位流
JPEG编码的最后一步为把各种标记代码和编码后的图像组成数据，这样做的目的是为了便于传输、存储和译码器进行译码。

注1：JPEG标准也允许（但是并不要求）使用在数学上优于霍夫曼编码的算术编码。然而，这个特色几乎很少被使用，因为它被专利所涵盖，且它相较于霍夫曼编码在编码和解码上会更慢。使用算术编码一般会让档案更小约 5%。
注2：Huffman编码，除“霍夫曼编码”外，还有“哈夫曼编码”等其他译法存在。

本文参考资料：
《多媒体技术基础》 雷运发主编 中国水利水电出版社 2005年4月出版
中文Wikipedia中关于JPEG的条目：http://zh.wikipedia.org/wiki/JPEG

转眼间，夏天到了——在这里，似乎夏天来得比别的地方都晚。尽管人们早就穿上了短衣短裤，但是潜意识中，期待的那几样夏天的标志，之前还都没来。比如蚊子、雷阵雨、闷热、高温等等。
前些日子说过“连续两周的阴雨刚刚过去”，谁知那只是夏天的开始。不知道是今年气候异常还是怎么的，每天午后这里一定会下雨。哈尔滨的阵雨真厉害，雨来的又急又快，雨点大，乘着风砸在地上能溅起来很高。
昨天晚上睡觉的时候，隐约听到耳边有嗡嗡的声音，这才一下子意识到，啊，原来夏天已经来了。今天早晨，果然发现手上多了一个小小的包，不断发痒。于是拿出上个星期买的花露水喷在上面，感觉立刻好了不少。只是喷了一下花露水而已，房间里面立刻溢满了浓浓的花香。陕西同学开玩笑地说，忍不住想让蚊子多咬我几次，那样就能“常咬常香”了。

昨天在校园网上看到了下面这条通知：

关于禁止学生在宿舍内做网络代理的通知
我校的校园宽带网是由联通公司投入大量资金建设而成，运行5年来，为学校的学科建设、教学、科研、管理、对内对外宣传等各项工作和师生的日常生活提供了较好的服务，发挥了巨大的信息交流与传递作用，全校师生员工应按照校园网管理规定进行使用。但是，近期发现有部分学生私自在宿舍内做网络代理，自行吸纳用户，牟取私利，严重违反了校园网络管理规定，对我校网络规范化管理及使用造成极大损害。
为加强对网络的管理，学校决定从下周起对学生宿舍进行大规模检查，对私自做网络代理的学生一经发现，将严格按照《黑龙江大学学生管理规定》的有关条款严肃处理，并罚款1000元。学校鼓励广大学生对此类事件进行揭发检举，如情况属实，对举报人实行500元奖励。
学校希望各学院深入了解学生情况，及时掌握学生动向，在最短的时间内通知到每一位学生，做好学生的思想工作，坚决杜绝此类现象的发生。
黑龙江大学
2006年6月23日

看这篇公告写的，真是太有水平了。义正言辞、恩威并用、赏罚兼施、威逼利诱，一副“大义在我这边，学生们不仁不义，非但不乖乖给我交钱，还翻着花样折腾我‘吃巨资’搭建的校园网”的脸孔。但无论话怎么说、檄文如何写，总之一句话，“你把代理给我拆了”。
这里先不看学生们是否陈凯歌、廉通是否猴急。我们先来看一看黑龙江大学的网络情况：
黑龙江大学本部分A、B、C三个区域，网络中心在B区（A区和C区中间，可以参考上篇Blog中贴的卫星照片）。这里着重讲问题最为严重的C区。
C区的电话、网络全部由廉通垄断。外局的ADSL信号无法到达，学生在宿舍中打电话必须要使用廉通的电话卡。C区为四人宿舍，每间宿舍有两个网络接口，分别到达楼下值班室的机柜内连接HUB。所以学生上网就只有，也必须通过廉通的这条线进行虚拟拨号连接至校园网。
现在看看廉通的资费标准：
套餐A：每月80元/80小时（相当于1元/小时），超过80小时按照1.5元/小时计费。
套版B：1.5元/小时，按时间计费，消费满30小时赠送5小时。
套餐C：80元包月。但仅限于教师住宅区的用户，要求使用身份证和工作证办理帐号。
很明显的抢钱资费，廉通利用其在C区的垄断地位（在B区可以用电话线通过网通ADSL上网。廉通在C区的垄断已经经过了网通和电信的证实。我打电话给网通客服，询问是否可以在C区安装网通ADSL，对方直言不讳“C区被廉通给霸占了”），强破学生接受如此高额的、与网吧相同的资费标准（相对于电信/网通一般80元/包月）。普通学生一般只是在网上聊聊天、浏览一下网页，网络资源被闲置浪费，却要被迫承担昂贵的资费。于是，部分学生想出了数人分摊支付费用，设置代理服务器的方法。这种方式高效地利用了网络资源，并且由于分摊支付费用，降低了每个人所支付的费用，是非常好的办法。但是这样一来，就断了廉通的生财之道，所以廉通当然要猴急。这恐怕是廉通当初吃巨资建设校园网的时候没有想到的吧。
廉通抨击架设代理服务器行为的根本立足点为“牟取私利”，那么我们来分析一下学生们的“私利空间”到底有多少：
按照每月30天、每天6：00~23：00提供服务计算，每月要使用510小时的上网时间，其中480小时的上网时间可通过套餐A来实现（6*80小时），另外30小时通过套餐B来实现（由7名学生分别持自己的学生证至廉通营业厅办理7个帐号）。这样一来在网络费用方面每月成本约为525元（31天/月的月份为550元）。
此外还需计算电费所产生的成本。我们假设代理服务器的功率为350W，同样早6：00~晚11点开机，每月约用电178.5度。宿舍分配给每个宿舍每月20度电免费使用，超过部分要缴电费。假设这20度电中15度用于电灯、随身听、手机充电以及其他用途，那么每月实际需要支付电费的电量为173.5度，按照学校的电价0.45元/度计算为78.07元（31天/月的月份为80.75元）。
这样一来，除去电脑本身的折旧与损耗，每月的成本为603元左右（31天/月的月份为631元左右），按照30元/人来计算，至少要有21人参加代理计划才能收回成本，人数为22人的时候才能开始盈利。扣除了朋友、同学等因为义理人情无法实现收费的人，要做到保持21人的用户是异常困难的。这也是为什么学生搭建的代理服务器大多坚持不果两个月的原因。
依据学生代理用户提供的线索可以了解到，因为学生的代理服务器成本高、生命周期短，教师住宅区内的部分“住户”（教师住宅区内住着谁，不言自明）便举起了代理大旗，每月80元包月，只需吸纳5、6人便可盈利。与学生的代理服务器相比，其竞争力之强、成本之低一眼就能看出。而廉通此次“整治行动”——我们姑且先称之为“整治行动”——却把矛头对准学生宿舍，“决定从下周起对学生宿舍进行大规模检查”，可见其决策的错误与愚蠢。学生在这次事件中，不但受到廉通的剥削，还要受到校方的检查，是双重的受害者。
我在此呼吁，廉通——你不要在错误的道路上越走越远，悬崖勒马，回头是岸，一个企业若只看到眼前小利，不惜作恶来赚取“短钱”，那这个企业终究会在市场竞争中彻底失败。试想——若没有黑大在背后给你撑腰，而与网通、电信进行竞争，你在黑大还活得到今天吗！

哈尔滨连续两个星期的阴雨天气中与结束了，今天迎来了阳光明媚的一天。
不过对于我这个在阴天中泡了两个星期的人来说，突然来这么“过于明媚”的一天，一出门还真有点不适应——阳光太刺眼了。
总体来说，哈尔滨的初夏还是相当凉快的，尤其是刚刚过去的两个星期的阴雨天气，气温总维持在20度上下，凉风吹过来，根本没有夏天的感觉。盖着毛巾被睡觉，到了早晨甚至会被冻醒。相比起来，老妈那边就要难受多了。在短信里，老妈经常抱怨天气闷热、稍微一活动就要出汗等等的，真是够呛。
突然想起来了今年高考的表妹，她报了成都的一所大学。那里的夏天……啊，天哪……不敢想象。