RU2329522C2 - Adaptive embedding of water marks through several channels - Google Patents

Abstract

FIELD: stenography.

SUBSTANCE: invention refers to digital stenography, particularly to direct, without spectral transformations reversible embedding of random water marks by means of quantisation and modification of amplitude values of a signal under conditions when an original reflection (a container) is not accessible, and a transmitted message is not known at a receiving end - that is a technology of a blind embedding. A method of iterative embedding of random messages (bit planes) into a digital representation by means of successive alterations of brightness of a pixel representation and embedding into representation of each successive bit plane is performed considering modification of the reflection at embedding of previous bit planes; embedding of the first bit plane is carried out by a method of "one-channel embedding"; it contains the stages of iterative division of the brightness scale of a total reflection into successive ranges; at that for each of the ranges obtained at one of the intermediate iterations there are determined not changeable and variable at embedding of the message components of reflection and embedding of a bit message into pixels of a variable component by means of either accepting values of brightness of a reflection pixel as a pixel, containing an embedded message, or a mirror reflection of a value of its brightness against the central value of brightness for the above said range; at that embedding of bit planes is cyclic repeated till the received stego-reflection does not quit changing at embedding of the said bit planes.

EFFECT: upgraded efficiency of messages hiding.

5 cl, 14 dwg

Description

FIELD OF THE INVENTION

The invention relates to the field of digital steganography or embedding arbitrary watermarks in a digital image. More specifically, the invention relates to the field of direct, without spectral transformations, reversible embedding of arbitrary watermarks by quantizing and modifying the amplitude values of the signal under conditions when the original image (container) is unavailable and the transmitted message is not known at the receiving end - blind embedding technology.

The terminology used in this document

The set and unset bits are alternative bit values that are described regardless of the particular interpretation; usually 0 and 1, in the invention ± 1 or 0 and 2, etc.

Image, signal - the video signal is digitized and presented as a matrix of integer brightness values. It is divided into an explicit (observed) signal and an implicit signal, the modification of which is visually inconspicuous.

Pixel (“dot”) - image element.

The brightness count (count, brightness) - the value of the pixel brightness.

Image conversion - obtaining a new image by changing the brightness values of its pixels.

Image representation is the result of image conversion.

A container is a source digital signal, an image intended for embedding.

Container context - observed container information formally represented by some set of visually perceptible pixels of an explicit signal. The context of the container (the subject area of the images in question) is not limited.

Message, watermark - embedded data, ordered in bytes of elements of a certain matrix of amplitude values, a sequence of bit planes containing arbitrary bits of independent message components or independent bit messages intended to be embedded with each other and transferred together with the container context. It is an arbitrary binary code (bits) containing embedded information, which is encoded by a sequence of modifications of the container pixel brightness values and supplements the observed information (container context), stored by fixing the brightness value of a given pixel at certain stages of modifying the container pixel brightness.

Embedding - embedding, storing a message in a container. Modification of natural (original), embedded noise, etc. implicit information (implicit signal) contained in the image.

Stego image is a digital image containing an embedded message. Image with modified codes of natural, built-in noise, etc. implicit information (implicit signal).

Amplitude, amplitude value is a synonym for the term “brightness”, which is convenient to denote the brightness of a formally calculated representation of a signal when used together with the term “brightness”, which refers to the original image.

Grayscale - sequential, non-repeating brightness values listed in order, which may occur in an arbitrary image or image representation. For image processing, the scale is presented in the form of a sequence of addresses identifiable with the brightness (amplitude) addresses of an array of computer memory cells, in which values are mapped to various brightness values, for example, the number of pixels of a given brightness encountered when calculating the histogram, or the amplitude when calculating the image representation in the form "Histogram image."

The brightness range is a certain range of brightness values of the scale, limited by the brightness (amplitude) values encountered in the image (image representation).

Working range - the considered range of brightness of the image, limited by the minimum and maximum brightness values encountered in the image.

Calculated (about the range) - calculated by the histogram of the image by iteratively dividing the working range into a sequence of ranges nested in one another. In the provided number of iterations, the ranges are calculated the same for the container and the stego image.

The approximation of the image below (above) is a representation of the image in which the brightness values of the pixels are replaced by the minimum (maximum) brightness values of the calculated ranges to which the brightness values of these pixels belong. The approximations from below and from above directly for each pixel in the image establish the boundary brightness of the ranges and the ranges of the permissible variation of the pixel brightness values themselves or, for brevity, simply the ranges of the permissible variation of brightness. In this case, independent from each other variation of the brightness values of image pixels within the established ranges of permissible variation of brightness does not affect the result of calculating the approximations from below and above from the modified image.

A channel is a “corridor” between the image approximations from below and above (combining, according to the coordinates of the ranges of permissible variation of pixel brightness values). More precisely, a plurality of images, for each of which the considered pair of image approximations from below and above is calculated. In another definition, equivalent in the framework of the invention, a channel is a set of images generated by independent variation of pixel brightness values within the ranges of acceptable brightness variation. A channel is considered as a member of a hierarchical sequence (hierarchy) of channels nested into each other. With a selected pair of image approximations from below and above, the channel contains all kinds of stego images generated by embedding various messages in this container (but not limited to these stego images). The maximum channel includes all other channels and is generated by the independent variation of the pixel values of the image of unlimited brightness within the working brightness range.

Ternary memory is a real or emulated device for generating and storing in their cells (integer) numbers encoded in the ternary number system. How the device is used, for example, as part of a universal ternary computer (see Brusentsov N.P. Computing machine "Setun", Moscow State University. In the book: New developments in the field of computational mathematics and computer technology. Kiev, 1960. P. 226- 234 [BRUS60], Brusentsov NP Restoration of logic. - M.: “The New Millennium”, 2005, 165 pp. [BRUS05]), in which instead of the bits of traditional computers are used trits that take three values -1, 0, 1 or, in another interpretation, 0, 1, 2. Optimal for the best implementation of the invention, especially nennaya a ternary memory (memory matrix with elements of the arithmetic-logical operations), wherein a lock mechanism ternary storage elements of its cells (i.e., trityl) by recording.

Trit is an analogue of a bit, a memory element of a ternary memory cell or an element of record (integer) of a number in a ternary system, which encodes a member of the additive decomposition of a number written in a cell in increasing degrees of a triple (digit) with coefficients (digits) 0, 1, 2.

Multichannel ternary memory - attributed to the image memory from ternary cells containing information codes of the explicit signal, as well as message codes embedded in the implicit signal. Formed, generated by an explicit signal, regardless of the implicit signal, modified when embedding a message. The memory elements of ternary cells are trits, which are divided into active (containing codes of an explicit signal that can be modified) and inactive (containing codes of an implicit signal that can only be read). In an equivalent sense, multichannel ternary memory is a copy of the ternary memory assigned to an image in a real or emulated ternary storage device, which for embedding a message is created in the computer memory allocated for a given image, defines the corresponding ternary memory area and is modified synchronously with image processing. Multichannel ternary memory is a matrix of cells of ternary memory, which are one-to-one map to image pixels. The structure (separation of trites into active and inactive) and the contents (values of trites) of multichannel memory are calculated bitwise - from the highest digits to the lowest digits, the digits are sequentially mapped to the channels in the order of nesting (from the highest, oldest channel to the nested lower channels), and the value of this the discharge depending on the geometrical coordinates is determined by the sign of the difference between the pixel brightness and the central brightness of the range of permissible variation calculated in the considered coordinate d For the next channel.

Single-channel embedding - writing bits of a binary matrix (bit plane) into a given bit of all active trites, encoded in the selected channel by pixel modification with brightness varying in this channel.

Multi-channel embedding - sequential bitwise recording of message bit planes into active trites of ternary memory, which begins with single-channel encoding of the first bit plane in the selected channel, continues in all lower channels and is repeated until the image is stabilized.

Packing by brightness - image conversion, which consists in replacing the brightness values of pixels with successive numbers of the brightness scale values found in the image, for example, brightness values 1, 100, 110 are replaced by their numbers in order, for example, 0, 1, 2.

Equidistant normalization - a linear transformation of the brightness values of the image pixels, for example, for visualization (display), which is reduced to multiplying the brightness values of the packed image by a factor so that the maximum brightness value encountered coincides with the upper limit of the maximum range, which is determined by the number of bits provided in a computer for image input / output. If during “packing” the luminances are replaced by their numbers in order, for example, luminances 1, 100, 110 are replaced by 0, 1, 2, then with “equidistant normalization” the packed luminances are multiplied by a factor, for example, by 127.5 so that the maximum brightness matches with a maximum possible brightness value of 255.

Standard transformations are packaging, linear stretching (by multiplying the brightness values by a factor greater than 1), equidistant normalization, and other linear and non-linear transformations of the brightness values of image pixels without violating their sequence.

Invariant (default) - preserved during standard transformations.

Arithmetic conversion (amplitude value) - dividing an odd value by two and doubling an even value previously divided by four. The use of this particular transformation for the invariant representation of an image in a pseudo-ternary coding system is justified, for example, in: M.V. Kharinov, V.L. Gorokhov. Pseudotroin number system and image analysis // News of Russian Universities. Radio Electronics / Issue. 2, - St. Petersburg, 2003 .-- S. 49-53.

An isomorphic representation of an image, an image is such a representation of an image in which the relations “less”, “equal”, “greater” existing in the original image are saved between the pixel brightness values. For example, standard transformations generate isomorphic images.

A homomorphic representation of an image, an image is a representation of an image, upon receipt of which the transition of unequal brightnesses into equal ones is allowed. For example, the arithmetic transformation defined above generates homomorphic images.

State of the art

Solutions related to embedding a message in a container when transmitting via a public communication channel are conventionally divided into steganography tasks and watermark embedding tasks in a container. Steganography is understood as covert embedding of a relatively large message into a container, which can be part of the container, supplement the context of the container in a dependent or independent way to restrict unauthorized access to the message, duplicate the context in case of interference, provide it with accompanying information, etc. By embedding a watermark usually it means covert embedding of a previously known distributed or repeating message of relatively small volume for identification container context authenticity or source of the stego-image, copyright protection and so on., as well as for steganography objects attained within a limited amount of posts.

With a limited amount of information required, watermark embedding is subject to the most stringent requirements, among which are (see B. Chen and GW Wornell, "Digital Watermarking and Information Embedding using Dither Modulation", IEEE Signal Processing Society 1998 Workshop on Multimedia Signal Processing December 7 -9, 1998, Los Angeles, California, USA, Electronic Proceedings May 1998 [Chen98], and B. Chen and GW Wornell, "Quantization index modulation: A class of provably good methods of digital watermarking and information embedding", IEEE Transactions on Information Theory Vol. 47, pp. 1423-1443, May 2001, [Chen01]) the following three main:

- maximum speed of embedding (and extraction) of the message;

- the metric proximity of the stego image and the original container, for example, by standard deviation;

- The maximum robustness of embedding a message.

The listed production requirements are justly considered to be contradictory. To overcome the concomitant shortcomings, an analysis of the target settings is necessary, which consists in the following.

With the current sharp increase in computer computing resources, the problem of insufficient speed of embedding messages arises due to the insufficiently efficient organization of data storage and repeated calculations with various parameters, due to direct enumeration of variants of known messages in the process of correlation analysis or enumeration of embedding methods ([Chen98, Chen01]), as well as other reasons that are not relevant for the present invention.

The requirement of metric proximity of the stego image and the source container is the main source of controversy, because:

- logically inconsistent with the assumption of a container that is not available at the receiving end;

- limits the possible message size;

