KR101141897B1 - Encoding/Decoding Method for Data Hiding And Encoder/Decoder using the method - Google Patents

Abstract

The present invention relates to encoding and decoding for lossless data concealment, and more particularly, to encoding and decoding for lossless data concealment using LZW compression, which is the best known lossless compression method. The present invention uses a method of updating a dictionary of LZW. If the length of the updated string is the same as the parity of the data to be concealed, it is updated as it is. Update code, such as code that exists in existing dictionaries, to hide data by making the code itself redundant.

Data concealment, lossless compression, Lempel-Ziv-Welch (LZW) compression

Description

Encoding / Decoding Method for Data Hiding And Encoder / Decoder using the method}             

1 is a functional block diagram of a typical Lempel-Ziv-Welch (LZW) encoder.

2 is an operation flowchart of a general LZW encoding.

3 is a functional block diagram of a typical LZW decoder.

4 is an operational flowchart of general LZW decryption.

5 is a functional block diagram of an encoder for hiding data according to a preferred embodiment of the present invention.

6 is an operational flowchart of encoding for data concealment according to a preferred embodiment of the present invention.

7 is a flowchart illustrating the key operations of encoding for data concealment according to a preferred embodiment of the present invention.

8 is a functional block diagram of a decoder for extracting hidden data according to a preferred embodiment of the present invention.                 

9 is an operational flowchart of decryption for extracting hidden data according to a preferred embodiment of the present invention.

10 is a flowchart illustrating a key operation of decryption for extracting hidden data according to an exemplary embodiment of the present invention.

<Description of the symbols for the main parts of the drawings>

10,100: encoder's input buffer 15,150: decoder's input buffer

20,200: control unit of the encoder 25,250: control unit of the decoder

30,300: storage unit of the encoder 30A, 300A: prefix storage area

30B, 300B: Suffix storage area 35,350: Storage part of decoder

35A, 350A: Suffix storage area 35B, 350B: Previous code storage area

35C, 350C: New code storage area 40,400: Dictionary of encoder

50,500: Encoder output buffer 600: Message concealment unit

650: message decoder

The present invention relates to encoding and decoding for concealing data, and more particularly, it is possible to conceal and recover data without incurring loss or distortion of original data and to compress data simultaneously with such concealment. The present invention relates to an encoding / decoding method for data concealment and a decoder / decoder using the same.

In general, a method known as data concealment can be roughly divided into steganography and watermarking. The former differs only in that purpose because it does not expose the data to third parties even if the data is concealed, and the latter believes that the data is known to be concealed and has a philosophy that it must be robust to potential third party attacks. For this reason, the algorithm for concealment is quite similar. Data hiding is concealing the user's message to the original data, which adds some distortion to the original data as additional messages are added to the original. The original data is generally compressed because of its large file size. For that reason, the algorithm using compression is more efficient than the method using the original.

Although there are various compression methods, a compression method that is widely used at present is Lempel-Ziv-Welch (hereinafter, abbreviated as "LZW") compression method. LZW is currently used for modem communications CCITT V.42 Vis Standard, GIF and TIFF video format compression modules, and Adobe's pdf format compression.

LZW's compression scheme is an adaptive lossless data compression scheme that can directly code each character stream as it is input, without having to examine the probability distribution over the entire data to be compressed. In addition, it is a dictionary-based compression scheme in which the same code table is dynamically generated by an encoder and a decoder and does not require a separate transmission.                         

The main terms used in LZW compression can be summarized as follows:

-Character: A basic processing unit of data to be compressed. It includes audio, text, and video, and is not limited to the letters such as the alphabet itself. For example, in an English document file, each alphabet or a predetermined number of sets may be referred to as characters, and in the image, each pixel or a predetermined number of pixels may be considered as characters.

String: A string of one or more characters.

Character stream: A sequence of characters given to an input, meaning the entire input data.

Code: Also known as an index, each string is assigned a string and is the output of the LZW encoder for compressed data.

Dictionary: Also called a code table, a code (or index) is assigned to each string in the dictionary.

Entry: Each string in the dictionary and code that refers to that string.

-Hidden code stream: Compressed data, including hidden messages, which is a series of codes that are output after compression.

1 is a functional block diagram of a general LZW encoder, and FIG. 2 illustrates an operation flow of a general LZW encoding.                         

A general LZW encoder and LZW encoding will be described with reference to FIGS. 1 and 2.

First, the controller 20 performs a dictionary 40 initialization process defining a code for each character for all characters that may exist in the input character stream (step S100), and then input buffer (for compression). A character is read from the input character stream inputted at 10) and stored as a prefix in the prefix storage area 30A of the storage unit 30 (step S101). Subsequently, the controller 20 reads the next character from the input character stream stored in the input buffer 10 and stores it as a suffix in the suffix storage area 30B of the storage unit 30 (step S102).

Thereafter, the control unit 20 checks whether there is a string matching the prefix and suffix read and stored in the steps S101 and S102 matches an entry in the dictionary 40 (step S103).

As a result of checking in step S103, if there is a match, the controller 20 stores the current character string (prefix + suffix) as a prefix in the prefix storage area 30A of the storage unit 30 (step S104). . Here, the pre-stored prefix is updated and stored in the prefix storage area 30A as a new prefix (that is, an existing prefix + suffix) in step S104.

