Extended Attributed String Matching for Shape Recognition

Sei-Wang Chen, S. T. Tung, Chiung-Yao Fang, Shen Cherng, Anil K. Jain

Research output: Contribution to journalArticle

28 Citations (Scopus)

Abstract

In this paper, we extend the attributed string matching (ASM) technique, which originally dealt with single objects, to handle scenes containing multiple objects. The emerging issues have uncovered several weaknesses inherent in ASM. We overcome these weaknesses in this study. Major tasks include the introduction of an invariant two-way relaxation process with fuzzy split-and-merge mechanism, a new set of cost functions for edit operators, and the legality costs of edit operations. Three algorithms have been developed, respectively, implementing the original ASM, its modification (MASM) characterized by the proposed new cost functions, and extended ASM (EASM) further incorporating the legality costs of edit operations. These algorithms are then applied to a number of real images. By comparing their performances, we observe that both the new cost functions and the legality costs of edit operations have greatly enlarged the range of the computed similarity values. An augmentation in the separability of similarity values signifies an increment in the discernibility among objects. Experimental results support the applicability of the extended ASM

Original languageEnglish
Pages (from-to)36-50
Number of pages15
JournalComputer Vision and Image Understanding
Volume70
Issue number1
DOIs
Publication statusPublished - 1998 Jan 1

Fingerprint

Cost functions
Costs
Relaxation processes
Mathematical operators

Keywords

  • Attributed string matching
  • Dynamic programming
  • Fuzzy split and merge
  • Invariant two-way relaxation scheme
  • Legality costs of edit operations

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition

Cite this

Extended Attributed String Matching for Shape Recognition. / Chen, Sei-Wang; Tung, S. T.; Fang, Chiung-Yao; Cherng, Shen; Jain, Anil K.

In: Computer Vision and Image Understanding, Vol. 70, No. 1, 01.01.1998, p. 36-50.

Research output: Contribution to journalArticle

Chen, Sei-Wang ; Tung, S. T. ; Fang, Chiung-Yao ; Cherng, Shen ; Jain, Anil K. / Extended Attributed String Matching for Shape Recognition. In: Computer Vision and Image Understanding. 1998 ; Vol. 70, No. 1. pp. 36-50.
@article{ad8888d6549e4564a5656c87373072fc,
title = "Extended Attributed String Matching for Shape Recognition",
abstract = "In this paper, we extend the attributed string matching (ASM) technique, which originally dealt with single objects, to handle scenes containing multiple objects. The emerging issues have uncovered several weaknesses inherent in ASM. We overcome these weaknesses in this study. Major tasks include the introduction of an invariant two-way relaxation process with fuzzy split-and-merge mechanism, a new set of cost functions for edit operators, and the legality costs of edit operations. Three algorithms have been developed, respectively, implementing the original ASM, its modification (MASM) characterized by the proposed new cost functions, and extended ASM (EASM) further incorporating the legality costs of edit operations. These algorithms are then applied to a number of real images. By comparing their performances, we observe that both the new cost functions and the legality costs of edit operations have greatly enlarged the range of the computed similarity values. An augmentation in the separability of similarity values signifies an increment in the discernibility among objects. Experimental results support the applicability of the extended ASM",
keywords = "Attributed string matching, Dynamic programming, Fuzzy split and merge, Invariant two-way relaxation scheme, Legality costs of edit operations",
author = "Sei-Wang Chen and Tung, {S. T.} and Chiung-Yao Fang and Shen Cherng and Jain, {Anil K.}",
year = "1998",
month = "1",
day = "1",
doi = "10.1006/cviu.1998.0599",
language = "English",
volume = "70",
pages = "36--50",
journal = "Computer Vision and Image Understanding",
issn = "1077-3142",
publisher = "Academic Press Inc.",
number = "1",

}

TY - JOUR

T1 - Extended Attributed String Matching for Shape Recognition

AU - Chen, Sei-Wang

AU - Tung, S. T.

AU - Fang, Chiung-Yao

AU - Cherng, Shen

AU - Jain, Anil K.

PY - 1998/1/1

Y1 - 1998/1/1

N2 - In this paper, we extend the attributed string matching (ASM) technique, which originally dealt with single objects, to handle scenes containing multiple objects. The emerging issues have uncovered several weaknesses inherent in ASM. We overcome these weaknesses in this study. Major tasks include the introduction of an invariant two-way relaxation process with fuzzy split-and-merge mechanism, a new set of cost functions for edit operators, and the legality costs of edit operations. Three algorithms have been developed, respectively, implementing the original ASM, its modification (MASM) characterized by the proposed new cost functions, and extended ASM (EASM) further incorporating the legality costs of edit operations. These algorithms are then applied to a number of real images. By comparing their performances, we observe that both the new cost functions and the legality costs of edit operations have greatly enlarged the range of the computed similarity values. An augmentation in the separability of similarity values signifies an increment in the discernibility among objects. Experimental results support the applicability of the extended ASM

AB - In this paper, we extend the attributed string matching (ASM) technique, which originally dealt with single objects, to handle scenes containing multiple objects. The emerging issues have uncovered several weaknesses inherent in ASM. We overcome these weaknesses in this study. Major tasks include the introduction of an invariant two-way relaxation process with fuzzy split-and-merge mechanism, a new set of cost functions for edit operators, and the legality costs of edit operations. Three algorithms have been developed, respectively, implementing the original ASM, its modification (MASM) characterized by the proposed new cost functions, and extended ASM (EASM) further incorporating the legality costs of edit operations. These algorithms are then applied to a number of real images. By comparing their performances, we observe that both the new cost functions and the legality costs of edit operations have greatly enlarged the range of the computed similarity values. An augmentation in the separability of similarity values signifies an increment in the discernibility among objects. Experimental results support the applicability of the extended ASM

KW - Attributed string matching

KW - Dynamic programming

KW - Fuzzy split and merge

KW - Invariant two-way relaxation scheme

KW - Legality costs of edit operations

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

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

U2 - 10.1006/cviu.1998.0599

DO - 10.1006/cviu.1998.0599

M3 - Article

AN - SCOPUS:0032050368

VL - 70

SP - 36

EP - 50

JO - Computer Vision and Image Understanding

JF - Computer Vision and Image Understanding

SN - 1077-3142

IS - 1

ER -