Pipeline Architecture and Parallel Computation-Based Real-Time Stereovision Tracking System for Surgical Navigation

This paper studies the development of a real-time stereovision system to track multiple infrared markers attached to a surgical instrument. Multiple stages of pipeline in field-programmable gate array (FPGA) are developed to recognize the targets in both left and right image planes and to give each target a unique label. The pipeline architecture includes a smoothing filter, an adaptive threshold module, a connected component labeling operation, and a centroid extraction process. A parallel distortion correction method is proposed and implemented in a dual-core DSP. A suitable kinematic model is established for the moving targets, and a novel set of parallel and interactive computation mechanisms is proposed to position and track the targets, which are carried out by a cross-computation method in a dual-core DSP. The proposed tracking system can track the 3-D coordinate, velocity, and acceleration of four infrared markers with a delay of 9.18 ms. Furthermore, it is capable of tracking a maximum of 110 infrared markers without frame dropping at a frame rate of 60 f/s. The accuracy of the proposed system can reach the scale of 0.37 mm RMS along the x- and y-directions and 0.45 mm RMS along the depth direction (the depth is from 0.8 to 0.45 m). The performance of the proposed system can meet the requirements of applications such as surgical navigation, which needs high real time and accuracy capability.

Pipeline Architecture and Parallel Computation-Based Real-Time Stereovision Tracking System for Surgical Navigation

This paper studies the development of a real-time stereovision system to track multiple infrared markers attached to a surgical instrument. Multiple stages of pipeline in field-programmable gate array (FPGA) are developed to recognize the targets in both left and right image planes and to give each target a unique label. The pipeline architecture includes a smoothing filter, an adaptive threshold module, a connected component labeling operation, and a centroid extraction process. A parallel distortion correction method is proposed and implemented in a dual-core DSP. A suitable kinematic model is established for the moving targets, and a novel set of parallel and interactive computation mechanisms is proposed to position and track the targets, which are carried out by a cross-computation method in a dual-core DSP. The proposed tracking system can track the 3-D coordinate, velocity, and acceleration of four infrared markers with a delay of 9.18 ms. Furthermore, it is capable of tracking a maximum of 110 infrared markers without frame dropping at a frame rate of 60 f/s. The accuracy of the proposed system can reach the scale of 0.37 mm RMS along the x- and y-directions and 0.45 mm RMS along the depth direction (the depth is from 0.8 to 0.45 m). The performance of the proposed system can meet the requirements of applications such as surgical navigation, which needs high real time and accuracy capability.

一种易于并行求解Euler方程组的分区技术

在具有复杂边界的计算区域内,求解偏微分方程组时,经常需要分区和并行计算,分区方法直接关系到数值计算的并行化程度,本文在应用时间算子分裂方法求解Euler方程组的过程中,提出了一种非常容易实现并行化计算的分区技术.

Numerical Simulation of R-M Instability

In order to capture shock waves and contact discontinuities in the field and easy to program with parallel computation a new algorithm is developed to solve the N-S equations for simulation of R-M instability problems. The method with group velocity control is used to suppress numerical oscillations, and an adaptive non-uniform mesh is used to get fine resolution. Numerical results for cylindrical shock-cylindrical interface interaction with a shock Mach number Ms=1.2 and Atwood number A=0.818, 0.961, 0.980 (the interior density of the interface/outer density p(1)/p(2) = 10, 50, 100, respectively), and for the planar shock-spherical interface interaction with Ms=1.2 and p(1)/p(2) = 14.28are presented. The effect of Atwood number and multi-mode initial perturbation on the R-M instability are studied. Multi-collisions of the reflected shock with the interface is a main reason of nonlinear development of the interface instability and formation of the spike-bubble structures In simulation with double mode perturbation vortex merging and second instability are found. After second instability the small vortex structures near the interface produced. It is important factor for turbulent mixing.

面向高性能数值计算的并行计算模型DRAM(h)