Thereafter, the control of the control unit 20 proceeds to step S109, and the control unit 20 checks whether there are any more characters to read from the input character stream which is input and stored in the input buffer 10.                         

If it is confirmed in the step S109 that the character to be read remains, the control of the control unit 20 returns to the above-described S102, and reads the next character from the input character stream which is input and stored in the input buffer 10 and the The control process from step S102 is repeated.

If it is determined in step S109 that there are no characters left to read, the control unit 20 outputs a code corresponding to the prefix stored in the prefix storage area 30A of the storage unit 30 remaining at the end of the dictionary 40. Is found and output as an output signal through the output buffer 50 (step S110), and all encoding control ends.

On the other hand, in the above step S103, when it is confirmed that the string matching the string of the sum of the current prefix and the suffix does not exist in the dictionary 40, the controller 20 stores the prefix of the current storage unit 30 The code corresponding to the prefix stored in the area 30A is found in the dictionary 40 and output as an output signal through the output buffer 50 (step S106).

Thereafter, the control unit 20 adds the prefix and suffix currently stored in the prefix storage area 30A and the suffix storage area 30B of the storage unit 30, respectively, and adds a new entry into the dictionary 40. In addition, the dictionary 40 is updated (step S107).

Subsequently, the controller 20 updates and stores the value read from the surface storage area 30B as a prefix in the prefix storage area 30A of the storage unit 30 to be used for the next compression (step S108).                         

Thereafter, the control of the control unit 20 proceeds to step S109 described above to check whether there are any more characters to read from the input character stream that is input and stored in the input buffer 10. If it is confirmed in the step S109 that the character to be read remains, the control of the control unit 20 returns to the above-described S102, and reads the next character from the input character stream which is input and stored in the input buffer 10 and the The control process from step S102 is repeated. On the other hand, if it is determined in step S109 that no character remains to be read, the controller 20 corresponds to the prefix (ie, suffix) updated and stored in the prefix storage area 30A of the storage unit 30 in step S108. The code 40 is searched in the dictionary 40 and output through the output buffer 50 (step S110), and all encoding control ends.

3 is a functional block diagram of a general LZW decoder, and FIG. 4 illustrates an operation flow of general LZW decoding.

A general LZW decoder and LZW decoding will be described with reference to FIGS. 3 and 4.

First, the controller 25 performs a dictionary 45 initialization process defining a code for each character for all characters that may exist in the encoded character stream (step S300), and then inputs transmitted from the encoder. The signal stream is stored in the input buffer 15, one code is read therefrom, and stored in the previous code storage area 35B of the storage unit 35 as OCODE (old code) (step S301). The corresponding string is found in the dictionary 45 and output through the output buffer 55 (step S302).

For example, the controller 25 reads the next code from the input buffer 15 and stores it as NCODE (new code) in the new code storage area 35C of the storage unit 35 (step S303).

Then, the control unit 25 checks whether the NCODE exists in the dictionary 45 (step S304), and if present, reads the character string corresponding to the NCODE from the dictionary 45, and indicates the string region STRING of the output buffer 55. (Step S307), the control of the controller 25 proceeds to step S308 below. Here, the string storage area 55A is used as a temporary buffer.

Thereafter, in step S308, the controller 25 controls to output the STRING stored in the string storage area 55A (step S308), and the controller 25 sets the first character of the output STRING as the suffix. The data is stored in the suffix storage area 35A of the storage unit 35 (step S309).

Subsequently, the controller 25 adds the dictionary 45 by adding the character string corresponding to the OCODE stored in the previous code storage area 35B and the suffix stored in the suffix storage area 35A to the dictionary 45. Update (step S310).

When the dictionary update process is completed, the controller 25 updates and stores the value read from the new code storage area 35C as an OCODE in the previous code storage area 35B of the storage unit 35 for the next process (step S312). ).

Thereafter, the controller 25 checks whether there are any more codes to be read from the input buffer 15 (step S313), and if the code remains, repeats the process from step S303 again. On the other hand, if it is determined in step S313 that no more code remains, the control of all decoding processes ends.

On the other hand, if the NCODE does not exist in the dictionary in step S304 described above, it means that the addition to the dictionary 45 is later than the code to be encoded in a special case. In this case, the controller 25 reads a character string corresponding to the OCODE stored in the previous code storage area 35B of the storage unit 35 from the dictionary and sets it as a STRING in the string storage area 55A of the output buffer 55. (Step S305), the STRING stored in the string storage area 55A and the sum of the first character of the STRING and the sum are updated and stored as a new STRING in the string storage area 55A of the output buffer 55 ( Step S306).

Thereafter, the controller 25 controls to output the STRING stored in the string storage area 55A (step S308), and performs the processes of steps S309 to S313 as described above.

Meanwhile, various data concealment methods, such as watermark and steganography, have been proposed. As described above, they perform data concealment by modifying original data before signal processing such as compression. It has the disadvantage of causing distortion of the original information. Such existing methods include a method of hiding data in a GIF image using LZW compression and a method of hiding data using a palette, which is a definition of color information. These methods include Ogihara, T. and Kaneda, Y., "Data Embedding into Compressed Data of GIF Images," Proceedings of Pacific Rim Workshop on Digital Steganography 2003, and Friedrich, J., and Du Dui, "A new steganographic methods for palette-based images, "IS & T PICS Conference, pp. 285-389, 1999."

