Perancangan dan Analisis Algoritma Breadth first search dan Image scaling Pada Studi Kasus SPOJ 3360 IMGREC2 - Digital Image Recognition

Shobr, Pierra Muhammad (2025) Perancangan dan Analisis Algoritma Breadth first search dan Image scaling Pada Studi Kasus SPOJ 3360 IMGREC2 - Digital Image Recognition. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201062-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (5MB) | Request a copy

Abstract

Pada sebuah situs pengujian Sphere Online Jugde (SPOJ) terdapat permasalahan dengan kode 3360 IMGREC2 – Digital Image Recognition. Dimana terdapat sebuah gambar berukuran R x C dengan setiap pixel memiliki nilai 1 atau 0. Pixel bernilai 1 adalah bagian dari component gambar dan pixel bernilai 0 adalah latar belakang dari gambar. Pixel bernilai 1 yang saling berdekatan satu sama lain membentuk sebuah component dengan pola tertentu. Sebuah component berpotensi untuk membentuk pola menyerupai angka digital 0 – 9, namun tidak selalu secara sempurna menyerupai angka digital 0 – 9. Hal ini dapat terjadi akibat dari ukuran stroke penyusun angka digital yang bervariasi mengakibatkan angka digital tidak secara sempurna sama dengan angka digital 0 – 9. Tujuan dari penelitian ini adalah menjumlahkan setiap angka yang ditemukan pada component yang menyerupai angka digital.
Pada prosesnya, identifikasi component dilakukan dengan mengekstrak fitur yang menjadi ciri dari setiap angka digital 0 – 9. Ciri yang digunakan adalah banyaknya outer corner yang digunakan untuk membentuk stroke pada angka digital dan inner corner yang merupakan sudut dari pertemuan dua stroke secara tegak lurus. Untuk menghindari adanya jumlah outer corner dan inner corner yang berbeda akibat adanya variasi ukuran stroke, Image scaling menjadi solusi dengan memperbesar gambar menjadi dua kali lebih besar sehingga total outer corner dan inner corner menjadi lebih konsisten. Proses pengumpulan pixel dari component dalam gambar dapat dilakukan dengan menggunakan Breadth first search, yang tidak hanya membantu untuk mencari component secara utuh tapi juga melanjutkan ke identifikasi outer corner dan inner corner sebelum lanjut pada component berikutnya. solusi algoritma Breadth first search dan Image scaling yang digunakan berhasil menyelesaikan permasalahan dengan menduduki peringkat 19 dari 27 pengguna pada tanggal 31 Oktober 2024. Solusi dapat menyelesaikan permasalahan dan menyelesaikan permasalahan dengan kompleksitas O( n^2.m^2 ).
================================================================================================================================
An image of size R x C with each pixel has a value of 1 or 0. Each pixel with value 1 is part of the image object and pixel with value 0 is the background. pixels with value 1 that are close to each other form an object with a certain pattern. Every object in the image has the potential to have pattern that have similarities with digital numbers 0-9, but does not always have the normal form of digital numbers 0-9. This can occur due to the size of the strokes that make up digital numbers that vary resulting in digital numbers that are not perfectly the same as digital numbers. The purpose of this research is to sum every number found in objects that resemble digital numbers. In the process, object identification is done by extracting features that characterize each digital number 0-9. The feature used is the number of outer corners used to form strokes in digital numbers and inner corners created as a result of the meeting of two strokes perpendicularly. To avoid the number of different outer corner and inner corner due to avoid the number of different outer corners and inner corners due to variations in stroke size, Image scaling becomes a solution by enlarging the image to be twice as large so that the total outer corners and inner corners become more consistent. The process of collecting pixels from objects in the image can be done using Breadth first search, which not only helps to search the object as a whole but also proceeds to identify the outer corner and inner corner before moving
on to the next object. Based on the test results on the given case study, the Breadth first search and Image scaling algorithm solutions used successfully solved the problem by ranking 19th out of 27 users who solved the problem and solved the problem with O( n^2.m^2 ).

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Breadth first search, Image scaling
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Pierra Muhammad Shobr
Date Deposited:	01 Feb 2025 05:10
Last Modified:	01 Feb 2025 05:10
URI:	http://repository.its.ac.id/id/eprint/117414

Actions (login required)

View Item