Embedding large amounts of secret data into a cover image with low distortion is an important research issue in steganography. The proposed scheme uses two clustering technologies - similar and dissimilar clustering - to enhance hiding capacity as provided by Du and Hsu's scheme. In general, the hiding capacity of our proposed scheme is higher than that of Du and Hsu's scheme, about 16 Kb for the same image quality. In addition, the image quality of our proposed scheme is more than provided by the schemes of either Du and Hsu's or Shie et al., about 2 dB. Moreover, the distortion for each test image in our proposed scheme is always less than those caused by Du and Hsu's and Shie et al.'s schemes. Experimental results confirm that the proposed scheme is significantly better than earlier works.