Fast Optical Flow – Sean I Young, PhD

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO

Abstract—We propose the fast optical ﬂow extractor, a ﬁltering

method that recovers artifact-free optical ﬂow ﬁelds from HEVC-

compressed video. To ex tr ac t acc ur at e o pt ical ﬂow ﬁelds, we form

a regularized optimization problem that considers the smoothness

of the solution and the pixelwise conﬁdence weights of an artifact-

ridden HEVC motion ﬁeld. Solving such an optimization problem

is slow, so we ﬁrst convert the problem into a conﬁdence-weighted

ﬁltering task. By leveraging the already-available HEVC motion

parameters, we achieve a 100-fold speed-up in the running times

compared to similar methods, while producing subpixel-accurate

ﬂow estimates. Je fast optical ﬂow extractor is useful when video

frames are already available in coded formats. Our method is not

speciﬁc to a coder, and works with motion ﬁelds from video coders

such as H.264/AVC and HEVC.

Index Terms—Optical ﬂow, inverse problems, edge-preserving

ﬁltering, HEVC.

!" !!"#$%&'"($!#

$%!$&#'(%!)*%!$&#+,#-#./-,,+.#0+,+12#3415/67#8+9:#

-33/+.-9+12#4-2;+2;#<417#41519#2-0+;-9+12#-2=#7-33+2;#

>?@A#>B@#-2=#:C7-2#-.9+0+9D#-2-/D,+,#>E@F>G@#91#0+=61#.1=+2;#>H@#

-2=#-2-/D,+,#>I@A#>J@"#)146#46.629/DA#719+12#6,9+7-9+12#:-,#-/,1#

5662#C,6=#91#-+=#-C912171C,#06:+./6#2-0+;-9+12#>K@A#>?L@"#

# M6#14+;+2,#1<#719+12#6,9+7-9+12#46,6-4.:#7-D#56#-994+5C96=#

91#9:6#,67+2-/#814N#1<#O+5,12#>??@A#8:+.:#+206,9+;-96,#9:6#41/6##

1<#139+.-/#P14#15,6406=Q#719+12#<14#:C7-2#0+,C-/#364.639+12"#*#

7-9:67-9+.-/#,9C=D#1<#139+.-/#719+12#>?B@A#>?E@#9:62#+//C,94-96=#

9:-9#;+062#-2#139+.-/#719+12#R6/=A#:C7-2,#.-2#+2<64#9:6#719+12#

1<#15S6.9,#+2#9:6#3:D,+.-/#814/="#'0629C-//DA#T142#-2=#(.:C2.N#

>?U@#,:186=#9:-9#139+.-/#719+12A#+2#9C42A#.-2#56#6,9+7-96=#<417#

,C..6,,+06#0+68,#1<#-#,.626#+<#.649-+2#-,,C739+12,#.-2#56#7-=6#

46;-4=+2;#+9,#,7119:26,,"#V6,3+96#+9,#,+73/+.+9DA#9:6#0-4+-9+12-/#

139+7+W-9+12#<4-76814N#1<#T142#-2=#(.:C2.N#+,#,9+//#9:6#5-,+,#

1<#46.629#719+12#6,9+7-9+12#-/;14+9:7,X#,66A#6";"A#>?G@F>BB@"#%1#

;C+=6#9:6#46-=64A#Y+;"#?#P=Q#+//C,94-96,#-2#139+.-/#Z18#R6/=#<417#

9:6#(+296/#0+=61#,6[C62.6,#>BE@"#!2#9:+,#814NA#86#C,6#9:6#9647,#

\139+.-/#Z18]#-2=#\719+12]#+2964.:-2;6-5/D"#

# !2#0+=61#.1=+2;#-33/+.-9+12,A#719+12#+2<147-9+12#+,#C,6=#<14#

719+12^.17362,-9+2;#346=+.9+12#1<#<C9C46#3+.9C46#<4-76,#C,+2;#

3460+1C,#.1=6=#<4-76,"#_+9:#346=+.9+06#.1=+2;A#12/D#346=+.9+12#

64414,#-2=#719+12#06.914,#-46#.1=6=#-2=#.177C2+.-96=A#8:+.:#

6`6.9+06/D#.17346,,6,#0+=61#=-9-"#(+2.6#9:6#15S6.9+06#1<#0+=61#

.1=+2;#+,#=-9-#.17346,,+12A#719+12#6,9+7-96=#<14#0+=61#.1=+2;#

7C,9#:-06#-#/18#,914-;6#.173/6a+9D"#*,#-#46,C/9A#.1=6=#719+12#

+,#,3-4,6A#8+9:#12/D#126#14#981#719+12#06.914,#C,C-//D#-,,+;26=#

91#6-.:#46.9-2;C/-4#346=+.9+12#C2+9#1<#9:6#<4-76"#!2#T'bcA#9:6#

/-96,9#0+=61#.1=+2;#,9-2=-4=#>BU@A#86#.-2#-/,1#.:6-3/D#-,,+;2#-#

,+2;/6#719+12#06.914#91#3+.9C46#46;+12,#8+9:#.173/6a#51C2=-4D#

;617694D#C,+2;#346=+.9+12#C2+9#764;+2;"#)-2D#346=+.9+12#C2+9,#

=6/+564-96/D#-,,+;2#719+12#06.914,#9:-9#-46#+2.1446.9A#-,#/12;#-,#

,C.:#719+12#:6/3,#+734106#9:6#1064-//#.1=+2;#6d.+62.D"#Y+;"#?#

P5Q#,:18,#-#9D3+.-/#719+12#R6/=#6,9+7-96=#5D#T'bc"#

# M6#=+`6462.6#5698662#9:6#719+12#R6/=#6,9+7-96=#5D#T'bc#

-2=#\46-/]#139+.-/#Z18#769:1=,#+,#+//C,94-96=#+2#Y+;"#?"#$39+.-/#

Z18#-/;14+9:7,#6,9+7-96#3+6.68+,6#,7119:#719+12#R6/=,#8:+/6##

5/1.N^5-,6=#0+=61#.1=64,#/+N6#T'bc#6,9+7-96#-#\5/1.ND]#126#

5D#=6,+;2"#$26#.1C/=#-33/D#-2#6=;6^346,640+2;#R/964#12#T'bc#

719+12#91#467106#5/1.N#-49+<-.9,#<417#+9A#5C9#,+73/6#R/964+2;#+,#

+2,Cd.+629#91#341=C.6#139+.-/#Z18#R6/=,#1<#:+;:#-..C4-.D"#Y14#

6a-73/6A#-#2C7564#1<#346=+.9+12#C2+9,#-46#.1=6=#8+9:1C9#C,+2;#

-2D#719+12#+2<147-9+12#-9#-//A#,1#86#7C,9#-==+9+12-//D#+2^3-+29#

9:6#719+12#06.914,#+2#346=+.9+12#C2+9,#8+9:#7+,,+2;#719+12"#_6#

7-D#-/,1#8+,:#91#3/-.6#/6,,#.12R=62.6#+2#9:6#719+12#06.914,#1<#

346=+.9+12#C2+9,#8+9:#/-4;6#346=+.9+12#64414"#!73149-29/DA#,+73/6#

6=;6^-8-46#R/964+2;#=16,#219#<-.+/+9-96#0-4+-9+12-/#139+7+W-9+12#

1<#9:6#719+12A#8:+.:#+,#+2=+,362,-5/6#91#6,9+7-9+2;#139+.-/#Z18#

R6/=,#1<#,C5^3+a6/#-..C4-.D"#

# _6#34131,6#9:6#<-,9#139+.-/#Z18#6a94-.914A#-#R/964+2;#769:1=#

Fast Optical Flow Extraction

from Compressed Video

Sean I. Young , Member, IEEE, Bernd Girod , Fellow, IEEE, and David Taubman , Fellow, IEEE

(a) decoded frame

(b) decoded motion

(d) ground truth flow

)*+,-.,-/0123456789-:*981-2198;7-7<2=-67->?@'-A;19<28-6-9821989-B;6C8-D6E-601F+-G*H=-6-9821989-C1H*1F-I809-D5E-67-6-5J4A;19<2H,-K8-9821989-C1H*1F-I8097-

21FH6*F-50123-6;H*B62H7-6F9-;8+*1F7-1B-C*77*F+-C1H*1F-:82H1;7-D50623-;8+*1F7E,-L8-I0H8;-7<2=-6-C1H*1F-I809-H1-A;19<28-6;H*B62H4B;88-1AH*260-M1G-D2E,-$<;-8NH;62H89-

1AH*260-M1G-*7-7*C*06;-H1-H=8-+;1<F9-H;<H=-1AH*260-M1G-D9E,-/87H-:*8G89-1F0*F8,-

- O6F<72;*AH- ;828*:89- O6J- P.Q- PR.ST- ;8:*789- )85;<6;J- .RQ- PRPRT- 6228AH89--

)85;<6;J-..Q-PRPR,-%6H8-1B-A<50*26H*1F-UA;*0-.RQ-PRPRT-96H8-1B-2<;;8FH-:8;7*1F-

O6J-.VQ-PRPR,-K8-67712*6H8-89*H1;-211;9*F6H*F+-H=8-;8:*8G-1B-H=*7-C6F<72;*AH-

6F9-6AA;1:*F+-*H-B1;-A<50*26H*1F-G67-W;1B,-X1280JF-'=6FF<71H,-!"#$$%&'#()*(+,

-./0#$1,2%-(,34,5#.(+46,

- Y86F- (,- Z1<F+- 6F9- /8;F9- [*;19- 6;8- G*H=- H=8- (FB1;C6H*1F- YJ7H8C7- \6514

;6H1;JQ- %8A6;HC8FH- 1B- ?082H;*260- ?F+*F88;*F+Q- YH6FB1;9- &F*:8;7*HJQ- YH6FB1;9Q-

'U-S]^R_-&YU-D84C6*0`-786FRa7H6FB1;9,89<Q-5+*;19a7H6FB1;9,89<E,-

- %6:*9-"6<5C6F-*7-G*H=-H=8-Y2=110-1B-?082H;*260-?F+*F88;*F+-6F9-"80821C4

C<F*26H*1F7Q- &F*:8;7*HJ- 1B-!8G- Y1<H=-L6087Q-YJ9F8JQ- !YL-PR_P-U<7H;60*6--

D84C6*0`-9,H6<5C6Fa<F7G,89<,6<E,-

- %*+*H60-$5b82H-(98FH*I8;-.R,..RSc"(W,PRPR,PSd_dVV

.R_e4e.]S- f- PRPR- (???,- W8;71F60- <78-*7- A8;C*HH89Q- 5<H-;8A<50*26H*1Fc;89*7H;*5<H*1F- ;8g<*;87-(???- A8;C*77*1F,-

Y88- =HHA7`ccGGG,*888,1;+cA<50*26H*1F7c;*+=H7c*F98N,=HC0- B1;- C1;8- *FB1;C6H*1F,

2 TRANSACTIONS ON IMAGE PROCESSING: VOL. 0, NO. 0, DECEMBER 2020

91#159-+2#,C5^3+a6/^-..C4-96#139+.-/#Z18#<417#=6.1=6=#719+12#

=-9-"#Y+4,9A#86#+2^3-+29#9:6#=6.1=6=#719+12#91#341=C.6#-#.1-4,6#

R6/=A#-2=#364<147#139+.-/#Z18#6,9+7-9+12#12#9:6#.1-4,6#Z18#91#

159-+2#-#,C5^3+a6/^-..C4-96#Z18#R6/="#e19:#1C4#+2^3-+29+2;#-2=##

139+.-/#Z18#6,9+7-9+12#P0-4+-9+12-/#139+7+W-9+12Q#3415/67,#.-2##

56#6a346,,6=#+2#9:6#;6264-/#<147##

minimize () = (−)

∗

(−) + 

∗

,#

P?Q#

-2=#86#,1/06#P?Q#-,#-#.12R=62.6^86+;:96=#R/964+2;#9-,NA#8:+.:#

150+-96,#9:6#266=#<14#,/1864#+964-9+06#2C764+.-/#,1/064,"#Y+;"#?#

P-QFP=Q#+//C,94-96#9:6#3+36/+26#<14#1C4#34131,6=#<-,9#139+.-/#Z18#

6a94-.914"#*#346/+7+2-4D#064,+12#1<#1C4#814N#-336-4,#+2#>BG@"#!2#

9:+,#6a962=6=#3-364A#86#-==+9+12-//D#3410+=6#=69-+/6=#-2-/D,6,#

1<#1C4#.12R=62.6^R/964+2;#769:1=A#-2=#-#7146#6a962,+06#,69#1<#

6a364+7629,"#Y-,9#0-4+-9+12-/#139+7+W-9+12#+2#9:+,#814N#+,#268"#

!!" f?\U"?%-_$#h#

# f6/-96=#91#1C4#346,629#814N#+,#T'bc^'g!c#>BH@A#8:+.:#C,6,#

9:6#719+12#06.914,#1<#T'bc#346=+.9+12#C2+9,#-,#,3-4,6#7-9.:6,#

91#+2+9+-/+W6#'3+.Y/18#>?K@"#_:646-,#T'bc#719+12#06.914,#-46#

.1=6=#,3-4,6/DA#9:6#719+12#R6/=#9:-9#9:6D#46346,629#PY+;"#?#5Q#+,#

-#=62,6#BV#,+;2-/"#M646<146A#86#<147-/+W6#9:6#46.1064D#1<#9:6#

C2=64/D+2;#139+.-/#Z18#R6/=#7146#<C2=-7629-//D#-,#-#R/964+2;#

3415/67#+2#9:+,#814N"#Y+4,9A#86#460+68#981#7-+2#-3341-.:6,#91#

R/964+2;#3+6.68+,6#,7119:#,+;2-/,#,C.:#-,#139+.-/#Z18#R6/=,"##

A. Edge-preserving Filtering

# *#2C7564# 1<#6=;6^346,640+2;#R/964+2;#96.:2+[C6,#:-06#5662#

34131,6=#1064#9:6#3-,9#=6.-=6,"#M6D#.-2#56#./-,,+R6=#541-=/D#

-,#+964-9+06#14#212^+964-9+06A#5-,6=#12#9:6#'C./+=6-2#14#;61=6,+.#

=+,9-2.6"#e19:#'C./+=6-2#-2=#;61=6,+.#R/964,#-064-;6#6/67629,#

9:-9#-46#26-4^5D#C,+2;#9:6+4#46,36.9+06#219+12,#1<#=+,9-2.6"#_+9:#

9:6#'C./+=6-2#=+,9-2.6A#+7-;6#6/67629,#/D+2;#12#=+`64629#,+=6,#

1<#-2#6=;6#-46#-064-;6=#91;69:64A#5C9#219#8+9:#9:6#;61=6,+.#126##

56.-C,6#9:6#981#6/67629,#-336-4#<C49:64#-3-49#C2=64#9:+,#7694+.#

P=63+.96=#+2#Y+;"#BQ"#M6#212^+964-9+06A#5+/-964-/#R/964#1<#%17-,+#

-2=#)-2=C.:+#>BI@#+,#-2#6a-73/6#1<#-#'C./+=6-2#R/964#8:646-,#

9:6#R/964,#34131,6=#+2#>BJ@F>EL@#-46#;61=6,+."#*#;6264-/+W-9+12#

1<#'C./+=6-2#-2=#;61=6,+.#R/964,#+,#9:6#;C+=6=#R/964#<4-76814N#

>E?@A#8:+.:#76-,C46,#9:6#=+,9-2.6#P;61=6,+.#14#'C./+=6-2Q#12#-#

,C33/+6=#;C+=6#,+;2-/#+2,96-=#P31,,+5/D#9:6#+23C9#+7-;6#+9,6/<Q"##

# $26#+,,C6#8+9:#5+/-964-/#14#19:64#:+;:^=+762,+12-/#O-C,,+-2#

R/964,#+,#9:6+4#:+;:#.173C9-9+12-/#.173/6a+9D"#*#2-h06#R/964+2;#

+73/67629-9+12#:-,#(

)#.173/6a+9DA#8:646##=62196,#9:6#

2C7564#1<#3+a6/,#+2#9:6#+7-;6A#-2=##9:6#R/964#4-=+C,"#g-4+,#-2=#

VC4-2=#>EB@#-..6/64-96#5+/-964-/#R/964+2;#5D#=182^,-73/+2;#9:6#

,+;2-/#1291#9:6#5+/-964-/#/-99+.6#P,3/-9QA#O-C,,+-2#R/964+2;#12#9:6#

.1-4,64#/-99+.6#P5/C4QA#-2=#C3^,-73/+2;#9:6#R/9646=#,+;2-/#P,/+.6Q#

91#341=C.6#9:6#R/964#1C93C9"#M6#,3/-9^5/C4^,/+.6#3+36/+26#+,#-/,1#

6a3/1+96=#5D#/-964#<-,9#5+/-964-/#-2=#:+;:^=+762,+12-/#O-C,,+-2#

R/964,A#,C.:#-,#9:6#O-C,,+-2#V^9466#>EE@#14#9:6#3647C91:6=4-/#

/-99+.6#>EU@#R/964,A#-//#1<#8:+.:#:-06#(

)#.173/6a+9+6,"#M6#

-=-39+06#7-2+<1/=#R/964#1<#O-,9-/#-2=#$/+06+4-#>EG@#+,#5-,6=#12#

,+7+/-4#,3/-9^5/C4^,/+.6#34+2.+3/6,"#

B. Edge-preserving Regularization

# e19:#'C./+=6-2#-2=#;61=6,+.#R/964+2;#-46#C,6=#<14#-#2C7564#

1<#+7-;6#341.6,,+2;#-33/+.-9+12,#>EH@F>EJ@A#-2=#0+,+12^46/-96=#

+2064,6#3415/67,#>?I@A#>EK@A#-/9:1C;:#126#7-D#56#569964^,C+96=#

9:-2#9:6#19:64#=6362=+2;#12#9:6#-33/+.-9+12"#T186064A#R/964+2;#

-/126#+,#911#46,94+.9+06#<14#7146#.173/6a#+2064,6#3415/67,#9:-9#

=6362=#12#6/67629^8+,6#.12R=62.6#86+;:9,"#Y14#6a-73/6A#86#

7+;:9#8-29#91#=6^86+;:9#9:6#=639:#0-/C6,#1<#1../C=6=#3+a6/,#+2#

=+,3-4+9D#7-3#62:-2.67629#9-,N,A#5C9#,+73/6#R/964+2;#3410+=6,#

21#76.:-2+,7#91#+2.14314-96#3+a6/^8+,6#86+;:9+2;"#_:+/6#,C.:#

9-,N,#.-2#56#<1476=#-,#139+7+W-9+12#3415/67,#+2,96-=A#91#,1/06#

9:67#+,#,/1864#9:-2#,+73/6#R/964+2;"##

# '=;6#346,640+2;#46;C/-4+W-9+12#.-2#56#-.:+606=#0+-#=+`64629#

769:1=,#-,#86//"#M6#212/+26-4#919-/#0-4+-9+12#46;C/-4+W-9+12#1<##

fC=+2#69#-/"#>UL@#46.1064,#-#3+6.68+,6#,7119:#,1/C9+12#56.-C,6#

+9,#

#2147#+,#7146#<14;+0+2;#918-4=,#/-4;6#=+`6462.6#+2#,+;2-/#

6/67629,#.173-46=#91#9:6#

#2147A#-2=#=16,#219#5/C4#9:6#6=;6,#

+2#9:6#,+;2-/#-,#7C.:"#T186064A#919-/#0-4+-9+12#46;C/-4+W-9+12#+,#

,1769+76,#46,94+.9+06#,+2.6#+9#.-2#+731,6#46;C/-4+9D#12/D#-.41,,#

,3-9+-//D#-=S-.629#0649+.6,#P-#3-+48+,6#)fYQ"#O+/51-#-2=#$,:64#

>U?@#;6264-/+W6#919-/#0-4+-9+12#91#-#;4-3:^/+N6#,699+2;A#-2=#,:18#

9:-9#9:+,#212/1.-/#919-/#0-4+-9+12#46;C/-4+W-9+12#+,#5626R.+-/#<14#

+7-;6#+2^3-+29+2;#-2=#=621+,+2;#3415/67,"#&60649:6/6,,A#C,+2;##

6+9:64#<147#1<#919-/#0-4+-9+12#46;C/-4+W-9+12#462=64,#9:6#+2064,6#

3415/67#212^,7119:A#8:+.:#.-2#12/D#56#,1/06=#8+9:#46/-9+06/D#

,/18#+964-9+06#,1/064,#/+N6#9:6#=C-/^341S6.9+12#-/;14+9:7#>UB@#14##

+9,#<-,9#0-4+-29,#>UE@A#>UU@"#

!!!" b(%?$-c$%(![-U!%-%$"U\-bU#(U"($!#

# e6<146#86#6a94-.9#139+.-/#Z18#<417#.1=6=#719+12A#86#,9C=D#

:18#-#0+=61#.1=64#6,9+7-96,#+9,#719+12#+2#9:6#R4,9#3/-.6i-<964#

)*+,-P,-?9+84A;878;:*F+-I0H8;*F+-1B-6-+;6J72608-*C6+8-D6E-26F-58-B62*0*H6H89-5J-8C5899*F+-H=8-*C6+8-*F-6-H=;8849*C8F7*1F60-7A628-D2EQ-D9E-6F9-<7*F+-6F-6AA;1A;*6H8-

