用于指尖定位的多目標(biāo)分布估計(jì)算法

劉 可， 鞏敦衛(wèi)

(1.商丘師范學(xué)院 電子電氣工程學(xué)院，河南 商丘 476000； 2.中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221116)

0 引言

一般來(lái)說(shuō)，某一指尖的位置，就是該指尖區(qū)域中心的坐標(biāo). 人們利用指尖區(qū)域的特征，能夠從手部區(qū)域中得到所有指尖的位置，這一圖像處理的過(guò)程就是指尖定位. 目前，解決指尖定位問題的方法有：基于人手骨架的方法、基于手部邊緣曲率的方法等.

在手部區(qū)域中，指尖區(qū)域位于手指區(qū)域的最外部. 與人手的其他區(qū)域相比，指尖區(qū)域具有兩個(gè)特點(diǎn): 一是指尖區(qū)域的人手邊界形狀最接近半圓弧，二是指尖區(qū)域與手掌中心的距離最遠(yuǎn). 根據(jù)這兩個(gè)特點(diǎn)，文獻(xiàn)[1]提出了用于選擇指尖區(qū)域像素點(diǎn)的多目標(biāo)優(yōu)化模型. 通過(guò)求解這一優(yōu)化模型，能夠得到某一手部區(qū)域中的所有指尖區(qū)域像素點(diǎn). 根據(jù)指尖伸出的數(shù)量，對(duì)得到的指尖區(qū)域像素點(diǎn)進(jìn)行聚類，能夠得到任一指尖區(qū)域的像素點(diǎn). 然后，對(duì)于某一指尖區(qū)域的所有像素點(diǎn)計(jì)算它們的坐標(biāo)的平均值，這一平均值就是指尖區(qū)域中心的坐標(biāo). 對(duì)于上述指尖定位的優(yōu)化模型，為了得到比較準(zhǔn)確的指尖位置，需要保證選擇出的指尖區(qū)域像素點(diǎn)是準(zhǔn)確的. 由此可見，在求解指尖定位的優(yōu)化模型時(shí)，采用適合的求解方法，才能保證選擇出準(zhǔn)確的指尖區(qū)域像素點(diǎn).

筆者對(duì)求解指尖定位優(yōu)化模型的分布估計(jì)算法進(jìn)行研究，提出決策變量的維數(shù)、種群規(guī)模、最大采樣方差、最小采樣方差等分布估計(jì)算法的主要參數(shù). 當(dāng)這些主要參數(shù)均取最佳值時(shí)，得到的指尖中心位置最接近其真實(shí)的位置.

本研究有3個(gè)方面的貢獻(xiàn): ①對(duì)于求解指尖定位優(yōu)化模型的分布估計(jì)算法，提出了它的主要參數(shù)； ②提出這些主要參數(shù)均存在最佳值； ③通過(guò)實(shí)際手部圖像中的指尖定位實(shí)驗(yàn)，證明了所提參數(shù)及其最佳值的有效性.

1 相關(guān)工作

1.1 指尖定位

文獻(xiàn)[2]計(jì)算了手部邊緣曲線上所有像素點(diǎn)的曲率，進(jìn)而給出某一閾值；如果某一像素點(diǎn)的曲率大于這一閾值，就認(rèn)為該像素點(diǎn)的位置是指尖的位置. 文獻(xiàn)[3]把指尖定位的過(guò)程分為兩個(gè)階段，第一個(gè)階段進(jìn)行粗定位，第二個(gè)階段進(jìn)行精確定位， 這樣可以在不同的尺度上對(duì)定位的精度進(jìn)行調(diào)節(jié).

近年來(lái)，很多新的方法和技術(shù)在指尖定位領(lǐng)域出現(xiàn). 文獻(xiàn)[4]通過(guò)計(jì)算手部邊界曲線包含的凸多邊形，得到多個(gè)候選的指尖位置，進(jìn)而選擇出指尖的準(zhǔn)確位置. 文獻(xiàn)[5]在手部邊界曲線上均勻地選擇出一系列的像素點(diǎn)，計(jì)算其中的任一像素點(diǎn)與手掌中心的距離，然后通過(guò)比較這些像素點(diǎn)的距離值，得到指尖位置的像素點(diǎn).

