A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Published

    View graph of relations

    As an unsupervised machine-learning algorithm, K-means clustering for images has been widely used in image segmentation. The standard Lloyd’s algorithm iteratively allocates all image pixels to clusters until convergence. The processing requirement can be a problem for high-resolution images and/or real-time systems. In this paper, we present a new histogram-based algorithm for K-means clustering, and its FPGA implementation. Once the histogram has been constructed, the algorithm is O(GL) for each iteration, where GL is the number of grey levels. On a Xilinx ZedBoard, our algorithm achieves 140 FPS (640 × 480 images, running at 150 MHz, 4 clusters, 25 iterations), including final image reconstruction. At 100 MHz, it achieves 95 FPS. It is 7.6 times faster than the standard Lloyd’s algorithm, but uses only approximately half of the resources, while giving the same results. The more iterations, the bigger the speed-up. For 50 iterations, our algorithm is 10.2 times faster than the Lloyd’s approach. Thus for all cases our algorithm achieves real time performance whereas Lloyd’s struggles to do so. The number of clusters (up to a user-defined limit) and the initialization method (one of three) can be selected at runtime.

    Documents

    DOI

    Original languageEnglish
    Title of host publicationIntelligent Computing and Internet of Things
    Subtitle of host publicationFirst International Conference on Intelligent Manufacturing and Internet of Things and 5th International Conference on Computing for Sustainable Energy and Environment, Chongqing, China, September 21-23, 2018
    EditorsZhile Yang, Dongsheng Yang, Kang Li, Minrui Fei, Dajun Du
    PublisherSpringer-Verlag
    Pages468-477
    Number of pages10
    Volume924
    ISBN (Print)9789811323836
    DOIs
    Publication statusPublished - 2018
    Event1st International Conference on Intelligent Manufacturing and Internet of Things, IMIOT 2018 and International Conference on Intelligent Computing for Sustainable Energy and Environment, ICSEE 2018 - Chogqing, China
    Duration: 21 Sep 201823 Sep 2018

    Publication series

    NameCommunications in Computer and Information Science
    Volume924
    ISSN (Print)1865-0929

    Conference

    Conference1st International Conference on Intelligent Manufacturing and Internet of Things, IMIOT 2018 and International Conference on Intelligent Computing for Sustainable Energy and Environment, ICSEE 2018
    CountryChina
    CityChogqing
    Period21/09/201823/09/2018

      Research areas

    • Data processing, FPGA acceleration, K-means clustering, Unsupervised machine learning

    ID: 154016802