ARCHITECTURES FOR COMPUTER VISION From Algorithm to Chip with Verilog Hong Jeong ARCHITECTURES FOR COMPUTER VISION ARCHITECTURES FOR COMPUTER VISION FROM ALGORITHM TO CHIP WITH VERILOG HongJeong PohangUniversityofScienceandTechnology,SouthKorea Thiseditionfirstpublished2014 ©2014JohnWiley&SonsSingaporePte.Ltd. Registeredoffice JohnWiley&SonsSingaporePte.Ltd.,1FusionopolisWalk,#07-01SolarisSouthTower,Singapore138628. Fordetailsofourglobaleditorialoffices,forcustomerservicesandforinformationabouthowtoapplyfor permissiontoreusethecopyrightmaterialinthisbookpleaseseeourwebsiteatwww.wiley.com. AllRightsReserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystemortransmitted,in anyformorbyanymeans,electronic,mechanical,photocopying,recording,scanning,orotherwise,exceptas expresslypermittedbylaw,withouteitherthepriorwrittenpermissionofthePublisher,orauthorizationthrough paymentoftheappropriatephotocopyfeetotheCopyrightClearanceCenter.Requestsforpermissionshouldbe addressedtothePublisher,JohnWiley&SonsSingaporePte.Ltd.,1FusionopolisWalk,#07-01SolarisSouth Tower,Singapore138628,tel:65-66438000,fax:65-66438008,email:[email protected]. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsinprintmaynotbe availableinelectronicbooks. Designationsusedbycompaniestodistinguishtheirproductsareoftenclaimedastrademarks.Allbrandnamesand productnamesusedinthisbookaretradenames,servicemarks,trademarksorregisteredtrademarksoftheir respectiveowners.ThePublisherisnotassociatedwithanyproductorvendormentionedinthisbook.This publicationisdesignedtoprovideaccurateandauthoritativeinformationinregardtothesubjectmattercovered.Itis soldontheunderstandingthatthePublisherisnotengagedinrenderingprofessionalservices.Ifprofessionaladvice orotherexpertassistanceisrequired,theservicesofacompetentprofessionalshouldbesought. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbesteffortsinpreparing thisbook,theymakenorepresentationsorwarrantieswithrespecttotheaccuracyorcompletenessofthecontentsof thisbookandspecificallydisclaimanyimpliedwarrantiesofmerchantabilityorfitnessforaparticularpurpose.Itis soldontheunderstandingthatthepublisherisnotengagedinrenderingprofessionalservicesandneitherthe publishernortheauthorshallbeliablefordamagesarisingherefrom.Ifprofessionaladviceorotherexpert assistanceisrequired,theservicesofacompetentprofessionalshouldbesought. LibraryofCongressCataloging-in-PublicationData Jeong,Hong. Architecturesforcomputervision:fromalgorithmtochipwithVerilog/HongJeong. pagescm. Includesbibliographicalreferencesandindex. ISBN978-1-118-65918-2(cloth) 1.Verilog(Computerhardwaredescriptionlanguage) 2.Computervision. I.Title. II.Title:Fromalgorithmto chipwithVerilog. TK7885.7.J462014 621.39–dc23 2014016398 Setin9/11ptTimesbyAptaraInc.,NewDelhi,India 1 2014 Contents AbouttheAuthor xi Preface xiii PartOne VERILOGHDL 1 Introduction 3 1.1 ComputerArchitecturesforVision 3 1.2 AlgorithmsforComputerVision 6 1.3 ComputingDevicesforVision 7 1.4 DesignFlowforVisionArchitectures 8 Problems 9 References 10 2 VerilogHDL,Communication,andControl 11 2.1 TheVerilogSystem 11 2.2 Hello,World! 12 2.3 ModulesandPorts 14 2.4 UUTandTB 17 2.5 DataTypesandOperations 17 2.6 Assignments 20 2.7 Structural-BehavioralDesignElements 22 2.8 TasksandFunctions 25 2.9 SyntaxSummary 27 2.10 Simulation-Synthesis 29 2.11 VerilogSystemTasksandFunctions 30 2.12 ConvertingVisionAlgorithmsintoVerilogHDLCodes 33 2.13 DesignMethodforVisionArchitecture 36 2.14 CommunicationbyNameReference 38 2.15 SynchronousPortCommunication 40 2.16 AsynchronousPortCommunication 44 2.17 PackingandUnpacking 50 2.18 ModuleControl 51 2.19 ProceduralBlockControl 55 Problems 61 References 62 vi Contents 3 Processor,Memory,andArray 63 3.1 ImageProcessingSystem 63 3.2 TaxonomyofAlgorithmsandArchitectures 64 3.3 NeighborhoodProcessor 66 3.4 BPProcessor 68 3.5 DPProcessor 70 3.6 ForwardandBackwardProcessors 73 3.7 FrameBufferandImageMemory 74 3.8 MultidimensionalArray 76 3.9 Queue 77 3.10 Stack 79 3.11 LinearSystolicArray 81 Problems 87 References 88 4 VerilogVisionSimulator 89 4.1 VisionSimulator 90 4.2 ImageFormatConversion 91 4.3 Line-basedVisionSimulatorPrinciple 98 4.4 LVSIMTopModule 100 4.5 LVSIMIOSystem 102 4.6 LVSIMRAMandProcessor 105 4.7 Frame-basedVisionSimulatorPrinciple 109 4.8 FVSIMTopModule 111 4.9 FVSIMIOSystem 112 4.10 FVSIMRAMandProcessor 116 4.11 OpenCVInterface 122 Problems 125 References 128 PartTwo VISIONPRINCIPLES 5 EnergyFunction 131 5.1 DiscreteLabelingProblem 132 5.2 MRFModel 132 5.3 EnergyFunction 135 5.4 EnergyFunctionModels 136 5.5 FreeEnergy 138 5.6 InferenceSchemes 139 5.7 LearningMethods 141 5.8 StructureoftheEnergyFunction 142 5.9 BasicEnergyFunctions 144 Problems 147 References 147 6 StereoVision 151 6.1 CameraSystems 151 6.2 CameraMatrices 153 Contents vii 6.3 CameraCalibration 156 6.4 CorrespondenceGeometry 158 6.5 CameraGeometry 162 6.6 SceneGeometry 163 6.7 Rectification 165 6.8 AppearanceModels 167 6.9 FundamentalConstraints 169 6.10 SegmentConstraints 171 6.11 ConstraintsinDiscreteSpace 172 6.12 ConstraintsinFrequencySpace 176 6.13 BasicEnergyFunctions 179 Problems 180 References 180 7 MotionandVisionModules 183 7.1 3DMotion 184 7.2 DirectMotionEstimation 187 7.3 StructurefromOpticalFlow 188 7.4 FactorizationMethod 191 7.5 ConstraintsontheDataTerm 192 7.6 ContinuityEquation 197 7.7 ThePriorTerm 197 7.8 EnergyMinimization 201 7.9 BinocularMotion 203 7.10 SegmentationPrior 205 7.11 BlurDiameter 205 7.12 BlurDiameterandDisparity 207 7.13 SurfaceNormalandDisparity 208 7.14 SurfaceNormalandBlurDiameter 209 7.15 LinksbetweenVisionModules 210 Problems 212 References 213 PartThree VISIONARCHITECTURES 8 RelaxationforEnergyMinimization 219 8.1 Euler–LagrangeEquationoftheEnergyFunction 220 8.2 DiscreteDiffusionandBiharminicOperators 224 8.3 SOREquation 225 8.4 RelaxationEquation 226 8.5 RelaxationGraph 231 8.6 RelaxationMachine 234 8.7 AffineGraph 236 8.8 FastRelaxationMachine 238 8.9 StateMemoryofFastRelaxationMachine 240 8.10 ComparisonofRelaxationMachines 242 Problems 243 References 244 viii Contents 9 DynamicProgrammingforEnergyMinimization 247 9.1 DPforEnergyMinimization 247 9.2 N-bestParallelDP 254 9.3 N-bestSerialDP 255 9.4 ExtendedDP 256 9.5 HiddenMarkovModel 260 9.6 Inside-OutsideAlgorithm 265 Problems 273 References 274 10 BeliefPropagationandGraphCutsforEnergyMinimization 277 10.1 BeliefinMRFFactorSystem 278 10.2 BeliefinPairwiseMRFSystem 280 10.3 BPinDiscreteSpace 283 10.4 BPinVectorSpace 285 10.5 FlowNetworkforEnergyFunction 288 10.6 SwapMoveAlgorithm 291 10.7 ExpansionMoveAlgorithm 295 Problems 299 References 300 PartFour VERILOGDESIGN 11 RelaxationforStereoMatching 305 11.1 Euler–LagrangeEquation 305 11.2 DiscretizationandIteration 307 11.3 RelaxationAlgorithmforStereoMatching 308 11.4 RelaxationMachine 309 11.5 OverallSystem 309 11.6 IOCircuit 312 11.7 UpdationCircuit 314 11.8 CircuitfortheDataTerm 317 11.9 CircuitfortheDifferential 319 11.10 CircuitfortheNeighborhood 320 11.11 FunctionsforSaturationArithmetic 321 11.12 FunctionsforMinimumArgument 323 11.13 Simulation 324 Problems 325 References 326 12 DynamicProgrammingforStereoMatching 327 12.1 SearchSpace 327 12.2 LineProcessing 330 12.3 ComputationalSpace 331 12.4 EnergyEquations 333 12.5 DPAlgorithm 334 12.6 Architecture 337 12.7 OverallScheme 338