Luận văn Thạc sĩ Khoa học máy tính: Một số kỹ thuật trích chọn đặc trưng chữ viết tay trong nhập điểm rèn luyện tự động

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

MAI QUỐC AN

MỘT SỐ KỸ THUẬT TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY TRONG NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Thái Nguyên - 2016

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

MAI QUỐC AN

MỘT SỐ KỸ THUẬT TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY TRONG NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG

Chuyên ngành: Khoa học máy tính

Mã số: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. Vũ Duy Linh

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Thái Nguyên - 2016

LỜI CAM ĐOAN

Tôi xin cam đoan toàn bộ nội dung bản luận văn này là do tôi tự sưu tầm, tra

cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.

Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ hình

thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên cứu nào.

Tất cả phần mã nguồn của chương trình đều do tôi tự thiết kế và xây dựng,

trong đó có sử dụng một số thư viện chuẩn và các thuật toán được các tác giả xuất

bản công khai và miễn phí trên mạng Internet.

Nếu sai tôi xin hoàn toàn chịu trách nhiệm.

Thái Nguyên, ngày tháng 07 năm 2016

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Người cam đoan

LỜI CẢM ƠN

Trong quá trình học tập và nghiên cứu tại lớp Cao học khóa 12 chuyên ngành

Khoa học máy tính tại trường ĐH Công nghệ thông tin và truyền thông - Đại học

Thái Nguyên, tôi đã nhận được rất nhiều sự chỉ bảo, dìu dắt, giảng dậy nhiệt tình của

các thầy, cô giáo trong Viện công nghệ thông tin. Các thầy cô giáo quản lý trong

trường ĐH Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã luôn

giúp đỡ, tạo điều kiện tốt nhất cho tôi trong quá trình công tác cũng như học tập.

Nhân dịp này tôi xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy, cô giáo trong

Viện công nghệ thông tin, các thầy cô giáo trong trường ĐH Công nghệ thông tin

và truyền thông - Đại học Thái Nguyên.

Tôi xin chân thành cảm ơn sâu sắc tới thầy giáo TS. Vũ Duy Linh đã cho tôi

nhiều ý kiến đóng góp quý báu, đã tận tình hướng dẫn và tạo điều kiện cho tôi hoàn

thành tốt luận văn tốt nghiệp này.

Tôi xin cảm ơn các đồng nghiệp và người thân đã động viên, giúp đỡ tôi trong

quá trình nghiên cứu và thực hiện luận văn này.

Quá trình thực hiện đề tài không tránh khỏi các thiếu sót, rất mong tiếp tục nhận

được sự đóng góp ý kiến của các thầy, các cô giáo, các bạn đồng nghiệp đối với đề

tài nghiên cứu của tôi để đề tài được hoàn thiện hơn.

Tôi xin trân trọng cảm ơn!

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Thái Nguyên, ngày tháng 07 năm 2016

iii

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

MỤC LỤC PHẦN MỞ ĐẦU ................................................................................................... 1 Chương 1: KHÁI QUÁT VỀ NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG VÀ TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY ...................................................... 2 1.1. Khái quát về nhập điểm rèn luyện tự động ............................................ 2 1.1.1. Quản lý và nhập điểm rèn luyện tự động ............................................ 2 1.1.2. Kiến trúc một hệ thống nhận dạng điểm rèn luyện sử dụng mạng nơron nhân tạo ........................................................................................................ 5 1.2. Khái quát trích chọn đặc trưng chữ viết tay ........................................ 13 1.2.1. Đặc trưng màu sắc .............................................................................. 15 1.2.2. Đặc trưng hình dạng .......................................................................... 16 1.2.3. Đặc trung kết cấu ................................................................................ 17 1.2.4. Đặc trung cục bộ bất biến .................................................................. 17 Chương 2: NHẬN DẠNG PHIẾU ĐIỂM SỬ DỤNG MẠNG NƠ RON ...... 19 2.1. Thiết kế mạng nơron nhân tạo ............................................................... 19 2.1.1. Các bước thiết kế ................................................................................ 19 2.1.2. Chi tiết các bước thiết kế một mạng nơron ....................................... 19 2.2. Các kỹ thuật trích chọn đặc trưng ......................................................... 24 2.2.1. Kỹ thuật trích chọn đặc trưng kết hợp biến đổi DCT và thuật toán phân tích thành phần chính PCA ........................................................................ 24 2.2.2 Kỹ thuật trích đặc trưng sử dụng Momen Legendre ......................... 27 2.2.3. Kỹ thuật sử dụng mạng Neural nhân chập (Convolution neural network) ................................................................................................................. 32 2.3. Huấn luyện mạng..................................................................................... 35 2.3.1. Các phương pháp học ......................................................................... 35 2.3.2. Học có giám sát trong các mạng nơron ............................................. 36 2.3.3. Thuật toán lan truyền ngược Back-Propagation .............................. 37 2.4. Nhận dạng sử dụng mạng nơron ........................................................... 49 2.4.1. Khả năng sử dụng mạng nơron trong nhận dạng ............................ 49 2.4.2. Mô hình nhận dạng hệ thống sử dụng mạng nơron ........................ 49 2.4.3. Nhận dạng hệ thống sử dụng mạng nơron ....................................... 51 Chương 3: CHƯƠNG TRÌNH THỬ NGHIỆM .............................................. 52 3.1. Đặc trưng của phiếu điểm ...................................................................... 52 3.2. Bài toán ..................................................................................................... 53 3.3. Tiền xử lý .................................................................................................. 54 3.4. Phân đoạn và trích chọn đặc trưng ....................................................... 57 3.5. Huấn luyện và nhận dạng ....................................................................... 57 3.6. Hậu xử lý .................................................................................................. 58 iii

PHẦN KẾT LUẬN ............................................................................................. 58 TÀI LIỆU THAM KHẢO ................................................................................. 60

CÁC CHỮ VIẾT TẮT

Từ viết tắt Ý nghĩa

CSDL Cơ sở dữ liệu

MCP Mô hình McCulloch và Pitts

MSE Mean-Square Error

BP Back-Propagation

PCA Principal Component Analysis

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

OMR Optical Mark Recognition)

MỤC LỤC HÌNH ẢNH

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 1: Nơron đơn giản ........................................................................................ 7 Hình 2: Nơron phức tạp hơn ................................................................................. 7 Hình 3: mạng truyền thẳng .................................................................................... 9 Hình 4: mạng hồi quy đơn giản........................................................................... 10 Hình 5: Perceptron .............................................................................................. 11 Hình 6: Sự khác nhau giữa hồi quy tuyến tính và mạng nơron .......................... 12 Hình 7: Các bước cơ bản trong hệ thống nhận dạng văn bản ............................. 14 Hình 8: Ví dụ về xác định các đặc trưng của ảnh ............................................... 15 Hình 9: Ảnh hưởng của vector riêng, giá trị riênglên tập dữ liệu ....................... 24 Hình 10: Các bước trích chọn đặc trưng bằng biến DCT kết hợp PCA ............. 26 Hình 11: Biến đổi DCT và cách lấy dữ liệu theo đường zigzag ......................... 27 Hình 12: Họ đa thức Legendre ............................................................................ 29 Hình 13: Thao tác nhân chập .............................................................................. 33 Hình 14: Quá trình trích chọn đặc trưng sử dụng mạng Neural nhân chập ........ 34 Hình 15: Minh họa quá trình lấy đặc trưng bằng mạng Neuron nhân chập ....... 34 Hình 16: Mô hình học có giám sát. ..................................................................... 36 Hình 17: Mạng lan truyền với một lớp ẩn. .......................................................... 38 Hình 18: xấp xỉ của mạng trong các trường hợp i = 1, 2, 4, 8 ............................ 42 Hình 19: Xác định tần số. .................................................................................... 47 Hình 20: Mô hình nhận dạng cơ bản. .................................................................. 50 Hình 21: Mẫu phiếu điểm đánh giá rèn luyện ..................................................... 52 Hình 22: Mẫu phiếu điểm tổng kết ..................................................................... 53 Hình 23: Nhị phân hóa ảnh. ................................................................................ 54 Hình 24: Lọc nhiễu.............................................................................................. 55 Hình 25: Chuẩn hóa kích thước ảnh các số “4” và “6”. ..................................... 55 Hình 26: Làm tròn biên chữ. ............................................................................... 56 Hình 27: Làm mảnh chữ. .................................................................................... 56

Hình 28: Tách thông tin phiếu điểm. .................................................................. 57

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

PHẦN MỞ ĐẦU

Công nghệ thông tin đang là một trong những ngành then chố t trong quá trình công nghiê ̣p hó a hiê ̣n đại hóa đất nước. Viê ̣c triển khai nghiên cứ u các công trình khoa học và đưa vào thực tế ứng du ̣ng góp phần giải phó ng sứ c lao đô ̣ng con ngườ i, tiết kiê ̣m thờ i gian, nâng cao hiê ̣u suất công viê ̣c là mô ̣t viê ̣c làm hết sứ c có ý nghĩa trong giai đoa ̣n này.

Bài toán nhâ ̣n dạng chữ viết tay xuất hiện cách đây khá lâu và đã được ứng dụng rất hiệu quả trong nhiều lĩnh vực khác nhau như y tế, giáo dục, quốc phòng, nghiên cứu vũ trụ.

Trong quá trình công tác, tôi nhận thấy rằng: Việc xử lý kết quả đánh giá rèn luyện của sinh viên hiện nay hầu hết ở các trường được thực hiện một cách thủ công. Quy trình đánh giá rèn luyện của học sinh - sinh viên được tiến hành từ cấp lớp đến cấp khoa và cấp trường. Kết quả đánh giá rèn luyện được giảng viên nhập vào bảng tổng hợp dựa trên phiếu đánh giá rèn luyện. Việc nhập điểm thủ công như vậy tốn khá nhiều công sức và khả năng nhầm lẫn cao.

Để giải quyết vấn đề trên đòi hỏi chúng ta phải xây dựng được các công cụ hữu hiệu trong việc nhận dạng chữ viết tay và sẽ đem la ̣i các lơ ̣i ích sau khi đưa vào ứ ng du ̣ng thực tế:

- Giảm lượng nhân công nhập điểm.

- Độ chính xác cao.

- Tiết kiệm thời gian, công sức.

- Dễ dàng giám sát tiến trình nhập điểm, giúp đưa ra cách giải quyết phù hợp khi

có sai sót xảy ra.

Trong phạm vi một đề tài luận văn thạc sỹ, tôi sẽ đi sâu vào tìm hiểu kỹ thuật trích chọ đặc trưng nhận dạng chữ viết tay trên phiếu đánh giá kết quả rèn luyện. Do đó tôi chọn đề tài: “Một số kỹ thuật trích chọn đặc trưng chữ viết tay trong nhập điểm rèn luyện tự động”.

Chương 1: KHÁI QUÁT VỀ NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG VÀ

TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY

1.1. Khái quát về nhập điểm rèn luyện tự động

1.1.1. Quản lý và nhập điểm rèn luyện tự động

Hiện nay, đánh giá kết quả rèn luyện của học sinh, sinh viên các trường đại học,

cao đẳng và trung học chuyên nghiệp nhằm góp phần thực hiện mục tiêu giáo dục là

đào tạo con người Việt Nam phát triển toàn diện, có đạo đức, tri thức, sức khỏe, thẫm

mỹ và nghề nghiệp, trung thành với lý tưởng độc lập dân tộc và chủ nghĩa xã hội;

hình thành và bồi dưỡng nhân cách, phẩm chất và năng lực của công dân, đáp ứng yêu

cầu xây dựng và bảo vệ Tổ quốc.

Việc đánh giá kết quả rèn luyện của học sinh, sinh viên là việc làm thường xuyên

ở các trường. Quá trình đánh giá phải đảm bảo chính xác, công bằng, công khai và

dân chủ.

Có nhiều bài toán hiệu quả và tin cậy để giải quyết khâu nhập điểm như các bài

toán điều tra xã hội học, thi tuyển sinh qua trắc nghiệm, nhập chứng từ ngân hàng,

nhập các tờ khai thuế...Khó khăn ở chỗ khối lượng nhập rất nhiều và việc kiểm soát

độ chính xác trong quá trình nhập.

Để tăng tốc độ nhập dữ liệu, một số phương pháp được nghiên cứu là:

- Phân tải để có thể nhập từ nhiều nguồn, nhiều đầu mối;

- Nhập qua các giá mang tính trung gian để tận dụng được nhiều phương pháp,

nhiều đầu mối, sau đó dùng các công cụ để chuyển về định dạng cần thiết;

- Nhập qua giao diện âm thanh hoặc hình ảnh, trong đó hình ảnh là phương pháp

được quan tâm nhiều hơn. Đã có nhiều thành công trong các hệ thống nhận dạng chữ

viết, nhận dạng các form tài liệu, nhận dạng các phiếu đánh dấu.

Để tăng độ tin cậy, người ta thường phải áp dụng các biện pháp tìm sai sót và

chỉnh sửa như:

- Kiểm lỗi trực tiếp;

- Nhập hai lần từ hai người khác nhau để phát hiện sai lệch;

- Tăng cường độ tin cậy của các hệ nhập liệu tự động;

- Phát hiện những ràng buộc toàn vẹn để đặt ra các cơ chế kiểm soát tự động theo

các ràng buộc và trong nhiều truờng hợp có thể tự sửa lỗi.

Trong hệ thống quản lý rèn luyện hiện nay có một vài giải pháp nhập điểm đã

được đưa vào để thực hiện như nhập liệu thủ công trực tiếp, nhập điểm trực tuyến,

nhập điểm theo lô từ file, và nhập điểm bằng nhận dạng ảnh phiếu điểm.

Việc nhập điểm bằng nhận dạng ảnh phiếu điểm: Một trong các giải pháp nhập

điểm khác được áp dụng là dùng các phiếu ghi điểm được viết theo những định dạng

đặc biệt. Sau đó bảng điểm được quét vào thành một ảnh và dùng một phần mềm

nhận dạng để biết cột nào được đánh dấu để suy ra điểm và ghi vào CSLD. Giải pháp

này có ưu điểm là giảm tải cho phòng Công tác học sinh - sinh viên, thay vì việc phải

nhập điểm chỉ cần quét ảnh, sau đó chạy phần mềm nhận dạng. Tuy nhiên vẫn phải in

bảng điểm và mời giáo viên lên ký.

* Quy trình chung một hệ thống nhập điểm tự động.

Quy trình chung của một hệ thống nhập điểm tự động thường bao gồm:

- Quét ảnh: quét ảnh phiếu điều tra và lưu dưới dạng ảnh raster: Quét trực tiếp

các loại phiếu điều tra thông qua máy quét. Đọc và xử lý hơn 30 dạng tệp tin ảnh phổ

