PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms
This paper focuses on the computational optimization of RANSAC. We describe the Parallel Efficient Sample Consensus (PESAC) framework that allows efficient utilization of SIMD extensions and provides memory locality due to a special way of storing the input sequence of correspondences and generating...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10207729/ |
| _version_ | 1797742973178347520 |
|---|---|
| author | Ekaterina O. Rybakova Anton V. Trusov Elena E. Limonova Natalya S. Skoryukina Konstantin B. Bulatov Dmitry P. Nikolaev |
| author_facet | Ekaterina O. Rybakova Anton V. Trusov Elena E. Limonova Natalya S. Skoryukina Konstantin B. Bulatov Dmitry P. Nikolaev |
| author_sort | Ekaterina O. Rybakova |
| collection | DOAJ |
| description | This paper focuses on the computational optimization of RANSAC. We describe the Parallel Efficient Sample Consensus (PESAC) framework that allows efficient utilization of SIMD extensions and provides memory locality due to a special way of storing the input sequence of correspondences and generating a batch of samples per one main loop iteration. It is inspired by the USAC framework and has a block structure capable of implementing most modern RANSAC-based methods. We enhance it with individual blocks of sample and model restrictors that are aimed at the rejection of “bad” samples and model hypothesis before time-consuming model computation and verification blocks. We also provide a detailed description implementing 2D homography estimation problem in PESAC and benchmark the running time on the MIDV-2020 dataset of identity documents. Comparing to naive implementation, we accelerated our framework by 122 times for the document classification task (with a 6% increase in accuracy) and by 18 times for document tracking (with a 46% decrease in tracking failure rate) by using both restrictors and vector processing. This version also outperformed a number of USAC implementations from OpenCV-4.6.0 in runtime and accuracy of estimation (3 times faster, 6% greater accuracy for the classification task, and 2 times faster, 33% lower failure rate for tracking if comparing with USAC_MAGSAC). |
| first_indexed | 2024-03-12T14:47:55Z |
| format | Article |
| id | doaj.art-7fb6ba744f38469fbba08b3eb4da4e0f |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-12T14:47:55Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-7fb6ba744f38469fbba08b3eb4da4e0f2023-08-15T23:00:42ZengIEEEIEEE Access2169-35362023-01-0111821518216610.1109/ACCESS.2023.330177710207729PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing PlatformsEkaterina O. Rybakova0https://orcid.org/0009-0002-7171-3721Anton V. Trusov1https://orcid.org/0000-0003-4084-4614Elena E. Limonova2Natalya S. Skoryukina3https://orcid.org/0000-0002-4210-8365Konstantin B. Bulatov4https://orcid.org/0000-0003-1644-5162Dmitry P. Nikolaev5https://orcid.org/0000-0001-5560-7668Department of Computational Mathematics, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaSmart Engines Service LLC, Moscow, RussiaThis paper focuses on the computational optimization of RANSAC. We describe the Parallel Efficient Sample Consensus (PESAC) framework that allows efficient utilization of SIMD extensions and provides memory locality due to a special way of storing the input sequence of correspondences and generating a batch of samples per one main loop iteration. It is inspired by the USAC framework and has a block structure capable of implementing most modern RANSAC-based methods. We enhance it with individual blocks of sample and model restrictors that are aimed at the rejection of “bad” samples and model hypothesis before time-consuming model computation and verification blocks. We also provide a detailed description implementing 2D homography estimation problem in PESAC and benchmark the running time on the MIDV-2020 dataset of identity documents. Comparing to naive implementation, we accelerated our framework by 122 times for the document classification task (with a 6% increase in accuracy) and by 18 times for document tracking (with a 46% decrease in tracking failure rate) by using both restrictors and vector processing. This version also outperformed a number of USAC implementations from OpenCV-4.6.0 in runtime and accuracy of estimation (3 times faster, 6% greater accuracy for the classification task, and 2 times faster, 33% lower failure rate for tracking if comparing with USAC_MAGSAC).https://ieeexplore.ieee.org/document/10207729/Homography estimationidentity documentimage matchinglocalizationRANSACrestrictors |
| spellingShingle | Ekaterina O. Rybakova Anton V. Trusov Elena E. Limonova Natalya S. Skoryukina Konstantin B. Bulatov Dmitry P. Nikolaev PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms IEEE Access Homography estimation identity document image matching localization RANSAC restrictors |
| title | PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms |
| title_full | PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms |
| title_fullStr | PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms |
| title_full_unstemmed | PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms |
| title_short | PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms |
| title_sort | pesac the generalized framework for ransac based methods on simd computing platforms |
| topic | Homography estimation identity document image matching localization RANSAC restrictors |
| url | https://ieeexplore.ieee.org/document/10207729/ |
| work_keys_str_mv | AT ekaterinaorybakova pesacthegeneralizedframeworkforransacbasedmethodsonsimdcomputingplatforms AT antonvtrusov pesacthegeneralizedframeworkforransacbasedmethodsonsimdcomputingplatforms AT elenaelimonova pesacthegeneralizedframeworkforransacbasedmethodsonsimdcomputingplatforms AT natalyasskoryukina pesacthegeneralizedframeworkforransacbasedmethodsonsimdcomputingplatforms AT konstantinbbulatov pesacthegeneralizedframeworkforransacbasedmethodsonsimdcomputingplatforms AT dmitrypnikolaev pesacthegeneralizedframeworkforransacbasedmethodsonsimdcomputingplatforms |