Số hóa bởi Trung tâm Học liệu



ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG









Nguyễn Cảnh Ân




PHƢƠNG PHÁP PHÁT HIỆN BẢNG
TRONG TÀI LIỆU TỔNG HỢP

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN













THÁI NGUYÊN- 2014





Số hóa bởi Trung tâm Học liệu



ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG










Nguyễn Cảnh Ân




PHƢƠNG PHÁP PHÁT HIỆN BẢNG
TRONG TÀI LIỆU TỔNG HỢP



Chuyên ngành : Khoa học máy tính
Mã số: 60 48 01



LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN





NGƢỜI HƢỚNG DẪN KHOA HỌC:


PGS.TS Ngô Quốc Tạo







THÁI NGUYÊN- 2014




Số hóa bởi Trung tâm Học liệu


MỤC LỤC
DANH MỤC CÁC HÌNH VẼ i
LỜI CẢM ƠN iii
MỞ ĐẦU 1
CHƢƠNG 1: HỆ PHÂN TÍCH TRANG TÀI LIỆU ẢNH VÀ BÀI TOÁN
PHÁT HIỆN BẢNG……………………………………………………………4
1.1. Giới thiệu chung hệ phân tích trang tài liệu và bài toán phát hiện bảng… 4
1.1.1. Quá trình thu nhận ảnh 7
1.1.2. Các bước xử lý điểm ảnh 8
1.1.2.1. Phương pháp nhị phân 8
1.1.2.2. Giảm nhiễu 10
1.1.2.3. Phân đoạn 11
1.1.2.4. Làm mảnh và xác định vùng 11

1.1.2.5. Mã hóa CC và véctơ hóa 13
1.1.3. Phân tích các đặc trưng của tài liệu ảnh 14
1.1.4. Phân tích các đối tượng văn bản trong tài liệu 15
1.1.4.1. Ước lượng độ nghiêng của văn bản 15
1.1.4.2. Phân tích sơ đồ trình bày của trang tài liệu 17
1.1.5. Nhận dạng ký tự quang học (OCR) 19
1.1.5.1. Trích chọn đặc trưng 21
1.1.5.2. Phân loại 22
1.1.5.3. Nhận dạng ký tự dựa trên ngữ cảnh 25
1.2. Bài toán phát hiện bảng 26
1.2.1. Mô tả bài toán 27


Số hóa bởi Trung tâm Học liệu


1.2.2. Một số hướng tiếp cận 29
1.3. Kết luận chương 30
CHƢƠNG 2: PHÂN TÍCH BẢNG DỰA TRÊN T-RECS 32
2.1. Phương pháp phát hiện bảng trong tài liệu ảnh 32
2.2. Giới thiệu thuật toán T-Recs 38
2.2.1. Các bước khởi tạo và phân đoạn của thuật toán 41
2.2.2. Trường hợp xác định sai cột của thuật toán 43
2.2.3. Cải tiến một số bước của thuật toán 44
2.2.4. Những ưu điểm của thuật toán 48
2.2.5. Những mặt hạn chế của thuật toán khởi tạo 49
2.3. Xử lý khối sau khi phân đoạn 51
2.3.1. Trộn các khối phân đoạn sai 51
2.3.2. Phân tách các cột bị trộn vào một khối 52
2.3.3. Nhóm các từ bị phân tách 55

2.4. Phân tích khối 56
2.5. Phát hiện cấu trúc các cột, hàng 57
2.6. Kết luận chương 58
CHƢƠNG 3: CHƢƠNG TRÌNH DEMO CỦA THUẬT TOÁN 59
3.1. Giới thiệu chung 59
3.2. Mô tả chương trình 60
3.3. Một số kết quả thử nghiệm 61
KẾT LUẬN 63
DANH MỤC CÁC TÀI LIỆU THAM KHẢO 66
i

Số hóa bởi Trung tâm Học liệu


DANH MỤC CÁC HÌNH VẼ
Hình 1.1
Sơ đồ khối của việc xử lý tài liệu
Hình 1.2
Các bước xử lý cho một hệ phân tích tài liệu, đi kèm sơ đồ là một
thí dụ với các kết quả thu được từ từng bước
Hình 1.3
Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám
nguyên bản. Trục ngang biểu diễn các giá trị ngưỡng được chọn.
Ảnh sau khi được nhị phân: (b) sử dụng ngưỡng thấp, (c) ngưỡng
hợp lý, (d) ngưỡng quá cao
Hình 1.4
Ảnh nguyên bản bên trái và ảnh sau khi làm mảnh bên phải.
(a) Ký tự “m”. (b) Một sơ đồ. (c) Vân tay……………………

Hình 1.5

Cửa sổ 3x3 điểm ảnh với điểm ảnh X nằm ở tâm. Các giá trị số
biểu diễn cho hướng mà một điểm láng giềng của X thuộc: 0
(hướng tây), 1(tây - bắc), 2(bắc), 3(đông - bắc), 4(đông), 5(đông
– nam), 6(nam), 7(tây – nam)
Hình 1.6
Văn bản bị nghiêng khi quét
Hình 1.7
Biểu đồ Histogram của phép chiếu ngang và dọc của ảnh (a) và
(b)
Hình 1.8
Kết quả phân tích cấu trúc và chức năng các khối
Hình 1.9
Để phân tách và nhận dạng hai số 4,2 có các nét nối liền nhau
như trên dễ gây nhầm lẫn
Hình 1.10
Các ký tự viết bằng tay sẽ rất dễ nhầm lẫn………………………
Hình 1.11
Các cấu trúc đặc trưng nét, tính lõm, lỗ hổng, các điểm cắt ngang
và kết thúc có thể được sử dụng làm các chiều của không gian
đặc trưng để phân loại ký tự
Hình 1.12
Các đặc trưng của ảnh ký tự được trích ra
ii

