IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

1

Merge Frame Design for Video Stream Switching
using Piecewise Constant Functions
Wei Dai Student Member, IEEE, Gene Cheung Senior Member, IEEE, Ngai-Man Cheung Senior Member, IEEE,
Antonio Ortega Fellow, IEEE, Oscar C. Au Fellow, IEEE

Abstract—The ability to efficiently switch from one preencoded video stream to another (e.g., for bitrate adaptationor view switching) is important for many interactive streaming
applications. Recently, stream-switching mechanisms based on
distributed source coding (DSC) have been proposed. In order toreduce the overall transmission rate, these approaches provide
a “merge” mechanism, where information is sent to the decodersuch that the exact same frame can be reconstructed given thatany one of a known set of side information (SI) frames is available
at the decoder (e.g., each SI frame may correspond to a different
stream from which we are switching). However, the use of bitplane coding and channel coding in many DSC approaches leads
to complex coding and decoding. In this paper, we propose analternative approach for merging multiple SI frames, using apiecewise constant (PWC) function as the merge operator. In
our approach, for each block to be reconstructed, a series ofparameters of these PWC merge functions are transmitted inorder to guarantee identical reconstruction given the known sideinformation blocks. We consider two different scenarios. In thefirst case, a target frame is first given, and then merge parameters
are chosen so that this frame can be reconstructed exactly at the
decoder. In contrast, in the second scenario, the reconstructed
frame and merge parameters are jointly optimized to meet arate-distortion criteria. Experiments show that for both scenarios,
our proposed merge techniques can outperform both a recent
approach based on DSC and the SP-frame approach in H.264,
in terms of compression efficiency and decoder complexity.

I. I NTRODUCTION
In conventional non-interactive video streaming, a client
plays back successive frames in a pre-encoded stream in a
fixed order. In contrast, in interactive video streaming [1],a client can switch freely in real-time among a numberof pre-encoded streams. Examples include switching among
multiple streams representing the same video encoded at
different bit-rates for real-time bandwidth adaptation [2], or
switching among views in a multi-view video [3–7]. See [1]for more examples of interactive streaming. A major challenge
in interactive video streaming is to achieve efficient realtime switching among pre-encoded video streams. A simple
approach would be to insert an intra-coded I-frame at each
W. Dai is with Hong Kong University of Science and Technology, Clear
Water Bay, Kowloon, Hong Kong. Email: weidai@connect.ust.hk
G. Cheung is with National Institute of Informatics, 2-1-2, Hitotsubashi,
Chiyoda-ku, Tokyo, 101-8430, Japan. Email: cheung@nii.ac.jp
N.-M. Cheung is with Singapore University of Technology and Design, 8Somapah Road, Singapore 487372. Email: ngaiman cheung@sutd.edu.sg
A. Ortega is with University of Southern California, 3740 McClintock Ave.,
Los Angeles, CA 90089-2564. Email: ortega@sipi.usc.edu
This research is supported in part by JSPS and the National Research
Foundation Singapore under its Interactive Digital Media (IDM) Strategic
Research Programme.

potential switching point [4]. But the relatively high raterequired for I-frames often makes it impractical to insert themfrequently in the streams, thus reducing the interactivity of
playback.

Fig. 1. Reconstructed coefficient value X̄b (k) as a piecewise constant functionf ( ) of coefficient Xb (k) of an SI frame. Specifically, given the k-th coefficient
Xb (k) in block b from either SI frame 1 or 2, f (x) maps either Xb1 (k) or Xb2 (k)to the same X̄b (k) if they fall on the same constant interval of f ( ).

Towards a more efficient stream-switching mechanism, distributed source coding (DSC) has been proposed. DSC can inprinciple achieve compression efficiency that is a function of
the worst-case correlation between the target frame and theside information (SI) frames (from which the client may beswitching) [8–10]. As an example, illustrated in Fig. 1, in theblock-based DCT approach of [10], a desired k-th quantizedfrequency coefficient value X̄b (k) in block b of the target frame
needs to be reconstructed using either Xb1 (k) or Xb2 (k), thecorresponding coefficients in SI frames 1 and 2, respectively.
A D-frame is transmitted so that it is possible to reconstruct
the exact same target frame given any one of the two SI frames[10]. Thus we say that the D-frame supports a merge operation.
In particular, the least significant bits (LSBs) of Xb1 (k) andXb2 (k) are treated as “noisy” versions of the LSBs of X̄b (k).
The most significant bits (MSBs) of X̄b (k) are obtained from
the MSBs of Xb1 (k) or Xb2 (k), which are identical, while the Dframe contains channel codes that can produce the actual LSBs
of X̄b (k) taking Xb1 (k) or Xb2 (k) as inputs. The channel codes
associated to these target frame coefficients compose the Dframes, which potentially require significantly fewer bits thanan I-frame representation of the target frame [10].
There remain significant hurdles towards practical implementation of D-frames, however. First, the use of bit-plane
encoding and channel codes in proposed techniques [10]means that the computation complexity at the decoder is high.
Second, because the average statistics of a transform coeffi-

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

cient bit-plane for the entire image are used, non-stationary
noise statistics can lead to high rate channel codes, resulting
in coding inefficiency.
In this paper, we propose to use a piecewise constant (PWC)
function1 as the signal merging operator. This approach operates directly on quantized frequency coefficients (instead ofusing a bit-plane representation) and does not require channel
codes. As will be discussed in detail in Section VI-C, oursignal merging approach can be interpreted as a generalizationof coset coding [12], where we explicitly optimize the merged
target values for improved rate-distortion (RD) performance.
The basic idea is summarized in Fig. 1, which depicts afloor function characterized by two parameters: a step size
W and a shift c. In our approach, the encoder selects W andc to guarantee that Xb1 (k) and Xb2 (k) are in the same constantinterval and thus map to the same reconstruction value. A W
will be chosen for each frequency k, based on the statistics ofthe various Xb (k) across all blocks b. Then, given W it will bepossible to adjust c so that the reconstructed value matches adesired target, X̄b (k). A value of c will be chosen for each k
and b, so that the bitrate required by our proposed technique
is dominated by the cost of transmitting c. In this paper, we
will formulate the problem of selecting c and W, and develop
techniques for RD optimization of this selection.
We consider two scenarios. In the first one, fixed target
merging, we will assume that X̄b (k) has been given, e.g., byfirst generating an intra-coded version of the target frame, andusing the corresponding quantized coefficient values as targets.
We will show how to choose W to guarantee that X̄b (k) canbe reconstructed. We will also show that given W, c is fixed.
This type of merging is useful when there are cycles in theinteractive playback, i.e., frame A is an SI frame for frame B
and B is an SI frame for A. This will be the case in static
view switching for multiview video streaming, to be discussed
in Section III.
In the second scenario, optimized target merging, we selectW, c and X̄b (k) based on an RD criteria, where distortionis computed with respect to a desired target Xb0 (k). In this
scenario, we can use smaller values for W, and no longer
need to select a fixed c for given W and X̄b (k). This allows us
to optimize c so as to significantly reduce the rate needed to
encode the merging information. This approach can be used
when there are no cycles in the interactive playback, e.g., indynamic view switching scenarios (also discussed in Section
III). Experimental results show significant compression gains
over D-frames [10] and SP-frames in H.264 [13] at reduced
decoder computation complexity.
The paper is organized as follows. We first summarize
related work in Section II. We then provide an overview ofour coding system in Section III. We discuss the use of PWC
functions for signal merging in Section IV. We present our
PWC function parameter selection methods for fixed target
merging and optimized target merging in Section V andVI, respectively. Finally, we present experimental results andconclusions in Section VII and VIII, respectively.
1 An earlier conference version of this paper was presented in 2013 [11].

2

II. R ELATED W ORK
The H.264 video coding standard [14] introduced the concept of SP-frames [13] for stream-switching. In a nutshell, firstthe difference between one SI frame and the target picture islossily coded as the primary SP-frame. Then, the difference between each additional SI frame and the reconstructed primary
SP-frame is losslessly coded as a secondary SP-frame; losslesscoding ensures identical reconstruction between primary andeach of the secondary SP-frames. One drawback of SP-frames
is coding inefficiency. Due to lossless coding in secondary
SP-frames, their sizes can be significantly larger than conventional P-frames. Further, the number of secondary SP-frames
required is proportional to the number of SI frames, resulting
in large storage costs. As we will discuss, our proposed scheme
encodes only one merge frame for all SI frames, and hence
the storage requirement is lower than for SP-frames.
There exist proposals to improve coding performance of theoriginal SP-frames [15, 16]. [15] first proposed Flex SP, where
one quantization module in the primary SP-frame coder was
moved to the secondary SP-frame coder to improve quality ofprimary SP-frames. [15] then proposed Hybrid SP, where twocoding modes—choosing between Flex SP and original SP—
were employed, resulting in better RD performance. Similar inprinciple, [16] proposed to remove one of the two quantization
modules in the primary SP-frame coder to improve quality ofprimary SP-frames, while still retaining the drift-free streamswitching property using a different secondary SP-frame construction strategy. While [15, 16] do improve performance, therelatively large sizes of secondary SP-frames due to losselsscoding is still unavoidable. That means the worst-case streamswitching cost using secondary SP-frames remains much larger
than our proposal.
While DSC has been proposed for designing interactive andstream-switching mechanisms in the past decade [2, 8–10, 17],
partly due to the computation complexity required for bitplane and channel coding in common DSC implementations,
DSC is not widely used nor adopted into any video coding
standards. In contrast, our proposed coding tool involves only
quantization (PWC function) and entropy coding of function
parameters, both of which are computationally simple. Further,
we demonstrate coding gain over a previously proposed DSCbased approach [10] in Section VII.
[2, 18] also considered switching among multiple bitrate
videos, using Wyner-Ziv (WZ) coding techniques. However,the problem considered there is not the same as our work. First,[2, 18] did not consider identical reconstruction for drift-freestream-switching. This can be observed in their experimental
results (Fig. 13 and 14 in [2]), where there is a gap in
PSNR between WZ switching and the “switching-to” videos.
In contrast, our coding tools guarantee identical reconstruction
and drift-free stream-switching. Second, [2, 18] considered an
on-line scenario, where a switching controller at the server has
knowledge about the requested switching (e.g., from quality 1
to quality 2) to estimate the appropriate amount of WZ bits
for transmission to the receiver. In contrast, we consider an
off-line coding scenario, where multiple switching streams are
known at coding time, but exactly from which stream one isIEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

Fig. 2. Example of an acyclic picture interactivity graph (PIG) for dynamic
view switching. Each picture Πv,t has subscript indicating its view index v andtime instant t. After viewing picture Π2,1 of stream 2, the client can choose
to keep watching the same stream and jump to Π2,2 , or switch to Π1,2 orΠ3,2 of stream 1 and 3, respectively.

3

