Animated electronic image segmentation process according to the movement of image blocks, using a contour detection process.

0001The field of the invention is that of the analysis and coding of sequences of electronic images, and more particularly of the analysis of the movement of the points of such electronic images.

0002In a specific case which will be detailed below, the method according to the invention applies to the analysis of sequences of images in high definition intended to be transmitted through a channel with limited bit rate. A preferred application of this type is the transmission of high definition television on MAC channel.

0003However, the method of the invention can also be used in any system analyzing a sequence of images (robotics, target tracking, search for spatial and / or temporal parameters, ...) or a sequence of data sets (medical, meteorological applications, ...).

0004The method according to the invention is intended to be part of an image processing chain, and to constitute a link for analyzing the speeds of movement of the image points in the image plane, in particular in order to detect and validate the existence of contours, or borders of objects, moving in the image. A preferred application of such a contour detection method is in particular to allow the grouping of points within blocks of points with homogeneous displacement, according to an operation called "segmentation".

0005There are many advantages to such an analysis.

0006In the case of the transmission of sequences of HD images in a limited speed channel, the purpose of image processing is to reduce the volume of information transmitted, so that: - On transmission, an HD image sub-sampling operation is carried out, the sub-sampled data being accompanied by "assistance data" transmitted jointly in the data channel; - On reception, an inverse operation is carried out consisting in using the assistance data and the sub-sampled signal in an interpolation and compensation operation to restore a high definition signal.

0007If necessary, the subsampled signal can be viewed as it is on a conventional television set.

0008In this type of application, the step of segmenting the image into blocks of points having relatively homogeneous displacement speeds, according to the present invention, occurs for example prior to the operation of sub-sampling on transmission.

0009The segmentation of the image thus advantageously fits between a prior operation of estimation of movement of the image points, and an operation of compression of the image data.

0010The purpose of the motion estimation operation is to create a spatio-temporal database, the data of which are representative of the motion activity of the points, in the image plane, and in time.

0011The segmentation operation helps to optimize the subsequent sub-sampling of the image signal, by grouping together as many points as possible, within blocks of points with homogeneous displacement. Each block is therefore capable of being represented by a single vector of displacement speed.

0012The displacement speed vectors then make it possible to carry out a sub-sampling of the image in the axis of the movement, as described in the French patent application No. 87 17 601 of 16.12.87, in the names of the same applicants.

0013FIG. 1 schematically illustrates the succession of steps of the coding / decoding process in which the segmentation method according to the invention is included.

0014It will be noted that the segmentation drives not only the subsampling of images, but also the development of assistance data, the latter allowing the restitution of the high definition image, by interpolation and compensation, from the image. subsampled.

0015An advantageous application of such a contour detection method is for example to make it possible to optimize the grouping of image points within blocks of points with homogeneous displacement, according to an operation called "segmentation".

0016An electronic image segmentation process is already known, in blocks with homogeneous displacement, as described in French patent application No. 8803639, filed on March 21, 1988 in the name of the same applicants. According to this known method, the segmentation operation is inserted at least partially into a process for estimating the movement of the image points using specific and costly calculations of criteria for choosing the speed vectors representing, calculations used simultaneously for the segmentation of the velocity vector field.

0017The actual segmentation, in this prior method, has the basic principle of allocating a vector to an image block on majority criterion. However, this principle suffers from at least two drawbacks: - first of all, the implementation of this method on an HDMAC signal is only compatible with the limited bit rate of the MAC data channel, unless a sampling structure of the "field skip" type is used (jump frames). This structure consists in systematically eliminating every second frame, and in sampling on the same lines each frame preserved but staggered. The temporal frequency of transmission of the movement information is then 25 Hz. However, if one modifies this structure in the direction of an increase in the temporal frequency of transmission, until for example a value of 50 Hz, one exceeds the capacity of the data channel MAC (1 Mbit / s ); - on the other hand, allocation on the majority criterion of a vector representing a block of images is unsuitable for image blocks containing a "contour". A contour is essentially defined as a rupture zone in the image, which corresponds for example to the separation border, in the image plane, of two adjacent or superimposed objects. Now we see that the selection on the majority criterion of a representative vector for such a contour block, results in poor image restitution, and unpleasant psychovisual noise.

