Triangulation (computer vision)
کمپیوٹر وژن میں، مثلث سے مراد تھری ڈی اسپیس میں کسی نقطہ کا تعین کرنے کا عمل ہے جس میں اس کے پروجیکشنز کو دو، یا زیادہ، تصاویر پر دیا جاتا ہے۔ اس مسئلے کو حل کرنے کے لیے اس میں شامل کیمروں کے لیے 3D سے 2D تک کیمرہ پروجیکشن فنکشن کے پیرامیٹرز کو جاننا ضروری ہے، آسان ترین صورت میں جس کی نمائندگی کیمرہ میٹرکس کرتے ہیں۔ مثلث کو بعض اوقات تعمیر نو یا چوراہا بھی کہا جاتا ہے۔ مثلث کا مسئلہ اصولی طور پر معمولی ہے۔ چونکہ کسی تصویر کا ہر نقطہ تھری ڈی جگہ میں ایک لکیر سے مطابقت رکھتا ہے، اس لیے تھری ڈی میں لائن کے تمام نکات کو تصویر کے نقطہ پر پیش کیا جاتا ہے۔ اگر دو، یا زیادہ تصاویر میں متعلقہ پوائنٹس کا ایک جوڑا پایا جا سکتا ہے، تو یہ معاملہ ہونا چاہیے کہ وہ ایک عام 3D پوائنٹ x کا پروجیکشن ہیں۔ امیج پوائنٹس سے پیدا ہونے والی لائنوں کے سیٹ کو x (3D پوائنٹ) پر کاٹنا چاہیے اور x (3D پوائنٹ) کے نقاط کی الجبرائی تشکیل کو مختلف طریقوں سے شمار کیا جا سکتا ہے، جیسا کہ ذیل میں پیش کیا گیا ہے۔ تاہم، عملی طور پر، امیج پوائنٹس کے نقاط کو من مانی درستگی کے ساتھ نہیں ماپا جا سکتا۔ اس کے بجائے، مختلف قسم کے شور، جیسے کہ لینس کی مسخ سے ہندسی شور یا انٹرسٹ پوائنٹ کا پتہ لگانے کی غلطی، پیمائش شدہ امیج کوآرڈینیٹس میں غلطیوں کا باعث بنتی ہیں۔ نتیجے کے طور پر، متعلقہ تصویری نکات سے پیدا ہونے والی لکیریں ہمیشہ 3D جگہ میں ایک دوسرے کو نہیں کاٹتی ہیں۔ اس کے بعد مسئلہ یہ ہے کہ ایک تھری ڈی پوائنٹ تلاش کیا جائے جو پیمائش شدہ امیج پوائنٹس پر بہتر طور پر فٹ ہو۔ ادب میں متعدد تجاویز ہیں کہ کس طرح اصلاح کی وضاحت کی جائے اور کس طرح زیادہ سے زیادہ تھری ڈی پوائنٹ تلاش کیا جائے۔ چونکہ وہ مختلف اصلاح کے معیار پر مبنی ہوتے ہیں، اس لیے جب شور شامل ہوتا ہے تو مختلف طریقے 3D پوائنٹ x کے مختلف تخمینے تیار کرتے ہیں۔ تعارف درج ذیل میں، یہ فرض کیا جاتا ہے کہ پن ہول کیمروں سے پیدا ہونے والے دو نظاروں سے متعلقہ تصویری نکات پر مثلث بنایا جاتا ہے۔ ان مفروضوں کی عمومی شکل پر یہاں بحث کی گئی ہے۔ بائیں طرف کی تصویر پن ہول ماڈل کے سٹیریو کیمروں کی ایک جوڑی کی ایپی پولر جیومیٹری کی وضاحت کرتی ہے۔ تھری ڈی اسپیس میں ایک پوائنٹ ایکس (تھری ڈی پوائنٹ) کو متعلقہ امیج پلین پر ایک لکیر (سبز) کے ساتھ پیش کیا جاتا ہے جو کیمرے کے فوکل پوائنٹ سے گزرتا ہے، اور اس کے نتیجے میں دو متعلقہ امیج پوائنٹس اور۔ اگر اور دیا گیا ہے اور دونوں کیمروں کی جیومیٹری معلوم ہے، تو دو پروجیکشن لائنوں (سبز لکیروں) کا تعین کیا جا سکتا ہے اور یہ اس صورت میں ہونا چاہیے کہ وہ نقطہ x (3D نقطہ) پر ایک دوسرے کو کاٹتے ہیں۔ بنیادی لکیری الجبرا کا استعمال کرتے ہوئے کہ انٹرسیکشن پوائنٹ کا تعین سیدھے طریقے سے کیا جا سکتا ہے۔ دائیں طرف کی تصویر اصل کیس کو دکھاتی ہے۔ تصویر کی پوزیشن کی طرف اشارہ کرتا ہے اور اس کی پیمائش بالکل نہیں کی جا سکتی۔ وجہ جیومیٹرک مسخ جیسے عوامل کا مجموعہ ہے، مثال کے طور پر لینس کی مسخ، جس کا مطلب ہے کہ کیمرے کی 3D سے 2D میپنگ پن ہول کیمرہ ماڈل سے ہٹ جاتی ہے۔ کسی حد تک ان غلطیوں کی تلافی کی جا سکتی ہے، جس سے ایک بقیہ ہندسی غلطی رہ جاتی ہے۔ ایکس (تھری ڈی پوائنٹ) سے روشنی کی ایک واحد کرن پوائنٹ اسپریڈ فنکشن کے مطابق کیمروں کے لینس سسٹم میں منتشر ہوتی ہے۔ تصاویر میں بکھرے ہوئے شدت کے فنکشن کی پیمائش سے متعلقہ امیج پوائنٹ کی بازیابی غلطیاں دیتی ہے۔ ڈیجیٹل کیمرے میں، تصویر کی شدت کی تقریب کو صرف مجرد سینسر عناصر میں ماپا جاتا ہے۔ حقیقی فنکشن کو بازیافت کرنے کے لیے مجرد شدت فنکشن کی غیر درست انٹرپولیشن کا استعمال کرنا پڑتا ہے۔ مثلث کے لیے استعمال ہونے والے امیج پوائنٹس y1 'اور y2' اکثر مختلف قسم کے فیچر ایکسٹریکٹرز کا استعمال کرتے ہوئے پائے جاتے ہیں، مثال کے طور پر کونوں یا دلچسپی کے پوائنٹس۔ پڑوس کی کارروائیوں کی بنیاد پر کسی بھی قسم کی خصوصیت نکالنے کے لیے ایک موروثی لوکلائزیشن کی غلطی ہوتی ہے۔ نتیجے کے طور پر، پیمائش شدہ تصویری نکات اور کے بجائے اور ہیں۔ تاہم، ان کی پروجیکشن لائنیں (نیلی) کو 3D جگہ میں کاٹنا یا x کے قریب آنا ضروری نہیں ہے۔ در حقیقت، یہ لکیریں صرف اس صورت میں ایک دوسرے کو کاٹتی ہیں جب بنیادی میٹرکس کے ذریعہ بیان کردہ ایپی پولر رکاوٹ کو پورا کرتی ہیں۔ پیمائش کے شور کو دیکھتے ہوئے اور یہ امکان ہے کہ ایپی پولر رکاوٹ مطمئن نہیں ہے اور پروجیکشن لائنیں ایک دوسرے کو نہیں کاٹتی ہیں۔ یہ مشاہدہ اس مسئلے کی طرف لے جاتا ہے جو مثلث میں حل ہوتا ہے۔ کون سا 3D پوائنٹ xest دیا ہوا x اور کیمروں کی جیومیٹری کا بہترین تخمینہ ہے؟ جواب اکثر ایک غلطی کی پیمائش کی وضاحت کرکے پایا جاتا ہے جو xest پر منحصر ہوتا ہے اور پھر اس غلطی کو کم سے کم کرتا ہے۔ مندرجہ ذیل حصوں میں، ادب میں پیش کردہ xest کی کمپیوٹنگ کے کچھ مختلف طریقوں کو مختصر طور پر بیان کیا گیا ہے۔ مثلث کے تمام طریقے اس صورت میں xest = x پیدا کرتے ہیں اور، یعنی، جب ایپی پولر رکاوٹ پوری ہو جاتی ہے (سوائے واحد نکات کے، نیچے دیکھیں)۔ یہ تب ہوتا ہے جب رکاوٹ پوری نہیں ہوتی ہے جو طریقوں کے درمیان مختلف ہوتی ہے۔ خصوصیات مثلث کے طریقہ کار کو کسی فنکشن کے لحاظ سے اس طرح بیان کیا جا سکتا ہے کہ دریافت شدہ تصویری نکات کے یکساں نقاط کہاں ہیں اور کیمرہ میٹرکس کہاں ہیں۔ x (3D پوائنٹ) نتیجے میں آنے والے 3D پوائنٹ کی یکساں نمائندگی ہے۔ اس نشان کا مطلب یہ ہے کہ صرف ایک ویکٹر پیدا کرنے کی ضرورت ہے جو x کے برابر ہو اور غیر صفر اسکیلر کے ضرب تک ہو کیونکہ یکساں ویکٹر شامل ہوتے ہیں۔ مخصوص طریقوں، یعنی مخصوص افعال کو دیکھنے سے پہلے، ان طریقوں سے متعلق کچھ عمومی تصورات ہیں جن کی وضاحت کرنے کی ضرورت ہے۔ کسی خاص مسئلے کے لیے کون سا مثلث کا طریقہ منتخب کیا جاتا ہے اس کا انحصار کچھ حد تک ان خصوصیات پر ہوتا ہے۔ سنگلریٹیز کچھ طریقے x (3D پوائنٹ) کے تخمینے کو درست طریقے سے شمار کرنے میں ناکام رہتے ہیں اگر یہ 3D اسپیس کے کسی خاص ذیلی سیٹ میں واقع ہے، جو ان کے کچھ امتزاج سے مطابقت رکھتا ہے۔ اس ذیلی سیٹ میں ایک نقطہ پھر مثلث کے طریقہ کار کی انفرادیت ہے۔ ناکامی کی وجہ یہ ہو سکتی ہے کہ حل کیا جانے والا کچھ مساوات کا نظام کم متعین ہے یا یہ کہ xest کی پروجیکٹو نمائندگی واحد پوائنٹس کے لیے صفر ویکٹر بن جاتی ہے۔ کچھ ایپلی کیشنز میں، یہ مطلوب ہے کہ مثلث 3D پوائنٹس کی نمائندگی کرنے کے لیے استعمال ہونے والے کوآرڈینیٹ سسٹم سے آزاد ہو۔ اگر مثلث کا مسئلہ ایک کوآرڈینیٹ سسٹم میں وضع کیا جاتا ہے اور پھر دوسرے میں تبدیل ہو جاتا ہے تو اس کے نتیجے میں تخمینہ xest کو اسی طرح تبدیل ہونا چاہیے۔ اس خاصیت کو عام طور پر انواریینس کہا جاتا ہے۔ ہر مثلث کا طریقہ غیر متغیر کی یقین دہانی نہیں کرتا، کم از کم عام قسم کی مربوط تبدیلیوں کے لیے نہیں۔ 3D نقاط کی یکساں نمائندگی کے لیے، سب سے عام تبدیلی ایک پروجیکٹو تبدیلی ہے، جس کی نمائندگی میٹرکس کرتا ہے۔ اگر یکساں نقاط کو اس کے مطابق تبدیل کیا جاتا ہے تو کیمرہ میٹرکس کو یکساں یکساں تصویری نقاط (yk) پیدا کرنے کے لیے (Ck) کے طور پر تبدیل ہونا چاہیے۔ اگر مثلث فنکشن غیر متغیر ہے تو درج ذیل تعلق درست ہونا چاہیے جس سے سب کے لیے اس کی پیروی ہوتی ہے۔ ہر مثلث کے طریقہ کار کے لیے، اس بات کا تعین کیا جا سکتا ہے کہ آیا یہ آخری تعلق درست ہے۔ اگر ایسا ہے تو، یہ صرف پروجیکٹو تبدیلیوں کے ذیلی سیٹ کے لیے مطمئن ہو سکتا ہے، مثال کے طور پر، سخت یا افائن تبدیلیاں۔ کمپیوٹیشنل پیچیدگی فنکشن صرف ایک کمپیوٹیشن کی تجریدی نمائندگی ہے جو عملی طور پر نسبتا پیچیدہ ہو سکتی ہے۔ کچھ طریقوں کے نتیجے میں ایک بند شکل کا مسلسل فعل ہوتا ہے جبکہ دوسروں کو کمپیوٹیشنل مراحل کی ایک سیریز میں تحلیل کرنے کی ضرورت ہوتی ہے جس میں، مثال کے طور پر، ایس وی ڈی یا کثیر الجہتی کی جڑیں تلاش کرنا شامل ہیں۔ طریقوں کی ایک اور کلاس کے نتیجے میں کچھ پیرامیٹرز کے تکراری تخمینے پر انحصار کرنا ضروری ہے۔ اس کا مطلب یہ ہے کہ کمپیوٹیشن کا وقت اور اس میں شامل کارروائیوں کی پیچیدگی دونوں مختلف طریقوں کے درمیان مختلف ہو سکتی ہیں۔ میتھڈز مڈ پوائنٹ میتھڈ دونوں امیج پوائنٹس میں سے ہر ایک اور اس کی ایک متعلقہ پروجیکشن لائن ہے (اوپر دائیں تصویر میں نیلی)، جسے یہاں اور کے طور پر ظاہر کیا گیا ہے، جس کا تعین کیمرہ میٹرکس کو دیکھتے ہوئے کیا جا سکتا ہے۔ فرض کریں کہ ایک (3D لائن) L اور ایک x (3D پوائنٹ) کے درمیان فاصلہ فنکشن ایسا ہے جو اور کے درمیان یوکلڈین فاصلہ ہے۔ مڈپوائنٹ طریقہ نقطہ xest کو تلاش کرتا ہے جو کم سے کم کرتا ہے۔ یہ پتہ چلتا ہے کہ xest بالکل مختصر ترین لائن سیگمنٹ کے وسط میں واقع ہے جو دو پروجیکشن لائنوں میں شامل ہوتا ہے۔ ضروری میٹرکس کے ذریعے براہ راست لکیری تبدیلی وہاں حل کیا جانے والا مسئلہ یہ ہے کہ متعلقہ نارملائزڈ امیج کوآرڈینیٹس اور کو دیکھتے ہوئے حساب کیسے کیا جائے۔ اگر ضروری میٹرکس معلوم ہے اور متعلقہ گردش اور ترجمہ کی تبدیلیوں کا تعین کیا گیا ہے، تو یہ الگورتھم (لانگویٹ-ہیگنس کے مقالے میں بیان کیا گیا ہے) ایک حل فراہم کرتا ہے۔ چلو گردش میٹرکس کی صف k کی نشاندہی کرتے ہیں: دو کوآرڈینیٹ سسٹمز میں 3D کوآرڈینیٹس کے درمیان مذکورہ بالا تعلقات کو یکجا کرنا اور پہلے بیان کردہ 3D اور 2D پوائنٹس کے درمیان نقشہ سازی سے ملتا ہے یا ایک بار طے ہو جانے کے بعد، دیگر دو کوآرڈینیٹس کا حساب لگایا جا سکتا ہے۔ مثالی صورت میں، جب کیمرہ ایک کامل پن ہول کیمرے کے مطابق 3D پوائنٹس کا نقشہ بناتا ہے اور اس کے نتیجے میں 2D پوائنٹس کا بغیر کسی شور کے پتہ لگایا جا سکتا ہے، تو دونوں کے لیے تاثرات برابر ہوتے ہیں۔ تاہم، عملی طور پر، وہ نہیں ہیں اور مثال کے طور پر، کسی قسم کی اوسط کے لحاظ سے، دونوں تخمینوں کو یکجا کرنا فائدہ مند ثابت ہوسکتا ہے۔ مندرجہ بالا حسابات کی دیگر اقسام کی توسیعات بھی ہیں جو ممکن ہیں۔ انہوں نے پرائمیڈ امیج کوآرڈینیٹس کے اظہار سے آغاز کیا اور غیر پرائمیڈ سسٹم میں 3D کوآرڈینیٹس اخذ کیے۔ غیر بنیادی امیج کوآرڈینیٹس سے شروع کرنا اور بنیادی تھری ڈی کوآرڈینیٹس حاصل کرنا بھی ممکن ہے، جنہیں آخر میں غیر بنیادی تھری ڈی کوآرڈینیٹس میں تبدیل کیا جا سکتا ہے۔ پھر، مثالی صورت میں نتیجہ مندرجہ بالا تاثرات کے برابر ہونا چاہیے، لیکن عملی طور پر وہ انحراف کر سکتے ہیں۔ ایک حتمی تبصرہ اس حقیقت سے متعلق ہے کہ اگر ضروری میٹرکس کا تعین متعلقہ امیج کوآرڈینیٹ سے کیا جاتا ہے، جو اکثر اس صورت میں ہوتا ہے جب 3D پوائنٹس کا تعین اس طرح کیا جاتا ہے، تو ترجمہ ویکٹر صرف ایک نامعلوم مثبت اسکیلنگ تک جانا جاتا ہے۔ نتیجے کے طور پر، دوبارہ تعمیر شدہ 3D پوائنٹس بھی مثبت اسکیلنگ کے حوالے سے غیر متعین ہیں۔ بنڈل ایڈجسٹمنٹ لائن لائن انٹرسیکشن حوالہ جات بیرونی لنکس کمپیوٹر وژن اسٹیریوفوٹوگرامٹری میں میٹ لیب جیومیٹری میں دو ویو اور ملٹی ویو مثلث دیکھیں۔