Ngày nay thông tin nói chung sử dụng trong ảnh là phổ biến. Rất nhiều lĩnh vực sử dụng ảnh nhưmột công cụ để thực hiện công việc.
Những năm gần đây, chứng kiến tốc độ gia tăng mạnh của ảnh số trên toàn thế giới, bởi sự gia tăng mạnh mẽ của các trạm làm việc tại mặt đất cũng như trạm vệ tinh, khó khăn trong lưu trữ, chi phí cao cho xử lývà internet. Sự đa dạng các ứng dụng của ảnh góp phần ra đời thế hệ ảnh số.
90 trang |
Chia sẻ: vietpd | Lượt xem: 1372 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu phương pháp nhận dạng hình dạng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Bộ giáo dục và đào tạo
Tr−ờng đại học bách khoa Hà nội
---------------------------------------------
Luận văn thạc sĩ khoa học
Nghiên cứu ph−ơng pháp nhận
dạng hình dạng
Ngành: xử lý thông tin và truyền thông
M∙ số: 421
đinh thị kim ph−ợng
Ng−ời h−ớng dẫn khoa học: T.S. Nguyễn kim anh
Hà nội 2006
- 2 -
Lời cam đoan
Tôi xin cam đoan bản luận văn này là kết quả nghiên cứu của bản thân d−ới
sự h−ớng dẫn của TS. Nguyễn Kim Anh. Nếu có gì sai phạm, tôi xin hoàn toàn
chịu trách nhiệm.
Ng−ời làm cam đoan
Đinh Thị Kim Ph−ợng
- 3 -
Mục Lục
Lời cam đoan..........................................................................................................2
Mục Lục .................................................................................................................3
Danh Mục Các từ viết tắt........................................................................................6
Danh mục hình vẽ...................................................................................................7
Lời nói đầu .............................................................................................................9
Ch−ơng 1:Tổng quan về tìm kiếm ảnh dựa trên hình dạng .Error! Bookmark not
defined.
1.1. Giới thiệu...................................................................................................12
1.2. Trích chọn đặc tr−ng..................................................................................13
1.2.1.Biến đổi Fourier ...................................................................................12
1.2.1.1.Chuỗi Fourier....................................................................................13
1.2.1.2. Sự hội tụ của chuỗi Fourier..............................................................14
1.2.1.3. Biến đổi Fourier...............................................................................14
1.2.1.4. Biến đổi Fourier rời rạc ...................................................................15
1.2.1.5. Biến đổi Fourier hai chiều ...............................................................16
1.2.1.6. Phạm vi của biến đổi Fourier...........................................................16
1.2.2. Không gian độ chia (Scale space).......................................................17
1.2.2.1. Cơ sở ................................................................................................17
1.2.2.2. Không gian độ chia Gaussian..........................................................19
1.2.2.3. Phạm vi của sự không tạo các đặc tr−ng mới ..................................19
1.2.2.4. Không gian độ chia mâu thuẫn với việc đa quyết định ...................20
1.2.3.Thảo luận .............................................................................................22
1.3. Phép đo t−ơng đ−ơng và thực hiện phép đo...............................................22
1.3.1. Phép đo sự giống nhau........................................................................23
1.3.1.1. Không gian phép đo khoảng cách (Distance Metric Spaces) .........24
1.3.1.2. Khoảng cách dạng Minkowski ........................................................24
1.3.1.3. Khoảng cách Cosin..........................................................................24
1.3.1.4. Thông tin thống kê
2χ ...................................................................25
1.3.1.5. Đ−ờng giao biểu đồ .........................................................................25
- 4 -
1.3.1.6. Khoảng cách bậc hai........................................................................26
1.3.1.7. Khoảng cách Mahalanobis ..............................................................27
1.3.2.Thực hiện phép đo ...............................................................................27
1.3.2.1. Độ nhạy và độ chính xác(RPP). ......................................................28
1.3.2.2. Tỷ lệ trọng số thành công (PWH- Percentage of Weighted Hits) ...28
1.3.2.3. Phần trăm của thứ bậc giống nhau (PSR-Percentage of Similarity
Ranking ) ......................................................................................................29
1.3.2.4. Thảo luận .........................................................................................30
1.3.3. Trích chọn đặc tr−ng hình dạng..........................................................30
1.4. Thảo luận...................................................................................................32
Ch−ơng 2 Ph−ơng pháp tách contrario .................................................................33
2.1. Cluster có thứ bậc và đánh giá giá trị........................................................34
2.1.1.Giá trị nhóm Contrario ........................................................................34
2.1.1.1. Cơ sở: ...............................................................................................34
2.1.1.2. Nhóm có ý nghĩa. ............................................................................35
2.1.2. Tiêu chuẩn kết hợp tốt nhất. ...............................................................37
2.1.3. Vấn đề tính toán .................................................................................40
2.1.3.1. Lựa chọn vùng thử. ..........................................................................40
2.1.3.2. Riêng rẽ và cực đại. .........................................................................42
2.2.1. Nhiễu điểm .........................................................................................43
2.2.2. Phân đoạn ...........................................................................................43
2.3. Kết cấu nhóm và không gian t−ơng ứng....................................................46
2.3.1. Tại sao phải tách kết cấu không gian. ................................................46
2.3.2. Đối sánh nhân tố hình dạng................................................................47
2.3.3. Biến đổi mô tả.....................................................................................49
2.3.3.1. Tr−ờng hợp t−ơng đồng ...................................................................49
2.3.3.2. Tr−ờng hợp biến đổi mối quan hệ ...................................................50
2.3.4. Cluster có ý nghĩa của biến đổi ..........................................................52
2.3.4.1. Phép đo sự không t−ơng đ−ơng giữa các biến đổi. ..........................52
2.3.4.2 Ph−ơng thức nền ...............................................................................52
2.3.4.3. Kỹ thuật nhóm .................................................................................54
2.4. Thảo luận...................................................................................................55
Ch−ơng 3:Ph−ơng pháp ra quyết định Contrario..................................................56
3.1. Một quyết định Contrario ......................................................................58
3.1.1. Ph−ơng pháp hình dạng trái ng−ợc ph−ơng pháp nền ........................58
3.1.2. Ph−ơng thức quyết định Contrario......................................................59
3.1.3. Ước l−ợng xác suất cảnh báo sai ........................................................61
- 5 -
3.1.4. Luật ra quyết định Contrario ..............................................................61
3.2. Tự động thiết lập ng−ỡng khoảng cách .................................................62
3.2.1. Số các cảnh báo sai NFA....................................................................62
3.2.2. Đối sánh có ý nghĩa ............................................................................63
3.2.3. Ng−ỡng nhận dạng t−ơng ứng với ngữ cảnh.......................................64
3.2.4. Tại sao quyết định Contrario ..............................................................65
3.3. Xây dựng đặc tr−ng độc lập thống kê....................................................66
3.4.Chuẩn hóa nhân tố hình dạng từ ảnh cho đặc tr−ng độc lập...................68
3.4.1. Biểu diễn hình dạng bằng các mức đ−ờng..........................................68
3.4.2.Tiêu chuẩn hóa và mã hóa bán cục bộ.................................................70
3.4.2.1. Mã hóa / Tiêu chuẩn hóa trị không đổi t−ơng đ−ơng ......................71
3.4.2.2. Mã hóa / Chuẩn hóa quan hệ bất biến .............................................73
3.4.3. Từ chuẩn hóa nhân tố hình dạng đến đặc tr−ng độc lập. ....................73
3.5. Thảo luận ...............................................................................................76
Ch−ơng 4Thử nghiệm...........................................................................................78
4.1. Thử nghiệm ph−ơng pháp nền...................................................................78
4.2. Thử nghiệm ph−ơng pháp Contrario..........................................................80
4.2.1. Hai ảnh không quan hệ với nhau ........................................................80
4.2.2. Méo dạng quan sát xa gần ..................................................................81
4.2.3. Quan hệ với sự nghẽn cục bộ và thay đổi độ t−ơng phản...................83
Kết luận ................................................................................................................88
Tài liệu tham khảo................................................................................................89
Tóm tắt luận văn...................................................................................................90
- 6 -
Danh Mục Các từ viết tắt
STT Từ viết tắt ý nghĩa
1 CBIR Content Based Image Retrieval
2 FD Fourie Descriptor
3 FFT Fast Fourie Transform
4 CSDL Cơ sở dữ liệu
5 NFA Number of Fasle Alarm
6 PFA Pridicion Fasle Alarm
7 FT Fourie Transform
8 NFAg NFA of region
9 NFAgg NFA of region-region
10 Pro Proposition
11 PFA Probability of False Alarm
- 7 -
Danh mục hình vẽ
Hình 1.1: Đối t−ợng bị làm nhiễu bởi biến đổi phổ. ............................................13
Hình 1.2: ảnh và các biến đổi khác .....................................................................13
Hình 1.3: Điểm qua 0 tại vị trí x và độ chia t của tín hiệu ...................................20
Hình 1.4: (a) Khoảng cách Ocolit, .......................................................................25
(b) khoảng cách Cosin, (c) khoảng cách L1.........................................................25
Hình 1:a) ảnh ký tự,b) mức đ−ờng t−ơng ứng, c) Đoạn mức đ−ờng ...................31
Hình 2.2: Nhóm dữ liệu 950 điểm đồng dạng......................................................37
Hình 2.5: Vấn đề quan trọng của phân bố ph−ơng thức nền................................43
Hình 2.6: Phân đoạn ảnh đã scan và 71 đ−ờng mức có mức ý nghĩa cực đại. .....44
Hình 2.7: Nhóm với mối quan hệ tới h−ớng.........................................................45
Hình 2.8: Nhóm trong không gian(toạ độ x, h−ớng)............................................46
Hình 2.9: Thử nghiệm Guernica...........................................................................48
Hình 2.10: Thử nghiệm “ Guernica “ quan hệ t−ơng ứng ý nghĩa không đổi ......49
Hình 2.11: Hai đoạn mức đ−ờng và khung t−ơng ứng .........................................50
Hình 2.12: Thử nghiệm “ Guernica “ ...................................................................51
Hình 3.1: Trích chọn mức đ−ờng có ý nghĩa.......................................................70
Hình 3.3: Mã hoá sự không đổi t−ơng đ−ơng bán cục bộ ....................................73
Hình 3.4 : Mã hóa bán cục bộ mối quan hệ không đổi. . .....................................74
Hình 3.5 : Mã hóa hình dạng bán cục bộ quan hệ bất biến..................................75
- 8 -
Hình 3.6: Mã hoá sự t−ơng đồng không đổi.........................................................76
Hình 4.1: ảnh và mức đ−ờng có ý nghĩa .............................................................80
Hình 4.2: Thử nghiệm hitchcook..........................................................................82
Hình 4.3: Ph−ơng pháp nhận dạng bán cục bộ quan hệ không đổi ......................83
Hình 4.4: Ph−ơng pháp nhận dạng quan hệ bán cục bộ không đổi ......................83
Hình 4.5 Ph−ơng pháp nhận dạng bán cục bộ .....................................................84
Hình 4.6: Tập các đoạn đ−ờng mức đối sánh với ảnh trong CSDL......................85
Hình 4.7: Ph−ơng pháp bán cục bộ t−ơng đồng không đổi ..................................85
Hình 4.8: ảnh gốc và mức đ−ờng có ý nghĩa.......................................................86
Hình 4.9: ảnh Menima và mức đ−ờng có ý nghĩa ...............................................86
- 9 -
Lời nói đầu
Ngày nay thông tin nói chung sử dụng trong ảnh là phổ biến. Rất nhiều
lĩnh vực sử dụng ảnh nh− một công cụ để thực hiện công việc.
Những năm gần đây, chứng kiến tốc độ gia tăng mạnh của ảnh số trên toàn
thế giới, bởi sự gia tăng mạnh mẽ của các trạm làm việc tại mặt đất cũng nh−
trạm vệ tinh, khó khăn trong l−u trữ, chi phí cao cho xử lý và internet. Sự đa dạng
các ứng dụng của ảnh góp phần ra đời thế hệ ảnh số. Các ứng dụng của ảnh bao
gồm: giải trí số, th− viện số, giáo dục và World Wide Web (www). Các ứng dụng
ngày càng trở nên phụ thuộc vào việc sử dụng ảnh gốc. Lợi ích tr−ớc mắt của ảnh
số gồm cả mặt xã hội và th−ơng mại. Sử dụng ảnh gốc giúp sáng tạo sản phẩm
mới, tiết kiệm thời gian và tiền bạc. Tuy nhiên, độ lớn của kho l−u trữ ảnh số trên
toàn thế giới có giới hạn, sự tận dụng ảnh số từ CSDL hiện tại khó hơn. Điều này
là vì thiếu cách đánh chỉ mục và quản lý ảnh số chuẩn.
Thông th−ờng các ảnh đ−ợc l−u trữ trong CSDL sử dụng d−ới dạng các
thông tin thuộc tính. Thuận lợi của việc đánh chỉ mục thuộc tính ảnh: nó có thể
cung cấp cho ng−ời sử dụng từ khoá tìm kiếm l−ớt qua mục lục, thậm chí thông
qua giao diện truy vấn; ví dụ nh− ngôn ngữ truy vấn cấu trúc (SQL). Tuy nhiên,
nhìn từ bên ngoài có hạn chế; một trong những hạn chế đó là thời gian tính toán
khi CSDL lớn, nó d−ờng nh− không thể chú giải thủ công tất cả các ảnh. Mặt
khác các đặc tr−ng thị giác của ảnh rất khó mô tả bằng từ ngữ một cách khách
quan, có một tiêu điểm mới trên việc phát triển công nghệ đánh chỉ mục ảnh, đó
là khả năng tìm kiếm ảnh dựa trên ngữ cảnh: nó có thể độc lập và có thể tự động
hoá. Các công nghệ hiện tại đa phần qui về tìm kiếm ảnh dựa trên ngữ nghĩa
(CBIR). CBIR đ−ợc giới thiệu nh− phần bổ xung cho việc tiến tới đánh chỉ mục
thuộc tính truyền thống, nó là cần thiết để cấu thành CSDL multimedia. Vì những
- 10 -
tiềm năng ứng dụng rộng rãi của nó, CBIR đã thu hút đ−ợc số l−ợng lớn các chú
ý trong những năm gần đây (KAT 92, NIB 93, YOS 99).
Trong CBIR, ảnh trong CSDL là dữ liệu không cấu trúc, ảnh số hoàn toàn
chỉ bao gồm mảng các pixel độ chói, không có ý nghĩ vốn có. Một trong những
chìa khoá bắt nguồn CBIR là sự cần thiết để trích chọn thông tin hữu ích từ dữ
liệu thô, để phản ánh ngữ nghĩa ảnh. Vì vậy việc trích chọn hiệu quả các đặc
tr−ng ngữ nghĩa đó là điều cốt yếu sự thành công của CBIR. Nghiên cứu trên
những yêu cầu của ng−ời sử dụng đối với ảnh từ bộ s−u tập ảnh biểu thị những
đặc tr−ng nguyên thuỷ đó nh− màu sắc, kết cấu, hình dạng hoặc hỗn hợp của
chúng là rất hữu ích đối với việc mô tả và khôi phục ảnh (EAK 99). Những đặc
tr−ng này là khách quan và trực tiếp bắt nguồn từ tự bản thân ảnh mà không cần
tham khảo bất kỳ một kiến thức cơ bản nào từ bên ngoài. Vì vậy đặc tr−ng
nguyên thuỷ của ảnh ở mức thấp có thể đ−ợc bắt nguồn và khai thác để khuyến
khích việc CBIR tự động hoá.
*Đối t−ợng nghiên cứu
Từ các thông tin cơ bản trên đây các ảnh trong CSDL có thể đ−ợc đánh chỉ
mục bằng cách sử dụng thông tin thuộc tính hoặc thông tin ngữ nghĩa. Ngữ nghĩa
của ảnh có thể đ−ợc mô tả sử dụng các đặc tr−ng nguyên thuỷ; ví dụ: màu sắc,
cấu trúc, hình dạng hoặc tổ hợp của chúng. Kết quả nghiên cứu này chấp nhận
tiến tới CBIR, đó là việc đánh chỉ mục và tìm kiếm ảnh bằng ngữ nghĩa của ảnh.
Đặc biệt, việc tìm kiếm hội tụ ở việc đánh chỉ mục và tìm kiếm ảnh dựa trên hình
dạng. Mục đích chủ yếu của cách tìm kiếm này là tìm kiếm và khai thác hình
dạng rất khả thi để tìm kiếm và nhận dạng hình dạng. Điều tra các công nghệ và
phát triển trong nghiên cứu này có thể là trực tiếp ứng dụng cho các ứng dụng
đặc thù; ví dụ tìm kiếm nhãn mác, nhận dạng đối t−ợng… hoặc có thể hợp nhất
trong bất cứ hệ thống CBIR nào để dễ dàng nhận dạng hình dạng sử dụng các đặc
tr−ng hỗn hợp của ảnh.
- 11 -
Nhận dạng nói chung hội tụ các vấn đề của nhận dạng trực quan dựa trên
thông tin hình dạng hình học. Ph−ơng pháp nhận dạng hình dạng th−ờng bao
gồm 3 tiến trình: trích chọn đặc tr−ng, đối sánh (cốt lõi của tiến trình này là định
nghĩa 1 khoảng cách hoặc phép đo sự t−ơng đồng giữa các đặc tr−ng hình dạng
đ−ợc mô tả) và ra quyết định. Phần này chủ yếu nghiên cứu vấn đề ra quyết định
cho đối sánh hình dạng, đặc biệt trong khung chung giữa hai hình dạng giống
nhau để đối sánh, nó có thể đi tới quyết định nh− thế nào? Mục đích để định
nghĩa tiêu chuẩn thống kê dẫn tới quyết định 2 hình dạng là giống hay không.
Nghiên cứu các tiến trình thực hiệnnhận dạng hình dạng theo trình tự các
công đoạn: từ công đoạn sơ khai biểu diễn ảnh, trích chọn đặc tr−ng, tách nhóm
nhân tố hình dạng thành 1 hình dạng và chủ yếu là ph−ơng pháp ra quyết định
Contrario cho nhận dạng hình dạng.
*Cấu trúc luận văn
Ch−ơng 1 : Tổng quan về tìm kiếm ảnh dựa trên hình dạng
Ch−ơng 2: Tách nhóm
Ch−ơng 3: Ph−ơng pháp Contrario cho nhận dạng hình dạng
Ch−ơng 4: Thử nghiệm
Do thời gian và khả năng có hạn nên luận văn này sẽ còn nhiều thiếu sót. Rất
mong đ−ợc sự góp ý và thông cảm của các thầy giáo, cô giáo.
Hà nội, ngày 6 tháng 11 năm 2006
Học viên
Đinh Thị Kim Ph−ợng
- 12 -
Ch−ơng 1
Tổng quan tìm kiếm ảnh
dựa trên hình dạng
1.1. Giới thiệu
Vấn đề cơ bản của tìm kiếm ảnh dựa trên hình dạng là phép đo sự t−ơng
đồng giữa các các hình dạng đ−ợc mô tả bởi các đặc tr−ng của chúng. Vì vậy, hai
b−ớc cần thiết trong tìm kiếm và nhận dạng ảnh dựa trên hình dạng đó là trích
chọn đặc tr−ng và phép đo t−ơng đ−ơng giữa các đặc tr−ng đã đ−ợc trích chọn.
Hai công cụ cơ bản cần thiết đ−ợc sử dụng trong trích chọn đặc tr−ng hình
dạng là biến đổi Fourier và không gian độ chia. Mặc dù trích chọn đặc tr−ng là
mấu chốt để tìm kiếm ảnh dựa trên hình dạng và nhận dạng hình dạng, phép đo
sự t−ơng đồng giữa các đặc tr−ng đ−ợc trích chọn cũng rất quan trọng. yêu cầu
hiệu quả tìm kiếm ảnh đó là nhận biết nhanh các hình dạng t−ơng đồng - sự
t−ơng đồng trong giới hạn của các đặc tr−ng đ−ợc trích chọn.
1.2. Công cụ trích chọn đặc tr−ng
Biến đổi Fourie là một công cụ kinh điển. Nó đã đ−ợc sử dụng từ nhiều
năm nay trong mọi hệ thống xử lý tín hiệu và hệ thống máy tính. Còn không gian
độ chia là một công cụ mới đang đ−ợc chú ý gần đây.
1.2.1.Biến đổi Fourier
Biến đổi Fourie là mấu chốt trong xử lý ảnh nó đ−ợc ứng dụng rộng rãi
trong lý thuyết cũng nh− trong thực tế. Nguyên tắc cơ bản của biến đổi Fourie đó
là một đối t−ợng đ−ợc coi nh− một tín hiệu và nh− vậy có thể biểu diễn đối t−ợng
thành các thành phần cơ bản của tín hiệu. Biến đổi Fourie rất hữu ích cho phân
tích các đối t−ợng khác nhau: có thể đối t−ợng bị làm nhiễu bởi biến đổi phổ
- 13 -
(Hình 1.1), trong khi các đối t−ợng t−ơng đ−ơng khác sẽ có biến đổi phổ t−ơng
tự thậm chí cả khi chúng bị ảnh h−ởng bởi nhiễu và các biến đổi khác(hình 1.2).
Hình 1.1: Đối t−ợng bị làm nhiễu bởi biến đổi phổ.
Hình 1.2: ảnh và các biến đổi khác
1.2.1.1.Chuỗi Fourier
Đặt f(x) là hàm tuần hoàn chu kỳ 2π và nguyên trong một chu kỳ, theo lý
thuyết Four