基于代數多重網格的圖像傳感器物體識別技術

黃 穎，王文斌，鄭弘暉（.重慶郵電大學軟件工程學院 重慶 南岸區 400065；.北京郵電大學電子工程學院 北京 海淀區 00876）

基于代數多重網格的圖像傳感器物體識別技術

黃 穎1，王文斌1，鄭弘暉2
（1.重慶郵電大學軟件工程學院 重慶 南岸區 400065；2.北京郵電大學電子工程學院 北京 海淀區 100876）

物聯網中的物體識別可以減少人為的參與，提高物物相連的效率。該文針對物聯網環境中的物體識別進行了初步研究，提出了一種結合代數多重網格的物體識別的方法，降低了物理存儲和網絡傳輸的代價。首先運用代數多重網格方法對不同模糊程度的圖像進行重建，在此基礎上進行特征檢測；然后運用“詞袋”模型對使用了代數多重網格方法與未使用該方法的物體識別進行了對比試驗。實驗結果表明，運用一定程度的模糊圖像識別物體能得到較高的穩定性，并且提升了與非同一場景的物體識別的區分度；運用代數多重網格方法的“詞袋”模型提高了物體識別的準確率。

代數多重網格；特征提??；圖像重建；物體識別；物聯網

目前物聯網的應用越來越廣泛，物物相連帶給人們很多方便，但物聯網應用還處于初級的人工參與階段，如何實現物物相連的智能化是目前的研究熱點［1］?，F在的物聯網主要通過條形碼等對物體進行分類，條形碼可以攜帶的信息有限，不能直觀地描述物體，這需要人工編碼將條形碼和實際物體一一對應。因此直接使用物體識別的方法將條形碼和物體類型進行關聯，通過攝像傳感器識別物體，以減少人為的參與，更好地實現物物相連。圖像數據一般較大，如果能夠在不影響識別效果的基礎上減少圖像的存儲和傳輸空間，就會進一步擴大物體識別在物聯網中的應用。

基于代數多重網格方法（AMG）進行物體識別可以有效地避免上述問題。進行物體識別時只需要物體的關鍵信息［2］，即能反映該物體基本特征的信息即可。當識別一個人時，在1km處能發現這個人的大致形狀，在500m處能大致判斷這個人的性別，而在300m處就能識別這個人是誰。實際上在小于300m時會增加更多的關于這個人的信息，但對于識別這個人而言，增加的信息都是多余的。因此只需要保存300m處所知道的這個人的信息，而更近的信息不需要保存，這樣就可以節約大量的存儲空間、傳輸空間和處理時間，同時不影響識別效果。

1982年文獻［3］提出了代數多重網絡的概念，2001年文獻［4］作了一個較為系統的陳述。AMG方法僅利用方程組本身的信息來求解代數方程組［5］，允許在無結構的網格上進行求解，因此更容易擴展到圖像去噪、圖像分割等領域［6-8］。目前的主要思路是根據處理的問題構建相應的PDE方程，然后利用AMG方法進行優化求解。AMG方法的本質是一種多粒度的方法。在問題求解過程中，使用方法跟求解域之間應該有一個比較切合的頻段，如果頻段達到共振，就能取得事半功倍的效果。AMG方法相對于金字塔結構而言，它增加了粗網格調整過程［9］，該過程可以看成是對平滑過程的一個反饋，能將更多的有用信息保留在粗網格之中。對代數多重網格方法得到的粗網格數據進行分析，粗網格中會保留強連接部分而去掉弱連接部分，將這種機制應用到圖像處理，可以發現代數多重網格方法粗化的網格可以提供較為豐富的輪廓信息［10］。在代數多重網格方法粗化的各層數據中，粗網格數據具有圖像的輪廓，變化劇烈的細節部分點分布聚集，平滑模糊部分點分布較稀疏均勻。因此可以在粗網格的基礎上進行特征提取，有效提高特征的區別能力，最終提高物體識別的性能。

1 代數多重網格算法和物體識別基礎

1.1 代數多重網格算法簡介

AMG方法用于求解離散域Ω0上的問題：

式中，A=（aij）n×n，U=（u1，u2，…，un）T；F=（f，f，…，f）T，粗網格的選擇見文獻［11］。在粗12n網格Ωm上，可以得到越來越小的代數方程組：

式中，m=1，2，…，M；n=n1＞…＞nM；A1=A，U1=U，F1=F。

代數多重網格的大致流程為：1）初始為Ω0，在此網格上做若干次迭代，將誤差投影到Ω1，得到A1U1=F1；2）再做若干次迭代，將誤差投影到下一級網格中，繼續迭代求解；3）然后在最粗的網格Ω上，得到AMUM=FM。由于此時階數較低，所

