Luận văn Thạc sĩ Khoa học máy tính: Đánh giá sự ảnh hưởng của tham số đến kết quả phân tách của thuật toán WhiteSpace

TRƯỜNG ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG 



PHẠM VĂN THỦY

ĐÁNH GIÁ SỰ ẢNH HƯỞNG CỦA THAM SỐ

ĐẾN KẾT QUẢ PHÂN TÁCH CỦA THUẬT TOÁN WHITESPACE

LUẬN VĂN THẠC SĨ

Thái Nguyên, tháng 06 năm 2017

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn cao học “Đánh giá sự ảnh hưởng của

tham số đến kết quả phân tách của thuật toán WhiteSpace” là công trình

nghiên cứu của riêng tôi và hoàn thành dưới sự hướng dẫn khoa học của TS.

Nguyễn Đức Dũng.

Trong toàn bộ nội dung của luận văn, những phần được trình bày là

của cá nhân tôi hoặc được tổ hợp từ nhiều nguồn tài liệu khác nhau. Tất cả

các tài liệu, số liệu đều là trung thực có xuất xứ rõ ràng và được trích dẫn

đúng theo quy định.

Tôi hoàn toàn chịu trách nhiệm với lời cam đoan của mình.

Học viên thực hiện luận văn

Phạm Văn Thủy

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn chân thành tới TS. Nguyễn Đức Dũng vì đã có

những chỉ dẫn, động viên trong suốt quá trình thực hiện luận văn của tôi.

Đồng thời tôi xin chân thành cảm ơn các thầy cô giáo trong Ban giám hiệu,

phòng Đào tạo, các thầy cô giáo của trường Đại học Công nghệ Thông tin và

Truyền thông - Đại học Thái Nguyên cùng các thầy cô giáo trong Viện Công

nghệ Thông Tin - Viện Hàn lâm Khoa học Việt Nam đã quan tâm, tạo điều

kiện thuận lợi, giảng dạy và hướng dẫn tôi trong suốt quá trình học tập và

hoàn thiện luận văn.

Cuối cùng tôi xin cảm ơn mọi sự giúp đỡ từ người thân, đồng nghiệp

những người đã luôn ủng hộ, hỗ trợ tôi trong suốt quá trình thực hiện luận văn

của mình.

Mặc dù đã có nhiều cố gắng, tuy nhiên luận văn của tôi không thể tránh

khỏi những thiếu sót, do đó tôi rất mong nhận đuợc những ý kiến đánh giá, bổ

sung để tôi có thể hoàn thiện luận văn của mình./.

Quảng Ninh, ngày tháng năm 2017

MỤC LỤC

DANH MỤC HÌNH ẢNH ............................................................................... 7

PHẦN MỞ ĐẦU ............................................................................................ 10

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

2. Nội dung nghiên cứu chính ................................................................ 11

2.1. Mục tiêu chính của đề tài ................................................................ 11

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

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

2.4. Phương pháp nghiên cứu ............................................................... 12

2.5. Phạm vi nghiên cứu ......................................................................... 13

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

CHƯƠNG 1: TỔNG QUAN VỀ PHÂN TÍCH ẢNH TÀI LIỆU ............. 14

1.1. Tổng quan về phân tích ảnh tài liệu.................................................. 14

1.1.1. Giới thiệu về ảnh tài liệu ............................................................... 14

1.1.2. Hệ phân tích ảnh tài liệu .............................................................. 15

1.1.3 Quá trình thu nhận ảnh tài liệu .................................................... 20

1.1.4. Vai trò của phân tích ảnh tài liệu. ................................................ 21

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

1.2.1. Cấu trúc vật lý ................................................................................ 23

1.2.2. Cấu trúc logic ................................................................................ 24

1.3. Phân tích trang tài liệu ....................................................................... 24

1.3.1. Tiền xử lý (preprocessing): ........................................................... 26

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

1.3.3. Phân tích cấu trúc logic: ............................................................... 29

1.4 Kết luận ................................................................................................. 30

CHƯƠNG 2: ĐÁNH GIÁ SỰ ẢNH HƯỞNG CỦA THAM SỐ ĐẾN KẾT

QUẢ PHÂN TÁCH CỦA THUẬT TOÁN WHITESPACE ..................... 31

2.1. Các hướng tiếp cận và một số thuật toán phân tách trang tiêu biểu

..................................................................................................................... 31

2.1.1. Hướng tiếp cận Top-down ............................................................ 31

a) Tổng quan ........................................................................................ 31

c) Ưu điểm: .......................................................................................... 35

d) Nhược điểm: .................................................................................... 35

2.1.2. Hướng tiếp cận Bottom-up ........................................................... 38

a) Tổng quan ........................................................................................ 38

c) Ưu điểm ............................................................................................ 42

d) Nhược điểm ..................................................................................... 42

2.1.3. Hướng tiếp cận theo phương pháp lai ghép (hybrid). ................. 43

a) Tổng quan ........................................................................................ 43

b) Thuật toán tách và Nối thích nghi (Adaptive Split - and - Merge)

............................................................................................................... 43

c) Ưu điểm ............................................................................................ 45

d) Nhược điểm ..................................................................................... 45

2.1.4. Đánh giá và lựa chọn thuật toán. ................................................. 46

2.2. Thuật toán phân tích trang tài liệu Whitespace .............................. 47

2.2.1. Giới thiệu ....................................................................................... 47

2.2.2. Whitespace Cover .......................................................................... 48

2.2.2.1. Định nghĩa bài toán ............................................................... 48

2.2.2.2. Thuật toán .............................................................................. 49

2.3. Ảnh hưởng của tham số đến kết quả phân tách của thuật toán

Whitespace .................................................................................................. 54

2.3.1. Tham số về tỉ lệ chồng lấp (giao nhau) của các hình chữ nhật

trắng. ........................................................................................................ 54

2.3.2. Tham số về khoảng trắng tối đa trong trang văn bản ................. 56

2.4 Kết luận ................................................................................................. 68

CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH VÀ THỰC NGHIỆM

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

3.1. Yêu cầu hệ thống ................................................................................. 71

3.2. Giới thiệu chương trình ..................................................................... 71

3.2.1. Giao diện chương trình ................................................................ 72

3.2.2. Chức năng ..................................................................................... 72

3.3. Thực nghiệm ........................................................................................ 73

3.3.1. Dữ liệu ........................................................................................... 73

3.3.2. Giới thiệu độ đo PSET .................................................................. 73

3.3.3. Kết quả thực nghiệm và thảo luận ............................................... 76

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

DANH MỤC HÌNH ẢNH

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

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

Hình 1.3: Sơ đồ khối liệt kê nhiệm vụ xử lý ảnh tài liệu được phân chia theo

cấp bậc trong mỗi vùng của ảnh. ..................................................................... 17

Hình 1.4: mô phỏng một chuỗi các bước trong phân tích hình ảnh tài liệu phổ

biến. ................................................................................................................. 19

Hình 1.5. Một hình ảnh nhị phân của chữ "e" được thực hiện lên ON và OFF

các điểm ảnh, ON điểm ảnh được hiển thị ở đây là "X"[15]. ......................... 21

Hình 1.6: Sơ đồ OCR cơ bản .......................................................................... 22

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

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

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

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

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

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

Hình 2.1: 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 .................................................................................... 32

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

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

......................................................................................................................... 33

Hình 2.4: Kết quả thực hiện của thuật toán X-Y Cut ...................................... 35

Hình 2.5: Lược đồ chiếu ngang của một dòng chữ nghiêng ........................... 36

- rất khó phân đoạn ký tự ................................................................................ 36

Hình 2.6: Lược đồ chiếu đứng của trang tài liệu bị nghiêng .......................... 37

Hình 2.7: Lược đồ chiếu đứng của một bài báo .............................................. 37

