Skip to main content

Architectures for Computer Vision: From Algorithm to Chip with Verilog

Architectures for Computer Vision: From Algorithm to Chip with Verilog

Hong Jeong

ISBN: 978-1-118-65919-9

Aug 2014

336 pages

Description

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.

Related Resources

About the Author xi

Preface xiii

Part One VERILOG HDL

1 Introduction 3

1.1 Computer Architectures for Vision 3

1.2 Algorithms for Computer Vision 6

1.3 Computing Devices for Vision 7

1.4 Design Flow for Vision Architectures 8

Problems 9

References 10

2 Verilog HDL, Communication, and Control 11

2.1 The Verilog System 11

2.2 Hello, World! 12

2.3 Modules and Ports 14

2.4 UUT and TB 17

2.5 Data Types and Operations 17

2.6 Assignments 20

2.7 Structural-Behavioral Design Elements 22

2.8 Tasks and Functions 25

2.9 Syntax Summary 27

2.10 Simulation-Synthesis 29

2.11 Verilog System Tasks and Functions 30

2.12 Converting Vision Algorithms into Verilog HDL Codes 33

2.13 Design Method for Vision Architecture 36

2.14 Communication by Name Reference 38

2.15 Synchronous Port Communication 40

2.16 Asynchronous Port Communication 44

2.17 Packing and Unpacking 50

2.18 Module Control 51

2.19 Procedural Block Control 55

Problems 61

References 62

3 Processor, Memory, and Array 63

3.1 Image Processing System 63

3.2 Taxonomy of Algorithms and Architectures 64

3.3 Neighborhood Processor 66

3.4 BP Processor 68

3.5 DP Processor 70

3.6 Forward and Backward Processors 73

3.7 Frame Buffer and Image Memory 74

3.8 Multidimensional Array 76

3.9 Queue 77

3.10 Stack 79

3.11 Linear Systolic Array 81

Problems 87

References 88

4 Verilog Vision Simulator 89

4.1 Vision Simulator 90

4.2 Image Format Conversion 91

4.3 Line-based Vision Simulator Principle 98

4.4 LVSIM Top Module 100

4.5 LVSIM IO System 102

4.6 LVSIM RAM and Processor 105

4.7 Frame-based Vision Simulator Principle 109

4.8 FVSIM Top Module 111

4.9 FVSIM IO System 112

4.10 FVSIM RAM and Processor 116

4.11 OpenCV Interface 122

Problems 125

References 128

Part Two VISION PRINCIPLES

5 Energy Function 131

5.1 Discrete Labeling Problem 132

5.2 MRF Model 132

5.3 Energy Function 135

5.4 Energy Function Models 136

5.5 Free Energy 138

5.6 Inference Schemes 139

5.7 Learning Methods 141

5.8 Structure of the Energy Function 142

5.9 Basic Energy Functions 144

Problems 147

References 147

6 Stereo Vision 151

6.1 Camera Systems 151

6.2 Camera Matrices 153

6.3 Camera Calibration 156

6.4 Correspondence Geometry 158

6.5 Camera Geometry 162

6.6 Scene Geometry 163

6.7 Rectification 165

6.8 Appearance Models 167

6.9 Fundamental Constraints 169

6.10 Segment Constraints 171

6.11 Constraints in Discrete Space 172

6.12 Constraints in Frequency Space 176

6.13 Basic Energy Functions 179

Problems 180

References 180

7 Motion and Vision Modules 183

7.1 3D Motion 184

7.2 Direct Motion Estimation 187

7.3 Structure from Optical Flow 188

7.4 Factorization Method 191

7.5 Constraints on the Data Term 192

7.6 Continuity Equation 197

7.7 The Prior Term 197

7.8 Energy Minimization 201

7.9 Binocular Motion 203

7.10 Segmentation Prior 205

7.11 Blur Diameter 205

7.12 Blur Diameter and Disparity 207

7.13 Surface Normal and Disparity 208

7.14 Surface Normal and Blur Diameter 209

7.15 Links between Vision Modules 210

Problems 212

References 213

Part Three VISION ARCHITECTURES

8 Relaxation for Energy Minimization 219

