Image analysis – Applications
Reexamination Certificate
2001-01-08
2004-11-16
Mehta, Bhavesh M. (Department: 2621)
Image analysis
Applications
C713S176000
Reexamination Certificate
active
06819774
ABSTRACT:
The present invention concerns a method of determining a segmentation of a set of coefficients representing at least part of a digital image in order to insert and extract a set of watermarking signals, and an associated method of inserting and extracting these watermarking signals.
Correlatively it concerns a device for determining a segmentation of a set of coefficients representing at least part of a digital image in order to insert and extract a set of watermarking signals and an associated device for inserting and extracting these watermarking signals.
The present invention lies in general terms in the technical field of watermarking of digital images, more particularly fixed images.
Watermarking digital data makes it possible to protect these data, for example by associating copyright information therewith, or conveying added value data, such as metadata.
In its general principle, watermarking consists of inserting an indelible watermark in digital data, similar to the encoding of additional information in the data.
The decoding of this additional information makes it possible, for example, to check the copyright information inserted.
This inserted watermark must consequently be at the same time imperceptible, robust to certain distortions applied to the digital image and capable of reliable detection.
In a conventional fashion, a usual technique of inserting a watermarking signal in a digital image consists of using a modulation model in which at least one subset of coefficients representing the digital image is modulated according to this model using a weighting coefficient.
Denoting a set of coefficients representing at least part of a digital image as X={X
i
, 1≦i≦N} and a watermarking signal of size P≦N as w={w
j
, 1≦j≦P}, a pseudo-random signal of known distribution and null mean, the insertion formula is:
X′
j
=X
j
+b.&agr;
j
.w
j
with 1
≦j≦P,
in which {X
j
, 1≦j≦P} is a subset of the set of coefficients X, b is an information bit, and &agr;
j
is a weighting coefficient, also referred to as modulation amplitude.
Detection of the watermarking signal then consists of detecting whether or not the pseudo-random sequence w has been inserted in a set of coefficients. This detection is carried out without using the original image and can be based on a standardised statistical test which makes it possible to calculate a probability of detection.
Such an insertion technique makes it possible, by inserting a watermarking signal, to insert a single information bit since the response of the detector is binary (yes
o). Typically, in order to insert a binary signal, either b=1 or b=−1 is used, depending on whether the value of the bit to be inserted is zero or one.
In order to insert a larger number of information bits in the digital image, in particular when a code of C bits indicating for example the name or address of the owner or author of the image is required, it is necessary to reiterate the insertion method described previously as many times as there are information bits to be inserted.
In other words, it is necessary to choose C subsets of coefficients and effect the modulation of these subsets by choosing C watermarking signals.
Preferably distinct subsets of coefficients are chosen so that the modulations are not superimposed on each other, which could interfere with the detection or cause unwanted visual effects.
It is consequently a question of choosing a partitioning of the coefficients representing the digital image into C distinct subsets, each carrying an information bit.
Methods are known for the arbitrary partitioning of the set of coefficients, into blocks, independently of the content of the digital image.
However, the content of the images is not spatially homogeneous, which gives rise to unequal probabilities of detection for the detected bits, and consequently a probability of global error on the inserted message which cannot be minimal. It is therefore advantageous to determine a partitioning which is adapted to the image. In this case, if it is wished to insert a predetermined number C of watermarking bits, it is also necessary to minimise a probability of error at the time of extraction of the watermarking signals.
The purpose of the present invention is to propose a method of determining a partitioning of the signal to be watermarked, whilst minimising a probability of error in the detection of the predetermined number of watermarking signals.
To this end, the invention proposes a method of determining a segmentation into distinct regions of a set of coefficients representing at least part of an image in order to insert a set of watermarking signals with a predetermined cardinal, characterised in that it includes the steps of:
generating a set of acceptable segmentations,
calculating, for each acceptable segmentation, a probability of error on the detection of the watermarking signals inserted in said each acceptable segmentation, and
selecting a segmentation in the set of acceptable segmentations, by minimising, on all the acceptable segmentations, the probability of error subject to a constraint on the cardinal of the regions of the selected segmentation, with respect to the cardinal of said set of watermarking signals.
It is thus possible to effect a segmentation of a set of coefficients into distinct regions, effecting adaptive partitioning which minimises a probability of error in the detection of the predetermined number of watermarking signals.
According to a preferred characteristic of the invention, said set of coefficients is a set of transformed coefficients issuing from a spatial-frequency transformation of a digital image. This type of transformation is frequently used in image processing.
According to another preferred characteristic of the invention, the acceptable segmentations are obtained by arborescent segmentation of the coefficients representing at least part of an image.
According to a preferred characteristic of the invention, the acceptable segmentations are obtained by segmenting into a quaternary tree the coefficients representing at least part of an image.
This implementation is rapid and has low calculation complexity.
According to a preferred characteristic of the invention, each of the watermarking signals is associated with a watermarking bit and the probability of error on the detection of the watermarking signals is the probability of making at least one error on a bit during the detection of the watermarking bits.
According to a preferred characteristic of the invention, the minimisation of the probability of error includes a maximisation of a separable quantity and the selected segmentation is obtained by pruning an arborescent segmentation.
According to a preferred characteristic of the invention, the constraint of the optimisation step is that the cardinal of the regions of the selected segmentation is greater than or equal to the cardinal of said set of watermarking signals.
According to a preferred characteristic of the invention the method of determining a segmentation comprises a step of applying a distortion to the set of coefficients, before the step of generating a set of acceptable segmentations.
In this embodiment, the method comprises more precisely the steps of:
generation of a centred pseudo-random sequence (w) equal in size to the cardinal number of the said set of coefficients, formed from centred pseudo-random sub-sequences;
modulation) of the said set of coefficients by the said centred pseudo-random sequence in order to insert the same information bit on the said set of coefficients; and
applying a distortion to the set of coefficients, before the step of generating a set of acceptable segmentations.
This embodiment allows to enhance the robustness of an inserted watermark, against some post-processing undergone by the image.
According to a preferred characteristic of the invention, the method also includes the display of the probability of error on all the watermarking signals.
This pr
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Mehta Bhavesh M.
Tabatabai Abolfazl
LandOfFree
Determination of a segmentation of a digital signal for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determination of a segmentation of a digital signal for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determination of a segmentation of a digital signal for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3333659