Số hóa bởi Trung tâm Học liệu ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG


ĐOÀN DUY THƢỜNG

NGHIÊN CỨU PHƢƠNG PHÁP PHÂN TÍCH CẤU TRÚC ẢNH MÀU,
ỨNG DỤNG TRONG NHẬN DẠNG CHỨNG MINH NHÂN DÂN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN- 2014

LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi và hoàn
thành dƣới sự hƣớng dẫn khoa học của TS. Nguyễn Thị Thanh Tân.
Nếu có gì vi phạm tôi xin hoàn toàn chịu trách nhiệm.

Học viên thực hiện luận văn Đoàn Duy Thƣờng

ii

Số hóa bởi Trung tâm Học liệu

LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn chân thành nhất tới TS. Nguyễn Thị Thanh Tân vì
đã có những chỉ dẫn, động viên quý báu trong suốt quá trình thực hiện luận
văn của tôi. Đồng thời tôi xin chân thành cảm ơn các thầy cô giáo trong Ban
giám hiệu, phòng Đào tạo, các thầy cô giáo của trƣờng Đại học Công nghệ
Thông tin và Truyền thông - Đại học Thái Nguyên cùng các thầy cô giáo
trong Viện Công nghệ Thông Tin - Viện Hàn lâm Khoa học Việt Nam đã
quan tâm, tạo điều kiện thuận lợi, nhiệt tình giảng dạy và hƣớng dẫn tôi trong
suốt quá trình học tập và hoàn thiện luận văn.
Cuối cùng tôi xin cảm ơn mọi sự giúp đỡ từ ngƣời thân, đồng nghiệp
những ngƣời đã luôn ủng hộ, hỗ trợ tôi trong suốt quá trình thực hiện luận văn
của mình.

4. Bố cục của luận văn. 3
CHƢƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG VĂN BẢN VÀ BÀI TOÁN
PHÂN TÍCH CẤU TRÚC 4
1.1. Tổng quan về nhận dạng văn bản 5
1.2. Bài toán phân tích cấu trúc trang 7
1.2.1 Giới thiệu chung 7
1.2.2. Một số kỹ thuật tiền xử lý trong phân tích cấu trúc trang ảnh 10
1.2.2.1. Nhị phân ảnh 10
1.2.2.2. Căn chỉnh độ nghiêng trang ảnh 13
1.2.2.3. Lọc nhiễu 14
1.2.2.4. Tách nền 16
1.2.2.5. Các toán tử hình thái 16
iv

Số hóa bởi Trung tâm Học liệu

1.2.3. Một số hƣớng tiếp cận trong phân tích cấu trúc trang văn bản 19
1.3. Kết luận 20
CHƢƠNG 2: MỘT SỐ KỸ THUẬT PHÂN TÍCH CẤU TRÚC, ỨNG DỤNG
TRONG PHÁT HIỆN VÀ BÓC TÁCH CÁC TRƢỜNG THÔNG TIN TRÊN
ẢNH TÀI LIỆU 21
2.1. Kỹ thuật X-Y Cut 21
2.2. Kỹ thuật Smearing 23
2.3. Kỹ thuật Whitespace 26
2.4. Kỹ thuật Docstrum 27
2.5. Kỹ thuật dựa trên lƣợc đồ Voronoi 29
2.6. Kỹ thuật phát hiện các ràng buộc trên dòng văn bản 32
2.7. Kỹ thuật phân tích cấu trúc ảnh tài liệu 33
2.7.1. Đặc trƣng của ảnh tài liệu cần nhận dạng 33
2.7.2. Phát hiện trƣờng số trong ảnh 35

OCR
Optical Character Recognition
CMND
Chứng minh nhân dân
RLSA
The run-length smearing algorithm

vii


Hình 3. 5. Phƣơng pháp tia quay 61
Hình 3. 6. Ảnh CMND 65
Hình 3. 7. Một số trƣờng hợp khó phát hiện 66 ix

Số hóa bởi Trung tâm Học liệu

