###### tags: `Paper` 、`3D Computer Game`、`Motion`

# [**Motion Graphs**](https://dl.acm.org/doi/10.1145/566654.566605)

本篇論文是 2002 年由 *Lucas Kovar, Michael Gleicher* 發表於 *SIGGRAPH* 的 paper。

**Websites：** [Lucas Kovar](https://research.cs.wisc.edu/graphics/Gallery/kovar.vol/MoGraphs/)、[Michael Gleicher](https://gleicher.sites.cs.wisc.edu/video/2002_mographs/)

## 1. Introduction
<font color="red">本篇論文主要是將原有的 motion clip 重新拼接組合成一個新的 motion sequence。</font>

要生成逼真的人體運動動畫，
- 常見解決方法是做 motion capture，但卻有耗時、數據難以修改，<font color="blue">例如該動作演員已經過世，或是身價昂貴等因素</font>，當手邊的 data 與要求的不夠相似時，除了蒐集更多的數據外，並沒有其他更好的方法了，且有無法適用於 interactive environments 等問題。
- 本篇論文提出的方法是基於捕捉到的動作，合成為 stream ，並且仍保持原始數據的質量。
- 首先編譯一個名為 motion graph 的 structure，並以不同的方式重新組合
- motion graph 為 directed graph ，其中 edges 上包含了原始捕捉的片段動作數據以及自動生成的過度動作。
- directed graph 上的 node 作為選擇點，可以連接 clips
- 由於論文中的方法會自動檢測並創建過渡動作，因此用戶無需捕捉專門設計用於連接的動作。

==之所以選擇用 graph 這個資料結構，主要是因為 graph 的一個特色，我們可以在 graph 裡，沿著 edge 隨意走動，而不用擔心會跑出 graph 外。==

<center>


</center>

上排圖片為原始 motion capture data，下排圖片為重新生成的 motion。黑色線條為原始路徑，黃色線條為生成後的路徑。前兩組圖皆為 walk 動作，第 3 組圖，原始圖片為 sneaking，下方為 walk 結合 sneaking。

==這邊作者先延續前一篇論文 [Motion Path Editing](https://dl.acm.org/doi/10.1145/364338.364400) 的假設，將動作跟方向分開。==

## 2. Related Work
1. Andrew Witkin, Zoran Popović. 1995. [*Motion warping*](https://dl.acm.org/doi/10.1145/218380.218422).
- 可以平滑地對 motion 進行細微的變化。
2. Michael Gleicher. 1998. [*Retargeting Motion to New Characters*](https://dl.acm.org/doi/10.1145/280814.280820).
- 將其中一方骨架套到另外一個骨架上
4. Jehee Lee, Sung Yong Shin. 1999. [*A Hierarchical Approach to Interactive Motion Editing for Human-like Figures*](https://dl.acm.org/doi/10.1145/311535.311539).
- 一種用於調整 human-like 角色現有動作的技術，透過 constraints set 做到所需的指定特徵。

## 3. Motion Graph Construction
<font color="red">motion graph 是一個有向圖，其中每個 edge 對應的是一個 motion clip。</font>在 motion clip 中，包含了 root 的 position 以及 quaternions 兩個角色參數。<font color="red">每個 node 則是一個選擇點，將這些 clips 連接起來。</font>創建一個 2n 的 disconnected graph，每個 clip 的開頭即結尾各有一個 node，因此，我們可以透過插入 node 的方式，將一個 clip 分成兩個小 clips。

<center>


</center>

(原圖)

<center>


</center>

(筆記)

在上圖中，有兩個 initial clips，我們可以插入一個 node(黃色部分) 將 initial clip 分成較小的 clip，也可以插入一個 transition motion，連接兩個不同的 initial clip(紫色部分)，或者是連接 initial clip 的不同部分(藍色部分)。

然而要生成 transition motion 是一個很難的問題，但如果是兩個相似度很高的 motion，則可以透過簡單的混和技術就可以產生 transition motion。鑑於此，作者提出的方法是，先辨識 inital clips 之間，相似的部分。

接下來的三個小節，描述如何選出一部分的 transition clips，再從這些 clips 中再次進行選擇，並且混和這些 transition clips，最後解釋如何修剪並消除有問題的 edges。

### 3.1 Detecting Candidate Transitions
在作者的系統中， motion capture data 通常是以參數向量的方式來表示，這些參數用以指定，在每個 frame 上，骨架的 root position 和 joint rotation。這邊作者提到一個錯誤的方法，是用計算 vector norm([範數](https://ch-hsieh.blogspot.com/2010/04/norm.html)) 的方式，來測量兩個 frame 之間的 pose 的差異，以決定 transition motion 的插入位置，但這並非一個好方法，因為這仍然有需多問題無法解決：

1. 有些關節的影響比起其他關節來說會大得多，例如：臀部、手腕，但卻無法找到一個適合的固定權重，因為關節所能旋轉的角度，仍取決於當下身體當下的狀況。
2. motion 是 rigid 2D 的 coodination transformation，因此當我們對 motion 進行平移或旋轉時，並不會有根本上的變化，因為 [rigid transformation](http://motion.cs.illinois.edu/RoboticSystems/CoordinateTransformations.html) 的兩個特性：

- 變換後兩點間的距離不會改變
- 在 2D 中，任何三角形的方向和面積皆不會改變

3. 要做到 seamless transition ，所需的資訊遠比單一 frame 能給予的多太多，包含關節速度、加速度，和高階導數。

作者在比對相似性時，同時也將上述因素考慮進去，並且注意到在動畫中，polygonal mesh 會根據骨架的姿勢變形，在比對畫的兩個 frames 的接近程度時，這是一個考量因素，因此，作者想出根據骨骼驅動的 cloud point ，來測量兩個 frame 之間的距離。

要取得兩個 point cloud 之間的距離 $D(A_i, B_j)$，可以透過計算 $A_i$ 與 $B_j$ 在 point cloud 的對應點 $p_i$ 和 $p'_i$ 之間的距離平方和得到。公式中透過 linear transformation $T_\theta$ 將 p 點旋轉沿 $y$ 軸 $\theta$ 度，然後平移至 $(x_0, z_0)$。當 index 超過 point cloud 裡的所有點時。可以增加某些關節的權重($w_i$)。

<font color="red">$$ \underset{\theta, x_0, z_0} {min} {\underset{i} \sum w_i || P_i - {T_{\theta, x_0, z_0}P'_i} ||^2} \tag1 $$</font>

==這邊這行公式所要表達的，就是將 $B_j$ 的對應點 $p'$ 做 translation 和 rotation 到 $A_i$ 的對應點 $p$ 的位置上，使兩個 motion 重疊，再將兩個 motion 做比較。==

<center>


</center>

<font color="red">上圖是兩個 motion 做 error function 後，對應到 point cloud 的結果，黑色部分為 error 較高者；白色部分為 error 較低者；綠色點為 local minima。</font>

### 3.2 Selecting Transition Points
上述公式中算出來的最小值，並不一定是最好的 transition motion，這個值僅代表其比其鄰居有更好的 transition motion。我們可以設定閾值，並選取與 local minima 誤差最小的值。

### 3.3 Creating Transitions

如果 $D(A_i, B_j)$ 求出的值滿足閾值要求，通過將 $A_i$ 到 $A_{i + k - 1}$ 的 frame 與 $B_j$ 到 $B_{j - k + 1}$ 的 frame 做混和來建出 transition motion。

~~第一步是對 motion B 進行適當的 aligning 2D transformation，然後在 transition motion 的第 p 幀線性內插(linear interpolation) root position 並對 joint rotation 做球面線性內插 (spherical linear interpolation)：~~ $$R_p = \alpha(p)R_{A_{i+p}} + [1 - \alpha(p)]R_{B_{j - k + 1 + p}} \tag5$$

==這邊這行公式要表達的其實是，為了將兩個 motion 連接在一起，中間的 transition 勢必要透過做線性內插來得到，而在這段 transition 中，每一個 frame 對 $A$ 和 $B$ 會有不同的權重，較靠近 motion $A$ 的 frame 對 $A$ 的權重會較重，反之，較靠近 motion $B$ 的 frame 對 $B$ 的權重會較重。==

<font color="blue">也就是說，在靠近 frame $A$ 的 motion 會跟 frame $A$ 比較接近，而比較靠近 frame $B$ 的 motion 會跟 frame $B$ 較接近。</font> $$q^i_p = slerp(q^i_{A_{i + p}}, q^i_{B_{j-k+1+p}}, \alpha(p)) \tag6 $$

為了保持連續性，會根據以下條件選擇混和權重：$$\alpha(p) = 1 \ for \ p \leq -1, \\ \alpha(p) = 0 \ for \ p \geq k, \\ \alpha(p) = 2(\frac{p+1}{k})^3 - 3(\frac{p+1}{k})^2 + 1, \ -1 < p < k \tag7$$

使用線性混和可能會違反原本 motion 的 constraint，例如本應該被固定的，卻出現角色的腳有滑動的狀況，這時可以透過原始 motion 的 constraint 進行調整。

### 3.4 Pruning The Graph
在目前階段生成的圖，有可能遇到像 dead ends(如下圖 Node 5) 或 sink (如下圖 Node 4) 等，會造成生成出來的 motion graph 有錯誤的情況。

<center>


</center>

為了解決這個問題，<font color="red">可以利用計算 strongly connected components(SCC)，以消除除了上述所提到的兩種 node 外，以及沒有 edge 的 nodes</font>。以上圖為例結果如下：

<center>


</center>

## 4. Extracting Motion
~~到此已經完成的 motion graph 的建構，接著要來提到的問題是將 graph walk 轉換成 displayable motion。~~

### ~~4.1 Converting Graph Walks To Motion~~
~~由於每一個 edge 都是一段 motion，所以我們只要將 graph walk 的每個片段，對應到 motion 就好。因此，會遇到的唯一問題就是，如何將每個片段放置到正確的位置及方向。換句話說，我們需要將每一個 frame 都做一次 2D rigid transformatiom。~~

~~如同 3.3 節所述，若使用線性混和來創建 transition，會產生 artifact 的狀況，然而每個 graph walk 都有 constraint，可能來自於原始數據，或者是於 3.3 節中所生成的，取決於該 frame 是 original data 或 transition。~~

### ~~4.2 Searching For Motion~~
現在我們要考慮的問題是如何找到 user 指定要的 motion。作者將此問題轉變成一個搜尋問題，user 給定一個 scalar function $g(w,e)$，用來計算當增加 edge $e$ 到現有路徑後，該路徑與 user 所指定的路徑間的誤差值。$$f(w) = f([e_1, ... , e_n]) = \sum_{i = 1}^{n} g([e_1, ... , e_{i -1}], e_i) \tag 8$$

~~$w$ 由 edges 組成，因 $g(w, e)$ 非負，故不能通過增加 edges 來減少 error。除了 $f$ 和 $g$ 外，user 也須提供一個停止條件，指示何時不應將額外的 edge 加入進 graph walk。當滿足停止條件時，即為完成圖。要找出 f 為最小值的完成圖，其中一個方法是利用 DFS，然而可能的 graph walk 數量，會隨著 graph walk 的平均大小成指數增長。為了解決這個問題，作者使用 branch and bound 來剔除不可能為最小值的 branch。~~

==這邊舉個例子，延續上圖，假設從 node 6 出發，做 DFS ，我們可以先得到一個 6 -> 7 -> 8 -> 3 -> 1 -> 2 的結果，此時可以得到一個誤差值，若此誤差值並非最小值，則從最後一個 node 開始剔除，並加入其他的 node ，因這邊只有一種結果，故只要從最後一個 node 開始一步步做剔除，即可得到最適合的那個 motion sequence。==

~~### 4.3 Deciding What To Ask For
當給定起始 node $N$ 及目標 edge $e$，要求找適合的 graph walk，使得 tranformation $T$ 接近 $T'$，有可能得出如下圖的結果。~~

<!-- <center>


</center> -->

~~這裡可以發現有兩個問題：~~

~~1. 對於中間的 motion 並沒有給出相關的指示
2. 結果可能比原先所需的更加具體~~

~~因此，可以得出兩個重要訊息：~~

~~1. $g$ 應該在整個 motion 中提供某種指示，因為任意的 motion 是不應該被允許的
2. $g$ 不應該限制的比必要條件還多，然而要注意一點，要與過度阻止考慮所有可能選項作平衡~~

## ~~5. Path Synthesis~~
~~到此，motion extraction 將轉變成一個優化問題。~~

### ~~5.1 Implementing Path Synthesis~~
~~在這節，唯一的任務就是定義 error function $g(w,e)$ 和適當的停止條件。這裡基本上就是計算角色在 graph walk 上實際經過的路徑 $P'$ 並計算與給定路徑 $P$ 之間的不同。最簡單判斷 $P'$ 的方法是將每一幀的 root 投影到地上，形成分段線性曲線。~~

~~設定 $P(s)$ 為 $P$ 上自 $P$ 點起，弧長距離為 $s$ 的點。$w_i$ 為第 $i^{th}$ 幀，自 $P'$ 算起，距離弧長 $s(w_i)$ 處。將在 $P$ 上有相同弧長的相對應點 $P(s(w_i))$。對於第 $j^{th}$ 幀的 $e$，作者計算了 $P'(s(e_j))$ 與 $P(s(e_j))$ 距離的平方。$g(w, e)$ 即為這些 errors 的總和：~~

<!-- $$g(w, e) = \sum^{n}_{i = 1} ||P' (s(e_i)) - P(s(e_i))||^2 \tag 9$$ -->

~~而停止條件是當前 $P'$ 的總長度達到或超過 $P$ 的總長度時。圖上任何以大於 $P$ 總長度的弧長行走的幀都映射到 $P$ 上的最後一個點。~~

### ~~5.2 Results~~

### ~~5.3 Applications Of Path Synthesis~~

## 6. Discussion
本篇論文提出一個 framework，將捕捉到的 motion data，加入新建置的 transition motion，最終生成出新的逼真、可控的 motion。本篇論文的方法可以自動構建一個 graph，這個 graph 將 database 中，所有 motion 連接起來，並且在這個 graph 中，尋找 user 所需要的 motion。

---

這作者集該實驗室發表了一系列跟 Motion 相關的論文，從 [Retargeting Motion to New Characters](https://dl.acm.org/doi/10.1145/280814.280820) 到前面提到的 [Motion Path Editing](https://dl.acm.org/doi/10.1145/364338.364400)，和 [Footskate Cleanup for Motion Capture Editing](https://dl.acm.org/doi/10.1145/545261.545277)，再到這篇，以及之後的 [Flexible Automatic Motion Blending with Registration Curves](https://dl.acm.org/doi/10.5555/846276.846307)、[Automated Extraction and Parameterization of Motions in Large Data Sets](https://dl.acm.org/doi/10.1145/1015706.1015760)、[Parametric Motion Graphs](https://dl.acm.org/doi/10.1145/1230100.1230123) 皆是與 Human Motion 相關的一系列主題論文，也是這次我們 Paper Presentation 主要報告的幾篇論文。更是我們第一個 [Project](https://hackmd.io/gB4yJHKDQY2mqdv0_NYgNQ) 的題目及演算法的重要依據。

<font color=white>另外同實驗室還有另外一篇不得不提的跟 Motion 有關的論文，就是這篇 [Group Motion Graphs](https://dl.acm.org/doi/10.1145/1073368.1073409)，為什麼特別提這篇呢？是什麼神作嗎？是不是神作我不清楚，主要是因為這篇是賴教授大大寫的論文啊(指導教授的論文，想拜讀一下，但...有點沒時間啊)，對，沒錯，就只是因為這個理由。</font>