Method and apparatus for image analysis and processing by identification of characteristic lines and corresponding parameters

• US 6,760,483 B1
• Filed: 11/21/2000
• Issued: 07/06/2004
• Est. Priority Date: 10/13/2000
• Status: Expired due to Fees

• Current Assignee: Vimatix (Bvi) Ltd.
• Original Assignee: Vimatix (Bvi) Ltd.
• Inventors: Elichai, Yoram, Yomdin, Yosef
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US09/716,279
• Time in Patent Office: 1,323 Days
• Field of Search: 382/162, 382/167, 382/173, 382/199, 382/203, 382/215, 382/232, 382/233, 382/241-243, 382/248, 382/254, 382/275-276, 382/286, 382/288, 382/298, 382/299-300, 345/418-419, 345/423, 345/586, 345/588, 348/384.1, 348/390.1, 375/240.08, 375/240.09
• US Class Current: 382/241
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 2207/30141 Printed circuit board [PCB]
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes

Abstract

A method and apparatus is provided for analyzing and processing images by identification of characteristic lines and corresponding parameters. More particularly, the method and apparatus transforms an image into mathematical models derived from the characteristic lines and parameters, based on repetitive image patterns. The parameters include central lines, signatures, cross-sections, characteristic strips, margins, end areas, fitting transformations and fitting sequences. Each of the parameters associated with the identified characteristic lines are representable by mathematical models, which accurately approximate the geometric and brightness (or color) attributes of the respective characteristic lines.

Claims

1. A method for representation of an image comprising:

identifying at least one characteristic line of the image, based on a global image pattern, each characteristic line comprising a line along which a visual pattern repeats itself;

determining a central line corresponding to the characteristic line, the central line approximating a shape of the characteristic line and comprising a plurality of points; and

determining a cross-section at each of the plurality of points along the central line, the cross-section comprising at least one geometric parameter and at least one brightness parameter.

2. The method of claim 1 for representation of an image, further comprising:

determining a basis cross-section representative of the characteristic line;

transforming the basis cross-section to the cross-sections of the plurality of points along the central line; and

assembling a characteristic line model representing the characteristic line, the characteristic line model comprising the central line, the basis cross-section and information representative of the transformed cross-sections.

3. The method of claim 2 for representation of an image, further comprising:

performing at least one of storing, transmitting and processing the characteristic line model.

4. The method of claim 2 for representation of an image, wherein the image is a digital image.

5. A method for representation of an image comprising:

identifying at least one characteristic line of the image, based on a global image pattern, each characteristic line comprising a line along which a visual pattern repeats itself;

determining a central line corresponding to the characteristic line, the central line approximating a shape of the characteristic line; and

identifying a plurality of patterns along the central line.

6. The method of claim 5 for representation of an image, further comprising:

determining a basis signature representative of the characteristic line;

transforming the basis signature to approximate at least one repetition of the visual pattern along the central line; and

assembling a characteristic line model representing the characteristic line, the characteristic line model comprising the central line, the basis signature and information representative of the transformations of the basis signature.

7. A method for representation of an image, comprising:

detecting a plurality of edges on the image, based on a global image pattern;

detecting adjacencies among each of the plurality of edges;

interpreting common adjacencies as characteristic lines;

determining a central line corresponding to each of the characteristic lines, the central line approximating a shape of the characteristic line and comprising a plurality of points; and

detecting a plurality of cross-sections corresponding to the plurality of points along the central line, each of the plurality of cross-sections comprising at least one geometric parameter and at least one brightness parameter.

8. The method of claim 7 for representation of an image, further comprising:

detecting a plurality of ridges on the image, based on a global image pattern;

detecting adjacencies among each of the plurality of ridges;

interpreting common adjacencies as characteristic lines;

determining a central line corresponding to each of the characteristic lines, the central line approximating the shape of the characteristic line and comprising a plurality of points; and

detecting a plurality of cross-sections corresponding to the plurality of points along the central line, each of the plurality of cross-sections comprising at least one geometric parameter and at least one brightness parameter.

9. The method of claim 7 for representation of an image, further comprising:

