A structure-preserving composite model for skin lesion segmentation includes partitioning a dermoscopic image into superpixels at a first scale. Each superpixel is a vertex on a graph defined by color coordinates and spatial coordinates, and represents a number of pixels of the dermoscopic image according to the first scale. Further, constructing a plurality of k background templates by k-means clustering selected ones of the superpixels in space and color. Additionally, generating sparse representations of the plurality of superpixels based on the plurality of background templates. Also, calculating a reconstruction error for each superpixel by comparison of its sparse representation to its original color coordinates and spatial coordinates. Furthermore, outputting a confidence map that identifies each pixel of the dermoscopic image as belonging or not belonging to a skin lesion, based on the reconstruction errors of the representative superpixels.