BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
======

NGUYỄN ĐỨC TOÀN

NGHIÊN CỨU PHƢƠNG PHÁP PHÂN ĐOẠN ẢNH
VÀ ỨNG DỤNG CHO ẢNH TÀI LIỆU

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ MÁY TÍNH
Ngƣời hƣớng dẫn khoa học: PGS. TS. NGÔ QUỐC TẠO

HÀ NỘI, 2015


1

LỜI CẢM ƠN
Trong thời gian thực hiện luận văn thạc sỹ em đã nhận được rất nhiều
sự khích lệ, động viên, giúp đỡ từ phía thầy cô, cha mẹ và bạn bè xung quanh.
Em xin bày tỏ lòng biết ơn chân thành nhất tới thầy giáo, PGS.TS Ngô
Quốc Tạo, người đã trực tiếp hướng dẫn em hoàn thành luận văn thạc sỹ này.
Cảm ơn đề tài: “ Hệ thống đeo tay hỗ trợ đọc sách tiếng Việt dành cho
người khiếm thị” Mã số VAST01.07/15-16 hỗ trợ trong thực hiện luận văn.
Em xin gửi lời cảm ơn chân thành tới các thầy cô trong trường Đại học
Sư phạm Hà Nội 2.
Em đã cố gắng học tập và hoàn thành luận văn thạc sỹ nhưng có thể
luận văn thạc sỹ vẫn còn thiếu sót. Em rất mong nhận được sự góp ý, chỉ bảo

1.1. Xử lý ảnh, các vấn đề cơ bản trong xử lý ảnh. .................................. 11
1.2. Quá trình xử lý ảnh .............................................................................. 11
1.2.1. Thu nhận ảnh (Image Acquisition) ............................................................13
1.2.2. Tiền xử lý (Image Processing) .....................................................................14
1.2.3. Phân đoạn (Segmentation) hay phân vùng ảnh .......................................14
1.2.4. Biểu diễn ảnh (Image Representation) ......................................................15
1.2.5. Nhận dạng và nội suy ảnh (Image Recognition and Interpretation)....15
1.2.6. Cơ sở tri thức (Knowledge Base) ................................................................16
1.2.7. Mô tả ảnh ........................................................................................... 16
1.3. Phân đoạn ảnh ..................................................................................... 19
1.3.1. Điểm ảnh (Picture Element) ........................................................................19
1.3.2. Độ phân giải của ảnh ....................................................................................20
1.3.3. Mức xám của ảnh ..........................................................................................20
1.3.4. Quan hệ giữa các điểm ảnh .........................................................................21
1.3.4.1. Các lân cận của điểm ảnh (Image Neighbors) ............................. 21
1.3.4.2. Khoảng cách giữa các điểm ảnh ................................................... 22
1.3.4.3. Các thành phần cơ bản của hệ thống xử lý ảnh .......................... 24
1.3.5. Những vấn đề khác trong xử lý ảnh ................................................ 25


4

1.3.5.1. Biến đổi ảnh (Image Transform) ...............................................................25
1.3.5.2. Nén ảnh .........................................................................................................25
1.3.5.3. Các định dạng cơ bản trong xử lý ảnh........................................... 26
CHƢƠNG 2: PHƢƠNG PHÁP PHÂN ĐOẠN ẢNH .............................. 27
Trộn các vùng ............................................................................................................38
2.1. Phƣơng pháp phân đoạn ảnh dựa trên miền đồng nhất. ................ 47
2.1.1. Phƣơng pháp tách cây tứ phân ........................................................ 48
2.1.2. Phƣơng pháp cục bộ ......................................................................... 50

KẾT LUẬN VÀ KIẾN NGHỊ .................................................................... 86
TÀI LIỆU THAM KHẢO .......................................................................... 87


6

DANH MỤC BẢNG
Hình 2.1 Các phương pháp phân đoạn ảnh ................................................... 28
Bảng 2.2.Ưu nhược điểm của các phương pháp phân v ng ......................... 28
Bảng 2.3 Bảng tra màu .................................................................................. 33
Bảng 2.3 Biểu đồ tần xuất histogram của ảnh I ............................................ 61
Bảng 2.4 : Định nghĩa thành phần liên thông ............................................... 72
Bảng 2.5. Ảnh nhị phân và nhãn của các thành phần ................................... 72
Bảng 2.6. Cấu trúc Union - Find với hai tập nhãn ........................................ 73
Bảng 2.7 Giả mã cho thủ tục Find ................................................................ 74
Bảng 2.8 : Giả mã cho thủ tục Union ............................................................ 74
Bảng 2.9. Giả mã thuật toán và gán nhãn cho các thành phần liên thông .... 76
Bảng 2.10 Ứng dụng thuật toán gán nhãn cho các thành phần liên thông .. 78


