基于修正共軛梯度算法的設(shè)計(jì)類App 圖像識(shí)別算法的研究

張 婷

（福建工程學(xué)院 應(yīng)用技術(shù)學(xué)院，福建 福州 350001）

伴隨移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，智能手機(jī)App、PC 端網(wǎng)站和平板電腦已成為用戶使用數(shù)字媒體的重要信息載體?！兑苿?dòng)用戶需求與行為調(diào)研報(bào)告》顯示，超過90%的移動(dòng)用戶幾乎每天都會(huì)使用移動(dòng)社交App，且人均每天在移動(dòng)媒體上所花費(fèi)的時(shí)間為1.5 h，70% 以上的用戶會(huì)在空閑時(shí)間使用移動(dòng)端App 應(yīng)用［1-4］。設(shè)計(jì)類App（例如堆糖、站酷等）主要以圖像搜索為主，因此研究移動(dòng)端設(shè)計(jì)類App中圖像識(shí)別的相關(guān)算法是非常有必要的。

本文先將設(shè)計(jì)類App 中常見的圖像特征歸納為顏色、紋理、形狀和空間關(guān)系等4 類，并構(gòu)造了4個(gè)特征矩陣及以這4 個(gè)矩陣為系數(shù)矩陣的一類線性矩陣方程［5］。將App 中的圖像近似搜索匹配問題轉(zhuǎn)化為求解這類線性矩陣方程是本文研究圖像識(shí)別算法的關(guān)鍵，如何求解該類矩陣方程是本文研究的重點(diǎn)。修正共軛梯度算法是求解矩陣方程的有效算法［6-7］，本文在此算法的基礎(chǔ)上建立求解這類多變量矩陣方程的迭代算法，當(dāng)方程有解時(shí)，根據(jù)該算法可以求得此類方程的解，則在已知圖庫中可以找到匹配的圖像；當(dāng)方程無解時(shí)，可以求該方程的最小二乘解，則能在已知圖庫中找到最相似的圖像。該算法的建立，能更好地解決設(shè)計(jì)類App中圖像識(shí)別近似匹配的問題。

1 矩陣方程的系數(shù)矩陣建立

在設(shè)計(jì)類App圖像識(shí)別的過程中，圖像信息的獲取主要是通過用戶在手機(jī)前端所選擇的某一感興趣的區(qū)域圖像進(jìn)行近似匹配。首先需要將圖像信息抽象化，根據(jù)圖像的顏色特征、紋理特征、形狀特征和空間關(guān)系特征，分別構(gòu)造圖像的顏色特征矩陣、紋理特征矩陣、形狀特征矩陣和空間關(guān)系特征矩陣，并分別記為A、B、C、D，獲取到的目標(biāo)區(qū)域圖像矩陣記為E。其中，A、B、C、D、E均為n階方陣。

1.1 顏色矩陣構(gòu)造

顏色矩是一種簡單有效的顏色特征表示方法，有一階矩（均值，mean）、二階矩（方差，variance）和三階矩（斜度，skewness）等。由于顏色信息主要分布于低階矩中，所以用一階矩、二階矩和三階矩足以表達(dá)圖像的顏色分布。顏色矩已被證明可有效地表示圖像中的顏色分布，該方法的優(yōu)點(diǎn)在于不需要顏色空間量化，特征向量維數(shù)低，但通過實(shí)驗(yàn)發(fā)現(xiàn)該方法的檢索效率比較低，因而在實(shí)際應(yīng)用中往往用來過濾圖像以縮小檢索范圍。3個(gè)顏色矩的數(shù)學(xué)定義如下：

式中，pi,j表示彩色圖像第j個(gè)像素的第i個(gè)顏色分量；N表示圖像中的像素個(gè)數(shù)。

由圖像的3 個(gè)分量Y、U、V圖像的前三階顏色矩組成一個(gè)多維直方圖向量，即圖像的顏色特征表示為

則顏色特征矩陣為

1.2 紋理矩陣構(gòu)造

紋理是一種圖像普遍存在的視覺現(xiàn)象，常見的紋理主要分為自然紋理、人工紋理和混合紋理等3類。描述紋理的參量有粗糙性、方向性、周期性、紋理強(qiáng)度和密度等，紋理描述是跟尺度相關(guān)的，紋理特征可以通過色調(diào)和結(jié)構(gòu)來描述。本文采用灰度共生矩陣來構(gòu)造紋理矩陣B。