Hình 2.8: Phương pháp Dostrum cho phân tích định dạng trang (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.

định được dòng văn bản. ................................................................................. 39

Hình 2.9: Kết quả thực hiện của kỹ thuật Smearing ....................................... 41

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

Hình 2.11: Hình minh họa bước đệ quy của thuật toán Cover khoảng trắng

phân nhánh - giới hạn. Xem giải thích ở nội dung văn bản. ........................... 49

Hình 2.12: Áp dụng thuật toán tìm kiếm dòng ràng buộc cho các biến thức mô

phỏng của một trang. ....................................................................................... 52

Hình 2.13: Fig. 1.Mô tả thuật toán WCover [16]. (a) hình bao và các hình chữ

nhật, (b) điểm chốt tìm được (c,d) các miền con trai/phải và trên/dưới ......... 54

Hình 2.14: Mô hình dòng văn bản được sử dụng tìm kiếm dòng ràng buộc. . 58

Hình 2.15: Minh họa bài toán tìm kiếm dòng ràng buộc với những trở ngại. 59

Hình 2.16: Ví dụ về kết quả đánh giá khoảng trắng để phát hiện các ranh giới

cột trong tài liệu có bố cục phức tạp (các tài liệu A00C, D050, và E002 từ cơ

sở dữ liệu UW-III). Lưu ý rằng ngay cả các bố cục phức tạp cũng được mô tả

bởi một tập nhỏ các dấu tách cột. .................................................................... 63

Hình 3.1: Giao diện chương trình ................................................................... 72

Hình 3.2: Giao diện chức năng chương trình .................................................. 72

Hình 3.3: Minh họa các kiểu lỗi trong phân tích trang ảnh tài liệu ................ 74

Hình 3.4: Ảnh số 0000085 trong tập ảnh UW-III .......................................... 76

Hình 3.5: Giao diện và kết quả thực nghiệm .................................................. 77

Hình 3.6: Kết quả phân tách hình 0000085 – UW-III .................................... 77

Hình 3.7: Bảng kết quả thực nghiệm .............................................................. 79

Hình 3.8: Ảnh hưởng của số lượng khoảng trắng tối đa đến kết quả của Wcuts

và ageblock. ..................................................................................................... 80

Hình 3.9: Ảnh hưởng của Max_results đến thời gian thực hiện chương trình 80

Hình 3.10: Độ chính xác của thuật toán với độ đo PSET sử dụng tham số

khoảng trắng là 300 ......................................................................................... 82

Hình 3.11: Vùng bị bỏ qua .............................................................................. 83

Hình 3.12: Vùng bị phân tách thành các phần quá nhỏ .................................. 83

Hình 3.13: Độ chính xác của thuật toán với độ đo PSET sử dụng tham số tỉ lệ

giao nhau là 95% ............................................................................................. 84

PHẦN MỞ ĐẦU

1. Đặt vấn đề

Hiện nay, hầu hết tài liệu của con người đều đã được số hóa và được

lưu trữ trên máy tính, việc số hóa đảm bảo tính an toàn và thuận tiện hơn hẳn

so với sử dụng tài liệu giấy. Tuy nhiên việc sử dụng giấy để lưu trữ tài liệu

trong một số mục đích là không thể thay thế hoàn toàn được (như sách, báo,

tạp 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.

Việc chuyển đổi tài liệu điện tử sang tài liệu giấy có thể thực hiện được

dễ dàng bằng cách in hay fax, nhưng công việc ngược lại là chuyển từ tài liệu

giấy sang tài liệu điện tử lại là một vấn đề không hề đơn giản. Chúng ta mong

muốn có thể số hóa tất cả các tài liệu, sách, báo đó và lưu trữ chúng trên máy

tính, việc tổ chức và sử dụng chúng sẽ thuận tiện hơn rất nhiều. Vậy nhưng

giải pháp sẽ là gì?

Công nghệ đang phát triển một cách chóng mặt, các máy scan với tốc

độ hàng nghìn trang một giờ, các máy tính với công nghệ xử lí nhanh chóng

và chính xác một cách siêu việt. Vậy tại sao chúng ta không quét các trang tài

liệu vào và xử lý, chuyển chúng thành các văn bản một cách tự động? Nhưng

vấn đề là khi quét chúng ta chỉ thu được các trang tài liệu đó dưới dạng ảnh

nên không thể thao tác, sửa chữa, tìm kiếm như trên các bản Office được, khi

đó máy tính không phân biệt được đâu là điểm ảnh của chữ và đâu là điểm

ảnh của đối tượng đồ họa.

Một giải pháp được đưa ra đó là xây dựng các hệ thống nhận dạng chữ

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

trang văn bản và có thể mở, soạn thảo được trên các trình soạn thảo văn bản.

Trong thực tế quá trình nhận dạng thì 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… 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.

Dù đã được nghiên cứu trong nhiều năm nhưng bài toán phân tách

trang ảnh tài liệu vẫn là một vấn đề quan trọng và thời sự do sự thay đổi đa

dang về cấu trúc và các đặc trưng văn bản. Các thuật toán phân tách trang

hiện nay đều phụ thuộc rất nhiều vào kết quả của quá trình lọc khoảng trắng,

chỉnh góc nghiêng, tức là các tham số điều kiện để quyết định các khoảng

trắng có được giữ lại hay không, góc nghiêng có phù hợp hay không. Các

tham số này hoặc cố định hoặc được xác định trên toàn trang ảnh do đó có

hoặc không phù hợp trên những trang ảnh có sự thay đổi nhiều về kích cỡ

hoặc kiểu font. Trong luận văn này, tập trung nghiên cứu và “Đánh giá sự

ảnh hưởng của tham số đến kết quả phân tách của thuật toán

WhiteSpace” với mục đích lựa chọn được tham số phù hợp nhằm phát huy

các điểm mạnh và khắc phục nhược điểm của thuật toán.

2. Nội dung nghiên cứu chính

2.1 . Mục tiêu chính của đề tài

- Tìm hiểu hướng tiếp cận để phân tách trang (Top-down hay bottom-

up, …) 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, topdown hay bottom-up, …)Trình bày kỹ thuật phân tích trang văn bản

White-space.

- Cài đặt thử nghiệm một giải pháp phân tích trang văn bản trên kỹ

thuật Top-down bằng thuật toán White-space.

- Đánh giá sự ảnh hưởng của tham số đến kết quả phân tách trang của

thuật toán White-space.

- 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.

2.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 và thực nghiệm để làm rõ về sự ảnh hưởng của tham số đến

kết quả phân tách của thuật toán Whitespace.

- Đá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ư: Số hóa tài liệu, lưu trữ thư viện, điện tử hóa văn phòng, nhận dạng và xử

lý ảnh...

2.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ừ đó đánh giá sự ảnh hưởng của tham số và chọn một giải pháp tối

ưu khi lựa chọn tham số và cài đặt thử nghiệm chương trình phân tích trang

tài liệu.

2.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, độ đo và thực nghiệm và thảo luận.

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

Bài toán phân tích trang 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ới 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:

- 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.

- Kết quả thực kiệm.

- Đánh giá kết quả.

3. 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 :

Chương 1: Tổng quan về phân tích trang tài liệu

Chương 2: Đánh giá sự ảnh hưởng của tham số đến kết quả phân tách của

thuật toán WhiteSpace

Chương 3: Cài đặt chương trình Demo và đánh giá kết quả.

CHƯƠNG 1

TỔNG QUAN VỀ PHÂN TÍCH ẢNH TÀI LIỆU

1.1. Tổng quan về phân tích ảnh tài liệu

1.1.1. Giới thiệu về ảnh tài liệu

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

cách dùng máy scanner, hoặc chụp từ Các máy ảnh số, hay nhận từ một máy

fax. Ảnh tài liệu có nhiều loại: ảnh đen trắng, ảnh đa cấp xám, ảnh đa cấp xám

với các phần mở rộng như TIF, BMP, PCX, …(Hình 1.2) và ảnh tài liệu được

đưa ra trong luận văn này là ảnh đa cấp xám.

Tài liệu Thiết bị thu nhận ảnh Ảnh số tài liệu

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

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

1.1.2. Hệ phân tích ảnh tài liệu

Ảnh tài liệu sau khi được quét và lưu trữ vào máy tính thì nó được cấu

thành từ những điểm ảnh, nhiệm vụ của chúng ta là phải trích chọn được

những thông tin đặc trưng từ nó sao cho máy tính có thể “đọc” và “hiểu” được

các thành phần này. Để làm được điều này người ta phải áp dụng các thuật

toán kết hợp cùng với những kỹ thuật cả về phần cứng và phần mềm máy

tính, sự tích hợp này là yếu tố chính tạo thành một hệ phân tích ảnh tài liệu.

Sau khi tạo được hệ phân tích ảnh, người ta tiến hành quá trình xử lý ảnh gồm

việc thao tác lên ảnh đầu vào để cuối cùng cho ảnh đầu ra với kết quả đạt

được những mục tiêu đã định trước đó. Cụ thể là kết quả của ảnh đầu ra có thể

là một kết luận về sự nhận dạng hoặc là một ảnh đã được xử lý tốt hơn.

Một trong những công nghệ khá phổ biến hiện nay được áp dụng để

nhận dạng văn bản là công nghệ nhận dạng ký tự bằng quang học (Optical

Character Recognition-OCR). Cơ chế chủ yếu của nó là nhận dạng ký tự trên

nền định dạng ảnh tài liệu và chuyển sản phẩm nhận dạng được sang kiểu tập

tin văn bản. Từ đó OCR có thể giúp chúng ta thao tác trên văn bản như tạo,

sửa đổi, xóa bỏ, tìm kiếm, thay thế nội dung của tài liệu. Như vậy, mục tiêu

của hệ phân tích ảnh tài liệu là phát hiện ra được các đối tượng khác nhau

trong một ảnh tài liệu như chữ đánh máy, chữ viết bằng tay, hình ảnh, văn bản

chia thành hàng, cột, v.v. Đồng thời hệ phân tích này còn phải trích xuất được

những thành phần trong ảnh tài liệu mà chúng ta mong muốn để phục vụ cho

những mục đích nghiên cứu và ứng dụng khác nhau. Và đặc biệt trong bài

luận này là trọng tâm nhấn mạnh đến việc phát hiện được bảng biểu (detect

table) trong ảnh tài liệu. Trên cơ sở đặc điểm chung của một ảnh tài liệu

thường có chứa hai loại đối tượng chính là văn bản và hình ảnh cũng như đa

số các công nghệ nhận dạng được áp dụng hiện nay, chúng ta có thể thấy rằng

một hệ phân tích ảnh tài liệu thực hiện hai nhiệm vụ chính (xem hình 1.3).

Nhiệm vụ thứ nhất là phải xử lý các đối tượng hình ảnh được cấu thành

từ hình vẽ, đường kẻ, dấu vân tay, khuôn mặt, những nốt đen lớn, biểu

đồ,…Và nhiệm vụ thứ hai là phải xử lý các đối tượng văn bản cấu thành từ

chữ viết như ký tự, từ, chuỗi ký tự, chữ viết tay. Việc phát hiện độ nghiêng

(tilt) của tài liệu (độ nghiêng của văn bản xuất hiện khi chúng ta quét ảnh 5 tài

liệu từ máy quét đã đặt không chuẩn xác các vị trí của nó), phát hiện các

phông chữ, độ lớn chữ, từ, cụm từ, dòng văn bản, đoạn văn bản và các cột văn

bản là những công việc quan trọng và cần thiết để thực hiện việc phát hiện

văn bản được ứng dụng công nghệ OCR như đã đề cập. Sau khi thực hiện

thành công hai nhiệm vụ chính, hệ phân tích ảnh tài liệu sẽ trích chọn những

thông tin cần thiết đã phát hiện được, đưa vào một tài liệu ở một định dạng

khác như tập tin văn bản (word) hoặc ngôn ngữ hiển thị siêu văn bản (Hyper

Text Markup Language-HTML). Việc đầu tư tài chính, công nghệ, con người

cùng các yếu tố liên quan để thiết kế và ứng dụng hệ phân tích ảnh tài liệu là

rất cần thiết và vô cùng quan trọng. Nó giúp chúng ta giải quyết rất nhiều vấn

đề trong thực tế khi mà số lượng các dữ liệu lớn. Con người tiếp nhận và xử

lý thông tin nhờ vào các giác quan, nhưng có thể nói trong đó có khoảng 80%

là thu nhận bằng mắt. Một vài ví dụ điển hình có thể minh chứng rằng thực sự

cần thiết để sở hữu một hệ thống phân tích ảnh tài liệu nào đó. Thứ nhất, ta là

người phải nhập điểm số cho hàng trăm nghìn sinh viên trong một trường đại

học được gửi về từ các giáo viên giảng dạy, theo cách làm truyền thống thì tại

phòng xử lý điểm phải có ít nhất một người ngồi đọc điểm cùng với một

người gõ vào máy tính. Việc này vừa tốn thời gian, tốn chi phí nhân công, ít

khách quan lại dễ xảy ra sai sót do yếu tố con người. Thay vào đó, nhà trường

có thể thiết kế phiếu điểm giao cho giảng viên trong đó đã có sẵn các giá trị từ

1 đến 10 cho mỗi sinh viên và chỉ việc chấm điểm theo cách tô đen vào vị trí

điểm số mà sinh viên đạt được. Cuối cùng bảng điểm này được quét để máy

tính phát hiện điểm số một cách tự động nhờ vào chấm đen mà giảng viên đã

tô đậm thông qua một hệ nhận dạng ảnh tài liệu, theo đó sẽ khắc phục được

những nhược điểm của cách làm truyền thống.

Thứ hai là, tại một doanh nghiệp sản xuất kinh doanh với số nhân công

hàng chục ngàn người làm việc trong ngày, trong các công đoạn chấm công

có việc kiểm tra sự có mặt của nhân viên vào đầu giờ và cuối giờ làm. Với

phương pháp truyền thống doanh nghiệp phải cử ra rất nhiều người để theo

dõi các nhân viên còn lại việc vào và ra khỏi công ty phải đúng giờ. Việc này

đã được khắc phục nhằm đem lại sự thuận lợi, chính xác và ít tốn kém bằng

cách sử dụng một máy chấm công bằng vân tay, trong đó tích hợp công nghệ

xử lý và so sánh dấu vân tay bảo đảm công tác thống kê số giờ làm mà không

cần sự theo dõi trực tiếp của con 6 người. Trong đó, máy chấm công bằng dấu

vân tay ứng dụng hệ phân tích ảnh tài liệu.

Hình 1.3: Sơ đồ khối liệt kê nhiệm vụ xử lý ảnh tài liệu được phân chia

theo cấp bậc trong mỗi vùng của ảnh.

Hệ phân tích ảnh tài liệu đã được sử dụng trong vài thập kỷ qua, đặc

biệt là trong ngành kinh doanh ngân hàng, bưu điện, thư viện,…ứng dụng để

máy tính đọc mã vạch hoặc lưu trữ tài liệu ở dạng điện tử, vào cuối những

năm 1980 và 1990 thì đã phát triển nhanh chóng. Lý do chủ yếu của việc phát

triển này là tốc độ ngày càng lớn và chi phí thấp hơn của phần cứng máy tính.

Kể từ khi máy fax trở nên phổ biến, chi phí của máy quét quang học

cho các tài liệu đầu vào giảm xuống đã giúp các doanh nghiệp nhỏ cũng như

mỗi cá nhân có cơ hội được sử dụng những công nghệ này. Mặc dù ảnh tài

liệu có chứa một lượng tương đối lớn dữ liệu, thì ngay cả máy tính cá nhân

hiện nay cũng đã có tốc độ đủ để xử lý chúng. Bộ nhớ máy tính bây giờ

không những đủ cho các hình ảnh tài liệu lớn, mà quan trọng hơn, bộ nhớ

quang học bây giờ cũng đủ để lưu trữ khối lượng lớn dữ liệu. Điều này dẫn

đến ngày càng phát triển công nghệ nhận dạng và xử lý ảnh tài liệu. Sự bổ

sung cần thiết cho những cải tiến phần cứng là những tiến bộ đang được thực

hiện trong việc phát triển các thuật toán và phần mềm phân tích ảnh tài liệu.

Trong đó công nghệ OCR có khả năng nhận dạng văn bản với độ chính xác

lên đến khoảng 90%, bên cạnh đó nhiều phương pháp nhận dạng ảnh tài liệu

khác cũng được cải tiến gần như xử lý ảnh tài liệu xử lý văn bản xử lý đối

tượng ảnh Nhận dạng ký tự quang học phân tích bố trí trang xử lý đường kẻ

xử lý biểu tượng và vùng văn bản phát hiện độ nghiêng, dòng, khối và đoạn

văn bản Đường thẳng, góc và các đường cong Lấp đầy các khu vực Hình 1.1:

Sơ đồ khối liệt kê nhiệm vụ xử lý ảnh tài liệu được phân chia theo cấp bậc

trong mỗi vùng của ảnh[15]. Theo đó, các tài liệu viết tay hoặc tài liệu đã

được in ấn hay những hình ảnh có thể được chuyển thành tài liệu điện tử trên

máy tính để thuận tiện trong việc lưu trữ, quản lý, chỉnh sửa và biên soạn lại.

Tuy nhiên, tài liệu giấy cho đến nay vẫn đang phát huy vai trò truyền thống

của nó do tính chất trực quang, dễ thao tác, phổ biến được rộng rãi đối với

mọi đối tượng sử dụng. Vì vậy, chúng ta phải tìm cách giải quyết vấn đề là sử

dụng công nghệ và các thuật toán để tích hợp dữ liệu dưới dạng ảnh tài liệu

vào trong bộ nhớ phần cứng để xử lý bằng máy tính. Sau khi đã tạo ra dữ liệu,

máy tính phải thực hiện các bước xử lý cơ bản như xử lý điểm ảnh, phân tích

các thành phần đặc trưng, phân tách từng thành phần phát hiện riêng biệt là

phát hiện hình ảnh và phát hiện văn bản.

Hình 1.4: mô phỏng một chuỗi các bước

trong phân tích hình ảnh tài liệu phổ biến.

Các phần tiếp theo sẽ trình bày vắn tắt một số bước cơ bản này. Sau khi

thu thập dữ liệu, hình ảnh trải qua xử lý cấp độ điểm ảnh và phân tích tính

năng, sau đó mỗi loại đối tượng văn bản và hình ảnh được phát hiện và xử lý

riêng. Thu thập dữ liệu được thực hiện trên một tài liệu giấy thường bằng cách

quét quang học. Các dữ liệu sau đó được lưu trữ trong một tập tin hình ảnh,

gọi là điểm ảnh, được lấy mẫu trong một mô hình mạng lưới xuyên suốt ảnh

tài liệu [15].

1.1.3 Quá trình thu nhận ảnh tài liệu

Ảnh tài liệu thường được thu thập bằng cách quét quang học thông qua

máy quét hoặc bằng cách sao chép hình ảnh và những đoạn phim kỹ thuật số

từ máy chụp hoặc máy quay phim (camera) rồi được lưu trữ vào máy tính

dưới dạng một tập tin ảnh gồm có các yếu tố hình ảnh, hoặc điểm ảnh, đó là

“nguyên liệu” đầu vào để phân tích ảnh tài liệu sau này. Dữ liệu lúc này được

tập hợp là các điểm ảnh (pixels) và được mô phỏng thành tập hợp của một

lưới các điểm ảnh (a grid pattern) [15]. Các thiết bị thu nhận ảnh tài liệu có

hai loại chính tương ứng với hai loại ảnh thông dụng Vector và Raster. Theo

đó, quá trình thu nhận ảnh tài liệu thực hiện các công đoạn chính gồm việc

biến đổi năng lượng quang học thành năng lượng điện gọi là cảm biến và tổng

hợp năng lượng điện thành ảnh gọi là quá trình lượng tử hóa (Đỗ Năng Toàn-

2008). Với ảnh nhị phân thì cường độ điểm ảnh có thể nhận một trong hai giá

trị OFF (0) hoặc ON (1) (Hình 1.5). Đối với ảnh đa cấp xám thì cường độ

điểm ảnh nhận giá trị từ 0 đến 255 và với ảnh màu thì giá trị điểm ảnh nhận 3

kênh là R, G, B từ 0 đến 255 giá trị màu sắc. Thí dụ, với một trang ảnh tài liệu

có kích thước 30x40 cm và có 140 điểm ảnh trong 1 centimet thì tạo được ảnh

với 4200x5600 điểm ảnh. Từ đó cho thấy rằng một ảnh tài liệu thông thường

là tập hợp của các giá trị điểm ảnh mà người ta đã dùng các bộ cảm biến hoặc

máy quét để biến tín hiệu quang thành tín hiệu điện liên tục, rồi thì khắc phục

hiện tượng chồng phổ, thực hiện lượng tử hóa cùng với các công đoạn kỹ

thuật khác và cuối cùng sẽ trích chọn được các thông tin phù hợp.

Hình 1.5. Một hình ảnh nhị phân của chữ "e" được thực hiện lên ON và

OFF các điểm ảnh, ON điểm ảnh được hiển thị ở đây là "X"[15].

1.1.4. 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 1.6. Trong đó:

- 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

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õ rà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 qủ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 1.6: Sơ đồ OCR cơ bản

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

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.

1.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. 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,…

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 …

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

1.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, … Thông thường

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.

1.3. Phân tích trang 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[15].

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

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 1.9: Sơ đồ nguyên lý hệ thống xử lý tài liệu[15]

1.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, máy ảnh), 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

