Method and device for the numerical coding of an image, more particularly a television image

A method and device for the numerical coding of an image, more particularly a television image, made up of pixels (elementary points) which are regularly distributed in the plane of the image, and to which one or more radiometric qualities denoted as components C.sub.i are allotted. In the image, windows (f) are determined which have a predetermined geometrical shape and comprise a certain number of pixels (p); for each window regroupings are carried out into classes (R1,R2 . . . ) of radiometries (spectral or spatial) of the ends of the vectors representing the pixels or combinations of pixels of the image in space of N dimensions, in accordance with a criterion of proximity; for each class (R1,R2 . . . ) from the individual values of the pixels forming the class, N typical radiometries are defined which will be stored or transmitted to be used in the reconstruction of the image; to define each pixel, a characteristic code of the class (R1,R2 . . . ) to which it belongs will also be stored or transmitted enabling the pixel to be given the corresponding typical radiometries for the reconstruction of the image.

The invention relates to a method or a device for the numerical coding of 
an image, more particularly a television image, made up by elementary 
points (pels or pixels) which are regularly distributed in the plane of 
the image and to which are allotted one or more radiometric qualities 
denoted as components C.sub.i. 
The components C.sub.i can be, for example, the measurements of the 
radiometries of each pixel in N spectral channels supplied by suitable 
pickups staged over the spectrum of radio-electric frequencies; visible, 
infrared, X radiation, etc . . . They can also be quantities deduced from 
the measured radiometries, in a single spectrum zone of a predetermined 
spatial arrangement of pixels, by a linear transformation defining N 
independent channels. 
The digitalization of an image for its processing or transmission causes a 
very large volume of information to appear which is always difficult to 
handle if acceptable fidelity is to be maintained. 
In the example of colour television, it is considered that the density and 
precision of sampling for the practically distortion-free reproduction of 
a colour image requires about 6 million bits, at the rate of 16 bits per 
pixel. The numerical output of a television transmission on this basis 
implies a channel of 170M bits/second--i.e. the equivalent of 2,500 
telephone calls. This is a ratio which is prohibitive in view of current 
cost levels and which would heavily penalise the economics of such a 
transmission system. 
Attempts have therefore been made to evaluate numerical processing methods 
adapted to reduce such output and, for this purpose, to eliminate as far 
as possible the redundancy of the message. In practice this means avoiding 
the repetition of information already transmitted as long as the 
variations observed, in space or in the time between adjacent samples, are 
lower than certain values defined in relation to the required quality 
(signal-to-noise ratio, undesirable structures and fluctuations, 
sensitivity to errors, etc.) 
Numerous proposals, using differential coding techniques, orthogonal 
transformations, statistical coding methods and a combination thereof have 
been tried out with differing degress of success, although none of them 
has been found completely satisfactory. It has also been proposed (G 
LOWITZ "Recognition of shapes and processing of images", AFCET-IRIA 
Congress, Feb. 21-23, 1978, pages 699-714) to adopt a method using a 
technique frequently known by the Anglo-Saxon term "clustering". In that 
method for the numeral coding of an image, more particularly a television 
image, windows are determined in the image which have a predetermined 
geometrical shape and comprise a certain number of elementary points; for 
each window regroupings are performed into classes of radiometries 
(spectral or spatial) of the ends of the vectors which represent the 
pixels or combinations of pixels of the image in space or N dimensions in 
accordance with a criterion of proximity; one defines for each class, from 
the individual values of the pixels forming the class, N typical 
radiometries which will be stored or transmitted to be used in the 
reconstruction of the image; to define each pixel a characteristic code of 
the class to which it belongs is also stored or transmitted enabling it to 
be given the typical corresponding radiometries for the reconstruction of 
the image. 
It is a primary object of the invention to provide a method and device for 
numerical coding of images which are free from or at least less subject to 
the aforementioned disadvantages and which more particularly enable a high 
compression rate to be obtained. 
To this end the invention proposes a method characterised in that a 
processing of high spatial frequencies is performed by a unit 
transformation one of whose coefficients, that of the new value 
corresponding to lower spatial frequencies, is associated with the 
components of different spectral channels for processing by a 
complementary classification. 
The idea of proximity, the measurement of which is used as the criterion 
for regrouping the pixels into classes, must be understood in a very wide 
sense to be defined in accordance with an application of the method, as 
will be seen hereinafter. The metrics associated with it must in fact take 
into account each quality criterion essential for the satisfactory 
reconstruction of the image; these may differ substantially in dependance 
on the end sought (for example, fidelity of contours, rendering of 
half-tints, strong differentiation of textures or colours, etc.) in the 
application envisages. 
The criterion of proximity can be, for example, the distance, in 
conventional metrics, in space of N dimensions between the end of the 
vector representing a pixel and the end of a vector representing a class; 
in that case for each window a number of classes can be established which 
are identified by a vector whose N components correspond to predetermined 
values of the radiometries for each channel of the image; for each pixel 
the distance in space of N dimensions is calculated between the end of the 
vector representing such pixel and the end of each vector representing a 
class; the distances thus obtained are compared for each pixel, and the 
pixel is included in the class corresponding to the shortest distance 
obtained; for each pixel on the one hand a code is stored or transmitted 
enabling the class to be identified in which the pixel has been included, 
while on the other hand a dictionary is stored or transmitted which gives 
for each class the components of the vectors representing that class and 
obtained by calculation from the different pixels belonging thereto. 
The method is based on the characteristics of the natural images which 
indicate the possibility of grouping the pixels (elementary points) of an 
arbitrarily bounded subimage (or window) into a restricted number of 
judiciously selected classes. As a result each pixel can be qualified by a 
code with a small number of bits whose meaning is given by the specific 
conversion table (dictionary) of the subimage processed. 
In the histogram of the radiometries of the window (or subimage), groups of 
points included in a predetermined class must be discovered whose initial 
radiometric values can be validly replaced by a group of radiometric 
values corresponding to that of the class. 
Instead of transmitting or storing for each pixel or combination or pixels 
the radiometric values discovered, they are given a code (the number of 
the class in which they were included), whose number is much lower than 
the assembly of possible radiometries. To make the message intelligible it 
is enough to add to each window (assembly of classes) a dictionary in 
which each class code is explained by its corresponding radiometries. 
To make considerable compression possible, subimages (windows) of 
sufficient volume must be processed to enable the transmission of the 
dictionary of the conversion table to be considered as marginal in the 
global volume of the message. 
Preferably, for a particular window, after a first classification of the 
elementary points in the predetermined classes has been carried out, and 
radiometries typical of the points have been calculated for each class 
from the points which were included in such class, a fresh classification 
of each elementary point is performed into fresh classes based on the 
calculated radiometries, such iteration operation being repeated as many 
times as necessary to obtain a predetermined precision. 
By an adaptive method, therefore, an attempt is made to obtain the best 
radiometry representative of each group of pixels included in a class, so 
as to introduce only a negligible error into the energy balance of the 
transformation. 
Clearly, the efficiency of such a clarification is intimately bound up with 
the statistical properties of the image, in both spectral and spatial 
energy distribution. To use such statistics to the best advantage, the 
method should be applied to homogeneous data--i.e. data characterising one 
or other of these aspects independently. For example, we can deal with the 
various C.sub.i components of the same pixel in different spectral 
channels and form the classes in accordance with a criterion of spectral 
similarity. In monochrome we can also define the N channels referring to a 
spatial distribution of the pixels or combination of pixels in a group of 
suitable shape. The fact is that this method may prove less effective if 
the two types of data, spectrum and spatial, are classified 
simultaneously, thus bringing into play two different categories of 
statistics. 
This problem is solved by the processing of generally panchromatic spatial 
high frequencies by a unit transformation, one of whose coefficients, that 
of the mean value corresponding to lower spatial frequencies, is 
associated with the components of different spectral channels for 
processing by a complementary classification such as that described 
hereinbefore. 
In practice, in colour television, in order to make the best use of the 
image, procedure is as follows: a number of elementary points are combined 
and for each combination a new value of the luminance and chrominance 
components [(Y.sub.M) (R-Y).sub.M (B-Y).sub.M ] is determined from each 
component from each elementary point of the combination; the previously 
mentioned classification operations are performed; and, for the 
reconstruction of all the elementary points on reception, a linear 
transformation is applied to the luminance signals (Y) of each of the 
elementary points of a combination which enables the volume of information 
to be transmitted to be reduced, and the values of the complementary 
coefficients resulting from such transformation are transmitted and, on 
reception, an expansion of information is performed by deducting, from the 
mean values transmitted [(Y.sub.M) (R-Y).sub.M (B-Y).sub.M ] and the 
transformed values also transmitted, the luminance and chrominance values 
for each elementary point of a group. 
The combination of the points may concern four or sixteen adjacent pixels, 
which are grouped in accordance with the type of probing, orthogonal, 
quincunx or raster which may have been selected. 
Two complementary conjoint zones are therefore defined by selecting for 
each of them the mode of coding best adapted to their nature. 
The first zone forms a polychromatic subassembly, each point of which 
corresponds to the mean point of a combination and comprises components 
obtained with a lower probing density. 
The second zone required for a reconstruction with full resolution is 
formed from the high frequencies of the luminance signal (Y) on its own, 
without any chromaticity information. 
Advantageously, the unit transformation used is a Walsh Hadamard 
transformation. 
The window is advantageously formed by at least one horizontal line; in the 
case of the television image, the window is advantageously formed by two 
contiguous lines. Advantageously, there are thirty two classes. 
The invention also relates to a device for putting the method defined 
hereinbefore into effect; such a device is characterised in that it 
comprises: 
means for forming a window in the colour image and for sweeping the whole 
image by such window; 
means for acquiring the values associated with each elementary point of a 
window; 
means for calculating the distances between the end of the vector 
corresponding to an elementary point or a mean point of the combination of 
a number of elementary points and the ends of the vectors identifying each 
class; 
comparator means enabling each elementary point or each mean point to be 
included in the class corresponding to the shortest distance calculated; 
and means for calculating the components of the vector identifying a class 
from the different points belonging thereto, the output of such device 
being connected to the means for transmitting the output data. 
Apart from the arrangements set forth hereinbefore, the invention consists 
in certain other arrangements which will be described more specifically 
hereinafter in connection with the special embodiments described in detail 
with reference to the accompanying drawings.

DETAILED DESCRIPTION OF EMBODIMENTS 
In the following description, mainly with reference to colour television 
images, based on an analysis of the trichromatic image into the three 
primaries "red, green and blue" supplying three independent channels will 
for reasons of simplification be presented as a combination of such 
primaries R, V, B, to give the luminance (Y). 
In this example the number of channels N is therefore equal to three. 
However, the method and device according to the invention are also suitable 
for treating images with a number of images higher or lower than three. 
The colour television image can be considered as a combination of three 
primary images I1, I2, I3, shown diagrammatically on the left hand side of 
FIG. 1 and corresponding to the three channels. Each image is made up of 
pixels p distributed in lines; the pixels of image I1 are associated with 
the radiometry values for the first channel, those of the image I2 being 
associated with the radiometry values for the second channel, and those of 
the image I3 being associated with the radiometry values for the third 
channel. 
COMPRESSION BY