Early detection of malignant melanoma skin cancer is crucial for treating the disease and saving lives. Many computerized techniques have been reported in the literature to diagnose and classify the disease with satisfactory skin cancer detection performance. However, reducing the false detection rate is still challenging and preoccupying because false positives trigger the alarm and require intervention by an expert pathologist for further examination and screening. In this paper, an automatic skin cancer diagnosis system that combines different textural and color features is proposed. New textural and color features are used in a bag-of-features approach for efficient and accurate detection. We particularly claim that the Histogram of Gradients (HG) and the Histogram of Lines (HL) are more suitable for the analysis and classification of dermoscopic and standard skin images than the conventional Histogram of Oriented Gradient (HOG) and the Histogram of Oriented Lines (HOL), respectively. The HG and HL are bagged separately using a codebook for each and then combined with other bagged color vector angles and Zernike moments to exploit the color information. The overall system has been assessed through intensive experiments using different classifiers on a dermoscopic image dataset and another standard dataset. Experimental results have shown the superiority of the proposed system over state-of-the-art techniques.