許德剛 ，廉飛宇 *

（河南工業(yè)大學(xué) 1.糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室；2.糧食光電探測(cè)與控制河南省重點(diǎn)實(shí)驗(yàn)室；3.信息科學(xué)與工程學(xué)院，河南 鄭州 450001）

一種糧粒圖像快速重構(gòu)方法

許德剛1，2，3，廉飛宇1，2，3*

（河南工業(yè)大學(xué) 1.糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室；2.糧食光電探測(cè)與控制河南省重點(diǎn)實(shí)驗(yàn)室；3.信息科學(xué)與工程學(xué)院，河南 鄭州 450001）

針對(duì)糧情實(shí)時(shí)檢測(cè)過(guò)程中圖像清晰度下降，給后續(xù)分析造成困難的問(wèn)題，提出一種新的圖像重建記憶梯度追蹤（MGP）算法，用于減少壓縮感知方向追蹤算法的重構(gòu)時(shí)間并提高重構(gòu)精度。該算法結(jié)合正則化正交匹配追蹤（ROMP）的元胞生成方法，利用非單調(diào)非精確阿米霍線搜索方法確定迭代步長(zhǎng)，利用MGP算法鎖定搜索方向，可以在保證圖像重構(gòu)精度的同時(shí)，縮短重構(gòu)時(shí)間。對(duì)原有MGP算法的方向參數(shù)公式進(jìn)行了推導(dǎo)和改進(jìn)，得到了效率更高的計(jì)算公式，使得算法的運(yùn)行時(shí)間較共軛梯度追蹤算法節(jié)省30%，并可精確重構(gòu)二維糧粒圖像信號(hào)。本算法的運(yùn)行結(jié)果表明，在相同硬件平臺(tái)下，其二維糧粒圖像信號(hào)的重構(gòu)性能優(yōu)于其他的同類重構(gòu)算法。

糧粒檢測(cè)；壓縮感知；方向追蹤；記憶梯度；圖像重構(gòu)

0 引言

我國(guó)是糧食生產(chǎn)、流通、消費(fèi)大國(guó)，隨著人們生活水平的提高，糧食供求的主要矛盾已從數(shù)量上的欠缺轉(zhuǎn)為質(zhì)量上的擔(dān)憂。當(dāng)前，糧食品質(zhì)檢測(cè)還停留在利用傳統(tǒng)手段人工觀測(cè)的水平，有關(guān)品質(zhì)指標(biāo)的確定缺乏客觀性和科學(xué)性，而且無(wú)法滿足快速檢測(cè)的要求，給糧食的分級(jí)利用造成了困難。

目前，將圖像處理技術(shù)引入糧食顆粒外觀品質(zhì)檢測(cè)，成為了國(guó)內(nèi)外的研究熱點(diǎn)[1]。在實(shí)際應(yīng)用中，糧食收儲(chǔ)環(huán)境復(fù)雜，外部噪聲和干擾很強(qiáng)，對(duì)糧粒成像質(zhì)量造成影響，為圖像的后續(xù)分析帶來(lái)困難，因此糧粒圖像的快速恢復(fù)重建十分重要。近年來(lái)，壓縮感知（CS）理論受到廣泛關(guān)注，它突破了傳統(tǒng)的Naquist定理的限制，帶來(lái)了信號(hào)獲取方式的變革。在CS中，信號(hào)的恢復(fù)重建是一個(gè)基本的關(guān)鍵問(wèn)題，其算法應(yīng)當(dāng)能夠?qū)π盘?hào)進(jìn)行精確重構(gòu)，這實(shí)質(zhì)上可歸結(jié)為一個(gè)優(yōu)化問(wèn)題的求解過(guò)程[2-3]。因此，將壓縮感知（CS）理論方法應(yīng)用于糧粒圖像重構(gòu)，提升成像質(zhì)量，對(duì)于促進(jìn)糧食顆粒品質(zhì)檢測(cè)技術(shù)發(fā)展以及應(yīng)用領(lǐng)域拓展有重要的實(shí)際意義。

