数字图像处理——图像压缩

形态学是生物的一个分支，用来研究动植物的形状和结构。而这里的形态学图像处理，指的是提取图片中关于形状结构的组成承认，比如边界，骨架以及凸包（convex hull）。

集合论的概念

关于形态学图像处理离不开集合的一些操作，因此在这里先说明写一下可能会用到的操作。

属于$\in$，不属于$notin$,子集$\subset$，并集$\cup$，交集$\cap$，空集$\emptyset$，补集$A^c$，两个集合的差：$A - B = A \cap B^c$。

集合的反射：$\hat B = \{w \vert w = -b, b \in B\}$；

集合的平移：$(A)_z = \{c\vert c = a + z , \text{for }a \in A\}$

二进制上的布尔操作规则如下：

形态学图像处理

转换不变（shift-invariance）

在二值图上的逻辑操作是形态学图像处理。转换不变定义如下：

我们可以看出来，转换不变也就是这个转换不会改变位置。需要注意的是，转换不变并不意味着是线性的。

SE（Structure Element）

结构元素用来探测一个图片，可以把他当成滤波器的窗口，mask等等，类似的东西。不过它的形状是可以任意的：

腐蚀（Erosion）

$A,B$是二维空间中的几何，而将A用B腐蚀定义为： $$A \ominus B = \{z \vert (B)_z \subset A\}$$ 这里的z是一个平移量，也就是如果$B$经过平移$z$之后还被$A$完全包含，那么所有这些平移量(z是平移量，这里指的应该是$A$在$z$处的值)就被定义为$A$被$B$腐蚀。这个操作可以让$A$变小一圈：

在二值图片上，它的表现就是，用一个SE要游动，SE中的值都是1，而如果SE与某一块的$A$取交集，全部得到1，那么该中心的值取1，否则取0。这个操作如下图：

上面这张图中，白色表示1，而黑色表示的是0。侵蚀会侵蚀掉所有的小方块，而对于比自己大的方块，它不会完全消失，而是会保留靠近中心位置的白色。因此通过侵蚀我们可以来去除图片中一些不想要的像素。不过侵蚀后得到小的方块又如何复原？这需要用到下一个操作：膨胀。

膨胀（dilation）

将A用B膨胀的定义如下： $$A \oplus B = \{ z \vert (\hat B)_z \ne \emptyset\}$$ 我们知道$\hat B$是反射，因此所有在$\hat B$上的平移，只要A与平移后的$\hat B$有重叠区域（腐蚀需要全部重叠，也就是A包含平移后的B），那么该平移就属于膨胀。

膨胀的效果如下：

膨胀操作是腐蚀操作的对偶操作： $$(A \ominus B)^c = A^c \oplus \hat B$$

从上图可以看出膨胀可以用来加粗字体，也使得一些断掉的地方连接起来了。下面是腐蚀和膨胀的对比：

侵蚀实际上就是背景的膨胀，但是要注意，膨胀不是侵蚀的逆，也就是你侵蚀然后膨胀，不一定得到原来的结果。

使用不同形状的SE也能得到不同的结果：

下面这张图，使用一个交叉形状的SE进行腐蚀操作，来定位这个网格在哪里断掉了：

开闭（Opening & Closing）

开闭操作实际上是侵蚀和膨胀的组合。Opening操作先腐蚀然后膨胀，一般来说可以用来平滑一个物体，如下图：

需要注意的是，这里使用了圆形的SE，而矩形的SE会得到不同的形状。Opening操作定义如下： $$A \circ B = (A \ominus B) \oplus B$$ Opening有下面几个性质:

• $A \circ B \subset A$
• $(A \circ B) \circ B = A \circ B$

Closing操作只是顺序与Opening不同： $$A \bullet B = (A \oplus B) \ominus B$$

它具有下面的性质：

• $A \subset (A \bullet B)$
• $(A \bullet B) \bullet B = A \bullet B$

Opening与Closing是对偶操作： $$(A \bullet B)^c = A^c \circ \hat B$$ 下面一张图展现了开闭操作的对比：