0018The invention particularly aims to overcome these drawbacks.

0019More precisely, a first objective of the invention was to highlight the cause of the poor restitution of the contours, by the known segmentation process. The inventors have thus identified in particular that the problem results from the fact that the majority choice criterion amounts to retaining as a vector representing a contour image block, the speed of movement of one of the two adjacent or superimposed objects, and not the speed of movement of the contour. Indeed, in the case where each of the two overlapping objects is moving in the image, at a different speed, the contour between objects belongs and must be assigned to one of the objects. However, the inventors have realized that the detection of these contours has a double advantage: - from a psychovisual point of view, the allocation of the contour speed vector to a contour block is much preferable to the allocation criterion with majority vector; - the detection and processing of the contours generally seems to be accompanied by a greater psychovisual tolerance which then makes it possible, at least in certain cases, to segment the image into blocks of relatively larger sizes and therefore to further limit the bit rate of the subsampled image signal.

0020On the other hand, the inventors have also established that in the case of objects with a "uniform", or "almost uniform" surface, only the identification of the contours makes it possible to note a reliable speed of movement value. Indeed, insofar as the criterion for estimating the speed of movement of the image points is constituted by the difference in luminance DFD (DFD = "displaced frame difference") between the source image and the estimated image (see WALKER DR RAO KR "New technic in pel - recursive motion compensation" ICC 84, Amsterdam, pp. 703-706), or any other equivalent criterion based on the luminance or chrominance of the image at the points concerned, a uniform or almost uniform moving surface does not make it possible to obtain an exact speed estimate, or even useful. The speed estimate cannot be exact, because the DFD recorded is zero or very low in the uniform or almost uniform surface, even though this surface can be at high speed of movement. The speed information obtained is therefore useless, or at least has a utility fundamentally less than the speed of movement of the contour.

0021The objective of the invention was not only to identify the problems presented above, but also to provide optimized means for solving these problems.

0022Thus, an essential objective of the invention is to provide a method of detecting contours, in an electronic image, which is inexpensive in terms of algorithmic calculations, and reliable.

0023Another objective of the invention is to provide such a method which determines the speed of displacement of the contour, in an image, and in particular of the contours with translative displacement. It will be noted that, in most cases, the detection of such contours is carried out, according to the invention, on blocks of images sufficiently small so that contours with more complex displacement (in particular with a rotational component) are nevertheless considered in approximation as being with translational displacement.

0024Another fundamental objective of the invention is to provide a method of segmenting an electronic image, which combines performance in terms of throughput of processed data (and in particular assistance data, with transmission on MAC channel), to a HD (High Definition) quality of the images reconstructed in the decoder, including a process for detecting contours in the image.

0025A complementary objective of the invention is to provide such a segmentation method which makes it possible to maximize the size of the blocks of segmented images, without compromising the psychovisual quality of the reconstructed images. As already mentioned, this objective aims to overcome the shortcomings of the prior segmentation process by which the reading of the vector field in a contour block, does not allow to allocate one or the other vector on majority criterion, and leads therefore unfavorably to a division of the block, see to its classification in the category of “non-compensable” blocks (that is to say insusceptible of faithful representation by a single speed vector, for lack of apparent homogeneity), even though the selection of the speed of movement of the contour is psychovisually acceptable.

0026These objectives, as well as others which will appear subsequently, are achieved using a process of reallocation of speed vectors in image blocks as a function of the segmentation of a speed vector field, in particular representative of the values ​​of the current speed of movement, in the image plane, of points of an electronic image belonging to an image sequence, said segmentation consisting in dividing said vector field into blocks with a substantially homogeneous speed of movement and in assigning to each of said blocks at least one vector-speed representing, in particular in order to carry out an optimized compression processing of the image signal providing one part of the samples of the image points, and the other part of the data for assisting in the reconstruction of the image from said samples, the assistance data comprising in particular the values ​​of speed vectors representative of the displacement of the samples of points, method characterized in that it comprises a method for detecting contours in each of said image blocks, and in that said representative speed vector assigned to a block having a predominant single contour is the displacement speed vector of said contour.

