基於關鍵幀的卡通角色輪廓跟蹤方法

2023-06-27 21:53:46 2

專利名稱：基於關鍵幀的卡通角色輪廓跟蹤方法
技術領域：
本發明涉及一種基於關鍵幀的從卡通角色運動序列中跟蹤角色輪廓的方法，屬於計算機二維動畫領域。

背景技術：
傳統卡通動畫的製作通常是比較耗費時間和勞力的。隨著傳統卡通動畫被廣泛地應用於各個領域，大量的現成卡通動畫素材可以被重用。通過重用已有的卡通素材，可以在一定程度上降低卡通動畫製作的複雜程度，進而提高卡通動畫製作的效率。
卡通角色運動捕獲與重定向是重用已有卡通素材的方式之一。這種重用方式通過從一段已有的卡通動畫序列中提取卡通角色的運動風格，然後將這種運動風格賦予一個新的卡通角色，生成一段新的運動序列。比如2002年在SIGGRAPH會議上發表的文章《Turning to the MastersMotion CapturingCartoons》就是採用這種方式重用已有的卡通素材。在該文章中，給定一段卡通角色的運動序列，從中人為地指定卡通角色的關鍵幀，角色的運動風格被抽象成各部位的仿射形變係數和關鍵幀的插值係數；然後，用戶提供一組與指定的關鍵幀在姿態上相似的新角色的關鍵幀，將相應的係數應用到新角色的關鍵幀得到一段新的運動序列。採用這種方式重用卡通素材的一個主要困難是從卡通角色的運動序列中捕獲角色的運動。該文採用的卡通角色運動捕獲方法，首先將角色分解為多個部位，然後通過一種基於區域的跟蹤方法確定各個部位的仿射形變係數，最後利用仿射形變係數確定關鍵幀的插值係數。該捕獲方法對角色的各個部位分別進行跟蹤，而沒有利用角色的整體結構以及各個部位在運動序列上的約束信息，跟蹤得到的結果往往不夠魯棒。在2002年的PacificConference on Computer Graphics and Applications上發表的文章《Cartoon MotionCapture by Shape Matching》提出了一種基於形狀匹配的卡通角色運動捕獲方法。該方法通過分析卡通角色的輪廓在運動序列上發生的形變來獲取角色的運動風格。首先，在每一幀中的角色外輪廓上採樣一些點，然後利用魯棒點匹配的方法建立兩個不同幀上輪廓採樣點之間的對應，進而根據建立的輪廓點對應確定兩個不同幀上的角色輪廓之間的形變係數。為了應用該方法，必須事先將卡通角色從該運動序列中分割出來；而且，當某些部位在運動序列的某些幀中被遮擋時，該方法將會出錯。
輪廓跟蹤可以作為捕獲卡通角色運動的一種手段。輪廓跟蹤將輪廓用其上的一些輪廓點來表示，通過跟蹤確定這些輪廓點在整個運動序列上的位置。由於跟蹤得到的不同幀中的輪廓點間的對應已經建立，可以用於分析卡通角色的各個部位在不同幀之間發生的形變。在2004年的SIGGRAPH會議上發表的文章《Keyframe-Based Tracking for Rotoscoping and Animation》提出了一種基於關鍵幀的從普通視頻序列中跟蹤曲線的方法。該方法將要跟蹤的曲線建模成由其上的離散點作為控制點的三次貝塞爾曲線。首先，在關鍵幀上標註跟蹤曲線的控制點，根據關鍵幀上的標註，構建一個最優化模型，通過求解該最優化模型確定各個控制點在其他幀中的位置。因為卡通運動序列中，兩幀相鄰幀之間的變化比較大，加上角色部位的輪廓在運動過程中常會發生較大的形變，而該方法假設跟蹤的曲線在相鄰兩幀之間的變化比較小，並不適合在卡通運動序列上跟蹤角色的輪廓曲線。


