Tài liệu Xây dựng chương trình nhận dạng biển số xe gắn máy tự động ở việt nam

- 1 - PHẦN MỞ ĐẦU Lý do chọn đề tài Trong thời đại phát triển mạnh mẽ của công nghệ thông tin, khái niệm ảnh số đã trở nên thông dụng với hầu hết mọi người trong xã hội từ những chiếc máy chụp ảnh cao cấp đến những chiếc điện thoại di động tích hợp chụp ảnh thì việc thu nhận ảnh số đã dễ dàng hơn bao giờ hết. Do đó, xử lý ảnh đang là một lĩnh vực được mọi người quan tâm và là môn học chuyên ngành đối với sinh viên công nghệ thông tin trên cả nước. Ngoài ra, xử lý ảnh còn liên quan đến nhiều ngành khoa học khác như hệ thống thông tin, nhận dạng (khuôn mặt, dấu vân tay, …). Đối với mỗi con người chúng ta, việc học và phân biệt được sự khác nhau giữa từng ký tự thật dễ dàng nhưng để máy tính làm được điều tương tự thì không dễ dàng chút nào, việc này cần đến những người có kiến thức tốt về xử lý ảnh mới có thể giúp máy tính học và phân biệt được ký tự nhưng kết quả lại không như mong muốn. 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 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. - 2 - Vì vậy, việc nghiên cứu về hệ thống nhận dạng biển số xe tự động là cần thiết và có ý nghĩa rất lớn về mặt ứng dụng, đáp ứng nhu cầu tự động hóa của xã hội. Từ những yêu cầu đó, chúng em xin thực hiện đề tài “Xây dựng chương trình nhận dạng biển số xe gắn máy tự động ở Việt Nam”. Lịch sử nghiên cứu Trong xu thế tự động hóa, xử lý ảnh nói chung và giải thuật nhận dạng nói riêng có một vai trò cực kỳ quan trọng, là một nhân tố quyết định đến sự thành công của một chương trình. Nhận dạng biển số 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 quốc gia đang phát triển theo hướng tự động hóa. Vì điều đó, một số cá nhân và tập thể trong lĩnh vực xử lý ảnh đã nghiên cứu ở những góc độ, khía cạnh, phương pháp khác nhau. Đầu tiên là đề tài “Algorithmic and mathematical principles of automatic number plate recognition systems” (Ondrej Martinsky, BRNO University of Technology, 2007). Đề tài này là một phần trong kế hoạch nghiên cứu “SecurityOriented reseach in information technology, msm 0021630528” của đại học kỹ thuật BRNO. Đề tài trình bày chi tiết các bước nhận dạng ký tự, trong đó có so sánh giữa những phương pháp rồi chọn một phương pháp tốt nhất cho một công việc cụ thể. Đề tài không được đánh giá cao vì tỉ lệ nhận dạng thành công trong nhiều môi trường khác nhau không cao. Đề tài “Segmenting the license plate region using a color model” (Kaushik Deb and Kang-Huyn Jo, University of Ulsan, South Korea, 2002) đã đưa ra phương pháp xác định vùng biển số xe hoàn toàn mới bằng cách sử dụng mô hình màu HSI và thành phần liên thông, đây là ý tưởng mới nhưng đề tài chỉ dừng lại ở bước tách ký tự trên biển số mà không nghiên cứu giải thuật nhận dạng. Đề tài “A real-time vehicle license plate region system” (Bar-Hen Ron, Israel Institute of Technology, 2002) tập trung nhiều về xử lý của mạng Nơron. Đề tài cũng cho ta thấy cách tính chính xác hơn cho những tham số điều kiện.. - 3 - Bài báo “Pixel Clustering Based Partitioning Techique for Character Recognition in Vehicle License Plate” của nhóm tác giả Siddhartha Choubey – G.R.Sinha – Bhagwati Charan Patel – Abha Choubey – Kavita Thakur đạt giải 3 trong cuộc thi ICMLC 2011, tập trung trình bày hai giải thuật phân vùng ký tự, tách riêng từng ký tự theo phép chiếu ngang và phép chiếu dọc. Đề tài “Phân tích bố cục và nhận dạng ảnh công văn tiếng Việt” (Võ Đại Bình – Nguyễn Thị Tú Mi – Nguyễn Thùy Giang, Trường Đại Học Nông Lâm TPHCM, 2002) trình bày rất tốt phân tách từng khối ảnh với tỉ lệ thành công cao, bên cạnh đó đề cập nhiều đến giải thuật tính góc nghiêng, quay ảnh và tách ký tự trong văn bản. Hình 1. Hệ thống ORC trong phân tích bố cục văn bản Những đề tài nghiên cứu và tài liệu trên đây là những tài liệu quý báu giúp chúng em định được hướng nghiên cứu của đề tài, từ đó chúng em rút ra được những phương pháp cần thiết và tối ưu trong mỗi đề tài, 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 em. Mục tiêu nghiên cứu Xây dựng chương trình nhận dạng được biển số xe gắn máy từ ảnh chụp đầu vào và hiển thị dưới dạng văn bản. Đối tượng nghiên cứu và phạm vi nghiên cứu - Đối tượng nghiên cứu : biển số xe gắn máy ở Việt Nam. - 4 - - Phạm vi nghiên cứu : tất cả những biển số xe gắn máy ở Việt Nam, trong đó có những biển số mới nhất được ban hành ở Việt Nam với hàng dưới gồm 5 ký tự. 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ố. - 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. Những đóng góp mới của đề tài - những vấn đề mà đề tài chưa thực hiện được - Đề tài đưa ra hướng mới trong giải thuật nhận dạng theo phân lớp Bayes dựa trên xác suất tính được từ những mômen bất biến của ký tự đối với tập tin mẫu. - Tạo tiền đề cho việc xây dựng hệ thống nhận dạng biển số xe sau này. - Tuy nhiên, đề tài còn tồn tại một số khó khăn nhất định được như kích trước tập tin mẫu nhỏ. 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, những đóng góp - 5 - và những vấn đề tồn tại của đề tài để 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: Khái quát về xử lý ảnh Trình bày những khái niệm, định nghĩa cơ bản về ảnh số, xử lý ảnh số. Chương 2: 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 3: Chương trình nhận dạng biển số xe tự động. 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 - 6 - CHƯƠNG 1: KHÁI QUÁT VỀ XỬ LÝ ẢNH 1.1 Ảnh số 1.1.1, Khái niệm về ảnh Ảnh được định nghĩa là một hàm hai chiều, f(x, y), trong đó x và y là mặt phẳng tọa độ, f tại vị trí x, y được gọi là mức xám của ảnh tại điểm đó [6]. Hình 1.1. Ảnh hai chiều 1.1.2, Mô hình màu RGB Chúng ta có bảy màu chuẩn là đỏ, cam, vàng, lục, lam, chàm, tím. Nhưng thực tế ta không thể nhìn thấy ranh giới giữa các dãy màu vì chúng liên lục với nhau. Xét về cấu tạo thì tất cả các màu đều được liên kết bởi ba màu cơ bản Red (đỏ), Green (xanh lá), Blue (xanh dương). Hình 1.2. Mô hình màu RGB Mỗi màu cơ bản được mã hóa bởi 8bit, vì vậy mắt người có thể cảm nhận được hơn 16 triệu màu nhưng thực tế mắt người chỉ cảm nhận sự khác biệt giữa các màu khi giá trị giữa các màu chênh lệch lớn. Mô hình màu RGB bao gồm ba mặt phẳng độc lập. Vì vậy, để sử dụng mô hình màu RGB cho xử lý ảnh thì ảnh phải được biểu diễn theo một mặt phẳng màu. - 7 - 1.1.3, Mô hình màu HSI Mô hình màu HSI là mô hình dựa trên việc miêu tả màu sắc rất tự nhiên và trực quan đối với mắt người, do đó là công cụ tốt trong những thuật toán xử lý ảnh [11]. Mô hình màu HSI được biểu diễn bởi 3 thành phần: Hue (sắc lượng), Saturation (độ bão hòa), Intensity (độ chói). White I Green Cyan S Yellow H Blue Red Magenta Black Hình 1.3. Mô hình màu HSI 1.1.3.1, Hue Mô tả màu của chính đối tượng và dùng để phân biệt sự khác nhau giữa các màu như vàng, xanh, đỏ,… Hue được biểu thị từ 0 đến 360 độ. Trong đó, 0 độ là màu đỏ, 60 độ là màu vàng, 120 độ là màu xanh lá, 180 độ là màu xanh lơ, 240 độ là màu xanh dương và 300 độ là màu hồng sẫm. Hình 1.4 Hue - 8 - 1.1.3.2, Saturation Mô tả độ thuần của một màu hay khoảng cách của màu tới điểm có cường độ cân bằng (ảnh xám). Phạm vi của Saturation từ 0 đến 1. Hình 1.5. Saturation 1.1.3.3, Intensity Mô tả độ sáng của một màu. Intensity có phạm vi từ 0 đến 1. Trong đó, 0 là màu đen, 1 là màu trắng. Hình 1.6. Intensity Công thức chuyển đổi từ mô hình màu RGB sang mô hình màu HSI [7]. ⎧ θ H =⎨ ⎩ 360 − θ if B ≤ G if B > G (1.1-1) Trong đó: ⎧ ⎫ 1 ⎪ ⎪ 2 [( R − G ) + ( R − B)] θ = cos ⎨ ⎬ 1 2 2 ⎪⎩ ⎡⎣ ( R − G ) + ( R − B )(G − B ) ⎤⎦ ⎭⎪ −1 S = 1− 3 [ min(R, G, B)] ( R + G + B) (1.1-2) (1.1-3) - 9 - 1 I = ( R + G + B) 3 (1.1-4) Chú ý: Nếu S = 0 thì H không xác định. Nếu I = 0 thì S không xác định. 1.2 Một số khái niệm về xử lý ảnh 1.2.1, Xử lý ảnh là gì? Xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả như mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh tốt hơn hoặc một kết luận [1]. Ảnh “tối ưu” Ảnh Xử lý ảnh Kết luận Hình 1.7. Quá trình xử lý ảnh 1.2.2, Các phép hình thái học Hình thái là thuật ngữ chỉ sự nghiên cứu về cấu trúc hay tính chất hình học của đối tượng trong ảnh [10]. Mục tiêu của việc ứng dụng các phép toán hình thái học nhằm đơn giản hóa tín hiệu bằng việc loại bỏ các thông tin không cần thiết Phần lớn các phép toán hình thái được định nghĩa từ hai phép toán cơ bản là phép giãn nở ( Dilation) và phép bào mòn (Erosion). 1.2.2.1, Dilation Cho A và B là hai tập trong Z, giãn nở A bởi B kí hiệu A ⊕ B được định nghĩa như sau { } A ⊕ B = z ( B) z ∩ A ≠ ∅ Lấy tập (1.2) dời đi một độ dời z sao cho tập vừa dời giao với tập A khác rỗng. - 10 - Lưu ý phương trình này dựa trên tập phản xạ của B, nhưng do B thường là = B. đối xứng nên Hình 1.8. Phép giãn nở ảnh 1.2.2.2, Erosion Cho A và B là 2 tập trong Z, bào mòn A bởi B kí hiệu là A Θ B .được định nghĩa như sau AΘB = { z ( B ) z ∩ Ac = ∅} (1.3) c Trong đó A là ảnh ngược với ảnh A. Hình 1.9. Phép bào mòn ảnh 1.2.2.3, Opening Phép mở của một tập hợp A bởi phần tử có cấu trúc B, ký hiệu A o B được định nghĩa như sau A o B = ( AΘ B ) ⊕ B Trong đó Α Θ B : phép bào mòn ảnh. A ⊕ B : phép giản nở ảnh (1.4) - 11 - 1.2.2.4, Closing Phép đóng của một tập hợp A bởi phần tử có cấu trúc B, ký hiệu A•B được định nghĩa như sau A • B = ( A ⊕ B )Θ B (1.5) Trong đó Α Θ B : phép bào mòn ảnh. A ⊕ B : phép giản nở ảnh 1.2.3, Kỹ thuật nâng cao chất lượng ảnh 1.2.3.1, Lược đồ xám Là một đồ thị dạng thanh biểu diễn tần suất xuất hiện các mức xám của ảnh [8]. Trong đó trục hoành biểu diễn giá trị mức xám của ảnh có giá trị từ 0 đến 255, trục tung biểu diễn tần suất xuất hiện mức xám của ảnh. Công thức tổng quát p (rk ) = nk / MN (1.6) Trong đó p (rk ) : tần suất xuất hiện mức xám rk nk : giá trị điểm ảnh tại vị trí k Hình 1.10. Lược đồ xám của ảnh 1.2.3.2, Phân ngưỡng theo phương pháp Otsu Đầu tiên, sử dụng lược đồ xám (histogram) ta sẽ nhận được đồ thị biểu diễn tần suất xuất hiện các mức xám của ảnh [2]. L −1 p i = ∑ ni / ( M * N ) i=0 Trong đó: (1.7-1) - 12 - ni: số lượng điểm ảnh của giá trị i. L : 1, 2, …, 256 p0 + p1 + p2 + … + pL-1 = 1 Tiếp theo, ta chọn một ngưỡng T(k) = k, (0 < k < L – 1) để phân ảnh đầu vào thành hai lớp C1 (tập hợp tất cả những điểm ảnh có giá trị <= k) và C2 (tập hợp tất cả những điểm ảnh có giá trị > k). Tỉ lệ lớp C1 với số lượng điểm ảnh đến k với tổng số lượng điểm ảnh được ký hiệu P1(k), tương tự C2 ký hiệu là P2(k). P1 ( k ) = P2 ( k ) = k ∑ i=0 L −1 ∑ i = k +1 pi (1.7-2) pi = 1 − P1 ( k ) (1.7-3) Sau đó, ta tính giá trị trung bình m1 của lớp C1 k m1 ( k ) = ∑ iP (i / C1 ) = i =0 1 k ∑ iPi P1 ( k ) i = 0 (1.7-4) Tương tự, ta tính giá trị trung bình m2 của lớp C2 L −1 1 L −1 m2 (k ) = ∑ iP(i / C2 ) = ∑ iPi P2 (k ) i = k +1 i = k +1 (1.7--5) Theo Otsu, ta sẽ tính ngưỡng k* mà giá trị tại đó sự chênh lệch giữa hai đoạn (màu nền và màu ký tự) đạt giá trị cực đại, ký hiệu σ B2 (k *) , được tính theo công thức sau σ B2 (k*) = max σ B2 (k ) 0≤ k ≤ L −1 (1.7-6) Trong đó σ B2 là phương sai của hai lớp C1 và C2, ta có σ B2 = P1 ( m1 − mG ) 2 + P2 ( m2 − mG ) 2 = P1 P2 ( m1 − m2 ) 2 = ( mG P1 − m ) P1 (1 − P1 ) 2 Từ công thức trên, ta suy ra (1.7-7) - 13 - [mG P1 (k ) − m(k )]2 σ (k ) = P1 ( k )[1 − P1 ( k )] 2 B (1.7-8) Trong đó: mG : giá trị trung bình của ảnh. mG = L −1 ∑ ip i=0 i hoặc mG = P1 m1 + P2 m 2 (1.7-9) m(k) : giá trị trung bình đến ngưỡng k mk = k ∑ ip i=0 i (1.7-10) Nếu có nhiều giá trị σ B2 lớn nhất bằng nhau, ta sẽ chọn k có giá trị lớn nhất làm ngưỡng k*, sau đó ta thực hiện nhị phân biển số theo theo ngưỡng. ⎧1 if f(x, y) > k* g ( x, y ) = ⎨ ⎩0 if f(x, y) ≤ k* (1.7-11) Trong đó: g(x, y) : ảnh đầu ra f(x ,y) : ảnh đầu vào x = 0, 1, 2, …, M-1 y = 0, 1, 2, …, N-1 1.2.3.3, Lọc trung vị Lọc trung vị (median filter) là một kĩ thuật lọc phi tuyến (non-linear), nó khá hiệu quả đối với hai loại nhiễu: nhiễu đốm (speckle noise) và nhiễu muối tiêu (saltpepper noise). Kĩ thuật này là một bước rất phổ biến trong xử lý ảnh [9]. Công thức tổng quát f ( x, y) = median{ g(s, t)} ( s,t )∈Sxy (1.8) Ý tưởng chính của thuật toán lọc trung vị như sau: ta sử dụng một cửa sổ lọc (ma trận m x m, m thường là số lẻ) quét qua lần lượt từng điểm ảnh của ảnh đầu vào. Tại vị trí mỗi điểm ảnh lấy giá trị của các điểm ảnh tương ứng trong vùng m x m của ảnh gốc gán vào ma trận lọc. Sau đó sắp xếp các điểm ảnh trong ma trận này theo thứ tự tăng dần (hoặc giảm dần). Cuối cùng, gán điểm ảnh nằm chính giữa - 14 - (trung vị) của dãy giá trị điểm ảnh đã được sắp xếp ở trên cho giá trị điểm ảnh đang xét của ảnh đầu ra. 5 5 4 4 3 3 2 2 1 Phần tử trung vị trước khi sắp xếp 1 Phần tử trung vị sau khi sắp xếp Hình 1.11. Kỹ thuật lọc trung vị 1.2.4, Một số kỹ thuật khác 1.2.4.1, Phép biến đổi Hough Trong phân tích hình ảnh kỹ thuật số, thường xuất hiện hình dạng đơn giản, chẳng hạn như đường thẳng. Biến đổi Hough là phương pháp biến đổi tuyến tính để phát hiện các đường thẳng [3] . Trong ảnh, các đường thẳng được mô tả bằng : y = mx + b. Các điểm ảnh là (x, y). Trong biến đổi Hough, ý tưởng chính là xem xét các đặc điểm của đường thẳng nhưng không phải là điểm (xo, yo), (x1, y2)… thay vào đó, ta xem xét các đặc điểm của tham số góc m và các tham số b . Với một điểm ảnh (x, y) bất kỳ trên hình luôn tồn tại hai tham số r (RHO), θ (Theta) thỏa mãn công thức sau ⎛ cosθ ⎞ ⎛ r ⎞ y = ⎜− ⎟ x +⎜ ⎟ ⎝ sinθ ⎠ ⎝ sinθ ⎠ Hay r = xcos θ + ysin θ với θ ∈[0,2π), r ≥0 , r∈ R. (1.9-1) - 15 - Hình 1.12. Đồ thị mô tả phép biến đổi Hough Sau khi chạy phép biến đổi Hough ta tìm được θm và rm và đường thẳng đi qua nhiều điểm trên ảnh nhất. Tương ứng với công thức ⎛ cosθm ⎞ ⎛ r ⎞ y = ⎜− ⎟ x +⎜ ⎟ ⎝ sinθm ⎠ ⎝ sinθm ⎠ (1.9-2) Trong đó cosθm là hệ số góc của phương trình đường thẳng. sinθm Gọi α là góc cần tính, ta có cosθ m = tg (α ) sin θ m (1.9-3) -cotg(θm)=tg(α) (1.9-4) − hay Mặt khác o sinα = - cos(α + 90 ) (1.9-5) o cosα = sin(α+90 ) (1.9-6) o => tgα = -cotg(90 +α) (1.9-7) Từ công thức (1.9-4) và (1.9-7), ta tính được góc α o α = θm - 90 (1.9 – 8) - 16 - 1.2.4.2, Trích biên ảnh Biên của tập A kí hiệu là β(A) được trích ra bằng cách ta bào mòn A bởi B, lấy ảnh A ban đầu trừ đi ảnh đã bào mòn, ta sẽ được biên [6]. Công thức tổng quát β(A) = A – (A Θ B) (1.10) Hình 1.13. Ảnh sau khi được tách biên 1.2.5, Nhận dạng ảnh 1.2.5.1, Mômen bất biến Mômen bất biến là những mômen được trích ra từ những đặc trưng riêng của một đối tượng mà những mômen đó không thay đổi đối với phép quay, phép tính tiến, phép tỉ lệ [6]. Một đối tượng hay chính xác hơn là một ký tự bao gồm bảy mômen bất biến, ký hiệu φ1 , φ2 , φ3 , φ4 , φ5 , φ6 , φ7 . Bảy mômen bất biến là yếu tố quyết định đến độ chính xác trong quá trình nhận dạng, do đó khi tính toán cần phải thật cẩn thận và chính xác. Ta cũng xây dựng tập tin mẫu dựa trên bảy mômen bất biến và sử dụng nó trong phân lớp Bayes. Công thức tổng quát φ1 = η20 + η02 (1.11-1) φ2 = (η20 −η02 )2 + 2η112 (1.11-2) - 17 - φ3 = (η30 − 3η12 )2 + (3η21 −η03 )2 (1.11-3) φ4 = (η30 +η12 )2 + (η21 +η03 )2 (1.11-4) φ5 = (η30 − 3η12 )(η30 +η12 )[(η30 +η12 )2 − 3(η21 +η03 )2 ] + (3η21 −η03 )(η21 +η03 )[3(η30 +η12 )2 − (η21 +η03 )2 ] φ6 = (η20 −η02 )[(η30 + η12 )2 − (η21 + η03 )2 ] +4η11 (η30 + η12 )(η21 + η03 ) φ7 = (3η 21 − η03 )(η30 + η12 )[(η30 + η12 ) 2 − 3(η 21 + η03 ) 2 ] + (3η12 − η30 )(η 21 + η03 )[3(η30 + η12 ) 2 − (η 21 + η03 ) 2 ] (1.11-5) (1.11-6) (1.11-7) Với ηpq là giá trị trung tâm được định nghĩa như sau μ pq μ00γ (1.11-8) p+q +1 2 (1.11-9) η pq = Trong đó γ= M −1 N −1 μ pq = ∑ ∑ ( x − x) p ( y − y ) q f ( x, y ) (1.11-10) x =0 y =0 Với điều kiện p = 0, 1, 2, … q = 0, 1, 2, … x= m10 m01 và y = m00 m00 (1.11-11) Công thức tổng quát tính giá trị mpq m pq = M −1 N −1 ∑∑x x=0 y =0 p y q f ( x, y ) (1.11-12) - 18 - 1.2.5.2, Phân lớp Bayes Trong vài năm gần đây, một phương pháp phân tích “mới” ra đời và đang dần trở thành phổ biến trong nghiên cứu khoa học và nghiên cứu lâm sàng có thể đáp ứng hai nhu cầu về khoa học và nghệ thuật. Nói là “mới” nhưng trong thực tế thì cơ sở lí thuyết của phương pháp này đã ra đời từ thế kỉ 18. Đó là suy luận theo trường phái Bayes do Thomas Bayes đề xuất vào năm 1763. Thomas Bayes đã chỉ ra một phương pháp suy luận hoàn toàn logic. Ngày nay, phương pháp Bayes được ứng dụng trong hầu hết tất cả lĩnh vực khoa học, tiên lượng kinh tế, phân tích các mối liên hệ xã hội, và lí giải qui trình suy nghĩ của con người. Suy luận theo trường phái Bayes được nhắc đến trên báo chí đại chúng chứ không chỉ trong báo khoa học. Những tờ báo lớn như New York Times, Economist, Guardian, v.v. đều thường xuyên nhắc đến phương pháp suy luận Bayes[12]. Trong lĩnh vực công nghệ thông tin, rất nhiều ứng dụng đã được xây dựng theo suy luận của trường phái Bayes, tiêu biểu như ứng dụng ngăn chặn thư rác điện tử. Trong lĩnh vực nhận dạng, ngoài hai phương pháp nhận dạng cổ điển và mạng nơron, một phương pháp mới được xây dựng theo trường phái Bayes là phân lớp Bayes. a. Tiền đề Phân lớp Bayes là kỹ thuật phân lớp dựa trên việc tính xác suất có điều kiện, từ đó ước tính một thông số cần thiết cho tập mẫu của mỗi lớp [6]. Xác suất mà một tập mẫu x có thể nằm trong lớp ωj, ký hiệu p(ωj/x). Tuy nhiên, không phải lúc nào tập mẫu x cũng chắc chắn nằm trong lớp ωj, luôn xảy ra rủi ro nhất định giữa tập mẫu x với lớp ωj, ký hiệu Lkj. Nếu ta có một số lớp xác định - W lớp, thì xuất hiện điều kiện rủi ro trung bình của tập mẫu x với lớp ωj. W rj ( x) = ∑ Lkj p(ω j / x) (1.12-1) k =1 Theo toán xác suất, ta có p(A/B) = [p(A)p(B/A)]/p(B). Lúc này công thức (1.12-1) được viết lại như sau - 19 - 1 W rj ( x ) = ∑ Lkj p( x / ωk )P(ωk ) p( x) k =1 (1.12-2) Bởi vì 1/p(x) là một số xác định và không thay đổi đối với rj(x) khi j thay đổi từ 1 đến W. Do đó 1/p(x) không ảnh hưởng đến kết quả rj(x) từ giá trị nhỏ nhất đến giá trị lớn nhất. Sau khi bỏ 1/p(x) trong công thức (1.12-2), ta có W rj ( x) = ∑ Lkj p( x / ωk )P(ωk ) (1.12-3) k =1 Tiếp theo, với tập mẫu x bất kỳ, ta tính giá trị r1(x), r2(x), r3(x), …, rW(x). Từ đó ta quyết định tập mẫu x thuộc lớp nào dựa trên rj(x) nhỏ nhất. Tương tự, phân lớp Bayes sẽ quyết định tập mẫu x thuộc lớp ωj nếu ri(x) < rj(x), với j = 1, 2, 3, …, W; j ≠ i. Rủi ro trung bình Lkj = 1 - δkj, với ⎧ 1 if i = j ⎩0 if i ≠ j δ ij = ⎨ (1.12-4) Thay Lkj = 1 - δkj vào công thức (1.12-3) W rj ( x) = ∑ (1 − δ kj ) p ( x / ω j )P(ωk ) k =1 = p ( x) − p ( x / ω j ) P(ω j ) (1.12-5) Như đã nói ở trên, phân lớp Bayes sẽ quyết định tập mẫu x thuộc lớp ωj nếu ri(x) < rj(x) hay p(x) - p(x/ωi)P(ωi) < p(x) - p(x/ωj)P(ωj) Rút gọn công thức p(x/ωi)P(ωi) > p(x/ωj)P(ωj) với j = 1, 2, 3, …, W; j ≠ i (1.12-6) Cuối cùng, công thức phân lớp Bayes có sai số từ 0 đến 1 dj(x) = p(x/ωj)P(ωj) với j = 1, 2, 3, …, W (1.12-7) xác định tập mẫu x thuộc lớp có giá trị dj(x) lớn nhất. Đến đây, chúng ta đã xác định được điều kiện cho thuật toán nhận dạng với giá trị dj(x) là lớn nhất. Đó là trong điều kiện lý tưởng, còn thực tế thì không phải - 20 - lúc nào tập mẫu cũng có sự khác biệt lớn về giá trị, có những tập mẫu có sự khác biệt rất nhỏ mà chúng ta không thể kiểm soát được. Với tập mẫu x ban đầu và W lớp, ta sẽ nhận được W giá trị khác nhau, ta không thể đảm bảo rằng tất cả W giá trị đó sẽ đúng theo mong muốn. Ngoài ra, cơ sở dữ liệu của mỗi lớp quá ít hoặc không được xử lý tốt thì kết quả nhận được có thể sai hoàn toàn. Do đó, phân lớp Bayes đã giả sử tập tin mẫu theo hàm mật độ Gauss.để giải quyết vấn đề trên. b. Phân lớp Bayes với hàm mật độ Gauss Hàm mật độ Gauss định nghĩa hai giá trị là giá trị trung bình mi (mean) và độ lệch chuẩn σi (standard deviation) [6]. Hình 1.14. Biểu đồ mật độ xác suất hai tập mẫu Guass Nhìn vào biểu đồ, ta thấy m1, m2 là giá trị trung bình của hai tập mẫu tương ứng. Điểm x0 dùng để hiển thị ranh giới nơi mà hai tập mẫu có giá trị giống nhau. Phân lớp Bayes theo tập mẫu Gauss có công thức biển đổi như sau dj(x) = p(x/ωj)P(ωj) = 1 e 2πσ j − ( x − m j )2 2σ 2j P(ω j ) (1.12-8) Quay lại hình 1.14, tại vị trí x0 ta có d1(x0) = d2(x0) hay P(ω1) = P(ω2) =1/2. và p(x0/ω1) = p(x0/ω2), nghĩa là bất kỳ tập mẫu có giá trị tại vị trí x0 sẽ thuộc về hai lớp ω1 và ω2. Tương tự, những giá trị nằm bên phải x0 thuộc về lớp ω1, giá trị nằm