Sınır çizgilerini uyuşturma yöntemi ile yerleştirme

Abstract

Sınır Çizgilerini Uyuşturma Yöntemi ile Yerleştirme Bu çalışmanın temel amacı, nesnelerin sınır çizgilerinin benzerliğinden yararlanarak iki boyutlu şekillerin yanyana yerleştirilmesi için bir yöntem geliştirmektir. Belirli bir geometrik şekle sahip olmayan ve üzerinde delikler olabilen şekillerin yanyana yerleştirilmeleri özellikle gören robot dizgelerinde ve deri konfeksiyonunda önemli bir problemdir. Bu nedenle yapılan çalışmada bu problemin çözümüne yönelik yöntem ve algoritmalar geliştirilmiş, ayrıca önerilen çözümler hazırlanan yazdım ile denenmiş ve doğrulanmıştır. Çalışmada, bilgisayarlı görüş dizgelerinde kullanılan yöntemlere benzer olarak, şekillere ilişkin verilerin görüntü bilgisi içeren bitmap dosyası şeklinde bulunduğu varsayılarak yapay veriler kullanılmıştır. Bu nedenle yapılan çalışmada bilgisayarlı görü ve tanıma amacıyla kullanılan yöntemlere yer verilmiştir. Geliştirilen yöntemin birinci adımında, şekillere ait sınır çizgileri görüntüden elde edilerek, sınırlar zincir kodu ile kodlanmaktadır. Bu adımda görüntü içinde bulunan bütün şekiller ayırt edilerek kodlanmakta ve birbirlerine göre konumlan belirlenmektedir. Yine birinci aşamada şekillerin birbirinden ayırt edilmesi ve sınırlarının kodlanmasına yönelik algoritmalar geliştirilmiştir. Bu adımda ayrıca şekillerin sınırlarında olabilecek kopuklukları bulan ve bulduğu kopukluğu birleştiren algoritmalar geliştirilmiştir. Geliştirilen yöntemin ikinci adımında, sınırlara ait zincir kodlarından yararlanarak şekillerin sınır çizgilerinin üzerinde olabilecek gürültülerin filtrelenmesi ve köşelerin, şekilleri en iyi karakterize eden özellikli olması nedeniyle köşe noktalarının bulunmasına yönelik algoritmalar geliştirilmiştir. Bu çalışmanın üçüncü adımında, şeklin sınırının eğriliklerinden yararlanarak elde edilen ve şekli karakterize eden veriler, sayı dizileri halinde düzenlenmiştir. Bu karakteristik bilgiler, dönme ve ötelemeden bağımsız olmaktadır. Bulunan köşe noktalan ve kenarların eğrilikleri için; köşenin eğriliği ve kenar uzunluğu ile doğru orantılı büyüklükte sıfir eğrilik değeri hesaplanarak bir diziye yerleştirilir. Böylece şekillerin sınırlan sayı dizileri haline çevrilir. Çalışmanın dördüncü adımında, sınır çizgilerinin benzer bölgeleri bulunmuştur. Benzeyen bölgelerin en çok benzeyeninden en az benzeyenine kadar hepsinin bulunması gereklidir. Bütün benzeyen bölgelerin bulunması için bu çalışmada "Bütün Uyuşanları Bul" adını verdiğimiz bir algoritma geliştirilmiştir. Bu bölgelerin çakışması için gerekli olan döndürme açısı ve öteleme miktarı en küçük kareler tekniği ile hesaplanmıştır. Elde edilen döndürme açısı ve öteleme miktarı için dönüşüm uygulanarak, yerleştirme gerçeklenmektedir. Geliştirilen yöntemin beşinci adımında ise, yerleştirme sonunda iki şeklin birbiriyle kesişip kesişmediği araştırılmaktadır. Bu amaç için poligonların kesişmesini sınayan genel amaçlı bir algoritma geliştirilmiştir. Eğer kesişme var ise diğer uyuşan bölge için aynı işlemler uygulanmaktadır. Bu adımda aynı zamanda deliklerin durumu da kontrol edilmektedir. Bu tez kapsamında geliştirilen yöntemler yerleştirme amacıyla kullanılacağı gibi şekillerin tanınması için de kullanılabilir. Uygulamaları konfeksiyon sanayinde, özellikle deri konfeksiyonunda ve gören robot dizgelerinde olabilecektir. Bu algoritmalar nesnelerin yüzeyleri kullanılarak üç boyutlu duruma genişletilebilir.

