Contour-based object recognition using attributed string matching

Abstract

oz ÖZNİTELİKLİ DİZGİ EŞLEME YÖNTEMİ KULLANARAK ÇEVRİT TABANLI NESNE TANIMA Kaygın, Serkan Doktora, Elektrik ve Elektronik Mühendisliği Bölümü Tez Yöneticisi: Doç. Dr. M. Mete Bulut Eylül 2001, 102 Sayfa İki ana yenilik içeren çok katmanlı modele dayalı iki boyutlu nesne tanıma metodu sunulmaktadır. Çalışmanın katkıları (i) iki seviyeli imgelerdeki şekil sınırlarını sezmek için kullanılan aktif zincir algoritması ve (ii) yeni bir şekil eşleme tekniği olan VASM'dır. Aktif zincir algoritması aktif çevrit modellerinden ilham almıştır. Aktif zincir, kapalı dört-bağlantılı zincir kodlu bir çevrit olarak başlatılır. Zincir daralır, bölünür ve imgedeki birden fazla sayıda nesnenin sınırını sarar. Aktif zincirin parametreleri gürültülü ya da kıpırtılı imgelerdeki hedef bölgeleri sezmek için ayarlanabilir. VASM algoritması, poligon köşe noktalarının temel öğe olarak kullanıldığı öznitelikli dizgi eşleme (ASM) metodudur. Öznitelikli dizginin temel yapısal birimleri olarak çizgi bölütleri yerine köşe noktalarının seçimi sayesinde ek bir hesaplama maliyeti olmadan birleştirme işlecinin avantaj lan kazanılmıştır. NxM boyutlarındaki bir imge için aktif zincir algoritmasının saklama yeri ihtiyacı ve hesaplama karmaşıklığı 0(MN)'dir. İmgedeki birden fazla nesne bir geçişte sezilir. Sezilmiş sınırlar zaten kapalı zincir kodu şeklinde oldukları içinfazladan çevirme, birleştirme ya da bağlama işlemine ihtiyaç kalmaz. Öte yandan VASM'da n ve m adet köşe sayışma sahip iki poligonun çevrimsel olmayan eşleme karmaşıklığı 0(nm)'dir. Aynı sonuç, birleştirme işlecine sahip çizgi bölütü tabanlı ASM metoduyla (XnW) sürede elde edilebilir. Anahtar Kelimeler: Nesne tanıma, Çevrit sezimi, Öznitelikli dizgi eşleme vı

ABSTRACT CONTOUR-BASED OBJECT RECOGNITION USING ATTRIBUTED STRING MATCHING Kaygın, Serkan Ph. D., Department of Electrical and Electronics Engineering Supervisor: Assoc. Prof. Dr. M. Mete Bulut September 2001, 102 Pages A multi-layer model-based 2D-object recognition method involving two main novelties is proposed. The contributions of the work are (i) the active chain algorithm used to detect shape boundaries in bi-level images, and (ii) a new shape matching technique, VASM. Active chain algorithm is inspired by the active contour models. It is initialized as a closed 4-connected chain coded contour. The chain shrinks, splits, and covers the boundaries of the multiple objects in the image. Parameters of the active chain can be configured to detect target regions in noisy or dithered images. VASM algorithm is an attributed string matching (ASM) method, where the polygon vertices are used as the primitives. By selecting the vertices instead of the line segments as the basic structural units of the attributed string, benefits of the merge operator are achieved without an extra computation cost. For an NxM image, space requirement and computational complexity of the active chain algorithm are both 0(MN). Multiple objects in the image are detected in one pass. Since the detected boundaries are already in closed chain mcoded form, no more conversions, merging, or linking are required. On the other hand, non-cyclic matching complexity of two polygons with n and m vertices in VASM is 0(nm). The same result can be achieved with line-segment based ASM methods with merge operator in OfaW) time. Keywords: Object recognition, Contour detection, Attributed string matching. IV