When Haidilao Hotpot Maze Meets Image Processing

This is an article inspired by a free side dish + my curious soul.

I will divide my article into 2 sections: the fun part and the technical part.

The Fun Part will show you what this project does and how it looks like. That's it, simple and short :) but if you were as curious as me and would like to know the details of the implementation then keep reading.

In the Technical Part, I will treat it as my technical note to remind me what I did for solving the problems and why I did that.

It was a Sunday afternoon, we had been cooking for ages and were sick of doing so... finally we decided to try the expensive hotpot Haidilao. The Haidilao is famous about its premium services and expensive cost.

I know they offer nail and hand skin-care services to customers in waiting queue and yes I actually got the service :)

But what I did not know was that they also offered me a little maze to play to kill the waiting time. What's even better was if I got it solved while I was still in the waiting queue, they would reward me with a free dish 😊!

A piece of cake~!

Within 10 minutes, Lily beat me.... huh.... okay, if I couldn't beat you, I could make a program to beat you. Extracting a maze from a photo looks like a good fit for Image Processing!

Here is what it looks like~!

As you can see here, the app takes a photo and extracts the maze inside the photo and solves the maze problem.

If you were going to have your lovely Haidilao Hotpot, then I have also made it available for you :)

The demo video looks pretty short, to implement it from the scratch, it only took me 2 or 3 days, but... to perfect it and make it available online actually cost me 3 or 4 weeks....

After couple of weeks working on it, it's still not perfect but good enough to satisfy my requirements, so don't expect it to be a commercial project which works for each and every scenario, I have to admit that it has its limitations. I will explain what the limitations are in the following paragraphs.

So here is the procedure how I got it implemented:

👉 Extract the maze out of the photo and warp/rotate it to face directly to us

👉 Find its 2 entrances, the Start and the Exit

👉 Find the path :)

Now, let's talk about how to extract the maze out of the photo and get it face straight to us

There are certain steps to do:

1. Get the white balanced image first~!!
2. Mask the low saturation area, because the maze area happens to be the low saturation area,
3. Use Morphology Close/Open to remove details of the maze so that we only get a big block of white area where the maze is located,
4. Find the most outside contour of the image(now you know one of the limitations),
5. Crop the image so that it only contains the maze area and thus reduces the computation later on,
6. Threshold the image, so that only 0 and 255 are left to the values of pixels, it simplifies the following processing,
7. Use a seed image which is created by taking the center part of the maze image and apply Morphological Reconstruction to extract the maze,
8. Invert the extracted maze to be white wall and black path,
9. Get the convex hull of the extracted maze,
10. Use the convex hull to get its corners,
11. Then crop the image again to extract the exact maze,
12. Warp the maze if it's rotated and get it ready for the next step.

I cannot stress it enough that how important of white balance is. I can tell you that 2 weeks of my precious time was wasted because I did not do the White Balance. To my understanding, it behaves like Normalization in Computer Vision for AI. Without doing it, your code would be fragile and endless frustration is waiting ahead.

What did I mean by this?

Any changes of lighting, the human eyes cannot event notice the differences, will jeopardize the result and breaks the program. I was scratching my head to try to figure out why it works for one image but not for another.

To give you an idea of how the white balanced image look like:

As you can see above, it does change the look and feel of the image by equalizing the Red, Green and Blue channels.

This is very helpful, as it makes the rest of the code free from being affected by any changes of lighting, so the code is more stable.

I wasn't thinking of using HSV color space at first as RGB is the most popular color space. But by operating in the HSV, I found out that the maze area is always the darkest area.

This is great, as it enables me to easily pick the maze paper out of the whole photo(Mask).

As I mentioned above, by also applying morphological close and open I can erase out the rest image and leave a big block of white area to indicate where the maze is located:

The morphological close "eats" the surrounded black pixels, so walls inside are removed see Mask1, then I apply "open" to connected the isolated black holes together just to make it less "noises" see Mask2.

With the mask2, we can now find out biggest and out-most contour and use it to crop the image: cut image.

Then we simplify the image further to only allow it to have 2 values, black(0) and white(255): thresholdimgrec2