Fig. 3. Example of a cyclic picture interactivity graph (PIG) for static viewswitching. Each picture Πv,t has subscript indicating its view index v andtime instant t. After viewing Π2,2 of stream 2, the client can choose to keep
watching stream 2 in time and jump to Π2,3 , or change to Π1,2 or Π3,2 of
stream 1 and 3, respectively, corresponding to the same time instant as Π2,2 .

stream 1

switching is not known till actual streaming.
One of the primary applications of our proposed merge
frame is interactive media systems, which have attracted
considerable interest [19]. In particular, a range of media datatypes have been considered for interactive applications in the
past: images [20], light-fields [21, 22], volumetric images [23],videos [8, 9, 24–28] and high-resolution videos [29–32]. In
principle, our proposed merge frame can be applicable in someof these scenarios where DSC techniques have been proposed
previously. In this paper we focus on real-time switchingamong multiple pre-encoded video streams, as discussed in
Section III.
This paper extends our earlier work [11], by providing amore detailed presentation and evaluation of the system, as
well as introducing two new concepts. First, we study the fixed
target merging case (Section V). Second, for the optimized
target merging case, we develop a new algorithm to computea locally optimal probability function P(c) for shift c—one that
leads to more efficient entropy coding of c, and small signal
reconstruction distortion after merging (Section VI). We willshow in our experiments, described in Section VII, that our
new algorithm leads to significantly better RD performance
than our previously published work [11].
III. S YSTEM OVERVIEW
A. IVSS System Overview
We overview our coding system for interactive video stream
switching (IVSS), in which our proposed merge frame isa key enabling component. In the sequel, a “picture” is a
raw captured image in a video sequence, while a “frame”
is a particular coded version of the picture (e.g., I-frame,P-frame). In this terminology, a “picture” can have multiple
coded versions or “frames”.
In an IVSS system, there are multiple pre-encoded video
streams that are similar (e.g., videos capturing the same 3D
scene from different viewpoints [7]). During video playbackof a single stream, at a switch instant, the client can switchfrom a picture of the original stream to a picture of a different destination stream. Fig. 2 illustrates an example pictureinteractivity graph (PIG) for three streams, where there is aswitch instant every two pictures in time. An arrow Πp → Πq
indicates that a switch is possible from picture Πp to picture

I1,1

P1,2

(1)
P1,3

M1,3

P1,4

(2)
P1,3

stream 2

I2,1

P2,2

P2,3

P2,4

Fig. 4. Example of our proposed stream-switching mechanism to enable aswitch from picture 2 of stream 2 to picture 3 of stream 1. Each frame Fv,tis denoted by frame type F (I-, P- or M-frame), view v and instant t. A solid
directed edge indicates the relationship between a differentially coded frame(1)(2)
and its predictor. Specifically, SI frames P1,3 and P1,3 are first differentiallycoded using predictor frames P1,2 and P2,2 , respectively. M-frame M1,3 isencoded to merge the two SI frames into an identical reconstruction.

Πq . This particular graph is acyclic, i.e., it has no loops andwe cannot have both Πp → Πq and Πq → Πp .
The scenario in Fig. 2 is an example of dynamic viewswitching [33], where a frame at time t is always followed
by a frame at time t + 1. In contrast, in static view switchinga user can stop temporal playback and interactively select theangle from which to observe a 3D scene frozen in time [34].
Fig. 3 shows an example of static view switching, where thecorresponding graph is cyclic, i.e., it contains loops so that we
can have both Πp → Πq and Πq → Πp . We will discuss themerge frame design for the cyclic case in Section V.
B. Stream-Switch Mechanism in IVSS
For each possible switch Πp → Πq , we first encode a Pframe Pq | p for picture Πq , where a decoded frame of Πp isused as a predictor. Reconstructed Pq | p is called a SI frame,
which constitutes a particular reconstruction of destination Πq .
Because there are in general multiple origins for a given destination (the in-degree for destination picture in the PIG), there
are multiple corresponding SI frames. Multiple reconstructionsof the same Πq creates a problem for the following frame(s)that use Πq as a predictor for predictive coding; it is not knowna priori which SI frame Pq | p will be available at the decoder
buffer for prediction. This illustrates the need for our proposed
merge frame (called M-frame in the sequel) Mq , which is an
extra frame corresponding to Πq . Decoding of M-frame Mq
guarantees a unique reconstruction of Πq , no matter which SI
frame Pq | p is actually available at the decoder.
(1)(2)
As an illustration, in Fig. 4 two P-frames, P1,3 and P1,3 ,generated from predictors P1,2 and P2,2 respectively, are theIEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

SI frames. An M-frame M1,3 is added to merge the SI frames
to produce an identical reconstruction for Π1,3 . During a
stream-switch, the server can transmit any one of the two SI
frames and M1,3 leading to the same reconstructed frame forΠ1,3 , thus avoiding coding drift in the following frame P1,4 .
An alternative approach based on SP frames would requiresending a primary SP-frame S11,3 (using P1,2 as the predictor)
for the switch Π1,2 → Π1,3 , or a losslessly coded secondary
SP-frame S21,3 (using P2,2 as the predictor) for the switch
Π2,2 → Π1,3 . SP-frame approaches are asymmetric; rate ismuch lower when only a primary SP-frame is needed. In
contrast, the switching cost using M-frame is always the same(a pair of P- and M-frames). We will show that a pair of Pand M-frames requires lower rate than a secondary SP-frame.
C. Merge Frame Overview
In our proposed M-frame, each fixed-size code block in
an SI frame is first transformed to the DCT domain. DCT
coefficients are then quantized. The quantized coefficients
across SI frames (called q-coeffs in the sequel) are thenexamined. If the q-coeffs of a given block are very different
across SI frames, then the overhead to merge their differences
to targeted q-coeffs would be large. Thus, we will encode theblock as a conventional intra block. On the other hand, if theq-coeffs of a given block are already identical across all SI
frames, then we can simply inform the decoder that the qcoeffs can be used directly2 . Finally, if the q-coeffs across SI
frames are not identical but are similar, then each q-coeff ismerged identically to a target value via our proposed merge
operator. Hence, together there are three coding modes foreach code block: intra, skip and merge. We will focus ourattention on optimizing the parameters in merge mode, since
the intra and skip modes are straightforward.
IV. P ROBLEM F ORMULATION
A. Notation
We first define the notation that will be used in the sequel;
see Table I for quick reference. We denote the N SI framesby S1 , . . . , SN , one of which is guaranteed to be available atthe decoder buffer when M-frame M is decoded. We denotea desired target picture by T, and for notational convenience
we will include it in the set of SI frames as S0 = T.
We denote the group of fixed-size code blocks in M thatare encoded in merge mode by BM . Each block has K pixels.
We denote by xnb the b-th block in SI frame Sn coded inmerge mode. Each block xnb is transformed into the DCT
domain as Ynb = [Ybn (0), . . . , Ybn (K−1)], where Ybn (k) is the k-th
DCT coefficient of xnb . We denote by Xbn (k) the k-th quantizedcoefficient (q-coeff ) given uniform quantization step size Q:!
Yn (k),(1)
Xbn (k) = round b
Q
where round(x) rounds x to the nearest integer.
2 This is equivalent to the case when there is only a single SI frame, andthus no merging operation is necessary for identical reconstruction.

4

TABLE ITABLE OF N OTATIONS
N
Sn
T
M
R(M)
D(T, T̄(M))
λ
BM
K
xnb
Ybn (k)Xbn (k)Q
X̄b (k)Z∗b (k)Z∗B (k)M
WBM (k)cb (k)Fb (k)Zb (k)ZBM (k)# (k)WBMnumber of SI frames
SI frame ndesired target frame
M-framerate of M-frame M
distortion of reconstructed M wrt T
weight parameter to trade off distortion with rate
block group encoded in merge mode
number of pixels in a code block
block b of SI frame Sn
k-th DCT coefficient of block b of SI frame Sn
k-th q-coeff of block b of SI frame Sn
quantization step size
k-th reconstructed q-coeff of block b
max. pair difference between any pair of Xbn (k)group-wise max. pair difference, i.e. maxb∈BM Z∗b (k)step size for k-th q-coeff of block group BM
shift parameter for k-th q-coeff of block b
feasible range of shift cb for identical merging
max. target diff. between target Xb0 (k) and any Xbn (k)group-wise max. target difference, i.e. maxb∈BM Zb (k)step size for k-th q-coeff for fixed target merging

B. Formulation
We consider two different problems based on the reconstruction requirement with respect to the desired target T.
One typically chooses T a priori, e.g., by encoding the target
picture independently (intra only) and using the decodedversion as T. The first problem requires the M-frame toreconstruct identically to the desired target T:
Problem 1. Fixed Target Merging (Section V). Find M-frame
M such that the decoder, taking as input any one of the SI
frames Sn and M, can reconstruct T identically as output.
Because of the differences between the SI frames Sn andthe desired target T, there may be situations where a high rate
is required for M. In this case, we allow the reconstruction todeviate from the desired target T in order to reduce the raterequired for M by optimizing an RD criterion:
Problem 2. Optimized Target Merging (Section VI). Find
M∗ and T̄(M∗ ) so that the decoder, taking as input any oneof SI frames Sn and M∗ , can always identically reconstructT̄(M∗ ) as output, and where M∗ is an RD-optimal solution fora given weight parameter λ, i.e.,M∗ = arg min D(T, T̄(M)) + λR(M),M(2)

where D(T, T̄(M)) is the distortion incurred (with respect toT) when choosing T̄(M) as the common reconstructed frame,
and R(M) is the rate needed to encode M.
The second problem essentially states that the reconstruction target T̄(M) is RD-optimized with respect to the desired
target T, while the first problem requires identical reconstruction to target T. Note that in both problem formulations weavoid coding drift since they guarantee identical reconstruction
for any SI frame, but a solution to Problem 2 will be shownto lead to significantly lower coding rates.

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

5

0.3

A merge operation must, given q-coeff Xbn (k) of any SI
frames Sn , n ∈ {1, . . . , N}, reconstruct an identical value X̄b (k),for all frequencies k. We use a PWC function f (x) as thechosen merging operator, with parameters shift c and step size
W selected for each frequency k of each block b encoded inmerge mode (see Fig. 1). The selection of these parameters
influences the RD performance of this merging operation forthe optimized target merging case. We now discuss how c and
W are selected for each coefficient. Because the optimizationis the same for each frequency k, we drop the frequency index
k for a clearer presentation.
Examples of PWC functions are ceiling, round,floor, etc. In this paper, we employ the floor function3 :


