Multimedia bsc Exam 2000 SOLUTIONS Setter: ADM CheckerACJ Additional Material: SMIL Language Description Sheet Answer 3 Questions out of 4 (a)What is meant by the terms Multimedia and Hypermedia? Distinguish between these two concepts Multimedia---- An Application which uses a collection of multiple media sources e.g.text, graphics, images, sound/audio, animation and/or video Hypermedia--- An application which uses associative relationships among information contained within multiple media data for the purpose of facilitating access to, and manipulation of, the information encapsulated by the data 2 MARKS---- BOOKWORK (b) What is meant by the terms static media and dynamic media? Give two examples ofeach type of media Static Media-does not change over time, e.g. text, graphics Dynamic Media -- Time dependent (Temporal), e.g. Video, sound, animation 4 MARKS--- BOOKWORK (c) What issues offunctionality need to be provided in order to effectively use a wide variety of media in Multimedia applications? Your answer should briefly address how such functionality can facilitated in general Multimedia applications The following functionality should be provided Digital Representation of Media ---Many formats for many media Capture: Digitisation of Media--- special Hardware/Software Creation and editing ---assemble media and alter it Storage Requirements ---significant for multimedia Compression ---related to above and below, ie can save on storage but can hinder retrieval Structuring and retrieval methods of media ---simple to advanced Data Base
Multimedia BSc Exam 2000 SOLUTIONS Setter: ADM CheckerACJ Additional Material: SMIL Language Description Sheet Answer 3 Questions out of 4 1. (a) What is meant by the terms Multimedia and Hypermedia? Distinguish between these two concepts. Multimedia ---- An Application which uses a collection of multiple media sources e.g. text, graphics, images, sound/audio, animation and/or video. Hypermedia --- An application which uses associative relationships among information contained within multiple media data for the purpose of facilitating access to, and manipulation of, the information encapsulated by the data. 2 MARKS ---- BOOKWORK (b) What is meant by the terms static media and dynamic media? Give two examples of each type of media. Static Media – does not change over time, e.g. text, graphics Dynamic Media --- Time dependent (Temporal), e.g. Video, sound, animation. 4 MARKS --- BOOKWORK (c) What issues of functionality need to be provided in order to effectively use a wide variety of media in Multimedia applications? Your answer should briefly address how such functionality can facilitated in general Multimedia applications. The following functionality should be provided: - Digital Representation of Media --- Many formats for many media - Capture: Digitisation of Media --- special Hardware/Software - Creation and editing --- assemble media and alter it - Storage Requirements --- significant for multimedia - Compression --- related to above and below, ie can save on storage but can hinder retrieval - Structuring and retrieval methods of media --- simple to advanced DataBase Storage
Display or Playback methods---effect of retrieval must view data Media Synchronisation -- display multimedia as it is intended 9 MARKS---BOOKWORK (d) Different types of media will require different types of supporting operations to provide adequate levels functionality. For the examples of static and dynamic media given in your answer to part /(b) briefly discuss what operations are need to support a wide range of multimedia applications A selection of the items below is reuired for good marks NOT ALL Other Solns Possible? Typical Range of operations required for common media Text: Editing Formatting ng Searching Encrypting ABOVE REQUIRE Character manipulation String Manipulation Audio Audio editing Synchronisation Conversion/Translation Filtering/ Sound Enhancing Operators pressi Searching ABOVE REQUIRE ample manipulation Waveform Manipulation Graphics: Graphic primitive Editing Shading Ⅴ lewing Rendering ng ABOVE REQUIRE Structural/Group Manipulation
- Display or Playback methods --- effect of retrieval must view data - Media Synchronisation --- display multimedia as it is intended 9 MARKS --- BOOKWORK (d) Different types of media will require different types of supporting operations to provide adequate levels of functionality. For the examples of static and dynamic media given in your answer to part 1(b) briefly discuss what operations are need to support a wide range of multimedia applications. A selection of the items below is reuired for good marks NOT ALL. Other Solns Possible? Typical Range of operations required for common media Text: Editing Formatting Sorting Indexing Searching Encrypting ABOVE REQUIRE: : Character Manipulation String Manipulation Audio: Audio Editing Synchronisation Conversion/Translation Filtering/ Sound Enhancing Operators Compression Searching Indexing ABOVE REQUIRE: : Sample Manipulation Waveform Manipulation Graphics: Graphic primitive Editing Shading Mapping Lighting Viewing Rendering Searching Indexing ABOVE REQUIRE: : Primitive Manipulation Structural/Group Manipulation
Image Pixel operations Geometric Operations Filter XIng Compression Animation: Primitive/Group Editing Structural Editing Rendering Searching exIng Video Pixel Operations Frame Operations Editing Synchronisation Conversion Mixing Searching Video effects/Filtering 2 MARKS --- UNSEEN
Image: Pixel operations Geometric Operations Filtering Conversion Indexing Compression Searching Animation: Primitive/Group Editing Structural Editing Rendering Synchronistaion Searching Indexing Video: Pixel Operations Frame Operations Editing Synchronisation Conversion Mixing Indexing Searching Video Effects/Filtering 12 MARKS --- UNSEEN
(a) Why is file or data compression necessary for Multimedia activities? Multimedia files are very large therefore for storage file transfer etc file 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 ofeach 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 ossy 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 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
2. (a) Why is file or data compression necessary 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) = 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 2. 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 exploiti 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, XO, and assign 4 bits for each difference then we only use 20 bits Which is better than an average 5 bits/pixel 8 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 (e.g, ABC Initialization: Put all nodes in an OPEN list, keep it sorted at all times EDEY
1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE. 2. 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 8 MARKS --- BOOKWORK (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 )From open pick two nodes having the lowest equencies/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, I to the two branches of the tree, and delete the children from open Symbol Count OPEN (1)OPEN (2)OPEN (3) B 10 C 3 Total ndicate merge node with other node with number in column
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 20 B 10 C 3 7 12 - D 4 - E 5 - Total 30 - indicate merge node with other node with number in column
Finished Huffman Tree Symbol Code 01 ABCDE 0001 0000 How is this message transmitted when encoded P4(30) P3(20) B(10) P2(1 A(8) P1 E(5) 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 ABCDE 10 3 16 15
Finished Huffman Tree: Symbol Code A 01 B 1 C 0001 D 0000 E 001 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 10 C 3 13 D 4 16 E 5 15 D(4) C(3) P1(7) E(5) P2(12) A(8) P3(20) B(10) P4(30) 0 0 0 0 1 1 1 1
Total Number bits(excluding code book)=70 Entropy.=70/30=23333 4 MARKS-- UNSEEN (iii) What amendments are required to this coding technique if data is generated live or is othenwise not wholly available? Show how you could use this modified scheme by adding the tokens ADADA to the above message Adaptive method needed Basic idea(encoding Initialize model( while ((c getc (input))!= eof) encode (c, output)i update model (c) So encode message as before A=01D=0000 So addd stream 01000001000001
Total Number bits (excluding code book) = 70 Entropy = 70/30 = 2.3333 4 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 adding the tokens ADADA to 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
TSABCDE ify Symbol Count OPEN (1)OPEN (2)OPEN (3 1036 P4(35) P3(24) A(11) P2(14) B(10) P1( D(6) 6 Marks -- UNSEEN
Modify Tree: Symbol Count OPEN (1) OPEN (2) OPEN (3) A 11 B 10 24 C 3 8 14 - D 6 - E 5 - 6 Marks --- UNSEEN E(5) C(3) P1(8) D(6) P2(14) A(11) P3(24) B(10) P4(35) 0 0 0 0 1 1 1 1
3(a)What are the major factors to be taken into account when considering what storage requirements are necessary for Multimedia Systems? Major factors Large volume of date Real time delive Data format Storage medium Retrieval mechanisms 4 MARKS---Unseen/applied bookwork (b) What is RAID technology and what advantages does it offer as a medium for the storage and delivery of large data? RAID--- Redundant Array of Inexpensive Disks Offers. Affordable alternative to mass storage High throughput and reliability RAID System Set of disk drives viewed by user as one or more logical drives Data may be distributed across drives Redundancy added in order to allow for disk failure 4 MARKS--BOOKWORK (c) Briefly explain the eight levels of RAlD functionality Level 0- Disk Striping---distributing data across multiple drives Level 1-Disk Mirroring ---Fault tolerancing Level 2- Bit Interleaving and HEC Parity Level 3- Bit Interleaving with XOR Parity Level 4- Block Interleaving with XOR Parity Level 5-block Interleaving with Parity Distribution Level 6- Fault Tolerant System Error recovery Level 7-Heterogeneuos System--- Fast access across whole system 8 MARKS--- BOOKWORK (d) a digital video file is 40 Mb in size. The disk subsystem has four drives and the controller is designed to support read and write onto each drive, concurrently. The digital video stored using the disk striping concept. A block size of 8 Kb is used for each 1/0 operation
3 (a) What are the major factors to be taken into account when considering what storage requirements are necessary for Multimedia Systems? Major factors: Large volume of date Real time delivery Data format Storage Medium Retrieval mechanisms 4 MARKS --- Unseen/applied bookwork (b) What is RAID technology and what advantages does it offer as a medium for the storage and delivery of large data? RAID --- Redundant Array of Inexpensive Disks Offers: Affordable alternative to mass storage High throughput and reliability RAID System: Set of disk drives viewed by user as one or more logical drives Data may be distributed across drives Redundancy added in order to allow for disk failure 4 MARKS --- BOOKWORK (c) Briefly explain the eight levels of RAID functionality . Level 0 – Disk Striping --- distributing data across multiple drives Level 1 – Disk Mirroring --- Fault tolerancing Level 2 – Bit Interleaving and HEC Parity Level 3 - Bit Interleaving with XOR Parity Level 4 – Block Interleaving with XOR Parity Level 5 - Block Interleaving with Parity Distribution Level 6 – Fault Tolerant System --- Error recovery Level 7 – Heterogeneuos System --- Fast access across whole system 8 MARKS --- BOOKWORK (d) A digital video file is 40 Mb in size. The disk subsystem has four drives and the controller is designed to support read and write onto each drive, concurrently. The digital video stored using the disk striping concept. A block size of 8 Kb is used for each I/O operation
