Sử dụng floodfill để tìm ký tự

Hãy tưởng tượng về 1 bản đồ địa hình, trong đó có các đỉnh núi và các thung lũng. Khi chúng ta đổ nước vào đó thì mực nước sẽ luôn bằng nhau vì nước chảy lan đến khi gặp vật cản thì dừng lại. Dựa vào ý tưởng đó chúng ta có thể tách ký tự bằng cách xem các ký tự là các thung lũng, hoặc ngược lại các ký tự là những vùng cao còn nền là thung lũng.

floodfill
Hình trên là bản đồ địa hình, các đường đồng mức thể hiện mực nước dâng cùng độ cao và các vùng được liên kết với với nhau

Ý tưởng của thuật toán

Thuật toán floodfill hoạt động như sau: user chỉ định 1 điểm và gán 1 màu cho pixel ở đó, thuật toán sẽ tìm tất cả các pixel lân cận có cùng giá trị và tô màu. Nếu user chỉ định cận trên/cận dưới thì thuật toán tìm các pixel có giá trị chênh lệch trong khoảng giá trị cho phép. Kết quả ta được tập hợp các pixels nằm kề nhau với các giá trị giống/gần giống nhau kèm theo 1 hình chữ nhật chứa bao lấy.

Trong lib OpenCV có sẵn sample viết bằng C++ lẫn Python minh hoạ thuật toán này. Thuật toán này chạy được với ảnh binary, xám và màu.

Bạn có thể dùng mspaint, dùng tool Fill with Color (có hình thùng sơn) để hiểu về thuật toán.

Ứng dụng vào tìm ký tự biển số xe

Thuật toán này dùng để tìm các ký tự, các đối tượng foreground trên background. Để tìm được phải chuyển qua ảnh trắng đen, sau đó cần phải sử dụng thuật toán nhiều lần để tìm được tất cả các blob trong ảnh:

  • Duyệt qua tất cả các pixels lớn hơn 0 trong ảnh
  • Pixel đầu tiên dùng floodfill tô 1 màu, ta được blob đầu tiên
  • Qua pixel tiếp theo, nếu khác màu chúng ta đã tô thì tô màu mới, nếu giống màu chúng ta đã từng tô thì bỏ qua
  • Lặp lại cho đến hết ảnh

Như vậy, 1 biển số xe sau khi được cắt chuyển thành ảnh trắng đen, sau đó dùng thuật toán floodfill sẽ tách được các ký tự như hình bên dưới
biển số xe

Code c++

Hàm bên dưới tìm tất cả các blob trong ảnh binary. Struct blob có các tham số về kích cỡ Mat chứa nó, hình chữ nhật bao lấy và số điểm tạo thành blob đó.

Blob được định nghĩa là tập hợp các pixel liền kề có giá trị giống (hoặc gần giống nhau, ±2 chẳng hạn). Do bài này tìm trên ảnh nhị phân [0;255] nên các pixel của blob phải giống nhau

Code Python

Floodfill.py (3 KB)

4 Responses to Sử dụng floodfill để tìm ký tự

  1. Chuc Tran says:

    Anh ơi, làm sao để có thể lấy được dữ liệu chính xác hơn ạ. Em làm nhưng 1 biển số xe chỉ lấy được có 6 hoặc 7 ký tự thôi ạ

    • vohungvi says:

      thì dùng nhiều biển để lấy ra nhiều ký tự

    • Chuc Tran says:

      như thế thì em có thể dùng tool Object locator để khoanh vùng ký tự từ biển số xe mà không phải dùng thuật toán floodfill này để tách ký tự cũng được phải không a

    • vohungvi says:

      đó cũng là 1 cách, cách này mình làm từ thời sinh viên

Leave a Reply