subdividing each of the plurality of edges into a corresponding plurality of spline segments;

evaluating each of the plurality of spline segments and identifying adjacent spline segments; and

identifying adjacency intervals on each of a plurality of edge components corresponding to each of the plurality of edges.

10. The method of claim 9 for representation of an image, wherein identifying adjacent spline segments corresponding to each of the plurality of spline segments comprises:

scanning the plurality of spline segments; and

identifying for one of the plurality of spline segments the other spline segments comprising (i) at least one point less than or equal to a predetermined distance from the selected one spline segment, (ii) a direction that forms an angle with a direction of the selected one spline segment less than or equal to a predetermined value, and (iii) a midpoint that, when joined by an adjacency pointer with a midpoint of the selected one spline segment, results in an adjacency pointer having a direction that forms an angle with the direction of each of the joined remaining spline segments which differs from 90 degrees by less than or equal to a predetermined value; and

repeating the identification for each of the plurality of spline segments.

11. A method for representation of an image comprising:

detecting a plurality of edges on the image;

subdividing each of the plurality of edges into a corresponding plurality of spline segments;

evaluating each of the plurality of spline segments and identifying adjacent spline segments;

connecting, with an adjacency pointer, a midpoint of the evaluated spline segment with a midpoint of each of the corresponding adjacent spline segments, to create a plurality of adjacency couples;

identifying adjacency intervals as continuous chains of adjacent couples;

identifying a central point of each adjacency pointer within each adjacency couple;

joining the central points of each adjacency pointer within each adjacency interval, forming a central line corresponding to a characteristic line, the central line comprising a plurality of points;

detecting a plurality of cross-sections corresponding to the plurality of points along the central line, each of the plurality of cross-sections comprising at least one geometric parameter and at least one brightness parameter;

determining a basis cross-section representative of the characteristic line;

determining a fitting path corresponding to the plurality of cross-sections, the fitting path comprising a transformation of the basis cross-section to the cross-sections of the plurality of points along the central line; and

assembling a characteristic line model representing the characteristic line, the characteristic line model comprising data representing the central line, the basis cross-section, and the fitting path.

12. The method of claim 11 for representation of an image further comprising:

performing at least one of storing, transmitting and processing the characteristic line model data.

13. The method of claim 11 for representation of an image, wherein identifying adjacent spline segments corresponding to each of the plurality of spline segments comprises:

scanning the plurality of spline segments; and

identifying for, a selected one of the plurality of spline segments, remaining spline segments comprising (i) at least one point less than or equal to a predetermined distance from the selected one spline segment, (ii) a direction that forms an angle with a direction of the selected one spline segment less than or equal to a predetermined value, and (iii) a midpoint that, when joined by an adjacency pointer with a midpoint of the selected one spline segment, results in an adjacency pointer having a direction that forms an angle with the direction of each of the joined remaining spline segments which differs from 90 degrees by less than or equal to a predetermined value; and

repeating the identification for each of the plurality of spline segments.

14. The method of claim 11 for representation of an image, wherein detecting the plurality of cross-sections comprises:

identifying a plurality of scanning points at equal intervals along the central line of a characteristic line;

projecting a line segment orthogonal to the central line at each of the plurality of scanning points;

identifying a characteristic point on the orthogonal line segment at each point where the orthogonal line segment intersects a margin of edges forming the characteristic line;

sampling an image brightness at each of the characteristic points on the orthogonal line segment; and

approximating the cross-section of each orthogonal line segment by a cross-section of the edges corresponding to the sampled image brightness.

15. The method of claim 11 for representation of an image, wherein detecting the plurality of cross-sections comprises:

subdividing the central line into a plurality of subpieces, each having a predetermined length;

identifying a plurality of pixels located within a characteristic strip corresponding to each of the plurality of subpieces, and defining each of the plurality of pixels at least according to a distance from the central line and a brightness parameter; and

deriving a cross-section at each of the plurality of subpieces based on the defined pixels.

16. The method of claim 15 for representation of an image, further comprising:

forming a quadratic difference between each derived cross-section and the cross-section derived from the next one of the plurality of subpieces;

