塔式GPCA張量線性子空間圖像模式低秩識別

申希兵，韋 容，楊 毅

(1.欽州學院 資源與環(huán)境學院，廣西 欽州 535000；2.欽州學院 人文學院，廣西 欽州 535000；3.廣西科技大學 軟件學院，廣西 柳州 545006)

0 引 言

在圖像模式識別[1,2]中，維度降低可實現(xiàn)無損前提下的數(shù)據(jù)處理量的降低，但是降維存在的最大問題是，會導致圖像模式的拓撲和幾何特征信息丟失[3]。

很多研究人員都致力于數(shù)據(jù)降維算法的研究，文獻[4]提出多值屬性的圖像金字塔降維技術(shù)，采用多值來構(gòu)造多分辨率金字塔骨架；文獻[5]提出基于圖論的3個金字塔方法，可保留圖像的幾何性質(zhì)；文獻[6]開發(fā)了邊緣特征向量方法；文獻[7]開發(fā)了奇異值分解(SVD)圖像編碼系統(tǒng)；文獻[8]提出廣義主成分分析(GPCA)的圖像壓縮方法；文獻[9]研究顯示從高維歐氏空間到低維歐氏空間的嵌入點存在低失真可能性；文獻[10]實驗結(jié)果表明，隨機映射可保持低維子空間中的原始數(shù)據(jù)與高維數(shù)據(jù)之間的距離；文獻[11]指出構(gòu)建隨機矩陣的條目必須至少4組，且相互獨立；文獻[12]建立了對稱正定矩陣的幾何感知降維方法，其學習方法不依賴于流形的切空間近似。此類文獻較多，不再贅述。

上述圖像模式識別文獻存在的問題有：①理論分析不夠深入，缺乏理論佐證；②降維過程存在的圖像模式的拓撲和幾何特征信息丟失問題未得到有效解決。對此，為解決上述問題，本文提出一種基于塔式隨機映射廣義主成分分析(GPCA)的張量線性子空間圖像模式低秩識別方法，從理論分析和拓撲、幾何特征信息保持角度進行算法設計，并進行了有效性驗證。

1 塔式變換與隨機映射

1.1 塔式變換

利用因子σ定義下采樣操作Dσ

g(x,y)=Dσf(x,y)=f(σx,σy)

(1)

利用因子σ定義上采樣操作Uσ

(2)

上述下采樣和上采樣操作存在以下特性：

特性1 部分等距特性：這些操作滿足關(guān)系

(3)

(4)

降維算子R的對偶算子E可定義為

(5)

根據(jù)式(1)可知，降維是通過卷積核ωσ的平滑函數(shù)實現(xiàn)，在實際應用時選取σ=2。

對于一個非擴張映射φ，其滿足

(6)

式中：φ(f)≠λf，則可得定理1，具體如圖1所示。

圖1 函數(shù)及其非擴張映射夾角

定理1 設定∠f,g為f和g在Hilbert空間上的夾角，其滿足

∠(φ(f),φ(g))≤∠(f,g)

(7)

(8)

(9)

對于f(x,y)和g(x,y)之間的卷積h(x,y)=g(x,y)*f(x,y)，可得如下推論：

推論1 對于卷積能量，可得如下特性

(10)

對于線性算子R，如果Rf≠0，則當f∈L2,g∈L2時，存在關(guān)系

(11)

定理2 塔式變換是線性擴張和降維映射。

證明：根據(jù)定義可知，對于兩個二維圖像，通過塔式變換線性操作可將原始尺寸的圖像降低到1/4。因此，這個操作線性降維映射。同時根據(jù)式(11)，塔式變換是非擴張映射。

根據(jù)上述特性，可得到以下特性：

特性2 假陽性識別：對于本來很大的模式相似性，定理2通過塔式變換可提供比原來的模式更大的相似性。然而，對于原來很小的模式相似性，塔式變換可提供更大的相似性，此特性可有效對假陽性進行識別。

對于采樣函數(shù)fij=f(i,j)，下采樣Dσ和對偶操作Uσ可擴展為

(12)

此外，塔式變換線性降維算子R和其對偶算子E可擴展為

(13)

其中，ω±1=1/4和ω0=1/2。此外，對整數(shù)m-i和n-j進行求和操作。這兩個操作涉及的圖像大小降維和擴展。作為非擴張映射，塔式變換可對O1/2n的n階張量進行壓縮，并可保持張量數(shù)據(jù)的微分幾何結(jié)構(gòu)。

1.2 隨機映射

塔式變換是一種度量嵌入方法，可近似保留原空間中的點與點之間的距離。此外，對于任意一個點集，塔式變換可保留點角集、卷積單形和光滑曲線及流形的長度。圖2(a)～圖2(c)，顯示了存儲的距離，角度和體積，以及塔式變換流形。

圖2 圖像模式識別映射情形

