Gene Cheung
National Institute of Informatics
15th July, 2016

Interactive Media Streaming
Applications Using Merge Frames.
MSR Visit 7/15/2016

1

Acknowledgement
Collaborators:• B. Motz, Y. Mao, Y. Ji (NII, Japan)• W. Hu, P. Wan, W. Dai, J. Pang, J. Zeng, A. Zheng,
O. Au (HKUST, HK)• Y.-H. Chao, A. Ortega (USC, USA)• D. Florencio, C. Zhang, P. Chou (MSR, USA)
• Y. Gao, J. Liang (SFU, Canada)• L. Toni, A. De Abreu, P. Frossard (EPFL, Switzerland)• C. Yang, V. Stankovic (U of Strathclyde, UK)• X. Wu (McMaster U, Canada)• P. Le Callet (U of Nantes, France)• L. Fang (USTC, China)• C.-W. Lin (National Tsing Hua University, Taiwan)

MSR Visit 7/15/2016

2

NII Overview• National Institute of Informatics• Chiyoda-ku, Tokyo, Japan.
• Government-funded research lab.

• Offers graduate courses & degrees
through The Graduate University for
Advanced Studies (Sokendai).
• 60+ faculty in “informatics”:
quantum computing, discretealgorithms, database, machinelearning, computer vision, speech &audio, image & video processing.

• Get involved!
• 2-6 month Internships.
• Short-term visits via
MOU grant.
• Lecture series,
Sabbatical.
MSR Visit 7/15/2016

3

Introduction to APSIPA and APSIPA DL

APSIPA Mission: To promote broad spectrum of research and education
activities in signal and information processing in Asia Pacific
APSIPA Conferences: ASPIPA Annual Summit and Conference

APSIPA Publications: Transactions on Signal and Information Processingin partnership with Cambridge Journals since 2012; APSIPA Newsletters
APSIPA Social Network: To link members together and to disseminate
valuable information more effectively
APSIPA Distinguished Lectures: An APSIPA educational initiative to reachout to the community

APSIPA Distinguished Lecture Series
www.apsipa.org

4Outline• What is interactive media navigation?
• e.g. Multiview / free-viewpoint video• Merge frame for interactive media navigation• Previous works• Merge frame / block overview• Fixed target merging• Optimized target merging• Interactive Light Field Streaming (ILFS)

Wei Dai, Gene Cheung, Ngai-Man Cheung, Antonio Ortega, Oscar Au, "Merge Frame Design for Video Stream Switching
using Piecewise Constant Functions," IEEE Transactions on Image Processing, vol. 25, no.8, August 2016
B. Motz, G. Cheung, A. Ortega, “Redundant Frame Structure using M-frame for Interactive Light Field Streaming,”(accepted to) IEEE International Conference on Image Processing, Phoenix, USA, September, 20165

Outline• What is interactive media navigation?
• e.g. Multiview / free-viewpoint video• Merge frame for interactive media navigation• Previous works• Merge frame / block overview• Fixed target merging• Optimized target merging• Interactive Light Field Streaming (ILFS)MSR Visit 7/15/2016

6

What is interactive media navigation /streaming?
• Server: a very large correlated media data set.
server• e.g., multiview video, light field data, etc.

• Client: can observe only small data subset at a time.
• Network: cannot deliver whole dataset before start ofnavigation.

network• Interactive navigation: client requests data, server sends
data. Repeat.
request data

clientdeliver dataserverclientG. Cheung, A. Ortega, N.-M. Cheung, B. Girod, “On Media Data Structures for Interactive Streaming in Immersive
Applications,” in SPIE Visual Communications and Image Processing, Huang Shan, China, July, 2010.

7

Interactive Multiview Video Streaming(IMVS)• Server: multiple views of same video captured synchronously in time.
• Client: can observe only 1 view at a time.
• Interactive navigation:• Client plays back video in time uninterrupted.
• Client requests view, server sends view. Repeat.