DANH MỤC BẢNG BIỂU
Bảng 1. 1. Bảng mã 4 màu 11
Bảng 2. 1. Thông tin mặt trƣớc CMND 34
Bảng 3.1. Kết quả thực nghiệm 66
PHẦN MỞ ĐẦU
1. Đặt vấn đề
Nhận dạng mẫu là một ngành khoa học của học máy (hay trí tuệ nhân
tạo) nhằm phân loại dữ liệu (các mẫu) vào một số lớp[13]. Mẫu có thể là bất
kỳ thực thể nào cần đƣợc nhận ra, ví dụ: chữ in, chữ viết tay, vân tay, khuôn
mặt, tiếng nói, hình dạng… Cùng với sự phát triển của khoa học kỹ thuật,
các ứng dụng của nhận dạng mẫu ngày càng đƣợc mở rộng, từ việc tự động
hoá một số quy trình trong sản xuất công nghiệp cho đến dự báo thời tiết, dự
báo cháy rừng hay là một phần quan trọng trong các hệ thống máy tính
thông minh…
Một trong những ứng dụng phổ biến của nhận dạng mẫu hiện nay là
phân tích và nhận dạng ảnh tài liệu (có nguồn gốc từ hệ thống nhận dạng ký
tự quang học), nhằm số hoá các trang tài liệu giấy nhƣ sách, báo, tạp chí…
Cho đến nay, bài toán phân tích và nhận dạng ảnh tài liệu đã đƣợc giải quyết
gần nhƣ trọn vẹn và cũng đã có những sản phẩm thƣơng mại, nhƣ VnDOCR
của Viện công nghệ thông tin hay FineReader của hãng ABBYY…
Bên cạnh lớp bài toán phân tích và nhận dạng ảnh tài liệu một cách
tổng quát ở trên còn có lớp bài toán riêng biệt cho từng ngành, từng lĩnh vực
cụ thể, nhƣ: phân tích và nhận dạng bảng biểu, phiếu điều tra, mẫu điền
thông tin, danh thiếp, hộ chiếu,… Đối với lớp bài toán này thì việc phân tích
cấu trúc của ảnh tài liệu là đặc biệt quan trọng, bởi vì nó sẽ quyết định đến
việc tách và nhận dạng chính xác các trƣờng thông tin cần thiết cho từng ứng
dụng cụ thể.
Trên thế giới đã có nhiều sản phẩm phần mềm phân tích và nhận dạng
ảnh thẻ chứa thông tin cá nhân (nhƣ hộ chiếu, danh thiếp…) và đƣợc ứng
dụng trong nhiều lĩnh vực, nhƣ: làm thủ tục hải quan, các giao dịch ở các cửa
2

Số hóa bởi Trung tâm Học liệu


phân tích ảnh CMND trong thực tế.
4. Bố cục của luận văn.
Các nội dung trình bày trong luận văn đƣợc chia thành 3 chƣơng.
Chƣơng 1 giới thiệu các vấn đề tổng quan nhận dạng văn bản và bài toán
phân tích cấu trúc trang ảnh tài liệu. Chƣơng 2 tập trung vào các kỹ thuật
phân tích cấu trúc, ứng dụng trong phát hiện và bóc tách các trƣờng thông tin
cần nhận dạng trên ảnh tài liệu (ảnh CMND).Chƣơng 3 trình bày quá trình
phân tích, thiết kế và cài đặt chƣơng trình thử nghiệm nhằm đánh giá hiệu quả
của phƣơng pháp trên các tập dữ liệu ảnh CMND đầu vào đƣợc thu thập từ
thực tế. 4

Số hóa bởi Trung tâm Học liệu

CHƢƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG VĂN BẢN VÀ
BÀI TOÁN PHÂN TÍCH CẤU TRÚC
Ngày nay, việc sử dụng máy tính để lƣu trữ tài liệu không còn là vấn đề
mới mẻ và cần phải chứng minh tính an toàn, thuận tiện của nó. Tuy nhiên
việc sử dụng giấy để lƣu trữ tài liệu trong một số mục đích vẫn chƣa thể thay
thế đƣợc nhƣ sách báo, công văn Hơn nữa, lƣợng tài liệu đƣợc tạo ra từ
nhiều năm trƣớc vẫn còn rất nhiều mà không thể bỏ đi đƣợc vì tính quan
trọng của chúng.
Chúng ta mong muốn có thể điện tử hóa hàng tỉ trang tài liệu đó và cất
chúng chỉ trong một thiết bị lƣu trữ với kích thƣớc bằng một cuốn sách nhỏ,
tìm kiếm các thông tin mà chỉ cần tốn vài giây với một lần gõ phím Enter.
Vậy giải pháp là gì?
Thông thƣờng ngƣời ta sẽ phải thuê ngƣời cùng với việc tốn hàng tháng,
hàng năm mới có thể nhập vào máy tính đƣợc hết lƣợng tài liệu đó. Hiện nay

