Optimal His togram Matching by Monotone Gray Level Transformation

This paper investigates the problem of optimal
his togram matching using monotone gray level 
transformation, which always assigns all picture points
of a given gray level i to another gray level 
T(i) such that if i > j, then T(i) > T(j).  The objective
is to find a transformed digital picture of 
a given picture such that the sum of absolute errors
between the gray level his togram of the transformed 
picture and that of a reference picture is minimized.
 This is equivalent to placing k1 linearly ordered 
objects of different sized one by one into k2 linearly ordered
boxes of assorted sizes, such that the 
accumulated error of space under packed or overpacked
in the boxes is minimized; the placement function 
is monotonic, which ensures a polynomial time solution
to this problem.  A tree search algorithm for 
optimal his togram matching is presented which has time
complexity O(k1 x k2).  If the monotone property 
is dropped, then the problem becomes NP-complete,
even if it is restricted to k2 = 2. 

CACM October, 1978

Chang, S.
Wong, Y.

Optimal his togram matching, gray level transformation,
packing problem, tree searching algorithm, 
picture processing

3.24 5.25 5.42

CA781004 DH January 29, 1979  6:08 PM

3057	5	3057
3057	5	3057
3057	5	3057