M以可直接求出精確解；4）最后一步步迭代回去，誤差一步一步地返回到原來的網格中，就可以快速地得到問題的精確解。

1.2 物體識別的基礎

物體識別主要研究用計算機對物體進行分類，是人工智能的重要組成部分。常用的物體識別方法包括：決策理論方法、句法方法、人工神經網絡方法和“詞袋”模型方法［12］等?；凇霸~袋”模型的物體識別方法因為計算簡單，對噪聲、光照變化和局部遮擋更加魯棒等特點引起了廣泛關注。識別步驟如下：

1）輸入原始圖像，首先檢測圖像中的興趣點，對興趣點進行特征描述，形成sift或其他特征向量；2）通過K均值等聚類方法對訓練樣本的特征向量進行量化，生成的聚類中心即為所謂的視覺單詞，所有的聚類中心匯總成視覺詞典；3）統計每個樣本中的視覺單詞形成直方圖，對訓練樣本的直方圖進行參數模型學習，形成模型庫；4）對圖像進行特征檢測，得到該圖像所有的視覺單詞，并將圖像表示為視覺單詞的直方圖；5）將圖像的直方圖與模型庫進行對比，最終完成分類識別。

物聯網環境下進行物體識別，需要更進一步考慮縮小識別對象范圍的問題。如一個倉儲應用，只對倉儲所涉及的那些類別的物體建立識別庫，則可以大大減少識別庫的空間。同時再對圖像傳感器采集得到的數據進行壓縮，得到每個樣本的反映關鍵特征的圖像，用于進行物體識別則會提高系統的處理速度。

2 基于AMG方法的特征檢測和物體識別算法的步驟

借鑒Normalized-Cut方法，將圖像轉化為圖G（V，E），其中，V為圖像的像素點，E為圖像的像素點的相似度?？梢酝ㄟ^構建圖像的親和力（affinity）矩陣W來表示E。若一幅圖像的尺寸為M×N，親和力矩陣為M×N維。像素間的相似度可利用權函數計算，常用的權函數有：

式中，Fi、Fj分別為灰度圖像中像素點i、j的灰度值；xi為像素點的空間坐標；σl為圖像灰度值高斯函數的標準差；σx為圖像空間位置函數的標準差；r為兩節點的有效距離。

AMG粗網格提取的算法為：

1）構造網格序列

首先構建圖像的親和力矩陣W，得到最細的網格Ω1，v1為該網格上的點集；再使用限制算子得到粗網格Ω2，v2為該空間的點集。表達式為：

2）擴充網格

將N層粗網格Ω1，Ω2，…，NΩ還原成原始圖像大小的Ω′1，Ω′2，…，Ω′N。粗網格Ωk中對應位置的數據直接進入到Ω′k，對應的元素值I（x，y）為1，其他為0，即表達式為：

3）網格與圖像對應

根據粗網格Ω′1，Ω′2，…，Ω′N構建對應重建圖像R1，R2，…，RN，采取如下策略：

①如果網格Ω′k中的數據是1，Rk對應位置的像素r（x，y）為圖像相應位置的灰度值；

②如果網格Ω′k中的數據是0，Rk對應位置的像素r（x，y）等于相鄰節點數據的網格插值結果，插值可以選擇cubic、linear等方法。由于cubic插值方法總體光滑性較好，較為符合圖像像素的特性，本文選擇cubic插值方法，則有：

在Rk的基礎上提取圖像的sift特征描述符或centrist特征描述符，形成特征直方圖。采用SVM等方法對所有訓練樣本的直方圖進行參數模型學習，最后進行分類識別。

3 實驗結果及其分析

實驗首先對mother圖片提取的清晰區域進行不同模糊程度的高斯過程；然后對所有的圖像進行代數多重網格方法重建，得到一系列不同清晰度的圖像，其中blur1～blur5為對原始圖像進行模糊處理的結果，且模糊程度不斷遞增。在此基礎上進行sift特征檢測和匹配，圖1和表1給出了6幅不同清晰度圖像的sift特征匹配的結果。圖1中對應圖中的特征匹配線絕大部分都是平行的，說明代數多重網格對于sift特征檢測到的特征點位置影響不大。從實驗結果中可以發現，模糊圖像與清晰圖像之間能夠進行較好的特征匹配。

圖1 sift特征匹配結果圖

表1 代數多重網格sift特征匹配數量

圖2 使用AMG重建的結果進行圖像檢索

