Maze Solving with Image Processing Algorithms Using MATLAB

Digital Image Processing was the most interesting course in my 7th semester, we were not only studying about digital image analysis but also its applications to human being to help their daily activities. In the end of this class we had to make a project about image processing, so we (Fajar, Yulia and I) wanted to make a project about Maze Solving with Image Processing Algorithm using MATLAB.

Why Maze Solving?

Do you know Maze Game?. yeah it is quite interesting, isn’t it?. Maze game is one of favorite “brain and puzzle” game in the world. it is played maybe more than a billion people in the world, all ages, with various level. we can solve the maze easily for a low level of difficulty, but it will takes a long time to solve for high level of difficulty.  If you take to long to solve the maze and you are so curious about the solution, we can solve the maze with image processing in very very short time. the maze puzzle can be solved using MATLAB program that created as *.m file and the solution will be displayed as *.fig file.

f74c1f1f6491ce9395e28882dfec9b4a
Diagram block system

How to Solve The Maze?

Before I explain how to solve the maze with Image Processing algorithms, would you mind to solve this maze to me?

SolOneit is very easy, isn’t it? You can solve it (maybe) under a minute.. and how about this one.MazeMedium0mm.. Interesting, you can solve it, but you need more time. it’s quite difficult. And, how about this one.

MazeExtraooh maan.. That’s crazy.. you’ll show me just-kill-me-already-look.

To solve those mazes, we use some of technique that we have just learned in the class, and we divided into several steps, there are:

  • Pre-Processing
This is the first step to solve the maze. we need to prepare the maze image which will be solved. When the program starts running, the dialog box appears on the screen and asks user to choose the maze image [1]. when user click “Open” button, maze image is ready to be process. look up this picture [2].
[1] Dialog box
[1] Dialog box
  • Image Enhancement
In this step, the maze image will be converted to monochrome image. monochrome image will be obtained by extraction each of color (RGB) that consists of Red, Green, and Blue channel color, and we choose one of these monochrome channels which have high contrast. After that, we need to prepare image for thresholding process with scaling the image become 0 – 255 range. we have to invert the binary image to become binary inverse. so the walls will become white, and the path is become black, you can see in this picture [3].
[2] Original image (left), [3] Binary image (right)
  • Image segmentation
in this step, the program will perform the segmentation process. in this process, we will determine which maze is connected or separated. to distinguish the wall are connected each other is done by random coloring to each connected wall. the result can be seen in this picture [4]. in that picture [4], we can see, we obtain two group connected-wall. It appears in two different color. we need to choose one of those walls to the next process and eliminate the other one. the following results after we eliminate one of the connected-wall is in this picture [5].
[4] Segmentation to distinguish between connected-wall and separated-wall
[4] Segmentation to distinguish between connected-wall and separated-wall, [5] Selection one the the connected-wall
  • Morphological Operation
after we obtain one connected-wall, we need to perform dilation process to close the unnecessary path. here the result of dilation by passing a large structure element with a particular pixel [6]. the result of dilation process is often still leaves holes that need to be closed. here the result of the closing holes [7]. after closing the holes, we have to perform erosion process, here the result [8]. after that, we need to do subtraction between the image from dilation process (+closed holes) and the image form erosion process in order to get the solution path in this picture [9].
lala
From left to right, [6] dilation process, [7] closing the holes, [8] erosion process, and [9] the path which is got by subtraction process between dilation (+ closing the holes) image and erosion image, is the solution path
  • Post-Processing
in this last process, we have to combine the solution path that we have been obtained with the initial image in the single image. the process is performed by merger from three monochrome channel into a single image (RGB). here the final result to solve the maze. the red object in this picture [10] is solution path of *.jpg file.
Path solution of the maze.
[10] Path solution of the maze.
Very simple, isn’t it?, and definitely very interesting.  you don’t need using some kind of advanced algorithm to solve maze problem. well, mmm, thanks to Fajar and Yulia have engaged me with this project. May the luck be here with us. #fingercross
[Update]
I was really proud of my team for this project.. We got an excellent response from our Lecturer, and I quoted “Very interesting idea, outstanding presentation, overwhelmed project”. Well, that’s big, really big. Thanks anyway.
Advertisements

Embedded System Projects Using Nuvoton Board

For the first time, I need to explain a little bit about Embedded System itself. What is it?. An embedded system is a computer system with a dedicated function within a larger mechanical or electrical system, often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. Embedded systems control many devices in common use today. (Wikipedia).