G. Cheung, A. Ortega, N.-M. Cheung, "Interactive Streaming of Stored Multiview Video using Redundant
Frame Structures," IEEE Transactions on Image Processing, vol.20, no.3, pp.744-761, March 2011.

8

Outline• What is interactive media navigation?
• e.g. Multiview / free-viewpoint video• Merge frame for interactive media navigation• Previous works• Merge frame / block overview• Fixed target merging• Optimized target merging• Interactive Light Field Streaming (ILFS)MSR Visit 7/15/2016

9

Merge Frame for Media Navigation:
conflicting coding requirements• Inherent tension between coding efficiency &flexible decoding.
• Differential coding assumes single
order of frame decoding.
1

2

3• Flexible decoding assumes several
orders (paths) of frame decoding.
• Other examples:• Interactive
browsingof JPEG2000
Research
Question:How
to enableimages.
flexible decoding• Single-video w/ forward & backward playback.
without• Interactive
Light
Field performance?
Streaming (ILFS).
great
sacrifice ofcodingMSR Visit 7/15/201610

Merge Frame for Media Navigation:
previous works 1• SP frames (H.264 extended profile):• Primary SP-frame: motion prediction + extra
quantization. (small).
• Secondary SP-frame: motion prediction +lossless encoding. (large).

1

2

1

2

3
3
3

4
4

• Pros: small primary SP-frame.
• Cons:• very large secondary SP-frames.
• As many secondary SP-frames as decoding paths.
M. Karczewicz and R. Kurceren, “The SP- and SI-frames design for H.264/AVC,” in IEEE Transactions
on Circuits and Systems for Video Technology, vol. 13, no.7, July 2003, pp. 637–644.
X. Sun, F. Wu, S. Li, G. Shen, and W. Gao, “Drift-free switching of compressed video bitstreams at predictive frames,”in IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no.5, May 2006, pp. 565–576.

11

Merge Frame for Media Navigation:
previous works 2• DSC frames:• Key Idea: treat merging as noise removal.
• Divide side information (SI) frames into block,perform DCT, quantization.

1

2

1

2

4

• Examine bit-planes of quantized coefficients.
• If bit-planes different from target, channel coding
to “denoise” SI bit-planes to target bit-planes.

34• Pros: one merge frame for many decoding paths.
• Cons:• Bit-plane / channel coding are complex.
• Channel coding works well only for average statistics.
P. Ramanathan, M. Kalman, and B. Girod, “Rate-distortion optimized interactive light field streaming,”
in IEEE Transactions on Multimedia, vol. 9, no.4, June 2007, pp. 813–825.
N.-M. Cheung, A. Ortega, and G. Cheung, “Distributed source coding techniques for interactive
multiview video streaming,” in 27th Picture Coding Symposium, Chicago, IL, May 2009.

12

Merge Frame for Media Navigation:
definition• Interactive Video Stream Switching (IVSS)• Multiple related pre-encoded video streams.
• Designated switching points to switch from one to another.

• Picture Interactive Graph

Dynamic View Switching:switch to neighboring viewof next time instant.

No loops in PIG.



Optimized target merging.

W. Dai, G. Cheung, N.-M. Cheung, A. Ortega, O. Au, “Rate-distortion Optimized Merge Frame using Piecewise
Constant Functions,” IEEE International Conference on Image Processing, Melbourne, Australia, September, 2013.
Wei Dai, Gene Cheung, Ngai-Man Cheung, Antonio Ortega, Oscar Au, "Merge Frame Design for Video Stream Switching
using Piecewise Constant Functions," IEEE Transactions on Image Processing, vol. 25, no.8, August 201613

Merge Frame for Media Navigation:
definition• Interactive Video Stream Switching (IVSS)• Multiple related pre-encoded video streams.
• Designated switching points to switch from one to another.

• Picture Interactive Graph

Static View Switching:switch to neighboring viewof same time instant.



Loops in PIG.



Fixed target merging.