在目前的壓縮感知重建算法中，貪婪算法是應(yīng)用最為廣泛的一類，其要點(diǎn)有兩個(gè)：匹配追蹤和方向追蹤。在匹配追蹤中，通常采用正交匹配追蹤（orthogonal matching pursuit，MP）算法。該算法繼承了匹配追蹤（matching pursuit，MP）算法的元胞生成方法，并在選中元胞后進(jìn)行正交化。但該算法對(duì)于高維觀測(cè)矩陣需要大量投影計(jì)算，時(shí)間復(fù)雜度較高，因而一系列改進(jìn)算法又被提了出來(lái)，如正則化正交匹配追蹤（regularized OMP）[4]、分段正交匹配追蹤（blockOMP）等。在方向追蹤中，常用的算法是基于貪婪算法的方向追蹤算法[5]，主要包括：梯度追蹤法（gradientpursuit,GP）、近似共軛梯度追蹤法（approximate conjugate gradient pursuit，ACGP）、 共軛梯度追蹤法（conjugate gradient pursuit， CGP）、譜投影梯度追蹤法（spectral projected gradient pursuit，SPGP）[6]和分段弱閾值共軛梯度追蹤法[7]等。

方向追蹤法和匹配追蹤法的元胞生成方式相同，不同之處在于：方向追蹤法采用的是共軛梯度、負(fù)梯度方向作為搜索方向進(jìn)行求解，而不是采用匹配追蹤法中較為耗時(shí)的最小二乘法進(jìn)行求解，但其缺陷是重建精度不夠高。作者針對(duì)這一問(wèn)題，在正則化正交匹配追蹤基礎(chǔ)上，采用非單調(diào)記憶梯度的方向更新機(jī)制，提出一種新的記憶梯度追蹤算法，該算法克服了共軛梯度追蹤法計(jì)算量大且收斂速度慢的問(wèn)題。

1 元胞生成方法

對(duì)于長(zhǎng)度為N的一維信號(hào)x?RN，若其不為零的元素個(gè)數(shù)為S且S＜N，則稱信號(hào)是稀疏的。由壓縮感知理論，對(duì)于隨機(jī)測(cè)量矩陣 A?RM×N,當(dāng) M＜N且滿足一定條件時(shí)，通過(guò)壓縮感知可得到長(zhǎng)度為M的一維觀測(cè)信號(hào)y，且有如下關(guān)系：

稱測(cè)量矩陣A的列向量Ai為元胞。根據(jù)文獻(xiàn)[8]，信號(hào)x通過(guò)M個(gè)在測(cè)量矩陣A上的非相干投影，即可實(shí)現(xiàn)重建。本文的元胞生成方法采用正則化正交匹配追蹤算法[4]。該方法首先進(jìn)行元胞的第一次篩選，方法是通過(guò)求矩陣A中各個(gè)元胞與余量r的內(nèi)積（Ai， ）

r的絕對(duì)值來(lái)求取相關(guān)系數(shù)u，即：

通過(guò)此方法篩選出S個(gè)元胞，并將其索引值存到侯選集J中。然后進(jìn)行第2次篩選，即對(duì)篩選出的元胞先進(jìn)行正則化，根據(jù)式（2）將第1次篩選出的元胞的系數(shù)進(jìn)行分組，生成系數(shù)值最大的一組元胞，并將其序號(hào)存入侯選集J0中，J0在文中又稱為初次侯選集。

選擇正則化正交匹配追蹤算法的目的在于避免采用最小二乘法進(jìn)行信號(hào)逼近帶來(lái)的算法復(fù)雜性問(wèn)題，其算法的簡(jiǎn)單流程為：

（1）初始化參數(shù)。初始余量r0=y，迭代次數(shù)n=1，估計(jì)信號(hào)稀疏度為S，索引值集合A=φ，J=φ；

（2）根據(jù)式（2）計(jì)算相關(guān)系數(shù)u；

（3）對(duì)u降序排列，取前S個(gè)最大值，更新 J中對(duì)應(yīng)的索引值；

（4） 正則化。篩選滿足|u（i）|≤2|u（j）|,i，j?J 的元胞，將其索引值存入集合J0中；

（5） 更新支撐集 AΛ，其中 Λ=Λ∪J0。

2 非單調(diào)記憶梯度算法

