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

Ganesha Firefox Club and Divkom HME-ITB Help Students to Make A Website Easily Using WebMaker

Hi guys, I’d love to share my experience when I hosted an event about WebMaker a week ago in my campus.

Divkom is an organization under of HME-ITB as advisor (HME-ITB is Electrical Engineering student union of Institut Teknologi Bandung), which helps members to develop skills regarding professionalism in electrical field, in this case Divkom engaged in information technology firm, such as web development, mobile or desktop application development, and computer network. Every year, Divkom held a regeneration event named StartUp Divkom. StartUp Divkom is an annual regeneration organized by Divkom HME-ITB in preparing a successors in the development of information technology. This week, Divkom want to give a workshop about web development to the candidates who wish to continue the steps to become the crew of Divkom.

Last week, My friends and I held a gathering all of Ganesha Firefox Club members. The contents of the discussion concerned about the introduction of FSA, and its activities. As a crew both of Divkom and FSA, I had an idea that Ganesha Firefox Club could help Divkom to share our knowledge about web development and what we can do to make a web easily.

4
Webmaker logo on screen

Event which I planned are :

  • What is Mozilla?
  • How to build website using WebMaker easily?

This event has announced on Mozilla Events Pages, you can reach on this page [1] and our Firefox Club page on this page [2], and for the detail invitation you can reach on this page [3]. Here I would like to share my experience as a host this event.

Before Workshop

Before the workshop begun, I had meeting with other crew of Divkom about how long I would make for both sessions. We had about 30 people as audiences, and workshop was one and a half hours long. Following topic were covered in the event by myself.

  1. What is Mozilla
  2. What are Mozilla missions and products
  3. What is Webmaker
  4. What Webmaker can do
  5. What are tools that can be used in Webmaker
  6. The audiences try to make a web using each of tools
  7. Demo

The Workshop

This workshop was at Signal and System Lab. of Institut Teknologi Bandung where we had a lot of students waiting for us. we had about 30 people in this workshop and I took two sessions.

First session was taken by myself to introduce all about Mozilla. the students were actually misguided about what Mozilla is. so, I explained to them what Mozilla is, our mission and our products include Firefox Browser, Mozilla Thunderbird, Mozilla Persona, WebFWD, Firefox OS, Mozilla Webmaker (our focus), Marketplace, and Firefox for Android. after this short session finished, the students was actually very surprised and we had changed their paradigm about Mozilla.

I was presenting Mozilla Webmaker tools
I was presenting Mozilla Webmaker tools
2
I helped the audience using Webmaker tools
The audience tried to remix a project using Thimble
The audience tried to remix a project using Thimble

Next session was taken by my self too on Mozilla products that will help us to make a website easily. I told them that Mozilla has a product can help us to make a website easily called Mozilla Webmaker and its tools include X-Ray Goggles, Thimble, and Popcorn Maker. They found this session admirably. They can see how the web works in X-Ray Goggles because X-Ray Goggles allow us to see the building blocks that make up websites on the internet. We can inspect the code behind any webpage, the remix elements with a single click, swapping in our own text, images and more. they can see how to make a web easily because Thimbles makes it ridiculously simple to create and share our own web pages in way we write and edit HTML and CSS right in our browser then instantly preview our work, and then will help them easily remix web video, audio, and images into cools mashups that we can embed on other websites using Popcorn maker. I helped them using each of this tools and it became so fantastic.

After Workshop

It felt like the time went so fast, the workshop finally finished. it was time to give the Mozilla merchandise. I told you, they came enthusiastically to pick up the merchandise. most of them picked the merchandise up more then three merchandises. it was really funny when they struggled each other to pick it up. 😀

It is great experience for me because this is my first event I ever hosted. if you want to see how fun it was, please visit my flickr here [4].

Group photo at the end of the sessions.
Group photo at the end of the sessions.

————————————————————

Useful Links :

[1] Mozilla Event Page : https://wiki.mozilla.org/StudentAmbassadors/Events#December_15th

[2] Ganesha Firefox Club :  https://wiki.mozilla.org/Ganesha_Firefox_Club

[3] Event invitation :  https://yopiyuanggara.wordpress.com/2013/12/08/how-to-build-website-using-webmaker/

[4] Photos : http://www.flickr.com/photos/112083344@N05/

How to Build Website Using WebMaker

Ganesha Firefox Club  – Indonesia, already have planned to host an event in Institut Teknologi Bandung next week. We, Ganesha Firefox Club and Divkom HME-ITB [1] work together in StartUp Divkom 2013 [2]. This event will be held :

Date : Sunday, December 15th, 2013

Time : 13.00 – 16.00 (GMT+7)

Venue : Signal and System Laboratorium 3

Host : Yopi Yuanggara (Firefox Student Ambassadors – Indonesia)

Audience : More than 30 (candidate of Divkom HME-ITB crew)

Session : “What is Mozilla?” and “How to build website using Web Maker?”

YOU CAN SEE THE SUMMARY OF THE EVENT ON THIS PAGE.

————–

Note :

[1]. Divkom HME-ITB is one of the divisions of the HME-ITB (Electrical Engineering Student Association) which is structurally independent-profitable organization and HME-ITB as the advisor. Divkom HME-ITB is engaged in Information Technology but focus on web programming, java programming, and networking.

[2]. StartUp Divkom 2013 is an annual regeneration organized by Divkom HME-ITB in preparing a successors in the development of technology, especially in web programming, java programming, and networking.

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