J.-G. Lou, H. Cai, and J. Li, “A real-time interactive multi-view video system,” in ACM International
Conference on Multimedia, Singapore, November 2005.
N.-M. Cheung and A. Ortega, “Compression algorithms for flexible video decoding,” in IS&T/SPIE Visual
Communications and Image Processing (VCIP’08), San Jose, CA, January 2008.

14

Merge Frame for Media Navigation:framework• Switching Mechanism• Side Information (SI) frame: P-frame predicted from diff. streams.
• Merge frame: merge diff. among SI frames into same frame.
• Interactive Transmission: transmit one SI frame + merge frame according
to chosen decoding path.

MSR Visit 7/15/201615

Merge Frame for Media Navigation:
merge frame (M-frame) overview
1. Each decoded SI frame is divided into 8x8 blocks, DCT transform andcoefficient quantized (q-coeff).
2. Given block b, if q-coeffs of SI frames very different, use I-block.
3. If q-coeffs of SI frames the same, use skip block.

4. If q-coeffs of SI frames slightly different, use merge block.

SI1

SI2

M-frameMSR Visit 7/15/201616

Merge Frame for Media Navigation:
merge block overview• Use piecewise constant function (pcf) for merging of SI’s q-coeffs:••

Q-coeff’s must land on the same “step” for identical merging.

pcf defined by step size W and shift c:•

Choose W per frequency of all merge blocks (cheap).

•

Choose c per block per frequency (expensive).

W x  cf x   
W

c

2
 W 

pcf

q-coeffs

17

Merge Frame for Media Navigation:
2 merging problems
Static view switching
Fixed Target Merging:•

Find M-frame M to reconstruct any SI
frame Sn, n=1,…,N, identically to a fixed
target T.

•

Difficult to optimize M-frame parameters.

Optimized Target Merging:•

Dynamic view switching

Find M-frame M to reconstruct any SI
frame Sn, n=1,…,N, identically to afloating target T M  , such that:M *  arg min D T, T M    R M 
M•

Optimize M-frame parameters in RD
manner.
MSR Visit 7/15/201618

Merge Frame for Media Navigation:
step W, shift c (fixed target merging)• Choosing step size W for given freq k:• Compute max diff. from target q-coeff in each block b:

Z b  max X b0  X bnn1,, N 

X b0

X b1

Zb

• Choose step size W to be roughly 2 * max diff:pcf:
W x  cf x   
W

c

2
 W 

W  2Zb  2#
b• Choosing shift c for each block b:• Choose shift:

X b2

cb  Wb# / 2  X b0, 2 , where X b, 2  X b mod Wb
00#• Lemma V.1: given this choice of step and shift,f X bn   X b0 , n  0,, N • Merge block group Bm, use a bigger step:

Z BM  max Z bbBM

WB#m  2 Z Bm  2

X b0, 2  X b0 mod WB#m

19

Merge Frame for Media Navigation:
step W, shift c (optimized target merging)• Choosing step size W for given freq k:• Compute max diff. bet’n 2 q-coeffs in block b, then block-wise max diff.:Z  max X  X*
bi , j0 ,, N 

i
b

j
b

Z

*
BM

 max Z

• Choose step size W to be roughly max diff:

bBM

*
b

X b2

X b0

X b1

Z b*

WBM  Z B* M  1• Choosing shift c for each block b:• Given step W, range Fb of shifts c can leadto identical merging.
• Choose c in Fb to min RD cost:min0 cb WB M | cbFbd b    log P cb 

peaks + uniform

continuous• Initialize P(cb):• Initialize a “peaks + uniform” distribution.
• Rate-constrained LM till convergence.

20Comparison with Coset Coding
X b2• Coset Coding:• SI values X b are noisy observations of target X b0
n

X b1

X b0
Zb

• Compute first largest difference w.r.t. to target:

Z b  max X bn  X b0n

• Encoder: select coset size W  2 Z b , transmit coset index ib  X b mod W
0• Decoder: compute Xˆ b  arg min X bn  X
X Z

s.t. ib  X mod W• Fixed Target Merging:• Step W is roughly 2 Z b : Wb  2 Z b  2#• Shift c given W is remainder of target: cb  Wb / 2  X b , 2 , where#0

