Electronic Proceedings of the
ACM Workshop on Effective Abstractions in Multimedia
November 4, 1995
San Francisco, California

Introductory Slides for Session 4: Presentation -- Temporal Layout

Polle Zellweger
: Xerox PARC; 3333 Coyote Hill Road; Palo Alto, CA 94304, USA; 415/812-4426; zellweger@parc.xerox.com

ACM Copyright Notice

Abstract

An overview of effective abstractions for (automatic) temporal layout in multimedia document authoring and presentation.

The Temporal Layout Problem
Higher-Level Temporal Specification Languages
User-Level Specification Issues
Temporal Layout Algorithms
Algorithm Issues
Lower-Level Temporal Specification Languages
Future Challenges
This Session's Papers
Bibliography

The Temporal Layout Problem

spatial layout = WHERE to place media objects
temporal layout = WHEN to present media objects
want to coordinate the presentation of media objects with one another in time
- static items with no inherent notion of time, but author may wish to impose temporal element
- predictable items with a playback rate that defines a canonical length
- unpredictable items with an unknown duration
  or time of occurrence

Higher-Level Temporal Specification Languages

timelines [Macromind Director, Drapeau 91]
temporal interval relationships [Hamblin 72, Allen 83]
simple parallel-sequential trees
- may have additional constraints (eg sychronization arcs) [Hardman+ 93]
Petri nets
- timed [Stotts/Furuta 90]
- OCPN [Little/Ghafoor 90]
temporal constraint graphs (dags) [Buchanan/Zellweger 93b]
standards
- MHEG
- HyTime

User-Level Specification Issues

expressiveness
- internal points (events)
- unpredictable items (time and/or duration)
- alternate object instantiations [Blakowski+ 92]
- incorporating behavior
usability
- provide for document modularity/composition/reuse
- simple user model desirable
- minimize user measurements/steps
- support document creation & maintenance
=> Automatic Temporal Layout

+ flexibility to facilitate automatic methods
- continuous
- discrete

Temporal Layout Algorithms

all-pairs-shortest-paths [Dechter+ 91]
- provides legal range
- complexity n**3
linear programming
- provides a minimal cost solution under some metric
- theoretically exponential but not in practice
dynamic programming, quadratic programming
temporal glue [Hamakawa/Rekimoto 93]
heuristic search and optimization
runtime
- often based on message-passing

Algorithm Issues

power
complexity/cost
lookahead
debuggability/feedback
- incremental algorithms (Layaida/Keramane 95*)
user controllability
- direct choice among possible document lengths [Kim/Song 95]
- indirect via adjusting costs [Buchanan/Zellweger 93a]

Lower-Level Temporal Specification Languages

model delays, jitter, lip-synch between streams
[Kim/Kenchammana-Hosekote+ 92]
specify media setup times, buffer sizes, etc. (Zhang/Gollapudi 95*)

Future Challenges

appropriate user-level visualization
interplay between spatial and temporal specifications
automatic generation of presentations (eg Feiner/McKeown 91)
better debuggability, controllability
incremental algorithms
temporal equivalents to "center", styles, DTDs
contextualizing mm objects (Souza+ 95*)
rhetoric of multimedia authoring
- hypertext still looking for its rhetoric also

This Session's Papers

Synchronization Aspects of an Hypermedia Presentation Model with Composite Nodes
Guido Lemos de Souza Filho, Luiz Fernando Gomes Soares, Marco Antonio Casanova
PUC-Rio (GLSF, LFGS) and IBM Brazil (MAC), Brazil
On Synchronized Presentation Management in Multimedia Database Systems
Aidong Zhang, Sreenivas Gollapudi
SUNY Buffalo, USA
Maintaining Temporal Consistency of Multimedia Documents
Nabil Layaïda, Chérif Keramane
INRIA Rhône-Alpes, France

< -- Table of Contents

Bibliography

[Allen 83]: Allen J. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11 (Nov. 1983), 832-843.
[Blakowski+ 92]: Blakowski G., Hubel J., and Langrehr U. Tool support for the synchronization and presentation of distributed multimedia. Computer Communications 15, 10 (Dec. 1992), 611-618.
[Buchanan/Zellweger 93a]: Buchanan M.C. and Zellweger P. Automatic temporal layout mechanisms. Proceedings ACM Multimedia'93, Anaheim, CA, August 1993, 341-350.
[Buchanan/Zellweger 93b]: Buchanan M.C. and Zellweger P. Automatically generating consistent schedules for multimedia documents. Multimedia Systems J. 1, 2, (Sept 1993) ACM/Springer-Verlag.
[Dechter+ 91]: Dechter R., Meiri I., and Pearl J. Temporal constraint networks. Artificial Intelligence 49 (1991), 61-95.
[Drapeau 91]: Drapeau G. and Greenfield H. A distributed multimedia authoring environment. Proceedings 1991 Summer USENIX Conference, Nashville, TN, June 1991, 315-328.
[Feiner/McKeown 91]: S.K. Feiner and K.R. McKeown. Automating the generation of coordinated multimedia explanations. IEEE Computer 24(10), 1991, 33-41.
[Hamakawa/Rekimoto 93]: Hamakawa R. and Rekimoto J. Object composition and playback models for handling multimedia data. Proceedings ACM Multimedia'93, Anaheim, CA, August 1993, 273-281.
[Hamblin 72]: Hamblin C.L. Instants and intervals. Proceedings First Conference of the Int'l Society for the Study of Time, 1972, 324-331.
[Hardman+ 93]: Hardman L., van Rossum G., and Bulterman D.C.A. A distributed multimedia authoring environment. Proceedings ACM Multimedia'93, Anaheim, CA, August 1993, 283-289.
[Kim/Kenchammana-Hosekote+ 92]: Kim W., Kenchammana-Hosekote D., Lim E.P., and Srivastava J. Synchronization Relation Tree: A model for temporal synchronization in multimedia presentations. Tech. Rep. 92-42, U. of Minnesota, Computer Science Dept., 1992.
[Kim/Song 95]: Kim M.Y. and Song J. Multimedia documents with elastic time. Proceedings ACM Multimedia'95, San Francisco, CA, November 1995, 143-154.
[Little/Ghafoor 90]: Little T.D.C. and Ghafoor A. Synchronization and storage models for multimedia objects. IEEE J. Selected Areas of Commun. 8, 3 (April 1990), 413-427.
[Stotts/Furuta 90]: Stotts D. and Furuta R. Temporal hyperprogramming. J. Visual Languages and Computing 1, 3 (Sept. 1990), 237-253.