Multimedia gds MSc exam 2000 SOLUTIONS Setter: ADM Checker: AcJ Answer 3 Questions out of 4 Time allowed 2 Hours 1.(a)Why is data compression, including file compression, highly desirable for Multimedia activities? Multimedia files are very large therefore for storage, file transfer etc file sizes need to be reduced. Text and other files may also be encoded/compressed for email and other applications 2 MARKS--- BOOKWORK (b) Briefly explain, clearly identifying the diferences between them, how entropy coding and transform coding techniques work for data compression. Illustrate your answer with a simple example ofeach type Compression can be categorised in two broad ways ossless Compression where data is compressed and can be reconstituted (uncompressed) without loss of detail or information. These are referred to as bit-preserving or reversible compression systems also Lossy Compression where the aim is to obtain the best possible fidelity for a given bit-rate or minimizing the bit-rate to achieve a given fidelity measure. Video and audio compression techniques are most suited to this form of compression Lossless compression frequently involves some form of entropy encoding and are based in information theoretic techniques Lossy compression use source encoding techniques that may involve transform encoding, differential encoding or vector quantisation ENTROPY METHODS
Multimedia IGDS MSc Exam 2000 SOLUTIONS Setter: ADM Checker: ACJ Answer 3 Questions out of 4 Time Allowed 2 Hours 1. (a) Why is data compression, including file compression, highly desirable for Multimedia activities? Multimedia files are very large therefore for storage, file transfer etc. file sizes need to be reduced. Text and other files may also be encoded/compressed for email and other applications. 2 MARKS --- BOOKWORK (b) Briefly explain, clearly identifying the differences between them, how entropy coding and transform coding techniques work for data compression. Illustrate your answer with a simple example of each type. Compression can be categorised in two broad ways: Lossless Compression -- where data is compressed and can be reconstituted (uncompressed) without loss of detail or information. These are referred to as bit-preserving or reversible compression systems also. Lossy Compression -- where the aim is to obtain the best possible fidelity for a given bit-rate or minimizing the bit-rate to achieve a given fidelity measure. Video and audio compression techniques are most suited to this form of compression. Lossless compression frequently involves some form of entropy encoding and are based in information theoretic techniques Lossy compression use source encoding techniques that may involve transform encoding, differential encoding or vector quantisation. ENTROPY METHODS:
The entropy of an information source S is defined as H(S)=SUM,(P Log2(1/P) where Pi is the probability that symbol S, in S will occur Log2(1/P)indicates the amount of information contained in Si, i.e., the number of bits needed to code s Encoding for the Shannon-Fano Algorithm A top-down approach 1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE 3 Recursively divide into two parts, each with approx. same number of counts (Huffman algorithm also valid indicated below) A simple transform coding example A Simple Transform Encoding procedure maybe described by the following steps for a 2x2 block of monochrome pixels 1. Take top left pixel as the base value for the block, pixel A 2. Calculate three other transformed values by taking the difference between these(respective) pixels and pixel A, i.e. B-A, C-A, D-A 3. Store the base pixel and the differences as the values of the transform Given the above we can easily for the forward transform and the inverse transform is trivial The above transform scheme may be used to compress data by explo redundancy in the data Any redundancy in the data has been transformed to values, Xi. So we can compress the data by using fewer bits to represent the differences. I. e if we use 8 bits per pixel then the 2x2 block uses 32 bits/ If we keep 8 bits for the ba pixel, XO, and assign 4 bits for each difference then we only use 20 bits Which is better than an average 5 bits/pixel 7 MARKS--- BOOKWORK
The entropy of an information source S is defined as: H(S) = SUMI (PI Log2 (1/PI) where PI is the probability that symbol SI in S will occur. Log2 (1/PI) indicates the amount of information contained in SI, i.e., the number of bits needed to code SI. Encoding for the Shannon-Fano Algorithm: A top-down approach 1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE. 3 Recursively divide into two parts, each with approx. same number of counts. (Huffman algorithm also valid indicated below) A simple transform coding example A Simple Transform Encoding procedure maybe described by the following steps for a 2x2 block of monochrome pixels: 1. Take top left pixel as the base value for the block, pixel A. 2. Calculate three other transformed values by taking the difference between these (respective) pixels and pixel A, i.e. B-A, C-A, D-A. 3. Store the base pixel and the differences as the values of the transform. Given the above we can easily for the forward transform: and the inverse transform is trivial The above transform scheme may be used to compress data by exploiting redundancy in the data: Any Redundancy in the data has been transformed to values, Xi. So We can compress the data by using fewer bits to represent the differences. I.e if we use 8 bits per pixel then the 2x2 block uses 32 bits/ If we keep 8 bits for the base pixel, X0, and assign 4 bits for each difference then we only use 20 bits. Which is better than an average 5 bits/pixel 7 MARKS --- BOOKWORK
(c)( Show how you would use Huffman coding to encode the following set of tokens BABACACADADABBCBABEBEDDABEEEBB How is this message transmitted when encoded? The Huffman algorithm is now briefly summarised Initialization: Put all nodes in an OPEN list, keep it sorted at all times (e.g., ABCDE) 2. Repeat until the open list has only one node left (a) From open pick two nodes having the lowest frequencies/probabilities, create a parent node of them (b) Assign the sum of the childrens frequencies/probabilities to the parent node and insert it into OPEN (c)Assign code 0, I to the two branches of the tree, and delete the children from OPeN Symbol Count OPEN (1)OPEN (2)OPEN (3) ABCDE 8u34 7 Total 30 8 indicate merge node with other node with number in column
(c) (i) Show how you would use Huffman coding to encode the following set of tokens: BABACACADADABBCBABEBEDDABEEEBB How is this message transmitted when encoded? The Huffman algorithm is now briefly summarised: 1. Initialization: Put all nodes in an OPEN list, keep it sorted at all times (e.g., ABCDE). 2. Repeat until the OPEN list has only one node left: (a) From OPEN pick two nodes having the lowest frequencies/probabilities, create a parent node of them. (b) Assign the sum of the children's frequencies/probabilities to the parent node and insert it into OPEN. (c) Assign code 0, 1 to the two branches of the tree, and delete the children from OPEN. Symbol Count OPEN (1) OPEN (2) OPEN (3) A 8 18 B 10 - C 3 7 12 D 4 - E 5 - Total 30 8 indicate merge node with other node with number in column
Finished Huffman Tree P4(30) P2(1 P3(18) E(5) A(8) B(10) C(3) D(4) Symbol Code ABCDE 11 010 0l1 How is this message transmitted when encoded? Send code book and then bit code for each symbol 7 Marks -- UNSEEN (ii) How many bits are needed transfer this coded message and what is its Entropy? Symbol Count Subtotal of bits 8 ABCDE 9
Finished Huffman Tree: Symbol Code A 10 B 11 C 010 D 011 E 00 How is this message transmitted when encoded? Send code book and then bit code for each symbol. 7 Marks --- UNSEEN (ii) How many bits are needed transfer this coded message and what is its Entropy? Symbol Count Subtotal # of bits A 8 16 B 10 20 C 3 9 D 4 12 E 5 10 D(4) C(3) P1(7) E(5) P2(12) A(8) P3(18) B(10) P4(30) 0 0 0 0 1 1 1 1
Total Number bits(excluding code book)=62 Entropy=62/30=20666 8 MARKS--- UNSEEN (iii) What amendments are required to this coding technique if data is generated live or is otherwise not wholly available? Show how you could se this modified scheme by appending the tokens ADADA to the end of the above message Adaptive method needed Initialize model( le ((c getc code (C, output) update model (c) So encode message as before A=01D=0000 So addd stre 01000001000001
Total Number bits (excluding code book) = 62 Entropy = 62/30 = 2.06667 8 MARKS --- UNSEEN (iii) What amendments are required to this coding technique if data is generated live or is otherwise not wholly available? Show how you could use this modified scheme by appending the tokens ADADA to the end of the above message. Adaptive method needed: Basic idea (encoding) Initialize_model(); while ((c = getc (input)) != eof) { encode (c, output); update_model (c); } So encode message as before: A= 01 D = 0000 So addd stream: 01000001000001
Modify tree Symbol Count OPEN (1)OPEN (2) OPEN (3) 21 ABCDE 10365 P4(35) P2(1 P3(21) 0 B(10 A(11) D(6) C(3) E(5) 5 Marks -- UNSEEN
Modify Tree: Symbol Count OPEN (1) OPEN (2) OPEN (3) A 11 21 B 10 - C 3 8 14 D 6 - E 5 - 5 Marks --- UNSEEN D(6) C(3) P1(8) E(5) P2(14) A(11) P3(21) B(10) P4(35) 0 0 0 0 1 1 1 1
2(a) Give a definition of a Multimedia Authoring System. What key features should such a system provide? An Authoring System is a program which has pre-programmed elements for the development of interactive multimedia software titles Authoring systems vary widely in orientation, capabilities, and learning curve There is no such thing(at this time)as a completely point-and-click automated authoring system; some knowledge of heuristic thinking and algorithm design necessary Authoring is basically just a speeded-up form of programming---VISUAL PROGRAMMING; you don,'t need to know the intricacies of a programming language, or worse, an APl, but you do need to understand how programs work 2 MARKS --BOOKWORK (b)What Multimedia Authoring paradigms exist? Describe each paradigm briefly There are various paradigms, including The Scripting paradigm is the authoring method closest in form to traditional programming. The paradigm is that of a programming language, which specifies( filename)multimedia elements, sequencing, hotspots, synchronization, etc. A powerful, object-oriented scripting language is usually the centerpiece of such a system; in-program editing of elements( still graphics, video, audio, etc. )tends to be minimal or non-existent. Scripting languages do vary; check out how much the language is object-based or object-oriented The scripting paradigm tends to be longer in development time(it takes longer to code an individual interaction), but generally more powerful interactivity is possible. Since most Scripting languages are interpreted, instead of compiled, the runtime speed gains over other authoring methods are minimal The media handling can vary widely; check out your system with your contributing package formats carefully. The Apple's Hyper Talk for HyperCard, Assymetrix's Open Script for Tool Book and Lingo scripting language of Macromedia Director are examples of a Multimedia scripting language Here is an example lingo script to jump to a frame glob gNav
2 (a) Give a definition of a Multimedia Authoring System. What key features should such a system provide? An Authoring System is a program which has pre-programmed elements for the development of interactive multimedia software titles. Authoring systems vary widely in orientation, capabilities, and learning curve. There is no such thing (at this time) as a completely point-and-click automated authoring system; some knowledge of heuristic thinking and algorithm design is necessary. Authoring is basically just a speeded-up form of programming --- VISUAL PROGRAMMING; you don't need to know the intricacies of a programming language, or worse, an API, but you do need to understand how programs work. 2 MARKS ---- BOOKWORK (b) What Multimedia Authoring paradigms exist? Describe each paradigm briefly. There are various paradigms, including: Scripting Language The Scripting paradigm is the authoring method closest in form to traditional programming. The paradigm is that of a programming language, which specifies (by filename) multimedia elements, sequencing, hotspots, synchronization, etc. A powerful, object-oriented scripting language is usually the centerpiece of such a system; in-program editing of elements (still graphics, video, audio, etc.) tends to be minimal or non-existent. Scripting languages do vary; check out how much the language is object-based or object-oriented. The scripting paradigm tends to be longer in development time (it takes longer to code an individual interaction), but generally more powerful interactivity is possible. Since most Scripting languages are interpreted, instead of compiled, the runtime speed gains over other authoring methods are minimal. The media handling can vary widely; check out your system with your contributing package formats carefully. The Apple’s HyperTalk for HyperCard, Assymetrix’s OpenScript for ToolBook and Lingo scripting language of Macromedia Director are examples of a Multimedia scripting language. Here is an example lingo script to jump to a frame glob al gNav
Sprl on exitFrame go the frame play sprite gNavsprite Iconic/flow control This tends to be the speediest(in development time) authoring style; it is best suited for rapid prototyping and short-development time projects. Many of these tools are also optimized for developing Computer-Based Training(CBT). The core of the paradigm is the Icon Palette, containing the possible functions/interactions of a program, and the Flow Line, which shows the actual links between the icons. These programs tend to be the slowest runtimes, because each interaction carries with it all of its possible permutations; the higher end packages, such as Authorware or IconAuthor, are extremely powerful and suffer least from runtime speed problems Fr rame The Frame paradigm is similar to the Iconic/Flow Control paradigm in that it usually incorporates an icon palette; however, the links drawn between icons are conceptual and do not always represent the actual flow of the program. This is a very fast development system, but requires a good auto-debugging function, as it is visually un-debuggable. The best of these have bundled compiled-language scripting, such as Quest( whose scripting language is C)or Apple Media Kit Card/Scripting The Card/Scripting paradigm provides a great deal of power(via the incorporated scripting language)but suffers from the index-card structure. It is excellently suitedfor Hypertext applications, and supremely suited for navigation intensive(a la Cyan's"MYST game)applications. Such programs are easily extensible via XCMDs andDLLS; they are widely used for shareware applications. The best applications allow all objects (including individual graphic elements )to be scripted many entertainment applications are prototyped in a card/ scripting system prior to Cast/ScoreScrinting The Cast/Score/Scripting paradigm uses a music score as its primary authoring metaphor; the synchronous elements are shown in various horizontal tracks withsimultaneity shown via the vertical columns. The true power of this metaphor lies in the ability to script the behavior of each of the cast members. The most popularmember of this paradigm is Director, which is used in the creation of many commercial applications. These programs are best suited for animation-intensive orsynchronized media applications; they are easily extensible to handle other functions(such as hypertext)via XOB JS, XCMDS, and dlls Macromedia director uses this
Spri te on exitFrame go the frame play sprite gNavSprite end Iconic/Flow Control This tends to be the speediest (in development time) authoring style; it is best suited for rapid prototyping and short-development time projects. Many of these tools are also optimized for developing Computer-Based Training (CBT). The core of the paradigm is the Icon Palette, containing the possible functions/interactions of a program, and the Flow Line, which shows the actual links between the icons. These programs tend to be the slowest runtimes, because each interaction carries with it all of its possible permutations; the higher end packages, such as Authorware or IconAuthor, are extremely powerful and suffer least from runtime speed problems. Frame The Frame paradigm is similar to the Iconic/Flow Control paradigm in that it usually incorporates an icon palette; however, the links drawn between icons are conceptual and do not always represent the actual flow of the program. This is a very fast development system, but requires a good auto-debugging function, as it is visually un-debuggable. The best of these have bundled compiled-language scripting, such as Quest (whose scripting language is C) or Apple Media Kit. Card/Scripting The Card/Scripting paradigm provides a great deal of power (via the incorporated scripting language) but suffers from the index-card structure. It is excellently suitedfor Hypertext applications, and supremely suited for navigation intensive (a la Cyan’s “MYST” game) applications. Such programs are easily extensible via XCMDs andDLLs; they are widely used for shareware applications. The best applications allow all objects (including individual graphic elements) to be scripted; many entertainment applications are prototyped in a card/scripting system prior to compiled-language coding. Cast/Score/Scripting The Cast/Score/Scripting paradigm uses a music score as its primary authoring metaphor; the synchronous elements are shown in various horizontal tracks withsimultaneity shown via the vertical columns. The true power of this metaphor lies in the ability to script the behavior of each of the cast members. The most popularmember of this paradigm is Director, which is used in the creation of many commercial applications. These programs are best suited for animation-intensive orsynchronized media applications; they are easily extensible to handle other functions (such as hypertext) via XOBJs, XCMDs, and DLLs. Macromedia Director uses this
Hierarchical obiect The Hierarchical Object paradigm uses a object metaphor(like OoP)which is visually represented by embedded objects and iconic properties. Although the learning curve is non-trivial, the visual representation of objects can make very complicated constructions possible Hypermedia Linkage conceptual links between elements; however, it lacks the Frame paradigm s vsSuayiso The Hypermedia Linkage paradigm is similar to the Frame paradigm in that it shov linkage metaphor The Tagging paradigm uses tags in text files(for instance, SGML/HTML, SMIL (Synchronised Media Integration Language), VRML, 3DML and WinHelp)to link pages, provide interactivity and integrate multimedia elements 8 Marks --BOOKWORK (c) You have been asked to provide a Multimedia presentation that can support media in both English and French. You have been given a sequence of 10 images and a single 50 second digitised audio soundtrack in both languages. Each Image should be mapped over consecutive 5 second fragments of the audio. All Images are of the same 500x500 pixel dimension Describe, giving suitable code fragments, how you would assemble such a presentation using SMIL. Your solution should cover all aspects of the SMIL presentation out
Hierarchical Object The Hierarchical Object paradigm uses a object metaphor (like OOP) which is visually represented by embedded objects and iconic properties. Although the learning curve is non-trivial, the visual representation of objects can make very complicated constructions possible. Hypermedia Linkage The Hypermedia Linkage paradigm is similar to the Frame paradigm in that it shows conceptual links between elements; however, it lacks the Frame paradigm’s visual linkage metaphor. Tagging The Tagging paradigm uses tags in text files (for instance, SGML/HTML, SMIL (Synchronised Media Integration Language), VRML, 3DML and WinHelp) to link pages, provide interactivity and integrate multimedia elements. 8 Marks --- BOOKWORK (c) You have been asked to provide a Multimedia presentation that can support media in both English and French. You have been given a sequence of 10 images and a single 50 second digitised audio soundtrack in both languages. Each Image should be mapped over consecutive 5 second fragments of the audio. All Images are of the same 500x500 pixel dimension. Describe, giving suitable code fragments, how you would assemble such a presentation using SMIL. Your solution should cover all aspects of the SMIL presentation ………
audio system-language="en"src="english. au"/> 14 Marks -- UNSEEN
……. 14 Marks ---- UNSEEN