網(wǎng)格分割算法（Random Walks）

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

　　該問題可以描述為如下數(shù)學(xué)形式：

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

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

?????? 那么通過求解該線性方程組就可以得到各個(gè)點(diǎn)到達(dá)目的地N點(diǎn)的概率，以上就是一維隨機(jī)游走算法原理。

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

?????? [Lai et al. 2008]將這種思想擴(kuò)展到三維網(wǎng)格分割，文章將網(wǎng)格中每個(gè)三角片對(duì)應(yīng)圖中一個(gè)節(jié)點(diǎn)，利用相鄰三角片之間的二面角來定義節(jié)點(diǎn)之間的權(quán)重，具體如下：

對(duì)于三角片f_i，定義一個(gè)f_i與相鄰三角片f_i,k(k = 1, 2, 3)之間幾何差異的函數(shù)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的法向，對(duì)于凹邊η設(shè)置為1.0，對(duì)于凸邊η設(shè)置為0.2。

　　將d歸一化：

　　節(jié)點(diǎn)之間的權(quán)重p_i,k可以根據(jù)函數(shù)d(f_i, f_i,k)給定：

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

　　[Zhang et al. 2010]對(duì)[Lai et al. 2008]的網(wǎng)格分割算法做了部分改進(jìn)，文章將網(wǎng)格中每個(gè)頂點(diǎn)對(duì)應(yīng)圖中一個(gè)節(jié)點(diǎn)，由于一個(gè)網(wǎng)格的三角片數(shù)量通常是頂點(diǎn)數(shù)量的2倍左右，這樣求解的方程變量數(shù)就會(huì)減少一半左右，計(jì)算速度就會(huì)得到提高。

效果：

?

歡迎大家一起探討計(jì)算機(jī)圖形學(xué)算法問題，郵箱：shushen@126.com

本文為原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處：http://www.cnblogs.com/shushen。

?

?

參考文獻(xiàn)：

[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.

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

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。