Comparative study of algorithms for voronoi diagram construction on segmentation of Arabic hand writing

Jabril Ramdan Abdslam Salem (P50166)

Please use this identifier to cite or link to this item: https://ptsldigital.ukm.my/jspui/handle/123456789/476369

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Khairuddin Omar, Prof. Dr.
dc.contributor.author	Jabril Ramdan Abdslam Salem (P50166)
dc.date.accessioned	2023-10-06T09:17:12Z	-
dc.date.available	2023-10-06T09:17:12Z	-
dc.date.issued	2011-09
dc.identifier.other	ukmvital:84250
dc.identifier.uri	https://ptsldigital.ukm.my/jspui/handle/123456789/476369	-
dc.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
dc.language.iso	eng
dc.publisher	UKM, Bangi
dc.relation	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat
dc.rights	UKM
dc.subject	Voronoi polygons
dc.subject	Arabic language
dc.subject	Writing
dc.title	Comparative study of algorithms for voronoi diagram construction on segmentation of Arabic hand writing
dc.type	theses
dc.format.pages	104
dc.identifier.callno	QA278.2.S238 2011 3 tesis
dc.identifier.barcode	001972
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Files in This Item:

File	Description	Size	Format
ukmvital_84250+SOURCE1+SOURCE1.0.PDF Restricted Access		1.56 MB	Adobe PDF	View/Open

Show simple item record Recommend this item