Intelligent spatial reasoning

• US 7,263,509 B2
• Filed: 04/09/2003
• Issued: 08/28/2007
• Est. Priority Date: 04/09/2003
• Status: Active Grant

• Current Assignee: Leica Microsystems CMS GmbH (Danaher Corporation)
• Original Assignee: Shih-Jong J. Lee
• Inventors: Oh, Seho, Lee, Shih-Jong J.
• Primary Examiner(s): Hirl; Joseph P
• Application Number:
  US10/411,437
• Publication Number:
  US 20040205038A1
• Time in Patent Office: 1,602 Days
• Field of Search: 706/47, 706/19, 706/14, 700/259
• US Class Current: 706/47
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

An intelligent spatial reasoning method receives a plurality of object sets. A spatial mapping feature learning method uses the plurality of object sets to create at least one salient spatial mapping feature output. It performs spatial reasoning rule learning using the at least one spatial mapping feature to create at least one spatial reasoning rule output. The spatial mapping feature learning method performs a spatial mapping feature set generation step followed by a feature learning step. The spatial mapping feature set is generated by repeated application of spatial correlation between two object sets. The feature learning method consists of a feature selection step and a feature transformation step and the spatial reasoning rule learning method uses the supervised learning method.

The spatial reasoning approach of this invention automatically characterizes spatial relations of multiple sets of objects by comprehensive collections of spatial mapping features. Some of the features have clearly understandable physical, structural, or geometrical meanings. Others are statistical characterizations, which may not have clear physical, structural or geometrical meanings when considered individually. A combination of these features, however, could characterize subtle physical, structural or geometrical conditions under practical situations. One key advantage of this invention is the ability to characterize subtle differences numerically using a comprehensive feature set.

Claims

1. A computerized automatic spatial reasoning method to create spatial reasoning rules to characterize subtle physical, structural or geometrical conditions comprising the steps of:

a) Inputting a plurality of image object sets, each object contains its associated image pixels;

b) Designating one of the image object sets as target object set and another object set as condition object set;

c) Calculating spatial mapping features for the target object set from transformed images of the target object set and the condition object set;

d) Performing spatial mapping feature learning using the spatial mapping features to create at least one salient spatial mapping feature output;

e) Performing spatial reasoning rule learning by a supervised learning method using the at least one spatial mapping feature to create at least one spatial reasoning rule output;

f) Using the spatial reasoning rule output to characterize spatial relations of multiple sets of objects for applications such as geographical information systems, cell image informatics, semiconductor or electronic automatic defect classification or military automatic target classification applications.

2. The computerized automatic spatial reasoning method of claim 1 wherein the spatial mapping feature learning process further comprises the steps of:

a) Performing spatial mapping feature set generation using the plurality of image object sets to create a spatial mapping feature set output;

b) Performing feature learning using the spatial mapping feature set to create at least one salient spatial mapping feature output;

c) Using events associated with the feature sets as the labels for the spatial mapping features.

3. The computerized automatic spatial reasoning of claim 2 wherein the spatial mapping feature set is generated by the steps of:

a) Transforming each object set by several image label propagation operations to generate transformed images of the target object set and the condition object set;

b) Applying spatial correlation between the transformed images of the target object set and the condition object set.

4. The computerized automatic spatial reasoning of claim 2 wherein the feature learning method consists of the steps of:

a) Performing feature selection to select a subset of features that could discriminate between pixels of different classes;

b) Performing feature transformation to transform the original feature set into a subset of derived features.

5. A computerized automatic two image object set spatial mapping feature generation method to create spatial mapping features that can be used to characterize subtle physical, structural or geometrical conditions comprises the steps of:

a) Inputting a first image object set containing its associated image pixels, designated as target image object set;

b) Inputting a second image object set containing its associated image pixels, designated as condition image object set;

c) Performing label propagation operation assigning labels to image pixels on the target image object set and the condition image object set to create target image object set transformed data and condition image object set transformed data output;

d) Performing a spatial mapping features calculation using the target image object set transformed data and the condition image object set transformed data to create an image spatial mapping features output;

e) Using the image spatial mapping features output to characterize spatial relations of two image object sets for applications such as geographical information systems, cell image informatics, semiconductor or electronic automatic defect classification or military automatic target classification applications.

6. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the label propagation operation is selected from the set consisting of

a) No operation,

b) Inner distance transformation of the image pixels,

c) Outer distance transformation of the image pixels,

d) Connected component labeling of the image pixels, and

e) Zone of influence labeling of the image pixels.

7. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with no operation target image data and no operation condition image data that is selected from the set consisting of

a) Condition ratio as the probability of condition image object set included in the target image object set, and

b) Intersection ratio:

Area(Condition ∩

Target)/Area(Condition U Target).

8. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with no operation target data and inner distance transformed condition data that is selected from the set consisting of

a) Inner distance mean,

b) Inner distance standard deviation,

c) Normalized inner distance mean,

d) Normalized inner distance standard deviation,

e) Inner distance skewness, and

f) Inner distance kurtosis.

9. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with no operation target image data and outer distance transformed condition image data that is selected from the set consisting of

a) Outer distance mean,

b) Outer distance standard deviation,

c) Normalized outer distance mean;

d) Normalized outer distance standard deviation,

e) Outer distance skewness, and

f) Outer distance kurtosis.

10. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with no operation target data and connected component labeled condition data that is selected from the set consisting of

a) Intersection-component-count,

b) Intersection-component-count-ratio,

c) Intersection-component-average-area,

d) intersection-component-sd-area,

e) Intersection-component-average-area-ratio,

f) Intersection-component-sd-area-ratio, and

g) Intersection-component-area-entropy.

11. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with no operation target data and zone of influence labeled condition data that is selected from the set consisting of

a) ZOI_intersection-component-count,

b) ZOI_intersection-component-count-ratio,

c) ZOI_intersection-component-average-area,

d) ZOI_intersection-component-sd-area,

e) ZOI_intersection-component-average-area-ratio,

f) ZOI_intersection-component-sd-area-ratio,

g) ZOI_intersection-component-area-entropy, and

h) Intersection-component-count_proportion.

12. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with inner distance target data and no operation condition data that is selected from the set consisting of:

a) Target-inner-distance-mean,

b) Target-inner-distance-standard-deviation,

c) Normalized-target-inner-distance-mean,

d) Normalized-target-inner-distance-standard-deviation,

e) Target-inner-distance-skewness, and

f) Target-inner-distance-kurtosis.

13. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with inner distance target data and inner distance transformed condition data that is selected from the set consisting of:

a) P<sub>I—

ID</sub>-Energy,

b) P<sub>I—

ID</sub>-Entropy,

c) P<sub>I—

ID</sub>-Correlation,

d) P<sub>I—

ID</sub>-Inertia,

e) P<sub>I—

ID</sub>-Homogeneity,

f) P<sub>I—

ID</sub>-Max_probability,

g) P<sub>I—

ID</sub>-Cluster_tendency, and

h) P<sub>I—

ID</sub>-Deep_overlap_tendency.

14. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with inner distance target data and outer distance transformed condition data that is selected from the set consisting of:

a) P<sub>I—

OD</sub>-Energy,

b) P<sub>I—

OD</sub>-Entropy,

c) P<sub>I—

OD</sub>-Correlation,

d) P<sub>I—

OD</sub>-Inertia,

e) P<sub>I—

OD</sub>-Homogeneity,

f) P<sub>I—

OD</sub>-Max_probability,

g) P<sub>I—

OD</sub>-Cluster_tendency, and

h) P<sub>I—

OD</sub>-Deep_overlap_tendency.

15. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with inner distance target data and connected component labeled condition data that is selected from the set consisting of:

a) Target-inner-distance-mean-standard-deviation,

b) Target-inner-distance-standard-deviation_mean,

c) Target-inner-distance-standard-deviation_sd,

d) Normalized-target-inner-distance-mean-standard-deviation,

e) Normalized-target-inner-distance-standard-deviation_mean, and

f) Normalized-target-inner-distance-standard-deviation_sd.

16. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with inner distance target data and zone of influence labeled condition data that is selected from the set consisting of:

a) ZOI_target-inner-distance-mean-standard-deviation,

b) ZOI_target-inner-distance-standard-deviation_mean,

c) ZOI_target-inner-distance-standard-deviation_sd,

d) ZOI_normalized-target-inner-distance-mean-standard-deviation,

e) ZOI_normalized-target-inner-distance-standard-deviation_mean, and

f) ZOI_normalized-target-inner-distance-standard-deviation_sd.

17. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with outer distance target data and no operation condition data that is selected from the set consisting of:

a) Target-outer-distance-mean,

b) Target-outer-distance-standard-deviation,

c) Normalized-target-outer-distance-mean,

d) Normalized-target-outer-distance-standard-deviation,

e) Target-outer-distance-skewness, and

f) Target-outer-distance-kurtosis.

18. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with outer distance target data and inner distance transformed condition data that is selected from the set consisting of:

