Taranmış resimlerin vektör formatına dönüştürülmesi

Abstract

Çizimdeki benek desenlerin, doğru parçalarına, yaylara, bileşik çizgilere, çemberlere ve uygun spline eğriler gibi temel geometrik nesnelere dönüştürülmesine vektörleştirme denmektedir. Bu işlem sonucunda ulaşılan resim temsili, noktasal resim temsilinden genellikle çok daha derlitopiudur. Fakat elde edilen nesnelerin sınırlarında mevcut küçük düzensizlikler gibi bazı bilgiler, yok edilebilirler. Bir mühendislik çiziminin, kâğıtta çizili olmasından ziyade elektronik ortamda bilgisayar destekli tasanm (BDT) formatında bulunmasının birçok getirişi vardır BDT çizimlerinin üzerinde değişikliklerin yapılması daha kolaydır, kopyalarının çıkarılması ve yeniden çizilmeleri daha hızlıdır, üzerlerinden bilgi çıkarmak daha kolaydır ve genel olarak çizimlerin yönetilmesi daha kolaydır. Buna rağmen günümüzde etkin olarak kullanılan ve üretilen mühendislik çizimlerinin çoğu, hâlâ sadece kâğıt üzerindedir. Maliyet-kâr analizleri göstermiştir ki, bir çizimin bir kaç kere düzenleneceği ihtimali varsa o çizimin, kâğıt üzerinde çizilmesinden ziyade elektronik ortamda oluşturulması, oldukça avantaj sağlamaktadır. Vektörleştirme işlemi, sadece mühendislik çizimlerinin noktasal formattan vektöre! formata dönüştürülmesi için kullanılmaz. Aynı zamanda şekil tanıma, şekil sınıflandırılması, nesnelerin geometrik testleri, serbest-el çizimlerinin yorumu gibi değişik alanlarda da vektörleştirme işleminden yararlanılmaktadır. Bu tezde ilk olarak vektörleştirme işlemindeki basamaklardan biri olan köşe tespiti üzerinde çalışılmıştır. Yedi adet köşe bulma algoritması sunulmuştur. Rosenfeld- Johnston, Rosenfeld-Weszka ve Medioni-Yasumoto köşe tespit yöntemleri de sunulmuştur. Bu köşe bulma yöntemlerinin, on sayısal kapalı eğri üzerindeki performans karşılaştırması yapılmıştır, ikinci olarak farklı, yeni bir vektörleştirme algoritması sunulmuştur. XI Kapalı bir sayısal eğri olan C, n adet tamsayı koordinattan oluşan aşağıdaki gibi bir küme kabul edilebilir. C = {i>=(W/),/ = l,-,»} (1) Burada Pi+V n modülüne göre Pt nin komşusudur. Bir sayısal eğrideki eğriliğin yüksek olduğu noktalar, köşe noktalan olacağı için genellikle köşe tespit yöntemleri ilk olarak herbir benek için eğrilik hesabına giderler. Daha sonra ikinci adımda köşe noktalanna karar verilmeğe çalışılır. Geliştirdiğimiz köşe bulma yöntemlerinden ilk beşi (Bartem, Moment, Spthr, Spmin, Sp3min), sayısal eğrinin ilgilenilen beneğindeki teğet doğrusunun bulunması esasına dayanır. Çünkü ardışık beneklerdeki teğetlerin eğimleri arasındaki fark, sayısal eğrinin o benekteki eğriliği kabul edilebilir. Hatmin adı verilen altıncı yöntem, bir hata fonksiyonuna göre sayısal eğriye bir parabol uydurur. Sayısal eğrinin ilgilenilen noktasındaki eğriliğinin parabolün aynı noktadaki eğriliği olduğu kabul edilir. Görüldüğü gibi geliştirilen ilk altı yöntemde ilk önce her benek için bir eğrilik değeri bulunmaya çalışılmış ve bu eğriliklerin belirtilen komşulukta maksimum olanlarına köşe noktaları denmiştir. LSQ adı verilen geliştirilen yedinci yöntemde ilgilenilen P, noktası için en küçük kareler yöntemi kullanılarak ü ve v vektörleri oluşturur, öndeki k adet benek, ü vektörünün oluşumu için arkadaki k adet benek, v vektörünün oluşumu için kullanılır. Her benek için oluşturulan bu iki vektörün skaler çarpımından hareketle cosa değeri bulunur. Her benek için bulunan cosa değerleri eğriliğin bir göstergesi kabul edilebilir. Dolayısıyla bir beneğin köşe olabilmesi için kendisine ait coşar değerinin lokal maksimum olması gerekecektir. «l-vl+«2-v2 cosa = ı " - /, (2) V«l2 + «22-Vvl2+v22 Uygulamalardan hareketle görülmüştür ki LSQ köşe tespit yöntemi gerçeğe en yakın sonuçları yermektedir. Dolayısıyla LSQ yöntemi, ilerideki geliştirmeler için tercih edilmektedir. XII Bu tezde köşe bulma yöntemleri üzerindeki çalışmalar tamamlandıktan sonra tesirli bir vektörleştirme işlemi sunulmuştur, özellikle mühendislik çizimlerinin (şimdilik sadece doğrulan içeren) sayısallaştırılmasıyla elde edilen noktasal formattaki resim verilerinin yorumu için bir algoritma tanımlanmıştır, önerilen algoritma beş basamaktan oluşun (1) sınır eğrlerin elde edilmesi, (2) sınır eğrilerdeki köşe tespiti, (3) komşulukların oluşturulması, (4) karşı karşıya komşulukların bitirilmesi ve (5) uç noktaların birleştirilmesi. Burada köşe tespiti için LSQ algoritması kullanılmıştır. Doğrular arasındaki ilişki bulunduktan sonra karşı karşıya olan komşu doğrular bulunur. Dördüncü adımda karşı karşıya komşuluğu olan sınır doğrulan, bir doğruya indirilir. Oluşan yeni doğruların uç noktaları üst üste olmayabilir. Bu yüzden son adım doğrulann uçlarında oluşan boşlukların giderilmesine yöneliktir. Sunulan vektörleştirme algoritması, inceltme adımını içermemektedir. Bu önemli bir üstünlüktür. Sonuçta inceltme kaynaklı karmaşıklık, yavaşlık ve istenmeyen yapay bozukluklar gibi problemler, safdışı edilmiş olur. Ayrıca önemli bir zaman tasarrufu da söz konusudur.

