Architectures for Computer Vision

This book provides comprehensive coverage of 3D vision systems, from vision models and state-of-the-art algorithms to their hardware architectures for implementation on DSPs, FPGA and ASIC chips, and GPUs. It aims to fill the gaps between computer vision algorithms and real-time digital circuit implementations, especially with Verilog HDL design. The organization of this book is vision and hardware module directed, based on Verilog vision modules, 3D vision modules, parallel vision architectures, and Verilog designs for the stereo matching system with various parallel architectures. Provides Verilog vision simulators, tailored to the design and testing of general vision chips Bridges the differences between C/C++ and HDL to encompass both software realization and chip implementation; includes numerous examples that realize vision algorithms and general vision processing in HDL Unique in providing an organized and complete overview of how a real-time 3D vision system-on-chip can be designed Focuses on the digital VLSI aspects and implementation of digital signal processing tasks on hardware platforms such as ASICs and FPGAs for 3D vision systems, which have not been comprehensively covered in one single book Provides a timely view of the pervasive use of vision systems and the challenges of fusing information from different vision modules Accompanying website includes software and HDL code packages to enhance further learning and develop advanced systems A solution set and lecture slides are provided on the book's companion website The book is aimed at graduate students and researchers in computer vision and embedded systems, as well as chip and FPGA designers. Senior undergraduate students specializing in VLSI design or computer vision will also find the book to be helpful in understanding advanced applications.

This book provides comprehensive coverage of 3D vision systems, from vision models and state-of-the-art algorithms to their hardware architectures for implementation on DSPs, FPGA and ASIC chips, and GPUs. It aims to fill the gaps between computer vision algorithms and real-time digital circuit implementations, especially with Verilog HDL design. The organization of this book is vision and hardware module directed, based on Verilog vision modules, 3D vision modules, parallel vision architectures, and Verilog designs for the stereo matching system with various parallel architectures.* Provides Verilog vision simulators, tailored to the design and testing of general vision chips* Bridges the differences between C/C++ and HDL to encompass both software realization and chip implementation; includes numerous examples that realize vision algorithms and general vision processing in HDL* Unique in providing an organized and complete overview of how a real-time 3D vision system-on-chip can be designed* Focuses on the digital VLSI aspects and implementation of digital signal processing tasks on hardware platforms such as ASICs and FPGAs for 3D vision systems, which have not been comprehensively covered in one single book* Provides a timely view of the pervasive use of vision systems and the challenges of fusing information from different vision modules* Accompanying website includes software and HDL code packages to enhance further learning and develop advanced systems* A solution set and lecture slides are provided on the book's companion websiteThe book is aimed at graduate students and researchers in computer vision and embedded systems, as well as chip and FPGA designers. Senior undergraduate students specializing in VLSI design or computer vision will also find the book to be helpful in understanding advanced applications.