W
x+c
W+
− c.
(3)
f (x) =
W
2
From Fig. 1, it is clear that there are numerous combinations ofparameters W and c such that identical merging is ensured—i.e., all Xbn map to the same constant interval. Note also thatthe choice of W depends on how spread out the collection
Xb0 , . . . , XbN are, that is, how correlated the SI blocks areto each other. In contrast, c is used to select a desiredreconstruction value Xb0 . Thus, because the level of correlation
can be assumed to be relatively consistent across blocks, a step
size WBM is selected once for all blocks b ∈ BM for a given
frequency. On the other hand, since the actual reconstruction
value will be different from block to block, the shift cb will
be selected on a per block basis for a given frequency.
The computation complexity of our proposed merge modeat the decoder can be analyzed as follows. For each q-coeff
Xbn in a merge mode block b of SI frame Sn , we computethe merged coefficient X̄n = f (Xbn ) using floor function (3),which involves only one round-down operation, three additions
and two multiplications (constant W/2 can be pre-computed).
Thus the computation cost at the decoder is minimal beyond
a JPEG-like block-based transform coder.
Before formulating the problem of optimizing the choice ofc and W, we derive constraints under which this selection ismade by determining:• Minimum value of W that still enables identical merging,• Given W, choices of c that lead to identical merging,• Effective range of c.
We first compute a minimum step size W to enable identicalmerging for blocks b in BM . Let Z∗b be the maximum pairdifference between any pair of q-coeffs of a given frequency
in block b, i.e.,

0.25

j

Z∗b = max Xbi − Xb = Xbmax − Xbmin ,i, j∈{0,...,N}(4)

where Xbmax and Xbmin are respectively the maximum andminimum q-coeffs among the SI frames, i.e.,
Xbmax = max Xbn ,n=0,...,N

Xbmin = min Xbn .
n=0,...,N(5)

Given Z∗b , we next define the group-wise maximum pair
3 We define floor function to minimize the maximum difference between
original x and reconstructed f (x), given shift c and step size W.

0.3
0.25

0.2

Probability

Probability

C. Piecewise Constant Function for Single Merging

0.15
0.1

0.1

0.05
0

0.2
0.15

0.05
0

5

10

15

20

0

25

0

5

Z*b

10

15

20

25

Z*b

Fig. 5. Two examples of probability distribution of Z∗b with three SI frames
at Q = 1 for Balloons at frequency k = 16 and k = 32.

difference Z∗BM for the blocks in group BM :Z∗BM = max Z∗b .
b∈BM

(6)

Since all Xbn are integer, Z∗BM is also an integer. We can now
establish a minimum for step size WBM , above which identicalmerging for all blocks b ∈ BM is achievable:
Fact 1. Minimum Step Size for Identical Merging: a step
size WBM > Z∗BM , is large enough for floor function f (Xbn )in (3) to merge any Xbn in BM to a same value X̄b .
Since each Sn is an approximation of (and thus is similarto) target T, the Sn ’s themselves are similar. Hence, thelargest difference Z∗b should be small in the typical case.
Indeed, we observe empirically that Z∗b follows an exponential
distribution (one-sided because Z∗b is non-negative). Fig. 5
shows Z∗b probability distribution for k = 16 and k = 32.
We observe that 80% of the blocks have Z∗b ≤ 5. Assumingthat Z∗b follows a Laplacian distribution, the maximum Z∗BM is
typically much larger than the average Z∗b . This will be shown
to be useful for the optimized merging case in Section VI.
Fact 1 states that step size WBM is wide enough so that
Xb0 , . . . , XbN can all fall on the same interval in f (x), as
shown in Fig. 1. However, given WBM , shift cb must still beappropriately chosen per block to achieve identical merging.
Mathematically, identical merging means that the floor
function with parameters cb and WBM produces the same
integer output for all inputs Xbn , that is:%  0$ n
Xb + cb
 Xb + cb  , ∀n ∈ {1, . . . , N}.
= 
(7)
WBM
WBM 
Thus for all Xbn , we must have for some m ∈ Z that:mWBM ≤ Xbn + cb < (m + 1)WBM , ∀n ∈ {0, . . . , N}

(8)

Instead of considering all Xbn ’s, it is sufficient to consider only
the maximum and minimum values, so that the range for cbthat guarantees identical reconstruction is:
mWBM − Xbmin ≤ cb < (m + 1)WBM − Xbmax(9)for some integer m. Note that given step size WBM , cb andcb + mWBM lead to the same output:%$
x + cb + mWBM
WBM
WBM +
− (cb + mWBM )f (x) =
WBM
2
$
%
WBM
x + cb
=
WBM +
− cb
WBM
2

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 201662) one shift cb (k) for each block b in group BM .

Fig. 6. Two cases of Xbmin and Xbmax (left: α < β and right: α > β) and theirimplications on the feasible range of shift cb .

Thus it will be sufficient to consider at most W different valuesof cb as possible candidates.
Define α = Xbmin mod WBM and β = Xbmax mod WBM andconsider the two possible cases.
1) In case (i), Xbmin = mWBM + α and Xbmax = mWBM + β,where α < β, so that Xbmin and Xbmax fall in the sameinterval when shift cb = 0. Hence we can have −α ≤cb < WBM − β in order to keep both Xbmin and Xbmax inthe interval [mWBM , (m + 1)WBM ).
2) In case (ii), Xbmin = mWBM +α and Xbmax = (m+1)WBM +β, where β < α, i.e., when cb = 0, Xbmin and Xbmax fall inneighboring intervals. Here we can have −α ≤ cb < −βto move Xbmax down to the interval [mWBM , (m+1)WBM ),or have WBM − α ≤ cb < WBM − β to move Xbmin up to
the interval [(m + 1)WBM , (m + 2)WBM ).
Note that the selection of WBM (Fact 1) implies that Xbmax −Xbmin < WBM , and α = β only if Xbmin = Xbmax , in which casethere is no merging needed and any cb would suffice.
The two cases (α < β and α > β) are illustrated in Fig. 6.
Note that given Xbmax ≥ Xbmin by definition, we will be in Case(ii) whenever β < α. We can summarize this result as:
Fact 2. Maximum Feasible Range Fb for Shift cb : For theshift cb to provide identical merging of q-coeffs Xb0 , . . . XbN toa same value X̄b , given step size WBM
cb ∈ Fb = [−α, WBM − β) if α < βandcb ∈ Fb = [WBM − α, WBM − β) if α > βwith α = Xbmin mod WBM and β = Xbmax mod WBM .

The cost of encoding a single WBM (k) for all k-th q-coeffs
in group BM is small, while the cost of encoding |BM | shiftscb (k) for each of the k-th q-coeffs can be significant. Thus weconsider only the rate associated to cb (k) in our optimization.
Note that since the high-frequency DCT coefficients of agiven code block are very likely zero, we can insert an End of
Block (EOB) flag Eb to signal the remaining high-frequency
q-coeffs in block b in a raster-scan order are 0. Effective useof Eb can reduce the amount of transmitted PWC function
parameters4 . In summary, we can define the RD optimized
target merging problem as:
X
WBM (k) > ZBM (k)min
Db + λRb ,(11)
cb (k) ∈ Fb (k)WBM (k), cb (k)b∈BMwith distortion Db and rate Rb for block b calculated as:
Db

=

Eb
X
k=0

Rb

=

Eb
X

K−1
X

db (k) +Yb0 (k)2

k=Eb +1

R(cb (k)),

k=0where db (k) is defined in (10) and R(cb (k)) is the rate toencode cb (k). We discuss how we tackle this optimization in
Section VI.

V. F IXED TARGET M ERGING
In certain applications, such as the static view switching
scenario discussed in Section III and illustrated in Fig. 3,
the PIG is cyclic, so that we may have that Πp → Πq
and Πq → Πp . Because of this interdependency, one cannot
directly define a simple target merging optimization, since
optimizing the reconstruction for Πq would require first fixing
a representation (frame) for Πp , but optimizing Πp would inturn require first fixing a representation for Πq . As a simple
alternative we propose fixed target merging, where the reconstruction target T for each picture is chosen independently
from the SI frames. For example, T can be the I-frame of thetarget picture for a given QP.

D. Formulation of Merge Frame RD-Optimization
In order to formulate the PWC function parameter optimization problem, we first define distortion, db , as the squared
difference between coefficient Yb0 of the desired target T andreconstructed coefficient f (Xb0 ) Q:
db = | Yb0 − f (Xb0 ) Q |2 .

(10)

Because shift cb will be always chosen within the feasible
range defined in Fact 2, all q-coeffs Xbn will map to the samevalue f (Xbn ), ∀n ∈ {0, . . . , N}. Thus we only need to computethe distortion for f (Xb0 ) in (10).
For the k-th q-coeff in block group BM , the encoder will
have to transmit to the decoder:1) one step size WBM (k) > ZBM (k) for each group BM .

A. Fixed Target Reconstruction using Merge Operator
We first show that given a target reconstruction value a anda step size W, we can always find a shift c so that f (x) in(3) is such that f (x) = a for all inputs x in the interval [a −W/2, a + W/2). To see this, first write target reconstruction
value a = a1 W + a2 , where a1 and a2 = a mod W are integers
and 0 ≤ a2 < W. Similarly, we write input x = a1 W + x2
4 In the fixed target merging case, E is inserted when the remaining highbfrequency q-coeffs of a block b in target T are exactly zero. In the optimized
target case, Eb can be inserted in an RD-optimal manner on a per-block basis,
similar to what is done in coding standards such as H.264 [14].

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 20167as part of the M-frame along with WB# M (k).

where integer x2 can be bounded:WW≤ x <a+2
2WW
a1 W + a2 −≤ a1 W + x2 < a1 W + a2 +
2
2
W
W
a2 −
≤ x2 < a2 +22
a−VI. O PTIMIZED TARGET M ERGING(12)

We now set c = W2 − a2 . We show that this ensures f (x) = a
for x ∈ [a − W/2, a + W/2):




 a1 W + x2 + W2 − a2  W + W − W − a2
f (x) = 
(13)

W
2
2
= a1 W + a2 = a.
where the second line is true because x2 + W2 − a2 in the
numerator of the floor operator argument can be boundedin [0, W) using (12):
W W
W
W W
+
− a2 ≤ x2 +− a2 < a2 +
+
− a2
2
2
2
2
2
W
0 ≤ x2 +− a2 < W(14)2
Next, recall from Section IV-C that we include the desired
target T as the first SI frame S0 . For a given frequency ofa particular block b, we first compute the maximum target
difference Zb as the largest absolute difference between target
q-coeff Xb0 and Xbn of any SI frame Sn , i.e.,a2 −Zb = max Xb0 − Xbnn∈{1,...,N}(15)