提出了一个基于存储层次的新并行计算模型DRAM（h），并在该模型下对两个经典并行数值计算算法的不同实现形式：四种形式并行了三角方程求解（PTRS）和六种形式无列选主元并行LU分解（PLU），进行了分析。模型分析表明，具有近乎相同时间和空间复杂性的同一算法不同实现形式在该模型下会有完全不同的存储复杂度。作者在日立公司SR2201 MPP并行机、曙光3000超级服务器和中国科学院科学与工程计算国家重点实验室（LSEC）的128节点Linux Cluster等三种并行计算平台上对模型分析结果进行了实验验证。结果表明，该模型分析在绝大数情况下都能较好地与不同实验枰台上的实验结果吻合。个别出现偏差的分析结果，在根据计算平台的存储层次特点修改模型分析的假定后，也能够进行解释。这说明了该模型以不同形式的算法实现进行存储访问模式区分的有效性。对在计算模型中加入指令/线程级并行的可行性和方法的研究是下一步的工作。

机械臂惯性矩阵的并行计算

本文在给出一种非递推形式的逆动力学计算公式的基础上，针对机械臂惯性矩阵的计算提出了一种面向Ｏ（ｎ）个处理器的并行算法，并以ＰＵＭＡ５６０机器人的前３个臂为例进行了计算效率分析

积分偏移的计算几何与并行实现

The Second Round of Oil & Gas Exploration needs more precision imaging method, velocity vs. depth model and geometry description on Complicated Geological Mass. Prestack time migration on inhomogeneous media was the technical basic of velocity analysis, prestack time migration on Rugged surface, angle gather and multi-domain noise suppression. In order to realize this technique, several critical technical problems need to be solved, such as parallel computation, velocity algorithm on ununiform grid and visualization. The key problem is organic combination theories of migration and computational geometry. Based on technical problems of 3-D prestack time migration existing in inhomogeneous media and requirements from nonuniform grid, parallel process and visualization, the thesis was studied systematically on three aspects: Infrastructure of velocity varies laterally Green function traveltime computation on ununiform grid, parallel computational of kirchhoff integral migration and 3D visualization, by combining integral migration theory and Computational Geometry. The results will provide powerful technical support to the implement of prestack time migration and convenient compute infrastructure of wave number domain simulation in inhomogeneous media. The main results were obtained as follows: 1. Symbol of one way wave Lie algebra integral, phase and green function traveltime expressions were analyzed, and simple 2-D expression of Lie algebra integral symbol phase and green function traveltime in time domain were given in inhomogeneous media by using pseudo-differential operators’ exponential map and Lie group algorithm preserving geometry structure. Infrastructure calculation of five parts, including derivative, commutating operator, Lie algebra root tree, exponential map root tree and traveltime coefficients , was brought forward when calculating asymmetry traveltime equation containing lateral differential in 3-D by this method. 2. By studying the infrastructure calculation of asymmetry traveltime in 3-D based on lateral velocity differential and combining computational geometry, a method to build velocity library and interpolate on velocity library using triangulate was obtained, which fit traveltime calculate requirements of parallel time migration and velocity estimate. 3. Combining velocity library triangulate and computational geometry, a structure which was convenient to calculate differential in horizontal, commutating operator and integral in vertical was built. Furthermore, recursive algorithm, for calculating architecture on lie algebra integral and exponential map root tree (Magnus in Math), was build and asymmetry traveltime based on lateral differential algorithm was also realized. 4. Based on graph theory and computational geometry, a minimum cycle method to decompose area into polygon blocks, which can be used as topological representation of migration result was proposed, which provided a practical method to block representation and research to migration interpretation results. 5. Based on MPI library, a process of bringing parallel migration algorithm at arbitrary sequence traces into practical was realized by using asymmetry traveltime based on lateral differential calculation and Kirchhoff integral method. 6. Visualization of geological data and seismic data were studied by the tools of OpenGL and Open Inventor, based on computational geometry theory, and a 3D visualize system on seismic imaging data was designed.

