Framework of hierarchical sensory grammars for inferring behaviors using distributed sensors

• US 8,630,965 B2
• Filed: 04/06/2007
• Issued: 01/14/2014
• Est. Priority Date: 04/06/2006
• Status: Active Grant

• Current Assignee: University of Maryland, Yale University
• Original Assignee: Yale University
• Inventors: Savvides, Andreas, Lymberopoulos, Dimitrios, Aloimonos, Yiannis, Ogale, Abhijit S.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US12/296,078
• Publication Number:
  US 20100153321A1
• Time in Patent Office: 2,475 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 7/00 Computing arrangements based on specific mathematical models
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules

Abstract

Provided herein are methods, systems, and apparatuses that can utilize a grammar hierarchy to parse out observable activities into a set of distinguishable actions.

Claims

1. A method for identifying a human behavior of an entity that takes place in space and time, comprising:

a) receiving sensor data related to an action sequence of the entity from a pluralityof sensors that are positioned at respective nodes of a sensor network;

b) interpreting the sensor data according to a grammar hierarchy to produce a current set of semantics;

c) determining if a higher level grammar hierarchy exists;

d) interpreting the current set of semantics according to the higher level grammar hierarchy to produce a new set of semantics, wherein the new set of semantics comprises human behaviors of the current set of semantics that are interpreted as higher order human behaviors that take place at a more macroscopic level than the scale of the human behaviors of the current set of semantics;

e) identifying the new set of semantics as the current set of semantics;

f) repeating steps c, d and e, until it is determined that no higher level grammar hierarchy exists; and

g) outputting the current set of semantics as indicative of a particular human behavior of the entity,

wherein each grammar level for each node generates outputs from the sensor data generated by each node, wherein the current set of semantics for each node is propagated across the sensor network; and

wherein each grammar hierarchy level computes a set of probabilities for each human behavior such that lower level grammar hierarchies infer simple human behaviors that allow for higher level grammar hierarchies to infer higher order human behaviors that take place at a more macroscopic level.

2. The method of claim 1, wherein each sensor comprises at least one sensing modality.

3. The method of claim 2, wherein the sensor data is related to a spatial position of the entity.

4. The method of claim 3, wherein the sensor data is related to a time that the entity is at the spatial position.

5. The method of claim 1, wherein the grammar hierarchies comprises hierarchies of probabilistic context free grammars.

6. The method of claim 5, wherein the probabilistic context free grammars comprise spatial hierarchies.

7. The method of claim 5, wherein the probabilistic context free grammars comprise spatio-temporal hierarchies.

8. The method of claim 1, wherein the step of interpreting the sensor data according to the grammar hierarchy to produce a new set of semantics comprises:

assembling the sensor data into a sequence of sensor measurements;

converting the sequence of sensor measurements to a sequence of phonemes;

converting the sequence of phonemes into a plurality of sequences of human behaviors;

computing a sequence probability for each sequence of human behaviors based on a probability associated with each human behavior; and

selecting the sequence of human behaviors with the highest sequence probability as the new set of semantics.

9. The method of claim 1, wherein the step of interpreting the sensor data according to the grammar hierarchy to produce a new set of semantics comprises:

assembling the sensor data into a sequence of sensor measurements and times;

converting the sequence of sensor measurements and times into a plurality of sequences of time durations at spatial positions;

computing a sequence probability for each sequence of time durations at spatial positions based on a probability associated with each duration of time at a spatial position; and

selecting the sequence of durations of times at spatial positions with the highest sequence probability as the new set of semantics.

10. The method of claim 1, wherein repeating steps c, d, and e, comprises:

converting the current set of semantics into a plurality of sequences of human sub-behaviors;

computing a sequence probability for each sequence of human sub-behaviors based on a probability associated with each human sub-behavior; and

selecting the sequence of human sub-behaviors with the highest sequence probability as the new set of semantics.

11. A method for determining a behavior of an entity that takes place in space and time, comprising:

receiving sensor measurements from a plurality of sensors that are positioned at respective nodes of a sensor network, wherein the sensor measurements are related to a spatial position or context of an entity;

interpreting the sensor measurements as phonemes according to a phoneme definition;

interpreting the phonemes according to a first grammar hierarchy to produce a first set of semantics, wherein the first grammar hierarchy comprises a plurality of human behaviors associated with a plurality of spatial positions; and

interpreting the first set of semantics according to a second grammar hierarchy to produce a second set of semantics, wherein the second set of semantics is indicative of the human behavior of the entity that takes place at a more macroscopic level than the scale of the human behaviors of the first set of semantics,

wherein the first and second grammar hierarchy for each node generates outputs from the sensor data generated by each node, wherein the second set of semantics for each node is propagated across the sensor network; and

wherein each grammar hierarchy computes a set of