- prevents the embedding of the message at the same time as simplifying the stego image by reducing the number of gradations of brightness (a concomitant change in the histogram entails a large point-to-point standard deviation);

- limits the possibilities of invariant embedding of the message regardless of the provided transformations;

- prevents robust embedding of a message with periodic repetitions in coordinates;

where, unlike invariance (preservation in the exact sense), robustness (resistance to possible accidental or deliberate interference in transmission) refers to incomplete, inaccurate message storage, which is studied using examples of previously known distortions in the form of linear transformations, JPEG compression, additions noise, etc.

It seems obvious that for effective concealment of messages it is necessary to be able to formally separate the signal, depending on the context, into visible and invisible components and then save the visible component during the embedding of the message. Nevertheless, in well-known solutions, the need for such a separation of the signal with subsequent preservation of the visible component is not sufficiently understood, formalized insufficiently simple and achieved by an incomplete heuristic implementation of either one or the other.

To increase the efficiency of hiding messages by taking into account the context of the container, methods are developed for distributing embedded codes over texture sections of the image with a high concentration of brightness differences, on which the introduction of message information is invisible (grass, hair, noise distortion, etc.).

The development trend of methods for directly embedding a message taking into account the context of the container is illustrated in FIG. 2.

In Fig. 2, the container is shown on the far left in the form of a standard Lena image (leftmost) and a), b), c) of embedding information on which white fields indicate variable pixels in which modification is allowed, i.e. into which message codes are embedded. Thus, the decisions are based on the coordinate-wise distribution of the built-in message codes according to the results of the container analysis: the leftmost one is the container; next - coordinate schemes of embedded codes with the simplest LSB method (a), block-by-block embedding of codes (b) and point-by-point embedding of codes in texture sections (c).

