Method for generating a data-bearing halftone image, and method for decoding the data-bearing halftone image

[0001] This application claims priorities of Taiwanese Patent Application No. 104134062 and Taiwanese Patent Application No. 104134064, both filed on Oct. 16, 2015.

[0002] The disclosure relates to an encoding system and a decoding system, and more particularly to an encoding system and a decoding system that are capable of respectively generating a data-bearing halftone image, and decoding the data-bearing halftone image.

[0003] An anti-counterfeiting manner involves using steganography to conceal message (regarding the copyright) in the documents and images. For example, U.S. Pat. No. 8,594,453 discloses a conventional method for creating a data-bearing halftone image in the form of a stegatone (steganographic halftone).

[0004] As shown in FIG. 1, a cell of a grayscale image may be converted into a stegatone using one of the four stegatone cells 502, 504, 506 and 508. Each of the stegatone cells is associated with a binary code having two bits (e.g., ‘00’, ‘01’, ‘10’ and ‘11’). As such, a message (e.g., a copyright claimer) in the form of a stream of binary codes may be represented by a series of stegatone cells which composes the data-bearing portion of the data-bearing halftone image.

[0005] However, the arrangements of the grayscale image using the stegatone cells are deliberately made. As a result, the quality of the generated data-bearing halftone image may be compromised.

[0006] Other documents related to the art include:

[0007] D. J. Lieberman and Jan P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Processing, Vol. 9, Issue 11, pp. 1950-1963, 2000. (doi:10.1109/83.877215);

[0008] Xiaotian Wu, Duanhao Ou, Juan Liu, and Wei Sun, “Data hiding in halftone images with homogeneous distribution of embedding positions,” Optical Engineering, Vol. 51, Issue 3, pp. 1-13, 2012. (doi:10.1117/1.OE.51.3.037005); and

[0009] Ming Sun Fu and O. C. Au, “Data hiding watermarking for halftone images,” IEEE Trans. Image Processing, Vol. 11, Issue 4, pp. 477-484, 2002. (doi:10.1109/TIP.2002.999680).

[0010] Therefore, an object of the disclosure is to provide a method for of generating a data-bearing halftone image that is encoded with a code, and that has a relatively better quality.

[0011] According to one embodiment of the disclosure, the method is implemented by an encoding system for generating a data-bearing halftone image. The encoding system includes a halftoning module and an encoding module. The encoding module stores a plurality of encoding rules associated with respective codes therein. The method includes the steps of:

[0012] converting, by the halftoning module, a grayscale image into a halftone image by screening the grayscale image using a predetermined threshold matrix that includes a plurality of grayscale threshold values, the halftone image having a plurality of image cells each corresponding to the predetermined threshold matrix in size, each of the image cells consisting of a plurality of dots, at least one of which is a first-tone dot and each of the rest of which is a second-tone dot; and

[0013] generating, by the encoding module, a data-bearing halftone image that is encoded with at least one of the codes by maintaining or changing the number of the first-tone dots in one of the image cells according to one of the encoding rules that is associated with the at least one of the codes.

[0014] Another object of the disclosure is to provide a method for decoding the data-bearing halftone image encoded by the above-mentioned method.

[0015] According to one embodiment of the disclosure, the method is for decoding a data-bearing halftone image that is encoded with a code and that includes a plurality of image cells. Each of image cells consists of a plurality of dots, at least one of which is a first-tone dot and each of the rest of which is a second-tone dot. The method is implemented by a decoding that system includes a database, a halftoning module, and a decoding module.

[0016] The database stores therein a grayscale image that corresponds to the data-bearing halftone image, a predetermined threshold matrix that includes a plurality of grayscale threshold values, and a plurality of encoding rules associated with respective codes. The method includes the steps of:

[0017] converting, by the halftoning module, the grayscale image into a halftone image by screening the grayscale image using the predetermined threshold matrix, the halftone image having a plurality of image cells each corresponding to the predetermined threshold matrix in size; and