X b0, 2  X b0 mod Wb#• Expect the same coding rate as coset coding!
MSR Visit 7/15/2016

21

Comparison with Coset Coding
X b2• Optimized Target Merging:

X b0

X b1

Zb

Z b*

Wb  Z  1 , where Z b  Z• Compared to coset size W  2 Z b , nearly half the step size!
• Step W is roughly Z b :

*
b

*
b

• Feasible range of shifts to select from via RD optimization:min0 cb WB M | cbFbd b    log P cb • Expect significant coding gain, especially at low rates.

MSR Visit 7/15/2016

22

Merge Frame for Media Navigation:
experiments• Exp Setup: Static view switching• Fixed target merging: 3 views with the same QP.
• H.264 for I- and P-frames.
• Compared w/ DSC frames.

MSR Visit 7/15/2016

23

Merge Frame for Media Navigation:
experiments 2• Exp Setup: Bit-rate adaptation• Optimized target merging: 3 streams of same sequence at diff. rates (TFRC).
• H.264 for I- and P-frames.
• vs. DSC frames, SP-frames.

• Worst case plots.

MSR Visit 7/15/2016

24

Merge Frame for Media Navigation:
experiments 3• Exp Setup: Dynamic view switching• Optimized target merging: 3 views with the same QP.
• H.264 for I- and P-frames.
• vs. DSC frames, SP-frames.

• Worst case plots.

MSR Visit 7/15/201625

Outline• What is interactive media navigation?
• e.g. Multiview / free-viewpoint video• Merge frame for interactive media navigation• Previous works• Merge frame / block overview• Fixed target merging• Optimized target merging• Interactive Light Field Streaming (ILFS)MSR Visit 7/15/201626

Interactive Light Field Streaming (ILFS)
Light Field:

LYTRO• Capture light intensity and direction per pixel.
• Micro-lenses placed in front of a traditional image sensor.

• Generate 2D array of viewpoint images for users to navigate.
Goal:• Design coding structures to facilitate viewswitches, while achieving low trans. Rate.

Idea:• Build redundant structures using I-frames, P-frames,
M-frames as building blocks, given storage size.
B. Motz, G. Cheung, A. Ortega, “Redundant Frame Structure using M-frame for Interactive Light Field Streaming,”(accepted to) IEEE International Conference on Image Processing, Phoenix, USA, September, 2016.

27

User Interaction Model
1. View Navigation Model:•

Define permissible view-switches.

2. User Behavior Model:•

Define probabilities of permissible view-switches.

coarse grid views
fine grid views

