Method and apparatus for extracting cluster shape features from digital images

Claim 1

An inspection and analysis system comprising: a sensing system for sensing features in an object and providing digital signals representative thereof; a programmed computer coupled to the sensing system, said computer being arranged to perform cluster analysis on data received from said sensing system, wherein said computer is programmed to employ an enhanced Hoshen-Kopelman with label reuse for identifying and labeling clusters concurrently for each of a plurality of data groups to detect and quantify cluster features in said data groups, and merge cluster shape feature properties for each of said data groups, thereby to detect and quantify cluster features other than cluster population; and an output device connected to indicate the identified and quantified cluster information developed from inspecting and analyzing the sensed object to a user of the system.

Claim 5

A method for extracting cluster shape feature properties of a d-dimensional image that can be unbounded in a first dimension wherein said image consisting of one or more classes containing sites selected from the group consisting of pixels and voxels comprising the steps of: (a) inputting an image section j of said image; (b) determining class type t of site i in image section j; (c) identifying zero or more distinct p proper cluster labels k 1 , . . . ,k p of labeled sites adjacent and of the same class type t as site i using a capability of a basic bounded Hoshen-Kopelman algorithm with label reuse for identifying proper labels of clusters; (d) calculating scalar and non-scalar image m site properties f.sup.(n) (i) for site i where n=1,2, . . . ,m; (e) if p=0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=f.sup.(n) (i) and C(k)=t wherein F.sup.(n) (k) is a cluster shape feature property of a cluster fragment of the same mathematical type as f.sup.(n) (i), C(k) is a cluster class type identifier and k is a cluster proper label selected using a basic bounded Hoshen-Kopelman algorithm with label reuse capability for selecting a cluster proper label when p=0; (f) if p>0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=F.sup.(n) (k.sub.1)⊕.sup.(n) . . . ⊕.sup.(n) (k.sub.p)⊕.sup.(n) f.sup.(n) (i) wherein ⊕.sup.(n) is binary associative and commutative operator that operates on said f.sup.(n) (i) and cluster feature shape properties F.sup.(n) (k 1 ), . . . , F.sup.(n) (k p ) of the same mathematical type as f.sup.(n) (i) and F.sup.(n) (k) and k is a cluster proper label selected using a capability of the Hoshen-Kopelman algorithm with label reuse for selecting a cluster proper label when p>0; (g) repeating steps (a), (b), (c), (d), (e) and (f) for all sites in image section j; (h) outputting of all the determined F.sup.(n) (k,) cluster feature shape properties for i. each labeled cluster extending up to the image section previous to image section j and ii. each labeled cluster and labeled cluster fragment extending into image section j; (i) stopping if processing of said image is interrupted; (j) stopping if a number of contiguous image sections to be processed is defined and if said number is equal to the number of already processed image sections of said image; and (k) repeating steps (a), (b), (c), (d), (e), (f), (h), (i) and (j) for the next image section j of said image.

Claim 6

A method for extracting cluster shape feature properties of a d-dimensional image that can be unbounded in a first dimension wherein said image consisting of one or more classes containing sites selected from the group consisting of pixels and voxels comprising the steps of: (a) inputting an image section j of said image; (b) determining class type t of site i in image section j; (c) identifying zero or more distinct p proper cluster labels k 1 , . . . ,k p of labeled sites adjacent and of the same class type t as site i using a capability of a basic bounded Hoshen-Kopelman algorithm with label reuse for identifying proper labels of clusters; (d) calculating scalar and non-scalar image m site properties f.sup.(n) (i) for site i where n=1,2, . . . ,m; (e) if p=0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=f.sup.(n) (i) and C(k)=t wherein F.sup.(n) (k) is a cluster shape feature property of a cluster fragment of the same mathematical type as f.sup.(n) (i), C(k) is a cluster class type identifier and k is a cluster proper label selected using a basic bounded Hoshen-Kopelman algorithm with label reuse capability for selecting a cluster proper label when p=0; (f) if p>0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=F.sup.(n) (k.sub.1)⊕.sup.(n) . . . ⊕.sup.(n) (k.sub.p)⊕.sup.(n) f.sup.(n) (i) wherein ⊕.sup.(n) is binary associative and commutative operator that operates on said f.sup.(n) (i) and cluster feature shape properties F.sup.(n) (k 1 ), . . . , F.sup.(n) (k p ) of the same mathematical type as f.sup.(n) (i) and F.sup.(n) (k) and k is a cluster proper label selected using a capability of the Hoshen-Kopelman algorithm with label reuse for selecting a cluster proper label when p>0; (g) repeating steps (a), (b), (c), (d), (e) and (f) for all sites in image section j; (h) outputting of all the determined F.sup.(n) (k,) cluster feature shape properties for i. each labeled cluster extending up to the image section previous to image section j and ii. each labeled cluster and labeled cluster fragment extending into image section j; (i) stopping if processing of said image is interrupted; (j) stopping if a number of contiguous image sections to be processed is defined and if said number is equal to the number of already processed image sections of said image; and (k) repeating steps (a), (b), (c), (d), (e), (f), (h), (i) and (j) for the next image section j of said image.

