1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

PHAN VĂN THUẬN

NHẬN DẠNG CÁC BIỂU MẪU TÀI LIỆU

Chuyên ngành: Công nghệ thông tin.
Mã số: 1.01.10

LUẬN VĂN THẠC SỸ.

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. NGÔ QUỐC TẠO

HÀ NỘI – 2007


4

MỤC LỤC
MỞ ĐẦU

CHƢƠNG 1 - Tổng quan ..................................................................................... 9
1.1 Đặt vấn đề .......................................................................................................... 9
1.2 Nội dung và cấu trúc của luận văn ........................................................... 11

CHƢƠNG 2 - Khái quát một số phƣơng pháp phân vùng ảnh và khử
nghiêng ....................................................................................................................... 13
2.1 Tổng quan về xử lý biểu mẫu. ................................................................... 13

2.1.1 Các đặc trƣng của biểu mẫu .................................................................... 13
2.1.2 Quá trình xử lý biểu mẫu dựa trên Ngôn ngữ mô tả biểu mẫu ......... 13
2.1.3 Quá trình xử lý biểu mẫu dựa trên đăng ký biểu mẫu (Form
registration) .......................................................................................................... 15
2.1.4 Hệ thống xử lý biểu mẫu ......................................................................... 15

2.2 Các kỹ thuật thƣờng đƣợc sử dụng trong nhận dạng cấu trúc biểu
mẫu. .......................................................................................................................... 16
2.2.1 Chỉnh độ nghiêng của văn bản biểu mẫu.............................................. 17
2.2.1.1.
2.2.1.2.
2.2.1.3.
2.2.1.4.
2.2.1.5.
2.2.1.6.

Phân tích hình ảnh của phép chiếu .................................................. 18
Xác định góc nghiêng dựa vào biến đổi Hough .............................. 20
Phân cụm hàng xóm gần nhất .......................................................... 22
Sự tƣơng quan của các đƣờng thẳng ............................................... 24
Một số kỹ thuật tính góc nghiêng khác. .......................................... 25
Bảng tổng kết về các thuật tốn xác định góc nghiêng. ................. 27

2.2.2 Phân tích trang ........................................................................................... 28
2.2.2.1.
2.2.2.2.
2.2.2.3.
2.2.2.4.
2.2.2.5.


Các kỹ thuật phân vùng ký tự .......................................................... 30
Các kỹ thuật phân vùng trang văn bản. ........................................... 36
Các kỹ thuật kết hợp phân vùng/phân lớp ....................................... 41
Các kỹ thuật phân lớp khối .............................................................. 47
Bảng tổng kết về các kỹ thuật phân tích trang ................................ 54

CHƢƠNG 3 - Đề xuất giải pháp sử dụng biểu mẫu động .................... 59
3.1 Hệ thống xử lý biểu mẫu động. ................................................................. 59
3.1.1 Giới thiệu về hệ thống xử lý biểu mẫu.................................................. 59
3.1.2 So sánh với các phƣơng pháp truyền thống ......................................... 60
3.1.3 Phƣơng pháp nhân dạng cơ bản ............................................................. 61
3.1.4 Thiết kế hệ thống ...................................................................................... 62
3.1.4.1.
3.1.4.2.
3.1.4.3.
3.1.4.4.

Kiến trúc hệ thống ............................................................................ 62
Hệ thống chuẩn bị biểu mẫu ............................................................ 62
Hệ thống xử lý biểu mẫu .................................................................. 65
Ứng dụng ........................................................................................... 68

3.2 Các thuật toán xử lý ảnh áp dụng cho xử lý biểu mẫu động ............ 69


5

3.2.1 Khái niệm biểu mẫu động. ...................................................................... 69
3.2.2 Lƣợc đồ xử lý biểu mẫu động. ................................................................ 71
3.2.3 Các phƣơng pháp tách chữ viết tay ra khỏi khung điền. ................... 72

3.2.3.1.
3.2.3.2.

Tìm hiểu các thuật toán tách cơ bản. ............................................... 72
Tách chữ viết tay ra khỏi khung điền. ............................................. 73

3.2.4 Xác định vị trí các khung điền. ............................................................... 75
3.2.4.1.
3.2.4.2.

Phƣơng pháp chiếu. .......................................................................... 75
Phƣơng pháp bỏ qua các khoảng trắng............................................ 76

3.2.5 Xác định thông tin ẩn chứa trong các khung điền. ............................. 77

3.3 Các thuật toán khác áp dụng cho biểu mẫu động ................................ 77
3.3.1 Thuật tốn bóc viền .................................................................................. 78
3.3.2 Thuật tốn xác định góc nghiêng ........................................................... 82
3.3.2.1.
3.3.2.2.

Thuật tốn sử dụng phép chiếu ........................................................ 82
Thuật toán sử dụng đƣờng thẳng dày. ............................................. 88

3.4 Thực nghiệm ................................................................................................... 91
3.4.1 Môi trƣờng thực nghiệm .......................................................................... 91
3.4.2 Thực nghiệm đối với các thuật toán cơ bản trên biểu mẫu động ..... 91
3.4.2.1.
3.4.2.2.
3.4.2.3.


Thực nghiệm tách chữ viết tay khỏi khung điền. ........................... 91
Thực nghiệm xác định vị trí các khung điền thơng tin ................... 92
Thực nghiệm xác định cấu trúc điểm nhỏ trong từng khung ......... 93

3.4.3 Thực nghiệm đối với các thuật toán khác ............................................ 93
3.4.3.1.

Xác định góc nghiêng của ảnh theo phƣơng pháp chiếu................ 93

3.4.3.2. Thực nghiệm nhận dạng đƣờng thẳng dày ................................ 95

Kết luận ...................................................................................................................... 96
o

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


6

DANH MỤC HÌNH ẢNH
Hình 2.1: Lược đồ q trình xử lý biểu mẫu dựa trên Ngôn ngữ mô tả biểu mẫu ... 14
Hình 2.2: Một hệ thống xử lý biểu mẫu văn bản .................................................... 15
Hình 2.3: (a) Ảnh trước khi khử nghiêng; (b) Ảnh sau khi khử nghiêng ................. 18
Hình 2.4: (a), (b), (c) : Các đối tượng trên ảnh ; (d), (e), (f) : Phân cụm các đối
tượng [17] ............................................................................................................. 23
Hình 3.1. Phân tách chữ viết tay và các khung. ..................................................... 62
Hình 3.2. Hệ thống biểu mẫu động. ....................................................................... 62
Hình 3.3: Data set ................................................................................................. 65
Hình 3.4: Vùng mã hóa thơng tin ........................................................................... 65