(14)

式中：i,j=1,2,…,N。從模式識別的角度來看，特性3表明該映射近似保留模式的相似性，而不受類型的模式或其分布的影響，雖然映射不能保存圖像的幾何形狀。

對于d維歐式空間的N個點集，k≤d，令R為k×d正交矩陣，形式為

(15)

(16)

(17)

對于上述隨機映射，可得如下定理：

定理3 隨機映射是線性和拓撲保持降維映射。

(18)

該下界表明，維度K的低維空間與D維原始空間是獨立的。下界k0來自馬爾可夫不等式，在大多數(shù)情況下，比實際誤差ε要小得多。對于標準的隨機線性映射，可得如下定理：

(19)

隨機矩陣R定義一個獨立的數(shù)據(jù)集X的k維隨機子空間。隨機線性映射降維并未考慮數(shù)據(jù)分布。密集的隨機矩陣生成需要的計算和存儲成本為Okd。此外，N個點映射需要計算和存儲成本為OkdN。實際計算中，所使用隨機線性映射的計算和存儲成本為Odlogd。

2 模式張量的線性降維

2.1 拓撲和幾何表示

圖2中給出圖像模式識別中的3種映射情形，盡管構(gòu)造順序結(jié)構(gòu)，但會在度量空間中嵌入數(shù)據(jù)。因此，可利用弱和強條件對階條件要求進行替換。一般情況下，在線性降維操作中，強的和偏向性的條件不成立。線性降維方法中，隨機映射滿足圖像模式識別所需的弱條件，而其它方法不滿足。

作為非線性降維方法，內(nèi)核方法通過映射函數(shù)Φ將數(shù)據(jù)映射到高維空間。內(nèi)核方法滿足條件

(20)

其為非線性映射，對于TsTl，則有dΦ(Φ(f),Φ(g))?d(f,g)以及dΦ(Φ(f),Φ(g))?d(f,g)成立。由于這種映射Φ增加兩類數(shù)據(jù)分布之間的分離比，可在高維空間中建立了一個線性分類。

內(nèi)核方法實際計算，給出兩個數(shù)據(jù)在高維空間投影的內(nèi)模，而不是在高維空間中的范數(shù)或距離。例如多項式函數(shù)

k(f,g)=(Φ(f),Φ(g))=((f,g)+1)p

(21)

高斯徑向基函數(shù)為

(22)

在高維空間中給出f和g的內(nèi)模。該函數(shù)給出對應距離比閾值T更大的內(nèi)模?；趦?nèi)核，在高維空間中執(zhí)行線性降維，并獲得在原來空間中的非線性映射。

2.2 二維隨機映射

(23)

(24)

(25)

(26)

通過矩陣Xi的Frobenius范數(shù)，替換vecXi的歐式范數(shù)，可得上述定理成立。

通過將二維數(shù)組擴展為二階張量，可減少任意維數(shù)據(jù)張量的維數(shù)。通過二維隨機映射在函數(shù)空間保存張量的拓撲結(jié)構(gòu)。

2.3 廣義主成分分析

(27)

其中，U=[u1,…,um],V=[vl,…,vn]通過最小化的標準

(28)

和最大化準則獲得

(29)

其限制條件為

UTU=Im,VTV=In

(30)

式中：Im和In為單位矩陣，通過計算特征值分解問題的極值可導出

(31)

MV=V,NU=U∑

(32)

式中：∑∈Rm×m,Λ∈Rn×n是滿足關(guān)系λi=σi的對角矩陣

(33)

Yi=(UP1)TXi(VP2)=LTXiR

(34)

其中，P1和P2為映射矩陣U和V的基向量，則式(34)所示矩陣為圖像壓縮的二維隨機映射方法，該方法采用二維PCA變換形式為

Yi=XiR

(35)

為實現(xiàn)上述奇異值分解的指標優(yōu)化，所提算法見偽代碼1。

偽代碼1:廣義主成分分析的迭代最小二乘算法(1)輸入:一組張量Xi∈m×n{}Ni=1。模式1和2的維度降低數(shù)k1和k2,最大迭代數(shù)K;(2)輸出:一組投影矩陣PL,PR{};如果k1=m、k2=n,則PL,PR{}給出全投影,否則,它給出了全投影截斷。(3)通過M(0)r=1N∑Ni=1XiXTi和M(0)c=1N∑Ni=1XTiXi的特征分解,計算初始投影矩陣P(0)L和P(0)R。(4)通過選擇M(0)r和M(0)c的k1和k2個特征向量,構(gòu)建投影矩陣;(5)計算ψ0=∑Ni=1P(0)TLXiP(0)R2F;(6)begin loop(7) for k=1,2,…,K(8) 選擇M(k)r=1N∑Ni=1XiP(k-1)RP(k-1)TRXTi的k1個特征向量,計算P(k)L;(9) 選擇M(k)c=1N∑Ni=1XTip(k-1)TLP(k-1)LXi的k2個特征向量,計算P(k)R;(10) if ψk-ψk-1<η,ψk=∑Mj=1P(k)TLXiP(k)R2Fbreak;end(11)return PL=P(k)L、PR=P(k)R;