The LZW compression method is a method of matching the parity of the code with the parity of the data to be concealed in a general LZW process. To compress the given data using the LZW method, read characters one by one until the longest string matches the entry in the dictionary from the input character stream, as described above, and output the code corresponding to the read string. do. At this time, if the parity of the code matches the parity of the data to be concealed, the original code is output as it is, otherwise the last character of the read string is replaced with the most similar character. If there is an entry in the dictionary that matches the string that changed the last character and the parity of the corresponding code matches the parity of the data to be hidden, the corresponding code is displayed. However, if there is no entry that matches the changed string, the code of the entry that matches the string from which the last string was removed is checked to see if the parity of the code matches the parity of the data to be concealed. If the parity matches each other, the corresponding code is printed. If not, the last character is changed to the most similar character and the process is repeated until the length of the string is 3. If the length of the string is less than 3, the data is not concealed. For example, if the data to be concealed is' 0 ', the string read is '01 01 33 11 02' and the code of the corresponding entry is' 130 ', the parity of the message to be concealed and the code to be outputted. Since the parity matches, the code '130' is output as is. However, if the code of the entry that matches the read string does not match the parity of the data to be hidden with '131', the last character of the read string, '02', is replaced with the most similar character. If the most similar character to '02' is '44', the existing string '01 01 33 11 02 'is changed to '01 01 33 11 44'. In this way, there is an entry in the dictionary that matches the changed string. If the parity of the code has the desired value, the corresponding code is output. Otherwise, the same process is performed for '01 01 33 11 'with the last character removed. Repeat. However, such a method causes a distortion of the original input signal due to the forced deformation of the input character.

The method of hiding data using the palette is as follows. After pairing with the most similar color for all the colors in the palette, different parity is given to the two colors in each pair. If the parity of the data to be concealed and the parity of the input character are the same, the input character is used as it is. Otherwise, the input character is changed to a color paired with the previous pair so that it has the color most similar to the input character and has a different parity. For example, if the color of '120' and '30' of the palette are the most similar, the pairs should be paired with each other.The parity of '0' for '120' and '1' for '30' Grant. If the input character value is '120' and the hidden data is '0', the input character is used as it is. If the data to be hidden is '1', it has the same parity and the color most similar to the original input character. Change the input character to '30'. However, when using this method, the receiver should have the same color as the table used by the sender, paired with each other and having the same parity with each color. In addition, similar to the method using the LZW compression method described above, the distortion of the original image due to the deformation of the color information has a disadvantage.

Currently, there is no example of applying a compression scheme such as LZW itself to data hiding technology because there is little redundancy of data after compression with LZW. For that reason, most existing algorithms perform data hiding on the data before compression, resulting in data distortion.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and an object of the present invention is to provide an encoding / decoder and an encoding / decoding method capable of concealing a desired message at the same time with compression without loss or distortion of data. The purpose is to.

Another object of the present invention is to provide a hidden message extraction method for extracting a hidden message by the method proposed by the present invention.

Each configuration of the present invention consists of a data concealment encoder and a data concealment decoder. The present invention changes the length of the string to match the parity of the message data to be concealed. The length of a string is the number of characters that make up a given string, and the addition of a new string as an entry in the dictionary is called an update. Also, varying the length of a string means adding it to the dictionary by reducing the number of characters that make up the string, which is defined as a forced update. Because LZW is a string that has been previously updated so that the string in the dictionary is the prefix of the string to be updated, the same string will always be present in the dictionary when the string is shortened and updated. Therefore, the forced update does not cause a problem at the time of decryption due to the characteristics of the LZW. That is, the present invention is completely compatible with the existing LZW, and is a method of concealing data by adding redundancy to the compression method itself by forcibly updating. In this case, the code stream coded by concealing the data does not conceal the data and generally increases the file size compared to the coded code stream, but the degree is small.

Hereinafter, with reference to the accompanying drawings will be described in detail a preferred embodiment of the present invention.

First, a coding method for data concealment and an encoder thereof according to a preferred embodiment of the present invention will be described in detail with reference to FIGS. 5 to 7.

5 is a functional block diagram of an encoder for data concealment according to a preferred embodiment of the present invention, FIG. 6 is an operation flowchart of encoding for data concealment according to a preferred embodiment of the present invention, and FIG. A flowchart of key operations of encoding for data concealment according to a preferred embodiment.

In FIG. 5, the input buffer 100, the dictionary 400, and the output buffer 500 perform substantially the same operations as the input buffer 10, the dictionary 40, and the output buffer 50 of FIG. 1. However, in an exemplary embodiment of the present invention, an input buffer 120 in which a hidden message that a user wants to conceal is input and temporarily stored is added, and a message concealment unit 600 for concealing the hidden message is added, and the storage unit 300 is provided. Prefix length value storage area 300C for storing the length value of the prefix in the storage area; and Residual hidden message bit amount storage area for storing the bit amount of the unhidden remaining hidden message stored in the input buffer 120 ( 300D) is added, and the control flow of the controller 200 is changed from that of FIG. 1.

