MULTIMEDIA
`SYSTEMS
`AND TECHNIQUES
`
`edited by
`
`Borko Furht
`
`Amazon EX-1026
`
`Amazon v. Audio Pod
`US Patent 10,805,111
`
`! ef providers
`
`Network
`interface
`
`Audio Subsystem
`
`(NTSC, PAL)
`
`Digital video
`MPEG)
`
`oe
`
`Analog audio
`(PCM)
`
`-i-
`
`Amazon v. Audio Pod
`US Patent 10,805,111
`Amazon EX-1026
`
`

`

`MULTIMEDIA SYSTEMS
`MULTIMEDIA SYSTEMS
`AND TECHNIQUES
`AND TECHNIQUES
`
`-ii-
`
`

`

`THE KLUWER INTERNATIONAL SERIES
`IN ENGINEERING AND COMPUTER SCIENCE
`
`MULTIMEDIA SYSTEMS AND APPLICATIONS
`
`Consulting Editor
`
`Borko Furht
`Florida Atlantic University
`
`Recently Published Titles:
`
`VIDEO AND IMAGE PROCESSING IN MULTIMEDIA SYSTEMS, by
`Borko Furht, Stephen W. Smoliar, HongJiang Zhang
`ISBN: 0-7923-9604-9
`
`MULTIMErHA S'lSTfMS AD A"LI~TI(JNS
`Advanced Book Series
`
`-iii-
`
`

`

`MULTIMEDIA SYSTEMS
`AND TECHNIQUES
`
`edited by
`
`Borko Furbt
`Florida Atlantic University
`
`~. "
`
`KLUWER ACADEMIC PUBLISHERS
`Boston / Dordrecht / London
`
`-iv-
`
`

`

`Distributors for North America:
`Kluwer Academic Publishers
`101 Philip Drive
`Assinippi Park
`Norwell, Massachusetts 02061 USA
`
`Distributors for all other countries:
`Kluwer Academic Publishers Group
`Distribution Centre
`Post Office Box 322
`3300 AH Dordrecht, THE NETHERLANDS
`
`Library of Congress Cataloging-in-Publication Data
`
`A C.I.P. Catalogue record for this book is available
`from the Library of Congress.
`
`ISBN-13: 978-1-4612-8577-9
`DOl: 10.1007/978-1-4613-1341-0
`
`e-ISBN-13: 978-1-4613-1341-0
`
`Copyright ~ 1996 by Kluwer Academic Publishers
`Softcover reprint ofthe hardcover 1st edition 1996
`
`All rights reserved. No part of this publication may be reproduced, stored in
`a retrieval system or transmitted in any form or by any means, mechanical,
`photo-copying, recording, or otherwise, without the prior written permission of
`the publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park,
`Norwell, Massachusetts 02061
`
`Printed on acid-free paper.
`
`-v-
`
`

`

`vi
`
`MULTIMEDIA SYSTEMS AND TECHNIQUES
`
`Applications and New Technologies
`4
`Conclusion
`5
`REFERENCES
`
`107
`117
`118
`
`4 MULTIMEDIA STORAGE SYSTEMS
`123
`Harrick M. Vin and P. Venkat Rangan
`123
`Introduction
`1
`2 Multimedia Storage Servers
`125
`3 Managing the Storage Space Requirement of Digital Multimedia126
`Efficient Retrieval of Multimedia Objects
`132
`4
`Commercial Video Servers
`140
`5
`Concluding Remarks
`141
`6
`142
`REFERENCES
`
`5 MULTIMEDIA NETWORKS
`Barko Furht and Hari Kalva
`Introduction
`1
`Traditional Networks and Multimedia
`2
`Asynchronous Transfer Mode
`3
`Summary of Network Characteristics
`4
`Comparison of Switching Technologies for Multimedia Com-
`5
`munications
`Information Superhighways
`Conclusion
`
`6
`7
`
`145
`145
`149
`156
`165
`
`166
`167
`171
`
`6 MULTIMEDIA SYNCHRONIZATION
`177
`B. Prabhakaran
`177
`Introduction
`1
`2
`181
`Language Based Synchronization Model
`185
`Petri Nets Based Models
`3
`Fuzzy Synchronization Models
`197
`4
`200
`Content-based Inter-media Synchronization
`5
`204
`6 Multimedia Synchronization and Database Aspects
`206
`7 Multimedia Synchronization and Object Retrieval Schedules
`8 Multimedia Synchronization and Communication Requirements 209
`213
`Summary and Conclusion
`9
`
`

`

