Automatic accurate segmentation methods are needed to assess longitudinal cartilage changes in osteoarthritis (OA). We propose a novel general spatio-temporal three-label segmentation method to encourage segmentation consistency across time in longitudinal image data. The segmentation is formulated as a convex optimization problem which allows for the computation of globally optimal solutions. The longitudinal segmentation is applied within an automatic knee cartilage segmentation pipeline. Experimental results demonstrate that the longitudinal segmentation improves the segmentation consistency in comparison to the temporally-independent segmentation. © 2013 IEEE.