METHOD AND APPARATUS FOR PREDICTING OBJECT PROPERTIES AND EVENTS USING SIMILARITY-BASED INFORMATION RETRIEVAL AND MODELING

• US 20100332210A1
• Filed: 06/25/2010
• Published: 12/30/2010
• Est. Priority Date: 06/25/2009
• Status: Active Grant

• Current Assignee: United States Secretary of the Army, University of Tennessee Research Foundation (University of Tennessee)
• Original Assignee: University of Tennessee Research Foundation (University of Tennessee), US Army Space & Missile Defense Command/Army Forces Strategic Command
• Inventors: Wang, Tse-Wei, Icove, David J., Rader, Mark, Birdwell, J. Douglas, Horn, Sally P.
• Granted Patent: US 8,375,032 B2
• Time in Patent Office: Days
• US Class Current: 703/22
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: G06Q 30/0185 Product, service or business identity fraud
• CPC Class Codes: G06Q 50/265 Personal security, identity or safety
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 10/945 User interactive design; Environments; Toolboxes

Abstract

Method and apparatus for predicting properties of a target object, in particular, one of an origin and a source, comprise application of a search manager for analyzing parameters of a plurality of databases for a plurality of objects, the databases comprising an electrical, electromagnetic, acoustic spectral database (ESD), a micro-body assemblage database (MAD) and a database of image data whereby the databases store data objects containing identifying features, source information and information on site properties and context including time and frequency varying data. The method comprises application of multivariate statistical analysis and principal component analysis in combination with content-based image retrieval for providing two-dimensional attributes of three dimensional objects, for example, via preferential image segmentation using a tree of shapes and to predict further properties of objects by means of k-means clustering and related methods. By way of example, a fire event and residual objects may be located and qualified such that, for example, properties of the residual objects may be qualified, for example, via black body radiation and micro-body databases including charcoal assemblages.

Claims

1. A method of predicting a property of a target object via receiving a query to processor search manager apparatus comprising a processor and memory, the processor search apparatus coupled to a database of spectral data, the method comprising:

storing data objects in the database of spectral data for a plurality of objects, an object being described by a vector of attributes;

processing the received query comprising information about the target object;

analyzing via said processor of said search manager apparatus the attributes utilizing multivariate statistical analysis to determine a subspace of an attributes space, the subspace having at least two dimensions;

clustering via said processor the objects into groups of objects where a measure of similarity between objects comprises projecting attribute vectors onto the attributes subspace and using one of a distance function and a metric as an inverse measure of similarity;

determining projections via said processor onto a subspace for clustering and indexing objects in said groups of objects; and

predicting one of a geographic origin property and an environmental property of the target object from said clustering and indexing.

2. The method of claim 1 further comprising said processor predicting one of source and origin properties of an object responsive to said clustering of said object into a group of like objects.

3. The method of claim 1 further comprising generating a second database of image data for said plurality of objects.

4. The method of claim 1 wherein said spectral data comprises acoustic and electromagnetic spectral data for an object.

5. The method of claim 1 further comprising generating a second database of image data and a third database comprising micro-body assemblage data.

6. The method of claim 1 wherein the attributes subspace is the object clustering and indexing subspace.

7. The method of claim 2 wherein said spectral data comprise one of acoustic and electromagnetic property data, the method further comprising predicting one of a geographic origin and an environment of a component of the target object.

8. The method of claim 1 wherein said spectral data comprise acoustic and electromagnetic property data, the method comprising identifying an object by a radio frequency spectral signature.

9. The method of claim 1 wherein said geographic origin property comprises a predicted identification of a manufacturing origin.

10. A method of predicting object properties of a target object via receiving at least one query to processor search manager apparatus coupled to a plurality of databases comprising a micro-body assemblage database and a spectral database for objects coupled to the processor search manager apparatus, the processor search manager apparatus comprising a processor and memory, the method comprising:

determining, responsive to the received query, a set of objects most similar to the target object via said processor search manager apparatus for searching the plurality of databases,