`Contents
`
`REFERENCES
`
`7
`
`8
`
`INFOSCOPES: MULTIMEDIA INFORMATION
`SYSTEMS
`Ramesh Jain
`1
`Introduction
`2
`Information and Data
`3 Operations in InfoScopes
`4
`InfoScope Architecture
`5 Knowledge organization
`6
`Interfaces
`Example Systems
`7
`Conclusion and Future Research
`8
`REFERENCES
`
`SCHEDULING IN MULTIMEDIA SYSTEMS
`A. L. Narasimha Reddy
`1
`Introduction
`:2
`Data Organization
`3
`Disk Scheduling
`4
`Network Scheduling
`5 General Discussion
`REFERENCES
`
`9 VIDEO INDEXING AND RETRIEVAL
`Stephen W. Smoliar and HongJiang Zhang
`1
`Introduction
`2
`Parsing
`3
`Representation and Classification
`4
`Indexing and Retrieval
`5
`Interactive Tools
`6
`Conclusion
`
`INDEX
`
`vii
`
`214
`
`217
`217
`220
`225
`228
`234
`237
`239
`250
`251
`
`255
`255
`258
`259
`275
`289
`290
`
`293
`293
`296
`307
`311
`315
`318
`
`323
`
`

`

`6
`
`MULTIMEDIA
`SYNCHRONIZATION
`B. Prabhakaran
`
`Department of Computer Science fj Engineering,
`Indian Institute of Technology, Madras. India
`
`1
`
`INTRODUCTION
`
`Multimedia information comprises of different media streams such as text, im(cid:173)
`ages, audio, and video. The presentation of multimedia information to the
`user involves spatial organization, temporal organization. delivery of the com(cid:173)
`ponents composing the multimedia objects, and allowing the user to interact
`with the presentation sequence. The presentation of multimedia information
`can be either live or orchestrated. In live presentation, multimedia objects are
`acquired in real-time from devices such as video camera and microphone. In
`orchestrated presentation. the multimedia objects are typically acquired from
`stored databases. The presentation of objects in the various media streams have
`to be ordered in time. Multimedia synchronization refers to the task of coordi(cid:173)
`nating this ordering of presentation of various objects in the time domain. In
`a live multimedia presentation, the ordering of objects in the time domain are
`implied and are dynamically formulated. In an orchestrated presentation. this
`ordering is explicitly formulated and stored along with the multimedia objects.
`
`Synchronization can be applied to concurrent or sequential presentation of ob(cid:173)
`jects in the various media streams composing the multimedia presentation.
`Figure 1 shows an example of synchronization during sequential and concur(cid:173)
`rent presentation. Consider the concurrent presentation of audio and images
`shown in Figure 1. Presentation of the objects in the individual media streams,
`audio and image, is sequential. The points of synchronization of the presenta(cid:173)
`tion corresponds to the change of an image and the beginning of a new audio
`clipping. Multimedia presentation applications must ensure that these points
`of synchronization are preserved.
`
`

`