Số hóa bởi Trung tâm Học liệu


Hình 1.13
Một số nhầm lẫn giữa bảng và đối tượng khác
Hình 1.14

Khái niệm các thành phần trong bảng
Hình 2.1
Một số lỗi phổ biến của các thuật toán phát hiện cấu trúc bảng
Hình 2.2
Thuật toán phát hiện bảng dựa Tab-stop
Hình 2.3
Các từ láng giềng của từ “consist” theo chiều dọc
Hình 2.4
Thuật toán phân đoạn khởi tạo đối với một đoạn văn bản
Hình 2.5
Trường hợp thuật toán nhận dạng sai cột
Hình 2.6
Trường hợp giữa các dòng của một cột trong bảng có ô trắng
Hình 2.7
Mô tả kết quả thuật toán đã được điều chỉnh nhận dạng khối
Hình 2.8
Kết quả nhận dạng các cột từ hình 2.5
Hình 2.9
Mô tả quá trình phân khối của văn bản trong các cột có khoảng cách
rất hẹp
Hình 2.10
Trường hợp một ô của bảng chiếm nhiều dòng dữ liệu
Hình 2.11
Những mặt hạn chế của thuật toán
Hình 2.12
Trộn hai khối bị phân tách
Hình 2.13

(a):Tách các cột nhỏ trong cột lớn;(b):Trộn các khối nhỏ vào khối
lớn

Hình 2.14
Trộn các từ bị tách nhờ vào các đoạn thẳng canh lề
Hình 2.15
(a) Phân tích khối loại 1 thành cấu trúc các ô của bảng ; (b) Ô
khối loại 2 được phân tich nhờ vào ô khối loại 1
Hình 2.16

Tách các khối loại 2 thành các hàng trong bảng
Hình 3.1
Giao diện chương trình thử nghiệm
Hình 3.2
Kết quả nhận dạng khối của chương trình
Hình 3.3
Trường hợp nhận dạng có môi trường bảng
Hình 3.4
Nhận dạng ra các cột, các khối văn bản

iii

Số hóa bởi Trung tâm Học liệu


LỜI CẢM ƠN
Trong suốt thời gian làm luận văn vừa qua, dưới sự giúp đỡ và chỉ bảo nhiệt
tình của PGS.TS Ngô Quốc Tạo – Viện Công nghệ Thông tin – Viện Khoa học
và công nghệ Việt Nam, luận văn của em đã được hoàn thành. Mặc dù bản thân
đã cố gắng không ngừng cùng với sự tận tâm của thầy hướng dẫn song do thời
gian và khả năng cũng còn nhiều hạn chế nên luận văn cũng không tránh khỏi
những thiếu sót trong quá trình làm.
Để hoàn thành xong luận văn này, em xin bày tỏ lòng biết ơn sâu sắc tới

PGS.TS Ngô Quốc Tạo – người thầy đã tận tình hướng dẫn em trong quá trình
tìm hiểu, xây dựng và phát triển luận văn này.
Em 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 Khoa học và Công nghệ Việt Nam đã quan tâm, tạo điều kiện
thuận lợi, nhiệt tình giảng dạy và hướng dẫn em trong suốt hai năm học qua. Và
cuối cùng tôi xin gửi lời cảm ơn đến gia đình, cơ quan và toàn thể học viên lớp
K11I Ninh Bình đã quan tâm, động viên và giúp đỡ tôi trong suốt hai năm học
vừa qua.
Cuối cùng em rất mong nhận được sự chỉ dẫn, góp ý của các thầy cô giáo để
luận văn của em được hoàn thiện hơn.
Em xin trân trọng cảm ơn !

1

Số hóa bởi Trung tâm Học liệu




MỞ ĐẦU
Trong những năm gần đây, các thiết bị phần cứng máy tính phục vụ cho
công việc lưu trữ và xử lý hình ảnh đã phát triển vượt bậc cả về dung lượng lẫn
tốc độ xử lý. Đồng thời, giá cả của các thiết bị này cũng đã giảm đến mức con
người trên toàn thế giới dễ dàng sở hữu những thiết bị liên quan đến việc phân
tích và xử lý hình ảnh.

học máy tính. Các loại tài liệu lưu trữ trên giấy và xử lý theo các cách thức cũ
không theo kịp tốc độ phát triển của công nghệ. Những công việc ngày nay liên

quan đến các loại tài liệu không chỉ là các tài liệu chữ chỉ để lưu trữ mà tài liệu
bao gồm nhiều thành phần như các bảng biểu, ảnh…với số lượng khổng lồ tài
liệu và xử lý những nhiệm vụ phức tạp trên máy tính ngày càng nhiều. Những
công việc văn phòng hàng ngày đều liên quan đến tài liệu, một tài liệu không chỉ
đơn giản được lưu trữ mà nó cần phải được xử lý để có khả năng thay đổi, soạn
thảo, chỉnh sửa và trích chọn các thông tin quan trọng. Vì thế các hệ phân tích
tài liệu ra đời, mục đích của chúng là giúp biểu diễn thông tin trong các tài liệu
ảnh, tài liệu giấy được đưa vào từ máy quét dưới dạng có cấu trúc.
Lĩnh vực xử lý ảnh là một công việc có nhiều ứng dụng trong cuộc sống,
theo đó, một số nước phát triển trên thế giới như Nhật Bản, Trung Quốc, Pháp,
Mỹ, Canada đã không ngừng nghiên cứu phát triển công nghệ phần mềm liên
quan đến ngành nhận dạng và xử lý hình ảnh để khai thác triệt để lợi thế của sức
mạnh phần cứng hiện có. Cùng với sự phát triển công nghệ tri thức và nhận dạng
trên thế giới, Việt Nam ta cũng đang từng bước đầu tư và phát triển ngành nhận
dạng và xử lý ảnh. Điển hình là sự phát triển và ứng dụng mạnh mẽ của Viện
Khoa học công nghệ Việt Nam – Viện Công nghệ Thông tin Việt Nam. Tại Viện
2