0027Advantageously, the step of determining the existence of a predominant single contour in an image block consists in verifying that there exists a single speed vector representing a percentage of the number of contour points selected in said block, greater than a predetermined percentage.

0028Advantageously, the detection of contours used consists in associating with each point of said image, a measurement of the gradient of the value of a variable visual criterion associated with each point, in the immediate environment of said point, and in selecting a set of contour points defined in that they are associated with a gradient measurement greater than a given threshold.

0029Advantageously, a first measurement of the gradient of the value of said visual criterion in vertical direction in the immediate environment of said point is associated with each point, and a second measurement of the gradient of the value of said visual criterion in horizontal direction in the environment immediately of said point, and the points whose horizontal gradient measurement is greater than a given threshold and / or whose vertical gradient measurement is greater than a given threshold are selected.

0030Preferably, each of said gradient measurements is carried out either between said point to which said measurement is associated and an adjacent point, or between two adjacent points which are substantially symmetrical with respect to said point to which said measurement is associated

0031The edge detection, adopted by the invention, is thus a "gradient" operator, and therefore of very simple design. Comparing the measurement with a predetermined threshold indicates whether or not the current point belongs to a contour.

0032Advantageously, said variable visual criterion is the luminance.

0033Preferably, the number of representative speed vectors, for an image, is at most equal to a predetermined number n.

0034In this case, the process of selecting said n representative speed vectors notably comprises the following steps: - we associate with each contour point, the estimated speed vector of its displacement in the image plane; - for each estimated speed vector value, the number of contour points with which said value is associated is calculated; - said speed vectors are classified in decreasing order of representativeness of the contour points - the first n speed vectors from said classification list are selected.

0035A two-dimensional histogram processing of the components of the vectors makes it possible to select the n independent and representative vectors, due in particular to an operation of "quantification" of their vertical and horizontal components. Independence ensures that there will be no conflict in the reallocation phase, and representativeness shows that a very large percentage of points can be allocated by one of the n vectors deduced from the histogram.

0036According to another characteristic of the invention, the segmentation process comprises a phase of reallocation of a speed vector, pure block of images, carried out in the following manner: - if there are in the current block points located on a contour, and animated by a near or equal speed, then this speed vector is assigned to the block; - on the contrary, if no contour has been detected, the block is considered to be spatially uniform, and a majority criterion allocates the vector most present in the block.

0037Advantageously, before proceeding to the classification of said speed vectors, there is a step of smoothing the value of each speed vector as a function of the immediate spatial environment of the contour point with which it is associated, for example by assigning to each contour point a speed vector, the value of which is the average of the speed vectors estimated for the points adjacent to said contour points, said adjacent points preferably being those present in a square window centered on said contour point.

0038According to a preferred characteristic of the invention, said method for detecting a predominant single contour is performed iteratively, on blocks of images divided into sub-blocks at each iteration, said iterative splitting being applied to each block or sub-block until a predominant single contour is detected in each block or sub-block, or until a minimum sub-block size is obtained.

0039Other characteristics and advantages of the invention will appear on reading the following description of a preferred material embodiment of the invention, given by way of illustration and not limitation, and the appended drawings in which:<ul id="ul0001" list-style="none"><li>- Figure 1 schematically illustrates the succession of steps of the coding / decoding process in which the preferred embodiment of the segmentation method of the invention is inscribed;</li><li>- Figure 2 is a flowchart illustrating the succession of the main steps of the preferred embodiment of the image segmentation method with edge detection, according to the invention;</li><li>- Figure 3 shows, schematically, a block of images comprising an outline</li><li>- Figure 4 is an enlargement of a sub-block of images of 3 x 3 pixels, crossed by a contour, and illustrating the contour detection method by difference in luminance;</li><li>- Figures 5, and 6a, 6b illustrate the principle of bidirectional detection of contours, on a block of images containing a closed trapezoidal contour.</li></ul>

