Occlusion Handling in Correlation-Based Matching
Mise en Correspondance par Corrélation avec Prise En Compte des Occultations
OPEN ACCESS
In binocular stereovision,the accuracy of the 3D reconstruction depends on the accuracy of matching results. Consequently,matching is an important task.Our first goal is to present a state of the art of matching methods.We define a generic and complete algorithm based on essential components to describe most of the matching methods. Occlusions are one of the most important difficulties and we also present a state of the art of methods dealing with occlusions.Finally,we propose matching methods using two correlation measures to take into account occlusions.The results highlight the best method that merges two disparity maps obtained with two different measures.
Résumé
En stéréovision binoculaire,la mise en correspondance est une étape cruciale pour réaliser la reconstruction 3D de la scène. De très nombreuses publications traitent ce problème. Ainsi,le premier objectif est de proposer un état de l'art des méthodes de mise en correspondance. Nous synthétisons cette étude en présentant un algorithme générique complet faisant intervenir des éléments constituants permettant de décrire les différentes étapes de la recherche de correspondances. Une des plus grandes difficultés,au cours de l'appariement,provient des occultations. C'est pourquoi le second objectif est de présenter un état de l'art des méthodes qui prennent en compte cette difficulté. Enfin,le dernier objectif est de présenter de nouvelles méthodes hybrides,dans le cadre des méthodes locales à base de corrélation. Nous nous appuyons sur l'utilisation de deux mesures de corrélation permettant de mieux prendre en compte le problème des occultations. Les résultats mettent en évidence la meilleure méthode qui consiste à fusionner deux cartes de disparités obtenues avec des mesures différentes.
Stereovision,matching,occlusions,correlation.
Mots clés
Stéréovision,mise en correspondance,occultations,corrélation.
[1] M. AGRAWAL et L. DAVIS, « Windowbased, discontinuity preserving stereo ». Dans IEEE CVPR, volume 1, pages 66-73, 2004.
[2] L. ALVAREZ, R. DERICHE, T. PAPADOPOULOS et J. SÁNCHEZ, « Symmetrical Dense Optical Flow Estimation with Occlusions Detection ». Dans ECCV, volume 1, pages 721-735, 2002.
[3] P. ANANDAN, « A Computational Framework and an Algorithm for the Measurement of Visual Motion ». IJCV, 2(3):283-310, 1989.
[4] X. ARMANGUÉ et J. SALVI, « Overall view regarding fundamental matrix estimation ». Image and Vision Computing, 21(2):205-220, 2003.
[5] P. ASCHWANDEN et W. GUGGENBÜL, Experimental results from a comparative study on correlation type registration algorithms. Dans W. Förstner et S. Ruwiedel, éditeurs, Robust computer vision: Quality of Vision Algorithms, pages 268-282. Wichmann, 1992.
[6] S. T. BARNARD, « Stochastic Stereo Matching over Scale ». IJCV, 3(1):17-32, 1989.
[7] P. N. BELHUMEUR et D. MUMFORD, « A bayesian Treatment of the Stereo Correspondence Problem Using Half-Occluded Regions ». Dans IEEE CVPR, pages 506-512, 1992.
[8] R. E. BELLMAN et S. E. DREYFUS, La programmation dynamique et ses applications. Dunod, 1962.
[9] D. N. BHAT et S. K. NAYAR, « Ordinal Measures for Image Correspondence ». IEEE TPAMI, 20(4):415-423, 1998.
[13] B. BOCQUILLON, S. CHAMBON et A. CROUZIL, « Segmentation semi-automatique en plans pour la génération de cartes denses de disparités ». Dans ORASIS, 2005. CDROM.
[14] A. BOVYRIN, V. ERUHIMOV, S. MOLINOV, V. MOSYAGIN et V. PISAREVSKY, « Fast and robust dense stereo correspondence by column segmentation ». Dans IEEE ICIP, volume 2, pages 1033-1036, 2003.
[15] Y. BOYKOV, O. VEKSLER et R. ZABIH, « Fast approximate energy minimization via graph cuts ». IEEE T-PAMI, 23(11):12221239, 2001.
[16] M. Z. BROWN, D. BURSCHKA et G. D. HAGER, « Advances in Computational Stereo ». IEEE T-PAMI, 25(8):993-1008, 2003.
[17] P. J. BURT et E. H. ADELSON, « The Laplacian Pyramid as a Compact Image Code ». IEEE T-Communications, 31(4):532-540, 1983.
[18] J. F. CANNY, « A computational approach to edge detection ». IEEE T-PAMI, 8(6):679-698, 1986.
[19] S. CHAMBON et A. CROUZIL, « Dense matching using correlation: new measures that are robust near occlusions ». Dans BMVC, volume 1, pages 143-152, 2003.
[20] S. CHAMBON et A. CROUZIL, « Mesures de corrélation pour des images couleur ». Trait. Signal, 21(6):635-659, 2004.
[21] S. CHAMBON et A. CROUZIL, « Towards correlation-based matching algorithms that are robust near occlusions ». Dans IEEE ICPR, volume 3, pages 20-23, 2004.
[22] H. CHEN et P. MEER, « Robust Regression with Projection Based M-estimators ». Dans IEEE ICCV, volume 2, pages 878-885, 2003.
[23] A. CROUZIL, « Perception du relief et du mouvement par analyse d’une séquence stéréoscopique d’images ». Thèse de doctorat, université Paul Sabatier, Toulouse III, 1997.
[24] A. CROUZIL, X. DESCOMBES et J.-D. DUROU, « A Multiresolution Approach for Shape from Shading Coupling Deterministic and Stochastic Optimization ». IEEE TPAMI, 25(11):1416-1421, 2003.
[25] A. CROUZIL, L. MASSIP-PAILHES et S. CASTAN, « A New Correlation Criterion Based on Gradient Fields Similarity ». Dans IEEE ICPR, volume 1, pages 632-636, 1996.
[26] L. S. DAVIS et A. ROSENFELD, « Cooperating processes for lowlevel vision: A survey ». Artificial Intelligence, 17(1-3):245-263, 1981.
[27] O. De JOINVILLE, G. MAILLET, H. MAÎTRE et M. ROUX, « Évaluation a priori de la qualité d’un MNS ». Dans ORASIS, pages 67-76, 2001.
[28] Y. DENG, Q. YANG, X. LIN et X. TANG, « A Symmetric PatchBased Correspondence Model for Occlusion Handling ». Dans IEEE ICCV, volume 2, pages 1316-1322, 2005.
[29] X. DESCOMBES, « Méthodes stochastiques en analyse d’image : des champs de Markov aux processus ponctuels marqués ». Habilitation à diriger des recherches, université de Nice-Sophia Antipolis, 2004.
[30] U. R. DHOND et J. K. AGGARWAL, « Stereo Matching in the Presence of Narrow Occluding Objects Using Dynamic Disparity Search ». IEEE T-PAMI, 17(7):719-724, 1995.
[31] G. EGNAL et R. P. WILDES, « Detecting Binocular HalfOcclusions: Empirical Comparisons of Five Approaches ». IEEE T-PAMI, 24(8):1127-1133, 2002.
[32] M. P. EKLUND et A. A. FARAG, « Robust correspondence methods for stereo vision ». Pattern Recognition and Artificial Intelligence, 17(7):1059-1079, 2003.
[33] P. FUA, « A parallel stereo algorithm that produces dense depth maps and preserves image features ». Machine Vision and Applications, 6(1):35-49, 1993.
[34] A. FUSIELLO,V. ROBERTOet E. TRUCCO,« Ecient Stereo with Multiple Windowing ». Dans IEEE CVPR, pages 858-863, 1997.
[35] D. GARCIA, « Mesures de formes et de champs de déplacements tridimensionnels par stéréo-corrélation d’images ». Thèse de doctorat, école des mines d’Albi, 2001.
[36] D. GEIGER, B. LADENDORF et A. YUILLE, « Occlusions and Binocular Stereo ». Dans IEEE ICIP, volume 14, pages 211-226, 1995.
[37] A. GHAFOOR, R. NAVEED IQBAL et S. SHOAD KHAN, « Image Matching Using Distance Transform ». Dans SCIA, pages 654-660, 2003.
[38] M. GONG,« Motion Estimation using Dynamic Programming with Selective Path Search ». Dans IEEE ICPR, volume 4, pages 203206, 2004.
[39] L. GOTTESFELD BROWN, « A Survey of Image Registration Techniques ». ACM Computing Surveys, 24(4):325-376, 1992.
[40] J. Y. GOULERMAS et P. LIATSIS, « A Collective-Based Adaptive Symbiotic Model for Surface Reconstruction in Area-Based Stereo ». IEEE T-EC, 7(5):482-502, 2003.
[41] K.-P. HAN, K.-W. SONG, E.-Y. CHUNG, S.-J. CHO et Y.-H. HA, « Stereo matching using genetic algorithm with adaptive chromosomes ». Pattern Recognition, 34(9):1729-1740, 2001.
[42] C. HARRIS et M. STEPHENS, « A Combined Corner and Edge Detector ». Dans Alvey Vision Conference, pages 147-151, 1988.
[43] R. I. HARTLEY, « Theory and Practice of Projective Rectification ». IJCV, 35(2):115-127, 1999.
[44] D. HASLER, L. SBAIZ, S. SÜSSTRUNK et M. VETTERLI. « Outlier Modelling in Image Matching ». IEEE T-PAMI, 25(3):301-315, 2003.
[45] H. HIRSCHMÜLLER, « Accurate and ecient stereo processing by semi-global matching and mutual information ». Dans IEEE CVPR, volume 2, pages 807-814, 2005.
[46] H. HIRSCHMÜLLER, P. R. INNOCENT et J. GARIBALDI, «Real-Time Correlation-Based Vision with Reduced Border Errors ». IJCV, 47(1-3):229-246, 2002.
[47] J. HOLLAND, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and, Artificial Intelligence. MIT Press, 1975.
[48] L. HONG et G. CHEN, « Segment-Based Stereo Matching Using Graph Cuts ». Dans IEEE CVPR, volume 1, pages 74-81, 2004.
[49] J. J. HOPFIELD, « Neural networks and physical systems with emergent collective computational abilities ». Proceedings of the National Academy of Sciences, 79:2254-2258, 1982.
[50] R. HORAUD et O. MONGA, Vision par ordinateur, outils fondamentaux. Traité des nouvelles technologies, série Informatique. Hermès, 1993.
[51] J. HU et P. SIY, « Stereo Correspondence through Multiple Constraint Neural Networks ». Dans IEEE ICNN, volume 2, pages 332-342, 1993.
[52] H. ISHIKAWA et D. GEIGER, « Occlusions, Discontinuities, and Epipolar Lines in Stereo ». Dans ECCV, volume 1, pages 232-248, 1998.
[53] C. V. JAWAHAR et P. J. NARAYANAN, « Generalised correlation for multi-feature correspondence». Pattern Recognition, 35(6):1303-1313, 2002.
[54] T. KANADE et M. OKUTOMI, « A Stereo Matching Algorithm with an Adaptive Window:Theory and Experiment ». IEEE TPAMI, 16(9):920-932, 1994.
[55] S. KANEKO, I. MURASE et S. IGARASHI, « Robust Image registration by Increment Sign Correlation ». Pattern Recognition, 35(10):2223-2234, 2002.
[56] C. KIM, K. M. LEE, B. T. CHOI et S. U. LEE, « A Dense Stereo Matching Using Two-Pass Dynamic Programming with Generalized Ground Control Points ». Dans IEEE CVPR, volume 2, pages 1075-1082, 2005.
[57] V. KOLMOGOROV et R. ZABIH, « Multicamera Scene Reconstruction via Graph Cuts ». Dans ECCV, volume 2, pages 8296, 2002.
[58] J. KOSTKOVÁ et R. SÁRA, Stratified Dense Matching for Stereopsis in Complex Scenes ». Dans BMVC, volume 1, pages 339- 348, 2003.
[59] Z. D. LAN, « Méthodes robustes en vision : application aux appariements visuels ». Thèse de doctorat, Institut National Polytechnique de Grenoble, 1997.
[60] G. Le BESNERAIS et H. ORIOT, « Disparity estimation for high resolution stereoscopic reconstruction using GNC approach ». Dans IEEE ICIP, volume 2, pages 594-597, 1998.
[61] S. H. LEE, Y. KANATSUGU et J.-I. PARK, « MAP-Based Stochastic Diffusion for Stereo Matching and Line Fields Estimation ». IJCV, 47(1-3):195-218, 2002.
[62] M. LHUILLIER et L. QUAN, « Robust Dense Matching Using Local ang Global Geometric Constraints ». Dans IEEE ICPR, volume 1, pages 968-972, 2000.
[63] J. L. LOTTIet G. GIRAUDON,« Correlation algorithm with adaptive window for aerial image in stereo vision ». Dans ESSRS Workshop, pages 2315-2325, 1994.
[64] D. G. LOWE, « Distinctive Image Features from Scale-Invariant Keypoints ». IJCV, 60(2):91-110, 2004.
[65] A. LUO et H. BURKHARDT, « An intensitybased cooperative bidirectional stereo matching with simultaneous detection of discontinuities and occlusions ». IJCV, 15(3):171- 188, 1995.
[66] R. MANDUCHI et C. TOMASI, « Distinctiveness Maps for Image Matching ». Dans ICIAP, pages 26-31, 1999.
[67] H. MAYER, « Analysis of Means to Improve Cooperative Disparity Estimation ». Dans ISPRS, pages 25-31, 2003.
[68] A. MONTANVERT, P. MEER et A. ROSENFELD, « Hierarchical Image Analysis Using Irregular Tessellations ». IEEE T-PAMI, 13(4):307-316, 1991.
[69] N. M. NASRABADI et C. Y. CHOO, « Hopfield Network for Stereo Vision Correspondence ». IEEE T-PAMI, 3(1):5-13, 1992.
[70] Y.-I. OHTA et T. KANADE, « Stereo by Intra- and Inter-Scanline Search Using 18 Dynamic Programming ». IEEE T-PAMI, 7(2):139-154, 1985.
[71] M. OKUTOMI et T. KANADE, « A Locally Adaptive Window For Signal Matching ». IJCV, 7(2):143-162, 1992.
[72] N. PAPARODITIS, M. CORD, M. JORDAN et J.-P. COCQUEREZ, « Building Detection and Reconstruction from Mid- and High-Resolution Aerial Imagery ». CVIU, 72(2):122142, 1998.
[73] J. P. PASCUAL STARINK et E. BACKER, « Finding point correspondences using simulated annealing ». Pattern Recognition, 28(2):231-240, 1995.
[74] J. PEARL, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, 1988.
[75] W. K. PRATT, Digital image processing. Wiley-Interscience Publication, 1978.
[76] C. RAO,A. GRITAI et M. SHAH, « Viewinvariant Alignment and Matching of Video Sequences ». Dans IEEE ICCV, volume 2, pages 939-945, 2003.
[77] P. J. ROUSSEEUW et C. CROUX, L1-Statistical Analysis and Related Methods. Dans Y. Dodge, éditeur, Explicit Scale Estimators with High Breakdown Point, pages 77-92. Elsevier, 1992.
[78] S. ROY et I. J. COX, « A Maximum-Flow Formulation of the Ncamera Stereo Correspondence Problem ». Dans IEEE ICCV, pages 492-499, 1998.
[79] H. SAITO et M. MORI, « Application of genetic algorithms to stereo matching of images ». Pattern Recognition Letters, 16(8):815821, 1995.
[80] D. SCHARSTEIN et R. SZELISKI, « A Taxomomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms ». IJCV, 47(1):7-42, 2002.
[81] P. SEITZ, « Using local orientational information as image primitive for robust object recognition ». Dans Visual Communication and Image Processing IV, volume SPIE-1199, pages 1630-1639, 1989.
[82] J. SHAO, « Generation of Temporally Consistent Multiple Virtual Camera Views from Stereoscopic Image Sequences ». IJCV, 47(2):171-180, 2002.
[83] J. SHEN et S. CASTAN, « An optimal linear operator for step edge detection ». CVGIP, 24(2):112-133, 1992.
[84] J. SHI et C. TOMASI, « Good features to track ». Dans IEEE CVPR, pages 593-600, 1994.
[85] M. SHIMIZU et M. OKUTOMI, « Sub-Pixel Estimation Error Cancellation on Area-Based Matching ». IJCV, 63(3):207-224, 2005.
[86] S. SMITH et J. BRADY, « SUSAN – a new approach to low level image processing ». IJCV, 23(1):45-78, 1997.
[87] C. SUN et S. PELEG, « Fast Panoramic Stereo Matching Using Cylindrical Maximum Surfaces ». IEEE T-SMC, 34(1):760-765, 2004.
[88] R. SZELISKI et D. SCHARSTEIN, « Symmetric Sub-Pixel Stereo Matching ». Dans ECCV, volume 2, pages 525-540, 2002.
[89] H. TAO, H. S. SAWHNWEY et R. KUMAR, « A Global Matching Framework for Stereo Computation ». Dans IEEE ICCV,volume 2, pages 532-539, 2001.
[90] M. F. TAPPEN et W. T. FREEMAN, « Comparison of Graph Cuts with Belief Propagation for Stereo, using Identical MRF Parameters ». Dans IEEE ICCV, volume 2, pages 900-907, 2003.
[91] Q. TIAN et M. N. HUHNS, « Algorithms for Subpixel Registration ». CVGIP, 35:220-233, 1986.
[92] P. H. S. TORR et A. CRIMINISI, « Dense stereo using pivoted dynamic programming ». Image and Vision Computing, 22(10):795-806, 2004.
[93] T. TUYTELAARS et L. Van GOOL, « Wide Baseline Stereo Matching based on Local,Anely Invariant Regions ». Dans BMVC, volume 1, pages 412-422, 2000.
[94] F. ULLAH, S. KANEKO et S. IGARASHI, « Orientation Code Matching For Robust Object Search ». IEICE Transactions on Information and Systems, E-84-D(8):999-1006, 2001.
[95] O. VEKSLER, « Efficient graph-based energy minimization methods in computer vision ». PhD thesis, Cornell University, États-Unis, 1999.
[96] L. WANG, S. B. KANG, H.-Y. SHUM et G. XU, « Cooperative segmentation and stereo using perspective space search ». Dans ACCV, pages 366-371, 2004. 1996.
[97] Y. WEI et L. QUAN, « Region-based Progressive Stereo Matching ». Dans IEEE CVPR, volume 1, pages 106-113, 2004.
[98] Y. WEISS et W. T. FREEMAN, « On the optimality of solutions of the maxproduct belief-propagation algorithm in arbitrary graphs ». IEEE T-IT, 47(2):736-744, 2001.
[99] J. WENG, N. AHUJA et T. S. HUANG, « Matching Two Perspective Views ». IEEE T-PAMI, 14(8):806-825, 1992.
[100] J. XIAO et M. SHAH, « Two-Frame Wide Baseline Matching ». Dans IEEE ICCV, volume 1, pages 603-609, 2003.
[101] Y. YANG, A. YUILLE et J. LU, « Local, Global, and Multilevel Stereo Matching ». Dans IEEE CVPR, pages 274-279, 1993.
[102] K.-J. YOON et I.-S. KWEON, « Locally Adaptive Support-Weight Approach for Visual Correspondence Search ». Dans IEEE CVPR, volume 2, pages 924-931, 2005.
[103] R. ZABIH et J. WOODFILL, « Nonparametric Local Transforms for Computing Visual Correspondence ». Dans ECCV, pages 151158, 1994.
[104] Y. ZHANG et C. KAMBHAMETTU, « Stereo Matching with Segmentation-based Cooperation ». Dans ECCV, volume 2, pages 556-571, 2002.
[105] Z. ZHANG, « Le problème de la mise en correspondance : l’état de l’art ». Rapport de recherche INRIA RR-2146, 1993.
[106] C. L. ZITNICK et T. KANADE, « A cooperative Algorithm for Stereo Matching and Occlusion Detection ». IEEE T-PAMI, 22(7):675-684, 2000.
[107] B. ZITOV et J. FLUSSER, « Image registration methods: A survey ». Image and Vision Computing, 21(11):977-1000, 2003.
[108] I. ZOGHLAMI,O. FAUGERASet R. DERICHE, « Traitement des occlusions pour la modification d’objet plan dans une séquence d’image ». Dans ORASIS, pages 93-103, 1996.