About the Author xiPreface xiiiPart One VERILOG HDL1 Introduction 31.1 Computer Architectures for Vision 31.2 Algorithms for Computer Vision 61.3 Computing Devices for Vision 71.4 Design Flow for Vision Architectures 8Problems 9References 102 Verilog HDL, Communication, and Control 112.1 The Verilog System 112.2 Hello, World! 122.3 Modules and Ports 142.4 UUT and TB 172.5 Data Types and Operations 172.6 Assignments 202.7 Structural-Behavioral Design Elements 222.8 Tasks and Functions 252.9 Syntax Summary 272.10 Simulation-Synthesis 292.11 Verilog System Tasks and Functions 302.12 Converting Vision Algorithms into Verilog HDL Codes 332.13 Design Method for Vision Architecture 362.14 Communication by Name Reference 382.15 Synchronous Port Communication 402.16 Asynchronous Port Communication 442.17 Packing and Unpacking 502.18 Module Control 512.19 Procedural Block Control 55Problems 61References 623 Processor, Memory, and Array 633.1 Image Processing System 633.2 Taxonomy of Algorithms and Architectures 643.3 Neighborhood Processor 663.4 BP Processor 683.5 DP Processor 703.6 Forward and Backward Processors 733.7 Frame Buffer and Image Memory 743.8 Multidimensional Array 763.9 Queue 773.10 Stack 793.11 Linear Systolic Array 81Problems 87References 884 Verilog Vision Simulator 894.1 Vision Simulator 904.2 Image Format Conversion 914.3 Line-based Vision Simulator Principle 984.4 LVSIM Top Module 1004.5 LVSIM IO System 1024.6 LVSIM RAM and Processor 1054.7 Frame-based Vision Simulator Principle 1094.8 FVSIM Top Module 1114.9 FVSIM IO System 1124.10 FVSIM RAM and Processor 1164.11 OpenCV Interface 122Problems 125References 128Part Two VISION PRINCIPLES5 Energy Function 1315.1 Discrete Labeling Problem 1325.2 MRF Model 1325.3 Energy Function 1355.4 Energy Function Models 1365.5 Free Energy 1385.6 Inference Schemes 1395.7 Learning Methods 1415.8 Structure of the Energy Function 1425.9 Basic Energy Functions 144Problems 147References 1476 Stereo Vision 1516.1 Camera Systems 1516.2 Camera Matrices 1536.3 Camera Calibration 1566.4 Correspondence Geometry 1586.5 Camera Geometry 1626.6 Scene Geometry 1636.7 Rectification 1656.8 Appearance Models 1676.9 Fundamental Constraints 1696.10 Segment Constraints 1716.11 Constraints in Discrete Space 1726.12 Constraints in Frequency Space 1766.13 Basic Energy Functions 179Problems 180References 1807 Motion and Vision Modules 1837.1 3D Motion 1847.2 Direct Motion Estimation 1877.3 Structure from Optical Flow 1887.4 Factorization Method 1917.5 Constraints on the Data Term 1927.6 Continuity Equation 1977.7 The Prior Term 1977.8 Energy Minimization 2017.9 Binocular Motion 2037.10 Segmentation Prior 2057.11 Blur Diameter 2057.12 Blur Diameter and Disparity 2077.13 Surface Normal and Disparity 2087.14 Surface Normal and Blur Diameter 2097.15 Links between Vision Modules 210Problems 212References 213Part Three VISION ARCHITECTURES8 Relaxation for Energy Minimization 2198.1 Euler-Lagrange Equation of the Energy Function 2208.2 Discrete Diffusion and Biharminic Operators 2248.3 SOR Equation 2258.4 Relaxation Equation 2268.5 Relaxation Graph 2318.6 Relaxation Machine 2348.7 Affine Graph 2368.8 Fast Relaxation Machine 2388.9 State Memory of Fast Relaxation Machine 2408.10 Comparison of Relaxation Machines 242Problems 243References 2449 Dynamic Programming for Energy Minimization 2479.1 DP for Energy Minimization 2479.2 N-best Parallel DP 2549.3 N-best Serial DP 2559.4 Extended DP 2569.5 Hidden Markov Model 2609.6 Inside-Outside Algorithm 265Problems 273References 27410 Belief Propagation and Graph Cuts for Energy Minimization 27710.1 Belief in MRF Factor System 27810.2 Belief in Pairwise MRF System 28010.3 BP in Discrete Space 28310.4 BP in Vector Space 28510.5 Flow Network for Energy Function 28810.6 Swap Move Algorithm 29110.7 Expansion Move Algorithm 295Problems 299References 300Part Four VERILOG DESIGN11 Relaxation for Stereo Matching 30511.1 Euler-Lagrange Equation 30511.2 Discretization and Iteration 30711.3 Relaxation Algorithm for Stereo Matching 30811.4 Relaxation Machine 30911.5 Overall System 30911.6 IO Circuit 31211.7 Updation Circuit 31411.8 Circuit for the Data Term 31711.9 Circuit for the Differential 31911.10 Circuit for the Neighborhood 32011.11 Functions for Saturation Arithmetic 32111.12 Functions for Minimum Argument 32311.13 Simulation 324Problems 325References 32612 Dynamic Programming for Stereo Matching 32712.1 Search Space 32712.2 Line Processing 33012.3 Computational Space 33112.4 Energy Equations 33312.5 DP Algorithm 33412.6 Architecture 33712.7 Overall Scheme 33812.8 FIFO Buffer 34212.9 Reading and Writing 34412.10 Initialization 34512.11 Forward Pass 34712.12 Backward Pass 35212.13 Combinational Circuits 35312.14 Simulation 355Problems 358References 35813 Systolic Array for Stereo Matching 36113.1 Search Space 36113.2 Systolic Transformation 36313.3 Fundamental Systolic Arrays 36513.4 Search Spaces of the Fundamental Systolic Arrays 36813.5 Systolic Algorithm 37113.6 Common Platform of the Circuits 37313.7 Forward Backward and Right Left Algorithm 37513.8 FBR and FBL Overall Scheme 37813.9 FBR and FBL FIFO Buffer 38413.10 FBR and FBL Reading and Writing 38713.11 FBR and FBL Preprocessing 38813.12 FBR and FBL Initialization 38913.13 FBR and FBL Forward Pass 39113.14 FBR and FBL Backward Pass 39413.15 FBR and FBL Simulation 39513.16 Backward Backward and Right Left Algorithm 39713.17 BBR and BBL Overall Scheme 40013.18 BBR and BBL Initialization 40613.19 BBR and BBL Forward Pass 40713.20 BBR and BBL Backward Pass 41013.21 BBR and BBL Simulation 412Problems 414References 41514 Belief Propagation for Stereo Matching 41714.1 Message Representation 41814.2 Window Processing 42014.3 BP Machine 42114.4 Overall System 42214.5 IO Circuit 42514.6 Sampling Circuit 42714.7 Circuit for the Data Term 42914.8 Circuit for the Input Belief Message Matrix 43114.9 Circuit for the Output Belief Message Matrix 43414.10 Circuit for the Updation of Message Matrix 43514.11 Circuit for the Disparity 43614.12 Saturation Arithmetic 43714.13 Smoothness 43914.14 Minimum Argument 44114.15 Simulation 442Problems 443References 444Index 447