We choose step size and shift based on the following lemma.
Lemma V.1. Choosing step size Wb# = 2Zb + 2 and shift00cb = Wb# /2 − Xb,2
, where Xb,2
= Xb0 mod Wb# , guarantees that0nf (Xb ) = Xb , ∀n ∈ {0, . . . , N}.
Note that Wb# is an even number, and c is an integer as
required.
0
Proof: Given shift cb = Wb# /2 − Xb,2
, showing Xbn ∈ [Xb0 −Wb# /2, Xb0 + Wb# /2) implies f (Xbn ) = Xb0 , ∀n ∈ {0, . . . , N}.
Given step size Wb# = 2Zb + 2, the interval [Xb0 − Wb# /2, Xb0 +Wb# /2) can be rewritten as [Xb0 − Zb − 1, Xb0 + Zb + 1). By thedefinition of Zb , we know Xb0 − Zb ≤ Xbn ≤ Xb0 + Zb . Hencethe required interval for Xbn is met.
Note that we can achieve fixed target merging for a given
Xb0 as long as the step size is larger than Wb# . For example, we
can assign the same step size WB# M for all blocks in a group
BM , so that we reduce the rate overhead:
WB# M = 2 + 2ZBM

(16)

where ZBM = maxb∈BM Zb is the group-wise maximum target
difference, and Zb , the block-wise maximum target difference
for block b, is computed using (15). In summary:1) We define a set of blocks BM and use WB# M (k) computed
using (16) for frequency k of all blocks in BM .
02) For block b, we set shift cb (k) = WB# M (k)/2 − Xb,2
(k),
0
0
#
where Xb,2 (k) = Xb (k) mod WBM (k). A different shift isused for each frequency k and block b, and transmitted

We now propose a merging approach based on selecting
WBM (k) and cb (k) so as to find a solution to the optimization
problem described in Section IV-D, where we allow thereconstructed value to be different from Xb0 (k).
If WBM is chosen large enough, i.e. WBM ≥ 2 + 2Zb , thenwe have shown (Lemma V.1) that one can select shift cb
to reconstruct target q-coeff Xb0 exactly. However, the shifts0
are a function of Xb,2
= Xb0 mod WBM (Lemma V.1), andthus we can expect them to have a uniform distribution. It
would mean that a rate of the order log2 (WBM ) would be
required as overhead. In order to reduce this rate, we use
two approaches: i) we allow WBM to be smaller than requiredby Lemma V.1, and ii) when multiple choices of cb provide
identical reconstruction, we optimize this choice based on thecriteria introduced in Section IV-D.
A. Selection of WBM
Note that the definition of Z∗BM ensures that all Xbn of SI
frames Sn can be mapped to the same constant interval ofsize WBM in the floor function (3), as long as WBM > Z∗BM ,assuming an appropriate cb is chosen (Fact 1). A small WBM
would in general mean a small rate for coding cb , since cb cantake at most WBM different values.
As shown in Fig. 5, we observe empirically that Z∗b follows
a Laplacian distribution. Thus, for a large block group BM ,Z∗BM = maxb∈BM Z∗b will be in general much larger than Z∗b .
Since Z∗b ≥ Zb , in practice for many blocks b it is possible
to reconstruct target Xb0 since WB∗ M ≥ 2 + 2Zb . That means
using a step size WBM much larger than Z∗BM would reap
very small additional benefit in distortion reduction, while
potentially increasing the rate of coding cb . Thus, we select
WBM = Z∗BM + 1, which is the minimum step size to guaranteethat Xbn of any block b can be mapped to the same interval,
with appropriate choice of cb to be discussed next.
B. RD-optimal Selection of Shifts
Given a chosen WBM , according to Fact 2 there will be
multiple values of cb that guarantee identical reconstruction for
all Xbn . To enable efficient entropy coding of cb , it is desirable
to have a skewed probability distribution P(cb ) of cb . We design
an algorithm to promote a skewed P(cb ) iteratively. We first
propose how to initialize P(cb ), and then discuss how to update
P(cb ) in subsequent iterations.
We optimize shift cb via the following RD cost function:min0≤cb <WBM | cb ∈Fb

db + λ(− log P(cb ))(17)

where the rate term is approximated as the negative log of theprobability P(cb ) of candidate cb , and db is the distortion termcomputed using (10). The difficulty in using objective (17)to compute optimal c∗b lies in how to define P(cb ) prior to
selecting cb . Our strategy is to initialize a skewed distribution
P(cb ) to promote a low coding rate, perform optimization (17)

0.7

0.14

0.6

0.12

0.5

0.1

0.4

0.08

f(x)

f(x)

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

0.3
0.2

0.06
0.04

0.1
0

8

0.02
0

10

20

30

40

0

0

10

x

20

30

40

x

Fig. 7. Two examples of shift distribution P(cb ). Left distribution has small
number of spikes and has low entropy (1.22). Right distribution is smooth but
has high entropy (4.38).

where D({csi }) is computed as the sum of squared difference
between co and spike csi in the bin that co is assigned to. Having
defined distortion D({csi }), the initial spike locations csi given H
spikes can be found as follows: i) construct H spikes evenly
spaced in the interval [0, WBM ), ii) use conventional LloydMax algorithm with no rate constraints to converge to a set of
H bin centroids csi .
Next, adding consideration for rate, the RD cost of the three
spikes can then be written as:


WB −1
bP
bP
M
2 −1
1 −1


P
g(co ))
D({csi }) + λ − log(g(co )) − log(g(co )) − log(
co =0

for each block b ∈ BM , then update P(cb ) based on statisticsof the selected cb ’s, and repeat until P(cb ) converges.
In order to choose an initial distribution P(cb ), we notethat a distribution with a small number of spikes has lower
entropy than a smooth distribution (see Fig. 7 as an example).
Choosing cb values following such a discrete distribution (e.g.,
Fig. 7 (left)) means that we reduce the number of possible cb ,which may increase db . Thus, if λ in (17) is small, in orderto reduce distortion one can increase the number of spikes inP(cb ). We propose to induce a multi-spike probability P(cb ),where the appropriate number of spikes depends on the desired
tradeoff between distortion and rate in (17).
Since cb is constrained to be in the feasible region Fb
defined in Fact 2, it is possible that when we restrict cb to justa few values as in Fig. 7 (left), there will be some blocks b forwhich none of the spikes in P(cb ) fall within their Fb . In orderto guarantee identical reconstruction, they must be allowed to
select non-spike values as shifts cb . Thus we propose a “spike+ uniform” distribution P(cb ):(psi if cb = csi(18)
P(cb ) =pc o.w.
where {cs1 , . . . , csH } are the H spikes, each with probability psi ,and pc is a small constant for non-spike shift values. pc ischosen so that P(cb ) sums to 1.
1) Computing distribution P(cb ) for fixed H: We now
discuss how we compute P(cb ) for given H. Empirically weobserve that for a reasonable number of spikes (e.g., H ≥ 3),
the majority of blocks (typically 99% or more) in BM have atleast one spike in their feasible region Fb . Thus, to simplify
our computation we first ignore the feasibility constraint andemploy an iterative rate-constrained Lloyd-Max algorithm (rcLM) [35] to identify spike locations.
We illustrate the operations of rc-LM to initialize H spikelocations for H = 3 as follows. Let cob be the shift valuethat minimizes only distortion for block b. Let g(co ) be theprobability distribution of distortion-minimizing shift co forblocks in Bm , where 0 ≤ co < WBM . g(co ) can be computed
empirically for group Bm . Without loss of generality, we define
quantization bins for the three spikes cs1 , cs2 and cs3 as [0, b1 ),[b1 , b2 ) and [b2 , WBM ) respectively. The expected distortion
D({csi }) given three spikes is:
bX
1 −1
co =0

o

|c −cs1 |2 g(co )+

bX
2 −1
co =b

1

WBM −1o|c −cs2 |2 g(co )+

X

co =b

2

|co −cs2 |2 g(co ) (19)co =b1

co =b2(20)(20) is essentially the aggregate of RD costs (17) for all blocks
in BM .
To minimize (20), rc-LM alternately optimizes bin boundaries bi and spike locations csi at a time until convergence.
Given spikes csi are fixed, each bin boundary bi is optimized
via exhaustive search in the range [csi , csi+1 ) to minimize bothrate and distortion in (20). Given bin boundaries bi are fixed,
optimal csi can be computed simply as the bin average:
Pbi+1 −1g(co )coco =bis(21)
ci = Pb −1
i+1g(co )
co =biwhere b0 = 0 and b3 = WBM .
Upon convergence, we can then identify the small fractionof blocks with no spikes in their feasible regions Fb andassign an appropriate constant pc so that P(cb ) is well definedaccording to (18). Computing P(cb ) with H spikes where
H , 3 can be done similarly.
2) Finding the optimal P(cb ): To find the optimal P(cb ),we add an outer loop for this P(cb ) construction procedure
to search for the optimal number of spikes H. Pseudo-codeof the complete algorithm is shown in Algorithm 1. We notethat in practice, we observe that the number of iterations untilconvergence is small.
Algorithm 1 Computing the optimal shift distribution P(cb )1: for each number of spikes H ∈ [1, WBM ] do
2:
Initialize distribution Po (cb ) via LM;3:
t = 0;
4:
repeat5:t = t + 1;
6:
Update H spike locations csi via (21);7:
Update bin boundaries bi by minimizing (20);8:Compute pc for a new Pt (cb );9:until kPt−1 (cb ) − Pt (cb )k ≤ 
10: end forOn the complexity of the M-frame encoder, we note firstthat the computation load is dominated by Algorithm 1 tocompute P(cb ). For a given number of spikes H, LM is used
to compute initial Po (cb ), then rc-LM is iterated to computeP(cb ). Experimentally we found that fewer than three iterations
are needed for both LM and rc-LM to converge. We foundalso that the number of spikes required for optimal RD
performance for all bitrates of interest is no larger than three.

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

9

TABLE II
V IEWPOINTS OF EACH MULTIVIEW SEQUENCES .

Thus we conclude that the encoder complexity is manageable.
Finally, we note that because the distribution P(cb ) is computed
independently for each frequency k, a fast implementation tocompute P(cb ) for different frequencies in parallel is possible.
C. Comparison with Coset Coding
We now discuss the similarity between our proposed approach and coset coding methods in DSC [12]. Consider first
fixed target merging of one q-coeff of a single block b. In ascalar implementation of coset coding, given possible SI values
Xbn , n ∈ {1, . . . , N}, seen as “noisy” versions of a target Xb0 , thelargest difference Zb = maxn |Xbn − Xb0 | with respect to Xb0 is
first computed. The size of the coset W is then selected suchthat W > 2Zb . The coset index ib = Xb0 mod W is computedat the encoder for transmission.
At the decoder, the reconstructed value X̂b is the integer
closest to received SI Xbn with the same coset index ib , i.e.,X̂b = arg min |Xbn − X|X∈Z

s.t. ib = X mod W(22)

