Solutions of 3-D elliptic PDEs form the basis of many mathematical models in medicine and engineering. Solving elliptic PDEs numerically in 3-D with fine discretization and high precision is challenging for several reasons, including the cost of 3-D meshing, the massive increase in operation count, and memory consumption when a high-order basis is used, and the need to overcome the "curse of dimensionality." This paper describes how these challenges can be either overcome or relaxed by a Tensor B-spline methodology with the following key properties: 1) the tensor structure of the variational formulation leads to regularity, separability, and sparsity, 2) a method for integration over the complex domain boundaries eliminates meshing, and 3) the formulation induces high-performance and memory-efficient computational algorithms. The methodology was evaluated by application to the forward problem of Optical Diffusion Tomography (ODT), comparing it with the solver from a state-of-the-art Finite-Element Method (FEM)-based ODT reconstruction framework. We found that the Tensor B-spline methodology allows one to solve the 3-D elliptic PDEs accurately and efficiently. It does not require 3-D meshing even on complex and non-convex boundary geometries. The Tensor B-spline approach outperforms and is more accurate than the FEM when the order of the basis function is > 1, requiring fewer operations and lower memory consumption. Thus, the Tensor B-spline methodology is feasible and attractive for solving large elliptic 3-D PDEs encountered in real-world problems.

Optical Diffusion Tomography (ODT) is a modern non-invasive medical imaging modality which requires mathematical modelling of near-infrared light propagation in tissue. Solving the ODT forward problem equation accurately and efficiently is crucial. Typically, the forward problem is represented by a Diffusion PDE and is solved using the Finite Element Method (FEM) on a mesh, which is often unstructured. Tensor B-spline signal processing has the attractive features of excellent interpolation and approximation properties, multiscale properties, fast algorithms and does not require meshing. This paper introduces Tensor B-spline methodology with arbitrary spline degree tailored to solve the ODT forward problem in an accurate and efficient manner. We show that our Tensor B-spline formulation induces efficient and highly parallelizable computational algorithms. Exploitation of B-spline properties for integration over irregular domains proved valuable. The Tensor B-spline solver was tested on standard problems and on synthetic medical data and compared to FEM, including state-of-the art ODT forward solvers. Results show that 1) a significantly higher accuracy can be achieved with the same number of nodes, 2) fewer nodes are required to achieve a prespecified accuracy, 3) the algorithm converges in significantly fewer iterations to a given error. These findings support the value of Tensor B-spline methodology for high-performance ODT implementations. This may translate into advances in ODT imaging for biomedical research and clinical application.

Traditional FPGA-based system-on-chip (SoC) design in general is accomplished via separate software and hardware design flows. With such a separate design methodology, extra development overhead has to be paid to meet the final system's performance, size and power consumption requirements. To overcome this development overhead which usually leads to significant increase of the time-to-market, a unified and efficient SoC design flow is needed. The current work addresses this problem via a SoC design flow which allows automatic building of a complete autonomous system on an FPGA in accordance with the need of a specific application. In the proposed design flow the architecture of the generated hardware is tailored to match the parallelism granularity and communication structure of the application. This, in turn, allows the application developer to meet the system's performance, size and power consumption requirements with a short time-to-market. To prove the applicability of the proposed approach, a monitor for real-time electrocardiographic (ECG) signal analysis and a motion detection algorithm have been implemented.

Many practical applications require the reconstruction of images from irregularly sampled data. The spline formalism offers an attractive framework for solving this problem; the currently available methods, however, are hard to deploy for large-scale interpolation problems in dimensions greater than two (3-D, 3-D+time) because of an exponential increase of their computational cost (curse of dimensionality). Here, we revisit the standard regularized least-squares formulation of the interpolation problem, and propose to perform the reconstruction in a uniform tensor-product B-spline basis as an alternative to the classical solution involving radial basis functions. Our analysis reveals that the underlying multilinear system of equations admits a tensor decomposition with an extreme sparsity of its one dimensional components. We exploit this property for implementing a parallel, memory-efficient system solver. We show that the computational complexity of the proposed algorithm is essentially linear in the number of measurements and that its dependency on the number of dimensions is significantly less than that of the original sparse matrix-based implementation. The net benefit is a substantial reduction in memory requirement and operation count when compared to standard matrix-based algorithms, so that even 4-D problems with millions of samples become computationally feasible on desktop PCs in reasonable time. After validating the proposed algorithm in 3-D and 4-D, we apply it to a concrete imaging problem: the reconstruction of medical ultrasound images (3-D+time) from a large set of irregularly sampled measurements, acquired by a fast rotating ultrasound transducer.

