DOI: 10.1111/cgf.12178. Sparse Iterative Closest Point

10.1111/cgf.12178

Crossref journal-article

Wiley

Computer Graphics Forum (311)

Abstract

AbstractRigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.

Bibliography

Bouaziz, S., Tagliasacchi, A., & Pauly, M. (2013). Sparse Iterative Closest Point. Computer Graphics Forum, 32(5), 113â123. Portico.

Authors 3

Sofien Bouaziz (first)
Andrea Tagliasacchi (additional)
Mark Pauly (additional)

References 48 Referenced 384

10.1145/1360612.1360684
10.1561/2200000015
{'key': 'e_1_2_10_4_2', 'volume-title': 'Metric Space & Complex Analysis', 'author': 'Banerjee A. K A.', 'year': '2008'} / Metric Space & Complex Analysis by Banerjee A. K A. (2008)
BaeK.‐H. LichtiD. D.:Automated registration of unorganised point clouds from terrestrial laser scanners. InIn: International Archives of Photogrammetry and Remote Sensing Vol. XXXV Part B5 Proceedings of the ISPRS working group V/2(2004) pp.222–227. 2.
10.1109/34.121791
10.1561/2200000016
10.1017/CBO9780511804441
10.1109/LSP.2007.898300
ChamplebouxG. LavalleeS. SzeliskiR. BrunieL.:From accurate range imaging sensor calibration to accurate model‐based 3d object localization. InComputer Vision and Pattern Recognition(1992) pp.83–89. 3.
ChenY. MedioniG.:Object modeling by registration of multiple range images. InProc. of the IEEE Intern. conf. on Robotics and Automation(1991) pp.2724–2729. 3.
10.1016/S1077-3142(03)00009-2
10.1109/TIT.2005.862083
10.1016/j.imavis.2004.05.007
10.1109/MSP.2007.914731
ChartrandR. WohlbergB.:A Nonconvex Admm Algorithm for Group Sparsity With Sparse Groups.Submitted to IEEE ICASSP(2013). 4. (10.1109/ICASSP.2013.6638818)
ChartrandR. YinW.:Iteratively reweighted algorithms for compressive sensing. InICASSP(2008) pp.3869–3872. 6. (10.1109/ICASSP.2008.4518498)
10.1109/TSP.2010.2044837
10.1007/s001380050048
10.1145/355744.355745
10.1016/j.cagd.2009.09.001
10.1016/j.imavis.2003.09.004
GelfandN. MitraN. J. GuibasL. PottmannH.:Robust global registration.Computer Graphics Forum (Proc. of the EG/SIGGRAPH Symposium on Geometry processing)(2005) 197–206. 2.
{'key': 'e_1_2_10_24_2', 'first-page': '418', 'volume-title': 'Proc. of the European Conf. on Computer Vision', 'author': 'Granger S.', 'year': '2002'} / Proc. of the European Conf. on Computer Vision by Granger S. (2002)
HontaniH. MatsunoT. SawadaY.:Robust non‐rigid ICP using outlier‐sparsity regularization. InComputer Vision and Pattern Recognition(2012). 4. (10.1109/CVPR.2012.6247673)
10.1109/TPAMI.2010.223
10.1016/j.cad.2004.02.009
LiH. SumnerR. W. PaulyM.:Global correspondence optimization for non‐rigid registration of depth scans. InProc. of the EG/SIGGRAPH Symposium on Geometry processing(2008). 2.
10.1109/70.210797
MitraN. J. GelfandN. PottmannH. GuibasL.:Registration of Point Cloud Data from a Geometric Optimization Perspective.Computer Graphics Forum (Proc. of the EG/SIGGRAPH Symposium on Geometry processing)(2004) 22–31. 3. (10.1145/1057432.1057435)
10.1109/TSP.2012.2212015
10.1006/cviu.1995.1024
{'key': 'e_1_2_10_33_2', 'volume-title': 'Numerical optimization', 'author': 'Nocedal J.', 'year': '2006'} / Numerical optimization by Nocedal J. (2006)
ParikhN. BoydS.:Proximal Algorithms.Found. and Trends in Optimization(2013) to appear. 6 11.
PyzaraA. BylinaB. BylinaJ.:The influence of a matrix condition number on iterative methods convergence. InConf. on Comp. Science and Information Systems(2011) pp.459–464. 8.
PottmannH. HoferM.:Geometry of the squared distance function to curves and surfaces.Visualization and Mathematics III Springer(2003) 221–242. 3. (10.1007/978-3-662-05105-4_12)
10.1007/s11263-006-5167-2
10.1016/j.cviu.2004.04.002
PaulyM. MitraN. J. GiesenJ. GrossM. GuibasL. J.:Example‐based 3d scan completion. InProc. of the EG/SIGGRAPH Symposium on Geometry processing(2005). 2.
PulliK.:Multiview registration for large data sets. InProc. of 3DIM(1999) pp.160–168. 2.
RusinkiewiczS. LevoyM.:Efficient variants of the ICP algorithm.3‐D Digital Imaging and Modeling(2001) 145–152. 2 3 6 7 8.
{'key': 'e_1_2_10_42_2', 'volume': '2013', 'author': 'Rusinkiewicz S.', 'journal-title': 'Derivation of point to plane minimization'} / Derivation of point to plane minimization by Rusinkiewicz S.
SegalA. HaehnelD. ThrunS.:Generalized‐icp. InProc. of Robotics: Science and Systems (RSS)(2009) pp.26–27. 2. (10.15607/RSS.2009.V.021)
{'key': 'e_1_2_10_44_2', 'first-page': '1', 'volume-title': 'Trans. on Visualization and Computer Graphics', 'author': 'Tam G.', 'year': '2012'} / Trans. on Visualization and Computer Graphics by Tam G. (2012)
10.1016/S0167-8655(99)00055-0
TsinY. KanadeT.:A correlation‐based approach to robust point set registration. InIn ECCV(2004) pp.558–569. 3. (10.1007/978-3-540-24672-5_44)
10.1111/j.1467-8659.2011.01884.x
10.1145/2010324.1964972
10.1007/BF01427149

