 |
Claims  |
|
|
I claim:
1. A device for segmenting, under the control of a sequencing stage for
furnishing corresponding control signals, a received textured image on the
basis of digital signals which are representative thereof, the segmenting
including characterizing each texture by representative parameters and
image decomposition into regions having different textures; said device
comprising:
for characterization of texture, a first sub-assembly following by a second
sub-assembly; the first sub-assembly including means for generating a
directionally morphologically filtered signal and a difference between
said received image and said directionally morphologically filtered
signal; the second sub-assembly including means for determining texture
parameters of said filtered image by computing a morphological gradient
from said difference; and
for regional decomposition of the filtered image, a third sub-assembly at
the output of said second sub-assembly; said third sub-assembly including
means for image segmentation of the morphological gradient by the
technique of extracting watershed lines.
2. A device for segmenting, under the control of a sequencing stage for
furnishing corresponding control signals, a received textured image on the
basis of digital signals which are representative thereof, the segmenting
including characterizing each texture by representative parameters and
image decomposition into regions having different textures; said device
comprising:
for characterization of texture, a first sub-assembly following by a second
sub-assembly; the first sub-assembly subjecting the received image to
directional morphological filtering to derive a directionally
morphologically filtered image; the second sub-assembly determining
texture parameters of said filtered image; and
for regional decomposition of the filtered image, a third sub-assembly at
the output of said second sub-assembly; said third sub-assembly subjecting
the texture parameters of the filtered image to regional segmentation by
the technique of extracting watershed lines in a texture parameter image
divided into blocks of a predetermined size;
(A) said first sub-assembly for directional morphological filtering
comprises:
(a) a first memory for storing the received image to be segmented;
(b) at the output of said first memory a first filter circuit for
subjecting the received image to directional morphological filtering,
thereby deriving a directional morphologically filtered image;
(c) a second memory for storing the filtered image; and
(d) a subtracter coupled to said first and second memories for deriving the
residue of the difference between the received image and the filtered
image, the residue forming a residual image which is stored in a third
memory;
(B) said second sub-assembly for determining texture parameters comprises:
(e) a circuit for integrating said residual image;
(f) a series arrangement of a fourth memory for storing the integrated
image, a circuit for spatial sub-sampling of the integrated image, and a
circuit for computing a morphological gradient of the sub-sampled image;
and
(g) a fifth memory for storing a global gradient produced at the output of
said computing circuit;
(C) said third sub-assembly for regional decomposition comprises a series
of arrangement of:
(h) a second filter circuit for morphological filtering of the stored
global gradient;
(i) a sixth memory for storing the filtered global gradient;
(j) a circuit for image segmentation of the filtered, global gradient by
the technique of computing watershed lines, thereby deriving an image of
regional segmentation labels; and
(k) a seventh memory for storing said image of regional segmentation
labels.
3. A device for segmenting, under the control of a sequencing stage for
furnishing corresponding control signals, a received textured image on the
basis of digital signals which are representative thereof, the segmenting
including characterizing each texture by representative parameters and
image decomposition into regions having different textures; said device
comprising:
for characterization of texture, a first sub-assembly following by a second
sub-assembly; the first sub-assembly subjecting the received image to
directional morphological filtering to derive a directionally
morphologically filtered image; the second sub-assembly determining
texture parameters of said filtered image; and
for regional decomposition of the filtered image, a third sub-assembly at
the output of said second sub-assembly; said third sub-assembly subjecting
the texture parameters of the filtered image to regional segmentation by
the technique of extracting watershed lines in a texture parameter image
divided into blocks of a predetermined size; wherein
(A) said first sub-assembly for directional morphological filtering
comprises:
(a) a memory for storing the received image to be segmented;
(b) at the output of said memory, a first four-position switch followed by
a parallel arrangement of four directional morphological filtering
circuits for filtering the stored image, thereby producing four respective
directional morphologically filtered images;
(c) a further memory for sequentially storing the four filtered images;
(d) a subtracter for sequentially deriving the residue of the difference
between the received image and each of the four filtered images, and a
further memory for sequentially storing four residual images formed by
said residues;
(B) said second sub-assembly for determining texture parameters comprises:
(e) a circuit for integrating each residual image;
(f) at the output of said integrating circuit, a second four-position
switch followed by four parallel circuit branches respectively comprising
a series arrangement of a further memory for storing a respective one of
the integrated images, a circuit for spatial sub-sampling of said
integrated image, a circuit for computing a morphological gradient of the
sub-sampled image, and a memory for storing the computed morphological
gradient; and
(g) an adder for combining the stored morphological gradients of the four
integrated images to derive a global gradient, and a further memory for
storing said global gradient;
(C) said third-assembly for regional decomposition comprises a series
arrangement of:
(h) a filter circuit for morphological filtering of the stored global
gradient;
(i) a further memory for storing the filtered global gradient;
(j) a circuit for image segmentation of the filtered global gradient by the
technique of computing watershed lines, thereby deriving an image of
regional segmentation labels; and
(k) a further memory for storing said image of regional segmentation
labels.
4. A segmentation device as claimed in claim 2, further comprising at the
output of said third sub-assembly for regional decomposition a forth
sub-assembly for merging the segmented regions in accordance with a
hierarchic classification, and successively for each pair of regions in
said classification deciding whether or not to merge dependent on a
criterion relating to the distribution of pixels in each segmented region.
5. A segmentation device as claimed in claim 2, further comprising at the
output of said third sub-assembly for regional decomposition a fourth
sub-assembly for sharpening contours in the segmented image by repeating
the computation of watershed lines for subdivisions of said image into
blocks of successively smaller size, iteratively repeating until the block
size reaches the resolution of a pixel.
6. An image segmentation system for segmenting a received image on the
basis of digital signals which are representative thereof, said image
being composed of textured regions which may be in juxaposition with
untextured regions; said system comprising as a first sub-assembly thereof
a segmentation device as claimed in claim 2 for segmenting the textured
regions of the received image, and further comprising:
a second sub-assembly for separating homogeneous regions of said image,
which regions correspond substantially exclusively to textures or slow
luminance variation, from heterogeneous regions which do not substantially
correspond to textures or slow luminance variation; said separation being
effected by determining for each region the residue of the difference
between an approximation of the output image produced by said first
sub-assembly and the received image, and comparing said residue with a
threshold applicable to said region;
at the output of said second sub-assembly, a third sub-assembly for sorting
the homogeneous regions into textured regions and regions having a slow
luminance variation; and
also at the output of said second sub-assembly, a fourth sub-assembly for
complementary segmentation of the separated heterogeneous regions.
7. A segmentation system as claimed in claim 6, wherein said second
sub-assembly for separating the homogeneous and heterogeneous regions
comprises a series arrangement of:
a circuit for polynomial approximation on the basis of the received image
to be segmented and images produced by said first sub-assembly during
segmentation of textured regions;
a polynominal synthesis circuit for receiving said polynominal
approximation and based thereon synthesizing an image which approximates
the luminance of each region of the received image;
a memory for storing the synthesized image;
a circuit which for each of said regions derives the residue of the
difference between the received image and the synthesized image;
a further memory for storing said residue; and
a first test circuit for comparing the stored residue or a quantity
directly related thereto with a threshold;
and wherein said third sub-assembly for sorting the homogeneous regions
comprises a second test circuit for computing for each of said regions the
standard deviation of said residue from the average value thereof, and
comparing said standard deviation with a threshold.
8. A segmentation system as claimed in claim 7, wherein said fourth
sub-assembly for complementary segmentation of heterogeneous regions
comprises a series arrangement of a circuit for selecting the
heterogeneous regions, a memory for storing said regions, a segmentation
circuit producing an image of regional segmentation labels, and a memory
for storing the image of regional segmentation labels.
9. A segmentation system as claimed in claim 7, wherein said fourth
sub-assembly for complementary segmentation of the heterogeneous regions
comprises:
a series arrangement of a selection circuit for exclusively selecting the
heterogenous regions, the output of said selection circuit being connected
to an input of an image memory for storing the received image to be
segmented; and
a segmentation circuit having an input connected to an output of said image
memory and an output connected to a memory in said first sub-assembly in
which is stored an image of regional segmentation labels of textured
regions in said image.
10. A segmentation system as claimed in claim 6, wherein said third
sub-assembly for sorting the homogeneous regions and said fourth
sub-assembly for complementary segmentation of the heterogeneous regions
are each connected to circuit means for coding the relevant sorting and
segmentation information for said regions.
11. A segmentation device as claimed in claim 3, further comprising at the
output of said third sub-assembly for regional decomposition a fourth
sub-assembly for merging the segmented regions in accordance with a
hierarchic classification, and successively for each pair of regions in
said classification, deciding whether or not to merge dependent on a
criterion relating to the distribution of pixels in each segmented region.
12. A segmentation device as claimed in claim 3, further comprising at the
output of said third sub-assembly for regional decomposition a fourth
sub-assembly for sharpening contours in the segmented image by repeating
the computation of watershed lines for subdivision of said image into
blocks of successively smaller size, iteratively repeating until the block
size reaches the resolution of a pixel.
13. A segmentation device as claimed in claim 11, further comprising at the
output of said third sub-assembly for regional decomposition a fourth
sub-assembly for sharpening contours in the segmented image by repeating
the computation of watershed lines for subdivision of said image into
blocks of successively smaller size, iteratively repeating until the block
size reaches the resolution of a pixel.
14. An image segmentation system for segmenting a received image on the
basis of digital signals which are representative thereof, said image
being composed of textured regions which may be in juxaposition with
untextured regions; said system comprising as a first sub-assembly thereof
a segmentation device as claimed in claim 3 for segmenting the textured
regions of the received image, and further comprising:
a second sub-assembly for separating homogeneous regions of said image,
which regions correspond substantially exclusively to textures or slow
luminance variation, from heterogeneous regions which do not substantially
correspond to textures or slow luminance variation; said separation being
effected by determining for each region the residue of the difference
between an approximation of the output image produced by said first
sub-assembly and the received image, and comparing said residue with a
threshold applicable to said region;
at the output of said second sub-assembly, a third sub-assembly for sorting
the homogeneous regions into textured regions and regions having a slow
luminance variation; and
also at the output of said second sub-assembly, a fourth sub-assembly for
complementary segmentation of the separated heterogeneous regions.
15. A segmentation system as claimed in claim 9, wherein said third
sub-assembly for sorting the homogeneous regions and said fourth
sub-assembly for complementary segmentation of the heterogeneous regions
are each connected to circuit means for coding the relevant sorting and
segmentation information for said regions. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a device for segmenting textured images on the
basis of digital signals which are representative of said images, by
defining each texture by representative parameters and decomposition of
each image into regions associated with the different textures. The
invention can be used, for example for preprocessing images before their
transmission and/or storage. The invention also relates to an image
segmentation system comprising such a device.
2. Description of the Related Art
The transmission or storage of images within very short periods of time
necessitates very high data rates which cannot generally be realised for
economic and technical reasons. It is thus necessary to compress the
information to be transmitted (or to be stored). Present data compression
techniques are conventionally based on signal processing by means of an
orthogonal transform with compression rates of about 10. Another approach,
based on a better analysis of the images concerned and leading to higher
compression rates, employs a method of preprocessing said images. Such
method consists of considering the images as being constituted by an
assembly of homogeneous regions each defined by a contour and an internal
texture.
Such an image preprocessing method is described, for example, in the
document "Segmentation adaptative pour le codage d'images", PhD thesis no.
691 (1987) presented by Mr. R. Leonardi at the Depanement d'Electricite de
l'Ecole Polytechnique Felerale of Lausanne. It provides a correct
segmentation into homogeneous regions when the luminance varies only
weakly in each of these regions, but leads to a severe oversegmentation
when these regions correspond to grass, raffia, wood textures etc. or, in
general, to zones in which a sort of structured and more or less
periodical aspect can be observed which is defined by a primary grain and
one or several rules of disposition or repetition of this grain on an
entire surface. For treating such textures, French Patent Application no.
2660459, whose introductory paragraph describes the diversity of currently
known segmentation processes in accordance with the texture type
concerned, proposes a segmentation method which is suitable for any type
of image and comprises particularly the following basic steps:
characterization of each texture by an assembly of parameters forming a
prototype vector and classification by decomposition of the image into
regions associated with the different textures, with a possible merging of
the regions obtained.
SUMMARY OF THE INVENTION
It is a first object of the invention to provide a device for segmenting
textured images in accordance with a novel method which carries out the
aforesaid basic steps.
To this end the invention relates to a segmentation device as described in
the opening paragraph and is characterized in that said device comprises:
(A) for characterization of the texture, a first sub-assembly for
directional morphological filtering followed by a second sub-assembly for
determining the texture parameters;
(B) at the output of the second sub-assembly for determining the texture
parameters, a third sub-assembly for segmentation into regions by the
technique of extracting watershed lines in a texture parameter image
subdivided into blocks of a given size; and
(C) a sequencing stage for furnishing different control signals for said
sub-assemblies.
The structure of the device thus proposed is novel for the following
reason. The mathematical morphology which, for effecting image
segmentation, uses a very efficient tool referred to as the watershed line
extraction, generally uses this tool for non-textured grey-tone images,
i.e. for isolating luminance zones wherein luminance is practically or
relatively constant. In principle, this technique is inapplicable in the
case of textured images because the zones corresponding to each texture do
not have a constant luminance. However, the difficulty which is thus
apparent may be reconciled by reconstituting, via original preprocessing
operations, the images to which the morphological tool may be applied.
Advantageously, the segmentation device is characterized in that:
(A) said directional morphological filtering first sub-assembly comprises
at least:
(a) a first memory for storing digital signals which are representative of
the image to be segmented;
(b) at the output of this first memory, a directional morphological
filtering circuit;
(c) a second memory for storing the obtained filtered image:
(d) a subtracter and, at its output, a third memory for storing an image of
the residue obtained from the difference between the original image and
the filtered image;
(B) said second sub-assembly for determining the texture parameters
comprises at least:
(e) a circuit for integrating the image of the residue;
(f) a series arrangement of a fourth memory for storing the image of the
texture characteristics obtained after filtering, a circuit for spatial
sub-sampling of this image and a circuit for computing the morphological
gradient;
(g) a memory for storing the global gradient present at the output of said
morphological gradient computing circuit;
(C) said third sub-assembly for segmentation comprises a series arrangement
of:
(h) a morphological filtering circuit;
(i) a seventh memory for storing the gradient thus filtered;
(j) a first circuit for segmentation by means of computing the watershed
fines;
(k) an eighth memory for storing the image of the labels.
In a specific embodiment the segmentation device according to the invention
is particularly characterized in that
(A) said directional morphological filtering first sub-assembly comprises:
(a) a first memory for storing the digital signals which are representative
of the image to be segmented;
(b) at the output of this first memory, a first four-position switch
followed by a parallel arrangement of four directional morphological
filtering circuits;
(c) a second memory for storing the four successively filtered images
obtained;
(d) a subtracter and, at its output, a third memory for storing the four
images of the residues successively obtained from the difference between
the original image and each of the four filtered images;
(B) said second sub-assembly for determining the texture parameters
comprises:
(e) a circuit for integrating the images of the residues;
(f) at the output of said circuit, a second four-position switch followed
by four parallel branches each comprising a series arrangement of a fourth
memory for storing the image of the texture characteristics associated
with the corresponding filtering operation, a circuit for spatial
sub-sampling of this image, a circuit for computing the morphological
gradient, and a fifth memory for storing said gradient;
(g) an adder for the output signal of said fifth memories;
(h) a sixth memory for storing the global gradient present at the output of
said adder;
(C) said segmentation third sub-assembly comprises a series arrangement of:
(i) a morphological filtering circuit;
(j) a seventh memory for storing the gradient thus filtered;
(k) a first circuit for segmentation by means of computing the watershed
lines;
(l) an eighth memory for storing the image of the labels.
A further embodiment of the segmentation device is characterized in that it
comprises, at the output of said segmentation third sub-assembly, a
further sub-assembly for merging the regions by establishing a hierarchic
classification of said regions and, successively for each of the pairs of
regions appearing in this classification, a decision of merging or not
merging as a function of a criterion related to the sizes which are
representative of the distribution of the pixels of each region.
In a preferred embodiment the segmentation device according to the
invention is also characterized in that it comprises, at the output of the
segmentation sub-assembly, a further sub-assembly for sharpening the
contours by repeating the extractions of the watershed lines for
subdivisions of the image into blocks of a smaller size, and this in an
iterative way until the resolution of a pixel is reached.
It is another object of the invention to provide a system for segmenting
images generally constituted notably, but not exclusively, by textures,
which system comprises to this end an image segmentation device as
described hereinbefore.
To this end the invention relates to a segmentation system comprising said
device but also:
(A) at the output of said device constituting a first sub-assembly for
initial segmentation, a second sub-assembly for separating the homogeneous
regions which correspond exclusively to textures or to regions having a
slow luminance variation, and for separating heterogeneous regions which
do not correspond, or correspond to a minor extent, to textures by
determining, for each region, the residual difference between an
approximation of the output image of said segmentation sub-assembly and
its input image and by comparing values of this difference or of a
directly related size with a threshold for the whole of said region;
(B) at the output of said separation sub-assembly, a third sub-assembly for
sorting the homogeneous regions into textured regions and into regions
having a slow luminance variation;
(C) also at the output of said separation sub-assembly, a fourth
sub-assembly for complementary segmentation of the heterogeneous regions.
In a particular embodiment this system is characterized in that said
sub-assembly for separating the regions comprises a series arrangement of
a circuit for polynomial approximation on the basis of the original images
and those obtained by initial segmentation, a polynomial synthesis circuit
for restoring an approximation function of the luminance of each region, a
memory for storing the output signals from said synthesis circuit, a
circuit for subtracting, for the concerned region, each original image and
the image of the polynomials present in said memory, a memory for storing
the residue constituted by this difference and a first test circuit for
this residue or for a quantity which is directly related thereto in view
of the separation, by way of comparison of said residue with a threshold,
of regions obtained by said initial segmentation into homogeneous regions
and into heterogeneous regions, and in that said sub-assembly for sorting
the homogeneous regions comprises a second test circuit for computing,
across the whole concerned region, the standard deviation of the residue
from the average value and for comparing this standard deviation with a
threshold.
In accordance with the proposed embodiment this system is characterized in
that said sub-assembly for complementary segmentation comprises a series
arrangement of a circuit for selecting the heterogeneous regions, a memory
for storing said regions, a segmentation device and a memory for storing
the image of the labels resulting from said segmentation.
However, in an advantageous embodiment in which the number of circuits can
be reduced, said system is characterized in that said sub-assembly for
complementary segmentation comprises a series arrangement of a circuit for
exclusive selection of the heterogeneous regions, the output of said
circuit being connected to a second input of the first memory for storing
the digital signals which are representative of the image to be segmented,
and a segmentation device whose input is connected to a second input of
said first memory and whose output is connected to the eighth memory for
storing the image of the labels.
This segmentation system may include the means for coding the various
information components obtained from segmentation and corresponding to
each region.
These and other aspects of the invention will be apparent from and
elucidated with reference to the embodiments described hereinafter.
BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1 to 4 illustrate different basic morphological transforms of a
function by a structuring element;
FIGS. 5 and 6 show an embodiment of a segmentation device according to the
invention;
FIGS. 7 and 8 illustrate the way in which the morphological filtering of
the global gradient is realised by geodesic erosion in the operation of
the device according to the invention;
FIGS. 9 and 10 show two embodiments of a segmentation system according to
the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS OF THE INVENTION
Before describing the embodiments, some notes relating to the textures and
the techniques by which these can be analyzed will be useful. Although
there is no strict definition of the notion of texture, any region can be
qualified as such which, whatever the zone observed, gives the same visual
impression, while the texture thus observed may be considered as a
macrotexture or, in contrast, as a microtexture in accordance with the
distance from which it is observed. A macrotexture seems to be defined by
a basic theme--a kind of grain--and by rules of dispositioning this theme
in the space by means of, for example, more or less regular repetition.
Such a texture has a relatively structured, periodical and thus ordered
aspect but, viewed from a larger distance, this structure and this
periodicity may disappear and, in contrast, the aspect may become
disordered.
This difficulty of formally describing a basic theme and its disposition
rules have led to the search for texture characteristics which can more
easily be quantified. This search has proceeded through successive steps
of analysis for extracting characteristic parameters from the texture(s)
concerned, and of segmentation for partitioning an image into regions
having homogeneous texture characteristics, which steps are often followed
by a synthesis step for the purpose of restoring the textures, for example
on the basis of parameters initially extracted for each region.
In the segmentation techniques used it is generally attempted to detect
discontinuities in an image or, in contrast, similarities of the image
characteristics, which means that the real contours of the objects (i.e.
the discontinuities in the image) are reproduced as precisely as possible
while minimizing the number of regions in order to avoid the formation of
artificial boundaries which do not correspond to a discontinuity. The
mathematical morphology particularly has available of a very efficient
technique for image segmentation, but only in applications where the
images concerned have non-textured grey tones corresponding to objects of
a relatively constant luminance. This technique, which is referred to as
the watershed line extraction (hereinafter abbreviated to WSL), is
described in the article entitled "Morphological Segmentation" by F. Meyer
and S. Beucher in "Journal of Visual Communication and Image
Representation", Vol. 1, no. 1, September 1990, pp. 21-46.
For a better understanding of the mathematical morphology and particularly
this WSL technique, it will be useful to represent the luminance function
as a relief in which the pixels of the grey level images appear clearer as
they are more elevated. This also applies to the gradient of this
luminance function and, in this relief, the crest lines of the gradient
correspond to the boundaries of the regions to be segmented. An image may
thus be considered as a juxtaposition of catchment basins at the bottom of
which there is a regional minimum, a son of plateau formed of dots having
a substantially uniform altitude, with all the neighbouring dots having a
higher altitude. If one pierces a hole in each regional minimum and if one
subsequently proceeds to a progressive immersion of the relief based on
regional minima, while taking care that the flood level rises at a
constant speed, it will be possible, whenever the floods from the two
regional minima meet each other, to construct a dam along the crest line
corresponding to the line where the floods meet each other so that the
floods from the two separate catchment basins do not merge.
However, the segmentation thus obtained by means of this WSL technique
cannot be applied to textured images because they do not have a constant
luminance. The Applicant's company has nevertheless attempted to use this
technique for an image constructed from correctly selected texture
parameters, rather than for a luminance image. For an original image which
is subdivided into blocks of pixels, these blocks have close texture
parameters if they relate to the same texture. Consequently, in images
which are no longer the original images but images of parameters
constructed from these original images, the blocks of pixels of the same
texture are characterized by very close grey levels. It is thus possible
to apply the WSL technique to an image evaluation other than luminance,
viz. to one of these parameters. For example, in the application described
hereinafter, to a morphological gradient G whose definition will be given
hereinafter.
It will be useful to first describe the main morphological tools currently
used for exploring the geometrical structure of images. The morphological
transform of a binary image represented by an assembly of discrete dam,
denoted X and defined in the space N of relative integral numbers, makes
use of a structuring element denoted B and which, chosen as a function of
the problem posed (form, dimension, orientation, etc.), is intended to
interact with the image for extracting useful geometrical information
components. The different basic transforms permitted by such a structuring
element B are the erosion and the dilation, illustrated in FIGS. 1 and 2,
as well as their combinations, i.e. opening and closure, illustrated in
FIGS. 3 and 4.
The morphological erosion of an image X by a structuring element B is
denoted X(-)B in this case and is used for narrowing this image. This
constriction may be written as follows:
X(-)B=[X+(-b)]
where X+(-b) is the result of a translation of the value b of the image X.
The resultant image is written, for example as:
Y="eroded function Y of X by B"=E.sup.B (X)
Similarly, the morphological dilation of X by B is denoted X(+)B and is
used for dilating the image, which dilation may also be denoted as
[X+(+b)] and corresponds, as hereinbefore, to a translation of the value b
of the image X, but in the opposite direction, so that an image Y is
obtained which is denoted as:
Y="dilated function Y of X by B"=D.sup.B (X).
These two basic operations may be combined to perform the more complex
morphological transforms. The opening of an image X by a structuring
element B, here denoted [X(-)B](+)B, consists of carrying out an erosion
followed by a dilation and its resultant image is written, for example as:
P=D.sup.B [E.sup.B (X)]
Similarly, the closure of an image X by B, denoted [X(+)B](-)B consists of
carrying out a dilation followed by an erosion and its resultant image is
written as:
F=E.sup.B [D.sup.B (X)]
The two latter transforms have for their object to smooth the contours of
the assemblies on which they act. In fact, an opening suppresses the
contour protuberances which are smaller than the structuring element, and
a closure closes the contour dips which are smaller than the structuring
element. Generally, these two transforms thus eliminate the components
which are smaller than the structuring element used.
The functions thus defined for simple geometrical boundaries, in this case
for the binary images, may be generalized for grey-tone images. If (x,y)
defines the position of a pixel X of the grey level image a(x,y), the
eroded grey level E(x,y) of X by B is given by the expression:
E(x,y)=min[a(x-i,y-j)-b(-i,-j)]
where b(i,j)=0 or -.infin. (minus infinity) dependent on whether (i,j)
belongs to B or not. The dilated grey level D(x,y) of X by B is similarly
given by the expression:
D(x,y)=max[a(x+i,y+j)+b(i,j)]
As is shown in the examples of FIGS. 1 and 2 illustrating the erosion and
the dilation, respectively, of a function f by a structuring element B,
the erosion tends to smooth the crests of the relief, i.e. to suppress the
bright patches of small thickness, and the dilation tends to fill up the
dips, i.e. to suppress the dark patches which also have a small thickness.
Similarly, with grey tones, the opening P and the closure F of a function
f by the structuring element B, illustrated in FIGS. 3 and 4 and denoted
as:
P(x,y)=sup[E.sup.B (f(u,v))]
F(x,y)=inf[D.sup.B (f(u,v))]
respectively, with (u,v) relating to B, have for their object to suppress
the luminance peaks and the luminance troughs, respectively, whose size is
smaller than that of the structuring element, while leaving the other
forms substantially unchanged.
Among other types of transforms, the morphological gradient G which is
given by the expression:
G(f)=[(f(+)B)-(f(-)B)]/2
may be defined, which corresponds, as it were, to half the difference
between the dilated function of f by B and the eroded function of f by B.
After this description relating to textures and morphological transform
techniques, the image segmentation device according to the invention will
now be described. This device, which is shown in FIGS. 5 and 6 to be
considered conjunctively, comprises a sub-assembly 100 for directional
morphological filtering. This sub-assembly 100 comprises a first memory 10
for storing the digital signals which are representative of the image to
be segmented (in this case as a function of the different textures which
it contains). The output of this memory 10 is connected to the common
input of a first four-position switch 5, followed, at its four parallel
outputs, by four directional morphological filtering circuits 11, 12, 13,
14. The four filtering circuits 11 to 14 provide the possibility of
realising four transforms of the image, each consisting of a successive
opening and closure for which the structuring element is plane and has a
width of 1 pixel, a length of 3 pixels and orientations of 0.degree.,
45.degree., 90.degree. and 135.degree., respectively. The four filtered
images are successively stored in a second memory 20. A third memory 30
provides the possibility of storing the image of the residue for each
structuring element, which residue is obtained at the output of a
subtracter 25 from the difference between the original image stored in the
memory 10 and each of the filtered images stored in the memory 20 (each
residue is given by the absolute value of this difference). The value of
this residue for each pixel and for each of the four morphological
filtering operations constitutes a texture parameter and it is possible to
establish as many texture parameter maps as there are variants of such
filtering operations.
In this implementation of the device shown in FIGS. 5 and 6, each pixel of
the image is thus replaced by four information components whose regrouping
may be considered as a vector having four components. However, a texture
cannot be defined from pointed attributes, because a single pixel is
neither representative of the grain nor of the rules of disposition of the
structure and the neighbourhood of this pixel must be used. To be able to
extract the texture characteristics in an objective manner, it is
necessary to know a sample thereof, having a size which is sufficient to
enable effective recognition of the texture portion which is present.
To this end a sub-assembly 200 for determining the texture parameters is
arranged at the output of the sub-assembly 100. This sub-assembly 200
comprises a circuit 35 for integrating the image of the residue, which
circuit is arranged at the output of the third memory 30 and with which
homogeneous zones can be formed where the value of the vectorial
components is substantially constant over large areas. The size m.times.n
of the integration window is a function of the type of the original image:
in the present case a window dimension of 24.times.24 pixels is maintained
for images which are constituted by 512.times.512 pixels, but it will be
evident that the presence of macrotextures in the image will necessitate a
higher resolution in order that the windows can contain all the texture
information. On the other hand, the integration thus realised is a simple
computation of the average value in this case, but, in such a computation,
for example the influence of each pixel could be weighted as a function of
its distance to the centre of the window.
The output of the integration circuit 35 is connected to the common input
of a second switch 36 whose non-common outputs, four in this case, are
connected to four parallel branches comprising a series arrangement of
fourth memories 41 to 44 and sub-sampling circuits 45 to 48. The memories
41 to 44 provide the possibility of successive disposal, in parallel, of
four images of texture characteristics corresponding to each of the four
morphological filtering operations performed. The sub-sampling circuits 45
to 48 provide the possibility of a spatial sub-sampling of these images
over all p.times.q pixels in the horizontal and vertical directions,
respectively, and each block of p.times.q pixels is now replaced by a
sub-sample which will hereinafter be referred to as macropixel (in the
example described, p=q=16). Associated with each macropixel is the value
taken from the memories 41 to 44 and corresponding to the average value of
the texture parameters which is obtained after integration on the selected
window. This sub-sampling operation now enables all the subsequent
operations at the resolution p.times.q to be carried out, with the
elementary entity being the block p.times.q and no more the pixel. It
should be noted that within such a block the choice has been made for a
simple computation of the average value, but other, more complex
computations may be adopted. Notably for refining the boundaries between
blocks, the contribution of each pixel may also be weighted as a function
of its distance to the centre of the block in accordance with, for example
a Gaussian law.
The four parallel branches are also provided with four circuits 51 to 54
for computing the morphological gradient, four memories 55 to 58 for
storing the gradients thus computed, which memories are referred to as
fifth memories. The outputs of these fifth memories constitute those of
the four branches and are connected to an identical number of inputs of an
adder 59 supplying a global gradient G.sub.G which is stored in a sixth
memory 60. The description hereinbefore has dealt first with the WSL
technique and then with the technical choice of applying this technique to
the images constructed from relevant texture parameters and particularly
from the morphological gradient G. In fact, within a texture the
variations of the gradient G are relatively less important, while at the
level of the boundaries between regions of different texture the global
gradient is higher (higher as the contrast between these regions is
greater).
The actual segmentation is now realised in a segmentation sub-assembly 300.
This segmentation by way of the WSL technique comprises two steps, the
first consisting of marking the regions which are to be extracted and the
second consisting of outlining the regions of the image in a definitive
manner. A marker, which is a small assembly of pixels within the region
and constitutes, as it were, the nucleus of its development should
correspond in a unique manner to the region which it marks. A good
candidate for this marker role is the minimum of the global gradient G in
each region. It can be ascertained that the application of the WSL
technique to all the detected regional minima leads to a relatively
considerable oversegmentation because some minima are not really
significant (they are only due to small fluctuations of the gradient
within anyone of the textures).
To avoid this oversegmentation, a preprocessing operation is carried out in
the sub-assembly 300, which operation eliminates these insignificant
minima. This preprocessing treatment is realised with the aid of a circuit
65 for morphological filtering by way of geodesic erosion. In addition to
the description hereinbefore, relating to several basic functions of the
mathematical morphology, it is here noted that the geodesic distance
d.sub.z (x,y) between two dots x and y of an assembly Z is the lower limit
of the different possible path lengths between x and y in Z. This distance
may be denoted as d.sub.z (x,y)=inf[lengths C(x,y)] where C designates an
arbitrary path in Z between x and y (between two dots situated in two
distinct catchment basins as obtained by the WSL technique, this distance
is thus conventionally considered as being infinite because these two dots
cannot be confluent). The geodesic sphere having a radius R centered on x
thus is referred to as the assembly S(x,r) of dots y relating to the same
assembly Z, such that their geodesic distance d.sub.z (x,y) at the do | | |