View Navigation Model (#):• WALK: navigate locally on fine grid.
• move to horizontal/vertical adjacent fine views {n, e, s, w}.

• JUMP: navigate neighborhoods on coarse grid.
• move to earest horizontal/vertical coarse views {N, E, S, W}.
#W. Cai, G. Cheung, S.-J. Lee, and T. Kwon, “Optimal frame structure design using landmarks for interactive light fieldstreaming,” in IEEE International Conference on Acoustics, Speech and Signal Processing, Kyoto, Japan, March 2012.

28

User Behavior Model
Memoryless Model: pi , j•

Prob of next view j depends on curr. view i.

1-hop Memory Model:

pk ,i , j•

Prob of next view j depends on curr. view i& past view k.

•Tend to select same direction repeatedly.

Define pk ,i , j when i is fine grid view:switches to coarse grid views
q1 / 3
if j  G cswitch to same-direction finegrid view
pk ,i , j   q0 1  q1  if  k , i    i, j 
switches to different-direction fine1  q 1  q  / 3
o
.
w
.
0
1

grid views
MSR Visit 7/15/2016

29

Redundant Frame StructureDefault Structure:•

1 I-frames, 1 M-frames per view.

•

View navigation possible using I-frames.

Redundancy in P-frames:• Add P-frame Pi  j  to facilitate switchfrom view j to view i.
• Diff. P-frames Pi  j  reconstruct tosame I-frame I i using M-frame M i .
• P-frame can enable 2-hop trans.

Question: which P-frames to add given storage constraint?
MSR Visit 7/15/201630

Expected transmission cost assuming aflexible 1-frame Buffer

display ref.
buffer bufferview jilFlexible 1-Frame Buffer:••

In addition to 1 I-frame display buffer, there is 1-frame ref. buffer.

•

Simplified buffer model to keep optimization tractable.

Assume lifetime of T view-switches.

Expected Transmission cost for user at view i at instant t,
given prev. view k and buffered view l:





(t )
(t )



c l    pk ,i , j min h l , j , hi l , j , hi l , j 
(t )
i|k

(t )
i

j
0-hop trans.

1-hop trans.

2-hop trans.

view-switching prob.
MSR Visit 7/15/201631

0-hop transmission cost
(I-frame)

display ref.
buffer bufferview jil• Send I-frame I j given curr. view i and ref. view l.
• A choice of keeping view i or l in ref. buffer.

hi( t ) l , j   rjI  1t  T  min c (jt|i1)   l ,i I-frame trans. cost

Recurse only if there
are view-switches
display ref.
buffer bufferj
MSR Visit 7/15/2016

irecursive cost withchoice of ref frame

display ref.
buffer buffer

j

l
32

1-hop transmission cost(one P-frame)

display ref.
buffer bufferview jil• Send P-frame Pj i  or Pj l  plus M-frame M j given curr.
view i and ref. view l.
• Occupancy of ref. buffer depends on P-frame used.


 



hi( t ) l , j   min rjP    1t  T c (jt|i1)    l ,iP-frame trans. cost

Recurse only if there
are view-switches
display ref.
buffer bufferj
MSR Visit 7/15/2016

irecursive cost withdifferent ref frames
display ref.
buffer buffer

j

l
33

2-hop transmission cost
(two P-frames)

display ref.
buffer bufferview jil• Transition to intermediate view η, then transition from η todestination j.
• Occupancy of ref. buffer depends on P-frame used.

ht( t ) l , j   min  rjP    1t  T c (jt|i1)    min rP    l ,i P-frame trans. cost fromintermediate view ηtransition cost tointermediate view ηrecursive cost

j

η

i

η

l

η

MSR Visit 7/15/2016

34

Structure Optimization• Question: how to add P-frames given storage constraint?
• Greedy Alg: add P-frame that maximally lower
Lagrangian cost, one at a time:

min cs( 0 )     b storage cost

expected trans. costb    Pj i 

P-frames in structure θPj i MSR Visit 7/15/2016

35

Experimental Setup• 2 Light field images of size 432x624• We select a 6x6 fine grid and 2x2 coarse grid
• The user can switch T=12 times• HEVC HM-15.0 for 𝐼-, 𝑃-frames. QP is set s.t. PSNR=36dB•

Flowers

Swans

I-frames costx 5 Vertical P-frames
x10 horizontal P-frames

x10 P-frames

M-frames cost

x3 Vertical P-frames
x6 horizontal P-frames

x5 P-frames

𝑞0 = 0.4 and 𝑞1 = 0.6• COMPARISON SCHEME:• I-only: structure with only I frames• Fixed 1 frame buffer: ref. view is previous displayed view.
• Flexible infinite buffer: Client keeps all traversed frames for ref. Simulate
100 clients for average.
MSR Visit 7/15/2016

36

Simulation Results (Swans Dataset)

20% better

only 6% worse

MSR Visit 7/15/2016

38

Simulation Results (Flowers Dataset)

15% better

only 6% worse

MSR Visit 7/15/2016

39

Summary• Interactive media navigation• Difficult to achieve to good compression efficiency & flexible
decoding.

• Merge frame to facilitate interactive navigation• Fixed target merging• Optimized target merging• Interactive light field streaming• Redundancy to enable faster switches

MSR Visit 7/15/2016

39

Q&A

• Email: cheung@nii.ac.jp• Homepage: http://research.nii.ac.jp/~cheung/

MSR Visit 7/15/201640