|
The semivariogram is a statistical measure of the spatial distribution of data and is based on Markov Random Fields
(MRFs). Semivariogram analysis is a computationally intensive algorithm that has typically seen applications in the
geosciences and remote sensing areas. Recently, applications in the area of medical imaging have been investigated,
resulting in the need for efficient real time implementation of the algorithm. The semivariogram is a plot of
semivariances for different lag distances between pixels. A semi-variance, γ(h), is defined as the half of the expected
squared differences of pixel values between any two data locations with a lag distance of h. Due to the need to
examine each pair of pixels in the image or sub-image being processed, the base algorithm complexity for an image
window with n pixels is 𝑂(𝑛2). Field Programmable Gate Arrays (FPGAs) are an attractive solution for such
demanding applications due to their parallel processing capability. FPGAs also tend to operate at relatively modest
clock rates measured in a few hundreds of megahertz, but they can perform tens of thousands of calculations per
clock cycle while operating in the low range of power. This paper presents a technique for the fast computation of
the semivariogram using two custom FPGA architectures. The design consists of several modules dedicated to the
constituent computational tasks. A modular architecture approach is chosen to allow for replication of processing
units. This allows for high throughput due to concurrent processing of pixel pairs. The current implementation is
focused on isotropic semivariogram computations only. Anisotropic semivariogram implementation is anticipated to
be an extension of the current architecture, ostensibly based on refinements to the current modules. The algorithm is
benchmarked using VHDL on a Xilinx XUPV5-LX110T development Kit, which utilizes the Virtex5 FPGA.
Medical image data from MRI scans are utilized for the experiments. Computational speedup is measured with
respect to Matlab implementation on a personal computer with an Intel i7 multi-core processor. Preliminary
simulation results indicate that a significant advantage in speed can be attained by the architectures, making the
algorithm viable for implementation in medical devices
|
