TheCodeWay:我的博客

步骤五：哈弗曼编码

---

        JPEG压缩的最后一步是对数据进行哈弗曼编码(Huffman coding)，哈弗曼几乎是所有压缩算法的基础，它的基本原理是根据数据中元素的使用频率，调整元素的编码长度，以得到更高的压缩比。
        举个例子，比如下面这段数据

        这段数据里面包含了33个字符，每种字符出现的次数统计如下

        如果我们用我们常见的定长编码，每个字符都是3个bit。

        那么这段文字共需要3*33 = 99个bit来保存，但如果我们根据字符出现的概率，使用如下的编码

        那么这段文字共需要3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63个bit来保存，压缩比为63%，哈弗曼编码一般都是使用二叉树来生成的，这样得到的编码符合前缀规则，也就是较短的编码不能够是较长编码的前缀，比如上面这个编码，就是由下面的这颗二叉树生成的。

        我们回到JPEG压缩上，回顾上一节的内容，经过数据量化，我们现在要处理的数据是一串一维数组，举例如下：
Continue reading “JPEG算法解密（四）” →

步骤四：数据量化

---

        经过上一节介绍的离散余弦变换，图像数据虽然已经面目全非，但仍然是处于“可逆”的状态，也就是说我们还没有进入“有损”的那一步。这次我们来玩真的，看一下数据中的细节是如何被滤去的。先来考察一下要对付的问题是什么，经过颜色空间转换和离散余弦变换，每一个8X8的图像块都变成了三个8X8的浮点数矩阵，分别表示Y,Cr,Cb数据，比如以其中某个亮度数据矩阵举例，它的数据如下

        我们的问题是，在可以损失一部分精度的情况下，如何用更少的空间存储这些浮点数？答案是使用量子化（Quantization），简称量化。“量子”这个概念来自于物理学，意思是说连续的能量可以看做是一个个单元体的组合，看起来高端大气，其实很简单，比如游戏中在处理角色面朝方向时，一般并不是使用0到2π这样的浮点数，而是把方向分成16个区间，用0到16这样的整数来表示，这样只用4个bit就足够了。JPEG提供的量子化算法如下：

	(3.1)

        其中G是我们需要处理的图像矩阵，Q称作量化系数矩阵（Quantization matrices），JPEG算法提供了两张标准的量化系数矩阵，分别用于处理亮度数据Y和色差数据Cr以及Cb。

Continue reading “JPEG算法解密（三）” →

步骤三：离散余弦变换

---

        这次我们来介绍JPEG算法中的核心内容，离散余弦变换（Discrete cosine transform），简称DCT。
        离散余弦变换属于傅里叶变换的另外一种形式，没错，就是大名鼎鼎的傅里叶变换。傅里叶是法国著名的数学家和物理学家，1807年，39岁的傅里叶在他的一篇论文里提出了一个想法，他认为任何周期性的函数，都可以分解为为一系列的三角函数的组合，这个想法一开始并没有得到当时科学界的承认，比如当时著名的数学家拉格朗日提出质疑，三角函数无论如何组合，都无法表达带有“尖角”的函数，一直到1822年拉格朗日死后，傅里叶的想法才正式在他的著作《热的解析理论》一书中正式发表。
        金子总会闪光，傅里叶变换如今广泛应用于数学、物理、信号处理等等领域，变换除了它在数学上的意义外，还有其哲学上的伟大意义，那就是，世上任何复杂的事物，都可以分解为简单的事物的组合，而这个过程只需要借助数学工具就可以了。但是当年拉格朗日的质疑是正确的，三角函数的确无法表达出尖角形状的函数，不过只要三角函数足够多，可以无限逼近最终结果。比如下面这张动图，就动态描述了一个矩形方波，是如何做傅里叶分析的。

        当我们要处理的不再是函数，而是一堆离散的数据时，并且这些数据是对称的话，那么傅里叶变化出来的函数只含有余弦项，这种变换称为离散余弦变换。举个例子，有一组一维数据[x₀,x₁,x₂,…,x_n-1],那么可以通过DCT变换得到n个变换级数F_i

	(2.1)

        此时原始数据X_i可以通过离散余弦变换变化的逆变换（IDCT)表达出来

	(2.2)

        也就是说，经过DCT变换，可以把一个数组分解成数个数组的和，如果我们数组视为一个一维矩阵，那么可以把结果看做是一系列矩阵的和

	(2.3)

