WO2004015590A2 - Robust detection of a reference image during major photometric transformations - Google Patents

Abstract

The invention relates to a method and a system for identifying a specific image (11) within a flow (3) of images (6). The inventive system comprises means for calculating a reference index (10) of the specific image (11) and means for calculating (43) the current indexes (14) of the current images (13) of said flow (3). The index (14) has the form of an ordered and finite set (21b) of values encoding the content of the current image (13). The system also comprises means (44) for comparing said reference index (10) with the current index (14) of the current image (13) of the monitored flow (3). The inventive method and system make it possible to detect a specific image (11) within a flow (3) with great precision and extremely fast while being robust during very large photometric alterations.

Description

 DETECTION OF A ROBUST REFERENCE IMAGE WITH LARGE PHOTOMETRIC TRANSFORMATIONS

Preamble to the description

Field concerned, problem posed

The present invention relates to a method and a system for identifying a determined image and / or a determined audiovisual sequence in any stream of images or audiovisual sequences, in particular with a view to being able to identify a proprietary image in the stream and / or be able to identify, preferably in real time, several proprietary audiovisual sequences in the stream.

In the field of monitoring protected audiovisual content, one of the problems concerns the identification of a proprietary video sequence when it is broadcast. Since a video sequence is a series of images, solving the problem involves being able to detect and identify a particular image (called the reference image) in real time, while being robust to a certain number of photometric transformations which can affect the image. during its broadcast.

The solution to this problem:

- must be robust to small differences in characteristics, - must allow rapid calculations,

- must have a strong discriminating power.

Solution The process according to the invention

The method comprises the step of calculating, for each image, an index in the form of an ordered and finite set of values, in particular in the form of a characteristic vector, coding the content of the image. The index calculation process is hereinafter referred to as the indexing process.

The method comprises the following steps implementing the indexing process:

the step of calculating a reference index, by implementing the indexing process for the determined image, or

the step of extracting reference indexes from the determined audiovisual sequence, so as to compose a reference set of reference indexes.

This gives reference indices characteristic of the determined image and / or of the audiovisual sequence determined.

The method further comprises the step of calculating an index, for current images of the stream, by implementing the indexing process for the current images of the stream. The index thus calculated is hereinafter referred to as the current index.

The method includes the step of comparing the reference indexes with the current index of the current image of the observed flow. It is thus possible to detect in a flow a determined image with very high precision, in an extremely rapid manner, while being robust to very strong photometric alterations.

Indexing process

Preferably, according to the invention the method is such that, to calculate an index of an image, in particular a reference index and / or a current index, it comprises the step of resampling the image into an image with fixed dimensions through advanced. The resampled image is hereinafter referred to as the normalized image.

The method further comprises, in the case where the image is a color image comprising color levels, the step of converting beforehand the color levels of the image to be resampled into gray levels.

The normalized image is represented by a matrix of pixel values, after discrete quantization of the pixel values.

The method further comprises the step of arranging the values according to an order of predetermined traversal of the positions in the matrix, in particular by concatenating the values of each line of the matrix in the form of a characteristic vector. This vector makes up the index.

Preferably, according to the invention the method further comprises the step of calculating the discrete entropy of the ^dispensing of the reference index values or index stream. The entropy is hereinafter referred to as the reference marginal entropy or the current marginal entropy.

By doing so we optimize the comparison time.

The index can be completed with the marginal entropy value.

Calculating an index comparison distance

Preferably according to the invention, the indexes are in the form of ordered and finite sets of values. These values are identified, in the reference index and the current index, by a coordinate system.

The method further comprises the step of defining, for a given coordinate of the coordinate system, a pair of values:

- whose first value is the value appearing in the reference index associated with the given coordinate, and

- whose second value is the value appearing in the current index associated with the given coordinate. The method further comprises the step of calculating the two-dimensional histogram of the pairs of values obtained for all the coordinates of the coordinate system of the reference index and of the current index.

The method further comprises the step of calculating the discrete entropy of said two-dimensional histogram, hereinafter called the entropy of the two-dimensional histogram.

The method further comprises the step of calculating a comparison distance between a reference index and a current index by forming the ratio between, to the numerator, the sum of the reference marginal entropy and the current marginal entropy reduced by l entropy of the two-dimensional histogram, and in the denominator the sum of the reference marginal entropy and the current marginal entropy.

Reference index extraction

Preferably according to the invention, the method is such that, to extract from the determined audiovisual sequence the reference indexes of the determined audiovisual sequence, it further comprises the step of initializing a reference set containing the reference indexes of the determined images. This set is initialized with the reference index of the first determined image of the determined audiovisual sequence. The reference index of the first determined image of the determined audiovisual sequence constitutes the first reference index of the reference set.

The method further comprises:

- (a) the step of calculating, for each determined image of the determined audiovisual sequence, a current temporary index and of calculating a comparison distance between the current temporary index and the last reference index added to the reference set,

(b) the step of comparing, at a predetermined threshold SE, the comparison distance between the current temporary index and the last reference index added to the reference set, - (c) the step of adding the current temporary index to the reference set, if the comparison distance exceeds the predetermined threshold SE.

The current temporary index becomes the last reference index of the reference set.

The method further comprises the step of iterating steps (a) to (c) until the end of the determined audiovisual sequence.

Detection

Preferably according to the invention, the method is such that, to compare the reference indexes with the current index of the current image of the observed flux, it further comprises the step of comparing the comparison distance with a predetermined threshold SF. So that the determined image is detected in any stream of images when the comparison distance between the reference index of the determined image and the current index is less than the predetermined threshold SF.

According to another alternative embodiment - of the invention, the method is more particularly designed to detect a given audiovisual sequence in any stream of audiovisual sequences. Preferably in the case of this alternative embodiment, the method comprises:

- (a) the step of initializing a variable T to - 1 and of initializing a variable D to 0,

- (b) the step of calculating, for each reference index of the reference set, the comparison distance between the reference index of the reference set and the current index.

If the comparison distance thus calculated is less than a predetermined threshold SD the variable D is incremented by one. This condition is hereinafter referred to as the reference index detection condition.

