Real-Time Image and Video Processing: From Research to Reality
ABSTRACT
This book presents an overview of the guidelines and strategies for transitioning an image or video processing algorithm from a research environment into a real-time constrained environment.
Such guidelines and strategies are scattered in the literature of various disciplines including image processing, computer engineering, and software engineering, and thus have not previously appeared in one place. By bringing these strategies into one place, the book is intended to serve the greater community of researchers, practicing engineers, industrial professionals, who are interested in taking an image or video processing algorithm from a research environment to an actual real-time implementation on a resource constrained hardware platform.
These strategies consist of algorithm simplifications, hardware architectures, and software methods. Throughout the book, carefully selected representative examples from the literature are presented to illustrate the discussed concepts. After reading the book, the readers are exposed to a wide variety of techniques and tools, which they can then employ for designing a real-time image or video processing system of interest.
KEYWORDS
Real-time image and video processing, Real-time implementation strategies, Algorithmic simplifications for real-time image and video processing, Hardware platforms for real-time image and video processing, Software methods for real-time image and video processing.
Contents
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 1
1.2 Parallelism in Image/Video Processing Operations . . . . . . . . . . . . . . . . . . . . . . . .1
1.2.1 Low-Level Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Intermediate-Level Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
1.2.3 High-Level Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.2.4 Matrix–Vector Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Diversity of Operations in Image/Video Processing . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Definition of “Real-Time” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
1.4.1 Real-time in Perceptual Sense . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 Real-time in Software Engineering Sense . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.3 Real-time in Signal Processing Sense . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.4 Misinterpretation of Concept of Real-time . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.5 Challenges in Real-time Image/Video Processing . . . . . . . . . . . . . . . . . . . . 9
1.5 Historical Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9
1.5.1 History of Image/Video Processing Hardware Platforms . . . . . . . . . . . . . .9
1.5.2 Growth in Applications of Real-time Image/Video Processing . . . . . . . 11
1.6 Trade-Off Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 11
1.7 Chapter Breakdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 12
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Core Simplification Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 16
2.2.1 Reduction in Number of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
2.2.2 Reduction in Amount of Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.3 Simplified Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
2.3 Examples of Simplifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 19
2.3.1 Reduction in Number of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
2.3.2 Reduction of Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 Simple Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .31
3. Hardware Platforms for Real-Time Image and Video Processing . . . . . . . . . . . . . . . . 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Essential Hardware Architecture features . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 34
3.3 Overview of Currently Available processors . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1 Digital Signal Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.2 Field Programmable Gate Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
3.3.3 Multicore Embedded System-on-Chip . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.4 General-Purpose Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 39
3.3.5 Graphics Processing Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40
3.4 Example Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
3.4.1 DSP-Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.2 FPGA-Based Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
3.4.3 Hybrid Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.4 GPU-Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.5 PC-Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52
3.5 Revolutionary Technologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54
4. Software Methods for Real-Time Image and Video Processing . . . . . . . . . . . . . . . . . . 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Elements of Software Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.1 Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.2 Software Architecture Design . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 60
4.2.3 Real-time Operating System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
4.3 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
4.3.1 Memory Performance Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3.2 Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3.3 Organization of Image Data in Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.4 Spatial Locality and Cache Hits/Misses . . . . . . . . . . . . . . . . . . . . . . . . . . . .63
4.3.5 Memory Optimization Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63
4.4 Software Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.1 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.2 Compiler Optimization Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.3 Fixed-Point Versus Floating-Point Computations and Numerical Issues . . . . .67
4.4.4 Optimized Software Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
4.4.5 Precompute Information. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
4.4.6 Subroutines Versus In-Line Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4.7 Branch Predication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70
4.4.8 Loop Transformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70
4.4.9 Packed Data Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 Examples of Software Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .71
4.5.1 Software Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.2 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.3 Software Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
5.1 Recommended Road Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
About the Authors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .97
Preface
The relentless progression of Moore’s Law coupled with the establishment of international standards for digital multimedia has served as the catalyst behind the ubiquitous dissemination of digital information in our everyday lives in the form of digital audio, digital images, and more recently, digital video. Nowadays, entire music libraries can be stored on portable MP3 players, allowing listening to favorite songs wherever one goes. Digital cameras and camera-equipped cell phones are enabling easy capturing, storing, and sharing valuable moments through digital images and video. Set-top boxes are being used to pause, record, and stream live television signal over broadband networks to different locations, while smart camera systems are providing peace of mind through intelligent scene surveillance. Of course, all of these innovative multimedia products would not have materialized without efficient, optimized implementations of practical signal and image processing algorithms on embedded platforms, where constraints are placed not only on system size, cost, and power consumption, but also on the interval of time in which processed information must be made available.While digital audio processing presents its own implementation difficulties, the processing of digital images and video is challenging primarily due to the fact that vast amounts of data must be processed on platforms having limited computational resources, memory, and power consumption. Another challenge is that the algorithms for processing digital images and video are developed and prototyped on desktop PCs or workstations, which are considered to be, in contrast to portable embedded devices, resource unlimited platforms. Adding to this the fact that the vast majority of algorithms developed to process digital images and video are quite computationally intensive, one requires to resort to specialized processors, judicious trade-off decisions to reach an accepted solution, or even abandoning a complex algorithm for a simpler, less computationally complex algorithm. Noting that there are many competing hardware platforms with their own advantages and disadvantages, it is rather difficult to navigate the road from research to reality without some guidelines. Real - Time Image and Video Processing: From Research to Reality is intended to provide such guidelines and help bridge the gap between the theory and the practice of image and video processing by providing a broad overview of proven algorithmic, hardware, software tools and strategies.
This book is intended to serve the greater community of researchers, practicing engineers, and industrial professionals who deal with designing image and video processing systems and are asked to satisfy strict system design constraints on performance, cost, and power consumption.