applying at least one model to predict a property of the target object,

comparing hypothetical relationships involving the target object and a subset of the set of similar objects, and

determining a probable relationship and one of a geographic origin property and an environmental property of the target object.

11. The method of claim 10 further comprising inferring a property value for a newly acquired object by modeling how a property value varies with other attributes of the newly acquired object.

12. The method of claim 10 wherein the plurality of databases further comprises a database of image data for objects.

13. The method of claim 10 further comprising predicting one of a geographic source location and region associated with a target object responsive to said determined probable relationship and property value of the target object.

14. The method of claim 10 wherein said at least one model comprises a Bayesian model.

15. The method of claim 14 further comprising having at least two different models and using one of a maximum likelihood estimation and a likelihood ratio to choose a better model of the two different models.

16. A method of predicting a property of a target object by receiving a query input to processor search manager apparatus coupled to a core database comprising a database of spectral property data of objects that are different from one another, a database of property data of three dimensional objects comprising micro-body assemblages, and a database of image data of objects having image segments, the processor search manager apparatus comprising a processor and memory, an object comprising a micro-body assemblage and an object having spectral properties, an object being described by a vector of real-valued attributes, the method comprising:

receiving a property data input query for the target object;

linking said core database of property data to said image database for comparison of the input property data of the target object to image data of said image database of said core database;

initiating a query of said core database;

measuring similarity between image segments produced using an image segmentation algorithm;

analyzing via said processor search manager apparatus the attributes utilizing multivariate statistical analysis including using principal component analysis to determine a subspace having at least two dimensions of an attributes space in which the objects can be clustered into two groups where a measure of similarity between objects comprises projecting the attribute vectors onto orthogonal vectors for the subspace, the measure being an inverse of the Euclidean distance between points in the subspace;

determining projections onto the subspace for clustering and indexing like objects; and

using the properties of objects stored in at least one of the databases and belonging to a cluster to predict one of a source property, an origin property and an environmental property of the target object.

17. The method of claim 16 further comprising linking said core database to said micro-body assemblage property database for comparison of the input property data of the target object to assemblage data of said assemblage database of said core database and measuring similarity between micro-body assemblage property data of said target object and data of objects of said micro-body assembly property database.

18. The method of claim 16 further comprising linking said core database to said database of spectral properties of objects for comparison of the input property data of the target object to spectral property data of said spectral database of said core database and measuring similarity between spectral property data of said target object and spectral data of objects of said spectral property database.

19. The method of claim 16 wherein said spectral properties comprise one of acoustic and electromagnetic property data of an object.

20. The method of claim 19 wherein said spectral properties comprise one of acoustic and electromagnetic property data of objects and further comprising predicting one of a geographic origin property and an environmental property of a component of the target object.

21. The method of claim 16 further comprising generating an impulse response model from time series data associated with an object.

22. The method of claim 16, said property data comprising characteristic spectrum signature property data for identifying one of a source and an origin of a target object.

23. The method of claim 21 wherein said impulse response model generation comprises solving a convex optimization problem.

24. A method of predicting one of a source, an origin and an environmental property of a target object upon receiving a query input to search manager apparatus coupled to at least one reference database containing micro-body assemblage information and at least one second reference database of second type information obtained by one of electrical, electromagnetic, acoustic, chemical, mechanical, optical and isotopic measurement, the micro-body assemblage and second reference databases being related to at least two sample objects, the at least one second reference database including one of source and origin property information about at least two sample objects in which the micro-body assemblage information and the second type of information are stored, the processor search manager apparatus comprising a processor and memory, the method comprising:

receiving at least one input query comprising information describing a sample of micro-bodies of the target object and a measurement of one of an electrical, electromagnetic, acoustic, chemical, mechanical, optical and isotopic property of the target object for which information of the same type is stored in database memory;

for a type of information present in the query and reference database determined by the information type;

(a) utilizing a tree-structured index to identify stored information from the reference database that is most similar to input information of the target object, wherein the processor identifies reference database information of one or more samples or objects to which the target object input information is related; and