Continue reading “JPEG算法解密（二）” →

        图片压缩有多重要，可能很多人可能并没有一个直观上的认识，举个例子，一张800X800大小的普通图片，如果未经压缩，大概在1.7MB左右，这个体积如果存放文本文件的话足够保存一部92万字的鸿篇巨著《红楼梦》，现如今互联网上绝大部分图片都使用了JPEG压缩技术，也就是大家使用的jpg文件，通常JPEG文件相对于原始图像,能够得到1/8的压缩比，如此高的压缩率是如何做到的呢？
        JPEG能够获得如此高的压缩比是因为使用了有损压缩技术，所谓有损压缩，就是把原始数据中不重要的部分去掉，以便可以用更小的体积保存，这个原理其实很常见，比如485194.200000000001这个数，如果我们用485194.2来保存，就是一种“有损”的保存方法，因为小数点后面的那个“0.000000000001”属于不重要的部分，所以可以被忽略掉。JPEG整个压缩过程基本上也是遵循这个步骤：
        1. 把数据分为“重要部分”和“不重要部分”
        2. 滤掉不重要的部分
        3. 保存

步骤一：图像分割

---

        JPEG算法的第一步，图像被分割成大小为8X8的小块，这些小块在整个压缩过程中都是单独被处理的。后面我们会以一张非常经典的图为例，这张图片名字叫做Lenna，据说是世界上第一张JPG图片，这张图片自从诞生之日开始，就和图像处理结下渊源，陪伴了无数理工宅男度过了的一个个不眠之夜，可谓功勋卓著，感兴趣的朋友可以在这里了解到这张图片的故事。

步骤二：颜色空间转换RGB->YC_bC_r

---

        所谓“颜色空间”，是指表达颜色的数学模型，比如我们常见的“RGB”模型，就是把颜色分解成红绿蓝三种分量，这样一张图片就可以分解成三张灰度图，数学表达上，每一个8X8的图案，可以表达成三个8X8的矩阵，其中的数值的范围一般在[0,255]之间。
Continue reading “JPEG算法解密（一）” →

      3月28号是牛顿的忌日，但是知道的人很少，我们毕竟更关心沈殿霞和张国荣。其实牛顿老师在科学圈里曾经很有权势，被女王封了爵位成了贵族，人称牛爵爷，官至皇家造币局局长兼皇家学会会长。如果阿尔伯特没有辞了以色列总统的话和他有一拼。
      说他有权势并不仅是官大，主要还是贡献大。如果17世纪就有诺贝尔奖的话，牛顿老师至少能连续垄断4届物理学奖（分光计；力学体系的构建；反射望远镜；万有引力），同时为了表彰他在炼金方面的造诣，再奉送他一届化学奖。而且这孙子鼓捣出了流数术，所以菲尔兹数学奖也要给他。要知道，他的这些发现基本都是在26岁以前获得的，30岁以后牛顿就开始玩票了，成天琢磨上帝和炼金，以及怎样把莱布尼茨搞臭，捎带手的把以前的发现整理成书。所以你能想象到他在当时的欧洲是如何的一呼万应，敢跟他叫板的只有莱布尼茨和大主教贝克莱。牛老师死的时候，全英国的贵族以给他扶柩为荣，全欧洲的名流蜂拥伦敦。来自法国的傻逼文科生伏尔泰在国葬现场大受刺激，回去就写了首诗，嫉妒之情溢于言表。
      牛顿老师的一生是天才的一生，战斗的一生，也是孤独的一生。一辈子没有朋友，也没有结过婚，很可能到死都是处男，关于牛顿是否处男的问题，由于篇幅过长，我将在另一篇文中论证。当然他肯定不会孤独，因为科学的世界里乐趣无限，快感连连。出乎世俗想象的是，科学其实远比任何娘们儿都风骚，玩科学比玩女人爽得多，得到一个成果所获得的高潮强烈而持久，不仅有快感，更有巨大的自我认同感，远胜于那几秒寒颤之后无边的空虚与落寞。所以陈景润其实是沉溺于美色不能自拔，身体弱架不住高潮过度被爽死了。
Continue reading “【转载】牛顿逼的一生” →

        所谓表面张力，正如前面所讲，就是由于流体“试图减小表面积”而产生的力，这种力产生的效果非常有趣，它会使肥皂膜紧绷，使水滴变成球形，但在大部分SPH应用场合中，和其他力相比，表面张力产生的效果其实是微乎其微的，所以常常忽律表面张力的计算。
        如果要想计算表面张力，就要考虑它的特殊性质，首先只有位于流体表面的粒子才会受到表面张力的影响，所以第一个问题就是如何找到那些处于“表面”的粒子。
        首先构造这么一个标量场，在有流体粒子的位置都染上一个“颜色值”1，其他位置的”颜色值”都是0，针对二维情况说明，这就好像构造了类似于一个“高度图”的标量场。

        根据光滑核原理，流体内任意一点r所在位置的“颜色”值为

	(5.1)

        对这个标量场做哈密顿运算，回想一下我们以前提到的梯度的概念，所得到的梯度场∇c_s可以给我们两个信息，第一，由于梯度反应的是标量场中“变化的程度”，所以只有在流体的边界部分才会有比较大的梯度值，而内部的梯度值几乎为0，根据这个特性可以用来判断粒子是否处于表面，第二，梯度场的方向指向大值部分，也就是流体的内部，而这正是表面张力的方向。
