In multiple object tracking, it is challenging to maintain the correct tracks of objects in the presence of occlusions. The paper proposes a new method to this problem, building on the patch representation of object appearance. We formulate multiple object tracking as classification tasks which competitively use the appearance models of the interacting objects. To obtain the optimal configuration of classification, a patches-based MAP-MRF decision framework is presented to make a global inference based on local spatial information existing between adjacent patches and the maximum a posteriori solution is evaluated exactly with graph cuts. As a result, accurate object identification is achieved. Extensive experiments on several difficult sequences validate that the proposed method is effective in dealing with multiple object occlusion, and comparative results show that our method outperforms the previous methods. (C) 2009 Elsevier B.V. All rights reserved.