Hình 3.5: Một minh họa về biểu mẫu động ............................................................ 66
Hình 3.6: Luồng xử lý ............................................................................................ 67
Hình 3.7: Hình ảnh của chấm nhỏ ......................................................................... 69
Hình 3.8: Một cấu trúc của khung ......................................................................... 69
Hình 3.9: Một biểu mẫu động ................................................................................ 69
Hình 3.10: Một số cấu trúc chấm nhỏ .................................................................... 70
Hình 3.11: Một lược đồ xử lý biểu mẫu động ......................................................... 71
Hình 3.12 : Khung trước khi tách .......................................................................... 74
Hình 3.13 : Khung sau khi đã tách chữ viết tay ..................................................... 74
Hình 3.14 : Chữ viết tay sau khi đã tách khung ..................................................... 74
Hình 3.15 : Phép chiếu theo chiều ngang .............................................................. 75
Hình 3.16 : Phép chiếu khung theo chiều dọc ........................................................ 75
Hình 3.17 : Phép chiếu theo chiều dọc các điểm ảnh ............................................. 77
Hình 3.18: Ảnh scan có đường viền màu đen ......................................................... 78
Hình 3.19: Các kiểu hình dạng khác nhau của cụm, mỗi màu tương ứng với một
cụm........................................................................................................................ 79
Hình 3.20: Mơ tả điểm lân cận trực tiếp ................................................................ 80
Hình 3.21: Mơ tả điểm lân cận .............................................................................. 80
Hình 3.22: Mơ tả điểm nối ..................................................................................... 81
Hình 3.23: Ảnh scan có đường viền màu đen và ảnh sau khi đã bóc viền đen ........ 82
Hình 3.24: (a) Ảnh scan, các đường màu đỏ là các đường chiếu ở góc nghiêng θ.
(b) Ảnh được xấp xỉ bởi các hình bình hành .......................................................... 84
Hình 3.25: (a) Ảnh scan. (b) (c) (d) Ảnh các đường chiếu đen và trắng ở các góc
nghiêng -2.50, -3.50, 20........................................................................................... 85
Hình 3.26: (a) Ảnh scan. (b) Ảnh sau khi chính xác góc nghiêng ........................... 87
Hình 3.27. Ảnh trước và sau khi xoay đúng chiều .................................................. 90
Hình 3.28. Phiếu trả lời được quét ngược chiều .................................................... 90


7


DANH MỤC BẢNG BIỂU
Bảng 2.1 Một số đặc tính của các kỹ thuật chỉnh góc nghiêng .............................. 28
Bảng 2.2 Sự phân lớp của các thuật tốn phân tích trang ....................................... 29
Bảng 2.3 Các đặc trƣng của các kỹ thuât phân vùng ký tự .................................... 55
Bảng 2.4 Các đặc trƣng của kỹ thuật phân vùng trang ........................................... 56
Bảng 2.5 Các đặc trƣng của các kỹ thuật kết hợp phân vùng/phân lớp ................... 57
Bảng 2.6 Các đặc trƣngcủa các kỹ thuật phân lớp khối .......................................... 58
Bảng 3.1: Character Type ...................................................................................... 64
Bảng 3.2 : Direction .............................................................................................. 64
Bảng 3.3: Kết quả thực nghiệm tách chữ ra khỏi khung điền bằng phép toán gán
nhãn ...................................................................................................................... 91
Bảng3.5: Kết quả thực nghiệm xác định vị trí các khung điền ............................... 92
Bảng 3.6: Kết quả thực nghiệm xác định cấu trúc điểm nhỏ .................................. 93
Bảng 3.7. Kết quả thực nghiệm xác định góc nghiêng với một số góc tiêu biểu .. 94
Bảng 3.8: Kiểm thử hiệu năng ............................................................................... 94


8

MỞ ĐẦU
Nhập dữ liệu tự động đang là bài toán ngày càng thu hút nhiều sự chú ý và
đầu tƣ nghiên cứu bởi vì đây thật sự là một vấn đề quan trọng, cần thiết do khả năng
áp dụng rộng rãi vào thực tế cũng nhƣ hiệu quả mà nó mang lại. Trong bài toán này,
khử nhiễu, khử nghiêng và phân vùng ảnh là một phần có vai trị đặc biệt quan
trọng. Chức năng của nó là chính xác ảnh, tách ra các vùng đƣợc nhập thông tin,
tách chữ viết tay ra khỏi khung điền thông tin để làm đầu vào cho module nhận
dạng chữ. Trong luận văn này chúng tơi trình bày một phƣơng pháp sử dụng “cấu
trúc các chấm nhỏ” để tạo ra các khung điền thông tin. Cấu trúc các chấm nhỏ này
đƣợc tạo ra bởi rất nhiều các chấm nhỏ hoặc các đoạn thẳng nhỏ. Phƣơng pháp của

chúng tơi có những đặc điểm nổi bật sau:
 Khơng cần thiết kế biểu mẫu có màu sắc mà vẫn tách các ký tự chữ
viết tay ra khỏi khung điền.
 Dễ dàng tách phần chữ viết tay ra khỏi khung điền một cách nhanh
chóng và dễ dàng bằng các thuật toán xử lý ảnh đơn giản, đặc biệt
trong các trƣờng hợp chữ viết tay đè lên khung.
 Chi phí cho xử lý biểu mẫu là thấp
 Không cần biết trƣớc vị trí logic của các khung điền chữ và tìm cách
xử lý tự động các ký tự trong khung ..
Chúng tôi đã tiến hành thực nghiệm trên nhiều mẫu biểu mẫu động và thu
đƣợc những kết quả rất khả quan.
Từ khóa – Xử lý ảnh, Phân tích trang tài liệu, Nhận dạng, Biểu mẫu, Phép tốn
hình thái, Active form.


9

CHƢƠNG 1 - Tổng quan
1.1 Đặt vấn đề
Trong thực tế, cơng việc nhập dữ liệu chiếm một chi phí khá lớn do khối
lƣợng dữ liệu phải nhập và công sức bỏ ra để đảm bảo việc nhập có độ chính xác
cao. Vì thế từ lâu vấn đề nhập liệu tự động đã đƣợc đầu tƣ nhiều. Nguồn dữ liệu phổ
biến nhất là các văn bản trên giấy, do đó giải pháp chủ yếu là phải lấy ảnh và nhận
dạng. Nhận dạng là bài toán đã xuất hiện khá lâu và đã đạt đƣợc nhiều thành tựu to
lớn. Tuy nhiên nhận dạng một văn bản bất kì bao gồm cả các văn bản có lẫn chữ
viết tay hay hình ảnh ln là một bài tốn khó và hiện nay vẫn chƣa thật sự có giải
pháp hồn chỉnh.
Trên thế giới, hiện đã có nhiều ứng dụng liên quan đến vấn đề nhận dạng
văn bản hay nhập dữ liệu tự động. Có thể kể đến nhƣ : sản phẩm FineReader, Scan
To Office của hãng ABBYY, Smart scan Xpress của Pegasus Image, các ứng dụng

