I
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
VŨ VÂN DU
NGHIÊN CỨU PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC
TRƢNG ẢNH DỰA TRÊN ĐỐI SÁNH HÌNH DẠNG VÀ
ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên, tháng 5 năm 2014
Tác giả
Vũ Vân Du
III
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
LỜI CAM ĐOAN Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung
thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan là
cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận
văn đã được chỉ rõ nguồn gốc.
Thái Nguyên, tháng 5 năm 2014
Tác giả Vũ Vân Du IV
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
MỤC LỤC
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
2.3.1. Kỹ thuật dò biên gián tiếp đơn giản 29
2.3.2. Kỹ thuật dò biên gián tiếp bằng cách xác định chu tuyến 30
2.4. Xử lý ảnh trong miền tần số và biến đổi Fourier 31
2.4.1. Biến đổi Fourier rời rạc (DFT) 34
2.4.2. Biến đổi Fourier nhanh (FFT) 34
2.5. Mô tả Fourier 35
2.6. Các bất biến moment 37
2.7. Các hàm xoay/góc xoay 37
2.8. Độ tròn, độ lệch tâm và hướng trục chính 38
CHƢƠNG 3: ỨNG DỤNG TRÊN BÀI TOÁN TRA CỨU BIỂN BÁO GIAO
THÔNG 40
3.1. Bài toán tra cứu biển báo giao thông 40
3.2. Phân tích bài toán 41
3.3. Xây dựng chương trình đối sánh biển báo giao thông 45
3.3.1. Sơ đồ khối 45
3.3.2. Đọc ảnh 46
3.3.3. Dò biên đối tượng ảnh 46
3.3.4. Resample 46
3.3.5. Biến đổi Fourier nhanh 47
3.3.6. Tạo véc tơ đặc trưng hình dạng cho ảnh 47
3.3.7. So sánh ảnh bằng cách tính khoảng cách Euclide 48
3.5. Đánh giá chương trình 50
3.5.1. Kết quả đạt được 50
3.5.2. Hạn chế 50
3.5.3. Khả năng mở rộng 50
KẾT LUẬN 51
TÀI LIỆU THAM KHẢO 53
Hình 3.2: Sơ đồ khối phần tra cứu ảnh theo hình dạng 45
Hình 3.3: Một số kết quả chạy thử chương trình 49
VII
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1: Một số phần mềm tự động chấm bài thi trắc nghiệm 6
Bảng 2.1: So sánh đặc trưng và phương pháp khử nhiễu của hai loại nhiễu 10
Bảng 3.1: Một số loại biển báo giao thông ở Việt Nam 42
Bảng 3.2: Hình dạng đặc trưng của một số loại biển báo 43 VIII
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
DANH MỤC CÁC THUẬT NGỮ
Ảnh màu : Color Image
Ảnh số : Digial Image
Ảnh tương tự : Analog Image
Ảnh xám : Gray Image
Ảnh nhị phân : Binary Image
Ảnh cắt lớp vi tính : Computed Tomography (CT)
Biển báo giao thông : Traffic sign (Road sign)
Biến đổi Fourier nhanh : Fast Fourier Transform (FFT)
Biến đổi Fourier rời rạc : Discrete Fourier Transform (DFT)
Bộ số hoá : Digitalizer
PHẦN MỞ ĐẨU
Công nghệ Thông tin ngày càng phát triển và có vai trò hết sức quan trọng
không thể thiếu trong cuộc sống hiện đại. Con người ngày càng tạo ra những cỗ máy
thông minh có khả năng tự nhận biết và xử lý được các công việc một cách tự động,
phục vụ cho lợi ích của con người.
Trong những năm gần đây, một trong những bài toán nhận được nhiều sự quan
tâm của lĩnh vực công nghệ thông tin, đó chính là thị giác máy tính. Nó đã được các
nhà nghiên cứu quan tâm vì tính ứng dụng cao của bài toán cũng như sự phức tạp của
nó.
Bài toán nhận dạng là một phần quan trọng của thị giác máy tính. Nó được sử
dụng trong rất nhiều lĩnh vực như: nhận dạng con người, đồ vật, chữ viết, cử chỉ…
trong các lĩnh vực đó thì đều có những nhu cầu từ thực tiễn và tính ứng dụng lớn.
Trong nhận dạng ảnh, thường dùng các phương pháp trích chọn đặc trưng để đối sánh.
Một số phương pháp thường dùng như: trích chọn đặc trưng theo màu sắc, theo kết cấu
và theo hình dạng của ảnh.
Hiện tại, thị giác máy tính ứng dụng trong khá nhiều lĩnh vực như: y khoa, quân
sự, các lĩnh vực quản lý v.v… Trong lĩnh vực thông tin giao thông với 200 loại biển
báo thì việc nghi nhớ nội dung biển báo là một trở ngại lớn đối với người tham gia
giao thông. Vì vậy việc xây dựng một chương trình có thể nhận dạng và đưa ra các
thông tin cũng như cảnh báo đến người dùng là cần thiết.
Trong khuân khổ luận văn thạc sỹ tôi chọn để tài: “Nghiên cứu phƣơng pháp
trích chọn đặc trƣng ảnh dựa trên đối sánh hình dạng và ứng dụng” nhằm tìm
hiểu kỹ về các kỹ thuật trích chọn đặc trưng hình dạng của ảnh, hiểu rõ hơn bản chất
của bài toán tìm kiếm ảnh theo hình dạng từ đó áp dụng vào bài toán tra cứu biển báo
giao thông. 2
Hình 1.1: Mô phỏng hệ thống thị giác của con người (nguồn: bionicvision.org.au)
Mặc dù thị giác máy tính và thị giác con người có chức năng tương tự, nhưng
khó có thể chế tạo một hệ thống thị giác máy tính có thể tái tạo chính xác chức năng
của thị giác người. Điều này phần lớn là do máy tính chưa mô phỏng được tâm lý học
thị giác.
Thu nhận ảnh
Xử lý ảnh
Kết quả
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
Hình 1.2: Mô phỏng hệ thống thị giác máy tính
Thị giác máy tính là một chủ đề phong phú và bổ ích cho học tập và nghiên cứu của
các kỹ sư điện tử, khoa học máy tính và nhiều nhóm ngành khác. Trong thương mại,
thị giác máy tính ngày càng có một tương lai rộng mở. Và xử lý ảnh là một trong
những phần quan trọng trong thị giác máy tính.
1.1.2. Mối liên quan giữa thị giác máy tính và xử lý ảnh
Thị giác máy tính là một khái niệm mở bao trùm nhiều khái niệm khác nhau từ
phần cứng (máy ảnh, máy tính, bộ phận hiển thị, chấp hành…) đến các phần mềm (xử
lý, tổng hợp, điều khiển…) và xử lý ảnh là một trong những khâu quan trọng nhất của
thị giác máy tính.
1.1.3. Tầm quan trọng của thị giác máy tính
Là một trong năm giác quan của con người, thị giác là nơi tiếp nhận phần lớn
lượng thông tin tác động đến con người hàng ngày. Có thể nói, thị giác là giác quan
quan trọng nhất là có cơ sở khi có tới gần 25% nơ-ron thần kinh dùng để tiếp nhận và
xử lý các thông tin về hình ảnh.
Trong khi đó, trải qua một thời gian dài máy tính tiếp nhận dữ liệu bằng các thao
tác từ những đầu thu nhận. Giờ đây, nhu cầu đặt ra cho hệ thống xử lý dữ liệu cần xử
2
TestPro
Công ty TMSoft
3
SuperEMR
Công ty PSC
4
MR.Test
TT Nghiên cứu và Phát triển Công nghệ Phần mềm – ĐH
Công nghệ - ĐHQG HN
Ngoài các ứng dụng trong nước dành cho ngành giáo dục thì cũng có một số
các nghiên cứu ứng dụng xử lý ảnh áp dụng cho các ngành khác như y tế ví dụ như
một số chương trình do Bộ môn Vật lý Kỹ thuật y sinh, Trường Đại Học Bách Khoa –
Đại học Quốc gia Thành phố Hồ Chí Minh thực hiện:
BKDoctor: Chương trình tái tạo ảnh 3D từ các lớp cắt song song
IBK: Chương trình xử lý ảnh y khoa trên nền MATLAB
sgDICOM-J: Chương trình xử lý ảnh y khoa 3-D trên nền JAVA
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
Hình 1.3: Giao diện chương trình BKDoctor của Bộ môn Vật lý Kỹ thuật Y sinh,
Trường Đại Học Bách Khoa – ĐHQG TP.HCM
Trong ngành giao thông vận tải, xử lý ảnh đã và đang được phát triển mạnh mẽ,
phục vụ được nhiều nhu cầu liên quan đến độ an toàn của con người và phương tiện
1.2. Tổng quan về xử lý ảnh
1.2.1. Xử lý ảnh là gì?
Trong ngành khoa học hình ảnh, xử lý ảnh là hình thức xử lý tín hiệu mà đầu
vào là một hình ảnh, chẳng hạn như một bức ảnh hoặc khung hình của đoạn phim; đầu
ra của xử lý hình ảnh có thể là một hình ảnh, một tập hợp các đặc điểm hoặc các thông
số liên quan đến hình ảnh.
Hình 1.5: Quá trình xử lý ảnh
Có thể hiểu một cách khác, xử lý ảnh bao gồm tất cả các lý thuyết và kỹ thuật
liên quan, cho phép tạo lập một hệ thống có khả năng tiếp nhận thông tin từ các hình
ảnh thu được, lưu trữ và xử lý theo nhu cầu.
Sơ đồ tổng quát của một hệ thống xử lý ảnh [1]:
Hình 1.6: Các bước cơ bản trong xử lý ảnh
Thu
nhận ảnh
Tiền
xử lý
Trích chọn
đặc điểm
Hậu
xử lý
Hệ
quyết định
Đối sánh, rút
ra kết luận
Lưu trữ
cho các bước xử lý sau đó.
Khử nhiễu: Nhiễu được chia thành hai loại:
Bảng 1.1: So sánh đặc trưng và phương pháp khử nhiễu của hai loại nhiễu
Loại nhiễu
Nhiễu hệ thống
Nhiễu ngẫu nhiên
Đặc trưng
Có quy luật
Không có quy luật
Phương pháp khử nhiễu
Phép biến đổi
Phương pháp nội suy, lọc
trung vị, lọc trung bình
Chỉnh mức xám: Là kỹ thuật nhằm chỉnh sửa tính không đồng đều của thiết bị
thu nhận hoặc độ tương phản giữa các vùng ảnh.
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
Chỉnh tán xạ: Ảnh thu nhận từ các thiết bị quang học hay điện tử có thể bị mờ,
nhòe. Phương pháp biến đổi Fourier dựa trên tích chập của ảnh với hàm tán xạ cho
phép giải quyết việc hiệu chỉnh này.
Nắn chỉnh hình học: Những biến dạng hình học thường do các thiết bị điện tử
và quang học gây ra. Do đó phương pháp hiệu chỉnh hình ảnh dựa trên mô hình được
mô tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng f(x’,y’)
như sau:
(1.1)
Trong đó, là các phương trình tuyến tính (biến dạng do phối cảnh) hay phương
trình bậc hai (biến dạng do ống kính camera).
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:
Đối sánh mẫu dựa trên các đặc trưng được trích chọn.
Phân loại thống kê.
Đối sánh cấu trúc.
Phân loại dựa trên mạng nơ-ron nhân tạo.
Trong các ứng dụng không thể chỉ dùng có một cách tiếp cận đơn lẻ để phân loại
tối ưu nên 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 bao gồm nhiều mô
hình kết hợp.
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
1.2.3. Một số khái niệm trong xử lý ảnh
1.2.3.1. Ảnh tƣơng tự, điểm ảnh và ảnh số
Ảnh tương tự là một bức ảnh được lưu trữ trên phim, giấy, gỗ… Ảnh tương tự là
ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính, ảnh tương tự cần phải
được số hoá.
Số hoá ảnh là sự biến đổi gần đúng một ảnh tương tự thành một tập điểm phù
hợp với ảnh thật về vị trí (không gian) và độ sáng (mức xám). Khoảng cách giữa các
điểm ảnh đó được thiết lập sao cho mắt người không phân biệt được ranh giới giữa
chúng. Mỗi một điểm như vậy gọi là điểm ảnh và tập hợp các điểm ảnh theo một tiêu
chuẩn được gọi là một ảnh số.
1.2.3.2. Độ phân giải, mật độ điểm ảnh
Độ phân giải là số lượng điểm ảnh của một ảnh số. Độ phân giải của ảnh được
đo bằng đơn vị pixel. Hiện nay số lượng điểm ảnh đã lên tới hàng triệu và thường
Ảnh nhị phân: là ảnh chỉ có 2 mức đen trắng phân biệt. Nói cách khác: mỗi
điểm ảnh của ảnh nhị phân chỉ có thể mang giá trị là 0 hoặc 1.
1.2.4. Phƣơng pháp biểu diễn ảnh
Sau khi thu nhận và số hóa, ảnh sẽ được lưu trữ hay chuyển sang giai đoạn phân
tích. Dưới đây là một số phương pháp biểu diễn ảnh trên bộ nhớ máy tính.
1.2.4.1. Mã loạt dài
Mã loạt dài hay dùng để biểu diễn cho vùng ảnh hay ảnh nhị phân. Một vùng
ảnh R có thể biểu diễn đơn giản nhờ một ma trận nhị phân:
(1.2)
Với các biểu diễn trên, một vùng ảnh hay ảnh nhị phân đựoc xem như chuỗi 0
hay 1 đan xen. Các chuỗi này được gọi là mạch (run). Theo phương pháp này, mỗi
mạch sẽ được biểu diễn bởi địa chỉ bắt đầu của mạch và chiều dài mạch theo dạng
{<hàng,cột>, chiều dài}.
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
1.2.4.2. Mã xích
Mã xích thường được dùng để biểu diễn biên của ảnh. Thay vì lưu trữ toàn bộ
ảnh thì lưu trữ dãy các điểm ảnh như A, B…M. Theo phương pháp này, 8 hướng của
vectơ nối 2 điểm biên liên tục được mã hóa. Khi đó ảnh được biểu diễn qua điểm ảnh
bắt đầu A cùng với chuỗi các từ mã. Điều này được minh họa trong hình dưới đây:
Hình 1.9: Hướng các điểm biên và mã tương ứng
1.2.4.3. Mã tứ phân
Theo phương pháp mã tứ phân, một vùng ảnh coi như bao kín một hình chứ
nhật. Vùng này được chia làm 4 vùng con (Quadrant). Nếu một vùng con gồm toàn
điểm đen (1) hay toàn điểm trắng (0) thì không cần chia tiếp. Trong trường hợp ngược
lại, vùng con gồm cả điểm đen và trắng gọi là vùng không đồng nhất, tiếp tục chia
thành 4 vùng con tiếp và kiểm tra tính đồng nhất của các vùng con đó.
dựa vào biên độ, phân vùng dựa theo kết cấu.
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
CHƢƠNG 2: MỘT SỐ KỸ THUẬT TRÍCH CHỌN ĐẶC TRƢNG HÌNH DẠNG
Các đặc điểm hình dạng của các vùng ảnh và các đối tượng ảnh được sử dụng
trong rất nhiều hệ thống tra cứu ảnh. So với các đặc điểm về màu sắc và các đặc điểm
về kết cấu thì các đặc điểm về hình dạng thường chỉ được sử dụng sau khi ảnh đã phân
thành các vùng hoặc các đối tượng ảnh.
Các phương pháp trích chọn đặc điểm hình dạng thường được chia thành hai loại
là trích chọn dựa theo đường biên và trích chọn dựa theo vùng ảnh.
Một phương pháp trích chọn đặc điểm hình dạng tốt phải đảm bảo yêu cầu là phải
không phụ thuộc vào vị trí, góc quay hay sự co giãn của đối tượng ảnh.
Trước khi áp dụng các phương pháp trích chọn đặc điểm hình dạng, các đối tượng
ảnh cần phải được tách ra khỏi ảnh. Giả sử là trong mỗi ảnh chỉ có một đối tượng ảnh
duy nhất, nhiệm vụ của hệ thống trước hết là phải tách được đối tượng ảnh ra khỏi nền
ảnh.
Cách biểu diễn hình dạng của đối tượng ảnh có thể chia thành hai kiểu:
Theo đường bao quanh (biên)
Theo vùng
Cách biểu diễn theo đường viền bao quanh chỉ sử dụng đường biên bên ngoài của
hình dạng, điều này có thể thực hiện được bằng cách mô tả vùng đó bằng cách đặc tính
bên ngoài của nó tức là các điểm ảnh dọc theo đường viền bao quanh đối tượng. Cách
biểu diễn theo vùng sử dụng cả vùng ảnh bằng cách mô tả vùng đang quan tâm bằng
các đặc tính bên trong tức là các điểm ảnh ở bên trong vùng đó.
Hình 2.1: Biểu diễn hình dạng theo đường biên và theo vùng a, Đường biên lý tưởng b, Đường biên bậc thang c, Đường biên thực
Hình 2.2: Biểu diễn đường biên ảnh
u
u
u
x
x
x
Copyright: Tài liệu đại học ©