[0018] decoding, by the decoding module, a data-bearing block of the data-bearing halftone image by

• • [0019] identifying the data-bearing block of the data-bearing halftone image that corresponds in location to an encodable block in the halftone image, the data-bearing block including adjacent four of the image cells of the data-bearing halftone image,
  • [0020] determining, between each of the image cells in the encodable block of the halftone image and a corresponding one of the image cells in the data-bearing block of the data-bearing halftone image, a difference of a number of first-tone dots contained therein, and
  • [0021] determining the code represented by the data-bearing block of the data-bearing halftone image based on the plurality of sets of encoding rules, and on the difference of the number of first-tone dots between each of the image cells in the encodable block of the halftone image and corresponding one of the image cells in the data-bearing block of the data-bearing halftone image.

[0039] Before the disclosure is described in greater detail, it should be noted that where considered appropriate, reference numerals or terminal portions of reference numerals have been repeated among the figures to indicate corresponding or analogous elements, which may optionally have similar characteristics.

[0040] FIG. 2 illustrates an encoding system according to an embodiment of the disclosure. The encoding system is configured to generate a data-bearing halftone image from a grayscale image 30 (as shown in FIG. 4). In this embodiment, the grayscale image 30 has a size of 16*16 pixels, and is extracted from a full grayscale image 3 (as shown in FIG. 4) that is to be encoded.

[0041] The encoding system includes a halftoning module 1 and an encoding module 2. In this embodiment, the encoding system may be embodied using a server computer that includes a processor, and the modules in the encoding system may be software applications that, when executed by the processor of the server computer, causes the processor to perform various functions that will be described below.

[0042] The halftoning module 1 stores a predetermined threshold matrix 40 (as shown in FIG. 4), and is configured to convert the grayscale image 30 into a halftone image 31.

[0043] Specifically, the term “halftone” refers to the technique that simulates continuous tone imagery using black dots and blanks. When a grayscale image is processed using the halftone technique, a halftone image is generated. When being apart from the halftone image by more than a sufficient distance, the halftone image may be perceived by the human eye as an image with continuous tone.

[0044] In this embodiment, the halftoning module 1 converts the grayscale image 30 into the halftone image 31 by screening the grayscale image 30 using the predetermined threshold matrix 40.

[0045] Specifically, the predetermined threshold matrix 40 is a square matrix generated using one of clustered-dot ordered dithering and dispersed-dot ordered dithering.

[0046] Exemplary threshold matrices generated respectively using the clustered-dot ordered dithering and the dispersed-dot ordered dithering are illustrated in FIG. 3.

[0047] In this embodiment, the predetermined threshold matrix 40 is generated using dispersed-dot ordered dithering, has a size of 4*4 elements, and is generated with reference to a screen tile vector set that consists of a pair of two-dimensional vectors.

[0048] The screen tile vector set is for determining a shape and a rotating angle of the predetermined threshold matrix 40. In this embodiment, the screen tile vector set is composed of two two-dimensional vectors [0,4] and [4,0], and has 4*4 grayscale threshold values.

[0049] Related documents regarding generation of the threshold matrix includes:

[0050] Jin-Young Kim, Yung-Yao Chen, Mani Fischer, Omri Shacham, Carl Staelin, Kurt Bengtson, and Jan P. Allebach, “Design of color screen tile vector sets,” Proc. SPIE, Color Imaging XVI: Displaying, Processing, Hardcopy, and Applications, Vol. 78661C, pp. 1-12, 2011. (doi:10.1117/12.878658); and

[0051] F. A. Baqai and Jan P. Allebach, “Computer-aided design of clustered-dot color screens based on a human visual system model,” IEEE Trans. Image Processing, Vol. 90, Issue 1, pp. 104-122, 2002. (doi:10.1109/5.982409)

[0052] “Design of Color Screen Tile Vector Sets”; and

[0053] “Computer-aided Design of Clustered-dot Color Screens Based on a Human Visual System Model”.

