A method detects noise in a document image. The image includes pixels representing at least text and image data forming the document. The noise includes at least one of halftone, bleeding and texture noise. The method partitions the image into tiles, formed of pixels, determines a set of dominant colors for each tile, associates each pixel with one of the determined dominant colors, and then determines for each dominant color a fragmentation statistic, and applies a threshold to each statistic to detect the noise in the corresponding dominant color in the tile. Detected noise in the image is reduced by (a) merging colors with noise to one color without noise if the noise is halftone noise or texture noise; and (b) removing the colors with noise if the noise is bleeding noise. The pixels of the tile are then quantized to those remaining dominant colors of the set.