System for extracting shape features from an image
First Claim
1. Method for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising the steps of:
- A. scanning said array along said rows in a single pass and detecting and identifying edges of objects in a succession of contiguous pairs of adjacent rows of said image, generating edge signals representative thereof, andB. processing said edge signals to identify segmentation features as a current line is scanned for each identified edge by identifying a portion of the boundary of the object associated with that identified edge as a primitive segment.
0 Assignments
0 Petitions
Accused Products
Abstract
A system for sequentially processing an image in order to identify objects in the image, and extract a variety of shape features of the identified objects. The system includes an image preprocessor, a controller, an object boundary resolver and identifier and a feature extractor. The image preprocessor scans the image and generates digital scan line signals wherein each bit is representative of a detected characteristic of an elemental region associated with a current scan position in the image. The object boundary resolver and identifier identifies object edge points from the digital scan line signals and maintains edge point data records representative of the position of the edge points in the two most recent scan lines. The resolver and identifier further processes the edge point data to identify continuation, creation, termination and merge conditions for the various objects within the image. For each of the identified objects, the feature extractor determines the presence of various shape features for the identified objects. These features include object count, perimeter (P), area (A), P2 /A, moments, neck features and segmentation features. All the features identified by the feature extractor are extracted in a single pass, sequential processing of the image.
244 Citations
116 Claims
-
1. Method for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising the steps of:
-
A. scanning said array along said rows in a single pass and detecting and identifying edges of objects in a succession of contiguous pairs of adjacent rows of said image, generating edge signals representative thereof, and B. processing said edge signals to identify segmentation features as a current line is scanned for each identified edge by identifying a portion of the boundary of the object associated with that identified edge as a primitive segment. - View Dependent Claims (2)
-
-
3. Method for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising the steps of:
-
A. detecting and identifying boundaries of objects in a succession of contiguous pairs of adjacent rows of said image and generating boundary signals representative thereof, B. processing said boundary signals to generate and store boundary data for each of the most recent pair of rows in said succession, said boundary data including; dta representative of the position and type of edges of objects intercepted by said most recent pair of rows, said type being left, right, top or bottom, C. generating and updating for each pair of rows, top view data from said boundary data, said top view data being representative of the cell position in said image and type of the left, right, top or bottom edge of an object which is both nearest to the respective cells in the most recent row of said succession and which is located at the same point along a previous row as the respective cells. - View Dependent Claims (4)
-
-
5. Method for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising the steps of:
-
A. scanning said image in a single pass along a succession of substantially parallel lines of scan, B. detecting the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, and generating scan signals representative thereof, C. processing said scan signals to identify left edges of objects in each scan line as said lines are scanned, and concurrently generating a left edge signal for each identified left edge, said left edge signal being representative of the position of said identified left edge along said current scan line, D. processing said scan signals to identify right edges of objects in each scan line as said lines are scanned, and concurrently generating a right edge signal for each identified right edge, said right edge signal being representative of the position of said identified right edge in said current scan line, E. storing current scan line data, said current scan line data including left and right edge signals generated as a current line is scanned, and storing previous scan line data, said previous scan line data including left and right edge signals generated during the scan of the next previous line, F. identifying objects by comparing each stored left and right edge signal of said current scan line data with said left and right edge signals of said stored previous scan line data, and including the substeps of; i. identifying a new object in said current scan line, ii. identifying an object left boundary which continues from said next previous scan line to the current scan line, iii. identifying an object right boundary which continues from said next previous scan line to said current scan line, iv. identifying an object which has terminated between said next previous and said current scan lines, v. identifying an object which has merged with another object between said next previous and current scan lines. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. Method for extracting features of one or more body objects against a background in a two dimensional image, said body objects having boundaries and being characterized within said boundaries by a value of a detectable characteristic in a first predetermined range, and said background being characterized by a value of said characteristic in a second predetermined range, and said image having a border characterized by a value of said characteristic in said first range, comprising the steps of:
-
A. scanning said image in a single pass, along a succession of N substantially parallel lines of scan, where N is an integer, B. detecting the value of said characteristic of M contiguous regions of said image along each of said scan lines, and generating scan signals representative thereof, where M is an integer, C. processing said scan signals to identify left edge regions in each scan line as said lines are scanned, each of said left edge regions being the first region along said scan line which is characterized by a value of said characteristic in said first range and which follows a region characterized by a value of said characteristic in said second range, and concurrently generating a left edge signal XL.sbsb.i (k) for each identified left edge region, said left edge signal being representative of the scan line k currently being scanned and in which said left edge region is identified, where k is an integer and 1≦
k<
N, and being further representative of the displacement XL from the left boundary of said image and the sequential position i of said left edge region along said current scan line, where i is an integer and 1≦
i≦
M/2,D. processing said scan signals to identify right edge regions in each scan line as said lines are scanned, each of said right edge regions being the first region along said scan line which is characterized by a value of said characteristic in said second range, and which follows a region characterized by a value of said characteristic in said first range, and concurrently generating a right edge signal XR.sbsb.i (k) for each identified right edge region, said right edge signal being representative of the scan line k currently being scanned and in which said right edge region is identified, and being further representative of the displacement XR from the left edge of said image and the sequential position i of said pair in said current scan line, E. storing as generated said current (kth) line left and right edge signals, XL.sbsb.1 (k), XL.sbsb.2 (k), . . ., XL.sbsb.i (k), . . . and XR.sbsb.1 (k), XR.sbsb.2 (k), . . ., XR.sbsb.i (k), . . . and following the detection of the Mth region in said kth scan line, storing said kth line left and right edge signals as the next previous (k-1th) line left and right edge signals, XL.sbsb.1 (k-1), XL.sbsb.2 (k-1), . . ., XLj (k-1), . . ., and XR.sbsb.1 (k-1), XR.sbsb.2 (k-1), . . ., XR.sbsb.j (k-1), . . ., where j is an integer and is representative of the sequential position of one of said edge signals in said k-1th line, and 1≦
j≦
M/2,F. identifying objects as said kth line is scanned by comparing each stored kth line left and right edge signal with said stored kth line left and right edge signals, and generating and storing an object number signal in said memory in association with each kth line left and right edge signal, including the substeps of; i. identifying a new body object having a left boundary at XL.sbsb.i+1 (k) when
space="preserve" listing-type="equation">X.sub.R.sbsb.i+1 (k)<
X.sub.L.sbsb.j+1 (k-1)unless
space="preserve" listing-type="equation">X.sub.R.sbsb.i-1 (k)<
X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)
space="preserve" listing-type="equation">X.sub.R.sbsb.j-1 (k-1)<
X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1),and a right boundary at XR.sbsb.i+1 (k), and generating a unique object number signal for each identified new body object and storing said object number signal in said memory in association with XL.sbsb.i+1 (k) and XR.sbsb.i+1 (k), ii. identifying a new hole object having a left boundary at XR.sbsb.i (k) when
space="preserve" listing-type="equation">X.sub.L.sbsb.i+1 (k)<
X.sub.R.sbsb.j (k-1),unless
space="preserve" listing-type="equation">X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i+1 (k)
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)<
X.sub.L.sbsb.j+1 (k-1),and a right boundary at XL.sbsb.i+1 (k), and generating a unique object number signal for each identified new hole object and storing said object number signal in said memory in association with XL.sbsb.i+1 (k) and XR.sbsb.i (k), iii. identifying an object boundary which continues from XL.sbsb.j (k-1) to XL.sbsb.i (k) when
space="preserve" listing-type="equation">X.sub.R.sbsb.i-1 (k)<
X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)
space="preserve" listing-type="equation">X.sub.R.sbsb.j-1 (k-1)<
X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1)and generating the same object number signal stored in association with XL.sbsb.j (k-1) for each identified continued object left boundary and storing said same object number signal in said memory in association with XL.sbsb.i (k), iv. identifying an object boundary which continues from XR.sbsb.j (k-1) to XR.sbsb.i (k) when
space="preserve" listing-type="equation">X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1)<
X.sub.L.sub.i+1 (k)
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)<
X.sub.L.sbsb.j+1 (k-1)and generating the same object number signal stored in association with XR.sbsb.j (k-1) for each identified continued object right boundary and storing said same object number signal in said memory in association with XR.sbsb.i (k), v. identifying a terminated body object when an object boundary at XL.sbsb.j (k-1) is not continued at XL.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i (k)and the object number signals stored in association with XL.sbsb.j (k-1) and XR.sbsb.j (k-1) are identical, vi. identifying a terminated hole object when an object boundary at XR.sbsb.j-1 (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signals stored in association with XR.sbsb.j-1 (k-1) and XL.sbsb.j (k-1) are identical, vii. identifying merged body objects when an object boundary at XR.sbsb.j-1 (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signals stored in association with XR.sbsb.j-1 (k-1) and XL.sbsb.j (k-1) are representative of different body objects, viii. identifying merged hole objects when an object boundary at XL.sbsb.j (k-1) is not continued at XL.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i (k)and the object number signals stored in association with XL.sbsb.j (k-1) and XR.sbsb.j (k-1) are representative of different hole objects, ix. identifying a hole object which merges with a body object when; a. an object boundary at XL.sbsb.j+1 (k-1) is not continued at XL.sbsb.i+1 (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j+1 (k-1)<
X.sub.L.sbsb.i+1 (k)and the object number signals stored in association with XL.sbsb.j+1 (k-1) is representative of a hole object and the object number signal stored in association with XR.sbsb.j+1 (k-1) is representative of a body object, or b. an object boundary at XL.sbsb.j (k-1) is not continued at XL.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i (k)and the object number signals stored in association with XL.sbsb.j (k-1) is representative of a body object and the object number signal stored in association with XR.sbsb.j (k-1) is representative of a hole object, x. identifying a body object which merges with a hole object when; a. an object left boundary at XR.sbsb.j (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signal stored in association with XR.sbsb.j (k-1) is representative of a body object and the object number signal stored in association with XL.sbsb.j+1 (k-1) is representative of a hole object, or b. an object boundary at XR.sbsb.j-1 (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signals stored in association with XR.sbsb.j-1 (k-1) is representative of a hole object and the object number signal stored in association with XL.sbsb.j (k) is representative of a body object. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. Method for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising the steps of:
-
scanning said image in a single pass along a succession of substantially parallel lines of scan, detecting the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, and generating scan signals representative thereof, processing said scan signals to identify said features of said objects as said image is scanned during said single pass, wherein said feature identifying step includes the stp of identifying neck features in said objects during said single scan.
-
-
33. Method for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising the steps of:
-
scanning said image in a single pass along a succession of substantially parallel lines of scan, detecting the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, and generating scan signals represenatative thereof, processing said scan signals to identify said features of said objects as said image is scanned during said single pass, whereihn said feature identifying step includes the step of identifying segmentation features during said single scan.
-
-
34. Method for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising the steps of:
-
scanning said image in a single pass along a succession of substantially parallel lines of scan. detecting the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, and generating scan signals representative thereof, processing said scan signals to identify said features of said objects as said image is scanned during said single pass, wherein said feature identifying step comprises the further step of; C. storing current scan line data, said current scan line data being representative of the detected values of said characteristic for the succession of contiguous regions of a current line being scanned, and storing previous scan line data, said previous scan line data being representative of the detected values of said characteristic for the succession of contiguous regions of the next previously scanned line.
-
-
35. Method for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising the steps of:
-
scanning said image in a single pass along a succession of substantially parallel lines of scan, detecting the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, and generating scan signal representative thereof, processing said scan signals to identify said features of said objects as said image is scanned during said single pass. wherein said feature identifying step comprises; A. identifying left edges of objects in each scan line as said lines are scanned, and concurrently generating a left edge signal for each identified left edge, said left edge signal being representative of the position of said identified left edge along said current scan line, identifying right edges of objects in each scan line as said lines are scanned, and concurrently generating a right edge signal for each identified right edge, said right edge signal being representative of the position of said identified right edge in said current scan line, C. storing current scan line data, said current scan line data including left and right edge signals generated as a current line is scanned, and storing previous scan line data, said previous scan line data including left and right edge signals generating during the scan of the next previous line. - View Dependent Claims (36)
-
-
37. System for extracting features of one or more objects against a background in a two dimensional image, said objects having boundaries and being characterized within said boundaries by a value of a detectable characteristic in a first predetermined range, and said background being characterized by a value of said characteristic in a second predetermined range, comprising:
-
A. means to scan said image in a single pass along a succession of substantially parallel lines, B. means to detect and identify edges of objects intercepted by said scan, C. segmentation feature identifying means operative as a current line is scanned for each identified edge to identify a portion of the boundary of the object associated with that identified edge as a primitive segment. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45, 46)
-
-
47. System for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising:
-
A. means to scan said array along said rows in a single pass, and to detect and identify edges of objects in a succession of contiguous pairs of adjacent rows of said image, and B. segmentation feature identifying means operative as a current line is scanned for each identified edge to identify a portion of the boundary of the object associated with that identified edge as a primitive segment. - View Dependent Claims (48, 49, 50, 51, 52, 53, 54, 55, 56)
-
-
57. System for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising:
-
A. scanning means for scanning said image in a single pass along a succession of substantially parallel lines of scan. B. detection means operative in conjunction with said scanning means to detect the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, C. left edge identification means responsive to said detection means to identify left edges of objects in each scan line as said lines are scanned, and to concurrently generate a left edge signal for each identified left edge, said left edge signal being representative of the position of said identified left edge along said current scan line, D. right edge identification means responsive to said detection means to identify right edges of objects in each scan line as said lines are scanned, and to concurrently generate a right edge signal for each identified right edge, said right edge signal being representative of the position of said identified right edge in said current scan line, E. memory means for storing current scan line data, said current scan line data including left and right edge signals generated as a current line is scanned, and for storing previous scan line data, said previous scan line data including left and right edge signals generated during the scan of the next previous line, F. object identification means operative in conjunction with said memory means to compare each stored left and right edge signal of said current scan line data with said left and right edge signals of said stored previous scan line data, and including; i. means to identify a new object in said current scan line, ii. means to identify an object left boundary which continues from said next previous scan line to the current scan line, iii. means to identify an object right boundary which continues from said next previous scan line to said current scan line, iv. means to identify an object which has terminated between said next previous and said current scan lines, v. means to identify an object which has merged with another object between said next previous and current scan lines. - View Dependent Claims (58, 59, 60, 61, 62)
-
-
63. System for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising:
-
scanning means for scanning said image in a single pass along a succession of substantially parallel lines of scan, detection means operative in conjunction with said scanning means to detect the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, feature extraction means operative as said image is scanned to identify said features of said objects during said single pass, wherein said feature extraction means includes means to identify neck features in said objects during said single scan.
-
-
64. System for extracting features of one or more objects in a two diemnsional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising:
-
scanning means for scanning said image in a single pass along a succession of substantially parallel lines of scan, detection means operative in conjunction with said scanning means to detect the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, feature extraction means operative as said image is scanned to identify said features of said objects during said single pass, wherein said feature extraction means includes means to identify segmentation features during said single scan.
-
-
65. System for extracting features of one or more objects in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising:
-
scanning means for scanning said image in a single pass along a succession of substantially parallel lines of scan, detection means operative in conjunction with said scanning means to detect the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, feature extraction means operative as said image is scanned to identify said features of said objects during said single pass, wherein said feature extraction means further comprises; C. memory means for storing current scan line data, said current scan line data being representative of the detected values of said characteristic for the succession of contiguous regions of a current scan line being scanned, and for storing previous scan line data, said previous scan line data being representative of the detected values of said characteristic for the succession of contiguous regions of the next previous scanned line.
-
-
66. System for extracting features of one or more objects in a two diemnsional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in one of r predetermined ranges, where r is an integer, comprising:
-
scanning means for scanning said image in a single pass along a succession of substantially parallel lines of scan, detection means operative in conjunction with said scanning means to detect the value of said characteristic of a succession of contiguous regions of said image along each of said scan lines, feature extraction means operative as said image is scanned to identify said features of said objects during said single pass, wherein said feature extraction means comprises; A. left edge identification means responsive to said detection means to identify left edges of objects in each scan line as said lines are scanned, and to concurrently generate a left edge signal for each identified left edge, said left edge signal being representative of the position of said identified left edge along said current scan line, B. right edge identification means responsive to said detection means to identify right edges of objects in each scan line as said lines are scanned, and to concurrently generate a right edge signal for each identified right edge, said right edge signal being representative of the position of said identified right edge in said current scan line, C. memory means for storing current scan line data, said current scan line data including left and right edge signals generated as a current line is scanned, and for storing previous scan line data, said previous scan line data including left and right edge signals generated during the scan of the next previous line. - View Dependent Claims (67)
-
-
68. system for extracting features of one or more objects against a background in a two dimensional image, each of said objects having a boundary and being characterized within said boundary by a value of a detectable characteristic in a first predetermined range, and said background being characterized by a value of said characteristic in a second predetermined range, comrpising:
-
A. scanning means for scanning said image in a single pass along a succession of substantially parallel lines of scan, B. detection means operative in conjunction with said scanning means to detect the value of said characteristic of a successon of contiguous regions of said image along each of said scan lines, C. left edge identification means responsive to said detection means to identify left edges of objects in each scan line as said lines are scanned, and to concurrently generate a left edge signal for each identified left edge, said left edge signal being representative of the position of said identified left edge along said current scan line, D. right edge identification means responsive to said detection means to identify right edges of objects in each scan line as said lines are scanned, and to concurrently generate a right edge signal for each identified right edge, said right edge signal being representative of the position of said identified right edge in said current scan line, E. memory means for storing current scan line data, said current scan line data including left and right edge signals generated as a current line is scanned, and for storing previous scan line data, said previous scan line data including left and right edge signals generated during the scan of the next previous line, F. object identification means operative in conjunction with said memory means to compare each stored left and right edge signal of said current scan line data with said left and right edge signals of said stored previous scan line data, and including; i. means to identify a new body object in said current scan line, ii. means to identify a new hole object in said current scan line, iii. means to identify an object left boundary which continues from said next previous scan line to the current scan line, iv. means to identify an object right boundary which continues from said next previous scan line to said current scan line, v. means to identify a body object which has terminated between said next previous and said current scan lines, vi. means to identify a hole object which has terminated between said next previous and current scan lines, vii. means to idenfity an object which has merged with another object between said next previous and current scan lines. - View Dependent Claims (69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89)
-
-
90. System for extracting features of one or more body objects against a background in a two dimensional image, said body objects having boundaries and being characterized within said boundaries by a value of a detectable characteristic in a first predetermined range, and said background being characterized by a value of said characteristic in a second predetermined range, and said image having a border characterized by a value of said characteristic in said first range, comprising:
-
A. scanning means for scanning said image in a single pass along a succession of N substantially parallel lines of scan, where N is an integer, B. detection means operative in conjunction with said scanning means to detect the value of said characteristic of M contiguous regions of said image along each of said scan lines, where M is an integer, C. left edge identification means responsive to said detection means to identify left edge regions in each scan line as said lines are scanned, each of said left edge regions being the first region along said scan line which is characterized by a value of said characteristic in said first range and which follows a region characterized by a value of said characteristic in said second range, and to concurrently generate a left edge signal XL.sbsb.i (k) for each identified left edge region, said left edge signal being representative of the scan line k currently being scanned and in which said left edge region is identified, where k is an integer and 1≦
k≦
N, and being further representative of the displacement XL from the left boundary of said image and the sequential position i of said left edge region along said current scan line, where i is an integer and 1≦
i≦
M/2,D. right edge is identification means responsive to said detection means to identify right edge regions in each scan line as said lines are scanned, each of said right edge regions being the first region along said scan line which is characterized by a value of said characteristic in said second range, and which follows a region characterized by a value of said characteristic in said first range, and to concurrently generate a right edge signal XR.sbsb.i (k) for each identified right edge region, said right edge signal being representative of the scan line k currently being scanned and in which said right edge region is identified, and being further representative of the displacement XR from the left edge of said image and the sequential position i of said pair in said current scan line, E. memory means for storing as generated said current (kth) line left and right edge signals, XL.sbsb.1 (k), XL.sbsb.2 (k), . . ., XL.sbsb.i (k), . . . and XR.sbsb.1 (k), XR.sbsb.2 (k), . . ., XR.sbsb.i (k), . . ., and means operative following the detection of the Mth region in said kth scan line for storing said kth line left and right edge signals as the next previous (k-1th) line left and right edge signals, XL.sbsb.1 (k-1), XL.sbsb.2 (k-1), . . ., XL.sbsb.j (k-1), . . ., and XR.sbsb.1 (k-1), XR.sbsb.2 (k-1), . . ., XR.sbsb.j (k-1), . . ., where j is an integer and is representative of the sequential position of one of said edge signals in said k-1th line, and 1≦
j≦
M/2,F. object identification means operative as said kth line is scanned and in conjunction with said memory means to compare each stored kth line left and right edge signal with said stored k-1th line left and right edge signals, and to generate and store an object number signal in said memory in association with each kth line left and right edge signal, including; i. means to identify a new body object having a left boundary at XL.sbsb.i+1 (k) when
space="preserve" listing-type="equation">X.sub.R.sbsb.i+1 (k)<
X.sub.L.sbsb.j+1 (k-1)unless
space="preserve" listing-type="equation">X.sub.R.sbsb.i-1 (k)<
X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)
space="preserve" listing-type="equation">X.sub.R.sbsb.j-1 (k-1)<
X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1),and a right boundary at XR.sbsb.i+1 (k), and further including means to generate a unique object number signal for each identified new body object and to store said object number signal in said memory in association with XL.sbsb.i+1 (k) and XR.sbsb.i+1 (k), ii. means to identify a new hole object having a left boundary at XR.sbsb.i (k) when
space="preserve" listing-type="equation">X.sub.L.sbsb.i+1 (k)<
X.sub.R.sbsb.j (k-1),unless
space="preserve" listing-type="equation">X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i+1 (k)
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)<
X.sub.L.sbsb.j+1 (k-1),and a right boundary at XL.sbsb.i+1 (k), and further including means to generate a unique object number signal for each identified new hole object and means to store said object number signal in said memory in association with XL.sbsb.i+1 (k) and XR.sbsb.i (k), iii. means to identify an object boundary which continues from XL.sbsb.j (k-1) to XL.sbsb.i (k) when
space="preserve" listing-type="equation">X.sub.R.sbsb.i-1 (k)<
X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)
space="preserve" listing-type="equation">X.sub.R.sbsb.j-1 (k-1)<
X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1)and means to generate the same object number signal stored in association with XL.sbsb.j (k-1) for each identified continued object left boundary and means to store said same object number signal in said memory in association with XL.sbsb.i (k), iv. means to identify an object boundary which continues from XR.sbsb.j (k-1) to XR.sbsb.i (k) when
space="preserve" listing-type="equation">X.sub.L.sbsb.i (k)<
X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i+1 (k)
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)<
X.sub.L.sbsb.j+1 (k-1)and means to generate the same object number signal stored in association with XR.sbsb.j (k-1) for each identified continued object right boundary and means to store said same object number signal in said memory in association with XR.sbsb.i (k), v. means to identify a terminated body object when an object boundary at XL.sbsb.j (k-1) is not continued at XL.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i (k)and the object number signals stored in association with XL.sbsb.j (k-1) and XR.sbsb.j (k-1) are identical, vi. means to identify a terminated hole object when an object boundary at XR.sbsb.j-1 (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signals stored in association with XR.sbsb.j-1 (k-1) and XL.sbsb.j (k-1) are identical, vii. means to identify merged body objects when an object boundary at XR.sbsb.j-1 (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signals stored in association with XR.sbsb.j-1 (k-1) and XL.sbsb.j (k-1) are representative of different body objects, viii. means to identify merged hole objects when an object boundary at XL.sbsb.j (k-1) is not continued at XL.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i (k)and the object number signals stored in association with XL.sbsb.j (k-1) and XR.sbsb.j (k-1) are representative of different hole objects, ix. means to identify a hole object which merges with a body object when; a. an object boundary at XL.sbsb.j+1 (k-1) is not continued at XL.sbsb.i+1 (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j+i (k-1)<
X.sub.L.sbsb.i+1 (k)and the object number signals stored in association with XL.sbsb.j+1 (k-1) is representative of a hole object and the object number signal stored in association with XR.sbsb.j+1 (k-1) is representative of a body object, or b. an object boundary at XL.sbsb.j (k-1) is not continued at XL.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.R.sbsb.j (k-1)<
X.sub.L.sbsb.i (k)and the object number signals stored in association with XL.sbsb.j (k-1) is representative of a body object and the object number signal stored in association with XR.sbsb.j (k-1) is representative of a hole object, x. means to identify a body object which merges with a hole object when; a. an object left boundary at XR.sbsb.j (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signal stored in association with XR.sbsb.j (k-1) is representative of a body object and the object number signal stored in association with XL.sbsb.j+1 (k-1) is representative of a hole object, or b. an object boundary at XR.sbsb.j-1 (k-1) is not continued at XR.sbsb.i (k) and
space="preserve" listing-type="equation">X.sub.L.sbsb.j (k-1)<
X.sub.R.sbsb.i (k)and the object number signals stored in association with XR.sbsb.j-1 (k-1) is representative of a hole object and the object number signal stored in association with XL.sbsb.j (k) is representative of a body object. - View Dependent Claims (91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104)
-
-
105. System for extracting features of one or more objects against a background in a two dimensional image, said objects having boundaries and being characterized within said boundaries by a value of a detectable characteristic in a first predetermined range, and said background being characterized by a value of said characteristic in a second predetermined range, comprising:
-
A. means to scan said image in a single pass along a succession of substantially parallel lines, B. means to detect and identify boundaries of objects intercepted by said scan, C. means to generate and store boundary data for each of the two most recent lines of scan, said boundary data including; data representative of the position and type of edges of objects intercepted by said scan in said two most recent lines, said type being left, right, top or bottom, D. means to generate, and to update during each scan, top view data from said boundary data, said top view data being representative of the position in said image and type of the left, right, top or bottom edge of an object which is nearest to the current point of scan and which is located at the same point along a previous scan line as the current point of scan. - View Dependent Claims (106)
-
-
107. System for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising:
-
A. means to detect and identify boundaries of objects in a succession of contiguous pairs of adjacent rows of said image, B. means to generate and store boundary data for each of the most recent pairs of rows in said succession, said boundary data including; data representative of the position and type of edges of objects intercepted by said two most recent rows, said type being left, right, top, or bottom, C. means to generate, and to update for each pair of rows, top view data from said boundary data, said top view data being representative of the cell position in said image and type of the left, right, top or bottom edge of an object which is both nearest to the respective cells in the most recent row of said succession and which is located at the same point along a previous row as the respective cells. - View Dependent Claims (108)
-
-
109. System for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising:
-
A. means to detect and identify edges of objects in a succession of contiguous pairs of adjacent rows of said image, and B. segmentation feature identifying means operative as a current line is scanned for each identified edge to identify a portion of the boundary of the object associated with that identified edge as a primitive segment, wherein said segmentation feature identifying means includes; means to identify a new object in said current scan line, first means operative in a current scan line in which a new object is identified, to identify the portion of said new object boundary in said current line as a directed reference segment, second means operative in a current scan line following said line in which a new object is identified, to identify the portion of said new object which continues to said identified edge in said current line from a previously identified edge in the next previous line as a directed primitive segment, wherein said second means includes means operative in a current scan line for determining the angular orientation of a current line directed primitive segment extending between said identified edge in said current line and said previously identified edge with respect to said reference segment, and means for determining the difference between said angular orientation of said current line primitive segment and the corresponding angular orientation of the directed primitive segment of the next previous line which is bounded by said parviously identified edge, and means for identifying said current line primitive segment as a; i. convex segment when the difference in orientation is a first polarity ii. concave segment when the difference in orientation is a second polarity, and iii. straight line segment when the difference in orientation is zero. - View Dependent Claims (110)
-
-
111. System for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising:
-
A. means to detect and identify edges of objects in a succession of contiguous pairs of adjacent rows of said image, and B. segmentation feature identifying means operative as a current line is scanned for each identified edge to identify a portion of the boundary of the object associated with that identified edge as a primitive segment, wherein said segmentation feature identifying means includes; means to identify a new object in said current scan line, first means operative in a current scan line in which a new object is identified, to identify the portion of said new object boundary in said current line as a directed reference segment, second means operative in a current scan line following said line in which a new object is identified, to identify the portion of said new object which continues to said identified edge in said current line from a previously identified edge in the next previous line as a directed primitive segment, wherein said second means includes means operative in a current scan line for determining the angular orientation of a current line directed primitive segment extending between said identified edge in said current line and said previously identified edge with respect to said reference segment, and means for determining the difference between said angular orientation of said current line primitive segment and the cprresponding angular orientation of the directed primitive segment of the next previous line which is bounded by said previously identified edge, and means for identifying said current line primitive segment as a straight line segment. - View Dependent Claims (112)
-
-
113. System for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said background being characterized by cells of a second binary state, comprising:
-
A. means to detect and identify edges of objects in a succession of contiguous pairs of adjacent rows of said image, and B. segmentation feature identifying means operative as a current line is scanned by each identified edge to identify a portion of the boundary of the object associated with that identified edge as a primitive segment, wherein said segmentation feature identifying means includes; means to identify a new object in said current scan line, first means operative in a current scan line in which a new object is identified, to identify the portion of said new object boundary in said current line as a directed reference segment, second means operative in a current scan line following said line in which a new object is identified, to identify the portion of said new object which continues to said identified edge in said current line from a previously identified edge in the next previous line as a directed primitive segment, wherein said second means includes means operative in a current scan line for determining the angular orientation of a current line directed primitive segment extending between said identified edge in said current line and said previously identified edge with respect to said reference segment, and means for determining the difference between said angular orientation of said current line primitive segment and the corresponding angular orientation of the directed primitive segment of the next previous line which is bounded by said previously identified edge, and means for identifying said current line primitive segment as a; i. convex segment when the difference in orientation is a first polarity or zero, and ii. concave segment when the difference in orientation is a second polarity. - View Dependent Claims (114)
-
-
115. System for extracting features of one or more objects against a background in a digitized image forming a multiple cell array having M rows and N columns, said objects having boundaries and being characterized by cells of a first binary state, and said backgound being characterized by cells of a second binary state, comprising:
-
A. means to detect and identify edges of objects in a succession of contiguous pairs of adjacent rows of said image, and B. segmentation feature identifying means operative as a current line is scanned for each identified edge to identify a portion of the boundary of the object associated with that identified edge as a primitive segment, wherein said segmentation feature identifying means includes; means to identify a new object in said current scan line, first means operative in a current scan line in which a new object is identified, to identify the portion of said new object boundary in said current line as a directed reference segment, second means operative in a current scan line following said line in which a new object is identified, to identify the portion of said new object which continues to said identified edge in said current line from a previously identified edge in the next previous line as a directed primitive segment, wherein said second means includes means operative in a current scan line for determining the angular orientation of a current line directed primitive segment extending between said identified edge in said current line and said previously identified edge with respect to said reference segment, and means for determining the difference between said angular orientation of said current line primitive segment and the corresponding angular orientation of the directed primitive segment of the next previous line which is bounded by said previously identified edge, and means for identifying said current line primitive segment as a; i. convex segment when the difference in polarity is a first polarity, and ii. concave segment when the difference in polarity is a second polarity or zero. - View Dependent Claims (116)
-
Specification