A common practice when displaying a document that contains sensitive information is to post-process it to make the sensitive parts not readable, for example by blurring or pixelizing them.
However, in many situations this practice is not sufficient. An attacker might be able to restore the scrambled part of the text, at least partially. That will be your job in this problem.
Problem specification
You are given two image files as input. The easy input is a clear image with black letters and white background, the hard input contains various kinds of noise as well. In both cases, the image has been post-processed to hide a part of the information it contains. Recover it, and submit an appropriate proof.
Blurring algorithm used
The blurred part of the image was produced using the following algorithm:
Pick a positive integer σ. We define
Compute the values Gr,c for -3σ ≤ r,c ≤ 3σ. Let S = ∑ -3σ≤r,c≤3σGr,c. Set Hr,c = Gr,c∕S.
For example, for σ = 1 you should get the following values: S = 6.279785, and the values Hr,c look as follows (with H0,0 in the middle):
0.000020 0.000239 0.001073 0.001769 0.001073 0.000239 0.000020
0.000239 0.002917 0.013071 0.021551 0.013071 0.002917 0.000239 0.001073 0.013071 0.058582 0.096585 0.058582 0.013071 0.001073 0.001769 0.021551 0.096585 0.159241 0.096585 0.021551 0.001769 0.001073 0.013071 0.058582 0.096585 0.058582 0.013071 0.001073 0.000239 0.002917 0.013071 0.021551 0.013071 0.002917 0.000239 0.000020 0.000239 0.001073 0.001769 0.001073 0.000239 0.000020 |
To blur a greyscale image, first represent each pixel [pr,pc] as an integer Ipr,pc between 0 and 255, inclusive. Here, 0 is black, and 255 white. Pixels outside of the image are considered to be white. The color Bpr,pc of a pixel [pr,pc] after blurring can be computed as follows:
In words, the new color is a weighted average of the colors of the nearby pixels, and the weights used are the values Hr,c defined above. The exact color Bpr,pc is then rounded to the nearest integer from the set {0,…,255}.
For a true color image, blurring is done separately for its red, green, and blue color component.
For the easy data set we used the value σ = 15, for the hard data set σ = 17.
Input specification
The input is a Portable Network Graphics (PNG) file.
(See http://en.wikipedia.org/wiki/Portable_Network_Graphics if you are not familiar with this image format. All modern browsers and all modern image manipulation programs should be able to open PNG files.)
Output specification
For each input file, submit an output file that contains a single English word in ALL UPPERCASE. If you submit the correct output but not in ALL UPPERCASE, it will be considered incorrect.
The word you are supposed to output is uniquely specified by the hidden part of the input file. For the hard data set, the word has between 6 and 9 letters, and starts with the letter P.
Example
Input image
|
Original image without the distortion
|
Output file
|