1.2 分布估計(jì)算法

生產(chǎn)生活中的很多實(shí)際問題都能夠歸結(jié)為優(yōu)化問題.有些優(yōu)化問題中存在多個(gè)目標(biāo)函數(shù)，它們可稱為多目標(biāo)優(yōu)化問題[6-7]. 進(jìn)化算法模擬生物種群的進(jìn)化過(guò)程，能夠有效地求解多目標(biāo)優(yōu)化問題[8].

對(duì)于某些多目標(biāo)優(yōu)化問題，其中的任一問題的最優(yōu)解集具有一定的分布規(guī)律，并且，在求解前，這一分布規(guī)律是已知的. 如果在這一問題的求解過(guò)程中，進(jìn)化算法利用最優(yōu)解集的分布規(guī)律，得到臨時(shí)種群，那么，這一進(jìn)化算法可稱為分布估計(jì)算法. 分布估計(jì)算法利用了最優(yōu)解集的分布規(guī)律，因此,它與一般的進(jìn)化算法相比，具有理論上的優(yōu)勢(shì).

文獻(xiàn)[9]提出了基于規(guī)則模型的多目標(biāo)分布估計(jì)算法. 文獻(xiàn)[10]根據(jù)手部像素點(diǎn)的坐標(biāo)分布在某一區(qū)間以內(nèi)，并且手部像素點(diǎn)分布在某些直線段的兩側(cè)，建立了用于選擇手部像素點(diǎn)的多目標(biāo)分布估計(jì)算法.

2 指尖定位的求解方法

2.1 算法流程

與手部其他區(qū)域的像素點(diǎn)相比，指尖區(qū)域的像素點(diǎn)也具有兩個(gè)特點(diǎn)： 一是指尖像素點(diǎn)對(duì)應(yīng)的人手邊界形狀最接近半圓弧，二是指尖像素點(diǎn)與手掌中心的距離最遠(yuǎn).如果手部像素點(diǎn)具有上述兩個(gè)特點(diǎn)，我們就可以認(rèn)為這些手部像素點(diǎn)是指尖像素點(diǎn).

文獻(xiàn)[6]根據(jù)指尖像素點(diǎn)的兩個(gè)特點(diǎn)，提出了選擇指尖像素點(diǎn)的多目標(biāo)優(yōu)化模型. 該模型用于從手部像素點(diǎn)中選擇出一系列指尖像素點(diǎn). 該模型的表達(dá)式如下：

(1)

式中:X是模型的決策空間，它是某一含有人手的圖像中，手部區(qū)域包含的所有像素點(diǎn)的集合； 2X是X的冪集；x是決策變量，它是位置互不重合的像素點(diǎn)的集合，它的表達(dá)式是x=(x1,x2,…,xn),xi=(xi,yi),i=1,2,…,n,n是決策變量中包含的像素點(diǎn)個(gè)數(shù).

目標(biāo)函數(shù)f1(x)使選取的像素點(diǎn)對(duì)應(yīng)的人手邊界形狀最接近半圓?。荒繕?biāo)函數(shù)f2(x)使選取的像素點(diǎn)與手掌中心的距離最遠(yuǎn).

目標(biāo)函數(shù)f1(x)的數(shù)學(xué)表示：

(2)

式中:Z1(xi)是xi對(duì)應(yīng)的人手邊界形狀與半圓弧的相似程度,Z1(xi)的數(shù)值越小，表明這一人手邊界形狀越接近半圓弧.

目標(biāo)函數(shù)f2(x)的數(shù)學(xué)表示：

(3)

式中:Z2(xi)為xi與手掌中心的距離.

通過(guò)求解模型(1)，能夠得到一系列位于指尖區(qū)域的像素點(diǎn). 模型(1)的最優(yōu)解集，包含一系列的指尖像素點(diǎn). 另外，這些指尖像素點(diǎn)分布在多個(gè)指尖區(qū)域中心的周圍，或者說(shuō)，這些指尖像素點(diǎn)分布在多個(gè)點(diǎn)的周圍. 因此，模型(1)的最優(yōu)解集具有一定的分布規(guī)律. 這一分布規(guī)律是模型(1)的最優(yōu)解分量xi分布在多個(gè)點(diǎn)的周圍.