0040FIGS. 7 to 12 detail the logical functions of a preferential hardware layout implementing the image segmentation method with edge detection according to the invention, and more precisely:<ul id="ul0002" list-style="none"><li>- Figure 7 relates to a first phase of calculating the histogram for the current image or portion of image, and determining the maximum of the histogram;</li><li>FIG. 8 relates to a second phase of selection of n vectors of speed of movement of the image points, in the histogram constructed in FIG. 7;</li><li>FIG. 9 relates to a material implementation of the classification phase of the n vectors selected in FIG. 8;</li><li>FIG. 10 relates to a third phase of reallocation by points of the n vectors selected and classified;</li><li>- Figures 11 and 12 explain a fourth phase of reallocation of the displacement speed vectors of the image points, by blocks of size N x N (N = 32, 16 and 8).</li></ul>

0041The entire segmentation process, with edge detection, according to the invention is presented in FIG. 2.

0042The method is applied to a source image 10, belonging to a sequence of electronic images. More specifically, the method is preferably applied to portions of images, so as to limit the requirements for calculation and storage means.

0043These image portions are for example quadrangular blocks representing 1/4, or 1 / 16th of an image.

0044The image portions 10 then undergo a filtering treatment 11, before being used on the one hand for a step 12 of estimation of movement between the current image and the previous image, and on the other hand, for a step 13 of detecting spatial contours in the current image.

0045The motion estimation step 12 makes it possible to obtain, for the image or the portion of image considered, a field of speed vectors defined by their coordinates (vx, vy). The estimation method is advantageously that described in the French patent application No. 8717601 already mentioned, but it is also possible to envisage using other methods for determining the field of speed vectors in the image.

0046Step 13 of detecting the spatial contours will be described in greater detail in relation to FIGS. 3, 4, 5, and 6a, 6b. This step makes it possible to identify the existence of contours in the image portion processed so as to select in the image the only points belonging to a contour.

0047This selection then makes it possible, in step 14, to draw a two-dimensional histogram (that is to say with two components vx, vy) of the speed vectors of the selected points only. In other words, the detection of the spatial contours made in step 13 makes it possible to make a selection on the field of the speed vectors of step 12, to retain in the histogram of step 14 only the displacement speeds of the points belonging to a contour.

0048Advantageously, said field of speed vectors can be determined beforehand by a method of estimating the movement, in the image plane, of the only selected contour points.

0049It may be advantageous to introduce a step (not shown) of detecting the existence of a "panorama" on the image, for example after step 13. The panorama corresponds to the case of a translation of the framing d 'a still image, for example when a camera scans a still landscape. In such a situation, it is economical from the point of view of processing costs and transmission rates, to identify that all of the contours are associated with a speed vector equal or very close. A single speed vector will therefore be transmitted for the entire image.

0050This situation is of course exceptional.

0051The processing of the two-dimensional histogram 14 makes it possible, in step 15, to select n independent vectors representative of the detected contours. As already mentioned above, independence ensures that there will be no conflict in the subsequent reallocation phase 16, 17 and representativeness is a factor of merit which accounts for the fact that each of the n vectors selected, in the histogram, suitable for reallocating a large percentage of points in the portion of the image processed.

0052The purpose of step 16 of "reallocation by point" is to replace the speed vector initially estimated at each image point, by one of the n representatives selected in step 15. This reallocation operation has as a criterion a notion of maximum absolute distance on each component vx, vy of the initial velocity vectors, and representatives.

