ปัญหาการจับคู่ซึ่งเป็นพื้นฐานสำหรับการคำนวณการไหลของแสงและการจับคู่สเตอริโอ เป็นปัญหาพื้นฐานใน การ ประมวลผลภาพ^{[ 1 ]}หมายถึงปัญหาในคอมพิวเตอร์วิชั่นในการตรวจสอบว่าส่วนใดของภาพหนึ่งตรงกับส่วนใดของภาพอื่น^{[ 2 ]}โดยความแตกต่างเกิดจากการเคลื่อนไหวของกล้อง การผ่านไปของเวลา และ/หรือการเคลื่อนไหวของวัตถุในภาพถ่าย ปัญหานี้เกี่ยวข้องกับการลงทะเบียนภาพซึ่งเกี่ยวกับการค้นหาการแปลงทางเรขาคณิตที่จัดเรียงจุดที่สอดคล้องกันให้ทับซ้อนกัน

อาจกล่าวได้ว่าการจับคู่ภาพเป็นองค์ประกอบพื้นฐานที่สำคัญในแอปพลิเคชันที่เกี่ยวข้องมากมาย เช่นการไหลของแสง (ซึ่งภาพสองภาพเกิดขึ้นต่อเนื่องกันตามเวลา) การมองเห็นแบบสเตอริโอ หนาแน่น (ซึ่งภาพสองภาพมาจากกล้องสเตอริโอคู่หนึ่ง) การสร้างโครงสร้างจากภาพเคลื่อนไหว (SfM) และ Visual SLAM (ซึ่งภาพมาจากมุมมองที่แตกต่างกันแต่ทับซ้อนกันบางส่วนของฉาก) และการจับคู่ภาพข้ามฉาก (ซึ่งภาพมาจากฉากที่แตกต่างกันโดยสิ้นเชิง)

วิธีง่ายๆ ในการค้นหาการจับคู่คือPatchMatchอัลกอริทึมการจับคู่สมัยใหม่ใช้เครือข่ายประสาทเทียมเพื่อค้นหาการจับคู่ได้อย่างรวดเร็วและมีความแม่นยำสูง นักวิจัยด้านคอมพิวเตอร์วิชั่นที่มีอิทธิพล อย่าง Takeo Kanadeเคยกล่าวไว้ว่าปัญหาพื้นฐานสามประการของคอมพิวเตอร์วิชั่นคือ “การจับคู่ การจับคู่ และการจับคู่!” ^{[ 3 ]}อย่างไรก็ตาม ปัญหานี้ถือว่าได้รับการแก้ไขแล้ว

เมื่อมีภาพสามมิติเดียวกันสองภาพขึ้นไปที่ถ่ายจากมุมมองที่แตกต่างกัน ปัญหาการจับคู่หมายถึงการหาชุดจุดในภาพหนึ่งที่สามารถระบุได้ว่าเป็นจุดเดียวกันในอีกภาพหนึ่ง ในการทำเช่นนี้จุดหรือคุณลักษณะในภาพหนึ่งจะถูกจับคู่กับจุดหรือคุณลักษณะในอีกภาพหนึ่ง เพื่อสร้างจุดที่สอดคล้องกันหรือคุณลักษณะที่สอดคล้องกันซึ่งเรียกอีกอย่างว่าจุดหรือคุณลักษณะที่เหมือนกันภาพเหล่านั้นอาจถ่ายจากมุมมองที่แตกต่างกัน ในช่วงเวลาที่แตกต่างกัน หรือมีวัตถุในฉากเคลื่อนที่โดยทั่วไปสัมพันธ์กับกล้อง การหาพิกเซลที่สอดคล้องกันในภาพสเตอริโอเรียกว่าปัญหาการจับคู่ ผลลัพธ์ที่ได้มักจะเป็นแผนที่ความเหลื่อมล้ำ ซึ่งเวกเตอร์การกระจัดไปยังพิกเซลที่สอดคล้องกันของอีกภาพหนึ่งจะถูกกำหนดสำหรับแต่ละพิกเซลของภาพหนึ่ง เพื่อจุดประสงค์นี้ จำเป็นต้องสร้างการจับคู่ที่ไม่ซ้ำกันระหว่างจุดของภาพแต่ละภาพ เนื่องจากการกำหนดพิกเซลอาจมีความคลุมเครือสูงและไม่สามารถทำได้เสมอไป ปัญหาการจับคู่จึงถูกเรียกว่าปัญหา "ที่ตั้งไว้ไม่ดี" ตามคำจำกัดความของHadamard ^{[ 4 ]}ยิ่งไปกว่านั้น การแก้ปัญหาการจับคู่ยังทำได้ยากขึ้นเนื่องจากการบิดเบือนมุมมอง เสียงรบกวน และความแตกต่างของแสงและความคมชัดระหว่างภาพ

