Method for computing all occurrences of a compound event from occurrences of primitive events

US 6,941,290 B2
Filed: 07/30/2001
Issued: 09/06/2005
Est. Priority Date: 11/10/2000
Status: Active Grant

First Claim

Patent Images

1. A computer implemented method for recognizing compound events depicted in video sequences, said compound events being determined from occurrences of primitive events depicted in the video sequences, wherein the compound events are defined as a combination of the primitive events, the method comprising the steps of:

(a) defining primitive event types, said primitive event types including;

x=y;

Supported(x);

RigidlyAttached(x, y);

Supports(x, y);

Contacts(x, y); and

Attached(x, y);

(b) defining combinations of the primitive event types as a compound event type, said compound event type being one of;

PickUp(x,y,z);

PutDown(x,y,z);

Stack(w,x,y,z);

Unstack(w,x,y,z);

Move(w,x,y,z);

Assemble(w,x,y,z); and

Disassemble(w,x,y,z);

(c) inputting, a series of video sequences, said video sequences depicting primitive event occurrences, such occurrences being specified as a set of temporal intervals over which a given primitive event type is true; and

(d) determining, the compound event occurrences, such occurrences being specified as the set of temporal intervals over which the compound event type is true, wherein the sets of temporal intervals in steps (c) and (d) are specified as smaller sets of spanning intervals, each spanning interval representing a set of all sub-intervals over which the primitive event type holds and wherein the spanning intervals take the form _α[_γ[i,j]_δ,_ε[k,l]_ζ]_β, where α

, β

, γ

, δ

, ε

, and ζ

are Boolean values, i,j,k, and l are real numbers, _α[_γ[i, j]_δ,_ε[k,l]_ζ]_β represents the set of all intervals _α[p,q]_βwhere i≦

_γp≦

_δj and k≦

_εq≦

_ζl, _α[p,q]_β represents the set of all points r, where p≦

_αr≦

_βq, and x≦

_θy means x≦

y when θ

is true and x<

y when θ

is false.

View all claims

3 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A method for computing all occurrences of a compound event from occurrences of primitive events where the compound event is a defined combination of the primitive events. The method includes the steps of: (a) defining primitive event types; (b) defining combinations of the primitive event types as a compound event type; (c) inputting the primitive event occurrences, such occurrences being specified as the set of temporal intervals over which a given primitive event type is true; and (d) computing the compound event occurrences, such occurrences being specified as the set of temporal intervals over which the compound event type is true, where the sets of temporal intervals in steps (c) and (d) are specified as smaller sets of spanning intervals, each spanning interval representing a set of intervals.

18 Citations

View as Search Results

5 Claims

1. A computer implemented method for recognizing compound events depicted in video sequences, said compound events being determined from occurrences of primitive events depicted in the video sequences, wherein the compound events are defined as a combination of the primitive events, the method comprising the steps of:
- (a) defining primitive event types, said primitive event types including;
  
  x=y;
  
  Supported(x);
  
  RigidlyAttached(x, y);
  
  Supports(x, y);
  
  Contacts(x, y); and
  
  Attached(x, y);
  
  (b) defining combinations of the primitive event types as a compound event type, said compound event type being one of;
  
  PickUp(x,y,z);
  
  PutDown(x,y,z);
  
  Stack(w,x,y,z);
  
  Unstack(w,x,y,z);
  
  Move(w,x,y,z);
  
  Assemble(w,x,y,z); and
  
  Disassemble(w,x,y,z);
  
  (c) inputting, a series of video sequences, said video sequences depicting primitive event occurrences, such occurrences being specified as a set of temporal intervals over which a given primitive event type is true; and
  
  (d) determining, the compound event occurrences, such occurrences being specified as the set of temporal intervals over which the compound event type is true, wherein the sets of temporal intervals in steps (c) and (d) are specified as smaller sets of spanning intervals, each spanning interval representing a set of all sub-intervals over which the primitive event type holds and wherein the spanning intervals take the form _α[_γ[i,j]_δ,_ε[k,l]_ζ]_β, where α
  
  , β
  
  , γ
  
  , δ
  
  , ε
  
  , and ζ
  
  are Boolean values, i,j,k, and l are real numbers, _α[_γ[i, j]_δ,_ε[k,l]_ζ]_β represents the set of all intervals _α[p,q]_βwhere i≦
  
  _γp≦
  
  _δj and k≦
  
  _εq≦
  
  _ζl, _α[p,q]_β represents the set of all points r, where p≦
  
  _αr≦
  
  _βq, and x≦
  
  _θy means x≦
  
  y when θ
  
  is true and x<
  
  y when θ
  
  is false.
