Giáo trình môn Xử lý ảnh | Đại học Thái Nguyên

Tài liệu gồm 76 trang, có 5 chương chính bao gồm các kiến thức cơ bản liên quan: Tổng quan về xử lý ảnh; Các kỹ thuật nâng cao chất lượng ảnh; Biên và các phương pháp phát hiện biên;...giúp bạn ôn luyện và nắm vững kiến thức môn học Xử lý ảnh Mời bạn đọc đón xem!

Môn:

Xử lý ảnh 2 tài liệu

Trường:

Đại học Thái Nguyên 164 tài liệu

Thông tin:
76 trang 1 năm trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Giáo trình môn Xử lý ảnh | Đại học Thái Nguyên

Tài liệu gồm 76 trang, có 5 chương chính bao gồm các kiến thức cơ bản liên quan: Tổng quan về xử lý ảnh; Các kỹ thuật nâng cao chất lượng ảnh; Biên và các phương pháp phát hiện biên;...giúp bạn ôn luyện và nắm vững kiến thức môn học Xử lý ảnh Mời bạn đọc đón xem!

199 100 lượt tải Tải xuống
1
ĐẠI HC THÁI NGUYÊN
KHOA CÔNG NGH THÔNG TIN
GIÁO TRÌNH MÔN HC
XNH
Người son : TS. ĐỖ NĂNG TOÀN,
TS. PHM VIT BÌNH
Thái Nguyên, Tháng 11 năm 2007
2
LI NÓI ĐẦU
Khong hơn mười năm tr li đây, phn cng máy tính và các thiết b
liên quan đã có s tiến b vượt bc v tc độ tính toán, dung lượng cha,
kh năng x lý v.v.. và giá c đã gim đến mc máy tính và các thiết b liên
quan đến xnh đã không còn là thiết b chuyên dng na. Khái nim
nh s đã tr nên thông dng vi hu h
ết mi người trong xã hi và vic
thu nhn nh s bng các thiết b cá nhân hay chuyên dng cùng vi vic
đưa vào máy tính xđã tr nên đơn gin.
Trong hoàn cnh đó, xnh là mt lĩnh vc đang được quan tâm và
đã tr thành môn hc chuyên ngành ca sinh viên ngành công ngh thông
tin trong nhiu trường đại hc trên c nước. Tuy nhiên, tài liu giáo trình
còn là mt điu khó khăn. Hin ti ch có m
t s ít tài liu bng tiếng Anh
hoc tiếng Pháp, tài liu bng tiếng Vit thì rt hiếm. Vi mong mun đóng
góp vào s nghip đào to và nghiên cu trong lĩnh vc này, chúng tôi biên
son cun giáo trình Xnh da trên đề cương môn hc đã được duyt.
Cun sách tp trung vào các vn đề cơ bn ca xnh nhm cung cp
mt nn t
ng kiến thc đầy đủ và chn lc nhm giúp người đọc có th t
tìm hiu và xây dng các chương trình ng dng liên quan đến xnh.
Giáo trình được chia làm 5 chương và phn ph lc: Chương 1, trình
bày Tng quan v xnh, các khai nim cơ bn, sơ đồ tng quát ca mt
h thng xnh và các vn đề cơ bn trong xnh. Chương 2, trình
bày các k thut nâng cao cht lượng nh da vào các thao tác vi đim
nh, nâng cao cht lượng nh thông qua vic x lý các đim nh trong lân
cn đim nh đang xét. Chương này cũng trình bày các k thut nâng cao
cht lượng nh nh vào các phép toán hình thái. Chương 3, trình bày các k
thut cơ bn trong vic phát hin biên ca các đối tượng nh theo c hai
khuynh hướng: Phát hin biên trc tiếp và phát hin biên gián ti
ếp. Chương
4 th hin cách k thut tìm xương theo khuynh hướng tính toán trc trung
v và hướng tiếp cn xp x nh các thut toán làm mnh song song và gián
tiếp. Và cui cùng là Chương 5 vi các k thut hu x lý.
Giáo trình được biên son da trên kinh nghim ging dy ca tác gi
trong nhiu năm ti các khóa đại hc và cao hc ca ĐH Công ngh -
ĐHQG Hà Ni, ĐH Khoa hc t nhiên –
ĐHQG Hà Ni, Khoa Công ngh
thông tin – ĐH Thái Nguyên v.v.. Cun sách có th làm tài liu tham kho
cho sinh viên các h k sư, c nhân và các bn quan tâm đến vn đề nhn
dng và xnh.
3
Các tác gi bày t lòng biết ơn chân thành ti các bn đồng nghip
trong Phòng Nhn dng và công ngh tri thc, Vin Công ngh thông tin,
B môn H thng thông tin, Khoa Công ngh thông tin, ĐH Thái Nguyên,
Khoa Công ngh thông tin, ĐH Công ngh, ĐHQG Hà Ni, Khoa Toán –
Cơ – Tin, ĐH Khoa hc t nhiên, ĐHQG Hà Ni đã động viên, góp ý và
giúp đỡ để hoàn chnh ni dung cun sách này. Xin cám ơn Lãnh đạo Khoa
Công ngh thông tin, ĐH Thái Nguyên, Ban Giám đốc ĐH Thái Nguyên đã
h tr và t
o điu kin để cho ra đời giáo trình này.
Mc dù rt c gng nhưng tài liu này chc chn không tránh khi
nhng sai sót. Chúng tôi xin trân trng tiếp thu tt c nhng ý kiến đóng
góp ca bn đọc cũng như các bn đồng nghip để có chnh lý kp thi.
Thư góp ý xin gi v: Phm Vit Bình,
Khoa Công ngh thông tin – ĐH Thái nguyên.
Quyết Thng, Tp. Thái Nguyên
Đin thoi: 0280.846506 Email: pvbinh@ictu.edu.vn
Thái Nguyên, ngày 22 tháng 11 năm 2007
CÁC TÁC GI
4
MC LC
LI NÓI ĐẦU
....................................................................................................................................................................... 2
MC LC
..................................................................................................................................................................................4
Chương 1: TNG QUAN V XNH
..................................................................................... 7
1.1. XNH, CÁC VN ĐỀ CƠ BN TRONG XNH
.................. 7
1.1.1. Xnh là gì?
............................................................................................................................................ 7
1.1.2. Các vn đề cơ bn trong xnh
........................................................................................ 7
1.1.2.1 Mt s khái nim cơ bn
........................................................................................................7
1.1.2.2 Nn chnh biến dng
.................................................................................................................... 8
1.1.2.3 Kh nhiu
................................................................................................................................................. 9
1.1.2.4 Chnh mc xám:
............................................................................................................................... 9
1.1.2.5 Trích chn đặc đim
.................................................................................................................... 9
1.1.2.6 Nhn dng
............................................................................................................................................ 10
1.1.2.7 Nén nh
................................................................................................................................................... 11
1.2. THU NHN VÀ BIU DIN NH
........................................................................................... 11
1.2.1. Thu nhn, các thiết b thu nhn nh
.................................................................................. 11
1.2.2. Biu din nh
.............................................................................................................................................. 12
1.2.2.1. Mô hình Raster
............................................................................................................................. 12
1.2.2.2. Mô hình Vector
............................................................................................................................ 13
Chương 2: CÁC K THUT NÂNG CAO CHT LƯỢNG NH
................... 14
2.1. CÁC K THUT KHÔNG PH THUC KHÔNG GIAN
.......................... 14
2.1.1. Gii thiu
......................................................................................................................................................... 14
2.1.2. Tăng gim độ sáng
............................................................................................................................... 14
2.1.3. Tách ngưỡng
................................................................................................................................................ 15
2.1.4. Bó cm
............................................................................................................................................................... 15
2.1.5. Cân bng histogram
............................................................................................................................ 16
2.1.6. K thut tách ngưỡng t động
................................................................................................ 17
2.1.7. Biến đổi cp xám tng th
........................................................................................................... 18
2.2. CÁC K THUT PH THUC KHÔNG GIAN
..................................................... 20
2.2.1. Phép cun và mu
................................................................................................................................. 20
5
2.2.2. Mt s mu thông dng
.................................................................................................................. 21
2.2.3. Lc trung v
.................................................................................................................................................. 22
2.2.4. Lc trung bình
........................................................................................................................................... 24
2.2.5. Lc trung bình theo k giá tr gn nht
............................................................................ 25
2.3. CÁC PHÉP TOÁN HÌNH THÁI HC
.................................................................................... 26
2.3.1. Các phép toán hình thái cơ bn
.............................................................................................. 26
2.3.2. Mt s tính cht ca phép toán hình thái
.................................................................... 27
Chương 3: BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIN BIÊN
..................... 32
3.1. GII THIU
............................................................................................................................................................ 32
3.2. CÁC PHƯƠNG PHÁP PHÁT HIN BIÊN TRC TIP
................................. 32
3.2.1. K thut phát hin biên Gradient
......................................................................................... 32
3.2.1.1. K thut Prewitt
.......................................................................................................................... 34
3.2.1.2. K thut Sobel
............................................................................................................................... 35
3.2.1.3. K thut la bàn
.............................................................................................................................. 35
3.2.2. K thut phát hin biên Laplace
........................................................................................... 36
3.3. PHÁT HIN BIÊN GIÁN TIP
....................................................................................................... 37
3.3.1 Mt s khái nim cơ bn
................................................................................................................. 37
3.3.2. Chu tuyến ca mt đối tượng nh
....................................................................................... 38
3.3.3. Thut toán dò biên tng quát
.................................................................................................... 40
Chương 4: XƯƠNG VÀ CÁC K THUT TÌM XƯƠNG
........................................ 44
4.1. GII THIU
............................................................................................................................................................ 44
4.2. TÌM XƯƠNG DA TRÊN LÀM MNH
........................................................................... 44
4.2.1. Sơ lược v thut toán làm mnh
........................................................................................... 44
4.2.2. Mt s thut toán làm mnh
...................................................................................................... 46
4.3. TÌM XƯƠNG KHÔNG DA TRÊN LÀM MNH
................................................ 46
4.3.1. Khái quát v lược đồ Voronoi
................................................................................................. 47
4.3.2. Trc trung v Voronoi ri rc
................................................................................................... 47
4.3.3. Xương Voronoi ri rc
.................................................................................................................... 48
4.3.4. Thut toán tìm xương
........................................................................................................................ 49
Chương 5: CÁC K THUT HU X
.................................................................................. 52
5.1. RÚT GN S LƯỢNG ĐIM BIU DIN
..................................................................... 52
5.1.1. Gii thiu
......................................................................................................................................................... 52
6
5.1.2. Thut toán Douglas Peucker
..................................................................................................... 52
5.1.2.1. Ý tưởng
................................................................................................................................................. 52
5.1.2.2. Chương trình
................................................................................................................................... 53
5.1.3. Thut toán Band width
.................................................................................................................... 54
5.1.3.1. Ý tưởng
................................................................................................................................................. 54
5.1.3.2. Chương trình
................................................................................................................................... 56
5.1.4. Thut toán Angles
................................................................................................................................. 57
5.1.4.1. Ý tưởng
................................................................................................................................................. 57
5.1.4.2. Chương trình
................................................................................................................................... 57
5.2. XP X ĐA GIÁC BI CÁC HÌNH CƠ S
.................................................................... 58
5.2.1 Xp x đa giác theo bt biến đồng dng
........................................................................ 59
5.2.2 Xp x đa giác theo bt biến aphin
...................................................................................... 62
5.3. BIN ĐỔI HOUGH
........................................................................................................................................ 63
5.3.1. Biến đổi Hongh cho đường thng
....................................................................................... 63
5.3.2. Biến đổi Hough cho đường thng trong ta độ cc
....................................... 64
5.3.2.1. Đường thng Hough trong ta độ cc
............................................................... 64
5.3.2.2. Áp dng biến đổi Hough trong phát hin góc nghiêng văn bn
..................................................................................................................... 65
PH LC
................................................................................................................................................................................ 68
TÀI LIU THAM KHO
.................................................................................................................................... 76
7
Chương 1:
TNG QUAN V XNH
1.1. XNH, CÁC VN ĐỀ CƠ BN TRONG XNH
1.1.1. Xnh là gì?
Con người thu nhn thông tin qua các giác quan, trong đó th giác
đóng vai trò quan trng nht. Nhng năm tr li đây vi s phát trin ca
phn cng máy tính, xnh và đồ ho đó phát trin mt cách mnh m
và có nhiu ng dng trong cuc sng. Xnh và đồ ho đóng mt vai
trò quan trng trong tương tác người máy.
Quá trình xnh được xem như là quá trình thao tác nh đầu vào
nh
m cho ra kết qu mong mun. Kết qu đầu ra ca mt quá trình x
nh có th là mt nh “tt hơn” hoc mt kết lun.
Hình 1.1. Quá trình xnh
nh có th xem là tp hp các đim nh và mi đim nh được xem
nhưđặc trưng cường độ sáng hay mt du hiu nào đó ti mt v trí nào
đó ca đối tượng trong không gian và nó có th xem như mt hàm n biến
P(c
1
, c
2
,..., c
n
). Do đó, nh trong xnh có th xem như nh n chiu.
Sơ đồ tng quát ca mt h thng xnh:
Hình 1.2. Các bước cơ bn trong mt h thng xnh
1.1.2. Các vn đề cơ bn trong xnh
1.1.2.1 Mt s khái nim cơ bn
* nh và đim nh:
Lưu tr
Thu nhn nh
(Scanner,
Camera,Sensor)
Tin x
Trích chn
đặc đim
H quyết định
Đối sánh rút
ra kết lun
Hu
x
XNH
nh
nh
“T
t
hơn”
K
ết lu
n
8
Đim nh được xem như là du hiu hay cường độ sáng ti 1 to độ
trong không gian ca đối tượng và nh được xem như là 1 tp hp các
đim nh.
* Mc xám, màu
Là s các giá tr có th có ca các đim nh ca nh
1.1.2.2 Nn chnh biến dng
nh thu nhn thường b biến dng do các thiết b quang hc và đin
t.
nh thu nhn nh mong mun
Hình 1.3. nh thu nhn và nh mong mun
Để khc phc người ta s dng các phép chiếu, các phép chiếu thường
được xây dng trên tp các đim điu khin.
Gi s (P
i
, P
i
’) i = n,1 có n các tp điu khin
Tìm hàm f: P
i
a f (P
i
) sao cho
min)(
2
'
1
=
ii
n
i
PPf
Gi s nh b biến đổi ch bao gm: Tnh tiến, quay, t l, biến dng
bc nht tuyến tính. Khi đó hàm f có dng:
f (x, y) = (a
1
x + b
1
y + c
1
, a
2
x + b
2
y + c
2
)
Ta có:
()( )
[
]
==
+++++==
n
i
iiiiii
n
i
ycybxaxcybxaPiPif
1
2
'
222
2
'
111
2'
1
))((
φ
Để cho φ min
P
i
P’
i
×f(P
i
)
9
=++
=++
=++
=
=
=
∑∑
∑∑
∑∑
== =
== ==
== ==
n
i
n
i
n
i
iii
n
i
n
i
n
i
ii
n
i
iiii
n
i
n
i
n
i
ii
n
i
iiii
xncybxa
xyycybyxa
xxxcyxbxa
c
b
a
11 1
'
111
11 1
'
1
1
2
11
11 1
'
1
11
2
1
1
1
1
0
0
0
φ
φ
φ
Gii h phương trình tuyến tính tìm được a
1
, b
1
, c
1
Tương t tìm được a
2
, b
2
, c
2
Xác định được hàm f
1.1.2.3 Kh nhiu
Có 2 loi nhiu cơ bn trong quá trình thu nhn nh
Nhiu h thng: là nhiu có quy lut có th kh bng các phép
biến đổi
Nhiu ngu nhiên: vết bn không rõ nguyên nhân khc phc
bng các phép lc
1.1.2.4 Chnh mc xám:
Nhm khc phc tính không đồng đều ca h thng gây ra. Thông
thường có 2 hướng tiếp c
n:
Gim s mc xám: Thc hin bng cách nhóm các mc xám gn
nhau thành mt bó. Trường hp ch có 2 mc xám thì chính là
chuyn v nh đen trng. ng dng: In nh màu ra máy in
đen trng.
Tăng s mc xám: Thc hin ni suy ra các mc xám trung gian
bng k thut ni suy. K thut này nhm tăng cường độ mn
cho nh
1.1.2.5 Trích chn đặc đ
im
Các đặc đim ca đối tượng được trích chn tu theo mc đích nhn
dng trong quá trình xnh. Có th nêu ra mt s đặc đim ca nh
sau đây:
Đặc đim không gian: Phân b mc xám, phân b xác sut, biên độ,
đim un v.v..
Đặc đim biến đổi: Các đặc đim loi này được trích chn b
ng vic
thc hin lc vùng (zonal filtering). Các b vùng được gi là “mt n đặc
10
đim” (feature mask) thường là các khe hp vi hình dng khác nhau (ch
nht, tam giác, cung tròn v.v..)
Đặc đim biên và đường biên: Đặc trưng cho đường biên ca đối
tượng và do vy rt hu ích trong vic trích trn các thuc tính bt biến
được dùng khi nhn dng đối tượng. Các đặc đim này có th được trích
chn nh toán t gradient, toán t la bàn, toán t Laplace, toán t “chéo
không” (zero crossing) v.v..
Vic trích chn hiu qu các đặc
đim giúp cho vic nhn dng các
đối tượng nh chính xác, vi tc độ tính toán cao và dung lượng nh lưu
tr gim xung.
1.1.2.6 Nhn dng
Nhn dng t động (automatic recognition), mô t đối tượng, phân
loi và phân nhóm các mu là nhng vn đề quan trng trong th giác máy,
được ng dng trong nhiu ngành khoa hc khác nhau. Tuy nhiên, mt câu
hi đặt ra là: mu (pattern) là gì? Watanabe, mt trong nhng người đi đầu
trong lĩ
nh vc này đã định nghĩa: “Ngược li vi hn lon (chaos), mu là
mt thc th (entity), được xác định mt cách ang áng (vaguely defined) và
có th gán cho nó mt tên gi nào đó”. Ví d mu có thnh ca vân tay,
nh ca mt vt nào đó được chp, mt ch viết, khuôn mt người hoc
mt ký đồ tín hiu tiếng nói. Khi biết mt mu nào đó, để nhn d
ng hoc
phân loi mu đó có th:
Hoc phân loi có mu (supervised classification), chng hn phân
tích phân bit (discriminant analyis), trong đó mu đầu vào được định danh
như mt thành phn ca mt lp đã xác định.
Hoc phân loi không có mu (unsupervised classification hay
clustering) trong đó các mu được gán vào các lp khác nhau da trên mt
tiêu chun đồng dng nào đó. Các lp này cho đến thi đim phân loi vn
ch
ưa biết hay chưa được định danh.
H thng nhn dng t động bao gm ba ku tương ng vi ba giai
đon ch yếu sau đây:
1
o
. Thu nhn d liu và tin x lý.
2
o
. Biu din d liu.
3
o
. Nhn dng, ra quyết định.
Bn cách tiếp cn khác nhau trong lý thuyết nhn dng là:
1
o
. Đối sánh mu da trên các đặc trưng được trích chn.
2
o
. Phân loi thng kê.
3
o
. Đối sánh cu trúc.
11
4
o
. Phân loi da trên mng nơ-ron nhân to.
Trong các ng dng rõ ràng là không th ch dùng có mt cách tiếp
cn đơn l để phân loi “ti ưu” do vy cn s dng cùng mt lúc nhiu
phương pháp và cách tiếp cn khác nhau. Do vy, các phương thc phân
loi t hp hay được s dng khi nhn dng và nay đã có nhng kết qu
trin vng da trên thiết kế các h
thng lai (hybrid system) bao gm nhiu
mô hình
kết hp.
Vic gii quyết bài toán nhn dng trong nhng ng dng mi, ny
sinh trong cuc sng không ch to ra nhng thách thc v thut gii, mà
còn đặt ra nhng yêu cu v tc độ tính toán. Đặc đim chung ca tt c
nhng ng dng đó là nhng đặc đim đặc trưng cn thiế
t thường là nhiu,
không th do chuyên gia đề xut, mà phi được trích chn da trên các th
tc phân tích d liu.
1.1.2.7 Nén nh
Nhm gim thiu không gian lưu tr. Thường được tiến hành theo c
hai cách khuynh hướng là nén có bo toàn và không bo toàn thông tin.
Nén không bo toàn thì thường có kh năng nén cao hơn nhưng kh năng
phc hi thì kém hơn. Trên cơ s hai khuynh hướng, có 4 cách tiếp cn cơ
bn trong nén nh:
Nén nh thng kê: K thut nén này da vào vic thng kê tn xut
xut hin ca giá tr các đim nh, trên cơ s đó mà có chiến lược
mã hóa thích hp. Mt ví d đin hình cho k thut mã hóa này
là *.TIF
Nén nh không gian: K thut này da vào v trí không gian ca
các đim nh để tiến hành mã hóa. K thut li dng s ging nhau
ca các
đim nh trong các vùng gn nhau. Ví d cho k thut này
là mã nén *.PCX
Nén nh s dng phép biến đổi: Đây là k thut tiếp cn theo
hướng nén không bo toàn và do vy, k thut thướng nến hiu qu
hơn. *.JPG chính là tiếp cn theo k thut nén này.
Nén nh Fractal: S dng tính cht Fractal ca các đối tượng nh,
th hin s lp li ca các chi tiế
t. K thut nén s tính toán để ch
cn lưu tr phn gc nh và quy lut sinh ra nh theo nguyên lý
Fractal
1.2. THU NHN VÀ BIU DIN NH
1.2.1. Thu nhn, các thiết b thu nhn nh
12
Các thiết b thu nhn nh bao gm camera, scanner các thiết b thu
nhn này có th cho nh đen trng
Các thiết b thu nhn nh có 2 loi chính ng vi 2 loi nh thông
dng Raster, Vector.
Các thiết b thu nhn nh thông thường Raster là camera các thiết b
thu nhn nh thông thường Vector là sensor hoc bàn s hoá Digitalizer
hoc được chuyn đổi t nh Raster.
Nhìn chung các h thng thu nhn nh thc hin 1 quá trình
Cm biến: biến đổi năng lượng quang hc thành năng lượng đin
Tng hp năng lượng đin thành nh
1.2.2. Biu din nh
nh trên máy tính là kết qu thu nhn theo các phương pháp s hoá
được nhúng trong các thiết b k thut khác nhau. Quá trình lưu tr nh
nhm 2 mc đích:
Tiết kim b nh
Gim thi gian x
Vic lưu tr thông tin trong b nhnh hưởng rt ln đến vic hin
th, in n và xnh được xem như là 1 tp hp các đim v
i cùng kích
thước nếu s dng càng nhiu đim nh thì bc nh càng đẹp, càng mn và
càng th hin rõ hơn chi tiết ca nh người ta gi đặc đim nàyđộ
phân gii.
Vic la chn độ phân gii thích hp tu thuc vào nhu cu s dng
đặc trưng ca mi nh c th, trên cơ s đó các nh th
ường được biu
din theo 2 mô hình cơ bn
1.2.2.1. Mô hình Raster
Đây là cách biu din nh thông dng nht hin nay, nh được biu
din dưới dng ma trn các đim (đim nh). Thường thu nhn qua các
thiết b như camera, scanner. Tu theo yêu cu thc thế mà mi đim nh
được biu din qua 1 hay nhiu bít
Mô hình Raster thun li cho hin th và in n. Ngày nay công ngh
phn cng cung cp nhng thiết b thu nhn nh Raster phù hp vi tc độ
nhanh và cht lượng cao cho c đầu vào và đầu ra. Mt thun li cho vic
hin th trong môi trường Windows là Microsoft đưa ra khuôn dng nh
DIB (Device Independent Bitmap) làm trung gian. Hình 1.4 th hình quy
trình chung để hin th nh Raster thông qua DIB.
13
Mt trong nhng hướng nghiên cu cơ bn trên mô hình biu din này
là k thut nén nh các k thut nén nh li chia ra theo 2 khuynh hướng là
nén bo toàn và không bo toàn thông tin nén bo toàn có kh năng phc
hi hoàn toàn d liu ban đầu còn nếu không bo toàn ch có kh năng
phc hi độ sai s cho phép nào đó. Theo cách tiếp cn này người ta đã đề
ra nhiu quy cách khác nhau như BMP, TIF, GIF, PCX…
Hin nay trên thế gii có trên 50 khuôn d
ng nh thông dng bao gm
c trong đó các k thut nén có kh năng phc hi d liu 100% và nén có
kh năng phc hi vi độ sai s nhn được.
Hình 1.4. Quá trình hin th và chnh sa, lưu tr nh thông qua DIB
1.2.2.2. Mô hình Vector
Biu din nh ngoài mc đích tiết kim không gian lưu tr d dàng
cho hin th và in n còn đảm bo d dàng trong la chn sao chép di
chuyn tìm kiếm… Theo nhng yêu cu này k thut biu din vector t ra
ưu vit hơn.
Trong mô hình vector người ta s dng hướng gia các vector ca
đim nh lân cn để mã hoá và tái to hình nh ban đầu nh vector được thu
nhn tr
c tiếp t các thiết b s hoá như Digital hoc được chuyn đổi t
nh Raster thông qua các chương trình s hoá
Công ngh phn cng cung cp nhng thiết b x lý vi tc độ nhanh
và cht lượng cho c đầu vào và ra nhưng li ch h tr cho nh Raster.
Do vy, nhng nghiên cu v biu din vectơ đều tp trung t chuyn
đổi t
nh Raster.
Hình 1.5. S chuyn đổi gia các mô hình biu din nh
BMP
PCC
.
.
.
DIB
Ca s
Thay đổi
Paint
RASTER
VECTOR
RASTER
Vecter
hóa
Raster
hóa
14
Chương 2:
CÁC K THUT NÂNG CAO CHT LƯỢNG NH
2.1. CÁC K THUT KHÔNG PH THUC KHÔNG GIAN
2.1.1. Gii thiu
Các phép toán không ph thuc không gian là các phép toán không
phc thuc v trí ca đim nh.
Ví d: Phép tăng gim độ sáng , phép thng kê tn sut, biến đổi
tn sut v.v..
Mt trong nhng khái nim quan trng trong xnh là biu đồ tn
sut (Histogram)
Biu đồ tn sut ca mc xám g ca nh I là s đim nh có giá tr g
ca nh I. Ký hiu là h(g)
Ví d
:
1 2 0 4
1 0 0 7
I = 2 2 1 0
4 1 2 1
2 0 1 1
g 0 1 2 4 7
h(g) 5 7 5 2 1
2.1.2. Tăng gim độ sáng
Gi s ta có I ~ kích thước m × n và s nguyên c
Khi đó, k thut tăng, gim độc sáng được th hin
for (i = 0; i < m; i + +)
for (j = 0; j < n; j + +)
I [i, j] = I [i, j] + c;
Nếu c > 0: nh sáng lên
Nếu c < 0: nh ti đi
15
2.1.3. Tách ngưỡng
Gi s ta có nh I ~ kích thước m × n, hai s Min, Max và ngưỡng θ
khi đó: K thut tách ngưỡng được th hin
for (i = 0; i < m; i + +)
for (j = 0; j < n; j + +)
I [i, j] = I [i, j] > = θ? Max : Min;
* ng dng:
Nếu Min = 0, Max = 1 k thut chuyn nh thành nh đen trng được
ng dng khi quét và nhn dng văn bn có th xy ra sai sót nn thành nh
hoc nh thành nn dn đến nh b
đứt nét hoc dính.
2.1.4. Bó cm
K thut nhm gim bt s mc xám ca nh bng cách nhóm li s
mc xám gn nhau thành 1 nhóm
Nếu ch có 2 nhóm thì chính là k thut tách ngưỡng. Thông thường
có nhiu nhóm vi kích thước khác nhau.
Để tng quát khi biến đổi người ta s ly cùng 1 kích thước
bunch_size
I [i,j] = I [i,j]/ bunch - size * bunch_size (i,j)
Ví d: Bó cm nh sau vi bunch_size= 3
1 2 4 6 7
2 1 3 4 5
I = 7 2 6 9 1
4 1 2 1 2
g
h(g)
0
16
0 0 3 6 6
0 0 3 3 3
I
kq
= 6 0 6 9 0
3 0 0 0 0
2.1.5. Cân bng histogram
nh I được gi là cân bng "lý tưởng" nếu vi mi mc xám g, g’ ta
có h(g) = h(g’)
Gi s, ta có nh I ~ kích thước m × n
new_level ~ s mc xám ca nh cân bng
levelnew
nm
TB
_
×
=
~ s đim nh trung bình ca mi mc xám
ca nh cân bng
=
=
g
i
ihgt
0
)()(
~ s đim nh có mc xám g
Xác định hàm f: g
a
f(g)
Sao cho:
= 1
)(
,0max)(
TB
gt
roundgf
Ví d: Cân bng nh sau vi new_level= 4
1 2 4 6 7
2 1 3 4 5
I = 7 2 6 9 1
4 1 2 1 2
g h(g) t(g) f(g)
1 5 5 0
2 5 10 1
3 1 11 1
4 3 14 2
5 1 15 2
6 2 17 2
7 2 19 3
9 1 20 3
17
0 1 2 2 3
1 0 1 2 2
I
kq
= 3 1 2 3 0
2 0 1 0 1
Chú ý:
nh sau khi thc hin cân bng chưa chc đã là cân bng "lý tưởng
"
2.1.6. K thut tách ngưỡng t động
Ngưỡng θ trong k thut tách ngưỡng thường được cho bi người s
dng. K thut tách ngưỡng t động nhm tìm ra ngưỡng θ mt cách t
động da vào histogram theo nguyên lý trong vt lý là vt th tách làm 2
phn nếu tng độ lnh trong tng phn là ti thiu.
Gi s, ta có nh I ~ kích thước m × n
G ~ s mc xám ca nh k c khuyết thiếu
t(g) ~ s đim nh có mc xám g
=
=
g
i
ihi
gt
gm
0
)(.
)(
1
)(
~ mômen quán tính TB có mc xám g
Hàm f:
)(gfg a
[]
2
)1()(
)(
)(
)(
= Gmgm
gtmxn
gt
gf
Tìm θ sao cho:
()
{
}
)(
max
10
gff
Gg <
=
θ
Ví d: Tìm ngưỡng t động ca nh sau
0 1 2 3 4 5
0 0 1 2 3 4
I = 0 0 0 1 2 3
0 0 0 0 1 2
0 0 0 0 0 1
Lp bng
g h(g) t(g) g.h(g)
=
g
i
iih
0
)( m(g) f(g)
0 15 15 0 0 0 1.35
1 5 20 5 5 0,25 1.66
18
2 4 24 8 13 0,54 1.54
3 3 27 9 22 0,81 1.10
4 2 29 8 30 1,03 0.49
5 1 30 5 35 1,16
Ngưỡng cn tách θ= 1 ng vi f(θ)= 1.66
2.1.7. Biến đổi cp xám tng th
Nếu biết nh và hàm biến đổi thì ta có th tính được nh kết qu và do
đó ta sđược histogram ca nh biến đổi. Nhưng thc tế nhiu khi ta ch
biết histogram ca nh gc và hàm biến đổi, câu hi đặt ra là liu ta có th
được histogram ca nh biến đổi. Nếu có như vy ta có th hiu chnh
hàm biến đổi để thu được nh kế
t qu có phân b histogram như
mong mun.
Bài toán đặt ra là biết histogram ca nh, biết hàm biến đổi hãy v
histogram ca nh mi.
Ví d:
g 1 2 3 4
h(g) 4 2 1 2
g + 1 nếu g 2
f(g)= g nếu g = 3
g – 1 nếu g > 3
Bước 1:
V Histogram ca nh cũ
g
f(g)
0
19
Bước 2:
V đồ th hàm f(g)
Bước 3:
V Histogram ca nh mi
Đặt q = f(g)
h(q) = card ({P| I(P) = q})
= card ({P| I(P) = f(g)})
= card ({P| g = f
-1
(I(P))})
=
)(
1
)(
qfi
ih
Histogram ca nh mi thua được bng cách chng hình và tính giá tr
theo các q (= f(g)) theo công thc tính trên. Kết qu cui thu được sau phép
quay góc 90 thun chiu kim đồng h.
g
h(g) f(g)
0
g
h(g)
0
20
2.2. CÁC K THUT PH THUC KHÔNG GIAN
2.2.1. Phép cun và mu
Gi s ta có nh I kích thước M × N, mu T có kích thước m × n khi
đó, nh I cun theo mu T được xác định bi công thc.
()()
jiTjyixIyxTI
n
j
m
i
,*,),(
1
0
1
0
=
=
++=
(2.1)
Hoc
()()
jiTjyixIyxTI
n
j
m
i
,*,),(
1
0
1
0
=
=
=
(2.2)
VD:
1 2 4 5 8 7
2 1 1 4 2 2
I = 4 5 5 8 8 2
1 2 1 1 4 4
7 2 2 1 5 2
T = 1 0
0 1
()()()()()()
1,1*1,10,0*,,*,),(
1
0
1
0
TyxITyxIjiTjyixIyxTI
ji
+++=++=
==
()
(
)
1,1,
+
+
+
= yxIyxI
2 3 8 7 10 *
7 6 9 12 4 * Tính theo (2.1)
I T = 6 6 6 12 12 *
3 4 2 6 6 *
* * * * * *
Tính theo công thc 2.2
* * * * * *
* 2 3 8 7 10
I T = * 7 6 9 12 4
* 6 6 6 12 12
* 3 4 2 6 6
21
* Nhn xét:
- Trong quá trình thc hin phép cun có mt s thao tác ra ngoài nh,
nh không được xác định ti nhng v trí đó dn đến nh thu được có kích
thước nhá hơn.
- nh thc hin theo công thc 2.1 và 2.2 ch sai khác nhau 1 phép
dch chuyn để đơn gin ta s hiu phép cun là theo công thc 2.1
2.2.2. Mt s mu thông dng
- Mu:
1 1 1
T
1
= 1 1 1
1 1 1
~ Dùng để kh nhiu Các đim có tn s cao
VD1:
1 2 4 5 8 7
2 31 1 4 2 2
I = 4 5 5 8 8 2
1 2 1 1 4 4
7 2 2 1 5 2
55 65 45 46 * *
52 58 34 35 * *
I T
1
= 29 27 35 35 * *
* * * * * *
* * * * * *
Áp dng k thut cng hng s vi c = -27, ta có:
28 38 18 19 * *
25 31 7 8 * *
I
kq
= 2 0 8 8 * *
* * * * * *
* * * * * *
- Mu:
0 -1 0
T
2
= -1 4 -1
0 -1 0
22
~ Dùng để phát hin các đim có tn s cao
VD2:
114 -40 0 -14 * *
-22 5 14 16 * *
I T2 =-1 -6 -10 -2 * *
* * * * * *
* * * * * *
2.2.3. Lc trung v
* Định nghĩa 2.1 (Trung v)
Cho dãy x
1
; x
2
...; x
n
đơn điu tăng (gim). Khi đó trung v ca dãy ký
hiu là Med({x
n
}), được định nghĩa:
+ Nếu n l
+ 1
2
n
x
+ Nếu n chn:
2
n
x
hoc
+ 1
2
n
x
* Mnh đề 2.1
min
1
=
n
i
i
xx
ti
{
}
)
n
xMed
Chng minh
+ Xét trường hp n chn
Đặt
2
n
M =
Ta có:
=
+
==
+=
M
i
iM
M
i
i
n
i
i
xxxxxx
111
()
=
+
=
+
+=
M
i
iiM
M
i
iMi
xxxxxx
11
()()
[]
=
+
+=
M
i
iMMM
xxxx
1
1
{}() {}()
∑∑
==
+
+=
M
i
M
i
iiiiM
xMedxxMedx
11
23
{}()
=
=
n
i
ii
xMedx
1
+ Nếu n l:
B sung thêm phn t
{
}
(
)
i
xMed
vào dãy. Theo trường hp n chn
ta có:
{}() {}()
ii
n
i
i
xMedxMedxx +
=1
min ti Med({x
n
})
=
n
i
i
xx
1
min ti Med({x
n
})
* K thut lc trung v
Gi s ta có nh I ngưìng θ ca s W(P) và đim nh P
Khi đó k thut lc trung v ph thuc không gian bao gm các bước
cơ bn sau:
+ Bước 1:
Tìm trung v
{I(q)| q W(P)} Med (P)
+ Bước 2:
Gán giá tr
=
)(
)(
)(
PMed
PI
PI
Nguoclai
PMedPI
θ
)()(
Ví d:
1 2 3 2
4 16 2 1
I = 4 2 1 1
2 1 2 1
W(3 × 3); θ = 2
1 2 3 2
4 2 2 1
I
kq
= 4 2 1 1
2 1 2 1
Giá tr 16, sau phép lc có giá tr 2, các giá tr còn li không thay đổi
giá tr.
24
2.2.4. Lc trung bình
* Định nghĩa 2.2 (Trung bình)
Cho dãy x
1
, x
2
…, x
n
khi đó trung bình ca dãy ký hiu AV({x
n
})
ddược định nghĩa:
{}()
=
=
n
i
in
x
n
roundxAV
1
1
* Mnh đề 2.2
()
min
2
1
=
n
i
i
xx
ti
{
}
(
)
n
xAV
Chng minh:
Đặt:
()
=
=
n
i
i
xxx
1
2
)(
φ
Ta có:
()
=
=
n
i
i
xxx
1
2)(
φ
0)(
'
=x
φ
()
=
=
n
i
i
xx
1
0
{}()
=
==
n
i
ii
xAVx
n
x
1
1
Mt khác,
02)(
''
>= nx
φ
min
φ
ti
{
}
)
i
xAVx
=
K thut lc trung bình
Gi s ta có nh I, đim nh P, ca s W(P) và ngưỡng θ. Khi đó k
thut lc trung bình ph thuc không gian bao gm các bước cơ bn sau:
+ Bước 1
: Tìm trung bình
{I(q)| q W(P)} AV(P)
25
+ Bước 2: Gán giá tr
=
)(
)(
)(
PAV
PI
PI
Nguoclai
PAVPI
θ
)()(
Ví d:
1 2 3 2
4 16 2 1
I = 4 2 1 1
2 1 2 1
W(3 × 3); θ = 2
1 2 3 2
4 3 2 1
I
kq
= 4 2 1 1
2 1 2 1
Giá tr 16 sau phép lc trung bình có giá tr 3, các giá tr còn li gi
nguyên sau phép lc.
2.2.5. Lc trung bình theo k giá tr gn nht
Gi s ta có nh I, đim nh P, ca s W(P), ngưỡng θ và s k. Khi
đó, lc trung bình theo k giá tr gn nht bao gm các bước sau:
+ Bước 1
: Tìm K giá tr gn nht
{I(q) q W(p)} {k giá tr gn I(P) nht}
+ Bước 2
: Tính trung bình
{k giá tr gn I(P) nht} AV
k
(P)
+ Bước 3
: Gán giá tr
=
)(
)(
)(
PAV
PI
PI
k
Nguoclai
PAVPI
k
θ
)()(
Ví d:
1 2 3 2
4 16 2 1
I = 4 2 1 1
2 1 2 1
W(3 × 3); θ = 2; k = 3
26
1 2 3 2
4 8 2 1
I
kq
= 4 2 1 1
2 1 2 1
* Nhn xét:
- Nếu k ln hơn kích thước ca s thì k thut chính là k thut lc
trung bình
- Nếu k= 1 thì nh kết qu không thay đổi
Cht lượng ca k thut ph thuc vào s phân t la chn k.
2.3. CÁC PHÉP TOÁN HÌNH THÁI HC
2.3.1. Các phép toán hình thái cơ bn
Hình thái là thut ng ch s nghiên cu v cu trúc hay hình hc topo
ca đối tượng trong nh. Phn ln các phép toán ca "Hình thái" đưc định
nghĩa t hai phép toán cơ bn là phép "giãn n" (Dilation) và phép "co"
(Erosion).
Các phép toán này được định nghĩa như sau: Gi thiết ta có đối tượng
X và phn t cu trúc (mu) B trong không gian Euclide hai chiu. Kí hiu
B
x
là dch chuyn ca B ti v trí x.
Định nghĩa 2.3 (DILATION)
Phép "giãn n" ca X theo mu B là hp ca tt c các B
x
vi x thuc
X. Ta có:
X B =
U
Xx
x
B
Định nghĩa 2.4 (EROSION)
Phép "co" ca X theo B là tp hp tt c các đim x sao cho B
x
nm
trong X. Ta có:
X \ B = {x : B
x
X}
Ví d: Ta có tp X như sau: X =
00
000
000
00
00
xxx
xx
xx
xxx
xxx
B =
8
x
27
X B =
xxxx
xxxx
xxx
xxxxx
xxxx
0
0
00
0
và X\B =
000
00000
0000
0000
0000
xx
x
x
x
Đình nghĩa 2.5 (OPEN)
Phép toán m (OPEN) ca X theo cu trúc B là tp hp các đim ca
nh X sau khi đã co và giãn n liên liếp theo B. Ta có:
OPEN(X,B) = (X \ B) B
Ví d: Vi tp X và B trong ví d trên ta có
OPEN(X,B) =
(X\B) B =
0xxx0
00000
00xx0
0xx00
xx000
Định nghĩa 2.6 (CLOSE)
Phép toán đóng (CLOSE) ca X theo cu trúc B là tp hp các đim
ca nh X sau khi đã giãn n và co liên tiếp theo B. Ta có:
CLOSE(X,B) = (X B) \ B
Theo ví d trên ta có:
CLOSE(X,B) = (X B) \ B =
0xxx0
0xxx0
00xx0
xxxxx
xxxx0
2.3.2. Mt s tính cht ca phép toán hình thái
* Mnh đề 2.3 [Tính gia tăng]:
(i) X X’ X \ B X’ \ B B
X B X’ B B
(ii) B B
'
X \ B X
\ B
'
X
X B X B’ X
28
Chng minh:
(i) X B =
BXBB
Xx
x
Xx
x
=
'
'
UU
X \ B =
{}
{
}
'// XBxXBx
xx
= X’ \ B
(ii) X B =
'' BXBB
Xx
x
Xx
x
=
UU
Theo định nghĩa:
X \ B’ =
{}
{
}
XBxXBx
xx
/'/
= X \ B .
*Mnh đề 2.4 [Tính phân phi vi phép ]:
(i) X (B B') = (X B) (X B')
(ii) X\ (B B') = (X \ B) (X \B')
Chng minh:
(i) X (B
B’) = ( X B) (X B’)
Ta có: B
B’ B
X (B
B’) X B (tính gia tăng)
Tương t:
X ( B
B’) X B’
X (B
B’) (X B)
(X B’) (2.3)
Mt khác,
y X (B
B’) x X sao cho y (B B’)
x
y B
x
y X B
y B’
x
y X B’
y (X B)
(X B’)
X (B
B’) (X B ) (X B’) (2.4)
T (2.3) và (2.4) ta có: X (B
B’) = (X B) (X B’)
(ii) X \ (B
B’) = (X \ B)
(X \ B’)
Ta có: B
B’ B
X \ (B
B’) X \ B (tính gia tăng)
Tương t : X \ (B
B’) X \ B’
X \ (B
B’) (X \ B)
( X \ B’) (2.5)
29
Mt khác,
x (X \ B)
(X \ B’)
Suy ra, x X \ B B
x
X
x X \ B’ B’
x
X
( B
B’)
x
X
x X \ (B
B’)
X \ (B
B’) (X \ B)
(X \ B’) (2.6)
T (2.5) và (2.6) ta có: X \ (B
B’) = (X \ B) (X \ B’).
* Ý nghĩa:
Ta có th phân tích các mu phc tp tr thành các mu đơn gin
thun tin cho vic cài đặt.
* Mnh đề 2.5 [Tính phân phi vi phép ]:
(X Y) \ B = (X \ B) (Y \ B)
Chng minh:
Ta có, X
Y X
(X
Y) \ B X \ B
Tương t: (X
Y) \ B Y \ B
(X
Y) \ B (X \ B)
(Y \ B) (2.7)
Mt khác,
x (X \ B)
(Y \ B)
Suy ra x X \ B B
x
X
x Y \ B B
x
Y
Bx X
Y
x ( X
Y) \ B
(X
Y) \ B (X \ B)
(Y \ B) (2.8)
T (2.7) và (2.8) ta có: (X
Y) \ B = (X \ B)
(Y \ B).
* Mnh đề 2.6 [Tính kết hp]
(i) (X B) B' = X (B B')
(ii) (X \ B) \ B' = X \ (B B')
30
Chng minh:
(i) (X B) B' = X (B' B)
Ta có, (X B) B' = (
U
Xx
x
B
) B'
=
U
Xx
x
BB
)(
'
=
U
Xx
x
BB
)(
'
= X (B' B)
(i) (X \ B) \ B' = X \ (B B')
Trước hết ta đi chng minh:
'
x
B X \ B
x
BB )(
'
X
Tht vy, do
'
x
B X \ B nên y
'
x
B yX \ B
B
y
X
XB
x
By
y
U
'
x
BB )(
'
X
Mt khác,
x
BB )(
'
X (
'
x
B
B) X
U
'
x
By
y
B
X
y
'
x
B
ta có B
y
X
hay y
'
x
B
ta có y X \ B
Do đó,
'
x
B X \ B
Ta có, (X \ B) \ B' =
{
}
XBx
x
/ \ B'
= {x/
'
x
B X \ B}
= {x/
x
BB )(
'
X} (do chng minh trên)
= X \ (B B') .
* Định lý 2.1 [X b chn bi các cn OPEN và CLOSE]
Gi s, X là mt đối tượng nh, B là mu, khi đó, X s b chn trên
bi tp CLOSE ca X theo B và b chn dưới bi tp OPEN ca X theo B.
Tc là:
(X B) \ B X (X \ B) B
31
Chng minh:
Ta có: x X B
x
X B (Vì X B =
U
Xx
x
B
)
x (X B) \ B (theo định nghĩa phép co)
(X B) \ B X (2.9)
Mt khác,
y (X \ B) B, suy ra:
x X \ B sao cho y B
x
(Vì (X\B) B =
U
BΘXx
x
B )
B
x
X y X
Suy ra: X (X \ B) B (2.10)
T (2.9) và (2.10) Ta có: (X B) \ B X (X \ B) B .
*H qu 2.1 [Tính bt biến] :
(i) ((X B) \B) B = X B
(ii) ((X \ B) B) \ B = X\B
Chng minh:
(i) Tht vy, t định lý 2.1 ta có X
(X B) Ө B
X B
((X B) \B) B (do tính cht gia tăng) (2.11)
Mt khác, cũng t định lý 2.1 ta có (X \ B) B X X
Do đó, thay X bi X B ta có, ((X B) \B) B X B (2.12)
T (2.11) và (2.12) Ta có: ((X B) \B) B = X B
(ii) Tht vy, t định lý 2.1 ta có (X \ B) B
X
((X \ B) B) \ B
X\B (do tính cht gia tăng) (2.13)
Mt khác, cũng t định lý 2.1 ta có X
(X B) Ө B X
Do đó, thay X bi X \ B ta có, X\B ((X \ B) B) \ B (2.14)
T (2.13) và (2.14) Ta có: ((X \ B) B) \ B = X\B (đpcm).
32
Chương 3:
BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIN BIÊN
3.1. GII THIU
Biên là vn đề quan trng trong trích chn đặc đim nhm tiến ti hiu
nh. Cho đến nay chưa có định nghĩa chính xác v biên, trong mi ng
dng người ta đưa ra các độ đo khác nhau v biên, mt trong các độ đo đó
độ đo v s thay đổi đột ngt v cp xám. Ví d: Đối vi nh đen trng,
mt đim được g
i là đim biên nếu nó là đim đen có ít nht mt đim
trng bên cnh. Tp hp các đim biên to nên biên hay đường bao ca
đối tượng. Xut phát t cơ s này người ta thường s dng hai phương
pháp phát hin biên cơ bn:
Phát hin biên trc tiếp: Phương pháp này làm ni biên da vào s
biến thiên mc xám ca nh. K thut ch yế
u dùng để phát hin biên
đây là da vào s biến đổi cp xám theo hướng. Cách tiếp cn theo đạo
hàm bc nht ca nh da trên k thut Gradient, nếu ly đạo hàm bc hai
ca nh da trên biến đổi gia ta có k thut Laplace.
Phát hin biên gián tiếp: Nếu bng cách nào đó ta phân được nh
thành các vùng thì ranh gii gia các vùng đó gi là biên. K thut dò biên
và phân vùng nh là hai bài toán đối ngu nhau vì dò biên
để thc hin phân
lp đối tượng mà khi đã phân lp xong nghĩa là đã phân vùng được nh và
ngược li, khi đã phân vùng nh đã đưc phân lp thành các đối tượng, do đó
có th phát hin được biên.
Phương pháp phát hin biên trc tiếp t ra khá hiu qu và ít chu nh
hưởng ca nhiu, song nếu s biến thiên độ sáng không đột ngt, phương
pháp t ra kém hiu qu, phươ
ng pháp phát hin biên gián tiếp tuy khó cài
đặt, song li áp dng khá tt trong trường hp này.
3.2. CÁC PHƯƠNG PHÁP PHÁT HIN BIÊN TRC TIP
3.2.1. K thut phát hin biên Gradient
33
Theo định nghĩa, gradient là mt véctơ có các thành phn biu th tc
độ thay đổi giá tr ca đim nh, ta có:
Trong đó, dx, dy là khong cách (tính bng s đim) theo hướng x và
y.
* Nhn xét:
Tuy ta nói là ly đạo hàm nhưng thc cht ch là mô pháng và xp x
đạo hàm bng các k thut nhân chp (cun theo mu) vì nh s là tín hiu
ri rc nên đạo hàm không tn ti.
Ví d: Vi dx = dy = 1, ta có:
()()
()()
+
+
yxfyxf
y
f
yxfyxf
x
f
,1,
,,1
Do đó, mt n nhân chp theo hướng x là A=
(
)
11
và hướng y là B=
1
1
Chng hn:
0 0 0 0
0 3 3 3
I = 0 3 3 3
0 3 3 3
Ta có,
0 0 0 * 0 3 3 *
I A = 3 0 0 * ; I B= 0 0 0 *
3 0 0 * 0 0 0 *
* * * * * * * *
0 0 0 *
I A + I B= 3 0 0 *
3 0 0 *
* * * *
dy
yxfdyyxf
fy
y
yxf
dx
yxfydxxf
fx
x
yxf
),(),(),(
),(),(),(
+
=
+
=
34
3.2.1.1. K thut Prewitt
K thut s dng 2 mt n nhp chp xp x đạo hàm theo 2 hướng x
và y là:
-1 0 1
H
x
= -1 0 1
-1 0 1
-1 -1 -1
H
y
= 0 0 0
1 1 1
Các bước tính toán ca k thut Prewitt
+ Bước 1
: Tính I H
x
và I H
y
+ Bước 2
: Tính I H
x
+ I H
y
Ví d:
0 0 0 0 0 0
5 5 5 5 0 0
5 5 5 5 0 0
I = 5 5 5 5 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 -10 -10 * *
0 0 -15 -15 * *
I H
x
= 0 0 -10 -10 * *
0 0 -5 -5 * *
* * * * * *
* * * * * *
15 15 10 5 * *
0 0 0 0 * *
-15 -15 -10 -5 * *
I H
y
= -15 -15 -10 -5 * *
* * * * * *
* * * * * *
35
15 15 0 -5 * *
0 0 -15 -15 * *
I H
x
+ I H
y
= -15 -15 -20 -15 * *
-15 -15 -15 -10 * *
* * * * * *
* * * * * *
3.2.1.2. K thut Sobel
Tương t như k thut Prewitt k thut Sobel s dng 2 mt n nhân
chp theo 2 hướng x, y là:
-1 0 1
H
x
= -2 0 2
-1 0 1
-1 -2 -1
H
y
= 0 0 0
1 2 1
Các bước tính toán tương t Prewitt
+ Bước 1
: Tính I H
x
và I H
y
+ Bước 2
: Tính I H
x
+ I H
y
3.2.1.3. K thut la bàn
K thut s dng 8 mt n nhân chp theo 8 hướng 0
0
, 45
0
, 90
0
, 135
0
,
180
0
, 225
0
, 270
0
, 315
0
5 5 -3 5 5 5
H
1
= 5 0 -3 H
2
= -3 0 -3
-3 -3 -3 -3 -3 -3
-3 5 5 -3 -3 5
H
3
= -3 0 5 H
4
= -3 0 5
-3 -3 -3 -3 -3 5
-3 -3 -3 -3 -3 -3
H
5
= -3 0 5 H
6
= -3 0 -3
-3 5 5 5 5 5
-3 -3 -3 5 -3 -3
H
7
= 5 0 -3 H
8
= 5 0 -3
5 5 -3 5 -3 -3
36
Các bước tính toán thut toán La bàn
+ Bước 1
: Tính I H
i
; i = 1,8
+ Bước 2
:
=
8
1i
i
HI
3.2.2. K thut phát hin biên Laplace
Các phương pháp đánh giá gradient trên làm vic khá tt khi mà độ
sáng thay đổi rõ nét. Khi mc xám thay đổi chm, min chuyn tiếp tri
rng, phương pháp cho hiu qu hơn đó là phương pháp s dng đạo hàm
bc hai Laplace.
Toán t Laplace được định nghĩa như sau:
Ta có:
()
),(),1(
2
2
yxfyxf
xx
f
xx
f
+
=
[]
[
]
),1(),(2),1(
),1(),(),(),1(
yxfyxfyxf
yxfyxfyxfyxf
++
+
Tương t,
()
),()1,(
2
2
yxfyxf
yy
f
y
y
f
+
=
[]
[
]
)1,(),(2)1,(
)1,(),(),()1,(
++
+
yxfyxfyxf
yxfyxfyxfyxf
Vy:
2
f= f(x+1,y) + f(x,y+1) - 4f(x,y) + f(x-1,y) + f(x,y-1)
Dn ti:
010
141
010
H
=
Trong thc tế, người ta thường dùng nhiu kiu mt n khác nhau để
xp x ri rc đạo hàm bc hai Laplace. Dưới đây là ba kiu mt n
thường dùng:
2
2
2
2
2
y
f
x
f
f
+
=
37
VD: 0 0 0 0 0 0
5 5 5 5 0 0
I = 5 5 5 5 0 0
5 5 5 5 0 0
0 0 0 0 0 0
0 0 0 0 0 0
3.3. PHÁT HIN BIÊN GIÁN TIP
3.3.1 Mt s khái nim cơ bn
*nh và đim nh
nh s là mt mng s thc 2 chiu (I
ij
) có kích thước (M×N), trong
đó mi phn t I
ij
(i = 1,...,M; j = 1,...,N) biu th mc xám ca nh ti (i,j)
tương ng.
nh được gi là nh nh phân nếu các giá tr I
ij
ch nhn giá tr 0
hoc 1.
đây ta ch xét ti nh nh phân vì nh bt k có th đưa v dng
nh phân bng k thut phân ngưỡng. Ta ký hiu là tp các đim vùng
(đim đen) và
là tp các đim nn (đim trng).
*Các đim 4 và 8-láng ging
Gi s (i,j) là mt đim nh, các đim 4-láng ging là các đim k
trên, dưới, trái, phi ca (i,j):
N
4
(i,j) = {(i’,j’) : |i-i’|+|j-j’| = 1},
và nhng đim 8-láng ging gm:
N
8
(i,j) = {(i’,j’) : max(|i-i’|,|j-j’|) =1}.
Trong Hình 1.2 biu din ma trn 8 láng ging k nhau, các đim P
0
,
P
2
, P
4
, P
6
là các 4-láng ging ca đim P, còn các đim P
0
, P
1
, P
2
, P
3
, P
4
, P
5
,
P
6
, P
7
là các 8-láng ging ca P.
=
=
=
121
242
121
H
111
181
111
H
010
141
010
H
321
38
Hình 1.3. Ma trn 8-láng ging k nhau
*Đối tượng nh
Hai đim P
s
, P
e
E, E hoc
được gi là 8-liên thông (hoc 4-
liên thông) trong E nếu tn ti tp các đim được gi là đường đi
(i
o
,j
o
)...(i
n
,j
n
) sao cho (i
o
,j
o
)= P
s
, (i
n
,j
n
)= P
e
, (i
r
,j
r
) E và (i
r
,j
r
) là 8-láng ging
(hoc 4-láng ging tương ng) ca (i
r-1
,j
r-1
) vi r = 1,2,...,n
Nhn xét
: Quan h k-liên thông trong E (k=4,8) là mt quan h phn x,
đối xng và bc cu. Bi vy đó là mt quan h tương đương. Mi lp
tương đương được gi là mt thành phn k-liên thông ca nh. V sau ta s
gi mi thành phn k-liên thông ca nh là mt đối tượng nh.
3.3.2. Chu tuyến ca mt đối tượng nh
Định nghĩa 3.1: [Chu tuyến]
Chu tuyến ca mt đối tượng nh là dãy các đim ca đối tượng nh
P
1
,,P
n
sao cho P
i
và P
i+1
là các 8-láng ging ca nhau (i=1,...,n-1) và P
1
8-láng ging ca P
n
, i Q không thuc đối tượng nh và Q là 4-láng ging
ca P
i
(hay nói cách khác i thì Pi là biên 4). Kí hiu <P
1
P
2
..P
n
>.
Tng các khong cách gia hai đim kế tiếp ca chu tuyến là độ dài ca
chu tuyến và kí hiu Len(C) và hướng P
i
P
i+1
là hướng chn nếu P
i
và P
i+1
các 4 – láng ging (trường hp còn li thì P
i
P
i+1
là hướng l).
Hình 3.1 dưới đây biu din chu tuyến ca nh, trong đó, P là đim khi
đầu chu tuyến.
Hình 3.1. Ví d v chu tuyến ca đối tượng nh
P
5
P
7
P
6
P
4
P
0
P
P
3
P
1
P
2
P
39
Định nghĩa 3.2 [Chu tuyến đối ngu]
Hai chu tuyến C= <P
1
P
2
..P
n
> và C
= <Q
1
Q
2
..Q
m
> được gi là đối ngu
ca nhau nếu và ch nếu
i j sao cho:
(i) P
i
và Q
j
là 4-láng ging ca nhau.
(ii) Các đim P
i
là vùng thì Q
j
là nn và ngược li.
Định nghĩa 3.3 [Chu tuyến ngoài]
Chu tuyến C được gi là chu tuyến ngoài (Hình 3.2a) nếu và ch nếu
(i) Chu tuyến đối ngu C
là chu tuyến ca các đim nn
(ii) Độ dài ca C nh hơn độ dài C
Định nghĩa 3.4 [Chu tuyến trong]
Chu tuyến C được gi là chu tuyến trong (Hình 3.2b) nếu và ch nếu:
(i) Chu tuyến đối ngu C
là chu tuyến ca các đim nn
(ii) Độ dài ca C ln hơn độ dài C
Chu tuyÕn C
Chu tuyÕn C
Chu tuyÕn C
Chu tuyÕn C
a) Chu tuyến ngoài b) Chu tuyến trong
Hình 3.2. Chu tuyến trong, chu tuyến ngoài
Định nghĩa 3.5 [Đim trong và đim ngoài chu tuyến]
Gi s C= <P
1
P
2
..P
n
> là chu tuyến ca mt đối tượng nh và P là mt
đim nh. Khi đó:
(i) Nếu na đường thng xut phát t P s ct chu tuyến C ti s l ln,
thì P được gi là đim trong chu tuyến C và kí hiu in(P,C)
(ii) Nếu P
C và P không phi là đim trong ca C, thì P được gi là
đim ngoài chu tuyến C và kí hiu out(P,C).
B đề 3.1 [Chu tuyến đối ngu]
Gi s E
là mt đối tượng nh và C= < P
1
P
2
..P
n
> là chu tuyến ca
E, C
=<Q
1
Q
2
..Q
m
> là chu tuyến đối ngu tương ng. Khi đó:
(i) Nếu C là chu tuyến trong thì in(Q
i
,C) i (i=1,....,m)
40
(ii) Nếu C là chu tuyến ngoài thì in(P
i
,C
) i (i=1,...,n)
B đề 3.2 [Phn trong/ngoài ca chu tuyến]
Gi s E
là mt đối tượng nh và C là chu tuyến ca E. Khi đó:
(i) Nếu C là chu tuyến ngoài thì
x E sao cho xC, ta có in(x,C)
(ii) Nếu C là chu tuyến trong thì
x E sao cho xC, ta có out(x,C)
Định lý 3.1 [Tính duy nht ca chu tuyến ngoài]
Gi s E
là mt đối tượng nh và C
E
là chu tuyến ngoài ca E.
Khi đó C
E
là duy nht.
3.3.3. Thut toán dò biên tng quát
Biu din đối tượng nh theo chu tuyến thường da trên các k thut
dò biên. Có hai k thut dò biên cơ bn. K thut th nht xét nh biên thu
được t nh vùng sau mt ln duyt như mt đồ th, sau đó áp dng các thut
toán duyt cnh đồ th. K thut th hai da trên nh vùng, kết hp đồng thi
quá trình dò biên và tách biên. đây ta quan tâm cách tiếp c
n th hai.
Trước hết, gi s nh được xét ch bao gm mt vùng nh 8-liên thông
, được bao bc bi mt vành đai các đim nn. D thy là mt vùng 4-
liên thông ch là mt trường riêng ca trường hp trên.
V cơ bn, các thut toán dò biên trên mt vùng đều bao gm các
bước sau:
Xác định đim biên xut phát
D báo và xác định đim biên tiếp theo
Lp bước 2 cho đến khi gp đim xut phát
Do xut phát t nhng tiêu chun và định nghĩa khác nhau v đim
biên, và quan h liên thông, các thut toán dò biên cho ta các đường biên
mang các sc thái rt khác nhau.
Kết qu tác động ca toán t dò biên lên mt đim biên r
i
đim biên
r
i+1
(8-láng ging ca r
i
). Thông thường các toán t này được xây dng như
mt hàm đại s Boolean trên các 8-láng ging ca r
i
. Mi cách xây dng
các toán t đều ph thuc vào định nghĩa quan h liên thông và đim biên.
Do đó s gây khó khăn cho vic kho sát các tính cht ca đường biên.
Ngoài ra, vì mi bước dò biên đều phi kim tra tt c các 8-láng ging ca
mi đim nên thut toán thường kém hiu qu. Để khc phc các hn chế
trên, thay vì s dng mt đim biên ta s dng c
p đim biên (mt thuc ,
mt thuc
), các cp đim này to nên tp nn vùng, kí hiu là NV và
phân tích toán t dò biên thành 2 bước:
41
Xác định cp đim nn vùng tiếp theo.
La chn đim biên
Trong đó bước th nht thc hin chc năng ca mt ánh x trên tp
NV lên NV và bước th hai thc hin chc năng chn đim biên.
Thut toán dò biên tng quát
Bước 1: Xác định cp nn-vùng xut phát
Bước 2: Xác định cp nn-vùng tiếp theo
Bước 3: La chn đim biên vùng
Bước 4: Nếu g
p li cp xut phát thì dng, nếu không quay li
bước 2.
Vic xác định cp nn-vùng xut phát được thc hin bng cách duyt
nh ln lượt t trên xung dưới và t trái qua phi ri kim tra điu kin la
chn cp nn-vùng. Do vic chn đim biên ch mang tính cht quy ước, nên
ta gi ánh x xác định cp nn-vùng tiếp theo là toán t
dò biên.
Định nghĩa 3.6 [Toán t dò biên]
Gi s T là mt ánh x như sau: T: NV
NV
(b,r) a (b’,r’)
Gi T là mt toán t dò biên cơ s nếu nó tho mãn điu kin: b’,r’ là
các 8-láng ging ca r.
Gi s (b,r)
NV; gi K(b,r) là hàm chn đim biên. Biên ca mt
dng
có th định nghĩa theo mt trong ba cách:
Tp nhng đim thuc có mt trên NV, tc là K(b,r)= r
Tp nhng đim thuc
có trên NV, tc là K(b,r)= b
Tp nhng đim o nm gia cp nn-vùng, tc là K(b,r) là nhng
đim nm gia hai đim b và r.
Cách định nghĩa th ba tương ng mi cp nn-vùng vi mt đim
biên. Còn đối vi cách định nghĩa th nht và th hai mt s cp nn-
vùng có th có chung mt đim biên. Bi vy, quá trình chn đi
m biên
được thc hin như sau:
i:= 1; (b
i
,r
i
):= (b
o
,r
o
);
While K(b
i
,r
i
)<>K(b
n
,r
n
) and i8 do
Begin (b
i+1
,r
i+1
)= T(b
i
,r
i
); i:= i+1; End;
Điu kin dng
Cp nn-vùng th n trùng vi cp nn vùng xut phát: (b
n
,r
n
)= (b
o
,r
o
)
42
* Xác định cp nn – vùng xut phát
Cp nn vùng xut phát được xác định bng cách duyt nh ln lượt t
trên xung dưới và t trái sang phi đim đem đầu tiên gp được cùng vi
đim trng trước đó (theo hướng 4) để to nên cp nn vùng xut phát.
* Xác định cp nn vùng tiếp theo
Đầu vào: pt, dir
Ví d: (3, 2) 4
Point orient
[]= {(1,0);(1;-1);(0;-1);(-1;-1);(-1;0);(-1,1);(0,1);(1,1)};
//Hàm tìm hướng có đim đen gn nht
BYTE GextNextDir(POINT pt, BYTE dir)
{
BYTE pdir= (dir + 7)%8;
do{
if(getpixel(pt. x+orient
[pdir]. x,pt.y+orient [pdir]. y))==BLACK)
return pdir;
pdir = (pdir + 7) %8;
}while(pdir ! = dir);
return. ERR; //Đim cô lp
}
//Gán giá tr cho bước tiếp theo
pdir = GetNextDir(pt, dir);
if(pdir==ERR) //Kim tra có là đim cô lp không?
return. ERR; //Đim cô lp
pt. x = pt. x + orient
[pdir]. x;
pt. y = pt. y + orient
[pdir]. y ;
Để tính giá tr cho hướng tiếp theo ta lp bng da trên giá tr pdir đã
tính được trước đó theo các kh năng có th xy ra:
43
pdir Đim trng trước đó Trng so vi đen mi
0 1 2
1 2 4
2 3 4
3 4 6
4 5 6
5 6 0
6 7 0
7 0 2
Do đó công thc để tính hướng tiếp theo s là :
dir= ((pdir+3)/ 2 * 2)%8 ;
44
Chương 4:
XƯƠNG VÀ CÁC K THUT TÌM XƯƠNG
4.1. GII THIU
Xương được coi như hình dng cơ bn ca mt đối tượng, vi s ít
các đim nh cơ bn. Ta có th ly được các thông tin v hình dng nguyên
bn ca mt đối tượng thông qua xương.
Mt định nghĩa xúc tích v xương da trên tính continuum (tương t
như hin tượng cháy đồng c) được đưa ra bi Blum (1976) như sau: Gi
thiết r
ng đối tượng là đồng nht được ph bi c khô và sau đó dng lên
mt vòng biên la. Xương được định nghĩa như nơi gp ca các vt la và
ti đó chúng được dp tt.
a) nh gc b) nh xương
Hình 4.1. Ví d v nh và xương
K thut tìm xương luôn là ch đề nghiên cu trong xnh
nhng năm gn đây. Mc dù có nhng n lc cho vic phát trin các
thut toán tìm xương, nhưng các phương pháp được đưa ra đều b mt
mát thông tin. Có th chia thành hai loi thut toán tìm xương cơ bn:
Các thut toán tìm xương da trên làm mnh
Các thut toán tìm xương không da trên làm mnh
4.2. TÌM XƯƠNG DA TRÊN LÀM MNH
4.2.1. Sơ lược v thut toán làm mnh
Thut toán làm mnh nh s nh phân là mt trong các thut toán quan
trng trong xnh và nhn dng. Xương cha nhng thông tin bt biến
v cu trúc ca nh, giúp cho quá trình nhn dng hoc vectơ hoá sau này.
45
Thut toán làm mnh là quá trình lp duyt và kim tra tt c các đim
thuc đối tượng. Trong mi ln lp tt c các đim ca đối tượng s được
kim tra: nếu như chúng tho mãn điu kin xoá nào đó tu thuc vào mi
thut toán thì nó s b xoá đi. Quá trình c lp li cho đến khi không còn
đim biên nào được xoá. Đối tượng
được bóc dn lp biên cho đến khi nào
b thu mnh li ch còn các đim biên.
Các thut toán làm mnh được phân loi da trên phương pháp x
các đim là thut toán làm mnh song song và thut toán làm mnh tun t.
Thut toán làm mnh song song, là thut toán mà trong đó các đim
được x lý theo phương pháp song song, tc là được x lý cùng mt lúc.
Giá tr ca mi đim sau mt ln lp ch ph thu
c vào giá tr ca các láng
ging bên cnh (thường là 8-láng ging) mà giá tr ca các đim này đã
được xác định trong ln lp trước đó. Trong máy có nhiu b vi x lý mi
vi x lý s x lý mt vùng ca đối tượng, nó có quyn đọc t các đim
vùng khác nhưng ch được ghi trên vùng ca nó x lý.
Trong thut toán làm mnh tun t các đim thuc đối tượ
ng s được
kim tra theo mt th t nào đó (chng hn các đim được xét t trái qua
phi, t trên xung dưới). Giá tr ca đim sau mi ln lp không nhng
ph thuc vào giá tr ca các láng ging bên cnh mà còn ph thuc vào
các đim đã được xét trước đó trong chính ln lp đang xét.
Cht lượng ca thut toán làm mnh đượ
c đánh giá theo các tiêu
chun được lit kê dưới đây nhưng không nht thiết phi tho mãn đồng
thi tt c các tiêu chun.
Bo toàn tính liên thông ca đối tượng và phn bù ca đối tượng
S tương hp gia xương và cu trúc ca nh đối tượng
Bo toàn các thành phn liên thông
Bo toàn các đim ct
Xương ch gm các đim biên, càng mnh càng tt
Bn vng đối vi nhiu
Xương cho phép khôi phc nh ban đầu ca đối tượng
Xương thu được chính gia đường nét ca đối tượng được
làm mnh
Xương nhn được bt biến vi phép quay.
46
4.2.2. Mt s thut toán làm mnh
Trong phn này đim qua mt s đặc đim, ưu và khuyết đim ca các
thut toán đã được nghiên cu.
1
o
. Thut toán làm mnh c đin là thut toán song song, to ra xương
8 liên thông, tuy nhiên nó rt chm, gây đứt nét, xoá hoàn toàn
mt s cu hình nh.
2
o
. Thut toán làm mnh ca Toumazet bo toàn tt c các đim ct
không gây đứt nét đối tượng. Tuy nhiên, thut toán có nhược đim
là rt chm, rt nhy cm vi nhiu, xương ch là 4-liên thông và
không làm mnh được vi mt s cu hình phc tp
3
o
. Thut toán làm mnh ca Y.Xia da trên đường biên ca đối
tượng, có th cài đặt theo c phương pháp song song và tun t.
Tc độ ca thut toán rt nhanh. Nó có nhược đim là gây đứt nét,
xương to ra là xương gi (có độ dày là 2 phn t nh).
4
o
. Thut toán làm mnh ca N.J.Naccache và R.Shinghal. Thut toán
ưu đim là nhanh, xương to ra có kh năng khôi phc nh ban
đầu ca đối tượng. Nhược đim chính ca thut toán là rt nhy
vi nhiu, xương nhn được phn ánh cu trúc ca đối tượng thp.
5
o
. Thut toán làm mnh ca H.E.Lu P.S.P Wang tương đối nhanh,
gi được tính liên thông ca nh, nhưng li có nhược đim là
xương to ra là xương 4-liên thông và xoá mt mt s cu
hình nh.
6
o
. Thut toán làm mnh ca P.S.P Wang và Y.Y.Zhang da trên
đường biên ca đối tượng, có th cài đặt theo phương pháp song
song hoc tun t, xương là 8-liên thông, ít chu nh hưởng ca
nhiu. Nhược đim chính ca thut toán là tc độ chm.
7
o
. Thut toán làm mnh song song thun tuý nhanh nht trong các
thut toán trên, bo toàn tính liên thông, ít chu nh hưởng ca
nhiu. Nhược đim là xoá hoàn toàn mt s cu hình nh, xương
to ra là xương 4-liên thông.
4.3. TÌM XƯƠNG KHÔNG DA TRÊN LÀM MNH
Để tách được xương ca đối tượng có th s dng đường biên ca đối
tượng. Vi đim p bt k trên đối tượng, ta bao nó bi mt đường biên.
Nếu như có nhiu đim biên có cùng khong cách ngn nht ti p thì p nm
trên trc trung v. Tp tt c các đim như vy lp thành trc trung v hay
xương ca đối tượ
ng. Vic xác định xương được tiến hành thông qua
hai bước:
47
Bước th nht, tính khong cách t mi đim nh ca đối tượng đến
đim biên gn nht. Như vy cn phi tính toán khong cách ti tt c
các đim biên ca nh.
Bước th hai, khong cách nh đã được tính toán và các đim nh có
giá tr ln nht được xem là nm trên xương ca đối tượng.
4.3.1. Khái quát v lược đồ Voronoi
Lược đồ Voronoi là mt công c hiu qu trong hình hc tính toán.
Cho hai đim P
i
, P
j
là hai phn t ca tp Ω gm n đim trong mt phng.
Tp các đim trong mt phng gn P
i
hơn P
j
là na mt phng H(P
i
, P
j
)
cha đim P
i
và b gii hn bi đường trung trc ca đon thng P
i
P
j
. Do
đó, tp các đim gn P
i
hơn bt k đim P
j
nào có th thu được bng cách
giao n-1 các na mt phng H(P
i
, P
j
):
V(P
i
) = H(P
i
, P
j
) ij (i= 1,...,n) (4.1)
Định nghĩa 4.1 [Đa giác/Sơ đồ Voronoi]
Sơ đồ Voronoi ca
Ω là hp ca tt c các V(P
i
)
Vor(
Ω) = V(P
i
) P
i
∈Ω (là mt đa giác) (4.2)
Định nghĩa 4.2 [Đa giác Voronoi tng quát]
Cho tp các đim
Ω, đa giác Voronoi ca tp con U ca Ω được định
nghĩa như sau:
V(U) =
{P| v U, w Ω \ U : d(P,v) < d(P,w)}
=
V(P
i
) P
i
U (4.3)
4.3.2. Trc trung v Voronoi ri rc
Định nghĩa 4.3 [Bn đồ khong cách - Distance Map]
Cho đối tượng S, đối vi mi (x, y)
S, ta tính giá tr khong cách
map(x, y) vi hàm khong cách d(.,.) như sau:
(x, y)S: map(x, y) = min d[(x, y), (x
i
, y
i
)] (4.4)
trong đó (x
i
, y
i
) B(S) - tp các đim biên ca S
Tp tt c các map(x, y), kí hiu là DM(S), được gi là bn đồ khong
cách ca S.
Chú ý: Nếu hàm khong cách d(.,.) là khong cách Euclide, thì phương
trình (4.4) chính là khong cách ngn nht t mt đim bên trong đối tượng
ti biên. Do đó, bn đồ khong cách được gi là bn đồ khong cách
Euclide EDM(S) ca S. Định nghĩa trên được dùng cho c hình ri rc ln
liên tc.
i
48
Định nghĩa 4.4 [Tp các đim biên sinh]
Cho map(x, y) là khong cách ngn nht t (x, y) đến biên (theo định
nghĩa 4.3). Ta định nghĩa: map
-1
(x, y) = {p| p B(S), d(p,
(x, y)):=map(x, y)
}
Khi đó tp các đim biên sinh ^B(S) được định nghĩa bi:
^B(S) =
map
-1
(x, y), (x, y) S (4.5)
Do S có th cha các đường biên ri nhau, nên ^B(S) bao gm nhiu
tp con, mi tp mô t mt đường biên phân bit:
^B(S)=
{B
1
(S),..B
N
(S)} (4.6)
Định nghĩa 4.5 [Trc trung v Voronoi ri rc (DVMA)]
Trc trung v Voronoi ri rc được định nghĩa là kết qu ca sơ đồ
Voronoi bc nht ri rc ca tp các đim biên sinh giao vi hình sinh S :
DVMA(^B(S)) = Vor(^B(S))
S (4.7)
4.3.3. Xương Voronoi ri rc
Định nghĩa 4.6 [Xương Voronoi ri rc - DiscreteVoronoi Skeleton]
Xương Voronoi ri rc theo ngưỡng T, kí hiu là Ske
DVMA
(^B(S),T)
(hoc Ske(^B(S),T)) là mt tp con ca trc trung v Voronoi:
Ske
DVMA
(^B(S),T)= {(x,y)| (x,y)DVMA(^B(S)), Ψ(x,y) > T} (4.8)
Ψ: là hàm hiu chnh.
D thy nếu ngưỡng T càng ln thì càng thì s lượng đim tham gia
trong xương Vonoroi càng ít (Hình 4.2).
Hình 4.2. Xương Voronoi ri rc nh hưởng ca các hàm hiu chnh khác nhau.
(a) nh nh phân. (b) Sơ đồ Voronoi. (c) Hiu chnh bi hàm Potential, T=9.0.
(d) Hiu chnh bi hàm Potential, T=18.0
a)
b)
c) d)
49
4.3.4. Thut toán tìm xương
Trong mc này s trình bày ý tưởng cơ bn ca thut toán tìm xương
và mô t bng ngôn ng ta Pascal.
Tăng trưởng: Vic tính toán sơ đồ Voronoi được bt đầu t mt đim
sinh trong mt phng. Sau đó đim sinh th hai được thêm vào và quá trình
tính toán tiếp tc vi đa giác Voronoi đã tìm được vi đim va được thêm
vào đó. C như thế, quá trình tính toán sơ
đồ Voronoi được thc hin cho
đến khi không còn đim sinh nào được thêm vào. Nhược đim ca chiến
lược này là mi khi mt đim mi được thêm vào, nó có th gây ra s phân
vùng toàn b các đa giác Voronoi đã được tính.
Chia để tr: Tp các đim biên đầu tiên được chia thành hai tp đim
có kích c bng nhau. Sau đó thut toán tính toán sơ đồ Voronoi cho c hai
tp con đim biên đó. Cui cùng, ng
ười ta thc hin vic ghép c hai sơ đồ
Voronoi trên để thu được kết qu mong mun. Tuy nhiên, vic chia tp các
đim biên thành hai phn không phi được thc hin mt ln, mà được lp
li nhiu ln cho đến khi vic tính toán sơ đồ Voronoi tr nên đơn gin. Vì
thế, vic tính sơ đồ Voronoi tr thành vn đề làm thế nào để trn hai sơ đồ
Voronoi li v
i nhau.
Thut toán s trình bày đây là s kết hp ca hai ý tưởng trên. Tuy
nhiên, nó s mang nhiu dáng dp ca thut toán chia để tr.
Hình 4.3 minh ho ý tưởng ca thut toán này. Mười mt đim biên
được chia thành hai phn (bên trái: 1- 6, bên phi: 7-11) bi đường gp
khúc
δ, và hai sơ đồ Voronoi tương ng Vor(S
L
) và Vor(S
R
). Để thu được
sơ đồ Vornonoi Vor(S
L
S
R
), ta thc hin vic trn hai sơ đồ trên và xác
định li mt s đa giác s b sa đổi do nh hưởng ca các đim bên cnh
thuc sơ đồ kia. Mi phn t ca
δ s là mt b phn ca đường trung trc
ni hai đim mà mt đim thuc Vor(S
L
) và mt thuc Vor(S
R
). Trước khi
xây dng
δ, ta tìm ra phn t đầu và cui ca nó. Nhìn vào hình trên, ta
nhn thy rng cnh
δ
1
δ
5
là các tia. D nhn thy rng vic tìm ra các
cnh đầu và cui ca
δ tr thành vic tìm cnh vào t
α
và cnh ra t
ω
.
Hình 4.3. Minh ho thut toán trn hai sơ đồ Voronoi
1
2
4
3
6
5
7
9
8
11
10
CH(S
R
)
CH(S
L
)
δ
1
δ
5
t
α
t
ω
50
Sau khi đã tìm được t
α
và t
ω
, các đim cui ca t
α
được s dng để xây
dng phn t đầu tiên ca
δ (δ
1
trong hình trên). Sau đó thut toán tìm đim
giao ca
δ vi Vor(S
L
) và Vor(S
R
). Trong ví d trên, δ đầu tiên giao vi
V(3). K t đây, các đim nm trên phn kéo dài
δ s gn đim 6 hơn đim
3. Do đó, phn t tiếp theo
δ
2
ca δ s thuc vào đường trung trc ca đim
6 và đim 7. Sau đó đim giao tiếp theo ca
δ s thuc và Vor(S
L
); δ bây
gi s đi vào V(9) và
δ
2
s được thay thế bi δ
3
. Quá trình này s kết thúc
khi
δ gp phn t cui δ
5
.
Trên đây ch là minh ho cho thut trn hai sơ đồ Voronoi trong chiến
lược chia để tr. Tuy nhiên, trong thut toán s trình bày đây thì s thc
hin có khác mt chút. Tp các đim nh không phi được đưa vào ngay t
đầu mà s được quét vào tng dòng mt. Gi s ti bước th i, ta đã thu được
mt sơ đồ Voronoi gm i-1 hàng các đim sinh Vor(S
i-1
). Tiếp theo, ta quét
ly mt hàng L
i
các đim nh t tp các đim biên còn li. Thc hin vic
tính sơ đồ Voronoi Vor(L
i
) cho hàng này, sau đó trn Vor(S
i-1
) vi Vor(L
i
).
Kết qu ta s được mt sơ đồ mi, và li thc hin vic quét hàng L
i+1
các
đim sinh còn li v.v.. Quá trình này s kết thúc khi không còn đim biên nào
để thêm vào sơ đồ Voronoi. Do Vor(L
i
) s có dng răng lược (nếu L
i
có k
đim thì Vor(L
i
) s gm k-1 đường thng đứng), nên vic trn Vor(S
i-1
) vi
Vor(L
i
) có phn đơn gin hơn.
Hình 4.4. Minh ho thut toán thêm mt đim biên vào sơ đồ Voronoi
Gii thut trên có th được mô t bng ngôn ng ta Pascal như sau:
Procedure VORONOI
(*S
i
: Tp các đim ca i dòng quét đầu tiên,
0 <= i <=i
MAX
,
Vor(S
i
) sơ đồ Vorronoi ca S
i
*)
δ
t
α
t
ω
p
1
p
2
p
3
p
4
p
5
p
6
p
7
p
8
p
9
p
10
v
1
v
2
v
3
v
4
v
5
v
6
Các đim thuc
S
i-1
51
Begin
i:=0; S
i
:=rng;
While (i<i
max
S
i
straight_line) do
Begin
(*Khi to sơ đồ Voronoi cho đến khi nó cha ít nht mt đỉnh*)
increment i;
GetScanLine L
i
;
Vor(S
i
) = VoroPreScan(Vor(S
i-1
, L
i
));
End
While (i < i
max
) do
Begin
Increment i;
GetScanLine L
i
;
Vor(L
i
) := các đường trung trc sinh bi các đim sinh thuc L
i
Vor(S
i
) := VoroLink(Vor(S
i-1
), Vor(L
i
));
End
End.
Gi s xét trên h to độ thc. nh vào được quét t dưới lên. To độ
y (biến i) tương ng vi tng dòng quét được tăng dn theo tng dòng.
Trong th tc trên, hàm quan trng nht là hàm VoroLink, hàm này thc
hin vic trn sơ đồ Voronoi ca L
i-1
dòng đã được quét trước đó vi sơ đồ
Voronoi ca dòng hin ti th i. Trong vòng lp trên, hàm VoroPreScan là
mt biến th ca hàm VoroLink, có nhim v khi to sơ đồ Voronoi và
thoát khi vòng lp ngay khi nó thành lp được sơ đồ Voronoi cha ít nht
mt đỉnh. Hàm VoroLink thc hin vic trn hai sơ đồ Voronoi Vor(S
i-1
) và
Vor(L
i
) vi nhau để thành Vor(S
i
).
52
Chương 5:
CÁC K THUT HU X
5.1. RÚT GN S LƯỢNG ĐIM BIU DIN
5.1.1. Gii thiu
Rút gn s lượng đim biu din là k thut thuc phn hu x lý. Kết
qu ca phn dò biên hay trích xương thu được 1 dãy các đim liên tiếp.
Vn đề đặt ra là hiu có th bá bt các đim thu được để gim thiu không
quan lưu tr và thun tin cho vic đối sách hay không.
Bài toán:
Cho đường cong gm n đim trong mt phng (x
1
, y
1
), (x
2
, y
2
)…
(x
n
,y
n
). Hãy b bt 1 s đim thuc đường cong sao cho đường cong mi
nhn được là (X
i1
; Y
i1
), (X
i2
; Y
i2
)… (X
im
; Y
im
) “gn ging” vi đường cong
ban đầu.
* Mt s độ đo “gn ging”
+ Chiu dài (chiu rng) ca hình ch nht nhá nht cha đường cong
+ Khong cách ln nht t đường cong đến đon thng ni 2 đầu mót
ca đường cong
+ T l gia chiu dài và chiu rng ca hình ch nht nhá nht cha
đường con
+ S l
n đường cong ct đon thng ni 2 đầu mót
5.1.2. Thut toán Douglas Peucker
5.1.2.1. Ý tưởng
Hình 5.1. Đơn gin hóa đường công theo thut toán Douglas Peucker
Ý tưởng cơ bn ca thut toán Douglas-Peucker là xét xem khong
cách ln nht t đường cong ti đon thng ni hai đầu mút đường cong
(xem Hình 5.1) có ln hơn ngưỡng
θ không. Nếu điu này đúng thì đim xa
nht được gi li làm đim chia đường cong và thut toán đưc thc hin
h > θ
θ
53
tương t vi hai đường cong va tìm được. Trong trường hp ngược li,
kết qu ca thut toán đơn gin hoá là hai đim đầu mút ca đường cong.
Thut toán Douglas-Peucker:
Bước 1: Chn ngưỡng θ.
Bước 2: Tìm khong cách ln nht t đường cong ti đon thng
ni hai đầu đon đường cong h.
Bước 3: Nếu h θ thì dng.
Bước 4: Nếu h > θ thì gi li đim đạt cc đại này và quay tr li
bước 1.
Nhn xét: Thut toán này t ra thun li đối vi các đường cong thu nhn
được mà gc là các đon thng, phù hp vi vic đơn gin hoá trong quá
trình véctơ các bn v k thut, sơ đồ thiết kế mch in v.v..
5.1.2.2. Chương trình
//Hàm tính đường cao t dinh đến đon thng ni hai
đim dau, cuoi
float Tinhduongcao (POINT dau, POINT cuoi, POINT dinh)
{
floot h;
⎢⎢tính đường cao
returm h ;
}
//Hàm đệ quy nhm đánh du loi b các đim trong đường cong
void DPSimple(POINT *pLINE,int dau,int cuoi,BOOL *chiso,float
θ)
{
int i, index = dau;
float h, hmax = 0;
for(i = dau + 1; i < cuoi; i++)
{
h= Tinhduongcao(pLINE
[dau], pLINE[cuoi]; pLINE[i]);
if(h > hmax)
{
hmax = h;
index = i;
54
}
}
if(hmax
θ)
for(i= dau + 1; i < cuoi, i++)
chiso
[i] = FALSE;
else
{
DPSimple(PLINE, dau, index, chiso,
θ);
DPSimple(PLINE, index, cuoi, chiso,
θ) ;
}
}
//Hàm rút gn s lượng đim DouglasPeucker
int DouglasPeucker(POINT *pLINE, int n, float
θ)
{
int i, j;
BOOL chiso
[MAX_PT];
for(i = 0; i < m; i++) //Tt c các đim được gi li
chiso
[i] = TRUE;
DPSimple(pLINE, 0, n – 1, chiso,
θ);
for(i = j = 0; i < n; i ++)
if (chiso
[i] ==TRUE)
pLINE
[j++] = pLINE[i];
return j;
}
5.1.3. Thut toán Band width
5.1.3.1. Ý tưởng
Trong thut toán Band Width, ta hình dung có mt di băng di chuyn
t đầu mút đường cong dc theo đường cong sao cho đường cong nm
trong di băng đó cho đến khi có đim thuc đường cong chm vào biên ca
di băng, đim này s được gi li. Quá trình này được thc hin vi phn
còn li ca đường cong bt đầu t đim va tìm được cho đến khi hết
đườ
ng cong. C th như sau:
55
Hình 5.2. Đơn gin hóa đường cong vi thut toán Band Width
Bt đầu bng vic xác định đim đầu tiên trên đường cong và coi đó
như là mt đim cht (P
1
). Đim th ba (P
3
) được coi là đim động. Đim
gia đim cht và đim động (P
2
) là đim trung gian. Ban đầu khong cách
t đim trung gian đến đon thng ni đim cht và đim động được tính
toán và kiếm tra. Nếu khong cách tính được này nh hơn mt ngưỡng θ
cho trước thì đim trung gian có th b đi, tiến trình tiếp tc vi đim cht
đim cht cũ, đim trung gian là đim động cũđim động là đim kế
tiếp sau đim động cũ. Trong trường hp ngược li, khong cách tính được
ln hơn ngưỡng
θ cho trước thì đim trung gian s được gi li, tiến trình
tiếp tc vi đim cht là đin trung gian, đim trung gian là đim động cũ
đim động là đim kế tiếp sau đim động cũ. Tiến trình được lp cho
đến hết đường cong (Hình 5.2 minh ha thut toán Band-Width).
Thut toán Band-Width:
Bước 1: Xác định đim đầu tiên trên đường cong và coi đó như
mt đim cht (P
1
). Đim th ba (P
3
) được coi là đim
động. Đim gia đim cht và đim động (P
2
) là đim
trung gian.
Bước 2: Tính khong cách t đim trung gian đến đon thng ni
hai đim cht và đim động.
Bước 3: Kim tra khong cách tìm được nếu nh hơn mt ngưỡng
θ cho trước thì đim trung gian có th b đi. Trong trường
hp ngược li đim cht chuyn đến đim trung gian.
Bước 4: Chu trình được lp li thì đim trung gian được chuyn
đến đim động và đim kế tiếp sau đim động được ch
định làm đim động mi..
Nhn xét: Thut toán này tăng tc độ trong trường hp đường ng cha
nhiu đim, điu đó có nghĩa là độ lch gia các đim trong
đường thng là
nh, hay độ dày nét ca đường được véctơ hoá là mnh.
d
i
P
3
P
2
P
4
d
k
P
5
P
1
56
5.1.3.2. Chương trình
//Hàm tính đường cao t đỉnh đến đon thng ni hai đim dau, cuoi
float Tinhduongcao(POINT dau, POINT cuoi, POINT dinh)
{
floot h;
⎢⎢tính đường cao
returm h ;
}
//Hàm đệ quy nhm đánh du loi b các đim trong đường cong
void BWSimple(POINT *pLINE, int chot, int tg, BOOL *chiso,
float
θ, int n)
{
if(Tinhduongcao(pLINE
[chot], pLINE[tg+1], pLINE[tg]) θ)
chiso
[tg] = 0;
else
chot = tg;
tg = tg + 1
if(tg < n - 1)
BWSimple (pLINE, chot, tg, chiso,
θ, n) ;
}
//Hàm rút gn s lượng đim BandWidth
int BandWidth(POINT *pLINE, int n, floot
θ)
{
int i, j;
BOOL chiso
[MAX_PT];
for (i = 0; i < n; i++)
chiso
[i]= TRUE; //Tt c các đim được gi li
BWSimple(pLINE, 0, 1, chiso,
θ, n);
for(i= j= 0; i < n; i++)
if(chiso
[i]== TRUE)
57
pLINE
[j ++1] = pLINE [i];
return j;
}
5.1.4. Thut toán Angles
5.1.4.1. Ý tưởng
Tương t như thut toán Band Width nhưng thay vic tính toán
khong cách bi tính góc. C th thut toán bt đầu vi đim đầu đường
cong (P
1
) là đim cht.
Hình 5.3. Đơn gin hóa đường cong vi thut toán Angles
Đim th 3 ca đường cong (P
3
) là đim động, đim gia đim cht và
đim động (P
2
) là đim trung gian
Góc to bi đim cht, trung gian, động vi đim trung gian là đỉnh
vic tính toán và kim tra
Nếu thì đim trung gian có th b đi trong trường hp ngược li đim
cht sđim trung gian cũ và quá trình lp vi đim trung gian là đim
động cũ, đim động mi là đim kế tiếp sau đi
m động cũ. Tiến trình thc
hin cho đến hết đường cong.
5.1.4.2. Chương trình
//Hàm tính đường cao t đỉnh đến đon thng ni hai đim dau, cuoi
float Tinhgoc(POINT dau, POINT cuoi, POINT dinh)
{
float
θ;
⎢⎢tinhgoc (t viết)
return
θ;
}
//Hàm đệ quy nhm đánh du loi b các đim trong đường cong
void ALSimple(POINT *pLINE,int chot,int tg,BOOL *chiso,float
θ,int n)
{
P
1
α
i
P
3
P
2
P
4
α
k
P
5
58
if(Tinhgoc(pLINE
[chot], pLINE[tg], pLINE[tg+1]) > θ)
chiso
[tg] = FALSE;
else
chot = tg;
tg = tg + 1;
if(tg < n - 1)
ALSimple(pLINE, chot, tg, chiso,
θ, n);
}
//Hàm rút gn s lượng đim Angles
int Angles(POINT *pLINE, int n, float
θ)
{
int i, j, chiso
[MAX];
for (i = 0; i < n; i++) //Tt c các đim được gi li
chiso
[i]= TRUE;
ALSiple (PLINE, 0, 1 chiso,
θ, n) ;
for (i = j = 0; i < n; i++)
if (chiso ==TRUE)
pLINE
[j++]= pLINE [i];
return j;
}
* Chú ý:
Vi θ= 0 thut toán DouglasPeucker và BandWidth s b đi các đim
gia thng hàng. Thut toán Angles phi có
θ= 180
o
để b đi các đim gia
thng hàng.
5.2. XP X ĐA GIÁC BI CÁC HÌNH CƠ S
Các đối tượng hình hc được phát hin thường thông qua các k thut
dò biên, kết qu tìm được này là các đường biên xác định đối tượng. Đó là,
mt dãy các đim liên tiếp đóng kính, s dng các thut toán đơn gin hoá
như Douglas Peucker, Band Width, Angle v.v.. ta s thu được mt polyline
hay nói khác đi là thu được mt đa giác xác định đối tượng du. Vn đề
ta cn phi xác định xem đối tượng có phi là đối t
ượng cn tách hay
không? Như ta đã biết mt đa giác có th có hình dng ta như mt hình cơ
59
s, có th có nhiu cách tiếp cn xp x khác nhau. Cách xp x da trên các
đặc trưng cơ bn sau:
Đặc trưng toàn cc: Các mô men thng kê, s đo hình hc như chu
vi, din tích, tp ti ưu các hình ch nht ph hay ni tiếp đa giác v.v..
Đặc trưng địa phương: Các s đo đặc trưng ca đường cong như
góc, đim li, lõm, un, c
c tr v.v..
Hình 5.4. Sơ đồ phân loi các đối tượng theo bt biến
Vic xp x t ra rt có hiu qu đối vi mt s hình phng đặc bit
như tam giác, đường tròn, hình ch nht, hình vuông, hình ellipse, hình
tròn và mt đa giác mu.
5.2.1 Xp x đa giác theo bt biến đồng dng
Hình 5.5. Xp x đa giác bi mt đa giác mu
Mt đa giác vi các đỉnh V
0
,..,V
m-1
được xp x vi đa giác mu
U
0
,..,U
n-1
vi độ đo xp x như sau:
EVU
n
dm
d
(, ) min=
≤≤01
Δ
,
Nhn dng đối tượng
Bt biến
đồng dng
Bt biến
Aphin
Đường tròn
Ellipse
Hình ch nht
Ellipse
Tam giác
T giác
60
Trong đó
Δ
d
R
jjdm
j
n
d
kR U a V=+
≤≤
+
=
min
,
()mod
02
0
1
2
2
θπα
θ
r
, k
area V V
area U U
m
n
=
()
()
01
01
L
L
, vi R
θ
phép quay quanh gc to độ mt góc
θ.
Trong đó,
Δ
d
được tính hiu qu bng công thc sau:
Δ
djdm jdm
j
n
jjjdm
j
n
j
n
j
n
d
V
n
VkUkUV=− +
++
=
+
=
=
=
∑∑
||| |||| |
( ) mod ( ) mod ( ) mod
2
0
1
22 2
0
1
0
1
0
1
1
2
đây U
j
, V
j
được hiu là các s phc ti các đỉnh tương ng. Khi
m >> n thì độ phc tp tính toán rt ln. Vi các hình đặc bit như hình
tròn, ellipse, hình ch nht, hình xác định duy nht bi tâm và mt đỉnh (đa
giác đều ) ta có th vn dng các phương pháp đơn gin hơn như bình
phương ti thiu, các bt biến thng kê và hình hc.
Định nghĩa 5.1
Cho đa giác Pg có các đỉnh U
0
, U
1
,..., U
n
(U
0
U
n
) Khi đó mô men bc
p+q được xác định như sau:
Mxydxdy
pq
pq
=
∫∫
Pg
.
Trong thc hành để tính tích phân trên người ta thường s dng công
thc Green hoc có th phân tích phn bên trong đa giác thành tng đại s
ca các tam giác có hướng
Δ OU
i
U
i+1
.
O(0,0)
fxyxydxdy
sign x y x y
fxyxydxdy
pq
ii i i
i
n
pq
OU U
ii
(,)
()
(,)
Pg
∫∫
∫∫
=
−×
++
=
+
11
0
1
1
Δ
Hình 5.6. Phân tích min đa giác thành tng đại s các min tam giác
U
0
U
1
U
2
U
3
U
n-
-
-
61
a. Xp x đa giác bng đường tròn
Dùng phương pháp bình phương ti thiu, ta có độ đo xp x:
E(Pg,Cr)= min ( )
,,abc R
ii i i
i
n
n
x y ax by c
=
++ + +
1
22 2
1
b. Xp x đa giác bng ellipse
Cũng như đối vi đường tròn phương trình xp x đối vi ellipse được
cho bi công thc:
E(Pg,El)= min ( )
,,,,abcde
iiiiii
i
n
n
xaybxycxdye
=
++ +++
R
1
22 2
1
Mt biến th khác ca phương pháp bình phương ti thiu khi xp x
các đường cong bc hai được đưa ra trong [7].
c. Xp x đa giác bi hình ch nht
S dng tính cht din tích bt biến qua phép quay, xp x theo din
tích như sau: Gi
μ
μ
μ
11 20 02
,,
là các mô men bc hai ca đa giác (tính theo
din tích). Khi đó góc quay được tính bi công thc sau:
tg2
ϕ
μ
μμ
=
2
- .
11
20 02
Gi din tích ca hình ch nht nh nht có các cnh song song vi
các trc quán tính và bao quanh đa giác Pg là S.
Kí hiu E(Pg, Rect)=
SareaPg ()
Hình 5.8. Xp x đa giác bng hình ch nht
ϕ
x
y
Hình 5.7. Xp x đa giác bng đường tròn
62
d. Xp x đa giác bi đa giác đều n cnh
Gi M(x
0
,y
0
) là trng tâm ca đa giác, ly mt đỉnh Q tu ý ca đa
giác, xét đa giác đều n cnh Pg’ to bi đỉnh Q vi tâm là M.
Kí hiu E(Pg, Pg’)= area Pg area Pg() (')
E(Pg, E
n
)=min E(Pg,Pg’) khi Q chy khp các đỉnh ca đa giác.
5.2.2 Xp x đa giác theo bt biến aphin
Trong [7] đưa ra mô hình chun tc v bt biến aphin, cho phép chúng
ta có th chuyn bài toán xp x đối tượng bi bt biến aphin v bài toán
xp x mu trên các dng chun tc. Như vy có th đưa vic đối sánh các
đối tượng vi mu bi các bt biến đồng dng, chng hn vic xp x bi
tam giác, hình bình hành, ellipse tương đương vi xp x tam giác đề
u, hình
vuông, hình tròn v.v... Th tc xp x theo bt biến aphin mt đa giác vi
hình cơ s được thc hin tun t như sau:
+ Bước 0
:
Phân loi bt biến aphin các dng hình cơ s
Dng hình cơ s Dng chun tc
Tam giác Tam giác đều
Hình bình hành Hình vuông
Ellipse Đường tròn
+ Bước 1:
Tìm dng chun tc cơ s Pg' tho mãn điu kin:
mm
mm
mm
01 10
02 20
13 31
0
1
0
==
==
==
(phép tnh tiến)
(phép co dãn theo hai trc x, y)
(**)
+ Bước 2
:
Xác định biến đổi aphin T chuyn đa giác thành đa giác Pg dng
chun tc (tho mãn tính cht (**)).
Xp x đa giác Pg vi dng chun tc cơ s Pg’ tìm được bước 1 vi
độ đo xp x E(Pg,Pg’).
+ Bước 3
:
Kết lun, đa giác ban đầu xp x T-1(Pg’) vi độ đo xp x E(Pg,Pg’).
63
Đối vi bước 1 trong [7] đã đưa ra hai ví d sau:
Ví d 1:
Tn ti duy nht tam giác đều ΔP1P2P3 tho mãn tính cht (**) là
P1=(0,-2
α),P2=
),( αα3
, P3=
),( αα 3
,
3
32
84
=α
.
Ví d 2:
Tn ti hai hình vuông P1P2 P3 P4 tho mãn tính cht (**)
Hình vuông th nht có 4 đỉnh tương ng là (-p,-p),(-p,p), (p,-
p),(p,p), vi p=
3
4
4
Hình vuông th hai có 4 đỉnh tương ng là (-p,0),(p,0), (0,-p),(0,p),
vi p=
3
4
.
5.3. BIN ĐỔI HOUGH
5.3.1. Biến đổi Hongh cho đường thng
Bng cách nào đó ta thu được mt s đim vn đề đặt ra là cn phi
kim tra xem các đim cóđường thng hay không
Bài toán:
Cho n đim (x
i
; y
i
) i = 1, n và ngưỡng θ hãy kim tra n đim có to
thành đường thng hay không?
* Ý tưởng
Gi s n đim nm trên cùng mt đường thng và đường thng có
phương trình
y = ax + b
Vì (x
i
, y
i
) i = 1, n thuc đường thng nên y
1
= ax
1
+ b, i = 1, n
b = - x
i
a + y
1
; i = 1, n
Như vy, mi đim (x
i
; y
i
) trong mt phng s tương ng vi mt s
đường thng b = - x
i
a + y
i
trong mt phng tham s a, b. n đim (x
i
; y
i
) i =
1, n thuc đường thng trong mt phng tương ng vi n đường thng
trong mt phng tham s a, b giao nhau ti 1 đim và đim giao chính là a,
b. Chính là h s xác định phương trình ca đường thng mà các đim
nm vào.
64
* Phương pháp:
- Xây dng mng ch s [a, b] và gán giá tr 0 ban đầu cho tt c các
phân t ca mng
- Vi mi (x
i
; y
i
) và a, b là ch s ca phn t mng tho mãn
b = - x
i
a + y
i
tăng giá tr ca phân t mng tương ng lên 1
- Tìm phn t mng có giá tr ln nht nếu giá tr ln nht tìm đưc so
vi s phân t ln hơn hoc bng ngưìng
θ cho trước thì ta có th kết lun
các đim nm trên cùng 1 đường thng và đường thng có phương trình
y = ax + b trong đó a, b tương ng là ch s ca phn t mng có giá tr ln
nht tìm được:
Ví d:
Cho 5 đim (0, 1); (1, 3); (2, 5); (3, 5); (4, 9) và
θ = 80%. Hãy kim
tra xem 5 đim đã cho có nm trên cùng mt đường thng hay không? Hãy
cho biết phương trình đường thng nếu có?
- Lp bng ch s
[a, b] và gán giá tr 0
+ (0, 1): b = 1
+ (1, 3): b = -a + 3
+ (2, 5): b = -2a + 5
+ (3, 5): b = -3a + 5
+ (4, 9): b = -4a + 9
- Tìm phn t ln nht có giá tr 4
4/5 = 80%
- Kết lun: 5 đim này nm trên cùng 1 đưng thng
Phương trình: y = 2x + 1
5.3.2. Biến đổi Hough cho đường thng trong ta độ cc
5.3.2.1. Đường thng Hough trong ta độ cc
65
OH.HA=0
Mi đim (x,y) trong mt phng được biu din bi cp (r,
ϕ) trong ta
độ cc.
Tương t mi đường thng trong mt phng cũng có th biu din bi
mt cp (r,
ϕ) trong ta độ cc vi r là khong cách t gc ta độ ti đường
thng đó và
ϕ là góc to bi trc 0X vi đường thng vuông góc vi nó,
hình 5.9 biu din đường thng hough trong ta độ Decard.
Ngược li, mi mt cp (r,
ϕ) trong to độ cc cũng tương ng biu
dim mt đường thng trong mt phng.
Gi s M(x,y) là m đim thuc đường thng được biu din bi (r,
ϕ),
gi H(X,Y) là hình chiếu ca gc to độ O trên đường thng ta có:
X= r. cos
ϕ và Y= r.sinϕ
Mt khác, ta có:
T đó ta có mi liên h gia (x,y) và (r,
ϕ) như sau: x*cosϕ+y*sinϕ= r.
Xét n đim thng hàng trong ta độ Đề các có phương trình
x*cos
ϕ
0
+y*sinϕ
0
= r
0
. Biến đổi Hough ánh x n đim này thành n đường sin
trong ta độ cc mà các đường này đều đi qua (r
0
,ϕ
0
). Giao đim (r
0
,ϕ
0
) ca
n đường sin s xác định mt đường thng trong h ta độ đề các. Như vy,
nhng đường thng đi qua đim (x,y) s cho duy nht mt cp (r,
ϕ) và có
bao nhiêu đường qua (x,y) s có by nhiêu cp giá tr (r,
ϕ).
5.3.2.2. Áp dng biến đổi Hough trong phát hin góc nghiêng văn bn
Ý tưởng ca vic áp dng biến đổi Hough trong phát hin góc nghiêng
văn bn là dùng mt mng tích lu để đếm s đim nh nm trên mt
đường thng trong không gian nh. Mng tích lu là mt mng hai chiu
vi ch s hàng ca mng cho biết góc lch
ϕ ca mt đường thng và ch
s ct chính là giá tr r khong cách t gc to độ ti đường thng đó. Sau
đó tính tng s đim nh nm trên nhng đường thng song song nhau theo
ϕ
y
0
H
x
x.cosϕ+y.sinϕ=r
Hình 5.9. Đường thng Hough trong to độ cc
r
66
các góc lch thay đổi. Góc nghiêng văn bn tương ng vi góc có tng gía
tr mng tích lu cc đại.
Theo biến đổi Hough, mi mt đường thng trong mt phng tương
ng được biu din bi mt cp (r,
ϕ). Gi s ta có mt đim nh (x,y) trong
mt phng, vì qua đim nh này có vô s đường thng, mi đường thng li
cho mt cp (r,
ϕ) nên vi mi đim nh ta s xác định được mt s cp
(r,
ϕ) thon phương trình Hough.
Hình v trên minh ho cách dùng biến đổi Hough để phát hin góc
nghiêng văn bn. Gi s ta có mt s đim nh, đây là nhng đim gia
đáy các hình ch nht ngoi tiếp các đối tượng đã được la chn t các
bước trước. đây, ta thy trên mt phng có hai đường thng song song
nhau. Đường thng th nht có ba đi
m nh nên giá tr mng tích lu bng
3, đường thng th hai có gia tr mng tích lu bng 4. Do đó, tng giá tr
mng tích lu cho cùng góc
ϕ trường hp này bng 7.
Gi Hough[360][Max] là mng tích lũy, gi s M và N tương ng là
chiu rng và chiu cao ca nh, ta có các bước chính trong quá trình áp
dng biến đổi Hough phát hin góc nghiêng văn bn như sau:
+ Bước 1
: Khai báo mng ch s Hough[ϕ][r] vi 0 ϕ 3600
và 0
r
NNMM ** +
.
+ Bước 2: Gán giá tr khi to bng 0 cho các phn t ca mng.
+ Bước 3
: Vi mi cp (x,y) là đim gia đáy ca hình ch nht
ngoi tiếp mt đối tượng.
- Vi mi
ϕ
i
t 0 đến 360 tính giá tr r
i
theo công thc
r
i
= x.cosϕ
i
+y.sinϕ
- Làm tròn giá tr r
i
thành s nguyên gn nht là r
0
- Tăng giá tr ca phn t mng Hough[
ϕ
i
][r
0
] lên mt
đơn v.
y
x.cos
ϕ
+y.sin
ϕ
=r
1
ϕ
Hough[
ϕ
][r
1
]=3
x
0
x.cos
ϕ
+y.sin
ϕ
=r
2
Hough[
ϕ
][r
1
]=4
Hình 5.10. ng dng biến đổi Hough phát hin góc
67
+ Bước 4
: Trong mng Hough[ϕ][r] tính tng giá tr các phn t theo
tng dòng và xác định dòng có tng giá tr ln nht.
Do s phn t ca mt phn t mng Hough[
ϕ
0
][r
0
] chính là s đim
nh thuc đường thng x.cos
ϕ
0
+y.sinϕ
0
= r
0
vì vy tng s phn t ca mt
hàng chính là tng s đim nh thuc các đường thng tương ng được
biu din bi góc
ϕ ca hàng đó. Do đó, góc nghiêng ca toán văn bn
chính là hàng có tng giá tr các phn t mng ln nht.
68
Ph lc 1:
MT S ĐỊNH DNG TRONG XNH
Hin nay trên thế gii có trên 50 khuôn dng nh thông dng.
Sau đây là mt s định dng nh hay dùng trong quá trình x nh
hin nay.
1. Định dng nh IMG
nh IMG là nh đen trng, phn đầu ca nh IMG có 16 byte
cha các thông tin:
6 byte đầu: dùng để đánh du định dng nh. Giá tr ca 6
byte này viết dưới dng Hexa: 0x0001 0x0008 0x0001
2 byte tiếp theo: cha độ dài mu tin. Đó là độ dài ca dãy
các byte k lin nhau mà dóy này s được lp li mt s ln
nào đó. S ln lp này s được lưu trong byte đếm. Nhiu dãy
ging nhau được lưu trong mt byte.
4 byte tiếp: mô tch c pixel.
2 byte tiếp: s pixel trên mt dòng nh.
2 byte cui: s dòng nh trong nh.
nh IMG được nén theo tng dòng, mi dòng bao gm các gói
(pack). Các dòng ging nhau cũng được nén thành mt gói. Có 4 loi
gói sau:
Loi 1: Gói các dòng ging nhau.
Quy cách gói tin này như sau: 0x00 0x00 0xFF Count. Ba byte
đầu tiên cho biết s các dãy ging nhau, byte cui cho biết s các
dòng ging nhau.
Loi 2: Gói các dãy ging nhau.
Quy cách gói tin này như sau: 0x00 Count. Byte th hai cho biết
s các dãy ging nhau đưc nén trong gói. Độ dài ca dãy ghi
đầu tp.
Loi 3: Dãy các Pixel không ging nhau, không lp li và
không nén được.
Quy cách gói tin này như sau: 0x80 Count. Byte th hai cho biết
độ dài dãy các pixel không ging nhau không nén được.
69
Loi 4: Dãy các Pixel ging nhau.
Tu theo các bít cao ca byte đầu tiên được bt hay tt. Nếu bít
cao được bt (giá tr 1) th đây là gói nén các byte ch gm bít 0, s
các byte được nén được tính bi 7 bít thp còn li. Nếu bt cao tt
(gi tr 0) thì đây là gói nén các byte gm toán bít 1. S các byte
được nén được tính bi 7 bít còn li.
Các gói tin ca file IMG rt đa dng do nh IMG là nh đen
trng, do vy ch cn 1 bít cho 1 pixel thay vì 4 hoc 8 như
đã nói
trên. Toàn b nh ch có nhng đim sáng và ti tương ng vi giá
tr 1 hoc 0. T l nén ca kiu định dng này là khá cao.
2. Định dng nh PCX
Định dng nh PCX là mt trong nhng định dng nh c đin.
Nó s dng phương pháp mó ho lot dài RLE (Run – Length –
Encoded) để nén d liu nh. Quá trnh nn và gii nn được thc
hin trên tng dũng nh. Thc tế, phương pháp gii nén PCX kém
hiu qu hơn so vi kiu IMG. Tp PCX gm 3 phn: đầu tp
(header), d liu nh (Image data) và bng màu m
rng.
Header ca tp PCX có kích thước c định gm 128 byte và
được phân b như sau:
1 byte: ch ra kiu định dng.Nếu là PCX/PCC thì nó luôn
giá tr là 0Ah.
1 byte: ch ra version s dng để nén nh, có th có các giá
tr sau:
+
0: version 2.5.
+
2: version 2.8 vi bng màu.
+
3: version 2.8 hay 3.0 không có bng màu.
+
5: version 3.0 c bng màu.
1 byte: ch ra phương pháp mã hoá. Nếu là 0 thì mã hoá theo
phương pháp BYTE PACKED, ngược li là phương
pháp RLE.
1 byte: S bít cho mt đim nh plane.
1 word: to độ góc trái ca nh. Vi kiu PCX nó có giá tr
(0,0), cũn PCC thì khác (0,0).
1 word: to độ góc phi dưới.
1 word: kích thước b rng và b cao ca nh.
70
1 word: s đim nh.
1 word: độ phân gii màn hình.
1 word.
48 byte: chia nó thành 16 nhóm, mi nhóm 3 byte. Mi nhóm
này cha thông tin v mt thanh ghi màu. Như vy ta có 16
thanh ghi màu.
1 byte: không dùng đến và luôn đặt là 0.
1 byte: s bt plane mà nh s dng. Vi nh 16 màu, giá tr
này là 4, vi nh 256 mu (1pixel/8bits) thì s bít plane li
là 1.
1 byte: s bytes cho mt dòng quét nh.
1 word: kiu bng màu.
58 byte: không dùng.
Định dng nh PCX thường được dùng để lưu tr nh và thao
tác đơn gin, cho phép nén và gii nén nhanh. Tuy nhiên, vì cu trúc
ca nó c định, nên trong mt s trường hp làm tăng kích thước lưu
tr. Cũng vì nhược đim này mà mt s ng dng s dng mt kiu
định dng khác mm do hơn: định dng TIFF (Targed Image File
Format) s mô t dưới đây.
3. Định dng nh TIFF
Kiu định dng TIFF được thiết kế để làm nh bt các vn đề
liên quan đến vic m rng tp nh c định. V cu trúc, nó cũng
gm 3 phn chính:
Phn Header(IFH): cú trong tt c cc tp TIFF và gm
8 byte:
+
1 word: ch ra kiu to tp trên máy tính PC hay máy
Macintosh. Hai loi này khác nhau rt ln th t các
byte lưu tr trong các s dài 2 hay 4 byte. Nếu trường
này có giá tr là 4D4Dh thì đó là nh cho máy Macintosh,
nếu là 4949h là ca máy PC.
+
1 word: version. t này luôn có giá tr là 42. đây là đặc
trưng ca file TIFF và không thay đổi.
+
2 word: giá tr Offset theo byte tính t đầu ti cu trúc
IFD là cu trúc th hai ca file. Th t các byte này ph
thuc vào du hiu trường đầu tiên.
71
Phn th 2(IFD): Không ngay sau cu trúc IFH mà v trí
được xác định bi trường Offset trong đầu tp. Có th có mt
hay nhiu IFD cùng tn ti trong mt file.
Mt IFD bao gm:
+
2 byte: cha các DE ( Directory Entry).
+
12 byte là các DE xếp liên tiếp, mi DE chiếm 12 byte.
+
4 byte: cha Offset tr ti IFD tiếp theo. Nếu đây là IFD
cui cùng thì trường này có giá tr 0.
Phn th 3: các DE: các DE có d dài c định gm 12 byte
và chia làm 4 phn:
+
2 byte: ch ra du hiu mà tp nh đó được xây dng.
+
2 byte: kiu d liu ca tham s nh. Có 5 kiu tham s
cơ bn:
1: BYTE (1 byte)
2: ASCII (1 byte)
3: SHORT (2 byte).
4: LONG (4 byte)
5: RATIONAL (8 byte)
+
4 byte: trường độ dài chưa s lượng ch mc ca kiu d
liu đó ch ra. Nó không phi là tng s byte cn thiết để
lưu tr. Để có s liu này ta cn nhân s ch mc vi kiu
d liu đã dùng.
+
4 byte: đó là Offset ti đim bt đầu d liu liên quan ti
du hiu, tc là liên quan vi DE không phi lưu tr vt
lý cùng vi nó nm mt v trí nào đó trong file.
D liu cha trong tp thường được t chc thành các nhóm
dòng (ct) quét ca d liu nh. Cách t chc này làm gim b nh
cn thiết cho vic đọc tp. Vic gi
i nén được thc hin theo 4 kiu
khác nhau được lưu tr trong byte du hiu nén.
72
4. Định dng file nh BITMAP
Mi file BITMAP gm đầu file cha các thông tin chung v file,
đầu thông tin cha các thông tin v nh, mt bng màu và mt mng
d liu nh. Khuôn dng được cho như sau:
BITMAPFILEHEADER bmfh;
BITMAPINFOHEADER bmih;
RGBQUAD aColors[];
BYTE aBitmapBits[];
Trong đó, các cu trúc được định nghĩa như sau:
typedef struct tagBITMAPFILEHEADER { /* bmfh */
UINT bfType;
DWORD bfSize;
UINT bfReserved1;
UINT bfReserved2;
DWORD bfOffBits;
} BITMAPFILEHEADER;
typedef struct tagBITMAPINFOHEADER { /* bmih */
DWORD biSize;
LONG biWidth;
LONG biHeight;
WORD biPlanes;
WORD biBitCount;
DWORD biCompression;
DWORD biSizeImage;
LONG biXPelsPerMeter;
LONG biYPelsPerMeter;
DWORD biClrUsed;
DWORD biClrImportant;
} BITMAPINFOHEADER, *LPBITMAPINFOHEADER;
vi
biSize kích thước ca BITMAPINFOHEADER
biWidth Chiu rng ca nh, tính bng s đim nh
biHeight Chiu cao ca nh, tính bng s đim nh
73
biPlanes S plane ca thiết b, phi bng 1
biBitCount S bit cho mt đim nh
biCompression Kiu nén
biSizeImage Kích thước ca nh tính bng byte
biXPelsPerMeter
độ phân gii ngang ca thiết b, tính bng đim nh trên
met
biYPelsPerMeter
độ phân gii dc ca thiết b, tính bng đim nh trên
met
biClrUsed S lượng các màu thc s được s dng
biClrImportant
S lượng các màu cn thiết cho vic hin th, bng 0 nếu
tt c các màu đều cn để hin th
Nếu bmih.biBitCount > 8 thì mng màu rgbq[] trng, ngược li thì
mng màu có 2<< bmih.biBitCount phn t.
typedef struct tagRGBQUAD { /* rgbq */
BYTE rgbBlue;
BYTE rgbGreen;
BYTE rgbRed;
BYTE rgbReserved;
} RGBQUAD;
Ta cũng có:
typedef struct tagBITMAPINFO {
BITMAPINFOHEADER bmiHeader;
RGBQUAD bmiColors[1];
} BITMAPINFO, *PBITMAPINFO;
74
Ph lc 2:
CÁC BƯỚC THAO TÁC VI FILE AVI
AVI là chun video thường được tích hp trong các thư vin ca
các môi trường lp trình. Để x lý video, cn có các thao tác cơ bn
để chuyn v xnh các khung hình (các frames).
1. Bước 1: Mđóng thư vin
Trước mi thao tác vi file AVI, chúng ta phi m thư vin:
AVIFileInit( )
Hàm này không cn tham s, có nhim v khi động thư vin
cung cp các hàm thao tác vi file AVI. (Đó là thư vin vfw32.lib,
được khai báo trong file vfw.h).
Sau tt c các thao tác bn phi nh đóng thư vin đã mc
đầu, ch bng lnh:
AVIFileExit( )
Nếu thiếu bt c hàm nào, dù là m hay đóng thư vin thì trình
biên dch đều s thông báo li.
2. Bước 2: Mđóng file AVI để thao tác:
Sau khi m thư vin, bn phi m file AVI bn định thao tác:
AVIFileOpen(PAVIFILE* ppfile, LPCSTR fname, UINT mode,
CLSID pclsidHandler)
Thc cht, hàm này to ra mt vùng đệm cha con tr tr đến
file có tên là fname cn m. Và ppfile là con tr tr đến vùng b đệm
đó. Tham s mode quy định kiu m file; chng hn OF_CREATE
để to mi, OF_READ để đọc, OF_WRITE để ghi …. Tham s cui
dùng
là NULL.
Trước khi đóng thư vin, bn phi đóng file AVI đã m, bng
cách dùng hàm:
AVIFileRelease(PAVIFILE pfile)
Trong đó, pfile là con tr tr đến file cn đóng.
75
3. Bước 3:
M dòng d liu hình nh hay âm thanh trong file AVI đã m ra
để thao tác:
AVIFileGetStream(PAVIFILE pfile, PAVISTREAM * ppavi,
DWORD fccType, LONG lParam)
Trong đó, pfile là con tr đến file đã m; ppavi tr đến dòng d
liu kết qu; fccType là loi dòng d liu chn để m, là
streamtypeAUDIO nếu là tiếng và streamtypeVIDEO nếu là hình,…
lParam đếm s loi dòng được m, là 0 nếu ch thao tác vi mt loi
dòng d liu.
Sau các thao tác vi dòng d liu này, bn nh phi đóng nó li:
AVIStreamRelease(PAVITREAM pavi).
4. Bước 4: Trường hp thao tác vi d liu hình ca phim
Chun b cho thao tác vi khung hình (frames):
AVIStreamGetFrameOpen(PAVISTREAM pavi,
LPBITMAPINFOHEADER lpbiWanted)
Trong đó pavi tr đến dòng d liu đã m, lpbiWanted là con
tr tr đến cu trúc mong mun ca hình nh, ta dùng NULL để s
dng cu trúc mc định.
Hàm này tr v đối tượng có kiu PGETFRAME để dùng cho
bước 5.
Sau khi thao tác vi các frame ri, phi gi hàm :
AVIStreamGetFrameClose(PGETFRAME pget)
5. Bước 5: Thao tác vi frame
Dùng hàm
AVIStreamGetFrame(PGETFRAME pget, LONG lpos)
Hàm này tr v con tr tr đến d liu ca frame th lpos. D
liu đó có kiu là DIB đã định khi.
Thc hin các thao tác mong mun.
76
TÀI LIU THAM KHO
[1]. Lương Mnh Bá, Nguyn Thanh Thy (2002), N
hp Môn Xnh
s
, Nxb Khoa hc và K thut, 2002.
[2]. Anil K.Jain (1989),
Fundamental of Digital Image Processing.
Prentice Hall
, Engwood cliffs.
[3]. J.R.Paker (1997),
Algorithms for Image processing and Computer
Vision
. John Wiley & Sons, Inc.
[4]. Randy Crane (1997),
A simplified approach to image processing,
Prentice-Hall, Inc.
[5]. John C.Russ (1995),
The Image Procesing Handbook. CRC Press, Inc.
[6]. Adrian Low (1991),
Introductory Computer Vision and Image
Processing
, Copyright (c) 1991 by McGrow Hill Book Company
(UK) Limited.
[7]. T. Pavlidis (1982),
Algorithms for Graphics and Image Processing,
Computer Science Press.
| 1/76

Preview text:

ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
GIÁO TRÌNH MÔN HỌC XỬ LÝ ẢNH
Người soạn : TS. ĐỖ NĂNG TOÀN, TS. PHẠM VIỆT BÌNH
Thái Nguyên, Tháng 11 năm 2007 1 LỜI NÓI ĐẦU
Khoảng hơn mười năm trở lại đây, phần cứng máy tính và các thiết bị
liên quan đã có sự tiến bộ vượt bậc về tốc độ tính toán, dung lượng chứa,
khả năng xử lý v.v.. và giá cả đã giảm đến mức máy tính và các thiết bị liên
quan đến xử lý ảnh đã không còn là thiết bị chuyên dụng nữa. Khái niệm
ảnh số đã trở nên thông dụng với hầu hết mọi người trong xã hội và việc
thu nhận ảnh số bằng các thiết bị cá nhân hay chuyên dụng cùng với việc
đưa vào máy tính xử lý đã trở nên đơn giản.
Trong hoàn cảnh đó, xử lý ảnh là một lĩnh vực đang được quan tâm và
đã trở thành môn học chuyên ngành của sinh viên ngành công nghệ thông
tin trong nhiều trường đại học trên cả nước. Tuy nhiên, tài liệu giáo trình
còn là một điều khó khăn. Hiện tại chỉ có một số ít tài liệu bằng tiếng Anh
hoặc tiếng Pháp, tài liệu bằng tiếng Việt thì rất hiếm. Với mong muốn đóng
góp vào sự nghiệp đào tạo và nghiên cứu trong lĩnh vực này, chúng tôi biên
soạn cuốn giáo trình Xử lý ảnh dựa trên đề cương môn học đã được duyệt.
Cuốn sách tập trung vào các vấn đề cơ bản của xử lý ảnh nhằm cung cấp
một nền tảng kiến thức đầy đủ và chọn lọc nhằm giúp người đọc có thể tự
tìm hiểu và xây dựng các chương trình ứng dụng liên quan đến xử lý ảnh.
Giáo trình được chia làm 5 chương và phần phụ lục: Chương 1, trình
bày Tổng quan về xử lý ảnh, các khai niệm cơ bản, sơ đồ tổng quát của một
hệ thống xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh. Chương 2, trình
bày các kỹ thuật nâng cao chất lượng ảnh dựa vào các thao tác với điểm
ảnh, nâng cao chất lượng ảnh thông qua việc xử lý các điểm ảnh trong lân
cận điểm ảnh đang xét. Chương này cũng trình bày các kỹ thuật nâng cao
chất lượng ảnh nhờ vào các phép toán hình thái. Chương 3, trình bày các kỹ
thuật cơ bản trong việc phát hiện biên của các đối tượng ảnh theo cả hai
khuynh hướng: Phát hiện biên trực tiếp và phát hiện biên gián tiếp. Chương
4 thể hiện cách kỹ thuật tìm xương theo khuynh hướng tính toán trục trung
vị và hướng tiếp cận xấp xỉ nhờ các thuật toán làm mảnh song song và gián
tiếp. Và cuối cùng là Chương 5 với các kỹ thuật hậu xử lý.
Giáo trình được biên soạn dựa trên kinh nghiệm giảng dạy của tác giả
trong nhiều năm tại các khóa đại học và cao học của ĐH Công nghệ -
ĐHQG Hà Nội, ĐH Khoa học tự nhiên – ĐHQG Hà Nội, Khoa Công nghệ
thông tin – ĐH Thái Nguyên v.v.. Cuốn sách có thể làm tài liệu tham khảo
cho sinh viên các hệ kỹ sư, cử nhân và các bạn quan tâm đến vấn đề nhận dạng và xử lý ảnh. 2
Các tác giả bày tỏ lòng biết ơn chân thành tới các bạn đồng nghiệp
trong Phòng Nhận dạng và công nghệ tri thức, Viện Công nghệ thông tin,
Bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin, ĐH Thái Nguyên,
Khoa Công nghệ thông tin, ĐH Công nghệ, ĐHQG Hà Nội, Khoa Toán –
Cơ – Tin, ĐH Khoa học tự nhiên, ĐHQG Hà Nội đã động viên, góp ý và
giúp đỡ để hoàn chỉnh nội dung cuốn sách này. Xin cám ơn Lãnh đạo Khoa
Công nghệ thông tin, ĐH Thái Nguyên, Ban Giám đốc ĐH Thái Nguyên đã
hỗ trợ và tạo điều kiện để cho ra đời giáo trình này.
Mặc dù rất cố gắng nhưng tài liệu này chắc chắn không tránh khỏi
những sai sót. Chúng tôi xin trân trọng tiếp thu tất cả những ý kiến đóng
góp của bạn đọc cũng như các bạn đồng nghiệp để có chỉnh lý kịp thời.
Thư góp ý xin gửi về: Phạm Việt Bình, Khoa Công
nghệ thông tin – ĐH Thái nguyên. Xã
Quyết Thắng, Tp. Thái Nguyên Điện thoại: 0280.846506 Email: pvbinh@ictu.edu.vn
Thái Nguyên, ngày 22 tháng 11 năm 2007 CÁC TÁC GIẢ 3 MỤC LỤC
LỜI NÓI ĐẦU.......................................................................................................................................................................2
MỤC LỤC ..................................................................................................................................................................................4
Chương 1: TỔNG QUAN VỀ XỬ LÝ ẢNH.....................................................................................7
1.1. XỬ LÝ ẢNH, CÁC VẤN ĐỀ CƠ BẢN TRONG XỬ LÝ ẢNH..................7
1.1.1. Xử lý ảnh là gì?............................................................................................................................................7
1.1.2. Các vấn đề cơ bản trong xử lý ảnh ........................................................................................7
1.1.2.1 Một số khái niệm cơ bản ........................................................................................................7
1.1.2.2 Nắn chỉnh biến dạng....................................................................................................................8
1.1.2.3 Khử nhiễu.................................................................................................................................................9
1.1.2.4 Chỉnh mức xám: ...............................................................................................................................9
1.1.2.5 Trích chọn đặc điểm ....................................................................................................................9
1.1.2.6 Nhận dạng............................................................................................................................................ 10
1.1.2.7 Nén ảnh................................................................................................................................................... 11
1.2. THU NHẬN VÀ BIỂU DIỄN ẢNH ........................................................................................... 11
1.2.1. Thu nhận, các thiết bị thu nhận ảnh.................................................................................. 11
1.2.2. Biểu diễn ảnh.............................................................................................................................................. 12
1.2.2.1. Mô hình Raster............................................................................................................................. 12
1.2.2.2. Mô hình Vector............................................................................................................................ 13
Chương 2: CÁC KỸ THUẬT NÂNG CAO CHẤT LƯỢNG ẢNH................... 14
2.1. CÁC KỸ THUẬT KHÔNG PHỤ THUỘC KHÔNG GIAN.......................... 14
2.1.1. Giới thiệu......................................................................................................................................................... 14
2.1.2. Tăng giảm độ sáng ............................................................................................................................... 14
2.1.3. Tách ngưỡng................................................................................................................................................ 15
2.1.4. Bó cụm............................................................................................................................................................... 15
2.1.5. Cân bằng histogram ............................................................................................................................ 16
2.1.6. Kỹ thuật tách ngưỡng tự động ................................................................................................ 17
2.1.7. Biến đổi cấp xám tổng thể........................................................................................................... 18
2.2. CÁC KỸ THUẬT PHỤ THUỘC KHÔNG GIAN..................................................... 20
2.2.1. Phép cuộn và mẫu ................................................................................................................................. 20 4
2.2.2. Một số mẫu thông dụng.................................................................................................................. 21
2.2.3. Lọc trung vị .................................................................................................................................................. 22
2.2.4. Lọc trung bình ........................................................................................................................................... 24
2.2.5. Lọc trung bình theo k giá trị gần nhất............................................................................ 25
2.3. CÁC PHÉP TOÁN HÌNH THÁI HỌC .................................................................................... 26
2.3.1. Các phép toán hình thái cơ bản.............................................................................................. 26
2.3.2. Một số tính chất của phép toán hình thái.................................................................... 27
Chương 3: BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN ..................... 32
3.1. GIỚI THIỆU............................................................................................................................................................ 32
3.2. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN TRỰC TIẾP ................................. 32
3.2.1. Kỹ thuật phát hiện biên Gradient......................................................................................... 32
3.2.1.1. Kỹ thuật Prewitt.......................................................................................................................... 34
3.2.1.2. Kỹ thuật Sobel............................................................................................................................... 35
3.2.1.3. Kỹ thuật la bàn.............................................................................................................................. 35
3.2.2. Kỹ thuật phát hiện biên Laplace........................................................................................... 36
3.3. PHÁT HIỆN BIÊN GIÁN TIẾP....................................................................................................... 37
3.3.1 Một số khái niệm cơ bản................................................................................................................. 37
3.3.2. Chu tuyến của một đối tượng ảnh....................................................................................... 38
3.3.3. Thuật toán dò biên tổng quát.................................................................................................... 40
Chương 4: XƯƠNG VÀ CÁC KỸ THUẬT TÌM XƯƠNG ........................................ 44
4.1. GIỚI THIỆU............................................................................................................................................................ 44
4.2. TÌM XƯƠNG DỰA TRÊN LÀM MẢNH........................................................................... 44
4.2.1. Sơ lược về thuật toán làm mảnh ........................................................................................... 44
4.2.2. Một số thuật toán làm mảnh...................................................................................................... 46
4.3. TÌM XƯƠNG KHÔNG DỰA TRÊN LÀM MẢNH................................................ 46
4.3.1. Khái quát về lược đồ Voronoi................................................................................................. 47
4.3.2. Trục trung vị Voronoi rời rạc................................................................................................... 47
4.3.3. Xương Voronoi rời rạc.................................................................................................................... 48
4.3.4. Thuật toán tìm xương........................................................................................................................ 49
Chương 5: CÁC KỸ THUẬT HẬU XỬ LÝ.................................................................................. 52
5.1. RÚT GỌN SỐ LƯỢNG ĐIỂM BIỂU DIỄN..................................................................... 52
5.1.1. Giới thiệu......................................................................................................................................................... 52 5
5.1.2. Thuật toán Douglas Peucker..................................................................................................... 52
5.1.2.1. Ý tưởng ................................................................................................................................................. 52
5.1.2.2. Chương trình................................................................................................................................... 53
5.1.3. Thuật toán Band width .................................................................................................................... 54
5.1.3.1. Ý tưởng ................................................................................................................................................. 54
5.1.3.2. Chương trình................................................................................................................................... 56
5.1.4. Thuật toán Angles................................................................................................................................. 57
5.1.4.1. Ý tưởng ................................................................................................................................................. 57
5.1.4.2. Chương trình................................................................................................................................... 57
5.2. XẤP XỈ ĐA GIÁC BỞI CÁC HÌNH CƠ SỞ.................................................................... 58
5.2.1 Xấp xỉ đa giác theo bất biến đồng dạng ........................................................................ 59
5.2.2 Xấp xỉ đa giác theo bất biến aphin ...................................................................................... 62
5.3. BIẾN ĐỔI HOUGH........................................................................................................................................ 63
5.3.1. Biến đổi Hongh cho đường thẳng....................................................................................... 63
5.3.2. Biến đổi Hough cho đường thẳng trong tọa độ cực....................................... 64
5.3.2.1. Đường thẳng Hough trong tọa độ cực............................................................... 64
5.3.2.2. Áp dụng biến đổi Hough trong phát hiện góc nghiêng văn bản
..................................................................................................................... 65
PHỤ LỤC................................................................................................................................................................................ 68
TÀI LIỆU THAM KHẢO.................................................................................................................................... 76 6 Chương 1:
TỔNG QUAN VỀ XỬ LÝ ẢNH
1.1. XỬ LÝ ẢNH, CÁC VẤN ĐỀ CƠ BẢN TRONG XỬ LÝ ẢNH
1.1.1. Xử lý ảnh là gì?
Con người thu nhận thông tin qua các giác quan, trong đó thị giác
đóng vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của
phần cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ
và có nhiều ứng dụng trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai
trò quan trọng trong tương tác người máy.
Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào
nhằm cho ra 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. Ảnh “Tốt hơn” Ảnh XỬ LÝ ẢNH Kết luận
Hình 1.1. Quá trình xử lý ảnh
Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem
như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào
đó của đối tượng trong không gian và nó có thể xem như một hàm n biến
P(c1, c2,..., cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh n chiều.
Sơ đồ tổng quát của một hệ thống xử lý ảnh: Hệ quyết định Thu nhận ảnh Trích chọn Hậu (Scanner, Tiền xử lý Đối sánh rút đặc điểm Camera,Sensor) xử lý ra kết luận Lưu trữ
Hình 1.2. Các bước cơ bản trong một hệ thống xử lý ảnh
1.1.2. Các vấn đề cơ bản trong xử lý ảnh
1.1.2.1 Một số khái niệm cơ bản
* Ảnh và điểm ảnh: 7
Điểm ảnh được xem như là dấu hiệu hay cường độ sáng tại 1 toạ độ
trong không gian của đối tượng và ảnh được xem như là 1 tập hợp các điểm ảnh. * Mức xám, màu
Là số các giá trị có thể có của các điểm ảnh của ảnh
1.1.2.2 Nắn chỉnh biến dạng
Ảnh thu nhận thường bị biến dạng do các thiết bị quang học và điện tử. P’ Pi i ×f(Pi) Ảnh thu nhận Ảnh mong muốn
Hình 1.3. Ảnh thu nhận và ảnh mong muốn
Để khắc phục người ta sử dụng các phép chiếu, các phép chiếu thường
được xây dựng trên tập các điểm điều khiển.
Giả sử (Pi, Pi’) i = ,1 n có n các tập điều khiển
Tìm hàm f: Pi a f (Pi) sao cho ∑n f (P ) 2 ' − P → min i i i 1 =
Giả sử ảnh bị biến đổi chỉ bao gồm: Tịnh tiến, quay, tỷ lệ, biến dạng
bậc nhất tuyến tính. Khi đó hàm f có dạng:
f (x, y) = (a1x + b1y + c1, a2x + b2y + c2) Ta có: n n
φ = ∑( f (Pi) − Pi' 2) = ∑ ([a x + b y + c x 2 ' a x b y c y 2 ' 1 i 1 i 1 i ) + ( + + − 2 i 2 i 2 i ) ] i=1 i=1 Để cho φ → min 8 ⎧ ∂φ ⎧ n n n n ⎪ = 0 ⎪∑ a x2 + b x y c x x x' 1 i ∑ + 1 i i ∑ = 1 ii i ⎪∂a1 ⎪ i=1 i=1 i=1 i=1 ⎪ ∂φ ⎪ n n n n
= 0 ⇔ ⎨∑ a x y + b y2 c y y x' 1 i i ∑ + 1 i ∑ = 1 ii i ⎪∂b1 ⎪ i=1 i=1 i=1 i=1 ⎪ ∂φ ⎪ n n n ⎪ = 0 ⎪∑ a x + b y nc x' 1 i ∑ + = 1 i 1 ∑ ⎩∂c1 ⎩ i i=1 i=1 i=1
Giải hệ phương trình tuyến tính tìm được a1, b1, c1
Tương tự tìm được a2, b2, c2
⇒ Xác định được hàm f 1.1.2.3 Khử nhiễu
Có 2 loại nhiễu cơ bản trong quá trình thu nhận ảnh
• Nhiều hệ thống: là nhiễu có quy luật có thể khử bằng các phép biến đổi
• Nhiễu ngẫu nhiên: vết bẩn không rõ nguyên nhân → khắc phục bằng các phép lọc
1.1.2.4 Chỉnh mức xám:
Nhằm khắc phục tính không đồng đều của hệ thống gây ra. Thông
thường có 2 hướng tiếp cận:
• Giảm số mức xám: Thực hiện bằng cách nhóm các mức xám gần
nhau thành một bó. Trường hợp chỉ có 2 mức xám thì chính là
chuyển về ảnh đen trắng. Ứng dụng: In ảnh màu ra máy in đen trắng.
• Tăng số mức xám: Thực hiện nội suy ra các mức xám trung gian
bằng kỹ thuật nội suy. Kỹ thuật này nhằm tăng cường độ mịn cho ảnh
1.1.2.5 Trích chọn đặc điểm
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 (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc 9
điểm” (feature mask) 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 v.v..)
Đặ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” (zero crossing) v.v..
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. 1.1.2.6 Nhận dạng
Nhận dạng tự động (automatic recognition), mô tả đối tượng, phân
loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy,
được ứng dụng trong nhiều ngành khoa học khác nhau. Tuy nhiên, một câu
hỏi đặt ra là: mẫu (pattern) là gì? Watanabe, một trong những người đi đầu
trong lĩnh vực này đã định nghĩa: “Ngược lại với hỗn loạn (chaos), mẫu là
một thực thể (entity), được xác định một cách ang áng (vaguely defined) và
có thể gán cho nó một tên gọi nào đó”. Ví dụ mẫu có thể là ảnh của vân tay,
ảnh của một vật nào đó được chụp, một chữ viết, khuôn mặt người hoặc
một ký đồ tín hiệu tiếng nói. Khi biết một mẫu nào đó, để nhận dạng hoặc
phân loại mẫu đó có thể:
Hoặc phân loại có mẫu (supervised classification), chẳng hạn phân
tích phân biệt (discriminant analyis), trong đó mẫu đầu vào được định danh
như một thành phần của một lớp đã xác định.
Hoặc phân loại không có mẫu (unsupervised classification hay
clustering) trong đó các mẫu được gán vào các lớp khác nhau dựa trên một
tiêu chuẩn đồng dạng nào đó. Các lớp này cho đến thời điểm phân loại vẫn
chưa biết hay chưa được định danh.
Hệ thống nhận dạng tự động bao gồm ba khâu tương ứng với ba giai
đoạn chủ yếu sau đây:
1o. Thu nhận dữ liệu và tiền xử lý.
2o. Biểu diễn dữ liệu.
3o. Nhận dạng, ra quyết định.
Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là:
1o. Đối sánh mẫu dựa trên các đặc trưng được trích chọn. 2o. Phân loại thống kê. 3o. Đối sánh cấu trúc. 10
4o. Phân loại dựa trên mạng nơ-ron nhân tạo.
Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp
cận đơn lẻ để phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều
phương pháp và cách tiếp cận khác nhau. Do vậy, các phương thức phân
loại tổ hợp hay được sử dụng khi nhận dạng và nay đã có những kết quả có
triển vọng dựa trên thiết kế các hệ thống lai (hybrid system) bao gồm nhiều mô hình kết hợp.
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ề thuật giải, 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. 1.1.2.7 Nén ảnh
Nhằm giảm thiểu không gian lưu trữ. Thường được tiến hành theo cả
hai cách khuynh hướng là nén có bảo toàn và không bảo toàn thông tin.
Nén không bảo toàn thì thường có khả năng nén cao hơn nhưng khả năng
phục hồi thì kém hơn. Trên cơ sở hai khuynh hướng, có 4 cách tiếp cận cơ bản trong nén ảnh:
• Nén ảnh thống kê: Kỹ thuật nén này dựa vào việc thống kê tần xuất
xuất hiện của giá trị các điểm ảnh, trên cơ sở đó mà có chiến lược
mã hóa thích hợp. Một ví dụ điển hình cho kỹ thuật mã hóa này là *.TIF
• Nén ảnh không gian: Kỹ thuật này dựa vào vị trí không gian của
các điểm ảnh để tiến hành mã hóa. Kỹ thuật lợi dụng sự giống nhau
của các điểm ảnh trong các vùng gần nhau. Ví dụ cho kỹ thuật này là mã nén *.PCX
• Nén ảnh sử dụng phép biến đổi: Đây là kỹ thuật tiếp cận theo
hướng nén không bảo toàn và do vậy, kỹ thuật thướng nến hiệu quả
hơn. *.JPG chính là tiếp cận theo kỹ thuật nén này.
• Nén ảnh Fractal: Sử dụng tính chất Fractal của các đối tượng ảnh,
thể hiện sự lặp lại của các chi tiết. Kỹ thuật nén sẽ tính toán để chỉ
cần lưu trữ phần gốc ảnh và quy luật sinh ra ảnh theo nguyên lý Fractal
1.2. THU NHẬN VÀ BIỂU DIỄN ẢNH
1.2.1. Thu nhận, các thiết bị thu nhận ảnh 11
Các thiết bị thu nhận ảnh bao gồm camera, scanner các thiết bị thu
nhận này có thể cho ảnh đen trắng
Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 loại ảnh thông dụng Raster, Vector.
Các thiết bị thu nhận ảnh thông thường Raster là camera các thiết bị
thu nhận ảnh thông thường Vector là sensor hoặc bàn số hoá Digitalizer
hoặc được chuyển đổi từ ảnh Raster.
Nhìn chung các hệ thống thu nhận ảnh thực hiện 1 quá trình
• Cảm biến: biến đổi năng lượng quang học thành năng lượng điện
• Tổng hợp năng lượng điện thành ảnh
1.2.2. Biểu diễn ảnh
Ảnh trên máy tính là kết quả thu nhận theo các phương pháp số hoá
được nhúng trong các thiết bị kỹ thuật khác nhau. Quá trình lưu trữ ảnh nhằm 2 mục đích: • Tiết kiệm bộ nhớ
• Giảm thời gian xử lý
Việc lưu trữ thông tin trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển
thị, in ấn và xử lý ảnh được xem như là 1 tập hợp các điểm với cùng kích
thước nếu sử dụng càng nhiều điểm ảnh thì bức ảnh càng đẹp, càng mịn và
càng thể hiện rõ hơn chi tiết của ảnh người ta gọi đặc điểm này là độ phân giải.
Việc lựa chọn độ phân giải thích hợp tuỳ thuộc vào nhu cầu sử dụng
và đặc trưng của mỗi ảnh cụ thể, trên cơ sở đó các ảnh thường được biểu
diễn theo 2 mô hình cơ bản
1.2.2.1. Mô hình Raster
Đây là cách biểu diễn ảnh thông dụng nhất hiện nay, ảnh được biểu
diễn dưới dạng ma trận các điểm (điểm ảnh). Thường thu nhận qua các
thiết bị như camera, scanner. Tuỳ theo yêu cầu thực thế mà mỗi điểm ảnh
được biểu diễn qua 1 hay nhiều bít
Mô hình Raster thuận lợi cho hiển thị và in ấn. Ngày nay công nghệ
phần cứng cung cấp những thiết bị thu nhận ảnh Raster phù hợp với tốc độ
nhanh và chất lượng cao cho cả đầu vào và đầu ra. Một thuận lợi cho việc
hiển thị trong môi trường Windows là Microsoft đưa ra khuôn dạng ảnh
DIB (Device Independent Bitmap) làm trung gian. Hình 1.4 thể hình quy
trình chung để hiển thị ảnh Raster thông qua DIB. 12
Một trong những hướng nghiên cứu cơ bản trên mô hình biểu diễn này
là kỹ thuật nén ảnh các kỹ thuật nén ảnh lại chia ra theo 2 khuynh hướng là
nén bảo toàn và không bảo toàn thông tin nén bảo toàn có khả năng phục
hồi hoàn toàn dữ liệu ban đầu còn nếu không bảo toàn chỉ có khả năng
phục hồi độ sai số cho phép nào đó. Theo cách tiếp cận này người ta đã đề
ra nhiều quy cách khác nhau như BMP, TIF, GIF, PCX…
Hiện nay trên thế giới có trên 50 khuôn dạng ảnh thông dụng bao gồm
cả trong đó các kỹ thuật nén có khả năng phục hồi dữ liệu 100% và nén có
khả năng phục hồi với độ sai số nhận được. BMP Paint PCC . . DIB Cửa sổ . Thay đổi
Hình 1.4. Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB
1.2.2.2. Mô hình Vector
Biểu diễn ảnh ngoài mục đích tiết kiệm không gian lưu trữ dễ dàng
cho hiển thị và in ấn còn đảm bảo dễ dàng trong lựa chọn sao chép di
chuyển tìm kiếm… Theo những yêu cầu này kỹ thuật biểu diễn vector tỏ ra ưu việt hơn.
Trong mô hình vector người ta sử dụng hướng giữa các vector của
điểm ảnh lân cận để mã hoá và tái tạo hình ảnh ban đầu ảnh vector được thu
nhận trực tiếp từ các thiết bị số hoá như Digital hoặc được chuyển đổi từ
ảnh Raster thông qua các chương trình số hoá
Công nghệ phần cứng cung cấp những thiết bị xử lý với tốc độ nhanh
và chất lượng cho cả đầu vào và ra nhưng lại chỉ hỗ trợ cho ảnh Raster.
Do vậy, những nghiên cứu về biểu diễn vectơ đều tập trung từ chuyển đổi từ ảnh Raster. Vecter Raster RASTER VECTOR RASTER hóa hóa
Hình 1.5. Sự chuyển đổi giữa các mô hình biểu diễn ảnh 13 Chương 2:
CÁC KỸ THUẬT NÂNG CAO CHẤT LƯỢNG ẢNH
2.1. CÁC KỸ THUẬT KHÔNG PHỤ THUỘC KHÔNG GIAN 2.1.1. Giới thiệu
Các phép toán không phụ thuộc không gian là các phép toán không
phục thuộc vị trí của điểm ảnh.
Ví dụ: Phép tăng giảm độ sáng , phép thống kê tần suất, biến đổi tần suất v.v..
Một trong những khái niệm quan trọng trong xử lý ảnh là biểu đồ tần suất (Histogram)
Biểu đồ tần suất của mức xám g của ảnh I là số điểm ảnh có giá trị g
của ảnh I. Ký hiệu là h(g) Ví dụ: 1 2 0 4 1 0 0 7 I = 2 2 1 0 4 1 2 1 2 0 1 1 g 0 1 2 4 7 h(g) 5 7 5 2 1
2.1.2. Tăng giảm độ sáng
Giả sử ta có I ~ kích thước m × n và số nguyên c
Khi đó, kỹ thuật tăng, giảm độc sáng được thể hiện for (i = 0; i < m; i + +) for (j = 0; j < n; j + +) I [i, j] = I [i, j] + c;
• Nếu c > 0: ảnh sáng lên
• Nếu c < 0: ảnh tối đi 14 2.1.3. Tách ngưỡng
Giả sử ta có ảnh I ~ kích thước m × n, hai số Min, Max và ngưỡng θ
khi đó: Kỹ thuật tách ngưỡng được thể hiện for (i = 0; i < m; i + +) for (j = 0; j < n; j + +)
I [i, j] = I [i, j] > = θ? Max : Min; * Ứng dụng:
Nếu Min = 0, Max = 1 kỹ thuật chuyển ảnh 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 dính. 2.1.4. Bó cụm
Kỹ thuật nhằm giảm bớt số mức xám của ảnh bằng cách nhóm lại số
mức xám gần nhau thành 1 nhóm
Nếu chỉ có 2 nhóm thì chính là kỹ thuật tách ngưỡng. Thông thường
có nhiều nhóm với kích thước khác nhau.
Để tổng quát khi biến đổi người ta sẽ lấy cùng 1 kích thước bunch_size h(g) g 0
I [i,j] = I [i,j]/ bunch - size * bunch_size ∀(i,j)
Ví dụ: Bó cụm ảnh sau với bunch_size= 3 1 2 4 6 7 2 1 3 4 5 I = 7 2 6 9 1 4 1 2 1 2 15 0 0 3 6 6 0 0 3 3 3 Ikq = 6 0 6 9 0 3 0 0 0 0
2.1.5. Cân bằng histogram
Ảnh I được gọi là cân bằng "lý tưởng" nếu với mọi mức xám g, g’ ta có h(g) = h(g’) Giả sử, ta có ảnh I ~ kích thước m × n
new_level ~ số mức xám của ảnh cân bằng m × n TB =
~ số điểm ảnh trung bình của mỗi mức xám new _ level của ảnh cân bằng g
t(g) = ∑h i() i=0
~ số điểm ảnh có mức xám ≤ g Xác định hàm f: g a f(g) ⎧ ⎛ t(g) ⎞ ⎫
Sao cho: f (g) = max⎨ , 0 round⎜ ⎟ − ⎬ 1 ⎩ ⎝ TB ⎠ ⎭
Ví dụ: Cân bằng ảnh sau với new_level= 4 1 2 4 6 7 2 1 3 4 5 I = 7 2 6 9 1 4 1 2 1 2 g h(g) t(g) f(g) 1 5 5 0 2 5 10 1 3 1 11 1 4 3 14 2 5 1 15 2 6 2 17 2 7 2 19 3 9 1 20 3 16 0 1 2 2 3 1 0 1 2 2 Ikq = 3 1 2 3 0 2 0 1 0 1
Chú ý: Ảnh sau khi thực hiện cân bằng chưa chắc đã là cân bằng "lý tưởng "
2.1.6. Kỹ thuật tách ngưỡng tự động
Ngưỡng θ trong kỹ thuật tách ngưỡng thường được cho bởi người sử
dụng. Kỹ thuật 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 2
phần nếu tổng độ lệnh trong từng phần là tối thiểu. Giả sử, ta có ảnh I ~ kích thước m × n G ~ là
số mức xám của ảnh kể cả khuyết thiếu t(g) ~
số điểm ảnh có mức xám ≤ g g 1 m(g) = ∑i h. i() t(g) i=0
~ mômen quán tính TB có mức xám ≤ g
Hàm f: g a f (g) t(g) f (g) =
[m(g) − m(G − ]2 ) 1
mxn t(g) Tìm θ sao cho: f (θ ) = {f (g }) max 0≤g<G 1 −
Ví dụ: Tìm ngưỡng tự động của ảnh sau 0 1 2 3 4 5 0 0 1 2 3 4 I = 0 0 0 1 2 3 0 0 0 0 1 2 0 0 0 0 0 1 Lập bảng g g h(g) t(g) g.h(g) ∑ih i() m(g) f(g) i=0 0 15 15 0 0 0 1.35 1 5 20 5 5 0,25 1.66 17 2 4 24 8 13 0,54 1.54 3 3 27 9 22 0,81 1.10 4 2 29 8 30 1,03 0.49 5 1 30 5 35 1,16 ∞
Ngưỡng cần tách θ= 1 ứng với f(θ)= 1.66
2.1.7. Biến đổi cấp xám tổng thể
Nếu biết ảnh và hàm biến đổi thì ta có thể tính được ảnh kết quả và do
đó ta sẽ có được histogram của ảnh biến đổi. Nhưng thực tế nhiều khi ta chỉ
biết histogram của ảnh gốc và hàm biến đổi, câu hỏi đặt ra là liệu ta có thể
có được histogram của ảnh biến đổi. Nếu có như vậy ta có thể hiệu chỉnh
hàm biến đổi để thu được ảnh kết quả có phân bố histogram như mong muốn.
Bài toán đặt ra là biết histogram của ảnh, biết hàm biến đổi hãy vẽ histogram của ảnh mới. Ví dụ: g 1 2 3 4 h(g) 4 2 1 2 g + 1 nếu g ≤ 2 f(g)= g nếu g = 3 g – 1 nếu g > 3
Bước 1: Vẽ Histogram của ảnh cũ f(g) g 0 18
Bước 2: Vẽ đồ thị hàm f(g) h(g) g 0
Bước 3: Vẽ Histogram của ảnh mới Đặt q = f(g) h(q) = card ({P| I(P) = q}) = card ({P| I(P) = f(g)}) = card ({P| g = f-1 (I(P))}) = ∑h(i) h(g) f(g) − ∈ 1 i f (q) g 0
Histogram của ảnh mới thua được bằng cách chồng hình và tính giá trị
theo các q (= f(g)) theo công thức tính trên. Kết quả cuối thu được sau phép
quay góc 90 thuận chiều kim đồng hồ. 19
2.2. CÁC KỸ THUẬT PHỤ THUỘC KHÔNG GIAN
2.2.1. Phép cuộn và mẫu
Giả sử ta có ảnh I kích thước M × N, mẫu T có kích thước m × n khi
đó, ảnh I cuộn theo mẫu T được xác định bởi công thức. m 1 − n 1 −
I T (x, y) = ∑ ∑ I(x + i, y + j)*T(i, j) (2.1) i=0 j=0 m 1 − n 1 −
Hoặc I T (x, y) = ∑ ∑I(x i, y j)*T(i, j) (2.2) i=0 j=0 VD: 1 2 4 5 8 7 2 1 1 4 2 2 I = 4 5 5 8 8 2 1 2 1 1 4 4 7 2 2 1 5 2 T = 1 0 0 1 1 1
I T (x, y) = ∑ ∑I(x + i, y + j)*T(i, j)= I(x, y)*T( 0 , 0 )+ I(x + , 1 y + ) 1 *T ( ) 1 , 1 i=0 j=0
= I(x, y)+ I(x + , 1 y + ) 1 2 3 8 7 10 * 7 6 9 12 4 * Tính theo (2.1) I ⊗ T = 6 6 6 12 12 * 3 4 2 6 6 * * * * * * * Tính theo công thức 2.2 * * * * * * * 2 3 8 7 10 I ⊗ T = * 7 6 9 12 4 * 6 6 6 12 12 * 3 4 2 6 6 20 * Nhận xét:
- Trong quá trình thực hiện phép cuộn có một số thao tác ra ngoài ảnh,
ảnh không được xác định tại những vị trí đó dẫn đến ảnh thu được có kích thước nhá hơn.
- Ảnh thực hiện theo công thức 2.1 và 2.2 chỉ sai khác nhau 1 phép
dịch chuyển để đơn giản ta sẽ hiểu phép cuộn là theo công thức 2.1
2.2.2. Một số mẫu thông dụng - Mẫu: 1 1 1 T1 = 1 1 1 1 1 1
~ Dùng để khử nhiễu ⇒ Các điểm có tần số cao VD1: 1 2 4 5 8 7 2 31 1 4 2 2 I = 4 5 5 8 8 2 1 2 1 1 4 4 7 2 2 1 5 2 55 65 45 46 * * 52 58 34 35 * * I ⊗ T1 = 29 27 35 35 * * * * * * * * * * * * * *
Áp dụng kỹ thuật cộng hằng số với c = -27, ta có: 28 38 18 19 * * 25 31 7 8 * * Ikq = 2 0 8 8 * * * * * * * * * * * * * * - Mẫu: 0 -1 0 T2 = -1 4 -1 0 -1 0 21
~ Dùng để phát hiện các điểm có tần số cao VD2: 114 -40 0 -14 * * -22 5 14 16 * * I ⊗ T2 =-1 -6 -10 -2 * * * * * * * * * * * * * * 2.2.3. Lọc trung vị
* Định nghĩa 2.1 (Trung vị)

Cho dãy x1; x2...; xn đơn điệu tăng (giảm). Khi đó trung vị của dãy ký
hiệu là Med({xn}), được định nghĩa: ⎡n
+ Nếu n lẻ x⎢ + ⎥ 1 ⎣2 ⎦ ⎡n⎤ ⎡n ⎤ + Nếu n chẵn: x x + ⎢ ⎥ hoặc ⎢ ⎥ 1 ⎣2⎦ ⎣2 ⎦ * Mệnh đề 2.1
n x x → min Med( xn ) i tại { } i 1 = Chứng minh
+ Xét trường hợp n chẵn n Đặt M = 2 Ta có: ∑n M M x x = x x x x i ∑ − + i ∑ − M+i i=1 i=1 i=1 M M
= ∑(x x + x x xx i M +i ) ∑ M+i i i=1 i=1 M
= ∑ ([x x + x x M +1 M ) ( M i )] i=1 M M
= ∑ x Med x + x Med x M +i {( i}) ∑ i {( i}) i=1 i=1 22 n
= ∑ x Med x i {( i}) i=1 + Nếu n lẻ:
Bổ sung thêm phần tử Med {
( x vào dãy. Theo trường hợp n chẵn i }) ta có: n
x x + Med x Med x i {( i})
{( i}) → min tại Med({xn}) i=1 n
x xi → min tại Med({xn}) i=1
* Kỹ thuật lọc trung vị
Giả sử ta có ảnh I ngưìng θ cửa sổ W(P) và điểm ảnh P
Khi đó kỹ thuật lọc trung vị phụ thuộc không gian bao gồm các bước cơ bản sau:
+ Bước 1: Tìm trung vị
{I(q)| q ∈ W(P)} → Med (P)
+ Bước 2: Gán giá trị ⎧I(P)
I (P) − Med(P) ≤ θ I (P) = ⎨ ⎩Med(P) Nguoclai Ví dụ: 1 2 3 2 4 16 2 1 I = 4 2 1 1 2 1 2 1 W(3 × 3); θ = 2 1 2 3 2 4 2 2 1 Ikq = 4 2 1 1 2 1 2 1
Giá trị 16, sau phép lọc có giá trị 2, các giá trị còn lại không thay đổi giá trị. 23 2.2.4. Lọc trung bình
* Định nghĩa 2.2 (Trung bình)

Cho dãy x1, x2…, xn khi đó trung bình của dãy ký hiệu AV({xn}) ddược định nghĩa: 1 AV { ( x round x n }) ⎛ n ⎞ = ⎜ ∑ ⎟ ⎝ i n i=1 ⎠ * Mệnh đề 2.2 2
n(x x AV ( xn ) i ) → min tại { } i 1 = Chứng minh: n 2
Đặt: φ(x) = ∑ (x xi ) i=1 Ta có: n
φ(x) = 2∑(x xi ) i=1 ' φ (x) = 0 n ⇔ ∑(x x 0 i ) = i=1 n ⇔ 1
x = ∑ x = AV x i {( i}) n i=1 Mặt khác, '
φ (x) = 2n > 0
⇒ φ → min tại x = AV { ( xi})
Kỹ thuật lọc trung bình
Giả sử ta có ảnh I, điểm ảnh P, cửa sổ W(P) và ngưỡng θ. Khi đó kỹ
thuật lọc trung bình phụ thuộc không gian bao gồm các bước cơ bản sau:
+ Bước 1: Tìm trung bình {I(q)| q ∈ W(P)} → AV(P) 24
+ Bước 2: Gán giá trị ⎧I(P)
I (P) − AV (P) ≤ θ I (P) = ⎨ ⎩AV (P) Nguoclai Ví dụ: 1 2 3 2 4 16 2 1 I = 4 2 1 1 2 1 2 1 W(3 × 3); θ = 2 1 2 3 2 4 3 2 1 Ikq = 4 2 1 1 2 1 2 1
Giá trị 16 sau phép lọc trung bình có giá trị 3, các giá trị còn lại giữ nguyên sau phép lọc.
2.2.5. Lọc trung bình theo k giá trị gần nhất
Giả sử ta có ảnh I, điểm ảnh P, cửa sổ W(P), ngưỡng θ và số k. Khi
đó, lọc trung bình theo k giá trị gần nhất bao gồm các bước sau:
+ Bước 1: Tìm K giá trị gần nhất
{I(q) ⏐q ∈ W(p)} → {k ∼ giá trị gần I(P) nhất}
+ Bước 2: Tính trung bình
{k ∼ giá trị gần I(P) nhất} → AVk(P)
+ Bước 3: Gán giá trị ⎧I (P)
I (P) − AV (P) ≤ θ I (P) = ⎨ kAV (P) k Nguoclai Ví dụ: 1 2 3 2 4 16 2 1 I = 4 2 1 1 2 1 2 1 W(3 × 3); θ = 2; k = 3 25 1 2 3 2 4 8 2 1 Ikq = 4 2 1 1 2 1 2 1 * Nhận xét:
- Nếu k lớn hơn kích thước cửa sổ thì kỹ thuật chính là kỹ thuật lọc trung bình
- Nếu k= 1 thì ảnh kết quả không thay đổi
⇒ Chất lượng của kỹ thuật phụ thuộc vào số phân tử lựa chọn k.
2.3. CÁC PHÉP TOÁN HÌNH THÁI HỌC
2.3.1. Các phép toán hình thái cơ bản
Hình thái là thuật ngữ chỉ sự nghiên cứu về cấu trúc hay hình học topo
của đối tượng trong ảnh. 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 "giãn nở" (Dilation) và phép "co" (Erosion).
Các phép toán này được định nghĩa như sau: Giả thiết ta có đối tượng
X và phần tử cấu trúc (mẫu) B trong không gian Euclide hai chiều. Kí hiệu
Bx là dịch chuyển của B tới vị trí x.
Định nghĩa 2.3 (DILATION)
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. Ta có: X ⊕ B = UB x xX
Định nghĩa 2.4 (EROSION)
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. Ta có: X \ B = {x : Bx ⊆ X}
⎛ 0 x 0 x x ⎞ ⎜ ⎟
x 0 x x 0 ⎟
Ví dụ: Ta có tập X như sau: X = ⎜ ⎟ ⎜ 0 x x 0 0 ⎟ B = 8 x
⎜ 0 x 0 x 0 ⎟ ⎜ ⎟ ⎝ 0 x x x 0 ⎠ 26 ⎛ 0 x x x x ⎞ ⎜ ⎟ ⎛ 0 0 0 x 0 ⎞ ⎜ ⎟ ⎜ x x x x x ⎟ ⎜ 0 0 x 0 0 ⎟ ⎜ ⎟ 0 x x x 0 ⎜ ⎟ X ⊕ B = ⎜ ⎟ và X 0 x 0 0 0 \B = ⎜ ⎟ ⎜ 0 x x x x ⎟ ⎜ 0 0 0 0 0 ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ 0 x x x x ⎠ ⎝ 0 x x 0 0 ⎠
Đình nghĩa 2.5 (OPEN)
Phép toán mở (OPEN) 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 liếp theo B. Ta có: OPEN(X,B) = (X \ B) ⊕ B
Ví dụ: Với tập X và B trong ví dụ trên ta có ⎛ 0 0 0 x x ⎞ ⎜ ⎟ ⎜ 0 0 x x 0 ⎟ ⎜ ⎟
OPEN(X,B) = (X\B) ⊕ B = ⎜ 0 x x 0 0 ⎟ ⎜ ⎟ ⎜ 0 0 0 0 0 ⎟ ⎜ ⎟ ⎝ 0 x x x 0 ⎠
Định nghĩa 2.6 (CLOSE)
Phép toán đóng (CLOSE) của X theo cấu trúc B là tập hợp các điểm
của ảnh X sau khi đã giãn nở và co liên tiếp theo B. Ta có: CLOSE(X,B) = (X ⊕ B) \ B Theo ví dụ trên ta có: ⎛ 0 x x x x ⎞ ⎜ ⎟ ⎜ x x x x x ⎟ ⎜ ⎟
CLOSE(X,B) = (X ⊕ B) \ B = ⎜ 0 x x 0 0 ⎟ ⎜ ⎟ ⎜ 0 x x x 0 ⎟ ⎜ ⎟ ⎝ 0 x x x 0 ⎠
2.3.2. Một số tính chất của phép toán hình thái
* Mệnh đề 2.3
[Tính gia tăng]: (i) X ⊆ X’ ⇒ X \ B ⊆ X’ \ B ∀B X ⊕ B ⊆ X’ ⊕ B ∀B (ii) B ⊆ B' ⇒ X \ B ⊇ X \ B' ∀X X ⊕ B ⊆ X ⊕ B’ ∀X 27 Chứng minh: (i) X ⊕ B = B B = X ⊕ ' B x x U U xX xX ' X
\ B = {x / B X ⊆ ⊆ x } {x / B X x }' = X’ \ B (ii) X ⊕ B = B
B' = X B' x x U U xX xX Theo định nghĩa: X
\ B’ = {x / B' ⊆ X ⊆ / ⊆ x } {x B X x } = X \ B .
*Mệnh đề 2.4 [Tính phân phối với phép ]:
(i) X ⊕ (B ∪ B') = (X ⊕ B) ∪ (X ⊕ B')
(ii) X\ (B ∪ B') = (X \ B) ∩ (X \B') Chứng minh:
(i) X ⊕ (B ∪ B’) = ( X ⊕ B) ∪ (X ⊕ B’) Ta có: B ∪ B’ ⊇ B
X ⊕ (B ∪ B’) ⊇ X ⊕ B (tính gia tăng) Tương tự:
X ⊕ ( B ∪ B’) ⊇ X ⊕ B’
X ⊕ (B ∪ B’) ⊇ (X ⊕ B) ∪ (X ⊕ B’) (2.3) Mặt khác,
∀ y ∈ X ⊕ (B ∪ B’) ⇒ ∃x ∈ X sao cho y ∈ (B ∪ B’) x ⇒ y ∈ Bx ⇒ y ∈ X ⊕ B y ∈ B’x y ∈ X ⊕ B’
⇒ y ∈ (X ⊕ B) ∪ (X ⊕ B’)
⇒ X ⊕ (B ∪ B’) ⊆ (X ⊕B ) ∪ (X ⊕B’) (2.4)
Từ (2.3) và (2.4) ta có: X ⊕ (B ∪ B’) = (X ⊕ B) ∪ (X ⊕ B’)
(ii) X \ (B ∪ B’) = (X \ B) ∩ (X \ B’) Ta có: B ∪ B’ ⊇ B ⇒ X
\ (B ∪ B’) ⊆ X \ B (tính gia tăng)
Tương tự : X \ (B ∪ B’) ⊆ X \ B’ ⇒
X \ (B ∪ B’) ⊆ (X \ B) ∩ ( X \ B’) (2.5) 28 Mặt khác,
∀x ∈ (X \ B) ∩ (X \ B’)
Suy ra, x ∈ X \ B ⇒ Bx ⊆ X x ∈ X \ B’ B’x ⊆ X ⇒ ( B ∪ B’)x ⊆ X ⇒ x ∈ X \ (B ∪ B’)
⇒ X \ (B ∪ B’) ⊇ (X \ B) ∩ (X \ B’) (2.6)
Từ (2.5) và (2.6) ta có: X \ (B ∪ B’) = (X \ B) ∩ (X \ B’). * Ý nghĩa:
Ta có thể phân tích các mẫu phức tạp trở thành các mẫu đơn giản
thuận tiện cho việc cài đặt.
* Mệnh đề 2.5 [Tính phân phối với phép ]:
(X ∩ Y) \ B = (X \ B) ∩ (Y \ B) Chứng minh: Ta có, X ∩ Y ⊆ X ⇒ (X ∩ Y) \ B ⊆ X \ B Tương tự: (X ∩ Y) \ B ⊆ Y \ B ⇒ (X
∩ Y) \ B ⊆ (X \ B) ∩ (Y \ B) (2.7) Mặt khác, ∀x ∈ (X \ B) ∩ (Y \ B) Suy ra x ∈ X \ B ⇒ Bx ⊆ X x ∈ Y \ B Bx ⊆ Y ⇒ Bx ⊆ X ∩ Y ⇒ x ∈ ( X ∩ Y) \ B
⇒ (X ∩ Y) \ B ⊇ (X \ B) ∩ (Y \ B) (2.8)
Từ (2.7) và (2.8) ta có: (X ∩ Y) \ B = (X \ B) ∩ (Y \ B).
* Mệnh đề 2.6 [Tính kết hợp]
(i) (X ⊕ B) ⊕ B' = X ⊕ (B ⊕ B')
(ii) (X \ B) \ B' = X \ (B ⊕ B') 29 Chứng minh:
(i) (X ⊕ B) ⊕ B' = X ⊕ (B' ⊕ B)
Ta có, (X ⊕ B) ⊕ B' = ( UB ) ⊕ B' x xX =
U(B B')= (B B') x U x xX xX = X ⊕ (B' ⊕ B)
(i) (X \ B) \ B' = X \ (B ⊕ B')
Trước hết ta đi chứng minh: '
B ⊆ X \ B ⇔ (B' ⊕ B) ⊆ X x x Thật vậy, do '
B ⊆ X \ B nên ∀y∈ ' B ⇒ y∈X \ B x x ⇒ By ⊆ X ⇒ B X y U y B ∈ 'x
⇒ (B' ⊕ B) ⊆ X x
Mặt khác, (B' ⊕ B) ⊆ X ⇔ ( ' B ⊕ B) ⊆ X x x ⇔ UB ⊆ X y ' y Bx ⇒ ∀y∈ ' B ta có B x y ⊆ X ⇒ hay ∀y∈ ' B ta có y ∈ X \ B x Do đó, ' B ⊆ X \ B x
Ta có, (X \ B) \ B' = {x / B X \ B' x } = {x/ ' B ⊆ X \ B} x = {x/
(B' ⊕ B) ⊆ X} (do chứng minh ở trên) x = X \ (B ⊕ B') .
* Định lý 2.1 [X bị chặn bởi các cận OPEN và CLOSE]
Giả sử, X là một đối tượng ảnh, B là mẫu, khi đó, X sẽ bị chặn trên
bởi tập CLOSE của X theo B và bị chặn dưới bởi tập OPEN của X theo B. Tức là:
(X ⊕ B) \ B ⊇ X ⊇ (X \ B) ⊕ B 30 Chứng minh:
Ta có: ∀ x ∈ X ⇒ Bx ⊆ X ⊕ B (Vì X ⊕ B = UB ) x xX
⇒ x ∈ (X ⊕ B) \ B (theo định nghĩa phép co) ⇒ (X ⊕ B) \ B ⊇ X (2.9) Mặt khác,
∀ y ∈ (X \ B) ⊕ B, suy ra:
∃ x ∈ X \ B sao cho y ∈ Bx (Vì (X\B) ⊕ B = UB ) xx X B Θ ⇒ Bx ⊆ X ⇒ y ∈ X Suy ra: X ⊇ (X \ B) ⊕ B (2.10)
Từ (2.9) và (2.10) Ta có: (X ⊕ B) \ B ⊇ X ⊇ (X \ B) ⊕ B .
*Hệ quả 2.1 [Tính bất biến] :
(i) ((X ⊕ B) \B) ⊕ B = X ⊕ B
(ii) ((X \ B) ⊕ B) \ B = X\B Chứng minh:
(i) Thật vậy, từ định lý 2.1 ta có X ⊆ (X ⊕ B) Ө B
⇒ X ⊕ B ⊆ ((X ⊕ B) \B) ⊕ B (do tính chất gia tăng) (2.11)
Mặt khác, cũng từ định lý 2.1 ta có (X \ B) ⊕ B ⊆ X ∀X
Do đó, thay X bởi X ⊕ B ta có, ((X ⊕ B) \B) ⊕ B ⊆ X ⊕ B (2.12)
Từ (2.11) và (2.12) Ta có: ((X ⊕ B) \B) ⊕ B = X ⊕ B
(ii) Thật vậy, từ định lý 2.1 ta có (X \ B) ⊕ B ⊆ X
⇒ ((X \ B) ⊕ B) \ B ⊆ X\B (do tính chất gia tăng) (2.13)
Mặt khác, cũng từ định lý 2.1 ta có X ⊆ (X ⊕ B) Ө B ∀X
Do đó, thay X bởi X \ B ta có, X\B ⊆ ((X \ B) ⊕ B) \ B (2.14)
Từ (2.13) và (2.14) Ta có: ((X \ B) ⊕ B) \ B = X\B (đpcm). 31 Chương 3:
BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN 3.1. GIỚI THIỆU
Biên là vấn đề quan trọng trong trích chọn đặc điểm nhằm tiến tới hiểu
ảnh. Cho đến nay chưa có định nghĩa chính xác về biên, trong mỗi ứng
dụng người ta đưa ra các độ đo khác nhau về biên, một trong các độ đo đó
là độ đo về sự thay đổi đột ngột về cấp xám. Ví dụ: Đối 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 biên hay đường bao của
đối tượng. Xuất phát từ cơ sở này người ta thường sử dụng hai phương
pháp phát hiện biên cơ bản:
Phát hiện biên trực tiếp: Phương pháp này làm nổi biên dựa vào sự
biến thiên mức xám của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên ở
đây là dựa vào sự biến đổi cấp xám theo hướng. Cách tiếp cận theo đạo
hàm bậc nhất của ảnh dựa trên kỹ thuật Gradient, nếu lấy đạo hàm bậc hai
của ảnh dựa trên biến đổi gia ta có kỹ thuật Laplace.
Phát hiện biên gián tiếp: Nếu bằng cách nào đó ta phân được ảnh
thành các vùng thì ranh giới giữa các vùng đó gọi là biên. Kỹ thuật dò biên
và phân vùng ảnh là hai bài toán đối ngẫu nhau vì dò biên để thực hiện phân
lớp đối tượng mà khi đã phân lớp xong nghĩa là đã phân vùng được ảnh và
ngược lại, khi đã phân vùng ảnh đã được phân lớp thành các đối tượng, do đó
có thể phát hiện được biên.
Phương pháp phát hiện biên trực tiếp tỏ ra khá hiệu quả và ít chịu ảnh
hưởng của nhiễu, song nếu sự biến thiên độ sáng không đột ngột, phương
pháp tỏ ra kém hiệu quả, phương pháp phát hiện biên gián tiếp tuy khó cài
đặt, song lại áp dụng khá tốt trong trường hợp này.
3.2. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN TRỰC TIẾP
3.2.1. Kỹ thuật phát hiện biên Gradient 32
Theo định nghĩa, gradient là một véctơ có các thành phần biểu thị tốc
độ thay đổi giá trị của điểm ảnh, ta có: f ∂ (x, y)
f (x + dx, y) − f (x, y) = fx xdx f ∂ (x, y)
f (x, y + dy) − f (x, y) = fy ydy
Trong đó, dx, dy là khoảng cách (tính bằng số điểm) theo hướng x và y. * Nhận xét:
Tuy ta nói là lấy đạo hàm nhưng thực chất chỉ là mô pháng và xấp xỉ
đạo hàm bằng các kỹ thuật nhân chập (cuộn theo mẫu) vì ảnh số là tín hiệu
rời rạc nên đạo hàm không tồn tại.
Ví dụ: Với dx = dy = 1, ta có:
⎧∂f f (x + ,1 y)− f (x, y) ⎪⎪∂x
⎪∂f f (x, y + )
1 − f (x, y) ⎪⎩∂y
Do đó, mặt nạ nhân chập theo hướng x là A= (−1 ) 1 ⎛− ⎞ 1
và hướng y là B= ⎜⎜ ⎟⎟ ⎝ 1 ⎠ Chẳng hạn: 0 0 0 0 0 3 3 3 I = 0 3 3 3 0 3 3 3 Ta có, 0 0 0 * 0 3 3 * I ⊗ A = 3 0 0 * ; I ⊗ B= 0 0 0 * 3 0 0 * 0 0 0 * * * * * * * * * 0 0 0 * I ⊗ A + I ⊗ B= 3 0 0 * 3 0 0 * * * * * 33
3.2.1.1. Kỹ thuật Prewitt
Kỹ thuật sử dụng 2 mặt nạ nhập chập xấp xỉ đạo hàm theo 2 hướng x và y là: -1 0 1 Hx = -1 0 1 -1 0 1 -1 -1 -1 Hy = 0 0 0 1 1 1
Các bước tính toán của kỹ thuật Prewitt
+ Bước 1: Tính I ⊗ Hx và I ⊗ Hy
+ Bước 2: Tính I ⊗ Hx + I ⊗ Hy Ví dụ: 0 0 0 0 0 0 5 5 5 5 0 0 5 5 5 5 0 0 I = 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -10 -10 * * 0 0 -15 -15 * * I ⊗ Hx = 0 0 -10 -10 * * 0 0 -5 -5 * * * * * * * * * * * * * * 15 15 10 5 * * 0 0 0 0 * * -15 -15 -10 -5 * * I ⊗ Hy = -15 -15 -10 -5 * * * * * * * * * * * * * * 34 15 15 0 -5 * * 0 0 -15 -15 * *
I ⊗ Hx + I ⊗ Hy = -15 -15 -20 -15 * * -15 -15 -15 -10 * * * * * * * * * * * * * *
3.2.1.2. Kỹ thuật Sobel
Tương tự như kỹ thuật Prewitt kỹ thuật Sobel sử dụng 2 mặt nạ nhân
chập theo 2 hướng x, y là: -1 0 1 Hx = -2 0 2 -1 0 1 -1 -2 -1 Hy = 0 0 0 1 2 1
Các bước tính toán tương tự Prewitt
+ Bước 1: Tính I ⊗ Hx và I ⊗ Hy
+ Bước 2: Tính I ⊗ Hx + I ⊗ Hy
3.2.1.3. Kỹ thuật la bàn
Kỹ thuật sử dụng 8 mặt nạ nhân chập theo 8 hướng 00, 450, 900, 1350, 1800, 2250, 2700, 3150 5 5 -3 5 5 5 H1 = 5 0 -3 H2 = -3 0 -3 -3 -3 -3 -3 -3 -3 -3 5 5 -3 -3 5 H3 = -3 0 5 H4 = -3 0 5 -3 -3 -3 -3 -3 5 -3 -3 -3 -3 -3 -3 H5 = -3 0 5 H6 = -3 0 -3 -3 5 5 5 5 5 -3 -3 -3 5 -3 -3 H7 = 5 0 -3 H8 = 5 0 -3 5 5 -3 5 -3 -3 35
Các bước tính toán thuật toán La bàn
+ Bước 1: Tính I ⊗ Hi ; i = 1,8 8
+ Bước 2: ∑ I H i i=1
3.2.2. Kỹ thuật phát hiện biên Laplace
Các phương pháp đánh giá gradient ở trên làm việc khá tốt khi mà độ
sáng thay đổi rõ nét. Khi mức xám thay đổi chậm, miền chuyển tiếp trải
rộng, phương pháp cho hiệu quả hơn đó là phương pháp sử dụng đạo hàm bậc hai Laplace.
Toán tử Laplace được định nghĩa như sau: Ta có: 2 2 ∂ ∂ 2 f ff = + 2 2 xy ∂ 2 ∂ f ∂ ⎛ f ∂ ⎞ ∂ = ⎜ ⎟ ≈
( f (x + ,1 y) − f (x, y)) 2 xx ∂ ⎝ x ∂ ⎠ x ∂ ≈ [ f (x + ,
1 y) − f (x, y)]− [ f (x, y) − f (x − , 1 y)] ≈ f (x + ,
1 y) − 2 f (x, y) + f (x − , 1 y) Tương tự, 2 ∂ f ∂ ⎛ f ∂ ⎞ ∂ = ≈
( f (x, y + )1 − f (x, y)) 2 yy ⎜⎜ ∂ ⎝ y ⎟⎟ ∂ ⎠ y
≈ [ f (x, y + )
1 − f (x, y)]− [ f (x, y) − f (x, y − ) 1 ] ≈
f (x, y + )
1 − 2 f (x, y) + f (x, y − ) 1
Vậy: ∇2 f= f(x+1,y) + f(x,y+1) - 4f(x,y) + f(x-1,y) + f(x,y-1) Dẫn tới: ⎛0 1 0⎞ ⎜ ⎟ H = ⎜1 − 4 1 ⎟ ⎜ 0 1 0⎟ ⎝ ⎠
Trong thực tế, người ta thường dùng nhiều kiểu mặt nạ khác nhau để
xấp xỉ rời rạc đạo hàm bậc hai Laplace. Dưới đây là ba kiểu mặt nạ thường dùng: 36 ⎛ 0 −1 0 ⎞ ⎛−1 −1 −1⎞ ⎛ 1 − 2 1 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ H = 1 ⎜−1 4 − ⎟ 1 H = 2 ⎜−1 8 −1⎟ H = 3 ⎜− 2 4 − 2⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ 0 −1 0 ⎠ ⎝−1 −1 −1⎠ ⎝ 1 − 2 1 ⎠ VD: 0 0 0 0 0 0 5 5 5 5 0 0 I = 5 5 5 5 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3.3. PHÁT HIỆN BIÊN GIÁN TIẾP
3.3.1 Một số khái niệm cơ bản *Ảnh và điểm ảnh
Ảnh số là một mảng số thực 2 chiều (Iij) có kích thước (M×N), trong
đó mỗi phần tử Iij(i = 1,...,M; j = 1,...,N) biểu thị mức xám của ảnh tại (i,j) tương ứng.
Ảnh được gọi là ảnh nhị phân nếu các giá trị Iij chỉ nhận giá trị 0 hoặc 1.
Ở đây ta chỉ xét tới ảnh nhị phân vì ảnh bất kỳ có thể đưa về dạng
nhị phân bằng kỹ thuật phân ngưỡng. Ta ký hiệu ℑ là tập các điểm vùng
(điểm đen) và ℑ là tập các điểm nền (điểm trắng).
*Các điểm 4 và 8-láng giềng
Giả sử (i,j) là một điểm ảnh, các điểm 4-láng giềng là các điểm kề
trên, dưới, trái, phải của (i,j):
N4(i,j) = {(i’,j’) : |i-i’|+|j-j’| = 1},
và những điểm 8-láng giềng gồm:
N8(i,j) = {(i’,j’) : max(|i-i’|,|j-j’|) =1}.
Trong Hình 1.2 biểu diễn ma trận 8 láng giềng kề nhau, các điểm P0,
P2, P4, P6 là các 4-láng giềng của điểm P, còn các điểm P0, P1, P2, P3, P4, P5,
P6, P7 là các 8-láng giềng của P. 37 P P P 3 2 1 P P P 4 0 P P P 5 6 7
Hình 1.3. Ma trận 8-láng giềng kề nhau *Đối tượng ảnh
Hai điểm Ps, Pe ∈ E, E ⊆ ℑ hoặc ℑ được gọi là 8-liên thông (hoặc 4-
liên thông) trong E nếu tồn tại tập các điểm được gọi là đường đi
(io,jo)...(in,jn) sao cho (io,jo)= Ps, (in,jn)= Pe, (ir,jr) ∈ E và (ir,jr) là 8-láng giềng
(hoặc 4-láng giềng tương ứng) của (ir-1,jr-1) với r = 1,2,...,n
Nhận xét: Quan hệ k-liên thông trong E (k=4,8) là một quan hệ phản xạ,
đối xứng và bắc cầu. Bởi vậy đó là một quan hệ tương đương. Mỗi lớp
tương đương được gọi là một thành phần k-liên thông của ảnh. Về sau ta sẽ
gọi mỗi thành phần k-liên thông của ảnh là một đối tượng ảnh.
3.3.2. Chu tuyến của một đối tượng ảnh
Định nghĩa 3.1: [Chu tuyến]

Chu tuyến của một đối tượng ảnh là dãy các điểm của đối tượng ảnh
P1,…,Pn sao cho Pi và Pi+1 là các 8-láng giềng của nhau (i=1,...,n-1) và P1 là
8-láng giềng của Pn, ∀i ∃Q không thuộc đối tượng ảnh và Q là 4-láng giềng
của Pi (hay nói cách khác ∀i thì Pi là biên 4). Kí hiệu .
Tổng các khoảng cách giữa hai điểm kế tiếp của chu tuyến là độ dài của
chu tuyến và kí hiệu Len(C) và hướng PiPi+1 là hướng chẵn nếu Pi và Pi+1 là
các 4 – láng giềng (trường hợp còn lại thì PiPi+1 là hướng lẻ).
Hình 3.1 dưới đây biểu diễn chu tuyến của ảnh, trong đó, P là điểm khởi đầu chu tuyến. P
Hình 3.1. Ví dụ về chu tuyến của đối tượng ảnh 38
Định nghĩa 3.2 [Chu tuyến đối ngẫu]
Hai chu tuyến C= và C⊥= được gọi là đối ngẫu
của nhau nếu và chỉ nếu ∀i ∃j sao cho:
(i) Pi và Qj là 4-láng giềng của nhau.
(ii) Các điểm Pi là vùng thì Qj là nền và ngược lại.
Định nghĩa 3.3 [Chu tuyến ngoài]
Chu tuyến C được gọi là chu tuyến ngoài (Hình 3.2a) nếu và chỉ nếu
(i) Chu tuyến đối ngẫu C⊥ là chu tuyến của các điểm nền
(ii) Độ dài của C nhỏ hơn độ dài C⊥
Định nghĩa 3.4 [Chu tuyến trong]
Chu tuyến C được gọi là chu tuyến trong (Hình 3.2b) nếu và chỉ nếu:
(i) Chu tuyến đối ngẫu C⊥ là chu tuyến của các điểm nền
(ii) Độ dài của C lớn hơn độ dài C⊥ Chu tuyÕn CChu tuyÕn CChu tuyÕn C Chu tuyÕn C a) Chu tuyến ngoài b) Chu tuyến trong
Hình 3.2. Chu tuyến trong, chu tuyến ngoài
Định nghĩa 3.5 [Điểm trong và điểm ngoài chu tuyến]
Giả sử C= là chu tuyến của một đối tượng ảnh và P là một điểm ảnh. Khi đó:
(i) Nếu nửa đường thẳng xuất phát từ P sẽ cắt chu tuyến C tại số lẻ lần,
thì P được gọi là điểm trong chu tuyến C và kí hiệu in(P,C)
(ii) Nếu P∉C và P không phải là điểm trong của C, thì P được gọi là
điểm ngoài chu tuyến C và kí hiệu out(P,C).
Bổ đề 3.1 [Chu tuyến đối ngẫu]
Giả sử E ⊆ ℑ là một đối tượng ảnh và C= < P1P2..Pn> là chu tuyến của
E, C⊥= là chu tuyến đối ngẫu tương ứng. Khi đó:
(i) Nếu C là chu tuyến trong thì in(Qi,C) ∀i (i=1,....,m) 39
(ii) Nếu C là chu tuyến ngoài thì in(Pi,C⊥) ∀i (i=1,...,n)
Bổ đề 3.2 [Phần trong/ngoài của chu tuyến]
Giả sử E ⊆ ℑ là một đối tượng ảnh và C là chu tuyến của E. Khi đó:
(i) Nếu C là chu tuyến ngoài thì ∀x ∈ E sao cho x∉C, ta có in(x,C)
(ii) Nếu C là chu tuyến trong thì ∀x ∈ E sao cho x∉C, ta có out(x,C)
Định lý 3.1 [Tính duy nhất của chu tuyến ngoài]
Giả sử E ⊆ ℑ là một đối tượng ảnh và CE là chu tuyến ngoài của E. Khi đó CE là duy nhất.
3.3.3. Thuật toán dò biên tổng quát
Biểu diễn đối tượng ảnh theo chu tuyến thường dựa trên các kỹ thuật
dò biên. Có hai kỹ thuật dò biên cơ bản. Kỹ thuật thứ nhất xét ảnh biên thu
được từ ảnh vùng sau một lần duyệt như một đồ thị, sau đó áp dụng các thuật
toán duyệt cạnh đồ thị. Kỹ thuật thứ hai dựa trên ảnh vùng, kết hợp đồng thời
quá trình dò biên và tách biên. Ở đây ta quan tâm cách tiếp cận thứ hai.
Trước hết, giả sử ảnh được xét chỉ bao gồm một vùng ảnh 8-liên thông
ℑ, được bao bọc bởi một vành đai các điểm nền. Dễ thấy ℑ là một vùng 4-
liên thông chỉ là một trường riêng của trường hợp trên.
Về cơ bản, các thuật toán dò biên trên một vùng đều bao gồm các bước sau:
• Xác định điểm biên xuất phát
• Dự báo và xác định điểm biên tiếp theo
• Lặp bước 2 cho đến khi gặp điểm xuất phát
Do xuất phát từ những tiêu chuẩn và định nghĩa khác nhau về điểm
biên, và quan hệ liên thông, các thuật toán dò biên cho ta các đường biên
mang các sắc thái rất khác nhau.
Kết quả tác động của toán tử dò biên lên một điểm biên ri là điểm biên
ri+1 (8-láng giềng của ri). Thông thường các toán tử này được xây dựng như
một hàm đại số Boolean trên các 8-láng giềng của ri. Mỗi cách xây dựng
các toán tử đều phụ thuộc vào định nghĩa quan hệ liên thông và điểm biên.
Do đó sẽ gây khó khăn cho việc khảo sát các tính chất của đường biên.
Ngoài ra, vì mỗi bước dò biên đều phải kiểm tra tất cả các 8-láng giềng của
mỗi điểm nên thuật toán thường kém hiệu quả. Để khắc phục các hạn chế
trên, thay vì sử dụng một điểm biên ta sử dụng cặp điểm biên (một thuộc ℑ,
một thuộc ℑ ), các cặp điểm này tạo nên tập nền vùng, kí hiệu là NV và
phân tích toán tử dò biên thành 2 bước: 40
• Xác định cặp điểm nền vùng tiếp theo.
• Lựa chọn điểm biên
Trong đó bước thứ nhất thực hiện chức năng của một ánh xạ trên tập
NV lên NV và bước thứ hai thực hiện chức năng chọn điểm biên.
Thuật toán dò biên tổng quát
Bước 1
: Xác định cặp nền-vùng xuất phát
Bước 2: Xác định cặp nền-vùng tiếp theo
Bước 3: Lựa chọn điểm biên vùng
Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2.
Việc xác định cặp nền-vùng xuất phát được thực hiện bằng cách duyệt
ảnh lần lượt từ trên xuống dưới và từ trái qua phải rồi kiểm tra điều kiện lựa
chọn cặp nền-vùng. Do việc chọn điểm biên chỉ mang tính chất quy ước, nên
ta gọi ánh xạ xác định cặp nền-vùng tiếp theo là toán tử dò biên.
Định nghĩa 3.6 [Toán tử dò biên]
Giả sử T là một ánh xạ như sau: T: NV → NV (b,r) a (b’,r’)
Gọi T là một toán tử dò biên cơ sở nếu nó thoả mãn điều kiện: b’,r’ là các 8-láng giềng của r.
Giả sử (b,r) ∈ NV; gọi K(b,r) là hàm chọn điểm biên. Biên của một
dạng ℑ có thể định nghĩa theo một trong ba cách:
• Tập những điểm thuộc ℑ có mặt trên NV, tức là K(b,r)= r
• Tập những điểm thuộc ℑ có trên NV, tức là K(b,r)= b
• Tập những điểm ảo nằm giữa cặp nền-vùng, tức là K(b,r) là những
điểm nằm giữa hai điểm b và r.
Cách định nghĩa thứ ba tương ứng mỗi cặp nền-vùng với một điểm
biên. Còn đối với cách định nghĩa thứ nhất và thứ hai một số cặp nền-
vùng có thể có chung một điểm biên. Bởi vậy, quá trình chọn điểm biên
được thực hiện như sau: i:= 1; (bi,ri):= (bo,ro);
While K(bi,ri)<>K(bn,rn) and i≤8 do
Begin (bi+1,ri+1)= T(bi,ri); i:= i+1; End; Điều kiện dừng
Cặp nền-vùng thứ n trùng với cặp nền vùng xuất phát: (bn,rn)= (bo,ro) 41
* Xác định cặp nền – vùng xuất phát
Cặp nền vùng xuất phát được xác định bằng cách duyệt ảnh lần lượt từ
trên xuống dưới và từ trái sang phải điểm đem đầu tiên gặp được cùng với
điểm trắng trước đó (theo hướng 4) để tạo nên cặp nền vùng xuất phát.
* Xác định cặp nền vùng tiếp theo Đầu vào: pt, dir Ví dụ: (3, 2) 4
Point orient []= {(1,0);(1;-1);(0;-1);(-1;-1);(-1;0);(-1,1);(0,1);(1,1)};
//Hàm tìm hướng có điểm đen gần nhất
BYTE GextNextDir(POINT pt, BYTE dir) { BYTE pdir= (dir + 7)%8; do{
if(getpixel(pt. x+orient [pdir]. x,pt.y+orient [pdir]. y))==BLACK) return pdir; pdir = (pdir + 7) %8; }while(pdir ! = dir);
return. ERR; //Điểm cô lập }
//Gán giá trị cho bước tiếp theo pdir = GetNextDir(pt, dir);
if(pdir==ERR) //Kiểm tra có là điểm cô lập không?
return. ERR; //Điểm cô lập
pt. x = pt. x + orient [pdir]. x;
pt. y = pt. y + orient [pdir]. y ;
Để tính giá trị cho hướng tiếp theo ta lập bảng dựa trên giá trị pdir đã
tính được trước đó theo các khả năng có thể xảy ra: 42 pdir
Điểm trắng trước đó Trắng so với đen mới 0 1 2 1 2 4 2 3 4 3 4 6 4 5 6 5 6 0 6 7 0 7 0 2
⇒ Do đó công thức để tính hướng tiếp theo sẽ là : dir= ((pdir+3)/ 2 * 2)%8 ; 43 Chương 4:
XƯƠNG VÀ CÁC KỸ THUẬT TÌM XƯƠNG 4.1. GIỚI THIỆU
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 nguyên
bản của một đối tượng thông qua xương.
Một định nghĩa xúc tích về xương dựa trên tính continuum (tương tự
như hiện tượng cháy đồng cỏ) được đưa ra bởi Blum (1976) như sau: Giả
thiết rằng đối tượng là đồng nhất được phủ bởi cỏ khô và sau đó dựng lên
một vòng biên lửa. Xương được định nghĩa như nơi gặp của các vệt lửa và
tại đó chúng được dập tắt. a) Ảnh gốc b) Ảnh xương
Hình 4.1. Ví dụ về ảnh và xương
Kỹ thuật tìm xương luôn là chủ đề nghiên cứu trong xử lý ảnh
những năm gần đây. Mặc dù có những nỗ lực cho việc phát triển các
thuật toán tìm xương, nhưng các phương pháp được đưa ra đều bị mất
mát thông tin. Có thể chia thành hai loại thuật toán tìm xương cơ bản:
• Các thuật toán tìm xương dựa trên làm mảnh
• Các thuật toán tìm xương không dựa trên làm mảnh
4.2. TÌM XƯƠNG DỰA TRÊN LÀM MẢNH
4.2.1. Sơ lược về thuật toán làm mảnh
Thuật toán 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. 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 hoặc vectơ hoá sau này. 44
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 thoả mãn điều kiện xoá nào đó tuỳ thuộc vào mỗi
thuật toán thì nó sẽ bị xoá đi. Quá trình cứ lặp lại cho đến khi không còn
điểm biên nào được xoá. Đố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.
Các thuật toán làm mảnh được phân loại dựa trên phương pháp xử lý
các điểm là thuật toán làm mảnh song song và thuật toán làm mảnh tuần tự.
Thuật toán làm mảnh song song, là thuật toán mà trong đó các điểm
được xử lý theo phương pháp song song, tức là được xử lý cùng một lúc.
Giá trị của mỗi điểm sau một lần lặp chỉ phụ thuộc vào giá trị của các láng
giềng bên cạnh (thường là 8-láng giềng) mà giá trị của các điểm này đã
được xác định trong lần lặp trước đó. Trong máy có nhiều bộ vi xử lý mỗi
vi xử lý sẽ xử lý một vùng của đối tượng, nó có quyền đọc từ các điểm ở
vùng khác nhưng chỉ được ghi trên vùng của nó xử lý.
Trong thuật toán làm mảnh tuần tự các điểm thuộc đối tượng sẽ được
kiểm tra theo một thứ tự nào đó (chẳng hạn các điểm được xét từ trái qua
phải, từ trên xuống dưới). Giá trị của điểm sau mỗi lần lặp không những
phụ thuộc vào giá trị của các láng giềng bên cạnh mà còn phụ thuộc vào
các điểm đã được xét trước đó trong chính lần lặp đang xét.
Chất lượng của thuật toán làm mảnh được đánh giá theo các tiêu
chuẩn được liệt kê dưới đây nhưng không nhất thiết phải thoả mãn đồng
thời tất cả các tiêu chuẩn.
• Bảo toàn tính liên thông của đối tượng và phần bù của đối tượng
• Sự tương hợp giữa xương và cấu trúc của ảnh đối tượng
• Bảo toàn các thành phần liên thông
• Bảo toàn các điểm cụt
• Xương chỉ gồm các điểm biên, càng mảnh càng tốt
• Bền vững đối với nhiễu
• Xương cho phép khôi phục ảnh ban đầu của đối tượng
• Xương thu được ở chính giữa đường nét của đối tượng được làm mảnh
• Xương nhận được bất biến với phép quay. 45
4.2.2. Một số thuật toán làm mảnh
Trong phần này điểm qua một số đặc điểm, ưu và khuyết điểm của các
thuật toán đã được nghiên cứu.
1o. Thuật toán làm mảnh cổ điển là thuật toán song song, tạo ra xương
8 liên thông, tuy nhiên nó rất chậm, gây đứt nét, xoá hoàn toàn một số cấu hình nhỏ.
2o. Thuật toán làm mảnh của Toumazet bảo toàn tất cả các điểm cụt
không gây đứt nét đối tượng. Tuy nhiên, thuật toán có nhược điểm
là rất chậm, rất nhạy cảm với nhiễu, xương chỉ là 4-liên thông và
không làm mảnh được với một số cấu hình phức tạp
3o. Thuật toán làm mảnh của Y.Xia dựa trên đường biên của đối
tượng, có thể cài đặt theo cả phương pháp song song và tuần tự.
Tốc độ của thuật toán rất nhanh. Nó có nhược điểm là gây đứt nét,
xương tạo ra là xương giả (có độ dày là 2 phần tử ảnh).
4o. Thuật toán làm mảnh của N.J.Naccache và R.Shinghal. Thuật toán
có ưu điểm là nhanh, xương tạo ra có khả năng khôi phục ảnh ban
đầu của đối tượng. Nhược điểm chính của thuật toán là rất nhạy
với nhiễu, xương nhận được phản ánh cấu trúc của đối tượng thấp.
5o. Thuật toán làm mảnh của H.E.Lu P.S.P Wang tương đối nhanh,
giữ được tính liên thông của ảnh, nhưng lại có nhược điểm là
xương tạo ra là xương 4-liên thông và xoá mất một số cấu hình nhỏ.
6o. Thuật toán làm mảnh của P.S.P Wang và Y.Y.Zhang dựa trên
đường biên của đối tượng, có thể cài đặt theo phương pháp song
song hoặc tuần tự, xương là 8-liên thông, ít chịu ảnh hưởng của
nhiễu. Nhược điểm chính của thuật toán là tốc độ chậm.
7o. Thuật toán làm mảnh song song thuần tuý nhanh nhất trong các
thuật toán trên, bảo toàn tính liên thông, ít chịu ảnh hưởng của
nhiễu. Nhược điểm là xoá hoàn toàn một số cấu hình nhỏ, xương
tạo ra là xương 4-liên thông.
4.3. TÌM XƯƠNG KHÔNG DỰA TRÊN LÀM MẢNH
Để tách được xương của đối tượng có thể sử dụng đường biên của đối
tượng. Với điểm p bất kỳ trên đối tượng, ta bao nó bởi một đường biên.
Nếu như có nhiều điểm biên có cùng khoảng cách ngắn nhất tới p thì p nằm
trên trục trung vị. Tập tất cả các điểm như vậy lập thành trục trung vị hay
xương của đối tượng. Việc xác định xương được tiến hành thông qua hai bước: 46 •
Bước thứ nhất, tính khoảng cách từ mỗi điểm ảnh của đối tượng đến
điểm biên gần nhất. Như vậy 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.
4.3.1. Khái quát về lược đồ Voronoi
Lược đồ Voronoi là một công cụ hiệu quả trong hình học tính toán.
Cho hai điểm Pi, Pj là hai phần tử của tập Ω gồm n điểm trong mặt phẳng.
Tập các điểm trong mặt phẳng gần Pi hơn Pj là nửa mặt phẳng H(Pi, Pj)
chứa điểm Pi và bị giới hạn bởi đường trung trực của đoạn thẳng PiPj. Do
đó, tập các điểm gần Pi hơn bất kỳ điểm Pj nào có thể thu được bằng cách
giao n-1 các nửa mặt phẳng H(Pi, Pj):
V(Pi) = ∩ H(Pi, Pj) i≠j (i= 1,...,n) (4.1)
Định nghĩa 4.1 [Đa giác/Sơ đồ Voronoi]
Sơ đồ Voronoi của Ω là hợp của tất cả các V(Pi)
Vor(Ω) = ∪ V(Pi) Pi∈Ω (là một đa giác) (4.2)
Định nghĩa 4.2 [Đa giác Voronoi tổng quát]
Cho tập các điểm Ω, đa giác Voronoi của tập con U của Ω được định nghĩa như sau:
V(U) = {P| ∃v ∈ U, ∀w ∈ Ω \ U : d(P,v) < d(P,w)} = ∪ V(Pi) Pi ∈ U (4.3)
4.3.2. Trục trung vị Voronoi rời rạc
Định nghĩa 4.3 [Bản đồ khoảng cách - Distance Map]