發明內容
本發明的目的是克服現有技術的不足，提供一種基於關鍵幀的卡通角色輪廓跟蹤方法。
基於關鍵幀的卡通角色輪廓跟蹤方法包括如下步驟 1)從一段卡通運動序列中選出關鍵幀，兩個相鄰關鍵幀之間的幀序列構成一個運動子序列； 2)對於每個運動子序列，分別在第一幀和最後一幀上的角色各個部位的輪廓上設置關鍵點，將相鄰的兩個關鍵點用直線進行連接，每個部位被表示成一個多邊形，第一幀和最後一幀上設置的關鍵點數目相同並且一一對應，第一幀上標註的輪廓被複製到該子序列上除最後一幀以外的其他幀上； 3)對每個運動子序列，構建一個以該子序列上的所有關鍵點為優化變量的包含時序約束和空間約束的優化模型； 4)將上述優化模型轉化成

的非線性最小二乘問題，採用阻尼最小二乘法進行求解，在求解得到子序列的中間幀上各個關鍵點的位置後，將每幀上的相鄰關鍵點用線段連接，得到角色的輪廓。
所述的對每個運動子序列，構建一個以該子序列上的關鍵點集合為變量的包含時序約束和空間約束的優化模型對每兩個相鄰關鍵幀之間的運動子序列構造一個目標函數E，該目標函數包括6個約束項，其中前4項是時序約束項，後2項是空間約束項 E＝wLEL+wAEA+wSES+wVEV+wEEE+wRER1 其中wL，wA，wS，wV，wE和wR分別為各項的權重係數，下面依次介紹各項的定義及作用； 第1約束項為長度項EL，該項反映了角色輪廓上的各條線段在運動子序列上的長度變化， 其中si(j)為第i幀中的角色輪廓上的第j條線段，Nf為運動子序列的幀數，Ns為角色輪廓上線段的數目； 第2約束項為角度項EA，該項反映了角色輪廓上的各個關鍵點處的夾角在運動子序列上的變化， 其中ci(j)為第i幀上中角色輪廓上的第j個關鍵點，Nc表示角色輪廓上關鍵點的數目； 第3約束項為面積項ES，該項反映了角色的各個部位在運動子序列上的面積變化， 其中pi(j)為第i幀中表示角色第j個部位的多邊形，fS是計算多邊形面積的函數，Np為角色部位的數目。
第4約束項為速度項EV，該項反映了角色輪廓上的各個關鍵點的在相鄰幀間的位置偏移量在運動子序列上的變化， 第5約束項為邊界項EE，該項使得角色的輪廓在運動子序列的每一幀上靠近圖像邊界，邊界項計算方法如下 首先對運動子序列中的每一幀圖像Fi採用坎尼邊界檢測算法提取圖像邊界，得到圖像邊界圖Ei；接著，對每一幅圖像邊界圖Ei計算歐式距離變換，得到一個H×W的距離變換矩陣Di，其中H和W為圖像的高度和寬度，Di(x，y)表示圖像坐標為(x，y)的像素點在Ei中離最近邊界像素點的歐式距離；然後，利用距離變換定義角色輪廓上的線段到圖像邊界的距離。在每一條線段si(j)上等間隔採樣t個像素點，設它們的圖像坐標為{(xk，yk)|1≤k≤t}，使用下面公式進行計算線段到圖像邊界的距離 最後，邊界項被定義為 第6約束項為區域項ER，該項使得在運動子序列的每一幀中，角色的各個部位落在正確的圖像區域，區域項的計算方法如下 首先，利用關鍵幀上的標註，跟蹤出角色的每個部位在中間幀上的大致位置根據兩個關鍵幀上標註的部位p1(j)和

