基于K-means聚類算法的行走姿勢(shì)分類標(biāo)準(zhǔn)研究

徐偉，穆小旭，郭威

（中國(guó)人民公安大學(xué)研究生院，北京102623）

0 引言

在傳統(tǒng)足跡分析中關(guān)于行走姿勢(shì)只有通過(guò)觀察然后用語(yǔ)言敘述的形式對(duì)行走姿勢(shì)進(jìn)行分類，例如：軀干前傾、正?；蚝笱觯活^部的抬頭、平視和低頭等[1]。此類描述要求人們具有豐富的經(jīng)驗(yàn)和相關(guān)的專業(yè)知識(shí)，而對(duì)于沒(méi)有從事相關(guān)研究或?qū)I(yè)的人在描述行走姿勢(shì)時(shí)，對(duì)行走姿勢(shì)的描述差別很大。因此，如果能對(duì)行走姿勢(shì)進(jìn)行量化表示，通過(guò)數(shù)據(jù)的形式對(duì)不同的行走姿勢(shì)進(jìn)行分類，再結(jié)合經(jīng)驗(yàn)對(duì)量化后的行走姿勢(shì)分類標(biāo)準(zhǔn)進(jìn)行調(diào)整，制定出一個(gè)統(tǒng)一的分類標(biāo)準(zhǔn)，就能使大部分人對(duì)不同行走姿勢(shì)的分辨更加準(zhǔn)確，讓傳統(tǒng)足跡的研究更加科學(xué)。目前對(duì)行走姿勢(shì)進(jìn)行量化分類的研究很少，借助計(jì)算機(jī)技術(shù)對(duì)傳統(tǒng)足跡學(xué)進(jìn)行研究，不僅豐富了相關(guān)的研究方法而且讓研究?jī)?nèi)容更加科學(xué)。

K-means聚類算法是聚類算法中的一種，將離散的數(shù)據(jù)點(diǎn)通過(guò)k個(gè)質(zhì)心進(jìn)行聚類，分成k簇相似性較小的數(shù)據(jù)點(diǎn)的集合[2]。采用歐氏距離作為相似性的評(píng)價(jià)指標(biāo)，即兩個(gè)樣本之間距離越近其相似性就越大。K-means算法的具體步驟：預(yù)先設(shè)定k值并且將每個(gè)類的數(shù)據(jù)的中心作為初始質(zhì)心；根據(jù)初始質(zhì)心對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行距離計(jì)算逐個(gè)歸類，將數(shù)據(jù)點(diǎn)歸為離它最近的聚類點(diǎn)，歸入新的數(shù)據(jù)點(diǎn)后更新此類的均值；通過(guò)劃分后的均值進(jìn)行數(shù)次迭代達(dá)到最優(yōu)分類效果[3-4]。

從生理學(xué)上來(lái)看，人體行走姿勢(shì)是在大腦中樞的調(diào)節(jié)下，調(diào)動(dòng)身體各部位肌肉群相互配合，通過(guò)從年幼到成年的長(zhǎng)期行走鍛煉，形成個(gè)體特有的行走習(xí)慣，這些行走習(xí)慣一旦形成就會(huì)很難改變，最終形成運(yùn)動(dòng)動(dòng)力定型。所以人體行走時(shí)，身體各部位形成的行走姿勢(shì)具有一定的穩(wěn)定性[5-6]。因此對(duì)具有相似行走姿勢(shì)的不同人，對(duì)相似姿勢(shì)所采集的人體角度數(shù)據(jù)會(huì)分布在相近范圍內(nèi)，通過(guò)對(duì)角度數(shù)據(jù)進(jìn)行分類，就會(huì)得到不同行走姿勢(shì)的分類標(biāo)準(zhǔn)。而K-means聚類算法的聚類核心就是通過(guò)對(duì)研究對(duì)象進(jìn)行相似度計(jì)算，把性質(zhì)相近的對(duì)象進(jìn)行分類。因此使用K-means聚類算法對(duì)角度數(shù)據(jù)進(jìn)行分類可以達(dá)到較好的數(shù)據(jù)分類效果。

