ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ ĐỨC HIẾU ỨNG DỤNG MỘT SỐ KỸ THUẬT XỬ LÝ ẢNH TRONG
PHÂN TÍCH CHỨNG MINH THƯ NHÂN DÂN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2012
-4-
Mục lục
Lời cam đoan 2
Lời cảm ơn 3
Mục lục 4
Danh mục hình vẽ 6
Danh mục bảng biểu 8
Danh mục thuật toán 9
Mở đầu 10
Chương 1: Tổng quan về phân tích ảnh tài liệu 12
1.1. Tổng quan về hệ thống nhận dạng ảnh tài liệu 12
1.2. Phân tích ảnh tài liệu 13
1.2.1. Bố cục tự nhiên và cấu trúc lôgic 14
1.2.2. Phân loại ảnh tài liệu 15
1.3. Phân tích bố cục 16
1.3.1. Hướng tiếp cận trên-xuống 17
1.3.2. Hướng tiếp cận dưới-lên 18
1.4. Phân tích cấu trúc 19
1.5. Kết luận chương 20
Chương 2: Một số thuật toán tiền xử lý ảnh 21
2.1. Nhị phân ảnh 21
2.1.1. Phân loại các phương pháp xác định ngưỡng T 23
2.1.2. Một số phương pháp xác định ngưỡng T 23
2.1.3. Nhận xét 26
2.2. Hiệu chỉnh độ nghiêng của trang văn bản 28
2.2.1. Phương pháp dựa trên biến đổi Hough 29
2.2.2. Phương pháp láng giềng gần nhất (nearest neighbours) 31
2.2.3. Phương pháp sử dụng chiếu nghiêng (project profile) 33
2.2.4. Nhận xét 34
2.3. Các toán tử hình thái (Morphological operations) 34

Hình 1. 6 Thuật toán whitespace 18
Hình 1. 7 Thuật toán Docstrum 19
Hình 1. 8 Thuật toán Voronoi 20
Hình 2. 1 Nhị phân ảnh 22
Hình 2. 2 So sánh các phương pháp nhị phân ảnh đối với có độ sáng thay đổi 27
Hình 2. 3 So sánh các phương pháp nhị phân ảnh đối với ảnh Chứng minh nhân dân 28
Hình 2. 4 Biến đổ Hough 30
Hình 2. 5 Phương pháp láng giếng gần nhất 32
Hình 2. 6 Phương pháp chiếu nghiêng 33
Hình 2. 7 Phần tử cấu trúc 3x3 34
Hình 2. 8 Phép giãn ảnh với phần tử cấu trúc 3x3 35
Hình 2. 9 Phép co ảnh với phần tử cấu trúc 3x3 36
Hình 2. 10 Phép toán opening 36
Hình 2. 11 Phép toán closing 37
Hinh 3. 1 Mẫu “Giấy Chứng minh nhân dân” 38
Hinh 3. 2 Vùng thông tin cần tách ở mặt trước CMND 39
Hinh 3. 3 Tiền xử lý ảnh mặt trước CMND 41
Hinh 3. 4 Xác định vùng Số CMND 44
Hinh 3. 5 Phân đoạn vùng Số CMND 45
Hinh 3. 6 Mặt nạ dòng mặt trước 47
Hinh 3. 7 Xoá phần tiêu đề 49
Hinh 3. 8 Kết quả lấy lại các ký tự bị mất 50
Hinh 3. 9 Các vùng thông tin cần tách ở mặt sau 51
Hinh 3. 10 Tiền xử lý mặt sau CMND 52
-7-
Hinh 3. 11 Xác định cấu trúc bảng 53
Hình 4. 1 So khớp khối đúng và khối tách được 56
Hình 4. 2 Trường hợp tách bị lỗi 57

-8-

