Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
2000-01-24
2004-02-03
Boudreau, Leo (Department: 2621)
Image analysis
Pattern recognition
Feature extraction
C382S204000, C382S197000
Reexamination Certificate
active
06687403
ABSTRACT:
TECHNICAL FIELD
The invention generally relates to the field of image recognition.
BACKGROUND OF THE INVENTION
Image recognition is important in many fields, including automatic data collection, for example bar code reading. The ability to capture image data at higher resolutions leads to a need for faster processing of the captured image data.
SUMMARY OF THE INVENTION
Some aspects of the invention concern a process for detection of straight-line segments in a stream of digital data that are representative of an image having dimension (m, n) and size T=m×n, in which the contour points of said image each defined by the modulus and the orientation of their gradient in relation to a horizontal axis are identified. It extends to a device for detection of straight-line segments for implementing this detection process.
In one aspect, a process for detection of straight-line segments can permit processing of the digital data that are representative of a high-resolution image at a very elevated rate, supplying the start and end coordinates and the orientation of each of said straight-line segments.
Such a process is applied, in particular, for the detection of straight-line segments in a stream of digital data that are representative of images of codes in one and two dimensions which are formed on an electronic sensor such as a photosensitive matrix. To this end, the process may be implemented in a detection device which is integrated within a processing submodule forming an image acquisition and processing subassembly to process images of codes which are formed on a photosensitive matrix, such as described in the French patent application (French Serial No. 99.00717 filed on Jan. 22, 1999) filed in the name of the applicant, the processing submodule can employ cabled processing units comprising, upstream of said detection device:
a replicate-sampling circuit capable of reducing the size T of the image formed on the photosensitive matrix, for example by dividing said size T in accordance with the pyramidal method of BURT so as to obtain an image of reduced size T/4 and then T/16; and
a contour detection circuit to detect the contours in the reduced image emitted from the replicate-sampling circuit, adapted to supply images of said contours in which the contour points are defined by the modulus and the orientation of their gradient in relation to a horizontal axis, where the gradient represents the magnitude of the contrast between two points. These contour points are determined, for example, by calculating the gradients by application of the masks method of ROBERTS in the horizontal and vertical directions and by retaining as contour points the sole points for which the modulus of the gradient is greater than a predetermined threshold and maximal in the direction of said gradient which is defined by the argument of the latter, the other points being considered as not pertaining to a contour and being identified, for example, by a value such as −1 of the orientation of their gradient.
Another aspect of the invention provides, for each image, a histogram of the orientations of the various straight-line segments detected.
The process for detection of straight-line segments according to the invention can be characterized in that the stream of digital data is stored in the form of two successive lines, each of n points P(i, j), with 1≦i≦m and n≦7≦j, and for each of the lines the n points of said line are extracted successively, and for each point Pc(i, j) extracted, the so-called current point:
the three points having inferior coordinates Pa(i−1, j−1), Pb(i, j−1), Pd(i−1, j) directly neighbouring said current point are extracted,
successively the value of the orientation of the gradient of the current point Pc are compared with that of the neighbouring points Pa, Pb and Pd, and the values of the orientations of the gradients of the points Pb and Pd are compared,
the result of a comparison, representative of a connection between two points, is validated if said points are contour points and if the difference between the values of the orientation of their gradient is less than or equal to a predetermined value k,
when the result of a comparison is validated the coordinates of the point of the connection having inferior coordinates, the so-called start-point, are copied over to those of the point of said connection having superior coordinates, the so-called end-point, and the coordinates of the start-point are erased from the memory, unless said start-point has been identified as being an origin point of a straight-line segment.
it is verified whether solely the point Pa (i−1, j−1) is a contour point amongst the four points Pa, Pb, Pc, Pd extracted, and in the affirmative case the size of the straight-line segment for which said point Pa is the final point is calculated and the coordinates of the origin point and of the final point and the orientation of said straight-line segment, if its size is greater than a predetermined threshold, are saved.
This process therefore operates on the basis of line memories corresponding to successive lines of the image and permitting the whole of said image to be scanned from top to bottom, said memories on the one hand containing the result of the detection of contours, that is to say, for each point the value of the orientation of its gradient (equal to a given value if the point is a contour point and to −1 in the contrary case), and on the other hand serving to write the coordinates of the extremities, the origin point and final point, and the orientation of the straight-line segments.
Moreover, the obtaining of a series of straight-lines segments from a contour consists in following this contour from the “highest” point as far as the “lowest” point thereof and in deciding, firstly, for each point P(i, j) containing a contour, whether P pertains to a neighbouring segment S, itself constituted by one or more contour points. Then if P pertains to the segment S the final extremity of this segment takes as its coordinates those of P, that is to say (i, j), the origin extremity of said segment remaining unchanged and the coordinates of the possible intermediate points being erased. On the other hand, if P does not pertain to this segment it then defines the origin of a new segment, the two extremities of which are equal to (i, j), the size of which is equal to I and the orientation of which is &thgr;,P.
Such a detection process may permit processing at a higher rate—equivalent, for example, to the pixel frequency at which data that are representative of images are supplied by a photosensitive matrix—of the digital data that are representative of the contours of high-resolution images.
According to a particular embodiment which is directed towards the processing of horizontal or substantially horizontal straight-line segments:
at the time of the validation of a first connection between two neighbouring points P(i−1, j), P(i, j) pertaining to the same line, representative of an initial horizontal straight-line segment, the coordinates of the start-point of the connection are replaced by those of the- end-point of said connection, and conversely those of the end-point are replaced by those of the start-point.
then, for any point P(i+x,j) pertaining to said line, connected to the initial straight-line segment, the coordinates of said point are replaced by the initial coordinates (i−1, j) of the origin point of the initial horizontal straight-line segment and the coordinates of said origin point are replaced by those (i+x, j) of said point.
Moreover, and in advantageous manner, at the time of the validation of the connection between a point
P(i, j) with a point P(i−1, j−1) or P(i+1, j−1) validated as an extremity point, origin or final, of a horizontal straight-line segment, the coordinates of said point P(i, j) are transferred to those of the opposing extremity point, final or origin, of said straight-line segment, and those of said opposing extr
Akel Khalid El
Dumontier Christophe
Massieu Jean-Louis
Puech Jean-Michel
Reuze Patrick
Akhavannik Hussein
Boudreau Leo
Intermec IP Corp.
Seed IP Law Group PLLC
LandOfFree
Process and device for detection of straight-line segments... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process and device for detection of straight-line segments..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process and device for detection of straight-line segments... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3336913