Continue reading “SPH算法简介（五）：表面张力的计算” →

        上几节，我们推导出一大推复杂无比的公式，似乎有点纸上谈兵，这节来点真的，写一个可以运行的SPH系统，下面就是SPH基本的运算流程

1. 初始化粒子，为每个粒子赋上初始位置
2. 根据公式3.7计算每个粒子的密度
3. 根据公式3.10计算每个粒子的压强
4. 根据公式3.18计算每个粒子的加速度
5. 根据临界条件调整加速度
6. 根据加速度计算每个粒子的速度变化
7. 根据速度计算粒子位置的变化
8. 绘制粒子
9. 回到步骤2

        下面有个简单的示例程序，运行效果如下

        这个程序基本上没有怎么考虑效率，只是让系统跑起来，所以比较适合拿来对照公式学习，按照惯例，放出源代码和可执行程序
        源码下载:fluid_source.zip(395KB)
        可执行程序下载: fluid.zip(120KB)
        SPH还有很多细节值得讨论，比如表面张力、并行计算、构建网格、真实材质的水渲染等，这些部分我会抽时间再写一些东西出来介绍。

        和其他流体力学中的数学方法类似，SPH算法同样涉及到“光滑核”的概念，可以这样理解这个概念，粒子的属性都会“扩散”到周围，并且随着距离的增加影响逐渐变小，这种随着距离而衰减的函数被称为“光滑核”函数，最大影响半径为“光滑核半径”。

        反过来不难理解，尽管我们将流体视为一个个分散的粒子，但流体毕竟是连续充满整个空间的，流体中每个位置参与运算的值都是由周围一组粒子累加起来的。

Continue reading “SPH算法简介（三）: 光滑核函数” →

        SPH算法的基本设想，就是将连续的流体想象成一个个相互作用的微粒，这些例子相互影响，共同形成了复杂的流体运动，对于每个单独的流体微粒，依旧遵循最基本的牛顿第二定律。
\begin{equation}
m\vec{a}=\vec{F}\tag{2.1}
\end{equation}        这是我们分析的基础，在SPH算法里，流体的质量是由流体单元的密度决定的，所以一般用密度代替质量
\begin{equation}
\rho\vec{a}=\vec{F}\tag{2.2}
\end{equation}        这里的的作用力F的量纲发生变化，正常情况下，“力”的量纲\(dim F=MT^{-2}L\)，而在这里\(dim F=MT^{-2}L^{-2}\)，后面的分析都是用这个量纲的“作用力”，这一点一定要注意。作用在一个微粒上的作用力由三部分组成
\begin{equation}
\vec{F}=\vec{F}^{external}+\vec{F}^{pressure}+\vec{F}^{viscosity}\tag{2.3}
\end{equation}        其中\(\vec{F}^{external}\ \)称为外部力，一般就是重力
\begin{equation}
\vec{F}^{external}=\rho\vec{g}\tag{2.4}
\end{equation} Continue reading “SPH算法简介（二）: 粒子受力分析” →

前言：这个系列是我很早以前写的，这次重新开博原本并不打算重新找回原来的文章，不过不断有朋友找找我要其中的源码和图片，好在这些还有备份，重新发出来以做纪念

        SPH(Smoothed Particle Hydrodynamics)算法是一种流体模拟算法，他的特点是简单快速，可以用在例如游戏这样的实时的交互软件中。SPH算法虽然简单，但要完全搞明白其中的原理和实现方法，也不是易事，写这个系列希望能全面介绍一下相关的内容，如果你搜索到这里，可以仔细看一下这个系列，希望能帮到你。
        烟雾、海浪、水滴…，这些司空见怪的自然现象其实有着非常复杂的数学规律，对于流体的研究，有两种完全不同的视角，分别是欧拉视角和拉格朗日视角。欧拉视角的坐标系是固定的，如同站在河边观察河水的流动一样，用这种视角分析流体需要建立网格单元，还会涉及到有限元等复杂的工程方法，一般用在离线的应用中。而拉格朗日视角则将流体视为流动的单元，例如将一片羽毛放入风中，那么羽毛的轨迹可以帮我们指示空气的流动规律。

        SPH算法是典型的拉格朗日视角，它的基本原理就是通过粒子模拟流体的运动规律，然后再转换成网格进行流体渲染。

		>		>

---

        在正式开始之前，需要把SPH算法涉及到的相关数学概念介绍一下，这些概念基本上都是大学数学中的内容，所以不用紧张，翻翻书就能想起来。
        

标量场和矢量场

        如果空间区域内一点M，都有一个确定的数量f(M)，则称这个空间区域内确定了一个标量场，如果空间区域内任意一点M，都有一个确定的向量F(M)，则称这空间区域内确定了一个矢量场。例如，液体中的密度，就是标量场，而速度，就是矢量场
Continue reading “SPH算法简介（一）: 数学基础” →