記憶梯度法不用矩陣的存儲(chǔ)和計(jì)算，是改進(jìn)的共軛梯度法，適用于無(wú)約束優(yōu)化問(wèn)題的求解[9]，算法簡(jiǎn)單，是常用的最優(yōu)化方法之一，常采用如下迭代式：

式中：xn為估計(jì)值；αn為搜索步長(zhǎng)；dn為更新方向。

CGP算法采用共軛梯度方向[5]確定更新方向，而在記憶梯度法中，則是由前一迭代點(diǎn)的搜索方向dn－1和當(dāng)前迭代點(diǎn)的反梯度方向-gn組合成搜索方向，這種組合不僅利用了當(dāng)前點(diǎn)的方向信息，也利用了前一迭代點(diǎn)的方向信息，提高了參數(shù)選擇靈活性，因而使收斂更為穩(wěn)定[9]。

下面利用梯度追蹤法求解式（1）：

式中：Λn為在n次迭代時(shí)，選取元胞下標(biāo)的集合，AΛn為Λn對(duì)應(yīng)的元胞組成的矩陣。

將式（4）代入式（6），

重建圖像時(shí)，GP算法有兩個(gè)問(wèn)題需要解決：一是如何確定循環(huán)步長(zhǎng)，二是如何確定前一迭代點(diǎn)負(fù)梯度的方向。設(shè)gn為梯度函數(shù)，則：

而更新方向的計(jì)算如下：

（1）當(dāng)｜｜gn｜｜＝0，停止迭代，否則繼續(xù)；

（2）確定搜索方向：

在CGP算法中，最優(yōu)步長(zhǎng)的求法依賴單調(diào)精確搜索算法[12]，如下式所示。

式中：琢可根據(jù)文獻(xiàn)[11]確定。

求解無(wú)約束優(yōu)化問(wèn)題時(shí)，單調(diào)精確算法的效率較低，甚至?xí)袖忼X現(xiàn)象[12]，采用非單調(diào)搜索算法[13]，解決了一些缺點(diǎn)，使算法的整體性能有了很大的改善。本文采用文獻(xiàn)[11]的方法，它是一種非單調(diào)改進(jìn)Armijo線搜索，具有運(yùn)算量少、速度快、易于實(shí)現(xiàn)的優(yōu)點(diǎn)。

3 記憶梯度追蹤算法的改進(jìn)

方向追蹤算法的元胞生成方法與MP算法是相同的，不同之處是它的余差更新方式是記憶梯度算法，而不是最小二乘算法，從而更容易得到全局最優(yōu)解。

在記憶梯度算法中，搜索方向中的參數(shù)βn，根據(jù)文獻(xiàn)[14]，由式（3）可得：

記憶梯度法的算法流程如圖1所示。算法首先進(jìn)行初始化：r0＝y(tǒng)，索引集 J=?，I0＝?，迭代變量 n＝1；然后重復(fù)以下步驟：

圖1 記憶梯度算法流程圖Fig.1 The flow diagram of the memory gradient algorithm

（1）利用ROMP算法得到投影系數(shù)值μ，進(jìn)行元胞選擇，得到候選元胞集，進(jìn)行正則化，得到最大能量子集，即

（2）采用非單調(diào)記憶梯度法求解 xn，dn，rn，步驟如下：①計(jì)算梯度；②計(jì)算方向，將本節(jié)推導(dǎo)的 βn帶入式（9）求得③計(jì)算步長(zhǎng)；④求的近似解；⑤觀測(cè)余量信號(hào)更新，即

重復(fù)步驟（1）和步驟（2）直到滿足迭代停止條件。最后輸出重構(gòu)信號(hào)的元胞支撐集

上述MPG算法的時(shí)間復(fù)雜度主要由兩個(gè)方面決定，一是元胞的選擇，需要計(jì)算ATr，其時(shí)間復(fù)雜度記為O（A），和正則化元胞的二次篩選，其時(shí)間復(fù)雜度為O（KMN），二是更新方向和步長(zhǎng)的計(jì)算，時(shí)間復(fù)雜度分別為 O（A）和O（M）。從總體上看，MGP算法的時(shí)間復(fù)雜度與CGP算法處于相同級(jí)別上。