Cho đối tượng S, đối với mỗi (x, y)∈S, ta tính giá trị khoảng cách
map(x, y) với hàm khoảng cách d(.,.) như sau:
∀(x, y)∈S: map(x, y) = min d[(x, y), (xi, yi)] (4.4) trong đó (x i
i, yi) ∈ B(S) - tập các điểm biên của S
Tập tất cả các map(x, y), kí hiệu là DM(S), được gọi là bản đồ khoảng cách của S.
Chú ý: Nếu hàm khoảng cách d(.,.) là khoảng cách Euclide, thì phương
trình (4.4) chính là khoảng cách ngắn nhất từ một điểm bên trong đối tượng
tới biên. Do đó, bản đồ khoảng cách được gọi là bản đồ khoảng cách
Euclide EDM(S) của S. Định nghĩa trên được dùng cho cả hình rời rạc lẫn liên tục. 47
Định nghĩa 4.4 [Tập các điểm biên sinh]
Cho map(x, y) là khoảng cách ngắn nhất từ (x, y) đến biên (theo định
nghĩa 4.3). Ta định nghĩa: map-1(x, y) = {p| p ∈B(S), d(p, (x, y)):=map(x, y)}
Khi đó tập các điểm biên sinh ^B(S) được định nghĩa bởi:
^B(S) = ∪map-1(x, y), (x, y)∈ S (4.5)
Do S có thể chứa các đường biên rời nhau, nên ^B(S) bao gồm nhiều
tập con, mỗi tập mô tả một đường biên phân biệt: ^B(S)={B1(S),..BN(S)} (4.6)
Định nghĩa 4.5 [Trục trung vị Voronoi rời rạc (DVMA)]
Trục trung vị Voronoi rời rạc được định nghĩa là kết quả của sơ đồ
Voronoi bậc nhất rời rạc của tập các điểm biên sinh giao với hình sinh S :
DVMA(^B(S)) = Vor(^B(S)) ∩ S (4.7)
4.3.3. Xương Voronoi rời rạc
Định nghĩa 4.6 [Xương Voronoi rời rạc - DiscreteVoronoi Skeleton]

