Efficient Hardware Architecture Design of K-Means Clustering Algorithm for AV1 Palette Mode Coding

doi:10.1109/TCSII.2025.3580435

	Efficient Hardware Architecture Design of K-Means Clustering Algorithm for AV1 Palette Mode Coding
	Huang, Xiaofeng 1; Lin, Jiaqing 1; Liu, Fengguang 2; Ji, Wen 3; Yin, Haibing 1; Ma, Siwei 4
	2025-08-01
发表期刊	IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS
ISSN	1549-7747
卷号	72 期号:8 页码:1078-1082
摘要	The palette mode is a specialized coding tool for coding screen content video in Alliance for Open Media Video 1 (AV1), and K-means clustering is a necessary step in the palette mode. However, the high computational complexity and the strong data dependency in K-means clustering impede real-time processing. To address these issues, we propose an efficient hardware architecture design for the K-means clustering algorithm. Firstly, we propose a fully pipelined hardware architecture with two data-interleaving optimization methods, including K-interleaving and block-interleaving. Then, we propose a novel method for reusing original pixel data, which is motivated by the fact that the input original pixels are the same for different coding blocks. Finally, we propose a parallelized architecture that features three "K-means Engine" modules, with reusing of the "Euclidean distance calculate" module to minimize area. Experimental results show that the proposed hardware architecture can process all K-means clustering for pixels in a superblock in 10246 cycles under 650MHz working frequency, which can achieve 4K@30fps real-time processing. To the best of our knowledge, our work is the first attempt to design a K-means clustering hardware accelerator for palette mode in AV1.
关键词	Random access memory Hardware Engines Indexes Encoding Bandwidth Clustering algorithms Heuristic algorithms Throughput Memory management K-means clustering Palette mode Alliance for Open Media Video 1 (AV1) data reuse hardware architecture
DOI	10.1109/TCSII.2025.3580435
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2023YFB4502803] ; The Leading Goose Program of Zhejiang Province[2024C01107] ; The Leading Goose Program of Zhejiang Province[2025C01036] ; Zhejiang Key Laboratory of Film and TV Media Technology[CM2025002]
WOS研究方向	Engineering
WOS类目	Engineering, Electrical & Electronic
WOS记录号	WOS:001545622700020
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/42011
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Fengguang; Yin, Haibing
作者单位	1.Hangzhou Dianzi Univ, Sch Commun Engn, Hangzhou 310018, Peoples R China 2.Zhejiang Sci Technol Project Management & Serv Ctr, Platform Dev Dept, Hangzhou 316000, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 4.Peking Univ, Sch Comp Sci, Beijing 100871, Peoples R China
推荐引用方式 GB/T 7714	Huang, Xiaofeng,Lin, Jiaqing,Liu, Fengguang,et al. Efficient Hardware Architecture Design of K-Means Clustering Algorithm for AV1 Palette Mode Coding[J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS,2025,72(8):1078-1082.
APA	Huang, Xiaofeng,Lin, Jiaqing,Liu, Fengguang,Ji, Wen,Yin, Haibing,&Ma, Siwei.(2025).Efficient Hardware Architecture Design of K-Means Clustering Algorithm for AV1 Palette Mode Coding.IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS,72(8),1078-1082.
MLA	Huang, Xiaofeng,et al."Efficient Hardware Architecture Design of K-Means Clustering Algorithm for AV1 Palette Mode Coding".IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 72.8(2025):1078-1082.