Threshold-based segmentation methods provide a simple and efficient way to implement lip segmentation. However, automatic computation of robust thresholds presents a major challenge. This research proposes an adaptive method for selecting the histogram threshold, based on feedback of shape information. The proposed method reduces unnecessary overhead by first comparing the initial segmentation to a reference lip shape model to decide if optimisation is required. In cases where optimisation is required, the algorithm adjusts the threshold until the segmentation is sufficiently similar to a reference shape model. The algorithm is tested on the AR Face Database by comparing the segmentation accuracy before and after optimisation. The proposed method increases the number of segmentations classified as ‘good’ (overlap above 90 %) by 7.1 % absolute, and significantly improves the segmentation in challenging cases containing facial hair.