dụng nhất như PCX, BMP, TIF, GIF, JPG, ... Có thể nhận dạng trực tiếp phiếu điều

tra thông qua máy quét, không cần lưu trữ dưới dạng tệp ảnh trung gian. Các phiếu

điều tra có thể được quét và lưu trữ dưới dạng tệp tin cơ sở dữ liệu.

- Tiền xử lý: nối các đường đứt nét, quay ảnh, xoá nhiễu,... lấp lỗ hổng. co dãn,

vuốt trơn đường, phát hiện góc nghiêng, độ dịch chuyển và hiệu chỉnh 1 cách tự

động...

- Lựa chọn vùng: Markread hiển thị phiếu mẫu sạch đẹp chưa điền thông tin và

chọn các vùng và điền thông tin liên quan đến chúng.

- Học form: vùng được lựa chọn có thể chứa nhiều ô hình chữ nhật trên ảnh mẫu

và tách ra các ô chữ nhật, elip và chúng được sử dụng cho trường OMR

* Dữ liệu đầu vào:

Phiếu điểm: là các ảnh đen trắng hoặc đa cấp xám từ đĩa hoặc từ Scanner. Khi đó

yêu cầu chung về dữ liệu là các tệp ảnh có thể có nhiễu, nghiêng và dịch chuyển

nhưng hạn chế, các bản in và photocopy tương đối rõ ràng. Hầu hết các khuôn dạng

thông thường như TIFF, GIF, PCX, BMP, JPG,... Các ảnh này gồm các ô hình vuông,

chữ nhật, tròn, e-lip có thể đánh dấu, chữ và chữ số có hạn chế.

- Nhận dạng phiếu điểm: Tự động nhặt ra các đối tượng theo mẫu đã chỉ ra trong

các phiếu mẫu. Ở giai đoạn này đối với mỗi đối tượng cần nhận dạng sẽ được tiến

hành theo các bước cơ bản: Xử lý sơ bộ, trích chọn các đặc trưng liên quan đến mẫu,

đối sánh các đặc trưng của đối cần nhận dạng với mẫu.

- Hiệu chỉnh: Hiệu chỉnh bằng tay hoặc tự động các vị trí trong phiếu mẫu.

- Trích chọn đặc trưng mẫu: Tự động phân tích và tách các vùng này các đối

tượng riêng lẻ (cô lập đối tượng) và tính đặc trưng cho các hình này rồi lưu vào tệp

mẫu học.

* Dữ liệu ra:

- Tệp kết quả của nhận dạng được đưa ra theo các qui cách DBF, MDB, XLS.

- Mỗi phiếu là một bản ghi gồm các trường tương ứng với các đối tượng cần

nhận dạng (hình vuông, chữ nhật, hình tròn, e-lip) đã được điền.

- Tên các trường được sinh ra một cách tự động hoặc được người dùng đưa vào.

Tiếp cận phương pháp nhận dạng nhãn quang học hiện đại:

- Tự động xử lý các bản kiểm tra, phiếu thăm dò, câu hỏi và các phiếu mẫu.

1.1.2. Kiến trúc một hệ thống nhận dạng điểm rèn luyện sử dụng mạng nơron

nhân tạo

1.1.2.1. Khái niệm mạng nơron nhân tạo

Mạng nơron nhân tạo hay thường gọi ngắn gọn là mạng nơron, trong tiếng anh là

Artificial Neural Network. Nó gồm có một nhóm các nơron nhân tạo nối với nhau, và

xử lý thông tin bằng cách truyền theo các kết nối và tính giá trị mới tại các nút. Trong

nhiều trường hợp, mạng nơron nhân tạo là một hệ thống thích ứng, tự thay đổi cấu

trúc của mình dựa trên các thông tin bên ngoài hay bên trong chảy qua mạng trong

quá trình học.

Một mạng nơron nhân tạo được cấu hình cho một ứng dụng cụ thể (nhận dạng

mẫu, phân loại dữ liệu, ...) thông qua một quá trình học từ tập các mẫu huấn luyện. Về

bản chất, học chính là quá trình hiệu chỉnh trọng số liên kết giữa các nơron.

1.1.2.2. Lịch sử phát triển của mạng nơron

Một trong những mô hình điển hình của mạng noron chính là não bộ của con

người. Bộ não người là một mạng noron có cấu tạo vô cùng phức tạp. Con người đã

nghiên cứu nó hàng nghìn năm nay. Cùng với sự phát triển của khoa học kĩ thuật đặc

biệt là những tiến bộ trong ngành điện tử hiện đại, con người đã bắt đầu nghiên cứu

các nơron và sự kiện đầu tiên đánh dấu sự ra đời của mạng nơron nhân tạo vào năm

1943 khi nhà thần kinh học Warren McCulloch và nhà toán học Walter Pitts viết bài

báo mô tả cách thức các nơron hoạt động. Họ cũng đã tiến hành xây dựng một mạng

nơron đơn giản bằng các mạch điện. Năm 1949 cuốn sách Organization of Behavior

của Donald Hebb được xuất bản đã chỉ ra rằng các nơron nhân tạo sẽ trở lên hiệu quả

hơn sau mỗi lần chúng được sử dụng.

Những tiến bộ của máy tính đầu những năm 1950, dự án Dartmouth nghiên cứu

về trí tuệ nhân tạo năm 1956 đã mở ra thời kỳ phát triển mới cả trong lĩnh vực trí tuệ

nhân tạo lẫn mạng nơron. Những năm tiếp theo của dự án Dartmouth, John von

Neumann đã đề xuất việc mô phỏng các nơron đơn giản bằng cách sử dụng rơle điện

áp hoặc đèn chân không. Nhà sinh học chuyên nghiên cứu về nơron Frank Rosenblatt

cũng bắt đầu nghiên cứu về Perceptron - một thuật ngữ trong học máy, đó là một thuật

toán phân loại. Sau thời gian nghiên cứu này Perceptron đã được cài đặt trong phần

cứng máy tính và được xem như là mạng nơron lâu đời nhất còn được sử dụng đến

ngày nay.

Năm 1974 Paul Werbos đã phát triển và ứng dụng phương pháp học lan truyền

ngược (back-propagation).

Ngày nay, đi xa hơn mức nghiên cứu lý thuyết, các nhà khoa học đã nghiên cứu

mạng nơron để cho ra các ứng dụng có khả năng giải quyết các bài toán thực tế được

diễn ra ở khắp mọi nơi. Các ứng dụng mạng nơron ra đời ngày càng nhiều và ngày

càng hoàn thiện hơn.

1.1.2.3. Mô hình nơron

a. Nơron nhân tạo đơn giản

Một nơron nhân tạo đơn giản là một thiết bị với nhiều đầu vào và có một đầu ra.

Nơron có hai chế độ hoạt động: chế độ huấn luyện và chế độ sử dụng. Trong chế độ

huấn luyện, nơron có thể được huấn luyện với một số các mẫu đầu vào tới khi không

được sử dụng nữa. Trong chế độ sử dụng thì khi phát hiện một mẫu đã học tại đầu

vào, đầu ra của nó sẽ trở thành đầu ra hiện tại. Nếu mẫu đầu vào không thuộc vào

danh sách mẫu đã học thì luật loại bỏ được sử dụng để tiếp tục dùng hay loại bỏ

nơron. Hình 1 mô tả một nơron đơn giản đó.

Hình 1: Nơron đơn giản

b. Nơron phức tạp hơn (Mô hình McCulloch và Pitts: MCP)

Sự khác biệt với mô hình đơn giản ở trên là đầu vào của mô hình này có trọng

số, hiệu quả của nó là mỗi đầu vào có một sự đưa ra quyết định phụ thuộc vào trọng

số của từng đầu vào. Trọng số của một đầu vào là một số mà khi nhân với

đầu vào thì ta có được trọng số đầu vào. Những đầu vào trọng số này được nhóm

lại với nhau và nếu chúng vượt quá giá trị ngưỡng thì nơron sẽ bị loại bỏ. Với các

trường hợp khác thì nơron không bị loại bỏ.

Hình 2:Nơron phức tạp hơn

Ví dụ ta có giá trị ngưỡng là T thì về mặt toán học, nơron này sẽ bị loại bỏ khi và

chỉ khi bất đẳng thức sau xảy ra:

X1.W1 + X2.W2 + X3.W3 + … > T

Sự thêm vào trọng số đầu vào và giá trị ngưỡng của nơron làm cho nó

linh hoạt và mạnh hơn. Nơron MCP có khả năng thích nghi với hoàn cảnh cụ thể

như là thay đổi trọng số hay giá trị ngưỡng.

1.1.2.4. So sánh mạng nơron với máy tính truyền thống

Các mạng nơron có cách tiếp cận khác trong giải quyết vấn đề so với máy tính

truyền thống. Các máy tính truyền thống sử dụng cách tiếp cận theo hướng giải thuật,

tức là máy tính thực hiện một tập các câu lệnh để giải quyết một vấn đề. Vấn đề được

giải quyết phải được biết và phát biểu dưới dạng một tập chỉ lệnh rõ ràng. Những câu

lệnh này sau đó phải được chuyển sang một chương trình ngôn ngữ bậc cao và chuyển

sang mã máy để máy tính có thể hiểu được. Nếu các bước cụ thể mà máy tính cần

tuân theo được chỉ ra không rõ ràng, máy tính sẽ không làm được gì cả. Điều đó giới

hạn khả năng của các máy tính truyền thống ở phạm vi giải quyết các vấn đề mà

chúng ta đã hiểu và biết chính xác cách thực hiện. Các máy tính sẽ trở lên hữu ích hơn

nếu chúng có thể thực hiện được những việc mà bản thân con người không biết chính

xác là phải làm như thế nào.

Các mạng nơron xử lý thông tin theo cách thức giống như bộ não con người.

Mạng được tạo nên từ một số lượng lớn các phần tử xử lý được kết nối với nhau làm

việc song song để giải quyết một vấn đề cụ thể. Các mạng nơron học theo mô hình,

chúng không thể được lập trình để thực hiện một nhiệm vụ cụ thể. Các mẫu phải được

chọn lựa cẩn thận nếu không sẽ rất mất thời gian, thậm chí mạng sẽ hoạt động không

đúng. Điều hạn chế này là bởi vì mạng tự tìm ra cách giải quyết vấn đề, thao tác của

nó không thể dự đoán được.

Các mạng nơron và các máy tính truyền thống không cạnh tranh nhau mà bổ

sung cho nhau. Có những nhiệm vụ thích hợp hơn với máy tính truyền thống, ngược

lại có những nhiệm vụ lại thích hợp hơn với các mạng nơron. Thậm chí rất nhiều

nhiệm vụ đòi hỏi các hệ thống sử dụng tổ hợp cả hai cách tiếp cận đểthực hiện được

hiệu quả cao nhất. (thông thường một máy tính truyền thống được sử dụng để giám

sát mạng nơron).

1.1.2.5. Một số kiến trúc mạng nơron dùng nhận dạng mẫu

a. Mạng truyền thẳng

Mạng truyền thẳng (hình 3) cho phép tín hiệu truyền chỉ theo một đường từ đầu

vào tới đầu ra, không có sự phản hồi hay lặp lại. Mạng này có xu hướng truyền thẳng

giữa đầu vào với đầu ra. Chúng được dùng rộng rãi trong nhận dạng mẫu. Cách tổ

chức trong mạng truyền thẳng là tham chiếu tới phương pháp từ dưới lên hoặc là từ

trên xuống.

Hình 3:mạng truyền thẳng

b. Mạng hồi quy

Mạng hồi quy có kiến trúc tương tự mạng truyền thẳng (hình 2.3) nhưng có điểm

khác nhau đó là nó cho phép tín hiệu truyền theo cả hai hướng. Mạng hồi quy truyền

tín hiệu rất tốt và có thể trở lên rất phức tạp. Nó có tính động; trạng thái của nó thay

đổi liên tục tới khi đạt tới điểm trạng thái cân bằng. Chúng duy trì điểm cân bằng tới

khi đầu vào thay đổi và cần tìm một một trạng thái cân bằng mới. Kiến trúc hồi quy

có thể tham chiếu tới việc tương tác.

c. Các lớp mạng

Các loại phổ biến nhất của mạng nơron nhân tạo bao gồm ba nhóm hoặc lớp của

các đơn vị: một lớp của các đơn vị "đầu vào" được kết nối với một lớp của các đơn vị

"ẩn", và lớp đơn vị “ẩn” này được kết nối với một lớp của đơn vị"đầu ra". (xem hình 4)

•Hoạt động của các đơn vị đầu vào mô tả các thông tin thô được đưa vào mạng.

•Hoạt động của từng đơn vị ẩn được xác định bởi các hoạt động của các đơn vị

đầu vào và trọng số trên các kết nối giữa đầu vào và các đơn vị ẩn.

•Hành vi của các đơn vị đầu ra phụ thuộc vào hoạt động của các đơn vị ẩn và

trọng số giữa các đơn vị ẩn và đầu ra.

Hình 4:mạng hồi quy đơn giản

Loại mạng hồi quy đơn giản này khá thú vị bởi vì các đơn vị ẩn được tự do xây

dựng đại diện đầu vào riêng của chúng. Trọng số giữa đầu vào và các đơn vị ẩn xác

định khi mỗi đơn vị ẩn đang hoạt động. Do đó bằng cách thay đổi các trọng số, một

đơn vị ẩn có thể chọn cái nó đại diện.

Chúng ta cũng phân biệt kiến trúc lớp đơn và kiến trúc nhiều lớp. Tổ chức lớp

đơn, trong đó tất cả các đơn vị được kết nối với nhau, tạo thành trường hợp tổng quát

nhất và là sức mạnh tính toán tiềm năng hơn tổ chức nhiều lớp cấu trúc phân cấp.

Trong các mạng đa lớp, các đơn vị thường được đánh số theo lớp, thay vì đánh số

theo toàn bộ hệ thống mạng.

d. Perceptrons

Nghiên cứu có ảnh hưởng nhất trên mạng nơron trong những năm 60 được tiến

hành dưới tiêu đề của “perceptron” một thuật ngữ được đặt ra bởi Frank Rosenblatt.

Perceptron (hình 5) trở thành một mô hình MCP (nơron với đầu vào trọng số) với một

số bổ sung, sửa chữa, tiền xử lý. Các đơn vị có nhãn A1, A2, Aj, Ap được gọi là đơn

vị kết nối và nhiệm vụ của chúng là trích xuất các đặc điểm riêng biệt từ những hình

ảnh đầu vào. Perceptron bắt chước các ý tưởng cơ bản đằng sau hệ thống thị giác

động vật có vú. Chúng chủ yếu được sử dụng trong mô hình nhận dạng mẫu mặc dù

khả năng của chúng được mở rộng hơn rất nhiều.