ปัญหาการจับคู่ภาพสามารถเกิดขึ้นได้ในสถานการณ์สเตอริโอเมื่อใช้ภาพสองภาพของฉากเดียวกัน หรือสามารถขยายไปสู่ปัญหาการจับคู่ภาพแบบ N มุมมองได้ ในกรณีหลัง ภาพอาจมาจากกล้อง N ตัวที่ถ่ายภาพพร้อมกัน หรือจากกล้องตัวเดียวที่เคลื่อนที่สัมพันธ์กับฉาก ปัญหานี้จะยากขึ้นเมื่อวัตถุในฉากเคลื่อนที่สัมพันธ์กับกล้อง

การประยุกต์ใช้ปัญหาการจับคู่จุดที่พบได้ทั่วไปคือ การสร้างภาพ พาโนรามาหรือการต่อภาพ — เมื่อต้องการต่อภาพสองภาพขึ้นไปที่มีส่วนที่ทับซ้อนกันเพียงเล็กน้อย ให้เป็นภาพขนาดใหญ่ขึ้น ในกรณีนี้ จำเป็นต้องสามารถระบุชุดจุดที่สอดคล้องกันในภาพคู่หนึ่ง เพื่อคำนวณการแปลงภาพหนึ่งไปต่อกับอีกภาพหนึ่ง

หนึ่งในแหล่งที่มาของข้อผิดพลาดที่สำคัญที่สุดในการกำหนดการจับคู่ภาพสามมิติคือการมีพื้นที่ในฉากที่มองเห็นได้จากมุมมองของกล้องเพียงตัวเดียว สำหรับพื้นที่ภาพที่แมปบริเวณเหล่านี้ของฉาก จะไม่มีองค์ประกอบที่สอดคล้องกันในภาพสามมิติอื่น พื้นที่ภาพเหล่านี้เรียกว่าสิ่งกีดขวาง หากไม่คำนึงถึงสิ่งกีดขวางอย่างเพียงพอในระหว่างการกำหนดการจับคู่ จะเกิดการแก้ไขที่ไม่ถูกต้องมากหรือน้อยขึ้นอยู่กับวิธีการ ส่งผลให้การสร้างความลึกไม่ถูกต้อง ดังนั้น สิ่งกีดขวางจึงเป็นปัญหาสำคัญในการประมวลผลภาพสามมิติ^{[ 6 ]}

ในเรขาคณิตสเตอริโอที่มีแกนแสงขนานกัน การเคลื่อนที่ของจุดภาพที่สอดคล้องกันในคู่ภาพสเตอริโอจะขนานกับฐานสเตอริโอเสมอ ด้วยความรู้ที่แม่นยำเกี่ยวกับเรขาคณิตของกล้อง ทิศทางของความเหลื่อมล้ำสามารถกำหนดล่วงหน้าได้ จึงทำให้การค้นหาจุดภาพที่สอดคล้องกันง่ายขึ้นอย่างมาก อย่างไรก็ตาม บริเวณภาพที่ไม่มีโครงสร้างหรือการเปลี่ยนแปลงความเข้มเกิดขึ้นในทิศทางของฐานสเตอริโอถือเป็นปัญหา ในกรณีนี้ จะไม่สามารถตรวจจับการเคลื่อนที่ของจุดภาพที่สอดคล้องกันได้ เนื่องจากการตรวจจับการเคลื่อนที่ในสเตอริโอสโคปีมักจะดำเนินการโดยผู้ปฏิบัติงานในพื้นที่ โดยไม่สนใจส่วนที่เหลือของฉาก ปัญหานี้จึงถือเป็นกรณีพิเศษของปัญหาที่เรียกว่าปัญหารูรับแสง ซึ่งมีความสำคัญอย่างยิ่งในการวิเคราะห์การเคลื่อนไหว (การไหลของแสง) ^{[ 7 ]}

