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