1 實(shí)現(xiàn)過(guò)程

1.1 數(shù)據(jù)采集和處理

借助?？低暤囊曨l采集儀對(duì)公安大學(xué)年齡段在18～20歲之間的共317名學(xué)生進(jìn)行正常情況下側(cè)面和正面的行走姿勢(shì)進(jìn)行錄制。側(cè)面錄制攝像頭和行走方向垂直即與圖像成90°，正面錄制攝像頭和行走方向在同一直線上。側(cè)面和正面的視頻同時(shí)對(duì)一趟行走視頻進(jìn)行錄制。視頻錄制結(jié)束后，使用MATLAB對(duì)錄制的視頻進(jìn)行分幀處理。

行走姿勢(shì)主要部分涉及身體軀干、頭部和兩臂。對(duì)于分幀后的側(cè)面圖片選取位于鏡頭視野中部，且左腿或右腿垂直支撐階段的一幀圖片，正面圖像則選取視頻中視野適中雙臂張開(kāi)最大時(shí)的一幀圖片作為實(shí)驗(yàn)數(shù)據(jù)圖片。

所選圖片用Photoshop軟件進(jìn)行處理。側(cè)面照片用于生成頭部數(shù)據(jù)和軀干數(shù)據(jù)。身體軀干為人體側(cè)面髖關(guān)節(jié)到肩關(guān)節(jié)。由于實(shí)驗(yàn)條件限制，所拍攝的視頻中人物衣物寬松，無(wú)法確定髖關(guān)節(jié)的位置。因此，選取人行走時(shí)的垂直支撐階段即支撐腿和軀干成一條直線的狀態(tài)為軀干，此時(shí)取水平線與腳跟到肩關(guān)節(jié)連線的夾角α作為軀干姿勢(shì)的數(shù)據(jù)。人體頭部側(cè)面取耳朵最高點(diǎn)與眼睛的連線與地面垂線的夾角β作為頭部姿勢(shì)的數(shù)據(jù)。人體行走正面圖取頭頂最高點(diǎn)垂線與最高點(diǎn)與其中一個(gè)手臂的夾角γ作為手臂姿勢(shì)數(shù)據(jù)。收集到軀干角度、頭部角度和兩臂角度數(shù)據(jù)。見(jiàn)圖1。

圖1

1.2 聚類過(guò)程

（1）采集317名學(xué)生的軀干、頭部和兩臂角度數(shù)據(jù)。

（2）選擇歐氏距離進(jìn)行樣本數(shù)據(jù)計(jì)算得出距離矩陣進(jìn)行聚類。距離公式

（3）通過(guò)觀察數(shù)據(jù)的散點(diǎn)圖，分析數(shù)據(jù)分布情況，并且用層次聚類來(lái)確定初始類別數(shù)。

（4）畫(huà)出聚類圖，展示分類效果。

（5）頭部數(shù)據(jù)、兩臂數(shù)據(jù)處理過(guò)程同步驟（1）-（4）。

2 結(jié)果與分析

2.1 實(shí)驗(yàn)結(jié)果

做出角度數(shù)據(jù)的散點(diǎn)圖和層次聚類圖。散點(diǎn)圖的縱軸表示學(xué)生序號(hào)，橫軸表示角度數(shù)據(jù)，見(jiàn)圖2。層次聚類樹(shù)，見(jiàn)圖3。

在確定初始分類k值時(shí)，一種方法可以通過(guò)傳統(tǒng)足跡里對(duì)軀干、頭部和兩臂的分類來(lái)確定k值；另一種方法通過(guò)層次聚類法來(lái)確定初始k值。層次聚類通過(guò)相似度計(jì)算，即使用歐氏距離計(jì)算出樣本之間的距離矩陣，再用平均值算法計(jì)算出系統(tǒng)聚類樹(shù)[7-8]。層次聚類一般有兩種聚類方式，自下而上和自上而下。本文采用自下而上的方式進(jìn)行。

表1 傳統(tǒng)足跡行走姿勢(shì)分類