近年，基于內容的圖像檢索得到了廣泛的關注，它與物體識別類似，強調特征的區分性。本文首先針對圖像檢索進行相應的實驗。實驗使用IOSB軟件進行圖像檢索，在Prof.James Wang提供的圖庫（http://wang.ist.psu.edu/docs/related.shtml）搜索圖像。因為mother圖片是灰度圖片，所以首先將圖像搜索庫中所有圖片處理成灰度圖片。然后使用代數多重網格方法和小波方法對不同模糊程度的圖片進行重建，將重建結果作為待搜索圖像，最后IOSB系統從組成的圖像搜索庫中尋找出25幅最接近待搜索圖片的圖像，實驗結果分別如圖2和圖3所示。從圖2中可以看出，6幅圖片中用不同高斯模糊的圖像都可以搜索出所有的正確圖片，查全率和準確度均為100％。而從圖3中可以看出，當原始圖像mother和blur1作為待檢索圖像時，圖2a和圖2b中沒有檢索出所有正確的圖像。

從圖3中可以發現圖像越清晰，小波重建對于干擾識別的特征去除得不夠，這也是造成搜索問題的主要原因所在。代數多重網格方法能將主要的特征保留，將干擾識別的特征去除，因此能得到較好的搜索結果。下面從搜索結果的相關值方面對匹配結果進一步分析，將模糊程度與搜索準確性之間的關系進行定量的說明。

圖4和圖5為選擇的mother及模糊化圖片和第一張非該序列的圖片，按檢索出的相關值的距離進行的排序。由圖4統計結果可知，當待搜索圖片處于一定模糊度時，檢索出的正確圖片的相關值會很接近，因此檢索結果會變得更穩定，其中blur3在第六到第七的跳變最大，即區分同一場景物體和不同場景物體的能力最強。

圖3 使用小波重建的結果進行圖像檢索的情況

而圖5中可以看到，使用相同的待搜索圖像，小波重建后的圖像搜索出的圖像相關值明顯比代數多重網格重建的圖像相關值小，即小波在圖像的重建過程中不能很好地提取出圖像的關鍵特征。從以上實驗結果可以得出，使用代數多重網格重建的圖像保留了圖像最本質的特征，而去掉區分度不大的特征，只需要保存和傳輸某一個模糊程度的圖像的影像，這樣可以減少網絡傳輸信息和存儲信息的空間，保證同類場景物體的識別精度，提高不同場景物體的區分度。

圖4 使用AMG重建不同高斯模糊的待檢索圖像的檢索結果

圖5 使用小波重建不同高斯模糊的待檢索圖像檢索結果

本文應用“詞袋”模型［15］對各種光照和環境下的C1樣本（87張茄子圖片），以及從Caltech-101庫（http://www.vision.caltech.edu/Image_Datasets/Caltech101/Caltech101.html#Download）中隨機選取的C2樣本（800張飛機圖片）、C3樣本（42張錨圖片）和C4樣本（42張螞蟻圖片）共4個樣本庫（971張圖）進行了多組物體的物體識別實驗，實驗結果如表2所示。表中前4個是在原始圖像基礎上進行特征檢測和物體識別；后4個先使用AMG方法重建圖像，在重建結果的基礎上進行特征檢測和物體識別。其中只對C3樣本（錨圖片）進行了粗網格提取，其他的圖片都使用原始圖片。實驗的其他參數相同，這樣可以突出粗網格提取的圖片對物體識別的貢獻情況。從表2中可以看到，C3樣本物體識別的結果有較為明顯的優勢，同時總體平均識別率也有一定的提高，證明了本文算法的有效性。

表2 在原始圖像和AMG重建圖像中進行物體識別的結果

4 結束語

本文將代數多重網格方法應用于物聯網中的物體識別。使用代數多重網格進行圖像的重建，在重建的基礎上進行特征檢測和物體識別。該方法在減少物理存儲和網絡信息的傳輸的前提下，還能進行較好的物體識別。通過實驗驗證，本文方法能夠較為穩定地使用模糊程度的圖像識別清晰圖像和不同程度模糊的圖像，而且也對最終的物體識別率有一定程度的提高。傳統AMG的應用一般強調AMG方法在解決PDE方面的優勢，而本文則著重在代數多重網格方法提取圖像特征方面的能力，并將其應用于特征優化和物體識別，這在一定程度上擴展了代數多重網格方法的應用領域，但這方面的研究還有待于進一步深入。該方法在編碼中采用了Python、matlab和C++的混合編程，因此程序執行時間較長，不能較好地滿足實時的要求。目前該方法處理一幅512×512的圖像需10s多（Intel core2 duo CPU 2.26 GHz×2，2 GB，64位平臺）。

本文研究得到重慶郵電大學博士啟動基金（A2012-20）的支助，在此表示感謝。

［1］MATTERN F，FLOERKEMEIER C.From the internet of computers to the internet of Things［J］.Informatik- Spektrum，2010，33（2）：107-121.

［2］ZHU Min-chen，WANG Wei-zhi，LIU Bing-han，et al.Improved prototype selection in synergetic pattern recognition to recognize human face expressions［J］.Journal of Algorithms ＆Computational Technology，2013，7（4）：541-552.

