區域鄰接圖

區域鄰接圖是拓撲數據結構中的一個典型，其中，結點對應於區域，相鄰的區域用弧線連線起來。分割的圖像由具有相似的性質（亮度、紋理、彩色......）的區域構成，這些區域對應著場景中的一些實體，當區域之間具有一些共同邊界時，相鄰關係就成立了。

基本介紹

• 中文名：區域鄰接圖
• 外文名：Region adjacency graph
• 是：一種拓撲數據結構
• 歸屬學科：數字圖像處理
• 特點：結點對應區域,用弧線連相鄰區域
• 套用領域：計算機視覺

定義

拓撲數據結構將圖像描述為一組元素及其相互關係，這些關係通常用圖結構來表示。圖(Graph) ，是一個代數結構，由一組結點 和一組弧 構成。每條弧 代表一對無次序的節點 ，結點不必由區別。結點的度數等於該結點所具有的弧數。

圖1

區域鄰接圖是這一類數據結構的一個典型，其中，結點對應於區域，相鄰的區域用弧線連線起來。分割的圖像由具有相似的性質（亮度、紋理、彩色......）的區域構成，這些區域對應著場景中的一些實體，當區域之間具有一些共同邊界時，相鄰關係就成立了。

圖1給出了一個區域鄰接圖例子，其中圖像中的區域用數字標識，標識0代表著圖像外的像素。在區域鄰接圖中，這個數值用來指出與圖像邊界接觸的區域。

特點

區域鄰接圖具有一些吸引人的特徵。如果一個區域包圍其他區域，那么，對應於內部區域的那部分圖就可以被圖的割分離出來，度數為1的結點表示簡單的孔。

區域鄰接圖的弧可以包括相鄰區域之間關係的一個描述，常見的關係有“在左側”或“在內部”。在識別任務中區域鄰接圖可用於與存儲的模式進行匹配。

區域鄰接圖通常是從區域圖創建的，區域圖是和原始圖像矩陣相同維數的矩陣，其元素是區域的識別標號。為了創建區域鄰接圖，圖中所有的區域邊界都要跟蹤出來，所有的相鄰區域的標號都要記錄下來，也可從四叉樹表示的圖像中創建區域鄰接圖。

區域鄰接圖明確地存儲了圖中所有區域的相鄰信息。區域圖中也含有這樣的信息，但從中得到它卻要困難得多。如果想快速地將區域鄰接圖和區域圖關聯起來，只要將區域鄰接圖中的結點，用區域的標識號和某個代表像素（例如，區域左上角的像素）標註起來，就足夠了。

形成過程

區域鄰接圖（RAG）的形成過程如下：

①對標號圖像上的每一個標號，在區域鄰接圖建立一個對應的節點，標記為

②順序掃描標號影像，並在每一個像素角標完成下列各步

③令Label1=Label1[i,j] ( i 為行號，j 為列號)

④先後查看像素[i,j] 的右鄰接像素[i,j+1] 和下鄰接像素[i+1,j] ，令Label2 分別等於 Label[i,j+1]和Label[i+1,j]，若 Label1≠Label2，查看對RAG的節點和之間是否已經建立了連線，如果沒有，則增加一條弧線，以建立連線；

⑤回到步驟②繼續循環執行，直到遍歷完畢。

套用示例

在區域邊緣立體匹配方面：

通過圖像分割提取的輪廓邊緣屬於區域邊界，常規的匹配思路是以兩兩區域之間的邊界線為單位，將閉合的區域邊界按分段邊緣的數據結構形式進行匹配。而由於不同視點的成像差異會使左右圖像分割區域通常並不嚴格對應，區域之間的邊界線也很難一一對應，往往是左圖像中一條邊緣的一部分和右圖像中一條邊緣的其中一部分對應，出現交叉對應的複雜情況。若以分段邊緣線為匹配基元，在一定程度上會造成部分邊緣的丟失，而對過多的邊緣線進行匹配也相對更為耗時。

由於邊界具有同時屬於相鄰的兩個區域的特點，區域邊緣能夠反映圖像中各分割區域的相互連線狀況，反之也能根據區域的鄰接關係來指導邊緣匹配，以確定合適的匹配順序。圖像分割區域的鄰接關係通常採用區域鄰接圖(Region Adjacency Graph, RAG)的數據結構形式進行描述。