The irregularity of a lesion border has been identified as the most significant factor in the diagnosis of malignant melanoma. The objective of the research was to find objective computable measures of contour irregularity and to apply them to skin lesions. A descriptive definition of irregularity was formulated which defines irregularity in terms of the five attributes: departure from a typical sequence (deviation), lack of obvious description, lack of compressibility, lack of symmetry and lack of a rule for generating a sequence. Methods based on the Hidden Markov Models, the Conditional Entropy, and a novel method based on Pattern Theory, were implemented, evaluated and tested. Their predictive power as classifiers of lesion abnormality was tested on 98 lesions. All methods showed sensitivity and specificity of over 0.7, with 0.82 scored for the Weibull based Hidden Markov Models. Ranking correlation between the computed measures and the human perception of the border irregularity varied from W=0.49 for the Hidden Markov Models based measure to W=0.95 for the measure based on Pattern Theory.