(49-6) 22 * << * >> * Russian * English * Content * All Issues

Constant Time Feature Matching for ID Document Type Identification with On-the-Fly Type Subset Selection
E.E. Limonova 1,2, A.V. Trusov 1,2,3, D.Z. Rybalko 2, N.S. Skoryukina 1,2, K.B. Bulatov 2

1 Federal Research Center "Computer Science and Control" of Russian Academy of Sciences,
119333, Russia, Moscow, Vavilova 44, kor. 2;
2 Smart Engines Service LLC,
117312, Russia, Moscow, pr. 60-letiya Oktyabrya 9;
3 Moscow Institute of Physics and Technology,
141701, Russia, Dolgoprudny, Institutskiy per. 9

 PDF, 2241 kB

DOI: 10.18287/COJ1758

Pages: 1061-1070.

Full text of article: English language.

Abstract:
Identity document recognition is becoming more and more common in our daily lives. As security measures and document standards improve, the number of documents that need to be recognized is also increasing. So, one of the essential tasks of identity document recognition systems is to identify the document type from thousands of possible variants. However, in many cases, we have supplementary information and can reduce a set of possible types on-the-fly to improve processing speed and quality. In this paper, we discuss ID document recognition with on-the-fly type subset selection. The main challenges in such a system are responding within a limited time and achieving computational and memory efficiency for subset handling. We propose a solution based on a feature-matching approach using binary keypoint descriptors and adjusted multi-index hashing, which uses two new heuristics to ensure a constant number of comparisons for each request. We experimentally evaluate this method on the MIDV-500 and MIDV-2019 datasets and demonstrate that it offers an excellent combination of accuracy, configuration time, and search time compared to commonly used hierarchical clustering, hierarchical navigable small-world graphs, multi-probe locality-sensitive hashing, and straightforward brute-force solutions.

Keywords:
identity documents, ID document classification, on-the-fly selection, descriptor matching, multi-index hashing, approximate nearest neighbors.

Citation:
Limonova EE, Trusov AV, Rybalko DZ, Skoryukina NS, Bulatov KB. Constant Time Feature Matching for ID Document Type Identification with On-the-Fly Type Subset Selection. Computer Optics 2026; 49(6): 1061-1070. DOI: 10.18287/COJ1758.

