Method for the processing of images by hierarchically organized queues

• US 5,463,698 A
• Filed: 12/29/1993
• Issued: 10/31/1995
• Est. Priority Date: 03/20/1991
• Status: Expired due to Term

• Current Assignee: Association pour la Recherche et le Développement des méthodes et processus Industriels
• Original Assignee: Association Pour La Recherche Et Le Development Des Methodes Et Processus Industriels (A.R.M.I.N.E.S)
• Inventors: Meyer, Fernand
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/119,126
• Time in Patent Office: 671 Days
• Field of Search: 382/41, 382/49, 382/37, 382/34
• US Class Current: 382/276
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A method for processing images using hierarchically organized queues is provided. In particular, the method relates to the segmentation and filtering of certain shapes whose contours appear to be imprecise due to the existence of image noise, thereby eliminating such noise and providing a more precise image. The disclosed method is applicable to all sectors of image analysis and is especially useful in the analysis of images acquired by tomographs used in the medical field, whether these images are two-, three- or even four-dimensional. The method can also be extended to numerous dimensions and to color images. The method is also of particular usefulness in the fields of traffic control, i.e., detection of vehicles and roads, and more generally to all fields of industrial vision. The disclosed method can also be essential in coding and image compression for telecommunications and archiving.

Claims

1. A method for processing an image stored in a memory containing, at each picture element address, a physical value of a physical element of a body associated with each picture element and a marker value associated with each said picture element used to obtain a physical image and a marker image, said method comprising an initialization phase and a processing phase, and being aimed at the construction of a result image, wherein in the initialization phase:

a hierarchically organized group of queues HOQ, is created, the queues of this group being of the first-in-first-out type and being differentiated from one another according to an order of priority determined by their correspondence with one value among the possible values of a priority parameter,

in at least one of the physical image and the marker image, picture elements for initiating the method are identified,

a level of priority of each initiating picture element is assessed as a function of the physical and marker values associated with the picture element or neighboring elements of the picture element,

the address of each initiating picture element is stored in a queue that corresponds to the level of its priority,

in the processing phase, steps 1 and 2 are repeated so long as the HOQ is not empty;

step 1;

the address of the picture element with the highest priority is extracted from the queue with the highest priority that is undergoing processing, x designating this picture element,

step 2;

neighbors of x are put on a neighborhood list of x, for each neighbor, y, of x that is found in said neighborhood list of x and that has never yet been stored in the HOQ during the processing phase, the level of priority of y is assessed as a function of its physical value or of physical values of picture elements of a neighborhood of y, the address of y is stored in the HOQ that corresponds to this level of priority, and x is given, in the result image memory, a label depending on its window.

2. Method according to claim 1, characterized in that an assessment is made of the value of a physical parameter that is used as a priority parameter, for a point t, at the time when said point is put into the HOQ.

3. Method according to claim 2, characterized in that, to assess the value of the physical parameter, a distance is computed between the point t and a neighboring marked region R.

4. Method according to claim 3, characterized in that, to compute the distance, a computation is made of the shortest distance between the color of t and the color of a neighbor of t in the region R having the color closest to t.

5. Method according to claim 3, characterized in that the mean color of all the picture elements constituting a region neighboring t is computed and in that, to compute the distance, the distance is computed from the color of the point t to this mean color.

6. Method according to claim 3, characterized in that a fixed reference color is defined for each region and in that, to compute the distance, the distance is computed from the color of the point t to this reference color.

7. Method according to claim 1, characterized in that the initiating picture elements are identified as those belonging to a marker region and possessing, in their neighborhood, a picture element not belonging to said marker region.

8. Method according to claim 1, characterized in that the initiating picture elements are identified as those picture elements that are outside a marker region and have a picture element of a marker region in their neighborhood.

9. Method according to claim 1, characterized in that each address of the initiating picture elements is stored in a queue relating to a unique initialization value.

10. Method according to claim 1, characterized in that

when a priority queue has been emptied of the addresses of the picture elements that it contained, it is eliminated from the group of the queues, and in that

the addresses of the picture elements selected subsequently to this elimination, which should have been stored in this eliminated queue, are stored in the queue with the highest-ranking priority that exists after the rank of this eliminated queue.

11. Method according to claim 1, characterized in that

when a priority queue has been emptied of the addresses of the picture elements that it contained, it is eliminated from the group of the queues, and in that

the addresses of the picture elements selected after this elimination, which should have been stored in this eliminated queue, are stored in a special queue with higher-ranking priority than all the other queues at a given time in the processing operation, to process these emergency situations.

12. Method according to claim 1, characterized in that, to assess the level of priority of y, a computation is made of the gradient of a physical magnitude measured in a body and assigned to a corresponding picture element for y at the place in the body at which this measurement is made.

13. Method according to claim 1, characterized in that, to assess the priority level of y,

an image parameter representing an image window of this picture element is prepared according to a computation algorithm.

14. Method according to claim 1, characterized in that, to select picture elements y neighboring a picture element x:

a selection is made of all the picture elements for which at least one of the address terms is different by one unit element from the corresponding term of the address of the picture element x.

15. Method according to claim 1, characterized in that, to select the picture elements y neighboring a picture element x:

a selection is made of all the picture elements for which at least one of the address terms is different at most by two unit elements from the corresponding term of the address of the picture element x.

16. Method according to claim 1, characterized in that, to select the picture elements y neighboring a picture element x:

a selection is made of all the picture elements that belong to a list attached to the picture element x.

17. Method according to claim 1, characterized in that, when it is being stored in the HOQ, y receives, in at least one of the marker image and result image, a label identical to a label that has been assigned to x in at least one of this marker image and result image.

18. Method according to claim 1, characterized in that, when y is being extracted from the HOQ, y receives, in at least one of the marker image and result image, a label determined as follows:

if the point x is a neighbor of two regions having different labels in the image, it is given a boundary picture element label, and the step 1 is recommenced for the next picture element of the HOQ;

if the point x is the neighbor of only one neighboring marked region, the point x is given the label of this region.

19. Method according to claim 1, characterized in that, when it is being stored in the HOQ, during the processing stage, a picture element receives a label indicating that it has been stored in the HOQ and that, when it comes out of the HOQ, it receives another label indicating that this element has come out therefrom.

20. Method according to claim 1, characterized in that, for any picture element x coming out of the HOQ and not yet having a label characteristic of the picture elements having come out of the HOQ, the following processing is applied to each neighbor y of x that does not yet have a label in the marker image:

a) a variable V is considered as a function of the vector images in x and in y,

b) the picture element y is stored with a priority V in the HOQ,

c) and the value of V is given to y as a result value.

21. Method according to claim 20, characterized in that the variable V has, as its value:

V=Max (Fx or Py) in which Px represents a value of a film function at the point x, Py representing a physical value at the neighboring point y.1.