El çizimi diyagramların modifiye destek vektör makineleri ve grid tabanlı su havzası ile tanınması
Recognition of hand drawn diagrams using modified support vector machines and grid based watershed
Yazar: ORHAN NOORULDEEN
Danışman: DR. ÖĞR. ÜYESİ OĞUZ ALTUN
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı
Derece: Doktora, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Diyagram ve görüntülerdeki kapalı nesnelerin ve yapıların algılanması ve tanınması, son yıllarda ilginç bir araştırma kavramı olarak kabul edilmektedir. Çünkü; elle yazılmış belgelerin dijitalleştirilmesi, literatür ve tanıma yönetiminin tüm seviyelerinde giderek daha fazla gerçekleştirilmektedir. Havza (Watershed); çizgi bağlı el çizimlerinde, kapalı şekil tespiti için kullanılabilecek klasik bir görüntü bölütleme algoritmasıdır. Bununla birlikte, havza algoritması, gürültü eşit olmadığından fazla bölütlemeye neden olabilmektedir. Ayrıca, nesneler birbirine çok yakın olduğunda algoritma verimli değildir. Çünkü; yerel minimumlara karşı algoritma oldukça duyarlıdır. Bu sınırlamalar yüzünden, kapalı şekil nesnelerini tespit etmek için, yeni ileri tekniklere ihtiyaç duyulmaktadır.
Bu tez kapsamında ilk araştırma, elle çizilmiş ok bağlantılı diyagramlarda kapalı şekil nesnelerini tespit etmek için, ızgara havzası (Gridshed) adlı basit, yeni ve verimli bir sistem geliştirmeyi amaçlamaktadır. Izgara havzası algoritmasında, başlangıçta elle çizilmiş diyagram ön-işlemden geçmektedir. Daha sonra, dijital diferansiyel analizörü kullanılarak, kenarlar ve kapalı döngüler oluşturmak için en yakın darbelerin uç noktalarını bağlayarak, görüntü iyileştirilmektedir. Sembol çıkarma, boş görüntü piksellerin kenarlık kutularını bağlayarak gerçekleştirilmektedir. Boş hücrelerin sürekli bağlanmasıyla, diyagramın şeklinin darbeleri kapalı bölgelerden tanınabilmektedir.
Tezin ikinci araştırma çalışması, elle çizilmiş ok şemaları ve dijital mantık devre şemaları için SKETRACK adlı yeni, verimli darbe tabanlı çevrimiçi el çizimi tanıma yönteminin, tasarımı ve geliştirilmesine odaklanmaktadır. Bu yöntemin temel aşamaları; metin ayrımı, sembol bölütlemesi, özellik çıkarma, sınıflandırma ve yapısal analizdir. Önerilen yöntem, metni şekillerden ayırmak için normalleştirme ve bölütleme araçlarını kullanmaktadır. Daha sonra etkili işlem için, şekil darbelerinin farklı yapısal varyasyonlarının özellikleri çıkarılmaktadır. Darbeler, özellikler arasındaki benzerliği hesaplamak ve benzer özellikleri gruplayarak özellik boyut sayısını aza indirmek için p-uzaklığı ve Öklid mesafesine dayalı spektral kümeleme algoritması kullanılarak kümelenmektedir. Daha sonra sembol tanıma, hibrit çekirdek fonksiyonun kullanıldığı Modifiye Destek Vektör Makinesi (Modified Support Vector Machine, MDVM) sınıflandırıcısı kullanılarak gerçekleştirilmektedir. Hibrit çekirdek fonksiyon parametreleri Aslan Optimizasyon Algoritması ile optimize edilmektedir. Yapısal analiz, son diyagram gösterimlerini oluşturmak ve sembol adaylarını tanımak için gerçekleştirilmektedir.  Önerilen bu tanıma modeli, akış şemaları, sonlu otomat ve mantık devre şemaları gibi daha basit yapılar için uygun olmaktadır.
Deneyler yoluyla, önerilen Gridshed ve SKETRACK yöntemlerinin performansı, veri tabanlarında değerlendirilmekte, sonuçlar üstün verimliliklerini doğrulamak için en son yöntemlerle karşılaştırılmaktadır.

Abstract:
Detection and recognition of the closed shape objects and structures in diagrams and images is considered to be an interesting research concept in the recent years as the digitalization of handwritten documents have been increasingly performed at all levels of literature and administration. Watershed is a classical image segmentation algorithm that can be utilized for closed shape detection in line connected sketches. However, the watershed algorithm results in excessive over-segmentation when the noise is non-uniform. Also, the algorithm is not efficient when objects are very close to each other as it is highly sensitive to local minima. These limitations created the need for novel advanced techniques for detecting the closed shape objects. 
First research work of this thesis aims at developing a simple, novel, and efficient system named Gridshed for detecting the closed shape objects in hand-drawn arrow-connected diagrams. In Gridshed, initially the hand drawn diagram is pre-processed. Then the image visualization is enhanced by connecting the closest stroke's endpoints to form edges and closed loops using the digital differential analyzer. The symbol extraction is performed by connecting the border boxes of the empty image pixels. By continual connection of empty grids, the shape strokes of the diagram can be recognized through the closed regions.
Second research work of the thesis focuses on the design and development of a new, efficient Stroke based online hand-drawing recognition scheme named SKETRACK for hand-drawn arrow diagrams and digital logic circuit diagrams. The fundamental parts of this model are text separation, symbol segmentation, feature extraction, classification and structural analysis. The proposed scheme utilizes the concepts of normalization and segmentation to isolate the text from the sketches. Then the features are extracted to form the feature extraction model of different structural variations of the strokes that are categorized into the arrows/lines and the symbols for effective processing. The strokes are clustered using the spectral clustering algorithm based on p-distance and Euclidean distance to compute the similarity between the features and minimize the feature dimensionality by grouping similar features. Then the symbol recognition is performed using Modified Support Vector Machine (MSVM) classifier in which a hybrid kernel function with a tuning parameter optimized by Lion Optimization Algorithm is utilized. Structural analysis is performed to form the final diagram representations and recognize symbol candidates. This proposed recognition model is suitable for the simpler structures like flow charts, finite automata and the logic circuit diagrams.
Through the experiments, the performance of the proposed Gridshed and SKETRACK schemes are evaluated on databases and the results are compared with the state-of-the-art methods to validate their superior efficiency.