ĐẠ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