使用線性插值得到卡通角色的第j個部位在第i幀上的大致形狀，記為pi′(j)，採用仿射填充算法利用p1(j)的紋理為pi′(j)填充顏色；通過計算pi′(j)各個頂點坐標的平均值得到pi′(j)的中心cpi′(j)，在以cpi′(j)為中心的搜索窗口裡定位cpi′(j)在第i幀上的最佳位置cpi*(j)，使得將部位pi′(j)的中心cpi′(j)平移到cpi*(j)後，部位pi′(j)與其所在的圖像區域的顏色差異最小； 接著，對第i幀上表示角色第j個部位的多邊形pi(j)，通過計算它的各個頂點坐標的平均值得到該部位的中心cpi(j)； 最後，使用下面的公式定義區域項 所述的採用仿射填充算法利用p1(j)的紋理為pi′(j)填充顏色步驟包括 1)將多邊形p1(j)和pi′(j)分別表示成2×M的矩陣A和B，其中A的第k列和B的第k列分別表示p1(j)和pi′(j)的第k個頂點的圖像坐標； 2)採用線性最小二乘法最小化下面的式子來計算多邊形pi′(j)到多邊形p1(j)的仿射變換AT 3)對多邊形pi′(j)內的每一個像素點px′，px′的坐標表示成

的形式，通過下式計算得到一個像素點px 如果px的坐標位置在多邊形p1(j)內部，則將多邊形p1(j)上位於該坐標位置的像素點的顏色賦值給px′； 4)對於多邊形pi′(j)內每個還未著色的像素點，選擇與其距離最近的已著色的像素點的顏色作為它的顏色值。
本發明具有的有益的效果是利用在一段卡通角色的運動序列的關鍵幀上標註的輪廓，構建一個包含時序約束和空間約束的優化模型，然後將該優化模型轉化成非線性最小二乘問題，採用阻尼最小二乘法進行求解，可以比較準確並快速地確定角色輪廓在運動序列的其他幀上的位置。利用輪廓跟蹤捕獲卡通角色的運動，由於各個部位的在不同幀上的輪廓之間的對應可以從跟蹤結果中直接得到，避免了輪廓匹配。



圖1是本發明在一段卡通角色運動序列上的標註的角色輪廓示意圖； 圖2是本發明定義的線段到圖像邊界的距離計算方式示意圖； 圖3是本發明在一段卡通角色運動序列上跟蹤角色上臂部位的結果示意圖； 圖4是本發明定義的區域項的工作原理示意圖； 圖5是本發明在一段卡通角色運動序列上跟蹤角色輪廓的結果示意圖。