傳統(tǒng)足跡分類中對(duì)軀干、頭部和兩臂的分類多種多樣，在此采用多數(shù)資料中統(tǒng)一采用的行走姿勢(shì)分類即軀干、頭部和兩臂的分類數(shù)均為3，見(jiàn)表1。使用層次聚類時(shí)，x軸表示樣本編號(hào)，縱軸表示層次樹(shù)高度，由于編號(hào)太多x軸上不予全部顯示。做與x軸平行的水平線，從上到下平移，與聚類樹(shù)相交，有幾個(gè)交點(diǎn)表明可以將數(shù)據(jù)分為幾類。由于類別可以有很多種選擇，因此可以根據(jù)自己需要選擇合適分類個(gè)數(shù)。由圖3可以看出可以將軀干分為3類，頭部分為2類或4類，兩臂分為3類較為合適。綜合以上兩種方法，將軀干初始設(shè)置為3，頭部設(shè)置為2或3，兩臂設(shè)置為3。其中通過(guò)多次實(shí)驗(yàn)將頭部在初始k值設(shè)置為3時(shí)，可以達(dá)到很好分類效果，因此頭部聚類結(jié)果選取類別為3時(shí)作為展示。

圖2

經(jīng)過(guò)K-means聚類運(yùn)算，得出軀干、頭部和兩臂中三類各自的聚類結(jié)果以及聚類后的質(zhì)心數(shù)據(jù)，見(jiàn)圖4。

圖3

表2 分類后質(zhì)心角度數(shù)

通過(guò)對(duì)數(shù)據(jù)的分類結(jié)果分別確定軀干、頭部和兩臂的角度分類標(biāo)準(zhǔn)。見(jiàn)表3，表4，表5。

表3 軀干角度分類標(biāo)準(zhǔn)

表4 頭部角度分類標(biāo)準(zhǔn)

表5 兩臂角度分類標(biāo)準(zhǔn)

2.2 結(jié)論與誤差分析

（1）軀干、頭部和兩臂的分類標(biāo)準(zhǔn)見(jiàn)表5。

（2）自然行走狀態(tài)下軀干正常時(shí)質(zhì)心值為90.5°，此數(shù)值符合人體正常行走時(shí)軀干與地面垂直的行走狀態(tài)，軀干正常的角度分布范圍在88.4°≤α≤92.4°之間，在于正常行走狀態(tài)下身體不可避免的略微向前或向后擺動(dòng)，符合人體行走正常狀態(tài)下的容差范圍。頭部平視時(shí)質(zhì)心值為 87.1°，角度分布范圍為 78.4°≤β≤94.5°。正常情況下，平視時(shí)眼睛水平線應(yīng)與地面成90°角。但是實(shí)際行走過(guò)程中，我們會(huì)注意前行路況，因此實(shí)驗(yàn)質(zhì)心值小于90°。雙臂前后擺動(dòng)時(shí)質(zhì)心值為8.1°，角度分布范圍為4.9°≤γ≤10.8°，質(zhì)心值與范圍起點(diǎn)相差較大因?yàn)椴杉瘮?shù)據(jù)的學(xué)生來(lái)源為警校生，長(zhǎng)期的訓(xùn)練使他們?cè)谛凶邥r(shí)雙臂自然向體前收縮，因此測(cè)量出的正常行走雙臂角度數(shù)據(jù)偏向體前擺動(dòng)。

（3）對(duì)分類后所在類別的人數(shù)進(jìn)行統(tǒng)計(jì)，得出自然行走狀態(tài)下軀干正常的人數(shù)為216人，頭部平視人數(shù)196人，兩臂前后擺動(dòng)人數(shù)231人。數(shù)據(jù)顯示在317名

青年人中大部分人行走姿勢(shì)正常。前傾中有3人前傾程度大于正常值，一方面原因在于行走速度過(guò)快，另一方面由于自身身體習(xí)慣性佝背導(dǎo)致的測(cè)量數(shù)據(jù)異常。頭部仰頭和低頭數(shù)據(jù)未有大偏差。兩臂角度數(shù)據(jù)中有2人行走過(guò)程中顯示未擺臂，原因在于這兩名實(shí)驗(yàn)對(duì)象日常行走兩臂擺動(dòng)幅度較小，在運(yùn)用Photoshop進(jìn)行角度標(biāo)注時(shí)，不能對(duì)小幅度擺動(dòng)進(jìn)行精確的角度測(cè)量。

