Luận văn thạc sỹ công nghệ thông tin tìm hiểu phương pháp phân tích bằng bên trong tài liệu ảnh
- 78 trang
- file .pdf
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
------------ ------------
Nguyễn Thị Hiếu
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
Thái Nguyên, tháng 11 năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
------------ ------------
Nguyễn Thị Hiếu
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
Chuyên ngành: Khoa học máy tính
Mã số: 604801
Ngƣời hƣớng dẫn Khoa học:
PGS.TS Ngô Quốc Tạo
Thái Nguyên, tháng 11 năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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 MỤ C CÁ C HÌNH VẼ --------------------------------------------------------
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2.5. Phân tích đặ c trƣng củ a tà i liệ u ả nh -------------------------------------
15 2.6. Phân tích đố i tƣợ ng văn bả n trong tà i 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ố cụ c củ a trang tà i liệ u ả nh ----------------------------
-- 18 2.7. Nhận dạng ký tự quang học (OCR) ------------------------------------
--- 19 2.7.1. Thuậ t toá n OCR -----------------------------------------------------
20
2.7.1.1. Trích chọn đặc trƣng --------------------------------------- 20
2.7.1.2. Phân loại ------------------------------------------------------ 21
2.7.2. Nhận dạng ký tự dựa trên ngữ cảnh ------------------------------ 21
2.8. 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. Tổ ng quan về phân tá ch văn bả n – ảnh ---------------------------------
24 3.2. Những đặc trƣng chung của một tệp tài liệu ảnh ---------------------
27
3.3. 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 TÀ I LIỆ U Ả NH ----------------------------------------------------------
-- 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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 VÀ MINH HỌ A THUẬ T
TOÁN T-RECS++ ---------------------------------------------------------------------
56
5.1. Mô tả chƣơng trình -------------------------------------------------------
56
5.2. Mộ t số kế t quả -------------------------------------------------------------
58 KẾ T LUẬ N VÀ ĐỀ XUẤ T -----------------------------------------------------
----- 61 THUẬT NGỮ TIẾNG ANH
3–D 3 Dimensions
CAD Computer Aided Design
CAM Computer Aided Manufacturing
CC Chain Code
CCs Connected Components
CPU Control Processing Unit
DP Dynamic Programming
HWRatio Heigh Width Ratio
K – NNR K – Nearest Neighbor Rule
LC Linear Component
LSD Local Stroke Density
NCCs New Connected Components
NNR Nearest Neighbour Rule
OCR Optical Character Recognition
T-Recs Table Recognition System
WBRatio White Black Ratio
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
WDG White-space Density Graphs
DANH MỤ C CÁ C HÌ NH VẼ
Hình Sơ đồ quá trình xử lý tà i liệ u
2.1
Hình Sơ đồ quá trình phân tích trang tà i liệ u
2.2
Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên
Hình
bản, (b) chọn ngưỡng thấp, (c) chọn ngưỡng hợp lý, (d) chọn ngưỡng
2.3
quá cao.
Hình Ảnh nguyên bản(Vân tay) bên trái và ảnh sau khi làm mảnh bên phải.
2.4
Tài liệu ảnh trước và sau các bước tiền xử lý. Ảnh (a) gốc, ảnh (b) ảnh
Hình
sau khi chuyển về ảnh nhị phân, ảnh (c) ảnh sau khi chỉnh nghiêng, ảnh
2.5
(d) ảnh sau khi lọc nhiễu.
Hình văn bả n bị nghiêng sau khi đượ c qué t qua má y qué t.
2.6
Hình Ví dụ minh họa kết quả phân tích bố cục của trang tài liệu ảnh
2.7
Hình Chữ viế t tay có thể gây nhầ m lẫ n
2.8
Hình Ví dụ về các đối tượng văn bản và đối tượng ảnh
3.1
Hình Biểu diễn các điểm ảnh giao nhau
3.2
Hình Một số trường hợp ngoại lệ
3.3
Hình Sơ đồ thuậ t toá n phân tá ch văn bả n
3.4
Hình Hình 3.5 Nhậ n dạ ng đườ ng kẻ nghiêng vớ i phé p toá n ké o da ̃n
3.5
Hình Ví dụ minh họa tư tưởng của thuật toán khởi tạo
4.1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình thuật khở i tạ o đố i vớ i mộ t đoạ n văn bả n
4.2
Hình Trường hợp thuật toán nhận dạng sai cột
4.3
Hình Trường hợp giữa các dòng của một cột trong bảng có ô trắng
4.4
Hình Mô phỏng việc thực hiện các bước đã cải tiến của thuật toán
4.5
Hình Quá trình phân đoạn các cột của bảng
4.7
Hình Trường hợp một ô của bảng chiếm nhiều dòng
4.8
Hình Những mặt hạn chế của thuật toán
4.9
Hinh Trộn hai khối bị phân tách
4.10
Hình Tách các cột bị trộn
4.11
Hình Trộ n lạ i cá c khố i con bị tá ch
4.12
Hình Tách các khối loại 1 thành các ô của bảng
4.14
Hình Tách các khối loại 2 thành các hàng trong bảng
4.15
Hình Giao diệ n chương trình T-Recs
5.1
Hình Nhậ n dạ ng khố i văn bả n vớ i T-Recc++
5.2
Hình Nhậ n dạ ng tà i liệ u ả nh là bả ng quy chế vớ i T-Recs++
5.3
Lêi c¶m ¬n
Trong quá trình 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 Việ t Nam, luậ n văn củ a tôi đã đượ c hoà n thà nh . Mặ c dù
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
đã 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 vẫn còn nhiều hạn chế nên luận vă n khó tránh khỏi
những thiếu sót trong quá trình là m luậ n văn .
Để hoà n thà nh đượ c 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 giú p đỡ em trong suố t
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 Việ n Công
nghệ Thông tin – Việ n khoa họ c Việ t N am đã giả ng dạ y và hướ ng dẫ n
em trong suố t 2 năm học qua. Em cũ ng xin cả m ơn ban lã nh đạ o khoa và
toà n thể thầ y cô giá o trong khoa Công Nghệ thông tin – Đạ i Họ c Thá i
Nguyên đã tạ o điề u kiệ n tố t nhấ t giú p em họ c tậ p và hoà n thà nh luậ n
văn nà y . Và cuối cùng tôi cũng xin cảm ơn gia đình , các bạn trong nhóm
luậ n văn và toà n thể cá c họ c viên lớ p Cao họ c K 6 đã độ ng viên , quan
tâm và giú p đỡ tôi trong thơ ì gian qua.
Cuố i cù ng tôi rấ t mong nhậ n đượ c sự chỉ dẫ n , góp ý của các thầy
cô và các bạn để luận văn của tôi được hoàn thiện hơn .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
CHƢƠNG 1: MỞ ĐẦU
Nhận dạng và xử lý ảnh là một lĩnh vực mang tính khoa học và công
nghệ. Ở Việt Nam Nhận dạng và xử lý ảnh là một ngành khoa học mới mẻ so
với nhiều ngành khoa học khác nhưng tốc độ phát triển của nó rất nhanh. Sự ra
đời của nó đã tạo ra các kỹ thuật quan trọng ảnh hưởng trực tiếp đến các lĩnh
vực như: Tivi, truyền thông, kỹ xảo đồ hoạ…
Cùng với sự phát triể n đó có nhữ ng nhu cầ u thự c tế đặ t ra thách
thức các nhà khoa học máy tính càng nhiều . Nhữ ng công việ c , nhữ ng bà i
toá n đượ c xử lý theo lố i cổ truyề n không theo kịp tố c độ phá t triể n cu ̉a
công nghệ ngày nay. Một trong nhữ ng bà i toá n đó chính là các tài liệu đươ ̣c
lưu trữ trên các chất liệu cổ truyền như giấ y, gỗ , vải vớ i khố i lượ ng khổ ng
lồ , chứ a đự ng rấ t nhiề u tri thứ c củ a nhân loạ i nhưng lạ i không có độ bề n
vĩnh cử u , khó xử lý và lưu trữ . Mộ t bà i toá n khá c là ngà y nay công việ c
văn phò ng liên quan nhiề u đế n cá c tà i liệ u không đơn thuầ n là tà i liệ u
chữ mà tà i liệ u có nhiề u thành phần như bảng biểu , ảnh. Tấ t cả cá c tà i liệ u
đó nế u tiế p tụ c lưu trữ theo phương phá p cổ truyề n thì rấ t phứ c tạ p và khó
xử lý . Vậ y là m thế nà o để chuyể n đổ i nhữ ng kho tà ng tri thứ c trên và o
má y tính để lưu trữ , xử lý dễ dàng, thuậ n tiên và nhanh gọ n . Mộ t lĩnh
vự c của khoa học nhân da ̣ng là Phân tích tài liệu ảnh đã ra đờ i nhằ m biể u
diễ n thông tin trong cá c tà i liệ u ả nh dướ i dạng có cấu trúc.
Hệ phân tích và nhận dạng tài liệu ảnh có mục đích là chuyển đổi tự động
những thông tin lưu trữ trong tài liệu giấy thành biểu diễn dưới dạng những cấu
trúc mà có thể truy xuất, thay đổi được bằng máy tính. Quy trình xử lý của một
hệ phân tích tài liệu bắt đầu bằng việc lấy dữ liệu, các tài liệu từ giấy in sẽ được
quét qua máy quét để lưu trữ trong máy tính dưới dạng các tệp dữ liệu ảnh.
Một tài liệu ảnh là một cách biểu diễn trực quan của các trang tài liệu
được in như một bài tạp chí, một lá thư, một trang báo, một mẩu thư hay một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
bản vẽ kỹ thuật, .v.v.. Một tài liệu ảnh có thể bao gồm các chuỗi ký tự, các hình
vẽ, các bức ảnh, .v.v.. Bên cạnh việc chuyển toàn bộ nội dung của tài liệu sang
tài liệu điện tử cũng cần phải bảo toàn cấu trúc và định dạng của tài liệu. Mục
tiêu cơ bản của một hệ phân tích tài liệu ảnh hoàn chỉnh đó là chuyển một tài
liệu lưu trữ bằng giấy sang dạng biểu diễn có thứ tự cấu trúc và nội dung của
nó. Tài liệu được chuyển sang phải có khả năng thay đổi, soạn thảo và lưu trữ
bởi vì nội dung của tài liệu có thể truy cập bởi cấu trúc của nó thay vì phải truy
cập dưới dạng những mẫu ảnh. Có một số lượng lớn ứng dụng của hệ phân tích
tài liệu ảnh được ứng dụng trong các lĩnh vực như: dịch vụ bưu chính, Chính
phủ, chăm sóc y tế, thư viện, ...v.v.
Mục đích của luận văn là nghiên cứ u kỹ thuậ t nhậ n dạ ng bả ng và trích
chọn ra đối tượng của tài liệu ảnh. Kỹ thuật “Phân tích bảng – T-Recs” là
nghiên cứ u chính .
Với tư tưởng chính của “Phương pháp phân tích bả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 cấu trúc bảng. Thay
vào đó phương pháp sẽ tập trung vào việc 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). Phương pháp 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
bottom - up.
1.1. Cơ sở nghiên cứu và mục đích của luận văn
Ảnh là một đối tượng khá phức tạp về đường nét, dung lượng điểm ảnh, độ sáng
tối, môi trường để thu nhận ảnh phong phú kéo theo nhiễu. Trong nhiều khâu
phân tích ảnh ngoài việc đơn giản hoá các phương pháp toán học đảm bảo tiện
lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử ảnh theo
cách của con người. Trong các bước xử lý đó nhiều khâu hiện nay đã xử lý theo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
các phương pháp trí tuệ của con người. 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. 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 đó.
Nhận dạng bảng là bài toán nhận dạng ra cấu trúc bảng có trong trang tài
liệu ảnh, bao gồm việc nhận dạng các cột, các dòng và các ô có chứa dữ liệu
trong bảng. Nhận dạng đối tượng ảnh là bài toán nhằm phân tách các đối tượng
ảnh trong những trang tài liệu ảnh có chứa hỗn hợp các đối tượng là chuỗi ký tự
và các đối tượng ảnh như: các sơ đồ, hình vẽ, bức ảnh …v.v.
Mặc dù đã có nhiều kỹ thuật trong hệ thống nhận dạng cấu trúc. Tuy nhiên
những nghiên cứu trên những vấn đề đó vẫn còn tiếp tục phát triển bởi vì chất
lượng, độ chính xác, tính hiệu quả của những phương pháp được công bố trước
đây vẫn còn chưa hoàn chỉnh và cần phải cải tiến chúng. Luận văn này trình bày
kỹ thuật nhận dạng cấu trúc bảng bên trong tài liệu ảnh T-Recs và đề xuất một
số phương pháp khắc phục hạn chế thuật toán T-Recs để hoàn thiện hiện hơn
phương pháp phân tích bảng.
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Chương 2 Tổ ng quan về hệ phân tích tà i liệ u ả nh và cá c thà nh phâ ̀n
chính trong hệ phân tích tà i liệ u ả nh : Lấ y dữ liệ u , xử lý ả nh , trích chọn
đặc trưng, nhậ n dạ ng đố i tượ ng ả nh và nhậ n dạ ng văn bả n .
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.
CHƢƠNG 2: TỔNG QUAN VỀ HỆ PHÂN TÍ CH TÀ I LIỆ U Ả NH
2.1. Tài liệu ảnh
Hình ảnh của một đối tượng là sự sao chụp lại chính bản thân đối tượng
đó. Ảnh được hình thành qua một hệ thống ảnh.
Tài liệu ảnh là các file ảnh đã được số hóa thu được bằng cách: quét các
trang tài liệu, chụp ảnh, máy fax, hoặc từ vệ tinh, các file ảnh này được lưu trữ
trong máy tính. Ảnh tài liệu có nhiều loại: đen trắng, ảnh màu, ảnh đa cấp
xám,…v.v.
2.2. Hệ phân tích trang tà i liệ u
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
Hệ phân tích trang tà i liệ u : Là một hệ thống bao gồm những thuật toán và
các k ỹ thuật có thể áp dụng cho các tài liệu ảnh để lấy ra được các thông tin mà
máy tính có thể đọc được và hiểu được từ các điểm dữ liệu ảnh.
Một lĩnh vực thu được nhiều thành công nhất trong phân tích tài liệu ảnh đó là
Nhận dạng Ký tự Quang học (OCR), phần mềm có khả năng nhận, chuyể n đổ i
cá c ký tự từ các loại tài liệu dưới dạng ảnh sang tà i liệ u dướ i dạ ng text . OCR
giúp người dùng có khả năng soạn thảo và tìm kiếm nội dung của tài liệu.
Thành phần chính có trong một hệ phân tích tài liệu: Mục đích của một
hệ phân tích tài liệu là có khả năng nhận dạng ra các đối tượng văn bản, đối
tượng ảnh trong tài liệu ảnh và có khả năng trích chọn ra được các thông tin mà
người dùng mong muốn. Chúng ta có thể chia một hệ phân tích tài liệu thành
hai phần. Phần thứ nhất là xử lý văn bản, liên quan đến việc xử lý các đối tượng
văn bản: ký tự, chuỗi ký tự, các từ. Xử lý văn bản bao gồm các công việc sau:
xác định độ nghiêng của tài liệu (độ nghiêng hay độ xiên của tài liệu ảnh do tài
liệu được đặt không đúng khi thực hiện quét vào từ máy quét), tìm các cột, các
đoạn văn bản, các dòng văn bản, các từ và cuối cùng là nhận dạng văn bản (có
thể thêm các thuộc tính như loại phông chữ, kích thước của phông chữ) bởi
phương pháp nhận dạng ký tự quang học (OCR).
Phần thứ hai là xử lý các đối tượng ảnh là các đối tượng tạo ra từ các đường kẻ
trong sơ đồ, các đường kẻ phân tách giữa các đoạn văn bản, các hình vẽ, các
lôgô của công ty… Sau khi áp dụng các kỹ thuật phân tích ảnh và văn bản, các
đối tượng cần nhận dạng trong tài liệu ảnh được trích ra và được biểu diễn dưới
dạng một tài liệu định dạng khác, chẳng hạn như word, html… Ta có thể tóm tắt
quá trình xử lý của hệ phân tích tài liệu theo sơ đồ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
Hình 2.1 [8]:
Xử lý tài liệu
Xử lý văn bản Xử lý đối tượng
ảnh
Nhận dạng Phân tích Xử lý Xử lý vùng
ký tự quang câu truc đường và ký tự đặc
học trang kẻ biêt
Xác định độ nghiêng, Vùng được tô
Văn bản
dòng văn bản, các khối Đường thẳng,
cong,
đường
văn bản, các đoạn văn góc
Hình 2.1 Sơ đồ quá trình xử lý tà i liệ u
Tại sao lại phải phân tích tài liệu ? Nhữ ng bà i toá n trong phầ n giớ i
thiệ u đã đề cậ p , ta hã y xem xé t kỹ hơn về bà i toá n điể n hình để thấ y đượ c
sự cầ n thiế t củ a việ c phân tích tà i liệ u .
- Lượ ng tri thứ c vô giá củ a nhân loạ i vớ i số lượ ng lớ n đươ ̣c
lưu trữ
trong cá c thư việ n cổ điể n dướ i cá c chấ t liệ u như giấ y , vải, gỗ vẫ n cò n tồ
n tạ i rấ t nhiề u, việ c cá c tà i liệ u bị mất các thông tin , thiếu thông tin, số lượng
bản sao hạn chế hay thậm chí các tài liệu bị thoái hoá theo thời gian là những vấn
đề phổ biến. Vì vậy chúng cần phải được khôi phục và chỉnh sửa bằmg những kỹ
thuật phân tích tài liệu.
- Ngày nay các văn phòng hiện đại các công việc đều được giải
quyết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
dự a và o má y tính . Các tài liệu văn bản với nhiều đối tượng (chữ , hình ảnh ,
các sơ đồ) đượ c tạ o ra trên nhiề u m áy tính khác nhau , phầ n mề m kha ́c nhau
do đó có thể là cá c định dạ ng củ a cá c tà i liệ u đó là không tương thích vớ i
nhau, kích thước cũng khác nhau . Như vậ y cầ n mộ t hệ phân tích tà i liệ u giúp
nhận dạng các loại tài liệu, trích chọn ra được các phần chức năng và có thể
chuyển từ một định dạng máy tính này sang một định dạng khác.
- Mộ t bài toán khác đượ c đề cậ p là các máy phân loại thư tự
động dùng để phân loại, sắp xếp thư và nhận dạng địa chỉ thư. Những máy
này đã có từ những thập kỷ trước, nhưng ngày nay yêu cầu cao hơn đó là
xử lý nhiều thư hơn, nhanh hơn và yêu cầu chính độ xác cao hơn.
Những bài toán trên đã tạo ra thách thức và động lực cho sự phát triển
những giải pháp trong tương lai của một hệ phân tích tài liệu.
Hình 2.2 mô tả cá c bướ c xử lý cho mộ t hệ phân tích tà i liệ u [8]. Sau
khi dữ liệ u (tài liệu ảnh ) đượ c đưa và o , tài liệu ảnh trải qua các bước xử lý
điểm ảnh và phân tích đặc trưng và sau đó phần nhận dạng văn bản và phầ n nhậ
n dạ ng ảnh đượ c tá ch ra hai chứ c năng riêng rẽ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
Trang tai liêu
Thu nhân dư liêu
Xư ly điêm anh
Phân tich đăc trưng
Phân tích và nhận Phân tích và nhận
dạng đối tượng văn dạng đối tượng ảnh
Mô tai liêu
Hình 2.2 Sơ đồ quá trình phân tích trang tà i liệ u
Các hệ phân tích tài liệu sẽ ngày càng phát triển và hiển nhiên là chúng sẽ
có trong các hệ xử lý tài liệu. Chẳng hạn như, hệ thống OCR sẽ
được sử dụng rộng rãi để lưu trữ, tìm kiếm và trích dẫn từ các tài liệu lưu trữ
trên giấy. Các kỹ thuật phân tích cách bố trí trong một trang tài liệu giúp nhận
dạng những biểu mẫu (form) riêng biệt, hay định dạng của một trang tài liệu và
cho phép sao lưu tài liệu đó. Các sơ đồ có thể được đưa vào từ các bức ảnh hay
vẽ bằng tay và có thể thay đổi, soạn thảo lại chúng. Sử dụng máy tính có thể
chuyển các tài liệu viết bằng tay thành các tài liệu điện tử được lưu trữ trong
máy tính. Các tài liệu được lưu trữ trong các thư viện, các tài liệu kỹ thuật trong
các công ty sẽ được chuyển đổi sang thành tài liệu điện tử nhằm nâng cao hiệu
quả, thuận tiện trong việc lưu trữ và dễ dàng mang đến cơ quan hay mang về
nhà. Mặc dù tài liệu sẽ ngày càng được xử lý và lưu trữ nhiều trong máy tính
nhưng trên thực tế có rất nhiều các hệ thống khác nhau mà tài liệu giấy là phương
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
tiện làm việc hiệu quả và chắc chắn rằng tài liệu giấy vẫn sẽ là phương tiện làm
việc với chúng ta trong một vài thập kỷ nữa. Vấn đề ở đây là làm sao chúng ta
tích hợp những tài liệu giấy vào trong máy tính xử lý.
Sau đây ta sẽ tìm hiểu ngắn gọn các bước xử lý của một hệ phân tích
tài liệu ảnh.
2.3. Thu nhậ n dƣ̃ liệ u ảnh
Các dữ liệu trên các trang tài liệu giấy thường được quét qua máy quét và
đưa vào máy tính dưới dạng file ảnh , chúng bao gồm các điểm ảnh (pixels) và
đượ c lưu trữ . Vớ i ả nh nhị phân g iá trị điểm ảnh có thể là 0 hoặ c 1 ,vớ i ảnh
đa cấp xám và ảnh màu giá trị điể m ả nh nằ m trong khoả ng 0 đến 255 với 3
giá trị R, G, B từ 0 đến 255. Ở độ phân giải thông thường thì có 120 điểm ảnh
trên 1 centimet và với 1 trang có kích thước 20 x 30 cm thì tạo ra một ảnh với
2400 x 3600 điểm ảnh. Do đó có thể thấy rằng một tài liệu ảnh chỉ bao bồ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.
2.4. Tiề n xử lý điểm ảnh
Bước tiếp theo trong một hệ phân tích tài liệu là thực hiện một số thao
tác xử lý trên tài liệu ảnh thu được để chuẩn bị cho những bước phân tích tiế p
theo. Chẳng hạn như các thao tác: chọn ngưỡng để chuyển ảnh đa cấp xám, ảnh
màu về dạng ảnh nhị phân, giảm nhiễu để loại bỏ những dữ liệu không liên quan,
phân đoạn để phân tách các thành phần khác nhau trong ảnh và cuối cùng là làm
mảnh hay dò biên để dễ dàng xác định các vùng, các đặc trưng thích hợp và các
đối tượng cần quan tâm. Sau những bước xử lý ở trên, dữ liệu thường được biểu
diễn dưới dạng nén lại như dùng mã hoá CC và biểu diễn dưới dạng véctơ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
2.4.1. Xƣ̉ lý nhị phân
Với những ảnh đa cấp xám các thông tin đã sẵ n ở dạng nhị phân chẳng hạn như
các chuỗi văn bản hay các đối tượng ảnh, thì phương pháp nhị phân thông
thường sẽ được thực hiện trước. Mục đích của phương pháp này là sẽ tự động
chọn một ngưỡng cần thiết để tách ảnh ra làm hai phần: thông tin ảnh và thông
tin nền. Việc lựa chọn một ngưỡng tốt (ngưỡng mà có thể phân tách ảnh thành
hai phần: phần ảnh, phần nền một cách chính xác) luôn là một quá trình khó và
dễ gây ra lỗi (0).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
KHOA CÔNG NGHỆ THÔNG TIN
------------ ------------
Nguyễn Thị Hiếu
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
Thái Nguyên, tháng 11 năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
------------ ------------
Nguyễn Thị Hiếu
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
Chuyên ngành: Khoa học máy tính
Mã số: 604801
Ngƣời hƣớng dẫn Khoa học:
PGS.TS Ngô Quốc Tạo
Thái Nguyên, tháng 11 năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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 MỤ C CÁ C HÌNH VẼ --------------------------------------------------------
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2.5. Phân tích đặ c trƣng củ a tà i liệ u ả nh -------------------------------------
15 2.6. Phân tích đố i tƣợ ng văn bả n trong tà i 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ố cụ c củ a trang tà i liệ u ả nh ----------------------------
-- 18 2.7. Nhận dạng ký tự quang học (OCR) ------------------------------------
--- 19 2.7.1. Thuậ t toá n OCR -----------------------------------------------------
20
2.7.1.1. Trích chọn đặc trƣng --------------------------------------- 20
2.7.1.2. Phân loại ------------------------------------------------------ 21
2.7.2. Nhận dạng ký tự dựa trên ngữ cảnh ------------------------------ 21
2.8. 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. Tổ ng quan về phân tá ch văn bả n – ảnh ---------------------------------
24 3.2. Những đặc trƣng chung của một tệp tài liệu ảnh ---------------------
27
3.3. 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 TÀ I LIỆ U Ả NH ----------------------------------------------------------
-- 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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 VÀ MINH HỌ A THUẬ T
TOÁN T-RECS++ ---------------------------------------------------------------------
56
5.1. Mô tả chƣơng trình -------------------------------------------------------
56
5.2. Mộ t số kế t quả -------------------------------------------------------------
58 KẾ T LUẬ N VÀ ĐỀ XUẤ T -----------------------------------------------------
----- 61 THUẬT NGỮ TIẾNG ANH
3–D 3 Dimensions
CAD Computer Aided Design
CAM Computer Aided Manufacturing
CC Chain Code
CCs Connected Components
CPU Control Processing Unit
DP Dynamic Programming
HWRatio Heigh Width Ratio
K – NNR K – Nearest Neighbor Rule
LC Linear Component
LSD Local Stroke Density
NCCs New Connected Components
NNR Nearest Neighbour Rule
OCR Optical Character Recognition
T-Recs Table Recognition System
WBRatio White Black Ratio
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
WDG White-space Density Graphs
DANH MỤ C CÁ C HÌ NH VẼ
Hình Sơ đồ quá trình xử lý tà i liệ u
2.1
Hình Sơ đồ quá trình phân tích trang tà i liệ u
2.2
Phương pháp nhị phân ảnh. (a) Histogram của ảnh đa cấp xám nguyên
Hình
bản, (b) chọn ngưỡng thấp, (c) chọn ngưỡng hợp lý, (d) chọn ngưỡng
2.3
quá cao.
Hình Ảnh nguyên bản(Vân tay) bên trái và ảnh sau khi làm mảnh bên phải.
2.4
Tài liệu ảnh trước và sau các bước tiền xử lý. Ảnh (a) gốc, ảnh (b) ảnh
Hình
sau khi chuyển về ảnh nhị phân, ảnh (c) ảnh sau khi chỉnh nghiêng, ảnh
2.5
(d) ảnh sau khi lọc nhiễu.
Hình văn bả n bị nghiêng sau khi đượ c qué t qua má y qué t.
2.6
Hình Ví dụ minh họa kết quả phân tích bố cục của trang tài liệu ảnh
2.7
Hình Chữ viế t tay có thể gây nhầ m lẫ n
2.8
Hình Ví dụ về các đối tượng văn bản và đối tượng ảnh
3.1
Hình Biểu diễn các điểm ảnh giao nhau
3.2
Hình Một số trường hợp ngoại lệ
3.3
Hình Sơ đồ thuậ t toá n phân tá ch văn bả n
3.4
Hình Hình 3.5 Nhậ n dạ ng đườ ng kẻ nghiêng vớ i phé p toá n ké o da ̃n
3.5
Hình Ví dụ minh họa tư tưởng của thuật toán khởi tạo
4.1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình thuật khở i tạ o đố i vớ i mộ t đoạ n văn bả n
4.2
Hình Trường hợp thuật toán nhận dạng sai cột
4.3
Hình Trường hợp giữa các dòng của một cột trong bảng có ô trắng
4.4
Hình Mô phỏng việc thực hiện các bước đã cải tiến của thuật toán
4.5
Hình Quá trình phân đoạn các cột của bảng
4.7
Hình Trường hợp một ô của bảng chiếm nhiều dòng
4.8
Hình Những mặt hạn chế của thuật toán
4.9
Hinh Trộn hai khối bị phân tách
4.10
Hình Tách các cột bị trộn
4.11
Hình Trộ n lạ i cá c khố i con bị tá ch
4.12
Hình Tách các khối loại 1 thành các ô của bảng
4.14
Hình Tách các khối loại 2 thành các hàng trong bảng
4.15
Hình Giao diệ n chương trình T-Recs
5.1
Hình Nhậ n dạ ng khố i văn bả n vớ i T-Recc++
5.2
Hình Nhậ n dạ ng tà i liệ u ả nh là bả ng quy chế vớ i T-Recs++
5.3
Lêi c¶m ¬n
Trong quá trình 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 Việ t Nam, luậ n văn củ a tôi đã đượ c hoà n thà nh . Mặ c dù
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
đã 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 vẫn còn nhiều hạn chế nên luận vă n khó tránh khỏi
những thiếu sót trong quá trình là m luậ n văn .
Để hoà n thà nh đượ c 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 giú p đỡ em trong suố t
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 Việ n Công
nghệ Thông tin – Việ n khoa họ c Việ t N am đã giả ng dạ y và hướ ng dẫ n
em trong suố t 2 năm học qua. Em cũ ng xin cả m ơn ban lã nh đạ o khoa và
toà n thể thầ y cô giá o trong khoa Công Nghệ thông tin – Đạ i Họ c Thá i
Nguyên đã tạ o điề u kiệ n tố t nhấ t giú p em họ c tậ p và hoà n thà nh luậ n
văn nà y . Và cuối cùng tôi cũng xin cảm ơn gia đình , các bạn trong nhóm
luậ n văn và toà n thể cá c họ c viên lớ p Cao họ c K 6 đã độ ng viên , quan
tâm và giú p đỡ tôi trong thơ ì gian qua.
Cuố i cù ng tôi rấ t mong nhậ n đượ c sự chỉ dẫ n , góp ý của các thầy
cô và các bạn để luận văn của tôi được hoàn thiện hơn .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
CHƢƠNG 1: MỞ ĐẦU
Nhận dạng và xử lý ảnh là một lĩnh vực mang tính khoa học và công
nghệ. Ở Việt Nam Nhận dạng và xử lý ảnh là một ngành khoa học mới mẻ so
với nhiều ngành khoa học khác nhưng tốc độ phát triển của nó rất nhanh. Sự ra
đời của nó đã tạo ra các kỹ thuật quan trọng ảnh hưởng trực tiếp đến các lĩnh
vực như: Tivi, truyền thông, kỹ xảo đồ hoạ…
Cùng với sự phát triể n đó có nhữ ng nhu cầ u thự c tế đặ t ra thách
thức các nhà khoa học máy tính càng nhiều . Nhữ ng công việ c , nhữ ng bà i
toá n đượ c xử lý theo lố i cổ truyề n không theo kịp tố c độ phá t triể n cu ̉a
công nghệ ngày nay. Một trong nhữ ng bà i toá n đó chính là các tài liệu đươ ̣c
lưu trữ trên các chất liệu cổ truyền như giấ y, gỗ , vải vớ i khố i lượ ng khổ ng
lồ , chứ a đự ng rấ t nhiề u tri thứ c củ a nhân loạ i nhưng lạ i không có độ bề n
vĩnh cử u , khó xử lý và lưu trữ . Mộ t bà i toá n khá c là ngà y nay công việ c
văn phò ng liên quan nhiề u đế n cá c tà i liệ u không đơn thuầ n là tà i liệ u
chữ mà tà i liệ u có nhiề u thành phần như bảng biểu , ảnh. Tấ t cả cá c tà i liệ u
đó nế u tiế p tụ c lưu trữ theo phương phá p cổ truyề n thì rấ t phứ c tạ p và khó
xử lý . Vậ y là m thế nà o để chuyể n đổ i nhữ ng kho tà ng tri thứ c trên và o
má y tính để lưu trữ , xử lý dễ dàng, thuậ n tiên và nhanh gọ n . Mộ t lĩnh
vự c của khoa học nhân da ̣ng là Phân tích tài liệu ảnh đã ra đờ i nhằ m biể u
diễ n thông tin trong cá c tà i liệ u ả nh dướ i dạng có cấu trúc.
Hệ phân tích và nhận dạng tài liệu ảnh có mục đích là chuyển đổi tự động
những thông tin lưu trữ trong tài liệu giấy thành biểu diễn dưới dạng những cấu
trúc mà có thể truy xuất, thay đổi được bằng máy tính. Quy trình xử lý của một
hệ phân tích tài liệu bắt đầu bằng việc lấy dữ liệu, các tài liệu từ giấy in sẽ được
quét qua máy quét để lưu trữ trong máy tính dưới dạng các tệp dữ liệu ảnh.
Một tài liệu ảnh là một cách biểu diễn trực quan của các trang tài liệu
được in như một bài tạp chí, một lá thư, một trang báo, một mẩu thư hay một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
bản vẽ kỹ thuật, .v.v.. Một tài liệu ảnh có thể bao gồm các chuỗi ký tự, các hình
vẽ, các bức ảnh, .v.v.. Bên cạnh việc chuyển toàn bộ nội dung của tài liệu sang
tài liệu điện tử cũng cần phải bảo toàn cấu trúc và định dạng của tài liệu. Mục
tiêu cơ bản của một hệ phân tích tài liệu ảnh hoàn chỉnh đó là chuyển một tài
liệu lưu trữ bằng giấy sang dạng biểu diễn có thứ tự cấu trúc và nội dung của
nó. Tài liệu được chuyển sang phải có khả năng thay đổi, soạn thảo và lưu trữ
bởi vì nội dung của tài liệu có thể truy cập bởi cấu trúc của nó thay vì phải truy
cập dưới dạng những mẫu ảnh. Có một số lượng lớn ứng dụng của hệ phân tích
tài liệu ảnh được ứng dụng trong các lĩnh vực như: dịch vụ bưu chính, Chính
phủ, chăm sóc y tế, thư viện, ...v.v.
Mục đích của luận văn là nghiên cứ u kỹ thuậ t nhậ n dạ ng bả ng và trích
chọn ra đối tượng của tài liệu ảnh. Kỹ thuật “Phân tích bảng – T-Recs” là
nghiên cứ u chính .
Với tư tưởng chính của “Phương pháp phân tích bả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 cấu trúc bảng. Thay
vào đó phương pháp sẽ tập trung vào việc 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). Phương pháp 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
bottom - up.
1.1. Cơ sở nghiên cứu và mục đích của luận văn
Ảnh là một đối tượng khá phức tạp về đường nét, dung lượng điểm ảnh, độ sáng
tối, môi trường để thu nhận ảnh phong phú kéo theo nhiễu. Trong nhiều khâu
phân tích ảnh ngoài việc đơn giản hoá các phương pháp toán học đảm bảo tiện
lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử ảnh theo
cách của con người. Trong các bước xử lý đó nhiều khâu hiện nay đã xử lý theo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
các phương pháp trí tuệ của con người. 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. 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 đó.
Nhận dạng bảng là bài toán nhận dạng ra cấu trúc bảng có trong trang tài
liệu ảnh, bao gồm việc nhận dạng các cột, các dòng và các ô có chứa dữ liệu
trong bảng. Nhận dạng đối tượng ảnh là bài toán nhằm phân tách các đối tượng
ảnh trong những trang tài liệu ảnh có chứa hỗn hợp các đối tượng là chuỗi ký tự
và các đối tượng ảnh như: các sơ đồ, hình vẽ, bức ảnh …v.v.
Mặc dù đã có nhiều kỹ thuật trong hệ thống nhận dạng cấu trúc. Tuy nhiên
những nghiên cứu trên những vấn đề đó vẫn còn tiếp tục phát triển bởi vì chất
lượng, độ chính xác, tính hiệu quả của những phương pháp được công bố trước
đây vẫn còn chưa hoàn chỉnh và cần phải cải tiến chúng. Luận văn này trình bày
kỹ thuật nhận dạng cấu trúc bảng bên trong tài liệu ảnh T-Recs và đề xuất một
số phương pháp khắc phục hạn chế thuật toán T-Recs để hoàn thiện hiện hơn
phương pháp phân tích bảng.
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Chương 2 Tổ ng quan về hệ phân tích tà i liệ u ả nh và cá c thà nh phâ ̀n
chính trong hệ phân tích tà i liệ u ả nh : Lấ y dữ liệ u , xử lý ả nh , trích chọn
đặc trưng, nhậ n dạ ng đố i tượ ng ả nh và nhậ n dạ ng văn bả n .
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.
CHƢƠNG 2: TỔNG QUAN VỀ HỆ PHÂN TÍ CH TÀ I LIỆ U Ả NH
2.1. Tài liệu ảnh
Hình ảnh của một đối tượng là sự sao chụp lại chính bản thân đối tượng
đó. Ảnh được hình thành qua một hệ thống ảnh.
Tài liệu ảnh là các file ảnh đã được số hóa thu được bằng cách: quét các
trang tài liệu, chụp ảnh, máy fax, hoặc từ vệ tinh, các file ảnh này được lưu trữ
trong máy tính. Ảnh tài liệu có nhiều loại: đen trắng, ảnh màu, ảnh đa cấp
xám,…v.v.
2.2. Hệ phân tích trang tà i liệ u
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
Hệ phân tích trang tà i liệ u : Là một hệ thống bao gồm những thuật toán và
các k ỹ thuật có thể áp dụng cho các tài liệu ảnh để lấy ra được các thông tin mà
máy tính có thể đọc được và hiểu được từ các điểm dữ liệu ảnh.
Một lĩnh vực thu được nhiều thành công nhất trong phân tích tài liệu ảnh đó là
Nhận dạng Ký tự Quang học (OCR), phần mềm có khả năng nhận, chuyể n đổ i
cá c ký tự từ các loại tài liệu dưới dạng ảnh sang tà i liệ u dướ i dạ ng text . OCR
giúp người dùng có khả năng soạn thảo và tìm kiếm nội dung của tài liệu.
Thành phần chính có trong một hệ phân tích tài liệu: Mục đích của một
hệ phân tích tài liệu là có khả năng nhận dạng ra các đối tượng văn bản, đối
tượng ảnh trong tài liệu ảnh và có khả năng trích chọn ra được các thông tin mà
người dùng mong muốn. Chúng ta có thể chia một hệ phân tích tài liệu thành
hai phần. Phần thứ nhất là xử lý văn bản, liên quan đến việc xử lý các đối tượng
văn bản: ký tự, chuỗi ký tự, các từ. Xử lý văn bản bao gồm các công việc sau:
xác định độ nghiêng của tài liệu (độ nghiêng hay độ xiên của tài liệu ảnh do tài
liệu được đặt không đúng khi thực hiện quét vào từ máy quét), tìm các cột, các
đoạn văn bản, các dòng văn bản, các từ và cuối cùng là nhận dạng văn bản (có
thể thêm các thuộc tính như loại phông chữ, kích thước của phông chữ) bởi
phương pháp nhận dạng ký tự quang học (OCR).
Phần thứ hai là xử lý các đối tượng ảnh là các đối tượng tạo ra từ các đường kẻ
trong sơ đồ, các đường kẻ phân tách giữa các đoạn văn bản, các hình vẽ, các
lôgô của công ty… Sau khi áp dụng các kỹ thuật phân tích ảnh và văn bản, các
đối tượng cần nhận dạng trong tài liệu ảnh được trích ra và được biểu diễn dưới
dạng một tài liệu định dạng khác, chẳng hạn như word, html… Ta có thể tóm tắt
quá trình xử lý của hệ phân tích tài liệu theo sơ đồ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
Hình 2.1 [8]:
Xử lý tài liệu
Xử lý văn bản Xử lý đối tượng
ảnh
Nhận dạng Phân tích Xử lý Xử lý vùng
ký tự quang câu truc đường và ký tự đặc
học trang kẻ biêt
Xác định độ nghiêng, Vùng được tô
Văn bản
dòng văn bản, các khối Đường thẳng,
cong,
đường
văn bản, các đoạn văn góc
Hình 2.1 Sơ đồ quá trình xử lý tà i liệ u
Tại sao lại phải phân tích tài liệu ? Nhữ ng bà i toá n trong phầ n giớ i
thiệ u đã đề cậ p , ta hã y xem xé t kỹ hơn về bà i toá n điể n hình để thấ y đượ c
sự cầ n thiế t củ a việ c phân tích tà i liệ u .
- Lượ ng tri thứ c vô giá củ a nhân loạ i vớ i số lượ ng lớ n đươ ̣c
lưu trữ
trong cá c thư việ n cổ điể n dướ i cá c chấ t liệ u như giấ y , vải, gỗ vẫ n cò n tồ
n tạ i rấ t nhiề u, việ c cá c tà i liệ u bị mất các thông tin , thiếu thông tin, số lượng
bản sao hạn chế hay thậm chí các tài liệu bị thoái hoá theo thời gian là những vấn
đề phổ biến. Vì vậy chúng cần phải được khôi phục và chỉnh sửa bằmg những kỹ
thuật phân tích tài liệu.
- Ngày nay các văn phòng hiện đại các công việc đều được giải
quyết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
dự a và o má y tính . Các tài liệu văn bản với nhiều đối tượng (chữ , hình ảnh ,
các sơ đồ) đượ c tạ o ra trên nhiề u m áy tính khác nhau , phầ n mề m kha ́c nhau
do đó có thể là cá c định dạ ng củ a cá c tà i liệ u đó là không tương thích vớ i
nhau, kích thước cũng khác nhau . Như vậ y cầ n mộ t hệ phân tích tà i liệ u giúp
nhận dạng các loại tài liệu, trích chọn ra được các phần chức năng và có thể
chuyển từ một định dạng máy tính này sang một định dạng khác.
- Mộ t bài toán khác đượ c đề cậ p là các máy phân loại thư tự
động dùng để phân loại, sắp xếp thư và nhận dạng địa chỉ thư. Những máy
này đã có từ những thập kỷ trước, nhưng ngày nay yêu cầu cao hơn đó là
xử lý nhiều thư hơn, nhanh hơn và yêu cầu chính độ xác cao hơn.
Những bài toán trên đã tạo ra thách thức và động lực cho sự phát triển
những giải pháp trong tương lai của một hệ phân tích tài liệu.
Hình 2.2 mô tả cá c bướ c xử lý cho mộ t hệ phân tích tà i liệ u [8]. Sau
khi dữ liệ u (tài liệu ảnh ) đượ c đưa và o , tài liệu ảnh trải qua các bước xử lý
điểm ảnh và phân tích đặc trưng và sau đó phần nhận dạng văn bản và phầ n nhậ
n dạ ng ảnh đượ c tá ch ra hai chứ c năng riêng rẽ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
Trang tai liêu
Thu nhân dư liêu
Xư ly điêm anh
Phân tich đăc trưng
Phân tích và nhận Phân tích và nhận
dạng đối tượng văn dạng đối tượng ảnh
Mô tai liêu
Hình 2.2 Sơ đồ quá trình phân tích trang tà i liệ u
Các hệ phân tích tài liệu sẽ ngày càng phát triển và hiển nhiên là chúng sẽ
có trong các hệ xử lý tài liệu. Chẳng hạn như, hệ thống OCR sẽ
được sử dụng rộng rãi để lưu trữ, tìm kiếm và trích dẫn từ các tài liệu lưu trữ
trên giấy. Các kỹ thuật phân tích cách bố trí trong một trang tài liệu giúp nhận
dạng những biểu mẫu (form) riêng biệt, hay định dạng của một trang tài liệu và
cho phép sao lưu tài liệu đó. Các sơ đồ có thể được đưa vào từ các bức ảnh hay
vẽ bằng tay và có thể thay đổi, soạn thảo lại chúng. Sử dụng máy tính có thể
chuyển các tài liệu viết bằng tay thành các tài liệu điện tử được lưu trữ trong
máy tính. Các tài liệu được lưu trữ trong các thư viện, các tài liệu kỹ thuật trong
các công ty sẽ được chuyển đổi sang thành tài liệu điện tử nhằm nâng cao hiệu
quả, thuận tiện trong việc lưu trữ và dễ dàng mang đến cơ quan hay mang về
nhà. Mặc dù tài liệu sẽ ngày càng được xử lý và lưu trữ nhiều trong máy tính
nhưng trên thực tế có rất nhiều các hệ thống khác nhau mà tài liệu giấy là phương
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
tiện làm việc hiệu quả và chắc chắn rằng tài liệu giấy vẫn sẽ là phương tiện làm
việc với chúng ta trong một vài thập kỷ nữa. Vấn đề ở đây là làm sao chúng ta
tích hợp những tài liệu giấy vào trong máy tính xử lý.
Sau đây ta sẽ tìm hiểu ngắn gọn các bước xử lý của một hệ phân tích
tài liệu ảnh.
2.3. Thu nhậ n dƣ̃ liệ u ảnh
Các dữ liệu trên các trang tài liệu giấy thường được quét qua máy quét và
đưa vào máy tính dưới dạng file ảnh , chúng bao gồm các điểm ảnh (pixels) và
đượ c lưu trữ . Vớ i ả nh nhị phân g iá trị điểm ảnh có thể là 0 hoặ c 1 ,vớ i ảnh
đa cấp xám và ảnh màu giá trị điể m ả nh nằ m trong khoả ng 0 đến 255 với 3
giá trị R, G, B từ 0 đến 255. Ở độ phân giải thông thường thì có 120 điểm ảnh
trên 1 centimet và với 1 trang có kích thước 20 x 30 cm thì tạo ra một ảnh với
2400 x 3600 điểm ảnh. Do đó có thể thấy rằng một tài liệu ảnh chỉ bao bồ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.
2.4. Tiề n xử lý điểm ảnh
Bước tiếp theo trong một hệ phân tích tài liệu là thực hiện một số thao
tác xử lý trên tài liệu ảnh thu được để chuẩn bị cho những bước phân tích tiế p
theo. Chẳng hạn như các thao tác: chọn ngưỡng để chuyển ảnh đa cấp xám, ảnh
màu về dạng ảnh nhị phân, giảm nhiễu để loại bỏ những dữ liệu không liên quan,
phân đoạn để phân tách các thành phần khác nhau trong ảnh và cuối cùng là làm
mảnh hay dò biên để dễ dàng xác định các vùng, các đặc trưng thích hợp và các
đối tượng cần quan tâm. Sau những bước xử lý ở trên, dữ liệu thường được biểu
diễn dưới dạng nén lại như dùng mã hoá CC và biểu diễn dưới dạng véctơ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
2.4.1. Xƣ̉ lý nhị phân
Với những ảnh đa cấp xám các thông tin đã sẵ n ở dạng nhị phân chẳng hạn như
các chuỗi văn bản hay các đối tượng ảnh, thì phương pháp nhị phân thông
thường sẽ được thực hiện trước. Mục đích của phương pháp này là sẽ tự động
chọn một ngưỡng cần thiết để tách ảnh ra làm hai phần: thông tin ảnh và thông
tin nền. Việc lựa chọn một ngưỡng tốt (ngưỡng mà có thể phân tách ảnh thành
hai phần: phần ảnh, phần nền một cách chính xác) luôn là một quá trình khó và
dễ gây ra lỗi (0).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn