1
雷鋒網(wǎng)按：本文作者系VR行業(yè)資深從業(yè)者。
2016年，VR如龍卷風(fēng)一樣席卷了整個科技圈，一時間，恨不得所有行業(yè)都要跟VR搭上邊才能體現(xiàn)其與時俱進(jìn)的創(chuàng)新性，也有越來越多的人開始了解并走進(jìn)VR，當(dāng)然其中不乏一些湊熱鬧的人。正所謂，這年頭吹牛的時候不整點專業(yè)的詞都不好意思唬人。筆者簡單整理了幾個VR中常用到的算法供大家參考。這些看起來非常高大上的算法，你了解幾個呢？
運動分為正向運動和反向運動。FK是 forward kinematics的縮寫， 即正向動力學(xué)；IK是Inverse Kinematics的縮寫，即反向運動學(xué)。人體的分級結(jié)構(gòu)骨架，由許多采用分級方式組的環(huán)節(jié)鏈構(gòu)成，包括分級結(jié)構(gòu)關(guān)節(jié)或鏈，運動約束和效應(yīng)器，由效應(yīng)器帶動所有部分同時運動。
例如，肩關(guān)節(jié)、肘關(guān)節(jié)、腕關(guān)節(jié)及其子骨骼就是一條環(huán)節(jié)鏈，也就是運動鏈，是整個人體運動鏈上的一條分支，而我們的身體即是利用運動鏈對運動進(jìn)行控制的。已知鏈上各個關(guān)節(jié)旋轉(zhuǎn)角，求各關(guān)節(jié)的位置信息和末端效應(yīng)器(end effector)的位置信息，這是正向運動學(xué)的問題；而己知末端效應(yīng)器的位置信息，反求其祖先關(guān)節(jié)的旋轉(zhuǎn)角和位置，這就是反向運動學(xué)。
首先，我們先一起詳細(xì)了解一下FK，即正向動力學(xué)。
正向動力學(xué)認(rèn)為子級關(guān)節(jié)會跟隨父級關(guān)節(jié)的運動，而子級關(guān)節(jié)又可以獨立運動而不影響到父級關(guān)節(jié)的狀態(tài)。以人體運動為例，當(dāng)我們舉起手臂時，腕關(guān)節(jié)會隨其父級肘關(guān)節(jié)上抬，肘關(guān)節(jié)會隨其父級肩關(guān)節(jié)的旋轉(zhuǎn)而移動。擔(dān)當(dāng)腕關(guān)節(jié)旋轉(zhuǎn)時，其上級關(guān)節(jié)都不會發(fā)生運動，這就是典型的正向動力學(xué)運動方式。因此，如果我們已知運動鏈上每個關(guān)節(jié)的旋轉(zhuǎn)角，就可以控制其子級關(guān)節(jié)的運動。
正向動力學(xué)的優(yōu)勢是計算簡單，運算速度快，缺點是需指定每個關(guān)節(jié)的角度和位置，而由于骨架的各個節(jié)點之間有內(nèi)在的關(guān)聯(lián)性，直接指定各關(guān)節(jié)的值很容易產(chǎn)生不自然協(xié)調(diào)的動作。應(yīng)用于VR動作捕捉行業(yè)時使用者需要在每一個骨骼分支都佩戴動捕設(shè)備，使用不方便。
正向動力學(xué)被應(yīng)用于VR動捕技術(shù)中，具體實現(xiàn)流程是：
使用者身上每一個骨骼分支都佩戴動作捕捉節(jié)點，例如手部、小臂、大臂、肩膀構(gòu)成一條鏈。動作捕捉節(jié)點獲取每個骨關(guān)節(jié)在運動過程中的旋轉(zhuǎn)角，將旋轉(zhuǎn)角應(yīng)用到FK算法中，與相對應(yīng)的骨骼長度一起即可計算出子關(guān)節(jié)和末端效應(yīng)器的位置信息，再利用這些信息控制整個人體模型的運動。
應(yīng)用：動作捕捉技術(shù)。
接下來我給大家介紹一下IK，即反向動力學(xué)。
上文已經(jīng)介紹了IK算法所要解決的問題，我再以投球動作為例說明：如果我們知道出球的起始位置、最終位置和路徑，那么投球者手臂等的轉(zhuǎn)動即可按反向運動學(xué)自動算出。反向運動學(xué)方法在一定程度上減輕了正向運動學(xué)方法的繁瑣工作，是生成逼真關(guān)節(jié)運動的最好方法之一。
求解IK問題的方法有很多，大致可以分為兩大類：
解析法（AnalyticSolutiosn）：可以求得所有的解，對于自由度較少的IK鏈，求解速度較快，比較適合應(yīng)用于自由度較少的控制中，便于實時控制。但隨著關(guān)節(jié)數(shù)量的增加，解析法求解方程的復(fù)雜度也急劇增加。所以解析法只適合自由度比較少的鏈，不適合復(fù)雜的IK鏈。
數(shù)值法（Numerialsolutions）：數(shù)值法的優(yōu)勢在于通用性和靈活性，能處理自由度較多的比較復(fù)雜的具有分層結(jié)構(gòu)的IK鏈，并且能較容易的實現(xiàn)在IK鏈中加入新的約束條件。數(shù)值法實際上是一種反復(fù)逼近，不斷迭代的方法。由于IK問題的復(fù)雜性，數(shù)值法的不足之處在于高計算量，由于是反復(fù)迭代進(jìn)行求解，所以所求結(jié)果未必準(zhǔn)確。
由于反向動力學(xué)可以解決定位問題，所以VR動作捕捉技術(shù)、手勢識別技術(shù)均可應(yīng)用IK算法。我以動作捕捉技術(shù)為例說明具體實現(xiàn)流程如下：
動作捕捉技術(shù)是通過使用稱為跟蹤器的專門的傳感器來記錄運動者的運動信息。然后，我們就可以利用所記錄下來的數(shù)據(jù)來產(chǎn)生動畫運動。
利用IK算法進(jìn)行動作捕捉的大體流程如下：
首先在VR內(nèi)容中建立人體模型，然后為人體模型預(yù)留數(shù)據(jù)接口；
利用硬件獲取末端效應(yīng)器的位置信息，然后利用IK（反向動力學(xué)）算法計算出人體運動數(shù)據(jù)，包括關(guān)節(jié)旋轉(zhuǎn)角和位置等；
再將這些信息賦予人體模型預(yù)留的接口，驅(qū)動人體模型按照佩戴硬件的目標(biāo)人物動起來，并顯示在內(nèi)容中。
應(yīng)用：動作捕捉技術(shù)、手勢識別技術(shù)。
PNP準(zhǔn)確來說是一個問題，PNP 問題是由 Fisher 和 Bolles于 1981 年提出的。
PNP 問題的具體表述如下：在已知給定n個特征點中任意兩個特征點之間的距離以及這兩個特征點與光心所成的角度，來求解各特征點與光心的距離，這就是PNP問題。PNP的主要用處就是可以確定目標(biāo)物體上的n個特征點在攝像機坐標(biāo)系下的坐標(biāo)，然后根據(jù)標(biāo)定獲取的攝像機內(nèi)外部參數(shù)，求算出特征點在世界坐標(biāo)系下的坐標(biāo)值，最終給出目標(biāo)的位姿信息。
PNP 問題是一種基于單幅圖像的定位解算方法，在VR目標(biāo)定位和姿態(tài)解算上得到廣泛的應(yīng)用。
求解PNP問題的方法有很多，大致可以分為兩大類，非迭代算法和迭代算法：
非迭代算法主要是針對 P3P、P4P 等特征點較少的PNP 問題進(jìn)行研究，主要是應(yīng)用數(shù)學(xué)代數(shù)算法直接求解被測目標(biāo)的相對位姿，并且還推導(dǎo)出多種解析算法。非迭代算法運算量小算法計算速度快，但是受系統(tǒng)誤差影響較大，而且解算精度一般情況下都不高，主要被應(yīng)用于迭代算法的初值計算。非迭代算法求解主要對象是針對于6個以上異面特征點或是有4個以上共面特征點兩種情況。
迭代算法應(yīng)用于求解PNP問題時，是基于不存在圖像噪聲假設(shè)條件下進(jìn)行推導(dǎo)的，得出解析解相對于攝像機特征像點的位置誤差的敏感度特別高。而為了克服噪聲的影響，提高位姿解算精度，多采用PNP迭代算法進(jìn)行位姿信息的求解，其主要思路是將PNP 問題進(jìn)一步表示為一種受約束的非線性優(yōu)化問題，通過求解得到被測目標(biāo)相對位姿的數(shù)值解。該處理方法的優(yōu)化變量空間為N+6維（N為點特征數(shù)），迭代計算量較大，又受初始值解算精度影響，因此算法通常會收斂到局部最小值或收斂到錯誤解，而不是全局最小值。
可能上述的描述會比較抽象，這里我以P3P為例，為大家舉例說明：
如上圖：O 為相機光心，目標(biāo)的三個特征點 A， B ，C 與光心 O 之間的長度分別為 x， y， z ，已知三條線間的夾角為α，β，γ， |AB|=c ，|AC|=b |BC|=a，利用α，β，γ和a，b，c求解 x， y， z，這就是P3P問題。
P3P 問題特征點數(shù)目只有3個，可以直接使用非迭代算法，其方程描述如下：
設(shè) A'，B'，C'分別是 A， B，C在攝像機成像平面上的點，則在求得 x ，y，z 后，利用A'， B' ，C'坐標(biāo)，根據(jù)攝像機的成像關(guān)系，就可解算的特征點在攝像機坐標(biāo)系下的坐標(biāo)。
PNP算法可以應(yīng)用于VR的定位技術(shù)，如紅外光學(xué)定位技術(shù)，用來獲取位姿信息。
具體實現(xiàn)流程：
攝像機獲取目標(biāo)物體的圖像，然后在圖像中提取出特征點；
再利用PNP算法獲得特征點在攝像機坐標(biāo)系下的坐標(biāo)；
然后利用旋轉(zhuǎn)理論將攝像機坐標(biāo)系下的坐標(biāo)轉(zhuǎn)換到世界坐標(biāo)系下，最終獲得世界坐標(biāo)系下特征點的信息。
應(yīng)用：紅外光學(xué)定位等VR定位技術(shù)。此外，PNP獲取的位姿信息還可以應(yīng)用到IK算法中，共同實現(xiàn)VR動作捕捉。
實際上，POSIT算法是上文提到的PNP問題迭代算法的一種，之所以特別提出來說是因為POSIT算法具有收斂域廣和算法速度快的優(yōu)點，在VR行業(yè)中得到非常廣泛的應(yīng)用。迭代算法作為 PnP 問題解法的一個分支，相比于非迭代解法而言可以避免求解非線性方程組，在一定程度上減少了計算復(fù)雜度，POSIT 算法即是迭代算法的典型代表。
POSIT 算法輸入為至少 4個非共面的三維物體表面的三維特征點坐標(biāo)及其對應(yīng)的圖像上二維特征點的坐標(biāo)，它是基于三維物體上所有點都具有相同深度（忽略物體內(nèi)部各點的深度差異）的弱投影假設(shè)實現(xiàn)的。
首先通過正交投影和尺寸變換關(guān)系求得三維物體位姿參數(shù)的初值（POS, Pose from Orthography and Scaling 算法），然后利用此初值對起始特征點進(jìn)行重投影，將重投影所得的新的點作為新的位姿測量參數(shù)，重新運行 POS 算法，經(jīng)過反復(fù)迭代直到滿足所需的精度。
POSIT算法具有以下優(yōu)點：相對于傳統(tǒng)迭代算法，POSIT 不需要一個近似的初始姿態(tài)估計；算法易于編寫代碼實現(xiàn)，傳說中在 MATLAB 環(huán)境下只需要25 行必要的代碼就是它了；相對于數(shù)值迭代算法，POSIT 算法的時間只是相當(dāng)于前者的 10%。
應(yīng)用：紅外光學(xué)定位等VR定位技術(shù)。
以上我介紹了幾個VR中比較常用的問題和算法，文章涉及內(nèi)容不深，只做簡單科普。如果您是行業(yè)小白，又想了解VR，希望我的文章能夠幫到你。
雷鋒網(wǎng)注：本文為雷鋒網(wǎng)獨家約稿，轉(zhuǎn)載請聯(lián)系授權(quán)，并保留出處和作者，不得刪減內(nèi)容。
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