0053Step 17 of "block reallocation" is carried out within a hierarchical coding procedure by iterative division of the blocks until an acceptable threshold of "uniformity" or "representativeness" is obtained by a speed vector. representative (quadtree). The initial blocks are, for example, 32 × 32 point blocks, which can be divided into four blocks of 16 × 16 points, themselves further cut into 8 × 8 point sub-blocks. According to the invention, the block reallocation process consists in: -assign to each block, or sub-block, the speed vector of a contour when there are in the current block points located on a single contour, and animated by an equal or near speed;

0054-allocate the speed vector most present in the block, if the block is spatially uniform, and therefore does not have a contour. This allocation is for example carried out on the use of a majority criterion within a local histogram of the speed vectors; -decide that the current block is non-compensable if, after maximum cutting in the iterative coding process, no representative speed vector is likely to be allocated to the sub-block.

0055The complete set of image blocks, each assigned to their representative vector, is then routed (18) to a processing of coding of the contours, and of the representative vectors, for transmission at reduced bit rate.

0056FIG. 3 illustrates the situation of an image block crossed by a contour, to which the segmentation method according to the invention provides a substantial improvement.

0057In the block 30 shown in FIG. 3, there is on the one hand a first zone 31 of points animated with a speed V1, and on the other hand, a second zone 32 of points animated with a speed V2. Each of these essentially homogeneous areas 31, 32 corresponds, for example, to a portion of the apparent surface of two adjacent objects, or objects superimposed in the plane of the image. The border 33 between these two zones 31 and 32 constitutes a contour, animated with a speed equal to either V1 or V2.

0058Within the framework of a classic segmentation process, consisting in assigning to the whole of block 30 a speed vector on a majority criterion, one notes on the one hand a decision difficulty (in the case where zones 31 and 32 are approximately equal surfaces), and on the other hand, a systematic psychovisual distortion, as already underlined in the preamble.

0059The method according to the invention consists in locating the contours 33, in the image blocks, so as to be able to allocate to the contour blocks, the displacement speed vector.

0060In the case of the presence of several contours of different speed in the same starting block 30, provision is made for a division of the block into four blocks of smaller size on which an identical analysis of location of the contours is carried out. This division can be carried out iteratively several times, up to a minimum size at which the block is declared non-compensable if none of the n vectors can be allocated.

0061Conversely, in the absence of a contour 33 in a block 30, the majority speed vector will advantageously be allocated to the block. Tests have shown that this allocation procedure, without constraint of representativeness appears satisfactory from a psychovisual point of view.

0062FIG. 4 illustrates the principle of contour detection by measuring a luminance gradient in the environment of a point 40.

0063The point 40 is here surrounded in particular by 4 adjacent points 41, 42, 43, 44 forming an image mesh. The mesh represented is crossed by a contour 45.

0064The detection of the contour 45 is carried out, in the case shown, by two brightness difference measurements: - a first measurement of difference in brightness, grad x, in the horizontal direction, between points 42 and 44; - a second measurement of different brightness: grad y, in the vertical direction, between points 41 and 43.

0065The identification of a contour is then carried out according to whether or not a luminance difference threshold is exceeded, for one or other of the gradient measurements carried out. Indeed, if grad x is high, there is detection of a vertical contour. On the other hand, grad x is less than a previously fixed threshold, we will consider that there is no vertical contour between the points considered.

0066Clearly, the same reasoning applies for the measurement of a vertical difference in brightness (grad y) corresponding to the detection of horizontal contours.

0067Of course, the measurement of the two gradients associated with point 40 could be carried out differently, for example by conventionally carrying out a measurement between the luminance of point 40, and of each of the following points 44 and 43, in horizontal and vertical directions respectively.

0068The principle of double measurement, horizontally and vertically, despite its redundancy in certain cases, makes it possible to cope with all scenarios.

0069This is represented in FIG. 5, and 6a, 6b, in which the detection of a trapezoidal contour 51 inscribed in an image block 50 is illustrated (FIG. 5).

0070The trapezoidal contour 51 consists of two horizontal sides 52, 53, a vertical side 54 and an oblique side 55. The measurement of the difference in horizontal brightness (grad x) is reliable for the detection of the portions of contour 54 and 55 (Figure 6a). This measurement of grad x, in block 50, makes it possible to retain the points of the contour portions 54 and 55. On the other hand, the measurement of grad x is not reliable for the detection of the horizontal contour portions 52 and 53.