The instant at which the first reference index of the reference set of the determined audiovisual sequence satisfies the detection condition is referred to below as the time of the first detection.

The method further comprises the following steps:

- (c) the step of assigning to the variable T the time elapsed since the instant of the first detection if the variable D is other than zero,

- (d) the step of iterating step (b) until the variable D reaches the predetermined threshold SD, or of iterating step (a) if the variable T exceeds a predetermined threshold ST,

- (e) the step of detecting the audiovisual sequence determined if the variable D reaches the predetermined threshold SD.

The system according to the invention The system comprises:

first calculation means for calculating a reference index for the determined image, by implementing an indexing process, or

- first computer analysis means for extracting reference indexes from the determined audiovisual sequence, so as to compose a reference set of reference indexes.

The reference index is in the form of an ordered and finite set of values, in particular in the form of a characteristic vector, coding the content of the determined image. It results from the combination of technical features that a reference index characteristic of the determined image and / or of the determined audiovisual sequence is thus obtained. The system includes:

reception means for receiving the stream of images or audiovisual sequences comprising at least one determined image and / or at least one determined audiovisual sequence,

- computer processing means for digitizing the flow of images or audiovisual sequences.

The system further includes second calculating means for calculating a current index for current images of the flow, implementing the indexing process for the current images of the flow. The current index is in the form of an ordered and finite set of values, in particular in the form of a characteristic vector, coding the content of the current image. The system further comprises comparison means for comparing the reference index of the determined image with the current index of the current image of the observed flow. It results from the combination of technical features that the system makes it possible to detect in a flow a determined image with very high precision, in an extremely rapid manner, while being robust to very strong photometric alterations.

Indexing process

Preferably according to the invention, the first calculation means for calculating a reference index of a determined image comprise:

- sampling means for resampling the determined image into a determined resampled image with the dimensions fixed in advance,

means of discrete quantification of the pixel values of the determined resampled image.

After discrete quantization, the determined resampled image is represented by a matrix of the values of the pixels.

The first means of calculating the reference index of a determined image further comprise scheduling means for arranging the values of the pixels according to a predetermined order of traversing of the positions in the matrix, in particular by concatenating the values of each line of the matrix in the form of a characteristic vector. The reference index is thus obtained.

The system further comprises, in the case where the determined image is a color image comprising color levels, conversion means for converting beforehand the color levels of the image determined to resample in grayscale.

Preferably, according to the invention, the first calculation means further comprise reference processing means for calculating the discrete entropy of the distribution of the values of the reference index. This entropy is hereinafter referred to as the reference marginal entropy.

It is thus possible to optimize the comparison time. It is possible to complete the reference index with this reference marginal entropy value.

Preferably according to the invention, the system is such that the second calculation means for calculating a current index of a current image comprise:

- sampling means for resampling the current image into a current image with the dimensions fixed in advance,

- means for discrete quantification of the pixel values of the current image.

After discrete quantization, the resampled current image is represented by a matrix of the values of the pixels.

The second calculation means for calculating a current index of a current image also comprise ordering means for arranging the values of the pixels according to a predetermined order of traversal of the positions in the matrix, in particular by concatenating the values of each line of the matrix in the form of a characteristic vector. This gives the current index.

The system further comprises, in the case where the current image is a color image comprising color levels, conversion means for converting beforehand the color levels of the current image to be resampled into gray levels.

Preferably, according to the invention, the second calculation means further comprise current processing means to calculate the discrete entropy of the distribution of the values of the current index. This entropy is hereinafter called the current marginal entropy.

It is thus possible to optimize the comparison time. It is possible to complete the current index with this current marginal entropy value.

Calculating an index comparison distance

Preferably according to the invention, each reference index and each current index are in the form of ordered and finite sets of values. These values are identified, in the reference index and the current index, by a coordinate system. The system is such that it also comprises third calculation means for defining, for a given coordinate of the coordinate system, a pair of values, the first value of which is the value appearing in the reference index associated with the given coordinate. , and whose second value is the value appearing in the current index associated with the given coordinate. The third calculation means make it possible to calculate the two-dimensional histogram of the pairs of values obtained for all the coordinates of the coordinate system of the reference index and of the current index.

The third calculation means also make it possible to calculate the discrete entropy of said two-dimensional histogram, hereinafter called the entropy of the two-dimensional histogram.

The third calculation means also make it possible to calculate a comparison distance between a reference index and a current index by forming the ratio between, to the numerator, the sum of the reference marginal entropy and the current marginal entropy minus the entropy of the two-dimensional histogram, and in the denominator the sum of the reference marginal entropy and the current marginal entropy.

Reference index extraction Preferably according to the invention, the system is such that, for extracting from the determined audiovisual sequence, composed of determined images, the reference indexes of the determined audiovisual sequence, it further comprises fourth calculation means. These fourth calculation means implement a calculation algorithm comprising a step of initializing a reference set containing the reference indexes of the determined images. The reference set is initialized with the reference index of the first determined image of the determined audiovisual sequence. The reference index of the first determined image of the determined audiovisual sequence constitutes the first reference index of the reference set. The calculation algorithm also includes:

- (a) the step of (i) calculating, for each determined image of the audiovisual sequence determined, a current temporary index and (ii) calculating a comparison distance between the current temporary index and the last reference index added to the reference set,

(b) the step of comparing, at a predetermined threshold SE, the comparison distance between the current temporary index and the last reference index added to the reference set,

- (c) the step of adding the current temporary index to the reference set, if the comparison distance exceeds the predetermined threshold SE.

The current temporary index becomes the last reference index of the reference set. The calculation algorithm further comprises the step of iterating steps (a) to (c) until the end of the determined audiovisual sequence.

Detection

Preferably according to the invention, the system is such that the third calculation means compare to a predetermined threshold SF the comparison distance between each reference index and the current index of the current image of. observed flow. So that the determined image is detected in any flow of images when the comparison distance between the reference index of the determined image and the current index is less than the predetermined threshold SF.