Hình 5: Perceptron

1.1.2.6.Ứng dụng của mạng nơron nhân tạo

Khả năng học và xử lý song song là hai đặc trưng của mạng nơron nhân tạo. Nó

có thể mô tả gần đúng mối quan hệ tương quan phức tạp giữa các yếu tố đầu vào và

đầu ra của các quá trình cần nghiên cứu. Thêm vào đó thì khi đã học được thì việc

kiểm tra độc lập thường cho kết quả tốt. Sau khi đã học xong, mạng nơron nhân tạo có

thể tính toán kết quả đầu ra tương ứng với bộ số liệu đầu vào mới.

Về mặt cấu trúc, mạng nơron nhân tạo là một hệ thống gồm nhiều phần tử xử lý

đơn giản cùng hoạt động song song. Tính năng này của mạng nơron nhân tạo cho

phép nó có thể được áp dụng để giải các bài toán lớn.

Về khía cạnh toán học, theo định lý Kolmogorov, một hàm liên tục bất kỳ f(x1,

(1.1)

x2,.. , xn ) xác định trên khoảng In ( với I =[0,1]) có thể được biểu diễn dưới dạng:

trong đó : χj , Ψij là các hàm liên tục một biến. Ψij là hàm đơn điệu, không phụ

thuộc vào hàm f. Mặt khác, mô hình mạng nơron nhân tạo cho phép liên kết có trọng

số các phần tử phi tuyến (các nơron đơn lẻ) tạo nên dạng hàm tổng hợp từ các hàm

thành phần. Do vậy, sau một quá trình điều chỉnh sự liên kết cho phù hợp (quá trình

học), các phần tử phi tuyến đó sẽ tạo nên một hàm phi tuyến phức tạp có khả năng

xấp xỉ hàm biểu diễn quá trình cần nghiên cứu. Kết quả là đầu ra của nó sẽ tương tự

với kết quả đầu ra của tập dữ liệu dùng để luyện mạng. Khi đó ta nói mạng nơron

nhân tạo đã học được mối quan hệ tương quan đầu vào - đầu ra của quá trình và lưu

lại mối quan hệ tương quan này thông qua bộ trọng số liên kết giữa các nơron. Do đó,

mạng nơron nhân tạo có thể tính toán trên bộ số liệu đầu vào mới để đưa ra kết quả

đầu ra tương ứng.

Hình 6: Sự khác nhau giữa hồi quy tuyến tính và mạng nơron

Với những đặc điểm đó, mạng nơron nhân tạo đã được sử dụng để giải quyết

nhiều bài toán thuộc nhiều lĩnh vực của các ngành khác nhau. Các nhóm ứng dụng mà

mạng nơron nhân tạo đã được áp dụng rất có hiệu quả là:

•Bài toán phân lớp: Loại bài toán này đòi hỏi giải quyết vấn đề phân loại các đối

tượng quan sát được thành các nhóm dựa trên các đặc điểm của các nhóm đối tượng

đó. Đây là dạng bài toán cơ sở của rất nhiều bài toán trong thực tế: nhận dạng chữ

viết, tiếng nói, phân loại gen, phân loại chất lượng sản phẩm,…

•Bài toán dự báo: Mạng nơron nhân tạo đã được ứng dụng thành công trong việc

xây dựng các mô hình dự báo sử dụng tập dữ liệu trong quá khứ để dự đoán số liệu

trong tương lai. Đây là nhóm bài toán khó và rất quan trọng trong nhiều ngành khoa

học.

•Bài toán điều khiển và tối ưu hoá: Nhờ khả năng học và xấp xỉ hàm mà mạng

nơron nhân tạo đã được sử dụng trong nhiều hệ thống điều khiển tự động cũng như

góp phần giải quyết những bài toán tối ưu trong thực tế.

Tóm lại, mạng nơron nhân tạo được xem như là một cách tiếp cận đầy tiềm năng

để giải quyết các bài toán có tính phi tuyến, phức tạp và đặc biệt là trong tình huống

mối quan hệ bản chất vật lý của quá trình cần nghiên cứu không dễthiết lập tường minh.

1.2. Khái quát trích chọn đặc trưng chữ viết tay

Nhận dạng chữ là lĩnh vực được nhiều nhà nghiên cứu quan tâm và cho đến nay

lĩnh vực này cũng đã đạt được nhiều thành tựu lớn và cả mặt lý thuyết lẫn thực tế.

Lĩnh vự nhận dạng chữ được chia làm hai loại: Nhận dạng chữ in và nhận dạng chữ

viết tay.

Nhận dạng chữ in đã được giải quyết gần như trọn vẹn (sản phẩm FineReader

9.0 của hãng ABBYY cỏ thế nhận dạng chữ in theo 192 ngôn ngữ khác nhau, phần

mềm nhận dạng chữ Viết in VnDOCR 4.0 của Viện Công nghệ Thông tin Hà Nội có

thể nhận dạng được các tài liệu chứa hình ảnh, bảng và các văn bản với độ chính xác

trên 98%).

Nhận dạng chữ viết tay vẫn còn là vấn đề thách thức lớn đối với các nhà nghiên

cứu. Khó khăn lớn nhất khi nghiên cứu bài toán nhận dạng chữ viết tay là sự biến thên

quá đa dạng trong các viết của từng người. Điều này gây ra nhiều trở ngại trong việc

trích chọn đặc trưng cũng như lựa chọn mô hình nhận dạng.

Hình 7: Các bước cơ bản trong hệ thống nhận dạng văn bản

Trích chọn đặc trưng đòng vai trò cực kỳ quan trọng trong một hệ thống nhận

dạng. Mục đích của việc trích chọn đặc trưng là làm giảm kích thước của ảnh và đồng

thời vẫn bảo toàn thông tin cần thiết vầ bức ảnh. Việc trích chọn hiệu quả các đặc

trưng giúp cho việc nhận dạng các đối tượng ảnh chính xác, với tốc độ tính toán cao

và dung lượng ưu trữ giảm xuống.

Dựa trên các thông tin thu nhận được qua quá trình phân vùng, kết hợp với các

kỹ thuật xử lý để đưa ra các đặc trưng về đối tượng ảnh cũng như cá thông tin cần

thiết trong quá trình xử lý. Trích chọn đặc trung phụ thuộc vào bản chất của bài toán

cần xử lý.

Hình 8: Ví dụ về xác định các đặc trưng của ảnh

1.2.1. Đặc trưng màu sắc

1.2.1.1 Lược đồ màu (Histogram)

Là đại lượng đặc trưng cho phân bố màu cục bộ của ảnh .

Độ đo tính tương tự về màu sắc được tính bằng phần giao của 2 lược đồ màu ảnh

truy vấn H(IQ) và ảnh trong cơ sở dữ liệu ảnh H(ID). Kết quả sẽ là một lược đồ màu

thể hiện độ giống nhau giữa 2 ảnh trên.

Tuy nhiên lược đồ màu chỉ thể hiện tính phân bố màu toàn cục của ảnh mà

không xét đến tính phân bố cục bộ của điểm ảnh nên có thể có 2 ảnh trông rất khác

nhau nhưng lại có cùng lược đồ màu.

1.2.1.2. Vector liên kết màu (Color Coherence Vector)

Là lược đồ tinh chế lược đồ màu, chia mỗi ô màu (bin) thành 2 nhóm điểm ảnh:

nhóm liên kết màu (coherence pixels) và nhóm không liên kết màu (non-coherence

pixels) Vector liên kết màu c ̣n giúp giải quyết khuyết điểm về tính không duy nhất của

lược đồ màu đối với ảnh. Hai ảnh có thể có chung lược đồ màu nhưng khác nhau hoàn

toàn, đây là khuyết điểm của lược đồ màu. Nhưng với tìm kiếm theo đặc trưng vector

liên kết màu th́ nó sẽ giải quyết được khuyết điểm không duy nhất này.

1.2.2. Đặc trưng hình dạng

Là đặc trưng dựa trên các yếu tố nguyên thủy (đoạn thẳng, cung) tạo ra các ký

tự. Các ký tự có thể phân biệt bằng độ đo của các đại lượng hình học nhử tỉ số giữa

chiều rộng và chiều cao của khung chứa ký tự, quan hệ khoảng cách giữa hai điểm, độ

dài một nét, đồ dài tương quan giữa hai nét, tỉ lệ giữa chữ hoa và chữ thường trong

một kí tự, độ dài từ...Vì thế các ký tự được tổ chức thành các tập họp của các yếu tố

nguyên thủy, sau đó đưa các yếu tố nguyên thủy vào các đồ thị liên quan.

Đặc trưng hình dạng đòi hỏi sự phân biệt giữa các vùng để tiến hành xử lý về độ

đo của hình dạng. Các hệ thống nhận dạng chữ viết tay thường khai thác hai nhóm

biểu diễn hình dạng sau:

- Biểu diễn hình dạng theo đường biên (cotour-based descriptor): Biểu diễn các

đường biên bao ngoài

- Biểu diễn theo vùng (region-based descriptor) Biểu diễn vùng toàn vẹn

1.2.3. Đặc trung kết cấu

Hiện tại vẫn chưa có một định nghĩa chính thức cụ thể về kết cấu. Kết cấu là một

đối tượng dùng để phân hoạch ảnh ra thành những vùng quan tâm để phân lớp những

vùng đó

Kết cấu cung cấp thông tin về sự sắp xếp về không gian của màu sắc và cường

độ một ảnh. Kết cấu được đặc trưng bởi sự phân bố không gian của những mức cường

độ trong một khu vực láng giềng với nhau. Kết cấu gòm các kết cấu gốc hay nhiều kết

cấu gộp lại đôi khi gọi là texel.

Một số phương pháp dùng để trích chọn các đặc trưng kết cấu như:

- Kim tự tháp “có thể lái được” ;

- Biến đổi đường viền;

- Biến đổi sóng Gabor;

- Biểu diễn mà trận đồng hiện;

- Hệ thống bộ lọc định hướng phức tạp.

1.2.4. Đặc trung cục bộ bất biến

Người ta thường chia đặc trưng cục bộ thành 2 loại là những điểm trích xuất

được từ điểm “nhô ra” của ảnh là đặc trưng SIFT được trích chọn từ các điểm hấp dẫn

Haris.

Các đặc trưng bất biến với việc tahy đổi tỉ lệ ảnh, quay ảnh, đôi khi là thay đổi

điểm nhìn và thêm nhiễu ảnh hay thay đổi cường độ sáng của ảnh. Phương pháp được

lựa chọn có tên là Scale-Invariant Feature Transform (SIFT) và đặc trưng trích rút

được gọi là đặc trưng SIFT. Các đặc trưng SIFT này được trích rút ra từ các điểm hấp

dẫn cục bộ (Local Interest Point).

Điểm hấp dẫn (Interest Point (Keypoint)): Là vị trí (điểm ảnh) "hấp dẫn" trên

ảnh. "Hấp dẫn" ở đây có nghĩa là điểm đó có thể có các đặc trưng bất biến với việc

quay ảnh, co giãn ảnh hay thay đổi cường độ chiếu sáng của ảnh.

Phương pháp trích rút các đặc trưng bất biến SIFT được tiếp cận theo phương

pháp thác lọc, theo đó phương pháp được thực hiện lần lượt theo các bước sau:

Phát hiện các điểm cực trị Scale-Space (Scale-Space extrema detection): Bước

đầu tiên này tiến hành tìm kiếm các điểm hấp dẫn trên tất cả các tỉ lệ và vị trí của ảnh.

Nó sử dụng hàm different-of-Gaussian để xác định tất cả các điểm hấp dẫn tiềm năng

mà bất biến với quy mô và hướng của ảnh.

- Định vị các điểm hấp dẫn (keypoint localization): Một hàm kiểm tra sẽ được đưa

ra để quyết định xem các điểm hấp dẫn tiềm năng có được lựa chọn hay không ?

- Xác định hướng cho các điểm hấp dẫn (Orientation assignment): Xác định

hướng cho các điểm hấp dẫn được chọn

- Mô tả các điểm hấp dẫn (Keypoint descriptor): Các điểm hấp dẫn sau khi được

xác định hướng sẽ được mô tả dưới dạng các vector đặc trưng nhiều chiều.

Chương 2: NHẬN DẠNG PHIẾU ĐIỂM SỬ DỤNG MẠNG NƠ RON

2.1. Thiết kế mạng nơron nhân tạo

2.1.1. Các bước thiết kế

Các bước trong thiết kế một mô hình mạng nơron nhân tạo, gồm 7 bước:

 Bước 1: Lựa chọn biến

 Bước 2: Thu thập dữ liệu

 Bước 3: Tiền xử lý dữ liệu

 Bước 4: Các tập dữ liệu huấn luyện, kiểm thử, và chứng thực.

 Bước 5: Sơ đồ mạng nơron:

 Số lượng lớp ẩn,

 Số lượng nơron ẩn,

 Số lượng nơron đầu ra,

 Hàm chuyển đổi.

 Bước 6: Huấn luyện mạng nơron: Số lần lặp lại huấn luyện.

 Bước 7: Triển khai

2.1.2. Chi tiết các bước thiết kế một mạng nơron

2.1.2.1. Lựa chọn biến

Để thiết kế tốt được mạng nơron thì chúng ta cần phải hiểu rõ vấn đề chúng ta cần

giải quyết. Lựa chọn biến đầu vào cho phù hợp là một quá trình không dễ dàng. Với

những giá trị đầu vào không quan trọng sẽ tăng độ phức tạp cho quá trình học của mạng

nơron. Ta cần chọn biến đầu vào nào cho tối ưu nhất với yêu cầu đầu ra mà chúng ta

cần. Một số vấn đề xảy ra nếu chúng ta chọnđầu vào chưa tốt:

-Tăng số lượng đầu vào sẽ làm tính toán phức tạp và cần nhiều bộ nhớ hơn.

-Quá trình học sẽ khó khăn với các đầu vào không cần thiết.

-Khó khăn hơn để hiểu mô hình mạng nơron này.

Phương pháp lựa chọn biến đầu vào được phát triển dựa trên quá trình kiểm thử

thống kê giữa các giá trị đầu vào và đầu ra mong muốn. Một số trường hợp có sự phụ

thuộc giữa biến đầu vào dẫn đến việc đánh giá quá cao số lượng đầu vào. Một cách để

giải quyết vấn đề này là khi tiền xử lý dữ liệu, chúng ta dùng phương pháp phân tích

thành phần phụ thuộc.

2.1.2.2. Thu thập dữ liệu

Sau khi đã chọn biến thì các nhà nghiên cứu cần phải thu thập dữ liệu cho các

biến đã chọn. Việc thu thập dữ liệu phải tách biệt với tiền xử lý, tập huấn hay đánh giá