通過(guò)上述流程，本文的記憶梯度算法與其他算法相比，其優(yōu)勢(shì)為：（1）元胞生成方法采用方向追蹤與正則化正交匹配追蹤選擇相結(jié)合，提高了每次迭代的速率；（2）采用非單調(diào)線搜索，減少了步長(zhǎng)計(jì)算的時(shí)間，提高了收斂效率，避免了鋸齒現(xiàn)象的發(fā)生。

4 測(cè)試結(jié)果和性能分析

首先通過(guò)重構(gòu)一個(gè)一維稀疏信號(hào)，比較本文算法與傳統(tǒng)的梯度追蹤算法、正交匹配算法在時(shí)間復(fù)雜性、相對(duì)誤差方面的性能；然后通過(guò)重構(gòu)一個(gè)二維糧粒圖像信號(hào)，比較本文算法與上述兩種算法在時(shí)間復(fù)雜性、相對(duì)誤差方面的性能。

對(duì)相對(duì)誤差的定義[15]：

式中：f＊為原始信號(hào)，f為重構(gòu)信號(hào)，e為相對(duì)誤差，e越小表明精度越高。

本文算法及其他算法的比較均在Windows 7系統(tǒng)下運(yùn)行，硬件配置為：CPU2GHz，內(nèi)存4GBDDR2，顯卡支持DirectX 9，硬盤(pán) 500 GB。仿真軟件使用的是MATLAB R2013a。仿真參數(shù)如表1所示。

表1 仿真參數(shù)Table 1 Simulation parameters

4.1 一維稀疏信號(hào)的重構(gòu)性能

對(duì)本文的改進(jìn)記憶梯度追蹤算法、傳統(tǒng)梯度追蹤算法、近似共軛梯度追蹤算法以及正則化正交匹配追蹤算法進(jìn)行了重構(gòu)誤差和運(yùn)算時(shí)間上的比較?？紤]到信號(hào)中通常含有高斯噪聲，在高斯噪聲方差為σ2時(shí)，各算法對(duì)一維稀疏信號(hào)的重構(gòu)精度和時(shí)間如表2所示。

由表2可知，4種算法的運(yùn)算時(shí)間在一個(gè)數(shù)量級(jí)上。當(dāng)σ2=1×10-3時(shí)，4種算法的相對(duì)誤差均較小，隨著σ2增大，正則化正交匹配追蹤和改進(jìn)型記憶梯度追蹤算法的時(shí)間逐漸延長(zhǎng)，當(dāng)σ2=5×10-3時(shí)，這兩種算法所需時(shí)間較短?？傮w上看，正則化正交匹配追蹤算法對(duì)高斯噪聲比較敏感，而改進(jìn)型記憶梯度追蹤算法則穩(wěn)定性較好，抗干擾性能優(yōu)于其他算法。由圖2可見(jiàn)，從重建效果上看，改進(jìn)型記憶梯度追蹤算法對(duì)一維稀疏信號(hào)的重構(gòu)質(zhì)量和運(yùn)算時(shí)間均優(yōu)于近似共軛梯度追蹤算法和正則化正交匹配追蹤算法。

表2 一維信號(hào)的重建時(shí)間和重建誤差Table 2 The reconstruction time and error of one-dimensional signal

圖2 一維稀疏信號(hào)的重構(gòu)性能（稀疏度，方差0.001）Fig.2 The reconstruction performance of one-dimensional sparse signal（sparsenes，variance:0.001）

4.2 二維糧粒圖像信號(hào)的重構(gòu)性能

改進(jìn)型記憶梯度追蹤算法是一種對(duì)稀疏信號(hào)進(jìn)行精確重構(gòu)的算法，在用于對(duì)糧粒圖像的重構(gòu)時(shí)，首先需要將糧粒圖像表示為稀疏信號(hào)。常用方法有小波變換法、快速傅里葉變換法等。本文采用小波變換法。重構(gòu)糧粒圖像信號(hào)的流程為：①將高斯隨機(jī)矩陣與小波基相乘，得到測(cè)量矩陣；②利用測(cè)量矩陣得到糧粒圖像信號(hào)的測(cè)量值；③利用改進(jìn)型記憶梯度追蹤算法，重構(gòu)出糧粒圖像的小波系數(shù)；④通過(guò)小波反變換重構(gòu)出原始糧粒圖像。

