Binary MPEG format for XML (BiM)
MPEG doc#: N7922
Date: January 2006
Authors: Philippe de Cuetos, Claude Seyrat, Cedric Thienot (Expway)
Introduction
ISO/IEC 23001 (MPEG systems technologies) Part 1 [1], also called Binary MPEG format for XML or BiM, provides a standardized set of generic technologies for encoding XML documents. It addresses a broad spectrum of applications and requirements by providing generic methods for transmitting and compressing XML documents.
ISO/IEC 23001-1 provides a specification which (i) gives rules for the preparation of XML documents for efficient transport and storage, and (ii) enables the development of ISO/IEC 23001-1 terminals to receive, decode and assemble possibly partitioned and compressed XML documents.
The binary MPEG format for XML relies on schema knowledge between encoder and decoder in order to reach high compression efficiency, while providing fragmentation mechanisms for ensuring transmission and processing flexibility. The specification also defines means to compile and transmit schema knowledge information to enable the decoding of compressed XML documents without a priori schema knowledge at the receiving terminal.
The binary format for XML described in this specification can be used for encoding MPEG-7 and MPEG-21 descriptions, as specified in ISO/IEC 15938-1 (MPEG-7 Systems)[3] and 21000-16 (MPEG-21 Binary Format)[4], respectively.
BiM main encoding concepts
The basic idea behind BiM encoding of XML documents is to reduce the coding possibilities (and therefore the encoding size) of every document’s component by a contextual decoding combined with the use of the schema information. Practically, BiM structure encoding is based on the XML Schema [2] notion of "content model" from which the encoding format takes most of its source of optimization. BiM is a schema aware encoding scheme, i.e. it is based on the shared knowledge of the schema between the encoder and the decoder.
Additionally, because a schema may change over time, or a decoder may not have a priori knowledge of all schema information, BiM allows the encoder to embed or send new schema information to the decoder. Additional schema information is sent in such a way that it requires minimal CPU of the decoder to be able to process it: schemas are binary encoded and carried in a Schema Update Unit (SUU).
BiM decoding process
Fragment Update Units
The transmission of a BiM document is progressive, i.e., is done through a set of elementary updates called Fragment Update Units (FUU). These FUUs are themselves packed into access units (AU), which is the minimal transport packet to which timing information is associated. Figure 1 shows an example of partitioning an XML document into 3 AUs for encoding and transmission.
Figure 1: Progressive Transmission of a Document
Each FUU is basically composed of a path (FU Context Path) pointing at the node to be added, updated or deleted to the decoder current representation of the document, and a payload (FU Payload) containing the portion of the carried document. Figure 2 shows the result of an “add” command to the decoder current XML tree.
Figure 2: Application of a « add » command
Context Path
During the decoding of a FU Context Path, the element names and types are progressively decoded from the root element down to the context node, in a depth first manner. In this case, at each step of the tree, traversal codes are assigned to each possible element of the path. In addition to this information its position among its sibling elements is decoded. Other information related to element substitution and type-casting are also decoded.
Figure 3: Context Path Decoding
Payload Decoding
In the case of payload decoding, the element names and types are progressively decoded from the first element to the last one in a breadth first manner as shown in Figure 4. No position needs to be decoded and several techniques are used to provide a good compression ratio.
Figure 4: Payload Decoding
The most notable technique to encode structural information relies on Finite State Automaton Decoders (FSAD). Originally inspired by the automata approach used, e.g., in validating XML parsers, FSAD are used in BiM to model the binary syntax of an element. A FSAD is basically a transducer that, by reading some bits from the binary stream, generates XML elements.
Figure 5: Example of a Finite State Automaton Decoder (simplified)
FSADs are built according to the schema definition of a complex type, more specifically according to the structure of its content model (a sequence, choice of elements …) and the cardinality of the content model components (‘minOccurs’ and ‘maxOccurs’ attributes). The decoding is done by the propagation of a token through the automaton; codes are assigned to each possible state transition. Figure 5 shows an example of such FSAD used to decode a sequence of elements A, B and a choice between elements Z or C and D.
Datatype Codecs
Each simple type (string, integer, …) is decoded using basic datatype codecs provided by the specification (IEEE 754, UTF-8, compact integers, VLC integers, lists of values, etc.). New codecs specific to a language's types can be plugged in using the type-codec mapping mechanism defined in the standard
In addition to allowing for the association of specific decoders to each simple data type, BiM gives the possibility to define advanced optimized decoders that can be switched on/off dynamically during the processing of the document, and have parameters that can be dynamically modified. Although each application can use its own advanced optimized codecs, the BiM specification defines by default three such advanced codecs: uniform quantizer, non-uniform quantizer, and zlib.
Conclusion
BiM defines an extensible framework for efficient compression and flexible transmission of XML documents. Good performances in compression are obtained from the sharing of schema knowledge between the encoder and decoder (a priori or by transmission of compiled schema information); processing and transmission flexibility is ensured by various fragmentation mechanisms.
Because BiM is a generic format that applies to any XML vocabulary, it outperforms ad-hoc binary formats that are difficult to evolve and maintain.
References
[1] ISO/IEC 23001-1, Information technology – MPEG system technologies – Part 1: Binary MPEG Format for XML.
[2] XML Schema: W3C Recommendation, 2 May 2001, http://www.w3.org/XML/Schema.
[3] ISO/IEC 15938-1, Information technology – Multimedia content description interface – Part 1: Systems.
[4] ISO/IEC 21001-16, Information technology – Multimedia Framework – Part 16: Binary Format.