Noise cleaning is the process of removing unwanted noise from an image. The problem with existing techniques is that they do not preserve two-dimensional image structure, and/or they require parameters to be supplied by the user. In this paper we describe an algorithm called MNC which explicitly segments the local neighbourhood of the pixel to be cleaned, and filters using only those pixels in the same segment. Additionally, the Minimum Message Length principle is used to decide on what is the best segmentation. We show MNC to be a good performer, with little structure loss and no special parameters.