9*7H6F28-C8H;*2,-K8-^%-?<20*986F-9*7H6F28-D2E-*7-<78B<0-B1;-I0H8;*F+-*C6+8-;8+*1F7-1B-7*C*06;-*FH8F7*HJ-62;177-89+87-G=8;867-H=8-^%-+81987*2-9*7H6F28-D9E-*7-<78B<0-

B1;-I0H8;*F+-*C6+8-;8+*1F7-1B-7*C*06;-*FH8F7*HJ-1F-H=8-76C8-7*98-1B-6F-89+8,-K8-9*7H6F28-D5E-9187-F1H-B62*0*H6H8-89+84A;878;:*F+-I0H8;*F+,#

(a) Grayscale image (b) 2D distance (c) 3D Euclidean distance (d) 3D geodesic distance

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO 3

-//A#86#.-2219#6a94-.9#139+.-/#Z18#<417#-2#-45+94-4D#,+;2-/"#_6#

218#,:18#9:-9#719+12#6,9+7-9+12#5D#-#5/1.N^5-,6=#0+=61#.1=64#

,C.:#-,#bc?A#V+4-.#-2=#T"BHUj*bc#-.9C-//D#,1/06,#9:6#%b^

P919-/^0-4+-9+12^

Q#139+.-/#Z18#6,9+7-9+12#3415/67#>?G@#8:62#

-//#9:6#5/1.N,#-46#<14.6=#91#56#1 ×1#3+a6/#+2#,+W6"#(+2.6#%b^

+,#-2#6=;6^346,640+2;#71=6/A#719+12#6,9+7-9+12#1<#5/1.N^5-,6=##

.1=64,#,+7+/-4/D#346,6406,#6=;6,A#-/56+9#8+9:#5/1.ND#-49+<-.9,#-9#

9:6#51C2=-4+6,#1<#710+2;#15S6.9,"#%1# 6a94-.9#139+.-/#Z18#<417#

-#5/1.N^5-,6=#719+12#R6/=A#+9#9:646<146#,Cd.6,#91#467106#,C.:#

-49+<-.9,#-9#9:6#15S6.9#51C2=-4+6,"#f6-=64,#<-7+/+-4#8+9:#5/1.N^

5-,6=#0+=61#.1=+2;#.-2#,N+3#9:+,#,6.9+12#12#R4,9#46-=+2;"##

A. 8e RD Optimization Framework

# !2#0+=61#.1=+2;#-33/+.-9+12,A#719+12#+2<147-9+12#+,#C,6=#<14#

719+12^.17362,-9+2;#346=+.9+12#1<#<C9C46#3+.9C46#<4-76,#C,+2;#

3460+1C,#.1=6=#<4-76,"#_+9:#346=+.9+06#.1=+2;A#12/D#346=+.9+12#

64414,#-2=#719+12#06.914,#-46#.1=6=#-2=#.177C2+.-96=A#8:+.:#

6`6.9+06/D#.17346,,6,#0+=61#=-9-"#g46=+.9+12#64414#,+;2-/,#-46#

.1=6=#+2#-#/1,,D#7-2264A#+2941=C.+2;#=+,9149+12#+2#9:6#=6.1=6=#

<4-76"#M646<146A#719+12#6,9+7-9+12#<14#0+=61#.1=+2;#:-,#9:466#

7+2+7+W-9+12#15S6.9+06,k#=6.1=6=#<4-76#=+,9149+12A#-2=#.1=+2;#

4-96,#1<#<4-76#346=+.9+12#64414#-2=#719+12#06.914,"#_6#-2-/DW6#

9:+,#4-96^=+,9149+12#139+7+W-9+12#341.6,,#8+9:#9:6#<4-76814N#1<#

.1206a#139+7+W-9+12"#

# *#.1=6=#<4-76#.-2#56#,662#-,#.1734+,+2;#346=+.9+12#C2+9,#14#

5/1.N,#1<#0-4+-5/6#,+W6A#4-2;+2;#<417#4 ×8#-2=#8 ×4#3+a6/,A#91#

64 ×64#3+a6/,"#M6#9:#5/1.N#1<#,-73/6,#

𝑖

#+2#-#.1=6=#<4-76#+,#

346=+.96=#C,+2;#9:6#.1^/1.-96=#5/1.N#

𝑖

(

𝑖

)#+2#,176#3-,9#<4-76#

94-2,/-96=#5D#-#719+12#06.914#

𝑖

∈

"#g46=+.9+12#64414,#1<#9:6#

9:#5/1.N#-46#-3341a+7-96=#8+9:#9:6#46,+=C6#,+;2-/#

𝑖

"#e19:#9:6#

46,+=C6#

𝑖

#-2=#9:6#719+12#06.914#

𝑖

#-46#,C5,6[C629/D#.1=6=#<14#

.177C2+.-9+12"##

# (C331,6#9:6#<4-76#.129-+2,##,-73/6,#-.41,,##5/1.N,"#_6#

C,6#, , ∈

𝑁

#-2=#∈

𝑃 ×2

#91#=62196#9:6#0649+.-/#,9-.N+2;##

1<#9:6#364^5/1.N#0-4+-5/6,#

𝑖

, 

𝑖

, 

𝑖

A#-2=#

𝑖

A#46,36.9+06/D"#Y14#-##

5/1.N^5-,6=#0+=61#.1=64#,C.:#-,#T'bcA#719+12#6,9+7-9+12#.-2##

56#<147C/-96=#-,#9:6#4-96^=+,9149+12#139+7+W-9+12#3415/67#

minimize 

(

, 

)

= 

(

, 

)

+ 

(



)

+ 

(



)

PBQ#

+2#8:+.:#(, )#46346,629,#9:6#=+,9149+12#1<#9:6#=6.1=6=#<4-76#

-<964#719+12^.17362,-9+2;#346=+.9+12#5D##-2=#9:6#46,+=C6##+,##

-==6="#M6#9647,#()#-2=#()#=62196A#46,36.9+06/DA#9:6#.1=6=#

/62;9:,#1<#9:6#46,+=C6##-2=#719+12#06.914,#"#M6#3-4-76964##

=69647+26,#9:6#94-=6^1`#5698662#=+,9149+12#-2=#.1=+2;#4-96"#

# M6#=6.1=6=#<4-76#=+,9149+12#PC,+2;#9:6#76-2#,[C-46=#64414Q#

.-2#56#84+9962#-,#

(, ) =

‖

() −−

‖

PEQ#

= 

‖



𝑖

(

𝑖

) −

𝑖

−

𝑖

‖











𝑑

𝑖

(𝐯

𝑖

,𝐞

𝑖

)

𝑃

𝑖=1

-2=#9:6#.1=6=#4-96#1<#46,+=C6#84+9962#-,##

() =

‖



‖

= 

‖



𝑖



𝑖

‖



𝑟

𝑖

(𝐞

𝑖

)

𝑃

𝑖=1

PUQ#

+2#8:+.:##+,#,176#6264;D^.173-.9+2;#94-2,<147"#M6#Vc%#+,#

126#313C/-4#.:1+.6#<14#

𝑖

#+2#5/1.N^5-,6=#0+=61#.1=64,#,C.:#-,#

T'bc#>BU@"#M6#.1=6=#46,+=C6##+2#9:6#=+,9149+12#9647#PEQ#7-D#

56#+296434696=#-,#\,C5,+=+W+2;]#9:6#346=+.9+12#64414#14#=6R.+9#-9#

9:6#.1,9#,36.+R6=#5D#PUQ"#&18A#9:6#.1=6=#46,+=C6#0-4+-5/6##.-2##

56#139+7+W6=#1C9#+2#-=0-2.6#<417#9:6#15S6.9+06#1<#PBQ#91#D+6/=##

() = min

𝐞

(, ) + ()#

PGQ#

‖

(() −)

‖

𝐻

= 

‖



𝑖

(

𝑖

(

𝑖

) −

𝑖

)

‖

𝐻











𝑔

𝑖

(𝐯

𝑖

)

𝑃

𝑖=1

+2#8:+.:#

‖



‖

𝐻

#=62196,#9:6#TC564#2147A#8:1,6#94-2,+9+12#31+29#

+,#-9#/2"#f6<64#91#*3362=+a#*#<14#9:6#=64+0-9+12#1<#PGQ"#

# !2#7-2D#0+=61#.1=64,A#9:6#719+12#06.914,#

𝑖

#-46#9:67,6/06,#

.1=6=#346=+.9+06/Di86#C,6#,176#

𝑖

#91#346=+.9#

𝑖

A#.1=+2;#12/D#

9:6#=+`6462.6#

𝑖

−

𝑖

"#M6#719+12#5+9^/62;9:#56.176,#

() =

‖

−

‖

= 

‖



𝑖

−

𝑖

‖











ℎ

𝑖

(𝐯

𝑖

)

𝑃

𝑖=1

PHQ#

9:-9#+,A#9:6#,C7#1<#-5,1/C96#719+12#06.914#=+`6462.6,#-.41,,#-//##

346=+.9+12#5/1.N,"#!2#T"BHUj*bc#<147,#6-.:#346=+.914#

𝑖

#-,#



𝑖

= med

𝐯

𝑗

∶ 𝑖∼𝑗







𝑗



PIQ#

+2#8:+.:#med#=62196,#9:6#.173126298+,6#76=+-2A#-2=#∼#+<##

9:6#9:#346=+.9+12#C2+9#+,#=+46.9/D#91#9:6#2149:6-,9A#2149:#14#86,9#

9:6#9:#126"#l69#C,#-2-/DW6#,C.:#-#76=+-2^5-,6=#719+12#06.914#

346=+.9+12#,.:676#<C49:64"#!<#86#,C5,9+9C96#9:6#76=+-2,#PIQ#+291#

PHQA#86#159-+2#-#919-/#0-4+-9+12#,67+^2147#1<#719+12#06.914,#12##

9:+,#346=+.914#;4-3:k#



(



)

‖

−



‖



‖

PJQ#

+2#8:+.:##+,#9:6#+2.+=62.6#7-94+a#1<#9:+,#346=+.914#;4-3:A#-2=#

#+,#-#=+-;12-/#46^86+;:9+2;#7-94+aA#8:1,6#6/67629,#-46#6+9:64#

1/3#14#1X#,66#*3362=+a#e"#Y+;"#E#0+,C-/+W6,#126#,C.:#;4-3:"#

# eD#.1294-,9A#T'bc#<147,#6-.:#346=+.914#

𝑖

#-,##



𝑖

= argmin

𝐯

𝑗

∶ 𝑖∼𝑗







𝑖

−

𝑗



PKQ#

+2#8:+.:#∼#=62196,#9:6#9:#346=+.9+12#C2+9#+,#346=+.96=#<417#

9:6#9:#126"#%D3+.-//DA#∼#+<#9:6#9:#346=+.9+12#C2+9#+,#=+46.9/D#

91#9:6#2149:6-,9#14#,1C9:86,9#1<#9:6#9:#126"#_6#.-2#6a346,,#9:6#

.1446,312=+2;#719+12#.1=+2;#.1,9#0+-#PJQA#8:646#9:6#6/67629,#

)*+,-^,->,PV]cU@'-C1H*1F-:82H1;-A;89*2H1;-+;6A=-DQP = 28E-1B-H=8-PF9-B;6C8-

