MS for Michael Estlick Title: An FPGA Implementation of the K-Means Algorithm for Image Processing Abstract: Satellite and airborne sensors can produce images of the earth with hundreds of channels of spectral data and millions of pixels. Interpreting these hyperspectral images can be difficult for analysts and processing them with a standard microprocessor is time consuming. One way to visualize a hyperspectral image is to group the pixels into a few clusters, where all of the pixels in one cluster are similar to each other and different from pixels in other clusters. An analyst can then view an image of the clusters, where each pixel is represented by the average spectrum of the cluster to which it belongs, instead of the whole hyperspectral image. Most image processing algorithms have a great deal of parallelism and involve processing large amounts of data. Most of this parallelism cannot be exploited on a sequential microprocessor. A Field Programmable Gate Array (FPGA) architecture for clustering multispectral images with the k-means clustering algorithm is presented. This implementation takes advantage of the parallelism in the algorithm. Two transformations to the k-means algorithm are presented that provide for a smaller and faster implementation on an FPGA. These are using Manhattan in place of Euclidean distance as a distance metric for clustering, and truncating input data. Studies are presented that highlight the advantages and disadvantages of these transformations. The resulting implementation is two orders of magnitude faster than the same algorithm run in software.