MỤC LỤC
Nội dung Trang
ĐẶT VẤN ĐỀ . 8
LỜI NÓI ĐẦU . 9
Chương 1: KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ ĐỘ ĐO TưƠNG TỰ
TRONG XỬ LÝ ẢNH . 11
1.1. Khái quát về xử lý ảnh . 11
1.1.1. Một số khái niệm cơ bản . 11
1.1.2. Một số vấn đề trong xử lý ảnh . 12
1.1.2.1. Các hệ thống xử lý ảnh . 12
1.1.2.2. Các hình thái của ảnh. 14
1.1.2.3. Một số ứng dụng trong xử lý ảnh . 15
1.1.2.4. Một số khái niệm, định nghĩa trong xử lý video . 17
1.1.2.5. Lược đồ màu (Color Histogram) . 22
1.1.2.6. Lược đồ tương quan màu (Color Correlogram) . 25
1.1.2.7. Đặc trưng chuyển động (Motion) . 26
1.1.2.8. Các bước thao tác với file video . 28
1.2. Độ đo tương tự trong xử lý ảnh . 30
Chương 2: MỘT SỐ PHưƠNG PHÁP XÁC ĐỊNH ĐỘ ĐO TưƠNG TỰ . 32
2.1. Độ đo dựa trên khoảng cách . 32
2.1.1. Độ đo khoảng cách min – max. 32
2.1.2. Độ đo khoảng cách Euclid . 32
2.1.3. Độ đo khoảng cách toàn phương: . 32
2.2. Độ đo sử dụng trọng số . 32
2.2.1. Độ đo có trọng số: . 32
2.2.2. Độ đo hỗn hợp . 33
2.2.2.1. Thuộc tính rời rạc . 33
2.2.2.2. Thuộc tính có thứ tự . 34
2.2.2.3. Thuộc tính liên tục . 35
2.2.2.4. Kết hợp độ đo của các thuộc tính . 36
2.2.2.5. Thuật toán nhanh cho thuộc tính liên tục . 38
2.2.2.6. Thuật toán nhanh cho thuộc tính có thứ tự . 40
2.3. Độ đo tương tự có thể học (Trainable similarity measure) . 41
2.4. Độ đo dựa trên Histogram . 43
2.4.1. Giới thiệu . 43
2.4.2. Định nghĩa . 43
2.4.3. Lược đồ mức xám hai chiều. 44
2.4.4. Các tính chất của lược đồ mức xám . 45
2.4.5. Quan hệ giữa lược đồ mức xám và ảnh . 46
2.4.6. Một chiều . 46
2.4.7. Hai chiều . 47
CHưƠNG 3: ỨNG DỤNG ĐỘ ĐO TưƠNG TỰ TRONG VIỆC PHÂN
LOẠI ẢNH TRONG FILE VIDEO . 49
3.1. Giới thiệu bài toán . 49
3.2. Cài đặt thuật toán . 49
3.2.1. Code đọc ảnh . 49
3.2.2. Code đọc và extract frame file video . 56
3.3. Kết quả thực nghiệm và đánh giá . 59
PHẦN KẾT LUẬN . 62
TÀI LIỆU THAM KHẢO .
63 trang |
Chia sẻ: maiphuongdc | Lượt xem: 3019 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu một số kỹ thuật xác định độ đo tương tự và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
reen), lam (blue). Không gian
màu RGB cũng gồm có 3 thành phần màu: Red, Green, và Blue. Những
thành phần này được gọi là màu gốc để cộng vào, vì mỗi màu được tạo nên
bằng cách cộng thêm các phần tử vào màu đen(0,0,0).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Hình 1.8. Không gian RGB
Hình 1.9. Không gian RGB
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
Hình 1.10. Không gian RGB
- Không gian màu CMY
Không gian CMY được dùng chủ yếu trong in ấn. CMY là viết tắt
của Cyan-Magenta-Yellow (màu lục lam, màu đỏ tươi, màu vàng), đó là ba
màu chính tương ứng với ba màu mực in. Chúng được gọi là những màu
gốc để trừ, vì mỗi màu trong không gian CMY được tạo ra thông qua
việc hấp thu độ sáng. Cyan hấp thu sự chiếu sáng của màu đỏ, Magenta hấp
thu màu xanh lục, Yellow hấp thu màu xanh dương.
Hình 1.11. Không gian CMY
Mối quan hệ giữa RGB và CMY :
C = 1 – R
M = 1 – G
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
Y = 1 - B
- Không gian màu HSV
Mô hình HSV(Hue, Saturation, Value), còn gọi là HSB (Hue, Saturation,
Brightness) định nghĩa một không gian màu gồm có 3 thành phần tạo nên :
Hue, loại màu (chẳng hạn màu đỏ, xanh, hay vàng) Có giá trị
từ 0 - 360 hoặc từ 0 - 2đ
Saturation, độ thuần khiết của màu
Có giá trị từ 0 – 100%, thường được chuẩn hoá về 0 – 1. Độ thuần khiết của
một màu càng thấp, độ xám của màu đó càng nhiều và màu đó càng mờ.
Value, độ sáng của màu
Có giá trị từ 0 – 100%, thường được chuẩn hóa về 0 – 1.
Mô hình HSV được tạo ra từ nãm 1978 bởi Alvy Ray Smith. Nó là một
phép biến đổ i phi tuyến của không gian màu RGB. Mô hình HSV giúp tách
bạch màu (H, S) và độ sáng (V), phù hợp với cảm nhận của con người.
1.1.2.5. Lược đồ màu (Color Histogram)
* Định nghĩa
Lược đồ màu của ảnh cho biết sự phân bố của các màu trong ảnh.
n
in
iH
][
][
Trong đó :
i là một bin màu, nếu ảnh độ xám thì i[0,255] , nếu ảnh màu RGB
thì i [0,224 ]
n[i] : số điểm ảnh có giá trị màu là i n : tổng số điểm ảnh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
Hình 1.12. Lược đồ màu ứng với frame
Hình 1.13. Mắt người không nhạy cảm với sự thay đổi màu sắc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
Để cải tiến phù hợp cho việc ứng dụng trong tìm kiếm, các màu trong
không gian màu HSV được định lượng trước khi tính lược đồ màu. Có nhiều
cách định lượng, một trong những cách đó là
chia Hue thành 18 vùng,
chia Saturation thành 3 vùng
chia Value thành 3 vùng
Khi đó, tổng số màu bằng HxSxI = 162 màu, chi phí tính toán và lư u
trữ giảm đi rất nhiều, và lược đồ màu này rất thích hợp cho việc truy tìm
thông tin thị giác.
Hình 1.14. Các màu đã được định lượng trong không gian HSV
* Ý nghĩa của lược đồ màu
Đối với một màu ci, Hci(I) thể hiện số điểm ảnh có màu ci trong ảnh I.
Nói cách khác, với mỗi điểm ảnh trong ảnh I, Hci(I) thể hiện xác suất điểm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25
ảnh đó có màu là ci. Không có mang thông tin về không gian.
* Đánh giá ưu điểm, khuyết điểm
Ưu điểm
- Tính toán lược đồ màu ít tốn chi phí, đơn giản, nhanh chóng.
- Lược đồ màu bất biến đối với một số phép biến đổi hình học như phép
biến đổi Affine : tịnh tiến, xoay, sự co, giãn.
Khuyết điểm
Lược đồ màu chỉ xét phân bố toàn cục về màu của ảnh mà không xét
đến yếu tố cục bộ về vị trí, làm mất thông tin về quan hệ không gian giữa các
màu. Dẫn đến việc có thể có nhiều ảnh khác nhau nhưng lại có cùng lược đồ
màu
Ứng dụng
Được ứng dụng nhiều trong việc phân đoạn video và truy tìm thông tin
thị giác.
1.1.2.6. Lược đồ tương quan màu (Color Correlogram)
* Giới thiệu lược đồ tương quan màu
Quan sát thấy rằng lược đồ màu thiếu thông tin về cách mà màu sắc
được phân bố theo không gian, Một đặc trưng mới được giới thiệu gọi là
lược đồ tương quan màu. Lược đồ tương quan màu hứa hẹn mô tả không chỉ
là phân phối màu của các điểm ảnh mà còn là sự tương quan về không quan
giữa các cặp màu.
* Tính lược đồ tương quan màu
Gọi [D] là tập gồm D khoảng cách d1 , d 2 ,..., d D được đo bằng độ đo L .
Lược đồ tương quan màu của ảnh I được xác định với cặp màu ci , c j
và khoảng cách d như sau:
]|||[Pr)( 212
,
)(
,
21
dppIpI Lc
IpIp
d
cc j
c
ji
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26
Trong đó I là ảnh, kích thước MxN (Điểm ảnh), I c p I | Ip c, lược
đồ tương quan màu thể hiện xác suất cặp điểm ảnh bất kỳ p1và p2 chịu sự
ràng buộc về màu ( p1 có màu ci, p2 có màu c j ) và vị trí ( p1 p2 |L d ).
* Lược đồ tự tương quan màu
Nếu chúng ta xét đến tất cả sự kết hợp có thể có của các cặp màu,
kích thước của lược đồ tương quan màu sẽ rất lớn, hơn nữa, thời gian tính
toán sẽ lâu.
Do đó, một phiên bản đơn giản hơn được sử dụng, gọi là lược đồ tự tương
quan màu. Lược đồ này chỉ quan tâm đến sự tương quan về không gian
giữa những màu giống nhau và do đó giảm được số chiều và chi phí tính
toán. Lược đồ tự tương quan màu được xác định như sau:
)()( )(,
)( II dcc
d
c
c
( d)
(I ) là lược đồ tự tương quan màu của ảnh I ứng với màu c và khoảng
cách d.
* Ứng dụng
- Dùng trong việc phân đoạn video
- Tạo chỉ mục và so sánh ảnh
- Định vị đối tượng, theo vết đối tượng
So với lược đồ màu, lược đồ tự tương quan màu cho những kết quả truy
tìm tốt hơn nhưng tốn chi phí nhiều hơn.
1.1.2.7. Đặc trưng chuyển động (Motion)
* Giới thiệu
Chuyển động là một trong những đặc trưng của dữ liệu video. Đây
là một đặc trưng nổi bật của video mà ảnh tĩnh không có. Đặc trưng chuyển
động được sử dụng rất rộng rãi trong các nghiên cứu cũng như cài đặt ứng
dụng xử lý video số.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27
Hình 1.15. Đặc trưng chuyển động
* Lược đồ chuyển động
Nếu như lược đồ màu thể hiện sự phân phối màu trong ảnh thì lược đồ
chuyển động cho thấy sự phân phối chuyển động của các khung hình liên tiếp.
Sự phân phối này được thể hiện dưới dạng các góc chuyển động.
- Thuật toán tính lược đồ chuyển động
Chia khung hình thành n khối điểm ảnh, và định lượng các góc từ 0 đến
360 độ thành 8 phần : 0o-44o, 45o-89o,…, 315o-359o.
Bước 1: khởi động mảng các góc đã định lượng : H [i] 0 , với i từ 0 đến 7.
Bước 2: Xét một khối điểm ảnh của khung hình hiện tại, tính độ dịch
chuyển của nó bằng cách : trong khung hình tiếp theo, tìm khối có sự khác
biệt đặc trưng nhỏ nhất so với khối đang xét và sự khác biệt này cũng nhỏ
hơn một ngưỡng định trước. Mục đích của bước này là để xem khối này dịch
chuyển đến vị trí nào. Nếu không tìm thấy thì xem như khối điểm ảnh
này không di chuyển.
Bước 3 : Sau khi tính độ dịch chuyển, dễ dàng tính được góc dịch chuyển của
khối và định lượng góc đó về một giá trị a, a nằm trong khoảng từ 0 đến 7.
Bước 4 : tăng giá trị của H [a] H [a] 1 . Quay lại bước 2 cho đến khi tính hết
tất cả các khối điểm ảnh của khung hình.
ảnh tại vị trí điểm ảnh đang xét. Lặp lại bước 2 cho đến khi tính hết các
điểm ảnh trong khung hình.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28
Sau khi tính toán cho tất cả điểm ảnh trong khung hình, ta có được 2
ảnh chuyển động của khung hình theo 2 phương .
- Ý nghĩa
Ảnh chuyển động cho biết độ lớn chuyển động theo 2 phương của
mỗi điểm ảnh của khung hình. Tại vị trí nào đó mà ảnh chuyển động có giá trị
lớn thì điểm ảnh đó chuyển động càng nhiều.
1.1.2.8. Các bước thao tác với file video [1]
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).
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.
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ố
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29
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.
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).
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(PAVISTREAMpavi,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)
Bƣớc 5: Thao tác với frame
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30
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.
1.2. Độ đo tƣơng tự trong xử lý ảnh[3]
Hiện nay trên thế giới có rất nhiều phương tiện dùng để thu thập thông
tin và lưu dưới dạng số hoá. Trong khi lưu trữ các thông tin này người sử
dụng gặp phải vấn đề với quá nhiều hình ảnh khác nhau và vấn đề quản lý
những hình ảnh này. Rất nhiều các nhà lập trình đã tiếp cận và tạo ra hệ thống
để quản lý một cách có hiệu quả nhất tức là dùng bộ nhớ thị giác của máy tính
để lưu trữ và đối sánh những hình ảnh này.
Nghiên cứu “sự tương tự” (thường ở dạng đối ngẫu của nó là “khoảng
cách”) thuộc phạm vi toán học, chẳng hạn trong lý thuyết tôpô và xấp xỉ;
nhưng trong khoa học máy tính và các ứng dụng máy tính có phần khác.
Trong khoa học máy tính, phép tính xấp xỉ thường được sử dụng theo một lối
không có tính hệ thống (non-systematic) và không theo thể thức (ad-hoc).
Trong ngữ cảnh này, khái niệm “sự tương tự” xuất hiện ở nhiều dạng, diễn
xuất, và nhiều ứng dụng.
Khái niệm “sự tương tự” có nhiều dạng khác nhau. Bất chấp những
khác biệt, chúng đều có điểm chung: “sự tương tự” được sử dụng để so sánh
hai (hay nhiều) đối tượng, hai hoàn cảnh, hai vấn đề, v.v… với nhiều nguyên
do khác nhau. Luôn có mục đích nào đó với một phép so sánh như thế, bởi vì
một hành động tiếp sau đó được thực hiện và cuối cùng thì một vấn đề nào đó
phải được giải quyết. Vì lý do đó, hai đối tượng được đem so sánh giữ những
vai trò khác nhau. Đối tượng thứ nhất đang được xem xét và được gọi là vấn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31
đề (problem). Đối tượng thứ hai là đã biết và đã lưu; thường được gọi là bản
mẫu (prototype) hay tình huống (case).
- Trong diễn xuất hình ảnh (Image Interpretation), các hình ảnh được diễn
xuất theo ý nghĩa của chúng và chúng được so sánh với nhau. Ví dụ, một ảnh
y khoa thực tế và một ảnh không có bệnh lý nào đó được so sánh với nhau; độ
tương tự giữa những ảnh này được sử dụng để cho biết ảnh thực kia có chứa
bệnh lý hay không. Xác minh hình ảnh (Image Identification) cũng thuộc về
lĩnh vực này.
- Trong tâm lý học nhận thức và xã hội (Cognitive and Social Psychology),
“sự tương tự” là cái gì đó chủ quan; ám chỉ thái độ, giá trị, sở thích, và cá tính
giữa những con người tương xứng mức độ nào. Có nhiều dạng mô hình về sự
tương tự trong tâm lý học, bốn mô hình nổi bật là hình học (geometric), đặc
tính (featural), dựa trên canh lề (alignment-based), và biến đổi
(transformational).
- Trong lĩnh vực an ninh, quốc phòng để xác định đối tượng ảnh khi muốn xác
định vân tay, kiểm tra những băng đĩa mang những nội dung cần kiểm soát...
Độ đo tương tự là một trong những phương pháp tốt để máy tính phân
biệt được các hình ảnh qua nội dung của chúng. Thông thường hệ thống
CBIR(content-based image retrieval) sẽ truy vấn hình ảnh bằng phương pháp
đo tương tự dựa trên các chức năng, việc xác định nó có thể dưới nhiều hình
thức như phát hiện biên, màu sắc, vị trí điểm ảnh… các phương pháp như
histogram, màu sắc và phân tích histogram dòng cột sử dụng biểu đồ để xác
định độ tương tự.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
Chƣơng 2:
MỘT SỐ PHƢƠNG PHÁP XÁC ĐỊNH ĐỘ ĐO TƢƠNG TỰ
2.1. Độ đo dựa trên khoảng cách
2.1.1. Độ đo khoảng cách min – max
Được thực hiện dựa trên ý tưởng lấy phần giao của hai lược đồ cần so
sánh, ta sẽ được một lược đồ, tính tổng các giá trị có được từ lược đồ này cho
ta được độ đo min – max
Đối với độ đo min: ta tính dựa vào giá trị min tại mỗi K bin
Intersection (h(I), h(M) =
K
j 1
h(M)[j]}{h(I)[j],min
Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi K bin
Intersection (h(I), h(M) =
K
j 1
h(M)[j]}{h(I)[j],max
Matching(h(I),h(M)) =
ii
iMhiIh
MhIhtionInter
])[(,])[(max
))(),((sec
2.1.2. Độ đo khoảng cách Euclid
Đây là cách tính khoảng cách Euclid thông thường giữa các K bin:
Intersection (h(I), h(M) =
K
j 1
2h(M))-(h(I)
Hoặc có thể là:
Intersection (h(I), h(M) =
K
j
MhIh
1
)()(
2.1.3. Độ đo khoảng cách toàn phương:
Intersection (h(I), h(M) =
K
j
K
j
ij jhihajhih
1 1
)]()([)()([
2.2. Độ đo sử dụng trọng số
2.2.1. Độ đo có trọng số:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33
dhist(I,Q) = (h(I) – h(Q))
T
A(h(I) – h(Q))
trong đó, h(I) và h(Q) là những lược đồ tương ứng của ảnh I và Q và A là ma
trân đồng dạng K x K. Trong ma trận này, những màu mà rất giống nhay thì
gần với giá trị một còn những màu khác nhau thì sẽ cí giá trị gần với không.
2.2.2. Độ đo hỗn hợp
Một trong các độ đo hỗn hợp (độ đo MSM) được đưa ra bởi Goodall [1].
Để tính độ đo giống nhau giữa các đối tượng, đầu tiên ta tính độ đo cho từng
thuộc tính, sau đó kết hợp lại.
Dưới đây ta sẽ lần lượt xét các độ đo cho từng loại thuộc tính liên tục và
rời rạc. Ngoài ra, ta cũng xét độ đo cho loại thuộc tính thứ tự trên thuộc tính
rời rạc.
2.2.2.1. Thuộc tính rời rạc
Loại thuộc tính đầu tiên mà ta xét là thuộc tính rời rạc. Các giá trị khác
nhau thuộc tính không thể được so sánh. Ta coi cặp các giá trị khác nhau có
độ giống nhau bằng 0; cặp các giá trị trùng nhau có độ giống nhau khác 0 và
phụ thuộc vào xác suất xuất hiện của cặp giá trị đó. Cặp giá trị trùng nhau có
xác suất xuất hiện nhỏ hơn sẽ có độ giống nhau lớn hơn.
Kí hiệu Vi là các giá trị khác nhau của thuộc tính. Xác suất xuất hiện của
các giá trị này là
1,1,
1
n
i
ii pnip
. Kí hiệu Sij là độ giống nhau của cặp giá
trị Vi và Vj, ta có:
0
0
ij
ij
i j S
i j S
ngoài ra,
i k ij kli j k l p p S S
Gọi Pij là xác suất xuất hiện một cặp giá trị có độ giống nhau lớn hơn
cặp (Vi, Vj). Dễ thấy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
2 ,
1,
k
k Q
ij
p i j
P
i j
trong đó
: k iQ k p p
Từ đó, suy ra
21 ,
1
0,
k
k Q
ij ij
p i j
S P
i j
với Q được xác định theo công thức ở trên.
Trong thực tế, các giá trị xác suất pi là không biết trước nhưng ta có thể
xấp xỉ các giá trị này bằng tần suất xuất hiện của chúng trong tập mẫu. Gọi m
là số lượng các phần tử trong tập mẫu và fi là tần suất của giá trị Vi, độ đo
giống nhau có thể được tính xấp xỉ bởi
1
1 ,
1
0,
k k
ij k Q
f f
i j
S m m
i j
trong đó
: k iQ k f f
2.2.2.2. Thuộc tính có thứ tự
Trong trường hợp này, ta cần phải tính tới tính có thứ tự trong độ đo
giống nhau.
Do có tính thứ tự nên thông thường một cặp giá trị sẽ có độ giống nhau
nhỏ hơn so với các cặp giá trị nằm giữa chúng. Ví dụ, ta nói cặp (B, C) sẽ có
độ giống nhau lớn hơn cặp (A, C) và (B, E). Tuy nhiên, ta không thể có sự so
sánh như vậy với hai cặp (A, C) và (B, E). Trong trường hợp này, chúng ta lại
sử dụng đến xác suất xuất hiện của các giá trị.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
Giả sử các giá trị của thuộc tính là
1 2, ,..., nV V V
. Theo cách hiểu thông
thường và lập luận ở trên, ta có
i k ij kli j k l p p S S
ij kli j k l S S
ij ik jk iki j k S S S S
và
j l
t t ij kl
t i t k
i j k l p X S S
j l
t t ij kl
t i t k
i j k l p X S S
Xác suất
ijP
để xuất hiện một cặp có độ giống nhau hơn cặp
,i jV V
là
2 ,ij k
k Q
P p i j
với
: k iQ k p p
và 1
2
1 1 1
2 ,
n n
ij k k l
k k l k
P p p p i j
trong đó
là số thoả mãn
1j
t t t
t k t i t k
p p p
Trong trường hợp phải tính xấp xỉ, ta sử dụng công thức
1
1 1 1
1
,
1
1
2 ,
1 1
i i
k Q
ij
n n
i i k l
k k l k
f f
i j
m m
P
f f f f
i j
m m m m
2.2.2.3. Thuộc tính liên tục
Với thuộc tính liên tục, ta sẽ sử dụng khoảng cách – trị tuyệt đối của hiệu
của hai giá trị – làm tiêu chuẩn chính trong việc đo độ giống nhau. Cặp của
hai giá trị trùng nhau thì có độ giống nhau lớn hơn cặp của hai giá trị khác
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
nhau; cặp có khoảng cách nhỏ hơn sẽ giống nhau hơn cặp có khoảng cách lớn
hơn. Và khi các cặp có cùng khoảng cách ta sẽ sử dụng đến xác suất.
Ta có:
i j k l ij kl
j l
i j k l t t ij kl
t i t k
j l
i j k l t t ij kl
t i t k
V V V V S S
V V V V p p S S
V V V V p p S S
Tương tự, xác suất Pij là
2 2
i
jk i i t
i Q t T
P p p p
trong đó
: 1i jQ i j k p p i n
và
:
t i k j
k ti
t i k j u u
u j u i
V V V V
T t i t n
V V V V p p
Công thức để tính gần đúng độ giống nhau trong trường hợp này:
1
1 2
1
i
jk i i i t
i Q t T
P f f f f
m m
2.2.2.4. Kết hợp độ đo của các thuộc tính
Trong các phần trên ta đã xét độ giống nhau cho từng thuộc tính riêng rẽ.
Độ đo giống nhau cho cặp hai đối tượng sẽ được kết hợp từ các độ đo này. Để
có thể kết hợp được, ta phải giả sử là các giá trị của các thuộc tính của một
đối tượng là độc lập với nhau.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
Kí hiệu Og và Oh là hai đối tượng cần tính độ giống nhau và
k
ghP
là xác
suất xuất hiện cặp giá trị của thuộc tính k có độ giống nhau lớn hơn cặp
,k kg hv v
. Ta định nghĩa quan hệ giữa hai đối tượng như sau:
1 1
t t
k k
gh ij gh ij
k k
P P S S
trong đó t là số lượng thuộc tính và
S
là kí hiệu chỉ độ giống nhau giữa
hai đối tượng. Nếu kí hiệu
1 gh ghP S
là xác suất xuất hiện một cặp đối tượng
có độ giống nhau lớn hơn cặp (Og, Oh), thì tương tự như đối với thuộc tính
riêng rẽ, ta có:
1 1
t t
k l
gh i j
Q k l
p pP
trong đó
k
ip
là xác suất xuất hiện giá trị thứ i của thuộc tính thứ k và Q là tập
tất cả các cặp đối tượng (Oi, Oj) thoả mãn
1 1
t t
k k
ij gh
k k
P P
Việc tính chính xác
S
theo công thức trên yêu cầu số lượng tính toán rất
lớn và trong thực tế người ta thường tính xấp xỉ nó bằng các phân bố của
Fisher và Lancaster như sau
2 22
0
1 2
!
i
t
i
e
i
P
trong đó
1d ct t t
và
2 2 2
d c
, với
2
1
2 ln
ct
k
c
k
P
cho các thuộc tính liên tục (phân bố Fisher) và
' '
2
'
1
ln ln
2 1
dt k k k k
d k
k k
P P P P
P P
cho thuộc tính rời rạc (phân bố Lancaster).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
2.2.2.5. Thuật toán nhanh cho thuộc tính liên tục
Để tính độ đo giống nhau trong trường hợp thuộc tính liên tục, ta cần
phải duyệt qua các xác suất xuất hiện của giá trị của thuộc tính. Do đó, độ
phức tạp tính toán trong trường hợp này là
( )n
, với n là số lượng giá trị.
Trong trường hợp thuộc tính liên tục (số), nếu tính trực tiếp theo công
thức MSM như C. Li và G. Biswas [2] đề nghị thì độ phức tạp tính toán trong
trường hợp xấu nhất là
2( )n
. Chúng tôi đã đề xuất cách tính gián tiếp độ đo
cho kết quả hoàn toàn trùng khớp những chỉ với độ phức tạp tính toán là
( )n
như nêu trong [3, 4, 5].
Ý tưởng chính của phương pháp này là không tính trực tiếp độ đo theo
công thức
2 2
i
jk i i t
i Q t T
P p p p
trong đó T là tập các chỉ số t (
k t n
) thoả mãn
t i k jV V V V
hoặc
k t
t i k j u u
u j u i
V V V V p p
mà tính gián tiếp thông qua
1jk jkS P
. Ta chỉ cần quan tâm đến trường hợp
j k
, bời vì khi j = k thì
2
jk i
i Q
P p
, với
: i kQ i p p
và tính Pjk với độ phức tạp tuyến tính.
Dễ thấy,
1
1 2 ,
i
n
jk jk i t
i t T
S P p p j k
với
iT
là tập
:
k t
i t i k j t i k j u u
u j u i
T t V V V V V V V V p p i t n
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
Ta có thể viết
iT
ở dạng đơn giản hơn như sau
0:i i iT t t t n T
trong đó
it
là giá trị nhỏ nhất còn thoả mãn
t i k jV V V V
và
0
iT
là tập chỉ số
t thoả mãn
k t
t i k j u u
u j u i
V V V V p p
. Chú ý rằng
0
iT
hoặc là rỗng hoặc
chỉ có một phần tử.
Công thức tính Sjk còn có thể biến đổi như sau
1
2 1 ,
n
jk i i
i
S p s j k
trong đó, 0 1
1
i it T
i t
t
s p
Tính Sjk theo công thức này ta có thể tận dụng si tính được trong bước
trước. Dưới đây là thuật toán với độ phức tạp tuyến tính.
Một số kí hiệu trong thuật toán
sij: độ đo giống nhau của cặp giá trị (Vi, Vj).
sumij: tổng các tần xuất từ i tới j.
dij: trị tuyệt đối của hai giá trị Vi và Vj.
beforek: tổng các tần xuất từ 1 tới k – 1.
sumt: tổng các tần xuất 1 tới t.
f[k]: tần xuất của giá trị thứ k.
n: số lượng giá trị của thuộc tính.
Thuật toán (cho trường hợp
i j
)
t = 1; beforek = 0.0; sumt = 0.0; sij = 0.0; sumij = 0.0;
dij = abs(v[j] – v[i]);
for k = i to j do
sumij = sumij + f[k];
for k = 1 to n do {
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
if (v[k] + dij <= v[n]) {
if (k > 1)
beforek = beforek + f[k-1];
while (t <= n and abs(v[t] – v[k] <= dij)) {
sumt = sumt + f[t];
t = t + 1;
}
sij = sij + 2 * f[k] * (1 – sumt);
if (abs(v[t – 1] – v[k]) = dij and sumt – beforek <= dij)
sij = sij + 2 * fk * f[t – 1];
}
}
2.2.2.6. Thuật toán nhanh cho thuộc tính có thứ tự
Áp dụng phương pháp tương tự như đối với thuộc tính liên tục, ta cũng
có thể tính độ đo giống nhau cho thuộc tính có thứ tự với độ phức tạp tuyến
tính.
Trước hết ta viết lại biểu thức tính Pij dưới dạng
1
2
1 1 1
1
2
1 1
1
2
1
2
2
2
n n
ij k k l
k k l k
n
n k k l
k l k
n
n k l k
k l k
P p p p
p p p p
p p p p
trong đó
thoả mãn
1
1
j
t t t
t k t i t k
k p p p
.
Ta có thể viết lại
1
2
n
ij k l k
k l k
P p p p
với
bây giờ có thể nhận thêm giá trị k.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41
Sử dụng các kí hiệu như trên, thuật toán tính nhanh cho thuộc tính có
Các file đính kèm theo tài liệu này:
- 10LV09_CNTT_KHMTTranQuangHuy.pdf