Luận văn Nhận dạng chữ viết và phân tích trang tài liệu

Luận văn

Nhận dạng chữ viết và phân

tích trang tài liệu

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Mục lục

M ụ c l ụ c ........................................................................................................................i

Danh m ụ c các hình ả nh ..............................................................................................i v

M Ở ĐẦ U .................................................................................................................... 1

I. Đặ t v ấn đề ........................................................................................................1

II. N ộ i dung nghiên c ứ u .......................................................................................2

III. B ố c ụ c c ủ a lu ận vă n .......................................................................................4

Ch ƣơ ng I. T Ổ NG QUAN V Ề NH Ậ N D Ạ NG CH Ữ VI Ế T ........................................... 5

VÀ PHÂN TÍCH TRANG TÀI LI Ệ U ......................................................................... 5

I.1. Ả nh tài li ệ u và nh ậ n d ạ ng ả nh tài li ệ u ............................................................5

I.1.1. T ổ ng quan v ề ả nh tài li ệ u........................................................................5

I.1.2. Nh ậ n d ạ ng tài li ệ u và vai trò c ủ a phân tích ả nh tài li ệ u ...........................6

I.2. C ấ u trúc c ủ a ả nh tài li ệ u ................................................................................7

I.2.1. C ấ u trúc v ậ t lý ........................................................................................8

I.2.2. C ấ u trúc logic .......................................................................................1 0

I.3. Quá trình phân tích tài li ệ u ..........................................................................1 0

I.3.1. Ti ề n x ử lý(preprocessing): ....................................................................1 1

I.3.2. Phân tích c ấ u trúc v ậ t lý........................................................................1 2

I.3.3. Phân tích c ấ u trúc logic.........................................................................1 3

I.4. M ộ t s ố h ệ th ố ng phân tích tài li ệ u hi ệ n nay..................................................1 4

I.4.1. VnDOCR..............................................................................................1 4

I.4.2. OminiPag e ............................................................................................1 8

I.4.3. Finereader.............................................................................................2 0

I.5. K ế t lu ậ n.......................................................................................................2 2

Ch ƣơ ng II: CÁC PH ƢƠ NG PHÁP TI Ế P C Ậ N ......................................................... 23

ĐỂ PHÂN TÍCH TRANG TÀI LI Ệ U ........................................................................ 23

II.1. Các ph ƣơng pháp phân tích đị nh d ạ ng trang tài li ệ u ...................................2 3

II.1.1. Top-down............................................................................................2 3

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

i

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

II.1.2. Bottom-up ...........................................................................................3 0

II.1.3. Ph ƣơ ng pháp Tách và N ố i thích nghi (Adaptive Split – and – Merge) .3 2

II.1.4. Fractal Signature (FS)..........................................................................3 4

II.2. L ự a ch ọ n gi ả i pháp.....................................................................................3 8

II.3. Thi ế t k ế h ệ th ố ng........................................................................................3 9

II.3.1. S ơ đ ồ kh ố i ...........................................................................................3 9

II.3.2. Ảnh đầ u vào ........................................................................................3 9

II.3.3. Module Ti ề n x ử lý...............................................................................4 0

II.3.4. Phân tích s ử d ụ ng gi ả pháp Fractal Signature ......................................4 1

II.4. K ế t lu ậ n .....................................................................................................4 5

Ch ƣơ ng III: XÂY D Ự NG CH ƢƠ NG TRÌNH TH Ử NGHI Ệ M .................................. 46

III.1. Yêu c ầ u h ệ th ố ng .....................................................................................4 6

III.2. Thi ế t k ế ch ƣơ ng trình................................................................................4 6

III.2.1. C ấ u trúc d ữ li ệ u..................................................................................4 6

III.2.2. Module chu ẩ n hóa ả nh .......................................................................4 8

III.2.3. Module giao di ệ n chính......................................................................5 1

III.2.4. Module phân tích Top-down (TD)......................................................5 2

III.2.5. Module phân tích Fractal Signatur e ....................................................5 5

III.2.6. Module l ọ c và làm tr ơ n nhi ễ u.............................................................5 7

III.2.7. Module mô ph ỏ ng thu ậ t toán FS ........................................................5 8

III.2.8. Các hàm ch ức năng chính củ a image processing tool trong matlab s ử

d ụ ng trong ch ƣơ ng trình ................................................................................6 0

III.3. K ế t lu ận và đánh giá kế t qu ả .....................................................................6 2

K ế t lu ậ n..................................................................................................................... 83

TÀI LI Ệ U THAM KH Ả O ......................................................................................... 84

Ph ụ c L ụ c ................................................................................................................... 85

A. Mã ngu ồn đầy đủ c ủ a ch ƣơ ng trìn h ...............................................................8 5

A.1. Danh m ụ c các ch ƣơ ng trình con trong ch ƣơ ng trìn h ...............................8 5

A.2. S ơ kh ố i liên k ế t gi ữ a các th ủ t ụ c trong ch ƣơ ng trình...............................8 6

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

ii

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

A.3. Mã ngu ồ n các module ............................................................................8 6

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

iii

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Danh mục các hình ảnh

Hình 1: S ơ đồ t ổ ng quan quá trình t ạ o ả nh tài li ệ u ...................................................5

Hình 2: Ví d ụ ả nh tài li ệ u ........................................................................................6

Hình 3: S ơ đồ OCR c ơ b ả n ......................................................................................7

Hình 4: b-C ấ u trúc v ậ t lý: c,d-C ấ u trúc logic c ủ a m ộ t tài li ệ u[4 ]..............................9

Hình 5: Ví d ụ lo ạ i tài li ệ u có b ố c ụ c ph ứ c ta p ........................................................1 0

Hình 6: S ơ đồ nguyên lý h ệ th ố ng x ử lý tài li ệ u[6] ................................................1 1

Hình 7: a - Ả nh g ố c b - Ả nh sau khi tách n ề n ........................................................1 2

