Abstract
A schedule for a multimedia document indicates when document events should occur. We describe a two-phase algorithm that automatically produces schedules for interactive multimedia documents, which can contain both predictable behavior (such as audio and video) and unpredictable behavior (such as user interaction and programs with unpredictable execution times). The first phase of the algorithm, called the compiletime scheduler, preprocesses high-level temporal specifications before the document is presented and creates as much of the schedule as possible. Our compiletime scheduler is conceptually similar to TEX's spatial layout algorithm in that it permits time to be stretched or shrunk between events inside media segments to arrive at an “optimal” presentation for a document. The second phase of the algorithm, called the runtime scheduler, resolves the presentation of media segments that depend upon unpredictable behavior.
Similar content being viewed by others
References
Anderson DP (1990) Meta-scheduling for distributed continuous media. University of California at Berkeley, EECS Department, Technical Report No. UCB/CSD 90/599
Bier E (1992) EmbeddedButtons: supporting buttons in documents. ACM Trans Info Syst 10(4):381–407
Blakowski G, Hubel J, Langrehr U (1992) Tool support for the synchronization and presentation of distributed multimedia. Comput Commun 15:611–618
Buchanan MC (1993) Specifying temporal behavior in multimedia documents. PhD dissertation, University of Washington, Seattle, WA (in press)
Buchanan MC, Zellweger PT (1992) Specifying temporal behavior in hypermedia documents. In: Lucarella D, Nanard J, Nanard M, Paolini P (eds) Proc ACM Conference on Hypertext, ACM Press, New York, 262–271
Buchanan MC, Zellweger PT (1993) Automatic temporal layout mechanisms, Proc ACM Multimedia'93 (in press)
Buchanan MC, Zellweger PT, Pier K (1993) Multimedia documents as user interfaces (video)
Bulterman DCA, van Rossum G, van Liere R (1991) A structure for transportable, dynamic multimedia documents. Proc 1991 Summer USENIX Conf, pp 137–155
Cormen TH, Leiserson CE, Rivest RL (1990) Introduction to Algorithms. MIT Press, Cambridge, Mass, and McGraw-Hill, New York
Dechter R, Meiri I, Pearl J (1989) Temporal constraint networks. Proc 1st Int Conf on Principles of Knowledge Representation and Reasoning
Drapeau GD, Greenfield H (1991) MAEstro — a distributed multimedia authoring environment. Proc 1991 Summer USENIX Conf, pp 315–328
Gibbs S (1991) Composite multimedia and active objects. Proc OOPSLA'91, pp 97–112
Goldfarb CF (1991) HyTime: A standard for structured hypermedia exchange. IEEE Computer 24:81–84
Hamakawa R, Sakagami H, Rekimoto J (1992) Audio and video extensions to graphical user interface toolkits. Proc 3rd Int Workshop on Network and Operating System Support for Digital Audio and Video, San Diego, pp 356–361
Hillier FS, Lieberman GJ (1974) Operations Research. Holden-Day, San Francisco
Jaffar J, Michaylov S, Stuckey PJ, Yap RHC (1992) The CLP(R) language and system. ACM Trans Program Lang Syst 14:339–395
Jeffay K, Stanat DF, Martel CU (1991) On non-pre-emptive scheduling of periodic and sporadic tasks. Proc 12th IEEE Real-Time Systems Symposium, pp 129–139
Kim W, Kenchammana-Hosekote D, Lim EP, Srivastava J (1992) Synchronization Relation Tree: a model for temporal synchronization in multimedia presentations. University of Minnesota Computer Science Dept. Technical Report No. 92-42
Knuth DE, Plass MF (1981) Breaking paragraphs into lines. Software-Practice and Experience 11:1119–1184
Lawler E (1976) Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York Chicago San Francisco
Little TDC, Ghafoor A (1990) Network considerations for distributed multimedia object composition and communication. IEEE Network 4:32–49
MacroMind, Inc. (1989) MacroMind Director: Overview Manual, MacroMind, Inc. San Francisco, CA
Nelson G (1985) Juno, a constraint-based graphics system. Proc SIG-GRAPH'85, pp 235–243
Nicolaou C (1990) An architecture for real-time multimedia communication systems. IEEE J Selected Areas Commun 8:391–400
Northcutt JD, Kuerner EM (1992) System support for time-critical applications. In: Herrtwich RG (ed) Network and operating system support for digital audio and video. Lecture Notes in Computer Science No. 614, Springer, Berlin Heidelberg New York, pp 242–254
Ogawa R, Harada H, Kameko A (1990) Scenario-based hypermedia: a model and a system. In: Rizk A, Streitz N, Andre J (eds) Hypertext: concepts, systems, and applications, Cambridge University Press, Cambridge, pp 38–51
Poole L (1991) QuickTime in motion, MACWORLD 9:154–159
Rossum van G, Jansen J, Mullender KS, Bulterman DCA (1993) CMIFed: a presentation environment for portable hypermedia documents. Proc ACM Multimedia'93 (in press)
Steinmetz R (1990) Synchronization properties in multimedia systems. IEEE J Selected Areas of Commun 8:401–412
Stotts PD, Furuta R (1990) Temporal hyperprogramming. J Visual Lang Comput 1:237–253
Swinehart DC, Zellweger PT, Beach R, Hagmann R (1986) A structural view of the Cedar programming environment. ACM Trans Program Lang Syst 8:419–490
Zellweger PT, Terry DB, Swinehart DC (1988) An overview of the Etherphone system and its applications. Proc 2nd IEEE Computer Workstation Conf, pp 160–168
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Buchanan, M.C., Zellweger, P.T. Automatically generating consistent schedules for multimedia documents. Multimedia Systems 1, 55–67 (1993). https://doi.org/10.1007/BF01213484
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01213484