Dates

Type	When
Created	12 years ago (Aug. 19, 2013, 3:31 p.m.)
Deposited	1 year, 10 months ago (Oct. 15, 2023, 6:23 p.m.)
Indexed	4 days, 12 hours ago (Aug. 23, 2025, 9:51 p.m.)
Issued	12 years ago (Aug. 1, 2013)
Published	12 years ago (Aug. 1, 2013)
Published Online	12 years ago (Aug. 19, 2013)
Published Print	12 years ago (Aug. 1, 2013)

Funders 0

None

BibTeX

@article{Bouaziz_2013, title={Sparse Iterative Closest Point}, volume={32}, ISSN={1467-8659}, url={http://dx.doi.org/10.1111/cgf.12178}, DOI={10.1111/cgf.12178}, number={5}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Bouaziz, Sofien and Tagliasacchi, Andrea and Pauly, Mark}, year={2013}, month=aug, pages={113–123} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        24
      ]
    ],
    "date-time": "2025-08-24T01:51:05Z",
    "timestamp": 1756000265037
  },
  "reference-count": 48,
  "publisher": "Wiley",
  "issue": "5",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2013,
            8,
            19
          ]
        ],
        "date-time": "2013-08-19T00:00:00Z",
        "timestamp": 1376870400000
      },
      "content-version": "vor",
      "delay-in-days": 18,
      "URL": "http://onlinelibrary.wiley.com/termsAndConditions#vor"
    }
  ],
  "content-domain": {
    "domain": [
      "onlinelibrary.wiley.com"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2013,
        8
      ]
    ]
  },
  "abstract": "<jats:title>Abstract</jats:title><jats:p>Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at <jats:ext-link xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink:href=\"http://lgg.epfl.ch/sparseicp\">http://lgg.epfl.ch/sparseicp</jats:ext-link>.</jats:p>",
  "DOI": "10.1111/cgf.12178",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2013,
        8,
        19
      ]
    ],
    "date-time": "2013-08-19T19:31:38Z",
    "timestamp": 1376940698000
  },
  "page": "113-123",
  "update-policy": "http://dx.doi.org/10.1002/crossmark_policy",
  "source": "Crossref",
  "is-referenced-by-count": 384,
  "title": "Sparse Iterative Closest Point",
  "prefix": "10.1111",
  "volume": "32",
  "author": [
    {
      "given": "Sofien",
      "family": "Bouaziz",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Andrea",
      "family": "Tagliasacchi",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Mark",
      "family": "Pauly",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "311",
  "published-online": {
    "date-parts": [
      [
        2013,
        8,
        19
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_10_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/1360612.1360684"
    },
    {
      "key": "e_1_2_10_3_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1561/2200000015"
    },
    {
      "key": "e_1_2_10_4_2",
      "volume-title": "Metric Space & Complex Analysis",
      "author": "Banerjee A. K A.",
      "year": "2008"
    },
    {
      "key": "e_1_2_10_5_2",
      "unstructured": "BaeK.\u2010H. LichtiD. D.:Automated registration of unorganised point clouds from terrestrial laser scanners. InIn: International Archives of Photogrammetry and Remote Sensing Vol. XXXV Part B5 Proceedings of the ISPRS working group V/2(2004) pp.222\u2013227. 2."
    },
    {
      "key": "e_1_2_10_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/34.121791"
    },
    {
      "key": "e_1_2_10_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1561/2200000016"
    },
    {
      "key": "e_1_2_10_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1017/CBO9780511804441"
    },
    {
      "key": "e_1_2_10_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/LSP.2007.898300"
    },
    {
      "key": "e_1_2_10_10_2",
      "unstructured": "ChamplebouxG. LavalleeS. SzeliskiR. BrunieL.:From accurate range imaging sensor calibration to accurate model\u2010based 3d object localization. InComputer Vision and Pattern Recognition(1992) pp.83\u201389. 3."
    },
    {
      "key": "e_1_2_10_11_2",
      "unstructured": "ChenY. MedioniG.:Object modeling by registration of multiple range images. InProc. of the IEEE Intern. conf. on Robotics and Automation(1991) pp.2724\u20132729. 3."
    },
    {
      "key": "e_1_2_10_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S1077-3142(03)00009-2"
    },
    {
      "key": "e_1_2_10_13_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TIT.2005.862083"
    },
    {
      "key": "e_1_2_10_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.imavis.2004.05.007"
    },
    {
      "key": "e_1_2_10_15_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/MSP.2007.914731"
    },
    {
      "key": "e_1_2_10_16_2",
      "doi-asserted-by": "crossref",
      "unstructured": "ChartrandR. WohlbergB.:A Nonconvex Admm Algorithm for Group Sparsity With Sparse Groups.Submitted to IEEE ICASSP(2013). 4.",
      "DOI": "10.1109/ICASSP.2013.6638818"
    },
    {
      "key": "e_1_2_10_17_2",
      "doi-asserted-by": "crossref",
      "unstructured": "ChartrandR. YinW.:Iteratively reweighted algorithms for compressive sensing. InICASSP(2008) pp.3869\u20133872. 6.",
      "DOI": "10.1109/ICASSP.2008.4518498"
    },
    {
      "key": "e_1_2_10_18_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TSP.2010.2044837"
    },
    {
      "key": "e_1_2_10_19_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/s001380050048"
    },
    {
      "key": "e_1_2_10_20_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/355744.355745"
    },
    {
      "key": "e_1_2_10_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.cagd.2009.09.001"
    },
    {
      "key": "e_1_2_10_22_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.imavis.2003.09.004"
    },
    {
      "key": "e_1_2_10_23_2",
      "unstructured": "GelfandN. MitraN. J. GuibasL. PottmannH.:Robust global registration.Computer Graphics Forum (Proc. of the EG/SIGGRAPH Symposium on Geometry processing)(2005) 197\u2013206. 2."
    },
    {
      "key": "e_1_2_10_24_2",
      "first-page": "418",
      "volume-title": "Proc. of the European Conf. on Computer Vision",
      "author": "Granger S.",
      "year": "2002"
    },
    {
      "key": "e_1_2_10_25_2",
      "doi-asserted-by": "crossref",
      "unstructured": "HontaniH. MatsunoT. SawadaY.:Robust non\u2010rigid ICP using outlier\u2010sparsity regularization. InComputer Vision and Pattern Recognition(2012). 4.",
      "DOI": "10.1109/CVPR.2012.6247673"
    },
    {
      "key": "e_1_2_10_26_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TPAMI.2010.223"
    },
    {
      "key": "e_1_2_10_27_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.cad.2004.02.009"
    },
    {
      "key": "e_1_2_10_28_2",
      "unstructured": "LiH. SumnerR. W. PaulyM.:Global correspondence optimization for non\u2010rigid registration of depth scans. InProc. of the EG/SIGGRAPH Symposium on Geometry processing(2008). 2."
    },
    {
      "key": "e_1_2_10_29_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/70.210797"
    },
    {
      "key": "e_1_2_10_30_2",
      "doi-asserted-by": "crossref",
      "unstructured": "MitraN. J. GelfandN. PottmannH. GuibasL.:Registration of Point Cloud Data from a Geometric Optimization Perspective.Computer Graphics Forum (Proc. of the EG/SIGGRAPH Symposium on Geometry processing)(2004) 22\u201331. 3.",
      "DOI": "10.1145/1057432.1057435"
    },
    {
      "key": "e_1_2_10_31_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TSP.2012.2212015"
    },
    {
      "key": "e_1_2_10_32_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1006/cviu.1995.1024"
    },
    {
      "key": "e_1_2_10_33_2",
      "volume-title": "Numerical optimization",
      "author": "Nocedal J.",
      "year": "2006"
    },
    {
      "key": "e_1_2_10_34_2",
      "unstructured": "ParikhN. BoydS.:Proximal Algorithms.Found. and Trends in Optimization(2013) to appear. 6 11."
    },
    {
      "key": "e_1_2_10_35_2",
      "unstructured": "PyzaraA. BylinaB. BylinaJ.:The influence of a matrix condition number on iterative methods convergence. InConf. on Comp. Science and Information Systems(2011) pp.459\u2013464. 8."
    },
    {
      "key": "e_1_2_10_36_2",
      "doi-asserted-by": "crossref",
      "unstructured": "PottmannH. HoferM.:Geometry of the squared distance function to curves and surfaces.Visualization and Mathematics III Springer(2003) 221\u2013242. 3.",
      "DOI": "10.1007/978-3-662-05105-4_12"
    },
    {
      "key": "e_1_2_10_37_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/s11263-006-5167-2"
    },
    {
      "key": "e_1_2_10_38_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.cviu.2004.04.002"
    },
    {
      "key": "e_1_2_10_39_2",
      "unstructured": "PaulyM. MitraN. J. GiesenJ. GrossM. GuibasL. J.:Example\u2010based 3d scan completion. InProc. of the EG/SIGGRAPH Symposium on Geometry processing(2005). 2."
    },
    {
      "key": "e_1_2_10_40_2",
      "unstructured": "PulliK.:Multiview registration for large data sets. InProc. of 3DIM(1999) pp.160\u2013168. 2."
    },
    {
      "key": "e_1_2_10_41_2",
      "unstructured": "RusinkiewiczS. LevoyM.:Efficient variants of the ICP algorithm.3\u2010D Digital Imaging and Modeling(2001) 145\u2013152. 2 3 6 7 8."
    },
    {
      "key": "e_1_2_10_42_2",
      "volume": "2013",
      "author": "Rusinkiewicz S.",
      "journal-title": "Derivation of point to plane minimization"
    },
    {
      "key": "e_1_2_10_43_2",
      "doi-asserted-by": "crossref",
      "unstructured": "SegalA. HaehnelD. ThrunS.:Generalized\u2010icp. InProc. of Robotics: Science and Systems (RSS)(2009) pp.26\u201327. 2.",
      "DOI": "10.15607/RSS.2009.V.021"
    },
    {
      "key": "e_1_2_10_44_2",
      "first-page": "1",
      "volume-title": "Trans. on Visualization and Computer Graphics",
      "author": "Tam G.",
      "year": "2012"
    },
    {
      "key": "e_1_2_10_45_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0167-8655(99)00055-0"
    },
    {
      "key": "e_1_2_10_46_2",
      "doi-asserted-by": "crossref",
      "unstructured": "TsinY. KanadeT.:A correlation\u2010based approach to robust point set registration. InIn ECCV(2004) pp.558\u2013569. 3.",
      "DOI": "10.1007/978-3-540-24672-5_44"
    },
    {
      "key": "e_1_2_10_47_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1111/j.1467-8659.2011.01884.x"
    },
    {
      "key": "e_1_2_10_48_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/2010324.1964972"
    },
    {
      "key": "e_1_2_10_49_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01427149"
    }
  ],
  "container-title": "Computer Graphics Forum",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.wiley.com/onlinelibrary/tdm/v1/articles/10.1111%2Fcgf.12178",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.12178",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2023,
        10,
        15
      ]
    ],
    "date-time": "2023-10-15T22:23:15Z",
    "timestamp": 1697408595000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://onlinelibrary.wiley.com/doi/10.1111/cgf.12178"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2013,
        8
      ]
    ]
  },
  "references-count": 48,
  "journal-issue": {
    "issue": "5",
    "published-print": {
      "date-parts": [
        [
          2013,
          8
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1111/cgf.12178"
  ],
  "URL": "http://dx.doi.org/10.1111/cgf.12178",
  "relation": {},
  "ISSN": [
    "0167-7055",
    "1467-8659"
  ],
  "subject": [],
  "container-title-short": "Computer Graphics Forum",
  "published": {
    "date-parts": [
      [
        2013,
        8
      ]
    ]
  },
  "assertion": [
    {
      "value": "2013-08-19",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}