đa cấp xám 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 pixel 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, …)

- 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 1.10: 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.

1.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ó[15]. 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)

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 1.11: Ví dụ một ảnh tài liệu bị nghiêng một góc 5 độ

1.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 1.7)

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

1.4 Kết luận

Chương thứ nhất với những nội dung cơ bản và một số nội dung mới có

liên quan mật thiết với hệ phân tích ảnh tài liệu. Đặc biệt là đã đề cập một số

công đoạn chính trong xuyên suốt quá trình kể từ lúc thu quét ảnh tài liệu đầu

vào, đến lúc có thể phát hiện và trích chọn được những tính năng quan trọng

do người dùng đặt ra ban đầu. Bên cạnh một số kỹ thuật truyền thống, kết hợp

với việc tham khảo các tài liệu trong nước và thế giới đã có đề cập đến một số

cải tiến, một số phương pháp cũng như ý tưởng mới của một số tác giả từng

có nhiều cống hiến và thành công trong lĩnh vực nghiên cứu xử lý ảnh.

Chương 2 và chương 3 của bài luận sẽ trình bày tiếp những nội dung sâu sắc

hơn về bài toán tìm vùng trắng tối đa và thuật toán phân tách trang tài liệu

WhiteSpace, quá trình thực nghiệm và một số kết quả đạt được.

CHƯƠNG 2

ĐÁNH GIÁ SỰ ẢNH HƯỞNG CỦA THAM SỐ

ĐẾN KẾT QUẢ PHÂN TÁCH CỦA THUẬT TOÁN WHITESPACE

2.1. Các hướng tiếp cận và một số thuật toán phân tách trang tiêu biểu

Các thuật toán phân tách trang ảnh tài liệu được chia thành ba loại,

tương ứng với ba cách tiếp cận khác nhau là từ trên xuống (top-down), từ

dưới lên (bottom-up) và phương pháp lai ghép (hybrid).

2.1.1. Hướng tiếp cận 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 đa cấp xám đen (hoặc trắng) theo

phương vuông góc với x dọc theo trục y. 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-

2.1): 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-2.3).

Cũng theo nguyên tắc này nếu áp dụng phép 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-2.1).

Hình 2.1: 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

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

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

b) Thuật toán X-Y Cut

Thuật toán X-Y Cut [17]còn được gọi là thuật toán đệ quy X-Y Cut

(RXYC). RXYC là thuật toán đi từ trên xuống dựa vào một cây cơ sở. Ở đây,

gốc của cây cơ sở đại diện cho toàn bộ trang tài liệu. Tất cả các lá cùng đại

diện cho các phần phân khúc. Thuật toán X-Y Cut chia tách các tài liệu thành

hai hay nhiều khối chữ nhật đại diện cho nút của cây.

Thuật toán X-Y Cut được sử dụng để phân khúc trang tài liệu trong hệ

thống ORC. Khi một tài liệu được scan, ảnh của file scan sẽ xuất hiện “noise”

có thể gọi là hiện tượng nhiễu. Làm cho file ảnh vừa scan bị lệch đi nhiều hay

