744

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

Interactive Streaming of Stored Multiview Video
Using Redundant Frame Structures
Gene Cheung, Senior Member, IEEE, Antonio Ortega, Fellow, IEEE, and Ngai-Man Cheung, Member, IEEE

Abstract—While much of multiview video coding focuses on
the rate-distortion performance of compressing all frames of all
views for storage or non-interactive video delivery over networks,
we address the problem of designing a frame structure to enableinteractive multiview streaming, where clients can interactively
switch views during video playback. Thus, as a client is playing
back successive frames (in time) for a given view, it can send arequest to the server to switch to a different view while continuing
uninterrupted temporal playback. Noting that standard tools for
random access (i.e., I-frame insertion) can be bandwidth-inefficient for this application, we propose a redundant representationof I-, P-, and “merge” frames, where each original picture can be
encoded into multiple versions, appropriately trading off expectedtransmission rate with storage, to facilitate view switching. We
first present ad hoc frame structures with good performance
when the view-switching probabilities are either very large orvery small. We then present optimization algorithms that generate
more general frame structures with better overall performance forthe general case. We show in our experiments that we can generate
redundant frame structures offering a range of tradeoff points
between transmission and storage, e.g., outperforming simple
I-frame insertion structures by up to 45% in terms of bandwidth
efficiency at twice the storage cost.
Index Terms—Media interaction, multiview video coding, video
streaming.

I. INTRODUCTIONM

ULTIVIEW video consists of sequences of spatiallycorrelated pictures captured simultaneously and periodically by multiple closely spaced cameras. The cameras canbe parts of a real physical camera system [1] or a virtual camera
setup inside a computer [2] using API manipulation of graphics
cards [3]. Much of the previous research in multiview video
focuses on compression: to design coding techniques exploiting
temporal (across time) and spatial (across view) correlation to
encode all frames of all views of a multiview sequence in a
rate-distortion optimal manner [4]–[7].

Manuscript received December 21, 2009; revised May 17, 2010; accepted
August 08, 2010. Date of publication August 26, 2010; date of current version
February 18, 2011. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Alex C. Kot.
G. Cheung is with the National Institute of Informatics, Tokyo 101-8430,
Japan (e-mail: cheung@nii.ac.jp).
A. Ortega is with the Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089-2564 USA (e-mail:antonio.ortega@sipi.usc.edu).
N.-M. Cheung is with the Department of Electrical Engineering, Stanford
University, Stanford, CA 94305 USA (e-mail: ncheung@stanford.edu).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TIP.2010.2070074

Compression of all multiview data in an interdependent way
is a sensible objective when the intended application is storageof the entire data set, or non-interactive delivery over networks,
i.e., where, as in TV broadcast [8], the clients’ potential interaction with the received multiview content does not effect how
and what data is delivered from the server.
In this paper, we focus instead on the problem of interactive multiview video streaming (IMVS). In this problem, after
one representation of a multiview sequence is pre-encoded andstored at the server, streaming clients interactively request desired views for successive video frames in time. Each client requests and plays back one single view at a time out of possibly
many available views, meaning that the requested data corresponds to only a small subset out of a large set of available multiview data at the server. The encoding is done once at the server
for a possibly large group of clients, each of which can navigate
the content by playing it back (in time) while switching views,
thus resulting in a different traversal of views across time foreach user. Our goal is to provide a desired level of view interactivity with minimum expected transmission bandwidth cost. The
extent of view interactivity is determined by the view switching
period ; i.e., view switching can only take place at multiples
of frames.
A natural approach to enable this kind of interactive viewswitching is to make use of standard random access tools, i.e.,making every th frame (in all views) an I-frame. Our work isbased on the observation that random access and view switching
are fundamentally different functionalities, and thus efficient
tools for one problem may not provide the best solution for theother. For random access to a frame, one can make no assumptions about which frames are available at the decoder; independently coded I-frames are therefore well suited for this purpose.
View switching, on the other hand, arises when temporal playback is not interrupted; i.e., successive frames in time are displayed, but one wishes to switch point of view. The key difference with respect to random access is that the decoder has accessto some of the frames (possibly from a different view) immediately preceding in time the requested frame. Thus, since consecutive frames in different views tend to be correlated, using an
I-frame for switching can be inefficient in terms of bandwidth.
The main focus of our work is then to study alternatives forview switching that are more bandwidth-efficient than simple
I-frame insertions. Note that our proposed tools do not support
random access, and thus we are not advocating using these tools
instead of random access tools such as I-frame insertion. Rather,
we propose to consider view switching and random access as
two explicitly different functionalities, supported by different
tools. It will then be up to the system designer to select the1057-7149/$26.00 © 2011 IEEECHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

745

Fig. 1. Examples and transmission rate/storage tradeoffs at one switching point using I-, various M-, and redundant P-frames. (a) Redundant P-frames and M-frame.
(b) Rate/storage tradeoffs at one switching point.

appropriate setting for a given application. For example, one
for view switching and separately
may select a parameterallow random access at every th frame, where typically.
One can see that the design of a multiview representation topermit interactive view switching can involve a tradeoff between
expected transmission rate and required storage space. For simcase, i.e., we require a user’s ability
plicity consider theto switch views at any time, but restrict allowable switching toview from a neighboring view in a one-dimensional camera
array setup, i.e.,. Since temporal playback is not interrupted, at time one of the previous frames’s of time(for at most three different views ) will
be available at the decoder. Thus, one possible way to support
switching would be the following: for each possible decodedframe, differentially encode one P-frame to represent
original picture
at time and view using
as a predictor—we call this approach redundant P-frames. An example
is shown in Fig. 1(a)(i) where three P-frames representing thesame picture
are constructed, each using a different predictor. Doing so for every view will increase the number of
decoding paths (frame representations) at each switching instantby a factor of three, resulting in a tree structure of size
when there are switching instants in between two I-frame insertion points. So while performing this redundant P-frame encoding for every view at every switching instant would lead to a
structure with minimum transmission cost (only bandwidth-efficient P-frames are used), the size of the resulting structure isimpractically large.
At the other extreme, one can construct a single quantized
representation of original picture(in Fig. 1(a)(ii)) forall possible decoder states; i.e., a frame (we call merge frameor M-frame) that can be correctly and identically decoded
the user is switching (frame
no matter from whichorin Fig. 1(a)(ii)). Doing so will keep
the number of frame representations (and hence decoding
for
total
paths) at a switching instant to a minimum
views. Obviously, an independently coded I-frame would fit
the M-frame reconstruction constraint, but more generally, one
can conceive other implementations of M-frame that employ
differential coding, using only one predictor from the previous’s (whichever one is available at the decoder)frame set
and produces the exact same reconstruction regardless of which
predictor was used. Example implementations of M-frames
include SP-frames in H.264 [9] and different distributed source

coding (DSC) techniques [10], [11].1 Different implementations of M-frames typically result in different tradeoffs between
storage and transmission costs, as shown in Fig. 1(b).2 Note,however, that all implementations of M-frame must havelarger transmission rate than a P-frame, since by definition, an
M-frame must merge multiple (more than one) decoding paths
each with a different predictor—a more stringent reconstruction
requirement than a P-frame which has only one decoding pathwith one known predictor. If we encode an M-frame using themost storage-efficient implementation available—the left-mostpoint on the convex hull3—for every view at every switching
point, this leads to the most storage-efficient frame structure.
However, as shown in Fig. 1(b), this structure has high transmission rate, since the size of an M-frame is in general muchlarger than a P-frame.
Note that the underlying assumption of the two approaches
above is that coding drift is not desirable and must be avoided,
either by preserving decoding paths via redundant P-frames, orby perfectly merging decoding paths via a single M-frame thatreconstructs to the exact same frame representation no matter
which decoded frame is available at the decoder for prediction.
A simple experiment can show that coding drift is indeed nonnegligible. Suppose we first encode a closed loop prediction representation for frames within the same view, then add cross-view
P-frames to facilitate view switches, as shown in Fig. 2(a). For
example, to switch from view 2 to view 1 at instant 2, we sendis prethe bold outlined frames in Fig. 2(a), even though
as predictor indictively coded using a different version ofstead of the transmitted, resulting in coding drift inonwards. (Due to quantization, the reconstructed image fromdecoding path ending with cross-view P-frame will be different
from image from path ending with same-view P-frame of sameview and instant.) Using H.263+ for source coding, we see in
Fig. 2(b) and (c) that due to drift, a single view switch resulted
in 1.2 dB loss in visual quality (PSNR), while two consecutive
switches resulted in well over 2 dB loss for both ballroom andakko&kayo sequences. Given view switches are a likely eventin an IMVS scenario, our discussed approaches of redundant
1In the context of DSC, “predictor” frames are used as side information fordecoding.
2Though in Fig. 1(b) DSC1 has higher transmission rate and storage than redundant P-frames at one switching point, due to its ability to merge all decoding
paths into one frame, DSC1 does not lead to exponential number of decoding
paths and storage in the entire structure.
3We discuss a storage-efficient implementation of an M-frame using
DSC—DSC0 in Fig. 1(b)—in Section III.