chấm thi tự động …Ở Việt Nam cũng đã có các ứng dụng nhận dạng văn bản nhƣ
VNDocR của Viện Công nghệ Thông tin hay ImageScan của CardPro. Đây là các
ứng dụng nhận dạng chữ in. Việc nhận dạng chữ viết tay đang còn là một thách
thức. Một số nghiên cứu về nhận dạng chữ viết tay đã đƣợc thực hiện tại Viện
CNTT và Bộ môn Công nghệ Phần mềm. Tuy nhiên các ứng dụng này hiện vẫn còn
rất nhiều hạn chế do khả năng nhận dạng chữ viết tay chƣa đạt đƣợc độ chính xác
cần thiết để có thể áp dụng rộng rãi trên thực tế.
Có hai đối tƣợng văn bản cần nhận dạng có đặt trƣng khác nhau địi hỏi có
các phƣơng pháp xử lý khác nhau. Đó là nhận dạng văn bản phi cấu trúc và nhận
dạng văn bản kiểu biểu mẫu với các dữ liệu chữ đƣợc sắp xếp trong những vùng xác
định. Cùng với sự phát triển của công nghệ xử lý ảnh hiện nay, các thuật tốn nhận
dạng ngày càng chính xác và đƣa ra đƣợc các kết quả đáng tin cậy. Ngay cả đối với
chữ viết tay cũng có thể đạt đƣợc độ chính xác cao với điều kiện là chỉ nhận dạng
từng chữ riêng biệt và chữ viết đẹp. Với các văn bản thơng thƣờng, ta khó có thể đạt


10

đƣợc điều này. Tuy nhiên, các biểu mẫu nhập liệu là kiểu văn bản có cấu trúc và ta
có thể đƣa ra một số quy tắc ràng buộc để tăng độ chính xác cho việc nhận dạng chẳng hạn nhƣ: các chữ đƣợc viết riêng rẽ trên các ô riêng biệt của các vùng nhập
liệu. Mặt khác, việc nhận dạng chữ viết khơng cần thiết phải tiến hành trên tồn bộ
ảnh của tài liệu mà chỉ giới hạn ở những vùng nhập dữ liệu. Đặc điểm này cũng cho
phép ta tiếp cận bài tốn một cách có hiệu quả hơn, chẳng hạn có thể sử dụng các
thơng tin sẵn có từ thiết kế biểu mẫu làm tham số nhận dạng. Một khía cạnh khác
của nhận dạng biểu mẫu tài liệu là các dữ liệu nhận dạng đƣợc của mỗi vùng của
biểu mẫu sẽ phải đƣợc tự động gắn vào một trƣờng dữ liệu xác định của ứng dụng.
Luận văn này chỉ giới hạn tập trung trình bày về quá trình nhận dạng các
vùng dữ liệu, trích chọn ra chữ viết tay để đƣa vào module nhận dạng chữ tiếng
Việt. Cụ thể, chúng tôi đề xuất sử dụng “biểu mẫu động” và các thuật toán xử lý
trên biểu mẫu động, bao gồm xác định các khung điền thông tin, tách chữ viết tay ra

khỏi khung điền, mã hóa thơng tin vào khung điền, giải mã các thông tin từ khung
điền dựa vào cấu trúc các điểm nhỏ. Thêm vào đó, chúng tơi cũng sẽ đề xuất một
số thuật tốn hỗ trợ để nâng cao tỉ lệ nhận dạng đúng. Các giải pháp thực nghiệm
bao gồm các công việc cụ thể nhƣ sau:
 Các thuật toán xử lý biểu mẫu động :
- Thuật tốn xác định các khung điền thơng tin.
- Thuật tốn tách chữ viết tay ra khỏi khung điền thơng tin và ngƣợc lại.
- Thuật tốn giải mã các thơng tin.
 Các thuật tốn nâng cao độ chính xác:
-

Thuật tốn bóc biên.

-

Thuật tốn chỉnh độ nghiêng dựa vào phép chiếu.

-

Thuật toán chỉnh độ nghiêng dựa vào đƣờng thẳng dày.


11

 Thực nghiệm
- Thử nghiệm độ chính xác của các thuật toán.
- Đánh giá kết quả, hiệu quả của thuật toán và nhận xét.

1.2 Nội dung và cấu trúc của luận văn
Bài toán con đƣợc thực hiện trong khoá luận này là bài toán phân vùng ảnh

và tách ra đƣợc các chữ viết tay để phục vụ cho module nhận dạng chữ viết tay.
Nắm bắt đƣợc khó khăn cũng nhƣ những đặc trƣng của bài tốn này, chúng tơi đã
áp dụng một giải pháp mới, đó là sử dụng biểu mẫu động, có độ chính xác cao trong
việc tiền xử lý biểu mẫu, phân vùng và tách ra đƣợc các chữ viết tay để nhận dạng.
Với nội dung chính là trình bày những lý thuyết cơ bản về tiền xử lý ảnh,
phân vùng ảnh khóa luận đƣợc tổ chức nhƣ sau:
Chƣơng 1: Tổng quan
Phần đầu của chƣơng giới thiệu về bài tốn nhập dữ liệu tự động nói chung:
tình hình Việt Nam và thế giới, các thành tựu đã đạt đƣợc trong lĩnh vực nhận dạng
chữ viết, những khó khăn cũng nhƣ các đặc trƣng của bài toán nhận dạng biểu mẫu
nhập dữ liệu so với các bài toán nhận dạng khác. Phần tiếp theo giới thiệu về hệ
thống chung mà chúng tôi đang tiến hành nghiên cứu và xây dựng: nghiên cứu và
xây dựng hệ thống nhập dữ liệu tự động bằng nhận dạng hình ảnh, phạm vi giới hạn
và quy trình giải quyết bài tốn. Từ đó nêu lên nội dung mà chúng tôi nghiên cứu và
thực hiện trong bài toán chung.
Chƣơng 2: Tổng quan một số phƣơng pháp phân vùng ảnh và khử nghiêng
Chƣơng hai trình bày về các phƣơng pháp phân vùng ảnh, khử nghiêng, các
khái niệm và tầm quan trọng của khử nghiêng và phân vùng ảnh trong nhận dạng
biểu mẫu. Chƣơng này cũng xác định các ƣu nhƣợc điểm và phạm vi áp dụng của
mỗi phƣơng pháp để từ đó lựa chọn giải pháp thích hợp.
Chƣơng 3: Đề xuất giải pháp sử dụng biểu mẫu động


12

Chƣơng này trình bày về phần việc chính mà tơi đã thực hiện trong đề tài
chung: Giải pháp sử dụng hệ thống xử lý biểu mẫu động cho việc phân vùng ảnh và
tách chữ viết tay. Nội dung của chƣơng tập trung vào:
 Đƣa ra các khái niệm về biểu mẫu động và hệ thống xử lý biểu mẫu
động.

 Trình bày các thuật toán cơ bản ứng dụng cho việc nhận dạng biểu mẫu
động.
 Đánh giá ƣu và nhƣợc điểm của các thuật tốn này.
 Mơ tả chi tiết q trình thực nghiệm các thuật tốn đã đề xuất.
