Natalya Kitaryeva

K-Means Clustering for Color Image Processing on a Reconfigurable Hardware Board

Thursday, May 17, 2001

Image processing algorithms are natural candidates for high performance computing due to their inherent parallelism and intense computational demands. For example, a single 3 x 3 convolution on a 512 x 512 gray scale image at 30 frames per second may require up to 67 million multiplications and 60 million additions to be performed in one second. Image processing tasks can be classified into three categories based on their computational complexity and communication complexity: low-level, intermediate-level, and high-level. In this thesis we examine mapping a clustering algorithm to a Field Programmable Gate Array (FPGA). Special-purpose hardware provides better performance compared to general-purpose hardware for all three levels of image processing tasks. With recent advantages in very large scale integration (VLSI) technology, an application specific integrated circuit (ASIC) can provide the best performance in terms of total execution time. However, long design times, high development costs and inflexibility of dedicated hardware deter the design of ASICs. In contrast, FPGAs support shorter design times and easier design adaptability at lower cost. FPGA-based custom computing machines are playing a major role in realizing high performance application accelerators. In this thesis the k-means clustering algorithm is investigated for mapping onto a custom computing machine. K-means clustering is considered to be an intermediate-level image processing algorithm. The performance of the k-means clustering algorithm is shown on an Annapolis Microsystems WildForce FPGA-based custom computing machine. The advantages demonstrated by this implementation are as follows. First, custom computing machines are suitable for intermediate-level image processing algorithms. Second, a custom computing approach permits image processing applications to run at high speed.

Committee: Prof. David Kaeli Prof. Miriam Leeser (advisor) Prof. Waleed Meleis