hiệu năng mạng. Mọi dữ liệu cần được kiểm tra lỗi nếu có sự biến đổi hàng ngày của

dữ liệu, biến đổi về phạm vi, và sự thống nhất về logic.

2.1.2.3. Tiền xử lý dữ liệu

Việc xử lý trước dữ liệu chính là phân tích và chuyển đổi biến đầu vào và đầu ra

sao cho giảm bớt nhiễu, nhấn mạnh các liên hệ quan trọng, tìm ra xu hướng và phân

đồng đều các biến, giúp mạng nơron học các mẫu liên quan hiệu quả hơn. Vì mạng

nơron là các khớp mẫu, việc miêu tả dữ liệu cực kỳ quan trọng trong việc thiết kế

thành công mạng nơron. Dữ liệu được thu thập để đưa vào mạng hiếm khi để nguyên

dạng thô ban đầu. Ít nhất thì dữ liệu đó cũng được cân bằng với cận trên và cận dưới

của hàm chuyển đổi ( thường là nằm giữa 0 và 1 hoặc -1 và 1).

Có hai phương pháp chuyển đổi dữ liệu phổ biến đó là đạo hàm bậc nhất và

logarit tự nhiên của một biến. Một cách khác nữa đó là dùng tỉ lệ của các biến đầu

vào. Làm mịn dữ liệu đầu vào và đầu ra bằng cách tính trung bình đơn giảnhoặc dùng

số mũ.

Lấy mẫu và lọc dữ liệu giúp cho việc hủy các observation từ tập huấn luyện và

kiểm thử để tạo ra một sự phân phối đồng đều hơn. Cách lọc được sử dụng nên thống

nhất với mục đích của nhà nghiên cứu. Nhà nghiên cứu phải xác định chính xác mạng

nơron của mình cần học gì. Một lợi ích của việc lọc là tăng về số lượng thực tế tập

huấn mà cho phép kiểm thử trên nhiều biến đầu vào, nhiều trọng số ban đầu ngẫu

nhiên hoặc nhiều nơron ẩn hơn các tập dữ liệu huấn luyện lớn.

Trên thực tế thì quá trình tiền xử lý dữ liệu gồm nhiều thử nghiệm và có lỗi nhiều.

Để lựa chọn thích hợp biến đầu vào cần kiểm thử kết hợp đa dạng các biến đầu vào.

2.1.2.4. Các tập dữ liệu huấn luyện, kiểm thử, và chứng thực.

- Trên thực tế, tập dữ liệu được chia thành ba tập khác nhau đó là tập huấn luyện,

tập kiểm thử và tập hợp lệ.

- Tập dữ liệu huấn luyện là tập lớn nhất và mạng nơron học từ dữ liệu này.

- Tập kiểm thử là tập dữ liệu dùng để kiểm thử. Lấy dữ liệu đó để kiểm tra xem

độ chính xác của mạng nơron là bao nhiêu phần trăm. Tập này có kích thước tương

đương 10% - 30% kích thước của tập huấn luyện.

- Việc kiểm tra cuối cùng trong hiệu năng của mạng huấn luyện là sử dụng tập

hợp lệ. Kích thước của tập này dựa vào sự cân bằng giữa việc đủ đểđánh giá mạng và

có đủ dữ liệu còn lại cho cả huấn luyện và kiểm thử.

2.1.2.5. Sơ đồ mạng nơron

Thực tế thì có nhiều phương pháp để xây dựng mạng nơron. Các công việc cần

làm để xây dựng một mạng nơron là xác định hàm chuyển đổi, các đầu vào được kết

hợp với nhau như thế nào, và xây dựng kiến trúc mạng nơron bằng việc định nghĩa cấu

trúc bên trong bao gồm số lượng nơron nằm trên một lớp, số lượng và các loại kết nối.

Như đã đề cập ở phần một thì chúng ta lần lượt đi xác định các thông số sau: số

lượng lớp ẩn, số lượng nơron ẩn, số lượng nơron đầu ra, hàm chuyển đổi.

a. Số lượng lớp ẩn

Lớp ẩn cung cấp cho mạng khả năng phân loại dữ liệu. Về lý thuyết, một mạng

nơron có một lớp ẩn với số lượng đầy đủ các nơron ẩn có khả năng tính toán xấp xỉ

của hàm liên tục. Trong thực tế, các mạng nơron có một hoặc đôi khi là hai lớp ẩn là

đủ. Nếu tăng số lượng lớp ẩn thì thời gian tính toán cũng tăng. Vì thế, khuyến cáo

rằng chỉ nên có một hoặc nhiều nhất hai lớp ẩn.

b. Số lượng nơron ẩn

Thực tế thì không có công thức chung để lựa chọn số lượng tối ưu các nơron ẩn.

Vì vậy các nhà nghiên cứu dựa trên thực nghiệm nghiệm để lựa chọn. Tuy nhiên, có

một số quy tắc để lựa chọn cho hợp lý. Ta có thể dụng phương pháp kim tự tháp hình

học để tính gần đúng. Với một mạng ba lớp có n nơron đầu vào và m nơron đầu ra thì

lớp ẩn cần có căn bậc hai của (n x m) số lượng nơron. Số lượng thực tế của nơron ẩn

có thể vẫn rơi vào một nửa tới gấp hai lần giá trị có được từ quy tắc kim tự tháp, nó

phụ thuộc vào độ phức tạp của vấn đề.

Ba phương pháp lựa chọn số lượng nơron ẩn thường được dùng đó là sửa chữa,

xây dựng và tiêu hủy.

Phương pháp sửa chữa: một nhóm các mạng nơron với số lượng nơron ẩn khác

nhau được huấn luyện. Sự tăng lên về số lượng nơron ẩn có thể là một, hai hoặc nhiều

hơn phụ thuộc vào tài nguyên tính toán. Phác họa tiêu chí đánh giá trên kiểm thử với

mỗi mạng sẽ cung cấp một đồ thị lỗi hình cái bát. Mạng với ít lỗi nhất tìm thấy ở đáy

bát được lựa chọn. Phương pháp này tốn thời gian nhưng rất hiệu quả.

Phương pháp xây dựng và tiêu hủy: thay đổi số lượng nơron ẩn trong quá

trình huấn luyện chứ không tạo các mạng nơron biệt lập nhau với số lượng nơron

ẩn khác nhau. Phương pháp xây dựng là thêm các nơron ẩn tới khi hiệu năng của

mạng giảm. Ngược lại với phương pháp tiêu hủy là loại bớt các nơron ẩn trong quá

trình huấn luyện.

Bỏ qua việc sử dụng phương pháp nào để lượng chọn số lượng nơron ẩn, quy tắc

là lựa chọn mạng sao cho thực hiện tốt nhất trên tập kiểm thử với ít nơron ẩn nhất.

Khi kiểm thử số lượng nơron ẩn thì cần phải giữ nguyên các thông số khác.

c. Số lượng nơron đầu ra

Quyết định số lượng nơron đầu ra đôi khi không đơn giản vì có nhiều lý do bắt

buộc luôn sử dụng một nơron đầu ra. Các mạng nơron có nhiều đầu ra sẽ cho kết quả

kém hơn so với mạng có một đầu ra đơn. Một mạng nơron huấn luyện bởi quá trình

chọn trọng số sao cho lỗi trung bình trên toàn bộ nơron đầu ra là nhỏ nhất.

d. Các hàm chuyển đổi

Các hàm chuyển đổi là các công thức toán dùng để quyết định đầu ra của một

nơron xử lý. Phần lớn các mô hình mạng nơron hiện tại sử dụng hàm sigmoid (hình S)

nhưng số khác thì dùng hyperbolic và tuyến tính. Mục đích của hàm chuyển đổi là

ngăn chặn các đầu ra đạt tới giá trị quá lớn khiến cho mạng nơron tê liệt và không

huấn luyện được nữa. Các hàm chuyển đổi tuyến tính không hữu ích cho ánh xạ

không tuyến tính và phân loại không tuyến tính.

2.1.2.6. Quá trình huấn luyện mạng nơron

Ta cần xác định số lần lặp lại quá trình huấn luyện. Trong mỗi lần lặp, trọng số

thay đổi để mạng hoạt động hiệu quả hơn. Quá trình lặp lại tới khi không có sự cải

thiện gì thêm. Các mạng nơron thông thường sẽ lặp từ mười tới mười nghìn lần nhưng

số lượng vài trăm là phổ biến nhất.

2.1.2.7. Triển khai

Bước triển khai được thực hiện sau khi có đầy đủ các yếu tố cần thiết như là dữ

liệu, số lần huấn luyện, tiêu chuẩn đánh giá cho mạng nơron. Ta có thể sử dụng một

số phần mềm để triển khai mạng nơron đã được xây dựng sẵn hoặc dùng bảng tính

với việc biết kiến trúc của nó, các hàm chuyển đổi và các trọng số. Khi được triển

khai thì hiệu năng của mạng sẽ giảm dần tới khi mà mạng được huấn luyện lại. Một

mô hình tốt tương ứng với tần suất tái huấn luyện của nó.

2.2. Các kỹ thuật trích chọn đặc trưng

Trích chọn đặc trưng đóng vai trò hết sức quan trọng để giải quyết bài toán nhận

dạng chữ viết tay. Thực chất quá trình trích chọn đặc trưng của chữ viết tay tức là ta

đi tìm các đại lượng để biểu diễn cho các ký tự viết tay, mà các đại lượng này ít bị

thay đổi khi ký tự có sự biến đổi về hình dạng. Một Kỹ thuật trích đặc trưng chữ viết

tốt cho ra được các đặc trưng ít bị biến đổi khi ký tự bị biến dạng nhiều. Dưới đây xin

dưới thiệu 3 kỹ thuật trích chọn đặc trưng hay được sử dụng cho bài toán nhận dạng

chữ viết tay.

2.2.1. Kỹ thuật trích chọn đặc trưng kết hợp biến đổi DCT và thuật toán phân

tích thành phần chính PCA

Khái niệm giá trị riêng và vector riêng được các nhà toán học tìm ra vào cuối thể

kỷ 19 đầu thế kỷ 20.Có hàng loạt tính chất quan trọng liên quan đến giá trị riêng và

vector riêng, các tính chất này được ứng dụng rất nhiều trong các lĩnh vực kỹ

thuật.Dưới đây là một trong các tính chất đó: cho tập dữ liệuX, A là ma trận hiệp

phương sai của tập dữ liệu X (A là ma trận vuông). Khi đó tập vector riêng của A là

tập các vector trực giao, khi chiếu tập dữ liệu X lên tập các vector riêng này, thì dữ

liệu sẽ dao đông nhiều quanh các vector riêng tương ứng với giá trị riêng lớn, dữ liệu

ít dao động xung quanh các vector riêng tương ứng với các giá trị riêng nhỏ.

Hình 9: Ảnh hưởng của vector riêng, giá trị riênglên tập dữ liệu

Thuật toán phân tích thành phần chính (PCA) là hệ quả trực tiếp của tính chất đã

nêu trên. Trong kỹ thuật thuật toán PCA là một thuật toán phổ biến được sử dụng để

giảm số chiều của dữ liệu nhưng vẫn giữ được nhiều thông tin khi phân biệtvới các dữ

liệu khác.Thuật toán PCA được đề xuất đầu tiên bởi H. Hotelling (ban đầu được biết

với tên là biến đổi Hotelling-Hotelling’s transform). Dưới đây là nội dung thuật toán

PCA, sau đó xin giới thiệu kỹ thuật trích chọn đặc trưng bằng cách sử dụng biến đổi

cosin rời rạc (DCT) kết hợp với thuật toán PCA để thu gọn số chiều của dữ liệu.

2.2.1.1. Thuật toán PCA

Giả sử ta có tập dữ liệu trong đó các đước sắp xếp thành các

hang để được ma trận có kích thước . Ta mong muốn làm giảm số chiều dữ

liệu tập có D chiều thành tập dữ liệu Y có L chiều, L< D. Có thể tóm tắt thuật toán

PCA như sau:

Bước 1: Tính giá trị trung bình trên tường chiều dữ liệu 1…D của tập dưc liệu X

ta được vector giá trị trung bình u có kích thước trong đó

Bước 2: Thực hiện giảm giá trị của dữ liệu trên từng chiều với giá trị trung bình

tương ứng:

Ta lưu giá trị tính được vào ma trận B

trong đó h là ma trận có kích thước

Bước 3: Tính ma trận hiệp phương sai của ma trận B

Bước 4: Tìm giá trị riêng và vector riêng của ma trận hiệp phương sai C

Đầu tiên ta tính tập giá trị riêng

của ma trận C bằng cách giải phương

trình sau đó ta tìm tập vector riêng cách giải phương trình

trong đó

Bước 5: Sắp xếp tập giá trị riêng và tập vector riêng tương ứng theo chiều

giảm dần của giá trị riêng.

Bước 6: Chọn lấy L vector đầu tiên từ tập vector riêng sau khi đã sắp xếp

Bước 7: Tính giá trị của Y

Y=X*WT

Nhìn chung việc tính giá trị riêng và vector riêng là một bài toán khó trong toán

học. Trong phần thực nghiệm của mình, tôi sử dụng thư viện MATLAB để thực hiện

tìm giá trị riêng và vector riêng của ma trận.

2.2.1.2. Kỹ thuật trích chọn đặc trưng kết hợp phép biến đổi DCT và thuật toán PCA

Ta xét dữ liệu đầu vào là ma trận điểm ảnh, hình vec dưới đây mô tả các bước

của thuật toán:

Hình 10: Các bước trích chọn đặc trưng bằng biến DCT kết hợp PCA

Từ ảnh dữ liệu ban đầu kích thước MxN dùng phép biến đổi Cosin rời rạc ta

được ma trận MxN các hệ số thực. Sau đó ta lấy dữ liệu theo đường zigzag như hình

vẽ bên dưới ta được vector với MxN đặc trưng.Tiếp đó ta dùng thuật toán PCA để

thu gọn số chiều của vector đặc trưng, khi đó kết quả đầu ra sau bước nàyxem như là

vector đặc trưng của bước ảnh đầu vào.

Hình 11: Biến đổi DCT và cách lấy dữ liệu theo đường zigzag

Ta thấy rằng bức ảnh gốc qua phép biến đổi DCT thì ta không bị mất thông tin vì

ta có thể sử dụng phép biến đổi DCT nghịch đảo để thu được hình ảnh gốc. Ở ma trận

hệ số của phép biến đổi DCT, các điểm ở gần gốc (1,1) thể hiện mức sáng nền của

bức ảnh gốc, còn các điểm điểm càng xa điểm gốc thể hiện mức độ chi tiết của bước

ảnh (trong thuật toán nén ảnh JPEG sau khi biến đổi DCT người ta thường lược bỏ

các hệ số xa điểm gốc, mà mắt người vẫn không nhận thấy sự thay đổi), như vậy sau

