本文相關
-
Paper Summary:https://github.com/FDU-VTS/CVPaper -
Code:https://github.com/FDU-VTS/CVCode
原文鏈接
基礎知識
- 一張圖是由不同的像素點構成的绒怨，本文的計算和構建都是基于像素點的運算凳怨，即
(RGB)值 - 高斯模糊/拉普拉斯變換:用于轉換圖像，減少圖像噪聲的平滑算法
- 最小生成樹
(Minimum Spanning Tree | MST)指的是钻洒，在圖中建立一個連通圖并且沒有回路是生成樹，而最小生成樹指的是構成結果權值最小 - 不同像素點之間的差:即
RGB值之間的歐氏距離 - 并查集算法(union find set)以及克魯斯卡爾算法(Kruskal)篓叶，使用邊建立并查集野哭，并且使用kruskal進行搜索合并
早期的分割方法
- Zahn提出了一種基于圖的最小生成樹（MST）的分割方法，用來進行點聚類以及圖像分割胳搞，前者權值是點間距離，后者權值是像素差異称杨。
- 不足：根據(jù)閾值不同肌毅，會導致高可變性（大約是色彩對比強的一個區(qū)域）區(qū)域劃分為多個區(qū)域；將ramp和constant region合并到一起姑原。
- Urquhart提出用邊相連的點中邊權值最小的進行歸一化悬而，找周圍相似的。
- 根據(jù)各個區(qū)域是否符合某種均勻性標準來分割锭汛，找均勻強度或梯度的區(qū)域笨奠，不適用于某個變化很大的區(qū)域袭蝗。
- 使用特征空間聚類：通過平滑數(shù)據(jù)——給定半徑的超球面對各個點擴張其連通分量，找到簇艰躺，來保持該區(qū)域的邊界呻袭，并對數(shù)據(jù)進行轉換。
基于圖的分割
定義
-
G:將圖像由像素點轉化為圖 -
V:每一個像素點都是圖中的點 -
E:任意兩個相鄰像素點之間邊 -
C:被劃分的Segmentation,一個C中有至少1個像素點 -
Int(C):區(qū)域內(nèi)最小生成樹權值最大的邊腺兴，表示的是左电，記為 -
Dif(C1,C2):表示C1和C2之間的距離页响，記為 - 最后要形成的分組要求是(表示了所有區(qū)域之間的最小距離都比區(qū)域內(nèi)的最大距離和權值的和要大)
- 其中
MInt(C1,C2)的值為: - 閾值設定的原因是為了在開始時篓足，因為只有單個像素點，那么點內(nèi)的距離為0闰蚕，而點之間的距離還存在栈拖，那么導致無法合并。所以加入閾值没陡。
分割算法（與克魯斯卡爾算法構建最小生成樹有密切關系涩哟。）
- 輸入是一個有n個節(jié)點和m條邊的圖G，輸出是一系列區(qū)域盼玄。步驟如下：
- 0.將邊按照權重值以非遞減方式排序
- 1.最初的分割記為S（0）贴彼，即每一個節(jié)點屬于一個區(qū)域。
- 2.按照以下的方式由S(q-1)構造S(q)：記第q條邊連接的兩個節(jié)點為vi和vj埃儿，如果在S(q-1)中vi和vj是分別屬于兩個區(qū)域并且第q條邊的權重小于兩個區(qū)域的區(qū)域內(nèi)間距器仗，則合并兩個區(qū)域。否則令S(q) = S(q-1)童番。
- 3.從q=1到q=m精钮，重復步驟2。
- 4.返回S(m)即為所求分割區(qū)域集合剃斧。
補充
高斯濾波器
- 高斯變換就是用高斯函數(shù)對圖像進行卷積轨香，高斯濾波器是一種線性濾波器，能夠有效抑制噪聲幼东，并平滑圖像臂容。其實質(zhì)是取濾波器窗口內(nèi)像素的均值作為輸出。
- 高斯函數(shù)公式如下:
-
其中筋粗，u是x的均值,σ是方差策橘。
-
- 由一維函數(shù)炸渡，我們可以推導出二維函數(shù)的公式如下：
- 高斯函數(shù)在圖像處理中的使用娜亿，實際上就是對每個像素點的周邊像素取平均值，從而達到平滑的效果蚌堵，在取值(周邊半徑)時买决，周圍像素點的半徑越大沛婴，則圖像的模糊度就越強。在實際計算時督赤，利用高斯模糊按正態(tài)曲線分配周邊像素的權重嘁灯，從而求中心點的加權平均值。
- 高斯模糊的具體計算方式如下：
- 1.將中心點周圍的八個點帶入到高斯函數(shù)中躲舌，從而得到權重矩陣A1丑婿；
- 2.為使歸一化，將矩陣A1中的各個點除以所有點(9個點)的權重和没卸，得到歸一化后的權重矩陣A2;
- 3.圖片原始的像素矩陣分別乘以A2中各自的權重值羹奉，將得到的所有點的值加起來求平均，便得到中心點的高斯模糊值约计。圖像中其余點相同求法诀拭。
- 注：1.彩色圖片，可對RGB三通道分別作高斯模糊煤蚌。
- 2.
σ代表數(shù)據(jù)的離散程度耕挨，σ越大，中心系數(shù)越小尉桩，圖像越平滑筒占；反之，反之魄健。
拉普拉斯變換：是為解決傅立葉變換等幅振蕩的缺點赋铝。
- 首先了解一下傅立葉變換：傅立葉變換是一種物理上探究頻譜的方法，三角公式是：
- 其中,
w0表示基波沽瘦。
- 由歐拉公式：
- 將傅立葉三角形式公式中的正余弦函數(shù)用指數(shù)函數(shù)表示革骨，改寫為用復指數(shù)表示的公式，如下：
- 將上述公式改為積分形式析恋，即得到復指數(shù)形式公式為：
- 但由于傅立葉變換是等幅振蕩的正弦波良哲，故當f(t)不斷趨向無窮時，此時函數(shù)將不再收斂助隧，這時候便不再適合使用傅立葉變換筑凫。于是，我們引入一個衰減因子并村，對其作變換巍实。對函數(shù)y=f(t)乘上一個
,其中，
σ>0哩牍。 - 對上式進行合并同類項棚潦，可得到
- 我們將指數(shù)中的
σ+jw最初的分割記為S，于是得到拉普拉斯公式：-
??
-
- 由上式推導膝昆，很清楚的知道丸边，當s=jw時叠必，拉普拉斯函數(shù)就變成了傅立葉函數(shù)，也就相當于拉氏不再具有衰減功能妹窖。
- 又由上述公式可以很直觀地看到當取值
剛好收斂時纬朝，則
>