0071These contour portions 52, 53 are on the other hand detected by means of the criterion of the difference in vertical luminosity of points grad y, as well as, again, the contour portion 55 (FIG. 6b).

0072Of course, the invention is not limited to the use of a gradient operator applied to the luminance of the image points for the detection of contours. Any equivalent process in relation to a psychovisual criterion of edge detection can also be used.

0073Figures 7 to 12 correspond to a description of a preferred material embodiment of the invention.

0074We suppose to have the components Vx and Vy in memory at point (x, y), corresponding to the full field of vector-velocities of an image portion.

0075To simplify the calculations and lighten the material realization, Vx and Vy are determined every second point, according to a staggered line structure in the current image.

0076x note the horizontal dimension (position of the image point in the line y) and y note the vertical dimension (position of the line in the image).

0077Figure 7 describes the functions corresponding to the construction phase of the two-dimensional histogram.

0078The histogram of speed vectors is established from the contours of the current image.

0079A "spatial gradients" operator defines (71) the spatial activity at point (x, y) and validates the reading of the speed vector at this point if one of the gradients is greater than a threshold (of typical value equal to 8 ).

0080The "gradient" operation considered is advantageously an absolute difference between the intensities I: .grad x = / I (x-1, y) - I (x + 1, y) / = / I (42) - I (44) / (see Fig. 4) .grad y = / I (x, y-1) - I (x, y + 1) / = / I (41) - I (43) / (see Fig. 4)

0081The validated vector (Vx, Vy) increments the content N (Vx, Vy) at the address (Vx, Vy) of the histogram by one unit (73): Vx, Vy ---> N (Vx, Vy) + 1

0082Advantageously, Vx and Vy are defined by 8 bits (1 sign bit, dynamic +/- 16, precision 1/8). But it has been found that, more generally, an expression on 6 to 8 bits is suitable, with 1 sign bit, and a tolerated precision of 2 to 3 bits after the decimal point.

0083Histogram 14 is a 256 x 256 memory, with a depth limited to 16 bits (dynamic = 64 K). This value is rarely reached since the source image is analyzed in pieces (typically, a piece represents 1 / 16th of HD image). If this value is reached, it can only be once (due to the maximum number of points per image piece).

0084The maximum MAX 75 of the histogram is determined during and on each access to the histogram 14. The incremented content of the current address is compared 74 with the last maximum recorded. The largest is kept for future comparison: MAX (i) = max (N (Vx, Vy) + 1, MAX (il)) i denotes the current instant and i-1 the last maximum retained.

0085The value of the maximum 75 is stored in memory 70 to allow successive comparisons 74 and is no longer of interest at the end of this local processing.

0086A management system 76 analyzes the image in predetermined pieces and controls 79 the initialization of the histogram 77, and of the maximum 78 at the start of each processed piece.

0087FIG. 8 corresponds to a phase of selection of n vectors in the histogram, chosen as being the most representative on the portion of the image processed.

0088At the start of this phase, there is a histogram 14 and the value (Vx, Vy) of the maximum of this histogram in memory 70.

0089Determining the n most important vectors amounts to extracting the n maxima from the histogram.

0090However, it is considered that all the points belonging to a certain range, for example distant from +/- dV (81) (in terms of vector-speed) will have the same representative vector.

0091The error thus introduced on certain points is not subjectively visible and the advantages are multiple, in term of "filtering" of the vector field, in term of total number of points represented or even in particular in term of precision for the compensation.

0092The parameter: dV = 1/8 was considered to be optimal following the experiments carried out and the results obtained. A higher value increases the number of points represented, but critical cases of light but noticeable saccades have been noted. These jerks are due to the switching between vectors or to a choice of vector that is too far away (to within dV) from the real value.

