Sınır çizgilerini uyuşturma yöntemi ile yerleştirme
Part nesting using contour matching
- Tez No: 46558
- Danışmanlar: PROF.DR. EŞREF ADALI
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Şekil kodlama sistemi, Şekil tanıma, Shape coding system, Shape recognition
- Yıl: 1995
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET 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.
Özet (Çeviri)
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: XItypedef 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°. XllBut, 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) xni5. 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,.<? Compute the coordinate of new point using chain code, 6. If any pixel is not found in step 3-4-5;.. Pixel test direction <- Pixel test direction + 2;.. Repeat three times from 3 to 5. 7. Test the pixel to see if there is a break point or not. 8. Insert new point with shape number into balanced tree. 9. If the new point is a breakpoint, find another breakpoint and connect the two points. 10. Put the new chain code to the end of the code list. 11. Repeat the step 2 to 10 until finding the first point. 12. Return. In the second step of the method developed by us, the dominant points of shape are found by using chain codes that are computed during the contour tracing. At the same time noise on the contour is filtered using scale space filtering. A dominant point or corner of the shape is a point that has higher curvature according to neighboring points. Curvature is basically defined as the rate of change of slope as a function of arc length. A curve C can be defined as C= { x(t),y(t) } in parametric form. where; t, path length of the curve; x(t), x coordinates of the curve at path length t; y(t), y coordinates of the curve at path length t;. xivCurvature for a planar curve at p point which is defined as the instantaneous rate of change of slope angle of the tangent, at point p with respect to path length t; dt E can be computed if the curve is expressed in terms of the derivatives of functions x(t) and y(t). For this reason first and second derivatives of y = /(x) function are defined as following;, dy“ d2y r = - - v = - dx ' y dx2 Curvature is known in terms of derivatives as e- r (l + (y')2)M A corner point should have the following properties:.< The corner point should have a view which constitutes a meaningful region of support of the curve.. The corner point should block the view from neighboring nondominant points. A support region developed by Teh-Chin [18] is determined using the following operations. 1. Determine the length of the cord, joining the points p;_k with pi+k as \k ~ I Pi-kP i+k let dfc be the perpendicular distance from the point Pj to the cord Pi_kpi+k 2. Start with k=l, compute 1^ and d^ until a) lac * Wi, or b)dikli,k+1>dik+1lik,fordik>0 djk'Wi ^ «Wi-Jik, for dj,, < 0 xv3. 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,<o) = y(t) * h(t,o) =- \= ]y(i:)exp[-0.5((t-T)/co)2]dT COV27Cİ so X and Y coordinates are computed once more. In our algorithm, spatial support of the filter is selected according to the support region of each point. So adaptive filtering operation is applied to shape contour. Then chain codes are computed again and dominant points are computed by using following suppressing strategy. xviFor each point compute curvature value using, CUR,,-!/»,-/,! where f{ is a chain code computed after Gaussian smoothing. * Find the largest curvature value in each support region of points. And suppress other points which has smaller curvature values points. * If the support region of p; is equal to 1, Either P;_, or pi+1 still remains. Then suppress the point with a smaller curvature value. The main steps of the Dominant Point Finding Algorithm which is developed in this study are explained as; 1. Compute all the support regions of contour points, using chain codes. 2. Compute the smoothing value of each point coordinates, using Gaussian filter, with filter support region width. Then, compute the new chain codes according to the smoothed point coordinates. 3. Compute the curvature values using the new chain codes for each contour points. 4. Repeat step 2 to 3 for all contour points. 5. Find the dominant points, using suppression strategy. (a) (b) The form of shape (a) after filtering (c) (d) The Form of shape (c) after filtering Figure-3 : Different shapes before and after filtering xvuThe noises on contour are filtered with scale space filtering. Thus, finding the probability of fake dominant points are lessen. Sample shapes filtered and detected dominant points with our methods are presented in Figure-3 In the third step of this study, the curvatures of dominant points and edges are computed and constructed as number strings. These strings computed in the third step are the signature of shape contour. The signature used for finding similarity of two shapes' contour is independent from shape position and orientation.. In the fourth step of the study, the similar segments are found between the two shapes. To find similar segments, shape signatures which are produced using curvatures of shape contour are used. So the problem of contour matching is changed into string matching problem. Two number strings produced in the third step, using curvatures of dominant points are matched and all similar substrings are found in the two number strings. Then these substrings are marked from the longest to shortest. The reason is that the new transformation should be computed if any intersection is found after nesting. In order to find all the matching substrings in the two number strings, an algorithm which is named ”Find All Matching“ is developed by us during this study. Our algorithm finds all matching substrings in the two strings with a minimum cost. At the same time the algorithm ”Find All Matching“ finds the matching substrings in the two strings so that, if one shape is reversed, the number string is produced inversely. Then the Find All Matching algorithm should find all matching substrings in these strings. So that the nesting of reversed shapes is guaranteed. Because of these properties of the Find All Matching algorithm, it is used to detect similarities of two shapes. Data structures which are used in our Find All Matching algorithm are presented as follows: typedef struct htbl{/* Data structure of Element Index and Equally Shifted Elements Tables */ int i; /* The Location of element in string AorB */ struct htbl *link; /* The next element */ }; typedef struct uyslst{ /* Data structure of matching substrings */ int il,i2; /* The locations of first elements of matching substrings */ struct uyslst *link; }; In the Find All Matching algorithm that we developed, hashing method is used and three hash tables are computed using the value of two siring elements. Let the two number string A contains n elements and B contains m elements (n > m). We want to figure out if there are matching substrings in the two strings or not. For this purpose, operations are explained as follows: xvm1. Create a hash table using the first string A. Each element of string indicates the index of the hash array. The element location of string A is stored in a hash table which is indicated by the value of string element. We named this table as ”Element Index“ table. 2. Create a hash table using string B and Element Index table which is produced in step 1. This table contains the following specifications... The index of the each element in the new table is pointed out by the sum or difference of index in the A and B string element which is matched..» Table element contains the element location matched in string B and string A. ? Table which is constructed in this step using all elements of string B and Element Index Table is called ”Equally Shifted Elements" table. 3. Compute the length of the matching substring and the location of the first matching element of each string by using the Equally Shifted Elements table. (a) Shapes with different positions (b) The positions of shapes in (a) after nesting Figure-4. The presentation of shapes before and after the application of our method. In this step, rotation angle and translation value are computed by using the longest matching region. The computation error of rotation angle and translation value is xixminimized using least square method. After the new position of the shape is computed, the new locations of two shapes are drawn. A sample application of our algorithm is presented in Figure-4. In the Figure-4 two shapes which are nested by our method is shown. In the last step of our method, the intersection of shapes are tested after nesting. If any intersection is detected, new transformation will be computed. A general purpose algorithm is developed to test the intersection of nested shapes. At the same time, the holes of shapes are controlled during the intersection test. Applications of our method is in the area of leather confection and robot vision. In addition, the methods which are developed in this thesis will be used for the recognition of shapes. Our techniques can be extended into three dimensions using the surface of the objects. xx
Benzer Tezler
- Etan molekülü spektrumundaki genişleme etkilerinin neural network yöntemi ile ortadan kaldırılması
Başlık çevirisi yok
NESRİN ÖZDENER
Yüksek Lisans
Türkçe
1991
Fizik ve Fizik MühendisliğiMarmara ÜniversitesiFizik Eğitimi Ana Bilim Dalı
PROF. DR. AHMET K. ATAKAN
- Turbomakinalarda akışın numerik metodlarla analizi
Analysis of flows in turbomachines with numerical methods
KEMAL SARIOĞLU
- İki parametreli elastik zemine oturan sonlu kiriş eleman için genel bir rijitlik matrisi ve tesir çizelgeleri
A General stiffness matrix and influence lines for beams resting on two parameter elastic foundation
MURAT MARMARA
- İki boyutlu yapısal olmayan ağların adaptasyonu
Adaptive remeshing on two dimensional unstructured meshes
SERDAR DİLAVER