`178
`
`CHAPTER 6
`
`10
`
`11
`
`12
`
`(I) SeQuentiel Syncl'lronlzalion
`
`10
`
`11
`
`12
`
`(II) COncurrenl Syncl'lronizaUon
`
`In
`
`In
`
`Figure 1 Synchronization in multimedia presentation.
`
`The points of synchronization in a multimedia presentation can be modified by
`the user going through the presentation. In an orchestrated presentation, for
`example, a user may interact by giving inputs such as skip event(s), reverse
`presentation , navigate in time, scale the speed of presentation, scale the spatial
`requirements. handle spatial clash, freeze and restart of a presentation. User
`inputs such as skip, reverse presentation and navigate time modify the sequence
`of objects that are being presented. User inputs such as scaling the speed of
`presentation modify the presentation duration of the objects. User inputs such
`as handling spatial clash on the display screen make the corresponding media
`stream active or passive depending on whether the window is in the foreground
`or background. Similarly, while the freeze user input suspends the activities
`on all streams, restart input resumes the activities on all streams.
`In the
`presence of non-sequential storage of multimedia objects, data compression,
`data distribution, and randQm communication delays, supporting these user
`operations can be very difficult.
`
`1.1 Modeling Temporal Relations
`
`The points of synchronization in a multimedia presentation are described by
`the corresponding temporal information . Temporal information can be rep(cid:173)
`resented by time points or time instants and time intervals. Time instants
`are characterized by specifications such as AT.9.00 AM and time intervals by
`specifications such as 1 hour or 9.00 AM to 5. 00 PM. Time interval is defined
`by two time instants: the start and the end. A time instant is a zero-length
`
`

`

`Multimedia Synchronization
`
`179
`
`moment in time whereas a time interval has a duration associated with it. A
`time interval can be defined as an ordered pair of instants with the first instant
`less than the second [5]. Time intervals can be formally defined as follows [13].
`Let [S,~] be a partially ordered set, and let a, b be any two elements of S such
`that a ~ b. The set {xla ~ x ~ b} is called an interval of S denoted by [a,b].
`Temporal relations can then be defined based on the start and end time instants
`of the involved intervals. Given any two time intervals, there are thirteen ways
`in which they can relate in time [5], whether they overlap, meet, precede, etc.
`Figure 2 shows a timeline representation of the temporal relations. Six of the
`thirteen relations are inverse of the seven relations that are shown in Figure 2.
`
`(I) a betore b
`
`(i) a meets b
`
`11
`a
`
`11
`
`a
`
`12
`
`b
`
`12
`
`(IN) a overlaps b
`
`t1
`
`b
`
`a
`
`eIV) b rushes a
`
`(v) a slarts b
`
`b
`
`11
`
`(VI)bckJnnga
`
`\1
`
`b
`t2
`
`(VIi) a equats b
`
`a
`
`b
`
`11
`
`Figure 2 Temporal relations between two events.
`
`M\lltimedia presentation can be modeled by temporal intervals with the time
`and duration of presentation of the multimedia objects being represented by
`individual time intervals. The time dependencies of the multimedia objects
`composing the presentation are brought out by their temporal relationships. In
`some cases, it may not be possible to formulate precise temporal relationships
`among the multimedia objects. However, relative temporal relationships can be
`specified among the objects to be presented. This mode of fuzzy representation
`or the relative temporal specification is to be contrasted with the absolute
`specification. As an example, the specification present object A at time T is an
`absolute temporal relation. Whereas present object A with (or after) object B is
`
`

`

`180
`
`CHAPTER 6
`
`a relative temporal specification. Consider a scenario where n objects are to be
`presented and the exact temporal requirements of the composing objects are not
`available. Using fuzzy temporal specification, one can formulate a relationship
`saying that all the n - 1 objects are to be presented during the presentation of
`the object that has the longest duration.
`
`1.2 Synchronization Specification
`Methodologies
`
`Multimedia synchronization specification in terms of the temporal relationships
`can be absolute or relative. Even in the case of absolute temporal relations,
`the time deadlines are soft. For example, nothing untoward happens if the
`object is not available for presentation at the scheduled time instant. Method(cid:173)
`ologies used for synchronization specification should capture all the temporal
`interdependencies of the objects composing the multimedia presentation and at
`the same time should have the flexibility for indicating soft deadlines. A syn(cid:173)
`chronization methodology should also allow the user to modify the sequence
`of presentation dynamically. The temporal relationships in orchestrated mul(cid:173)
`timedia presentations have to be captured in the form of a database and a
`specification methodology must be suitable for developing such a database.
`
`One approach to the specification of multimedia synchronization is to use par(cid:173)
`allellanguage paradigms that can be parsed during presentation to the user.
`Here, the presentation of individual media streams are assigned to executable
`processes and these processes synchronize via inherent language constructs.
`Language based schemes for multimedia synchronization have been proposed
`in [9, 11, 14]. Another approach is to use graphical models. Graphical mod(cid:173)
`els have the additional advantage of providing a visual representation of the
`synchronization specification. Graphical models for synchronization specifica(cid:173)
`tion have been based on Petri nets [1] and Time-flow Graphs [19]. Another
`new approach to synchronization specification has been proposed in [21]. This
`proposal, called the content-based synchronization, is based on the semantic
`structure of the objects composing the multimedia presentation.
`
`In this chapter, we discuss the various method(cid:173)
`Outline of this Chapter:
`ologies used for describing multimedia synchronization in an orchestrated mul(cid:173)
`timedia presentation. In Section 2, we examine language based models for
`multimedia synchronization. In Sections 3 and 4, we discuss graphical mod(cid:173)
`els based on Petri nets and Time-flow Graphs. In Section 5, we study the
`content-based approach for synchronization specification. After discussing the
`
`

`

`A1ultimedia Synchronization
`
`181
`
`synchronization methodologies. we present the database storage aspects ofmul(cid:173)
`timedia synchronization in Section 6. We then consider distributed orchestrated
`multimedia presentations where objects have to be retrieved over a computer
`network before their delivery to the user. In Sections 7 and 8. we describe how
`a multimedia synchronization specification can be applied to derive schedules
`for object retrieval over computer networks and to derive the communication
`requirements of an orchestrated presentation.
`
`2 LANGUAGE BASED
`SYNCHRONIZATION MODEL
`
`Language based synchronization models view multimedia synchronization in
`the context of operating systems and concurrent programming languages. Based
`on an object model for a multimedia presentation. the synchronization charac(cid:173)
`teristics of the presentation are described using concurrent programming lan(cid:173)
`guages. As discussed in [9], the basic synchronization characteristics of a multi(cid:173)
`media presentation as viewed from the point of view of programming languages
`are:
`
`•
`
`•
`
`•
`
`•
`
`•
`
`number of multimedia objects involved
`
`blocking behavior of individual multimedia objects while waiting for syn(cid:173)
`chronization
`
`allowing more than two multimedia objects combine many synchronization
`events
`
`ordering of synchronization events
`
`coverage of real-time aspects
`
`The above characteristics influence the basic features required from a concur(cid:173)
`rent programming language in order to describe a multimedia presentation. For
`example. the number of involved objects describes the communication among
`the multimedia objects that should be described by the language. Blocking
`behavior of a multimedia object describes the nature of synchronization mech(cid:173)
`anism that is required viz. blocked·mode. non-blocked mode and restricted
`blocked mode. The non-blocked mode would never force synchronization but
`allows objects to exchange messages at specified states of execution. Blocked
`
`

`

