TÌM HIỂU PHưƠNG PHÁP PHÂN TÍCH BẰNG
BÊN TRONG TÀI LIỆU ẢNH
Luận văn Thạc sỹ Công nghệ thông tin
1.2. Tổ chức của luận văn
Luận văn được trình bày thành 5 chương và 1 phụ lục.
Chương 1 Trình bày tóm tắt cơ sở nghiên cứu và mục đích cũng như
cách tổ chức của luận văn.
Chương 2 Tông quan vê hê phân tí ch tai liêu anh va cac thanh phân
̣
chính trong hê phân tí ch tai liêu anh : Lây dư liêu , xư ly anh , trích chọn đặc
̣
́
trưng, nhân dang đôi tương anh va nhân dang văn ban .
Chương 3 trình bày bài toán phân tách văn bản và ảnh một cách riêng
rẽ. Trong chương này một thuật toán phân tách văn bản và ảnh cũng sẽ được
trình bày dựa vào việc phân tích các thành phần liên thông (CCs).
Chương 4 trình bày phương pháp phân tích bảng ( T-Recs) dựa trên
những hình chữ nhật bao quanh một từ và đầu ra là cấu trúc logic của khối
văn bản, cụ thể với những bảng nhận dạng được sẽ là cấu trúc các cột và các ô
của bảng dữ liệu. Phân tích những mặt hạn chế của thuật toán - trường hợp
nhận dạng chưa chính xác các cột dữ liệu trong bảng luận văn đưa ra thuật
toán khắc phục những mặt hạn chế đó.
Chương 5 Chương trình thử nghiệm và minh họa phân tích bảng trong
trang tài liệu ảnh.
MỤC LỤC
Trang phụ bìa
Lời cảm ơn
MỤC LỤC -------------------------------------------------------------------------------i
THUẬT NGỮ TIẾNG ANH:---------------------------------------------------------iii
DANH MUC CAC HÌ NH VE --------------------------------------------------------iv
CHưƠNG I: MỞ ĐẦU ----------------------------------------------------------------1
1.1. Cơ sở nghiên cứu và mục đích của luận văn ----------------------------3
1.2. Tổ chức của luận văn: --------------------------------------------------------4
CHưƠNG II: TỔNG QUAN VỀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH ---------5
2.1. Tài liệu ảnh ---------------------------------------------------------------------5
2.2. Hệ phân tích trang tài liệu --------------------------------------------------5
2.3. Thu thập dữ liệu ảnh ---------------------------------------------------------6
2.4. Tiền xử lý điểm ảnh -----------------------------------------------------------9
2.4.1.
Xử lý nhị phân ----------------------------------------------------------10
2.4.2.
Giảm nhiễu---------------------------------------------------------------11
2.4.3. Phân đoạn ảnh -----------------------------------------------------------12
2.4.4. Làm mảnh và xác định vùng -----------------------------------------12
2.4.5. Mã hóa CC và véctơ hóa ----------------------------------------------13
2.5.
Phân tí ch đăc trưng cua tai liêu anh -------------------------------------15
2.6. Phân tí ch đôi tương văn ban trong tai liêu -----------------------------15
2.6.1.
Xác định góc nghiêng của văn bản ----------------------------------16
2.6.2.
Phân tí ch bô cuc cua trang ta i liêu anh ------------------------------18
2.7. Nhận dạng ký tự quang học (OCR) ---------------------------------------19
2.7.1.
Thuât toan OCR -----------------------------------------------------20
2.7.1.1.
2.7.1.2.
2.7.2.
2.8.
Trích chọn đặc trưng ---------------------------------------20
Phân loại------------------------------------------------------21
Nhận dạng ký tự dựa trên ngữ cảnh ------------------------------21
Phân tích các đối tượng ảnh trong tài liệu ------------------------------22
CHưƠNG 3: THUẬT TOÁN TÁCH VĂN BẢN - ẢNH TỪ TRANG TÀI
LIỆU ẢNH ------------------------------------------------------------------------------24
3.1.
3.2.
3.3.
Tông quan vê phân tach văn ban – ảnh ---------------------------------24
Những đặc trưng chung của một tệp tài liệu ảnh ---------------------27
Thuật toán phân tách văn bản - ảnh --------------------------------------30
3.3.1.
Xoá bỏ các đối tượng tuyến tính ---------------------------------31
3.3.2.
Phân tích các thành phần liên thông của nét bút ---------------32
3.3.3. Kết hợp các nét ký tự tạo thành các chuỗi văn bản ------------34
3.3.4. Thực hiện các phép toán hình thái -------------------------------35
3.3.5. Phân tích các thành phần liên thông mới -----------------------35
3.3.6. Biểu diễn cấu trúc thông tin của các chuỗi văn bản -----------36
CHưƠNG IV: PHưƠNG PHÁP PHÂN TÍCH BẢNG T-RECS TRONG
TRANG TAI LIÊU ANH------------------------------------------------------------39
4.1.
Giới thiệu --------------------------------------------------------------------39
4.2. Thuật toán phân đoạn khởi tạo ----------------------------------------41
4.2.1.
Trường hợp thuật toán nhận dạng sai cột -----------------------42
4.2.2. Cải tiến các bước của thuật toán phân đoạn khởi tạo T - Recs++ 44
4.2.3. Những ưu điểm của thuật toán -----------------------------------46
4.2.4. Những mặt hạn chế của thuật toán khởi tạo --------------------47
4.3. Các bước xử lý khối sau khi phân đoạn ------------------------------48
4.3.1.
Trộn các khối phân đoạn sai --------------------------------------48
4.3.2. Phân tách các cột bị trộn vào một khối --------------------------49
4.3.3. Nhóm các từ bị phân tách -----------------------------------------52
4.4.
Phân tích khối --------------------------------------------------------------53
4.5. Xác định cấu trúc các cột, hàng ----------------------------------------54
CHưƠNG 5 CHưƠNG TRÌ NH THư NGHIỆM VA MINH HOA THUÂT
TOÁN T-RECS++ ---------------------------------------------------------------------56
5.1. Mô tả chương trình -------------------------------------------------------56
5.2. Môt sô kêt qua -------------------------------------------------------------58
́
KÊT LUÂN VA ĐÊ XUÂT ----------------------------------------------------------61
74 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1760 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Tìm hiểu phương pháp phân tích bằng bên trong tài liệu ảnh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ch hợp để không loại bỏ dấu của Tiếng Việt.
3.3.3. Kết hợp các nét ký tự tạo thành các chuỗi văn bản
Trong đặc trưng thứ 2 của phần 3.2 độ dài của khoảng trắng giữa các
ký tự hay giữa các từ thường là nhỏ, do đó chúng ta có thể nhóm chúng cùng
với nhau. Nếu như khoảng cách giữa hai điểm ảnh màu đen là nhỏ, chẳng hạn
như số lượng điểm ảnh trắng giữa chúng nhỏ hơn một tham số T5, chúng ta sẽ
thay thế các điểm ảnh màu trắng giữa chúng là màu đen. Điều này giống như
chúng ta dùng bút tô màu đen để tô lên các điểm ảnh trắng. Hướng của bút
lông này là theo chiều ngang hoặc chiều dọc. Hình 3.6 chỉ ra một thí dụ về
việc dùng bút để tô các điểm ảnh. Mục đích bước này là xây dụng các thành
phần liên thông mới (NCCs) bằng việc kết hợp nét bút của các ký tự, NCCs
được xây dựng dựa vào đặc trưng 2 của phần 3.2. Có thể tóm tắt lại mục đích
của bước này như sau đây:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
1. Những dấu chấm (.), ký hiệu “-“, và một số nét bút bị xoá đi ở
bước trước có thể khôi phục lại được.
2. Việc kết hợp các nét bút và các ký tự sẽ giúp dễ dạng nhận dạng
vùng văn bản, bởi vì một chuỗi văn bản được kết hợp tạo thành NCCs sẽ thể
hiện tính đặc trưng của văn bản rõ rảng hơn.
3. Thao tác dùng bút lông để tô những điểm ảnh thích hợp sẽ giúp
phân tách các đối tượng ảnh một cách rõ ràng hơn và giúp các bước xử lý sau
này dễ dàng phân tách hai đối tượng văn bản và ảnh.
Hình 3.6 Dùng bút để tô các điểm ảnh thoả mãn (T5 = 12 với kích thước cỡ chữ là 20).
3.3.4. Thực hiện các phép toán hình thái
Thực hiện các phép toán hình thái nhằm mục đích loại bỏ khả năng có
thể xảy ra khi ký tự tiếp xúc với đối tượng ảnh hay các chuỗi ký tự tiếp xúc
với nhau và sau đó xây dựng lại thành phần NCCs mới để cuối cùng phân
tách chuỗi văn bản và ảnh. Quá trình này gồm hai thao tác : một thao tác co
ảnh và một thao tác giãn ảnh.
3.3.5. Phân tích các thành phần liên thông mới
Bước này thực hiện giống như bước 3.3.2 tuy nhiên nó sẽ làm việc với
NCCs thay vì CCs như trong 3.3.2. Một cách tương tự, chúng ta sẽ duyệt qua
tất cả các điểm biên của NCCs bằng cách quét ảnh theo từng dòng và lấy ra
toạ độ của tất cả các điểm biên. Ba thông số quan trọng, MaxBox2,
WBRatio2, HWRatio2 sẽ được tính. Thành phần NCCs sẽ được coi như là
một đối tượng ảnh khi các thông số trên thoả mãn 1 trong những điều kiện
sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
WBRatio2 ≤ T6,
Độ dài của cạnh dài hơn trong MaxBox2 ≤ T7,
Độ dài của cạnh nhỏ hơn trong MaxBox2 ≤ T8, hay
Độ dài của cạnh nhỏ hơn trong MaxBox2 ≤ T7 và HWRatio2 ≥ T9
Trong đó T6, T7, T8 và T9 là các các tham số ngưỡng cho trước .
Trong bước này hướng của chuỗi văn bản cũng sẽ được đánh giá.
Trường hợp WBRatio2 không đủ cao, chúng ta sẽ tìm cách thu nhỏ lại hình
chữ nhật bao của NCCs. Chính vì lý do đó, các điểm biên trong ảnh của
NCCs sẽ được quay để tìm hình bao chữ nhật nhỏ nhất. Trong thuật toán này
mỗi lần sẽ được quay 10 độ, vì vậy cần có 8 lần quay cho mỗi NCCs. Sau đó
hình bao chữ nhật nhỏ nhất sẽ được quay ngược lại ngần ấy độ, kết quả là
hình chữ nhật nghiêng sẽ là hình bao nhỏ nhất của NCCs và khi đó góc của
hình chữ nhật nghiêng sẽ là hướng của chuỗi ký tự.
Sau bước này, toàn bộ các đối tượng ảnh được nhận dạng sẽ được đưa vào
lớp đối tượng ảnh.
3.3.6. Biểu diễn cấu trúc thông tin của các chuỗi văn bản
Trong 3.3.5, khi một đối tượng NCCs được coi là một chuỗi ký tự,
hình bao MaxBox2 sẽ được biểu diễn dưới cấu trúc sau:
Char_Box { double Angle; int Coe;},
Trong đó Angle biểu diễn hướng của chuỗi ký tự. Khi Angle = 0, hình
bao là hình chữ nhật và Coe biểu diễn toạ độ góc trên bên trái và góc dưới bên
phải của hình bao. Khi Angle > 0, hình bao sẽ là một hình chữ nhật nghiêng
và Coe biểu diễn toạ độ góc trên bên trái và góc dưới bên phải. Kết quả của
bước này là trích ra được các thông tin từ vùng giới hạn chuỗi ký tự, cũng
chính là ghi lại thông tin các vùng bao hình chữ nhật từ tài liệu ảnh ban đầu.
Nếu dựa vào các thông tin này chúng ta lấy ra các vùng giới hạn của chuỗi ký
tự từ ảnh baban đầu, phần còn lại của ảnh khi đó sẽ là các đối tượng ảnh.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
Chương này đã trình bày một thuật toán phân tách văn bản và ảnh một
cách hiệu quả. Thuật toán sẽ hoạt động tốt và hiệu quả ở một số khía cạnh
sau:
- Nó có thể phân tách ảnh và văn bản trong trường hợp 2 đối tượng
này tiếp xúc với nhau, điều này dường như có thể rất khó với các thuật toán
khác, chẳng hạn như [3].
- Có thể nhận dạng khá tốt các ký tự của Trung Hoa.
- Việc xác định hướng của văn bản là rất dễ dàng.
- Phần lớn các tham số đều được tính qua đại lượng Hav, đại lượng
này cho phép có thể thay đổi được. Điều này giúp cho thuật toán khá là thuận
tiện. Kết quả ảnh thu được của thuật toán cũng sẽ không bị ảnh hưởng lớn vào
Hav khi mà giá trị Hav nằm trong một khoảng giá trị là độ cao trung bình của
một ký tự.
- Thuật toán cũng sẽ không bị ảnh hưởng khi ảnh có nhiều điểm
nhiễu.
Mặt khác cũng sẽ dễ dàng nhận thấy thuật toán cũng còn một số điểm
hạn chế. Chúng ta có thể tóm tắt lại các loại lỗi mà thuật toán gặp phải như
sau:
- Khi mà độ đậm đặc của đối tượng ảnh quá cao hay độ đậm đặc của
vùng văn bản thấp sẽ dẫn đến nhận dạng nhầm đối tượng ảnh là văn bản.
- Một số ký hiệu văn bản đặc biệt như “.”, “1”, “l” hoặc “I” hay các
đường kẻ gạch ngang thường cho kết quả không tin cậy.
- Đối với sơ đồ có các hình mũi tên, thông thường thuật toán sẽ không
chuyển được các hình mũi tên theo chiều ngang và chiều dọc.
- Nếu hai chuỗi ký tự được đặt song song và đặt quá gần nhau, chúng có
thể được nhóm lại như là một chuỗi ký tự. Bởi vì thuật toán sẽ sự dùng hình
bao chữ nhật để trích ra các ký tự, vì vậy tất cả các thành phần nằm trong hình
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
bao sẽ được hiểu là một thành phần văn bản. Lỗi sẽ xảy ra khi có một vài
thành phần của đối tượng ảnh nằm trong hình bao đó.
Dù vẫn còn một số hạn chế trong việc nhận dạng một số đối tượng
nhưng có thể khắc phục được vấn đề này dựa vào việc điều chỉnh tham số.
Hơn thế nữa trong một số tình huống việc thực hiện chuyển tất cả các thành
phần tuyến tính thoả mãn điều kiện sang thành đối tượng ảnh có thể để lại
những điểm ảnh rời rạc thuộc đối tượng ảnh mà các bước thực hiện sau này
không có khả năng nhận dạng chúng là đối tượng ảnh.
Dựa trên sự phân tích những đặc trưng khác nhau của các đối tượng
ảnh và văn bản, thuật toán sẽ điều chỉnh với những sự thay đổi về kiểu ký tự,
kích thước ký tự, loại ảnh và hướng của chuỗi ký tự trong văn bản. Thuật toán
có khả năng nhận dạng các ký tự Trung Hoa, ký tự Phương Tây, ký tự Tiếng
Việt và một số ký hiệu đặc biệt khá thành công. Nó có một số hạn chế đối với
ảnh có các cấp độ nhiễu khác nhau và có khả năng phân tách với trường hợp
văn bản và ảnh tiếp xúc nhau. Nếu được cải tiến ở tốc độ xử lý và xây dựng
cách tính tham số hợp lý thì thuật toán sẽ thích hợp trong việc sử dụng để viết
những ứng dụng nhận dạng trong văn phòng như OCR, CAD/CAM.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
CHƢƠNG 4
PHƢƠNG PHÁP PHÂN TÍCH BẢNG T-RECS
TRONG TRANG TÀI LIỆU ẢNH
4.1. Giới thiệu
Hệ thống nhận dạng quang học (OCR) trước đây chỉ là những phép
chuyển đổi đơn giản một tài liệu ảnh sang một tài liệu văn bản bao gồm các từ
nhưng ngày nay hệ thống OCR đã tiến xa hơn trước , ngoài việc chuyển tài
liệu ảnh sang tài liệu văn bản nó còn tập trung vào việc xác định đúng những
cấu trúc đặc trưng trong tài liệu.
Mục đích của những hệ thống nhận dạng cấu trúc không chỉ đơn giản
là chuyển một tài liệu in thành một tài liệu điện tử mà hơn thế nữa còn là xây
dựng những quá trình xử lý kết hợp chẳng hạn như: tự động chép nội dụng,
đánh chỉ mục và phân loại [13]. Do đó việc quan trọng là kèm theo nội dung
của tài liệu cũng phải trích chọn ra những cấu trúc đi kèm với từng nội dung
đó.
Khi đề cập đến vấn đề nhận dạng cấu trúc trong các tài liệu có chứa
dữ liệu bảng biểu sẽ có hai hướng tiếp cận khác nhau: cách tiếp cận thứ nhất
đó là xác định chính xác cấu trúc của bảng, bao gồm các ô trong bảng, cách
này thường được gọi là phân đoạn hay nhận dạng cấu trúc. Cách thứ hai là
dựa vào hình dạng bất kỳ của các khối đã được sắp xếp và đưa tập các đối
tượng trong các khối về một cấu trúc bậc cao hơn. Quá trình này được gọi tên
là gán nhãn lôgíc, phân tích cấu trúc hay phân tích bố cục trình bày trang..
Tìm hiểu những phương pháp nhận dạng cấu trúc bảng đã có trước
đây đều cho thấy một điểm giống nhau, đó là các phương pháp này đều nhận
dạng ra cấu trúc bảng bằng xác định ra các dấu hiệu phân cách, có thể là các
khoảng trắng, các đường kẻ. Chẳng hạn như Rus và Summers [1] mô tả một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
hệ nhận dạng cấu trúc bảng có khả năng xác định được bảng mà các cột cách
nhau một khoảng hẹp sử dụng WDG. Trong khi đó một số phương pháp khác
lại dựa vào độ rộng thích hợp của khoảng trắng giữa hai cột để nhận dạng
[17].
Một số phương pháp khác xác định cấu trúc của bảng bằng quy tắc các
đường kẻ. Một trong số đó là mô tả của Green và Krishnamoorthy [18], các
ông đã áp dụng phân tích vị trí của các đường kẻ để đưa ra cấu trúc của bảng.
Trong phương pháp sẽ trình bày dưới đây với tư tưởng là không xem
xét đến bất cứ một loại đường phân cách nào để xác định bảng mà sẽ đi vào
nhận biết các từ trong cùng một khối logic (chẳng hạn các từ trong cùng một
cột dữ liệu sẽ được cho vào trong cùng một khối). Chúng ta sẽ không đi tìm
những đặc trưng để phân biệt hai vùng dữ liệu (hai cột) khác nhau mà tìm
những đặc trưng để tìm ra các từ trong cùng một khối logic và từ đó xây dựng
cấu trúc riêng theo phương pháp tiếp cận dưới lên (bottom - up). Một điều dễ
nhận thấy ngay từ phương pháp này đó là chúng ta sẽ không phụ thuộc vào
kiểu của đường thẳng được vẽ trong bảng nếu có hay là các khoảng trắng đủ
rộng giữa các khối để nhận dạng cấu trúc của bảng.
Đầu vào (input) của thuật toán là tập hợp các hình bao chữ nhật của
các từ trong một đoạn văn bản. Đầu ra (output) là các cột, các dòng, các ô của
bảng nếu tồn tại môi trường bảng trong đoạn văn bản. Thuật toán sẽ cần các
bước tiền xử lý như nhận dạng các dòng văn bản của trang tài liệu, hình bao
chữ nhật các từ trên từng dòng văn bản và nhận dạng các đoạn văn bản khác
nhau. Từ đó có nhận dạng môi trường bảng trên từng đoạn văn bản của trang
tài liệu.
Toàn bộ chức năng của thuật toán T-Recs mà phần cốt yếu là thuật
toán phân đoạn khởi tạo sẽ được trình bày trong chương nà y. Đầu tiên luận
văn sẽ trình bày thuật toán phân đoạn khởi tạo do Thomas G. Kieninger [19]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41
đề xuất và sau đó chỉ ra những trường hợp mà thuật toán phân đoạn do G.
Kieninger sẽ nhận dạng sai. Tiếp theo luận văn sẽ trình bày thuật toán phân
đoạn cải tiến (T-Recs++) để có thể nhận dạng chính xác các cột dữ liệu tồn tại
trong một bảng.
Những ưu điểm và hạn chế của thuật toán cũng được chỉ ra trong phần
đầu của chương. Phần tiếp theo trong chương này luận văn sẽ chỉ ra một số
bược xử lý sau khi phân đoạn (postprocessing) để khắc phục những hạn chế
của thuật toán phân đoạn khởi tạo. Phần cuối của chương luận văn mô tả việc
phân tích các cột được nhận dạng thành các dòng và các ô trong bảng để đưa
ra được cấu trúc chính xác của bảng.
4.2. Thuật toán phân đoạn khởi tạo
Phân đoạn khởi tạo ta có thể hiểu như là quá trình phân cụm các từ.
Trong khi các phương pháp tiếp cận dưới-lên khác thường xác định các
đường kẻ từ các từ liền kề theo chiều ngang và các khối từ các đường liền kề
theo chiều dọc, hệ thống sẽ trực tiếp đánh giá các cấu trúc khối văn bản từ
việc phân đoạn các từ.
Tư tưởng của thuật toán : lấy một từ bất kỳ làm nhân để xây dựng
một khối mới. Nhìn trên Hình 4.1 (ở giữa), ta vẽ một vùng mờ ảo bao quanh
hình chữ nhật bao của từ (consist). Vùng mờ ảo này có độ rộng bằng với độ
rộng của hình bao của từ và chiều dọc mở rộng đến các dòng liền kề với từ
đó. Tất cả các từ mà có hình bao gối lên vùng mờ ảo của từ làm nhân sẽ nằm
trong cùng một khối với từ đó. Do đó một khối bao gồm tất cả các từ được
liên kết với nhau (hình bên phải của Hình 4.1).
Hình 4.1 Ví dụ minh họa tư tưởng của thuật toán khởi tạo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42
Thủ tục trên sẽ được mở rộng bằng cách thực hiện đệ quy cho tất cả
các từ cho đến khi không tìm thấy có từ nào mới mà không nằm trong một
khối nào đó. Đầu vào của thủ tục là hình bao chữ nhật của các từ, đầu ra là
các khối lôgíc và các từ thuộc từng khối lôgíc.
Thủ tục xây dựng thuật toán khởi tạo:
1) Tìm một từ bất kỳ nào đó Wx mà chưa được đánh dấu là mở rộng
(expanded).
2) Tạo một khối mới Bi
3) Đánh dấu Wx là đã mở rộng và thêm Wx vào Bi
4) Tìm tất cả các từ Wj theo chiều ngang ở dòng trước và dòng kế tiếp,
sao cho Wj nằm chồng lên Wx (có nghĩa là Wj gối lên vùng mờ ảo của
Wx).
5) Thực hiện đệ quy các bước 3, 4, và 5 cho các từ Wj vừa tìm được.
6) Nếu không tìm được từ nào mà chưa đánh dấu và không nằm chồng
lên nhau (theo ý nghĩa của bước 4) thì tăng i lên một và quay trở lại
bước 1.
7) Dừng thủ tục lại nếu không tìm thấy từ nào chưa được đánh dấu
trong tài liệu.
Hình 4.2 mô tả kết quả của thuật toán sau khi mở rộng tất cả các từ trong
khối
Hình 4.2 thuật khởi tạo đối với một đoạn văn bản
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
43
4.2.1. Trƣờng hợp thuật toán nhận dạng sai cột
7 bước trong thuật toán phân đoạn khối phía trên về cơ bản nhận dạng
được các khối riêng rẽ nhưng cũng chưa đủ tốt để nhận dạng được tất cả các
loại khối phân tách. Hình 4.2 mô phỏng một thí dụ về trường hợp thuật toán
phân tách thành hai khối khác nhau nhưng về logíc hai khối trên thực chất là
một khối.
Hình 4.3 Trường hợp thuật toán nhận dạng sai cột
Khi phân tích các bước của thuật toán trên ta thấy có một hạn chế, đó
là khi một từ Wj mới được xem xét có thêm vào khối đang duyệt Bi hay không
thì thuật toán chỉ quan tâm xem Wj có nằm chồng lên từ Wx (là từ ở dòng
trước hay dòng sau của Wj) mà không xem xét Wj có nằm chồng lên bất kỳ từ
nào thuộc khối Bi hay không.
Nhìn trên Hình 4.3, nếu thực hiện lần lượt các bước từ 1 đến 7 thì ta
thấy các từ trên được chia thành hai khối riêng rẽ, nhưng ta thấy hai từ Thành
và vọng tuy nằm chồng lên nhau nhưng lại thuộc hai khối khác nhau bởi vì
khi thuật toán đi đến từ là nó sẽ xem xét hai từ là kỳ và vọng trong đó chỉ có
mỗi từ kỳ là nằm chồng lên nó còn từ vọng không nằm chồng lên từ là
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44
Hình 4.4 Trường hợp giữa các dòng của một cột trong bảng có ô trắng
Hình 4.4 chỉ ra một thí dụ mà thuật toán do G. Kieninger có thể nhận
dạng được các cột trong bảng. Trong 7 bước mà G. Kieninger đề xuất, khi
thực hiện xuất phát từ một hình bao chữ nhật của một từ thuật toán chỉ tìm các
từ có nằm chồng lên nó trong dòng trước và dòng kế tiếp. Vì vậy trong trường
hợp một cột trong bảng mà có nhiều dòng để trống (chẳng hạn khi một ô của
bảng kéo dài trên nhiều dòng) thì khi thực hiện tìm các từ ở dòng kế tiếp và
dòng trước sẽ không tìm được từ nào thuộc cột đó. Do đó để tìm được chính
xác các từ thuộc một cột của bảng thì xuất phát từ một từ phải tìm trên tất cả
các dòng của đoạn văn bản.
Dưới đây sẽ trình bày những cải tiến các bước của thuật toán phân
đoạn trên.
4.2.2. Cải tiến các bƣớc của thuật toán phân đoạn khởi tạo - T-Recs++
Do các cột của một bảng đều nằm ở các vị trí là những khoảng khác
nhau theo chiều ngang, vì vậy để cải tiến thuật toán ta sẽ đi xác định toạ độ
nhỏ nhất - Xmin và lớn nhất - Xmax theo chiều ngang của một khối. Khi duyệt
qua các từ cần thêm vào khối nếu như toạ độ nhỏ nhất và lớn nhất theo chiều
ngang của khối có giao với khoảng (Xmin, Xmax) thì ta sẽ thêm từ đó vào khối
và cập nhật lại toạ độ Xmin, Xmax của khối đó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45
Đầu vào của thủ tục là hình bao chữ nhật của các từ, đầu ra là các khối
lôgíc và các từ thuộc từng khối lôgic.
Các bước cải tiến của thuật toán phân đoạn khởi tạo sẽ gồm 8 bước
như sau:
1. Gán Xmin= -1 và Xmax = 0.
2. Tìm một từ bất kỳ nào đó Wx mà chưa được đánh dấu là mở rộng
(expanded). Tính các toạ độ XXmin, XXmax lần lượt là 2 toạ độ nhỏ nhất
và lớn nhất theo chiều ngang của hình bao của từ Wx.
3. Tạo một khối mới Bi
4. Đánh dấu Wx là đã mở rộng và thêm Wx vào Bi. Xét:
Nếu Xmin = -1 thì gán Xmin= XXmin.
Nếu Xmin > XXmin thì gán Xmin= XXmin.
Nếu Xmax < XXmax thì gán Xmax = XXmax.
5. Tìm tất cả các từ Wj nằm theo chiều ngang ở các dòng trước và
những dòng kế tiếp (thuộc đoạn văn bản), sao cho:
(Xmin , Xmax) ∩ (XJmin , XJmax) ≠ Φ
Trong đó các toạ độ XJmin, XJmax lần lượt là 2 toạ độ nhỏ nhất và lớn
nhất theo chiều ngang của hình bao của từ Wj.
6. Thực hiện đệ quy các bước 4, 5, và 6 cho các từ Wj vừa tìm được.
7. Nếu không tìm được từ nào mà chưa đánh dấu và không thoả mãn
điều kiện 5 thì tăng i lên một và quay trở lại bước 1.
8. Dừng thuật toán lại nếu không tìm thấy từ nào mà chưa được đánh
dấu là mở rộng trong tài liệu.
Hình 4.5 dưới đây mô tả các bước thuật toán phân đoạn đã cải tiến.
Nếu như trên Hình 4.3, thuật toán trước có thể phân tách các từ vào hai khối
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
riêng rẽ thì với các bước đã cải tiến trên thuật toán sẽ nhóm các từ trong Hình
4.3 vào thành một khối duy nhất (hình cuối bên phải của Hình 4.5).
Hình 4.5 Mô phỏng việc thực hiện các bước đã cải tiến của thuật toán
Trong bước thứ 5 của thuật toán, khi thực hiện tìm những từ thoả mãn
để đưa vào một khối, thuật toán sẽ tìm tất cả các từ ở các dòng trước và các
dòng kế tiếp chứ không phải chỉ tìm ở dòng trước và dòng kế tiếp của dòng
đang xét. Do đó việc nhận dạng đúng các cột của bảng từ Hình 4.4 được minh
hoạ trên Hình 4.6.
Hình 4.6 Kết quả nhận dạng các cột từ Hình 4.4
4.2.3. Những ƣu điểm của thuật toán
Trong thí dụ đưa ra ở trên, điểm nổi bật của thuật toán vẫn chưa thể
hiện rõ ràng vì sự phân đoạn của những khối văn bản dường như cũng giống
những phương pháp có trước đây. Hình 4.7 minh hoạ điểm nổi bật của thuật
toán khi nhận dạng cấu trúc của bảng: ở đây ta thấy mỗi khối trong hình cách
nhau một khoảng cách hẹp. Do không có một từ nào nằm giữa các cột vì vậy
mà các cột được phân biệt với nhau một cách rõ ràng. (Để quan sát dễ dàng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47
hơn, mỗi cột đều được bôi một màu khác nhau để nổi bật). Ngoài những điểm
mạnh đề cập trên, thuật toán còn có những đặc điểm sau:
Hình 4.7 Quá trình phân đoạn các cột của bảng
Không quan tâm đến nội dung văn bản. Do đó nó có thể áp dụng cho
một tài liệu kém chất lượng để thực hiện phân đoạn.
Cho phép nhận dạng ra các cột trong bảng trong trường hợp khoảng
cách giữa các cột hẹp.
Nhận dạng cấu trúc của bảng mà không cần thông tin về tiêu đề của
bảng.
Nhận dạng cấu trúc bảng với các ô có nhiều hơn một dòng dữ liệu
(Hình 4.8)
Thuật toán áp dụng với các loại tài liệu phổ biến (không hạn chế một
số loại bảng nào đó; không quy định luật cụ thể, không cần phải có
giai đoạn học nhận dạng).
Hình 4.8 Trường hợp một ô của bảng chiếm nhiều dòng
4.2.4. Những mặt hạn chế của thuật toán khởi tạo
Thuật toán phân đoạn khởi tạo cũng tồn tài một số mặt hạn chế vốn
có. Chẳng hạn như thuật toán sẽ coi một dòng đơn là bảng bởi vì dòng này
không có những dòng là láng giềng của nó theo chiều dọc. Do đó nó sẽ coi đó
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
là một bảng chỉ có một dòng dữ liệu trong đó mỗi một từ coi như là một cột
trong bảng. Do đó khi nhận dạng một đoạn văn bản có tạo thành bảng hay
không cần xem số dòng của đoạn văn bản là bao nhiêu.
Hạn chế thứ hai thường xảy ra đối với một đoạn văn bản thông thường
mà đều có ký tự cách (space) tại cùng một vị trí của tất cả các dòng trong
đoạn văn bản đó. Do đó đoạn văn bản đó cũng không được nhận biết đó là
một khối thống nhất.
Một hạn chế khác đó là một số cột trong bảng có chung một tiêu đề.
Trong trường hợp này tiêu đề chung của bảng sẽ được cho vào một khối với
các cột có tiêu đề chung và thuật toán nhận biết đó chỉ là một cột. Hình 4.9
mô tả toàn bộ các mặt hạn chế trên.
Hình 4.9 Những mặt hạn chế của thuật toán
4.3. Các bƣớc xử lý khối sau khi phân đoạn
Một số bước xử lý được đưa ra để để khắc phục những hạn chế đề cập
ở trên khi nhận dạng. Trong phần này sẽ đề cập đến hai loại khối khác nhau:
khối loại một là khối chỉ bao gồm một từ trên một dòng (Hình 4.7), khối loại
hai là tất cả các trường hợp còn lại (Hình 4.8). Dễ nhận thấy rằng khối loại
một là một bảng đơn giản.
Phân biệt hai loại khối này sẽ giúp chúng ta dễ dàng chọn lựa từng
phương pháp, kỹ thuật để phân tích từng loại khối. Phần dưới đây sẽ trình bày
những phương pháp xử lý để khắc phục những trường hợp nhận dạng sai từ
Hình 4.9.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49
4.3.1. Trộn các khối phân đoạn sai
Hình 4.9 ở trên chỉ ra một thí dụ với một đoạn văn bản thông thường
mà đều có ký tự cách (space) tại cùng một vị trí của tất cả các dòng trong
đoạn văn bản đó. Trong trường hợp này phương pháp phân đoạn trên đoạn
văn bản đó không nhận biết đó là một khối thống nhất mà sẽ hiểu rằng đó là
hai khối tách biệt nhau. Do đó ta cần có bước xử lý để nhận biết và trộn hai
khối tách biệt này làm một khối thống nhất.
Trong phương pháp này chúng ta sẽ sử dụng những khối sau khi phân
đoạn ở trên. Có thể thấy rõ ràng rằng các khối mà có thể trộn thành một khối
chung thường nằm bên trái hoặc bên phải của nhau. Giả sử ta đã xác định
được 2 khối có thể trộn với nhau, từ một khối trước tiên chúng ta sẽ đánh giá
khoảng cách trung bình giữa các từ của hai khối để tìm độ rộng trung bình của
ký tự cách trong đoạn văn bản. Nếu khoảng cách giữa hai khối xấp xỉ bằng độ
rộng trung bình của ký tự cách thì có thể trộn hai khối đó vào làm một.
Hinh 4.10 Trộn hai khối bị phân tách
Một lưu ý rằng khi ta xét hai khối có khả năng được trộn với nhau thì
các khối đó phải thoả mãn là tất cả các dòng của khối đều có các từ nằm ngoài
cùng bên trái hay bên phải có vùng bao của từ phải thẳng hàng theo chiều
dọc. Tức là khi khối có một từ ở một dòng nào đó nằm thụt vào so với mép lề
trái hay mép lề phải của khối (Hình 4.10) thì ta coi hai khối đó không có khả
năng trộn với nhau.
Đối với khối loại hai chúng ta chúng ta dễ dàng tính được khoảng
cách trung bình giữa các từ trên cùng một dòng, sau đó ta lấy khoảng cách đó
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50
so sánh với khoảng cách giữa hai khối. Dựa trên một số sai số đưa ra ta sẽ
quyết định liệu rằng hai khối có được trộn vào với nhau hay không.
Trong trường hợp hai khối được trộn lại là hai khối loại 1 do đó ta sẽ
không tính được độ rộng trung bình của các từ trong khối liền kề. Vì vậy
trong trường hợp này ta sẽ tính độ rộng trung bình giữa các từ dựa vào một
khối loại hai khác. Hình 4.10 chỉ ra hai khối được xử lý bởi kỹ thuật trên và
kết quả tương ứng của nó.
4.3.2. Phân tách các cột bị trộn vào một khối
Một vấn đề khác gặp phải đó là các cột riêng biệt được trộn với nhau,
chẳng hạn các cột có chung tiêu đề thường bị trộn thành một cột ở bước phân
đoạn khởi tạo. Trong khi tìm ra dấu hiệu đơn giản để nhận biết các cột được
tách ra ta nhận thấy rằng mối quan hệ một – một giữa các từ trong cột là tiêu
chuẩn để đánh giá các cột được tách ra . Mối quan hệ đó phải đảm bảo là , nếu
một từ Wa có chính xác một từ W b là láng giềng dưới và W b cũng chỉ có duy
nhất Wa là láng giềng trên .
Bước tiếp theo hoàn toàn dễ hiểu : chúng ta sẽ đi phân tách tất cả các
từ có quan hệ một – một vào thành một khối , gọi là khối con của khối đó . Do
đó chúng ta không cần phải quan tâm đến khía cạnh nội dung v à độ cao của
khối để phân tách . Mối quan hệ một - một ở trên chỉ giúp chúng ta tách được
các khối con loại một (trên mỗi dòng chỉ có duy nhất một từ) do đó để tách
các khối con loại hai ta phải sử dụng kỹ thuật khác.
Kết quả của quá trình phân tách sẽ được mô tả trên Hình 4.11 nhưng
quá trình phân tách đến bước này vẫn chưa kết thúc vì cần phải xử lý một số
bước nữa để tránh phân tách sai.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
Hình 4.11 Tách các cột bị trộn
Do kỹ thuật trên áp dụng cho tất cả các khối loại ha i, nhưng có một số
trường hợp ta thấy rõ ràng rằng có một số lượng lớn các từ có quan hệ một –
một nhưng chúng lại không tạo thành cột trong bảng . Tuy nhiên , trong bước
xử lý ở trên chúng ta chưa áp dụng một số điều kiệ n ràng buộc nào để loại trừ
những trường hợp đó .
Hình 4.12 Trộn lại các khối con bị tách
Một quy tắc đơn giản để nhận biết một cột đó là cột đó luôn đi cùng
với những cột khác . Xuất phát từ các khối đã được tách ra làm khối con ,
chúng ta tìm đến các khối láng giềng của khối con mới được phân tách . Tìm
số lượng các khối loại một bao quanh nó , độ cao của chúng , độ rộng các
khoảng trắng cách ly bên trái bên phải và có thể là độ t ương đồng của các từ
trong cột v.v.. để đánh giá sự tồn tại của cột đó . Nếu các điều kiện trên không
thoả mãn theo một tiêu chuẩn nào đó thì khối con mới được tạo ra đó sẽ được
trộn ngược trở lại với khối cha nó (khi đó khối con không thoả mãn tạo thành
một cột).
Cụ thể hoá quá trình nhận biết một khối con được tách riêng từ một
khối cha có tạo thành một cột riêng rẽ trong bảng hay không ta sẽ đi so sánh
các khối con được tách ra với nhau. Quá trình tách một khối thành các khối
con sẽ chia khối cha thành các khối con được đánh số từ B1 đến Bn. Do một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
khối Bi (1 ≤ i ≤ n) bao gồm các từ liên tục nằm cạnh nhau, mỗi khối Bi có
những đặc trưng (XImin, YImin) và (XImax, YImax). Trong đó (XImin, YImin) là toạ
độ góc trên cùng bên trái của khối và (XJmax, YJmax) là toạ độ góc dưới cùng
bên phải của khối. Vì vậy ta sẽ tìm tất cả các khối từ 1 đến n, nếu tồn tại hai
khối i và j thoả mãn điều kiện như sau:
XJmin <= XImin < XImax <= XJmax
YJmin<= YImin < YImax <= YJmax
thì có nghĩa là khối i nằm trong khối j và ta sẽ thực hiện trộn hai khối i và j
vào làm một khối. Quá trình sẽ tiếp tục tìm hai khối bất kỳ đến khi không có
hai khối nào thoả mãn điều kiện trên thì bước tìm kiếm sẽ dừng lại. Điều kiện
trên sẽ đảm bảo các khối con được tách riêng ra sẽ tạo thành một cột trong
bảng hay chúng sẽ được trộn với các khối khác để tạo thành một cột của bảng
khi mà khối đó không thoả mãn điều kiện tạo thành một cột riêng rẽ của bảng.
Một cách khác để nhận biết các khối con bị tách ra không tạo thành
các cột trong bảng đó là dựa vào so sánh khoảng cách giữa hai khối với độ
rộng trung bình của ký tự cách (khoảng cách trung bình giữa các từ trong một
khối). Nhiều trường hợp do sự trùng lặp của ký tự cách mà một khối loại hai
được chia thành các khối con loại một. Do đó các khối con này phải được trộn
ngược lại tạo thành một khối duy nhất.
Hình 4.12 chỉ ra một thí dụ một khối loại hai được phân tách thành ba
khối con và kết quả sau khi phân tích ba khối này lại được trộ n với khối cha
tạo thành một khối duy nhất .
4.3.3. Nhóm các từ bị phân tách
Một số từ mà không có các từ làm láng giềng trên hay láng giềng dưới
thì chúng có thể thuộc về một dòng phân tách (chẳng hạn dòng tiêu đề của
bảng), những từ gắn vào phía cuối của một khối chưa được căn chỉnh hay
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
những từ mô tả cho nội dung của một ô trong bảng. Những từ này sẽ được
thuật toán phân đoạn khởi tạo tách ra thành các khối riêng.
Vì vậy trước tiên chúng ta cần phải tìm xem những từ bị phân tách này
có nằm trong một môi trường bảng hay không, chúng có tương ứng với một ô
(cell) trong bảng hay không và nếu có chúng ta cần phải xem xét chúng với
toàn bộ các cột có thể có của bảng. Để đạt được điều này chúng ta sẽ từng
bước đi qua từng khối và cứ ở chỗ nào có hai hoặc nhiều hơn các khối nằm kề
nhau theo chiều ngang ta sẽ cho đó có thể có bảng và ta đánh giá cấu trúc lề
bao gồm các điểm căn lề (margin points).
Cấu trúc lề nắm giữ thông tin về giới hạn theo chiều dọc của các cột
trong bảng và chứa hàng loạt các điểm căn lề. Các điểm căn lề này chỉ ra ranh
giới bên trái, bên phải của tất cả các khối (các cột trong bảng) nằm liền kề
nhau. Một điểm căn lề mới sẽ được tạo ra trong trường hợp có một điểm
không nằm trong khoảng đã đưa ra. Các điểm này cũng nắm giữ thông tin liệu
chúng có thể bị chặn bởi các đường biên của khối bên trái hay bên phải không
(vì thế ta gọi chúng là các điểm căn lề bên trái, bên phải). Số lượng các dòng
của các khối mà có liên quan đến cặp điểm căn lề trái và phải gọi là số lượng
quan hệ (reference counter) của điểm đó. Một khoảng trắng rộng theo chiều
dọc hay một khối bao phủ toàn bộ độ rộng của tài liệu sẽ đóng lại cấu trúc lề
được đánh giá này.
Hình 4.13 Nhận biết các từ bị phân tách dựa vào các điểm phân lề
Bước tiếp theo sẽ là các điểm căn lề của tất cả các khối được xem xét.
Nếu như số lượng quan hệ của các điểm căn lề bên trái và bên phải của một
khối không đạt được một giới hạn đưa ra, thì khối này này sẽ được trộn với
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
các khối láng giềng tương ứng theo từng phía mà xuất hiện trong một phạm vi
quy định.
Tác dụng của kỹ thuật trên là nhận biết được các từ phân tách mà
không thích hợp với những cột xung quoanh. Hình 4.13 mô tả việc đánh giá
các điểm căn lề và kết quả thu được dựa vào phân tích của kỹ thuật trên.
4.4. Phân tích khối
Trong khi thông thường tất cả các khối loại 2 thể hiện cho cấu trúc
văn bản như là: đoạn văn bản hay đôi khi là một ô của bảng, khối loại 1 là
biểu diễn của một cột trong bảng bao gồm các ô khác nhau. Để đưa ra một
cấu trúc biểu diễn ở mức cao hơn từ tập hợp các loại khối trên, chúng ta cần
phân chia khối loại một thành các ô của bảng. Kết quả của quá trình này được
áp dụng cho Hình 4.11 và kết quả được đưa ra trên Hình 4.14
Hình 4.14 Tách các khối loại 1 thành các ô của bảng
Trong trường hợp những khối loại 2 là láng giềng với khối loại 1 và ta
cũng cần tách khối loại 2 thành các ô của bảng, do đó ta chỉ cần phân đoạn
các dòng cho khối loại 1 thì đồng thời ta cũng tách được các ô cho khối loại 2.
Hình 4.15 mô tả một ví dụ về việc tách các ô trong bảng với hai cột
Pos và Nmb là cột thuộc khối loại 1, cột Description là khối loại 2.
Hình 4.15 Tách các khối loại 2 thành các hàng trong bảng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
Đầu tiên chúng ta sẽ phân đoạn khối loại 1 để tách ra các hàng trong
bảng. Các hàng của bảng được phân cách với nhau bằng các đường kẻ (Hình
4.15 bên trái). Các đường kẻ này đồng thời cũng chia thành các hàng cho khối
loại 2.
4.5. Xác định cấu trúc các cột, hàng
Sau khi đã tiến hành phân đoạn tất cả các khối cơ bản (để tách ra các ô
của bảng), chúng ta vẫn cần khai thác thêm thông tin từ những khối này, xác
định thêm những khối có khả năng tạo thành bảng và đặt các khối tương ứng
với cột và hàng thích hợp.
Để làm việc này chúng ta sẽ sử dụng lại hệ thống ước lượng các điểm
căn lề trong phần 4.3.3. Nhóm các từ bị phân tách về việc nhận biết các từ bị
phân tách. Các khối láng giềng nằm theo chiều ngang tạo ra một cấu trúc lề
bao gồm một danh sách các điểm căn lề.
Trong khi duyệt qua các điểm căn lề từ trái qua phải chúng ta nhận ra
rằng mỗi một lần chuyển từ điểm căn lề phải sang trái xác định đường phân
cách giữa hai cột của bảng và vì thế cũng tính được số lượng cột trong bảng.
Trong trường hợp có những khối trải dài qua nhiều đường phân cách của hai
cột thi ta coi khối đó (hay ô) chứa nhiều cột.
Trong chương 4 đã trình bày phương pháp nhận dạng bảng T-Recs,
một phương pháp nhận dạng bảng với tốc độ nhanh và hiệu quả. Chương này
cũng trình bày những cải tiến của thuật toán phân đoạn khởi tạo (T–Recs) do
T. G. Kieninger đề xuất trước đây nhằm giúp cho thuật toán phân đoạn các
cột một cách chính xác nhất. Một số bước xử lý khối sau khi phân đoạn cũng
được thêm vào nhằm khắc phục những hạn chế của thuật toán phân đoạn khởi
tạo. Hơn thế nữa T-Recs cũng cho thấy nhiều ưu điểm nổi bật so với các
phương pháp nhận dạng bảng khác, đặc biệt nhận dạng bảng không dựa vào
dấu hiệu phân cách của bảng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
Mặc dù vậy thuật toán cũng đề ra những thách thức, đó là một số vấn
đề vẫn còn tồn tại mà thuật toán chưa phân tích đúng. Trường hợp thứ nhất đó
là việc tách các khối loại 2 (không nằm cùng khối loại 1) ra thành các hàng
trong bảng. Thuật toán chỉ đề ra phương pháp tách các hàng dựa vào khối loại
một. Trường hợp thứ hai, thuật toán thường nhận dạng sai đối với các dòng
tiêu đề của thư, chẳng hạn như địa chỉ thư, ngày gửi .v.v.. thuật toán thường
nhận dạng chúng là bảng dữ liệu. Do đó những cải tiến phương pháp nhận
dạng trong những trường hợp trên là cần thiết để thuật toán nhận dạng được
tất cả các loại bảng.
Một trong những thách thức lớn đối với phương pháp nhận dạng bảng
T-Recs là khả năng nhận dạng được môi trường bảng trong một trang tài liệu,
thông thường T-Recs sẽ được thực hiện trên từng đoạn văn bản của trang tài
liệu và việc phân tích trên từng đoạn văn bản đó để xem có tồn tại bảng
không. Trong trường hợp một bảng dữ liệu và một đoạn văn bản nằm liền kề
nhau không có sự khác biệt lớn (chẳng hạn không coi đó là hai đoạn văn bản
riêng biệt) thì sẽ rất khó để xác định được bảng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
CHƢƠNG 5
CHƢƠNG TRÌNH THỬ NGHIỆM VÀ MINH HỌA
THUẬT TOÁN T-RECS++
Phần này sẽ mô tả chương trình thử nghiệm T-Recs++ nhận dạng bảng
bằng thuật toán T-Recs++ được mô tả trong 4.2.2. Chương trình gồm hai phần
chính:
Phần một là quét qua toàn bộ ảnh để nhận dạng và xây dựng các
hình bao của các từ có trong ảnh.
Phần thứ hai dựa vào các hình bao thu được từ phần một và thuật
toán T-Recs++ để nhận dạng các cột có thể có của bảng trong
từng trang tài liệu ảnh.
5.1. Mô tả chƣơng trình
Chương trình thử nghiệm dưới đây chỉ dừng lại ở phần chính đó là
nhận dạng các cột có thể có của bảng. Vì khả năng còn hạn chế và thời gian
không nhiều nên các bước xử lý nhằm khắc phục lỗi hay bước tách các cột
của bảng thành các dòng chưa đưa vào trong chương trình. Chương trình cũng
chỉ áp dụng nhận dạng các bảng khi chúng không có các đường kẻ. Chương
trình hoạt động bao gồm các bước như sau:
Bước 1: Tài liệu ảnh được tải vào chương trình bằng việc người sử
dụng chọn một tệp ảnh nhị phân (bmp) để mở. Khi đó tài liệu ảnh sẽ được
quét để nhận dạng số dòng văn bản có trong tài liệu.
Bước 2: Sau khi tài liệu được quét để nhận dạng số dòng văn bản có
trong tài liệu. Chương trình sẽ thực hiện quét lần lượt qua tất cả các dòng, tại
mỗi dòng sẽ nhận dạng từng ký tự và nhận dạng từng từ trên mỗi dòng. Từ đó
xây dựng hình bao cho mỗi từ trên từng dòng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
Bước 3: Dựa vào thông tin hình bao của các từ, chương trình sẽ xây
dựng các từ nằm trong cùng một khối bằng thuật toán T-Recs++. Thuật toán
sẽ quét từ trên xuống dưới và nhận biết các đoạn văn bản khác nhau, sau đó
thực hiện thuật toán T-Recs++ trên các đoạn văn bản khác nhau đó. Cách
nhận biết các đoạn văn bản khác nhau đó là dựa vào khoảng trắng giữa các
dòng văn bản. Và kết quả chương trình đưa ra ảnh bao gồm các từ thuộc cùng
một khối (một cột).
Chương trình có một tham số cần phải thiết lập, đó là tham số số điểm
ảnh lớn nhất giữa hai ký tự trong một từ, bởi vì tham số này phụ thuộc vào
kích cỡ của phông chữ. Tham số này giúp xác định các ký tự thuộc cùng một
từ. Dựa vào tham số này để chương trình nhận biết khi hai ký tự cách nhau
một khoảng như thế nào thì nhóm chúng lại làm một từ.
Giao diện của chương trình được chia thành 3 phần chính được mô tả
trên Hình 5.1. Phần 1 cho biết thông tin về toạ độ, chiều rộng, chiều cao, hình
dạng của từng ký tự sẽ hiển thị phía trên khi nhận dạng, phần 2 gồm các nút
mở tệp , đặt tham số và 2 khung chứa ảnh . Phần 3 chứa các nút lệnh nhận
dạng.
Hình 5.1 Giao diện chương trình T-Recs
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
Nhấn vào nút Mở tệp ảnh để chọn một ảnh nhị phân để mở.
Nhấn vào nút Đặt tham số để thiết lập tham số số điểm ảnh tối đa
giữa hai ký tự (được đặt mặc định là 5).
Nhấn vào nút XD hình bao để nhận dạng hình bao cho các từ trong
ảnh và đồng thời chương trình sẽ vẽ ra môt hình chữ nhật nhỏ nhất bao từ.
Nhấn vào nút Nhận dạng để nhận dạng các cột có thể có của bảng
trong ảnh.
Nút Ký tự tiếp theo cho phép nhận dạng từng ký tự của ảnh.
5.2. Một số kết quả
Với một đoạn văn bản thông thường , T-Recs++ chỉ xây dựng được
một khối duy nhất . Hình 5.1 là kết quả nhận dạng đối với một đoạn văn bản
thông thường.
Hình 5.2 Nhận dạng khối văn bản với T-Recc++
Với tài liệu ảnh là một bản thông báo như trên Hình 5.3 Một kết quả
nhận dạng khá phức tạp hơn. Các trường hợp chỉ có một dòng văn bản hay có
ký tự cách trùng lặp có thể dễ dàng xử lý để nhận biết không có môi trường
bảng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
Hình 5.3 Nhận dạng tài liệu ảnh dạng thông báo với T-Recs++
Một trường hợp khác có tồn tại môi trường bảng như trên Hình 5.4.
Đầu tiên chương trình nhận thấy ảnh có ba đoạn văn bản và thực hiện thuật
toán T-Recs++ trên 4 đoạn văn bản này. Mặc dù hai đoạn văn bản phía trên
không phải là bảng và có ký tự cách trùng lặp ở một vị trí, và thuật toán đã
nhận dạng những đoạn văn bản này có nhiều hơn một cột dữ liệu. Trong tệp
ảnh trên Hình 4.4 chỉ có mỗi đoạn văn bản thứ tư là môi trường bảng và thuật
toán đã nhận dạng chính xác 5 cột của bảng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
Hình 5.4 Nhận dạng môi trường bảng với T-Recs++
Trên đây là một kết quả thực nghiệm của thuật toán T -Recs++. Mặc
dù đã với tài liệu có môi trườ ng bảng chương trình đã nhận dạng được song
chỉ dừng lại ở việc nhận dạng được các cột có thể có của bảng. Sau đây là một
số kết luận và ý kiến đề xuất để tiếp tục phát triển luận văn .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
KẾT LUẬN VÀ ĐỀ XUẤT
Luận văn đã trình bày phương pháp phân tích bảng bên trong tài liệu
ảnh và một số khái niệm , kỹ thuật trong lĩnh vực xử lý ảnh . Nhận dạng bảng,
nhận dạng biểu mẫu và nhận dạng ảnh là những bài toán điển hình về nhận
dạng cấu trúc và các đối tượng đặc biệt trong tài liệu ảnh. Trong khuôn khổ
của mình, luận văn đã đi vào nghiên cứu hai thuật toán để nhận dạng bảng và
các đối tượng ảnh trong tài liệu ảnh kỹ thuật.
Nhận dạng đối tượng ảnh nhằm phân tách riêng rẽ hai thành phần văn
bản và ảnh trong tài liệu. Có rất nhiều hướng nghiên cứu khác nhau đề phân
tách văn bản và ảnh, một trong những hướng nghiên cứu đưa ra nhiều phương
pháp phân tách hiệu quả nhất đó là phân tách hai đối tượng văn bản và ảnh
dựa vào phân tích thành phần liên thông.
Thuật toán nhận dạng bảng được đề cập trong luận văn dựa trên thuật
toán T-Recs do G. Kieninger đề xuất, tuy nhiên các bước thực hiện mà
Kieninger đưa ra vẫn còn nhiều hạn chế và nhận dạng sai trong một số trường
hợp. Luận văn đã đưa ra những cải tiến các bước thực hiện của thuật toán, đặt
tên là T-Recs++. Một số thuật toán nhận dạng bảng trước đây dựa trên dấu
hiện phân cách các ô trong bảng, chẳng hạn như là các đường kẻ, khoảng
trắng .v.v.. Tuy nhiên T-Recs++ là phương pháp nhận dạng bảng không dựa
trên một dấu hiệu phân cách nào, kể cả trong trường hợp khoảng cách giữa
hai cột trong bảng cách nhau một khoảng cách hẹp. Đó chính là một ưu điểm
nổi bật của thuật toán. Trong một khối văn bản thuật toán nhận dạng khá
chính xác các cột dữ liệu nếu có của bảng. Một vấn đề còn tồn tại của thuật
toán đó là khả năng nhận dạng các dòng của bảng, trong thuật toán này việc
nhận dạng ra dòng của bảng phụ thuộc vào khối loại một. Trong trường hợp
bảng chỉ bao gồm khối loại hai phương pháp tách các dòng của bảng nhận
dạng phải dựa vào dấu hiệu phân tách nào đó. Kết quả thực nghiệm ở trên cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
thấy thuật toán T-Recs++ có khả năng nhận dạng chính xác gần như hoàn
toàn các cột có của bảng, kể cả trong trường hợp khoảng cách giữa các cột
của bảng hẹp. Kết quả thực nghiệm cho thấy độ chính xác trong việc nhận
dạng các cột của bảng từ 92% đến 96%. Một số lỗi nhận dạng có thể xuất hiện
là trường hợp trùng lặp ký tự cách tại cùng một vị trí trên các dòng văn bản,
một số từ nằm ở các vị trí bất thường của đoạn văn bản cũng tạo thành cột hay
trường hợp các dòng đơn .v.v..
Các nghiên cứu thực nghiệm ở trên tuy chỉ áp dụng với ảnh nhị phân,
tuy nhiên với tư tưởng và các bước thực hiện của hai thuật toán nhận dạng
bảng đã trình bày ở trên có thể áp dụng đối với ảnh đa cấp xám và ảnh màu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
TÀI LIỆU THAM KHẢO
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
DANH MỤC TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Ngô Quốc Tạo: “Bài giảng xử lý ảnh”.
[2] Đỗ Năng Toàn, Phạm Việt Bình: “Giáo trình xử lý ảnh”
Tiếng Anh
[1] D. Rus and K. Summers, “Using White Space for Automated
Document Structuring”, Technical Report TR 94-1452, Department
of Computer Science, Cornell University, 1994.
[2] D. X. Le, G. R. Thoma, and H.Wechsler. “Classification of binary
document images into textual or nontextual data blocks using neural
network models”. Machine Vision and Applications, 8:289_304,
1995.
[3] D.N. Ying, E.J. Wang, L. Ye, W. Li, and Y. Wang, “A Study on
Automatic Input and Recognition of Engineering Drawing,” Proc.
CAD/GRAPHICS, pp. 478-481, Hangzhou, China, 23-26 Sept. 1991
[4] Fletcher A, Kasturi R 1988 A robust algorithm for text string
separation from mixed text /graphics images. IEEE Trans. Pattern
nal. Machine Intell. PAMI-10: 910–918
[5] H. Luo and I. Dinstein. “Using Directional Mathematical
Morphology for Separation of Character Strings from Text/Graphics
Image”. In Shape, Structure and Pattern Recognition (Post-
proceedings of IAPR Workshop on Syntactic and Structural Pattern
Recognition, Nahariya, Israel), pages 372_381. World Scientific,
1994.
[6] H. Yamada et al., “MAP: Multi-Angled Parallelism for Feature
Extraction From Topographical Maps,” Pattern Recognition, vol. 24,
no. 6, pp. 479-488, 1991.
[7] K. Y. Wong, R. G. Casey, and F. M. Wahl. “Document Analysis
System”. IBM Journal of Research and Development,
26(6):647_656, 1982.
[8] Kasturi, O‟Gorman, Govindaraju: “Document image analysis: A
primer”, 2002.
[9] Nartker T A, Rice S V, Kanai J 1994 OCR Accuracy. UNLV‟s
Second Annual Test. Technical Journal INFORM, University of
Nevada, Las Vegas.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
[10] O‟Gorman L 1993 The document spectrum for structural page layout
analysis. IEEE Trans. Pattern Anal. Machine Intelli. AMI-15: 1162–
73.
[11] Pavlidis T, Zhou J 1991 Page segmentation by white streams. Proc.
1st Int. Conf. on Document Analysis and Recognition ICDAR), St.
Malo, France, pp 945–953.
[12] Q. Yuan, C. L. Tan: “Text Extraction from Gray Scale Document
Images Using Edge Information”. In Proceedings of the Sixth
International Conference on Document Analysis and Recognition
(ICDAR‟01) 2001, IEEE.
[13] S, Baumann, M. Malburg, H.-G. Hein, R. Hoch, T. Kieninger, and N.
Kuhn, “Document analysis at DFKI, part 2: Information extraction,”
DFKI Research Report RR-95-03, German Research Center for
Artificial Interligence (DFKI), Kaiserlautern, March 1995.
[14] T. Kaneko. “Line Structure Extraction from Line-Drawing Images”.
Pattern 1 Recognition, 25(9):963_973, 1992.
[15] T. Pavlidis and J. Zhou. “Page Segmentation and Classification”.
CVGIP: Graphical Models and Image Processing, 54(6):484_496,
November 1992.
[16] Z. Lu, “Detection of Text Regions from Digital Engineering
Drawings”, IEEE Transactions on PAMI, 20(4):431:439, April 1998.
[17] M. A. Rahgozar, Z. Fan, and E. V. Rainero, “Tabular document
recognition”, in Proc. Of the SPIE Conference on Document
Recognition, 1994.
[18] E. Green and M. Krishnamoorthy, “Recognition of table using table
grammars”, in Proc. of the 4-th Symposium on Document Analysis
and Information Retrieval – SDAIR95, Las Vegas, Nevada, 1995.
[19] Thomas G.Kieninger, “Table Structure Recognition Based On
Robust Block Segmentation”, 1998.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
Phụ lục
Các file đính kèm theo tài liệu này:
- 22LV09_CNTT_KHMTNguyenThiHieu.pdf