可以看到Opening可以使得细微的链接断裂，而Closing一般会填补更小的空洞缝隙等，他们都可以平滑对象。

下面这张图展示了Opening，closing操作在指纹上的应用：

边界提取

之前也介绍了一些边界提取的算法，主要使用的是滤波器。这次我们介绍形态学图像处理中如何对二值化的图像进行边界处理。

$\beta (A)$表示了一个集合$A$的边界，那么我们可以通过下面的操作来提取边界： $$\beta (A ) = A - (A \ominus B).$$ 这个道理很简单，就是用原来的图像减去了被腐蚀的图像，因为腐蚀一定会将边界腐蚀掉，下图是一个直观解释：

区域填充

区域填充可以用来一个边界，或者空洞。算法如下： $$X_k = (X_ {k-1} \oplus B) \cap A^c,k = 1,2,3,X_0 = p$$ 这里的p是待填充区域中的一个点，而B是一个对称的SE。这里与$A^c$求交集，保证了得到的点都在待处理的区域内部，而不会逃出边界。当$X_k =X_ {k-1}$时，算法停止，下面是这个算法的运行过程：

这个算法的运行原理也很简单，首先是膨胀一个待填充区域的点，膨胀之后将该点以及SE与原图像的补集做交集，实际上这样得到的就是接下来需要膨胀的点。一直这样操作，直到最终算法停止。下面是区域填充算法的效果：

骨架提取

对于姿势模拟，骨架提取是非常重要的。骨架$S(A)$定义如下：对于一个点$z$，定义$(D)_z$是最大的以$z$为中心的一个圆盘，并且被A完全包含。如果$(D)_z$接触了$A$的边界两个点以上，而且没有办法找到比$(D)_z$更大的圆盘（不局限于以z为中心），那么$(D)_z$被称为最大圆盘，而这个$z$正是骨架上的一点，所有的这样的$z$构成了骨架。

实际上骨架的定义直观来说很容易明白，但是努力用数学语言描述反而说得复杂了。下面是骨架的示意图：

骨架提取算法如下： $$S(A) = \bigcup_ {k=0}^K S_k(A)$$ 其中: $$ S_k(A) = (A \ominus k B) - (A \ominus kB) \circ B\\ (A \ominus kB) = (...((A \ominus B) \ominus B )...)\ominus B $$ 可以看到$(A \ominus kB)$也就是不断地对A进行腐蚀。而$K$被定义为将$A$腐蚀为空集的腐蚀次数： $$K = \max \{k \vert (A \ominus kB) \ne \emptyset \}.$$ 算法首先将$A$进行腐蚀，这是合理的，但是这样得到的并不一定是骨架，可能还是相对膨胀的，因此这里还加了减去开操作。开操作使用不同的SE可以得到不同的效果，但是平滑明显不是这里使用它的主要原因。腐蚀可能直接将细微的连接直接腐蚀了，而增加开操作可以除掉这些细微的连接，同时对于大片的区域会保存下来，因此用原图减去开操作可以比较好的保留下来这个细微的连接。每次都这样，首先尝试把物体变细，然后保存细微的连接，然后将这些连接取并集，就可以得到骨架。当然，这里的骨架提取是非常简单的，而且不一定会连续，实际上还有很多更高级的骨架提取算法，可以查阅相关的论文。

我们也可以通过骨架来尝试重建原来的图形，但是很大可能不会和原来一样了。重建算法如下： $$ A = \bigcup _ {k=0}^K (S_k(A) \oplus kB)\\ (S_k(A) \oplus kB) = (...((S_k(A) \oplus B) \oplus B) \oplus... )\oplus B $$ 因此，也就是一个不断膨胀的过程。下面是算法的简单示意图：

这里的形态学图像处理，目前看起来很基础，不知道有什么用，但是实际上简单的规则可以构成非常复杂庞大的系统。这里有一份关于形态学图像处理的补充材料，如果感兴趣可以阅读，看看形态学图像处理可以做那些神奇的事情：Supplementary Material。