7

DANH MỤC HÌNH
Hình 2.1 Các phương pháp phân đoạn ảnh ................................................... 28
Bảng 2.2.Ưu nhược điểm của các phương pháp phân v ng ......................... 28
Bảng 2.3 Bảng tra màu .................................................................................. 33
Bảng 2.3 Biểu đồ tần xuất histogram của ảnh I ............................................ 61
Bảng 2.4 : Định nghĩa thành phần liên thông ............................................... 72
Bảng 2.5. Ảnh nhị phân và nhãn của các thành phần ................................... 72
Bảng 2.6. Cấu trúc Union - Find với hai tập nhãn ........................................ 73


3. Nhiệm vụ nghiên cứu
Tìm hiểu khái niệm phân đoạn ảnh.
Các phương pháp phân đoạn ảnh.
Ứng dụng phương pháp phân đoạn cho ảnh tài liệu.


9

4. Đối tƣợng và phạm vi nghiên cứu
Đối tượng, phạm vi nghiên cứu về tổng quan về phân đoạn ảnh, các
phương pháp phân đoạn ảnh và chọn ra phương pháp phân đoạn cho ảnh cụ
thể và các ứng dụng thực tế phân đoạn cho ảnh tài liệu.

5. Phƣơng pháp nghiên cứu
Thu thập tài liệu, phân tích, suy luận, tổng hợp, đánh giá. Từ đó đề xuất
nghiên cứu và tìm hiểu: “Nghiên cứu phương pháp phân đoạn ảnh và ứng
dụng cho ảnh tài liệu”.


10

NỘI DUNG
Chƣơng 1: Khái niệm về phân đoạn ảnh
1.1 Xử lý ảnh, các vấn đề cơ bản trong xử lý ảnh.
1.2 Quá trình xử lý ảnh.
1.3 Phân đoạn ảnh.
Chƣơng 2: Phƣơng pháp phân đoạn ảnh
2.1 Phương pháp phân đoạn ảnh dựa trên miền đồng nhất.
2.2 Phương pháp phân đoạn ảnh dựa trên LBP (Local Binary Pattern)

nạn giao thông phác họa hiện trường tai nạn…
1.2. Quá trình xử lý ảnh
Xử lý ảnh là một lĩnh vực mang tính khoa học và công nghệ, là một
ngành khoa học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ phát
triển rất nhanh, kích thích các trung tâm nghiên cứu, ứng dụng, đ c biệt là
máy tính chuyên dụng riêng.


12

Xử lý ảnh liên quan đến nhiều lĩnh vực và cần nhiều kiến thức cơ sở
khác. Đầu tiên phải kể đến Xử lý tín hiệu số là một môn học hết sức cơ bản
cho xử lý tín hiệu chung, các khái niệm về tích chập, các biến đổi Fourier,
biến đổi Laplace, các bộ lọc hữu hạn… Thứ hai, các công cụ toán như Đại số
tuyến tính, Xác xuất, thống kê. Một số kiến thứ cần thiết như Trí tuệ nhân tao,
Mạng nơron nhân tạo c ng được đề cập trong quá trình phân tích và nhận
dạng ảnh. Các phương pháp xử lý ảnh bắt đầu từ các ứng dụng chính: nâng
cao chất lượng ảnh và phân tích ảnh.
Ứng dụng đầu tiên được biết đến là nâng cao chất lượng ảnh báo được
truyền qua cáp từ Luân Đôn đến New York từ những năm 1920. Vấn đề nâng
cao chất lượng ảnh có liên quan tới phân bố mức sáng và độ phân giải của
ảnh. Việc nâng cao chất lượng ảnh được phát triển vào khoảng những năm
1955. Điều này có thể giải thích được vì sau thế chiến thứ hai, máy tính phát
triển nhanh tạo điều kiện cho quá trình xử lý ảnh sô thuận lợi. Năm 1964, máy
tính đã có khả năng xử lý và nâng cao chất lượng ảnh từ m t trăng và vệ tinh
Ranger 7 của Mỹ bao gồm: làm nổi đường biên, lưu ảnh. Từ năm 1964 đến
nay, các phương tiện xử lý, nâng cao chất lượng, nhận dạng ảnh phát triển
không ngừng.
Các phương pháp tri thức nhân tạo như mạng nơron nhân tạo, các thuật
toán xử lý hiện đại và cải tiến, các công cụ nén ảnh ngày càng được áp dụng

camera là ảnh tương tự (loại camera ống chuẩn CCIR với tần số 1/25, mỗi ảnh
25 dòng), c ng có loại camera đã số hoá (như loại CCD - Change Coupled
Device) là loại photodiot tạo cường độ sáng tại mỗi điểm ảnh. Camera thường


