Therapeutic Imaging By K Mean Clustering Algorithm Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

This paper is concerned with a speed up of image processing methods on 2D and 3D images making use of modern FPGA technology. The processing speed ranges in 2000 frames per seconds. The FPGA based hardware implementation profits especially from the high parallelism in the algorithm and preserve the mathematical models. With advances in the VLSI technology hardware implementation has become an attractive alternative implementing complex computation tasks on hardware and by exploiting parallelism and pipelining in algorithms yield significant reduction in execution times. The applications of this methods ranges from 2D and 3D image denoising and restoration, segmentation, morphological shape recovery and matching to vector field visualization and simulation.

Key words: FPGA (Field Programmable Gate Array), VLSI (Very Large Scale Integrated), k-mean clustering, MRI or CT scan images.


Image processing is an ever growing and dynamic area with applications reaching out into our everyday life such as medicine, space exploration, surveillance, authentication, automated industry inspection and many more areas. Applications such as these involve different processes like image enhancement and object detection. Implementing such applications on a general purpose computer can be easier, but not very time efficient due to additional constraints on memory and other peripheral devices. Application specific hardware implementation offers much greater speed than a software implementation.


Imaging architects use high-level software tools to model various algorithms and results. Image modeling tools, such as the Interactive Data Language, are available from companies like RSI, BIR, and Advanced Digital Imaging Research (ADIR). Another trend is the use of open-source toolkits for image registration, segmentation, and image-guided surgery. These tools are optimized for imaging applications and algorithm development via software, but not for implementation into FPGAs.

Algorithmic development in MATLAB software and system-level design in Simulink software are very common DSP design approaches. For example, ADIR, a research and development organization specializing in digital imaging software and algorithm development needs flexible tools to create fast and accurate image-processing algorithms. ADIR has been using MATLAB as a development tool for almost 15 years in its various specialties, including digital image processing, quantitative image analysis, pattern recognition, digital image coding and compression, automated microscopy, forensic image processing, and 2D wavelet transforms. In addition to algorithm development, MATLAB can also simulate the use of fixed-point arithmetic commonly used in FPGAs.


Figure 1: Overview of the Operation

A. Boundary Identification

There are two methods

Level set method

Up Winding method

These are discussed below

1. Level Set Method:

Level set methods play an important role segmentation and for morphing purpose. The motion of an interface G(t) in time t starting from an initial Position G(0) = G0 [1]can be formulated based on an implicit description of the interface. If f(t, x) is the speed of the interface at time t and position x we obtain the partial differential equation.

It can be used to efficiently address the problem of curve/surface/etc. propagation in an implicit manner, provides a direct way to estimate the geometric properties of the evolving structure, Furthermore, they can be used to define an optimization framework as proposed by Zhao, Merriman and Osher in 1996. Therefore, one can conclude that it is a very convenient framework to address numerous applications of computer vision and medical image analysis. Furthermore, research into various level set data structures has led to very efficient implementations of this method.

2. Up Winding Method:

In this process, the image can be divided into layer by layer. To change the layer can be disturb the Processing. The image quality does not change anywhere.

B. Segmentation

Segmentation algorithms are based on one of two basic properties of intensity values is continuity and similarity. First category is to partition an image based on abrupt changes in intensity, such as edges in an image. Second categories are based on partitioning an image into regions that are similar according to predefined criteria. The goal of image segmentation is to cluster pixels into salient image regions, i.e., regions corresponding to individual surfaces, objects, or natural parts of objects. Segmentation could be used for object recognition, occlusion boundary estimation within motion or stereo systems, image compression, image editing, or image database look-up.

