Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 1

Trang 1

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 2

Trang 2

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 3

Trang 3

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 4

Trang 4

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 5

Trang 5

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 6

Trang 6

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 7

Trang 7

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 8

Trang 8

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 9

Trang 9

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân trang 10

Trang 10

Tải về để xem bản đầy đủ

pdf 27 trang nguyenduy 16/04/2024 1130
Bạn đang xem 10 trang mẫu của tài liệu "Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

Tóm tắt nội dung tài liệu: Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân

Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân
¥y S-Tree (M.A. Nascimento, 2002 ) là c¥y nhi·u nh¡nh c¥n b¬ng theo chi·u cao.
Méi nút trong c¥y S-Tree gồm nhi·u chú ký li¶n k¸t đến c¡c nút con. Méi ph¦n tû cõa
nút l¡ gồm chú ký và định danh cõa đối tưñng.
2.6. C¥y Sig-Tree
2.6.1. Giới thi»u c¥y Sig-Tree
 Méi nút trong c¥y Sig-Tree gồm hai thành ph¦n để li¶n k¸t đến nút cha và li¶n k¸t
đến c¡c nút con. Ph¦n này thi¸t k¸ c§u trúc và c¡c thao t¡c tr¶n c¥y Sig-Tree gồm:
ch±n nút, lo¤i bỏ nút, t¡ch nút và t¼m ki¸m tr¶n c¥y.
2.6.2. Thi¸t k¸ c§u trúc dú li»u c¥y Sig-Tree
 Méi nút trong c¥y Sig-Tree có hai ph¦n: (1) Ph¦n li¶n k¸t đến nút cha gồm chú
ký tê hñp và ph¦n li¶n k¸t v· nút cha: hsignature; parenti; (2) Ph¦n nëi dung là tªp
c¡c chú ký và li¶n k¸t đến nút con: fSIGi = hsignaturei; nextiiji = 1; :::; kg. Méi nút
l¡ cũng gồm hai ph¦n: ph¦n li¶n k¸t nút cha hsignature; parenti và ph¦n nëi dung
fSIGi = hsignaturei; oidiiji = 1; :::; kg là tªp chú ký nhị ph¥n và định danh.
 4
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
2.6.3. Ph²p tê hñp c¡c chú ký tr¶n c¥y Sig-Tree
 Trong c¥y Sig-Tree, méi chú ký cõa nút cha là tê hñp c¡c chú ký cõa nút con. N¸u
c¡c thành ph¦n cõa nút con thay đổi th¼ ph£i tê hñp l¤i c¡c chú ký cõa nút cha và
thực hi»n cho đến nút gèc. Thuªt to¡n tê hñp chú ký được đề xu§t như sau:
Thuªt to¡n 2.5. Tê hñp chú ký
Input: Nút v c¦n tê hñp.
Output: C¥y Sig-Tree sau khi tê hñp.
Function UnionSignature(v)
 Begin
 if v ! parent 6= null then
 Signature = _(SIGi ! sig); SIGi 2 v;
 v ! parent ! (SIGi ! sig) = Signature; UnionSignature(v ! parent);
 end if
 Return Sig-Tree; End. =0
M»nh đề 2.3. Độ phùc t¤p cõa Thuªt to¡n 2.5 là O(k log n), với n là sè chú ký
tr¶n c¥y, k là chi·u dài chú ký.
2.6.4. Ph²p t¡ch mët nút tr¶n c¥y Sig-Tree
 K¸t qu£ cõa ph²p t¡ch nút là hai cụm chú ký rời nhau tương ùng với hai nút trong
c¥y Sig-Tree. Vi»c t¡ch nút làm cho c¥y Sig-Tree t«ng trưởng theo hướng gèc. Thuªt
to¡n t¡ch nút được đề xu§t như sau:
Thuªt to¡n 2.6. T¡ch nút
Input: Tªp c¡c chú ký S cõa nút c¦n t¡ch, chú ký α và β.
Output: Hai nút đã được t¡ch gồm NodeA và NodeB.
Function SplitNode(S, α, β)
 Begin
 NodeA = {α}; NodeB = {β;}
 for si 2 S do
 T½nh đë đo d(α; si) và d(β; si);
 if d(α; si) < d(β; si) then Ch±n si vào NodeA
 else Ch±n chú ký si vào NodeB;
 end if
 end for
 Return {NodeA, NodeB};
 End. =0
 5
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
Thuªt to¡n 2.7. T¡ch nút trong c¥y Sig-Tree
Input: Nút c¦n t¡ch v.
Output: C¥y Sig-Tree sau khi được t¡ch.
Function SplitTree(v)
 Begin
 T¤o tªp chú ký S cõa nút v; Tr½ch xu§t hai chú ký α, β cõa nút v;
 {NodeA, NodeB} = SplitNode(S, α, β);
 T¤o hai chú ký tê hñp SigA, SigB cõa NodeA, NodeB;
 G¡n vparent là nút cha cõa nút v;
 if (v ! parent == null) then Root = fSigA; SigBg
 else Bê sung chú ký SigA, SigB vào nút vparent; UnionSignature(v ! parent);
 if (vparent đầy) SplitTree(v ! parent); end if
 end if
 Return Sig-Tree; End. =0