2.4 張量的子空間低秩逼近分類

對于矩陣X，設定PL和PR為正交投影，則X到Y(jié)的正交投影為

(36)

(37)

(38)

則可得G∈Ck(δ)。

設定Rd為d維歐氏空間，定義內(nèi)積f,g，令f∈Rd,Pk分別為第i類模式和操作算子，其中第i類模式可定義為

(39)

由于模式擾動，可定義類別i形式為

(40)

其中，δ表示小擾動模式。對于輸入g∈Rd和類別Ci，分別定義相似性和分類標準

θi=∠(Ci(δ),g),0<θi

(41)

定義輸入模式g和模式空間的角度為

(42)

輸入模式和模式空間之間的角度表示兩者之間相似性。對于輸入g∈Rd構(gòu)建

(43)

由此可得

θi=∠(Ci(δ),Cg(δ)),θ<θi

(44)

其中，CgCk(δ)∩Cg(δ)?δ。為fi∈Ci構(gòu)建操作算子Pi

(45)

(46)

圖3顯示了基于塔式變換降維，主成分分析和二維張量主成分分析子空間低秩逼近分類過程。塔式變換和PCA變換都是酉變換。

圖3 子空間低秩逼近

3 實驗分析

為評價所提圖像模式識別的維數(shù)約簡方法性能，實驗對象選取CALTECH101目標檢測數(shù)據(jù)集、YaleB人臉數(shù)據(jù)庫、ORL人臉數(shù)據(jù)集和ETL9G中文字符集，具體如圖4所示。

圖4 測試數(shù)據(jù)集

(47)

(48)

圖5 能量消耗對比

圖6 圖像間距相對誤差均值

由圖5能量消耗對比曲線可知，塔式變換所需要的消耗指標最大，其次為二維離散余弦變換，第三是隨機映射，而本文算法所需要的能耗指標最低，這表明所提算法在計算資源消耗上要少于選取的3種對比算法。由圖6圖像間距相對誤差均值對比曲線可知，在CALTECH101目標檢測數(shù)據(jù)集和ETL9G中文字符集中，塔式變換相對誤差均值最大，其次為二維離散余弦變換，第三是隨機映射，而本文算法圖像間距相對誤差均值指標最低，在YaleB人臉數(shù)據(jù)庫和ORL人臉數(shù)據(jù)集上，算法間相對誤差均值指標在壓縮比取值較小時，存在交叉現(xiàn)象，但是整體上本文所提算法的相對誤差均值指標更低，這表明所提算法在原數(shù)據(jù)拓撲和幾何特征保持能力上要優(yōu)于選取的3種對比算法。

為更加直觀的驗證所提算法在圖像模式識別中的性能，選取識別率和計算時間作為對比指標，對比算法選取文獻[13,14]算法，這兩種算法均為隨機映射算法的改進版本。實驗硬件參數(shù)：CPU i5-6200U，內(nèi)存6G ddr3-1600，系統(tǒng)win7旗艦版，硬盤為浦科特M6S+ 128G固態(tài)硬盤，實驗對象選取上述YaleB人臉數(shù)據(jù)庫和ETL9G中文字符集，實驗對比數(shù)據(jù)見表1。

表1 識別率和計算效率對比

根據(jù)表1數(shù)據(jù)可知，在識別率指標中，本文算法在YaleB人臉數(shù)據(jù)庫和ETL9G中文字符集上的識別率分別為91.5%和94.1%，要稍高于文獻[13,14]兩種對比算法，在計算時間指標中，本文算法在YaleB人臉數(shù)據(jù)庫和ETL9G中文字符集上的計算時間分別為7.6 s和6.5 s，要優(yōu)于文獻[14]算法，同時與文獻[13]算法相差不大。上述實驗結(jié)果驗證了所提算法在識別率和計算時間指標上的性能優(yōu)勢。

4 結(jié)束語

本文提出一種基于塔式隨機映射廣義主成分分析(GPCA)的張量線性子空間圖像模式低秩識別方法，推導出隨機映射所具有的線性和拓撲保持的降維映射特性，并基于塔式變換降維，隨機映射和GPCA構(gòu)建張量子空間低秩逼近分類過程，實驗結(jié)果表明，所提算法在能量消耗等指標上要優(yōu)于選取的對比算法。

同時應該看到，在計算識別率指標上，所提算法還有進一步提升的空間，其在在YaleB人臉數(shù)據(jù)庫和ETL9G中文字符集上識別率與文獻[15]所提算法識別率相比，并無絕對優(yōu)勢。