圖3為采用M/N=0.5的采樣率，4種算法的糧粒圖像重構(gòu)效果，相應(yīng)的峰值信噪比如表3所示。圖3中的糧粒圖像來(lái)源于河南工業(yè)大學(xué)糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室，像素尺寸均為512×512。

圖3 不同算法對(duì)糧粒圖像的重建效果Fig.3 The reconstruction effect of the grain images of four algorithms

表3 不同算法圖像重建峰值信噪比Table 3 The peak signal to noise ratio of four algorithms dB

由圖3可以看出，改進(jìn)型記憶梯度追蹤算法的峰值信噪比最大，且算法運(yùn)行時(shí)間比近似共軛梯度追蹤算法減少30%。當(dāng)M/N=0.5時(shí)，具有相對(duì)更高的重構(gòu)精度。

圖4表明了采樣率對(duì)糧粒圖像重構(gòu)的影響。由圖4可知，4種算法隨著測(cè)量次數(shù)的增加，糧粒圖像的重構(gòu)質(zhì)量均有所提高。當(dāng)采樣率小于0.2時(shí)，4種算法的重構(gòu)效果相差不大，但當(dāng)采樣率大于0.2時(shí)，改進(jìn)型記憶梯度追蹤算法的峰值信噪比高于其他算法，因而具有更好的特性。雖然正則化正交匹配追蹤具有與記憶梯度追蹤相同的元胞生成方法，但正則化正交匹配追蹤算法的圖像重構(gòu)質(zhì)量最差。這是因?yàn)楸疚母倪M(jìn)型記憶梯度追蹤算法采用的是不同方向的步長(zhǎng)更新機(jī)制，因而使其性能得到大幅度提高。

圖4 不同采樣率的糧粒圖像重建效果Fig.4 The reconstruction effect of the grain images of four sampling frequency

5 結(jié)論

針對(duì)糧情實(shí)時(shí)監(jiān)測(cè)過(guò)程中圖像清晰度不足造成識(shí)別困難的問(wèn)題，提出了一種新的圖像重構(gòu)算法——改進(jìn)型記憶梯度追蹤算法(MGP)，用于提高糧食品質(zhì)在線監(jiān)測(cè)中糧粒圖像的恢復(fù)效果。該算法吸收正則化正交匹配追蹤算法的元胞吸收方法，結(jié)合方向梯度算法，采用記憶梯度最終確定搜索方向，采用非單調(diào)非精確Armijo線搜索準(zhǔn)則確定補(bǔ)償，使得在提高信號(hào)重構(gòu)精確度的同時(shí)，縮短了重構(gòu)時(shí)間。仿真結(jié)果表明，本算法可顯著改善糧粒圖像和其他實(shí)時(shí)糧情監(jiān)測(cè)圖像的重構(gòu)質(zhì)量。算法存在的問(wèn)題是，在時(shí)間復(fù)雜度上還沒(méi)有顯著的優(yōu)化，另外，目前還沒(méi)有考慮彩色圖像的重構(gòu)，需要在今后的工作中做進(jìn)一步的研究。

［1］ 周志強(qiáng)，成軍虎，潘石.基于計(jì)算機(jī)視覺(jué)的稻米品質(zhì)評(píng)價(jià)研究進(jìn)展［J］.河南工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012， 33（6）:95-100.

［2］ 周燕，曾凡智.基于二維壓縮感知和分層特征的圖像檢索算法［J］.電子學(xué)報(bào)，2016，44（2）:453-460.

［3］ 劉芳，武嬌，楊淑媛，等.結(jié)構(gòu)化壓縮感知進(jìn)展［J］.自動(dòng)化學(xué)報(bào)，2013，39（12）:1980-1995.

［4］ 劉哲，張鶴妮，張永亮，等.基于弱選擇正則化正交匹配追蹤的圖像重構(gòu)算法［J］.光子學(xué)報(bào)，2012，41（10）:1217-1221.

