Abstract: Jointly solving the object detection and semantic segmentation under a unified energy minimization framework is a promising way towards a holistic scene understanding, in which how to design powerful expressive higher order potentials and how to construct the corresponding efficient inference algorithms are two key issues. In this work, we at first introduce three design criteria for suitable higher order potential to appropriately model label consistency between object detection and semantic segmentation, then based on these three criteria, a robust higher order potential and its corresponding efficient inference algorithm are proposed. Our proposed higher order potential separately models the label consistency of the pixels within the bounding boxes for true, false and inaccurate detectors, and can be represented as the lower envelope of three linear functions. By introducing only two auxiliary binary variables, it is proved the higher order α-expansion move function can be transformed to submodular pairwise energy, which in turn can be efficiently minimized via graph cuts. The comparative experiments on PASCAL VOC 2010 dataset with the state-of-the-art algorithms showed that our proposed robust higher order potential could effectively model the label consistency of object detection and semantic segmentation for both accepted and rejected detectors, while keeping robust to the false detectors resulting from inaccurate localization.