图像并行处理（共7篇）
图像并行处理 篇1
摘要：运动模糊图像的重构是图像处理中很重要的一个部分,他在照相机防抖、拍摄高清晰图像及运动物体的检测方面都有很重要的作用。介绍运动模糊图像的成因,并推导出运动模糊图像的数学模型及频谱特征,针对水平模糊图像的频谱特征提出一种自动判断运动幅度的算法,并针对多核处理器,采用OpenMP多线程技术进行并行化处理,极大地提高了算法的执行效率。
关键词：图像重构,运动模糊,并行计算,OpenMP
运动模糊图像的重构是图像处理中很重要的一个部分,他在照相机防抖、拍摄高清晰图像及运动物体的检测方面都有很重要的作用。运动模糊,即采集图像时由于采集设备与目标发生相对运动而产生的图像模糊,导致图像质量的降低,即退化。因此,要想在运动过程中采集到清晰度高的图像,就必须要对模糊图像进行处理,即运动模糊图像的重构。
目前,对运动模糊图像重构的关键之一是测量出运动模糊幅度,这主要是靠测量运动模糊图像的频谱中“条纹”,即能量谱的间距。本文提出一种自动提取运动幅度的方法,他带有预处理运动图像频谱的能力,这样可以避免Hough识别直线中出现识别集中的现象。
最后,本文将运动模糊图像的整个算法进行并行化处理,使之能在多核处理器上获得最大的执行效率。本文主要针对水平模糊图像进行重构,并行化处理也只针对水平方向,但由于水平与竖直方向的处理几乎一致,故竖直方向的并行化处理也类似。
1 运动模糊图像重构算法
1.1 运动模糊图像的数学模型
运动模糊图像复原的基本思路:先建立退化的数学模型,然后根据该模型对退化图像进行拟合。图像复原模型可以用离散数学处理,处理项的实现可在空间域卷积,或在频域相乘。胶片上的总曝光量是在快门开闭期间的积分,即运动模糊成像表示为: 成像系统与物体间相对运动造成的像模糊,如图1所示。
设只有像函数f(x,y)相对系统的移动,设:Δx(t)为x方向的移动分量;Δy(t)为y方向的移动分量。在不考虑噪声的情况下,原始图像的退化模型表示为:
undefined
再简化一次,让物体仅在x方向做直线匀速运动,且在曝光时间T内的总位移量为a,物体沿x方向的变换分量为:
undefined
let:undefined
则:
undefined
where:undefined
为沿x方向造成运动模糊的点扩散函数:
undefined
为运动物体沿x方向移动时的图像退化模型。
对运动模糊图像进行重构,首先要确定运动模糊图像的运动幅度。由上面的分析可知,运动模糊图像的运动幅度是以在频域中的条纹,即能量谱数目来表现。因此,要确定运动幅度,只需确定图像在频域中的条纹数目。而由于各个条纹间的距离是固定的,只需要确定图像最中间的两条直线间的间距即可。一般的方法是依靠霍夫变换检测直线的方法,对图像反复霍夫变换去检测条纹,最终识别出中间的两条直线,并计算出他们之间的距离。
1.2 含预处理的自动识别频谱条纹算法
虽然Hough变换可以识别直线,但是如果不对原始图像先进行一次检测,就可能会出现识别直线在“波谷”处过于集中的情况。对此,设计了一种预处理的方法,检测条纹间的“波谷”,这种算法可以写为:
最后,逐行扫描每一个像素,如果该像素所在列的波谷数量超过某一个值,并且该点的亮度值小于一定范围(不能是亮点),那么判定该点为“可能波谷点”,经过上面的一步筛选之后,再用Hough变换来识别这些“可能波谷点”的点所构成的直线,如图2所示。再经过计算,可得到图像的运动幅度。
由于运动幅度已经确定,逆滤波处理相对简单。这里设定逆滤波的h(x,y)为:
其中,N为运动幅度。再经过FFT(将零点与高频部分设为0.5),做相除运算最后经IFFT把图像复原,如图3所示。
1.3 程序算法流程图
程序的算法主要包括几个部分:对图像的快速傅里叶变换,将图像由空间域转换为频域,为以后做频域处理打基础;对图像的频域做运动幅度检测,利用霍夫变换检测直线深谷,最后检测出中间两条直线间的距离,进而判断出运动幅度;在运动幅度以及方向都确定的情况下,采用逆滤波处理进行图像重建,最终将图像重建。算法流程图如图4所示。
2 运动模糊图像重构算法的并行化处理
当今的处理器时代已经由单核向多核发展,应用程序及算法向多核处理器上进行移植,并获取最大执行效率是当前所有研究学者需要考虑的工作之一。算法在多核处理器进行优化,主要依靠多线程技术将算法进行单个任务拆分为多个认为,使得操作系统可以平均分配多核CPU的工做负载。
由上面对运动模糊图像重构的算法分析不难发现,此算法的各个环节都包含着大量的重复并独立的工作,比如快速傅里叶变换,逆滤波处理,可以直接进行算法上的并行化处理;而采用霍夫变换做直线识别,由于识别次数较多,可以进行功能并行。本文中的并行化处理采用OpenMP编译制导语言自动完成。采用OpenMP简单而高效,他可以自动分析当前线程并创建用于执行程序的并行化多线程。
2.1 快速傅里叶变换的并行化处理
由于图像是二维空间的,其傅里叶变换需要横竖2次才能完成。由于行与行之间,列与列之间是独立的,因此采用对行列的并行化处理。这里没有采用碟型网格等高级的并行算法,这主要是考虑到算法执行完毕后需要直接对其结果进行处理,采用碟型网格会带来一些不便,需要额外的处理工作。同时采用行列之间的简单并行已经可以很好的提升并行化效率。图像快速傅里叶变换的程序流程图如图5所示:
程序首先读入图像数据至缓冲区,并将其以二维数组的形式存储。然后首先对水平方向进行FFT处理,由于快速傅立叶变换的可并行特点,因此对每行的FFT的处理可以全部并行化。对竖直方向每列的并行化也如此。未并行与并行之后的CPU使用记录及程序执行时间如表1所示。
2.2 运动检测过程的并行化处理
由于需要采用霍夫变换来进行10次直线,那么对霍夫变换的并行化处理就显得非常重要。虽然霍夫变换具有一定的可并行性,但由于重复次数较多,功能并行对于加速比的提升要高于对霍夫变换算法本身的并行。未并行与并行之后的CPU使用记录及程序执行时间如表2所示。
2.3 逆滤波处理的并行化处理
逆滤波处理过程是整个程序中最费时间的部分,他包括快速傅里叶变换,频域运算和快速傅里叶反变换3部分。幸运的是,这些环节内部均是可独立并行的,因此可对整个逆滤波处理做局部的并行化处理。并行化流程图如图6所示:
程序首先对图像进行快速傅里叶变换,这部分的并行化处理前面已经提到了。接着进行逆滤波处理的相关运算,由于这部分算法的迭代次数较多,运算量较大,所以适合进行对迭代部分的并行化处理。最后对快速傅里叶逆变换的并行,可按照傅里叶变换的并行化处理方法。
2.4 整个程序的CPU运行状态和运行时间
通过用OpenMP将傅里叶变换并行化,运动检测并行化以及逆滤波处理并行化,程序的执行速度大大提升。整个算法并行化前后的CPU使用记录及程序执行时间如表3所示。
3 结 语
随着现代社会数字化技术的普及,数字图像在人们的生活中不可或缺。因此,数字图像处理技术在社会中的应用将越来越广泛。他不仅要求处理的精确性,还要求快速性。精确性主要依靠算法的设计理论,而快速性不仅依靠算法效率,与对其优化的结果也有很大关系。
本文提出一种新的运动幅度检测的方法,在运动模糊图像重构上有一定应用价值。同时,本文对现有的运动模糊图像重构算法进行了并行化处理,使之能够借助多核处理器的强大处理能力,提升算法执行速度。
参考文献
[1]阮秋琦.数字图像处理学[M].北京:电子工业出版社,2001.
[2][美]Rafael C Gonzalez.数字图像处理[M].北京:电子工业出版社,2007.
[3]向世明.Visual C++数字图像与图形处理[M].北京:电子工业出版社,2006.
[4][美]Michael J Quinn.MPI与OpenMP并行程序设计[M].北京:清华大学出版社,2004.
[5]毋立芳.二值运动模糊图像参数提取[J].北京工业大学学报,1996,12(22),4-6.
[6]贺建峰.运动模糊图像的参数估计[J].昆明理工大学学报,1998,12(23):6-7.
图像并行处理 篇2
随着科学技术的发展和社会发展应用需求, 人们对视频图像采集处理高清化, 传输实时化和控制智能化的要求越来越高。高清视频图像在军事、科研、安防、工业生产、医疗卫生等领域得到了更为广泛的应用[1]。
特别在安防行业, 现有系统由于技术、成本和传输距离的原因, 传输带宽都不高, 直接实时传输高清视频图像难以实现, 但是某些关键时刻或者特殊场景却需要高清晰度、高分辨率的图像进行细节的分析处理, 便于智能化的应用。本文为了解决这一个矛盾的需求, 提出了在视频监控系统的前端——图像采集和处理将采集到的原始高清图像数据分成两路同时进行处理的思想:一路按照传统的处理方法压缩处理转为标清视频流传输, 实现监控的实时化;另一路数据由外部扩展SDRAM缓存, DSP实时读取缓存数据进行智能分析处理, 根据分析处理结果决定是否传输高清图像或者结果。基于不同处理芯片在图像处理各层次应用有不同的针对性, 合理分配硬件资源及算法, 能够显著提高系统整体性能。本文采用FPGA+DSP技术实现高清图像采集和处理, 并在硬件层面将数据分路处理。
1 系统结构及原理
本文设计的硬件系统, 就是利用FPGA和DSP对高分辨率CMOS数字图像传感器OV5642进行图像采集和处理。系统完成对FPGA, DSP和OV5642芯片进行初始化。FPGA对OV5642进行全分辨率的数据采集。FPGA将采集到的图像数据成两路处理, 一路直接原始高清数据传输外部SDRAM缓存, 由DSP读取缓存数据进行智能分析处理;另一路由FPGA进行硬件预处理, 将原始高清图像转换为合适的分辨率, 送到DSP片内进行格式转换、压缩等处理后传输到外部接口。DSP根据分析处理结果和设置阈值条件, 决定是否对高清图像数据进行传输。需要传输的图像帧融入数据流中传输。外部扩展的输出接口可以将经过系统处理的数据流传输到本地监控或者远程监控。系统原理框图如图1所示。
在高清实时图像采集处理中, 图像采集的速度高, 低层的预处理中要处理的数据量大, 对处理速度要求高, 但运算结构相对比较简单, 适合用兼顾速度及灵活性的FPGA进行硬件实现。高层的处理算法的特点是处理的数据量较低层算法少, 但算法的结构复杂, 适合用运算速度高、寻址方式灵活、通信机制强的DSP芯片来实现[2]。DSP+FPGA架构的最大特点是结构灵活, 有较强的通用性, 适合于模块化设计, 从而能够提高算法效率, 同时其开发周期短, 系统易于维护和升级, 适合于实时视频图像处理[3]。
在本设计中充分考虑到FPGA和DSP在图像采集处理各层次应用有着不同的优势, 采用FPGA+DSP结构, 通过合理的硬件资源分配及算法处理, 实现了高清图像采集和实时处理。在FPGA内设计采集模块和预处理模块, 充分利用FPGA时钟频率高, 内部延时小, 运行速度快, 全部控制逻辑由硬件完成的特点, 主要完成图像数据采集、数据分路和图像缩放预处理。通过FPGA内模块间协调, 在硬件层面完成数据的分路。在DSP内则是利用DSP运算速度快、寻址方式灵活、通信机制强大等特点, 主要完成系统配置、图像格式转化、压缩处理以及图像的智能分析处理、传输接口配置等。
2 系统硬件设计
2.1 图像采集模块设计
图像采集模块主要包括传感器工作模式配置、图像采集控制和数据传输。整个模块的功能示意图如图2所示。FPGA片内模拟I2C控制器, 将COMS图像传感器OV5642初始化。OV5642[4]在外部时钟VXCLK作用下, 输出Bayer RGB格式图像数据和同步时钟。FPGA内部设计的采集控制器在PCLK, HREF, VSYNC同步时钟作用下, 产生相应控制读写信号, 进行数据传输采集。
通过SCCB总线设置OV5642相关的内部控制寄存器, 实现对OV5642初始化, 从而确定输出分辨率、开窗位置、曝光时间等。SCCB总线是Omni Vision公司特有的一种三线串行摄像控制总线[5]。三线中的SCCB_E为片选信号线, 本文中只有OV5642一个从设备, 所以SCCB_E直接置低, 始终选中OV5642。在模拟I2C控制器控制下, 第一步, SIO_D线传输OV5642的器件地址加上写操作标识, 确定操作的器件和注明是写操作;第二步, 传输内部的目标寄存器的地址;第三步, 传输要设置的数据并写入到对应的寄存器中, 完成寄存器配置。
采集控制器是在FPGA设置的一个时序逻辑控制器, 主要产生OV5642需要的外部时钟XVCLK和根据OV5642输出的像素时钟PCLK, 行参考时钟HREF, 帧同步时钟VSYNC产生读写控制存储信号。通过对PCLK, HREF, VSYNC时钟的计数, 可以得到写满一行或者一帧信号, 为后继处理提供同步时钟和使能信号。
2.2 预处理模块设计
预处理模块主要是利用FPGA可编程性和内部丰富的硬件资源, 在硬件层面选择性的传输数据, 将高清图像的分辨率降低。FPGA采集到的原始图像数据格式为Bayer RGB格式, 每个像素点只有一种颜色分量, 其余颜色分量可以通过插值算法恢复[6,7]。如图3左边所示就是4×4的Bayer RGB格式。为了保持数据格式一致性, 需要每隔2行或者每隔2列选择一个像素传输。本设计采用在行方向上每隔2列选择传输一个像素点, 在列方向上每隔2行选择传输一个像素点。这样能将图像分辨率降低, 达到缩放目的, 如图3所示。
图像数据是逐个像素逐行串行传输的, 在缩放处理上, 利用PCLK, HREF和VSYNC信号时序关系产生计数脉冲和使能信号。在行方向上, 选择传输一个像素点数据后, 利用PCLK作为列计数脉冲, 每过两个脉冲 (隔两个像素点) 再选择传输一个像素点数据, 一直循环选择, 直到处理完一行图像数据。这时根据HREF信号产生列计数器清零信号, 将列计数器清零, 暂停数据选通。在列方向上, 由行计数器利用HREF信号进行计数, 每过两个计数脉冲 (隔两行图像数据) , 重复行方向上的处理方式对当前行进行选择数据传输。如此循环处理, 直到一帧图像数据处理完毕。每帧图像处理完毕信号是由VSYNC信号产生的。同时, VSYNC信号对行计数和列计数器清零, 直到新一帧图像到达, 计数器重新计数, 开始新的一帧图像缩放处理。通过这样的缩放处理, 可以将2 592×1 944的图像降为648×486的图像, 数据量得到减少。预处理模块将缩放后图像传输到DSP中处理。
2.3 SDRAM控制器 (MC) 的设计
SDRAM控制器模块是FPGA内部设计的模块, 用于将图像数据传输到外部存储器暂存。图4为FPGA设计的顶层模块示意图[8]。在MC控制器的内部, 采用状态机来实现数据读写、设置模式寄存器和刷新等操作的命令译码, 产生输出给SDRAM芯片的RAS/CAS/WE/CS/DQM等信号。已经初始化的SDRAM在得到了RAS, CAS, WE的值后开始执行相应的命令[9]。在对SDRAM进行读、写操作过程中, 要先进行页激活操作, 保证存储单元是打开的, 再通过预充电命令实现来关闭存储单元。在进行写操作时, 内部的列地址和数据都会被寄存, 而进行读操作时, 内部地址被寄存, 数据的读取则发生在CAS延迟时间 (通常为1～3个时钟周期) 后。SDRAM顺次的进行读、写操作后, 当达到突发长度或者突发终止指令出现时, SDRAM控制器将终止其操作。
通过SDRAM控制器模块的控制传输, 可以将采集到图像数据实时的传输到存储器件暂存。采用控制器模式具有一定的通用性, DSP可以通过控制器模块直接读取存储图像数据进行分析处理。
2.4 DSP子系统
DSP接收预处理模块输出的降了分辨率的Bayer RGB格式数据到数据缓存器, 再将缓存数据传到片内preview engine模块进行格式转换, 将Bayer RGB格式图像数据转换为YUV422格式数据[10]。DSP对YUV422格式数据进行压缩处理后送到输出端口输出。
DSP通过SDRAM控制器读取SDRAM中的高清原始数据, 进行一些智能化分析处理, 如识别、验证等。根据处理结果和系统设定的阈值如光强变化、动静变化等, 决定是否对当前或者前几帧图像进行传输。高清图像数据传输由DSP通过一定的相关处理结合到输出数据流中传输到后端, 由后端提取出高清原始数据, 进行各种应用。
3 结 语
采用了FPGA和DSP技术, 设计了对CMOS图像传感器进行图像采集和处理系统。该系统直接对CMOS传感器进行原始数据的采集, 为后继处理的灵活性和应用的多样性做好数据基础。在FPGA中将数据分成两路, 一路作为原始数据暂存到SDRAM, 一路按照传统的处理、输出。这样既能实现了传统图像采集处理系统的功能, 又能保存原始的数据为进一步的应用开发提供了硬件基础, 能较好地解决网络传输带宽不足与关键时刻或者关键场景需要高分辨率图像进行分析处理的矛盾要求。采用FPGA+DSP的硬件组合具有相当大的灵活性, 后期功能开发潜力大, 可以根据不同的软件配置, 实现多种功能, 具有良好的应用前景。
参考文献
[1]孙康明, 袁祥辉.PCI9052在图像采集系统中的应用[J].仪器仪表学报, 2004 (8) :554-555.
[2]王建华, 刘缠牢, 陈大川, 等.基于DSP+FPGA技术的实时视频采集系统的设计[J].研究与开发, 2007 (9) :42-44.
[3]刘晓明, 田雁, 许朝辉.基于DSP和FPGA的视频处理系统设计及其实现[J].激光与红外, 2007 (12) :1328-1330.
[4]Omni Vision.OV5642_datasheet (1.11) [M].USA:OmniVision Technologies Inc., 2009.
[5]Omni Vision.Serial camera control bus (SCCB) functionalspecification[M].USA:Omni Vision Technologies Inc., 2003.
[6]BAYER B E.Color i maging array:US, 3971065[P].1976-07-20.
[7]马涛, 汶德胜, 崔巍.Bayer格式图像压缩方法及FPGA实现[J].科学技术与工程, 2006 (6) :1505-1511.
[8]赵釜.基于CycloneⅡ系列FPGA的图像实时采集与预处理系统研究[D].重庆:重庆大学, 2009.
[9]李刚, 李智.SDRAM通用控制器的FPGA模块化设计[J].电子产品世界, 2007 (8) :84-88.
基于网格环境的遥感图像并行分类 篇3
随着航天传感器的进步,大量超高分辨率的遥感图像数据被收集,遥感需处理的数据量越来越大,处理速度要求越来越高。由于现阶段计算机硬件的限制,系统往往会出现图像数据内存溢出或效率低下等技术性问题。即使一些优秀的软件内部能使用一些算法来解决该问题,但由于数据量巨大,会严重消耗系统资源导致系统无反应或者在图像处理中消耗大量时间等状况的发生。计算复杂性问题一直是遥感图像处理中很难克服的瓶颈问题。采用新技术来进行图像处理已成为遥感领域的一项当务之急。
为了实现高速和大容量的图像处理,并行计算以它的优势吸引了越来越多人的关注。集群系统因性价比较高,扩展性好,在遥感图像并行处理中已有应用[1,2]。但这些图像并行处理系统与具体硬件相关性大,通用性差,对系统配置要求高,由于网络带宽的限制和计算机资源的缺乏而几乎不可能在传统网络环境中实现。网格计算为解决这一问题提供了新的思路[3]。网格计算技术将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一体,提供更多的资源、功能和交互性[4]。因此,在新的资源共享环境下,在遥感图像处理中引入网格计算的思想,用以提高图像的处理速度大,是解决当前海量遥感图像处理的非常有效的方式。目前,已有一些对网格环境中的图像处理的研究。文献[5]针对K-Means算法提出了一种基于分块逼近的并行模型; 文献[6]采用MPICH-G2模型和Grid FTP在网格环境下,实现了遥感图像的批量处理; 曾少斌等[3]基于网格环境,通过资源和服务状态属性分析,提供高效的遥感图像融合处理服务; Wang利用网格对遥感图像的非监督分类做了初步研究[7]; Shen等建立了遥感图像处理的分布式并行计算模型[8];Liu等使用网格平台Globus Toolkit 2. 4和贝叶斯分类建立了基于网格环境的遥感图像的监督分类[9]; Sun Jiabo等基于最大似然方法实现了网格环境下遥感图像的自动分类[10]; Gao等建立了M-A模型,在网格环境下,为遥感数据的标准化、共享和集成提供了实际有效的支撑[11]。
1 基于网格环境的遥感图像并行处理的构建
1. 1 基于网格的遥感图像并行处理模型
网格计算是网络上资源共享系统,是图像并行处理的理想环境。本文将分布在各节点机上的计算资源和服务注册登记到网格数据库服务器中,提供对服务的查询,而且可以动态增加节点机和服务到网格环境中,提供了计算资源共享的平台,便于实现对遥感图像并行的处理。设计的网格服务的遥感图像并行分类处理的框架如图1所示。
图1中框架的主要组成:
1) 中心服务器
中心服务器是整个网格结构的核心,它一方面与用户交互,接收用户远程的任务请求信息,将最终结果返回给用户。其重要的工作是对接收任务的分解划分,分类参数的选取,以及任务的调度,与节点机和数据库服务器之间的交互,这些操作对用户都是透明的。
2) 若干节点机
节点机是执行任务的直接者,其上部署了网格服务,由中心服务器调度分类执行任务。其执行状态及有关节点机的信息,在数据库服务器中存储。一台节点机可以部署多个网格服务,也可以同时执行多个处理任务。
3) 数据库服务器
数据库服务器是网格数据和资源的存储池。用户信息,任务信息,节点机的信息以及网格服务注册表都存储在此。
1. 2 基于网格环境的遥感影像分类并行处理流程
用户首先登录到Web门户,通过Web页面提交作业任务,同时提供待分类的遥感图像文件,训练样本文件以及选择分类的方法。中心服务器接收到用户的请求后,通过查询服务注册表来寻找能够处理此类请求的网格服务。同时将建立该任务( 对应数据库服务器上的任务表) ,并对图像进行分块,将用户提交的作业转换成一组相互独立的子任务。根据一定的任务分配策略和调度策略,将分块的图像及分类方法参数传输给各节点机,节点机的信息在数据库服务器中 ( 包括节点机的状态等) 。各节点机处理子分类任务后,将分类结果返回给中心服务器。最后由中心服务器将各子分类结果合并成最终分类结果文件,传输到指定的URL处,用户可通过FTP客户端访问该URL获取结果数据。
用户提交和创建遥感图像任务,上传遥感图像数据,在处理的过程中,可以查看遥感图像任务处理的进度( 进展情况) 。
2 构建网格平台的关键技术
2. 1 网格服务
1) 资源服务注册机制
网格计算借助XML,SOAP,UDD和Web Services技术,提供了比其他分布式模型具有更先进的资源共享方法。图2展示了网格计算的资源注册机制。
服务提供者通过资源注册中心注册其共享的资源服务,服务请求者从资源注册中心查询所需要的服务,从获取的信息中与能完成其任务的服务提供者建立联系。资源注册中心对网格系统中的任何成员提供服务注册和服务查询,提供一个公众的地址。其功能类似UDDI( universal description discovery and integration) ,网格计算通过网格服务技术实现所有服务注册过程。在上述的网格环境下的遥感影像并行处理架构中,数据库服务器充当了资源注册中的资源的管理,通过服务注册和服务监测,以及与中心服务器的交互,实现资源服务注册机制。
2) 网格节点文件传输服务
文件传输服务实现对系统中网格节点之间的相互通信及文件传输。包括网格系统中心服务于网格节点之间,网格系统数据服务器与网格节点之间,网格节点之间的相互通信及文件传输,在具体网格服务封装中,该传输服务被分解为文件发送服务与文件接收服务。此服务建立在传统的文件发送接收技术基础之上,将传统的文件发送接收流程通过Globus Toolkit 4框架封装成为网格服务。在此给出了网格节点文件传输服务的流程设计。
文件传输发送服务业务流程设计如下:
1文件传输发送服务需要传入要发送的文件句柄、发送者要填写目标IP、端口号。它们来自于Globus Toolkit 4框架的factory与instance服务传入。这两个服务通过给定的URI来调用指定节点机的网格服务并传入从数据库节点机表查询出的文件传输发送节点IP与端口后和指定的传输文件路径;
2发送服务给接收服务一个是否准备接收确认包,接收端收到确认包后回复一个接收确认包,发送者收到确认包,判断是否接收文件,如果不接收,则传输结束,如果接收,则准备发送文件;
3发送服务将会打开要发送的文件,将文件指定字节读入缓冲区。并在最后填写字符是最后一个文件缓冲区标志,然后发送给接收端;
4发送完最后一个文件片段时,文件传输结束;
5将整个文件发送服务逻辑封装成为Globus Toolkit 4框架下的网格服务。
3) 网格节点目录创建服务
在网格的每台节点机上自动创建系统所需的文件目录结构,由于在网格遥感图像处理系统中需要访问节点机或者中心服务器中存在的数据资源,或者需要节点之间进行数据文件传输。因而需要为这些数据资源提供标准化的目录结构。并且在用户使用系统时,用户会创建一些遥感图像处理任务,这些任务名称由用户自由创建,系统会根据用户提供的任务名称结合系统目录创建规范来进行路径拼接,并将拼接后的路径加入到目录系统中,最后由调用节点机上的网格目录创建服务根据传入的目录数据结构进行目录创建工作。
在中心服务器与节点计算机中的目录系统并不是一成不变的。它会随着系统后期功能添加动态改变目录结构,根据用户创建遥感图像处理任务名称对应生成文件目录结构。因此,能更好地适应网格遥感图像处理系统后期开发及维护。
4) 遥感图像分类处理服务
系统将遥感图像分类算法( 如监督分类的SVM,决策树等)封装成为网格服务,部署在网格的节点机中。远程计算机可以通过调用封装好的网格服务在节点计算机中进行图像处理,并将结果返回给中心服务器。
图像的分类通过数据并行模式实现。一幅图像的分类操作被划分成对若干小块的分类操作,再对分块操作的结果进行合并生成整个图像分类的结果。遥感图像的空间划分是根据图像的大小确定划分的策略( 划分数量和分块大小) ,依据划分策略,将原图像划分为多个块,分别生成子图像文件,并记录下各子块之间的顺序。当各子图像文件在各节点机处理完毕后,返回的结果依照各子块之间的排列顺序依次合并,得到最终的处理结果。
2. 2 任务的调度
当用户从客户端提交的任务创建后,其信息存放在数据服务器中( 包括任务的优先级及提交时间) 。中心服务器对数据库中那些未处理的任务进行定时扫描,将扫描结果传入任务优先级处理模块,通过对任务优先级的判定将任务分配到不同优先级的集合。同一优先级中的任务再按照FCFS( First ComeFirst Serve先来先服务) 策略进行调度。选定某一任务后,中心服务器分配任务的处理流程如下:
Step1中心服务器对遥感图像文件进行分块,得到n个子图像文件;
Step2如果分类方法需要参数寻优,在此进行参数优化;
Step3中心服务器按照任务的优先级调度,查询数据库服务器,获取空闲的节点机,并将子图像文件以及处理服务请求发送给空闲节点机,同时将该节点机的状态修改为“忙”;
Step4节点机接受中心服务器分配的任务,并调用对应的分类服务进行处理,处理完后,将结果返回给中心服务器; 同时该节点机状态修改为“空闲”;
Step5重复Step3 - Step4 ,直到所有子任务( n个子图像文件) 处理完毕;
Step6中心服务器合并收到的n个处理结果; 并将任务完成信息返回给用户。
3 并行遥感分类实验与结果分析
3. 1 实验网格环境的搭建
根据文中提出的框架和相关算法,设计了一个如图4所示的测试网格环境,硬件的配置如表1所示。由于网格中的中心服务器需要对大数据量的遥感图像数据进行复杂的数据操作,因而,中心服务器需要较高硬件配置; 而网格中的其他节点机由于处理任务简单,并且处理数据量较小配置可相对降低。
3. 2Globus Toolkit 4 软件部署
通过Globus联盟开发的一个软件工具箱Globus Tools 4提供的软件包配置网格平台。Globus Toolkit是由Globus联盟开发的一个软件工具箱,由一些松耦合组件组成的开放源代码的工具箱。本实验网格环境使用此工具箱来构建网格系统。
3. 3 实验结果与分析
在上述搭建的网格环境下,用以遥感图像分类。测试的实例是如表2所示的3幅TM遥感图像( 7个波段) 。
当中心服务器接收到用户客户端提交的遥感分类任务后,先对遥感图像划分若干子块的策略为:
对应于测试的3个图像实例,按照上述策略分类划分为25块,25块和50块。分类的算法采用SVM( Support Vector Machine) ,在Matlab环境中编写后封装成网格服务,部署到节点机中。
实验中遥感图像分类处理所需的时间是指从用户在客户端提交分类任务到任务完成的时间T,包括三个部分的时间,即:
T = T1 + T2 + T3
T1指分类算法参数计算时间,图像分块时间以及图像合并时间( 在中心服务器完成) ; T2指图像在整个处理过程中的传输时间( 客户端与中心服务器,中心服务器与节点机之间的信息传输) ; T3指的是分类服务完成分类操作的时间( 各分类子任务在节点机上的处理时间) 。
对于图像1,文件大小不大,按划分策略分为了25个子块,并行分配给5个节点机处理,完成时间T为10分钟; 而图像2也划分为25块,在5个节点机下的T为12分钟。二者文件大小差别很大,但是所需的T差不多,主要原因是对于小的遥感图像文件,分类处理任务的完成时间T绝大部分花费在图像分块和信息的传输上,即T1和T2。因此,用并行处理的优越性并没体现出来。对于大的遥感图像,并行处理的优越性比较明显。如表3为图像3( 932 MB) 在不同处理的节点机数目下所花费的处理时间T。
当节点机增加时,T1和T2随着增加,而T3逐渐减少。实验中图像3参与处理的节点数目与处理时间的关系如图4所示。当节点数为1时,相当于是单机处理的结果; 随着节点机数目的增加,处理的时间逐渐减少,到达5、6个节点时,处理的时间趋于稳定。
由实验结果表明,构建的网格环境对于遥感图像并行处理在遥感图像较大时,能取得了较好的效果,分类的效率提高明显。
图像3分类的结果如图5所示。
4 结 语
网格技术的出现,为海量遥感图像高效处理提供了理想的环境。本文根据网格计算的特征及基本理论要求,设计了一个基于网格环境的遥感图像分类并行处理框架,该框架支持动态地扩展各类服务和节点机数目。搭建一个测试的网格平台,在节点机上部署了遥感分类的SVM分类服务,远程用户从客户端提交的分类任务,在网格的中心服务器中完成任务的分解,调度分配给个节点机完成。实验结果表明,测试平台实现了网格环境下的遥感图像并行分类的架构,有效提高大容量遥感数据的分类效率,为分布式并行处理遥感图像提供了有效的途径。但实验平台中的节点平台是同构,都是同一类型操作系统下( Windows) 。如何在现有的实验平台上构建异构的节点,充分利用网格环境的资源共享,还在深入研究中。
摘要：随着遥感技术的发展,高分辨率大容量遥感数据的应用,对图像处理效率提出了更高的要求。网格计算因具有分布式、高性能和充分的资源共享性,为海量遥感图像的处理提供了有效的解决途径。针对遥感图像分类,提出基于网格环境的遥感影像并行模型,分析构建此模型的网格服务机制,设计网格服务及任务调度的算法流程。搭建网格实验测试平台,采用封装的SVM分类服务,实现了遥感图像并行分类处理。实验结果及分析表明,测试平台实现了网格环境下的遥感图像并行分类的架构,有效提高大容量遥感数据的分类效率,为分布式并行处理遥感图像提供了有效的途径。
图像并行处理 篇4
关键词：分布式存储,特征索引,并行检索,分片管理
近年来,图像数据量急剧增长,如何有效地检索这些海量图像成为一个迫切需要解决的问题。传统图像检索方法是基于文本的,检索结果依赖于对图像的文字描述而不是图像的内容,造成图像的查准率不高,因此需要直接从待查找的图像视觉特征出发,通过图像的颜色、形状、纹理等特征进行图像检索。基于内容的图像检索[1]中提取的图像特征都是高维的,特征匹配就意味着检索高维的数据。当图像数据量很大时,单机上基于内容的图像检索速率面临巨大的挑战。
HadoOp[2]是Apache下用于分布式计算的开源软件框架,可以使大量的数据在集群上并行处理,在大数据领域得到广泛应用。因此,本文提出Hadoop平台上基于内容的图像检索系统。
1 相关工作
1.1 基于内容的图像检索
基于内容的图像检索技术分为两步,即特征提取和特征匹配。
1.1.1 特征提取
图像特征提取是基于内容的图像检索的基础,常用的特征是颜色特征、形状特征、纹理特征。由于一种特征总是存在无法克服的缺陷,或者检索太慢,或者匹配效果差,目前很多检索技术都是综合多种特征,因此本文采用图像局部不变特征SIFT与颜色特征相结合。
SIFT[3]是一种基于尺度空间对图像缩放、旋转、光照、变化甚至裁剪、遮挡等保持不变性的点特征提取算法。主要包括4个步骤:1)检测尺度空间的极值;2)定位关键点;3)根据图像的局部梯度方向,给关键点分配方向;4)用特征向量来描述关键点。
颜色特征是图像特征中最显著、最可靠的视觉特征,它对图像本身的尺寸、方向、视角的依赖性较小,从而具有较高的鲁棒性。本文用颜色直方图来表达颜色特征。颜色直方图表达了颜色的空间分布信息,统计每种颜色分量的像素数占图像总像素数的比例。
给定一幅图像(fxy)M*N,fxy表示像素点(x,y)处的颜色值,M×N表示图像的尺寸,图像所包含的颜色集记为C,则图像的颜色直方图可表示为
1.1.2 特征匹配
特征匹配过程是计算样本图像与目标图像之间的相似度,获得与样本图像最相似的图像。测量两幅图像之间相似度通常是计算图像特征向量之间的距离,如欧氏距离、马氏距离。本文采用欧氏距离来比较图像相似度,欧氏距离定义如下
式中:Ai和Aj表示两幅图像的特征向量;r是向量的维数。特征向量间欧氏距离越小,则相似度越大。
1.2 Hadoop
Hadoop[5]是一个分布式的计算框架,主要由HDFS、MapReduce组成。HDFS是用于存储大数据的分布式文件系统。MapReduce是用于处理数据的分布式框架,数据处理过程分为两步:Map和Reduce。Map阶段处理输入的数据分片,并输出中间的key-value对。将具有相同key值的key-value对输入Reduce,处理后输出最终的key-value对。
2 并行图像内容检索系统设计
2.1 系统结构
本文设计的并行图像内容检索系统主要3个模块:海量小图片分布式存储(Store)、并行建立图像特征索引(Indexing)、并行图像检索(Retrieve),结构如图1所示。
2.2 海量小图片分布式存储(Store)
Hadoop是针对大数据来设计的,处理海量小文件时非常消耗内存资源,导致效率很低。为了避免Hadoop处理海量的小文件,通常是将小文件组织起来生成MapFile,并自动上传至HDFS进行分布式存储。但MapFile一般针对于文本文件,因此本文提出了针对海量图片数据生成MapFile。
MapFile是排序后的SequenceFile,由两部分组成:分别是data和index。index作为文件的数据索引,主要记录了每个图片的文件名,以及该图片在MapFile文件中的偏移位置。在MapFile被访问的时候,索引文件会被加载到内存,通过索引映射关系可迅速定位到指定图片所在文件位置,并且添加图像时,需要先将图像的文件名按照字典序排序。
2.3 并行建立图像特征索引(Indexing)
图像索引模块中,本文设计了MapReduce[4]框架上并行建立图像特征索引。由于索引Document不支持MapReduce输出类型的Writable接口,所以不能直接使用Document作为MapReduce的输出。因此本文提出了一种索引缓存模式,在内存中并行建立索引,map任务结束后将内存中的索引存入HDFS,该方法有效提高了建立索引的速度。图像特征索引创建流程如图2所示。
1) InputFormat:将HDFS中图像的MapFile作为输入,由于MapFile是排序后的SequenceFile,因此将文件输入格式写为SequenceFilelnputFormat。
2)SequenseFileRecordReader:该类将读入的MapFile分片解析成键值对(Text key,BytesWritable value),key为图像文件名,类型为Text,value为图像内容,类型为BytesWritable。
3) Mapper:Mapper阶段处理由SequenceFileRecordReader解析出的(key,value)键值对。提取出图像的SITF与颜色特征,通过Lucene在内存中根据图像特征建立特征索引,特征索引建立结构如图3所示。最后在close()阶段将内存中的索引存入HDFS。
2.4 并行图像检索(Retrieve)
图像检索时需要在很短的时间内获取检索结果,而MapReduce框架是用来做离线处理的,因此MapReduce并不适用于图像检索。本文提出一种在线并行检索系统,将存储在HDFS中的索引用Katta进行分片部署,将索引分片存储在各子节点上。检索时,同时读取各节点的索引分片进行检索,然后将获得的所有检索结果中前10个合并,并按照从小到大的顺序排序。最终得到特征距离最小的10张图像的名称,只需从图像的MapFile中按文件名获取图像。
3 实验分析
3.1 实验环境
软件环境:Linux操作系统,JDK1.7,Hadoopl.2.1,Opencv、Javacv计算机视觉库,Lucene。
硬件环境:实验使用3个节点,每个节点配置双核Intel CPU,4 Gbyte内存。
3.2 并行创建索引实验结果分析
实验图像总共50 000张,来源于加州理工学院101类图像数据库,加州理工学院256类图像数据库,其中部分图像重复,但具有不同的文件名。将不同张数的图像生成MapFile分别上传至HDFS,使用MapReduce进行离线并行图像特征索引创建,实验对单机建立索引和分布式建立索引的时间进行对比,如图4所示,图中横轴为图像的张数,纵轴为建立索引所用时间。
由图4可以看出,随着图像张数的增加,在单机上建立索引所需时间不断增长;而用MapReduce并行建立索引,所需时间明显少于单机建立索引时间,且时间增长趋势缓慢。
3.3 在线图像检索实验结果分析
实验HDFS中的索引进行分片管理,将索引分片存储在各子节点本地上,由此进行图像的并行检索,实验对图像单机检索和并行检索的时间进行对比,结果如图5所示,图中横轴为图像的张数,纵轴为图像检索所用时间。
由图5可知,图像数据少时,单机进行检索所需时间较少,由于节点间需要通信,所以并行检索所需时间较大;随着数据量增大,单机检索所花费的时间在直线增长,而并行检索花费的时间增长缓慢。当图像数量到5万张时,并行检索速度较单机检索速度提高了33.3%,并行检索速度与文献[6]相比提高了20%。
3.4 图像查准率、查全率
本实验采用信息检索中标准的评估方法:查准率、查全率来对提出的设计进行评估。
查准率是指在一次查询过程中,返回的查询结果中的相关图像数目r与在所有返回图像数目N中占有的比例,表示为
Precision=r/N
查全率指在一次查询过程中,返回的查询结果中相关图像的数目r在图像库中所有相关图像数目R中占有的比例,公式表示为
Recall=r/R
实验在50 000张图像中随机抽取4张图像进行检索,在图像库中每张图像的相关图像共10张,将检索结果按照图像间的距离升序排列,图像查准率、查全率如表1。
以上实验结果表明,本文提出的基于图像特征索引的并行图像检索系统具有相对较高的查全率与查准率。
4 小结
经过以上分析,基于图像特征索引的并行检索系统大大减少了建立图像特征索引时间和基于内容检索图像的时间;SIFT特征与颜色特征结合建立索引,达到了较好的检索效果,该系统有效解决了单机下对海量图像检索效率低的问题。
参考文献
[1]ZHANG C,CHEN T.An active learning framework for contentbased information retrieval[J].IEEE Trans.Multimedia,2002,4(2):260-268.
[2]Hadoop[EB/OL].[2014-04-16].http://www.Hadoop.org.
[3]DAVID G L.Distinct image features from local scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.
[4]DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proc.Symposium Conf.Opearting Systems Design&Implementation.[S.1.]:IEEE Press,2004:107-113.
[5]刘炳均,戴云松.基于超算平台和Hadoop的并行转码方案设计[J].电视技术,2014,38(7):123-126.
图像并行处理 篇5
遥感技术的发展,伴随着遥感图像的分辨率不断提高,导致每一景图像的数据量大增,计算量也相应增加。根据图像数据本身存储的规律性以及相关性特点,其算法也具有一致性、邻域性、行顺序性的特点,自然就为图像并行计算创造了良好的条件。主要体现在:几何图形的并行性、相邻并行性、像素位的并行性和操作的并行性[1]。并行处理总的来说可以分为两类:数据并行性和任务并行。目前对于任务分配的研究取得了一定的成果,提出很多算法模型以及各种任务优先图。如启发式任务分配算法[2]多核处理器与网络处理器任务分配算法的研究等[3]。但专门针对集群环境图像处理过程的图像融合系统中任务分配调度研究相对较少。虽然图像融合的算法和应用取得了一定的进步,但快速有效地提高计算的效率仍是一个具有挑战性的研究课题。图像融合作为图像处理和模式识别过程的重要阶段,涉及到几个问题,其中任务并行对图像处理难度较大,因为同一任务的算法内部之间数据的相关性较大,不易分解,鉴于此我们提出采用数据并行处理的思路,吸取动态负载均衡的任务分配思想提出数据并行计算技术的算法模型。
1 集群环境下的图像融合并行计算
1.1 图像预处理
图像融合的目的就是将多传感器的个体优势转化成融合后的综合优势,更好地为判读解译过程提供服务。将其并行化是提高融合效率、满足图像的快速甚至实时处理要求的有效途径,因此对图像实施诸如增强、消畸变、配准、去噪等预处理,是保证图像融合的关键。本文提到的预处理是对预处理图像进行数据“区域”的划分,这里所提及的“区域”是指一个相互连通的、具有一致性属性的像素集。因此必须先对图像进行灰度处理,然后依据图像的灰度值对图像进行划分,以得到目标对象区域最小边界,最后统计出这些含有目标对象最小多边形的个数,以便将数据分配给集群机进行计算。
图像存储的规律性,是图像以矩阵进行存储与计算的基础,因此改善矩阵计算的并行性是提高图像处理性能的一个重要手段。本文采用四叉树结构对图像进行区块划分与存储。其基本思想是:首先获取待划分区块的四等分线,对每一等份继续按上述方法进行划分,一直等分到子象限上仅为目标对象区域最小长方形区域为止,然后舍弃不含目标对象已划分的区块,统计出含有目标区块的总数。这样就大大减少了对不含目标对象区域的计算时间,区块划分与编码方法如图1所示,所得块状结构用四叉树结构进行组织存储,即把2n×2n像元组成的阵列当作树的节点,树的高度为n级(最多为n级)。每个节点有分别代表北西(NW)、北东(NE)、南西(SW)、南东(SE)四个象限的四个分支。存储树结构如图2所示。
1.2 集群体系数据划分与并行计算
由并行模式的理论可知,分解方法有功能分解和数据分解两种。功能分解指的是将整个执行过程按一定的分解粒度对执行过程进行分解;数据分解指将待融合的图像先进行划分以获得子图,然后再在子图上施加适当的计算。通常对图像分解采用规则的分解,如条状划分或多维划分。虽然子域理论可以小到只有一个像素,而条状划分最小粒度是一行。与文献[6]提到的影像数据划分策略不同,同时也与文献[7]提到的基于小波包串行融合算法中的数据划分策略不同,其思想只是依据图像的区块大小进行划分,如图3所示。在此我们按照上一节介绍的四叉树结构的划分与存储思想,先把一幅图像进行图像的预处理,划分区块获得目标区域的数量,这些数量也就是我们进行并行计算的子图数量。我们仅关注含有目标的区块,因为就目标识别而言,所要计算的目标对象相对较少。如图4所示。依据集群体系结构对处理器节点层级分配策略,采用集中式处理结构,可以自适应地分配处理器节点层级与子图的数量,通过监测各处理器运行状态及预计执行时间,使用任务队列的方式适时地调配待处理的子图数据到处理器节点。
1.2.1 集群体系数据分配策略
分布式集群体系结构四叉树数据处理(以下简称为任务)分配模型可以考虑两方面内容。其一就是任务粒度的划分;其二就是各处理节点的任务分配。由于数据的划分已经在数据预处理阶段完成,下面主要讨论节点的任务分配问题。
如图5所示,首先将系统中所有的网络节点进行分级,初始时分级方法对应四叉树结构,主控节点对应根节点,依次类推。其中主控节点负责向各二级节点分配任务,并收集各二级节点的负载信息;二级节点在收到主控节点分配的任务之后,对三级节点进行调度,安排三级节点进行相应的工作;二级节点同时将自己的负载情况向主控节点汇报,主控节点根据提供的消息在二级节点之间进行负载平衡;三级节点在收到二级节点的命令之后,开始执行相应的任务,并将执行结果返还给二级节点。
考虑到二级计算节点所起的桥梁作用,其它除主控根与树叶位置外的节点算法也类同,因此有必要重点讨论一下二级计算节点的具体算法,描述如图6所示。
在进行具体的算法实现中,采用开源的p RPL函数库辅助实现四叉树节点信息的获取及调度,算法的核心代码如下:
1.2.2 集群体系时间成本计算
传统的单节点图像融合计算就是根据多光谱与高光谱图像的信息对整幅图像各像素点顺序扫描计算,因此融合时间相对较长。然而,集群体系图像融合并行计算的时间总开销主要包括图像分割时间、传输时间、节点图像融合时间和图像再分割时间、返回结果传输时间以及图像拼接规整时间等组成。由于我们摒弃了绝大部分的非目标区域的计算时间,同时采用并行计算与任务动态调度的思想,总计算时间与效率均有改善。具体计算公式为:
其中Max[Tn1,Tn2,Tn3,Tn4]表示按四叉树结构按单任务划分后对下级节点再分割与计算的最长时间,因此这个计算式是一个递归计算过程,取决于递归划分的粒度与计算节点的个数。每划分一次,其计算时间都将有一定的减少,划分后即有:
时间成本计算代码如下:
1.3 图像融合的并行计算
本文采用标准的图像融合方法,通常按如下步骤进行:
1)将原始图像增强、消畸变、校准、去噪;
2)对多光谱图像进行RGB到IHS的变换;
3)对真彩色图像和IHS多光谱图像的亮度成分进行直方图匹配。
首先,用真彩色图像的亮度成分作为融合图像的亮度成分,然后做逆变换以获得融合的RGB图像。
标准融合方法的结果依赖于采用的IHS系统,最常用的亮度变换公式为:
其次,被融合的两幅图像的亮度成分应当在融合之前进行匹配。为校准亮度,要计算每幅图像的亮度的均值和标准差,并用于调整一幅图像相对于另一幅参考图像的亮度成分。其表达式为:
其中I表示原来的亮度值;I'表示校准后的亮度值;σ1,m1分别是第一幅图像的亮度的均值和标准差,而σ2,m2分别是第二幅图像的亮度的均值和标准差。校准了亮度后,两幅图像可用下式进行逆变换到RGB平面:
具体的功能实现过程中,借助IDL函数库实现栅格图像的融合处理,提高并行运算的效率。主要代码如下:
1.4 数据的收集规整
对上述除主控核外的各级核计算结果,主控核负责按划分块即子图的索引ID及其相应的位置信息逐块进行无缝连接,形成一幅完整的融合图像,以便进一步的计算处理。至此,图像融合的整个过程完毕。
2 实验结果与性能分析
基于以上遥感图像的集群并行计算模型与四叉树结构分块策略,我们选取大小为200M左右的高光谱与多光谱遥感影像为融合数据,其中高光谱影像分辨率为14253×14312,数据大小为196Mb,多光谱影像分辨率为7129×7151,数据大小为196Mb,并将图像分别划分为4,16,64块,以单机、集群PC机的个数为1,4,16,64进行了相关测试,测试结果为图像融合进行10次所得的平均值。
测试节点计算环境为:集群系统中每个节点的CPU都为酷睿2代,内存4GB,实验中总共用到了64个节点,整个集群系统通过速度为1Gb/s的以太网相连,系统通过图像划分、融合、合成等步骤,同比单机图像融合计算的效率有所提高。测试结果见表1。
从表1可知,如果采用单机对于一个遥感图片处理,计算时间的代价将大于没有进行集群分割与并行策略。在数据分块数少于计算节点数的情况下,所花费的时间数与等数据块花费的时间相同。对单节点而言,随着分块数的增加,花费的时间也相应增加。另外,随着分块数与节点数的增加,总时间花费减少。
3 结语
基于四叉树结构数据划分策略在海洋遥感目标识别中,可以减少非目标区域的计算时间;整个算法的执行时间不仅跟图像数据划分有关,而且与计算节点数目有关;采用动态任务分配与调度算法也能减少并行运算时间。由于本算法主要关注的是对图像目标区域的划分策略与并行效率,对处理结果的收集与整理考虑欠缺,因此在融合的精度方面将在下一步的研究中加以改进。
摘要：集群体系下的大规模并行计算,是高性能计算的基础。遥感图像处理效率的提高,有赖于并行计算技术的应用。在分析已有网格计算环境下分布式任务分配方法的基础上,针对海上遥感图像目标物数量相对较少的特点,首先利用四叉树结构理念对目标区域进行划分,同时采用动态负载均衡的任务分配策略与并行计算思想,提出对目标区域图像进行融合处理的集群体系任务分配算法处理模型。通过对比验证,表明该集群体系下算法模型能有效地提高图像融合的速度。
关键词：集群计算,并行计算,四叉树结构,图像融合
参考文献
[1]程英蕾.多源遥感图像融合方法研究[D].西北工业大学,2006.
[2]刘轶,等.一种面向多核处理器并行系统的启发式任务分配算法[J].计算机研究与发展,2009,46(6):1058-1064.
[3]刘轶,等.多核处理器大规模并行系统中的任务分配问题及算法[J].小型微型计算机系统,2008,29(5).
[4]Liu Zhen,Rhonda R.Optimal parallel processing of random task graphs[J].Journal of Scheduling,2001,3(4):139-156.
[5]沈占锋,等.高分辨率遥感影像并行处理数据分配策略研究[J].哈尔滨工业大学学报,2006,38(11).
[6]程英蕾,等.一种多传感器图像并行融合新方法[J].空军工程大学学报:自然科学版,2006,7(6).
[7]刘振英,等.一个有效的动态负载平衡算法[J].软件学报,2001,12(4):563-569.
[8]翟亮,等.一种新型的遥感影像压缩质量评价指标[J].武汉大学学报:信息科学版,2007,32(10).
图像并行处理 篇6
随着数字图像处理技术的飞速发展, 图像处理的应用范围不断扩展, 其中图像分割是由图像处理到图像分析的关键步骤。图像分割是为了更好理解图像的内容, 按照实际应用要求和图像内容, 将图像分割成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程[1]。现有的图像分割方法主要分以下几类:基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法等[1,2]。
(1) 基于区域的分割。基于区域的分割算法是指侧重于根据区域内的特征相似性来进行分割的方法, 其基本思想是根据图像的特征将图像划分为不同区域。常见的基于区域的图像分割的算法大致可以划分为三大类, 即, 阈值法、区域生长法以及区域分裂合并法。由于基于区域的分割算法简单、精度较高, 且分割结果较为连续, 因此应用较为广泛。
(2) 基于边缘检测的分割。该方法主要是基于图像一定有边缘存在的假设上进行的, 通过检测图像灰度值的突变来标记出不同区域的边缘。其实现的基本思想为:先检测图像中的边缘点, 再按照一定的规则将边缘合并成轮廓。
(3) 边缘与区域相结合的分割。该方法集成了边缘检测与基于区域分割两者的优点, 一方面通过边缘点的限制避免区域的过度分割, 另一方面通过区域分割补充漏检的边缘来保证图像轮廓的完整性。
目前越来越多的大规模图像处理对计算的速度提出的较高的要求。因此, 本文介绍了一个在GPU的CUDA环境上实现的一个并行算法来提升图像分割的效率。
本文在对现有图像分割算法进行分析的基础上, 对传统图像分割算法中的区域生长法进行了基于CUDA架构的并行化设计改进, 提出一种新型的利于并行实现基于区域的图像分割算法。实验证明, 该设计提高了计算能力和运行速度, 有效缩减程序耗时, 降低算法运行时间。
2 基于CUDA的区域生长算法的并行设计
2.1 串行算法描述和分析
区域生长是根据事先定义的准则将像素或者子区域聚合成更大区域的过程[1,2]。首先从图像中选取某个或某些像素点作为种子点, 再由种子点出发, 向这些点的八邻域内进行搜索与种子点具有某种相似性质的像素点, 并将这些像素点合并到种子点所在的区域中, 每一轮生长的新像素点作为下一轮生长的种子像素点继续迭代地进行上述过程, 直到没有新的点归入该区域。主要根据像素的灰度值进行区域划分, 将灰度值相似的像素点划分在同一区域, 即区域内的像素点灰度值之差不大于指定阈值。
为了方便并行改进, 在经典的串行算法基础上添加了对区域面积的判断以及对各区域的重新标记过程, 即:区域生长完毕之后, 将符合面积标准的区域按序进行标记, 以便进行下一步的图像处理。此外, 考虑到区域面积过大或过小的区域极有可能是背景色或噪声, 因此面积不在给定的面积范围内的区域将被从结果中剔除, 即将该区域标记值置0。串行分割算法流程如图1所示。
通过对上述串行算法进行分析可知, 大量的时间被用于程序的反复迭代及判断, 算法效率不高的主要原因在于以下三点:
(1) 大多数算法采用的主要是交互式人为手动设置种子点, 这一步骤导致程序运行缓慢;
(2) 区域生长过程是一个迭代的过程。其中, 下一轮迭代的结果与上一轮迭代息息相关, 导致程序的串行度较高;
(3) 计算区域面积是一个串行的过程。由于在计算面积的过程中, 每次只能使一个区域面积加1, 当区域面积过大或是区域个数较多时, 该过程将耗费程序的大量时间。
因此, 本文从该算法的问题入手, 利用CUDA架构的特点对原算法重新进行并行设计, 将以上所提的三个耗时点, 即设置种子点、区域生长、计算面积同时放入GPU进行计算, 从而达到缩减程序时间的效果。
2.2 基于CUDA的并行算法设计
在对区域生长串行算法进行分析中可知, 程序的大部分时间都花在区域生长的不断迭代过程中, 因此, 减少迭代次数是实现算法性能提升的关键, 而区域生长算法具有全局统一的特性, 所以本文采用分而治之的方法, 即将图像分成若干块, 先以各个分块为单位同时进行区域生长, 然后再将这些分块进行合并。并行算法具体流程如图2所示。
在CUDA架构下, 计算任务被映射为大量的可并行线程, 因此显卡芯片的最小执行单位是线程。一个线程块中包含多个可以沟通协作的线程, 而执行相同程序的线程块则可以组成一个线程网格。一个线程块内的线程可读取同一块共享内存, 但不同块间线程无法进行数据通信[3]。结合CUDA特点, 本文对块内迭代和块间合并的算法设计如下:
2.2.1 块内迭代
首先将原图像划分为若干个线程块, 即上文中提到的划分块, 然后每个线程块分别执行区域生长算法。为了更好的达到并行化的目的, 本文对传统的区域生长算法进行了改进:采用一个线程处理一个像素点的方式, 在初始化时把所有像素点都作为种子点, 然后跟据阈值判定不断地将相似的种子点合并来完成图像的分割过程, 本文算法主要参考的是文献[4,5]。该并行算法的具体过程如图3所示。
图3 (a) 表示源图像的初始化阶段。其中每一个方块代表一个像素点, 方块上的数字代表该像素点的索引值 (非标记值) 。在这里我们设置阈值为0, 面积范围为[4,6]。图 (b) 和 (c) 表示区域生长过程, 这个过程类似并查集的合并过程, 本文用树的结构来表示, 即:一棵树代表一个区域, 树的根节点是该区域内索引值最小的点。每个像素点都在自己的八邻域内寻找比自己小的索引值, 即寻找自己的父节点。这个过程不断的进行, 最终当树不再变化的时候, 即所有的点都指向根节点的时候, 区域生长完成, 而一个区域的标记值是这个区域内最小的索引值。图 (d) 表示比较面积过程, 其中标记为0, 2, 6, 21的区域面积大小不在指定面积范围内, 因此不对这四个区域进行标记, 并将其中的像素点标记值设为0。图 (e) 表示重新标记过程, 则原始的1, 5, 7标记将分别被修改为1, 2, 3。
2.2.2 块间合并
当块内迭代结束, 再进行块间合并的过程。实现块间合并的步骤如图4所示。
图4中, 左侧的每个小方块代表源图像的一个子集, 即一个线程块。程序合并线程块的过程也是一个迭代的过程。由于线程块和共享存储的大小限制, 因此我们采用了3-D block进行合并, 如图5所示。
其中线程块的x和y维度表示待合并块的x和y坐标, 而线程块的z维度包含一组独立的线程, 用来比较和合并不同块间的区域, 本文线程块的z维度为32。我们主要采用每次合并4×4共16个块的方式来完成块间合并, 以达到迭代次数最少且线程利用率较高的目的。在合并过程中, 先合并每个块的底部水平边界, 再合并右侧的垂直边界, 合并过程主要做的是首先找到这两个像素点对应的区域树根节点, 然后将对应标记值较大的根节点的标记修改为标记值较小的根节点, 即更新较大根节点标记值为较小根节点对应的标记值。
2.3 基于CUDA的并行算法实现
结合CUDA特点, 为了在最大程度上提高算法的执行效率主要采用了如下策略:
2.3.1 块内迭代和块间合并相结合
在对区域生长串行算法进行分析的基础上, 本文提出块内迭代和块间合并相结合的并行改进算法以减少迭代次数。除此之外, 采用块内迭代和块间合并相结合还有另外两个好处:一是块内迭代采用共享内存来进行优化, CUDA中共享内存速度具有极大优势, 通过采用共享内存进行块内迭代, 能够减少算法运行时间时间;二是减少了数据由主存拷贝至显存的拷贝时间, 由于连通区域过程在device端进行, 也就节省了原本需要在主存进行迭代的大量数据拷贝的时间, 从而达到提高性能的目的。
2.3.2 缩减并行度
在进行区域面积的计算时, 本文通过单GPU Thread处理32个像素点, 利用这32个像素点之间的位置与计算关系, 减少计算量以及原子加操作的调用次数, 从而达到提高性能的目的, 如图6所示。
在图6中, (a) 显示了未使用优化策略前计算面积的主要操作; (b) 显示了该过程的处理示意图。该图主要以一个GPU线程处理16个位于同一列的连续像素点为例, 其中灰色区域表示连通部分。图 (a) 显示, 在未使用该优化策略前, 计算左侧灰色连通区域的面积需进行12次原子加操作, 而计算右侧灰色连通区域的面积则需进行16次原子加操作;图 (b) 显示, 使用该优化策略后, 计算左侧灰色连通区域面积总共仅需进行3次原子操作, 而计算右侧连通区域面积则仅需一次原子操作, 其中curvalue是一个线程自有的寄存器变量, 而在CUDA存储器空间中, 寄存器具有最快的运行速度。
2.3.3 在内核中实现重新标记
在对所有区域进行重新标记时, 以往采取的方式是首先将标记值由device端传入host端, 在host端进行一轮排序后再将结果传入device端来实现重新标记过程。而本文算法中, 我们通过申请一个一维线程块和一维线程网格, 并利用共享存储是块内共享的优势来计算每行根节点个数, 再根据行号和在行内的索引找到区域根节点的最终标记值来实现重新标记, 大大减少了程序内存的反复拷贝时间。
3 实验结果及性能分析
实验平台配置:GPU为NVIDIA Tesla C2075 (两块) ;CPU为Intel Core2 i7 2500;内存为12GB DDR 1333MHz, 操作系统为Ubuntu 10.10 Server x64 (kernel 2.6.35-22) ;软件环境:NVIDIA CUDA Driver 270.41.19;CUDA version, 4.0, OpenCV 2.3.1。
实验使用了13幅图像作为测试用例, 所有实验数据均是在相同的实验条件下, 算法循环100次后统计得出。我们从中选择一幅图像进行实验效果描述。实验输入源图像为1024×768的灰度图像, 如图7所示。图像分割后的灰度图像如图8所示。
在算法性能验证方面, 我们主要用三种图来反映程序的执行性能, 分别为概率分布曲线、性能对比图以及加速比图。cv Blob是OpenCV上计算机视觉应用中在二值图像里寻找连通域的库.能够执行连通域分析与特征提取, 与这里讨论的算法基本类似。
(1) 概率密度曲线。曲线上任意一点 (x, P) 代表测试变量小于等于x时的概率为P。该曲线的斜率反映出算法的稳定性, 曲线斜率越大算法波动越小, 表明算法的具有较好的稳定性。实验得到的概率密度累积图像如图9所示, 图中显示本文算法在运行时间内波动较小, 表明具有较好的稳定性。
(2) 性能对比图。它显示了本文算法与cv Blob算法执行时间的对比结果, 如图10所示。从图中可以看到, 总体上本文提出的新型图像分割算法在速度上有一定的优势, 其中, 本文算法处理图像CP00和CP01的时间要稍慢于cvBlobs, 这是由于这两幅图像中背景区域较大, 几乎占了全图的2/3, 而cvBlobs具有不计算背景像素的区域这一特点, 对于背景较大的情况计算速度快, 背景较小的情况速度慢。
(3) 加速比图。它反映了两种算法的执行性能比率。在这里, 我们选择OpenCV的性能为基准, 即OpenCV的加速比将被设置为1。实验得到的加速比图如图11所示。从图中可以看到, 经过CUDA并行改进后的算法对比于与算法类似的cvBlob算法, 速度提升了约2~3倍。
4 结语
本文根据CUDA特性, 针对基于区域生长的图像分割问题, 利用块内迭代和块间合并等多种优化策略, 提出了一种基于CUDA平台的并行图像分割算法。实验结果表明, 该算法与O p e n C V中cvBlob相比, 在运行时间内具有较好的稳定性, 在背景区域较小的情况下速度优势较大, 缩短了计算时间, 提高了算法的工程实用性。
参考文献
[1]Rafael C.Gonzalez, Richard E.Woods.数字图像处理[M].北京:电子工业出版社, 2007.
[2]黄长专, 王彪, 杨忠.图像分割方法研究[J].计算机技术与发展, 2009, 19 (6) :76-79.
[3]罗希平, 田捷, 诸葛婴等.图像分割方法综述[J].模式识别与人工智能, 1999, 12 (3) :300-312.
[4]侯立华.图像分割方法综述[J].科技创新导报, 2008, 22:249.
[5]NVIDIA.CUDA C Programming Guide[EB/OL].http://developer.download.nvidia.com/
[6]张舒, 褚艳利, 赵开勇等.GPU高性能之CUDA[M].北京:中国水利水电出版社, 2009.
[7]Jason Sanders, Edward Kandrot.GPU高性能编程CUDA实战[M].北京:机械工业出版社, 2011.
[8]邹炎, 杨志义, 张凯龙.CUDA并行程序的内存访问优化技术研究[J].计算机测量与控制, 2009, 17 (12) :2504-2506.
[9]Christophe Fiorio, Jens Gustedt.Two linear time Union-Findstrategies for image processing[J].Theoretical Computer Science.1996, 154 (2) :165-181.
[10]Oleksandr Kalentev, Abha Rai, Stefan Kemnitz.ConnectedComponent Labeling on a 2D grid using CUDA[J].Journal of Par-allel and Distributed Computing.2011, 71 (4) :615-620.
[11]In-Yong Jung, Chang-Sung Jeong.Parallel connected-com-ponent labeling algorithm for GPGPU applications[C].Communi-cations and Information Technologies (ISCIT) , Tokyo, 2010:1149-1153.
图像并行处理 篇7
1 算法原理
8阶显示图像的信息范围为[0,255],通常取中间值即127作为量化的阀值,小于127的像素点值统一量化为0,而大于127的像素点值统一量化为1,从而将整个8阶图像信息量化为只有0、1两种数值的矩阵。但是这种量化方法很粗糙,目前流行的转化方法是1975年由Floyd和Steínberg提出的图像误差扩散算法,可以实现在有限色彩显示范围的设备上显示连续色彩范围的数字图像[1][3]。
其处理图像误差的流程分为三步:
(1)量化。
将8阶图像数据量化为1阶图像数据。这时将所有处于[0,127]范围内的像素值量化为0,将所有处于[128,255]范围内的像素值量化为1。
(2)误差计算。
这是误差扩散算法的核心所在,要进行误差计算,首先必须统一量纲。采取的方法是:量化值为0的像素点对应的8阶数值量为0,而量化值为1的像素点对应的8阶数值量为255。误差就是原来的8阶像素值和量化值对应的8阶量值的差。
(3)最后,将误差值分布到区域中相邻的像素上去[1][3]。如图1所示。
图1就是采用FloydSteinberg误差扩散算法将误差传播到相邻的像素上。7/16的误差被加到正在处理的当前像素右侧的像素上,5/16的误差被加到下一行中当前像素正下方的像素上,……。图像中所有的像素都要通过上述误差扩散算法的处理。
误差扩散算法看上去是一个典型的串行算法:在误差被计算出来之后就将其分布到相邻的像素上去,因此要计算下一个像素的值就必须知道前面元素的误差值,这种相关性暗示了程序在一个时刻只能处理一个像素。但是可以从另一个角度思考:一个被扩散误差的数据,只要它所接受的四个误差值都准备好了,就马上可以开始。图2是从接受像素的观点来查看误差扩散算法的[2]。
有了这样的基础,就可以将这种原来是串行计算的算法转换为可以并行执行的算法。如果在系统中存在着两个处理任务,当一个任务处理数据完全产生了对下一行某个数据的三个误差值时,另一个任务就可以马上处理相应的数据了。这时,在系统里同时有两个任务在进行数据的处理,实现了误差数据的并行操作。
2 基于Mailbox的双NIOS实现方案
NIOSⅡ是Altera公司特有的基于通用FPGA构架的软CPU内核,是一个可灵活配置的通用32位RISC嵌入式处理器。NIOSⅡ有快速型(NIOSⅡ/f)、经济型(NIOSⅡ/e)和标准型(NIOSⅡ/s)三种类型。快速型NIOSⅡ内核具有最高的性能,经济型NIOSⅡ内核具有最低的资源占用,而标准型NIOSⅡ在性能和面积之间做了一个平衡。
NIOSⅡ软核处理器具有高灵活性、丰富的可配置外设、存储器和接口、高速的数据处理能力等特点。
(1)高灵活性:
可以在SoPC Builder中添加自定义的外设,可随时根据需要添加外设。
(2)高速的数据处理能力:
NIOSⅡ/s(标准)拥有5级流水线,动态支路预测,可设置指令及数据缓冲,动态支路预测等功能来提升性能。采用用户自定义指令可以实现传统处理器无法达到的最佳系统性能。
(3)Avalon交换架构:
每当系统加入模块或者外设接入优先权改变时,SoPC Builder利用最少的FPGA资源,产生新的最佳Avalon交换架构。Avalon交换架构支持多种系统体系结构,可实现数据在外设与性能最佳数据通道之间的无缝传输[4]。
Altera公司为构建基于NIOSⅡ多核系统提供了两个类型的组件:Mutex和Mailbox。Mutex被用于保证共享资源的互斥使用,而Mailbox用于多个处理器之间的消息通讯。在进行多处理器之间消息通讯和共享时,由于Mutex只能在同一时刻使一个且仅有一个处理器应用处于活动状态,Mailbox能够保证在消息有效时,系统中有多个处理器应用处于活动状态,因而使用Mailbox的效率会比Mutex高。在本设计中,双核系统的通讯工具就采用了Mailbox。图3为基于Mailbox的NIOSⅡ多软核处理器系统的硬件设计框图。
根据并行化误差扩散算法的特点,采用了Mailbox作为传递上一行处理数据时产生的误差值向下一行传递的!工具。系统中有两个NIOSⅡ软核处理器,一个存储原来8阶图像数值矩阵的所有奇数行数据,另外一个存储原来8阶图像数值矩阵的所有偶数行数据,双方通过两个Mailbox进行数据通讯。Even Mailbox传递奇数行产生的误差值给存储有偶数行数据值的NIOSⅡ软核处理器,系统中的SRAM存储器作为存储介质;odd Mailbox传递偶数行产生的误差值给存储有奇数行数据值的NIOSⅡ软核处理器,将系统中的SDRAM存储器作为存储介质。
系统的工作流程分为以下几步:
(1)NIOS处理器1:
顺序扫描第一个奇数行的数据,处理第一个奇数行里面的每一个像素,将产生的误差值送进even mailbox;
(2)NIOS处理器2:
检查even mailbox,发现数据立即将数据放入误差数值矩阵中,启动扫描误差数值矩阵的循环,检查是否有某个偶数行像素点所需要的误差全部准备好的。如果有,进行相应偶数行像素点的处理,这时偶数行像素点也会产生相应的误差值,通过odd mailbox向NIOS处理器1发送;
(3)NIOS处理器1:
检查odd mailbox,发现数据立即将数据放入误差数值矩阵中,启动扫描误差数值矩阵的循环,检查是否有某个奇数行像素点所需要的误差全部准备好的。如果有,进行相应奇数行像素点的处理,这时奇数行像素点也会产生相应的误差值,通过even mailbox向NIOS处理器2发送。
如此循环处理就可以将所有的数据处理完毕。下面说明扫描误差数值矩阵的循环是如何发现某个元素的误差值已经全部准备好的。某行数据处理后产生的误差值的顺序为(1:1)(2:1)(1:2)(2:2)(3:1)(2:3)(3:2)(4:1)(3:3)(4:2)(5:1)(4:3)……。
一行中某个元素将产生3个对下一行有影响的误差值(其中首个元素只产生2个),括号中的第一个数字表示误差值对下一行的哪个元素起作用,1表示对第一个元素起作用,2表示对第二个元素起作用,……;冒号后面的数字表示产生的数值具体对应于哪一个误差因子,1对应的误差因子是3/16,2对应的误差因子是5/16,3对应的误差因子是1/16。下一行相应的数据元素中如果3个误差扩散因子都产生了,NIOSⅡ软核处理器就可以进行数据处理了。根据观察,可以发现,每当产生3个误差数据时,下一行数据元素中一定有一个可以进行处理,这正是发现误差数值准备好的基础。
因此,mailbox传递信息的数据结构设置如下:
数据处理的流程如图4所示。
3 系统特点
基于Mailbox的NIOSⅡ双软核系统,对图像误差扩散算法进行了并行化的设计,实现了预期的目的。由于在系统运行时,有两个处理器任务处于活动状态,从而在硬件和软件两个层面上实现了多核并行。
随着嵌入式应用的飞速发展,系统面临的处理任务和处理数据日益庞大,传统的以单个处理器为核心的系统已经不能满足应用的需求,需要进行多核系统开发。如果使用硬核进行多核系统构建,有着更新难、可配置性能低、价格昂贵的缺点,而使用NIOSⅡ软核处理器和SoPC技术,能够在性能和价格取得平衡,使多核系统更有效,更具灵活性。
参考文献
[1] FLOYD R W,STEINBERG L.An adaptive algorithm for spatial grey scale.Proc.Soc.Inf.Display,1976,17:75-77．
[2] AKHTER S,ROBERTS J.Multi-Core programming[M].USA:Intel press,2007．
[3] FLOYD R W,STEINBERG L.An adaptive algorithm for spatial grey scale.in Proc.Dig.SID International Symp.,pp.36-37,Los Angeles,California(1975) .
[4] 王建校,危建国.SoPC 设计基础与实践[M].西安:西安电子科技大学出版社,2006．