In FIG. 6, compared with FIG. 2, step S200 for message concealment is added, and a detailed flow thereof is shown in FIG. 7, and step S100_1 is added to calculate a bit amount of a message to be concealed, and the prefix of In order to calculate the length value, the control contents of steps S101, S104, and S108 were changed to denote steps S101A, S104A, and S108A using the variable K.                     

5, 6 and 7 will be described with reference to the data concealment process for the encoding method and the encoder for data concealment according to the preferred embodiment of the present invention.

First, original data consisting of an image or a document is obtained, and a message to be concealed represented by binary columns of 0 and 1 is configured according to a user's needs, and the user designates a predetermined threshold value THD. Here, the threshold value THD is used to adjust the minimum value of the length of the string selected to insert the message. The threshold value THD hides only the message having a length greater than or equal to the threshold value THD. In the following embodiment, the threshold value THD is set to the same value in each control program of encoding and decoding.

Then, as in the general LZW encoding process, a given character stream is stored in the input buffer 100 while a message to be concealed is stored in the input buffer 120.

The controller 200 performs a dictionary 400 initialization process defining a code for each character for all characters that may exist in the input character stream (step S100). Then, the user wants to conceal the hidden message is input to the input buffer 120 is in a state waiting for the message concealment process, the control unit 200 is to conceal the input completed to the input buffer 120 The total hidden message bit amount is checked and the hidden message bit amount is stored in the remaining hidden message bit amount storage area 300D of the storage unit 300 (step S100_1).

Thereafter, the controller 200 reads the first character from the input character stream stored in the input buffer 100 for compression, stores the first character in the prefix storage area 300A of the storage area 300, and stores the prefix. The prefix length value K is stored as "1" in the prefix length value storage area 300C of the unit 300 (step S101A).

Subsequently, the controller 200 reads the next character from the input character stream stored in the input buffer 100 and stores it as a suffix in the suffix storage area 300B of the storage unit 300 (step S102).

Subsequently, the control unit 200 has a dictionary (400 + suffix) of a string including the prefix and the suffix stored in the prefix storage area 300A and the suffix storage area 300B of the storage unit 300. In step S103, it is checked whether or not there is an entry that matches.

If there is an entry matched in step S103, the controller 200 updates the prefix and the suffix and stores it as a prefix in the prefix storage area 300A of the storage unit 300, and stores the prefix length value storage area. The new prefix length value K is updated and stored at 300C by adding "1" to the previous prefix length value K (step S104A).

Thereafter, the controller 200 checks whether there is a character to be read from the input buffer 100 (step S109), and if the character to be read from the input buffer 100 remains, the process returns to the step S102. The next character is read to see if there is an entry again matched in the dictionary 400 (step S103), and the process does not have any characters to read from the input buffer 100 or until there are no more matches. Repeat until not.

If it is determined that the character to be read in step S109 does not remain, the control unit 200 the code corresponding to the prefix stored in the prefix storage area 300A of the storage unit 300 remaining at the end of the dictionary 400 Find and output through the output buffer 500 (step S110), and ends the control of all encoding processes.

On the other hand, if it is determined in step S103 that there is no match, the control of the controller 200 proceeds to step S200. This step S200 is a step for message concealment, the specific process of which is shown in FIG.

In step S201 of FIG. 7, the controller 200 checks whether data for current concealment further remains in the input buffer 120 during a series of LZW encoding processes (step S201). To this end, the control unit 200 reads the remaining hidden message bit amount in the storage hidden message bit amount storage area 300D of the storage unit 300 and the remaining hidden message bit amount waiting to be hidden in the input buffer 120. Check if it is greater than "0".

When it is confirmed in step S201 that the message for insertion is no longer left (i.e., the amount of the remaining hidden message bits waiting for concealment is "0"), the control of the control unit 200 performs a general LZW encoding process. If it is determined that it is not (i.e., the amount of the remaining hidden message bits waiting for concealment is larger than " 0 "), then the control of the controller 200 proceeds to the next process (step S202). Proceed to

In step S202, the controller 200 compares the prefix length value K stored in the prefix length value storage area 300C of the storage unit 300 with a predetermined threshold value THD.

If the prefix length value K is not greater than the threshold value THD in step S202, the control of the controller 200 proceeds to step S106 for a general LZW encoding process.

On the other hand, when the prefix length value K is greater than the threshold value THD in step S202, the control unit 200 reads a hidden message one bit from the input buffer 120, and the storage unit 300 The remaining hidden message bit amount storage area of the storage unit 300 by subtracting 1 from the existing remaining hidden message bit amount stored in the remaining hidden message bit amount storage area 300D as a new remaining hidden message bit amount. Update to 300D) (step S203).