14

d ng là loại quét dòng ; ảnh tạo ra có dạng hai chiều. Chất lượng một ảnh thu
nhận được phụ thuộc vào thiết bị thu, vào môi trường (ánh sáng, phong cảnh).
1.2.2. Tiền xử lý (Image Processing)
Sau bộ thu nhận, ảnh có thể nhiễu độ tương phản thấp nên cần đưa vào
bộ tiền xử lý để nâng cao chất lượng. Chức năng chính của bộ tiền xử lý là lọc
nhiễu, nâng độ tương phản để làm ảnh rõ hơn, nét hơn.
Mục đích của các công việc này là làm cho chất lượng ảnh trở lên tốt
hơn chuẩn bị cho các bước xử lý tiếp theo.
Khử nhiễu: Nhiễu được chia thành hai loại là nhiễu hệ thống và nhiễu
ngẫu nhiên. Đ 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 hệ thống b ng việc sử dụng phép biến đổi Fourie 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 thì có thể khử b ng phương pháp nội
suy, lọc trung vị và lọc trung bình.
Chỉnh độ tƣơng phản: Công việc cụ thể là 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.
1.2.3. Phân đoạn (Segmentation) hay phân vùng ảnh
Phân v ng ảnh là tách một ảnh đầu vào thành các v ng thành phần để
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 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

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ó.
Trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết.
1.2.5. Nhận dạng và nội suy ảnh (Image Recognition and Interpretation)
Nhận dạng ảnh là quá trình xác định ảnh b ng cách so sánh ảnh với
mẫu chuẩn đã được lưu từ trước.


16

Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng ảnh.
Ví dụ: một loạt chữ số và nét gạch ngang trên phong bì thư có thể 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 sau:
- 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.2.6. Cơ sở tri thức (Knowledge Base)
Ả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, nhiễu do môi trường thu ảnh phong phú. Trong nhiều khâu
xử lý và phân tích ảnh, ngoài việc đơn giản hoá các phương pháp toán học
đảm bảo tiện lợi cho xử lý thì chúng ta luôn hướng đến việc xây dựng hệ
thống tự động tiếp nhận và xử lý theo cách của con người. Vì vậy, nhiều khâu
hiện nay đã được xử lý theo các phương pháp trí tuệ nhân tạo, sử dụng cơ sở
tri thức của con người.
1.2.7. Mô tả ảnh
Từ Hình 1.1, ảnh sau khi số hoá sẽ được lưu vào bộ nhớ, ho c chuyển

- Biểu diễn bằng mã tứ phân
Phương pháp mã tứ phân được d ng để mã hoá cho v ng ảnh. V ng ảnh
đầu tiên được chia làm bốn phần thường là b ng nhau. Nếu mỗi v ng đã đồng
nhất (chứa toàn điểm đen (1) hay trắng (0)) thì gán cho v ng đó một mã và
không chia tiếp. Các v ng không đồng nhất được chia tiếp làm bốn phần theo
thủ tục trên cho đến khi tất cả các v ng đều đồng nhất. Các mã phân chia
thành các v ng con tạo thành một cây phân chia các v ng đồng nhất.


18

Trên đây là các thành phần cơ bản trong các khâu xử lý ảnh. Trong thực
tế, các quá trình sử dụng ảnh số không nhất thiết phải qua hết các khâu đó t y
theo đ c điểm ứng dụng. Hình 1.2 cho sơ đồ phân tích và xử lý ảnh và lưu đồ
thông tin giữa các khối một cách khá đầy đủ. Ảnh sau khi được số hóa được
nén, lưu lại để truyền cho các hệ thống khác sử dụng ho c để xử lý tiếp theo.
M t khác, ảnh sau khi số hóa có thể bỏ qua công đoạn nâng cao chất lượng
(khi ảnh đủ chất lượng theo một yêu cầu nào đó) để chuyển tới khâu phân
đoạn ho c bỏ tiếp khâu phân đoạn chuyển trực tiếp tới khâu trích chọn đ c
trưng. Hình 1.2 c ng chia các nhánh song song như: nâng cao chất lượng ảnh
có hai nhánh phân biệt: nâng cao chất lượng ảnh (tăng độ sáng, độ tương
phản, lọc nhiễu) ho c khôi phục ảnh (hồi phục lại ảnh thật khi ảnh nhận được
bị méo) v.v…

Cảnh
quan
(Scenne)

Thu
ảnh

trưng

Phân
đoạn
Khôi
phục
ảnh

Phân
Tích
Thống
Kê/
cấu
trúc