1B-H=8-OW(4Y*FH80-6008Ji.-78g<8F28Q-G=8;8-:8;H*287-D91H7E-;8A;878FH-A;89*2H*1F-

<F*H7Q-6F9-89+87-D0*F87E-8NA;877-H=8-A;89*2H*1F-;806H*1F,-K8-A;89*2H*1F-+;6A=-*7-

60G6J7-<F9*;82H89-60H=1<+=-H=8-A;89*2H*1F-;806H*1F-*H780B-*7-F1H-21CC<H6H*:8,#

4 TRANSACTIONS ON IMAGE PROCESSING: VOL. 0, NO. 0, DECEMBER 2020

1<#9:6#=+-;12-/#7-94+a##-46#218#6+9:64#0#14#1"##

# !2#46-/+9DA#9:6#.1=6=#/62;9:#1<#719+12#06.914#=+`6462.6#962=,#

91#56#7146#/1;-4+9:7+.#9:-2#/+26-4#+2#9:6#7-;2+9C=6"#!964-9+06/D#

46^86+;:9+2;#9:6#

#2147#+2#PJQ#C,+2;#>UG@#.1446.9/D#71=6/,#9:6##

/1;-4+9:7+.#2-9C46#1<#9:6#94C6#.1=+2;#<C2.9+12"##

B. Relation to TV-

Optical Flow

# (C5,9+9C9+2;#9:6#=+,9149+12#PGQ#-2=#719+12#4-96#PJQ#9647,#+291#

9:6#4-96^=+,9149+12#139+7+W-9+12#3415/67#PBQ#;+06,#C,#

minimize () =

‖

(() −)

‖

𝐻

+ 

‖



‖

P?LQ#

9:-9#+,A#-#5/1.N^5-,6=A#;4-3:#%b^

#PTC564Q#719+12#6,9+7-9+12#

3415/67"#_:62#-//#9:6#346=+.9+12#5/1.N,#-46#<14.6=#91#56#1 ×1#

3+a6/,#+2#,+W6A##46=C.6,#91#+=629+9DA#-2=#3415/67#P?LQ#56.176,#

9:6#./-,,+.#%b^

#139+.-/#Z18#6,9+7-9+12#3415/67#>?G@A#>UU@"#

# *#./-,,+.#.1206a#139+7+W-9+12#-3341-.:#<14#,1/0+2;#3415/67#

P?LQ#+,#0+-#9:6#+964-9+06#34+7-/^=C-/#769:1=#>UU@"#*#0+=61#.1=64#

,C.:#-,#T"BHUj*bc#12#9:6#19:64#:-2=#,1/06,#9:6#,-76#3415/67#

5/1.N#5D#5/1.N#5D#0+,+9+2;#6-.:#346=+.9+12#5/1.N#12/D#12.6"#*9#

9:6#9:#346=+.9+12#5/1.NA#9:6#.1=64#,1/06,#9:6#3415/67##

minimize 

𝑖

(



𝑖

)

= 

𝑖

(



𝑖

)

+ 

𝑖

(



𝑖

P??Q#

91#159-+2#-#;466=D#,1/C9+12#<14#9:6#9:#5/1.N"#T186064A#86#.-2#

-/,1#9:+2N#1<#9:6#7+2+7+W-9+12#1<#9:6#,6[C62.6#(

, 

, . . . , 

𝑃

5D#9:6#0+=61#.1=64#-,#126#+964-9+12#1<#9:6#O-C,,^(6+=6/#769:1=#

<14#,1/0+2;#3415/67#P?LQ"#

!b" '%[?^g#?Y?#@(![-Y(\"?#(![#

# Y-,9#139+.-/#Z18#6a94-.9+12#6,,629+-//D#-71C29,#91#,1/0+2;#-#

.12R=62.6^86+;:96=#46;C/-4+W6=#139+7+W-9+12#3415/67"#(C.:#-#

3415/67#+,#;6264-//D#,/18#91#,1/06A#,1#86#.120649#9:6#3415/67#

91#-#R/964+2;#9-,N"#T646A#86#=606/13#1C4#\.12R=62.6^86+;:96=]#

R/964A#719+0-9+2;#+9#<417#9:6#46/-9+06#,9462;9:,#-2=#86-N26,,6,#

1<#212^+964-9+06#R/964+2;#-2=#+964-9+06#139+7+W-9+12"#

A. Non-iterative Filtering

# (C331,6#86#:-06#-2#^,-73/6#+7-;6#∈

𝑁

= 

𝐷

#8:1,6#

3+a6/#/1.-9+12,#.1446,312=#91#0649+.6,##1<#-#46.9-2;C/-4#/-99+.6#

12#9:6#^#3/-26"#m,+2;##-,#+23C9A#86#6a346,,#9:6#1C93C9#

out

1<#,176#6=;6^346,640+2;#R/964#-,#



out

= 

†

, = (),

P?BQ#

+2#8:+.:##+,#-#R/964#7-94+aA#8:1,6#6/67629,#

𝑚𝑛

#=6,.4+56#9:6#

-d2+9D#5698662#981#,+;2-/#6/67629,#

𝑚

#-2=#

𝑛

"#M+,#-d2+9D#+,##

1<962#84+9962#-,#e

−dist

A#8:646#dist#+,#9:6#=+,9-2.6#7694+.#C,6="#

# *2#6a-73/6#1<#-#R/964#5-,6=#12#9:6#'C./+=6-2#=+,9-2.6#+,#9:6#

5+/-964-/#R/964"#_6#:-06#

𝑚𝑛

= e

−|𝐩

𝑛

−𝐩

𝑚

A#8:646#



𝑛

= 



𝑛



𝑋



𝑛



𝑌



𝑛



𝑍

∈⊕

[

0,255

]

P?EQ#

+,#9:6#31,+9+12#1<#9:6#9:#3+a6/#+2#-#'C./+=6-2A#^^#,3-.6"#M6#

31,+9+12,#{

𝑛

}#.1//6.9+06/D#=6R26#-#981^=+762,+12-/#7-2+<1/=#

6756==6=#+2#9:6#9:466^=+762,+12-/#,3-.6"#

# Y14#;61=6,+.# R/964+2;A# 86# :-06#

𝑚𝑛

= e

−geod(𝐩

𝑛

,𝐩

𝑚

)

A# 8+9:#

geod(

𝑛

, 

𝑚

)A#9:6#=+,9-2.6#1<#9:6#,:1496,9#3-9:#<417#31+29#

𝑛

91#31+29#

𝑚

#12#9:6#981^=+762,+12-/#7-2+<1/="#M-9#+,A#

geod(

𝑛

, 

𝑚

) = min

𝑝,{𝐯

𝑖

}

1≤𝑖≤𝑝

: 𝐯

𝑖

∼𝐯

𝑖+1

𝐩

𝑛

=𝐯

, 𝐯

𝑝

=𝐩

𝑚





𝑖

−

𝑖+1

𝑝−1

𝑖=1

P?UQ#

+2#8:+.:#∼

′

#=62196,#9:-9##-2=#

′

#-46#=+46.9/D#26+;:514+2;#

+2#9:6#9:466^=+762,+12-/#,3-.6X#,66#Y+;"#B#<14#-2#+//C,94-9+12#1<#

9:6#'C./+=6-2#-2=#9:6#;61=6,+.#=+,9-2.6,"#

B. Filtering as Optimization

# Y417#-#;4-3:^9:61469+.#364,36.9+06A#86#.-2#9:+2N#1<##-,#9:6#

-=S-.62.D#7-94+a#1<#-#86+;:96=#;4-3:#8:1,6#0649+.6,#-46#;+062#

5D#P?EQ"#(+7+/-4/DA##.-2#56#46;-4=6=#-,#9:6#=6;466#7-94+a#1<#

9:6#;4-3:"#%1;69:64A#9:6#981#7-94+.6,#=6R26#9:6#l-3/-.+-2#>UH@#

1<#9:6#;4-3:#-,#= −"#(+2.6##+,#,D77694+.#-2=#31,+9+06#

,67+^=6R2+96A#86#7-D#-/,1#<147C/-96#6=;6^346,640+2;#R/964+2;#

1<#9:6#+7-;6##-,#9:6#;4-3:^46;C/-4+W6=#139+7+W-9+12#3415/67#

minimize 

(



)

‖

−

‖

+ 

∗

,

P?GQ#

+2#8:+.:##+,#-#46;C/-4+W-9+12#3-4-76964"#M6#,1/C9+12#1<#P?GQ#+,##

,+73/D#

opt

= (+ )

−1

"#

# %1# 46/-96#

out

#P?BQ#8+9:#9:6#,1/C9+12#

opt

#1<#P?GQA#86#-,,C76#

9:-9##:-,#5662#5+^,91.:-,9+.+W6=#-,#+2#>EK@A#>UI@#,+2.6#126#.-2#

6a3/+.+9/D#5+^,91.:-,9+.+W6##8+9:#9:6#(+2N:142#769:1=#>UJ@"#!2#

9:6#5+^,91.:-,9+.#.-,6A#86#:-06#= #,1#9:-9#

out

= #8:+/6#

= −"#!<#86#218#84+96#= 

∗

A#8:646##=62196#9:6##

6+;6206.914,#1<##-2=#= (

, 

, . . . , 

𝑁

)#=62196#9:6+4#

-,,1.+-96=#6+;620-/C6,#8+9:#0 = 

≤  ≤

𝑁

≤1A#126#,66,#

9:-9#9:6#R/964#= − :-,#9:6#6+;620-/C6,#

1 = 1 −

≥1 −

≥  ≥1 −

𝑁

≥0,#

P?HQ#

-2=#= (+ )

−1

#:-,#9:6#6+;620-/C6,##

1 =

1 + 

≥

1 + 

≥  ≥

1 + 

𝑁

≥

P?IQ#

-,,C7+2;#= 1#<14#,+73/+.+9D"#*,#-#.12,6[C62.6A#86#:-06#9:-9#

≈= 2−#-2=#

out

≈2

opt

−"#_6#=6712,94-96#,C.:#

-#46/-9+12,:+3#5698662#

out

#-2=#

opt

#+2#Y+;"#U#8+9:#-#96,9#+7-;6#

+2#9:6#.-,6#8:646##+,#9:6#5+/-964-/#R/964"#

# M6#,+7+/-4+9D#+2#9:6#,36.94-#1<##-2=##+,#3-49+.C/-4/D#6-,D#

91#,:18#8:62##+,#-#126^=+762,+12-/#O-C,,+-2#R/964A#+2#8:+.:#

(a) Input image

(b) Bilateral ﬁltered

(d) Output diﬀerence

)*+,-],-K8-1<HA<H-1B-H=8- 5*06H8;60-I0H8;-𝐀-D5E-<7*F+-I0H8;-726087-(𝜎

𝑋

, 𝜎

𝑌

, 𝜎

𝑍

) = (8, 8, 24)Q-6F9- H=8-1<HA<H-B;1C-I0H8;-𝐇 D2E,-)1;-𝐇Q- G8-IN-𝜆 = 1-6F9-<78-I0H8;-

726087-(4, 4, 18)-H1-C6N*C*j8-H=8-A863-Y!#-1B-H=8-1<HA<H-D42.5 dBE-;806H*:8-H1-H=8-5*06H8;604I0H8;89-1F8,-K8-HG1-1<HA<H7-6;8-:*;H<600J-*98FH*260-D9E,#

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO 5

.-,6##+,#9:6#=+,.4696#Y1C4+64#5-,+,#-2=#(

, 

, . . . , 

𝑁

)#+,#9:6#

<46[C62.D#46,312,6#1<#R/964#"#m,+2;#9:6#,9-2=-4=#46,C/9,#<417#

,+;2-/#341.6,,+2;#>UK@A#86#,66#9:-9#9:6#<46[C62.D#46,312,6#1<#-#

=+,.4696#126^=+762,+12-/#O-C,,+-2#N6426/##+,#



(

; 

)

= e

−𝜎

𝜉

, −≤≤,

P?JQ#

+2#8:+.:##+,#9:6#,.-/6#1<#9:6#R/964"#(36.94-/#-/+-,+2;#+2##=C6#91#

,-73/+2;#+,#26;/+;+5/6#-,#/12;#-,#> 3

−1

≈1"#!9#<1//18,#9:-9#

9:6#126^=+762,+12-/#N6426/##1<#9:6#R/964#= (+ )

−1

#:-,#

9:6#<46[C62.D#46,312,6#

(; , ) =

1 + (1 −e

−𝜎

𝜉

)

, −≤≤,#

P?KQ#

14#-#O-C,,+-2^/+N6#46,312,6#,:+<96=#C3#5D#(+ 1)

−1

# %1#94-2,<147##91#,176#O-C,,+-2^/+N6#46,312,6#



A#86#,:+<9##

=182#5D#(+ 1)

−1

#<14#-#W641#;-+2#-,#→∞A#-2=#,.-/6#+9#5-.N#

C3#5D#(+ 1)/#<14#-#C2+9#;-+2#-9#= 0"#_6# 159-+2#-#N6426/##

:-0+2;#9:6#<46[C62.D#46,312,6#





(; , ) =

(+ 1)e

𝜎

𝜉

−

, −≤≤,

PBLQ#

-,#.-2#56#064+<+6=#-/;654-+.-//D"#Y+;"#G#3/19,#9:6#46,312,6#



#-2=##

9:6#94C6#O-C,,+-2#46,312,6#"#

b" c$!)(%?!'?^L?([>"?%-Y(\"?#(![#

# $C4#15S6.9+06#+2#9:+,#814N#+,#91#,1/06#-#7146#;6264-/#<147#1<#

3415/67#P?GQA#8:+.:#+2.14314-96,#3+a6/^8+,6#86+;:9+2;"#(C.:#-#

3415/67#.-2#56#6a346,,6=#-,#

minimize () = (−)

∗

(−) + 

∗

,#

PB?Q#

+2#8:+.:#9:6#9:#6/67629#

𝑛𝑛

∈

[

0,1

]

#1<#9:6#=+-;12-/#7-94+a##

46346,629,#1C4#.12R=62.6#+2#9:6#9:#15,640-9+12#

𝑛

#1<#"#Y417#

-#)*g#6,9+7-9+12#364,36.9+06A##+,#9:6#+2064,6#0-4+-2.6#7-94+a#

3-4-76964+W+2;#9:6#+2=6362=629#O-C,,+-2#3415-5+/+9D#=62,+9+6,#

1<#9:6#15,640-9+12,##;+062##8:+/6# +,#9:6#+2064,6#.10-4+-2.6#

7-94+a#3-4-76964+W+2;#9:6#34+14#O-C,,+-2#3415-5+/+9D#=62,+9D#1<#

9:6#S1+29#C2=64/D+2;#,+;2-/"#g415/67#PB?Q#+,#[C-=4-9+.#+2#A#-2=#

+9,#./1,6=#<147#,1/C9+12#+,#

opt

= (+ )

−1

"#

A. Filtering Scalar Signals

# &-h06/D#.173C9+2;#

opt

= (+ )

−1

#46[C+46,#C,+2;#-#

2C764+.-/#769:1=#,C.:#-,#.12SC;-96#;4-=+629,A#8:+.:#+,#,/1864#

9:-2#212^+964-9+06#R/964+2;"#M646<146A#86#.120649#3415/67#PB?Q#

91#.12R=62.6^86+;:96=#R/964+2;#



out

= 

†

, = (),

PBBQ#

219+2;#9:-9#PBBQ#46=C.6,#91#P?BQ#8+9:#= "#'[C+0-/629/DA#PBBQ#

-=-39,#2147-/+W6=#.1201/C9+12#1<#n2C9,,12#-2=#_6,9+2#>GL@#91#

+2.14314-96#3+a6/^8+,6#86+;:9+2;"##

# %1#46/-96#

out

#PBBQ#91#9:6#,1/C9+12#

opt

= (+ )

−1

#1<#

PB?QA#,C331,6#9:6#.12R=62.6#86+;:9,#-46#+2+9+-//D#= "#!<#86#

,69#9:6#86+;:9#

𝑛𝑛

#-9#-2#9:#3+a6/#91#1 −

𝑛

A#9:62#86#:-06#<417#

9:6#(:647-2^)144+,12#<147C/-##

(+ )

−1

= (+ −

𝑛



𝑛



𝑛

∗

)

−1

PBEQ#

= +



𝑛



𝑛



𝑛

∗



∗

1 −

𝑛



𝑛

∗



𝑛

= + 

𝑛



𝑛



𝑛

∗

+2#8:+.:#



𝑛



𝑛

1 −

𝑛



𝑛𝑛

, 0 ≤

𝑛

≤1,#

PBUQ#

-2=#

𝑛

#+,#9:6#9:#.1/C72#1<#9:6#+=629+9D#7-94+a"#

# %:6#6[C-/+9+6,#1<#PBEQ#96//#C,#9:-9#,699+2;#

𝑛𝑛

= 1 −

𝑛

#-==,#



𝑛



𝑛



𝑛

∗

#91#A#9:6#C2+[C6#-=SC,97629#;C-4-2966+2;#9:-9#7-94+a#

(+ 

𝑛



𝑛



𝑛

∗

)#:-,#-#C2+9#418^,C7"#%:+,#-=SC,97629#+,#,7-//#

+<##:-,#-#/-4;6#6<<6.9+06#<+/964#,.-/6#,+2.6##

𝑛

∗

= 1 +73/+6,#9:6#

6/67629,#1<#

𝑛

#-46#,7-//"#_6#,+7+/-4/D#;C-4-2966#9:-9#9:6#<+/964#

7-94+a#

†

#PBBQ#:-,#-#C2+9#418^,C7#5D#2147-/+W+2;##8+9:#



†

#6a3/+.+9/D"#!2#9:6#;6264-/#.-,6A#86#.-2#.12,+=64#9:6#6<<6.9#1<#

=+<<64629#86+;:9,#-9#7C/9+3/6#/1.-9+12,#5D#C,+2;#PBEQ#+964-9+06/D#

-.41,,#"#Y+;"#H#+//C,94-96,#9:6#601/C9+12#1<#(+ )

−1

-,#126#

.:-2;6,#+2.46-,+2;#2C7564,#1<#.12<+=62.6#86+;:9,"#_6#,66#9:6#

,:-36#1<#9:6#<+/964#N6426/#467-+2,#/-4;6/D#C2.:-2;6=A#,1#9:-9#86#

.-2#-3341a+7-96#(+ )

−1

#5D#

†

#6062#+2#9:6#.-,6#8:646#

9:6#.12<+=62.6#86+;:9,#≠"#

B. Filtering Ve ct or i al Si g na l s

# c12R=62.6^86+;:96=#R/964+2;#+,#6-,+/D#6a962=6=#91#06.914+-/#

,+;2-/,"#&18A#,C331,6#= (

, . . . , 

𝑁

, 

, . . . , 

𝑁

)

∗

∈

2𝑁

#+,#

-#B^06.914+-/#,+;2-/#12#-2#^,-73/6#/-99+.6A#8:1,6#9:#0-/C6#+,#

9:6#3-+4#

𝑛

= (

𝑛

, 

𝑛

)#8+9:#.12R=62.6#

𝑛

∈

2×2

"#$26#.-2219#

)*+,-_,-";6F7B1;C*F+-H=8-B;8g<8F2J-;87A1F78-𝑔(𝜉)-H1-6-[6<77*6F40*38-1F8-G=8F-

𝜆 = 1

-DH1A-;1GE,-L8-I;7H-7=*BH-

𝑔

-91GF-5J-

(1 + 𝜆)

−1

= 0.5-B1;-6-j8;1-+6*F-67-

𝜉 → ∞

-Q-6F9-72608-*H-5623-<A-5J-

𝜆

−1

(1 + 𝜆)

-B1;-6-<F*H-+6*F-6H-

𝜉 = 0-H1-15H6*F-

ℎ



,-Y=1GF-B1;-

𝜎 = 1.0

,-(F78H-A01H7-H=8-76C8-B<F2H*1F7-1:8;-

𝜉 ∈ [−𝜋, 𝜋]

𝑔



(

𝜉

)

−

ℎ



(

𝜉

)

𝑎



(

𝜉

)

𝜎 = 1.0

)*+,-V,-?:10<H*1F-1B-H=8-_RH=-;1G-1B-(𝐂 + 𝜆𝐋)

−1

∈ 𝕊

50×50

-67-G8-982;8678-H=8-

21FI98F28-G8*+=H7-𝑐

𝑛

-B;1C-

-H1-

1 − 𝜖

𝑛

-B1;-600-

50 ≤ 𝑛 ≤ 50 + 𝑘,-K8-G8*+=H7-

1 − 𝜖

𝑛

-6;8-76CA089-B;1C-6-<F*B1;C-9*7H;*5<H*1F-1:8;-

[0,1]

,-Y=1GF-B1;-

𝜎 = 0.5-

6F9-𝜆 = 80

