A network device and method are directed towards detecting and blocking image spam within a message by employing a weighted min-hash to perform a near duplicate detection (NDD) of determined features within an image as compared to known spam images. The weighting for the min-hash is determined based on employing a machine learning algorithm, such as a perceptron, to identify an importance of each bit in a signature vector of the image. The signature vector is generated by extracting a shape of text in the image using a Discrete Cosine Transform, extracting low-frequency characteristics using a high-pass filter, and then performing various morphological operations to emphasize the shape of the text and reduce noise. Selected feature bits are extracted from the lowest frequency and intensity bits of the resulting signal to generate the signature vector used in the weighted min-hash NDD.