IP Library Granted Patent US 12,340,556
Granted Patent B2
US 12,340,556 · App. 18/117,672 · Granted Jun 24, 2025

System and method for correspondence map determination

Inventors: Jason Devitt (Redwood City, CA); Haoyang Wang (Redwood City, CA); Konstantin Azarov (Redwood City, CA)
Assignee: Compound Eye, Inc.
G06V10/751G06N3/08G06V10/7715G06V10/82
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,340,556
App. No.
18/117,672
Granted
Jun 24, 2025
Kind
B2
Abstract

A system and method for determining a correspondence map between a first and second image by determining a set of correspondence vectors for each pixel in the first image and selecting a correspondence vector from the set of correspondence vectors based on a cost value.

Claims (13)

1. A method comprising:

determining a pixel hash for each pixel in a first image and each pixel in a second image;

determining a first correspondence map relating matching pixels in the first and second images by, for each of a set of pixels in the first image:

determining a set of correspondence vectors for the respective pixel based on correspondence vectors of neighboring pixels, wherein each correspondence vector identifies a corresponding pixel in the second image that is paired with the respective pixel; and

selecting a correspondence vector from the set of correspondence vectors based on a cost value determined between the pixel hashes of the paired pixels;

using a neural network to generate a second correspondence map with a greater number of correspondence vectors than the first correspondence map, wherein the neural network ingests the first correspondence map and at least one of the first or second image; and

determining a dense depth map based on the second correspondence map.

2. The method of claim 1 , wherein the set of correspondence vectors for an analysis pixel comprises each of:

an average correspondence vector between the correspondence vector of a right and left neighboring pixel of the analysis pixel; and

an average correspondence vector between the correspondence vector of a neighboring pixel above and a neighboring pixel below the analysis pixel.

3. The method of claim 1 , wherein the neural network is trained to fill gaps in the first correspondence map.

4. The method of claim 1 , wherein the first and second image are associated with a first and second timestamp, respectively, wherein the first and second timestamps are distinct.

5. The method of claim 1 , wherein at least one of the first or second correspondence map comprises an integer-accurate correspondence map, the method further comprising refining the integer-accurate correspondence map using a new pixel hash for each pixel in the first image and in the second image, wherein the new pixel hashes are distinct from the pixel hashes used to determine the integer-accurate correspondence map.

