An Object Exchange Format (OEF) has been defined to specify MSS by our research group . 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 . 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" . 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
||equal || 0
||co-begin || 0
||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.