Hình 8: Ví d ụ m ộ t ả nh tài li ệ u b ị nghiêng m ột góc 5 độ .........................................1 3

Hình 9: Ví d ụ m ộ t cây mô t ả c ấ u trúc logic c ủ a m ộ t trang tài li ệ u[5] .....................1 4

Hình 10: VnDOCR và m ộ t ví d ụ nh ậ n d ạ ng ..........................................................1 5

Hình 11: Ả nh m ẫ u có c ấ u trúc v ậ t lý ph ứ c t ạ p .......................................................1 6

Hình 12: K ế t qu ả ra hai vùng ả nh v ớ i ả nh m ẫ u 11 .................................................1 6

Hình 13: M ẫ u ả nh có c ấ u trúc v ậ t lý ph ứ c t ạ p, nh ƣ ng các kh ố i bao b ở i hình ch ữ nh ậ t

..............................................................................................................................1 7

Hình 14: K ế t qu ả phân tích v ớ i ả nh 13...................................................................1 8

Hình 15: Đầ u ra phân vùng ch ỉ có 1 vùng văn bả n.................................................1 9

Hình 16: Đầ u ra có vùng ch ứ a c ả ả nh và tex t .........................................................1 9

Hình 17: V ớ i ảnh 13 đạ t hi ệ u qu ả 90 %..................................................................2 0

Hình 18 V ớ i ả nh I-15 hi ệ u qu ả đạ t 100%...............................................................2 1

Hình 19: V ớ i m ẫ u ph ứ c t ạ p h ơ n Finereader cho k ế t qu ả 95% ................................2 2

Hình 20: K ế t qu ả chi ế u nghiêng theo ph ƣơ ng ngang và ph ƣơ ng th ẳng đứ ng c ủ a m ộ t

trang tài li ệ u ..........................................................................................................2 4

Hình 21: Phân tách c ộ t d ự a vào phép chi ế u nghiêng theo ph ƣơ ng ngang ...............2 5

Hình 22: Phép chi ế u nghiêng theo ph ƣơng ngang để phân đoạ n ký t ự ho ặ c t ừ .......2 6

Hình 23: L ƣợc đồ chi ế u ngang c ủ a m ộ t dòng ch ữ nghiêng - r ất khó phân đoạ n ký t ự

..............................................................................................................................2 7

Hình 24: L ƣợc đồ chi ếu đứ ng c ủ a trang tài li ệ u b ị nghiêng....................................2 8

Hình 25: L ƣợc đồ chi ếu đứ ng c ủ a m ộ t bài báo.......................................................2 9

Hình 26: Ph ƣơng pháp Dostrum cho phân tích đị nh d ạ ng trang t ừ d ƣớ i lên. (a) M ộ t

ph ầ n c ủ a n ội dung văn bả n g ố c. (b) Các thành ph ầ n lân c ậ n g ầ n nh ất đƣợc xác đị nh.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

iv

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

(c) Các hình chữ nhật tối thiểu tạo nên nhóm láng giềng gần nhất từ đó xác định

đƣợc dòng văn bản. ...............................................................................................31

Hình 27: Mô t ả thu ậ t toán Tách và N ố i thích nghi .................................................3 3

Hình 28: Mô t ả thu ậ t toán FS.................................................................................3 5

Hình 29: S ơ đồ kh ố i h ệ th ố ng phân tích tài li ệ u trong ph ạm vi đề tài .....................3 9

Hình 30: Ví d ụ m ộ t bolck chuy ể n sang d ạ ng b ề m ặ t trong không gian 3 D .............4 1

Hình 31: Ví d ụ chuy ể n ả nh ch ữ "c" sang d ạ ng b ề m ặ t trong không gian 3D .........4 1

Hình 32: (a) Ả nh m ộ t tài li ệ u g ố c, (b) k ế t qu ả sau khi áp d ụ ng F S .........................4 4

Hình 33: Giao di ệ n chính.......................................................................................5 1

Hình 34: K ế t qu ả phân tích c ủ a top-down trên tài li ệ u có c ấu trúc đơ n gi ả n...........63

Hình 35: K ế t qu ả phân tích c ủ a top-down trên tài li ệ u có c ấ u trúc b ả ng.................6 5

Hình 36: : K ế t qu ả phân tích c ủ a top-down trên tài li ệ u thu ần văn bả n...................6 7

Hình 37: : K ế t qu ả phân tích c ủ a top-down trên tài li ệ u có c ấ u trúc ph ứ c t ạ p (trang

t ạ p trí)....................................................................................................................6 9

Hình 38 : K ế t qu ả phân tích c ủ a top-down trên m ộ t t ờ qu ả ng cáo ..........................7 1

Hình 39: K ế t qu ả phân tích c ủ a top-down trên tài li ệ u có c ấ u trúc ph ứ c t ạ p ...........73

Hình 40: K ế t qu ả phân tích c ủ a top-down trên tài li ệ u b ị nghiêng.........................7 5

Hình 41: K ế t qu ả phân tích c ủ a FS trên tài li ệ u b ị nghiêng ....................................7 7

Hình 42: K ế t qu ả phân tích c ủ a FS trên tài có c ấ u trúc ph ứ c t ạ p ............................7 9

Hình 43: K ế t qu ả phân tích c ủ a FS trên m ộ t trang qu ả ng cáo.................................8 1

Hình 44: K ế t qu ả phân tích c ủ a FS trên tài li ệu đơ n gi ả n .......................................8 2

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

v

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

MỞ ĐẦU

I. Đặt vấn đề

Ngày nay việc sử dụng máy tính để lƣu trữ tài liệu không còn là vấn đề mới

mẻ và cần phải chứng minh tính an toàn, thuận tiện của nó. Tuy nhiên việc sử dụng

giấy để lƣu trữ tài liệu trong một số mục đích vẫn không thể thay thế đƣợc (nhƣ

báo, sách, công văn,…). Hơn nữa lƣợng tài liệu đƣợc tạo ra từ nhiều năm trƣớc vẫn