In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments (sets of pixels known as super pixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label shared with visual characteristics.


K-means clustering is a very popular clustering technique, which is used in numerous applications. In the k-means clustering algorithm, each point in the dataset is assigned to the nearest cluster by calculating the distances from each point to the cluster centers. The computation of these distances is a very time-consuming task, particularly for large dataset and large number of clusters. In order to achieve high performance, we need to reduce the number of the distance calculations for each point efficiently.

Clustering is a mathematical tool that attempts to discover structures or certain patterns in a data set, where the objects inside each cluster show a certain degree of similarity.  The algorithm is iterative in nature. It is a very popular clustering technique, which is used in numerous applications. In the k-means clustering algorithm, each point in the dataset is assigned to the nearest cluster by calculating the distances from each point to the cluster centers. K stands for number of clusters it is a user input to the algorithm.


In the k-means clustering algorithm, each point in the dataset is assigned to the nearest cluster by calculating distances from each point to the cluster centers. Then, the cluster centers are improved so that the error (sum of the square distances) is minimized. These two steps (called iteration one) are repeated until no improvement of the error is obtained.

The computation of the distances is a very time-Consuming task, particularly for large dataset and large number of clusters. With dedicated hardware systems, we can accelerate the performance of the distance calculations by processing them in parallel.

However, when the number of clusters is large, its performance is not enough for real-time applications, because the distances to all cluster centers cannot be calculated in parallel with reasonable amount of hardware resources. In order to reduce the computation time, many sophisticated software algorithms have been proposed to date. However, it is not easy to implement those techniques on the hardware systems because of their complexity.

X1…XN are data points or vectors Observations. Each observation will be assigned to one and only one cluster. C (I) denotes cluster number for the observation. Rows indicate the features of image and columns denote the components of image,


Distance Metric: Euclidean Distance

Step 1

Figure:2 Selecting the clustering variable at randomly

Step 2

Figure: 3 Finding the distance between the pixels

Step 3

Figure: 4 Grouping the nearer pixels

Step 4

Figure: 5 Grouped pixels


Figure: 6 Final grouped image pixels

The algorithm consists of a simple re-estimation procedure:

First, K centroid points are selected mj, e.g., at random.

Second, each data points is assigned to the cluster Sj of the closest centroid mj.

Third, the centroid mj is recomputed for each cluster set.

The steps two and three are alternated until a stopping criterion is met, i.e., when there is no further change in the assignment of the data points.


All of the components supplied as part of the VHDL Image Processing Source Modules are intended to be run from one system-wide Pixel Clock. For each individual application the maximum frequency of the Pixel Clock will be governed by the slowest operation performed in the pipeline. For many of the components, it is difficult to provide a complete set of performance figures as there are many issues that will affect the overall performance.

For example, by varying the generic N of each component, the overall performance will drop as wider and wider data operations are performed. In addition, many components may be pipelined together. When doing this the Pixel Clock rate will relate to the number of stages of maths performed between one register stage in the pipeline and the next. For this reason, the synchronous/asynchronous generic has been provided so that register stages can be introduced at key points in the pipeline in order to increase the operation frequency.


Medical imaging equipment is taking on an increasingly critical role in healthcare, as the industry strives to lower patient costs and achieve earlier disease prediction using non- invasive means. To provide the functionality needed to meet these industry goals, equipment developers are turning to programmable logic devices.

Earlier prediction and treatment are driving the fusion of modalities such as positron emission tomography (PET)/computerized tomography (CT) and X-ray/CT equipment. The higher image resolutions that are needed require fine geometry micro-array detectors coupled with sophisticated software/hardware systems for the analysis of photonic and electronic signals.

These systems must provide both highly accurate and extremely fast processing of large amounts of image data (up to 250 GMACS and 1 Gbps). Furthermore, to lower patient costs, each piece of equipment must be lower priced and possess a longer life utility. This calls for more flexible systems with the capability to continually update features and algorithms over the equipment's lifetime. Together, flexible algorithm deployment and modality fusion compel the use of programmable system electronic components, such as high-powered CPUs and FPGAs.


Locate tumors and other pathologies

Measure tissue volumes

Computer-guided surgery


Treatment planning

Study of anatomical structure

Several factors should be considered in the efficient development of flexible medical imaging equipment:

Development of imaging algorithms requires high-level intuitive modeling tools for continual improvements in digital signal processing (DSP).

The performance needs for near real-time analysis require system platforms that scale with both software (CPUs) and hardware (configurable logic). These processing

platforms must meet various performance price points and be capable of bridging the fusion of multiple imaging modalities.

System architects and design engineers need to quickly partition and debug algorithms onto these platforms, using the latest tools and intellectual property (IP) libraries, to speed their deployment and improve profitability.


MRI reconstruction creates cross-sectional images of the human body. Two distinct steps are necessary to reconstruct a 3D volume:

1. 2D reconstruction of each slice via FFT produces slices in gray-level, typically matrices, from the frequency domain data.

3D volume reconstruction creates an interslice distance close to the inter pixel distance via interpolation of slices, so that images can be viewed from any 2D plane.

Figure 7: Input MRI image of the MATLAB (gray scale level)

Fig 8: Segmentation of MRI image at Centroiod value is 50

Fig 9: Segmentation of MRI image at Centroiod value is 100

Fig 10: Segmentation of MRI image at Centroiod value is 150


The speed of our FPGA solution for the image processing algorithms is approximately 15 times faster than the software implementation. FPGA technology can be more efficient than either technology alone. Applications are video conferencing, video-based interfaces for human-computer interaction, Satellite Imaging, Real-time Human Body Imaging, Face Recognition and so on. This suggests that future processors can achieve high efficiency by selectively applying reconfigurable and dedicated hardware to the tasks for which they are best suited. In addition, many components may be pipelined together. When doing this the Pixel Clock rate will relate to the number of stages of maths performed between one register stage in the pipeline and the next.


[1] J. A. Sethian. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, Cambridge, 2nd edition, Nov. 1998. ISBN 0-521-64204-3.

[2] Silicon Software. microEnable Users Guide, 1999.

[3] Xilinx. Programmable Logic Data Book, 1999.

[4] Steffen Klupsch, Markus Ernst, Sorin A. Huss, M. Rumpf, R. Strzodka, Real Time Image Processing based on Reconfigurable Hardware Acceleration,

[5] Herout A., Zem_ík P., Beran V., Kadlec J.: Image and Video Processing Software Framework for Fast Application Development, In: AMI/PASCAL/IM2/M4 workshop, Martigny, CH, 2004, p. 1

[6] Heather Quinn and Miriam Leeser, Laurie Smith King Implementing Image Processing Pipelines in a Hardware/Software Environment.

[7] Gonzalez, Woods, Eddins Digital Image Processing using MATLAB, Prentice Hall, (2004),

[8] S. Yu and J. Shi. Multiclass spectral clustering. In Proc. Int’l Conf. Computer Vision, 2003.