Claim 16

A method for extracting cluster shape feature properties in a d-dimensional image that can be unbounded in a first dimension wherein said image consisting of one or more classes containing sites of one or more classes represented by vectors contained within cells comprising the steps of (a) inputting an image section j of said cells of said image; (b) determining class type t of site i in cell q in image section j; (c) identifying zero or more distinct p proper cluster labels k 1 , . . . ,k p of labeled adjacent sites in adjacent cells and of the same class type t as site i using a capability of a basic bounded Hoshen-Kopelman algorithm with label reuse for identifying proper labels of clusters; (d) calculating scalar and non-scalar image m site properties f.sup.(n) (i) for site i where n=1,2, . . . ,m; (e) if p=0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=f.sup.(n) (i) and C(k)=t wherein F.sup.(n) (k), is a cluster shape feature property of a cluster fragment of the same mathematical type as f.sup.(n) (i), C(k) is a cluster class type identifier and k is a cluster proper label selected using a basic bounded Hoshen-Kopelman algorithm with label reuse capability for selecting a cluster proper label when p=0; (f) if p>0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=F.sup.(n) (k.sub.1)⊕.sup.(n) . . . ⊕.sup.(n) F.sup.(n) (k.sub.p)⊕.sup.(n) f.sup.(n) (i) wherein ⊕.sup.(n) is binary associative and commutative operator that operates on said f.sup.(n) (i) and cluster feature shape properties F.sup.(n) (k 1 ), . . . , F.sup.(n) ( p ) of the same mathematical type as f.sup.(n) (i) and F.sup.(n) (k) and k is a cluster proper label selected using a capability of the Hoshen-Kopelman algorithm with label reuse for selecting a cluster proper label when p>0; (g) repeating steps (a), (b), (c), (d), (e) and (f) for all sites belonging to all cells in image section j; (h) outputting of all the determined F.sup.(n) (k) cluster feature shape properties for i. each labeled cluster extending up to the image section previous to image section j and ii. each labeled cluster and labeled cluster fragment extending into image section j; (i) stopping if processing of said image is interrupted; (j) stopping if a number of contiguous image sections to be processed is defined and if said number is equal to the number of already processed image sections of said image; and (k) repeating steps (a), (b), (c), (d), (e), (f), (h), (i) and (j) for the next image section j of said image.

Claim 17

A method for extracting cluster shape feature properties in a d-dimensional image that can be unbounded in a first dimension wherein said image consisting of one or more classes containing sites of one or more classes represented by vectors contained within cells comprising the steps of (a) inputting an image section j of said cells of said image; (b) determining class type t of site i in cell q in image section j; (c) identifying zero or more distinct p proper cluster labels k 1 , . . . ,k p of labeled adjacent sites in adjacent cells and of the same class type t as site i using a capability of a basic bounded Hoshen-Kopelman algorithm with label reuse for identifying proper labels of clusters; (d) calculating scalar and non-scalar image m site properties f.sup.(n) (i) for site i where n=1,2, . . . ,m; (e) if p=0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=f.sup.(n) (i) and C(k)=t wherein F.sup.(n) (k), is a cluster shape feature property of a cluster fragment of the same mathematical type as f.sup.(n) (i), C(k) is a cluster class type identifier and k is a cluster proper label selected using a basic bounded Hoshen-Kopelman algorithm with label reuse capability for selecting a cluster proper label when p=0; (f) if p>0 computing for all n=1,2, . . . ,m F.sup.(n) (k)=F.sup.(n) (k.sub.1)⊕.sup.(n) . . . ⊕.sup.(n) F.sup.(n) (k.sub.p)⊕.sup.(n) f.sup.(n) (i) wherein ⊕.sup.(n) is binary associative and commutative operator that operates on said f.sup.(n) (i) and cluster feature shape properties F.sup.(n) (k 1 ), . . . , F.sup.(n) ( p ) of the same mathematical type as f.sup.(n) (i) and F.sup.(n) (k) and k is a cluster proper label selected using a capability of the Hoshen-Kopelman algorithm with label reuse for selecting a cluster proper label when p>0; (g) repeating steps (a), (b), (c), (d), (e) and (f) for all sites belonging to all cells in image section j; (h) outputting of all the determined F.sup.(n) (k) cluster feature shape properties for i. each labeled cluster extending up to the image section previous to image section j and ii. each labeled cluster and labeled cluster fragment extending into image section j; (i) stopping if processing of said image is interrupted; (j) stopping if a number of contiguous image sections to be processed is defined and if said number is equal to the number of already processed image sections of said image; and (k) repeating steps (a), (b), (c), (d), (e), (f), (h), (i) and (j) for the next image section j of said image.