[0054] Referring to FIG. 4, in the screening process, the halftoning module 21 is configured to divide the grayscale image 30 into sixteen grayscale image cells 301, each corresponding to the predetermined threshold matrix 40 in size. That is to say, the predetermined threshold matrix 40 includes a number (m) of threshold values, and each of the grayscale image cells 301 has the number (m) of pixels. In this embodiment, the predetermined threshold matrix 40 includes 16 threshold values, and each of the grayscale image cells 301 has a size of 4*4 pixels. Each of the pixels is represented by a grayscale intensity value in the range of 0 to 255, where 0 indicates the strongest intensity and 255 indicates the lowest intensity.

[0055] Afterward, each of the grayscale image cells 301 and the predetermined threshold matrix 40 are compared element by element (a process referred to as “screening”). When one element of the grayscale image cell 301 (i.e., the grayscale intensity value of the pixel) is lower than or equal to the corresponding element in the predetermined threshold matrix 40 (the grayscale threshold value) in value, a value ‘0’ is outputted to represent a first-tone dot. Otherwise, a value ‘1’ is outputted to represent a second-tone dot.

[0056] The outputted values from each of the grayscale image cells 301 compose an image cell 311 of the halftone image 31, and the first-tone dot and second-tone dot represented by the outputted values compose a dot pattern of the image cell 311. The dot pattern of each of the image cells 311 of the halftone image 31 has the number (m) of dots (4*4 in this embodiment). In this embodiment, the first-tone dot represents a black dot, and the second-tone dot represents a white dot.

[0057] After the screening process is completed, a halftone image 31 consisting of first-tone dots and the second-tone dots is generated. The encoding module 2 is then configured to process the halftone image 31, in order to generate a data-bearing halftone image 32.

[0058] Specifically, as shown in FIG. 5, the encoding module 2 defines at least one encodable block 312 that includes adjacent four of the image cells 311 of the halftone image 31. In this embodiment, the halftone image 31 includes a plurality of encodable blocks 312, each being an 8*8 square block. It is known that in other embodiments, an encodable block 312 may be in the form of a 4*16 block or a 16*4 block. In one embodiment, the positions of the encodable blocks 312 in the halftone image 31 are stored in a database (not shown in the drawings).

[0059] The encoding module 2 stores a plurality of encoding rules associated with respective codes. Specifically, in this embodiment, the encoding module 2 stores sixteen encoding rules, each associated with a distinct 4-bit code, as shown in FIG. 6. For example, when a code “0000” is to be encoded in the halftone image 31, the encoding module 2 is configured to look up the corresponding encoding rule. From FIG. 6, it is shown that an encoding rule that correspond with the code “0000” includes four numbers “0000”. Those numbers are associated with a change of a number (i.e., quantity) of the first-tone dots in each of the image cells 311.

[0060] For example, for the encoding rule that corresponds with the code “0000”, in encoding this code, one encodable block 312 is used, and the number of the first-tone dots in each of the four image cells 311 of the encodable block 312 is maintained. That is to say, the entire encodable block 312 is unchanged.

[0061] The encoding rule that corresponds with the code “0001” has four numbers “+1”, “−1”, “0”, and “0”. In encoding this code, another encodable block 312 is used, and for an upper-left one of the image cells 311 of the encodable block 312, the number of the first-tone dots is increased by one. Additionally, for an upper-right one of the image cells 311 of the encodable block 312, the number of the first-tone dots is decreased by one. For the other two image cells 311, the numbers of the first-tone dots are maintained.

[0062] As illustrated in FIG. 7, an exemplary encodable block 312 is to be encoded with the code “0001”. It is determined that the top left, top right, bottom left and bottom right image cells 311 of the exemplary encodable block 312 respectively contain eight, nine, eight, and nine first-tone dots. After applying the above encoding action according to the encoding rule that corresponds with the code “0001”, a data-bearing block 313 may be generated with the top left, top right, bottom left and bottom right image cells 311 thereof respectively containing nine, eight, eight, and nine first-tone dots.

