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