A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans

Jegoon Ryu; Sei ichiro Kamata

doi:10.1007/978-3-031-02444-3_42

A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans

Jegoon Ryu^*, Sei ichiro Kamata

^*Corresponding author for this work

Graduate School of Information, Production and Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper proposes a novel distance measurement using multi-Hilbert scans for matching point patterns on images. A modified Hausdorff distance has been widely used for point pattern matching, recognition tasks, and evaluation of medical image segmentation. However, the computation cost increases sharply with the number of feature points or the increase of data sets. Multi-Hilbert Scanning Distance (MHSD) based on sets of one-dimensional points using Hilbert scans is introduced to overcome this problem. MHSD consists of a combination of four directional Hilbert scans and diagonally shifted Hilbert scans. The proposed method was tested on vehicle images and compared with Hausdorff distance, partial Hausdorff distance, and modified Hausdorff distance. Experimental results show that the proposed method outperforms the compared methods.

Original language	English
Title of host publication	Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers
Editors	Christian Wallraven, Qingshan Liu, Hajime Nagahara
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	562-574
Number of pages	13
ISBN (Print)	9783031024436
DOIs	https://doi.org/10.1007/978-3-031-02444-3_42
Publication status	Published - 2022
Event	6th Asian Conference on Pattern Recognition, ACPR 2021 - Virtual, Online Duration: 2021 Nov 9 → 2021 Nov 12

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13189 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Asian Conference on Pattern Recognition, ACPR 2021
City	Virtual, Online
Period	21/11/9 → 21/11/12

Keywords

Hausdorff distance (HD)
Hilbert scan
Modified Hausdorff distance (MHD)
Multi-Hilbert Scanning Distance (MHSD)
Point Pattern Matching (PPM)

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-031-02444-3_42

Cite this

Ryu, J., & Kamata, S. I. (2022). A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans. In C. Wallraven, Q. Liu, & H. Nagahara (Eds.), Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers (pp. 562-574). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13189 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-02444-3_42

A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans. / Ryu, Jegoon; Kamata, Sei ichiro.
Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers. ed. / Christian Wallraven; Qingshan Liu; Hajime Nagahara. Springer Science and Business Media Deutschland GmbH, 2022. p. 562-574 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13189 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ryu, J & Kamata, SI 2022, A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans. in C Wallraven, Q Liu & H Nagahara (eds), Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13189 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 562-574, 6th Asian Conference on Pattern Recognition, ACPR 2021, Virtual, Online, 21/11/9. https://doi.org/10.1007/978-3-031-02444-3_42

Ryu J, Kamata SI. A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans. In Wallraven C, Liu Q, Nagahara H, editors, Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2022. p. 562-574. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-02444-3_42

Ryu, Jegoon ; Kamata, Sei ichiro. / A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans. Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers. editor / Christian Wallraven ; Qingshan Liu ; Hajime Nagahara. Springer Science and Business Media Deutschland GmbH, 2022. pp. 562-574 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e3e853caf37842ad80298667805ffa31,

title = "A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans",

abstract = "This paper proposes a novel distance measurement using multi-Hilbert scans for matching point patterns on images. A modified Hausdorff distance has been widely used for point pattern matching, recognition tasks, and evaluation of medical image segmentation. However, the computation cost increases sharply with the number of feature points or the increase of data sets. Multi-Hilbert Scanning Distance (MHSD) based on sets of one-dimensional points using Hilbert scans is introduced to overcome this problem. MHSD consists of a combination of four directional Hilbert scans and diagonally shifted Hilbert scans. The proposed method was tested on vehicle images and compared with Hausdorff distance, partial Hausdorff distance, and modified Hausdorff distance. Experimental results show that the proposed method outperforms the compared methods.",

keywords = "Hausdorff distance (HD), Hilbert scan, Modified Hausdorff distance (MHD), Multi-Hilbert Scanning Distance (MHSD), Point Pattern Matching (PPM)",

author = "Jegoon Ryu and Kamata, {Sei ichiro}",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 6th Asian Conference on Pattern Recognition, ACPR 2021 ; Conference date: 09-11-2021 Through 12-11-2021",

year = "2022",

doi = "10.1007/978-3-031-02444-3_42",

language = "English",

isbn = "9783031024436",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "562--574",

editor = "Christian Wallraven and Qingshan Liu and Hajime Nagahara",

booktitle = "Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers",

}

TY - GEN

T1 - A Fast and Accurate Point Pattern Matching Algorithm Based on Multi-Hilbert Scans

AU - Ryu, Jegoon

AU - Kamata, Sei ichiro

PY - 2022

Y1 - 2022

N2 - This paper proposes a novel distance measurement using multi-Hilbert scans for matching point patterns on images. A modified Hausdorff distance has been widely used for point pattern matching, recognition tasks, and evaluation of medical image segmentation. However, the computation cost increases sharply with the number of feature points or the increase of data sets. Multi-Hilbert Scanning Distance (MHSD) based on sets of one-dimensional points using Hilbert scans is introduced to overcome this problem. MHSD consists of a combination of four directional Hilbert scans and diagonally shifted Hilbert scans. The proposed method was tested on vehicle images and compared with Hausdorff distance, partial Hausdorff distance, and modified Hausdorff distance. Experimental results show that the proposed method outperforms the compared methods.

AB - This paper proposes a novel distance measurement using multi-Hilbert scans for matching point patterns on images. A modified Hausdorff distance has been widely used for point pattern matching, recognition tasks, and evaluation of medical image segmentation. However, the computation cost increases sharply with the number of feature points or the increase of data sets. Multi-Hilbert Scanning Distance (MHSD) based on sets of one-dimensional points using Hilbert scans is introduced to overcome this problem. MHSD consists of a combination of four directional Hilbert scans and diagonally shifted Hilbert scans. The proposed method was tested on vehicle images and compared with Hausdorff distance, partial Hausdorff distance, and modified Hausdorff distance. Experimental results show that the proposed method outperforms the compared methods.

KW - Hausdorff distance (HD)

KW - Hilbert scan

KW - Modified Hausdorff distance (MHD)

KW - Multi-Hilbert Scanning Distance (MHSD)

KW - Point Pattern Matching (PPM)

UR - http://www.scopus.com/inward/record.url?scp=85130219485&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130219485&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-02444-3_42

DO - 10.1007/978-3-031-02444-3_42

M3 - Conference contribution

AN - SCOPUS:85130219485

SN - 9783031024436

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 562

EP - 574

BT - Pattern Recognition - 6th Asian Conference, ACPR 2021, Revised Selected Papers

A2 - Wallraven, Christian

A2 - Liu, Qingshan

A2 - Nagahara, Hajime

PB - Springer Science and Business Media Deutschland GmbH

T2 - 6th Asian Conference on Pattern Recognition, ACPR 2021

Y2 - 9 November 2021 through 12 November 2021

ER -