網格分割算法（Random Walks）

　　首先以一維隨機游走（1D Random Walks）為例來介紹下隨機游走（Random Walks）算法，如下圖所示，從某點出發，隨機向左右移動，向左和向右的概率相同，都為1/2，并且到達0點或N點則不能移動，那么如何求該點到達目的地N點的概率。

　　該問題可以描述為如下數學形式：

P(0) = 0

P(N) = 1

P(x) = 1/2*P(x - 1) + 1/2*P(x + 1) for x = 1, 2, 3, … , N-1

　　如果用矩陣形式描述，即：

?????? 那么通過求解該線性方程組就可以得到各個點到達目的地N點的概率，以上就是一維隨機游走算法原理。

?????? [Grady et al. 2006]提出了利用隨機游走思想來分割二維圖像，文章將圖像考慮成一張圖（Graph），每個像素對應圖中一個節點，根據亮度差值定義節點間的權重（相當于一維隨機游走中向左和向右的概率），然后用戶指定前景（foreground）和背景（background）標簽（相當于一維隨機游走中N點和0點），通過求解線性方程組就可以得到各個像素點屬于前景或背景的概率，如果將閾值概率設置為0.5，那么就可以分割得到期望的圖像區域。

?????? [Lai et al. 2008]將這種思想擴展到三維網格分割，文章將網格中每個三角片對應圖中一個節點，利用相鄰三角片之間的二面角來定義節點之間的權重，具體如下：

對于三角片f_i，定義一個f_i與相鄰三角片f_i,k(k = 1, 2, 3)之間幾何差異的函數d(f_i, f_i,k)：

d(f_i, f_i,k) = η·[1 – cos(dihedral(f_i, f_i,k))] = η/2·||N_i?– N_i,k||²

其中：dihedral(f_i, f_i,k)代表相鄰三角片f_i與f_i,k之間的二面角，N_i為三角片f_i的法向，對于凹邊η設置為1.0，對于凸邊η設置為0.2。

　　將d歸一化：

　　節點之間的權重p_i,k可以根據函數d(f_i, f_i,k)給定：

　　同樣通過求解線性方程組可以得到網格分割效果。

　　[Zhang et al. 2010]對[Lai et al. 2008]的網格分割算法做了部分改進，文章將網格中每個頂點對應圖中一個節點，由于一個網格的三角片數量通常是頂點數量的2倍左右，這樣求解的方程變量數就會減少一半左右，計算速度就會得到提高。

效果：

?

歡迎大家一起探討計算機圖形學算法問題，郵箱：shushen@126.com

本文為原創，轉載請注明出處：http://www.cnblogs.com/shushen。

?

?

參考文獻：

[1] Grady, L., "Random Walks for Image Segmentation," in Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.28, no.11, pp.1768-1783, Nov. 2006

[2] Yu-Kun Lai, Shi-Min Hu, Ralph R. Martin, and Paul L. Rosin. 2008. Fast mesh segmentation using random walks. In Proceedings of the 2008 ACM symposium on Solid and physical modeling (SPM '08). ACM, New York, NY, USA, 183-191.

[3] Zhang, J., Wu, C., Cai, J., Zheng, J. and Tai, X.-c. (2010), Mesh Snapping: Robust Interactive Mesh Cutting Using Fast Geodesic Curvature Flow. Computer Graphics Forum, 29: 517–526.

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的网格分割算法（Random Walks）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。