Time Limit: 1s
Memory Limit: 128MB
Scientist Y.D.I has created a robot, called Y.G.Tobor. It’s first version has only one ability, which is Looking The World.
Y.D.I has considered some situation while designing Tobor, and he give Tobor a gift, with which Tobor can filter image he saw. The method of filter is Histogram Equalization. This method usually increases the global contrast of many images, and it can be expressed as follow.
a. Consider a discrete grayscale image, every pixel has a gray level value, and let Ni be the number of occurrences of gray level i.
b. Let us also define the Cumulative Distribution Function of gray level v corresponding to Ni as
cdf(v) = Sum{ Ni }, where 0 <= i <=v.
c. We can transform an old gray level value to a new one with the following expression:
h(v)=Round((cdf(v)-cdf_{min})/(M*N-cdf_{min})*(L-1)).
where v is the old gray level value, and h(v) is the new one, L is 256 in this problem, and cdf_{min} is the minimum greater than zero value of {cdf}, cdf(v) has be calculated in part b. As an example, you can search “Histogram Equalization site:wikipedia.org” with google.com.
Now you are asked to solve the question:
Give you a gray-scale image with N rows and M columns, every element of this image is integer, you need to tell the filtered image.
Note: if the image has only one kind of color, then put what you get. See Sample.
Multiple case, you need process to the EOF. First line of each case is N and M, 0 < N,M <= 256.
There is M integers in every next N lines, which is split by single space, and the value is in the range of [0, 255].
Print case number in the first line, and N lines follow. Each line contains M integers, which indicates the new value of gray scale. No blank lines between cases. See Sample Output.
2 2 1 2 3 4 1 1 255
Case 1: 0 85 170 255 Case 2: 255
For more information, please download the problems in zip or pdf.
Any question please mail to dy0013@163.com.