[0063] It is noted that, in this embodiment, when it is to increase the number of the first-tone dots in a particular image cell 311, one of the second-tone dots in the image cell 311 is selected, and toggled to become a first-tone dot. On the other hand, when it is to decrease the number of the first-tone dots in a particular image cell 311, one of the first-tone dots in the image cell 311 is selected, and toggled to become a second-tone dot. The selection may be arbitrary.

[0064] Applying the above procedure, the entire halftone image 31 may be encoded with a number of codes to generate a data-bearing halftone image 32 containing at least one data-bearing block 313 (see FIG. 8).

[0065] Referring to FIG. 2 and FIG. 8, the encoding system further includes an image optimization module 4. The image optimization module 4 is coupled to the encoding module 2 for receiving the data-bearing halftone image 32, and is configured to perform image optimization for each of the image cells 311 of the data-bearing halftone image 32 by utilizing techniques similar to direct binary search (DBS).

[0066] FIG. 9 illustrates how the image optimization may be implemented on an exemplary data-bearing halftone image. First, an image cell 100 of the data-bearing halftone image is selected (3*3 in this example) (hereinafter referred to as an encoded image cell). Then, a differential value between the encoded image cell and a corresponding portion of the grayscale image is calculated, and a differential value between the corresponding portion of the grayscale image and the encoded image cell after conducting each of a number of DBS trial actions with respect to a central pixel 10 thereof (the DBS trial actions result in a number of candidate image cells) is also calculated. The differential value is associated with how differently the human eye perceives the image cell and the corresponding portion of the grayscale image. This may be achieved by applying a human visual system filter kernel to both the image cell and the corresponding portion of the grayscale image.

[0067] Specifically, a trial swap action is applied to the central pixel 10 of the encoded image cell 100 (which a white dot in the example depicted in FIG. 9) by swapping the same with an adjacent dot having an opposite tone (i.e., an adjacent black dot in the depicted example). For this image cell 100, three black dots are present, and as a result three distinct trial swap actions are performed to result in three candidate image cells 100a, 100b, 100c.

[0068] For this example, four differential values are obtained, and the image cell with the lowest differential value is determined (either the encoded image cell 100 or one of the candidate image cells 100a, 100b, 100c) to serve as a corresponding optimized image cell (i.e., the difference between the optimized image cell and the corresponding portion of the grayscale image as perceived by the human eye is minimum).

[0069] Note that the DBS trial actions conventionally also include a trial toggle action. However, since a toggle action changes the number of first-tone dots in an image cell, for the purpose herein, the trial toggle action is not used.

[0070] A related document regarding the DBS technique is listed below:

[0071] F. A. Baqai and Jan P. Allebach, “Computer-aided design of clustered-dot color screens based on a human visual system model,” IEEE Trans. Image Processing, Vol. 90, Issue 1, pp. 104-122, 2002. (doi:10.1109/5.982409)

[0072] FIGS. 10A to 10C illustrate operations of the image optimization module 4 on exemplary image cells 311A to 311C.

[0073] The image cell 311A has four first-tone dots (represented in gray). For one of the first-tone dots that is marked black in FIG. 10A, the image optimization module 4 first determines a relative position of the marked one of the first-tone dots (i.e., whether the dot is located at a corner of the image cell 311A, on an edge of the image cell 311A but not at a corner, or otherwise). This is to ensure that all swap actions are performed within the image cell 311A. Since the marked one of the first-tone dots is not on an edge or at a corner, all eight adjacent dots are within the image cell 311A and among them, the second-tone dots can therefore be swapped with the marked one of the first-tone dots (one exemplary swapping is depicted). This swap action is referred to as a center swap action.

[0074] For the image cell 311B, a marked one of the first-tone dots is at a corner of the image cell 311A. As a result, only three adjacent dots may be considered for the swap action (one exemplary swapping is depicted). This swap action is referred to as a corner swap action.

[0075] For the image cell 311C, a marked one of the first-tone dots is on an edge of the image cell 311A but not at a corner. As a result, only the second-tone dots among five adjacent dots may be considered for the swap action (one exemplary swapping is depicted). This swap action is referred to as a side swap action.