Số hóa bởi Trung tâm Học liệu


đã có nhiều tác giả nghiên cứu và cải tiến một số thuật toán quan trọng liên quan
đến việc nhận dạng và phân tách các đối tượng khác nhau trong ảnh tài liệu. Từ
đó đưa ra được một số phần mềm ứng dụng thiết thực trong cuộc sống. Điển
hình là sản phẩm phần mềm Hệ nhận dạng quang học OCR, hay hệ nhận dạng
các chuỗi văn bản, bảng biểu VnDOCR.
Nhiều thuật toán ra đời và từng bước phát triển đã phục vụ đắc lực cho việc
đưa ra các ứng dụng khả thi vào cuộc sống cũng như góp phần xây dựng và bổ
sung kho tri thức khoa học công nghệ của thế giới. Điển hình về thuật toán nhận
dạng đối tượng trong ảnh tài liệu là thuật toán nhận dạng bảng theo phương pháp

tiếp cận dưới lên (bottom-up) được đề xuất bởi tác giả Thomas G.Kieninger
được đặt tên là T-Recs.
Phát hiện bảng và ảnh trong tài liệu ảnh là những bài toán khó và phức tạp.
Trước đây các hệ phân tích tài liệu ảnh chỉ tập trung vào nhận dạng các chuỗi ký
tự, phân đoạn các khối văn bản. Ngày nay tài liệu không chỉ đơn thuần là văn
bản mà nó còn bao gồm hỗn hợp những đối tượng các chuỗi ký tự, ảnh, các hình
vẽ, sơ đồ, các bảng biểu .v.v
Một số yếu tố cấu thành nên bảng biểu (structure of table) đó là các ô
(cells), các dòng (rows) và các cột (columns). Phát hiện bảng là bài toán phát
hiện ra các cột, các dòng, các ô của bảng biểu. Việc phân tích cấu trúc của ảnh
tài liệu có vai trò quan trọng rằng khi máy tính định hình được cấu trúc của ảnh
thì sẽ giúp ích cho việc phục vụ mang tính chất đầu cuối cho những công đoạn
xử lý khác, cũng như kết hợp xử lý tự động các dữ liệu thu thập được. Do đó,
khi đã phát hiện được một đối tượng (văn bản hay hình ảnh) thì việc phát hiện
luôn cả cấu trúc chứa đựng và liên quan với đối tượng đó là thật sự cần thiết.
Một trong những cấu trúc quan trọng phổ biến thường được sử dụng mà trong
luận văn quan tâm đề cập đến đó là việc phát hiện bảng biểu (detect table) trong
ảnh tài liệu
3

Số hóa bởi Trung tâm Học liệu


Trong phạm vi một đề tài luận văn thạc sĩ với chủ đề “Phƣơng pháp phát
hiện bảng trong tài liệu tổng hợp” tôi sẽ tìm hiểu một số phương pháp, kỹ
thuật phát hiện bảng trong tài liệu tổng hợp, đưa ra giải pháp cải tiến thuật toán,
hướng phát triển của thuật toán, xây dựng chương trình thử nghiệm.
Bố cục của luận văn ngoài phần mở đầu và phần kết luận bao gồm 3
chương. Chương 1 trình bày ngắn gọn cấu trúc chung của một hệ phân tích tài
liệu ảnh, bao gồm các thành phần chính như: lấy dữ liệu, xử lý điểm ảnh, trích

chọn đặc trưng và giới thiệu bài toán phát hiện bảng
Chương 2 đưa ra một thuật toán phát hiện bảng theo phương pháp tiếp cận
dưới – lên (bottom – up). Thuật toán được đề xuất bởi Thomas G .Kieninger
(1998) được đặt tên là T-Recs. Tuy nhiên để phát hiện được chính xác các cấu
trúc bảng thì thuật toán còn nhiều hạn chế. Luận văn sẽ chỉ ra trường hợp thuật
toán phát hiện sai và đưa ra giải pháp nâng cao độ chính xác khi phát hiện.
Cuối cùng chương 3 trình bày chương trình thử nghiệm: Nhận dạng bảng
theo cấu trúc dùng để nhận dạng bảng trong trang tài liệu tổng hợp.
Phần kết luận nêu tóm tắt lại các vấn đề được đưa ra trong luận văn và đưa
ra những vấn đề còn tồn tại để nâng cao tính hiệu quả của những thuật toán. Các
hướng giải quyết và nghiên cứu trong tương lai đối với những phương pháp này
cũng sẽ được đưa ra.








4

Số hóa bởi Trung tâm Học liệu