We present a new computational method for reconstructing a vector velocity field from scattered, pulsed-wave ultrasound Doppler data. The main difficulty is that the Doppler measurements are incomplete, for they do only capture the velocity component along the beam direction. We thus propose to combine measurements from different beam directions. However, this is not yet sufficient to make the problem well posed because 1) the angle between the directions is typically small and 2) the data is noisy and nonuniformly sampled. We propose to solve this reconstruction problem in the continuous domain using regularization. The reconstruction is formulated as the minimizer of a cost that is a weighted sum of two terms: 1) the sum of squared difference between the Doppler data and the projected velocities 2) a quadratic regularization functional that imposes some smoothness on the velocity field. We express our solution for this minimization problem in a B-spline basis, obtaining a sparse system of equations that can be solved efficiently. Using synthetic phantom data, we demonstrate the significance of tuning the regularization according to the a priori knowledge about the physical property of the motion. Next, we validate our method using real phantom data for which the ground truth is known. We then present reconstruction results obtained from clinical data that originate from 1) blood flow in carotid bifurcation and 2) cardiac wall motion.

We propose a novel method for image reconstruction from nonuniform samples with no constraints on their locations. We adopt a variational approach where the reconstruction is formulated as the minimizer of a cost that is a weighted sum of two terms: (1) the sum of squared errors at the specified points and (2) a quadratic functional that penalizes the lack of smoothness. We search for a solution that is a uniform spline and show how it can be determined by solving a large, sparse system of linear equations. We interpret the solution of our approach as an approximation of the analytical solution that involves radial basis functions and demonstrate the computational advantages of our approach. Using the two-scale relation for B-splines, we derive an algebraic relation that links together the linear systems of equations specifying reconstructions at different levels of resolution. We use this relation to develop a fast multigrid algorithm. We demonstrate the effectiveness of our approach on some image reconstruction examples.

The quantitative assessment of cardiac motion is a fundamental concept to evaluate ventricular malfunction. We present a new optical-flow-based method for estimating heart motion from two-dimensional echocardiographic sequences. To account for typical heart motions, such as contraction/expansion and shear, we analyze the images locally by using a local-affine model for the velocity in space and a linear model in time. The regional motion parameters are estimated in the least-squares sense inside a sliding spatiotemporal B-spline window. Robustness and spatial adaptability is achieved by estimating the model parameters at multiple scales within a coarse-to-fine multiresoluion framework. We use a wavelet-like algorithm for computing B-spline-weighted inner products and moments at dyadic scales to increase computational efficiency. In order to characterize myocardial contractility and to simplify the detection of myocardial dysfunction, the radial component of the velocity with respect to a reference point is color coded and visualized inside a time-varying region of interest. The algorithm was first validated on synthetic data sets that simulate a beating heart with a speckle-like appearance of echocardiograms. The ability to estimate motion from real ultrasound sequences was demonstrated by a rotating phantom experiment. The method was also applied to a set of in vivo echocardiograms from an animal study. Motion estimation results were in good agreement with the expert echocardiographic reading.

We propose a new spatio-temporal elastic registration algorithm for motion reconstruction from a series of images. The specific application is to estimate displacement fields from two-dimensional ultrasound sequences of the heart. The basic idea is to find a spatio-temporal deformation field that effectively compensates for the motion by minimizing a difference with respect to a reference frame. The key feature of our method is the use of a semi-local spatio-temporal parametric model for the deformation using splines, and the reformulation of the registration task as a global optimization problem. The scale of the spline model controls the smoothness of the displacement field. Our algorithm uses a multiresolution optimization strategy to obtain a higher speed and robustness. We evaluated the accuracy of our algorithm using a synthetic sequence generated with an ultrasound simulation package, together with a realistic cardiac motion model. We compared our new global multiframe approach with a previous method based on pairwise registration of consecutive frames to demonstrate the benefits of introducing temporal consistency. Finally, we applied the algorithm to the regional analysis of the left ventricle. Displacement and strain parameters were evaluated showing significant differences between the normal and pathological segments, thereby illustrating the clinical applicability of our method.