Could you give me example? Yes.. Every process control system, engine control, antilock breaking system, computer peripherals, etc. Embedded system run into specific function, various processor, real-time, RTOS, limited power sources, etc.

Could you tell me how to create it?.  We need 3 elements to creat an embedded system, they are: [1]. Modelling, [2]. Design, and [3]. Analysis. Creating embedded systems requires an iterative process of modelling, design, and analysis.

***

Well, this is a list of projects that Adit, Adam, and I have ever made using Novoton Board in Embedded System Design Class during last semester. Maybe you find it interesting.

1. Debouncing

Debouncing is used to avoid bouncing. There are several type of switch debouncing in electrical world. In this project, we use software debouncing. Software debouncing is another method to get rid of bounces in the circuit. The basic principle is to sample the switch signals and filter out glitches if any.

2. Debouncing with Auto-Repeat

Basically, this is similar with the first project but in this case we should add another feature, which is called auto-repeat.

3. Keypad Multitap

Multitap is an entry system as text for mobile phones. typically, the alphabet is popped up each key which is pressed. Generally, key ‘2’ contains alphabet A, B, and C, key ‘3’ contains D, E, and F, etc. Multitap is used to write a text-messaging for mobile phones. some of them have changed it to mini keyboard but still in the same function. Since 2012, most of the mobile phones have used predictive input method with fewer key but we have to learn from the beginning how the mobile phones keypad works.

4. Digital Clock

it uses keypad as input using scanning methods. user can set time and date when this program starts running.

Massive thanks to Adam and Adit for helping me with this kind of tasks and to accompany me to the end of this semester.

Power Supply with Self Set Timer

keadaan awal1
Power Supply with Self Set Timer

Ponsel merupakan sebuah alat atau teknologi yang sungguh dekat dengan kehidupan kita pada zaman sekarang ini, hampir setiap orang baik dewasa ataupun anak-anak memiliki setidaknya satu ponsel, ya setidaknya, karena banyak juga yang memiliki lebih dari satu, misal dua, tiga, dst, salah satunya saya sendiri, saya membekali diri saya dengan dua ponsel.

Ponsel memang sudah bukan teknologi yang super mahal, sekarang banyak sekali ponsel-ponsel canggih berkualitas bagus namun dengan harga yang murah, walaupun begitu, tetap saja, yang namanya sebuah alat, mesin, teknologi, atau apalah namanya, pasti tentu butuh perawatan dan penggunaan yang baik agar benda tersebut bisa awet dan tahan lama. Salah satu hal yang perlu diperhatikan/ dijaga adalah kondisi baterai dari ponsel tersebut. Keawetan baterai menjadikan salah satu faktor yang perlu perawatan yang baik, apalagi baterai original. Bayangkan, ketika asyik menelpon orang tersayang, eh baru 5 menit baterai sudah memberikan warning saja kalau akan habis, panggilan penting dari client mendadak, eh tiba-tiba ponsel sudah mati saja. ga enak kan.

Salah satu perawatan yang perlu diperhatikan adalah ketika kita charging baterai. Sering kali kita lupa bahwa ponsel kita sedang charging dan sudah full-charge namun tidak kunjung dicabut juga dengan alasan ketiduran, lupa, dll charging sampai berjam-jam, alhasil hal itu dapat merusak kondisi baterai kita dan menjadi gembung, buncit istilah anak2 sekarang.. Memang, banyak yang jual baterai pengganti, tapi kebanyakan baterai pengganti pun mudah rusak, sehingga menjaga kondisi baterai original perlu juga diperhatikan sehingga dapat dijaga keawetannya.

Trus apa solusinya dong? 

Namanya “Power supply with self set timer”, atau dalam bahasa indonesianya penyuplai daya dengan pengaturan waktu sendiri. Lupa juga kenapa dipilih nama ini, yang jelas tujuan dari alat ini adalah supply daya yang kita lakukan ke peralatan elektronik kita dapat diatur waktunya sesuai dengan keinginan kita. Walaupun zaman sekarang baterai Li-ion sudah banyak yang bagus dan adaptor yang diberikan juga sudah bagus, but hey it’s worth knowing, right?

 Gimana cara bikinnya cuy?
Untuk alatnya sendiri saya membagi menjadi dua, yaitu:
* SisMin: Sebagai otak dari pengaturan waktu, kendali dari semua sistem. Terdiri dari:
ATMEGA sebagai processor coded by C language with winAVR,
Keypad sebagi input user,
LCD sebagai monitor,
LED sebagai indikator,
LM7805 sebagai DC-DC coverter (~5 Volt),