a) P<sub>O—

ID</sub>-Energy,

b) P<sub>O—

ID</sub>-Entropy,

c) P<sub>O—

ID</sub>-Correlation,

d) P<sub>O—

ID</sub>-Inertia,

e) P<sub>O—

ID</sub>-Homogeneity,

f) P<sub>O—

ID</sub>-Max_probability,

g) P<sub>O—

ID</sub>-Cluster_tendency, and

h) P<sub>O—

ID</sub>-Deep_overlap_tendency.

19. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with outer distance target data and outer distance transformed condition data that is selected from the set consisting of:

a) P<sub>O—

OD</sub>-Energy,

b) P<sub>O—

OD</sub>-Entropy,

c) P<sub>O—

OD</sub>-Correlation,

d) P<sub>O—

OD</sub>-Inertia,

e) P<sub>O—

OD</sub>-Homogeneity,

f) P<sub>O—

OD</sub>-Max_probability,

g) P<sub>O—

OD</sub>-Cluster_tendency, and

h) P<sub>O—

OD</sub>-Inside_overlap_tendency.

20. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with outer distance target data and connected component labeled condition data that is selected from the set consisting of:

a) Target-outer-distance-mean-standard-deviation,

b) Target-outer-distance-standard-deviation_mean,

c) Target-outer-distance-standard-deviation_sd,

d) Normalized-target-outer-distance-mean-standard-deviation,

e) Normalized-target-outer-distance-standard-deviation_mean, and

f) Normalized-target-outer-distance-standard-deviation_sd.

21. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with outer distance target data and zone of influence labeled condition data that is selected from the set consisting of:

a) ZOI_target-outer-distance-mean-standard-deviation,

b) ZOI_target-outer-distance-standard-deviation_mean,

c) ZOI_target-outer-distance-standard-deviation_sd,

d) ZOI_normalized-target-outer-distance-mean-standard-deviation,

e) ZOI_normalized-target-outer-distance-standard-deviation_mean, and

f) ZOI_normalized-target-outer-distance-standard-deviation_sd.

22. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with connected component labeled target data and no operation condition data that is selected from the set consisting of:

a) Intersection-target-component-count,

b) Intersection-target-component-count-ratio,

c) Intersection-target-component-average-area,

d) Intersection-target-component-sd-area,

e) Intersection-target-component-average-area-ratio,

f) Intersection-target-component-sd-area-ratio, and

g) Intersection-target-component-area-entropy.

23. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with connected component labeled target data and inner distance transformed condition data that is selected from the set consisting of:

a) Condition-inner-distance-mean-standard-deviation,

b) Condition-inner-distance-standard-deviation_mean,

c) Condition-inner-distance-standard-deviation_sd,

d) Normalized-condition-inner-distance-mean-standard-deviation,

e) Normalized-condition-inner-distance-standard-deviation_mean, and

f) Normalized-condition-inner-distance-standard-deviation_sd.

24. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with connected component labeled target data and outer distance transformed condition data that is selected from the set consisting of:

a) Condition-outer-distance-mean-standard-deviation,

b) Condition-outer-distance-standard-deviation_mean,

c) Condition-outer-distance-standard-deviation_sd,

d) Normalized-condition-outer-distance-mean-standard-deviation,

e) Normalized-condition-outer-distance-standard-deviation_mean, and

f) Normalized-condition-outer-distance-standard-deviation_sd.

25. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with connected component labeled target data and connected component labeled condition data that is selected from the set consisting of:

a) Target_intersection-component-count_mean,

b) Target_intersection-component-count_sd,

c) Target_intersection-component-count-ratio_mean,

d) Target_intersection-component-count-ratio_sd,

e) Target_intersection-component-average-area_mean,

f) Target_intersection-component-average-area_sd,

g) Target_intersection-component-average-area-ratio_mean,

h) Target_intersection-component-average-area-ratio_sd,

i) Target_intersection-component-area-entropy_mean, and

j) Target_intersection-component-area-entropy_sd.

26. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with connected component labeled target data and zone of influence labeled condition data that is selected from the set consisting of:

a) Target_intersection-ZOI-component-count_mean,

b) Target_intersection-ZOI-component-count_sd,

c) Target_intersection-ZOI-component-count-ratio_mean,

d) Target_intersection-ZOI-component-count-ratio_sd,

e) Target_intersection-ZOI-component-area_mean,

f) Target_intersection-ZOI-component-average-area_sd,

g) Target_intersection-ZOI-component-average-area-ratio_mean,