đế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 hàng, khách sạn,… Ở Việt
Nam loại thẻ chứa thông tin các nhân được sử dụng nhiểu nhất là Giấy chứng minh
nhân dân (CMND), nhưng hiện nay chưa có một giải pháp nào được đưa ra cho việc
phân tích và nhận dạng CMND. Do đó, trong luận văn này, tôi xin đề xuất một phương
pháp phân tích ảnh CMND dựa trên việc phân tích và nhận dạng biểu mẫu. Luận văn
gồm bốn chương với các nội dung như sau:
Chương 1: Tổng quan về phân tích ảnh tài liệu. Giới thiệu tổng quan về hệ thống
nhận dạng ảnh tài liệu nói chung và hệ thống phân tích ảnh tài liệu nói riêng. Giới
thiệu các hướng tiếp cận trong phân tích bố cục và cấu trúc của ảnh tài liệu.
Chương 2: Một số thuật toán tiền xử lý ảnh. Giới thiệu một số thuật toán tiền xử lý
ảnh thường được áp dụng trong các hệ thống phân tích và nhận dạng ảnh tài liệu, như:
nhị phân ảnh, căn chỉnh độ nghiêng, các toán tử hình thái.
-11-
Chương 3: Phương pháp phân tích Giấy chứng minh nhân dân. Giới thiệu bài toán

trơn ảnh, căn chỉnh độ nghiêng của trang tài liệu…
 Phân tích ảnh: Là quá trình phân ly ảnh thành các vùng (văn bản, hình ảnh,
bảng biểu,…) và hiểu vai trò chức năng của mỗi vùng cũng như mối quan hệ của
nó với các vùng khác. Đây là một trong những công đoạn quan trọng nhất của
một hệ thống nhận dạng vì nó ảnh hưởng rất lớn đến kết quả nhận dạng.
 Nhận dạng: Đây là thao tác gán nhãn các đối tượng dựa trên các tri thức đã được
học, hay nói cách khác là việc tìm một lớp mẫu phù hợp nhất với đối tượng đầu
vào.
 Hậu xử lý: Bao gồm các công việc như: ghép các ký tự đã được nhận dạng thành
các từ, các câu, các đoạn nhằm khôi phục lại văn bản như ban đầu, đồng thời
phát hiện các lỗi nhận dạng bằng việc kiểm tra chính tả dựa trên cấu trúc và ngữ
nghĩa của câu, đoạn văn.
 Lưu văn bản: Sau khi đã tái tạo được nguyên bản của tài liệu, cần lưu chúng ở
các định dạng file được hệ thống hỗ trợ (như: *.doc, *.docx, *.rtf,…).
1.2. Phân tích ảnh tài liệu
Một ảnh tài liệu bao gồm nhiều thành phần khác nhau như các khối văn bản, hình ảnh,
bảng biểu, sơ đồ, công thức,… và chúng có thể được gán cho các nhãn lôgic hay chức
năng khác nhau như nhan đề, tiêu đề, tên và địa chỉ tác giả,… Quá trình phân tích ảnh
tài liệu là việc cố gắng phân ly tài liệu thành các vùng và hiểu vai trò chức năng cũng
như mối quan hệ giữa các vùng [5].
Các ảnh tài liệu thường được tạo ra từ các tài liệu thực bởi quá trình số hoá sử dụng
máy quét hoặc máy ảnh kỹ thuật số. Nhiều tài liệu như báo, tạp chí, quảng cáo có bố
cục rất phức tạp do sự sắp đặt của hình ảnh, nhan đề và đầu đề, nền phức tạp, định
dạng văn bản có tính nghệ thuật,… (Hình 1. 2) Một người đọc sử dụng một loạt các
thông tin bổ xung như ngữ cảnh, quy ước và thông tin ngôn ngữ/kịch bản, cùng với
quá trình lý luận phức tạp để giải mã nội dung của tài liệu. Tự động phân tích một tài
liệu tuỳ ý với bố cục phức tạp là một nhiệm vụ vô cùng khó khăn và vượt ngoài khả
năng của các hệ thống phân tích bố cục và cấu trúc tài liệu tiên tiến. Bởi vì các tài liệu
này được thiết kế để hiệu quả và rõ ràng đối với sự phân tích của con người hơn các
ảnh có trong tự nhiên.

