We propose a novel fully automatic three-label bone segmentation approach applied to knee segmentation (femur and tibia) from T1 and T2* magnetic resonance (MR) images. The three-label segmentation approach guarantees separate segmentations of femur and tibia which cannot be assured by general binary segmentation methods. The proposed approach is based on a convex optimization problem by embedding label assignment into higher dimensions. Appearance information is used in the segmentation to favor the segmentation of the cortical bone. We validate the proposed three-label segmentation method on nine knee MR images against manual segmentations for femur and tibia.