,-(F78H-A01H7-H=8-76C8-B<F2H*1F7-1:8;-

𝑛 ∈ [42,48]

𝑘

𝜎 = 0.5

6 TRANSACTIONS ON IMAGE PROCESSING: VOL. 0, NO. 0, DECEMBER 2020

R/964#9:6#981 .17312629,#1<##,63-4-96/D#56.-C,6#9:6D#-46#218#

.1C3/6=#0+-#

𝑛

#PC2/6,,#-//#

𝑛

#-46#=+-;12-/Q"#_6#.-2#6a346,,#9:6##

.12R=62.6#R/964+2;#1<#06.914+-/#,+;2-/,#-,#



out

= 

†

, = 

(



)

PBGQ#

+2#8:+.:#

=







=







PBHQ#

-2=#

=



(

) (

)

(

) (

)



PBIQ#

C,+2;#9:6#219-9+12#

𝑖𝑗

= 

1𝑖𝑗

, 

2𝑖𝑗

, . . . , 

𝑁𝑖𝑗

"#

# !2#9:6#06.914+-/#.-,6A#9:6#C2+9^,C7#3413649D#:1/=,#<14#9:6#981#

,+;2-/#.17312629,#,63-4-96/Dk#86#:-06#(+ )

−1



= 

-2=#(+ )

−1



= 

A#8:646#9:6#.12,9-29#

= (

∗

, 

∗

)

∗

-2=#

= (

∗

, 

∗

)

∗

"#$5,6406#9:-9#06.914+-/#.12R=62.6#R/964+2;#

PBGQ#-/,1#;C-4-2966,#9:6#C2+9^,C7#56.-C,6#

†



= 

#-2=#



†



= 

"#Y+;"#J#+//C,94-96,#9:6#601/C9+12#1<#(+ )

−1

-,#9:6#06.914+-/#86+;:9,#

𝑛

#-46#71=+R6="#M6#,:-36#1<#9:6#R/964#

N6426/#467-+2,#/-4;6/D#C2.:-2;6=A#,1#9:-9#126#.-2#-3341a+7-96#

(+ )

−1

#C,+2;#

†

#6062#8:646#9:6#.12R=62.6#86+;:9+2;##

≠A#,+7+/-4/D#91#9:6#,.-/-4#.-,6"#

# V6,3+96#9:6#,+73/+.+9DA#PBBQFPBGQ#-46#4-46/D#7629+126=#+2#9:6#

6=;6^346,640+2;#R/964+2;#/+964-9C46A#-2=#,6064-/#-C9:14,#34131,6#

<-,9#,1/064,#>UI@A#>G?@#<14#3415/67#PB?Q#+2,96-="#T186064A#6062#

<-,9#,1/064,#7C,9#60-/C-96##7C/9+3/6#9+76,#8:646-,#1C4#

-3341-.:#46[C+46,#12/D#-#,+2;/6#60-/C-9+12#1<#"#_6#-/,1#

7-N6#21#-,,C739+12,#46;-4=+2;#9:6#+=629+9D#1<#9:6#R/964#A#-2=#

+,#7146#;6264-/#9:-2#9:6#+73/67629-9+12^,36.+R.#-..6/64-9+12,#

>UI@A#>G?@"#!2#(6.9+12,#b!#-2=#b!!A#86#,:18#9:6#364<147-2.6#1<#

9:6#'C./+=6-2#-2=#9:6#;61=6,+.#R/964#0-4+-29,#1<#1C4#0-4+-9+12-/#

139+7+W64A#-,#86//#-,#9:6+4#2-h06#.1C29643-49,"#

b!" $W"('U\-Y\$L-'k"#U'"($!#

# l69#C,#218#C,6#9:6#.12R=62.6^86+;:96=#R/964+2;#<4-76814N#

<14#<-,9#139+.-/#Z18#6a94-.9+12"#_6#-,,C76#9:6#=6.1=64#:-,#SC,9#

=6.1=6=#-2#^3+a6/#.1/14#9-4;69#3+.9C46A#-2=#,176#719+12#R6/=#

= 

𝑥

, 

𝑦

∈

𝑁×2

A#8:+.:#+,#-#5D^341=C.9#1<#9:6#346=+.9+12#

341.6,,"#_6#7-D#84+96#9:6#6a94-.96=#139+.-/#Z18#R6/=#-,##



out

= 

†

, = 

(



)

PBJQ#

+2#8:+.:##+,#,176#6=;6^346,640+2;#R/964A#-2=##+,#-#=+-;12-/#

7-94+a#1<#3+a6/8+,6#.12R=62.6#86+;:9,#5-,6=A#<14#6a-73/6A#12#

9:6#,+W6#1<#9:6#346=+.9+12#C2+9,"#_6#.120649#1C4#9-4;69#3+.9C46#91#

126#+2#9:6#^^#,3-.6A#-2=#<147#9:6#0649+.6,#1<#1C4#R/964#7-94+a#

#+2#9:6#^^^^#,3-.6#-,#



𝑛

= 



𝑛



𝑋



𝑛



𝑌



𝑛



𝑍



𝑛



𝑍



𝑛



𝑍

,#

PBKQ#

9:-9#+,A#86#C,6#9:6#=6.1=6=#9-4;69#<4-76#91#;C+=6#9:6#R/964+2;#1<#

9:6#719+12#"#_6# C,6#

𝑋,𝑌

= 24#-2=#

𝑍

= 8A -2=#

𝑋,𝑌

= 96#

-2=#

𝑍

= 128#<14#1C4#5+/-964-/#-2=#9:6#;61=6,+.#769:1=,"#

# $..-,+12-//DA#-#346=+.9+12#C2+9#7-D#,94-==/6#519:#<146;41C2=#

-2=#5-.N;41C2=#15S6.9#46;+12,A#8:646#6-.:#46;+12#+,#,C5S6.9#91##

+9,#182#139+.-/#719+12"#*,,+;2+2;#9:6#719+12#1<#9:6#<146;41C2=##

P46,3"#5-.N;41C2=Q#15S6.9#91#9:6#629+46#346=+.9+12#C2+9#341=C.6,#

719+12#1C9/+64,#+2#9:6#5-.N;41C2=#P46,3"#<146;41C2=Q#46;+12#1<#

9:6#346=+.9+12#C2+9"#&-h06/D#R/964+2;#719+12#R6/=,#341=C.6=#5D##

-#0+=61#.1=64#=+`C,6,#1064#719+12#06.914#1C9/+64,#-9#9:6#15S6.9#

51C2=-4+6,A#8:+.:#5/C4,#9:6#6=;6,#1<#1C4#6a94-.96=#139+.-/#Z18#

R6/=#-,#-#46,C/9"#M646<146A#,C.:#1C9/+64,#7C,9#56#+;2146=#8:62#

6a94-.9+2;#9:6#139+.-/#Z18#R6/="#YC49:647146A#-#346=+.9+12#C2+9#

9:-9#:-,#5662#.1=6=#8+9:1C9#-2D#719+12#+2<147-9+12#7C,9#:-06#

+9,#719+12#06.914#+2^3-+296=#<417#19:64#719+12#06.914,#26-45D"#

"U/\?-(-

OEAN4SQUARED ERROR OF DECODED MOTION VECTORS IN

PREDICTION UNITS OF SIZES L×> DAND >×LE -

W&-Y*j8

QP = 22

QP = 27

QP = 32

QP = 37

4 × 8 -

8 × 8 -

4 × 16-

8 × 16-

12 × 16-

16 × 16-

8 × 32-

16 × 32-

24 × 32-

32 × 32-

16 × 64-

32 × 64-

48 × 64-

64 × 64-

.P,_S-

..,.R-

-d,]R-

-V,R^-

-_,V.-

-^,d.-

-^,PV-

-P,]_-

-.,Pd-

-.,..-

-R,VV-

-R,^P-

-R,Rd-

-R,R^-

D.^,]_E-

D..,.RE-

D..,R_E-

Dd,_^E-

DV,]eE-

D^,d.E-

D],^dE-

D.,S_E-

D.,_.E-

D.,..E-

DR,.SE-

DR,^SE-

DR,.RE-

DR,R^E--

PR,^P-

PP,_R-

._,SP-

.],SP-

..,^S-

-S,Vd-

.P,.e-

-V,VV-

-_,Vd-

-^,P_-

-.,Pe-

-P,Ve-

-R,.d-

-R,._-

DPP,P_E-

DPP,_RE-

DP_,dRE-

DPR,S^E-

D.e,RSE-

DS,VdE-

D.R,S^E-

DV,SVE-

DS,PSE-

D^,P_E-

DR,^eE-

DR,SeE-

DR,.dE-

DR,._E--

^e,R_-

]R,Vd-

P],P.-

PV,__-

PR,]d-

P^,]S-

Pd,_R-

PP,Re-

.V,R^-

-d,PP-

-.,SR-

.R,SS-

-.,eS-

-.,.R-

D^_,_RE-

D]R,VdE-

DPe,R]E-

DPS,RVE-

DP],.dE-

DP^,]SE-

D^^,_^E-

D.S,V.E-

DP.,dSE-

Dd,PPE-

Dd,RSE-

Dd,dRE-

DP,._E-

D.,.RE--

].,^^-

Vd,PS-

]],]_-

^V,d_-

]P,dV-

^e,].-

].,P^-

^R,P_-

Pe,P^-

PP,V_-

.R,d_-

.],.]-

.^,dV-

-^,de-

D^P,V^E-

DVd,PSE-

D^P,P_E-

D]V,PRE-

DPd,_SE-

D^e,].E-

D^S,eVE-

D^V,eSE-

D^R,]eE-

DPP,V_E-

D..,eSE-

DPS,RPE-

DV,P_E-

D^,deE--

U:8;6+8-

_,VP-

d,V.-

.^,_P-

.S,.R-

)*+,-d,-?:10<H*1F-1B-H=8-_RH=-;1G-1B-(𝐂 + 𝜆𝐋)

−1

∈ 𝕊

100×100

Q-67-G8-982;8678-

21FI98F28-G8*+=H7-𝐜

𝑛

-B;1C-H=8-*98FH*HJ-C6H;*N-H1-;6F91C-;6F341F8-1F87Q-G*H=-

0 ≤ ‖𝐜

𝑛

‖ ≤ 1

-B1;- 600-

50 ≤ 𝑛 ≤ 50 + 𝑘

,- Y=1GF- B1;-

𝜎 = 0.5

-6F9-

𝜆 = 4,- (F78H-

A01H-H=8-76C8-B<F2H*1F7-1:8;-𝑛 ∈ [42,58]

𝑘

𝜎 = 0.5

(a) decoded motion

(b) confidence weights

(d) extracted flow (bilateral)

)*+,-e,-$AH*260-M1G-I8097-8NH;62H89-B;1C-H=8-9821989-C1H*1F-D6E-<7*F+-H=8-+81987*2-D2E-6F9-H=8-5*06H8;60-D9E-:6;*6FH7-1B-1<;-8NH;62H1;,-L8-<78-21FI98F28-G8*+=H7-

D5E-56789-1F-H=8-7*j8-1B-H=8-A;89*2H*1F-<F*H7,-%6;38;-D;87A,-5;*+=H8;E-A*N807-*F-H=8-21FI98F28-G8*+=H-C6A-21;;87A1F9-H1-7C6008;-D;87A,-06;+8;E-G8*+=H7,-

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO 7

# !2,96-=#1<#,6-4.:+2;#6a3/+.+9/D#<14#346=+.9+12#C2+9,#9:-9#.41,,#

719+12#51C2=-4+6,A#86#7-D#C,6#9:6#15,640-9+12#9:-9#346=+.9+12#

C2+9,#-9#719+12#51C2=-4+6,#962=#91#56#,7-//64"#M+,#15,640-9+12#

-;466,#8+9:#9:6#<-.9#9:-9#<14#,7-//##+2#PBQA#+9#+,#139+7-/#91#.1=6#

9:6#,-73/6,#12#9:6#981#,+=6,#1<#9:6#719+12#51C2=-4D#C,+2;#981#

,63-4-96#,7-//64#346=+.9+12#C2+9,A#4-9:64#9:-2#-#/-4;6#346=+.9+12#

C2+9#9:-9#+2-..C4-96/D#346=+.9,#519:#,+=6,"#M646<146A#86#C,6#9:6#

,+W6#1<#346=+.9+12#C2+9,#91#=64+06#1C4#.12R=62.6#86+;:9,A#5-,6=#

12#9:6#+2064,6^0-4+-2.6#4C/6"#

# )146#,36.+R.-//DA#/69#C,#=62196#5D#

𝑛

#-2=#

𝑛

A#9:6#8+=9:#-2=#

9:6#:6+;:9A#46,36.9+06/DA#1<#9:6#346=+.9+12#5/1.N#8:+.:#.129-+2,#

9:6#9:#719+12#06.914"#_6# =6R26#

𝑛𝑛

= 

𝑛



𝑤

𝑛

,ℎ

𝑛

−2

8:646#

𝑤,ℎ

+,#9:6#64414#0-4+-2.6#1<#9:6#=6.1=6=#719+12#<14#346=+.9+12#C2+9,#

1<#,+W6#×A#-2=#

𝑛

#+,#-#5+2-4D#+2=+.-914#8:646#

𝑛

= 0#+<#9:6#

9:#719+12#06.914#+,#219#-0-+/-5/6"#_6#/6-42#9:6#0-4+-2.6,#

𝑤,ℎ

1o+26#5D#.1=+2;#9:6#94-+2+2;#0+=61#,6[C62.6,#8+9:#T'bc#-2=#

R2=+2;#9:6#76-2#,[C-46=#64414#1<#9:6#=6.1=6=#719+12#<14#6-.:#

346=+.9+12#C2+9#,+W6"#M6#719+12#64414#0-4+-2.6,#-46#3410+=6=#+2#

%-5/6#!"#T646A#86#2196#9:-9#9:6#64414#0-4+-2.6,#<14#0649+.-/#P9-//Q#

346=+.9+12#C2+9,#-46#/1864#9:-2#+2#9:6#:14+W129-/#P<-9Q#126,#8+9:#

9:6#,-76#-46-,"#Y+;"#I#,:18,#139+.-/#Z18#R6/=,#6a94-.96=#C,+2;#

9:6#.12R=62.6#86+;:9,#

𝑛



𝑤

𝑛

,ℎ

𝑛

−2

341=C.6,#./6-264#Z18#6=;6,"#

b!!" YUY"-bU#(U"($!U\-$W"(O(lU"( $ ! #

# !<#,C5^3+a6/^-..C4-96#139+.-/#Z18#R6/=,#-46#46[C+46=A#86#.-2#

C,6#-#T142^(.:C2.N^/+N6#0-4+-9+12-/#139+7+W-9+12#341.6=C46#12#

9:6#6a94-.96=#Z18#R6/="#M+,#139+7+W-9+12#341.6=C46#+964-9+06/D#

46R26,#-#Z18#R6/=#,C.:#9:-9#+9#8-43,#9:6#46<6462.6#<4-76#91#9:6##

9-4;69#126"#M6#Z18#46;C/-4+9D#9647#86#+2.14314-96#+,#9:6#212^#

/1.-/#P;4-3:Q#6a962,+12#1<#9:6#T142^(.:C2.N#>?U@#71=6/"#(C.:#

-#212^/1.-/#71=6/#341=C.6,#-#=62,6#,D,967#1<#6[C-9+12,#9:-9#+,#

,/18#91#,1/06A#6062#8+9:#Ogm#-..6/64-9+12#>?H@#14#<-,9#R/964+2;#