[0076] As described above, for each first-tone dot in one particular image cell 311 in the data-bearing halftone image 32, the image optimization module 4 calculates a differential value between each of the image cell 311 and corresponding candidate image cell(s) and a corresponding portion of the grayscale image. Afterward, one of the image cell 311 and the candidate image cell(s) with the lowest differential value is taken by the image optimization module 4 to be the corresponding optimized image cell.

[0077] This process is iterated until an optimized image cell is determined for all image cells 311 of the data-bearing halftone image 32 to result in an optimized data-bearing halftone image 33 (see FIG. 8).

[0078] It is worth noting that in this embodiment, the image optimization module 4 performs image optimization for the image cells 311 in an order from left to right and from top to bottom of the data-bearing halftone image 32.

[0079] FIG. 11 illustrates a decoding system that is configured to decode the code that is contained in the data-bearing halftone image 32 and/or the optimized data-bearing halftone image 33. In this embodiment, the optimized data-bearing halftone image 33 is to be processed.

[0080] The decoding system includes a database 51, a halftoning module 52, and a decoding module 53. In this embodiment, the decoding system may be embodied using a server computer that includes a processor, the database 51 may be embodied using a physical storage device coupled to the server computer, and the modules in the encoding system may be software applications that, when executed by the processor of the server computer, causes the processor to perform various functions that will be described below.

[0081] As shown in FIG. 12, the database 51 stores the grayscale image 30 that corresponds to the optimized data-bearing halftone image 33, the predetermined threshold matrix 40, and the plurality of encoding rules associated with respective codes. It is noted that the predetermined threshold matrix 40 stored in the database 51 has the properties identical to those of the predetermined threshold matrix 40 stored in the encoding system. That is to say, the predetermined threshold matrix 40 is a square matrix having a screen tile vector set composed of two two-dimensional vectors [0,m] and [m, 0], and has m*m grayscale threshold values. Additionally, the grayscale threshold values in the threshold matrix are generated using one of clustered-dot ordered dithering and dispersed-dot ordered dithering (dispersed-dot ordered dithering in this embodiment).

[0082] In some embodiments, the database further stores a plurality of locations of the encodable blocks 312.

[0083] In decoding the optimized data-bearing halftone image 33, the halftoning module 52 of the decoding system first converts the grayscale image 30 into the halftone image 31 in a manner similar to that of the halftoning module 1 of the encoding system. As such, the halftone image 31 has a plurality of image cells 311, each corresponding to the predetermined threshold matrix 40 in size.

[0084] Afterward, the decoding module 53 is configured to decode the data-bearing block 313 of the optimized data-bearing halftone image 33, based on the halftone image 31 and the encoding rules.

[0085] Specifically, as shown in FIG. 12, assuming that the upper-left quarter part (an 8*8 block) of the optimized data-bearing halftone image 33 is a data-bearing block 313 and the upper-left quarter part (an 8*8 block) of the halftone image 31 is an encodable block 312. In this embodiment, the location of the encodable block 312 (and in turn, data-bearing block 313) is identified by the decoding module 53 since the decoding system may include mechanisms for defining the encodable block 312 that is similar to those of the encoding module 2 of the encoding system. In other embodiments, the location of the encodable block 312/data-bearing block 313 is pre-stored in the database 51.

[0086] The decoding module 53 then calculates the number of the first-tone dots in each of the image cells 311 in the data-bearing block 313 of the optimized data-bearing halftone image 33 (nine for the top left image cell, eight for the top right image cell, eight for the bottom left image cell, and nine for the bottom right image cell), and the number of the first-tone dots in each of the image cells 311 in the corresponding encodable block 312 of the halftone image 31 (eight for the top left image cell, nine for the top right image cell, eight for the bottom left image cell, nine for the bottom right image cell).