Chƣơng 4: Kết luận
Chƣơng bốn tổng kết lại những kết quả đạt đƣợc và những việc cần đƣợc
tiếp tục thực hiện trong tƣơng lai.


13

CHƢƠNG 2 - Khái quát một số phƣơng
pháp phân vùng ảnh và khử nghiêng
2.1 Tổng quan về xử lý biểu mẫu.
Biểu mẫu văn bản (Form document) là một loại văn bản “có mục đích”,
đƣợc sử dụng rất rộng rãi trong cuộc sống hàng ngày của chúng ta. Ví dụ, hàng
triệu các phiên giao dịch tài chính đƣợc thực hiện hàng ngày cùng với sự xuất hiện
của biểu mẫu văn bản nhƣ là các loại séc, giấy tờ thanh toán...Với thể loại văn bản
này, chúng ta có thể sử dụng các phƣơng pháp riêng biệt để hiểu về nó.

2.1.1 Các đặc trƣng của biểu mẫu
Biểu mẫu có một số đặc trƣng nhƣ sau:
 Nhìn chung, biểu mẫu bao gồm nhiều đoạn thẳng mà có chung hƣớng
theo chiều ngang hoặc theo chiều dọc.
 Những thông tin cần lấy từ biểu mẫu thƣờng là các thơng tin đƣợc điền
vào. Các vị trí điền thơng tin có thể đƣợc xác định thơng qua các đƣờng
thẳng đƣợc nhận dạng.
 Các chữ trong biểu mẫu thƣờng là: tập hợp các chữ in máy, tập hợp các
chữ in đƣợc viết bằng tay và tập hợp các chữ viết tay. Các kiểu chữ này
có thể đƣợc nhận dạng thông qua các kỹ thuật nhận dạng chữ viết tay.


2.1.2 Q trình xử lý biểu mẫu dựa trên Ngơn ngữ mơ tả biểu mẫu
Chúng ta biết rằng, q trình xử lý biểu mẫu có thể đƣợc thực hiện dựa trên
ngơn ngữ mô tả biểu mẫu (Form Description Language). Một sơ đồ khối của
phƣơng pháp này đƣợc thể hiện ở hình 1 dƣới đây. Mục đích của phƣơng pháp này
là trích chọn ra đƣợc các thông tin đƣợc gọi là item từ các biểu mẫu.


14

Để thu đƣợc các item từ biểu mẫu, bộ mô tả item đƣợc sử dụng. Giả sử ta
có ba tập hợp hữu hạn bao gồm tập hợp các quan hệ Γ = {Γ1, Γ2, ...,Γk} giữa tập hợp
các item α = {α1, α2, ....,αm} và tập hợp các đồ thị Σ = {Σ1, Σ2, ...,Σn} và nó có thể
đƣợc thể hiện bởi ma trận 0-Γi. Chúng ta gọi nó là ma trận mô tả Item: MID, nhƣ là :

l if ( i , j )  
M ID  

0 if ( i , j )  
thoả mãn điều kiện sau:

l (l  ()),   R, L, A, B
trong đó R, L, A, B thể hiện cho thứ tự phải, trái, trên, dưới.
DV

GTC

DH

GTN


DS

GTM

B
PV

PH

PL

L

R

1

L

2

I
A

..

B

n


L

1
2

..

m

1
W

2

..

k

Hình 2.1: Lược đồ quá trình xử lý biểu mẫu dựa trên Ngôn ngữ mô tả
biểu mẫu


15

2.1.3 Quá trình xử lý biểu mẫu dựa trên đăng ký biểu mẫu (Form
registration)
Một hệ thống xử lý biểu mẫu có thể phát triển dựa trên việc đăng ký trƣớc
các biểu mẫu trống. Quá trình xử lý bao gồm hai bƣớc:
(1) Đăng ký biểu mẫu trống.

(2) Nhận dạng các dữ liệu điền trong biểu mẫu.
Trong bƣớc đăng ký, một biểu mẫu, ví dụ chƣa điền thơng tin gì sẽ đƣợc
qt và đƣợc đăng ký với máy tính. Thơng qua việc nâng cao chất lƣợng đƣờng
thẳng (line), trích chọn đƣờng viền và xác định góc vng thì cả dữ liệu và nhãn của
nó sẽ đƣợc trích chọn ra. Các mối quan hệ giữa những vùng điền thông tin đƣợc xác
định. Giao tiếp giữa con ngƣời và máy tính đƣợc địi hỏi trong suốt quá trình đăng
ký. Kết quả của quá trình đăng ký đƣợc lƣu trữ nhƣ là dữ liệu định dạng của biểu
mẫu ví dụ. Trong suốt bƣớc đăng ký biểu mẫu, chỉ các vùng dữ liệu đƣợc chích
chọn để xác đinh vị trí của các vùng này.
2.1.4 Hệ thống xử lý biểu mẫu
Compression

Document
image
acquisition

Document
classification

Document
library

Data extraction
& OCR

Image
database

Document
overlay


Coded
database

Hình 2.2: Một hệ thống xử lý biểu mẫu văn bản


16

Ở đây, một hệ thống xử lý biểu mẫu thông minh (IFPS) đƣợc trình bày. Hệ
thống này cung cấp các khả năng về:
 Tự động đánh chỉ số cho biểu mẫu về viêc lƣu trữ/truy vấn từ thƣ viện
biểu mẫu.
 Nắm bắt đƣợc thơng tin về hình ảnh biểu mẫu đƣợc quét, sử dụng OCR.
 Khả năng lƣu trữ rất hiệu quả dữ liệu hình ảnh biểu mẫu sau khi đƣợc
qt.
IFPS bao gồm 6 thành phần chính:
 Mơ hình định nghĩa biểu mẫu.
 Lƣu trữ mơ hình biểu mẫu trong một thƣ viện biểu mẫu.
 Kết nối biểu mẫu đầu vào dựa vào mơ hình đƣợc lƣu trữ trong thƣ viện
biểu mẫu.
 Đăng ký mơ hình đƣợc chọn cho biểu mẫu đầu vào.
 Chuyển đổi dữ liệu ảnh đƣợc trích chọn thành mã ký hiệu cho đầu vào
của cơ sở dữ liệu.
 Loại bỏ phần chỉ số của một biểu mẫu và giữ lại chỉ phần điền dữ liệu
trong việc lƣu trữ.
Mục đính chính của luận văn này là tập trung vào việc nhận dạng và phân
tích cấu trúc biểu mẫu văn bản cịn nhiệm vụ nhận dạng chữ khơng nằm trong
khn khổ của luận văn này. Do đó ở phần tiếp theo, chúng ta sẽ tìm hiểu các thuật
tốn nhận dạng thực hiện việc này.


2.2 Các kỹ thuật thƣờng đƣợc sử dụng trong nhận dạng cấu
trúc biểu mẫu.
Mục đích của q trình nhận dạng và phân tích cấu trúc biểu mẫu là xác
định, phân lớp các vùng trên ảnh biểu mẫu, liên kết chúng với các biến kiểu dữ liệu
và cuối cùng là biểu diễn lại chúng dƣới dạng cấu trúc logic (logic structure).