còn rất nhiều mà không thể bỏ đi đƣợc vì tính quan trọng của chúng.

Chúng ta mong muốn có thể điện tử hóa hàng tỉ trang tài liệu đó và cất chúng

chỉ trong một ổ cứng kích thƣớc bằng một cuốn sách nhỏ, tìm kiếm thông tin mà chỉ

cần tốn vài giây với một cái gõ phím Enter. Giải pháp là gì?

Thông thƣờng ngƣời ta sẽ phải thuê ngƣời cùng với việc tốn hàng tháng,

hàng năm mới có thể nhập vào máy tính đƣợc hết lƣợng tài liệu đó. Hiện nay chúng

ta đã có các máy Scan với tốc độ cao, công nghệ xử lý của máy tính ngày càng siêu

việt với tốc độ tính toán vƣợt cả tốc độ ánh sáng, vậy tại sao chúng ta không quét

toàn bộ các trang tài liệu vào và chuyển chúng thành văn bản một cách tự động?

Bằng cách đó tốc độ và tính chính xác sẽ tăng hàng trăm lần trong khi chi phí

lại là cực tiểu. Vấn đề là khi quét vào máy tính chúng ta không thu đƣợc ngay các

dòng văn bản từ các trang tài liệu kia, để có thể soạn thảo, sửa chữa và tìm kiếm

nhƣ làm trên Office. Tất cả những gì thu đƣợc chỉ là các tấm ảnh của các trang văn

bản, máy tính lại đối xử công bằng nhƣ nhau với mọi điểm ảnh, máy tính không có

“mắt” nhƣ chúng ta để biết đâu là điểm ảnh của chữ, đâu là điểm ảnh của đối tƣợng

đồ họa.

Một giải pháp đƣợc nghĩ đến ngay đó là đó là xây dựng các hệ thống nhận

dạng chữ, trong tấm ảnh chứa cả chữ và đối tƣợng đồ họa cần tách và chuyển thành

dạng trang văn bản, từ đó có thể mở và soạn thảo đƣợc trên các trình soạn thảo văn

bản.

Một cách tổng quát thì cách thức làm việc của một hệ thống nhận dạng chữ

nhƣ sau[5]:

1. Chụp ảnh các trang tài liệu trên giấy và lƣu lại trong máy tính dƣới dạng hình

ảnh.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

1

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

2. Sử dụng một chƣơng trình xử lý ảnh để phân tích hình ảnh sau khi quét, đọc

đƣợc ký tự trên hình ảnh đó và ghi lại vào máy tính theo cách mà máy tính

quản lý đƣợc thông tin dữ liệu đó.

a. Bƣớc 1 là phân tích cấu trúc của ảnh tài liệu, từ đó xác định đâu là

phần chứa chữ, đâu là phần chứa cả ảnh lẫn ký tự và đâu chỉ chứa

hình ảnh. Bƣớc này thực sự quan trọng cho bƣớc nhận dạng. Bởi nó

định vị chính xác cho việc áp dụng các thuật toán nhận dạng lên vùng

đã xác định tính chất, nếu bƣớc này chính xác trƣớc tiên nó hạn chế

thời gian cho việc nhận dạng, sau là tăng ngữ nghĩa bổ sung cho việc

nhận dạng.

b. Bƣớc 2 nhận dạng ký tự dựa vào các tính chất của ký tự, ví dụ nhƣ sắp

xếp theo dòng, khoảng cách giữa 2 từ lớn hơn khoảng cách giữa 2 ký

tự, dùng trí tuệ nhân tạo để dự đoán các ký tự kề nhau phải nhƣ thế

nào, các từ trong câu phải nhƣ thế nào để câu có nghĩa. Từ đó có nội

dung đúng để lƣu trữ, quản lý….

Trong thực tế không phải quá trình nhận dạng nào cũng chỉ trải qua hai bƣớc

nhƣ trên, bởi vì có rất nhiều tham số ảnh hƣởng đến kết quả của các chƣơng trình

nhận dạng, nhƣ nhiễu, Font chữ, kích thƣớc chữ, kiểu chữ nghiêng, đậm, gạch dƣới.

Ngoài ra các dòng chữ cũng có thể trộn lẫn với các đối tƣợng đồ họa, vì thế trƣớc

khi nhận dạng chữ, một số thao tác tiền xử lý sẽ đƣợc tác động lên ảnh nhƣ, lọc

nhiễu, chỉnh góc nghiêng và đặc biệt quan trọng là phân tích trang tài liệu để xác

định cấu trúc của trang văn bản đồng thời tách biệt hai thành phần là chữ và các đối

tƣợng đồ họa (phi chữ).

II. Nội dung nghiên cứu

1. Mục tiêu nghiên cứu chính của đề tài

 Tìm hiểu cấu trúc trang tài liệu (cấu trúc vật lý, logic)?

 Tìm hiểu một số kỹ thuật phân tích trang tài liệu (phân vùng, phân

đoạn,…)

 Cài đặt thử nghiệm một giải pháp phân tích có hiệu quả cao so với các

phƣơng pháp truyền thống nhƣ top-down hay bottom-up trên ảnh vào là

ảnh đa cấp xám có cấu trúc phức tạp.

 Từ kết quả nghiên cứu có một sự chuẩn bị kiến thức đẩy đủ cho bƣớc

nghiên cứu tiếp theo là nhận dạng ký tự quang.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

2

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

2. Ý nghĩa khoa học của đề tài

 Giải quyết đƣợc vấn đề về học thuật: đề tài sẽ mang ý nghĩa cung cấp về

mặt lý thuyết để làm rõ về các phƣơng pháp phân tích trang tài liệu.

 Đáp ứng đƣợc yêu cầu của thực tiễn: từ các lý thuyết đã đƣợc nghiên cứu,