CHƢƠNG 1: HỆ PHÂN TÍCH TRANG TÀI LIỆU ẢNH VÀ
BÀI TOÁN PHÁT HIỆN BẢNG
1.1. Giới thiệu chung một hệ phân tích trang tài liệu và bài toán phát hiện bảng
Ảnh tài liệu sau khi được quét và lưu trữ trong máy tính dưới dạng các tệp
dữ liệu ảnh, chúng bao gồm các điểm ảnh (pixels) và mô hình giống như lưới
các điểm ảnh. Một vấn đề đặt ra cho chúng ta là trích chọn ra các thông tin đặc
trưng để máy tính có thể nhận biết được các dữ liệu này. Đây chính là nhiệm vụ
của một hệ phân tích trang tài liệu. Đó chính là một tập hợp các thuật toán và
các kỹ thuật để có thể phát hiện ra các đối tượng văn bản, đối tượng ảnh trong
ảnh tài liệu và có khả năng trích chọn ra các thông tin người dùng mong muốn.
Một trong những công nghệ đượ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). Phần
mềm này có khả năng 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 sang kiểu tập tin văn bản có khả năng soạn thảo và tìm
kiếm nội dung của tài liệu.
Như vậy, mục đích của hệ phân tích tài liệu là phát hiện ra được các đối
tượng khác nhau trong ảnh tài liệu như các đối tượng văn bản, hình ảnh… và
đưa ra được các thông tin người dùng mong muốn để phục vụ cho các mục đích
nghiên cứu, ứng dụng khác nhau. Và đặc biệt, trong phạm vi nghiên cứu của
luận văn này đi sâu về việc phát hiện bảng (detect table) trong ảnh tài liệu.
Trong các loại văn bản, tài liệu thì đối tượng bảng là thành phần quan trọng
trong một trang tài liệu tổng hợp, do đó trước hết việc phân tích sơ đồ trình bày,
5

Số hóa bởi Trung tâm Học liệu


cấu trúc trang là rất cần thiết để phục vụ cho việc xác định đối tượng bảng biểu.
Một trang tài liệu tổng hợp thông thường gồm có hai loại đối tượng chính là văn

bản và hình ảnh, trên cơ sở các công nghệ nhận dạng hiện nay thì một hệ phân
tích trang tài liệu sẽ thực hiện hai nhiệm vụ chính sau. Nhiệm vụ thứ nhất là xử
lý các đối tượng văn bản như ký tự, chuỗi ký tự, các từ. Nhiệm vụ thứ hai là xử
lý các đối tượng hình ảnh được tạo ra từ các hình vẽ, đường kẻ, biểu đồ, các
lôgô công ty…Sau khi thực hiện thành công hai nhiệm vụ chính trên thì hệ phân
tích trang tài liệu sẽ trích chọn ra các thông tin cần thiết đã phát hiện được và
được lưu lại dưới dạng định dạng tài liệu khác như Word,Html…
Ta có thể đưa ra sơ đồ khối liệt kê quá trình xử lý ảnh tài liệu như sau:



Hình 1.1: Sơ đồ khối của việc xử lý tài liệu.
Nguồn: Gorman(2009)

Trên thực tế chúng ta thấy việc thiết kế và ứng dụng được một hệ phân tích
tài liệu ảnh rất cần thiết, nó giúp chúng ta giải quyết nhiều vấn đề khi mà số
lượng dữ liệu lớn. Chúng ta có thể xem một số ví dụ cụ thể dưới đây để thấy
được sự cần thiết của việc phân tích trang tài liệu. Thứ nhất, thực tế khi ta làm
Xử lý tài liệu
Xử lý văn bản
Nhận dạng ký
tự quang học -
OCR
Phân tích sơ
đồ trình bày
Xử lý đối tượng ảnh
Xử lý
đường kẻ
Xử lý vùng và
biểu tượng

Văn bản
Xác định độ nghiêng,
dòng văn bản, các khối
văn bản, đoạn văn bản
Đường thẳng,
đường cong,
góc
Vùng được
tô
6

Số hóa bởi Trung tâm Học liệu


các công việc văn phòng thì hầu hết các tài liệu văn bản được tạo ra từ máy tính
nhưng các máy tính có thể được cài đặt các phần mềm khác nhau, do đó có thể
định dạng của chúng là không tương thích với nhau và kích thước cũng khác
nhau. Khi đó sẽ cần có một hệ phân tích tài liệu ảnh có khả năng lựa chọn được
một số thông tin cần thiết để có khả năng chuyển đổi giữa các định dạng trên
máy tính khác nhau.
Trường hợp thứ hai là tại các doanh nghiệp sản xuất lớn với hàng ngàn công
nhân thì việc chấm công theo cách thông thường sẽ rất khó khăn. Tuy nhiên,
việc này được khắc phục nhằm đem lại sự tiện lợi, chính xác và nhanh chóng
bằng cách sử dụng máy chấm công bằng vân tay tích hợp công nghệ xử lý và so
sánh dấu vân tay bảo đảm được công tác chấm công giờ làm không cần sự theo
dõi trực tiếp của con người. Trong đó máy chấm công bằng vân tay ứng dụng hệ
phân tích ảnh tài liệu.
Ngày nay, Công nghệ OCR có khả năng nhận dạng văn bản chính xác đến
hơn 90%, các tài liệu lưu trữ trong thư viện, các tài liệu kỹ thuật sẽ được chuyển
đổi thành các tài liệu điện tử trên máy tính để thuận tiện hơn trong việc lưu trữ,

chỉnh sửa, biên tập lại. Tuy nhiên tài liệu giấy cho đến nay vẫn được sử dụng
rộng rãi vì phù hợp với mọi đối tượng, dễ thao tác, phổ biến vì tính trực quan.
Do đó, vấn đề ở đây là chúng ta phải sử dụng công nghệ kết hợp các thuật toán
để tích hợp các dữ liệu dưới dạng ảnh để đưa vào xử lý trong máy tính.
Sau khi có 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át hiện đối tượng văn bản và
đối tượng ảnh.
7