8.1 Euler–Lagrange Equation of the Energy Function 220

8.2 Discrete Diffusion and Biharminic Operators 224

8.3 SOR Equation 225

8.4 Relaxation Equation 226

8.5 Relaxation Graph 231

8.6 Relaxation Machine 234

8.7 Affine Graph 236

8.8 Fast Relaxation Machine 238

8.9 State Memory of Fast Relaxation Machine 240

8.10 Comparison of Relaxation Machines 242

Problems 243

References 244

9 Dynamic Programming for Energy Minimization 247

9.1 DP for Energy Minimization 247

9.2 N-best Parallel DP 254

9.3 N-best Serial DP 255

9.4 Extended DP 256

9.5 Hidden Markov Model 260

9.6 Inside-Outside Algorithm 265

Problems 273

References 274

10 Belief Propagation and Graph Cuts for Energy Minimization 277

10.1 Belief in MRF Factor System 278

10.2 Belief in Pairwise MRF System 280

10.3 BP in Discrete Space 283

10.4 BP in Vector Space 285

10.5 Flow Network for Energy Function 288

10.6 Swap Move Algorithm 291

10.7 Expansion Move Algorithm 295

Problems 299

References 300

Part Four VERILOG DESIGN

11 Relaxation for Stereo Matching 305

11.1 Euler–Lagrange Equation 305

11.2 Discretization and Iteration 307

11.3 Relaxation Algorithm for Stereo Matching 308

11.4 Relaxation Machine 309

11.5 Overall System 309

11.6 IO Circuit 312

11.7 Updation Circuit 314

11.8 Circuit for the Data Term 317

11.9 Circuit for the Differential 319

11.10 Circuit for the Neighborhood 320

11.11 Functions for Saturation Arithmetic 321

11.12 Functions for Minimum Argument 323

11.13 Simulation 324

Problems 325

References 326

12 Dynamic Programming for Stereo Matching 327

12.1 Search Space 327

12.2 Line Processing 330

12.3 Computational Space 331

12.4 Energy Equations 333

12.5 DP Algorithm 334

12.6 Architecture 337

12.7 Overall Scheme 338

12.8 FIFO Buffer 342

12.9 Reading and Writing 344

12.10 Initialization 345

12.11 Forward Pass 347

12.12 Backward Pass 352

12.13 Combinational Circuits 353

12.14 Simulation 355

Problems 358

References 358

13 Systolic Array for Stereo Matching 361

13.1 Search Space 361

13.2 Systolic Transformation 363

13.3 Fundamental Systolic Arrays 365

13.4 Search Spaces of the Fundamental Systolic Arrays 368

13.5 Systolic Algorithm 371

13.6 Common Platform of the Circuits 373

13.7 Forward Backward and Right Left Algorithm 375

13.8 FBR and FBL Overall Scheme 378

13.9 FBR and FBL FIFO Buffer 384

13.10 FBR and FBL Reading and Writing 387

13.11 FBR and FBL Preprocessing 388

13.12 FBR and FBL Initialization 389

13.13 FBR and FBL Forward Pass 391

13.14 FBR and FBL Backward Pass 394

13.15 FBR and FBL Simulation 395

13.16 Backward Backward and Right Left Algorithm 397

13.17 BBR and BBL Overall Scheme 400

13.18 BBR and BBL Initialization 406

13.19 BBR and BBL Forward Pass 407

13.20 BBR and BBL Backward Pass 410

13.21 BBR and BBL Simulation 412

Problems 414

References 415

14 Belief Propagation for Stereo Matching 417

14.1 Message Representation 418

14.2 Window Processing 420

14.3 BP Machine 421

14.4 Overall System 422

14.5 IO Circuit 425

14.6 Sampling Circuit 427

14.7 Circuit for the Data Term 429

14.8 Circuit for the Input Belief Message Matrix 431

14.9 Circuit for the Output Belief Message Matrix 434

14.10 Circuit for the Updation of Message Matrix 435

14.11 Circuit for the Disparity 436

14.12 Saturation Arithmetic 437

14.13 Smoothness 439

14.14 Minimum Argument 441

14.15 Simulation 442

Problems 443

References 444

Index 447