Method and apparatus for coding information

[0002] The present invention relates to a method and apparatus for the insertion, and subsequent decoding, of coded information into images.

[0003] It is known to insert codes into images for example video transmissions or video clips or stills transmitted across a telecommunication link, for the purpose of identifying the owner of the images. There are a number of known schemes for inserting identification codes into the sync periods, and more recently it has been proposed to insert identification codes into the image itself, but in such a manner that the code cannot be detected by the eye.

[0004] WO 95/14289 discloses the embedding of an identification code throughout an image by modulating a digitised version of the image with a small noise signal. The specific system described suffers from the disadvantage of requiring to have to hand the original image for code identification. Further improvements in code robustness for transmission over telecommunications links or broadcasting are also desirable.

[0005] WO 95/20291 discloses a method of hiding copyright related messages with a digital. data work, which relies on commonly occurring patterns or sequences of data in the work acting as signposts to target data elements which are modified according to certain rules. The disclosed method suffers from a lack of robustness to signal degradation.

[0006] The above references suffer from a disadvantage that they are concerned wholly or principally with the digital domain, and the disclosed techniques are not suited to the analog domain, in particular where digital to analog conversion and analog to digital conversion may easily lose or degrade individual pixel values.

[0007] In our copending application PCT/GB96/00246 (the national phase entry of which is U.S. application Ser. No. 08/875,546, filed Jul. 31, 1997), there is disclosed and claimed a method for inserting coded information into an image, comprising analysing the image, identifying strongly featured regions and inserting coded information into these regions. Because the method relies on an analysis of the entire image and code being inserted in strongly featured regions, rather than in individual pixels, as in the prior art, the code is better able to survive analog to digital conversions and digital to analog conversions, where there will inevitably be pixel misalignments between the original and processed images, and hence the pixel values will be apparently altered.

[0008] By “strongly featured regions” is meant regions of primary strength to which the eye responds in viewing an image, for example, textured regions or lines or boundaries between two regions of different luminance. In such regions, it is possible to insert a relatively large amount of information without significantly altering the image in its appearance to the eye. Edge regions between areas of different luminance are preferred since these are very distinctive and will permit code insertion without visibly degrading the image, and the coded information is inserted into such strongly featured regions by altering the structure of the image in such region in a predictable or identifiable manner. The image is altered by applying an insert function to an area including the strongly featured region, which insert function gradually decreases in intensity from the centre of its region of application, so as to blend with the surrounding region.

[0009] A main advantage of applying the coded information by altering the image in a predictable or identifiable manner, is that the information can be recovered in a decoding process at a remote location without having the original to hand.

[0010] As disclosed in PCT GB96/00246 the image, for example, a video frame or field, is divided up into a number M×N of blocks in M rows and N columns, each block comprising nxn pixel elements (e.g. 8×8). Strongly featured regions are searched in each block for insertion of code. In order to encode a significant amount of information into an image, it is necessary to apply the insertion function to a number of edges in the image. If for example, one edge is chosen in each block into which the image is divided, then in order to increase confidence when attempting to recognise the code, the edges in one row may be encoded according to two separate pseudo-random codes, representing a “1” or “0”.

[0011] Prior to inserting the information, the image is assessed as to whether the image is suitable for code insertion, for example, the degree of consistency of the edge, the definition of the edge centre to prevent insertions when the image is determined to be unsuitable. Problems have arisen in the method described in PCT/GB96/00246 where more than one distinct edge is present in the image, or the part of the image under consideration for code insertion; for example there may be a corner feature.

[0012] An object of the present invention is to provide a method of embedding coded information into images by adding into the image a function which is dependant on the edge activity in the image.

[0013] The present invention accordingly provides in one aspect a method for inserting coded information into an image, comprising the steps of analysing the image, identifying edge regions calculating the strength of the detected edge and producing an edge function dependent on the strength of the edge, and adding the edge function to the image in order to represent coded information.

[0014] In accordance with the present invention, an image (or block within an image) may be selected to be encoded using an edge detection based scheme, the selection being dependant on the edge activity in the block. This allows for encoding of blocks with multiple features such as blocks containing a corner or block containing two edges. In these blocks, an edge detection scheme is applied to the block to produce a function within the block which has a value at each pixel, which is related to the strength of the edge at that pixel. This edge function is suitably scaled, and optionally multiplied by a circular function centred on the centre of the block. The scaled edge function is then added to the image on a pixel by pixel basis, with the sign of the function, plus or minus, representing a “1” or “0” bit of information. In a decoding operation, edges are detected and an estimate is made of the appropriate edge function. This estimate is then correlated with the image in order to reveal the existence of coded information.