ít so với bản gốc, gây khó khăn cho việc phân đoạn tài liệu.Thuật toán X-Y

Cut là một trong những thuật toán được đưa ra để giải quyết tình trạng này

Input: Ảnh sau khi được quét Output: Ảnh được xử lý thành từng khối

chữ nhật.

Bước 1. Loại bỏ nhiễu ở biên của phân đoạn;

- Lấy các tài liệu quét;

- Chọn một điểm ảnh (X,Y) từ tài liệu và nhận được và kết nối với

những điểm ảnh tương ứng, làm như vậy cho 8 điểm ảnh xung quanh ta có

được giá trị của các điểm ảnh còn lại (X-1,Y),Right( X+1,Y),Top(X, Y+1),

Bottom(X,Y-1) và điểm ảnh bốn chéo {(X-1,Y-1),(X+1,Y-1),(X-

1,Y+1),(X+1,Y+1)};

- Nếu tất cả các điểm ảnh kết nối là màu đen sau đó thay đổi tất cả các

điểm kết nối với màu trắng và tiếp tục này quá trình cho đến khi toàn bộ tài

liệu được bao phủ bằng cách khác quá trình điểm ảnh tiếp theo và lặp lại

bước 1.

Bước 2. Tạo bảng tổng hợp tiền tố cho hệ thống OCR;

Bước 3. Tạo biểu đồ cho các giá trị điểm ảnh tại mỗi nút;

Bước 4. Tạo một giá trị ngưỡng (Tx, Ty) tương ứng với trục X và trục

Bước 5. So sánh (Tx, Ty) với thung lũng biểu đồ (Vx và Vy ) 5.1. Nếu

Vx > Tx hoặc Vy > Ty thì: + Chia tại trung điểm; + Quay lại bước 4; 5.2.

Ngược lại, thực hiện bước 6.

Bước 6. Kết thúc thuật toán;

Kết quả thực hiện của thuật toán X-Y Cut cải tiến với một ảnh tài liệu

đầu vào thực tế được thể hiện như hình sau:

Hình 2.4: Kết quả thực hiện của thuật toán X-Y Cut

c) Ưu điểm:

Điểm mạnh của các thuật toán này là độ phức tạp tính toán thấp, cho

kết quả phân tách tốt trên những trang ảnh có cấu trúc rectangular (những

vùng ảnh văn bản có thể xác định đường biên là các hình chữ nhật)

d) Nhược điểm:

Phân tích top-down tồn tại một số nhược điểm như:

- Kém hiệu quả với các loại tài liệu có bố cục phức tạp (Hình 2.5).

- Cần xoay ảnh về đúng vị trí ngang nếu ảnh bị nghiêng (Hình 2.6). -

Làm việc tốt chỉ với ảnh nhị phân.

- Kém hiệu quả với các trang tài liệu sử dụng nhiều loại font và size

khác nhau.

- Thông thường top-down được sử dụng cho các loại tài liệu biết trước

form bố cục, và có bố cục vật lý đơn giản.

Hình 2.5: Lược đồ chiếu ngang của một dòng chữ nghiêng

- rất khó phân đoạn ký tự

Hình 2.6: Lược đồ chiếu đứng của trang tài liệu bị nghiêng

Hình 2.7: Lược đồ chiếu đứng của một bài báo

2.1.2. Hướng tiếp cận Bottom-up

a) Tổng quan

Bottom-up bắt đầu với những phần nhỏ và tìm cách nhóm chúng vào

những phần lớn hơn, liên tiếp tới khi mọi khối trên trang được xác định. Thực

hiện phép nhóm bottom-up các phần văn bản nhờ một loạt thao tác làm trơn

theo loạt, theo các hướng. Kết quả thu được là các vùng ON và ta phân tích

các vùng liên thông trên đó. Tính toán một vài số liệu trên những vùng liên

thông này, ví dụ khoảng chiều cao và chiều dài các từ. Những thông tin đặc

trưng này được dùng để phân biệt các khối văn bản và phân biệt phần văn bản

và phần đồ họa. Esposito đã dùng cách tiếp cận tương tự, nhưng trước hết xác

định hợp biên của từng ký tự, sau đó thao tác trên hợp biên này, thay vì trên

từng pixel nhằm giảm lượng tính toán. Một số thuật toán tiêu biểu cho hướng

tiếp cận này là Smearing[15], Docstrum[14], Voronoi[16].

Phương pháp Docstrum bó cụm khác thực hiện với k lân cận gần nhất

để nhóm các ký tự và các dòng văn bản và các khối cấu trúc (Hình 2.8).

Trước tiên, với mỗi phần tài liệu, xác định các đường nối k lân cận gần nhất

với các phần xung quanh. Khoảng cách và góc của các đường nối này được vẽ

trên các biểu đồ. Vì hầu hết các đường nối được tạo giữa các ký tự cùng dòng,

góc tối đa sẽ chỉ ra góc nghiêng và khoảng cách tối đa sẽ là khoảng cách giữa

các ký tự. Sử dụng các ước lượng này, các dòng văn bản được xác định như

nhóm các ký tự và các từ dọc theo hướng của trang. Các dòng văn bản được

nhóm thành các khối sử dụng đặc tính của tài liệu là các dòng cùng khối

thường gần nhau hơn các dòng khác khối.

Hình 2.8: Phương pháp Dostrum cho phân tích định dạng trang (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. (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.

b) Thuật toán Smearing

Thuật toán Smearing Còn gọi là RLSA(The run-length smearing

algorithm)[15], thuật toán này dựa trên việc làm nhòe/mờ các ảnh điểm đen

trên một hình ảnh nhị phân. Quá trình này sẽ làm mờ các điểm ảnh đen trên

một trang mà theo đó các điểm ảnh trắng nhỏ sẽ bị làm đen.

Thuật toán được mô tả cụ thể như sau:

Input: Ảnh sau khi được quét: I

Output: Ảnh J chứa các vùng thông tin được xác định.

Bước 1: Nhị phân ảnh đầu vào.

+ Các điểm trắng (white pixels) được thể hiện bằng giá trị 0.

+ Các điểm đen (black pixels) được thể hiện bằng giá trị 1.

Bước 2: I1 Ảnh I được làm mờ theo phương ngang với giá trị ngưỡng Th.

Bước 3: I2 Ảnh I được làm mờ theo phương thẳng đứng với ngưỡng Tv.

Bước 4: J I1AND I2.

Bước 5: Làm mờ ảnh J theo phương ngang với ngưỡng Ts .

Bước 6: Liên kết các các thành phần liên thông thành các vùng văn bản.

Việc làm mờ sẽ được thực hiện dựa trên 2 quy tắc đơn giản:

Quy tắc 1: Bit 0 sẽ được chuyển thành 1 nếu số liền sát 0 nhỏ hơn hoặc bằng

với ngưỡng C nhất định (nếu độ dài một chuỗi của 0 nhỏ hơn hoặc bằng với

một ngưỡng, thì 0 sẽ được đổi thành 1).

Quy tắc 2: Bit 1 không đổi.

Xem xét ví dụ dưới đây, khi 0 tượng trưng cho điểm ảnh trắng và 1

tượng trưng cho điểm ảnh đen, dòng đầu tiên thể hiện chuỗi điểm ảnh nguyên

bản và dòng thứ 2 là kết quả thu được sau khi sử dụng phương pháp làm mờ.

Ngưỡng làm mờ C=4

0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0

1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1

Đầu tiên, toàn bộ dữ liệu hình ảnh sẽ được làm mờ theo phương ngang

với ngưỡng Th=300 cho ra hình ảnh làm mờ đầu tiên. Thực hiện quá trình

tương tự theo phương thẳng đứng với ngưỡng Tv=500. Các ngưỡng này đã

được cố định qua kinh nghiệm thực hành. Sau đó, 2 hình ảnh nhị phân này sẽ

được kết nối lại bởi phép toán điểm ảnh thông minh AND. Sau đó hình ảnh

nhị phân này sau đó sẽ được làm trơn một lần nữa bằng thuật toán làm mờ với

ngưỡng Ts=300. Sau đó ta sẽ thu được hình ảnh cuối cùng như sau:

Hình 2.9: Kết quả thực hiện của kỹ thuật Smearing

Tiếp theo sẽ tiến hànhphân tách các vùng giới hạn thông qua phương

pháp phân tích các thành phần liên thông. Đây được coi là bước nhập liệu

hình ảnh và đặt lại các thành phần liên thông vào các vùng tương ứng. Một

thành phần liên kết sẽ bao gồm một chuỗi các điểm ảnh liên thông với nhau.

Chúng ta sẽ xem xét các điểm ảnh theo 4 hướng: phía trên, phía dưới, bên trái

và bên phải, còn được gọi chung là 4-vùng lân cận (trái ngược với 8-vùng lân

cận kể cả các vùng chéo). Các vùng liên thông được xác định là những vùng

hình chữ nhật với kích thước nhỏ nhất có thể bao gồm tất cả các điểm ảnh của

thành phần liên kết đó.

c) Ưu điểm

Điểm mạnh của hướng tiếp cận này là các thuật toán có thể xử lý tốt

những trang ảnh với cấu trúc bất kì (mahattan hoặc non-mahattan [14]). Tuy

nhiên, do các vùng nhỏ được gộp lại với nhau dựa trên những tham số khoảng

cách, các tham số này được ước lượng trên toàn trang ảnh nên các thuật toán

này thường quá nhạy cảm với giá trị tham số và mắc lỗi chia quá nhỏ (over-

segmentation) các vùng ảnh văn bản, đặc biệt là các vùng chữ có sự khác biệt

về kích cỡ và kiểu font.

d) Nhược điểm

Phương pháp phân tích Bottom-Up cũng tồn tại một số nhược điểm như sau:

- Cần phải phân đoạn để xác định các thành phần cơ sở trước khi có thể

nhóm lại.

- Tốc độ thực hiện chậm và phụ thuộc vào số các thành phần trong

trang tài liệu.

- Cũng như Top-Down hiệu quả phục thuộc trực tiếp vào việc xác định

được góc nghiêng của tài liệu, vì khoảng cách dòng và từ chỉ xác định chính

xác được nếu góc nhiêng của tài liệu ≈00

- Kém hiệu quả với những trang tài liệu có cấu trúc phức tạp (nhiều

bảng, tỷ lệ đồ họa lớn hơn văn bản).

- Kém hiệu quả với loại trang tài liệu có nhiều loại Font chữ (chứa

nhiều size chữ khác nhau), vì với các trang chứa nhiều font có size khác nhau

hoặc loại font chữ nghiêng đặc biêt với chữ viết tay thì chương trình rất khó

có thể tính được chiều cao chữ hay độ rộng giữa hai dòng thông qua biểu đồ

chiếu nghiêng.

2.1.3. Hướng tiếp cận theo phương pháp lai ghép (hybrid).

