Apparatus and method for picture representation by data compression

Processes for pictorial representation by data compression including dividing a picture into regions of designated brightness values, fixing a characteristic scale for each region representing a number of pixels, dividing each region into cells, identifying each cell representing the basic structure of each cell by way of models, and storing and/or transmitting the data for each such model in the form of primary compression of the picture.

FIELD OF THE INVENTION 
This invention relates to apparatus and methods for representing pictures 
by data compression, particularly, but not exclusively, for the purpose of 
storing and/or transmitting the compressed data and subsequently 
reconstructing the picture in a manner as faithful as possible. 
BACKGROUND OF THE INVENTION 
The representation of various objects by data compression is a problem with 
which the art has been increasingly occupied in recent times. The problem 
is encountered in many cases, e.g. when a picture, or a succession of 
pictures, for example constituting a television broadcast, has to be 
registered in a magnetic memory, such as a video tape, or is to be 
transmitted over a distance by electromagnetic waves or by cable. On the 
one hand, it is of considerable economic importance to increase as much as 
possible the amount of optical and acoustic information that can be 
registered on a given memory, whereby to reduce the size and cost of 
magnetic tapes or other information storage means. On the other hand, the 
available wave bands are increasingly crowded, and so are the cables, and 
it is increasingly necessary to compress the transmitted data, so that as 
great a number of them as possible may be transmitted over a given 
frequency or by a given cable. Data compression problems, therefore, are 
increasingly acute, both in data storage and in data transmission. 
In particular, the art has dealt with the problem of compressing the data 
which represent an object, e.g. a picture. A process for the production of 
images of objects is disclosed in EPA 0 465 852 A2, which process 
comprises the steps of: (1) approximating the object by a model comprising 
at least one differentiable component; (2) establishing the maximum 
allowable error and the degree of the polynomials by which the 
differentiable components of the model are to be approximated; (3) 
constructing a grid of a suitable pitch; (4) computing the coefficients of 
the Taylor polynomials of the aforesaid differentiable components at 
selected points of said grid. 
However, none of the method and apparatus of the prior art are wholly 
satisfactory. Either the degree of compression is too small, or the 
picture cannot be faithfully reconstructed--viz. "decompressed"--from the 
compressed data, or both. There is another important requirement, not 
satisfied by known compression methods: application of image processing 
operations on compressed data, and natural extendibility of the 
compression scheme to video sequences compression. 
In describing this invention, two-dimensional pictures, in particular color 
pictures, such as those created on a television screen, are considered, 
but three- or more than three-dimensional objects could be represented by 
the apparatus and method provided by the invention, e.g. by defining them 
by means of views or cross-sections in different planes. 
The efficiency of a compression method depends on the one hand on the 
degree of compression, which should be as high as possible, but on the 
other on the faithfulness with which the picture reconstructed from the 
compressed data reproduces the original one. Perfect reproduction is 
obtained when the two pictures are visually undistinguishable. Two 
pictures are considered to be "visually undistinguishable", as defined by 
the MPEG (Motion Picture Expert Group of the International Standard 
Organization), when any ordinary viewer cannot distinguish between them 
when viewing them from a distance equal to six times the picture height. 
Different requirements for visual undistinguishability may be defined for 
different applications, such as: high end computer imaging, PC computer 
imaging, PC or video games, multimedia, pre-press applications, fax, 
colour video conferencing, videophone, archiving, medical imaging, aerial 
picture analysis, etc. However, the invention does not always require that 
the picture representation and the original be visually undistinguishable, 
though this is generally preferred: the degree of similarity may depend on 
the particular application and on the degree of faithfulness that is 
required of the representation in each case. 
SUMMARY OF THE INVENTION 
Broadly, the method of picture representation by data compression according 
to the invention comprises the steps of: 
1. subdividing the picture into regions; 
2. registering the values of a brightness function (or "grey levels") 
preferably at each pixel of the picture; 
3. fixing for each region a characteristic scale (hereinafter indicated by 
L) preferably defined in terms of a number of pixels; 
4. dividing each region into cells, each comprising a number of points 
(pixels) defined by two variables (coordinates), said cells having linear 
dimension in the order of L, and preferably equal approximately to L; 
5. identifying in each cell the "basic elements" or "structures", as 
hereinafter defined; 
6. in each cell, representing the basic elements by models (or submodels), 
as hereinafter defined; and 
7. storing and/or transmitting, for each cell the data defining each model, 
said data together representing the "primary compression" of the picture. 
Optionally, said data may be further compressed by any suitable methods, or 
otherwise processed as will be explained hereinafter. 
The regions into which the picture is subdivided are chosen in such a way 
that the data to be stored and/or transmitted for each of them will not be 
too numerous, and thus will not create files that are too cumbersome, 
particular with regard to the hardware that is available and to its 
capacity. Therefore in some cases the whole picture may be considered as a 
single region, or conversely, in other cases the regions will only be 
small fractions of the whole picture. Thus a suitable subdivision into 
regions will offer no difficulties to skilled persons. 
The picture to be represented is defined by the brightness values of the 
basic colours (usually three) for each pixel, or by equivalent data. Said 
values may be available in the form of computer files, or may be 
transmitted by a picture generating apparatus, e.g. a TV camera, or may be 
read by means of canners. In any case, when a colour picture is to be 
compressed, the method according to the invention can be applied 
separately to each of the three (or two or four) basic colours, and 
corresponding monochrome picture images are obtained. Alternatively, 
transformation of colour data, by methods known in the art (see e.g. R. J. 
Clarke, Transform Coding of Images, Academic Press, 1985, from page 248) 
may be carried out, and the three original monochrome signals, 
corresponding to the RGB system, can be transformed into one (monochrome) 
luminance signal and two reduced bandwidth colour-information carrying 
signals (sometimes referred to collectively, hereinafter, as "colour 
information signals). 
Therefore, hereinafter the expression "brightness function" (or "grey 
levels") should be understood as meaning the function defined by the array 
of the brightness values of any basic color or of the values of any of the 
luminance and/or colour information carrying signals. 
By decompressing the compressed and stored and/or transmitted data relative 
to the various cells, which contain all the chromatic information 
required, a "picture image", viz. an image which colosely approximates the 
picture, can be reconstructed. Said data include a brightness value for 
each pixel and for each basic colour, or equivalent information deriving 
from the transformation hereinbefore mentioned, and this information 
permits any apparatus capable of creating an image, be it e.g. a computer 
which has stored the said information in its memory, or a printer, a still 
camera, a TV camera, and so on, which receive the information from a 
computer, to create the picture image. Such apparatus and their operation 
are well known to persons skilled in the art. 
The information defining, in any chosen way, the brightness distribution of 
the various colors or signals, may be a function of time. This will occur 
e.g. whenever a motion or a television picture is compressed and 
reconstructed. In such a case, the method steps according to the invention 
should be carried out in a very short time, e.g. in the order of 30 frames 
per second. 
The apparatus according to the invention comprises: 
A-means for defining the brightness values of the basic colours, or 
equivalent information, preferably at each pixel of the original picture; 
B-means for registering the said brightness values or equivalent 
information, as sets of values associated with the pixels of a number of 
cells, of predetermined size, of each region of the picture; 
C-means for determining the parameters of any one of set of basic models, 
in particular by minimizing the square deviation of the values of said 
basic model from the values of a brightness function at the pixels of the 
cell; and 
D-means for storing and/or transmitting information defining the types of 
basic models chosen and the said parameters thereof. 
The means A- for determining the brightness values of the points of the 
cell may be different depending on the particular embodiment of the 
invention. They may consist, e.g., merely in means for relaying to the 
apparatus values which are defined by means that are not part of the 
apparatus, in particular by the apparatus which creates or transmits the 
original picture. Thus, if the invention is applied to the compression of 
a television movie, for the purpose of registering it on a video tape, the 
brightness values relative to each point of the television receiver screen 
are transmitted, as functions of time, from a broadcasting station via 
electromagnetic waves or via cable, and these same values can be relayed 
directly to the registering means B-. The brightness value determining 
means will then essentially be a part of the television receiver: said 
values will be registered in the apparatus according of the invention 
concurrently with their appearing as optical values on the receiver 
screen. In this case, one may say that the picture is being compressed in 
real time. A similarly situation will prevail if the picture to be 
compressed is not being transmitted, but has been registered on a magnetic 
tape: the reading of the tape, that would be carried out in order to 
screen the registered picture in a normal way, will directly provide the 
brightness values. In other embodiments, the invention may be used to 
compress a picture that is already optically defined. Then the brightness 
value determining means will be normally constituted by a scanner. 
The storing and/or transmitting mans D- may be conventional in themselves, 
and may be constituted, e.g. by magnetic tapes, such as video tapes, by 
optical or magnetic disks, or by television broadcasting apparatus, and 
the like. 
The stored and/or transmitted, compressed picture must be reconstructed by 
decompression from the compressed data, so that it may be viewed. 
Therefore, there must be additionally provided 
E-means for reconstructing the picture by producing at each point of each 
cell a color brightness, for each color, the value of which is defined by 
the value at said point of said basic model having said parameters. 
In some embodiments, decompressing mans E- are part of the apparatus 
according to the invention. Thus, if the invention is used to compress 
data for recording television pictures on video tapes, the apparatus will 
comprise means for actuating the television screen to screen pictures 
defined by the compressed data. This will generally occur when the 
reconstructed picture must be seen at the location at which it has been 
compressed. However, if the point at which the picture is to be seen, is 
different from the one at which the apparatus comprising components A- to 
D- is located, means E- will not be physically a part of sad apparatus. In 
general, means E- are functionally, but not necessarily or even usually 
structurally connected with means A- to D-. These latter, while usually 
connected with one another, need not necessarily be structurally combines. 
In a preferred aspect of the invention, the basic structures comprise 
background areas, edges, ridges, positive and negative hills and, 
optionally, saddles as hereinafter defined. 
In a preferred aspect of the invention, the identification of the basic 
structures and their representation by models are carried out by the 
following steps: 
I. constructing geometric models representing said structures; 
II. associating to each of said geometric models a mathematical model 
representing it; 
III. condensing said models to define a global model for each cell of the 
regions; and subsequently 
IV. encoding and quantizing the data defining said global model; wherein 
steps II and III may be partly concurrent. 
It should be understood that, since, as has been said before, the process 
of the invention is carried out separately on each basic color or on each 
luminance or color information carrying signal, the "objects" which the 
geometric models are intended to represent may not be, and generally are 
not, actually physical objects which the eye would discern in the picture, 
but represent characteristics of the distribution of the basic color 
brightness or the value of the color signal under consideration. 
Therefore, in principle, the objects and the corresponding models could be 
quite different for different basic colors or color information signals. 
Thus, in principle, the amount of compressed data required to represent a 
color picture would be three or four times as large as the amount required 
for each basic color or color information signal. However, it has been 
surprisingly discovered that it is possible to identify in the models two 
different kinds of parameter, which will be called respectively "geometric 
parameters" and "brightness parameters", such that the geometric 
parameters are, in most practical cases, the same for all the basic colors 
or color information signals. Thus, in most cases it is enough to process 
the monocromatic luminance signal and add the color data later, which 
color data, when operating according to the invention, may require as 
little as an additional 3% to 10% approximately of data. This is an 
important feature of this invention, particularly in its preferred aspect. 
It is therefore another preferred aspects of the invention a method of 
compressing color pictures, which comprises carrying out the compression 
method hereinbefore defined with reference to one basic color or 
monochrome signal and successively repeating it for the remaining basic 
colors or color information carrying signals, by using the same modes with 
the same geometric parameters and determining the appropriate brightness 
parameters, as will be defined hereinafter. 
In the process according to the invention, geometric and/or mathematical 
models are considered as "representing" picture elements or other 
geometric and/or mathematical models whenever they approximate these 
latter to a degree determined by absolute or relative parameters or 
thresholds, the determination of which is part of the invention. The 
absolute thresholds have a fixed value. The relative thresholds depend on 
the values of the quantity considered over a certain area, or over the 
entire region. Usually, but not necessarily, the relative thresholds have 
the form of kM, where k is a coefficient and M is the average value of the 
quantity over the area that has been chosen for averaging. 
The various thresholds will be defined as they come into play during 
various stages of the process, for specific embodiments of the invention. 
Definition of the basic elements or structures 
By "basic elements" is meant, in the broad definition of the invention, a 
number of simple structures such that in combination they approximate any 
actual structure or "object" that can be found in the picture. In carrying 
out the invention, a list of such basic elements is prepared for each 
application. Usually the same list is adequate for all applications of the 
same nature, e.g. for all TV pictures. 
As used in this specification, the term "submodel" is to be construed as 
meaning: a) an array of grey levels of RGB values for a certain part of a 
picture (e.g. grey level z=.PHI..sub.ab (x,y), wherein .PHI. is an 
expression depending on parameters a and b); or b) the geometry of certain 
objects on a picture (e.g. the form of a certain curve can be represented 
as y=.PSI..sub.cd (x), such as e.g. y=cx+dx.sup.2). 
The term "model" means an expression consisting of one or more submodels, 
and allowing for computing for any given x,y a grey level z=.PHI.(x,y). 
The parameters of submodels, representing the geometry of objects, are 
called "geometric parameters", and the parameters of submodels, 
representing grey levels, are called "brightness parameters". Some of the 
models explicitly contain submodels responsible for the position and the 
geometry of the described objects, as shown in the following example: 
In the model z=.PHI.(x,y), wherein .PHI. is equal to a.sub.1 x+b.sub.1 
y+c.sub.1, if y.gtoreq..alpha.x.sup.2 +.beta.x+.chi., and is equal to 
a.sub.2 x+b.sub.2 y+c.sub.2, if y&lt;.alpha.x.sup.2 +.beta.x+.chi., the 
geometric submodel is the curve y=.alpha.x.sup.2 +.beta.x+.chi. and 
.alpha.,.beta.,.chi. are the geometric parameters. z=a.sub.1 x+b.sub.1 
y+c.sub.1 and z=a.sub.2 x+b.sub.2 y+c.sub.2 are two other submodels of 
this model. 
Polynomial models or submodels are those given by polynomials of low degree 
(usually .ltoreq.4), with coefficients assuming a limited number of values 
(usually .ltoreq.256). 
To "represent" a picture, or a part thereof, or a certain object that is in 
the picture, by a model, means to replace the original grey or RGB levels 
z=f(x,y) by the grey level model values z=.PHI.(x,y). 
In all the definitions of picture objects (not of models and submodels), 
hereinafter, reference is made to a given part of a picture of a size 
approximately equal to the scale L. Therefore said definitions are 
scale-dependent. A list of basic elements, particularly suitable for 
representing TV picture, but also for other applications, will now be 
described. However, persons skilled in the art may modify it and add other 
basic elements, when dealing with other applications or with particular 
cases of the same application. 
Smooth objects and smooth regions--The word "smooth" is used and will 
always be used hereinafter to define those brightness distributions 
(brightness surfaces) that can be represented by a polynomial P(x,y) of a 
low degree, e.g. a degree generally not higher than 4, in a visually 
undistiguishable way. Thus smooth regions are those in which the 
brightness surface z=f(x,y) defining the distribution of a colour in the 
picture, can be so represented; and smooth objects are those any part of 
which inside any cell can be so represented by a polynomial model or 
submodel of a low degree. Analogously, a "smooth curve" is a curve in the 
neighbourhood of whose intersection with any cell the picture can be 
represented by a model, within which the curve is defined by a polynomial 
of low degree. 
Simple models or submodels are those containing a small total number of 
parameters (usually .ltoreq.6), each of these parameters assuming a 
limited number of values (usually .ltoreq.256). 
Simple models or submodels are those containing a small total number of 
parameters (usually .ltoreq.6), each of these parameters assuming a 
limited number of values (usually .ltoreq.256). 
Simple objects--An object, part of a picture, is said to be "simple", if 
for any cell the part of the object inside the cell can be represented in 
a visually undistinguishable way (as hereinbefore defined) by a simple 
model or submodel. 
Curvilinear structures--Are those in which the brightness distribution can 
be represented by a surface z=f(x,y), generated by a simple (as the word 
is defined hereinbefore) profile, a point of which follows a simple curve, 
the parameters defining the profile being simple functions of the position 
of said point on said curve. Curvilinear structures can be unbounded (in 
the cell under consideration), or bounded at one end, or at both ends to 
constitute a segment. They can also form nets, when several curvilinear 
structures are joined at some points or portions, that will be called 
"crossing". 
Local simple elements--An element is "local" if its diameter is comparable 
with L, at most 2 to 3 L. Local simple elements are those that are local 
and simple, as the latter word is defined hereinbefore. 
In practice, the aforesaid types of brightness distributions are never 
found in their pure form, but types that are sufficiently similar to be 
treated as such are generally found. 
The determination of the characteristic scale L is a fundamental step. If L 
is too small, the structure found in the cells--the "object"--can easily 
be represented by basic element models, but the amount of data that will 
be involved in the compression is too high for the compression to be 
successful. On the other hand, if L is too large, it is impossible to 
represent the objects in a visually undistiguishable way by means of basic 
element models. 
Therefore the choice of L will depend on each specific application, and L 
will be chosen as the largest scale that permits to approximate the actual 
objects by means of basic element modes in such a way as to achieve a 
visually undistinguishable representation, or at least as faithful a 
representation as desire for the specific application; and it will also 
depend, of course, on the quality and resolution of the original picture. 
L is expressed in terms of pixels. For instance, when applying the 
invention to the compression of television images, it is found that L 
should be comprised between 10 and 16 pixels, e.g. about 12 pixels. For 
most applications, L may be comprised between 6-8 and 48 pixels, but these 
values are not a limitation. A frequent value is L=16. It is appreciated 
that each cell, if square, contains L.times.L pixels, so that if L is 16, 
the cell will contain 256 pixels. A square cell having the dimensions 
L.times.L will be called the "standard cell". Since most hardware is 
designed to operate with ASCII symbols, such a size of cell or a smaller 
one is convenient. If a certain object is simple or smooth with respect to 
a given scale L, it is simple or smooth with respect to any smaller scale. 
It has been found that, for representing television pictures, if the 
picture is divided into cells of 4.times.4 pixels, and in each cell the 
grey levels are approximated by second degree polynomials, an essentially 
visually undistinguishable picture representation is obtained. Therefore 
in a television picture any object is smooth and simple on a 
characteristic scale of 4. Furthermore, for such an application, the array 
of basic elements hereinbefore described is adequate and sufficient for 
picture representation on any scale between 8 and 16, preferably of 12. 
In the preferred aspect of the invention, the basic structures are defined 
as follows: 
background (also called sometimes "smooth") areas are those wherein the 
values of the brightness function may be considered to be changed slowly; 
edges are curvilinear structures on one side of which the values of the 
brightness function undergo a sharp change; 
ridges are curvilinear structures defined by a center line, the 
cross-sections of which in planes perpendicular to the center line are 
bell like curves, and they are positive or "white" (ridges proper) or 
negative or "black" (valleys), according to whether at the point of each 
cross-section located on the center line the brightness function value is 
a maximum or a minimum; 
hills are points or small areas at which the brightness function value is a 
maximum (positive--white--hills or hills proper) or a minimum 
(negative--black--hills or hollows) and decreases or increases, 
respectively, in all directions from said point or small area. 
saddles are curvilinear structures which comprise a central smooth region 
bounded by two edges, wherein the brightness function values increase at 
one edge and decrease at the other. They may be treated as basic 
structures, for convenience purpose, or they may be separated into their 
aforesaid three components: two edges and an intermediate smooth area. 
The said basic structures represent a particular case of the basic elements 
hereinbefore defined. In particular, (white and black) ridges and edges 
are specific cases of curvilinear structures. Hills and hollows are 
specific cases of local simple structures. 
Preferably they are identified through the derivatives of the brightness 
function z=f(x,y), x and y being the Cartesian (or other) coordinates of a 
coordinate system of the region considered, or through the derivatives of 
an approximating function, as will be explained hereinafter.