Abstract: Color-based particle filter for object tracking has been an active research topic in recent years. Despite great efforts of many researchers, there still remains to be solved the problem of contradiction between efficiency and robustness. The paper makes an attempt to partially solve this problem. Firstly, the Integral Histogram Image is introduced by which histogram of any rectangle region can be computed at negligible cost. However, straightforward application of the Integral Histogram Images causes the problem of "curse of dimensionality." In addition, traditional histogram is inefficient and inaccurate. Thus we propose to adaptively determine histogram bins based on K-Means clustering, which can represent color distribution of object more compactly and accurately with as a small number of bins. Thanks to the Integral Histogram Images and the clustering based color histogram, we finally achieve a fast and robust particle filter algorithm for object tracking. Experiments show that the performance of the algorithm is encouraging.