746

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

Fig. 2. Experiments showing effects of coding drift on visual quality during view switches. (a) Frame structure where pictures in the same view are encoded using
I- and subsequent P-frames, then additional cross-view P-frames (dotted edges) are added to faciliate view switches. Bold-edge frames are transmitted to provide
view switch from view 2 to 1 at instant 2. Drift begins at F due to predictor mismatch. (a) Structure with drift, (b) ballroom, (c) akko&kayo.

P-frames and M-frames to circumvent coding drift are reasonable if one chooses to preserve quality across view switches.4
From the above discussion, it is clear that more practicalmultiview representations lie between the two extremes,containing the optimal combination of I-frames (for random
access), P-frames (for low transmission rate) and M-frames(for storage efficiency), that optimally trade off transmission
and storage costs. In this paper, we develop heuristics and optimization algorithms that construct good frame structures for
IMVS using available I-, P, and implementations of M-frames
as building blocks. In our experiments with several multiview
video datasets, we show that our algorithm can offer a range of
tradeoff points between transmission and storage costs, and thatthe generated frame structures outperform the simple I-frame
insertion approach. In particular, we show that in some cases
our algorithm generates frame structures reducing expectedtransmission rate by up to 45% compared to I-frame insertion
approach, at twice the storage costs.
The outline of the paper is as follows. We first review related work in Section II. We then overview our IMVS system
and models and describe three example implementations ofM-frames in Section III. We formulate the problem of optimallygenerating redundant frame structures for IMVS in Section IV.
For intuition, we first discuss two classes of heuristic structures
for the extreme cases when the likelihood of switching viewis very high or very small, and then based on the intuition
developed, we discuss a greedy optimization that performs
reasonably well for all values of view switching probabilities
in Section V. To further improve performance, we extend thegreedy optimization into a provably optimal recursive one(under some simplifying conditions) in Section VI at the costof increased complexity. Finally, we discuss our experiments
and conclude in Sections VII and VIII, respectively.
II. RELATED WORK
A. Interactive Media Streaming
The communication paradigm for our IMVS work is one
where the server continuously and reactively sends appropriate
4A generalization is to use an imperfect M-frame to merge multiple decoding
paths, such that the resulting reconstructed frame depends on the predictor available at the decoder, but any two reconstructed frames (using two different predictors) differ by no more than a chosen threshold d^ to bound coding drift inthe system. Theoretically, the same optimization presented in this paper can beused to find optimal combinations of redundant P-frames and such an imperfectM-frame. Implementation of an imperfect M-frame, however, is left for future
work.

media data in response to a client’s periodic requests for datasubsets; we call this paradigm interactive media streaming.
This is in sharp contrast to non-interactive media streaming
scenarios like terrestrial digital TV broadcast [8], where theentire media set is delivered server-to-client before a clientinteracts with the received data set (e.g., switching TV channel,etc). Interactive media streaming has the advantage of reduced
bandwidth utilization since only the requested media subset istransmitted and is used for a wide range of media modalities.
One example is interactive browsing of JPEG2000 images [12],[13], where a small spatial area, selected by a user, of a possibly
very large image encoded using discrete wavelet transform,
is transmitted successively via incremental quality layers. Yetanother example is video playback with flexible decoding [14],where a video frame is DSC encoded using both past and future
frames as predictors (side information), so that frames can besent either forward or backward in time per client’s request,
and the client can simply decode and play back the video in thetransmission order with no excess buffering.
B. Interactive Light Field Streaming
In the case of light fields [15], where a subset of a densely
sampled 2-D array of images is used to interpolate a desired
view using image-based rendering (IBR) [16], the notion ofinteractive media streaming has been investigated extensively[17]–[22]. These works are motivated by the very large sizeof the original image set—on the order of tens of Gigabytes[23]—so that sending the entire set before view navigation will
create intolerably large delay to the user. To exploit inter-view
spatial correlation among nearby views for coding gain, many
works employed disparity compensation while providing somelevel of random access. Two representative works are [17] and[19], which used DSC and SP-frame-like lossless coding respectively to accommodate different decoding paths. We firstnote that both proposals in [17] and in [19] are captured in our
M-frame abstraction of “single frame reconstruction using oneof multiple predictors”. Hence, these are viewed as implementations of an M-frame in our formulation, using which our proposed optimization can generate structures containing the optimal combinations. We also note that [17], [19] do not consider
multiple decoding paths resulting from the use of redundantP-frames to represent an original picture, hence [17], [19] provide no mechanism to systematically further lower transmission
cost by making use of extra storage capacity, if available.

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES[21], [22] first assumed that each coding block of an image
is encoded as INTRA, INTER or SKIP as done in H.263 [24].
Then, for a requested INTER coding block to be correctly decoded, all blocks in its dependency chain5 that are not alreadyin the client cache must be transmitted, creating a cost both intransmission rate and decoding complexity. The notion of transmitting and decoding multiple blocks before displaying a single
one is called rerouting in our previous work [25]. Our findingsin [25] showed that rerouting provides marginal performancegain in the IMVS scenario when view switching period isreasonably large and when redundant P-frames are already used
(multiple-frame representation of a single picture is not considered in [21], [22]). Hence, we will assume rerouting is not usedduring formulation in Section IV.
In summary, though we focus on the IMVS scenario indeveloping our optimization framework in this paper, we cantheoretically retarget our optimization for interactive light fieldstreaming: previous switching techniques like [17], [19] canbe abstracted into different implementations of M-frames,
and rerouting [21], [22] can be easily incorporated into the
optimization as done in our earlier work [25]. Unlike theseprevious work on light fields, our optimization can in addition
systematically trade off transmission rate with storage bycontrolling the number of decoding paths created by redundantP-frames. An in-depth investigation specifically for light fieldstreaming using our optimization is left for future work.
C. Interactive Multiview Video Streaming
Most of the previous research in multiview video has focusedon efficient compression of all frames of all views exploiting
temporal (across time) and spatial (across view) correlation[4]–[6]. This approach makes obvious sense when the application is compact storage of the entire multiview content,
or non-interactive media streaming applications as describedearlier.
For interactive streaming of stored multiview video, thetwo-layer approach proposed in [26], [27] can be one solution, where coarse and fine quality layers of several views aregrouped and pre-encoded. During actual streaming, a subset ofviews of low quality plus two views of high quality, carefully
selected based on user’s behavioral prediction, would then be
sent to the client. All transmitted views were subsequently
decoded, and the highest quality views that matched the user’s
at-the-moment desired views were displayed. While the intended IMVS application is the same, our approach is different
in that we focus on the optimal tradeoff between transmission
rate and storage using combinations of redundant P-frames andM-frames in our frame structure.
The most similar work to our proposal is [28], which developed three separate frame structures to support three typesof interactivity: view switching, frozen moment and view
sweeping. While the authors recognized the importance of a“proper tradeoff among flexibility (interactivity), latency andbandwidth cost”, no explicit optimization was performed to
5By dependency chain we mean all the blocks that need to be decoded before
the requested block can be decoded, i.e., an INTRA block followed by a succession of disparity compensated INTER blocks.

747

explore the best possible tradeoffs among these quantities in
one structure given an interaction model.
In our previous work, we formally posed the IMVS problem
as a combinatorial optimization in [2], proved its NP-hardness,and provided two heuristics-based algorithms to find good frame
structures while allowing unlimited rerouting for IMVS. [25] isa more thorough and analytical treatment of the same problem
with limited rerouting, using only I- and P-frames in the structure. We have also developed two novel DSC implementations
to serve as M-frames for IMVS in [11]. Preliminary results ofusing I-, P-, and DSC frames in an IMVS optimized structure
is presented in [29]; this paper is a generalization of [29] where
the optimization is posed as a search for the best combinationof I-, P-, and generalized M-frames.
D. Distributed Source Coding
DSC [30] has been studied extensively in the past few years
for low-complexity video encoding, e.g., [31], [32]. In addition, DSC has been investigated for a variety of applications,
ranging from scalable coding [33], [34], error resilience video
transmission [35], [36], distributed compression of multiview
image/video [37], [38], to hyperspectral image compression[39] (see [40] for a recent survey). In this paper, we extend ourprevious work [10], [11] to apply DSC to facilitate interactive
view switching, and this is significantly different from other
DSC applications. Relevant information theoretic results forthis setup were developed in [41], [42].
III. SYSTEM MODEL, INTERACTION MODEL & M-FRAME
IMPLEMENTATIONS
To transition to later sections describing our core contribution
on frame structure optimization for IMVS, as introduction material we first overview the IMVS system model, the assumed interaction model between an observer and the multiview content,
and describe three different implementations for merge frames(M-frames).
A. System Model
The system model we consider for our IMVS problem isshown in Fig. 3. A Multiview Video Source simultaneously
captures multiple pictures ofdifferent views at regularintervals. An example of a multiview sequence of two views
across four time instants is shown in Fig. 5(a). A Video Server
sequentially grabs the captured uncompressed pictures from
Multiview Video Source and encodes them offline, using an
optimized frame structure of I-, P-, and different implementations of M-frames for each picture batch of all views acrosscapturing intervals. The Video Server stores the structured
representation of the sequence locally, using which the server
serves multiple streaming clients subsequently. An alternative
approach of real-time encoding a path traversal tailor-madefor each streaming client’s interactivity is computationallyprohibitive if the number of clients is large.
In the sequel, we will use the term frame to denote a specific coded version of a picture and the term picture for thecorresponding original captured image. A frame can be an
intra-coded I-frame, a differentially coded P-frame with asingle predictor, or a conceptual merge frame (M-frame) that

748

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

Fig. 3. Interactive multiview video streaming system.

uses a known set of predictors at encoding time. I-frame isused for random access. For view switching, P-frame offers
the lowest possible transmission rate but increases the storage
required as the number of decoding paths multiplies over time.
M-frame offers the merging of multiple decoding paths into
one single representation but at a higher transmission cost thanP-frame.
Available M-frame implementations include SP frames in
H.264 [9] or DSC [10], [11]. Each implementation itself can becomposed of one or more encoded components, each encodedusing a different coding technique. Each implementation of
M-frame must satisfy the M-frame reconstruction condition:
the exact same decoded version must be reconstructed at the
decoder no matter which one of a known set of predictors isavailable at the decoder buffer. Three example implementationsof M-frames using DSC are described in detail in Section III.C.
Our system will have representation redundancy, in the sensethat there may be more than one coded version (frame) torepresent a given picture.
B. View Interaction Model
We assume a view interaction model where, upon watching
any decoded version of the picture, corresponding to time
instant and view , an interactive client will request a codedof view and next time instant,version of pictureand,6 with view transiwhere view is between
tion probability; we call this interactivity forward viewswitching.7 Another possible interactivity for multiview video isto freeze video in time and switch view (static view switching);
this interactivity can be efficiently supported by novel usage of
DSC [11]. Incorporation of static view switching into our optimization framework is left for future work.
Note that a significant difference between our setting and thatof general light field streaming [17]–[22] is that in the lattercase the user is free to explore a static scene in all directions,while here we play forward in time with only limited switchingpossibilities (i.e., among neighboring views). The implication is’s of difthat only a limited number of previous frames
ferent views ’s (three views in our setting) could have beenis requested, and so redundecoded when a current frame
dant P-frame representation of a picture is more practical in
IMVS than general light field streaming. (However, redundantP-frames can be practical for light field streaming if a more re6One can of course easily generalize our 2-neighbor view switching toclosest-V -neighbor view switching.
7All video streaming systems today offer forward playback of video, hence
forward view switching is a natural extension.

stricted interaction model—only vertical and horizontal viewswitches are permitted, for example—is adopted.)Though our interactive model presumes a client’s desire to, our model encomswitch views at single-frame level.
passes the more general case of a view switching periodin our model can repreIn the more general case, a “frame”
sent consecutive actual frames of view (a carefully chosen
I-, P- or M-frame determined by our optimization followed byconsecutive P-frames of the same view).
C. Implementations of M-Frames
We discuss three novel implementations of M-frames using
DSC [11]. Each implementation represents a different tradeoff
between transmission and storage cost as illustrated in Fig. 1(b).
1) DSC Implementation 0 of M-Frame: The first DSC implementation (DSC0) of M-frame is straightforward: constructa single DSC component
for all possible transitions into’s of previous instantview of instant from frames
using algorithm in [10]. In other words, given side information’s, encode a DSC image for target
of previous frames
using codec in [10], such that the same image can be re’s isconstructed no matter which one of previous framespresent at the decoder buffer. The size of implementation DSC0
) is modeled as, where is(lone DSC component
the maximum view index difference between DSC component
and a predictor. Size of a DSC image in general is inversely
proportional to the amount of correlation between the target andthe weakest correlated predictor [10]. An example of DSC0 isshown in Fig. 4(b).
. In other
The transmission cost of DSC0 is simply
words, the transmission cost of DSC0 is the size of the lone DSC
itself.
component
DSC0 represents the most storage-efficient one of three implementations of M-frames using DSC discussed here; because
this approach exploits correlation between successive frames(using a previous frame as side information), both the transmission and storage costs are smaller than a corresponding I-frameas shown in Fig. 4(a).
2) DSC Implementation 1 of M-Frame: The second DSC
implementation (DSC1) of M-frame is the following: first
construct multiple closed-loop differentially coded components’s corresponding to all possible transitions from frames’s of previous instant, then construct a DSC componentof the same view and same instant from the constructed’s. Closed-loop differentially coded components’s areessentially P-frames encoded using motion/disparity compensation, while the DSC component is encoded using DSC codec
described in [10]. See Fig. 4(c) for an example of DSC1.
, given predictor set , isThe storage cost of DSC1
’s plus thethe size of all differentially coded components
size of the DSC component:(1)is the size of the differentially coded component
where
given predictor , andis the size of the DSC component using predictors of the same time and view. The trans-

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

749

Fig. 4. Examples of DSC implementations of M-Frame for two views. I-, P-, and M-frames are denoted as solid circles, solid squares and solid diamonds, respectively. Differentially coded components and DSC components are denoted as dotted squares and dotted diamonds, respectively. (a) I- and P-frames only, (b) I-, Pframes and DSC0, (c) I-, P- frames and DSC1, (d) I-, P- frames and DSC0+1.

mission cost
given predictor
can be written similarly:. With the additional closed-loop differen’s, storage cost of DSC1 is almost
tially coded components
surely larger than DSC0. However, given the DSC component
and its predictors are of the same instant and view, a large correlation exists between the target and the weakest predictor. Thisthan
. For predictor withresults in a much smaller
strong correlation to target(e.g., same view as), onlyplus a small DSC compoa small differential component
is required, resulting in smaller transmission cost, i.e.,nent. This is in contrast to DSC0, where a large
coding penalty(size corresponding to the least correlated
predictor in ) must be paid for all predictors ’s.
3) DSC Implementation 0+1 of M-Frame: We can combine
the two discussed DSC constructs into a hybrid one (DSC0+1):
construct multiple closed-loop differentially coded components’s and subsequent DSC component
as done in DSC1,
then replace a subset of differentially coded components’sthat correspond to unlikely view switches with a single DSC. See Fig. 4(d) for an example where three difcomponent’s in Fig. 4(c) are replaced byferentially coded components
a DSC component. The size of a DSC component
with multiple predictors is larger than a differentially coded, hence the transmission cost of each replacedcomponent
decoding path is larger. On the other hand, the combined storage

cost of the multiple replaced differentially coded components’s is likely larger than a single DSC component, hence
DSC0+1 offers a tradeoff of transmission and storage that is in
between DSC0 and DSC1.
IV. PROBLEM FORMULATION
We now formulate our IMVS problem as a combinatorial
optimization problem. We first present necessary definitions in
Section IV.A. We then define IMVS formally in Section IV.B.
We present an alternative expression for the Lagrangian formulation, useful during algorithm development, in Section IV.C.
A. Definitions
1) Redundant Frame Structure: Suppose we are given a mulviews andtime switching instants,8tiview sequence ofand corresponding view transition probabilities’s as discussed in Section III.B. For simplicity of discussion we assume. Fig. 5(a) showsfor now that video starts with a single view,andan example multiview sequence where.
Given a multiview sequence, one can construct a redundantframe structure , comprised of I-, P-, and different imple’s,’s and’smentations of M-frames, denoted as
8Given random access and view switching intervals T and T , respectively,
where T > T , we have N
b T = T c0 .

= ( )( )1750IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

Fig. 5. Example of redundant frame structure. I-, P-, and M-frames are drawn as circles, rectangles and diamonds, respectively. A single edge from F
toF in (b) means a P-frame P
is differentially coded using reference frame F . A set of edges from F
to a set of frames F ’s means an M-frameM
is predictively coded using reference frames F ’s. (a) Multiview video sequence. (b) Redundant frame structure.