0093Knowledge of the maximum (Vx, Vy) 70 of the histogram and the parameter dV construct a regular grid 82 of the histogram centered on (Vx, Vy). Each elementary cell has for center: Vi = Vx + k. (2. dV + 1) Vj = Vy + k. (2. dV + 1) k is an integer, varying in steps of 1, from 0 to the values ​​verifying the inequalities: - 16 &lt;Vi &lt;16 - 16 &lt;Vj &lt;16

0094Each elementary cell has the dimensions (2. dV + 1). (2. dV + 1) centered on Vi, Vj.

0095To select the n vectors, all the cells are read 83 and the content of each is accumulated 84 (independently of the others). For the cell identified by 1, the associated integral I (1) is:<maths id="math0001"><img file="EP0348320A1_D0001.tif" /></maths>

0096Vi (1) and Vj (1) are the coordinates of the center of cell 1. N (V1, V2) is the content of the histogram of vector-velocities at point (V1, V2).

0097Classification 85 consists in determining the n strongest values ​​of I (1) and consequently, in knowing the n vectors (Vi (1), Vj (1) representatives.

0098Call I (m) the content of the accumulator m 90 (Figure 9) associated with the vector (Vi (m), Vj (m)), m belongs to (1, n).

0099If I (1) I (m), the content I (m) of the accumulator m takes the value I (1) and the vector (Vi (1), Vj (1)) is memorized in correspondence in the memory 91 The content I (m) is shifted (94) to position m + 1 and this, until n. The content I (n) is eliminated (95).

0100To avoid testing the inequalities one by one, the global solution of FIG. 9 proposes to conduct all the comparisons 96 in parallel. A processing absorbs the results and manages the offsets (93).

0101As illustrated in FIG. 10 (third phase), the initial vector-speed field is then reallocated at each point (x, y) by one of the n selected vectors.

0102We notice: Vx, Vy the original vector at point (x, y) Vix, Viy the vector of rank i (i belongs to (1, n). Simultaneous verification of inequalities: / Vx-Vix / &lt;or = dV / Vy-Viy / &lt;ou = dV allows to assign the vector (Vix, Viy) to the point (x, y).

0103Because of the regular grid of description of the histogram, there cannot be multiple solutions (criterion of independence between vectors).

0104There will be at most a couple of verified inequalities. Parallel operation of the n candidates 101 accelerates the processing and analysis 102 of the results of the comparisons transfers in memory 103 the code i at the point (x, y).

0105The advantage of memorizing the code is to limit the size of memory 103: Vx, Vy ---> 16 bit i ---> 4 bits if n = 16 candidate vectors

0106Thanks to initialization before 0 104, any point (x, y) such as: for all i: / Vx-Vix /> dV or / Vy-Viy /> dV i belongs to (1, n) is considered an unallocated point.

0107The fourth phase (Figure 11) corresponds to a block reallocation. We consider a block of size N x N. A vector will be allocated to this block if:<ul id="ul0003" list-style="none"><li>1) the points of this block located on a spatial contour of the image have the same vector (to within x%);</li><li>2) no contour exists in this block, in which case a majority criterion assigns the most present vector.</li></ul>

0108If none of the preceding conditions is satisfied, the size N x N of the block is divided and we consider 4 blocks of size N / 2 x N / 2 on which the above procedures are implemented separately.

0109If the size N x N is the minimum size allowed, the unallocated block is considered non-compensable.

0110From the gradients already calculated, we count the number of points of the block located on a contour, therefore verifying the system (72): grad x> threshold or grad y> threshold

0111The cumulative 111 is the function: NCC ---> NCC + 1, and allows to count the points located on a contour.

0112In parallel, there are 114 the number of points of the block located on a contour and attached to a vector, by the cumulative function 113. NVC ---> NVC + 1, if: code i <> 0, and if: grad x> threshold or: grad y> threshold

0113These functions 111, 113 are easily carried out by conventional electronic circuits or possibly by specialized circuits developed for this.