khi lấy dữ liệu cho vector đặc trưng theo đường zigzag thì các điểm gần nhau trên

đường zigzag (cũng như trong vector đặc trưng) luôn có quan hệ về mặt giá trị cũng

như ảnh hưởng đối với ảnh gốc. Điều này giúp cho vector đặc trưng mạng nhiều

thông tin cho việc nhận dạng. Cuối cùng vector đặc trưng được xử lý qua thuật toán

PCA để thu gọn số chiều dữ liệu giúp cho việc nhận dạng được hiệu quả hơn.

2.2.2 Kỹ thuật trích đặc trưng sử dụng Momen Legendre

2.2.2.1 Momen và Momen Legendre

a) Khái niệm Momen (toán học)

Trong toán học khái niệm momen xuất phát từ khái niệm momen trong vật lý,

giá trị momen bậc n của hàm số thực f(x) tại c được định nghĩa như sau:

(2.1)

Trong trường hợp f là hàm hai biến số thì momen bậc (n+m) của hàm số f(x,y) tại

điểm (c1, c2) được định nghĩa như sau:

(2.1)

b) Khái niệm Momen trong xử lý ảnh:

Momen ảnh (image moments) là trọng số trung bình cụ thể nào đó của độ sáng

các điểm ảnh, nếu ảnh là ảnh liên tục thì định nghĩa momen ảnh giống công thức

(2.1), nếu ảnh đã rời rạc hóa thì momen bậc (m+n) tại điểm (c1,c2) của ảnh được định

nghĩa như sau:

(2.3)

Trong đó là kích thước của ảnh, I(x,y) là độ sáng của ảnh tại điểm

(x,y).Giá trị momen ảnh được có thể dùng để mô tả các đối tượng ảnh sau khi đã được

phân đoạn. Một số thuộc tính cơ bản của đối tượng ảnh có thể được phát hiện thông

qua momen ảnh: diện tích, tâm, hướng của vật thể...

Các momen bất biến (invarians moments) trong phép biến đổi ảnh được nghiên

cứu vào thập niên 60 của thế kỷ 20. Momen bất biến là những giá trị momen không

thay đổi trong các phép biến đổi ảnh như dời hình, xoay, đồng dạng... Trong giai đoạn

nghiên cứu này rất nhiều loại momen được giới thiệu: Momen Legendre, momen

Zernike...Kèm theo đó là rất nhiều thuật toán nhanh và hiệu quả để tính giá trị các

momen này.

c) Định nghĩa momen Legendre:

Momen Legendre bậc (m+n) của ảnh liên tục f(x,y) được định nghĩa như sau:

(2.4)

Trong đó m,n=0,1,2…,∞, Pm,Pn là đa thức Legendre. Họ đa thức Legendre là tập

các đa thức trực giao trên đoạn [-1,1]. Để tồn tại momen Legendre được xác định thì

hàm f(x,y) phải xác định trên đoạn [-1,1]. Đa thức Legendre bậc n được định nghĩa như:

(2.5)

Hình 12: Họ đa thức Legendre

Ta có thể xây dựng lại ảnh f(x,y) từ momen Legendre bằng công thức sau:

(2.6)

Với ảnh đã được rời rạc hóa Pxy ta có công thức sau để tính momen legendre:

(2.7)

Người ta đã chứng minh được rằng giá trị momen Legendre là đại lượng bất biến

trong các phép dời hình, và đồng dạng. Vì thếmomen Legendre thường được sử dụng

để nhận dạng các đối tượng hình học khi nó bị biến đổi bằng phép dời hình hay phép

đồng dạng.Tuy nhiên nhược điểm của momen Legendre đó là nó không phải là

momen bất biến trong phép xoay hình vì vậy tầm ứng dụng của nó vẫn còn hạn chế.

2.2.2.2. Kỹ thuật trích chọn đặc trưng chữ viết tay bằng Momen Legendre

Tư tưởng chính của kỹ thuật như sau: Giả sử ta có ảnh đầu vào X, ta đặt

MAX_ORDER là một giá trị cho trước nào đấy, sau đó ta tính tất cả các giá trị

Momen Legendre bậc (m+n) sao cho m < n < MAX_ORDER. Các giá trị Momen này

được lưu và ma trận L: . Ta gọi ma trận L

là ma trận momen Legendre. Sau khi tính xong ma trận L ta viết các giá trị của ma

trận L thành một hàng và xem đó như là giá trị đặc trưng của ảnh đầu vào X. Do tính

chất của Momen Legendre đó là bất biến với các phép biến đổi ảnh: dời hình và xoay

hình nên nếu dữ liệu kiểm tra đồng dạng hay bị dời hình so với dữ liệu huấn luyện thì

sẽ cho kết quả nhận dạng rất tốt. Sau đây là từng bước cụ thể của kỹ thuật trích chọn

đặc trưng chữ viết tay bằng Momen Legendre:

Bước 1: chuyển đổi tọa độ:

Chú ý rằng momen Legendre chỉ được xác định trên đoạn [-1,1] nên để áp dụng

được với một bức ảnh kích thước bất kỳ thì ta phải thực hiện bước đổi tọa độ

như sau: ta gọi i,j là tọa độ trên ảnh gốc , x,y là tọa độ sau khi đổi

khi đó công thức chuyển và

đổi tọa độ là .

Bước 2: Tính toán giá trị của ma trân Momen Legendre:

Dưới đây là thủ tục viết bằng giả mã để tính giá trị của ma trận Momen Legendre

For k:=0 to MAX_ORDER do

For l:=0 to k do

For i:= 0 to N do

For j:=0 to M do

End

Để tính nhanh được Pn(x) ta có thể sử dụng công thức truy hổi sau:

Bước 3: Chuyển ma trận Legendre thành vector đặc trưng

Thực chất ở bước này ta thực hiện viết giá trị các điểm trong ma trận Legendre

thành một hàng (hay vector) và ta xem đó là vector đặc trưng của ảnh đầu vào.

2.2.3. Kỹ thuật sử dụng mạng Neural nhân chập (Convolution neural network)

Kỹ thuật trích chọn đặc trưng sử dụng mạng neural nhân chập được đề xuất đầu

tiên bới LeCun và Bengio vào năm 1995. Đây là kỹ thuật trích chọn đặc trưng cho độ

chính xác nhận dạng cao nhất hiện nay (đạt độ chính xác đến 99.6% với bộ dữ liệu

MNIST).Trước khi đi sâu vào chi tiết thuật toán xin giới thiệu khái niệm cơ sở đó là:

thao tác nhân chập trong xử lý ảnh (convolutionoperator).

2.2.3.1 Khái niệm cơ sở

Thao tác nhân chập

Nhân chập là một khái niệm quen thuộc trong xử lý số tín hiệu, trong lĩnh vực

xử lý ảnh thao tác nhân chập được dùng để biến đổi ảnh thành một dạng mong muốn

nào đấy: như làm nổi cạnh (detect edge), là mượt ảnh (smoothing), làm sắc nét

(sharpening)... Trong thao tác nhân chập người ta sử dụng mặt nạ nhân chập

(convolution mask)-là ma trận vuông 2 chiều có kích thước là số lẻ (thông thường là

3x3 và 5x5) và tác động nhân chập vào tất cả các điểm của ảnh gốc. Thao tác nhân

chập lên một điểm của ảnh gốc được thực hiện như sau:

+Bước 1: Đầu tiên tâm của mặt nạ nhân chập được đặt trùng vào điểm cần tính

nhân chập.

+Bước 2: Thực hiện nhân từng giá trị của mặt nạ nhân chập với giá trị độ sáng

của điểm ảnh tương ứng

+Bước 3: Cộng tổng của từng giá trị đã tính ở bước 2 kết quả lưu vào vị trí

nhân chập của ảnh gốc.

Hình 13: Thao tác nhân chập

2.2.3.2 Kỹ thuật trích đặc trưng sử dụng mạng Neural nhân chập

Tư tưởng chính của kỹ thuật này là biến một bức ảnh từ độ phân giải cao về ảnh

có độ phân giải thấp hơn nhưng lại mang nhiều thông tin hơn cho quá trình nhận dạng

hơn (bằng phép nhân chập và thu nhỏ ảnh). Kỹ thuật này đạt hiệu quả cao cho việc

trích đặc trưng chữ viết tay là bởi vìnhờ thao tác nhân chập nó làm nổi bật lên được

các đường nét, hình dạng, các giao điểm... của ký tự viết tay. Hơn nữa các đặc trưng

của nó ít bị thay đổi bởi các phép dịch ảnh và phép biến dạng bóp méo ảnh

(distortion).

1) Kiến trúc mạng

Ta giả thiết ảnh đầu vào có kích thước 29x29, dưới đây là kiến trúc mạng để lấy

đặc trưng:

+Bước 1: Đầu tiên ta sử dụng 5 mặt nạ nhân chập khác nhau kích thước 5x5 thực

hiện thao tác nhân chập lên ảnh gốc, sau khi nhân chập ta thực hiện phép thu nhỏ ảnh đi

2 lần.Vì quá trình nhân chập không tác động lên những điểm biên nên sau một phép nhân

chập và thu nhỏ thì kích thước mới của ảnhsẽ là (n-3)/2 (n là kích thước ảnh ban đầu).

+Bước 2: Với mỗi ảnh ở lớp thứ 2 ta dùng 10 mặt nạ nhân chập khác nhau kích

thước 5x5 thực hiện nhân chập và thu nhỏ ảnh đi 2 lần, ta được 50 ảnh ở lớp thứ 3.

+Bước 3: với mỗi ảnh ở lớp thứ 3 ta lại dùng 2 mặt nạ nhân chập khác nhau

kích thước 5x5 thực hiện nhân chập ta thu được 100 ảnh kích thước 1x1.Ta xem đây

chính là 100 đặc trưng của ảnh gốc ban đầu.

Hình 14: Quá trình trích chọn đặc trưng sử dụng mạng Neural nhân chập

Hình 15: Minh họa quá trình lấy đặc trưng bằng mạng Neuron nhân chập

2) Huấn luyện mạng

Quá trình huấn luyện mạng Neural nhân chập là quá trình xác định các hệ số của

các mặt nạ nhân chập. Để làm được điều nàyngười ta xem kiến trúc ở hình 14 như là

một mạng Neural tuyến tính truyền thẳng nhiều tầng sau đó thêm bộ phân lớp tuyến

tính vào sau, rồi người ta huấn luyện mạng bằng phương pháp lan truyền ngược

2.3. Huấn luyện mạng

2.3.1. Các phương pháp học

Hình trạng mạng và trọng số của các liên kết bên trong mạng quyết định chức

năng của một mạng nơron. Hình trạng của mạng bao gồm số lớp, số đơn vị trên mỗi

tầng, và cách mà các lớp được liên kết với nhau của mạng và thường là cố định. Một

thuật toán huấn luyện được lưa chọn sẽ quyết định các trọng số. Tiến trình điều chỉnh

các trọng số để mạng “nhận biết” được quan hệ giữa đầu vào và đích mong muốn

được gọi là học hay huấn luyện. Rất nhiều thuật toán học đã được phát minh để tìm ra

tập trọng số tối ưu làm giải pháp cho các bài toán. Có hai nhóm thuật toán chính: Học

có giám sát (Supervised learning) và học không có giám sát (Unsupervised Learning).

a. Học có giám sát

Học có giám sát là cách học mà mạng được huấn luyện bằng cách cung cấp cho

nó các cặp mẫu đầu vào và các đầu ra mong muốn. Sự khác biệt giữa các đầu ra thực

tế so với các đầu ra mong muốn được thuật toán sử dụng để thích ứng các trọng số

trong mạng. Điều này thường được đưa ra như một bài toán xấp xỉ hàm số - cho dữ

liệu huấn luyện bao gồm các cặp mẫu đầu vào x, và một đích tương ứng t, mục đích là

tìm ra hàm f(x) thoả mãn tất cả các mẫu học đầu vào.

Hình 16: Mô hình học có giám sát.

b. Học không có giám sát

Với cách học không có giám sát, không xác định được đầu ra của mạng có đúng

hay chưa bởi vì không có phản hồi từ môi trường. Mạng sẽ phải tự động khám phá

các đặc trưng, các điều chỉnh, các mối tương quan, hay các lớp trong dữ liệu vào một

cách. Trong thực tế, đối với phần lớn các biến thể của học không có giám sát, các đích

trùng với đầu vào. Nói một cách khác, học không có giám sát luôn thực hiện một công

việc tương tự như một mạng tự liên hợp, cô đọng thông tin từ dữ liệu vào.

2.3.2. Học có giám sát trong các mạng nơron

Học có giám sát có thể được xem như việc xấp xỉ một ánh xạ: X→ Y, trong đó X

là tập các vấn đề và Y là tập các lời giải tương ứng cho vấn đề đó. Các mẫu (x, y) với

x = (x1, x2,..., xn) ∈ X, y = (yl, y2,…,ym) ∈ Y được cho trước. Học có giám sát trong

các mạng nơron thường được thực hiện theo các bước sau:

Bước 1: mạng nơron cần được xây dựng cấu trúc thích hợp, ví dụ có (n + 1)

nơron vào (n nơron cho biến vào và 1 nơron cho ngưỡng x0), m nơron đầu ra, và khởi

tạo các trọng số liên kết của mạng.

Bước 2: Đưa một vector x trong tập mẫu huấn luyện X vào mạng

Bước 3: Tính vector đầu ra o của mạng

Bước 4: So sánh vector đầu ra mong muốn y (là kết quả được cho trong tập huấn

luyện) với vector đầu ra o do mạng tạo ra; nếu có thể thì đánh giá lỗi.

Bước 5:Hiệu chỉnh các trọng số liên kết theo một cách nào đó sao cho ở lần tiếp

theo khi đưa vector x vào mạng, vector đầu ra o sẽ giống với y hơn.

Bước 6: Nếu cần, lặp lại các bước từ 2 đến 5 cho tới khi mạng đạt tới trạng thái

hội tụ. Việc đánh giá lỗi có thể thực hiện theo nhiều cách, cách dùng nhiều nhất là sử

dụng lỗi tức thời: Err = (o - y), hoặc Err = |o - y|; lỗi trung bình bình phương (MSE:

mean-square error): Err = (o- y)2/2;

Có hai loại lỗi trong đánh giá một mạng nơron:

- Thứ nhất, gọi là lỗi rõ ràng, đánh giá khả năng xấp xỉ các mẫu huấn luyện của

một mạng đã được huấn luyện.

- Thứ hai, gọi là lỗi kiểm tra, đánh giá khả năng tổng quá hóa của một mạng đã

được huấn luyện, tức khả năng phản ứng với các vector đầu vào mới. Để đánh giá lỗi