定義1：從灰度為i的像素點(diǎn)出發(fā)，到該像素點(diǎn)的距離為(dx,dy)的另一個(gè)像素點(diǎn)的灰度為j的概率，記為P(i,j)。

數(shù)學(xué)表達(dá)式為

式中，d是用像素?cái)?shù)量表示的相對(duì)距離；θ指像素點(diǎn)j與像素點(diǎn)i的相對(duì)位置方向；#表示集合；(x,y)為圖像中的像素坐標(biāo)。在構(gòu)造紋理矩陣中用反差、能量、熵、相關(guān)性等特征量來表示紋理特征矩陣的元素。

其中，反差、能量、熵、相關(guān)性的定義分別如下：

由反差、能量、熵、相關(guān)性等4 個(gè)特征量構(gòu)造的共生矩陣B為

1.3 形狀矩陣

本文所采用的是形狀不變矩法，利用目標(biāo)圖像所占區(qū)域的矩作為形狀描述參數(shù)。將目標(biāo)圖像離散為M×N數(shù)字圖像f(x,y)，其中心矩定義為

利用2 階和3 階中心矩可以導(dǎo)出n個(gè)具有平移和縮放的不變性的特征集合，將其構(gòu)造為一個(gè)矩陣C。將目標(biāo)圖像依次縮小為80%、60%、50%、30%等，目標(biāo)圖像的左右上下平移操作分別用向量ci表示，得到如下的向量ci和矩陣C。

1.4 空間關(guān)系矩陣

圖像對(duì)象空間關(guān)系描述在圖像識(shí)別近似匹配的研究中是一個(gè)重要的因素。所謂空間關(guān)系是指圖像中分割出來的多個(gè)目標(biāo)之間的相互的空間位置或相對(duì)方向關(guān)系，這些關(guān)系也可分為連接和鄰接關(guān)系，交疊和重疊關(guān)系以及包含和包容關(guān)系等。對(duì)于給定圖像，首先通過圖像分割算法得到n個(gè)對(duì)象oi(i=1,2,…,n)，計(jì)算其重心ci(i=1,2,…,n)作為對(duì)象的代表點(diǎn)，計(jì)算n個(gè)重心兩兩之間的距離dij=d(ci,cj)，組成距離矩陣D。將圖像中的第一個(gè)對(duì)象o1與其余包含o1的oi(i=1,2,…,n)的重心距離作為矩陣的第一列，依次類推，可得

2 生成的方程

圖像識(shí)別問題就是根據(jù)所選的區(qū)域圖像，將其二值化為矩陣后，在App圖庫中找到與已知圖像匹配的圖像或最接近的圖像與已知圖像匹配。歸結(jié)到數(shù)學(xué)問題中，即為矩陣方程求解問題。根據(jù)圖像的顏色特征矩陣、紋理特征矩陣、形狀特征矩陣和空間關(guān)系特征矩陣，構(gòu)造一個(gè)含有4 個(gè)未知變量矩陣的線性矩陣方程，如式（13）。基于修正共軛梯度算法原理，建立求解這類方程的算法。

其 中，A、B、C、D、F∈Rn×n，用Rm×n表 示m×n實(shí)矩陣集合；定義同階實(shí)矩陣A與B的內(nèi)積為(A,B)=tr(ATB)，由此導(dǎo)出矩陣的Frobenius 范數(shù)

3 方程的求解

本文主要討論方程式（13）的兩個(gè)問題：

問題Ⅰ：若線性矩陣方程式（13）有解，求(X1,X2,X3,X4)∈Rn×n，使其滿足方程式（13）。

問題Ⅱ：若線性矩陣方程式（13）無解，求(X1,X2,X3,X4)∈Rn×n，使‖AX1+BX2+CX3+DX4-F‖=min。

3.1 求解問題Ⅰ的修正共軛梯度算法

借鑒共軛梯度算法原理，建立求解問題Ⅰ的修正共軛梯度算法，引入記號(hào)：

算法1（問題Ⅰ的修正共軛梯度算法）：

Step1：給定初始矩陣X(1)1、X(1)2、X(1)3、X(1)4∈Rn×n，置k：=1，計(jì)算

Step2：如果Rk=O，或者Rk≠O而Qk=O，停止計(jì)算；否則，計(jì)算

Step4：置k：=k+1，轉(zhuǎn)step2。

