Information hiding can be performed under the guise of a digital image. We consider the following scenario: Alice and Bob share an image and would like to use it as a cover image to communicate a message m. We are interested in answering two questions: What is the maximum amount of information that can be sent for a given level of degradation to an image? and How can this level of efficiency be achieved in practice? We require the recovered message to be the same as the embedded one. Our model begins with Alice compressing a message to obtain a binary sequence with uniform distribution. She then converts the binary sequence into a Q-ary sequence having a pre-defined distribution, and finally adding each symbol to a pixel. The distribution of the Q-ary sequence is chosen such that the amount of information is maximized for a given value of the signal to noise ratio. Bob recovers the sequence by subtracting the image data, and then converting the Q-ary string into the original binary string. We determine the optimal distribution analytically and provide a graphical representation of the variation of the amount of information with signal-to-noise ratio when Q varies.