từ đó liên hệ và gắn vào thực tiễn để có thể áp dụng vào các lĩnh vực

nhƣ: Lƣu trữ thƣ viện, điện tử hóa văn phòng, nhận dạng và xử lý ảnh, …

3. Nhiệm vụ nghiên cứu

Mục đích của luận văn đề cập đƣợc đến hai phần:

 Phần lý thuyết: Nắm rõ và trình bày những cơ sở lý thuyết liên quan đến

cấu trúc trang tài liệu, một số kỹ thuật phân tích trang tài liệu, từ đó có để

có thể xác định tính quan trọng của bƣớc này trong nhận dạng ký tự, đồng

thời hiểu các công việc kế tiếp cần làm trong bƣớc nhận dạng ký tự.

 Phần phát triển ứng dụng: Áp dụng các thuật toán đã trình bày ở phần lý

thuyết từ đó lựa chọn một giải pháp tối ƣu và cài đặt thử nghiệm chƣơng

trình phân tích trang tài liệu.

4. Phƣơng pháp nghiên cứu

 Tìm kiếm, tham khảo, tổng hợp tài liệu từ các nguồn khác nhau để xây

dựng phần lý thuyết cho luận văn.

 Sử dụng các kỹ thuật đƣợc áp dụng phân tích trang tài liệu để làm rõ bản

chất của các vấn đề đƣợc đƣa ra trong phần lý thuyết.

 Xây dựng chƣơng trình Demo.

5. Phạm vi nghiên cứu

Bài toán nhận dạng và xử lý ảnh tài liệu đã đƣợc phát triển với nhiều thành tựu

trong thực tế, có rất nhiều thuật toán tối ƣu đã đƣợc các nhà khoa học đề nghị. Tuy

nhiên có thể nói chƣa có một chƣơng trình nào có thể “đọc” một ảnh văn bản nhƣ

con ngƣời, vì thực tế có rất nhiều kiểu trang văn bản khác nhau, khác nhau về cấu

trúc trình bày, ngôn ngữ, kiểu font, chữ viết tay,… Đây thực sự là một bài toán lớn,

chính vì thế trong phạm vi của luận văn chỉ tìm hiểu một số kỹ thuật phân tích trang

văn bản tiêu biểu với mục đích để so sánh và một thuật toán mới chƣa đƣợc đƣa ra

ở các đề tài trƣớc. Cuối cùng, dựa vào đó để xây dựng Demo cho một ứng dụng.

Các kết quả nghiên cứu dự kiến cần đạt đƣợc:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

3

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

 Tìm hiểu tài liệu liên quan đến lĩnh vực quan tâm để nắm bắt đƣợc bản

chất vấn đề đặt ra.

 Báo cáo lý thuyết

 Chƣơng trình Demo.

III. Bố cục của luận văn

Nội dung của luận văn đƣợc trình bày trong ba chƣơng với nội dung chính

sau.

Chƣơng 1: Trình bày các khái niệm và mô hình tổng quát của hệ thống nhận dạng

chữ viết, cùng với một số phần mềm nhận dạng tiêu biểu hiện nay.

Chƣơng 2: Trình bày một số phƣơng pháp phân tích trang tài liệu, từ đó đánh giá

ƣu nhƣợc điểm để lựa chọn phƣơng pháp Fractal Signature cho chƣơng trình thử

nghiệm. Trình bày về thiết kế cho chƣơng trình demo.

Chƣơng 3: Trình bày chi tiết về việc cài đặt chƣơng trình cũng nhƣ các thủ tục sử

dụng trong chƣơng trình với phƣơng pháp phân tích Fractal Signature và ảnh đầu

vào

là

ảnh

đa

cấp

xám

có

độ

phức

tạp

cao.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

4

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Chƣơng I. TỔNG QUAN VỀ NHẬN DẠNG CHỮ VIẾT

VÀ PHÂN TÍCH TRANG TÀI LIỆU

Chƣơng này đƣa ra các khái niệm về đối tƣợng làm việc của đề tài là ảnh tài

liệu, khái niệm về cấu trúc vật lý và cấu trúc logic. Giới thiệu các khâu trong một hệ

thống nhận dạng chữ viết hoàn chỉnh. Đồng thời đƣa ra một số phần mềm nhận

dạng của Việt Nam và Thế giới cùng với các mẫu kết quả phân tích của nó nhàm

mục đích so sánh và xác định phạm vi cho đề tài.

I.1. Ảnh tài liệu và nhận dạng ảnh tài liệu

I.1.1. Tổng quan về ảnh tài liệu

Trang ảnh tài liệu đƣợc đề cập ở đây là các file ảnh số hoá thu đƣợc bằng

cách quét các trang tài liệu dùng máy scanner, máy ảnh số, hay nhận từ một máy fax

(Hình 1), file ảnh này đƣợc lƣu giữ trong máy tính. Ảnh tài liệu có nhiều loại: ảnh

đen trắng, ảnh màu, ảnh đa cấp xám với các phần mở rộng nhƣ TIF, BMP, PCX,

…(Hình 2) và ảnh tài liệu đƣợc đƣa ra trong luận văn này là ảnh đa cấp xám.

Ảnh số

Tài liệu

Thiết bị thu nhận ảnh

Anh số tài liệu

Hình 1: Sơ đồ tổng quan quá trình tạo ảnh tài liệu

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

5

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 2: Ví dụ ảnh tài liệu

I.1.2. Nhận dạng tài liệu và vai trò của phân tích ảnh tài liệu

Ngày nay, máy tính đang phát triển mạnh mẽ, tốc độ xử lý không ngừng

đƣợc nâng lên. Cùng với nó là sự ra đời của các phần mềm thông minh đã khiến

máy tính ngày một gần gũi với con ngƣời hơn. Một trong các khả năng tuyệt vời

của con ngƣời mà các nhà khoa học máy tính muốn đạt đƣợc đó là khả năng nhận