Hình 1. 3 Sơ đồ hệ thống phân tích bố cục và cấu trúc ảnh tài liệu
1.2.2. Phân loại ảnh tài liệu
Dựa trên mức độ phụ thuộc của tài liệu vào bố cục tự nhiên hay cấu trúc lôgic, người
ta chia làm 4 loại ảnh tài liệu (Hình 1. 4) [6]:
Loại 1: Quá phụ thuộc vào bố cục tự nhiên. Vị trí, độ dài của các trường dữ liệu là
được ấn định trước. Ví dụ như các biễu mẫu ứng dụng, ngân phiếu, danh sách câu
hỏi,…
Loại 2: Phụ thuộc vào cấu trúc lôgic hơn là bố cục tự nhiên. Cụ thể, vị trí của mỗi
trường có thể di chuyển lên/xuống hoặc sang trái/phải từ vị trí bình thường so với các
trường có liên quan hoặc các trường trước đó. Ví dụ như thẻ danh mục, thư từ, danh
thiếp.
Loại 3: Phụ thuộc vào bố cục tự nhiên như loại 1, nhưng cấu trúc phức tạp hơn (các
trường phân cấp hoặc lặp đi lặp lại) hoặc bố cục được hướng dẫn bởi các yếu tố khác
(ví dụ như các đoạn thẳng, các vùng trống,…). Vị trí, độ dài mỗi trường là gần như cố
định. Ví dụ như bảng biểu.
Loại 4: Vị trí và độ dài của các trường phụ thuộc vào mối quan hệ của các trường. Nói
chung, mặc dù cấu trúc chung của tài liệu là đã được định nghĩa trước bởi bố cục tự
Nhị phân
ảnh
Ảnh
tài liệu
Chỉnh
độ nghiêng
Xoá nhiễu
Phân tích
cấu trúc
Tài liệu
đã phân
đoạn
Phân tích

ngân phiếu,
danh sách câu hỏi,…
[Loại 1]
bảng biểu,…
[Loại 3]
thẻ danh mục,
thư từ,
danh thiếp,…
[Loại 2]
trang báo,
bài báo, …
[Loại 4]
Bố cục
tự nhiên
Cấu trúc lôgic
-17-
 Phân loại vùng: Là việc quyết định xem các vùng đã phân đoạn được thuộc loại
nào. Bài toán điển hình là phân loại các vùng vào khối văn bản hay hình ảnh và
nhận ra đâu là các đối tượng đồ hoạ, đâu là các bảng biểu. Phân loại vùng là điều
kiện kiên quyết để xử lý nhiều loại vùng, vì mỗi loại vùng thì có các đặc trưng
khác nhau nên cần các thuật toán khác nhau để xử lý.
Có rất nhiều thuật toán đã được đề xuất để thực hiện phân tích bố cục của ảnh tài liệu.
Bây giờ chúng ta sẽ xem xét một số thuật toán phổ biến để minh họa cho các hướng
tiếp cận ở trên.
1.3.1. Hướng tiếp cận trên-xuống

Hình 1. 5 Hình chiếu ngang và dọc của ảnh tài liệu
Một kỹ thuật cơ bản của hướng tiếp cận trên-xuống là sử dụng hình chiếu theo phương
ngang và dọc để chia ảnh tài liệu đầu vào thành các vùng nhỏ hơn. Ví dụ điển hình của
kỹ thuật này là thuật toán X-Y Cut [7], bắt đầu chia ảnh tài liệu thành các phần dựa vào

ngưỡng của góc giữa tâm các thành phần. Biểu đồ khoảng cách giữa các thành phần là
được sử dụng để xác định khoảng cách giữa các ký tự trong từ và giữa các từ. Khoảng
các giữa các thành phần liên thông trong dòng và giữa các dòng được tính toán để tạo
thành các dòng và các khối văn bản. Thuật toán có một tập các tham số được thiết lập
bởi các thí nghiệm trên một các tài liệu. Thuật toán thực hiện tốt với nhiều bố cục của
-19-
các văn bản tiếng Anh. Hình 1. 7 cho chúng ta thấy thuật toán xử lý tốt các phông chữ
với kích cỡ và kiểu khác nhau, và có bố cục tương đối phức tạp.

