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

Claim 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.

Claim 2

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.