minimizing the quadratic differences with respect to the parameters of a fitting transformation;

identifying a minimized fitting transformation of each derived cross-section and the cross-section derived from the next one of the plurality of subpieces;

composing a plurality of fitting transformations from the plurality of minimized fitting transformations and interpolating each of the plurality of fitting transformations along the corresponding line segment;

deriving a fitting path from the interpolated fitting transformations;

redefining each of the plurality of pixels according to a distance from the central line corrected according to the fitting path and a brightness parameter corrected according to the fitting path; and

deriving a corrected cross-section at each of the plurality of subpieces based on the redefined pixels.

17. The image representation method of claim 16, further comprising:

identifying a geometrically central point of the corrected cross-section; and

applying the fitting path to the central point to derive a corrected central line.

18. A method for representation of an image, having an original size, comprising:

reducing the image from the original size;

identifying at least one characteristic line of the reduced image, each characteristic line comprising a line along which a visual pattern repeats itself;

re-scaling the reduced image to the original size;

determining, for the re-scaled image a central line corresponding to the characteristic line, the central line approximating a shape of the characteristic line and comprising a plurality of points; and

identifying a plurality of patterns along the central line.

19. The method of claim 18 for representation of an image, further comprising:

determining a basis signature representative of the characteristic line;

transforming the basis signature to approximate a repetition of the visual pattern along the central line; and

assembling a characteristic line model representing the characteristic line, the characteristic line model comprising the central line, the basis signature and information representative of the transformation of the basis signature.

20. The image representation method of claim 19, further comprising:

identifying as a candidate central line the central line of the re-scaled image;

determining a characteristic strip associated with the candidate central line, the characteristic strip comprising portions of the image adjacent to the candidate central line;

detecting a plurality of image patterns within the characteristic strip;

determining whether each of the plurality of image patterns within the characteristic strip repeats along the central line;

if the plurality of image patterns within the characteristic strip does not repeat along the central line, then discarding the candidate central line as not corresponding to a characteristic line;

if the plurality of image patterns within the characteristic strip does repeat along the central line, then separating each of the plurality of image patterns, identifying a signature and determining a geometric transformation that fits the signature to the repetitions of the pattern along the candidate central line; and

approximating a signature and a fitting sequence corresponding to the candidate central line.

21. A method for representation of an image, comprising:

identifying at least one central line approximating a shape of a characteristic line;

subdividing the central line into a plurality of subpieces, each having a predetermined length;

identifying a plurality of pixels located within a characteristic strip corresponding to each of the plurality of subpieces, and defining each of the plurality of pixels at least according to a distance from the central line and a brightness parameter; and

deriving a cross-section at each of the plurality of subpieces based on the defined pixels.

22. The method of claim 21 for representation of an image, further comprising:

forming a quadratic difference between each derived cross-section and the cross-section derived from the next one of the plurality of subpieces;

minimizing the quadratic differences with respect to the parameters of a fitting transformation;

identifying a minimized fitting transformation of each derived cross-section and the cross-section derived from the next one of the plurality of subpieces;

composing a plurality of fitting transformations from the plurality of minimized fitting transformations and interpolating each of the plurality of fitting transformations along the corresponding line segment;

deriving a fitting path from the interpolated fitting transformations;

redefining each of the plurality of pixels according to a distance from the central line corrected according to the fitting path and one of a brightness or a color parameter corrected according to the fitting path; and

deriving a corrected cross-section at each of the plurality of subpieces based on the redefined pixels.

23. The image representation method of claim 22, further comprising:

identifying a geometrically central point of the corrected cross-section; and

applying the fitting path to the central point to derive a corrected central line.

24. A method for representation of an image, comprising:

identifying an empirical cross-section of at least one point of a line on the image;

determining whether the line approximates a shape of a uniform characteristic line; and

if the line does approximate the shape of a uniform characteristic line, then identifying a fitting path, a corrected cross-section and a central line of the uniform characteristic line.

25. A computing apparatus for implementing representation of a digital image, comprising:

a computing device for executing computer readable code;

an input device for receiving the digital image and interfacing with a user, said input device being in communication with said computing device;