[0015] In another aspect, the invention provides a method of decoding information contained in an image, the method comprising analysing the image, identifying edge regions and providing an estimate of the edge function dependent on the strength of the edge, and correlating the estimated edge function with the image in order to identify coded information present within the image.

[0016] As preferred, the image may be divided into M×N blocks, and an encoding/decoding operation is carried out on each block. Further, in accordance with the invention, an assessment is made of the type of features present in the image or image block, and a coding function is added to the image, the type of function depending on the type of image, as more fully described in our Application PCT/GB96/00246. Thus if only a single main edge is present, then an elliptical function may be added centred on the edge, if no distinct feature is present, then a circular function may be added, and if more than one distinct edge is present, then the edge function of the present invention may be added.

[0017] Another aspect of the present invention concerns synchronising the decoding process. An encoded image may be presented to the decoder in a geometrically altered state from which it was encoded. The geometric transformation may be for example an offset (x,y) translation, or a scaling in one or both axes (including different scaling in each axis), or a rotation. If the geometric transformation is of a significant size, then in order to decode it, this geometric distortion must be accounted for. The decoder synchronising process achieves this by an analysis process involving splitting the image into blocks, analysing the blocks for the type of insert and decoding the block accordingly. The process produces a measure of coded insets and their centres and the regularity of their structure. The offsets, scaling and rotations are then calculated from the geometric variations of the centres and structure. This is then used to correct the image before the final decoding.

[0018] A preferred embodiment of the invention will now be described with reference to the accompanying drawing wherein:

[0019] FIGS. 1 to 3 are diagrams for explaining the preferred method of the present invention.

[0020] FIG. 4 is a flowchart illustrating the operation of the invention.

[0021] The encoding and decoding algorithms of the preferred embodiment are listed below as a sequence of steps:

[0022] Encoding Algorithm

[0023] 1) split the frame into M*N adjacent blocks each of n*n pixels

[0024] 2) calculate the local orientation for each pixel in each block

[0025] 3) calculate the edge detection function for each block.

[0026] 4) calculate the dominant orientation for each block, the amount of activity in each block, and the consistency of the dominant orientation

[0027] 5) to encode one data bit process each block within a predefined set of blocks distributed throughout the image, as follows:

[0028] 5a) look up the next element of the PRS (psuedo random sequence) for the data bit

[0029] 1) if it is a 1 set to add

[0030] 2) if it is a−1 set to subtract

[0031] 5b) segment the blocks in the following categories

[0032] a) a single edge/line in a dominant orientation

[0033] b) a low activity block

[0034] c) several major lines or edges

[0035] 5c) process the blocks as follows:-

[0036] a) add/subtract an elliptical function

[0037] a1) centred on the edge

[0038] a2) aligned to the block orientation

[0039] a3) scaled by the activity in the block

[0040] b) add/subtract a circular function

[0041] b1) centred on the centre of the block

[0042] b2) fixed strength

[0043] c) add/subtract the edge detection function

[0044] c1) centred on the centre of the block, and modulated by a circular function.

[0045] c2) scaled to bring it within the magnitude range of the elliptical function in a).

[0046] 6) repeat step 5) until all the bits are encoded.

[0047] Decoding Algorithm

[0048] 1) split the frame into M*N adjacent blocks each of n*n pixels

[0049] 2) calculate the local orientation for each pixel in each block

[0050] 3) calculate the edge detection function for each block.

[0051] 4) calculate the dominant orientation for each block, the amount of activity in each block, and the consistency of the dominant orientation

[0052] 5) to decode one data bit process each block within the predefined set of blocks distributed throughout the image, as follows:-

[0053] 5a) segment the blocks in the following categories

[0054] a) a single edge/line in a dominant orientation

[0055] b) a low activity block

[0056] c) several major lines or edges

[0057] 5b) process the blocks as follows:-

[0058] a) calculate the concave/convex-ness of an elliptical function

[0059] a1) centred on the edge

[0060] a2) aligned to the block orientation

[0061] a3) scaled by the activity in the block

[0062] b) calculate the concave/convex-ness of a circular function

[0063] b1) centred on the centre of the block

[0064] b2) fixed strength

[0065] c) calculate the concave/convex-ness of an edge detection function

[0066] c1) centred on the centre of the block and modulated by a circular function

[0067] c2) scaled to bring it within the magnitude range