［3］BRANDT A，MCCORMICK S，RUGE J.Algebraic multigrid（AMG）for automatic multigrid solution with application to geodetic computations［R］.Fort Collins，Colorado，USA：Institute for Computational Studies，1982.

［4］STüBEN K.A review of algebraic multigrid［J］.Journal of Computational and Applied Mathematics，2001（208）：281-309.

［5］FALGOUT R D，SCHRODER J B.Non-Galerkin coarse grids for algebraic multigrid［J］.SIAM Journal on Scientific Computing，2014，36（3）：309-334.

［6］XU Yi-ping，CHEN Han-lin.An improved model for image denoising［C］//2013 IEEE International Conference on Signal Processing Communication and Computing（ICSPCC）.［S.l.］：IEEE，2013：1-4.

［7］ZEEUW P M.A multigrid approach to image processing［J/OL］.Scale Space and PDE Methods in Computer Vision，2005（3459）：396-407.［2014-09-20］.http://link.springer.com/chapter/10.1007％2F11408031_34.

［8］DUARTE-CARVAJALINO J M，SAPIRO G，VELEZREYES M.et al.Multiscale representation and segmentation of hyperspectral imagery using geometric partial differential equations and algebraic multigrid methods［J］.IEEE Transactions on Geoscience and Remote Sensing，2008，46（8）：2418-2434.

［9］SIAM J.An algebraic multigrid approach for image analysis［J］.Soceity for Industrial and Applied Mathematics，2003，24（4）：1218-1231.

［10］HUANG Ying，XIE Mei，LI Wei-sheng，et al，A new application with algebraic multigrid method［J］.Journal of Information and Computational Science，2012，9（6）：1447-1454.

［11］CHANG Qian-shun，LI Zheng-feng.New interpolation formulain algebraic multigrid method［J］.Chinese Journal of Computational Physics，1990，7（4）：453-460.

［12］ZHANG Hui.Bag-of-words model based image classification and evaluation of image sample quality in remote sesning［C］//IEEE TENCON 2013.Xi’an：IEEE，2013.

［13］史培林.代數多重網格法及其在圖像重構的應用［D］.北京：中國科學院，2003．

SHI Pei-lin.Algebraic multigrid method and its application in image reconstruction［D］.Beijing：Chinese Academy of Scienc，2003.

［14］YU Guo-shen，MALLAT S，BACRY E.Audio denoising by time-frequency block thresholding［J］.IEEE Transactions on Signal Processing，2008，56（5）：1830-1839.

［15］趙曉霞，基于優化“詞袋”模型的物體識別方法研究［D］.重慶：重慶郵電大學，2011.

ZHAO Xiao-xia.Research on object recognition based on optimal bag-of-visual-words［D］.Chongqing：Chongqing University of Posts and Telecommunications，2011.

編輯 張 俊

Algebraic Multigrid Based Object Recognition Technology Applied on Image Sensors

HUNG Ying1，WANG Wen-bin1，and ZHENG Hong-hui2
（1.School of Software Engineering Chongqing University of Posts and Telecommunications Nan’an Chongqing 400065；2.School of Electronic Engineering Beijing University of Posts and Telecommunications Haidian Beijing 100876）

Object recognition in the Internet of things（IOT）can make the connection of objects easier by reducing the participation of the people significantly.Because of the particularity of IOT，how to reduce the storage and network transmission cost is an important research topic.In this paper，algebraic multigrid method is proposed to reduce the storage and network transmission costs in the application of object recognition under the environment of IOT.Firstly，the coarse grid data extracted by algebraic multi-grid（AMG）method is reconstructed，then the features are detected for object recognition，and finally，an object recognition experiment is provided by the "bag of words" model in the images reconstructed with and without the algebraic multi-grid method.The experimental results show that the "bag of words" model with algebraic multi-grid method can recognize the blurred objects more steadily than the model without algebraic multi-grid method，and the distinguish degree is improved between the same scenes and the different ones by the method of AMG.Therefore，AMG method can be used as a new feature extraction method in object recognition under the IOT environment.

algebraic multigrid；feature extraction；image reconstruction；object recognition；the internet of things

TP391.4

A

10.3969/j.issn.1001-0548.2015.05.018

2014-10-22；

2014-11?04

重慶市教委科學技術研究項目（KJ1400408，KJ1400407）；重慶市基礎與前沿研究計劃項目（cstc2014jcyjA40043，cstc2014jcyjA10051）；重慶市大學生創新訓練計劃項目（渝教高（2013）27號）

黃穎（1978-），男，博士，副教授，主要從事數字圖像處理、模式識別和人工智能方面的研究.