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

有效

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

1.一種基于Tarjan算法和區域連接的圖像分割方法，其特征在于，該方法包括以下步驟：

S1.基于圖像相鄰像素點之間的梯度差的正負對輸入圖像I構建有向圖I'；令p，q表示圖像I上一對相鄰的像素點，表示兩點的梯度值，若構建兩條有向連接線分別指向p和q；若構建一條有向連接線由q指向p，反之構建有向連接線從p指向q；

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

S3：計算相鄰碎片區域之間的兩類連接邊，一類邊連接相鄰兩區域的葉子節點，權重為w_e1；另一類邊連接相鄰兩區域的根節點，權重為w_e2；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中像素點的個數；

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

size(U)-size(V)≤α；

size(U)≤β或者size(V)≤β；

c＜min(Int(U)+τ(U),Int(V)+τ(V))

其中α＝β＝50，c表示當前判斷的連接邊的權重，Int(U)表示區域U里面的最大的邊權重，Int(V)表示區域V里面的最大的邊權重；

τ(U)＝k/size(U)；k＝m*n/s

m和n表示輸入圖像I的寬度和高度，s＝200；τ(U)控制兩個區域之間的差異在多大程度上小于區域內差異才能被連接；

S5：輸出分割圖像I”。

2.根據權利要求1所述的基于Tarjan算法和區域連接的圖像分割方法，其特征在于：S4中λ取0.2。