We introduce local weighted geometric moments that are computed from an image within a sliding window at multiple scales. When the window function satisfies a two-scale relation, we prove that lower order moments can be computed efficiently at dyadic scales by using a multiresolution wavelet-like algorithm. We show that B-splines are well-suited window functions because, in addition to being refinable, they are positive, symmetric, separable, and very nearly isotropic (Gaussian shape). We present three applications of these multiscale local moments. The first is a feature-extraction method for detecting and characterizing elongated structures in images. The second is a noise-reduction method which can be viewed as a multiscale extension of Savitzky-Golay filtering. The third is a multiscale optical-flow algorithm that uses a local affine model for the motion field, extending the Lucas-Kanade optical-flow method. The results obtained in all cases are promising.

We propose a novel multiresolution-multigrid based signal reconstruction method from arbitrarily spaced samples. The signal is reconstructed on a uniform grid using B-splines basis functions. The computation of spline weights is formulated as a variational problem. Specifically, we minimize a cost that is a weighted sum of two terms: (i) the sum of squared errors at the specified points; (ii) a quadratic functional that penalizes the lack of smoothness. The problem is equivalent to solving a very large system of linear equations, with the dimension equal to the number of grid points. We develop a computationally efficient multiresolution-multigrid scheme for solving the system. We demonstrate the method with image reconstruction from contour points.

We define multiscale moments that are estimated locally by analyzing an image through a sliding window at multiple scales. When the analysis window satisfies a two-scale relation, we prove that these moments can be computed very efficiently using a multiresolution wavelet-like algorithm. We also show that B-spline windows are best suited for this kind of analysis because, in addition to being refinable, they are positive, symmetric and very nearly isotropic. We present two applications of our method. The first is a feature extraction method for detecting strands of DNA in noisy cryoelectron-micrographs. The second is an extension of the Lucas-Kanade optical flow algorithm (see Lucas, B. and Kanade, T., Proc. DARPA IU Workshop, p.121-30, 1981) that assumes a local affine model of the motion field. The results obtained in both cases are very promising.

Wavelet-based methods have become most popular for the compression of two-dimensional medical images and sequences. The standard implementations consider data sizes that are powers of two. There is also a large body of literature treating issues such as the choice of the "optimal" wavelets and the performance comparison of competing algorithms. With the advent of telemedicine, there is a strong incentive to extend these techniques to higher dimensional data such as dynamic three-dimensional (3-D) echocardiography [four-dimensional (4-D) datasets]. One of the practical difficulties is that the size of this data is often not a multiple of a power of two, which can lead to increased computational complexity and impaired compression power. Our contribution in this paper is to present a genuine 4-D extension of the well-known zerotree algorithm for arbitrarily sized data. The key component of our method is a one-dimensional wavelet algorithm that can handle arbitrarily sized input signals. The method uses a pair of symmetric/antisymmetric wavelets (10/6) together with some appropriate midpoint symmetry boundary conditions that reduce border artifacts. The zerotree structure is also adapted so that it can accommodate noneven data splitting. We have applied our method to the compression of real 3-D dynamic sequences from clinical cardiac ultrasound examinations. Our new algorithm compares very favorably with other more ad hoc adaptations (image extension and tiling) of the standard powers-of-two methods, in terms of both compression performance and computational cost. It is vastly superior to slice-by-slice wavelet encoding. This was seen not only in numerical image quality parameters but also in expert ratings, where significant improvement using the new approach could be documented. Our validation experiments show that one can safely compress 4-D data sets at ratios of 128:1 without compromising the diagnostic value of the images. We also display some more extreme compression results at ratios of 2000:1 where some key diagnostically relevant key features are preserved.