TABLE ISUMMARY OF NOTATIONS FOR IMVS PROBLEM FORMULATION(M-frame of implementation ), respectively, to represent thesequence and enable IMVS. Note first that we do not specify
whether the predictions for P-frames are motion- and/or disparity-compensated; our abstraction only aims to capture the dependencies among frames and not the particular encoding tool
used. Note also that we specify only a storage and transmission cost here for each of implementations of an M-frame. Our abstraction and subsequent optimization apply generally to all implementation of M-frames, including the three
discussed in Section III.C. Without loss of generality, however,is the most storage-efwe do assume that the first construct
ficient among all implementations—i.e., it corresponds to theleft-most tradeoff point on the convex hull of transmission rateversus storage, as illustrated by DSC0 in Fig. 1(b). A structure representing the example multiview sequence in Fig. 5(a)is shown in Fig. 5(b).
A frame structure forms a directed acyclic graph (DAG)
with I-frames as start nodes (nodes without ancestors). In
is the lone start node of structure .
Fig. 5(b), I-frame
is redundant in that an original picture
can be represented’s. In Fig. 5(b),is represented by
by multiple framesand. From frame
to a feasible
two P-frames, without loss of generality,
view switchsuch
we assume structure contains one target framethat. This ensures structure is feasible; i.e.,
when viewer
a server can schedule transmission of.
requests view after observing(which are inGiven view transition probabilities
trinsic to the problem) and a frame structure , we will next
and transmission cost.
formally define storage cost
See Table I for a summary of notations.
2) Frame Display Probabilities: For ease of discussion, we’s—the probabilfirst define frame display probabilities’s are sent by server to be displayed at theities that frames’s from front ofviewer upon requests. We can compute, to the back as follows using view transithe structure ,tion probabilities,:(2)

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

In words, starting with initial I-frameof display probaof frame
bility one, the display probability
is the sum of display probabilities of previous frames’sthat can switch view to, scaled by transition probabili.
ties3) Storage Cost: For a given frame structure , we can de, by simply adding thefine the corresponding storage cost,storage required by all encoded frames in :
(3)
where
denotes the storage required by frame. For an, rate only depends on the frame itself, and so we deI-frame. In contrast, the rate for a P-frame
dependsnote
also on the frame used for prediction. Assuming
is differentially encoded using predictor, the corresponding rate
; i.e., we assume that
depends only
will beon the view of predictor. For example, we expect that a, and so in
more accurate prediction can be obtained if
general, for.
As discussed in Section III.C, the size of an M-frame
depends on implementation . Further, for a given implementaalso depends on the set of frames
tion , size of an M-frame. We hence writefrom which observer can view-switch toas—a function
the size of an M-frameof both the implementation and the set of predictorsthat precedes M-framein structure . We will assume inis smaller if the predictor set
general that size M-frame
is smaller:of frame
depends on theTransmission costframe type: if
is I- or P-frame, it is just the frame size
itself scaled by frame display probability. If
is an M-frame, then depending on which previous framea view transition has arrived from, the transmission
would be different. See (7) at thecostbottom of the page.
isFor example, from Fig. 5(b) the transmission costthe sum of costs
andfor the two possible
transitions fromand, respectively.
B. Optimization Problem Defined
We can now formally define the search for the optimal redundant frame structure for IMVS as a combinatorial optimization
problem: find a structure , using a combination of I-, P-, andimplementations of M-frames, in feasible space9 that possesses the smallest possible expected transmission cost
while a storage constraint is observed. We denote this opti:
mization problem as(8)Though (8) differs from the definition in [2], a similar proof
is NP-hard. Givencan be easily constructed to show thatthe computational difficulty of (8), we focus next on solving
the corresponding Lagrangian optimization for given Lagrange
multiplier instead10:(9)(4)
As previous discussed, we will also assume that the first of
implementations is the most storage-efficient, i.e.,(5)
We will discuss how’s,’s and’s
were generated in our experiments in Section VII.
4) Transmission Cost: Similar to storage cost, given a structure we can define a corresponding transmission cost
for as the sum of individual transmission costs
’s:

(6)

751

C. Alternative Expression for Lagrangian Cost
It turns out that one of the complexities of the
problem—optimal selection of implementation given available ones for a given chosen M-frame—can be solved separably
without loss of optimality when the optimal frame structure issought in (9). More precisely, when evaluating the Lagrangianas preobjective of (9), given previous frame set, one can find the optimal
dictors and target view frame
9The feasible space is the set of structures that enable an observer, uponof deviewing displayed frame F , to switch to a displayed frame F
sired view k , where transitions have been constrained depending on desirable
application characteristics, e.g., j and k may be constrained to be neighboring
views.
10Technically, the corresponding Lagrangian should be C (S )+[B (S )0B ].
 are fixed, however, it is equivalent to (8).
When  and B

(7)

752

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

Fig. 6. Examples of frame structures generated using path-based heuristic. (a) Minimum storage frame structure. (b) Minimum storage structure plus added
sub-path. Additional path in (b) is shown in thick-line rectangles.

implementation
amongof M-frame
costthat minimizes the Lagrangianas follows:

simple, perform well when the view transition probabilities’s are very small and very large, respectively. The resulting intuition will guide us to a greedy structure optimizationin Section V.C. For the sake of keeping the heuristics simple, wefirst assume the most storage-efficient implementationis always used when an M-frame is selected. The recursivealgorithm in Section VI will consider the more general casewhen implementations of an M-frame are available.
A. Path-Based Heuristic Structures(10)

Equation (10) says that for a given M-frame with the same
previous frame set
and target frame, one can findin Lagrangian
the optimal implementation for M-frame
sense, independent of other parts of the overall structure .
Hence, the selection of the optimal implementation for M-frame
can be solved simply as a sub-routine using (10) when the Lagrangian cost of the M-frame is needed during frame structure
search in (9).
Given the derivation for Lagrangian cost of an M-frame in(10), we can now write the Lagrangian cost of structure simply’s, of individual frames
as a sum of Lagrangian costs,
’s:
(11)

(12)
We will focus on minimizing the Lagrangian cost of structure
in form (12) in later sections.
V. HEURISTIC APPROACHES
In a nutshell, good frame structures should contain the “right”
mixture of redundant P-frames (for bandwidth efficiency) andM-frames (for storage efficiency) for a given Lagrangian
multiplier . To gain intuition as to what frame structures are
good, we first consider two heuristics, path-based heuristic
and tree-based heuristic, to construct mixtures of redundantP-frames and M-frames, without performing any explicit Lagrangian optimization. We show that these heuristics, though

We first consider the case when the view transition probabili’s are very small; i.e., an observer will very likely reties
main in the same view throughout all potential view switches.
To construct a good redundant frame structure for this case,we start with the minimum storage frame structure, as discussed
in Section I, one where an M-frame is used at each switching
andpoint. Fig. 6 shows an example of this structure for. Note that this structure has no redundant representation; each picture is represented by only one decoded frame.
Note also that this structure is optimal regardless of transition
probabilities when is sufficiently large.
This minimum storage frame structure comes with hightransmission cost. To reduce transmission cost by incrementally increasing redundancy in the structure (thereby increasingstorage), one can do the following. Because an observer is very
likely to stay in a path of the same view throughout, a simple
heuristic is to locate the most likely transition
from frame
to a view in the structure, and add a sub-pathof P-frames for this transition till the end of the structure. In
is added to the transition
Fig. 6(b), a sub-pathfromto same view 1. Note that in this case, the originalis subsequently replaced by a P-frame, because
M-frame’s set of previous frame
the sub-path addition has caused
predictors to reduce to a single predictor.
We compare the performance of structures generated using
the path-based heuristic to structures generated by a full optimization procedure to be described in Section VI. The performance of each structure is shown as a data point in Fig. 7(a),representing the tradeoff between the expected transmission rateand storage required to store the structure. We see that when thetransition probabilities are low, the path-based heuristic indeed
produced structures (path-lo) that closely approximates performance of the optimal (opt-lo), demonstrating that the useof the path abstraction indeed is appropriate. When the transition probabilities are high, however, the performance of thepath-based heuristic (path-hi) and the optimal (opt-hi) are

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

753

Fig. 7. Comparison of transmission rate/storage tradeoff between path-based heuristic and full optimization, and between tree-based heuristic and full optimization, respectively. (a) Rate/storage tradeoff for path-based heuristic. (b) Rate/storage tradeoff for tree-based heuristic.

Fig. 8. Examples of frame structures generated using path-based heuristic. (a) Minimum transmission frame structure. (b) Minimum transmission structure oflimited depth.

quite far apart. This motivates us to derive a different heuristic
when the transition probabilities are high.
B. Tree-Based Heuristic Structure
When the view transition probabilities’s are verylarge, e.g., when it is just as likely for an observer to stay in thesame view as to switch to the neighboring view(s), we use a
different heuristic. We now start from the minimum transmission frame structure as described in Section I, one where only
P-frames are used at every switching point. This is essentiallyas the root ofa full-tree of depth with the lone I-frame. The
the tree; Fig. 8(a) shows such a full-tree of depth
tree has exponential
number of frames—3 is the sizeof the set of neighboring views an observer can switch to at aswitching point—which is not practical for large . However,this redundant structure is optimal in Lagrangian cost whenis sufficiently small.
As similarly done before for the minimum storage structure,
to lower the storage cost by incrementally reducing the redundancy in the minimum transmission structure, we do the following. Because each transition is equally likely, the probabilityof arriving at a certain P-frame of a given tree depth is exactly
the same as arriving at any other P-frame of the same depth.
That means the Lagrangian costs of individual P-frames at thesame tree depth are roughly the same (assuming all P-frames
are of roughly the same size). On the other hand, as P-framesof one tree depth transition to P-frames of the next tree depth,
the total transmission cost of P-frames of the next tree depth