`182
`
`CHAPTER 6
`
`mode forces an object to wait till the cooperating object(s) reach the specified
`state(s). Restricted blocked mode is a concept introduced in [9]. In the context
`of multimedia presentation, restricted blocking allows an activity to be repeated
`by an object till the synchronization is achieved with the cooperating object(s).
`The activity can be presenting the last displayed image for an image object or
`playing out a pleasant music in the case of an audio object. Restricted blocking
`basically allows the multimedia presentation to be carried out in a more user
`friendly manner.
`
`More than two objects may have to be allowed to combine many synchronizing
`events. This is especially true in presentations where many streams of infor(cid:173)
`mation are presented concurrently. A programming language should be able
`to describe this scenario. The ordering of synchronization events become nec(cid:173)
`essary when two or more synchronization events are combined by some kind
`of a relation. The ordering can be pre-defined, prioritized or based on certain
`conditions. As multimedia presentations deal with data streams conveying in(cid:173)
`formation to be passed in real-time, synchronization of the events composing
`the presentation incorporates real-time features.
`
`2.1 Enhancements For Concurrent
`Programming Languages
`
`Following the above discussions, additional features are necessary in a concur(cid:173)
`rent programming language for describing real-time features and for describing
`restricted blocking. In this section, we discuss these enhancements for a con(cid:173)
`current programming language suggested in [9].
`
`In a multimedia presentation,
`Real-Time Synchronization Semantics:
`events have to be synchronized at specified times or within a time interval. As
`an example, video images and the corresponding audio have to be synchronized
`within 150 milliseconds. In [9], following terms of multimedia relations are
`introduced for a concurrent programming language.
`
`•
`
`•
`
`Timemin is the minimum acceptable delay between two synchronization
`events. The usual parameter is "0".
`
`Timeave is the ideal delay between synchronization events i.e., the syn(cid:173)
`chronization should be as close to timeave as possible, though it might
`occur before or after timeave. The usual timeave parameter is also "0".
`
`

`

`Multimedia Synchronization
`
`183
`
`Expression
`timemin( .... )
`
`timeave( .... )
`timemax( .... )
`timemin( .... ) AND
`timemax( .... )
`timemin( .... ) AND
`timeave( .... )
`timemax( .... ) AND
`timeave( .... )
`timemin( .... ) AND
`timemax( .... ) AND
`timeave( .... )
`
`Meaning
`Minimum acceptable delay
`between two synchronizing events.
`Ideal delay.
`Maximum acceptable delay.
`Synchronization:
`between timemin and timemax.
`Synchronization: closer to
`timeave, never before timemin.
`Synchronization : closer to
`timeave, never after timemax.
`Synchronization : closer to
`timeave, between timemin and
`timemax.
`
`Table 1 Semantics For Basic Real-Time Synchronization.
`
`•
`
`Timemax is the time-out value and refers to the maximum acceptable
`delay between synchronization events. The parameter for timemax vary
`depending on the type of media objects involved in the synchronization.
`
`The proposal in [9] also allows the above specified temporal operands to be
`combined. The operands time min and timemax are not commutative, thereby
`allowing specification of a different delay depending on which multimedia ob(cid:173)
`ject executes its synchronizing operation first. The temporal operands can be
`combined using logical operator AND. Table 1 describes the possible temporal
`expressions and their associated meaning.
`
`Restricted Blocking Semantics :
`Figure 3 shows a possible multime(cid:173)
`dia presentation scenario with restricted blocking. Here, activity A presents a
`full motion video while the activity B presents the corresponding audio. Ac(cid:173)
`tivity A, if it first waits for synchronization with activity B, keeps displaying
`the last presented image. In a similar manner, activity B, if it first waits for
`synchroniz'ation with activity A, plays out pleasant music. The proposal in [9]
`describes a WHILE-WAITING clause for specifying restricted blocking. The
`program segment in Table 2 shows the synchronization between the activities
`A and B (shown in Figure 3) with restricted blocking and real-time restrictions.
`The synchronization delay between the two objects should be between 1 second
`of the audio object ahead of the video object and 2 seconds of the video object
`
`