at least one data storage device for storing computer data, said at least one data storage device being in communication with said computing device; and

a programming code reading device that reads computer executable code, said programming code reading device being in communication with said computing device;

wherein the computer executable code instructs the computing device to identify at least one characteristic line of the image based on a global image pattern, each characteristic line comprising a line along which a visual pattern repeats itself;

to determine a central line corresponding to the characteristic line, the central line approximating a shape of the characteristic line and comprising a plurality of points;

to determine a cross-section at each of the plurality of points along the central line, the cross-section comprising at least one geometric parameter and at least one brightness parameter;

to determine a basis cross-section representative of the characteristic line; and

to transform the basis cross-section to the cross-sections of the plurality of points along the central line; and

wherein the computer executable code stores data representing the characteristic line, the central line, the cross-section and the transforms of the cross-section in said at least one data storage device.

26. The computing apparatus of claim 25, wherein at least one of the characteristic line of the image and the central line corresponding to the characteristic line is identified by the user via said input device.

27. A computing apparatus for implementing representation of an image, comprising:

a computing device for executing computer readable code;

an input device for receiving the image and interfacing with a user, said input device being in communication with said computing device;

at least one data storage device for storing computer data, said data storage device being in communication with said computing device; and

a programming code reading device that reads computer executable code, said programming code reading device being in communication with said computing device;

wherein, the computer executable code instructs the computing device to identify at least one characteristic line of the image based on a global image pattern, each characteristic line comprising a line along which a visual pattern repeats itself;

to determine a central line corresponding to the characteristic line, the central line approximating a shape of the characteristic line;

identify a plurality of patterns along the central line;

to determine a basis signature representative of the characteristic line; and

to transform the basis signature to approximate a repetition of the visual pattern along the central line; and

wherein the computer executable code stores data representing at least one of the characteristic line, the central line, the patterns, the basis signature, and the transforms of the cross-section in said at least one data storage device.

28. The computing apparatus of claim 27, wherein at least one of the characteristic line of the image, the central line corresponding to the characteristic line and the visual pattern is identified by the user via said input device.

29. A computing apparatus for implementing representation of an image, comprising:

an image reading device for reading and storing the image;

an interface device for enabling a user interface;

a program module that receives and executes computer readable code; and

a model storage device that stores characteristic line model data representing the image;

wherein said program module detects at least one of a plurality of edges and a plurality of ridges on the image, based on a global image pattern, stored in said image reading device;

detects adjacencies among each of the plurality of edges and the plurality of ridges;

interprets common adjacencies as characteristic lines;

determines a central line corresponding to each of the characteristic lines, the central line approximating a shape of the characteristic line and comprising a plurality of points; and

detects a plurality of cross-sections corresponding to the plurality of points along the central line, each of the plurality of cross-sections comprising at least one geometric parameter and at least one brightness parameter.

30. The apparatus of claim 29 for representation of an image, wherein said program module further subdivides each of the plurality of edges and the plurality of ridges into a corresponding plurality of spline segments;

evaluates each of the plurality of spline segments and identifies adjacent spline segments; and

identifies at least one adjacency interval on each of a plurality of edge components corresponding to each of the plurality of edges.

31. A computing apparatus for implementing representation of an image, comprising:

an image reading device for reading and storing the image;

an interface device for enabling a user interface;

a program module that receives and executes computer readable code; and

a model storage device that stores characteristic line model data representing the image;

wherein said program module detects a plurality of edges on the image;

subdivides each of the plurality of edges into a corresponding plurality of spline segments;

evaluates each of the plurality of spline segments and identifies adjacent spline segments;

connects, with an adjacency pointer, a midpoint of the evaluated spline segment with a midpoint of each of the corresponding adjacent spline segments, creating a plurality of adjacency couples;

identifies adjacency intervals as continuous chains of adjacent couples;

identifies a central point of each adjacency pointer within each adjacency couple;

joins the central points of each adjacency pointer within each adjacency interval, forming a central line corresponding to a characteristic line, the central line comprising a plurality of points;