dạng và lĩnh vực nhận dạng thu đƣợc nhiều thành công nhất là nhận dạng ký tự

quang OCR–Optical Character Recognition. OCR có thể đƣợc hiểu là quá trình

chuyển đổi tài liệu dƣới dạng file ảnh số hoá (là dạng chỉ có ngƣời đọc đƣợc) thành

tài liệu dƣới dạng file văn bản (là tài liệu mà cả ngƣời và máy đều có thể đọc đƣợc).

OCR có rất nhiều ứng dụng hữu ích trong cuộc sống nhƣ:

- Sắp xếp thƣ tín, dựa vào việc nhận dạng mã bƣu chính (Zipcode) hay địa

chỉ gửi tới.

- Tự động thu thập dữ liệu từ các mẫu đơn/báo biểu hay từ các hồ sơ lao

động.

- Hệ thống tự động kiểm tra trong ngân hàng (tự động xác nhận chữ ký)

- Tự động xử lý các hóa đơn hay các yêu cầu thanh toán

- Hệ thống tự động đọc và kiểm tra passport

- Tự động phục hồi và copy tài liệu từ các ảnh quét.

- Máy đọc cho những ngƣời khiếm thính

- Các ứng dụng Datamining

- …

Sơ đồ một hệ thống OCR cơ bản ở Hình 3.

Trong đó:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

6

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

- Scanner: Thiết bị quét ảnh

- OCR hardware/software:

o Document analysis: Phân tích tài liệu

o Character recognition: Nhận dạng ký tự

o Contexttual processor: Xử lý văn cảnh

- Output interface: Đầu ra

 Nhƣ vậy vai trò chính của khâu phân tích ảnh tài liệu là việc phân đoạn trang,

tách vùng văn bản ra khỏi nền và đồ họa tạo mẫu chuẩn cho khâu nhận dạng. Rõ

dàng là kết quả của khâu phân tích này ảnh hƣởng rất lớn đến hiệu của của khâu

nhận dạng nếu sử dụng mẫu hay các chuỗi văn bản đầu ra của nó.

Hình 3: Sơ đồ OCR cơ bản

I.2. Cấu trúc của ảnh tài liệu

Một khái niệm mấu chốt trong xử lý tài liệu đó là cấu trúc của tài liệu. Cấu

trúc tài liệu thu đƣợc từ việc liên tiếp chia nhỏ nội dung của tài liệu thành các phần

nhỏ đơn vị (tức không thể phân chia đƣợc nữa) và chúng đƣợc gọi là các đối tƣợng

cơ sở (basic objects). Còn tất cả các đối tƣợng khác đƣợc gọi là các đối tƣợng hỗn

hợp.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

7

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Có hai loại cấu trúc của tài liệu đƣợc quan tâm ở đây đó là cấu trúc vật lý

(hay bố cục vật lý) và cấu trúc logic mô tả mối quan hệ logic giữa các vùng đối

tƣợng trong tài liệu.

I.2.1. Cấu trúc vật lý

Bố cục vật lý của một tài liệu mô tả vị trí và các đƣờng danh giới giữa các

vùng có nội dung khác nhau trong một trang tài liệu[6]. Quá trình phân tích bố cục

tài liệu là thực hiện việc tách từ một trang tài liệu ban đầu thành các vùng có nội

dung cơ sở nhƣ hình ảnh nền, vùng văn bản,…

Để mô tả bố cục vật lý của tài liệu ngƣời ta sử dụng một cấu trúc hình học

với mỗi đối tƣợng trong cấu trúc là một phần tử chỉ chứa nội dung đồng nhất. Các

kiểu đối tƣợng hình học đƣợc định nghĩa nhƣ sau[4]:

 Block là đối tƣợng cơ sở tƣơng ứng với một vùng hình chữ nhật chứa một phần

nội dụng của tài liệu.

 Frame một đối tƣợng hỗn hợp tƣơng ứng với một hình chữ nhật bao gồm một

hoặc nhiều block hoặc bao gồm các frame.

 Page là đối tƣợng hình học hoặc hỗn hợp các thành phần cơ sở tƣơng ứng với

một vùng hình chữ nhật, nếu là đối tƣợng hỗn hợp nó chứa một hoặc nhiều

block, một hoặc nhiều frame.

 Page set (tập trang) là một tập của một hoặc nhiều page.

 Điểm gốc của cấu trúc (hay nút gốc) là một đối tƣợng ở mức cao nhất trong sơ

đồ phân cấp của cấu trúc hình học tài liệu. Hình 4(b) cho ví dụ một cấu trúc hình

học mô tả bố cục vật lý của trang tài liệu tƣơng ứng.

Các thuật toán phân tích bố cục tài liệu có thể đƣợc chia làm ba loại chính

dựa theo phƣơng pháp thực hiện của nó.

- Bottom-up: Ý tƣởng chính của các thuật toán loại này là bắt đầu từ những

phần tử nhỏ nhất (nhƣ từ các pixel hay các phần tử liên thông) sau đó liên

tục nhóm chúng lại thành các vùng lớn hơn.

- Top-down: Thuật toán này bắt đầu từ vùng lớn nhất chứa cả trang tài liệu

sau đó liên tục phân chia thành các vùng nhỏ hơn.

- Các thuật toán không theo thứ bậc: nhƣ Fractal Signature, Adaptive split-

and-merge …

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

8

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 4: b-Cấu trúc vật lý: c,d-Cấu trúc logic của một tài liệu[4]

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

9

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

I.2.2. Cấu trúc logic

Ngoài bố cục vật lý, các trang tài liệu còn chứa đựng nhiều thông tin về ngữ cảnh

và nội dung nhƣ các tiêu đề, đoạn văn, đề mục, …và mỗi vùng nội dung này lại đƣợc gán

các nhãn logic hay nhãn theo chức năng tƣơng ứng, khác biệt hoàn toàn với các nhãn