M»nh đề 2.4. Độ phùc t¤p cõa Thuªt to¡n 2.6 là O(M), với M là sè chú ký.
M»nh đề 2.5. Độ phùc t¤p cõa Thuªt to¡n 2.7 là O(k(log n)2 + M log n), với
M; n; k l¦n lượt là sè chú ký tèi đa cõa nút, sè chú ký tr¶n c¥y, chi·u dài chú ký.
2.6.5. Ph²p lo¤i bỏ chú ký tr¶n c¥y Sig-Tree
 Vi»c lo¤i bỏ mët nút trong c¥y d¨n đến ph£i lo¤i bỏ mët ph¦n tû tương ùng cõa
nút cha. N¸u nút cha sau khi lo¤i bỏ có sè ph¦n tû ½t hơn sè lượng tèi thiºu th¼ ph£i
lo¤i bỏ luôn nút cha và thu gom c¡c chú ký t¤i nút l¡ theo nút cha này và thực hi»n
thao t¡c ch±n trở l¤i. Mët gi£i ph¡p đề xu§t là thực hi»n g¡n định danh đối tượng
oid = null n¸u như mët nút l¡ sau khi lo¤i bỏ có sè lượng ph¦n tû nhỏ hơn sè lượng
tèi thiºu. Khi thực hi»n thao t¡c ch±n chú ký t¤i mët nút l¡, n¸u sè lượng ph¦n tû có
oid 6= null nhi·u hơn sè lượng tèi thiºu th¼ thực hi»n lo¤i bỏ c¡c ph¦n tû có oid = null.
Thuªt to¡n 2.8. Lo¤i bỏ chú ký
Input: Chú ký Sig và nút l¡ v, sè chú ký tèi thiºu m.
Output: C¥y Sig-Tree sau khi lo¤i bỏ chú ký.
Function DeleteNode(Sig; v; m)
 Begin
 Khởi t¤o SIG = v:SIG sao cho v:SIG = Sig;
 if (v:count > m) then Lo¤i bỏ ph¦n tû SIG; UnionSignature(v)
 else v:SIG ! oid = null;
 end if
 Return Sig-Tree; End. =0
 6
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
M»nh đề 2.6. Độ phùc t¤p cõa Thuªt to¡n 2.8 là O(k log n), với n là sè chú ký
tr¶n c¥y, k là chi·u dài chú ký.
2.6.6. Ph²p ch±n chú ký tr¶n c¥y Sig-Tree
 Méi l¦n ch±n chú ký vào nút l¡ thực hi»n đếm sè ph¦n tû kh¡c trèng, n¸u vượt
qua sè lượng tèi thiºu th¼ lo¤i bỏ c¡c ph¦n tû trèng này. N¸u nút l¡ bị đầy th¼ t¡ch
nút theo Thuªt to¡n 2.7. Thuªt to¡n ch±n chú ký được đề xu§t như sau:
Thuªt to¡n 2.9. Ch±n chú ký
Input: Chú ký Sig và nút v.
Output: C¥y Sig-Tree sau khi ch±n nút.
Function InsertNode(Sig, v)
 Begin
 if (v là nút l¡) then
 Ch±n chú ký Sig vào nút v;
 if (sè lượng ph¦n tû nút v > m) then Lo¤i bỏ c¡c nút trèng; end if
 UnionSignature(v);
 if (nút v đầy) then SplitTree(v); end if
 else
 Chọn SIG 2 v : độ đo d(SIG:Sig; Sig) nhỏ nh§t;
 v = SIG ! next; InsertNode(v);
 end if
 Return Sig-Tree; End. =0