96.:2+[C6,#>?I@"#_6#,1/06#9:+,#,-76#=62,6#,D,967#1<#6[C-9+12,#

5D#.120649#+9#91#-#.12R=62.6^86+;:96=#R/964+2;#9-,N"#

A. 8e 1D Stereo Case

# !2#9:6#126^=+762,+12-/#.-,6A#86#-,,C76#9:-9#9:6#139+.-/#Z18#

+,#.12,94-+26=#91#56#212^W641#12/D#-/12;#9:6##=+46.9+12"#O+062#

-2#+2+9+-/#139+.-/#Z18#R6/=#

∈

𝐷

A#9:6#46<6462.6#

ref

#-2=#9:6#

9-4;69#

tar

#+7-;6,A#1C4#15S6.9+06#+,#91#R2=#-#Z18#+2.467629#∆#

,C.:#9:-9#= 

+ ∆ +,#./1,64#91#9:6#94C6#Z18"#

# Y14#,7-//#∆= −

A#86#159-+2##-,#9:6#7+2+7+W64#1<#

minimize () =

‖



𝑥

(−

) + 

𝑡

‖

+ 

∗

#

PELQ#

>?U@A#+2#8:+.:#

∗

#=62196#9:6#46,36.9+06#3-49+-/#=64+0-9+06#1<#9:6#

9-4;69#<4-76#A#-2=#86#84+96#

∗

= (

∗

)"#T646A#7-94+a##+,#

9:6#;4-3:#l-3/-.+-2#7-94+a#<417#P?GQA#-2=##+,#-#46;C/-4+W-9+12#

3-4-76964"#&12/1.-/#46;C/-4+W-9+12#:-,#-/,1#5662#.12,+=646=#+2#

-#,+7+/-4#7-2264#5D#,6064-/#-C9:14,#>?H@F>?J@"#

# %1#,1/06#PELQ#C,+2;#1C4#R/964+2;#-3341-.:A#86#84+96#PELQ#-,##

minimize 

(



)

‖



𝑥

(

−

+ 

𝑥

†



𝑡

)

‖

+ 

∗

,

PE?Q#

219+2;#9:-9#PE?Q#+,#+2#9:6#,-76#<147#-,#PB?Q"#M646<146A#PE?Q#.-2#

56#,1/06=#5D#.12R=62.6^R/964+2;#C,+2;#86+;:9,#= 

𝑥

"#!<#86#

=62196# = −

𝑥

†



𝑡

A#1C4#R/964+2;#,1/C9+12#1<#PE?Q#56.176,#

= 

†

(

+ ), = (

𝑥

)

PEBQ#

,+7+/-4/D#91#PBBQ"#(+;2-/##+,#9:6#Z18#9:-9#81C/=#56#6,9+7-96=#+<#

9:6#+7-;6#,C4<-.6#+,#/+26-4A#,63-4-96/D#+2#6-.:#418#1<#9:6#+7-;6#



tar

"#M+,#+,#+//C,94-96=#+2#Y+;"#K"#

# !2#34-.9+.6A#9:6#1C93C9##<417#PEBQ#.-2#,9+//#56#<-4#-8-D#<417#

9:6#94C6#Z18A#,1#86#+964-96#PEBQA#+2+9+-/+W+2;#

#+2#6-.:#+964-9+12#

91#9:6#1C93C9##1<#9:6#3460+1C,#126"#(C.:#-2#+964-9+12#+,#,+7+/-4#

91#9:6#+964-9+06#8-43+2;#>GB@#C,6=#+2#9:6#139+.-/#Z18#-/;14+9:7,#

>?I@A#>?K@A#>BL@A#5C9A#+2#1C4#.-,6A#86#266=#219#,1/06#-#,D,967#1<#

6[C-9+12,#91#159-+2#6-.:#"#&196#9:-9#,1/0+2;#3415/67#PELQ#.-2#

56#C246-,12-5/6#+<#9:646#+,#-#/-4;6#-71C29#1<#54+;:926,,#.:-2;6#

5698662#9:6#46<6462.6#-2=#9:6#9-4;69#<4-76,A#+2#8:+.:#.-,6A#9:6#

46/-9+12,:+3#,:182#+2#Y+;"#K#21#/12;64#:1/=,"#%1#415C,9+<D#PELQ#

-;-+2,9#54+;:926,,#.:-2;6A#86#.-2#<147#

𝑥

#-2=#

𝑡

#5-,6=#12#9:6#

,3-9+-/#;4-=+629A#-,#34131,6=#5D#g-362564;#et al.#>GB@"#

B. 8e General 2D Case

# !2#9:6#981^=+762,+12-/#.-,6A#86#-46#;+062#-2#6a94-.96=#Z18#

R6/=#

= 

0𝑥

∗

, 

0𝑦

∗



∗

"#M6#Z18#= 

𝑥

∗

, 

𝑦

∗



∗

#86#,66N#+,#9:6#

,1/C9+12#1<#

minimize

() = 

𝑥

∗



𝑥

+ 

𝑦

∗



𝑦



(

𝑥

, 

𝑦

)(−

) + 

𝑡













𝑑

(

𝐮

)

PEEQ#

)*+,-S,-(00<7H;6H*1F-1B-H=8-M1G-𝐟 = −𝐙

𝑥

†

𝐳

𝑡

-*F-H=8-1F849*C8F7*1F60-2678Q-G=8;8-

H=8-;8B8;8F28-𝑧

ref

-*7-9*7A06289-H1-H=8-08BH-5J-P-A17*H*1F7-B;1C-H=8-H6;+8H-

𝑧

tar

,-UH-

H=8-𝑛

H=-A*N80-0126H*1FQ-

𝑧

𝑥𝑛

-;8A;878FH7-H=8-DB1;G6;9E-7A6H*60-9*m8;8F28Q-6F9-

𝑧

𝑡𝑛

*7- H8CA1;60- 9*m8;8F28-𝑧

𝑛

ref

− 𝑧

𝑛

tar

,- (F- 012600J-0*F86;-;8+*1F7Q-

𝑓

𝑛

= −𝑧

𝑡𝑛

/𝑧

𝑥𝑛

-*7--

6-+119-87H*C6H8-1B-H=8-H;<8-9*7A0628C8FH-*B-H;*6F+087-𝐴

-6F9-

𝐵

-6;8-7*C*06;,#

𝑧

ref

𝑧

tar

𝑧

𝑥1

𝑧

𝑥0

𝑧

𝑡0

/𝑧

𝑥0

𝑧

𝑡0

𝑧

𝑡1

𝐴

𝐵

#



0𝑛

+ 

𝑛



𝑛

#



0𝑛



𝑛



𝑛

)*+,-.R,-[81C8H;*2-*FH8;A;8H6H*1F-1B-H=8-M1G-𝐟,-UH-H=8-𝑛H=-76CA08-0126H*1FQ-H=8-

M1G-:82H1;-𝐟

𝑛

-*7-A6;60080-H1-H=8-*C6+8-+;69*8FH-

𝐳

𝑛

-G*H=-H=8-D7*+F89E-C6+F*H<98--

−𝑧

𝑡𝑛

/‖𝐳

𝑛

‖

,-?g<*:608FH0JQ-

𝐟

𝑛

-*7-H=8-A;1b82H*1F-1FH1-

𝐳

𝑛

-1B-M1G-:82H1;7-G=*2=-

76H*7BJ- H=8- 1AH*260- M1G- 21F7H;6*FH- D967=89- 6;;1G7E,- L8- =6:8-𝐳

𝑛

= (1,2)-6F9-

𝑧

𝑡𝑛

= −3

√

Q-6F9-H=8-*F*H*60-M1G-:82H1;-

𝐮

0𝑛

= (4,1)

8 TRANSACTIONS ON IMAGE PROCESSING: VOL. 0, NO. 0, DECEMBER 2020

,+7+/-4/D#91#9:6#126^=+762,+12-/#.-,6"#g415/67#PEEQ#46=C.6,#91#

9:6#14+;+2-/#<147C/-9+12#1<#T142#-2=#(.:C2.NA#+<#9:6#l-3/-.+-2#

1364-914##+,#.12,94C.96=#<417#9:6+4#,9-2=-4=#K^31+29#l-3/-.+-2#

,962.+/#+2,96-="#M6#7-94+a#

𝑥

, 

𝑦

#+,#219#,[C-46A#5C9#126#7-D#

,9+//#84+96#9:6#/-,9#9647#1<#PEEQ#-,#

() =





𝑥

, 

𝑦

−

+ 

𝑥

, 

𝑦



†



𝑡





PEUQ#

C,+2;#9:6#<-.9#9:-9#

𝑥

, 

𝑦



𝑥

, 

𝑦



†

= "#

# g415/67#PEEQ#.-2#56#,1/06=#5D#.12R=62.6#R/964+2;#,+7+/-4/D#

91#9:6#126^=+762,+12-/#.-,6"#M6#212^+964-9+06#,1/C9+12#+,#



out

= 

†



(



+ 

)

PEGQ#

+2#8:+.:#

=







=





𝑥



𝑥



𝑦



𝑥



𝑦



𝑦



PEHQ#

-2=#

=



(

𝑥



𝑥

) 

𝑥



𝑦





𝑥



𝑦

 

𝑦



𝑦





PEIQ#

-2=# = 

𝑥

∗

, 

𝑦

∗



∗

= −

𝑥

, 

𝑦



†



𝑡

"#_6#.-2#+29643469#9:6#,+;2-/#

#-,#9:6#Z18#1<#9:6#,7-//6,9#2147#9:-9#,-9+,R6,#9:6#139+.-/#Z18#

.12,94-+29,A#8:+.:#26.6,,-4+/D#/+6,#-/12;#9:6#+7-;6#;4-=+629"##

# %1#.173C96#9:6#139+.-/#Z18#A#/69#C,#,C331,6#-9#9:6#9:#3+a6/#

/1.-9+12#(, )

𝑛

#9:-9#86#:-06#+2962,+9D#

𝑛

∈A#,3-9+-/#;4-=+629#



𝑥

, 

𝑦



𝑛

A#-2=#9:6#967314-/#=+`6462.6#

𝑡𝑛

"#!<#9:6#+7-;6#,C4<-.6#

+,#/1.-//D#/+26-4A#9:6#Z18#06.914#

𝑛

= 

𝑥

, 

𝑦



𝑛

#;+062#5D#



𝑥

, 

𝑦



𝑛

∗

−

𝑡𝑛

(

𝑥

, 

𝑦

)

𝑛

∗





(



𝑥

, 

𝑦

)

𝑛

∗

(

𝑥

, 

𝑦

)

𝑛

∗



PEJQ#

= −(

𝑥

, 

𝑦

)

𝑛

†



𝑡𝑛

/+6,#-/12;#(

𝑥

, 

𝑦

)

𝑛

#8:+/6#,-9+,<D+2;#9:6#139+.-/#Z18#.12,94-+29#

(

𝑥

, 

𝑦

)

𝑛

(

𝑥

, 

𝑦

)

𝑛

∗

+ 

𝑡𝑛

= 0#-9#(, )

𝑛

"#Y/18#06.914#

𝑛

#+,#-/,1#

9:6#15,640-5/6#.17312629#1<#9:6#94C6#Z18#-9#(, )

𝑛

#>?U@#,+2.6#

126#.-2219#15,6406#9:6#.17312629#

𝑛

⊥

1<#9:6#Z18#06.914A#-/12;#

9:6#+,1^+2962,+9D#.1291C4#

𝑥

, 

𝑦



𝑛

⊥

= (−

𝑦

, 

𝑥

)

𝑛

#2147-/#91#9:6#

;4-=+629"#M6#Z18#R6/=##.-2#56#.173C96=#6/67629^8+,6A#C,+2;#

9:6#R4,9#/+26#1<#PEJQ#<14#-//#"#_6#0+,C-/+W6##+2#Y+;"#?L"#

# !2#.1294-,9#8+9:#9:6#126^=+762,+12-/#,96461#.-,6#PEBQA#8:646#

9:6#.12R=62.6#7-94+a#+,#31,+9+06#-2=#=+-;12-/A#9:6#;6264-/#.-,6#

+201/06,#-#.12R=62.6#7-94+a#PEHQ#8+9:#1`^=+-;12-/#6294+6,"#_6#

7-D#C2=64,9-2=#PEHQ#-,#-,,+;2+2;#212^W641#86+;:9,#12/D#91#9:6#

Z18#.17312629,#

𝑛

#,C.:#9:-9#

𝑛

⊥

#-46#+296431/-96=#629+46/D#<417#

9:6#-=S-.629#Z18#06.914,"#$5,6406#86#.-2#84+96#9:6#,C5^7-94+a#

1<##9:-9#-33/+6,#91#

𝑛

#-,#

𝑛

= 

𝑛



𝑛



𝑛

∗

A#8:646#



𝑛





, 

𝑛





𝑥𝑛

−

𝑦𝑛



𝑦𝑛



𝑥𝑛



PEKQ#

,1#9:-9#9:6#7-33+2;#

𝑛



𝑛



𝑛

#R4,9#=6.1446/-96,#9:6#15,6406=#

-2=#C215,6406=#.17312629,#1<#

𝑛

#8+9:#-#419-9+12#

𝑛

∗

A#86+;:9,#

9:6#419-96=#06.914#5D#

𝑛

A#R2-//D#419-96,#5-.N#9:6#46,C/9#5D#

𝑛

91#341=C.6#

𝑛



𝑛

"#(C.:#-2#-,,+;27629#1<#W641#86+;:9#-/12;#9:6#

+,1^+2962,+9D#

𝑥

, 

𝑦



𝑛

⊥

#.-2#56#0+686=#-,#-2#+2R2+96#,7119:26,,#

34+14#-/12;#9:+,#=+46.9+12A#-2=#+,#./1,6/D#46/-96=#8+9:#9:6#./-,,+.#

14+6296=#,7119:26,,#46;C/-4+W64#1<#&-;6/#-2=#'2N6/7-22#>GE@"#

# %1# 2147-/+W6#5D#

†

A#2196#9:-9##+,#3647C9-9+12^,+7+/-4#91#-#

5/1.N^=+-;12-/#7-94+a#8:1,6#9:#5/1.N#6/67629#+,#9:6#,94C.9C46#

7-94+a#



𝑛





𝑛

∗



𝑛

∗





𝑥

 

𝑥



𝑦





𝑥



𝑦

 

𝑦





∈

2×2

PULQ#

,1#86#.-2#2147-/+W6#9:6#9:#Z18#06.914#5D#/6<9^7C/9+3/D+2;#5D##



𝑛

†

= 

𝑛



𝑛

†



𝑛

∗

"#M6#.1/C72,#1<#

𝑛

-46#981#6+;6206.914,#1<##



𝑛

A#-2=#

𝑛

#+,#-#7-94+a#1<#9:6#981#-,,1.+-96=#6+;620-/C6,"#_6##

.-2#-/,1#,C5,9+9C96#9:6#46;C/-4+W6=#+2064,6#(

𝑛

+ )

−1

#<14#9:6##

3,6C=1+2064,6#

𝑛

†

#,+2.6#-#46;C/-4+W6=#+2064,6#+,#7146#6d.+629#

91#.173C96#9:-2#9:6#3,6C=1+2064,6#126"#

# M6#212^2147-/+W6=#.12R=62.6#86+;:9,##:-06#9:6#6`6.9#1<#

-,,+;2+2;#/-4;6#R/964#86+;:9,#91#Z18#06.914,#+2#46;+12,#1<#/-4;6#

+7-;6#;4-=+629,#-4+,+2;#=C6#91#+7-;6#21+,6#14#1../C,+12,"#(C.:#

/-4;6#86+;:9,#9:C,#-,,C76#:+;:#.12R=62.6,#+2#9:6#Z18#06.914,#

1<#46;+12,#8:646#9:6D#.-2219#56#6,9+7-96=#86//"#_6#46.9+<D#9:+,#

1064^86+;:9+2;#5D#2147-/+W+2;#9:6#

𝑥

A#

𝑦

A -2=#

𝑥



𝑦

#7-94+.6,#

1<#PEHQ#5D#

𝑥

+ 

𝑦

A#,+7+/-4/D#91#9:6#=-9-#9647#2147-/+W-9+12#

1<#>GU@"#Y+;"#??#0+,C-/+W6,#9:6#6`6.9#1<#0-4+-9+12-/#139+7+W-9+12#

9:6#139+.-/#Z18#R6/="#

C. Robust Conﬁdence Filtering

# '/67629,#1<#9:6#Z18##+2#1../C=6=#46;+12,#-46#219#46/-96=#91#

9:6#94C6#Z18A#,1#9:6D#,:1C/=#56#=182^86+;:96=#<14#R/964+2;"#!2#

9:6#126^=+762,+12-/#.-,6A#86#.-2#+2.14314-96#=182^86+;:9+2;#

=+46.9/D#+291#PEBQ#C,+2;#

= 

𝑥

, = (

𝑥

)#

PU?Q#

9:646+2A#8:646#9:6#6/67629,#1<#9:6#=+-;12-/#7-94+a##-46#;+062#

5D#

𝑛𝑛

= e

−𝑧

𝑡𝑛

/2𝜎

#<14#-#;+062#,.-/6#3-4-76964#"#T646A##.-2#

56#46;-4=6=#-,#9:6#!fl(#86+;:9,#<14#9:6#=-9-#9647#1<#PE?Q#8:62#

9:6#_6/,.:#/1,,#+,#C,6=#+2,96-=#1<#9:6#,[C-46=#126#>GG@"#_6#.-2#

415C,9+<D#981^=+762,+12-/#R/964+2;#PEGQ#,+7+/-4/D#5D#86+;:9+2;#

-//#1..C4462.6,#1<#

𝑥

A#

𝑦

#-2=#

𝑥



𝑦

#+2#PEHQ#5D#"#

# !9#+,#-/,1#31,,+5/6#9:-9#981#26-45DA#,+7+/-4/D#.1/146=#,-73/6,#

56/12;#91#=+`64629#15S6.9,A#6-.:#8+9:#+9,#182#719+12"#Y+/964+2;#

9:6#Z18#5-,6=#12#.1/14#,+7+/-4+9D#-/126#+,#9:C,#219#415C,9"#$26#

.-2#-C;7629#.1/14#,+7+/-4+9D#5D#9:6#,+7+/-4+9D#1<#9:6#Z18#<417#

9:6#3460+1C,#8-43+2;#,963#91#415C,9+<D#9:6#R/964"#_6#+2.14314-96#

-#_6/,.:^/1,,^5-,6=#Z18#,+7+/-4+9D#=+46.9/D#+291#7-94+a##PBJQ#

(a) initial extracted flow

(b) optimized (geodesic)

(d) ground truth flow

)*+,-..,-$AH*260-M1G-I8097-A;19<289-<7*F+-H=8-+81987*2-D5E-6F9-H=8-5*06H8;60-D2E-:6;*6FH7-1B-1<;-B67H-:6;*6H*1F60-1AH*C*j8;,-'1CA6

;89-G*H=-H=8-*F*H*60-8NH;62H89-M1G--

D6EQ-1<;-:6;*6H*1F600J-1AH*C*j89-1AH*260-M1G-I8097-D5EQ-D2E-6;8-20178;-H1-H=8-+;1<F9-H;<H=,-

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO 9

5D#=6R2+2;#9:6#0649+.6,#1<##C,+2;#



𝑛

= 



𝑛



𝑋



𝑛



𝑌



𝑛



𝑈



𝑛



𝑈



𝑛



𝑍



𝑛



𝑍



𝑛



𝑍

,#

PUBQ#

+2#8:+.:#

𝑛

= (

𝑛

, 

𝑛

)#+,#9:6#9:#06.914#1<#9:6#Z18#R6/=#<417#

9:6#3460+1C,#+964-9+12A#-2=#

𝑈

#+,#-#,.-/6#3-4-76964"##

b!!!" 'kW?#(O?!"U\-#?Y&\"Y#

# %1# 0-/+=-96# 1C4#.12R=62.6^86+;:96=#R/964+2;#<147-/+,7A#86#

C,6#9:6#313C/-4#)g!^(+296/#139+.-/#Z18#=-9-,69#>BE@#.129-+2+2;##

BE#2-9C4-/+,9+.#0+=61#,6[C62.6,#8+9:#;41C2=#94C9:#139+.-/#Z18,#

<14#,C..6,,+06#3-+4,#1<#<4-76,"#_6#3410+=6#:646#46,C/9,#12/D#<14#

9:6#?U#/12;64#,6[C62.6,A#6-.:#1<#8:+.:#.129-+2,#GL#<4-76,"#_6#

C,6#9:6#3647C91:6=4-/#/-99+.6#R/964#>EU@#<14#9:6#5+/-964-/#0-4+-29#

1<#.12R=62.6#R/964+2;A#-2=#9:6#=17-+2#94-2,<147#R/964#>EL@#<14#

9:6#;61=6,+.#0-4+-29"#*//#9+7+2;#46,C/9,#-46#159-+26=#12#-#,+2;/6#

.146#1<#9:6#B"I#OTW#!296/#c146#+G#341.6,,14#P+)-.#)+=#BL??Q"#

A. Fast Optical Flow Extraction (FOFE)

# M6#?B#0+=61#,6[C62.6,#8646#R4,9#.1=6=#C,+2;#9:6#/18^=6/-D#

.12R;C4-9+12#1<#9:6#T'bc#46<6462.6#,1<98-46#P7-+2A#g^<4-76,#

12/DQ#-9#QP = 22, 27, 32, 37"#m2=64#9:+,#.12R;C4-9+12A#T'bc#

6,9+7-96,#9:6#719+12#<14#6-.:#3-+4#(

𝑡+1

, 

𝑡

)#1<#<4-76,#8:646-,#

9:6#(+296/#=-9-,69#.129-+2,#9:6#;41C2=#94C9:#719+12#12/D#<14#9:6##