remains the same (still one P-frame per transition), while thestorage has increased by factor 3. That means Lagrangian cost of
the P-frame set at deeper tree depth are strictly more expensive
than cost of the P-frame set at shallower tree depth. A reasonby
able heuristic then is to eliminate P-frames of tree depth
replacing P-frames at tree depth with M-frames. More specifically, starting with the minimum transmission structure, one canwith M-frames for one strucreplace P-frames at depth
ture—cutting the tree into halves—resulting in smaller storage
but higher transmission cost. For more tradeoff between storageandand transmission, one can replace P-frame at depthwith M-frames for another structure—cutting the tree
into thirds, etc. Fig. 8(b) shows a structure where P-frames atof the full free in Fig. 8(a) are replaced bydepth
M-frames.
We now compare the performance of structures generatedusing the tree-based heuristic to that of the full optimization
procedure, shown in Fig. 7(b). We see that when the transition
probabilities are high, the tree-based heuristic produced structures (tree-hi) approximate that of the optimal (opt-hi),proving empirically that the use of the tree abstraction is indeed
appropriate. On the other hand, when the switching probabilities
are low, the performance of the tree-based heuristic (tree-lo)
compared to the optimal (opt-lo) is inferior. This suggeststhat an optimal structure must use a combination of paths andtrees corresponding to different transition probabilities to optimize the rate/storage tradeoff. We discuss such an optimization
next.

754

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

C. Greedy Structure Optimization
In this section, we derive a greedy structure optimization
based on our observations of Sections V.A and V.B. While in
Sections V.A and V.B we started with a complete structure(minimum storage or minimum transmission, respectively) andthen incrementally made heuristic modifications to the structure
to lower transmission or storage cost, here we iteratively build astructure from front to back, i.e., starting with an initial I-frame, we construct frames’s at view switching instant 1,’s at switching instant 2 and so on. At eachthen frames
switching instant , the key question we need to answer is:’s constructed at previous switching instantgiven frames, how do we optimally construct frames’s to minimize(12) for given Lagrange multiplier ?
’s at switching
Suppose that given constructed frames
most likely view switches frominstant , we identify the’s, and construct a P-frame to fulfill each of theview
switches. We then construct M-frames for total views and’s to them. Let
assign the remaining view switches frombe the sum of probabilities of thesemost likely viewswitches. If a P-frame at instant has average size , and anandM-frame has average transmission and storage cost ofrespectively, then we can find the optimal that minimizes
the Lagrangian cost at instant as follows:(13)
We can now grow a structure from front to back greedilyusing (13) at every
starting from the initial I-frame
switching instant. Note that the algorithm is greedy in that at
each instant , the locally optimal th “slice” of the structure is.
chosen with no lookahead into future switching instants
We now compare the performance of structures generatedusing the greedy optimization to that of the full optimization
procedure, shown in Fig. 9. We see that the greedy optimization produced structures (heu-hi, heu-mid, heu-lo)
approximate that of the optimal (opt-hi, opt-mid,
opt-lo) on most data points whether the view transition
probabilities are high, medium or low. There are, however,points that are far from the optimal due to the greedy natureof (13). We next investigate an optimal algorithm, extendingon the greedy optimization here to take into account futureswitching instants as well via recursion, generating the best
structures possible in a Lagrangian sense.
VI. RECURSIVE OPTIMIZATION
We now extend the previous greedy structure optimization in
Section V.C to a recursive algorithm to generate best possible. We first derive an optimal algorithm forstructures forwith exponential running time in Section V.C. We thendiscuss methods to reduce its complexity for practical use in
Sections VI.B and VI.C.
A. Optimal Algorithm
We first provide an overview of the algorithm to develop intuition. Similar to the greedy algorithm in Section V.C, we build aframe structure from front to back one “slice” at a time, starting

Fig. 9. Comparison of transmission rate/storage tradeoff between greedy optimization and full optimization.

. We define
as a partial strucwith an initial I-frameup till switching instantisture constructed from
. For given partial structure, each frame
simplyin
has a display probability
computable
will switch to view
front-to-back using (2). Each framewith probability
either via a P-frame
predicted from, or via an M-frame, each with different local Lagrangian costs at instant . An optimal structure
at switching instant given
has the smallest sum of:i) local Lagrangian costs at instant , and ii) future (recursive)
minimum Lagrangian costs stemming from .
as the local structure at instant for view
We first define; eachreceives view transitions from frames’s into frames’s of view .
can be a set of M-frames’s, a set of P-frames’s each coded with different refer’s in, or a combination of both. Partial
ence frames
structure at the next instant is simply a concatenation of preand chosen local structures’s forvious partial structure
all view ’s with appropriate coding dependencies attached.
We now define the minimum Lagrangian costfrom switching instant till last switching instant , given, as the sum of local Lagrangian cost
partial structureof all view ’s at instant , and recursive cost
, where structure
is a concatenation ofand’s as discussed:(14)
Note that all feasible local structures’s must be searchedexhaustively to find the global minimum in (14).
for view can be diLocal Lagrangian costand of P-frames
in localvided into costs of M-frames
structure, where, to receive transitions to’s:view from previous frames(15)

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

The local Lagrangian costis simply the sum of
individual Lagrangian cost of each M-frame
in
using
(10):

755

B. Complexity Reduction 1: Simplify Local Structure Selection’s that are searched at each function invocationin (14) to reduce complexity. Towards that goal, we
first state the following result:Lemma 1: If local Lagrangian cost of switching fromframes’s in partial structure
to a single M-frame
in local structure
at instant and view is no larger
than corresponding local Lagrangian costs of switching toconstructed P-frames’s,, then resulting
global Lagrangian cost of switching tois also no larger’s.
than resulting global Lagrangian costs11 of switching to
In other words, if the local cost of merging transitions to an
M-frame is no larger than the cost of corresponding P-frames,
then surely the merging decision of using M-frame is also globally optimal. The proof for Lemma 1 is stated as follows.
Proof of Lemma 1: We show that for any set of subtrees’s in, one canof P-frames stemming from constructed
construct a corresponding subtree of P-frames stemming frominsuch that the resulting global Lagrangian cost is’s below’s, weno larger. For given set of subtrees
by taking the union
construct corresponding subtree forof’s; i.e., for each P-framein, we add a correof the same size to if does not already havesponding
constructed. (See Fig. 10 for an example.) First, we know
since union of sets is no larger thento any frame
sum of sets. Further, transmission cost frominis exactly the same fromto its corresponding
in , hence the transmission cost of using over’salone induces nocan be no worse. Since by assumption’s, we concludeandlarger local Lagrangian cost thanalso induce no larger global cost than’s and’s.
To make good use of Lemma 1, we construct the following
greedy heuristic to simplify the selection of local structure
for view given invocation. First, we create an
to which all viable switches to view from
M-frameframes’s inwould transition. Then we identify
in, whose corresponding local Lathe frame,
grangian cost associated with transition to M-frame, would decrease the most if
transitions
to a P-frame, instead. We create,
to transition to, and compute global Lareassign
grangian cost using (14) to test global optimality. The processinand
repeats to find the most locally beneficial
add corresponding P-frametountil no cost-reducing
remains.
From the description of the greedy heuristic, it is clear that
local structures’s, where is the number ofat mostviable transitions to view from frames
’s in
, are
recursively computed for global optimality using (14). The stopcan be constructed toping condition—that no more P-frame
lower local Lagrangian cost—is guaranteed to be optimal within
local structures given Lemma 1. (The corollary
the set ofof Lemma 1 is that local Lagrangian cost cannot be further decreased by constructing more P-frames means that global Lagrangian cost also cannot be further decreased by constructing
more P-frames.) Further, it turns out that restricting testing ofTo reduce complexity in (14), in this section we derive amethodology to systematically reduce the number of local

F(16)
As discussed in Section IV.C, the optimal of implementaand encoding
tions of an M-frame given predictor set
targetis found locally using (10) without loss of global optimality.
for P-frames
The local Lagrangian cost’s, on the other hand, is the sum of each transition probaplus times the size of:bility into a unique(17)

is the sum of display
Display probability for M-frame’s scaled byprobabilities of previous predictor framestransition probabilities
’s:

(18)
We claim that a call
, using (14) solves
the Lagrangian (9) optimally. We state this result formally as atheorem below and then provide a simple proof.
Theorem 1: Using initial argument, optimization (14) returns an optimal solution to.
Proof: We prove this by induction. For the base case of, it is clear that starting from any initialrecursion depth
at instant 0, (14) finds the optimal solution by
structure slice
exhaustively searching all feasible local structures’s with no. For the inductive case, suppose (14) isrecursive termyields the optimal
optimal for recursive depth ; i.e.,. For recursive depth of,structure of depth given
we can do the following. Given initial slice , exhaustively’s, and for each set, evaluate its local
search all feasible set of, whereis simply
Lagrangian cost plus recursive costand set of’s. By assumption,
a combination of
returns optimal structure of depth given . Given’s areexhaustively searched, this procedure gives the optimal solution. Note that this is exactly how (14) performs its
for depth. Hence, the inductive case is also
optimization for depth
proven, and (14) is globally optimal.
Though optimal, (14) is nevertheless exponential in running
time; each of the potential transitions into instant and view
, can be mapped to either a P- or an M-frame, hence there are at
least
local structures’s for view alone. For general, exhaustive search is simply not tractable, and we will hence
discuss strategies to reduce the overall complexity next.

structures

11This lemma assumes that each P-frame

is of size rkP

encoded using predictor( ) as described in Section IV.A.

756

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

Fig. 10. Example of union construction of M-frame subtree. (a) Multiple P-frames and subtrees. (b) M-frame and subtree.

Fig. 11. Complexity reduction 1: Simplify selection of local structure s’s during invocation L (SFig. 12. Complexity reduction 2: Sliding window of maximum recursion depth h during invocation L (Sglobal optimality to only these
local structures remains
globally optimal if the only implementation of M-frame is an
I-frame implementation, and frame sizes of I- and P-frames do
not change across time and across view. The intuition is thatgiven the difference in frame sizes between M- and P-frames remains the same across time, there is nothing extra to be gainedthat cannot already be obtained locally atin future instants
instant . See Appendix I for a detailed proof of this special case.
insteadMore generally, one can create another M-frame
when reassigning’s in
to transiof P-frametion to newly created frames to lower local Lagrangian cost. For
completeness, Fig. 11 describes the general complexity reduc’s during invocation procedure 1 to select local structures.
tion
C. Complexity Reduction 2: Sliding Window of Recursion
Depth
Though the number of next-level recursive calls from each
invocation is now linear due to procedure in Section VI.B, thenumber of total calls is still exponential in the depth of the recursion . Hence, we propose a sliding-window strategy of maxas shown in Fig. 12. Essentially,
imum lookahead depth
the algorithm performs optimization (14) up to maximum depth
starting with initial I-frame,, as argument, adds).

).

the first “slice” of the optimized partial frame structure to ,as the new argument to solve (14) again
and then use updated
up to maximum depth , and so on. We will show in Section VII
that the sliding-window strategy produces good approximatedresults.
VII. EXPERIMENTATION
A. Experimental Setup
To gather multiview video data for our experiments, weused three neighboring views12 from 100-frame sequences
akko&kayo and ballroom at 320 240 resolution and 30
fps and 25 fps, respectively. The distance between neighboring
cameras for akko&kayo and ballroom were 5 cm and 20
cm respectively; using both data sets can test our algorithm withmultiview sequences of different characteristics. To generate
data for DSC0 and DSC1 implementations of M-frames, weused the algorithm in [11], which is based on H.263 tools(e.g., half-pel motion estimation). We selected QP such that
12We believe the general trends in the tradeoff between transmission rate andstorage will remain the same for larger number of views, due to our assumptionthat an observer can only switch to a neighboring view. Hence, any intermediate
view (i.e., neither the left-most nor right-most view) will behave like the middle
view of the three views used in our experiments.

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

757= 24 = 3

Fig. 13. Tradeoffs between expected transmission rate and storage per picture for T;T, comparing performance between full recursive optimization(opt) and optimization with finite sliding window of size h (fast). (a) akko&kayo, (b) ballroom.

I-, P-, and DSC-frames were reconstructed to the same quality(around 34 dB).
More precisely, for each sequence, we generated encoding’s,’s, as inputs to our optimization algorithm asrates
was obtained when we encoded pictureasfollows. EachI-frame.
’s were obtained when we encoded picture
in a single-view sequence where each
was motion-compen. For’s,, we first generated foursated fromzigzagged sequences as follows:
.
1)
2)
.
.
3)
4)
.
, we simply located the zigzagged stream
For eachthat contained the sub-sequence
and assigned thecorresponding coding rate.
For transition probabilities’s, we assume frame
remains at the same view
with probability, and tranandwith probability
sitions to neighboring views
each. Frametransition to the single neighboringwith the same probability .
view
B. Experimental Results
1) Approximation Using Sliding-Window Strategy: We firstexamine how closely the fast sliding-window strategy (fast)
discussed in Section VI.C approximates the original algorithm
without the sliding window (opt). For random access period
and switch period of—hence optimizaof—we gention window depth oferated tradeoff points between expected transmission rate andstorage required per picture using opt, shown in Fig. 13 forthe two test sequences. Lagrangian multiplier was swept from0.01 to 10.24 to induce different tradeoffs. We also generated.
tradeoff points for fast when the lookahead depth was
We see that the convex hull of fast closely resembled that ofopt, demonstrating that the sliding-window strategy performs
numerically close to the original in practice. For this case when
, we found experimentally that performance as a function, beyond whichof lookahead improves noticeably up to
the improvement is marginal. We conjecture that the reason isthat sufficient number of frame structures are already considered(including the “full tree” framefor optimization whenleaf nodes). Hence, lookahead
is usedstructure withfor the rest of the results section.
2) Algorithm Performance Comparison 1: Different Transition Probabilities: For algorithm comparison, using first aframes and switching periodrandom access period offrames, we plotted the tradeoff points for our algorithmofusing I- and P-frames only (IP) and I-, P- and M-frames (IPM),
for the akko&kayo and ballroom sequences in Fig. 14(a)and (b), respectively. To induce different transition probabilities’s, was set to 0.1 and 0.2 for two different trials.
We also plotted the performance of the random access approach(RA-I) where I-frames were inserted at all switching points forview switching.
We first see that RA-I was represented by a single point;
because the I-frame insertion algorithm was fixed, it had one
corresponding fixed transmission and storage cost, and therefore
could not take advantage of extra storage capacity if available
to lower transmission cost.
Second, we see that our algorithm found tradeoff points inIPand IPM that were to the lower left of RA-I; i.e., our algorithm generated frame structures that offered lower transmission rates than and required smaller storage than RA-I. Thisis particularly noticeable when M-frames were used in addition
to I- and P-frames, where our algorithm generated frame structures with 38% and 20% smaller expected transmission rate respectively for the two sequences, while requiring comparable
storage.
Third, unlike RA-I, our algorithm offered a range of tradeoff
points to take advantage of extra storage when available tofurther decrease expected transmission rate. In particular, attwice the storage of RA-I, our algorithm generated frame
structures with 45% and 32% smaller expected transmission
rate than RA-I for akko&kayo and ballroom, respectively.
The performance improvement of IPM over RA-I was more
dramatic for akko&kayo than ballroom; we conjecture that
this was due to relatively smaller sizes of P-frames comparedto I-frames in akko&kayo, as a result of the closely spaced
cameras.
Fourth, we see that using M-frames (IPM) in addition I- andP-frames (IP) did generate better tradeoff points at all storage

758

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

= 30

=3

= 30

= 01

Fig. 14. Tradeoffs between expected transmission rate and storage per picture for T;T, comparing performance among random acesss I-frame
insertion (RA-I), I- and P-frames only (IP), and I-, P-, and M-frames (IPM) for different view switching probability . (a) akko&kayo, (b) ballroom.

Fig. 15. Tradeoffs between expected transmission rate and storage per picture for T;: , comparing performance among random acesss I-frame
insertion (RA-I), I- and P-frames only (IP), and I-, P-, and M-frames (IPM) for different view switching period T . (a) akko&kayo, (b) ballroom.

requirements. The differences are largest at stringent storage requirement, when M-frames are used more often then redundantP-frames.
Finally, we see that as the switching probabilities increased,
the performance of our algorithm deteriorated gradually (curvesof IP and IPM shifted to the upper-right). This is expected, as
more transitions mean more inter-view predicted frames are required, resulting in higher transmission rates. The improvement
over RA-I, however, remains dramatic.
3) Algorithm Performance Comparison 2: Different View
Switching Periods: We repeated the same experiment again,
where this time we varied the view switching period from
3 to 5. The results are shown in Fig. 15(a) and (b) for the twotest sequences. We observe that larger switching period means
smaller transmission rate and storage in general; this is intuitivesince staying in the same view more often means same-view
predicted P-frames that are very bandwidth-efficient wereused more extensively between transitions. Nevertheless, ouralgorithm did generate similar patterns of tradeoff points thatare superior to RA-I, and using M-frames did perform better
than optimization using I- and P-frames only.
4) Algorithm Performance Comparison 3: Frame Rate Approximation: One source of complexity in our algorithms is theacquisition of data—specifically, frame sizes for I-, P and different implementations of M-frames—for input into our opti-

