Method for estimating optical flow

US 6,507,661 B1
Filed: 09/08/1999
Issued: 01/14/2003
Est. Priority Date: 04/20/1999
Status: Expired due to Term

First Claim

Patent Images

1. A method for estimating the optical flow between a plurality of images, the method comprising the steps of:

(a) obtaining a motion orientation component, including the steps of;

creating a first graph G₁using spatio-temporal derivatives of the plurality of images;

solving for a first maximum-flow in first graph G₁to thereby obtain a first minimum-cut therefrom; and

computing the motion orientation component from the first minimum-cut;

(b) obtaining a motion magnitude component, including the steps of;

creating a second graph G₂using spatio-temporal derivatives of the plurality of images and the motion orientation component;

solving for a second maximum-flow in second graph G₂to thereby obtain a second minimum-cut therefrom; and

computing the motion magnitude component from the second minimum-cut;

whereby the motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A method for estimating the optical flow between a plurality of images is provided. The method includes obtaining a motion orientation component and a motion magnitude component. Determining the motion orientation component includes creating, a first graph using spatio-temporal derivatives of the plurality of images, solving for a first maximum-flow in the first graph to thereby obtain a first minimum-cut therefrom, and computing the motion orientation component from the first minimum-cut. Determining the motion magnitude component includes creating a second graph using spatio-temporal derivatives of the plurality of images and the motion orientation component, solving for a second maximum-flow in the second graph to thereby obtain a second minimum-cut therefrom, and computing the motion magnitude component from the second minimum-cut. The motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images. The method properly models errors in the measurement of image derivatives while enforcing a brightness constraint, and efficiently provides a globally optimal solution to the optical flow in the context of the model.

Citations

15 Claims

1. A method for estimating the optical flow between a plurality of images, the method comprising the steps of:
- (a) obtaining a motion orientation component, including the steps of;
  
  creating a first graph G₁using spatio-temporal derivatives of the plurality of images;
  
  solving for a first maximum-flow in first graph G₁to thereby obtain a first minimum-cut therefrom; and
  
  computing the motion orientation component from the first minimum-cut;
  
  (b) obtaining a motion magnitude component, including the steps of;
  
  creating a second graph G₂using spatio-temporal derivatives of the plurality of images and the motion orientation component;
  
  solving for a second maximum-flow in second graph G₂to thereby obtain a second minimum-cut therefrom; and
  
  computing the motion magnitude component from the second minimum-cut;
  
  whereby the motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
- - 2. The method of claim 1, wherein the first graph G₁is created by deriving an edge capacity function from a cost function of:
    - $\min_{θ} \sum_{i \in S} \sum_{i^{'} \in N_{i}} β_{1} \langle θ_{i} - θ_{i^{'}} \rangle - \sum_{i \in S} \ln (P (θ  I_{di}))$
3. The method of claim 2, wherein the neighborhood is a 4-neighborhood.
4. The method of claim 2, wherein the conditional probability distribution P(θ
- |I_di) is [P(θ
  
  |I_d⁰)·
  
  P(I_d⁰|I_d)], wherein P(θ
  
  |I_d⁰) is a model of motion orientation and P(I_d⁰|I_d) is a model of error in measurement of the image derivatives, and wherein;
5. The method of claim 2, wherein the second graph G₂is created by deriving an edge capacity function from a cost function of:
- $\min_{m} \sum_{i \in S} \sum_{i^{'} \in N_{i}} β_{2} \langle m_{i} - m_{i^{'}} \rangle - \sum_{i \in S} \ln (P (m \langle θ_{si}, I_{di}))$ wherein S is a set of all pixels, N_iis a set of all pixels that are in a neighborhood of pixel i, β
  
  ₂is an arbitrary, nonnegative smoothness constant, m_iis magnitude of pixel i, I_dis a measured image derivative, and P(m|θ
  
  _si, I_di) is the conditional probability of a magnitude m given a known orientation θ
  
  _siand an image derivative I_di.
6. The method of claim 5, wherein a conditional probability distribution P(m|θ
- _si, I_di) is derived from combining the conditional probability distribution P(θ
  
  |I_di) and a constant brightness assumption.
7. The method of claim 1, wherein the second graph G₂is created by deriving an edge capacity function from a cost function of:
- $\min_{m} \sum_{i \in S} \sum_{i^{'} \in N_{i}} β_{2} \langle m_{i} - m_{i^{'}} \rangle - \sum_{i \in S} \ln (P (m \langle θ_{si}, I_{di}))$ wherein S is a set of all pixels, N_iis a set of all pixels that are in a neighborhood of pixel i, β
  
  ₂is an arbitrary, nonnegative smoothness constant, m_iis magnitude of pixel i, I_dis a measured image derivative, and P(m|θ
  
  _si, I_di) is the conditional probability of a magnitude m given a known orientation θ
  
  _siand an image derivative I_di.
8. The method of claim 7, wherein the neighborhood is a 4-neighborhood.