[0087] Afterward, the decoding module 53 is configured to determine a difference of the number of the first-tone dots between each of the image cells 311 in the data-bearing block 313 of the optimized data-bearing halftone image 33 and the corresponding image cell 311 in the corresponding encodable block 312 of the halftone image 31 (+1, −1, 0, 0). As such, the decoding module 53 is capable of determining the corresponding 4-bit code that is encoded in the data-bearing block 313 of the optimized data-bearing halftone image 33 (the code “0001”).

[0088] In brief, the operations of the encoding module 2 are capable of encoding the halftone image 31 with the codes, while bringing up only minimal changes to the resultant data-bearing halftone image 33 in comparison with the halftone image 31. Specifically, for each of the image cells 311, the encoding action changes the number of the first-tone dots at most by one. For each of the encodable blocks 312, the encoding action does not alter the total number of the first-tone dots (reference may be made to the encoding rules). As a result, the data-bearing halftone image 32 thus generated has relative better quality.

[0089] Additionally, the employment of the image optimization module 4 is able to provide the optimized data-bearing halftone image 33, which is processed using a technique similar to the DBS to ensure that the outputted image is as close to the grayscale image as possible for optimal perception to the human eye.

[0090] FIG. 13 is a flow chart illustrating a method for generating a data-bearing halftone image 32 by the encoding system, according to one embodiment of the disclosure.

[0091] In step 602, the encoding system receives a grayscale image 30.

[0092] In step 604, the halftoning module 1 converts the grayscale image 30 into a halftone image 31.

[0093] In step 606, the encoding module 2 generates a data-bearing halftone image 32.

[0094] In particular, as shown in FIG. 14, step 606 includes the sub-steps as described below.

[0095] In sub-step 606a, the encoding module 2 defines at least one encodable block 312 that includes adjacent four of the image cells 311 of the halftone image 31.

[0096] In sub-step 606b, the encoding module 2 encodes the at least one encodable block 312 with one of the four-bit codes.

[0097] In step 608, the image optimization module 4 performs image optimization on each of the image cells 311 of the data-bearing halftone image 32.

[0098] In particular, as shown in FIG. 15, step 608 includes the sub-steps as described below.

[0099] In step 608a, for each first-tone dot in the image cell 311, the image optimization module 4 calculates a differential value between the image cell 311 and a corresponding portion of the grayscale image 30.

[0100] In step 608b, for each first-tone dot in the image cell 311, the image optimization module 4 calculates a differential value between the corresponding portion of the grayscale image 30 and each of at least one candidate image cell that is obtained by swapping the first-tone dot with a corresponding second-tone dot adjacent to the first-tone dot within the image cell 311.

[0101] In step 608c, the image optimization module 4 determines a lowest one of the differential values thus calculated.

[0102] In step 608d, the image optimization module 4 replaces the image cell 311 with one of the image cell and the candidate image cell(s) that has the lowest differential value.

[0103] FIG. 16 is a flow chart illustrating a method for decoding a data-bearing halftone image 32 by the decoding system, according to one embodiment of the disclosure.

[0104] In step 702, the decoding system receives a data-bearing halftone image 32.

[0105] In step 704, the halftoning module 52 converts the grayscale image 30 into a halftone image 31.

[0106] In step 706, the decoding module 53 decodes the data-bearing block 313 of the data-bearing halftone image 32.

[0107] In the description above, for the purposes of explanation, numerous specific details have been set forth in order to provide a thorough understanding of the embodiment(s). It will be apparent, however, to one skilled in the art, that one or more other embodiments may be practiced without some of these specific details. It should also be appreciated that reference throughout this specification to “one embodiment,” “an embodiment,” an embodiment with an indication of an ordinal number and so forth means that a particular feature, structure, or characteristic may be included in the practice of the disclosure. It should be further appreciated that in the description, various features are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure and aiding in the understanding various inventive aspects.

[0108] While the disclosure has been described in connection with what are considered the exemplary embodiments, it is understood that this disclosure is not limited to the disclosed embodiments but is intended to cover various arrangements included within the spirit and scope of the broadest interpretation so as to encompass all such modifications and equivalent arrangements.