Trích
chọn
quan
hệ

Hình 1.2 Sơ đồ phân tích và xử lý ảnh và lưu đồ thông tin giữa các khối

Mô
tả
và
Nội
suy


19

20

và mức xám (ho c màu) của ảnh số gần như ảnh thật. Mỗi phần tử trong ma
trận được gọi là một phần tử ảnh.
1.3.2. Độ phân giải của ảnh
Định nghĩa
Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn định
trên một ảnh số được hiển thị.
Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao
cho mắt người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách
thích hợp tạo nên một mật độ phân bổ, đó chính là độ phân giải và được phân
bố theo trục x, y trong không gian hai chiều.
Ví dụ: Độ phân giải của màn hình CGA (Color Graphic Adaptor) là
một lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc * 200 điểm
ảnh (320*200). C ng loại màn hình CGA và ở c ng độ phân giải 320*200, ta
sẽ thấy màn hình CGA 12‟‟ mịn hơn màn hình CGA 17‟‟. Lý do chính là ở
c ng một độ phân giải nhưng diện tích màn hình rộng hơn thì độ mịn hay tính
liên tục của các điểm ảnh sẽ thấp hơn
1.3.3. Mức xám của ảnh
Mức xám của điểm ảnh là cường độ sáng của nó được gán b ng giá trị
số tại điểm đó.
Các giá trị mức xám thông thường như: 16, 32, 64, 128, 256. Trong đó,
mức 256 là mức phổ dụng cho các máy tính ngày nay do máy tính d ng 1
byte (8 bit) để biểu diễn mức xám nên sẽ có 28=256 mức.
Ảnh đen trắng: là ảnh có hai màu đen trắng với mức xám ở các điểm
ảnh có thể khác nhau.
Ảnh nhị phân: là ảnh chỉ có 2 mức đen trắng phân biệt d ng 1 bit mô
tả 2 mức khác nhau. Như vậy, mỗi điểm ảnh của ảnh nhị phân chỉ có thể là 0
ho c 1.


tọa độ (s,t) là hàm khoảng cách (Distance) nếu:
1. D(p,q) ≥ 0 (Với D(p,q)=0 nếu và chỉ nếu p≡q)
2. D(p,q) = D(q,p)
3. D(p,z) ≤ D(p,q) + D(q,z); z là một điểm ảnh khác.
Khoảng cách Euclide: Khoảng cách Euclide giữa hai điểm ảnh p(x,y)
và q(s,t) được định nghĩa như sau:
De(p,q) = (x - s)2  (y - t)2
Khoảng cách Euclide giữa hai điểm p và q là chiều dài đoạn thẳng

.

Trong hệ tọa độ Descartes, nếu p = (p1, p2,..., pn) và q = (q1, q2,..., qn) là hai
điểm trong không gian Euclidn chiều, thì khoảng cách từ p đến q b ng:

Dạng chuẩn Euclid là khoảng cách của một điểm đến điểm gốc trong không
gian Euclid:

trong đó phương trình sau cùng là tích vô hướng. Đây là chiều dài của p, khi
ta xem nó là một Véc-tơ Euclid có gốc n m ở gốc tọa độ. Khoảng cách khi đó
b ng


23

Khoảng cách khối: Khoảng cách D4(p,q) được gọi là khoảng cách
khối đồ thị (City – Block Distance) và được xác định như sau:
D4(p,q) = | x-s| + |y-t|
Giá trị khoảng cách giữa các điểm ảnh r: giá trị bán kính r giữa điểm
ảnh từ tâm điểm ảnh đến tâm điểm ảnh q khác. Ví dụ: màn hình CGA 12”
(12”*2,54cm=30,48cm=304,8mm) độ phân giải 320*200; tỷ lệ 4/3 (Chiều

là
.

Do mọi mã đều là đơn ánh, khoảng cách nhỏ nhất luôn lớn hơn ho c
b ng .
Khoảng cách lớn hơn cho phép phát hiện và sửa nhiều lỗi hơn. Chẳng hạn,
nếu ta chỉ xét trường hợp lỗi làm thay đổi kí tự trong mã tự gửi đi nhưng
không thêm hay xóa bớt kí tự thì số lỗi chính là số vị trí khác nhau giữa
khối gửi đi và khối nhận được. Một mã với khoảng cách
hiện

lỗi vì sau khi thay đổi không quá

cho phép phát

vị trí của một mã tự, ta

không thể thu được một mã tự mới. Ngoài ra, nếu chỉ có không


24

lỗi, người nhận có thể sửa lỗi và tìm ra mã tự gửi đi. Đó là

quá

vì trong khoảng cách

từ khối tự nhận được chỉ có đúng một mã