17

2.2.1 Chỉnh độ nghiêng của văn bản biểu mẫu
Khi một biểu mẫu đƣợc in và sau đó đƣợc quét vào máy tính thì việc hình
ảnh của biểu mẫu bị nghiêng đi là vấn đề không thể tránh khỏi. Để xác định đƣợc
góc nghiêng của biểu mẫu nói riêng hay của văn bản nói chung là khó và thƣờng
gặp phải những khó khăn sau:
 Góc nghiêng để có thể nhận dạng đƣợc bị giới hạn.
 Kích cỡ và kiểu của font chữ trong biểu mẫu bị giới hạn.
 Phụ thuộc vào cấu trúc của biểu mẫu: sự có mặt kết hợp của các hình vẽ,
đƣờng phân cách, bảng biểu sẽ gây ra nhiều vấn đề.
 Chỉ thực hiện đƣợc trên một số độ phân giải cho trƣớc của ảnh.
 Chi phí tính tốn cao.
 Giới hạn trên một số ứng dụng nhất định.
 Yêu cầu các vùng text phải rộng.
 Hơn nữa, hầu hết các thuật toán áp dụng cho văn bản chữ in sẽ không
chạy đƣợc đối với văn bản chữ viết tay.
Hầu hết các kỹ thuật xác đinh góc nghiêng có thể phân chia thành các lớp
chính nhƣ sau:
1. Phân tích hình ảnh của phép chiếu (projection profiles)
2. Biến đổi Hough
3. Phân cụm các phần tử kết nối (connected component clustering)

4. Sự tƣơng quan giữa các đƣờng thẳng
Ngoài các thuật tốn đƣợc xếp vào 4 lớp trên cịn có một thuật xác định độ
nghiêng khác nhƣ là:
 Xác định độ nghiêng dựa vào phân tích phổ Fourier.
 Xác định độ nghiêng dựa vào phân tích Gradient.


Các thuật tốn liên quan đến biến đổi hình thái (morphological)


18

 Xác định độ nghiêng dựa vào xác định các đƣờng thẳng trong các
phân vùng....

Hình 2.3: (a) Ảnh trước khi khử nghiêng; (b) Ảnh sau khi khử nghiêng
2.2.1.1. Phân tích hình ảnh của phép chiếu
Những tiền đề cơ bản của các phƣơng pháp tiếp cận này là giải quyết văn
bản trong trƣờng hợp các dòng văn bản đủ dài, thẳng và nằm song song với nhau.
Lƣợc đồ tính tốn cơ bản của phép chiếu là phụ thuộc vào từng góc nghiêng, định
nghĩa của một hàm đối tƣợng, và việc lựa chọn góc nghiêng đƣợc thực hiện thơng
qua hàm này. Với u cầu giảm bớt độ phức tạp tính tốn khi thực hiện, hàng loạt
các thuật toán khác nhau dựa trên cơ sở phép chiếu đã đƣợc đƣa ra. Mục đích của
các thuật toán này là giảm thiểu khối lƣợng dữ liệu tham gia vào q trình tính tốn
hoặc là nâng cao chiến lƣợc tìm kiếm điều kiện tốt nhất cho việc xác định góc
nghiêng.
Trong thuật tốn đƣợc đƣa ra bởi Postl [26], chỉ những điểm đầu mũi trên
lƣới văn bản đƣợc sử dụng để tính trong phép chiếu và khoảng cách giữa các đỉnh



19

lồi trên hình chiếu sẽ đƣợc tính tốn. Góc nghiêng sẽ đƣợc lựa chọn trong trƣờng
hợp tổng khoảng cách này là lớn nhất.
Thuật toán do Baird [27] đề xuất cũng không sử dụng tất cả các điểm ảnh
mà lựa chọn một số điểm để sử dụng trong phép chiếu: đầu tiên xác định từng thành
phần liên thơng, điểm chính giữa ở đáy của hình bao của mỗi thành phần liên thông
sẽ đƣợc sử dụng trong phép chiếu. Hàm xác định góc nghiêng sẽ tính tổng độ rộng
của các đáy lõm trên hình chiếu. Để tăng tốc độ trong việc lựa chọn góc nghiêng
đúng nhất, một kỹ thuật lặp đƣợc thực hiện. Ở lần lặp đầu tiên, ta sẽ tính phép chiếu
mà mỗi lần thay đổi góc chiếu là lớn. Ở các lần lặp tiếp theo, với góc nghiêng thu
đƣợc từ lần lặp trƣớc, ta lại thực hiện lại phép chiếu nhƣng sự thay đổi góc chiếu là
nhỏ hơn...Thuật tốn này cho kết quả chính xác với tốc độ nhanh và hoạt động với
nhiều loại văn bản khác nhau: nhiều hình khối, bảng biểu, nhiều kích cỡ, kiểu chữ
khác nhau.
Thuật tốn của Ciardiello [28] chỉ sử dụng một vùng nhỏ trên trang văn bản
(đó là vùng có mật độ cao các điểm đen trên mỗi dịng) trong phép chiếu; và góc
nghiêng đƣợc chọn khi mà sự chênh lệch giữa đỉnh lồi và đáy lõm trong hình chiếu
là lớn nhất.
Thuật tốn do Ishitani [29] sử dụng phép chiếu mà hình chiếu đƣợc định
nghĩa theo cách khác. Đầu tiên, một tập hợp các đƣờng thẳng song song sẽ đƣợc xác
định và chỉ các đƣờng thẳng này sẽ đƣợc sử dụng trong phép chiếu. Góc nghiêng
đƣợc xác định trong trƣờng hợp mà độ dốc trong phép chiếu là lớn nhất. Phƣơng
pháp này chạy tốt trong trƣờng hợp các vùng rộng khơng có ký tự.
Bagdanow và Kanai [30] đƣa ra một kỹ thuật ứng dụng cho các ảnh văn bản
nén định dạng JBIG. Họ tìm kiếm các vệt đen liên thông của các điểm ảnh mà nó
khơng có các điểm đen hàng xóm ở phía dƣới: vệt đen bên phải lớn nhất đƣợc lựa
chọn. Những sự sắp xếp của các điểm ảnh này ứng dụng chuẩn pass mode trong
chuẩn nén CCITT4. Chúng có thể dễ dàng đƣợc xác định bởi việc phân tích



20

