JP2000306108A - オプティカルフロー推定方法 - Google Patents
オプティカルフロー推定方法Info
- Publication number
- JP2000306108A JP2000306108A JP2000022967A JP2000022967A JP2000306108A JP 2000306108 A JP2000306108 A JP 2000306108A JP 2000022967 A JP2000022967 A JP 2000022967A JP 2000022967 A JP2000022967 A JP 2000022967A JP 2000306108 A JP2000306108 A JP 2000306108A
- Authority
- JP
- Japan
- Prior art keywords
- optical flow
- flow
- graph
- image
- motion
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/20—Analysis of motion
- G06T7/269—Analysis of motion using gradient-based methods
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Image Analysis (AREA)
Abstract
(57)【要約】
【課題】 複数画像間のオプティカルフローを有効かつ
正確に推定する。 【解決手段】 先ず、複数画像の空間時間導関数を用い
て第１のグラフＧ1を作成し（ステップ４０２）、第１
のグラフＧ1で第１の最大フローの解を得ることでそれ
から第１の最小カットを得て（ステップ４０４）、その
第１の最小カットから運動方向成分４０８を計算する
（ステップ４０６）。次に、複数画像の空間時間導関数
を用いて第２のグラフＧ2を作成し（ステップ４１
０）、その第２のグラフＧ2で第２の最大フローの解を
得ることでそれから第２の最小カットを得て（ステップ
４１２）、その第２の最小カットから運動速度成分４１
６を計算する（ステップ４１４）。運動方向成分４０８
と運動速度成分４１６とを合わせて、複数画像間のオプ
ティカルフローが推定される。
正確に推定する。 【解決手段】 先ず、複数画像の空間時間導関数を用い
て第１のグラフＧ1を作成し（ステップ４０２）、第１
のグラフＧ1で第１の最大フローの解を得ることでそれ
から第１の最小カットを得て（ステップ４０４）、その
第１の最小カットから運動方向成分４０８を計算する
（ステップ４０６）。次に、複数画像の空間時間導関数
を用いて第２のグラフＧ2を作成し（ステップ４１
０）、その第２のグラフＧ2で第２の最大フローの解を
得ることでそれから第２の最小カットを得て（ステップ
４１２）、その第２の最小カットから運動速度成分４１
６を計算する（ステップ４１４）。運動方向成分４０８
と運動速度成分４１６とを合わせて、複数画像間のオプ
ティカルフローが推定される。
Description
【０００１】
【発明の属する技術分野】本発明は、機械に人間の視覚
系を持たせることを目的とするマシンビジョン（機械視
覚）の分野に関するものであり、特に複数の画像間での
オプティカルフローを有効に推定する方法に関する。
系を持たせることを目的とするマシンビジョン（機械視
覚）の分野に関するものであり、特に複数の画像間での
オプティカルフローを有効に推定する方法に関する。
【０００２】
【従来の技術】運動推定は、ロボット工学（ナビゲーシ
ョンおよび障害物回避を含む）、自律走行自動車、医学
画像解析（血管造影等の非剛直運動を含む）等の多くの
種類のマシンビジョン処理の際に生じる重要な問題であ
る。２個以上の時系列連続画像間の動きが小さい場合、
２個の異なる像間の２次元の動きベクトル場として定義
されるオプティカルフローによって説明される。オプテ
ィカルフローは、画像中の対象物が、どのように運動
し、どこに向かって運動し、どの程度の速さであるかを
示すものである。
ョンおよび障害物回避を含む）、自律走行自動車、医学
画像解析（血管造影等の非剛直運動を含む）等の多くの
種類のマシンビジョン処理の際に生じる重要な問題であ
る。２個以上の時系列連続画像間の動きが小さい場合、
２個の異なる像間の２次元の動きベクトル場として定義
されるオプティカルフローによって説明される。オプテ
ィカルフローは、画像中の対象物が、どのように運動
し、どこに向かって運動し、どの程度の速さであるかを
示すものである。
【０００３】輝度一定の仮定（Constant Brightness As
sumption：以下ＣＢＡと称する）下では、画素の動きは
１次元方向に制限することができる。しかしながら、１
個の画素におけるフローには２成分（すなわち、方向
（向きおよび角度）と絶対値（すなわち速度））が存在
するため、オプティカルフロー推定は固有の困難さを有
する問題である。従って、その問題に対処すべく、いく
つかの試みが行われてきた。
sumption：以下ＣＢＡと称する）下では、画素の動きは
１次元方向に制限することができる。しかしながら、１
個の画素におけるフローには２成分（すなわち、方向
（向きおよび角度）と絶対値（すなわち速度））が存在
するため、オプティカルフロー推定は固有の困難さを有
する問題である。従って、その問題に対処すべく、いく
つかの試みが行われてきた。
【０００４】ほとんどの先行技術が、フロー場を「規則
化」することで、すなわちフロー場に対して何らかの形
の平滑化を行うことで、その問題を克服するものである
（Horn et al., "Determining Optical Flow, "Artific
ial Intelligence, Vol.17,pp.185-203 (1981); H.Nage
l et al., "On The Estimation Of Optical Flow: Rela
tions Between Different Approaches And Some New Re
sults," ArtificialIntelligence, Vol.33, pp.299-324
(1987)参照）。ＣＢＡはまた、２個の画像間の最小二
乗差を最小化することでフロー場を推定するエネルギー
最小化とすることもできる（P.Anandan, "A Computatio
nal Framework And An Algorithm ForThe Measurement
Of Structure From Motion, "Int'l Journal of Comput
er Vision, Vol.2, pp.283-310 (1989); A.Singh, Opti
c Flow Computation: A Unified Perspective, IEEE Co
mputer Society Press (1992)参照）。オプティカルフ
ローはまた、小さい画像区画全体にわたって局所輝度を
分割することで計算することもできる（B.Lucas et a
l., "An Iterative Image Registration TechniqueWith
An Application To Stereo Vision, "DARPA IU Worksh
op, pp.121-130 (1981)参照）。平滑化の問題には、パ
ラメータ化された画像全体の運動モデルを適合化するこ
とで対処することもできる（S.Srinivasan et al., "Op
tical Flow Using Overlapped Basis Functions For So
lving Global Motion Problems," Proceedings of Euro
pean Conference on Computer Vision, Freburg, Germa
ny, pp.288-304 (1988)参照）。
化」することで、すなわちフロー場に対して何らかの形
の平滑化を行うことで、その問題を克服するものである
（Horn et al., "Determining Optical Flow, "Artific
ial Intelligence, Vol.17,pp.185-203 (1981); H.Nage
l et al., "On The Estimation Of Optical Flow: Rela
tions Between Different Approaches And Some New Re
sults," ArtificialIntelligence, Vol.33, pp.299-324
(1987)参照）。ＣＢＡはまた、２個の画像間の最小二
乗差を最小化することでフロー場を推定するエネルギー
最小化とすることもできる（P.Anandan, "A Computatio
nal Framework And An Algorithm ForThe Measurement
Of Structure From Motion, "Int'l Journal of Comput
er Vision, Vol.2, pp.283-310 (1989); A.Singh, Opti
c Flow Computation: A Unified Perspective, IEEE Co
mputer Society Press (1992)参照）。オプティカルフ
ローはまた、小さい画像区画全体にわたって局所輝度を
分割することで計算することもできる（B.Lucas et a
l., "An Iterative Image Registration TechniqueWith
An Application To Stereo Vision, "DARPA IU Worksh
op, pp.121-130 (1981)参照）。平滑化の問題には、パ
ラメータ化された画像全体の運動モデルを適合化するこ
とで対処することもできる（S.Srinivasan et al., "Op
tical Flow Using Overlapped Basis Functions For So
lving Global Motion Problems," Proceedings of Euro
pean Conference on Computer Vision, Freburg, Germa
ny, pp.288-304 (1988)参照）。
【０００５】多くの先行技術による推定方法によれば、
コスト関数を最小化することで、輝度の制約と平滑化と
の間の均衡が得られる。それらの方法は、反復非線形法
に基づくものであるため、広域最小値に収束するとは限
らず、従って、局所最小値に収束する際に満足できる結
果を与えない。
コスト関数を最小化することで、輝度の制約と平滑化と
の間の均衡が得られる。それらの方法は、反復非線形法
に基づくものであるため、広域最小値に収束するとは限
らず、従って、局所最小値に収束する際に満足できる結
果を与えない。
【０００６】
【発明が解決しようとする課題】本発明の方法は、フロ
ー推定の問題を、マルコフランダム場（Markov RandomF
ield：ＭＲＦ」）の枠組みでのラベリング問題として公
式化することで、上記の制限を克服するものである。従
って本発明は、フロー場における不連続性を保持しなが
ら、高密度でノンパラメトリックなフローを解くもので
ある。
ー推定の問題を、マルコフランダム場（Markov RandomF
ield：ＭＲＦ」）の枠組みでのラベリング問題として公
式化することで、上記の制限を克服するものである。従
って本発明は、フロー場における不連続性を保持しなが
ら、高密度でノンパラメトリックなフローを解くもので
ある。
【０００７】ある種のＭＲＦでは、グラフ上での最大フ
ロー計算によって、正確な帰納的最大（Maximum A Post
eriori：ＭＡＰ）推定値を効率良く得ることができる。
最適であることが保証されていることから、この計算に
よって、局所最小解の問題が回避される。ＭＲＦ公式化
およびグラフ理論解を用いる最近の一部の方法につい
て、各種文献等にその例が記載されている（S.Roy et a
l., "A Maximum-Flow Formulation Of The n-Camera St
ereo Correspondence Problem," Int'l Conference on
Computer Vision, Mumbai, India, pp.492-499 (199
8)；ロイ（S.Roy）によって１９９７年１１月２６日に
出願された米国特許出願０８／９７８、８３４号（発明
の名称「Maximum Flow Method For Stereo Corresponde
nce」。）；H.Ishikawa et al., "Occlusions, Discont
inuities, and Epipolar Lines In Stereo," Proceedin
gs of European Conference on Computer Vision, Frei
burg, Germany, pp.232-237 (1998)；Y.Boykow et al.,
"Markov Random Fields With Efficient Approximatio
ns," Proceedings of IEEE Conference on Computer Vi
sion and Pattern Recognition, pp.648-655 (1998)参
照）。
ロー計算によって、正確な帰納的最大（Maximum A Post
eriori：ＭＡＰ）推定値を効率良く得ることができる。
最適であることが保証されていることから、この計算に
よって、局所最小解の問題が回避される。ＭＲＦ公式化
およびグラフ理論解を用いる最近の一部の方法につい
て、各種文献等にその例が記載されている（S.Roy et a
l., "A Maximum-Flow Formulation Of The n-Camera St
ereo Correspondence Problem," Int'l Conference on
Computer Vision, Mumbai, India, pp.492-499 (199
8)；ロイ（S.Roy）によって１９９７年１１月２６日に
出願された米国特許出願０８／９７８、８３４号（発明
の名称「Maximum Flow Method For Stereo Corresponde
nce」。）；H.Ishikawa et al., "Occlusions, Discont
inuities, and Epipolar Lines In Stereo," Proceedin
gs of European Conference on Computer Vision, Frei
burg, Germany, pp.232-237 (1998)；Y.Boykow et al.,
"Markov Random Fields With Efficient Approximatio
ns," Proceedings of IEEE Conference on Computer Vi
sion and Pattern Recognition, pp.648-655 (1998)参
照）。
【０００８】フロー推定における別の重要な問題は画像
導関数の計算である。画像は空間、時間および強度の次
元で識別されることから、空間時間導関数の離散的計算
の正確さには制限がある。この問題は、複雑な導関数フ
ィルターによってある程度解決される。実際には導関数
は、照明の変化、輝度の尺度および反射などの輝度一定
の仮定からの逸脱によっても信頼性が低下する。従っ
て、輝度の制約が、「真の」厳密な制約と考えるべきで
はない。この不確定性の考え方について説明するため、
本発明では、輝度の制約を確率的枠組みに入れる。オプ
ティカルフローの確率的解釈についての関連する例が、
シモンセリらの論文（E.Simoncelli et al, "Probabili
ty Distributions of Optical Flow,", Proceedings of
IEEE Conference on Computer Vision and Pattern Re
cognition, pp.310-315 (1991)）に記載されている。こ
の方法では、非確率的アプローチにおける問題の一部が
克服されているが、オプティカルフローの確率の非線形
特性について考慮されておらず、また画像導関数におけ
る誤差を適切に考慮せずに過度に単純化されたオプティ
カルフローモデルを用いているため充分な効果を得られ
るものではない。
導関数の計算である。画像は空間、時間および強度の次
元で識別されることから、空間時間導関数の離散的計算
の正確さには制限がある。この問題は、複雑な導関数フ
ィルターによってある程度解決される。実際には導関数
は、照明の変化、輝度の尺度および反射などの輝度一定
の仮定からの逸脱によっても信頼性が低下する。従っ
て、輝度の制約が、「真の」厳密な制約と考えるべきで
はない。この不確定性の考え方について説明するため、
本発明では、輝度の制約を確率的枠組みに入れる。オプ
ティカルフローの確率的解釈についての関連する例が、
シモンセリらの論文（E.Simoncelli et al, "Probabili
ty Distributions of Optical Flow,", Proceedings of
IEEE Conference on Computer Vision and Pattern Re
cognition, pp.310-315 (1991)）に記載されている。こ
の方法では、非確率的アプローチにおける問題の一部が
克服されているが、オプティカルフローの確率の非線形
特性について考慮されておらず、また画像導関数におけ
る誤差を適切に考慮せずに過度に単純化されたオプティ
カルフローモデルを用いているため充分な効果を得られ
るものではない。
【０００９】そこで、輝度の制約を行ないながら、画像
導関数の測定における誤差を適切にモデル化し、しかも
そのモデルの環境においてオプティカルフローに対する
画像全体の最適解を効率良く得られるオプティカルフロ
ーの推定方法が必要とされている。
導関数の測定における誤差を適切にモデル化し、しかも
そのモデルの環境においてオプティカルフローに対する
画像全体の最適解を効率良く得られるオプティカルフロ
ーの推定方法が必要とされている。
【００１０】従って本発明の目的は、複数画像間のオプ
ティカルフローを有効かつ正確に推定するオプティカル
フローの推定方法を提供することにある。
ティカルフローを有効かつ正確に推定するオプティカル
フローの推定方法を提供することにある。
【００１１】本発明の別の目的は、輝度一定の仮定の制
約を行ないながら、画像導関数の測定における誤差を適
切にモデル化するオプティカルフローの推定方法を提供
することにある。
約を行ないながら、画像導関数の測定における誤差を適
切にモデル化するオプティカルフローの推定方法を提供
することにある。
【００１２】本発明のさらに別の目的は、そのモデルの
環境下で、オプティカルフローに対する画像の全体的な
最適解を効率良く与えるオプティカルフローの推定方法
を提供することにある。
環境下で、オプティカルフローに対する画像の全体的な
最適解を効率良く与えるオプティカルフローの推定方法
を提供することにある。
【００１３】
【課題を解決するための手段】本発明によれば、複数の
画像間でのオプティカルフローを推定する方法が提供さ
れる。本発明のオプティカルフロー推定方法は、運動の
方向成分と運動速度成分を得るステップとから構成され
ている。運動方向成分を求める方法は、複数の画像の空
間時間導関数を用いて第１のグラフを作成するステップ
と、第１のグラフで第１の最大フローについて解を求め
ることで、それから第１の最小カットを得るステップ
と、第１の最小カットから運動方向成分を計算する段階
を行うステップとから構成される。また、運動速度成分
を求めるステップは、複数の画像の空間時間導関数およ
び前記運動方向成分を用いて第２のグラフを作成するス
テップと、第２のグラフで第２の最大フローについて解
を求めることで、それから第２の最小カットを得るステ
ップと、第２の最小カットから運動速度成分を計算する
段階を行うステップとから構成される。そして、運動方
向成分および運動速度成分とを組み合わせて、複数画像
間のオプティカルフローが推定される。本発明のオプテ
ィカルフロー推定方法は、輝度の制約を行ないながら、
画像導関数の測定における誤差を適切にモデル化し、そ
のモデルの環境において、オプティカルフローに対して
画像全体の最適解を効率良く提供するものである。
画像間でのオプティカルフローを推定する方法が提供さ
れる。本発明のオプティカルフロー推定方法は、運動の
方向成分と運動速度成分を得るステップとから構成され
ている。運動方向成分を求める方法は、複数の画像の空
間時間導関数を用いて第１のグラフを作成するステップ
と、第１のグラフで第１の最大フローについて解を求め
ることで、それから第１の最小カットを得るステップ
と、第１の最小カットから運動方向成分を計算する段階
を行うステップとから構成される。また、運動速度成分
を求めるステップは、複数の画像の空間時間導関数およ
び前記運動方向成分を用いて第２のグラフを作成するス
テップと、第２のグラフで第２の最大フローについて解
を求めることで、それから第２の最小カットを得るステ
ップと、第２の最小カットから運動速度成分を計算する
段階を行うステップとから構成される。そして、運動方
向成分および運動速度成分とを組み合わせて、複数画像
間のオプティカルフローが推定される。本発明のオプテ
ィカルフロー推定方法は、輝度の制約を行ないながら、
画像導関数の測定における誤差を適切にモデル化し、そ
のモデルの環境において、オプティカルフローに対して
画像全体の最適解を効率良く提供するものである。
【００１４】
【発明の実施の形態】次に、本発明の実施の形態につい
て詳細に説明する。
て詳細に説明する。
【００１５】本発明の実施形態について説明する前に、
本発明についての理解を深めるため、輝度の制約を行な
いながら画像導関数における誤差をモデル化する場合の
問題について説明および公式化する。 Ａ．問題についての公式化 輝度の制約は、画素の画像輝度が一定であると仮定して
得られる。その結果、空間時間座標に関する画素の強度
の全体的導関数はゼロである。従って、以下の式のよう
になる。
本発明についての理解を深めるため、輝度の制約を行な
いながら画像導関数における誤差をモデル化する場合の
問題について説明および公式化する。 Ａ．問題についての公式化 輝度の制約は、画素の画像輝度が一定であると仮定して
得られる。その結果、空間時間座標に関する画素の強度
の全体的導関数はゼロである。従って、以下の式のよう
になる。
【００１６】
【数６】 式中、Ｉx、ＩyおよびＩtは空間時間画像導関数であ
り、υx、υyは、ｘ方向およびｙ方向でのフロー成分で
ある。この制約は、直線の式を説明するものである（図
１（ａ）および図１（ｂ）参照）。図１（ａ）におい
て、斜線を施した「許容」領域は、法線ベクトルυnに
ついての全ての可能な運動を表している。図１（ｂ）に
おいて、法線ベクトルυnを中心とする斜線を施した半
円における全ての方向が同等の確率を有する。前述のよ
うに、輝度の制約は、画像導関数における固有の不確定
性によって緩和されるはずである。以下に説明するよう
に、ベイズ（Bayesian）の枠組みにおいて単純かつ直観
的な前提（すなわち、問題の解を得る前にわかっている
知見を表す、アプリオリ確率分布）を用いることで、Ｃ
ＢＡの有用なモデルを得ることができる。
り、υx、υyは、ｘ方向およびｙ方向でのフロー成分で
ある。この制約は、直線の式を説明するものである（図
１（ａ）および図１（ｂ）参照）。図１（ａ）におい
て、斜線を施した「許容」領域は、法線ベクトルυnに
ついての全ての可能な運動を表している。図１（ｂ）に
おいて、法線ベクトルυnを中心とする斜線を施した半
円における全ての方向が同等の確率を有する。前述のよ
うに、輝度の制約は、画像導関数における固有の不確定
性によって緩和されるはずである。以下に説明するよう
に、ベイズ（Bayesian）の枠組みにおいて単純かつ直観
的な前提（すなわち、問題の解を得る前にわかっている
知見を表す、アプリオリ確率分布）を用いることで、Ｃ
ＢＡの有用なモデルを得ることができる。
【００１７】便宜上のため、本明細書では、以下の表記
を用いる。空間導関数Ｉx、Ｉyを∇Ｉと称し、空間時間
導関数Ｉx、Ｉy、ＩtはＩdと称する。これらの画像導関
数はいかなる方法でも求めることができ、そのための多
くのアルゴリズムが公知である。ある画素でのフロー
は、υ、すなわちυ＝［υx、υy、１］と表記される。
を用いる。空間導関数Ｉx、Ｉyを∇Ｉと称し、空間時間
導関数Ｉx、Ｉy、ＩtはＩdと称する。これらの画像導関
数はいかなる方法でも求めることができ、そのための多
くのアルゴリズムが公知である。ある画素でのフロー
は、υ、すなわちυ＝［υx、υy、１］と表記される。
【００１８】図１（ａ）および図１（ｂ）に示したよう
に、Ｉd 0と表記される真の空間時間導関数は、動きベク
トルυを、Ｉd 0・υ＝０で示される直線上に来るように
制限する。確率の形では、Ｐ（υ｜Ｉd）は、ノイズ画
像導関数Ｉdによって決まるフローの確率と定義され
る。画像導関数についての誤差モデルは、以下のように
定義される。
に、Ｉd 0と表記される真の空間時間導関数は、動きベク
トルυを、Ｉd 0・υ＝０で示される直線上に来るように
制限する。確率の形では、Ｐ（υ｜Ｉd）は、ノイズ画
像導関数Ｉdによって決まるフローの確率と定義され
る。画像導関数についての誤差モデルは、以下のように
定義される。
【００１９】
【数７】 式中、ｎは観察誤差であり、平均値ゼロおよび何らかの
共分散Σにてガウス分布していると仮定されている。Ｐ
（υ｜Ｉd）を得るために、ベイズの法則を用いて下記
式が得られる。
共分散Σにてガウス分布していると仮定されている。Ｐ
（υ｜Ｉd）を得るために、ベイズの法則を用いて下記
式が得られる。
【００２０】
【数８】 加法的ノイズモデルを考慮すると、条件的確率Ｐ（Ｉd 0
｜Ｉd）はガウス分布であり、平均はＩd、共分散がΣで
ある。従って、真の画像導関数Ｐ（υ｜Ｉd 0）によって
決まるフローのアプリオリ分布を考慮すると、所望の条
件的確率Ｐ（υ｜Ｉd）を示すことができる。
｜Ｉd）はガウス分布であり、平均はＩd、共分散がΣで
ある。従って、真の画像導関数Ｐ（υ｜Ｉd 0）によって
決まるフローのアプリオリ分布を考慮すると、所望の条
件的確率Ｐ（υ｜Ｉd）を示すことができる。
【００２１】式（３）と同じ条件的確率について記載し
ている同様の確率的方法がこれまで用いられているが
（シモンセリら（同上）参照）、先行技術の方法は、２
つの重要な点で本実施形態と異なっている。第１に、先
行技術の方法のノイズモデルは、画像導関数ではなくフ
ローベクトルに誤差の原因があり、それは最初から誤差
のあることが知られている。第２に、先行技術の方法で
は、フローベクトルＰ（υ）でのアプリオリ分布を選択
する必要がある。この前提条件は説明が非常に困難であ
り、運動の種類、シーンでの奥行き分布などによって変
わる。さらに、解析を容易にするためには、Ｐ（υ）に
ついてゼロ平均のガウス分布を選択する必要があり、そ
れは実際には実現できる場合が少ない。
ている同様の確率的方法がこれまで用いられているが
（シモンセリら（同上）参照）、先行技術の方法は、２
つの重要な点で本実施形態と異なっている。第１に、先
行技術の方法のノイズモデルは、画像導関数ではなくフ
ローベクトルに誤差の原因があり、それは最初から誤差
のあることが知られている。第２に、先行技術の方法で
は、フローベクトルＰ（υ）でのアプリオリ分布を選択
する必要がある。この前提条件は説明が非常に困難であ
り、運動の種類、シーンでの奥行き分布などによって変
わる。さらに、解析を容易にするためには、Ｐ（υ）に
ついてゼロ平均のガウス分布を選択する必要があり、そ
れは実際には実現できる場合が少ない。
【００２２】それとは対照的に本実施形態では、条件的
分布Ｐ（υ｜Ｉd 0）、すなわち画素の真の画像導関数を
考慮したフロー確率を選択する必要があるだけである。
そこで、本実施形態で使用される前提の方が扱い易く、
画面全体の運動パターンＰ（υ）についての知識を必要
としない。この前提の選択およびそれが解に与える影響
について、以下のセクションで説明する。 Ｂ．輝度制約についての確率モデル 図１（ａ）および図１（ｂ）からわかる通り、動きベク
トルυの未知成分はＣＢＡ直線上にあり、角度θによっ
てパラメータ化することができる。これは、可能なθ値
の空間を、許容（斜線）領域と非許容領域に分けるもの
である。許容領域は、Ｉd 0に関連する法線ベクトルυn
を中心とする半円である。そこで、必要な前提条件Ｐ
（υ｜Ｉd 0）をθの条件的前提条件と記載することがで
きる。
分布Ｐ（υ｜Ｉd 0）、すなわち画素の真の画像導関数を
考慮したフロー確率を選択する必要があるだけである。
そこで、本実施形態で使用される前提の方が扱い易く、
画面全体の運動パターンＰ（υ）についての知識を必要
としない。この前提の選択およびそれが解に与える影響
について、以下のセクションで説明する。 Ｂ．輝度制約についての確率モデル 図１（ａ）および図１（ｂ）からわかる通り、動きベク
トルυの未知成分はＣＢＡ直線上にあり、角度θによっ
てパラメータ化することができる。これは、可能なθ値
の空間を、許容（斜線）領域と非許容領域に分けるもの
である。許容領域は、Ｉd 0に関連する法線ベクトルυn
を中心とする半円である。そこで、必要な前提条件Ｐ
（υ｜Ｉd 0）をθの条件的前提条件と記載することがで
きる。
【００２３】最も弱い形では、θに関する前提は単に、
許容領域でのフロー方向が同等の確率を有するというも
のである（図１のＰ（θ｜Ｉd 0）参照）。従来技術にお
ける“核”は、以下の通りである。
許容領域でのフロー方向が同等の確率を有するというも
のである（図１のＰ（θ｜Ｉd 0）参照）。従来技術にお
ける“核”は、以下の通りである。
【００２４】
【数９】 式中、θnは、法線ベクトルυnの方向である。所望に応
じて、フローについての具体的知見を用いて、フロー方
向の条件的分布を変えることができる。例として、フロ
ーの速度が厳密に規定された場合に、θnからの許容さ
れる角度逸脱の範囲を縮小することができる。
じて、フローについての具体的知見を用いて、フロー方
向の条件的分布を変えることができる。例として、フロ
ーの速度が厳密に規定された場合に、θnからの許容さ
れる角度逸脱の範囲を縮小することができる。
【００２５】真のフローはθによって十分にわかること
から、条件的前提Ｐ（θ｜Ｉd 0）を選択することで、条
件的前提Ｐ（υ｜Ｉd 0）が自動的に決まる。それは、以
下のように示すことができる。
から、条件的前提Ｐ（θ｜Ｉd 0）を選択することで、条
件的前提Ｐ（υ｜Ｉd 0）が自動的に決まる。それは、以
下のように示すことができる。
【００２６】
【数１０】 式中、υnは‖Ｉt‖／‖∇Ｉ‖に等しい速度を有する。
式（３）、（４）および（５）を比較することで、Ｐ
（υ｜Ｉd）はＰ（Ｉd 0｜Ｉd）の関数として表すことが
できる。しかしながら、この関数は簡単な解析型を有す
るものではない。実際、それは数値的に評価するのが好
ましい。
式（３）、（４）および（５）を比較することで、Ｐ
（υ｜Ｉd）はＰ（Ｉd 0｜Ｉd）の関数として表すことが
できる。しかしながら、この関数は簡単な解析型を有す
るものではない。実際、それは数値的に評価するのが好
ましい。
【００２７】各画素が画像導関数Ｉdを生じる。次に、
分布Ｐ（Ｉd 0｜Ｉd）から誘導されて、一連の実現的な
値が得られる。各実現的な値について、従来の核が所望
の分布Ｐ（υ｜Ｉd）上に累積される。真のフローＰ
（υ｜Ｉd）の条件的分布は、異なる方向を示す核の加
重平均であり、その場合加重は、条件的分布Ｐ（Ｉd 0｜
Ｉd）によって決定される。
分布Ｐ（Ｉd 0｜Ｉd）から誘導されて、一連の実現的な
値が得られる。各実現的な値について、従来の核が所望
の分布Ｐ（υ｜Ｉd）上に累積される。真のフローＰ
（υ｜Ｉd）の条件的分布は、異なる方向を示す核の加
重平均であり、その場合加重は、条件的分布Ｐ（Ｉd 0｜
Ｉd）によって決定される。
【００２８】上記の確率分布について説明するため、図
２には、３種類の画像導関数［２０、２０、１０］、
［１０、１０、５］および［４、４、２］についての法
線フロー分布および条件フロー分布Ｐ（υ｜Ｉd）を示
してある。これらの導関数は、各種量の画像テクスチャ
を特徴づける領域で認められる同じ法線フローベクトル
［−０．３５、−０．３５］に相当する。画像導関数に
おける誤差は、空間時間次元の各次元での標準偏差が１
のガウス分布によってモデル化される。高レベルのテク
スチャの場合（Ｉd＝［２０、２０、１０］）、輝度制
限と法線フローベクトルは信頼性が高い。従って、得ら
れる法線フロー分布は非常にコンパクトであり、フロー
分布全体は、輝度制限線方向のみが不確定である。中程
度のテクスチャの場合（法線フローベクトルの位置およ
び全フローの両方における不確定性が高くなる。画像テ
クスチャの量が低い場合（Ｉd＝［４、４、２］）、法
線フローおよび全フローの両方の値における不確定性の
程度が大幅に高くなる。これは、法線フローおよび輝度
制限の信頼性が局所区画にある画像テクスチャの量によ
って決まるという直観的事実に相当するものである。低
テクスチャ領域ではこのモデルは、輝度制限線からの大
幅な逸脱をもたらすものではない。
２には、３種類の画像導関数［２０、２０、１０］、
［１０、１０、５］および［４、４、２］についての法
線フロー分布および条件フロー分布Ｐ（υ｜Ｉd）を示
してある。これらの導関数は、各種量の画像テクスチャ
を特徴づける領域で認められる同じ法線フローベクトル
［−０．３５、−０．３５］に相当する。画像導関数に
おける誤差は、空間時間次元の各次元での標準偏差が１
のガウス分布によってモデル化される。高レベルのテク
スチャの場合（Ｉd＝［２０、２０、１０］）、輝度制
限と法線フローベクトルは信頼性が高い。従って、得ら
れる法線フロー分布は非常にコンパクトであり、フロー
分布全体は、輝度制限線方向のみが不確定である。中程
度のテクスチャの場合（法線フローベクトルの位置およ
び全フローの両方における不確定性が高くなる。画像テ
クスチャの量が低い場合（Ｉd＝［４、４、２］）、法
線フローおよび全フローの両方の値における不確定性の
程度が大幅に高くなる。これは、法線フローおよび輝度
制限の信頼性が局所区画にある画像テクスチャの量によ
って決まるという直観的事実に相当するものである。低
テクスチャ領域ではこのモデルは、輝度制限線からの大
幅な逸脱をもたらすものではない。
【００２９】図３には、図２と同じＩd値を用いて、フ
ローの方向および速度について得られる分布を示してあ
る。図３において各縦軸には、記載されている画像導関
数についてのフローの方向（上図）および速度（下図）
の条件的分布を示してある。図３からわかる通り、フロ
ー方向の分布は本質的に、利用可能なテクスチャの量に
よる影響を受けない。しかしながら、テクスチャの量
は、フローの速度の確率に大きく影響する。高テクスチ
ャの場合、法線フローが信頼性が高く、従って全フロー
の速度は法線フロー（垂線で示してある）の速度より大
きいはずである。テクスチャの量が減少するに連れて、
法線フローの速度の信頼性が低くなり、法線フローより
小さいフローの速度の確率が高くなる。これは、信頼性
の低い法線フローは全フロー値の範囲をさほど制限する
ものではないという直観的事実を裏付けるものである。
極端な場合は、識別可能な運動がない場合、すなわちＩ
d≒［０、０、０］の場合であると考えられる。その場
合、シミュレーションされる方向分布は、［−π、π］
の範囲で均一である。結果的に、そのような画素の方向
は、強制的な平滑化のために、完全に隣接画素の方向に
よって決まることになる。 Ｃ．オプティカルフローの解法 ほとんどの先行技術の方法では、フロー場は局所的には
平滑であるとの仮定のもとに、輝度の制約に対する忠実
度を左右するコスト関数を最小とすることによりオプテ
ィカルフローの推定を行っている。奥行きの不連続性の
ため、フロー場は各区分ごとに平滑であるのが普通であ
る（すなわちそれには、大きい不連続部によって分離さ
れた平滑運動区画がある）。平滑化を行うことにより、
フローの推定が、それらの境界部を通って平滑化され、
結果的にフロー推定が不正確になる。
ローの方向および速度について得られる分布を示してあ
る。図３において各縦軸には、記載されている画像導関
数についてのフローの方向（上図）および速度（下図）
の条件的分布を示してある。図３からわかる通り、フロ
ー方向の分布は本質的に、利用可能なテクスチャの量に
よる影響を受けない。しかしながら、テクスチャの量
は、フローの速度の確率に大きく影響する。高テクスチ
ャの場合、法線フローが信頼性が高く、従って全フロー
の速度は法線フロー（垂線で示してある）の速度より大
きいはずである。テクスチャの量が減少するに連れて、
法線フローの速度の信頼性が低くなり、法線フローより
小さいフローの速度の確率が高くなる。これは、信頼性
の低い法線フローは全フロー値の範囲をさほど制限する
ものではないという直観的事実を裏付けるものである。
極端な場合は、識別可能な運動がない場合、すなわちＩ
d≒［０、０、０］の場合であると考えられる。その場
合、シミュレーションされる方向分布は、［−π、π］
の範囲で均一である。結果的に、そのような画素の方向
は、強制的な平滑化のために、完全に隣接画素の方向に
よって決まることになる。 Ｃ．オプティカルフローの解法 ほとんどの先行技術の方法では、フロー場は局所的には
平滑であるとの仮定のもとに、輝度の制約に対する忠実
度を左右するコスト関数を最小とすることによりオプテ
ィカルフローの推定を行っている。奥行きの不連続性の
ため、フロー場は各区分ごとに平滑であるのが普通であ
る（すなわちそれには、大きい不連続部によって分離さ
れた平滑運動区画がある）。平滑化を行うことにより、
フローの推定が、それらの境界部を通って平滑化され、
結果的にフロー推定が不正確になる。
【００３０】概して、得られるコスト関数は、反復非線
形最適化法を用いて最小化され、広域最小値に収束する
保証はない。フロー推定を、制限がある種類のＭＲＦモ
デルに関するラベル問題として公式化することで、反復
法を回避することができ、画像全体の最適解が保証され
る。グラフ上で最大フロー問題への変換を行うことで、
このラベル問題の正確な帰納的最大（ＭＡＰ）推定値を
得ることができる。この広域最小値は、大きい不連続部
を保存する傾向を有する。
形最適化法を用いて最小化され、広域最小値に収束する
保証はない。フロー推定を、制限がある種類のＭＲＦモ
デルに関するラベル問題として公式化することで、反復
法を回避することができ、画像全体の最適解が保証され
る。グラフ上で最大フロー問題への変換を行うことで、
このラベル問題の正確な帰納的最大（ＭＡＰ）推定値を
得ることができる。この広域最小値は、大きい不連続部
を保存する傾向を有する。
【００３１】ＭＲＦのＭＡＰ推定値に対して最大のフロ
ー解を得るには、ラベルが１次元である必要がある。残
念ながら、全ての画素のフローが、２次元ベクトルによ
って説明される。そのため、フローを２個の１次元空間
にパラメータ化する必要がある。本実施形態において
は、２次元フロー場［υx、υy］は、相当する角度−速
度表示［θ、ｍ］へとパラメータ化される。このパラメ
ータ化の好ましい選択について、以下でさらに詳細に説
明する。
ー解を得るには、ラベルが１次元である必要がある。残
念ながら、全ての画素のフローが、２次元ベクトルによ
って説明される。そのため、フローを２個の１次元空間
にパラメータ化する必要がある。本実施形態において
は、２次元フロー場［υx、υy］は、相当する角度−速
度表示［θ、ｍ］へとパラメータ化される。このパラメ
ータ化の好ましい選択について、以下でさらに詳細に説
明する。
【００３２】一般的なＭＲＦの考え方は当業界では知ら
れており、それについての詳細な説明がリー（S.LI）ら
の著作にある（S.Li et al., Markov Random Field Mod
eling In Computer Vision, Springer-Verlag publ. (1
995)）。しかしながら、本実施形態の方法の公式化に先
だって、ＭＲＦの基礎となる考え方を以下に簡単に説明
する。
れており、それについての詳細な説明がリー（S.LI）ら
の著作にある（S.Li et al., Markov Random Field Mod
eling In Computer Vision, Springer-Verlag publ. (1
995)）。しかしながら、本実施形態の方法の公式化に先
だって、ＭＲＦの基礎となる考え方を以下に簡単に説明
する。
【００３３】Ｓ＝｛０、．．．、ｍ−１｝で表される箇
所（画素）の集合が与えられた場合には、個々のラベル
問題は、ラベル集合Ｌ＝｛０、．．．、ｍ−１｝から引
き出される固有のラベル（方向または速度）を各箇所に
割り当てるという問題となる。ラベルの各構成は、確率
変数Ｆ＝｛Ｆ0、．．．、Ｆm-1｝群から引き出される。
ＭＲＦのマルコフ特性は、ある場所が一定のラベルｆi
を取る確率がそれに隣接するものによってのみ決まるよ
うに決定される。概して、その確率は決定が困難である
が、ハンマースレー−クリフォード（Hammersley-Cliff
ord）の定理により、その確率をギブズ分布を用いて
「クリーク電位」Ｖc（ｆ）に関連させ得ることが明ら
かである。すなわち下記式の通りである。
所（画素）の集合が与えられた場合には、個々のラベル
問題は、ラベル集合Ｌ＝｛０、．．．、ｍ−１｝から引
き出される固有のラベル（方向または速度）を各箇所に
割り当てるという問題となる。ラベルの各構成は、確率
変数Ｆ＝｛Ｆ0、．．．、Ｆm-1｝群から引き出される。
ＭＲＦのマルコフ特性は、ある場所が一定のラベルｆi
を取る確率がそれに隣接するものによってのみ決まるよ
うに決定される。概して、その確率は決定が困難である
が、ハンマースレー−クリフォード（Hammersley-Cliff
ord）の定理により、その確率をギブズ分布を用いて
「クリーク電位」Ｖc（ｆ）に関連させ得ることが明ら
かである。すなわち下記式の通りである。
【００３４】
【数１１】 上記式において、Ｕ（ｆ）＝Σc∈Ｖc（ｆ）である。す
なわち、全クリークにわたって合計されたクリーク電位
である。クリークは局所的近傍Ｎ全体にわたって考慮さ
れ、この近傍としては例えば、画素の４個の隣接画素
（各画素が隣接する画素を４個のみ有すると考える場
合）その他の隣接関数があると考えられる。ベイズの式
では、事後確率Ｐ（Ｆ＝ｆ｜Ｘ＝ｘ）（ｘは観察された
データである）を最大とすることが望ましい。ベイズ則
を用いると、下記式のようになる。
なわち、全クリークにわたって合計されたクリーク電位
である。クリークは局所的近傍Ｎ全体にわたって考慮さ
れ、この近傍としては例えば、画素の４個の隣接画素
（各画素が隣接する画素を４個のみ有すると考える場
合）その他の隣接関数があると考えられる。ベイズの式
では、事後確率Ｐ（Ｆ＝ｆ｜Ｘ＝ｘ）（ｘは観察された
データである）を最大とすることが望ましい。ベイズ則
を用いると、下記式のようになる。
【００３５】
【数１２】 ノイズが“ｉｉｄ”（identically and independently
distributed：独立し同様に分布）であると仮定する
と、確度の項は以下のように定義される。
distributed：独立し同様に分布）であると仮定する
と、確度の項は以下のように定義される。
【００３６】
【数１３】 上記式において、積は全箇所にわたるものである（すな
わち、全ピクセル）。要約すると、ＭＡＰの推定は、エ
ネルギーが下記式で表されるエネルギー最小化問題に書
き換えることができる。
わち、全ピクセル）。要約すると、ＭＡＰの推定は、エ
ネルギーが下記式で表されるエネルギー最小化問題に書
き換えることができる。
【００３７】
【数１４】 上記式は、ラベル構成からの寄与と得られるクリークポ
テンシャルからの寄与とを含んでいる。代表的には、ク
リークポテンシャルは、問題の事前の知見を反映するも
のであり、オプティカルフローの場合には、推定された
フロー場に平滑化を課すのに使用される。
テンシャルからの寄与とを含んでいる。代表的には、ク
リークポテンシャルは、問題の事前の知見を反映するも
のであり、オプティカルフローの場合には、推定された
フロー場に平滑化を課すのに使用される。
【００３８】前述のように、本実施形態は、非反復的広
域最小化法を用いて、ラベル問題の解を得るものであ
る。これは、Ｅ（ｆ）をフローグラフとして表し、そこ
で最大フローの計算を行うことで得られる。平均計算量
を実験的に測定したところ、Ｏ（ｎ1.15、ｄ1.31）であ
る（ｎは画像のサイズであり、ｄはラベル数である）。
この環境では、クリークポテンシャルＶ（）は線形であ
る必要があり、下記の形の平滑化項が得られる。
域最小化法を用いて、ラベル問題の解を得るものであ
る。これは、Ｅ（ｆ）をフローグラフとして表し、そこ
で最大フローの計算を行うことで得られる。平均計算量
を実験的に測定したところ、Ｏ（ｎ1.15、ｄ1.31）であ
る（ｎは画像のサイズであり、ｄはラベル数である）。
この環境では、クリークポテンシャルＶ（）は線形であ
る必要があり、下記の形の平滑化項が得られる。
【００３９】
【数１５】 式中、βは解において望まれる平滑化の量を制御する比
例定数である。 １．オプティカルフローについての最大フロー解 前セクションで説明したように、最大フロー計算を用い
て最小化するコスト関数は以下の通りである。
例定数である。 １．オプティカルフローについての最大フロー解 前セクションで説明したように、最大フロー計算を用い
て最小化するコスト関数は以下の通りである。
【００４０】
【数１６】 最大フロー式およびＭＲＦ解釈の詳細は公知であり、上
述の米国特許出願０８／９７８、８３４号ならびにロイ
（Roy）らやイシカワ（Ishikawa）らの論文（前出）な
どに記載されている。ＭＡＰ推定に関連する最小コスト
カットの広域最適性も保証されることが知られており、
ボイコフ（Boykov）ら（前出）やイシカワら（前出）の
文献に記載されている。
述の米国特許出願０８／９７８、８３４号ならびにロイ
（Roy）らやイシカワ（Ishikawa）らの論文（前出）な
どに記載されている。ＭＡＰ推定に関連する最小コスト
カットの広域最適性も保証されることが知られており、
ボイコフ（Boykov）ら（前出）やイシカワら（前出）の
文献に記載されている。
【００４１】前述のように、本実施形態におけるフロー
場のパラメータ化は、（θ、ｍ）表示である。フローに
ついての解を得るには、フロー速度分布Ｐ（υ｜Ｉd）
をそれの角度成分Ｐ（θ｜Ｉd）および速度成分Ｐ（ｍ
｜Ｉd）に簡単に因数分解することで、上記の段落Ｂに
記載の方法に従って、条件的確率Ｐ（θ｜Ｉd）を計算
する。方向フロー場θ（全画素についての方向の構成を
示す）についての解を得るため、式１１は以下の形とな
る。
場のパラメータ化は、（θ、ｍ）表示である。フローに
ついての解を得るには、フロー速度分布Ｐ（υ｜Ｉd）
をそれの角度成分Ｐ（θ｜Ｉd）および速度成分Ｐ（ｍ
｜Ｉd）に簡単に因数分解することで、上記の段落Ｂに
記載の方法に従って、条件的確率Ｐ（θ｜Ｉd）を計算
する。方向フロー場θ（全画素についての方向の構成を
示す）についての解を得るため、式１１は以下の形とな
る。
【００４２】
【数１７】 ＭＲＦ法は有限数のラベルを用いることから、θ＝［−
π、π］の値の範囲は有限数の段階に区分する必要があ
ることが明らかであろう。本実施形態を用いた実験で
は、段階のサイズは１°〜４°を用いた。画素の運動を
区分することで、非離散的表現の場合と比較して大きい
誤差を生じるように思われるかも知れないが、この実験
から、それは当てはまらないことが明らかになった。
π、π］の値の範囲は有限数の段階に区分する必要があ
ることが明らかであろう。本実施形態を用いた実験で
は、段階のサイズは１°〜４°を用いた。画素の運動を
区分することで、非離散的表現の場合と比較して大きい
誤差を生じるように思われるかも知れないが、この実験
から、それは当てはまらないことが明らかになった。
【００４３】フロー方向についての解が得られたら次
に、各画素についての速度ｍについての解を得る必要が
ある。速度は、フロー方向の解を求めた方法と同様にし
て解を得ることができる。しかしながら実際には、速度
の計算は、フローの方向の計算よりかなり難しい。好ま
しくは、計算された方向推定値によって得られる追加デ
ータを利用することで、条件的分布Ｐ（ｍ｜Ｉd）を修
正する。それによってＰ（ｍ｜θs、Ｉd）が得られる
（θsは、画素の方向についての解である）。そこで、
運動速度を計算するためのコスト関数は、以下のように
なる。
に、各画素についての速度ｍについての解を得る必要が
ある。速度は、フロー方向の解を求めた方法と同様にし
て解を得ることができる。しかしながら実際には、速度
の計算は、フローの方向の計算よりかなり難しい。好ま
しくは、計算された方向推定値によって得られる追加デ
ータを利用することで、条件的分布Ｐ（ｍ｜Ｉd）を修
正する。それによってＰ（ｍ｜θs、Ｉd）が得られる
（θsは、画素の方向についての解である）。そこで、
運動速度を計算するためのコスト関数は、以下のように
なる。
【００４４】
【数１８】 留意すべき点として、式（１２）および（１３）におけ
るβを、それぞれβ1およびβ2と表すことで、βの特定
の値が任意であり、運動方向と運動速度の両方で両式に
おいて同じであっても、あるいは運動方向および運動速
度について２式で異なっていても良いことを示してい
る。
るβを、それぞれβ1およびβ2と表すことで、βの特定
の値が任意であり、運動方向と運動速度の両方で両式に
おいて同じであっても、あるいは運動方向および運動速
度について２式で異なっていても良いことを示してい
る。
【００４５】上記の修正により、得られる効果は大幅に
向上される。それは、方向推定がフロー全体を直線に制
限することで、速度の分布の不確定性を低減することで
説明される。すなわち、輝度制約線方向の曖昧さがなく
なっていることから、この新たな条件的分布Ｐ（ｍ｜θ
s、Ｉd）は、真のフローの速度を代表する程度がかなり
高くなっている。２つの推定値（すなわち、θおよび
ｍ）を合わせることで、２個の画像間のオプティカルフ
ローが得られる。
向上される。それは、方向推定がフロー全体を直線に制
限することで、速度の分布の不確定性を低減することで
説明される。すなわち、輝度制約線方向の曖昧さがなく
なっていることから、この新たな条件的分布Ｐ（ｍ｜θ
s、Ｉd）は、真のフローの速度を代表する程度がかなり
高くなっている。２つの推定値（すなわち、θおよび
ｍ）を合わせることで、２個の画像間のオプティカルフ
ローが得られる。
【００４６】図４について説明すると、本実施形態の方
法全体を描いたフローチャートを示してある。時系列連
続画像４００が、本方法に対する入力として提供され
る。時系列連続画像４００は代表的には、７個以上の画
像の連続ビデオ画像であるが、画像導関数の計算ができ
るだけの時間的密度を有する複数画像であればいかなる
ものであっても良い。時系列連続画像４００を、本実施
形態の方法の２つの段階に対する入力として用いる。第
１段階では運動方向を推定し（ステップ４０２、４０
４、４０６および４０８）、第２段階では、運動速度を
推定する（ステップ４１０、４１２、４１４および４１
６）。運動方向の結果も運動速度を得るための段階への
入力として提供されることから、運動方向を得るための
段階を最初に行うのが普通である。
法全体を描いたフローチャートを示してある。時系列連
続画像４００が、本方法に対する入力として提供され
る。時系列連続画像４００は代表的には、７個以上の画
像の連続ビデオ画像であるが、画像導関数の計算ができ
るだけの時間的密度を有する複数画像であればいかなる
ものであっても良い。時系列連続画像４００を、本実施
形態の方法の２つの段階に対する入力として用いる。第
１段階では運動方向を推定し（ステップ４０２、４０
４、４０６および４０８）、第２段階では、運動速度を
推定する（ステップ４１０、４１２、４１４および４１
６）。運動方向の結果も運動速度を得るための段階への
入力として提供されることから、運動方向を得るための
段階を最初に行うのが普通である。
【００４７】運動方向を得るための段階では、第１のフ
ローグラフＧ1がステップ４０２において作成される。
第１のフローグラフＧ1は、画像の空間時間導関数（式
（１））を用いて作成され、コスト関数が得られ（式
（１２））、それの最小値が、運動の方向成分となる。
このフローグラフＧ1は上述の米国特許出願０８／９７
８、８３４号と同様の構成となっているが、式（１２）
のコスト関数を用いて、エッジ容量関数（ｏｃｃ（ｕ、
ｖ）＝βおよびｒｅｇ（ｕ、ｖ）＝−ｌｎ（Ｐ（θ｜Ｉ
di）））を誘導している。次に、本実施形態の方法で
は、ステップ４０４において、第１のグラフＧ1で中の
最大フローの解を求め、上述の米国特許出願０８／９７
８、８３４号に記載の方法と同様にして、第１のグラフ
Ｇ1から最小カットを抜き出す。ステップ４０６では、
該最小カットから運動方向を計算する。方向θi（全画
素について、ｉ∈Ｓ）は、最小カットにおける「ラベ
ル」エッジによって直接得られる。結果として、運動方
向４０８が得られ、それは運動の方向であることから、
オプティカルフローの１成分を表す。
ローグラフＧ1がステップ４０２において作成される。
第１のフローグラフＧ1は、画像の空間時間導関数（式
（１））を用いて作成され、コスト関数が得られ（式
（１２））、それの最小値が、運動の方向成分となる。
このフローグラフＧ1は上述の米国特許出願０８／９７
８、８３４号と同様の構成となっているが、式（１２）
のコスト関数を用いて、エッジ容量関数（ｏｃｃ（ｕ、
ｖ）＝βおよびｒｅｇ（ｕ、ｖ）＝−ｌｎ（Ｐ（θ｜Ｉ
di）））を誘導している。次に、本実施形態の方法で
は、ステップ４０４において、第１のグラフＧ1で中の
最大フローの解を求め、上述の米国特許出願０８／９７
８、８３４号に記載の方法と同様にして、第１のグラフ
Ｇ1から最小カットを抜き出す。ステップ４０６では、
該最小カットから運動方向を計算する。方向θi（全画
素について、ｉ∈Ｓ）は、最小カットにおける「ラベ
ル」エッジによって直接得られる。結果として、運動方
向４０８が得られ、それは運動の方向であることから、
オプティカルフローの１成分を表す。
【００４８】運動速度段階では、ステップ４１０で第２
のフローグラフＧ2が作成される。第２のフローグラフ
Ｇ2は、画像の空間時間導関数（式（１））と前段階で
計算された画素の運動方向４０８とを用いて作成され
る。コスト関数が得られ（式（１３））、その最小値
が、Ｐ（ｍ｜θ、Ｉd）に当てはめた場合に、運動速度
成分を与える。このフローグラフＧ2は上述の米国特許
出願０８／９７８、８３４号と同様の構成となっている
が、このコスト関数を用いて、エッジ容量関数（ｏｃｃ
（ｕ、ｖ）＝βおよびｒｅｇ（ｕ、ｖ）＝−ｌｎ（Ｐ
（ｍ｜θsi、Ｉdi）））を誘導している。次に本実施形
態の方法では、ステップ４１２において、第２のフロー
グラフＧ2中での最大フローの解を求め、上述の米国特
許出願０８／９７８、８３４号に記載の方法と同様にし
て、第２のグラフＧ2から最小カットを抜き出す。ステ
ップ４１４では、その最小カットから運動速度を計算す
る。速度ｍi（全画素について、ｉ∈Ｓ）は、最小カッ
トにおける「ラベル」エッジによって直接得られる。結
果として、運動速度４１６が得られ、それは運動速度で
あることから、オプティカルフローの別の成分を表す。
のフローグラフＧ2が作成される。第２のフローグラフ
Ｇ2は、画像の空間時間導関数（式（１））と前段階で
計算された画素の運動方向４０８とを用いて作成され
る。コスト関数が得られ（式（１３））、その最小値
が、Ｐ（ｍ｜θ、Ｉd）に当てはめた場合に、運動速度
成分を与える。このフローグラフＧ2は上述の米国特許
出願０８／９７８、８３４号と同様の構成となっている
が、このコスト関数を用いて、エッジ容量関数（ｏｃｃ
（ｕ、ｖ）＝βおよびｒｅｇ（ｕ、ｖ）＝−ｌｎ（Ｐ
（ｍ｜θsi、Ｉdi）））を誘導している。次に本実施形
態の方法では、ステップ４１２において、第２のフロー
グラフＧ2中での最大フローの解を求め、上述の米国特
許出願０８／９７８、８３４号に記載の方法と同様にし
て、第２のグラフＧ2から最小カットを抜き出す。ステ
ップ４１４では、その最小カットから運動速度を計算す
る。速度ｍi（全画素について、ｉ∈Ｓ）は、最小カッ
トにおける「ラベル」エッジによって直接得られる。結
果として、運動速度４１６が得られ、それは運動速度で
あることから、オプティカルフローの別の成分を表す。
【００４９】オプティカルフロー４１８は、運動方向成
分４０８と運動速度成分４１６を合わせたものであるこ
とから、オプティカルフロー場全体となる。 ２．２次元フローのパラメータ化 前述のように、オプティカルフローはパラメータ化され
て、２個の１次元表現になる。これら２つのパラメータ
はできるだけ互いに独立であることが望ましい（すなわ
ち、Ｐ（υ｜Ｉd）＝Ｐ（ａ（υ）｜Ｉd）Ｐ（ｂ（υ）
｜Ｉd）であって、式中ａ（υ）およびｂ（υ）はフロ
ーを表す新たな１次元パラメータである）。そこで、角
度−速度表現（θ、ｍ）および速度成分（υx、υy）と
いう２つの選択肢を検討した。最良の表現を決定するた
め、相互相関係数を実験的に測定した。多数の代表的画
像導関数の場合（５００の実験）、相当する条件的分布
Ｐ（υ｜Ｉd）を得て、２つの異なるパラメータ化につ
いて相互相関係数を計算した。相互相関係数ρは以下の
ように定義される。
分４０８と運動速度成分４１６を合わせたものであるこ
とから、オプティカルフロー場全体となる。 ２．２次元フローのパラメータ化 前述のように、オプティカルフローはパラメータ化され
て、２個の１次元表現になる。これら２つのパラメータ
はできるだけ互いに独立であることが望ましい（すなわ
ち、Ｐ（υ｜Ｉd）＝Ｐ（ａ（υ）｜Ｉd）Ｐ（ｂ（υ）
｜Ｉd）であって、式中ａ（υ）およびｂ（υ）はフロ
ーを表す新たな１次元パラメータである）。そこで、角
度−速度表現（θ、ｍ）および速度成分（υx、υy）と
いう２つの選択肢を検討した。最良の表現を決定するた
め、相互相関係数を実験的に測定した。多数の代表的画
像導関数の場合（５００の実験）、相当する条件的分布
Ｐ（υ｜Ｉd）を得て、２つの異なるパラメータ化につ
いて相互相関係数を計算した。相互相関係数ρは以下の
ように定義される。
【００５０】
【数１９】 式中、Ｅは期待値であり、μは平均を示し、（ａ、ｂ）
は（θ、ｍ）または（υx、υy）のいずれかである。ρ
の平均値は、（θ、ｍ）表現の場合は０．０４であり、
（υx、υy）表現の場合は０．４である。（θ、ｍ）表
現はほとんど独立であるが、（υx、υy）表現はそうで
はないことが明らかである。従って、角度−速度のパラ
メータ化を選択するのが適切である。 Ｄ．結果 本セクションでは、バロン（Barron）らによる評価につ
いての論文（Barron et al., "Performance Of Optical
Flow Techniques," Int'l Journal of Computer Visio
n, Vol.2, No.1, pp.43-77 (1994)）からの合成データ
集合および実データ集合について本実施形態の方法を用
い、さらにはその論文に記載の各種方法の結果と本実施
形態の結果とを比較することで、本実施形態の方法の効
果を評価する。
は（θ、ｍ）または（υx、υy）のいずれかである。ρ
の平均値は、（θ、ｍ）表現の場合は０．０４であり、
（υx、υy）表現の場合は０．４である。（θ、ｍ）表
現はほとんど独立であるが、（υx、υy）表現はそうで
はないことが明らかである。従って、角度−速度のパラ
メータ化を選択するのが適切である。 Ｄ．結果 本セクションでは、バロン（Barron）らによる評価につ
いての論文（Barron et al., "Performance Of Optical
Flow Techniques," Int'l Journal of Computer Visio
n, Vol.2, No.1, pp.43-77 (1994)）からの合成データ
集合および実データ集合について本実施形態の方法を用
い、さらにはその論文に記載の各種方法の結果と本実施
形態の結果とを比較することで、本実施形態の方法の効
果を評価する。
【００５１】本実施形態の方法について試験を行う際に
は、画像導関数の計算は、空間−時間ガウスフィルター
（σ＝１．５）の適用と、次に４点差演算子（１／１
２）［−１、８、−８、１］の適用から成るものであ
る。バロンら（同上）における修正ホーン−シュンク
（Horn and Shunk）アルゴリズムは、同じ導関数計算を
使用するものである。ほとんどの実験に要する実行時間
は、小さい画像の場合で数秒の範囲であり、高速ワーク
ステーションでの大きい画像の場合で１０分以内であ
る。これらの実行時間は、解にほとんど影響を与えるこ
となく、運動パラメータについての比較的粗い離散化を
用いることで、容易に短縮することができる。本セクシ
ョンに示した結果はいずれも、事後処理を行わずに、本
実施形態の方法によって得られた生のフロー場である。 １．合成画像 本実施形態のオプティカルフロー推定方法を、正しい結
果が得られているバロンらの５種類の合成画像列につい
て行った。この５種類の合成画像列は、バロンらの論文
において、様々なアルゴリズムを比較するために用いら
れている画像列の例であり、それぞれ「Sinusoid 1」、
「square 2」、「Translating Tree」、「Diverging Tr
ee」、「Yosemite」というタイトルがつけられている。
は、画像導関数の計算は、空間−時間ガウスフィルター
（σ＝１．５）の適用と、次に４点差演算子（１／１
２）［−１、８、−８、１］の適用から成るものであ
る。バロンら（同上）における修正ホーン−シュンク
（Horn and Shunk）アルゴリズムは、同じ導関数計算を
使用するものである。ほとんどの実験に要する実行時間
は、小さい画像の場合で数秒の範囲であり、高速ワーク
ステーションでの大きい画像の場合で１０分以内であ
る。これらの実行時間は、解にほとんど影響を与えるこ
となく、運動パラメータについての比較的粗い離散化を
用いることで、容易に短縮することができる。本セクシ
ョンに示した結果はいずれも、事後処理を行わずに、本
実施形態の方法によって得られた生のフロー場である。 １．合成画像 本実施形態のオプティカルフロー推定方法を、正しい結
果が得られているバロンらの５種類の合成画像列につい
て行った。この５種類の合成画像列は、バロンらの論文
において、様々なアルゴリズムを比較するために用いら
れている画像列の例であり、それぞれ「Sinusoid 1」、
「square 2」、「Translating Tree」、「Diverging Tr
ee」、「Yosemite」というタイトルがつけられている。
【００５２】本実施形態のオプティカルフロー推定方法
による結果を、１００％のフロー場密度を与えるバロン
らにおける５種類のアルゴリズムの結果と比較した。本
実施形態は特に、高密度フロー場の推定を行うためのも
のであって、密度の低い場を与えるよう修正することは
容易ではないことから、低密度法を直接比較することは
できない。誤差の測定は、バロンらにおいて用いられて
いる方法と同じである。２つの動き［ｕ0、υ0］および
［ｕ1、υ1］の場合、誤差の測定値は、２個のベクトル
［ｕ0、υ0、１］および［ｕ1、υ1、１］間の角度と定
義される。
による結果を、１００％のフロー場密度を与えるバロン
らにおける５種類のアルゴリズムの結果と比較した。本
実施形態は特に、高密度フロー場の推定を行うためのも
のであって、密度の低い場を与えるよう修正することは
容易ではないことから、低密度法を直接比較することは
できない。誤差の測定は、バロンらにおいて用いられて
いる方法と同じである。２つの動き［ｕ0、υ0］および
［ｕ1、υ1］の場合、誤差の測定値は、２個のベクトル
［ｕ0、υ0、１］および［ｕ1、υ1、１］間の角度と定
義される。
【００５３】得られた結果を図５にまとめてある。図５
において、本実施形態の結果は、最大フローとして表し
ている。これらデータ集合に対する本実施形態の成績は
常に良好である。しかしながら、これらのデータ集合は
いずれも、非常に平滑な運動場を特徴とするものであっ
て、この運動場は、運動の不連続部付近のアルゴリズム
の挙動を明らかにするものではない。さらに、それには
ノイズおよびその他の画素の不一致要素が含まれる。こ
れらは、実画像についてのオプティカルフロー計算の重
要な側面であり、本実施形態で特に良好に扱われるもの
である。
において、本実施形態の結果は、最大フローとして表し
ている。これらデータ集合に対する本実施形態の成績は
常に良好である。しかしながら、これらのデータ集合は
いずれも、非常に平滑な運動場を特徴とするものであっ
て、この運動場は、運動の不連続部付近のアルゴリズム
の挙動を明らかにするものではない。さらに、それには
ノイズおよびその他の画素の不一致要素が含まれる。こ
れらは、実画像についてのオプティカルフロー計算の重
要な側面であり、本実施形態で特に良好に扱われるもの
である。
【００５４】最も驚くべき結果は、本実施形態の方法が
他のいずれの方法より数桁も優れた成績を与える「squa
re 2」に関するものである。これは、非常に低密度の導
関数データが得られている場合であることから、局所的
ではなく全体的に平滑化を行うことが有利であることを
示すものである。本実施形態が、相関に基づくアルゴリ
ズム（例：Anandan（前出）；Singh（前出））より常に
良好な成績を与え、他のいかなる方法より大きく劣るこ
とは決してないことが明らかであろう。 ２．実画像 実際の条件下での本実施形態の成績を示すため、４種類
の実画像についてのフローを調べる（図６（ａ）、図７
（ａ）、図８（ａ）および図９（ａ））。これらは、良
く知られているルービックキューブ（図６（ａ））、Ｎ
ＡＳＡ画像列（図７（ａ））、ハンブルグのタクシー
（図８（ａ））およびＳＲＩ樹木（図９（ａ））であ
り、バロンらの論文（前述）でも検討されている。正し
い結果が得られていないため、質的結果のみを示す。
他のいずれの方法より数桁も優れた成績を与える「squa
re 2」に関するものである。これは、非常に低密度の導
関数データが得られている場合であることから、局所的
ではなく全体的に平滑化を行うことが有利であることを
示すものである。本実施形態が、相関に基づくアルゴリ
ズム（例：Anandan（前出）；Singh（前出））より常に
良好な成績を与え、他のいかなる方法より大きく劣るこ
とは決してないことが明らかであろう。 ２．実画像 実際の条件下での本実施形態の成績を示すため、４種類
の実画像についてのフローを調べる（図６（ａ）、図７
（ａ）、図８（ａ）および図９（ａ））。これらは、良
く知られているルービックキューブ（図６（ａ））、Ｎ
ＡＳＡ画像列（図７（ａ））、ハンブルグのタクシー
（図８（ａ））およびＳＲＩ樹木（図９（ａ））であ
り、バロンらの論文（前述）でも検討されている。正し
い結果が得られていないため、質的結果のみを示す。
【００５５】ルービックキューブについての推定フロー
場を図６（ｂ）に示してある。このデータ集合は、回転
台上で回転するキューブについての特徴を示すものであ
る。フローは、方向および速度のいずれにおいても、回
転台およびキューブの運動にそのまま従うことがわか
る。フローは、回転台の上面のようなテクスチャのない
領域全体で良好に広がっている。さらに、運動の不連続
部は良好に保存されている。このフロー場の詳細図が図
６（ｃ）にある。図６において、存在する３種類の運動
（キューブ、回転台および背景の運動）が正確に再現さ
れている。
場を図６（ｂ）に示してある。このデータ集合は、回転
台上で回転するキューブについての特徴を示すものであ
る。フローは、方向および速度のいずれにおいても、回
転台およびキューブの運動にそのまま従うことがわか
る。フローは、回転台の上面のようなテクスチャのない
領域全体で良好に広がっている。さらに、運動の不連続
部は良好に保存されている。このフロー場の詳細図が図
６（ｃ）にある。図６において、存在する３種類の運動
（キューブ、回転台および背景の運動）が正確に再現さ
れている。
【００５６】ＮＡＳＡ画像列は、カメラズームによって
生じる発散フロー場の特徴を示すものである。図７
（ａ）に示した画像においてカメラはズームインしてい
る。運動速度は非常に小さく、１画素よりかなり小さい
のが普通である。図７（ｂ）に示したように、フローの
発散は良好に再現されている。注目すべき点として、炭
酸飲料中央部における誤差はほとんどが、反射と少ない
運動とが相まって生じたものと考えられる。
生じる発散フロー場の特徴を示すものである。図７
（ａ）に示した画像においてカメラはズームインしてい
る。運動速度は非常に小さく、１画素よりかなり小さい
のが普通である。図７（ｂ）に示したように、フローの
発散は良好に再現されている。注目すべき点として、炭
酸飲料中央部における誤差はほとんどが、反射と少ない
運動とが相まって生じたものと考えられる。
【００５７】ハンブルグのタクシー画像列は、複数の独
立した運動の１例である。３台の車が画像列を通じて独
立に動いている。得られるフローを図８（ｂ）に示して
ある。車の動きは良好に再現され、良好に局所化されて
いることから、運動速度の簡単な閾値処理を行うこと
で、運動を分割することができる。これは、運動不連続
部の正確な再現が必須である場合の例である。
立した運動の１例である。３台の車が画像列を通じて独
立に動いている。得られるフローを図８（ｂ）に示して
ある。車の動きは良好に再現され、良好に局所化されて
いることから、運動速度の簡単な閾値処理を行うこと
で、運動を分割することができる。これは、運動不連続
部の正確な再現が必須である場合の例である。
【００５８】ＳＲＩ樹木の画像列は、水平方向に移動す
るカメラについての特徴を示すものである。それは、多
数の閉塞および低コントラストを特徴とするものであ
る。カメラの動きが普通とは異なることから、運動速度
は、場面の奥行きと等価である。従って、図９（ｂ）で
の結果は、奥行きマップとして示してある。暗い領域は
運動が小さいことを示し（大きい奥行き）、明るい領域
は運動が大きいことを示している（奥行きが小さい）。
結果は、カメラの動きについてのデータを利用し、従っ
て良好な性能を有すると予想される専用の立体アルゴリ
ズムによって得られる結果に非常に近いものである。画
像中央にある木の幹に沿って見られるように、奥行きの
不連続部は良好に再現されている。他方、注目すべき点
として、地表面の平面性が良好に保存されている。それ
は、高レベルの平滑化を行ないながら、しかもシャープ
な不連続部を再現することが可能であることを示してい
る。従って、確率的枠組みでオプティカルフローを推定
する新規な方法が提供される。簡単なノイズモデルを用
いて、画像導関数の固有の不正確さを明瞭に考慮するこ
とで、全フローの確率モデルが得られている。フローを
それの角度−速度成分に分離することで、全フローが２
段階で計算され、各段階は線形のクリーク電位を用いた
ＭＲＦのＭＡＰ推定に基づくものである。これらの推定
値は最適のものであり、グラフ全体にわたる最大フロー
の計算によって効果的に得られる。再現されるフロー場
は高密度であり、シャープな運動不連続部を保持してい
る。注意深く確率モデルを作成することで、オプティカ
ルフロー推定の問題に固有の大幅な誤差に対して高レベ
ルの堅牢性を得ることができると考えられる。
るカメラについての特徴を示すものである。それは、多
数の閉塞および低コントラストを特徴とするものであ
る。カメラの動きが普通とは異なることから、運動速度
は、場面の奥行きと等価である。従って、図９（ｂ）で
の結果は、奥行きマップとして示してある。暗い領域は
運動が小さいことを示し（大きい奥行き）、明るい領域
は運動が大きいことを示している（奥行きが小さい）。
結果は、カメラの動きについてのデータを利用し、従っ
て良好な性能を有すると予想される専用の立体アルゴリ
ズムによって得られる結果に非常に近いものである。画
像中央にある木の幹に沿って見られるように、奥行きの
不連続部は良好に再現されている。他方、注目すべき点
として、地表面の平面性が良好に保存されている。それ
は、高レベルの平滑化を行ないながら、しかもシャープ
な不連続部を再現することが可能であることを示してい
る。従って、確率的枠組みでオプティカルフローを推定
する新規な方法が提供される。簡単なノイズモデルを用
いて、画像導関数の固有の不正確さを明瞭に考慮するこ
とで、全フローの確率モデルが得られている。フローを
それの角度−速度成分に分離することで、全フローが２
段階で計算され、各段階は線形のクリーク電位を用いた
ＭＲＦのＭＡＰ推定に基づくものである。これらの推定
値は最適のものであり、グラフ全体にわたる最大フロー
の計算によって効果的に得られる。再現されるフロー場
は高密度であり、シャープな運動不連続部を保持してい
る。注意深く確率モデルを作成することで、オプティカ
ルフロー推定の問題に固有の大幅な誤差に対して高レベ
ルの堅牢性を得ることができると考えられる。
【００５９】以上、ある種の利用分野で使用するための
オプティカルフローの推定方法について説明・図示した
が、本明細書に添付の請求の範囲のみによって限定され
る本発明の精神および広義の内容から逸脱しない限りに
おいて、変更および修正が可能であることは、当業者に
は明らかであろう。
オプティカルフローの推定方法について説明・図示した
が、本明細書に添付の請求の範囲のみによって限定され
る本発明の精神および広義の内容から逸脱しない限りに
おいて、変更および修正が可能であることは、当業者に
は明らかであろう。
【００６０】
【発明の効果】上記で説明したように本発明によれば、
下記のような効果を得ることができる。 （１）複数画像間のオプティカルフローを有効かつ正確
に推定することができる。 （２）輝度一定の仮定の制約を行ないながら、画像導関
数の測定における誤差を適切にモデル化することができ
る。 （３）モデル化された環境下で、オプティカルフローに
対する画像の全体的な最適解を効率良く得ることができ
る。
下記のような効果を得ることができる。 （１）複数画像間のオプティカルフローを有効かつ正確
に推定することができる。 （２）輝度一定の仮定の制約を行ないながら、画像導関
数の測定における誤差を適切にモデル化することができ
る。 （３）モデル化された環境下で、オプティカルフローに
対する画像の全体的な最適解を効率良く得ることができ
る。
【図１】オプティカルフロー推定に対する輝度制約を示
す図であり（図１（ａ））、および、図１（ａ）に図示
した輝度制約に相当する従来の条件的分布Ｐ（θ｜
Ｉd 0）を示す図（図１（ｂ））である。
す図であり（図１（ａ））、および、図１（ａ）に図示
した輝度制約に相当する従来の条件的分布Ｐ（θ｜
Ｉd 0）を示す図（図１（ｂ））である。
【図２】図２は、３つの異なる画像テクスチャを代表す
る３つの異なる画像導関数を有する３つの異なる画像導
関数についての法線フローおよびオプティカルフローの
確率分布、すなわち、局所画像変化の程度を描いた図で
ある。
る３つの異なる画像導関数を有する３つの異なる画像導
関数についての法線フローおよびオプティカルフローの
確率分布、すなわち、局所画像変化の程度を描いた図で
ある。
【図３】図３は、図２で用いた３つの異なる画像導関数
についてのオプティカルフローの方向および速度の確率
分布を描いた図である。
についてのオプティカルフローの方向および速度の確率
分布を描いた図である。
【図４】本発明の方法の全体を示すフローチャートであ
る。
る。
【図５】本発明の方法について結果と比較した、各種合
成データ集合についての各種試験アルゴリズムの結果を
示す棒グラフである。
成データ集合についての各種試験アルゴリズムの結果を
示す棒グラフである。
【図６】本発明についての試験を行うのに使用される回
転台上で回転するキューブの連続画像のうちの１個の画
像、（図６（ａ））、および図６（ａ）の画像を含む連
続画像を用いて、本発明の方法によって推定されるオプ
ティカルフロー場を示した図（図６（ｂ））、図６
（ｂ）に示したオプティカルフロー場の拡大図である
（図６（ｃ））。
転台上で回転するキューブの連続画像のうちの１個の画
像、（図６（ａ））、および図６（ａ）の画像を含む連
続画像を用いて、本発明の方法によって推定されるオプ
ティカルフロー場を示した図（図６（ｂ））、図６
（ｂ）に示したオプティカルフロー場の拡大図である
（図６（ｃ））。
【図７】本発明についての試験を行うのに使用される、
炭酸飲料缶と各種取り合わせた対象物の連続画像中の１
画像である（図７（ａ））、および図７（ａ）の画像を
含む連続画像を用いて、本発明の方法によって推定した
オプティカルフロー場を示した図（図７（ｂ））であ
る。
炭酸飲料缶と各種取り合わせた対象物の連続画像中の１
画像である（図７（ａ））、および図７（ａ）の画像を
含む連続画像を用いて、本発明の方法によって推定した
オプティカルフロー場を示した図（図７（ｂ））であ
る。
【図８】本発明についての試験を行うのに使用される、
独立に運動する複数の車の連続画像中の１画像を示した
図（図８（ａ））、および図８（ａ）の画像を含む連続
画像を用いて、本発明の方法によって推定されるオプテ
ィカルフロー場を示す図（図８（ｂ））である。
独立に運動する複数の車の連続画像中の１画像を示した
図（図８（ａ））、および図８（ａ）の画像を含む連続
画像を用いて、本発明の方法によって推定されるオプテ
ィカルフロー場を示す図（図８（ｂ））である。
【図９】本発明についての試験を行うのに使用される、
カメラが画像を横切って水平方向に移動する、樹木の連
続画像中の１画像を示す図（図９（ａ））、および図９
（ａ）の画像を含む連続画像を用いて、本発明の方法に
よって推定されるオプティカルフロー場を示す奥行きマ
ップを示す図（図９（ｂ））である。
カメラが画像を横切って水平方向に移動する、樹木の連
続画像中の１画像を示す図（図９（ａ））、および図９
（ａ）の画像を含む連続画像を用いて、本発明の方法に
よって推定されるオプティカルフロー場を示す奥行きマ
ップを示す図（図９（ｂ））である。
４００ 時系列連続画像 ４０２、４０４、４０６ ステップ ４０８ 運動方向 ４１０、４１２、４１４ ステップ ４１６ 運動速度
Claims (8)
- 【請求項１】 複数の画像間でのオプティカルフローを
推定するオプティカルフロー推定方法であって、 （ａ）複数の画像の空間時間導関数を用いて第１のグラ
フＧ1を作成するステップと、 前記第１のグラフＧ1中の第１の最大フローについて解
を求めることで、それから第１の最小カットを得るステ
ップと、 前記第１の最小カットから運動方向成分を計算するステ
ップとを有する、運動方向成分を得るステップと、 （ｂ）前記複数の画像の空間時間導関数および前記運動
方向成分を用いて第２のグラフＧ2を作成するステップ
と、 前記第２のグラフＧ2中の第２の最大フローについて解
を求めることで、それから第２の最小カットを得るステ
ップと、 前記第２の最小カットから運動速度成分を計算するステ
ップとを有する、運動速度成分を得るステップとを有
し、 前記運動方向成分および前記運動速度成分とを組み合わ
せて、複数画像間のオプティカルフローを推定するオプ
ティカルフロー推定方法。 - 【請求項２】 前記第１のグラフＧ1が、 【数１】 ［式中、Ｓは全画素集合を示し、Ｎiは画素ｉに隣接す
る全画素集合を示し、β1は負ではない任意の平滑化定
数を示し、θiは画素ｉの方向を示し、Ｉdは測定画像導
関数を示し、Ｐ（θ｜Ｉdi）は画像導関数がＩdiの場合
の方向θの条件的確率を示している。］で示されるコス
ト関数からエッジ容量関数を誘導することで作成され
る、請求項１記載のオプティカルフロー推定方法。 - 【請求項３】 隣接する画素が４個である、請求項２記
載のオプティカルフロー推定方法。 - 【請求項４】 条件的確率分布Ｐ（θ｜Ｉdi）が［Ｐ
（θ｜Ｉd 0）・Ｐ（Ｉ d 0｜Ｉd）］（式中、Ｐ（θ｜Ｉd
0）は運動方向のモデルを示し、Ｐ（Ｉd 0｜Ｉd）は画像
導関数の測定における誤差のモデルを示す）であり、さ
らに 【数２】 および 【数３】 である請求項２記載のオプティカルフロー推定方法。 - 【請求項５】 前記第２のグラフＧ2が、 【数４】 ［式中、Ｓは全画素集合を示し、Ｎiは画素ｉに隣接す
る全画素集合を示し、β2は負ではない任意の平滑化定
数を示し、ｍiは画素ｉの速度を示し、Ｉdは測定画像導
関数を示し、Ｐ（ｍ｜θsi、Ｉdi）は方向が既知のθsi
であって、画像導関数がＩdiの場合の速度ｍの条件的確
率を示す。］で示されるコスト関数からエッジ容量関数
を誘導することで作成される、請求項２記載のオプティ
カルフロー推定方法。 - 【請求項６】 条件的確率分布Ｐ（θ｜Ｉdi）と輝度一
定の仮定とを組み合わせて、条件的確率分布Ｐ（ｍ｜θ
si、Ｉdi）を得る、請求項５記載のオプティカルフロー
推定方法。 - 【請求項７】 前記第２のグラフＧ2が、 【数５】 ［式中、Ｓは全画素集合を示し、Ｎiは画素ｉに隣接す
る全画素集合を示し、β2は負ではない任意の平滑化定
数を示し、ｍiは画素ｉの速度を示し、Ｉdは測定画像導
関数を示し、Ｐ（ｍ｜θsi、Ｉdi）は方向が既知のθsi
であって、画像導関数がＩdiの場合の速度ｍの条件的確
率を示す。］で示されるコスト関数からエッジ容量関数
を誘導することで作成される請求項１記載のオプティカ
ルフロー推定方法。 - 【請求項８】 隣接する画素が４個である請求項７記載
のオプティカルフロー推定方法。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US13016899P | 1999-04-20 | 1999-04-20 | |
| US09/391732 | 1999-09-08 | ||
| US09/391,732 US6507661B1 (en) | 1999-04-20 | 1999-09-08 | Method for estimating optical flow |
| US60/130168 | 1999-09-08 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000306108A true JP2000306108A (ja) | 2000-11-02 |
| JP3557982B2 JP3557982B2 (ja) | 2004-08-25 |
Family
ID=26828229
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000022967A Expired - Fee Related JP3557982B2 (ja) | 1999-04-20 | 2000-01-31 | オプティカルフロー推定方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6507661B1 (ja) |
| EP (1) | EP1047019A3 (ja) |
| JP (1) | JP3557982B2 (ja) |
| CA (1) | CA2297233C (ja) |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB9920256D0 (en) * | 1999-08-26 | 1999-10-27 | Wave Limited M | Motion estimation and compensation in video compression |
| US6744923B1 (en) * | 1999-08-30 | 2004-06-01 | Cornell Research Foundation, Inc. | System and method for fast approximate energy minimization via graph cuts |
| DE10109921A1 (de) * | 2001-03-01 | 2002-09-05 | Ruediger Schrott | Computeranimation von Rennfahrzeugen für Fernsehübertragungen |
| KR100415313B1 (ko) * | 2001-12-24 | 2004-01-16 | 한국전자통신연구원 | 동영상에서 상관 정합과 시스템 모델을 이용한 광류와카메라 움직임 산출 장치 |
| US7164800B2 (en) * | 2003-02-19 | 2007-01-16 | Eastman Kodak Company | Method and system for constraint-consistent motion estimation |
| CA2464569A1 (en) * | 2003-04-16 | 2004-10-16 | Universite De Montreal | Single or multi-projector for arbitrary surfaces without calibration nor reconstruction |
| WO2005050560A1 (en) * | 2003-11-20 | 2005-06-02 | Yissum Research Development Company Of The Hebrew University Of Jerusalem | Image mosaicing responsive to camera ego motion |
| US20060020562A1 (en) * | 2004-07-21 | 2006-01-26 | University Of Southern Mississippi | Apparatus and method for estimating optical flow |
| US7558755B2 (en) * | 2005-07-13 | 2009-07-07 | Mott Antony R | Methods and systems for valuing investments, budgets and decisions |
| TWI287103B (en) * | 2005-11-04 | 2007-09-21 | Univ Nat Chiao Tung | Embedded network controlled optical flow image positioning omni-direction motion system |
| US20070280507A1 (en) * | 2006-06-01 | 2007-12-06 | Beddhu Murali | Apparatus and Upwind Methods for Optical Flow Velocity Estimation |
| DE102006027123A1 (de) | 2006-06-12 | 2007-12-13 | Robert Bosch Gmbh | Verfahren für die Erfassung eines Verkehrsraums |
| US8340349B2 (en) * | 2006-06-20 | 2012-12-25 | Sri International | Moving target detection in the presence of parallax |
| US7974460B2 (en) * | 2007-02-06 | 2011-07-05 | Honeywell International Inc. | Method and system for three-dimensional obstacle mapping for navigation of autonomous vehicles |
| US7925089B2 (en) * | 2007-09-18 | 2011-04-12 | Microsoft Corporation | Optimization of multi-label problems in computer vision |
| FR2931277B1 (fr) * | 2008-05-19 | 2010-12-31 | Ecole Polytech | Procede et dispositif de reconnaissance invariante-affine de formes |
| US8060271B2 (en) * | 2008-06-06 | 2011-11-15 | Toyota Motor Engineering & Manufacturing North America, Inc. | Detecting principal directions of unknown environments |
| KR100955044B1 (ko) * | 2008-07-11 | 2010-04-28 | 포항공과대학교 산학협력단 | 서브 픽셀 해상도의 옵티컬 플로우 추정 장치 및 방법 |
| JP5278776B2 (ja) * | 2008-12-09 | 2013-09-04 | トヨタ自動車株式会社 | 物体検出装置および物体検出方法 |
| US8553943B2 (en) | 2011-06-14 | 2013-10-08 | Qualcomm Incorporated | Content-adaptive systems, methods and apparatus for determining optical flow |
| EP3570132B1 (en) | 2014-09-30 | 2022-03-02 | SZ DJI Technology Co., Ltd. | System and method for data recording and analysis |
| EP3429186B1 (en) | 2016-03-30 | 2022-08-24 | Huawei Technologies Co., Ltd. | Image registration method and device for terminal |
| US20240144490A1 (en) * | 2022-10-13 | 2024-05-02 | The Hong Kong University Of Science And Technology | Joint count and flow analysis for video crowd scenes |
| US12541930B2 (en) * | 2023-12-28 | 2026-02-03 | Snap Inc. | Pixel-based multi-view garment transfer |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5680487A (en) * | 1991-12-23 | 1997-10-21 | Texas Instruments Incorporated | System and method for determining optical flow |
| DE69433074D1 (de) * | 1993-07-02 | 2003-10-02 | Siemens Corp Res Inc | Hintergrundrückgewinnung in monokularer Bildverarbeitung |
| US5751838A (en) * | 1996-01-26 | 1998-05-12 | Nec Research Institute, Inc. | Correction of camera motion between two image frames |
| US6046763A (en) * | 1997-04-11 | 2000-04-04 | Nec Research Institute, Inc. | Maximum flow method for stereo correspondence |
-
1999
- 1999-09-08 US US09/391,732 patent/US6507661B1/en not_active Expired - Lifetime
-
2000
- 2000-01-26 CA CA002297233A patent/CA2297233C/en not_active Expired - Fee Related
- 2000-01-27 EP EP00101283A patent/EP1047019A3/en not_active Withdrawn
- 2000-01-31 JP JP2000022967A patent/JP3557982B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP1047019A3 (en) | 2003-10-29 |
| EP1047019A2 (en) | 2000-10-25 |
| JP3557982B2 (ja) | 2004-08-25 |
| CA2297233C (en) | 2006-07-18 |
| US6507661B1 (en) | 2003-01-14 |
| CA2297233A1 (en) | 2000-10-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3557982B2 (ja) | オプティカルフロー推定方法 | |
| Zhu et al. | Spatial-temporal fusion for high accuracy depth maps using dynamic MRFs | |
| US7352386B1 (en) | Method and apparatus for recovering a three-dimensional scene from two-dimensional images | |
| Min et al. | Cost aggregation and occlusion handling with WLS in stereo matching | |
| Newcombe et al. | Live dense reconstruction with a single moving camera | |
| US6278460B1 (en) | Creating a three-dimensional model from two-dimensional images | |
| US8447099B2 (en) | Forming 3D models using two images | |
| US8599252B2 (en) | Moving object detection apparatus and moving object detection method | |
| EP3367334B1 (en) | Depth estimation method and depth estimation apparatus of multi-view images | |
| US7184071B2 (en) | Method of three-dimensional object reconstruction from a video sequence using a generic model | |
| US20120177284A1 (en) | Forming 3d models using multiple images | |
| KR20190042187A (ko) | 깊이 값을 추정하는 방법 및 장치 | |
| EP3293700B1 (en) | 3d reconstruction for vehicle | |
| Choi et al. | A consensus-driven approach for structure and texture aware depth map upsampling | |
| WO2003041015A1 (en) | A method for computing optical flow under the epipolar constraint | |
| CN112085842A (zh) | 深度值确定方法及装置、电子设备和存储介质 | |
| Pan et al. | Depth map completion by jointly exploiting blurry color images and sparse depth maps | |
| Chen et al. | A particle filtering framework for joint video tracking and pose estimation | |
| Kim et al. | Error analysis of robust optical flow estimation by least median of squares methods for the varying illumination model | |
| Calway | Recursive estimation of 3D motion and surface structure from local affine flow parameters | |
| US10121257B2 (en) | Computer-implemented method and system for processing video with temporal consistency | |
| Sim et al. | Robust reweighted MAP motion estimation | |
| Hatzitheodorou et al. | Stereo matching using optic flow | |
| Kuschk et al. | Real-time variational stereo reconstruction with applications to large-scale dense SLAM | |
| JP2001167249A (ja) | 画像合成方法、画像合成装置、画像合成プログラムを記録した記録媒体 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20040218 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040405 |
|
| A911 | Transfer of reconsideration by examiner before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20040409 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040427 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040510 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090528 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100528 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110528 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110528 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120528 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120528 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130528 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140528 Year of fee payment: 10 |
|
| LAPS | Cancellation because of no payment of annual fees |