[發明專利]一種基于Tarjan算法和區域連接的圖像分割方法

有效

• 申請號: 201710416337.4
• 申請日: 2017-06-06
• 公開（公告）號: CN107274415B
• 公開（公告）日: 2019-08-09
• 發明（設計）人: 張云洲;張珊珊;劉及惟;楚好;姜浩;商艷麗;張凱
• 申請（專利權）人: 東北大學
• 主分類號: G06T7/11
• 分類號: G06T7/11
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉

本發明公開了一種基于Tarjan算法和區域連接的圖像分割技術，所述的Tarjan算法用于求解有向圖的最小分支，當構建完最小分支后，圖像被分割成大量碎片。為防止圖像出現過分割，若相鄰區域間的大小和相似性滿足區域連接條件，則連接相鄰區域。對比目前存在的圖像分割技術，該算法用于圖像分割具有時間快，分割準確，構建過程中不需要設置任何參數等優點。

技術領域

本發明屬于圖像處理技術領域，涉及一種圖像分割技術，具體是一種基于Tarjan算法和區域連接的圖像分割方法。

背景技術

所謂圖像分割指的是根據灰度、顏色、紋理和形狀等特征把圖像劃分成若干互不交迭的區域，并使得這些特征在同一區域內呈現相似性，在不同區域之間呈現明顯的差異性。

現有的圖像分割方法主要分以下幾類：基于閾值的分割方法、基于區域的分割方法、基于邊緣的分割方法以及基于圖論的分割方法等。Zahn提出一種基于圖的最小生成樹的分割方法，但這種簡單的割斷最小權重邊的方法存在很大缺陷。由于圖像中往往灰度劇烈變化的區域的像素之間的灰度差別很大，但是其對應在圖中的邊權重很小，若簡單的設置閾值來割斷小權重邊，則會出現不合理的分割。

但是基于Tarjan算法和區域連接的圖像分割技術，不僅在構圖的時候利用了有向的信息，而且在分割的過程中結合了區域的概念，既保證整體上是一個最小樹形圖，又保證了分割后的每個區域都是一個最小樹形圖，最后的區域連接技術再一次保證了圖像分割的準確性，防止出現過分割。

發明內容

本發明目的是提供一種快速，準確的基于Tarjan算法和區域連接的圖像分割方法，首次提出了在有向圖上進行的，不需要任何參數設置的快速圖像分割算法，該算法具有很大的發展前景和應用空間。

本發明提供一種基于Tarjan算法和區域連接的圖像分割方法，包括以下步驟：

S1.基于圖像相鄰像素點之間的梯度差的正負對輸入圖像I構建有向圖I'。

S2：在有向圖I'上利用Tarjan算法構建最小樹形圖，為了保證樹形圖一定存在，需要添加一個虛擬節點，從虛擬節點構建直線連接有向圖的每個節點，權重為無窮大。構建完最小樹形圖之后去掉虛擬節點和虛擬節點所連接的邊，形成一個個獨立的根樹，每個根樹代表一個碎片區域。

S3：計算相鄰碎片區域之間的兩類連接邊，一種邊連接相鄰兩區域的葉子節點，權重為w_e1。另一種邊連接相鄰兩區域的根節點，權重為w_e2。

S4：將S3中所計算的兩類邊按w_e1，λw_e2進行升序排列并依次判斷：若該邊所連接的兩碎片大小和相似性滿足區域連接條件，則用由區域間顏色差決定的權重邊連接兩碎片區域。

S5：輸出分割圖像I”。

進一步的，S1中構建有向圖的方法為：令p，q表示圖像I上一對相鄰的像素點，表示兩點的梯度值，若構建兩條有向連接線分別指向p和q。若構建一條有向連接線由q指向p，反之構建有向連接線從p指向q。

進一步的，S3中所述w_e1和w_e2計算公式為：

w_e2＝|avg(U)-avg(V)|

其中p1和p2表示相鄰兩區域U和V的根樹的葉子節點，avg(U)和avg(V)代表區域U和V的平均

顏色強度。

avg(U)＝Col_sum(U)/size(U)

Col_sum(U)表示區域U中所有像素點的RGB三通道顏色值之和，size(U)表示區域U中像素點的個數。