Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
PHẠM NGỌC QUÝ PHÁT HIỆN BIÊN, BIỂU DIỄN FOURIER ELLIPTIC
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN PHẠM NGỌC QUÝ
PHÁT HIỆN BIÊN, BIỂU DIỄN FOURIER ELLIPTIC
VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 604801
`
1.2.1 Khái niệm về biên ảnh và các phương pháp phát hiện
biên cơ bản........................................................................................... 9
1.2.2 Vai trò của biên trong nhận dạng ảnh ........................................ 14
1.2.3 Biểu diễn biên dựa trên mô tả Fourier ....................................... 14
1.2.3.1 Phương pháp dựa trên mô tả Fourier................................. 16
1.2.3.2 Phương pháp góc quay ............................................... 19
CHƢƠNG 2: MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN BIÊN
VÀ PHÉP BIỂU DIỄN FORIER ELLIPTIC ............................................................. 22
2.1 Một số phương pháp phát hiện biên ...................................................... 22
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
2.1.1. Phương pháp phát hiện biện trực tiếp ....................................... 22
2.1.2 Phương pháp phát hiện biên gián tiếp ........................................ 31
2.1.3 Phương pháp phát hiện biên kết hợp.......................................... 32
2.1.4 Phát hiện biên dựa vào trung bình cục bộ .................................. 38
2.1.5 Cải thiện và nâng cao chất lượng biên ảnh ................................ 40
2.2 Phép biến đổi Fourier ........................................................................... 49
2.2.1 Định nghĩa ................................................................................ 49
2.2.1 Elliptic Fourier .......................................................................... 50
2.2.3 Biến đổi Fourier rời rạc ............................................................. 55
2.2.4 Các thuộc tính khác của biến đổi Fourier .................................. 61
CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM ..................................................... 62
3.1 Giới thiệu ............................................................................................. 62
3.2 Số hóa biên đối tượng ảnh .................................................................... 62
3.2 Chương trình thử nghiệm ..................................................................... 66
KẾT LUẬN ................................................................................................................. 70
Phạm Ngọc Quý
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
Danh mục các ký hiệu, các chữ viết tắt
CSDL
Cơ sở dữ liệu
FD
(Fourier descriptors) - Mô tả Fourier
Pixel
Điểm ảnh
Radius
Bán kính
RGB
Không gian màu RGB Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình 2.14 So sánh với mức xám trung bình của cửa sổ ảnh trong
trường hợp N=5 .......................................................................................... 36
Hình 2.15 Xác định điểm biên thực sự ....................................................... 37
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iv
Hình 2.16 Ảnh biên kết hợp phương pháp kết hợp với N =5 ...................... 37
Hình 2.17 Ma trận điểm ảnh trước và sau lọc ............................................. 39
Hình 2.18 Các ảnh biên kết quả thu được theo thuật toán đề xuất ............... 39
Hình 2.19 Lấy tổ hợp các điểm ảnh lân cận ................................................ 41
Hình 2.20 Một số kiểu mặt nạ sử dụng cho kỹ thuật lọc phi tuyến.............. 41
Hình 2.21 Minh họa thuật toán hậu xử lý ................................................... 46
Hình 2.22 Ví dụ về chain code ................................................................... 51
Hình 2.23 Minh họa sự kết hợp của chuỗi mã 4, 8-láng giềng ................... 52
Hình 2.24 Minh họa chuỗi mã .................................................................... 54
Hình 2.25 Biển đổi xung mẫu ..................................................................... 57
Hình 2.26 Ảnh dùng biến đổi Fourier rời rạc 2D ........................................ 58
Hình 2.27 (a) Ảnh mặt (b) Biển đổi ảnh mặt .............................................. 60
Hình 2.28 Biến đổi Fourier 2D ................................................................... 61
Hình 3.1 Thuật toán số hóa biên ảnh của đối tượng ảnh ............................. 63
Hình 3.2 Thuật toán chaincodeal ................................................................ 64
Hình 3.3 Lá gấc ban đầu ............................................................................. 66
Hình 3.4 Lá gấc sau khi Histogram ............................................................ 67
Hình 3.5 Lá gấc sau khi chain code ............................................................ 67
Hình 3.6 (a) Lá gấc trước khi được xử lý .................................................... 68
Hình 3.6 (b) Lá gấc sau khi được xử lý ...................................................... 68
đang được quan tâm bởi yêu cầu ứng dụng đa dạng của chúng trong thực tiễn.
Mục đích đặt ra cho xử lý ảnh được chia thành hai phần chính: phần
thứ nhất liên quan đến những khả năng từ các ảnh thu lại các ảnh để rồi từ các
ảnh đã được cải biến nhận được nhiều thông tin để quan sát và đánh giá bằng
mắt, chúng ta coi như là sự biến đổi ảnh (image transformation) hay sự làm
đẹp ảnh (image enhancement). Phần hai nhằm vào nhận dạng hoặc đoán nhận
ảnh một cách tự động, đánh giá nội dung các ảnh.
Quá trình nhận dạng ảnh nhằm phân loại các đối tượng thành các lớp
đối tượng đã biết (supervised learning) hoặc thành những lớp đối tượng chưa
biết (unsupervised learning). Sau quá trình tăng cường và khôi phục (đối với
những ảnh có nhiễu), giai đoạn tiếp theo, người ta phải trích rút các đặc tính
quan trọng, quyết định của ảnh cần nhận dạng. Các đặc tính đó có thể là đặc
tính hình học, đặc tính ngữ cảnh.
Các đặc tính hình học chứa những thông tin về vị trí, kích thước hình
học, hình dạng của các đối tượng trong ảnh, là đặc tính rất quan trọng trong
xử lý nhận dạng ảnh. Các đặc tính này thường được trích rút ra thông qua việc
xác định các đường biên các đối tượng trong ảnh. Biên chứa các thông tin về
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
hình dạng ngoài của đối tượng ảnh. Có thể nói xác định biên là một trong
những vấn đề quan trọng và hấp dẫn trong lĩnh vực nghiên cứu xử lý ảnh bởi
khả năng biểu đạt cấu trúc đối tượng và tính ứng dụng rộng rãi của nó vào
việc giải quyết nhiều bài toán khó như: nhận dạng tự động, thị thực máy tính,
hoạt hình…
Bên cạnh đó, trong những năm gần đây các nghiên cứu về biên ảnh và
phép biến đổi Fourier đã và đang được ứng dụng rộng rãi. Thực tế này đặt ra
giỏc mỏy, l quỏ trỡnh bin i t mt nh ban u sang mt nh mi vi cỏc
c tớnh m tuõn theo ý mun ca vic x lý. X lý nh cú th l quỏ trỡnh
phõn tớch, phõn lp cỏc i tng, lm tng cht lng, phõn on v tỡm
biờn, gỏn nhón cho vựng hay quỏ trỡnh biờn dch cỏc thụng tin hỡnh nh ca
nh. Hỡnh di s minh ha cỏc giai on chớnh trong quỏ trỡnh x lý nh.
Hỡnh 1.1. Cỏc giai on chớnh trong quỏ trỡnh x lý nh
1.1.2. Quỏ trỡnh thu nhn, biu din v lu gi nh
1.1.2.1.Quỏ trỡnh thu nhn nh
nh tn ti trong thc t l mt nh liờn tc c v khụng gian cng nh
v giỏ tr sỏng, v vic thu nhn nh cú th dựng Scanner, camera... Mun
a nh liờn tc trong thc t vo mỏy tớnh x lý cn phi qua mt khõu
trung gian ú l quỏ trỡnh s hoỏ. S hoỏ l quỏ trỡnh ri rc hoỏ v khụng
gian v lng t hoỏ v giỏ tr.Quỏ trỡnh ri rc hoỏ v khụng gian l quỏ
trỡnh thu nhn nhng im ri rc t mt nh liờn tc, nhng phi m bo
bng mt thng khụng phõn bit c hai im k nhau. Quỏ trỡnh ny cng
Hệ
Q.định
L-u
trữ
SENSOR
Số hoá
Trong đó R = Red, G = Green, B = Blue
Hệ toạ độ (R,G,B ) là hệ cơ bản nhất, người ta đã chứng minh được
R,G,B là ba màu độc lập, là một hệ cơ sở. Hầu như các màu khác nhau trong
Black
Blue
Cyan
White
Green
YellowRed
Mag Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Mô hình Raster thuận lợi cho việc thu nhận, hiển thị và in ấn.
Mô hình Vector: Bên cạnh mục đích tiết kiệm không gian lưu trữ, dễ
dàng hiển thị và in ấn, các ảnh biểu diễn theo mô hình vector còn có ưu
điểm cho phép dễ dàng lựa chọn, sao chép, di chuyển, tìm kiếm …
Theo những yêu cầu này thì kỹ thuật biểu diễn vector tỏ ra ưu việt hơn.
Trong mô hình này, người ta sử dụng hướng vector của các điểm ảnh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
lân cận để mã hóa và tái tạo lại hình ảnh ban đầu. Các ảnh vector được
thu nhận trực tiếp từ các thiết bị số hóa như Digitalize hoặc được
chuyển đổi từ các ảnh Raster thông qua các chương trình vector hóa.
Khi xử lý các ảnh Raster chúng ta có thể quan tâm đến mối quan hệ
trong vùng lân cận của các điểm ảnh. Các điểm ảnh có thể xếp hàng trên một
lưới (raster) hình vuông, lưới hình lục giác hoặc theo một cách hoàn toàn
ngẫu nhiên với nhau. Cách sắp xếp theo hình vuông là được quan tâm đến
nhiều nhất và có hai loại: điểm 4 láng giềng (4 liền kề) hoặc 8 láng giềng (8
liền kề). Hình dưới đây minh họa điểm 4 láng giềng và điêm 8 láng giềng.
1.1.2.3. Lưu giữ ảnh
Trong sự phát triển công nghệ thông tin nói chung, một vấn đề lớn chi
với ảnh này ta có histogram của ảnh như hình 1.3.
Từ kết quả histogram của ảnh, chỉ cho ta nhìn nhận tổng quát quá trình
phân bố giải độ sáng trên ảnh, chứ không cho ta biết kết cấu chi tiết của ảnh.
Ngoài ra, căn cứ vào số đỉnh trên histogram của ảnh sẽ có sự nhìn nhận ban
đầu về số vùng của ảnh. Đó là cơ sở cho việc phân vùng ảnh và tìm biên sau
này, đặc biệt là phương pháp tìm biên gián tiếp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
b) c)
Hình 1.3. b) Ảnh gốc; c) Histogram của ảnh gốc theo RGB và Gray
từ máy tính.
Nhận dạng chữ viết tay (với mức độ ràng buộc khác nhau về cách viết,
kiểu chữ, v.v.. ) phục vụ cho nhiều lĩnh vực.
Ngoài hai kỹ thuật nhận dạng trên, hiện nay một số kỹ thuật nhận
dạng mới dựa vào kỹ thuật mạng nơron và fourier đang được áp dụng và
cho kết quả khả quan.
1.2 Biên ảnh và vai trò trong nhận dạng ảnh
1.2.1 Khái niệm về biên ảnh và các phương pháp phát hiện biên
cơ bản
1.2.1.1 Khái niệm biên ảnh
Các phương pháp phát hiện biên là các phương pháp xử lý cục bộ rất
quan trọng trong việc xác định sự thay đổi độ sáng của hàm ảnh.
Một điểm ảnh được coi là biên nếu ở đó có sự thay đổi đột ngột về mức
xám. Tập hợp các điểm biên tạo thành biên hay đường bao của ảnh.
Phương pháp phát hiện biên trực tiếp nhằm làm nổi biên dựa vào sự
biến thiên về độ sáng của điểm ảnh. Sử dụng kỹ thuật đạo hàm để phát
hiện biên. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp
gradient, nếu lấy đạo hàm bậc hai ta có kỹ thuật Laplace.
Một hàm ảnh phụ thuộc vào 2 biến đó là toạ độ của điểm ảnh, vì vậy
các toán tử mô tả biên ảnh được biểu diễn bởi các đạo hàm riêng (theo
2 hướng x,y).
Phương pháp gradient là phương pháp dò biên cục bộ dựa vào cực đại
của đạo hàm.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
Biên ảnh được biểu diễn bởi 1 véc tơ với 2 thành phần:
1.2.1.2 Các 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 theo hướng. Nếu lấy đạo hàm bậc nhất của ảnh ta có kỹ
thuật Gradient, nếu lấy đạo hàm bậc hai của ảnh 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.
1.2.1.2.1. Phương pháp phát hiện biên trực tiếp
a) Kỹ thuật phát hiện biên Gradient
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.
b) Kỹ thuật phát hiện biên Laplace
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
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.
1.2.1.2.2. Phương pháp phát hiện biên gián tiếp
a) Một số khái niệm cơ bản
P
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
Định nghĩa 2: [Chu tuyến đối ngẫu]
Hai chu tuyến C= <P
1
P
2
..Pn> và C
= <Q
1
Q
2
..Qm> được gọi là đối ngẫu
của nhau nếu và chỉ nếu i j sao cho:
1. Pi và Qj là 4-láng giềng của nhau.
2. Các điểm Pi là vùng thì Qj là nền và ngược lại.
Định nghĩa 3: [Chu tuyến ngoài]
Chu tuyến C được gọi là chu tuyến ngoài nếu và chỉ nếu:
1. Chu tuyến đối ngẫu C
là chu tuyến của các điểm nền
2. Độ dài của C nhỏ hơn độ dài C
mẫu) và tập các phần tử mẫu được chia thành các lớp.
Giai đoạn nhận dạng: Khi có đối tượng cần nhận dạng, các đặc điểm của đối
tượng sẽ được trích chọn và sử dụng hàm quyết định để xác định đối tượng
cần nhận dạng thuộc lớp nào.
1.2.3 Biểu diễn biên dựa trên mô tả Fourier
Hình dạng mà một đặc trưng trực quan quan trọng và nó là một trong
những đặc trưng gốc của việc mô tả nội dung ảnh. Tuy nhiên, mô tả nội dung
hình dạng là một công việc khó. Bởi vì khó xác định được các đặc trưng hình
dạng và phép đo sự tương tự giữa các hình dạng. Để tạo vấn đề phức tạp hơn,
hình dạng thường không rõ ràng cùng với các nhiễu không rõ ràng.
Trong phần này mục tiêu chính nghiên cứu về hình dạng để nhận dạng
đối tượng. Mỗi một kỹ thuật biểu diễn hình dạng nhằm vào các ứng dụng
riêng biệt. Sự chính xác là mối quan tâm chính trong các kỹ thuật biểu diễn.
Các yêu cầu được đưa ra để đo hiệu quả biểu diễn hình dạng gồm: truy vấn
chính xác, các đặc trưng cô đọng, ứng dụng tổng quát, độ phức tạp tính toán
thấp, thao tác truy vấn đơn giản.
Biểu diễn biên dựa trên mô tả Fourier: là mô tả hình dạng của đối tượng ảnh
bằng một biến đổi Fourier của đường biên của đối tượng.
Ba loại biểu diễn đường biên: bằng độ cong, bằng khoảng cách trọng tâm,
bằng hàm toạ độ phức. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
Phương pháp chung nhất và tổng quát nhất là dựa trên việc sử dụng
điểm nằm trên đường bao hình dạng trái ngược với các điểm bên trong hình
dạng. Các kỹ thuật biểu diễn hình dạng có thể nhận ra giữa vùng không gian
1.2.3.1 Phƣơng pháp dựa trên mô tả Fourier
Năm 1977, Persoon và Fu lần đầu tiên đã đưa ra kỹ thuật sử dụng ký
hiệu mô tả Fourier để biểu diễn hình dạng. Rất nhiều nghiên cứu đã được thực
hiện theo sau ý tưởng này. Trong số đó, Refiei và Mendlzon đã đưa ra phương
pháp biểu diễn hình dạng của họ sử dụng các dấu hiệu mô tả Fourier để mô tả
hình dạng của một đối tượng.
Giả sử biên hình dạng được trích chọn trong quá trình tiền xử lý là:
( ( ), ( )), 0,1,..., 1x t y t t N
.
Copyright: Tài liệu đại học ©