Process and device for sequential image transformation

• US 4,809,348 A
• Filed: 08/07/1986
• Issued: 02/28/1989
• Est. Priority Date: 08/07/1985
• Status: Expired due to Fees

• Current Assignee: Association Pour La Recherche et Le Developpement Des Methodes et Processus Industriels Armines
• Original Assignee: Association Pour La Recherche et Le Developpement Des Methodes et Processus Industriels Armines
• Inventors: Klein, Jean-Claude, Meyer, Fernand
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US06/894,123
• Time in Patent Office: 936 Days
• Field of Search: 358/260, 358/284, 382/41, 382/43, 382/44, 382/45, 382/47, 382/49, 382/54-56
• US Class Current: 382/259
• CPC Class Codes: G06T 5/20 using local operators

Abstract

The transformation applies to images defined by pixels each presenting a characteristic, such as a brightness, defined by a digital value, with the pixels being distributed according to a matrix and their relations and distances established by a neighborhood graph. All or part of the image is explored according to a predetermined exploration mode and the value of each pixel is modified as a function of the values of a set of associated pixels, assuming their value in at least the image and being located inside a sliding window related to the pixel to be transformed, identical for all pixels and constituting a structuring element. The transformed version of each pixel is immediately substituted for the preceding value in an image memory. To implement the process, a device can be utilized having a morphological opening processor, an image memory and a morphological processor with rewrite processing.

Claims

1. Process for skeletonization of an image made up of a matrix of pixels, wherein each of the pixels constitutes a central pixel in a neighborhood consisting of a predetermined plurality of pixels adjacent to the central pixel, each of the pixels in said matrix presenting a characteristic feature, such as a brightness, defined by a digital value, said method comprising the steps of:

(a) transforming said image by eliminating its plateaus to generate a relief without plateaus;

(b) coding said relief without plateau in the neighborhood of each of said pixels according to a predetermined coding algorithm to provide a coded relief represented by coded values;

(c) marking peak points on said coded relief, said peak points belonging to a skeleton of shapes in said image; and

(d) starting from said peak points, generating upstream parts of said skeleton by a re-write transformation including;

(d1) a first scan of the image in a direct direction, during which a value is selected for each pixel in the image which is responsive to values of a set of pixels within a structuring element associated with the pixel whose value is to be selected and identical for all pixels;

the selected value of each pixel is immediately substituted for the coded value in a image memory, whereby the pixel values in said structuring element include coded values and already selected values; and

(d2), after symmetry or rotation of the structuring element, repeating step (d1) using a reversed direction scan, at least once.

2. Process according to claim 1, wherein said digital value of each pixel is binary and, during step (a), the plateaus are eliminated by generating an ERODE function of the image.

3. Process according to claim 2, wherein said digital value is binary and the relief is coded as a RELIEF function having any one of four values defined as:

space="preserve" listing-type="equation">RELIEF(x)=0 if ERODE(x)=0

space="preserve" listing-type="equation">RELIEF(x)=1+[ERODE(x)+2 modulo 3] if not.

4. Process according to claim 1, wherein, the digital value of each pixel being considered as an altitude of that pixel, the plateaus are eliminated during step (a) by construction of a flow graph in at least two passes, as follows:

(a1) during a first pass, generating arrows each directed from a pixel x0 towards a pixel x1 in the neighborhood of pixel x0 when x0 has an altitude higher than the altitude of x1;

(a2) during a second pass, generating additional arrows from each pixel x0 toward a pixel x1 in the neighborhood which has the same altitude as x0 when an arrow has already been generated starting from x1 and there is no arrow starting from x0,

(a3) repeating subsequent passes until arrows are no longer created.

5. Process according to claim 1, wherein said plateaus are eliminated during step (a) by constructing a digital function having a specific value for each pixel from 0 to a predetermined maximum value of the digital values, said digital function being equivalent to a flow graph and being constructed in at least two successive passes:

(a1) carrying out a direct video scanning of the matrix and carrying out the following transformation on each pixel d having a neighborhood;

##EQU28## wherein;

B is an auxiliary image initialized at said maximum digital value, and

C(x)=Max-1 if A(x)>

A(d),

C(x)=B(x) if A(x)=A(d),

C(x)=1 if A(x)<

A(d) for x=a, b or c

with pixel x being considered as having an altitude higher than a pixel y if;

A(x)>

A(y) or

A(x)=A(y) and, at the same time, B(x)>

B(y).

6. Process according to claim 1, wherein, the digital value of each pixel being considered as an altitude of the respective pixel:

each pixel x of the matrix is coded as follows during step (b);