Using the aforementioned coset coding scheme for blocks0b ∈ BM , coding of ib = Xb0 mod W = Xb,2
per block isnecessary, where coset size W is chosen such that W > 2ZBM .
In our fixed target merging scheme using the floor function
0(3), we code a shift cb = WB# M /2−Xb,2for each block b, where#step size WBM is also proportional to 2ZBM . Comparing thetwo schemes, one can see that the number of choices thatneeds to be sent to the decoder is the same (one of WB# M
possible values in both cases). Both the shift value cb and ib are0functions of Xb,2
, the remainder or least significant bits (LSB)0of Xb , which are likely to have an approximately uniform
distribution. Thus the overhead rate should be the same forboth coset coding and fixed target merging.
Consider now the optimized merging case. In this scenario,
we are able to choose WBM = Z∗BM + 1—likely much smaller
than 2ZBM ≤ 2Z∗BM —so that we can still guarantee identicalreconstruction, with a reduction in rate that comes at the costof an increase in distortion. As for the coset coding approach,
if we were to reduce to choose a smaller WBM as well, wein fact can no longer guarantee identical reconstruction. Thisis because when WBM < 2ZBM there will be cases where not
all the Xbn are in the same interval, and thus the same ib willlead to two different values at the decoder depending on the
SI received. This imperfect merging will lead to undesirable
coding drift in the following predicted frames, as discussed in
Section III.
VII. E XPERIMENTS
We first discuss the general experimental setup and Mframe parameter selection (Section VII-A). We then verify theeffectiveness of our proposed “Spike + Uniform” distribution(Section VII-B). Next, we compare the performance of our
M-frame in three different situations: 1) static view switching(Scenario 1 in Section VII-C); 2) switching among streams
of different rates for the same single-view video (Scenario 2
in Section VII-D), and 3) dynamic view switching of multiview videos of different viewpoints and encoded in the same
bit-rate (Scenario 3 in Section VII-E).

Sequence Name
Balloons
Kendo
Lovebird1
Newspaper

Viewpoints
1, 3, 5
1, 3, 54, 6, 83, 4, 5

A. Experimental Setup
We use four different multiview video test sequences withresolution 1024x768 for scenarios 1 and 3: Balloons,Kendo5 , Lovebird1 and Newspaper6 . The viewpointsof each sequence are shown in Table II. For scenario 2,
we use four single-view video sequences with resolution
1920x1080: BasketballDrive, Cactus, Kimono1 and
ParkScene7 .
We compare the coding performance of our proposed
scheme against two schemes8 : SP-frame [13] in H.264 andD-frame proposed in [36]. QP for D-frame is set to be equal
to QPSI to maintain consistent quality. QPSI is set to 22,
26, 30 and 34 to induce different RD tradeoffs. For multiview scenarios 1 and 3, we encoded three streams from three
viewpoints: the center view was set as the target, to which theother two side views can switch at a defined switching point.
For Scenario 2, we encoded the single-view video in threedifferent bit-rates and then switched among them. QPs forthe three streams were adjusted according to additive increase
multiple decrease (AIMD) rate control principle in TCP and
TFRC [37]: one stream has twice the target stream’s bit-rate,
while the other has slightly smaller bit-rate (0.9 times of thetarget stream’s bit-rate). The results are shown in plots of
PSNR versus coding rate for a switched frame.
M-frame parameters are selected as follows. In Scenario
1, different QPM will result in different rates, and so we set
QPM to equal to QPSI , as was done for D-frames. However,for optimized target merging, coding rate is determined mainlyby the number of spikes in the distribution, and not QPM . In
our experiments, as similarly done in High Efficiency Video
Coding (HEVC), we first empirically compute λ as a functionof the SI frame’s QPSI :λ = 20.6QPSI −12(23)

The number of spikes in the distribution is driven by the selected λ. We then set QPM = 1 to maintain small quantization
error. For mode selection among skip, intra and merge, foreach block b we first examine q-coeffs Xbn (k) of N SI frames.
If Xbn (k) of all K frequencies are identical across the SI frames,
then block b is coded as skip. Otherwise, selection between
intra and merge is done based on a RD criteria.
We note that intra mode is implemented unconventionallyfor fixed target M-frame. After intra prediction is performed
to obtain a predicted block, it is first transformed to the
5 http://www.tanimoto.nuee.nagoya-u.ac.jp/mpeg/mpeg ftv.html
6 ftp://203.253.128.142
7 ftp://ftp.tnt.uni-hannover.de/testsequences/
8 QP

A denotes the QP for quantizing DCT coefficients in approach A.

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

Balloons

10

Balloons

Kendo

Kendo
45

40

40

40

40

PSNR
ICIP 8x8
4x4
8x8
16x16

35

ICIP 8x8
4x4
8x8
16x16

35

30
200

300
400
kBits/Frame

500

100

150

200 250 300
kBits/Frame(a) Balloons(b) Kendo

Lovebird1

Newspaper

40

40

350

400

ICIP 8x8
4x4
8x8
16x16

35

30
200

400

600
800
kBits/Frame

1000(c) Lovebird1

1200

30

200

400

600
kBits/Frame

0

1

2
3
kBits/Frame

Naive Approach
Proposed Approach

4

5

30

0

0.5

1
1.5
kBits/Frame

5

x 10

2

2.5
5

x 10

(b) Kendo

Fig. 9. PSNR v.s. encoding rate comparison with different block sizes forsequences Balloons, Kendo.

ICIP 8x8
4x4
8x8
16x16

35

35
Naive Approach
Proposed Approach(a) Balloons

PSNR

45

PSNR

45

35

30

30
100

PSNR

45

PSNR

45

PSNR

45

800

1000

(d) Newspaper

Fig. 8. PSNR v.s. encoding rate comparison with different block sizes forsequences Balloons, Kendo, Lovebird1 and Newspaper.

DCT domain and quantized. Then the difference between thepredicted q-coeffs and the target q-coeffs is computed andlosslessly coded via entropy coding. This ensures that target
q-coeffs can be exactly reconstructed in intra mode, just likemerge and skip modes during fixed target merging.
In HEVC, large code block sizes are introduced which bringsignificant coding gain on high resolution sequences [38].
Motivated by this observation, we also investigated the effectof different block sizes (4 × 4, 8 × 8, 16 × 16) on coding
performance. We also compare our current proposal against
the performance of our previous work [11], where block size isfixed at 8×8, initial probability distribution of shift P(cb ) is not
optimized, and no RD-optimized EOB flag is employed. The
corresponding PSNR-bitrate curves for scenario 3 are shownin Fig. 8.
From Fig. 8, we observe that block size 16 × 16 provides
the best coding performance at all bit-rates. One reason forthe superior performance of large blocks in M-frame is thefollowing: because SI frames are already reconstructions of thetarget frames (albeit slightly different), motion compensation
is not necessary, so the benefit of smaller blocks typical invideo coding is diminished. We note that in general an optimal
block size per frame can be selected by the encoder a priori
and encoded as side information to inform the decoder. In thefollowing experiments, the block size will be fixed at 16 × 16
for best performance.
Further, we observe also that our proposed method achieves
a significant coding performance gain compared to our previous method in [11] over all bit-rate regions, showing theeffectiveness of our newly proposed optimization techniques.
B. Effectiveness of “Spike + Uniform” Distribution
In order to verify the effectiveness of our proposed “Spike +Uniform” (SpU) probability distribution P(cb ) for shift parameter cb , we choose a competing naı̈ve distribution for P(cb )as follows: first, we compute distortion-minimizing g(c0 ) as
the initial probability distribution. Next, we compute the RDoptimal cb for each block b ∈ BM via (17) for a single iteration
using the initialized probability distribution and compute a new
P0 (cb ). This P0 (cb ) is then used to compute the rate to encode
each cb of a merge block b. The difference between P0 (cb ) andour proposed Pt (cb ) is that P0 (cb ) in general is an arbitrarily
shaped distribution, not a skewed “spiky” distribution. Experimental results of M-frame using these distributions are shownin Fig. 9.
We observe from Fig. 9 that our proposed SpU distribution
outperforms the naı̈ve distribution in the high bit-rate region
and is comparable in the low bit-rate region. This is because in
the low bit-rate region λ is very large, so that for any initial
distribution, after one iteration, there will only remain one
spike, and the number of iterations required for convergenceis very small.
C. Scenario 1: Static View Switching
We first test our proposed M-frame in the static viewswitching scenario for multi-view sequences. Three views are
encoded using same QP. The fixed target merging algorithm
described in Section V is used to facilitate switching toneighboring views among pictures of the same instant, asshown in Fig. 3.
Specifically, we constructed M- / D- frames to enable static
view-switching from view 1 or 3 to target view 2. We firstuse H.264 to encode two SI frames (P-frames) using Π2,2 as
the target and Π1,2 and Π3,2 as predictors, respectively. This
results in encoded rates R1,2 and R2,2 for the two SI frames,
respectively. Then we encoded a M- / D- frame to merge thesetwo SI frames identically to Π2,2 . The corresponding rates forMD
M-frame and D-frame are R2,2
and R2,2, respectively. Since
SP-frame in H.264 cannot perform fixed target merging, it is
not tested in this scenario.
We assume that the switching probability is equal on bothview 1 and 3, which is 0.5. Then the overall rate for the Dframe is calculated as:
R1,2 + R3,2
D
+ R2,2
.
(24)
RD =
2
Also, the overall rate for our proposed M-frame using fixed
target merging scheme is calculated as:
RM =R1,2 + R3,2
M
+ R2,2.
2(25)

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

Kendo

50

BasketballDrive

45

40

PSNR

PSNR

PSNR

45

40

35
Merge Frame
D−Frame
30

0

500

1000
Bits/Frame

1500

35

2000

0

500

1000
Bits/Frame

1500

42

40

40
38

38
36

2000

32

0

1000

2000
3000
kBits/Frame

4000(b) Kendo(a) BasketballDrive

Lovebird1

Newspaper

Kimono1

50

Merge Frame
D−FrameSP−Frame

32
30

5000

(a) Balloons
45

36
34

Merge Frame
D−FrameSP−Frame

34

Merge Frame
D−FrameCactus42

PSNR

Ballons

11

0

2000

4000
kBits/Frame

6000

8000

(b) Cactus
ParkScene

44

42

42

40

40

38

PSNR

PSNR

PSNR

40

35

PSNR

45
40

38
36

34
Merge Frame
D−FrameSP−Frame

35
Merge Frame
D−Frame
30

0

1000

2000
Bits/Frame

3000

4000

Merge Frame
D−Frame300(c) Lovebird1

500

1000
1500
Bits/Frame

2000

2500

(d) Newspaper

Fig. 10. PSNR v.s. encoding rate comparing proposed M-frame using fixed
target merging scheme with D-frame for sequences Balloons, Kendo,
Lovebird1 and Newspaper in static view switching scenario.
TABLE IIIBD- RATE REDUCTION OF PROPOSED M- FRAME USING FIXED TARGETMERGING SCHEME COMPARED TO D- FRAME IN STATIC VIEW SWITCHINGSCENARIO .

Sequence Name
Balloons
Kendo
Lovebird1
Newspaper

M-frame vs. D-frame-31.7%-40.1%-35.7%-31.1%

