/*--------------------------------------------------------------------------* | E_BLIND -- embed a watermark by simply adding a message pattern | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | alpha -- embedding strength | | wr -- reference pattern (width x height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_BLIND( unsigned char *c, int width, int height, int m, double alpha, double *wr ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ /* Encode the message in a pattern */ ModulateOneBit( m, wr, wm, width, height ); /* Scale and add pattern to image (with clipping and rounding) */ AddScaledPattern( c, width, height, alpha, wm ); } /*--------------------------------------------------------------------------* | D_LC -- detect watermarks using linear correlation | | | | Arguments: | | c -- image | | width -- width of img | | height -- height of img | | tlc -- detection threshold | | wr -- reference pattern (width by height array of doubles) | | | | Return value: | | decoded message (0 or 1), or NO_WMK if no watermark is found | *--------------------------------------------------------------------------*/ int D_LC( unsigned char *c, int width, int height, double tlc, double *wr ) { double lc; /* linear correlation */ int m; /* decoded message (or NO_WMK) */ /* Find the linear correlation between the image and the reference pattern */ lc = ImgPatInnerProduct( c, wr, width, height ) / (width * height); /* Decode the message */ if( lc > tlc ) m = 1; else if( lc < -tlc ) m = 0; else m = NO_WMK; return m; } /*--------------------------------------------------------------------------* | ModulateOneBit -- encode a one-bit message by either copying or negating | | a given reference pattern | | | | Arguments: | | m -- message to be encoded | | wr -- reference pattern | | wm -- where to store resulting message pattern | | width -- width of wm | | height -- height of wm | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void ModulateOneBit( int m, double *wr, double *wm, int width, int height ) { int i; /* index into patterns */ if( m == 0 ) for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = -wr[ i ]; else for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = wr[ i ]; } /*--------------------------------------------------------------------------* | AddScaledPattern -- scale and add a pattern to an image with clipping | | and rounding | | | | This multiplies w by alpha to obtain the added pattern, and adds | | it to c, clipping and rounding each pixel to an 8-bit integer. | | | | Arguments: | | c -- image to which to add pattern (changed in place) | | width -- width of image | | height -- height of image | | alpha -- scaling factor | | w -- pattern to scale and add (width times height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void AddScaledPattern( unsigned char *c, int width, int height, double alpha, double *w ) { int i; /* pixel index */ for( i = 0; i < width * height; i = i + 1 ) c[ i ] = ClipRound( (double)c[ i ] + alpha * w[ i ] ); } /*--------------------------------------------------------------------------* | ImgPatInnerProduct -- get the inner product of an image and a pattern | | | | Arguments: | | c -- image | | w -- pattern | | width -- width of both patterns | | height -- height of both patterns | | | | Return value: | | inner product of c and w | *--------------------------------------------------------------------------*/ double ImgPatInnerProduct( unsigned char *c, double *w, int width, int height ) { double product; /* inner product of c and w */ int i; /* index into patterns */ product = 0; for( i = 0; i < width * height; i = i + 1 ) product = product + c[ i ] * w[ i ]; return product; } /*--------------------------------------------------------------------------* | ClipRound -- clip and round a real value to an 8-bit integer | | | | Arguments: | | v -- real value | | | | Return value: | | clipped and rounded value | *--------------------------------------------------------------------------*/ int ClipRound( double v ) { int iv; /* clipped and rounded value */ if( v < 0 ) iv = 0; else if( v > 255 ) iv = 255; else iv = (int)floor( v + .5 ); return iv; } /*--------------------------------------------------------------------------* | E_FIXEDLC - embed a watermark by adding a reference pattern after | | scaling to obtain a specific linear correlation | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | t -- threshold that will be used during detection | | beta -- embedding strength (target correlation will be thresh + beta) | | wr -- reference pattern (width x height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_FIXEDLC( unsigned char *c, int width, int height, int m, double t, double beta, double *wr ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ double cDotWm; /* inner product of c and wm */ double wmDotWm; /* inner product of wm with itself */ double alpha; /* scaling factor that will lead to desired linear correlation */ /* Encode the message in a pattern */ ModulateOneBit( m, wr, wm, width, height ); /* Determine scaling factor */ cDotWm = ImgPatInnerProduct( c, wm, width, height ); wmDotWm = PatPatInnerProduct( wm, wm, width, height ); alpha = (width * height * (t + beta) - cDotWm) / wmDotWm; /* Add pattern to image (with clipping and rounding) */ AddScaledPattern( c, width, height, alpha, wm ); } /*--------------------------------------------------------------------------* | PatPatInnerProduct -- get the inner product of two patterns | | | | Arguments: | | w1 -- one of the patterns | | w2 -- the other pattern | | width -- width of both patterns | | height -- height of both patterns | | | | Return value: | | inner product of w1 and w2 | *--------------------------------------------------------------------------*/ double PatPatInnerProduct( double *w1, double *w2, int width, int height ) { double product; /* inner product of w1 and w2 */ int i; /* index into patterns */ product = 0; for( i = 0; i < width * height; i = i + 1 ) product = product + w1[ i ] * w2[ i ]; return product; } /*--------------------------------------------------------------------------* | E_BLKBLIND -- embed a block-based watermark by simply adding a reference | | mark | | | | This routine performs the following three basic steps: | | | | 1. Extract a mark from the unwatermarked image. | | 2. Choose a new mark that is close to the extracted mark and (hopefully) | | within the detection region for the given reference mark. | | 3. Modify the image so that, when a mark is extracted from it, the | | result will be (approximately) the new mark chosen above. | | | | Step 2 is performed by blindly adding a fraction of the reference mark | | to the extracted mark: newMark = origMark + alpha * refMark. | | | | It should be pointed out that this routine could be greatly simplified, | | since step 3 involves adding a fraction of newMark - origMark to each | | pixel of the image, and newMark - origMark = alpha * refMark. This | | means that steps 1 and 2 could be skipped, with step 3 using | | alpha * refMark directly. | | | | However, in later block-based embedding algorithms, step 2 will be | | performed in more sophisticated ways that do not allow such | | simplification. The present routine is coded with steps 1 and 2 in | | place so that its relationship to these later routines is apparent. | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of image | | height -- height of image | | m -- one-bit message to embed | | alpha -- embedding strength | | wr -- reference mark (length 64 vector of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_BLK_BLIND( unsigned char *c, int width, int height, int m, double alpha, double *wr ) { double wm[ 64 ]; /* message mark */ double vo[ 64 ]; /* mark extracted from image before modification */ double vw[ 64 ]; /* new mark that's (hopefully) inside the detection region around wm */ /* Encode message in a pattern */ ModulateOneBit( m, wr, wm, 64, 1 ); /* Embed */ ExtractMark( c, width, height, vo ); MixBlind( vo, alpha, wm, vw ); InvExtractMark( c, width, height, vw ); } /*--------------------------------------------------------------------------* | D_BLK_CC -- detect block-based watermarks using normalized correlation | | | | Arguments: | | c -- image | | width -- width of image | | height -- height of image | | tcc -- detection threshold | | wr -- reference mark (8x8 array of doubles) | | | | Return value: | | decoded message (0 or 1), or NO_WMK if no watermark is found | *--------------------------------------------------------------------------*/ int D_BLK_CC( unsigned char *c, int width, int height, double tcc, double *wr ) { double v[ 64 ]; /* mark extracted from image */ double cc; /* correlation coefficient between wr and v */ int m; /* decoded message (or NO_WMK) */ /* Compute the correlation coefficient between wr and a mark extracted from the image */ ExtractMark( c, width, height, v ); cc = CorrCoef( v, wr ); /* Decode the message */ if( cc > tcc ) m = 1; else if( cc < -tcc ) m = 0; else m = NO_WMK; return m; } /*--------------------------------------------------------------------------* | ExtractMark -- Extract a mark vector from an image by dividing the image | | into 8x8 blocks and taking their average. | | | | Arguments: | | c -- image from which to extract mark | | width -- width of image | | height -- height of image | | v -- where to store resulting 64-element vector | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void ExtractMark( unsigned char *c, int width, int height, double *v ) { int imgX, imgY; /* coordinates in image */ int imgI; /* index into c */ int markX, markY; /* coordinates in averaged block */ int markI; /* index into averaged block */ int n[ 64 ]; /* number of pixels accumulated into each of the 64 elements of v */ /* Initialize v and n to 0. */ for( markI = 0; markI < 64; markI = markI + 1 ) { v[ markI ] = 0; n[ markI ] = 0; } /* Accumulate pixels. */ for( imgY = 0; imgY < height; imgY = imgY + 1 ) for( imgX = 0; imgX < width; imgX = imgX + 1 ) { /* Find index for this pixel in image. */ imgI = imgY * width + imgX; /* Find index for this pixel in accumulated block */ markX = imgX % 8; markY = imgY % 8; markI = markY * 8 + markX; /* Accumulate. */ v[ markI ] = v[ markI ] + c[ imgI ]; n[ markI ] = n[ markI ] + 1; } /* Divide by n to obtain average of 8x8 blocks. */ for( markI = 0; markI < 64; markI = markI + 1 ) v[ markI ] = v[ markI ] / n[ markI ]; } /*--------------------------------------------------------------------------* | MixBlind -- use blind embedding to choose a new vector in mark space | | that is close to a given extracted mark and (hopefully) | | inside the detection region | | | | Arguments: | | vo -- mark extracted from original image | | alpha -- embedding strength | | wm -- message mark | | vw -- where to store resulting vector | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void MixBlind( double *vo, double alpha, double *wm, double *vw ) { int i; for( i = 0; i < 64; i = i + 1 ) vw[ i ] = vo[ i ] + alpha * wm[ i ]; } /*--------------------------------------------------------------------------* | InvExtractMark -- modify an image so that, when entered into | | ExtractMark, it will produce (approximately) a given | | mark | | | | In principle, for each pixel in the image, c, this function could simply | | let | | | | c[ imgI ] = c[ imgI ] + vw[ markI ] - vo[ markI ] | | | | where imgI is the index of a pixel, markI is the corresponding index in | | the extracted vector, vw is the desired new vector, and vo is the vector | | obtained by applying ExtractMark to the original, unmodified image. | | (Recall that each element of an extracted mark is the average of a bunch | | of pixels.) Unfortunately, due to clipping and round-off errors, this | | does not achieve the level of precision required for our experiments. | | In other words, if we implement this with clipping and rounding, and | | then enter the resulting image into ExtractMark, the vector we obtain is | | not always close enough to vw. | | | | To fix this problem, we use the following algorithm: | | | | 1. Initialize n[ markI ] to the number of pixels that are averaged | | together to obtain the markI'th element of an extracted vector. | | | | 2. Initialize delta[ markI ] = n[ markI ] (vw[ markI ] - vo[ markI ]) to | | the total amount we want to add to the pixels that go into the | | markI'th element of an extracted vector. | | | | 3. Loop through the pixels in the image. At the imgI'th pixel, perform | | the following steps: | | | | a. Let oldPixel = the original value of the pixel, c[ imgI ]. | | | | b. Compute newPixel = c[ imgI ] + delta[ markI ] / n[ markI ], where | | markI is the index of the extracted vector element that | | corresponds to imgI. | | | | c. Set c[ imgI ] to the value of newPixel with clipping and rounding. | | Thus, c[ imgI ] will not be exactly equal to newPixel. | | | | d. Decrement n[ markI ]. This is now the number of pixels remaining | | in the set that are averaged for element markI. | | | | e. Let delta[ markI ] = delta[ markI ] - (c[ imgI ] - oldPixel). | | This is now the total amount to be added to the remaining | | n[ markI ] pixels. | | | | If no errors were introduced by clipping and rounding, this algorithm | | would yield exactly the same results as the simpler method. However, | | when an error is introduced, it will usually be corrected over | | subsequent pixels. Thus, this represents a simple form of error | | diffusion. | | | | Arguments: | | c -- image to modify (changed in place) | | width -- width of image | | height -- height of image | | vw -- new mark | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void InvExtractMark( unsigned char *c, int width, int height, double *vw ) { int nvo[ 64 ]; /* sums of pixels that would be averaged to obtain extracted mark (nvo[ i ] = n[ i ] * vo[ i ] in the comment block above this routine) */ double delta[ 64 ]; /* total values to be added to pixels that have not yet been modified */ int n[ 64 ]; /* numbers of pixels that have not yet been modified */ int oldPixel; /* value of a pixel before being modified */ double newPixel; /* desired value of a pixel after being modified, but before clipping and rounding */ int imgX, imgY; /* coordinates in image */ int imgI; /* index into c */ int markX, markY; /* coordinates in averaged block */ int markI; /* index into averaged block */ /* Initialize nvo and n to 0. */ for( markI = 0; markI < 64; markI = markI + 1 ) { nvo[ markI ] = 0; n[ markI ] = 0; } /* Accumulate pixels. */ for( imgY = 0; imgY < height; imgY = imgY + 1 ) for( imgX = 0; imgX < width; imgX = imgX + 1 ) { /* Find index for this pixel in image. */ imgI = imgY * width + imgX; /* Find index for this pixel in accumulated block */ markX = imgX % 8; markY = imgY % 8; markI = markY * 8 + markX; /* Accumulate. */ nvo[ markI ] = nvo[ markI ] + c[ imgI ]; n[ markI ] = n[ markI ] + 1; } /* Initialize delta. */ for( markI = 0; markI < 64; markI = markI + 1 ) delta[ markI ] = n[ markI ] * vw[ markI ] - nvo[ markI ]; /* Modify image. */ for( imgY = 0; imgY < height; imgY = imgY + 1 ) for( imgX = 0; imgX < width; imgX = imgX + 1 ) { /* Find index for this pixel in image. */ imgI = imgY * width + imgX; /* Find index for this pixel in accumulated block */ markX = imgX % 8; markY = imgY % 8; markI = markY * 8 + markX; /* Find desired value of this pixel */ oldPixel = c[ imgI ]; newPixel = (double)c[ imgI ] + delta[ markI ] / n[ markI ]; /* Set pixel to new value, with clipping and rounding */ c[ imgI ] = ClipRound( newPixel ); /* Update n and delta. */ n[ markI ] = n[ markI ] - 1; delta[ markI ] = delta[ markI ] - (c[ imgI ] - oldPixel); } } /*--------------------------------------------------------------------------* | CorrCoef -- compute the correlation coefficient between two vectors in | | mark space | | | | Arguments: | | v1 -- one vector | | v2 -- the other vector | | | | Return value: | | correlation coefficient between v1 and v2 | *--------------------------------------------------------------------------*/ double CorrCoef( double *v1, double *v2 ) { double cc; /* correlation coefficient */ double v1n[ 64 ]; /* v1 - mean of v1 */ double v2n[ 64 ]; /* v2 - mean of v2 */ double v1v2; /* v1n dot v2n */ double v1v1; /* v1n dot v1n */ double v2v2; /* v2n dot v2n */ double mean; /* mean of v1 or v2 */ int i; /* index into vectors */ /* Subtract out the mean of v1. */ mean = MarkMean( v1 ); for( i = 0; i < 64; i = i + 1 ) v1n[ i ] = v1[ i ] - mean; /* Subtract out the mean of v2. */ mean = MarkMean( v2 ); for( i = 0; i < 64; i = i + 1 ) v2n[ i ] = v2[ i ] - mean; /* Compute various dot products. */ v1v2 = MarkMarkInnerProduct( v1n, v2n ); v1v1 = MarkMarkInnerProduct( v1n, v1n ); v2v2 = MarkMarkInnerProduct( v2n, v2n ); /* Test for the pathalogical case in which the two vectors have essentially zero magnitude (ESSENTIALLY_ZERO is a very small number -- testing for exactly zero doesn't work because of round-off problems). If we have that case, let the correlation coefficient = 0. Otherwise, compute the correlation coefficient properly. */ if( v1v1 * v2v2 < ESSENTIALLY_ZERO ) cc = 0; else cc = v1v2 / sqrt( v1v1 * v2v2 ); return cc; } /*--------------------------------------------------------------------------* | MarkMean -- get the mean of the elements of a vector in mark space | | | | Arguments: | | v -- vector to find mean of | | | | Return value: | | mean of v | *--------------------------------------------------------------------------*/ double MarkMean( double *v ) { double mean; /* mean of v */ int i; /* index into v */ mean = 0; for( i = 0; i < 64; i = i + 1 ) mean = mean + v[ i ]; mean = mean / 64; return mean; } /*--------------------------------------------------------------------------* | MarkMarkInnerProduct -- get the inner product of two vectors in mark | | space (64 dimensions) | | | | Arguments: | | v1 -- one of the vectors | | v2 -- the other vector | | | | Return value: | | inner product of v1 and v2 | *--------------------------------------------------------------------------*/ double MarkMarkInnerProduct( double *v1, double *v2 ) { double product; /* inner product */ int i; /* index into vectors */ product = 0; for( i = 0; i < 64; i = i + 1 ) product = product + v1[ i ] * v2[ i ]; return product; } /*--------------------------------------------------------------------------* | E_SIMPLE_8 -- embed an eight-bit watermark by adding or subtracting a | | reference pattern for each bit | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- eight-bit message to embed | | alpha -- embedding strength | | seed -- seed for generating patterns | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_SIMPLE_8( unsigned char *c, int width, int height, int m, double alpha, int seed ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ /* Encode message in a pattern */ SimpleModulate( m, seed, wm, width, height ); /* Normalize the encoded pattern to have zero mean and unit variance (this is done only to ensure that a given value of alpha leads to the same fidelity impact in E_SIMPLE8 as in E_BLIND, so that the parameters in our experiments are comparable) */ NormalizePattern( wm, width, height ); /* Scale and add pattern to image (with clipping and rounding) */ AddScaledPattern( c, width, height, alpha, wm ); } /*--------------------------------------------------------------------------* | D_SIMPLE8 -- detect and decode 8-bit watermarks embedded with E_SIMPLE8 | | | | Arguments: | | c -- image | | width -- width of img | | height -- height of img | | seed -- seed for generating reference patterns | | | | Return value: | | decoded message (does not determine whether watermark is present) | *--------------------------------------------------------------------------*/ int D_SIMPLE8( unsigned char *c, int width, int height, int seed ) { static double v[ MAX_IMG_SIZE ]; /* image converted to real values for call to SimpleDemodulate */ int i; /* pixel index */ /* Convert image to data type compatible with SimpleDemodulate (this is just done for symmetry, since SimpleModulate makes an array of real-values) */ for( i = 0; i < width * height; i = i + 1 ) v[ i ] = c[ i ]; return SimpleDemodulate( v, width, height, seed ); } /*--------------------------------------------------------------------------* | SimpleModulate -- encode a message in a pattern by adding or subtracting | | a reference pattern for each bit | | | | Arguments: | | m -- message to be encoded | | seed -- each seed leads to a unique encoding of m | | wm -- where to store resulting message pattern | | width -- width of wm | | height -- height of wm | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void SimpleModulate( int m, int seed, double *wm, int width, int height ) { int bitNum; /* bit number */ static double wr[ MAX_PATTERN_SIZE ]; /* reference pattern for bit bitNum */ int bitVal; /* value of bit bitNum */ int i; /* Initialize the message pattern to 0 */ for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = 0; /* Loop through the eight bits of the message */ for( bitNum = 0; bitNum < 8; bitNum = bitNum + 1 ) { /* Get the reference pattern for this bit (NOTE: by calling MakeRandomPattern with a seed of seed + bitNum, we get a distinct pattern for each bit) */ MakeRandomPattern( seed + bitNum, wr, width, height ); /* Find the value of this bit */ if( m & (1 << bitNum) ) bitVal = 1; else bitVal = 0; /* Either add or subtract the reference pattern */ if( bitVal == 1 ) for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = wm[ i ] + wr[ i ]; else for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = wm[ i ] - wr[ i ]; } } /*--------------------------------------------------------------------------* | NormalizePattern -- normalize a pattern to have zero mean and unit | | standard-deviation | | | | Arguments: | | w -- pattern to be normalized (changed in place) | | width -- width of w | | height -- height of w | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void NormalizePattern( double *w, int width, int height ) { double mean; /* mean of pattern */ double std; /* standard deviation of pattern */ int i; /* subtract out mean */ mean = 0; for( i = 0; i < width * height; i = i + 1 ) mean = mean + w[ i ]; mean = mean / (width * height); for( i = 0; i < width * height; i = i + 1 ) w[ i ] = w[ i ] - mean; /* normalize standard deviation */ std = 0; for( i = 0; i < width * height; i = i + 1 ) std = std + w[ i ] * w[ i ]; std = sqrt( std / (width * height) ); if( std > ESSENTIALLY_ZERO ) for( i = 0; i < width * height; i = i + 1 ) w[ i ] = w[ i ] / std; } /*--------------------------------------------------------------------------* | SimpleDemodulate -- decode a message by correlating an image against | | a reference pattern for each bit | | | | Arguments: | | c -- image | | width -- width of img | | height -- height of img | | seed -- seed for generating reference patterns | | | | Return value: | | decoded message | *--------------------------------------------------------------------------*/ int SimpleDemodulate( double *v, int width, int height, int seed ) { static double wr[ MAX_IMG_SIZE ]; /* reference pattern for one bit */ int bitNum; /* bit number */ int m; /* decoded message */ /* Initialize all the bits to 0. */ m = 0; /* Set each bit to 1 if the correlation between its reference pattern and the given image is positive */ for( bitNum = 0; bitNum < 8; bitNum = bitNum + 1 ) { MakeRandomPattern( seed + bitNum, wr, width, height ); if( PatPatInnerProduct( v, wr, width, height ) > 0 ) m = m | (1 << bitNum); } return m; } /*--------------------------------------------------------------------------* | MakeRandomPattern -- make a random pattern by drawing pixel values | | independently from a Normal distribution and then | | normalizing to have zero mean and unit variance | | | | Arguments: | | seed -- each seed leads to a unique pattern | | w -- where to store generated pattern | | width -- width of w | | height -- height of w | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void MakeRandomPattern( int seed, double *w, int width, int height ) { int i; SeedRand( seed ); for( i = 0; i < width * height; i = i + 1 ) w[ i ] = RandNormal(); NormalizePattern( w, width, height ); } /*--------------------------------------------------------------------------* | E_TRELLIS_8 -- embed an eight-bit watermark by adding a trellis-coded | | pattern | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- eight-bit message to embed | | alpha -- embedding strength | | seed -- seed for generating patterns | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_TRELLIS_8( unsigned char *c, int width, int height, int m, double alpha, int seed ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes msg */ /* Encode message in a pattern */ TrellisModulate( m, seed, wm, width, height ); /* Normalize the encoded pattern to have zero mean and unit variance (this is done only to ensure that a given value of alpha leads to the same fidelity impact in E_SIMPLE8 as in E_BLIND, so that the parameters in our experiments are comparable) */ NormalizePattern( wm, width, height ); /* Add pattern to image (with clipping and rounding) */ AddScaledPattern( c, width, height, alpha, wm ); } /*--------------------------------------------------------------------------* | D_TRELLIS8 -- detect and decode 8-bit watermarks coded with a simple | | trellis code | | | | Arguments: | | c -- image | | width -- width of img | | height -- height of img | | seed -- seed for generating reference patterns | | | | Return value: | | decoded message (does not determine whether or not mark is present) | *--------------------------------------------------------------------------*/ int D_TRELLIS8( unsigned char *c, int width, int height, int seed ) { static double v[ MAX_IMG_SIZE ]; /* image converted to real values for call to TrellisDemodulate */ int i; /* pixel index */ /* Convert image to data type compatible with SimpleDemodulate (this is just done for symmetry, since TrellisModulate makes an array of real-values) */ for( i = 0; i < width * height; i = i + 1 ) v[ i ] = c[ i ]; return TrellisDemodulate( seed, v, width, height ); } /*--------------------------------------------------------------------------* | TrellisModulate -- encode a message in a pattern using a simple form of | | trellis-coded modulation | | | | Arguments: | | m -- message to be encoded | | seed -- each seed leads to a unique encoding of m | | wm -- where to store resulting message pattern | | width -- width of wm | | height -- height of wm | | | | Return value: | | none | *--------------------------------------------------------------------------*/ /* nextState -- description of the graph that defines the code. For each state, nextState contains two entries. nextState[ s ][ 0 ] gives the state reached by crossing the 0 arc from state s. nextState[ s ][ 1 ] gives the state reached by crossing the 1 arc. nextState is global so that it can be used in other routines based on this trellis (TrellisDemodulate, TrellisEncode, and TrellisDecode) */ static int nextState[ NUM_STATES ][ 2 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, }; void TrellisModulate( int m, int seed, double *wm, int width, int height ) { int state; /* current state */ int bitNum; /* bit number */ static double wr[ MAX_PATTERN_SIZE ]; /* reference pattern for bit bitNum */ int bitVal; /* value of bit bitNum */ int i; /* Initialize the message pattern to 0 */ for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = 0; /* Start at state 0 */ state = 0; for( bitNum = 0; bitNum < NUM_BITS; bitNum = bitNum + 1 ) { /* Get the reference pattern for this bit (NOTE: by calling MakeRandomPattern with a seed of seed + state * NUM_BITS + bitNum, we get a distinct pattern for each transition in the trellis) */ MakeRandomPattern( seed + state * NUM_BITS + bitNum, wr, width, height ); /* Find the value of this bit */ if( m & (1 << bitNum) ) bitVal = 1; else bitVal = 0; /* Either add or subtract the reference pattern */ if( bitVal == 1 ) for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = wm[ i ] + wr[ i ]; else for( i = 0; i < width * height; i = i + 1 ) wm[ i ] = wm[ i ] - wr[ i ]; /* Go on to the next state */ state = nextState[ state ][ bitVal ]; } } /*--------------------------------------------------------------------------* | TrellisDemodulate -- use Viterbi's algorithm to decode a message from a | | trellis-modulated pattern | | | | Arguments: | | seed -- seed used during modulation of message | | v -- pattern to decode | | width -- width of v | | height -- height of v | | | | Return value: | | decoded message | *--------------------------------------------------------------------------*/ int TrellisDemodulate( int seed, double *v, int width, int height ) { /* Uses global nextState (see TrellisModulate) */ static double wr[ MAX_IMG_SIZE ]; /* reference pattern for one arc */ double lc0[ 8 ]; /* correlation obtained from best path (so far) to each state */ int m0[ 8 ]; /* message obtained from best path (so far) to each state */ double lc1[ 8 ]; /* values of lc0 in next iteration */ int m1[ 8 ]; /* values of m0 in next iteration */ int bitNum; /* bit number */ int state; /* state index */ int next; /* index of state at the other end of an arc */ double lc; /* correlation between v and wr */ int bestState; /* state with the highest correlation at the end of the algorithm */ /* All paths must start from state 0, so we initialize that state to 0 correlation and null message, and label the remaining states as unreached. */ lc0[ 0 ] = 0; m0[ 0 ] = 0; for( state = 1; state < 8; state = state + 1 ) lc0[ state ] = STATE_NOT_REACHED; /* Apply the Viterbi algorithm to decode 10 bits. */ for( bitNum = 0; bitNum < 10; bitNum = bitNum + 1 ) { /* Indicate that the states in the next iteration are not yet reached. */ for( state = 0; state < 8; state = state + 1 ) lc1[ state ] = STATE_NOT_REACHED; /* Loop through all the states in the current iteration, updating the values for states in the next iteration. */ for( state = 0; state < 8; state = state + 1 ) if( lc0[ state ] != STATE_NOT_REACHED ) { /* Find the correlation between v and the reference mark for the two arcs leading out of this state (the arc for 1 is labled with a positive version of this reference mark, the arc for 0 is labled with a negative version) */ MakeRandomPattern( seed + state * 10 + bitNum, wr, width, height ); lc = PatPatInnerProduct( v, wr, width, height ) / (width * height); /* Update values for the state connected to this state by a 0 arc */ next = nextState[ state ][ 0 ]; if( lc1[ next ] == STATE_NOT_REACHED || lc1[ next ] < lc0[ state ] - lc ) { lc1[ next ] = lc0[ state ] - lc; m1[ next ] = m0[ state ]; } /* We know that the last two bits of the message must be 0 (because they're padding added by TrellisModulate), so only update using the 1 arc if this bit is not one of them. */ if( bitNum < 8 ) { next = nextState[ state ][ 1 ]; if( lc1[ next ] == STATE_NOT_REACHED || lc1[ next ] < lc0[ state ] + lc ) { lc1[ next ] = lc0[ state ] + lc; m1[ next ] = m0[ state ] | (1 << bitNum); } } } /* Go on to the next iteration. */ for( state = 0; state < 8; state = state + 1 ) { lc0[ state ] = lc1[ state ]; m0[ state ] = m1[ state ]; } } /* Find the state with the highest correlation. */ bestState = 0; for( state = 1; state < 8; state = state + 1 ) if( lc0[ state ] > lc0[ bestState ] ) bestState = state; /* Return the message for the best state. */ return m0[ bestState ]; } /*--------------------------------------------------------------------------* | E_BLK_8 -- embed a trellis-coded 8-bit watermark in a block-based | | watermark | | | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of image | | height -- height of image | | m -- eight-bit message to embed | | alpha -- embedding strength | | seed -- seed for generating patterns | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_BLK_8( unsigned char *c, int width, int height, int m, double alpha, int seed ) { double wm[ 64 ]; /* message mark */ double vo[ 64 ]; /* mark extracted from image before modification */ double vw[ 64 ]; /* new mark that's (hopefully) inside the detection region around wm */ /* Encode message in a pattern */ TrellisModulate( m, seed, wm, 8, 8 ); /* Normalize the encoded pattern to have zero mean and unit variance */ NormalizePattern( wm, 8, 8 ); /* Embed */ ExtractMark( c, width, height, vo ); MixBlind( vo, alpha, wm, vw ); InvExtractMark( c, width, height, vw ); } /*--------------------------------------------------------------------------* | D_BLK_TRELLIS8 -- detect block-based, trellis coded, 8-bit watermarks | | using correlation coefficient | | | | Arguments: | | c -- image | | width -- width of img | | height -- height of img | | tcc -- detection threshold | | seed -- seed for generating reference marks | | | | Return value: | | decoded message (8 bits), or NO_WMK if no watermark is found | *--------------------------------------------------------------------------*/ int D_BLK_TRELLIS8( unsigned char *c, int width, int height, double tcc, int seed ) { double v[ 64 ]; /* mark extracted from image */ int m; /* message decoded from v */ double wm[ 64 ]; /* message mark obtained by re-encoding m */ double cc; /* correlation coefficient between v and wm */ /* Decode the watermark. */ ExtractMark( c, width, height, v ); m = TrellisDemodulate( seed, v, 8, 8 ); /* Determine whether the message m was embedded. */ TrellisModulate( m, seed, wm, 8, 8 ); cc = CorrCoef( v, wm ); if( cc < tcc ) m = NO_WMK; return m; } /*--------------------------------------------------------------------------* | E_BLKFIXEDCC -- embed a block-based watermark with fixed-correlation | | coefficient embedding | | | | This routine performs the following three basic steps: | | | | 1. Extract a mark from the unwatermarked image. | | 2. Choose a new mark that is close to the extracted mark and has a fixed | | correlation coefficient with the given reference mark. | | 3. Modify the image so that, when a mark is extracted from it, the | | result will be (approximately) the new mark chosen above. | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of image | | height -- height of image | | m -- one-bit message to embed | | tcc -- detection threshold that will be used by detector | | beta -- embedding strength | | wr -- reference mark (length 64 vector of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_BLK_FIXEDCC( unsigned char *c, int width, int height, int m, double tcc, double beta, double *wr ) { double wm[ 64 ]; /* message mark */ double vo[ 64 ]; /* mark extracted from image before modification */ double vw[ 64 ]; /* new mark that's (hopefully) inside the detection region around wm */ /* Encode message in a pattern */ ModulateOneBit( m, wr, wm, 64, 1 ); /* Embed */ ExtractMark( c, width, height, vo ); MixFixedCC( vo, tcc, beta, wm, vw ); InvExtractMark( c, width, height, vw ); } /*--------------------------------------------------------------------------* | MixFixedCC -- compute a vector that is close to a given extracted | | vector, and has a fixed correlation coefficient with a | | given message mark | | | | The correlation between the new vector and the reference vector is | | specified as the sum of a detection threshold and a "strength" | | parameter. The new vector is as close as possible to the given | | extracted vector, measured by Euclidian distance. | | | | Arguments: | | vo -- mark extracted from original image | | tcc -- detection threshold | | beta -- strength parameter | | wm -- message mark | | vw -- where to store resulting vector | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void MixFixedCC( double *vo, double tcc, double beta, double *wm, double *vw ) { double wmMean; /* mean of wm */ double voMean; /* mean of vo */ double X[ 64 ]; /* unit vector aligned with wm - wmMean */ double Y[ 64 ]; /* unit vector orthogonal to X, such that X and Y describe the plane containing wm - wmMean, vo - voMean, and the origin */ double xvo, yvo; /* coordinates of vo in the XY plane */ double xa, ya; /* unit vector in the XY plane that has the desired correlation with the watermark */ double xvw, yvw; /* coordinates of new vector in the XY plane */ int i; /* index into vectors */ /* Subtract out the mean of wm to obtain an initial version of X. */ wmMean = MarkMean( wm ); for( i = 0; i < 64; i = i + 1 ) X[ i ] = wm[ i ] - wmMean; /* Subtract out the mean of vo to obtain an initial version of Y. */ voMean = MarkMean( vo ); for( i = 0; i < 64; i = i + 1 ) Y[ i ] = vo[ i ] - voMean; /* Apply Gram-Schmidt orthonormalization to obtain two orthogonal unit vectors. */ Orthonormalize( X, Y ); /* Find projection of vo into the XY plane. */ xvo = MarkMarkInnerProduct( vo, X ); yvo = MarkMarkInnerProduct( vo, Y ); /* Find unit vector in the XY plane that has a normalized correlation with the watermark of tcc + beta */ xa = tcc + beta; ya = sqrt( 1 - xa * xa ); /* Find the point on the line described by xa,ya that is closest to xvo,yvo */ xvw = xa * (xa * xvo + ya * yvo); yvw = ya * (xa * xvo + ya * yvo); /* Project xvw,yvw back into mark space */ for( i = 0; i < 64; i = i + 1 ) vw[ i ] = xvw * X[ i ] + yvw * Y[ i ] + voMean; } /*--------------------------------------------------------------------------* | Orthonormalize -- convert two vectors into two unit-length, orthogonal | | vectors that lie in the same plane | | | | Arguments: | | X -- vector who's direction will not be changed (changed in place) | | Y -- vector who's direction will be changed (changed in place) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void Orthonormalize( double *X, double *Y ) { double XDotY; /* inner product of original Y and unit-length X */ double len; /* Euclidian length (magnitude) of a vector */ int i; /* index into marks */ /* Normalize X to unit length. */ len = 0; for( i = 0; i < 64; i = i + 1 ) len = len + X[ i ] * X[ i ]; len = sqrt( len ); for( i = 0; i < 64; i = i + 1 ) X[ i ] = X[ i ] / len; /* Subtract X * (X dot Y) from Y to ensure that X and Y are orthogonal. */ XDotY = MarkMarkInnerProduct( X, Y ); for( i = 0; i < 64; i = i + 1 ) Y[ i ] = Y[ i ] - XDotY * X[ i ]; /* Normalize Y to unit length. */ len = 0; for( i = 0; i < 64; i = i + 1 ) len = len + Y[ i ] * Y[ i ]; len = sqrt( len ); for( i = 0; i < 64; i = i + 1 ) Y[ i ] = Y[ i ] / len; } /*--------------------------------------------------------------------------* | E_BLKFIXEDR -- embed a block-based watermark with fixed-robustness | | embedding | | | | This routine performs the following three basic steps: | | | | 1. Extract a mark from the unwatermarked image. | | 2. Choose a new mark that is close to the extracted mark and has a fixed | | estimated robustness with respect to a given reference mark and | | detection threshold. | | 3. Modify the image so that, when a mark is extracted from it, the | | result will be (approximately) the new mark chosen above. | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of image | | height -- height of image | | m -- one-bit message to embed | | tcc -- detection threshold that will be used by detector | | r -- embedding strength | | wr -- reference mark (length 64 vector of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_BLK_FIXEDR( unsigned char *c, int width, int height, int m, double tcc, double r, double *wr ) { double wm[ 64 ]; /* message mark */ double vo[ 64 ]; /* mark extracted from image before modification */ double vw[ 64 ]; /* new mark that's (hopefully) inside the detection region around wm */ /* Encode message in a pattern */ ModulateOneBit( m, wr, wm, 64, 1 ); /* Embed */ ExtractMark( c, width, height, vo ); MixFixedR( vo, tcc, r, wm, vw ); InvExtractMark( c, width, height, vw ); } /*--------------------------------------------------------------------------* | MixFixedR -- compute a vector that is close to a given extracted | | vector, and has a fixed estimated robustness value with | | respect to a given reference mark and detection threshold | | | | The robustness value is specified with a "strength" parameter. | | The new vector is as close as possible to the given | | extracted vector, measured by Euclidian distance. | | | | Arguments: | | vo -- mark extracted from original image | | tcc -- detection threshold | | r -- strength parameter | | wm -- message mark | | vw -- where to store resulting vector | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void MixFixedR( double *vo, double tcc, double r, double *wm, double *vw ) { double wmMean; /* mean of wm */ double voMean; /* mean of vo */ double X[ 64 ]; /* unit vector aligned with wm - wmMean */ double Y[ 64 ]; /* unit vector orthogonal to X, such that X and Y describe the plane containing wm - wmMean, vo - voMean, and the origin */ double xvo, yvo; /* coordinates of vo in the XY plane */ double xvw, yvw; /* possible coordinates for new vector in the XY plane (this point yields the desired robustness value, but might not be the closest one) */ double dx; /* = xvw - xvo */ double dy; /* = yvw - yvo */ double d; /* Euclidian distance between xvo,yvo and xvw,yvw */ double bestXvw, bestYvw; /* closest point in XY plane that yields the desired robustness */ double bestD; /* Euclidian distance between xvo,yvo and bestXvw,bestYvw */ int i; /* index into vectors, and counter during search for bestXvw,bestYvw */ /* Subtract out the mean of wm to obtain an initial version of X. */ wmMean = MarkMean( wm ); for( i = 0; i < 64; i = i + 1 ) X[ i ] = wm[ i ] - wmMean; /* Subtract out the mean of vo to obtain an initial version of Y. */ voMean = MarkMean( vo ); for( i = 0; i < 64; i = i + 1 ) Y[ i ] = vo[ i ] - voMean; /* Apply Gram-Schmidt orthonormalization to obtain two orthogonal unit vectors. */ Orthonormalize( X, Y ); /* Find projection of vo into the XY plane. */ xvo = MarkMarkInnerProduct( vo, X ); yvo = MarkMarkInnerProduct( vo, Y ); /* Perform brute-force search for the point on the XY plane that yields the desired robustness and is closest to xvo,yvo. */ for( i = 0; i < 10000; i = i + 1 ) { /* Find coordinates of this point (the formula for xvw ensures that the point will yield the desired robustness) */ yvw = yvo * i / 10000; xvw = sqrt( tcc * tcc * (r + yvw * yvw) / (1 - tcc * tcc) ); /* Compute the distance from this point to xvo,yvo. */ dx = xvw - xvo; dy = yvw - yvo; d = dx * dx + dy * dy; /* Keep track of the closest point found so far. */ if( i == 0 || d < bestD ) { bestXvw = xvw; bestYvw = yvw; bestD = d; } } /* Project bestXvw,bestYvw back into mark space */ for( i = 0; i < 64; i = i + 1 ) vw[ i ] = bestXvw * X[ i ] + bestYvw * Y[ i ] + voMean; } /*--------------------------------------------------------------------------* | E_DIRTYPAPER -- embed a block-based watermark with fixed-robustness | | embedding and a dirty-paper code | | | | This routine performs the following four basic steps: | | | | 1. Extract a mark from the unwatermarked image. | | 2. Search through a set of random message marks to find the one that | | has the highest correlation with the extracted mark. This becomes | | the message mark that will be embedded. | | 3. Choose a new mark that is close to the extracted mark and has a fixed | | estimated robustness with respect to the message mark and the given | | detection threshold. | | 4. Modify the image so that, when a mark is extracted from it, the | | result will be (approximately) the new mark chosen above. | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | tcc -- detection threshold that will be used by detector | | r -- embedding strength | | seed -- seed for random number generator (this specifies the set of | | random reference marks) | | N -- number of reference marks for each message | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_DIRTY_PAPER( unsigned char *c, int width, int height, int m, double tcc, double r, int seed, int N ) { double vo[ 64 ]; /* mark extracted from unwatermarked image */ double w[ 64 ]; /* one reference mark from the set of random marks that represent the message */ double wm[ 64 ]; /* best reference mark for representing the message */ double vw[ 64 ]; /* mark that is reasonably close to origMark, but is inside the detection region for msgMark */ int markNum; /* counter for searching through reference marks */ double cor; /* correlation between origMark and refMark */ double bestCor; /* correlation between origMark and msgMark */ int i; /* index into mark vectors */ /* Extract a mark from the unwatermarked image. */ ExtractMark( c, width, height, vo ); /* Find the best message mark. */ StartMarks( seed, m ); for( markNum = 0; markNum < N; markNum = markNum + 1 ) { /* Find the correlation between vo and this mark. */ GetNextMark( w ); cor = MarkMarkInnerProduct( w, vo ); /* Keep track of the mark with the highest correlation. */ if( markNum == 0 || cor > bestCor ) { for( i = 0; i < 64; i = i + 1 ) wm[ i ] = w[ i ]; bestCor = cor; } } /* Embed */ MixFixedR( vo, tcc, r, wm, vw ); InvExtractMark( c, width, height, vw ); } /*--------------------------------------------------------------------------* | D_DIRTYPAPER -- detect dirty-paper coded watermarks | | | | Arguments: | | c -- image | | width -- width of image | | height -- height of image | | tcc -- detection threshold | | seed -- seed for generating reference marks | | N -- number of marks for each message | | | | Return value: | | decoded message (0 or 1), or NO_WMK if no watermark is found | *--------------------------------------------------------------------------*/ int D_DIRTYPAPER( unsigned char *c, int width, int height, double tcc, int seed, int N ) { double v[ 64 ]; /* mark extracted from image */ double wr[ 64 ]; /* a reference mark */ int m; /* message */ double cc; /* correlation coefficient between v and reference mark for message m */ int bestM; /* message represented by the reference mark that has the highest correlation with v */ double bestCC; /* highest correlation coefficient with v */ int markNum; /* counter for looping through the reference marks for each message */ /* Extract a mark from the image. */ ExtractMark( c, width, height, v ); /* Loop through all the possible messages (0 and 1), and find the message mark that has the highest correlation coefficient with the extracted mark */ for( m = 0; m < 2; m = m + 1 ) { StartMarks( seed, m ); for( markNum = 0; markNum < N; markNum = markNum + 1 ) { /* Find the correlation coefficient between v and this mark. */ GetNextMark( wr ); cc = CorrCoef( wr, v ); /* Keep track of the message with the highest correlation. */ if( (m == 0 && markNum == 0) || cc > bestCC ) { bestM = m; bestCC = cc; } } } /* Determine whether the watermark is present. */ if( bestCC < tcc ) m = NO_WMK; else m = bestM; return m; } /*--------------------------------------------------------------------------* | StartMarks -- set up to make a sequence of marks specified by a seed and | | a message value | | | | Arguments: | | seed -- for a given message, each seed leads to a different sequence | | of marks | | m -- message | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void StartMarks( int seed, int m ) { SeedRand( seed + m ); } /*--------------------------------------------------------------------------* | GetNextMark -- get the next mark in the sequence initiated by a call | | to StartMarks | | | | Arguments: | | w -- where to store mark | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetNextMark( double *w ) { int i; /* index into mark */ for( i = 0; i < 64; i = i + 1 ) w[ i ] = RandNormal(); NormalizePattern( w, 8, 8 ); } /*--------------------------------------------------------------------------* | E_LATTICE -- embed a message using lattice-coded watermarking | | | | Arguments: | | c -- image in which to embed (changed in place) | | width -- width of image | | height -- height of image | | m -- message to embed (array of integer bit values) | | mLen -- length of message (number of bits) | | beta -- embedding strength | | alpha0 -- lattice spacing (as a multiple of the length of wr0) | | wr0 -- basic reference mark (8x8 pattern) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_LATTICE( unsigned char *c, int width, int height, int *m, int mLen, double beta, double alpha0, double *wr0 ) { double alpha; /* value of alpha0 after normalizing */ double wr[ 64 ]; /* value of wr0 after normalizing */ int mc[ MAX_CODED_BITS ]; /* message after coding */ int numRows; /* number of block rows in image */ int numCols; /* number of block columns in image */ int row, col; /* location of a block */ int i0; /* index of first pixel in block */ double cor; /* correlation between block and wr */ int bitNum; /* number of bit embedded in block */ int zm; /* index in sublattice for message */ double wa; /* one element of added pattern */ int x, y; /* position within block */ /* Normalize the description of the lattice. */ alpha = NormalizeLatticeDesc( alpha0, wr0, wr ); /* Find number of blocks in image. */ numRows = height / 8; numCols = width / 8; /* Encode message. */ PadAndCodeMsg( m, mLen, mc, numRows * numCols ); /* Embed coded bits. */ bitNum = 0; for( row = 0; row < numRows; row = row + 1 ) for( col = 0; col < numCols; col = col + 1 ) { /* Find the first pixel of this block. */ i0 = row * 8 * width + col * 8; /* Correlate this block with the reference pattern. */ cor = 0; for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) cor = cor + c[ i0 + y * width + x ] * wr[ y * 8 + x ]; /* Find the index of the closest point in the sublattice for this message. */ zm = (int)floor( (cor - mc[ bitNum ] * alpha) / (2 * alpha) + .5 ) * 2 + mc[ bitNum ]; /* Modify the block so that its correlation with the reference pattern, scaled by alpha, will be close to zm. */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) { /* Find one element of the added pattern. */ wa = beta * (alpha * zm - cor) * wr[ y * 8 + x ]; /* Add wa to the image with clipping and rounding. */ c[ i0 + y * width + x ] = ClipRound( c[ i0 + y * width + x ] + wa ); } /* Go on to the next bit. */ bitNum = bitNum + 1; } } /*--------------------------------------------------------------------------* | D_LATTICE -- detect a message embedded with lattice-coded watermarking | | | | Arguments: | | c -- image | | width -- width of image | | height -- height of image | | alpha0 -- lattice spacing (as a multiple of the length of wr0) | | wr0 -- basic reference mark (8x8 pattern) | | m -- where to store detected message | | | | Return value: | | length of detected message (number of bits) | *--------------------------------------------------------------------------*/ int D_LATTICE( unsigned char *c, int width, int height, double alpha0, double *wr0, int *m ) { double alpha; /* value of alpha0 after normalizing */ double wr[ 64 ]; /* value of wr0 after normalizing */ int mc[ MAX_CODED_BITS ]; /* coded message */ int mcLen; /* length of coded message */ int mLen; /* length of decoded message */ int numRows; /* number of block rows in image */ int numCols; /* number of block columns in image */ int row, col; /* location of a block */ int i0; /* index of first pixel in block */ double cor; /* correlation between block and wr */ int bitNum; /* number of bit embedded in block */ int z; /* index in lattice */ int x, y; /* position within block */ /* Normalize the description of the lattice. */ alpha = NormalizeLatticeDesc( alpha0, wr0, wr ); /* Find number of blocks in image. */ numRows = height / 8; numCols = width / 8; /* Detect coded bits. */ bitNum = 0; for( row = 0; row < numRows; row = row + 1 ) for( col = 0; col < numCols; col = col + 1 ) { /* Find the first pixel of this block. */ i0 = row * 8 * width + col * 8; /* Correlate this block with the reference pattern. */ cor = 0; for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) cor = cor + c[ i0 + y * width + x ] * wr[ y * 8 + x ]; /* Find the index of the closest point in the lattice */ z = (int)floor( cor / alpha + .5 ); /* The least significant bit of z is the watermark bit in this block */ mc[ bitNum ] = z & 1; /* Go on to the next bit. */ bitNum = bitNum + 1; } mcLen = bitNum; /* Decode the detected bit sequence. */ mLen = TrellisDecode( mc, mcLen, m ); return mLen; } /*--------------------------------------------------------------------------* | NormalizeLatticeDesc -- normalize the description of a lattice | | | | This takes a lattice described by a reference mark and a multiplier. It | | scales the multiplier by the length of the reference mark and normalizes | | the mark to unit length. This results in the same lattice as the one | | described originally, but simplifies its use. | | | | Arguments: | | wr0 -- original reference mark | | alpha0 -- original multiplier | | wr1 -- where to store new reference mark | | | | Return value: | | new multiplier | *--------------------------------------------------------------------------*/ double NormalizeLatticeDesc( double alpha0, double *wr0, double *wr1 ) { double alpha1; /* new multiplier */ double wr0Len; /* Euclidian length of wr0 */ int i; /* index into wr0 and wr1 */ /* Find the length of wr0. */ wr0Len = 0; for( i = 0; i < 64; i = i + 1 ) wr0Len = wr0Len + wr0[ i ] * wr0[ i ]; wr0Len = sqrt( wr0Len ); /* Scale the multiplier. */ alpha1 = wr0Len * alpha0; /* Normalize the reference mark. */ for( i = 0; i < 64; i = i + 1 ) wr1[ i ] = wr0[ i ] / wr0Len; return alpha1; } /*--------------------------------------------------------------------------* | PadAndCodeMsg -- prepare a message for embedding with E_LATTICE | | | | Arguments: | | m -- message to prepare (expressed as an array of bits) | | mLen -- length of message | | mc -- where to store resulting coded bit sequence | | mcLen -- desired length of mc | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void PadAndCodeMsg( int *m, int mLen, int *mc, int mcLen ) { int paddedBits[ MAX_MSG_BITS ]; /* message padded with enough zeros to make its length as close as possible to mcLen / 4, without going over */ int paddedLen; /* length of padded sequence */ int i; /* index into bit sequences */ /* Pad the message to obtain the maximum number of message bits that can be represented with codedLen code bits. */ paddedLen = (int)(mcLen / 4); for( i = 0; i < mLen; i = i + 1 ) paddedBits[ i ] = m[ i ]; for( i = mLen; i < paddedLen; i = i + 1 ) paddedBits[ i ] = 0; /* Encode the padded message. */ TrellisEncode( paddedBits, paddedLen, mc ); /* Pad the encoded bits to exactly codedLen bits (this is necessary if codedLen is not an integral multiple of 4) */ for( i = 4 * paddedLen; i < mcLen; i = i + 1 ) mc[ i ] = 0; } /*--------------------------------------------------------------------------* | TrellisEncode -- encode a message with a sequence of bits, using a | | trellis code | | | | Arguments: | | m -- message to be encoded (expressed as an array of bits) | | mLen -- length of message | | mc -- where to store resulting coded bit sequence | | | | Return value: | | none | *--------------------------------------------------------------------------*/ /* trellisBits -- Labels on arcs in graph. For each state, there are two 4-bit codes: one for the arc traversed by a 0 in the message, and one for the arc traversed by a 1. This table is global so that it can be used in TrellisDecode. */ static int trellisBits[ 8 ][ 2 ][ 4 ] = { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, }; void TrellisEncode( int *m, int mLen, int *mc ) { /* Uses global nextState (see TrellisModulate in E-TRELLIS8/D-TRELLIS8) */ int state; /* current state */ int bitNum; /* message bit number */ int bitVal; /* = m[ bitNum ] */ int i; /* index into arc label */ /* Start at state 0 */ state = 0; for( bitNum = 0; bitNum < mLen; bitNum = bitNum + 1 ) { /* Get the value of this message bit */ bitVal = m[ bitNum ]; /* Copy label of appropriate arc into mc */ for( i = 0; i < 4; i = i + 1 ) mc[ bitNum * 4 + i ] = trellisBits[ state ][ bitVal ][ i ]; /* Go on to the next state */ state = nextState[ state ][ bitVal ]; } } /*--------------------------------------------------------------------------* | TrellisDecode -- use Viterbi's algorithm to decode a trellis-coded | | bit sequence | | | | Arguments: | | mc -- coded bits | | mcLen -- length of mc | | m -- where to store decoded bits | | | | Return value: | | length of decoded message | *--------------------------------------------------------------------------*/ int TrellisDecode( int *mc, int mcLen, int *m ) { /* Uses global nextState (see TrellisModulate in E-TRELLIS8/D-TRELLIS8) */ /* Uses global trellisBits (see TrellisEncode) */ int h0[ 8 ]; /* hamming distance obtained from best path (so far) to each state */ static int m0[ 8 ][ MAX_MSG_BITS ]; /* message obtained from best path (so far) to each state */ int h1[ 8 ]; /* values of h0 in next iteration */ static int m1[ 8 ][ MAX_MSG_BITS ]; /* values of m0 in next iteration */ int mLen; /* length of message */ int bitNum; /* bit number */ int state; /* state index */ int next; /* index of state at the other end of an arc */ int h; /* hamming distance between portion of mc and label for an arc */ int bestState; /* state with the lowest hamming distance at the end of the algorithm */ int i; /* index into messages */ /* Find length of message */ mLen = mcLen / 4; /* All paths must start from state 0, so we initialize that state to 0 hamming distance, and label the remaining states as unreached. */ h0[ 0 ] = 0; for( state = 1; state < 8; state = state + 1 ) h0[ state ] = STATE_NOT_REACHED; /* Apply the Viterbi algorithm to decode. */ for( bitNum = 0; bitNum < mLen; bitNum = bitNum + 1 ) { /* Indicate that the states in the next iteration are not yet reached. */ for( state = 0; state < 8; state = state + 1 ) h1[ state ] = STATE_NOT_REACHED; /* Loop through all the states in the current iteration, updating the values for states in the next iteration. */ for( state = 0; state < 8; state = state + 1 ) if( h0[ state ] != STATE_NOT_REACHED ) { /* Update values for the state connected to this state by a 0 arc. (Note: mc + 4 * bitNum is pointer arithmetic. The four bits used to encode bit bitNum of m are (mc + 4 * bitNum)[ 0...3 ]. */ next = nextState[ state ][ 0 ]; h = HammingDist( mc + 4 * bitNum, trellisBits[ state ][ 0 ], 4 ); if( h1[ next ] == STATE_NOT_REACHED || h1[ next ] > h0[ state ] + h ) { h1[ next ] = h0[ state ] + h; for( i = 0; i < bitNum; i = i + 1 ) m1[ next ][ i ] = m0[ state ][ i ]; m1[ next ][ bitNum ] = 0; } /* Update values for the state connected to this state by a 1 arc. */ next = nextState[ state ][ 1 ]; h = HammingDist( mc + 4 * bitNum, trellisBits[ state ][ 1 ], 4 ); if( h1[ next ] == STATE_NOT_REACHED || h1[ next ] > h0[ state ] + h ) { h1[ next ] = h0[ state ] + h; for( i = 0; i < bitNum; i = i + 1 ) m1[ next ][ i ] = m0[ state ][ i ]; m1[ next ][ bitNum ] = 1; } } /* Go on to the next iteration. */ for( state = 0; state < 8; state = state + 1 ) { h0[ state ] = h1[ state ]; for( i = 0; i < mLen; i = i + 1 ) m0[ state ][ i ] = m1[ state ][ i ]; } } /* Find the state with the minimum hamming distance. */ bestState = 0; for( state = 1; state < 8; state = state + 1 ) if( h0[ state ] < h0[ bestState ] ) bestState = state; /* Return the message for the best state. */ for( i = 0; i < mLen; i = i + 1 ) m[ i ] = m0[ bestState ][ i ]; return mLen; } /*--------------------------------------------------------------------------* | HammingDist -- compute the hamming distance between two bit sequences | | | | Arguments: | | b1 -- one bit sequence | | b2 -- other bit sequence | | len -- length of sequences | | | | Return value: | | hamming distance | *--------------------------------------------------------------------------*/ int HammingDist( int *b1, int *b2, int len ) { int h; int i; h = 0; for( i = 0; i < len; i = i + 1 ) if( b1[ i ] != b2[ i ] ) h = h + 1; return h; } /*--------------------------------------------------------------------------* | D_WHITE -- detect watermarks using whitening and linear correlation | | | | Arguments: | | c -- image | | width -- width of img | | height -- height of img | | twh -- detection threshold | | wr -- reference pattern (width x height array of doubles) | | | | Return value: | | decoded message (0 or 1), or NO_WMK if no watermark is found | *--------------------------------------------------------------------------*/ int D_WHITE( unsigned char *c, int width, int height, double twh, double *wr ) { static double c1[ MAX_IMG_SIZE ]; /* whitened image */ static double wr1[ MAX_IMG_SIZE ]; /* whitened reference pattern */ double lc; /* correlation between c1 and wr1 */ int m; /* decoded message (or NO_WMK) */ int i; /* index into patterns */ /* Whiten the image. */ for( i = 0; i < width * height; i = i + 1 ) c1[ i ] = c[ i ]; Whiten( c1, width, height, 0 ); /* Whiten the watermark reference pattern. */ for( i = 0; i < width * height; i = i + 1 ) wr1[ i ] = wr[ i ]; Whiten( wr1, width, height, 0 ); /* Compute the correlation between the whitened image and whitened reference pattern. */ lc = PatPatInnerProduct( c1, wr1, width, height ) / (width * height); /* Decode the message */ if( lc > twh ) m = 1; else if( lc < -twh ) m = 0; else m = NO_WMK; return m; } /*--------------------------------------------------------------------------* | Whiten -- apply a whitening filter to a pattern | | | | This routine is used in two detection algorithms: D_WHITE and | | D_WHITE_BLK_CC. In D_WHITE_BLK_CC, the filter must wrap around at the | | edges of the given array. In D_WHITE it must not. So Whiten takes a | | flag as one argument indicating whether or not to wrap around. | | | | Arguments: | | v -- pattern to whiten (changed in place) | | width -- width of pattern | | height -- height of pattern | | mustWrapAround -- 1 if filter must wrap around at edges of pattern | | (as in D_WHITE_BLK_CC). 0 if it must not (as in | | D_WHITE). | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void Whiten( double *v, int width, int height, int mustWrapAround ) { /* Whitening filter. */ static double fwh[ 11 ][ 11 ] = { 0.0, 0.0, 0.0, 0.0, 0.1, -0.2, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, -0.3, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2, -0.5, 0.2, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.4, -1.1, 0.4, 0.1, 0.0, 0.0, 0.0, 0.1, 0.1, 0.2, 0.4, 1.8, -5.3, 1.8, 0.4, 0.2, 0.1, 0.1, -0.2, -0.3, -0.5, -1.1, -5.3, 15.8, -5.3, -1.1, -0.5, -0.3, -0.2, 0.1, 0.1, 0.2, 0.4, 1.8, -5.3, 1.8, 0.4, 0.2, 0.1, 0.1, 0.0, 0.0, 0.0, 0.1, 0.4, -1.1, 0.4, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2, -0.5, 0.2, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, -0.3, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, -0.2, 0.1, 0.0, 0.0, 0.0, 0.0 }; static double v1[ MAX_IMG_SIZE ]; /* whitened version of v */ double t; /* accumulator for computing each element of v1 */ int x, y; /* location in v and v1 */ int xOff, yOff; /* offsets from x,y */ int x1, y1; /* location x,y plus offsets, possibly wrapped around */ int i; /* index into v and v1 */ /* Loop through each element of v1. */ for( y = 0; y < height; y = y + 1 ) for( x = 0; x < width; x = x + 1 ) { /* Compute value of v1[x,y] by applying filter to v, centered at x,y. This loops through the 11x11 neighborhood around x,y, multiplying each element in the neighborhood by the corresponding element of fwh, and accumulating the results in t. */ t = 0; for( yOff = -5; yOff <= 5; yOff = yOff + 1 ) { /* Find the row of elements corresponding to offset yOff. If mustWrapAround is set, then this will wrap around instead of going off the edge. (Note: the '+ height' in the expression for wrapping around is necessary to deal with negative values of y1. This won't work if height < 5.) */ y1 = y + yOff; if( mustWrapAround ) y1 = (y1 + height) % height; /* If row y1 is not off the edge ... */ if( 0 <= y1 && y1 < height ) for( xOff = -5; xOff <= 5; xOff = xOff + 1 ) { /* Find the column corresponding to offset xOff, with wraparound if mustWrapAround is set. */ x1 = x + xOff; if( mustWrapAround ) x1 = (x1 + width) % width; /* If column x1 is not off the edge, accumulate. */ if( 0 <= x1 && x1 < width ) t = t + fwh[ yOff + 5 ][ xOff + 5 ] * v[ y1 * width + x1 ]; } } /* Store the accumulated value. */ v1[ y * width + x ] = t; } /* Copy v1 into v. */ for( i = 0; i < width * height; i = i + 1 ) v[ i ] = v1[ i ]; } /*--------------------------------------------------------------------------* | D_WHITE_BLK_CC -- detect block-based watermarks using whitening and | | correlation coefficeint | | | | Arguments: | | c -- image | | width -- width of image | | height -- height of image | | tcc -- detection threshold | | wr -- reference mark (8x8 array of doubles) | | | | Return value: | | decoded message (0 or 1), or NO_WMK if no watermark is found | *--------------------------------------------------------------------------*/ int D_WHITE_BLK_CC( unsigned char *c, int width, int height, double tcc, double *wr ) { double wr1[ 64 ]; /* whitened reference mark */ double v[ 64 ]; /* mark extracted from image and whitened */ double cc; /* correlation coefficient between v and wr1 */ int m; /* message */ int i; /* index into marks */ /* Whiten the reference mark. */ for( i = 0; i < 64; i = i + 1 ) wr1[ i ] = wr[ i ]; Whiten( wr1, 8, 8, 1 ); /* Extract a mark from the image and whiten it. Note: the last argument in the call to Whiten indicates that whitening is performed with wrap-around. */ ExtractMark( c, width, height, v ); Whiten( v, 8, 8, 1 ); /* Find the correlation coefficient between the whitened reference mark and the whitened extracted mark. */ cc = CorrCoef( v, wr1 ); /* Decode the message */ if( cc > tcc ) m = 1; else if( cc < -tcc ) m = 0; else m = NO_WMK; return m; } /*--------------------------------------------------------------------------* | E_PERC_GSCALE - embed a watermark by adding a reference pattern after | | scaling to obtain a fixed fidelity | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | jnds -- embedding strength (target according to Watson's model) | | wr -- reference pattern (width by height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_PERC_GSCALE( unsigned char *c, int width, int height, int m, double jnds, double *wr ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ /* Encode the message in a pattern */ ModulateOneBit( m, wr, wm, width, height ); /* Scale the message pattern by an amount that yields close to the desired fidelity, and add it to image (with clipping and rounding) */ AddPercScaledPattern( c, width, height, jnds, wm ); } /*--------------------------------------------------------------------------* | AddPercScaledPattern -- scale a pattern by an amount that leads to a | | desired number of JNDs (according to Watson's | | model), and add it to an image | | | | Arguments: | | c -- image to which to add pattern (changed in place) | | width -- width of image | | height -- height of image | | targetJNDs -- desired number of JNDs | | w -- pattern to scale and add (width times height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void AddPercScaledPattern( unsigned char *c, int width, int height, double targetJNDs, double *w ) { static double C[ MAX_IMG_SIZE ]; /* image in block-DCT domain */ static double s[ MAX_IMG_SIZE ]; /* slacks for block-DCT coefficients computed using Watson's model */ double jnds; /* perceptual distance */ double alphaInTheory; /* theoretically best alpha */ double bestAlpha; /* best value of alpha found in practice */ double bestJNDs; /* perceptual impact of using bestAlpha */ double alpha, alpha0, alpha1; /* used during search for best value of alpha in practice */ static unsigned char c1[ MAX_IMG_SIZE ]; /* temporary copy of c used during search for best value of alpha */ static double w1[ MAX_IMG_SIZE ]; /* pattern added using a given value of alpha (different from alpha*w because of clipping and rounding) */ static double W[ MAX_IMG_SIZE ]; /* added pattern in the block-DCT domain */ int i; /* index into block-DCT arrays */ int n; /* counter for brute-force search */ /* Get the slacks for the block-DCT coefficients */ Img2BlockDCT( c, C, width, height ); GetWatsonSlks( C, s, width, height ); /* Determine perceptual impact of adding w to image */ Pat2BlockDCT( w, W, width, height ); jnds = 0; for( i = 0; i < width * height; i = i + 1 ) jnds = jnds + pow( W[ i ] / s[ i ], 4. ); jnds = pow( jnds, 0.25 ); /* In theory, if there were no clipping and rounding, the value of alpha we should use is targetJNDs/jnds */ alphaInTheory = targetJNDs / jnds; /* In practice, with clipping and rounding, alphaInTheory might not result in the desired number of JND's. This probably wouldn't be a serious problem in an actual application. However, the size of this problem is different in different embedding algorithms, which could invalidate our comparative tests. So, to ensure that all our algorithms result in JND's tightly distributed around the target value, we now perform a simple brute-force search around alphaInTheory to find a better value of alpha. */ alpha0 = alphaInTheory * 0.2; alpha1 = alphaInTheory * 1.1; for( n = 0; n <= 40; n = n + 1 ) { /* Find the value of alpha to try in this iteration */ alpha = alpha0 + n * (alpha1 - alpha0) / 40; /* Make a temporary, watermarked version of c using this value of alpha */ for( i = 0; i < width * height; i = i + 1 ) c1[ i ] = c[ i ]; AddScaledPattern( c1, width, height, alpha, w ); /* Find out the actual pattern that was added (this might be different from alpha*w because of clipping and rounding) */ for( i = 0; i < width * height; i = i + 1 ) w1[ i ] = c1[ i ] - c[ i ]; /* Determine the perceptual impact of adding this pattern */ Pat2BlockDCT( w1, W, width, height ); jnds = 0; for( i = 0; i < width * height; i = i + 1 ) jnds = jnds + pow( W[ i ] / s[ i ], 4. ); jnds = pow( jnds, 0.25 ); /* Keep track of the value of alpha which results in a number of JNDs closest to targetJNDs */ if( n == 0 || fabs( jnds - targetJNDs ) < fabs( bestJNDs - targetJNDs ) ) { bestAlpha = alpha; bestJNDs = jnds; } } /* Add the pattern with the best value of alpha found */ AddScaledPattern( c, width, height, bestAlpha, w ); } /*--------------------------------------------------------------------------* | Img2BlockDCT -- convert an image into the block DCT domain | | | | Arguments: | | c -- image to be converted | | C -- result of conversion (filled in by this routine) | | width -- width of image | | height -- height of image | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void Img2BlockDCT( unsigned char *c, double *C, int width, int height ) { double block[ 8 ][ 8 ]; /* 8x8 block in DCT domain */ int row, col; /* location in array of 8x8 blocks */ int x, y; /* location within an 8x8 block */ int i0; /* index of upper-left corner of current block */ /* Loop through the 8x8 blocks in the image */ for( row = 0; row < height / 8; row = row + 1 ) for( col = 0; col < width / 8; col = col + 1 ) { /* Find the upper-left corner of this block */ i0 = row * 8 * width + col * 8; /* Copy the image block into an 8x8 array of doubles */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) block[ y ][ x ] = c[ i0 + y * width + x ]; /* Convert block to DCT domain */ Data2DCT88( block ); /* Copy the 8x8 array of doubles into the block DCT array */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) C[ i0 + y * width + x ] = block[ y ][ x ]; } } /*--------------------------------------------------------------------------* | GetWatsonSlks -- using Watson's model, compute the slacks for all the | | terms in the block-DCT representation of an image | | | | Arguments: | | C -- image in the block-DCT domain | | s -- where to store resulting 8x8 array of slacks | | width -- width of C | | height -- height of C | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetWatsonSlks( double *C, double *s, int width, int height ) { int numBlkRows; /* number of rows of 8x8 blocks in C */ int numBlkCols; /* number of columns of blocks in C */ int blkRow, blkCol; /* location in array of blocks */ int x, y; /* location within a block */ double CBlk[ 64 ]; /* one block in C */ double sBlk[ 64 ]; /* one block in s */ double C00; /* average DC term of blocks in C */ int i; /* Find the number of block rows and columns in this image */ numBlkRows = (int)(height / 8); numBlkCols = (int)(width / 8); /* Find the average DC term of blocks in C */ C00 = 0; for( blkRow = 0; blkRow < numBlkRows; blkRow = blkRow + 1 ) for( blkCol = 0; blkCol < numBlkCols; blkCol = blkCol + 1 ) C00 = C00 + C[ (blkRow * 8 + 0) * width + (blkCol * 8 + 0) ]; C00 = C00 / (numBlkRows * numBlkCols); /* Prevent divide-by-zeros in the pathalogical case of a completely black image */ if( C00 == 0 ) C00 = 1; /* Initialize all the slacks to 1 (this is necessary if the image width or height is not an even multiple of 8, because, in that case, some rows or columns of s won't be filled in, and subsequent use of the array could lead to problems) */ for( i = 0; i < width * height; i = i + 1 ) s[ i ] = 1; /* Loop through the blocks of the image, computing the slacks for each one */ for( blkRow = 0; blkRow < numBlkRows; blkRow = blkRow + 1 ) for( blkCol = 0; blkCol < numBlkCols; blkCol = blkCol + 1 ) { /* Copy the block into a temporary, 8x8 array */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) CBlk[ y * 8 + x ] = C[ (blkRow * 8 + y) * width + (blkCol * 8 + x) ]; /* Compute the slacks for this block */ GetWatsonSlksForOneBlock( CBlk, C00, sBlk ); /* Copy the slacks for this block into the full array of slacks */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) s[ (blkRow * 8 + y) * width + (blkCol * 8 + x) ] = sBlk[ y * 8 + x ]; } } /*--------------------------------------------------------------------------* | GetWatsonSlksForOneBlock -- compute the slacks for one 8x8 DCT block | | | | Arguments: | | C -- block for which to compute slacks | | C00 -- mean DC value of all blocks in image | | s -- where to store resulting 8x8 array of slacks | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetWatsonSlksForOneBlock( double *C, double C00, double *s ) { /* table of sensitivity values */ static double t[ 8 * 8 ] = { 1.404, 1.011, 1.169, 1.664, 2.408, 3.433, 4.796, 6.563, 1.011, 1.452, 1.323, 1.529, 2.006, 2.716, 3.679, 4.939, 1.169, 1.323, 2.241, 2.594, 2.988, 3.649, 4.604, 5.883, 1.664, 1.529, 2.594, 3.773, 4.559, 5.305, 6.281, 7.600, 2.408, 2.006, 2.988, 4.559, 6.152, 7.463, 8.713, 10.175, 3.433, 2.716, 3.649, 5.305, 7.463, 9.625, 11.588, 13.519, 4.796, 3.679, 4.604, 6.281, 8.713, 11.588, 14.500, 17.294, 6.563, 4.939, 5.883, 7.600, 10.175, 13.519, 17.294, 21.156 }; double tL; /* luminance masking threshold */ double m; /* contrast masking threshold */ int i; /* index into block */ /* Loop through the block */ for( i = 0; i < 64; i = i + 1 ) { /* Compute luminance masking (which incorporates sensitivity) */ tL = t[ i ] * pow( C[ 0 ] / C00, .649 ); /* Compute contrast masking (which incorporates luminance masking) NOTE: for the DC term, there is no contrast masking */ if( i == 0 ) m = tL; else m = max( tL, pow( fabs( C[ i ] ), .7 ) * pow( tL, .3 ) ); /* Store resulting slack */ s[ i ] = m; } } /*--------------------------------------------------------------------------* | Pat2BlockDCT -- convert an array of doubles into the block DCT domain | | | | Arguments: | | w -- array to be converted | | W -- result of conversion (filled in by this routine) | | width -- width of image | | height -- height of image | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void Pat2BlockDCT( double *w, double *W, int width, int height ) { double block[ 8 ][ 8 ]; /* 8x8 block in DCT domain */ int row, col; /* location in array of 8x8 blocks */ int x, y; /* location within an 8x8 block */ int i0; /* index of upper-left corner of current block */ /* Loop through the 8x8 blocks in the pattern */ for( row = 0; row < height / 8; row = row + 1 ) for( col = 0; col < width / 8; col = col + 1 ) { /* Find the upper-left corner of this block */ i0 = row * 8 * width + col * 8; /* Copy the pattern block into an 8x8 array of doubles */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) block[ y ][ x ] = w[ i0 + y * width + x ]; /* Convert block to DCT domain */ Data2DCT88( block ); /* Copy the 8x8 array of doubles into the block DCT array */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) W[ i0 + y * width + x ] = block[ y ][ x ]; } } /*--------------------------------------------------------------------------* | E_PERC_SHAPE - embed a watermark by adding a reference pattern after | | simple perceptual shaping | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | jnds -- embedding strength (target according to Watson's model) | | wr -- reference pattern (width by height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_PERC_SHAPE( unsigned char *c, int width, int height, int m, double jnds, double *wr ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ static double C[ MAX_IMG_SIZE ]; /* image in block-DCT domain */ static double s[ MAX_IMG_SIZE ]; /* perceptual slacks */ static double W[ MAX_IMG_SIZE ]; /* pattern in block-DCT domain */ static double ws[ MAX_IMG_SIZE ]; /* shaped version of wm */ int i; /* index into block-DCT */ /* Encode the message in a pattern */ ModulateOneBit( m, wr, wm, width, height ); /* Get the perceptual slacks for this image */ Img2BlockDCT( c, C, width, height ); GetWatsonSlks( C, s, width, height ); /* Convert the message pattern into the block-DCT domain, shape it using the slacks computed from the image, and convert it back into the spatial domain to obtain the shaped pattern, ws */ Pat2BlockDCT( wm, W, width, height ); for( i = 0; i < width * height; i = i + 1 ) W[ i ] = W[ i ] * s[ i ]; BlockDCT2Pat( W, ws, width, height ); /* Scale the shaped pattern by an amount that yields close to the desired fidelity, and add it to image (with clipping and rounding) */ AddPercScaledPattern( c, width, height, jnds, ws ); } /*--------------------------------------------------------------------------* | BlockDCT2Pat -- convert an array of doubles from the block DCT domain | | into the spatial domain | | | | Arguments: | | W -- pattern in the block DCT domain | | w -- result of conversion (filled in by this routine) | | width -- width of image | | height -- height of image | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void BlockDCT2Pat( double *W, double *w, int width, int height ) { double block[ 8 ][ 8 ]; /* 8x8 block in DCT domain */ int row, col; /* location in array of 8x8 blocks */ int x, y; /* location within an 8x8 block */ int i0; /* index of upper-left corner of current block */ /* Loop through the 8x8 blocks in the block DCT array */ for( row = 0; row < height / 8; row = row + 1 ) for( col = 0; col < width / 8; col = col + 1 ) { /* Find the upper-left corner of this block */ i0 = row * 8 * width + col * 8; /* Copy the dct block into an 8x8 array of doubles */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) block[ y ][ x ] = W[ i0 + y * width + x ]; /* Convert block to spatial domain */ DCT2Data88( block ); /* Copy the 8x8 array into the pattern */ for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) w[ i0 + y * width + x ] = block[ y ][ x ]; } } /*--------------------------------------------------------------------------* | E_PERC_OPT - embed a watermark by adding a reference pattern after | | "optimal" perceptual shaping | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | jnds -- embedding strength (target according to Watson's model) | | wr -- reference pattern (width by height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_PERC_OPT( unsigned char *c, int width, int height, int m, double jnds, double *wr ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ static double C[ MAX_IMG_SIZE ]; /* image in block-DCT domain */ static double s[ MAX_IMG_SIZE ]; /* perceptual slacks */ static double W[ MAX_IMG_SIZE ]; /* pattern in block-DCT domain */ static double ws[ MAX_IMG_SIZE ]; /* shaped version of wm */ int i; /* index into block-DCT */ /* Encode the message in a pattern */ ModulateOneBit( m, wr, wm, width, height ); /* Get the perceptual slacks for this image */ Img2BlockDCT( c, C, width, height ); GetWatsonSlks( C, s, width, height ); /* Convert the message pattern into the block-DCT domain, shape it using the slacks computed from the image, and convert it back into the spatial domain to obtain the shaped pattern, ws (NOTE: the C library routine pow() cannot take cube roots of negative numbers) */ Pat2BlockDCT( wm, W, width, height ); for( i = 0; i < width * height; i = i + 1 ) if( W[ i ] < 0 ) W[ i ] = -pow( -W[ i ] * pow( s[ i ], 4. ), 1. / 3. ); else W[ i ] = pow( W[ i ] * pow( s[ i ], 4. ), 1. / 3. ); BlockDCT2Pat( W, ws, width, height ); /* Scale the shaped pattern by an amount that yields close to the desired fidelity, and add it to image (with clipping and rounding) */ AddPercScaledPattern( c, width, height, jnds, ws ); } /*--------------------------------------------------------------------------* | E_MOD -- embed a watermark using modulo 256 addition | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of img | | height -- height of img | | m -- one-bit message to embed | | alpha -- embedding strength | | wr -- reference pattern (width x height array of doubles) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_MOD( unsigned char *c, int width, int height, int m, double alpha, double *wr ) { static double wm[ MAX_IMG_SIZE ]; /* pattern that encodes m */ int i; /* pixel index */ /* Encode the message in a pattern */ ModulateOneBit( m, wr, wm, width, height ); /* Scale the message pattern by alpha and add it to the image, modulo 256 (NOTE: the scaled reference pattern is rounded to an integer before adding) */ for( i = 0; i < width * height; i = i + 1 ) c[ i ] = (int)(c[ i ] + floor( alpha * wm[ i ] + .5)) % 256; } /*--------------------------------------------------------------------------* | E_DCTQ -- embed an authentication mark by quantizing coefficients in the | | block DCT of an image | | | | Arguments: | | c -- image in which to embed mark (changed in place) | | width -- width of image | | height -- height of image | | seed -- a different mark is embedded for each value of seed | | alpha -- maximum JPEG quantization factor that the mark should survive | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_DCTQ( unsigned char *c, int width, int height, int seed, double alpha ) { static int sigBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* bit pattern to embed */ int numBits; /* number of bits embedded in image */ /* Make the psuedo-random bit pattern. */ numBits = (height / 8) * (width / 8) * 4; GetRandomSignature( seed, sigBits, numBits ); /* Embed bits into the image. */ EmbedDCTQWmkInImage( c, width, height, seed, alpha, sigBits ); } /*--------------------------------------------------------------------------* | D_DCTQ -- determine whether or not an image is authentic using a | | semi-fragile watermark based on DCT quantization | | | | Arguments | | c -- image | | width -- width of image | | height -- height of image | | tmatch -- fraction of bits that must match embedded pattern for | | image to be considered authentic | | seed -- seed for random-number generator (must be same as the seed | | used during embedding) | | alpha -- multiplier for quantization matrix | | | | Return value: | | 1 if the image appears authentic, 0 otherwise | *--------------------------------------------------------------------------*/ int D_DCTQ( unsigned char *c, int width, int height, double tmatch, int seed, double alpha ) { static int sigBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* random signature that was embedded if this image was authenticated using this seed */ static int wmkBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* bit pattern actually found in image */ int numBits; /* number of bits embedded in image */ int numMatches; /* number of extracted bits that match embeddedBits */ double matchFract; /* fraction of extracted bits that match embeddedBits */ int i; /* index into bit arrays */ /* Make the psuedo-random signature. */ numBits = (height / 8) * (width / 8) * 4; GetRandomSignature( seed, sigBits, numBits ); /* Extract bits from the image. */ ExtractDCTQWmkFromImage( c, width, height, seed, alpha, wmkBits ); /* Find the fraction of watermark bits that match the signature. */ numMatches = 0; for( i = 0; i < numBits; i = i + 1 ) if( wmkBits[ i ] == sigBits[ i ] ) numMatches = numMatches + 1; matchFract = (double)numMatches / numBits; /* Decide whether watermark is authentic */ if( matchFract > tmatch ) return 1; else return 0; } /*--------------------------------------------------------------------------* | GetRandomSignature -- get a sequence of bits specified by a given seed | | | | Arguments: | | seed -- determines bit sequence | | sigBits -- where to store resulting bit pattern | | numBits -- number of bits | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetRandomSignature( int seed, int *sigBits, int numBits ) { int i; /* index into bit pattern */ srand( seed ); for( i = 0; i < numBits; i = i + 1 ) if( rand() > RAND_MAX / 2 ) sigBits[ i ] = 1; else sigBits[ i ] = 0; } /*--------------------------------------------------------------------------* | EmbedDCTQWmkInImage -- embed a given sequence of bits in an image | | | | Arguments: | | c -- image (changed in place) | | width -- width of image | | height -- height of image | | seed -- seed for random-number generator (must be same as the seed | | used during embedding) | | alpha -- multiplier for quantization matrix | | wmkBits -- bits to embed | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void EmbedDCTQWmkInImage( unsigned char *c, int width, int height, int seed, double alpha, int *wmkBits ) { double aQ[ 64 ]; /* quantization matrix */ int coefs[ 64 ]; /* assignment of coefficients to bits in a block (coefs[ 0 ... 6 ] give the indices of the 7 coefficients used for the first bit, coefs[ 7 ... 13 ] are the bits used for the second bit, etc.) */ double block[ 64 ]; /* one 8x8 block in the image */ int numBlockRows; /* number of block rows in image */ int numBlockCols; /* number of block columns in image */ int blockNum; /* block number */ int row, col; /* location in array of 8x8 blocks */ int i0; /* index of first pixel in current block */ int x, y; /* location within an 8x8 block */ /* Get the quantization matrix, scaled by alpha. */ GetDCTQMatrix( alpha, aQ ); /* Compute the number of 8x8 blocks in this image. */ numBlockRows = height / 8; numBlockCols = width / 8; /* Embed 4 bits from each block. */ for( row = 0; row < numBlockRows; row++ ) for( col = 0; col < numBlockCols; col++ ) { /* Get the assignment of coefficients to bits in this block. */ blockNum = row * numBlockCols + col; GetDCTQBitAssignments( seed, blockNum, coefs ); /* Get the pixel values of the block. */ i0 = row * 8 * width + col * 8; for( y = 0; y < 8; y++ ) for( x = 0; x < 8; x++ ) block[ y * 8 + x ] = c[ i0 + y * width + x ]; /* Embed four bits into this block. Note: wmkBits + blockNum * 4 is pointer arithmetic. The 4 bits embedded in this block are given by (wmkBits + blockNum * 4)[ 0 ... 3 ]. */ EmbedDCTQWmkInOneBlock( block, coefs, aQ, wmkBits + blockNum * 4 ); /* Copy the modified block into the image. */ for( y = 0; y < 8; y++ ) for( x = 0; x < 8; x++ ) c[ i0 + y * width + x ] = (int)block[ y * 8 + x ]; } } /*--------------------------------------------------------------------------* | EmbedDCTQWmkInOneBlock -- embed four bits in a block | | | | Arguments: | | c -- block in which to embed (in spatial domain) | | coefs -- lists of coefficients to use for the four bits | | aQ -- quantization matrix | | wmkBits -- array of four bits to embed | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void EmbedDCTQWmkInOneBlock( double *c, int *coefs, double *aQ, int *wmkBits ) { double Co[ 64 ]; /* DCT of block before embedding */ int numIterationsLeft; /* counter for limiting number of iterations to 10 */ int notDone; /* flag set to 0 when bits have been successfully embedded */ int bitWasFlipped; /* flag set to 1 when DCTQSetBit had to flip a bit found in the block */ int i; /* index into block or bit sequence */ /* Record the DCT of the original, unmodified block. This is used for comparisons inside DCTQSetBit. */ for( i = 0; i < 64; i = i + 1 ) Co[ i ] = c[ i ]; Data2DCT88( Co ); /* Embed four bits into this block, then quantize and clip to eight bit values. Repeat up to 10 times or until all the bits are correctly embedded. */ numIterationsLeft = 10; do { notDone = 0; /* Convert the block into the DCT domain, embed four bits into it, and convert it back to the spatial domain. */ Data2DCT88( c ); for( i = 0; i < 4; i = i + 1 ) { /* Note: coefs + i * 7 is pointer arithmetic. The 7 coefficients that are used for bit i are given by (coefs + i * 7)[ 0 ... 6 ]. */ bitWasFlipped = EmbedOneDCTQWmkBit( c, Co, coefs + i * 7, aQ, wmkBits[ i ] ); if( bitWasFlipped ) notDone = 1; } DCT2Data88( c ); /* Clip and round to eight bit values. */ for( i = 0; i < 64; i = i + 1 ) c[ i ] = ClipRound( c[ i ] ); /* Keep track of the number of iterations remaining */ numIterationsLeft = numIterationsLeft - 1; } while( notDone && numIterationsLeft > 0 ); } /*--------------------------------------------------------------------------* | EmbedOneDCTQWmkBit -- embed one bit in a block | | | | Arguments: | | C -- DCT of block in which to embed bit (changed in place) | | Co -- DCT of original version of block, before any bits were embedded | | coefs -- list of seven coefficients to use for this bit | | aQ -- quantization matrix | | b -- desired value of bit | | | | Return value: | | 0 if the block already decodes to the given bit value, 1 otherwise | *--------------------------------------------------------------------------*/ int EmbedOneDCTQWmkBit( double *C, double *Co, int *coefs, double *aQ, int b ) { int Ci[ 64 ]; /* multipliers for aQ that yield new coefficient values (note: in any given call to this routine, only 7 elements of this array are used) */ int be; /* value of bit represented by the coefficients listed in coefs, before embedding */ int flippedCi; /* value of a member of Ci after flipping its least-significant bit by either incrementing or decrementing */ double flipError; /* error that results from using flippedCi */ int bestJ; /* index of coefficient that leads to the smallest flipError */ int bestFlippedCi; /* value of flippedCi for coefficient bestJ */ double bestFlipError; /* smallest value of flipError */ int i; /* index into coefs */ int j; /* coefficient index (= coefs[i]) */ /* When this routine is used in E_SFSIG, the bit value (b) might be 2, meaning that we shouldn't embed anything here. So, if b==2, just return without making any changes. */ if( b == 2 ) return 0; /* Find the quantization factor multiples, Ci, that get closest to the current coefficient values. (That is, Ci[j]*aQ[j] is as close as possible to C[j], with integer Ci[j].) */ for( i = 0; i < 7; i = i + 1 ) { j = coefs[ i ]; Ci[ j ] = (int)floor( C[ j ] / aQ[ j ] + .5 ); } /* Find the current bit value. */ be = 0; for( i = 0; i < 7; i = i + 1 ) { j = coefs[ i ]; be = be ^ (Ci[ j ] & 1); } /* If this isn't the desired bit value, then flip the least-significant bit (lsb) of one of the Ci values. */ if( be != b ) { /* Find the Ci value that results in the smallest error when its lsb is flipped. */ for( i = 0; i < 7; i = i + 1 ) { /* Get the index of the i'th coefficient. */ j = coefs[ i ]; /* Find what the new value of Ci[j] would be if we flip the lsb. We'll flip the lsb by either adding or subtracting 1, depending on whether the unquantized value is greater than or less than the current quantized value, respectively. This yields the value of aQ[j]*flippedCi that is closest to Co[j]. */ if( Co[ j ] < aQ[ j ] * Ci[ j ] ) flippedCi = Ci[ j ] - 1; else flippedCi = Ci[ j ] + 1; /* Find the magnitude of the error that would result from replacing Ci[j] with flippedCi */ flipError = fabs( aQ[ j ] * flippedCi - Co[ j ] ); /* Keep track of the guy that results in the smallest error */ if( i == 0 || flipError < bestFlipError ) { bestJ = j; bestFlippedCi = flippedCi; bestFlipError = flipError; } } /* Flip the lsb of the selected Ci. */ Ci[ bestJ ] = bestFlippedCi; } /* Change the coefficient values to the selected multiples of their respective quantization step sizes. */ for( i = 0; i < 7; i = i + 1 ) { j = coefs[ i ]; C[ j ] = aQ[ j ] * Ci[ j ]; } /* If we had to flip a bit, then return 1. Otherwise, return 0. */ return be != b; } /*--------------------------------------------------------------------------* | ExtractDCTQWmkFromImage -- extract a watermark from the high-frequency | | DCT coefficients of an image's block DCT | | | | Arguments: | | c -- image | | width -- width of image | | height -- height of image | | seed -- seed for random-number generator (must be same as the seed | | used during embedding) | | alpha -- multiplier for quantization matrix | | wmkBits -- where to store watermark bits | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void ExtractDCTQWmkFromImage( unsigned char *c, int width, int height, int seed, double alpha, int *wmkBits ) { double aQ[ 64 ]; /* quantization matrix */ int coefs[ 64 ]; /* assignment of coefficients to bits in a block (coefs[ 0 ... 6 ] give the indices of the 7 coefficients used for the first bit, coefs[ 7 ... 13 ] are the bits used for the second bit, etc.) */ double block[ 64 ]; /* one 8x8 block in the image */ int numBlockRows; /* number of block rows in image */ int numBlockCols; /* number of block columns in image */ int blockNum; /* block number */ int row, col; /* location in array of 8x8 blocks */ int i0; /* index of first pixel in current block */ int x, y; /* location within an 8x8 block */ /* Get the quantization matrix, scaled by alpha. */ GetDCTQMatrix( alpha, aQ ); /* Compute the number of 8x8 blocks in this image. */ numBlockRows = height / 8; numBlockCols = width / 8; /* Extract 4 bits from each block. */ for( row = 0; row < numBlockRows; row++ ) for( col = 0; col < numBlockCols; col++ ) { /* Get the assignment of coefficients to bits in this block. */ blockNum = row * numBlockCols + col; GetDCTQBitAssignments( seed, blockNum, coefs ); /* Get the pixel values of the block. */ i0 = row * 8 * width + col * 8; for( y = 0; y < 8; y++ ) for( x = 0; x < 8; x++ ) block[ y * 8 + x ] = c[ i0 + y * width + x ]; /* Extract four bits from this block. Note: wmkBits + blockNum * 4 is pointer arithmetic. The 4 bits extracted from this block are (wmkBits + blockNum * 4)[ 0 ... 3 ]. */ ExtractDCTQWmkFromOneBlock( block, coefs, aQ, wmkBits + blockNum * 4 ); } } /*--------------------------------------------------------------------------* | ExtractDCTQWmkFromOneBlock -- extract four watermark bits from the | | high-frequency DCT coefficients of | | an 8x8 block | | | | Arguments: | | c -- block from which to extract bits (in spatial domain) | | coefs -- lists of coefficients to use for each bit | | aQ -- quantization matrix | | wmkBits -- where to store bits | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void ExtractDCTQWmkFromOneBlock( double *c, int *coefs, double *aQ, int *wmkBits ) { int i; /* index into bit sequence */ /* Convert the block into the DCT domain and extract four bits */ Data2DCT88( c ); for( i = 0; i < 4; i = i + 1 ) { /* Note: coefs + i * 7 is pointer arithmetic. The 7 coefficients that are used for bit i are given by (coefs + i * 7)[ 0 ... 6 ]. */ wmkBits[ i ] = ExtractOneDCTQWmkBit( c, coefs + i * 7, aQ ); } } /*--------------------------------------------------------------------------* | ExtractOneDCTQWmkBit -- extract one watermark bit from the | | high-frequency DCT coefficients of an 8x8 block | | | | Arguments: | | C -- DCT of block | | coefs -- list of seven coefficients to use for this bit | | aQ -- quantization matrix | | | | Return value: | | value of bit | *--------------------------------------------------------------------------*/ int ExtractOneDCTQWmkBit( double *C, int *coefs, double *aQ ) { int Ci[ 64 ]; /* multipliers for aQ that yield new coefficient values (note: in any given call to this routine, only 7 elements of this array are used) */ int b; /* value of bit represented by the coefficients listed in coefs */ int i; /* index into coefs */ int j; /* coefficient index (= coefs[i]) */ /* Find the quantization factor multiples, Ci, that get closest to the current coefficient values. (That is, Ci[j]*aQ[j] is as close as possible to C[j], with integer Ci[j].) */ for( i = 0; i < 7; i = i + 1 ) { j = coefs[ i ]; Ci[ j ] = (int)floor( C[ j ] / aQ[ j ] + .5 ); } /* Find the bit value. */ b = 0; for( i = 0; i < 7; i = i + 1 ) { j = coefs[ i ]; b = b ^ (Ci[ j ] & 1); } return b; } /*--------------------------------------------------------------------------* | GetDCTQMatrix -- get the JPEG quantization matrix, multiplied by a given | | scaling factor | | | | Arguments: | | alpha -- scaling factor | | aQ -- where to store scaled quantization matrix | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetDCTQMatrix( double alpha, double *aQ ) { /* Quantization table (from W.B.Pennebaker and J.L.Mitchell, "JPEG: Still Image Data Compression Standard", Van Nostrand Reinhold, 1993, page 37, Table 4-1) */ static int Q[ 64 ] = { 16, 11, 10, 16, 24, 40, 51, 61, 12, 12, 14, 19, 26, 58, 60, 55, 14, 13, 16, 24, 40, 57, 69, 56, 14, 17, 22, 29, 51, 87, 80, 62, 18, 22, 37, 56, 68, 109, 103, 77, 24, 35, 55, 64, 81, 104, 113, 92, 49, 64, 78, 87, 103, 121, 120, 101, 72, 92, 95, 98, 112, 100, 103, 99 }; int i; /* index into Q and aQ */ for( i = 0; i < 64; i = i + 1 ) aQ[ i ] = alpha * Q[ i ]; } /*--------------------------------------------------------------------------* | GetDCTQBitAssignments -- get the lists of coefficients to be used for | | each of the four bits in a given block | | | | Arguments: | | seed -- seed given as a key to the embedder or detector | | blockNum -- number of block | | coefs -- where to store lists of coefficients (coefs[0...6] will be | | the indices of coefficients used for the first bit, | | coefs[7...13] will be the coefficients for the second bit, | | etc.) | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetDCTQBitAssignments( int seed, int blockNum, int *coefs ) { /* Set of coefficients used for embedding */ static int embeddingCoefs[ 28 ] = { 15, 22, 23, 29, 30, 31, 36, 37, 38, 39, 43, 44, 45, 46, 47, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63 }; int i; /* index into list of coefficients */ for( i = 0; i < 28; i = i + 1 ) coefs[ i ] = embeddingCoefs[ i ]; Shuffle( coefs, 28, seed + blockNum + 1 ); } /*--------------------------------------------------------------------------* | Shuffle -- reorder a given list of integers according to a given seed | | | | Arguments: | | list -- list to be shuffled | | len -- length of list | | seed -- seed for random-number generator | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void Shuffle( int *list, int len, int seed ) { int i, j; /* indices into list */ int tmp; /* temporary variable used for swapping values in-place */ /* Seed the random number generator */ srand( seed ); /* Shuffle list by swapping each element with another element, chosen at random */ for( i = 0; i < len; i++ ) { /* Note: rand() is a C library routine that returns a random value uniformly distributed between 0 and RAND_MAX, inclusive */ j = rand() * len / (RAND_MAX + 1); tmp = list[ i ]; list[ i ] = list[ j ]; list[ j ] = tmp; } } /*--------------------------------------------------------------------------* | E_SFSIG -- embed an authentication mark using a semi-fragile signature | | and quantized-DCT embedding | | | | Arguments: | | c -- image in which to embed mark (changed in place) | | width -- width of image | | height -- height of image | | seed -- a different mark is embedded for each value of seed | | alpha -- maximum JPEG quantization factor that the mark should survive | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_SFSIG( unsigned char *c, int width, int height, int seed, double alpha ) { static int sigBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* bit pattern to embed */ static int wmkBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* pattern that was actually embedded */ int numBits; /* number of bits in signature */ int notDone; /* flag set to 0 when the extracted bits match the signature */ int numIterationsLeft; /* counter for limiting number of iterations to 10 */ int i; /* index into bit sequences */ /* Find the number of bits in a signature. */ numBits = (height / 8) * (width / 8) * 4; /* Extract a signature and embed it up to 10 times, or until all the bits extracted from the image match the signature. */ ExtractSignature( c, width, height, seed, sigBits ); numIterationsLeft = 10; do { /* Embed signature into the image. */ EmbedDCTQWmkInImage( c, width, height, seed, alpha, sigBits ); /* Check whether the embedded bits match the signature. Note: clipping and roundoff errors during the embedding process might have changed the signature, so we need to extract it again. */ ExtractSignature( c, width, height, seed, sigBits ); ExtractDCTQWmkFromImage( c, width, height, seed, alpha, wmkBits ); notDone = 0; for( i = 0; i < numBits; i = i + 1 ) if( sigBits[ i ] != 2 && wmkBits[ i ] != sigBits[ i ] ) { notDone = 1; break; } /* Keep track of the number of iterations remaining */ numIterationsLeft = numIterationsLeft - 1; } while( notDone && numIterationsLeft > 0 ); } /*--------------------------------------------------------------------------* | D_SFSIG -- determine whether or not an image is authentic using a | | semi-fragile signature embedded with DCT quantization | | | | Arguments | | c -- image | | width -- width of image | | height -- height of image | | tmatch -- fraction of bits that must match embedded pattern for | | image to be considered authentic | | seed -- seed for random-number generator (must be same as the seed | | used during embedding) | | alpha -- multiplier for quantization matrix | | | | Return value: | | 1 if the image appears authentic, 0 otherwise | *--------------------------------------------------------------------------*/ int D_SFSIG( unsigned char *c, int width, int height, double tmatch, int seed, double alpha ) { static int sigBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* signature extracted from image */ static int wmkBits[ 4 * (MAX_IMG_SIZE / 64) ]; /* bit pattern actually found in image */ int numBits; /* number of bits embedded in image */ int numMatches; /* number of extracted bits that match embeddedBits */ int numPossibleMatches; /* number of bits where the signature has a defined value (i.e. where sigBits has not been set to 2) */ double matchFract; /* = numMatches / numPossibleMatches */ int i; /* index into bit arrays */ /* Find the number of bits in a signature. */ numBits = (height / 8) * (width / 8) * 4; /* Extract the signature. */ ExtractSignature( c, width, height, seed, sigBits ); /* Extract bits from the image. */ ExtractDCTQWmkFromImage( c, width, height, seed, alpha, wmkBits ); /* Find the fraction of bits that match the embedded pattern. */ numPossibleMatches = 0; numMatches = 0; for( i = 0; i < numBits; i = i + 1 ) if( sigBits[ i ] != 2 ) { numPossibleMatches = numPossibleMatches + 1; if( wmkBits[ i ] == sigBits[ i ] ) numMatches = numMatches + 1; } matchFract = (double)numMatches / numPossibleMatches; /* Decide whether watermark is authentic */ if( matchFract > tmatch ) return 1; else return 0; } /*--------------------------------------------------------------------------* | ExtractSignature -- extract a semi-fragile signature from the | | low-frequency coefficients of an image's block DCT | | | | Arguments: | | c -- image from which to extract signature | | width -- width of image | | height -- height of image | | seed -- a different mark is embedded for each value of seed | | sigBits -- where to store resulting signature | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void ExtractSignature( unsigned char *c, int width, int height, int seed, int *sigBits ) { /* Set of coefficients used for signatures */ static int sigCoefs[ 8 ] = { 0, 1, 2, 8, 9, 10, 16, 17 }; static int blockI[ MAX_IMG_SIZE / 64 ]; /* randomized list of blocks (each element of this array is the pixel index of the first pixel in a block) */ static double block0[ 64 ]; /* first block in a pair */ static double block1[ 64 ]; /* second block in a pair */ int numBlocks; /* number of blocks in image */ int bitNum; /* counter for extracting 8 bits from each block pair */ int blockNum; /* counter for making list of blocks */ int pairNum; /* counter for looping through pairs of blocks */ int row, col; /* indices of a block */ int i0; /* index of first pixel in a block */ int x, y; /* coordinates in a block */ int i; /* index into DCT of a block */ /* Make the randomized list of blocks. */ blockNum = 0; for( row = 0; row < height / 8; row = row + 1 ) for( col = 0; col < width / 8; col = col + 1 ) { blockI[ blockNum ] = row * 8 * width + col * 8; blockNum = blockNum + 1; } numBlocks = blockNum; Shuffle( blockI, numBlocks, seed ); /* Loop through pairs of blocks, extracting eight signature bits from each pair. */ for( pairNum = 0; pairNum < numBlocks / 2; pairNum = pairNum + 1 ) { /* Get the first block and convert it to the DCT domain. */ i0 = blockI[ pairNum * 2 + 0 ]; for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) block0[ y * 8 + x ] = c[ i0 + y * width + x ]; Data2DCT88( block0 ); /* Get the second block and convert it to the DCT domain. */ i0 = blockI[ pairNum * 2 + 1 ]; for( y = 0; y < 8; y = y + 1 ) for( x = 0; x < 8; x = x + 1 ) block1[ y * 8 + x ] = c[ i0 + y * width + x ]; Data2DCT88( block1 ); /* Extract eight bits. */ for( bitNum = 0; bitNum < 8; bitNum = bitNum + 1 ) { /* Note: if the two blocks are equal at this coefficient, then the bit value is undetermined, which is indicated by setting sig to 2. */ i = sigCoefs[ bitNum ]; if( block0[ i ] < block1[ i ] ) sigBits[ pairNum * 8 + bitNum ] = 0; else if( block0[ i ] > block1[ i ] ) sigBits[ pairNum * 8 + bitNum ] = 1; else sigBits[ pairNum * 8 + bitNum ] = 2; } } } /*--------------------------------------------------------------------------* | E_PXL -- embed an authentication mark using the Yeung & Mintzer method | | | | Arguments: | | c -- image to be watermarked (changed in place) | | width -- width of image | | height -- height of image | | seed -- seed for random mapping from pixel values to bit values | | bitPat -- bit pattern to embed | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void E_PXL( unsigned char *c, int width, int height, int seed, unsigned char *bitPat ) { int pixel2BitTable[ 256 ]; /* table for mapping pixel values to bit values (generated according to seed) */ int newPixelVal0[ 256 ]; /* table of new values for pixels that should have 0's embedded (that is, if pixel i, with intensity c[i], should have a 0 embedded, then its new value should be newPixelVal0[ c[i] ]) */ int newPixelVal1[ 256 ]; /* table of new values for pixels that should have 1's embedded */ int oldPixelVal; /* value of a pixel before embedding */ double err; /* error introduced by embedding */ int x, y; /* location in image */ int bestJ; /* used to find best value for each entry in newPixelVal0 and newPixelVal1 tables */ int i, j; /* general-purpose counters */ /* Get the table mapping pixel values into bit values. */ GetPixel2BitTable( seed, pixel2BitTable ); /* Find the pixel-value substitutions required for embedding 0's and 1's. */ for( i = 0; i < 256; i = i + 1 ) { /* Find the pixel value closest to i which maps into 0. */ bestJ = -1; for( j = 0; j < 256; j = j + 1 ) if( pixel2BitTable[ j ] == 0 ) if( bestJ == -1 || abs( j - i ) < abs( bestJ - i ) ) bestJ = j; newPixelVal0[ i ] = bestJ; /* Find the pixel value closest to i which maps into 1. */ bestJ = -1; for( j = 0; j < 256; j = j + 1 ) if( pixel2BitTable[ j ] == 1 ) if( bestJ == -1 || abs( j - i ) < abs( bestJ - i ) ) bestJ = j; newPixelVal1[ i ] = bestJ; } /* Embed watermark. */ for( y = 0; y < height; y = y + 1 ) for( x = 0; x < width; x = x + 1 ) { /* Find the index of this pixel. */ i = y * width + x; /* Change the pixel's value to encode the corresponding bit of the watermark pattern, and find the error that was introduced. */ oldPixelVal = c[ i ]; if( bitPat[ i ] ) c[ i ] = newPixelVal1[ oldPixelVal ]; else c[ i ] = newPixelVal0[ oldPixelVal ]; err = oldPixelVal - c[ i ]; /* Distribute error to neighboring pixels that haven't yet been processed. */ if( x + 1 < width ) { j = y * width + (x + 1); c[ j ] = ClipRound( c[ j ] + err * 7 / 16 ); } if( x - 1 > 0 && y + 1 < height ) { j = (y + 1) * width + (x - 1); c[ j ] = ClipRound( c[ j ] + err * 3 / 16 ); } if( y + 1 < height ) { j = (y + 1) * width + x; c[ j ] = ClipRound( c[ j ] + err * 5 / 16 ); } if( x + 1 < width && y + 1 < height ) { j = (y + 1) * width + (x + 1); c[ j ] = ClipRound( c[ j ] + err * 1 / 16 ); } } } /*--------------------------------------------------------------------------* | D_PXL -- detect a pixel-based authentication mark | | | | Arguments: | | c -- image to authenticate (changed in place to the detected pattern) | | width -- width of img | | height -- height of img | | seed -- seed for random mapping from pixel values to bit values | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void D_PXL( unsigned char *c, int width, int height, int seed ) { int pixel2BitTable[ 256 ]; /* table for mapping pixel values to bit values (generated according to seed) */ int i; /* index into image */ GetPixel2BitTable( seed, pixel2BitTable ); for( i = 0; i < width * height; i++ ) c[ i ] = pixel2BitTable[ c[ i ] ] * 255; } /*--------------------------------------------------------------------------* | GetPixel2BitTable -- get a table mapping pixels into bit values | | | | Arguments: | | seed -- each seed generates a unique table | | pixel2BitTable -- where to store table | | | | Return value: | | none | *--------------------------------------------------------------------------*/ void GetPixel2BitTable( int seed, int *pixel2BitTable ) { int i; /* pixel value */ srand( seed ); for( i = 0; i < 256; i = i + 1 ) if( rand() < RAND_MAX / 2 ) pixel2BitTable[ i ] = 0; else pixel2BitTable[ i ] = 1; }