pixel x and the pixels in the neighborhood thereof having an altitude above pixel x are coded 2,

pixels in the neighborhood of pixel x having an altitude below pixel x are coded 0,

pixels in the neighborhood pixel x having an altitude equal to pixel x are given all possible combinations of values 0 and 2,

whereby a family (vi) of neighbors is obtained, for each pixel,

and, during step (c), a pixel x is considered as a peak point, if it has a neighborhood belonging to the family (vi) and for which one of the following three conditions is fulfilled;

all pixels in the neighborhood of pixel x are equal to zero and zeroing x would eliminate a particle consisting of 2s,

zeroing x would create a bridge between two particles consisting of 0s which had no mutual connection between themselves in the neighborhood of x,

zeroing x would eliminate the only connection existing between two particles consisting of 2 which have no other connection in the neighborhood of pixel x.

7. Process according to claim 1, wherein one subset only of all possible sets of peak points is retained during step (c) by applying an additional predetermined selection criterion.

8. Process according to claim 1, for transformation of an image made up of a square matrix of pixels, each pixel having a neighborhood which is defined with a four connexity when relating to a shape and a four connexity for background, wherein:

the neighborhood of each pixel is coded as follows during step (b);

each pixel at the center of a neighborhood of four neighboring pixels is coded 1 when said neighborhing pixels have the same digital value as the central pixel to be coded,

pixels having higher values than the central pixel in the neighborhood are coded 2; and

pixels having lower values than the central pixel in the neighborhood are coded 0;

and all pixels which do not verify any of the following configurations;

##EQU29## (where the . signs indicate that the value of the pixel is indifferent) nor any of the configurations deduced therefrom by rotation or symmetry, are detected as peak points during step (c).

9. Process according to claim 8, including the additional step of

(c1) marking, as additional peak points, the pixels which verify at least one of the configurations:

##EQU30## (where the . signs indicate that the value of the pixel is indifferent) or any of the configurations deduced therefrom by rotation, such additional pixel representing ends of barbules.

10. Process according to claim 6, wherein pixels x1 are marked as being upstream from previously marked peak pixel x if

the altitude of x1 is greater than that of x, and

if, in a predetermined structuring element surrounding x and including a plurality of pixels, vector x₀ x₁ has a slope greater than slopes of two vectors having x as an origin, having as an end pixels of the structural element and close to x1.

11. Process according to claim 10, for generating a geodetic skeleton, wherein the pixels upstream of the peak pixel are determined along a first direction of the matrix at a time, successively for each direction of the matrix.

12. Process according to claim 1, further including the step of completing the skeleton in all areas where a first pixel of the skeleton and a second pixel of the skeleton upstream of the first pixel are not connected by a path by inserting into said skeleton mutually adjacent points of the matrix which constitute a path of minimum length between the first and second pixels.

13. Process according to claim 1, wherein, with matrix being square and the image comprising particles which can present barbules whose ends are not part of the peak points, during step (c) in addition to the peak points, the pixels are detected having a number of neighbors whose altitude is lower than their own, greater than a predetermined number, so as to retain the pixels constituting the end of the barbules.

14. Process according to claim 6, wherein, with the matrix being hexagonal, the neighborhood of each pixel is coded during step (b) in the following manner:

pixel x and its respective neighbors having the same altitude are coded 1;

the respective neighbors having a higher altitude are coded 2,

the pixels having lower altitude are coded 0 and in that during step (c) all pixels which do not verify any of the following configurations are detected as peak points;

##EQU31## (where the pixels represented by . have the value of 0, 1 or

     2) or any of the configurations which are deduced therefrom by rotation.

15. Process according to claim 6, wherein, with the matrix being hexagonal, and with binary euclidian, pixels whose neighborhood is as follows are detected as peak points, with a close rotation:

##EQU32## (where 2 indicates that the pixel in question has a value of 0 or 1 but not

     2)

and four points are also detected as peak points at once when they present the following configuration;

##EQU33##

16. Process according to claim 6, wherein the matrix being square and each pixel having a neighborhood which is defined with 8 connexity when relating to a shape and 4 connexity for background, all of the pixels which do not verify any of the following configurations are detected as peak points:

##EQU34## where the . signs indicate that the value of the pixel is indifferent) or any of the configurations deduced therefrom by rotation or symmetry.

17. Process according to claim 6, wherein, with the matrix being square, and each pixel having a neighborhood with 8 connexity for shape and background, all pixels which do not verify any of the following configurations are detected as peak points:

##EQU35## (where the . signs indicate that the value of the pixel is indifferent) or any of the configurations deduced therefrom by rotation or symmetry.