[0068] 5c) correlate the convex/concave-ness of the block with the next element of the data bit 1 PRS and accumulate the result.

[0069] 5d) correlate the convex/concave-ness of the block with the next element of the data bit 0 PRS and accumulate the result.

[0070] 6) compare the data bit 1 accumulated correlation with the data bit 0 accumulated correlation. The larger of the two is the decoded data bit. The size of the correlation is the confidence in the result.

[0071] 7) repeat steps 5) and 6) for each data bit.

[0072] Referring now to FIGS. 1 to 3, the frame axis conventions used to describe the mathematics are shown in FIG. 1. A pixel is defined by its coordinates (x,y) and its luminance value is r(x,y). Note that the top left pixel of an image is the (0,0) pixel, and that the y axis has its positive direction down the frame.

[0073] As shown in FIG. 2, the frame is segmented into non-overlapping blocks, each block being of size n by n pixels. Smaller values of n mean that it is more likely that only a single edge will be found in any given block. It also means that more individual blocks will be available for the correlation process. Larger values of n mean that larger, and therefore more robust, insertions can be made. In practice a good choice of n is 8. The block axis conventions used in segmenting the frame are shown in FIG. 2.

[0074] Referring to FIG. 3, the local orientation for each point in the frame is calculated from four surrounding points by a process as described below. This gives a vector at each point in the frame, with the magnitude of the vector representing the strength of the feature, and the angle representing twice the local orientation. This is illustrated in FIG. 3. Thus the local orientation gives a measure of gradient of luminance in a particular direction within the block. A very large value of orientation indicates the existence of an edge; In this double angle form, the vectors can be vector-averaged over a block, to give the local orientation for the block. This provides a relatively fast estimating algorithm.

[0075] e.g., as shown in FIG. 3:

[0076] θ˜−45 degrees: by convention, θ is associated with point a=(x,y)

[0077] −dx˜0.7

[0078] −dy˜−0.7

[0079] θ is estimated from

[0080] a=r(x,y)

[0081] b=r(x,y+1)

[0082] c=r(x+1,y)

[0083] d=r(x+1,y+1)

[0084] e=d−a

[0085] f=b−c

[0086] Re=−2*e*f

[0087] Im=e²−f² $\theta =\frac{1}{2}{\mathrm{Tan}}^{-1}\left(\frac{\mathrm{Im}}{\mathrm{Re}}\right)$

[0088] θ is in single angle form

[0089] Re,Im are in double angle form

[0090] orientations are averaged in the Re,Im double angle form.

[0091] In the present invention, the measurement of luminance gradient is employed not only to give an assessment of the type of image in the block, and for determining the location of edges within the block as disclosed in PCT/GB96/00246, but also to determine the value of the edge detection function which is to be added to the image information in order to insert coded information within the image.

[0092] The edge detection function is calculated by taking the magnitudes of the orientation-vectors for each pixel, then for each pixel the average of the magnitudes of it's neighbours is calculated. I.e. for pixels (a) to (t) arranged in 4 rows of 5 columns, thus: $\begin{array}{ccccc}a& b& c& d& e\\ f& g& h& i& j\\ k& l& m& n& o\\ p& q& r& s& t\end{array}\begin{array}{c}\mathrm{the}\mathrm{averages}\\ \mathrm{are}\mathrm{calculated}\\ \mathrm{as}\mathrm{shown}\end{array}\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& \left(a+b+f+g\right)/4& \left(b+c+g+h\right)/4& \left(c+d+h+i\right)/4& \\ 0& \left(f+g+k+l\right)/4& \left(g+h+l+m\right)/4& \left(h+i+m+n\right)/4& \\ 0& \left(k+l+p+q\right)/4& \left(l+m+q+r\right)/4& \cdots \mathrm{etc}.& \end{array}$

[0093] The average magnitude for each pixel is then multiplied by a circular function centred on the center of the block. The edge detection function has a single number per pixel in the block but with the outer pixels set to zero. This is to say, that in the example discussed above, the edge detection function for pixels (a) to (e), (f), (j), (k), (o) and (p) to (t) are set to zero. This gives a pattern of values for the edge function thus:

[0094] The edge detection function is scaled to get it in the range 0.0 to 1.0, so that it is in the same range as an elliptical function calculated for blocks having just a single dominant edge as described in PCT/GB96/00246. This is done by taking the magnitude at each pixel, scaling it by a fixed factor, and limiting it between zero and a fixed factor.

[0095] The scale edge detection function is then added to the original image.