ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM PHI HIỆU XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÀ DỊCH TRÊN THIẾT BỊ DI ĐỘNG LUẬN VĂN THẠC SỸ Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM PHI HIỆU XÂY DỰNG HỆ THỐNG NHẬN DẠNG VÀ DỊCH TRÊN THIẾT BỊ DI ĐỘNG Ngành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 60 48 10 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS KIỀU VĂN HƯNG Hà Nội - 2011 1 MỤC LỤC DANH MỤC HÌNH VẼ ....................................................................................................... 3 MỞ ĐẦU .............................................................................................................................. 5 CHƢƠNG 1 – TỔNG QUAN VỀ OCR............................................................................... 8 1.1. Giới thiệu về OCR ................................................................................................ 8 1.1.1. OCR là gì........................................................................................................ 8 1.1.2. Một số công nghệ, phần mềm OCR tiêu biểu ................................................ 10 1.1.3. Một số khái niệm cơ bản ............................................................................... 11 1.2. Các bƣớc cơ bản trong một hệ thống OCR ....................................................... 13 1.2.1. Thu nhận ảnh ................................................................................................ 13 1.2.2. Tiền xử lý ảnh ............................................................................................... 14 1.2.2.1. Nhị phân hóa ảnh .................................................................................. 14 1.2.2.2. Chỉnh độ nghiêng và hướng................................................................... 16 1.2.2.3. Giảm nhiễu ........................................................................................... 17 1.2.3. Phân tích bố cục ............................................................................................ 18 1.2.4. Tách dòng và từ ............................................................................................ 19 1.2.5. Huấn luyện và nhận dạng .............................................................................. 20 1.2.6. Xử lý kết quả ................................................................................................ 21 CHƢƠNG 2 – CÁC CÔNG NGHỆ SỬ DỤNG TRONG HỆ THỐNG............................ 22 2.1. Công nghệ Tesseract OCR ................................................................................. 22 2.1.1. Giới thiệu về Tesseract OCR ......................................................................... 22 2.1.2. Tesseract làm việc như thế nào? .................................................................... 24 2.1.3. Vấn đề tập huấn ngôn ngữ ............................................................................. 26 2.2. Công nghệ Android ................................................................................................. 29 2.2.1. Giới thiệu về hệ điều hành android ................................................................ 29 2.2.2. Kiến trúc hệ thống......................................................................................... 30 2.3. Mô hình client/server .......................................................................................... 33 2.3.1. Giới thiệu về mô hình client/server ............................................................... 33 2.3.2. Các kiến trúc client/server ............................................................................. 34 2.3.2.1. Client/Server hai tầng ............................................................................ 34 2.3.2.2. Client/server ba tầng.............................................................................. 35 2.3.2.3. Client/server n-tầng ............................................................................... 36 2.4. Công nghệ dịch thuật Google Translate ............................................................ 36 2.4.1. Xử lý ngôn ngữ tự nhiên ............................................................................... 36 2.4.2. Dịch tự động ................................................................................................. 37 2.4.3. Dịch vụ dịch thuật trực tuyến Google Translate............................................. 40 CHƢƠNG 3 – HỆ THỐNG NHẬN DẠNG VÀ DỊCH TRÊN THIẾT BỊ DI ĐỘNG ..... 42 3.1. Sơ đồ tổng quát của hệ thống ............................................................................. 42 3.2. Ứng dụng trên client ........................................................................................... 43 3.2.1. Chức năng..................................................................................................... 43 3.2.2. Giao diện ...................................................................................................... 43 3.3. Ứng dụng trên server ......................................................................................... 47 3.3.1. Chức năng tiền xử lý ảnh .............................................................................. 48 3.3.2. Chức năng OCR ............................................................................................ 50 3.3.3. Chức năng hậu xử lý kết quả OCR ................................................................ 52 3.3.4. Chức năng sửa lỗi chính tả tự động ............................................................... 52 3.3.4.1. Hàm đánh giá minimum edit distance (MED) ........................................ 53 3.3.4.2. Hàm đánh giá maximum số cặp ký tự giống nhau .................................. 53 3.3.5. Chức năng dịch sang ngôn ngữ khác ............................................................. 54 CHƢƠNG 4 – THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................................................ 55 2 4.1. Thực nghiệm trên Tesseract engine ................................................................... 55 4.1.1. Tập mẫu thực nghiệm ................................................................................... 55 4.1.2. Kết quả OCR ................................................................................................ 55 4.1.3. Nhận xét ....................................................................................................... 56 4.2. Thực nghiệm trên một số hệ thống OCR khác nhau ......................................... 57 4.2.1. Tập mẫu thực nghiệm ................................................................................... 58 4.2.2. Kết quả ......................................................................................................... 58 4.2.3. Nhận xét ....................................................................................................... 58 KẾT LUẬN ........................................................................................................................ 59 TÀI LIỆU THAM KHẢO ................................................................................................. 61 3 DANH MỤC HÌNH VẼ Hình 1.1: Ứng dụng OCR .............................................................................8 Hình 1.2: Các đường cơ bản trong dòng text ...............................................12 Hình 1.3: Thành phần liên thông 4 và 8 ......................................................13 Hình 1.4: Quy trình cơ bản trong một hệ thống OCR ..................................13 Hình 1.5. Mô tả lược đồ mức xám ..............................................................15 Hình 1.6. Phân ngưỡng trên lược đồ mức xám ............................................15 Hình 1.7. Kết quả chọn ngưỡng xám theo phương pháp Otsu .....................16 Hình 1.8. Ảnh văn bản trước và sau khi chỉnh nghiêng ...............................16 Hình 1.9. Ảnh văn bản trước và sau khi chỉnh hướng đúng .........................17 Hình 1.10. Các vùng nhiễu trên ảnh văn bản ...............................................17 Hình 1.11. b-Cấu trúc vật lý; c,d-Cấu trúc lôgic ..........................................19 Hình 2.1. Kiến trúc Tesseract ......................................................................24 Hình 2.2. Ảnh trước và sau phân tích bố cục ...............................................24 Hình 2.3. Fitting cap line, mean line, baseline, descent line .......................25 Hình 2.4. Ví dụ bổ fixed pitch thành các ký tự ............................................25 Hình 2.5. Sự khác nhau trong khoảng các từ ...............................................25 Hình 2.6. Các thành viên của "Liên minh di động mở" ...............................29 Hình 2.7. Kiến trúc Android OS .................................................................30 Hình 2.8. Mô hình client/server ..................................................................33 Hình 2.9. Mô hình kiến trúc client/server 2 tầng .........................................35 Hình 2.10. Mô hình kiến trúc client/server 3 tầng .......................................35 Hình 2.11. Dịch vụ dịch thuật online Google translate ................................40 Hình 2.12. Các ngôn ngữ Google Translate hỗ trợ dịch ..............................40 Hình 3.1. Sơ đồ hệ thống nhận dạng và dịch trên thiết bị di động ...............42 Hình 3.2. Giao diện chính chương trình client ............................................43 4 Hình 3.3. Giao diện tab image ....................................................................44 Hình 3.4. Ảnh chụp ở chế độ chụp “full mode” ..........................................44 Hình 3.5. Ảnh chụp ở chế độ chụp “block mode” .......................................45 Hình 3.6. Chương trình đang chờ xử lý .......................................................45 Hình 3.7. Giao diện thiếp lập tùy chọn ........................................................45 Hình 3.8. Giao diện tab OCR Result ...........................................................46 Hình 3.9. Giao diện tạo liên hệ mới ............................................................46 Hình 3.10. Giao diện gửi SMS ....................................................................47 Hình 3.11. Giao diện tìm kiếm và hiển thị thông tin....................................47 Hình 3.12. Ảnh có bố cục và phân bố màu sắc phức tạp .............................48 Hình 3.13. Ảnh gốc sau khi nhị phân hóa và làm sạch ................................49 Hình 3.14. Các ảnh con cắt ra từ ảnh gốc ....................................................50 Hình 3.15. Kết quả OCR trên ảnh gốc .........................................................50 Hình 3.16. Kết quả OCR trên các ảnh con ..................................................50 Hình 3.17. Định nghĩa hàm OcrFromImage() .............................................51 Hình 4.1. Kết quả thực nghiệm OCR với Tesseract engine ........................55 Hình 4.2. Kết quả thực nghiệm OCR trên 4 hệ thống khác nhau ................58 5 MỞ ĐẦU Đặt vấn đề Từ lâu con người đã quen với việc sử dụng máy tính để lưu trữ những tài liệu cần thiết, xuất phát từ những tiện ích to lớn do máy tính mang lại: lưu trữ khối dữ liệu lớn, ít bị hư hỏng, dễ quản lí, dễ tìm kiếm, dễ chỉnh sửa... Tuy nhiên giấy vẫn là một vật liệu quan trọng đã, đang và sẽ được sử dụng để lưu trữ tài liệu vì sự cần thiết của nó trong cuộc sống hàng ngày (ví dụ sách, báo...). Một nhu cầu tất yếu, con người muốn đưa các tài liệu đang lưu trữ trên giấy (cũng như trên một số vật liệu khác) lên máy tính để có thể làm việc với chúng một hiệu quả hơn. Một cách thông thường, con người sẽ đánh máy trực tiếp các tài liệu đó lên máy tính. Đối với một số lượng nhỏ tài liệu, việc này hoàn toàn bình thường. Song đối với một khối lượng tài liệu khổng lồ (ví dụ như cả kho sách), đây là một vấn đề nan giải; mặc dù với việc đánh máy độ chính xác rất cao nhưng lại tốn quá nhiều thời gian, trong khi với các công nghệ hiện có cho phép ta giải quyết vấn đề này: chụp ảnh tài liệu và nhận dạng ký tự trong ảnh. Nhận dạng ký tự quang học (tiếng Anh: Optical Character Recognition, viết tắt là OCR)[20] là quá trình rút trích ký tự trong ảnh cho ra dưới dạng văn bản để có thể lưu trữ, chỉnh sửa và tìm kiếm được. Lĩnh vực OCR là một nhánh trong ngành khoa học xử lý ảnh, tuy còn mới mẻ so với nhiều lĩnh vực khoa học khác nhưng nhanh chóng đã đạt được nhiều bước tiến quan trọng. Xuất phát từ nhu cầu thực tế là đưa các tài liệu lưu trữ trên giấy vào máy tính mà không phải đánh máy, nhiều công nghệ OCR ra đời (phát hành dưới dạng sản phẩm thương mại, miễn phí hoặc nguồn mở) đã và đang ứng dụng rộng rãi trong các lĩnh vực liên quan đến việc nhận dạng. Với sự đầu tư mạnh mẽ và nghiên cứu liên tục của các cá nhân tổ chức, kết quả nhận dạng trong lĩnh vực OCR ngày càng được cải thiện, đặc biệt sự nhận dạng ký tự Latinh đánh máy có thể tiến tới tỉ lệ chính xác 100%. Ngoài công nghệ nhận dạng ký tự quang học OCR thì hiện nay còn có thêm nhiều cơ chế nhận dạng tiêu biểu khác được ứng dụng vào thực tế như: nhận dạng ký tự thông minh (Intelligent Character Recognition, viết tắt ICR), nhận dạng vùng đánh dấu (Optical Mark Recognition, viết tắt OMR), nhận dạng chữ mực từ (Magnetic Ink Character Recognition, viết tắt MICR), nhận dạng mã vạch (Barcode Regconition). Chúng ta thường thực hiện công việc nhận dạng trực tiếp trên máy tính: dùng các thiết bị thu ảnh để scan, chụp ảnh các tài liệu và đưa các ảnh đó lên máy tính rồi chạy ứng dụng nhận dạng đã cài đặt. Điều này hầu như chỉ thực 6 hiện được khi chúng ta làm việc ở nhà, ở cơ quan với chiếc máy tính bên cạnh. Tuy nhiên nhu cầu OCR của chúng ta có thể xuất hiện mọi lúc mọi nơi, ví dụ muốn lưu nhanh thông tin trong một name card mà người bạn đưa cho vào điện thoại mà không phải nhập bằng tay. Song chúng ta không thể lúc nào cũng mang bên mình máy scan, máy ảnh cũng như máy tính để hỗ trợ cho việc OCR. Chưa kể đôi khi chúng ta muốn dịch nhanh một bảng chỉ dẫn bằng tiếng nước ngoài mà không có từ điển bên cạnh. Một khó khăn nữa là các ứng dụng OCR hiệu quả cho công việc của chúng ta lại đa phần được tung ra dưới dạng thương mại, muốn sử dụng phải mất một chi phí không nhỏ. Chính những sự bất tiện thực tế trên, vấn đề đặt ra là phải có những hệ thống phần cứng-phần mềm nhỏ gọn, di động nhưng vẫn thực hiện một cách linh hoạt và hiệu quả các chức năng chụp ảnh tài liệu, OCR trên ảnh đã chụp và dịch kết quả ra ngôn ngữ khác. Hiện nay công nghệ mạng internet phát triển mạnh mẽ, internet có mặt hầu hết khắp nơi trên thế giới. Công nghệ di động phát triển vượt bậc, việc sử dụng điện thoại bùng nổ, điện thoại di động trở thành mặt hàng bình dân mà ai cũng có thể sở hữu được. Nhiều công nghệ OCR tiên tiến được đưa ra dưới dạng mã nguồn mở và được các công ty, tổ chức lớn tài trợ phát triển. Với nền tảng công nghệ hiện có ở trên đã tạo ra nhiều giải pháp để xây dựng được nhiều hệ thống có khả năng đáp ứng cao với vấn đề đặt ra. Mục tiêu nghiên cứu Với mong muốn tìm hiểu về lĩnh vực và một số công nghệ OCR tiên tiến, đồng thời mong muốn góp phần vào kho ứng dụng OCR hiện có một sản phẩm nguồn mở mới: một hệ thống trên thiết bị di động giúp con người có thể thu ảnh, rút trích thông tin trong ảnh, dịch kết quả ra ngôn ngữ mong muốn và quản lý các thông tin ấy trên thiết bị di động. Thiết bị di động được chọn là điện thoại di động chạy hệ điều hành nguồn mở Android. Và từ đó luận văn lựa chọn đề tài nghiên cứu “Xây dựng hệ thống nhận dạng và dịch trên thiết bị di động”. Nội dung nghiên cứu Về mặt lý thuyết: - Nghiên cứu tổng quan về lĩnh vực OCR, các thành phần trong một hệ thống OCR cơ bản. - Nghiên cứu công nghệ mã nguồn mở Tesseract. - Nghiên cứu công nghệ mã nguồn mở Android. - Nghiên cứu mô hình client/server. - Nghiên cứu công nghệ dịch Google Translate. - Nghiên cứu phương pháp sửa lỗi chính tả tự động. 7 Về mặt thực hành: - Nghiên cứu xây dựng ứng dụng web service chạy trên server : sử dụng nguồn mở của Tesseract để tạo ra module có chức năng OCR trên ảnh; sử dụng các hàm API do Google cung cấp để tạo ra module có chức năng dịch văn bản sang ngôn ngữ tùy chọn. Web service còn hỗ trợ chức năng hậu xử lý kết quả OCR và tự động sửa lỗi chính tả trên ngôn ngữ tiếng Anh. - Nghiên cứu xây dựng ứng dụng trên client: sử dụng Android SDK để tạo ra ứng dụng chạy trên điện thoại Android có chức năng chụp ảnh; gửi ảnh về server và nhận kết quả xử lý từ server trả về; quản lý nội dung thông tin đã rút trích từ ảnh. Bố cục luận văn Ngoài phần mở đầu giới thiệu về mục tiêu, ý nghĩa, tình hình nghiên cứu liên quan và phần kết luận tóm tắt những kết quả chính đạt được cũng như đưa ra nhận xét; bố cục luận văn gồm 4 chương chính: Chương 1: Trình bày kiến thức tổng quan về lĩnh vực OCR làm nền tảng cho các nghiên cứu về sau. Chương 2: Trình bày nội dung tìm hiểu về công nghệ mã nguồn mở Tesseract OCR, công nghệ Android, mô hình client/server, công nghệ dịch Google Translate. Các công nghệ, mô hình này được sử dụng để xây dựng hệ thống. Chương 3: Giới thiệu kiến trúc và các thành phần cơ bản của hệ thống nhận dạng và dịch trên thiết bị di động đã xây dựng. Chương 4: Trình bày kết quả thực nghiệm chức năng rút trích thông tin từ ảnh của hệ thống cũng như so sánh một sách tương đối kết quả OCR với một số hệ thống khác. 8 CHƢƠNG 1 – TỔNG QUAN VỀ OCR 1.1. Giới thiệu về OCR Hình 1.1. Ứng dụng OCR[21] 1.1.1. OCR là gì OCR (optical character recognition)[7] là lĩnh vực nhận dạng ký tự quang học. Kỹ thuật này cho phép máy tính tự động nhận dạng ký tự thông qua cơ chế quang học. Đối tượng của OCR là ảnh scan các tài liệu, sách, hoặc các video liên quan. Mục tiêu của OCR là chuyển các nguồn tài liệu này sang các định dạng có thể chỉnh sửa và tìm kiếm được. Vào những những năm đầu của thế kỷ 20, các nhà khoa học đã quan tâm nghiên cứu trong lĩnh vực OCR. Tuy nhiên kết quả lúc bấy giờ vẫn còn rất hạn chế. Từ những năm 90 đến nay, OCR có những nghiên cứu mang tính đột phá, kết hợp với những công nghệ tiến tiến của thời đại đã cho ra đời những hệ thống OCR mạnh mẽ và hiệu suất cao. 9 Năm 1929, đã xuất hiện chiếc máy nhận dạng chữ số. Đến những năm đầu của thập niên 1950, chiếc máy đầu tiên có khả năng chuyển tài liệu bản in thành ngôn ngữ trên máy tính được phát minh bởi David Shepard, một chuyên gia về giải mã làm việc cho cơ quan An Ninh quốc gia Hoa Kỳ. Năm 1955 khi Reader‟s Digest mua lại công nghệ này, sản phẩm từ công nghệ OCR được đưa ra thương mại hóa lần đầu tiên. Tuy nhiên mãi đến năm 1978, phiên bản OCR cho máy tính mới được ra đời; ứng dụng đầu tiên của nó là dùng để tải những văn bản luật và tin tức lên cơ sở dữ liệu trực tuyến. Ngày nay, công nghệ OCR được kết hợp với máy scan tốc độ cao và những thuật toán máy tính phức hợp đã làm gia tăng tốc độ xử lý cũng như sự chính xác của dữ liệu. Những công nghệ OCR hiện tại đều có thể nhận dạng hầu hết các font chữ với độ chính xác cao, một số còn hỗ trợ khả năng kết xuất ra những đoạn văn bản có định dạng gần giống hoàn toàn với bản gốc[21]. Ngoài công nghệ nhận dạng ký tự quang học OCR thì hiện nay còn có thêm nhiều cơ chế nhận dạng tiêu biểu khác[9] được ứng dụng vào thực tế như: nhận dạng ký tự thông minh ICR (Intelligent Character Recognition), nhận dạng vùng đánh dấu OMR (Optical Mark Recognition), nhận dạng chữ mực từ MICR (Magnetic Ink Character Recognition) và cơ chế nhận dạng mã vạch (barcode). Các công nghệ tiên tiến này đã hỗ trợ rất nhiều cho các tổ chức và doanh nghiệp trong việc xử lý thông tin phát sinh xuyên suốt quá trình hoạt động. Những lĩnh vực thường được ứng dụng các công nghệ nhận dạng trên là giáo dục, tài chính, y tế, bảo hiểm, giao vận và ngay cả trong các tổ chức của chính phủ như thuế, hải quan[21]. Công nghệ nhận dạng OCR đã tạo ra sự ảnh hưởng to lớn trong việc lưu trữ, chia sẻ và chỉnh sửa thông tin. Trước đây, nếu chúng ta muốn chuyển một quyển sách từ bản in sang bản điện tử thì cách duy nhất là ngồi nhập thủ công toàn bộ quyển sách vào máy tính thông qua chương trình soạn thảo văn bản, và điều này buộc chúng ta phải trả giá với một khoảng thời không nhỏ. Tuy nhiên, ngày nay với sự phát triển vượt bậc của công nghệ thông tin, chỉ cần một máy scan kết nối với một máy tính tích hợp sẵn phần mềm nhận dạng OCR, bằng một vài thao tác đơn giản, toàn bộ quyển sách sẽ được chuyển thành tập tin đúng như mong muốn của người sử dụng. Do đó có thể nói, công nghệ OCR đã giúp người ta đến gần với nhiều dạng thông tin hơn, xóa bỏ nhiều rào cản về việc chia sẻ nguồn tri thức của nhân loại. Mặc dù không được sử dụng phổ biến và nhắc đến nhiều như các ngành công nghiệp viễn thông, phần cứng hay phần mềm nhưng ngành công nghiệp 10 nhận dạng lại mang đến hiệu quả rõ ràng nhất khi được đưa vào ứng dụng trong thực tế. Việc chuyển đổi thông tin từ tài liệu giấy sang tài liệu điện tử giúp nhiều người dùng có thể truy cập thông tin một cách dễ dàng, cùng một lúc dù ở bất cứ đâu mà không phải chờ đợi hoặc mất quá nhiều thời gian cho việc tìm kiếm. Điều này cũng tạo cho công tác quản lý và bảo mật thông tin trở nên đơn giản hơn khi tất cả những thay đổi hoặc ngày giờ truy cập thông tin đều được kiểm soát chặt chẽ. Đối với các doanh nghiệp, các tổ chức, các cơ quan hành chính, công nghệ OCR mang lại nhiều lợi ích kinh tế, tiết kiệm được những khoảng chi phí không nhỏ như giảm thiểu không gian lưu trữ, giảm tối đa nguồn nhân lực trong công tác quản lý thông tin. Hiện nay nhiều ứng dụng OCR được đưa ra sử dụng dưới dạng offline trên máy tính hoặc tích hợp và chạy online trên các thiết bị OCR chuyên dụng. Đặc biệt các hệ thống OCR thời gian thực được chú trọng phát triển. Các kỹ thuật nhận dạng hiện nay kết hợp rất hiệu quả với một số phương pháp luận trong lĩnh vực học máy (machine learning) như mạng nơ ron, mô hình Markov ẩn, SVM (supper vector machines), xử lý ngôn ngữ tự nhiên. Mặc dù được phát triển mạnh mẽ, nhưng kết quả nghiên cứu trong lĩnh vực OCR cũng gặp phải những trở ngại nhất định. OCR không bao giờ đạt tới tỷ lệ chính xác 100% trong nhiều trường hợp. Các yếu tố ảnh hưởng nhiều đến kết quả OCR như chất lượng ảnh đầu vào, bố cục ảnh, loại font chữ, các ký tự đặc biệt (ví dụ công thức toán học), các dạng chữ viết phức tạp (như chữ Trung Quốc) và một số yếu tố khác. 1.1.2. Một số công nghệ, phần mềm OCR tiêu biểu Lĩnh vực OCR hiện nay được rất nhiều cá nhân, tổ chức quan tâm nghiên cứu, nhiều công nghệ OCR ra đời và được ứng dụng rộng rãi trong nhiều lĩnh vực liên quan đến nhận dạng. Dưới đây liệt kê danh sách một số phần mềm OCR tiêu biểu[17]: Tên Giấy phép ABBYY FineReader Proprietary AnyDoc Software Proprietary Brainware Proprietary CuneiForm/OpenOCR BSD variant ExperVision TypeReader & RTK Proprietary GOCR GPL Image to OCR Converter Proprietary LEADTOOLS Proprietary Microsoft Office Document Imaging Proprietary 11 Microsoft Office OneNote 2007 Proprietary Nicomsoft CrystalOCR Proprietary Ocrad GPL OCRopus GPL OCRopus Apache OmniPage Proprietary Puma.NET BSD Readiris Proprietary ReadSoft Proprietary RelayFax Proprietary Scan2CAD Proprietary Scantron Proprietary SimpleOCR Freeware and Commercial SmartScore Proprietary Tesseract Apache Transym OCR Proprietary 1.1.3. Một số khái niệm cơ bản Pixel (Picture element)[2] : Ảnh trong thực tế là một ảnh liên tục về không gian và giá trị về độ sáng. Ảnh cần phải số hóa để có thể xử lý ảnh bằng máy tính. Trong quá trình số hóa ảnh người ta biến đổi tín hiệu liên tục thành tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lượng hóa thành phần giá trị mà nguyên tắc mắt thường không phân biệt được hai điểm kề nhau. Khái niệm Picture Element (ta quen gọi hay viết là pixel - phần tử ảnh, điểm ảnh) được sử dụng trong quá trình này. Do vậy một ảnh có thể coi là một tập các pixel. Ở đây cũng cần phân biệt khái niệm pixel hay đề cập đến trong các hệ thống đồ họa máy tính. Để tránh nhầm lẫn ta tạm gọi khái niệm pixel này là pixel thiết bị. Khái niệm pixel thiết bị có thể xem xét như sau: khi ta quan sát màn hình (chế độ đồ họa), màn hình không liên tục mà gồm nhiều điểm nhỏ, gọi là pixel. Trong ảnh 2 chiều, mỗi pixel gồm một cặp tọa độ x, y và màu. Độ phân giải của ảnh(Resolution)[2]: chính là mật độ điểm ảnh được ấn định trên một ảnh số được hiển thị. Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao cho mắt người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên một mật độ phân bổ, đó chính là độ phân giải và được bố trí theo hai trục x, y trong không gian hai chiều. Đơn vị cho độ phân giải là dpi (dots per inch). 12 Mức xám của ảnh: Mỗi điểm ảnh đều có một cường độ sáng. Mỗi mức xám là kết quả của sự mã hóa tương ứng một cường độ sáng của mỗi điểm ảnh với một giá trị số - kết quả của quá trình lượng hóa. Các thang giá trị mức xám thông thường là 16, 32, 64, 128, 256, trong đó mức thông dụng nhất là 256, mỗi pixel được mã hóa bởi 8 bit. Ảnh nhị phân: Tùy theo giá trị mức xám của điểm ảnh mà các ảnh được phân chia ra thành ảnh màu, ảnh xám hay ảnh nhị phân. Khi trên một ảnh chỉ có giá trị 0 hoặc 1 thì ta nói đó là một ảnh nhị phân hay một ảnh đen trắng và các điểm ảnh của nó gọi là điểm ảnh nhị phân. Ảnh màu: hay còn gọi là ảnh RGB. Cách biểu diễn cũng tương tự như ảnh đen trắng, chỉ khác là các số tại mỗi phần tử của ma trận biểu diễn cho ba màu riêng lẻ gồm: đỏ (Red), lục (Green), lam (Blue). Để biểu diễn cho một điểm ảnh màu cần 24 bit, 24 bit này chia thành 3 khoảng 8 bit. Mỗi khoảng này biểu diễn cho cường độ sáng của một trong các màu chính tổ hợp của các màu ta được nhiều mức biểu diễn, như vậy mỗi điểm ảnh có thể được mô tả rõ giá trị màu tự nhiên của nó (true color). Ảnh đa cấp xám: là ảnh có nhiều mức xám khác nhau. Thực tế chỉ ra rằng bất cứ ứng dụng nào trên ảnh mức xám cũng được ứng dụng trên ảnh màu. Ta có thể biến đổi ảnh màu về ảnh xám. Mỗi điểm ảnh màu gồm 3 giá trị (Red, Green, Blue), nếu 3 giá trị này bằng nhau thì ta có ảnh xám (grey). Khi đó mỗi điểm ảnh ta chỉ cần lưu 1 giá trị. Các đường cơ bản trong dòng text Hình 1.2. Các đường cơ bản trong dòng text  Đường 1 (capline): là đường thẳng giới hạn chiều cao của đỉnh cao nhất của một số chữ cái (ví dụ S, b,h,l..).  Đường 2 (mean line): là đường thẳng ở giữa của một dòng chữ, giới hạn chiều cao của các chữ bình thường (ví dụ u,a,r,n,….).  Đường 3 (baseline): là đường thẳng thẳng nối các phần chân của hầu hết các chữ cái trong dòng text, và bất kì một chữ nào cũng nằm trên một đường này.  Đường 4 (descent line) là đường thẳng giới hạn phần thấp của các chữ có thể tạo ra trên một dòng (p,y,…). 13  Khoảng cách giữa mean line và baseline là chiều cao cơ bản của một dòng chữ, gọi là x-Height. Thành phần liên thông (connected component): là tập hợp các pixel lân cận nhau. Thành phần liên thông gồm thành phần liên thông 4 và thành phần liên thông 8. Hình 1.3. Thành phần liên thông 4 và 8 1.2. Các bƣớc cơ bản trong một hệ thống OCR Hoạt động của một hệ thống OCR thông thường gồm các bước sau: thu nhận ảnh, tiền xử lý ảnh, phân tích bố cục trang, tách dòng và từ, huấn luyện và nhận dạng, hậu xử lý. Kết quả của mỗi bước ảnh hưởng rất lớn đến kết quả cuối cùng của hệ thống. Hình 1.4. Quy trình cơ bản trong một hệ thống OCR 1.2.1. Thu nhận ảnh Thu nhận ảnh là bước đầu tiên trong quy trình của hệ thống OCR. Hình ảnh tài liệu bên ngoài được thu nhận qua các thiết bị thu ảnh như camera, máy ảnh, máy scan và được số hóa để biến đổi tín hiệu tương tự thành tín hiệu rời rạc (lấy mẫu) và lưu vào máy tính dưới các định dạng file ảnh. Ảnh thu được có thể là ảnh trắng đen, ảnh màu, ảnh đa cấp xám... Độ phân giải của ảnh ảnh hưởng rất lớn đến kết quả OCR. Ảnh thu được có độ phân giải 300dpi không phải là chuẩn 14 chính thức quy ước cho các ảnh đầu vào của các hệ thống OCR nhưng cũng có thể xem như một chuẩn tương đối tốt. Tuy nhiên không phải ảnh có độ phân giải càng cao thì kết quả OCR càng tốt. Do đó các hệ thống OCR khuyến nghị các bức ảnh đầu vào nên có độ phân giải từ 200dpi – 400dpi. Để nâng cao hiệu quả OCR, ngoài việc cố gắng đảm bảo độ phân giải của ảnh nằm trong khoảng tương đối chấp nhận được, các bức ảnh thu được cần tiến hành xử lý nhằm nâng cao chất lượng trước khi đưa vào nhận dạng. Quá trình này gọi là tiền xử lý ảnh. 1.2.2. Tiền xử lý ảnh Các bức ảnh thu được chất lượng thường không tốt như ý muốn, có thể do một số nguyên nhân như: chất lượng của thiết bị thu ảnh (độ phân giải thấp), yếu tố nguồn sáng, tài liệu ảnh thực tế bị suy biến, tư thế chụp không đúng...Do vậy, ảnh trước khi đưa vào nhận dạng cần phải qua một số bước xử lý nhằm tăng cường chất lượng ảnh, làm nổi bật một số đặc tính của ảnh, đặc biệt tăng độ tương phản giữa foreground (đối tượng trong ảnh) và background (nền ảnh). Một số công việc chủ yếu trong bước này bao gồm nhị phân hóa ảnh, dò hướng đúng và chỉnh độ nghiêng ảnh, giảm nhiễu để loại bỏ những thành phần không cần thiết. 1.2.2.1. Nhị phân hóa ảnh Mục đích của nhị phân hóa là biến ảnh gốc thành ảnh nhị phân nhằm tăng sự tương phản giữa nền (background) và các đối tượng (object hay foreground). Nếu đầu vào là ảnh màu, trước khi nhị phân hóa cần chuyển sang ảnh xám theo tiêu chuẩn: Grey = 0.3R + 0.59G + 0.11 B. Quan trọng nhất trong bước nhị phân hóa ảnh gốc là xác định ngưỡng xám T (0 ≤ T ≤ 255). Nếu giá trị cường độ của một pixel ≤ T, pixel này được thiết lập là màu đen, ngược lại là màu trắng. Nhị phân hóa ảnh gồm 2 loại: Nhị phân hóa toàn cục: sử dụng một ngưỡng T duy nhất cho toàn bộ bức ảnh Nhị phân hóa cục bộ: tính toán lại ngưỡng T thích hợp cho từng vùng ảnh 15 Việc tính toán chọn ngưỡng T phù hợp có ý nghĩa rất lớn trong quá trình nhị phân hóa. Một số phương pháp xác định ngưỡng xám T phổ biến và hiệu quả như Otsu (ngưỡng toàn cục); Niblack, Sauvola (ngưỡng cục bộ). Dưới đây trình bày phương pháp Otsu trong việc xác định ngưỡng xám toàn cục. Phương pháp Otsu[6] Lược đồ mức xám: là một hàm rời rạc cung cấp tần suất xuất hiện của mỗi mức xám. trong đó: sk là mức xám thứ k; nk là số các điểm ảnh khác có cùng mức xám s k; n là tổng số các điểm ảnh trong ảnh. Minh họa với bức ảnh 6x6 với các pixel chỉ trong 6 mức xám: Hình 1.5. Mô tả lược đồ mức xám Phương pháp Otsu được mô tả như sau: Bước 1: Chọn một giá trị ước lượng ngưỡng xám ban đầu T. Thông thường T được chọn là giá trị mức xám trung bình của bức ảnh. Ví dụ trong lược đồ mức xám Hình 1.5, có thể chọn T = 3. Bước 2: Dùng ngưỡng T phân hoạch bức ảnh thành 2 phân vùng R1, R2 (tương ứng 2 lược đồ mức xám mới Hình 1.6). Hình 1.6. Phân ngưỡng trên lược đồ mức xám 16 Bước 3: Tính toán giá trị mức xám trung bình  1 và  2 của hai phân vùng R1, R2 . 1 Bước 4: Tính toán lại giá trị ngưỡng T mới : T = 1   2  . 2 Bước 5: Lặp lại bước 2 đến bước 4 đến khi nào độ biến thiên của ngưỡng T bé hơn giá trị  cho trước. Hình 1.7. Kết quả chọn ngưỡng xám theo phương pháp Otsu 1.2.2.2. Chỉnh độ nghiêng và hướng Ảnh thu được có thể bị nghiêng, bị xoay ngang dọc do vị trí đặt tài liệu cần thu ảnh lệch vị trí đúng với thiết bị thu ảnh. Với những bức ảnh như thế, hiệu quả nhận dạng giảm đi rõ rệt. Do đó trước khi nhận dạng, ta cần thực hiện việc chỉnh lại độ nghiêng và hướng của trang ảnh. Sau khi xác định được độ nghiêng và hướng chính xác của ảnh sẽ thực hiện việc quay ảnh về lại trạng thái đúng ban đầu. Tuy nhiên ít nhiều chất lượng ảnh sẽ bị giảm sau khi quay. Một số phương pháp xác định độ nghiêng trang ảnh như phương pháp hình chiếu, phương pháp biến đổi Hough, phương pháp dựa trên các thành phần liên thông và một số phương pháp khác như phân tích độ lệch so với trục dọc, biến đổi Fourier, các phép toán hình thái[8]. Nhiều phương pháp dò hướng cũng được đề xuất và áp dụng, một số tác giả như Caprari đưa ra năm 1999, Aradhyu đưa ra năm 2005, Lu và một số tác giả khác đưa ra năm 2006[8]. Việc dò tìm độ nghiêng và hướng của trang ảnh có thể thực hiện riêng lẻ hoặc kết hợp đồng thời với nhau. Một phương pháp tiêu biểu cho việc kết hợp giữa việc dò độ nghiêng và hướng được đưa ra bởi Breuel (và một số tác giả khác) sử dụng mô hình hóa hình học của các dòng text chữ viết Latinh[8]. Dò độ nghiêng và quay ảnh thực hiện trong phạm vi góc -45o, +45o (Hình 1.8); dò hướng đúng và quay ảnh theo các hướng 0o, 90o, 180o, 270o (Hình 1.9). Hình 1.8. Ảnh văn bản trước và sau khi chỉnh nghiêng 17 Hình 1.9. Ảnh văn bản trước và sau khi chỉnh hướng đúng 1.2.2.3. Giảm nhiễu Việc xuất hiện nhiễu, đặc biệt ở biên ảnh (các thành phần không mong muốn trong ảnh) làm tăng thời gian và giảm kết quả OCR bởi nhiễu trong ảnh nếu không làm lọc đi sẽ được OCR như là ký tự bình thường, thậm chí làm sai lệch nghiêm trọng kết quả với các vùng text thực sự. Hình 1.10. Các vùng nhiễu trên ảnh văn bản[8] Nhiễu trong tài liệu ảnh có thể do nhiều nguyên nhân: sự xuống cấp của tài liệu theo thời gian, sự tác động vật lý, hóa học của môi trường xung quanh; tác động ngoại cảnh trong quá trình chụp ảnh như ánh sáng không tốt. Do đó trước khi nhận dạng, ảnh cần áp dụng một vài kỹ thuật phù hợp để giảm nhiễu nhằm tạo ra một ảnh tốt hơn cho các bước phía sau của quá trình OCR. Nhiễu trong ảnh thực tế gồm nhiều loại song chúng ta thường chú ý và xem xét đến 3 loại nhiễu chính: nhiễu cộng, nhiễu nhân, nhiễu xung [3]. - Nhiễu cộng thường phân bố khắp ảnh. Nếu gọi ảnh quan sát (ảnh thu được) là Xqs , ảnh gốc là Xgốc, nhiễu là  , ảnh thu được có thể biểu diễn bởi: Xqs = Xgốc +  18 - Nhiễu nhân thường được phân bố khắp ảnh và ảnh thu được sẽ biểu diễn bởi công thức: Xqs = Xgốc *  - Nhiễu xung thường gây đột biến tại một số điểm ảnh. Từ bản chất của nhiễu (thường tương ứng với tần số cao) và từ cơ sở lý thuyết lọc là: bộ lọc chỉ cho tín hiệu có tần số nào đó thông qua, do đó để lọc nhiễu người ta thường sử dụng bộ lọc thông thấp (theo quan điểm tần số không gian) hay lấy tổ hợp tuyến tính để sang băng (bộ lọc trung bình). Để làm nổi cạnh (ứng với tần số cao), người ta sử dụng bộ lọc thông cao, lọc Laplace[2]. Do có nhiều loại nhiễu can thiệp vào quá trình xử lý ảnh nên cần nhiều bộ lọc thích hợp. Với nhiễu cộng và nhiễu nhân ta dùng các bộ lọc thông thấp, trung bình và lọc đồng hình (homomorphie); với nhiễu xung ta dùng bộ lọc trung vị, giả trung vị, lọc ngoài (Outlier)[2]. Trong lọc trung bình người ta ưu tiên cho các hướng để bảo vệ biên của ảnh khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng tùy theo các trường hợp khác nhau. Các bộ lọc trên là bộ lọc tuyến tính theo nghĩa điểm ảnh ở tâm cửa sổ sẽ được thay bởi tổ hợp các điểm lân cận chập với mặt nạ. Lọc thông thấp thường được dùng để làm trơn nhiễu. Các bộ lọc phi tuyến cũng được dùng trong kỹ thuật tăng cường ảnh. Trong kỹ thuật này người ta dùng bộ lọc trung vị, giả trung vị, lọc ngoài. Với bộ lọc trung vị các điểm ảnh sẽ được thay thế bởi trung vị các điểm ảnh, còn lọc giả trung vị sẽ dùng trung bình cộng của 2 giá trị “trung vị” (trung bình cộng của max và min)[2]. 1.2.3. Phân tích bố cục Tài liệu ảnh thường gồm các “vùng đối tượng” có nội dung, tích chất khác nhau (vùng ảnh, vùng text, bảng biểu...). Phân tích bố cục tài liệu ảnh là một bước quan trọng được thực hiện để xác định cấu trúc, xác định các vùng đối tượng được bố trí trong tài liệu ảnh. Cấu trúc của tài liệu ảnh thường được quan tâm trong việc phân tích bố cục là cấu trúc vật lý và cấu trúc lôgic. Cấu trúc vật lý chỉ ra vị trí, đường biên giữa các vùng đối tượng khác nhau. Việc xác định cấu trúc vật lý có ý nghĩa rất lớn đối với lĩnh vực OCR trong việc chỉ lấy và xử lý các vùng text, giảm thời gian thực hiện và tăng độ chính xác kết quả.