The coding results are shown in Fig. 10 and BD-rate [39]comparison can be found in Table III. We observe from
Table III that our proposed M-frame using fixed target merging
scheme achieved up to 40.1% BD-rate reduction compared toD-frame. Further, from Fig. 10 we observe that our M-frame
is better than D-frame in all bit-rate regions, especially in low
and high bit-rate region, mainly due to the skip block and EOB
flag tools. In high bit-rate region, due to the small distortion
in SI frames, more blocks will be classified into skip block,which efficiently reduces the bits to encode the M-frame, while
in low bit-rate region more coefficients are set to zero andskipped due to the EOB flag. This shows the effectivenessof our proposed M-frame using fixed target merging scheme
compared to the D-frame.

34
32

0

1000

2000
kBits/Frame

3000(c) Kimono1

4000

Merge Frame
D−FrameSP−Frame

32
30

0

1000

2000
3000
kBits/Frame

4000

5000

(d) ParkScene

Fig. 11. PSNR versus encoding rate comparing proposed RD-optimized
M-frame with D-frame and SP-frame for sequences BasketballDrive,
Cactus, Kimono1 and ParkScene in average case.

and Π1,1 , Π2,1 and Π3,1 as reference respectively. This resultsin encoded rate R1,1 , R2,1 and R3,1 for the three SI frames,
respectively. Then we encoded a M- / D-frame to merge thesethree SI frames into an identical frame. The corresponding rateM
D
for M-frame and D-frame are R2,2
and R2,2, respectively.
We also constructed SP-frames to enable stream-switchingfrom stream 1, 2 or 3 to target stream 2. We first encoded a
primary SP-frame using Π2,2 as target and Π2,1 as reference.
We then losslessly encoded two secondary SP-frames using
the primary SP-frame as target and Π1,1 , Π3,1 as referenceS
respectively. R2,1
denotes the rate for primary SP-frame while
S
S
R1,1 and R3,1 denote the rate for two secondary SP-frames.
As measure for transmission rate, we consider both theaverage and worst case code rates during a stream-switch. For
the average case, in the absence of application-dependent information, we assume that the probability of stream-switchingis equal for all views9 . Thus, the overall rate for RD optimized
M-frame is calculated as:
R1,1 + R2,1 + R3,1
M
+ R2,2.
(26)
RTMA =
3
The overall rate for D-frame is calculated as:
R1,1 + R2,1 + R3,1
D
RTDA =.
(27)+ R2,2
3
The overall rate for SP-frame is calculated as:D. Scenario 2: Bit-rate Adaptation
We next conducted experiments of bitrate adaptation scenario for single-view video sequences. M-frame is encoded
in a RD-optimized manner, described in section VI with thesystem framework shown in Fig. 2. Three streams of different
rates are encoded according to AIMD rate control behavior.
We constructed M- / D- frames to enable stream-switchingfrom stream 1, 2 or 3 to target stream 2 under different bitrates. We first encode three SI frames using Π2,2 as target

36

RTSPA =

SS
S
R1,1
+ R2,1+ R3,1.
(28)
3
The coding results for the average case are shown in
Fig. 11 and BD-rate comparison can be found in Table IV.
9 Note that if the stream-switching probabilities are far from uniform, more
complex coding structure designs using fixed target and optimized target
merge frames as building blocks are possible to minimize the expectedswitching cost. See [40] for details.

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

12

TABLE IV
BD- RATE REDUCTION OF RD- OPTIMIZED M- FRAME COMPARED TO D- FRAME AND SP- FRAME OF SCENARIO 2.

Sequence Name
BasketballDrive
CactusKimono1
ParkSceneM-frame vs. D-frame
Average Case Worst Case
-63.4%-63.7%-63.5%-63.2%-65.6%-65.4%-56.3%-56.7%

Cactus
42

40

40
38

38

PSNR

PSNR

BasketballDrive
42

36

34
Merge Frame
D−FrameSP−Frame

34
32

36

0

1000

2000
3000
kBits/Frame

4000

Merge Frame
D−FrameSP−Frame

32
30

5000

0

2000

(a) BasketballDrive
Kimono1

8000

ParkScene
42

42

40

40

38
PSNR

PSNR

6000

(b) Cactus

44

38
36

36
34

Merge Frame
D−FrameSP−Frame

34
32

4000
kBits/Frame

0

1000

2000
kBits/Frame

3000(c) Kimono1

4000

Merge Frame
D−FrameSP−Frame

32
30

0

1000

2000
3000
kBits/Frame

4000

5000

M-frame vs. SP-frame
Average Case Worst Case
-17.0%-39.4%-18.8%-42.1%-36.3%-49.9%-19.5%-43.8%

tween average and worst case for D-frame is small. However,for SP-frame the performance difference between average andworst case is large. This is due to lossless coding in secondary
SP-frames, resulting in a much larger size than primary SPframe (typically 10 times larger).
We have also collected statistics to examine the percentagesof code blocks chosen as merge, intra and skip blocks in
our proposed M-frame for different sequences at different
qualities. The results are shown in Table V. We see that thevast majority of blocks are chosen as merge blocks, whichmeans that the bulk of the observed coding gain is due toour carefully designed signal merging operator. For optimized
target merging, because QPM = 1 as discussed earlier, there
are very few blocks with exactly the same q-coeffs for all SI
frames, thus the percentages of skip blocks are very small. On
the other hand, for fixed target merging QPM = QPSI , so it isreasonable to observe that as QP increases, the percentages ofskip blocks increase also.

(d) ParkScene

Fig. 12. PSNR versus encoding rate comparing RD-optimized M-framewith D-frame and SP-frame for sequences BasketballDrive, Cactus,
Kimono1 and ParkScene in worst case.

We observe from Table IV that our proposed RD-optimized
M-frame achieves up to 65.6% BD-rate reduction comparedto D-frame and 36.3% BD-rate reduction compared to SPframe. Moreover, from Fig. 11 we observe that our proposed
RD-optimized M-frame is better than D-frame and SP-framein all bit-rate regions. Note that for the SP-frame case, if theswitching probability to the primary SP-frame is higher, it will
result in a smaller average rate.
For the worst case, the code rate for M-frame is calculated
as:
M
.
(29)
RTMW = max(R1,1 , R2,1 , R3,1 ) + R2,2
The rate for D-frame is calculated as:
D.
RTDW = max(R1,1 , R2,1 , R3,1 ) + R2,2

(30)

The rate for SP-frame is calculated as:
SSS
RTSPW = max(R1,1, R2,1, R3,1).

(31)

The coding results for the worst case are shown in Fig. 12
and BD-rate comparison can be found in Table IV. We observefrom Table IV that our proposed RD-optimized M-frame
achieves up to 65.4% BD-rate reduction compared to D-frameand 49.9% BD-rate reduction compared to SP-frame.
We observe in Table IV that the performance difference be-

E. Scenario 3: Dynamic View Switching
Finally we conducted experiments of dynamic view switching scenario for multiview video sequences. Three views
are encoded using same QP. The detailed frame structure
for M-frame, D-frame and SP-frame are the same as in
Section VII-D. Also, the overall rate calculation for average
and worst case are the same also.
The coding results of dynamic view switching for the
average case and the worst case are shown in Fig. 13 and
14 respectively. BD-rate comparison for average case andworst case can be found in Table VI. From Table VI weobserve that our proposed RD-optimized M-frame achieves
57.5% BD-rate reduction compared to D-frame and 19.3%
BD-rate reduction compared to SP-frame. From Table VI weobserve that our proposed RD-optimized M-frame achieves
58.7% BD-rate reduction compared to D-frame and 36.4%
BD-rate reduction compared to SP-frame.
F. Sensitivity Analysis
Finally, we investigate M-frame’s sensitivity to two parameters in the stream-switching setting: i) QPs of the switchingstreams, and ii) the number of SI frames that requires merging.
We conducted bitrate adaptation experiments for single-view
video sequences. For the first part, we first fixed QP of thetarget stream as Q, then changed QPs of three reference
streams to be Q − δ, Q and Q + δ, where δ ∈ {1, 2, 4, 8}.
By varying Q, we constructed PSNR versus rate plots forthe constructed M-frames for different δ. The results of fourIEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

13

TABLE VP ERCENTAGES OF MERGE , INTRA AND SKIP BLOCKS FOR DIFFERENT SEQUENCES AND QP S .
Sequence Namemerge
99.94%
99.55%
96.26%
93.81%

BasketballDrill (opt)
BQMall (opt)
Balloons (fixed)
Kendo (fixed)

QPSI = 22
intra
skip
0.06%
0%
0.19%
0.26%
3.25%
0.49%
3.29%
2.90%

merge
99.81%
97.88%
93.52%
92.25%QPSI = 26
intra
skip
0.19%
0%
1.67%
0.45%
3.03%
3.45%
2.70%
5.05%

merge
99.87%
98.21%
90.98%
88.80%QPSI = 30
intra
skip
0.13%
0%
1.35%
0.45%
1.96%
7.06%
2.80%
8.40%

merge
99.55%
98.01%
83.01%
85.06%QPSI = 34
intra
skip
0.45%
0%
1.67%
0.32%
2.57%
14.42%
2.12%
12.82%TABLE VI
BD- RATE REDUCTION OF RD- OPTIMIZED M- FRAME COMPARED TO D- FRAME AND SP- FRAME OF SCENARIO 3.

M-frame vs. D-frame
Average Case Worst Case
-55.1%-53.0%-53.8%-53.6%-57.5%-58.7%-51.6%-50.4%

Sequence Name
Balloons
Kendo
Lovebird1
Newspaper

Balloons

M-frame vs. SP-frame
Average Case Worst Case
-19.2%-35.0%-19.3%-36.4%-11.3%-28.7%-5.0%-12.9%

Kendo

50

Balloons

45

Kendo

50

46
44

45

45

40

PSNR

PSNR

PSNR

PSNR

42
40

40

40
38

Merge Frame
D−FrameSP−Frame

35

30

0

200

400
600
800
kBits/Frame

1000

Merge Frame
D−FrameSP−Frame
35

1200

0

200

400
kBits/Frame

600

Merge Frame
D−FrameSP−Frame

35

30

800

0

200

400
600
800
kBits/Frame

1000(a) Balloons(b) Kendo(a) Balloons

Lovebird1

Newspaper

Lovebird1

4550Merge Frame
D−FrameSP−Frame

36
34

1200

0

200

400
600
kBits/Frame

800

1000

(b) Kendo
Newspaper

45

45

40

40

PSNR

PSNR

PSNR

40

35

35
Merge Frame
D−FrameSP−Frame

30

PSNR

45
40

0

500

1000
1500
kBits/Frame

2000(c) Lovebird1

2500

30

35

Merge Frame
D−FrameSP−Frame

35

0

500

1000
kBits/Frame

1500

2000

(d) Newspaper

Fig. 13. PSNR versus encoding rate comparing proposed RD-optimized
M-frame with D-frame and SP-frame for sequences Balloons, Kendo,
Lovebird1 and Newspaper in average case.

