The automatic extraction and labeling of the rib centerlines is a useful yet challenging task in many clinical applications. In this paper, we propose a new approach integrating rib seed point detection and template matching to detect and identify each rib in chest CT scans. The bottom-up learning based detection exploits local image cues and top-down deformable template matching imposes global shape constraints. To adapt to the shape deformation of different rib cages whereas maintain high computational efficiency, we employ a Markov Random Field (MRF) based articulated rigid transformation method followed by Active Contour Model (ACM) deformation. Compared with traditional methods that each rib is individually detected, traced and labeled, the new approach is not only much more robust due to prior shape constraints of the whole rib cage, but removes tedious post-processing such as rib pairing and ordering steps because each rib is automatically labeled during the template matching. For experimental validation, we create an annotated database of 112 challenging volumes with ribs of various sizes, shapes, and pathologies such as metastases and fractures. The proposed approach shows orders of magnitude higher detection and labeling accuracy than state-of-the-art solutions and runs about 40 seconds for a complete rib cage on the average.