US4843630A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of bridging between contour elements in an image
Assignee: General Electric CGR SA
•
Filing: 1986-11-24
•
Granted: 1989-06-27
•
Expires: 2006-11-24
Abstract
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.
Inventors
- 👤 Jean Yves Catros
- 👤 Francois Malo-Renault
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 15:09
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20; G06Q; G06Q10/00; G06Q10/04; G06T7/00; G06T7/10; G06T7/12; G06T2207/00; G06T2207/10; G06T2207/10116; G06T2207/30; G06T2207/30004; G06T2207/30101
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
236 words
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.
Claim 2
Dependent Claim
236 words
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.
Claim 3
Dependent Claim
80 words
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 C.sub.ij =Max-a.sub.j, where Max designates a maximum amplitude of the luminance gradient in the portion of the digital image memory defining the search window, and a j designates an amplitude of the luminance gradient at crossing point j.
Claim 4
Dependent Claim
68 words
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.
Claim 5
Dependent Claim
95 words
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 C.sub.ij =Max-a.sub.j +K.sub.1 ·|θ.sub.j -θ.sub.mean | and C.sub.ij =Max-a.sub.j,/(K.sub.2 ·Q) where K 1 and K 2 are constants, Q=|θ j -θ mean | if θ j ≠θ mean or Q=1/K 2 if θ j =θ mean and θ j and θ mean designate respectively the local orientation at crossing point j and the mean of the local orientations at said facing ends.
Claim 6
Dependent Claim
75 words
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 C.sub.ij =Max-aj/K.sub.2 ·Q, where K 2 is a constant, Q=|θ j -θ i | if θ j ≠θ i and Q=1/K 2 if θ j =θi and θ j and θ i designate respectively the local orientation at crossing points j and i.
Claim 7
Dependent Claim
97 words
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.
Claim 8
Dependent Claim
60 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-06-26 | 1992-12-26 | 1993-06-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-06-26 | 1996-12-26 | 1997-06-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-06-26 | 2000-12-26 | 2001-06-27 | $7700.00 | Window Closed / Lapsed |