sequences BasketballDrive, Cactus, Kimono1 and
ParkScene are shown in Fig. 15. We observe that while±8QP in general has the worst RD performance, the differences are very small. The reason is that, in our proposal, using
corresponding frames in the switching streams as predictors
we first encode SI frames that are already reconstructions of
the target picture at the target QP (shown in Fig. 4). Hence thesubsequent M-frame is tasked with merging SI frames of thesame QP, and the QPs of the switching streams have minimal
effect on the M-frame’s RD performance.
For the second part, we varied the number switching streams
from 3 to 9 and examined the M-frame’s RD performance. The
QPs settings when the number of SI frames were 3, 5, 7 and9 were respectively: {Q − 1, Q, Q + 1}, {Q − 2, Q − 1, Q, Q +1, Q + 2}, {Q − 4, Q − 2, Q − 1, Q, Q + 1, Q + 2, Q + 4} andMerge Frame
D−FrameSP−Frame
30

0

500

1000
1500
kBits/Frame

2000(a) Lovebird1

2500

Merge Frame
D−FrameSP−Frame
30

0

500

1000
kBits/Frame

1500

2000

(b) Newspaper

Fig. 14. PSNR versus encoding rate comparing proposed M-frame with Dframe and SP-frame for sequences Balloons, Kendo, Lovebird1 andNewspaper in worst case.

{Q − 8, Q − 4, Q − 2, Q − 1, Q, Q + 1, Q + 2, Q + 4, Q + 8}.
The resulting PSNR versus rate plots for the same four
sequences are shown in Fig. 16. We observe that, as thenumber of SI frames increased, the RD performance of Mframe worsened. This agrees with our intuition that as thenumber of SI frames increases, the maximum pair differenceZ∗b for a transform coefficient in a block b will likely increase,making the merging operation more difficult. However, Fig. 16
shows that the RD performance degrades gracefully for all four
sequences, demonstrating that our M-frame remains useful forchallenging stream-switching scenarios.
VIII. C ONCLUSION
In this paper, we propose a new merging operator—
piecewise constant (PWC) function—for merging different

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

BasketballDrive

14

Cactus42

implementation of DSC frame and H.264 SP-frames with areduction in decoder complexity.

45

40± 1 QP± 2 QP± 4 QP± 8 QP

36

PSNR

PSNR

40
38

R EFERENCES± 1 QP± 2 QP± 4 QP± 8 QP

35

34

30
0

500

1000
kBits/Frame

1500

2000

0

1000

(a) BasketballDrive

2000
kBits/Frame

3000

4000

(b) Cactus

KimonoParkScene

44

45

42

38

± 1 QP± 2 QP± 4 QP± 8 QP

36

PSNR

PSNR

40
40

± 1 QP± 2 QP± 4 QP± 8 QP

35

34

30
0

200

400
600
kBits/Frame

800

1000

0

500

(a) Kimono1

1000 1500 2000
kBits/Frame

2500

3000

(b) ParkScene

Fig. 15. PSNR versus encoding rate using different QPs in switching streams
for sequences BasketballDrive, Cactus, Kimono1 and ParkScene.
BasketballDrive

Cactus

42

45

40

PSNR

PSNR

40
38
36
3 SI Frames
5 SI Frames
7 SI Frames
9 SI Frames

34

3 SI Frames
5 SI Frames
7 SI Frames
9 SI Frames

35

32

30
0

500
1000
kBits/Frame

1500

0

1000

(a) BasketballDrive

2000
kBits/Frame

3000

4000

(b) Cactus

KimonoParkScene

44

45

42

PSNR

PSNR

40
40
38
3 SI Frames
5 SI Frames
7 SI Frames
9 SI Frames

36
34

3 SI Frames
5 SI Frames
7 SI Frames
9 SI Frames

35

30
0

200

400
600
kBits/Frame(a) Kimono1

800

1000

0

500

1000 1500 2000
kBits/Frame

2500

3000

(b) ParkScene

Fig. 16. PSNR versus encoding rate using different number of SI frames forsequences BasketballDrive, Cactus, Kimono1 and ParkScene.

reconstructed versions of a target frame to a unique one—toenable stream switching while preserving coding efficiency.
Specifically, in order to merge k-th transform coefficients ofdifferent side information (SI) frames to the same value, we
encode appropriate step sizes and shift parameters of a floor
function, so that all the SI coefficients fall on the same constantinterval. We propose two methods to select floor function
parameters for signal merging. In the first method, we selectedparameters so that coefficients are merged identically to a predetermined target value. In the second method, the merged
target value can be RD-optimized to induce better coding
performance. Experimental results show that for both cases,
our proposed merge frame has significant coding gain over an[1] G. Cheung, A. Ortega, N.-M. Cheung, and B. Girod, “On media data
structures for interactive streaming in immersive applications,” in SPIE
Visual Communications and Image Processing, Huang Shan, China, July
2010.
[2] M. Guo, Y. Lu, F. Wu, D. Zhao, and W. Gao, “Wyner-Ziv switching
scheme for multiple bit-rate video streaming,” in IEEE Transactions on
Circuits and Systems for Video Technology, vol. 18, no.5, May 2008,
pp. 569–581.
[3] G. Cheung, A. Ortega, and T. Sakamoto, “Coding structure optimization
for interactive multiview streaming in virtual world observation,” inIEEE International Workshop on Multimedia Signal Processing, Cairns,
Queensland, Australia, October 2008.
[4] G. Cheung, A. Ortega, and N.-M. Cheung, “Generation of redundant
coding structure for interactive multiview streaming,” in SeventeenthInternational Packet Video Workshop, Seattle, WA, May 2009.
[5] ——, “Bandwidth-efficient interactive multiview video streaming using
redundant frame structures,” in 2009 APSIPA Annual Summit andConference, Sapporo, Japan, October 2009.
[6] G. Cheung, N.-M. Cheung, and A. Ortega, “Optimized frame structureusing distributed source coding for interactive multiview streaming,”
in IEEE International Conference on Image Processing, Cairo, Egypt,
November 2009.
[7] G. Cheung, A. Ortega, and N.-M. Cheung, “Interactive streaming ofstored multiview video using redundant frame structures,” in IEEE
Transactions on Image Processing, vol. 20, no.3, March 2011, pp. 744–
761.
[8] N.-M. Cheung, H. Wang, and A. Ortega, “Video compression with flexible playback order based on distributed source coding,” in IS&T/SPIE
Visual Communications and Image Processing (VCIP’06), San Jose, CA,
January 2006.
[9] 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.
[10] 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.
[11] W. Dai, G. Cheung, N.-M. Cheung, A. Ortega, and O. Au, “Ratedistortion optimized merge frame using piecewise constant functions,”in IEEE International Conference on Image Processing, Melbourne,
Australia, September 2013.
[12] S. Pradhan and K. Ramchandran, “Distributed source coding using
syndromes (DISCUS): design and construction,” IEEE Transactions on
Information Theory, vol. 49, no. 3, pp. 626–643, 2003.
[13] 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.
[14] T. Wiegand, G. Sullivan, G. Bjontegaard, and A. Luthra, “Overview
of the H.264/AVC video coding standard,” in IEEE Transactions on
Circuits and Systems for Video Technology, vol. 13, no.7, July 2003, pp.
560–576.
[15] X. Sun, F. Wu, S. Li, G. Shen, and W. Gao, “Drift-free switching ofcompressed video bitstreams at predictive frames,” in IEEE Transactions
on Circuits and Systems for Video Technology, vol. 16, no.5, May 2006,
pp. 565–576.
[16] S.-M. Hsu, C.-W. Lin, and I.-H. Lee, “A new seamless bitstream
switching scheme for H.264 video adaptation with enhanced coding
performance,” in IEEE International Conference on Image Processing,Atlanta, GA, October 2006.
[17] A. Aaron, P. Ramanathan, and B. Girod, “Wyner-Ziv coding of lightfields for random access,” in IEEE International Workshop on Multimedia Signal Processing, Siena, Italy, September 2004.
[18] M. Guo, Y. Lu, F. Wu, D. Zhao, and W. Gao, “Practical Wyer-Ziv
switching scheme for multiple bit-rate video streaming,” in Proc. ICIP,
2006.
[19] N.-M. Cheung and G. Cheung, “Coding for Interactive Navigation in
High-dimensional Media Data,” in Emerging Technologies for 3D Video(eds Frederic Dufaux, Beatrice Pesquet-Popescu, Marco Cagnazzo),
2013.
[20] D. Taubman and R. Rosenbaum, “Rate-distortion optimized interactive
browsing of JPEG2000 images,” in Proceedings of International Conference on Image Processing, 2003, 2003, pp. 765–768.

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016[21] 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.
[22] W. Cai, G. Cheung, S.-J. Lee, and T. Kwon, “Optimal frame structure
design using landmarks for interactive light field streaming,” in IEEE
International Conference on Acoustics, Speech and Signal Processing,
Kyoto, Japan, March 2012.
[23] Z. Fan and A. Ortega, “Overlapped tiling for fast random access of 3-ddatasets,” in Proceedings of the IEEE DCC’07, 2009.
[24] S. J. Wee and B. Vasudev, “Compressed-domain reverse play of MPEG
video streams,” in Proceedings of SPIE Multimedia Systems and Applications (eds A. G. Tescher, B. Vasudev, V. M. Bove, Jr., and B.
Derryberry), 1999, pp. 237–248.
[25] C. W. Lin, J. Zhou, J. Youn, and M. T. Sun, “MPEG video streamingwith VCR functionality,” IEEE Trans. Circ. Syst. Vid., vol. 11, no. 3,
pp. 415–425, 2001.
[26] C.-H. Fu, Y.-L. Chan, and W.-C. Siu, “Efficient reverse-play algorithms
for MPEG video with VCR support,” IEEE Trans. Circ. Syst. Vid.,
vol. 16, no. 1, pp. 19–30, 2006.
[27] F.-O. Devaux, J. Meessen, C. Parisot, J. Delaigle, B. Macq, and C. D.
Vleeschouwer, “A flexible video transmission system based on jpeg2000
conditional replenishment with multiple references,” in Proceedings ofthe IEEE ICASSP’07, 2007.
[28] A. Naman and D. Taubman, “JPEG2000-based scalable interactive video(JSIV),” IEEE Transactions on Image Processing, vol. 20, no. 5, pp.
1435–1449, 2011.
[29] A. Mavlankar and B. Girod, “Spatial-random-access-enabled videocoding for interactive virtual pan/tilt/zoom functionality,” IEEE Trans.
Circ. Syst. Vid., vol. 21, no. 5, pp. 577–588, 2011.
[30] A. Mavlankar, P. Agrawal, D. Pang, S. Halawa, N.-M. Cheung, and
B. Girod, “An interactive region-of-interest video streaming system foronline lecture viewing,” in Proceedings of 18th International Packet
Video Workshop (PV), 2010, pp. 64–71.
[31] S. Halawa, D. Pang, N.-M. Cheung, and B. Girod, “ClassX an open
source interactive lecture streaming system,” in MM11 Proceedings of
the ACM International Conference on Multimedia, 2011, pp. 719–722.
[32] D. Pang, S. Halawa, N.-M. Cheung, and B. Girod, “Mobile interactive
region-of-interest video streaming with crowd-driven prefetching,” inProceedings of IMMPD 11 Proceedings of the 2011 International ACM
Workshop on Interactive Multimedia on Mobile and Portable Devices,
2011, pp. 7–12.
[33] H. Huang, G. Chan, G. Cheung, and P. Frossard, “Distributed content
replication for multiple movies in interactive multiview video streaming,” in 19th International Packet Video Workshop, Munich, Germany,
May 2012.
[34] 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.
[35] G. J. Sullivan, “Efficient scalar quantization of exponential and laplacian
random variables,” Information Theory, IEEE Transactions on, vol. 42,
no. 5, pp. 1365–1374, 1996.
[36] N.-M. Cheung, A. Ortega, and G. Cheung, “Rate-distortion based
reconstruction optimization in distributed source coding for interactive
multiview video streaming,” in Image Processing (ICIP), 2010 17th
IEEE International Conference on. IEEE, 2010, pp. 3721–3724.
[37] D.-M. Chiu and R. Jain, “Analysis of the increase and decrease algorithms for congestion avoidance in computer networks,” Computer
Networks and ISDN systems, vol. 17, no. 1, pp. 1–14, 1989.
[38] G. J. Sullivan, J. Ohm, W.-J. Han, and T. Wiegand, “Overview of theHigh Efficiency Video Coding (HEVC) Standard,” IEEE Transactions
on Circuits and Systems for Video Technology, vol. 22, no. 12, pp. 1649–
1668, 2012.
[39] G. Bjøntegaard, “Improvements of the BD-PSNR model,” document
VCEG-AI11, ITU-T SG16, 2008.
[40] B. Motz, G. Cheung, and N.-M. Cheung, “Designing coding structureswith merge frames for interactive multiview video streaming,” in 22ndInternational Packet Video Workshop, Seattle, USA, July 2016.

