Asymmetry is one of key characteristics for early diagnosis of melanoma according to medical algorithms such as (ABCD, CASH etc.). Besides shape information, cues such as irregular distribution of colors and structures within the lesion area are assessed by dermatologists to determine lesion asymmetry. Motivated by the clinical practices, we have used Kullback-Leibler divergence of color histogram and Structural Similarity metric as a measures of these irregularities. We have presented performance of several classifiers using these features on publicly available PH2 dataset. The obtained result shows better asymmetry classification than available literature. Besides being a new benchmark, the proposed technique can be used for early diagnosis of melanoma by both clinical experts and other automated diagnosis systems.