According to another variant embodiment of the invention, the system is more particularly designed to detect a given audiovisual sequence in any stream of audiovisual sequences. In this case, the system comprises initialization means for loading the value - 1 into a first register T, and the value 0 into a second register D.

The system further comprises, in the case of this variant, fifth calculation means for calculating, for each reference index of the reference set, the comparison distance between the reference index of the reference set and the current index.

If the comparison distance thus calculated is less than a predetermined threshold SD the second register D is incremented by one. This condition is hereinafter referred to as the reference index detection condition.

The instant at which the first reference index of the reference set of the determined audiovisual sequence satisfies the detection condition is referred to below as the instant of the first detection.

The fifth calculation means are arranged to load into the first register T the time elapsed since the instant of the first detection if the value stored in the second register D is other than zero. The fifth calculation means are arranged (i) to iterate the calculation of the comparison distance until the value stored in the second register D reaches the predetermined threshold SD, or (ii) to iterate the implementation of the means initialization if the value stored in the first register T exceeds a predetermined threshold ST. So that the determined audiovisual sequence is deemed to be detected if the stored value of the second register D reaches the predetermined threshold SD.

Mathematical details on the nature of the comparison function implemented in the present invention

The method which is the subject of the invention makes it possible to detect proprietary audio-visual sequences in a video stream to be analyzed. This process is based on the existence of a comparison distance making it possible to compare any two images.

This function has the property of returning a low value, close to 0, when the two images are different and of returning a high value when the two images are superimposable, even in the presence of significant photometric transformations between the two images, that is to say ie profoundly modifying the pixel values of an image.

Section 1 defines the function used for the comparison, and Section 2 shows why the detection takes place under the stated conditions, even difficult.

1. Mutual information between two random variables

Coming from the field of statistics, the concepts recalled below are known and can be found in technical works presenting the foundations of communication theory, for example in Information Theory, by Robert B. Ash, Dover Publications Inc.

1. 1 Concept of discrete entropy

If X is a random variable taking discrete values {x_l, ... x_n} with the corresponding probability distribution {p_l, ... p_n} {i. e p (X = x_l) = p_l, ..., p (X = x_n) = p_n), the discrete entropy of X is by definition:

H (X) = -∑px_ixlog (px_i)

1.2 Concept of discrete joint entropy

If X is a random variable taking discrete values {x_l, ... x_n} with the corresponding probability distribution {px l, ... px n}; If Y is a random variable taking discrete values {y__l, ... y_n} with the corresponding probability distribution {py_l, ... py_n};

If the joined random variable Z = (X, Y), taking by definition the discrete values {(x_l, y__l), ..., (x_n, y_n)} provided with the corresponding probability distribution {pz_ll, ... pz_nn } such that p (X = x_l, Y = y_l) = pz_ll, ..., p (X = x_, Y = y_n) = pz_nn, then the discrete joined entropy of Z = (X, Y) is by definition

1. 3 Concept of discrete conditional entropy

If X is a random variable taking discrete values {x_l, ... x_n} with the corresponding probability distribution {px_l, ... px_n};

If Y is a discrete random variable taking values {y_l, ... y_n} with the corresponding probability distribution {py_l, ... py_n};

If the discrete conditional random variable = (X | Y), being pronounced "X knowing Y", taking by definition the discrete values {(x_l | y_l), ..., (x_n | y_n)} provided with the probability distribution corresponding {p_ll, ... p _nn}, so that p (X = x_l | Y = y_l) = p_ll, ..., p (X = x_n | Y = y_n) ^ pw_nn, then the conditional entropy of W = (X | Y) is by definition

H (Z) = H (X, Y) - ∑ _{± r} ιpw_ijxloq (pw_ij)

It is easy to prove that H (X, Y) = H (X | Y) + H (Y).

1. 4 Concept of mutual information

The mutual information MI (X, Y) between two random variables X and Y is by definition:

MI (X, Y) = H (X) + H (Y) -H (X, Y)

MI (X, Y) = H (X) -H (X | Y)

MI (X, Y) = H (Y) H (Y | X)

1.5 Concept of standardized mutual information The normalized mutual information NMI (X, Y) between two random variables X and Y is by definition given by the following formula:

NMI (X, Y) = MI (X, Y) / (H (X) + H (Y))

The notion of comparison distance entering into the definition of the technical features of the present invention corresponds to NMI.

1. 5. 1 Case of the independent variables

If X and Y are independent, then by definition H (X | Y) = H (X), therefore NMI (X, Y) = 0.

1. 5. 2 Case of functionally linked variables

If Y = f (X), then H (Y | X) = H (f (X) | X) = 0, because the value of the random variable f (X) is entirely determined by the knowledge of X. By reporting in the definition of mutual information, we obtain the remarkable simplification:

MI (X, Y) = H (Y) = H (f (X))

Therefore,

NMI (X, Y) = H (f (X)) / (H (X) + H (f (X)))

2. Detection of images by standardized mutual information

2. 1 Images, histograms and random variables

The image detection method according to the invention is based on the definitions and properties which have just been described.

Indeed :

• The normalized gray level histogram of an image I, obtained by calculating the histogram of the values taken by I (x) for x taking all the possible positions in the image, is a distribution of discrete probabilities allowing by extension to define “the entropy of an image”, see paragraph 1.1.

• The normalized joint histogram of the gray levels of two images II and 12 of the same dimension, obtained by calculating the two-dimensional histogram of the values taken by (Il (x), 12 (x)) for x taking all the possible positions in image II, is a two-dimensional probability distribution allowing by extension to define respectively “the entropy joined between two images”, “l 'conditional entropy between two images', 'mutual information between two images', 'normalized mutual information between two images', see respectively paragraphs 1.2, 1.3, 1.4 and 1.5

Thus, the comparison distance used to carry out detections is NMI (X, Y), where X and Y are two images.

2.2 Detection criteria

To detect a determined image, the comparison distance NMI (X, Y) is compared to a predetermined threshold, fixed in advance. If the distance between the current image, candidate for detection, and the reference image is less than this threshold, the current image is declared "recognized" or detected.