（4）在運(yùn)用Photoshop對(duì)圖像進(jìn)行角度數(shù)據(jù)測(cè)量時(shí)，人工標(biāo)點(diǎn)連線時(shí)存在選取點(diǎn)不準(zhǔn)，同時(shí)角度數(shù)據(jù)特別敏感，容易造成大的測(cè)量誤差，影響分類標(biāo)準(zhǔn)的范圍確定。此類誤差可以通過(guò)對(duì)相同對(duì)象圖像進(jìn)行多次的角度測(cè)量取其平均值來(lái)減小誤差。

圖4

3 結(jié)語(yǔ)

本文通過(guò)對(duì)自然行走狀態(tài)下的人體各部位進(jìn)行劃分，利用Photoshop軟件對(duì)各部位角度進(jìn)行數(shù)據(jù)收集，使用傳統(tǒng)足跡中行走姿勢(shì)分類標(biāo)準(zhǔn)和層次聚類的方法確定初始k值，最后通過(guò)K-means聚類算法對(duì)角度數(shù)據(jù)進(jìn)行聚類，得到了一種通過(guò)角度數(shù)據(jù)對(duì)行走姿勢(shì)進(jìn)行分類的標(biāo)準(zhǔn)。此標(biāo)準(zhǔn)有助于我們將來(lái)對(duì)行走姿勢(shì)下包含的各類因素進(jìn)行深入研究。由于實(shí)驗(yàn)條件限制，采集實(shí)驗(yàn)樣本人數(shù)小，年齡段集中在18～20歲之間，角度測(cè)量工具誤差大，且采集數(shù)據(jù)過(guò)程中實(shí)驗(yàn)對(duì)象在視頻錄制下難以保持正常行走狀態(tài)，實(shí)驗(yàn)結(jié)果無(wú)法適應(yīng)所有年齡段行走姿勢(shì)分類標(biāo)準(zhǔn)，但是在對(duì)青年人行走姿勢(shì)研究方面還是具有相關(guān)參考價(jià)值。本文下一步將就從身高、性別、胖瘦和擴(kuò)大樣本采集量等方面進(jìn)行深入研究，并且優(yōu)化聚類算法同時(shí)使用其他算法進(jìn)行數(shù)據(jù)處理，以便得到更加科學(xué)的分類標(biāo)準(zhǔn)。

參考文獻(xiàn)：

[1]史力民.足跡學(xué)[M].中國(guó)人民公安大學(xué)出版社,2007.

[2]Hartigan JA,WongM A.Algorithm AS 136:AK-Means Clustering Algorithm[J].Applied Statistics，1979，28（1）：100-108.

[3]李飛,薛彬,黃亞樓.初始中心優(yōu)化的K-Means聚類算法[J].計(jì)算機(jī)科學(xué),2002,29（7）：94-96.

[4]Selim SZ,IsmailM A.K-Means-Type Algorithms:AGeneralized Convergence Theorem and Characterization of Local Optimality[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,1984,6（1）：81-7.

[5]錢(qián)競(jìng)光,宋雅偉,葉強(qiáng),等.步行動(dòng)作的生物力學(xué)原理及其步態(tài)分析[J].南京體育學(xué)院學(xué)報(bào)（自然科學(xué)版）,2006,5（4）:1-7.

[6]喬曉曉.人體行走運(yùn)動(dòng)與行走姿態(tài)的影響[J].產(chǎn)業(yè)與科技論壇,2016,15（5）:63-64.

[7]吳帆,李石君.一種高效的層次聚類分析算法[J].計(jì)算機(jī)工程,2004,30（9）:70-71.

[8]胡學(xué)鋼,王東波,吳共慶.一種基于層次樹(shù)的高效密度聚類算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2008,31（2）:187-190.