［5］ 劉盼盼.壓縮感知中梯度追蹤算法的研究［D］.南京：南京郵電大學(xué)，2015.

［6］ 李志林，陳后金，姚暢，等.基于譜投影梯度追蹤的壓縮感知重建算法［J］.自動(dòng)化學(xué)報(bào)，2012，38（7）:1218-1223.

［7］ BLUMENSATH T，DAVIES M E.Gradient pursuits［J］.IEEE Transactions on Signal Processing， 2008， 56（6）:2370-2382.

［8］ 方紅，楊海蓉.貪婪算法與壓縮感知理論［J］.自動(dòng)化學(xué)報(bào)，2011，37（12）:1413-1421.

［9］ 時(shí)貞軍.無(wú)約束優(yōu)化的超記憶梯度算法［J］.工程數(shù)學(xué)學(xué)報(bào)，2000，17（2）:99-104.

［10］ JIAN B J，ZENG F Y，TANG C M.A generalized super-memory gradient projection method of strongly sub-feasible directions with strong convergence for nonlinear inequality constrained optimization［J］.Computers and Mathematics with Applications， 2007，54（4）:507-524.

［11］ 湯京永，董麗.一類新的記憶梯度法及其收斂性［J］.工程數(shù)學(xué)學(xué)報(bào)，2010，27（4）:637-642.

［12］ 湯京永，董麗.非單調(diào)線搜索下的記憶梯度法及其全局收斂性［J］.四川師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，33（1）:32-35.

［13］ 湯京永，賀國(guó)平，董麗.一類新的求解無(wú)約束優(yōu)化問(wèn)題的記憶梯度法［J］.數(shù)學(xué)雜志，2011，31（2）:362-368.

［14］ MALLAT S，陳剛，張亶，等.應(yīng)用數(shù)學(xué)和信號(hào)處理相遇［J］.高校應(yīng)用數(shù)學(xué)學(xué)報(bào)， 1999，14（3）:350-366.

［15］ 郭強(qiáng)，孫鵬，趙迎春，等.基于記憶梯度追蹤的高效稀疏跟蹤算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2016，28（4）:565-571.

A FAST METHOD FOR IMAGE RECONSTRUCTION OF GRAIN KERNELS

XU Degang1，2，3，LIAN Feiyu1，2，3
（Henan University of Technology，1.Key Laboratory of Ministry of Education for Grain Information Processing and Control；2.Key Laboratory of Henan Province for Grain Photodetection and Control；3.School of Information Science and Engineering，Zhengzhou 450001，China）

For the problem that charity of images decreasing in the real-time monitoring of grain kernels situation， which causing difficulties for the subsequent analysis， a new image reconstruction method based on memory gradient pursuit （MGP）algorithm was proposed used to reduce the reconstruction time and improve the reconstruction precision of the compressed sensing direction tracking algorithm. The algorithm combined the cell generation method of regularized orthogonal matching pursuit，utilizing non-monotonic and un-precise Armijo linear search to determine step size， and using MGP to lock search direction， which could reduce reconstruction time under satisfactory reconstruction precision. In this study，the former formula of direction parameters for MGP was inferred and improved， and the formula with higher efficiency was afforded， which made the proposed algorithm to save time 30% compared with Conjugate gradient tracking algorithm，and could also reconstruct two-dimensional images of grian precisely. Experimental results indicated that the method proposed in the present study had better reconstruction performance of grain images than other algorithms under the same test conditions.

grain kernels detection；compressive sensing；direction tracking；memory gradient method；image reconstruction

TP391.9

B

1673-2383(2017)06-0074-06

http://kns.cnki.net/kcms/detail/41.1378.N.20171226.1723.026.html

網(wǎng)絡(luò)出版時(shí)間：2017-12-26 17:24:10

2017-03-17

河南省科技發(fā)展計(jì)劃項(xiàng)目（162102310405）；河南省基礎(chǔ)與前沿計(jì)劃項(xiàng)目 (152300410079)；國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（2017YFD0401003）

許德剛（1978—），男，河南周口人，副教授，研究方向?yàn)橹悄軆?yōu)化算法、圖像處理。

*通信作者