Xương Voronoi rời rạc theo ngưỡng T, kí hiệu là SkeDVMA(^B(S),T)
(hoặc Ske(^B(S),T)) là một tập con của trục trung vị Voronoi:
SkeDVMA(^B(S),T)= {(x,y)| (x,y)∈DVMA(^B(S)), Ψ(x,y) > T} (4.8) Ψ: là hàm hiệu chỉnh.
Dễ thấy nếu ngưỡng T càng lớn thì càng thì số lượng điểm tham gia
trong xương Vonoroi càng ít (Hình 4.2). a) b) c) d)
Hình 4.2. Xương Voronoi rời rạc ảnh hưởng của các hàm hiệu chỉnh khác nhau.
(a) Ảnh nhị phân. (b) Sơ đồ Voronoi. (c) Hiệu chỉnh bởi hàm Potential, T=9.0.
(d) Hiệu chỉnh bởi hàm Potential, T=18.0 48
4.3.4. Thuật toán tìm xương
Trong mục này sẽ trình bày ý tưởng cơ bản của thuật toán tìm xương
và mô tả bằng ngôn ngữ tựa Pascal.
Tăng trưởng: Việc tính toán sơ đồ Voronoi được bắt đầu từ một điểm
sinh trong mặt phẳng. Sau đó điểm sinh thứ hai được thêm vào và quá trình
tính toán tiếp tục với đa giác Voronoi đã tìm được với điểm vừa được thêm
vào đó. Cứ như thế, quá trình tính toán sơ đồ Voronoi được thực hiện cho
đến khi không còn điểm sinh nào được thêm vào. Nhược điểm của chiến
lược này là mỗi khi một điểm mới được thêm vào, nó có thể gây ra sự phân
vùng toàn bộ các đa giác Voronoi đã được tính.
Chia để trị: Tập các điểm biên đầu tiên được chia thành hai tập điểm
có kích cỡ bằng nhau. Sau đó thuật toán tính toán sơ đồ Voronoi cho cả hai
tập con điểm biên đó. Cuối cùng, người ta thực hiện việc ghép cả hai sơ đồ
Voronoi trên để thu được kết quả mong muốn. Tuy nhiên, việc chia tập các
điểm biên thành hai phần không phải được thực hiện một lần, mà được lặp
lại nhiều lần cho đến khi việc tính toán sơ đồ Voronoi trở nên đơn giản. Vì
thế, việc tính sơ đồ Voronoi trở thành vấn đề làm thế nào để trộn hai sơ đồ Voronoi lại với nhau.
Thuật toán sẽ trình bày ở đây là sự kết hợp của hai ý tưởng ở trên. Tuy
nhiên, nó sẽ mang nhiều dáng dấp của thuật toán chia để trị.
Hình 4.3 minh hoạ ý tưởng của thuật toán này. Mười một điểm biên
được chia thành hai phần (bên trái: 1- 6, bên phải: 7-11) bởi đường gấp
khúc δ, và hai sơ đồ Voronoi tương ứng Vor(SL) và Vor(SR). Để thu được
sơ đồ Vornonoi Vor(SL ∪ SR), ta thực hiện việc trộn hai sơ đồ trên và xác
định lại một số đa giác sẽ bị sửa đổi do ảnh hưởng của các điểm bên cạnh
thuộc sơ đồ kia. Mỗi phần tử của δ sẽ là một bộ phận của đường trung trực
nối hai điểm mà một điểm thuộc Vor(SL) và một thuộc Vor(SR). Trước khi
xây dựng δ, ta tìm ra phần tử đầu và cuối của nó. Nhìn vào hình trên, ta
nhận thấy rằng cạnh δ1 và δ5 là các tia. Dễ nhận thấy rằng việc tìm ra các
cạnh đầu và cuối của δ trở thành việc tìm cạnh vào tα và cạnh ra tω. 3 δ1 tα 7 CH(S ) L 1 6 11 CH(S ) R 4 9 2 10 5 tω 8 δ5
Hình 4.3. Minh hoạ thuật toán trộn hai sơ đồ Voronoi 49
Sau khi đã tìm được tα và tω, các điểm cuối của tα được sử dụng để xây
dựng phần tử đầu tiên của δ (δ1 trong hình trên). Sau đó thuật toán tìm điểm
giao của δ với Vor(SL) và Vor(SR). Trong ví dụ trên, δ đầu tiên giao với
V(3). Kể từ đây, các điểm nằm trên phần kéo dài δ sẽ gần điểm 6 hơn điểm
3. Do đó, phần tử tiếp theo δ2 của δ sẽ thuộc vào đường trung trực của điểm
6 và điểm 7. Sau đó điểm giao tiếp theo của δ sẽ thuộc và Vor(SL); δ bây
giờ sẽ đi vào V(9) và δ2 sẽ được thay thế bởi δ3. Quá trình này sẽ kết thúc
khi δ gặp phần tử cuối δ5.
Trên đây chỉ là minh hoạ cho thuật trộn hai sơ đồ Voronoi trong chiến
lược chia để trị. Tuy nhiên, trong thuật toán sẽ trình bày ở đây thì sự thực
hiện có khác một chút. Tập các điểm ảnh không phải được đưa vào ngay từ
đầu mà sẽ được quét vào từng dòng một. Giả sử tại bước thứ i, ta đã thu được
một sơ đồ Voronoi gồm i-1 hàng các điểm sinh Vor(Si-1). Tiếp theo, ta quét
lấy một hàng Li các điểm ảnh từ tập các điểm biên còn lại. Thực hiện việc
tính sơ đồ Voronoi Vor(Li) cho hàng này, sau đó trộn Vor(Si-1) với Vor(Li).
Kết quả ta sẽ được một sơ đồ mới, và lại thực hiện việc quét hàng Li+1 các
điểm sinh còn lại v.v.. Quá trình này sẽ kết thúc khi không còn điểm biên nào
để thêm vào sơ đồ Voronoi. Do Vor(Li) sẽ có dạng răng lược (nếu Li có k
điểm thì Vor(Li) sẽ gồm k-1 đường thẳng đứng), nên việc trộn Vor(Si-1) với
Vor(Li) có phần đơn giản hơn. v p 5 p v 8 9 2 p10 v1 δ t p ω 6 v4 p v 7 3 tα p5 p4 v 6 p p Các điểm thuộc 1 2 p3 Si-1
Hình 4.4. Minh hoạ thuật toán thêm một điểm biên vào sơ đồ Voronoi
Giải thuật trên có thể được mô tả bằng ngôn ngữ tựa Pascal như sau: Procedure VORONOI
(*Si: Tập các điểm của i dòng quét đầu tiên, 0 <= i <=iMAX,
Vor(Si) sơ đồ Vorronoi của Si *) 50 Begin i:=0; Si:=rỗng; While (ido Begin
(*Khởi tạo sơ đồ Voronoi cho đến khi nó chứa ít nhất một đỉnh*) increment i; GetScanLine Li;
Vor(Si) = VoroPreScan(Vor(Si-1, Li)); End
While (i < imax) do Begin Increment i; GetScanLine Li;
Vor(Li) := các đường trung trực sinh bởi các điểm sinh thuộc Li
Vor(Si) := VoroLink(Vor(Si-1), Vor(Li)); End End.
Giả sử xét trên hệ toạ độ thực. Ảnh vào được quét từ dưới lên. Toạ độ
y (biến i) tương ứng với từng dòng quét được tăng dần theo từng dòng.
Trong thủ tục trên, hàm quan trọng nhất là hàm VoroLink, hàm này thực
hiện việc trộn sơ đồ Voronoi của Li-1 dòng đã được quét trước đó với sơ đồ
Voronoi của dòng hiện tại thứ i. Trong vòng lặp trên, hàm VoroPreScan là
một biến thể của hàm VoroLink, có nhiệm vụ khởi tạo sơ đồ Voronoi và
thoát khỏi vòng lặp ngay khi nó thành lập được sơ đồ Voronoi chứa ít nhất
một đỉnh. Hàm VoroLink thực hiện việc trộn hai sơ đồ Voronoi Vor(Si-1) và
Vor(Li) với nhau để thành Vor(Si). 51 Chương 5:
CÁC KỸ THUẬT HẬU XỬ LÝ
5.1. RÚT GỌN SỐ LƯỢNG ĐIỂM BIỂU DIỄN 5.1.1. Giới thiệu
Rút gọn số lượng điểm biểu diễn là kỹ thuật thuộc phần hậu xử lý. Kết
quả của phần dò biên hay trích xương thu được 1 dãy các điểm liên tiếp.
Vấn đề đặt ra là hiệu có thể bá bớt các điểm thu được để giảm thiểu không
quan lưu trữ và thuận tiện cho việc đối sách hay không. Bài toán:
Cho đường cong gồm n điểm trong mặt phẳng (x1, y1), (x2, y2)…
(xn,yn). Hãy bỏ bớt 1 số điểm thuộc đường cong sao cho đường cong mới
nhận được là (Xi1; Yi1), (Xi2; Yi2)… (Xim; Yim) “gần giống” với đường cong ban đầu.
* Một số độ đo “gần giống”
+ Chiều dài (chiều rộng) của hình chữ nhật nhá nhất chứa đường cong
+ Khoảng cách lớn nhất từ đường cong đến đoạn thẳng nối 2 đầu mót của đường cong
+ Tỷ lệ giữa chiều dài và chiều rộng của hình chữ nhật nhá nhất chứa đường con
+ Số lần đường cong cắt đoạn thẳng nối 2 đầu mót
5.1.2. Thuật toán Douglas Peucker 5.1.2.1. Ý tưởng h > θ θ
Hình 5.1. Đơn giản hóa đường công theo thuật toán Douglas Peucker
Ý tưởng cơ bản của thuật toán Douglas-Peucker là xét xem khoảng
cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu mút đường cong
(xem Hình 5.1) có lớn hơn ngưỡng θ không. Nếu điều này đúng thì điểm xa
nhất được giữ lại làm điểm chia đường cong và thuật toán được thực hiện 52
tương tự với hai đường cong vừa tìm được. Trong trường hợp ngược lại,
kết quả của thuật toán đơn giản hoá là hai điểm đầu mút của đường cong.
Thuật toán Douglas-Peucker:
• Bước 1: Chọn ngưỡng θ.
• Bước 2: Tìm khoảng cách lớn nhất từ đường cong tới đoạn thẳng
nối hai đầu đoạn đường cong h.
• Bước 3: Nếu h ≤ θ thì dừng.
• Bước 4: Nếu h > θ thì giữ lại điểm đạt cực đại này và quay trở lại bước 1.
Nhận xét: Thuật toán này tỏ ra thuận lợi đối với các đường cong thu nhận
được mà gốc là các đoạn thẳng, phù hợp với việc đơn giản hoá trong quá
trình véctơ các bản vẽ kỹ thuật, sơ đồ thiết kế mạch in v.v..
5.1.2.2. Chương trình
//Hàm tính đường cao từ dinh đến đoạn thẳng nối hai điểm dau, cuoi
float Tinhduongcao (POINT dau, POINT cuoi, POINT dinh) { floot h; ⎢⎢tính đường cao returm h ; }
//Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong
void DPSimple(POINT *pLINE,int dau,int cuoi,BOOL *chiso,float θ) { int i, index = dau; float h, hmax = 0;
for(i = dau + 1; i < cuoi; i++) {
h= Tinhduongcao(pLINE[dau], pLINE[cuoi]; pLINE[i]); if(h > hmax) { hmax = h; index = i; 53 } } if(hmax ≤ θ)
for(i= dau + 1; i < cuoi, i++) chiso[i] = FALSE; else {
DPSimple(PLINE, dau, index, chiso, θ);
DPSimple(PLINE, index, cuoi, chiso, θ) ; } }
//Hàm rút gọn số lượng điểm DouglasPeucker
int DouglasPeucker(POINT *pLINE, int n, float θ) { int i, j; BOOL chiso [MAX_PT];
for(i = 0; i < m; i++) //Tất cả các điểm được giữ lại chiso[i] = TRUE;
DPSimple(pLINE, 0, n – 1, chiso, θ);
for(i = j = 0; i < n; i ++) if (chiso [i] ==TRUE) pLINE[j++] = pLINE[i]; return j; }
5.1.3. Thuật toán Band width 5.1.3.1. Ý tưởng
Trong thuật toán Band Width, ta hình dung có một dải băng di chuyển
từ đầu mút đường cong dọc theo đường cong sao cho đường cong nằm
trong di băng đó cho đến khi có điểm thuộc đường cong chạm vào biên của
dải băng, điểm này sẽ được giữ lại. Quá trình này được thực hiện với phần
còn lại của đường cong bắt đầu từ điểm vừa tìm được cho đến khi hết
đường cong. Cụ thể như sau: 54 P 3 P 2 d P 4 i d k P P 1 5
Hình 5.2. Đơn giản hóa đường cong với thuật toán Band Width
Bắt đầu bằng việc xác định điểm đầu tiên trên đường cong và coi đó
như là một điểm chốt (P1). Điểm thứ ba (P3) được coi là điểm động. Điểm
giữa điểm chốt và điểm động (P2) là điểm trung gian. Ban đầu khoảng cách
từ điểm trung gian đến đoạn thẳng nối điểm chốt và điểm động được tính
toán và kiếm tra. Nếu khoảng cách tính được này nhỏ hơn một ngưỡng θ
cho trước thì điểm trung gian có thể bỏ đi, tiến trình tiếp tục với điểm chốt
là điểm chốt cũ, điểm trung gian là điểm động cũ và điểm động là điểm kế
tiếp sau điểm động cũ. Trong trường hợp ngược lại, khoảng cách tính được
lớn hơn ngưỡng θ cho trước thì điểm trung gian sẽ được giữ lại, tiến trình
tiếp tục với điểm chốt là điển trung gian, điểm trung gian là điểm động cũ
và điểm động là điểm kế tiếp sau điểm động cũ. Tiến trình được lặp cho
đến hết đường cong (Hình 5.2 minh họa thuật toán Band-Width). Thuật toán Band-Width:
• Bước 1: Xác định điểm đầu tiên trên đường cong và coi đó như là
một điểm chốt (P1). Điểm thứ ba (P3) được coi là điểm
động. Điểm giữa điểm chốt và điểm động (P2) là điểm trung gian.
• Bước 2: Tính khoảng cách từ điểm trung gian đến đoạn thẳng nối
hai điểm chốt và điểm động.
• Bước 3: Kiểm tra khoảng cách tìm được nếu nhỏ hơn một ngưỡng
θ cho trước thì điểm trung gian có thể bỏ đi. Trong trường
hợp ngược lại điểm chốt chuyển đến điểm trung gian.
• Bước 4: Chu trình được lặp lại thì điểm trung gian được chuyển
đến điểm động và điểm kế tiếp sau điểm động được chỉ
định làm điểm động mới..
Nhận xét: Thuật toán này tăng tốc độ trong trường hợp đường ống chứa
nhiều điểm, điều đó có nghĩa là độ lệch giữa các điểm trong đường thẳng là
nhỏ, hay độ dày nét của đường được véctơ hoá là mảnh. 55
5.1.3.2. Chương trình
//Hàm tính đường cao từ đỉnh đến đoạn thẳng nối hai điểm dau, cuoi
float Tinhduongcao(POINT dau, POINT cuoi, POINT dinh) { floot h; ⎢⎢tính đường cao returm h ; }
//Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong
void BWSimple(POINT *pLINE, int chot, int tg, BOOL *chiso, float θ, int n) {
if(Tinhduongcao(pLINE[chot], pLINE[tg+1], pLINE[tg]) ≤ θ) chiso[tg] = 0; else chot = tg; tg = tg + 1 if(tg < n - 1)
BWSimple (pLINE, chot, tg, chiso, θ, n) ; }
//Hàm rút gọn số lượng điểm BandWidth
int BandWidth(POINT *pLINE, int n, floot θ) { int i, j; BOOL chiso [MAX_PT]; for (i = 0; i < n; i++)
chiso[i]= TRUE; //Tất cả các điểm được giữ lại
BWSimple(pLINE, 0, 1, chiso, θ, n); for(i= j= 0; i < n; i++) if(chiso [i]== TRUE) 56 pLINE [j ++1] = pLINE [i]; return j; }
5.1.4. Thuật toán Angles 5.1.4.1. Ý tưởng
Tương tự như thuật toán Band Width nhưng thay việc tính toán
khoảng cách bởi tính góc. Cụ thể thuật toán bắt đầu với điểm đầu đường cong (P1) là điểm chốt. P 3 α P k 2 αi P 4 P 5 P 1
Hình 5.3. Đơn giản hóa đường cong với thuật toán Angles
Điểm thứ 3 của đường cong (P3) là điểm động, điểm giữa điểm chốt và
điểm động (P2) là điểm trung gian
Góc tạo bởi điểm chốt, trung gian, động với điểm trung gian là đỉnh
việc tính toán và kiểm tra
Nếu thì điểm trung gian có thể bỏ đi trong trường hợp ngược lại điểm
chốt sẽ là điểm trung gian cũ và quá trình lặp với điểm trung gian là điểm
động cũ, điểm động mới là điểm kế tiếp sau điểm động cũ. Tiến trình thực
hiện cho đến hết đường cong.
5.1.4.2. Chương trình
//Hàm tính đường cao từ đỉnh đến đoạn thẳng nối hai điểm dau, cuoi
float Tinhgoc(POINT dau, POINT cuoi, POINT dinh) { float θ; ⎢⎢tinhgoc (tự viết) return θ; }
//Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong
void ALSimple(POINT *pLINE,int chot,int tg,BOOL *chiso,float θ,int n) { 57
if(Tinhgoc(pLINE[chot], pLINE[tg], pLINE[tg+1]) > θ) chiso[tg] = FALSE; else chot = tg; tg = tg + 1; if(tg < n - 1)
ALSimple(pLINE, chot, tg, chiso, θ, n); }
//Hàm rút gọn số lượng điểm Angles
int Angles(POINT *pLINE, int n, float θ) { int i, j, chiso [MAX];
for (i = 0; i < n; i++) //Tất cả các điểm được giữ lại chiso[i]= TRUE;
ALSiple (PLINE, 0, 1 chiso, θ, n) ;
for (i = j = 0; i < n; i++) if (chiso ==TRUE) pLINE[j++]= pLINE [i]; return j; } * Chú ý:
Với θ= 0 thuật toán DouglasPeucker và BandWidth sẽ bỏ đi các điểm
giữa thẳng hàng. Thuật toán Angles phải có θ= 180o để bỏ đi các điểm giữa thẳng hàng.
5.2. XẤP XỈ ĐA GIÁC BỞI CÁC HÌNH CƠ SỞ
Các đối tượng hình học được phát hiện thường thông qua các kỹ thuật
dò biên, kết quả tìm được này là các đường biên xác định đối tượng. Đó là,
một dãy các điểm liên tiếp đóng kính, sử dụng các thuật toán đơn giản hoá
như Douglas Peucker, Band Width, Angle v.v.. ta sẽ thu được một polyline
hay nói khác đi là thu được một đa giác xác định đối tượng dấu. Vấn đề là
ta cần phải xác định xem đối tượng có phải là đối tượng cần tách hay
không? Như ta đã biết một đa giác có thể có hình dạng tựa như một hình cơ 58
sở, có thể có nhiều cách tiếp cận xấp xỉ khác nhau. Cách xấp xỉ dựa trên các đặc trưng cơ bản sau:
Đặc trưng toàn cục: Các mô men thống kê, số đo hình học như chu
vi, diện tích, tập tối ưu các hình chữ nhật phủ hay nội tiếp đa giác v.v..
Đặc trưng địa phương: Các số đo đặc trưng của đường cong như
góc, điểm lồi, lõm, uốn, cực trị v.v.. Nhận dạng đối tượng Bất biến Bất biến đồng dạng Aphin Đường tròn Ellipse Ellipse Tam giác Hình chữ nhật Tứ giác
Hình 5.4. Sơ đồ phân loại các đối tượng theo bất biến
Việc xấp xỉ tỏ ra rất có hiệu quả đối với một số hình phẳng đặc biệt
như tam giác, đường tròn, hình chữ nhật, hình vuông, hình ellipse, hình
tròn và một đa giác mẫu.
5.2.1 Xấp xỉ đa giác theo bất biến đồng dạng
Hình 5.5. Xấp xỉ đa giác bởi một đa giác mẫu
Một đa giác với các đỉnh V0,..,Vm-1 được xấp xỉ với đa giác mẫu
U0,..,Un-1 với độ đo xấp xỉ như sau: Δ E V U d ( , ) = min , 0≤d m−1 n 59 Trong đó n−1 2 area V ( V L ) Δ = min , k 0 m = −1 , với R r θ là 2 ∑ kR U + a V d θ j
( j+d ) mod m 0≤θ ≤2π ,α Rarea U ( U L ) j=0 0 n−1 d
phép quay quanh gốc toạ độ một góc θ.
Trong đó, Δd được tính hiệu quả bằng công thức sau: n−1 n−1 n−1 n−1 1 Δ = ∑ V | |2 − | 2 2 2 2 ( ) mod ∑V | +k ( ) mod
U| | − k|∑U V | d j+d m j+d m j
j ( j+d ) mod m =0 n j j=0 j=0 j=0 d
Ở đây Uj, Vj được hiểu là các số phức tại các đỉnh tương ứng. Khi
m >> n thì độ phức tạp tính toán rất lớn. Với các hình đặc biệt như hình
tròn, ellipse, hình chữ nhật, hình xác định duy nhất bởi tâm và một đỉnh (đa
giác đều ) ta có thể vận dụng các phương pháp đơn giản hơn như bình
phương tối thiểu, các bất biến thống kê và hình học. Định nghĩa 5.1
Cho đa giác Pg có các đỉnh U0, U1,..., Un(U0 ≡Un) Khi đó mô men bậc
p+q được xác định như sau: M x p yq = dxdy ∫∫ . pq Pg
Trong thực hành để tính tích phân trên người ta thường sử dụng công
thức Green hoặc có thể phân tích phần bên trong đa giác thành tổng đại số
của các tam giác có hướng Δ OUiUi+1 . U U 2 1 p q
f (x, y)x y dxdy ∫∫ = Pg - n U 0 U 3
∑−1sign(x y x y ) × i i+1 i+1 i O(0,0) i=0 p q
f (x, y)x y dxdy ∫∫ - OU Δ U i i +1 Un-
Hình 5.6. Phân tích miền đa giác thành tổng đại số các miền tam giác 60
a. Xấp xỉ đa giác bằng đường tròn
Dùng phương pháp bình phương tối thiểu, ta có độ đo xấp xỉ: n 1 E(Pg,Cr)= min
∑(x2 + y2 + ax +by + c)2 i i i i a,b,c Rn i=1
Hình 5.7. Xấp xỉ đa giác bằng đường tròn
b. Xấp xỉ đa giác bằng ellipse
Cũng như đối với đường tròn phương trình xấp xỉ đối với ellipse được cho bởi công thức: n 1 E(Pg,El)= min
∑(x2 + ay2 +bx y + cx + dy + e)2 i i i i i i
a,b,c,d ,eR n i=1
Một biến thể khác của phương pháp bình phương tối thiểu khi xấp xỉ
các đường cong bậc hai được đưa ra trong [7].
c. Xấp xỉ đa giác bởi hình chữ nhật
Sử dụng tính chất diện tích bất biến qua phép quay, xấp xỉ theo diện
tích như sau: Gọi μ ,μ ,μ là các mô men bậc hai của đa giác (tính theo 11 20 02
diện tích). Khi đó góc quay được tính bởi công thức sau: 2μ tg2ϕ = 11 μ - μ . 20 02
Gọi diện tích của hình chữ nhật nhỏ nhất có các cạnh song song với
các trục quán tính và bao quanh đa giác Pg là S.
Kí hiệu E(Pg, Rect)= S area(Pg) y ϕ x
Hình 5.8. Xấp xỉ đa giác bằng hình chữ nhật 61
d. Xấp xỉ đa giác bởi đa giác đều n cạnh
Gọi M(x0,y0) là trọng tâm của đa giác, lấy một đỉnh Q tuỳ ý của đa
giác, xét đa giác đều n cạnh Pg’ tạo bởi đỉnh Q với tâm là M. Kí hiệu E(Pg, Pg’)=
area( Pg) − area( Pg')
E(Pg, En)=min E(Pg,Pg’) khi Q chạy khắp các đỉnh của đa giác.
5.2.2 Xấp xỉ đa giác theo bất biến aphin
Trong [7] đưa ra mô hình chuẩn tắc về bất biến aphin, cho phép chúng
ta có thể chuyển bài toán xấp xỉ đối tượng bởi bất biến aphin về bài toán
xấp xỉ mẫu trên các dạng chuẩn tắc. Như vậy có thể đưa việc đối sánh các
đối tượng với mẫu bởi các bất biến đồng dạng, chẳng hạn việc xấp xỉ bởi
tam giác, hình bình hành, ellipse tương đương với xấp xỉ tam giác đều, hình
vuông, hình tròn v.v... Thủ tục xấp xỉ theo bất biến aphin một đa giác với
hình cơ sở được thực hiện tuần tự như sau: + Bước 0:
Phân loại bất biến aphin các dạng hình cơ sở
Dạng hình cơ sở Dạng chuẩn tắc Tam giác Tam giác đều Hình bình hành Hình vuông Ellipse Đường tròn … … + Bước 1:
Tìm dạng chuẩn tắc cơ sở Pg' thoả mãn điều kiện: m ⎧ = m = 0 (phép tịnh tiến) 01 10 ⎪ ⎨m = m = 1 02 20
(phép co dãn theo hai trục x, y) (**) ⎪ m = m = 0 ⎩ 13 31 + Bước 2:
Xác định biến đổi aphin T chuyển đa giác thành đa giác Pg ở dạng
chuẩn tắc (thoả mãn tính chất (**)).
Xấp xỉ đa giác Pg với dạng chuẩn tắc cơ sở Pg’ tìm được ở bước 1 với
độ đo xấp xỉ E(Pg,Pg’). + Bước 3:
Kết luận, đa giác ban đầu xấp xỉ T-1(Pg’) với độ đo xấp xỉ E(Pg,Pg’). 62
Đối với bước 1 trong [7] đã đưa ra hai ví dụ sau: Ví dụ 1:
Tồn tại duy nhất tam giác đều ΔP1P2P3 thoả mãn tính chất (**) là 4 28 3 α = P1=(0,-2α),P2=( , α 3 α) , P3= (− 3 , α α) , 3 . Ví dụ 2:
Tồn tại hai hình vuông P1P2 P3 P4 thoả mãn tính chất (**)
Hình vuông thứ nhất có 4 đỉnh tương ứng là (-p,-p),(-p,p), (p,- 3 4 p),(p,p), với p= 4
Hình vuông thứ hai có 4 đỉnh tương ứng là (-p,0),(p,0), (0,-p),(0,p), với p= 4 3 .
5.3. BIẾN ĐỔI HOUGH
5.3.1. Biến đổi Hongh cho đường thẳng
Bằng cách nào đó ta thu được một số điểm vấn đề đặt ra là cần phải
kiểm tra xem các điểm có là đường thẳng hay không Bài toán:
Cho n điểm (xi; yi) i = 1, n và ngưỡng θ hãy kiểm tra n điểm có tạo
thành đường thẳng hay không? * Ý tưởng
Giả sử n điểm nằm trên cùng một đường thẳng và đường thẳng có phương trình y = ax + b
Vì (xi, yi) i = 1, n thuộc đường thẳng nên y1 = ax1 + b, ∀i = 1, n
⇔ b = - xia + y1; ∀i = 1, n
Như vậy, mỗi điểm (xi; yi) trong mặt phẳng sẽ tương ứng với một số
đường thẳng b = - xia + yi trong mặt phẳng tham số a, b. n điểm (xi; yi) i =
1, n thuộc đường thẳng trong mặt phẳng tương ứng với n đường thẳng
trong mặt phẳng tham số a, b giao nhau tại 1 điểm và điểm giao chính là a,
b. Chính là hệ số xác định phương trình của đường thẳng mà các điểm nằm vào. 63 * Phương pháp:
- Xây dựng mảng chỉ số [a, b] và gán giá trị 0 ban đầu cho tất cả các phân tử của mảng
- Với mỗi (xi; yi) và ∀a, b là chỉ số của phần tử mảng thoả mãn
b = - xia + yi tăng giá trị của phân tử mảng tương ứng lên 1
- Tìm phần tử mảng có giá trị lớn nhất nếu giá trị lớn nhất tìm được so
với số phân tử lớn hơn hoặc bằng ngưìng θ cho trước thì ta có thể kết luận
các điểm nằm trên cùng 1 đường thẳng và đường thẳng có phương trình
y = ax + b trong đó a, b tương ứng là chỉ số của phần tử mảng có giá trị lớn nhất tìm được: Ví dụ:
Cho 5 điểm (0, 1); (1, 3); (2, 5); (3, 5); (4, 9) và θ = 80%. Hãy kiểm
tra xem 5 điểm đã cho có nằm trên cùng một đường thẳng hay không? Hãy
cho biết phương trình đường thẳng nếu có?
- Lập bảng chỉ số [a, b] và gán giá trị 0 + (0, 1): b = 1 + (1, 3): b = -a + 3 + (2, 5): b = -2a + 5 + (3, 5): b = -3a + 5 + (4, 9): b = -4a + 9
- Tìm phần tử lớn nhất có giá trị 4 4/5 = 80%
- Kết luận: 5 điểm này nằm trên cùng 1 đường thẳng Phương trình: y = 2x + 1
5.3.2. Biến đổi Hough cho đường thẳng trong tọa độ cực
5.3.2.1. Đường thẳng Hough trong tọa độ cực
64 0 y ϕ r x.cosϕ+y.sinϕ=r H x
Hình 5.9. Đường thẳng Hough trong toạ độ cực
Mỗi điểm (x,y) trong mặt phẳng được biểu diễn bởi cặp (r,ϕ) trong tọa độ cực.
Tương tự mỗi đường thẳng trong mặt phẳng cũng có thể biểu diễn bởi
một cặp (r,ϕ) trong tọa độ cực với r là khoảng cách từ gốc tọa độ tới đường
thẳng đó và ϕ là góc tạo bởi trục 0X với đường thẳng vuông góc với nó,
hình 5.9 biểu diễn đường thẳng hough trong tọa độ Decard.
Ngược lại, mỗi một cặp (r,ϕ) trong toạ độ cực cũng tương ứng biểu
diễm một đường thẳng trong mặt phẳng.
Giả sử M(x,y) là mộ điểm thuộc đường thẳng được biểu diễn bởi (r,ϕ),
gọi H(X,Y) là hình chiếu của gốc toạ độ O trên đường thẳng ta có: X= r. cosϕ và Y= r.sinϕ Mặt khác, ta có: OH.HA=0
Từ đó ta có mối liên hệ giữa (x,y) và (r,ϕ) như sau: x*cosϕ+y*sinϕ= r.
Xét n điểm thẳng hàng trong tọa độ Đề các có phương trình
x*cosϕ0+y*sinϕ0= r0. Biến đổi Hough ánh xạ n điểm này thành n đường sin
trong tọa độ cực mà các đường này đều đi qua (r0,ϕ0). Giao điểm (r0,ϕ0) của
n đường sin sẽ xác định một đường thẳng trong hệ tọa độ đề các. Như vậy,
những đường thẳng đi qua điểm (x,y) sẽ cho duy nhất một cặp (r,ϕ) và có
bao nhiêu đường qua (x,y) sẽ có bấy nhiêu cặp giá trị (r,ϕ).
5.3.2.2. Áp dụng biến đổi Hough trong phát hiện góc nghiêng văn bản
Ý tưởng của việc áp dụng biến đổi Hough trong phát hiện góc nghiêng
văn bản là dùng một mảng tích luỹ để đếm số điểm ảnh nằm trên một
đường thảng trong không gian ảnh. Mảng tích luỹ là một mảng hai chiều
với chỉ số hàng của mảng cho biết góc lệch ϕ của một đường thẳng và chỉ
số cột chính là giá trị r khoảng cách từ gốc toạ độ tới đường thẳng đó. Sau
đó tính tổng số điểm ảnh nằm trên những đường thẳng song song nhau theo 65
các góc lệch thay đổi. Góc nghiêng văn bản tương ứng với góc có tổng gía
trị mảng tích luỹ cực đại.
Theo biến đổi Hough, mỗi một đường thẳng trong mặt phẳng tương
ứng được biểu diễn bởi một cặp (r,ϕ). Giả sử ta có một điểm ảnh (x,y) trong
mặt phẳng, vì qua điểm ảnh này có vô số đường thẳng, mỗi đường thẳng lại
cho một cặp (r,ϕ) nên với mỗi điểm ảnh ta sẽ xác định được một số cặp
(r,ϕ) thoả mãn phương trình Hough.
x.cosϕ+y.sinϕ=r1 0 y Hough[ϕ][r1]=3 ϕ
x.cosϕ+y.sinϕ=r2 Hough[ϕ][r 1]=4 x
Hình 5.10. Ứng dụng biến đổi Hough phát hiện góc
Hình vẽ trên minh hoạ cách dùng biến đổi Hough để phát hiện góc
nghiêng văn bản. Giả sử ta có một số điểm ảnh, đây là những điểm giữa
đáy các hình chữ nhật ngoại tiếp các đối tượng đã được lựa chọn từ các
bước trước. Ở đây, ta thấy trên mặt phẳng có hai đường thẳng song song
nhau. Đường thẳng thứ nhất có ba điểm ảnh nên giá trị mảng tích luỹ bằng
3, đường thẳng thứ hai có gia trị mảng tích luỹ bằng 4. Do đó, tổng giá trị
mảng tích luỹ cho cùng góc ϕ trường hợp này bằng 7.
Gọi Hough[360][Max] là mảng tích lũy, giả sử M và N tương ứng là
chiều rộng và chiều cao của ảnh, ta có các bước chính trong quá trình áp
dụng biến đổi Hough phát hiện góc nghiêng văn bản như sau:
+ Bước 1: Khai báo mảng chỉ số Hough[ϕ][r] với 0 ≤ ϕ ≤ 3600
và 0≤ r ≤ M * M + N * N .
+ Bước 2: Gán giá trị khởi tạo bằng 0 cho các phần tử của mảng.
+ Bước 3: Với mỗi cặp (x,y) là điểm giữa đáy của hình chữ nhật
ngoại tiếp một đối tượng. -
Với mỗi ϕi từ 0 đến 360 tính giá trị ri theo công thức ri= x.cosϕi+y.sinϕ
- Làm tròn giá trị ri thành số nguyên gần nhất là r0 -
Tăng giá trị của phần tử mảng Hough[ϕi][r0] lên một đơn vị. 66
+ Bước 4: Trong mảng Hough[ϕ][r] tính tổng giá trị các phần tử theo
từng dòng và xác định dòng có tổng giá trị lớn nhất.
Do số phần tử của một phần tử mảng Hough[ϕ0][r0] chính là số điểm
ảnh thuộc đường thẳng x.cosϕ0+y.sinϕ0= r0 vì vậy tổng số phần tử của một
hàng chính là tổng số điểm ảnh thuộc các đường thẳng tương ứng được
biểu diễn bởi góc ϕ của hàng đó. Do đó, góc nghiêng của toán văn bản
chính là hàng có tổng giá trị các phần tử mảng lớn nhất. 67 Phụ lục 1:
MỘT SỐ ĐỊNH DẠNG TRONG XỬ LÝ ẢNH
Hiện nay trên thế giới có trên 50 khuôn dạng ảnh thông dụng.
Sau đây là một số định dạng ảnh hay dùng trong quá trình xử lý ảnh hiện nay.
1. Định dạng ảnh IMG
Ảnh IMG là ảnh đen trắng, phần đầu của ảnh IMG có 16 byte chứa các thông tin:
• 6 byte đầu: dùng để đánh dấu định dạng ảnh. Giá trị của 6
byte này viết dưới dạng Hexa: 0x0001 0x0008 0x0001
• 2 byte tiếp theo: chứa độ dài mẫu tin. Đó là độ dài của dãy
các byte kề liền nhau mà dóy này sẽ được lặp lại một số lần
nào đó. Số lần lặp này sẽ được lưu trong byte đếm. Nhiều dãy
giống nhau được lưu trong một byte.
• 4 byte tiếp: mô tả kích cỡ pixel.
• 2 byte tiếp: số pixel trên một dòng ảnh.
• 2 byte cuối: số dòng ảnh trong ảnh.
Ảnh IMG được nén theo từng dòng, mỗi dòng bao gồm các gói
(pack). Các dòng giống nhau cũng được nén thành một gói. Có 4 loại gói sau:
• Loại 1: Gói các dòng giống nhau.
Quy cách gói tin này như sau: 0x00 0x00 0xFF Count. Ba byte
đầu tiên cho biết số các dãy giống nhau, byte cuối cho biết số các dòng giống nhau.
• Loại 2: Gói các dãy giống nhau.
Quy cách gói tin này như sau: 0x00 Count. Byte thứ hai cho biết
số các dãy giống nhau được nén trong gói. Độ dài của dãy ghi ở đầu tệp.
• Loại 3: Dãy các Pixel không giống nhau, không lặp lại và không nén được.
Quy cách gói tin này như sau: 0x80 Count. Byte thứ hai cho biết
độ dài dãy các pixel không giống nhau không nén được. 68
• Loại 4: Dãy các Pixel giống nhau.
Tuỳ theo các bít cao của byte đầu tiên được bật hay tắt. Nếu bít
cao được bật (giá trị 1) thỡ đây là gói nén các byte chỉ gồm bít 0, số
các byte được nén được tính bởi 7 bít thấp còn lại. Nếu bớt cao tắt
(giỏ trị 0) thì đây là gói nén các byte gồm toán bít 1. Số các byte
được nén được tính bởi 7 bít còn lại.
Các gói tin của file IMG rất đa dạng do ảnh IMG là ảnh đen
trắng, do vậy chỉ cần 1 bít cho 1 pixel thay vì 4 hoặc 8 như đã nói ở
trên. Toàn bộ ảnh chỉ có những điểm sáng và tối tương ứng với giá
trị 1 hoặc 0. Tỷ lệ nén của kiểu định dạng này là khá cao.
2. Định dạng ảnh PCX
Định dạng ảnh PCX là một trong những định dạng ảnh cổ điển.
Nó sử dụng phương pháp mó hoỏ loạt dài RLE (Run – Length –
Encoded) để nén dữ liệu ảnh. Quá trỡnh nộn và giải nộn được thực
hiện trên từng dũng ảnh. Thực tế, phương pháp giải nén PCX kém
hiệu quả hơn so với kiểu IMG. Tệp PCX gồm 3 phần: đầu tệp
(header), dữ liệu ảnh (Image data) và bảng màu mở rộng.
Header của tệp PCX có kích thước cố định gồm 128 byte và được phân bố như sau:
• 1 byte: chỉ ra kiểu định dạng.Nếu là PCX/PCC thì nó luôn có giá trị là 0Ah.
• 1 byte: chỉ ra version sử dụng để nén ảnh, có thể có các giá trị sau: + 0: version 2.5.
+ 2: version 2.8 với bảng màu.
+ 3: version 2.8 hay 3.0 không có bảng màu.
+ 5: version 3.0 cố bảng màu.
• 1 byte: chỉ ra phương pháp mã hoá. Nếu là 0 thì mã hoá theo
phương pháp BYTE PACKED, ngược lại là phương pháp RLE.
• 1 byte: Số bít cho một điểm ảnh plane.
• 1 word: toạ độ góc trái của ảnh. Với kiểu PCX nó có giá trị là
(0,0), cũn PCC thì khác (0,0).
• 1 word: toạ độ góc phải dưới.
• 1 word: kích thước bề rộng và bề cao của ảnh. 69
• 1 word: số điểm ảnh.
• 1 word: độ phân giải màn hình. • 1 word.
• 48 byte: chia nó thành 16 nhóm, mỗi nhóm 3 byte. Mỗi nhóm
này chứa thông tin về một thanh ghi màu. Như vậy ta có 16 thanh ghi màu.
• 1 byte: không dùng đến và luôn đặt là 0.
• 1 byte: số bớt plane mà ảnh sử dụng. Với ảnh 16 màu, giá trị
này là 4, với ảnh 256 mầu (1pixel/8bits) thì số bít plane lại là 1.
• 1 byte: số bytes cho một dòng quét ảnh.
• 1 word: kiểu bảng màu. • 58 byte: không dùng.
Định dạng ảnh PCX thường được dùng để lưu trữ ảnh và thao
tác đơn giản, cho phép nén và giải nén nhanh. Tuy nhiên, vì cấu trúc
của nó cố định, nên trong một số trường hợp làm tăng kích thước lưu
trữ. Cũng vì nhược điểm này mà một số ứng dụng sử dụng một kiểu
định dạng khác mềm dẻo hơn: định dạng TIFF (Targed Image File
Format) sẽ mô tả dưới đây.
3. Định dạng ảnh TIFF
Kiểu định dạng TIFF được thiết kế để làm nhẹ bớt các vấn đề
liên quan đến việc mở rộng tệp ảnh cố định. Về cấu trúc, nó cũng gồm 3 phần chính:
• Phần Header(IFH): cú trong tất cả cỏc tệp TIFF và gồm 8 byte:
+ 1 word: chỉ ra kiểu tạo tệp trên máy tính PC hay máy
Macintosh. Hai loại này khác nhau rất lớn ở thứ tự các
byte lưu trữ trong các số dài 2 hay 4 byte. Nếu trường
này có giá trị là 4D4Dh thì đó là ảnh cho máy Macintosh,
nếu là 4949h là của máy PC.
+ 1 word: version. từ này luôn có giá trị là 42. đây là đặc
trưng của file TIFF và không thay đổi.
+ 2 word: giá trị Offset theo byte tính từ đầu tới cấu trúc
IFD là cấu trúc thứ hai của file. Thứ tự các byte này phụ
thuộc vào dấu hiệu trường đầu tiên. 70
• Phần thứ 2(IFD): Không ở ngay sau cấu trúc IFH mà vị trí
được xác định bởi trường Offset trong đầu tệp. Có thể có một
hay nhiều IFD cùng tồn tại trong một file. Một IFD bao gồm:
+ 2 byte: chứa các DE ( Directory Entry).
+ 12 byte là các DE xếp liên tiếp, mỗi DE chiếm 12 byte.
+ 4 byte: chứa Offset trỏ tới IFD tiếp theo. Nếu đây là IFD
cuối cùng thì trường này có giá trị 0.
• Phần thứ 3: các DE: các DE có dộ dài cố định gồm 12 byte và chia làm 4 phần:
+ 2 byte: chỉ ra dấu hiệu mà tệp ảnh đó được xây dựng.
+ 2 byte: kiểu dữ liệu của tham số ảnh. Có 5 kiểu tham số cơ bản: 1: BYTE (1 byte) 2: ASCII (1 byte) 3: SHORT (2 byte). 4: LONG (4 byte) 5: RATIONAL (8 byte)
+ 4 byte: trường độ dài chưa số lượng chỉ mục của kiểu dữ
liệu đó chỉ ra. Nó không phải là tổng số byte cần thiết để
lưu trữ. Để có số liệu này ta cần nhân số chỉ mục với kiểu dữ liệu đã dùng.
+ 4 byte: đó là Offset tới điểm bắt đầu dữ liệu liên quan tới
dấu hiệu, tức là liên quan với DE không phải lưu trữ vật
lý cùng với nó nằm ở một vị trí nào đó trong file.
Dữ liệu chứa trong tệp thường được tổ chức thành các nhóm
dòng (cột) quét của dữ liệu ảnh. Cách tổ chức này làm giảm bộ nhớ
cần thiết cho việc đọc tệp. Việc giải nén được thực hiện theo 4 kiểu
khác nhau được lưu trữ trong byte dấu hiệu nén. 71
4. Định dạng file ảnh BITMAP
Mỗi file BITMAP gồm đầu file chứa các thông tin chung về file,
đầu thông tin chứa các thông tin về ảnh, một bảng màu và một mảng
dữ liệu ảnh. Khuôn dạng được cho như sau: BITMAPFILEHEADER bmfh; BITMAPINFOHEADER bmih; RGBQUAD aColors[]; BYTE aBitmapBits[];
Trong đó, các cấu trúc được định nghĩa như sau:
typedef struct tagBITMAPFILEHEADER { /* bmfh */ UINT bfType; DWORD bfSize; UINT bfReserved1; UINT bfReserved2; DWORD bfOffBits; } BITMAPFILEHEADER;
typedef struct tagBITMAPINFOHEADER { /* bmih */ DWORD biSize; LONG biWidth; LONG biHeight; WORD biPlanes; WORD biBitCount; DWORD biCompression; DWORD biSizeImage; LONG biXPelsPerMeter; LONG biYPelsPerMeter; DWORD biClrUsed; DWORD biClrImportant;
} BITMAPINFOHEADER, *LPBITMAPINFOHEADER; với biSize kích
thước của BITMAPINFOHEADER
biWidth Chiều rộng của ảnh, tính bằng số điểm ảnh
biHeight Chiều cao của ảnh, tính bằng số điểm ảnh 72
biPlanes Số plane của thiết bị, phải bằng 1
biBitCount Số bit cho một điểm ảnh biCompression Kiểu nén biSizeImage Kích
thước của ảnh tính bằng byte
độ phân giải ngang của thiết bị, tính bằng điểm ảnh trên biXPelsPerMeter met
độ phân giải dọc của thiết bị, tính bằng điểm ảnh trên biYPelsPerMeter met
biClrUsed Số lượng các màu thực sự được sử dụng
Số lượng các màu cần thiết cho việc hiển thị, bằng 0 nếu biClrImportant
tất cả các màu đều cần để hiển thị
Nếu bmih.biBitCount > 8 thì mảng màu rgbq[] trống, ngược lại thì
mảng màu có 2<< bmih.biBitCount phần tử.
typedef struct tagRGBQUAD { /* rgbq */ BYTE rgbBlue; BYTE rgbGreen; BYTE rgbRed; BYTE rgbReserved; } RGBQUAD; Ta cũng có:
typedef struct tagBITMAPINFO { BITMAPINFOHEADER bmiHeader; RGBQUAD bmiColors[1]; } BITMAPINFO, *PBITMAPINFO; 73 Phụ lục 2:
CÁC BƯỚC THAO TÁC VỚI FILE AVI
AVI là chuẩn video thường được tích hợp trong các thư viện của
các môi trường lập trình. Để xử lý video, cần có các thao tác cơ bản
để chuyển về xử lý ảnh các khung hình (các frames).
1. Bước 1: Mở và đóng thư viện
Trước mọi thao tác với file AVI, chúng ta phải mở thư viện: AVIFileInit( )
Hàm này không cần tham số, có nhiệm vụ khởi động thư viện
cung cấp các hàm thao tác với file AVI. (Đó là thư viện vfw32.lib,
được khai báo trong file vfw.h).
Sau tất cả các thao tác bạn phải nhớ đóng thư viện đã mở lúc đầu, chỉ bằng lệnh: AVIFileExit( )
Nếu thiếu bất cứ hàm nào, dù là mở hay đóng thư viện thì trình
biên dịch đều sẽ thông báo lỗi.
2. Bước 2: Mở và đóng file AVI để thao tác:
Sau khi mở thư viện, bạn phải mở file AVI bạn định thao tác:
AVIFileOpen(PAVIFILE* ppfile, LPCSTR fname, UINT mode, CLSID pclsidHandler)
Thực chất, hàm này tạo ra một vùng đệm chứa con trỏ trỏ đến
file có tên là fname cần mở. Và ppfile là con trỏ trỏ đến vùng bộ đệm
đó. Tham số mode quy định kiểu mở file; chẳng hạn OF_CREATE
để tạo mới, OF_READ để đọc, OF_WRITE để ghi …. Tham số cuối dùng là NULL.
Trước khi đóng thư viện, bạn phải đóng file AVI đã mở, bằng cách dùng hàm:
AVIFileRelease(PAVIFILE pfile)
Trong đó, pfile là con trỏ trỏ đến file cần đóng. 74 3. Bước 3:
Mở dòng dữ liệu hình ảnh hay âm thanh trong file AVI đã mở ra để thao tác:
AVIFileGetStream(PAVIFILE pfile, PAVISTREAM * ppavi,
DWORD fccType, LONG lParam)
Trong đó, pfile là con trỏ đến file đã mở; ppavi trỏ đến dòng dữ
liệu kết quả; fccType là loại dòng dữ liệu chọn để mở, là
streamtypeAUDIO nếu là tiếng và streamtypeVIDEO nếu là hình,…
lParam đếm số loại dòng được mở, là 0 nếu chỉ thao tác với một loại dòng dữ liệu.
Sau các thao tác với dòng dữ liệu này, bạn nhớ phải đóng nó lại:
AVIStreamRelease(PAVITREAM pavi).
4. Bước 4: Trường hợp thao tác với dữ liệu hình của phim
Chuẩn bị cho thao tác với khung hình (frames):
AVIStreamGetFrameOpen(PAVISTREAM pavi,
LPBITMAPINFOHEADER lpbiWanted)
Trong đó pavi trỏ đến dòng dữ liệu đã mở, lpbiWanted là con
trỏ trỏ đến cấu trúc mong muốn của hình ảnh, ta dùng NULL để sử
dụng cấu trúc mặc định.
Hàm này trả về đối tượng có kiểu PGETFRAME để dùng cho bước 5.
Sau khi thao tác với các frame rồi, phải gọi hàm :
AVIStreamGetFrameClose(PGETFRAME pget)
5. Bước 5: Thao tác với frame Dùng hàm
AVIStreamGetFrame(PGETFRAME pget, LONG lpos)
Hàm này trả về con trỏ trỏ đến dữ liệu của frame thứ lpos. Dữ
liệu đó có kiểu là DIB đã định khối.
Thực hiện các thao tác mong muốn. 75
TÀI LIỆU THAM KHẢO
[1]. Lương Mạnh Bá, Nguyễn Thanh Thủy (2002), Nhập Môn Xử lý ảnh
số, Nxb Khoa học và Kỹ thuật, 2002.
[2]. Anil K.Jain (1989), Fundamental of Digital Image Processing.
Prentice Hall, Engwood cliffs.
[3]. J.R.Paker (1997), Algorithms for Image processing and Computer
Vision. John Wiley & Sons, Inc.
[4]. Randy Crane (1997), A simplified approach to image processing, Prentice-Hall, Inc.
[5]. John C.Russ (1995), The Image Procesing Handbook. CRC Press, Inc.
[6]. Adrian Low (1991), Introductory Computer Vision and Image
Processing, Copyright (c) 1991 by McGrow Hill Book Company (UK) Limited.
[7]. T. Pavlidis (1982), Algorithms for Graphics and Image Processing, Computer Science Press. 76