In the simplest LSB method, embedding message codes is performed in a fixed number of low-order bits regardless of the context of the container, and embedding is stopped when the message is exhausted (see V.G. Gribunin, I.N. Okov, and I.V. Turintsev. Digital steganography. Moscow, SOLON-Press, 2002, 258 pp. (Analytical review) [Gri02]). In methods (see Gika S.N. Analysis of the effectiveness of methods of hiding information in graphic files // 32nd St. Petersburg Scientific and Technical Conference of Students, Graduate Students and Young Scientists. Abstracts. - SPb .: 2000. - 75 p. [Gi00], Hioki Hirohisa A data embedding method using BPCS principle with new complexity measures // Proc. Of Pacific Rim Workshop on Digital Steganography 2002, Jan. 2002. P. 30-47 [HiHi02]) embedding message codes is performed according to previously calculated sections of textures that are approximated by blocks of coordinates of embedding a simple shape.

The listed works reflect the tendency of modern solutions to adaptively hide messages taking into account the context of the container. However, the processing capabilities in this case are limited mainly by geometrically adaptive data embedding, which is performed on texture brightness and color segments with a high concentration of brightness differences of color components.

If a hidden message at reception is assumed to be unknown, then it is usually accompanied by accompanying control information about the location of the embedded data. The control information is not adaptively placed at the fixed coordinates of the provided signal fragment, regardless of the context of the container, as in the simplest “LSB” method. The message is embedded in some blocks of the container to reduce the amount of control information that is set, for example, by a list of block coordinates. At the same time, a block record of a message limits the accuracy of taking into account the geometry of the container pattern and reduces the effect of hiding message codes in texture sections. If the message is known to be known and detected during reception by standard correlation analysis methods, then you can do without control information, apply point-by-point embedding, and when embedding the message, limit yourself to highlighting textures (scheme (c) in Figure 2). However, the task of effectively highlighting textures in arbitrary images is problematic in itself.

Thus, it is typical for known methods of blindly embedding watermarks adaptively to the container that the container context is taken into account only by the geometric arrangement of message codes by coordinates for fixed ranges of brightness modification, the value of which is set to a multiple of degree 2. Since the results of calculating the coordinates of the built-in message codes on the container are not reproduced with a similar processing of the stego image (the built-in message affects the calculation of texture segments), for successful When treating a message, related information is embedded into the container regardless of the context, which can also be set algorithmically and independently in the general scheme of embedding and extracting messages, in particular, watermarks appear as an attribute key ([Gri02], VI Gorodetsky, VI Samoilov "Simulation -Based Exploration of SVD-Based Technique for Hidden Communication by Image Steganography Channel ", Proc. Of the Second Int. Workshop on Mathematical Methods, Models, and Architectures for ComputerNetwork Security MMM-ACNS, ISSN: 0302-9743, ISBN: 3- 540-40797-9, St. Petersburg: Springer-Verlag-Berlin-Heidelberg, pp. 349-359, Sep. 2003 [Hor03]), as illustrated in FIG. The dashed line in this drawing shows data that can be used at the input of the message extraction subcircuit, but is not always required.

If all optional elements are excluded from the circuit, it remains overloaded with the requested data at the input and not specific enough at the output. The main drawback of the generally accepted scheme and its practical implementations is that they do not fully describe the information of the original signal (container), which is stored after embedding the message data.

Most of the theoretical generalizations of the well-known methods of hiding messages are based on the analogy with cryptographic solutions. According to [Gri02], direct or indirect (algorithmic) indication of the list of coordinates of built-in message codes is considered to be an analog of a cryptographic key in steganography. At the same time, a cryptographic key seems to be necessary, since the results of calculating the coordinates of the built-in message codes on the container are not reproduced during the similar processing of the stego image.

In addition to the input key, which “imposes” the modification of the container regardless of the masking context of the image, when extracting the message, the message is not formalized or insufficiently formalized extracts the information of the original signal (container), which is stored after embedding the message codes. At the same time, the concepts of an unknown and inaccessible container are mixed.

In the absence of a container-independent key, the inaccessibility of the container itself when retrieving a message is the main obstacle to the exact calculation of the location coordinates of embedded codes, which is overcome in the Reversible Data Hiding RDH method of reversibly embedding data in an image or audio signal (see Mehmet U. Celik, Gaurav Sharma, A. Murat Tekalp, Eli Saber. Reversible Data Hiding. IEEE Proceedings of the International Conference on Image Processing (ICIP), New York, September 23, 2002. P. 157-160 [Meh02], Fridrich J., Goljan M. , Du R. Lossless data embedding - new paradigm in digital watermarking. EURASIP Journ. Appl. Sig. Proc., Vol. 02, Feb 2002. P. 185-196 [Fri02]). In this method, the embedding of the message is ensured by partial compression of the video data contained in the lower bits of the original signal representation. In this case, in the original RDH method, the message is first extracted, and then the container is restored. However, if you embed lists of coordinates for embedding codes as a message, then to recover the message, it will be necessary to restore the container beforehand.

In the scheme of the RDH method, a transformed container is understood to be a representation of the original signal with a certain number of low-order bits freed up due to the packaging of low-order information. The free space is used to embed the message, which allows you to save both the container and the built-in message during transmission without distortion.

However, due to the limited compression ratio and the relatively small amount of embedded codes (less than 10%) of the container volume, as well as due to instability to distortions during the transmission of the stego image, the RDH method is not effective enough for embedding messages of a relatively large volume and has Steganography tasks are of limited practical importance.

SUMMARY OF THE INVENTION

The above disadvantages are overcome in the present invention, which relates to a method for reversible blind idempotent (in one iteration) embedding steganographic messages or arbitrary watermarks without using a key in pixels with calculated brightness ranges of a variable value and is divided into single-channel embedding of message bits in the container, presented in the form binary matrix (bit plane), as well as a more general one - multi-channel embedding of message codes specified in the form of lnosti bit planes.

Single-channel embedding is similar to embedding message bits in one of the least significant bits of a container. However, if in the LSB method a change in the bit of the pixel brightness value, regardless of the container, is encoded by increasing (or decreasing) this value by degree 2, that is, by modifying the brightness in one of the nested ranges multiple of degree 2, then in the invention the message bit is encoded by the brightness modification within the range of permissible variation from the hierarchy of nested ranges, which is not specified in advance, but is calculated by the histogram of the container.

The LSB method provides for encoding several message bits in a single container pixel luminance value, which is problematic within the framework of multi-channel embedding. The fact is that as a result of embedding the message, the histogram of the container changes and the hierarchy of ranges nested in this range of acceptable variation in brightness changes. In addition, encoding an additional bit of a message can change the value of a bit already embedded in a given coordinate. To overcome these problems, a method has been developed for multi-channel embedding of message components or a method for adaptively embedding watermarks over several channels, the number of which is calculated depending on the container (and message), and these problems are solved by updating the histogram (and the results of its processing) when embedding the next bit the plane of the message (or an independent bit message), taking into account additional brightness values that cannot be modified in the considered channels, and also due to iteratively repeat the embed procedure until the embed results are completely stabilized.

General advantages of these embodiments of the invention are characterized by the following.

The solution is designed to record and retrieve arbitrary codes of information (video data) and, depending on the conditions of use, is interpreted as embedding a steganographic message or an arbitrary watermark of a relatively large volume in a container. Contrary to prevailing stereotypes, it is believed that the inconspicuousness of embedding, by itself, does not determine the essence and features of algorithms, but rather is a restriction on the choice of configuration parameters of embedding in the process of application in real time (on-line). Regardless of the condition of visual invisibility of embedding a message, the basic steganography task or the task of embedding an arbitrary message does not change essentially and includes, first of all, reversible embedding of message codes adaptively to the container.

In the present invention, the concepts of an unknown and inaccessible container are separated, believing the container upon receipt to be known, but in a coarsened, simplified form. To formalize the concept of “invisible embedding”, instead of metric proximity, the assumption is used that the container context observed after embedding the message can simply be calculated independently of the message and presented as a coarsened new image (image) obtained by a predefined algorithm for iterative segmentation of the container or stego image . Since the indicated segmentation algorithm refers to image enhancement algorithms with a decrease in the number of brightness gradations (see Pratt W. Digital image processing: In 2-book M .: Mir, 1982. 714 pp. [Pratt]), then a real improvement in visual perception is considered instead accepted in steganography, a formal assessment of the deterioration in the quality of the stego image by the standard deviation from the container.

Since the same simplified container is calculated at the transmitting end before embedding the message as at the receiving end, the transmitting side has the ability to pre-evaluate the degree of preservation of the container context for processing automation purposes. In order to control the concealment of message codes in real time, it is provided, in addition to the standard reduction in message size, the maximum distribution of embedded codes in the image field.

If the requirement of metric proximity of the container and the stego image is excluded from the list of essential requirements for embedding a message while maintaining the container context, it is possible to divide the non-strict concept of robustness into the exact concept of invariance (strict preservation) of the embedded message with linear and non-linear standard transformations of the stego image (packaging, linear transformations, equidistant normalization by brightness, etc.) and the usual stability of the message with respect to random or technological x stego-image distortion (noise, JPEG-conversion) as well as intentional external attacks. In problems with a limited message volume, stability is achieved with respect to container distortions during transmission due to periodic repetition when embedding codes of a message embedded in the image boundaries known in advance at the receiving end of the size, and then summing the extracted corresponding codes of various copies when receiving the message.

Message bits are inserted, similarly to the LSB method, according to a predetermined law (from the beginning of the image, from the end of the image, using a random number generator, etc.), however, with gaps depending on the context of the container.

When embedding a message in a stego image with a simultaneous decrease in its number of luminance gradations in comparison with the original container, the differences between the luminances with which the message is encoded increase. Due to such coding of the message with large differences in brightness and, as a result, an increase in the amplitude of the message signal, the robustness of embedding the message increases.

The invariance of embedding a message with respect to the standard transforms of the stego image is ensured by the fact that, before embedding the message, the container, regardless of the standard transformations, is converted at the transmitting end according to a certain algorithm to some invariant representation, and before the message is extracted at the receiving end, the stego image is converted for restoration messages, in the case of the provided transformations during transmission.

To control the embedding, an automated real-time parameter setting is provided. In general, optimal embedding is achieved in a specific task as a reasonable compromise between the volume of the embedded message, on the one hand, and the conditions of invisibility and robustness of embedding, on the other hand.

The total amount of codes of a geometrically repeating message (i.e., repeating the same embedded message at image locations with different coordinates) is determined by the context of the container, but the message itself is arbitrary. The stego image, in addition to the codes of the message itself, does not contain information about the message, nor about the source container, as in the LSB method. Although the container is not required to retrieve the message at the receiving end, however, the original signal (or, in case of invariant embedding, its image) in a simplified form is known during transmission and reception, since it is saved during the embedding of the message. The message at the receiving end is considered not known. When a message is received, the brightness modification ranges are not fixed the same for different coordinates, and no special indication of the embedding coordinates of the message is required, since the coordinates of pixels with variable brightness and the embedding ranges of the message are calculated by the received signal signal exactly the same as the original container. Correlation analysis is not expected.

Figure 3 in a simplified form presents a diagram of the proposed solution according to a variant implementation in the invention of single-channel embedding.

Instead of the information compression procedure used in the RDH method, image segmentation is used. Due to segmentation and weakening of the conditions for the complete recovery of container information, it is possible to increase the amount of embedded message codes.

As a result of segmentation, the container is irreversibly, but without significant damage to visual perception, is converted into a simplified representation of the image - a segmented signal (container or stego image) with a limited number of brightness gradations, which is defined by a calculated set of pixel brightness values with an unchanged brightness value and such a signal saved when embedding a message. Pixels with a brightness that does not change when embedding a message are extreme in a certain way calculated brightness ranges and allow you to determine the reading level of the brightness values, as well as the limits of the brightness of the remaining (modified) pixels with intermediate brightness values, the brightness of which the message is encoded. Thus, the brightness values of the pixels of the segmented container, as well as the segmented stego image, make it possible to determine the reference level for modifying the brightness values used to encode the message. Unlike the RDH method, message codes are placed adaptively to the container, since they are recorded in the stego image in pixels with variable (variable, modifiable) brightness, which are interspersed with pixels in the container that have unchanged brightness. Robustness, stability of the message to possible distortions of the stego image is ensured by geometric repetition of the message codes within the container.

The robustness of the message in the exact sense of its preservation under the provided linear and nonlinear isomorphic transformations of the stego image (packaging, stretching, equidistant normalization in brightness) is ensured by preliminary transformation of the container when embedding the message, and when the message is extracted, the stego image into an invariant homomorphic idempotent representation .

Robustness, stability of the message to unintended distortions of the stego image is ensured by geometric repetition of the message codes within the container, as well as by encoding the message with relatively large brightness differences

Figure 4 is given to compare the proposed solution with the known and illustrates the embedding of message codes in the present invention. The container to the bottom left in Figure 4 is shown, next to the container is the container approaching from below, the next one is its approaching from above and the extreme right is a representation of the difference in approximations from above and below. Based on a comparison of the brightness gradations of this representation with each other, we can visually assess the width of the range of allowable brightness variations in the signal for each pixel. “Permissible variation” means that image modification due to an independent change in pixel brightness strictly within the ranges of allowable brightness variation does not affect the calculation of these ranges. In contrast to known solutions, adaptive embedding of message codes is provided not only in coordinates, but also in brightness ranges without using non-adaptive control information or enumerating options in the process of correlation analysis. By removing the conditions of the LSB method for embedding message codes in a predetermined number of bits, the availability of the message for steganalysis is reduced. Masking the message is achieved not by limiting the changes in the brightness of the pixels of the container, but mainly by interleaving in the image pixels with embedded data messages with pixels with unchanged data from the container and by adding a high-frequency carrier signal to the message.

Along with embedding message bits in coordinates of ranges of permissible variation of container brightness, the proposed solution does not require non-adaptive (container-independent) indication of the coordinates of embedded data blocks and avoids block recording according to the known method, which enhances the advantages compared to known solutions.

Embedding control in the invention is performed in real time by adjusting the values of the ranges of permissible brightness modification while changing the ratio of stored and variable pixels, which are parameterized by Mersenne numbers in the form of degrees reduced by unity. With an increase in this parameter, the ranges of acceptable brightness variation decrease, the proportion of embedding pixels increases, and the degree of concealment of the message increases. Various parameters in the form of Mersenne numbers correspond to variants of the set of acceptable ranges for varying brightness. In this case, in each variant, the calculated ranges of permissible variation in brightness when recording a message vary from pixel to pixel. The values of the brightness variation ranges, generally speaking, do not coincide with powers of 2, i.e. ranges of permissible brightness variation accommodate an integer number of message bits. Although sequences of message bits per pixel of an image can be encoded in ranges with a magnitude greater than 3, in one embodiment of the present invention they are limited to embedding a single bit per each modifiable pixel to avoid reducing robustness and scrambling messages that are especially critical with variable brightness modification ranges over the image field .

This option single-channel embedding of the present invention in comparison with the known methods of hiding an arbitrary message provides the following features:

- message saving during linear and nonlinear isomorphic transformations of the stego image;

- robustness of the message in relation to unintended distortions due to the encoding of the message by means of relatively large differences in brightness, as well as due to the repetition of message bits in coordinates and colors;

- detection and assessment of unauthorized access (non-isomorphic distortions of the stego image);

- suppression of noise of limited amplitude;

- improving the sharpness of the stego image while reducing the number of gradations of brightness to simplify automatic processing.

The following characteristic disadvantages of modern steganography methods are also overcome:

- heuristic, insufficiently accurate estimates of the possible volume of the embedded message;

- the use of coordinates of data placement previously known to the addressee;

- the use of trivial embedding of data or control information in a fixed number of least significant bits or in container-independent coordinates;

- uniform embedding of the message in various containers, including in non-gradation images, which consist, for example, of one 0;

- uneven filling of the container when embedding the message.

With single-channel embedding, the volume of message codes is predicted regardless of its content, which simplifies the logic of reversible message hiding. However, the fact that the message volume in the original brightness scale according to the well-known Kolmogorov estimate of the amount of information in the combinatorial approach is described by an integer number of bits, on the contrary, leads to a complication of the solution due to the ambiguity of the heuristic organization of embedding message components with coordinates overlay.

One of the disadvantages of the single-channel embedding method is that in addition to embedding binary codes in the image coordinates, it does not provide for additional embedding of codes directly in the original container.

The main disadvantage of the single-channel embedding method of the invention is the limited amount of message due to the insufficient number of embed channels for message codes. An insufficient number of embedment channels entails insufficient camouflage of some message components by others, and a fixed number of channels also increases the availability of embedded information for stego analysis. In addition, the insufficient number of channels, obviously, limits the ability of robust embedding of message codes due to duplication of information encoded by the brightness of the same pixels.

Probably, the main reason for limiting the volume of embedding messages is the lack of models for the adequate presentation and storage of information, as well as insufficient implementation for the storage and processing of signals of computing devices with ternary memory, known, for example, as universal computers [BRUS60, BRUS05]. In these devices, instead of the usual bits, three states with three states that are most convenient for implementing the invention are used as storage cells.

In the invention, due to the multi-channel embedding according to the second embodiment, the advantages are developed and the disadvantages of the single-channel embedding method according to the first embodiment are overcome.

Due to the formalization of multichannel embedding and use when embedding ternary memory, the total amount of embedding message codes from several bit planes increases to 20-30% of the container volume.

Thanks to data storage via ternary memory and its use in calculations, multi-channel embedding of message bit-plane codes is achieved not only with invariant embedding of the primary message, but is already supported in the basic reversible multi-channel embedding algorithm without reducing the number of brightness gradations of the image. At the same time, the desired result of embedding codes immediately across all channels is achieved due to iterative repetition of embedding, during which the separation of trites into active and inactive adapts to a multi-channel message. In one of the methods of the invention, when forming the so-called “continuous” ternary memory, the embedding of a multi-channel message is achieved in one cycle and is performed in an idempotent transformation of the container.

The invariant embedding of relatively linear and non-linear isomorphic transformations of the stego image is achieved in the invention immediately along all minor channels due to its iterative repetition, packing of the control invariant idempotent homomorphic representation (histogram image) in brightness, and also the provided rules for the separation of ternary memory trits into active ( modifiable) and inactive (fixed).

The invention enhances the robust embedding of the message by duplicating the codes of the bit planes of the message with multiple overlapping coordinates. At the same time, robustness is achieved due to the geometric repetition of the codes of the bit planes of the message not only in coordinates, but also due to their repetition in nested brightness ranges, the hierarchy of which depends on the image context and varies from pixel to pixel.

Multiple overlapping of components of the embedded message on top of each other enhances the masking of the fact of concealment. For additional concealment of the fact of concealment, as well as for symmetric setting of the initial state of ternary memory, duplication of senior trit values in lower active trit is used, similar to how in the “LSB” method the values of bits of the highest order can be copied to the lower order to match a homogeneous message from identical bits some initial picture depending on the container.

Due to the adaptability property of the ternary memory of the invention with a known and accessible perturbation of the stego image, it is possible to provide robust embedding of a message by cyclically repeating the embedding of the message alternately with the perturbation.

Brief Description of the Drawings

Figure 1 illustrates a general scheme for embedding and extracting messages for steganography and embedding watermarks;

Figure 2 illustrates well-known solutions for coordinate-wise distribution of embedded message codes according to the results of container analysis;

Figure 3 illustrates a reversible data embedding scheme according to the invention;

Figure 4 illustrates the adaptive embedding of message codes in the coordinates and brightness ranges calculated according to the invention as a result of the analysis of the container;

Figure 5 illustrates the memorization of a sequence of values -1, 1, 0,1,0 ... in the i-th cell of a multi-channel ternary memory;

Figure 6 illustrates embedding a message bit in one channel using an example of a one-dimensional image fragment;

7 illustrates an example of an invariant isomorphic image representation obtained according to the invention;

Fig. 8 illustrates storing the hierarchy of partitions of discrete segments;

9 illustrates a message in its original form and a message deployed in a sequence of bit planes;

10 illustrates a standard image and a color image;

11 illustrates a basic iterative embedding of message codes on multiple channels;

12 illustrates the effect of the ternary memory continuity condition on multi-channel message embedding during initial partitioning of the operating range with parameter μ;

Fig. 13 illustrates multi-channel invariant embedding of a message in a ternary memory while reducing the number of gradations of brightness of the stego image;

Fig. 14 illustrates the increase in the stability of a stego image with a uniform message to JPEG conversion due to repeated embedding.

DETAILED DESCRIPTION OF THE INVENTION

In more detail, the method of single-channel embedding of message bits in the pixels of the container is explained below.

The visually observed component of the container is calculated as a context signal, which is stored after embedding the message. Masking is achieved by interleaving pixels containing the message with the pixels of the observed signal component and depends on the amplitude of the message signal, as well as on the frequency of the message signal, which can be increased by adding a high-frequency component to the message, for example, by adding a high-frequency component to the message signal or due to the formal introduction of periodic fluctuations of the “zero” reference signal level of the message.

The control of embedding the message is performed in real time by setting the values of the calculated ranges of the brightness scale by the histogram (and, as a result, the ranges of permissible variation of the brightness values of image pixels) using Mersenne numbers in the form of powers reduced by one (2 ⁿ - 1, for example, 1, 3, 7, 15, 31, 63, etc.), with a simultaneous change in the ratio of the number of pixels with stored and variable brightness values. With an increase in the indicated Mersenne number (i.e., an increase in the number of brightness ranges), the value of each range of permissible variation in brightness decreases. At the same time, the larger the number of ranges, the more pixels with boundary brightness values will be fixed. Since these pixels are included in the observed picture and interspersed with variable pixels, visually the degree of concealment of the message increases.

Thus, for different values of Mersenne numbers, variants of a set of acceptable brightness variation ranges are calculated, and in each variant, ranges of acceptable brightness variation when recording a message change from pixel to pixel, since pixels from different ranges are found nearby.

The values of the brightness variation ranges, in the general case, do not coincide with powers of 2. For example, the brightness range 0-4 contains 5 integer brightness values. Two of them are boundary and, if a pixel has a brightness equal to one of these values, it is immutable. Three others, namely values 1-3, can be used to encode the message. However, for encoding two bits of an embedded message, at least 4 internal values of the specified range are required in addition to the boundary values, therefore, if there are only three of these non-boundary values in the range 0-4, only one bit of the embedded message can be encoded. Therefore, to encode two bits of an embedded message, the number of brightness values together with the boundary values must be at least 6 within the same range.

Although it is possible to encode several (i.e., more than one) message bits per pixel in the ranges of acceptable brightness variation with the number of brightness values, including boundary values exceeding 5, the present invention is limited to embedding a single bit per each pixel to be modified to avoid robustness and scrambling Messages that are especially critical for variable brightness modification ranges over the image field.

In a more general way of multi-channel embedding for storing data, the inverse problem is solved - the actual storage medium in the form of a multi-channel ternary memory is calculated by the signal. Although multichannel ternary memory is generated by a signal component, it is able to store information similarly to the memory of a conventional computer. Any image, besides the context, contains some implicit message that can be retrieved and modified to transmit hidden information, protect the container, simplify automatic processing, etc. When you re-record the message that is contained in the container, the container does not change. The task of steganalysis is specified and interpreted not as the task of detecting a message, but as the task of retrieving a message and detecting a modification or substitution of some initial, for example, random message.

It is assumed that various images within certain conditions of invariance differ in context or in implicit information. Reversible embedding is interpreted as reading and writing information to the ternary memory associated with the image. Moreover, the lack of effectiveness of embedding methods and their diversity is explained by the underutilization of the possibilities of filling the ternary memory and is expressed by the insufficient volume of embedding.

The ternary memory expresses, simplifies, and supports the interpretation of the hierarchy of ranges of permissible variations in pixel brightness as information carriers containing an integer number of message codes. Embedding a message superposition using ternary memory is performed as follows.

Reversible embedment mathematical scheme

Embedding S _{h of} message h in the image (container) u is achieved by transforming W _h , which, when applied cyclically, generates some sequence of representations that converges to the representation of S _h u:

:

,

:

,

where n is the number of repetitions of the transformation W _h .

By the convergence of representations obtained by the transformation (program, mapping, etc.) W _h , we mean the existence of a limit S _h u of the indicated sequence of representations, which is called a stego image and does not change under the action of the program W _h . In other words, it is assumed that the iterative transformation is not looped, and with a sufficiently large number of N repetitions, the representation ν of the image u that is invariant with respect to the transformation W _h is achieved:

W _h ν = ν,

- стего-изображение.where ν

- stego image.

. В общем случае, если преобразование S_h достигается за несколько итераций N

, называем его итеративным встраиванием.Although the result of re-embedding S _{h of} message h in an arbitrary container u coincides with the result of a single entry, we call S _h idempotent embedding if the program W _h is such that embedding message h in an arbitrary container u is achieved in a single iteration and N = 1, and

. In the general case, if the transformation S _{h is} achieved in several iterations N

, call it iterative embedding.

. Представление h получается обнулением некоторого множества тритов представления

из одних

, строящегося посредством записи в троичную память исходной последовательности битов встраиваемой информации и выполняется с повторениями по координатам и разрядам троичной памяти до ее заполнения.Message h means a matrix of values of ternary cells of multichannel ternary memory, which are mapped to image pixels and contain sequences of trit with values 0,

. Representation h is obtained by zeroing out some set of representation trites

from some

constructed by writing to the ternary memory the initial sequence of bits of embedded information and is performed with repetitions in the coordinates and bits of the ternary memory until it is filled.

при записи в троичную память не учитываются в ее неактивных элементах, при чтении кодов сообщения из троичной памяти вычисляются как неопределенные и помечаются нулевыми значениями. Поскольку нулевые триты сообщения h предсказуемы при встраивании представления

, пропуска битов исходной встраиваемой информации можно избежать, например, за счет кодирования исходной последовательности битов с исключением пропуска информации при достаточном числе повторений. Поэтому можно рассматривать в качестве начального троичного представления исходной последовательности встраиваемых битов сообщение h и не останавливаться далее на деталях практической реализации, чтобы не загромождать изложение.Zero trits in the message h arise due to the fact that, depending on the context of the container u, some values of presentation trits

when writing to the ternary memory, they are not taken into account in its inactive elements; when reading codes, messages from the ternary memory are calculated as undefined and are marked with zero values. Since the zero trits of the message h are predictable when embedding the view

, skipping bits of the original embedded information can be avoided, for example, by encoding the original sequence of bits with the exception of skipping information with a sufficient number of repetitions. Therefore, we can consider message h as the initial ternary representation of the initial sequence of embedded bits and not dwell on the details of the practical implementation so as not to clutter up the presentation.

Thus, retrieving the message h consists in calculating it from the stego image from the condition that W _h leaves the stego image unchanged. Assuming that any image contains some message, we write down the condition of reversibility of embedding message h in the form:

R: R (W _h u = u) = h,

where R is the message extraction program that executes the solution of the equation W _h u = u with respect to h and, in fact, is an independent generation and output of the message file provided for in the body of the program W _h . In this formula, the argument of the mapping R is interpreted in two ways: as a result of a single embedding W _h u and as a condition W _h u = u, which is considered as an equation for finding h.

стего-изображения S_hu в процессе встраивания сообщения h позволяет обойтись при его извлечении условиями сохранения кодов сообщения при однократном встраивании, по каналам и координатам, как описывается в следующем разделе.The main feature of the described scheme is that the existence of an exact limit of approximations

Stego-images S _h u in the process of embedding message h allows you to dispense with its retrieval by preserving the message codes during a single embed, by channels and coordinates, as described in the next section.

Multichannel ternary signal memory model

Embedding a message is carried out in the invention as storing it in a multi-channel ternary memory, which is used to write and read arbitrary message codes like a conventional digital memory. It is believed that multichannel ternary memory consists of storage elements that are introduced by generalizing the concept of bits.

If we distract from the structure of the memory cell of a conventional computer, then the change in the values of the bits in which the brightness values of the image pixels are stored is encoded by modifying the brightness values in the nested ranges of the brightness scale, equal in magnitude to degrees 2. The bits of the multi-channel ternary memory being compared to the image are determined by the sequence of nested scale divisions brightness into ranges which, generally speaking, are not multiple of 2 in magnitude, and are calculated in the iterative separation algorithm of the brightness histogram a portion with an approximately equal number of pixels. The iterative splitting of the brightness scale continues until all ranges degenerate into ranges containing a single brightness, which is compared to a sequence of ranges contracting to it and belongs to one of them at each iteration. The algorithm for splitting the brightness scale is such that varying the brightness of each pixel in the image within its range, although it affects the histogram of brightness, does not affect the calculation of the current partition of the brightness scale, as well as the calculation of its previous partitions into brightness ranges. In this case, the pixels can be modified in brightness independently of each other.

It is believed that multichannel ternary memory cells are mapped to image pixels and consist of sequential storage elements. The value of the next cell element of the multichannel ternary memory, depending on the iteration number of the partition of the brightness scale, is determined by the sign of the deviation of the pixel brightness from the center of the next brightness range. At the same time, a positive, negative, or zero value of the sign of the difference between the pixel brightness and the central brightness of the range in question is assigned to this element of the multichannel ternary memory cell, as indicated in FIG. 5, which shows an example of storing a sequence of values -1, 1, 0,1,0 ... in the i-th cell of multichannel ternary memory.

5 illustrates the contents of a cell of a multi-channel ternary memory that is mapped to a certain image pixel with the number i. Stepped solid lines in Fig. 5 denote the brightness of the approximations from below and above. We set that -1 is recorded in the highest trit of the cell, since the pixel brightness is less than the average brightness of the range of acceptable variation, in the next trit of the lower bit, 1 is recorded, since the pixel brightness is higher than the average brightness of the corresponding range of acceptable variation, the next trit has the 0th value, since the brightness the pixel was in the middle of the next range, etc. It is obvious that if the portion of the brightness scale between a given pixel brightness value and the same brightness value reflected relative to the axis of the current range of its allowable variation considered is crossed by at least one of the axes of the previous ranges of permissible variation (such as, for example, the axis of the mentioned range corresponding to 0- value of the trit), then a modification of the brightness in the considered range of acceptable variation will entail a modification of the previous trit. Therefore, such trits, the modification of the values of which entails the modification of the previous trits, are classified as inactive, along with the trits corresponding to pixels with boundary and central brightnesses.

This establishes the contents of the ternary memory cell, as well as reading from pixels the values of ternary units of information called trites according to N. P. Brusentsov. Trites associated with this partition of the brightness scale constitute channels of the ternary memory and are considered ordered by decreasing the nested brightness ranges. In this case, the oldest trit of each ternary memory cell is calculated for the working brightness range, which contains the brightness of all pixels in the image.

The message is recorded in the trits of the multichannel ternary memory associated with the reflection of the brightness value of the pixel relative to the center of the corresponding range and is performed sequentially from the highest trits to the lowest ones. The brightness value that appears in the center of the range, obviously, does not change during reflection. Therefore, trits with zero values when recording a message cannot be modified and are considered inactive. Inactive are also trites, which are compared with brightnesses that limit the acceptable ranges of brightness variation, and trites, the change of which entails a modification of previous trites.

The basic principles of embedding a message in multichannel ternary memory include three requirements for invariance:

1. The invariance of the stego image relative to the re-embedding of the message (idempotency of embedding);

2. Invariance of the container with respect to the reverse embedding of the extracted message;

3. The invariance of the message with respect to linear and nonlinear isomorphic transformations of the stego image.

Here, it is understood that re-recording a message does not affect the stego image, any image is saved when the message extracted from it is embedded back into the image, and also that standard stego image transformations (packaging, stretching the working range, equidistant normalization of the stego image etc.) do not affect the message.

The components of the color image when calculating the ternary memory are considered independently of each other. Image redundancy is expressed by repeating trits in coordinates, ternary memory channels and colors. The distortion of the message codes in the process of image transmission during reception is compensated by a simple summation of the values of the corresponding bits of trit with the subsequent calculation of the sign of the received amount. To account for cases of zero total value, it is convenient to use exactly trits, not bits, as storage elements of the memory associated with the signal.

Thus, the trits make it possible to eliminate the systematic rounding errors characteristic of the use of bits when calculating the multi-channel memory associated with the signal and more accurately formalize the redundancy of video information. The features of the units of information representation in multichannel ternary memory compared to the original representation in binary computer memory are shown (for byte images) in table 1.

Table 1
Units of presentation and storage of video information Units
Attributes Bits Trites Serial number 0, 1, 2, ..., 7 0, 1, 2, ..., Ch condition 0.1

Status Rw R, RW

where Ch is the number of ternary memory channels, R and RW are the designations of inactive and active trites.

показана зависимость яркости u от координаты x.6 illustrates an interpretation of the concept of a ternary memory channel of a signal. 6, a solid dark line for the image (container)

The dependence of the brightness u on the x coordinate is shown.

The essence of the idea of performing reversible embedding using multichannel ternary memory without using a key to find the coordinates, as well as embedding ranges of message codes, boils down to constructing in the vicinity of the image a sequence of embedded “corridors” of acceptable image modification, one of which is indicated in the drawing and is limited by dashed lines. Corridors are mapped to sequences of bits of cells attributed to the image of multichannel ternary memory.

Each “corridor” of permissible modification of the original image, on the one hand, is calculated from the image, and, on the other hand, does not depend on the variation of the brightness of the image pixels within its limits. For clarity, the image is indicated by a continuous curve, and the corridor is shown with overlapping ranges of brightness variations, which, in fact, are calculated by non-overlapping and spaced along the vertical axis. As a result of constructing a variant of approximations from below and above, the boundaries of the ranges of permissible brightness variation are “stretched” to the brightness of the pixels of the signal (container or image stego) with the stored brightness, and for each pixel with variable brightness, the internal allowable range of variation of brightness is set, as well as for allowable ranges of variation luminance determine the central brightness values of white indicated by white color of the zero (ie, "segmented") signal. In principle, in the image there may not be a single pixel whose brightness value coincides with the central value in the allowable range of variation of the brightness value. Nevertheless, the central values of the brightness of the ranges, which are calculated the same for both the container at the transmitting end and the stego image at the receiving end, serve as the initial level for message codes no worse than the actual values of the brightness and can be considered as the brightness of the transmitted formal zero signal.

For accurate and unambiguous embedding (recording) of a message bit in an image without using integer rounding, a message bit is written by mirroring the brightness value of the image pixel relative to the axis of the allowable brightness modification range.

The invention is applied to the original digital signal, the brightness (amplitude, brightness samples, etc.) of which are specified in integer numbers. In this case, it is not the transition from continuous to discrete quantities that is considered, but the replacement of several (integer) quantities with a common value. In order to accurately and unambiguously embed (write) the message bit in the image in the present invention without using integer rounding, the message bit is recorded by mirroring the brightness value of the image pixel relative to the axis (i.e., an integer or half-integer central brightness value) of the acceptable range of brightness modification. For example, if u {x} is the brightness of a pixel with an x coordinate, and a {x} and b {x} are the boundary values of the range, then the brightness value v {x} “reflected” relative to the central value of the range is calculated by the formula v {x} = a {x} + b {x} -u {x}, and the value v {x} is integer. With another method of modification, the result may not be integral, and then rounding will be required.

The set and unset message bits are encoded in pixels with variable brightness values, respectively, positive and negative (or vice versa, negative and positive) unit values of the sign of the deviation of the pixel brightness from the central brightness of the range of acceptable variation. It should be noted that mirroring the brightness of the pixel relative to the central brightness of the range of acceptable variation is similar to reversing the value of the low-order bit in the LSB method and when recording a message bit according to the invention, it is performed only when the indicated sign value does not match the required message code. Therefore, when you re-record the message in the stego image, the latter does not change.

Reversible embedding of message bits in the brightness of pixels with x coordinates is described by the relation:

+sign(

)·

) =