Parallel Fully-Implicit Computation of MHD Acceleration Experiments

A three-dimensional MHD solver is described in the paper. The solver simulates reacting flows with nonequilibrium between translational-rotational, vibrational and electron translational modes. The conservation equations are discretized with implicit time marching and the second-order modified Steger-Warming scheme, and the resulted linear system is solved iteratively with Newton-Krylov-Schwarz method that is implemented by PETSc package. The results of convergence tests are plotted, which show good scalability and convergence around twice faster when compared with the DPLR method. Then five test runs are conducted simulating the experiments done at the NASA Ames MHD channel, and the calculated pressures, temperatures, electrical conductivity, back EMF, load factors and flow accelerations are shown to agree with the experimental data. Our computation shows that the electrical conductivity distribution is not uniform in the powered section of the MHD channel, and that it is important to include Joule heating in order to calculate the correct conductivity and the MHD acceleration.

Parallel Fully-Implicit Computation of Magnetohydrodynamics Acceleration Experiments

A three-dimensional MHD solver is described in the paper. The solver simulates reacting flows with nonequilibrium between translational-rotational, vibrational and electron translational modes. The conservation equations are discretized with implicit time marching and the second-order modified Steger-Warming scheme, and the resulted linear system is solved iteratively with Newton-Krylov-Schwarz method that is implemented by PETS,: package. The results of convergence tests arc plotted, which show good scalability and convergence around twice faster when compared with the DPLR method. Then five test runs are conducted simulating the experiments done at the NASA Ames MHD channel, and the calculated pressures, temperatures, electrical conductivity, back EMF, load factors and flow accelerations are shown to agree with the experimental data. Our computation shows that the electrical conductivity distribution is not uniform in the powered section of the MHD channel, and that it is important to include Joule heating in order to calculate the correct conductivity and the MHD acceleration.

On optimal message vector length for block single parallel partition algorithm in a three-dimensional ADI solver

It has long been recognized that many direct parallel tridiagonal solvers are only efficient for solving a single tridiagonal equation of large sizes, and they become inefficient when naively used in a three-dimensional ADI solver. In order to improve the parallel efficiency of an ADI solver using a direct parallel solver, we implement the single parallel partition (SPP) algorithm in conjunction with message vectorization, which aggregates several communication messages into one to reduce the communication costs. The measured performances show that the longest allowable message vector length (MVL) is not necessarily the best choice. To understand this observation and optimize the performance, we propose an improved model that takes the cache effect into consideration. The optimal MVL for achieving the best performance is shown to depend on number of processors and grid sizes. Similar dependence of the optimal MVL is also found for the popular block pipelined method.

MODIFIED DIRECT TWOS-COMPLEMENT PARALLEL ARRAY MULTIPLICATION ALGORITHM FOR COMPLEX MATRIX OPERATION

A direct twos-complement parallel array multiplication algorithm is introduced and modified for digital optical numerical computation. The modified version overcomes the problems encountered in the conventional optical twos-complement algorithm. In the array, all the summands are generated in parallel, and the relevant summands having the same weights are added simultaneously without carries, resulting in the product expressed in a mixed twos-complement system. In a two-stage array, complex multiplication is possible with using four real subarrays. Furthermore, with a three-stage array architecture, complex matrix operation is straightforwardly accomplished. In the experiment, parallel two-stage array complex multiplication with liquid-crystal panels is demonstrated.

Block and parallel modelling of broad domain nonlinear continuous mapping based on NN

The necessity of the use of the block and parallel modeling of the nonlinear continuous mappings with NN is firstly expounded quantitatively. Then, a practical approach for the block and parallel modeling of the nonlinear continuous mappings with NN is proposed. Finally, an example indicating that the method raised in this paper can be realized by suitable existed software is given. The results of the experiment of the model discussed on the 3-D Mexican straw hat indicate that the block and parallel modeling based on NN is more precise and faster in computation than the direct ones and it is obviously a concrete example and the development of the large-scale general model established by Tu Xuyan.