Giải mê cung bằng phương pháp morphology

Trò chơi tìm đường qua mê cung có lẽ không lạ gì với chúng ta, bài viết này giới thiệu 1 cách giải bằng thị giác máy tính. Các mê cung được sử dụng trong bài này là loại mê cung “hoàn hảo”, tức là chỉ có 1 đường đi duy nhất. Các bạn có thể tạo mê cung bằng trang web này http://mazegenerator.net/

Để đề phòng trường hợp link website tạo maze không truy cập được, tui có save 50 ảnh maze dự phòng.
Download ảnh maze

Các bước thực hiện

1. Load ảnh và chuyển thành ảnh binary

2.Tìm các vách tường của mê cung bằng hàm findContours, nếu có 2 vách tường (contour) thì không tìm nữa

3. Tô màu đen lên bức tường thứ nhất cho trùng màu với background, như vậy chỉ còn lại 1 bức tường

4. Làm bức tường tìm được nở rộng (dilate) ra vài pixel

5. Cũng bức tường đó bào mòn (erode) vài pixel

6. Lấy ảnh ở bước 4 trừ ảnh bước 5 ta lấy được đường đi qua mê cung

7.Vẽ đường đi lên ảnh kết quả

Nguồn: http://opencv-code.com/tutorials/solving-maze-with-morphological-transformation/

Source code SolveMaze_rev738.zip

Leave a Reply