`

`184
`
`CHAPTER 6
`
`TIme
`
`Activity A
`
`Activity B
`
`1
`Wail For Synch. ;
`Display ~l Image
`t
`... -
`Proceed Funher
`,
`
`- - - -
`
`~
`
`-
`
`- Ready ForSynch.
`
`Proceed Further
`
`j
`
`I
`t
`
`•
`
`j
`
`Figure 3 Restricted blocking in multimedia presentation.
`
`program of Object-A :
`- video
`- from Source A
`display (Object-A)
`SYNCHRONIZE WITH
`ObjecLB AT end
`MODE restricted_blocking
`WHILE_WAITING
`display( lastimage)
`TIMEMIN 0
`TIMEMAX Is
`TIMEAVE 0
`EXCEPTION display(lasUmage)
`
`program of Object_B :
`_. audio
`- from Source B
`display (Object_B)
`SYNCHRONIZE WITH
`Object-A AT end
`MODE restricted_blocking
`WHILE-WAITING
`play (music)
`TIMEMIN 0
`TIMEMAX 2s
`TIMEAVE 0
`EXCEPTION play(music)
`
`Table 2 Program With Restricted Blocking &. Time Constraints
`
`ahead ofthe image object. However. the target is no delay (with timemin being
`0).
`
`Summary: Language based specification of the multimedia synchronization
`characteristics uses concurrent programming language features. Enhancements
`
`

`

`Multimedia Synchronization
`
`185
`
`to the facilities offered by the programming languages are needed for describing
`certain features of multimedia presentation such as real-time specification and
`restricted blocking. However, language based specifications can become com(cid:173)
`plex when a multimedia presentation involves multiple concurrent activities
`that synchronize at arbitrary time instants. Also, modifying the presentation
`characteristics might even involve rewriting the program based specification.
`
`3 PETRI NETS BASED MODELS
`
`Petri Nets, as a modeling tool, have the ability to describe real-time process
`requirements as well as inter process timing relationships, as required for multi(cid:173)
`media presentations [1, 2]. A Petri net is a bipartite graph consisting of 'place'
`nodes and 'transition' nodes. Places, represented by circles, are used to rep(cid:173)
`resent conditions; transitions, drawn as bars, are used to represent events. A
`Petri net structure P is a triple.
`
`P = { T, P, A } where
`
`T = { tl, t 2, ... } represents a set of transitions (bars)
`p = { PI, P2, ... } represents a set of places (circles)
`I, I = { 1, 2, ... } representing set of inte(cid:173)
`A : { T * P } U { P * T } -
`gers
`
`The arcs represented by A describe the pre- and post-relations for places and
`transitions. The set of places that are incident on a transition t is termed the
`input places of the transition. The set of places that follow a transition t is
`termed the output places of the transition. A Marked Petri Net is one in which
`a set of 'tokens' are assigned to the places of the net. Tokens, represented by
`small dots inside the places, are used to define the execution of the Petri net,
`and their number and position change during execution. The marking (M) of a
`Petri net is a function from the set of places P to the set of nonnegative integers
`I, M : P -+ I. A marking is generally written as a vector (ml, m2, .... , m n ) in
`which mi = M(p;). Each integer in a marking indicates the number of tokens
`residing in the corresponding place (say Pi)'
`
`Execution of a Petri net implies firing of a transition. In a Marked Petri net,
`a transition t is enabled for firing iff each of its input place contain atleast one
`
`

`

`186
`
`CHAPTER 6
`
`token,i.e.,
`'t/(p E InputPlace(t» : M(p) ~ 1.
`Firing t consists of removing one token from each of its input place and adding
`one token to each of its output place. and this operation defines a new marking.
`An execution of a Petri net is described by a sequence of markings, beginning
`with an initial marking Mo and ending in some final marking Mf. Marking of
`a Petri net defines the state of the net. During the execution, Petri net moves
`from a marked state Mi to another state Mj by firing any transition t that are
`enabled in the state Mi.
`
`For the purpose of modeling time-driven systems, the notion of time was in(cid:173)
`troduced in Petri nets, calling them as Timed Petri Nets (TPN) [4]. In TPN
`models. the basic Petri net model is augmented by attaching an execution time
`variable to each node in the net. The node in the Petri net can be either the
`place or the transition. In a marked TPN. a set of tokens are assigned to places.
`A TPN N is defined as,
`
`N = { T, P, A, D, M } where
`
`M : P ---> I represents marking M which assigns tokens (dots) to each place in
`the net
`
`D : P -+ R represents durations as a mapping from the set of places to the
`set of real numbers
`
`other descriptions T, P. A are same as that of the normal Petri net.
`
`A transition is enabled for execution iff each of its input place contain atleast
`one token. The firing of a transition causes a token to be held in a locked state
`for a specified time interval in the output place of the transition, if the time
`intervals are assigned to places. If time intervals are assigned to transitions, the
`token is in a transition state for the assigned duration. The execution of a Petri
`net process might have to be interrupted in order to carry out another higher
`priority activity. Pre-emption of the on-going execution of a Petri net process
`can be modeled using escape arcs to interrupt the execution of a process [6]. In
`this section, we examine Petri net based models for the purpose of describing
`the synchronization characteristics of the multimedia components.
`
`