mization. To reduce the burden of data collection, we investigated the use of estimated data as representatives for the entire data set, in particular, use statistics of frames in the firstswitching instant for optimization of the entire sequence. For
of instant 1 and view
example, use of P-frame size
for all’s, . Fig. 16 shows the performance comparison of using approximated rates versus exact rates for bothakko&kayo and ballroom sequences. Our results show thatfor both cases when M-frames was (IPM) and wasn’t used (IP)in the optimization, using estimated data gave almost as good aperformance. Hence, in a scenario where encoding complexity
is a concern (though the proposed system is for stored-and-playback applications), one can choose to use estimated data for optimization with minor loss in performance.
VIII. CONCLUSION
In this paper, we motivated the need for an interactive multiview video streaming (IMVS) system, where an observer canperiodically send feedbacks to the server requesting desired
views out of many available. In response, the server will sendcorresponding pre-encoded video data to the observer fordecoding and display without interrupting forward video playback. Observing that one can trade off expected transmission
rate with a modest increase in storage when designing thepre-encoded frame structure, we formulated a combinatorial

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES

759= 30 = 0 2

Fig. 16. Tradeoffs between expected transmission rate and storage per picture for T;: , comparing performance between I- and P-frames only (IP)and I-, P-, and M-frames (IPM) using frame rate approximation. (a) akko&kayo, (b) ballroom.

Fig. 17. Structure constructions and corresponding Lagrangian costs for proof of optimality of greedy procedure. (a) Possible structures at instant i(b) Lagrangian cost versus transition probability.

optimization problem, where the optimal structure contains thebest mixture of I-frames (for random access), P-frames (for lowtransmission rate) and merge or M-frames (for low storage),
trading off transmission rate with storage. We presented fastheuristic-based strategies, as well as a near-optimal recursivealgorithm as potential solutions to the optimization problem.
Our results show that when compared to the simple I-frame
insertion strategy, our proposed frame optimization can reduce
expected transmission rate by up to 45% at twice the storage.
APPENDIX
We prove here that the greedy procedure described in
Section VI is optimal when the only implementation of
M-frame is an I-frame, and the sizes of P- and I-frames do
andbe thenot change across time and across view. Let
sizes of I- and P-frames respectively for all views and all time.
Under these assumptions, the greedy procedure will iteratively
select transitions with the largest probabilities for P-frame
constructions, until the resulting local Lagrangian cost exceedsthat of the previous iteration.
We prove the optimality of the greedy procedure by contradiction. Suppose at instant , an alternative procedure selects atthat is not the traniteration a transition with probability. Supsition with the th largest probability , i.e.,pose further that this alternative procedure eventually leads to asmaller overall Lagrangian cost compared to the greedy procedure. First, due to the different transition selection for P-frame
construction at iteration , the greedy procedure has a smaller
local Lagrangian cost over the alternative one at this instant by, as shown in Fig. 17(b). The difference intransition selection also leads to different display probabilities
and , for the greedy
for the resulting M-frame (I-frame),+ 1.

.
and alternative procedure, respectively, where
and.
Note also that, the transition probabilities to the same view
At instantfrom M-frame and the P-frame created from iteration of instant are
andrespectively for the greedy procedure,
andrespectively for the alternative procedure. Thisanddue to thedifference in transition probabilities at instantalternative procedure can lead to a lower local Lagrangian cost
, ifthan the greedy procedure for same view at instantthe optimal structure contains a P-frame for the M-frame in instant and an I-frame for the P-frame constructed in iteration
in instant , as illustrated in Fig. 17(a)(i). We call this structure. Any other structure for the alternative procedure would
lead to the same or worse local Lagrangian cost than a comparable structure for the greedy procedure. In contrast, the optimal
can be either
structure for the greedy procedure at instant, or a structure where only an I-frame is constructed tohandle both transitions from M-frame and P-frame of th largest
probability in instant —we call this structure I-only (seeFig. 17(a)(ii) for an illustration). We bound the gain in local Lagrangian cost by the alternative procedure for the two cases asfollows.
Suppose the optimal structure for the greedy procedure at in, like the alternative procedure, is also
. Becausestant
the alternative procedure leads to a larger transition probability
into the P-frame in instant, it will inducecompared toa smaller local Lagrangian cost at instant
the greedy procedure. The magnitude of the gain, however, is.
bounded by
Suppose now the optimal structure for the greedy procedure
is instead I-only. First, that means that it is
at instantmore costly to create a P-frame for transition of probability

760IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 20, NO. 3, MARCH 2011

stemming from the M-frame of instant than to merge this transition to an existing I-frame:[13] JPEG2000 Interactive Protocol (Part 9—JPIP). [Online]. Available:
http://www.jpeg.org/jpeg2000/j2kpart9.html[14] N.-M. Cheung, H. Wang, and A. Ortega, “Video compression withflexible playback order based on distributed source coding,” presented
at the IS&T/SPIE Visual Communications and Image Processing(VCIP’06), San Jose, CA, Jan. 2006.
[15] M. Levoy and P. Hanrahan, “Light field rendering,” in Proc. SIGGRAPH’96, Aug. 1996, pp. 31–42.
[16] H.-Y. Shum, S. B. Kang, and S.-C. Chan, “Survey of image-based representations and compression techniques,” IEEE Trans. Circuits Syst.
Video Technol., vol. 13, no. 11, pp. 1020–1037, Nov. 2003.
[17] A. Jagmohan, A. Sehgal, and N. Ahuja, “Compression of lightfield rendered images using coset codes,” in Proc. 37th Asilomar Conf. Signals,
Systems and Computers, Nov. 2003, vol. 1, pp. 830–834.
[18] A. Aaron, P. Ramanathan, and B. Girod, “Wyner-Ziv coding of lightfields for random access,” presented at the IEEE Int. Workshop on Multimedia Signal Processing, Siena, Italy, Sep. 2004.
[19] P. Ramanathan and B. Girod, “Random access for compressed lightfields using multiple representations,” presented at the IEEE Int. Workshop on Multimedia Signal Processing, Siena, Italy, Sep. 2004.
[20] C.-L. Chang and B. Girod, “Receiver-based rate-distortion optimized
interactive streaming for scalable bitstreams of light fields,” presented
at the 2004 IEEE Int. Conf. Multimedia and Expo, Taiwan, Jun. 2004.
[21] I. Bauermann and E. Steinbach, “RDTC optimized compression ofimage-based scene representation (part I): Modeling and theoreticalanalysis,” IEEE Trans. Image Process., vol. 17, no. 5, pp. 709–723,
May 2008.
[22] I. Bauermann and E. Steinbach, “RDTC optimized compression ofimage-based scene representation (part II): Practical coding,” IEEE
Trans. Image Process., vol. 17, no. 5, pp. 724–736, May 2008.
[23] M. Levoy and K. Pulli, “The digital michelangelo project: 3-D scanningof large statues,” in Proc. SIGGRAPH’00, Aug. 2000, pp. 131–144.
[24] Video Coding for Low Bitrate Communication, ITU-T, Recommendation H.263, Feb. 1998.
[25] G. Cheung, A. Ortega, and N.-M. Cheung, “Generation of redundant
coding structure for interactive multiview streaming,” presented at the17th Int. Packet Video Workshop, Seattle, WA, May 2009.
[26] A. M. Tekalp, E. Kurutepe, and M. R. Civanlar, “3DTV over IP:
End-to-end streaming of multiview video,” IEEE Signal Process.
Mag., vol. 24, no. 6, pp. 77–87, Nov. 2007.
[27] E. Kurutepe, M. R. Civanlar, and A. M. Tekalp, “Client-driven selective
streaming of multiview video for interactive 3DTV,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 11, pp. 1558–1565, Nov. 2007.
[28] J.-G. Lou, H. Cai, and J. Li, “A real-time interactive multi-view video
system,” presented at the ACM Int. Conf. Multimedia, Singapore, Nov.
2005.
[29] G. Cheung, N.-M. Cheung, and A. Ortega, “Optimized frame structureusing distributed source coding for interactive multiview streaming,”
presented at the 2009 IEEE Int. Conf. Image Processing, Cairo, Egypt,Nov. 2009.
[30] D. Slepian and J. Wolf, “Noiseless coding of correlated information
sources,” IEEE Trans. Inf. Theory, vol. IT-19, pp. 471–480, Jul. 1973.
[31] R. Puri and K. Ramchandran, “PRISM: A new robust video codingarchitecture based on distributed compression principles,” presented atthe 2002 Allerton Conf. Communications, Control, and Computing,
Urbana-Champaign, IL, Oct. 2002.
[32] B. Girod, A. Aaron, S. Rane, and D. Rebollo-Monedero, “Distributed
video coding,” Proc. IEEE, Special Issue on Advances in Video Coding
and Delivery, vol. 93, no. 1, pp. 71–83, Jan. 2005.
[33] H. Wang, N.-M. Cheung, and A. Ortega, “A framework for adaptive
scalable video coding using Wyner-Ziv techniques,” EURASIP J. Appl.
Signal Process., 2006, DOI 10.1155/ASP/2006/60971.
[34] Q. Xu, V. Stankovic, and Z. Xiong, “Layered Wyner-Ziv videocoding for transmission over unreliable channels,” EURASIP J. Signal
Process. Special Issue on Distributed Source Coding, vol. 86, no. 11,
Nov. 2006.
[35] A. Sehgal, A. Jagmohan, and N. Ahuja, “Wyner-Ziv coding of video:
An error-resilient compression framework,” IEEE Trans. Multimedia,
vol. 6, no. 2, pp. 249–258, Apr. 2004.
[36] J. Wang, V. Prabhakaran, and K. Ramchandran, “Syndrome-based robust video transmission over networks with bursty losses,” presented at
the Proc. Int. Conf. Image Processing (ICIP), Atlanta, GA, 2006.
[37] X. Zhu, A. Aaron, and B. Girod, “Distributed compression for large
camera arrays,” presented at the Workshop on Statistical Signal Processing, St. Louis, MO, 2003.

