Luận văn Phát hiện biên, biểu diễn Fourier Elliptic và ứng dụng
ĐẠ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
`
Thái Nguyên - 2009
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
Chuyên ngành: Khoa học máy tính
Mã số:
604801
`
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Ngƣời hƣớng dẫn khoa học: TS. Phạm Việt Bình
Thái Nguyên - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Ngu
i
MỤC LỤC
Lời cảm ơn.................................................................................................... i
Danh mục các ký hiệu, các chữ viết tắt.........................................................ii
Danh mục các hình......................................................................................iii
MỞ ĐẦU ..................................................................................................... 1
CHƢƠNG 1. TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN ..................................... 3
1.1. Một số khái niệm cơ bản trong xử lý ảnh............................................... 3
1.1.1. Xử lý ảnh. .................................................................................. 3
1.1.2 Quá trình thu nhận, biểu diễn và lưu giữ ảnh............................... 3
1.1.3 Histogram của ảnh ...................................................................... 7
1.1.4 Nhận dạng ảnh ............................................................................ 8
1.2 Biên ảnh và vai trò trong nhận dạng ảnh................................................. 9
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
i
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
TÀI LIỆU THAM KHẢO ............................................................................................ 72
Tiếng Việt .................................................................................................. 72
Tiếng Anh .................................................................................................. 72
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
LỜI CẢM ƠN
Trong quá trình làm luận văn thạc sĩ với đề tài “Phát hiện biên, biểu
diễn Fourier Elliptic và ứng dụng”, em đã nhận được nhiều đóng góp và
tạo điều kiện của các thầy cô và đồng nghiệp. Lời đầu tiên em xin chân thành
cảm ơn tới toàn thể các thầy cô, những người đã giảng dạy em.
Đặc biệt, em xin tỏ lòng cảm ơn chân thành và sâu sắc tới thầy thầy
Phạm Việt Bình, người đã luôn tận tình hướng dẫn, định hướng, và có những
chỉ bảo cặn kẽ em trong thời suốt thời gian qua.
Em rất cảm ơn các bạn, các đồng nghiệp đã động viên, khích lệ, cũng
như trao đổi tài liệu cho em trong thời gian làm luận văn.
Em cũng chân thành mong được sự đóng góp ý kiến của các thầy, các cô
và các đồng nghiệp để em có phát triển đề tài trong thời gian tới.
Xin chân thành cảm ơn !
Thái Nguyên, ngày 12 tháng 11 năm 2009
Học viên
Phạm Ngọc Quý
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
Danh mục các ký hiệu, các chữ viết tắt
CSDL
FD
Cơ sở dữ liệu
(Fourier descriptors) - Mô tả Fourier
Điểm ảnh
Pixel
Radius
RGB
Bán kính
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
ii
Danh mục các hình
Hình 1.1 Các giai đoạn chính trong quá trình xử lý ảnh................................ 3
Hình 1.2 Điểm 8 láng giềng và điểm 4 láng giềng........................................ 6
Hình 1.3(a) Đồ thị biểu diễn Histogram ảnh................................................. 8
Hình 1.3(b) Ảnh gốc..................................................................................... 8
Hình 1.3(c) Histogram của ảnh gốc theo RGB và Gray ................................ 8
Hình 1.4 Ví dụ chu tuyến của đối tượng ảnh .............................................. 12
Hình 1.5 Phân loại biểu diễn hình dạng và các kỹ thuật biểu diễn .............. 15
Hình 1.6 Biểu diễn góc quay ...................................................................... 20
Hình 1.7 Biểu diễn góc quay trong trường hợp có thay đổi nhỏ.................. 21
Hình 2.1 Mô hình 8 hướng ......................................................................... 23
Hình 2.2 Ảnh trước khi dò biên.................................................................. 24
Hình 2.3 Ảnh sau khi dò biên..................................................................... 25
Hình 2.4 (a) Ảnh gốc (b) Đạo hàm bậc nhất (c) Đạo hàm bậc hai............... 25
Hình 2.5(a) Ảnh gốc (b) Ảnh biên dùng Laplace H1 (a) Ảnh biên H2 ......... 27
Hình 2.6 Minh họa biểu diễn biên nhờ các phép hình thái .......................... 30
Hình 2.7 Ảnh gốc ....................................................................................... 33
Hình 2.8 Ảnh đen trắng .............................................................................. 33
Hình 2.9 Ảnh đen trắng dùng hàm ConvertRGB ........................................ 34
Hình 2.10 Ảnh đen trắng ............................................................................ 34
Hình 2.11 Biên của ảnh đen trắng............................................................... 35
Hình 2.12 Ảnh gốc ..................................................................................... 36
Hình 2.13 Ảnh biên với cách đánh giá độ chênh lệch mức xám của
điểm ảnh..................................................................................................... 36
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
iii
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iv
PHẦN MỞ ĐẦU
Xử lý ảnh là một lĩnh vực đã và đang được quan tâm của nhiều nhà khoa
học trong và ngoài nước bởi tính phong phú và lợi ích của nó được ứng dụng
trong khoa học kỹ thuật, kinh tế, xã hội và đời sống con người. Lĩnh vực xử lý
ảnh liên quan tới nhiều ngành khác như: hệ thống tin học, trí tuệ nhân tạo,
nhận dạng, viễn thám, y học, nông học...
Hiện nay, thông tin hình ảnh đóng vai trò rất quan trọng trong trao đổi
thông tin, bởi phần lớn thông tin mà con người thu được thông qua thị giác.
Do vậy, vấn đề nhận dạng trong xử lý ảnh, đặc biệt là nhận dạng biên ảnh
đ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
1
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
các bài toán như: đưa những ứng dụng đó vào xã hội và đời sống con người.
Một số nhóm nghiên cứu trong và ngoài nước đã đưa ra các phương pháp giải
quyết kết hợp các phương pháp phát hiện biên và phép biến đổi Fourier để
hoàn thành những ứng dụng góp phần vào sự phát triển trong xã hội.
Chình vì những ứng dụng thực tiễn đó em đã nghiên cứu luận văn thạc
sĩ với đề tài “Phát hiện biên, biểu diễn Forier Elliptic và ứng dụng”. Luận văn
gồm phần mở đầu, phần kết luận, và 3 chương nội dung:
Chương 1: Tổng quan về xử lý ảnh và biên.
Chương 2: Một số phương pháp phát hiện biên và phép biểu diễn
Fourier Elliptic.
Chương 3: Chương trình thử nghiệm.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN
1.1. Một số khái niệm cơ bản trong xử lý ảnh
1.1.1. Xử lý ảnh
Xử lý ảnh(Image processing) là đối tượng nghiên cứu của lĩnh vực thị
giác máy, là quá trình biến đổi từ một ảnh ban đầu sang một ảnh mới với các
đặc tính mà tuân theo ý muốn của việc xử lý. Xử lý ảnh có thể là quá trình
phân tích, phân lớp các đối tượng, làm tăng chất lượng, phân đoạn và tìm
biên, gán nhãn cho vùng hay quá trình biên dịch các thông tin hình ảnh của
ảnh. Hình dưới sẽ minh họa các giai đoạn chính trong quá trình xử lý ảnh.
L u
tr÷
camera
Ph©n tÝch
Thu nhËn
¶nh
Sè ho¸
NhËn
d¹ng
¶nh
SENSOR
HÖ
Q.®Þnh
L u
tr÷
Hình 1.1. Các giai đoạn chính trong quá trình xử lý ảnh
1.1.2. Quá trình thu nhận, biểu diễn và lƣu giữ ảnh
1.1.2.1.Quá trình thu nhận ảnh
Ảnh tồn tại trong thực tế là một ảnh liên tục cả về không gian cũng như
về giá trị độ sáng, và việc thu nhận ảnh có thể dùng Scanner, camera... Muốn
đưa ảnh liên tục trong thực tế vào máy tính để xử lý cần phải qua một khâu
trung gian đó là quá trình số hoá. Số hoá là quá trình rời rạc hoá về không
gian và lượng tử hoá về giá trị.Quá trình rời rạc hoá về không gian là quá
trình thu nhận những điểm rời rạc từ một ảnh liên tục, nhưng phải đảm bảo
bằng mắt thường không phân biệt được hai điểm kề nhau. Quá trình này cũng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
chính là việc tìm cách biểu diễn cả một ảnh lớn có vô số điểm, bởi một số hữu
hạn điểm, sao cho không làm mất đi hay thay đổi tính chất của ảnh, để việc
lưu trữ và xử lý ảnh được dễ dàng. Còn quá trình lượng tử hoá về giá trị là
quá trình rời rạc hoá về mặt giá trị để có thể đơn giản hoá việc tính toán và
đưa vào máy để xử lý. Tuỳ theo từng loại ảnh, độ chính xác yêu cầu và khả
năng xử lý của máy tính mà ta có các mức lượng tử thích hợp. Ví dụ với ảnh
256 cấp xám, ta phải dùng 256 mức lượng tử và biểu diễn trong máy tính
bằng 8 bits.
1.1.2.2. Quá trình biểu diễn ảnh
Sau quá trình số hoá sẽ thu được một ma trận tương ứng với ảnh cần xét,
mỗi phần tử của ma trận tương ứng với một điểm ảnh. Ảnh thường được biểu
diễn bởi một mảng hai chiều I(n,p) gồm n dòng và p cột. Như vậy, ảnh gồm
nxp pixels và người ta thường kí hiệu I(x,y) để chỉ một pixel cụ thể trong ảnh.
Các điểm này được đặc trưng bằng toạ độ màu (R,G,B) tương ứng với nó trên
hệ toạ độ màu cơ bản sau:
Blue
Cyan
Mag
White
Black
Green
Yellow
Red
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
thực tế đều có thể biểu diễn bởi toạ độ của chúng trong hệ toạ độ này, tức là
từ ba màu này chúng ta có thể tổng hợp được nhiều màu trong thực tế. Xét
một số trường hợp đặc biệt sau:
Màu đen (Black) tạo bởi R=B=G=0
Màu vàng (Yellow) tạo bởi R=G=1, B=0
Màu tím (Magenta) tạo bởi R=B=1, G=0
Màu xanh (Cyan) tạo bởi R=0, G=B=1
Màu trắng (White) tạo bởi R=G=B=1
Từ đó ta có thể thấy rằng, ảnh đa cấp sáng là trường hợp đặc biệt của ảnh
màu, trong đó các thành phần tọa độ màu tương ứng bằng nhau (R=G=B=1).
Về mặt toán học có thể xem ảnh là một hàm hai biến f(x,y) với x,y là các
biến tọa độ. Giá trị số ở điểm (x,y) tương ứng với giá trị xám hoặc độ sáng
của ảnh (x là các cột còn y là các hàng). Giá trị của hàm ảnh f(x,y) được hạn
chế trong phạm vi của các số nguyên dương.
0 = f(x,y) = fmax
Thông thường đối với ảnh xám, giá trị fmax là 255 ( 28=256) và mỗi phần
tử ảnh được mã hóa bởi một byte. Ảnh có thể được biểu diễn theo một trong
hai mô hình: mô hình Vector hoặc mô hình Raster.
Mô hình Raster: là mô hình 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 ảnh. Tùy theo nhu cầu
thực tế mà mỗi điểm ảnh có thể được biểu diễn bởi một hay nhiều bit.
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
5
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.
H×nh 1.2 : §iÓm 8 l¸ng giÒng vµ ®iÓm 4 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
phối các hoạt động thuộc lĩnh vực này là vấn đề bộ nhớ. Cần thiết phát triển
quá trình xử lý thông tin sao cho nhanh chóng và chính xác, song cũng cần
phát triển khả năng lưu trữ, bảo toàn các thông tin này. Các thế hệ máy tính
ngày nay đã có bộ nhớ rất lớn, song bao giờ nó cũng ít đối với những gì
chúng ta muốn lưu trữ và xử lý. Trong kĩ thuật xử lý ảnh cũng vậy, vì lượng
thông tin chứa trong một bức ảnh là khá lớn, lên việc lưu giữ nó là vấn đề cần
quan tâm. Trong thực tế ma trận điểm ảnh tạo ra bởi quá trình số hoá, được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
lưu trữ trong máy tính dưới dạnh các files và thường thì các files này được
nén để tiết kiệm bộ nhớ .
Hầu hết các files ảnh đều có phần đề ở đầu files để ghi những thông tin
cơ bản về ảnh như: Kích thước ảnh, số planes, số bits cho một điểm ảnh ...
Trong thực tế, ta hay gặp và xử lý đầu vào là các ảnh bitmap đó là ảnh được
tạo ra từ các điểm ảnh. Ngoài ra trong quá trình thực hiện, sau một số phép
biến đổi có thể chuyển nó về dạng vectơ có đơn vị là các đường để tiện cho
việc lưu giữ.
1.1.3. Histogram của ảnh
Như ta đã biết, mỗi điểm có một giá trị độ sáng nào đó. Histogram của
ảnh là đồ thị cho biết tần suất hiện các điểm ảnh với các mức biến thiên
độ sáng.
Thí dụ: Có một ảnh 100 điểm , độ sáng của ảnh được phân thành 5 mức
sáng: level1, level2,..., level 5.
Số điểm ảnh của các mức tương ứng là 20, 25, 10, 30, 15. Như vậy tần
suất hiện của các điểm ảnh ở mức tương ứng là 20%, 25%, 10%, 30%, 15%,
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
7
30%
25%
20%
15%
10%
H×nh 1.3a Đå thÞ biÓu diÔn Histogram ¶nh
b)
c)
Hình 1.3. b) Ảnh gốc;
c) Histogram của ảnh gốc theo RGB và Gray
1.1.4. Nhận dạng ảnh
Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tượng mà
người ta muốn đặc tả nó. Quá trình nhận dạng thường đi sau quá trình trích
chọn các đặc tính chủ yếu của đối tượng. Có hai kiểu mô tả đối tượng:
- Mô tả tham số (nhận dạng theo tham số).
- Mô tả theo cấu trúc ( nhận dạng theo cấu trúc).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
Trên thực tế, người ta đã áp dụng kỹ thuật nhận dạng khá thành công
với nhiều đối tượng khác nhau như: nhận dạng ảnh vân tay, nhận dạng chữ
(chữ cái, chữ số, chữ có dấu).
Nhận dạng chữ in hoặc đánh máy phục vụ cho việc tự động hoá quá
trình đọc tài liệu, tăng nhanh tốc độ và chất lượng thu nhận thông tin
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
9
Biên ảnh được biểu diễn bởi 1 véc tơ với 2 thành phần:
o Biên độ của gradient
o Và hướng của biên với góc , hướng của biên lệch so với hướng
của gradient một góc -900
Hướng gradient là hướng của sự gia tăng lớn nhất của hàm ảnh.
Như mô tả trong hình dưới, các đường biên khép kín là các đường có
cùng độ sáng; quy ước hướng
là chỉ hướng đông.
Biên thường được sử dụng trong phân tích ảnh để xác định đường bao
của các vùng trong ảnh.
Đường bao và các thành phần của nó (các điểm biên) vuông góc với
hướng của gradient
Một số dạng của đường bao ảnh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
Roof là dạng điển hình cho các đối tượng có đường biên mảnh.
Các kỹ thuật phát hiện biên thường được điều chỉnh để phù hợp với
dạng của biên ảnh.
Đôi khi chúng ta chỉ chú ý đến sự thay đổi biên độ mà không quan tâm
đến sự thay đổi về hướng; khi đó chúng ta sử dụng toán tử tuyến tính
Laplace để phát hện biên.
Toán tử Laplace có cùng tính chất ở mọi hướng, và do đó nó là thành
phần bất biến quay trong các ảnh.
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
11
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
*Ảnh và điểm ảnh:
Ảnh là một mảng số thực 2 chiều (Iij) có kích thước (mn), 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.
*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 và 8 láng giềng là: N4= {(i’,j’) : |i-
i’|+|j-j’| = 1}, N8 = {(i’,j’) : max(|i-i’|,|j-j’|) =1}.
b) Chu tuyến của một đối tượng ảnh
Định nghĩa 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
<P1P2..Pn>.Hình 1.4 biểu diễn chu tuyến của ảnh, P là điểm khởi đầu
chu tuyến.
P
Hình 1.4 Ví dụ về chu tuyến của đối tượng ảnh
Định nghĩa 2: [Chu tuyến đối ngẫu]
Hai chu tuyến C= <P1P2..Pn> và C= <Q1Q2..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
Định nghĩa 4: [Chu tuyến trong]
Chu tuyến C được gọi là chu tuyến trong 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 lớn hơn độ dài C
c) Thuật toán dò biên tổng quát
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
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
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
1.2.2. Vai trò của biên trong nhận dạng
Như đã đề cập tới ở phần tổng quan về một hệ thống nhận dạng và xử lý
ảnh, quá trình nhận dạng có hai giai đoạn cần thực hiện:
Giai đoạn học: Các đặc điểm của đối tượng mẫu được lưu trữ (gọi là họ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
14
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
và vùng đặc trưng. Các phương pháp trong vùng không gian tương xứng với
hình dạng trên các điểm cơ sở (hoặc đặc trưng điểm), trong khi kỹ thuật vùng
đặc trưng tương xứng với hình dạng trên các đặc trưng cơ sở (véc tơ). Sự
phân loại khác của các kỹ thuật biểu diễn hình dạng được dựa trên sự bảo toàn
thông tin gốc. Các phương pháp cho phép xây dựng lại hình dạng từ các mô tả
gọi là bảo toàn thông tin, trong khi các phương pháp khác chỉ có thể xây dựng
lại một phần hoặc mô tả không rõ ràng gọi là không bảo toàn thông tin.
Hình 1.5 Phân loại biểu diễn hình dạng và các kỹ thuật biểu diễn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
Một khi đối tượng trong ảnh đã được xác định, chúng sẽ được đặc
trưng hóa thông qua các phương pháp như: miền, độ lệch tâm - eccentricity
(chẳng hạn như tỷ lệ giữa trục chính và trục phụ), vòng tròn - circularity (sự
tương đồng với vòng tròn bao quanh vùng có kích thước tương tự), dấu hiệu
hình dạng (một dãy các số chỉ khoảng cách từ biên tới tâm của hình dạng), mô
men hình dạng (shape moments), sự uốn cong - curvature (xác định mức độ
đường biên đổi hướng), chiều fractal – fractal dimension (mức độ tự tương
tự), .v.v.
Một số tiêu chuẩn biểu diễn hình dạng:
Bất biến đối với phép quay, co giãn và tịnh tiến.
Nhỏ gọn, dễ thao tác.
Tương tự với cảm nhận của con người.
Bền vững với phép biến đổi hình dạng.
Độc lập với các ứng dụng.
Sau đây sẽ trình bày một số phương pháp biểu diễn hình dạng
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à:
.
(x(t), y(t)), t 0,1,..., N 1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
Nếu ta xem xét hình dạng trên một mặt phẳng phức, ta có thể thu được
hàm phức một chiều bằng cách lần theo biên của nó. đơn giản là
f (t)
f (t)
một số phức được tổng quát hóa từ hệ tọa độ đường bao.
f (t)
x(t) xc
j
y(t) yc
xc , yc
Với
là trọng tâm của hình dạng, được tính theo công thức sau:
N1
N 1
1
1
xc
x(t)
,
yc
y(t)
N
N
t0
t0
miêu tả đường bao của hình dạng,
là dấu hiệu hình dạng bất
f (t)
f (t)
biến đối với phép dịch chuyển.
Biến đổi Fourier rời rạc của dấu hiệu hình dạng
được cho bởi:
f (t)
N 1
1
j2ut
F
f (t).exp
N
t0
u
N
với u=0 đến M-1, trong đó M là tổng số mẫu f(t).
Có nhiều loại dấu hiệu hình dạng. Các loại dấu hiệu hình dạng hay sử
dụng là trên cơ sở độ cong, trên cơ sở bán kính và trên cơ sở tọa độ biên hình
dạng. Hiệu năng phân lớp hình dạng trên cơ sở ba loại dấu hiệu này không
khác nhau nhiều. Dấu hiệu trên cơ sở bán kính là đơn giản và dễ cài đặt nhất.
Dấu hiệu trên cơ sở bán kính bao gồm một số khoảng cách theo thứ tự
từ tâm hình dạng đến các điểm trên biên (gọi là radius - các bán kính). Radius
được định nghĩa như sau:
r (xc xi )2 (yc yi )2
i
(xc , yc )
(xi , yi )
với i=0 đến 63 là tọa độ của
trong đó,
là tọa độ tâm hình dạng,
64 điểm mẫu theo biên hình dạng. Các điểm biên được lấy mẫu sao cho tổng
số điểm ảnh theo biên giữa hai điểm láng giềng là như nhau.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
Radius hình dạng và biến đổi giữa chúng là bất biến dịch chuyển. Chú
ý rằng các hình dạng không chuẩn hóa hướng trước khi sử dụng radius hình
dạng. Thực hiện chuẩn hóa bằng cách bỏ qua các giá trị pha của Fourier (FD).
Xoay hình dạng được phản ánh trong thông tin pha của Fu và độ lớn của Fu
,
hay | F | là bất biến với xoay. | F | phản ánh năng lượng của radius hình dạng,
u
0
vậy | F | / | F | sẽ bất biến co dãn. Do vậy, ta sử dụng véc tơ đặc trưng sau (nó
u
o
bất biến với dịch chuyển, xoay, và co dãn) để chỉ mục hình dạng:
F
F63
F0
1
x
,...,
F
0
Khoảng cách giữa các hình dạng được tính toán bằng khoảng cách
Euclidean giữa các véc tơ đặc trưng của chúng.
Chỉ mục mỗi hình dạng trong CSDL cùng với mô tả Fourier. Sự tương
tự giữa hai hình dạng truy vấn và mỗi hình dạng trong CSDL với
fq ( fq1, fq2 ,..., fqm ) và
lần lượt là các véc tơ đặc trưng của hai
ft ( ft1, ft2,..., ftm )
hình dạng.
m
d ( ( f q f t )2 )1
2
i
i
i1
Tại sao ta sử dụng FD để chỉ mục hình dạng thay cho trực tiếp radius?
Lý do chính là biểu diễn trực tiếp là rất nhạy với thay đổi nhỏ và nhiễu, dẫn
tới hiệu năng truy tìm rất thấp. Nếu 64 độ dài bán kính sử dụng trực tiếp làm
chỉ mục, có thể sẽ rất khó co dãn và chuẩn hóa xoay. Có thể thực hiện chuẩn
hóa xoay bằng nhận ra bán kính ngắn nhất (hay dài nhất) và thực hiện chuẩn
hóa co dãn bằng cố định độ dài của bán kính ngắn nhất. Nhưng chuẩn hóa này
không ổn định vì với thay đổi nhỏ trên đường biên sẽ ảnh hưởng đến vị trí bán
kính nhỏ nhất và các vị trí của điểm mẫu, dẫn tới chỉ mục rất khác nhau và
khoảng cách rất lớn giữa các hình dạng do thay đổi nhỏ. Mục tiêu sử dụng FD
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
là chuyển đổi độ dài bán kính nhạy cảm vào miền tần số nơi dữ liệu bền vững
hơn đối với thay đổi nhỏ và nhiễu.
1.2.3.2 Phƣơng pháp góc quay
Arkin và các đồng nghiệp đề xuất một phương pháp hiệu quả để biểu
diễn các hình đa giác gọi là phương pháp góc quay. Tổng quát, phương pháp
biểu diễn một hình đa giác A đơn giản sẽ mô tả biên của A bằng cách liệt kê
dãy các đỉnh (vertex) trong đó mối đỉnh được mô tả bởi cặp tọa độ (x,y). Tuy
nhiên, Arkin đưa ra một cách biểu diễn khác cho biên của một hình đa giác.
Theo phương pháp của ông, biên có thể được mô tả bởi hàm quay A
đo góc của tiếp tuyến của cung (arc-length) theo chiều ngược chiều
quay đồng hồ. Cung S được tính từ điểm tham chiếu bắt đầu O trên biên của
đa giác. Khi đó A là góc tạo bởi tiếp tuyến tại O và trục tham chiếu nào
đó, chẳng hạn là trục x. Theo cách này, hàm quay A sẽ đi dọc theo biên,
S
. Hàm
A
S
O
S
tăng khi quay sang bên trái và giảm khi quay sang bên phải.
Không mất tính tổng quát, Arkin giả thiết rằng mọi đa giác được thay
đổi kích thước hay chuẩn hóa sao cho chu vi của nó bằng 1. Khi đó A
S
là
quay của một đa giác.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
Hình 1.6 Biểu diễn theo góc quay
di chuyển ngược chiều quay đồng hồ dọc theo biên của đa giác. Chú ý rằng
với đa giác lồi A, hàm quay của nó A
S
sẽ tăng đơn điệu từ v đến
.
v2
Cho trước hai đa giác A và B với các hàm quay tương ứng là A
S
và
B
S
, sự khác biệt giữa chúng được định nghĩa là:
D(A, B) minr, (
( (i) (i))2 )
A
B
i
trong đó, minr, đại diện cho giá trị nhỏ nhất của mọi trường hợp dịch
chuyển và xoay của đa giác B.
Việc biểu diễn hình dạng này là bất biến với việc dịch chuyển, thay đổi
kích thước và việc xoay. Mặc dù cách biểu diễn này có nhiều ưu điểm, nó vẫn
nhạy cảm với các thay đổi nhỏ của hình ảnh. Điều này được mô tả trong Hình.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Tải về để xem bản đầy đủ
83 trang
15/06/2025
490
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Phát hiện biên, biểu diễn Fourier Elliptic và ứng dụng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_phat_hien_bien_bieu_dien_fourier_elliptic_va_ung_du.pdf
