Tài liệu Hệ thống giữ xe tự động

TRƯỜNG ĐẠI HỌC LẠC HỒNG KHOA CÔNG NGHỆ THÔNG TIN ---------- BÁO CÁO NGHIÊN CỨU KHOA HỌC ĐỀ TÀI: HỆ THỐNG GIỮ XE TỰ ĐỘNG ĐINH HỒNG HÀ NGUYỄN THỊ PHƯƠNG THẢO BIÊN HÒA, THÁNG 12/2013 TRƯỜNG ĐẠI HỌC LẠC HỒNG KHOA CÔNG NGHỆ THÔNG TIN ---------- BÁO CÁO NGHIÊN CỨU KHOA HỌC ĐỀ TÀI: HỆ THỐNG GIỮ XE TỰ ĐỘNG SVTH : ĐINH HỒNG HÀ NGUYỄN THỊ PHƯƠNG THẢO GVHD :ThS. NGUYỄN VŨ DUY QUANG BIÊN HÒA, THÁNG 12/2013 LỜI CÁM ƠN Để hoàn thành đề tài này và có kiến thức như ngày hôm nay, đầu tiên chúng tôi xin gửi lời cảm ơn đến Ban Giám Hiệu cùng toàn thể Thầy Cô Khoa Công Nghệ Thông Tin – Trường Đại Học Lạc Hồng đã tận tình giảng dạy, truyền đạt kiến thức cũng như những kinh nghiệm quý báu cho chúng tôi trong suốt quá trình học tập tại trường. Chúng tôi cũng chân thành cảm ơn thầy Nguyễn Vũ Duy Quang đã tận tình hướng dẫn và quan tâm, động viên chúng tôi trong quá trình thực hiện đề tài. Chúng tôi cũng bày tỏ lòng biết ơn đến những người thân trong gia đình, bạn bè đã động viên và tạo mọi điều kiện giúp chúng tôi trong quá trình học tập cũng như trong cuộc sống. Mặc dù chúng tôi đã cố gắng hoàn thành tốt đề tài nhưng cũng không thể tránh khỏi những sai sót nhất định, rất mong được sự thông cảm và chia sẻ cùng quý Thầy Cô và bạn bè. Chúng tôi xin gửi lời chúc sức khỏe và thành đạt tới tất cả quý thầy cô cùng các bạn. Sinh viên thực hiện Đinh Hồng Hà Nguyễn Thị Phương Thảo MỤC LỤC LỜI CẢM ƠN MỤC LỤC DANH MỤC VIẾT TẮT DANH MỤC BẢNG DANH MỤC HÌNH DANH MỤC SƠ ĐỒ PHẦN MỞ ĐẦU ......................................................................................................................... 1 1. Lý do chọn đề tài ............................................................................................................. 1 2. Tình hình phát triển đề tài ............................................................................................... 1 2.1 Ngoài nước................................................................................................................. 2 2.2 Trong nước................................................................................................................. 2 3. Mục tiêu nghiên cứu ........................................................................................................ 3 4. Đối tượng nghiên cứu và phạm vi nghiên cứu ................................................................ 3 5. Phương pháp nghiên cứu ................................................................................................. 3 6. Kết cấu của đề tài ............................................................................................................ 4 CHƯƠNG 1: PHƯƠNG PHÁP NHẬN DẠNG BIỂN SỐ XE ......................................... 5 1.1Khái quát phương pháp nhận dạng biển số xe ............................................................... 5 1.2 Xác định vùng chứa biển số xe ...................................................................................... 6 1.2.1Phân vùng màu ........................................................................................................ 6 1.2.2 Gán nhãn và lọc vùng ứng viên .............................................................................. 7 1.2.2.1 Gán nhãn vùng ứng viên .................................................................................. 8 1.2.2.2 Lọc vùng ứng viên ......................................................................................... 10 1.3 Tách ký tự .................................................................................................................... 12 1.3.1 Quay ảnh ............................................................................................................... 12 1.3.1.1 Sơ lược về thuật toán quay ảnh ...................................................................... 12 1.3.1.2 Tách biên ảnh ................................................................................................. 12 1.3.1.3 Phép biến đổi Hough ...................................................................................... 13 1.3.1.4 Quay ảnh ........................................................................................................ 14 1.3.1.5 Làm mịn ảnh .................................................................................................. 17 1.3.2 Phân ngưỡng ảnh .................................................................................................. 17 1.3.2.1 Phân ngưỡng theo phương pháp Otsu ............................................................ 17 1.3.2.2 Ngưỡng cục bộ ............................................................................................... 19 1.3.3 Phân vùng ký tự .................................................................................................... 21 1.4 Nhận dạng biển số xe ................................................................................................... 25 1.4.1 Khái quát ............................................................................................................... 25 1.4.2 Nhận dạng ký tự .................................................................................................... 25 1.4.2.1 Giới thiệu phương pháp ................................................................................. 26 1.4.2.2 Giải thuật nhận dạng theo phân lớp Bayes .................................................... 27 1.5 Tiểu kết ........................................................................................................................ 28 CHƯƠNG 2: CÔNG NGHỆ NHẬN DẠNG VÔ TUYẾN - RFID ................................ 29 2.1 Giới thiệu chung về nhận dạng vô tuyến RFID........................................................... 29 2.1.1 Lịch sử phát triển của hệ thống RFID .................................................................. 29 2.1.2 Khái niệm RFID ................................................................................................... 31 2.2 Các thành phần của một hệ thống RFID ..................................................................... 32 2.2.1 Thẻ RFID .............................................................................................................. 33 2.2.2 Reader ................................................................................................................... 37 2.2.3 Database ................................................................................................................ 39 2.3 Giao thức thẻ RFID ..................................................................................................... 40 2.3.1 Thuật ngữ và khái niệm ........................................................................................ 40 2.3.2 Phương thức lưu trữ dữ liệu trên thẻ..................................................................... 41 2.3.3 Dải tần hoạt động của hệ thống RFID .................................................................. 43 2.4 Ứng dụng RFID ở Việt Nam ....................................................................................... 43 2.5 Tiểu kết ........................................................................................................................ 44 CHƯƠNG 3: CHƯƠNG TRÌNH GIỮ XE TỰ ĐỘNG .................................................... 45 3.1 Ứng dụng công nghệ mã nguồn mở ............................................................................ 45 3.1.1 Điều kiện cơ bản ................................................................................................... 45 3.1.2 Nhận dạng biển số xe ............................................................................................ 45 3.2 Ứng dụng công nghệ RFID vào chương trình. ............................................................ 46 3.3 Giao tiếp với cổng chắn ............................................................................................... 48 3.4 Giới thiệu hệ thống giữ xe tự động.............................................................................. 51 3.4.1 Chức năng chính ................................................................................................... 51 3.4.2 Mô tả các thiết bị cần có trong hệ thống............................................................... 52 3.4.3 Xây dựng cơ sở dữ liệu ......................................................................................... 53 3.4.4 Hoạt động của hệ thống giữ xe tự động ................................................................ 55 3.4.4.1 Tại cửa vào ..................................................................................................... 55 3.4.4.2 Tại cửa ra ....................................................................................................... 56 3.4.5 Chương trình đã xây dựng .................................................................................... 57 3.4.5.1 Giao diện chính .............................................................................................. 57 3.4.5.2 Quản lý người dùng ....................................................................................... 58 3.4.5.3 Quản lý người quản lý hệ thống..................................................................... 59 3.4.5.4 Quản lý nạp tiền ............................................................................................. 59 3.4.5.5 Cập nhật giá tiền ............................................................................................ 60 3.4.5.6 Cập nhật loại thẻ ............................................................................................ 61 3.5 Tiểu kết ........................................................................................................................ 61 PHẦN KẾT LUẬN .......................................................................................................... 62 TÀI LIỆU THAM KHẢO DANH MỤC VIẾT TẮT ANPR Auto Number Plate Recognition BMP Bitmap Portable EPA European Parking Association GIF Graphics Interchange Format HSI Hue – Saturation – Intensity IFF Identification Friend or Foe JPG Joint Photographic Experts Group OCR Optical Character Recognition PNG Portable Network Graphics RF Radio Frequency RFID Radio-frequency identification RGB Red – Green – Blue TIFF Tagged Image File Format DANH MỤC BẢNG Bảng 1.1 Bảng hiển thị bảy giá trị bất biến của hình 1.24 27 DANH MỤC HÌNH Hình 1.1 Ảnh chuyển từ RGB sang HSI 7 Hình 1.2 Ảnh sau khi lọc nhiễu 8 Hình 1.3 Ảnh sau khi tô màu theo đường biên không đệ qui 9 Hình 1.4 Bốn giá trị vùng ứng viên 10 Hình 1.5 Ảnh vùng chứa biển số xe sau khi lọc 11 Hình 1.6 Các bước quay ảnh 12 Hình 1.7 Ảnh sau khi tách biên 13 Hình 1.8 Phương trình đường thẳng ảnh sau khi tách biên 13 Hình 1.9 Biển số bị nghiêng bên trái 14 Hình 1.10 Mô tả những thông số quay ảnh bị nghiêng bên trái 14 Hình 1.11 Ảnh bị nghiêng bên trái sau khi quay 15 Hình 1.12 Biển số bị nghiêng bên phải 15 Hình 1.13 Mô tả những thông số quay ảnh bị nghiêng bên phải 16 Hình 1.14 Ảnh bị nghiêng bên phải sau khi quay 16 Hình 1.15 Ảnh sau khi làm mịn 17 Hình 1.16 Phân ngưỡng ảnh theo phương pháp Otsu 18 Hình 1.17 Phân ngưỡng ảnh theo phương pháp Otsu bị lỗi 19 Hình 1.18 Ảnh sau khi phân ngưỡng cục bộ 21 Hình 1.19 Sử dụng phép chiếu ngang cắt biển số thành 2 hàng 22 Hình 1.20 Ảnh mô tả phép chiếu dọc 23 Hình 1.21 Hình thể hiện hai thông số wi và hi 23 Hình 1.22 Kết quả sau khi tách ký tự 24 Hình 1.23 a) Hình gốc, b) Hình tịnh tiến, c) Hình giảm 40% kích thước, d) Hình gương, e) Hình quay 45 độ, f) Hình quay 90 độ. 26 Hình 2.1 Lịch sử phát triển RFID giai đoạn 1880-1960 29 Hình 2.2 Lịch sử phát triển RFID giai đoạn 1960-1990 30 Hình 2.3 Lịch sử phát triển RFID giai đoạn 1990-2009 31 Hình 2.4 Hệ thống RFID toàn diện 33 Hình 2.5 Layout của thiết bị mang dữ liệu, transponder 33 Hình 2.6 Cấu trúc của một thẻ thụ động 34 Hình 2.7 Một số loại thẻ tích cực 35 Hình 2.8 Cấu trúc của một thẻ bán tích cực 36 Hình 2.9 Cấu trúc layout cơ bản của một reader 38 Hình 2.10 Layout bộ nhớ của một thẻ minh họa 42 Hình 3.1 Mô hình hệ thống giữ xe tự động 51 Hình 3.2 Cơ sở dữ liệu 53 Hình 3.3 Giao diện chính của chương trình 57 Hình 3.4 Giao diện quản lý người dùng 58 Hình 3.5 Giao diện quản lý người quản lý hệ thống 59 Hình 3.6 Giao diện quản lý nạp tiền 60 Hình 3.7 Giao diện chương trình cập nhật giá tiền 60 Hình 3.8 Giao diện chương trình cập nhật loại thẻ 61 DANH MỤC SƠ ĐỒ Sơ đồ 1.1 Trình tự các bước trong phương pháp nhận dạng biển số xe 5 Sơ đồ 1.2 Thuật toán tô màu theo đường biên không đệ qui 9 Sơ đồ 1.3 Lọc vùng ứng viên 11 Sơ đồ 1.4 Phân ngưỡng theo phương pháp Otsu 18 Sơ đồ 1.5 Phân ngưỡng cục bộ. 20 Sơ đồ 1.6 Cắt biển số thành hai hàng 21 Sơ đồ 1.7 Tách ký tự biển số xe 24 Sơ đồ 1.8 Nhận dạng ký tư bằng phân lớp Bayes 25 Sơ đồ 3.1 Sơ đồ hệ thống giữ xe tự động có cửa vào và ra khác vị trí 52 1 PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay trên thế giới bên cạnh việc tăng trưởng kinh tế là sự phát triển của các ngành khoa học kỹ thuật nói chung, mà trong đó ngành công nghiệp sản xuất các phương tiện giao thông lại là một trong những ngành có tốc độ phát triển cực nhanh. Sự phát triển ấy, được thể hiện rõ ràng nhất thông qua hình ảnh các phương tiện giao thông trên thế giới ngày một tăng cao và đa dạng. Tuy nhiên, điều đó lại gây ra một áp lực đối với những người và cơ quan các cấp quản lý, làm cho công tác quản lý và giám sát sẽ khó khăn hơn.Và đây cũng là một trong những vấn nạn ở Việt Nam. Công tác quản lý phương tiện giao thông nói chung và quản lý ô tô, xe máy là vô cùng phức tạp cũng như công tác phát hiện, xử phạt các hành vi vi phạm giao thông, chống trộm, sẽ tốn nhiều thời gian và công sức hơn. Để làm giảm lượng nhân lực trong việc công tác quản lý, kiểm soát phương tiện giao thông, trên thế giới đã nhanh chóng xây dựng hệ thống giám sát tự động đối với các phương tiện giao thông. Hệ thống này đã được sử dụng rộng rãi tuy nhiên ở Việt Nam đây vẫn là một lĩnh vực mới mẻ và chưa thực sự tự động hóa. Do đó, chúng tôi chọn làm đề tài “Hệ thống giữ xe tự động” với mục đích để tìm hiểu nhằm trợ giúp cho công tác giám sát, quản lý các phương tiện giao thông một cách hiệu quả, dễ dàng, nhanh chóng và tự động hơn. Chúng tôi tin ở Việt Nam mình trong tương lai gần hệ thống này sẽ được sử dụng rộng rãi. 2. Tình hình phát triển đề tài Những hệ thống nhận dạng ký tự (OCR - Optical Character Recognition) đang được phát triển hàng ngày với độ ổn định cao nhằm phục vụ cho xu hướng tự động hóa của con người. Trong đó hệ thống nhận dạng biển số xe là một trong những hệ thống quan trọng góp phần giải quyết nạn kẹt xe đang tồn tại ở những quốc gia có lưu lượng xe lưu thông dày đặc nhưng cơ sở hạ tầng không phát triển kịp để đáp ứng nhu cầu đó. Bên cạnh đó, nhận dạng biển số xe được ứng dụng rất nhiều trong thực tế. Với những bãi giữ xe, họ cần một công cụ vừa giữ xe và trả xe nhanh nhằm giảm tải kẹt xe vào giờ cao điểm, vừa có độ an toàn cao để tránh trường hợp mất xe.Với trạm thu phí, họ cần một công cụ giảm số lượng nhân công, chỉ với một người có thể quản lý toàn bộ khu 2 vực thu phí mà không cần tốn nhiều công sức.Với cảnh sát giao thông, họ cần một công cụ giúp họ kiểm soát được số lượng xe lưu thông trên đường và xác định chính xác những xe máy vi phạm giao thông mà không cần truy đuổi… Trên đây là những ví dụ điển hình về khả năng ứng dụng của hệ thống nhận dạng biển số xe. Hệ thống giữ xe tự động là vấn đề được rất nhiều quốc gia quan tâm và trở thành đề tài nóng hổi đối với một số quốc gia đang phát triển theo hướng tự động hóa. Sau đây là một số hệ thống giữ xe tự động của một số nước trên thế giới và nước ta. 2.1 Ngoài nƣớc Hệ thống giữ xe tự động Budapest – Parksafe 580 của tập đoàn WORH (Đức): Ý tưởng tạo ra 200 địa điểm đỗ xe công cộng trong không gian 300 mét vuông ở phía bên ngoài đường phố của một tòa nhà nổi tiếng như một phần của một dự án cải tạo đã được giải thưởng 2009 EPA do European Parking Association công nhận. Hệ thống giữ xe tự động CHD-DX-L010 Control box and barrier gates là sản phẩm mới nhất của tập đoàn Shenzhen Newabel Electronics (Trung Quốc): cấu hình một cách tự do, hỗ trợ hiển thị chi phí bên ngoài màn hình, camera, đầu đọc thẻ RF vv. Nó hỗ trợ rất nhiều chức năng có sẵn, đếm thời gian thực cho chỗ đậu xe, khi không còn chỗ đậu, nó cấm xe vào cho đến khi có không gian trống. 2.2 Trong nƣớc Hệ thống giữ xe thông minh Green Parking do công ty Isoftco phối hợp với Phú Lê Telecom thực hiện: sử dụng hộp đen lưu trữ thông tin “thông minh” để tìm kiếm lại thông tin xe vào ra dựa vào số thẻ, số xe và tra cứu qua lại camera vào ra. Hệ thống giữ xe ezVIP (Very Intelligent Parking) do công ty AIO sản xuất: sử dụng các công nghệ nhận dạng hiện đại, tiên tiến bậc nhất hiện nay: công nghệ nhận dạng vân tay và công nghệ thẻ cảm ứng. Những dự án, sản phẩm trên đây là những tài liệu quý báu giúp chúng tôi định được hướng nghiên cứu của đề tài, từ đó chúng tôi rút ra được những phương pháp cần thiết và tối ưu trong mỗi hệ thống, tìm ra phương pháp mới để ứng dụng và hoàn thành tốt đề tài của chúng tôi. 3 3. Mục tiêu nghiên cứu Xây dựng hệ thống giữ xe tự động: - Chụp ảnh biển số xe. - Đọc thẻ RFID. - Đưa/lấy thẻ xe. - Mở/đóng cổng chắn. - Một số chức năng cần thiết khác. 4. Đối tƣợng nghiên cứu và phạm vi nghiên cứu - Đối tượng nghiên cứu: bãi giữ xe gắn máy ở Việt Nam. - Phạm vi nghiên cứu: tất cả những hệ thống giữ xe gắn máy ở Việt Nam. 5. Phƣơng pháp nghiên cứu - Khảo sát, tìm hiểu và thu thập tài liệu, hình ảnh về biển số, đề tài đã nghiên cứu trước đây. - Tìm hiểu các bước nhận dạng một biển số xe bao gồm: xác định vị trí biển số xe, tách ký tự trên biển số và nhận dạng ký tự trên biển số. - Tìm hiểu, lựa chọn những phương pháp cần thiết của mỗi bước trong quá trình nhận dạng biển số. - Tìm hiểu, nghiên cứu xử lý - nhận dạng biển số xe Việt Nam. - Kế thừa những phương pháp đạt kết quả tốt và phù hợp với nội dung cần đạt được của đề tài. - Phát triển và cải tiến phương pháp đã có ở những đề tài trước để xây dựng chương trình hướng tới kết quả tốt hơn. - Tìm ra một hướng đi mới trong mỗi bước cần làm của đề tài, đặc biệt là trong giải thuật nhận dạng. - Tìm hiểu công nghệ nhân dạng vô tuyến RFID. - Tìm hiểu phương thức lưu trữ dữ liệu trên thẻ RFID nhằm phục vụ lưu trữ thông tin gửi và trả xe trên thẻ RFID. 4 6. Kết cấu của đề tài Báo cáo này được trình bày thành ba phần chính: Phần mở đầu, phần nội dung và phần kết luận. Phần mở đầu Giới thiệu sơ lược về lý do chọn đề tài, lịch sử nghiên cứu, mục tiêu nghiên cứu, đối tượng và phạm vi nghiên cứu, phương pháp nghiên cứu từ đó đem lại cho mọi người một cái nhìn tổng quan nhất về đề tài. Phần nội dung Chƣơng 1: Phương pháp nhân dạng biển số xe Trình bày nội dung về trình tự các bước trong quá trình nhận dạng biển số. Đưa ra một số phương pháp rồi so sánh lựa chọn phương pháp tối ưu.. Chƣơng 2: Công nghệ RFID Tìm hiểu phương pháp đọc và lưu trữ dữ liệu trên thẻ từ, thẻ RFID Chƣơng 3: Chương trình giữ xe tự động Giới thiệu phần mềm nhận dạng biển số xe SimpleLPR. Giới thiệu về chương trình và kết quả đạt được sau khoảng thời gian nghiên cứu. Phần kết luận 5 CHƢƠNG 1: PHƢƠNG PHÁP NHẬN DẠNG BIỂN SỐ XE 1.1 Khái quát phƣơng pháp nhận dạng biển số xe Từ ảnh đầu vào (ảnh RGB) ta lọc ra vùng có chứa biển số xe, sau đó trích xuất những ký tự có trên biển số và lần lượt so sánh những ký tự vừa trích xuất với tập tin mẫu trong cơ sở dữ liệu để nhận dạng biển số. Chi tiết các bước của phương pháp nhận dạng được trình bày như sau: Ảnh đầu vào (RGB) Chuyển sang mô hình màu HSI Chia biển số thành 2 hàng Tách riêng từng ký tự trên mỗi hàng Xác định vùng chứa biển số xe Tính bảy mômen bất biến Tính góc nghiêng biển số Quay biển số Nhận dạng ký tự theo phân lớp Bayes Nhị phân biển số theo ngưỡng Sơ đồ 1.1. Trình tự các bước trong phương pháp nhận dạng biển số xe 6 1.2 Xác định vùng chứa biển số xe 1.2.1 Phân vùng màu Bằng mắt thường ta dễ dàng nhận biết vùng chứa biển số xe vì nó có sự khác biệt về màu sắc với vùng khác trong toàn bộ ảnh. Từ đó, ta sử dụng mô hình màu HSI để phân vùng màu tại vùng chứa biển số với vùng khác trong ảnh hay nói cách khác thì mô hình màu HSI đổi tất cả vùng có giá trị tương tự với giá trị vùng chứa biển số thành 1 (màu trắng) và vùng còn lại thành 0 (màu đen). Những thông số của mô hình màu được sử dụng để phát hiện vùng ứng viên và những đặc tính hình học của biển số xe để giảm số lượng vùng ứng viên có khả năng chứa biển số xe đều dựa trên những khảo sát thực tế. Trước đây để phát hiện vùng ứng viên chứa biển số xe, ta thường đặt ra những giá trị mặc định để phân vùng, công thức cơ bản R(x, y) >R; G(x, y) >G; B(x, y) >B R(x, y) - G(x, y) >RG; R(x, y) - B(x, y) >RB (1.1) Trong đó R, G, B : Red, Green, Blue. , : là một số cho trước. Tuy nhiên, phương pháp trên chỉ tốt khi ảnh đầu vào được chụp trong điều kiện ánh sáng tốt, nếu ảnh được chụp trong thời tiết xấu, ánh sáng không đồng đều thì tỉ lệ chính xác rất thấp. Trong phần này, đề tài đưa ra hai thông số là giá trị trung bình (mean) và độ lệch chuẩn (standard deviation) để phát hiện vùng ứng viên chứa biển số xe. Điều thuận lợi là phương pháp này không phụ thuộc hoàn toàn vào điều kiện thời gian (sáng, trưa, chiều, tối) và môi trường xung quanh. Công thức tổng quát [3] 1, S ( x, y )  ( S   S ) & I ( x, y )   I  1.0*  S )  btrang    (1.2) 0, otherwise   Trong đó: S(x, y) : độ bão hòa (Saturation) tại điểm x, y. 7 I(x, y) : độ chói (Intensity) tại điểm x, y. S, I : giá trị trung bình của S và I. S, I: độ lệch chuẩn của S và I. Hình 1.1. Ảnh chuyển từ RGB sang HIS 1.2.2 Gán nhãn và lọc vùng ứng viên Sau khi phân vùng màu, ảnh xuất hiện rất nhiều đốm trắng và những vùng trắng nhỏ không có khả năng chứa biển số xe, điều này làm cho bức ảnh bị nhiễu và tăng thời gian tính toán của chương trình. Ở bước này, ta sẽ giảm nhiễu, lọc những vùng ứng viên không chứa biển số và loại chúng ra. Để giảm nhiễu ảnh, chúng ta sử dụng một phép toán hình thái học là phép mở (Opening). Phép mở sử dụng để làm mịn đường viền của đối tượng, cắt những đường biên hẹp, loại bỏ những điểm lồi lõm. Phép mở sử dụng mặt nạ B (B là ma trận vuông m x m) để xác định kích thước tối đa vùng sẽ bị lọc. Do đó m càng lớn thì vùng bị lọc càng lớn, điều này có thể ảnh hưởng đến kích thước của những vùng còn lại do mặt nạ B quét trên toàn bộ ảnh. Ở đây, ta cài đặt ma trận mặt nạ B có kích thước 3x3 làm mặt nạ chuẩn trong phép mở. 8 Hình 1.2. Ảnh sau khi lọc nhiễu 1.2.2.1 Gán nhãn vùng ứng viên Ảnh nhận được ở bước trên chỉ còn lại một vài vùng ứng viên có khả năng chứa biển số, ta sử dụng thuật toán gãn nhãn thành phần liên thông để tính những thông số cần thiết cho việc xác định vùng chứa biển số. Một trong những thuật toán phù hợp với ma trận ảnh có kích thước lớn là thuật toán tô màu theo đường biên không đệ qui. Ý tưởng thuật toán như sau:  Cho trước điểm s nằm bên trong đường cong bất kỳ khép kín.  Loang sang phải và lưu hoành độ bên nhất vào stack.  Lặp cho đến khi stack rỗng o Lấy trong stack ra o Tô sang trái và gọi hoành độ bên trái là xmin o Đi lên và loang sang phải, sang trái để tìm các hoành độ bên phải và lưu vào stack o Đi xuống và loang sang phải, sang trái để tìm các hoành độ bên phải và lưu vào stack o Quay về đầu vòng lặp. 9 Bắt đầu f(x,y) = = 255 Stack = LoangPhai(f,x,y,BC) S IsEmpty (Stack)==0 Đ p = Pop(Stack) Xmin = ToTrai (f,p.x,p.y,FC,BC) TimCacXBenPhaiNhat( stack,f,p.x, p.y-1,xmin,FC,BC) TimCacXBenPhaiNhat( stack,f,p.x, p.y+1,xmin,FC,BC) Kết thúc Sơ đồ 1.2. Thuật toán tô màu theo đường biên không đệ qui Hình 1.3. Ảnh sau khi tô màu theo đường biên không đệ qui 10 1.2.2.2 Lọc vùng ứng viên Trong bước này, ta dựa vào những đặc tính hình học quan trọng của một biển số xe khi quan sát bằng mắt thường và tính toán, ta có được bốn giá trị cần thiết từ mỗi thành phần liên thông được gán nhãn gồm cmax, cmin, rmax,. rmin. Rmax Cmin Cmax Rmin Hình 1.4. Bốn giá trị vùng ứng viên Sau đó xác định vùng ứng viên chứa biển số xe dựa trên hai thông số diện tích vùng ứng viên và tỉ lệ cạnh.  Diện tích là số lượng điểm ảnh của vùng ứng viên. S = (cmax - cmin)( rmax - rmin) (1.3-1)  Tỉ lệ cạnh là tỉ lệ giữa chiều dài với chiều rộng hình chữ nhật ngoại tiếp vùng ứng viên. PA  cmax  cmin  1 rmax  rmin  1 (1.3-2) Trong đó: S : diện tích PA : tỉ lệ cạnh cmax : tọa độ điểm lớn nhất theo trục X cmin : tọa độ điểm nhỏ nhất theo trục X rmax : tọa độ điểm lớn nhất theo trục Y rmin : tọa độ điểm nhỏ nhất theo trục Y Quy định đối với kích thước biển số xe gắn máy ở Việt Nam có chiều cao 140mm, chiều dài 190mm. Do đó ta có tỉ lệ PA đối với kích thước thât của biển số là 1.35. Giới