﻿ 基于和表的互相关计算方法在超声弹性成像中的性能分析
 光电工程  2019, Vol. 46 Issue (6): 180437      DOI: 10.12086/oee.2019.180437

1. 西南石油大学计算机科学学院，四川 成都 610500;
2. 密歇根理工大学，密歇根州 霍顿 49931，美国

Performance analysis of a sum-table-based method for computing cross-correlation in GPU-accelerated ultrasound strain elastography
Peng Bo1, Luo Shasha1, Yang Feng1, Jiang Jinfeng2
1. School of Computer Science, Southwest Petroleum University, Chengdu, Sichuan 610500, China;
2. Department of Biomedical Engineering, Michigan Technological University, Houghton, Michigan 49931, USA
Abstract: The calculation of correlation is critically important for ultrasound strain elastography. The sum-table based method for the calculation of the normalized correlation coefficient (ST-NCC) can greatly improve computational efficiency under an environment of serial computing. Its implementation and performance are yet to be investigated when given a parallel computing platform, particularly, under a GPU environment. In this study, the published ST-NCC method was implemented into GPU and its performance was evaluated for speckle tracking. Particularly, the performance of the ST-NCC method was compared to the classic method of computing NCC using simulated ultrasound data. Our preliminary results indicated that, under the GPU platform, the implemented ST-NCC method did not further improve the computational efficiency, as compared to the classic NCC method implemented into the same GPU platform.
Keywords: speckle tracking    block-matching    normalized cross-correlation    sum-table    ultrasound strain elastography

1 引言

2 方法 2.1 超声散斑运动追踪方法

 图 1 超声散斑运动追踪流程示意图 Fig. 1 Diagram of ultrasonic speckle motion tracking process
2.1.1 归一化互相关算法

 ${R_{{\rm{ncc}}}}(m, n, {\tau _x}, {\tau _y})\\ = \frac{{\sum\nolimits_{m = u}^U {\sum\nolimits_{n = v}^V {f(m, n) \cdot g(m + {\tau _x}, n + {\tau _y})} } }}{{\sqrt {\sum\nolimits_{m = u}^U {\sum\nolimits_{n = v}^V {{f^2}(m, n)} \cdot \sum\nolimits_{m = u}^U {\sum\nolimits_{n = v}^V {{g^2}(m + {\tau _x}, n + {\tau _y})} } } } }},$ (1)

2.2.6 算法实现与数据分析

3 结果

 图 3 不同片上优化策略下算法的计算时间对比 Fig. 3 Comparison of computation time for method 1 under different optimization strategies

 图 4 两种方法的运动追踪性能比较。(a)和(d)为用方法一的CPU串行实现计算得到横向和轴向位移；(b)和(e)为由(a)和(d)计算得到的对应横向和轴向应变；(c)和(f)为两种方法的CPU串行实现之间的横向和轴向位移差；(g)和(i)为方法一的CPU串行实现与GPU并行实现之间的横向和轴向位移差；(h)和(j)为两种方法的GPU并行实现之间的横向和轴向位移差 Fig. 4 A comparative performance analysis of CPU and GPU implementations. (a) and (d) are lateral and axial displacements obtained using CPU implementation of method 1; (b) and (e) are corresponding strain images; (c) and (f) are difference images of lateral and axial displacements between two methods on CPU; (g) and (i) are difference images of lateral and axial displacements between the CPU and GPU implementations of method 1; (h) and (j) are the difference images of displacement between GPU implementation of method 1 and method 2

 图 5 不同互相关追踪窗口两种算法计算时间。(a)两种方法CPU实现随互相关追踪窗口变化时的计算时间；(b)两种方法GPU实现随互相关追踪窗口变化时的计算时间 Fig. 5 Comparison of computation time of two method under different cross-correlation tracking windows. (a) Computation time of CPU implementation of the two methods; (b) Computation time of GPU implementation of the two methods

 图 6 不同搜索范围条件下两种算法计算时间。(a)两种方法CPU实现随搜索范围变化时的计算时间；(b)两种方法GPU实现随搜索范围变化时的计算时间 Fig. 6 Comparison of computation time of two methods under different search ranges. (a) Computation time of CPU implementation of two methods; (b) Computation time of GPU implementation of two methods
