An algorithm for optimizing routing of remote sensing image parallel processing based on data partitioning

doi:10.11947/j.AGCS.2019.20160524

Abstract

Abstract: Parallel processing technologies have been widely applied to remote sensing images processing. While previous research has developed many parallel algorithms for processing images, few studies have been focused on synchronous parallel processing for multiple computing tasks when one copy of remote sensing image has many redundant backups under the cloud computing environment. To bridge the research gap, this research proposes a routing optimization algorithm for parallel processing of remote sensing image. Based on data segmentation, the method is developed to solve the dynamic routing optimization problem when applying the parallel technology to remote sensing image distributed storage and processing. Following the introduction of 8 definitions (e.g. model data state, model elements, relative information quantity and matrix mapping) and 6 properties (e.g. directed, transitive, reproductive, multi-dimensional properties), a mathematical model is proposed. Under the framework, the ratio of average computation costs is used as the flag to control horizontal or vertical parallel processing. In addition, typical examples such as quadtree index generation, and quadtree-based target detection are presented for illustrating the application of our model on parallel processing. Finally, through the experiments, we verify the effectiveness of the algorithm, discussing the characteristics and influential factors of the algorithm.

Key words: parallel, remote sensing image, data generation, optimal path, GIS

CLC Number:

P237

FANG Lei, YAO Shenjun, BAO Hangcheng, KANG Junfeng, LIU Ting. An algorithm for optimizing routing of remote sensing image parallel processing based on data partitioning[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 572-582.

References

[1] 吕捷, 张天序, 张必银. MPI并行计算在图像处理方面的应用[J]. 红外与激光工程, 2004, 33(5):496-499. LÜ Jie, ZHANG Tianxu, ZHANG Biyin. Applications of MPI parallel-computing on image processing[J]. Infrared and Laser Engineering, 2004, 33(5):496-499.
[2] 方金云, 何建邦. 并行栅格数据处理网格服务节点软件的关键技术[J]. 地球信息科学学报, 2004, 6(1):17-21. FANG Jinyun, HE Jianbang. Key technology of implementation of computing node software for parallel processing of raster data[J]. Geo-Information Science, 2004, 6(1):17-21.
[3] CROOKES D. Architectures for high performance image processing:the future[J]. Journal of Systems Architecture, 1999, 45(10):739-748.
[4] RITTER G X, GADER P D. Image algebra techniques for parallel image processing[J]. Journal of Parallel and Distributed Computing, 1987, 4(1):7-44.
[5] CHALERMWAT P. High-performance automatic image registration for remote sensing[D]. Fairfax, Virginia:George Mason University, 1999.
[6] 刘志军, 丁明跃, 周成平, 等. 基于并行遗传算法的图像超分辨率复原[J]. 中国图象图形学报, 2004, 9(1):62-68. LIU Zhijun, DING Mingyue, ZHOU Chengping, et al. A parallel genetic algorithm for image super-resolution restoration[J]. Journal of Image and Graphics, 2004, 9(1):62-68.
[7] 陆松, 刘光明. 分布共享存储的遥感图像并行预处理系统结构研究[J]. 计算机工程与科学, 2004, 26(10):56-59. LU Song, LIU Guangming. Research on the parallel preprocessing architecture with distributed shared memory for remote sensing images[J]. Computer Engineering & Science, 2004, 26(10):56-59.
[8] 张发存, 王忠, 赵晓红, 等. 遥感卫星图像几何粗校正的数据并行方法研究[J]. 计算机研究与发展, 2004, 41(7):1200-1206. ZHANG Facun, WANG Zhong, ZHAO Xiaohong, et al. A data parallel algorithm on geometric correction of remote-sensing satellite images[J]. Journal of Computer Research and Development, 2004, 41(7):1200-1206.
[9] 周海芳, 唐宇, 何凯涛, 等. 基于小波的遥感图像全局配准算法研究及其并行实现[J]. 自动化学报, 2004, 30(6):880-889. ZHOU Haifang, TANG Yu, HE Kaitao, et al. An automatic global registration algorithm based on wavelet and its parallel implementation[J]. Acta Automatica Sinica, 2004, 30(6):880-889.
[10] 郑明玲, 周海芳, 刘衡竹, 等. 遥感多图像配准中自动提取特征点的并行算法[J]. 计算机工程与科学, 2004, 26(10):45-48. ZHENG Mingling, ZHOU Haifang, LIU Hengzhu, et al. A parallel algorithm of automatically selecting the characteristic points in the multiple image registration for remote sensing[J]. Computer Engineering and Science, 2004, 26(10):45-48.
[11] 肖汉, 张祖勋. 基于GPGPU的并行影像匹配算法[J]. 测绘学报, 2010, 39(1):46-51. XIAO Han, ZHANG Zuxun. Parallel image matching algorithm based on GPGPU[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(1):46-51.
[12] 王宗跃, 马洪超, 明洋. 基于GPGPU的全波形并行分解算法[J]. 遥感学报, 2014, 18(6):1217-1222. WANG Zongyue, MA Hongchao, MING Yang. GPGPU-based parallel algorithm for full waveform decomposition[J]. Journal of Remote Sensing, 2014, 18(6):1217-1222.
[13] 郑肇葆. 遗传算法与单纯形法组合的影像纹理分类方法[J]. 测绘学报, 2003, 32(4):325-329. DOI:10.3321/j.issn:1001-1595.2003.04.008. ZHENG Zhaobao. Classification of image texture by combination of genetic algorithm and simplex method[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(4):325-329. DOI:10.3321/j.issn:1001-1595.2003.04.008.
[14] 常方正, 赵银娣, 刘善磊. 遥感影像CVA变化检测的CUDA并行算法设计[J]. 遥感学报, 2016, 20(1):114-128. CHANG Fangzheng, ZHAO Yindi, LIU Shanlei. CUDA parallel algorithm for CVA change detection of remote sensing imagery[J]. Journal of Remote Sensing, 2016, 20(1):114-128.
[15] 董志鹏, 王密, 李德仁, 等. 利用对象光谱与纹理实现高分辨率遥感影像云检测方法[J]. 测绘学报, 2018, 47(7):996-1006. DOI:10.11947/j.AGCS.2018.20170690. DONG Zhipeng, WANG Mi, LI Deren, et al. A cloud detection method for high resolution remote sensing imagery based on the spectrum and texture of objects[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(7):996-1006. DOI:10.11947/j.AGCS.2018.20170690.
[16] 刘婧, 李培军. 结合结构和光谱特征的高分辨率影像分割方法[J]. 测绘学报, 2014, 43(5):466-473. DOI:10.13485/j.cnki.11-2089.2014.0087. LIU Jing, LI Peijun. A high resolution image segmentation method by combined structural and spectral characteristics[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(5):466-473. DOI:10.13485/j.cnki.11-2089.2014.0087.
[17] 董志鹏, 王密, 李德仁. 一种融合超像素与最小生成树的高分辨率遥感影像分割方法[J]. 测绘学报, 2017, 46(6):734-742. DOI:10.11947/j.AGCS.2017.20160514. DONG Zhipeng, WANG Mi, LI Deren. A high resolution remote sensing image segmentation method by combining superpixels with minimum spanning tree[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(6):734-742. DOI:10.11947/j.AGCS.2017.20160514.
[18] 黄波, 赵涌泉. 多源卫星遥感影像时空融合研究的现状及展望[J]. 测绘学报, 2017, 46(10):1492-1499. DOI:10.11947/j.AGCS.2017.20170376. HUANG Bo, ZHAO Yongquan. Research status and prospect of spatiotemporal fusion of multi-source satellite remote sensing imagery[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1492-1499. DOI:10.11947/j.AGCS.2017.20170376.
[19] 周海芳, 刘光明, 郑明玲, 等. 遥感图像自动配准的串行与并行策略研究[J]. 国防科技大学学报, 2004, 26(2):56-61. ZHOU Haifang, LIU Guangming, ZHENG Mingling, et al. A research on serial and parallel strategies of the automatic image registration for remote sensing[J]. Journal of National University of Defense Technology, 2004, 26(2):56-61.
[20] 胡晓东, 骆剑承, 沈占锋, 等. 高分辨率遥感影像并行分割结果缝合算法[J]. 遥感学报, 2010, 14(5):917-927. HU Xiaodong, LUO Jiancheng, SHEN Zhanfeng, et al. Data sewing algorithm for parallel segmentation of high-resolution remotely sensed image[J]. Journal of Remote Sensing, 2010, 14(5):917-927.
[21] 杨景辉. 遥感影像像素级融合通用模型及其并行计算方法[J]. 测绘学报, 2015, 44(8):943. DOI:10.11947/j.AGCS.2015.20150059. YANG Jinghui. The generalized model and parallel computing methods for pixel-level remote sensing image fusion[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(8):943. DOI:10.11947/j.AGCS.2015.20150059.
[22] 史园莉, 李海涛, 宋朝达, 等. 一种基于通用模型的遥感影像并行处理算法——以PCA融合为例[J]. 遥感信息, 2011(3):14-18, 120. SHI Yuanli, LI Haitao, Song Chaoda, et al. A remote sensing data parallel processing algorithm based on general model:with an example of PCA fusion[J]. Remote Sensing Information, 2011(3):14-18, 120.
[23] 刘坡, 龚建华. 大规模遥感影像全球金字塔并行构建方法[J]. 武汉大学学报(信息科学版), 2016, 41(1):117-122. LIU Po, GONG Jianhua. Parallel construction of global pyramid for large remote sensing images[J]. Geomatics and Information Science of Wuhan University, 2016, 41(1):117-122.
[24] 祁昆仑. 基于视觉特征的高分辨率光学遥感影像多任务分类研究[J]. 测绘学报, 2017, 46(6):802. DOI:10.11947/j.AGCS.2017.20170081. QI Kunlun. Multi-task classification of high resolution optic remote sensing images based on visual features[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(6):802. DOI:10.11947/j.AGCS.2017.20170081.
[25] 方雷. 基于云计算的土地资源服务高效处理平台关键技术探索与研究[D]. 浙江大学2011. FANG Lei. Exploration and study on key technologies of high performance platform for land resource service based on cloud computing[D]. Zhejiang University 2011.