CHƯƠNG 1. GIỚI THIỆU VỀ NHẬN DẠNG MẪU Nhận dạng mẫu là lĩnh vực khoa học với mục đích phân loại và mô tả các đối tượng. Tùy thuộc vào các ứng dụng, các đối tượng này có thể là chữ viết, ảnh, sóng âm thanh, v. Trong chương này phần 1.1 dành để giới thiệu tóm tắt khái niệm nhận dạng mẫu và các bài toán cơ bản.2 giới thiệu một ví dụ về bài toán nhận dạng mẫu.3 giới thiệu các lĩnh vực liên quan.
Các hệ thống nhận dạng mẫu được giới thiệu trong phần 1. Chu trình thiết kế bộ phân lớp được giới thiệu trong phần 1.5 kết luận được trình bày trong phần 1. Mẫu và các bài toán nhận dạng thƣờng gặp 1. Mẫu (pattern) Có thể phân làm hai hoại: mẫu trừu tượng và mẫu cụ thể.
Các ý tưởng, lập luận và khái niệm. là những ví dụ về mẫu trừu tượng, nhận dạng các mẫu như vậy thuộc về lĩnh vực nhận dạng khái niệm. Các mẫu cụ thể bao gồm các đối tượng có tính không gian, thời gian và hình ảnh. hoặc các đối tượng vật lý, chữ ký, chữ viết, ký hiệu, ảnh, đoạn sóng âm thanh, điện não đồ hoặc điện tâm đồ, hàm số.là những ví dụ về mẫu cụ thể.
Nhận dạng mẫu là gì? Không có một định nghĩa thống nhất nào về nhận dạng mẫu (Pattern recognition viết tắt là PR) nhưng điều này cũng không gây ra tranh cãi gì trong giới nghiên cứu. Sau đây là một số định nghĩa theo ngữ cảnh nghiên cứu: - Duda et al: Nhận dạng mẫu là việc quy những đối tượng vật lí hay sự kiện vào một loại (nhóm) nào đó đã xác định từ trước. - Jürgen Schürmann: Nhận dạng mẫu là việc gán nhãn w cho một quan sát x. - Selim Aksoy: Nhận dạng mẫu là việc nghiên cứu cách làm cho một máy có thể thực hiện: + Quan sát môi trường.
+ Học cách phân biệt được các mẫu cần quan tâm. + Đưa ra các quyết định đúng đắn về loại (nhóm) của các mẫu. Như vậy thay cho việc tìm định nghĩa chính xác cho khái niệm nhận dạng mẫu ta sẽ liệt kê các bài toán chính trong lĩnh vực này. Các bài toán nhận dạng mẫu thƣờng gặp LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 Các bài toán nhận dạng mẫu thường gặp có thể quy về các dạng sau.
Phân lớp có giám sát hay phân loại (classify): Dựa trên một tập con (tập đào tạo) đã biết nhãn, đưa ra một cách gán nhãn cho các đối tượng mới để phân tập các đối tượng thành các lớp. Ví dụ: nhận dạng chữ viết tay nhờ các chữ đã biết. Phân lớp không giám sát hay phân cụm (cluster): Chia tập đối tượng thành nhóm sao cho các đối tượng trong mỗi nhóm tương đối giống nhau còn các đối tượng khác nhóm thì khác nhau. Phân tích hồi quy (regression) hay nhận dạng hàm: Xác định một biến (hàm) qua tập các biến khác.
Nhận thực (Identify): Xác định đối tượng trong tập đã cho có là đối tượng đang quan tâm hay không. Chẳng hạn như nhận thực vân tay, nhận thực mặt người. Mô tả: Mô tả các đối tượng dưới hình thức dễ phân tích. Chẳng hạn mô tả điện tâm đồ dưới dạng biểu đồ đặc trưng hoặc xâu mã.
Để hiểu rõ hơn quá trình nhận dạng mẫu, ta xét ví dụ sau. Ví dụ về bài toán nhận dạng mẫu Giả sử ta muốn tự động hóa quá trình sắp xếp, hay phân lớp những con cá được nhập vào trên băng truyền dựa theo loài. Với dự án nhỏ, chúng ta cần phân biệt giữa cá hồi (salmon) và cá vược biển (sea bass). Ta thiết lập 1 máy ghi hình (sensor: cảm biến quang học), lấy một số mẫu và bắt đầu ghi chép một số đặc tính vật lý khác nhau giữa 2 loài cá như tính nhanh nhẹn, chiều rộng, số lượng và hình dáng của vây, vị trí của miệng, và tiếp tục sử dụng các đặc trưng này để dùng trong việc phân lớp.
Chúng ta cũng phải chú ý đến sự biến đổi giữa các hình ảnh – sự biến đổi về độ sáng, vị trí của con cá trên băng truyền hay ngay cả vị trí của máy ghi hình. Chắc chắn là số lượng cá hồi và cá vược sẽ khác nhau, chúng ta xem chúng như mỗi mô hình khác nhau để có thể tạo được mô hình toán học. Vấn đề bao quát trong phân lớp mẫu là đưa ra một lớp các mô hình, xử lý dữ liệu để loại bỏ nhiễu (không phụ thuộc vào mô hình), và với mỗi mẫu chúng ta chọn ra mô hình thích hợp nhất. Hệ thống nguyên mẫu để thực hiện công việc rất đặc thù này được mô tả như hình 1.
Đầu tiên máy ghi hình thu nhận hình ảnh của con cá. Sau đó tín hiệu từ máy ghi hình được đưa vào công đoạn tiền xử lý để đơn giản hóa các thao tác sau này mà LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 không làm mất thông tin liên quan. Đặc biệt chúng ta có thể sử dụng thao tác phân đoạn (segmentation) để tách các bức ảnh của các loại cá khác nhau hay kể cả là ảnh nền. Thông tin từ mỗi con cá sau đó được đưa tới bộ trích chọn đặc trưng với mục đích là rút gọn dữ liệu bằng cách đánh giá các “đặc trưng‟ hay „thuộc tính‟ nào đó có cần cho bộ phân lớp hay không.
Những đặc trưng này (hay chính xác hơn là giá trị của chúng) sau đó được chuyển cho bộ phân lớp để đánh giá các dấu hiệu và đưa ra quyết định cuối cùng về loại cá. Bộ tiền xử lý sẽ tự động điều chỉnh độ sáng trung bình, hay loại bỏ hình nền của bức ảnh. Tại thời điểm này chúng ta hãy bỏ qua bước phân đoạn mà tập trung vào 2 bước là trích chọn đặc trưng và phân lớp. Giả sử rằng cá vược thường dài hơn cá hồi.
Như vậy hiển nhiên chiều dài là một đặc trưng, và chúng ta có thể phân lớp cá bằng cách xem chiều dài của chúng có đạt độ dài L hay không. Để chọn giá trị của L chúng ta xem một vài con cá mẫu, tính giá trị độ dài và phân tích kết quả. Giả sử rằng chúng ta thực hiện và thu được biểu đồ như hình 2. Biểu đồ này cho chúng ta thấy đúng là chiều dài trung bình của cá vược lớn hơn của cá hồi nhưng lại không có cách gì để chọn ra được một giá trị L khả dĩ để phân biệt chúng bằng chiều dài.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Biểu đồ về đặc trưng chiều dài của hai loại cá Thật khó khăn, nhưng chúng ta sẽ tiếp tục với các đặc trưng khác như độ sáng trung bình. Bây giờ ta phải rất cẩn thận để loại trừ sự biến thiên của ánh sáng, bởi vì nó có thể làm hỏng bộ phân lớp mới của chúng ta. Kết quả và giá trị tối đa x* được thể hiện trên hình 3 đã thỏa mãn hơn.
Các lớp đã được phân biệt tốt hơn. Hình 3: Biểu đồ về đặc trưng độ sáng của hai loại cá. Việc chọn yếu tố nào để quyết định sẽ đòi hỏi chi phí liên quan, và ta cần phải làm cho chi phí đó ở mức thấp nhất. Đây là nhiệm vụ trung tâm của lý thuyết quyết định trong đó phân lớp mẫu là lĩnh vực con quan trọng nhất.
Ngay cả khi chúng ta đã biết chi phí của các quyết định và chọn được giá trị x* tốt nhất, chúng ta vẫn có thể chưa thỏa mãn. Chúng ta muốn tìm các đặc trưng khác để phân lớp. Tuy nhiên không có đặc trưng trực quan riêng lẻ nào tốt hơn là độ sáng, vì vậy để tăng hiệu quả chúng, ta phải sử dụng nhiều hơn một đặc trưng để nhận dạng. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Khi tìm các đặc trưng khác chúng ta có thể thấy là cá vược thường có chiều rộng lớn hơn cá hồi.
Bây giờ chúng ta có 2 đặc trưng để đánh giá – độ sáng x1 và chiều rộng x2. Không tính đến thực tế chúng ta nhận ra rằng bộ trích chọn đặc trưng sẽ rút gọn mỗi bức ảnh về thành 1 điểm hay 1 véc tơ đặc trưng x trong không gian đặc trưng 2 chiều: x xx12 Bài toán của chúng ta là phải phân hoạch không gian đặc trưng thành 2 phần sao cho mọi điểm trong 1 vùng được coi là cá vược, và vùng còn lại là cá hồi. Sau khi xử lý chúng ta có thể có được minh họa như Hình 4. Đường kẻ gợi ý cho ta cách phân biệt các con cá: Quyết định một con cá là cá vược nếu vectơ đặc trưng của nó nằm dưới đường biên, ngược lại thì là cá hồi.
Luật này có vẻ thực hiện tốt và nó gợi ý cho chúng ta rằng có thể dùng thêm nhiều đặc trưng nữa. Bên cạnh độ sáng và chiều rộng, ta có thể cho thêm 1 vài tham số về hình dạng như góc nghiêng của vây ở lưng, hay vị trí của mắt,. Nhưng làm sao chúng ta có thể biết trước là đặc trưng nào là thích hợp nhất. Một số đặc trưng có thể giảm bớt.
Ví dụ như nếu màu của mắt cá có quan hệ chặt chẽ với chiều rộng thì hiệu quả của chương trình sẽ không tăng nếu ta sử dụng cả 2 đặc trưng, ngay cả khi chúng ta không phải lo lắng về việc tăng chi phí tính toán. Tại sao chúng ta phải có quá nhiều đặc trưng, như vậy là tự làm khổ mình. Hình 4: Hai đặc trưng về độ sáng và chiều rộng cho cá hồi và cá vược. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Giả sử rằng các đặc trưng còn lại là rất khó đo, hoặc không giúp cải thiện tốc độ bao nhiêu, đôi khi còn làm giảm, và chúng ta quyết định sẽ dùng hai đặc trưng như trên hình 1.4, đường đậm chỉ ra một biên quyết định của bộ phân loại.
Nếu những mô hình của ta phức tạp hơn thì đường biên sẽ là đường cong chứ không phải là đường thẳng như trên biểu đồ. Trong trường hợp đó tất cả các mẫu sẽ được phân loại như ở hình 1. Nhưng còn quá sớm để nói đến sự thành công vì mục đích của ta là phân lớp các mẫu mới, có thể rất kỳ lạ. Đó là sự tổng quát hóa, không chắc đường biên ở hình 1.5 đã cho kết quả tốt nhất, nó có vẻ chỉ như là chia lại các mẫu huấn luyện chứ chưa phải là mô hình thật sự của bài toán.
Hình 5: Một mô hình phức tạp cho cá Các mô hình quá phức tạp cho cá sẽ dẫn tới các biên quyết định trở nên phức tạp, nó sẽ làm cho các hệ thống tương lai chạy chậm.