(2)關于上一篇博文中提到的歐幾裡德分割法稱之為标準的距離分離,當然接下來介紹其他的與之相關的延伸出來的聚類的方法,我稱之為條件歐幾裡德聚類法,(是我的個人了解),這個條件的設定是可以由我們自定義的,因為除了距離檢查,聚類的點還需要滿足一個特殊的自定義的要求,就是以第一個點為标準作為種子點,候選其周邊的點作為它的對比或者比較的對象,如果滿足條件就加入到聚類的對象中,至于到底怎麼翻譯我也蒙了,隻能這樣了解了
主要的缺點:該算法沒有初始化種子系統,沒有過度分割或者分割不足的控制,還有就是從主循環運算中調用條件函數時,效率比較低,
看一下代碼吧,至于到底怎麼了解各個有個人的了解吧
上面執行的條件是檢查候選點的Y坐标是否小于種子的Y坐标,沒有什麼實際意義。是以我就再檢視結果了。
那麼同時我暫時也用不到,如果有想法的時候再回來研究吧
(2)最小分割算法
該算法是将一幅點雲圖像分割為兩部分:前景點雲(目标物體)和背景物體(剩餘部分)
關于該算法的論文的位址:http://gfx.cs.princeton.edu/pubs/Golovinskiy_2009_MBS/paper_small.pdf
The Min-Cut (minimum cut) algorithm最小割算法是圖論中的一個概念,其作用是以某種方式,将兩個點分開,當然這兩個點中間可能是通過無數的點再相連的。如圖

如果要分開最左邊的點和最右邊的點,紅綠兩種割法都是可行的,但是紅線跨過了三條線,綠線隻跨過了兩條。單從跨線數量上來論可以得出綠線這種切割方法更優 的結論。但假設線上有不同的權值,那麼最優切割則和權值有關了。當你給出了點之間的 “圖” ,以及連線的權值時,最小割算法就能按照要求把圖分開。
是以那麼怎麼來了解點雲的圖呢?
顯而易見,切割有兩個非常重要的因素,第一個是獲得點與點之間的拓撲關系,這種拓撲關系就是生成一張 “圖”。第二個是給圖中的連線賦予合适的權值。隻要這兩個要素合适,最小割算法就會正确的分割出想要的結果。點雲是分開的點。隻要把點雲中所有的點連起來就可以了。連接配接算法如下:
找到每個點臨近的n個點
将這n個點和父點連接配接
找到距離最小的兩個塊(A塊中某點與B塊中某點距離最小),并連接配接
重複3,直至隻剩一個塊
經過上面的步驟現在已經有了點雲的“圖”,隻要給圖附上合适的權值,就滿足了最小分割的前提條件。物體分割比如圖像分割給人一個直覺印象就是屬于該物體的點,應該互相之間不會太遠。也就是說,可以用點與點之間的歐式距離來構造權值。所有線的權值可映射為線長的函數。
我們知道這種分割是需要指定對象的,也就是我們指定聚類的中心點(center)以及聚類的半徑(radius),當然我們指定了中心點和聚類的半徑,那麼就要被保護起來,保護的方法就是增加它的權值
接下來我們就來看看代碼
看一下實際運作的最小分割法的結果
原始的點雲
最小分割法的結果
對于實際應用中我們應該設定正确的參數這是最為關鍵的!