基于并行计算的图像检索技术的研究.doc

基于并行计算的图像检索技术的研究赵树梅，姜学军（沈阳理工大学 信息科学与工程学院，辽宁 沈阳，110159）摘 要：由于图像处理和检索过程中的数据量巨大，而且各种算法中大量卷积运算和矩阵乘法运算的存在，为图像处理过程中的并行算法设计和实现提供了可能。提高图像的处理的速度是由图像数据的特点和图像处理算法的复杂性引起的。并行计算是提高处理和检索速度的有效手段之一。所以将以并行算法在图像处理和检索中的应用为研究对象，重点研图像处理和图像检索的并行算法处理，并且证明多核环境下实现的基于内容的图像检索提高图像的检索技术大大提高了图像的检索速率。 关 键 词：图像处理；图像检索；并行计算；多核技术Image retrieval based on parallel computing technology researchZhao Shumei,Jiang Xuejun(Shenyang Ligong University,Shenyang 110159,China)Abstract: As the image processing and data retrieval process was great, and the various algorithms in a large number of convolution and matrix multiplication of the existence of parallel image processing algorithm design and implementation possible. Improve the speed of image processing features from image data and image processing algorithms due to the complexity. Parallel computing is to improve the processing speed and effective means of retrieval. Therefore, in parallel algorithms in image processing and retrieval application for the study, focusing on research retrieval of image processing and image processing algorithms in parallel, and that multi-core environment to achieve content-based image retrieval improved image retrieval technology greatly improves image retrieval rate.Key Words：image processing; image retrieval; parallel computing;multi-core technology1 引言本文重点研究并行算法在图像处理和检索中的应用，采用并行计算机，分析和研究合适的图像处理的并行算法，以提高图像的处理速度，满足系统的实时性要求 。本文对基于多核系统图像的并行处理和检索技术进行深入的研究，实现图像处理和基于内容的图像检索的并行化。以便提高海量图像数据的检索速度。2 基于并行计算的图像检索技术 2.1 图像处理的并行算法在现代科技许多领域，图像处理起着非常重要的作用。但图像处理在使用中的困难在于它的数据量非常巨大，有时很难满足实时处理的时间要求。解决这个问题一般有两种代表性途径，一是采用专用硬件来实现，二是采用并行处理。由于图像处理一般是计算密集型的，而且普通的图像算法都有非常规则的结构，相似的操作在不同的图像像素或图像部分上操作，因此，图像处理是很利于并行实现的。在数字图像处理中的运算并行可分为两类：流水线并行与数据并行。流水线并行可用如下的方式表达Y = F（X）=Fn（Fn-1（F2（F1（X） ） ） ）式中，X为输入图像；Y为输出图像；F为某种算子。它是把处理单元按顺序串联在一起，即一个处理单元的输出和下一个处理单元的输入相连接。如果一个大任务可以分解成一些复杂性大致相同的小任务，而且这些小任务都能独立完成，就可以采用这种流水线结构来构成并行处理系统。在这种流水线结构里，多种任务在流水线的各级上同时执行，整个任务的速度取决于执行时间最长的子任务的执行时间。在流水线中，任何一个处理单元出现的故障都将直接破坏整个流水线的正常工作，所以这种流水线结构里，对每一个处理单元都有严格的要求。在采用流水线的图像处理中，整个处理节奏是以同一速率进行的。对于图像处理，一个完整的图像检索系统需要不同的图像处理操作，如果这些操作中某些操作之间具有完全独立性，那么就可以使它们在多个处理器上同时执行。数据并行可以用以下表达方式表示：Y = F（X）= F1（X）| F2（X）| | Fn（X）式中， X 为输入图像； Y 为输出图像； F 为某种算子，符号 “|” 表示并行执行。它是用多个处理单元组成一个并行阵列，每一个处理单元都可以独立执行任务。对于图像并行处理来说，这是一种常见并有效的底层并行化图像处理方法，它先把图像分成块，然后把这些块分到各个处理器上，每个处理器对它们那块进行同样的图像处理。于底层图像处理来说，像素级及区域间的图像处理占主导地位，所以，处理是非常局部的，因此，处理器能相对独立的处理从而实现并行化。2.2 基于内容的图像检索技术所谓的基于内容的检索(CBR，Content-Based Retrieval)，是指直接根据描述媒体对象内容的各种特征进行检索。它根据用户提出的反应媒体内容特征的查询要求，能从数据库中查找到具有指定特征或含有特征内容的图像(包括视屏片段)，它区别于基于关键词的检索手段，融合了图像处理、模式识别、计算机视觉、图像理解、数据库管理等多种技术，具有如下特点： 1、直接从媒体内容中提取信息线索；2、基于内容的检索是一种内容匹配，这一点常规数据库检索方法有明显不同；3、特征提取和索引建立可由计算机自动实现，避免了人工描述的主观性，也大大减少了工作量。 图像特征的提取与表达是基于内容图像检索技术的基础。从广义上讲，图像的特征包括基于文本的特征(如关键字、注释等)和视觉特征(如色彩、纹理、形状等)两类。由于基于文本的图像特征提取在数据库系统和信息检索等领域中己有深入的研究，所以主要讨论图像视觉特征的提取和表达。视觉特征可分为通用的视觉特征和领域相关的视觉特征。前者用于描述所有图像本身固有的特征，与图像的具体类型或内容无关，主要包括色彩、纹理、形状和空间关系;后者则建立在对所描述图像内容的某些先验知识(或假设)的基础上，与具体的应用紧密有关，例如人的面部特征或指纹特征等。由于领域相关的图像特征主要属于模式识别的研究范围，并涉及许多专业的领域知识，在此我们就不再详述，而只考虑通用的视觉特征。对于某个特定的图像特征，通常又有多种不同的表达方法。由于人们主观认识上的千差万别，对于某个特征并不存在一个所谓最佳的表达方式。事实上图像特征的不同表达方式从各个不同的角度刻画了该特征的某些性质。3 系统设计与实现本系统包括图像特征提取和检索引擎两大模块，图像特征提取是从图像数据库读取图像进行预处理，图像的预处理采用的是图像的并行处理算法，然后对预处理后的图像提取图像特征，将特征向量保存到特征数据库; 图像检索引擎模块是用户通过一个查询接口提交待查图像，然后对待查图像进行特征提取，匹配待查图像的特征与特征数据库中的特征向量，依据最小距离分类法，将与待查图像的相似图像按着相似度的大小反馈给用户。图像的特征提取及图像匹配均采用多线程的并行技术，使检索系统的速度得以提高。图1.1是图像检索系统的体系结构: 图1.1 系统体系结构图像预处理部分主要负责图像的前期处理，为后面的特征提取做准备。图像的预处理采用并行的图像处理算法，提高大量图像数据的处理速度。经过处理后的图像本系统提取的图像特征有形状和纹理特征，为了减少图像颜色和背景的干扰，因此将输入图像进行灰度化处理。(1)并行程序初始化。初始化并行环境，得到总进程数、当前进程号及并行环境的当前时间，这些并行环境的参数主要用来实现计算任务的动态分配和得到算法运行的时间，以衡量算法的优劣。MPI_Init (&argc ,&argv) ; /并行程序初始化MPI_Comm_rank(MPI_COMM_WORLD ,&my_rank);MPI_Comm_size(MPI_COMM_WORLD ,&group_size);(2)结点0 读入图像文件，分为文件头和文件数据。从文件头中得到一些有用参数文件大小，图像高、宽，每个像素点的位数，再把文件数据读入缓冲区内，以数组形式保存在结点0 中。(3)并行实现图像处理的算法。for (y = 0 ;y = line ;y + )for (x = 1 ;x g2) if (g2 g3) g = g2 ;elseif (g1 g3) g = g3 ;else g = g1 ;elseif (g1 g3) g = g1 ;elseif (g2 g3) g = g3 ;else g = g2 ;*(tempdata + i) = g ;(4)动态分配计算任务，数据分散在各个进程中。由进程0 收集这些结果。 (5)输出执行时间4 实验与分析实验一是有大量图像需要输入时，在单线程、双线程和四线程情况下，处理不同数量图像的时间长度。实验利用双核计算机，即第一套硬件配置的硬件环境进行测试，实验结果如表1.1所示： 表1.1 运行时间对照表图片 平均处理时间/s数量 单线程 双线程 四线程10 45 25 23 50 223 124 116 100 445 241 209 300 1383 747 659 500 2268 1382 1023实验二是在大量图像输入时，比较单线程，双线程和四线程情况下，系统处理图像的时间长度，采用第二套硬件配置的电脑进行测试，实验结果如表1.2 表1.2 运行时间对照表图片 平均处理时间/s数量 单线程 双线程 四线程10 44 27 17 50 183 131 71 100 425 263 159 300 1342 782 359 500 2061 1213 6965 结论在理论和实际问题中，设计并实现了一个图像检索原型系统，实现了并行算法的基于内容的图像检索系统，并实现了流线型图像并行处理方法，利用实验得到采用两种不同的并行图像处理方式与传统顺序图像处理方式的比较数据，从而得出结论，证实该系统确实提高了图像特征提取速度。从实验结果中可以看出，当处理的图像数量较少时，采用多线程并行技术，图像处理速度提高不明显，当图像数量较多时，采用多线程并行技术使图像处理速度明显提高;当采用双核CPU进行四线程处理时，效果与采用双线程处理时无明显差别，因为双核CPU最多只支持双线程同时运行，而采用四线程处理时，同一时间也只有两个线程在运行，因此，时间差别不明显;同时可以看到，当在CPU所支持的能同时运行的线程数范围内，随着线程数的增加，处理图像的效率有显著提升。参考文献：1 孙世新,卢光辉.并行算法及其应用 M.北京:机械工业出版社,2005.2Amir Said,William A Pearlman.A new, fast, and efficient image code based on set partitioning in hierarchical trees 1996(6) :243-2503C.-c.Chen,H.Wactlar，J.Z.Wang,and K.Kierman.Digital imagery for significant cultural and historical materials-Aing resear field briding people,culture,and technologie