Tài liệu Xây dựng ứng dụng OCR cho thiết bị iPhone

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐINH QUANG HUY XÂY DƢ̣NG Ƣ́NG DỤNG OCR CHO THIẾT BI ̣iPHONE 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Ệ ĐINH QUANG HUY XÂY DƢ̣NG Ƣ́NG DỤNG OCR CHO THIẾT BI ̣iPHONE 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. PHẠM BẢO SƠN Hà Nội – 2011 MỤC LỤC CHƢƠNG 1 TỔNG QUAN VỀ OCR VÀ Ƣ́NG DỤNG OCR ................. 1 1.1 Tổ ng quan về bài toán nh ận dạng văn bản – OCR......................... 1 1.2 Mục tiêu xây dƣ̣ng ƣ́ng du ̣ng OCR ............................................... 2 CHƢƠNG 2 THƢ VIỆN MỞ TESSERACT ............................................ 5 2.1 Lịch sử ra đời ................................................................................ 5 2.2 Tổng quan kiến trúc ...................................................................... 5 2.3 Xác định dòng và từ ...................................................................... 6 2.4 Nhận dạng từ ................................................................................ 9 2.5 Bộ phân loại kí tự tĩnh ................................................................ 11 2.6 Phân tích ngôn ngữ ..................................................................... 13 2.7 Phân lớp động ............................................................................. 13 CHƢƠNG 3 KIẾN TRÚ C CỦA Ƣ́NG DỤNG OCR .............................. 15 3.1 Kiến trúc của hệ điều hành của iPhone ........................................ 15 3.2 Kiến trúc hê ̣ điề u hành iOS ......................................................... 15 3.3 Mô ̣t số chƣ́c năng và dich ̣ vu ̣ của lớp Cocoa Touch ..................... 17 3.4 Mô ̣t số API cơ bản của lớp thƣ viện Cocoa Touch ...................... 20 3.5 Mô hình kiến trúc của chƣơng trình OCR ................................... 24 3.6 Mô hình thiết kế .......................................................................... 26 CHƢƠNG 4 CHƢƠNG TRÌNH THƢ̣C NGHIỆM ................................ 28 4.1 Giới thiệu mô trƣờng phát triển và cách cài đặt ........................... 28 4.2 Giới thiệu về công cu ̣ phát triể n ƣ́ng ........................................... 30 4.3 Chƣơng trình thực nghiệm .......................................................... 32 4.4 Kế t quả thƣ̣c nghiê ̣m ................................................................... 34 KẾT LUẬN .............................................................................................. 36 TÀI LIỆU THAM KHẢO ........................................................................ 37 PHỤ LỤC 1. GIỚI THIỆU NGÔN NGƢ̃ LẬP TRÌNH OBJECTIVE -C 38 DANH MỤC HÌNH VẼ Hình 1. Mô hình tổng quan của một hệ thống OCR ................................ 2 Hình 2. Thị phần thiết bị di động chia theo hệ điều hành - Nguồ n : Gartner (tháng 2/2011) ....................................................................................... 3 Hình 3. Ứng dụng OCR cho iPhone ....................................................... 4 Hình 4. Minh họa về đƣờng cơ sở đã đƣợc hiệu chỉnh cong. .................. 8 Hình 5. Ví dụ minh họa một từ đã đƣợc cắt theo chiều cao cố định ........ 8 Hình 6. Minh họa của từ có khoảng cách khó xác định ........................... 9 Hình 7. Ví dụ về điểm cắt thích hợp và nhát căt ................................... 10 Hình 8. Minh ho ̣a chƣ̃ bi ̣đƣ́t đoa ̣n ........................................................ 11 Hình 9. (a) Kí tự ‗h‘ mẫu, (b) ‗h‘ đứt đoạn, (c) nét đặc trƣng so với mẫu 11 Hình 10. Chuẩn hóa ký tự theo đƣờng cơ sở và mo-men ........................ 14 Hình 11. Các ứng dụng dựa trên hệ điều hành iOS ................................. 16 Hình 12. Các lớp thƣ viê ̣n của iOS ......................................................... 16 Hình 13. Cấ u trúc phân hê ̣ các lớp trên bô ̣ thƣ viê ̣n Cococa ................... 24 Hình 14. Mô hin ̀ h MVC ......................................................................... 26 Hình 15. Mô hình Cococa MVC của Apple ............................................ 26 Hình 16. Mô hin ̀ h Use-Case của ƣ́ng du ̣ng ............................................. 27 Hình 17. Mô hin ̀ h cô ̣ng tác của ƣ́ng du ̣ng OCR ...................................... 27 Hình 18. So sánh giữa iPad và iPhone. ................................................... 29 Hình 19. Cài đặt iPhone SDK ................................................................. 31 Hình 20. Bộ công cụ Xcode, Interface Builder, iPhone simulator ........... 32 Hình 21. Giao diện chƣơng trình thực nghiệm ........................................ 33 Hình 22. Kể quả thử nghiệm chƣơng trình.............................................. 34 DANH MỤC BẢNG BIỂU Bảng 1. Kết quả thực nghiệm chƣơng trình ........................................... 35 I GIỚI THIỆU Các kết quả nghiên cứu trong lĩnh vực nhận dạng quang học (OCR) đã đạt đƣợc những thành công vƣợt bậc trong việc giúp chuyển đổi các tài liệu văn bản từ dạng hình ảnh sang dạng văn bản có thể chỉnh sửa, soạn thảo đƣợc. Hƣớng nghiên cứu OCR ra đời từ trƣớc khi có máy tính điện tử, đến nay đã hình thành một thị trƣờng phần mềm chuyên về xử lý nhận dạng văn bản. Có rất nhiều phần mềm nổi tiếng nhờ có độ chính xác cao và hỗ trợ nhiều ngôn ngữ nhƣ phần mềm FineReader của hãng AABBYY, OmmiPage của hãng Scansoft đƣợc dùng để nhận dạng các văn bản tiếng Anh,… VNDOCR của Viện công nghệ thông tin cho các văn bản tiếng Việt. Các phần mềm trên chủ yếu là hoạt động dựa nền tảng là máy tính cá nhân. Trong khi đó, các thiết bị di động thông minh (smartphone) ngày càng mạnh hơn trong năng lực xử lý nhƣng chƣa có nhiều phần mềm ứng dụng OCR cho các thiết bị này. Mục tiêu của luân văn này là nghiên cứu bộ thƣ viện mở Tesseract [6] và xây dựng ứng dụng OCR cho thiết bị di dộng dựa trên nền hệ điều hành iOS. Nội dung của luận văn sẽ nghiên cứu, làm rõ kiến trúc của bộ thƣ viện mã nguồn mở Teseract. Đây là bộ thƣ viện mã nguồn mở có độ chính xác tốt và có thể hoạt động trên nhiều nền tảng hệ điều hành khác nhau. Luận văn này cũng sẽ đi sâu vào việc tìm hiểu kiến trúc của hệ điều iOS, hệ điều hành của hãng Apple dùng chi các thiết bị di động nhƣ iPhone, iPod Touch, iPad, qua đó giúp tác giả phân tích, thiết kế kiến trúc cho ứng dụng OCR phù hợp với việc thực thi trên hệ điều hành dành cho thiết bị di động này. Kết quả của luận này là sản phẩm phần mềm ứng dụng OCR cho thiết bị iPhone. Sản phẩm này có tính ứng dụng thực tiễn cao. Ngƣời sử dụng có thể cài đặt phần mềm này và sử dụng carmera có sẵn của thiết bị để chụp lại ảnh các tài liệu cần nhận dạng, chuyển đổi. Các dữ liệu hình ảnh sẽ đƣợc nhận dạng và chuyển đổi sang dạng dữ liệu văn bản. Sau đó, thông qua công cụ dịch của Google, dữ liệu văn bản này có thể đƣợc dịch sang ngôn ngữ có thể hiểu đƣợc đối với ngƣời dùng. II LỜI CẢM ƠN Trƣớc tiên tôi xin gửi lời cảm chân thành tới các thầy, cô giáo trong trƣờng Đại Học Công Nghệ và đặc biệt là thầy TS. Phạm Bảo Sơn. Thầy Sơn là ngƣời đã trực tiếp giảng dậy cũng nhƣ là ngƣời hƣớng dẫn khoa học. Trong quá trình học tập tại trƣờng mỗi giờ lên lớp của các thầy cô trong trƣờng đã giúp ích cho tôi rất nhiều trong việc mở rộng tầm hiểu biết của mình không chỉ về kiến thức chuyên môn mà còn cả về những kinh nghiệm thực tiễn. Trong quá trình làm luận văn khoa học, các chỉ dẫn kịp thời của thầy Phạm Bảo Sơn đã giúp tôi có đƣợc những hƣớng nghiên cứu khoa học đƣợc chính xác hơn. Trong quá trình học tập và nghiên cứu khoa học, tôi đã nhận đƣợc rất nhiều sự cổ vũ động viên khích lệ tinh thần của gia đình đặc biệt là từ vợ - Vũ Thị Xuân Hƣơng và con gái tôi Đinh Thanh Trúc. Gia đình là chỗ dựa vững chắc về tinh thần giúp tôi vƣợt qua đƣợc những khó khăn trong cuộc sống. Mọi ngƣời trong gia đình luôn quan tâm chăm sóc và dành nhiều thời gian cho tôi phục vụ công việc nghiên cứu khoa học qua đó đã giúp tôi hoàn thành đề tài luận văn này. Tôi cũng xin cảm ơn tới những ngƣời bạn, những đồng nghiệp luôn sát cánh bên tôi tại Trung tâm CNTT – Học viện Công Nghệ Bƣu Chính Viễn Thông. Tại đây tôi đã nhận đƣợc những chia sẻ về kinh nghiệm công việc, kinh nghiệm thực tiễn về nghiên cứu khoa học. Qua đó đã giúp tôi có đƣợc nhiều kinh nghiệm hơn trong việc nghiên cứu và làm khoa học. Một lần nữa tôi xin cảm ơn tất cả các thầy cô giáo, những ngƣời thân trong gia đình, những bạn bè, đồng nghiệp đã giúp đỡ tôi rất nhiều về kiến thức chuyên môn, kinh nghiệm thực tế, động viên khích lệ tinh thần trong quá trình hoàn học tập, nghiên cứu khoa học của tôi. Những đóng góp trên là một phần thành công của luận văn này. Mọi đóng góp về luận văn này xin gửi về địa chỉ email [email protected]. Xin chân thành cảm ơn 1 CHƢƠNG 1 TỔNG QUAN VỀ OCR VÀ ỨNG DỤNG OCR 1.1 Tổng quan về bài toán nhận dạng văn bản – OCR Ngày nay, hầu nhƣ tất cả thông tin đƣợc lƣu trữ và xử lý trên máy tính. Mỗi ngày, chúng ta nhập một khối lƣợng dữ liệu rất lớn vào máy tính. Nhƣng dƣờng nhƣ bản thân máy tính không đủ thông minh để nhận biết các kí hiệu, kí tự, hình ảnh … mà con ngƣời sử dụng. Điều đó làm giảm rất lớn hiệu quả công việc của con ngƣời. Do đó, vấn đề nhận dạng ra đời giống nhƣ cầu nối giữa con ngƣời và máy tính nhằm tăng khả năng xử lý thông tin của máy tính. Nằm trong số những bài toán nhận dạng, nhận dạng văn bản nhằm giải quyết vấn đề nhận dạng các kí tự xuất hiện trong văn bản. Nó có ý nghĩa đặc biệt quan trọng trong xử lý thông tin vì phần lớn thông tin mà con ngƣời sử dụng ở dạng kí tự. Hơn nữa, ngày càng nhiều thiết bị di động thông minh (smartphone) hay các thiết bị cầm tay nhỏ gọn nhƣ máy PDA (Personal Digital Assitants, thiết bị điện tử cầm tay), là công cụ tiện dụng trong xử lý thông tin cá nhân. Các thiết bị này, ngày nay, thƣờng đƣợc trang bị các thành phần xử lý tốc độ cao và thƣờng tích hợp sẵn camera có độ phân giải cao. Do đó, chúng ta có thể xây dựng các ứng dụng nhận dạng ký tự cho các loại thiết bị này nhằm nâng cao hơn nữa tiện ích sử dụng của ngƣời dùng trong các hoạt động phục vụ công việc nghiên cứu học tập hoặc là công cụ dịch tự động cho ngƣời đi du lịch nƣớc ngoài. Vấn đề nhận dạng văn bản đã đƣợc nghiên cứu gần bốn thập kỉ qua. Nhƣng chỉ những năm gần đây, kỹ thuật nhận dạng mới đƣợc phát triển đủ mạnh để có thể xây dựng các ứng dụng thƣơng mại. Có nhiều loại vấn đề trong nhận dạng chữ nhƣ việc thể hiện đặc trƣng trong hệ thống nhận dạng hay vấn đề chia cắt kí tự trong một từ để nhận dạng.vv... Các bộ thƣ viện, phần mềm OCR đặc trƣng thƣờng có mô hình xử lý với các bƣớc nhƣ hình bên dƣới. 2 Hình 1. Mô hình tổng quan của một hệ thống OCR 1.2 Mục tiêu xây dựng ứng dụng OCR Hiê ̣n nay các sản phẩ m thiế t bi ̣m áy tính bảng , điê ̣n thoa ̣i thông minh ngày càng phổ biến . Các sản phẩm này ngày càng mạnh mẽ về hiệu năng xử lý cũng nhƣ giầ u tính năng sƣ̉ du ̣ng nhờ có nhiề u phầ n mề m ƣ́ng du ̣ng trên đó . Có rất nhiề u công ty trong liñ h vƣ̣c thiế t bi ̣di đô ̣ng cùng tham gia vào thị phần này nhƣ Nokia, Sony, LG, Samsam, Apple…Trong các sản phẩ m điê ̣n thoa ̣i thông minh thì thiết bị iPhone của hãng Apple - Mỹ đang giành đƣợc nhiều sự quan tâm không chỉ ngƣời sƣ̉ du ̣ng mà cả cô ̣ng đồ ng phát triể n ƣ́ng du ̣ng cho thiế t bi ̣này . 3 Hình 2. Thị phần thiết bị di động chia theo hê ̣ điề u hành - Nguồ n : Gartner (tháng 2/2011) Theo kế t quả điề u tra của tổ chƣ́c nghiên cƣ́u Gatner thì năm 2010 có 1.6 tỷ thiế t bi ̣đi đô ̣ng đã đƣơ ̣c bán ra. Trong đó hañ g Apple đã bán đƣơ ̣c 46.6 triê ̣u sản phẩ m, tăng 87.2% so với năm 2009. Kế t quả điề u tra cho thấ y các thiế t bi ̣d i đô ̣ng iPhone đang ngày càng trở nên phổ biế n đố i với ngƣời dùng . Nhằ m năng cao thi ̣phầ n cũng nhƣ cung cấ p nhiề u tiê ̣n ích hơn đố i với ngƣời dùng sản phẩ m của mình , hãng Apple đã xây dựng và khai trƣơng một kho ƣ́ng du ̣ng trƣ̣c tuyế n riêng dành cho các thiế t bi ̣dƣ̣a trên nề n hê ̣ điề u hành iOS vào tháng 6 năm 2008. Theo báo cáo mới nhấ t của hañ g Apple , tính đến ngày 22 tháng 1 năm 2011, số ƣ́ng du ̣ng hiê ̣n có kho ƣ́ng du ̣ng trƣ̣c tuyế n của hãng đã lên tới con số hơn 350,000 với hơn 10 tỷ lƣợt tải ứng dụng của ngƣời dùng. Các ứng dụng trên kho ƣ́ng du ̣ng trƣ̣c tuyế n của Apple rấ t đa da ̣ng và phong phú nhằ m cung cấ p cho ngƣời sƣ̉ du ̣ng rấ t nhiề u ƣ́ng du ̣ng về tiê ̣n ić h văn phòng, công cu ̣ ho ̣c tâ ̣p , giáo dục , ứng dụng trò chơi giải trí , du lich…Mu ̣ ̣c tiêu của việc x ây dƣ̣ng ƣ́ng du ̣ng OCR cho iPhone là nhằ m bổ xung thêm mô ̣t ƣ́ng dụng vô cùng tiện í ch phu ̣c vu ̣ dich ̣ vu ̣ chuyể n đổ i các dòng văn bản ở da ̣ng hình ảnh thành định dạng văn bản thuần túy có thể soạn thảo đƣợc . Các dòng văn bản sau khi đƣơ ̣c chuyể n đổ i sẽ đƣơ ̣c dich . ̣ tƣ̣ đô ̣ng sang ngôn ngƣ̃ tùy cho ̣n khác 4 Đây là mô ̣t ƣ́ng du ̣ng hƣ̃u ić h giúp cho ngƣời sƣ̉ du ̣ng thiế t bi ̣khi muố n dich ̣ nhanh mô ̣t cu ̣m tƣ̀ hay mô ̣t đoa ̣n văn bản ngắ n . Ứng dụng này rất có ích kh i ngƣời sƣ̉ du ̣ng đi du lich ̣ ở nƣớc ngoài , hoă ̣c ngƣời không rành ngoa ̣i ngƣ̃ . 心筋梗塞 Nhồi máu cơ tim Hình 3. Ứng dụng OCR cho iPhone 5 CHƢƠNG 2 THƢ VIỆN MỞ TESSERACT 2.1 Lịch sử ra đời Tesseract là một thƣ viện OCR mã nguồn mở [6] đƣợc phát triển bởi hãng HP từ năm 1984 đến 1994. Tesseract đƣợc ra đời từ một dự án nghiên cứu luận án tiến sỹ [1] tại phòng thí nghiệm của HP tại Brsitol và nó đƣợc thúc đẩy mạnh mẽ hơn để có thể cho ra một sản phẩm phần mềm khả thi đi kèm với dòng sản phẩm máy quyét để bàn của HP. Một nhân tố nữa thúc đẩy dự án này đó là các sản phẩm OCR thƣơng mại lúc đó mới bắt đầu hình thành và vẫn còn nhiều lỗi cho dù chất lƣợng ảnh đầu vào rất tốt. Ngay sau khi phòng thí nghiệm ở Bristol và phòng phát triển máy quét tại Colorado, đều của hãng HP, sát nhập với nhau, Tesseract đã có những bƣớc tiến đáng kể về độ chính xác, vƣợt qua cả những sản phẩm thƣơng mại, nhƣng nó vẫn chƣa trở thành 1 sản phẩm phần mềm thực sự. Sau đó phòng thí nghiệm Bristol của HP tiếp tục phát triển thƣ viện này với mục tiêu làm cho nó gọn nhỏ hơn. Các công việc chủ yếu tập trung vào việc nâng câu hiêu quả của việc loại bỏ các thông tin dƣ thừa mà không tập vào việc cải thiện mức độ chính xác cơ bản hiện tại. Vào cuối dự án, cuối năm 1994, việc phát triển dừng lại hoàn toàn. Thƣ viện này sau đó, năm 1995, đƣợc chuyển cho trƣờng đại học Nevada, Las Vegas để thực hiện việc kiểm thử độ chính xác của các phần mềm nhận dạng văn bản – OCR, đây là một cuộc kiểm tra đƣợc tổ chức thƣờng niên. Tại thời điểm năm 1995 Tesseract là 1 trong 3 sản phẩm có độ nhận dạng chính xác tốt nhất. Năm 2005, HP chính thức công bố Tesseract dƣới dạng mã nguồn mở. Hiện tại nó đang đƣợc lƣu trữ tại http://code.google.com/p/tesseract-ocr. 2.2 Tổng quan kiến trúc HP đã tự phát triển độc lập công nghệ phân tích cấu trúc trang, công nghệ đã đƣợc sử dụng trong các sản phẩm của HP (và do vậy nó không đƣợc công bố dƣới dạng mã nguồn mở) nên bản thân kiến trúc của Tesseract [3] không bao gồm bộ phân tích cấu trúc trang của riêng nó. Thƣ viện Tesseract mặc định đầu 6 vào của nó là một ảnh nhị phân và một tùy trọn là vùng văn bản cần nhận dạng đƣợc xác định trƣớc. Quá trình xử lý tuân theo các bƣớc của mô hình kiến trúc pipeline, tuy nhiên có 1 vài khâu xử lý không đƣợc sử dụng nhƣng vẫn còn giữ lại tại các phiên bản hiện tại. Bƣớc đầu tiên là phân tích các thành phần liên thông, theo đó các nét chính của các thành phần sẽ đƣợc lƣu lại. Đây là bƣớc tính toàn tốn rất nhiều thời gian, nhƣng nó có ƣu điểm quan trọng: bằng việc phát hiện ra các nét lồng nhau và số lƣợng các nét con, cháu sẽ giúp cho Tesseract dễ dàng nhận biết đƣợc chữ bị đảo ngƣợc và nhận dạng nó một cách dễ dàng vời các chữ đen trên nền trắng. Tesseract có lẽ là thƣ viện OCR đầu tiên có khả năng xử lý đƣợc các chữ trắng trên nền đen một cách hiệu quả. Tại giai đoạn này, các đƣờng nét đƣợc nhóm lại với nhau thành các blob. Các blob đƣợc nhận dạng thành các dòng chữ và các vùng đƣợc phân tích theo các văn bản có độ nghiêng cố định hoặc mang tính tỷ lệ. Các dòng văn bản đƣợc chia thành các từ khác nhau dựa theo kiểu ký tự giãn cách. Các chữ có độ nghiêng cố định đƣợc cắt gọt thành từng từ ô ký tự. Các chữ mang tính tỷ lệ thì đƣợc chia thành các từ bằng việc sử dụng các khoảng trống đƣợc định nghĩa sẵn và các khoảng trống ―mờ‖. Quá trình nhận dạng sau đó là một tiến trình 2 pha. Trong pha thứ nhất, nó cố gắng nhận ra các từ một cách lần lƣợt. Mỗi từ sau đó nếu thỏa mãn các điều kiện thì sẽ đƣợc chuyển cho bộ phân lớp động nhƣ là dữ liệu huấn luyện. Bộ phân lớp động sau đó sẽ có cơ hội nhận dạng chính xác hơn các văn bản ở phía bên dƣới trang. Do bộ phân lớp động có thể sẽ nhận đƣợc các dữ liệu hữu ích qua trễ để có thể xử lý đƣợc văn bải phía đầu trang, cho nên một pha thứ 2 sẽ chạy lại toàn bộ trang, trong đó các từ chƣa đƣợc nhận dạng dầy đủ sẽ đƣợc nhận dạng lại. Bƣớc cuối cùng là xử lý các khoảng trống không rõ ràng và kiểm tra các giả thiết lựa chọn chiều cao để xác định các văn bản chữ thƣờng (không phải chữ hoa). 2.3 Xác định dòng và từ 7 2.3.1 Tìm dòng Giải thuật xác định dòng đƣợc thiết kế để có thể nhận dạng một trang văn bản bị nghiêng, xiên mà không cần phải khử nghiêng, do đó nó tránh đƣợc việc làm mất thông tin ảnh. Các thành phần quan trọng trong tiến trình xử lý đó là lọc ra đƣợc các khối ký tự và tạo dựng dòng văn bản. Giả sử rằng, bộ phân tích cấu trúc trang đã xác định và đƣa các các vùng văn bản thô với cỡ chữ đồng nhất, lúc này 1 bộ lọc phân vị cao (percentile height filter) sẽ loại bỏ các chữ hoa trang trí (drop-cap) và các kí tự dựng đứng. Độ cao trung bình gần đúng với cỡ chữ trong vùng, do vậy rất an toàn khi lọc bỏ các ô chữ mà có độ cao nhỏ hơn so với độ cao trung bình theo một tỷ lệ nào đó. Các ô bị lọc đi phần lớn là các dấu cú pháp nhƣ chấm, phẩy hay các dấu của ký tự thậm chí là cả nhiễu. Các ô đã đƣợc lọc ra phần lớn là các mẫu không phủ lấp lên nhau đứng song song. Việc xắp xếp, xử lý các ô này theo trục x sẽ giúp chúng ta gán các ô ký tự đó vào một dòng văn bản duy nhất, trong khi vẫn bám theo độ dốc trên toàn trang, nên đã giảm thiểu đi rất nhiều sai sót do gán nhầm vào các dòng không đúng do sự nghiêng, méo của trang. Khi các ô đƣợc gắn vào các dòng, một bộ lọc trung vị thích hợp đƣợc sử dùng để ƣớc lƣợng các dòng cơ bản và các ô đã bị loại bỏ trƣớc đấy đƣợc đƣa trở lại vào dòng tƣơng ứng. Bƣớc cuối cùng của dòng quá trình tạo đƣờng thẳng là trộn lại các ô mà bị phủ lấp nên nhau ít nhất 1 nửa kích thƣớc theo chiều ngang, đặt các ký tự dấu vào đúng phần tử đã đƣợc nhận dạng chính xác trƣớc đó và nối một cách chính xác các phần đứt đoạn của ký tự. 2.3.2 Hiệu chỉnh đƣờng cơ sở Khi các dòng văn bản đã đƣợc xác định, các đƣờng cơ sở đƣợc điều chỉnh cho chính xác hơn bằng việc sử dụng hàm nội suy spline bậc 2. Đây là bƣớc cần thiết trƣớc nhất đối với 1 hệ thống nhận dạng OCR và nó cho phép Tesseract có thể xử lý các trang có các đƣờng cơ bản bị cong, vênh điều này rất hay xẩy ra không chỉ khi quét các quyển sách đóng gáy mà còn cả đối các dạng văn bản tài liệu khác. 8 Các đƣờng cơ bản đƣợc điều chỉnh bằng việc phân hoạch các ô ký tự thành các nhóm với một độ giãn cách liên tiếp hợp lý đối so với đƣờng cơ bản gốc ban đầu. Hàm nội suy spline bậc 2 đƣợc điều chỉnh cho phù hợp với phân vùng có nhiều ký tự nhất bởi một hàm bình phƣơng tối thiểu phù hợp. Nội suy spline bậc 2 có điểm lợi đó là việc tính toán đạt đƣợc sự ổn định một cách hợp lý. Tuy nhiên điểm yếu của nó chính là sự rời rạc có thể tăng lên khi số phân đoạn tăng. Trong trƣờng hợp này, nội suy bậc 3 sẽ cho kết quả tốt hơn. Hình 4. Minh họa về đƣờng cơ sở đã đƣợc hiệu chỉnh cong. Hình trên thể hiện một minh họa một dòng văn bản đƣợc điều chỉnh theo đƣờng cơ sở, đƣờng hạ thấp, đƣờng trung bình và đƣờng nâng cao. Tất cả các đƣờng thẳng này đều ―song song‖ với nhau. Đƣờng tăng có mầu xanh (khi in có màu xám) và đƣờng mầu đen phía trên đều là đƣờng thẳng. Khi xem kỹ hơn chúng ta thấy rằng, đƣờng mầu xanh/xám có độ vênh tƣơng đối so với đƣờng thẳng mầu đen phía trên. 2.3.3 Phát hiện khoảng cách cố định và chia cắt Tesseract thực hiện kiểm tra các dòng chữ để quyết định xem liệu có phải chúng có độ cao cố định hay không. Sau khi xác định độ cao cố định, Tesseract sẽ cắt các chữ thành các ký tự bằng việc sử dụng độ cao và rồi vô hiệu hóa bộ cắt và chuyển các chữ này sang bƣớc nhận dạng từ. Hình dƣới dây minh họa một ví dụ điển hình của một từ có khoàng cách cố định. Hình 5. Ví dụ minh họa một từ đã đƣợc cắt theo chiều cao cố định 2.3.4 Xác định các từ theo tỷ lệ 9 Việc chia tách các văn bản có dãn cách chữ mang tính tỷ lệ hoặc không, có chiều cao cố định, cũng là một tác vụ quan trọng. Hình 6 minh họa một một vài trƣờng hợp điển hình. Khoảng các giữa các hàng chục và hàng đơn vị trong chuỗi ‗11.9% ‗ có kích thƣớng tƣơng tự với các khoảng trống khác và lớn hơn khoảng giãn cách giữa chuỗi ‗erated‘ và chuỗi ‗junk‘. Một khó khăn dễ thấy nữa trong quá trình nhận dạng đó là không có khoảng cách giữa viền bao ngoài của chữ ‗of‘ và viền bao ngoài của chữ ‗finacial‘. Tuy nhiên Tesseract đã đƣợc xây dựng một cơ chế để giải quyết phần lớn những khó khăn này bằng cách đo các khoảng cách trong một vùng giới hạn theo chiều dọc giữa đƣờng cơ sở và đƣờng trung bình. Trong giai đoạn này, các khoảng cách mà gần với ngƣỡng thì đƣợc làm mờ đi, và một quyết định cuối cùng sẽ đƣợc đƣa ra sau quá trình nhận dạng từ. Hình 6. Minh họa của từ có khoảng cách khó xác định 2.4 Nhận dạng từ Một phần quan trong trong tiến trình nhận dạng của bất cứ bộ nhận dạng văn bản nào đó là xác định xem một từ đƣợc chia cắt thành các ký tự nhƣ thế nào. Bƣớc chia cắt từ thành các ký tự đƣợc thực hiện lần đầu tiên trong tiến trình xác định đƣờng thẳng và nó là bƣớc phân loại lần thứ nhất. Bƣớc còn lại của quá trình nhận dạng đƣợc thực hiện trên nhóm văn bản có chiều cao không cố định. 2.4.1 Chia cắt các ký tự dính vào nhau Khi kết quả nhận dạng một từ không thể thỏa mãn các điều kiện thì Tesseract cố gắng nâng cao kết quả bằng cách cắt gọt các ô ký tự với có độ tin cậy thấp nhất khỏi bộ phân loại ký tự. Các điểm cắt thích hợp đƣợc xác định từ 10 đỉnh lõm của một hình đa giác đƣợc xấp xỉ gần đúng với đƣờng viền ngoài của ký tự và có thể có các đỉnh lõm đối điện hoặc là một đoạn thẳng. Phải cần có tối thiểu 3 cặp đỉnh cắt để có thể tách thành công các ký tự thuộc tập ký tự ASCII. Hình 7. Ví dụ về điểm cắt thích hợp và nhát căt Hình phía trên chỉ ra tập các điểm cắt thích hợp tại vị trí các mũi tên và nhát cắt đƣợc lựa chọn là một đƣờng ngang qua đƣờng bao ngoài tại điểm ký tự ‗r‘ dính vào ký tự ‗m‗. Các nhát cắt đƣợc thực hiện theo thứ tự ƣu tiên. Bất cứ nhát cắt nào mà không cải thiện đƣợc độ tin cậy của kết quả thì sẽ đƣợc khôi phục lại, tuy nhiên nó sẽ không bị hủy bỏ hoàn toàn do vậy nhát cắt có thể đƣợc dùng lại lần sau bởi bộ ghép ký tự nếu cần thiết. 2.4.2 Ghép nối các kỹ tự bị đứt đoạn Khi các đƣờng cắt tiềm năng có quá nhiều, nếu từ vẫn chƣa đủ tốt, một bộ ghép nối sẽ đƣợc sử dụng. Bộ ghép nối sẽ thực hiện phép tìm kiếm A* (tốt nhất trƣớc) trên các thành phần đồ thị với các khả năng kết hợp lớn nhất các mảnh bị chia cắt của các ô ký tự thành một các ký tự tiềm năng. Nó thực hiện điều này mà không hề xây dựng các phân đoạn đồ thị mà thay vào đó là xây dựng một bảng băm của các vùng đã đƣợc viếng thăm. Tìm kiếm A* đƣợc bắt đầu bằng cách đƣa các thành phần ứng viên vào vùng mới từ một hàng đợi ƣu tiên và đánh giá chúng bằng việc phân lớp các sự kết hợp của các phân mảnh mà chƣa đƣợc phân loại. Có thể có lập luận cho rằng hƣớng tiếp cận liên kết sau khi đã cắt gọt là một cách làm không thực sự đem lại kết quả tối ƣu và có khả năng lớn là làm mất các nhát cắt quan trọng. Tuy nhiên mặt mạnh của phƣơng pháp này đó là làm đơn giản cấu trúc dữ liệu cần thiết để lƣu giữ đầy đủ các phân đoạn đồ thị. 11 Hình 8. Minh ho ̣a chƣ̃ bi đƣ ̣ ́ t đoa ̣n Khi giải thuật tìm kiếm dựa trên phân đoạn A* đƣợc cài đặt lần đầu vào năm 1989, Tesseract đã trở thành bộ nhận dạng các ký tự bị đƣt đoạn có đột chinh xác nội trội, vƣợt qua cả những phần mềm thƣơng mại. Hình trên là một ví dụ điển hình. Thành phần nền của sự thành công đó là bộ phân loại ký tự có thể nhận dạng dễ dàng các kí tự bị đứt đoạn. 2.5 Bộ phân loại kí tự tĩnh 2.5.1 Trích chọn đặc trƣng Phiên bản đầu tiên của Tesseract sử dụng các topo nét đặc trƣng đƣợc phát triển từ công trình nghiên cứu của Shillman. Tuy không bị phụ thuộc vào font và độ lớn, nhƣng các nét đặc trƣng không thực sự tốt trong một số trƣờng hợp thực tế nhƣ Bokser mô tả. Mộ ý tƣởng lúc đó liên quan tới việc sử dụng các phân đoạn của đa giác xấp xỉ làm đặc trƣng của ký tự, tuy nhiên phƣơng pháp này cũng không phải là tốt đối với các ký tự không nguyên vẹn. Hình 9 bên dƣới là một ví dụ đặc trƣng. Trong hình (a), phía bên phải của của nét thẳng đứng thì bao gồm 2 mảnh chính nhƣng trong hình (b) thì chỉ có 1 mảnh duy nhất. Hình 9. (a) Kí tự ‘h’ mẫu, (b) ‘h’ đứt đoạn, (c) nét đặc trƣng so với mẫu 12 Một ý tƣởng giải pháp đột phá đó là các đặc trƣng của một phần tử chƣa biết không nhất thiết phải giống với các đặc trƣng trong dữ liệu huấn luyện. Trong suốt quá trình huấn luyện, các phần của một đa giác xấp xỉ đƣợc sử dụng dụng làm các đặc trƣng, nhƣng trong quá trình nhận dạng, các đặc trƣng của một phần nhỏ, có độ dài cố định (theo đơn vị đo bình thuờng thì đƣợc tách ra từ nét phác thảo và đƣợc so sánh gép cặp một-nhiều dựa vào nhóm các mẫu đặc trƣng của kho dữ liệu huấn luyện. Trong hình 9(c), các đƣờng kẻ đứt đoạn, dầy là các đặc trƣng đƣợc trích xuất từ một đối tƣợng chƣa nhận dạng, và các đƣờng liền, mảnh là nhóm các phần cả đa giác xấp xỉ đƣợc sử dụng nhƣ là các nguyên mẫu. Ta thấy rằng một nguyên mẫu nối giữa phần bên trái và bên phải ở hình 9(c) thì hoàn toàn không đƣợc ghép cặp. Ví dụ này cho thấy quá trình xử lý khớp các đặc trƣng nhỏ vào các nguyên mẫu lớn thì có thể dễ dàng xử lý nhận dạng với các hỉnh ảnh có lỗi. Tuy vậy khó khăn chính của nó chính là chi phí tính toán cho việc tính khoảng cách giữa đối tƣợng chƣa biết với mẫu là khá lớn. Các đặc trƣng trích xuất từ các đối tƣợng là các mẫu 3 chiều (tọa độ x,y và góc). Với mỗi ký tự thì thƣờng có 50 đến 100 đặc trƣng. Các đặc trƣng của nguyên mẫu ở dạng 4 chiều, (vị trí x,y, góc, độ dài. Các nguyên mẫu thƣờng có 10-20 các đặc trƣng và đƣợc lƣu trong bảng tham số cấu hình nguyên mẫu. 2.5.2 Phân lớp Tiến trình phân phân lớp bao gồm 2 bƣớc. Trong bƣớc thứ nhất một bộ chia lớp tạo ra một danh sách đã sàng lọc các lớp ký tự mà các đối tự chƣa nhận dạng có thể khớp mẫu ký tự đó. Lẫn lƣợt mỗi một đặc trƣng lấy chọn ra từ một bảng tìm kiếm 3 chiều đã đƣợc lƣợng tử hóa, 1 bit-vector của các lớp mà nó có thể khớp và các bit-vector sẽ đƣợc tính tổng trên toàn bộ các đặc trƣng. Các lớp có số lần khớp cao nhất (sau khi đã điều chỉnh lại số lƣợng các đặc trƣng mong muốn) sẽ đƣợc đƣa vào danh sách tiềm năng cho bƣớc tiếp theo. Mỗi đặc trƣng của đối tƣợng chƣa biết sẽ tìm kiếm một bit-vector của nguyên mẫu trong lớp đƣa danh mà nó có thể khớp và sau đó sự giống nhau giữa chúng sẽ đƣợc tính toán. Mỗi lớp ký tự nguyên mẫu đƣợc thể hiện với một biểu thức lôgic tổng của các tích với các số hạng đƣợc gọi là cấu hình, do đó tiến