Claim 18

An apparatus for extracting cluster shape feature properties of a d-dimensional image that can be unbounded in a first dimension wherein said image consisting of one or more classes containing sites selected from the group consisting of pixels and voxels comprising: (a) means for inputting an image section j of said image; (b) means for determining class type t of site i in image section j; (c) means for identifying zero or more distinct p proper cluster labels k 1 , . . . ,k p of labeled sites adjacent and of the same class type t as site i using a capability of a basic bounded Hoshen-Kopelman algorithm with label reuse for identifying proper labels of clusters; (d) means for calculating scalar and non-scalar image m site properties f.sup.(n) (i) for site i where n=1,2, . . . ,m; (e) if p=0 means for computing for all n=1,2, . . . ,m F.sup.(n) (k)=f.sup.(n) (i) and C(k)=t wherein F.sup.(n) (k) is a cluster shape feature property of a cluster fragment of the same mathematical type as f.sup.(n) (i), C(k) is a cluster class type identifier and k is a cluster proper label selected using a basic bounded Hoshen-Kopelman algorithm with label reuse capability for selecting a cluster proper label when p=0; (f) if p>0 means for computing for all n=1,2, . . . ,m F.sup.(n) (k)=F.sup.(n) (k.sub.1)⊕.sup.(n) . . . ⊕.sup.(n) F.sup.(n) (k.sub.p)⊕.sup.(n) f.sup.(n) (i) wherein ⊕.sup.(n) is binary associative and commutative operator that operates on said f.sup.(n) (i) and cluster feature shape properties F.sup.(n) (k 1 ), . . . ,F.sup.(n) (k p ) of the same mathematical type as f.sup.(n) (i) and F.sup.(n) (k) and k is a cluster proper label selected using a capability of the Hoshen-Kopelman algorithm with label reuse for selecting a cluster proper label when p>0; (g) means for repeating (a), (b), (c), (d), (e) and (f) for all sites in image section j; (h) means for outputting of all the determined F.sup.(n) (k) cluster feature shape properties for i. each labeled cluster extending up to the image section previous to image section j and ii. each labeled cluster and labeled cluster fragment extending into image section j; (i) means for stopping if processing of said image is interrupted; (j) means for stopping if a number of contiguous image sections to be processed is defined and if said number is equal to the number of already processed image sections of said image; and (k) means of repeating (a), (b), (c), (d), (e), (f), (h), (i) and (j) for the next image section j of said image.

Claim 19

An apparatus for extracting cluster shape feature properties of a d-dimensional image that can be unbounded in a first dimension wherein said image consisting of one or more classes containing sites selected from the group consisting of pixels and voxels comprising: (a) means for inputting an image section j of said image; (b) means for determining class type t of site i in image section j; (c) means for identifying zero or more distinct p proper cluster labels k 1 , . . . ,k p of labeled sites adjacent and of the same class type t as site i using a capability of a basic bounded Hoshen-Kopelman algorithm with label reuse for identifying proper labels of clusters; (d) means for calculating scalar and non-scalar image m site properties f.sup.(n) (i) for site i where n=1,2, . . . ,m; (e) if p=0 means for computing for all n=1,2, . . . ,m F.sup.(n) (k)=f.sup.(n) (i) and C(k)=t wherein F.sup.(n) (k) is a cluster shape feature property of a cluster fragment of the same mathematical type as f.sup.(n) (i), C(k) is a cluster class type identifier and k is a cluster proper label selected using a basic bounded Hoshen-Kopelman algorithm with label reuse capability for selecting a cluster proper label when p=0; (f) if p>0 means for computing for all n=1,2, . . . ,m F.sup.(n) (k)=F.sup.(n) (k.sub.1)⊕.sup.(n) . . . ⊕.sup.(n) F.sup.(n) (k.sub.p)⊕.sup.(n) f.sup.(n) (i) wherein ⊕.sup.(n) is binary associative and commutative operator that operates on said f.sup.(n) (i) and cluster feature shape properties F.sup.(n) (k 1 ), . . . ,F.sup.(n) (k p ) of the same mathematical type as f.sup.(n) (i) and F.sup.(n) (k) and k is a cluster proper label selected using a capability of the Hoshen-Kopelman algorithm with label reuse for selecting a cluster proper label when p>0; (g) means for repeating (a), (b), (c), (d), (e) and (f) for all sites in image section j; (h) means for outputting of all the determined F.sup.(n) (k) cluster feature shape properties for i. each labeled cluster extending up to the image section previous to image section j and ii. each labeled cluster and labeled cluster fragment extending into image section j; (i) means for stopping if processing of said image is interrupted; (j) means for stopping if a number of contiguous image sections to be processed is defined and if said number is equal to the number of already processed image sections of said image; and (k) means of repeating (a), (b), (c), (d), (e), (f), (h), (i) and (j) for the next image section j of said image.