This paper presents a method for localizing and labeling the lumbar vertebrae and intervertebral discs in mid-sagittal MR image slices. The approach is based on a Markov-chain-like graphical model of the ordered discs and vertebrae in the lumbar spine. The graphical model is formulated by combining local image features and semiglobal geometrical information. The local image features are extracted from the image by employing pyramidal histogram of oriented gradients (PHOG) and a novel descriptor that we call image projection descriptor (IPD). These features are trained with support vector machines (SVM) and each pixel in the target image is locally assigned a score. These local scores are combined with the semiglobal geometrical information like the distance ratio and angle between the neighboring structures under the Markov random field (MRF) framework. An exact localization of discs and vertebrae is inferred from the MRF by finding a maximum a posteriori solution efficiently using dynamic programming. As a result of the novel features introduced, our system can scale-invariantly localize discs and vertebra at the same time even in the existence of missing structures. The proposed system is tested and validated on a clinical lumbar spine MR image dataset containing 80 subjects of which 64 have disc-and vertebra-related diseases and abnormalities. The experiments show that our system is successful even in abnormal cases and our results are comparable to the state of the art.