Algorithmic transformations in the implementation of K- means clustering on reconfigurable hardware

ABSTRACT

In mapping the k-means algorithm to FPGA hardware, we examined algorithm level transforms that dramatically increased the achievable parallelism. We apply the k-means algorithm to multi-spectral and hyper-spectral images, which have tens to hundreds of channels per pixel of data. K-means is an iterative algorithm that assigns assigns to each pixel a label indicating which of K clusters the pixel belongs to.K-means is a common solution to the segmentation of multi-dimensional data. The standard software implementation of k-means uses floating-point arithmetic and Euclidean distances. Floating point arithmetic and the multiplication-heavy Euclidean distance calculation are fine on a general purpose processor, but they have large area and speed penalties when implemented on an FPGA. In order to get the best performance of k-means on an FPGA, the algorithm needs to be transformed to eliminate these operations. We examined the effects of using two other distance measures, Manhattan and Max, that do not require multipliers. We also examined the effects of using fixed precision and truncated bit widths in the algorithm.It is important to explore algorithmic level transforms and tradeoffs when mapping an algorithm to reconfigurable hardware. A direct translation of the standard software implementation of k-means would result in a very inefficient use of FPGA hardware resources. Analysis of the algorithm and data is necessary for a more efficient implementation. Our resulting implementation exhibits approximately a 200 times speed up over a software implementation.

REFERENCES

• 1: P. Banerjee , N. Shenoy , A. Choudhary , S. Hauck , C. Bachmann , M. Haldar , P. Joisha , A. Jones , A. Kanhare , A. Nayak , S. Periyacheri , M. Walkden , D. Zaretsky, A MATLAB Compiler for Distributed, Heterogeneous, Reconfigurable Computing Systems, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.39, April 17-19, 2000
• 2: Vittorio Castelli , Thomas M. Cover, On the exponential value of labeled samples, Pattern Recognition Letters, v.16 n.1, p.105-111, Jan. 1995 [doi>10.1016/0167-8655(94)00074-D]
• 3: B. Draper , W. Najjar , W. Bohm , J. Hammes , B. Rinker , C. Ross , M. Chawathe , J. Bins, Compiling and Optimizing Image Processing Algorithms for FPGAs, Proceedings of the Fifth IEEE International Workshop on Computer Architectures for Machine Perception (CAMP'00), p.222, September 11-13, 2000
• 4: C. Funk, J. Theiler, D. A. Roberts, and C. C. Borel. Clustering to improve matched-filter detection of weak gas plumes in hyperspectral imagery. Technical Report LA-UR 00-3673, Los Alamos National Laboratory, 2000.
• 5: Maya B. Gokhale , Janice M. Stone , Jeff Arnold , Mirek Kalinowski, Stream-Oriented FPGA Computing in the Streams-C High Level Language, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.49, April 17-19, 2000
• 6: P.-F. Hsieh and D. Landgrebe. Statistics enhancement in hyperspectral data analysis using spectral-spatial labeling, the EM algorithm, and the leave-one-out covariance estimator. Proc. SPIE, 3438:183-190, 1999.
• 7: P. M. Kelly and J. M. White. Preprocessing remotely-sensed data for effcient analysis and classification. In U. M. Fayyad and R. Uthurusamy, editors, Artificial Intelligence 1993:Knowledge-Based Systems in Aerospace and Industry, volume 1963, pages 24-30, 1993.
• 8: NASA, 1999. http://makalu.jpl.nasa.gov/avaris.html.
• 9: R. A. Schowengerdt. Techniques for Image Processing and Classification in Remote Sensing. Academic Press, Orlando, 1983.
• 10: J. Theiler, M. Leeser, M. Estlick, and J. J. Szymanski. Design issues for hardware implementation of an algorithm for segmenting hyperspectral imagery. In M. R. Descour and S. S. Shen, editors, Imaging Spectrometry VI, volume 4132, 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Experimentation