文獻(xiàn)[6]根據(jù)模型(1)最優(yōu)解集的上述分布規(guī)律，提出了用于求解該模型的多目標(biāo)分布估計(jì)算法. 這一算法的流程如下.

步驟1 令迭代次數(shù)t=0，在決策空間中隨機(jī)采樣，產(chǎn)生初始種群P(0)；

步驟2 如果迭代次數(shù)t增加到最大值，停止迭代，輸出種群P(t)的最優(yōu)解集；

步驟3 根據(jù)P(t)的最優(yōu)解集，建立多個(gè)點(diǎn)作為候選解分量xi的概率分布模型；

步驟4 在上述多個(gè)點(diǎn)附近采樣，得到臨時(shí)種群Q(t)；

步驟5 采用快速非支配排序的方法，在P(t)和Q(t)的合并種群中，選擇出子代種群P(t+1)；

步驟6 令t=t+1，轉(zhuǎn)至步驟2.

上述算法流程中，P(0)、P(t)、Q(t)、P(t+1)中個(gè)體的數(shù)量均是N.

2.2 概率分布模型

對(duì)于一個(gè)人的手，如果其伸出的指尖數(shù)量是K，其指尖區(qū)域的像素點(diǎn)分布在K個(gè)指尖區(qū)域中心附近. 對(duì)于模型(1)的最優(yōu)解集，其包含的指尖像素點(diǎn)也分布在這K個(gè)中心點(diǎn)的附近.

在上述分布估計(jì)算法的流程中，對(duì)于每一代的種群P(t)，其最優(yōu)解集包含的像素點(diǎn)可以認(rèn)為分布在K個(gè)中心點(diǎn)附近. 算法經(jīng)過(guò)多次迭代之后，這K個(gè)中心點(diǎn)的位置會(huì)逐漸接近K個(gè)指尖區(qū)域中心的位置. 同時(shí)，隨著種群P(t)的進(jìn)化，其最優(yōu)解集也會(huì)逐漸接近模型(1)的最優(yōu)解集. 由此可見，在每一次迭代過(guò)程中，可以把種群P(t)的K個(gè)中心點(diǎn)作為候選解分量xi的概率分布模型.

對(duì)于種群P(t)的最優(yōu)解集包含的所有像素點(diǎn)，計(jì)算任意兩個(gè)像素點(diǎn)之間的距離進(jìn)而根據(jù)它們之間的距離，采用K-means聚類算法，把它們分成K類. 對(duì)于每一類中的所有像素點(diǎn)，其中心位置就是上述P(t)的某一個(gè)中心點(diǎn)的位置. 這樣，就得到種群P(t)的K個(gè)中心點(diǎn)的位置，它們也是本次迭代的過(guò)程中候選解分量xi的概率分布模型.

由模型(1)可知，如果決策變量x的維數(shù)比較大，x中包含的像素點(diǎn)個(gè)數(shù)也比較大，那么種群P(t)的最優(yōu)解集包含的像素點(diǎn)，其數(shù)量也比較大. 如果種群P(t)中個(gè)體的數(shù)量，即種群的規(guī)模比較大，那么一般情況下，P(t)中最優(yōu)解的數(shù)量比較大，因此P(t)的最優(yōu)解集包含的像素點(diǎn)其數(shù)量也比較大.

當(dāng)P(t)的最優(yōu)解集包含的像素點(diǎn)比較多時(shí)，這些像素點(diǎn)中存在指尖像素點(diǎn)的可能性就會(huì)比較大，那么通過(guò)對(duì)這些像素點(diǎn)進(jìn)行K-means聚類得到的K個(gè)中心點(diǎn)的位置就會(huì)更加接近K個(gè)指尖區(qū)域中心的位置.

由此可見，如果決策變量的維數(shù)比較大，或者種群的規(guī)模比較大，根據(jù)其建立的K個(gè)中心點(diǎn)的位置，即候選解分量xi的概率分布模型就會(huì)更加準(zhǔn)確.

