Author: Guojun Lu
Hardcover 373 pp.
Published in October 1999, by Artech House Publishers
ISBN: 0-89006-342-7
Traditional database management systems can’t handle the demands of managing multimedia data. With the rapid growth of multimedia platforms and the world wide web, database management systems must now process, store, index, and retrieve alphanumeric data, bitmapped and vector-based graphics, and video and audio clips both compressed and uncompressed. The comprehensive, systematic approach of Multimedia Database Management Systems presents you with current and emerging methods for managing the increasing demands of multimedia databases and their inherent design and architecture issues.
With this comprehensive resource, you learn how to create an effective multimedia database by integrating the various information indexing and retrieval methods currently available. Also, you learn to measure multimedia database performance that is based on similarity to queries and routinely affected by human judgement.
This book concludes with a discussion of networking and operating system support for multimedia databases and a look at current research and development in this dynamic field. It is a vital tool for database developers and managers, multimedia researchers, as well as web developers.
Outline:
Detailed Table of Contents
Preface xvii
Chapter 1 Introduction 1
1.1 Some Important Definitions 1
1.1.1 Media Types and Multimedia 1
1.1.2 Databases and Database Management Systems 2
1.1.3 Text Document Information Retrieval 2
1.1.4 Multimedia Indexing and Retrieval 3
1.1.5 Feature Extraction, Content Representation and Indexing 3
1.2 Need for MIRS 3
1.2.1 Proliferation of Multimedia Data and Their Characteristics 3
1.2.2 DBMSs and Their Role in Handling Multimedia Data 4
1.2.3 Information Retrieval Systems and Their Role in Multimedia
Retrieval 7
1.2.4 Integrated Approach to Multimedia Information Indexing and
Retrieval 7
1.3 An Overview of the MIRS 7
1.4 Expected Capabilities and Common Applications of MIRS 8
1.5 Organization of the Subsequent Chapters 10
Problems 11
REFERENCES 11
Chapter 2 Multimedia Data Types and Formats 13
2.1 Introduction 13
2.2 Text 14
2.2.1 Plain Text 14
2.2.2 Structured Text 15
2.2.3 Text Compression 15
Huffman Coding 15
Run-Length Coding 16
Lempel-Ziv-Welch (LZW)
Coding 17
2.3 Vector Graphics and Animation 17
2.4 Audio 18
2.4.1 Basic Characteristics of Audio Signal 18
2.4.2 Digital Representation of Audio 18
Sampling 19
Quantization 20
Coding 20
Determination of
Sampling Rate 21
Determining the Number
of Quantization Levels 22
2.4.3 Musical Instrument Digital Interface (MIDI) 24
2.4.4 Audio Compression 24
Nonlinear Quantization
24
Predictive Coding 25
Compression Technique
Using Masking Property: MPEG-Audio 27
2.5 Digital Images 28
2.5.1 Digital Image Representation 28
Representation of Grey Scale Images 28
Representation of Color Images 29
2.5.2 Main Parameters of Digital Images 29
2.5.3 Image Compression 29
Spatial Subsampling 30
Predictive Coding 30
Transform Coding 31
Vector Quantization 31
Fractal Image Coding 32
Wavelet Compression 33
Practical Coding Systems 33
The JPEG-Still Image Compression Standard 33
JBIG 34
JPEG-2000 36
2.6 Digital Video 36
2.6.1 Digital Video Representation 36
2.6.2 Video Compression 37
2.6.2.1 Motion Estimation and Compensation 37
2.6.2.2 MPEG 38
MPEG-1 39
MPEG-2 40
MPEG-4 41
MPEG-7 42
Other Standards 43
2.7 Standards for Composite Multimedia Documents 43
2.8 Major Characteristics and Requirements of Multimedia Data and
Applications 44
2.8.1 Storage and Bandwidth Requirements 44
2.8.2 Semantic Structure of Multimedia Information 46
2.8.3 Delay and Delay Jitter Requirements 46
2.8.4 Temporal and Spatial Relationships Among Related Media 47
2.8.5 Subjectiveness and Fuzziness of the Meaning of Multimedia Data 47
2.9 Summary 47
Problems 48
Further Reading 50
References 50
Chapter 3 Multimedia Database Design Issues 53
3.1 Introduction 53
3.2 MIRS Architecture 54
3.3 Data Models 55
3.3.1 Data Model Requirements 55
3.3.2 A General Multimedia Data Model 56
Object Layer 56
Media Type Layer 57
Media Format Layer 57
Remaining Issues 57
3.3.3 Example Data Models 58
VIMSYS Data Model 58
A General Video Model
59
Virage Image Schema
Structure 60
3.4 User Interface Design 61
3.4.1 Database Population 61
3.4.2 Query Support 62
Search 62
Browsing 62
Query refinement 63
3.4.3 Result Presentation 63
3.5 Feature Extraction, Indexing and Similarity Measure 64
3.5.1 Feature Extraction 64
3.5.2 Indexing Structure 66
3.5.3 Similarity Measurement 66
3.6 Quality of Service Guarantees in Clients, Servers and Communication
Systems 66
3.7 Other Issues 67
3.7.1 Multimedia Data Compression 67
3.7.2 Data Representation Standardization 68
3.7.3 Query Processing and Retrieval 69
3.8 Summary 69
Problems 69
Further Readings 71
References 71
Chapter 4 Text Document Indexing and Retrieval 73
4.1 Introduction 73
4.2 Differences Between IR Systems and DBMS 74
4.3 Automatic Text Document Indexing and Boolean Retrieval Model 75
4.3.1 Basic Boolean Retrieval Model 75
4.3.2 File Structure 76
Inverted Files 76
Extensions of the
Inverted File Operation 77
4.3.3 Term Operations and Automatic Indexing 78
4.3.4 Summary of Automatic Document Indexing 81
4.4 Vector Space Retrieval Model 81
4.4.1 Basic Vector Space Retrieval Model 81
4.4.2 Relevance Feedback Techniques 82
Query Modification 83
Document Modification
83
4.5 Probabilistic Retrieval Model 84
4.6 Cluster-based Retrieval Model 84
4.6.1 Cluster Generation 85
4.6.2 Cluster-Based Retrieval 85
4.7 Non-traditional Information Retrieval Methods 85
4.8 Performance Measurement 86
4.9 Performance Comparison among Different IR Techniques 89
4.10 WWW Search Engines 89
4.10.1 A Brief Introduction to the WWW 89
4.10.2 Resource Discovery 92
4.10.3 Major Differences Between IR Systems and WWW Search
Engines 93
4.10.3.1 WWW Documents are Distributed 94
4.10.3.2 The Number of WWW Documents Is
large 94
4.10.3.3 WWW Documents are Dynamic and
Heterogeneous 95
4.10.3.4 WWW Documents Are Structured 95
4.10.3.5 WWW Search Engines Are Heavily Used 96
4.10.3.6 Other Issues 96
4.10.4 General Structure of Www Search Engines 96
4.10.5 An Example Search Engine 97
4.10.5.1 Architecture Overview of Google 97
4.10.5.2 Web Crawling 99
4.10.5.3 PageRanks and Anchor Text 99
4.10.5.4 Searching 100
4.11 Summary 100
Problems 100
Further Reading 103
References 103
Chapter 5 Indexing and Retrieval of Audio 105
5.1 Introduction 105
5.2 Main Audio Properties and Features 106
5.2.1 Features Derived in the Time Domain 106
5.2.2 Features Derived from the Frequency Domain 108
Sound Spectrum 108
Bandwidth 110
Energy Distribution 110
Harmonicity 110
Pitch 111
5.2.3 Spectrogram 111
5.2.4 Subjective Features 112
5.3 Audio Classification 112
5.3.1 Main Characteristics of Different Types of Sound 113
5.3.2 Audio Classification Frameworks 113
5.4 Speech Recognition and Retrieval 116
5.4.1 Speech Recognition 116
5.4.1.1 Basic Concepts of ASR 116
5.4.1.2 Techniques Based on Dynamic Time
Warping 118
5.4.1.3 Techniques Based on Hidden Markov
Models 119
5.4.1.4 Techniques Based on Artificial Neural
Networks 121
5.4.1.5 Speech Recognition Performance 121
5.4.2 Speaker Identification 122
5.4.3 Summary 122
5.5 Music Indexing and Retrieval 122
5.5.1 Indexing and Retrieval of Structured Music and Sound Effects 122
5.5.2 Indexing and Retrieval of Sample-Based Music 123
Music retrieval based on a set of features 123
Music retrieval based on pitch 124
5.6 Multimedia Information Indexing and Retrieval using Relationships
Between Audio and Other Media 125
5.7 Summary 126
Problems 126
References 128
Chapter 6 Image Indexing and Retrieval 131
6.1 Introduction 131
6.2 Different Approaches to Image Indexing and Retrieval 132
6.3 Text-based Image Retrieval 132
6.4 Color Based Image Indexing And Retrieval Techniques 133
6.4.1 The Basic Color Based Image Retrieval Technique 133
6.4.2 Improvements to the Basic Technique 134
6.4.2.1 Making Use of Similarity Among Colors
135
6.4.2.2 Making Use of Spatial Relationships
Among Pixels 137
6.4.2.3 Making Use of the Statistics of Color
Distribution 138
6.4.2.4 Better Color Representation 138
Different Color Spaces
138
Variations of Image
Representation 139
Effects of Different
Image Representations on Retrieval
Performance 139
6.5 Image Retrieval Based on Shape 142
6.5.1 Definitions of Common Terms and Some Simple Shape
Measurements 143
6.5.2 Invariant Moments 143
6.5.3 Fourier Descriptors Method 145
6.5.4 Histogram of Significant Edges 146
6.5.5 Ordered List of Interest Points 146
6.5.6 Elastic Template Matching 147
6.5.7 Region-Based Shape Representation and Similarity Measure 147
6.5.7.1 Basic Idea of Region-Based Shape
Representation 148
6.5.7.2 Rotation Normalisation 148
6.5.7.3 Scale Normalisation 149
6.5.7.4 Unique Shape Representation - Shape
Index 149
6.5.7.5 Similarity Measure 150
6.5.7.6 Other Shape Operations 151
6.5.7.7 Handling Multiple Major Axes 152
6.5.7.8 Summary of Index and Retrieval
Processes 152
6.5.7.9 Retrieval Performance 153
6.6 Image Retrieval Based on Texture 155
6.7 Image Indexing And Retrieval Based On Compressed Image Data 156
6.7.1 Image Indexing and Retrieval Based on DCT Coefficients 156
6.7.2 Image Indexing and Retrieval Based on Wavelet Coefficients 157
6.7.3 Image Indexing and Retrieval Based on VQ Compressed Data 157
6.8 Other Image Indexing and Retrieval Techniques 159
6.8.1 Image Retrieval Based on Model-Based Compression 159
6.8.2 Image Retrieval Based on Spatial Relationship 159
6.9 Integrated Image Indexing And Retrieval Techniques 159
6.9.1 Query By Image Content (QBIC) 160
6.9.2 Virage Image Search Engine 160
6.9.3 WebSEEK 160
6.9.4 ImageRover WWW Search Engine 161
Problems 161
Appendix A Color Representations 163
A.1 Color Properties 164
A.2 Color Specification Systems 164
Device-Independent Color Specification 165
Relationships Between CIE XYZ and Other Color
Spaces 167
Uniform Color Spaces 169
A.3 Different Color Representations 170
Gamma Correction 170
Different RGB Systems or Color Spaces 173
References 175
Chapter 7 Video Indexing and Retrieval 179
7.1 Introduction 179
7.2 Overview of Shot-based Video Indexing and Retrieval 180
7.3 Video Shot Detection or Segmentation 181
7.3.1 Basic Video Segment Techniques 181
7.3.2 Detecting Shot Boundaries with Gradual Change 182
7.3.3 Preventing False Shot Detection 183
7.3.4 Other Shot Detection Techniques 184
7.3.5 Segmentation of Compressed Video 185
Based on MPEG Compressed Video 185
Based on VQ Compressed Video 186
7.4. Video Indexing and Retrieval 186
7.4.1 Indexing and Retrieval Based on R-Frames of Video Shots 186
7.4.2 Indexing and Retrieval Based on Motion Information 188
7.4.3 Indexing and Retrieval Based on Objects 189
7.4.4 Indexing and Retrieval Based on Meta Data 190
7.4.5 Indexing and Retrieval Based on Annotation 190
7.4.6 Integrated Approach to Video Indexing and Retrieval 190
7.5 Effective Video Representation and Abstraction 191
7.5.1 Topical or Subject Classification 191
7.5.2 Motion Icon or Video Icon 192
7.5.3 Video Streamer 193
7.5.4 Clipmap 194
7.5.5 Hierarchical Video Browser 194
7.5.6 Storyboard 195
7.5.7 Mosaicing 195
7.5.8 Scene Transition Graph 195
7.5.9 Video Skimming 196
7.6 Summary 196
Problems 196
References 198
Chapter 8 Integrated Multimedia Indexing and Retrieval 201
8.1 Introduction 201
8.2 Integrated Indexing and Retrieval Techniques 202
8.2.1 Integrated Audio Indexing and Retrieval 203
8.2.2 Integrated Image Indexing and Retrieval 204
8.2.3 Integrated Video Indexing and Retrieval 204
8.2.4 Merging of Results Obtained Based on Individual Features 204
8.2.5 Media Translation 205
8.3 A General Architecture of Multimedia Information Management 205
8.4 User Interface 208
Multimedia authoring and annotation 208
Search and browsing 208
Result presentation and relevance feedback 209
8.5 Example Systems 209
8.5.1 QBIC 210
8.5.2 An Integrated WWW Image Search Engine Developed at
Monash University 211
Text-based image indexing and retrieval 212
Color-based image indexing and retrieval 213
Image retrieval combining text- and
colour-based methods 213
8.5.3 Meta-Search Engines 214
The query interface 215
The query dispatching component 216
The result merger 217
8.6 Summary 218
Problems 218
References 219
Chapter 9 Techniques and Data Structures for Efficient Multimedia
Similarity Search 223
9.1 Introduction 223
9.2 Filtering Processes for Reducing Search Space 224
9.2.1 Filtering with Classification, Structured Attributes and Keywords
225
9.2.2 Methods Based on the Triangle Inequality 225
9.2.3 Methods Specific to Color Histogram Based Retrieval 227
9.2.4 Latent Semantic Indexing for Vector Space Based IR 228
9.3 B+- and B-trees 229
9.3.1 B+-Trees 229
9.3.2 B-Trees 233
9.4 Clustering 233
9.5 Multidimensional B+-tree 235
9.5.1 Overview of MB+-Trees in Two Dimension Space 235
9.5.2 Building a 2-d MB+-tree 237
9.5.3 Search in MB+-trees 238
Point query 238
Range query 238
k Nearest-neighbour query 238
9.5.4 Higher Dimensional MB+-trees 239
9.6 k-d Trees 239
9.7 Grid Files 241
9.8 R-Tree Family 242
9.8.1 An Overview of the R-Tree Structure 242
9.8.2 Search, Insertion and Deletion of Region Objects 244
9.8.3 Search, Insertion and Deletion of Point Data 244
9.8.4 Search Efficiency in the R-Tree 245
9.8.5 R*-tree, R+-tree and VAMSplit R-tree 245
9.8.6 SS-Tree and SS+-Tree 246
9.9 The TV-tree 247
9.10 Summary 247
Problems 248
References 250
Chapter 10 System Support for Distributed Multimedia Databases 253
10.1 Introduction 253
10.2 Qos Management 256
10.2.1 Definition 256
10.2.2 General QOS Framework 257
10.2.3 QOS Specification 258
10.2.4 Admission Control, QOS Negotiation and Renegotiation 258
10.2.5 Different Levels of Guarantee 259
10.2.6 Providing QOS Guarantees 259
10.2.7 An Example of QOS Handling 260
10.3 Design Goals of Multimedia Systems 260
10.4 Multimedia Data Storage Devices and Management 261
10.4.1 Multimedia Storage Server Requirements 262
10.4.2 Storage Devices 263
10.4.2.1 Storage Capacity and Transfer
Bandwidth Requirements 263
10.4.2.2 Comparison of Different Types of
Storage Devices 263
10.4.2.3 Disk Arrays and RAID 264
First-Level RAID:
Mirrored Disks 264
Second-Level RAID:
Hamming Code for Error Correction 264
Third-Level RAID:
Single Check Disk Per Group 265
Fourth-Level RAID:
Independent Reads 265
Fifth-Level RAID: No
Dedicated Check Disk 266
10.4.2.4 Storage Hierarchies 266
10.4.3 Data Placement On Disks 267
10.4.3.1 Contiguous Data Placement 267
10.4.3.2 Scattered Data Placement 268
10.4.3.3 Data Placement in Disk Arrays 269
10.4.4 Disk Scheduling And Admission Control 269
10.4.4.1 Traditional Disk-Scheduling Algorithms
270
10.4.4.2 Earliest Deadline First 270
10.4.4.3 Scan-Earliest Deadline First 271
10.4.4.4 Round-Robin 271
10.4.4.5 Group Sweeping Scheduling 272
10.4.5 Provision Of User Interaction 273
10.4.5.1 Pause and Resume 273
10.4.5.2 Fast Forward and Backward 275
10.4.5.3 QOS Issue Related to User Interactions
275
10.4.6 Server Configuration And Network Connection 276
10.4.7 Summary 277
10.5 Multimedia Computer Architectures 277
10.5.1 Processor Architectures for Multimedia 278
10.5.1.1 SIMD and VLIW 278
10.5.1.2 Dedicated Multimedia Processors 279
10.5.1.3 General-Purpose Processors 279
10.5.2 Multimedia Computer Architectures 280
10.5.2.1 The Basic Architecture 280
10.5.2.2 The Use of Local Buses 281
10.5.2.3 The Use of Dedicated Multimedia
Devices 282
10.5.2.4 Network-Based Multimedia Computer
Architecture 283
10.6 Multimedia Operating Systems 284
10.6.1 Multimedia Operating System Requirements 284
10.6.2 Design Issues of Multimedia Operating Systems 285
10.6.3 Conventional Time-sharing Operating Systems and
Incorporation of Real-time Features 285
10.6.4 Solutions To Data-copying Problem 287
10.6.4.1 Data-Copying
Problem 287
10.6.4.2 Two Data
Movement Methods 288
10.6.4.3 Single-Copy
and Zero-Copy Architecture 288
10.6.5 Solutions To Reduce Context And Domain Switch Overhead 289
10.6.6 QOS Support 290
10.6.6.1 QOS Specification 290
10.6.6.2 Admission Control 290
10.6.6.3 Resource Reservation and Policing 291
10.6.6.4 Process Scheduling Disciplines 291
Rate Monotonic 292
Earliest Deadline First
292
Time-Driven Resource
Management 293
10.6.6.5 QOS Graceful Degradation and Media
Scaling 293
10.7 Multimedia Networks 294
10.7.1 Network Characteristics Suitable For Multimedia Communications
295
10.7.1.1 Network Speed or Bandwidth 295
10.7.1.2 Efficient Sharing of Network Resources
296
10.7.1.3 Performance Guarantees 297
10.7.1.4 Network Scalability 298
10.7.1.5 Networks Suitable for Multimedia
Communications 298
10.7.2 Asynchronous Transfer Mode 300
10.7.2.1 What Is ATM? 300
10.7.2.2 B-ISDN Protocol Reference Model 302
10.7.2.3 Why Is ATM Suitable for Multimedia
Communications? 304
10.7.3 Network Performance Guarantees 305
10.8 Multimedia Transport Protocols 306
10.8.1 Requirements Of Multimedia Transport Protocols 306
10.8.1.1 High Throughput 307
10.8.1.2 QOS Specification and Guarantee 307
10.8.2 Why Traditional Transport Protocols Are Not Suitable
For Multimedia
Communications 307
10.8.2.1 Data Copying 308
10.8.2.2 Flow Control 308
10.8.2.3 Error Control 309
10.8.2.4 Positioning and Handling of Control
Information 309
10.8.2.5 Lack of QOS Support 310
10.8.2.6 Suitability of eXpress Transport
Protocol 310
10.8.3 Resource Reservation Protocols 310
10.8.3.1 ST-II 311
ST-II Connection Setup
311
Flow Specification 312
10.8.3.2 RSVP 313
10.8.3.3 Comparison of ST-II and RSVP 314
10.8.4 Real-time Transport Protocol (RTP) 315
10.8.5 Other Multimedia Transport Protocols: HeiTP and Tenet 316
10.9 Achieving Overall Synchronous Presentation 317
10.9.1 Synchronization Specification 318
10.9.1.1 Scripts 318
10.9.1.2 Time-Line-Based Temporal Specification
319
10.9.1.3 Petri Nets 320
10.9.2 Analysis of Causes of Losing Multimedia Synchronization 320
10.9.3 Mechanisms To Achieve Multimedia Synchronization 322
10.9.3.1 Measures To Counter Network Delay
Variations 322
Corrective Measures 322
Preventive Measures: Network and Transport Support
for Continuous Media 324
10.9.3.2 Measures To Counter Media-Specific
Processing Skew 324
10.9.3.3 Measures To Counter Clock Rate
Difference 324
10.9.3.4 Measures To Counter
Packet-Out-of-Order Problems 325
10.9.3.5 Measures To Coordinate Multiple
Sources for
Synchronous
Transmission 325
10.9.3.6 Workstation and Server Support for
Continuous Media 326
10.9.3.7 Measures To Provide User Interaction
Synchronization 326
10.9.3.8 Playout Techniques To Achieve Optimal
Presentation
Effects 326
10.9.4 An Ultimate Solution Based On QOS Framework 327
Problems 327
References 330
Chapter 11 Measurement of Multimedia Information Retrieval Effectiveness 335
11.1 Introduction 335
11.2 Collection Of Human Judgement Data 336
Method 1 336
Method 2 336
Method 3 337
Selection of data collection methods 337
Need for standard test databases 337
11.3 Recall And Precision Pair (RPP) 338
11.4 Percentage Of Weighted Hits (PWH) 338
11.5 Percentage Of Similarity Rankings (PSR) 339
11.6 Suitability Of The Common Effectiveness Measurements 339
11.6.1 A Numerical Example 340
11.6.2 Strengths and Weaknesses of PSR, PWH and RPP 342
11.7 Modified RPP 343
11.8 Factors Affecting Retrieval Effectiveness 343
11.9 Summary 344
Problems 344
References 345
Chapter 12 Products, Applications and New Developments 347
12.1 Introduction 347
12.2 Products Of Multimedia Database Management Systems 348
12.3 Applications Of Multimedia Indexing And Retrieval 348
12.3.1 WWW Multimedia Search Engines 349
12.3.2 Digital Libraries 349
12.3.3 Video-on-demand Systems 350
12.3.3.1 Networking Support for VOD 351
Asymmetric Digital
Subscriber Line 351
Hybrid Fiber Coax 352
High-Speed Digital
Subscriber Line 353
Direct Optical Fiber
Connection 353
12.3.3.2 Set-Top-Boxes 353
12.3.3.3 Future Developments 354
12.4 Multimedia Security 354
12.4.1 Providing Privacy and Confidentiality 355
12.4.2 Authentication Verification 356
12.4.3 Copyright Protection 357
12.5 MPEG-7 357
Problems 359
References 359
List of Acronyms 361
About the Author 367
Index 369