Số hóa bởi Trung tâm Học liệu




Hình 1.2: Các bước xử lý cho một hệ phân tích tài liệu, đi kèm sơ đồ là
một thí dụ với các kết quả thu được từ từng bước.
Nguồn: Gorman(2009)

1.1.1. Quá trình thu nhận ảnh
Thông thường ảnh đượ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, những đoạn phim kỹ thuật số từ
máy chụp hoặc máy quay phim 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.
Giá trị điểm ảnh có thể là 0 và 1 trong ảnh nhị phân, 0 đến 255 trong ảnh đa
cấp xám và ảnh màu với 3 giá trị R, G, B từ 0 đến 255. Thí dụ, với một trang
Phân tích đặc trưng
Mô tả tài liệu
Lấy dữ liệu
Xử lý điểm ảnh

10
7
điểm ảnh
7500 hình bao ký tự, mỗi ký tự
có kích thước 15x20 điểm ảnh
500 đường kẻ và đường cong với
độ dài từ 20 đến 2000 điểm ảnh
Trang tài liệu
Phân tích và nhận
dạng đối tượng ảnh
Phân tích và nhận
dạng văn bản
1000 vùng ảnh được tô với kích thước
từ 20x20 đến 200x200 điểm ảnh
500x5 đặc trưng của đường
thẳng và đường cong
10x5 đặc trưng vùng
Hai sơ đồ và 1 ảnh lô
gô của công ty,.v.v
7500x10 đặc
trưng của ký tự
1500x10 ký tự, 10
đoạn văn bản, 1 tiêu
đề chính và 2 tiêu đề
phụ
8

Số hóa bởi Trung tâm Học liệu



ả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. Do đó có thể thấy rằng một tài liệu ảnh chỉ
bao gồm các dữ liệu thô (giá trị các điểm ảnh) và chúng sẽ được sử dụng những
kỹ thuật phân tích thích hợp để lấy ra được các thông tin cần thiết.
1.1.2. Các bƣớc xử lý điểm ảnh
Sau khi đã thu thập được ảnh, người ta sẽ tiến hành quá trình xử lý điểm
ảnh để làm cơ sở cho các quá trình phân tích và nhận dạng về sau. Cụ thể,
thường thực hiện các công việc như chọn ngưỡng để chuyển ảnh đa cấp
xám, ảnh màu về dạng ảnh nhị phân hay các thành phần trong ảnh tài liệu
không cần quan tâm đến có thể được loại trừ bằng việc giảm nhiễu (noise
reduction) và một số bước còn lại là phân đoạn, dò biên để xác định các vùng,
các đặc trưng và đối tượng phù hợp. Sau khi đã thực hiện các công đoạn vừa
rồi, thì người ta thường nén các dữ liệu bằng các phương pháp mã hóa chuỗi
(chain coding) và biểu diễn ở dạng vectơ.
1.1.2.1. Phƣơng pháp nhị phân
Đối với ảnh tài liệu dạng đa cấp xám có thông tin vốn là nhị phân như văn
bản hoặc hình ảnh thì mục tiêu là phải chọn được một ngưỡng để tách thông tin
nền và thông tin ảnh thành hai phần riêng biệt. Công việc này chính là để chọn
được một ngưỡng thích hợp để tách thông tin ảnh tài liệu thành hai phần như
vậy không phải là việc dễ dàng và sẽ càng khó khăn hơn đối với chúng ta khi
gặp phải những thông tin ảnh mà độ tương phản giữa giá trị điểm ảnh nền và
giá trị điểm ảnh văn bản là thấp. Khi đường nét của văn bản quá mỏng hoặc khi
quét ảnh tài liệu không đủ cường độ sáng thích hợp thì cũng gây ra những khó
khăn trong quá trình tìm ngưỡng. Vì vậy, người ta đã áp dụng nhiều phương
pháp tách ngưỡng để khắc phục khó khăn trên. Trong đó phương pháp tách
ngưỡng tự động thường được áp dụng. Cụ thể, giá trị ngưỡng α trong kỹ thuật
9

Số hóa bởi Trung tâm Học liệu







tách ngưỡng thường cho bởi người sử dụng. Kỹ thuật tìm, tách ngưỡng tự
động nhằm tìm ra ngưỡng α một cách tự động dựa vào histogram theo nguyên
lý trong vật lý là vật thể tách làm hai phần nếu tổng độ lệch trong từng phần
là tối thiểu (Đỗ Năng Toàn-2008).
























Hình 1.3: Mô phỏng phương pháp nhị phân ảnh. (a): Biểu đồ Histogram
của ảnh đa cấp xám ban đầu. (b): ngưỡng thấp. (c): ngưỡng phù hợp. (c):
ngưỡng cao. Nguồn: Gorman (2009).
10

Số hóa bởi Trung tâm Học liệu