4 讨论

5 结论

 [1] Jiang J, Hall T J. A parallelizable real-time motion tracking algorithm with applications to ultrasonic strain imaging[J]. Physics in Medicine & Biology, 2007, 52(13): 3773-3790. [Crossref] [2] Chen L J, Treece G M, Lindop J E, et al. A quality-guided displacement tracking algorithm for ultrasonic elasticity imaging[J]. Medical Image Analysis, 2009, 13(2): 286-296. [Crossref] [3] Peng B, Wang Y Q, Hall T J, et al. A GPU-accelerated 3-D coupled subsample estimation algorithm for volumetric breast strain elastography[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2017, 64(4): 694-705. [Crossref] [4] Zhou Y J, Zheng Y P. A motion estimation refinement framework for real-time tissue axial strain estimation with freehand ultrasound[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2010, 57(9): 1943-1951. [Crossref] [5] Luo J W, Konofagou E E. A fast normalized cross-correlation calculation method for motion estimation[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2010, 57(6): 1347-1357. [Crossref] [6] Zhu Y N, Hall T J. A modified block matching method for real-time freehand strain imaging[J]. Ultrasonic Imaging, 2002, 24(3): 161-176. [Crossref] [7] D'Hooge J, Bijnens B, Thoen J, et al. Echocardiographic strain and strain-rate imaging: a new tool to study regional myocardial function[J]. IEEE Transactions on Medical Imaging, 2002, 21(9): 1022-1030. [Crossref] [8] Konofagou E E, D'Hooge J, Ophir J. Myocardial elastography--a feasibility study in vivo[J]. Ultrasound in Medicine & Biology, 2002, 28(4): 475-482. [Crossref] [9] Lewis J P. Fast template matching[J]. Proceeding of Vision Interface, 1995, 32(4): 351-361. [Crossref] [10] Yang X, Deka S, Righetti R. A hybrid CPU-GPGPU approach for real-time elastography[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2011, 58(12): 2631-2645. [Crossref] [11] Peng B, Huang L. GPU-accelerated sub-sample displacement estimation method for real-time ultrasound elastography[J]. Opto-Electronic Engineering, 2016, 43(6): 83-88. 彭博, 黄丽. GPU加速的高精度位移估计方法及超声弹性成像应用[J]. 光电工程, 2016, 43(6): 83-88 [Crossref] [12] Peng B, Chen Y, Liu D Q. Investigation of GPU-based ultrasound elastography[J]. Opto-Electronic Engineering, 2013, 40(5): 97-105. 彭博, 谌勇, 刘东权. 基于GPU的超声弹性成像并行实现研究[J]. 光电工程, 2013, 40(5): 97-105 [Crossref] [13] Rosenzweig S, Palmeri M, Nightingale K. GPU-based real-time small displacement estimation with ultrasound[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2011, 58(2): 399-405. [Crossref] [14] Chang L W, Hsu K H, Li P C. GPU-based color Doppler ultrasound processing[C]//2009 IEEE International Ultrasonics Symposium. Rome, Italy, 2009. [15] Sun X, Wang S S, Song J J, et al. Toward parallel optimal computation of ultrasound computed tomography using GPU[J]. Proceedings of SPIE, 2018, 10580: 105800R. [16] Sengupta S, Harris M, Garland M, et al. Efficient parallel scan algorithms for GPUs[M]//Kurzak J, Bader D A, Dongarra J. Scientific Computing with Multicore and Accelerators. Boca Raton: Taylor & Francis, 2008. [17] Blelloch G E. Scans as primitive parallel operations[J]. IEEE Transactions on Computers, 2002, 38(11): 1526-1538. [Crossref] [18] Jensen J A. Field: A program for simulating ultrasound systems[J]. Medical & Biological Engineering & Computing, 1996, 34(1): 351-352. [Crossref] [19] Luo J W, Bai J, He P, et al. Axial strain calculation using a low-pass digital differentiator in ultrasound elastography[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2004, 51(9): 1119-1127. [Crossref] [20] Du H N, Liu J, Pellot-Barakat C, et al. Optimizing multicompression approaches to elasticity imaging[J]. IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2006, 53(1): 90-99. [Crossref]