常见边界提取算子
一、邊緣的重要性
? ??
? ? ? ? 邊緣在圖像處理中的重要性不言而喻。當前AI最高端技術莫過于深度學習，而圖像方面的深度學習建模所需要的特征，很多是從邊緣為起點，不斷向上構成更高層次的特征描述。我們來看下例子，此例摘自zouxy09關于深度學習的一篇文章（?Deep Learning（深度學習）學習筆記整理系列）：
? ? ? ?1995 年前后，Bruno Olshausen和 David Field 兩位學者任職 Cornell University，他們試圖同時用生理學和計算機的手段，雙管齊下，研究視覺問題。
??????? 他們收集了很多黑白風景照片，從這些照片中，提取出400個小碎片，每個照片碎片的尺寸均為 16x16 像素，不妨把這400個碎片標記為 S[i], i = 0,.. 399。接下來，再從這些黑白風景照片中，隨機提取另一個碎片，尺寸也是 16x16 像素，不妨把這個碎片標記為 T。
????????他們提出的問題是，如何從這400個碎片中，選取一組碎片，S[k], 通過疊加的辦法，合成出一個新的碎片，而這個新的碎片，應當與隨機選擇的目標碎片 T，盡可能相似，同時，S[k] 的數量盡可能少。用數學的語言來描述，就是：
??????? Sum_k (a[k] * S[k]) --> T,???? 其中 a[k] 是在疊加碎片 S[k] 時的權重系數。
??????? 為解決這個問題，Bruno Olshausen和 David Field 發明了一個算法，稀疏編碼（Sparse Coding）。
??????? 稀疏編碼是一個重復迭代的過程，每次迭代分兩步：
1）選擇一組 S[k]，然后調整 a[k]，使得Sum_k (a[k] * S[k]) 最接近 T。
2）固定住 a[k]，在 400 個碎片中，選擇其它更合適的碎片S’[k]，替代原先的 S[k]，使得Sum_k (a[k] * S’[k]) 最接近 T。
????????經過幾次迭代后，最佳的 S[k] 組合，被遴選出來了。令人驚奇的是，被選中的 S[k]，基本上都是照片上不同物體的邊緣線，這些線段形狀相似，區別在于方向。
??????? Bruno Olshausen和 David Field 的算法結果，與 David Hubel 和Torsten Wiesel 的生理發現，不謀而合！
? ? ? ? ??也就是說，復雜圖形，往往由一些基本結構組成。比如下圖：一個圖可以通過用64種正交的edges（可以理解成正交的基本結構）來線性表示。比如樣例的x可以用1-64個edges中的三個按照0.8,0.3,0.5的權重調和而成。而其他基本edge沒有貢獻，因此均為0 。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖 1
? ? ? 上面的例子只是說明了邊緣特征的重要性（是不是扯遠了）。接著扯。。。
二、邊緣定義及類型
? ??
? ? ? ? 定義：邊緣是不同區域的分界線，是周圍（局部）像素有顯著變化的像素的集合，有幅值與方向兩個屬性。這個不是絕對的定義，主要記住邊緣是局部特征以及周圍像素顯著變化產生邊緣。
? ? ? ? ?tips：輪廓和邊緣的關系，一般認為輪廓是對物體的完整邊界的描述，邊緣點一個個連接起來構成輪廓。邊緣可以是一段邊緣，而輪廓一般是完整的。人眼視覺特性，看物體時一般是先獲取物體的輪廓信息，再獲取物體中的細節信息，比如看到幾個人站在那，我們一眼看過去馬上能知道的是每個人的高矮胖瘦，然后才獲取臉和衣著等信息。
? ? ? ? ?類型：簡單分為4中類型，階躍型、屋脊型、斜坡型、脈沖型，其中階躍型和斜坡型是類似的，只是變化的快慢不同，同樣，屋脊型和脈沖型也是如此。見圖2，（a）和（b）可認為是階躍或斜坡型，（c）脈沖型，（d）屋脊型，階躍與屋脊的不同在于階躍上升或下降到某個值后持續下去，而屋脊則是先上升后下降。
圖 2 邊緣類型
三、圖像邊緣描述
? ? ? ??
? ? ? ?我們更多關注的是階躍和屋脊型邊緣，邊緣用微分算子來刻畫，見圖3
圖 3
? ? ? ? 在數學中，函數的變化率由導數來刻畫，圖像我們看成二維函數，其上面的像素值變化，當然也可以用導數來刻畫，當然圖像是離散的，那我們換成像素的差分來實現。對于階躍型邊緣，圖3中顯示其一階導數具有極大值，極大值點對應二階導數的過零點，也就是，準確的邊緣的位置是對應于一階導數的極大值點，或者二階導數的過零點（注意不僅僅是二階導數為0值的位置，二值正負值過渡的零點）。故邊緣檢測算子的類型當然就存在一階和二階微分算子。
四、邊緣檢測算子類別
? ? ? ??
? ? ?常見邊緣檢測算子：Roberts 、Sobel 、Prewitt、Laplacian、Log/Marr、Canny、Kirsch、Nevitia
? ? ? ?一階微分算子：Roberts 、Sobel 、Prewitt
? ? ? ??Robert算子是第一個邊緣檢測算子，提出者Lawrence Roberts in 1963。
? ? ? ? Sobel邊緣算子，當年作者并沒有公開發表過論文，僅僅是在一次博士生課題討論會(1968)上提出("A 3x3 Isotropic Gradient Operator for Image Processing")，后在1973年出版的一本專著（"Pattern Classification and Scene Analysis"）的腳注里作為注釋出現和公開的。提出者Irwin Sobel。
? ? ? ? Prewitt算子來自J.M.S. Prewitt "Object Enhancement and Extraction" in "Picture processing and Psychopictorics", Academic Press,1970。
? ? ? ? 我們看這三種邊緣檢測算子模板及寫成差分的形式
?Roberts算子
Sobel算子
Prewitt算子
圖 4 一階微分算子
? ? ? ?如何計算邊緣幅值與方向？以Sobel算子為例。3*3 Sobel兩個方向的算子在圖像上滑動，模板與其覆蓋的圖像3*3區域9個像素進行卷積，求和后得到此方向的邊緣檢測幅值。
f(x,y)為圖像，Gx和Gy分別是水平和豎直方向算子的卷積結果，G則是最終得到的邊緣幅值，θ值則是邊緣方向。當然G的計算有時簡化為
??
或者
?
求幅值時是有多種選擇的，一般根據具體應用選擇用水平還是豎直或是兩個方向同時檢測。
? ? ? ? 另外，需要說明的是，Sobel算子還有一種變種，是各向同性Sobel算子，其模板為
圖 5 各向同性Sobel算子
Sobel各向同性算子的權值比普通Sobel算子的權值更準確。為什么？模板的權值是離中心位置越遠則權值（看絕對值）影響越小，如上圖，把模板看成是9個小正方形，小正方形邊長為1，則虛線三角形的斜邊長為，下直角邊長為1，則如果（0,0）位置權值絕對值大小為1，則按照距離關系，位置（1,0）處的權值絕對值大小應該為才是準確的。
? ? ? ?二階微分算子：Laplacian、Log/Marr
? ? ? ? 拉普拉斯算子來自拉普拉斯變換，而Log算子又稱Marr算子，由David Courtnay Marr和Ellen Hildreth（1980）共同提出，計算神經學創始人Marr在1980年正式發表論文時，因換白血病早逝，后面設立Marr獎以此紀念其貢獻，現在每兩年的ICCV（與ECCV，CVPR并稱計算機視覺三大頂級會議）會評出一個Marr獎。這兩種算子模板如下：
Laplacian算子（兩種模板）
Log算子
圖 6 二階微分算子
拉普拉斯算子數學公式是
寫成差分形式為
? ? ? ? Log邊緣檢測則是先進行高斯濾波再進行拉普拉斯算子檢測，然后找過零點來確定邊緣位置，很多時候我們只是知道Log 5*5模板如上圖所示，但是具體是怎么得到的？下面進行推導。
二維高斯公式是
按拉普拉斯算子公式求x，y方向的二階偏導后為
這里x，y不能看成模板位置，應看成是模板其他位置到中心位置的距離。那么寫成
這里x0，y0就是模板中心位置，x，y是模板其他位置，對于5*5模板，則x0=2，y0 = 2，那對于模板中（0,0）位置的權值，即把x= 0，y= 0，x0= 2，y0 = 2帶入上式，另= 1，得到約等于0.0175，這樣得到
通過取整變符號，且模板總和為0，得到圖6所示的模板。
? ? ? ? 另外，這里模板大小是如何取的？通常高斯分布中，在（-3，3）的范圍內就覆蓋了絕大部分區域，所以模板大小一般取dim = 1 + 6（在SIFT特征中，其中的高斯模糊也是這樣取），dim如果為小數，則取不小于dim的最小整數，當然實際使用時沒有這么嚴格，如上面我們取=1時，模板大小取5*5。那同一個尺寸的模板中的權值調整就是的變化得到的，變化到一定程度，模板尺寸大小改變（這個是個人理解，歡迎拍磚）。
? ? ? ?非微分邊緣檢測算子：Canny
? ? ? ?Canny邊緣檢測大家應該很熟悉，這里列出步驟，并給出一個詳細介紹的鏈接Canny算子。
? ? 1. ? ? ?彩色圖像轉換為灰度圖像
? ? 2. ? ? ?對圖像進行高斯模糊
? ? 3. ? ? ?計算圖像梯度，根據梯度計算圖像邊緣幅值與角度（這里其實用到了微分邊緣檢測算子來計算梯度幅值方向）
? ? 4. ? ? ?非最大信號壓制處理（邊緣細化）
? ? 5. ? ? ?雙閾值邊緣連接處理
? ? 6. ? ? ?二值化圖像輸出結果
? ?方向算子Kirsch（8個3*3模板），Nevitia （12個5*5模板）
? ? ? ? 這兩個算子是利用多個方向的子模板進行分別計算，最后取幅值最大的那個為最終邊緣幅值，方向即最大幅值對應的那個方向
五、各邊緣檢測算子對比
opencv直接調用的Roberts和Prewitt邊緣檢測
自己寫的Sobel算子，分別進行豎直和水平邊緣檢測，最后取豎直和水平邊緣最大幅值
opencv直接調用的Laplacian和Canny邊緣檢測
Log 5*5模板，可以看出Log檢測出的邊緣很多并不是真正的邊緣位置，下圖沒有經過過零點排除一些邊緣點，噪聲被充分檢測出來。
當然，有很多關于以上邊緣檢測算子的理論解釋及特性等可以參考以下幾篇博文：
1、http://blog.csdn.net/xiaojiegege123456/article/details/7714863
2、http://blog.csdn.net/yanmy2012/article/details/8110316
3、http://blog.csdn.net/langb2014/article/details/45667921
參考資料：
1、張麗.《經典邊緣檢測算子比較》.南京信息工程大學.
2、百度百科“Sobel算子”
3、http://blog.csdn.net/a361251388leaning/article/details/50288479
4、http://blog.csdn.net/zouxy09/article/details/8775488
總結
- 上一篇： php7对象转换成数组,php 如何把对
- 下一篇： IntelliJ IDEA——数据库集成