Beis, J. and Lowe, D. G. 1997. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Conference on Computer Vision and Pattern Recognition, Puerto Rico, pp. 1000–1006.
มกราคม 08, 2022
การค, นหาแบบเบสท, นเฟ, สท, การค, นแบบเบสท, นเฟ, สท, งกฤษ, best, first, เป, นข, นตอนว, การค, นหาท, ใช, ในการหาจ, ดท, อย, ใกล, nearest, neighbor, search, โดยประมาณในปร, หลายม, โดยข, นตอนว, การประย, กต, มาจากต, นไม, เคด, tree, ทำให, การค, นม, ประส, ทธ, ภาพและเร, . karkhnaebbebsthbinefirsth xngkvs Best Bin First epnkhntxnwithikarkhnhathiichinkarhacudthixyuiklthisud nearest neighbor search odypramaninpriphumihlaymiti odykhntxnwithinimikarprayuktmacaktnimekhdi k d tree thaihkarkhnmiprasiththiphaphaelaerwmakkhun nxkcakniyngepnkhntxnwithikarkhnhathisamarthnaipichidcringinthangptibti xyangechn ichkbkartrwchalksnaednaebbsifth SIFT sungepnhnunginkhntxnwithiinkartrwchalksnaedn feature detection ineruxngkhxmphiwetxrwithsn computer vision enuxha 1 thima 1 1 pyhakarhacudthixyuiklthisud 1 2 tnimekhdi 2 khntxnwithikhxngebsthbinefirsth 3 prasiththiphaphinkarthangan 4 twxyangkarichngan karrucawtthuodyichkartrwchalksnaednaebbsifth 5 duephim 6 xangxingthima aekikhkarkhnaebbebsthbinefirsthnimithimacakpyhakarhacudthixyuiklthisud nearest neighbor search sungkhntxnwithikarkhnhanithukkhidkhnkhunmaephuxephimkhwamerwinkarkhninpriphumithimihlaymiti aelamikhwamaemnyamakphxthicanaipichcring odyhlkkarsakhyxyanghnungthiebsthbinefirsthnamaichkhuxkarekbkhxmulcudinpriphumidwytnimekhdi k d tree pyhakarhacudthixyuiklthisud aekikh pyhakarhacudthixyuiklthisud nearest neighbor search epnpyhathangwithyakarkhxmphiwetxrinkarhacudthixyuiklcudthikahndmakthisudinpriphumimititang odyrayathangthiichwdrayarahwangcudxaccaepnrayathangaebbyukhlid Euclidean distance hruxepnrayathangaebbaemnhttn Manhattan distance kid sungpyhaniidmikhwamphyayaminkarxxkaebbkhntxnwithiihmiprasiththiphaphinkarkhnmakthisud klawkhux samarthkhncuddngklawiderwaelaaemnya khladekhluxnnxythisud inpccubnmikhntxnwithisahrbpyhanihlaywithi aelamithngkarkhncudthixyuiklthisudaebbaemnyaaelaaebbpraman twxyangechn thaepnkarkhnaebbtrng kcaepnkarkhnaebbesntrng linear search thiichwithikarkhnaebbethiybthukcud miprasiththiphaphinkarthanganepn O Nd odythi N aethncanwncud aela d aethncanwnmitikhxngpriphumi xyangirkdi karkhninpriphumithimicanwnmitithisungkhunkcamikhwamsbsxnephimkhun thaihtxngmikarkhidkhnkhntxnwithiihm inkarkhn withihnungthithuknamaichinkarchwykhnkhuxkarichtarangaehch aetwithiniimehmaakbpyhathimicanwnmitisung xikwithihnungthithuknamaichnganaelaihphlepnthinaphxicemuxmicanwnmitisung khuxkarichtnimekhdi k d tree sungepnkaraebngpriphumixxkepnswn ephuxekbkhxmulepntnim tree karekbkhxmulepntnimnikthaihsamarthkhnkhxmulidrwderwechnkn aelathuknamaichinkarkhnaebbebsthbinefirsthdwy tnimekhdi aekikh tnimekhdi k d tree epnokhrngsrangkhxmulthiichinkaraebngswninpriphumiinrupkhxngtnim tree ephuxephimprasiththiphaphinkarkhn hlkkarthanganodyyxkhuxcaerimaebngswnkhxngcudinpriphumicakmitithimikhwamaeprprwn variance khxngcudsungthisud aelwaebngcudxxkepn 2 klumthimicanwncudinaetlaklumethakn aelwinaetlaklumkcathakaraebngechnnilngiperuxy cnsud sungcaehluxcudephiyngcudediyw aelwekbkhxmulkaraebngaetlakhnepnpm echuxmknepntnim xyangirktam raylaexiydinkarnaipichngancringxaccaimtaytw khunxyukbkarxxkaebbkhxngnkekhiynopraekrmdwy xyangechn hlkinkaraebngkhrungwacahacudthixyukungklangthisudinmitinnaelwaebngkhrungthicudnnhruxaebngthikhamthythankhxngcudinmitinnaethn sungcaidcudxyuinpmib leaf node khxngtnimaethnthicaidcudxyupracapmthukpmintnim odysahrbkarkhnaebbebsthbinefirsthnicaichwithikaraebngxyanghlng khuxaebngthikhamthythan ephuxihpmthimicudepnibkhxngtnim aetihsngektdwywapmibaetlapmni imidaethncud 1 cud aetaethnswnkhxngpriphumithithukaebngcnehluxswnthimicudxyuphayinephiyng 1 cudkhntxnwithikhxngebsthbinefirsth aekikhkhntxnwithiinkarkhnaebbebsthbinefirsthnicaepnkarnatnimekhdi k d tree maprayuktichkbkarkhnhacudthixyuiklthisudodypraman odykhxmulthiidrbmakhuxestkhxngcudinpriphumi d miti aelacud q sungepncudthitxngkarsxbtham query point singthikhntxnwithinicakhunklbmakhuxcudinestthixyuiklkbcud q makthisud erimcakthakaraebngswnkhxngpriphumitamkhxmulcudthiidrbmaephuxsrangepntnimekhdidngthiidklawiwinhwkhxtnimekhdi emuxsrangesrccaidwakhxmulkhxngcudthukcudinestcaepnibkhxngtnim tree nnkhux pmibthukpmkhxngtnimcamicudinestephiyng 1 cudethann ykewnpmthimicud q xyu cami 2 cud idaek cudinestaelacud q ihhawacud q nnxyuinpmibidkhxngtnimaelwkahndthrngklm n mitithimirsmiepnrayacakcud q thungcudthixyuinpmibediywknepnkarcakdrayacakcud q thicaichkhnhacudthixyuiklthisud aelwkcawnhacuddngklawodykarthxngipintnimephuxthicaipyngpmibaetlapmthixyuphayinrsmi xyangirktam enuxngcakebsthbinefirsthepnkarkhnhaodypraman cungmikarcakdcanwnkhrngthicaichkhnha hruxphudinxiknyhnungkkhuxcakdcanwnpmibthicathakarethiybharayakbcud q nnexng nxkcakni ephuxephimprasiththiphaphinkarkhn camikarichaethwkhxyladbkhwamsakhy priority queue inkarcdladbpmibthicakhndwy odycdladbcakrayacakkhxbkhxngpmibnninpriphumiipyngcud q dngnnnxkcakcamikarcakdcanwnkhrngthicaichkhnaelw yngerimkhncakpmibthixyuiklthisudkxndwy wdrayacakcud q thungkhxbswnkhxngpmib imichwdthungcudkungklangkhxngpmib cungepnthimakhxngchuxebsthbinefirsth best bin first odythikhawabin bin macakkhawathwiphakh binary sunghmaythungkaraebngswnkhxngpriphumitamhlkkhxngtnimekhdithicaaebngxxkkhrnglasxngswnlngiperuxy cnthungswnkhxngpriphumithimicudephiyngcudediyw imnbcud q odythimikarthdlxngaelwwakhakhxngcudthixyuiklthisudodypramanthiidcakkhntxnwithikhxngebsthbinefirsthnnmikhwamaemnyasungphxthicanaipprayuktichinthangptibti aelasamarthsrupkarthanganepnrhsethiym pseudocode iddngni BestBinFirst S q input S estkhxngcudinpriphumi d miti q cudthitxngkarsxbtham query point output c cudthixyuinest S thixyuiklcud q makthisud 1 ih kdtree epntnimekhdi k d tree thiekidcakkaraebngswnpriphumitamest S 2 ih c epncudthixyuinpmibediywknkbcud q 3 ih Dc epnrayacakcud q ipyngcud c 4 ih Em epncanwnpmibthicathakarkhn 5 ih PQ epnaethwkhxyladbkhwamsakhy priority queue thieriyngladbtamkhwamiklcakcud q thungkhxbkhxngpmib 6 thakar enqueue pmibthimirayacakcud q phayinrsmi Dc 7 sahrb i 1 thung Em 8 tha PQ empty ih break 9 ih b PQ removeMin 10 tha cud b xyuiklcud q makkwacud c ih c b 11 return cprasiththiphaphinkarthangan aekikhcakrhsethiym pseudocode danbn caehnwapharainkarthangankhxngkhntxnwithinicatkxyuthibrrthdthi 1 khuxkarsrangtnimekhdi k d tree sungmiprasiththiphaphinkarthanganepn O n log2 n emuxmikarichkhntxnwithikareriyngladbthimiprasiththiphaphepn O n log n inkarhakhamthythan swnbrrthdthi 5 nncring kmipharakarthanganthihnkechnkn aetenuxngcakidmikarkhdpmibxxkipcakkarcakdkharsmi Dc sungsamarthkhdkrnithiimcaepnxxkipidcanwnmak pharainkarthanganswnnicungebakhunmak aelaswnthiichinkarkhncudthixyuiklthisudcring miprasiththiphaphinkarthanganepn O 1 enuxngcakmikarcakdcanwnkhrnginkarhaaennxnwaimekin Em khrng ephraachannodyrwmaelwkhntxnwithinicungkhniderwmaktwxyangkarichngan karrucawtthuodyichkartrwchalksnaednaebbsifth aekikhkartrwchalksnaednaebbsifth SIFT epnwithikarthangkhxmphiwetxrwithsn computer vision inkartrwchalksnaedn feature detection sungsamarthnamaprayuktichineruxngkarrucawtthu object recognition odythicathakaraeplngkhxmulrupphaphthiidmaephuxhacudthimilksnaedn keypoint khxngrupnn odythikhxmulkhxngcudlksnaednnisudthaycathukaeplngepncudinpriphumi 128 miti ephuxichepntwbxkcudlksnasakhy keypoint descriptor thimikhwamepnexklksnsung emuxtxngkarethiybrupwtthukbrupphaphthiidmawamiwtthuxyuinrupphaphdngklawhruxim kcathakarhacudlksnaedn keypoint aelatwbxkcudlksnasakhy keypoint descriptor aelwnamaharayathangaebbyukhlid Euclidean distance rahwangtwbxkcudlksnasakhydwykn thacudthixyuiklthisudxyuiklkwarayathikahndiwkcathuxwacudlksnaednkhxngthng 2 rupepncudediywkn odycasngektidwatwbxkcudlksnasakhyniepnkarekbkhxmulcudinpriphumithimicanwnmitisungmak khux 128 miti dngnnephuxephimprasiththiphaphinkarkhn cungichkarkhnaebbebsthbinefirsthephuxkhncudthixyuiklthisuddngklawduephim aekikhNearest neighbor search k d tree Feature detection SIFTxangxing aekikhBeis J and Lowe D G 1997 Shape indexing using approximate nearest neighbour search in high dimensional spaces Conference on Computer Vision and Pattern Recognition Puerto Rico pp 1000 1006 ekhathungcak https th wikipedia org w index php title karkhnhaaebbebsthbinefirsth amp oldid 5263354, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,