High-level computer vision tasks, such as object detection in single images, are of growing importance for our every day lives. Reliable systems for object detection, in particular, may simplify our lives significantly or make them safer (e.g.~in driver assistance scenarios). %This dissertation studies object detection in challenging scenes based on graphical models. Graphical models lend themselves to analyze and design computer vision algorithms because of their modularity that allows to design complex models built on simpler modules. This modularity and decomposability enables a better understanding of the domain of interest that in turn enables the design of models with increased reliability. In this dissertation we study discriminative, undirected graphical models, namely conditional random fields (CRFs), and propose extensions to standard CRFs in order to address object detection in challenging scenes. %The use of CRFs allows a fundamental understanding of the structure of the domain of interest that is crucial for reliably handling challenging scenes. %These challenging scenes require a fundamental understanding of the structure of the domain of interest. We discuss the advantages of discriminative models compared to generative variants in the presence of cluttered background, partial occlusion and viewpoint variation. While standard CRFs are restricted to fixed, local neighborhood dependencies we propose to learn arbitrary graph structures. Furthermore, we take advantage of the decomposability of graphical models and propose to interpret the random variables as object parts and develop a joint approach of part-based and monolithic object detection. This view on objects yields a better and intuitive understanding of the structure of objects, and in accordance with observations of related work we demonstrate an improved reliability of our joint system. A secondary focus of this work is the field of search and rescue robotics. Specifically, we are concerned with victim detection in search and rescue scenarios, which requires additional demands besides reliability. In this setting we require real-time capable models, hence, we need efficient algorithms without sacrificing performance. We propose to leverage the complementarity of different sensors (visual, thermal and laser in this work) within a sensor fusion scheme for an improved victim detection performance.