CCITT4 hoặc dựa vào chuỗi bit nén JBIG. Việc lựa chọn góc nghiêng tƣơng tự nhƣ
thuật tốn của Postl.
2.2.1.2. Xác định góc nghiêng dựa vào biến đổi Hough
Dựa vào biến đổi Hough, hàng loạt các kỹ thuật xác định góc nghiêng đƣợc
phát triển. Các kỹ thuật này dựa trên sự tìm kiếm những đặc tính khác biệt của văn
bản nhƣ là hƣớng của các ký tự, các dòng văn bản thƣờng song song với nhau.
Từng điểm đen (x,y) của ảnh đƣợc ánh xạ vào trong không gian Hough (ρ, θ), sử
dụng biến đổi ρ = x cos(θ) + y sin(θ). Các điểm ảnh thẳng hàng sẽ đem lại các đỉnh
trong khơng gian Hough. Góc nghiêng của phƣơng pháp này phụ thuộc vào góc
nghiêng của trục . Độ phức tạp của thuật tốn là tuyến tính đối với số lƣợng các
điểm biến đổi và sự thay đổi góc quay .
Srihari và Govindaraju [31] đã ứng dụng kỹ thuật này cho ảnh nhị phân mà
thoả mãn điều kiện ảnh chỉ có ký tự và các khối ký tự đều có chung một hƣớng.
Từng điểm đen đƣợc ánh xạ vào không gian Hough và góc nghiêng đƣợc xác định
trong trƣờng hợp tổng các điểm dọc theo thành phần ρ là lớn nhất.
Để cải thiện tốc độ tính tốn của kỹ thuật, hàng loạt các biến thể của thuật
toán đƣợc phát triển, chủ yếu là nhằm vào việc giảm bớt số lƣợng các điểm ảnh ánh
xạ vào khơng gian Hough. Việc này có thể đạt đƣợc nhờ:
 Sự lựa chọn tập hợp điểm ảnh đƣợc đại diện bởi một điểm ảnh.
 Giới hạn việc phân tích trên một phần của ảnh.
Hinds phát triển một thuật tốn xác định góc nghiêng mà giảm lƣợc phần
lớn số lƣợng điểm ảnh đƣợc ánh xạ vào không gian Hough. Ảnh văn bản có độ phân
giải là 300 dpi đƣợc chuyển đổi sang một ảnh phụ. Ảnh phụ đƣợc tạo ra bằng cách
thay thế 4 điểm đen liên thông theo chiều dọc bằng một điểm đen ở đáy của liên
thông, nhằm loại bỏ các thành phần không phải là ký tự. Biến đổi Hough đƣợc áp
dụng cho tất các các điểm ảnh trên ảnh phụ mà ảnh phụ này có kích thƣớc giảm di
25 lần so với ảnh gốc.



21

Spitz [23] mô tả một kỹ thuật giảm số lƣợng điểm ảnh đầu vào, hoạt động
trực tiếp trên ảnh nén CCITT 4. Các điểm ảnh tƣơng ứng với pass codes đƣợc chích
chọn với một singer pass trên tồn bộ ảnh nén và đƣợc ánh xạ vào không gian
Hough. Kỹ thuật này đƣợc mở rộng cho ảnh nén JBIG.
Le [34] mô tả một thuật toán xác định hƣớng của trang và độ nghiêng của
văn bản. Hƣớng của trang đƣợc xác định bằng cách phân chia ảnh thành các phần
vuông nhỏ, từng phần đƣợc xác định là có dữ liệu nguyên bản hay không nguyên
bản dựa vào các kỹ thuật nhân heuristic thông qua việc xác định mật độ và sự phân
tán của các điểm đen. Từng vùng nguyên bản đƣợc phân lớp nhƣ là hình, phong
cảnh bằng việc phân hình của các phép chiếu theo chiều dọc và chiều ngang. Việc
phân lớp phụ thuộc chủ yếu vào việc thay đổi của các đỉnh lồi so với các đáy lõm,
và sự so sánh sự biến đổi của các ảnh phép chiếu. Số lƣợng của các điểm đen trong
từng vùng nguyên bản sẽ đƣợc sử dụng nhƣ là kết quả phân lớp. Những vùng vng
này tạo thành lớp đầu tiên của một hình chóp; từng tầng tiếp theo đƣợc cấu tạo bởi
các vùng vuông lớn hơn, các vùng này đƣợc tạo ra bởi sự kết hợp của chín vùng
nhỏ hơn của tầng trƣớc. Đỉnh của hình chóp thể hiện cả trang văn bản. Thông tin về
việc phân lớp đƣợc truyền từ các tầng dƣới lên tới đỉnh: từng vùng đƣợc phân lớp,
trang văn bản đƣợc đặt nằm dọc hay nằm ngang, bằng một tiêu chuẩn phân lớp chủ
yếu giữa chín vùng dƣới và đƣợc truyền vào phần kết quả phân lớp. Góc nghiêng
đƣợc xác định thông qua các vùng nhỏ trên ảnh mà có kết quả phân lớp cao nhất
trong số chín vùng ở tầng thấp nhất của hình chóp. Biến đổi Hough đƣợc áp dụng
tính tốn cho các điểm đen ở hàng cuối cùng của mỗi thành phần liên kết.
Một kỹ thuật khác có thể giảm bớt dữ liệu tính tốn đƣợc đề xuất bởi Min
[35]. Ảnh văn bản đƣợc phân chia thành các vùng dọc từ trên xuống dƣới, độ rộng
của mỗi vùng phụ thuộc vào các đƣờng thẳng phân chia vùng và góc nghiêng lớn
nhất có thể. Trong từng vùng này, một vectơ đƣợc xây dựng bằng việc gán giá trị 1

cho dịng chứa ít nhất một điểm đen và giá trị 0 cho các trƣờng hợp ngƣợc lại. Các


22

điểm đen ở trung tâm của các vệt đen dọc của từng vectơ sẽ đƣợc ánh xạ vào không
gian Hough.
Pal và Chaudhuri [36] đƣa ra hai kỹ thuật xác định góc nghiêng khác. Kỹ
thuật thứ nhất thực hiện việc giảm thiểu dữ liệu tính tốn thơng qua tính các hình
vng bao phủ của các thành phần kết nối. Ý tƣởng cơ bản là xoá bỏ các thành phần
mang theo nhiễu: các ký tự to dần, nhỏ dần .... Các thành phần nhỏ đƣợc lọc bỏ nếu
nó có độ sâu nhỏ hơn độ sâu trung bình của các thành phần. Từ đây, hình thành hai
tập hợp điểm L1 và L2 tách biệt: L1 chứa các điểm ảnh ở bên trái phía trên nhất và
L2 chứa các điểm ảnh ở bên phải phía dƣới nhất của từng thành phần. Các điểm ở
trong L1 và L2 sẽ đƣợc sử dụng trong biến đổi Hough.
Một thuật tốn xác định góc nghiêng khác dựa vào biến đổi Hough đƣợc đề
xuất bởi Yu và Jain [37]. Bƣớc đầu tiên của thuật toán tập trung vào việc tính tốn
hiệu quả các thành phần liên thơng và trọng tâm của chúng dựa vào một cấu trúc gọi
là đồ thị liền kề khối. Biến đổi Hough đƣợc áp dụng cho các điểm trọng tâm này với
hai độ phân giải góc biến đổi khác nhau. Ở độ phân giải góc lớn cho phép chúng ta
tính xấp xỉ góc nghiêng, sau đó chúng ta sẽ tính chính xác đƣợc góc nghiêng thơng
qua lần tính biến đổi Hough lần 2 với độ phân giải góc mịn hơn. Thuật tốn này
chạy rất nhanh và chính xác đối với những ảnh có độ phân giải thấp.
2.2.1.3. Phân cụm hàng xóm gần nhất
Phƣơng pháp phân cụm hàng xóm gần nhất sử dụng để xác định góc
nghiêng của ảnh dựa trên việc xác định các cụm đối tƣợng gần nhau, ví dụ tiêu biểu
là các dịng chữ. Vì trong ảnh văn bản các đối tƣợng thƣờng đƣợc phân bố đều và
có hƣớng cùng với hƣớng của văn bản nên việc xác định các cụm đối tƣợng gần
nhau này giúp ta ƣớc lƣợng đƣợc góc nghiêng của ảnh.