<4-76#3-+4,#(

𝑡

, 

𝑡+1

)"#M646<146A#86#.1=6#9:6#0+=61#,6[C62.6,#

+2#9:6#46064,6#14=64#<14#9:+,#6a364+7629"#

# !2#%-5/6#!!A#86#3410+=6#9:6#64414#1<#9:6#6a94-.96=#139+.-/#Z18#

R6/=,"#Y14#.173-4+,12A#86#+2./C=6#9:6#64414#1<#Z18,#6,9+7-96=#

12#9:6#=6.1=6=#<4-76,#C,+2;#'3+.Y/18#>?K@A#V+,.4696Y/18#>B?@#

-2=#YC//Y/18#>BB@A#-//#1<#8:+.:#,1/06#-#3415/67#,+7+/-4#91#PEEQ#

5C9#C,+2;#=+`64629#769:1=,"#M6#62=^31+29#64414,#1<#9:6#T'bc#

=6.1=6=#719+12#-46#-064-;6=#12/D#1064#9:6#-46-,#8:646#719+12#

3-4-76964,#-46#346,629"#M6#'C./+=6-2#P5+/-964-/Q#0-4+-29#1<#1C4##

769:1=#C,6,#9:6#R/964#,.-/6,#

𝑋,𝑌

= 24#-2=#

𝑍

= 8#8:+/6#<14#

9:6#;61=6,+.#0-4+-29#

𝑋,𝑌

= 96#-2=#

𝑍

= 128"#*//#3-4-76964,#

1<#9:6#19:64#769:1=,#-46#,69#91#9:6+4#=6<-C/9#(+296/#,699+2;,"#$C4#

6a94-.96=#719+12#R6/=,#:-06#,+7+/-4#-..C4-.D#-,#'3+.Y/18#-2=#

V+,.4696Y/18"#_6#15,6406#9:-9#9:6#'C./+=6-2#P5+/-964-/Q#0-4+-29#

1<#1C4#769:1=#+,#,/+;:9/D#569964#9:-2#9:6#;61=6,+.#126#-.41,,#-//#

QP,"#%-5/6#!!!#346,629,#9:6#4C22+2;#9+76,#1<#9:6#981#0-4+-29,#1<#

1C4#6a94-.914#-2=#9:6#19:64#769:1=,"#_6#=62196#9:6#9+76#-,#F#+<#

9:6#769:1=#=16,#219#4C2#-9#-#3-49+.C/-4#46,1/C9+12"#_6#0+,C-/+W6#

9:6#6a94-.96=#Z18#R6/=,#-2=#9:6+4#64414,#+2#Y+;"#?B"##

B. Fast Va ria tio nal Optimization (FVO)

# _6#218#.173-46#9:6#-..C4-.D#-2=#9:6#4C22+2;#9+76#1<#Yb$#

PEGQ#-;-+2,9#9:6#2-h06#.12SC;-96^;4-=+629,#,1/C9+12#1<#PEEQ"#M6#

+2+9+-/#719+12#

#+,#,69#91#9:6#1C93C9#1<#9:6#'C./+=6-2#0-4+-29#1<#

1C4#139+.-/#Z18#6a94-.914#+2#519:#.-,6,"#_6#C,6#9:6#R/964#,.-/6,#



𝑋,𝑌

= 64A#

𝑍

= 192#-2=#

𝑈

= 1 + #<14#9:6#;61=6,+.#0-4+-29#

1<#Yb$#-2=#86#C,6#

𝑋,𝑌

= 64A#

𝑍

= 12#-2=#

𝑈

= 0.5 + 0.5#

<14#1C4#5+/-964-/#0-4+-29A#8:646##+,#9:6#4119#76-2#,[C-46#1<#9:6#

7-;2+9C=6,#1<#9:6#+2+9+-/#Z18#06.914,"#%1# 415C,9+<D# 9:6#139+.-/#

Z18#6,9+7-9+12#-;-+2,9#+//C7+2-9+12#.:-2;6#5698662#9:6#9-4;69#

-2=#9:6#46<6462.6#<4-76,A#86#.12,94C.9#

𝑥

A#

𝑦

#-2=#

𝑡

#C,+2;#9:6#

;4-=+629#1<#9:6#9-4;69#-2=#46<6462.6#+7-;6,#-,#=+,.C,,6=#6-4/+64#

+2#(6.9+12#b!!"#M6#+964-9+06A#0-4+-9+12-/#139+7+W64#1<#'3+.Y/18#

P-/,1#C,6=#5D#YC//Y/18Q#,+7+/-4/D#C,6,#;4-=+629#+7-;6,"#_6#C,6#

9:466#8-43+2;#,963,#<14#-//#769:1=,"#

# Y14#9:6#2-h06#,1/C9+12#1<#PEEQA#9:6#.12SC;-96#;4-=+629#769:1=#

60-/C-96,#9:6#7-33+2;##6d.+629/D#<14#6-.:#+964-9+12#5D#

C,+2;#9:6#<-.9#9:-9#= −A#-2=#9:-9#9:6#7-33+2;##

.-2#56#60-/C-96=#C,+2;#-#<-,9#R/964#+73/67629-9+12"#_6#R2=#9:6#

139+7-/#R/964#,.-/6,#

𝑋,𝑌

A#

𝑍

#<14##-2=#3-4-76964##8+9:#;4+=#

,6-4.:#12#9:6#?B#0+=61#,6[C62.6,"#M6#p-.15+#346.12=+9+1264#+,#

C,6=#91#-..6/64-96#2C764+.-/#.12064;62.6"#%-5/6#!b#3410+=6,#-#

"U/\?-((-

UVERAGE END4POINT ERROR OF THE FLOW EXTRACTED FROM DOR ESTIMATED ONE -

>?@'4CODED VIDEO SEQUENCES, ULL METHODS USED WITHOUT VARIATIONAL OPTIMIZATION,-

Y8g<8F28-

QP = 22

QP = 27-

QP = 32-

QP = 37-

$H=8;-C8H=197-

$<;7

$H=8;-C8H=197-

$<;7-

$H=8;-C8H=197-

$<;7-

$H=8;-C8H=197

$<;7-

(F*H

%*72

?A*2

)<00

?<2

[81

(F*H

%*72

?A*2

)<00

?<2

[81

(F*H

%*72

?A*2

)<00

?<2

[81

(F*H

%*72

?A*2

)<00

?<2

[81

6008J.-

6008JP-

6C5<7=e-

56C511.-

56C511P-

56F96+8.-

56F96+8P-

26:8]-

C6;38HP-

C1<FH6*F.-

7=6C6FP-

7=6C6F^-

7088A*F+.-

H8CA08P-

R,VR-

R,d.-

.,d^-

R,_^-

P,]^-

.,ed-

R,dS-

V,SS-

.,P.-

.,RV-

R,]S-

R,_P-

R,]]-

^,eS-

R,_d-

R,_S-

0.61

R,e.-

.,ed-

1.11

0.57

3.79

R,dd-

R,e_-

R,]^-

R,_R-

R,]e-

2.46

R,ed-

R,Vd-

R,e_-

R,de-

.,SR-

.,._-

R,V^-

],^R-

.,.^-

R,d^-

R,_.-

R,_S-

R,]^-

P,__-

.,._-

.,.S-

R,eR-

.,PV-

.,Se-

.,]P-

R,S.-

],RR-

.,Re-

.,._-

R,d_-

.,RS-

.,R_-

P,dV-

0.33

0.43

.,RR-

R,]_-

1.53

.,PS-

R,VR-

],_S-

0.85

0.72

R,^_-

0.33

0.28

P,_^

R,]R-

R,]V-

.,._-

0.43

.,eV-

.,Pe-

R,d^-

],S.-

0.85

R,SV-

0.34

R,^_-

0.28

P,V]

R,V]-

R,S.-

.,dP-

R,_e-

P,].-

P,.R-

.,RR-

e,P.-

.,^P-

.,PV-

R,VR-

R,VP-

R,_]-

^,dS-

R,V.-

R,VV-

0.70

R,eP-

.,d^-

1.33

0.63

],V.-

R,Se-

R,S.-

R,_P-

R,_V-

R,__-

2.64

R,eS-

R,e^-

R,d.-

R,de-

.,S_-

.,^_-

R,Ve-

],d^-

.,.d-

0.90

R,_d-

R,VP-

R,]d-

P,e.-

.,P.-

.,P^-

R,ed-

.,PV-

P,R^-

.,VP-

R,S_-

4.47

.,.e-

.,^.-

R,SP-

.,.]-

.,Rd-

^,R^-

0.37

0.52

.,R.-

R,]d-

1.56

.,VR-

R,eR-

_,Rd-

0.96

R,S.-

0.44

0.41

R,^V-

2.64

R,]P-

R,_]-

.,P_-

0.47

P,P^-

.,_V-

R,eR-

_,^d-

R,SS-

.,Re-

0.44

R,]P-

0.3]-

P,VS-

R,eV-

.,.R-

P,RR-

R,V_-

P,]e-

P,]R-

.,.]-

e,d^-

.,]^-

.,]P-

R,ee-

R,d]-

R,e^-

],.d-

R,eR-

R,dP-

0.84

R,e]-

.,de-

.,VP-

0.78

_,VS-

1.06

.,RV-

R,Ve-

R,ee-

R,eP-

2.86

R,d]-

R,SS-

R,dd-

P,RR-

1.59

R,eS-

_,_e-

.,P_-

1.05

R,eR-

R,ee-

R,VP-

P,S.-

.,^R-

.,^]-

R,Sd-

.,PS-

P,.d-

.,SP-

.,RV-

5.47

.,P_-

.,]V-

.,Re-

.,^.-

.,PR-

^,P_-

0.47

0.68

.,PR-

0.54

1.63

.,ed-

R,eS-

_,S^-

.,Re-

1.05

R,_S-

R,V.-

R,_P-

P,SR-

R,_.-

0.68

.,^S-

0.53

.,de-

.,e^-

0.78

V,P.-

.,Rd-

.,.S-

0.58

0.60

0.49

P,SR-

R,de-

.,^e-

P,]V-

R,eV-

P,_]-

P,d^-

.,^]-

d,ed-

.,__-

.,VP-

R,S]-

.,P]-

R,SS-

],]_

R,d^-

.,RS-

.,_]-

R,dR-

P,._-

P,Re-

.,R.-

e,^.-

.,PV-

.,^.-

R,dV-

.,P.-

.,RR-

^,]^

R,S_-

.,R]-

.,]d-

R,SP-

P,RS-

1.98

0.95

6.72

.,^S-

1.24

R,d]-

.,.]-

R,SP-

^,PS

.,]]-

.,_]-

.,_d-

.,^^-

P,PR-

P,^_-

.,Pd-

e,R^-

.,]P-

.,e.-

.,P^-

.,Vd-

.,]]-

^,e_

0.59

R,SP-

1.80

0.62

1.85

P,P.-

R,SS-

e,.S-

.,PV-

1.24

R,e_-

R,Sd-

R,eV-

3.26

R,VP-

0.88

.,d.-

R,V^-

.,Sd-

P,..-

R,SV-

e,P.-

1.24

.,^]-

0.72

0.92

0.70

^,PS-

6:8;6+8-

.,Ve-

1.09

.,PP

.,]d-

1.09

.,.S

.,ed-

.,P^-

.,^P

.,_S-

1.22

.,^P-

.,Sd-

.,]]-

.,]d-

.,eS-

1.41

.,]e-

P,Pe

.,d_

.,ed

P,.]

1.74

"U/\?-(((-

UVERAGE RUNNING TIMES OF OUR EXTRACTOR AND OTHER-

OPTICAL FLOW METHODS ON A P,e [>Z (NTEL 'ORE I_ WROCESSOR-

O8H=19-

1024 × 436-

1280 × 720-

1920 × 1080-

4096 × 2160-

$H=8;7

%*72;8H8)01G-

?A*2)01G-

)<00)01G-

- ^^,_-782-

- P^,e-782-

- Pe,_-782

- VS,_-782-

- P..,S-782-

- .VV,^-782

- .Vd,S-782-

$<;7

?<20*986F-