另外，如果P(t)的最優(yōu)解集包含的像素點(diǎn)比較多，對(duì)這些像素點(diǎn)進(jìn)行K-means聚類，就需要迭代更多的次數(shù)，那么該聚類方法的計(jì)算時(shí)間就會(huì)增加. 因此，如果決策變量的維數(shù)比較大，或者種群的規(guī)模比較大，聚類的計(jì)算時(shí)間會(huì)比較長(zhǎng).

如果對(duì)決策變量的維數(shù)和種群規(guī)模均合理取值，這樣能夠使指尖定位的求解方法在比較短的計(jì)算時(shí)間內(nèi)，得到比較準(zhǔn)確的最優(yōu)解集，那么決策變量的維數(shù)和種群規(guī)模的數(shù)值都是最佳值.

2.3 采樣

對(duì)于模型(1)的最優(yōu)解集，其包含的指尖像素點(diǎn)分布在K個(gè)指尖區(qū)域中心的附近. 因此，對(duì)于上述候選解分量的概率分布模型，在其K個(gè)中心點(diǎn)的附近采樣，就可能得到指尖像素點(diǎn). 通過(guò)這一采樣的方法，在決策空間中進(jìn)行一次采樣，得到一個(gè)候選解的分量xi，進(jìn)而通過(guò)n次采樣，得到一個(gè)候選解x.

令候選解x=φ. 對(duì)于概率分布模型中的K個(gè)中心點(diǎn)，基于任一點(diǎn)產(chǎn)生候選解分量的概率,均是同一數(shù)值.

采用如下的流程，產(chǎn)生一個(gè)候選解x.

步驟1 按照同一概率，從K個(gè)中心點(diǎn)中選擇出一個(gè)中心點(diǎn)；

步驟4 如果x中存在n個(gè)像素點(diǎn)，結(jié)束算法；否則，執(zhí)行步驟1.

在上述的采樣方法中，采樣方差λ決定了得到的候選解分量xi的分布范圍. 如果λ的數(shù)值與指尖區(qū)域的尺寸相似，采樣點(diǎn)的分布就比較符合指尖像素點(diǎn)的分布，那么，通過(guò)上述的采樣方法，就比較容易得到指尖區(qū)域的像素點(diǎn). 另外，根據(jù)上述的采樣方法，λ的數(shù)值由最大采樣方差和最小采樣方差決定. 因此，如果最大采樣方差和最小采樣方差的取值均比較合適，才能通過(guò)采樣得到指尖像素點(diǎn).

在模型(1)的求解過(guò)程中，最大采樣方差和最小采樣方差的取值過(guò)大，不利于種群的進(jìn)化和最優(yōu)解集的獲得；它們過(guò)小，也不利于種群的進(jìn)化和最優(yōu)解集的獲得.

如果最大采樣方差和最小采樣方差均合理取值，這樣能夠使指尖定位的求解方法得到比較準(zhǔn)確的最優(yōu)解集，那么最大采樣方差和最小采樣方差的數(shù)值都是最佳值.

3 實(shí)驗(yàn)部分

根據(jù)以上分析可知，決策變量的維數(shù)、種群規(guī)模、最大采樣方差、最小采樣方差是用于指尖定位的分布估計(jì)算法的主要參數(shù)，并且這些參數(shù)均存在最佳值.

采用NSGA-Ⅱ和MOCell作為對(duì)比方法，與所提的求解方法進(jìn)行比較. NSGA-Ⅱ通過(guò)交叉和變異操作，得到臨時(shí)種群.該算法的其他部分與所提的求解方法一致. MOCell在每次迭代過(guò)程中，均保存前幾代的一定數(shù)量的最優(yōu)個(gè)體，在這些最優(yōu)個(gè)體中，選擇一部分個(gè)體代替種群中相同數(shù)量的個(gè)體，進(jìn)而通過(guò)對(duì)種群進(jìn)行交叉和變異操作得到臨時(shí)種群. MOCell的其他部分與NSGA-Ⅱ一致.