h) Target_intersection-ZOI-component-average-area-ratio_sd,

i) Target_intersection-ZOI-component-area-entropy_mean, and

j) Target_intersection-ZOI-component-area-entropy_sd.

27. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with ZOI labeled target data and no operation condition data that is selected from the set consisting of:

a) Intersection-target-ZOI-component-count,

b) Intersection-target-ZOI-component-count-ratio,

c) Intersection-target-ZOI-component-average-area,

d) Intersection-target-ZOI-component-sd-area,

e) Intersection-target-ZOI-component-average-area-ratio,

f) Intersection-target-ZOI-component-sd-area-ratio, and

g) Intersection-target-ZOI-component-area-entropy.

28. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with ZOI labeled target data and inner distance transformed condition data that is selected from the set consisting of:

a) Condition-inner-distance-mean-ZOI-standard-deviation,

b) Condition-inner-distance-standard-deviation-ZOI-mean,

c) Condition-inner-distance-standard-deviation-ZOI_sd,

d) Normalized-condition-inner-distance-mean-ZOI-standard-deviation,

e) Normalized-condition-inner-distance-standard-deviation-ZOI_mean, and

f) Normalized-condition-inner-distance-standard-deviation-ZOI_sd.

29. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with ZOI labeled target data and outer distance transformed condition data that is selected from the set consisting of:

a) Condition-outer-distance-mean-ZOI-standard-deviation,

b) Condition-outer-distance-standard-deviation-ZOI-mean,

c) Condition-outer-distance-standard-deviation-ZOI_sd,

d) Normalized-condition-outer-distance-mean-ZOI-standard-deviation,

e) Normalized-condition-outer-distance-standard-deviation-ZOI_mean, and

f) Normalized-condition-outer-distance-standard-deviation-ZOI_sd.

30. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with ZOI labeled target data and outer distance transformed condition data that is selected from the set consisting of:

a) Target-ZOI_intersection-component-count_mean,

b) Target-ZOI_intersection-component-count_sd,

c) Target-ZOI_intersection-component-count-ratio_mean,

d) Target-ZOI_intersection-component-count-ratio_sd,

e) Target-ZOI_intersection-component-area_mean,

f) Target-ZOI_intersection-component-average-area_sd,

g) Target-ZOI_intersection-component-average-area-ratio_mean,

h) Target-ZOI_intersection-component-average-area-ratio_sd,

i) Target-ZOI_intersection-component-area-entropy_mean, and

j) Target-ZOI_intersection-component-area-entropy_sd.

31. The computerized automatic two image object set spatial mapping feature generation method of claim 5 wherein the spatial mapping features calculation includes the spatial mapping features associated with ZOI labeled target data and ZOI labeled condition data that is selected from the set consisting of:

a) Target-ZOI_intersection-ZOI-component-count_mean,

b) Target-ZOI_intersection-ZOI-component-count_sd,

c) Target-ZOI_intersection-ZOI-component-count-ratio_mean,

d) Target-ZOI_intersection-ZOI-component-count-ratio_sd,

e) Target-ZOI_intersection-ZOI-component-area_mean,

f) Target-ZOI_intersection-ZOI-component-average-area_sd,

g) Target-ZOI_intersection-ZOI-component-average-area-ratio_mean,

h) Target-ZOI_intersection-ZOI-component-average-area-ratio_sd,

i) Target-ZOI_intersection-ZOI-component-area-entropy_mean, and

j) Target-ZOI_intersection-ZOI-component-area-entropy_sd.

32. A computerized automatic multiple image object set spatial mapping feature generation method to create spatial mapping features that can be used to characterize subtle physical, structural or geometrical conditions comprising the steps of:

a) Inputting a first image object set containing its associated image pixels, designated as target image object set;

b) Inputting a plurality of additional image object sets, each object contains its associated image pixels;

c) Designating each of the plurality of additional image object sets as condition image object set;

d) Calculating spatial mapping features for the target image object set from transformed images of the target image object set and the condition image object set;

e) Performing contrast feature extraction using spatial mapping features for each dual of the object set pairs to create a contrast features output;

f) Using the contrast features output to characterize spatial relations of multiple sets of objects for applications such as geographical information systems, cell image informatics, semiconductor or electronic automatic defect classification or military automatic target classification applications.

33. The computerized automatic multiple image object set spatial mapping feature generation method of claim 32 wherein the contrast feature is selected from the set consisting of:

a) Feature difference,

b) Absolute feature difference,

c) First feature proportion,

d) Second feature proportion, and

e) Absolute difference proportion.