Disclosed is a method (500) of encoding a message (501) into a target area of an original image by determining a set of data items into which the message can be partitioned, partitioning the message into the data items, encoding (580) a first mark into the target area at a location determined by applying (550) a hash function (505) to a first data item, and encoding (580) a second mark into the target area at a location dependent upon (a) a hash value determined by applying (550) the hash function (505) to the first data item and a second data item, (b) the location of the encoded first mark, and (c) a predetermined constraint (504), wherein the first and second marks form at least part of a pattern of marks in the target area of the encoded image, the pattern having a visual characteristic defined by the predetermined constraint.