1. UKM Learning and Research Repository
2. Master Thesis / Tesis Master
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Comparative study of algorithms for voronoi diagram construction on segmentation of Arabic hand writing
Authors:	Jabril Ramdan Abdslam Salem (P50166)
Supervisor:	Khairuddin Omar, Prof. Dr.
Keywords:	Voronoi polygons Arabic language Writing
Issue Date:	Sep-2011
Description:	Segmenting Arabic characters is one of the challenging and tedious tasks in the character recognition process. This work proposes an approach to construct Arabic characters segmentation based on Voronoi area. The proposed approach is constructed based on three existing algorithms, such as Voronoi Diagrams (VD), Divided-and- Conquer algorithm (DAC), Half Plane Intersection algorithm (HPI) and Incremental algorithm (I). The VD method performs the segmentation processes by obtaining the line between the connected components, based on the neighbours graph. Whereas the DAC is a fundamental paradigm used for designing efficient algorithms, where the original problem is recursively divided into several simpler sub-problems of approximately equal size. Then the solution of the original problem will be obtained by merging the solutions of the sub-problems. The HPI algorithm is based on Delauney Triangulation. The VD is constructed by HPI algorithm as follows: i): Connect Nearest neighbors; ii): draw the perpendicular bisector for each Delauney line. Meanwhile, the 'I' algorithm calculates the VD by incremental insertion of Voronoi regions, which makes it more efficient and numerically robust to produce the best structures and yield better results in the segmentation process. The proposed algorithm determines the neighbours graph by drawing a line from the centre of the connected components to trace the boundaries of the neighbours in a white background. If there is a gap between the connected components then they are not considered as neighbours. The Euclidian distance is used as a base to draw line segment between the connected components, which is called as VD. In this research the IFN/ENIT1 dataset will be used. This dataset consists of 569 handwritten Arabic images of the names of Tunisian towns'. Many experiments has been carried out with the abovementioned base algorithms and compared in terms of time, speed of construction, the number of vertices, and edges. The early results shows that DAC is promising than the HPI in the static algorithm category, whereas the dynamic 'I' algorithm consumes more time than static algorithms.,Pemisahan huruf atau abjad Arab telah menjadi satu daripada kesukaran utama dalam proses segmentasi. Kesukaran yang ada adalah disebabkan sifat huruf atau abjad Arab. Dalam tugas ini, satu pendekatan telah dicadangkan kepada satu kajian perbandingan pada tiga algoritma pembinaan Rajah Voronoi (RV) “Pecah dan Perintah (PDP), Persilangan Separa Satah (PSS), dan Menokok (M)” yang memisahkan huruf atau abjad Arab berdasarkan kawasan Voronoi. RV adalah satu kaedah yang digunakan dalam proses segmentasi melalui talian antara komponen yang bersambung, bergantung kepada penentuan graf jiran. Algoritma yang diketengahkan ialah algoritma PDP yang merupakan paradigma fundamental untuk merekabentuk algoritma yang efisyen. Dalam paradigma ini, masalah yang wujud sejak awal dipecahkan secara berulang-ulang kepada beberapa masalah yang lebih kecil yang hampir sama saiznya, dan penyelesaian kepada masalah yang wujud dari awal adalah dengan menggabungkan penyelesaian dari masalah-masalah yang kecil, algoritma PSS berdasarkan kepada Delauney Triangulation. Mengikut peraturan, untuk membina RV menggunakan algoritma ini mesti mengikuti beberapa langkah. Langkah pertama: Menghubungkan jiran yang hampir. Langkah kedua: Lukis garisan serenjang bagi setiap garisan Delauney, dan algoritma M mengira RV dengan kemasukan menaik. Dalam kajian ini, algoritma untuk menentukan graf jiran ialah melukis garis dari pusat komponen yang berkaitan untuk mengesan sempadan untuk jiran selagimana latarbelakangnya adalah putih, maka mereka adalah jiran. Jika terdapat sebahagian dari komponen yang berkaitan atau semua komponen yang berkaitan antara mereka, maka tidak ada jiran. Pada algoritma segmentasi asas ini menggunakan jarak Euclidian di antara jiran untuk melukis garis segmen di antara komponen yang berkaitan dipanggil Kawasan-RV. Dalam kajian ini set data IFN/ENIT1 telah digunakan. Data set ini mengandungi 569 imej tulisan tangan Arab bagi nama Bandar Tunisia. Beberapa eksperimen telah dilaksanakan dan dibandingkan berdasarkan kelajuan pembinaan, bilangan bucu dan penyambung. Keputusan awal menunjukkan bahawa algoritma PDP sangat menjanjikan berbanding algoritma PSS pada algoritma statik, sementara algoritma dinamik iaitu algoritma M perlu lebih banyak masa daripada algoritma statik.,Master/Sarjana
Pages:	104
Call Number:	QA278.2.S238 2011 3 tesis
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.