DIMACS TR: 2004-53

Optimal Mapping of Deep Gray Scale Images to a Coarser Scale of Gray

Authors: Solomon Borodkin, Aleksey Borodkin and Ilya Muchnik

The problem of optimal mapping of multi-level gray scale images to a coarser gray scale is formulated and explored. A distance between images having different intensity ranges is introduced. Minimization of such a distance can be viewed as least squares approximation of a source high range image by the best target image with a given number of levels of gray. Following S.Lloyd [1], we proved that the latter problem is equivalent to optimal partitioning of the source image intensity range into a given number of intervals, provided that the sum of intra-interval variations reaches minimum. An efficient algorithm for optimal partitioning based on dynamic programming is used, which is the same in complexity as the ones known from literature, but better in terms of required memory. The proposed approach is applied to visualization of deep gray scale medical images. Advantages of the method over linear mapping and histogram equalization are demonstrated on the sample images. The other application fields may include image optimization for printing/faxing/copying.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-53.pdf
DIMACS Home Page