hồ sơ lao động, tự động kiểm tra, xác nhận chữ ký trong ngân hàng, tự
động xử lý các hóa đơn hay các yêu cầu thanh toán, nhập liệu tự động,
kiểm tra thông tin trên passport…

Hình 1. 1. Thu nhận ảnh tài liệu
6

Số hóa bởi Trung tâm Học liệu

Trang ảnh tài liệu đƣợc đề cập ở đây là các file ảnh số hoá thu đƣợc bằng
cách quét các trang tài liệu dùng máy scanner, máy ảnh số, hay nhận từ một
máy fax, file ảnh này đƣợc lƣu trữ trong máy tính (Hình 1. 1). Ảnh tài liệu có
nhiều loại: ảnh đen trắng, ảnh màu, ảnh đa cấp xám với các phần mở rộng nhƣ
TIF, BMP, PCX… và ảnh tài liệu đƣợc đƣa ra trong luận văn này là ảnh đa
cấp xám.
Quy trình chung của một hệ thống nhận dạng văn bản đƣợc thể hiện cụ
thể trên Hình 1. 2. Ảnh tài liệu cần nhận dạng trƣớc tiên sẽ đƣợc tiền xử lý
nhằm tăng cƣờng chất lƣợng, căn chỉnh độ nghiêng, nắnchỉnh hình ảnh. Sau
đó sẽ tiến hành phân tích nhằm xác định cấu trúc trang tài liệu đồng thời xác
định đƣợc các vùng thông tin cần nhận dạng trên ảnh đầu vào. Bƣớc tiếp theo
sẽ tiến hành nhận dạng các vùng thông tin văn bản đã đƣợc xác định. Bƣớc
hậu xử lý cuối cùng sẽ thực hiện các thao tác kiểm lỗi chính tả và địnhdạng lại
cấu trúc trang văn bản.

Hình 1. 2. Quy trình chung của một hệ thống OCR
7

Số hóa bởi Trung tâm Học liệu

Từ quy trình của hệ thống nhận dạng trênHình 1. 2 cho thấy bƣớc phân

cho bƣớc nhận dạng sau này. Việc đánh giá hiệu quả của các thuật toán phân
tích trang đƣợc tiến hành dựa trên các file ground truth (chứa thông tin chi tiết
của các vùng thông tin cần xác định) cho trƣớc.
Hình 1.4. Quy trình phân tích cấu trúc trang ảnh
Cấu trúc tài liệu thu đƣợc từ việc liên tiếp chia nhỏ nội dung của tài liệu
thành các phần đơn vị nhỏ (tức là không thể phân chia đƣợc nữa) và chúng
đƣợc gọi là các đối tƣợng cơ sở (basic objects). Còn tất cả các đối tƣợng khác
đƣợc gọi là các đối tƣợng hỗn hợp.Hai loại cấu trúc của tài liệu đƣợc quan
tâm ở đây đó là cấu trúc vật lý (hay bố cục vật lý) và cấu trúc logic mô tả mối
quan hệ logic giữa các vùng đối tƣợng trong tài liệu.
9

Số hóa bởi Trung tâm Học liệu

 Bố cục vật lý:
Bố cục vật lý của một tài liệu mô tả vị trí và các đƣờng danh giới giữa
các vùng có nội dung khác nhau trong một trang tài liệu. Quá trình phân tích
bố cục tài liệu là thực hiện việc tách từ một trang tài liệu ban đầu thành các
vùng có nội dung cơ sở nhƣ hình ảnh nền, vùng văn bản. Để mô tả bố cục vật
lý của tài liệu ngƣời ta sử dụng một cấu trúc hình học với mỗi đối tƣợng trong
cấu trúc là một phần tử chỉ chứa nội dung đồng nhất. Các kiểu đối tƣợng hình
học đƣợc định nghĩa nhƣ sau:
 Block:Là đối tƣợng cơ sở tƣơng ứng với một vùng hình chữ nhật chứa
một phần nội dụng của tài liệu.
 Frame:Một đối tƣợng hỗn hợp tƣơng ứng với một hình chữ nhật bao
gồm một hoặc nhiều Block hoặc bao gồm nhiều các Frame.
 Page:Là đối tƣợng hình học hoặc hỗn hợp các thành phần cơ sở tƣơng
ứng với một vùng hình chữ nhật, nếu là đối tƣợng hỗn hợp nó chứa một
hoặc nhiều Block, một hoặc nhiều Frame.
 Page set(tập trang):Là một tập của một hoặc nhiều page.