เนื่องจากลักษณะเฉพาะของมัน ปัญหาการจับคู่ เช่นเดียวกับปัญหาที่ไม่เหมาะสมอื่นๆ อีกมากมาย สามารถแก้ไขได้เพียงวิธีเดียวโดยการใช้ความรู้เบื้องต้นที่เหมาะสม ด้วยความช่วยเหลือของความรู้เบื้องต้นนี้ พื้นที่คำตอบจะลดลงอย่างเหมาะสม และปัญหาจะถูกแปลงเป็นปัญหาที่ "เหมาะสม" ^{[ 4 ]}ข้อจำกัดของพื้นที่คำตอบเกี่ยวข้องกับกระบวนการสร้างภาพและเรขาคณิตของกล้องที่ใช้ (ข้อจำกัดด้านเอพิโพลาร์และความเป็นเอกลักษณ์) ในด้านหนึ่ง และในอีกด้านหนึ่ง เกี่ยวข้องกับคุณสมบัติที่คาดการณ์ไว้ของฉากที่สังเกต (ข้อจำกัดด้านความต่อเนื่อง ลำดับ และการไล่ระดับ)

การกำหนดองค์ประกอบภาพที่สอดคล้องกันในการประมวลผลภาพดิจิทัลสามารถทำได้โดยใช้อัลกอริธึมและวิธีการทางคณิตศาสตร์ต่างๆ วิธีการเหล่านี้มีความแตกต่างกัน บางครั้งอาจแตกต่างกันอย่างมาก ในด้านความเสี่ยงต่อข้อผิดพลาดและความพยายามในการคำนวณที่จำเป็น

ในวิธีการแบบอิงพื้นที่ พื้นที่ภาพแต่ละส่วนของภาพสเตอริโอจะถูกกำหนดตามค่าระดับสีเทาหรือสภาพแวดล้อมเฉพาะที่ของพิกเซล การจับคู่ของพื้นที่ภาพมักจะถูกกำหนดโดยการคำนวณค่าความคล้ายคลึงกัน เช่น การหาความสัมพันธ์ไขว้เฉพาะที่ ในกรณีที่ง่ายที่สุด ความแตกต่างเกิดขึ้นจากการเลื่อนของบริเวณภาพระหว่างภาพด้านซ้ายและด้านขวาที่แสดงระดับการจับคู่ที่ดีที่สุด วิธีการเหล่านี้บางวิธีใช้ตัวดำเนินการที่สนใจเพื่อเลือกพื้นที่ที่มีคุณสมบัติเฉพาะจากแต่ละภาพก่อนที่จะกำหนดการจับคู่ จากนั้นจึงรวมพื้นที่เหล่านี้เข้าด้วยกัน^{[ 8 ]}

วิธีการสร้างภาพสามมิติที่มีอยู่ส่วนใหญ่สามารถจัดอยู่ในประเภทวิธีการที่ใช้คุณลักษณะเป็นพื้นฐาน เทคนิคนี้เกี่ยวข้องกับการสกัดคุณลักษณะจากข้อมูลภาพที่อธิบายภาพในระดับนามธรรมมากขึ้นก่อน จากนั้นจึงทำการวิเคราะห์ความสอดคล้องกันในระดับคุณลักษณะ คุณลักษณะที่ใช้กันทั่วไป ได้แก่ ขอบ เส้น หรือจุดยอด และส่วนของขอบหรือเส้น ตัวกรองความแตกต่าง ซึ่งสกัดความแปรผันของระดับสีเทา เช่น ขอบหรือเส้นจากสัญญาณภาพ มีความสำคัญอย่างยิ่งในวิธีการเหล่านี้^{[ 9 ]}

