)
1. 三種像不像的答案手勢軌跡匹配在比什么去年幫一個做教學(xué)演示的朋友搭手勢控制的小程序需求很樸素用戶在畫布上用鼠標(biāo)畫一筆系統(tǒng)判斷這是圓圈橫線勾閃電中的哪一種然后觸發(fā)對應(yīng)動作。他一開始想上深度學(xué)習(xí)我看了一眼他手頭的數(shù)據(jù)量——八類手勢每類他自己畫了五遍總共四十條軌跡——這個規(guī)模上神經(jīng)網(wǎng)絡(luò)純屬自找麻煩。傳統(tǒng)模板匹配在這個場景下反而更合適樣本極少、要求可解釋、還要在界面上把為什么認(rèn)為是這個手勢畫出來給人看這三條正好是距離度量類算法的主場。這篇文章要拆的就是圍繞DTW動態(tài)時間規(guī)整、Fréchet 距離弗雷歇距離和Hausdorff 距離豪斯多夫距離這三種軌跡相似度度量配一套 Matlab 的圖形界面把畫一筆、比一比、給結(jié)論這條鏈路走通的完整過程。關(guān)鍵詞我攤開說手勢識別、軌跡相似度、DTW、離散Fréchet、Hausdorff、Matlab GUI、最近鄰分類、軌跡重采樣歸一化。適合誰看手上有幾十條到幾百條軌跡樣本、想快速做出一個能演示能解釋的原型的人以及正在做課程設(shè)計、需要把算法原理和界面都講清楚的人。有 Matlab 基礎(chǔ)就能跟著跑沒做過軌跡匹配也能看懂思路因為我會把每一種距離到底在比什么用生活化的例子說透。1.1 同一個手勢畫三遍三條曲線差在哪先把問題本身看清楚了才知道為什么需要三種不同的尺子。假設(shè)你讓同一個人連著畫三個圓圈把鼠標(biāo)采樣點連起來會看到三種典型差異。第一種是速度差異。第一遍畫得快采樣點稀疏六十多個點第三遍手慢還中間頓了一下一百二十個點。兩條曲線的形狀幾乎一樣但點數(shù)差一倍逐點對齊算歐氏距離會產(chǎn)生巨大誤差——這就是 DTW 要解決的問題它允許時間軸上的非線性拉伸。第二種是起筆和收筆的位置偏差。同一個人畫圓起點有時在正上方有時在左上角終點也因此偏移。兩條曲線整體形狀高度一致但端點對不上。Hausdorff 距離完全不在乎這個因為它只問這條曲線上的每個點到另一條曲線上最近點的距離最大值是多少點的先后順序它根本不看。第三種是整體走向的細(xì)微差別比如一個畫得偏扁、一個畫得偏圓中間還帶點抖動。這種走著走著偏了的差異正是 Fréchet 距離擅長捕捉的——它考慮的是沿著曲線前進(jìn)時最壞情況下的偏離程度。我在調(diào)試初期最大的教訓(xùn)是不要指望一種尺子解決所有問題。當(dāng)時我拿 DTW 去區(qū)分橫線和橫線加回勾準(zhǔn)確率怎么調(diào)都上不去后來換成 Fréchet 一眼就分開了。原因后面細(xì)說。1.2 DTW、離散 Fréchet、Hausdorff 的度量哲學(xué)這三者看著都是算兩條點序列的距離底層假設(shè)完全不同我用一張表把關(guān)鍵差異擺出來這張表我在項目里反復(fù)回看過很多次維度DTW離散 FréchetHausdorff是否關(guān)心點的先后順序關(guān)心且允許重復(fù)對應(yīng)關(guān)心且必須單調(diào)前進(jìn)完全不關(guān)心當(dāng)作點集對繪制速度差異的容忍度極強(qiáng)可任意拉伸中等單調(diào)但不跳躍無速度快慢不影響結(jié)果對離群點飛點中等會被攤到路徑上較敏感最大值直接放大極敏感一個飛點就毀掉單次計算復(fù)雜度O(NM)可加窗口優(yōu)化O(NM)不可加窗口O(NM)可高度向量化是否滿足三角不等式不滿足加窗口后更不滿足連續(xù)版滿足離散耦合版近似滿足是真度量典型翻車場景停頓、筆畫粗細(xì)導(dǎo)致的對齊病態(tài)采樣過稀時距離虛高起筆抖動的孤立點表里有一行值得單獨說Hausdorff 把軌跡當(dāng)點集完全丟棄順序信息。你把一個橫著的 C和一個反著寫的 ?放在一起Hausdorff 距離會告訴你它們一模一樣——因為兩組點的空間分布幾乎重合。這在很多場景下是優(yōu)點比如只關(guān)心圖形覆蓋范圍但在手勢識別里是硬傷因為從左往右畫橫和從右往左畫橫在交互語義上可能是兩個完全不同的指令。DTW 不滿足三角不等式這一點也經(jīng)常被忽略。這意味著你不能拿它做度量空間上的加速索引比如 BK 樹也別指望距離小就一定相似、距離大就一定不相似的嚴(yán)格保證。做幾十條模板的暴力最近鄰?fù)耆珱]問題想上十萬條就得掂量了。1.3 什么樣的項目適合用這套傳統(tǒng)方案我把這個話題單拎出來講是因為見過太多人在四十條樣本的項目上硬套神經(jīng)網(wǎng)絡(luò)最后花兩周調(diào)參得到一個還不如模板匹配的結(jié)果。小樣本、強(qiáng)可解釋、需要可視化中間過程這三條只要占了兩條傳統(tǒng)距離度量就是更優(yōu)解。手勢識別只是其中一個例子同樣的思路可以遷移到工業(yè)上的裝配軌跡比對、體育動作的規(guī)范度打分、醫(yī)療康復(fù)里的關(guān)節(jié)運動軌跡評估——這些場景共同點是樣本少、每個樣本維度低二維或三維點序列、結(jié)果要能指出哪里不像。反過來什么情況別用手勢類別超過五十種、每類樣本上千條、需要識別不同人的風(fēng)格泛化這時候模板匹配的準(zhǔn)確率上限會很明顯該上學(xué)習(xí)模型就上。我個人的經(jīng)驗閾值大致是每類樣本少于三十條、類別數(shù)少于二十模板匹配的性價比遠(yuǎn)高于訓(xùn)練模型。還有一點這套算法的中間結(jié)果DTW 的對齊路徑、Fréchet 的自由空間圖、Hausdorff 的最大偏離點都能直接畫在界面上。給非技術(shù)人員演示的時候你看系統(tǒng)認(rèn)為你畫的第三段和模板的第二段對上了這種解釋比一個 0.87 的置信度分?jǐn)?shù)有說服力得多。2. 從鼠標(biāo)軌跡到歸一化矩陣預(yù)處理決定了后面所有的上限這一章我放在算法之前是因為踩過的最深的坑幾乎全在預(yù)處理。有句話我特別認(rèn)同軌跡匹配的上限由預(yù)處理決定距離度量只是把這個上限兌現(xiàn)出來。我最初偷懶直接把鼠標(biāo)回調(diào)拿到的原始點丟給 DTW結(jié)果同一手勢畫兩遍的類內(nèi)距離比不同手勢的類間距離還大調(diào)了三天參數(shù)毫無進(jìn)展最后發(fā)現(xiàn)是重采樣沒做。2.1 采集環(huán)節(jié)事件回調(diào)拿到的點在抖什么Matlab 里用鼠標(biāo)在坐標(biāo)軸上畫線最常見的寫法是在 figure 上掛WindowButtonDownFcn、WindowButtonMotionFcn、WindowButtonUpFcn三個回調(diào)用get(ax,CurrentPoint)取當(dāng)前坐標(biāo)function onMouseDown(src, ~) cp get(ax, CurrentPoint); % 返回 2x3 矩陣 p cp(1, 1:2); % 取第一行的 x y if ~inAxes(ax, p), return; end app.pts p; app.drawing true; set(app.hLine, XData, p(1), YData, p(2)); end function onMouseMove(src, ~) if ~app.drawing, return; end cp get(ax, CurrentPoint); app.pts(end1, :) cp(1, 1:2); set(app.hLine, XData, app.pts(:,1), YData, app.pts(:,2)); drawnow limitrate; end function onMouseUp(src, ~) app.drawing false; runRecognize(app); end function ok inAxes(ax, p) xl get(ax, XLim); yl get(ax, YLim); ok p(1) xl(1) p(1) xl(2) ... p(2) yl(1) p(2) yl(2); end這里有幾個實際的坑。第一個是CurrentPoint返回的是2x3矩陣而不是 2 元素向量直接索引cp(1)cp(2)會取到錯誤的值必須cp(1,1:2)。第二個是WindowButtonMotionFcn的觸發(fā)頻率取決于系統(tǒng)事件隊列不同機(jī)器上每秒采到的點數(shù)可能差好幾倍這意味著原始點序列的時間采樣是不可靠的。第三個是鼠標(biāo)移動事件在快速劃動時會被合并相鄰兩點之間可能隔著幾十個像素曲線看起來是直的一段。還有一個隱蔽問題用戶在同一個位置輕微抖動時會連續(xù)產(chǎn)生一批幾乎重合的點。這些點如果不去掉后面的等距重采樣用的累計弧長會出現(xiàn)零長度段interp1會報警告甚至返回 NaN。2.2 去重、等距重采樣與累計弧長插值我的做法是兩步走先按最小距離去重再按累計弧長做等距重采樣。為什么要按弧長而不是按下標(biāo)因為下標(biāo)反映的是采到了第幾個點受采樣頻率影響弧長反映的是沿著曲線走了多遠(yuǎn)是曲線的內(nèi)在屬性。等距重采樣之后兩條用不同速度畫出來的曲線在幾何上就有了可比性。function P resampleGesture(pts, N) % 輸入 pts: M x 2 原始軌跡點 % 輸出 P : N x 2 等弧長重采樣后的軌跡 % 1) 去重相鄰點距離過小則丟棄 if size(pts, 1) 2 P repmat(pts(1,:), N, 1); return; end d sqrt(sum(diff(pts).^2, 2)); keep [true; d 1e-9]; pts pts(keep, :); if size(pts, 1) 2 P repmat(pts(1,:), N, 1); return; end % 2) 累計弧長 seg sqrt(sum(diff(pts).^2, 2)); cum [0; cumsum(seg)]; total cum(end); if total 1e-9 P repmat(pts(1,:), N, 1); return; end % 3) 等弧長插值 qi linspace(0, total, N); P [interp1(cum, pts(:,1), qi, linear), ... interp1(cum, pts(:,2), qi, linear)]; endN取多少合適我用的是64。理由有三一是在我的小樣本上32 點對回勾閃電這類帶細(xì)節(jié)的手勢明顯不夠拐角會被抹平128 點對分類準(zhǔn)確率的提升不到一個百分點但 DTW 的 O(N2) 計算量翻四倍實時繪制的界面會開始卡64 是拐點。如果你只做簡單幾何圖形48 就夠如果做手寫數(shù)字類的復(fù)雜軌跡96 更穩(wěn)妥。去重閾值我用的是相對值而不是絕對像素代碼里寫1e-9是因為坐標(biāo)已經(jīng)歸一化過了。如果還沒歸一化用畫布寬度的千分之一左右比如 400 像素寬的畫布用 0.4。2.3 平移、縮放、旋轉(zhuǎn)三個開關(guān)各自的代價歸一化這三件事每一件都是用了方便、用錯了丟信息得一個一個想清楚。平移幾乎無腦要做把質(zhì)心挪到原點。這樣用戶在畫布任何位置畫同一個手勢結(jié)果都一致。代碼就一行P P - mean(P,1)。縮放要謹(jǐn)慎選擇范數(shù)。常見兩種按包圍盒的最大邊長縮放到統(tǒng)一大小L∞ 范數(shù)或者按離質(zhì)心最遠(yuǎn)點的距離縮放L2 范數(shù)。function P scaleGesture(P, mode) switch mode case bbox % 按包圍盒 s max(max(P) - min(P)); case radius % 按半徑 s max(sqrt(sum(P.^2, 2))); otherwise s 1; end if s 1e-9, P P / s; end end兩種的差別在細(xì)長形狀上很明顯一條橫線用包圍盒歸一化會被拉到滿寬用半徑歸一化則會被壓得很短。我最后選了bbox因為對圓方三角這類閉合圖形包圍盒歸一化后的尺寸更一致。但這里有個所有人都該知道的反噬縮放歸一化之后畫一個大圓和畫一個小圓就變成了同一類。如果你的手勢語義里大小是有意義的比如畫大圈音量10畫小圈音量1那縮放就得關(guān)掉或者按面積分檔。旋轉(zhuǎn)歸一化是最有爭議的一個。經(jīng)典做法是用首筆點到質(zhì)心的方向作為指示角把整個軌跡旋轉(zhuǎn)到這個角朝上。這個技巧對箭頭勾這類有明確指向的手勢有效但對圓形、方形、Z 形就沒意義——一個圓你轉(zhuǎn)多少度都是同一個圓反而會因為起筆點位置不同引入額外方差。我的處理是把它做成界面上的一個復(fù)選框默認(rèn)關(guān)閉只在特定手勢集合上打開function P rotateToIndicative(P) c mean(P, 1); P P - c; theta atan2(P(1,2), P(1,1)); % 首點相對質(zhì)心的方向角 R [cos(-theta) -sin(-theta); sin(-theta) cos(-theta)]; P P * R; % 注意右乘轉(zhuǎn)置等于左乘 R end這段代碼里P * R這個寫法值得盯一下方向不能反。我見過有人在這一點上debug半天畫出來的軌跡越轉(zhuǎn)越歪。2.4 預(yù)處理順序錯了就白干順序我固定成去重 → 平移 → 等距重采樣 → 縮放 → 旋轉(zhuǎn)。每一處的相對位置都有理由不能隨便換。去重必須在重采樣之前因為累計弧長依賴嚴(yán)格遞增的cum向量有重復(fù)點會導(dǎo)致interp1報錯。平移放在重采樣之前還是之后理論上可以互換平移不改變弧長但放在前面代碼更好讀?？s放必須在重采樣之后因為重采樣是在原始坐標(biāo)系下按弧長分布取點先縮放會改變數(shù)值精度。旋轉(zhuǎn)放最后因為它依賴質(zhì)心而質(zhì)心在平移后就固定在原點了。有個我實際踩到的坑平移和縮放如果在重采樣之前做容易遇到坐標(biāo)數(shù)值過小導(dǎo)致浮點精度問題。原始畫布坐標(biāo)通常是幾百像素量級歸一化后變成 0.001 量級此時再去算兩點間的平方距離有效位數(shù)會掉。解決辦法是先按畫布尺寸整體縮放到 [-1,1] 附近再做后續(xù)處理。這一條在論文里基本不會寫但真實調(diào)試時會遇到。3. 三種距離的 Matlab 實現(xiàn)與參數(shù)取舍這一段是全文的技術(shù)核心。我把三種度量都寫成了獨立函數(shù)輸入輸出形狀一致輸入兩個 N x 2 矩陣輸出一個標(biāo)量距離這樣在分類器里可以直接換著調(diào)用方便對比。下面每一段都會強(qiáng)調(diào)一個容易被忽略的實現(xiàn)細(xì)節(jié)。3.1 DTW遞推式、窗口帶與路徑歸一化DTW 的遞推式不復(fù)雜構(gòu)造一個 N x M 的代價矩陣DD(i,j)表示 A 的前 i 個點和 B 的前 j 個點匹配的最小累計代價。轉(zhuǎn)移只有三個方向——豎著走A 前進(jìn)一格B 停住、橫著走A 停住B 前進(jìn)、斜著走兩者同時前進(jìn)。function [dist, D] dtwDistance(A, B, bandRatio) % A, B : N x 2 歸一化后的軌跡 % bandRatio : Sakoe-Chiba 帶寬比例0 表示不限制 % dist : 歸一化后的 DTW 距離 N size(A,1); M size(B,1); d pairDist(A, B); % N x M 局部代價矩陣 D inf(N, M); if bandRatio 0 band max(N, M); else band max(1, round(bandRatio * max(N, M))); end for i 1:N jlo max(1, i - band); jhi min(M, i band); for j jlo:jhi if i 1 j 1 D(i,j) d(i,j); continue; end c inf; if i 1, c min(c, D(i-1, j )); end if j 1, c min(c, D(i, j-1)); end if i 1 j 1, c min(c, D(i-1, j-1)); end D(i,j) d(i,j) c; end end dist D(N, M) / N; % 兩序列長度相同按步數(shù)歸一化 end function D pairDist(A, B) % 不依賴 Statistics 工具箱的兩兩歐氏距離 D2 sum(A.^2,2) sum(B.^2,2) - 2 * (A * B); D sqrt(max(D2, 0)); end第一個細(xì)節(jié)pairDist這個手寫函數(shù)。很多人第一反應(yīng)是pdist2但那需要 Statistics and Machine Learning Toolbox。給人演示的代碼依賴越少越好用矩陣乘法展開(a-b)2 a2 b2 - 2ab完全等價而且更快。max(D2, 0)那一步不能省——浮點誤差會讓理論上為 0 的值變成 -1e-17開方得到復(fù)數(shù)。第二個細(xì)節(jié)末尾除以 N。這一步太多人漏掉。DTW 的累計代價是沿著路徑一路加過來的路徑越長累加值越大。兩條各自 64 點的軌跡路徑長度大致就是 64不歸一化的話形狀類似但細(xì)節(jié)更多的模板天然吃虧。有人會用路徑長度做精確歸一化回溯統(tǒng)計實際步數(shù)但兩條等長序列的路徑長度差異很小除以 N 更省事且效果相當(dāng)。如果你處理的序列長度不等比如沒做等距重采樣就必須回溯算真實路徑長度了。第三個細(xì)節(jié)Sakoe-Chiba 帶寬。不加限制時DTW 會把形狀上完全不相干的部分強(qiáng)行對齊產(chǎn)生所謂的病態(tài)對齊——比如把橫線的整段都壓到一個點上。加帶寬后只允許對角線附近的匹配計算量從 N2 降到 2·N·band。我實測bandRatio 0.15時64x64 的匹配耗時從約 1.8ms 降到 0.6ms準(zhǔn)確率只掉了 2 個百分點。如果你的界面要實時給反饋這個折中是值得的。3.2 離散 Fréchet為什么多數(shù) Demo 算的其實不是幾何 FréchetFréchet 距離有個流傳最廣的解釋一個人牽著狗人沿曲線 A 走狗沿曲線 B 走兩者都用任意速度但都不能后退問最短需要多長的狗繩。這個比喻很好但離散版實現(xiàn)和連續(xù)版定義完全是兩回事這里必須講清楚否則你會在參數(shù)調(diào)優(yōu)時一頭霧水。連續(xù)的 Fréchet 距離定義中人和狗可以停在曲線上的任意一點所以計算時需要把點投影到線段上用點到線段的距離并用自由空間圖free space diagram判定可達(dá)性。而絕大多數(shù)代碼實現(xiàn)包括很多教學(xué)資料里給的用的是離散耦合 Fréchet只在采樣點上做單調(diào)匹配用點到點的距離function [dist, C] frechetDistance(A, B) % 離散耦合 Fréchet 距離點對點非點到線段 N size(A,1); M size(B,1); d pairDist(A, B); C inf(N, M); C(1,1) d(1,1); for i 2:N, C(i,1) max(C(i-1,1), d(i,1)); end for j 2:M, C(1,j) max(C(1,j-1), d(1,j)); end for i 2:N for j 2:M m min([C(i-1,j), C(i-1,j-1), C(i,j-1)]); C(i,j) max(m, d(i,j)); end end dist C(N,M); end三個轉(zhuǎn)移方向取min選擇最溫和的前進(jìn)方式再和當(dāng)前局部代價取max因為要保證最壞情況。這個 max-min 結(jié)構(gòu)和 DTW 的純求和完全不同也是為什么 Fréchet 更容易被單個壞點拉高。后果是什么離散耦合 Fréchet 的值依賴采樣密度。同一條曲線采 32 個點和采 128 個點算出來的距離不一樣——采樣越稀落到最近點上的概率越低距離越大。這在跨模板比較時不致命因為所有模板都用同樣的 N 重采樣過但如果你拿它跟論文里的數(shù)值對比就會發(fā)現(xiàn)對不上。想算真正的幾何 Fréchet得把局部代價矩陣換成點到線段的距離判斷可達(dá)性還得用自由空間圖代碼量翻三倍。我的建議是做手勢識別離散耦合版夠用因為所有輸入都經(jīng)過了統(tǒng)一的等距重采樣這個偏差是系統(tǒng)性的、一致的。追求嚴(yán)格數(shù)學(xué)定義的話另寫一個函數(shù)。還有一個實操細(xì)節(jié)Fréchet 不支持 Sakoe-Chiba 那樣的窗口裁剪。它的遞推依賴前一行整行的值強(qiáng)行截斷會得到錯誤結(jié)果。好在 64x64 規(guī)模下全矩陣計算也就 1.5ms 左右不用優(yōu)化。3.3 Hausdorff一行代碼算完然后被一個飛點毀掉Hausdorff 距離的實現(xiàn)最短但解釋起來最需要小心。雙向 Hausdorff 的定義是A 上每個點到 B 的最近距離中的最大值與 B 上每個點到 A 的最近距離中的最大值取較大者。function [dist, dhAB, dhBA] hausdorffDistance(A, B) d pairDist(A, B); dhAB max(min(d, [], 2)); % A 每點到 B 的最小距離取最大 dhBA max(min(d, [], 1)); % B 每點到 A 的最小距離取最大 dist max(dhAB, dhBA); end注意min(d,[],2)是沿行取最小對 A 中每個點求到 B 所有點的最近距離min(d,[],1)是沿列取最小。這兩個方向搞反了代碼還能跑出數(shù)值但結(jié)果就不再有意義——這是我見過最常見的實現(xiàn)錯誤。Hausdorff 的致命弱點在max上。因為取的是最大值只要有一個點偏離極遠(yuǎn)整個距離就被它主導(dǎo)。手勢繪制的起筆瞬間最容易產(chǎn)生這種點鼠標(biāo)按下的位置和第一個移動事件的位置之間可能有跳動或者用戶畫完提筆時手抖了一下。這個點可能離模板的最近點有 0.3 的距離在歸一化坐標(biāo)系里算很遠(yuǎn)了直接把整條軌跡的距離拉到 0.3而正常匹配應(yīng)該在 0.05 以下。兩個修補(bǔ)辦法我都試過。第一個是用分位數(shù)替代最大值比如取 95 分位function dist hausdorffRobust(A, B, q) d pairDist(A, B); dhAB prctile(min(d, [], 2), q); dhBA prctile(min(d, [], 1), q); dist max(dhAB, dhBA); end第二個是在預(yù)處理階段做離群點剔除計算每個點到軌跡中位點的距離超過 3 倍中位絕對偏差的點直接丟掉。我最后兩個都用上了q 0.95配合預(yù)處理剔除Hausdorff 的準(zhǔn)確率才從 60% 出頭提到 70% 左右。但即使這樣Hausdorff 在我的測試?yán)锶匀皇侨咧袦?zhǔn)確率最低的。這不是實現(xiàn)問題是原理決定的它丟掉了順序信息也就丟掉了手勢最有辨識度的部分。我保留它的理由只有一個——它是最快的0.25ms 量級適合做粗篩先用 Hausdorff 快速排除明顯不相關(guān)的模板再用 DTW 精算前三個候選。3.4 我調(diào)出來的參數(shù)組合參數(shù)不是拍腦袋定的我是按固定其他、只動一個的方式掃出來的。這張表記錄的是最終值以及為什么這么定參數(shù)取值定位理由重采樣點數(shù) N6432 拐角丟失128 收益低且耗時翻倍去重閾值畫布寬度的 1/1000太低留下抖動點太高吃掉短筆畫縮放方式bounding box閉合圖形尺寸一致性更好旋轉(zhuǎn)歸一化關(guān)閉默認(rèn)對圓/方無意義反而增大類內(nèi)方差DTW 帶寬比例0全窗口/ 0.15實時模式離線準(zhǔn)確率優(yōu)先實時響應(yīng)優(yōu)先DTW 歸一化除以 N長度相同路徑長度近似 NFréchet 局部代價點對點離散耦合與重采樣統(tǒng)一的系統(tǒng)性偏差可接受Hausdorff 分位數(shù)0.95抑制起筆飛點降噪效果明顯分類器 k 值3k1 太敏感k5 明顯欠擬合表格里分類器 k 值那一行屬于下一章的內(nèi)容先放在這里備查。要提醒的是這些值是在我自己采集的小樣本上得到的換數(shù)據(jù)源必須重掃特別是 N 和帶寬這兩個對數(shù)據(jù)密度敏感的。4. GUI 骨架把算法裝進(jìn)一個能演示的界面算法跑通是一回事做成能給別人演示的界面是另一回事。我在這一章花了大約和算法本身一樣多的時間主要卡在兩個地方鼠標(biāo)回調(diào)的坐標(biāo)轉(zhuǎn)換以及實時重繪造成的卡頓。這兩件事在任何一篇講 DTW 的文章里都不會提但它是實際項目的必經(jīng)之路。4.1 界面布局與控制件分工我選的是經(jīng)典 figure uicontrol沒用 App Designer。理由很直接經(jīng)典方案的代碼全是純文本.m文件可以直接貼進(jìn)文章、復(fù)制到任何版本的 Matlab 里跑App Designer 的.mlapp是二進(jìn)制包分享和 diff 都麻煩。而且這個界面的交互復(fù)雜度十來個控件遠(yuǎn)沒到需要可視化設(shè)計器的程度。布局上分三塊。左側(cè)是主畫布axDraw負(fù)責(zé)繪制輸入軌跡占 55% 寬度。右上是一組控制件一個popupmenu選擇距離度量DTW / Fréchet / Hausdorff一個checkbox控制旋轉(zhuǎn)歸一化開關(guān)一個pushbutton觸發(fā)識別一個listbox顯示模板庫和計算出的距離排名。右下是一個小畫布axCompare用來把輸入軌跡和最佳匹配模板疊在一起畫出來讓用戶直觀看到哪里對上了、哪里偏了。function buildUI fig figure(Name, 手勢軌跡模板匹配演示, NumberTitle, off, ... MenuBar, none, ToolBar, none, ... Color, [0.95 0.95 0.95], ... Position, [280 180 960 580]); axDraw axes(Parent, fig, Units, normalized, ... Position, [0.04 0.10 0.55 0.84], ... Box, on, XLim, [0 1], YLim, [0 1], ... XTick, [], YTick, []); axCmp axes(Parent, fig, Units, normalized, ... Position, [0.65 0.10 0.32 0.34], ... Box, on, XLim, [-1.2 1.2], YLim, [-1.2 1.2], ... XTick, [], YTick, [], DataAspectRatio, [1 1 1]); uicontrol(Parent, fig, Style, popupmenu, ... String, {DTW, Frechet, Hausdorff}, ... Units, normalized, Position, [0.65 0.86 0.32 0.06], ... Callback, onMetricChanged); uicontrol(Parent, fig, Style, checkbox, ... String, 啟用旋轉(zhuǎn)歸一化, Value, 0, ... Units, normalized, Position, [0.65 0.79 0.32 0.05]); uicontrol(Parent, fig, Style, pushbutton, String, 識別, ... Units, normalized, Position, [0.65 0.71 0.15 0.06], ... Callback, onRecognize); uicontrol(Parent, fig, Style, listbox, String, {}, ... Units, normalized, Position, [0.65 0.49 0.32 0.19]); endaxCmp上那個DataAspectRatio [1 1 1]值得單獨說。軌跡是二維等比例數(shù)據(jù)如果不鎖定縱橫比畫出來的圓會變成橢圓用戶一看就懵。用axis equal也行但會在某些布局重排時被覆蓋。4.2 畫布回調(diào)的兩種寫法與坐標(biāo)陷阱回調(diào)掛載有兩種思路掛在axes上的ButtonDownFcn或者掛在figure上的WindowButtonDownFcn。區(qū)別在于axes的ButtonDownFcn只在點擊到 axes 的空白背景時觸發(fā)如果 axes 里已經(jīng)有 Line 對象點在線上就觸發(fā)不了。而WindowButtonDownFcn掛在 figure 上任何位置的按下都能收到。我做拖拽繪制用的是后者然后在回調(diào)里自己判斷坐標(biāo)落點是否在畫布范圍內(nèi)function onRecognize(app, ~) pts app.rawPts; if size(pts, 1) 3 set(app.hStatus, String, 軌跡太短請重新繪制); return; end P resampleGesture(pts, app.N); P P - mean(P, 1); P scaleGesture(P, bbox); if app.useRotate P rotateToIndicative(P); end names fieldnames(app.templates); D zeros(numel(names), 1); for k 1:numel(names) T app.templates.(names{k}); % 已經(jīng)是 N x 2 歸一化軌跡 switch app.metric case 1, D(k) dtwDistance(P, T, 0); case 2, D(k) frechetDistance(P, T); case 3, D(k) hausdorffDistance(P, T); end end [ds, idx] sort(D, ascend); set(app.hList, String, ... arrayfun((i) sprintf(%s %.4f, names{idx(i)}, ds(i)), ... 1:numel(idx), UniformOutput, false)); set(app.hList, Value, 1); plotCompare(app.axCmp, P, app.templates.(names{idx(1)}), names{idx(1)}); end坐標(biāo)陷阱在CurrentPoint上如果 axes 的XLim、YLim被用戶縮放比如誤觸了工具欄的放大按鈕那么CurrentPoint返回的是數(shù)據(jù)坐標(biāo)落點會跑到 [0,1] 之外后面所有歸一化都基于錯誤的數(shù)據(jù)。我的做法是直接把工具欄關(guān)掉ToolBar,none并顯式鎖定XLim、YLim。這樣鼠標(biāo)位置和數(shù)據(jù)坐標(biāo)之間是簡單的比例關(guān)系中間不需要任何換算。4.3 重繪卡頓的定位過程與修復(fù)最初版本的繪制手感很差畫兩筆就開始拖影。排查過程大致是這樣先確認(rèn)是繪制環(huán)節(jié)還是計算環(huán)節(jié)——我在onMouseMove的開頭結(jié)尾加了tic/toc發(fā)現(xiàn)單次回調(diào)耗時不到 1ms說明計算沒問題。然后確認(rèn)幀率用簡單的計數(shù)器統(tǒng)計每秒觸發(fā)的 motion 事件數(shù)結(jié)果只有十幾幀而系統(tǒng)事件隊列本身能提供 60。問題定位到重繪策略上。原來的寫法是每次移動都調(diào)用plot(axDraw, x, y)。plot每次都會清空 axes 并重建所有圖形對象即使只有一個 Line 這也是相對重的操作。改法有兩條第一條是不復(fù)建對象只改數(shù)據(jù)。一開始就創(chuàng)建一個Line句柄之后每次只更新XData/YData% 初始化時 hLine animatedline(axDraw, Color, [0.1 0.4 0.8], LineWidth, 2); % 移動時 addpoints(hLine, p(1), p(2)); drawnow limitrate;animatedline就是為了這類增量繪制設(shè)計的配合drawnow limitrate限制到大約每秒 20 幀效果立竿見影。注意必須給animatedline設(shè)定MaximumNumPoints否則長軌跡會積累上萬個點性能反而崩掉。我設(shè)的是 2048。第二條是把識別計算從繪制回調(diào)里剝離出來。識別只在MouseUp時觸發(fā)一次不要放在MouseMove里跑。早期版本我圖省事在移動時就實時算距離顯示在界面上結(jié)果每幀 6 個模板 × 1.8ms ≈ 11ms直接鎖死主線程。改成松手才計算之后拖拽立刻順滑。修復(fù)后我重新測了一輪64 點軌跡、8 個模板、滿窗口 DTW一次完整識別耗時約 15ms用戶完全感知不到延遲。5. 最近鄰分類器與模板庫的工程化處理算法和界面都有了剩下的就是把它們組織成一個能給出答案的分類器。這一層看起來最簡單——算距離、取最小——但里面的決策細(xì)節(jié)直接決定最終準(zhǔn)確率也是我在項目后期反復(fù)調(diào)整的地方。5.1 模板庫怎么選單模板、多模板與類別不平衡最樸素的方案是每類手勢存一個模板通常是用第一遍畫的待測軌跡和每個模板比一次取最近的。這套方案的可解釋性最好——界面上能明確顯示最像圓圈模板用戶容易接受。但它的問題在類內(nèi)方差。同一個圓圈有人起筆在頂、有人起筆在左單模板只能覆蓋其中一種風(fēng)格。我的改進(jìn)方案是每類存三個模板用 k-近鄰的思路投票分別算出待測軌跡到三個模板的距離取最小值作為類別距離或者對前 k 個最近鄰跨類別做加權(quán)投票。function [label, score] classify(P, templates, metricFn, k) % templates : struct每個字段是 N x M 的軌跡矩陣M 個模板堆疊 names fieldnames(templates); allD []; allL {}; for i 1:numel(names) T templates.(names{i}); for m 1:size(T, 1) / 64 seg T((m-1)*641 : m*64, :); allD(end1, 1) metricFn(P, seg); allL{end1, 1} names{i}; end end [ds, idx] sort(allD, ascend); k min(k, numel(ds)); win allL(idx(1:k)); label mode(win); score ds(1); end模板的采集要專門做一輪每種手勢讓同一個人畫 5 遍從中挑 3 個兩兩距離最分散的作為模板而不是隨便取前三個。選擇方法是先算 5 個候選之間的距離矩陣貪心地選第一個、離它最遠(yuǎn)的第二個、離前兩個距離和最大的第三個。這個技巧把留一法準(zhǔn)確率提高了大約 4 個百分點成本只是多寫二十行代碼。類不平衡的問題也不能忽略。圓圈可能收集了 20 條閃電只有 5 條那么圓形因為模板多天然更容易被選中。簡單處理是限定每個類別參與投票的模板數(shù)相同或者對類別距離做歸一化。5.2 距離歸一化與拒識邏輯三種度量的原始數(shù)值范圍差得很遠(yuǎn)。在歸一化坐標(biāo)系下DTW 除以 N 后的典型值在 0.020.5 之間離散 Fréchet 在 0.050.8 之間Hausdorff 在 0.010.4 之間。直接拿絕對值做閾值沒有可比性我在界面上顯示的置信度是相對值最小距離與次小距離的比值。if numel(ds) 2 ratio ds(2) / max(ds(1), 1e-9); % 越大越可信 conf 1 - exp(-(ratio - 1)); % 映射到 (0,1) else conf 0.5; end這個比值的解釋非常直觀如果第一名和第二名差距很大說明這個判斷很確定如果兩個類別距離接近說明系統(tǒng)自己也在猶豫。拒識是另一個必須有的機(jī)制。用戶隨手亂畫一條線如果系統(tǒng)硬要給出一個答案體驗會很糟。我的做法是設(shè)兩道閘絕對距離超過閾值用模板庫自匹配的 95 分位做參考值或者置信度低于 0.3都判為未識別。閾值的確定不能憑感覺要拿交叉驗證的距離分布來定——把所有留一法的正確匹配距離收集起來取 95 分位作為上限。5.3 自建小樣本上的實測結(jié)果與失敗案例分析我在自己的小數(shù)據(jù)集上跑了一輪留一法8 類手勢、每類 6 條共 48 條每次留一條做測試其余做模板。結(jié)果如下必須說明樣本量很小這些數(shù)字只能看相對趨勢不能當(dāng)基準(zhǔn)度量方式留一法準(zhǔn)確率單次匹配耗時64 點主要錯誤類型DTW全窗口91.7%約 1.8 ms回勾被判成橫線DTW帶寬 0.1589.6%約 0.6 ms同上誤差更多離散 Fréchet85.4%約 1.5 ms采樣稀疏的手勢距離虛高Hausdorff雙向68.8%約 0.25 ms起筆抖動點導(dǎo)致整條誤判Hausdorff95 分位70.8%約 0.30 ms同上略有改善DTW 輸?shù)舻哪且焕苡幸馑家粋€橫線加右側(cè)回勾被認(rèn)成了純橫線。查了對齊矩陣才發(fā)現(xiàn)純橫線模板在末尾有一段點密集區(qū)因為那次畫的時候手慢采到的點多DTW 就把回勾的那段點都對到了這段密集區(qū)上累計代價并沒有明顯升高。后來改用 Fréchet 做這個二分類的判別因為 Fréchet 取最大值回勾那一段的最大偏離一下子暴露出來了距離從 0.04 跳到 0.21干凈利落地分開。這個案例讓我形成了一個實用經(jīng)驗DTW 擅長判斷整體形狀是否一致Fréchet 擅長判斷是否存在局部嚴(yán)重偏離。如果兩類手勢的區(qū)別在于某個局部細(xì)節(jié)有沒有鉤、拐了幾個彎Fréchet 更靠譜如果區(qū)別在整體輪廓圓 vs 三角DTW 更穩(wěn)。Hausdorff 的錯誤集中在起筆位置。有一條閃電手勢被認(rèn)成了勾因為兩者都是鋸齒狀的折線點集分布高度相似Hausdorff 根本區(qū)分不出來——這印證了前面說的丟失順序信息是原理性的缺陷不是實現(xiàn)能補(bǔ)的。我最終的方案是兩級串聯(lián)先用 Hausdorff 快速篩出距離最小的 4 個候選這一步幾乎不耗時再在這 4 個候選上用 DTW 和 Fréchet 的距離加權(quán)權(quán)重 0.6 / 0.4做最終判定。這個組合在留一法上跑到 93.8%比任何一個單一度量都好。加權(quán)系數(shù)的來源是簡單網(wǎng)格搜索0.0 到 1.0 步長 0.1 掃了一遍最優(yōu)點很平緩說明結(jié)果對這個參數(shù)不敏感可以放心用。6. 換個數(shù)據(jù)源之后失效的地方幾個已驗證的邊界代碼寫完能跑和這個方案能用中間還隔著一堆邊界條件。我在往其他場景遷移這套東西的時候撞上了幾個明確的失效區(qū)寫出來省得別人再走一遍。6.1 從鼠標(biāo)點到骨架點采樣噪聲的量級完全變了鼠標(biāo)軌跡的噪聲主要來自事件合并和手抖量級在幾個像素。換成攝像頭采集的骨架關(guān)鍵點噪聲會突然放大到十幾個像素而且?guī)g抖動——同一個靜止的姿勢關(guān)鍵點坐標(biāo)在相鄰幀之間會跳。這時候原來的 95 分位 Hausdorff 就不夠用了因為噪聲點是遍布整條軌跡的不是集中在起筆那一兩個孤立點。我在這個場景下的處理是加一層時域平滑對每個坐標(biāo)維度做 5 點滑動平均或者用簡單的一階低通濾波function P smoothTrajectory(P, alpha) % alpha 越小越平滑0.3 左右是個不錯的起點 for i 2:size(P,1) P(i,:) alpha * P(i,:) (1 - alpha) * P(i-1,:); end end平滑必須放在重采樣之前否則重采樣已經(jīng)把點拉到等間距再平滑會改變采樣點的弧長分布引入新的偏差。這個順序反了曲線會被吃掉拐角看起來鈍鈍的。另外骨架點的采樣率是固定的比如 30fps這意味著原始序列的時間等距是可信的這時候等距重采樣反而會破壞時間信息——如果動作的節(jié)奏本身有語義快揮和慢揮是不同指令就該保留時間采樣改用按時間加權(quán)的 DTW 代價。6.2 多筆手勢與分段匹配現(xiàn)實里的手勢經(jīng)常不是一筆畫完的比如畫一個需要兩筆米需要四筆。直接把這些點連成一條序列交給 DTW會在筆畫之間的跳躍處引入巨大的虛假位移——筆尖離開畫布的瞬間上一個筆畫終點和下一個筆畫起點之間的連線被當(dāng)成了一段真實的軌跡。解決辦法是按筆畫分段段內(nèi)匹配、段間求和。每一段獨立做重采樣和歸一化縮放要按整組筆畫統(tǒng)一的包圍盒不能每段各自歸一化否則相對大小信息丟失然后總距離是各段距離的加權(quán)和function D multiStrokeDistance(A, B, metricFn) % A, B : cell 數(shù)組每個元素是一筆的 N x 2 軌跡 if numel(A) ~ numel(B) D inf; return; % 筆畫數(shù)不同直接判不匹配 end D 0; for k 1:numel(A) D D metricFn(A{k}, B{k}); end D D / numel(A); end筆畫數(shù)不同直接判不匹配這個策略簡單但有效因為幾筆本身就是很強(qiáng)的語義特征。代價是容忍不了用戶多畫或少畫一筆所以我在界面上給了一個允許分筆對其的備選模式用動態(tài)規(guī)劃找最優(yōu)的分段對應(yīng)關(guān)系——不過這條路徑我只在實驗里跑通最終沒放進(jìn)主流程因為它引入了太多需要調(diào)的參數(shù)收益并不明顯。還有一點值得記下來同一筆畫的反向繪制。DTW 和 Fréchet 都要求單調(diào)前進(jìn)用戶如果習(xí)慣了從右往左畫橫線遇到從左往右畫的模板距離會非常大。我的處理是給每個模板同時存一份反轉(zhuǎn)版本匹配時取兩者的較小值。成本是模板庫翻倍匹配耗時翻倍但對用戶友好度的提升很明顯——尤其在沒有明確指示該往哪個方向畫的界面上這個改動幾乎必須做。7. 我個人在調(diào)這套東西時沉淀的幾條判斷寫到這里我想收在幾個不屬于任何具體章節(jié)的經(jīng)驗上都是調(diào)試過程中反復(fù)驗證過的。先看數(shù)據(jù)再看算法。我見過太多人一上來就調(diào) DTW 的窗口、換距離函數(shù)實際上問題出在輸入軌跡本身——點數(shù)不一致、坐標(biāo)沒歸一化、有 NaN。加一段fprintf把每步預(yù)處理后的點數(shù)、取值范圍打出來五分鐘就能定位一半的算法不準(zhǔn)問題。距離的絕對值沒有意義相對排名才有意義。閾值和置信度不要拍腦袋定用留一法的距離分布推。這一點在換數(shù)據(jù)源時尤其重要我那套閾值在鼠標(biāo)數(shù)據(jù)上工作良好換到骨架點數(shù)據(jù)上全線失效就是因為分布整體平移了。三種度量別當(dāng)成互斥選項。它們度量的是不同側(cè)面DTW 看整體節(jié)奏對齊Fréchet 看局部最壞偏離Hausdorff 看空間覆蓋。把它們當(dāng)特征組合起來用比糾結(jié)哪個最好收益大得多。我最后那套兩級串聯(lián)的結(jié)構(gòu)代碼量只多了三十來行準(zhǔn)確率提了將近 7 個百分點。界面上一定要畫出對齊結(jié)果。不是為了好看是為了調(diào)試。DTW 的對齊路徑畫出來能一眼看出是某一段被壓縮了還是整體偏移比盯著一個數(shù)字調(diào)參高效太多。我那個axCompare小畫布后期基本成了主力調(diào)試工具比在命令行里打印距離矩陣直觀十倍。能跑通的最小版本要盡早跑通。這套東西我最初寫成三個獨立腳本加一個命令行驅(qū)動能跑出準(zhǔn)確率之后才動的界面。如果反過來先做界面調(diào)試算法時每次都要點鼠標(biāo)畫一筆才能看結(jié)果效率會低到讓人放棄。 DTW、Fréchet與Hausdorff手勢軌跡匹配及Matlab GUI實現(xiàn)
1. 三種像不像的答案手勢軌跡匹配在比什么去年幫一個做教學(xué)演示的朋友搭手勢控制的小程序需求很樸素用戶在畫布上用鼠標(biāo)畫一筆系統(tǒng)判斷這是圓圈橫線勾閃電中的哪一種然后觸發(fā)對應(yīng)動作。他一開始想上深度學(xué)習(xí)我看了一眼他手頭的數(shù)據(jù)量——八類手勢每類他自己畫了五遍總共四十條軌跡——這個規(guī)模上神經(jīng)網(wǎng)絡(luò)純屬自找麻煩。傳統(tǒng)模板匹配在這個場景下反而更合適樣本極少、要求可解釋、還要在界面上把為什么認(rèn)為是這個手勢畫出來給人看這三條正好是距離度量類算法的主場。這篇文章要拆的就是圍繞DTW動態(tài)時間規(guī)整、Fréchet 距離弗雷歇距離和Hausdorff 距離豪斯多夫距離這三種軌跡相似度度量配一套 Matlab 的圖形界面把畫一筆、比一比、給結(jié)論這條鏈路走通的完整過程。關(guān)鍵詞我攤開說手勢識別、軌跡相似度、DTW、離散Fréchet、Hausdorff、Matlab GUI、最近鄰分類、軌跡重采樣歸一化。適合誰看手上有幾十條到幾百條軌跡樣本、想快速做出一個能演示能解釋的原型的人以及正在做課程設(shè)計、需要把算法原理和界面都講清楚的人。有 Matlab 基礎(chǔ)就能跟著跑沒做過軌跡匹配也能看懂思路因為我會把每一種距離到底在比什么用生活化的例子說透。1.1 同一個手勢畫三遍三條曲線差在哪先把問題本身看清楚了才知道為什么需要三種不同的尺子。假設(shè)你讓同一個人連著畫三個圓圈把鼠標(biāo)采樣點連起來會看到三種典型差異。第一種是速度差異。第一遍畫得快采樣點稀疏六十多個點第三遍手慢還中間頓了一下一百二十個點。兩條曲線的形狀幾乎一樣但點數(shù)差一倍逐點對齊算歐氏距離會產(chǎn)生巨大誤差——這就是 DTW 要解決的問題它允許時間軸上的非線性拉伸。第二種是起筆和收筆的位置偏差。同一個人畫圓起點有時在正上方有時在左上角終點也因此偏移。兩條曲線整體形狀高度一致但端點對不上。Hausdorff 距離完全不在乎這個因為它只問這條曲線上的每個點到另一條曲線上最近點的距離最大值是多少點的先后順序它根本不看。第三種是整體走向的細(xì)微差別比如一個畫得偏扁、一個畫得偏圓中間還帶點抖動。這種走著走著偏了的差異正是 Fréchet 距離擅長捕捉的——它考慮的是沿著曲線前進(jìn)時最壞情況下的偏離程度。我在調(diào)試初期最大的教訓(xùn)是不要指望一種尺子解決所有問題。當(dāng)時我拿 DTW 去區(qū)分橫線和橫線加回勾準(zhǔn)確率怎么調(diào)都上不去后來換成 Fréchet 一眼就分開了。原因后面細(xì)說。1.2 DTW、離散 Fréchet、Hausdorff 的度量哲學(xué)這三者看著都是算兩條點序列的距離底層假設(shè)完全不同我用一張表把關(guān)鍵差異擺出來這張表我在項目里反復(fù)回看過很多次維度DTW離散 FréchetHausdorff是否關(guān)心點的先后順序關(guān)心且允許重復(fù)對應(yīng)關(guān)心且必須單調(diào)前進(jìn)完全不關(guān)心當(dāng)作點集對繪制速度差異的容忍度極強(qiáng)可任意拉伸中等單調(diào)但不跳躍無速度快慢不影響結(jié)果對離群點飛點中等會被攤到路徑上較敏感最大值直接放大極敏感一個飛點就毀掉單次計算復(fù)雜度O(NM)可加窗口優(yōu)化O(NM)不可加窗口O(NM)可高度向量化是否滿足三角不等式不滿足加窗口后更不滿足連續(xù)版滿足離散耦合版近似滿足是真度量典型翻車場景停頓、筆畫粗細(xì)導(dǎo)致的對齊病態(tài)采樣過稀時距離虛高起筆抖動的孤立點表里有一行值得單獨說Hausdorff 把軌跡當(dāng)點集完全丟棄順序信息。你把一個橫著的 C和一個反著寫的 ?放在一起Hausdorff 距離會告訴你它們一模一樣——因為兩組點的空間分布幾乎重合。這在很多場景下是優(yōu)點比如只關(guān)心圖形覆蓋范圍但在手勢識別里是硬傷因為從左往右畫橫和從右往左畫橫在交互語義上可能是兩個完全不同的指令。DTW 不滿足三角不等式這一點也經(jīng)常被忽略。這意味著你不能拿它做度量空間上的加速索引比如 BK 樹也別指望距離小就一定相似、距離大就一定不相似的嚴(yán)格保證。做幾十條模板的暴力最近鄰?fù)耆珱]問題想上十萬條就得掂量了。1.3 什么樣的項目適合用這套傳統(tǒng)方案我把這個話題單拎出來講是因為見過太多人在四十條樣本的項目上硬套神經(jīng)網(wǎng)絡(luò)最后花兩周調(diào)參得到一個還不如模板匹配的結(jié)果。小樣本、強(qiáng)可解釋、需要可視化中間過程這三條只要占了兩條傳統(tǒng)距離度量就是更優(yōu)解。手勢識別只是其中一個例子同樣的思路可以遷移到工業(yè)上的裝配軌跡比對、體育動作的規(guī)范度打分、醫(yī)療康復(fù)里的關(guān)節(jié)運動軌跡評估——這些場景共同點是樣本少、每個樣本維度低二維或三維點序列、結(jié)果要能指出哪里不像。反過來什么情況別用手勢類別超過五十種、每類樣本上千條、需要識別不同人的風(fēng)格泛化這時候模板匹配的準(zhǔn)確率上限會很明顯該上學(xué)習(xí)模型就上。我個人的經(jīng)驗閾值大致是每類樣本少于三十條、類別數(shù)少于二十模板匹配的性價比遠(yuǎn)高于訓(xùn)練模型。還有一點這套算法的中間結(jié)果DTW 的對齊路徑、Fréchet 的自由空間圖、Hausdorff 的最大偏離點都能直接畫在界面上。給非技術(shù)人員演示的時候你看系統(tǒng)認(rèn)為你畫的第三段和模板的第二段對上了這種解釋比一個 0.87 的置信度分?jǐn)?shù)有說服力得多。2. 從鼠標(biāo)軌跡到歸一化矩陣預(yù)處理決定了后面所有的上限這一章我放在算法之前是因為踩過的最深的坑幾乎全在預(yù)處理。有句話我特別認(rèn)同軌跡匹配的上限由預(yù)處理決定距離度量只是把這個上限兌現(xiàn)出來。我最初偷懶直接把鼠標(biāo)回調(diào)拿到的原始點丟給 DTW結(jié)果同一手勢畫兩遍的類內(nèi)距離比不同手勢的類間距離還大調(diào)了三天參數(shù)毫無進(jìn)展最后發(fā)現(xiàn)是重采樣沒做。2.1 采集環(huán)節(jié)事件回調(diào)拿到的點在抖什么Matlab 里用鼠標(biāo)在坐標(biāo)軸上畫線最常見的寫法是在 figure 上掛WindowButtonDownFcn、WindowButtonMotionFcn、WindowButtonUpFcn三個回調(diào)用get(ax,CurrentPoint)取當(dāng)前坐標(biāo)function onMouseDown(src, ~) cp get(ax, CurrentPoint); % 返回 2x3 矩陣 p cp(1, 1:2); % 取第一行的 x y if ~inAxes(ax, p), return; end app.pts p; app.drawing true; set(app.hLine, XData, p(1), YData, p(2)); end function onMouseMove(src, ~) if ~app.drawing, return; end cp get(ax, CurrentPoint); app.pts(end1, :) cp(1, 1:2); set(app.hLine, XData, app.pts(:,1), YData, app.pts(:,2)); drawnow limitrate; end function onMouseUp(src, ~) app.drawing false; runRecognize(app); end function ok inAxes(ax, p) xl get(ax, XLim); yl get(ax, YLim); ok p(1) xl(1) p(1) xl(2) ... p(2) yl(1) p(2) yl(2); end這里有幾個實際的坑。第一個是CurrentPoint返回的是2x3矩陣而不是 2 元素向量直接索引cp(1)cp(2)會取到錯誤的值必須cp(1,1:2)。第二個是WindowButtonMotionFcn的觸發(fā)頻率取決于系統(tǒng)事件隊列不同機(jī)器上每秒采到的點數(shù)可能差好幾倍這意味著原始點序列的時間采樣是不可靠的。第三個是鼠標(biāo)移動事件在快速劃動時會被合并相鄰兩點之間可能隔著幾十個像素曲線看起來是直的一段。還有一個隱蔽問題用戶在同一個位置輕微抖動時會連續(xù)產(chǎn)生一批幾乎重合的點。這些點如果不去掉后面的等距重采樣用的累計弧長會出現(xiàn)零長度段interp1會報警告甚至返回 NaN。2.2 去重、等距重采樣與累計弧長插值我的做法是兩步走先按最小距離去重再按累計弧長做等距重采樣。為什么要按弧長而不是按下標(biāo)因為下標(biāo)反映的是采到了第幾個點受采樣頻率影響弧長反映的是沿著曲線走了多遠(yuǎn)是曲線的內(nèi)在屬性。等距重采樣之后兩條用不同速度畫出來的曲線在幾何上就有了可比性。function P resampleGesture(pts, N) % 輸入 pts: M x 2 原始軌跡點 % 輸出 P : N x 2 等弧長重采樣后的軌跡 % 1) 去重相鄰點距離過小則丟棄 if size(pts, 1) 2 P repmat(pts(1,:), N, 1); return; end d sqrt(sum(diff(pts).^2, 2)); keep [true; d 1e-9]; pts pts(keep, :); if size(pts, 1) 2 P repmat(pts(1,:), N, 1); return; end % 2) 累計弧長 seg sqrt(sum(diff(pts).^2, 2)); cum [0; cumsum(seg)]; total cum(end); if total 1e-9 P repmat(pts(1,:), N, 1); return; end % 3) 等弧長插值 qi linspace(0, total, N); P [interp1(cum, pts(:,1), qi, linear), ... interp1(cum, pts(:,2), qi, linear)]; endN取多少合適我用的是64。理由有三一是在我的小樣本上32 點對回勾閃電這類帶細(xì)節(jié)的手勢明顯不夠拐角會被抹平128 點對分類準(zhǔn)確率的提升不到一個百分點但 DTW 的 O(N2) 計算量翻四倍實時繪制的界面會開始卡64 是拐點。如果你只做簡單幾何圖形48 就夠如果做手寫數(shù)字類的復(fù)雜軌跡96 更穩(wěn)妥。去重閾值我用的是相對值而不是絕對像素代碼里寫1e-9是因為坐標(biāo)已經(jīng)歸一化過了。如果還沒歸一化用畫布寬度的千分之一左右比如 400 像素寬的畫布用 0.4。2.3 平移、縮放、旋轉(zhuǎn)三個開關(guān)各自的代價歸一化這三件事每一件都是用了方便、用錯了丟信息得一個一個想清楚。平移幾乎無腦要做把質(zhì)心挪到原點。這樣用戶在畫布任何位置畫同一個手勢結(jié)果都一致。代碼就一行P P - mean(P,1)。縮放要謹(jǐn)慎選擇范數(shù)。常見兩種按包圍盒的最大邊長縮放到統(tǒng)一大小L∞ 范數(shù)或者按離質(zhì)心最遠(yuǎn)點的距離縮放L2 范數(shù)。function P scaleGesture(P, mode) switch mode case bbox % 按包圍盒 s max(max(P) - min(P)); case radius % 按半徑 s max(sqrt(sum(P.^2, 2))); otherwise s 1; end if s 1e-9, P P / s; end end兩種的差別在細(xì)長形狀上很明顯一條橫線用包圍盒歸一化會被拉到滿寬用半徑歸一化則會被壓得很短。我最后選了bbox因為對圓方三角這類閉合圖形包圍盒歸一化后的尺寸更一致。但這里有個所有人都該知道的反噬縮放歸一化之后畫一個大圓和畫一個小圓就變成了同一類。如果你的手勢語義里大小是有意義的比如畫大圈音量10畫小圈音量1那縮放就得關(guān)掉或者按面積分檔。旋轉(zhuǎn)歸一化是最有爭議的一個。經(jīng)典做法是用首筆點到質(zhì)心的方向作為指示角把整個軌跡旋轉(zhuǎn)到這個角朝上。這個技巧對箭頭勾這類有明確指向的手勢有效但對圓形、方形、Z 形就沒意義——一個圓你轉(zhuǎn)多少度都是同一個圓反而會因為起筆點位置不同引入額外方差。我的處理是把它做成界面上的一個復(fù)選框默認(rèn)關(guān)閉只在特定手勢集合上打開function P rotateToIndicative(P) c mean(P, 1); P P - c; theta atan2(P(1,2), P(1,1)); % 首點相對質(zhì)心的方向角 R [cos(-theta) -sin(-theta); sin(-theta) cos(-theta)]; P P * R; % 注意右乘轉(zhuǎn)置等于左乘 R end這段代碼里P * R這個寫法值得盯一下方向不能反。我見過有人在這一點上debug半天畫出來的軌跡越轉(zhuǎn)越歪。2.4 預(yù)處理順序錯了就白干順序我固定成去重 → 平移 → 等距重采樣 → 縮放 → 旋轉(zhuǎn)。每一處的相對位置都有理由不能隨便換。去重必須在重采樣之前因為累計弧長依賴嚴(yán)格遞增的cum向量有重復(fù)點會導(dǎo)致interp1報錯。平移放在重采樣之前還是之后理論上可以互換平移不改變弧長但放在前面代碼更好讀?？s放必須在重采樣之后因為重采樣是在原始坐標(biāo)系下按弧長分布取點先縮放會改變數(shù)值精度。旋轉(zhuǎn)放最后因為它依賴質(zhì)心而質(zhì)心在平移后就固定在原點了。有個我實際踩到的坑平移和縮放如果在重采樣之前做容易遇到坐標(biāo)數(shù)值過小導(dǎo)致浮點精度問題。原始畫布坐標(biāo)通常是幾百像素量級歸一化后變成 0.001 量級此時再去算兩點間的平方距離有效位數(shù)會掉。解決辦法是先按畫布尺寸整體縮放到 [-1,1] 附近再做后續(xù)處理。這一條在論文里基本不會寫但真實調(diào)試時會遇到。3. 三種距離的 Matlab 實現(xiàn)與參數(shù)取舍這一段是全文的技術(shù)核心。我把三種度量都寫成了獨立函數(shù)輸入輸出形狀一致輸入兩個 N x 2 矩陣輸出一個標(biāo)量距離這樣在分類器里可以直接換著調(diào)用方便對比。下面每一段都會強(qiáng)調(diào)一個容易被忽略的實現(xiàn)細(xì)節(jié)。3.1 DTW遞推式、窗口帶與路徑歸一化DTW 的遞推式不復(fù)雜構(gòu)造一個 N x M 的代價矩陣DD(i,j)表示 A 的前 i 個點和 B 的前 j 個點匹配的最小累計代價。轉(zhuǎn)移只有三個方向——豎著走A 前進(jìn)一格B 停住、橫著走A 停住B 前進(jìn)、斜著走兩者同時前進(jìn)。function [dist, D] dtwDistance(A, B, bandRatio) % A, B : N x 2 歸一化后的軌跡 % bandRatio : Sakoe-Chiba 帶寬比例0 表示不限制 % dist : 歸一化后的 DTW 距離 N size(A,1); M size(B,1); d pairDist(A, B); % N x M 局部代價矩陣 D inf(N, M); if bandRatio 0 band max(N, M); else band max(1, round(bandRatio * max(N, M))); end for i 1:N jlo max(1, i - band); jhi min(M, i band); for j jlo:jhi if i 1 j 1 D(i,j) d(i,j); continue; end c inf; if i 1, c min(c, D(i-1, j )); end if j 1, c min(c, D(i, j-1)); end if i 1 j 1, c min(c, D(i-1, j-1)); end D(i,j) d(i,j) c; end end dist D(N, M) / N; % 兩序列長度相同按步數(shù)歸一化 end function D pairDist(A, B) % 不依賴 Statistics 工具箱的兩兩歐氏距離 D2 sum(A.^2,2) sum(B.^2,2) - 2 * (A * B); D sqrt(max(D2, 0)); end第一個細(xì)節(jié)pairDist這個手寫函數(shù)。很多人第一反應(yīng)是pdist2但那需要 Statistics and Machine Learning Toolbox。給人演示的代碼依賴越少越好用矩陣乘法展開(a-b)2 a2 b2 - 2ab完全等價而且更快。max(D2, 0)那一步不能省——浮點誤差會讓理論上為 0 的值變成 -1e-17開方得到復(fù)數(shù)。第二個細(xì)節(jié)末尾除以 N。這一步太多人漏掉。DTW 的累計代價是沿著路徑一路加過來的路徑越長累加值越大。兩條各自 64 點的軌跡路徑長度大致就是 64不歸一化的話形狀類似但細(xì)節(jié)更多的模板天然吃虧。有人會用路徑長度做精確歸一化回溯統(tǒng)計實際步數(shù)但兩條等長序列的路徑長度差異很小除以 N 更省事且效果相當(dāng)。如果你處理的序列長度不等比如沒做等距重采樣就必須回溯算真實路徑長度了。第三個細(xì)節(jié)Sakoe-Chiba 帶寬。不加限制時DTW 會把形狀上完全不相干的部分強(qiáng)行對齊產(chǎn)生所謂的病態(tài)對齊——比如把橫線的整段都壓到一個點上。加帶寬后只允許對角線附近的匹配計算量從 N2 降到 2·N·band。我實測bandRatio 0.15時64x64 的匹配耗時從約 1.8ms 降到 0.6ms準(zhǔn)確率只掉了 2 個百分點。如果你的界面要實時給反饋這個折中是值得的。3.2 離散 Fréchet為什么多數(shù) Demo 算的其實不是幾何 FréchetFréchet 距離有個流傳最廣的解釋一個人牽著狗人沿曲線 A 走狗沿曲線 B 走兩者都用任意速度但都不能后退問最短需要多長的狗繩。這個比喻很好但離散版實現(xiàn)和連續(xù)版定義完全是兩回事這里必須講清楚否則你會在參數(shù)調(diào)優(yōu)時一頭霧水。連續(xù)的 Fréchet 距離定義中人和狗可以停在曲線上的任意一點所以計算時需要把點投影到線段上用點到線段的距離并用自由空間圖free space diagram判定可達(dá)性。而絕大多數(shù)代碼實現(xiàn)包括很多教學(xué)資料里給的用的是離散耦合 Fréchet只在采樣點上做單調(diào)匹配用點到點的距離function [dist, C] frechetDistance(A, B) % 離散耦合 Fréchet 距離點對點非點到線段 N size(A,1); M size(B,1); d pairDist(A, B); C inf(N, M); C(1,1) d(1,1); for i 2:N, C(i,1) max(C(i-1,1), d(i,1)); end for j 2:M, C(1,j) max(C(1,j-1), d(1,j)); end for i 2:N for j 2:M m min([C(i-1,j), C(i-1,j-1), C(i,j-1)]); C(i,j) max(m, d(i,j)); end end dist C(N,M); end三個轉(zhuǎn)移方向取min選擇最溫和的前進(jìn)方式再和當(dāng)前局部代價取max因為要保證最壞情況。這個 max-min 結(jié)構(gòu)和 DTW 的純求和完全不同也是為什么 Fréchet 更容易被單個壞點拉高。后果是什么離散耦合 Fréchet 的值依賴采樣密度。同一條曲線采 32 個點和采 128 個點算出來的距離不一樣——采樣越稀落到最近點上的概率越低距離越大。這在跨模板比較時不致命因為所有模板都用同樣的 N 重采樣過但如果你拿它跟論文里的數(shù)值對比就會發(fā)現(xiàn)對不上。想算真正的幾何 Fréchet得把局部代價矩陣換成點到線段的距離判斷可達(dá)性還得用自由空間圖代碼量翻三倍。我的建議是做手勢識別離散耦合版夠用因為所有輸入都經(jīng)過了統(tǒng)一的等距重采樣這個偏差是系統(tǒng)性的、一致的。追求嚴(yán)格數(shù)學(xué)定義的話另寫一個函數(shù)。還有一個實操細(xì)節(jié)Fréchet 不支持 Sakoe-Chiba 那樣的窗口裁剪。它的遞推依賴前一行整行的值強(qiáng)行截斷會得到錯誤結(jié)果。好在 64x64 規(guī)模下全矩陣計算也就 1.5ms 左右不用優(yōu)化。3.3 Hausdorff一行代碼算完然后被一個飛點毀掉Hausdorff 距離的實現(xiàn)最短但解釋起來最需要小心。雙向 Hausdorff 的定義是A 上每個點到 B 的最近距離中的最大值與 B 上每個點到 A 的最近距離中的最大值取較大者。function [dist, dhAB, dhBA] hausdorffDistance(A, B) d pairDist(A, B); dhAB max(min(d, [], 2)); % A 每點到 B 的最小距離取最大 dhBA max(min(d, [], 1)); % B 每點到 A 的最小距離取最大 dist max(dhAB, dhBA); end注意min(d,[],2)是沿行取最小對 A 中每個點求到 B 所有點的最近距離min(d,[],1)是沿列取最小。這兩個方向搞反了代碼還能跑出數(shù)值但結(jié)果就不再有意義——這是我見過最常見的實現(xiàn)錯誤。Hausdorff 的致命弱點在max上。因為取的是最大值只要有一個點偏離極遠(yuǎn)整個距離就被它主導(dǎo)。手勢繪制的起筆瞬間最容易產(chǎn)生這種點鼠標(biāo)按下的位置和第一個移動事件的位置之間可能有跳動或者用戶畫完提筆時手抖了一下。這個點可能離模板的最近點有 0.3 的距離在歸一化坐標(biāo)系里算很遠(yuǎn)了直接把整條軌跡的距離拉到 0.3而正常匹配應(yīng)該在 0.05 以下。兩個修補(bǔ)辦法我都試過。第一個是用分位數(shù)替代最大值比如取 95 分位function dist hausdorffRobust(A, B, q) d pairDist(A, B); dhAB prctile(min(d, [], 2), q); dhBA prctile(min(d, [], 1), q); dist max(dhAB, dhBA); end第二個是在預(yù)處理階段做離群點剔除計算每個點到軌跡中位點的距離超過 3 倍中位絕對偏差的點直接丟掉。我最后兩個都用上了q 0.95配合預(yù)處理剔除Hausdorff 的準(zhǔn)確率才從 60% 出頭提到 70% 左右。但即使這樣Hausdorff 在我的測試?yán)锶匀皇侨咧袦?zhǔn)確率最低的。這不是實現(xiàn)問題是原理決定的它丟掉了順序信息也就丟掉了手勢最有辨識度的部分。我保留它的理由只有一個——它是最快的0.25ms 量級適合做粗篩先用 Hausdorff 快速排除明顯不相關(guān)的模板再用 DTW 精算前三個候選。3.4 我調(diào)出來的參數(shù)組合參數(shù)不是拍腦袋定的我是按固定其他、只動一個的方式掃出來的。這張表記錄的是最終值以及為什么這么定參數(shù)取值定位理由重采樣點數(shù) N6432 拐角丟失128 收益低且耗時翻倍去重閾值畫布寬度的 1/1000太低留下抖動點太高吃掉短筆畫縮放方式bounding box閉合圖形尺寸一致性更好旋轉(zhuǎn)歸一化關(guān)閉默認(rèn)對圓/方無意義反而增大類內(nèi)方差DTW 帶寬比例0全窗口/ 0.15實時模式離線準(zhǔn)確率優(yōu)先實時響應(yīng)優(yōu)先DTW 歸一化除以 N長度相同路徑長度近似 NFréchet 局部代價點對點離散耦合與重采樣統(tǒng)一的系統(tǒng)性偏差可接受Hausdorff 分位數(shù)0.95抑制起筆飛點降噪效果明顯分類器 k 值3k1 太敏感k5 明顯欠擬合表格里分類器 k 值那一行屬于下一章的內(nèi)容先放在這里備查。要提醒的是這些值是在我自己采集的小樣本上得到的換數(shù)據(jù)源必須重掃特別是 N 和帶寬這兩個對數(shù)據(jù)密度敏感的。4. GUI 骨架把算法裝進(jìn)一個能演示的界面算法跑通是一回事做成能給別人演示的界面是另一回事。我在這一章花了大約和算法本身一樣多的時間主要卡在兩個地方鼠標(biāo)回調(diào)的坐標(biāo)轉(zhuǎn)換以及實時重繪造成的卡頓。這兩件事在任何一篇講 DTW 的文章里都不會提但它是實際項目的必經(jīng)之路。4.1 界面布局與控制件分工我選的是經(jīng)典 figure uicontrol沒用 App Designer。理由很直接經(jīng)典方案的代碼全是純文本.m文件可以直接貼進(jìn)文章、復(fù)制到任何版本的 Matlab 里跑App Designer 的.mlapp是二進(jìn)制包分享和 diff 都麻煩。而且這個界面的交互復(fù)雜度十來個控件遠(yuǎn)沒到需要可視化設(shè)計器的程度。布局上分三塊。左側(cè)是主畫布axDraw負(fù)責(zé)繪制輸入軌跡占 55% 寬度。右上是一組控制件一個popupmenu選擇距離度量DTW / Fréchet / Hausdorff一個checkbox控制旋轉(zhuǎn)歸一化開關(guān)一個pushbutton觸發(fā)識別一個listbox顯示模板庫和計算出的距離排名。右下是一個小畫布axCompare用來把輸入軌跡和最佳匹配模板疊在一起畫出來讓用戶直觀看到哪里對上了、哪里偏了。function buildUI fig figure(Name, 手勢軌跡模板匹配演示, NumberTitle, off, ... MenuBar, none, ToolBar, none, ... Color, [0.95 0.95 0.95], ... Position, [280 180 960 580]); axDraw axes(Parent, fig, Units, normalized, ... Position, [0.04 0.10 0.55 0.84], ... Box, on, XLim, [0 1], YLim, [0 1], ... XTick, [], YTick, []); axCmp axes(Parent, fig, Units, normalized, ... Position, [0.65 0.10 0.32 0.34], ... Box, on, XLim, [-1.2 1.2], YLim, [-1.2 1.2], ... XTick, [], YTick, [], DataAspectRatio, [1 1 1]); uicontrol(Parent, fig, Style, popupmenu, ... String, {DTW, Frechet, Hausdorff}, ... Units, normalized, Position, [0.65 0.86 0.32 0.06], ... Callback, onMetricChanged); uicontrol(Parent, fig, Style, checkbox, ... String, 啟用旋轉(zhuǎn)歸一化, Value, 0, ... Units, normalized, Position, [0.65 0.79 0.32 0.05]); uicontrol(Parent, fig, Style, pushbutton, String, 識別, ... Units, normalized, Position, [0.65 0.71 0.15 0.06], ... Callback, onRecognize); uicontrol(Parent, fig, Style, listbox, String, {}, ... Units, normalized, Position, [0.65 0.49 0.32 0.19]); endaxCmp上那個DataAspectRatio [1 1 1]值得單獨說。軌跡是二維等比例數(shù)據(jù)如果不鎖定縱橫比畫出來的圓會變成橢圓用戶一看就懵。用axis equal也行但會在某些布局重排時被覆蓋。4.2 畫布回調(diào)的兩種寫法與坐標(biāo)陷阱回調(diào)掛載有兩種思路掛在axes上的ButtonDownFcn或者掛在figure上的WindowButtonDownFcn。區(qū)別在于axes的ButtonDownFcn只在點擊到 axes 的空白背景時觸發(fā)如果 axes 里已經(jīng)有 Line 對象點在線上就觸發(fā)不了。而WindowButtonDownFcn掛在 figure 上任何位置的按下都能收到。我做拖拽繪制用的是后者然后在回調(diào)里自己判斷坐標(biāo)落點是否在畫布范圍內(nèi)function onRecognize(app, ~) pts app.rawPts; if size(pts, 1) 3 set(app.hStatus, String, 軌跡太短請重新繪制); return; end P resampleGesture(pts, app.N); P P - mean(P, 1); P scaleGesture(P, bbox); if app.useRotate P rotateToIndicative(P); end names fieldnames(app.templates); D zeros(numel(names), 1); for k 1:numel(names) T app.templates.(names{k}); % 已經(jīng)是 N x 2 歸一化軌跡 switch app.metric case 1, D(k) dtwDistance(P, T, 0); case 2, D(k) frechetDistance(P, T); case 3, D(k) hausdorffDistance(P, T); end end [ds, idx] sort(D, ascend); set(app.hList, String, ... arrayfun((i) sprintf(%s %.4f, names{idx(i)}, ds(i)), ... 1:numel(idx), UniformOutput, false)); set(app.hList, Value, 1); plotCompare(app.axCmp, P, app.templates.(names{idx(1)}), names{idx(1)}); end坐標(biāo)陷阱在CurrentPoint上如果 axes 的XLim、YLim被用戶縮放比如誤觸了工具欄的放大按鈕那么CurrentPoint返回的是數(shù)據(jù)坐標(biāo)落點會跑到 [0,1] 之外后面所有歸一化都基于錯誤的數(shù)據(jù)。我的做法是直接把工具欄關(guān)掉ToolBar,none并顯式鎖定XLim、YLim。這樣鼠標(biāo)位置和數(shù)據(jù)坐標(biāo)之間是簡單的比例關(guān)系中間不需要任何換算。4.3 重繪卡頓的定位過程與修復(fù)最初版本的繪制手感很差畫兩筆就開始拖影。排查過程大致是這樣先確認(rèn)是繪制環(huán)節(jié)還是計算環(huán)節(jié)——我在onMouseMove的開頭結(jié)尾加了tic/toc發(fā)現(xiàn)單次回調(diào)耗時不到 1ms說明計算沒問題。然后確認(rèn)幀率用簡單的計數(shù)器統(tǒng)計每秒觸發(fā)的 motion 事件數(shù)結(jié)果只有十幾幀而系統(tǒng)事件隊列本身能提供 60。問題定位到重繪策略上。原來的寫法是每次移動都調(diào)用plot(axDraw, x, y)。plot每次都會清空 axes 并重建所有圖形對象即使只有一個 Line 這也是相對重的操作。改法有兩條第一條是不復(fù)建對象只改數(shù)據(jù)。一開始就創(chuàng)建一個Line句柄之后每次只更新XData/YData% 初始化時 hLine animatedline(axDraw, Color, [0.1 0.4 0.8], LineWidth, 2); % 移動時 addpoints(hLine, p(1), p(2)); drawnow limitrate;animatedline就是為了這類增量繪制設(shè)計的配合drawnow limitrate限制到大約每秒 20 幀效果立竿見影。注意必須給animatedline設(shè)定MaximumNumPoints否則長軌跡會積累上萬個點性能反而崩掉。我設(shè)的是 2048。第二條是把識別計算從繪制回調(diào)里剝離出來。識別只在MouseUp時觸發(fā)一次不要放在MouseMove里跑。早期版本我圖省事在移動時就實時算距離顯示在界面上結(jié)果每幀 6 個模板 × 1.8ms ≈ 11ms直接鎖死主線程。改成松手才計算之后拖拽立刻順滑。修復(fù)后我重新測了一輪64 點軌跡、8 個模板、滿窗口 DTW一次完整識別耗時約 15ms用戶完全感知不到延遲。5. 最近鄰分類器與模板庫的工程化處理算法和界面都有了剩下的就是把它們組織成一個能給出答案的分類器。這一層看起來最簡單——算距離、取最小——但里面的決策細(xì)節(jié)直接決定最終準(zhǔn)確率也是我在項目后期反復(fù)調(diào)整的地方。5.1 模板庫怎么選單模板、多模板與類別不平衡最樸素的方案是每類手勢存一個模板通常是用第一遍畫的待測軌跡和每個模板比一次取最近的。這套方案的可解釋性最好——界面上能明確顯示最像圓圈模板用戶容易接受。但它的問題在類內(nèi)方差。同一個圓圈有人起筆在頂、有人起筆在左單模板只能覆蓋其中一種風(fēng)格。我的改進(jìn)方案是每類存三個模板用 k-近鄰的思路投票分別算出待測軌跡到三個模板的距離取最小值作為類別距離或者對前 k 個最近鄰跨類別做加權(quán)投票。function [label, score] classify(P, templates, metricFn, k) % templates : struct每個字段是 N x M 的軌跡矩陣M 個模板堆疊 names fieldnames(templates); allD []; allL {}; for i 1:numel(names) T templates.(names{i}); for m 1:size(T, 1) / 64 seg T((m-1)*641 : m*64, :); allD(end1, 1) metricFn(P, seg); allL{end1, 1} names{i}; end end [ds, idx] sort(allD, ascend); k min(k, numel(ds)); win allL(idx(1:k)); label mode(win); score ds(1); end模板的采集要專門做一輪每種手勢讓同一個人畫 5 遍從中挑 3 個兩兩距離最分散的作為模板而不是隨便取前三個。選擇方法是先算 5 個候選之間的距離矩陣貪心地選第一個、離它最遠(yuǎn)的第二個、離前兩個距離和最大的第三個。這個技巧把留一法準(zhǔn)確率提高了大約 4 個百分點成本只是多寫二十行代碼。類不平衡的問題也不能忽略。圓圈可能收集了 20 條閃電只有 5 條那么圓形因為模板多天然更容易被選中。簡單處理是限定每個類別參與投票的模板數(shù)相同或者對類別距離做歸一化。5.2 距離歸一化與拒識邏輯三種度量的原始數(shù)值范圍差得很遠(yuǎn)。在歸一化坐標(biāo)系下DTW 除以 N 后的典型值在 0.020.5 之間離散 Fréchet 在 0.050.8 之間Hausdorff 在 0.010.4 之間。直接拿絕對值做閾值沒有可比性我在界面上顯示的置信度是相對值最小距離與次小距離的比值。if numel(ds) 2 ratio ds(2) / max(ds(1), 1e-9); % 越大越可信 conf 1 - exp(-(ratio - 1)); % 映射到 (0,1) else conf 0.5; end這個比值的解釋非常直觀如果第一名和第二名差距很大說明這個判斷很確定如果兩個類別距離接近說明系統(tǒng)自己也在猶豫。拒識是另一個必須有的機(jī)制。用戶隨手亂畫一條線如果系統(tǒng)硬要給出一個答案體驗會很糟。我的做法是設(shè)兩道閘絕對距離超過閾值用模板庫自匹配的 95 分位做參考值或者置信度低于 0.3都判為未識別。閾值的確定不能憑感覺要拿交叉驗證的距離分布來定——把所有留一法的正確匹配距離收集起來取 95 分位作為上限。5.3 自建小樣本上的實測結(jié)果與失敗案例分析我在自己的小數(shù)據(jù)集上跑了一輪留一法8 類手勢、每類 6 條共 48 條每次留一條做測試其余做模板。結(jié)果如下必須說明樣本量很小這些數(shù)字只能看相對趨勢不能當(dāng)基準(zhǔn)度量方式留一法準(zhǔn)確率單次匹配耗時64 點主要錯誤類型DTW全窗口91.7%約 1.8 ms回勾被判成橫線DTW帶寬 0.1589.6%約 0.6 ms同上誤差更多離散 Fréchet85.4%約 1.5 ms采樣稀疏的手勢距離虛高Hausdorff雙向68.8%約 0.25 ms起筆抖動點導(dǎo)致整條誤判Hausdorff95 分位70.8%約 0.30 ms同上略有改善DTW 輸?shù)舻哪且焕苡幸馑家粋€橫線加右側(cè)回勾被認(rèn)成了純橫線。查了對齊矩陣才發(fā)現(xiàn)純橫線模板在末尾有一段點密集區(qū)因為那次畫的時候手慢采到的點多DTW 就把回勾的那段點都對到了這段密集區(qū)上累計代價并沒有明顯升高。后來改用 Fréchet 做這個二分類的判別因為 Fréchet 取最大值回勾那一段的最大偏離一下子暴露出來了距離從 0.04 跳到 0.21干凈利落地分開。這個案例讓我形成了一個實用經(jīng)驗DTW 擅長判斷整體形狀是否一致Fréchet 擅長判斷是否存在局部嚴(yán)重偏離。如果兩類手勢的區(qū)別在于某個局部細(xì)節(jié)有沒有鉤、拐了幾個彎Fréchet 更靠譜如果區(qū)別在整體輪廓圓 vs 三角DTW 更穩(wěn)。Hausdorff 的錯誤集中在起筆位置。有一條閃電手勢被認(rèn)成了勾因為兩者都是鋸齒狀的折線點集分布高度相似Hausdorff 根本區(qū)分不出來——這印證了前面說的丟失順序信息是原理性的缺陷不是實現(xiàn)能補(bǔ)的。我最終的方案是兩級串聯(lián)先用 Hausdorff 快速篩出距離最小的 4 個候選這一步幾乎不耗時再在這 4 個候選上用 DTW 和 Fréchet 的距離加權(quán)權(quán)重 0.6 / 0.4做最終判定。這個組合在留一法上跑到 93.8%比任何一個單一度量都好。加權(quán)系數(shù)的來源是簡單網(wǎng)格搜索0.0 到 1.0 步長 0.1 掃了一遍最優(yōu)點很平緩說明結(jié)果對這個參數(shù)不敏感可以放心用。6. 換個數(shù)據(jù)源之后失效的地方幾個已驗證的邊界代碼寫完能跑和這個方案能用中間還隔著一堆邊界條件。我在往其他場景遷移這套東西的時候撞上了幾個明確的失效區(qū)寫出來省得別人再走一遍。6.1 從鼠標(biāo)點到骨架點采樣噪聲的量級完全變了鼠標(biāo)軌跡的噪聲主要來自事件合并和手抖量級在幾個像素。換成攝像頭采集的骨架關(guān)鍵點噪聲會突然放大到十幾個像素而且?guī)g抖動——同一個靜止的姿勢關(guān)鍵點坐標(biāo)在相鄰幀之間會跳。這時候原來的 95 分位 Hausdorff 就不夠用了因為噪聲點是遍布整條軌跡的不是集中在起筆那一兩個孤立點。我在這個場景下的處理是加一層時域平滑對每個坐標(biāo)維度做 5 點滑動平均或者用簡單的一階低通濾波function P smoothTrajectory(P, alpha) % alpha 越小越平滑0.3 左右是個不錯的起點 for i 2:size(P,1) P(i,:) alpha * P(i,:) (1 - alpha) * P(i-1,:); end end平滑必須放在重采樣之前否則重采樣已經(jīng)把點拉到等間距再平滑會改變采樣點的弧長分布引入新的偏差。這個順序反了曲線會被吃掉拐角看起來鈍鈍的。另外骨架點的采樣率是固定的比如 30fps這意味著原始序列的時間等距是可信的這時候等距重采樣反而會破壞時間信息——如果動作的節(jié)奏本身有語義快揮和慢揮是不同指令就該保留時間采樣改用按時間加權(quán)的 DTW 代價。6.2 多筆手勢與分段匹配現(xiàn)實里的手勢經(jīng)常不是一筆畫完的比如畫一個需要兩筆米需要四筆。直接把這些點連成一條序列交給 DTW會在筆畫之間的跳躍處引入巨大的虛假位移——筆尖離開畫布的瞬間上一個筆畫終點和下一個筆畫起點之間的連線被當(dāng)成了一段真實的軌跡。解決辦法是按筆畫分段段內(nèi)匹配、段間求和。每一段獨立做重采樣和歸一化縮放要按整組筆畫統(tǒng)一的包圍盒不能每段各自歸一化否則相對大小信息丟失然后總距離是各段距離的加權(quán)和function D multiStrokeDistance(A, B, metricFn) % A, B : cell 數(shù)組每個元素是一筆的 N x 2 軌跡 if numel(A) ~ numel(B) D inf; return; % 筆畫數(shù)不同直接判不匹配 end D 0; for k 1:numel(A) D D metricFn(A{k}, B{k}); end D D / numel(A); end筆畫數(shù)不同直接判不匹配這個策略簡單但有效因為幾筆本身就是很強(qiáng)的語義特征。代價是容忍不了用戶多畫或少畫一筆所以我在界面上給了一個允許分筆對其的備選模式用動態(tài)規(guī)劃找最優(yōu)的分段對應(yīng)關(guān)系——不過這條路徑我只在實驗里跑通最終沒放進(jìn)主流程因為它引入了太多需要調(diào)的參數(shù)收益并不明顯。還有一點值得記下來同一筆畫的反向繪制。DTW 和 Fréchet 都要求單調(diào)前進(jìn)用戶如果習(xí)慣了從右往左畫橫線遇到從左往右畫的模板距離會非常大。我的處理是給每個模板同時存一份反轉(zhuǎn)版本匹配時取兩者的較小值。成本是模板庫翻倍匹配耗時翻倍但對用戶友好度的提升很明顯——尤其在沒有明確指示該往哪個方向畫的界面上這個改動幾乎必須做。7. 我個人在調(diào)這套東西時沉淀的幾條判斷寫到這里我想收在幾個不屬于任何具體章節(jié)的經(jīng)驗上都是調(diào)試過程中反復(fù)驗證過的。先看數(shù)據(jù)再看算法。我見過太多人一上來就調(diào) DTW 的窗口、換距離函數(shù)實際上問題出在輸入軌跡本身——點數(shù)不一致、坐標(biāo)沒歸一化、有 NaN。加一段fprintf把每步預(yù)處理后的點數(shù)、取值范圍打出來五分鐘就能定位一半的算法不準(zhǔn)問題。距離的絕對值沒有意義相對排名才有意義。閾值和置信度不要拍腦袋定用留一法的距離分布推。這一點在換數(shù)據(jù)源時尤其重要我那套閾值在鼠標(biāo)數(shù)據(jù)上工作良好換到骨架點數(shù)據(jù)上全線失效就是因為分布整體平移了。三種度量別當(dāng)成互斥選項。它們度量的是不同側(cè)面DTW 看整體節(jié)奏對齊Fréchet 看局部最壞偏離Hausdorff 看空間覆蓋。把它們當(dāng)特征組合起來用比糾結(jié)哪個最好收益大得多。我最后那套兩級串聯(lián)的結(jié)構(gòu)代碼量只多了三十來行準(zhǔn)確率提了將近 7 個百分點。界面上一定要畫出對齊結(jié)果。不是為了好看是為了調(diào)試。DTW 的對齊路徑畫出來能一眼看出是某一段被壓縮了還是整體偏移比盯著一個數(shù)字調(diào)參高效太多。我那個axCompare小畫布后期基本成了主力調(diào)試工具比在命令行里打印距離矩陣直觀十倍。能跑通的最小版本要盡早跑通。這套東西我最初寫成三個獨立腳本加一個命令行驅(qū)動能跑出準(zhǔn)確率之后才動的界面。如果反過來先做界面調(diào)試算法時每次都要點鼠標(biāo)畫一筆才能看結(jié)果效率會低到讓人放棄。