具體實施例方式 本發明提出的卡通角色輪廓跟蹤方法，首先在卡通角色的運動序列的關鍵幀上標註角色的輪廓，根據關鍵幀上的標註構建一個優化模型，通過求解該優化模型自動跟蹤出卡通角色的輪廓在運動序列的其他幀上的位置。由於傳統卡通動畫片都是以較低的幀率製作的，卡通角色的輪廓在相鄰兩幀之間的變化比較大；而且，卡通角色的部位在運動過程中往往會發生比較誇張的形變。該優化模型有效地利用了時序約束和空間約束，可以較準確地從卡通角色運動序列中跟蹤出角色的輪廓。
下面結合從一段孫悟空這個卡通角色的長度為15幀的運動序列中跟蹤角色輪廓的實施例子介紹本發明的具體技術方案和實施步驟 (1)從輸入的一段卡通運動序列中選出關鍵幀，並將兩個相鄰關鍵幀之間的幀序列組成一個運動子序列；在圖1給出的孫悟空這個角色的一個長度為15幀的運動序列中，第1幀和第15幀被選為關鍵幀； (2)對於每個運動子序列，分別在第一幀和最後一幀上的角色各個部位的輪廓上設置關鍵點，將相鄰的兩個關鍵點用直線進行連接，每個部位被表示成一個多邊形，第一幀和最後一幀上設置的關鍵點數目相同並且一一對應，第一幀上標註的輪廓被複製到該子序列上除最後一幀以外的其他幀上；圖1給出了一個在運動子序列的標註輪廓的示例，紅圈為關鍵點，藍線構成角色的輪廓； (3)對每個運動子序列，構建一個以該子序列上的所有關鍵點為優化變量的包含時序約束和空間約束的優化模型。也就是，對運動子序列構造一個目標函數E，該目標函數包括6個約束項，其中前4項是時序約束項，後2項是空間約束項 E＝wLEL+wAEA+wSES+wVEV+wEEE+wRER1 其中wL，wA，wS，wV，wE和wR分別為各項的權重係數；在這個實施例中，這些參數被依次設置為8，9，3，4，4和32，下面依次介紹各項的定義及作用； 第1約束項為長度項EL，該項反映了角色輪廓上的各條線段在運動子序列上的長度變化， 其中si(j)為第i幀中的角色輪廓上的第j條線段，Nf為運動子序列的幀數，Ns為角色輪廓上線段的數目； 第2約束項為角度項EA，該項反映了角色輪廓上的各個關鍵點處的夾角在運動子序列上的變化， 其中ci(j)為第i幀上中角色輪廓上的第j個關鍵點，Nc表示角色輪廓上關鍵點的數目； 第3約束項為面積項ES，該項反映了角色的各個部位在運動子序列上的面積變化， 其中pi(j)為第i幀中表示角色第j個部位的多邊形，fS是計算多邊形面積的函數，Np為角色部位的數目。
第4約束項為速度項EV，該項反映了角色輪廓上的各個關鍵點的在相鄰幀間的位置偏移量在運動子序列上的變化， 第5約束項為邊界項EE，該項使得角色的輪廓在運動子序列的每一幀上靠近圖像邊界，邊界項計算方法如下 首先對運動子序列中的每一幀圖像Fi採用坎尼邊界檢測算法提取圖像邊界，得到圖像邊界圖Ei；接著，對每一幅圖像邊界圖Ei計算歐式距離變換，得到一個H×W的距離變換矩陣Di，其中H和W為圖像的高度和寬度，Di(x，y)表示圖像坐標為(x，y)的像素點在Ei中離最近邊界像素點的歐式距離；然後，利用距離變換定義角色輪廓上的線段到圖像邊界的距離。在每一條線段si(j)上等間隔採樣t個像素點，設它們的圖像坐標為{(xk，yk)|1≤k≤t}，使用下面的公式計算線段到圖像邊界的距離 通常情況下，t的取值對結果影響不大，考慮到計算效率，可以取一個相對較小一些的值，比如5到10之間，在這個實施例子中t的取值為7。圖2給出了線段到圖像邊界的距離計算方式的示意，其中圖2(a)為圖像邊界圖，圖2(b)示意的是線段到邊界距離，綠線表示線段，紅圈為從線段上採樣的像素點，黃線段表示的是採樣像素點到圖像邊界的最小距離。最後，邊界項被定義為 第6約束項為區域項ER，該項使得在運動子序列的每一幀中，角色的各個部位落在正確的圖像區域，區域項的計算方法如下 首先，利用關鍵幀上的標註，跟蹤出角色的每個部位在中間幀上的大致位置。根據在兩個關鍵幀上標註的部位p1(j)和

使用線性插值得到卡通角色的第j個部位在第i幀上的大致形狀，記為pi′(j)，採用仿射填充算法根據p1(j)的紋理為pi′(j)填充顏色；通過計算pi′(j)各個頂點坐標的平均值得到pi′(j)的中心cpi′(j)，在以cpi′(j)為中心的一個搜索窗口裡定位cpi′(j)在第i幀上的最佳位置cpi*(j)，使得將部位pi′(j)的中心cpi′(j)平移到cpi*(j)後，部位pi′(j)與其所在的圖像區域的顏色差異最小；圖3給出了跟蹤得到的孫悟空這個角色的右上臂在運動序列的各個幀上的大致位置，綠圈表示部位的中心； 接著，對第i幀上表示角色第j個部位的多邊形pi(j)，通過計算它的各個頂點坐標的平均值得到該部位的中心cpi(j)，並使用下面的公式定義區域項 圖4示意的是區域項的作用原理。在圖4(a)中，黃色圓圈表示角色左手掌中心的最佳位置，藍色正方形為左手掌當前的中心位置；在圖4(b)中，在區域項的作用下，左手掌的中心位置不斷靠近其最佳位置，最終重合使得表示左手掌的曲線靠近到它在圖像中的正確位置； 所述的利用p1(j)的紋理為pi′(j)填充顏色的仿射填充算法步驟包括 1.將多邊形p1(j)和pi′(j)分別表示成2×M的矩陣A和B，其中A的第k列和B的第k列分別表示p1(j)和pi′(j)的第k個頂點的圖像坐標； 2.採用線性最小二乘法最小化下面的式子來計算多邊形pi′(j)到多邊形p1(j)的仿射變換AT 3.對多邊形pi′(j)內的每一個像素點px′，px′的坐標表示成