1.1.2.2. Giảm nhiễu
Xuất hiện các điểm nhiễu trong tài liệu ảnh là do nhiều nguyên nhân bao
gồm sự thoái hoá theo thời gian, sự sao chép, quá trình quét tài liệu từ máy quét
Các nhiễu làm giảm hoặc nhiều khi làm mất khả năng biểu lộ thông tin của đối
tượng chính trong ảnh. Có nhiều loại nhiễu như nhiễu cộng, nhiễu nhân, nhiễu
xung. Với mỗi loại nhiễu cần có các bộ lọc thích hợp. Với nhiễu cộng và nhiễu
nhân ta dùng các bộ lọc thông thấp, trung bình, và lọc đồng hình. Sở dĩ như vậy
vì bản chất của nhiễu là thường tương ứng với tần số cao và cơ sở lý thuyết của
các bộ lọc là chỉ cho những tín hiệu nào đó thông qua. Nhiễu có thể coi như sự
đột biến của một điểm ảnh so với các điểm lân cận. Một số kỹ thuật xử lý ảnh sẽ
được áp dụng để loại bỏ nhiễu.
Sau khi được nhị phân hoá, tài liệu ảnh sẽ được lọc để giảm nhiễu. Nhiễu
muối và nhiễu hạt tiêu (Salt and Pepper noise) là những loại nhiễu phổ biến nhất
có trong các tài liệu kém chất lượng. Chúng xuất hiện như những điểm ảnh khác
biệt so với vùng xung quanh, chẳng hạn các điểm ảnh nhiễu ON (điểm mang
thông tin ảnh) trong vùng nền OFF (điểm mang thông tin nền) hay ngược lại các
điểm ảnh OFF trong vùng nền ON và các cạnh gồ ghề của ký tự hay các đối
tượng ảnh. Các phép toán hình thái thường được sử dụng để loại bỏ nhiễu. Hai
phép toán hình thái cơ bản là giãn ảnh (Dilation) và co ảnh (Erosion). Co ảnh là
phương pháp làm giảm kích cỡ của vùng ON. Giãn ảnh là phương pháp ngược

lại với co ảnh, trong đó những điểm đơn ON thì tăng thêm. Các phép toán này
thường được kết hợp với nhau nhiều lần và áp dụng tuần tự co ảnh và giãn ảnh
nhiều lần. Một trong những phương pháp kết hợp đó được gọi là phép toán
OPENING, sử dụng cùng một số lần co ảnh và giãn ảnh. Kết quả của phép toán
OPENING là vùng biên của đối tượng nhẵn hơn, vùng eo nhỏ bị đứt và các vùng
điểm nhiễu nhỏ được loại bỏ. Phép toán đối xứng của OPENING là CLOSING.
Nó thực hiện giãn ảnh cùng một số lần với co ảnh. Kết quả thu được của phép
11

Số hóa bởi Trung tâm Học liệu


toán CLOSING đó là vùng biên nhẵn hơn, loại bỏ các lỗ hổng (holes) nhỏ trong
đối tượng và nối liền các kẽ hở ngắn giữa các đối tượng.
1.1.2.3. Phân đoạn
Để phục vụ cho các bước xử lý ảnh tài liệu về sau, một trong những công
đoạn khá quan trọng là phải tiến hành phân đoạn các đặc tính cơ bản có chứa
trong hình ảnh thu nhận được. Cụ thể, việc phân đoạn được tiến hành với hai
tiến trình chính. Thứ nhất là tách riêng biệt giữa các lớp của ảnh tài liệu, gồm
lớp hình ảnh và lớp văn bản đối với trường hợp dữ liệu đầu vào có chứa cả
hình ảnh và văn bản. Thứ hai là tiếp tục thực hiện các tiến trình phân tích trên
các lớp vừa được tách ra. Với lớp hình ảnh thì phân định rõ các đối tượng hình
vẽ, đường kẻ, biểu tượng cũng như các loại hình ảnh khác. Còn đối với lớp văn
bản thì tiến hành xác định các ký tự, từ, đoạn văn, chia cột văn bản,…Một số
hướng tiếp cận phương pháp phân khúc các đặc tính ảnh như dựa trên không
gian đặc trưng, không gian ảnh hoặc là dựa trên mô hình vật lý. Tiếp đến là
văn bản sẽ được tách thành các đoạn, các cột, các chuỗi, còn hình ảnh thì
được tách thành các biểu tượng, đường kẻ và các đối tượng ảnh khác. Như
vậy, tài liệu ảnh sau khi được thực hiện phân khúc sẽ quản lý được các đối
tượng rất nhỏ như các phần cơ bản của ảnh.

1.1.2.4. Làm mảnh và xác định vùng
Làm mảnh ảnh là một thao tác xử lý trong đó đối tượng ảnh được biểu diễn
như những đường trục trung tâm hay còn gọi là lấy xương của đối tượng ảnh.
Đây là kỹ thuật làm giảm bớt các điểm ảnh lân cận có cùng bản chất nhưng vẫn
bảo đảm tính liên kết và liên thông của mỗi đối tượng ảnh. Xương được coi như
là hình dạng cơ bản của một đối tượng, người ta có thể lấy lại được các thông
tin về hình dạng nguyên bản của một đối tượng thông qua xương của nó.
Việc tìm được xương của đối tượng ảnh sẽ giúp chúng ta giảm bớt tốn kém vì
không cần thiết phải lưu trữ những thông tin không quan trọng trong quá trình
12

Số hóa bởi Trung tâm Học liệu