พื้นฐานของวิธีการที่เรียกว่าวิธีการวัดความเหลื่อมล้ำแบบใช้เฟส คือ ทฤษฎีการกระจัดของการแปลงฟูริเยร์อย่างไรก็ตาม ในการประมวลผลภาพสเตอริโอ การเลื่อนภาพโดยรวมอย่างสมบูรณ์ระหว่างภาพนั้นโดยทั่วไปเป็นไปไม่ได้ เนื่องจากวัตถุที่อยู่ห่างจากระบบกล้องในระยะต่างๆ จะแสดงค่าความเหลื่อมล้ำที่แตกต่างกันในภาพสเตอริโอ ดังนั้น การเลื่อนของพื้นที่ภาพที่สอดคล้องกันในคู่ภาพสเตอริโอจะต้องถูกกำหนดโดยใช้ตัวดำเนินการเฉพาะที่ เพื่อให้ความสัมพันธ์ของเฟสโดยทั่วไปมีความหมายเฉพาะเมื่อใช้ร่วมกับการแปลงฟูริเยร์ที่จำกัดเฉพาะพื้นที่ภาพที่เล็กกว่า วิธีการที่สำคัญที่สุดในบรรดาวิธีการแบบใช้เฟสคือ วิธีการที่เรียกว่า วิธีการหาความแตกต่างของเฟส ด้วยเทคนิคเหล่านี้ ข้อมูลเฟสจะถูกดึงมาจากผลตอบสนองของคู่ตัวกรองเชิงซ้อนที่ใช้ในการกรองภาพอินพุต ข้อกำหนดสำคัญสำหรับวิธีนี้คือ เฟสของผลตอบสนองของตัวกรองจะต้องเป็นฟังก์ชันเชิงเส้นโดยประมาณของตำแหน่ง คุณสมบัตินี้สามารถเกิดขึ้นได้หากฟังก์ชันการถ่ายโอนของตัวกรองไม่มีค่าชดเชยและหายไปสำหรับความถี่ลบ คุณสมบัตินี้เรียกว่า พฤติกรรมแบบควอดราเจอร์^{[ 10 ]}เนื่องจากข้อมูลเฟสไม่เปลี่ยนแปลงเมื่อเทียบกับแอมพลิจูดของการตอบสนองของตัวกรอง วิธีการที่ใช้เฟสจึงมีความทนทานต่อความแตกต่างของแสงและความคมชัดระหว่างดวงตาค่อนข้างมาก อย่างไรก็ตาม เนื่องจากความกำกวมในการคำนวณเฟส จึงสามารถวัดค่าความเหลื่อมล้ำได้สูงสุดเพียงครึ่งหนึ่งของความยาวคลื่นการมอดูเลชันของตัวกรองที่ใช้เท่านั้น เช่นเดียวกับวิธีการอื่นๆ วิธีการที่ใช้เฟสก็มีความไวต่อการบดบังมากเช่นกัน^{[ 6 ]}