trong bố cục vật lý. Hầu hết các tài liệu đều có một quy tắc đọc để có thể hiểu hết nội

dung của tài liệu. Với một số ngôn ngữ đặc biệt nhƣ tiếng Trung, tiếng Ả rập lại có quy

cách đọc khác biệt (nhƣ đọc từ phải qua trái, trên xuống). Tập hợp tất cả các yếu tố logic

và chức năng trong một tài liệu và mối quan hệ giữa chúng đƣợc gọi là cấu trúc logic của

tài liệu[6]. Thông thƣờng pha phân tích cấu trúc logic của tài liệu đƣợc thực hiện trên kết

quả của bƣớc phân tích bố cục vật lý. Tuy nhiên với một số loại tài liệu phức tạp, thì pha

phân tích bố cục vật lý lại cần thêm một số thông tin logic liên quan đến các vùng để có

thể phân đoạn một cách chính xác. Hình 4(c,d) mô tả một ví dụ cấu trúc logic của tài liệu.

I.3. Quá trình phân tích tài liệu

Ảnh tài liệu chứa rất nhiều loại vùng thông tin khác nhau nhƣ các block, lines,

words, figures, tables và background. Ta có thể gọi các vùng này theo chức năng của nó

trong tài liệu hoặc gán cho nó các nhãn logic nhƣ sentences, titles, captions, address,…

Quá trình phân tích tài liệu là thực hiện việc tách một tài liệu thành các vùng theo một

tiêu chuẩn hay mối quan hệ lẫn nhau nào đấy. Công việc này đƣợc thực hiện qua nhiều

bƣớc nhƣ tiền xử lý, tách vùng, lặp cấu trúc tài liệu,…

Một số loại tài liệu nhƣ báo, tạp chí, sách quảng cáo, chúng có cấu trúc và bố cục

rất phức tạp và không có một form chung nào cả (Hình 5). Với con ngƣời để có thể đọc

hiểu đƣợc một trang tài liệu còn cần thêm nhiều kiến thức bổ sung nhƣ ngôn ngữ, hoàn

cảnh, các luật ngầm định, vì thế việc tự động phân tích các trang tài liệu một cách tổng

quát là một việc rất khó khăn thậm chí là không khả thi ngay cả với các hệ thống phân

tích tài liệu tiên tiến nhất[6].

Hình 5: Ví dụ loại tài liệu có bố cục phức tap

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

10

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Sơ đồ nguyên lý của một hệ thống tự động phân tích tài liệu nhƣ sau:

Hình 6: Sơ đồ nguyên lý hệ thống xử lý tài liệu[6]

I.3.1. Tiền xử lý(preprocessing):

Hầu hết các ảnh tài liệu đều có nhiễu do quá trình thu nhận ảnh gây ra (môi

trƣờng, chất lƣợng máy quét), vì thế trong quá trình xây dựng các thuật toán phân tích

cần loại bỏ các nhiễu này và công việc này thƣờng đƣợc tiến hành trƣớc khi bắt đầu phân

tích bố cục hay cấu trúc và gọi là Tiền xử lý. Nhiệm vụ chính của bƣớc này là loại bỏ

nhiễu, tách nền ra khỏi nội dung, phát hiện và xoay góc nghiêng,…

 Lọc nhiễu(noise removal):

Nhiễu luôn là một vấn đề trong hầu hết các bài toán đọc hiểu tài liệu. Nhiễu sinh

ra không chỉ do quá trình scan ảnh mà còn bao gồm cả các nhiễu trắng gây ra từ chính

sensor hay các mạch thu nhận trong các máy thu nhận ảnh số. Nhiễu có thể đƣợc loại bớt

sử dụng một số các kỹ thuật nhƣ lọc trung bình, lọc trung vị, lọc thông thấp,…

 Tách nền (Background separation):

Đây là một vấn đề rất quan trọng ảnh hƣởng trực tiếp đến hiệu quả của các thuật

toán phân tích tài liệu. Nếu đối với các loại tài liệu có nền đồng nhất màu trắng hoặc đen

thì việc tách có thể thực hiện đơn giản bằng phép phân ngƣỡng, tuy nhiên trong thực tế

rất nhiều ảnh tài liệu có nền rất phức tạp nhƣ ảnh hay đồ họa (Hình 7) thì việc xác định

các pixell nào thực sự thuộc về “phần nổi” là một công việc khó khăn.

Ta có thể tách nền bằng một số kỹ thuật nhƣ sau:

- Gán mỗi điểm ảnh vào “phần nổi” hay phần nền dựa theo một tiêu chí nào đấy

(nhƣ ngƣỡng mức xám, …)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

11

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

- Dựa theo độ đo xác suất xuất hiện của mỗi điểm ảnh mà phân lớp nó vào nền

hay phần nổi

- Dựa vào các pixel liên thông kết hợp với mạng noron để phân tách.

Hình 7: a - Ảnh gốc b - Ảnh sau khi tách nền

 Xác định góc nghiêng:

Do quá trình thu nhận ảnh (nhƣ đặt lệch tài liệu khi scan,…) ảnh tài liệu thu đƣợc

rất có thể bị nghiêng, tức trục của các dòng văn bản không song song với trục ngang

(Hình 8). Việc xác định đƣợc góc nghiêng và xoay lại tài liệu là một khâu rất quan trọng

ảnh hƣởng đến hiệu quả trong một số thuật toán phân tích. Ví dụ nhƣ các thuật toán dựa

theo biểu đồ sau phép chiếu nghiêng để tiến hành phân tích thì sẽ hoàn toàn thất bại nếu

văn bản bị nghiêng. Tuy nhiên việc có thể tự động ƣớc lƣợng đƣợc chính xác góc

nghiêng của ảnh tài liệu là một bài toán khó.

Có nhiều kỹ thuật để có thể xác định đƣợc góc nghiêng của tài liệu, điểm chung