kiểm tra chúng ta phải biết đầu ra mong muốn cho các mẫu kiểm tra.

Thuật toán tổng quát ở trên cho học có giám sát trong các mạng nơron có nhiều

cài đặt khác nhau, sự khác nhau chủ yếu là cách các trọng số liên kết được thay đổi

trong suốt thời gian học. Trong đó tiêu biểu nhất là thuật toán lan truyền ngược.

2.3.3. Thuật toán lan truyền ngược Back-Propagation

Sau đây là mô tả của thuật toán “học”, sử dụng để điều chỉnh hiệu năng của

mạng sao cho mạng có khả năng sinh ra được các kết quả mong muốn.

Như đã nêu, về cơ bản có hai dạng thuật toán để luyện mạng: học có giám sát và

học không có giám sát. Các mạng nơron truyền thẳng nhiều lớp được luyện bằng

phương pháp học có giám sát. Phương pháp này căn bản dựa trên việc yêu cầu mạng

thực hiện chức năng của nó và sau đó trả lại kết quả, kết hợp kết quả này với các đầu

ra mong muốn để điều chỉnh các tham số của mạng, nghĩa là mạng sẽ học thông qua

những sai sót của nó.

Thuật toán lan truyền ngược là dạng tổng quát của thuật toán trung bình bình

phương tối thiểu. Thuật toán này thuộc dạng thuật toán xấp xỉ để tìm các điểm mà tại

đó hiệu năng của mạng là tối ưu. Chỉ số tối ưu thường được xác định bởi một hàm số

của ma trận trọng số và các đầu vào nào đó mà trong quá trình tìm hiểu bài toán đặt ra.

2.3.3.1. Mô tả thuật toán

Mạng lan truyền ngược là một hàm phi tuyến có thể xấp xỉ gần đúng nhất một

hàm đích được cho qua một số mẫu trong tập mẫu. Một mạng lan truyền tổng quát là

một mạng có n (n>2) lớp: lớp thứ nhất gọi là lớp nhập, lớp thứ n là lớp xuất và n-2 lớp

ẩn. Phần lớn các mạng chỉ có một biến phụ thuộc nhưng với mô hình tả trên mạng

nơron cho phép số nút trong lớp nhập, lớp xuất, và lớp ẩn là tùy ý. Sốnút trong lớp

nhập và lớp xuất phụ thuộc vào yêu cầu bài toán, số nút ẩn do người xây dựng mô

hình quyết định.