23

Hình 2.4: (a), (b), (c) : Các đối tượng trên ảnh ; (d), (e), (f) : Phân cụm
các đối tượng [17]
Hashizume [38] thể hiện một kỹ thuật đi từ dƣới lên trên, dựa vào phân cụm
ngƣời hàng xóm gần nhất. Với từng thành phần, chúng ta tính hƣớng của đoạn mà
nó kết nối với những thành phần hàng xóm gần nhất. Các hƣớng này đƣợc tích luỹ
trong một histogram và giá trị lớn nhất của histogram sẽ cho giá trị của góc
nghiêng.
Một phƣơng pháp khác xác định góc nghiêng dựa vào tƣ tƣởng ngƣời hàng
xóm gần nhất đƣợc đề xuất bởi O’Gorman [39]. Tác giả tính tốn hình phổ tổng
hợp của trang văn bản, đƣợc gọi là docstrum, và dùng nó làm điểm xuất phát để
phân tích trang. Với từng thành phần kết nối tìm đƣợc trong trang văn bản, k thành
phần hàng xóm gần nhất đƣợc xác định. Một tập hợp các cặp đƣợc tạo thành từ bản
thân thành phần và với từng thành phần trong k hàng xóm gần nhất. Từng cặp thành
phần này đƣợc biến đổi trong bộ (d,ф), trong đó d là khoảng cách Euclidean và ф là
góc giữa hai điểm trung tâm của hai thành phần. Kết quả của tính tốn từng cặp này
sẽ đƣợc tổng hợp lại để tạo thành docstrum. Việc lựa chọn giá trị k là không giới
hạn, nhƣng giá trị k tốt có đƣợc phụ thuộc vào tính chất hình học của văn bản. Góc
nghiêng đƣợc xác định trong trƣờng hợp histogram phẳng nhất của góc ф.


24

Phƣơng pháp khác đƣợc trình bày bởi Smith [40] cũng dựa vào kỹ thuật
phân cụm các thành phần liên thông trong các dòng văn bản. Bƣớc đầu tiên là lọc
bỏ các thành phần nhỏ và chỉ giữ lại những thành phần có độ cao trong khoảng 20th và 95-th. Các thành phần còn lại đƣợc sắp xếp theo toạ độ các cột của chúng.
Trong từng dòng, các thành phần đƣợc phân chia vào các nhóm nhƣ sau: từng thành
phần mà có hƣớng theo chiều dọc trùng với các dịng đã tồn tại thì đƣợc tính. Nó

đƣợc đƣa vào tập hợp khoảng cách ngang giữa thành phần và dòng và đánh giá độ
nghiêng hiện thời của dòng. Thành phần hiện tại đƣợc sử dụng cho một dòng mới
hoặc một dòng đã có, phụ thuộc vào mức độ trùng nhau theo chiều dọc. Với từng
phân cụm, góc nghiêng của dịng đƣợc tính thơng qua giá trị của ít nhất một trung
tuyến của các vùng. Góc nghiêng tồn cục đƣợc tính thơng qua độ nghiêng của
trung tuyến này.
Pal và Chaudhuri [36] trình bày một cách tiếp cận khác dựa vào phân cụm
của hai tập hợp điểm, L1 và L2, đƣợc chích chọn từ trong ảnh. Hai tập hợp này đƣợc
phân tích tách biệt nhau nhƣ sau: một đƣờng thẳng khởi tạo đƣợc xác định bởi việc
tìm kiếm ba điểm gần nhau và thẳng hàng trong tập hợp bắt đầu từ đỉnh của ảnh.
Các điểm của tập hợp sau đó đƣợc phân cụm theo khoảng cách của chúng tới đƣờng
thẳng khởi tạo. Với từng phân cụm, độ dốc của vùng tham gia bởi hai điểm xa nhất,
sẽ xác định độ nghiêng xấp xỉ. Độ nghiêng tồn cục đƣợc tính theo trung bình của
các độ nghiêng tính trong L1 và L2.
2.2.1.4. Sự tƣơng quan của các đƣờng thẳng
Chúng ta nhận thấy rằng, độ nghiêng của vùng văn bản thể hiện một cấu trúc
đồng nhất theo chiều ngang, do vậy những kỹ thuật này sẽ tập trung vào việc xác định
độ nghiêng của ảnh thông qua tính tốn những độ lệch góc dọc theo hình ảnh.
Akiyama và Hagita [41] mơ tả một thuật tốn xác định nhanh góc nghiêng:
văn bản đƣợc chia thành nhiều các vùng dọc bằng nhau về độ rộng. Tại mỗi vùng,
một phép chiếu theo chiều ngang đƣợc thực hiện dọc theo sự nghiêng nhằm mục
đích đem lại mối tƣơng quan tốt nhất của từng phép chiếu thực hiện trƣớc đó. Độ


25

nghiêng đƣợc xác định nhƣ là sự nghịch đảo của phép tính tỉ lệ giữa độ dốc trung
bình và độ rộng của vùng.
Phƣơng pháp đƣợc mô tả bở Yan [42] có những điểm thú vị là nó có thể sử
dụng trực tiếp cho ảnh đa cấp xám hay ảnh màu mà cũng tƣơng tự nhƣ xử lý đối với