[81987*2

- R,V_-782

0.28 sec-

- .,.e-782

0.42 sec-

- P,^d-782

0.86 sec-

- d,e_-782-

3.55 sec-

U22808;6H*1F-

^_n.PR×-

- VRn_RR×-

-eRn.S_×-

10 TRANSACTIONS ON IMAGE PROCESSING: VOL. 0, NO. 0, DECEMBER 2020

.173-4+,12#1<#9:6#62=^31+29#64414,#1<#9:6#Z18,#159-+26=#5D#9:6#

'C./+=6-2#-2=#9:6#;61=6,+.#0-4+-29,#1<#Yb$A#-2=#9:6#.12SC;-96#

;4-=+629#P2-h06Q#.1C29643-49,"#_6#15,6406#9:-9#9:6#139+7+W-9+12#

769:1=#:-,#/+99/6#+73-.9#12#9:6#64414#1<#9:6#159-+2#Z18A#<C49:64#

.1441514-9+2;#1C4#R/964#46,312,6#-2-/D,+,#+2#(6.9+12#!b"#_6#/+,9#

+2#%-5/6#bA#9:6#4C22+2;#9+76,#1<#9:6#'C./+=6-2#-2=#9:6#;61=6,+.#

Yb$A#-2=#9:6+4#2-h06#.12SC;-96^;4-=+629#.1C29643-49,#P46,+=C-/#

2147#91/64-2.6#1<#10

−6

#C,6=Q"#_6#.-2#15,6406#9:-9#Yb$#+,#?FJ#

9+76,#<-,964#9:-2#+964-9+06#769:1=,#P9:6#0-4+-9+12-/#139+7+W64#1<#

'3+.Y/18A#'C./+=6-2#-2=#;61=6,+.#769:1=,#5-,6=#12#.12SC;-96#

;4-=+629,Q"#M6#'C./+=6-2#0-4+-29#1<#Yb$#+,#,/1864#3C46/D#=C6#

91#9:6#+73/67629-9+12#1<#9:6#5+/-964-/#R/964#C,6=#>EU@"#$26#7-D#

C,6#-#7146#46.629A#<-,9#5+/-964-/#R/964#+73/67629-9+12#>GH@A#>GI@#

91#,366=#C3#9:6#5+/-964-/#0-4+-29#1<#1C4#-3341-.:"#Y+;"#?B#,:18,#

9:6#Z18#R6/=,#-2=#64414,#341=C.6=#5D#;61=6,+.#Yb$"#

!q" c$!'\&Y($!#

# !2#9:+,#814NA#86#346,6296=#9:6#<-,9#139+.-/#Z18#6a94-.914#<14#

.17346,,6=#0+=61A#-#212^+964-9+06A#6=;6^346,640+2;#R/964#8:+.:#

.-2#-==+9+12-//D#+2.14314-96#3+a6/8+,6#.12R=62.6#86+;:9,"#M6#

6a94-.914#341=C.6,#139+.-/#Z18#R6/=,#1<#:+;:#-..C4-.D"#%1#:-06##

,C53+a6/#Z18#-..C4-.DA#86#-/,1#C,6=#1C4#212^+964-9+06#R/964+2;#

<4-76814N#91#,1/06#-#T142^(.:C2.N^9D36#3415/67"#_6#56/+606#

9:-9#19:64#0+=61^46/-96=#-33/+.-9+12,#,C.:#-,#-.9+12#46.1;2+9+12#

-2=#15S6.9#=696.9+12#.-2#56#<-.+/+9-96=#5D#C,+2;#1C4#-3341-.:#+<#

9:6#0+=61#,6[C62.6#+,#-/46-=D#-0-+/-5/6#+2#-#.17346,,6=#<147-9#

,C.:#-,#T'bc#14#T"BHUj*bc"#

*WW?!%(k-*#

$W"(O(l(![-$&"-">?-f?Y(%&U\#

# %1# 139+7+W6#1C9#9:6#.1=6=#46,+=C-/#0-4+-5/6##+2#PBQA#86#R4,9#

6a346,,#PEQ#-,#

(, ) =

‖

(() −−)

‖

PUEQ#

C,+2;#9:6#+20-4+-2.6#1<#9:6#

#2147#91#9:6#149:1;12-/#94-2,<147#

A#8:+.:#+,#9:6#Vc%#+2#1C4#.-,6"#m,+2;#9:6#.:-2;6#1<#0-4+-5/6,#

= A#86#84+96#9:6#R4,9#/+26#1<#PGQ#-,#



(



)

= min

𝐳





(

, 

)

+ 

(



)

PUUQ#

+2#8:+.:#



(, ) =

‖

(() −) −

‖

#-2=#() =

‖



‖

# M6#7+2+7+W-9+12#+2#PUUQ#+,#,63-4-5/6#-.41,,#9:6#.17312629,#

#1<#A#-2=#+,#+2=6362=629#1<#(() −)"#M646<146A#86#266=#

12/D#.12,+=64#9:6#,.-/-4#139+7+W-9+12#



(



)

= min

𝑧

(

−

)

+ 



PUGQ#

+2#8:+.:##46346,629,#-2D#.17312629#1<#= (() −)"#M6#

,1/C9+12#1<#PUGQ#+,#

min

= shrink(, /2)A#8:646#

shrink

(

, 

)



− if > +

+  if < −

0 if −≤≤+

PUHQ#

+,#N2182#-,#9:6#,:4+2N-;6#<C2.9+12"#(C5,9+9C9+2;#

min

#5-.N#+291#

9:6#4+;:9^:-2=#15S6.9+06#<C2.9+12#1<#PUGQ#;+06,#C,

() =





≤/2





−

/4 > /2

PUIQ#

9:-9#+,A#9:6#TC564#<C2.9+12#8+9:#9:6#94-2,+9+12#31+29#-9#/2"#M6#

,C7#

∑

( )

𝑡

#9:62#.1446,312=,#91#9:6#TC564#2147#+2#PGQ"#

*WW?!%(k-e#

%$"U\-bU#(U"($!-U!%-">?-)?%(U!#

# $26#.-2#46/-96#919-/#0-4+-9+12#46;C/-4+W-9+12#91#46;C/-4+W-9+12#

<417#9:6#76=+-2"#l69#C,#=62196#5D#

𝑖

(

𝑖

)A#,176#,94+.9/D#.1206a##

=+`64629+-5/6#<C2.9+12#91#56#7+2+7+W6=A#8+9:#9:6#46;C/-4+W-9+12#



𝑖

(

𝑖

) =

∑ |



𝑖

−

𝑖𝑘

𝑘=1

"#_6#7-D#-,,C76#9:-9#(

𝑖1

, 

𝑖2

, 

𝑖3

)#+,#

-#212^=6.46-,+2;#,6[C62.6A#,C.:#9:-9#+9,#76=+-2#+,#-/8-D,#

𝑖2

"##

# l69#C,#=62196#9:6#919-/^0-4+-9+12^46;C/-4+W6=#,1/C9+12#5D#



𝑖

𝛾

= argmin

𝑣

𝑖



𝑖

(

𝑖

) + (1/)

𝑖

(

𝑖

PUJQ#

+2#8:+.:##+,#,176#46;C/-4+W-9+12#3-4-76964"#$26#.-2#46/-96#9:6#

76=+-2^46;C/-4+W6=#,1/C9+12#



𝑖

opt

= argmin

𝑣

𝑖



𝑖

(

𝑖

) +



𝑖

−

𝑖2

PUKQ#

91#9:6#919-/#0-4+-9+12#46;C/-4+W6=#126#PUJQ#-,#



𝑖

opt





𝑖

if 

𝑖

∈(

𝑖1

, 

𝑖3

)



𝑖

if 

𝑖

∈(−∞, 

𝑖1

] ∪[

𝑖3

, ∞)

PGLQ#

-,#+,#,+7+/-4/D#=+,.C,,6=#+2#>GJ@"#

# !2#9:6#.1296a9#1<#T"BHUj*bc#719+12#6,9+7-9+12A#9:6#0-4+-5/6#



𝑖

#46346,629,#-#719+12#06.914#.17312629#1<#9:6#9:#5/1.NA#91#56#

.1=6=#346=+.9+06/D#<417#9:6#76=+-2#1<#(

𝑖1

, 

𝑖2

, 

𝑖3

)A#8:+.:#-46#

9:67,6/06,#0-4+-5/6,#=6219+2;#719+12#06.914#.17312629,#<417#

"U/\?-(@-

UVERAGE OPTICAL FLOW END4POINT ERROR DPIXELSE -

ON YINTEL SEQUENCES AFTER VARIATIONAL OPTIMIZATION-

Y8g<8F28-

QP = 22-

QP = 32-

$H=8;7

$<;7-

$H=8;7-

$<;7-

?A*2

?<2

[81

?<2

[81

?A*2

?<2

[81

?<2

[81

6008J.-

6008JP-

6C5<7=e-

56C511.-

56C511P-

56F96+8.-

56F96+8P-

26:8]-

C6;38HP--

C1<FH6*F.-

7=6C6FP-

7=6C6F^-

7088A*F+.-

H8CA08P-

0.27

R,^^-

R,de-

R,^e-

.,]]-

.,RP-

0.42

],.]-

0.74

0.57

0.27

R,PS-

R,P^-

P,^^

R,^R-

R,^]-

R,eS-

R,^e-

1.42

R,SV-

R,]^-

4.09

R,eV-

R,V^-

R,Pd-

R,PP-

2.29

R,^R-

R,^^-

0.77

R,^e-

.,]^-

0.95

R,]^-

],.]-

R,e_-

R,V.-

0.27

0.26

0.20

2.29

R,PS-

R,^^-

R,dR-

R,]R-

.,]e-

.,R_-

R,]_-

],.]-

R,ee-

R,VR-

0.27

R,Pe-

R,PP-

P,^]

R,Pd-

0.32

R,d.-

0.36

.,]]-

.,RR-

R,]^-

],.]-

R,e_-

R,_S-

0.27

R,^R-

R,P.-

P,^.-

R,]]-

R,V_-

.,._-

0.49

.,_d-

.,V.-

R,VS-

_,Ve-

R,SS-

R,Se-

R,_d-

R,V]-

R,__-

P,ee

R,]^-

R,_S-

.,R]-

R,_.-

1.54

.,]S-

0.66

5.50

R,Se-

R,_P-

R,_]-

R,]V-

P,Vd-

R,]^-

R,_d-

1.03

0.49

1.54

1.47

R,VV-

_,_P-

R,Se-

0.96

0.50

0.51

R,]P-

2.64

R,]^-

R,_d-

.,RV-

R,_P-

.,_d-

.,V^-

R,VS-

_,_d-

R,SS-

R,Se-

R,_]-

R,__-

R,]V-

P,e^-

0.41

0.56

.,R]-

R,_R-

1.54

.,_V-

0.66

_,_e-

0.96

R,_^-

R,__-

0.43

P,eR-

6:8;6+8-

R,S_-

0.94

R,SV

0.94

.,^]-

.,Pd-

1.27

.,^.-

.,Pd-

"U/\?-@-

UVERAGE RUNNING TIMES OF THE FAST VARIATIONAL OPTIMIZER -

AND NAÏVE CONJUGATE GRADIENTS ON A P,e [>Z (NTEL 'ORE I_

WROCESSOR-

O8H=19-

1024 × 436-

1280 × 720-

1920 × 1080

4096 × 2160

$H=8;7

?A*2)01G-

?<20*986F-

[81987*2-

R,dR-782-

.^,.-782--

P,R_-782-

.,V_-782-

Pe,R-782--

],P^-782-

^,e.-782-

VR,d-782-

S,_P-782

PSR,-782-

]V,V-782

$<;7

?<20*986F-

[81987*2-

P,SR-782-

0.35 sec-

V,^R-782-

0.72 sec-

.],V-782-

1.92 sec-

eR,R-782-

9.60 sec-

U22808;6H*1F-

R,Pdn^e×-

R,PVn^d×-

R,P_n^P×

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO

Decoded frame

Decoded motion

Optical ﬂow extraction

Variational optimized

)*+,-.P,-$AH*260-M1G-I8097-DH1A-;1GE-6F9-H=8-21;;87A1F9*F+-M1G-8;;1;-D51HH1C-;1GE-A;19<289-6BH8;-H=8-M1G-8NH;62H*1F-6F9-:6;*6H*1F60-1AH*C*j6H*1F-7H6+87,-L8-

7=1G-H=8-+;1<F9-H;<H=-M1G-*F-H=8-51HH1C-08BH,-L=*H8;-A*N807-21;;87A1F9-H1-7C6008;-M1G-:82H1;7,-?;;1;-C6A7-6;8-20*AA89-6H-H=8-M1G-8;;1;-C6+F*H<98-1B-],-Y=1GF-

B1;-QP = 22,-L8-<78-H=8-5*06H8;60-:6;*6FH-1B-1AH*260-M1G-8NH;62H*1F-6F9-H=8-+81987*2-:6;*6FH-1B-:6;*6H*1F60-1AH*C*j6H*1F,-

TRANSACTIONS ON IMAGE PROCESSING: VOL. 0, NO. 0, JANUARY 2019

9:6#9:#5/1.N"#(C77+2;#

𝑖

#1064#= 1, . . . , #341=C.6,#PJQ#-,#

46[C+46="#

f?)?#?!'?Y#

- o.p- U,-[*62=8HH*Q-O,-'6CA6F*Q-6F9-@,-"1;;8Q-qK8-<78-1B-1AH*260-M1G-B1;-;169-

F6:*+6H*1FQr-3777,8$-(&4,9#:#/4,;./#<4Q-:10,-.]Q-F1,-.Q-AA,-^]n]dQ-)85,-

.SSd,-

- oPp- Y,-l*F++Q-%,-Y26;6C<jj6Q-Y,-L8*77Q-6F9-#,-Y*8+G6;HQ-qOU@-F6:*+6H*1F-

H=;1<+=-*F911;-21;;*91;7-<7*F+-1AH*260- M1GQr-*F-3"9;Q- PR.RQ-AA,-^^V.n

^^Vd,-

- o^p- ",- /,- O1870<F9Q- U,- >*0H1FQ- 6F9- @,- h;s+8;Q- qU- 7<;:8J- 1B- 69:6F287- *F-

:*7*1F456789- =<C6F- C1H*1F-26AH<;8- 6F9- 6F60J7*7Qr-"#<'./4, =*&4, 3<-+%,

>()%$&/4Q-:10,-.R]Q-F1,-PQ-AA,-SRn.PVQ-!1:,-PRRV,-

- o]p- #,-W1AA8Q-q@*7*1F456789-=<C6F-C1H*1F-6F60J7*7`-UF-1:8;:*8GQr-"#<'./4,

=*&4,3<-+%,>()%$&/4Q-:10,-.RdQ-F1,-.Q-AA,-]n.dQ-$2H,-PRRe,-

- o_p- X,-h,-U++6;G60-6F9-O,-Y,-#J11Q-q><C6F-U2H*:*HJ-UF60J7*7`-U-#8:*8GQr-

;"?,"#<'./,2.$@Q-:10,-]^Q-F1,-^Q-AA,-.V`.n.V`]^Q-UA;,-PR..,-

- oVp- /,-)<;=HQ-X,-[;88F58;+Q-6F9-#,-L87HG6H8;Q-?#/*#(,7&/*<-/*#(,;A+#$*/0<&,

B#$,=*)%#,"#<'$%&&*#(,-YA;*F+8;-&YQ-.SSe,-

- oep- #,- /;<F800*Q-$,- O*2=Q- 6F9- ',-O,- O198F6Q- qU- 7<;:8J-1F- H=8- 6<H1C6H*2-

*F98N*F+-1B-:*981-96H6Qr-C4,=*&4,"#<<.(4,3<-+%,9%'$%&%(/4Q-:10,-.RQ-F1,-PQ-

AA,-edn..PQ-X<F,-.SSS,-

- odp- #,- )6508HQ- W,- /1<H=8CJQ- 6F9- W,- W8;8jQ- q!1FA6;6C8H;*2- C1H*1F-

2=6;62H8;*j6H*1F-<7*F+-26<760-A;1565*0*7H*2-C19807-B1;-:*981-*F98N*F+-6F9-

;8H;*8:60Qr-3777,8$-(&4,3<-+%,D$#E%&&4Q-:10,-..Q-F1,-]Q-AA,-^S^n]ReQ-UA;,-

PRRP,-

- oSp- Y,- Y*:6;6C6F- 6F9- O,- O,- ";*:89*Q- q\113*F+- 6H- :8=*2087- 1F- H=8- ;169`-U-

7<;:8J-1B-:*7*1F456789-:8=*208-98H82H*1FQ-H;623*F+Q-6F9-58=6:*1;-6F60J7*7Qr-

3777,8$-(&4,3(/%AA4,8$-(&'4,2F&/4Q-:10,-.]Q-F1,-]Q-AA,-.ee^n.eS_Q-%82,-PR.^,-

-o.Rp- t,-><Q-Y,-W6*7*H3;*6F+3;6*Q-',-Y=8FQ-U,-:6F-98F->8F+80Q-6F9-),-W1;*30*Q-

q)67H- 98H82H*1F- 1B- C<0H*A08- 15b82H7- *F- H;6u2- 728F87- G*H=- 6- 21CC1F-

98H82H*1F-B;6C8G1;3Qr-3777,8$-(&4,3(/%AA4,8$-(&'4,2F&/4Q-:10,-.eQ-F1,-]Q-AA,-

.RRPn.R.]Q-UA;,-PR.V,-

-o..p- X,-X,-[*571FQ-q$AH*260-C1H*1F7-6F9-H;6F7B1;C6H*1F7-67-7H*C<0*-B1;-:*7<60-

A8;28AH*1FQr-D&FE0#A4,9%@4Q-:10,-V]Q-F1,-_Q-AA,-PddnPS_Q-.S_e,-

-o.Pp- >,-',-\1F+<8H4>*++*F7-6F9-h,-W;6j9FJQ-qK8-*FH8;A;8H6H*1F-1B-6-C1:*F+-

;8H*F60-*C6+8Qr-D$#E,9,2#E,G#(),HQ-:10,-PRdQ-F1,-..e^Q-AA,-^d_n^SeQ-X<0,-

.SdR,-

-o.^p- h,-W;6j9FJQ-q?+1C1H*1F-6F9-;806H*:8-98AH=-C6A-B;1C-1AH*260-M1GQr-H*#A4,

"F:%$(4Q-:10,-^VQ-F1,-PQ-AA,-den.RPQ-)85,-.SdR,-

-o.]p- /,-h,-W,->1;F-6F9-/,-[,-Y2=<F23Q-q%8H8;C*F*F+-1AH*260-M1GQr-;$/*B4,3(/%AA4Q-

:10,-.eQ-F1,-.Q-AA,-.d_nPR^Q-U<+,-.Sd.,-

-o._p- ',-l62=Q-",-W123Q-6F9->,-/*72=1BQ-qU-9<60*HJ-56789-6AA;162=-B1;-;860H*C8-

"@4\.-1AH*260-M1GQr-*F-D-//%$(,9%E#+(*/*#(Q-PRReQ-AA,-P.]nPP^,-

-o.Vp- O,-L8;058;+8;Q-",- W123Q-6F9->,-/*72=1BQ-qO1H*1F-87H*C6H*1F-G*H=-F1F4

01260-H1H60-:6;*6H*1F-;8+<06;*j6H*1FQr-*F-"=D9Q-PR.RQ-AA,-P]V]nP]e.,-

-o.ep- W, -h ;v =8 F5 s= 0-6 F9 -@, -h 10 H<F Q-q? u2 *8 FH-F1 F0 12 60-;8 +< 06 ;* j6H *1 F-B1 ;-1 AH *2 60 -

M1GQr-*F-7""=Q-PR.PQ-AA,-^_Vn^VS,-

-o.dp- %,-Y<FQ-Y,-#1H=Q-6F9-O,-X,-/0623Q-qY82;8H7-1B-1AH*260-M1G-87H*C6H*1F-6F9-

H=8*;-A;*F2*A087Qr-*F-"=D9Q-PR.RQ-AA,-P]^PnP]^S,-

-o.Sp- X,- #8:6<9Q- W,- L8*Fj68AB80Q- l,- >6;2=61<*Q- 6F9- ',- Y2=C*9Q- q?A*2)01G`-

?9+84A;878;:*F+- *FH8;A106H*1F- 1B- 21;;87A1F98F287- B1;- 1AH*260- M1GQr- *F-

"=D9Q-PR._Q-AA,-..V]n..eP,-

-oPRp- O,- "61Q- X,- /6*Q- W,- h1=0*Q- 6F9- Y,- W6;*7Q- qY*CA08)01G`- 6- F1F4*H8;6H*:8Q-

7<50*F86;-1AH*260- M1G- 60+1;*H=CQr-"#<'./4,I$-'04,J#$.<Q- :10,- ^.Q-F1,-

PAH.Q-AA,-^]_n^_^Q-O6J-PR.P,-

-oP.p- O,-O8Fj8Q-',->8*A38Q-6F9-U,-[8*+8;Q-q%*72;8H8-1AH*C*j6H*1F-B1;-1AH*260-

M1GQr-*F-I"D9Q-PR._Q-AA,-.VnPd,-

-oPPp- t,- '=8F- 6F9- @,- h10H<FQ- q)<00- M1G`- $AH*260- M1G- 87H*C6H*1F- 5J- +01560-

1AH*C*j6H*1F-1:8;-;8+<06;-+;*97Qr-*F-"=D9Q-\67-@8+67Q-!@Q-&YUQ-PR.VQ-

AA,-]eRVn]e.],-

-oP^p- %,-X,-/<H08;Q-X,-L<0mQ-[,-/,-YH6F08JQ-6F9-O,-X,-/0623Q-qU-F6H<;60*7H*2-1A8F-

71<;28-C1:*8-B1;-1AH*260-M1G-8:60<6H*1FQr-*F-7""=Q-PR.PQ-AA,-V..nVP_,-

-oP]p- [,-X,-Y<00*:6FQ-X,-#,-$=CQ-L,-X,->6FQ-6F9-",-L*8+6F9Q-q$:8;:*8G-1B-H=8-

>*+=-?u2*8F2J-@*981- '19*F+-D>?@'E- YH6F96;9Qr-3777,8$-(&4,"*$E.*/&,

2F&/4,=*)%#,8%E0(#A4Q-:10,-PPQ-F1,-.PQ-AA,-.V]Sn.VVdQ-%82,-PR.P,-

-oP_p- Y,- (,- Z1<F+- 6F9- %,- "6<5C6FQ- q)67H- $AH*260- )01G- ?NH;62H*1F- B;1C-

'1CA;87789-@*981Qr-*F-KLMN,O*+*/-A,3<-+%,"#<'./*(+1,8%E0(*P.%&,-(),

;''A*E-/*#(&,!O3"8;6Q-PR.dQ-AA,-.nd,-

-oPVp- %,- #sB8F62=H- 6F9- %,- "6<5C6FQ- q>?@'4?W('`- )67H- $AH*260- )01G-

?7H*C6H*1F-);1C-'1989-@*981-:*6-?9+84W;878;:*F+-(FH8;A106H*1FQr-3777,

8$-(&4,3<-+%,D$#E%&&4Q-:10,-PeQ-F1,-VQ-AA,-^.RRn^..^Q-X<F,-PR.d,-

-oPep-',-"1C67*-6F9-#,-O6F9<2=*Q-q/*06H8;60-I0H8;*F+-B1;-+;6J-6F9-2101;-*C6+87Qr-

*F-3""=Q-.SSdQ-AA,-d^Snd]V,-

-oPdp- k,-/6*-6F9-[,-Y6A*;1Q-q[81987*2-C6HH*F+`-6-B;6C8G1;3-B1;-B67H-*FH8;62H*:8-

*C6+8-6F9-:*981-78+C8FH6H*1F-6F9-C6HH*F+Qr-3(/4,C4,"#<'./4,=*&4Q-:10,-dPQ-

F1,-PQ-AA,-..^n.^PQ-UA;,-PRRS,-

-oPSp- U,- ';*C*F*7*Q-",- Y=6;AQ- ',- #1H=8;Q- 6F9- W,- Ww;8jQ- q[81987*2- (C6+8- 6F9-

@*981-?9*H*F+Qr-;"?,8$-(&,I$-'0Q-:10,-PSQ-F1,-_Q-AA,-.^]`.n.^]`._Q-!1:,-

PR.R,-

-o^Rp- ?,-Y,-\,-[67H60-6F9-O,-O,-$0*:8*;6Q-q%1C6*F-H;6F7B1;C-B1;-89+846G6;8-

*C6+8-6F9-:*981-A;12877*F+Qr-*F-23II9;DQQ-!8G-Z1;3Q-!ZQ-&YUQ-PR..Q-

AA,-VS`.nVS`.P,-

-o^.p- h,->8Q-X,-Y<FQ-6F9-k,-"6F+Q-q[<*989-*C6+8-I0H8;*F+Qr-3777,8$-(&4,D-//%$(,

;(-A4,?-E04,3(/%AA4Q-:10,-^_Q-F1,-VQ-AA,-.^Sen.]RSQ-X<F,-PR.^,-

-o^Pp- Y,-W6;*7-6F9-),-%<;6F9Q-qU-B67H-6AA;1N*C6H*1F-1B-H=8-5*06H8;60-I0H8;-<7*F+-

6-7*+F60-A;12877*F+-6AA;162=Qr-3(/4,C4,"#<'./4,=*&4Q-:10,-d.Q-F1,-.Q-AA,-P]n

_PQ-X6F,-PRRS,-

-o^^p- U,-U96C7Q-!,-[80B6F9Q-X,-%1071FQ-6F9-O,-\8:1JQ-q[6<77*6F-h%4H;887-B1;-

B67H- =*+=49*C8F7*1F60- I0H8;*F+Qr- *F- 23II9;DQQ- !8G-Z1;3Q- !ZQ- &YUQ-

PRRSQ-AA,-P.`.nP.`.P,-

-o^]p- U,-U96C7Q- X,- /683Q- 6F9- O,-U,- %6:*7Q- q)67H- =*+=49*C8F7*1F60- I0H8;*F+-

<7*F+-H=8-A8;C<H1=89;60-06HH*28Qr-"#<'./4,I$-'04,J#$.<Q-:10,-PSQ-F1,-PQ-

AA,-e_^neVPQ-O6J-PR.R,-

-o^_p- ?,- Y,-\,- [67H60-6F9- O,- O,-$0*:8*;6Q- qU96AH*:8-C6F*B1097- B1;- ;8604H*C8-

=*+=49*C8F7*1F60-I0H8;*F+Qr-;"?,8$-(&,I$-'0Q-:10,-^.Q-F1,-]Q-AA,-^^`.n

^^`.^Q-X<0,-PR.P,-

-o^Vp- ?,- ?*78C6FF- 6F9- ),- %<;6F9Q- q)067=- W=1H1+;6A=J- ?F=6F28C8FH- :*6-

(FH;*F7*2-#80*+=H*F+Qr-*F-23II9;DQQ-PRR]Q-AA,-Ve^nVed,-

-o^ep- \,-L6F+Q-\,4Z, - L8 * Q - h , - l = 1 < Q - / , - [ < 1 Q - 6 F 9 - > , 4Z, - Y = < C Q - q > * + = - 9 J F 6 C * 2 -

;6F+8- *C6+8- =600<2*F6H*1FQr- *F- 7I29Q- U*;84064@*008Q- YG*Hj8;06F9Q-

YG*Hj8;06F9Q-PRReQ-AA,-^P.n^PV,-

-o^dp- X,-'=8FQ-Y,-W6;*7Q-6F9-),-%<;6F9Q-q#8604H*C8-89+846G6;8-*C6+8-A;12877*F+-

G*H=-H=8-5*06H8;60-+;*9Qr-*F-23II9;DQQ-!8G-Z1;3Q-!ZQ-&YUQ-PRReQ-AA,-

.R^`.44.R^`S,-

-o^Sp- X,-",-/6;;1F- 6F9-/,- W1108Q-qK8- B67H-5*06H8;60-710:8;Qr-*F-7""=Q- '=6CQ-

PR.VQ-:10,-SSReQ-AA,-V.enV^P,-

-o]Rp- \,- (,- #<9*FQ- Y,- $7=8;Q- 6F9- ?,- )6H8C*Q- q!1F0*F86;- H1H60- :6;*6H*1F- 56789-

F1*78-;8C1:60-60+1;*H=C7Qr-D0F&4,R#(A*(%-$,D0%(#<4Q-:10,-VRQ-F1,-.Q-AA,-

P_SnPVdQ-!1:,-.SSP,-

-o].p- [,-[*0516-6F9-Y,-$7=8;Q-q!1F01260-1A8;6H1;7-G*H=-6AA0*26H*1F7-H1-*C6+8-

A;12877*F+Qr-?.A/*&E-A%,?#)%A4,2*<.A4Q-:10,-eQ-F1,-^Q-AA,-.RR_n.RPdQ-!1:,-

PRRd,-

-o]Pp- U,- '=6C51008Q- qUF- 60+1;*H=C- B1;- H1H60- :6;*6H*1F- C*F*C*j6H*1F- 6F9-

6AA0*26H*1F7Qr-C4,?-/04,3<-+*(+,=*&4Q-:10,-PRQ-F1,-.nPQ-AA,-dSnSeQ-X6F,-PRR],-

-o]^p- U,- /823- 6F9- O,- "851<008Q- qU- B67H- *H8;6H*:8- 7=;*F36+84H=;87=109*F+-

60+1;*H=C-B1;-0*F86;-*F:8;78-A;1508C7Qr-23;?,C4,3<-+*(+,2E*4Q-:10,-PQ-F1,-

.Q-AA,-.d^nPRPQ-X6F,-PRRS,-

-o]]p- U,- '=6C51008- 6F9- ",- W123Q- qU- )*;7H4$;98;- W;*C604%<60-U0+1;*H=C- B1;-

'1F:8N-W;1508C7-G*H=-UAA0*26H*1F7-H1-(C6+*F+Qr-C4,?-/04,3<-+*(+,=*&4Q-

:10,-]RQ-F1,-.Q-AA,-.PRn.]_Q-O6J-PR..,-

-o]_p- ?,- X,- '6F9x7Q- O,- /,- L63*FQ- 6F9- Y,- W,- /1J9Q- q?F=6F2*F+- 7A6;7*HJ- 5J-

;8G8*+=H89-y.-C*F*C*j6H*1FQr-C4,J#.$*%$,;(-A4,;''A4Q-:10,-.]Q-F1,-_Q-AA,-

deenSR_Q-%82,-PRRd,-

-o]Vp- U,-X,-YC106-6F9-#,-h1F91;Q-qh8;F807-6F9-;8+<06;*j6H*1F-1F-+;6A=7Qr-*F-

G%-$(*(+, S%#$F, -(), T%$(%A, ?-E0*(%&Q- /8;0*FQ- >8*98058;+`- YA;*F+8;Q-

PRR^Q-AA,-.]]n._d,-

-o]ep- X,-",-/6;;1FQ-U,-U96C7Q-Z,-Y=*=Q-6F9-',->8;F6F98jQ-q)67H-5*06H8;6047A628-

7H8;81-B1;-7JFH=8H*2-98B12<7Qr-*F-"=D9Q-PR._Q-AA,-]]VVn]]e],-

-o]dp-W,-O* 06 FB 6;Q-q YJ CC 8H ;* j*F +-YC 11 H= *F +-) *0 H8 ;7Q r-23;?,C4,3<-+*(+,2E*4Q-:10,-

VQ-F1,-.Q-AA,-PV^nPd]Q-X6F,-PR.^,-

-o]Sp- U,-@,-$AA8F=8*C-6F9-#,-L,-Y2=6B8;Q-O*&E$%/%U8*<%,2*+(-A,D$#E%&&*(+Q-^-

89*H*1F,-&AA8;-Y69908-#*:8;`-W86;71FQ-PRRS,-

-o_Rp- >,-hF<H771F-6F9-',4),-L87H*FQ-q!1;C60*j89-6F9-9*m8;8FH*60-21F:10<H*1FQr-

*F-"=D9Q-.SS^Q-AA,-_._n_P^,-

-o_.p-U,-/6A6H-6F9-X,4O,-);6=CQ-qK8-91C6*F-H;6F7B1;C-710:8;Qr-*F-"=D9Q-PR.SQ-

AA,-VR.]nVRP^,-

-o_Pp- !,- W6A8F58;+Q-U,- /;<=FQ- ",- /;1NQ- Y,- %*967Q- 6F9- X,- L8*238;HQ- q>*+=0J-

622<;6H8-1AH*2-M1G-21CA<H6H*1F-G*H=-H=81;8H*2600J-b<7H*I89-G6;A*F+Qr-3(/4,

C4,"#<'./4,=*&4Q-:10,-VeQ-F1,-PQ-AA,-.].n._dQ-UA;,-PRRV,-

-o_^p- >,-!6+80-6F9-L,-?F380C6FFQ-qUF-*F:87H*+6H*1F-1B-7C11H=F877-21F7H;6*FH7-

B1;-H=8-87H*C6H*1F-1B-9*7A0628C8FH-:82H1;-I8097-B;1C-*C6+8-78g<8F287Qr-

3777,8$-(&4,D-//%$(,;(-A4,?-E04,3(/%AA4Q-:10,-dQ-F1,-_Q-AA,-_V_n_S^Q-Y8A,-

.SdV,-

-o_]p- >,-l*CC8;Q-U,-/;<=FQ-6F9-X,-L8*238;HQ-q$AH*2-M1G-*F-=6;C1FJQr-3(/4,C4,

"#<'./4,=*&4Q-:10,-S^Q-F1,-^Q-AA,-^Vdn^ddQ-X<0,-PR..,-

-o__p- l,-l=6F+Q-qW6;6C8H8;-87H*C6H*1F-H82=F*g<87`-6-H<H1;*60-G*H=-6AA0*26H*1F-H1-

21F*2-IHH*F+Qr-3<-+%,=*&4,"#<'./4Q-:10,-._Q-F1,-.Q-AA,-_SneVQ-X6F,-.SSe,-

-o_Vp- O,- [,-O1j8;1:-6F9- X,- :6F-98-L8*b8;Q- q[01560- '101;- YA6;78F877-6F9- 6-

\1260- YH6H*7H*27- W;*1;- B1;- )67H- /*06H8;60- )*0H8;*F+Qr- 3777, 8$-(&4, 3<-+%,

D$#E%&&4Q-:10,-P]Q-F1,-.PQ-AA,-_d]Pn_d_^Q-%82,-PR._,-

-o_ep- W, - !6 *; - 6F 9- h, - ! ,- ' =6 <9 =< ;JQ - q) 67 H- > *+ =4%*C8F7*1F60- /*06H8;60- 6F9-

YOUNG et al.: FAST OPTICAL FLOW EXTRACTION FROM COMPRESSED VIDEO 13

!1F01260-O86F7-)*0H8;*F+Qr-3777,8$-(&4,3<-+%,D$#E%&&4Q-:10,-PdQ-F1,-^Q-

AA,-.]eRn.]d.Q-O6;,-PR.S,-

-o_dp- Z, - \ * - 6 F 9 - Y , - $ 7 = 8 ; Q - q U - F 8 G - C 8 9 * 6 F - B 1 ; C < 0 6 - G * H = - 6 A A 0 * 2 6 H * 1 F 7- H1- W%?-

56789-98F1*7*F+Qr-"#<<.(4,?-/04,2E*4Q-:10,-eQ-F1,-^Q-AA,-e].ne_^Q-Y8A,-

PRRS,-

Sean I. Young-;828*:89-/,'1C-6F9-/,?,-98+;887-*F-71BHG6;8-8F+*F88;*F+-B;1C-

H=8-&F*:8;7*HJ-1B-U<2306F9-*F-PRRdQ-6F9-H=8-O,?F+Y2-6F9-W=,%,-98+;887-B;1C-

H=8-&F*:8;7*HJ-1B-!8G-Y1<H=-L6087Q-YJ9F8JQ-*F-PR..-6F9-PR.dQ-;87A82H*:80J,->8-

*7-2<;;8FH0J-6-W17H912H1;60-#8786;2=8;-6H-YH6FB1;9-&F*:8;7*HJQ-YH6FB1;9Q-'U,-(F-

PR.VQ-=8-G67-6-:*7*H*F+-;8786;2=8;-6H-(FH8;%*+*H60-'1CC<F*26H*1F7Q-Y6F-%*8+1Q-

'U,->*7-;8786;2=-*FH8;87H7-6;8-06;+8472608-1AH*C*j6H*1F-6F9-*F:8;78-A;1508C7-*F-

*C6+8- A;12877*F+,- >8- ;828*:89- H=8-UW#Yc(UW#- 587H- A6A8;- 6G6;9- 6H- %('"U-

PR.dQ-H1+8H=8;-G*H=-%6:*9-"6<5C6F,-

Bernd Girod ;828*:89- H=8-?F+*F88;*F+- %12H1;6H8- 98+;88-B;1C- &F*:8;7*HJ-1B-

>6FF1:8;Q-[8;C6FJQ-6F9-H=8-O,Y,-98+;88-B;1C-[81;+*6-(F7H*H<H8-1B-"82=F101+J,-

&FH*0-.SSSQ- =8- G67- 6-W;1B8771;- G*H=-H=8- ?082H;*260-?F+*F88;*F+-%8A6;HC8FHQ-

&F*:8;7*HJ-1B-?;06F+8Fn!<;8C58;+,->8-*7-2<;;8FH0J-H=8-#158;H-\,-6F9-U<9;8J-

Y,->6F2123-W;1B8771;-1B-?082H;*260-?F+*F88;*F+Q-YH6FB1;9-&F*:8;7*HJQ-'UQ-&YU,-

>8-=67- 6<H=1;89-1:8;- VRR-21FB8;8F28-6F9-b1<;F60-A6A8;7-6F9-7*N- 51137,->*7-

;8786;2=-*FH8;87H7-6;8-*F-H=8-6;86-1B-*C6+8Q-:*981Q-6F9-C<0H*C89*6-7J7H8C7,-U7-

6F-8FH;8A;8F8<;Q-=8- G67-*F:10:89-*F- F<C8;1<7-7H6;H<A-:8FH<;87Q-6C1F+- H=8C-

W10J21CQ-@*:1-Y1BHG6;8Q-dzdQ-6F9-#860!8HG1;37,->8-*7-6-?&#UY(W-)8001GQ-6-

C8C58;-1B-H=8-!6H*1F60-U2698CJ-1B-?F+*F88;*F+Q-6F9-6-C8C58;-1B-H=8-[8;C6F-

!6H*1F60-U2698CJ-1B-Y2*8F287-D\81A109*F6E,->8-;828*:89-H=8-?&#UY(W-Y*+F60-

W;12877*F+-/87H-W6A8;-UG6;9-*F-PRRPQ-H=8-(???-O<0H*C89*6-'1CC<F*26H*1F-

/87H-W6A8;-UG6;9-*F-PRReQ-H=8-?&#UY(W-(C6+8-'1CC<F*26H*1F-/87H-W6A8;-

UG6;9-*F-PRRdQ-H=8-?&#UY(W-Y*+F60-W;12877*F+-O17H-'*H89-W6A8;-UG6;9-*F-

PRRdQ-H=8-?&#UY(W-"82=F*260-U2=*8:8C8FH-UG6;9-*F-PRR]Q-6F9-H=8-"82=F*260-

U2=*8:8C8FH-UG6;9-1B-H=8-(???-Y*+F60-W;12877*F+-Y12*8HJ-*F-PR..,-

David Taubman-;828*:89-/,Y,-6F9-/,?,-98+;887-*F-8082H;*260-8F+*F88;*F+-B;1C-

H=8-&F*:8;7*HJ-1B-YJ9F8JQ-*F-.SdV-6F9-.SddQ-;87A82H*:80JQ-6F9-H=8-O,Y,-6F9-W=,%,-

98+;887- B;1C- H=8- &F*:8;7*HJ- 1B- '60*B1;F*6- 6H- /8;3808JQ- *F- .SSP- 6F9- .SS]Q-

;87A82H*:80J,- );1C- .SS]- H1- .SSdQ- =8- G67- G*H=- >8G08HH4W6236;9{7- #8786;2=-

\651;6H1;*87Q-W601-U0H1Q-'U,->8-b1*F89-&!YL-*F-.SSdQ-G=8;8-=8-*7-2<;;8FH0J-6-

W;1B8771;-G*H=-H=8-Y2=110-1B-?082H;*260-?F+*F88;*F+-6F9-"80821CC<F*26H*1F7,-

>8- =67- 6<H=1;89- H=8- 5113- XW?[PRRR`- (C6+8- '1CA;877*1F- )<F96C8FH607Q-

YH6F96;97-6F9-W;62H*28Q-G*H=-O,-O6;2800*F,->*7-;8786;2=-*FH8;87H7-*F20<98-=*+=0J-

72606508- *C6+8- 6F9- :*981- 21CA;877*1FQ- C1H*1F- 87H*C6H*1F- 6F9- C1980*F+Q-

*F:8;78-A;1508C7-*F-*C6+*F+Q-A8;28AH<60-C1980*F+Q-6F9-C<0H*C89*6-9*7H;*5<H*1F-

7J7H8C7,->8-;828*:89-H=8-&F*:8;7*HJ-O8960-B;1C-H=8-&F*:8;7*HJ-1B-YJ9F8J,->8-

=67-;828*:89-HG1-587H-A6A8;-6G6;97-B;1C-H=8-(???-'*;2<*H7-6F9-YJ7H8C7-Y12*8HJ-

B1;- H=8- .SSV- A6A8;- 8FH*H089-U-'1CC1F- );6C8G1;3- B1;- #6H8- 6F9- %*7H1;H*1F4

/6789-Y260*F+-1B->*+=0J-Y2606508-'1CA;87789-@*981Q-6F9-B;1C-H=8-(???-Y*+F60-

W;12877*F+- Y12*8HJ- B1;- H=8- PRRR- A6A8;- 8FH*H089- >*+=- W8;B1;C6F28- Y2606508-

(C6+8-'1CA;877*1F-G*H=-?/'$",