Digital colposcopy is an emerging technology, replacing the traditional colposcope for diagnosis of cervical lesions. Incorporating automated algorithms within a digital colposcopy system can improve the reliability and the diagnostic accuracy of cervical precancer and cancer. An automated computer-aided diagnosis (CAD) system can assess the three important cervical diagnostic cues: the color, the vascular patterns and the lesion margins with quantitative measures, similar to the way colposcopists use the Reid's index in traditional colposcopy. In this work we present a novel way to analyze and classify the global and the local features of one of the three major components in colposcopy diagnosis - the lesion margins. The margins of cervical lesion can be described as 'feathered,' 'geographic,' 'satellite,' 'regular or smooth' and 'margin-in-margin,' or they can be of mixed type. As margin characterization is a complex task, we use irregularity descriptors such as compactness indices and curvature descriptors. To address the complexity of the problem, the dependency of scale and the position of the lesion on the cervical image, our method use novel Fourier energy descriptors. The conceptually complex analysis of describing lesions as 'satellite' lesions or lesions with multiple margins is performed using descriptors, where the distance, the position and the local statistical estimates of image intensity play important role. We trained this new algorithm to classify and diagnose the cervix, evaluating only the lesions. The accuracy of the results is assessed against a 'ground truth' scheme, using colposcopists' annotations and pathology results. We report the resulted accuracy of the classification method assessed against this scheme.