ảnh nhị phân và nó khơng u cầu phải chích chọn ra đặc trƣng của các thành phần.
Phƣơng pháp này dựa vào việc tính tốn hàm tƣơng quan tích luỹ R cho nhiều phần
của các đƣờng thẳng dọc, đƣợc lựa chọn với khoảng cách cố định D. Nó đƣợc định
nghĩa nhƣ sau: R(s) =Σx,y I(x+D, y+s)I(x,y) với phép tính tơng đƣợc tính trên tồn
ảnh I. Góc nghiêng đƣợc tính bằng nghịch đảo của phép tính tang giữa giá trị s lớn
nhất của R(s) và D.
Gatos [33] đề xuất một kỹ thuật tính góc nghiêng dựa trên mối tƣơng quan
đo lƣờng giữa các vùng dọc của ảnh đã đƣơc tiền xử lý làm mịn theo chiều ngang.
Các vùng dọc có diện tích bằng nhau và có độ rộng đƣợc xác định qua thực nghiệm.
Với mỗi vùng, một hàm đƣợc xây dựng và gán giá trị 1 cho dịng mà có ít nhất 1
điểm đen và bằng 0 cho trƣờng hợp ngƣợc lại. Và với từng cặp hàm (Li, Lj), một ma
trân tƣơng quan đƣợc thiết lập: Ci,j(r, λ) = Li(r).Lj(r+λ), trong đó λ thể hiện sự thay
đổi theo chiều dọc. Một ma trận mối tƣơng quan chung đƣợc tạo ra bằng cách tổng
hợp các ma trận Ci,j. Một phép chiếu dọc theo trục λ sẽ giúp chúng ta tính đƣợc góc
nghiêng.
2.2.1.5. Một số kỹ thuật tính góc nghiêng khác.
Sauvola và Pietikainen [44] đề xuất một phƣơng pháp tính góc nghiêng dựa
vào phân tích hƣớng Gradient, có thể áp dụng cho ảnh nhị phân hoặc ảnh đa cấp
xám. Ảnh đƣợc sử dụng hai mặt nạ để lấy ánh xạ gradient (biên độ và hƣớng). Các
hƣớng trội của từng ơ trong lƣới sẽ đƣợc tính và sử dụng các thông tin gradient.
Lƣợc đồ Histogram của các hƣớng này đƣợc tính sau sự lƣợng tử hố góc. Giá trị
lớn nhất của lƣợc đồ Histogram kết quả sẽ cho chúng ta góc nghiêng văn bản.


26

Một kỹ thuật tƣơng tự đƣợc trình bày bởi Sun và Si [45]. Chúng ta biết rằng
trong một văn bản điển hình sẽ tồn tại nhiều điểm mà có hƣớng gradient là vng
góc với các dịng văn bản. Lƣợc đồ histogram của hƣớng gradient của ảnh đa cấp
xám đƣợc tính. Lƣợc đồ histogram này sau đó đƣợc làm nhẵn với lọc trung tuyến để

giảm các hiệu ứng phụ liên quan đến lƣợng tử hố. Mơ hình của lƣợc đồ histogram
sẽ cho chúng ta tính tốn đƣợc góc nghiêng.
Một kỹ thuật khác đƣợc đƣa ra bởi Postl [26]: tính biến đổi Fourier của
trang văn bản và thơng qua các đặc tính của hình phổ Fourier để tìm ra góc nghiêng.
Lấy S(u,v) là biến đổi 2-D Fourier của văn bản, và W(u,v) = |S(u,v)|2 là độ lớn của
phổ, thì kết quả đƣợc tính nhƣ là tập tuyến tính số nguyên của W(u,v) dọc theo
vector góc nghiêng β đối với trục tung v. Khi kết quả đạt đƣợc giá trị lớn nhất thì β
chính là góc nghiêng cần tìm.
Chen và Haralick [46] trình bày thuật tốn xác định góc nghiêng của văn
bản dựa vào sự dãn và co của biến đổi morphological [51]. Biến đổi co đƣợc thực
hiện đệ quy với các cấu trúc phần tử 2 x 2 hoặc 3 x 3, phụ thuộc vào việc đánh giá
giá trị góc nghiêng tới hạn. Ảnh kết quả đƣợc nhị phân hoá với ngƣỡng nhị phân
tìm đƣợc bằng cách tính histogram. Hoạt động này kết nối các ký tự, các từ và các
thành phần khác. Tuy vậy, một số từ ở các dòng khác nhau có thể kết nối với nhau,
do sự nhơ cao hoặc sự thụt xuống của một số ký tự. Biến đổi dãn đƣợc thực hiện đệ
quy trên ảnh kết quả, và vẫn sử dụng cấu trúc phần tử nhƣ trên. Ngƣỡng của ảnh kết
quả tạo ra một ảnh bitmap mà các dòng ký tự đƣợc thể hiện bởi các thành phần kéo
dài đã xác định đƣợc hƣớng. Các hƣớng này có thể là hƣớng sai bởi vì nhiễu, các
hình ảnh hoặc các thành phần tranh. Các đƣờng thẳng mà có hƣớng gần nhƣ nhau sẽ
đƣợc thu thập bởi một thuật tốn lặp. Góc nghiêng của trang văn bản sẽ đƣợc tính từ
tập hợp các hƣớng đƣợc lựa chọn này.
Một hƣớng tiếp cận khác rất thú vị đƣợc trình bày bởi Aghajan [47]. Việc
tính độ nghiêng văn bản đƣợc thực hiện thơng qua việc tính hƣớng đến của sóng
điện từ hai chiều đƣợc cảm nhận bởi một mảng cảm biến tuyến tính. Tại đỉnh của


27

các cột ảnh có các cảm biến ảo đo tín hiệu bởi một tập hợp các đƣờng thẳng trên
ảnh. Việc phân tích quang phổ của vector đo đƣợc thực hiện bởi kỹ thuật TLSESPRIT cho xử lý mảng. Thuật toán có khả năng xác định nhiều góc nghiêng thơng

và có thể chạy tốt trên ảnh nhị phân và ảnh đa cấp xám.
2.2.1.6. Bảng tổng kết về các thuật toán xác định góc nghiêng.
method

reference

input type

skew range / characteristics of documents

resolution

accuract;

Post! [26].1

b/w, gl.
160 dvi

±45° 0.6°

complex documents with a
dominant text direction

Baird [27]

b/w 300
dpi

±15° 0.05°


Ciardiello et
al. [28]
Ishitani [29]

b/w 300

±45° 0.70

dpi b/w
300
dvi b/w,
JBIG 300
dpi b/w
128 dpi

±3o 0.12°

a dominant text direction, a
few touching char acters, text
overwhelms non text
complex documents,
e.g. magazines
complex documents with few
text lines
documents with no or a few
non textual parts
text only documents

Projection

profile

Bagdanov
Krillai [30]
Srihari
Govindaraju
[31]
Hinds et al.
[32]
Lee et at [34]
Hough
transform

Nearest
Neighbor

Min et at
[35]

b/w 75 dpi

b/w 200
dpi
i b/w 300
dpi

±3°

±15° 0.5°


±200
0.5°

Pal Chaudhuri [36].1

b/w 160
dpi

±45° 0.2°

Yu .lain [37]

b/w 50-75
dpi

±90o

Hashizume
et al. [38]

b/w 54-63
dpi

±90o
5o

O’Gorman

b/w 300


±90o

0.1o

complex documents; an es
timate of max characters
height is needed
complex documents,
e.g. medical journals
noisy structured documents
with tables; an estimate of interline gaps is needed
complex documents with one
text direction, dominant tcxtual part., Roman script
complex documents with a
dominant text direction
Simple documents (e.g.
envelopes) with line gaps
wider than chacracter gaps
Text only documents with few