trong hầu hết các thuật toán là xác định góc nghiêng bằng việc xác định hƣớng của các

dòng văn bản dựa vào vị trí một số ký tự trong tài liệu.

I.3.2. Phân tích cấu trúc vật lý

Phân tích tài liệu đƣợc định nghĩa là quá trình xác định cấu trúc vật lý của một tài

liệu. Trong khâu này thì từ một ảnh tài liệu đầu vào sẽ đƣợc chia thành một số khối

(block) chứa các nội dung thành phần của tài liệu nhƣ các dòng văn bản, tiêu đề, đồ

họa,... cùng với có hoặc không các tri thức biết trƣớc về định dạng của nó[6].

Có một số phƣơng pháp phân tích và đƣợc phân ra làm hai loại nhƣ sau:

 Các phƣơng thức có thứ bậc: Trong quá trình chia tài liệu thành các block

chúng ta quan tâm đến mối quan hệ về mặt hình học giữa các block. Có ba

phƣơng pháp thuộc loại này là:

o Phân tích top-down (trên xuống)

o Phân tích buttom-up (dƣới lên)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

12

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

o Phân tích kiểu Adaptive split-and-merge (tách và nối thích nghi)

 Các phƣơng pháp không có thứ bậc: Trong quá trình chia tài liệu thành các

khối chúng ta không quan tâm đến mối quan hệ hình học giữa các block.

Hình 8: Ví dụ một ảnh tài liệu bị nghiêng một góc 5 độ

I.3.3. Phân tích cấu trúc logic

Từ kết quả của pha phân tích cấu trúc vật lý, phân tích cấu trúc logic sẽ đi xác

định mối quan hệ logic giữa các vùng đã đƣợc gắn nhãn nhƣ tiêu đề, văn bản, đề mục,

hearder,… Bƣớc này là cơ sở cho việc nhận dạng ký tự.

- Việc xác định đƣợc vị trí chính xác của mỗi vùng trong cấu trúc logic sẽ tăng

thêm thông tin cho quá trình nhận dạng nhƣ thông tin về ngữ cảnh, đoán nhận

đƣợc kiểu font và kích thƣớc chữ nếu biết nó thuộc vùng tiêu đề, đề mục hay

trong đoạn văn,… (Hình 9)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

13

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

document(page)

article(page)

abstract

article(page)

sub-title

paragraphs

Hình 9: Ví dụ một cây mô tả cấu trúc logic của một trang tài liệu[5]

I.4. Một số hệ thống phân tích tài liệu hiện nay

I.4.1. VnDOCR

Vndocr phần mềm nhận dạng tiếng Việt là một sản phẩm của Viện công Nghệ

thông tin. VnDOCR thu thập thông tin nhờ quá trình quét các loại sách báo thông qua

máy quét thành các tệp ảnh và chuyển đổi thành các tệp có định dạng *.doc, *.xls, *.txt,

*.rtf,... có thể đọc và chỉnh sửa đƣợc trên các phần mềm soạn thảo văn bản thông dụng

nhƣ Office, Wordpad,… (Hình 10)

Môi trƣờng

 PC với hệ điều hành Windows 9x, ME, 2000, XP, NT,… Tiện ích: Bộ gõ chữ Việt,

bộ font ABC, VNI, Unicode,...

Thông tin đƣa vào

 Quét trực tiếp các loại sách báo, văn bản qua máy quét (Scanner).

 Đọc và xử lý hơn 30 dạng tệp tin ảnh phổ dụng nhất nhƣ PCX, BMP, TIF, GIF, JPG,

...

 Có thể nhận dạng trực tiếp tài liệu quét qua Scanner không cần lƣu trữ dƣới dạng tệp

ảnh trung gian. Các trang tài liệu có thể đƣợc quét và lƣu trữ dƣới dạng tệp tin nhiều

trang.

Các chức năng chính:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

14

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

- Phân tích cấu trúc vật lý của tài liệu và đƣa ra cấu trúc phần vùng

- Phân tích và nhận dạng chữ đầu ra là text có thể copy hay lƣu trữ và soạn thảo

lại đƣợc.

Hình 10: VnDOCR và một ví dụ nhận dạng¹

Một số hạn chế: Tính đến phiên bản 4.0

- VnDOCR chỉ làm việc với ảnh đen trắng

- Với các ảnh có cấu trúc vật lý phức tạp VnDOCR cho kết quả phân tích với

hiệu quả chƣa cao (Hinh 11, 12)

Thí nghiệm 1:

- Với ảnh đầu vào nhƣ sau:

¹Nguồn từ www.vndocr.com

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

15

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 11: Ảnh mẫu có cấu trúc vật lý phức tạp

- Kết quả phân tích của VnDOCR không tim thấy vùng văn bản nào mà chỉ

khoanh vùng đƣợc 2 vùng ảnh (1,2) nhƣ Hình 12

Hình 12: Kết quả ra hai vùng ảnh với ảnh mẫu 11

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

16

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Thí nghiệm 2:

Với ảnh đầu vào có cấu trúc vật lý đơn giản hơn (các vùng cơ sở có bao là hình

chữ nhật – Hình 13).

Hình 13: Mẫu ảnh có cấu trúc vật lý phức tạp, nhƣng các khối bao bởi hình chữ nhật

Kết quả phân tích bởi VnDOCR bỏ sót một vùng văn bản và gồm nhầm 2 vùng

ảnh vào vùng văn bản số 1 (Hình 14).

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

17

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 14: Kết quả phân tích với ảnh 13

I.4.2. OminiPage

OmniPage là phần mềm nhận dạng văn bản của NUANCE. Nó có thể chuyển đổi

các file ảnh tài liệu hay file PDF sang dạng file văn bản có thể đọc đƣợc bởi các phần

mềm soạn thảo nhƣ Office, với khả năng nhận dạng các ký tự la tinh chính xác tới 99%.

Một số đặc tính chính²:

