i NGUYấN I HC THI TRNG I HC CễNG NGH THễNG TIN V TRUYN THễNG NGUYN THANH TN XUT CI TIN THUT TONTèM KIM TRONG C S D LIU M LUN VN THC S KHOA HC MY TNH Thỏi Nguyờn - 2016 ii NGUYấN I HC THI TRNG I HC CễNG NGH THễNG TIN V TRUYN THễNG NGUYN THANH TN XUT CI TIN THUT TONTèM KIM TRONG C S D LIU M Chuyờn ngnh: Khoa hc mỏy tớnh Mó s: 60480101 LUN VN THC S KHOA HC MY TNH NGI HNG DN KHOA HC PGS TS NGUYN THIN LUN Thỏi Nguyờn - 2016 i LI CAM OAN Tụi xin cam oan nhng ni dung lun xut ci tin thut toỏn tỡm kim c s d liu m l tụi thc hin di s hng dn trc tip ca thy giỏo PGS TS Nguyn Thin Lun Mitham kho dựngtronglun u ctrớch dnrừrngtờntỏc gi,tờn cụng trỡnh, thi gian, a im cụng b Mi chộp khụng hpl, vi phm quy ch oto, hay giantrỏ, tụi xin chu trỏch nhim hon ton Thỏi Nguyờn, ngy 12 thỏng nm 2016 Hc viờn Nguyn Thanh Tõn ii LI CM N Em xin by t lũng bit n sõu sc ti PGS TS Nguyn Thin Lun ngi thy kớnh mn ó hng dn, ch dy tn tỡnh em hon thnh lun ny Em xin chõn thnh cm n cỏc thy, cụ giỏo trng i hc Cụng ngh thụng tin v Truyn thụng Thỏi Nguyờn, Khoa o to sau i hc - i hc Thỏi Nguyờn, Vin Cụng ngh thụng tin Vit Nam ó ún nhn v truyn th kin thc cho em sut quỏ trỡnh hc va qua Tụi cng xin cm n c quan, bn bố ng nghip, gia ỡnh v nhng ngi thõn ó cựng chia s, giỳp , ng viờn v to mi iu kin thun li tụi hon thnh nhim v hc v bn lun ny Thỏi Nguyờn, ngy 12 thỏng nm 2016 Hc viờn Nguyn Thanh Tõn iii DANH MC T TING ANH V VIT TT ANN BK - trees Codd E F Damerau - Levenshtein distance DoG Episode Full text search Fuzzy Databases Fuzzy join Fuzzy Natural joint Fuzzy projection Fuzzy Search Fuzzy Selection Fuzzy Sets Frame Incomplete Information Retrieval KD - tree Keypoint Keypoint localization Keypoint descriptor L.A Zadeh Levenshtein distance Lia, shot Match Necessity Optical flow Orientation assignment Panning Possibility Approximative Nearest Neibour Cõy Burkhard - Keller Edgar Frank "Ted" Codd Khong cỏch Damerau - Levenshtein Deffirence of Gaussisan Mt hi Tỡm kim ton C s d liu m Phộp kt ni m Phộp kt ni t nhiờn m Phộp chiu m Tỡm kim m Phộp chn m Tp m Khung hỡnh Khụng y H thng tỡm kim thụng tin h tr short for k-dimensional tree im quan trng nh v im c trng Mụ t cỏc im c trng Lotfi Aliasker Zadeh Khong cỏch Levenshtein on c s i sỏnh Tt yu Dũng quang hc Xỏc nh hng Ch s quay trỏi, phi ca mỏy quay Kh nng iv Process RGB Scale Scale - Space extrema detection Scene Sequence SIFT Spell - checker method Task TFN uncertainty unexact Weighted tuples Tin trỡnh Red, Green, Blue T l Phỏt hin cỏc im cc tr Cnh Chui video, dóy video Scale Invariant Feature Transform Phng phỏp kim tra chớnh t Tỏc v Triangular Fuzzy Number Khụng chc chn Khụng chớnh xỏc B cú trng s v DANH MC BNG V HèNH V Hỡnh 1.1:Biu din cỏc ca mt m Hỡnh 1.2: Biu din cỏc hm liờn thuc ca phộp ly phn bự Hỡnh 1.3: Cỏc m hỡnh tam giỏc Hỡnh 1.4: Tp m Singleton Hỡnh 1.5: Tp m L (phi) Hỡnh 1.6: Tp m Gamma tuyn tớnh 10 Hỡnh 1.7: Tp m hỡnh thang 10 Hỡnh 2.1: Biu din s m tam giỏc 24 Hỡnh 2.2: Minh cỏc bc chớnh gii thut SIFT 26 Hỡnh 2.3: Quỏ trỡnh tớnh khụng gian o (L) v hm sai khỏc D 28 Hỡnh 2.4: Quỏ trỡnh tỡm im cc tr cỏc hm sai khỏc DoG 29 Hỡnh 2.5: Mụ phng cụng thc m rng ca Taylor cho hm DoG 30 Hỡnh 2.6:Minh cỏc bc ca quỏ trỡnh la chn cỏc im keypoints 32 Hỡnh 2.7: Tớnh ln v hng ca Gradient 34 Hỡnh 2.8: To b mụ t cc b 35 Hỡnh 2.9: Mụ hỡnh d liu video 37 Hỡnh 2.10: S thut toỏn phỏt hin chuyn cnh 39 Hỡnh 3.1: Mụ hỡnh bi toỏn tỡm kim video CSDL 46 Hỡnh 3.2: Quy trỡnh tỡm kim video bng hỡnh nh CSDL 47 Hỡnh 3.3: Mụ phng cỏc im keypoint cn lu tr 48 Hỡnh 3.4: Biu din cỏc tỡnh trng hp thụng thng 50 Hỡnh 3.5: Biu din cỏc tỡnh trng hp xu 51 Hỡnh 3.6: S i sỏnh s m tam giỏc 55 Hỡnh 3.7: Giao din chng trỡnh phõn on v m húa video 56 Hỡnh 3.8: Giao din chng trỡnh Smart Cutter for DV and DVB 57 Hỡnh 3.9: Mụ hỡnh lp trỡnh socket TCP gia tin trỡnh client v server 59 Hỡnh 3.10: Giao din chng trỡnh tỡm kim video 61 Bng d liu thụng tin Video 53 Bng d liu Video shot 54 Bng kt qu ỏnh giỏ hiu nng tỡm kim 62 vi MC LC LI CAM OAN i LI CM N ii DANH MC T TING ANH V VIT TT iii DANH MC BNG V HèNH V v MC LC vi M U 1 t i tng v phm vi nghiờn cu Hng nghiờn cu ca ti Nhng ni dung nghiờn cu chớnh Phng phỏp nghiờn cu í ngha khoa hc ca ti CHNG 1: TNG QUAN V Lí THUYT M CSDL M V NG DNG 1.1 Tng quan v lý thuyt m 1.1.1 Khỏi nim m 1.1.2 Mt s khỏi nim ca m 1.1.3 Cỏc phộp toỏn trờn m 1.1.4 Cỏc kiu hm thuc 1.1.5 Cỏc loi s m 11 1.2 C s d liu m, phng thc biu din v ng dng 12 1.2.1 nh ngha 12 1.2.2 Biu din thuc tớnh quan h m 13 1.2.3 So sỏnh cỏc giỏ tr thuc tớnh m 13 1.2.4 Cỏc phộp toỏn hp trờn quan h m 15 1.2.5 Cỏc phộp toỏn quan h m 15 1.2.6 Ph thuc hm m 16 1.2.7 Cỏc mụ hỡnh c s d liu m 17 a Mụ hỡnh m 17 vii b Mụ hỡnh da trờn quan h tng t 17 c Mụ hỡnh da trờn phõn b kh nng 18 d Mụ hỡnh da trờn phõn b kh nng m rng 18 e Mụ hỡnh CSDL m da trờn t hp cỏc mụ hỡnh trờn 18 f Mụ hỡnh theo cỏch tip cn i s gia t 19 1.3 Tng quan v phng phỏp tỡm kim m 19 1.3.1 Khong cỏch Levenshtein 20 1.3.2 Khong cỏch Damerau - Levenshtein 20 1.3.3 Thut toỏn Bitap vi nhng thay i ca Wu v Manber 21 1.3.4 Phng phỏp kim tra chớnh t 22 1.3.5 Phng phỏp N-gram 22 1.3.6 Cõy - BK (BK - trees) 22 1.4 Kt lun chng 23 CHNG 2: THUT TON TèM KIM TRONG CSDL M 23 2.1 S m tam giỏc 24 2.1.1 Cỏc phộp toỏn trờn s m tam giỏc 24 2.1.2 Quan h so sỏnh trờn s m tam giỏc 25 2.2 T chc d liu cho thut toỏn tỡm kim d liu m 26 2.2.1 i sỏnh nh da trờn c trng SIFT 26 a Phỏt hin cỏc im cc tr 27 b nh v cỏc im c trng 31 c Xỏc nh hng cho cỏc im c trng 34 d Mụ t cỏc im c trng 35 e i sỏnh c trng SIFT 37 2.2.2 Phõn on d liu video 38 a Mụ hỡnh d liu video 38 b Mt s k thut phõn on video 39 c K thut phõn on video bng i sỏnh c trng SIFT 40 d Túm tt video 41 viii 2.3 Ci tin thut toỏn tỡm kim d liu m 42 2.3.1 Thut toỏn tỡm kim 42 2.3.2 Thut toỏn tỡm kim d liu m 44 2.3.3 ỏnh giỏ thut toỏn tỡm kim 44 2.4 Kt lun chng 45 CHNG 3: CI T THUT TON TèM KIM 46 3.1 Phõn tớch mt s nhu cu tỡm kim video CSDL 46 3.2 Thit k mụ hỡnh bi toỏn tỡm kim CSDL 47 3.2.1 Mụ hỡnh bi toỏn tỡm kim video 47 3.2.2 Quy trỡnh tỡm kim video theo hỡnh nh 48 3.2.3 Quy trỡnh s dng logic m 49 3.2.4 M rng csdl quan h thnh csdl m da trờn phõn b kh nng 50 a B cú trng strong quan h m 50 b Biu din d liu m bng phõn b kh nng 51 c Mi quan h vi dng chun 1NF 54 d o kh nng v o cn thit 54 3.3 Ci t thut toỏn tỡm kim m v mt s giao din chớnh 55 3.3.1 La chn cụng c 55 3.3.2 Thit k c s d liu 55 3.3.3 Ci t thut toỏn tỡm kim v mt s giao din chớnh 56 a K thut i sỏnh hai s m tam giỏc 56 b Ci t thut toỏn phõn on video 57 c Ci t thut toỏn trớch chn frame i din v m húa video 59 d K thut to cỏc tin trỡnh v trao i d liu 60 e Ci t thut toỏn tỡm kim d liu m 62 3.3.4 Th nghim v ỏnh giỏ 64 3.4 Kt lun chng 64 KT LUN 65 TI LIU THAM KHO 67 55 + C hai giỏ tr kh nng u l khụng bit (c biu din bi NULL): kt qu so sỏnh hai giỏ tr c coi l hon ton khỏc bit 3.3 Ci t thut toỏn tỡm kim m v mt s giao din chớnh 3.3.1 La chn cụng c Lun la chn nhng cng c lm thc nghim demo di õy: - Ngụn ng lp trỡnh Python version 2.7.10 - H qun tr c s d liu MySQL - Th vin h tr OpenCV version 2.4.11 - Phn mm Smart Cutter for DV and DVBversion 1.9.3 - Mt s th vin ngụn ng lp trỡnh Python 3.3.2 Thit k c s d liu Bng d liu thụng tin Video: Id_video File_name Date_created Vid1 Frame_rate 25 *.mp4 File_size File_length Frame_count 1456202692 6637174 748.44 18711 Frame_width Frame_height VideoBitRate AudioBitRate VideoCodec 768 576 1339139 Script to bng d liu Video: CREATE TABLE IF NOT EXISTS `video` ( `idvideo` int(11) NOT NULL DEFAULT '0', `filename` text NOT NULL, `datecreated` int(11) DEFAULT NULL, `filesize` int(11) DEFAULT NULL, `filelength` float DEFAULT NULL, `framecount` int(11) DEFAULT NULL, `framerate` int(11) DEFAULT NULL, `framewidth` int(11) DEFAULT NULL, 128002 h264 56 `frameheight` int(11) DEFAULT NULL, `videobitrate` int(11) DEFAULT NULL, `audiobitrate` int(11) DEFAULT NULL, `videocode` text NOT NULL, PRIMARY KEY (`idvideo`) ) ENGINE=MyISAM DEFAULT CHARSET=utf8; Bng d liu Video shot: Id_shot Id_video Frame_bd Frame_kt Kypoint Shot1 Vid1 339 986 Kypoint Shot2 Vid1 987 1078 Kypoint Shot1 Vid2 1079 1197 Kypoint Script to bng d liu VideoShot: CREATE TABLE IF NOT EXISTS `shotvideo` ( `idshot` int(11) NOT NULL DEFAULT '0', `idvideo` int(11) NOT NULL DEFAULT '0', `framebd` int(11) DEFAULT NULL, `framekt` int(11) DEFAULT NULL, `keypoint` longblob NOT NULL, PRIMARY KEY (`idshot`,`idvideo`) ) ENGINE=MyISAM DEFAULT CHARSET=utf8; 3.3.3 Ci t thut toỏn tỡm kim v mt s giao din chớnh a K thut i sỏnh hai s m tam giỏc [5] thc hin i sỏnh s m tam giỏc ta tin hnh i sỏnh giỏ tr tõm ri n giỏ tr biờn phi v cui cựng l giỏ tr biờn trỏi Input: a, , , b, , < true ab true false true false true > 57 Hỡnh 3.6: S i sỏnh s m tam giỏc * Hm o thuc s m tam giỏc: Cho s m tam giỏc v (a, , ) (b, , ) giao ca s m cng ln thỡ thuc gia s m cng cao Ký hiu l thuc ca s m tam giỏc vo s m tam giỏc ta cú: = nu ầ = ặ | | 10 (min ( + ), ( + ) max ( ), ( )) nu ầ ặ b Ci t thut toỏn phõn on video Thut toỏn s dng bc nhy gim lng i sỏnh thc hin thut toỏn, ti mi bc nhy s i sỏnh c trng ca mi nh tỡm ngng ct cnh Nu cú o nh hn ngng ct cnh thỡ thỡ thc hin tỡm ct cnh bc nhy ny Thut toỏn dng ht chui video * Thut toỏn: Input: Video cn phõn on Output: File danh sỏch phõn on ca video 1) Khi to i = 1, k = step, d1 = frame i 58 2) While i< Frame_count 3) If i = k then 4) d2 = Trớch xut frame i t video 5) If i sỏnh d1 vi d2 < ngng ct cnh then 6) Thc hin i sỏnh cỏc nh khong i vi i +5 tỡm v trớ l im kt thỳc v im u ca dóy nh ang xột 7) Thc hin lu tr v trớ ny vo file 8) d1 = im u ca video mi 9) else 10) 11) d1 = d2 k = k + step Hỡnh 3.7: Giao din chng trỡnh phõn on v m húa video Quỏ trỡnh phõn on video l quỏ trỡnh ũi hi chi phớ v thi gian nhiu nht so vi cỏc quỏ trỡnh khỏc Lun ch dng li mc phỏt hin chuyn cnh t ngt (ngt cng), cũn v phỏt hin chuyn cnh dn dn Fade, chng m v Wipe l hng nghiờn cu tip sau ca lun thc hin vic phõn on video cho nhng dng chuyn cnh ny Quỏ trỡnh kim tra li nhng phõn on video s trớch chn frame u v frame cui ca mi phõn on video i sỏnh nu nh hn ngng thỡ 59 nhng video ny cn phi xem xột li cú ỳng l mt cnh (lia) video hay khụng chun b cho quỏ trỡnh trớch chn frame i din v m húa d liu video, lun cú s dng phn mm Smart Cutter for DV and DVB thc hin vic kim tra licỏc phõn on video Nhm mc ớch nõng cao hiu qu ca quỏ trỡnh la chn frame i din v m húa trớch trnc trng ca video Hỡnh 3.8: Giao din chng trỡnh Smart Cutter for DV and DVB c Ci t thut toỏn trớch chn frame i din v m húa video Mi phõn on video s la chn nh v thc hin tỡm keypoint ca nh ny lm c trng mụ t cho video Nu s lng keypoint nh hn ngng cho trc thỡ video ang xột c phõn chia thnh sub video, mi sub video ny li chn nh thc hin tỡm keypoint Sau ú hp keypoint ca cỏc sub video ny li lm b mụ t c trng cho video Thut toỏn dng ht cỏc on video * Thut toỏn: Input:Video ó c phõn on Output:M húa theo s m tam giỏc v Lu tr c trng 60 1) Trớch xut cỏc thụng tin metadata ca video v lu tr vo bng Video 2) Khi to f = 0, f1, f2 = giỏ tr frame u v frame kt thỳc ca on video file phõn on ca video 3) While f< Frame_count 4) If f = f1 then 5) If f2 - f1 < 100 then ->Khi to mng Images = [7 phn t] 6) If f2 - f1 > 100 v < 250 then 7) 8) 9) 10) Khi to mng Images = [9 phn t] If f2 - f1 > 250 v < 400 then Khi to mng Images = [11 phn t] If f2 - f1 > 400 then -> Khi to mng Images = [13 phn t] 11) If f < f2 then 12) Images.append = Trớch xut frame f t video 13) If f = f2 then 14) Chn nh Images thc hin m húa theo s m tam 15) If s lng keypoint < ngng then giỏc 16) Chia mng Images lm ba, mi subImages chn nh thc hin m húa theo s m tam giỏc 17) Thc hin lu tr keypoint ca video vo bng ShotVideo 18) f1, f2 = giỏ tr frame u v frame kt thỳc ca on video mi d K thut to cỏc tin trỡnh v trao i d liu Lun xõy dng cỏc tin trỡnh theo mụ hỡnh kin trỳc Client-Server, l mụ hỡnh ph bin cho giao tip gia tin trỡnh/2 mỏy.Mụ hỡnh client/server cung cp mt cỏch tip cn tng quỏt chia s ti nguyờn 61 cỏc h thng phõn tỏn.Cỏc tin trỡnh client v tin trỡnh server u cú th chy trờn cựng mt mỏy tớnh Mt tin trỡnh server cú th s dng dch v ca mt server khỏc Hỡnh 3.9: Mụ hỡnh lp trỡnh socket TCP gia tin trỡnh client v server Giai on 1:Server to Socket (Cú th hiu Socket nh mt im u cui ca kờnh kt ni gia tin trỡnh), gỏn s hiu cng v lng nghe yờu cu kt ni socket(): Server to socket s dng cỏc dch v ca tng chuyn bind():Server gỏn s hiu cng (port) cho socket listen(): Server lng nghe cỏc yờu cu kt ni trờn cng ó c gỏn Giai on 2:Client to Socket, yờu cu thit lp mt ni kt vi Server socket(): Client to socket s dng cỏc dch v ca tng chuyn 62 connect(): Client yờu cu kt ni n server cú a ch IP v Port xỏc nh accept(): Server chp nhn kt ni ca client, ú mt kờnh giao tip o c hỡnh thnh, Client v server trao i d liu thụng qua kờnh o ny Giai on 3:Trong giai on ny, vic trao i d liu gia Client v Server phi tuõn th giao thc ca tin trỡnh (Dng thc v ý ngha ca cỏc thụng ip, qui tc bt tay, ng b húa, ) Thụng thng Client sgi yờu cu n Server.Gi v nhn d liu vi cỏc cõu lnh read(), write() cú th c thc hin nhiu ln Giai on 4:Kt thỳc phiờn lm vic, kờnh o s b xúa Server hoc Client úng socket bng lnh close() e Ci t thut toỏn tỡm kim d liu m u vo l nh truy t ngi s dng, thut toỏn phõn chia phm vi d liu cho mi tỏc v Mi tỏc v (Client) thc hin gi nh truy v d liu video cho tin trỡnh (Server)tỡm kim Mi tin trỡnh thc hin trớch xut keypoint t nh truy v truy d liu ca shot video, sau ú thc hini sỏnh c trng vi Nu kt qu i sỏnh ln hn ngng tỡm kim thỡ gi thụng tin shot video v kt qu i sỏnh v cho tỏc v, tỏc v nhn d liu v cp nht danh sỏch kt qu Thut toỏn dng ó quột ht d liu bng shotvideo * Thut toỏn: Input: nh truy vn,bng Video, bng ShotVideo Output: Danh sỏch kt qu tỡm kim video 1) Khi to danh sỏch kt qu = ặ 2) While video< RowVideoCount 3) Phõn video cho tỏc v 4) Khi ngprocess thc hin tỏc v 63 * Thut toỏn trờn cỏc tỏc v (Client) - Send(nh truy cho tin trỡnh) - Khi to truy d liu bng Video vi d liu = vid -Forvideoin RowVideo - Send(video cho tin trỡnh) - Receive ( kt qu ) v Cp nht danh sỏch kt qu tỡm kim * Thut toỏn trờn cỏc process (Server) - Receive ( video ) v kp1 = keypoint ca nh truy - Khi to truy d liu bng ShotVideo vi d liu = video - For shotvideo in RowShotVideo - kp2 = keypoint l s m tam giỏc c s d liu - If DoiSanhSoMoTamGiac(kp1, kp2)> ngng then - Send(thụng tin ca video v kt qu i sỏnh) 5) Sp xp li danh sỏch kt qu Hỡnh 3.10: Giao din chng trỡnh tỡm kim video 64 3.3.4.Th nghim v ỏnh giỏ Lun thc nghim trờn: + Thit b phn cng: Processor Core i5 - 2.2 Ghz, Ram Gb + Phn mm v d liu: H iu hnh Microsoft Window 10 - 32 bit, bng Video gm 21 bn ghi, bng ShotVideo gm 3338 bn ghi v nh truy STT K thut Thi gian thc hin mỏy Tun t a lung (5 threads) process process process process Mi mỏy 4process 23 giõy 24 giõy 14 giõy 13 giõy 13 giõy 13 giõy giõy trung chớnh xỏc thc (Recall) (Precision) 0,85 0,85 0,85 0,85 0,85 0,85 0,85 0,943 0,943 0,943 0,943 0,943 0,943 0,943 Bng kt qu ỏnh giỏ hiu nng tỡm tim - ỏnh giỏ v tc thc hin: K thut tỡm kim a lung cho tc tỡm kim chm nht, k thut s dng mỏy tớnh vi mi mỏy process cho tc tỡm kim tt K thut process cho tc khỏ tt trng hp s dng mỏy tớnh, cũn k thut3process cho tc khỏ nhanh (ch kộm k thut process1 giõy) - ỏnh giỏ v chớnh xỏc: Cỏc k thut u cho kt qu tng t vỡ c bn u s dng phng phỏp i sỏnh 3.4 Kt lun chng Chng lun ó trỡnh by: Phõn tớch mt s nhu cu tỡm kim thụng tinvideo CSDL Thit k mụ hỡnh bi toỏn tỡm kim video, thit k bng d liu video Ci t thut toỏn tỡm kim v mt s giao din chớnh 65 Thc nghim v ỏnh giỏ kt qu thc nghim KT LUN Video ngy cng c ng dng rng rói nhiu lnh vc i sng khoa hc - xó hi Cỏc ti liu video k thut s ngy chim mt slng ln d liu a phng tin cú sn qun lý hiu qu cỏc ti liu video ny, chỳng cn phi c mụ t ngn gn hn v lu tr thun tin hn Cỏc phng phỏp mụ t da trờn bn l khụng cung cp mt mụ t y , ú mt hỡnh thc mi ca mụ t video l cn thit cho chui video Song song vi vic lu tr cỏc ti liu video, vic tỡm kim li nhng video ny cng cú nhiu nghiờn cu Lun trung nghiờn cu v mụ hỡnh c s d liu m vi phng phỏp m húa c trng cỏc frame i din ca video c s theo s m tam giỏclm c trng ca video v phng phỏp tỡm kim m nhng video ny Qua thi gian thc hin ti, lun nghiờn cu ó hon thnh c mc ớch v cỏc ni dung nghiờn cu ra, c th vi cỏc ni dung chớnh nh sau: - Nghiờn cu v tng quan lý thuyt m, c s d liu m v ng dng - Nghiờn cu tng quan v cỏc loi s m v phng phỏp tỡm kim m - Nghiờn cu v thut toỏn SIFT trớch chn c trng cc b ca nh - Nghiờn cu k thut nhy thớch ng ỏp dng phõn on video - Nghiờn cu k thut thit k thut toỏn song songthit k thut toỏn tỡm kim video - Ci t th nghim thut toỏn Quỏ trỡnh nghiờn cu giỳp bn thõn cú thờm kin thc chuyờn sõu v c s d liu m, k thut phõn on video, k thut m húa video, k thut tỡm 66 kim m Mc dự rt n lc nghiờn cu, song thi gian v nng lc cũn hn ch, nờn ti mi ch cp c mt s phn rt nhiu lnh vc liờn quan n c s d liu m v tỡm kim m, hng nghiờn cu tip theo ca lun vn: - Phõn on video m vi cỏc k thut phỏt hin v chuyn lia t t - M rng v chuyn i cỏc mụ hỡnh c s d liu sang c s d liu m - Cỏc thut toỏn tỡm kim c s d liu m Kt qu t c:Nm vng v lý thuyt m, c s d liu m, c s k thut phõn on video, c s k thut tỡm kim m, phng phỏp xõy dng thit k thut toỏn Hng phỏt trin ca lun vn: Tip tc xõy dng kho lu tr video v cỏc m húac trng cc b video rỳt gn giỳp cho vic tỡm kim video theo mt s iu kin c nhanh v thun tin 67 TI LIU THAM KHO Ti liu ting Vit [1] Bựi Cụng Cng, Nguyn Doón Phc (2006), H m mng nron v ng dng, Nh xut bn Khoa hc v K thut [2] Nguyn Cỏt H, Nguyn Cụng Ho (2009), Logic m v ng dng, i hc Khoa hc - i hc Hu [3] Nguyn Thin Lun (2015), Lý thuyt m ng dng tin hc, Nh xut bn Thng kờ [4] on Vn Thng (2010), Truy d liu vi thụng tin m v khụng chc chn c s d liu hng i tng, Tp khoa hc v cụng ngh, i hc Nng, S 4(39), tr 15-24 [5] Nguyn Cụng Ho, Trng Th M Lờ (2012), Truy c s d liu hng i tng m da trờn ng ngha i s gia t, Tp khoa hc, i hc Hu, Tp 74B (S 5), tr 39-53 [6] Nguyn Hũa (2015), Mt mụ hỡnh c s d liu quan h m, Cỏc cụng trỡnh nghiờn cu, phỏt trin v ng dng CNTT-TT, Tp V-1, S 13 (33) [7] Lng Xuõn Cng, Trung Tun, Xuõn Tin (2007), Chun b d liu trong vic xõy dng c s d liu video s, Tp tin hc v iu khin hc, T.23 (S.2), tr 141-152 Ti liu ting Anh [8] Amel Grissa Touzi and Mohamed Ali Ben Hassine (July 2009), New Architecture of Fuzzy Database Management Systems, The International Arab Journal of Information Technology, Vol 6, No 3, pp 213-220 68 [9] Austin Melton and Sujeet Shenoi (1991), Fuzzy Relations and Ruzzy Relational Databases, Computers Math Applic,Vol 21, No 11/12, pp 129138 [10] Feng Hao, John Daugman, and Piotr Zielinski (June 2008), A Fast Search Algorithm for a Large Fuzzy Database, Ieee Transactions on Information Forensics and Security, Vol 3, No 2, pp 203-212 [11] Jaydev Mishra and Sharmistha Debnath Ghosh (December 2008), A Study of Fuzzy Relational Database, International Journal of Computational Cognition,Vol 6, No 4, pp 45-50 [12] Josộ Galindo, Angộlica Urrutia and Mario Piattini (2006), Fuzzy Databases Modeling, Design and Implementation, Idea Group Inc [13] Miroslav Hudec (December 2009), An Approach to Fuzzy Database Querying, Analysis and Realisation, ComSIS, Vol 6, No 2, pp 127-140 [14] K K Phang, Mashkuri Hj Yaacob and T C Ling (June 1997), Development of Fuzzy Database Systems, Malaysian Journal of Computer Science, Vol 10, No 1, pp 42-46 [15] Maridalia Guerrero (2011), A Comparative Study of Three Image Matcing Algorithms: Sift, Surf, and Fast, All Graduate Teses and Dissertations, DigitalCommons@USU [16] Z M Ma and Li Yan (2008), A Literature Overview of Fuzzy Database Models, Journal of Information Science and Engineering, Vol 24, pp 189202 Xỏc nhn ca giỏo viờn hng dn Hc viờn 69 PGS TS Nguyn Thin Lun Nguyn Thanh Tõn [...]... theo iu kin tỡm kim m trong c s d liu vn c cỏc chuyờn gia nghiờn cu, trong vic truy tỡm thụng tin phự hp vi yờu cu ca mt truy vn a ra t ngi s dng.Ngi s dng cú xu hng tỡm kim ch yu trong c s d liu, vớ d nh tỡm kim mt lot hỡnh nh c vt liờn quan n nn vn hoỏ c Vit Nam, tỡm kim d liu õm thanh cú bn text kốm theo, tỡm kim video bi ging cho hc sinh ụn thi i hc Bi toỏn tỡm kim thụng tin trong c s d liu úng vai... Chng 2: Thut toỏn tỡm kim trong c s d liu m 2.1 S m tam giỏc 2.2 T chc d liu cho thut toỏn tỡm kim d liu m 2.3 Ci tin thut toỏn tỡm kim d liu m 2.4 Kt lun chng Chng 3:Ci t thut toỏn tỡm kim trong c s d liu qun lý cỏc chng trỡnh truyn hỡnh i PT-TH tnh Hũa Bỡnh 3.1 Phõn tớch mt s nhu cu tỡm kim video trong CSDL qun lý cỏc chng trỡnh truyn hỡnh 3.2 Thit k mụ hỡnh bi toỏn tỡm kim trong CSDL m qun lý cỏc... giỏ trờn c s hm thuc ca tp m, trong ú trng thỏi "ỳng" tng ng vi 1, trng thỏi "sai" tng ng vi 0 Cũn nhng giỏ tr (0,1) l phn ỏnh mc ỳng sai ca vic ỏnh giỏ: cng gn 1 cng ỳng, cng gn 0 cng sai Bi vy trong mi quan h m s cú mt thuc tớnh c bit gi l thuc tớnh tha, ký hiu l vi Dom() = [0,1], dựng ch mc l thnh viờn ca mi b trong quan h 1.2.3 So sỏnh cỏc giỏ tr thuc tớnh m Trong mụ hỡnh quan h kinh in cỏc... liờn quan n thuc ca cỏc b vo CSDL, tớnh m th hin trong cỏc giỏ tr thuc tớnh v quan h gia cỏc phn t ca min tr ca thuc tớnh.Nh vy, cỏch tip cn ny l t hp ca 19 cỏch tip cn theo phõn b kh nng, theo quan h tng t v theo mụ hỡnh tp con m Mi b ca mt quan h trong mụ hỡnh ny cú dng: t = {A1, A2, , Ai, , An,t} Trong ú cỏc giỏ tr thuc tớnh l cỏc phõn b kh nng, trong ú Ai Ui, ngoi ra, mi b t cũn c gỏn giỏ tr t... bi toỏn tỡm kim vi iu kin tỡm kim m trong c s d liu m qun lý cỏc chng trỡnh truyn hỡnh 6 í ngha khoa hc ca ti - Giỳp tỡm hiu, ỏnh giỏ khỏi quỏt v h c s d liu m, cỏc thut toỏn tỡm kim vi iu kin tỡm kim m - Vn dng tt thut toỏn tỡm kim vi iu kin tỡm kim m, giỳp chỳng ta cú th d dng tỡm kim nhng ni dung trong c s d liu - Xõy dng c s khoa hc cho cỏc bi toỏn tỡm kim trong c s d liu 5 CHNG 1: TNG QUAN V... àA (x)) trong khụng gian nnn s thc R c gi l s thc th m nu tha món 3 iu kin: -A l tp p m chớnh tc -A l l cỏc khong ng úng vi (0,1] - Tp S = suppàA (x) = {{x X / àA (x) > 0} gii ni b S m hỡnh ỡnh chuụng:L chuụng: mt tp m cú dng [a-, aa+] trong ú 0, 0 l cỏc s thc vi hm h liờn thuc: ( , , )( )= ( )khi ( )khi + 0 khi ( < )( > + ) c S m dng ng tam giỏc giỏc:L mt tp m cú dng [ a-, a, aa+ ] trong. .. [ a-, a,, b, b+ ] trong ú 0, 0 l cỏc s thc vi hm liờn thuc: 12 1 ( , , )( khi +1 khi +1 khi + )= 0 )hoc ( > khi( < + ) e S m dng khong: L tp m cú dng (a, ) trong ú 0 l cỏc s thc vi hm liờn thuc: ( , )( )= 0 +1 khi +1 khi khi + hoc > + 1.2 C s d liu m, phng thc biu din v ng dng[5] Mụ hỡnh quan h do Codd E F xut nm 1970 ó ỏp ng c nhu cu lu tr v x lý d liu ca con ngi trong mt thi gian... trong mụ hỡnh c s d liu kinh in thỡ phi i y thụng tin v i tng mi cp nht vo c s d liu, hoc nu c cp nht thỡ s gõy khú khn, mt ng ngha v khụng nht quỏn trong x lý d liu Do ú ỏp ng nhu cu thc t, mụ hỡnh c s d liu ó c m rng biu din v x lý nhng d liu m gi l c s d liu m (Fuzzy Databases) 1.2.1 nh ngha Cho W=(, A1, A2, An) l tp hu hn cỏc thuc tớnh, cỏc min giỏ tr tng ng D(A1), D(A2), D(An), D() =[0,1] Trong. .. thuc tớnh trong quan h m Xột lc quan h R=(, A1, An) i vi thuc tớnh Ai l rừ thỡ D(Ai)=U(Ai) i vi thuc tớnh Ai l thuc tớnh m thỡ: D(Ai)=U(Ai) T(Ai) F(Ai) I(Ai) õyU(Ai): L min giỏ tr c s, T(Ai): Tp cỏc giỏ tr ngụn ng ca bin ngụn ng Ai, F(Ai): Tp cỏc tp m biu din di dng s m hỡnh thang, I(Ai): Tp cỏc tp m biu din di dng s m dng khong Rừ rng l trong nhiu trng hp cỏc tp giỏ tr cú th l tp rng Trong c s d... hiu v lý thuyt m v ng dng - Tỡm hiu v c s d liu m v ng dng 3 - Tỡm hiu cỏc k thut v quy trỡnh tỡm kim thụng tin trong c s d liu m vi cỏc yờu cu tỡm kim cha ng thụng tin khụng rừ rng khụng chớnh xỏc - Ci tin thut toỏn tỡm kim trong c s d liu m 4 Nhng ni dung nghiờn cu chớnh Lun vn c trỡnh by trong 3 chng, cú phn m u, phn kt lun, phn mc lc, phn ti liu tham kho v phn danh mc bng v hỡnh v Cỏc ni dung c bn ... t[A] = t1[A] v t[B] = t2[B] v t[C] = t1[C] = t2[C] Trong ú fr1 xỏc nh trờn AC v fr2 xỏc nh trờn CB v AầBầC = ặ * Phộp kt ni m ( Fuzzy join) Trong trng hp l nhng phộp toỏn: , , , , thỡ phột... c s d liu m l tụi thc hin di s hng dn trc tip ca thy giỏo PGS TS Nguyn Thin Lun Mitham kho dựngtronglun u ctrớch dnrừrngtờntỏc gi,tờn cụng trỡnh, thi gian, a im cụng b Mi chộp khụng hpl, vi phm... 1.3.6 Cõy - BK (BK - trees) 22 1.4 Kt lun chng 23 CHNG 2: THUT TON TèM KIM TRONG CSDL M 23 2.1 S m tam giỏc 24 2.1.1 Cỏc phộp toỏn trờn s m tam giỏc