`

`Multimedia Synchronization
`
`187
`
`3.1 Hypertext Models Using Timed Petri
`Nets
`
`TPN concept has been used to specify the browsing semantics in the Trellis Hy(cid:173)
`pertext System [7, 10]. This Petri net based Hypertext model allows browsing
`events to be initiated by the reader or by the document itself. A synchronous
`hypertext H is defined as a 7-tuple H = < N, Mo, C, W, B, PI, Pd > in which
`
`N is a timed Petri net structure
`
`M 0
`
`is an initial state (or initial marking) for N
`
`C is a set of document contents
`
`W is a set of windows
`
`B is a set of buttons
`
`PI is a logical projection for the document
`
`Pd is a display projection for the document.
`
`In the above definition, the structure of the timed Petri net specifies the struc(cid:173)
`ture of the hypertext document. A marking in the hypertext hence represents
`the possible paths through a hyperdocument from the browsing point it rep(cid:173)
`resents. The initial marking of a synchronous hypertext therefore describes a
`particular browsing pattern. The definition also includes several sets of com(cid:173)
`ponents (contents, windows, and buttons) to be presented to the user going
`through the document. Two collections of mappings or projections are also
`defined: one from the Petri net to the user components and another from the
`user components to the display mechanism.
`
`The content elements from the set C can be text, graphics, still image, motion
`video, audio information or another hypertext. A button is an action selected
`from the set B. A window is defined as a logically distinct locus of information
`and is selected from the set W. PI, the logical projection, provides a mapping
`from the components of a Petri net (place and transitions) to the human(cid:173)
`consumable portions of a hypertext (contents, windows and buttons). A content
`element from the set C and a window element for the abstract display of the
`content from the set W, are mapped to each place in the Petri net. A logical
`button from the set B is mapped to each transition in the Petri net. Pd,
`the display projection, provides a mapping from the logical components of
`
`

`

`188
`
`CHAPTER 6
`
`the hypertext to the tangible representations, such as screen layouts, sound
`generation, video, etc. The layout of the windows and the way text information
`and buttons are displayed, is determined by Pd.
`
`Execution Rules For Trellis Hypertext
`
`The net execution rule in Trellis hypertext is a hybrid one, with a combination
`of a singleton transition firing rule (representing the actions of the hyperdocu(cid:173)
`ment reader) and a maximal transition firing rule (to allow simultaneous auto(cid:173)
`matic or system-generated events). The execution rule works as follows.
`
`• All the enabled transitions are identified. The enabled transitions set con(cid:173)
`sists of both timed out ones (i.e., have been enabled for their maximum
`latency) and active ones (i.e., have not timed out).
`
`• One transition from the group of active ones and a maximal subset from
`the group of timed-out transitions will be chosen for firing.
`
`This two step identification of transitions to be fired is basically for modeling
`both reader and timer based activity in the hypertext. A reader may select a
`button (fire a transition) during the same time slot in which several system(cid:173)
`generated events occur. In this case, the Trellis model gives priority to the
`reader's action by choosing the reader-fired transition first. When a transition
`is fired, a token is removed from each of its input place and a token is added
`to each of its output place.
`
`The implication of the firing rules is such that the document content elements
`are displayed as soon as tokens arrive in places. The display is maintained for a
`particular time interval before the next set of outgoing transitions are enabled.
`After a transition t becomes enabled. its logical button is made visible on the
`screen after a specified period of time. If the button remains enabled without
`being selected by the reader, the transition t will fire automatically at its point
`of maximum latency. The way the hypertext Petri net is structured along with
`its timings describes the browsing actions that can be carried out. In effect,
`windows displaying document contents can be created and destroyed without
`explicit reader actions. control buttons can appear and disappear after periods
`of inactivity, and at the same time user interactive applications can be created
`with a set of active nodes. Petri nets being a concurrent modeling tool, multiple
`tokens are allowed to exist in the net. These tokens can be used to effect the
`
`

`