- Nhận dạng chính xác tới 99% trên 119 ngôn ngữ khác nhau

- Nhận dạng cả các file vào là PDF

- Nhận dạng đƣợc các trang có nhiều loại font, kiểu font hoặc có nền là ảnh mầu

- Một số hạn chế chính:

- Chƣa hiệu quả với các ảnh tài liệu có cấu trúc phức tạp.

Thí nghiệm 1:

Với ảnh đầu vào Hình-11 có kết quả nhƣ sau: Omnipage đoán nhận tất các ảnh

đều là vùng văn bản (Hình-15)

²Nguồn từ nhà sảnh xuất http://www.nuance.com/imaging/omnipage/omnipage-professional.asp

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

18

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Thí nghiệm 2: Với ảnh đầu vào 13, tƣơng tự nhƣ VnDOCR OmniPage vẫn phân vùng

sai (Hình 16)

Hình 15: Đầu ra phân vùng chỉ có 1 vùng văn bản

Vùng lỗi

Hình 16: Đầu ra có vùng chứa cả ảnh và text

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

19

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

I.4.3. Finereader

Finereader là một sản phẩm ORC của ABBYY với một số tính năng chính sau³:

- Cho phép kết nối và nhận dạng ảnh trực tiếp từ Camera.

- Nhận dạng đƣợc 38 ngôn ngữ khác nhau.

- Nhận dạng cả text trong đồ họa.

- Với 2 mẫu văn bản có cấu trúc phức tạp nhƣ trên thì Finereader đều cho hiệu

quả cao, nói chung Fineread đều có hiệu quả cao với các tài liệu có bố cục

phức tạp.

Hình 17: Với ảnh 13 đạt hiệu quả 90%

³Nguồn từ nhà sản xuất http://finereader.abbyy.com/full_feature_list

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

20

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 18 Với ảnh I-15 hiệu quả đạt 100%

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

21

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 19: Với mẫu phức tạp hơn Finereader cho kết quả 95%

Hạn chế chính của Finereader là tốc độ làm việc chậm so với 2 phần mềm kể trên.

I.5. Kết luận

Từ những kết quả ở trên phạm vi đề tài ở đây sẽ chỉ tập trung vào việc phân tích

cấu trúc vậy lý của một trang tài liệu(trình bày chi tiết ở chƣơng 2). Để cải tiến hơn so

với VNDocr đối tƣợng của đề tài sẽ là ảnh đa cấp xám có độ phức tạp cao.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

22

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Chƣơng II: CÁC PHƢƠNG PHÁP TIẾP CẬN

ĐỂ PHÂN TÍCH TRANG TÀI LIỆU

Với phạm vi đặt ra ở chƣơng một và phần mở đầu là đề tài sẽ tập trung vào giải

pháp phân tích cấu trúc vật lý của trang tài liệu, chƣơng 2 sẽ giới thiệu một số phƣơng

pháp phân tích hiện nay, từ đó đƣa ra và đánh giá đƣợc ƣu nhƣợc điểm của mỗi phƣơng

pháp đó. Sau đó sẽ tập trung phân tích kỹ một phƣơng pháp mới chƣa đƣợc trình bày ở

các đề tài trƣớc đó là Fractal Signature với những ƣu điểm vƣợt trội của nó là hiệu quả

cao với tài liệu phức tạp, không phân biệt góc nghiêng. Đồng thời thiết kế hệ thống demo

với giải pháp mới này.

II.1. Các phƣơng pháp phân tích định dạng trang tài liệu

II.1.1. Top-down

a) Tổng quan

Ý tƣởng chính của thuật toán là phân tách liên tiếp từ một trang ban đầu thành các

vùng cơ sở nhỏ hơn. Các khối cơ sở ở đây là các khối nhƣ đoạn văn, tiêu đề, đồ họa,…

Việc phân tách chúng thành các vùng riêng biệt dựa trên tiêu chí về ngƣỡng khoảng cách

mà phƣơng pháp phổ thông nhất là xác định thông qua kết quả của phép chiếu nghiêng.

 Phép chiếu nghiêng theo hƣớng x bất kỳ: Thực chất là đi xác định lƣợc đồ xám bằng

cách tính tổng các điểm ảnh màu đen (hoặc trắng) theo phƣơng vuông góc với x dọc

theo trục x. Trong thực tế x thƣờng là phƣơng nằm ngang hay phƣơng thẳng đứng so

với trang văn bản.

Một ví dụ về phép chiếu nghiêng với một trang tài liệu cho ở Hình-20:

Trên lƣợc đồ xám của phép chiếu nghiêng sẽ xuất hiện các điểm cực trị, với phép

chiếu nghiêng theo phƣơng thẳng đứng ta dễ nhận thấy độ rộng của các đáy chính là

khoảng cách giữa hai dòng, với các độ rộng của đáy nào đó mà tần suất xuất hiện ít hoặc

vƣợt quá một ngƣỡng chính là khoảng các giữa hai vùng văn bản. Còn tại vị trí các đỉnh

là trục của mỗi dòng văn bản.

Với phép chiếu nghiêng theo phƣơng ngang ta có thể phân tách đƣợc các cột hay

các vùng cơ sở dựa vào ngƣỡng khoảng cách của đáy (Hình-20). Cũng theo nguyên tắc

này nếu áp dụng phe chiếu nghiêng trên mỗi dòng văn bản ta cũng có thể phân đoạn đƣợc

các ký tự hoặc các từ dựa vào khoảng cách của đáy (ví dụ nhƣ Hình-21).

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

23

GVHD: PGS. TS. Ngô Quốc Tạo

Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy

Hình 20: Kết quả chiếu nghiêng theo phƣơng ngang và phƣơng thẳng đứng của một trang tài liệu⁴

4

(Anoop M. Namboodiri and Anil K. Jain)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

http://www.lrc-tnu.edu.vn

24

GVHD: PGS. TS. Ngô Quốc Tạo