A method and apparatus of tile-based belief propagation are disclosed. An image is split into a number of tiles. Messages are iteratively generated within each of the tiles based on the messages from neighboring pixels to the tile at a previous iteration, wherein each message represents information of a state of the pixel. The generated messages for sending out of the tiles are stored. Labels are then determined based on the stored messages, wherein each label represents the state of the pixel.