a) Tổng quan

Phương pháp phân tích Adaptive Split – and – Merge được Lui, Tang

và Suen thiết kế với ý tưởng chính từ một trang tài liệu ban đầu và coi đó như

một vùng chưa đồng nhất, từ đó liên tiếp chia mỗi vùng thành các vùng nhỏ

hơn, tại mỗi bước chia thực hiện nối các vùng đồng nhất và chia tiếp các vùng

không đồng nhất.

b) Thuật toán tách và Nối thích nghi (Adaptive Split - and - Merge)

Để có thể mô tả được thuật toán một cấu trúc cây tứ phân phân lớp

được sử dụng để biểu diễn quá trình tách và nối của thuật toán. Trong đó nút

ở đỉnh tương ứng với trang tài liệu ban đầu và là gọi là lớp cao nhất, các nút

con tiếp theo là các vùng con tương ứng với lớp thứ k của bước chia thứ k các

vùng không đồng nhất (mô tả ở hình 2.3).

Các bước của thuật toán[14]:

B1: Tại lớp thứ K nếu tìm thấy một vùng không đồng nhất thì tiến hành

chia vùng đó thành 4 vùng nhỏ hơn

B2: Nếu thấy ít nhất 2 vùng trong 4 vùng vừa tách là đồng nhất thì tiến

hành nối chúng lại, còn các vùng không đồng nhất ta qua lại B1 và tách chúng

thành các vùng ở lớp thứ K+1.

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

Tiêu chuẩn xác định vùng đồng nhất để nối ghép[14]:

Hai vùng tương ứng rm và rn được coi là đồng nhất nếu chúng thảo mãn điều

kiện sau:

Trong đó:

Trong đó: Nm và Nn biểu thị số vùng con trong mỗi vùng tương ứng rm

và rn. M|rm và M|rn biểu thị giá trị trung bình của mỗi vùng tương ứng Nm và

Nn.

Một số thuật toán tiêu biểu cho hướng tiếp cận này là Tab-stop.

c) Ưu điểm

- Có thể áp dụng với các loại trang tài liệu có cấu trúc phức tạp vì thuật

toán này không quan tâm đến việc phân đoạn các thành phần cơ sở, mà chỉ

chia trang tài liệu thành các vùng hình chữ nhật và xem xét giá trị trung bình

của nó. Như vậy các trang tài liệu có thể bỏ qua khâu xác định và hiệu chỉnh

độ nghiêng

- Có thể áp dụng cho các loại trang tài liệu có nhiều loại font chữ khác

nhau

- Tốc độ thực hiện nhanh hơn so với Top-down và Bottom-up

d) Nhược điểm

- Hiệu quả của thuật toán phụ thuộc vào giá trị trung bình của vùng

được xét, trong một số tình huống thì giá trị trung bình của vùng văn bản và

vùng đồ họa là như nhau. Cho nên thuật toán này vẫn có thể phân đoạn nhầm.

- Không có một giá trị hằng số τ cho mọi trang tài liệu vì thế việc xác

định giá τ là một vấn đền khó.

2.1.4. Đánh giá và lựa chọn thuật toán.

Từ những phân tích trên cho thấy ưu điểm của hướng tiếp cận bottom-

up là nhược điểm của hướng tiếp cận Top-down và ngược lại. Do đó, trong

những năm gần đầy đã có nhiều các thuật toán phát triển theo hướng lai ghép

(Hybrid) giữa top-down và bottom-up, một trong các thuật toán tiêu biểu như

Tab-Stop [14], ...Các thuật toán dựa trên phương pháp bottom-up để xác định

các đường phân tách (ví dụ như, các khoảng trắng hình chứ nhật, các tab-stop,

...), từ đó suy ra cấu trúc tổng quát của trang ảnh. Sau đó, thuật toán sử dụng

phương pháp bottom-up cùng với các đường phân tách để xác định các vùng

chữ. Các thuật toán lai ghép đã khắc phục được hạn chế của hướng tiếp cận

Top-down đó là có thể thực hiện được các trường hợp trang ảnh có cấu trúc

ảnh non-Mahattan và hướng tiếp cận bottom-up. Điểm mẫu chốt của các thuật

toán Hybrid là xác định các đường phân tách. Tuy nhiên, việc xác định các

khoảng trắng phân tách lại là một bài toán gặp phải rất nhiều khó khắn bởi

nhiều lý do, ví dụ như có những vùng chứ ở quá gần nhau, các vùng chứ được

căn lề trái phải không thẳng hàng hoặc khoảng cách giữa các thành phần liên

thông là quá lớn,... điều này đã làm cho các thuật toán hiện tại thường mắc

phải các lỗi quên hoặc xác định nhầm các đường, phần. Để phân tách một

trang ảnh tài liệu thành các vùng dữ liệu thuần nhất, đối với nhiều thuật toán

tiên tiến đã sử dụng tập tất cả các phân tách được trình bày trên từng trang

ảnh tương ứng.

Các thuật toán phân tách trang hiện nay đều phụ thuộc rất nhiều vào kết

quả của quá trình lọc khoảng trắng, chỉnh góc nghiêng, tức là các tham số

điều kiện để quyết định các khoảng trắng có được giữ lại hay không, góc

nghiêng có phù hợp hay không.

Ta thấy trong hướng tiếp cận Top-down có thuật toán Whitespace là

thuật toán tương đối nổi tiếng bởi vì nó khá đơn giản nhưng nó lại rất hiệu

quả trong việc phát hiện nền trang ảnh và đã có trong bộ mã nguồn mở

OCROpus. Hiện tại có rất nhiều các thuật toán sử dụng nó như là một trong

các bước cơ bản để phát triển thuật toán. Cho nên việc tiếp tục nghiên cứu và

cả tiến nó là một vấn đề có ý nghĩa thực tiễn.

2.2. Thuật toán phân tích trang tài liệu Whitespace

2.2.1. Giới thiệu

Có nhiều hướng tiếp cận khác nhau để giải quyết bài toán phân tích cấu

trúc vật lý trang ảnh tài liệu (phân đoạn trang). Hướng tiếp cận dựa vào hình

chiếu (e.g., RecursiveX-YCuts [17]) sử dụng hình chiếu ngang và dọc để chia

đệ quy trang thành các vùng hình chữ nhật nhỏ hơn. Hướng tiếp cận dựa vào

các phép biến đổi hình thái học (e.g., Run-Length Smearing [16]) sử dụng các

phần tử cấu trúc để “nối” các đối tượng tiền cảnh của trang lại với nhau và từ

đó xác định các phân đoạn của trang. Hướng tiếp cận dựa vào phân tích cấu

trúc nền của trang (e.g., Whitespace [6])cố gắng tìm các khoảng trắng hình

chữ nhật lớn nhất để phân tách các vùng trong trang. Hướng tiếp cận dựa vào

phân tích kết cấu (texture-base analysis) (e.g., Docstrum[14]) tìm cách xây

dựng các biểu đồ thể hiện mối tương quan giữa các thành phần liên thông để

gom nhóm chúng thành các vùng lớn hơn. Hoặc là tìm các tab-stop[15] để

phân tách các cột, sau đó gom nhóm các phần của cột thành các khối đồng

nhất.

Hướng tiếp cận dựa vào nền trang sử dụng các vùng hình chữ nhật để

miêu tả cấu trúc của nền.Theo một cách tự nhiên, các đối tượng tiền cảnh

thường được miêu tả bởi các hình chữ nhật, nên các khoảng trắng nền cũng sẽ

được miêu tả bởi một tập hợp các hình chữ nhật. Phương pháp miêu tả

trong[16] sử dụng quét dòng để tìm các khoảng trắng hình chữ nhật cục bộ

lớn nhất, sau đó mới lựa chọn các hình chữ nhật dựa trên một số tiêu chí tối

ưu. Mặc dù thuật toán quét này là hiệu quả nhưng khó thực thi (vì phải miêu

tả một cấu trúc hình học phức tạp và xem xét nhiều trường hợp đặc biệt) và

kết quả trả về không theo thứ tự (không biết được cái nào là tốt nhất, xấu

nhất).Một thuật toán dễ thực thi và kết quả trả về được sắp xếp theo thứ tự

được miêu tả trong [16].

Mặc dù thuật toán Whitespace cho kết quả tốt tuy nhiên thuật toán

Whitespace phụ thuộc rất nhiều vào việc lựa chọn bộ các tham. Trong luận

văn này tôi sẽ trình bày tóm tắt lại thuật toán và chủ yếu đi sâu vào đánh giá

sự ảnh hưởng của tham số đến kết quả phân tích của thuật toán Whitespace.

Tiến hành một số thử nghiệm so sánh chứng minh trên 1600 trang ảnh của bộ

dữ liệu UW-III.

2.2.2. Whitespace Cover

2.2.2.1. Định nghĩa bài toán

Chúng ta xác định bài toán hình chữ nhật trắng cực đại như sau. Giả sử

rằng chúng ta có một tập hợp các hình chữ nhật C = {r0,..., r n } trong mặt

phẳng, tất cả được chứa trong một hình chữ nhật giới hạn đã cho r b. Trong

phân tích bố cục, ri sẽ thường tương ứng với các khung giới hạn của các thành

phần được kết nối trên trang, và hình chữ nhật giới hạn tổng thể r b sẽ đại diện

cho toàn bộ trang. Ngoài ra, giả sử rằng chúng ta có một hàm đánh giá cho

các hình chữ nhật Q : R4 → R thỏa mãn, cho bất kỳ hai hình chữ nhật r và r'

nào mà.

(1) r ⊂ r' → Q(r) ≤ Q(r')

Trong trường hợp được mô tả tại [14], hàm Q chỉ đơn giản là diện tích

của hình chữ nhật, điều được dễ dàng nhìn thấy thoả mãn điều kiện được nêu

trong Phương trình 1. Bài toán hình chữ nhật trắng cực đại là tìm một hình

chữ nhật r^ ⊂ rb nhằm tối đa hóa Q(T) trong số tất cả các hình chữ nhật có thể

r ⊂ rb, trong đó r không trùng với bất kỳ hình chữ nhật nào trong C. Hoặc,

được biểu diễn bằng ký hiệu toán học:

(2)

Trong

đó:

Hình 2.11: Hình minh họa bước đệ quy của thuật toán Cover khoảng trắng

phân nhánh - giới hạn. Xem giải thích ở nội dung văn bản.

2.2.2.2. Thuật toán

Như đã nói ở trên, có một số thuật toán cho các bài toán hình chữ nhật

trống cực đại, bao gồm các thuật toán từ hình học tính toán (ví dụ [15]) và

phân tích tài liệu (ví dụ [6]). Thật đáng tiếc, các thuật toán này thực hiện khá

phức tạp và không được sử dụng rộng rãi.

Thuật toán được trình bày trong bài viết này cho bài toán hình chữ nhật