(b) retrieving, from the reference database, one of source, origin and environmental property information included in the reference database about the identified sample or object; and

(c) predicting at least one origin, source or environmental property of the target object using a model for processing the retrieved source, origin or environmental property information.

25. The method of claim 24 wherein the processor uses the model to lead to an inference of at least one of geographic location, geographic region and environmental characteristics of points of origin, and one of time and season associated with the target object.

26. The method of claim 24 wherein the model is a Bayesian network or belief network.

27. The method of claim 24 wherein the model uses a least squares or maximum likelihood optimization method to determine a best fit of the values of one or more properties of the target and identified samples or objects of the reference database to produce an optimized model.

28. The method of claim 27 further comprising using the optimized model to predict at least one property of the target object.

29. The method of claim 24 wherein the model is a compartmental model.

30. The method of claim 24 wherein the predicted property is determined using one of a likelihood ratio and a maximum likelihood estimation.

31. The method of claim 24, predicting a property of the target object further comprising testing multiple hypotheses to predict one of a source and origin of the target object.

32. The method of claim 24 wherein said second type of information is one of an electrical, electromagnetic, acoustic and optical spectrum and the method comprises calculating a measure of the correlation between spectra to identify similar spectra in the second reference database to identify one of a source and an origin of the target object.

33. A method of predicting properties of a target object by receiving an input query at search manager apparatus coupled to a reference core database containing micro-body assemblage information, said micro-body assemblage information including one of geographic distributions of micro-bodies comprising pollen, charcoal, dust and soil property data and environmental characteristic of sample collection sites, the reference core database being coupled to processor search manager apparatus, the processor search manager apparatus comprising a processor and memory, the method comprising

inputting the query comprising information describing a sample of pollen, charcoal, dust or soil found on or in the target object;

utilizing a tree-structured index to retrieve stored information from the reference core database that is most similar to said input information;

obtaining a geographic distribution or an environmental characteristic associated with said retrieved information; and

predicting at least one property of the target object using a model for processing said retrieved information comprising at least one of the geographic distribution and the environmental characteristic.

34. The method of claim 33 wherein said micro-body assemblage information includes information about charcoal particles and predicting comprises predicting one of a fire and an intrusion event.

35. The method of claim 33 wherein the reference core database comprises an image database for image data of a micro-body assemblage, the image database including images of one of pollen, charcoal, dust and soil grains.

36. The method of claim 34 wherein said tree-structured index is utilized to retrieve at least one image of a pollen grain, a charcoal grain, a dust grain and a soil grain that is similar to an image of a pollen grain, a charcoal grain, a dust grain and a soil grain obtained from said target object.

37. The method of claim 33 wherein said tree-structured index is used to implement a preferential segment identification algorithm based upon a tree of shapes image segmentation model.

38. The method of claim 33 the micro-body assemblage information comprising geographic distribution data, the method further comprising interpreting the geographic distribution data of the micro-body assemblage information to determine an intersection of the geographic distribution data with data of said target object based on different characteristics of the micro-body assemblage information.

39. The method of claim 38 wherein the micro-body assemblage information comprise pollen assemblage information and the geographic distribution data comprises at least two geographic distributions of plants that have the same taxa as two pollen types that are present in the pollen assemblage information.

40. Portable apparatus for collecting sample data of a sample for uploading to a search manager apparatus and associated core database of a spectral database and of a micro-body assemblage database for predicting an object property, the portable apparatus comprising:

a data acquisition device for acquiring sample data of a sample comprising one of spectral data and micro-body assemblage data, the sample being identified with a location;

one of a client and a server connected to the data acquisition device for processing the data of a given type for uploading; and

a communications interface, responsive to the one of the client and server, for uploading the sample data of the given type to the search manager apparatus for storage in the core database and predicting the object property.

41. The portable apparatus of claim 40 wherein the portable apparatus comprises a client of a processor search manager server and the data acquisition device comprises a spectrum analyzer for obtaining frequency series data.