probabilities for each human behavior such that first level grammar hierarchies infer simple human behaviors that allow for the second grammar hierarchies to infer higher order human behaviors that take place at a more macroscopic level.

12. The method of claim 11, wherein the first grammar hierarchy and the second grammar hierarchy are comprised of hierarchies of probabilistic context free grammars.

13. The method of claim 12, wherein the plurality of spatial positions has been predefined.

14. The method of claim 13, wherein the step of interpreting the sensor measurements according to the first grammar hierarchy to produce a first set of semantics comprises:

assembling the sensor measurements into a sequence of phonemes;

converting the sequence of phonemes into a plurality of sequences of human behaviors;

computing a sequence probability for each sequence of human behaviors based on a probability associated with each human behavior; and

selecting the sequence of human behaviors with the highest sequence probability as the first set of semantics.

15. The method of claim 13, wherein the first grammar hierarchy further comprises a plurality of exceptions.

16. The method of claim 14, further comprising:

filtering an exception from the first set of semantics, thus preventing the first set of semantics from comprising the exception; and

triggering an action based on the exception.

17. The method of claim 13, wherein the second grammar hierarchy comprises a plurality of human sub-behaviors associated with the plurality of human behaviors.

18. The method of claim 17, wherein the step of interpreting the first set of semantics according to the second grammar hierarchy to produce a second set of semantics comprises:

converting the first set of semantics into a plurality of sequences of human sub behaviors;

computing a sequence probability for each sequence of human sub-behaviors based on a probability associated with each human sub-behavior; and

selecting the sequence of human sub-behaviors with the highest sequence probability as the second set of semantics.

19. The method of claim 18, further comprising:

filtering an exception from the second set of semantics, thus preventing the second set of semantics from comprising the exception; and

triggering an action based on the exception.

20. The method of claim 13, wherein the sensor measurements further comprise data related to a time the entity is at a position.

21. The method of claim 20, wherein the first grammar hierarchy comprises a plurality of time durations associated with the plurality of spatial positions.

22. The method of claim 21, wherein the step of interpreting the sensor measurements according to the first grammar hierarchy to produce a first set of semantics comprises:

assembling the sensor measurements into a sequence of spatial positions and times;

converting the sequence of spatial positions and times into a plurality of sequences of time durations at spatial positions;

computing a sequence probability for each sequence of time durations at spatial positions based on a probability associated with each duration of time at a spatial position; and

selecting the sequence of time durations at spatial positions with the highest sequence probability as the first set of semantics.

23. The method of claim 22, wherein the second grammar hierarchy comprises a plurality of human behaviors associated with the plurality of time durations associated with the plurality of spatial positions.

24. The method of claim 23, wherein the step of interpreting the first set of semantics according to the second grammar hierarchy to produce a second set of semantics comprises:

converting the first set of semantics into a plurality of sequences of human behaviors;

computing a sequence probability for each sequence of human behaviors based on a probability associated with each human behavior; and

selecting the sequence of human behaviors with the highest sequence probability as the second set of semantics.

25. The method of claim 24, further comprising:

filtering an exception from the second set of semantics, thus preventing the second set of semantics from comprising the exception; and

triggering an action based on the exception.

26. A system for identifying a behavior of an entity that takes place in space and time, comprising:

a sensor;

a memory;

a processor, coupled to the sensor and the memory, wherein the processor is configured for performing the steps of;

a) receiving sensor data related to an action sequence of the entity from the sensor and storing the sensor data on the memory;

b) interpreting the sensor data according to a grammar hierarchy to produce a current set of semantics;

c) determining if a higher level grammar hierarchy exists;

d) interpreting the current set of semantics according to the higher level grammar hierarchy to produce a new set of semantics, wherein the new set of semantics comprises human behaviors of the current set of semantics that are interpreted as higher order human behaviors that take place at a more macroscopic level than the scale of the human behaviors of the current set of semantics;

e) identifying the new set of semantics as the current set of semantics;

f) repeating steps c, d and e, until it is determined that no higher level grammar hierarchy exists; and

g) outputting the current set of semantics as indicative of a particular human behavior of the entity,

wherein each grammar level for each node generates outputs from the sensor data generated by each node, wherein the current set of semantics for each node is propagated across the sensor network; and

wherein each grammar hierarchy level computes a set of probabilities for each human behavior such that lower level grammar hierarchies infer simple human behaviors that allow for higher level grammar hierarchies to infer higher order human behaviors that take place at a more macroscopic level.

27. The system of claim 26, wherein each sensor comprises at least one sensing modality.

28. The system of claim 27, wherein the sensor data is related to a spatial position of the entity.

29. The system of claim 28, wherein the sensor data is related to a time that the entity is at the spatial position.

30. The system of claim 26, wherein the grammar hierarchies comprises hierarchies of probabilistic context free grammars.