P (

+ sign (

)

) =

sign(

)

- отклонение яркости стего-сигнала от центра диапазона;

- его абсолютная величина; sign - функция знака, принимающая значение -1, 0, 1 в зависимости от, соответственно, отрицательного, нулевого и положительного значения аргумента; sign(

) - сообщение, установленные и неустановленные биты которого кодируются в пикселях с варьируемыми значениями яркости, соответственно, положительными и отрицательными (или наоборот - отрицательными и положительными) единичными значениями функции знака от отклонения

;

+sign(

)·

+

- стего-изображение;

- нулевой сигнал, значения яркости которого совпадают с центральными значениями диапазонов допустимой яркостной модификации, а P - идемпотентное преобразование контейнера u в нулевой сигнал Pu.Where

sign (

)

- deviation of the brightness of the stego signal from the center of the range;

- its absolute value; sign is a sign function that takes the value -1, 0, 1 depending on, respectively, the negative, zero, and positive values of the argument; sign (

) is a message whose set and unset bits are encoded in pixels with variable brightness values, respectively, positive and negative (or vice versa, negative and positive) unit values of the sign function from deviation

;

+ sign (

)

+

- stego image;

is a zero signal, the brightness values of which coincide with the central values of the ranges of permissible brightness modification, and P is the idempotent transformation of the container u into a zero signal Pu.

