Access Restriction

Author Chang, Shi-Kuo ♦ Wong, Yin-Wah
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Gray level transformation ♦ Picture processing ♦ Optimal histogram matching ♦ Packing problem ♦ Tree searching algorithm
Abstract This paper investigates the problem of optimal histogram 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 histogram of the transformed picture and that of a reference picture is minimized. This is equivalent to placing k1 linearly ordered objects of different sizes one by one into k2 linearly ordered boxes of assorted sizes, such that the accumulated error of space underpacked 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 histogram matching is presented which has time complexity O(k1 × k2). If the monotone property is dropped, then the problem becomes NP-complete, even if it is restricted to k2 = 2.
Description Affiliation: Univ. of Illinois at Chicago Circle, Chicago (Chang, Shi-Kuo; Wong, Yin-Wah)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 10
Page Count 6
Starting Page 835
Ending Page 840

Open content in new tab

   Open content in new tab
Source: ACM Digital Library