The main goal of this work is to develop a method for nesting of objects using similarity of shape contours. It is an important problem in robot vision and confection, specially leather industry for nesting objects that has no specific shapes and they include holes. So many algorithms have been developed in this study to solve this problem. At the same time algorithms which are developed in this study have been programmed in C language and tested at a personal computer. The method, which is used in this work, is similar to the computer vision techniques. Vision data which includes shape information is a bitmap file. It is assumed that the bitmap files contain shape information sensed by an electronic camera. The picture signals are filtered using image processing techniques. So, we have used the computer vision and pattern recognition methods in this study.. Primary operations which are developed and realized during this study are introduced as follows: 1. Two dimensional shapes are extracted from the image and determined their position ( Two dimensional scene analysis ). 2. Shape area and contour length are computed, and the existence of holes in the area is checked. 3. Shape contour and contour coding are traced by using chain codes. 4. Dominant points of shapes are computed by using chain codes and converted to polygonal form. 5. Curvature computing of corner points and edges of polygonal representation of shapes are converted into number strings. 6. Longest matching subcurves of two shapes are found by using curvature of contours. 7. Rotation angle and translation value are computed by using longest matching region. Then the new position of the shape is computed.. 8. Intersection of shapes are tested after nesting. If any intersection is detected, new transformation will be computed. In the first step of the method which is developed in our study is to detect and learn shape's position in the scene image file. Shapes, which is detected in scene are traced their contours and coded by Freeman's chain codes. At the same time the position of the detected shapes are placed in a binary tree which is named a "Relation Tree" by us. Data structures used in relation tree are presented as follows: XI typedef struct point { /* Screen coordinates of a pixel in picture */ int x; inty; }; typedef struct koordinat {/*Corner coordinates of shapes converted into Poligon forms */ point p; /* Each corner coordinates of shape */ unsigned int uz; /*Edge length of shape */ }; typedef struct ilag{ point p; /* Detected first pixel coordinate of shape*/ char sekno, dskn; /* Shape no and surrounded shape no */ int zincad,kosad; /* Chain code of shape contour and the number of corner points */ int nokad; /* Pixel numbers which are covered by shape contour */ char *zbas; /* first address of chain codes */ unsigned char *yzbas;/*The new chain codes obtained after filtering */ koordinat *pt; /* Corner coordinates of shape */ struct Hag *solsek; /* Left subtree of relation tree */ struct Hag *delik; /* Hole subtree of relation tree */ struct Hag *sagsek; /* Right subtree of relation tree */ }; Chain codes developed by Freeman [28] are used very frequently to represent shape contour. Chain codes which are given below modifies the direction from one pixel to another pixel. A closed curve which is defined with n integer coordinate points are given as C = {pi = (xi,yi),i=l,...,n} where, pi+1 is neighbor of p;. The Freeman chain codes of C curve consist of n vectors, Ci = Pi-lPi Each C; can be represented by an integer. / = 0,...,4or/ = 0,...,7 If the angle between the X-axis for each vector is equal to 1/2tc/, 4 elements chain code is obtained, but if the angle is equal to l/47t/, 8 elements chain code is obtained. In four direction chain codes (0 12 3) in order to go to neighboring pixel, tracer must turn 90°. Xll But, for eight direction chain codes (0 1 2 3 4 5 6 7) the tracer must turn 45°. Four and eight elements chain codes are presented in Figure- 1. The chain of C closed curve is defined as { c;, i = l,...,n} and c; = ci±n. -2k- ?*o i 3 11 3 Ş (a) (b) Figure- 1 Four and eight elements chain code It is presented that chain codes which is coded eight elements codes at Figure-2 (56557660001 122235224) i 0 0 (D ı i L Figure-2 Contour and Chain codes coded in 8 elements chain codes. In this step, the shape contour is traced and placed in a relation tree. So all the shapes with holes are detected and extracted from the scene. This Shape Detecting Algorithm developed in this study is called "Find Shapes". Main operations of algorithm Find Shapes are explained as: 1. Read the image file and directly insert image data into graphics memory of computer. 2. Test the image pixel intensity level, line by line. 3. If a light pixel is found, search its coordinates in balanced tree. 4. If light pixel coordinate is found in balanced tree, search -the next light pixel on the same line. Insert the shape number and coordinate of two pixel into shape array, (this array will be used to compute area of shape and detecting of shape holes) xni 5. If light pixel coordinate is not found in balanced tree, this pixel may belong to shape contour. Then, trace the contour of shape using trace algorithm. 6. Draw the new shape using chain codes computed during tracing shape contour. Then insert shape specifications into relation tree. 7. Repeat step 2 to 6 for all images. Main operations of contour tracing algorithm developed in this study is presented in the following steps. 1. Take the first pixel coordinate found while contour tracing as beginning point. 2. Determine the pixel test direction according to tracing direction. 3. If there is a pixel on the pixel test direction - 1 ; * Chain code <- Pixel test direction -1,.» Compute the coordinate of new point using chain code, * Pixel test direction <- Pixel test direction -2; 4. If there is a pixel on the pixel test direction;.. Chain code <- Pixel test direction, * Compute the coordinate of new point using chain code, 5. If there is a pixel on the pixel test direction +1;.» Chain code «- Pixel test direction +1,.dik+1lik,fordik>0 djk'Wi ^ «Wi-Jik, for dj,, < 0 xv 3. Then the region of support of pj is a set of points which satisfy either condition (a) or condition ( b), D(Pi ) = {( Pi*-, Pi-i,-, P;.?...Pw.-.Pwt )l condition (a) or condition ( b)}. After having determined the region of support, we compute the new value of each points, using scale space filtering. Filter width is selected according to the region of support. So that if there is a noise on the curve it can be filtered adaptively. Because of the presentation of shape contour and quantization, some faulty dominant points can be detected. To filter such data, Gaussian filter is an ideal filter [30]. Gaussian filter is used as a filter for filtering shape contour. A planar curve can be defined in parametric form as follows: (x(t),y(t)) e il* Where; t, path length of the curve. Smoothing by a Gaussian filter is just convoluting x(t) and y(t) respectively, with a Gaussian distribution. One dimensional Gaussian distribution can be written as follows, h(t,(o) = - f=exp[-0.5(t/co)2] 0ÖV27C where, co is the width (spatial support) of the filter. The smoothed curve is denoted by the set of points: (X(t,a), Y(t,to) ) and "*" denotes convolution operator; X(t,co) = x(t) * h(t,o)= - \= f x(x)exp[-0.5((t-t)/o)2]dx ©V 271:1, Y(t,