Vectorization converts certain pixel patterns on the drawing into basic geometric entities such as straight line segments, arcs, polylines, circles and possibly splines. The resulting representation is usually much more compact than the represantation of the raster image, but some information is discarded, such as small irregularities in the boundaries of the inferred entities There are many advantages in having engineering drawings in electronic computer-aided design (CAD) format rather than hard copy only: CAD drawings are easier to modify, faster to copy and retrieve, easier to extract information from, and, in general, easier to manage. Nevertheles, most engineering drawings in active use today, and most of those being produced, are still in hard copy format only. Cost-benefit analyses show that, if a drawing is expected to be modified several times, it is advantageous to convert them from hard copy to electronic format. Vectorization is not only for transformation from raster to vector form of engineering drawing, but also it is used in pattern recognition, pattern classification, geometrical testing of objects, interpretation of freehand drawings etc. In this thesis firstly corner detection, one of the steps in vectorization process, is studied. We present seven corner detection algorithms. Corner detectors considered here include Rosenfeld-Johnston comer detector, Rosenfeld-Weszka comer detector and Medioni-Yasumoto comer detector. We compare the performance of these algorithms using ten digital closed curves. Secondly a different vectorization algorithm is presented. Let the sequence of n integer-coordinate points describe a closed curve C, XIV c={/î=(W/y=ı,-,«} d) where PM is a neighbor of Pt (modulo ri). Since dominant points on a curve correspond to points of high curvature, the various existing dominant point detection algorithms first compute an estimate of the curvature at each point on the curve. Next, a two-stage procedure is applied to choose dominant points. First five (Bartem, Moment, Spthr, Spmin, Sp3min) of our developed seven dominant point detection algorithms are based on constructing the tangent line at the point (pixel) being interested of the digital curve. Because the curvature at each pixel on the digital curve is calculated from difference between the slopes of the tangent line at the successive pixels. In the sixth method called Hatmin a parabola is fitted according to the error function. The curvature of the parabola at point P, is considered as the curvature of digital curve at Pr In these six methods the pixels having the maximum slope change (curvature) at specified neighbourhood are called corner points. In our developed seventh method, called LSQ, for the interesting pixel Pt, vectors u and v are formed by least squares method. The front £ -pixels are considered to form vector ü and the back £ -pixels for vector v. For each pixel cosar, angle between these two vectors by scaler multiply, is calculated. The point Pt is a corner if cosa, is a local maximum. ul-vl+u2-v2 cosar = /., =r - /, (2) Vk12 + h22.Vv12+v22 From the application point of view, it is seen that the performance of the LSQ corner detector is closest to that of a human viewer. So the LSQ method is preferred for feature development. In this thesis after the completion of the corner detection techniques, an effective vectorization process is proposed. An algorithm for the interpretation of raster data acquired by digitizing especially engineering drawings (in line format for the present) is described. The proposed algorithm includes five steps; (1) obtaining border curves, (2) detecting corners of border curves, (3) forming neighbours, (4) XV finishing face to face neighbours and (5) connecting end points. Here, for corner detection LSQ comer detector is used. After finding the relation between the lines, face-to-face neighbour border lines are caught. In the fourth step, a line is constructed from each face-to-face neighbour border lines. These new lines' end points may not be coincide. Therefore the last step tries to get rid of these gaps. The proposed vectorization process does not include thinning. This is the most important advantage. As a result, the problems being caused by a thinning algorithm like creating unwanted artifacts, complexity and slowness is eliminated. Additionally a serious time saving is a matter of course.