References:
  1. ICAO, Doc 9303, Machine Readable Travel Documents. Source: <https://www.icao.int/publications/pages/publication.aspx?docnum=9303> (Accessed on 27.06.2025).
  2. A. M. Awal, N. Ghanmi, R. Sicre, T. Furon, Complex Document Classification and Localization Application on Identity Document Images, in: ICDAR 2017, Vol. 1, 2017, pp. 426–431. DOI: 10.1109/ICDAR.2017.77.
  3. K. Bulatov, V. V. Arlazarov, T. Chernov, O. Slavin, D. Nikolaev, Smart IDReader: Document Recognition in Video Stream, in: ICDAR 2017, Vol. 6, 2017, pp. 39–44, DOI: 10.1109/ICDAR.2017.347.
  4. N. Skoryukina, V. V. Arlazarov, D. P. Nikolaev, Fast method of ID documents location and type identification for mobile and server application, in: ICDAR 2019, 2020, pp. 850–857, DOI: 10.1109/ICDAR.2019.00141.
  5. M. Norouzi, A. Punjani, D. J. Fleet, Fast Exact Search in Hamming Space With Multi-Index Hashing, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 2013, pp. 1107–1119, DOI: 10.1109/TPAMI.2013.231.
  6. V. V. Arlazarov, K. Bulatov, T. Chernov, V. L. Arlazarov, MIDV-500: A Dataset for Identity Document Analysis and Recognition on Mobile Devices in Video Stream, Computer Optics 43 (5) (2019) 818–824, DOI: 10.18287/2412-6179-2019-43-5-818-824.
  7. K. Bulatov, D. Matalov, V. V. Arlazarov, MIDV-2019: Challenges of the Modern Mobile-Based Document OCR, in: ICMV 2019, Vol. 11433, 2020, pp. 114332N1–114332N6, DOI: 10.1117/12.2558438.
  8. Q. Lv, W. K. Josephson, Z. Wang, M. Charikar, K. Li, Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search, in: Very Large Data Bases Conference, 2007.
  9. M. Muja, D. G. Lowe, Scalable Nearest Neighbor Algorithms for High Dimensional Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 2014, pp. 2227–2240, DOI: 10.1109/TPAMI.2014.2321376.
  10. Y. A. Malkov, D. A. Yashunin, Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs, IEEE transactions on pattern analysis and machine intelligence, 42 (4), 2018, pp. 824–836, DOI: 10.1109/TPAMI.2018.2889473.
  11. T. Nakai, K. Kise, M. Iwamura, Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval, in: Document Analysis Systems VII, 2006, pp. 541–552, DOI: 10.1007/11669487_48.
  12. P. Gomez-Krämer, K. Rouis, A. O. Diallo, M. Coustaty, Printed and scanned document authentication using robust layout descriptor matching, Multim. Tools Appl. 83 (2023), pp. 47477–47502, DOI: 10.1007/s11042-023-17021-1.
  13. S. Eskenazi, P. Gomez-Krämer, J.-M. Ogier, The Delaunay Document Layout Descriptor, in: Proceedings of the 2015 ACM Symposium on Document Engineering, 2015, pp.167–175, DOI: 10.1145/2682571.2797059.
  14. N. D. Moskin, K. A. Kulakov, A. A. Rogov, R. V. Abramov, Research the Stability of Decision Trees Using Distances on Graphs, Proceedings of the Instittute for Systems Analysis Russian Academy of Sciences (ISA RAS) 73 (1), 2023, pp. 94–100, DOI: 10.14357/20790279230111.
  15. E. Rublee, V. Rabaud, K. Konolige, G. R. Bradski, ORB: An efficient alternative to SIFT or SURF, 2011 International Conference on Computer Vision, 2011, pp. 2564–2571, DOI: 10.1109/ICCV.2011.6126544.
  16. I. Suárez, J. M. Buenaposada, L. Baumela, Revisiting Binary Local Image Description for Resource Limited Devices, IEEE Robotics and Automation Letters 6, 2021, pp. 8317–8324, DOI: 10.1109/LRA.2021.3107024.
  17. B. Fan, Q. Kong, T. Trzcinski, Z. Wang, C. Pan, P. V. Fua, Receptive Fields Selection for Binary Feature Description, IEEE Transactions on Image Processing 23, 2014, pp. 2583–2595, DOI: 10.1109/TIP.2014.2317981.
  18. M. Muja, D. G. Lowe, Fast Matching of Binary Features, 2012 Ninth Conference on Computer and Robot Vision, 2012, pp. 404–410, DOI: 10.1109/CRV.2012.60.
  19. D. Schlegel, G. Grisetti, HBST: A Hamming Distance Embedding Binary Search Tree for Feature-Based Visual Place Recognition, IEEE Robotics and Automation Letters 3, 2018, pp. 3741–3748, DOI: 10.1109/LRA.2018.2856542.
  20. D. Schlegel, G. Grisetti, Visual localization and loop closing using decision trees and binary features, 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2016, pp. 4616–4623, DOI: 10.1109/IROS.2016.7759679.
  21. B. Fan, Q. Kong, B. Zhang, H. Liu, C. Pan, J. Lu, Efficient nearest neighbor search in high dimensional hamming space, Pattern Recognit. 99, 2020, p. 107082, DOI: 10.1016/j.patcog.2019.107082.
  22. Y.-C. Liaw, M.-L. Leou, C.-M. Wu, Fast exact k nearest neighbors search using an orthogonal search tree, Pattern Recognition 43, 2010, pp. 2351–2358, DOI: 10.1016/j.patcog.2010.01.003.
  23. A. Lukoyanov, D. Nikolaev, I. Konovalenko, Modification of YAPE keypoint detection algorithm for wide local contrast range images, in: ICMV 2017, Vol. 10696, 2018, pp. 1069616–1–1069616–8, DOI: 10.1117/12.2310243.
  24. D. P. Matalov, E. E. Limonova, N. S. Skoryukina, V. V. Arlazarov, Memory effcient local features descriptor for identity document detection on mobile and embedded devices, IEEE Access 11, 2022, pp. 1104–1114, DOI: 10.1109/ACCESS.2022.3233463.
  25. D. V. Tropin, S. A. Ilyukhin, D. P. Nikolaev, V. V. Arlazarov, Approach for document detection by contours and contrasts, in: ICPR 2020, 2021, pp. 9689–9695, DOI: 10.1109/ICPR48806.2021.9413271.
  26. A. V. Trusov, E. E. Limonova, V. V. Arlazarov, Fast computation of RFD-like descriptors in four orientations, IEEE Access 11, 2023, pp. 19725–19740, DOI: 10.1109/ACCESS.2023.3249100.
  27. E. O. Rybakova, A. V. Trusov, E. E. Limonova, N. S. Skoryukina, K. B. Bulatov, D. P. Nikolaev, PESAC, the Generalized Framework for RANSAC-Based Methods on SIMD Computing Platforms, IEEE Access 11, 2023, pp. 82151–82166, DOI: 10.1109/ACCESS.2023.3301777.
  28. M. Douze, A. Guzhva, C. Deng, J. Johnson, G. Szilvasy, P.-E. Mazaré, M. Lomeli, L. Hosseini, H. Jégou, The Faiss library (2024).arXiv:2401.08281 .
  29. N. S. Skoryukina, E. A. Shalnova, V. V. Arlazarov, Method for Detecting False Responses of Localization and Identification Algorithms Using Global Features, ITiVS (4), 2023, pp. 28–36, DOI: 10.14357/20718632230403.
  30. A. de Sá Soares, R. B. das Neves Junior, B. L. D. Bezerra, BID dataset: a challenge dataset for document processing tasks, Conference on Graphics, Patterns and Images (SIBGRAPI), SBC, 2020, pp. 143–146.
  31. H. Guan, Y. Wang, L. Xie, S. Nag, R. Goel, N. E. N. Swamy, Y. Yang, C. Xiao, J. Prisby, R. Maciejewski, J. Zou, IDNet: A novel dataset for identity document analysis and fraud detection, arXiv preprint arXiv:2408.01690 (2024).

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20