Tài liệu Mạng nơ ron nhân tạo trong nhận dạng văn bản và ứng dụng vào hệ thống nhận dạng chữ việt in

MỤC LỤC MỞ ĐẦU CHƢƠNG I 6 TỔNG QUAN VỀ MẠNG NƠ -RON NHÂN TẠO VÀ HỆ 8 THỐNG NHẬN DẠNG VĂN BẢN 1.1. Giới thiệu về mạng nơ ron 1.1.1. Mô hình mạng nơ-ron nhân tạo 1.1.2. Ƣu và nhƣợc điểm của mạng nơ-ron 8 8 12 1.2. Phân loại mạng nơ ron 14 1.3. Hệ thống nhận dạng văn bản 17 1.3.1. Các hoạt động tiền xử lý 20 1.3.2. Phân tích trang văn bản 22 1.3.3. Trích chọn đặc trƣng 27 1.3.4. Học và nhận dạng 33 1.3.5. Hậu xử lý 34 CHƢƠNG II MỘT SỐ MÔ HÌNH MẠNG NƠ RON PHỔ BIẾN TRONG 36 HỆ THỐNG PHÂN TÍCH VÀ NHẬN DẠNG VĂN BẢN 2.1. Mạng Hamming 36 2.2. Mạng Kết hợp tuyến tính 40 2.3. Mạng Adaline 45 2.4. Mạng SOM 48 2.5. Mạng Multilayer Perceptron 56 2.6. Mạng RBF 65 CHƢƠNG III. XÂY DỰNG MỘT HỆ THỐNG NHẬN DẠNG CHỮ VIỆT 70 IN SỬ DỤNG MẠNG NƠ RON 3.1. Tập ký tự tiếng Việt 70 3.2. Hệ thống nhận dạng 70 3.2.1. Tiền xử lý 73 3.2.2. Học và nhận dạng 84 3.2.3. Hậu xử lý 85 3.3. Kết quả đạt đƣợc 85 3.3.1. Kết quả nhận dạng các ký tự riêng lẻ 86 3.3.2. Kết quả nhận dạng văn bản 86 KẾT LUẬN 89 TÀI LIỆU THAM KHẢO 92 MỞ ĐẦU Mạng nơ ron nhân tạo ngày nay đang là một lĩnh vực nghiên cứu nóng hổi, thu hút sự quan tâm đặc biệt của các nhà khoa học trong nhiều lĩnh vực. Đó là nhờ những thành công rực rỡ cả về mặt lý thuyết và ứng dụng của nó. Phạm vi áp dụng của mạng nơ ron rất rộng lớn: trong lĩnh vực xử lý, điều khiển nhƣ xử lý tín hiệu, khử nhiễu, phân lớp, nhận dạng, dự báo. Ngoài ra mạng nơ ron còn đƣợc ứng dụng trong các lĩnh vực toán học, y học, kinh doanh, tài chính, nghệ thuật. Mạng nơ ron đang ngày càng trở thành một hƣớng nghiên cứu, một giải pháp ngày càng hứa hẹn. Một trong những ứng dụng quan trọng của mạng nơ ron là nhận dạng và phân loại mẫu. Khả năng học và thích ứng của chúng đã làm cho chúng là lựa chọn hàng đầu đối với nhiệm vụ so sánh các tập dữ liệu hoặc trích chọn các mẫu thích hợp từ các dữ liệu phức hợp. Nhận dạng mẫu trong mạng nơ ron là một lĩnh vực rất rộng, nhƣng phổ biến nhất vẫn là nhận dạng chữ in và chữ viết tay. Nhận dạng văn bản là một bài toán đã đƣợc nghiên cứu từ lâu. Trên thế giới đã có khá nhiều phần mềm nổi tiếng về nhận dạng chữ la tin nhƣ OMNIPAGE của hãng Caere Corporation - Mỹ, RECOGNITA của Recognita Corporation - Hunggary, CURNEIFORM của Cognitive Technology Corporation - Mỹ, TexBridge Pro 96 của Xerox Corporation, IMAG-IN 4.0 – Pháp. Ở Việt nam có phần mềm nhận dạng chữ Việt in của Viện công nghệ thông tin. Nhận dạng văn bản là một bài toán khá phức tạp đòi hỏi nhiều nghiên cứu sâu sắc cả về xử lý ảnh và về kỹ thuật nhận dạng. Giải quyết bài toán này sẽ giúp tự động hoá rất nhiều công việc nhàm chán phải đánh lại văn bản khi ta chỉ có văn bản hoặc ảnh văn bản và cần chuyển những thông tin đó sang dạng text -6- để hiệu chỉnh lại hoặc tự động nhập liệu vào các hệ thống cơ sở dữ liệu, giảm thời gian và chi phí. Ngày nay với sự bùng nổ của internet và việc xây dựng các thƣ viện điện tử thì nhu cầu nhận dạng văn bản trong sách báo càng trở nên cực kỳ cần thiết. Nhận thấy khả năng mạnh mẽ của mạng nơ ron rất thích hợp với bài toán nhận dạng, kết hợp với nhu cầu thực tế về nhận dạng văn bản và có sự gợi ý định hƣớng của PGS .TS Đặng Quang Á, chúng tôi đã nghiên cứu đề tài "Mạng nơ ron nhân tạo trong nhận dạng văn bản và ứng dụng vào hệ thống nhận dạng chữ Việt in". Luận văn này không đi sâu nghiên cứu các kỹ thuật xử lý ảnh văn bản cụ thể mà tập trung vào khả năng ứng dụng mạng nơ ron trong hệ thống nhận dạng văn bản nói chung và xây dựng một hệ thống nhận dạng chữ Việt in để minh họa. Nội dung cơ bản của luận văn gồm có ba chƣơng: Chƣơng một trình bày tổng quan về mạng nơ ron nhân tạo, bao gồm: giới thiệu về mạng nơ ron, phân loại mạng nơ ron và tổng quan về hệ thống nhận dạng ký tự. Chƣơng hai trình bày về một số mạng nơ ron phổ biến trong hệ thống nhận dạng văn bản chữ in nhƣ mạng Hamming, mạng kết hợp tuyến tính, mạng Adaline, mạng SOM, mạng RBF, mạng Multilayer Perceptron. Chƣơng ba trình bày về hệ thống nhận dạng chữ Việt in sử dụng mạng nơ ron. -7- CHƢƠNG I TỔNG QUAN VỀ MẠNG NƠ RON NHÂN TẠO VÀ HỆ THỐNG NHẬN DẠNG KÝ TỰ 1.1. Giới thiệu về mạng nơ-ron Mạng nơ-ron nhân tạo đƣợc xây dựng từ những năm 1940, nhằm mô phỏng một số chức năng bộ não của con ngƣời. Nếu nhìn não từ góc độ tính toán, chúng ta dễ thấy rằng cách thức tính toán của não khác xa với tính toán theo thuật toán và chƣơng trình truyền thống. Sự khác biệt thể hiện ở hai điểm: + Quá trình tính toán đƣợc tiến hành song song và phân tán trên nhiều nơ ron gần nhƣ đồng thời + Tính toán thực chất là quá trình học chứ không phải theo một sơ đồ định sẵn từ trƣớc. Mạng nơ-ron nhân tạo đƣợc thiết kế tƣơng tự nhƣ nơ-ron sinh học, sẽ có khả năng giải quyết hàng loạt các bài toán mà sự suy luận tƣơng đối “mờ”, không đầy đủ dữ liệu, cần có quá trình “học” từ các ví dụ. 1.1.1. Mô hình mạng nơ-ron nhân tạo 1.1.1.1. Nơ-ron sinh học Bộ não ngƣời có khoảng 1011 tế bào thần kinh kết nối với mật độ cao gọi là các nơ-ron (một nơ ron có khoảng 104 liên kết). Có nhiều loại nơ-ron khác nhau về kích thƣớc và khả năng thu phát tín hiệu. Tuy nhiên, chúng có cấu trúc và nguyên lý hoạt động chung. Hình 1.1 là một ví dụ đơn giản hoá về một nơron. Mỗi nơ-ron gồm có ba phần: Thân nơ-ron (cell body) với nhân ở bên trong (soma), một trục dây thần kinh ra (axon) và một hệ thống lƣới cảm ứng hình cây (dendrites). Các xúc tu hay lƣới cảm ứng, là các dây thần kinh vào để nhận các -8- tín hiệu từ các nơ-ron khác. Thân nơ ron làm nhiệm vụ tổng hợp tín hiệu vào và biến đổi thành tín hiệu ra. Tín hiệu ra đƣợc chuyển đến trục dây thần kinh ra. Dây thần kinh trục phân thành nhiều nhánh ở cuối nhằm chuyển giao tín hiệu tới các nơ-ron khác. Điểm kết nối giữa trục của một nơ ron với xúc tu của một nơ ron khác gọi là khớp (synapse). Các nơ-ron có thể thay đổi mức tín hiệu tại các khớp. Trong nơ-ron nhân tạo, mức tín hiệu này thể hiện bằng trọng số. Hình 1.1. Mô hình nơ ron sinh học 1.1.1.2. Nơ-ron nhân tạo  Trọng số và tổng tín hiệu đầu vào: Trọng số mô phỏng chức năng của khớp nối giữa hai nơ ron (synapse). Mỗi nơ-ron sinh học có rất nhiều dây thần kinh vào, nghĩa là nó có thể tiếp nhận đồng thời nhiều tín hiệu. Tƣơng tự, mỗi nơ ron nhân tạo có thể có nhiều trọng số. Giả sử tại nơ-ron i có N tín hiệu vào, mỗi tín hiệu vào pj đƣợc gán một trọng số wij tƣơng ứng, tổng tín hiệu đi vào nơ ron ni có thể đƣợc ƣớc lƣợng theo một số dạng sau: (i) Dạng tuyến tính: N n i   w ijp j j1 (ii) Dạng toàn phƣơng: -9- (1.1) N n i   w ijp j2 (1.2) n i  ρ 2  p j - w ij 2 (1.3) j1 (iii) Dạng mặt cầu: N j1 Trong đó ρ và wij (j = 1->N) lần lƣợt là bán kính và tâm cầu.  Hàm kích hoạt: Hàm biến đổi tín hiệu đầu vào n thành tín hiệu đầu ra a đƣợc gọi là hàm kích hoạt (activation function hay transfer function). Hàm này mô phỏng chức năng của thân nơ ron. Ngƣời thiết kế mạng sẽ chọn một hàm cụ thể để đáp ứng yêu cầu của bài toán.  Nút Bias (hay offset): Là một nút bổ trợ nhằm tăng khả năng thích ứng của mạng nơ ron trong quá trình học. Bias gần giống nhƣ trọng số, trừ một điều là nó luôn có tín hiệu vào không đổi bằng 1. Nút này có thể bỏ đi nếu không cần thiết. Các trọng số và bias là các tham số có thể điều chỉnh của nơ ron. Một luật học sẽ điều chỉnh chúng sao cho quan hệ đầu vào/đầu ra của nơ ron đáp ứng đƣợc một mục tiêu nào đó. - 10 - Hình 1.2. Một số hàm kích hoạt phổ biến  Mô hình của một nút xử lý (nút thứ i): Hình 1.3. Mô hình một nơ ron - 11 - N n i   w ijp j  bi (1.7) a i  f i n i  (1.8) j1 Trong đó: ni: tổng tín hiệu vào tại nơ ron i ai: tín hiệu ra tại nơ ron i  Mạng nơ ron Tƣơng tự nhƣ các nơ ron sinh học phải liên kết với nhau một cách có tổ chức thì mới tạo nên sức mạnh, các nơ ron nhân tạo cũng phải liên kết với nhau thành mạng lƣới thì mới có khả năng giải quyết các bài toán thực tế. Tuy nhiên ngƣời ta đã chứng minh rằng không phải cứ liên kết tuỳ ý các nơ ron bất kỳ là đƣợc mà các liên kết phải có trật tự. Thông thƣờng các nơ ron nhân tạo liên kết với nhau thành từng tầng, tầng sau liên kết với đầu ra của tầng trƣớc. Các tín hiệu lan truyền từ tầng đầu tiên, đến tầng thứ hai, thứ ba và cuối cùng đến tầng ra. Các tín hiệu cũng có thể lan truyền hồi quy từ một tầng đến tầng trƣớc nó. tầng vào tầng ẩn tầng ra p1 p2 ... ... ... ... pn 1.1.2. Ƣu và nhƣợc điểm của mạng nơ-ron Hình 1.4. Mạng truyền thẳng nhiều tầng Đặc điểm nổi bật của mạng nơ ron là khả năng thích ứng của nó, mang lại một cách thiết kế hệ thống hoàn toàn mới. Thay vì xây dựng một hệ thống từ các (ii) ( - 12 - bản thiết kế khuôn mẫu, mạng nơ ron sử dụng dữ liệu bên ngoài để tự động xác định giá trị các tham số. Điều này nghĩa là mạng “nhận biết” đƣợc đầu ra của nó thông qua một cơ chế phản hồi có tính đến hàm chi phí. Cơ chế phản hồi này sẽ thay đổi các tham số thông qua một quá trình gọi là học hay huấn luyện. Nhờ đó mà đầu ra của hệ thống đƣợc điều chỉnh gần với đích mong muốn nhất. Hình 1.5. Mô hình huấn luyện mạng nơ ron Ưu điểm: - Xử lý song song. - Thiết kế hệ thống thích nghi. - Không đòi hỏi các đặc trƣng mở rộng của bài toán (chủ yếu dựa trên tập huấn luyện). Nhược điểm: - Không có các quy tắc và các hƣớng dẫn thiết kế một cách rõ ràng đối với một ứng dụng nhất định. - Không có cách tổng quát để đánh giá hoạt động bên trong mạng. - Việc học đối với mạng có thể khó thực hiện. - Khó có thể dự đoán trƣớc đƣợc hiệu quả của mạng trong tƣơng lai (khả năng tổng quát hoá). - 13 - 1.2. Phân loại mạng nơ ron Mạng nơ ron không cần phải đƣợc lập trình lại khi chạy trong môi trƣờng mới. Sở dĩ có điều này bởi vì cách ứng xử của nó thay đổi để thích ứng với môi trƣờng mới. Sự thay đổi này có đƣợc nhờ thay đổi các trọng số (weight). Ta gọi quá trình thay đổi trọng số này là học (learning).  Nếu phân loại mạng nơ ron theo mô hình học (learning paradigm) thì có ba loại chính: - Học có giám sát (Supervised learning): chúng ta cung cấp cho mạng dữ liệu vào (input data) và câu trả lời đúng, tức là đầu ra mà ta mong muốn nhận đƣợc ứng với đầu vào. Dữ liệu vào đƣợc truyền thẳng qua mạng cho đến tầng ra. Đầu ra thực tế của mạng đƣợc so sánh với đầu ra mong muốn. Nếu chúng giống nhau thì ta không thay đổi các trọng số của mạng. Nếu khác nhau, ta điều chỉnh trọng số để đảm bảo mạng sẽ đƣa ra câu trả lời chính xác hơn nếu nó gặp lại dữ liệu vào đó. - Học không giám sát (Unsupervised learning): ta chỉ cung cấp cho mạng dữ liệu vào mà không có đầu ra mong muốn. Mạng này cần phải tự tổ chức hay tự dạy chính nó. Kết quả học phụ thuộc vào cấu trúc dữ liệu vào. - Học tăng cƣờng (Reinforcement learning): là loại lai giữa hai loại trên. Ta cung cấp cho mạng dữ liệu vào và chỉ cho mạng biết là câu trả lời đúng hay sai. Nếu câu trả lời sai, ta điều chỉnh trọng số sao cho có thể nhận đƣợc câu trả lời đúng khi nhận đƣợc dữ liệu đó trong tƣơng lai.  Nếu phân loại mạng nơ ron theo kiến trúc mạng thì có hai loại chính: - Mạng truyền thẳng (Feed forward network): các tín hiệu truyền từ tầng vào thẳng qua các tầng tiếp theo rồi đến tầng ra. - Mạng hồi quy (Recurrent network): các tín hiệu sau khi đến tầng ra rồi lại truyền ngƣợc trở lại làm tín hiệu vào để phản hồi.  Nếu phân loại mạng nơ ron theo kết nối mạng thì có hai loại chính: - 14 - - Mạng đơn tầng: chỉ có một tầng ngoài tầng vào. - Mạng đa tầng: có hơn một tầng ngoài tầng vào.  Nếu phân loại mạng nơ ron theo giải thuật học thì có nhiều loại: - Học lan truyền ngƣợc (back propagation) - Học cạnh tranh - Học LVQ - Học Hebb - 15 - Hình 1.6. Phân loại các mô hình mạng nơ ron - 16 - Mạng nơ ron nhân tạo là một kiến trúc tính toán mạnh mẽ vì nó gồm một số lớn nơ ron liên kết song song và thích ứng với nhau. Vì vậy mạng nơ ron đƣợc sử dụng rất phổ biến trong lĩnh vực nhận dạng nói chung và nhận dạng văn bản nói riêng. Điển hình là mạng MLP của R. Rosenblatt và sau đó là Minsky và Papert chi tiết hóa, đã đƣợc ứng dụng rất rộng rãi trong cả nhận dạng chữ viết tay và chữ in, ví dụ nhƣ mạng nơ ron của Hussain và Kabuka, mạng Neocognitron của Fukushima. Mạng hai tầng truyền thẳng của Garland có thể nhận dạng 94 ký tự chữ in. Khả năng của mạng đã đƣợc kiểm tra bởi 300000 ký tự in bằng máy in laser, với 12 loại font phổ biến có kích thƣớc khác nhau. Kết quả là nhận dạng không có lỗi nào [30]! Sau đây chúng ta nghiên cứu chi tiết về hệ thống nhận dạng văn bản. 1.3. Hệ thống nhận dạng văn bản Nhận dạng văn bản (character recognition - CR) là một thuật ngữ tổng quát bao gồm tất cả các loại nhận dạng ký tự bằng máy trong các lĩnh vực khác nhau. Có thể phân loại hệ thống nhận dạng theo hai tiêu thức chính sau: o Căn cứ vào phƣơng pháp lấy mẫu văn bản (data acquisition process): online hay off-line. o Căn cứ vào loại văn bản (text type): chữ in (machine-printed) hay chữ viết tay (hand-written). On-line character recognition là quá trình nhận dạng chữ viết tay mà tín hiệu vào đƣợc thu nhận bằng các bộ số hóa (digitizer) theo một thứ tự thời gian của tọa độ bút. Các bộ số hóa thƣờng là các bảng điện tử. Chúng gửi tọa độ đầu ngòi bút vào máy tính sau mỗi khoảng thời gian. Trong off-line character recognition hay Optical Character Recognition (OCR), hình ảnh chữ viết đƣợc chuyển thành các mẫu bit bằng các thiết bị số hóa quang học nhƣ máy quét hay máy ảnh. Việc nhận dạng đƣợc tiến hành trên - 17 - các mẫu bit này, có thể là chữ in hay chữ viết tay. So với nhận dạng on-line thì nhận dạng off-line có nhiều khó khăn hơn. Không phụ thuộc văn bản thuộc loại nào, nói chung có năm giai đoạn chính sau trong quá trình nhận dạng văn bản: 1. Tiền xử lý (Preprocessing) 2. Phân tích trang văn bản (Segmentation hay Layout Analysis) 3. Trích chọn đặc trƣng (Feature Extraction hay Representation) 4. Học và nhận dạng (Training and Recognition) 5. Hậu xử lý (Post Processing) - 18 - Hình 1.7. Sơ đồ hệ thống nhận dạng văn bản tổng quát - 19 - 1.3.1. Các hoạt động tiền xử lý Tiền xử lý thực hiện biến đổi từ ảnh sang ảnh nhằm nâng cao chất lƣợng ảnh, làm cho việc nhận dạng dễ dàng và chính xác hơn. Nó làm nổi bật và làm sắc nét các đặc điểm của ảnh nhƣ các cạnh, biên, độ tƣơng phản. Hai mục tiêu chính của tiền xử lý là: o Khử nhiễu o Chuẩn hóa dữ liệu 1.3.1.1. Khử nhiễu  Lọc (Filtering): tích chập một mặt nạ xác định trƣớc với ảnh: giá trị của một điểm ảnh là một hàm của các điểm ảnh lân cận. Bộ lọc có thể dùng để làm mịn (smoothing), làm sắc nét (sharpening), phân ngƣỡng (thresholding), loại bỏ những cấu trúc yếu hay màu nền và điều chỉnh độ tƣơng phản.  Các phép toán hình thái (Morphological Operation): làm cho một đối tƣợng trong ảnh to hơn hay nhỏ hơn. Các phép toán này cần có một lõi (kernel hay structuring element). Kích thƣớc (số dòng và số cột) của toàn bộ ảnh không thay đổi. Các phép toán hình thái cơ bản là dilate (mở rộng đối tƣợng) hay erode (thu hẹp đối tƣợng). Các phép toán hình thái nối các nét đứt, tách các nét liền, làm mịn đƣờng biên, xoá các điểm nhiễu, làm mảnh ký tự và trích xuất biên. Vì vậy các phép toán hình thái đƣợc sử dụng rất thành công trong việc xóa nhiễu. Ví dụ về phép toán dilate: 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 ảnh gốc structuring element - 20 - ảnh kết quả 1.3.1.2. Chuẩn hóa dữ liệu Chuẩn hóa dữ liệu nhằm loại bỏ những biến động trong văn bản và nhận đƣợc dữ liệu chuẩn hóa. Chuẩn hoá dữ liệu thực hiện một số công việc sau:  Hiệu chỉnh góc nghiêng văn bản (skew normalization) Do sự không chính xác trong quá trình quét hay kiểu viết, văn bản có thể bị nghiêng hay cong, do đó ảnh hƣởng đến chất lƣợng nhận dạng. Hơn nữa, một số ký tự chỉ có thể phân biệt với nhau căn cứ vị trí của chúng đối với đƣờng thẳng đáy. Có một số phƣơng pháp xác định góc nghiêng văn bản: projection profile, nearest neighbors clustering, cross correlation method between lines, Hough Transform, Attractive Repulsive Neural Network.  Hiệu chỉnh ký tự nghiêng (slant normalization) Chữ nghiêng thể hiện bằng góc giữa nét dài nhất trong một từ và trục đứng. Chuẩn hoá chữ nghiêng nhằm đƣa tất cả các ký tự về một dạng thống nhất. Phƣơng pháp phổ biến nhất là tính góc trung bình của các nét gần thẳng đứng nhất. Một cách khác là tính projection profiles các góc so với trục thẳng đứng.  Hiệu chỉnh kích thƣớc chữ (size normalization) Là việc đƣa tất cả các ký tự về cùng một cỡ chữ. Có thể sử dụng phép hiệu chỉnh kích thƣớc theo chiều dọc và chiều ngang.  Phân ngƣỡng (thresholding) Để nhận dạng văn bản thì bộ nhận dạng chỉ quan tâm đến màu nền và màu chữ của ảnh. Phân ngƣỡng chuyển ảnh đa cấp xám hay ảnh màu thành ảnh đen trắng (binary) nhằm làm cho việc nhận dạng đƣợc dễ dàng, không bị ảnh hƣởng bởi mức độ xám của điểm ảnh. Phân ngƣỡng còn làm giảm bộ nhớ cần để lƣu trữ ảnh và tăng tốc độ xử lý. Có hai loại ngƣỡng: tổng thể (global) và cục bộ (local). Phân ngƣỡng tổng thể tìm một ngƣỡng cho toàn bộ ảnh văn bản, thƣờng - 21 - dựa trên ƣớc lƣợng giá trị màu nền từ biểu đồ tần suất cƣờng độ sáng của ảnh. Phân ngƣỡng cục bộ sử dụng các giá trị khác nhau cho mỗi điểm ảnh dựa trên thông tin cục bộ của các điểm ảnh lân cận nó.  Làm mảnh (thinning) Làm mảnh làm giảm kích thƣớc của ảnh, đồng thời trích chọn thông tin về hình dạng của ký tự. Có hai cách tiếp cận chính: dựa vào điểm ảnh (pixel wise) và không dựa vào điểm ảnh (non-pixel wise). Pixel wise xử lý cục bộ và tuần tự ảnh cho đến khi xƣơng của ký tự chỉ còn lại một điểm. Phƣơng pháp này rất nhạy cảm với nhiễu và dễ làm biến dạng ký tự. Non-pixel wise sử dụng thông tin tổng thể về ký tự trong khi làm mảnh. Nó trực tiếp tìm điểm trung vị hay đƣờng thẳng giữa của ký tự mà không xem xét tất cả các điểm ảnh riêng lẻ. Có thể sử dụng phƣơng pháp làm mảnh dựa trên phân cụm: xƣơng của ký tự chính là các tâm cụm. Có thể làm mảnh dựa trên các điểm mút, điểm giao, điểm uốn. 1.3.2. Phân tích trang văn bản Phân tích trang văn bản (Segmentation hay Page Layout Analysis) là chia nhỏ ảnh văn bản thành các thành phần nhỏ hơn có cùng cấu trúc. Đây là một giai đoạn rất quan trọng vì tách đƣợc ở mức độ dòng, từ hay ký tự trực tiếp quyết định mức độ nhận dạng ký tự. Kết quả phép tách đúng hay sai quyết định kết quả nhận dạng. Có hai loại phân tích văn bản:  External Segmentation: là việc tìm ra các thành phần ký tự khác nhau nhƣ đoạn, câu hay từ, văn bản hay phi văn bản.  Internal Segmentation: là việc tìm ra các ký tự riêng lẻ. Việc này đặc biệt khó trong chữ viết tay thảo. 1.3.2.1. External Segmentation External Segmentation là việc phân chia cấu trúc của trang thành các đơn vị lô gíc (các vùng có cùng cấu trúc). Đây là khâu trọng yếu của phân tích cấu - 22 - trúc văn bản (document layout analysis) nhằm cung cấp cho bộ nhận dạng các vùng có cấu trúc giống nhau và phục hồi văn bản sau khi nhận dạng về định dạng ban đầu. External Segmentation gồm hai giai đoạn: giai đoạn một là phân tích cấu trúc (structural analysis): tách ảnh văn bản thành các thành phần (đoạn, dòng, từ). Giai đoạn hai là phân tích chức năng (functional analysis): sử dụng vị trí, kích thƣớc, các luật về trình bày để gán nhãn chức năng cho các thành phần (tiêu đề, tóm tắt, …). Có hai cách tiếp cận để thực hiện External Segmentation:  Cách tiếp cận từ trên xuống (top-down): tách một trang thành các thành phần nhỏ hơn bằng các phép cắt theo X và theo Y, bắt đầu từ các thành phần lớn cho đến các thành phần nhỏ hơn, cuối cùng đạt đƣợc ký tự riêng lẻ. Tiếp cận theo hƣớng này có các phƣơng pháp: sử dụng phép chiếu nghiêng, phân tích khoảng trống trắng. Ƣu điểm lớn nhất của phƣơng pháp phân tích từ trên xuống là nó dùng cấu trúc toàn bộ trang để giúp cho phân tích định dạng đƣợc nhanh chóng. Đây là cách tiếp cận hiệu quả cho hầu hết các dạng trang. Tuy nhiên, với các trang không có các biên tuyến tính và có sơ đồ lẫn cả bên trong và quanh văn bản, các phƣơng pháp này có thể không thích hợp. Ví dụ, nhiều tạp chí tạo văn bản quanh một sơ đồ ở giữa, vì thế văn bản đi theo những đƣờng cong của đối tƣợng trong sơ đồ chứ không đi theo đƣờng thẳng.  Cách tiếp cận từ dƣới lên (bottom-up): xây dựng đệ qui các vùng đồng nhất từ các thành phần nhỏ hơn, tới khi mọi khối trên trang đƣợc xác định, dựa trên phép xử lý các điểm ảnh và các thành phần liên thông. Ví dụ nhƣ phƣơng pháp Docstrum sử dụng phƣơng pháp phân cụm k-nearest neighbor. Tuy nhiên không có một phƣơng pháp nào điển hình cho mọi kỹ thuật phân tích dƣới lên. Ngoài ra, một số kỹ thuật khác kết hợp cả hai cách tiếp cận topdown và bottom-up. - 23 -