Adaptor/ Baterai sebagai sumber daya sismin,

SisMin dengan Atmega
SisMin dengan Atmega
* Power Supply: Sebagai sumber daya. Terdiri dari:
Terminal listrik 2 socket or more, mau yang gaya juga boleh [pilih model terserah asal ada yang bisa dicolokin kesana, bebas sih ini, dibikin sendiri kayak socket yang langsung nempel dinding lebih bagus lagi],
Relay sebagai saklar arus AC diterminal,
Transistor BJT sebagai switching yang akan mengendalikan relay,

Diode sebagai pengaman dan penstabil tegangan,

Terminal/ Socket
Terminal/ Socket

Berapa biaya yang dikeluarkan tuh?
Semua murah meriah ga butuh duit banyak, kalo mau hitung sendiri monggo silahkan, tapi kalo saya tidak mengeluarkan uang banyak. Sismin bisa minjem, terminal jala-jala pake bekas kosan, tinggal beli kompenen elektronik sedikit saja, I can say less than 20k. he. Kalo mau lebih bagus beli komponen yang SMD biar lebih kecil dan lebih compact..

Nah, cara kerjanya?

Terminal terdiri dari dua socket dan masing-masing akan diatur waktu lamanya dapat dialiri arus jala-jala/ AC sampai akhirnya otomatis mati. ATMEGA coded by C language with AVR sesuai dengan fungsi yang kita butuhkan pada sistem.

 * Cara kerja software:
1. User akan memilih kondisi (MODE) apa yang diinginkan. Disini dibagi mejadi 4 MODE, MODE1: Socket1 dan Socket2 aktif, MODE2: Socket1 aktif, MODE3: Socket2 aktif, MODE4: Nonaktif.
2. User akan mengatur berapa lama masing-masing socket yang dipilih untuk aktif, input berupa HOUR, MINUTE, SEC yang berasal dari keypad 4×4 yang kita gunakan.
3. Semua input yang dimasukan akan ditampilkan pada LCD 16×2 yang telah terpasang pada sistem minimum.
4. klik START sehingga sistem akan mulai.
5. Apabila user menggunakan MODE2 dan MODE3 atau berada pada keadaan MODE2 dan MODE3 maka user bisa masuk ke kondisi SETTING dimana user dapat mengaktifkan lagi socket yang non-aktif tadi sehingga bisa masuk ke MODE1 lagi.

6. Program akan berjalan sampai waktu dikedua socket habis, dan akhirnya kedua socket akan mati walau terminal masih dialiri arus.

Untuk program tergantung kreativitas programmer, tergantung kebutuhan saja. Gampang banget kok sama kaya bikin timer, very basic microcontroller system.

* Cara kerja hardware:

Pada program dibuat bahwa ketika masing-masing socket diaktifkan, maka disalah satu port pada Atmega akan aktif (Logika 1, High) sehingga akan dialiri oleh arus ~5V ( bisa dicek dengan osciloscope). Port Atmega tadi tersambung dengan transistor BJT yang terpasang. Tansistor BJT berfungsi sebagai switch dimana mengatur tegangan keluaran yang dapat membuat Relay (Switching pada Jala-jala/ arus AC) dapat menyambung arus pada jala-jala/ arus AC. Apabila Atmega memberikan sinyal high (Logika 1) dari port output ke Base Transistor, sehingga menjadikan Tegangan Collector akan sama dengan Tegangan Emitter (bertindak sebagai ground ~0V) sehingga Relay yang terpasang diantara Vcc (~5V) dengan Tegangan Collector kasarnya akan dialiri arus dan membuat Relay tertutup (menjadi Switch ON) sehingga socket akan menyala/ dialiri arus. Sebaliknya, apabila Atmega memberikan sinyal low (Logika 0) dari port output ke Base Transistor, sehingga menjadikan Tegangan Collector akan sama dengan Vcc ( ~5V) sehingga Relay yang terpasang diantara Vcc (~5V) dengan Tegangan Collector kasarnya tidak akan dialiri arus dan membuat Relay terbuka (menjadi Switch OFF) sehingga socket akan tidak menyala/ tidak dialiri arus.

***

 Gitu. Gampang kok. hehe. Sehingga walau kelupaan karena ketiduran, atau lagi jalan keluar namun ponsel masih nge-charge maka kita bisa ngatur sendiri lo lamanya ngecas jadi ga usah takut baterai cepat buncit. Huge thanks to my buddy Indra Cip for helping me with this kind of project, thanks anyway. #EngineerForever