Here, in the traditional interpretation, an idempotent transformation is understood as a transformation whose repeated use coincides with a single:

P = P ²

The result of image transformation under the action of idempotent transformation in this invention is called idempotent representation.

Essential to simplify the description and implementation of the present invention is the concept of a hierarchy of homomorphic representations of the image, as well as algorithms for its construction and storage.

Hierarchy of homomorphic representations. Under the representation isomorphic to the image in brightness order, i.e. with respect to the brightness ratio between any two brightnesses, regardless of the ranges, we mean an image converted in the same coordinates, between which brightness values are preserved less, equal, more. If in the transformed image in the relationship between brightness values a transition from inequalities to equalities is allowed, but these relations are not replaced by alternative ones, then it is considered a homomorphic representation of the original image. The transformation of an image into an isomorphic (homomorphic) representation is called an isomorphic (homomorphic) transformation. Under the hierarchy of representations of the image in the framework of the invention refers to representations of the image that are generated by a sequence of partitions of the brightness scale into nested brightness ranges and which are calculated for each partition by isomorphic transformation. The ranges enclosed in each other are found by iteratively dividing the brightness scale, for example, into two parts, then each of the resulting ranges again into two parts, etc. As a result, it turns out that each brightness value is contained in some hierarchical sequence of ranges nested into each other, the upper and lower boundaries of which are “contracted” to this brightness value.

For a given partition of the brightness scale into ranges, homomorphic representations of the image are obtained by replacing the pixel brightness values encountered in the image with successive serial numbers of the calculated ranges, serial numbers of ranges with gaps in the numbers, or other consecutive indices of those ranges that contain the brightness of these pixels, and an isomorphic representation is obtained, when each range from a given partition of the brightness scale contains a single brightness value.

The numerical hierarchy of invariant idempotent homomorphic representations. A numerical hierarchy of image representations refers to a hierarchy of homomorphic representations, which is obtained by iteratively transforming the brightness values of pixels of an isomorphic representation of an image by integer division and multiplication by an integer that depends only on the brightness value of the converted pixel, in particular, by applying the aforementioned arithmetic transformation. In other words, a numerical hierarchy is a sequence of representations of an image, which is determined by the brightness values of pixels of an isomorphic representation of the image and arithmetic operations with them, for example, in the simplest case, iteratively dividing the brightness values of an image in half. An example of obtaining a numerical hierarchy for non-repeating brightness values is given in the description below with reference to Fig. 8.

A numerical hierarchy is considered invariant if the isomorphic representation that generates it does not depend on standard image transformations (packaging, linear transformation, equidistant normalization by brightness, as well as other linear and nonlinear isomorphic transformations).

Figure 7 shows an example of an invariant isomorphic representation of the image obtained according to the invention. In Fig. 7, the image is shown on the left and its invariant isomorphic idempotent representation, normalized to the working range of brightness values (from 0 to 255), on the right.

7 shows that the right image is nothing but a slight increase in sharpness, does not differ from the left, which suggests that the invariant isomorphic representation does not significantly change the image in terms of visual perception.

The invariant isomorphic representation of Hu shown in the drawing, image u, taken as the original image, does not change upon repeated transformation under the action of algorithm H. Therefore, the algorithm H is idempotent:

H = H ² ,

and the image Hu obtained by the algorithm H is an idempotent representation of the original image u.

из одноименной иерархии идемпотентных представлений во всех координатах x выражаются через инвариантное идемпотентное изоморфное представление

рекуррентными соотношениями: Invariant idempotent homomorphic representations

from the hierarchy of the same name idempotent representations in all x coordinates are expressed in terms of an invariant idempotent isomorphic representation

recurrence relations:

,

,

, которое вычисляется итеративным делением числа Mrsn нацело пополам; A - арифметическое преобразование, которое сводится к делению нечетных яркостей текущего представления нацело на 2, а четных - к удвоению амплитудных значений, предварительно поделенных нацело на 4.where Mrsn is the number of gradations of the formal amplitude scale of the representation Hu, expressed by a certain Mersenne number; μ is the number of gradations of the presentation scale

, which is calculated by iteratively dividing the number Mrsn completely in half; A is an arithmetic transformation that reduces to dividing the odd brightnesses of the current representation entirely by 2, and even ones to doubling the amplitude values previously divided entirely by 4.

называются гистограммными образами, в частности, представление Hu именуется изоморфным гистограммным образом.For brevity, invariant idempotent homomorphic representations

are called histogram images; in particular, the Hu representation is called an isomorphic histogram image.

The construction of a histogram image for reversible embedding of a message according to the invention ensures the separation of image pixels into pixels of the visible (calculated) context of the image (container and image stego), the brightness values of which cannot be modified when embedding the message, and pixels with variable brightness.

The histogram image is an invariant representation that is calculated in 1, 3, 7, 15 ... Mrsn gradations of the formal amplitude scale and does not change under standard transformations of the original image. With invariant embedding of the message, the histogram image is used as a container instead of the original image.

A histogram image is computed by iteratively applying a recurrent arithmetic transformation of the amplitude values of the pixels of an isomorphic histogram image, which in terms of the number of gradations encountered coincides with the original image and visually differs from it in increased sharpness. Moreover, the iterative application of the arithmetic transformation gives rise to a hierarchical sequence of histogram images, which in a limited number of 1, 3, 7, 15, ... Mrsn gradations of the amplitude scale represent an isomorphic histogram image in a simplified form. Embedding a message does not affect the initial sequence of histogram images in 1, 3, 7, 15, ..., μ gradations of the amplitude scale.

An isomorphic histogram image is constructed from the histogram of the image in the algorithm for iteratively dividing the histogram into 2 parts with the maximum equal total number of pixels (due to the allocation of the central 3 part with a single non-zero peak in the case of the other two parts with the same number of pixels).

The need to construct an isomorphic histogram image for embedding and retrieving a message is due to the fact that the sequence of partitions of the image brightness scale into ranges calculated by iterative arithmetic conversion of the indicated values is stored in its amplitude values. In this case, the signal (at the transmitting or receiving end) and its histogram image is easier than using the histogram to calculate the sequence of ranges of acceptable brightness variation and embed or extract the message.

In all pixels with non-boundary and off-center brightness values, message bits are encoded by mirroring the brightness values relative to the central value according to the above formula v {x} = a {x} + b {x} -u {x} (for reflection relative to the central value, it is not required calculating the most central value). The outer boundaries a {x}, b {x} of the permissible variation of the brightness values for each pixel are directly determined by the amplitude values of the image approximations from below and above, and the image approximations from below and above are calculated from the histogram image and the image without using a histogram. In this case, building the approximation of the image from below (above) reduces to finding the minimum (maximum) brightness value of the image pixels marked with the same amplitude values of the histogram image (i.e., pixels having the same amplitude values in the representation of the histogram image), and replacing the brightness values of the image pixels with minimum (maximum) brightness values.