`Multimedia Synchronization
`
`189
`
`action of multiple users browsing one document or to represent multiple content
`elements being visible together.
`
`Trellis Hypertext: An Example
`
`Figure 4 Guided tour using trellis hypertext.
`
`We shall consider the guided tour example discussed in [7]. In a guided tour,
`a set of related display windows is created by an author. All the windows in
`a set are displayed concurrently. A tour is constructed by linking such sets
`to form a directed graph. The graph can be cyclic as well. From anyone set
`of display windows, there may be several alternative paths. Figure 4 shows
`a representation of guided tour using the Trellis hypertext. Here, the set of
`windows to be displayed at any instant of time is described by a Petri net
`place. A place is connected by a transition to as many places as there are sets
`of windows to be displayed. A token is placed in the place(s) representing the
`first set of windows to be displayed. The actual path of browsing is determined
`by the user going through the information. For example, when the token is in
`pl, the information contents associated with pl are displayed and the buttons
`for the transitions t1 and t2 are selectable by the user.
`
`Summary:
`The synchronous hypertext models both the logically linked
`structure of a hyperdocument and a timed browsing semantics in which the
`reader can influence the browsing pattern. The Trellis Hypertext model uses
`Petri net structure for representing user interaction with a database (basically
`for browsing actions). However, in tht> Trellis model. the user's inputs such as
`
`

`

`190
`
`CHAPTER 6
`
`freeze and restart actions, scaling the speed of presentation (fast forward or
`slow motion playout) and scaling the spatial requirements cannot be modeled.
`Another aspect in the Trellis model is that the user can interact with the
`hypertext only when the application allows him to do so (i.e., when the buttons
`can be selected by the user). Random user behavior where one can possibly
`initiate operations such as skip or reverse presentation at any point in time,
`are not considered in Trellis hypertext.
`
`3.2 The Object Composition Petri Nets
`
`The Object Composition Petri Net (OCPN) model has been proposed in [8,
`12] for describing multimedia synchronization. The OCPN is an augmented
`Timed Petri' Nets (TPN) model with values of time represented as durations
`and resource utilization being associated with each place in the net. An OCPN
`is defined as
`
`COCPN = { T, P, A, D, R. M } where
`
`R : P --+ { rl, r2, ... } represents the mapping from set of places to a set of
`resources.
`
`other descriptions being same as that in the TPN model.
`
`The execution of the OCPN is similar to that of TPNs where the transition
`firing is assumed to occur instantaneously and the places are assumed to have
`states. The firing rules for the OCPN are as follows :
`
`1. A transition tj fires immediately when each of its input place contain an
`unlocked token.
`
`2. Upon firing the transition ti. a token is removed from each of its input
`place and a token is added to each of its output place.
`
`3. A place Pi remains in an active state for a specified duration Tj associated
`with the place, after receiving a token. The token is considered to be in a
`locked state for this duration. After the duration Ti, the place Pi becomes
`inactive and the token becomes unlocked.
`
`

`

`Multimedia Synchronization
`
`191
`
`It has been shown in [8, 12], that the OCPN can represent all the possible
`thirteen different temporal relationships between any two object presentation.
`T