xử lý sau này, cũng như có thể đồng bộ hóa việc lưu trữ các đối tượng ảnh
tương tự nhau ví dụ như những đoạn thẳng có thể vẽ với độ dày mỏng khác
nhau nhưng khi lưu trữ và biểu diễn thì các đoạn này là giống nhau nhờ vào
việc biểu diễn xương của chúng. Hình 1.4 biểu diễn ảnh nguyên bản bên trái và
xương tương ứng của chúng phía bên phải. Đã có nhiều thuật toán được phát
triển trong việc tìm xương nhằm từng bước khắc phục việc mất mát thông tin
trong quá trình thực hiện. Người ta chia thành hai loại thuật toán tìm xương là
tìm xương dựa trên làm mảnh (thinning) và tìm xương không dựa trên làm
mảnh. Thuật toán làm mảnh là quá trình lặp duyệt và kiểm tra tất cả các điểm
thuộc đối tượng. Trong mỗi lần lặp tất cả các điểm của đối tượng sẽ được kiểm
tra: Nếu chúng thỏa mãn điều kiện xóa nào đó tuỳ thuộc vào mỗi thuật toán thì
nó sẽ bị xóa đi. Quá trình được lặp lại cho đến khi không còn điểm biên nào
được xóa. Đối tượng được bóc dần lớp biên cho đến khi nào bị thu mảnh lại chỉ
còn các điểm biên. Người ta thường sử dụng thuật toán làm mảnh song song và
thuật toán làm mảnh tuần tự. Nếu tìm xương không dựa trên làm mảnh thì để
tách được xương của đối tượng, người ta sử dụng đường biên của đối tượng

nhờ vào trục trung vị thông qua hai bước cơ bản: Bước thứ nhất là tính khoảng
cách từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất và cần phải tính
toán khoảng cách tới tất cả các điểm biên của ảnh. Bước thứ hai, khoảng cách
ảnh đã được tính toán và các điểm ảnh có giá trị lớn nhất được xem là nằm trên
xương của đối tượng (Đỗ Năng Toàn-2008).
13

Số hóa bởi Trung tâm Học liệu



Hình 1.4: Ảnh nguyên bản bên trái và ảnh sau khi làm mảnh bên phải.
(a) Ký tự “m”. (b) Một sơ đồ. (c) Vân tay. Nguồn: Gorman (2009).
1.1.2.5. Mã hóa CC và véctơ hóa
Khi đã phát hiện được xương hoặc biên của đối tượng ảnh thì ta có thể
biểu diễn ảnh theo một trong hai cách này. Nhưng đối tượng ảnh còn có thể
được biểu diễn hiệu quả hơn bằng cách lưu trữ các điểm ảnh theo các giá trị ON
và OFF, trong đó giá trị ON thể hiện giá trị của mỗi điểm ảnh và OFF biểu diễn
giá trị điểm nền.
Một trong những phương pháp lưu ảnh hiệu quả đó là lưu dưới dạng mã
xích CC (Chain Code – Freeman 1974), trong đó các điểm có giá trị ON được
biểu diễn thông qua tập các điểm láng giềng đi theo một hướng quy định. Thay
vì phải lưu trữ vị trí của điểm ảnh có giá trị ON chúng ta sẽ lưu trữ hướng của
các điểm láng giềng. Các điểm láng giềng của một điểm x là tất cả các điểm nằm
liền kề với x thuộc ma trận 3 x 3 với điểm x là tâm. Có hai ưu điểm khi biểu
14

Số hóa bởi Trung tâm Học liệu



diễn giá trị điểm ảnh theo hướng thay vì phải lưu vị trí của điểm ảnh. Thứ nhất
đó là việc lưu trữ hiệu quả hơn. Thông thường với những ảnh có kích thước lớn
hơn 256 x 256, toạ độ giá trị điểm ảnh ON thường được biểu diễn bởi 16 bít; trái
lại với cách lưu trữ CC một điểm láng giềng thuộc 1 trong tám hướng, do đó
mỗi một điểm ảnh ON chỉ cần biểu diễn bằng 1 byte hay thậm chí chỉ cần 3 bít
để lưu. Một ưu điểm khác có thể thấy trong CC đó là vì CC lưu theo cấu trúc các
điểm ảnh có liên quan với nhau và do đó dựa vào cách thức lưu trữ này có thể
thực hiện các công việc xử lý như làm trơn các đường cong và tính xấp xỉ các
đường thẳng trơn.
Sau bước xử lý điểm ảnh, dữ liệu thô của ảnh đã được biểu diễn ở cấp độ
trừu tượng cao hơn: đã khoanh được vùng bao của chuỗi ký tự, biểu diễn CC và
véctơ của các đường cong và đường thẳng, hay đã xác định được vùng biên của
các đối tượng.
3
2
1
4
X
0
5
6
7

Hình 1.5: Cửa sổ 3x3 điểm ảnh với điểm ảnh X nằm ở tâm. Các giá trị số biểu
diễn cho hướng mà một điểm láng giềng của X thuộc: 0 (hướng tây), 1(tây -
bắc), 2(bắc), 3(đông - bắc), 4(đông), 5(đông – nam), 6(nam), 7(tây – nam)
1.1.3. Phân tích các đặc trƣng của tài liệu ảnh
Đặc trưng của ảnh tài liệu gồm có đặc trưng cục bộ (local features) và đặc
trưng toàn cục (global features). Với ảnh tài liệu chứa văn bản, đặc trưng toàn
cục mô tả từng trang, độ nghiêng của trang khi quét vào từ máy quét, độ dài

dòng, khoảng cách dòng, còn đặc trưng cục bộ thì mô tả về kích thước phông
chữ, dấu chấm câu, v.v…Tương tự như thế, với ảnh tài liệu chứa hình ảnh, thì
đặc trưng toàn cục cũng xét đến độ nghiêng của trang tài liệu, độ rộng dòng,
phạm vi của độ cong đối với các đường cong, độ dài tối thiểu của dòng. Và đặc
15

Số hóa bởi Trung tâm Học liệu