- View Dependent Claims (2, 3, 4, 5)
- - 2. The method according to claim 1, wherein the compound event type in step (b) is specified as an expression in temporal logic.
  - 3. The method according to claim 2, wherein the temporal logic expressions are constructed the logical connectives ∀
    - , ∃
      
      , , _R, ⋄
      
      _R, and , where R ranges over sets of relations between one-dimensional intervals.
  - 4. The method according to claim 3, wherein the relations are =, <
    - , >
      
      , m, mi, o, oi, s, si, f, fi, d, and di.
  - 5. The method according to claim 4, wherein the compound event occurrences are computed through the use of the following set of equations:
    - $ɛ (M, p (c_{1}, \dots, c_{n})) \underset{\underline{_}}{Δ} {i | p (c_{1}, \dots, c_{n}) @ i \in M}$ $ɛ (M, Φ ⋁ Ψ) \underset{\underline{_}}{Δ} ɛ (M, Φ) ⋃ ɛ (M, Ψ)$ $ɛ (M, \forall x Φ) \underset{\underline{_}}{Δ} ⋃_{i_{1} \in ɛ (M, Φ [x;= c_{1}])} \dots ⋃_{i_{1} \in ɛ (M, Φ [x;= c_{n}])} i_{1} ⋂ \dots ⋂ i_{n}$ $where C (M) = {c_{1}, \dots, c_{n}}$ $ɛ (M, \exists x Φ) \underset{\underline{_}}{Δ} ⋃_{c \in C (M)} ɛ (M, Φ [x;= c])$ $ɛ (M, ⫬ Φ) \underset{\underline{_}}{Δ} ⋃_{i_{1}^{'} \in ⫬_{1}} \dots ⋃_{i_{n}^{'} \in ⫬_{n}} i_{1}^{'} ⋂ \dots ⋂ i_{n}^{'}$ $where ɛ (M, Φ) = {i_{1}, \dots, i_{n}}$ $ɛ (M, Φ ⋀_{R} Ψ) \underset{\underline{_}}{Δ} ⋃_{i \in ɛ (M, Φ)} ⋃_{j \in ɛ (M, Ψ)} ⋃_{r \in R} ℐ (i, r, j)$ $ɛ (M, ◇_{R}, Φ) \underset{\underline{_}}{Δ} ⋃_{i \in ɛ (M, Φ)} ⋃_{r \in R} ?? (r, i) where, 〈_{α} {[_{γ} {{[i, j]}_{δ, ε} [k, l]}_{ζ}]}_{β} 〉 \underset{\underline{_}}{Δ} {\begin{matrix} {_{α} {[_{γ^{'}} {{[i, j^{'}]}_{δ^{'}, ε^{'}} [k^{'}, l]}_{ζ^{'}}]}_{β}} \\ where j^{'} = \min (j, l) \\ k^{'} = \max (k, i) \\ γ^{'} = γ ⋀ i \neq - \infty \\ δ^{'} = δ ⋀ \min (j, l) \neq \infty ⋀ (j < l ⋁ ζ ⋀ α ⋀ β) \\ ε^{'} = ε ⋀ \max (k, i) \neq - \infty ⋀ (k > i ⋁ γ ⋀ β ⋀ α) \\ ζ^{'} = ζ ⋀ l \neq \infty \\ when i \leq j^{'} ⋀ k^{'} \leq l ⋀ \\ [i = j^{'} \to (γ^{'} ⋀ δ^{'})] ⋀ [k^{'} = l \to (ε^{'} ⋀ ζ^{'})] ⋀ \\ [i = l \to (α ⋀ β)] ⋀ \\ i \neq \infty ⋀ j^{'} \neq - \infty ⋀ k^{'} \neq \infty ⋀ l \neq - \infty \\ {} otherwise \end{matrix} {α_{1} [_{y_{1}} {{[i_{1}, j_{1}]}_{δ_{1}, ε_{1}} [k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}} ⋂_{α_{2}} {[_{γ_{2}} {{[i_{2}, j_{2}]}_{δ_{2}, ε_{2}} [k_{2}, l_{2}]}_{ζ_{2}}]}_{β_{2}} \underset{\underline{_}}{Δ} 〈_{α_{1}} {[_{γ} {{[\max (i_{1}, i_{2}), \min (j_{1}, j_{2})]}_{δ, ε} [\max (k_{1}, k_{2}), \min (l_{1}, l_{2})]}_{ζ}]}_{β_{1}} 〉$ $\begin{matrix} where γ = {\begin{matrix} γ_{1} & i_{1} > i_{2} \\ γ_{1} ⋀ γ_{2} & i_{1} = i_{2} \\ γ_{2} & i_{1} < i_{2} \end{matrix} \\ δ = {\begin{matrix} δ_{1} & j_{1} < j_{2} \\ δ_{1} ⋀ δ_{2} & j_{1} = j_{2} \\ δ_{2} & j_{1} > j_{2} \end{matrix} \\ ε = {\begin{matrix} ε_{1} & k_{1} > k_{2} \\ ε_{1} ⋀ ε_{2} & k_{1} = k_{2} \\ ε_{2} & k_{1} < k_{2} \end{matrix} \\ ζ = {\begin{matrix} ζ_{1} & l_{1} < l_{2} \\ ζ_{1} ⋀ ζ_{2} & l_{1} = l_{2} \\ ζ_{2} & l_{1} > l_{2} \end{matrix} \end{matrix}$ $when α_{1} = α_{2} ⋀ β_{1} = β_{2}$ ${} otherwise$ $⫬_{α} {[_{γ} {[i, j]}_{δ},_{ε} {[k, l]}_{ζ}]}_{β} \underset{\underline{_}}{Δ} (\begin{matrix} 〈_{α} {[_{T} {[- \infty, \infty]}_{T},_{T} {[- \infty, k]}_{⫬ ε}]}_{β} 〉 ⋃ \\ 〈_{α} {[_{T} {[- \infty, \infty]}_{T},_{⫬ ζ} {[l, \infty]}_{T}]}_{β} 〉 ⋃ \\ 〈_{α} {[_{T} {[- \infty, i]}_{⫬ γ},_{T} {[- \infty, \infty]}_{T}]}_{β} 〉 ⋃ \\ 〈_{α} {[_{⫬ δ} {[j, \infty]}_{T},_{T} {[- \infty, \infty]}_{T}]}_{β} 〉 ⋃ \\ 〈_{⫬ α} {[_{T} {[- \infty, \infty]}_{T},_{T} {[- \infty, \infty]}_{T}]}_{β} 〉 ⋃ \\ 〈_{α} {[_{T} {[- \infty, \infty]}_{T},_{T} {[- \infty, \infty]}_{T}]}_{⫬ β} 〉 ⋃ \\ 〈_{⫬ α} {[_{T} {[- \infty, \infty]}_{T},_{T} {[- \infty, \infty]}_{T}]}_{⫬ β} 〉 \end{matrix})$ $SPAN (_{α_{1}} {{[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{\in_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}, α_{2}} [_{γ_{2}} {[i_{2}, j_{2}]}_{δ_{2}},_{\in_{2}} {[k_{2}, l_{2}]}_{ζ_{2}}]}_{β_{2}}) \underset{\underline{_}}{Δ} (\begin{matrix} 〈_{α_{1}} {[_{γ_{1}} {[i_{1}, j]}_{δ},_{\in} {[k, l_{1}]}_{ζ_{1}}]}_{β_{1}} 〉 ⋃ \\ 〈_{α_{1}} {[_{γ_{1}} {[i_{1}, j]}_{δ},_{\in} {[k, l_{2}]}_{ζ_{2}}]}_{β_{2}} 〉 ⋃ \\ 〈_{α_{2}} {[_{γ_{2}} {[i_{2}, j]}_{δ},_{\in} {[k, l_{1}]}_{ζ_{1}}]}_{β_{1}} 〉 ⋃ \\ 〈_{α} {[_{γ_{2}} {[i_{2}, j]}_{δ},_{\in} {[k, l_{2}]}_{ζ_{2}}]}_{β_{2}} 〉 \end{matrix})$ $where$ $j = \min (j_{1}, j_{2})$ $k = \max (k_{1}, k_{2})$ $δ = [(δ_{1} ⋀ j_{1} \leq j_{2}) ⋁ (δ_{2} ⋀ j_{1} \geq j_{2})]$ $ε = [(ε_{1} ⋀ k_{1} \leq k_{2}) ⋁ (ε_{2} ⋀ k_{1} \geq k_{2})]$ $?? (=, 1) \underset{\underline{_}}{Δ} {i}$ $(=, i) \underset{\underline{_}}{Δ} {i}$ $(<,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2}, β_{2} \in (T, F)} 〈_{α_{2}} {[_{⫬ β_{1} ⋀ ⫬ α_{2} ⋀ \in_{1}} {{[k_{1}, \infty]}_{T, T} [- \infty, \infty]}_{T}]}_{β_{2}} 〉$ $(>,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2}, β_{2} \in {T, F}} 〈_{α_{2}} {[_{T} {{[- \infty, \infty]}_{T, T} [- \infty, j_{1}]}_{⫬ α_{1} ⋀ ⫬ β_{2} ⋀ δ_{1}}]}_{β_{2}} 〉$ $(m,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{β_{2} \in {T, F}} 〈_{⫬ β_{1}} {[_{\in_{1} {{[k_{1}, l_{1}]}_{ζ_{1}, T} [- \infty, \infty]}_{T}}]}_{β_{2}} 〉$ $(mi,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2} \in {T, F}} 〈_{α_{2}} {[_{T} {{[- \infty, \infty]}_{T, γ_{1}} [i_{1}, j_{1}]}_{δ_{1}}]}_{⫬ α_{1}} 〉$ $(o,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2}, β_{2} \in {T, F}} 〈_{α_{2}} {[_{α_{1} ⋀ ⫬ α_{2} ⋀ γ_{1}} {{[i_{1}, l_{1}]}_{β_{1} ⋀ α_{2} ⋀ ζ_{1}, ⫬ β_{1} ⋀ β_{2}, \in_{1}} [k_{1}, \infty]}_{T}]}_{β_{2}} 〉$ $(oi,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2}, β_{2} \in {T, F}} 〈_{α_{2}} {[_{T} {{[- \infty, j_{1}]}_{⫬ α_{1} ⋀ α_{2} ⋀ δ_{1}, α_{1} ⋀ β_{2} ⋀ γ_{1}} [i_{1}, l_{1}]}_{β_{1} ⋀ β_{2} ⋀ ζ_{1}}]}_{β_{2}} 〉$ $(s,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{β_{2} \in {T, F}} 〈_{α_{1}} {[_{γ_{1}} {{[i_{1}, j_{1}]}_{δ_{1}, ⫬ β_{1} ⋀ β_{2} ⋀ \in_{1}} [k_{1}, \infty]}_{T}]}_{β_{2}} 〉$ $(si,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{β_{2} \in {T, F}} 〈_{α_{1}} {[_{γ_{1}} {{[i_{1}, j_{1}]}_{δ_{1}, T} [- \infty, l_{1}]}_{β_{1} ⋀ ⫬ β_{2} ⋀ ζ_{1}}]}_{β_{2}} 〉$ $(f,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2} ε {T, F}} 〈_{α_{2}} {[_{T} {[- \infty, j_{1}]}_{⫬ α_{1} ⋀ α_{2} ⋀ δ_{1}},_{\in_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}} 〉$ $(fi,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2} \in {T, F}} 〈_{α_{2}} {[_{α_{1} ⋀ ⫬ α_{2} ⋀ γ_{1}} {{[i_{1}, \infty]}_{T, \in_{1}} [k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}} 〉$ $(d,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2}, β_{2} \in {T, F}} 〈_{α_{2}} {[_{T} {{[- \infty, j_{1}]}_{⫬ α_{1} ⋀ α_{2} ⋀ δ_{1}, ⫬ β_{1} ⋀ β_{2} ⋀ \in_{1}} [k_{1}, \infty]}_{T}]}_{β_{2}} 〉$ $(di,_{α_{1}} {[_{γ_{1}} {[i_{1}, j_{1}]}_{δ_{1}},_{ε_{1}} {[k_{1}, l_{1}]}_{ζ_{1}}]}_{β_{1}}) \underset{\underline{_}}{Δ} ⋃_{α_{2}, β_{2} \in {T, F}} 〈_{α_{2}} {[_{α_{1} ⋀ ⫬ α_{2} ⋀ γ_{1}} {{[i_{1}, \infty]}_{T, T} [- \infty, l_{1}]}_{β_{1} ⋀ ⫬ β_{2} ⋀ ζ_{1}}]}_{β_{2}} 〉$ $and, (i, r, j) \underset{\underline{_}}{Δ} ⋃_{i^{'} \in ?? (r^{- 1}, j)} ⋃_{i^{'} \in i^{'} ⋂ i} ⋃_{j^{'} \in (r, i)} ⋃_{j^{'} \in j^{'} ⋂ j} SPAN (i^{′′}, j^{′′}) .$

Specification

Resources

Litigation Campaign Assessment

Current Assignee
NEC Corporation
Original Assignee
NEC Laboratories America Inc (NEC Corporation)
Inventors
Siskind, Jeffrey Mark
Primary Examiner(s)
Knight, Anthony
Assistant Examiner(s)
Bell, Meltin

Application Number

US09/916,249
Publication Number

US 20020138458A1
Time in Patent Office

1,499 Days
Field of Search

706/25, 706/45, 706/58, 706/49, 706/53, 706/56, 706/57, 704/251
US Class Current

706/58
CPC Class Codes

G06V 20/52 Surveillance or monitoring ...

Method for computing all occurrences of a compound event from occurrences of primitive events

First Claim

3 Assignments

0 Petitions

Accused Products

Abstract

18 Citations

5 Claims

Specification

Solutions

Use Cases

Quick Links

Method for computing all occurrences of a compound event from occurrences of primitive events

First Claim

3 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

18 Citations

5 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links