Hình 1. 7 Thuật toán Docstrum
Thuật toán dựa trên biển đồ Voronoi của Kise [12] là một phương pháp hiệu quả khác
bằng cách gom nhóm các thành phân liên thông trong một trang. Bắt đầu với việc tính
toán một lưới tổ ong Voronoi của ảnh tài liệu. Đồ thị láng giềng của các thành phần
liên thông là được tính toán từ sơ đồ Voronoi. Sau đó, thuật toán sử dụng một ngưỡng
dựa trên diện tích và khoảng cách giữa các thành phần liền kề trong biểu đồ Voronoi
để quyết định đường bao của vùng. Dòng văn bản được xác định dựa trên một ngưỡng
được tính toán từ khoảng các giữa các thành phần bên trong đồ thị láng giềng của nó.
Các kết quả thu được có độ chính xác cao và rất đáng tin cậy trên các tài liệu có nền
trắng, khi mà các thành phần liên thông được xác định một cách đáng tin cậy. Cũng
giống như Docstrum, thuật toán dựa trên Voronoi có thể xử lý các bố cục phức tạp và
thực hiện tốt trên hầu hết các văn bản bằng tiếng Anh (Hình 1. 8).
1.4. Phân tích cấu trúc
Cấu trúc lôgic của ảnh tài liệu là một ánh xạ từ các vùng tự nhiên trong tài liệu đến các
nhãn lôgic của chúng. Phân tích cấu trúc lôgic của ảnh tài liệu (sau đây gọi tách là
phân tích cấu trúc) là quá trình gán các nhãn lôgic cho các vùng tự nhiên đã xác định ở
bước phân tích bố cục. Các nhãn lôgic bao gồm tiêu đề, đoạn tóm tắt, tiêu đề con, đoạn
văn, câu, từ, đầu trang, cuối trang, chú thích, số trang,…
Một trong các hướng tiếp cận phổ biến để xác định cấu trúc lôgic của tài lại là coi tập
các vùng trong tài liệu như là một chuỗi các ký hiệu. Một ngữ pháp định nghĩa thông
qua các ký hiệu này để miêu tả cấu trúc lôgic của một tài liệu bất kỳ được xem xét.

-21-
Chương 2: Một số thuật toán tiền xử lý ảnh
Đầu vào của các hệ thống xử lý ảnh thường là các tệp ảnh được thu nhận từ các thiết bị
như: máy quét, máy ảnh, thiết bị ghi hình hay các thiết bị thu nhận hình ảnh khác. Các
ảnh này thường có chất lượng thấp (bị lẫn các nhiễu, mất các chi tiết của đối tượng,
hay bị lệch so với ảnh gốc một góc bất kỳ,…). Nguyên nhân là do: thiết bị thu nhận
không đảm bảo, điều kiện thu nhận không tốt (độ sáng thay đổi, thu nhận trong khi di
chuyển,…) hay quá trình sao lưu bị mất mát thông tin.
Để các bước xử lý tiếp theo thu được kết quả tốt cần phải có quá trình tiền xử lý để
nâng cao chất lượng ảnh đầu vào. Quá trình này bao gồm các công đoạn khôi phục và
tăng cường ảnh:
 Khôi phục ảnh nhằm mục đích loại bỏ hay giảm thiểu các ảnh hưởng của môi
trường tác động lên ảnh. Bao gồm các bước: lọc ảnh, khử nhiễu, xoay ảnh,…
nhằm giảm bớt các biến dạng của ảnh và đưa ảnh về trạng thái gần như ban đầu.
 Tăng cường ảnh không phải làm tăng lượng thông tin trong ảnh mà là làm nổi
bật các đặc trưng của ảnh giúp cho công việc phía sau được hiệu quả hơn. Công
đoạn này bao gồm các việc như: lọc độ tương phản, làm trơn ảnh, nhị phân
ảnh,…
Trong đó các thao tác nhị phân ảnh, căn chỉnh độ nghiêng và xóa nhiễu là các thao tác
cơ bản nhất và thường được áp dụng. Trong các phần tiếp theo của chương này sẽ
trình bầy một số thuật toán trong các thao tác đó.
2.1. Nhị phân ảnh
Ảnh nhận được từ các thiết bị thu nhận hình ảnh như máy ảnh hay camera thường là
ảnh mầu hay ảnh đa cấp xám, các thành phần trong ảnh là rất phức tạp (mầu sắc, kết
cấu…). Do đó muốn làm nổi bật các đặc trưng trong ảnh thì phải chuyển về dạng ảnh
nhị phân, ảnh chỉ có hai mầu (đen và trắng) – tương ứng với nền và tiền cảnh (đối
tượng “quan tâm”). Nhị phân ảnh (hay còn gọi là phân ngưỡng) là thao tác chuyển từ
ảnh đa cấp xám (hoặc ảnh mầu) về ảnh nhị phân (Thuật toán 2.1).
Thuật toán 2.1. Nhị phân ảnh
INPUT: Ảnh mầu hoặc ảnh đa cấp xám


