1.3 图像处理算法及其数据结构
从计算机技术的数据结构这一概念来看，基本的数据结构包括记录结构、数组结构和集合结构。在图像处理中，许多成熟的算法都具有显式或隐式所包含的数据形式，这种数据形式，可能是独立的单个数据，也可能是相邻的多个数据；独立的单个数据经过数据组织，也可以形成相邻的多个数据。所以，图像处理算法所包含的数据形式，一定能够以相邻的多个数据的形式来表示。算法的这种相邻的多个数据形式，就是数据的一个集合，称为图像邻域数据，简称为邻域数据。邻域数据包括水平方向的一维图像邻域数据、垂直方向的一维图像邻域数据和二维图像邻域数据。图像邻域数据的特点在于图像像素之间的相邻性。
显然，不了解施加于数据之上的算法就无法决定如何构造数据，即只有准确地了解算法，才能合理地组织算法所需要的数据；反之，算法的结构和选择却在很大程度上依赖于作为基础的数据结构，即数据结构将影响算法的实施。实现图像处理算法和图像处理系统之间的统一不仅要了解具体的应用要求、了解需要解决的具体问题，还有赖于对图像数据的认识。同时，要实现算法与系统实现的统一，也要对图像处理算法的数据结构有一个清楚的认识。
图像处理有静态与动态的、黑白与彩色的、二维与三维的、频域与时域的等，图像处理的算法也很多，而且各不相同。就图像数据而言，其数据具有数据量大、规律性强、邻域性强、相关性强、视频图像数据传输速率高等特点。这些特点，不仅强烈地表现在视频图像的数据中，也或多或少地表现在遥感、超声、CT等图像数据中。对图像数据进行处理，必然会遇到存储容量大、运算量大、实时应用困难等一系列问题，例如，对于512×512×8bit的黑白图像，其一幅图像的存储容量为256KB，实时数据传输速率为14.625MB/s（针对采样频率为14.625MHz的图像处理系统）。同理，对于512×512×24bit的真彩色图像，一幅图像的存储容量为768KB，实时数据传输速率为43.875MB/s（针对采样频率为14.625MHz的图像处理系统）。如果针对当前出现的高清晰度电视的活动图像，那么在数据量、数据传输速率、运算量方面都会有大幅度的提高。视频图像数据量大的特点在实际应用中表现得尤为突出，常常成为图像处理的难点。
图像数据具有的规律性是由图像的形成规律决定的，这种规律主要是指电视的扫描规律，具体来讲，在水平方向是按从左到右扫描规律进行，而在垂直方向是按从上到下且隔行扫描规律进行的，奇数场扫描行的顺序为1，3，5，7，9，…，偶数场扫描行的顺序为2，4，6，8，10，…，奇数场图像和偶数场图像合为一帧完整的图像。这种视频图像在水平方向上是连续的，在垂直方向是离散的。视频图像数字化所形成的数据流具有行方向数据流的突出特点，这也是许多图像硬件处理系统在处理图像时所使用的数据流形式。这种规律性，也常常影响着软件编程人员，致使在编程时，也采用从左到右、从上到下的数据组织形式。
数据相关性强体现在帧内和帧间的相关性上，这种相关性是由图像内容本身和视频图像扫描方式决定的，这既是许多图像压缩算法的基础，也是动目标检测、相关跟踪算法的基础。
1.3.1 数据处理层算法及其数据结构
数据处理层算法的共同特点是处理前和处理后依然是图像，即属于点位图到点位图的处理。除了图像的放大或缩小算法以外，数据处理层中的点处理和邻域处理在图像区域上没有发生变化，帧内的数据处理层算法是这样，帧间的数据处理层算法也是这样。在数据处理层中，主要实施点处理和邻域处理算法，这两类算法对数据的要求是不同的。数据处理层的点处理算法所要求的数据可以是一幅图像的单点，也可以是多幅图像（或一幅彩色图像中的R、G、B基色通道）相同地址的单点；而数据处理层的邻域处理算法所要求的数据可以是一幅图像单点的一个邻域，也可以是多幅图像（或一幅彩色图像中的R、G、B基色通道）相同地址的单点的一个邻域。
1.3.1.1 点处理算法及其数据结构
点处理算法主要有两类：帧内点处理算法和帧间点处理算法。帧内点处理算法包括一帧灰度图像的点处理和一帧彩色图像的多分量点处理，如R、G、B分量或Y、U、V分量的点处理。同理，帧间点处理算法也包括多帧灰度图像的点处理和多帧彩色图像的多分量点处理。
下面给出一些点处理算法。
1．灰度图像的求反
灰度图像的求反主要用于照片的两种输入方式，即正片和负片，常用的表达式为
式中，f（x, y）为原始图像；g（x, y）为求反后的输出图像；f（x, y）、g（x, y）均为8bit灰度图像。
2．图像单阈值分割
图像单阈值分割常用来进行图像二值化处理，其表达式为
式中，T0为阈值；f（x, y）为原始图像；g（x, y）为二值化后的输出图像。
3．两帧图像的相减运算
两帧图像的相减运算可以用于医学图像的减影、监控中的动目标检测，其表达式为
式中，f1（x, y）为一帧图像或是当前帧的图像；f2（x, y）为另一帧图像或是当前帧的后续一帧图像；g（x, y）为相减后的输出图像。
1.3.1.2 邻域处理算法及其数据结构
按照被处理的图像数据是否被重复使用，图像处理中的邻域处理算法可分为两类，一类算法是重复使用图像数据的，大多数邻域图像处理算法属于这一类算法。当然，这里的重复并非指完全的重复，而是局部重复，例如Roberts算子，所要求的是2×2的数据结构，假定当前处理某一点使用了该点相邻的4点数据，则下一点的处理一定会重复使用当前使用过的4个数据中的2个数据。另一类算法是不重复使用图像数据的，只有比较少的邻域图像处理算法属于这一类算法，如8×8的JPEG算法。当然，以数据块进行的并行点处理也可以归入不重复使用图像数据的邻域处理的形式。点处理有帧间处理的情况，而邻域图像处理则很少有帧间处理（除了块的点处理以外），因此，邻域图像处理基本上属于帧内处理。下面给出一些邻域处理算法。
1．Roberts算子
Roberts算子用于边缘增强，绝对值输出的Roberts算子数学表达式为
式中，f（x, y）为原始图像；G（x, y）为图像f（x, y）在（x, y）点的梯度。
在图像处理中，常常要对式（1.3.4）的G（x, y）进行二值化处理。
Roberts算子的数据结构如图1.3.1所示，显然这是一个2×2的数据结构。
图1.3.1 2×2数据结构
2．3×3卷积
3×3卷积的表达式为
式中，H（j，i）为卷积模板，也称为卷积核，其数据结构如图1.3.2所示。3×3卷积的图像数据结构如图1.3.3所示，这是一个3×3的数据结构。
图1.3.2 3×3卷积模板
图1.3.3 3×3数据结构
3．Sobel算子
Sobel算子用于边缘增强，该算子是测量沿两个垂直方向的灰度差，然后再把这些测量值组合起来形成边缘强度。如像素处理所得到的响应分别为Gx（x, y）、Gy（x, y），则
和图1.3.2中的3×3卷积模板的表示方法类似，式中x方向的卷积模板和y方向的卷积模板分别如图1.3.4和图1.3.5所示。
图1.3.4 x方向的卷积模板
图1.3.5 y方向的卷积模板
平方根输出的Sobel算子数学表达式为
绝对值输出的Sobel算子数学表达式为
Sobel算子的数据结构也是3×3的数据结构。
4．3×3十字中值滤波
3×3十字中值滤波有多种形式，最常使用的3×3十字中值滤波是对5个相邻像素进行排序，以确定中心点的数值。其数据组织如图1.3.6所示。十字中值滤波的数学表达式如下：
图1.3.6 3×3十字中值滤波数据结构
在3×3邻域四方向中值滤波的数据结构如图1.3.7所示，数学表达式为式（1.3.11）。
图1.3.7 3×3四方向中值滤波的数据结构
式中，
G1(x, y)=med[g(x-1, y), g(x, y), g(x+1, y)]
G2(x, y)=med[g(x-1, y-1), g(x, y), g(x+1, y+1)]
G3(x, y)=med[g(x, y-1), g(x, y), g(x, y+1)]
G4(x, y)=med[g(x+1, y-1), g(x, y), g（x-1，y+1）]
不论是重复使用图像数据的邻域处理算法还是不重复使用图像数据的邻域处理算法，其算法要求的整个邻域数据，均称为并行的邻域处理算法的数据结构，如Roberts算子的2×2数据结构、Sobel算子的3×3数据结构，JPEG静图像压缩的8×8数据结构等。常用的邻域处理算法的并行数据结构如图1.3.8所示。
图1.3.8 常用的邻域处理算法的并行数据结构
1.3.2 信息提取层算法及其数据结构
信息提取层算法的共同特点是处理的对象是图像，处理后的结果则是一些表征信息的数据，这种信息可以是某类结构，如构成物体的边缘、形状或纹理，也可以是图像的统计特性。信息提取层算法属于点位图到信息数据的处理，其处理获得的数据量小于被处理的点位图的数据量。下面给出一些信息提取层的算法。
1．直方图统计
直方图统计算法提供的是被统计区域的灰度分布情况，其数学表达式为
式中，Gk为图像f（x, y）的第k个灰度值；nk为f（x, y）中灰度值为Gk的图像像素的个数；m为图像f（x, y）的像素的总数量；L为f（x, y）图像分解力的灰度级的级数，如8bit的图像分解力，L的值为256。
直方图统计对图像像素进行统计计算，得到L个表示图像灰度分布的具体数据。
2．x轴、y轴投影直方图
x轴投影直方图统计的是一幅W×H的图像在x轴上的灰度积分，其数学表达式为
y轴投影直方图统计的是统计一幅W×H的图像在y轴上的灰度积分，其数学表达式为
以上所述的信息提取层算法既具有点位图的单点数据特点，也具有点位图的邻域数据特点，这样，也就具有点处理算法的数据结构和邻域处理算法的数据结构。由于信息提取层处理的结果是一些信息数据，因此在用硬件进行信息提取层处理的系统里，常常把这些信息数据存储在单独设置的SRAM存储器中，再转存储在计算机内。
1.3.3 知识应用层算法及其数据结构
知识应用层算法的共同特点是处理的对象是一些信息数据，利用知识进行处理，处理后的结果则是对图像的描述、理解、解释以及识别。这是数据对数据的处理，在处理中不依靠图像原始的点位图，而是依靠从原始图像中获得的某些信息。人脸识别是典型的知识应用层算法，我们将在后续章节中加以论述。
图1.3.9给出了用奇偶性检测的方法来确定区域内部的示意图。在本书的第11章，则给出了用奇偶性检测的方法确定区域内部的进一步描述。
图1.3.9 用奇偶性检测确定区域内部
如图1.3.9所示，在一个单连通域的外轮廓图中，I行水平线与外轮廓图相交，分别有4个边界点A、B、C、D，按x坐标排序，奇数点是边界的起点，偶数点为边界的终点，两两一对。在I行的A、B之间和C、D之间，是区域的内部。同理，第N行的E、F之间和G、H之间也是区域的内部。
描述一个单连通域的外轮廓，可以用外轮廓点的坐标值，还可以用链码值来描述。用链码有很多好处，不仅降低了码位的长度，还便于多种计算。我们采用链码值的定义如图1.3.10所示。
图1.3.10 链码值定义
1．周长
采用图1.3.10所示的链码值定义来计算图1.3.9所示区域轮廓线的长度。则闭合区间的周长L为
式中，N为边界点的点数。
式中，Mk为第k点的链码值。
2．面积
可用不同方法来计算闭合区间的面积。一种方法是利用图像分割的方法把该区间置为某一灰度值，再统计这一灰度值像素个数，这种方法要求区间内的灰度具有一致性；另一种方法是利用链码来计算闭合区间的面积，其做法是采用类似计算图1.3.9所示的区域内部的方法，从ymin到ymax计算每一行属于该区间面积，然后再求和，计算公式如下：
在I行里的边界点按x坐标从小到大排序，共有N个边界点，则
下面介绍另一种利用链码计算面积的简便方法。
用链码序列表示闭合区间且采用图1.3.10所示的链码值定义，表1.3.1给出了在这些条件下的面积因子dnx、dny和链码值M的对应值。
表1.3.1 面积因子dnx、dny和链码值M的对应值
闭合区间的像素面积为S，则
式中，dnx、dny为面积因子；yn-1为第n-1个边界点的y坐标。
3．重心
一个任意形状的封闭区域的重心，我们可以认为是一个均匀刚体的质心。其质心的坐标为（x0，y0），则
式中，My为该均匀刚体对y轴的力矩；Mx为该均匀刚体对x轴的力矩。计算力矩的方法是采用类似计算图1.3.9所示的区域内部的方法，按照行来切片，从ymin到ymax，计算每一行中属于该区域的对x轴的力矩，然后再求和，计算公式如下：
在I行里的边界点按x坐标从小到大排序，该行共有N个边界点，则
面积的计算仍按式（1.3.17）、式（1.3.18）计算，这样可以求出y0的数值。
计算My力矩的方法和计算Mx力矩的方法类似，这时按照列来切片，从xmin到xmax，计算每一行中属于该区域的对y轴的力矩，然后再求和，计算公式如下：
在J列里的边界点按y坐标从小到大排序，该列共有N个边界点，则
面积的计算仍按式（1.3.17）、式（1.3.18）计算，这样可以求出x0的数值。