Thereafter, the controller 200 compares whether the parity of the prefix length value K stored in the prefix length value storage area 300C of the storage unit 300 is the same as one bit of the hidden message read in step S203. (Step S204). Here, the parity comparison compares an odd number, an even number of the prefix length value K, and one bit of the message to be concealed. In this case, the parity may be assigned to even number 0 and odd number 1, and conversely, even number 1 may be assigned 0 and odd number 0, respectively. In other words, if 0 is assigned to an even number and 1 is assigned to an odd number, both the prefix length value (K) and the message to be concealed must be even or odd parity, and if the even number is 1 and the odd number is 0, the prefix length value ( If K) is even and the message to be concealed is odd, or the prefix length value (K) is odd and the message to be concealed is even, parity is considered to match.

If the parity of the two values is the same in step S204, the control unit 200 proceeds to the next step S106.

On the other hand, if the parity of the two values in step S204 is different, the control unit 200 deducts the current prefix length value K stored in the prefix length value storage area 300C of the storage unit by "1" and The deducted prefix length value K is updated and stored in the prefix length value storage area 300C of the storage unit 300 as a new prefix length value K (step S205). The controller 200 reads the prefix stored in the prefix storage area 300A of the storage unit 300 to remove the last character of the prefix, and defines the prefix from which the last character is removed as a new prefix. The new prefix is updated and stored in the prefix storage area 300A of the storage unit 300 (step S206). In addition, the controller 200 updates and stores the last character excluded from the prefix in step S206 as a new suffix in the suffix storage area 300B of the storage unit 300 (step S207), and the controller 200 ) Control proceeds to the next step S106. The suffix updated through step S207 replaces the character read from the input character stream and stored as the suffix in step S102 in the existing LZW encoding process.

Then, in step S106, the control unit 200 searches for the code corresponding to the current prefix stored in the prefix storage area 300A of the storage unit 300 in the dictionary 400 and outputs the output signal through the output buffer 500. It outputs (step S106).                     

Subsequently, the control unit 200 adds the prefix and the suffix currently stored in the prefix storage area 300A and the suffix storage area 300B of the storage unit 300, and converts the prefix and suffix into a new entry in the dictionary 400. In addition, the dictionary 400 is updated (step S107).

Thereafter, the controller 200 updates and stores the value read from the surface storage area 300B as a prefix in the prefix storage area 300A of the storage unit 300 to be used for the next compression. In the prefix length value storage area 300C of 300, the prefix length value is updated and stored as "1" (step S108A).

Subsequently, the control of the controller 200 proceeds to step S109 described above to check whether there are any more characters to be read from the input character stream that is input and stored in the input buffer 100. When it is confirmed in the step S109 that the character to be read remains, the control of the control unit 200 returns to the above-described S102, and reads the next character from the input character stream inputted and stored in the input buffer 100, The control process from step S102 is repeated. On the other hand, if it is determined in step S109 that no character remains to be read, the controller 200 corresponds to a prefix (ie, a suffix) updated and stored in the prefix storage area 300A of the storage unit 300 in step S108A. The code 400 is searched in the dictionary 400 and output as an output signal through the output buffer 500 (step S110), and all encoding control ends.

Next, a decoding method for data concealment and a decoder thereof according to a preferred embodiment of the present invention will be described in detail with reference to FIGS. 8 to 10.

8 is a functional block diagram of a decoder for data concealment according to a preferred embodiment of the present invention, FIG. 9 is a flowchart illustrating operation of decoding for data concealment according to a preferred embodiment of the present invention, and FIG. Is a flowchart illustrating a key operation of decryption for data concealment according to a preferred embodiment of the present invention.

In FIG. 8, the input buffer 150, the dictionary 450, and the output buffer 550 perform substantially the same operations as the input buffer 15, the dictionary 45, and the output buffer 55 of FIG. 3. However, in the embodiment of the present invention, an output buffer 555 for outputting a hidden message hidden by a user, and a hidden message decoder 650 for decoding and extracting the hidden message are added to the storage 350. The STRING length value storage area 350D for storing the length value of the string STRING is added, and the control flow of the controller 250 is changed from that of FIG. 3.

In FIG. 9, compared to FIG. 4, step S400 for decoding the hidden message has been added, and a detailed flow thereof is shown in FIG. 10, and steps S305, S306, and S307 for calculating the length value of the string STRING are performed. The control content of is changed to denote steps S305A, S306A and S307A using the variable J. In addition, in the dictionary initialization step, the control content of step S300 is changed to set the flag value of the flag FLAG setting register of the control unit to "0", and thus, it is indicated as step S300A.

8, 9 and 10, a decoding method and a decoder for data concealment according to a preferred embodiment of the present invention will be described with reference to a decoding process of hidden data.

First, the controller 250 performs a dictionary 450 initialization process that defines a code for each character for all characters that may exist in the input character stream, and sets a flag FLAG in an internal flag FLAG setting register. ) Is set to "0" (step S300A), and one code is read from the input signal stream transmitted from the encoder and stored in the input buffer 150 to OCODE in the previous code storage area 350B of the storage unit 350. After storing as (old code) (step S301), the string corresponding to the code is found in the dictionary 450 and output through the output buffer 550 (step S302).

For example, the controller 250 reads the next code from the input buffer 150 and stores the code as NCODE (new code) in the new code storage area 350C of the storage unit 350 (step S303).