detects a plurality of cross-sections corresponding to the plurality of points along the central line, each of the plurality of cross-sections comprising at least one geometric parameter and at least one brightness parameter;

determines a basis cross-section representative of the characteristic line;

determines a fitting path corresponding to the plurality of cross-sections, the fitting path comprising a transformation of the basis cross-section to the cross-sections of the plurality of points along the central line; and

assembles a characteristic line model representing the characteristic line, the characteristic line model comprising data representing the central line, the basis cross-section and the fitting path; and

wherein the program module stores data representing at least one of the characteristic line, the characteristic line model, the central line, the basis cross-section, and the fitting path in said at least one data storage device.

32. A computing apparatus for implementing representation of an image, comprising:

a computing device for executing computer readable code;

an input device for receiving the digital image and interfacing with a user, said input device being in communication with said computing device;

at least one data storage device for storing computer data, said data storage device being in communication with said computing device; and

a programming code reading device that reads computer executable code, said programming code reading device being in communication with said computing device;

wherein the computer executable code causes the computing device to reduce the image from an original size;

to identify at least one characteristic line of the reduced image, each characteristic line comprising a line along which a visual pattern repeats itself;

to re-scale the reduced image to the original size;

to determine for the re-scaled image a central line corresponding to the characteristic line, the central line approximating a shape of the characteristic line and comprising a plurality of points;

to identify a plurality of patterns along the central line;

to determine a basis signature representative of the characteristic line; and

transform the basis signature to approximate a repetition of the visual pattern along the central line; and

wherein the computer executable code stores data representing at least one of the characteristic line, the central line, the patterns, the basis signature, and the transforms of the cross-section in said at least one data storage device.

33. A computing apparatus for implementing representation of an image, comprising:

an image reading device for reading and storing the image;

an interface device for enabling a user interface;

a program module that receives and executes computer readable code; and

a model storage device that stores characteristic line model data representing the image;

wherein said program module identifies an empirical cross-section of at least one point of a line on the image;

determines whether the line approximates a shape of a uniform characteristic line; and

, if the line does approximate the shape of a uniform characteristic line, then identifies a fitting path, a corrected cross-section and a central line of the uniform characteristic line; and

wherein the program module stores data representing at least one of the uniform characteristic line, the central line, the fitting path, the empirical cross-section and the corrected cross-section in said at least one data storage device.

34. A computing apparatus for implementing representation of an image, comprising:

a computing device for executing computer readable code;

an input device for receiving the image and interfacing with a user, said input device being in communication with said computing device;

at least one data storage device for storing computer data, said data storage device being in communication with said computing device; and

a programming code reading device that reads computer executable code, said programming code reading device being in communication with said computing device;

wherein the computer executable code causes the computing device to identify at least one central line approximating a shape of a characteristic line;

to subdivide the central line into a plurality of subpieces, each having a predetermined length;

to identify a plurality of pixels located within a characteristic strip corresponding to each of the plurality of subpieces and define each of the plurality of pixels at least according to a distance from the central line and a brightness parameter;

to derive a cross-section at each of the plurality of subpieces based on the defined pixels;

to form a quadratic difference between each derived cross-section and the cross-section derived from the next one of the plurality of subpieces;

to minimize the quadratic differences with respect to the parameters of a fitting transformation;

to identify a minimized fitting transformation of each derived cross-section and the cross-section derived from the next one of the plurality of subpieces;

to compose a plurality of fitting transformations from the plurality of minimized fitting transformations and interpolate each of the plurality of fitting transformations along the corresponding line segment;

to derive a fitting path from the interpolated fitting transformations;

redefine each of the plurality of pixels according to a distance from the central line corrected according to the fitting path and one of a brightness and a color parameter corrected according to the fitting path;

to derive a corrected cross-section at each of the plurality of subpieces based on the redefined pixels;

to identify a geometrically central point of the corrected cross-section; and

to apply the fitting path to the central point to derive a corrected central line; and

wherein the computer executable code stores data representing at least one of the characteristic line, the central line, the plurality of fitting transformations, the fitting path, the derived cross-section and the corrected cross-section in said at least one data storage device.