什么是区域邻接图介绍

区域邻接图是拓扑数据结构中的一个典型，其中，结点对应于区域，相邻的区域用弧线连接起来。分割的图像由具有相似的性质（亮度、纹理、彩色......）的区域构成，这些区域对应着场景中的一些实体，当区域之间具有一些共同边界时，相邻关系就成立了。

区域邻接图定义

拓扑数据结构将图像描述为一组元素及其相互关系，这些关系通常用图结构来表示。图(Graph)

，是一个代数结构，由一组结点

和一组弧

构成。每条弧

代表一对无次序的节点

，结点不必由区别。结点的度数等于该结点所具有的弧数。

区域邻接图是这一类数据结构的一个典型，其中，结点对应于区域，相邻的区域用弧线连接起来。分割的图像由具有相似的性质（亮度、纹理、彩色......）的区域构成，这些区域对应着场景中的一些实体，当区域之间具有一些共同边界时，相邻关系就成立了。

图1给出了一个区域邻接图例子，其中图像中的区域用数字标识，标识0代表着图像外的像素。在区域邻接图中，这个数值用来指出与图像边界接触的区域。

区域邻接图特点

区域邻接图具有一些吸引人的特征。如果一个区域包围其他区域，那么，对应于内部区域的那部分图就可以被图的割分离出来，度数为1的结点表示简单的孔。

区域邻接图的弧可以包括相邻区域之间关系的一个描述，常见的关系有“在左侧”或“在内部”。在识别任务中区域邻接图可用于与存储的模式进行匹配。

区域邻接图通常是从区域图创建的，区域图是和原始图像矩阵相同维数的矩阵，其元素是区域的识别标号。为了创建区域邻接图，图中所有的区域边界都要跟踪出来，所有的相邻区域的标号都要记录下来，也可从四叉树表示的图像中创建区域邻接图。

区域邻接图明确地存储了图中所有区域的相邻信息。区域图中也含有这样的信息，但从中得到它却要困难得多。如果想快速地将区域邻接图和区域图关联起来，只要将区域邻接图中的结点，用区域的标识号和某个代表像素（例如，区域左上角的像素）标注起来，就足够了。

区域邻接图形成过程

区域邻接图（RAG）的形成过程如下：

①对标号图像上的每一个标号，在区域邻接图建立一个对应的节点，标记为

②顺序扫描标号影像，并在每一个像素角标

完成下列各步

③令Label1=Label1 ( i 为行号，j 为列号)

④先后查看像素 的右邻接像素 和下邻接像素 ，令Label2 分别等于 Label和Label，若 Label1≠Label2，查看对RAG的节点

和

之间是否已经建立了连接，如果没有，则增加一条弧线，以建立连接；

⑤回到步骤

②继续循环执行，直到遍历完毕。

区域邻接图应用示例

在区域边缘立体匹配方面：

通过图像分割提取的轮廓边缘属于区域边界，常规的匹配思路是以两两区域之间的边界线为单位，将闭合的区域边界按分段边缘的数据结构形式进行匹配。而由于不同视点的成像差异会使左右图像分割区域通常并不严格对应，区域之间的边界线也很难一一对应，往往是左图像中一条边缘的一部分和右图像中一条边缘的其中一部分对应，出现交叉对应的复杂情况。若以分段边缘线为匹配基元，在一定程度上会造成部分边缘的丢失，而对过多的边缘线进行匹配也相对更为耗时。

由于边界具有同时属于相邻的两个区域的特点，区域边缘能够反映图像中各分割区域的相互连接状况，反之也能根据区域的邻接关系来指导边缘匹配，以确定合适的匹配顺序。图像分割区域的邻接关系通常采用区域邻接图(Region Adjacency Graph, RAG)的数据结构形式进行描述。