màu nhận vào sẽ đƣợc chuyển thành ảnh xám với các mức xám có giá trị từ 0
đến 255 dựa trên ba giá trị RED, GREEN, BLUE của ảnh đầu vào. Từ ảnh
xám này, chúng ta sẽ so sánh mức xám của từng điểm với một ngƣỡng cho
Hình 1. 5.b- Cấu trúc vật lý; c,d - Cấu trúc logic của một tài liệu
11

Số hóa bởi Trung tâm Học liệu

trƣớc để quyết định điểm đó sẽ là 0 hoặc 255, giá trị 0 biểu diễn cho màu đen
và 255 biểu diễn cho màu trắng.
Nhị phân ảnh (hay còn gọi là phân ngƣỡng) là thao tác chuyển từ ảnh
màu, ảnh đa cấp xám về ảnh nhị phân bằng cách tìm một ngƣỡng: tổng quát
hoặc cục bộ. Kỹ thuật này đặt ngƣỡng để hiển thị các tông màu liên tục. Các
điểm trong ảnh đƣợc so sánh với ngƣỡng định trƣớc. Giá trị của ngƣỡng sẽ
quyết định điểm có đƣợc hiển thị hay không. Do vậy ảnh kết quả sẽ mất đi
một số chi tiết. Có nhiều kỹ thuật chọn ngƣỡng áp dụng cho các đối tƣợng
khác nhau:
Hiển thị 2 màu: Chỉ dùng ảnh đen trắng có 256 mức xám. Bản chất của
phƣơng pháp này là chọn ngƣỡng dựa trên lƣợc đồ mức xám của ảnh. Để đơn
giản có thể lấy ngƣỡng với giá trị là 127. Nhƣ vậy:

Trong đó u(m, n) là mức xám tại tọa độ i(m, n).
Nhìn chung kĩ thuật này khó chấp nhận vì ảnh mất khá nhiều chi tiết.
Hiển thị 4 màu: Hiện 4 màu để khắc phục nhƣợc điểm của kỹ thuật hiển
thị 2 màu. Một ví dụ của bảng mã 4 màu đƣợc cho ở Bảng 1. 1.
Mã màu
Màn hình monochrome
(đơn sắc)
Màn hình màu
0

entropy lai (giữa ảnh gốc và ảnh nhị phân) hay độ đo entropy mờ.
4. Các phƣơng pháp dựa vào thuộc tính giống nhau (Thresholding
Based on Attribute Similarity). Ngƣỡng đƣợc xác định dựa độ đo các thuộc
tính giống nhau của ảnh gốc và ảnh nhị phân, chẳng hạn nhƣ căn cứ vào
các cạnh thỏa mãn, độ chặt của hình dáng, momen mức xám, khả năng liên
kết, kết cấu…
5. Các phƣơng pháp căn cứ vào không gian (Spatial Thresholding
Methods). Sử dụng sự tƣơng liên hoặc/và phân phối thống kê bậc cao giữa
các pixel để chọn ngƣỡng.
6. Các phƣơng pháp ngƣỡng thích ứng cục bộ (Locally Adaptive
Thresholding). Kỹ thuật này sẽ xác định ngƣỡng t(x,y) cho từng điểm ảnh
(x,y) riêng biệt căn cứ vào mối tƣơng quan giữa điểm ảnh đó và các láng
giềng của nó.
13

Số hóa bởi Trung tâm Học liệu

1.2.2.2. Căn chỉnh độ nghiêng trang ảnh
Trong quá trình thu thập ảnh tài liệu, ảnh có thể bị nghiêng do đó cần
phải căn chỉnh độ nghiêng của ảnh bằng các xác định góc nghiêng và
xoay ảnh trở lại nhƣ ảnh gốc. Các bƣớc chỉnh độ nghiêng của ảnh đƣợc
mô tả nhƣ sau:
Thuật toán 1. 1. Thuật toán chỉnh độ nghiêng
Input: Ảnh (nhị phân) bị nghiêng
Output: Ảnh đã chỉnh độ nghiêng
1. Xác định góc nghiêng
2. Xoay ảnh với góc nghiêng
Trong đó, xác định góc nghiêng là thao tác quan trọng nhất và cũng là
thao tác khó khăn nhất. Có nhiều phƣơng pháp khác nhau để xác định góc
nghiêng: Có thể trực tiếp dựa vào các thống kê, đánh giá góc nghiêng của các