Thereafter, the controller 250 checks whether the NCODE exists in the dictionary 450 (step S304), and if present, reads the string corresponding to the NCODE from the dictionary 450 and the string region of the output buffer 550 (step S304). STRING) 550A, the length value of the string STRING stored in the corresponding string area is stored in the string length value storage area 350D of the storage unit 350 (step S305). Control of step 205 proceeds to step S308 below.

On the other hand, if the NCODE does not exist in the dictionary 450 in step S304 described above, it means that the addition to the dictionary 450 is later than the code to be encoded in a special case. In this case, the controller 250 reads the OCODE string from the previous code storage area 350B of the storage 350 and stores the string in the string storage area 550A of the output buffer 550 as a STRING. The length value of the string STRING stored in the area is stored in the string STRING length value storage area 350D of the storage unit 350 (step S306A).

Thereafter, the controller 250 updates and stores the STRING stored in the string storage area 550A with the first character of the STRING and adds the sum to the string storage area 550A of the output buffer 550 as a new STRING. After updating and storing a value obtained by adding "1" to a string length value previously stored in the string length value storage area 350D of the storage unit 350 as a new string length value ( Step S307A), the control of the controller 250 proceeds to step S308.

In step S308, the control unit 250 controls to output the STRING stored in the string storage area 550A, and the suffix storage area of the storage unit 350 using the first character of the output STRING as a suffix. 350A) (step S309).

Subsequently, the controller 250 updates the dictionary 450 by adding the OCODE stored in the previous code storage area 350B and the suffix stored in the suffix storage area 350A to the dictionary 450 (step). S310).

Thereafter, the controller 250 performs step S400, which is a hidden message decoding process, which will be described with reference to FIG.

First, the controller 250 checks flag FLAG information in an internal flag setting register (step S401). The string length value stored in the string length value storage area 350D of the storage unit 350 is determined. If J) is equal to the predetermined threshold THD, it is necessary to check whether there is at least one updated string in the dictionary 450 through LZW decoding on the corresponding string (ie, the string). However, since this operation is possible after the current string is updated in the dictionary 450, it is necessary to confirm whether the current string string length value (J) and the threshold value (THD) are the same in the following process. Use the flag FLAG.

When the flag FLAG is 0, the string length value J is larger than the threshold value THD. When the flag FLAG is 1, the string length value J is the threshold value THD. )

Therefore, when it is determined in step S401 that the flag FLAG value is 1, the controller 250 checks whether one or more strings identical to the currently updated string are already present in the dictionary 450 (step S402). If one or more identical strings are found, the control unit 250 reads the parity of the threshold THD (step S403), and outputs the parity of the read threshold value THD as a hidden message through the output buffer 555. After outputting (step 404), the flag FLAG is set to 0 in the internal flag setting register (step S405). On the other hand, when it is determined in step S402 that the same character string does not exist in the dictionary 450, the controller 250 sets the flag FLAG to 0 in the internal flag setting register because the message is not concealed. (Step S405).

Thereafter, the controller 250 compares the length value J of the STRING stored in the LZW decoding process with the size of the threshold value THD (step S406). When the length value J of the STRING is smaller than the threshold value THD, the control of the controller 250 proceeds to the next step S312.                     

On the other hand, when it is confirmed in step S406 that the length value J of the STRING is not smaller than (ie, greater than or equal to) the threshold value THD, the controller 250 determines the length value J of the STRING in step S407. ) Is equal to the threshold value THD.

When it is determined in step S407 that the length value J of the STRING is not equal to the threshold value THD (that is, when the length of the STRING is larger than the THD), it means that the message is concealed. Extracts a parity value indicating whether the length value J of the STRING is even or odd (step S409), and outputs the parity of the string length value J through the output buffer 555 as a hidden message bit (step S409). S410).

On the other hand, if it is determined in step S407 that the length value J of the STRING is equal to the threshold value THD, after the STRING is added to the dictionary 450 through the LZW decoding process, one or more of the same strings exist. It should be checked. However, since this process can be performed after reading the following code, the controller 250 sets the flag FLAG value to 1 for confirmation in step S408 and proceeds to step S312 below.

The dictionary 450 update process (step S310) and the hidden message decryption process (step S400) are performed as described above, and for the next process, the control unit 250 is stored in the previous code storage area 350B of the storage unit 350. The value read out from the new code storage area 350C is updated and stored as OCODE (step S312).

Thereafter, the controller 250 checks whether there are any more codes to be read from the input buffer 150 (step S313), and if the code remains, the control of the controller 250 returns to the above step S303. In step S303, the process is repeated, and on the other hand, if it is confirmed in step S313 that no more code remains, the control of all decoding processes ends.

Table 1 shows the case of compressing "abbabbaabbababbabbab" in order to compare general LZW encoding with LZW encoding which performs data hiding according to the present invention.

<Table 1>

LZW Coding LZW coding with data concealment of the present invention input output new symbol input output new symbol Hidden data a a 256 = aa a a 256 = aa b a 257 = ab b a 257 = ab b b 258 = bb b b 258 = bb a b 259 = ba a b 259 = ba bb 257 260 = abb bb 257 260 = abb aa 259 261 = baa aa 259 261 = baa bba 260 262 = abba bba 260 262 = abba One ba 257 263 = aba ba 257 263 = aba bbab 262 264 = abbab bbab 260 264 = abba One bab 258 265 = bba bab 262 265 = abbab 0