下面直接給出算法1 的性質(zhì)和定理，可以證明算法1在有限步計(jì)算之后停止。

當(dāng)res.data.resultCode返回的為-9999的時(shí)候，代表請(qǐng)求資源失敗，res.data.object.resultCode返回的為-9999的時(shí)候，代表業(yè)務(wù)處理失敗，即‘用戶名或密碼錯(cuò)誤’，否則代表業(yè)務(wù)處理成功。

性質(zhì)1對(duì)于算法1中的矩陣Ri、Q i和，有

性質(zhì)2設(shè)k≥2，對(duì)算法1中的矩陣Ri和Q j，有

性質(zhì)3設(shè)是問題Ⅰ的任意一組解，那么對(duì)任意初始矩陣由算法1得到的矩陣和Qk滿足

定理1設(shè)問題Ⅰ有解，則對(duì)任意的初始矩陣算法1可在有限步計(jì)算后求得問題Ⅰ的一組解。問題Ⅰ無解的充要條件是存在正整數(shù)k，使得由算法1得到的Rk≠O而Qk=O。

3.2 求解問題Ⅱ的MCG算法

在算法1中，當(dāng)Rk≠O而Qk=O時(shí)算法1中斷，表明方程式（13）無解。因此，求解問題Ⅱ，即求方程式（13）的最小二乘解。通過構(gòu)造等價(jià)線性矩陣方程，將求矩陣方程式（13）最小二乘解問題轉(zhuǎn)化為求等價(jià)正規(guī)方程的解問題，建立求矩陣方程式（13）的最小二乘解的迭代算法。

引入記號(hào)：

求解方程式（13）的最小二乘解等價(jià)于求矩陣方程式（13）的正規(guī)方程組的解，將方程式（13）按行拉直，則得到方程組Mx=v，其正規(guī)方程組為MTMx=MTv，因?yàn)檎?guī)方程組一定有解，所以方程式（13）的最小二乘解一定存在，即問題Ⅱ的解存在。

參照算法1 以及共軛梯度算法原理，建立求矩陣方程u(X)=G的解的算法，即求解問題Ⅱ的MCG算法如下。

算法2（問題Ⅱ的修正共軛梯度算法）：

Step1：給定初始矩陣置k：=1，計(jì)算

Step2：如果Rk=O，停止計(jì)算；否則，計(jì)算

Step3：計(jì)算

Step4：置k：=k+1，轉(zhuǎn)step2。

對(duì)于算法2有類似于算法1的收斂定理。

定理3對(duì)任意的初始矩陣，忽略舍入誤差，則算法2 可在有限步計(jì)算后求得問題Ⅱ的一組解，即矩陣方程式（13）的最小二乘解。

4 數(shù)值算例

用文中建立的算法1 求解矩陣方程式（13）的一組解，其中系數(shù)矩陣A、B、C、D、E均為元素為1的4n階方陣，終止準(zhǔn)則為ε=10-12。

選取初始矩陣X1=X2=X3=X4=O4n×4n，按照算法1 可求得矩陣方程式（13）的一組解，計(jì)算時(shí)間（s）、迭代次數(shù)、實(shí)際誤差及解矩陣的范數(shù)如表1（Matlab軟件2014版）所示。

表1 計(jì)算結(jié)果

當(dāng)n=1 時(shí)，計(jì)算得

從表1 可以看出，該算法具有較高的計(jì)算效率，當(dāng)方程有解時(shí)，可以得到方程式（13）的一組解，即能在已有的圖庫中找到匹配圖像；當(dāng)n=1 時(shí)，給定一個(gè)已知圖像信息矩陣，可以找到顏色特征矩陣、紋理特征矩陣、形狀特征矩陣和空間關(guān)系特征矩陣的組合系數(shù)解X1、X2、X3、X4。

5 結(jié)論

本文建立的MCG 算法具有較高的精準(zhǔn)度和較快的識(shí)別速度，當(dāng)方程有解時(shí)，則該App 算法可在圖庫中找到精準(zhǔn)匹配圖像；當(dāng)方程無解時(shí)，可以找到最小二乘解，即算法可找到最接近匹配圖像。該算法在計(jì)算機(jī)仿真中還需驗(yàn)證其有效性，在實(shí)際應(yīng)用中，若圖庫中有大量的設(shè)計(jì)類相似圖像時(shí)，如何能更精準(zhǔn)找到目標(biāo)圖像，還需要進(jìn)一步研究。