JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 41
Problem: Steganography

Problem Statement

    

Steganography is the process of transmitting a message by hiding it in such a way that it is not apparent there is a secret message. By comparison, typical encryption methods obscure a message in such a way that it can not be interpreted by others, but it is clear that a message is being transmitted. With a steganographic process, an uninitiated observer would have no cause for suspicion.

One of the most common forms of steganography is to send bitmapped images, where the lowest order bits of some of the pixels actually contain a secret message of some kind. Since only the lower few bits of any given pixel are altered from the original image, the image containing a secret message looks virtually identical to the casual observer.

You will be given an image. The image is given in int[] pixels. You are also given ints width and height. A pixel (x, y) of the image is given in element y * width + x of pixels. Each value is the RGB encoding of the three channels, pixel = red * 65536 + green * 256 + blue. Encoded within that image will be a second image, which is the secret message you are attempting to discover.

To generate test cases, two images from a set of 500 will be chosen at random. One will be the carrier image, and will be used at it's original size. The second will have a portion used as the hidden image. A size for the hidden image is chosen, with a minimum size of 50x50 and a maximum size of 200x200 (not necessarily square). Then, a section of the chosen size is extracted from the second image, to be used as the hidden image. Then, hiddenWidth distinct columns of the carrier image are chosen at random as xx[], as are hiddenHeight distinct rows, as yy[]. xx[] and yy[] are then sorted. Finally, the number of bits to use for the hidden image, k, is chosen between 2 and 4. The hidden image is then reduced to only use that many bits for each R, G, B channel. This is done by taking each R/G/B value for each pixel, and bit shifting it to the right by 8-k. Finally, the RGB values of each pixel (x, y) of the hidden image replace the k lowest order bits of each RGB channel of pixel(xx[x], yy[y]) in the carrier image.

Your solution should return a String[], where each element is a space-delimited list of integers, and each integer represents a pixel. Since you are returning the representation of a rectangular image, each element of the return should contain the same number of integers. Each integer should be encoded in the RGB format as described previously in the problem.

Your score is calculated by determining how many pixels of your returned image exactly match the pixels of the actual hidden image. Since the return may have more or less rows or columns than the actual image, your returned image will be compared against the actual image, adjusted by each possible offset in the x and y directions, taking the best value. Then, letting best = #pixels matched, your score is calculated as best^2 / yourArea / actualArea. Your final score will be the sum of your score from each individual test case.

 

Definition

    
Class:Steganography
Method:findImage
Parameters:int[], int, int
Returns:String[]
Method signature:String[] findImage(int[] pixels, int width, int height)
(be sure your method is public)
    
 

Notes

-Test cases are chosen using http://commons.wikimedia.org/wiki/Special:Random/Image . Images which are not primarily photographic or photo-realistic, such as line drawings, are discarded.
-Neither image dimension will be more than 500 pixels - larger images will be scaled so that the larger dimension becomes 500.
 

Constraints

-The time limit is 10 seconds, and the memory limit is 1GB.
-There are 50 non-example test cases.
 

Examples

0)
    
Carrier Image: http://www.topcoder.com/contest/problem/Steganography/original0.png Hidden Image: http://www.topcoder.com/contest/problem/Steganography/hidden0.png With Hidden Image: http://www.topcoder.com/contest/problem/Steganography/steg0.png Bits Used: 2
1)
    
Carrier Image: http://www.topcoder.com/contest/problem/Steganography/original1.png Hidden Image: http://www.topcoder.com/contest/problem/Steganography/hidden1.png With Hidden Image: http://www.topcoder.com/contest/problem/Steganography/steg1.png Bits Used: 2
2)
    
Carrier Image: http://www.topcoder.com/contest/problem/Steganography/original2.png Hidden Image: http://www.topcoder.com/contest/problem/Steganography/hidden2.png With Hidden Image: http://www.topcoder.com/contest/problem/Steganography/steg2.png Bits Used: 4
3)
    
Carrier Image: http://www.topcoder.com/contest/problem/Steganography/original3.png Hidden Image: http://www.topcoder.com/contest/problem/Steganography/hidden3.png With Hidden Image: http://www.topcoder.com/contest/problem/Steganography/steg3.png Bits Used: 3
4)
    
Carrier Image: http://www.topcoder.com/contest/problem/Steganography/original4.png Hidden Image: http://www.topcoder.com/contest/problem/Steganography/hidden4.png With Hidden Image: http://www.topcoder.com/contest/problem/Steganography/steg4.png Bits Used: 2
5)
    
6)
    
7)
    
8)
    
9)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.