In Table 1, the threshold value (THD) is set to 3, and data concealment is possible only for symbols larger than 3 lengths. Therefore, since symbols whose lengths are 256 to 261 and 263 are not larger than the threshold value THD, normal update processing is performed, and symbols having code indices of 262, 264, and 265 have a length value. Since it is larger than the threshold value THD, the symbol length is changed to perform data concealment.

 Table 2 shows a case where general LZW decoding of the compressed value of "abbabbaabbababbabbab" as shown in Table 1 above and data hiding LZW decoding according to the present invention are performed.

<Table 2>

LZW decryption LZW decryption performing data hiding of the present invention input old code output new table entry input old code output new table entry data a a a a a a a 256 = aa a a a 256 = aa b a b 257 = ab b a b 257 = ab b b b 258 = bb b b b 258 = bb 257 b ab 259 = ba 257 b ab 259 = ba 259 257 ba 260 = abb 259 257 ba 260 = abb 260 259 abb 261 = baa 260 259 abb 261 = baa One 257 260 ab 262 = abba 257 260 ab 262 = abba 262 257 abba 263 = aba 260 257 abb 263 = aba One 258 262 bb 264 = abbab 262 260 abba 264 = abba 0 257 258 ab 265 = bba b 262 b 265 = abbab

In the above-described embodiment, a method of concealing data during LZW encoding / decoding of a character stream has been described. However, the present invention is similarly applied to LZW encoding / decoding of all applicable data such as a digital video stream and a digital audio stream. The invention can be applied to conceal data.

Although the present invention has been described in detail with reference to the drawings, the present invention is not limited to the specific embodiments related to the drawings but may be modified and modified in various ways within the scope of the present invention. It will be apparent to those skilled in the art to which the present invention pertains.

As described above, the present invention is a combination of LZW compression and data concealment techniques, which is the most well-known lossless compression method, to eliminate the loss or distortion of the original data that occurred in the existing technology, and to reduce the compression that is the original purpose of LZW At the same time, authentication of data and additional message transmission can be performed through data hiding.

Claims (18)