Thus, embedding a message in a given channel is performed according to the image and the histogram image by constructing approximations of the image below and above without additional processing of the histogram.

Iterative formation of amplitude values of isomorphic histogram images

The hierarchical sequence of nested partitions of the brightness scale into ranges of permissible variation of brightness values is stored (set) directly in the amplitude values of an isomorphic histogram image, which is formed independently of linear and nonlinear isomorphic transformations, in particular, image packing by brightness. In this case, each amplitude value of the histogram image at one or another iteration marks successive values of the image brightness scale, assigned to the corresponding range of acceptable variation in the brightness of the image pixels, and is found from the amplitude value of the isomorphic histogram image using the recursive arithmetic transformation A, which is defined above.

Taking advantage of the fact that histogram images are independent of the image packaging, we explain the construction of an isomorphic histogram image (and with it the entire hierarchy of histogram images) using examples of brightness-packed images with 7-10 occurring brightness values. For simplicity, we assume that pixels with different brightness occur in the image the same number of times. In this case, the construction of an isomorphic histogram image is reduced to iteratively dividing the brightness scale (in the form of a segment of integer length) into equal parts, which is stored in the amplitude values of the histogram image.

Remembering the hierarchy of partitions of discrete segments.

Fig. 8 illustrates storing a hierarchy of partitions of discrete segments (rows of identical cells) of integer length. Above are the segments under consideration. Below them are the sequential results of iterative coding of the hierarchy of partitions of the image brightness scale into ranges, which are determined by the amplitude values of the histogram images line-by-line written out in the cells.

At the initial iteration, the amplitude values of the histogram image are assumed to be equal to 0 (rows of tables of Fig. 8 filled with zeros). At each subsequent iteration (next table rows), the amplitude value under consideration is doubled and 0, 1 or 2 is added to it, depending on where this value is located - in the left part, in the center, or in the right part of the current range from the same amplitude values . The formation of the amplitude values of the isomorphic histogram image is completed when each of them is different from the neighboring ones. At the same time, the construction of the most isomorphic histogram image is achieved by replacing the brightness of the image pixels with the generated amplitude values. The conversion of the considered matrix representation of the image into an isomorphic histogram image is reduced to replacing the brightness values with amplitude values in the form of numbers that are assigned to the brightnesses while maintaining order, but not necessarily sequentially (Fig. 8). In this case, the resulting histogram image is isomorphic to the image representation under consideration in brightness order. The histogram image, which is obtained by replacing the brightnesses of the image in question with the amplitude values calculated at the intermediate iteration, turns out to be homomorphic to the image in the brightness order. Homomorphic histogram images (or simply histogram images) are obtained from an isomorphic histogram image by recursively applying the division of odd amplitude values entirely by two, and even ones by doubling the result of division completely by four. Moreover, an isomorphic histogram image determines the hierarchy (hierarchical sequence) of intermediate histogram images, each of which can be obtained by applying the arithmetic transformation to the values of the isomorphic histogram image as many times as necessary.

The example of constructing a histogram image for 10 brightness values occurring in a packaged image the same number of times is illustrated in more detail in Fig. 8 on the right, and is explained as follows.

A sequence of brightness values ordered in increasing order is calculated for the brightness scale cells, the number of which in this case is equal to the number of brightness values encountered in the image.

At the initial iteration (the second line in Fig. 8 on the right), zeros are recorded in all cells — the initial values of the amplitudes of the generated histogram image, which are compared with the brightness values of the converted image. At the initial stage, there is only one range of brightness values from 0 to 10, specified by a single sequence of zero amplitude values of the histogram image.

At each subsequent iteration, all amplitude values are doubled. After that, 0, 1 or 2, respectively, is added to each amplitude value, depending on where this value is located - on the left side (closer to the left edge), in the center, or on the right side (i.e. closer to the right edge) of the previous range of the same amplitude values.

Thus, at the first iteration (the third row in Fig. 8 on the right), the sequence of cells is divided into two ranges of equal length and add to the doubled value of the cell of their previous row 0 or 2 for the brightness values to the left and right of the center of the range.

At the second iteration (the fourth line in Fig. 8 on the right), the amplitude values in the whole sequence are doubled (with the values 0 and 4 for the cells to the left and right of the middle of the previous range), after which each of the two ranges (marked 0 and 4) is divided into three parts: two ranges of equal length and a central value equidistant from the left and right edges. Then, in each of the ranges of 5 cells, values 0 and 2 are added for the brightness values in the cells to the left and right of the central cell and 1 for the value of the central cell itself.

At the third iteration (fifth line in Fig. 8), the brightness values of the entire sequence are doubled again, and each range obtained in the previous step is divided into two / three parts, respectively, and the formation of amplitude values is completed, since each resulting range is marked with a non-repeating amplitude the value of the histogram image, i.e. contains a single brightness value.

In this case, the formation of the amplitude values of the histogram image is completed when each of them is different from the neighboring ones. To build a histogram image, it remains to replace the brightness values of the image pixels with the generated amplitude values. Obviously, the finally formed histogram image is isomorphic to the original image, and each of the intermediate ones is homomorphic to the original image.

Fig. 8 should be interpreted as an abstract scheme for computing an isomorphic histogram image, which is built on the brightness histogram. In this case, the addresses of the cells in which the amplitude values of the isomorphic histogram image are formed are the brightness values of the pixels counted along the horizontal axis of the histogram, in which the number of pixels is plotted along the vertical axis. The number of pixels to the left and to the right of the considered brightness value in the general case of an isomorphic histogram image is used instead of the metric length of the row of cells.

The formation of the amplitude values of the histogram image by the histogram

More precisely, the formation of the amplitude values of the isomorphic histogram image is performed in accordance with the algorithm described below, which provides an iterative calculation of the amplitude value of the isomorphic histogram image for each brightness value encountered in the image.

In this case, the brightness values encountered in the image are considered (without taking into account “empty” values with zero peaks of the histogram, since the isomorphic histogram image does not change when the image is packaged, without loss of generality, all brightness values from the operating range can be considered to be found in the image), which are the horizontal axis of the histogram is first marked with zero amplitude values of the histogram image (i.e., each occurring brightness value is associated with an initial amplitude value of the histogram zerogram image).

Then, the ranges of brightness values marked with the same amplitude values of the histogram image are selected, and each of the ranges is processed as the working brightness range of the independent image. Processing consists of doubling the amplitude values of the histogram image and increasing them by 0, 1, or 2 depending on the sum of the peaks of the histogram section under consideration to the left and right of this brightness value. As a result, each sequence of the same amplitude values of the histogram image is divided into 2-3 new sequences, or remains a sequence of one element if it contains a single brightness value. The process of dividing ranges into 1-3 parts iteratively continues until it turns out that all the ranges contain one brightness value.

Processing the range of brightness values at the next iteration consists in the following:

The corresponding (current) value of the histogram image is doubled.

1. The sum of the peaks of the histogram located to the left of the current peak of the histogram is calculated, as well as the sum of the peaks of the histogram located to the right of the current peak (the current peak is not involved in the summation).

2. If the left and right sums coincide, then one is added to the doubled value of the current histogram image. Otherwise, if the left sum of the peaks is less than the right, then the doubled value of the current histogram image is left unchanged, or increased by two, if the left sum exceeds the right one.

Basic iterative embedding of message codes on several channels

Reversible embedding of a message in the next embodiment of the invention is performed using multi-channel ternary memory and consists in cyclic repetition of embedding of a message until the stego image is fully stabilized, upon reaching which the stego image does not change when embedding the message.

The cycle of a single embed of a message consists of a reversible sequential recording of the message codes from the upper digits to the lowest digits with the possibility of retrieval, and is performed in lexicographic order (processing is carried out in stages by channels, and for each fixed channel, all pixels are processed) embed codes by bits × coordinates of the multichannel ternary memory, which corresponds to the lexicographic order of the channels × coordinates (the coordinate changes first, the channels are taken from high to low) encoding I message in the brightness of the image. The multichannel ternary memory is structured and filled bitwise by means of an isomorphic histogram image. The formation of the next discharge of multichannel ternary memory and the encoding of the corresponding embedment channel are described below.

The isomorphic histogram image of the container is calculated (updated), which defines the complete hierarchy of histogram images (to speed up the calculations, you can restrict yourself to calculating the next approximation of the isomorphic image while maintaining the previous approximations). The next number of gradations of the amplitude scale of the histogram image is specified by the Mersenne number, and the isomorphic histogram image is reduced by an arithmetic transformation A to a given number of gradations. Using an isomorphic histogram image, the trits of the multichannel ternary memory are divided into active (modifiable) and inactive (Read Only) ones and their state is set according to the image state and the values of the higher-order trits. By modifying the image, the message codes are recorded in the active trits of the multichannel ternary memory.

Message retrieval from the stego image is performed in one scan cycle of multichannel ternary memory.

When retrieving the message from the stego image, an isomorphic histogram image of the stego image is calculated. In this case, the final histogram image of the resulting container used when embedding the message bits is exactly reproduced. In the absence of distortion during transmission, the separation of the trits into active and inactive is reproduced, and the corresponding message bits are read from the active trits.

биты сообщения с учетом повторений в поле изображения сообщения заранее известных размеров, получают суммарные положительные, отрицательные или нулевые суммарные значения пикселей сообщения, которые интерпретируют, соответственно, как установленные, неустановленные и не определенные биты сообщения в виде числовой матрицы. Если контейнер представляет собой изображение из пикселей с одинаковыми значениями яркости («чистый лист»), то все биты встроенного сообщения оказываются неопределенными. Если битов сообщения оказывается больше, чем тритов рассматриваемых младших разрядов многоканальной памяти, то «лишние» биты не используются.To suppress possible distortions, decoded in the form of

the message bits, taking into account the repetitions in the message image field of predetermined sizes, receive the total positive, negative or zero total values of the message pixels, which are interpreted, respectively, as set, undefined and undefined message bits in the form of a numerical matrix. If the container is an image of pixels with the same brightness values (“blank sheet”), then all bits of the embedded message are undefined. If there are more message bits than the trits of the lower-order bits of the multichannel memory under consideration, then the "extra" bits are not used.

Full-color 24-bit images are considered as three 8-bit grayscale images and when embedding, as well as when extracting messages, they are processed according to color components independently of each other.

Options

).To control the embedding of messages in real time, an initial separation of image pixels according to gradation of the histogram image into subsets is provided, which are further processed as separate images. The control parameter is the Mersenne number μ, which determines the total number of gradations of the histogram image scale, which is used for the initial image division (by default, we set the parameter μ to be

)

в виде числа Мерсенна, который задает число градаций шкалы гистограммного образа, используемого для замещения изображения инвариантным представлением.In case of invariant iterative embedding (see below), a similar parameter is added to the specified parameter

in the form of the Mersenne number, which sets the number of gradations of the scale of the histogram image used to replace the image with an invariant representation.

шкалы градаций гистограммного образа, предусмотренного для представления изображения в инвариантном виде, а также числа градаций μ шкалы градаций гистограммного образа, используемого для начального разделения множества пикселей на несколько самостоятельных множеств, в изобретении предусматривают параметр

, равный количеству старших каналов, которые при записи сообщения фиксируются и модулируют начало отсчета в остальных каналах, сопоставляемых вложенным диапазонам яркости (по умолчанию значение

полагают равным единице

, при котором начальные значения активных тритов младших разрядов отождествляются со значениями самого старшего разряда).In addition to the number of gradations

gradation scales of a histogram image provided for representing the image in an invariant form, as well as the number of gradations μ gradation scales of a histogram image used for the initial division of a set of pixels into several independent sets, the invention provides a parameter