9. A method for estimating the optical flow between a plurality of images, the method comprising the steps of:
- (a) obtaining a motion orientation component, including the steps of;
  
  creating a first graph G₁using spatio-temporal derivatives of the plurality of images by deriving an edge capacity function from a cost function of;
  
  $\min_{θ} \sum_{i \in S} \sum_{i^{'} \in N_{i}} β_{1} \langle θ_{i} - θ_{i^{'}} \rangle - \sum_{i \in S} \ln (P (θ \langle I_{di}))$
  
  wherein S is a set of all pixels, N_iis a set of all pixels that are in a neighborhood of pixel i, β
  
  ₁is an arbitrary, nonnegative smoothness constant, θ
  
  _iis orientation of pixel i, I_dis a measured image derivative, and P(θ
  
  |I_di) is the conditional probability of an orientation θ
  
  given an image derivative I_di;
  
  solving for a first maximum-flow in first graph G₁to thereby obtain a first minimum-cut therefrom; and
  
  computing the motion orientation component from the first minimum-cut;
  
  (b) obtaining a motion magnitude component, including the steps of;
  
  creating a second graph G₂using spatio-temporal derivatives of the plurality of images and the motion orientation component;
  
  solving for a second maximum-flow in second graph G₂to thereby obtain a second minimum-cut therefrom; and
  
  computing the motion magnitude component from the second minimum-cut;
  
  whereby the motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images.
- View Dependent Claims (10, 11, 12, 13)
- - 10. The method of claim 9, wherein the neighborhood is a 4-neighborhood.
  - 11. The method of claim 9, wherein the conditional probability distribution P(θ
    - |I_di) is [P(θ
      
      |I_d⁰)·
      
      P(I_d⁰|I_d)], wherein P(θ
      
      |I_d⁰) is a model of motion orientation and P(I_d⁰|I_d) is a model of error in measurement of the image derivatives, and wherein;
12. The method of claim 9, wherein the second graph G₂is created by deriving an edge capacity function from a cost function of:
- $\min_{m} \sum_{i \in S} \sum_{i^{'} \in N_{i}} β_{2} \langle m_{i} - m_{i^{'}} \rangle - \sum_{i \in S} \ln (P (m \langle θ_{si}, I_{di}))$ wherein S is a set of all pixels, N_iis a set of all pixels that are in a neighborhood of pixel i, β
  
  ₂is an arbitrary, nonnegative smoothness constant, m_iis magnitude of pixel i, I_dis a measured image derivative, and P(m|θ
  
  _si, I_di) is the conditional probability of a magnitude m given a known orientation θ
  
  _siand an image derivative I_di.
13. The method of claim 12, wherein a conditional probability distribution P(m|θ
- _si, I_di) is derived from combining the conditional probability distribution P(θ
  
  |I_di) and a constant brightness assumption.

14. A method for estimating the optical flow between a plurality of images, the method comprising the steps of:
- (a) obtaining a motion orientation component, including the steps of;
  
  creating a first graph G₁using spatio-temporal derivatives of the plurality of images;
  
  solving for a first maximum-flow in first graph G₁to thereby obtain a first minimum-cut therefrom; and
  
  computing the motion orientation component from the first minimum-cut;
  
  (b) obtaining a motion magnitude component, including the steps of;
  
  creating a second graph G₂using spatio-temporal derivatives of the plurality of images and the motion orientation component by deriving an edge capacity function from a cost function of;
  
  $\min_{m} \sum_{i \in S} \sum_{i^{'} \in N_{i}} β_{2} \langle m_{i} - m_{i^{'}} \rangle - \sum_{i \in S} \ln (P (m \langle θ_{si}, I_{di}))$
  
  wherein S is a set of all pixels, N_iis a set of all pixels that are in a neighborhood of pixel i, β
  
  ₂is an arbitrary, nonnegative smoothness constant, m_iis magnitude of pixel i, I_dis a measured image derivative, and P(m|θ
  
  _si, I_di) is the conditional probability of a magnitude m given a known orientation θ
  
  _siand an image derivative I_di;
  
  solving for a second maximum-flow in second graph G₂to thereby obtain a second minimum-cut therefrom; and
  
  computing the motion magnitude component from the second minimum-cut;
  
  whereby the motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images.
- View Dependent Claims (15)
- - 15. The method of claim 14, wherein the neighborhood is a 4-neighborhood.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
NEC Corporation
Original Assignee
NEC Research Institute, Inc. (NEC Corporation)
Inventors
Roy, Sebastien
Primary Examiner(s)
Boudreau, Leo
Assistant Examiner(s)
AZARIAN, SEYED H

Application Number

US09/391,732
Time in Patent Office

1,224 Days
Field of Search

382/107, 382/100, 382/293, 382/241, 382/302, 382/103, 382/238, 382/236, 382/199, 382/203, 382/276, 382/230, 348/155, 348/699, 348/700, 348/586, 348/625, 348/620
US Class Current

382/107
CPC Class Codes

G06T 7/269 using gradient-based methods

Method for estimating optical flow

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

Citations

15 Claims

Specification

Solutions

Use Cases

Quick Links

Method for estimating optical flow

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

Citations

15 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links