15

Wei Dai (S’10) received the B.E. degree in thecollege of control science and engineering from
Zhejiang University in 2010, and the Ph.D. degree in the department of electronic and computerengineering from the Hong Kong University of
Science and Technology in 2015. He is currently
with Agora.io, Inc. His research interests include
image/video signal processing, image/video coding
and deep learning techniques for computer vision.

Gene Cheung (M’00—SM’07) received the B.S.
degree in electrical engineering from Cornell University in 1995, and the M.S. and Ph.D. degrees inelectrical engineering and computer science from the
University of California, Berkeley, in 1998 and 2000,
respectively.
He was a senior researcher in Hewlett-Packard
Laboratories Japan, Tokyo, from 2000 till 2009. He
is now an associate professor in National Institute ofInformatics in Tokyo, Japan. He has been an adjunctassociate professor in the Hong Kong University of
Science & Technology (HKUST) since 2015.
His research interests include 3D image processing, graph signal processing,and signal processing for sleep analysis. He has served as associate editor forIEEE Transactions on Multimedia (2007–2011), DSP Applications Column
in IEEE Signal Processing Magazine (2010–2014) and SPIE Journal of
Electronic Imaging (2014–2016). He currently serves as associate editor forIEEE Transactions on Image Processing (2015–present), IEEE Transactions
on Circuits and Systems for Video Technology (2016–present) and APSIPA
Journal on Signal & Information Processing (2011–present), and as area editor
for EURASIP Signal Processing: Image Communication (2011–present). He
is a distinguished lecturer in APSIPA (2016–2017). He served as a member ofthe Multimedia Signal Processing Technical Committee (MMSP-TC) in IEEE
Signal Processing Society (2012–2014), and a member of the Image, Video,and Multidimensional Signal Processing Technical Committee (IVMSP-TC)(2015–2017). He has also served as technical program co-chair of International
Packet Video Workshop (PV) 2010 and IEEE International Workshop on
Multimedia Signal Processing (MMSP) 2015, and symposium co-chair for
CSSMA Symposium in IEEE GLOBECOM 2012. He is a co-author of
the best student paper award in IEEE Workshop on Streaming and Media
Communications 2011 (in conjunction with ICME 2011), best paper finalists
in ICME 2011, ICIP 2011 and ICME 2015, best paper runner-up award in
ICME 2012 and best student paper award in ICIP 2013.

Ngai-Man Cheung (M’00—SM’13) is an AssistantProfessor with the Singapore University of Technology and Design. He received the Ph.D. degree inelectrical engineering from the University of Southern California, Los Angeles. He has held research
positions at Stanford University and Mitsubishi Electric Research Labs (MERL). His research interests
include signal, image and video processing.

IEEE TRANSACTIONS ON IMAGE PROCESSING, MAY 2016

Antonio Ortega (S’91—M’95—SM’00—F’07) Antonio Ortega received the Telecommunications Engineering degree from the Universidad Politecnica
de Madrid, Madrid, Spain in 1989 and the Ph.D.
in Electrical Engineering from Columbia University,
New York, NY in 1994. At Columbia he was supported by a Fulbright scholarship.
In 1994 he joined the Electrical Engineering department at the University of Southern California(USC), where he is currently a Professor. He hasserved as Associate Chair of EE-Systems and director of the Signal and Image Processing Institute at USC. He is also a visiting
professor at National Institute of Informatics (NII). He is a Fellow of the IEEE,and a member of ACM and APSIPA. He has been Chair of the Image andMultidimensional Signal Processing (IMDSP) technical committee, a memberof the Board of Governors of the IEEE Signal Processing Society (SPS), andchair of the SPS Big Data Special Interest Group. He has been technicalprogram co-chair of MMSP 1998, ICME 2002, ICIP 2008 and PCS 2013.
He has been Associate Editor for the IEEE Transactions on Image Processing(IEEE TIP) and the IEEE Signal Processing Magazine, among others. He
is the inaugural Editor-in-Chief of the APSIPA Transactions on Signal andInformation Processing, an Associate Editor of IEEE T-SIPN and Senior Area
Editor of IEEE TIP. He received the NSF CAREER award, the 1997 IEEE
Communications Society Leonard G. Abraham Prize Paper Award, the IEEE
Signal Processing Society 1999 Magazine Award, the 2006 EURASIP Journalof Advances in Signal Processing Best Paper Award, the ICIP 2011 best paper
award, and a best paper award at Globecom 2012. He was a plenary speakerat ICIP 2013 and APSIPA ASC 2015.
His research interests are in the areas of signal compression, representation,communication and analysis. His recent work is focusing on distributed
compression, multiview coding, error tolerant compression, information representation in wireless sensor networks and graph signal processing. Almost 40
PhD students have completed their PhD thesis under his supervision at USC
and his work has led to over 300 publications in international conferences
and journals, as well as several patents.

16

Oscar C. Au received his B.A.Sc. from Univ. of
Toronto in 1986, his M.A. and Ph.D. from Princeton
Univ. in 1988 and 1991 respectively. After being
a postdoctoral researcher in Princeton Univ. for
one year, he joined the Hong Kong University of
Science and Technology (HKUST) in 1992. He wasa Professor of the Dept. of Electronic and Computer
Engineering, Director of Multimedia Technology
Research Center (MTrec), and Director of the Computer Engineering (CPEG) Program in HKUST. He
is now a patent engineer in LegalForce, learning to
be a patent agent in the US.
His main research contributions are on video and image coding andprocessing, watermarking and light weight encryption, speech and audio
processing. Research topics include fast motion estimation for MPEG1/2/4, H.261/3/4 and AVS, optimal and fast sub-optimal rate control, modedecision, transcoding, denoising, deinterlacing, post-processing, multi-viewcoding, view interpolation, depth estimation, 3DTV, scalable video coding,
distributed video coding, subpixel rendering, JPEG/JPEG2000, HDR imaging,compressive sensing, halftone image data hiding, GPU-processing, softwarehardware co-design, etc.
He has published 70+ technical journal papers, 380+ conference papers,
and 70+ contributions to international standards. His fast motion estimation
algorithms were accepted into the ISO/IEC 14496-7 MPEG-4 international
video coding standard and the China AVS-M standard. His light-weightencryption and error resilience algorithms are accepted into the China AVS
standard. He was Chair of Screen Content Coding AdHoc Group in the JCTVC
for the ITU-T H.265 HEVC video coding standard. He has 30+ granted patents
and is applying for 60+ more on his signal processing techniques. He has
performed forensic investigation and stood as an expert witness in the Hong
Kong courts many times.
Dr. Au is a Fellow of the Institute of Electrical and Electronic Engineering(IEEE) and is a Board 0f Governor member of the Asia Pacific Signal andInformation Processing Association (APSIPA). He is/was Associate Editorsof IEEE Trans. On Circuits and Systems for Video Technology (TCSVT),IEEE Trans. on Image Processing (TIP), and IEEE Trans. on Circuits andSystems, Part 1 (TCAS1). He is on the Editorial Boards of Journal of
Visual Communication and Image Representation (JVCIR), Journal of Signal
Processing Systems (JSPS), APSIPA Trans. On Signal and Information
Processing (TSIP), Journal of Multimedia (JMM), and Journal of Franklin
Institute (JFI).
He is/was Chair of IEEE CAS Technical Committee on Multimedia Systems
and Applications (MSATC), Chair of SP TC on Multimedia Signal Processing(MMSP), and Chair of APSIPA TC on Image, Video and Multimedia (IVM).
He is a member of CAS TC on Video Signal Processing and Communications (VSPC), CAS TC on Digital Signal Processing (DSP), SP TC on
Image, Video and Multidimensional Signal Processing (IVMSP), SP TC on
Information Forensics and Security (IFS), and ComSoc TC on Multimedia
Communications (MMTC).
He served on the Steering Committee of IEEE Trans. On Multimedia(TMM), and IEEE Int. Conf. of Multimedia and Expo (ICME). He also servedon the organizing committee of IEEE Int. Symposium on Circuits and Systems(ISCAS) in 1997, IEEE Int. Conf. On Acoustics, Speech and Signal Processing(ICASSP) in 2003, the ISO/IEC MPEG 71st Meeting in 2005, Int. Conf. on
Image Processing (ICIP) in 2010, and other conferences. He was General
Chair of Pacific-Rim Conference on Multimedia (PCM) in 2007, IEEE Int.
Conf. on Multimedia and Expo (ICME) in 2010 and the International Packet
Video Workshop (PV) in 2010. He won best paper awards in SiPS 2007, PCM
2007 and MMSP 2012. He is an IEEE Distinguished Lecturer (DLP) in 2009
and 2010, and has been keynote speaker for multiple times.