4
CHƯƠNG 1
GIỚI THIỆU TỔNG QUÁT VỀ HỆ PHÂN TÍCH ẢNH TÀI LIỆU
1.1 Tổng quan về hệ phân tích ảnh tài liệu
Ảnh tài liệu sau khi được quét và lưu trữ vào máy tính thì nó được cấu
thành từ những điểm ảnh, nhiệm vụ của chúng ta là phải trích chọn được những
thông tin đặc trưng từ nó sao cho máy tính có thể “đọc” và “hiểu” được các thành
phần này. Để làm được điều này người ta phải áp dụng các thuật toán kết hợp cùng
với những kỹ thuật cả về phần cứng và phần mềm máy tính, sự tích hợp này là yếu
tố chính tạo thành một hệ phân tích ảnh tài liệu. Sau khi tạo được hệ phân tích ảnh,
người ta tiến hành quá trình xử lý ảnh gồm việc thao tác lên ảnh đầu vào để cuối
cùng cho ảnh đầu ra với kết quả đạt được những mục tiêu đã định trước đó. Cụ thể
là kết quả của ảnh đầu ra có thể là một kết luận về sự nhận dạng hoặc là một ảnh đã
được xử lý tốt hơn. Một trong những công nghệ khá phổ biến hiện nay được áp
dụng để nhận dạng văn bản là công nghệ nhận dạng ký tự bằng quang học (Optical
Character Recognition-OCR). Cơ chế chủ yếu của nó là nhận dạng ký tự trên nền
định dạng ảnh tài liệu và chuyển sản phẩm nhận dạng được sang kiểu tập tin văn
bản. Từ đó OCR có thể giúp chúng ta thao tác trên văn bản như tạo, sửa đổi, xóa bỏ,
tìm kiếm, thay thế nội dung của tài liệu.
Như vậy, mục tiêu của hệ phân tích ảnh tài liệu là phát hiện ra được các đối
tượng khác nhau trong một ảnh tài liệu như chữ đánh máy, chữ viết bằng tay, hình
ảnh, văn bản chia thành hàng, cột, v.v. Đồng thời hệ phân tích này còn phải trích
xuất được những thành phần trong ảnh tài liệu mà chúng ta mong muốn để phục vụ
cho những mục đích nghiên cứu và ứng dụng khác nhau. Và đặc biệt trong bài luận
này là trọng tâm nhấn mạnh đến việc phát hiện được bảng biểu (detect table) trong
ảnh tài liệu. Trên cơ sở đặc điểm chung của một ảnh tài liệu thường có chứa hai loại
đối tượng chính là văn bản và hình ảnh cũng như đa số các công nghệ nhận dạng
được áp dụng hiện nay, chúng ta có thể thấy rằng một hệ phân tích ảnh tài liệu thực
hiện hai nhiệm vụ chính (xem hình 1.1). Nhiệm vụ thứ nhất là phải xử lý các đối
tượng hình ảnh được cấu thành từ hình vẽ, đường kẻ, dấu vân tay, khuôn mặt,
những nốt đen lớn, biểu đồ,…Và nhiệm vụ thứ hai là phải xử lý các đối tượng văn
bản cấu thành từ chữ viết như ký tự, từ, chuỗi ký tự, chữ viết tay. Việc phát hiện độ
nghiêng (tilt) của tài liệu (độ nghiêng của văn bản xuất hiện khi chúng ta quét ảnh
5
tài liệu từ máy quét đã đặt không chuẩn xác các vị trí của nó), phát hiện các phông
chữ, độ lớn chữ, từ, cụm từ, dòng văn bản, đoạn văn bản và các cột văn bản là
những công việc quan trọng và cần thiết để thực hiện việc phát hiện văn bản được
ứng dụng công nghệ OCR như đã đề cập. Sau khi thực hiện thành công hai nhiệm
vụ chính, hệ phân tích ảnh tài liệu sẽ trích chọn những thông tin cần thiết đã phát
hiện được, đưa vào một tài liệu ở một định dạng khác như tập tin văn bản (word)
hoặc ngôn ngữ hiển thị siêu văn bản (Hyper Text Markup Language-HTML).
Việc đầu tư tài chính, công nghệ, con người cùng các yếu tố liên quan để
thiết kế và ứng dụng hệ phân tích ảnh tài liệu là rất cần thiết và vô cùng quan trọng.
Nó giúp chúng ta giải quyết rất nhiều vấn đề trong thực tế khi mà số lượng các dữ
liệu lớn. Con người tiếp nhận và xử lý thông tin nhờ vào các giác quan, nhưng có
thể nói trong đó có khoảng 80% là thu nhận bằng mắt. Một vài ví dụ điển hình có
thể minh chứng rằng thực sự cần thiết để sở hữu một hệ thống phân tích ảnh tài liệu
nào đó. Thứ nhất, ta là người phải nhập điểm số cho hàng trăm nghìn sinh viên
trong một trường đại học được gửi về từ các giáo viên giảng dạy, theo cách làm
truyền thống thì tại phòng xử lý điểm phải có ít nhất một người ngồi đọc điểm cùng
với một người gõ vào máy tính. Việc này vừa tốn thời gian, tốn chi phí nhân công,
ít khách quan lại dễ xảy ra sai sót do yếu tố con người. Thay vào đó, nhà trường có
thể thiết kế phiếu điểm giao cho giảng viên trong đó đã có sẵn các giá trị từ 1 đến
10 cho mỗi sinh viên và chỉ việc chấm điểm theo cách tô đen vào vị trí điểm số mà
sinh viên đạt được. Cuối cùng bảng điểm này được quét để máy tính phát hiện điểm
số một cách tự động nhờ vào chấm đen mà giảng viên đã tô đậm thông qua một hệ
nhận dạng ảnh tài liệu, theo đó sẽ khắc phục được những nhược điểm của cách làm
truyền thống. Thứ hai là, tại một doanh nghiệp sản xuất kinh doanh với số nhân
công hàng chục ngàn người làm việc trong ngày, trong các công đoạn chấm công có
việc kiểm tra sự có mặt của nhân viên vào đầu giờ và cuối giờ làm. Với phương
pháp truyền thống doanh nghiệp phải cử ra rất nhiều người để theo dõi các nhân
viên còn lại việc vào và ra khỏi công ty phải đúng giờ. Việc này đã được khắc phục
nhằm đem lại sự thuận lợi, chính xác và ít tốn kém bằng cách sử dụng một máy
chấm công bằng vân tay, trong đó tích hợp công nghệ xử lý và so sánh dấu vân tay
bảo đảm công tác thống kê số giờ làm mà không cần sự theo dõi trực tiếp của con
6
người. Trong đó, máy chấm công bằng dấu vân tay ứng dụng hệ phân tích ảnh tài
liệu.
Xử lý Ảnh tài liệu
Xử lý Văn bản
Nhận dạng
ký tự
Quang học
Phân tích bố
trí trang
Xử lý đối tượng ảnh
Xử lý đường kẻ
Xử lý biểu
tượng và vùng
Phát hiện độ
Đường thẳng, góc và
Lấp đầy các
nghiêng,
các đường cong
khu vực
dòng, khối
và đoạn văn
bản
Hình 1.1: Sơ đồ khối liệt kê nhiệm vụ xử lý ảnh tài liệu được phân chia theo cấp bậc
trong mỗi vùng của ảnh. Nguồn: Gorman(2009), tác giả dịch thuật (7/2012).
Văn bản
Hệ phân tích ảnh tài liệu đã được sử dụng trong vài thập kỷ qua, đặc biệt là
trong ngành kinh doanh ngân hàng, bưu điện, thư viện,…ứng dụng để máy tính đọc
mã vạch hoặc lưu trữ tài liệu ở dạng điện tử, vào cuối những năm 1980 và 1990 thì
đã phát triển nhanh chóng. Lý do chủ yếu của việc phát triển này là tốc độ ngày
càng lớn và chi phí thấp hơn của phần cứng máy tính. Kể từ khi máy fax trở nên
phổ biến, chi phí của máy quét quang học cho các tài liệu đầu vào giảm xuống đã
giúp các doanh nghiệp nhỏ cũng như mỗi cá nhân có cơ hội được sử dụng những
công nghệ này. Mặc dù ảnh tài liệu có chứa một lượng tương đối lớn dữ liệu, thì
ngay cả máy tính cá nhân hiện nay cũng đã có tốc độ đủ để xử lý chúng. Bộ nhớ
máy tính bây giờ không những đủ cho các hình ảnh tài liệu lớn, mà quan trọng hơn,
bộ nhớ quang học bây giờ cũng đủ để lưu trữ khối lượng lớn dữ liệu. Điều này dẫn
đến ngày càng phát triển công nghệ nhận dạng và xử lý ảnh tài liệu. Sự bổ sung cần
thiết cho những cải tiến phần cứng là những tiến bộ đang được thực hiện trong việc
phát triển các thuật toán và phần mềm phân tích ảnh tài liệu. Trong đó công nghệ
OCR có khả năng nhận dạng văn bản với độ chính xác lên đến khoảng 90%, bên
cạnh đó nhiều phương pháp nhận dạng ảnh tài liệu khác cũng được cải tiến gần như
7
tương tự. Theo đó, các tài liệu viết tay hoặc tài liệu đã được in ấn hay những hình
ảnh có thể được chuyển thành tài liệu điện tử trên máy tính để thuận tiện trong việc
lưu trữ, quản lý, chỉnh sửa và biên soạn lại. Tuy nhiên, tài liệu giấy cho đến nay vẫn
đang phát huy vai trò truyền thống của nó do tính chất trực quang, dễ thao tác, phổ
biến được rộng rãi đối với mọi đối tượng sử dụng. Vì vậy, chúng ta phải tìm cách
giải quyết vấn đề là sử dụng công nghệ và các thuật toán để tích hợp dữ liệu dưới
dạng ảnh tài liệu vào trong bộ nhớ phần cứng để xử lý bằng máy tính.
Sau khi đã tạo ra dữ liệu, máy tính phải thực hiện các bước xử lý cơ bản
như xử lý điểm ảnh, phân tích các thành phần đặc trưng, phân tách từng thành phần
phát hiện riêng biệt là phát hiện hình ảnh và phát hiện văn bản.
Trang Tài liệu
Thu thập dữ liệu
107 điểm ảnh
Xử lý mức điểm ảnh
7.500 hình bao ký tự, mỗi hộp có kích
thước 15x20 điểm ảnh
500 đường kẻ và các đường cong, độ dài
từ 20 đến 2.000 điểm ảnh
10 khu vực khác nhau được tô, từ 20x20
đến 200x200 điểm ảnh
Phân tích mức đặc trưng
500x5 đặc trưng đường thẳng và
đường cong
10 x 5 đặc trưng vùng
7,500x10 đặc trưng ký tự
Phân tích và nhận
dạng văn bản
1.500 ký tự, 10 đoạn văn,
một tiêu đề chính,…
Phân tích và nhận
dạng hình ảnh
Hai sơ đồ, một biểu tượng công
ty, các hình ảnh khác.
Mô tả tài liệu
Hình 1.2. Một trình tự để phân tích ảnh tài liệu, cùng với các ví dụ về các kết quả trung
gian, kết quả cuối cùng và kích thước của dữ liệu. Nguồn: Gorman (2009), tác giả dịch
thuật (7/2012).
8
Hình 1.2 mô phỏng một chuỗi các bước trong phân tích hình ảnh tài liệu
phổ biến. Các phần tiếp theo sẽ trình bày vắn tắt một số bước cơ bản này. Sau khi
thu thập dữ liệu, hình ảnh trải qua xử lý cấp độ điểm ảnh và phân tích tính năng, sau
đó mỗi loại đối tượng văn bản và hình ảnh được phát hiện và xử lý riêng. Thu thập
dữ liệu được thực hiện trên một tài liệu giấy thường bằng cách quét quang học. Các
dữ liệu sau đó được lưu trữ trong một tập tin hình ảnh, gọi là điểm ảnh, được lấy
mẫu trong một mô hình mạng lưới xuyên suốt ảnh tài liệu (Gorman – 2009).
1.2 Quá trình thu nhận ảnh tài liệu
Ảnh tài liệu thường được thu thập bằng cách quét quang học thông qua máy
quét hoặc bằng cách sao chép hình ảnh và những đoạn phim kỹ thuật số từ máy
chụp hoặc máy quay phim (camera) rồi được lưu trữ vào máy tính dưới dạng một
tập tin ảnh gồm có các yếu tố hình ảnh, hoặc điểm ảnh, đó là “nguyên liệu” đầu vào
để phân tích ảnh tài liệu sau này. Dữ liệu lúc này được tập hợp là các điểm ảnh
(pixels) và được mô phỏng thành tập hợp của một lưới các điểm ảnh (a grid pattern)
(Gorman - 2009).
Các thiết bị thu nhận ảnh tài liệu có hai loại chính tương ứng với hai loại
ảnh thông dụng Vector và Raster. Theo đó, quá trình thu nhận ảnh tài liệu thực hiện
các công đoạn chính gồm việc biến đổi năng lượng quang học thành năng lượng
điện gọi là cảm biến và tổng hợp năng lượng điện thành ảnh gọi là quá trình lượng
tử hóa (Đỗ Năng Toàn-2008). Với ảnh nhị phân thì cường độ điểm ảnh có thể nhận
một trong hai giá trị OFF (0) hoặc ON (1) (Hình 1.3). Đối với ảnh đa cấp xám thì
cường độ điểm ảnh nhận giá trị từ 0 đến 255 và với ảnh màu thì giá trị điểm ảnh
nhận 3 kênh là R, G, B từ 0 đến 255 giá trị màu sắc. Thí dụ, với một trang ảnh tài
liệu có kích thước 30x40 cm và có 140 điểm ảnh trong 1 centimet thì tạo được ảnh
với 4200x5600 điểm ảnh. Từ đó cho thấy rằng một ảnh tài liệu thông thường là tập
hợp của các giá trị điểm ảnh mà người ta đã dùng các bộ cảm biến hoặc máy quét để
biến tín hiệu quang thành tín hiệu điện liên tục, rồi thì khắc phục hiện tượng chồng
phổ, thực hiện lượng tử hóa cùng với các công đoạn kỹ thuật khác và cuối cùng sẽ
trích chọn được các thông tin phù hợp.
9
Hình 1.3. Một hình ảnh nhị phân của chữ "e" được thực hiện lên ON và
OFF các điểm ảnh, ON điểm ảnh được hiển thị ở đây là "X". Nguồn
Gorman (2009).
1.3 Các bước xử lý điểm ảnh của ảnh tài liệu
Một số bước quan trọng trong quá trình xử lý điểm ảnh của hệ phân tích
ảnh tài liệu cần phải được thực hiện để làm cơ sở cho các quá trình phân tích và
nhận dạng về sau. Cụ thể, người ta thường thực hiện các công việc gồm tăng giảm
độ sáng bằng cách cộng thêm cho mỗi giá trị của điểm ảnh một giá trị nguyên c nào
đó, nếu giá trị c lớn hơn 0 thì ảnh sáng lên, ngược lại nếu giá trị c nhỏ hơn 0 thì ảnh
sẽ tối đi. Tiếp đến là việc chọn và tách ngưỡng để chuyển ảnh màu hoặc ảnh đa cấp
xám về ảnh nhị phân, hay các thành phần trong ảnh tài liệu không cần quan tâm đến
có thể được loại trừ bằng việc giảm nhiễu (noise reduction) và một số bước còn lại
là phân đoạn, dò biên để xác định các vùng, các đặc trưng và đối tượng phù hợp.
Sau khi đã thực hiện các công đoạn vừa rồi, thì người ta thường nén các dữ liệu
bằng các phương pháp mã hóa chuỗi (chain coding) và biểu diễn ở dạng vectơ.
1.3.1 Phương pháp nhị phân
Đối với ảnh tài liệu dạng đa cấp xám có thông tin vốn là nhị phân như văn
bản hoặc hình ảnh thì mục tiêu là phải chọn được một ngưỡng để tách thông tin nền
và thông tin ảnh thành hai phần riêng biệt. Vì vậy phương pháp nhị phân thường
được ưu tiên thực hiện trước. Song việc chọn được một ngưỡng thích hợp để tách
thông tin ảnh tài liệu thành hai phần như vậy không phải là việc dễ dàng và sẽ càng
khó khăn hơn đối với chúng ta khi gặp phải những thông tin ảnh mà độ tương phản
giữa giá trị điểm ảnh nền và giá trị điểm ảnh văn bản là thấp. Khi đường nét của văn
bản quá mỏng hoặc khi quét ảnh tài liệu không đủ cường độ sáng thích hợp thì cũng
10
gây ra những khó khăn trong quá trình tìm ngưỡng. Vì vậy, người ta đã áp dụng
nhiều phương pháp tách ngưỡng để khắc phục khó khăn trên. Trong đó phương
pháp tách ngưỡng tự động thường được áp dụng. Cụ thể, giá trị ngưỡng α trong kỹ
thuật tách ngưỡng thường cho bởi người sử dụng. Kỹ thuật tìm, tách ngưỡng tự
động nhằm tìm ra ngưỡng α một cách tự động dựa vào histogram theo nguyên lý
trong vật lý là vật thể tách làm hai phần nếu tổng độ lệch trong từng phần là tối
thiểu (Đỗ Năng Toàn-2008). Cũng phải lưu ý trong quá trình tách ngưỡng khi
chuyển ảnh màu thành ảnh đen trắng được ứng dụng khi quét và nhận dạng văn bản
có thể xảy ra sai sót nền thành ảnh hoặc ảnh thành nền, dẫn đến ảnh bị đứt nét hoặc
kết dính (Hình 1.4).
Hình 1.4: Mô phỏng phương pháp nhị phân ảnh. (a): Biểu đồ Histogram của ảnh đa cấp
xám ban đầu. (b): ngưỡng thấp. (c): ngưỡng phù hợp. (c): ngưỡng cao. Nguồn: Gorman
(2009).
11
1.3.2 Phương pháp khử nhiễu ảnh
Trong quá trình thu nhận ảnh tài liệu, có hai loại nhiễu cơ bản là nhiễu hệ
thống (nhiễu này có quy luật nên có thể khử bằng các phép biến đổi) và nhiễu ngẫu
nhiên (những dạng vết bẩn không rõ nguyên nhân nên có thể khắc phục bằng các
phép lọc). Nguyên nhân chủ yếu gây ra nhiễu là do quá trình sao chép ảnh
(photocopy) hay quá trình quét ảnh hoặc chuyển qua máy Fax. Giảm nhiễu nhằm
mục đích loại bỏ các tính năng không liên quan để tránh trường hợp gây ra lỗi trong
các bước xử lý tiếp theo cũng như giảm dung lượng lưu trữ và giảm được thời gian
xử lý.
Ảnh nhị phân thường xuất hiện một số loại nhiễu kích thước nhỏ gọi là
nhiễu xung, nhiễu đốm hay chỉ một loại bụi bẩn nào đó, thuật ngữ tiếng anh thường
gọi là salt-and-pepper noise, tức là mô tả điểm nhiễu như hạt muối hoặc hạt tiêu. Để
khử nhiễu, người ta thường sử dụng một số phương pháp như các phép toán hình
thái học, trong đó nghiên cứu về cấu trúc hay hình học topo của đối tượng trong ảnh
tài liệu. Phần lớn các phép toán của “Hình thái” được định nghĩa từ hai phép toán cơ
bản là phép toán “giãn nở” (Dilation) và phép toán “co” (Erosion). Giả sử ta có đối
tượng X và phần tử cấu trúc mẫu B trong không gian hai chiều, ký hiệu Bx là dịch
chuyển của B tới vị trí x. Khi đó, phép “giãn nở” của X theo mẫu B là hợp của tất cả
các Bx với x thuộc X. Và phép “co” của X theo B là tập hợp tất cả các điểm x sao
cho Bx nằm trong X. Như vậy có thể thấy rằng phép “co” ảnh sẽ làm giảm kích
thước của vùng mang thông tin ảnh trong vùng mang thông tin nền, và phép “giãn
nở” ảnh thực hiện điều ngược lại và làm cho vùng mang thông tin ảnh trong vùng
mang thông tin nền tăng lên. Người ta thực hiện tuần tự việc “co” và “giãn nở” ảnh
nhiều lần bằng cách kết hợp các phép toán này. Một vài phương pháp kết hợp như
vậy có tên là phép toán mở (OPEN) và phép toán đối xứng của nó là phép toán đóng
(CLOSE). Phép toán mở của X theo cấu trúc B là tập hợp các điểm của ảnh X sau
khi đã co và giãn nở liên tiếp theo B. Kết quả mà phép toán mở mang lại là làm
nhẵn vùng biên của đối tượng, làm đứt vùng eo nhỏ và từ đó khử được những vùng
điểm nhiễu nhỏ. Theo đó, kết quả của phép toán đóng là làm nhẵn vùng biên, các lỗ
hổng nhỏ được loại trừ và các kẽ hở không đáng kể giữa các đối tượng được hàn
gắn lại (Hình 1.5).
12
Hình 1.5: Mô phỏng sự kết hợp giữa các phép toán hình thái học ứng dụng vào
việc khử một vài loại nhiễu cơ bản. Nguồn: Gorman (2009).
1.3.3 Phân khúc các đặc tính
Để phục vụ cho các bước xử lý ảnh tài liệu về sau, một trong những công
đoạn khá quan trọng là phải tiến hành phân khúc (còn được gọi là phân đoạnsegmentation) các đặc tính cơ bản có chứa trong hình ảnh thu nhận được. Cụ thể,
việc phân khúc được tiến hành với hai tiến trình chính. Thứ nhất là tách riêng biệt
giữa các lớp của ảnh tài liệu, gồm lớp hình ảnh và lớp văn bản đối với trường hợp
dữ liệu đầu vào có chứa cả hình ảnh và văn bản. Thứ hai là tiếp tục thực hiện các
tiến trình phân tích trên các lớp vừa được tách ra. Với lớp hình ảnh thì phân định rõ
các đối tượng hình vẽ, đường kẻ, biểu tượng cũng như các loại hình ảnh khác. Còn
đối với lớp văn bản thì tiến hành xác định các ký tự, từ, đoạn văn, chia cột văn
bản,…Một số hướng tiếp cận phương pháp phân khúc các đặc tính ảnh như dựa trên
không gian đặc trưng, không gian ảnh hoặc là dựa trên mô hình vật lý. Hiện nay
một số phương pháp phân khúc thường được áp dụng như phương pháp phân khúc
13
yếu của B.G. Prasad hoặc phân khúc dựa trên ngưỡng cục bộ thích nghi. Giả sử ảnh
đầu vào là một trang sách, trong đó có cả chữ viết được chia thành các đoạn và chia
ra hai cột, đồng thời có cả hình ảnh minh họa, thì lúc này việc phân khúc ảnh sẽ
thực hiện tách riêng hình ảnh và văn bản. Tiếp đến là văn bản sẽ được tách thành
các đoạn, các cột, các chuỗi, còn hình ảnh thì được tách thành các biểu tượng,
đường kẻ và các đối tượng ảnh khác. Như vậy, tài liệu ảnh sau khi được thực hiện
phân khúc sẽ quản lý được các đối tượng rất nhỏ như các phần cơ bản của ảnh.
1.3.4 Tìm xương và phát hiện biên
Tìm xương của ảnh là việc biểu diễn ảnh dưới dạng những đường trục trung
tâm của đối tượng ảnh. Đây là kỹ thuật làm giảm bớt các điểm ảnh lân cận có cùng
bản chất nhưng vẫn bảo đảm tính liên kết và liên thông của mỗi đối tượng ảnh.
Xương được coi như là hình dạng cơ bản của một đối tượng, người ta có thể lấy lại
được các thông tin về hình dạng nguyên bản của một đối tượng thông qua xương
của nó. Việc tìm được xương của đối tượng ảnh sẽ giúp chúng ta giảm bớt tốn kém
vì không cần thiết phải lưu trữ những thông tin không quan trọng trong quá trình xử
lý sau này, cũng như có thể đồng bộ hóa việc lưu trữ các đối tượng ảnh tương tự
nhau ví dụ như những đoạn thẳng có thể vẽ với độ dày mỏng khác nhau nhưng khi
lưu trữ và biểu diễn thì các đoạn này là giống nhau nhờ vào việc biểu diễn xương
của chúng. Hình 1.6 biểu diễn ảnh nguyên bản bên trái và xương tương ứng của
chúng phía bên phải. Đã có nhiều thuật toán được phát triển trong việc tìm xương
nhằm từng bước khắc phục việc mất mác thông tin trong quá trình thực hiện. Người
ta chia thành hai loại thuật toán tìm xương là tìm xương dựa trên làm mảnh
(thinning) và tìm xương không dựa trên làm mảnh. Thuật toán làm mảnh là quá
trình lặp duyệt và kiểm tra tất cả các điểm thuộc đối tượng. Trong mỗi lần lặp tất cả
các điểm của đối tượng sẽ được kiểm tra: Nếu chúng thỏa mãn điều kiện xóa nào đó
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 các điểm biên. Người ta thường sử dụng thuật toán làm
mảnh song song và thuật toán làm mảnh tuần tự. Nếu tìm xương không dựa trên làm
mảnh thì để tách được xương của đối tượng, người ta sử dụng đường biên của đối
tượng nhờ vào trục trung vị thông qua hai bước cơ bản: Bước thứ nhất. tính khoảng
14
các từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất, và cần phải tính toán
khoảng cách tới tất cả các điểm biên của ảnh. Bước thứ hai, khoảng cách ảnh đã
được tính toán và các điểm ảnh có giá trị lớn nhất được xem là nằm trên xương của
đối tượng (Đỗ Năng Toàn-2008).
Việc tìm xương là hữu hiệu đối với những đối tượng ảnh có độ mảnh dạng
đường thẳng, nét viết, bản đồ, đường vân và các đối tượng có hình thù tương tự,
nhưng đối với những đối tượng ảnh có kích thước lớn như những vùng được tô kín
bằng màu đen hoặc những vết loan thì xương của chúng chỉ là một điểm ảnh nằm
tại tâm của đối tượng. Lúc này, việc phát hiện biên của đối tượng sẽ tỏ ra hiệu quả
hơn để định hình và biểu diễn đối tượng kiểu này. Biên là yếu tố quan trọng trong
việc trích chọn đặc điểm nhằm tiến đến “hiểu” ảnh. Với ảnh đen trắng, một điểm
được gọi là điểm biên nếu nó là điểm đen có ít nhất một điểm trắng bên cạnh. Tập
hợp các điểm biên tạo nên đường biên hay đường bao của đối tượng ảnh. Người ta
thường sử dụng một số phương pháp phát hiện biên như: Phát hiện biên trực tiếp,
phát hiện biên gián tiếp thông qua một số kỹ thuật phát hiện biên như kỹ thuật
Gradient, kỹ thuật Prewitt, kỹ thuật Sobel, kỹ thuật la bàn, kỹ thuật Laplace, kỹ
thuật Canny (Đỗ Năng Toàn-2008)…Còn đối với các đối tượng ảnh chiếm những
vùng nhỏ như những ký tự riêng biệt hoặc những nét vẽ các đối tượng cực nhỏ
trong sơ đồ bản mạch điện tử chẳng hạn thì cả việc tìm xương lẫn phát hiện biên
đều không phát huy hiệu quả mà lúc này người ta sẽ dùng cách thức lưu trữ mảng
(array) của những giá trị của điểm ảnh để biểu diễn những vùng ảnh nhỏ này.
Hình 1.6: Mô tả hình ảnh nguyên bản và Xương tương ứng của nó.
(a): chữ “m”; (b): sơ đồ bản mạch; (c): dấu vân tay. Nguồn Gorman (2009)
15
1.3.5 Lưu trữ dạng véctơ hóa
Khi đã phát hiện được xương hoặc biên của đối tượng ảnh thì ta có thể biểu
diễn ảnh theo một trong hai cách này. Nhưng đối tượng ảnh còn có thể được biểu
diễn hiệu quả hơn bằng cách lưu trữ các điểm ảnh theo các giá trị ON và OFF, trong
đó giá trị ON thể hiện giá trị của mỗi điểm ảnh và OFF biểu diễn giá trị điểm nền.
Người ta thường dùng phương pháp lưu trữ dưới dạng mã mắc xích, theo đó, các
điểm có giá trị ON được biểu diễn thông qua một tập các điểm láng giềng có thể đi
theo hướng 4 láng giềng hoặc 8 láng giềng của nó. Phương pháp này sẽ lưu trữ
hướng (vector) của các điểm láng giềng mà không cần lưu trữ vị trí của điểm ảnh có
giá trị ON. Láng giềng của điểm X là tất cả các điểm nằm liền kề điểm X thuộc ma
trận 3x3 với điểm X là tâm (Hình 1.7). Một số ưu điểm mà phương pháp này đem
lại là việc lưu trữ sẽ hiệu quả hơn vì thông thường với ảnh có kích thước lớn hơn
256x256 thì tọa độ giá trị điểm ảnh ON thường được biểu diễn bởi 16 bit; trong khi
đó cách lưu trữ dạng véctơ hóa một điểm láng giềng thuộc một trong tám hướng do
vậy mỗi điểm ảnh ON chỉ cần biểu diễn bằng một byte, thậm chí chỉ cần 3 bit để
lưu. Ngoài ra, phương pháp vector hóa lưu theo cấu trúc các điểm ảnh có liên quan
với nhau do vậy tạo điều kiện thuận lợi để làm trơn các đường cong và có thể xấp xỉ
cho các đường thẳng.
1.4 Các bước phân tích ảnh tài liệu
Để phân tích sâu sắc và hiểu được bản chất của ảnh tài liệu, thì sau các
bước tiền xử lý đã trình bày ở những phần trên, người ta tiếp tục tiến hành các công
đoạn phân tích ảnh. Một số nhiệm vụ quan trọng ở bước phân tích này là phân tích
16
các đặc trưng của ảnh, phân tích các đối tượng văn bản, trong đó việc ước lượng độ
nghiêng và phân tích sơ đồ trình bày trên trang tài liệu là được chú trọng hơn cả.
1.4.1 Phân tích các đặc trưng của ảnh tài liệu
Đặc trưng của ảnh tài liệu gồm có đặc trưng cục bộ (local features) và đặc
trưng toàn cục (global features). Với ảnh tài liệu chứa văn bản, đặc trưng toàn cục
mô tả từng trang, độ nghiêng của trang khi quét vào từ máy quét, độ dài dòng,
khoảng cách dòng, còn đặc trưng cục bộ thì mô tả về kích thước phông chữ, dấu
chấm câu, v.v…Tương tự như thế, với ảnh tài liệu chứa hình ảnh, thì đặc trưng toàn
cục cũng xét đến độ nghiêng của trang tài liệu, độ rộng dòng, phạm vi của độ cong
đối với các đường cong, độ dài tối thiểu của dòng. Và đặc trưng cục bộ lại xét đến
việc mô tả mỗi góc, mô tả đường cong và đường thẳng, định vị các hình chữ nhật,
hình tròn và hình dạng của các loại hình học khác.
Như vậy, để phục vụ cho các công đoạn xử lý ảnh tiếp theo, thì các hình
ảnh sau khi đã xử lý điểm ảnh nó sẽ được lưu trữ ở dạng xương, dạng hình bao hoặc
dạng véctơ hóa và tiếp tục được phân tích đặc trưng. Sau khi hoàn thành bước phân
tích đặc trưng thì gần như tất cả các loại đối tượng được phát hiện đầy đủ hơn, như
là phát hiện đường cong được xấp xỉ thành hình đa giác nào đó (polygonal
approximation), định vị được các điểm quan trọng nằm trên đường thẳng và đường
cong như các điểm góc và điểm chuẩn bị để uốn cong. Theo đó, các biểu tượng ảnh
hoặc các ký tự riêng biệt có các vùng giới hạn tương ứng thì những đặc trưng điển
hình như độ thắt chặt của hình bao, tỷ lệ hình ảnh, độ dày đặc của các điểm ON của
ảnh, số đường viền cũng như tính chất trơn của nó,… tất cả chúng đều được ghi
nhận và xử lý để làm cơ sở dữ liệu cho những thao tác xử lý nhận dạng về sau.
1.4.2 Phân tích các đối tượng văn bản trong ảnh tài liệu
Để phân tích đối tượng văn bản trong ảnh tài liệu, người ta thường sử dụng
một số phương pháp phân tích truyền thống. Thứ nhất là phương pháp phát hiện ký
tự, phát hiện chuỗi ký tự bằng công nghệ nhận dạng ký tự quang học (OCR) đã có
đề cập ở phần đầu của bài luận này. Thứ hai là người ta sử dụng phương pháp phân
tích bố trí trang tài liệu để phát hiện được định dạng của văn bản bao gồm những
yếu tố quan trọng như phát hiện khu vực ghi chú thích, khu vực phân biệt đoạn này
17
với đoạn khác, dấu hiệu cho thấy nơi trình bày tiêu đề phụ, tiêu đề chính. Chúng ta
có thể áp dụng hai phương pháp phân tích này một cách tuần tự, riêng lẻ hoặc phối
hợp chặt chẽ với nhau bằng việc kế thừa sản phẩm của phương pháp này để ứng
dụng vào phương pháp kia. Từ đó phát hiện được văn bản là một bảng ghi chú, một
tờ mục lục, một bảng liệt kê hay biểu mẫu được sử dụng trong ngân hàng hay là một
dạng bì thư được sử dụng trong ngành viễn thông và bưu điện. v.v…tùy vào cách
thức bố trí của các khối văn bản. Điểm mạnh của phương pháp OCR thường được
ghi nhận và đánh giá cao trong việc phát hiện văn bản từ những ký tự được tạo ra từ
máy in hoặc những chữ viết tay. Trong khi đó phương pháp phân tích bố trí trang tài
liệu lại đi phân tích các sơ đồ trình bày nhằm phân tích các định dạng trang ảnh tài
liệu để tiến đến phát hiện các cấu trúc của những bảng biểu và cả việc phát hiện
những thông tin đang được chứa đựng trong các biểu mẫu đó. Và đôi khi chúng ta
cũng phải chú trọng phát hiện độ nghiêng của ảnh tài liệu để có giải pháp khắc phục
sự nghiêng khi quét ảnh đầu vào vì yếu tố nghiêng sẽ ảnh hưởng rất lớn đến việc
nhận dạng các đối tượng về sau.
1.4.2.1
Xác định độ nghiêng của ảnh tài liệu
Như đã có trình bày sơ lược ở những phần trên của bài luận này, nguyên
nhân tạo ra độ nghiêng của ảnh tài liệu là do trong quá trình thu nhận ảnh đầu vào
(quá trình quét ảnh hoặc sao chụp ảnh bằng tay đã đặt ảnh không chính xác tuyệt
đối về vị trí thẳng góc, hoặc quá trình chụp ảnh không giữ được phương thẳng
đứng của máy chụp,…). Ảnh tài liệu được cho là nghiêng khi phát hiện góc nghiêng
khác 0. Một dòng văn bản được cấu thành từ một nhóm các ký tự, các từ tiếp giáp
tương đối gần nhau, các biểu tượng,…được bố trí trên một đường thẳng theo hướng
đứng hoặc nằm ngang. Những dòng văn bản này là căn cứ cơ bản để xác định góc
độ nghiêng của trang ảnh tài liệu trên cơ sở so sánh tính chất song song của các
dòng văn bản so với các cạnh của mép trang tài liệu. Tức nhiên là trang ảnh tài liệu
ban đầu sẽ không nghiêng theo nghĩa là các dòng văn bản có độ song song tuyệt đối
so với các cạnh theo chiều ngang và chiều dọc của một trang, và khi quét vào máy
tính thì trang này cũng có thể bảo toàn nghiêng nghĩa là góc nghiêng bằng 0 nhưng
điều này là không chắc chắn hoàn toàn. Vì vậy, cần phải định vị độ nghiêng và khắc
phục nó trước khi thực hiện những bước tiếp theo bởi vì khi áp dụng công nghệ
18
OCR hoặc phân tích bố trí trang tài liệu yêu cầu điều kiện là góc nghiêng trang tài
liệu phải bằng 0.
Một số phương pháp định vị độ nghiêng đã được đề xuất như là chọn đường
cơ sở phù hợp với phép biến đổi Hough (fitting baselines by the Hough transform),
phương pháp phân nhóm láng giềng gần nhất (nearest-neighbor clustering) hay
phương pháp chiếu nghiêng một bên (using the projection profile). Với phương
pháp chiếu nghiêng một bên thì người ta tính số các điểm ảnh có giá trị 1 đối với
ảnh nhị phân sau khi đã rà ảnh theo các cột hay các dòng rồi ghi nhận các giá trị này
vào một cấu trúc nhớ theo kiểu mảng hoặc danh sách liên kết, trong đó mỗi dòng
hay cột được rà sẽ tạo ra một chỉ số cho mảng hay cho danh sách liên kết. Do đó
một biểu đồ tần suất sẽ được hình thành để biểu thị các điểm ảnh có giá trị 1 nói
trên. Người ta tiến hành chiếu ảnh theo các góc có giá trị từ 0o đến 180o theo phép
chiếu nghiêng một bên (Hình 1.8a và Hình 1.8b). Người ta dùng các khái niệm
“vùng đỉnh” và “vùng lõm” để ứng dụng vào việc phát hiện nghiêng. Cụ thể, với ảnh
tài liệu có góc nghiêng là 0 thì vùng đỉnh của phép chiếu nghiêng một bên thể hiện
các dòng chứa các từ (word) và vùng lõm sẽ thể hiện khoảng trắng giữa các dòng
đó. Để định vị được độ lớn góc nghiêng của ảnh tài liệu, thì ta đi tìm góc quay một
bên mà tại đó biểu đồ tần suất thể hiện nhiều vùng lõm nhất và nhiều vùng đỉnh
nhất. Giả sử rằng biểu đồ tần suất ghi nhận được 20 vùng đỉnh và 20 vùng lõm thì
có thể biết rằng ảnh tài liệu hiện có 20 dòng văn bản. Theo đó, với từng phép chiếu
nghiêng một bên người ta tính tổng số đo về độ cao của các vùng đỉnh và tổng số đo
về độ cao của các vùng lõm tương ứng, góc chiếu nào có sự khác nhau giữa hai số
đo này lớn nhất thì đó là góc nghiêng của ảnh tài liệu.
19
Nguồn: Gorman (2009)
1.4.2.2
Phân tích cấu trúc bố trí của trang ảnh tài liệu
Nếu ảnh tài liệu thu nhận được đã phát hiện ra góc nghiêng khác 0, người ta
tiến hành xoay ảnh một góc thích hợp để trả độ nghiêng ảnh về 0, rồi tiếp tục thực
hiện quá trình phân tích cấu trúc bố trí của mỗi trang mà có khi còn được gọi là
phân tích theo cấu trúc bố trí vật lý và hình học. Mục tiêu của quá trình này là phát
hiện và trích chọn được cấu trúc của các phần văn bản (ở đây chủ yếu lấy được khối
và đoạn văn bản) bằng cách tách biệt các từ, tách cấu trúc của các khối, các dòng
v.v…tùy thuộc vào định dạng vật lý ban đầu của tài liệu. Ngoài ra việc xem xét để
phân tích cấu trúc của trang bố trí theo chức năng (còn được gọi là phân tích theo
sự bố cục loogic và cú pháp) cũng được thực hiện, trong đó có sử dụng những thông
tin miền phụ thuộc bao gồm các quy tắc bố trí của từng loại cấu trúc trang cụ thể, để
thực hiện gán nhãn cho các khối cấu trúc và đưa ra một số dấu hiệu nhận biết các
khối này. Việc ghi nhãn cho các khối chức năng này cũng có thể dẫn đến việc sáp
nhập hoặc chia tách các khối cấu trúc trong trang.
Hình 1.9 mô tả một thí dụ về kết quả phân tích cấu trúc một trang ảnh tài
liệu, trong đó nội dung và cách thức sắp xếp thông tin quy định trình bày cho trang
20
đầu tiên của một tài liệu kỹ thuật. Sau khi phân tích đã phân định được các khối chỉ
định cho các thành phần chính, gồm: tên tài liệu, tiêu đề chính, tên tác giả, phần tóm
tắt, các từ khóa, các đề mục, các khối cấu thành phần thân chính của văn bản, phần
chú thích và phần ghi nhận về bản quyền của tác giả.
Ảnh tài liệu nguyên
bản ban đầu được
quét vào máy tính
Tên của tài liệu
Tiêu đề
Tên tác giả
Từ khóa
Giới thiệu
Đề mục
Khối 1
thể hiện
Thân văn
bản
Chú thích
Hình ảnh thể hiện cấu trúc
Hình ảnh thể hiện chức
năng của các khối
Khối 2
thể hiện
Thân văn
bản
Thông tin bản
quyền tác giả
Hình 1.9: Mô tả phân tích cấu trúc và phân tích theo chức năng các khối trong trang tài liệu.
Nguồn: Xử lý của tác giả (7/2012)
21
Hai phương pháp phân tích theo hướng cấu trúc vật lý thường được sử dụng
để tiến hành phân tích trang là tiếp cận từ trên xuống (top-down) hoặc tiếp cận từ
dưới lên (bottom-up). Hai phương pháp này có tính đối ngẫu lẫn nhau. Nhưng người
ta thường áp dụng phối hợp theo hướng kế thừa sản phẩm của nhau để cùng phân
tích trang tài liệu. Thông thường phương pháp từ trên xuống sẽ đi phân tích những
khối cấu trúc lớn đến những khối và thành phần cấu trúc hay đối tượng nhỏ hơn.
Thí dụ một trang có thể được phân tích thành các khối phần trên, khối phần giữa và
khối phần chân của trang, rồi thì các khối này lại được phân tích thành các đoạn văn
bản và đối tượng ảnh, tiếp đến các đoạn này lại được tách thành các dòng, các cụm
từ, các từ, các ký tự. Trong khi đó phương pháp tiếp cận dưới lên lại phân tích theo
chiều hướng quy nạp ngược lại, cụ thể là nó đối ngẫu bằng cách xuất phát từ các
khoảng trắng liên thuộc được giao kết với các ký tự để phát hiện các từ, tiếp đến các
từ này lại được giao kết với nhau để nhận dạng được từng dòng, cứ tiếp tục như vậy
để phát hiện được các thành phần lớn hơn của trang.
1.5 Tìm hiểu phương pháp phát hiện ký tự quang học
Phát hiện ký tự quang học (OCR) là một công nghệ thuộc lĩnh vực nhận
dạng, người ta ứng dụng công nghệ này nhằm nhận dạng các chuỗi ký tự trên cơ sở
căn cứ ban đầu là những ký tự trong bảng chữ cái, khởi đầu là bảng chữ cái tiếng
Anh. Nhưng cho dù là bảng chữ cái giới hạn nào thì cũng có rất nhiều kiểu viết khác
nhau, có thể do sự đa dạng của các nét viết tay hoặc do kiểu phông chữ, kích thước
chữ. Vì thế, để phát hiện được các chuỗi ký tự đa dạng như vậy người ta phải tìm
cách tạo ra các quy tắc cũng như một số quy ước tổng thể làm căn cứ thì mới có thể
giải quyết được bài toán nhận dạng phức tạp này. Theo đó, OCR luôn cố gắng tích
hợp và phát triển cả công nghệ phần cứng lẫn những thuật toán và xây dựng hệ
thống phần mềm để từng bước nhận dạng chữ viết với khả năng càng giống với con
người càng tốt.
Tuy nhiên, cũng như những công nghệ nhận dạng khác, vì phải làm việc với
dữ liệu ảnh đầu vào cực kỳ phức tạp là chữ viết, nó được tạo ra một cách tự do đó là
không có một quy tắc nhất định hay bất kỳ ràng buộc nào về độ lớn, đường nét, độ
đậm nhạt, sự kết nét hay đứt nét…khi người ta viết chữ. Hay ngay cả khi đánh máy
tính thì với mỗi loại văn bản cũng được quy định bởi những phông chữ, cỡ chữ và
22
cách trình này khác nhau. Điều này tạo nên khó khăn rất lớn cho OCR trong khi
nhận dạng nếu gặp phải những ảnh tài liệu chữ viết hoặc văn bản có nhiều điểm
nhiễu hay bị liền nét giữa các con chữ hay bị đứt nét trong một con chữ hoặc gặp
phải chữ viết không được nắn nót. Một khi chữ viết tay không nắn nót hoặc máy
tính áp dụng một số phông chữ không được chân phương, không thường dùng thì
thí dụ chữ u rất giống với chữ v, số 6 giống với số 0 hoặc giống với số 4, số 3 giống
với số 9 (Hình 1.10a). Và sẽ càng khó khăn hơn khi mà cấu trúc của những từ ngữ
lại được xây dựng cả con số lẫn với chữ cái như số tài khoản sử dụng trong các
ngân hàng do máy tính tạo ra, hay thói quen viết tay các ký tự dính nét nhau khi tạo
thành một từ hoặc là những từ viết tắt chẳng hạn (Hình 1.10b).
Hình 1.10a: Mô tả những nét chữ viết tay không nắn nót dẫn đến rất khó
nhận dạng bằng công nghệ OCR. Nguồn: Dengel (2001).
Nguồn:
Dengel
(2001)
Hình 1.10b: Mô tả chữ viết tay với thói quen viết liền nét giữa số 4 và số 2
dẫn đến rất khó nhận dạng và tách biệt hai con số bằng công nghệ OCR
23
Công nghệ OCR là một hệ thống rất phức tạp của nhiều bước và nhiều công
đoạn thực hiện khác nhau. Trong đó có một số bước thực hiện cơ bản gồm có
phương pháp thực hiện và nhận dạng ký tự dựa trên ngữ cảnh như sau đây.
1.5.1 Phương pháp
Việc trích chọn các tính năng và phân loại để chia không gian đa chiều
thành các vùng tương ứng là những phần cốt lõi của công nghệ OCR trong đó có áp
dụng một số thuật toán chuyên biệt. Theo đó, thuật toán phân loại dựa trên các tính
năng của ảnh được trích chọn và những đặc điểm liên quan giữa các tính năng đó sẽ
được áp dụng để phân lớp trước các loại ký tự và phân bổ một ký tự nhận dạng
được vào trong một lớp tương ứng. Để phân bổ được một ký tự vào một lớp nào đó
người ta sử dụng tính chất về độ đo tương thích và thực hiện quá trình xử lý từ ngữ
dựa trên ngữ cảnh để hiệu chỉnh một số lỗi mà OCR chưa thể khắc phục được.
1.5.1.1
Trích chọn các tính năng
Các tính năng của đối tượng được trích xuất và sắp xếp dưới dạng những độ
đo. Song song với quá trình này, người ta xây dựng các lớp dữ liệu chứa các ký tự
bằng cách tạo ra một mô hình chung nhất cho các lớp đó. Từ đó tiếp tục thực hiện
quá trình chọn lựa tính năng đặc trưng bằng cách tìm kiếm và so sánh các thuộc tính
của từ ngữ đang nhận dạng trên cơ sở các lớp đã được xây dựng trước đó. Cụ thể,
các tính năng thường được đưa vào lớp để so sánh bao gồm các điểm bắt đầu, điểm
kết thúc, các dấu hiệu nối như gạch nối giữa hai thành phần để tạo nên ký tự mà cả
chữ A và chữ H đều có, các góc, các cạnh, các điểm uốn, điểm cắt, mặt lỗi lõm của
các đường bao bên ngoài cũng như các đường nét đặc trưng cơ bản của ký tự và của
từ. Cuối cùng các sản phẩm là những tính năng của các ký tự đã được trích chọn và
phân bổ vào từng lớp thích hợp. Nhưng trong quá trình phân lớp thì OCR thường
gặp phải những khó khăn khi phân định các lớp có những đặc trưng tương tự nhau,
như những đặc trưng của chữ o và số 0, chữ l và số 1 hay ký tự này quay đầu thì trở
thành ký tự khác như ký tự số 6 và số 9, chữ d và chữ p, v.v…
1.5.1.2
Phân loại
Nhìn chung nếu chỉ áp dụng một tính năng duy nhất thì không thể nhận
dạng được ký tự cũng như không thể tạo ra được các lớp đa dạng của những ký tự
- Xem thêm -