Hình 2. 1 Nhị phân ảnh
Có rất nhiều phương pháp để xác định ngưỡng phân tách T. Ngưỡng T có thể được xác
định cho toàn bộ ảnh (ngưỡng tổng quát) hay được xác định cho mỗi điểm ảnh cụ thể
-23-
(ngưỡng cục bộ). Trong phần tiếp theo sẽ phân loại và giới thiệu một số phương pháp
xác định ngưỡng T.
2.1.1. Phân loại các phương pháp xác định ngưỡng T
Căn cứ vào phương pháp được áp dụng, có thể chia ra làm 6 nhóm sau [13]:
1. Các phương pháp dựa vào hình dạng của histogram (Histogram Shape-
Based Thresholding Methods). Căn cứ vào hình dáng của histogram như: các
đỉnh, các khe và độ cong (peaks, valleys and curvatures) để xác định ngưỡng. Vị
trí lấy ngưỡng có thể là khe lõm nhất giữa hai đỉnh hay điểm cách xa đường
thẳng nối hai đỉnh.
2. Các phương pháp dựa vào việc chia nhóm (Clustering-Based Thresholding
Methods). Các phương pháp loại này cố gắng chia ảnh ra làm hai nhóm tương
ứng với nền và đối tượng dựa trên một số tiêu trí đánh giá “khoảng cách” giữa
hai nhóm hay giữa các phần tử trong mỗi nhóm.
3. Các phương pháp dựa vào entropy (Entropy-Based Thresholding Methods).
Trong kỹ thuật này người ta chọn ngưỡng dựa vào entropy dựa trên một số cơ sở
như: cực đại các entropy (nền và đối tượng), cực tiểu các 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).






2
2
2
2
2
,
1
),(
w
x
w
xi
w
y
w
yj
jig
w
yxm

     
 




như sau [15]:
   
 












 1
,
1,,
R
yx
kyxmyxT


Trong đó: R là giá trị lớn nhất của độ lệch chuẩn (với ảnh đa cấp xám: R = 128), k là
tham số nằm trong khoảng [0.2, 0.5], m(x, y) và σ(x, y) là giá trị đáp ứng các mức
ngưỡng khác nhau tùy theo các điểm lân cận. Với một vài vùng ảnh có độ tương phản
cao thì σ(x, y) ≈ R, khi đó T(x, y) ≈ m(x, y). Kết quả này giống như phương pháp
-25-
Niblack. Trong trường hợp T(x, y) nhỏ hơn giá trị trung bình thì sẽ xóa đi một vài vùng
tối của nền. Tham số k dùng để điểu chỉnh giá trị ngưỡng so với giá trị trung bình m(x,

t
F
P

b. Tính trị số trung bình của nền
t
B

và tiền cảnh
t
F


c. Tính độ lệch chuẩn của nền
t
B

và tiền cảnh
t
F


d. Xác định hàm khảng cách:
t
classbetween
var
hoặc
t
classwithin
var

i
t
B
pP
0





1
1
1
L
ti
i
t
B
t
F
pPP

Giá trị trung bình của tiền cảnh và nền:








1
1
L
ti
i
t
F
t
F
pi
P


Độ lệch chuẩn của tiền cảnh và nền:
 












t
i
i

1
L
ti
i
t
F
t
F
t
F
pi
P


Từ đó ta xác định được khoảng cách giữa hai lớp và khảng cách của lớp trong như sau:
   
 
2
22
var
t
F
t
B
t
F
t
B
t
F

var

Trong đó:




1
0
L
i
i
pi

là giá trị trung bình của toàn ảnh.
Khi đó ngưỡng
Otsu
t
được xác định là đối số để hàm
t
classbetween
var
đạt giá trị lớn nhất
hoặc hàm
t
classwithin
var
đạt giá trị nhỏ nhất:
  
  