equal to the number of senior channels that, when recording a message, are fixed and modulate the origin in the remaining channels associated with nested brightness ranges (by default,

assumed equal to unity

at which the initial values of the active trits of the lower digits are identified with the values of the highest rank).

Idempotent embedding of message codes on several channels

The time-efficient idempotent embedding of a message in an image is achieved in a single iteration if in the previous method a ternary memory with a continuous structure is formed, i.e. with the lack of alternating active and inactive trit. For this, during the formation of the ternary memory structure (from the highest to the lowest), when calculating the first inactive trit in this coordinate, all the trites of the lower digits compared to this coordinate are considered inactive.

Invariant iterative embedding of message codes on several channels

For invariant embedding of a message in an image, it is preliminarily replaced with its homomorphic, in particular, isomorphic image. Moreover, even with a continuous structure of ternary memory, the idempotency of embedding is generally lost, but iterative repetition of embedding ensures the convergence of the result to the desired stego image. A prerequisite for the accurate construction of a stego image in a converging transformation algorithm, in which it stops changing, is the brightness packing of a homomorphic histogram image, which replaces the image before embedding the next message codes.

Iterative robust embedding of a message with available perturbation of the stego image

With a previously known and accessible perturbation of the stego image, for example, JPEG conversion, embedding the message with the existing executable program module for generating perturbation of the stego image, the robustness of the message built in according to the invention is increased by cyclically applying the embedding of the message alternately with the perturbation. Moreover, the exact convergence of the result of iterative embedding of the message after the disturbance, generally speaking, is violated, i.e. the result of iterative application of both transformations in turn is a looping sequence of stego images, one of which is selected as the result of embedding.

In other words, with an iterative repetition of the processing cycle in the form of embedding a message after a perturbation at some iteration, a stego image is obtained that coincides with one of the previously received stego images. Further, when the processing is repeated, the following stego images will obviously be reproduced in a closed sequence. As the resulting stego image, one of the stego images of the specified sequence is selected.

Examples

The invention was developed in the process of program experiments to implicitly embed a message in 8-bit grayscale and 24-bit full-color images processed by color components as three independent grayscale images.

The main goal of the work was to verify the technical feasibility of the ternary multichannel memory option described in the invention, namely, the possibility of storing in all its active trites arbitrary codes of a multicomponent message from several independent bit planes. At the same time, as a prerequisite for embedding a message in multichannel memory, the condition of invariance of the stego image during repeated embedding of the message was checked, and the invariability of the container (arbitrary image) when the previously extracted message was back embedded into it.

An additional goal of the experiments was to test the method of invariant embedding of a message in a container, regardless of standard transformations of the stego image (packaging, stretching, equidistant normalization by brightness, etc.).

When solving the problem of embedding an arbitrary message in the image, the latter considered options for the grayscale representation of the message generated by some grayscale matrix with sizes smaller than the corresponding image sizes. Due to the periodic repetition of the bits of the grayscale matrix of the message in terms of coordinates and brightness ranges, the case of reaching the end of the recorded message was excluded, however, it was assumed that, depending on the container, some bits of the message representation are not placed in the container and are considered undefined during reading (as well as during writing).

The embedding of message bits with repetitions was performed due to geometric repetition in the image field of the initial grayscale matrix of the message as a whole, as well as its shift in brightness. At the same time, the dimensions of the binary message matrix and its bit depth are parameters that must be specified when receiving.

The correctness of the calculations, in particular, the convergence of the algorithms was controlled by embedding by directly extracting the message bits from the image stego and comparing their values with the required ones.

Data structure

A software implementation of the invention using three coding systems (in binary and ternary number systems, as well as coding in an intermediate pseudo-ternary system) is a rather complicated logical task, if the processing is presented in terms of the conversion of the original image pixels. The software implementation of the algorithms is greatly simplified thanks to the use of a debugged module for generating and storing in a pseudo-ternary coding system for the hierarchy of histogram images, by which intermediate and output matrix representations of the image are calculated. In this case, the main matrix representations of the image, calculated by the image, are (in order of priority of calculations):

- Representation of the image in the form of an isomorphic histogram image, which defines the hierarchy of (homomorphic) histogram images (formed in a pseudotrope coding system);

- Approximations of the image below and above, limiting the allowable ranges of variation in brightness of the image pixels;

- A structural representation of multichannel ternary memory, which defines the separation of trites into variable and fixed ones (formed in a binary number system);

- Numerical representation of multichannel ternary memory for storing message codes and fixed trit codes (generated in the ternary number system).

In addition, to fix pixels, the modification of which entails distortion of previously built-in message trits, an array of double values of central brightness of ranges is used. In the indicated array, as each next partition of the brightness scale is calculated on the scale of doubled brightness values, they are marked (by the current channel number), and depending on the channel number, the total values of the boundary brightnesses of the ranges are accumulated.

For the experimental implementation of the invention, variants of a program for hiding the superposition of bit messages in varying trits of multichannel ternary memory, calculated for each of the RGB image components independently of other components, have been created.

The experimental results are given below.

Experimental results

The results of program experiments are demonstrated by embedding messages in the form of halftone image codes (Fig. 9) into containers in the form of a standard Lena halftone image of 256 × 256 pixels in size, as well as a full-color image of 512 × 512 pixels in size (Figure 10).

Fig.9 illustrates the original message, which is taken as a sequence of drawn numbers and other characters of 51x82 pixels each, packed with overlapping in the bit planes of a grayscale image. Due to the periodic repetition of the message picture by coordinates and, if necessary, by brightness channels, the embedding of message codes continues until the multichannel ternary memory is full.

10 illustrates contemplated halftone and color containers. The standard Lena image is shown on the left, and the color image on the right is reduced.

For simplicity, the same message is repeated in all color components of a full-color image, repeating in color.

Basic iterative embedding of message codes on several channels and the effect of continuous ternary memory with idempotent embedding

11 shows the result of adaptive embedding of a message using the basic iterative embedding method over several channels, the number of which depends on the container and usually exceeds the number of brightness bits in the original image.

In the second row of FIG. 11, a structural and numerical representation of a multi-channel ternary memory is shown. The structural representation of multichannel ternary memory defines in bits of the binary representation of amplitude values the separation of trits into active and inactive. At the same time, the set bits of the structural representation for each image pixel specify the active, and unset bits set the inactive trites of the multichannel ternary memory. In the case of continuous ternary memory, the amplitude values of the pixels of each color component simply show the number of active trit mapped to the pixels - the larger the amplitude value, the more message bits are embedded with each other superimposed into this pixel. The brightnesses of the numerical representation of the ternary memory calculated in the ternary number system indicate the sequence of trites, which is mapped to each pixel of the image. Compared to the structural representation, the numerical representation of the ternary memory is more similar to the stego image and under certain conditions (when invariantly embedding a homogeneous message in the form of a “blank sheet” of bits with the same values) coincides with it up to an isomorphic transformation. Both views are calculated for the source container.

In the components of an embedded message, gray pixels indicate message bits that cannot be stored in multichannel memory and are calculated as bits with an undefined value. In the upper row of FIG. 11, a container is shown as a full-color 24-bit image (left) and a stego image (right). The second row shows the structural and numerical representations of multichannel ternary memory (left and right, respectively). The bottom of this drawing shows a sequence of reversibly embedded message bit planes.

The structural representation in FIG. 11 is calculated without taking into account the continuity condition of the multi-channel ternary memory and contains, according to the R, G, B components, 11, 13, 13 tones, respectively (in the continuous structural representation, 5, 4, 5 tones are obtained, respectively). For clarity of embedding, the calculations were performed by dividing the working brightness range by means of a histogram image in only three gradations of the amplitude scale (μ = 3) and a single fixed senior channel (f = 1), which is used to set the initial brightness positions in the remaining channels adaptively to the container. As μ or f increases, the embedding ceases to be detected.

In the stego image of FIG. 11, the drawn numbers embedded in the upper channels overwrite the numbers embedded in the lower channels. By carefully examining the image, you can distinguish between two components of the message in the form of drawn numbers. It should be noted that the modern theory of image processing, in addition to comparison with the standard, does not have obvious approaches to solving the problem of automatically detecting image areas where the figure recorded in the lower channel is noticeable. The multichannel ternary memory model provides an experimental study of the occurrence of messages from different channels on the image of information and allows them to be interpreted in terms of the distribution of active and inactive trites of multichannel memory representations by coordinates, channels and colors, which is of independent interest for steganography, as well as for modeling and automation visual perception.

(сверху вниз). Слева на чертеже иллюстрируются результаты итеративного встраивания сообщения при формировании троичной памяти без учета условия непрерывности, справа - результаты идемпотентного встраивания сообщения в многоканальную троичную память с непрерывной структурой.Fig. 12 allows you to compare the results of reversible embedding of the message when forming the structure of the multichannel ternary memory with and without taking into account the continuity condition, which shows the influence of the continuity condition of the ternary memory on the multichannel embedding of the message at the initial partition of the operating range with the parameter

(top down). On the left in the drawing, the results of iterative embedding of the message when forming the ternary memory without considering the continuity condition are illustrated, on the right are the results of idempotent embedding of the message in a multichannel ternary memory with a continuous structure.

The experimental results are still presented for a single fixed channel (f = 1), but several initial partitions of the working range of image brightness by μ = 1.3, and 7 gradations of the histogram image scale. As the experiment shows, ternary memory channels during iterative embedding of a message are used much more efficiently, which is explained by a random distribution of active trits of the lower digits by coordinates, which compensates for the missing bits of the embedded message due to the correlation of the contents of the message and the container. Both methods of iterative and idempotent embedding of the message are characterized by the “echo” effect of high channels in low channels, in which the outlines of the picture embedded in the high channel appear in the boundary lines of the bits with an undefined value indicated in gray. The indicated effect is somewhat more pronounced with idempotent embedding into continuous ternary memory and is explained by correlated information in various channels.

Embed volume

The results of calculating the embedment volume for the standard “Lena” grayscale image when forming a multi-channel ternary memory with and without taking into account the continuity condition are given in Table 2 for a homogeneous message consisting of all the same bits.

table 2
Experimental data on embedding a homogeneous message in a standard Lena image (64 Kb) Trinity memory with alternating active and inactive trit Continuous structure ternary memory μ Ch Max number of active trits per pixel t _max Active Volume I (Bytes) Ch Max number of active trits per pixel t _max Active Volume I (Bytes) one 9 four 24682 9 four 21612 3 10 3 19233 12 3 14566 7 9 3 17767 eleven 3 16031 fifteen 8 3 13897 10 3 13078 31 8 3 10390 10 3 10124 63 8 3 5348 9 2 5218 127 8 3 1333 8 3 1298 255 8 2 200 8 2 193 511 8 2 66 8 2 64 1023 7 2 21 6 one 19 2047 6 2 13 5 2 12 4095 5 2 four 5 2 four 8191 3 one 2 3 one 2 16383 2 0 0 2 0 0

where: μ is the maximum number of ranges of the initial partition of the image brightness scale; Ch is the number of channels.

Table 2 discusses the characteristics of multichannel ternary memory depending on the partition of the working brightness range into several initial ranges by means of a histogram image in μ gradations of amplitude. If by I {x} we mean the number of active trites mapped in the x coordinate to the image pixel, then the active volume I of multichannel ternary memory and the maximum number of active trites t _{max are} expressed by the relations:

I{x}t _max =

I {x}

I{x} (бит),I =

I {x} (bit),

