Gömülü teknikler kullanılarak çizge medyanının hesaplanması

Abstract

Graph (Çizge) Teorisinin birçok uygulaması görüntü işleme, bilgisayarla görü, biyoinformatik, veri madenciliği ve yapay zeka çalışmalarında sıklıkla kullanılmaktadır. Objelerin çizge gösterimiyle gösterilmesi ve resim eşleştirilmesi ise nesne tanıma çalışmalarında önemli bir yer kaplamaktadır. Birçok örnek resim verilerinde gürültü miktarı doğal koşullar neticesinde fazlaca bulunmaktadır ve elde edilen sonuçlarda da hata miktarı fazla çıkmaktadır. Her bir resmin çizge gösterimiyle gösterilmesi sonucu eşleştirme problemi özünde çizge karşılaştırma problemiyle eşdeğer bir hal almaktadır. Veri miktarının fazla olması ve çizge karşılaştırma işleminin maliyetli olması sebebiyle yakınsama algoritmaları (approximation algorithms) kullanılarak, yapılan işlemin maliyetini azaltma çalışmaları yapılmaktadır. Verilen çizgeleri karşılaştırmak için her grup çizge için, o grubu temsil eden yeni bir çizge hesaplanarak, aranan çizgeyi temsilci çizge ile karşılaştırmanın daha hızlı ve tolere edilebilecek seviyede gerçeğe yakın sonuçlar vereceği öngörülmüştür. Daha önce yapılan çalışmalarda, temel olarak, iki çizgenin karşılaştırılması için çizge uzayındaki her bir çizgeyi, temsil eden vektör uzayına dönüştürme ve daha az maliyetle vektör uzayında işlemler yapma üzerinde durulmuştur. Yapılan çalışmada, her veri sınıfı için veri kümemiz içindeki tüm çizgeler, veri kaybını minimum düzeyde tutacak şekilde, geometrik uzaya izomorfik olarak l_1 norm (Manhattan Uzaklık Metriği) altında dönüştürülmüştür. Bu sayede temsilci çizge bulunması esnasında yapılacak işlemlerin masrafları azaltılmış ve kullanmış olduğumuz Tırtıl Ayrışması (Caterpillar Decomposition) tekniğiyle minimum seviyede veri kaybı olması sağlanmıştır. Daha önce yapılan çalışmalardan farklı olarak, elde edilen geometrik uzayda her bir nokta, çizge üzerindeki bir düğüme (node) denk gelmektedir ve bu sayede veri kaybı azalmaktadır. Temsilci çizgenin belirlenmesi için, oluşturulan vektör uzayında, K-Means Algoritması kullanılmaktadır. Elde edilen temsilci nokta kümesi ile çizgeleri karşılaştırmak için Hausdorff Mesafesi algoritmasının 25 farklı hesaplama metriği kullanılmaktadır. Bu işleyiş yapısı içerisinde minimum seviyede hatayla daha hızlı sonuçlar elde etmek mümkün olmaktadır.

Graph theory applications are frequently used in image processing, computer vision, bioinformatics, data mining and artificial intelligence related works. On the other hand, representing objects with graphs and matching the images are important part of object recognitions applications. In most of sample image data, images have a lot of noise caused by natural conditions and the error levels in the final results are high. When each image is represented by a graph, matching problem inherently turns to be the same as graph comparison. Since the amount of data is huge and the graph comparison is costly, approximation algorithms are used to decrease the total cost. To compare the given graphs, for each group of graphs, a representative is selected. It is anticipated that, comparing the graph only with the representative graphs gives faster results and the results are tolerably close to the exact truth. In the previous works, to compare the graphs, mapping of each graph in the graph space into a vector in the vector space and then working on the vector space with minimum cost is used. In this work, for each data class we have, each graph in the set is mapped to geometric space by using isomorphic l_1 norm (Manhattan Distance metric), so that, the data lose is minimum. Consequently, the cost of finding the representative graph is decreased and the data lose is kept at the minimum by using Caterpillar Decomposition technique. Differently from the previous works, each point in the geometric space represents a node in the graph. Thus, the data lose is lowered. In the vector space, K-Means Algorithm is used to find the representative graph. To compare the representative points set with the graphs, 25 different distance metric calculations of Hausdorff Distance Algorithm is used. This working mechanism makes it possible to have faster results with minimum error level.