trống cực đại có thể được sử dụng với những obstacles là các hình chữ nhật

bao quanh điểm hoặc ký tự.

Ý tưởng chính tương tự với các phương pháp sắp xếp nhanh hoặc

nhánh cận (quicksort or branch-and-bound methods). Nó được minh họa trong

Hình 2.1.1. Hình 2.1.1(a) cho thấy sự khởi đầu của thuật toán: chúng ta có

một giới hạn bên ngoài và một tập hợp các hình chữ nhật (obstacles). Nếu

không có obstacles nào được chứa trong giới hạn thì chúng ta đã hoàn thành

công việc: bản thân giới hạn là hình chữ nhật cực đại cho những obstacles.

Nếu một hoặc nhiều obstacles được chứa trong giới hạn, chúng ta chọn một

trong những hình chữ nhật này làm một “pivot” (Hình 2.1.1 (b)). Tốt nhất là

chọn một hình chữ nhật nằm ở trung tâm của giới hạn. Giả sử chúng ta biết

rằng hình chữ nhật cực đại không thể chứa bất kỳ obstacles, đặc biệt, nó

không thể chứa pivot. Do đó, có bốn khả năng giải bài toán hình chữ nhật

trắng cực đại: về bên trái và bên phải của pivot (Hình 2.1.1 (c)) hoặc ở trên và

bên dưới pivot (Hình 2.1.1 (d)). Chúng ta tính toán các obstacles chồng lấp

lên mỗi bốn hình chữ nhật phụ này và đánh giá một giới hạn trên về chất

lượng của các hình chữ nhật trống cực đại có thể có trong mỗi hình chữ nhật

phụ; do đặc tính đơn điệu (Phương trình 1), hàm chất lượng Q được áp dụng

cho các hình chữ nhật phụ đảm nhiệm vai trò của một giới hạn trên. Các hình

chữ nhật phụ và các obstacles và tính chất liên quan của chúng được xếp vào

một hàng đợi ưu tiên và các bước trên được lặp đi lặp lại cho đến khi hình chữ

nhật không chứa obstacles đầu tiên xuất hiện ở đầu hàng đợi ưu tiên; hình chữ

nhật này là giải pháp tối ưu tổng thể cho bài toán hình chữ nhật trống cực đại

theo hàm chất lượng Q. Thuật toán này được cho trong phần giả mã ở dưới.

Để có được n giải pháp tốt nhất, chúng ta có thể tiếp tục mở rộng các

nút từ hàng đợi ưu tiên cho đến khi chúng ta có được n giải pháp theo thứ tự

chất lượng giảm dần. Tuy nhiên, rất nhiều trong số những giải pháp này sẽ

chồng lấp lên nhau đáng kể. Biến thức tham lam sau của thuật toán cho việc

tìm kiếm n giải pháp tốt nhất đã giải quyết vấn đề này. Sau khi chúng ta tìm

thấy hình chữ nhật trống cực đại r^, chúng ta có thể thêm nó vào danh sách

các obstacles và tiếp tục mở rộng. Khi chúng ta bỏ ra khỏi hàng đợi một trạng

thái tìm kiếm, chúng ta kiểm tra xem danh sách các obstacles có thay đổi

không, nếu có, tính toán lại chất lượng của nút và xếp lại nó vào hàng đợi.

Điều này sẽ tạo ra một Cover tham lam của khoảng trắng với các hình chữ

nhật cực đại và nhanh hơn đáng kể so với khởi động lại thuật toán.

Giả mã cho thuật toán như sau:

def find_whitespace(bound,rectangles):

queue.enqueue(quality(bound),bound,rectangles)

while not queue.is_empty():

(q,r,obstacles) = queue.dequeue_max() if

obstacles==[]: return r

= pivot = pick(obstacles) r0

r1 = (pivot.x1,r.y0,r.x1,r.y1)

r2 = (r.x0,r.y0,pivot.x0,r.y1)

r3 = (r.x0,pivot.y1,r.x1,r.y1)

(r.x0,r.y0,r.x1,pivot.y0) subrectangles =

[r0,r1,r2,r3] for sub_r in subrectangles:

sub_q = quality(sub_r) sub_obstacles =

[list of u in obstacles if not overlaps(u,sub_r)]

queue.enqueue(sub_q,sub_r,sub_obstacles)

Hơn nữa, thay vì nhấn mạnh vào một Cover của các hình chữ nhật tách

rời nhau hoàn toàn, chúng ta có thể cho phép một số trong số chúng chồng lấp

một phần hoặc hoàn toàn. Việc thực hiện tìm kiếm cẩn thận các hình chữ nhật

cực đại chồng lấp một phần này có thể đưa ràng buộc chồng lấp vào việc tính

toán giới hạn trên trong quá trình phân tách. Tuy nhiên, thuật toán chạy đủ

nhanh trên các bài toán thế giới thực, và số lượng các giải pháp chúng ta

mong muốn thường đủ nhỏ, nó là đủ chỉ đơn thuần là để tạo ra các hình chữ

nhật trống cực đại theo thứ tự chất lượng giảm dần bằng cách sử dụng thuật

toán chưa sửa đổi, thử nghiệm cho sự chồng lấp của bất kỳ giải pháp mới nào

với tất cả những giải pháp được xác định trước đó, và từ chối bất kỳ giải pháp

mới nào chồng lấp quá nhiều với một giải pháp đã tìm thấy trước đây.

Một ứng dụng của thuật toán này cho việc tìm kiếm một lớp bọc tham

lam của một tài liệu từ cơ sở dữ liệu UW-III với các hình chữ nhật trống cực

đại được biểu thị trong Hình 2.2. Thời gian tính toán cho các cài đặt tham số

xuất hiện thường xuyên bằng cách sử dụng một thuật toán xử lý C++ trên một

máy tính xách tay 400MHz là dưới một giây. Do vậy, thuật toán này có thể

được sử dụng như là một sự thay thế treo cho thuật toán Cover khoảng trắng

được sử dụng bởi [14], và nó sẽ rất hữu ích cho bất cứ ai quan tâm đến việc

thực hiện loại hệ thống phân đoạn trang này. Tuy nhiên, dưới đây, bài viết này

mô tả một cách dùng thay thế của thuật toán có sử dụng các tiêu chí đánh giá

khác nhau.

Hình 2.12: Áp dụng thuật toán tìm kiếm dòng ràng buộc cho các biến thức mô phỏng của một trang.

Các lề bên trong (obstacles) đã được tìm thấy tự động bằng cách sử

dụng thuật toán được mô tả trong bài viết này và được thể hiện bằng màu

xanh lá cây. Các dòng văn bản đã được tìm thấy bằng cách sử dụng công cụ

tìm kiếm dòng ràng buộc và được thể hiện bằng màu đỏ nhạt. (a) Hai cột lân

cận có định hướng khác nhau (điều này thường xảy ra ở hai bên gáy của một

cuốn sách được quét). (b) Hai cột lân cận có kích cỡ phông chữ khác nhau, và

kết quả là, các đường cơ sở không xếp thành hàng.

Thuật toán phân tích trang Whitespace được Breuel miêu tả trong [15]

bao gồm các bước chính sau:

1. Tìm và phân loại các thành phần liên thông (CCs) thành ba nhóm

dựa vào kích thước: nhóm lớn là các đối tượng hình ảnh, đường kẻ,… nhóm

vừa là các đối tượng ký tự, nhóm nhỏ là các đối tượng nhiễu, dấu của ký tự,…

Từ CCs của nhóm vừa, ước lượng chiều cao của dòng (x-height) và khoảng

cách giữa các ký tự, các từ và các dòng để tìm các bộ tham số cho thuật toán.

2. Tìm các khoảng trắng hình chữ nhật lớn nhất (gọi là các cover) dựa

vào CCs và hình bao của trang ảnh tài liệu. Hai cover này có thể chồng lên

nhau nhưng không quá ngưỡng t (t = 95% diện tích của cover tốt nhất)

3. Từ các cover tìm được, lọc lấy các cover dọc (các gutter) phân tách

các cột và các cover ngang (các hspace) phân tách các đoạn dựa trên một số

tiêu chí: kích thước và sự chồng gối lên nhau của các cover và mật độ CCs

liền kề với cover…

4. Tìm các phân đoạn trang bằng cách áp dụng thuật toán tìm cover ở

bước 2. Lúc này, các CCs được thay thế bằng các gutter và hspace.Để đảm

bảo các phân đoạn trang không được trùng nhau, với mỗi phân đoạn trang vừa

tìm được sẽ được cập nhật như một CC và tiếp tục tìm các phân đoạn trang

tiếp theo.

Như vậy, điểm mấu chốt trong thuật toán Whitespace là thuật toán tìm

các cover (thuật toán WCover). Tư tưởng chính của thuật toán WCover là

phương pháp nhánh cận, từ một hình bao (của trang) và một tập hợp các hình

chữ nhật (CCs) thuật toán có gắng chia hình bao thành các miền con sao cho

không chứa hình chữ nhật nào trong đó. Cụ thể, thuật toán bao gồm các bước

1. Tìm một CC làm điểm chốt “pivot”, sao cho, càng gần tâm của hình bao

càng tốt (Hình 2.13: Fig. 1.b).

2.13: Fig. 1.c,d).