2. 3 Robustness at photometric transformations

In theory, the image to be detected is the exact copy of the reference image. However, in practice, the image to be detected has generally passed through a noisy transmission channel, radio waves, television receiver, satellite, video recorder, etc. This noise can be expressed either by high frequency noise in the image but also by a low frequency distortion of the signal, change in contrast, brightness, saturation, etc.

It is therefore essential that the detection technique is robust to these photometric changes.

The distance NMI (X, Y) has the advantage of not directly comparing the pixel values of two images (a simple approach used for example in a correlation distance but unusable in practice because of its lack of robustness). On the other hand, the distance NMI (X, Y) has the advantage of calculating the capacity to predict the value of pixels of X knowing those of Y, without any particular hypothesis on the nature of the photometric transformation linking X and Y.

In other words, the distance NMI (X, Y) remains minimal if X and Y correspond geometrically, even if their intensity surfaces are not directly superimposable. Detection is therefore extremely robust to photometric changes.

detailed description

Other characteristics and advantages of the invention will appear on reading the description of alternative embodiments of the invention given by way of non-limiting example, and from the

FIG. 1 which schematically represents a stream 3 of any image 6 containing a determined image 11, in particular a proprietary image 4, which should be detected,

FIG. 2 which schematically represents the technical means making it possible to calculate a reference index 10 of a given image 11,

FIG. 3 which schematically represents the form in which a reference index can appear,

FIG. 4 which schematically represents the indexing process 39 making it possible to calculate an index 8, in particular a current index 14 in order to compare it with a reference index 10,

FIG. 5 which schematically represents a stream 3 of audiovisual sequences 7 containing a determined audiovisual sequence 2, in particular a proprietary audiovisual sequence 4,

FIG. 6 which schematically represents the technical means making it possible to calculate from a given audiovisual sequence 2 a reference set 30 composed of reference index 10,

FIG. 7 which schematically represents the form in which a reference index 10 of a reference assembly 30 can appear, FIG. 8 which schematically represents the indexing process 39 making it possible to calculate an index 8, in particular a current index 14 of a current image 13 of any audiovisual sequence 7, in order to compare it with a reference index 10 ,

FIG. 9 which schematically represents an embodiment of a process for indexing a determined image 11 in the case of the first variant of embodiment as in the case of the second variant of embodiment,

FIG. 10 which schematically represents an embodiment of a process for indexing a current image 13 in the case of the first variant of embodiment as in the case of the second variant of embodiment,

FIG. 11 which schematically represents a form of representation of the pairs of values 25, 26 making up a reference index 21a and a current index 21b,

FIG. 12 which schematically represents the technical means making it possible to calculate a comparison distance 29,

FIG. 13 which schematically represents an embodiment of the technical means making it possible to extract the reference indexes 10 and to constitute a reference assembly 30 in the case of the second variant embodiment,

- Figure 14 which schematically shows an embodiment of the technical means for detecting a specific audiovisual sequence 2, in the case of a second embodiment

FIG. 15 which schematically represents, in the case of the second variant embodiment, the flow diagram of the algorithm making it possible to detect a given audiovisual sequence 2 by implementing the technical means described with reference to FIG. 15.

First variant

In the case of the first embodiment of the invention which will now be described with reference to FIGS. 1, 2, 3 and 4 the system is designed to identify a determined image 11 in any stream 3 of images 6. The objective is to identify a proprietary image 4 in the stream 3.

In the case of this first alternative embodiment, the system comprises first calculation means 38 for calculating a reference index 10 for each determined image 11, by implementing an indexing process 39. A description will be given in detail below. such indexing process 39.

The reference index 10 (fig. 3) is in the form of an ordered and finite set 21a of values 20a, in particular in the form of a characteristic vector 9a, encoding the content of the determined image 11. We thus obtains a reference index 10 characteristic of the determined image 11.

The system further comprises reception means 41 for receiving the stream 3 of images 6 capable of comprising at least one determined image 11. The system further comprises computer processing means 42 for digitizing the stream 3 of images 6. The system further comprises second calculation means 43 for calculating a current index 14 for current images 13 of the stream 3. These second calculation means 43 calculate the current index 14 by implementing an indexing process 39 comparable to that implemented for the calculation of the reference indexes 10 of the determined images 11. Like the reference index 10, the current index 14 is in the form of an ordered set 21b and finite of values 20b, in particular in the form of a characteristic vector 9b coding the content of the current image 13.

The system further comprises comparison means 44 for comparing the reference index 10 of the determined image 11 with the current index 14 of the current image 13 of the stream 3 observed. It is thus possible to detect in a stream 3 a determined image 11 with very high precision, in an extremely rapid manner, while being robust to very strong photometric alterations. There will be described in more detail below, with reference to FIG. 12, an alternative embodiment of the technical means making it possible to carry out this detection.

Second variant

In the case of the second variant embodiment of the invention which will now be described with reference to FIGS. 5, 6, 7 and 8 the system is designed to identify a specific audiovisual sequence 2 in any stream 3 of any audiovisual sequence 7 .

The objective is to identify a proprietary audiovisual sequence 5 in stream 3.

In the case of this second variant embodiment, the system includes first means of computer analysis.

40 to extract reference indexes 10 from the determined audiovisual sequence 2, so as to compose a reference set 30 of reference indexes 10.

Each reference index 10 of the reference set 30 is calculated by calculation means 38 implementing an indexing process 39 comparable to that which has been described in the case of the first alternative embodiment. Each reference index 10 is in the form of an ordered and finite set 21b of values 20b, in particular in the form of a characteristic vector 9b coding the content of each determined image 11 of the determined audiovisual sequence 2. We thus obtain a reference set 30 characteristic of the determined audiovisual sequence 2.

The system further includes receiving means

41 to receive the stream 3 of audiovisual sequences 7 likely to include at least one specific audiovisual sequence 2.

The system further comprises computer processing means 42 for digitizing the stream 3 of audiovisual sequences 7. We will not describe, in the case of this second variant embodiment, the technical means used to calculate the current index 14 of each current image 13 of an audiovisual sequence 7. Indeed, they are comparable to those described in the case of the first alternative embodiment.