采用文獻(xiàn)[6]中的標(biāo)準(zhǔn)美國(guó)手語(yǔ)圖像庫(kù)進(jìn)行指尖定位的實(shí)驗(yàn). 所用的手部區(qū)域圖像共630幅. 對(duì)于其中任一幅手部區(qū)域圖像，首先，根據(jù)選擇指尖像素點(diǎn)的多目標(biāo)優(yōu)化模型，計(jì)算每一個(gè)手部像素點(diǎn)的f1(x)和f2(x)；然后，采用所提方法求解模型(1)，得到一系列像素點(diǎn)，進(jìn)而對(duì)得到的像素點(diǎn)進(jìn)行聚類，并計(jì)算每一類像素點(diǎn)的中心位置；最后，把得到的指尖位置與真實(shí)的指尖區(qū)域中心位置比較，計(jì)算其誤差值. 實(shí)驗(yàn)中，采用文獻(xiàn)[6]中的方法，人工確定真實(shí)的指尖區(qū)域中心位置. 在求解模型(1)之前，對(duì)于任一個(gè)手部區(qū)域，指尖伸出的數(shù)量K是已知的.

在求解過(guò)程中，首先，決策變量的維數(shù)取60，種群規(guī)模取30，最大采樣方差取15，最小采樣方差取4； 然后，決策變量的維數(shù)分別取40、50、70、80，其他3個(gè)參數(shù)的取值不變. 種群規(guī)模分別取20、25、35、40，最大采樣方差分別取13、14、16、17，最小采樣方差分別取2、3、5、6. 當(dāng)一個(gè)參數(shù)的取值變化時(shí)，其他3個(gè)參數(shù)的取值不變. 除了這4個(gè)主要參數(shù)以外，其他參數(shù)的取值與文獻(xiàn)[6]一致.

實(shí)驗(yàn)使用的計(jì)算機(jī)配置：Intel Core i5-4590, 3.30 GHz CPU, 4.00 GB 內(nèi)存.

對(duì)于上述第121、301、491、506、551幅手部區(qū)域圖像，通過(guò)一次模型(1)的求解，得到一系列像素點(diǎn)，如圖1中的(a)～(e)所示. 圖1(a)～(e)中，伸出的指尖數(shù)量依次是5、4、3、3、2. 在這一求解過(guò)程中，決策變量的維數(shù)取60，種群規(guī)模取30，最大采樣方差取15，最小采樣方差取4.

圖1 所提方法得到的像素點(diǎn)集Fig.1 The pixel sets obtained by the proposed method

從圖1可以看出，采用所提算法，能夠得到指尖區(qū)域的一系列像素點(diǎn). 根據(jù)伸出的指尖數(shù)量，對(duì)得到的指尖像素點(diǎn)進(jìn)行聚類操作，能夠得到每一個(gè)指尖區(qū)域的一系列像素點(diǎn)，進(jìn)而得到該指尖區(qū)域中心的位置.

決策變量的維數(shù)分別取40、50、60、70、80，種群規(guī)模取30，最大采樣方差取15，最小采樣方差取4，所有手部圖像的平均誤差值和計(jì)算時(shí)間如表1所示. 種群規(guī)模分別取20、25、30、35、40，決策變量的維數(shù)取60，最大采樣方差取15，最小采樣方差取4時(shí)，所有手部圖像的平均誤差值和計(jì)算時(shí)間如表2所示. 最大采樣方差分別取13、14、15、16、17，決策變量的維數(shù)取60，種群規(guī)模取30，最小采樣方差取4，所有手部圖像的平均誤差值如表3所示. 最小采樣方差分別取2、3、4、5、6，決策變量的維數(shù)取60，種群規(guī)模取30，最大采樣方差取15，所有手部圖像的平均誤差值如表4所示.

表1 決策變量維數(shù)的實(shí)驗(yàn)結(jié)果Tab.1 Experiment results of decision variable dimension

表2 種群規(guī)模的實(shí)驗(yàn)結(jié)果Tab.2 Experiment results of population size

表3 最大采樣方差的實(shí)驗(yàn)結(jié)果Tab.3 Experiment results of maximum sampling variance

