1.3 代数多重网格方法的实现

1.3.1 应用代数多重网格方法的预备过程

代数多重网格方法在计算粗网格时，会根据矩阵的实际情况构造一系列的粗网格分量，网格密度会根据矩阵中参数的各个元素实际情况变化。所以要将代数多重网格方法的粗网格提取过程应用到图像处理中，须建立多重网格所需要的系数矩阵。

借鉴Normalized-Cut方法，将图像转化为图，根据元素的像素灰度值关系建立图 G （ V ， E ）， V 为图像的像素点， E 为图像的像素点的相似度。那么就可以构建图像的亲和力（affinity）矩阵。若一幅图像的尺寸为 M × N ，那么将图像中的像素按照从左到右单行排列并作为相似度矩阵的行序列和列向量，相似度可以由相似度函数计算得来，那么亲和力矩阵行列均为 M × N ，元素个数为（ M × N ） ² 。

像素间的相似度可利用权函数来计算，常见的权函数有

其中， F _i ， F _j 为灰度图像中像素点 i ， j 的灰度值； x _i 为像素点的空间坐标； _l σ 为图像灰度值高斯函数的标准差； σ _x 为图像空间位置函数的标准差； r 是两节点的有效距离。那么由公式（1.12）可以看出，两节点距离越近，像素灰度值越接近，则相似度就越大。所以这个权函数既考虑了图像的像素关系，也兼顾图像的空间位置关系。

实验中使用的源图像如图1.11所示。

1.3.2 图像粗网格序列的提取

为了将代数多重网格方法运用到图像处理中，且要提取图像粗化序列，可以将图像的灰度矩阵作为基本数据，在这个基础上进行一系列的粗化。考虑到代数多重网格方法提取的粗网格序列的大小不是均匀变化的而且点数也没有一定的规律性，所以需要做以下几项工作：

（1）相邻的两级粗化图像像素点的对应关系；

（2）粗化图像序列与原始图像的像素点位置对应关系；

（3）粗化图像序列的显示。

考虑到图像的初始网格是等密度的，但在后续粗化网格中是不规律变化的。一幅图像可以用一个 m × n 的矩阵表示，可以构建亲和力矩阵 M ，因为代数多重网格方法可以直接作用于矩阵，那么运用代数多重网格方法也可以得到图像的粗网格序列。但是图像的显示应该是一个 m × n 的矩阵，而代数多重网格方法提取的粗网格序列是一系列的不规则的稀疏矩阵，故需要将这些不规则的粗网格序列还原成图像需要的矩阵格式。

在AMG图像重构中，采用python语言的pyamg包来实现AMG算法，可以得到粗化后的第1、第2、第3层数据，对应于原始图像中部分像素点，可采用多种插值函数插值，如最近邻法、线性插值法等，可以得到重构图像，详细步骤如下。

（1）得到网格序列。计算亲和力矩阵 M ，进行AMG粗化得到 N 层粗化网格 ₁ Ω ， ₂ Ω ，…， Ω _N 。

（2）扩充网格。将 N 层网格 ₁ Ω ， Ω ₂ ，…， Ω _N 还原成原始图像大小的 ，网格中的元素被选中为下一层粗网格，对应的元素值为1，否则为0。

（3）网格与图像对应。粗网格 与原始图像 I 很容易找到对应位置关系，采取如下策略：

① 如果网格 中的数据是1，则令对应位置的像素为图像相应位置的灰度值；

② 如果网格 中的数据是0，则令对应位置的像素等于0。

这样就产生了一系列图像 I ₁ ， I ₂ ，…， I _N 。本算法中使用的一些原始图片如图 1.11所示。利用代数多重网格得到的多层网格分别如图 1.12和图1.13所示。图1.13（c）是对图1.13（b）中的图进行局部放大，可以看到，局部放大的效果能把钟盘的数字较为清晰地反映出来。

1.3.3 粗网格序列的插值

在1.3.2节中，可以得到图像的一系列粗网格序列，这些图像系列随着像素点数的减少，对源图像的信息量保留也是逐渐降低的，但保留的是源图像的信息量较大的像素点。本节将对这些粗网格序列图像进行插值，即得到各层的重构图像。代数多重网格能够提取较为丰富的轮廓信息，因此利用轮廓信息进行图像的重建能够较好地逼近原始图像，保持原始图像的结构。对代数多重网格方法得到的粗网格数据进行分析，粗网格中会保留强连接部分而去掉弱连接部分，将这种机制应用到图像处理，可以发现代数多重粗化的网格可以提供较为丰富的轮廓信息。在代数多重网格方法粗化的各层数据中，粗网格数据具有图像的轮廓，变化剧烈的细节部分点分布聚集，平滑模糊部分点分布较稀疏均匀。在计算粗网格时，网格密度会根据图像中的变化情况而改变。初始化时原始图层网格是等密度的，但在粗网格中，图像灰度变化平滑区区域，网格密度较为稀疏且较规则，而当灰度变化急剧时，网格密度则很稠密且不规则，这种现象在一定程度上反映了代数多重网格方法中自适应网格的作用。根据这种特性，在粗网格上插值进行图像的重构，因粗网格较好地保持了图像的结构，理论上可以得到较好的重构结果。但是考虑到代数多重网格的网格序列的点集合是按照网格的代数信息（这里可以认为是图像的灰度信息）选取粗网格点的，粗网格的点是不规则的，所以应该将每层网格中的点对应到原始图像中的相应位置，这样才能得到较好的插值效果。插值效果的衡量采用的是均方误差（Mean Square Error），定义为

图1.14是利用多层网格进行插值得到的重建效果。它是对barb图利用第一到第四层粗网格数据进行插值的结果，说明代数多重网格方法对于纹理图片也能较为准确地反映出来。图1.15是使用不同插值方法得到的结果，第一行是使用线性插值方法得到的结果，第二行是使用cubic方法得到的插值结果。

比较粗化序列图像可以发现：粗化序列图像点密度分布均匀规则的地方，对应位置的源图像的灰度变化平缓；而粗化序列图像点分布不均匀的地方，源图像对应位置的灰度变化较剧烈。这个现象说明粗化序列一定程度上保持了图像轮廓特征，这种现象在一定程度上反映了代数多重网格方法中自适应网格的特性。通过对图像粗化序列信息量的比较，发现与网格提取的点数所占比例都小于图像的信息量，说明图像粗化序列能够较好地选择信息较丰富的像素点。

进一步考虑代数多重网格重建方法的效果，这里将其与小波重建算法做比较。对比图1.11中的face、fingerprint、meningg图片，分别对三幅图片做小波图像重建和代数多重网格方法重建，结果如表1.1所示，比较结果用MSE表示。

从表1.1中可以看出，针对一些简单的结构，如meningg，通过第三层粗网格都能得到较为精确的重建。针对比较复杂的结构，如图1.15所示，在第一层中能够得到较好的重建结果，说明代数多重网格方法对于纹理结构的提取也是比较有效的，由重构结果可以看出代数多重网格的重构结果比小波重构效果好。 empSh9hYiQBaMz5kvz8/50nn6NaZzuCjWRhDD4GAQCHJ0izpowVBvcMunpF8Zfb2