The system further comprises comparison means 44 for comparing the reference indexes 10 of the determined images 11 composing a determined audiovisual sequence 2 with the current indexes 14 of the current images 13 of the stream 3 observed. It is thus possible to detect in a stream 3 a specific audiovisual sequence 2 with very high accuracy, extremely quickly, while being robust to very strong photometric alterations.

We will describe in more detail below with reference to Figures 14 and 15 an alternative embodiment of the technical means for performing this detection.

The technical means, in particular the first calculation means 38 and the second calculation means 43, used to calculate the reference indexes 10 or to calculate the current indexes 14 could be combined in the same computer equipment, however one does not go out of the field of the present invention by calculating the reference indexes 10 in equipment distinct from those used to calculate the current indexes 1. This remark concerns the first variant as well as the second variant

Indexing process

In the case of the first variant of the invention as in the case of the second variant, the first calculation means 38 and the second calculation means 43 for calculating the reference indexes 10 and the current indexes 14 put implementing an indexing process which will now be described with reference to Figures 9 and 10 an embodiment. The term "index" has been used to designate a reference index 10 or a current index 14 when there is no need to distinguish them.

The elements having comparable functions for calculating the reference indexes 10 and the current indexes 14 have have been referenced in the figures by the same reference numerals.

The first calculation means 38 for calculating a reference index 10 of a determined image 11 comprise sampling means 45 for resampling the determined image 11 into a determined image resampled with the dimensions fixed in advance. This determined resampled image is hereinafter called the normalized determined image 116. In order to calculate the reference indexes 10 the first calculation means 38 furthermore comprise discrete quantification means 46 of the pixel values of the determined image 11 resampled 116. After discrete quantification, the determined image 11 resampled is represented by a matrix 19 of the values of the pixels 17. The first means 38 for calculating the reference index 10 of a determined image 11 comprise in in addition to scheduling means 47 for arranging the values of the pixels 17 according to a predetermined travel order of the positions 18 in the matrix 19, in particular by concatenating the values of each line of the matrix in the form of a characteristic vector 9a. This gives the reference index 10.

The system further comprises, in the case where the determined image 11 is a color image comprising color levels, conversion means 48 for converting beforehand the color levels of the determined image 11 to be resampled into gray levels .

Preferably according to the invention, the first calculation means 38 further comprise reference processing means 49a for calculating the discrete entropy of the distribution of the values of the reference index 10. This entropy is hereinafter called the reference marginal entropy 50a.

The comparison time of two indexes is the time necessary to calculate the comparison distance between said indexes. By completing the reference index 10 with this reference marginal entropy value 50a, the calculation of said comparison distance no longer requires the calculation of the reference entropy value 50a. The comparison time is thus reduced.

It is possible to complete the reference index 10 with this reference marginal entropy value 50a.

Preferably also according to the invention, the second calculation means 43 for calculating a current index 14 of a current image 13 comprise sampling means 45 for resampling the current image 13 into a current image with the dimensions fixed in advance. . This current resampled image is hereinafter called the normalized current image 136. The second calculation means 43 also comprise, for calculating a current index 14 of a current image 13, means of discrete quantification 46 of the pixel values of the current image 13. After discrete quantization, the resampled current image 13 is represented by a matrix 19 of the values of the pixels 17. The second calculation means 43 further comprise, for calculating a current index 14 of a current image 13, scheduling means 47 for arranging the values of the pixels according to a predetermined travel order of the positions 18 in the matrix, in particular by concatenating the values of each line of the matrix in the form of a characteristic vector 9b. This gives the current index 14.

The system further comprises, in the case where the current image 13 is a color image comprising color levels, conversion means 48 for converting beforehand the color levels of the current image 13 to be resampled into gray levels .

Preferably, according to the invention, the second calculation means 43 also comprise current processing means _. 49b for calculating the discrete entropy of the distribution of the values of the current index 14. This entropy is hereinafter called the current marginal entropy 50b. It is thus possible to optimize the comparison time. It is possible to complete the current index 14 with this current marginal entropy value 50b.

The reference 16 has sometimes been used to designate a normalized determined image whether it is a normalized determined image 116 or a normalized current image 136.

Calculating an index comparison distance

In the case of the first variant of the invention as in the case of the second variant, the system comprises comparison means 44 for (i) comparing the reference index 10 of the determined image 11 with the current index 14 of the current image 13 of the stream 3 observed or for (ii) comparing the reference indexes 10 of the determined images 11 composing a audiovisual sequence 2 with the current indexes 14 of the current images 13 of the stream 3 observed.

We will now describe, with reference to FIGS. 11 and 12, an advantageous embodiment of the technical means enabling these comparisons to be made. To this end, the notion of comparison distance 29 should be explained in the sense of the present invention.

As described above, each reference index 10 and each current index 14 are in the form of ordered and finite sets 21a and 21b with values 20a and 20b. It is therefore possible to identify these values 20a and 20b in the reference index 10 and the current index 14, by a coordinate system 22.

The system further comprises third calculation means 52 for defining, for a given coordinate 24 of the coordinate system 22, a pair of values 25, 26 whose first value 25 is the value appearing in the reference index 10 associated with the given coordinate 24, and whose second value 26 is the value appearing in the current index 14 associated with the given coordinate 24. The third calculation means 52 make it possible to calculate the two-dimensional histogram 27 of the pairs of values 25, 26 obtained for all the coordinates of the coordinate system of the reference index 10 and of the current index 14.

The third calculation means 52 also make it possible to calculate the discrete entropy of said two-dimensional histogram, hereinafter called the entropy of the two-dimensional histogram 28.

The third calculation means 52 also make it possible to calculate a comparison distance 29 between a reference index 10 and a current index 14 by forming the ratio between, to the numerator, the sum of the reference marginal entropy 50a and the marginal entropy current 50b minus the entropy of the two-dimensional histogram 28, and in the denominator the sum of the reference marginal entropy 50a and the current marginal entropy 50b.

Reference index extraction

