Method of bridging between contour elements in an image

• US 4,843,630 A
• Filed: 11/24/1986
• Issued: 06/27/1989
• Est. Priority Date: 11/26/1985
• Status: Expired due to Fees

• Current Assignee: Thomson -Cgr
• Original Assignee: Thomson -Cgr
• Inventors: Malo-Renault, Francois, Catros, Jean Yves
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/933,922
• Time in Patent Office: 946 Days
• Field of Search: 364/414, 358/111, 358/96, 358/160, 382/6, 382/22
• US Class Current: 382/130
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2207/10116 X-ray image
• CPC Class Codes: G06T 2207/30101 Blood vessel; Artery; Vein; Vascular
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

A method is provided for bridging between disjointed contour elements in an image by searching for an optimum bridging path between the facing ends of disjointed contour elements in the image. The method of the steps of defining a search window between each of the facing ends of the disjointed controur elements, considering in the window the different image points as nodes on a graph, determining an elementary cost associated with each path connecting each node to its neighboring nodes from amplitude and/or orientation data of the luminance function used for detecting the contours and in determining the optimum path by following, from the costs obtained, a line for which the luminance gradient of the detected points appears to be a maximum.

Claims

1. A digital processing method for bridging facing ends of disjointed contour elements in an image defined by pixel elements having intensity values stored in a digital image memory, comprising the steps of:

defining a search window in a portion of the digital image memory defining points between each of the facing ends of the disjointed contour elements;

intersecting said points in the portion of the digital image memory defining the search window by lines and columns so as to form a graph for measuring a luminance gradient of the pixel element intensity values stored in the portion of the digital image memory defining points located at crossing points of the lines and columns inside the search window;

forming in the portion of the digital image memory defining said search window an elementary path connecting each crossing point to each of its neighboring crossing points;

computing an elementary coding cost for each elementary path between neighboring crossing points depending on the luminance gradient of the points located in the portion of the digital image memory defining the search window;

computing an optimum path for linking the facing ends of the disjointed contour elements by following, from one end of one contour element, a line linking all elementary paths having a minimum coding cost, and storing the optimum path in the portion of the digital image memory defining said points between facing ends of the digital contour elements.

2. A digital processing method as claimed in claim 1, wherein each elementary coding cost C_ij computed in said elementary coding cost computing step for going from one crossing point i to a neighboring crossing point j is defined by a relationship

3. A digital processing method as claimed in claim 2, wherein the optimum path computed in said optimum path computing step is determined as a function of the local orientation of the elementary path found at each crossing point j of the graph for causing a shape of a desired path to intervene in the value of the elementary coding cost for each elementary path between neighboring crossing points.

4. A digital processing method as claimed in claim 3, wherein the desired path is a rectilinear path and each elementary coding cost C_ij is defined by a relationship equal to one of

5. A digital processing method as claimed in claim 3, wherein the desired path has a local orientation which varies progressively, and each elementary coding cost C_ij is defined by a relationship

6. A digital processing method as claimed in claim 3, comprising the further step of calculating along the optimum path computed in said optimum path computing step a criterion of quality C_r defined by the relationship ##EQU2## where A_i =the amplitude corrected by the orientation A_i =Max-C_ij of the luminance gradient at crossing point i of the path, N=the number of crossing points on the optimum path and a_max =the maximum amplitude of the luminance gradient on the optimum path, whereby bridging is effected if C_r is greater than a predetermined threshold.

7. A digital processing method as claimed in claim 1, comprising the further step of selecting an optimum path computed in said optimum path computing step if the total coding cost of said line linking all elementary paths having a minimum coding cost with respect to the number of crossing points in the optimum path is less than a predetermined threshold.