As follows from the table, the embedding volume, identified with the active volume I, is estimated at 20-30%. The number of Ch channels can exceed the bit depth (number of bits) of brightnesses of the original image, which is 8. in the case under consideration. In the general case, the number of active trites in a cell of multichannel ternary memory can also exceed the bit depth of the initial brightness representation of the image.

As the experimental results show, a significant decrease in the active volume (the total number of message bits and the number of bits that specify the initial state) is not observed, probably due to a small fraction of active trit, which, in violation of the continuity condition, alternate with inactive trit in the lower bits of the multi-channel ternary memory. Since the idempotency of embedding messages, achieved under the condition of continuity, increases the speed of program execution and, most importantly, significantly simplifies the programming logic, the continuity of ternary memory in the theoretical description should probably be attributed to its attributes.

Invariant embedding of message codes on several channels

13 illustrates the invariant embedding of a message from superimposed digits into luminance-packed histogram images of a standard Lena image of 256x256 pixels in size with continuous multi-channel ternary memory and a single fixed channel (f = 1).

The results are given for the initial values of the parameter μ ₁ = 15, 31, 63, which limits the number of possible gradations of brightness of the histogram image under consideration, and the parameter μ = 1, 3, 7, which limits the number of independent brightness ranges into which the working brightness range is formally divided.

13 illustrates a multi-channel invariant embedding of a message in a ternary memory while reducing the number of gradations of brightness of the stego image. 13 contains two triangular tables composed of images. The first table (on the left) is composed of stego images, and the second (in the upper right corner) is made up of embedded messages, the components of which are figures of numbers embedded in various channels.

The axes show the values of the parameters μ ₁ = 15, 31, 63 (from top to bottom) and μ = 1,3,7 (from left to right). Stego images are arranged in a triangular table on the left. In the upper right corner is a table of relevant messages. Images are equidistantly normalized by brightness to the operating range.

The extreme upper stego image obtained with the parameter μ ₁ = 15 has 8 gradations of brightness, the rest in the same column have 14 and 20 gradations (with parameters μ ₁ = 31 and μ ₁ = 63, respectively). When moving from view to view along the main diagonal, the number of gradations in the stego image approximately doubles.

A limited number of gradations in the stego images allows you to make sure that the message is saved during standard brightness transformations (packing, stretching, etc.) through the system editor.

It is characteristic that during the transition from presentation to presentation along the descending (main) diagonal and a coordinated change in the discussed parameters, the message components contained in the various channels and the message itself remain almost unchanged. However, at the same time, with increasing parameters μ and μ _{1, the} visible message components are “lost” in the masking picture, which is useful for controlling the embedding of a given message. Optimal message hiding is achieved in the boundary case when the message is actually embedded in the lowest channel.

For images with a sufficiently large number of channels of ternary memory, its junior channel is conveniently used for information accompanying the fact of hiding the message, for example, in tasks of monitoring information leakage, including hidden in other channels of ternary memory.

An example of iterative robust embedding of a message with an available perturbation of the stego image

With an iterative repetition of embedding a message, it becomes possible to obtain a stego image that is resistant to the provided image modification. In particular, modifying a stego image can mean embedding a fixed message with a “foreign” program with an unknown algorithm operating on the basis of a “black box”. In the context of general application, robust (stable) embedding of messages regarding the conversion of images into JPEG-format and vice versa is of interest, which can be provided by iterative repetition of the procedure for modifying and embedding the desired message in the stego image.

We illustrate the effect of iterative embedding using an example of a homogeneous message in a standard Lena image with an intermediate effect on the stego image of conversion to JPEG format and vice versa (with compression 12 times with the value of the control parameter equal to 15).

As the experiment showed, the algorithm for cyclic image conversion by embedding a message in turn with a JPEG conversion in a third dozen iterations is looped. However, from a practical point of view, we can assume that the maximum stego image is achieved, since the resulting repeating sequence contains only a couple of images, and the cyclic changes in brightness are limited to several cell fields 8 x 8 pixels in size.

Improving the stability of the stego image to JPEG conversion by repeatedly repeating the embedding of the message is illustrated in Fig.14. In the upper row on the left is the initial and on the right is a stego image adapted to JPEG conversion. In the lower row on the left is a histogram of the brightness changes of the stego image with a uniform message; on the right is a histogram of the brightness changes in the stego image after repeatedly embedding the homogeneous message in turn with JPEG transforms.

A standard image with a single and multiple built-in homogeneous message is shown in the representations in Fig. 14, respectively, in the upper left and right corners. Below are the brightness histograms of the difference patterns obtained through the PhotoShop editor. The results of the calculation of the mean and rms changes in brightness, which, due to repetitions of embedding the message, decrease several times, are also given there. Moreover, as a result of repeated embedding, the stego image with the integrated homogeneous message, which does not change when it is re-embedded, practically does not change under the influence of JPEG transforms either.

Similar results are obtained on other images (including color). In this case, the limit sequence of representations cyclically transformed into each other is usually achieved within 100 iterations. When the conversion results are looped, stabilization of the number of active trites modified when recording messages is observed, which is convenient to use when automatically establishing the fact of the loop.

Environment for implementing the present invention

The description of an exemplary working environment for implementing the present invention is only one example of a suitable computing environment and is not intended to impose any restrictions on the use or functionality of the invention.

The invention may be described by computer-executable software modules. Typically, program modules include routines, programs, data structures, etc. that perform specific tasks. In addition, it will be understood by those skilled in the art that the invention can be applied to a variety of computer system configurations, including portable devices, multiprocessor systems, minicomputers, general purpose computers, and the like. The invention can also be applied in distributed computing environments by performing operations on remote processing devices that are connected through communication networks. In a distributed computing environment, program modules may be located on both local and remote memory storage devices.

An example system for implementing the invention includes a general-purpose computing device in the form of a computer including a processor (processing means), system memory, and a system bus that connects various components of the system, including system memory and processor.

A computer typically includes a variety of computer-readable media. By way of example, and not limitation, computer-readable media may include computer memory media and communication media. Examples of computer memory media include random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technologies, CD-ROM, DVD ROM, or other types of storage devices .

The computer may also include other computer storage media, for example, a hard disk drive, a magnetic disk drive, an optical disk drive, and others. Storage devices are usually connected to the system bus using appropriate interfaces that are obvious to those skilled in the art.

The user can enter commands and information into the computer through input devices (means), for example, a keyboard, pointing device, such as a mouse or touchpad, means for receiving an input radio signal, etc. Other input devices may include a microphone, joystick, antenna, scanner, etc. These and other input devices are connected to the processor via the corresponding input device interface.

The display device (means) is also connected to the system bus via an interface, for example, a video interface. The display means may be any means of displaying the output: a monitor, a liquid crystal screen, a conventional television, or a screen projector. In addition to the display means (device), the computer may also include other peripheral output devices, such as a printer, which can be connected via the interface of the output devices.

The computer of the present invention can operate in a network environment using connections to one or more remote computers. Connections include a local area network and a wide area network, but may also include other networks, such as the Internet. Those skilled in the art will recognize that such components and reciprocal compounds are well known.

As mentioned previously, the present invention can be described by computer-assisted operation programs. Computer-used instructions include functions, procedures, routines, program segments, and modules used by one or more computers or other devices. The instructions used by the computer form an interface to enable the computer to respond in accordance with the input. The instructions interact with other program segments to initiate a variety of tasks in response to data received together with the source of received data.

However, the present invention can also be implemented using only computer hardware, for example, realizing processing units (means) in the form of specialized integrated circuits based on programmable logic arrays and the like, as is obvious to those skilled in the art.

All possible embodiments of the invention in the form of software, hardware and software and hardware are covered by the claims, and are not limited to any one implementation example.

Claims (5)

1. A method of embedding a plurality of messages in a digital image by changing the brightness of the pixels of said image in a system comprising input / output means and a processing means comprising the steps of: a) receive the image and the message to be embedded in the processing means from the input means for performing the embedding on one channel; b) represent the message bits in the form of matrix elements having arbitrary values greater than or less than zero, mapped to the bits of the embedded message with a non-zero and zero value, respectively; c) iteratively divide the brightness scale of the entire image into consecutive ranges, with each range at each iteration: they are either divided into two ranges with the maximum number of pixels closest to each other, or into two ranges with the maximum number of pixels closest to each other and the allocation of a central range containing a single brightness value, or left unchanged if it contains a single brightness value, to obtain multiple ranges containing one brightness value; d) for each of the ranges obtained at one of the intermediate iterations, image pixels with maximum and minimum brightness values and pixels with a central brightness value are determined and these pixels are assigned to the image component that does not change when the message is embedded, while for ranges with a single brightness value maximum or minimum, as well as central, brightness values are assumed to be the same, and the remaining pixels are attributed to the variable component of the image, e) embed each bit of the message in the current pixel of the variable image component by the following operation: accept the brightness of the pixel as a pixel containing a bit of the embedded message, if the sign of the difference in the brightness value of this pixel and the central brightness value of the range to which the mentioned pixel coincides with the sign of the matrix element corresponding to the embedded message bit, and if the said signs do not match, the pixel value of the image is assigned a brightness value of the pixel by mirroring the value of its brightness relative to the central value of the said range, e) receive the next message to be embedded in the next channel, and perform steps b) -e) to embed this message in the image obtained in step e) after embedding the previous message, and in step d) the component that does not change during embedding of the message is also the brightness values of pixels, the change of which changes the bit value of a previously embedded message, wherein the embedding of messages is performed until the image is fully stabilized with the built-in messages, g) display the resulting encoded image with embedded messages on the output means. 2. The method according to claim 1, characterized in that when assigning a pixel to an unchanging component of the image at the current iteration, it is attributed to the unchanging component of the image at all subsequent iterations, and embedding messages is achieved in one cycle. 3. The method according to any one of claims 1 and 2, characterized in that when embedding the message, the image is converted into an invariant idempotent brightness homomorphic representation that is packed in brightness, the embedding conversion procedure is cyclically repeated until an idempotent stego image is obtained. 4. The method according to any one of claims 1 and 2, characterized in that the construction of the stego image robust to the modification of the stego image available when embedding a message is iteratively repeated alternately with the specified modification until an unchanged sequence of stego images is obtained, from which the option is selected required stego image. 5. A method for extracting a plurality of messages from a digital image embedded by changing the pixel brightness of the image in a system comprising input / output means and a processing means comprising the steps of: a) receive an image with embedded messages in the processing means from the input means; b) iteratively divide the brightness scale of the entire image into consecutive ranges, with each range at each iteration: they are either divided into two ranges with the maximum number of pixels closest to each other, or into two ranges with the maximum number of pixels closest to each other and the allocation of a central range containing a single brightness value, or left unchanged if it contains a single brightness value, to obtain multiple ranges containing one brightness value; c) the image pixels with maximum and minimum brightness values and pixels with a central brightness value are determined and these pixels are classified as an image component that does not change when the message is embedded, while for ranges with a single brightness value, the maximum or minimum, as well as the central brightness values are the same, and the remaining pixels belong to the variable component of the image, d) the message bits are extracted from each current pixel of the variable image component by the following operation: take a message bit value equal to 1 if the difference in the brightness value of this pixel and the central brightness value of the range to which the said pixel belongs is greater than zero, and equal to 0 otherwise, e) perform steps b) -d) to extract the next message from the image obtained in step d) after extracting the previous message, and in step c) the pixel brightness values also belong to an unchanging component, the change of which changes the bit value of the previously extracted message, at the same time, the extraction of messages is performed until all nested brightness ranges are exhausted, g) output the extracted messages to the output means.

Images