Abstract Recently, MRFs with two-dimensional (2D) labels have proved useful to many applications, such as image matching and optical flow estimation. Due to the huge 2D label set in these problems, existing optimization algorithms tend to be slow for the inference of 2D label MRFs, and this greatly limits the practical use of 2D label MRFs. To solve the problem, this paper presents an efficient algorithm, named FastLCD. Unlike previous popular movemaking algorithms (e.g., ?-expansion) that visit all the labels exhaustively in each step, FastLCD optimizes the 2D label MRFs by performing label coordinate descents alternately in horizontal, vertical and diagonal directions, and by this way, it does not need to visit all the labels exhaustively. FastLCD greatly reduces the search space of the label set and benefits from a lower time complexity. Experimental results show that FastLCD is much faster, while it still yields high quality results.