ตามข้อจำกัดเรื่องความเป็นเอกลักษณ์ พิกเซลแต่ละพิกเซลสามารถกำหนดค่าความเหลื่อมล้ำได้เพียงค่าเดียวเท่านั้น และด้วยเหตุนี้จึงมีตำแหน่งในพื้นที่ที่พิจารณาได้มากที่สุดเพียงตำแหน่งเดียว (ไม่รวมพื้นผิวโปร่งแสง) อย่างไรก็ตาม ความกำกวมไม่สามารถตัดออกไปได้ด้วยวิธีการใดๆ ที่ใช้ในระดับท้องถิ่นหรือคุณลักษณะ (พื้นที่ที่คล้ายคลึงกันมากที่สุดในภาพสเตอริโอไม่จำเป็นต้องอยู่ด้วยกันเสมอไป) มีการใช้วิธีการต่างๆ เพื่อแก้ปัญหานี้ ขึ้นอยู่กับแนวทาง: ในวิธีการที่เรียกว่าการปรับค่าให้เป็นระเบียบ (regularization methods) จะมีการกำหนดฟังก์ชันต้นทุนหรือพลังงาน โดยคำนึงถึงข้อจำกัด (ดูพื้นฐาน) จากนั้นจึงค้นหาค่าต่ำสุดทั่วโลกภายในฟังก์ชันเหล่านี้ อีกแนวทางหนึ่งคือวิธีการผ่อนคลาย (relaxation methods) ในวิธีการส่วนใหญ่ที่ใช้วิธีนี้ในภาพสเตอริโอ คุณลักษณะหรือบริเวณภาพที่มีคุณสมบัติพิเศษจะถูกแยกออกมาจากข้อมูลภาพก่อน จากนั้นจะกำหนดสิ่งที่เรียกว่าโหนดให้กับพิกเซลภาพที่องค์ประกอบเหล่านี้ปรากฏอยู่ แต่ละโหนดเหล่านี้จะมีชุดตัวแปร ซึ่งแต่ละตัวแปรแสดงถึงความสัมพันธ์ระหว่างโหนดนั้นๆ กับองค์ประกอบต่างๆ ในภาพอื่น ตัวแปรเหล่านี้ถูกตีความว่าเป็นความน่าจะเป็น^{[ 1 ]}หรือเป็นกิจกรรมของเซลล์ประสาท^{[ 4 ]} (เครือข่ายประสาท) ขึ้นอยู่กับวิธีการ ในช่วงเริ่มต้นของกระบวนการผ่อนคลายจริง ตัวแปรจะถูกกำหนดค่าเริ่มต้นตามความคล้ายคลึงกันของคุณลักษณะหรือค่าพิกเซลที่สอดคล้องกัน ต่อมา ค่าของตัวแปรจะได้รับการอัปเดตซ้ำๆ ในกระบวนการแบบไดนามิก โดยการละเมิดข้อจำกัดจะมีผลยับยั้งหรือลดลง และการปฏิบัติตามข้อจำกัดจะมีผลเสริมแรง แผนที่ความแตกต่างที่ชัดเจนจะพร้อมใช้งานเมื่อถึงสภาวะคงที่ การใช้การเชื่อมต่อที่เหมาะสม การระบุผิดพลาดที่เกิดจากการบดบังสามารถระงับได้ด้วยวิธีนี้เช่นกัน^{[ 5 ]}

ในวิทยาการคอมพิวเตอร์ด้านการมองเห็น ปัญหาการจับคู่จุดจะถูกศึกษาในกรณีที่คอมพิวเตอร์ควรแก้ปัญหานี้โดยอัตโนมัติโดยใช้เพียงภาพเป็นข้อมูลป้อนเข้า เมื่อแก้ปัญหาการจับคู่จุดได้แล้ว และได้ชุดจุดภาพที่สอดคล้องกัน ก็สามารถนำวิธีการอื่นมาใช้กับชุดจุดนี้เพื่อสร้างตำแหน่ง การเคลื่อนที่ และ/หรือการหมุนของจุด 3 มิติที่สอดคล้องกันในฉากได้

ปัญหาการจับคู่ยังเป็นพื้นฐานของ เทคนิคการวัด ความเร็วภาพอนุภาคซึ่งปัจจุบันใช้กันอย่างแพร่หลายใน สาขา กลศาสตร์ของไหลเพื่อวัดการเคลื่อนที่ของไหลในเชิงปริมาณ

• สเตอริโอสโคปี
• พารัลแลกซ์
• การถ่ายภาพทางอากาศ
• การรับรู้เชิงลึก
• การมองเห็นสามมิติ
• วิชั่นคอมพิวเตอร์
• เมทริกซ์พื้นฐาน
• อัลกอริทึมการแยกสาขาและขอบเขตความเข้ากันได้ร่วม
• เรขาคณิตเอพิโพลาร์
• การลงทะเบียนภาพ
• ความแตกต่างระหว่าง Birchfield และ Tomasi
• การแปลงคุณลักษณะที่ไม่ขึ้นกับมาตราส่วน (SIFT)

• หน้าเว็บ Middlebury Stereo Vision