In the Rempel Jib Welch coding method for data concealment, Receiving a hidden message for performing text concealment and data concealment for Rampel Jib Welch encoding; And And performing a Rampel Jib Welch encoding on the character stream and concealing the hidden message in a result of the Rampel Jib Welch encoding on the character stream. The method of claim 1, wherein the performing of the Rampel Jib Welch encoding on the character stream and concealing the hidden message in the result of the Rampel Jib Welch encoding on the character stream comprises: Initializing a dictionary and storing a bit amount of the hidden message; Reading a first character, which is a first character, from the character stream, storing the first character as a prefix, and storing a prefix length value; And Reading a second character that is a next character of the first character from the character stream and storing it as a suffix and determining whether a string of the first and second characters matches the entry of the dictionary; Rempel Jib Welch coding method for data hiding. 3. The method of claim 2, wherein a character string read from the character stream, the second character that is the next character of the first character, is stored as a suffix, and the first character and the second character sum to match an entry of the dictionary. The judging step is When the string matches an entry of the dictionary, after the prefix and the suffix are combined, storing the prefix instead of updating the prefix length value by adding 1 to the prefix length value and storing the prefix length value. Rempel jib Welch encoding method for data hiding comprising a. 3. The method of claim 2, wherein a character string read from the character stream, the second character that is the next character of the first character, is stored as a suffix, and the first character and the second character sum to match an entry of the dictionary. The judging step is If the string does not match an entry in the dictionary, Checking whether the hidden message remains; Comparing the prefix length value with a predetermined threshold value; If the hidden message remains and the prefix length value is greater than the predetermined threshold, one bit is read from the hidden message and the remaining hidden message bit amount of the hidden message is updated, and the parity of the prefix length value and the Determining whether one bit read from the hidden message is the same; And Adding and updating the string as a new entry in the dictionary, and a Rempel Jib Welch encoding method for data hiding. The method of claim 4, wherein checking whether the hidden message remains and comparing the prefix length value with a predetermined threshold value include: Rempel Jib Welch encoding for data concealment, characterized in that if the hidden message remains or the prefix length value is not greater than the predetermined threshold, a code corresponding to the currently stored prefix is found and output from the dictionary. Way. 5. The method of claim 4, wherein if the hidden message remains and the prefix length value is greater than the predetermined threshold, one bit is read from the hidden message and the remaining hidden message bit amount of the hidden message is updated and the prefix is set. Determining whether the parity of the length value and one bit read from the concealment message is the same, If the parity of the prefix length value and one bit read from the concealment message are the same, finding and outputting a code corresponding to the currently stored prefix from the dictionary; If the parity of the prefix length value and one bit read from the hidden message are not the same, subtracting the stored prefix length value by 1 and updating and storing the prefix length value in the prefix length value storage area; Reading the stored prefix to remove the last character of the prefix and updating and storing the prefix from which the last character has been removed as a new prefix; And And storing the last character as a new suffix and finding and outputting a code corresponding to the currently stored prefix in the dictionary. In the Rempel Jib Welch decoding method for data concealment, Receiving an input signal stream for performing Rempel Jib Welch decoding for data concealment; And Rempel Jib Welch for performing the Rampel Jib Welch decoding on the input signal stream and outputting a hidden message through a parity value output when a predetermined condition is satisfied in the Rampel Jib Welch decoding process. Decryption method. 8. The method of claim 7, wherein the performing of the Rampel Jib Welch decoding on the input signal stream and outputting a hidden message through a parity value output when a predetermined condition is satisfied in the Rampel Jib Welch decoding process, Setting a flag of a flag setting register to 0, reading and storing a first code located in a first one of codes to be decoded from the input signal stream, and finding and outputting a string corresponding to the stored first code in a dictionary; Reading and storing a second code, which is a next code of the first code, from the input signal stream and determining whether the stored second code exists in the dictionary; Outputting a string stored in a string storage area, storing the first character of the output string as a suffix, and updating the dictionary by adding the stored first code and the suffix string to the dictionary; And A Rempel Jib Welch decoding method for concealing data comprising performing a concealment decoding process. The method of claim 8, wherein reading and storing a second code, which is a next code of the first code, from the input signal stream and determining whether the stored second code exists in the dictionary, If the stored second code exists in the dictionary, the dictionary reads the string of the stored second code and stores the string in the string storage area and stores the length value of the string stored in the string storage area. Rempel Jib Welch decoding method for concealment. The method of claim 8, wherein reading and storing a second code, which is a next code of the first code, from the input signal stream and determining whether the stored second code exists in the dictionary, If the stored second code does not exist in the dictionary, the data concealment may be read and stored in the string storage area and the length value of the string stored in the string storage area. Rempel Jib Welch decryption method. The method of claim 8, wherein performing the hidden decoding process comprises: Checking the flag value; And If the flag value is 1, it is checked whether at least one string identical to the string updated in the dictionary exists in the dictionary, and if the same string as the string updated in the dictionary does not exist, the flag value is zero. And setting the flag value to 0 after outputting a threshold parity as a hidden message when the same string as the updated string exists in the dictionary. The method of claim 8, wherein performing the hidden decoding process comprises: If the flag value is 0 and the length value of the string is larger than a predetermined threshold value, the length value parity of the string is extracted, the length value parity of the string is output as a hidden message, and the stored first code is updated and stored. Making; And And setting the flag value to 1 and updating and storing the stored first code if the string length value is equal to a predetermined threshold value. In the Rempel Jib Welch encoder for data concealment, A first input buffer for storing a character stream for performing Rempel jib Welch encoding; A second input buffer for storing a concealment message for data concealment; A storage unit for reading and storing the text stream and the hidden message stored in the first input buffer and the second input buffer, respectively; A controller configured to receive the text stream from the first input buffer to perform a Lempel Jib Welch encoding and to receive the hidden message from the second input buffer to perform data concealment; A message concealment unit which performs data concealment of the concealment message received from the second input buffer; A dictionary storing a code table including codes matched with character strings stored in the storage unit and strings of hidden messages; And The Rempel Jib Welch encoding apparatus for data concealment includes a character stream in which Rempel Jib Welch encoding is performed by the control unit and an output buffer for outputting a data hidden secret message. The method of claim 13, wherein the storage unit, A prefix storage area for storing a first character which is the first character of the character stream read from the first input buffer; A suffix storage area for storing a second character that is a next character of the first character of the character stream read from the first input buffer; A prefix length value storage area for storing a length value of a prefix stored in the prefix storage area; A Rempel Jib Welch encoding apparatus for concealing data comprising a remaining hidden message bit amount storage area for storing bit amounts of remaining hidden hidden messages. The method of claim 13, wherein the control unit, It is determined whether a string including a prefix and a suffix matches the dictionary, and when the string does not match the dictionary, the prefix length stored in the storage unit is compared with a size of a predetermined threshold value to determine the prefix length. The Rempel Jib Welch encoding apparatus for data concealment characterized in that if the value is larger than the predetermined threshold, control to perform data concealment of the concealment message. In the Rempel Jib Welch decoding apparatus for data concealment, An input buffer provided with an input signal stream to perform a Rampel Jib Welch decoding and receive a hidden message; A storage unit for reading and storing the input signal stream from the input buffer; A dictionary storing a code table including codes matching the input signal stream stored in the storage unit; A hidden message decoder for decoding a hidden message based on the input signal stream; A control unit which performs a determination to extract a hidden message based on the input signal stream stored in the storage unit; A first output buffer for outputting the hidden message decoded by the hidden message decoder; And And a second output buffer for outputting a value stored in the string storage region, the string storage region storing a string read from the storage unit. The method of claim 16, wherein the storage unit, An old code storage area and a new code storage area for storing an input signal stream input from the input buffer; A string length value storage area for storing a length value of a string stored in the string storage area; And And a suffix storage area for storing the first character of the string stored in the string storage area as a suffix. The method of claim 16, wherein the control unit, If the flag information is checked in an internal flag setting register, and the flag value is 0 and the string length value stored in the storage unit is larger than a predetermined threshold value, the parity value of the string length value is extracted to conceal the parity value. And a Rempel Jib Welch decoding apparatus for data concealment, characterized in that it is output through a first output buffer.

Images