With the image: thresholdimgrec2, we can now apply a new operation called Morphological Reconstruction(MR) to the image to further extract the maze from its paper.

Once the exact maze is extracted, we can get its convex hull which will be used to get the locations of maze corners.

The convex hull does not look perfect, because that there is an arrow for exit point which was not removed by the previous steps, but don't worry, it will be removed eventually.

Up until now, we have gotten the extracted maze, but it looks like rotated a bit.

Luckily, in OpenCV, there is a method called warpPerspective() which can help us to rotate the maze.

After the maze is extracted, I would like my code to detect the 2 entrances automatically

Is it possible?

I didn't design this part initially, as I thought users could simply click the screen to point out the Start and Exit points. But I found it's not user-friendly, so I will make my code to do it.

Here are the procedures:

1. Running through the 4 edges and "Ray-casting" until it hits a wall, through this step we can get the idea of where the "mountains" or the entrances are,
2. Pick up the Himalaya mountain in each side,
3. Get the middle point of the Himalaya peak,
4. Push the point a bit inwards so the later on code does not crash.

The idea of ray-casting on each side is very interesting. Imagining a beam of light cast on one edge of the maze and it bounces back. The way it works feels like bats using ultrasound to detect obstacles. I then draw graph to show the distance between the source of light(let's say it's distance 0) and how far it goes until it hits a wall. Once I have run the ray-casting on each side of the maze, the graph looks like this:

It looks beautiful~! On the sides which have no entrance, it's a flat line, but for the sides with entrance, the peak not only shows how far it goes until it bounces back but also shows where the location of entrance is. If you took a closer look at the X axis on the graph Left and Right, the values of the peaks on X axis collocate perfectly with their entrances. This is exactly what I want.

By combining how far the light goes on the Y axis and the value of the peaks on X axis, the location (x,y) of the entrance can be found.

The case above is a perfect case, but sometimes, a maze could be warped because that it is bent by the hand holding it. Let me show you the case:

In this case, there are more than one peak on the bottom side:

Stuck in some problems is boring, so in order to entertain myself, I start to call those peaks mountains and the highest mountain is called Himalaya.

So clearly, if there are multiple mountains, we only want the Himalaya, as the Mountain 1 could happen to be just a bent part on a edge.

Now if we drew the Start and Exit points on the maze, it should look like this:

As you can see that initially what I wanted to do was just to solve the maze by finding a path going through it, but up until now, it's already 80% of the article, this part has not even started yet. So by going through these many steps, I realized that

Now, finally let's solve the maze~!

With the start and exit entrances and the clean and "corrected" maze, we are ready to solve the problem.

Thanks to the Scikit-MPE, it provides a set of code to solve the maze problem. 👍 So all I need to do is to provide the maze image with locations of Start and Exit entrances.

I am sorry to disappoint you if you were expecting to see how the maze got solved. But I am not going to re-invent the wheel since solving a maze is a pretty popular topic, so I know there must be heaps of existing code to do so.

Finally, I would like to point out that the free hosting Python environment I use is Oracle Cloud.

Initially, I thought it's easy to find a free hosting service for Python as I know there are so many good cloud platforms for hosting Nodejs, JavaScript projects and Python is so popular. But it turns out, there are not many choices for a free and easy to use Python hosting platform.

Believe or not, I spent 2 weeks on finding the platform. I have tried:

PythonAnywhere: it is okay, but the UI looks a bit old fashion. If your project requires installing something outside Python's package system, it's a headache.

Microsoft Azure: It has free tier, but when I ssh into its VM, my connection was cut off every a few minutes and whether I can re-connect to the VM again really depends on my luck. I then changed to a plan which cost me $35/month (not a free tier but a developer/testing environment), the problem persists.

Heroku: I can run some bash command, but it is really limited. I know it also supports Docker. I probably would give it another try next time.

Oracle Cloud: the one which provides SSH access from my local console. So I can do everything like what I could on a computer. It also provides all sorts of OS image, I picked up Ubuntu as I am familiar with it. It is the clear winner.

Finally, I woud like to appreciate the help I got from the online community, without their help I cannot finish this hobby project.