2. Chia hình bao làm bốn miền con: left, right, top, bottom so với pivot (Hình

3. Nếu miền con không chứa bất kỳ CC nào thì nó là một cover.

4. Ngược lại, lặp lại bước 1 và 2 với các miền con.

Hình 2.13: Fig. 1.Mô tả thuật toán WCover [16]. (a) hình bao và các hình chữ nhật, (b) điểm chốt tìm được (c,d) các miền con trai/phải và trên/dưới

Vì các cover có thể chồng nhau nên chỉ cần tìm n-cover tốt nhất là có

thể miêu tả được cấu trúc nền của trang (có thể phân đoạn được trang). Để tìm

n-cover tốt nhất, Breuel đã sử dụng một hàng đợi ưu tiên để lưu các miền con

cần xét (tiêu chí ưu tiên là dựa trên diện tích của miền con [15]. Như vậy n-

cover tốt nhất tìm được sẽ được sắp xếp theo thứ tự.

2.3. Ảnh hưởng của tham số đến kết quả phân tách của thuật toán

Whitespace

2.3.1. Tham số về tỉ lệ chồng lấp (giao nhau) của các hình chữ nhật trắng.

Thuật toán cho việc tính toán Cover khoảng trắng có thể được sử dụng

như là một sự thay thế treo dễ thực hiện cho phương pháp được sử dụng trong

[14]. Trong quá trình thực hiện công việc này, các hình chữ nhật với tỉ lệ co

nhất định được ưa thích hơn, và, nói chung, các hình chữ nhật trắng lớn được

ưa thích hơn những hình nhỏ. Hàm đánh giá của chúng dựa trên các trắc

lượng thống kê về sự phân bố của các hình chữ nhật trắng trong các tài liệu

thực tế, và nó được thiết kế nhằm ưu tiên cho những hình chữ nhật là các dấu

phân cách ngang hoặc dọc có ý nghĩa.

Để kiểm tra sự thực hiện của các hàm đánh giá dựa trên phạm vi, tỉ lệ

co, và vị trí trên trang, các thuật toán độ bao phủ trắng mô tả ở trên được áp

dụng cho các khung giới hạn các ký tự có được từ hình ảnh tài liệu trong cơ

sở dữ liệu UW-III. Đối với mỗi hình ảnh tài liệu, một tập hợp 200 hình chữ

nhật trắng lớn nhất với sự chồng lấp theo cặp dưới 80% được tách ra. Đúng

như mong đợi, điều này tạo ra một tập hợp các hình chữ nhật trắng gần như

luôn luôn bao phủ hoàn toàn phông nền, cộng với các hình chữ nhật trắng bổ

sung vào đoạn văn bản. Để đi đến một phân tích bố cục, một hàm đánh giá là

cần thiết cho phép chúng ta chỉ chọn các hình chữ nhật mà sự kết hợp của

chúng tạo thành các khoảng trắng tách các thành phần của bố cục tài liệu.

Để có được một hàm đánh giá như vậy, một cây quyết định được đào

tạo để ước tính xác suất mà một hình chữ nhật trắng đã cho trở thành một

phần của nền trang. Không có đánh giá chính thức về nỗ lực thực hiện, nhưng

việc kiểm tra trực quan cho thấy rằng một phần đáng kể của các tài liệu trong

cơ sở dữ liệu UW-III không thể được phân đoạn hoàn toàn bằng cách sử dụng

phương pháp tiếp cận này. Theo báo cáo trong [15], các hình chữ nhật trắng

cao thường được phân loại chính xác, nhưng đối với các hình chữ nhật trắng

rộng (những hình tách các đoạn văn hoặc các phần với các đoạn, phần khác),

một số lượng đáng kể các lỗi dương và âm đã xảy ra. Hệ thống của Ittner và

Baird giải quyết những vấn đề này bằng cách tính toán các hình chữ nhật

trắng rộng nhưng bỏ qua các hình chữ nhật rộng giả cho đến các giai đoạn xử

lý sau này (chúng không được tính là không chính xác trong đánh giá phương

pháp). Hơn nữa, kiểm tra trực quan cho thấy rằng không có các quy tắc hay

hàm đánh giá chỉ dựa trên hình dạng của các hình chữ nhật trắng mà sẽ hoạt

động đáng tin cậy trong mọi trường hợp - cơ sở dữ liệu UW-III có chứa sự đa

dạng của các tài liệu mà ở đó có sự mơ hồ cố hữu.

Điều này có nghĩa rằng, trong khi các hàm đánh giá chỉ dựa trên hình

dạng của hình chữ nhật trắng có thể hữu ích và đáng tin cậy cho các tập tài

liệu nào đó, đối với các tập không đồng nhất, có lẽ chúng ta cần một phương

pháp khác. Tóm lại, các kết quả này gợi ý dùng một phương pháp phân loại

khoảng trắng cao riêng biệt và xem xét các tính năng ngoài hình dạng và vị trí

của các hình chữ nhật trắng trong việc đánh giá nó. Hơn nữa, một số quan sát

cho thấy khoảng trắng rộng, mặc dù đôi khi nhìn rất nổi bật, là không cần

thiết và cũng không đủ để phân tích bố cục trang tài liệu theo trục thẳng đứng.

Ví dụ, ngắt đoạn được chỉ định trong nhiều tài liệu kiểu Mỹ bằng cách thụt

đầu dòng, không phải là thêm khoảng trắng, chuyển từ tiêu đề tài liệu sang

thân bài hầu hết được chỉ định bằng các thay đổi trong căn chỉnh (căn lề giữa,

căn lề trái, căn lề phải), và một số đề mục được chỉ định không phải bằng giãn

cách thêm mà là những thay đổi trong kích thước và kiểu phông chữ.

Điều này sau đó dẫn đến quy trình bốn bước sau đây cho phân tích bố cục

trang tài liệu:

1. Tìm kiếm các hình chữ nhật trắng cao và đánh giá chúng như ứng viên cho

lề bên trong, dấu tách cột, v.v…

2. Tìm kiếm các dòng văn bản có cấu trúc dạng cột của tài liệu.

3. Nhận biết cấu trúc bố cục theo chiều dọc (đầu đề, tiêu đề, đoạn văn) dựa

trên mối tương quan (thụt đầu dòng, kích thước, giãn cách, v.v…) và nội

dung (kích thước và kiểu phông chữ, v.v…) của các dòng văn bản liền kề.

4. Xác định thứ tự đọc bằng cách sử dụng cả thông tin hình học và thông tin

ngôn ngữ học.

2.3.2. Tham số về khoảng trắng tối đa trong trang văn bản

Một thuật toán cho việc tìm kiếm các dòng văn bản khi có những trở

ngại. Những “trở ngại” hóa ra lại là các hình chữ nhật bao gồm Cover khoảng

trắng được phát hiện bởi thuật toán được mô tả trong phần trước và các tiêu

chuẩn đánh giá được mô tả trong phần tiếp theo. Thuật toán tìm kiếm dòng

ràng buộc cũng được liên kết với thuật toán được mô tả trong phần trước bằng

một phương pháp tiếp cận thuật toán tương tự: phân nhánh và giới hạn.

Bài toán mà Tìm kiếm dòng ràng buộc giải quyết trong phân tích tài

liệu là như sau. Nhiều tài liệu chứa văn bản có nhiều cột. Một số tài liệu hoặc

hình ảnh tài liệu thậm chí có thể chứa văn bản ở nhiều định hướng khác nhau,

có thể là do cách trình bày tài liệu phức tạp, hoặc (thông thường hơn) do hai

trang đối diện của một cuốn sách đã được quét tại những vòng quay hơi khác

nhau trong cùng một hình ảnh. Do đó, các dòng văn bản ở gần nhau có thể

vẫn có các tham số dòng khác nhau. Một số trường hợp được minh họa trong

Hình 2.3.

Các phương pháp tiếp cận truyền thống cố gắng giải quyết các trường

hợp này bằng cách tìm ra một phân đoạn trang hoàn chỉnh và chính xác và sau

đó thực hiện tìm kiếm dòng trong mỗi khối văn bản; tức là, chúng có cách tiếp

cận theo thứ bậc từ trên xuống dưới. Đáng tiếc là, việc tìm kiếm một phân

đoạn trang hoàn chỉnh và chính xác mà không có nhận biết về cấu trúc dòng

là rất khó khăn. Các giải pháp tích hợp tổng thể cho phân tích bố cục, giống

như những giải pháp được đề xuất bởi Liang và các cộng sự [15] tránh được

vấn đề này, nhưng dường như rất phức tạp để thực hiện và cho đến nay vẫn

chưa được ứng dụng rộng rãi.

Tìm kiếm dòng ràng buộc cung cấp một lựa chọn đơn giản hơn. Một

công cụ tìm kiếm dòng ràng buộc chỉ cần một danh sách các trở ngại mà các

dòng văn bản không đi qua. Những trở ngại này thường là các lề bên trong, và

một vài yếu tố đồ họa như hình minh họa hay các đường nhỏ thẳng đứng. Dựa

trên các kết quả được trình bày dưới đây, việc tìm kiếm lề bên trong dường

như là một bài toán đơn giản hơn nhiều so với một phân tích bố cục hoàn

chỉnh (thậm chí nếu chỉ là tạm thời), và ngay cả những bố cục phức tạp cũng

có xu hướng có một cấu trúc lề đơn giản (xem các ví dụ trong Hình 2.2). Các

lề bên trong này có thể được xác định dễ dàng bằng cách sử dụng phương

pháp Cover khoảng trắng được mô tả ở phần trước. Hơn nữa, phương pháp

tìm kiếm dòng ràng buộc được mô tả trong bài viết này cũng có thể được sử

dụng cùng với các kỹ thuật phân tích bố cục định hướng độc lập, cho phép

chúng ta tìm dòng văn bản với những định hướng tùy ý ngay cả trong văn bản

không được phân đoạn hoàn thiện.

Hình 2.14: Mô hình dòng văn bản được sử dụng tìm kiếm dòng ràng buộc.

Phương pháp tiếp cận tìm kiếm dòng ràng buộc là nền tảng của thuật

toán trong bài viết này trước đây đã được mô tả cho nhận dạng đối tượng hình

học [15], và được áp dụng cho tìm kiếm dòng văn bản [14]. Chúng ta hãy

biễu diễn mỗi ký tự trên trang bằng một điểm ở trung tâm dưới cùng của

khung giới hạn của ký tự đó (điểm căn chỉnh). Trong trường hợp không có

lỗi, đối với hầu hết các phông chữ Roman, mỗi điểm như vậy hoặc nghỉ trên

đường cơ sở hoặc nghỉ trên một đường thẳng song song với đường cơ sở, tức

đường hạ xuống phía dưới. Điều này được minh họa trong Hình 4.

Để tìm kiếm sự phù hợp “tối ưu” của các mô hình dòng văn bản đối với

khung giới hạn của một trang, chúng ta sử dụng một mô hình bình phương tối

thiểu mạnh mẽ. Đó là, sự đóng góp của mỗi ký tự đến điểm số phù hợp tổng

thể của một dòng văn bản bị cản trở bởi bình phương khoảng cách của điểm

căn chỉnh từ đường cơ sở hoặc đường hạ xuống phía dưới, lên đến một

ngưỡng. Điểm số phù hợp này tương ứng với một sự phù hợp tối đa có khả

năng xảy ra khi xuất hiện lỗi Gaussian trên vị trí và khi có một phông nền

thống nhất của các tính năng nhiễu âm, như thể hiện trong tài liệu [16].

Hãy giả định rằng các dòng được tham số hóa bằng khoảng cách r của

chúng từ gốc và hướng θ của pháp tuyến của chúng. Một tham số bổ sung, d,

cho khoảng cách của dòng của phần hạ thấp từ đường cơ sở. Ba thông số (r, θ,

d) này sau đó xác định một mô hình dòng văn bản. Nếu các điểm căn chỉnh

của tất cả các thành phần được kết nối trên trang được cho bởi {p1,... ,pn} ⊂ tập

conR2, chúng ta có thể biểu diễn chất lượng của hàm phù hợp (liên quan đơn

điệu đến hợp lý logarit) như sau:

(3)

Trong đó, dist (·, ·) là khoảng cách Ơ-clit và φ là một hàm ngưỡng

(4)

Tối đa hoá Q(r, θ, d) trên tất cả các thông số cho chúng ta giải pháp tối

ưu tổng thể cho bài toán tìm kiếm dòng không ràng buộc. Đối với bài toán tìm

kiếm dòng ràng buộc, chúng ta xem xét các đoạn dòng thay vì các dòng và

yêu cầu tìm kiếm một đoạn dòng tối đa mà không giao với bất kỳ trở ngại đã

cho nào.

Hình 2.15: Minh họa bài toán tìm kiếm dòng ràng buộc với những trở ngại.

Hình chữ nhật là trở ngại và các dấu chấm biểu diễn cho các điểm được

phù hợp bởi một dòng. Hai dòng ứng cử được thể hiện: một đường gạch phù

hợp với bốn điểm nhưng bị chặn lại bởi trở ngại, một đường gạch khác phù

hợp với năm điểm và gần như tránh được trở ngại.

Một thuật toán cho việc tìm kiếm các giải pháp tối ưu tổng thể cho bài

toán tìm dòng văn bản không ràng buộc đã được trình bày trong [14], dựa trên

công trình nghiên cứu trước đây về các phương pháp phân nhánh-giới hạn cho

sự phù hợp hình học [16]. Chúng ta sẽ xem xét ngắn gọn phương pháp không

ràng buộc ở đây.

Ý tưởng cơ bản là xem xét các tập con hình chữ nhật (các khung; tích

Đề các của các khoảng tham số dòng) của không gian ba chiều của các tham

số dòng văn bản và tính toán các cận trên của giá trị hàm chất lượng có thể

đạt được qua các tập con này. Các tập con với cận trên lớn được chia nhỏ

thành các tập con nhỏ hơn và được đánh giá lại. Cuối cùng, các tập con hình

chữ nhật đạt tới trong quá trình này đủ nhỏ để giới hạn giải pháp tối ưu cho

bài toán tối ưu hóa có độ chính xác số mong muốn. Đây là một ví dụ về một

thuật toán phân nhánh-giới hạn.

Để thực hành các bài toán tối ưu hóa hình học, có hai khó khăn cần

phải vượt qua: đầu tiên, chúng ta cần tìm ra được một cận trên Q^ cho hàm

chất lượng Q trên một số vùng, và thứ hai, chúng ta cần tính toán được cận

trên đó một cách hiệu quả. [16] mô tả sự tính toán của hàm cận trên Q^ cho

một khung các thông số dòng [r, r] x [θ, θ]. Chúng ta hãy xem xét ngắn gọn

cách tiếp cận này ở đây. Bây giờ, để đơn giản hóa sự tranh luận, chỉ xem xét

đường cơ sở, không xem xét đường hạ xuống phía dưới.

Hãy xem xét vùng LB được quét ra bởi các dòng với các tham số chứa

trong các khung tham số B = [r, r] x [θ, θ]. Chúng ta sử dụng như là cận trên

Q^(LB) = max(r, θ)∈ B Q(r,θ). Tận dụng lợi thế của sự đơn điệu của φ∈ (x),

cận này có thể dễ dàng nhìn được thấy

(5)

(6)

def find_constrained_lines(linebox,points,obstacles):

queue.enqueue(quality(linebox,points),linebox,points,obstacles)

while not queue.is_empty():

(q,linebox,points,obstacles) = queue.dequeue_max() if

accurate_enough(linebox): return linebox

excluded_obstacles =

[list of obstacle in obstacles

if linebox.can_not_intersect(obstacle)] if

excluded_obstacles!=[]:

...split linebox at excluded obstacles and enqueue...

sublineboxes = split(linebox) for sub_linebox in sublineboxes:

sub_points =

[list of point in points

if point.may_match(line)] sub_q =

quality(sub_linebox,sub_points)

queue.enqueue(sub_q,sub_linebox,sub_points,obstacles)

Giả mã cho tìm kiếm sự phù hợp ràng buộc tối ưu tổng thể của một

mô hình dòng đối với một tập hợp điểm.

Vùng LB là một vùng hình nơ con bướm. Nó được giới hạn bốn cạnh

bởi các dòng cho bởi các giá trị cực trị của các khung tham số dòng. Cạnh thứ

năm được giới hạn bởi một vòng cung nhỏ. Để tính toán cận trên Q^(B),

chúng ta cần phải tính toán khoảng cách của một điểm p từ vùng này, hoặc ít

nhất là một cận dưới. Sự tính toán này có thể được đơn giản hóa bằng cách

giới hạn vòng cung bằng việc sử dụng một dòng thứ năm. Một cận dưới của

khoảng cách dist(LB, pi) sau đó có thể được tính bằng cách sử dụng tích năm

điểm và một tổ hợp các phép toán cực tiểu và cực đại, được mô tả chi tiết hơn

trong [16]. Để tính toán các dòng hạ thấp, chúng ta thay dist(LB, p) bởi min

(dist(LB, p), dist(L'B, p)), trong đó L'B là vùng hình nơ con bướm được quét ra

bởi đường hạ thấp song song với đường cơ sở (xem [14] để hiểu chi tiết hơn).

Kỹ thuật thứ hai khiến cho việc giải các bài toán phù hợp hình học bằng

cách sử dụng phương pháp phân nhánh-giới hạn đơn giản và hiệu quả là sử

dụng các danh sách phù hợp. Đó là, đối với mỗi khung B của các tham số

dòng, chúng ta duy trì một danh sách tất cả và chỉ các điểm căn chỉnh có đóng

góp khác không đối với hàm chất lượng Q. Chúng ta gọi danh sách này

“matchlist” (danh sách phù hợp). Khi khung B được chia nhỏ, chỉ những điểm

căn chỉnh trên danh sách phù hợp mới cần phải được xem xét.

Tính đến thời điểm này, phần này đã xem xét lại công trình nghiên cứu

trước đây về tìm kiếm dòng tối ưu tổng thể. Bây giờ chúng ta chuyển sang câu

hỏi làm thế nào để đưa những trở ngại hình học vào khung này để tìm kiếm

dòng văn bản. Khi tìm kiếm dòng văn bản có những trở ngại, chúng ta không

cho phép các phù hợp trong đó một mô hình dòng văn bản l r, θ, d cắt một trở

ngại. Điều này được minh họa trong Hình 5. Hình này cho thấy hai dòng ứng

cử (gạch ngang). Một dòng tránh các trở ngại và phù hợp với các điểm từ cả

hai phía. Dòng kia phù hợp hơn với các điểm trên một phía của các trở ngại,

nhưng không thể “nhặt” các điểm căn chỉnh ở phía bên kia của các trở ngại.

Thực tế, trong bài toán tìm kiếm dòng văn bản ràng buộc, các giải pháp là các

đoạn dòng văn bản chứ không phải các dòng vô hạn.

Hình 2.16: Ví dụ về kết quả đánh giá khoảng trắng để phát hiện các ranh giới cột trong tài liệu có bố cục phức tạp (các tài liệu A00C, D050, và E002 từ cơ sở dữ liệu UW-III). Lưu ý rằng ngay cả các bố cục phức tạp cũng được mô tả bởi một tập nhỏ các dấu tách cột.

Có lẽ thật đáng ngạc nhiên, việc kết hợp những trở ngại vào thuật toán

tìm kiếm dòng văn bản phân nhánh-giới hạn rất đơn giản và không làm gia

tăng đáng kể sự phức tạp của thuật giải các bài toán thường gặp trong thực tế.

Cách tiếp cận như sau. Trong khi đánh giá phân nhánh-giới hạn, chúng ta lần

lượt xem xét các khung nhỏ hơn của các tham số dòng B. Khi các khung này

lớn, một số dòng được bao hàm bởi các tham số của chúng có thể giao cắt với

một trở ngại và một số có thể không. Tuy nhiên, khi các khung tham số càng

nhỏ đi, tại một số điểm, các dòng tương ứng với các giá trị tham số sẽ hoặc là

tất cả giao cắt với một trở ngại hoặc tất cả sẽ không giao cắt với một trở ngại.

Trong trường hợp tất cả các dòng không giao cắt với một trở ngại, chúng ta

chỉ cần loại bỏ trở ngại ra khỏi sự cân nhắc trong các lần phân nhỏ tiếp theo

của khung tham số. Trong trường hợp tất cả các dòng giao cắt với một trở

ngại, chúng ta chia tập hợp các điểm căn chỉnh phù hợp tiềm năng thành hai

tập con, những điểm bên trái của trở ngại và những điểm bên phải của trở

ngại. Sau đó chúng ta tiếp tục tìm kiếm với cùng khung B của các tham số

dòng và hai danh sách phù hợp riêng biệt, danh sách phù hợp cho các điểm

căn chỉnh bên trái của trở ngại, và danh sách phù hợp cho các điểm căn chỉnh

bên phải của trở ngại. Thuật toán được đưa ra trong giả mã ở Hình 6.

Cách tiếp cận này đối với sự phù hợp dòng có các trở ngại sử dụng các

danh sách phù hợp không chỉ là một tối ưu hóa, mà còn để cấu trúc sự tìm

kiếm và loại bỏ các điểm ra khỏi sự cân nhắc. Các đoạn dòng mà thuật toán

tìm thấy hoàn toàn được xác định bởi tập hợp các điểm căn chỉnh trên một

danh sách phù hợp, các trở ngại, và dòng. Cách tiếp cận này có hiệu quả đáng

kể hơn là nếu chúng ta cố gắng tìm kiếm trực tiếp trong khoảng cách của đoạn

dòng. Để tìm kiếm các đoạn dòng không có trở ngại với các đường cơ sở, có

thể trước đây đã phải tìm kiếm trên một vùng tham số năm chiều, trong khi

phương pháp tiếp cận dựa trên việc hạn chế các danh sách phù hợp chỉ yêu

cầu một sự tìm kiếm trong vùng tham số ba chiều gốc. Kết quả là, bằng cách

sử dụng phương pháp tiếp cận này, việc tìm kiếm dòng văn bản có những trở

ngại tốn một khoảng thời gian xấp xỉ bằng thời gian tìm kiếm dòng văn bản

không có trở ngại.

Thuật toán hình học hữu ích trong việc thực hiện các hệ thống phân tích

hình ảnh tài liệu. Thuật toán cho việc tính toán Cover khoảng trắng có thể

được sử dụng như là một sự thay thế treo dễ thực hiện cho phương pháp được

sử dụng trong [14]. Trong quá trình thực hiện công việc này, các hình chữ

nhật với tỉ lệ co nhất định được ưa thích hơn, và, nói chung, các hình chữ nhật

trắng lớn được ưa thích hơn những hình nhỏ. Hàm đánh giá của chúng dựa

trên các trắc lượng thống kê về sự phân bố của các hình chữ nhật trắng trong

các tài liệu thực tế, và nó được thiết kế nhằm thiên vị cho những hình chữ

nhật là các dấu phân cách ngang hoặc dọc có ý nghĩa.