The notion of comparison distance 29 between a reference index 10 and a current index 14 having been explained, we are now able to complete the description of. the second variant of the invention in the case of an advantageous embodiment, with reference to FIG. 13. In the case of this advantageous embodiment, intended to allow detection of a specific audiovisual sequence 2 in a stream 3 of audiovisual sequences 7, a preliminary phase of reference index 10 extraction is carried out so as to constitute a reference set 30.

To extract from the determined audiovisual sequence 2, composed of determined images 11, the reference indexes 10 of the determined audiovisual sequence 2, the system further comprises fourth calculation means 53. These fourth calculation means 53 implement a calculation algorithm 54 comprising a step of initializing a reference set 30 containing the reference indexes 10 of the determined images. The reference set 30 is initialized with the index of reference 100 of the first determined image 110 of the determined audiovisual sequence 2. The reference index 100 of the first determined image 110 of the determined audiovisual sequence 2 constitutes the first reference index of the reference set 30. The algorithm calculation unit 54 further comprises:

- (a) the step of (i) calculating, for each determined image 11 of the determined audiovisual sequence 2, a current temporary index 31 and (ii) calculating a comparison distance 29 between the current temporary index 31 and the last reference index 32 added to the reference set 30,

(b) the step of comparing, at a predetermined threshold SE 33, the comparison distance 29 between the current temporary index 31 and the last reference index 32 added to the reference set 30,

- (c) the step of adding the current temporary index 31 to the reference assembly 30, if the comparison distance 29 exceeds the predetermined threshold SE 33.

The current temporary index 31 then becomes the last reference index 32 of the reference set 30. The calculation algorithm 54 further comprises the step of iterating steps (a) to (c) until the end of specified audiovisual sequence 2.

Detection

We will now describe, in the case of the first alternative embodiment, with reference to FIG. 12, the final phase of the process for detecting the determined image 11, in particular of the proprietary image 4, in - a stream 3 any image 6. For this purpose, the third calculating means 52 compare a • predetermined threshold SF 65 with the comparison distance 29 between each reference index 10 and the current index 14 of the current image 13 of the stream 3 observed. The determined image 11 is deemed to be detected in any stream 3 of images 6 when the comparison distance 29 between the index 10 of the determined image 11 and the current index 14 is less than the predetermined threshold SF 65.

We will now describe, in the case of the second variant embodiment, with reference to FIGS. 14 and 15, the final phase of the process for detecting the determined audiovisual sequence 2, in particular of the proprietary audiovisual sequence 5, in a stream 3 any audiovisual sequence 7. In this case, the system comprises initialization means 57 for loading the value - 1, minus one, of a variable T 34, into a first register T ^" 55, and the value 0, zero , of a variable D 35, in a second register D 56.

The system further comprises in the case of this alternative embodiment of the fifth calculation means 58 for calculating, for each reference index 10 of the reference set 30, the comparison distance 29 between the reference index 10 considered of the reference assembly 30 and the current index 14 of a current image 13 of the stream 3 observed.

If the comparison distance 29 thus calculated is less than a predetermined threshold SD 59 the second register D 56 is incremented by one. This condition is hereinafter referred to as the reference index detection condition 10.

The instant at which the first reference index 10 of the reference set 30 of the determined audiovisual sequence 2 satisfies the detection condition is referred to below as the instant of the first detection.

The fifth calculation means 58 are arranged to load into the first register T 55 the time elapsed since the instant of the first detection if the value stored in the second register D 56 is other than zero. The fifth calculation means 58 are arranged (i) to iterate the calculation of the comparison distance 29 until the value stored in the second register D 56 reaches the predetermined threshold SD 59, or (ii) to iterate the implementation of the initialization means if the value stored in the first register T 55 exceeds a predetermined threshold ST 60. So that the determined audiovisual sequence 2 can be deemed to be detected if the stored value of the second register D 56 reaches the predetermined threshold SD 59.

FIG. 15 shows the flow diagram of the algorithm which has just been described.

Claims