Trong mạng lan truyền mỗi nút trong lớp thứ i (0

lớp thứ (i+1), và các nút trong cùng lớp không liên kết với nhau. Ngoài ra còn có một

số cung liên kết trực tiếp từ các nút trong lớp nhập đến các nút trong lớp xuất, ta gọi

mạng này là mạng lan truyền có nối trực tiếp. Mỗi cung trong mạng được gắn với một

trọng số w Є R. Hình 12 minh họa một mạng lan truyền với một lớp ẩn:

Hình 17: Mạng lan truyền với một lớp ẩn.

Trong hình 17, mạng gồm ba lớp: lớp nhập (input), lớp ẩn (hidden), và lớp xuất

(output). Mỗi nút trong nút nhập nhận giá trị của một biến độc lập và chuyển vào

mạng. Dữ liệu từ tất cả các nút trong lớp nhập được tích hợp ta gọi là tổng trọng hóa

và chuyển kết quả cho các nút trong lớp ẩn. Tương tự các nút trong lớp xuất cũng

nhận các tín hiệu tổng trọng hóa từ các nút ẩn. Mỗi nút trong lớp xuất tương ứng với

một biến phụ thuộc.

Mạng lan truyền chỉ có thể ở một trong hai trạng thái: trạng thái ánh xạ và trạng

thái học. Trong trạng thái ánh xạ, thông tin lan truyền từ lớp nhập đến lớp xuất và

mạng thực hiện ánh xạ để tính giá trị các biến phụ thuộc dựa vào giá trị các biến độc

lập được cho. Trong trạng thái học, thông tin lan truyền theo hai chiều nhiều lần để

học các trọng số.

Trong trạng thái ánh xạ, mạng xử lý mỗi lần một mẫu để tính giá trị Y=NN(X).

Trước tiên giá trị của biến độc lập được cho lớp nhập của mạng. Các nút nhập không

tính toán gì cả. Mỗi nút nhập chuyển giá trị của nó cho tất cả các nút ẩn. Mỗi nút ẩn

tính tổng trọng hóa của tất cả các dữ liệu nhập bằng cách cộng dồn tất cả các tích giữa

giá trị nút ẩn với trọng số của cung liên kết giữa nút nhập và nút ẩn. Kế tiếp, một hàm

kích hoạt được áp dụng trên tổng trọng hóa này cùng với một ngưỡng của nút ẩn đó

để cho ra giá trị thực của nút ẩn. Hàm kích hoạt đơn giản chỉ nén giá trị vào một miền

giới hạn nào đó. Sau khi nén tổng trọng hóa của nó, đến lượt mình, mỗi nút ẩn sẽ gửi

kết quả đến tất cả các nút xuất. Mỗi nút xuất thực hiện các thao tác tương tự như đã

thực hiên trong nút ẩn để cho giá trị kết xuất của nút xuất. Giá trị của các nút xuất

chính là giá trị của các biến phụ thuộc cần xác định.

Bản chất ánh xạ do mạng thực hiện tùy thuộc vào giá trị các trọng số trong

mạng. Lan truyền ngược là một phương pháp cho phép xác định tập trọng số tốt nhất

của mạng giải một bài toán được cho. Việc áp dụng phương pháp lan truyền ngược là

một quá trình lặp đi lặp lại hai tiến trình chính, ánh xạ và lan truyền ngược sai số. Hai

tiến trình này được áp dụng trên một tập mẫu xác định. Ta gọi chung tiến trình này là

luyện mạng hay còn gọi là học.

Quá trình luyện mạng đựợc bắt đầu với các giá trị trọng số tùy ý – có thể là ngẫu

nhiên – và tiến hành lặp đi lặp lại. Mỗi lần lặp gọi là một thế hệ. Trong mỗi thế hệ,

mạng hiệu chỉnh các trọng số sao cho sai số giảm dần. Sai số là độ lệch giữa kết quả

thực và kết quả đích. Tiến trình điều chỉnh nhiều lần giúp cho trọng số dần đạt các giá

trị tối ưu.

Để cập nhật trọng số trong mỗi thế hệ, mạng phải xử lý tất cả các mẫu trong tập

mẫu. Đối với từng mẫu, mạng sẽ thực hiên các thao tác sau đây:

- Trước tiên mạng thực hiên quá trình lan truyền tiến, nghĩa là mạng ánh xạ các

biến nhập của mẫu hiện hành thành các giá trị xuất.

- Kế tiếp sai số được tính dựa trên giá trị của kết xuất và giá trị đích. Trên cơ sở

sai số tính toán được, mạng sẽ cập nhật lại các trọng số theo nguyên tắc lan truyền

ngược sai số – gọi là lan truyền ngược.

Như vậy để học mỗi mẫu, mạng thực hiện hai bước: lan truyền tiến – thực hiện

ánh xạ và lan truyền ngược – cập nhật trọng số. Vì thế phương pháp này gọi tắt là lan

truyền ngược.

2.3.3.2. Sử dụng thuật toán Back – Propagation

Trên đây là thuật toán lan truyền ngược cơ bản, sau đây ta sẽ bàn về các khía

cạnh ứng dụng của thuật toán lan truyền ngược như chọn lựa cấu trúc mạng, sự hội tụ

và khả năng tổng quát hóa.

a. Lựa chọn cấu trúc mạng

Như ta đã biết, thuật toán lan truyền ngược có thể được sử dụng để xấp xỉ bất kỳ

một hàm số học nào nếu như ta có đủ số nơron trong các lớp ẩn. Mặc dù vậy, phát

biểu trên chưa cho ta được một số cụ thể các lớp và số nơron trong mỗi lớp cần sử

dụng. Ta sẽ dùng một ví dụ để có được cái nhìn chi tiết hơn về vấn đề này. Ví dụ, ta

muốn xấp xỉ hàm số sau:

trong đó i nhận các giá trị 1, 2, 4 và 8. Khi i tăng thì hàm số cần xét sẽ trở nên phức

tạp hơn do ta sẽ nhận được nhiều chu kỳ của hình sin trong phạm vi [-2, 2]. Khi đó,

mạng nơron với một số nơron cố định sẽ khó có thể xấp xỉ được hàm nếu i tăng.

Trong phần sau, ta sẽ sử dụng ví dụ Function Approximation trong thư viện của bộ

Matlab 5.3 (file nnd11fa.m). Ở đây, mạng sử dụng có 1 lớp ẩn, 1 lớp ra; đương nhiên,

mạng có 1 đầu vào và một đầu ra. Lớp ẩn sử dụng hàm sigmoid, lớp ra dùng hàm

đồng nhất:

Số nơron trong lớp ẩn là 4, kết quả xấp xỉ của mạng trong các trường hợp i = 1,

2, 4, 8 như trong các hình: Hình 13(a), hình 13(b), hình 13(c), hình 13(d) . Các đường

màu đen là trả lời của mạng, còn các đường mờ hơn là hàm cần xấp xỉ.

trường hợp i = 4 (c) trường hợp i = 1 (a)

trường hợp i = 8 (đ) trường hợp i = 2 (b)

Hình 18: xấp xỉ của mạng trong các trường hợp i = 1, 2, 4, 8

Khi ta tăng số nơron trong lớp ẩn lên thì khả năng xấp xỉ hàm số của mạng sẽ tốt

hơn. Chẳng hạn, xét trường hợp sử dụng 9 nơron trong lớp ẩn và i = 8 ta có được kết

quả như hình 13 (e) :

trường hợp i = 8 và số nơron lớp ẩn = 9 (e)

Điều đó có nghĩa là nếu ta muốn xấp xỉ một hàm số mà có số điểm cần xấp xỉ là

lớn thì ta sẽ cần số nơron lớn hơn trong lớp ẩn.

b. Sự hội tụ

Trong phần trên ta đã thấy các trường hợp mạng nơron không trả lại kết quả

chính xác mặc dù thuật toán lan truyền ngược đã thực hiện tối thiểu hóa trung bình

bình phương lỗi. Điều đó là do khả năng của mạng bị giới hạn bởi số nơron trong lớp

ẩn. Tuy nhiên, cũng có trường hợp mà thuật toán lan truyền ngược không cho ta các

tham số có thể dẫn đến kết quả chính xác nhưng mạng vẫn có thể xấp xỉ được hàm số.

Điều này xảy ra là do trạng thái khởi đầu của mạng, sau khi luyện, mạng có thể rơi

vào điểm cực tiểu toàn cục hoặc rơi vào điểm cực tiểu địa phương.

Cần chú ý rằng trong thuật toán trung bình bình phương tối thiểu, điểm cực trị

toàn cục là luôn tồn tại bởi lẽ hàm trung bình bình phương lỗi của thuật toán trung

bình bình phương tối thiểu là một hàm bậc hai, hơn nữa, do là hàm bậc hai nên đạo

hàm bậc hai của hàm lỗi sẽ là hằng số, do vậy mà độ cong của hàm theo một hướng

cho trước là không thay đổi.

Trong khi đó, thuật toán lan truyền ngược áp dụng cho các mạng nhiều lớp sử

dụng các hàm chuyển phi tuyến sẽ có nhiều điểm cực trị địa phương và độ cong của

hàm lỗi có thể không cố định theo một hướng cho trước.

c. tổng quát hóa

•Một số biến thể của thuật toán BP

Ta đã xem xét một số đặc điểm của thuật toán lan truyền ngược sử dụng kỹ thuật

giảm theo hướng. Mạng sử dụng thuật toán này tồn tại nhược điểm: rơi vào điểm cực

tiểu địa phương đối với mạng nơron truyền thẳng nhiều lớp sử dụng các hàm chuyển

phi tuyến. Hơn nữa, khi thực hiện luyện mạng bằng cách đưa từng mẫu vào, sau đó

thực hiện cập nhật tham số, sẽ làm ảnh hưởng đến quá trình học các mẫu khác. Do đó,

một phương pháp để tăng tốc độ hội tụ là sử dụng phương pháp học cả gói (batch

training), nghĩa là tất cả các mẫu được đưa vào mạng, sau đó mới thực hiện cập nhật

các tham số. Bây giờ ta sẽ xem xét một số biến thể của thuật toán lan truyền ngược sử

dụng phương pháp học cả gói nhằm vượt qua các nhược điểm này.

•Sử dụng tham số bước đà

Đây là một phương pháp heuristic dựa trên quan sát kết quả luyện mạng nhằm

làm tăng tốc độ hội tụ của thuật toán lan truyền ngược dựa trên kỹ thuật giảm nhanh

nhất. Thuật toán lan truyền ngược cập nhật các tham số của mạng bằng cách cộng

(2.8)

thêm vào một lượng thay đổi là:

Khi áp dụng thuật toán lan truyền ngược có sử dụng bước đà, phương trình trên

(2.9)

thay đổi như sau:

Người ta đã chứng tỏ rằng khi sử dụng tham số bước đà thì hệ số học có thể lớn

hơn rất nhiều so với thuật toán lan truyền ngược chuẩn không sử dụng tham số bước

đà trong khi vẫn giữ được độ tin cậy của thuật toán. Một điểm khác nữa là khi sử

dụng tham số bước đà thì sự hội tụ của thuật toán sẽ được tăng tốc nếu như thuật toán

đang đi theo một hướng bền vững (chỉ đi xuống trong một khoảng dài).

•Sử dụng hệ số học biến đổi:

Trong thực tế, các hàm hiệu năng có dạng biểu diễn hình học là không đồng đều,

có lúc có dạng phẳng (hàm không thay đổi giá trị hoặc thay đổi rất ít) hoặc có dạng

phễu (giá trị của hàm thay đổi rất nhanh khi thay đổi tham số đầu vào). Nếu ta chỉ sử

dụng hệ số học cố định thì có thể sẽ tốn thời gian tại các vùng phẳng. Vì vậy, tư tưởng

của thuật toán lan truyền ngược sử dụng hệ số học biến đổi là khi gặp vùng phẳng thì

tăng hệ số học lên và ngược lại khi gặp vùng dạng phễu thì giảm hệ số học đi. Người

ta đã đưa ra rất nhiều phương pháp để thực hiện điều trên, ở đây chỉ nêu ra một cách

biến đổi hệ số học dựa trên hiệu năng của mạng.

- Bước 1: Nếu bình phương lỗi trên toàn bộ tập huấn luyện tăng một số phần

trăm cho trước ξ (thông thường là từ 1% cho đến 5%) sau một lần cập nhật trọng số,

thì bỏ qua việc cập nhật này, hệ số học được nhân với một số hạng ρ nào đó (với 0 < ρ

< 1) và tham số bước đà (nếu có sử dụng) được đặt bằng 0.

-Bước 2: Nếu bình phương lỗi giảm sau một lần cập nhật trọng số, thì cập nhật

đó là chấp nhận được và hệ số học được nhân với một số hạng nào đó > 1, nếu tham

số bước đà đã bị đặt bằng 0 thì đặt lại giá trị lúc đầu.

-Bước 3: Nếu bình phương lỗi tăng một lượng < ξ, thì cập nhật trọng số là chấp

nhận được, nhưng hệ số học không thay đổi và nếu tham số bước đà đã bị đặt bằng 0

thì đặt lại giá trị lúc đầu.

Các thuật toán heuristic luôn cho ta sự hội tụ nhanh hơn trong một số bài toán,

tuy nhiên chúng có hai nhược điểm chính sau đây:

-Thứ nhất, việc sửa đổi thuật toán lan truyền ngược cần có thêm một số tham số,

trong khi trong thuật toán lan truyền ngược chuẩn chỉ yêu cầu có một tham số đó là hệ

số học. Một số thuật toán sửa đổi cần đến năm hoặc sáu tham số, trong khi hiệu năng

của thuật toán khá nhạy cảm đối với những thay đổi của các tham số này. Hơn nữa

việc chọn lựa các tham số lại độc lập với bài toán đặt ra.

-Thứ hai, các thuật toán sửa đổi có thể không hội tụ trong một số bài toán mà

thuật toán lan truyền ngược chuẩn có thể hội tụ được.

Người ta đã thấy rằng cả hai nhược điểm nêu trên thường xảy ra khi sử dụng các

thuật toán sửa đổi phức tạp hơn (yêu cầu nhiều tham số hơn).

•Sử dụng phương pháp Gradient kết hợp:

Nhắc lại phương pháp gradient kết hợp bao gồm các bước sau:

Bước 1: Chọn hướng bắt đầu ngược với gradient (p0 = -g0).

Bước 2: Thực hiện một bước (∆xk = (xk+1 - xk) = αkpk). Chọn αk để tối thiểu

hàm theo hướng tìm kiếm đã chọn. Có thể chọn như sau:

(2.10)

(phương trình trên được suy ra bằng cách chọn αk để tối thiểu hóa hàm F(xk +

αkpk). Để thực hiện, ta lấy đạo hàm của F theo αk, đặt bằng 0 ta sẽ thu được phương

trình trên.)

(2.11)

Bước 3: Nếu thuật toán chưa hội tụ thì quay lại bước 2.

Phương pháp này không thể áp dụng trực tiếp trong việc luyện mạng nơron, bởi

lẽ hàm chỉ số hiệu năng trong nhiều trường hợp không ở dạng bậc hai. Điều này ảnh

hưởng đến thuật toán này như sau:

(2.12)

-Thứ nhất, ta không thể sử dụng phương trình:

để tối thiểu hóa hàm theo đường thẳng (xk + αkpk) như trong bước thứ 2.

-Thứ hai, điểm cực tiểu chính xác sẽ không thể đạt tới được một cách bình

thường sau một số hữu hạn bước và do vậy thuật toán sẽ phải được thiết lập lại sau

một số hữu hạn bước.

d. Vấn đề tìm kiếm điểm cực tiểu

Ta cần có một thuật toán tổng quát để tìm điểm cực tiểu của một hàm số theo

một hướng cụ thể nào đó. Việc này liên quan đến hai thao tác: một là xác định tần số

(interval location) và giảm tần số. Mục đích của bước xác định tần số là tìm kiếm tần

số khởi đầu có chứa điểm cực tiểu. Bước giảm tần số sau đó giảm kích thước của tần

số cho đến khi tìm ra điểm cực tiểu với một độ chính xác nào đó.

Ta sẽ sử dụng phương pháp so sánh hàm để thực hiện bước xác định tần số. Thủ

tục này được mô tả trong hình 14 . Ta bắt đầu bằng cách tính chỉ số hiệu năng tại một

điểm khởi đầu nào đó (điểm a1 trong hình vẽ), điểm này chính là giá trị của chỉ số

hiệu năng với các tham số hiện tại của mạng.

Bước tiếp theo là tính giá trị hàm chỉ số hiệu năng tại điểm thứ 2, thể hiện bởi

điểm b1 trong hình vẽ cách điểm khởi đầu một đoạn là ε theo hướng tìm kiếm p0.

Hình 19: Xác định tần số.

Sau đó, ta tiếp tục tính giá trị của hàm hiệu năng tại các điểm bi có khoảng cách

đến điểm khởi đầu gấp đôi điểm trước. Quá trình này sẽ dừng lại nếu như giá trị của

hàm tăng lên so với điểm trước đó (trong hình vẽ là điểm b3 và b4). Đến đây, ta biết

rằng điểm cực tiểu sẽ rơi vào khoảng giữa [a5, b5]. Ta không thể thu hẹp thêm tần số

nữa bởi lẽ điểm cực tiểu có thể rơi vào vùng [a3, b3] hoặc [a4, b4].

Bây giờ ta tiếp tục bước thực hiện giảm tần số, ta sẽ lấy ít nhất là hai điểm c, d

trong khoảng [a5, b5] để có thể thực hiện việc này (nếu chỉ lấy 1 điểm thì ta khó có

thể xác định được liệu điểm cực tiểu sẽ nằm trong vùng nào). Có nhiều cách để chọn

các điểm trên, ở đây ta sẽ sử dụng phương pháp gọi là: Golden Section search.

Phương pháp này cố gắng thực hiện tìm kiếm sao cho số lần phải tính giá trị của hàm

là ít nhất (tại mỗi một bước ta đều cần phải tính giá trị của hàm).

2.3.3.3. Đánh giá thuật toán

Đưa các mẫu học từ miền của bài toán vào mạng là việc huấn luyện mạng theo

phương pháp học có giám sát liên quan đến cách thức. Các mẫu này sẽ được phân chia

thành các tập huấn luyện và tập kiểm thử. Mạng được khởi tạo các trọng số là các số

ngẫu nhiên, sau đó, các trọng số này sẽ được điều chỉnh cho phù hợp với tập huấn

luyện. Tập kiểm thử sẽ được dùng để xác định xem tỉ lệ thành công trong việc xác định

đầu ra từ đầu vào mà nó chưa được luyện. Mạng sẽ được đưa vào một tập con các mẫu,

mỗi mẫu một lần, sau khi nó biết tất cả các mẫu, nó sẽ phải thực hiện điều chỉnh các

trọng số bằng cách tính toán các lỗi xảy ra. Quá trình này được lặp lại cho đến khi

mạng được luyện đủ. Kích thước của tập con được giới hạn bởi số lần lặp, có thể là

trùng với kích thước của tập mẫu học, nếu không như vậy thì cần phải xác định thứ tự

đưa các mẫu vào cho mạng học một cách ngẫu nhiên.

•Ưu điểm của thuật toán:

-Dễ dàng triển khai;

-Phương pháp chuẩn và hoạt động tốt;

-Thời gian tính toán giảm nếu các trọng số được chọn ban đầu nhỏ;

-Không yêu cầu đặc tính đặc biệt của hàm được học.

•Nhược điểm thuật toán:

-Có thể bị vướng vào tối thiểu địa phương trong nghiệm tối ưu;

-Số lượng lớn đầu vào/đầu ra nhưng không chắc chắn về sự liên hệ giữa chúng

với đầu ra;

-Nghiệm của phương trình có thể thay đổi theo thời gian;

-Đầu ra có thể mờ và không phải là số.

2.4. Nhận dạng sử dụng mạng nơron

2.4.1. Khả năng sử dụng mạng nơron trong nhận dạng

Xét trường hợp đối tượng phi tuyến tính có độ phức tạp cao, nếu sử dụng

phương pháp giải tích thông thường để nhận dạng sẽ rất khó khăn, thậm chí không

thực hiện được do sự hiểu biết nghèo nàn về đối tượng. Vì vậy các nhà khoa học đã

đưa ra ý tưởng là sử dụng công cụ tính toán mềm như hệ mờ, mạng nơron, đại số gia

tử để xấp xỉ. Mạng nơron là một trong những công cụ hữu hiệu để nhận dạng mô

hình đối tượng. Bằng phương pháp này ta không biết được mô hình toán thực sự của

đối tượng nhưng hoàn toàn có thể dùng kết quả xấp xỉ để thay thế đối tượng.

Vì tính phi tuyến của các mạng nơron (hàm kích hoạt phi tuyến), chúng được

dùng để mô tả các hệ thống phi tuyến phức tạp. Mạng nơron là một trong những

công cụ nhận dạng tốt nhất vì các đặc trưng sau: khả năng học từ kinh nghiệm hay

được huấn luyện, khả năng khái quát hoá cho các đầu vào không được huấn luyện.

Mạng nơron có khả năng xấp xỉ các hàm phi tuyến một cách đầy đủ và chính

xác, nó được sử dụng tốt cho các mô hình động học phi tuyến. Điều quan trọng được

sử dụng là thuật truyền ngược tĩnh và động của mạng nơron, nó được sử dụng để

hiệu chỉnh các tham số trong quá trình nhận dạng.

Nền tảng cho tính xấp xỉ hàm của mạng nơron nhiều lớp là định lý Kolmgorov

và định lý Stone - Weierstrass. Các mạng Nơron nhân tạo đưa ra những lợi thế qua

việc học sử dụng phân loại và xử lý song song, điều này rất phù hợp với việc dùng

trong nhận dạng.

2.4.2. Mô hình nhận dạng hệ thống sử dụng mạng nơron

Khi xét một bài toán điều khiển, trước tiên ta cần phải có những hiểu biết về đối

tượng: số đầu vào, số đầu ra, các đại lượng vật lý vào ra, dải giá trị của chúng, quy

luật thay đổi của các đại lượng trong hệ hay mô hình toán học cơ bản của nó,...Tuy

nhiên không phải đối tượng nào hay hệ nào cũng cung cấp được đầy đủ các thông tin

như trên cũng như xây dựng được mô hình thực từ những thông tin ấy.

Việc nhận dạng là việc đầu tiên và quan trọng. Khi thông số của đối tượng là cần

thiết để việc điều khiển đạt chất lượng mong muốn. Khi thông số của đối tượng tự

thay đổi trong tiến trình làm việc (đối tượng phi tuyến) và có tính động học thì việc

nhận dạng theo chúng sẽ phức tạp hơn nhiều so với đối tượng có thông số bất biến.

Nhận dạng thường chia ra làm: nhận dạng mô hình và nhận dạng tham số. Nhận

dạng mô hình là quá trình xác định mô hình của đối tượng và thông số trên cơ sở đầu

vào và đầu ra của đối tượng. Mô hình thu được sau khi nhận dạng gọi là tốt nếu nó thể

hiện được đúng đối tượng. Như vậy có thể sử dụng mô hình thay cho đối tượng để dự

báo, kiểm tra và điều khiển. Mạng nơron được luyện để mô hình hóa quan hệ vào ra

của đối tượng. Như vậy quy trình nhận dạng mô hình có bản chất là thuật toán luyện

mạng Cấu trúc mạng nơron giải bài toán nhận dạng mô hình rất đa dạng, tùy thuộc

vào từng bài toán cụ thể.

Nhận dạng tham số chính là huấn luyện mạng. Mô hình cơ bản của mạng nơron

được luyện để mô phỏng hành vi của đối tượng giống như mô hình truyền thống được

biểu diễn trên Hình 15.

Hình 20: Mô hình nhận dạng cơ bản.

Tín hiệu sai là cơ sở cho quá trình luyện mạng. Mạng nơron ở đây có thể là mạng

nhiều lớp hoặc các dạng khác và có thể sử dụng nhiều thuật luyện mạng khác nhau.

2.4.3. Nhận dạng hệ thống sử dụng mạng nơron

Như vậy hai giai đoạn cần cho nhận dạng đó là lựa chọn mô hình và tối ưu tham số.

Đối với mạng nơron dựa vào nhận dạng lựa chọn số nút ẩn, số lớp ẩn (cấu trúc của

mạng) tương đương với mô hình lựa chọn. Mạng có thể được huấn luyện theo kiểu giám

sát với kỹ thuật lan truyền ngược, dựa vào luật học sai số hiệu chỉnh. Tín hiệu sai số được

lan truyền ngược qua mạng. Kỹ thuật lan truyền ngược sử dụng phương pháp giảm

gradient để xác định các trọng của mạng vì vậy tương đương với tối ưu tham số. Mạng

nơron được huấn luyện để xấp xỉ mối quan hệ giữa các biến.Mạng nơron được huấn

luyện để tối thiểu hàm sai số. Mạng được huấn luyện để tối thiểu sai số bình phương giữa

đầu ra của mạng và đầu vào hệ thống, xác định một hàm truyền ngược. Trong kiểu nhận

dạng này đầu ra của mạng hội tụ về đầu vào hệ sau khi huấn luyện, vì vậy mạng đặc

trưng cho hàm truyền ngược của hệ. Phương pháp nhận dạng khác cần phải hướng đầu ra

hệ thống tới đầu ra của mạng. Trong kiểu này mạng đặc trưng cho hàm truyền thẳng của

hệ thống. Giả sử các hàm phi tuyến để mô tả hệ thuộc lớp hàm đã biết trong phạm vi

quan tâm thì cấu trúc của mô hình nhận dạng phải phù hợp với hệ thống. Với giả thiết

các ma trận trọng của mạng nơron trong mô hình nhận dạng tồn tại, cùng các điều kiện

ban đầu thì cả hệ thống và mô hình có cùng lượng ra với bất kỳ lượng vào xác định. Do

đó quá trình nhận dạng thực chất là điều chỉnh tham số của mạng nơron dựa vào sai lệch

giữa các giá trị đầu ra của hệ thống và của mô hình.

Chương 3: CHƯƠNG TRÌNH THỬ NGHIỆM

3.1. Đặc trưng của phiếu điểm

Trước tiên, một vài điều kiện cần phải được áp đặt lên việc ghi phiếu để quá

trình phân đoạn cũng như nhận dạng diễn ra thuận lợi đó là:

-Viết rõ ràng, không đứt đoạn, không chồng chéo.

-Điểm được viết đúng vị trí, đúng ô, không đè lên các đường bao quanh ô, không

dập xóa lên phiếu.

Đặc trưng chung của các mẫu phiếu điểm rèn luyện là phần trên cùng gồm tên

phiếu điểm, các thông tin mô tả của phiếu điểm (tên sinh viên, tên lớp, khoa…). Phần

tiếp theo là điểm của sinh viên được ghi trong một bảng gồm nhiều hàng, mỗi hàng là

số điểm của sinh viên theo một tiêu chí. Các cột số điểm do sinh viên tự đánh giá, lớp

đánh giá và khoa đánh giá.

Mẫu phiếu điểm đánh giá rèn luyện: Phiếu điểm gồm các cột thông tin: Nội

dung đánh giá, điểm số, điểm do sinh viên tự đánh giá, điểm do lớp đánh giá, điểm do

hội đồng khoa đánh giá. Giáo viên sau khi chấm bài thi sẽ ghi điểm vào các phiếu này.

Hình 21: Mẫu phiếu điểm đánh giá rèn luyện

Mẫu phiếu điểm tổng kết: Phiếu điểm tổng kết gồm các cột thông tin: số thứ tự,

mã sinh viên, họ tên, điểm rèn luyện, ghi chú.

Hình 22: Mẫu phiếu điểm tổng kết

3.2. Bài toán

Hiện nay, đa phần các trường học đều sử dụng phần mềm tin học để quản lý

điểm rèn luyện. Việc này, giúp việc quản lý được chính xác, tra cứu nhanh chóng.

Tuy nhiên, theo tìm hiểu của tác giả thì các phần mềm này đều cho chỉ cho phép in

phiếu điểm để các giáo viên chấm thi nhập điểm rồi người phụ trách điểm phải có

trách nhiệm nhập điểm bằng tay. Mặc dù các phần mềm hiện nay đều có chức năng in

kiểm dò, nhưng công việc này vẫn hoàn toàn thủ công dẫn tới có nhiều sai sót.

Bài toán nhập điểm tự động nếu được giải quyết sẽ khắc phục được các vấn đề

mà tác giả đã nêu ở trên. Việc nhập điểm tự động sẽ là quá trình thu thập ảnh biên bản

chấm thi (thông thường qua máy Scanner) sau đó sẽ xử lý để đưa ra được bảng điểm

chính xác dưới dạng số trên máy tính. Trong bài toán này, có hai bài toán nhỏ cần giải

quyết đó là: Xác định vùng chứa dữ liệu điểm và nhận dạng chữ số viết tay. Trong

phạm vi nghiên cứu của luận văn, tác giả sẽ đi tập trung nghiên cứu vào việc nhận

dạng chữ số viết tay.

3.3. Tiền xử lý

Giai đoạn này góp phần làm tăng độ chính xác phân lớp của hệ thống nhận dạng,

tuy nhiên nó cũng làm cho tốc độ nhận dạng của hệ thống chậm lại. Vì vậy, tùy thuộc

vào chất lượng ảnh quét vào của từng phiếu điểm cụ thể để chọn một hoặc một vài

chức năng trong khối này. Nếu cần ưu tiên tốc độ xử lý và chất lượng của máy quét

tốt thì có thể bỏ qua giai đoạn này. Khối tiền xử lý bao gồm một số chức năng: Nhị

phân hóa ảnh, lọc nhiễu, chuẩn hóa kích thước ảnh, làm trơn biên chữ, làm đầy chữ,

làm mảnh chữ và xoay văn bản.

Nhị phân hóa ảnh

Nhị phân hóa ảnh là một kỹ thuật chuyển ảnh đa cấp xám sang ảnh nhị phân.

Trong bất kỳ bài toán phân tích hoặc nâng cao chất lượng ảnh nào, nó cũng cần thiết

để xác định các đối tượng quan trọng. Nhị phân hóa ảnh phân chia ảnh thành 2 phần:

phần nền và phần chữ. Hầu hết các phương pháp nhị phân hóa ảnh hiện nay đều lựa

chọn một ngưỡng thích hợp theo cường độ sáng của ảnh và sau đó chuyển tất cả các

giá trị độ sáng lớn hơn ngưỡng đó thành một giá trị độ sáng (ví dụ “trắng”) và tất cả

các giá trị bé hơn ngưỡng thành một giá trị độ sáng khác (“đen”).

Hình 23: Nhị phân hóa ảnh.

Lọc nhiễu

Nhiễu là một tập các điểm sáng thừa trên ảnh. Khử nhiễu là một vấn đề thường

gặp trong nhận dạng, nhiễu có nhiều loại (nhiễu đốm, nhiễu vệt, nhiễu đứt nét...).

Hình 24: Lọc nhiễu.

Để khử các nhiễu đốm (các nhiễu với kích thước nhỏ), có thể sử dụng các

phương pháp lọc (lọc trung bình, lọc trung vị...). Tuy nhiên, với các nhiễu vệt (hoặc các

nhiễu có kích thước lớn) thì các phương pháp lọc tỏ ra kém hiệu quả, trong trường hợp

này sử dụng phương pháp khử các vùng liên thông nhỏ tỏ ra có hiệu quả hơn.

Chuẩn hóa kích thước ảnh

Hình 25: Chuẩn hóa kích thước ảnh các số “4” và “6”.

Việc chuẩn hóa kích thước ảnh dựa trên việc xác định trọng tâm ảnh, sau đó xác

định khoảng cách lớn nhất từ tâm ảnh đến các cạnh trên, dưới, trái, phải của hình chữ

nhật bao quanh ảnh. Thông qua khoảng cách lớn nhất đó, có thể xác định được một tỷ

lệ co, giãn của ảnh gốc so với kích thước đã xác định, từ đó hiệu chỉnh kích thước ảnh

theo tỷ lệ co, giãn này. Như vậy, thuật toán chuẩn hóa kích thước ảnh luôn luôn đảm

bảo được tính cân bằng khi co giãn ảnh, ảnh sẽ không bị biến dạng hoặc bị lệch.

Làm trơn biên chữ

Đôi khi do chất lượng quét ảnh quá xấu, các đường biên của chữ không còn giữ

được dáng điệu trơn tru ban đầu mà hình thành các đường răng cưa giả tạo. Trong các

trường hợp này, phải dùng các thuật toán làm trơn biên để khắc phục.

(a) Ảnh gốc, (b) Ảnh sau khi được làm trơn biên.

Hình 26: Làm tròn biên chữ.

Chức năng này được áp dụng với các ký tự bị đứt nét một cách ngẫu nhiên. Ảnh

đứt nét gây khó khăn cho việc tách chữ, dễ bị nhầm hai phần liên thông của ký tự

thành hai ký tự riêng biệt, tạo nên sai lầm trong quá trình nhận dạng.

Làm mảnh chữ

Đây là một bước quan trọng nhằm phát hiện khung xương của ký tự bằng cách

loại bỏ dần các điểm biên ngoài của các nét. Tuy nhiên, quá trình làm mảnh chữ rất

nhạy cảm với việc khử nhiễu.

Hình 27: Làm mảnh chữ.

Điều chỉnh độ nghiêng của văn bản

Do trang tài liệu quét vào không cẩn thận hoặc do sự cố in ấn, các hàng chữ bị

lệch so với lề chuẩn một góc α, điều này gây khó khăn cho công đoạn tách chữ, đôi

khi không thể tách được. Trong những trường hợp như vậy, phải tính lại tọa độ điểm

ảnh của các chữ bị sai lệch. Có nhiều kỹ thuật để điều chỉnh độ nghiêng, kỹ thuật phổ

biến nhất dựa trên cơ sở biểu đồ chiếu (projection profile) của ảnh tài liệu; một số kỹ

thuật dựa trên cơ sở các phép biến đổi Hough và Fourier.

3.4. Phân đoạn và trích chọn đặc trưng

Khối này có nhiệm vụ tách từng ký tự ra khỏi phiếu điểm. Chỉ khi nào phiếu điểm

được tách và cô lập từng dòng (ứng với thông tin điểm của từng sinh viên) và cô lập

đúng từng ký tự đơn ra khỏi tổng thể hệ thống mới có thể nhận dạng đúng ký tự đó.

Trích chọn đặc trưng đóng vai trò cực kỳ quan trọng trong một hệ thống nhận

dạng. Trong trường hợp đơn giản nhất, ảnh đa cấp xám hoặc ảnh nhị phân được sử

dụng cho việc nhận dạng. Tuy nhiên, trong hầu hết các hệ nhận dạng, để giảm độ

phức tạp và tăng độ chính xác của các thuật toán phân lớp thì đòi hỏi các đặc trưng

được trích chọn phải rút gọn lại càng nhỏ càng tốt nhưng vẫn phải đảm bảo được

thông tin của ký tự. Với mục tiêu này, một tập các đặc trưng được trích chọn cho mỗi

lớp sao cho có thể phân biệt được với các lớp khác.

Hình 28: Tách thông tin phiếu điểm.

3.5. Huấn luyện và nhận dạng

Tập dữ liệu huấn luyện sau khi qua các khâu tiền xử lý và trích chọn đặc trưng sẽ

được đưa vào máy huấn luyện mô hình mạng nơron. Sau khi kết thúc quá trình huấn

luyện, hệ thống sẽ lưu lại giá trị các tham số của hàm quyết định phân lớp để phục vụ

cho việc nhận dạng sau này

3.6. Hậu xử lý

Đây là công đoạn cuối của quá trình nhận dạng phiếu điểm. Có thể hiểu hậu xử

lý là bước ghép nối các kí tự, điểm đã nhận dạng và chuyển vào cơ sở dữ liệu lưu trữ

điểm của sinh viên, đồng thời phát hiện ra các lỗi nhận dạng sai bằng cách kiểm tra

giá trị số báo danh, số phách, điểm số dựa trên các miền giá trị của chúng. Việc phát

hiện ra các lỗi, các sai sót trong nhận dạng ở bước này góp phần đáng kể vào việc

nâng cao chất lượng nhận dạng phiếu điểm.

PHẦN KẾT LUẬN

Trong các giai đoạn của một hệ thống nhập điểm tự động, giai đoạn phân đoạn

và trích chọn đặc trừng là khó khăn và đòi hỏi nhiều thời gian do ảnh thu được từ các

thiết bị thường bị sai lệch do các yếu tố như góc quay, khoảng cách, ánh sáng, ... Phần

lớn kết quả nhận dạng sai là do không trích chọn được những đặc trưng của ảnh. Đề

tài đã nghiên cứu một số kỹ thuật trích chọn đặc trưng và nhận dạng ảnh bằng phương

pháp mạng nơron.

Trong thời gian nghiên cứu và thực hiện luận văn, tác giả đã đạt được một số kết

quả sau:

- Nghiên cứu một số kỹ thuật tiền xử lý ảnh nhằm nâng cao chất lượng ảnh đầu vào;

- Nghiên cứu một số kỹ thuật trích chọn đặc trưng trong ảnh: Kỹ thuật trích chọn

đặc trưng kết hợp biến đổi DCT và thuật toán phân tích thành phần chính PCA, kỹ

thuật trích đặc trưng sử dụng Momen Legendre, Kỹ thuật sử dụng mạng Neural nhân

chập (Convolution neural network).

- Thiết kế chương trình trích nhận dạng ảnh dựa vào mạng nơron. Chương trình

cho phép nhận ảnh bảng điểm từ file.

TÀI LIỆU THAM KHẢO

Tiếng việt

[1] Lương Ma ̣nh Bá, Nguyễn Thanh Thủy (1999), Nhập môn xử lý ảnh số ,

NXB Khoa ho ̣c kỹ thuâ ̣t.

[2] Đỗ Năng Toàn (2010), Giáo trình xử lý ảnh, Ho ̣c viện Công nghê ̣ Bưu

chính Viễn thông. Tiếng anh

[3] D. Heckenberg, B. C. Lovell (2000), “A Gesture Driven Computer

Interface”, Proceeding of Visual Communications and Image Processing, SPIE, 4067,

261-268.

[4] Journal on Graphics (2006), Vision and Image Processing, 6.

[5] J. Mathews (2002), “An Introduction to Edge Detection: The Sobel Edge

Detector”.

[6] Peter l. Rockett (2005), “An Improved Rotation-Invarient Thinning

Algorithm”, IEEE transaction on Pattern, Analysis and Machine Intelligence,

27, 10.

[7] Te-Hsiu Sun, Fang-Chih Tien (2008), Using Backpropagation Neural

Network for Face Recognition with 2D+ 3D Hybrid Information, Elsevier: Expert

System with Applications, 35,361-372.

[8] N. Sakai, S. Yonekawa and A. Matsuzaki, Two-dimensional image

analysis of the shape of rice and its applications to separating varieties”, Journal of

Food Engineering, vol 27, 1996, pp. 397-407.

[9] A. J. M. Timmermans, and A. A. Hulzebosch, Computer vison system for

on-line sorting of pot plants using an artificial neural network classifier, Computers

and Electronics in Agriculture, vol. 15, 1996, pp. 41-55.

[10]

S. Abbasi, F. Mokhtarian, and J. Kittler, Reliable classification of

chrysanthemum leaves through curvature scale space, Lecture Notes in Computer

Science, vol. 1252, 1997, pp. 284-295.

[11] J. Camarero, S. Siso, and E.G-Pelegrin, Fractal dimension does not

adequately describe the complexity of leaf margin in seedlings of Quercus species,

Anales del Jardín Botánico de Madrid, vol. 60, no. 1, 2003, pp. 63-71.

Các trang website tham khảo

[12] http://andrewback.com/ivs.php

Luận văn Thạc sĩ Khoa học máy tính: Một số kỹ thuật trích chọn đặc trưng chữ viết tay trong nhập điểm rèn luyện tự động

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

MAI QUỐC AN

MỘT SỐ KỸ THUẬT TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY TRONG NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

MAI QUỐC AN

MỘT SỐ KỸ THUẬT TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY TRONG NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG

LỜI CẢM ƠN

PHẦN KẾT LUẬN ............................................................................................. 58 TÀI LIỆU THAM KHẢO ................................................................................. 60

PHẦN MỞ ĐẦU

Chương 1: KHÁI QUÁT VỀ NHẬP ĐIỂM RÈN LUYỆN TỰ ĐỘNG VÀ

1.2.3. Đặc trung kết cấu

Điểm hấp dẫn (Interest Point (Keypoint)): Là vị trí (điểm ảnh) "hấp dẫn" trên

Chương 2: NHẬN DẠNG PHIẾU ĐIỂM SỬ DỤNG MẠNG NƠ RON

2.2. Các kỹ thuật trích chọn đặc trưng

2.2.3. Kỹ thuật sử dụng mạng Neural nhân chập (Convolution neural network)

Bước 3: Tính vector đầu ra o của mạng

2.4.3. Nhận dạng hệ thống sử dụng mạng nơron

Chương 3: CHƯƠNG TRÌNH THỬ NGHIỆM

Mẫu phiếu điểm tổng kết: Phiếu điểm tổng kết gồm các cột thông tin: số thứ tự,

3.3. Tiền xử lý

3.5. Huấn luyện và nhận dạng

TÀI LIỆU THAM KHẢO

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok