text: the present invention allows data to be embedded into the low - order bits of host data with less error than would be caused by replacing the bits with either the bits or a code representing the bits taken from the auxiliary data . this is made possible because of the technique of selecting a block module in the host data , and representing the embedded bits by an offset from the center of the block module . in the present invention , the auxiliary data are encrypted or compressed before the modular error embedding process is begun , in order to randomize the auxiliary bits , and to minimize the effect of the auxiliary data on the noise in the low - order bits of the host data . after this is accomplished , the correlation of the host and auxiliary data values are used to reduce further the error caused by applying the method of the current invention . the auxiliary data placed into the low - order host image data bits are made to correlate with the host image data by permuting the order in which the host data pixels are sampled for embedding , reducing further the noise introduced into the host data . this permutation is different than permuting the order of pixel selection from the host image , because it applies to sequences of pixels , after the pixels are drawn from the image . this process is accomplished concurrently with other steps of the method according to the present invention . embedding information with modular error embedding affects the response of the host data to standard loss - less compression algorithms . data added in the low - order bits , even when correlated with the host image noise , increase the image entropy . however , the compressed size of the host image after the method of the present invention adds auxiliary data is less than the sum of the separate compressed sizes of the original host and the auxiliary data . therefore the present invention provides a means for increasing to a large amount ( high bit - rate coding ) the information that can be conveyed in digital data containing intrinsic noise . fig1 illustrates some examples of the process of the present invention . vertical line 1 - 1 represents the scale for numerical values . for n = 5 bit embedding , the auxiliary data samples range in value from 0 to 31 , inclusive . the original host data values fall anywhere on the line 1 - 1 . numbers by the short tick marks on the right side of vertical line 1 - 1 represent the block module values in the original host data . numbers on the left side of vertical line 1 - 1 represent host data values used for embedding . the new host data values , after embedding , are shown in parentheses on the left side of vertical line 1 - 1 . the values embedded , in the three examples following are shown on the right side of the vertical line 1 - 1 . for the five low - order bits in this example , n = 5 , and the embedding block , or module , size is 2 n = 32 . the invention partitions the host data values into blocks , or modules 32 units in size . fig1 shows modules centered at 0 , 32 , 64 , and 128 units . assume the auxiliary data value is 6 , and the host pixel value is 29 . replacing the five low - order host value bits with the auxiliary value , as in bit - slicing methods , introduces an error of 23 . again referring to fig1 the invention embeds the auxiliary data value 6 as an offset 6 units above the block centered at 32 . the new host data value is 38 , and the error is 9 . to recover the auxiliary value , the invention calculates the remainder of the new host data value , 38 , modulo the block size , 32 . the remainder is the auxiliary value , 6 . in this case , the invention changes the host block index , which is the sixth bit , from 0 ( the block starting at 0 ) to 1 ( the block starting at 32 ). in a second example , for which the auxiliary data value is 31 , and the host value is 33 , the difference between the auxiliary value and the host value is 2 . embedding with bit slicing would set the new host data value to 63 , and introduce an error of 30 . the invention sets the new host value to 31 , so the error is 2 . to recover the auxiliary value , the invention calculates the remainder of the new host data value , 31 , modulo the block size , 32 . the remainder is the auxiliary value , 31 . in this case , the invention changed the block index , which is the sixth bit , from 1 ( the block starting at 32 ) to 0 ( the block starting at 0 ). in yet a third example , for which the auxiliary data value is 16 , and the host value is 33 , the difference between the auxiliary and host values is 17 . for this case , the invention sets the new host value to 48 , so the error is 16 . the auxiliary value is the remainder of the new host data value modulo the block size , 32 . the remainder is 16 . in this case , the host data value block index is not changed and the invention performs identical to bit slicing . with modular error embedding , the maximum error is one - half the block size . with bit - slice methods , the maximum error equals the block size . changing the block index , i . e ., the ( n + 1 ) th bit , reduces the embedding error by bringing the host and auxiliary bits closer in value . in the third example , the block index is not changed . in the first and second examples , the invention changes the block index , the sixth bit , when the lowest five bits are replaced . the method of the present invention proceeds in three steps . first , a host data value , h , is drawn from the host image and represented by a block index , x 1 and an offset value , x 2 , according to values of the block index and offset are found from truncated integer division and the remaindering operation : in the second step , n - bits of auxiliary data are drawn and the auxiliary value , y , is used to calculate a new host data value , h &# 39 ;. the algorithm for finding h &# 39 ; is : in the third step , the host data value h is replaced with h &# 39 ;. the algorithm in equations . 3a - c constrains h &# 39 ;, the new host data value , to less than 2 n - 1 , or a factor of 2 less than the error range possible for bit - slicing n - bits of the data value . hence , for the same degradation of the host data values , the invention embeds double the amount of auxiliary information . a single step is required to recover the data value y , from its host data value , h &# 39 ;. to extract an embedded value , the invention calculates the remainder of the host value : fig2 is a reproduction in grey scale of a 24 - bit truecolor photograph having a noise level of one or two bits at most . comparing the original image and the image after embedding using 3 bits of the host data shows little evidence of the noise added by the invention . the lower image in fig2 contains 50 % auxiliary data , yet the invention preserves the appearance of the original image . fig3 and 4 show the histogram of the green color component , for the images in fig2 . after applying the invention , the histogram in fig4 differs from the original , which is shown in fig3 . however , the invention preserves the features of the histogram , and the image appears substantially unchanged from the original . reference is now directed to the left image in fig5 a reproduction in grey scale of a 24 - bit truecolor composite image . the composite image is constructed by manipulating separate photographs of the individuals , taken in a studio , and of the chicago skyline . the image was manipulated digitally by a graphics artist to shade the sky , and to lighten a vertical strip on the right side , for the purpose of adding caption information . composite images are used commonly for illustrations in publications . owing to the composition process , the noise level varies widely in a composite image . the histogram of the green component of the left image of fig5 is shown in fig6 and illustrates the large variations caused by manipulating images in the composition process . the right image in fig5 shows the result of applying the invention to embed the five lowest bits of the pixels in the composite image . the noise level is raised in some parts , notably in the sky background . the histogram of the right image of fig5 is shown in fig7 and is smooth , in comparison with the original , shown in fig6 . after embedding data , the histogram is consistent in appearance with a photographic source such as is illustrated in fig2 . for n = 5 , five bits per pixel are embedded into each pixel , in each of the three color planes of the 24 - bit truecolor - format image . in the right image in fig5 of the 24 bits , or 62 . 5 % of the host image size , contain auxiliary information not related to the pixel values . fig8 is a reproduction in greyscale images of a high - quality 24 - bit truecolor photograph of a detailed subject , rocks in a cobblestone pavement . the subject detail provides variations in the image that mimic the effect of noise , permitting a more aggressive application of the method of the present invention . the lower image in fig8 shows the result of applying the invention to the lowest 6 bits of the original image . the lower image contains 75 % auxiliary data . fig9 and 10 show the histogram of the green color component , for the images shown in fig8 . after applying the method of the present invention , the histogram in fig1 differs markedly from the original , shown in fig9 . however , in spite of the histogram differences , the detail in the original image supports the addition of considerable noise to the photograph . the method according to the invention succeeds in replacing the majority of the image content with auxiliary data . the invention divides the host value data - space into blocks of size 2 n , where n is the number of host data bits used to encode auxiliary data . the data values are modified modulo the blocksize . as previously discussed , the replacement bits affect the host data values by less than the amount of comparable high bit - rate coding using bit - slicing methods . table 1 compares , for comparable error , the size of the auxiliary data for images embedded with the invention and a bit - slice method . the right column in table 1 shows the improvement in size given by the invention . table 1______________________________________me versus bit - slice algorithmsno . of bits , n me size (%) bit - slice size (%) me improvement (%) ______________________________________1 12 . 5 12 . 5 02 25 . 0 12 . 5 12 . 53 33 . 3 25 . 0 8 . 34 50 . 0 33 . 3 16 . 75 62 . 5 50 . 0 12 . 56 75 . 0 62 . 5 12 . 5______________________________________ referring to table 1 , for n = 1 , the invention and bit - slice algorithms perform identically . however , for more than one embedding bit ( n & gt ; 1 ), the invention exceeds bit - slicing for the amount of information embedded . in particular , n = 6 is useful with the method of the present invention ( as shown in fig8 ), while it is not useful for bit - slicing . embedding with the method of the present invention differs from bit - slicing in the treatment of the next highest bit , in the n low - order bits of the host data sample . in bit - slicing , n bits are replaced with n bits from the auxiliary data . in the method according to the present invention , if the bits are numbered from the least significant by k = 1 , 2 , . . . , n - 1 , n , then the ( n + 1 ) th bit in the new host data pixel depends only the value of the auxiliary data bit . in the method of the present invention , the ( n + 1 ) th bit of the new host pixel depends on the difference between a quantity , x 2 , and the auxiliary data , as seen in the relations in equation 3a . the error introduced by embedding with the invention is thus reduced to o ( n - 1 ), in comparison with bit - slice methods having error of o ( n ). a feature of the present invention reduces further the error caused by replacing n bits in the host data . as taught above , the error committed by applying the invention is less than for bit - slice embedding , because the difference between the host image pixel value and the embedded data value is reduced to one - half the modular block size . further error reduction thus is possible , by increasing the correlation of the auxiliary and host data . the invention embeds bits drawn from the auxiliary data into the host data by replacing the value h with h &# 39 ; ( equation 3 ). thus , the error is the difference between these two values . assume a number , m + 1 , of host values can be drawn randomly from the host data . the m + 1 values in the sample are related to one another statistically through the host data histogram . the method according to the present invention takes m samples , each of bit - size n , from the auxiliary data . the m values taken from the auxiliary data sample are related to one another according to the statistical properties of the auxiliary data , and are assumed to be uniformly random , if encryption or loss - less compression is performed prior to processing the auxiliary data . in this procedure , the m data values are embedded sequentially into a permutation of m host data values , using the procedure as taught above to embed each value . the permutation is selected to minimize the total error of the m values embedded into the host image pixel offsets . the ( m + 1 ) th value drawn from the image data is used to contain an index for the permutation used for the embedding . the permutation index is embedded along with the auxiliary data , as taught above . permuting the host - data values to minimize error reduces further the degradation of the host values , at the expense of complicating the embedding algorithm , and of reducing the embedding space by the amount required to contain the permutation indices . the extraction sequence requires that the m + 1 values be retrieved , and the permutation index decoded to recover the particular permutation used for embedding the sequence of m data values . extracting the embedded data requires drawing the identical sequence of host data values . the permutation index is recovered from the first of the m + 1 pixels with the process of the present invention as taught in equation 4 above . the index can be stored in any of the m + 1 pixels , and the remaining m values permuted , according to the particular implementation of the algorithm . the remaining m host values are ordered according to the permutation generated from the index , and the auxiliary data are recovered by using the process of the invention on each , in sequence . the reduction in error given by permuting the host - image pixel samples is estimated empirically , for real image data . the image histogram provides the information required to estimate the error made by embedding , including the error committed by embedding a permutation index and data . the histogram is the probability density for the value of a pixel drawn randomly from the host image . the present invention modifies a pixel value according to the value of the auxiliary data . to estimate the error , we first consider the random auxiliary data . it is incorrect to estimate error by considering random pixel - offset values for the host data , because the pixel offsets follow the histogram probability density . a pixel - value offset , x 2 ( equation 3 ), derives from the host image value modulo the block size . because the invention uses more than the least significant bit , the offset values correlate with the host data . for most host data , as one considers successively lower bit - levels , the pixel - offset values transition from correlation with the image to a random distribution . generally , the pixel - offset values correlate with the host data for block sizes much above n = 4 , or n = 2 bits . integrating the normalized probability density function gives the probability distribution function . numbers drawn from a uniform generator enter the distribution function table as a probability , and sample pixel values according to their distribution in the image . to estimate the error of the permutation process , the pixel - offset value samples drawn from an image probability distribution are combined with a sequence of uniformly random values representing an auxiliary data stream . the process determines the permutation of the pixel - offset values giving the least total error for each sequence of auxiliary data values . a minimization algorithm or an exhaustive search determines the particular permutation sequence . to find the permutation giving minimum error , one would compute an error matrix e kl for k , l = 1 , 2 , 3 , . . . , m combinations of the host and auxiliary data samples . for m permutations , one draws the number m pixel values from the host image , and another m data values from the auxiliary information to be embedded . the matrix is defined by where x 2k is a host data pixel - offset value and y l is an auxiliary value to be embedded . summing the error matrix rows to calculate the total error for each auxiliary value is given by : ## equ1 ## consider an example to demonstrate operation of this algorithm . take m = 5 , n = 7 , and assume values for x 2k = 12 , 19 , 36 , 55 , 63 ; and for y l = 50 , 12 , 48 , 32 , 1 . differencing the values , the error matrix and row errors are : ______________________________________l 1 2 3 4 5 row error______________________________________1 38 31 14 5 13 1012 0 7 24 43 51 1253 36 29 12 7 15 994 20 13 4 23 31 915 11 18 35 54 62 180______________________________________ the permutations are found by processing the row error sums , e l ( l = 1 , 2 , 3 , . . . , m ), in decreasing order of magnitude . the first auxiliary value y l chosen is paired with the pixel - offset value of x 2k that gives the minimum error , e kl . thus , the first y l value to be processed is l = 5 , because the row error ( 180 ) is the largest . the minimum error in the row occurs for k = 1 . the next smallest row error is 125 , and it corresponds to l = 2 . the minimum error in the row occurs for k = 1 , but this value was selected previously . thus , the next smallest error occurs for k = 2 . continuing the selection mines the permutation sequence : ______________________________________l 1 2 3 4 5______________________________________k 4 2 3 5 1e . sub . kl 5 7 12 31 11______________________________________ the total error for the permutation is 66 , compared with 119 , the average of the row errors for the matrix . the error per value embedded is 66 / 5 ≈ 13 . the average error per value for the average of the row errors above is 24 . for this example , the algorithm gives about 55 % error reduction . an alternate method of finding the permutation giving the minimum error would be by an exhaustive search of all possibilities . numerical tests show the algorithm taught herein provides results which differ little from an exhaustive search result . the average error of applying the invention to the images in fig2 , and 8 with random auxiliary samples is given in table 2 as a &# 34 ; bit equivalent error .&# 34 ; the bit - equivalent error is the base - two logarithm of the average error in the pixel - offset value . the bit equivalent error is interpreted as the number of bits representing the error value . for bit - slice methods , with n bits , the average bit - equivalent error equals the error of the present invention for n + 1 bits . table 2 gives results from the method of the present invention without including the permutation , for 10 4 trials . table 2______________________________________me method bit equivalent errorsno . of bits balloons . bmp final2 . bmp rocks . bmp______________________________________7 4 . 74 4 . 79 4 . 776 3 . 77 3 . 78 3 . 755 2 . 79 2 . 79 2 . 794 1 . 84 1 . 84 1 . 833 0 . 88 0 . 89 0 . 92______________________________________ the bit - equivalent errors in table 2 show the substantial gain of about one bit that the present invention offers in comparison with conventional bit - sliced steganography . for example , for embedding with seven bits of the image pixel , the present invention gives errors equivalent to about five bits . for three bits , the invention error is about one bit . permuting the pixel values reduces the embedding error even more . the algorithm taught above was used to determine a permutation that reduces the total error for the embedded data - values , and the index for the permutation was embedded separately . table 3 gives results for permuting the host data values . the image used table 3 is the final2 . bmp picture , shown in fig5 . table 3______________________________________permuted process bit equivalent errorsembedding number of permutationsbits 5 4 3 2 1______________________________________7 4 . 31 4 . 60 4 . 89 5 . 17 4 . 796 n / a 3 . 52 3 . 86 4 . 15 3 . 785 n / a 2 . 47 2 . 81 3 . 15 2 . 794 n / a n / a 1 . 74 2 . 11 1 . 843 n / a n / a 0 . 72 1 . 04 0 . 89______________________________________ in table 3 , the &# 34 ; n / a &# 34 ; entries are permutations for which the embedding bit level does not permit embedding the permutation index . for example , for 5 permutations , there are 120 possible indices , but using six bits in a pixel permits storing no values larger than 2 6 - 1 = 63 . thus , the number of permutations usable depends on the number of image pixel bits used for embedding . in table 3 , the column for one permutation indicates the result of applying the present invention without the permutation process ( table 2 ). the greatest amount of information is embedded using seven bits . the error for five levels of permutation is 4 . 31 bits compared with 4 . 79 bits with no permutations , an improvement of 10 %. for the lowest number of embedding bits tested ( 3 ), the error with three permutations is 0 . 72 bits compared with 0 . 89 bits for no permutations , an improvement of 19 %. the improvement in error is largest for embedding with few image data - value bits , and for three permutations . the average error in table 3 is larger than the unpermuted ( m = 1 ) value for some permutations . for permutations of two and three , for five , six , and seven - bit embedding , the error is large because the unpermuted storage of the permutation index introduces an error greater than the error reduction by permuting . the necessity of embedding a permutation index increases the average error and negates the effect of permuting a small number of values . even though the permutation index increases the error in table 3 , only a fraction , 1 /( m + 1 ), of the host image pixels suffer the larger error . the majority of the host pixels have smaller errors , owing to the use of permutation process . the visual appearance of the image is measured better by neglecting the permutation index error contributions in table 3 . table 4 gives the errors for the same example as in table 3 , without the error contribution of the permutation index . the errors in table 4 are calculated by an exhaustive - search algorithm to determine the best permutation . table 4______________________________________permuted process errors without index errorno . of bits 5 4 3 2 1______________________________________7 3 . 64 3 . 74 3 . 82 3 . 88 4 . 796 n / a 2 . 74 2 . 83 2 . 88 3 . 785 n / a 1 . 78 1 . 85 1 . 90 2 . 794 n / a n / a 0 . 94 0 . 94 1 . 843 n / a n / a 0 . 06 0 . 07 0 . 89______________________________________ for seven - bit embedding , with three and two permutations , the errors calculated without including the effect of embedding the permutation index are 3 . 82 and 3 . 88 , respectively , compared with 4 . 89 and 5 . 17 ( table 3 ), when the permutation index error is included . thus , by permuting seven - bit embedding five times , the perceived , or visible - appearance , error reduces by more than one bit . in this case , 1 / 8 of the pixels having the index values have error ( 4 . 31 bits , table 3 ) larger than the average error in table 4 . using permutations of two and three , for 3 - bit embedding , the error in the perceived image is negligible . moreover , the error from embedding the permutation indices is less than one - bit , for the 1 / 4 of the image pixels containing permutation indices ( table 3 ). thus , it is possible to embed data using the lowest three bits of the host image with perceived , or visual - appearance errors of less than one bit . it is now helpful to refer to fig1 , wherein a partial listing of computer code in the c ++ language is printed . the code listed in fig1 demonstrates the method of embedding auxiliary bits according to the method of the invention . a class member function embedmoderror () performs the embedding of auxiliary data into the host image data value . the host value is passed to the function as a calling argument , in line 10 , as a pointer to the host image value , named by the variable pixel . a second calling argument is a pointer to an unsigned long variable named maxval holding the count of the number of bits embedded . lines 17 and 18 in fig1 calculate the block index , x 1 and the pixel offset value , x 2 . in line 20 , the auxiliary data value is drawn from the bit stream using a function named getbits (). the number of bits sliced is passed to the function with the class member variable named no -- bits -- sliced . lines 22 through 27 implement the algorithm to calculate the replacement value for the host data value . line 4 , fig1 ( page 2 ) replaces the original host data value with the new value containing the auxiliary data . line 5 increments the counter by the number of bits sliced in the host pixel value . referring now to fig1 , the class member function named extractslicedbits () that extracts the embedded data with the invention is shown . line 12 defines a class member function to extract information from the host data value . pointers to the host value and to a counter holding the number of bits extracted are passed as calling arguments . the variable named pixel points to the host data value , and the variable named maxval points to the counter . the extracted value is calculated in line 21 by remaindering the host pixel value with the size of the embedding block , stored in the member structure element named data -- header . mod -- block -- size . in line 24 , the auxiliary value extracted from the host pixel value is placed into the auxiliary bit stream with a routine named putbits (). the member structure element data -- header . no -- bits -- sliced is passed to specify the number of bits to be inserted into the auxiliary data stream . the counter is incremented in line 27 , and the routine returns a flag indicating success or failure in line 28 . as with the data embedding process disclosed in the copending application , the invention protects the auxiliary embedded data with a key . the key is used to generate the sequence of pixels used to embed the auxiliary data values . without the key , an unauthorized user cannot extract the embedded information . the security of the embedded data require protection of the key . one way of protecting the key is to encrypt it using public - key , or another encryption process . the present invention permits an encrypted key to be placed into the host image file , preventing extraction by unauthorized persons . the foregoing description of the preferred embodiment of the invention has been presented for purposes of illustration and description . it is not intended to be exhaustive or to limit the invention to the precise form disclosed , and obviously many modifications and variations are possible in light of the above teaching . the embodiments were chosen and described in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the art to best utilize the invention in various embodiments , and with various modifications as are suited to the particular use contemplated . it is intended that the scope of the invention be defined by the claims appended hereto .