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