Many computer vision tasks such as segmentation, stereo matching can be presented as a pixel labeling problem, which can be solved by optimizing a Markov Random Field modeling it. Most methods using this formulation treat every pixel as a node connected to its neighbors. Thus the compute requirements are directly proportional to the image size. For example a 720p image with 4-connectivity leads to 1 million nodes and 2 million edges. This is further scaled by the number of labels. With increasing resolution of cameras the traditional scheme does not scale well due to high compute and memory requirements, especially in mobile devices. Though methods have been proposed to overcome these problems, they still do not achieve high efficiency. In this paper we propose a framework for MRF optimization that significantly reduces the number of nodes through adaptive and intelligent grouping of pixels. This reduces the problem size in general and adapts to the image content. In addition we also propose a hierarchical grouping of labels, allowing for parallelization and thus suitable for modern processing units. We demonstrate this novel framework for the application of RGB-D scene segmentation and show up to 12X speed-up compared to the traditional optimization algorithms.