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
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:
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
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
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
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
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
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
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
ả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
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
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
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
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.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
Copyright: Tài liệu đại học ©