0114If: code i <> 0 (115) and if: grad x> threshold or: grad y> threshold (72), then the content of the address i is incremented by a unit 116 (the memory 117 containing the histogram will have been initialized at the start of the current block).

0115The determination of the maximum MMAX 118 of the histogram 117 and of the corresponding code KK is analogous to the processing already described in relation to FIG. 7. This value is stored in memory 119.

0116For the understanding of FIG. 12 relating to the choice of the vector of a block, it is recalled that: NCC: Number of contour points of the current block NVC: Number of contour points having a validated vector MMAX: maximum of the local histogram. We define : NCT: number below which the contour points are not validated (the block is then said to be uniform), for example: NCT = 5. NVC / NCC: ratio between the number of contour points having a validated vector and the total number of contour points. PCT: percentage imposing or not the influence of contour points having a validated vector, for example: PCT = 0.6. MMAX / NVC: greatest percentage of contour points having the same vector. VCM: acceptance or not of the majority vector of the contour points, for example: VCM = 0.8.

0117According to the results of the comparisons 121, 122, 123, 124 of FIG. 12, a transfer function 125 validates the output of a following circuit<ul id="ul0004" list-style="none"><li>1) CVM circuit: there is no spatial contour in the current block and the vector is chosen on the majority criterion. The majority vector of the block N x N is the vector most present in this block. By histogram and search for the maximum, the vector code corresponding to this maximum is retained. If the CVM circuit output is validated, all the points in the block are assigned the selected code.</li><li>2) RVPB circuit: the contour points mainly have the same vector which is allocated to all the points of the current block. The KK code corresponding to the majority contour vector is known (fig. 11). The RVPB circuit is then simply a validation of the KK code and its assignment to all the points of the block.</li><li>3) INDIC signal: allocation at block N x N is impossible and either the block is divided into 4 blocks, or the block is declared non-compensable if N x N is the smaller size allowed.</li></ul>

0118If the INDIC signal is zero, we test the size N x N.

0119If this size is not the minimum size, all the points of the block are assigned the null code which indicates that the block will not be compensable and must, in a complete HDMAC diagram, be treated by another way (French patent application 8717601, already cited).

0120The results obtained by implementing the invention, in the context of a High Definition image intended to be transmitted by MAC channel (HDMAC) are expressed in terms of image quality on the one hand, and bit rate on the other hand.

0121From the experiments carried out by the inventors, it appears that the proposed segmentation does not significantly degrade the quality of the reconstructed image compared to the original image. It is important to note that the segmentation affects one (or more) motion-compensated channel (s) in competition, within the same HDMAC system, with channels with linear filters. This system reproduces a global image, the result of the mixture of several ways.

0122To judge the speed, limited to 1.1 Mbits / s in the MAC channel, a simple operation makes it possible to evaluate the performance of the segmentation: flow = nb x (cb + cv) x nd x ft

0123The flow due to segmentation is the product of: nb = number of blocks per HD image sector nd = number of sectors in an HD image cb = number of bits to code the size of a block cv = number of bits to code a vector ft = time frequency

0124The figures currently used are: nd = 16 sectors per HD image cb = 1 (for 32 x 32, 16 x 16 or 8 x 8 blocks) cv = 4 (because 16 vectors per sector)

0125For a 40 ms channel with motion compensation, the sampling structure is of the "field skipped" type and therefore: ft = 25 Hz.

0126Knowing that on average: nb = 150, then the speed of a 40 ms channel is less than 400 kbits / s.

0127For an 80 ms motion-compensated channel, the odd frames are deinterlaced by linear filter. The movement is evaluated between the images thus formed. One of two original deinterleaved images is transmitted (spatially sub-sampled to comply with the MAC standard) and the segmented vector field used to reconstruct the non-transmitted image. The temporal frequency of transmission of the vectors is therefore: ft = 12.5 Hz hence a bit rate (for a compensated 80 ms channel) less than 200 kbits / s.

0128Since there is exclusion between the 40 ms and 80 ms channels, the total bit rate is less than the sum of the bit rates calculated above.