..
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
------------
BÙI THỊ THI
PHÁT HIỆN CẤU TRÚC BẢNG TRONG
NHẬN DẠNG VĂN BẢN
Chuyên ngành : Khoa học máy tính
Mã số
: 60.48.01
Luận văn thạc sĩ khoa học máy tính
Ngƣời hƣớng dẫn khoa học:
TS. Nguyễn Đức Dũng
Thái Nguyên, 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
http://www.lrc-tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
http://www.lrc-tnu.edu.vn
LỜI CẢM ƠN ..................................................................................................6
DANH SÁCH CÁC HÌNH ẢNH.....................................................................7
MỞ ĐẦU ..........................................................................................................8
CHƢƠNG 1 ...................................................................................................10
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH ....10
1.1. Tổng quan về xử lý ảnh .......................................................................10
1.1.1. Xử lý ảnh ......................................................................................10
1.1.2. Các bƣớc cơ bản trong xử lý ảnh ..................................................10
1.1.2.1. Thu nhận ảnh..........................................................................11
1.1.2.2. Tiền xử lý ...............................................................................11
1.1.2.3. Phân đoạn ảnh ........................................................................12
1.1.2.4. Biểu diễn và mô tả .................................................................13
1.1.2.5. Nhận dạng và nội suy ảnh ......................................................14
1.1.2.6. Cơ sở tri thức .........................................................................14
1.1.2.7. Trích chọn đặc điểm...............................................................15
1.2. Hệ phân tích tài liệu ảnh ......................................................................15
1.2.1. Tài liệu ảnh ...................................................................................15
1.2.2. Hệ phân tích trang tài liệu ảnh ......................................................16
1.2.3. Các bƣớc xử lý của một hệ phân tích tài liệu ảnh ........................17
1.2.3.1. Thu nhận dữ liệu ảnh .............................................................18
1.2.3.2. Tiền xử lý điểm ảnh ...............................................................18
1.2.3.2.1. Xử lý nhị phân ....................................................................18
1.2.3.2.2. Khử nhiễu ............................................................................19
1.2.3.3. Phân đoạn ảnh ........................................................................20
1.2.3.4. Làm mảnh và xác định vùng ..................................................20
1.2.3.5. Mã hóa Chain Code và vector hóa .........................................21
1.2.4. Phân tích đặc trƣng của tài liệu ảnh ..............................................22
1.2.5. Phân tích đối tƣợng văn bản trong tài liệu ảnh .............................23
1.2.5.1. Xác định góc nghiêng của văn bản ........................................23
1.2.5.2. Phân tích bố cục của trang tài liệu ảnh .................................25
CHƢƠNG 2 ...................................................................................................27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
http://www.lrc-tnu.edu.vn
PHƢƠNG PHÁP PHÁT HIỆN BẢNG TESSERACT, PHÂN TÍCH BẢNG
T-RECS TRONG TRANG ẢNH TÀI LIỆU .................................................27
2.1. Phƣơng pháp phát hiện bảng T-Recs trong trang ảnh tài liệu .............27
2.1.2. Phân tích cấu trúc văn bản thông qua phát hiện TAB-STOP ...........29
2.1.3. Phƣơng pháp phát hiện bảng Tesseract ............................................31
Thuật toán phát hiện bảng đƣợc xây dựng với hai thành phần của mô đun
phân tích cấu trúc sau: ................................................................................31
2.1.3.1. Xác định các phần của bảng ......................................................32
2.1.3.2. Xác định các trang cột phân tách ...............................................34
2.1.3.3 Xác định các cột bảng .................................................................34
2.1.3.4. Đánh dấu các vùng bảng ............................................................34
2.1.3.5. Loại bỏ các lỗi ...........................................................................35
2.2. Phƣơng pháp phân tích bảng T-Recs ......................................................35
2.2.1. Giới thiệu ...........................................................................................35
2.2.2. Thuật toán phân đoạn khởi tạo .........................................................37
CHƢƠNG 3 ...................................................................................................39
CÀI ĐẶT THỬ NGHIỆM VÀ ĐÁNH GIÁ..................................................39
3.1. Môi trƣờng cài đặt và dữ liệu kiểm thử ...............................................39
3.2. Trình tự thực hiện của thuật toán ........................................................39
3.3. Kết quả thực nghiệm ...........................................................................39
3.4. Đánh giá ..............................................................................................45
KẾT LUẬN ....................................................................................................51
TÀI LIỆU THAM KHẢO..............................................................................52
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
http://www.lrc-tnu.edu.vn
LỜI CẢM ƠN
Trƣớc hết em muốn đƣợc gửi lời cảm ơn đến các thầy, cô giáo ở Viện
Công nghệ thông tin, trƣờng ĐH Công nghệ Thông tin và Truyền thông… đã
quan tâm tổ chức chỉ đạo, quản lý lớp, trực tiếp giảng dạy khóa học của
chúng em.
Em xin đƣợc bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS. Nguyễn
Đức Dũng – Viện Công nghệ Thông tin – Viện Khoa học Việt Nam, ngƣời
thầy đã tận tình giúp đỡ, chỉ bảo em trong suốt quá trình tìm hiểu, viết đề
cƣơng và phát triển luận văn. Em xin đƣợc cảm ơn thầy giáo Lê Đức Hiếu –
Viện Công nghệ Thông tin – Viện Khoa học Việt Nam ngƣời thầy đã tận tình
giúp đỡ, chỉ bảo em trong suốt quá trình phát triển phần cài đặt, thử nghiệm.
Mặc dù đã có cố gắng song khả năng của bản thân em còn rất nhiều
hạn chế nên luận văn không tránh khỏi những thiếu sót. Em rất mong chỉ
bảo, góp ý của các thầy cô giáo và các bạn để luận văn của em đƣợ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
6
http://www.lrc-tnu.edu.vn
DANH SÁCH CÁC HÌNH ẢNH
Hình 1.1
Quá trình xử lý ảnh
Hình 1.2
Các bước cơ bản trong quá trình xử lý ảnh
Hình 1.3
Lân cận các điểm ảnh của tọa độ (x, y)
Hình 1.4
Văn bản bị nghiêng sau khi được quét qua máy quét
Hình 2.1
Kết quả đầu ra của các bước khác nhau của các mô-đun phân tích
trí trong tài liệu ảnh
Hình 2.2
Kết qủa của các bước khác nhau trong việc phân tích bố trí của c
vùng bảng của Tesseract’s
Hình 2.3
Kết quả của các bước khác nhau trong thuật toán phát hiện bảng
Hình 2.4
Ví dụ minh họa tư tưởng của thuật toán khởi tạo
Hình 2.5
Thuật toán khởi tạo đối với một đoạn văn bản
Hình 3.1
Phát hiện một phần
Hình 3.2
Chia nhỏ bảng
Hình 3.3
Gộp bảng với vùng văn bản
Hình 3.4
Phát hiện sai
Hình 3.5
Kết quả thực nghiệm 1
Hình 3.6
Kết quả thực nghiệm 2
Hình 3.7
Kết quả thực nghiệm 3
Hình 3.8
Kết quả thực nghiệm 4
Hình 3.9
Kết quả thực nghiệm 5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
http://www.lrc-tnu.edu.vn
MỞ ĐẦU
Xử lý ảnh là một trong những chuyên ngành quan trọng và lâu đời của
Công nghệ thông tin. Xử lý ảnh đƣợc áp dụng trong nhiều lĩnh khác nhau
nhƣ y học, vật lý, hoá học, tìm kiếm tội phạm, trong quân sự và trong một số
lĩnh vực khác....
Phần lớn con ngƣời thu nhận thông tin bằng thị giác, cụ thể đó là các
hình ảnh. Vì vậy xử lý ảnh là vấn đề không thể thiếu và hết sức quan trọng
để thu đƣợc hình ảnh tốt hơn, đẹp hơn, nhằm đáp ứng yêu cầu thông tin khác
nhau của ngƣời nhận.
Một trong những lĩnh vực của xử lý ảnh đó là xử lý, nhận dạng thông
tin chứa đựng trong các tài liệu ảnh, tài liệu ảnh đa dạng, phức tạp không đơn
thuần là các ký tự văn bản, hình vẽ, hình ảnh, bảng biểu…Trong đó phát hiện
các bảng trong các tài liệu hình ảnh là một khâu rất quan trọng vì không
những chúng ta phải xác định các thông tin chứa trong các bảng mà hầu hết
các phƣơng pháp hiện nay đều gặp khó khăn trong việc nhận diện các bảng.
Các phƣơng pháp phát hiện các bảng hiện nay tập trung chủ yếu vào các
bảng chỉ có một cột mà nó không làm việc tốt với các bảng có nhiều dạng
khác nhau.
Xuất phát từ thực tế đó, luận văn lựa chọn đề tài “Phát hiện cấu trúc
bảng trong nhận dạng văn bản”. Mục đích chính của đề tài là tìm hiểu các
phƣơng pháp phát hiện cấu trúc bảng, trình bày, cài đặt một thuật toán phát
hiện các bảng với độ chính xác cao áp dụng cho các dạng tài liệu phức tạp
nhƣ: các báo cáo của các công ty, các bài báo, các trang tạp chí,…
Ngoài phần mở đầu, kết luận luận văn đƣợc chia làm 3 chƣơng cụ thể
nhƣ sau:
Chƣơng 1: Tổng quan về xử lý ảnh và hệ phân tích tài liệu ảnh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
http://www.lrc-tnu.edu.vn
Trong chƣơng này trình bày sơ lƣợc về xử lý ảnh, giới thiệu các bƣớc
xử lý trong một hệ thống xử lý ảnh, 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 2: Phƣơng pháp phát hiện bảng Tesseract, phân tích bảng TRecs trong trang tài liệu ảnh
Trình bày các phƣơng pháp phát hiện bảng, thuật toán phát hiện cấu
trúc bảng. Minh họa phát hiện cấu trúc bảng trong trang ảnh tài liệu.
Tìm hiểu về thuật toán T-Recs do Thomas G.Kieninger [7] đề xuất.
Chƣơng 3: Cài đặt thử nghiệm và đánh giá
Mô tả chi tiết quá trình cài đặt thử nghiệm thuật toán, cũng nhƣ đánh
giá các kết quả đạt đƣợc trên bộ dữ liệu thu thập đƣợc.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
http://www.lrc-tnu.edu.vn
CHƢƠNG 1
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ HỆ PHÂN TÍCH TÀI LIỆU ẢNH
1.1. Tổng quan về xử lý ảnh
1.1.1. Xử lý ảnh
Quá trình xử lý nhận dạng ảnh là một quá trình thao tác nhằm biến đổi
một ảnh đầu vào để cho ra một kết quả mong muốn. Kết quả đầu ra của một
quá trình xử lý ảnh có thể là một ảnh "tốt hơn" hoặc một kết luận[1].
Ảnh “Tốt hơn”
Ảnh
Xử lý ảnh
Kết luận
Hình 1.1: Quá trình xử lý ảnh
Nhƣ vậy mục tiêu của xử lý ảnh có thể chia làm ba hƣớng nhƣ sau:
- Xử lý ảnh ban đầu để cho ra một ảnh mới tốt hơn theo một mong
muốn của ngƣời dùng (ví dụ: ảnh mờ cần xử lý để đƣợc rõ hơn).
- Phân tích ảnh để thu đƣợc thông tin nào đó giúp cho việc phân loại
và nhận biết ảnh (ví dụ: phân tích ảnh vân tay để trích chọn các đặc trƣng
vân tay).
- Từ ảnh đầu vào mà có những nhận xét, kết luận ở mức cao hơn, sâu
hơn (ví dụ: ảnh một tai nạn giao thông phác họa hiện trƣờng tai nạn).
1.1.2. Các bƣớc cơ bản trong xử lý ảnh
Quá trình xử lý một ảnh đầu vào nhằm thu đƣợc một ảnh đầu ra mong
muốn thƣờng phải trải qua rất nhiều bƣớc khác nhau [2]. Các bƣớc cơ bản
của một quá trình xử lý ảnh đƣợc thể hiện thông qua hình sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
http://www.lrc-tnu.edu.vn
Biểu diễn
và mô tả
Phân
đoạn ảnh
Tiền xử lý
ảnh
CƠ SỞ
TRI THỨC
Nhận dạng
và nội suy
Thu nhận ảnh
(Scanner,
sensor, camera)
Hình 1.2: Các bước cơ bản trong quá trình xử lý ảnh
1.1.2.1. Thu nhận ảnh
Đây là bƣớc đầu tiên trong quá trình xử lý ảnh. Để thực hiện điều này,
ta cần có bộ thu ảnh và khả năng số hoá những tín hiệu liên tục đƣợc sinh ra
bởi bộ thu ảnh đó. Bộ thu ảnh ở đây có thể là máy chụp ảnh đơn sắc hay
màu, máy quét ảnh, máy quay... Trong trƣờng hợp bộ thu ảnh cung cấp chƣa
phải là dạng số hoá ta còn phải chuyển đổi hay số hoá ảnh. Quá trình chuyển
đổi ADC (Analog to Digital Converter) để thu nhận dạng số hoá của ảnh.
Mặc dù đây chỉ là công đoạn đầu tiên song kết quả của nó có ảnh hƣởng rất
nhiều đến công đoạn kế tiếp.
1.1.2.2. Tiền xử lý
Ở bƣớc này, ảnh sẽ đƣợc cải thiện về độ tƣơng phản, khử nhiễu, khôi
phục ảnh, nắn chỉnh hỉnh học... Với mục đích làm cho chất lƣợng ảnh trở lên
tốt hơn nữa, chuẩn bị cho các bƣớc xử lý phức tạp kế tiếp sau đó.
* Khử nhiễu: Đặc trƣng của nhiễu hệ thống là tính tuần hoàn. Do
vậy, có thể khử nhiễu này bằng việc sử dụng phép biến đổi Fourier và loại bỏ
các đỉnh điểm. Đối với nhiễu ngẫu nhiên, trƣờng hợp đơn giản là các vết bẩn
tƣơng ứng với các điểm sáng hay tối, có thể khử bằng phƣơng pháp nội suy,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
http://www.lrc-tnu.edu.vn
lọc trung vị và trung bình.
* Chỉnh mức xám: Đây là kỹ thuật nhằm chỉnh sửa tính không đồng
đều của thiết bị thu nhận hoặc độ tƣơng phản giữa các vùng ảnh.
* Chỉnh tán xạ: Ảnh thu nhận đƣợc từ các thiết bị quang học hay
điện tử có thể bị mờ, nhoè. Phƣơng pháp biến đổi Fourier dựa trên tích chập
của ảnh với hàm tán xạ cho phép giải quyết việc hiệu chỉnh này.
* Nắn chỉnh hình học: Những biến dạng hình học thƣờng do các
thiết bị điện tử và quang học gây ra. Do đó, phƣơng pháp hiệu chỉnh ảnh dựa
trên mô hình đƣợc mô tả dƣới dạng phƣơng trình biến đổi ảnh biến dạng
f(x,y) thành ảnh lý tƣởng f(x',y') nhƣ sau:
x' hx ( x, y)
y' h y x, y
Trong đó hx, hy là các phƣơng trình tuyến tính (biến dạng do phối
cảnh) hay bậc hai (biến dạng do ống kính camera).
1.1.2.3. Phân đoạn ảnh
Phân đoạn ảnh là một thao tác ở mức thấp trong toàn bộ quá trình xử
lý ảnh. Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và
đồng nhất với nhau hay nói cách khác là xác định các biên của các vùng ảnh
đó. Các vùng ảnh đồng nhất này thông thƣờng sẽ tƣơng ứng với tòan bộ hay
từng phần của các đối tƣợng thật sự bên trong ảnh. Vì thế, trong hầu hết các
ứng dụng của lĩnh vực xử lý ảnh, thị giác máy tính, phân đoạn ảnh luôn đóng
một vai trò cơ bản và thƣờng là bƣớc tiền xử lý đầu tiên trong toàn bộ quá
trình trƣớc khi thực hiện các thao tác khác ở mức cao hơn nhƣ nhận dạng đối
tƣợng, biểu diễn đối tƣợng, nén ảnh dựa trên đối tƣợng, hay truy vấn ảnh dựa
vào nội dung.
Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần
khác nhau hay còn gọi là các đối tƣợng để biểu diễn phân tích, nhận dạng
ảnh. Ví dụ: để nhận dạng chữ (hoặc mã vạch) trên phong bì thƣ cho mục đích
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
http://www.lrc-tnu.edu.vn
phân loại bƣu phẩm, cần chia các câu, chữ về địa chỉ hoặc tên ngƣời thành
các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. Đây là phần
phức tạp khó khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính
xác của ảnh. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này.
Kết quả của bƣớc phân đoạn ảnh thƣờng đƣợc cho dƣới dạng dữ liệu
điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh hoặc tập hợp tất cả
các điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trƣờng hợp, sự
chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý
trong máy tính là hết sức cần thiết, nghĩa là nên biểu diễn một vùng ảnh dƣới
dạng biên hay dƣới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh
thuộc về nó.
- Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ
quan tâm đến các đặc trƣng hình dạng bên ngoài của đối tƣợng, ví dụ nhƣ
các góc cạnh và điểm uốn trên biên.
- Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các
tính chất bên trong của đối tƣợng. Ví dụ nhƣ vân ảnh hoặc cấu trúc xƣơng
của nó. Và trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết.
1.1.2.4. Biểu diễn và mô tả
a) Biểu diễn
Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã
phân đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số
liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính.
Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trƣng gắn với
việc tách các đặc tính của ảnh dƣới dạng các thông tin định lƣợng hoặc làm
cơ sở để phân biệt lớp đối tƣợng này với đối tƣợng khác trong phạm vi ảnh
nhận đƣợc. Ví dụ: trong nhận dạng ký tự trên phong bì thƣ, chúng ta miêu tả
các đặc trƣng của từng ký tự giúp phân biệt ký tự này với ký tự khác.
b) Mô tả
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
http://www.lrc-tnu.edu.vn
Ảnh sau khi số hoá sẽ đƣợc lƣu vào bộ nhớ, hoặc chuyển sang các
khâu tiếp theo để phân tích. Nếu lƣu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi
dung lƣợng bộ nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và
công nghệ. Thông thƣờng, các ảnh thô đó đƣợc đặc tả (biểu diễn) lại (hay
đơn giản là mã hoá) theo các đặc điểm của ảnh đƣợc gọi là các đặc trƣng ảnh
nhƣ: biên ảnh, vùng ảnh.
1.1.2.5. Nhận dạng và nội suy ảnh
Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thƣờng thu
đƣợc bằng cách so sánh với mẫu chuẩn đã đƣợc lọc (hoặc lƣu) từ trƣớc.
Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một
loạt chữ số và nét gạch ngang trên phong bì thƣ có thể đƣợc nội suy thành
mã điện thoại. Có nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về
nhận dạng, các mô hình toán học về ảnh đƣợc phân theo hai loại nhận dạng
ảnh cơ bản:
- Nhận dạng theo tham số.
- Nhận dạng theo cấu trúc.
Một số đối tƣợng nhận dạng khá phổ biến hiện nay đang đƣợc áp
dụng trong khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay,
chữ ký điện tử), nhận dạng văn bản, nhận dạng vân tay, nhận dạng mã vạch,
nhận dạng mặt ngƣời…
1.1.2.6. Cơ sở tri thức
Ảnh là một đối tƣợng khá phức tạp về đƣờng nét, độ sáng tối, dung
lƣợng điểm ảnh, môi trƣờng để thu ảnh phong phú kéo theo nhiễu. Trong
nhiều khâu xử lý và phân tích ảnh ngoài việc đơn giản hóa 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ử lý ả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 các phƣơng pháp trí tuệ con ngƣời. Vì
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
http://www.lrc-tnu.edu.vn
vậy, ở đây các cơ sở tri thức đƣợc phát huy.
1.1.2.7. Trích chọn đặc điểm
Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy
sinh trong cuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn
đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả những
ứng dụng đó là những đặc điểm đặc trƣng cần thiết thƣờng là nhiều, không
thể do chuyên gia đề xuất, mà phải đƣợc trích chọn dựa trên các thủ tục phân
tích dữ liệu.
Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các
đối tƣợng ảnh chính xác, với tốc độ tính toán cao và dung lƣợng nhớ lƣu trữ
giảm xuống.
Các đặc điểm của đối tƣợng đƣợc trích chọn tuỳ theo mục đích nhận
dạng trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau
đây:
- Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ,
điểm uốn v.v..
- Đặc điểm biến đổi: Các đặc điểm loại này đƣợc trích chọn bằng việc
thực hiện lọc vùng. Các bộ vùng đƣợc gọi là “mặt nạ đặc điểm” thƣờng là
các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn ...)
- Đặc điểm biên và đường biên: Đặc trƣng cho đƣờng biên của đối
tƣợng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến đƣợc
dùng khi nhận dạng đối tƣợng. Các đặc điểm này có thể đƣợc trích chọn nhờ
toán tử Gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo không” ...
1.2. Hệ phân tích tài liệu ảnh
1.2.1. Tài liệu ả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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
http://www.lrc-tnu.edu.vn
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,…
1.2.2. Hệ phân tích trang tài liệu ảnh
- Hệ phân tích trang tài liệu ảnh: 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ụ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.
- Một hệ phân tích tài liệu ảnh có thể chia làm 2 phần: xử lý văn bản
và xử lý các đối tƣợng ảnh.
* Xử lý văn bản:
+ Đối tƣợng văn bản: ký tự, chuỗi ký tự, các từ.
+ Các bƣớc xử lý văn bản:
- Xác định độ nghiêng của tài liệu (Độ nghiêng hay độ xiên của tài
liệu ảnh là do khi quét vào từ máy quét ngƣời dùng đặt lệch tài liệu).
- Xác định các cột, các đoạn văn bản, các dòng văn bản, các từ.
- Nhận dạng văn bản.
* Xử lý các đối tƣợng ảnh:
+ Đối tƣợng ảnh: các hình vẽ, các đƣờng kẻ trong sơ đồ, các đƣờng kẻ
phân tách giữa các đoạn văn bản.
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 tách ra và đƣợc biểu diễn dƣới dạng
một tài liệu định dạng khác, ví dụ: 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ơ đồ
hình 1.4 [5]:
Xử lý tài liệu
Xử lý văn bản
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
Xử lý đối tƣợng
http://www.lrc-tnu.edu.vn
1.2.3. Các bƣớc xử lý của một hệ phân tích tài liệu ảnh
Để mô tả các bƣớc xử lý cho một hệ phân tích tài liệu ảnh ta có hình
1.5 [5]. 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, sau đó phần nhận dạng văn bản,
ả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
17
http://www.lrc-tnu.edu.vn
Trang tài liệu
Thu nhận dữ liệu
Xử lý điểm ảnh
Phân tích đặc trƣng
Phân tích và nhận dạng
đối tƣợng văn bản
Phân tích và nhận dạng
đối tƣợng ảnh
Mô tả tài liệu
Hình 1.5 Sơ đồ quá trình phân tích trang tài liệu ảnh
1.2.3.1. Thu nhận dữ liệu ảnh
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, và đƣợc
lƣu trữ.
Ở độ phân giải thông thƣờng thì có 120 điểm ảnh trên 1centimet và
với một trang có kích thƣớc 20×30cm thì tạo ra một ảnh với 2400×3600
điểm ảnh. Do đó có thể thấy rằng một tài liệu ảnh chỉ bao gồm các dữ liệu
thô (giá trị các điểm ảnh) và chúng sẽ đƣợc sử dụng những kỹ thuật phân tích
thích hợp để lấy ra các thông tin cần thiết.
1.2.3.2. Tiền xử lý điểm ảnh
1.2.3.2.1. Xử lý nhị phân
- Mục đích: tự động chọn một ngƣỡng cần thiết để tách ra làm 2 phần:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
http://www.lrc-tnu.edu.vn
thông tin ảnh và thông tin nền. Quá trình xử lý nhị phân sẽ gặp khó khăn
trong các trƣờng hợp khi độ tƣơng phản giữa các giá trị các điểm ảnh văn
bản và nền là thấp (ví dụ nhƣ văn bản đƣợc soạn thảo trên một nền xám
thuần nhất); nét của văn bản mỏng hoặc dữ liệu không đƣợc chiếu sáng tốt
khi thực hiện quét tài liệu giấy. Nhiều phƣơng pháp đã đƣợc phát triển để
khắc phục những hạn chế trên, ví dụ phƣơng pháp tách ngƣỡng tự động để
tìm ra các giá trị thích hợp để chia ảnh thành 2 phần.
1.2.3.2.2. Khử nhiễu
- Nhiễu luôn là một vấn đề trong hầu hết các bài toán đọc hiểu tài liệu.
Nguyên nhân sinh ra nhiễu do quá trình quét tài liệu, quá trình sao chép, sự
thoái hóa của tài liệu theo thời gian.
Các nhiễu làm giảm hoặc nhiều khi làm mất khả năng biểu lộ thông
tin của đối tƣợng chính trong ảnh. Có nhiều loại nhiễu nhƣ nhiễu cộng, nhiễu
nhân, nhiễu xung. Với mỗi loại nhiễu cần có các bộ lọc thích hợp. Với nhiễu
cộng và nhiễu nhân ta dùng các bộ lọc thông thấp, trung bình, và lọc đồng
hình. Sở dĩ nhƣ vậy vì bản chất của nhiễu là thƣờng tƣơng ứng với tần số cao
và cơ sở lý thuyết của các bộ lọc là chỉ cho những tín hiệu nào đó thông qua.
Nhiễu có thể coi nhƣ sự đột biến của một điểm ảnh so với các điểm lân cận.
Trong kỹ thuật lọc, ngƣời ta sử dụng một mặt nạ và di chuyển khắp
ảnh gốc. Tuỳ theo cách tổ hợp điểm đang xét với các điểm lân cận mà ta có
kỹ thuật lọc tuyến tính hay phi tuyến. Điểm ảnh chịu tác động của biến đổi là
điểm ở tâm mặt nạ.
Trong kỹ thuật lọc tuyến tính, ảnh thu đƣợc sẽ là tổng trọng số hay là
trung bình trọng số các điểm lân cận với nhân cuộn hay mặt nạ.
Khác với lọc tuyến tính, kỹ thuật lọc phi tuyến coi một điểm ảnh kết
quả không phải là tổ hợp tuyến tính của các điểm lân cận. Bộ lọc phi tuyến
thƣờng dùng là lọc trung vị
mang tên Tuckey. Với bộ lọc trung vị các điểm ảnh sẽ đƣợc thay thế bởi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
http://www.lrc-tnu.edu.vn
trung vị các điểm ảnh, bộ lọc giả trung vị thì các điểm ảnh đƣợc thay thế bởi
trung bình cộng của hai giá trị “trung vị”.
1.2.3.3. Phân đoạn ảnh
Quá trình phân đoạn ảnh đƣợc thực hiện làm hai giai đoạn. Giai đoạn
thứ nhất, tách các lớp văn bản và ảnh riêng biệt nếu nhƣ trong tài liệu có
chứa cả văn bản và ảnh. Giai đoạn thứ hai là thực hiện phân tách trên hai lớp
đối tƣợng vừa tách ở trên, với văn bản xác định các cột, các đoạn văn bản,
các từ và các kí tự; với lớp đối tƣợng ảnh thực hiện phân tách các biểu tƣợng,
các hình vẽ, các đƣờng kẻ và các hình ảnh. Chẳng hạn nhƣ một tài liệu ảnh
có chứa các đoạn văn bản và các hình minh họa giống nhƣ một trang tạp chí,
đầu tiên văn bản và hình ảnh sẽ đƣợc tách riêng. Sau đó văn bản sẽ đƣợc tách
ra thành các chuỗi kí tự. Ảnh thì đƣợc tách ra các thành phần nhƣ hình chữ
nhật, hình tròn, các đƣờng kẻ, biểu tƣợng .v.v…Sau bƣớc trên tài liệu ảnh sẽ
đƣợc phân tách ra thành những đối tƣợng nhỏ hơn nhƣ các ký tự và các thành
phần cơ bản của ảnh.
1.2.3.4. Làm mảnh và xác định vùng
Thuật toán làm mảnh làm mảnh ảnh số nhị phân là một trong các
thuật toán quan trọng trong xử lý ảnh và nhận dạng. Thuật toán làm mảnh là
quá trình lặp duyệt và kiểm tra tất cả các điểm thuộc đối tƣợng. Trong mỗi
lần lặp tất cả các điểm của đối tƣợng sẽ đƣợc kiểm tra: nếu nhƣ chúng thỏa
mãn điều kiện xóa nào đó tùy thuộc vào mỗi thuật toán thì nó sẽ bị xóa đi.
Quá trình cứ lặp lại cho đến khi không còn điểm biên nào đƣợc xóa. Đối
tƣợng đƣợc bóc dần lớp biên cho đến khi nào bị thu mảnh lại chỉ còn điểm
biên.
Làm mảnh ảnh là một thao tác xử lý ảnh trong đó đối tƣợng ảnh đƣợc
biểu diễn nhƣ là những đƣờng trục đƣợc gọi là đƣờng tâm hay còn gọi là lấy
xƣơng của ảnh. Xƣơng đƣợc coi nhƣ hình dạng cơ bản của một đối tƣợng,
với số ít các điểm ảnh cơ bản. Ta có thể lấy đƣợc các thông tin về hình dạng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
http://www.lrc-tnu.edu.vn
nguyên bản của một đối tƣợng thông qua xƣơng. Thuật ngữ “xƣơng” đƣợc sử
dụng để chỉ kết qủa của việc làm mảnh ảnh mà không cần quan tâm đến hình
dạng chuẩn của ảnh ban đầu hoặc các phƣơng thức sử dụng để làm mảnh.
Xƣơng chứa những thông tin bất biến về cấu trúc của ảnh giúp cho quá trình
nhận dạng và vector hóa sau này.
Mục đích của việc làm mảnh ảnh là giảm bớt các thành phần mà chỉ
lƣu trữ các thông tin cần thiết yếu phục vụ cho việc phân tích và nhận dạng
sau này thuận tiện hơn. Chẳng hạn nhƣ một đƣờng kẻ thẳng có thể vẽ bằng
tay với độ đậm của nét bút là khác nhau nhƣng có thể biểu diễn chúng giống
nhau.
Nói chung với các đối tƣợng có kích thƣớc lớn thì sử dụng phƣơng
pháp dò biên là thích hợp để biểu diễn đối tƣợng, còn đối với những đối
tƣợng đƣợc tạo thành bởi nét kết nối dài thì sử dụng phƣơng pháp làm mảnh
là thích hợp hơn. Làm mảnh thƣờng đƣợc sử dụng nhƣ là một quá trình tiền
xử lý đối với những ứng dụng phân tích tài liệu nhƣ xử lý sơ đồ hay bản đồ.
Với những đối tƣợng ảnh lớn mà vùng ảnh đƣợc tô đầy chẳng hạn nhƣ những
logo thì áp dụng phƣơng pháp dò biên là thích hợp hơn. Nhƣng với những
vùng nhỏ chẳng hạn từng ký tự riêng biệt thì khi đó vùng ảnh sẽ đƣợc biểu
diễn dƣới dạng mảng các giá trị của điểm ảnh chứ không áp dụng phƣơng
pháp làm mảnh hay dò biên.
1.2.3.5. Mã hóa Chain Code và vector hóa
Khi một đối tƣợng ảnh đƣợc biểu diễn dƣới dạng xƣơng của ảnh hay
bằng đƣờng viền, chúng có thể biểu diễn một cách hiệu quả hơn là lƣu các
điểm ảnh một cách đơn giản các giá trị ON và OFF. Một trong những
phƣơng pháp lƣu ảnh hiệu quả đó là phƣơng pháp mã xích CC (Chain Code),
trong đó các điểm có giá trị ON đƣợc biểu diễn thông qua tập các điểm láng
giềng đi theo một hƣớng quy định. Thay vì phải lƣu trữ vị trí của điểm ảnh
có giá trị ON chúng ta sẽ lƣu trữ vị trí của điểm ảnh có giá trị ON chúng ta sẽ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
http://www.lrc-tnu.edu.vn
- Xem thêm -