Gingival health state assessment has always been considered of great importance in the field of dentistry. A major concern in this area is the subjectivity that commonly applied assessment methods inherit. Most of the previous approaches that aim at introducing objectivity in the assessment are based on data from photographic images of the gingival area. Nevertheless, they generally lack applicability in the clinical environment because of the requirement of expertise in image processing to perform the analysis. In this work, an enhanced teeth region segmentation scheme is proposed, based on the Self-Organizing Map algorithm. The segmentation task is the basis for further objective assessment of gingival health that can entirely be performed automatically. By introducing a novel training image selection approach, the segmentation performance of this task was increased significantly, compared to previous work. Apart from that, a newly developed spatial segmentation feature in addition to color is investigated and evaluated. The novel Labial Teeth and Gingiva Image Database of the University of Granada is used as benchmark for the segmentation scheme.