Patient specific surface models of the jaw are beneficial forpre-operative planning and manufacturing of customized prosthesis. Suchmodels can be generated on the basis of dental cone-beam CT images, butthose suffer from a comparatively bad image quality with regard to thesignal-to-noise ratio. Therefore, in this work, a statistical shapemodel (SSM) is used for robust segmentation of the mandible bone. Whileprevious works with that application require manual interaction duringSSM construction, we establish correspondence fully automatic byminimizing the description length of the model. Subsequently, themandible bone is automatically localized and segmented using the SSM asshape constraint. The standard SSM constraint is known to be inherentlylimited insofar as patient specific anatomical details can often not berepresented. To overcome this limitation, a new, mathematically sound,computationally fast, and intuitively interpretable, relaxed SSMconstraint is derived, which can be applied without any user-providedparameter. Evaluation on clinical cone beam CT images yields animprovement of the Jaccard coefficient up to 45% compared to thestandard SSM constraint. Our results are similar to that of alternativemethods in the literature, indicating the general potential of theproposed relaxed SSM constraint for medical image segmentation.