trưng cục bộ lại xét đến việc mô tả mỗi góc, mô tả đường cong và đường thẳng,
định vị các hình chữ nhật, hình tròn và hình dạng của các loại hình học khác.
Như vậy, để phục vụ cho các công đoạn xử lý ảnh tiếp theo, thì các
hình ảnh sau khi đã xử lý điểm ảnh nó sẽ được lưu trữ ở dạng xương, dạng
hình bao hoặc dạng véctơ hóa và tiếp tục được phân tích đặc trưng, được ghi
nhận và xử lý để làm cơ sở dữ liệu cho những thao tác xử lý nhận dạng về sau.
1.1.4. Phân tích các đối tƣợng văn bản trong tài liệu
Có hai loại phân tích được áp dụng trong việc phân tích văn bản trong tài liệu
ảnh. Loại thứ nhất là nhận dạng ký tự quang học (ORC) để nhận dạng từng ký
tự, các chuỗi ký tự từ ảnh bitmap (bmp), loại thứ hai là phân tích sơ đồ trình bày
của trang tài liệu nhằm nhận biết được định dạng của văn bản, và từ đó hiểu
được cấu trúc, vị trí, chức năng của các khối văn bản (tiêu đề chính, tiêu đề phụ,
đoạn văn bản, chú thích .v.v…). Phụ thuộc vào cách sắp xếp của các khối văn
bản, một biểu mẫu kinh doanh, hay là một phong bì thư. Nhận dạng ký tự quang
học và phân tích sơ đồ trình bày có thể được thực hiện một cách riêng rẽ, hay có
thể lấy kết quả của phần này để sử dụng cho phần kia. Nhận dạng ký tự quang
học thường được nhận biết như là ứng dụng nhận dạng ký tự viết tay hay các ký
tự trong tài liệu in. Kỹ thuật phân tích sơ đồ trình bày được áp dụng để phân tích
định dạng của trang, một loại ứng dụng phân tích sơ đồ trình bày đó là nhận
dạng biểu mẫu, giúp phân tích và nhận dạng cấu trúc biểu mẫu và văn bản có
trong biểu mẫu. Trong một số trường hợp người ta cần phải xác định độ nghiêng

của tài liệu bởi vì tài liệu được quét có thể bị nghiêng so với bề ngang của trang
giấy trong trường hợp tài liệu đó không được đặt đúng khi quét vào từ máy quét.
1.1.4.1. Ƣớc lƣợng độ nghiêng của văn bản
Ảnh tài liệu được cho là nghiêng khi phát hiện góc nghiêng khác 0. Một dòng
văn bản được cấu thành từ một nhóm các ký tự, các từ tiếp giáp tương đối gần
16

Số hóa bởi Trung tâm Học liệu


nhau, các biểu tượng,…được bố trí trên một đường thẳng theo hướng đứng hoặc
nằm ngang. Những dòng văn bản này là căn cứ cơ bản để xác định góc độ
nghiêng của trang ảnh tài liệu trên cơ sở so sánh tính chất song song của các
dòng văn bản so với các cạnh của mép trang tài liệu.
Việc xác định độ nghiêng và điều chỉnh độ nghiêng của tài liệu là một việc
làm cần thiết trước khi thực hiện những bước trên. Một phương pháp xác định
độ nghiêng của tài liệu phổ biến đó là phép chiếu nghiêng. Phép chiếu nghiêng
là phương pháp tính số lượng điểm ảnh ON (điểm ảnh có giá trị 1 trong ảnh nhị
phân) khi quét ảnh theo các dòng hay các cột và lưu giá trị này vào một mảng,
trong đó chỉ số của mảng chính là dòng hay cột được quét. Do đó giá trị các
điểm ảnh ON khi quét qua trang ảnh sẽ được biểu diễn bởi một đồ thị tần suất.
Mỗi một lần thực hiện phép chiếu nghiêng ta sẽ chiếu ảnh theo các góc khác
nhau (từ 0 đến 180 độ), tức là sẽ thực hiện quay ảnh một góc tương ứng. Để tìm
được góc nghiêng của văn bản thì sẽ tìm góc quay sao cho đồ thị tần suất có
nhiều những đỉnh cao nhất và những vùng trũng nhất. Nếu đồ thị tần suất có 10
đỉnh và 10 vùng trũng thì có thể suy ra rằng tài liệu ảnh có 10 dòng văn bản. Do
đó với mỗi phép chiếu nghiêng ta sẽ tính số đo độ cao của các đỉnh và số đo độ
cao các vùng trũng, góc chiếu nào mà có sự khác nhau giữa hai số đo này là lớn
nhất thì chính là góc nghiêng của văn bản.







Hình 1.6: Văn bản bị nghiêng sau khi được quét qua máy quét

17

Số hóa bởi Trung tâm Học liệu










Hình 1.7 : Biểu đồ Histogram của phép chiếu ngang và dọc của ảnh (a) và (b).
Nguồn: Gorman (2009)

1.1.4.2. Phân tích sơ đồ trình bày của trang tài liệu


(a)
18

Số hóa bởi Trung tâm Học liệu





Hình 1.8: Kết quả phân tích cấu trúc và chức năng các khối của một trang tài liệu.

Sau khi xác định được độ nghiêng của trang tài liệu, ảnh sẽ được quay một
góc để độ nghiêng của trang bằng 0, sau đó quá trình phân tích sơ đồ trình bày
của trang được thực hiện. Phân tích cấu trúc trình bày được thực hiện để lấy ra
được cấu trúc các khối văn bản (các đoạn văn bản) trong tài liệu. Tuỳ thuộc vào
định dạng của từng loại tài liệu, quá trình phân đoạn có thể thực hiện phân tách
các từ, các dòng văn bản hay cấu trúc các khối (nhóm các dòng văn bản, chẳng
hạn các đoạn văn bản hay các bảng danh mục). Thông thường người ta dựa vào