Assignments (2)
CORRECTIVE ASSIGNMENT TO CORRECT THE THE ASSIGNEE NAME PREVIOUSLY RECORDED AT REEL: 063082 FRAME: 0677. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNMENT. Recorded Jun 30, 2023
From: DEVITT, JASON; WANG, HAOYANG; AZAROV, KONSTANTIN
To: COMPOUND EYE, INC.
Reel/Frame 064185/0187 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 23, 2023
From: DEVITT, JASON; WANG, HAOYANG; AZAROV, KONSTANTIN
To: COMPOUND EYE, INC.
Reel/Frame 063082/0677 →
Continuity (5)
Continuation 17246235 · Apr 30, 2021
Continuation 17104898 · Nov 25, 2020
Provisional Application 63072897 · Aug 31, 2020
Provisional Application 62941397 · Nov 27, 2019
Related Publication 20230206594A1 · Jun 29, 2023
References Cited (140)
US 5692063A · Lee et al. · 1997 [cited by applicant]
US 5875264A · Carlstrom · 1999 [cited by applicant]
US 8036494B2 · Chen · 2011 [cited by applicant]
US 8639024B2 · Woodfill et al. · 2014 [cited by applicant]
US 8644620B1 · Lam · 2014 [cited by applicant]
US 9123118B2 · Ciurea et al. · 2015 [cited by applicant]
US 9338439B2 · Grossmann et al. · 2016 [cited by applicant]
US 9704250B1 · Shah et al. · 2017 [cited by applicant]
US 10339631B2 · Price et al. · 2019 [cited by applicant]
US 10528844B2 · Sugimura et al. · 2020 [cited by applicant]
US 10762655B1 · Lindskog et al. · 2020 [cited by applicant]
US 10764561B1 · Devitt · 2020 [cited by applicant]
US 10867190B1 · Vajna · 2020 [cited by examiner]
US 11030478B1 · Devitt et al. · 2021 [cited by applicant]
US 11069071B1 · Devitt et al. · 2021 [cited by applicant]
US 11270467B2 · Devitt et al. · 2022 [cited by applicant]
US 20020097912A1 · Kimmel et al. · 2002 [cited by applicant]
US 20040095999A1 · Piehl et al. · 2004 [cited by applicant]
US 20040240725A1 · Xu et al. · 2004 [cited by applicant]
US 20050140670A1 · Wu et al. · 2005 [cited by applicant]
US 20050275660A1 · Keller · 2005 [cited by applicant]
US 20070121998A1 · Stein · 2007 [cited by applicant]
US 20070146232A1 · Redert et al. · 2007 [cited by applicant]
US 20070229528A1 · Keller · 2007 [cited by applicant]
US 20080273751A1 · Yuan et al. · 2008 [cited by applicant]
US 20090037491A1 · Cachin et al. · 2009 [cited by applicant]
US 20100295926A1 · Estrada et al. · 2010 [cited by applicant]
US 20110206236A1 · Center · 2011 [cited by applicant]
US 20110273582A1 · Gayko et al. · 2011 [cited by applicant]
US 20120050488A1 · Cohen et al. · 2012 [cited by applicant]
US 20120250984A1 · Taylor · 2012 [cited by applicant]
US 20120306847A1 · Lim et al. · 2012 [cited by applicant]
US 20130266078A1 · Deligiannis et al. · 2013 [cited by applicant]
US 20140105499A1 · Shechtman et al. · 2014 [cited by applicant]
US 20140112572A1 · Reif et al. · 2014 [cited by applicant]
US 20140160247A1 · Shi et al. · 2014 [cited by applicant]
US 20150042766A1 · Ciurea et al. · 2015 [cited by applicant]
US 20150348273A1 · Chapiro et al. · 2015 [cited by applicant]
US 20160093056A1 · Ouzounis · 2016 [cited by applicant]
US 20160196654A1 · Aoki et al. · 2016 [cited by applicant]
US 20160267672A1 · Ciurea et al. · 2016 [cited by applicant]
US 20170161912A1 · Yoo et al. · 2017 [cited by applicant]
US 20170287169A1 · Garcia · 2017 [cited by applicant]
US 20170327127A1 · Simon · 2017 [cited by applicant]
US 20170343356A1 · Roumeliotis et al. · 2017 [cited by applicant]
US 20170374256A1 · Wagner · 2017 [cited by applicant]
US 20180018805A1 · Kutliroff et al. · 2018 [cited by applicant]
US 20180352213A1 · Valentin et al. · 2018 [cited by applicant]
US 20190007673A1 · Karvounis · 2019 [cited by applicant]
US 20190065868A1 · Tran et al. · 2019 [cited by applicant]
US 20190164040A1 · Naroditsky et al. · 2019 [cited by applicant]
US 20190180514A1 · Sasaki · 2019 [cited by applicant]
US 20190213746A1 · Azuma et al. · 2019 [cited by applicant]
US 20190279387A1 · Liu et al. · 2019 [cited by applicant]
US 20190297326A1 · Reda · 2019 [cited by examiner]
US 20190311485A1 · Buczko et al. · 2019 [cited by applicant]
US 20200082605A1 · Große · 2020 [cited by examiner]
US 20200084427A1 · Sun et al. · 2020 [cited by applicant]
US 20200186781A1 · Jannard et al. · 2020 [cited by applicant]
US 20200349846A1 · Siboni et al. · 2020 [cited by applicant]
US 20210021802A1 · Devitt · 2021 [cited by applicant]
US 20210065379A1 · Zhang et al. · 2021 [cited by applicant]
US 20210073953A1 · Lee · 2021 [cited by applicant]
US 20210225035A1 · Devitt et al. · 2021 [cited by applicant]
WO 2019079311A1 · 2019 [cited by applicant]
Sun, D., Yang, X., Liu, M. Y., & Kautz, J. (2019). Models matter, so does training: An empirical study of cnns for optical flow estimation. IEEE transactions on pattern analysis and machine intelligence, 42(6), 1408-142… [cited by examiner]
Jiang, W., Trulls, E., Hosang, J., Tagliasacchi, A., & Yi, K. M. (2021). Cotr: Correspondence transformer for matching across images. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 6207-… [cited by examiner]
Batsos, Konstantinos , et al., “RecResNet: A recurrent Residual CNN Architechture for Disparity Map Enhancement”, 2018 International Conference on 3D vision (3DV), IEEE, Sep. 5, 2018 (Sep. 5, 2018), pp. 238-247, XP03342… [cited by applicant]
Cyganek, Boguslaw, et al., “Image Matching Algorithms”, Jan. 1, 2008 (Jan. 1, 2008), An Introduction to 3D Computer Vision Techniques and Algorithms, Wiley, pp. 193-322, XP002698135, ISBN: 978-0-470-01704-3, * the whole… [cited by applicant]
Kellnhofer, Petr , et al., “Optimizing Disparity for Motion in Depth”, Computer Graphics Forum : Journal of the European Association for Computer Graphics, Wiley-Blackwell, Oxford, vol. 32, No. 4, Jul. 18, 2013 (Jul. 18… [cited by applicant]
Selzer, Jason Michael, “Desktop image-based rendering”, Jan. 1, 2007 (Jan. 1, 2007), XP93093151, Ottawa, Canada ISBN: 978-0-494-30020-6. [cited by applicant]
International Search Report and Written Opinion for Application No. PCT/US2021/014459 dated Jun. 22, 2021. [cited by applicant]
Podder et al. (“Evolution of Visual Odometry Techniques,” ARXIV (ID: 1804.11142), Apr. 30, 2018) (Year: 2018). [cited by applicant]
“Low-discrepancy sequence”, https://en.wikipedia.org/wiki/Low-discrepancy_sequence. [cited by applicant]
“Stereo Visual Odometry”, Viulib-Vicomtech Solutions, https://www.viulib.org/solutions/s5/stereo_visual_odometry. [cited by applicant]
Banz, C. , et al., “Evaluation of Penalty Functions for Semi-Global Matching Cost Aggregation”, Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci. 2012. [cited by applicant]
Banz, C. , et al., “Real-time stereo vision system using semi-global matching disparity estimation: Architecture and FPGA-implementation”, in 2010 International Conference on Embedded Computer Systems: (IEEE, 2010). [cited by applicant]
Baraldi, Patrizia , et al., “Motion and Depth from Optical Flow”, AVC 1989 doi:10.5244/C.3.35. [cited by applicant]
Barron, J.L. , et al., “Performance of Optical Flow Techniques”, IJCV 12:1, pp. 43-77, 1994. [cited by applicant]
Beall, Chris , “Stereo Visual Odometry”, CVPR 2014 Visual SLAM Tutorial, Georgia Tech, Institute for Robotics and Intelligent Machines. [cited by applicant]
Bleyer, M. , et al., “PatchMatch Stereo—Stereo Matching with Slanted Support Windows”, in Proceedings of the British Machine Vision Conference 2011 14.1-14.11 (British Machine Vision Association, 2011). doi:10.5244/C.25… [cited by applicant]
Bleyer, Michael , et al., “PatchMatch Stereo—Stereo Matching with Slanted Support Windows”, Patchmatch Stereo, 2011. [cited by applicant]
Bleyer, Michael , et al., “Stereo Matching—State-of-the-Art and Research Challenges”, In book: Advanced Topics in Computer Vision (pp. 143-179) Publisher: Springer, Jan. 2013. [cited by applicant]
Boukamcha, Hamdi , et al., “Robust auto calibration technique for stereo camera”, International Conference on Engineering & MIS (ICEMIS), Monastir, Tunisia, 2017, pp. 1-6, doi: 10.1109/ICEMIS.2017.8272992, https://ieeex… [cited by applicant]
Chang, J.R. , et al., “Pyramid Stereo Matching Network”, arXiv:1803.08669 [05] (2018). [cited by applicant]
Cormack, Lawrence K., et al., “Binocular Mechanisms of 3D Motion Processing”, https://www.ncbi.nlm.nih.gov/ pmc/articles/PMC5956901/. [cited by applicant]
Cvisic, Igor , et al., “Stereo odeemetry based on careful feature selection and tracking”, IEEE 2015, www.cvlibs.net/datasets/kitti/eval_odometry.php. [cited by applicant]
Dang, Thao , et al., “Continuous Stereo Self Calibration by Camera Parameter Tracking”, IEEE Transactions on Image Processing, vol. 18, No. 7, Jul. 2009. [cited by applicant]
Distler, Jonathan , “How to Know if Stereo Camera Lose Calibration”, https://www.foresightauto.com/how-to-know-if-stereo-cameras-lose-calibration/, Aug. 27, 2020. [cited by applicant]
Fucek, Luka , et al., “Dense Disparity Estimation in Ego-motion Reduced Search Space”, Computer Science, Engineering, ArXiv, published 2017, https://arxiv.org/pdf/1708.06301.pdf. [cited by applicant]
Geiger, A. , et al., “Efficient Large-Scale Stereo Matching. in Computer Vision”, ACCV 2010 (eds. Kimmel, R., Klette, R. & Sugimoto, A.) vol. 6492 25-38 (Springer Berlin Heidelberg, 2011). [cited by applicant]
Godard, C. , et al., “Unsupervised Monocular Depth Estimation with Left-Right Consistency”, arXiv:1609.03677 [cs,stat] (2017). [cited by applicant]
Hatzitheodorou, M. , et al., “Stereo Matching Using Optic Flow”, American College of Greece, 2000, Academic press, 16 pages. [cited by applicant]
Hemayed, Elsayed E., et al., “A Survey of Camera Self-Calibration”, Proceedings of the IEEE Conference on Advanced Video and Signal Based Surveillance, 2003. [cited by applicant]
Hirschmuller, H. , “Stereo Processing by Semiglobal Matching and Mutual Information”, IEEE Trans. Pattern Anal. Mach. Intell. 30, 328-341 (2008). [cited by applicant]
Hsiung, Jerry , et al., “Information Sparsification in Visual-Inertial Odometry”, Conference Paper, Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1146-1153, Oct. 2018. [cited by applicant]
Jonschkowski, Rico , et al., “What Matters in Unsupervised Optical Flow”, arXiv:2006.04902v2 [cs.CV] Aug. 14, 2020. [cited by applicant]
Kendall, A. , “End-to-End Learning of Geometry and Context for Deep Stereo Regression”, arXiv:1703.04309 [cs] (2017). [cited by applicant]
Kendall, Alex , et al., “End-to-End Learning of Geometry and Context for Deep Stereo Regression”, arXiv:1703.04309v1 [cs.CV] Mar. 13, 2017. [cited by applicant]
Knoblauch, Daniel , et al., “Factorization of Correspondence and Camera Error for Unconstrained Dense Correspondence Applications”, UC Davis, IDAV Publications, 2009. [cited by applicant]
Laga, H. , et al., “A Survey onDeep Learning Techniques for Stereo-based Depth Estimation”, arXiv:2006.02535 [cs] (2020). [cited by applicant]
Lai, Hsueh-Ying , et al., “Bridging Stereo Matching and Optical Flow via Spatiotemporal Correspondence”, 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 15-20, 2019, https://ieeexplore.i… [cited by applicant]
Lee, D.J. , et al., “Hardware Implementation of a Spline-Based Genetic Algorithm for Embedded Stereo Vision Sensor Providing Real-Time Visual Guidance to the Visually Impaired”, Eurasip J. Adv. Signal Process. 2008. [cited by applicant]
Marr, D. , et al., “Cooperative Computation of Stereo Disparity”, Science 194, 283-287 (1976). [cited by applicant]
Mentzer, Nico , et al., “Self-Calibration of Wide Baseline Stereo Camera System for Automative Applications”, In book: Towards a Common Software/Hardware Methodology for Future Advanced Driver Assistance Systems. The De… [cited by applicant]
Mourikis, Anastasios I., et al., “A Multi-State Constraint Kalman Filter for Vision-aided Inertial Navigation”, Proceedings 2007 IEEE International Conference on Robotics and Automation, Apr. 10-14, 2007, https://www-us… [cited by applicant]
Muhovic, Jon , et al., “Correcting Decalibration of Stereo Cameras in Self-Driving Vehicles”, Sensors 2020, 20,3241; doi:10.3390/s20113241, ww.mdpi.com/journal/sensors. [cited by applicant]
Nie, Y. , et al., “Adaptive rood pattern search for fast block-matching motion estimation”, IEEE Transactions on Image Processing (2002). [cited by applicant]
Ozuysal, Mustafa , “Manual and Auto Calibration of Stereo Camera Systems”, Thesis submitted to the Graduate School of Natural and Applied Sciences of Middle East Technical University, Aug. 2004. [cited by applicant]
Park, Jinsun , et al., “Non-Local Spatial Propagation Network for Depth Completion”, arXiv:2007.10042v1 [cs.CV] Jul. 20, 2020. [cited by applicant]
Poddar, Shashi , et al., “Evolution of Visual Odometry Techniques”, ARXIV (ID: 1804.11142), Apr. 30, 2018 (Year: 2018). [cited by applicant]
Psarakis, E.Z. , “An enhanced correlation-based method for stereo correspondence with subpixel accuracy”, in Tenth IEEE International Conference on Computer Vision, vol. 1, pp. 907-912. [cited by applicant]
Rabe, Clemens , et al., “Fast detection of moving objects in complex scenarios”, Proc. IEEE Symp. Intelligent Vehicles, Jun. 2007, (Year: 2007). [cited by applicant]
Rahnama, O. , et al., “Real-Time Dense Stereo Matching With ELAS on FPGA Accelerated Embedded Devices”, IEEE Robot. Autom. Lett. 3, 2008-2015 (2018). [cited by applicant]
Roberts, Richard , et al., “Learning general optical flow subspaces for egomotion estimation and detection of motion anomalies”, IEEE Conference on Computer Vision and Pattern Recognition, Jun. 20-25, 2009, (Year: 2009). [cited by applicant]
Rong, G. , et al., “Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams”, in Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering 176-181 (IEEE Computer S… [cited by applicant]
Rossi, M. , et al., “Joint Graph-Based Depth Refinement and Normal Estimation”, in 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition 12151-12160 (IEEE, 2020). [cited by applicant]
Scaramuzza, Davide , “Visual Odometry [Tutorial]”, IEEE Robotics & Automation Magazine, vol. 18, Is. 4, Dec. 2011) (Year: 2011). [cited by applicant]
Scaramuzza, Davide , et al., “Visual-Inertial Odometry of Aerial Robots”, Springer Encyclopedia of Robotics, 2019. [cited by applicant]
Scharstein, D. , “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms”, in Proceedings IEEE Workshop on Stereo and Multi-Baseline Vision (SMBV 2001) 131-140 (IEEE Comput. Soc, 2001). [cited by applicant]
Sivaraj, Hemanthkumar , et al., “Random Walk Based Heuristic Algorithms for Distributed Memory Model Checking”, Electronic Notes in Theoretical Computer Science 89, No. 1 (2003) 17 pages URL: http://elsevier.nl/locate/e… [cited by applicant]
Straub, J. , et al., “Fast Relocation for Visual Odometry Using Binary Features”, IEEE International Conference on Image Processing (ICIP), Sep. 2013, https://www.researchgate.net/publication/237048601_Fast_Relocalizati… [cited by applicant]
Sun, D. , et al., A Quantitative Analysis of Current Practices in Optical Flow Estimation and the Principles Behind Them, Int J Comput Vis 106, 115-137 (2014). [cited by applicant]
Talukder, Ashit , et al., “Real-time detection of moving objects from moving vehicles using dense stereo and optical flow”, IEEE/RSJ International Conference on Intelligent Robots and Systems, Sep. 28-Oct. 2, 2004, (Yea… [cited by applicant]
Tatsumi, S. , et al., “An FPGA accelerator for PatchMatch multi-view stereo using OpenCL”, J Real-Time Image Proc 17, 215-227 (2020). [cited by applicant]
Usenko, Vladyslav , et al., “Direct Visual-Inertial Odometry with Stereo Cameras”, 2016 IEEE International Conference on Robotics and Automation (ICRA), May 16-21, 2016, https://ieeexplore.ieee.org/document/7487335. [cited by applicant]
Zabih, R. , et al., “Non-parametric Local Transforms for Computing Visual Correspondence.”, in ECCV (1994). [cited by applicant]
Zhang, Tianguang , et al., “Visual odometry for the Autonomous City Explorer”, IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct. 10-15, 2009, (Year: 2009). [cited by applicant]
Zhuang, Hanqi , et al., “A self-calibration approach to extrinsic parameter estimation of stereo cameras”, Robotics and Autonomous Systems 15 (1995) 189-197. [cited by applicant]
“Triangulation (computer vision) Wikipedia”, https://en.wikipedia.org/wiki/Triangulation, first downloaded Jun. 8, 2023. [cited by applicant]
Cenek, Albl , et al., “From two rolling shutters to one global shutter”, CVPR 2020, Jun. 2, 2020. [cited by applicant]
Devitt, Jason , et al., “Systems and Method for Depth Determination”, U.S. Appl. No. 18/825,553, filed Sep. 5, 2024. [cited by applicant]
Im, Sunghoon , et al., “High Quality Structure from Small Motion for Rolling Shutter Cameras”, 2015 IEEE International Conference on Computer Vision. [cited by applicant]
Mo, Jiawei , et al., “Continuous-Time Spline Visual-Inertial Odometry”, arXiv:2109.09035 [cs.RO], Sep. 19, 2021. [cited by applicant]
Qu, Delin , et al., “Fast Rolling Shutter Correction in the Wild”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45 (10), pp. 1-18. 10.1109/TPAMI.2023.3284847. hal-04280534. [cited by applicant]
Saurer, Olivier , et al., “Rolling Shutter Stereo”, 2013 IEEE International Conference on Computer Vision, Dec. 1-8, 2013, Sydney, NSW, Australia, Mar. 3, 2014. [cited by applicant]
Schubert, David , et al., “Rolling-Shutter Modelling for Direct Visual-Inertial Odometry”, arXiv:1911.01015 [cs.CV], Nov. 4, 2019. [cited by applicant]
Wang, Ke , et al., “Relative Pose Estimation for Stereo Rolling Shutter Cameras”, arXiv:2006.07807 [cs.CV], Jun. 14, 2020. [cited by applicant]
Zhang, Ji , et al., “LOAM: Lidar Odometry and Mapping in Real-time”, Robotics: Science and Systems Conference Jul. 2014. [cited by applicant]
Zhuang, Bingbing , et al., “Learning Structure-And-Motion-Aware Rolling Shutter Correction”, Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 4551-4560. [cited by applicant]