表4 最小采樣方差的實(shí)驗(yàn)結(jié)果Tab.4 Experiment results of minimum sampling variance

從表1可以看出，當(dāng)決策變量的維數(shù)從40增加到60時(shí)，誤差值快速的減小，計(jì)算時(shí)間緩慢增加. 當(dāng)決策變量的維數(shù)從60增加到80時(shí)，誤差值緩慢減小，計(jì)算時(shí)間快速增加. 因此，決策變量維數(shù)的最佳值是60.

從表2可以看出，當(dāng)種群規(guī)模從20增加到30時(shí)，誤差值快速減小，計(jì)算時(shí)間緩慢增加. 當(dāng)種群規(guī)模從30增加到40時(shí)，誤差值緩慢減小，計(jì)算時(shí)間快速增加. 因此，種群規(guī)模的最佳值是30.

從表3可以看出，當(dāng)最大采樣方差的取值是15時(shí)，誤差值最小. 因此，最大采樣方差的最佳值是15. 從表4可以看出，當(dāng)最小采樣方差的取值是4時(shí)，誤差值最小. 因此，最小采樣方差的取值是4.

由此可見，決策變量維數(shù)的最佳值是60，種群規(guī)模的最佳值是30，最大采樣方差的最佳值是15，最小采樣方差的最佳值是4.

采用對(duì)比方法計(jì)算同樣的手部區(qū)域圖像時(shí)，NSGA-Ⅱ中的交叉概率和分布指數(shù)分別是0.9和2，變異概率和分布指數(shù)分別是0.1和2.在MOCell中，保存的最優(yōu)個(gè)體數(shù)量是50，選擇的最優(yōu)個(gè)體數(shù)量是10. 兩種對(duì)比方法的進(jìn)化代數(shù)和種群規(guī)模與所提方法一致. 對(duì)于所提方法與兩種對(duì)比方法，其所有手部圖像的平均誤差值如表5所示. 其中，所提方法的上述4個(gè)主要參數(shù)均取最佳值.

表5是依次采用所提算法、NSGA-Ⅱ、MOCell，計(jì)算同樣的手部區(qū)域圖像得到的大量指尖位置誤差值的平均值. 從表5可以看出，所提算法的平均誤差值與NSGA-Ⅱ、MOCell的平均誤差值相比較最小. 因此，所提方法優(yōu)于兩種對(duì)比方法.

表5 不同求解方法的實(shí)驗(yàn)結(jié)果Tab.5 Experiment results of different solution methods

從表1和2可以看出，當(dāng)所提算法的4個(gè)主要參數(shù)均取最佳值時(shí)，平均計(jì)算時(shí)間是4.36 s. 這主要是由多目標(biāo)進(jìn)化算法普遍具有的計(jì)算復(fù)雜度決定的. 對(duì)于靜止指尖的識(shí)別系統(tǒng)，比如用指尖點(diǎn)擊特定的位置，這一計(jì)算時(shí)間是可以接受的. 但是，對(duì)于運(yùn)動(dòng)指尖的識(shí)別系統(tǒng)，比如用指尖移動(dòng)鼠標(biāo)，這一計(jì)算時(shí)間是無(wú)法接受的. 因此，需要對(duì)所提算法及其主要參數(shù)進(jìn)行深入研究，進(jìn)而減少計(jì)算時(shí)間.

4 結(jié)論

指尖區(qū)域的像素點(diǎn)分布在指尖中心的附近，是指尖像素點(diǎn)的分布規(guī)律. 對(duì)于選擇指尖像素點(diǎn)的優(yōu)化模型，采用符合上述分布規(guī)律的求解方法，能夠得到比較準(zhǔn)確的結(jié)果. 筆者提出決策變量的維數(shù)、種群規(guī)模、最大采樣方差、最小采樣方差是這一分布估計(jì)算法的主要參數(shù). 當(dāng)這些主要參數(shù)均取最佳值時(shí)，所提的求解方法能夠快速得到準(zhǔn)確的指尖位置，并且優(yōu)于已有方法. 實(shí)驗(yàn)結(jié)果證明了上述理論分析的結(jié)果.