M»nh đề 2.7. Độ phùc t¤p cõa Thuªt to¡n 2.9 là O(k(log n)2 + M log n), với
M; n; k l¦n lượt là sè chú ký tèi đa cõa nút, sè chú ký tr¶n c¥y, chi·u dài chú ký.
2.6.7. T¼m ki¸m tr¶n c¥y Sig-Tree
 Luªn ¡n mô t£ vi»c t¼m ki¸m dựa tr¶n c§u trúc STACK tr¶n c¥y Sig-Tree như sau:
Thuªt to¡n 2.10. T¼m ki¸m £nh tr¶n c¥y Sig-Tree
Input: Chú ký t¼m ki¸m Sig và c¥y Sig-Tree.
Output: Tªp SigOid = fhsigi; oidii ji = 1; : : : ; pg.
Function STreeRetrieval(Sig, Sig-Tree)
 Begin
 Khởi t¤o:
 v = Root;
 SigOid = ; ; STACK = ;;
 while (not Empty(STACK )) do
 7
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 v = Pop(STACK );
 if (v không ph£i nút l¡) then
 Chọn SIG0 2 v: d(SIG0 ! sig; Sig) nhỏ nh§t;
 Push(STACK, Sig0 ! next)
 else SigOid = SigOid [ fhv ! sigi; v ! oidii ji = 1;:::; jvjg;
 end if
 end while
 Return SigOid; End. =0
M»nh đề 2.8. Độ phùc t¤p cõa Thuªt to¡n 2.10 là O(M log n), với M là sè chú
ký tèi đa cõa nút tr¶n c¥y, n là sè chú ký tr¶n c¥y.
2.7. Thực nghi»m t¼m ki¸m £nh dựa tr¶n c¥y Sig-Tree
 Sè li»u B£ng 2.2 cho th§y thời gian t¼m ki¸m trung b¼nh tr¶n tªp dú li»u £nh
COREL là 26,813 milli gi¥y, tr¶n tªp £nh dú li»u WANG là 692,947 milli gi¥y và tr¶n
tªp dú li»u £nh ImgColl01 là 2423,780 milli gi¥y.
 H¼nh 2.14. Hi»u su§t t¼m ki¸m tr¶n c¥y Sig-Tree cõa tªp £nh COREL
 H¼nh 2.15. Hi»u su§t t¼m ki¸m tr¶n c¥y Sig-Tree cõa tªp £nh WANG
 8
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 H¼nh 2.16. Hi»u su§t t¼m ki¸m tr¶n c¥y Sig-Tree cõa tªp £nh ImgColl01
 B£ng 2.2. Đánh gi¡ hi»u su§t giúa c¡c phương ph¡p tr¶n c¡c tªp dú li»u £nh
 B£ng 2.3. So s¡nh hi»u su§t t¼m ki¸m giúa c¡c phương ph¡p
 K¸t qu£ thực nghi»m được so s¡nh với c¡c phương ph¡p kh¡c đã công bè tr¶n tªp
dú li»u £nh COREL. Sè li»u so s¡nh tø B£ng 2.3 cho th§y phương ph¡p t¼m ki¸m
£nh theo nëi dung dựa tr¶n chú ký nhị ph¥n và c¥y Sig-Tree có thời gian t¼m ki¸m
nhanh hơn và độ ch½nh x¡c không k²m hơn c¡c phương ph¡p kh¡c.
2.8. Têng k¸t chương
 Chương 2 đã ti¸p cªn phương ph¡p t¼m ki¸m £nh dựa tr¶n chú ký nhị ph¥n và
c¥y Sig-Tree. K¸t qu£ thực nghi»m cho th§y phương ph¡p đ· xu§t là gi£i ph¡p hi»u
qu£ để t¼m ki¸m £nh theo nëi dung. Tuy nhi¶n, qu¡ tr¼nh truy t¼m cụm phụ thuëc vào
c¡c mùc tr¶n c¥y và ph²p t¡ch gh²p có thº £nh hưởng tr¶n toàn bë c¥y Sig-Tree. V¼
vªy, luªn ¡n thực hi»n c£i ti¸n phương ph¡p b¬ng c¡ch ph¥n cụm dựa tr¶n c§u trúc
đồ thị nh¬m t«ng độ ch½nh x¡c t¼m ki¸m £nh.
 9
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
Chương 3. ĐỀ XUẤT PHƯƠNG PHÁP TÌM KIẾM ẢNH
 DỰA TRÊN ĐỒ THỊ CHỮ KÝ
3.1. Giới thi»u
 Chương này x¥y dựng c§u trúc đồ thị S-kGraph và m¤ng Sig-SOM tr¶n cơ sở gom
cụm chú ký nhị ph¥n. Tø đó, luªn ¡n tr¼nh bày c¡c thuªt to¡n và thực nghi»m cho
phương ph¡p t¼m ki¸m £nh dựa tr¶n chú ký nhị ph¥n.
3.2. Chú ký nhị ph¥n cõa h¼nh £nh
Định nghĩa 3.1. Chú ký nhị ph¥n cõa đối tượng đặc trưng O tr¶n £nh I là mët chuéi
 O O O O O
bit SigI = b1 b2 :::bN , sao cho bi = 1 n¸u khèi thù i cõa £nh I và vùng đặc trưng O có
 O
di»n t½ch giao nhau lớn hơn ngưỡng θ cho trước, bi = 0 n¸u ngược l¤i; với N = n × k
là sè lượng c¡c khèi £nh.
 O O O O C C C C
Định nghĩa 3.2. Gọi SigI = b1 b2 :::bN và SigI = b1 b2 :::bM l¦n lượt là chú ký nhị
ph¥n đối tượng và chú ký nhị ph¥n màu s­c. Khi đó, chú ký nhị ph¥n cõa h¼nh £nh I
được định nghĩa là:
 O O O O O C C C
 Sig(I) = SigI ⊕ SigI = b1 b2 :::bN b1 b2 :::bM (3.1)
 Chú ký nhị ph¥n cõa h¼nh £nh gồm: (1) d¢y N-bit mô t£ chú ký nhị ph¥n đối
tượng; (2) d¢y M-bit mô t£ chú ký nhị ph¥n màu s­c (đã tr¼nh bày ở Chương 2).
3.3. Độ đo tương tự
 O C O C
Định nghĩa 3.3. Gọi Sig(I) = SigI ⊕ SigI và Sig(J) = SigJ ⊕ SigJ l¦n lượt là chú
ký nhị ph¥n cõa hai h¼nh £nh I và J. Độ đo tương tự cõa đối tượng đặc trưng và màu
 O O C C
s­c là µO(sigI ; sigJ ) và µC (sigI ; sigJ ) được x¡c định như sau:
 N
 O O 1 P O O
 µO(sigI ; sigJ ) = N (sigI [i]XORsigJ [i]) (3.2)
 i=1
 M
 C C 1 P C C
 µC (sigI ; sigJ ) = M (sigI [i]XORsigJ [i]) (3.3)
 i=1
M»nh đề 3.1. Độ tương tự µα trong Định nghĩa 3.3 (với α 2 fO; Cg) là mët
kho£ng c¡ch trong không gian metric.
Định nghĩa 3.4. Cho hai h¼nh £nh I và J l¦n lượt có chú ký nhị ph¥n là Sig(I) =
 O C O C
SigI ⊕ SigI và Sig(J) = SigJ ⊕ SigJ . Độ đo tương tự giúa hai h¼nh £nh I và J được
định nghĩa:
 O O C C
 φ(I;J) = α×(µO(sigI ; sigJ ))+β×(µC (sigI ; sigJ )) (3.4)
với α; β 2 (0; 1) là c¡c h» sè điều ch¿nh và α + β = 1.
 10
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
M»nh đề 3.2. Độ đo tương tự φ(I;J) trong Định nghĩa 3.4 là mët kho£ng c¡ch
trong không gian metric.
3.4. T¼m ki¸m £nh dựa tr¶n gom cụm chú ký nhị ph¥n
3.4.1. Gom cụm chú ký nhị ph¥n
 Méi ph¦n tû gồm chú ký nhị ph¥n sig và định danh oid. Ph¦n tû hsig; oidi được
ph¥n bè vào mët cụm n¸u kho£ng c¡ch d đến t¥m cụm này là ng­n nh§t và nhỏ hơn
ngưỡng θ. N¸u kho£ng c¡ch d lớn hơn θ th¼ ph¦n tû hsig; oidi t¤o mët t¥m cụm mới.
Thuªt to¡n 3.1. Gom cụm chú ký nhị ph¥n
Input: Ngưỡng tương tự θ và tªp chú ký h¼nh £nh Γ.
Output: Tªp c¡c cụm Ω.
Function SignatureClustering(θ, Γ)
 Begin
 Khởi t¤o Ω = ;;
 for hsig; oidi 2 Γ do
 if (Ω = ;) then Khởi t¤o cụm V0 với t¥m hsig; oidi
 else T¼m Vk 2 Γ: φ(sig; sigk) = minφ(sig; sigi); i = 1; : : : ; m; end if
 if (φ(sig; sigk) < θ) then Vk = Vk [ fhsig; oidig; Cªp nhªt l¤i t¥m cụm;
 else T¤o mới cụm V có t¥m hsig; oidi; Bê sung tªp cụm Ω = Ω [ V ; end if
 end for
 Return Ω; End. =0
M»nh đề 3.3. Độ phùc t¤p cõa Thuªt to¡n 3.1 là O(N 2), với N là sè lượng ph¦n
tû cõa tªp chú ký Γ.
3.4.2. Thuªt to¡n t¼m ki¸m £nh
 Qu¡ tr¼nh t¼m ki¸m £nh đưñc thực hi»n b¬ng c¡ch chọn ra cụm có t¥m g¦n nh§t
với h¼nh £nh tra cùu. N¸u kho£ng c¡ch này nhỏ hơn ngưỡng θ th¼ thực hi»n tr½ch xu§t
c¡c định danh oid trong tªp cụm và s­p x¸p theo độ đo tương tự. Thuªt to¡n t¼m
ki¸m £nh được đề xu§t như sau:
Thuªt to¡n 3.2. T¼m ki¸m £nh
Input: Chú ký £nh sig, tªp cụm Ω và ngưỡng t¼m ki¸m θ.
Output: Tªp c¡c định danh £nh tương tự Ψ.
Function ClusterRetrieval(sig, Ω, θ)
 Begin
 Khởi t¤o Ψ = ;; T¼m cụm Vk : φ(sig; sigk) = minφ(sig; sigi); i = 1; ::; m;
 11
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 if (φ(sig; sigk) < θ) then Chọn cụm Vk 2 Ω để truy hồi h¼nh £nh tương tự; end if
 Thực hi»n tra cùu £nh tương tự;
 Return Ψ; End. =0
M»nh đề 3.4. Độ phùc t¤p cõa Thuªt to¡n 3.2 là O(m), với m là sè lượng cụm.
3.4.3. Thực nghi»m t¼m ki¸m £nh dựa tr¶n gom cụm
 H¼nh 3.2. Mô h¼nh t¼m ki¸m £nh dựa tr¶n gom cụm chú ký nhị ph¥n
 H¼nh 3.9. Hi»u su§t t¼m ki¸m dựa tr¶n gom cụm tªp £nh CBIRimages
3.5. X¥y dựng đồ thị S-kGraph
3.5.1. C§u trúc đồ thị S-kGraph
Định nghĩa 3.5. Đồ thị chú ký là đồ thị vô hướng SG = (V; E), trong đó, tªp c¡c
đỉnh V và tªp c¡c c¤nh E được định nghĩa như sau:
 V = fvI = hsigI ; oidI ijI 2 =g (3.6)
 E = fhvI ; vJ ijφ(I;J) ≤ θ; 8I;J 2 =g (3.7)
với I, J là hai h¼nh £nh trong tªp £nh =; φ(I;J) là độ đo tương tự; θ là gi¡ trị ngưỡng.
 Ph¦n này x¥y dựng đồ thị S-kGraph với méi đỉnh là mët cụm dựa tr¶n độ đo φ.
Định nghĩa 3.6. Mët cụm V có t¥m I được định nghĩa:
 V = fJjφ(I;J) ≤ kθ; J 2 =g (3.8)
với kθ là b¡n k½nh cụm V , = là tªp dú li»u £nh, k 2 N ∗.
 12
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 H¼nh 3.10. Hi»u su§t t¼m ki¸m dựa tr¶n gom cụm tªp £nh COREL và WANG
 B£ng 3.4. Hi»u su§t t¼m ki¸m trung b¼nh dựa tr¶n gom cụm c¡c tªp £nh
 B£ng 3.5. So s¡nh độ ch½nh x¡c t¼m ki¸m tr¶n tªp £nh COREL
 Cho trước tªp Ω = fViji = 1; :::; ng là tªp c¡c cụm rời nhau, đồ thị S-kGraph được
định nghĩa như sau:
Định nghĩa 3.7. Đồ thị S-kGraph=(VSG;ESG) là mët đồ thị vô hướng, trong đó tªp
đỉnh VSG = Ω và tªp c¤nh ESG được x¡c định như sau:
 ESG = fhVi;Vjiji 6= j; Vi;Vj 2 VSG; φ(Ii0 ;Jj0 ) < kθg (3.9)
 Gọi I0 là £nh c¦n ph¥n bè vào tªp cụm rời nhau Ω. Gọi Im là t¥m cõa cụm Vm sao
cho: (φ(I0;Im) − kmθ) = minf(φ(I0;Ii) − kiθ); i = 1; :::; ng, với Ii là t¥m cõa cụm Vi.
Quy t­c 3.1. Quy t­c ph¥n bè h¼nh £nh:
 (1) N¸u φ(I0;Im) ≤ kmθ th¼ £nh I0 được ph¥n bè vào cụm Vm.
 (2) N¸u φ(I0;Im) > kmθ th¼ đặt k0 = [(φ(I0;Im) − kmθ)/θ], khi đó:
 (2.1) N¸u k0 > 0 th¼ t¤o cụm V0 t¥m I0, b¡n k½nh k0θ và Ω = Ω [ fV0g;
 13
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 (2.2) Ngược l¤i (k0 = 0), £nh I0 ph¥n bè vào cụm Vm và g¡n φ(I0;Im) = kmθ.
 Để tr¡nh xung đột dú li»u, c¡c h¼nh £nh n¸u được ph¥n bè th¼ ph£i thuëc v· mët
cụm duy nh§t. C¡c định lý sau đây chùng minh v· sự ph¥n bè duy nh§t này.
Định lý 3.1. Cho đồ thị S-kGraph=(VSG;ESG). Gọi hVi;Vji 2 ESG và Ii0 ;Jj0 l¦n lượt
là t¥m cõa Vi;Vj. Khi đó ta có:
 φ(Ii0 ;Jj0 ) > (ki0 + kj0 )θ (3.10)
với 8I 2 Vi; φ(Ii0 ;I) ≤ ki0 θ và 8J 2 Vj; φ(Jj0 ;J) ≤ kj0 θ.
Định lý 3.2. Méi £nh I ch¿ được ph¥n bè vào mët cụm duy nh§t trong tªp Ω =
fViji = 1; :::; ng.
Định lý 3.3. Với méi £nh I, gi¡ trị φ(I;Im) − kmθ ≤ 0 ch¿ x£y ra duy nh§t t¤i Im.
Định lý 3.4. Cho tªp Ω = fViji = 1; :::; ng là tªp c¡c cụm, gọi I là mët h¼nh £nh b§t
kỳ. Khi đó tồn t¤i cụm Vi0 2 Ω sao cho I 2 Vi0 .
3.5.2. Thuªt to¡n t¤o đồ thị S-kGraph
 Đồ thị S-kGraph được x¥y dựng tø tªp £nh = và ngưỡng θ theo Quy t­c 3.1.
Thuªt to¡n t¤o đồ thị S-kGraph được đề xu§t như sau:
Thuªt to¡n 3.3. T¤o đồ thị S-kGraph
Input: Tªp dú li»u £nh = và gi¡ trị ngưỡng b¡n k½nh θ.
Output: Đồ thị S-kGraph=(VSG;ESG).
Function CreateSkGraph(=,θ)
 Begin VSG = ;; ESG = ;; kI = 1; n = 1;
 for I(I 2 =) do
 if (VSG = ;) then
 n n
 I0 = I; r = kI θ; Khởi t¤o cụm Vn = fhI0 ; r; φ = 0ig; VSG = VSG [ Vn
 else
 n m i
 T¼m t¥m I0 :(φ(I;I0 ) − kmθ) = minf(φ(I;I0) − kiθ); i = 1; : : : ; ng;
 m
 if ((φ(I;I0 ) ≤ kmθ)) then
 m
 Vm = Vm [ fhI; kmθ; φ(I;I0 )ig;
 else
 m
 kI = [(φ(I;I0 ) ≤ kmθ)] ;
 if (kI > 0) then
 n+1 n+1
 I0 = I; r = kI θ; Khởi t¤o cụm Vn+1 = hI0 ; r; φ = 0i;
 n+1 i
 VSG = VSG [ Vn+1; ESG = ESG [ fhVn+1;Viijφ(I0 ;I0) ≤ kθ; i = 1; : : : ; n;
 n = n + 1;
 14
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 else
 m m
 φ(I;I0 ) = kmθ; Vm = Vm [ fhI; kmθ; φ(I;I0 )ig;
 end if
 end if
 end if
 end for Return S-kGraph; End. =0
M»nh đề 3.5. Độ phùc t¤p cõa Thuªt to¡n 3.3 là O(N), với N là sè lượng ph¦n
tû cõa tªp chú ký =.
3.5.3. Thuªt to¡n t¼m ki¸m £nh tr¶n đồ thị S-kGraph
 Thuªt to¡n 3.4. Thuªt to¡n t¼m ki¸m £nh tr¶n đồ thị S-kGraph
Input: Ảnh c¦n t¼m ki¸m IQ, đồ thị S-kGraph = (VSG;ESG), gi¡ trị ngưỡng kθ.
Output: Tªp £nh tương tự IMG.
Function SkGraphRetrieval(IQ, S-kGraph,kθ)
 Begin
 IMG = ;; V = ;;
 m i m
 φ(IQ;I0 ) = minfφ(IQ;I0); i = 1; :::; ng; V = V [ Vm, với Vm là cụm có t¥m là I0 ;
 m i
 for (Vi 2 VSG) do if(φ(I0 ;I0) ≤ kθ) then V = V [ Vi; end if end for
 j j
 for (Vj 2 V ) do IMG = IMG [ fIk;Ik 2 Vj; k = 1; :::; jVjjg; end for
 Return IMG;
 End. =0
M»nh đề 3.6. Độ phùc t¤p cõa Thuªt to¡n 3.4 là O(n), với n là sè lượng đỉnh
trong đồ thị S-kGraph.
3.5.4. Ph²p ph¥n r¢ cụm trong đồ thị S-kGraph
 Mục đích cõa vi»c ph¥n r¢ cụm nh¬m ph¥n ho¤ch l¤i c¡c cụm có b¡n k½nh qu¡ lớn.
Định lý 3.5. Thuªt to¡n t¡ch cụm V thành c¡c cụm con kh¡c réng, rời nhau C =
fV1; :::; VM g, nghĩa là V = V1 [ ::: [ VM và Vi \ Vj = ;, với i 6= j và i; j 2 f1; :::; Mg.
M»nh đề 3.7. Độ phùc t¤p cõa Thuªt to¡n 3.5 là O(m × n), với m; n là sè l¦n
ph¥n r¢ và sè lượng ph¦n tû trong cụm ph¥n r¢.
3.5.5. Thực nghi»m t¼m ki¸m £nh tr¶n đồ thị S-kGraph
 Thực nghi»m t¼m ki¸m £nh tr¶n đồ thị S-kGraph gồm hai giai đoạn: T¤o đồ thị
S-kGraph tø tªp dú li»u £nh và t¼m ki¸m tªp £nh tương tự với £nh tra cùu ban đầu.
 15
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 H¼nh 3.14. Mô h¼nh t¼m ki¸m £nh dựa tr¶n đồ thị S-kGraph
 H¼nh 3.19. Hi»u su§t t¼m ki¸m tr¶n đồ thị S-kGraph cõa tªp £nh CBIRimages
H¼nh 3.20. Hi»u su§t t¼m ki¸m tr¶n đồ thị S-kGraph cõa tªp COREL và WANG
 16
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 H¼nh 3.22. Hi»u su§t t¼m ki¸m tr¶n đồ thị S-kGraph cõa tªp £nh MSRDI
H¼nh 3.24. Hi»u su§t t¼m ki¸m tr¶n đồ thị S-kGraph cõa tªp £nh ImageCLEF
 H¼nh 3.26. Hi»u su§t t¼m ki¸m tr¶n đồ thị S-kGraph cõa tªp £nh ImgColl02
 B£ng 3.14. Hi»u su§t t¼m ki¸m tr¶n đồ thị S-kGraph cõa c¡c tªp dú li»u £nh
 17
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 B£ng 3.15. So s¡nh độ ch½nh x¡c t¼m ki¸m tr¶n tªp £nh COREL
3.6. X¥y dựng đồ thị S-kGraph dựa tr¶n m¤ng Sig-SOM
3.6.1. X¥y dựng c§u trúc m¤ng Sig-SOM
 Nh¬m c£i ti¸n qu¡ tr¼nh t¤o đồ thị S-kGraph và phương ph¡p t¼m ki¸m £nh, luªn
¡n x¥y dựng m¤ng Sig-SOM. M¤ng Sig-SOM có cơ ch¸ mở rëng đồ thị S-kGraph t¤i
t¦ng đầu ra theo như Quy t­c 3.1.
Định nghĩa 3.8. M¤ng Sig-SOM là m¤ng SOM, trong đó lớp đầu vào ùng với mët
chú ký nhị ph¥n Sig(I) = b1b2:::bN , bi 2 f0; 1g và lớp đầu ra gồm N thành ph¦n tương
ùng với c¡c cụm trong đồ thị chú ký S-kGraph = (VSG;ESG). Méi mët cụm thù j ở
t¦ng đầu ra được k¸t nèi đầy đủ với N thành ph¦n cõa t¦ng đầu vào. Méi cung k¸t nèi
tø thành ph¦n thù i cõa lớp đầu vào đến cụm thù j thuëc t¦ng đầu ra có mët trọng sè
k¸t nèi là wij 2 f0; 1g.
Định nghĩa 3.9. Gọi Sig(I) = b1:::bN là chú ký nhị ph¥n cõa £nh I và tªp SIG =
 0 0
fSig(I1 ); :::; Sig(In)g là tªp chú ký nhị ph¥n cõa c¡c t¥m cụm t¤i t¦ng đầu ra cõa
m¤ng Sig-SOM. Cụm chi¸n th­ng Vm ùng với dú li»u đầu vào Sig(I) = b1:::bN thỏa:
 0 0
 δ(I;Im) = maxfδ(I;Ii )ji = 1; :::; ng (3.12)
với δ(I;I0) = α × d (sigO; sigO) + β × d (sigC ; sigC ) và α; β 2 (0; 1); α + β = 1.
 i O I Ii C I Ii
 d (sigO; sigO) = 1 PN NOT (SigO[i]XORSigC [i])
 O I Ii N i=1 I Ii
 d (sigC ; sigC ) = 1 PM NOT (SigC [i]XORSigC [i])
 C I Ii M i=1 I Ii
 Khi đó, cụm chi¸n th­ng Vm là cụm k¸t nèi trực ti¸p với vec-tơ chi¸n th­ng Wm.
Định lý 3.6. N¸u Vm là cụm chi¸n th­ng ùng với dú li»u đầu vào Sig(I) = b1b2:::bN
 m
th¼ kho£ng c¡ch φ(I;I0 ) là ng­n nh§t, nghĩa là:
 m i
 φ(I;I0 ) = minfφ(I;I0)ji = 1; :::; jVSGjg (3.13)
 i
với I0 là t¥m cõa cụm Vi 2 VSG và φ là độ đo tương tự.
3.6.2. Thuªt to¡n hu§n luy»n m¤ng Sig-SOM
Quy t­c 3.2. Gọi Sig(I) = b1b2:::bN là chú ký nhị ph¥n cõa £nh I. Gọi Wm =
(w1m; w2m; :::; wNm) là vec-tơ trọng sè k¸t nèi t¤i thời điºm t. Quy t­c hu§n luy»n
m¤ng Sig-SOM t¤i thời điểm t + 1 ùng với dú li»u đầu vào Sig(I) = b1b2:::bN như sau:
 18
 T¼m ki¸m £nh dựa tr¶n đồ thị chú ký nhị ph¥n
 (t+1) (t)
 wi;m = bi _ wi;m (3.14)
 (t+1) (t)
 wi;j = :bi ^ wi;j (3.15)
với j 6= m và j = 1; :::; n
 (t)
Định lý 3.7. Đặt Sig(I) = b1:::bN là dú li»u đầu vào, Wm = (w1m; :::; wNm) là vec-tơ
trọng sè k¸t nèi t¤i thời điểm t. Ta có:
 (t) (t+1)
 δ(Sig(I);Wm ) ≤ δ(Sig(I);Wm ) (3.16)
 Thuªt to¡n 3.6. Thuªt to¡n hu§n luy»n m¤ng Sig-SOM
Input: Tªp hu§n luy»n Γ = fSig(Ii) = (bi1; bi2; :::; biN )ji = 1; :::; Kg.
Output: M¤ng Sig-SOM sau khi đã hu§n luy»n.
Function SigSOMTraining(Γ)
 Begin
 Bước 1. Khởi t¤o m¤ng
 Khởi t¤o tªp hu§n luy»n Γ gồm K vec-tơ c¡c chú ký nhị ph¥n Sig(Ii) = (bi1; :::; biN )
 mô t£ tªp c¡c h¼nh £nh ==fIiji = 1; :::; Kg; Khởi t¤o t¦ng đầu ra gồm n cụm
 Ω = fVj = hCj; kjθig, với Cj = (cj1; :::; cjN ); cjk 2 f0; 1g, k = 1; :::; N; j = 1; :::; n;
 Khởi t¤o tªp trọng sè W = fWjjWj = (w1j; :::; wnj); wij 2 f0; 1g; i = 1; :::; ng;
 Với méi chú ký nhị ph¥n đầu vào Sig(Ii) g¡n tªp S =; và

File đính kèm:

  • pdfluan_an_tim_kiem_anh_dua_tren_do_thi_chu_ky_nhi_phan.pdf