We can now bound the cost improvement of thestructureof the alternative procedure over the I-only structure of thegreedy procedure as follows:

Hence, the gain is also bounded by.
The same analysis will show that the gain for transition to other, scaled by probability, is also boundedviews ’s,similarly. Hence, alternative procedure does not lead to a lower. By inLagrangian cost than the greedy procedure at instantduction, it does not lead to a lower Lagrangian cost in future instants as well. Therefore, the alternative procedure does not leadto a smaller Lagrangian cost and the optimality of the greedy
procedure is proven.
REFERENCES[1] T. Fujii, K. Mori, K. Takeda, K. Mase, M. Tanimoto, and Y. Suenaga,“Multipoint measuring system for video and sound—100 camera andmicrophone system,” presented at the IEEE Int. Conf. Multimedia andExpo, Toronto, Canada, Jul. 2006.
[2] G. Cheung, A. Ortega, and T. Sakamoto, “Coding structure optimization for interactive multiview streaming in virtual world observation,”presented at the IEEE Int. Workshop on Multimedia Signal Processing,
Cairns, Queensland, Australia, Oct. 2008.
[3] OpenGL: The Industry’s Foundation for High Performance Graphics.
[Online]. Available: http://www.opengl.org[4] P. Merkle, A. Smolic, K. Muller, and T. Wiegand, “Efficient prediction structures for multiview video coding,” IEEE Trans. Circuits Syst.
Video Technol., vol. 17, no. 11, pp. 1461–1473, Nov. 2007.
[5] M. Flierl, A. Mavlankar, and B. Girod, “Motion and disparity compensated coding for multiview video,” IEEE Trans. Circuits Syst. Video
Technol., vol. 17, no. 11, pp. 1474–1484, Nov. 2007.
[6] S. Shimizu, M. Kitahara, H. Kimata, K. Kamikura, and Y. Yashima,“View scalable multiview coding using 3-D warping with depth
map,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 11, pp.
1485–1495, Nov. 2007.
[7] J. Kim, P. Lai, J. Lopez, A. Ortega, Y. Su, P. Yin, and C. Gomila,“New coding tools for illumination and focus mismatch compensationin multiview video coding,” IEEE Trans. Circuits Syst. Video Technol.,vol. 17, no. 11, pp. 1519–1535, Nov. 2007.
[8] Digital Video Broadcasting. [Online]. Available: http://www.dvb.org/[9] M. Karczewicz and R. Kurceren, “The SP- and SI-frames design for
H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7,
pp. 637–644, Jul. 2003.
[10] N. Cheung and A. Ortega, “Distributed source coding application to
low-delay free viewpoint switching in multiview video compression,”presented at the Picture Coding Symp., PCS’07, Lisbon, Portugal, Nov.
2007.
[11] N.-M. Cheung, A. Ortega, and G. Cheung, “Distributed source coding
techniques for interactive multiview video streaming,” presented at the27th Picture Coding Symp., Chicago, IL, May 2009.
[12] D. Taubman and R. Rosenbaum, “Rate-distortion optimized interactive
browsing of JPEG2000 images,” presented at the IEEE Int. Conf. Image
Processing, Barcelona, Spain, Sep. 2003.

CHEUNG et al.: INTERACTIVE STREAMING OF STORED MULTIVIEW VIDEO USING REDUNDANT FRAME STRUCTURES[38] X. Guo, Y. Lu, F. Wu, W. Gao, and S. Li, “Distributed multi-view videocoding,” presented at the Conf. Visual Communications and Image Processing (VCIP), San Jose, CA, 2006.
[39] N.-M. Cheung, C. Tang, A. Ortega, and C. S. Raghavendra, “Efficient wavelet-based predictive Slepian-Wolf coding for hyperspectral
imagery,” EURASIP J. Signal Process. Special Issue on Distributed
Source Coding, vol. 86, no. 11, Nov. 2006.
[40] C. Guillemot, F. Pereira, L. Torres, T. Ebrahimi, R. Leonardi, and J. Ostermann, “Distributed monoview and multiview video coding,” IEEE
Signal Process. Mag., vol. 24, no. 5, pp. 67–76, Sep. 2007.
[41] S. Draper and E. Martinian, “Compound conditional source coding,
Slepian-Wolf list decoding, and applications to media coding,” presented at the Int. Symp. Information Theory (ISIT), Nice, France, 2007.
[42] N.-M. Cheung and A. Ortega, “Compression algorithms for flexible
video decoding,” presented at the Visual Communications and Image
Processing (VCIP), San Jose, CA, 2008.

Gene Cheung (M’00–SM’07) received the B.S. degree in electrical engineering from Cornell University, Ithaca, NY, in 1995, and the M.S. and Ph.D. degrees in electrical engineering and computer sciencefrom the University of California, Berkeley, in 1998
and 2000, respectively.
He was a senior researcher with Hewlett-Packard
Laboratories, Japan, Tokyo, from 2000 to 2009. He
is currently an Assistant Professor with the National
Institute of Informatics, Tokyo, Japan. His researchinterests include media representation and networktransport, single- /multiple-view video coding and streaming, and immersive
communication and interaction. He has published more than 15 international
journal and 50 conference publications.
Dr. Cheung has served as an Associate Editor of the IEEE TRANSACTIONSON MULTIMEDIA since 2007, and serves as area chair of the IEEE International
Conference on Image Processing (ICIP) 2010, and as technical program co-chairof the International Packet Video Workshop 2010. He was a co-recipient of theTop 10% Paper Award in IEEE International Workshop on Multimedia Signal
Processing 2009.

761

Antonio Ortega (S’91–M’95–SM’00–F’07) received the Telecommunications Engineering degreefrom the Universidad Politecnica de Madrid, Madrid,
Spain, in 1989 and the Ph.D. degree in electricalengineering from Columbia University, New York,NY, in 1994. At Columbia he was supported by a
Fulbright scholarship.
In 1994 he joined the Electrical Engineering-Systems Department at the University of Southern California (USC), Los Angeles, where he is currently aProfessor. He currently serves as Associate Chair of
EE-Systems and as was previously a director of the Signal and Image Processing
Institute at USC. His research interests are in the areas of multimedia compression, communications and signal analysis. His recent work is focusing on distributed compression, multiview coding, error tolerant compression, waveletbased signal analysis and information representation in wireless sensor networks. His work at USC has been or is being funded by agencies such as NSF,
NASA, DOE, as well as a number of companies. Over 25 Ph.D. students havecompleted their Ph.D. thesis work under his supervision at USC, and his work
has led to over 250 publications in international conferences and journals.
Dr. Ortega has been Chair of the Image and Multidimensional Signal Processing (IMDSP) technical committee and a member of the Board of Governorsof the IEEE Signal Processing Society (2002). He has been technical program
co-chair of ICIP 2008, MMSP 1998 and ICME 2002. He has been an Associate Editor for the IEEE TRANSACTIONS ON IMAGE PROCESSING, the IEEE
Signal Processing Letters and the EURASIP Journal on Advances in Signal
Processing. He has received the NSF CAREER award, the 1997 IEEE Communications Society Leonard G. Abraham Prize Paper Award, the IEEE Signal
Processing Society 1999 Magazine Award, and the 2006 EURASIP Journal ofAdvances in Signal Processing Best Paper Award. He is a Fellow of the IEEEand a member of ACM.

Ngai-Man Cheung (M’08) received the Ph.D.
degree from the University of Southern California(USC), Los Angeles, in 2008.
He is currently a postdoctoral researcher with theInformation Systems Laboratory, Stanford University, Stanford, CA. He was a research associate with
Hong Kong University of Science and Technology(HKUST) from 2008 to 2009. His research interests
are multimedia signal processing and compression.
Dr. Cheung has received paper awards from the
EURASIP Journal of Advances in Signal Processing,IEEE International Workshop on Multimedia Signal Processing (MMSP) 2007,
IS&T/SPIE VCIP 2008, and the USC Department of Electrical Engineering.