基于代数多重网格的图像传感器物体识别技术

黄 颖，王文斌，郑弘晖（.重庆邮电大学软件工程学院 重庆 南岸区 400065；.北京邮电大学电子工程学院 北京 海淀区 00876）

基于代数多重网格的图像传感器物体识别技术

黄 颖1，王文斌1，郑弘晖2
（1.重庆邮电大学软件工程学院 重庆 南岸区 400065；2.北京邮电大学电子工程学院 北京 海淀区 100876）

物联网中的物体识别可以减少人为的参与，提高物物相连的效率。该文针对物联网环境中的物体识别进行了初步研究，提出了一种结合代数多重网格的物体识别的方法，降低了物理存储和网络传输的代价。首先运用代数多重网格方法对不同模糊程度的图像进行重建，在此基础上进行特征检测；然后运用“词袋”模型对使用了代数多重网格方法与未使用该方法的物体识别进行了对比试验。实验结果表明，运用一定程度的模糊图像识别物体能得到较高的稳定性，并且提升了与非同一场景的物体识别的区分度；运用代数多重网格方法的“词袋”模型提高了物体识别的准确率。

代数多重网格；特征提取；图像重建；物体识别；物联网

目前物联网的应用越来越广泛，物物相连带给人们很多方便，但物联网应用还处于初级的人工参与阶段，如何实现物物相连的智能化是目前的研究热点［1］。现在的物联网主要通过条形码等对物体进行分类，条形码可以携带的信息有限，不能直观地描述物体，这需要人工编码将条形码和实际物体一一对应。因此直接使用物体识别的方法将条形码和物体类型进行关联，通过摄像传感器识别物体，以减少人为的参与，更好地实现物物相连。图像数据一般较大，如果能够在不影响识别效果的基础上减少图像的存储和传输空间，就会进一步扩大物体识别在物联网中的应用。

基于代数多重网格方法（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-），男，博士，副教授，主要从事数字图像处理、模式识别和人工智能方面的研究.