1. Method for identifying a determined image (11) and / or a determined audiovisual sequence (2) in any stream (3) of images (6) or audiovisual sequences (7), in particular from the perspective of being able to identify a owner image (4) in said stream (3) and / or to be able to identify, preferably in real time, several proprietary audiovisual sequences (5) in said stream (3); said method comprising the step of calculating, for each image (6), an index in the form of an ordered and finite set of values (21), in particular in the form of a characteristic vector (9), coding the content of said image (6); said index calculation process being hereinafter called the indexing process (39); said method comprising: the step of calculating a reference index (10), by implementing said indexing process (39) for said determined image (11), or - the step of extracting reference indexes (10) from said determined audiovisual sequence (2), so as to compose a reference set (30) of reference indexes (10); so that reference indices (10) characteristic of the determined image (11) and / or of the determined audiovisual sequence (2) are thus obtained; said method further comprising the step of calculating an index, for current images (13) of said flow (3), by implementing said indexing process (39) for said current images (13) of said flow (3) ; said index being hereinafter called the current index (14); said method comprising the step of comparing said reference indexes (10) with the current index (14) of the current image (13) of the stream (3) observed; so that said method makes it possible to detect in a stream (3) a determined image (11) with very high precision, in an extremely rapid manner, while being robust to very strong photometric alterations. 2. Method according to claim 1; said method being such that, to calculate an index of an image (6), in particular a reference index (10) and / or a current index (14), it comprises the step of resampling said image (6) in an image with the dimensions fixed in advance; said resampled image being hereinafter referred to as the normalized image (16); said method further comprising, in the case where said image (6) is a color image comprising color levels, the step of previously converting said color levels of said image (6) to be resampled into gray levels ; said normalized image (16) being represented by a matrix (19) of pixel values (17), after discrete quantization of said pixel values; said method further comprising the following steps: - the step of arranging said values according to a predetermined order of browsing of the positions (18) in said matrix (19), in particular by concatating said values of each line of said matrix (19) in the form of a characteristic vector (9), so as to obtain said index. 3. Method according to claim 2; said method further comprising the step of calculating the discrete entropy of the distribution of the values of said reference index (10) or said current index (14); said entropy being hereinafter referred to as the reference marginal entropy (50a) or the current marginal entropy (50b); so that the comparison time is thus optimized; so that it is thus possible to complete said index with this marginal entropy value. 4. Method according to claim 3; said indexes being in the form of ordered sets (21a, 21b) and finite of identified values, in said reference index (10) and said current index (14), by a coordinate system (22); said method being such that it further comprises the following steps: - the step of defining, for a given coordinate (24) of the coordinate system (22), a pair of values (25, 26) including: • the first value (25) is the value appearing in the reference index (10) associated with said given coordinate (24), and of which The second value (26) is the value appearing in the current index (14) associated with said given coordinate (24), the step of calculating the two-dimensional histogram (27) of said pairs of values (25, 26) obtained for all, the coordinates of the coordinate system (22) of the reference index (10) and of the current index (14), the step of calculating the discrete entropy of said two-dimensional histogram, hereinafter called the entropy of the two-dimensional histogram (28), - the step of calculating a comparison distance (29) between a reference index (10) and a current index (14) by forming the ratio between, to the numerator, the sum of the reference marginal entropy (50a) and current marginal entropy (50b) minus the entropy of the two-dimensional histogram (28), and in the denominator the sum of the reference marginal entropy (50a) and the current marginal entropy (50b). 5. Method according to claim 4; said method being such that, to extract from said determined audiovisual sequence (2) the reference indexes (10) of said determined audiovisual sequence (2), it further comprises the following steps: the step of initializing a reference set (30) containing said reference indexes (10) of said determined images (11) with the reference index (100) of the first determined image (110) of said determined audiovisual sequence (2); said reference index (100) of said first determined image (110) of said determined audiovisual sequence (2) constituting the first reference index of said reference set (30); said method further comprising: - (a) the step of calculating, for each determined image (11) of said determined audiovisual sequence (2), a current temporary index (31) and calculating a comparison distance (29) between said current temporary index (31 ) and the last reference index (32) added to said reference set (30), - (b) the step of comparing, at a predetermined threshold SE (33), said comparison distance (29) between said current temporary index (31) and the last reference index (32) added to said set (30); - (c) the step of adding said current temporary index (31) to said reference set (30), if the comparison distance (29) exceeds said predetermined threshold SE (33); said current temporary index (31) becoming the last reference index (32) of said reference set (30); said method further comprising the step of iterating steps (a) to (c) _ until the end of said determined audiovisual sequence (2). 6. Method according to any one of claims 1 to 5; said method being such that to compare said reference indexes (10) with the current index (14) of the current image (13) of the flow (3) observed, it further comprises the step of comparing said comparison distance (29) at a predetermined threshold SF (65); so that in the case of any stream (3) of images (6) said determined image (11) is detected on the condition that said comparison distance (29) between the reference index (10) of said determined image (11) and the current index (14) is less than said predetermined threshold SF (65). 7. The method of claim 5; said method being more particularly designed to detect a specific audiovisual sequence (2) in any stream (3) of audiovisual sequences (7); said method comprising the following steps: - (a) the step of initializing a variable T (34) to - 1, the step of initializing a variable D (35) to 0, - (b) the step of calculating, for each reference index (10) of said reference set (30), said comparison distance (29) between said reference index (10) of said reference set (30) and l 'current index (14); so that if said comparison distance (29) is less than a predetermined threshold SD (59) said variable _ D (35) is incremented by one; said condition being hereinafter called reference index detection condition (10). the method being such that the instant at which the first reference index (10) of said reference set (30) of said determined audiovisual sequence (2) satisfies said detection condition is referred to below as the instant of first detection; the method further comprises the following steps: - (c) the step of assigning to said variable T (34) the time elapsed since said instant of the first detection if the variable D (35) is other than zero, - (d) the step of iterating step (b) until said variable D (35) reaches said predetermined threshold SD (59); or iterate step (a) if said variable T (34) exceeds a predetermined threshold ST (60), - (e) the step of detecting said determined audiovisual sequence (2) if the variable D (35) reaches said predetermined threshold SD (59). 8. System for identifying a specific image (11) and / or a specific audiovisual sequence (2) in any stream (3) of images (6) or audiovisual sequences (7), in particular from the perspective of being able to identify a owner image (4) in said stream (3) and / or to be able to identify, preferably in real time, several proprietary audiovisual sequences (5) in said stream (3); said system comprising: - first calculation means (38) for calculating a reference index (10) for said determined image (11), by implementing an indexing process (39), or - first computer analysis means (40) for extracting reference indexes (10) from said determined audiovisual sequence (2), so as to compose a reference set (30) of reference indexes (10); said reference index (10) being in the form of an ordered (21a) and finite set of values (20a), in particular in the form of a characteristic vector (9a), coding the content of said determined image (11 ); so that a reference index (10) characteristic of the determined image (11) and / or of the determined audiovisual sequence (2) is thus obtained; said system further comprising: - reception means (41) for receiving said stream (3) of images (6) or audiovisual sequences (7) comprising at least one determined image (11) and / or at least one determined audiovisual sequence (2), - computer processing means (42) for digitizing said stream (3) of images (6) or audiovisual sequences (7); said system further comprising: - second calculation means (43) for calculating a current index (14) for current images (13) of said stream (3), by implementing said indexing process (39) for said current images (13) of said flow flow (3); said current index (14) being in the form of an ordered and finite set of values (21b), in particular in the form of a characteristic vector (9b), coding the content of said current image (13); said system further comprising: - comparison means (44) for comparing said reference index (10) of said determined image (11) with the current index (14) of the current image (13) of the observed flow (3); .so that said system makes it possible to detect in a flow (3) a determined image (11) with very high precision, in an extremely rapid manner, while being robust to very strong photometric alterations. 9. The system of claim 8; said system being such that said first calculation means (38) for calculating a reference index (10) of a determined image (11) comprise: - sampling means (45) for resampling said determined image (11) into a determined image resampled to the dimensions fixed in advance, - means for discrete quantification (46) of the pixel values of said determined resampled image (11) so that said determined resampled image (11) is represented by a matrix (19) of the pixel values (17), after discrete quantification ; - scheduling means (47) for arranging said values of the pixels (17) according to a predetermined travel order of the positions (18) in said matrix (19), in particular by concatenating said values of each line of said matrix (19) in the form of a characteristic vector (9a), so as to obtain said reference index (10); said system further comprising, in the case where said determined image (11) is a color image (6) comprising color levels, conversion means (48) to previously convert said color levels from said determined image (11) to be re-sampled in gray levels. 10. The system of claim 9; said first calculation means (38) further comprising reference processing means (49a) for calculating the discrete entropy of the distribution of the values of said reference index (10); said entropy being hereinafter referred to as the reference marginal entropy (50a); so that the comparison time is thus optimized; so that one can thus complete said reference index (10) with this reference marginal entropy value (50a). 11. System according to any one of claims 8 to 10; said system being such that said second calculation means (43) for calculating a current index (14) of a current image (13) comprise: - sampling means (45) for ¹ resampling said current image (13) into a current image (13) with dimensions fixed in advance, - discrete quantification means (46) of the pixel values of said current image (13) so that said resampled current image (13) is represented by a matrix (19) of the pixel values (17), after quantization discreet ;. - scheduling means (47) for arranging said values of the pixels according to a predetermined order of traversing of the positions (18) in said matrix (19), in particular by concatenating said values of each line of said matrix (19) a characteristic vector (9b), so as to obtain said current index (14); said system further comprising, in the case where said current image (13) is a color image (6) comprising color levels, conversion means (48) for first converting said color levels of said current image (13) to be re-sampled into gray levels. 12. System according to claim 11; said second calculating means (43) further comprising current processing means (49b) for calculating the discrete entropy of the distribution of the values of said current index (14); said entropy being hereinafter called the current marginal entropy (50b); so that the comparison time is thus optimized; so that one can thus complete said current index (14) with this current entropy value. 13. The system of claim 12; said reference indexes (10) and said current indexes (14) being in the form of ordered sets (21a, 21b) and finite of identified values, in said reference index (10) and said current index (14), by a coordinate system (22); said system being such that, it further comprises third calculation means (52) for: - define, for a given coordinate (24) of the coordinate system (22), a pair of values (25, 26) whose first value (25) is the value appearing in the reference index (10) associated with said given coordinate (24), and whose second value (26) is the value appearing in the current index (14) associated with said given coordinate (24), - calculating the two-dimensional histogram (27) of said pairs of values (25, 26) obtained for all the coordinates of the coordinate system (22) of the reference index (10) and of the current index (14) , - calculating the discrete entropy of said two-dimensional histogram, hereinafter called the entropy of the two-dimensional histogram (28), - calculate a comparison distance (29) between a reference index (10) and a current index (14) by forming the ratio between, to the numerator, the sum of the marginal entropy of reference (50a) and of the current marginal entropy (50b) minus the entropy of the two-dimensional histogram (28), and in the denominator the sum of the reference marginal entropy (50a) and the current marginal entropy (50b). 14. The system of claim 13; said system being such that, to extract from said determined audiovisual sequence (2), composed of determined images (11), the reference indexes (10) of said determined audiovisual sequence (2), it furthermore comprises fourth means of calculation (53) implementing a calculation algorithm (54) comprising a step of initializing a reference set (30) containing said reference indexes (10) of said determined images (11) with the reference index ( 100) of the first determined image (110) of said determined audiovisual sequence (2); said reference index (100) of said first determined image (110) of said determined audiovisual sequence (2) constituting the first reference index of the reference set (30); said calculation algorithm (54) further comprising: - (a) the step of calculating, for each determined image (11) of said determined audiovisual sequence (2), a current temporary index (31) and calculating a comparison distance (29) between said current temporary index (31 ) and the last reference index (32) added to said reference set (30); - (b) the step of comparing, at a predetermined threshold SE (33), said comparison distance (29) between said current temporary index (31) and the last reference index (32) added to said reference set (30 ); - (c) the step of adding said current temporary index (31) to said reference set (30), if the comparison distance (29) exceeds said predetermined threshold SE (33); said current temporary index (31) becoming the last reference index (32) of said reference set (30); said calculation algorithm (54) further comprising the step of iterating steps (a) to (c) until the end of said determined audiovisual sequence (2). 15. System according to any one of claims 13 or 14; said system being such that said third calculation means (52) compare with a predetermined threshold SF (65) said comparison distance (29) between said reference indexes (10) and the current index (14) of the current image (13) of the flow (3) observed; so that in the case of any flow (3) of images (6) said determined image (11) is detected on condition that said comparison distance (29) between the reference index (10) of said determined image (11) and the current index (14) is less than said predetermined threshold SF (65). 16. The system of claim 14; said system being more particularly designed to detect a specific audiovisual sequence (2) in any stream (3) of audiovisual sequences (7); said system comprising initialization means (57) for loading: the value - 1 in a first register T (55), and the value 0 in a second register D (56); said system further comprising fifth calculation means (58) for calculating, for each reference index (10) of said reference set (30), said comparison distance (29) between said reference index (10) of said set of reference (30) and the current index (14); so that if said comparison distance (29) is less than a predetermined threshold SD (59) the second D register (56) is incremented by one; said condition being hereinafter called reference index detection condition (10). the system being such that the instant at which the first reference index (10) of said reference set (30) of said determined audiovisual sequence (2) satisfies said detection condition is referred to below as the time of first detection; said fifth calculation means (58) being arranged to load into said first register T (55) the time elapsed since said instant of the first detection if the value stored in said second register D (56) is other than zero; said fifth calculation means (58) being arranged to iterate said calculation of said comparison distance (29), until the value stored in said second register D (56) reaches said predetermined threshold SD (59), or to iterate the implementation of said initialization means (57) if the value stored in the first register T (55) exceeds a predetermined threshold ST (60), so that said audiovisual sequence determined (2) is detected if the stored value of said second register D (56) reaches said predetermined threshold SD (59).