Method of identification of arborescent structures in digital images and its application to an image-processing device

• US 4,771,467 A
• Filed: 12/03/1986
• Issued: 09/13/1988
• Est. Priority Date: 12/04/1985
• Status: Expired due to Term

• Current Assignee: Thomson-Cgr
• Original Assignee: Thomson-Cgr
• Inventors: Catros, Jean Y., Mischler, Denis
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): Parker, Michael D.
• Application Number:
  US06/937,618
• Time in Patent Office: 650 Days
• Field of Search: 382/6, 382/16, 382/19, 382/21, 382/25, 382/30, 382/37, 358/111, 358/260
• US Class Current: 382/130
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181

Abstract

In a method for identification of arborescent structures detected in digital images by starting from model arborescent structures, a matching operation consists in comparing an object tree with a model tree. The method involves computation of the distance between the object tree and the model tree in accordance with a so-called Selkow iterative method which utilizes predefined cost values for elementary operations of label-changing, insertion or destruction of sub-trees in the descriptive lists of the trees to be identified. Starting from all the steps of computation of the distance measurement, the elementary operations which have served to arrive at the final distance are recorded and identification is obtained by label changes of the sub-trees reduced to branches.

Claims

1. A method of identification of arborescent structures detected in digital images in which the branches of an object tree can be identified with those of a model tree, these two trees being defined in the form of a root and of a list of disjoint sub-trees each formed in the same manner or reduced if necessary to one branch, a label vector being assigned to each branch and the components of said vector being a function of the characteristics of said branches, wherein said method comprises:

in a first step, in converting the object tree to a model tree in a sequence of elementary operations on the entire set of sub-trees, a cost which is a function of the components of the label vectors of the branches constituting the sub-trees being assigned to each operation, these operations being either changes of label or insertions of sub-trees of the model tree or destructions of sub-trees of the object tree, and in selecting the least costly sequence of operations, the overall cost of which measures the distance between the trees in accordance with the so-called "Selkow" iterative method known per se,

then in a second step in resuming the sequence of operations in the opposite direction starting from the last operation performed so as to produce in respect of each step of the iterative computation, in accordance with the elementary operation which has served to obtain the minimum cost;

either a change of label;

a sub-tree of the object tree being identified with a sub-tree of the reference tree;

or insertion of a sub-tree of the model tree, in which case there is no corresponding sub-tree in the object tree;

or destruction of a sub-tree of the object tree, in which case there is no corresponding sub-tree in the reference tree;

the result of identification being formed by the entire set of label changes of the sub-trees reduced to their roots as obtained in this second step and the associated cost corresponding to the minimum distance of the sub-trees which have said branches as roots.

2. Application of the method according to claim 1 to a device for processing digital images.

3. Application according to claim 2 to images obtained by digital angiography for identification of blood vessels.