An Object Exchange Format (OEF) has been defined to specify MSS by our research group [28]. The underlying structure is a hypergraph structure. In the hypergraph structure, each node represents an MMO, either a composite object or a basic object. Among the nodes, there are a set of hyper-links which connect nodes. Five types of links are currently under our research group's investigation and are described as follows:
The G-Net descriptions of the MDS and the MCS can be specified as follows:
As the hypergraph structure representing MSS in the OEF could be complicated due to its rich set of links, the MSS is transformed into an intermediate model first then into the MDS in order to simplify the transformation. The intermediate model adopted here is based on the CWI Multimedia Interchange Format (CMIF) model [1, 9] augmented by adding a delay attribute to each node in it. The CMIF model is a hierarchically structured model for representing and manipulating multimedia documents. In the tree view of the hierarchy of the CMIF model, each internal node specifies the temporal relation, either parallel or serial, among its children nodes and each leaf node represents a multimedia object. By adding a delay into each node, various temporal relations can be represented in a unified schema as described in the following paragraph. The tree structure allows the employment of recursive algorithms to perform the transformation. However, there is a restriction of the CMIF model that it only provides synchronization between sibling nodes, i.e., nodes of the same parent node. Thus, the temporal links between non-sibling nodes are not processed in the transformation from MSS to IM and stored in a set of links L.
The temporal relations among objects are defined by the links in the MSS.
In the construction of the intermediate model, a temporal node is generated
in the IM for sibling nodes connected by a temporal link in the MSS.
This temporal node will become a child of the node in the IM corresponding to
the node to which those sibling nodes are attached in the MSS.
There are two categories of temporal relations between two objects:
parallel and sequential. The sequential category consists of two temporal
relations which are before and meet, while the parallel category
consists of five temporal relations: co-begin, co-end, equal,
overlap, and during [16].
The synchronization attributes of a temporal link include the temporal
relations and a temporal value, e.g., the gap between the end of an object and
the beginning of the other in relation before. Based on the
synchronization attributes,
a delay attribute can be added to each node connected by the link to specify the
delay , where , of that node.
A special value d, which stands for ``don't care",
for delay , is used for the temporal relation not specified definitely
among the objects.
Three assumptions are made here. One is that the temporal relation between
sibling nodes in the MSS not linked by a temporal link is defined as parallel
with as d. Another is that
the temporal relation among the annotating objects and annotated object is
the parallel relation during, which is a reasonable interpretation. The other is that each object
linked by a reference link should have its own MDS, and consequently MCS, as it
will be presented and/or transmitted only when requested. Therefore, the
referenced objects will not be included in the MDS transformed from the MSS.
However, the information is kept in the MSS and can be brought up when the
objects are referred.
Figure 
illustrates the construction of an intermediate model.
Figure: Construction of the Intermediate Model.
Figure: The insertion of an object in the IM-to-MDS' transformation. The
object is enclosed in a dotted ellipse.
Figure: The temporal relation between two objects and the corresponding structures.
The transformation from IM to MDS is divided into two phases. In the first phase, a temporary G-Net MDS' is transformed recursively from the intermediate model. In the second phase, the temporal links stored in the set L are processed by adding auxiliary places and transitions onto MDS' to complete the construction of the MDS.
When transforming from IM to MDS', two places and one transition are created
to represent each node in the corresponding MDS'.
One place, , is the input place while the other place, , is the
output place of the transition. The input place , which is called the
delay place, represents the delay
of the node, handles temporal links linking non-sibling nodes,
and provides possibly further synchronization.
One type of scenario for more flexible synchronization is
``fuzzy scenarios" [12]. For example, three multimedia objects are specified
to be presented in parallel while the order for presentation is not that
important. With the employment of the value d,
we can formulate a G-Net that describes this scenario.
The modeling for ``fuzzy scenarios" and other synchronization scenarios is
currently under investigation. The output place indicates the object
represented by the node and is called the object place. Therefore, a
unified construction of the MDS' can be achieved.
There are two scenarios of
inserting an object into the schema according to the temporal category of
its parent node and each scenario should be handled differently.
Figure describes both scenarios of parallel insertion and
sequential insertion.
The temporal relations between two objects and the corresponding hypergraph
structure, intermediate model, and MDS' that represent the relations are
depicted in Figure .
The last step in the transformation is to process the non-sibling links stored
in the set L previously. The idea is to make
use of the delay place of each object as well as to
generate auxiliary places and transitions to provide synchronization according
to the temporal attribute of a link.
Table 1 and Figure show the detail of processing a
link from object M1 to M2 .
Figure: The construction of MDS from MDS' by processing non-sibling links in
the MSS.
| Temporal Attribute of Link S S.attribute | Paux.duration tx
| meet | 0
| before,&delta | &delta
| equal | 0
| co-begin | 0
| overlap,&delta | &delta
| during,&delta | &delta
| co-end | &taua - &taub|
| |
|---|
The high-level description of the MSS-to-MDS transformation algorithm is shown in Algorithm 1. The detail of the subroutines is given in Appendix I.
Procedure MSS-to-MDS (OEFMSS, GMDS)
begin
/* Transform the MSS to an intermediate model of tree structure IM.
Links in the MSS are processed except non-sibling temporal links
in the MSS which will be stored in the set of links L. */
MSS-to-IM (OEFMSS, IM, L)
/* Call recursive function to construct a temporary G-net GMDS' from IM
. */
R = root of IM
newplace(P)
GMDS' = IM-to-MDS' (R, P)
/* Process non-sibling temporal links to complete the construction of
G-net GMDS. */
MDS'-to-MDS (GMDS', L, GMDS)
end
Figure: G-Net transformation when applying progressive transmission on object
.
Once the MDS is constructed, we do not have to reconstruct the corresponding MCS from scratch. By defining a transmission vector that specifies which types of objects are to be sent and the parameters of the heuristics, for example, levels of progressive transmission, the MCS can be constructed from MDS by applying the delete operation and heuristics such as progress operation on the corresponding objects. The transmission vector serves as an input parameter of the transformation. The values of the entries in the transmission vector are defined by both the hardware capacity of the machines and transmission specification provided by the user. Another input parameter is the quality of service (QOS) of the communication network which consists of two fields, namely QOS.request and QOS.support. QOS.request is the QOS requested by the user while the QOS.support is the QOS guaranteed by the system. Therefore, given the MDS, the transmission vector, and QOS, the transformation is performed in three steps described as follows.
In the case when progressive transmission is employed for an image
the algorithm progress (short for progressive) will apply. Figure shows the transformation of
this scenario wherein the algorithm progress is applied on object
and a rough object is sent first, followed by its progressive
details.
However, after is sent, the transmission of other objects does not
have to wait for the transmission of the details to be completed. The
details could be transmitted later when the bandwidth of the communication
network is enough.
Procedure MDS-to-MCS(GMDS, TV, QOS, GMCS)
begin
GMCS = GMDS
for each object place P in GMCS
if (TV[MMType(P.object)] == NO)
Delete(GMCS, P.object)
if (QOS.request > QOS.support)
ratio = QOS.request / QOS.support
for each object place P in GMCS
switch (Heuristics)
COMPRESS: Gp = ISP(h1(ratio))
break
PROGRESS: Gp = ISP(h2(ratio))
break
.
replace(P, Gp)
end
For example, we can define QOS.request and QOS.support as follows:
where is the MDS, T is the time specification, and QOS.network is
the QOS parameters provided by the communication network.
For example, a full-colored (24bits/pixel) image of dimension
is requested to be transmitted in over a communication network
with bandwidth 14400 bps.
The size of the image is 1800 Kbits and the bit rate requested is
225 Kbps > 14400 bps. The utilization ratio ratio = 16.
Therefore, we need to apply
heuristics to reduce the quality of the image in order to fit in the
service provided. Two possible heuristics, namely image compression
and progressive transmission, are depicted in Figure .
In general, QOS.request and QOS.support are also vectors, so that the
component-wise comparison will lead to the execution of different heuristics.
Figure: Applying heuristics to the image to be transmitted.