31. The system of claim 30, wherein the probabilistic context free grammars comprise spatial hierarchies.

32. The system of claim 30, wherein the probabilistic context free grammars comprise spatio-temporal hierarchies.

33. The system of claim 26, wherein the step of interpreting the sensor data according to the grammar hierarchy to produce a new set of semantics comprises:

assembling the sensor data into a sequence of sensor measurements;

converting the sequence of sensor measurements to a sequence of phonemes;

converting the sequence of phonemes into a plurality of sequences of human behaviors;

computing a sequence probability for each sequence of human behaviors based on a probability associated with each human behavior; and

selecting the sequence of human behaviors with the highest sequence probability as the new set of semantics.

34. The system of claim 26, wherein the step of interpreting the sensor data according to the grammar hierarchy to produce a new set of semantics comprises:

assembling the sensor data into a sequence of sensor measurements and times;

converting the sequence of sensor measurements and times into a plurality of sequences of time durations at spatial positions;

computing a sequence probability for each sequence of time durations at spatial positions based on a probability associated with each duration of time at a spatial position; and

selecting the sequence of durations of times at spatial positions with the highest sequence probability as the new set of semantics.

35. The system of claim 26, wherein repeating steps c, d, and e, comprises:

converting the current set of semantics into a plurality of sequences of human sub behaviors;

computing a sequence probability for each sequence of human sub-behaviors based on a probability associated with each human sub-behavior; and

selecting the sequence of human sub-behaviors with the highest sequence probability as the new set of semantics.

36. The system of claim 26, wherein the sensor is at least one of a camera, a timer, a GPS, an infrared detector, a sound detector, a current sensor, a contact sensor, a pressure sensor, and a passive infrared sensor.

37. A computer readable medium with computer executable instructions embodied thereon for performing the steps comprising:

a) receiving sensor data related to an action sequence of the entity from a sensor;

b) interpreting the sensor data according to a grammar hierarchy to produce a current set of semantics;

c) determining if a higher level grammar hierarchy exists;

d) interpreting the current set of semantics according to the higher level grammar hierarchy to produce a new set of semantics, wherein the new set of semantics comprises human behaviors of the current set of semantics that are interpreted as higher order human behaviors that take place at a more macroscopic level than the scale of the human behaviors of the current set of semantics;

e) identifying the new set of semantics as the current set of semantics;

f) repeating steps c, d and e, until it is determined that no higher level grammar hierarchy exists; and

g) outputting the current set of semantics as indicative of a particular human behavior of the entity,

wherein each grammar level for each node generates outputs from the sensor data generated by each node, wherein the current set of semantics for each node is propagated across the sensor network; and

wherein each grammar hierarchy level computes a set of probabilities for each human behavior such that lower level grammar hierarchies infer simple human behaviors that allow for higher level grammar hierarchies to infer higher order human behaviors that take place at a more macroscopic level.

38. The computer readable medium of claim 37, wherein each he sensor comprises a sensor network with at least one sensing modality.

39. The computer readable medium of claim 38, wherein the sensor data is related to a spatial position of the entity.

40. The computer readable medium of claim 39, wherein the sensor data is related to a time that the entity is at the spatial position.

41. The computer readable medium of claim 37, wherein the grammar hierarchies comprises hierarchies of probabilistic context free grammars.

42. The computer readable medium of claim 41, wherein the probabilistic context free grammars comprise spatial hierarchies.

43. The computer readable medium of claim 41, wherein the probabilistic context free grammars comprise spatio-temporal hierarchies.

44. The computer readable medium of claim 37, wherein the step of interpreting the sensor data according to the grammar hierarchy to produce a new set of semantics comprises:

assembling the sensor data into a sequence of sensor measurements;

converting the sequence of sensor measurements to a sequence of phonemes;

converting the sequence of phonemes into a plurality of sequences of human behaviors;

computing a sequence probability for each sequence of human behaviors based on a probability associated with each human behavior; and

selecting the sequence of human behaviors with the highest sequence probability as the new set of semantics.

45. The computer readable medium of claim 37, wherein the step of interpreting the sensor data according to the grammar hierarchy to produce a new set of semantics comprises:

assembling the sensor data into a sequence of sensor measurements and times;

converting the sequence of sensor measurements and times into a plurality of sequences of time durations at spatial positions;

computing a sequence probability for each sequence of time durations at spatial positions based on a probability associated with each duration of time at a spatial position; and

selecting the sequence of durations of times at spatial positions with the highest sequence probability as the new set of semantics.

46. The computer readable medium of claim 37, wherein repeating steps c, d, and e, comprises:

converting the current set of semantics into a plurality of sequences of human sub behaviors;

computing a sequence probability for each sequence of human sub-behaviors based on a probability associated with each human sub-behavior; and

selecting the sequence of human sub-behaviors with the highest sequence probability as the new set of semantics.