Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
การค้นแบบเบสท์บินเฟิร์สท์ (อังกฤษ: Best Bin First) เป็นขั้นตอนวิธีการค้นหาที่ใช้ในการหาจุดที่อยู่ใกล้ที่สุด (nearest neighbor search) โดยประมาณในปริภูมิหลายมิติ โดยขั้นตอนวิธีนี้มีการประยุกต์มาจาก (k-d tree) ทำให้การค้นมีประสิทธิภาพและเร็วมากขึ้น นอกจากนี้ยังเป็นขั้นตอนวิธีการค้นหาที่สามารถนำไปใช้ได้จริงในทางปฏิบัติ อย่างเช่น ใช้กับการตรวจหาลักษณะเด่นแบบซิฟท์ (SIFT) ซึ่งเป็นหนึ่งในขั้นตอนวิธีในการตรวจหาลักษณะเด่น (feature detection) ในเรื่องคอมพิวเตอร์วิทัศน์ (computer vision)
ที่มา
การค้นแบบเบสท์บินเฟิร์สท์นี้มีที่มาจากปัญหาการหาจุดที่อยู่ใกล้ที่สุด (nearest neighbor search) ซึ่งขั้นตอนวิธีการค้นหานี้ถูกคิดค้นขึ้นมาเพื่อเพิ่มความเร็วในการค้นในปริภูมิที่มีหลายมิติ และมีความแม่นยำมากพอที่จะนำไปใช้จริง โดยหลักการสำคัญอย่างหนึ่งที่เบสท์บินเฟิร์สท์นำมาใช้คือการเก็บข้อมูลจุดในปริภูมิด้วย (k-d tree)
ปัญหาการหาจุดที่อยู่ใกล้ที่สุด
ปัญหาการหาจุดที่อยู่ใกล้ที่สุด (nearest neighbor search) เป็นปัญหาทางวิทยาการคอมพิวเตอร์ในการหาจุดที่อยู่ใกล้จุดที่กำหนดมากที่สุดในปริภูมิมิติต่าง ๆ โดยระยะทางที่ใช้วัดระยะระหว่างจุดอาจจะเป็นระยะทางแบบยุคลิด (Euclidean distance) หรือเป็นระยะทางแบบแมนฮัตตัน (Manhattan distance) ก็ได้ ซึ่งปัญหานี้ได้มีความพยายามในการออกแบบขั้นตอนวิธีให้มีประสิทธิภาพในการค้นมากที่สุด กล่าวคือ สามารถค้นจุดดังกล่าวได้เร็วและแม่นยำ คลาดเคลื่อนน้อยที่สุด ในปัจจุบันมีขั้นตอนวิธีสำหรับปัญหานี้หลายวิธี และมีทั้งการค้นจุดที่อยู่ใกล้ที่สุดแบบแม่นยำและแบบประมาณ ตัวอย่างเช่น ถ้าเป็นการค้นแบบตรง ๆ ก็จะเป็นการค้นแบบเส้นตรง (linear search) ที่ใช้วิธีการค้นแบบเทียบทุกจุด มีประสิทธิภาพในการทำงานเป็น O(Nd) โดยที่ N แทนจำนวนจุด และ d แทนจำนวนมิติของปริภูมิ อย่างไรก็ดี การค้นในปริภูมิที่มีจำนวนมิติที่สูงขึ้นก็จะมีความซับซ้อนเพิ่มขึ้น ทำให้ต้องมีการคิดค้นขั้นตอนวิธีใหม่ ๆ ในการค้น วิธีหนึ่งที่ถูกนำมาใช้ในการช่วยค้นคือการใช้ตารางแฮช แต่วิธีนี้ไม่เหมาะกับปัญหาที่มีจำนวนมิติสูง อีกวิธีหนึ่งที่ถูกนำมาใช้งานและให้ผลเป็นที่น่าพอใจเมื่อมีจำนวนมิติสูง ๆ คือการใช้ (k-d tree) ซึ่งเป็นการแบ่งปริภูมิออกเป็นส่วน ๆ เพื่อเก็บข้อมูลเป็นต้นไม้ (tree) การเก็บข้อมูลเป็นต้นไม้นี้ก็ทำให้สามารถค้นข้อมูลได้รวดเร็วเช่นกัน และถูกนำมาใช้ในการค้นแบบเบสท์บินเฟิร์สท์ด้วย
ต้นไม้เคดี
(k-d tree) เป็นโครงสร้างข้อมูลที่ใช้ในการแบ่งส่วนในปริภูมิในรูปของต้นไม้ (tree) เพื่อเพิ่มประสิทธิภาพในการค้น หลักการทำงานโดยย่อคือจะเริ่มแบ่งส่วนของจุดในปริภูมิจากมิติที่มี (variance) ของจุดสูงที่สุด แล้วแบ่งจุดออกเป็น 2 กลุ่มที่มีจำนวนจุดในแต่ละกลุ่มเท่ากัน แล้วในแต่ละกลุ่มก็จะทำการแบ่งเช่นนี้ลงไปเรื่อย ๆ จนสุด ซึ่งจะเหลือจุดเพียงจุดเดียว แล้วเก็บข้อมูลการแบ่งแต่ละขั้นเป็นปม เชื่อมกันเป็นต้นไม้ อย่างไรก็ตาม รายละเอียดในการนำไปใช้งานจริงอาจจะไม่ตายตัว ขึ้นอยู่กับการออกแบบของนักเขียนโปรแกรมด้วย อย่างเช่น หลักในการแบ่งครึ่งว่าจะหาจุดที่อยู่กึ่งกลางที่สุดในมิตินั้นแล้วแบ่งครึ่งที่จุดนั้นหรือแบ่งที่ค่ามัธยฐานของจุดในมิตินั้นแทน ซึ่งจะได้จุดอยู่ในปมใบ (leaf node) ของต้นไม้แทนที่จะได้จุดอยู่ประจำปมทุกปมในต้นไม้ โดยสำหรับการค้นแบบเบสท์บินเฟิร์สท์นี้จะใช้วิธีการแบ่งอย่างหลัง คือแบ่งที่ค่ามัธยฐาน เพื่อให้ปมที่มีจุดเป็นใบของต้นไม้ แต่ให้สังเกตด้วยว่าปมใบแต่ละปมนี้ ไม่ได้แทนจุด 1 จุด แต่แทนส่วนของปริภูมิที่ถูกแบ่งจนเหลือส่วนที่มีจุดอยู่ภายในเพียง 1 จุด
ขั้นตอนวิธีของเบสท์บินเฟิร์สท์
ขั้นตอนวิธีในการค้นแบบเบสท์บินเฟิร์สท์นี้จะเป็นการนำ (k-d tree) มาประยุกต์ใช้กับการค้นหาจุดที่อยู่ใกล้ที่สุดโดยประมาณ โดยข้อมูลที่ได้รับมาคือเซตของจุดในปริภูมิ d มิติ และจุด q ซึ่งเป็นจุดที่ต้องการสอบถาม (query point) สิ่งที่ขั้นตอนวิธีนี้จะคืนกลับมาคือจุดในเซตที่อยู่ใกล้กับจุด q มากที่สุด เริ่มจากทำการแบ่งส่วนของปริภูมิตามข้อมูลจุดที่ได้รับมาเพื่อสร้างเป็นต้นไม้เคดีดังที่ได้กล่าวไว้ในหัวข้อต้นไม้เคดี เมื่อสร้างเสร็จจะได้ว่าข้อมูลของจุดทุกจุดในเซตจะเป็นใบของต้นไม้ (tree) นั่นคือ ปมใบทุกปมของต้นไม้จะมีจุดในเซตเพียง 1 จุดเท่านั้น ยกเว้นปมที่มีจุด q อยู่ จะมี 2 จุด ได้แก่ จุดในเซตและจุด q ให้หาว่าจุด q นั้นอยู่ในปมใบใดของต้นไม้แล้วกำหนดทรงกลม n มิติที่มีรัศมีเป็นระยะจากจุด q ถึงจุดที่อยู่ในปมใบเดียวกันเป็นการจำกัดระยะจากจุด q ที่จะใช้ค้นหาจุดที่อยู่ใกล้ที่สุด แล้วก็จะวนหาจุดดังกล่าวโดยการท่องไปในต้นไม้เพื่อที่จะไปยังปมใบแต่ละปมที่อยู่ภายในรัศมี อย่างไรก็ตาม เนื่องจากเบสท์บินเฟิร์สท์เป็นการค้นหาโดยประมาณ จึงมีการจำกัดจำนวนครั้งที่จะใช้ค้นหา หรือพูดในอีกนัยหนึ่งก็คือจำกัดจำนวนปมใบที่จะทำการเทียบหาระยะกับจุด q นั่นเอง นอกจากนี้ เพื่อเพิ่มประสิทธิภาพในการค้น จะมีการใช้แถวคอยลำดับความสำคัญ (priority queue) ในการจัดลำดับปมใบที่จะค้นด้วย โดยจัดลำดับจากระยะจากขอบของปมใบนั้นในปริภูมิไปยังจุด q ดังนั้นนอกจากจะมีการจำกัดจำนวนครั้งที่จะใช้ค้นแล้ว ยังเริ่มค้นจากปมใบที่อยู่ใกล้ที่สุดก่อนด้วย (วัดระยะจากจุด q ถึงขอบส่วนของปมใบ ไม่ใช่วัดถึงจุดกึ่งกลางของปมใบ) จึงเป็นที่มาของชื่อเบสท์บินเฟิร์สท์ (best bin first) โดยที่คำว่าบิน (bin) มาจากคำว่าทวิภาค (binary) ซึ่งหมายถึงการแบ่งส่วนของปริภูมิตามหลักของต้นไม้เคดีที่จะแบ่งออกครั้งละสองส่วนลงไปเรื่อย ๆ จนถึงส่วนของปริภูมิที่มีจุดเพียงจุดเดียว (ไม่นับจุด q) โดยที่มีการทดลองแล้วว่าค่าของจุดที่อยู่ใกล้ที่สุดโดยประมาณที่ได้จากขั้นตอนวิธีของเบสท์บินเฟิร์สท์นั้นมีความแม่นยำสูงพอที่จะนำไปประยุกต์ใช้ในทางปฏิบัติ และสามารถสรุปการทำงานเป็นรหัสเทียม (pseudocode) ได้ดังนี้
BestBinFirst(S,q) input: S = เซตของจุดในปริภูมิ d มิติ, q = จุดที่ต้องการสอบถาม (query point) output: c = จุดที่อยู่ในเซต S ที่อยู่ใกล้จุด q มากที่สุด 1: ให้ kdtree เป็นต้นไม้เคดี (k-d tree) ที่เกิดจากการแบ่งส่วนปริภูมิตามเซต S 2: ให้ c เป็นจุดที่อยู่ในปมใบเดียวกันกับจุด q 3: ให้ Dc เป็นระยะจากจุด q ไปยังจุด c 4: ให้ Em เป็นจำนวนปมใบที่จะทำการค้น 5: ให้ PQ เป็นแถวคอยลำดับความสำคัญ (priority queue) ที่เรียงลำดับตามความใกล้จากจุด q ถึงขอบของปมใบ 6: ทำการ enqueue ปมใบที่มีระยะจากจุด q ภายในรัศมี Dc 7: สำหรับ i = 1 ถึง Em { 8: ถ้า PQ.empty() ให้ break 9: ให้ b = PQ.removeMin() 10: ถ้า จุด b อยู่ใกล้จุด q มากกว่าจุด c ให้ c = b } 11: return c ประสิทธิภาพในการทำงาน
จากรหัสเทียม (pseudocode) ด้านบน จะเห็นว่าภาระในการทำงานของขั้นตอนวิธีนี้จะตกอยู่ที่บรรทัดที่ 1 คือการสร้าง (k-d tree) ซึ่งมีประสิทธิภาพในการทำงานเป็น O(n log2 n) เมื่อมีการใช้ขั้นตอนวิธีการเรียงลำดับที่มีประสิทธิภาพเป็น O(n log n) ในการหาค่ามัธยฐาน ส่วนบรรทัดที่ 5 นั้นจริง ๆ ก็มีภาระการทำงานที่หนักเช่นกัน แต่เนื่องจากได้มีการคัดปมใบออกไปจากการจำกัดค่ารัศมี Dc ซึ่งสามารถคัดกรณีที่ไม่จำเป็นออกไปได้จำนวนมาก ภาระในการทำงานส่วนนี้จึงเบาขึ้นมาก และส่วนที่ใช้ในการค้นจุดที่อยู่ใกล้ที่สุดจริง ๆ มีประสิทธิภาพในการทำงานเป็น O(1) เนื่องจากมีการจำกัดจำนวนครั้งในการหาแน่นอนว่าไม่เกิน Em ครั้ง เพราะฉะนั้นโดยรวมแล้วขั้นตอนวิธีนี้จึงค้นได้เร็วมาก
ตัวอย่างการใช้งาน : การรู้จำวัตถุโดยใช้การตรวจหาลักษณะเด่นแบบซิฟท์
การตรวจหาลักษณะเด่นแบบซิฟท์ (SIFT) เป็นวิธีการทางคอมพิวเตอร์วิทัศน์ (computer vision) ในการตรวจหาลักษณะเด่น (feature detection) ซึ่งสามารถนำมาประยุกต์ใช้ในเรื่องการรู้จำวัตถุ (object recognition) โดยที่จะทำการแปลงข้อมูลรูปภาพที่ได้มาเพื่อหาจุดที่มีลักษณะเด่น (keypoint) ของรูปนั้น โดยที่ข้อมูลของจุดลักษณะเด่นนี้สุดท้ายจะถูกแปลงเป็นจุดในปริภูมิ 128 มิติ เพื่อใช้เป็นตัวบอกจุดลักษณะสำคัญ (keypoint descriptor) ที่มีความเป็นเอกลักษณ์สูง เมื่อต้องการเทียบรูปวัตถุกับรูปภาพที่ได้มาว่ามีวัตถุอยู่ในรูปภาพดังกล่าวหรือไม่ ก็จะทำการหาจุดลักษณะเด่น (keypoint) และตัวบอกจุดลักษณะสำคัญ (keypoint descriptor) แล้วนำมาหาระยะทางแบบยุคลิด (Euclidean distance) ระหว่างตัวบอกจุดลักษณะสำคัญด้วยกัน ถ้าจุดที่อยู่ใกล้ที่สุดอยู่ใกล้กว่าระยะที่กำหนดไว้ก็จะถือว่าจุดลักษณะเด่นของทั้ง 2 รูปเป็นจุดเดียวกัน โดยจะสังเกตได้ว่าตัวบอกจุดลักษณะสำคัญนี้เป็นการเก็บข้อมูลจุดในปริภูมิที่มีจำนวนมิติสูงมาก คือ 128 มิติ ดังนั้นเพื่อเพิ่มประสิทธิภาพในการค้น จึงใช้การค้นแบบเบสท์บินเฟิร์สท์เพื่อค้นจุดที่อยู่ใกล้ที่สุดดังกล่าว
ดูเพิ่ม
- Nearest neighbor search
- k-d tree
- Feature detection
- SIFT
อ้างอิง
- 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.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
karkhnaebbebsthbinefirsth xngkvs Best Bin First epnkhntxnwithikarkhnhathiichinkarhacudthixyuiklthisud nearest neighbor search odypramaninpriphumihlaymiti odykhntxnwithinimikarprayuktmacak k d tree thaihkarkhnmiprasiththiphaphaelaerwmakkhun nxkcakniyngepnkhntxnwithikarkhnhathisamarthnaipichidcringinthangptibti xyangechn ichkbkartrwchalksnaednaebbsifth SIFT sungepnhnunginkhntxnwithiinkartrwchalksnaedn feature detection ineruxngkhxmphiwetxrwithsn computer vision thimakarkhnaebbebsthbinefirsthnimithimacakpyhakarhacudthixyuiklthisud nearest neighbor search sungkhntxnwithikarkhnhanithukkhidkhnkhunmaephuxephimkhwamerwinkarkhninpriphumithimihlaymiti aelamikhwamaemnyamakphxthicanaipichcring odyhlkkarsakhyxyanghnungthiebsthbinefirsthnamaichkhuxkarekbkhxmulcudinpriphumidwy k d tree pyhakarhacudthixyuiklthisud 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 khuxkarich k d tree sungepnkaraebngpriphumixxkepnswn ephuxekbkhxmulepntnim tree karekbkhxmulepntnimnikthaihsamarthkhnkhxmulidrwderwechnkn aelathuknamaichinkarkhnaebbebsthbinefirsthdwy tnimekhdi k d tree epnokhrngsrangkhxmulthiichinkaraebngswninpriphumiinrupkhxngtnim tree ephuxephimprasiththiphaphinkarkhn hlkkarthanganodyyxkhuxcaerimaebngswnkhxngcudinpriphumicakmitithimi 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 cudkhntxnwithikhxngebsthbinefirsthkhntxnwithiinkarkhnaebbebsthbinefirsthnicaepnkarna 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 estkhxngc u dinpr i ph u m i d m i t i q c u dth i t xngkarsxbtham query point output c c u dth i xy u inest S th i xy u ikl c u d q makth i s u d 1 ih kdtree ep nt nim ekhd i k d tree th i ek i dcakkaraeb ngs wnpr i ph u m i tamest S 2 ih c ep nc u dth i xy u inpmibed i ywk nk bc u d q 3 ih Dc ep nrayacakc u d q ipy ngc u d c 4 ih Em ep ncanwnpmibth i cathakarkh n 5 ih PQ ep naethwkhxylad bkhwamsakh y priority queue th i er i ynglad btamkhwamikl cakc u d q th u ngkhxbkhxngpmib 6 thakar enqueue pmibth i m i rayacakc u d q phayinr sm i Dc 7 sahr b i 1 th u ng Em 8 th a PQ empty ih break 9 ih b PQ removeMin 10 th a c u d b xy u ikl c u d q makkw ac u d c ih c b 11 return cprasiththiphaphinkarthangancakrhsethiym pseudocode danbn caehnwapharainkarthangankhxngkhntxnwithinicatkxyuthibrrthdthi 1 khuxkarsrang 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 karrucawtthuodyichkartrwchalksnaednaebbsifthkartrwchalksnaednaebbsifth 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 cungichkarkhnaebbebsthbinefirsthephuxkhncudthixyuiklthisuddngklawduephimNearest neighbor search k d tree Feature detection SIFTxangxingBeis 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