Düzlemde etkin şekil yerleştirme programı tasarımı

Abstract

ÖZET Günümüz bilgisayar sistemleri, yüksek teknoloji desteğinde çok büyük yetenek ve verimlilik kazanmışlardır. Bunun doğal sonucu olarak bilgisayar destekli tasarım ve üretim tüm endüstri dallarına inanılması güç bir hızla gi rmektedir. Bilgisayarın tasarım ve üretim aşamalarında endüstride yer alması çok daha hızlı ve güvenilir ürün elde edilmesini sağlamaktadır. Bu aşamada ihtiyaçlar doğrultusunda iyi geliştirilmiş yazılım ve donanım sis temine gereksinim doğar. önemli endüstri dallarından biri olan deri işleme konusunda da yine hedeflenen deri parçalarının en uygun ve en az kayıp ile kullanımını sağlamaktır. Bu çalışmada yukarıda belirtilen hedef doğrultusunda parça yerleştirme ve parça kesim ve sınır değerlerini elde etmek için bir yazılım geliştirilmiştir. iv -

SUMMARY THE SOFTWARE DESIGN OF SHAPE PLACEMENT ON PLANE This project is aimed of decreasing loss of place which oocured due to the shapes which is put in to place the other one included holes. Solving the placing problem the boundary of the shapes is extracted and then fitting of the boundary is established. The boundary curve of the shapes are aligned to the other shape. The problem of finding the best fit between two curves. Since two-dimensional objects are completely described, both globally and locally, by their closed boundary curves, the detection of partially objects participating in a composite scene can be done by matching the boundary curve of the scene with the boundary curves of the candidate objects and trying to find out whether they have a `long enough` matching subcurve. This method is particularly attractive in recognation of partially occluded objects, because in such a situation no use can come of global object characteristics, and only properties which are preserved locally, such as the visible boundary curve, can be taken into account. Curve matching algorihm also have potential applications in finding correspondence between maps and terrain images. Our approach has been motivated by an algorithm due to Shwartz and Sharir that solved the curve matching problem under the restrictive assumption that one curve to be matched is a proper subcurve of the other, namely: Given two curves, such that one is a proper subcurve of the other, find the translation and rotation of the subcurve given is the best least squares fit the longer curve. The complexity of this algorithm is O(nlogn), where n is the number of sample points on curves. In order to apply least squares algorithm to the boundary of the problem of object recognition, one has to divide the boundary of the visible scene in to subcurves belonging to different objects. One way to do it is to assume that overlapping parts create sharp concavities, so that each such concavity on the external boundary is conjectured to be a breakpoint between different parts. Similar heurestics have to be applied in assembly problem. - v -The algorithms presented in this correspondence are intended to solve the more general curve matching problem: Given two curves, find the longest matching subcurve which appears in both curves. Our algorithms do not require one curve to be proper subcurve of the other. Using such an algorithm the recognition of an occluded object in an overlapping scene can be obtained by matching directly its boundary curve to the boundary curve of the scene and finding their matching portion, without the need to divide the scene curve in advance. Also, this algorithm completely solves the 2-D assembly problem. Numerous algorithms were developed for the two-dimensional object recognition and location problem. We mention a few of them which use curve matching. Freeman describes two dimensional shapes by sets of critical points (such as discontinuties in curvature) and computes local shape features between consecutive critical points. This method is, however not applicable for curves which do not possess such critical points, or in scenes where such points are occluded. Curve matching algorithm, object recognition being one of its applications. In the development of this technique we were especially interested in general applicability and computational efficiency. The algorithm which are presented in this correspondence do not depend on special features of the curves such as critical points of or the breakpoints. The matching is based on information which is obtained from all sample points on the curve rather than on information obtained from some special points which may or may not exist. Subsequently, when a big number of sample points participate in the matching process, computational efficency becomes a major concern. Our technique has the drawback of not being efficient for curves which can be described by a small number of parametres, such as circle or rectangles. In such case other simple and well known methods, which can be applied in a first preprocessing stage, will suffice. The algorithm is based on conversion of curves in to numerical strings, efficient discovery of candidate long matching substings, and a subsequent verification of the proposed matches in the plane. In the algorithm we show - vi -that curve matching can be accomplished in time 0(n), n being the number of sample points on the curves. Since this is also the size of the input, we achive the best possible complexity. This algorithm exploits the most efficient string matching techniques for exact integer substring comprison. However such exact comparison may not be robust in presence of noisy data. Consider two planar curves arbitrarily positioned in the plane, having at least one `sufficiently long` common subcurve (modulo translation and rotation). The data describing the curves is assumed to be noisy. Longest common subcurve of these curves is wnted to find. Once this having this subcurve The angle and displacement is wanted to find by which one must rotate and translate one of the curves to make it fit the other curve along their common portion. We begin with three major preprocessing steps: 1) Objects are phographed by a camera from the same distance and viewing angle, and the pictures are digitized and thresholded to get a binary image for each object. 2) With halftoning technique, visual resolution of shape is obtained intensity levels. Halftoning is a technique for using a minimum number of intensity levels, generally balck and white, to obtain increased visual resolution. The visual resolution of computer-generated images can be increased using a technique called patterning. In contrast to halftone printing, which uses variable cell sizes, patterning generally uses fixed cell sizes. For a display of fixed resolution, several pixels are combined to yield a pattern cell. Thus, patterning trades spatial resolution for improved visual resolution. 3) The boundary of each object is extracted from the binary` image. These boundary curves are our `experimental` curves. It is noticed that the main objects have holes. After extacting the boundary curve of object, the boundary curves of the holes in the main objects are extracted from the binary image. The boundary of objects and holes extracted using Freeman Chain code. Assuming a rectangular grid eight basic between 0 and 7. As it this original inseption the code direction is defined. The direction are numerated was derived from the binary image. Each segment of the - vi i -curve which falls within one of the squares is approximated by one of the eight directions. This result can be expressed as astring of number representing the basic directions. The General Outline Of The Algorithm Our approach can be summirised in the following steps. Step A: Represent both curves by charcteristic strings of real numbers which present local translat ionally and rotationally invariant shape signatures. This step eliminates the effect of the rotation and translation parametres, and results in the fact that similiar subcurves (modulo translation and rotation) are represented by similiar numerical substrings. Step B: Find several long common substrings of the two shape signature strings, and return their starting points and endpoints. At first glance this step would seem not to be robust, since it depends on the accuracy of Step A. Hence it is desirableto develop a robust string matching algorithm which is considerably noise immune. We should also remember that the aim of this step is quite limited. All we want is to locate approximate starting points and endpoints of several long candidate subcurves for matching algorithm, which constitues Step C. Step C: For each pair of candidate matching substrings, which were passed from the previous step consider their corresponding subcurves in the (x,y) plane, and find the rotation and translation of one the subcurves giving the best least squares fit to the other. Check if the shape covers the hole. If it dosen't cover, this candidate matching substring is available. Verify the candidate results by calculating again the longest matching portion of the transformed (rotated and translated) original curves in the (x,y) plane, and choose the pair of candidates which has the longest such subcurve. This last calculation is introduced to archive more robustness. In a case of a number of candidate matches of equal length, it will eliminate the shorter subcurves using robust point match in the plane, and will not rely on the length found by less reliable string matching of Step B. - vixi -The algorithm outlined in this section is designed in a flexible way, so that a collection of `strong` candidate solution is passed from step to step, thus, on one hand, eliminating the overwhelming majority of obviously wrong solutions, and, onthe other hand, reducing the probability that the correct solution will be eliminated at an early stage of the algorithm. - IX -