的形式，通過下式計算得到一個像素點px 如果px的坐標位置在多邊形p1(j)內部，則將多邊形p1(j)上位於該坐標位置的像素點的顏色賦值給px′； 4.對於多邊形pi′(j)內每個還未著色的像素點，選擇與其距離最近的已著色的像素點的顏色作為它的顏色值。
(4)將上述優化模型轉化成

的非線性最小二乘問題的形式，採用阻尼最小二乘法進行求解，得到首幀標註的角色輪廓上的關鍵點在子序列的各個中間幀上的位置後，將每幀上的相鄰關鍵點用線段連接，得到角色的輪廓。圖5給出了這個實施例的輪廓跟蹤的結果。
權利要求
1.一種基於關鍵幀的卡通角色輪廓跟蹤方法，其特徵在於包括如下步驟
1)從一段卡通運動序列中選出關鍵幀，兩個相鄰關鍵幀之間的幀序列構成一個運動子序列；
2)對於每個運動子序列，分別在第一幀和最後一幀上的角色各個部位的輪廓上設置關鍵點，將相鄰的兩個關鍵點用直線進行連接，每個部位被表示成一個多邊形，第一幀和最後一幀上設置的關鍵點數目相同並且一一對應，第一幀上標註的輪廓被複製到該子序列上除最後一幀以外的其他幀上；
3)對每個運動子序列，構建一個以子序列上的所有關鍵點為優化變量的包含時序約束和空間約束的優化模型；
4)將上述優化模型轉化成
的非線性最小二乘問題，採用阻尼最小二乘法進行求解，在求解得到子序列的中間幀上各個關鍵點的位置後，將每幀上的相鄰關鍵點用線段連接，得到角色的輪廓。
2.根據權利要求1所述的一種基於關鍵幀的卡通角色輪廓跟蹤方法，其特徵在於，所述的對每個運動子序列，構建一個以該子序列上的關鍵點集合為變量的包含時序約束和空間約束的優化模型對每兩個相鄰關鍵幀之間的運動子序列構造一個目標函數E，該目標函數包括6個約束項，其中前4項是時序約束項，後2項是空間約束項
E＝wLEL+wAEA+wSES+wVEV+wEEE+wRER1
其中wL，wA，wS，wV，wE和wR分別為各項的權重係數，下面依次介紹各項的定義及作用；
第1約束項為長度項EL，該項反映了角色輪廓上的各條線段在運動子序列上的長度變化，
其中si(j)為第i幀中的角色輪廓上的第j條線段，Nf為運動子序列的幀數，Ns為角色輪廓上線段的數目；
第2約束項為角度項EA，該項反映了角色輪廓上的各個關鍵點處的夾角在運動子序列上的變化，
其中ci(j)為第i幀上中角色輪廓上的第j個關鍵點，Nc表示角色輪廓上關鍵點的數目；
第3約束項為面積項ES，該項反映了角色的各個部位在運動子序列上的面積變化，
其中pi(j)為第i幀中表示角色第j個部位的多邊形，fS是計算多邊形面積的函數，Np為角色部位的數目。
第4約束項為速度項EV，該項反映了角色輪廓上的各個關鍵點的在相鄰幀間的位置偏移量在運動子序列上的變化，
第5約束項為邊界項EE，該項使得角色的輪廓在運動子序列的每一幀上靠近圖像邊界，邊界項計算方法如下
首先對運動子序列中的每一幀圖像Fi採用坎尼邊界檢測算法提取圖像邊界，得到圖像邊界圖Ei；接著，對每一幅圖像邊界圖Ei計算歐式距離變換，得到一個H×W的距離變換矩陣Di，其中H和W為圖像的高度和寬度，Di(x，y)表示圖像坐標為(x，y)的像素點在Ei中離最近邊界像素點的歐式距離；然後，利用距離變換定義角色輪廓上的線段到圖像邊界的距離。在每一條線段si(j)上等間隔採樣t個像素點，設它們的圖像坐標為{(xk，yk)|1≤k≤t}，使用下面公式進行計算線段到圖像邊界的距離
最後，邊界項被定義為
第6約束項為區域項ER，該項使得在運動子序列的每一幀中，角色的各個部位落在正確的圖像區域，區域項的計算方法如下
首先，利用關鍵幀上的標註，跟蹤出角色的每個部位在中間幀上的大致位置根據兩個關鍵幀上標註的部位p1(j)和
使用線性插值得到卡通角色的第j個部位在第i幀上的大致形狀，記為pi′(j)，採用仿射填充算法利用p1(j)的紋理為pi′(j)填充顏色；通過計算pi′(j)各個頂點坐標的平均值得到pi′(j)的中心cpi′(j)，在以cpi′(j)為中心的搜索窗口裡定位cpi′(j)在第i幀上的最佳位置cpi*(j)，使得將部位pi′(j)的中心cpi′(j)平移到cpi*(j)後，部位pi′(j)與其所在的圖像區域的顏色差異最小；
接著，對第i幀上表示角色第j個部位的多邊形pi(j)，通過計算它的各個頂點坐標的平均值得到該部位的中心cpi(j)，並使用下面的公式定義區域項
3.根據權利要求2所述的一種基於關鍵幀的卡通角色輪廓跟蹤方法，其特徵在於，所述的採用仿射填充算法利用p1(j)的紋理為pi′(j)填充顏色步驟包括
1)將多邊形p1(j)和pi′(j)分別表示成2×M的矩陣A和B，其中A的第k列和B的第k列分別表示p1(j)和pi′(j)的第k個頂點的圖像坐標；
2)採用線性最小二乘法最小化下面的式子來計算多邊形pi′(j)到多邊形p1(j)的仿射變換AT
3)對多邊形pi′(j)內的每一個像素點px′，px′的坐標表示成
的形式，通過下式計算得到一個像素點px
如果px的坐標位置在多邊形p1(j)內部，則將多邊形p1(j)上位於該坐標位置的像素點的顏色賦值給px′；
4)對於多邊形pi′(j)內每個還未著色的像素點，選擇與其距離最近的已著色的像素點的顏色作為它的顏色值。
全文摘要
本發明公開了一種基於關鍵幀的卡通角色輪廓跟蹤方法。首先，人為地從一段卡通角色的運動序列中選出關鍵幀，在各個關鍵幀上用曲線畫出卡通角色的輪廓；然後，利用關鍵幀上標註的輪廓信息，構建一個優化模型；最後，將該優化模型轉化成非線性最小二乘問題進行求解，跟蹤出卡通角色的輪廓在運動序列的其他幀上的位置。本方法有效地利用了時序和空間上的約束信息，可以比較精確地從一段運動序列中跟蹤出卡通角色的輪廓；利用輪廓跟蹤方法捕獲得到的卡通角色在運動序列上各個部位的輪廓，可以用於分析這個角色在該段運動序列上各個部位發生的形變。
文檔編號G06T7/20GK101799927SQ20101013118
公開日2010年8月11日 申請日期2010年3月23日 優先權日2010年3月23日
發明者肖俊, 周春鑾, 莊越挺 申請人:浙江大學