Methods and apparatus for localized labeling in digital images. A region is obtained within which a global labeling solution for an image lies. The region is covered with a set of multiple overlapping tiles. A labeling function is applied to each tile in two or more subsets of the tiles to generate a local labeling for each of the tiles in the subsets. The local labeling for tiles in a first subset are input as a boundary condition to the labeling function when applied to overlapping tiles in a second subset. The local labelings for all of the tiles in all of the subsets are merged to form a global labeling for the image. The labeling function may be executed in parallel on two or more of the tiles.