Eight-point algorithm
آٹھ نکاتی الگورتھم ایک الگورتھم ہے جو کمپیوٹر وژن میں استعمال ہوتا ہے تاکہ متعلقہ امیج پوائنٹس کے سیٹ سے سٹیریو کیمرا جوڑی سے متعلق ضروری میٹرکس یا بنیادی میٹرکس کا اندازہ لگایا جا سکے۔ اسے کرسٹوفر لونگوئٹ-ہیگنس نے 1981 میں ضروری میٹرکس کے معاملے کے لیے متعارف کرایا تھا۔ نظریہ طور پر، یہ الگورتھم بنیادی میٹرکس کے لیے بھی استعمال کیا جا سکتا ہے، لیکن عملی طور پر نارملائزڈ آٹھ نکاتی الگورتھم، جسے 1997 میں رچرڈ ہارٹلی نے بیان کیا تھا، اس معاملے کے لیے بہتر موزوں ہے۔ الگورتھم کا نام اس حقیقت سے ماخوذ ہے کہ یہ آٹھ (یا اس سے زیادہ) متعلقہ تصویری نکات کے سیٹ سے ضروری میٹرکس یا بنیادی میٹرکس کا تخمینہ لگاتا ہے۔ تاہم، الگورتھم کے تغیرات کو آٹھ پوائنٹس سے کم کے لیے استعمال کیا جا سکتا ہے۔ کوپلانیریٹی کی رکاوٹ دو کیمروں کی ایپی پولر جیومیٹری اور خلا میں ایک نقطہ کو الجبرائی مساوات کے ساتھ ظاہر کیا جا سکتا ہے۔ مشاہدہ کریں کہ، اس بات سے کوئی فرق نہیں پڑتا کہ خلا میں نقطہ کہاں ہے، ویکٹر، اور ایک ہی سطح سے تعلق رکھتے ہیں۔ بائیں آنکھ کے حوالہ فریم میں نقاط کے نقاط کو کال کریں اور دائیں آنکھ کے حوالہ فریم میں نقاط کو کال کریں اور دو حوالہ فریموں کے درمیان گردش اور ترجمہ کو کال کریں۔ دو حوالہ فریموں میں کے نقاط کے درمیان تعلق ہے۔ مندرجہ ذیل مساوات ہمیشہ برقرار رہتی ہے کیونکہ اس سے پیدا ہونے والا ویکٹر دونوں کے لیے آرتھوگنل ہوتا ہے اور: کیونکہ، ہمیں ملتا ہے۔ کے ساتھ تبدیل کرتے ہوئے، ہمیں مشاہدہ ملتا ہے جسے میٹرکس کے طور پر سمجھا جا سکتا ہے ؛ لانگویٹ-ہیگنس نے اس کی نشاندہی کرنے کے لیے علامت کا استعمال کیا۔ مصنوعات کو اکثر ضروری میٹرکس کہا جاتا ہے اور اس کے ساتھ نشان زد کیا جاتا ہے۔ ویکٹر ویکٹرز کے متوازی ہوتے ہیں اور اس لیے اگر ہم ان ویکٹرز کو تبدیل کرتے ہیں تو کوپلانیریٹی کی رکاوٹ برقرار رہتی ہے۔ اگر ہم بائیں اور دائیں تصویری طیاروں کے پروجیکشنز کے نقاط کو کال کرتے ہیں، تو کوپلانیریٹی کی رکاوٹ کو بنیادی الگورتھم کے طور پر لکھا جا سکتا ہے۔ بنیادی آٹھ نکاتی الگورتھم کو یہاں ضروری میٹرکس کا تخمینہ لگانے کے معاملے کے لیے بیان کیا گیا ہے۔ یہ تین مراحل پر مشتمل ہے۔ سب سے پہلے، یہ ایک یکساں لکیری مساوات وضع کرتا ہے، جہاں حل کا براہ راست تعلق ہوتا ہے، اور پھر مساوات کو حل کرتا ہے، اس بات کو مدنظر رکھتے ہوئے کہ اس کا قطعی حل نہیں ہو سکتا ہے۔ آخر میں، نتیجے میں آنے والے میٹرکس کی اندرونی رکاوٹوں کا انتظام کیا جاتا ہے۔ پہلا مرحلہ لونگوئٹ-ہیگنس کے مقالے میں بیان کیا گیا ہے، دوسرا اور تیسرا مرحلہ تخمینہ نظریہ میں معیاری نقطہ نظر ہیں۔ لازمی میٹرکس کے ذریعہ بیان کردہ رکاوٹ اسی امیج پوائنٹس کے لیے ہے جس کی نمائندگی نارملائزڈ امیج کوآرڈینیٹس میں ہوتی ہے۔ الگورتھم جس مسئلے کو حل کرتا ہے وہ مماثل امیج پوائنٹس کے سیٹ کا تعین کرنا ہے۔ عملی طور پر، امیج پوائنٹس کے امیج کوآرڈینیٹس شور سے متاثر ہوتے ہیں اور حل کا حد سے زیادہ تعین بھی کیا جا سکتا ہے جس کا مطلب ہے کہ یہ تلاش کرنا ممکن نہیں ہو سکتا ہے کہ تمام پوائنٹس کے لیے مذکورہ بالا رکاوٹ کو بالکل پورا کرتا ہے۔ اس مسئلے کو الگورتھم کے دوسرے مرحلے میں حل کیا گیا ہے۔ مرحلہ 1: ایک یکساں لکیری مساوات کی تشکیل کے ساتھ اور رکاوٹ کو اس طرح بھی لکھا جا سکتا ہے یا کہاں اور یعنی 9 جہتی ویکٹر کی شکل میں ضروری میٹرکس کی نمائندگی کرتا ہے اور یہ ویکٹر ویکٹر کے لیے آرتھوگنل ہونا چاہیے جسے میٹرکس کی ویکٹر نمائندگی کے طور پر دیکھا جا سکتا ہے۔ متعلقہ امیج پوائنٹس کا ہر جوڑا ایک ویکٹر تیار کرتا ہے۔ تھری ڈی پوائنٹس کے ایک سیٹ کو دیکھتے ہوئے یہ ویکٹروں کے ایک سیٹ سے مطابقت رکھتا ہے اور ان سب کو ویکٹر کے لیے مطمئن ہونا چاہیے۔ کافی زیادہ (کم از کم آٹھ) لکیری طور پر آزاد ویکٹروں کو دیکھتے ہوئے سیدھے طریقے سے تعین کرنا ممکن ہے۔ تمام ویکٹروں کو میٹرکس کے کالموں کے طور پر جمع کریں اور پھر ایسا ہونا چاہیے کہ اس کا مطلب یہ ہے کہ یہ ایک یکساں لکیری مساوات کا حل ہے۔ مرحلہ 2: مساوات کو حل کرنا اس مساوات کو حل کرنے کے لیے ایک معیاری نقطہ نظر کا مطلب ہے کہ یہ ایک واحد قدر کے مطابق ایک صحیح واحد ویکٹر ہے جو صفر کے برابر ہے۔ بشرطیکہ اس کی تعمیر کے لیے کم از کم آٹھ لکیری طور پر آزاد ویکٹر استعمال کیے جائیں اس کے بعد یہ واحد ویکٹر منفرد ہے (اسکیلر ضرب کو نظر انداز کرتے ہوئے) اور اس کے نتیجے میں، اور پھر اس کا تعین کیا جا سکتا ہے۔ اس صورت میں جب تعمیر کے لیے آٹھ سے زیادہ متعلقہ پوائنٹس استعمال کیے جاتے ہیں تو یہ ممکن ہے کہ اس کی کوئی واحد قدر صفر کے برابر نہ ہو۔ یہ معاملہ عملی طور پر اس وقت ہوتا ہے جب تصویر کے نقاط مختلف قسم کے شور سے متاثر ہوتے ہیں۔ اس صورتحال سے نمٹنے کے لیے ایک عام نقطہ نظر یہ ہے کہ اسے کل کم سے کم مربع مسئلہ کے طور پر بیان کیا جائے۔ تلاش کریں جو کب کم ہوتا ہے۔ حل یہ ہے کہ سب سے چھوٹی واحد قدر کے مطابق بائیں واحد ویکٹر کے طور پر انتخاب کیا جائے۔ میٹرکس میں اس کی دوبارہ ترتیب اس مرحلے کا نتیجہ دیتی ہے، جسے یہاں کہا گیا ہے۔ مرحلہ 3: اندرونی رکاوٹ کو نافذ کرنا شور والی تصویر کے نقاط سے نمٹنے کا ایک اور نتیجہ یہ ہے کہ نتیجے میں آنے والا میٹرکس لازمی میٹرکس کی اندرونی رکاوٹ کو پورا نہیں کر سکتا، یعنی اس کی دو واحد اقدار برابر اور غیر صفر ہیں اور دوسرا صفر ہے۔ درخواست پر منحصر ہے، اندرونی رکاوٹ سے چھوٹے یا بڑے انحراف ایک مسئلہ ہو سکتے ہیں یا نہیں بھی ہو سکتے ہیں۔ اگر یہ اہم ہے کہ تخمینہ شدہ میٹرکس اندرونی رکاوٹوں کو پورا کرتا ہے، تو یہ رینک 2 کے میٹرکس کو تلاش کرکے پورا کیا جا سکتا ہے جو مرحلہ 2 کے نتیجے میں میٹرکس کو کم سے کم کرتا ہے اور فروبینیوس میٹرکس کا معیار استعمال کیا جاتا ہے۔ اس مسئلے کا حل پہلے ایک واحد قدر کے سڑنے کا حساب لگا کر دیا جاتا ہے: جہاں آرتھوگنل میٹرکس ہیں اور یہ ایک اخترن میٹرکس ہے جس کی واحد اقدار پر مشتمل ہے۔ مثالی صورت میں، کے اخترن عناصر میں سے ایک صفر ہونا چاہیے، یا دیگر دو کے مقابلے میں کم از کم چھوٹا ہونا چاہیے جو برابر ہونا چاہیے۔ کسی بھی صورت میں، ترتیب دیں کہ بالترتیب سب سے بڑی اور دوسری سب سے بڑی واحد اقدار کہاں ہیں۔ آخر میں، میٹرکس الگورتھم کے ذریعہ فراہم کردہ ضروری میٹرکس کا نتیجہ تخمینہ ہے۔ نارملائزڈ الگورتھم بنیادی آٹھ نکاتی الگورتھم کو اصولی طور پر بنیادی میٹرکس کا اندازہ لگانے کے لیے بھی استعمال کیا جا سکتا ہے۔ اس کی وضاحت کرنے والی رکاوٹ یہ ہے کہ متعلقہ امیج کوآرڈینیٹس کی یکساں نمائندگی کہاں ہیں (ضروری نہیں کہ معمول کی جائے)۔ اس کا مطلب یہ ہے کہ ضروری میٹرکس کی طرح ایک میٹرکس بنانا اور اس مساوات کو حل کرنا ممکن ہے جس کے لیے اس کا نئی شکل والا ورژن ہے۔ اوپر بیان کردہ طریقہ کار پر عمل کرتے ہوئے، پھر آٹھ مماثل پوائنٹس کے سیٹ سے تعین کرنا ممکن ہے۔ تاہم، عملی طور پر، نتیجے میں بنیادی میٹرکس ایپی پولر رکاوٹوں کے تعین کے لیے مفید نہیں ہو سکتا ہے۔ دشواری مسئلہ یہ ہے کہ اس کا نتیجہ اکثر غیر مشروط ہوتا ہے۔ نظریہ طور پر، ایک واحد قدر صفر کے برابر ہونی چاہیے اور باقی غیر صفر ہیں۔ تاہم، عملی طور پر، کچھ غیر صفر واحد اقدار بڑی اقدار کے مقابلے میں چھوٹی ہو سکتی ہیں۔ اگر تعمیر کرنے کے لیے آٹھ سے زیادہ متعلقہ نکات استعمال کیے جائیں، جہاں نقاط صرف تقریبا درست ہوں، تو ہو سکتا ہے کہ کوئی اچھی طرح سے متعین واحد قدر نہ ہو جس کی شناخت تقریبا صفر کے طور پر کی جا سکے۔ نتیجتا، مساوات کے یکساں لکیری نظام کا حل مفید ہونے کے لیے کافی درست نہیں ہو سکتا۔ کاز ہارٹلی نے اپنے 1997 کے مضمون میں اس تخمینے کے مسئلے کو حل کیا۔ اس کے مسئلے کے تجزیے سے پتہ چلتا ہے کہ یہ مسئلہ ان کی جگہ میں یکساں تصویری نقاط کی ناقص تقسیم کی وجہ سے ہے۔ 2 ڈی امیج کوآرڈینیٹ کی ایک عام یکساں نمائندگی وہ ہے جہاں دونوں جدید ڈیجیٹل کیمرے کے لیے 0 سے 1000-2000 کی حد میں ہوتے ہیں۔ اس کا مطلب یہ ہے کہ پہلے دو نقاط تیسرے نقاط کے مقابلے میں بہت بڑی حد میں مختلف ہوتے ہیں۔ مزید برآں، اگر تصویر کے نکات جو تعمیر کرنے کے لیے استعمال ہوتے ہیں وہ تصویر کے نسبتا چھوٹے علاقے میں ہوتے ہیں، مثال کے طور پر at، تو پھر ویکٹر تمام نکات کے لیے کم و بیش ایک ہی سمت میں اشارہ کرتا ہے۔ نتیجے کے طور پر، ایک بڑی واحد قدر ہوگی اور باقی چھوٹی ہیں۔ اس مسئلے کے حل کے طور پر، ہارٹلی نے تجویز پیش کی کہ دونوں تصاویر میں سے ہر ایک کے کوآرڈینیٹ سسٹم کو مندرجہ ذیل اصول کے مطابق آزادانہ طور پر ایک نئے کوآرڈینیٹ سسٹم میں تبدیل کیا جانا چاہیے۔ نئے کوآرڈینیٹ سسٹم کی ابتدا امیج پوائنٹس کے سینٹرائڈ (کشش ثقل کے مرکز) پر مرکوز ہونی چاہیے (اس کی ابتدا ہونی چاہیے)۔ یہ اصل اصل کا نئے میں ترجمہ کرکے پورا کیا جاتا ہے۔ ترجمہ کے بعد نقاط کو یکساں طور پر اسکیل کیا جاتا ہے تاکہ اصل سے پوائنٹس تک کے فاصلے کا اوسط برابر ہو۔ اس اصول کے نتیجے میں، عام طور پر، دونوں تصاویر میں سے ہر ایک کے لیے ایک الگ مربوط تبدیلی ہوتی ہے۔ نتیجے کے طور پر، نئے یکساں امیج کوآرڈینیٹس اس طرح دیے جاتے ہیں کہ پرانے سے نئے نارملائزڈ امیج کوآرڈینیٹس میں تبدیلیاں (ترجمہ اور اسکیلنگ) کہاں ہیں۔ یہ نارملائزیشن صرف امیج پوائنٹس پر منحصر ہے جو ایک ہی امیج میں استعمال ہوتے ہیں اور عام طور پر، نارملائزڈ کیمرے کے ذریعہ تیار کردہ نارملائزڈ امیج کوآرڈینیٹس سے الگ ہوتے ہیں۔ بنیادی میٹرکس پر مبنی ایپی پولر رکاوٹ کو اب کہاں کے طور پر دوبارہ لکھا جا سکتا ہے۔ اس کا مطلب یہ ہے کہ اوپر بیان کردہ بنیادی آٹھ نکاتی الگورتھم کا استعمال کرتے ہوئے تبدیل شدہ بنیادی میٹرکس کا اندازہ لگانے کے لیے عام شدہ یکساں امیج کوآرڈینیٹس کا استعمال کرنا ممکن ہے۔ نارملائزیشن ٹرانسفارمیشنز کا مقصد یہ ہے کہ میٹرکس، جو عام امیج کوآرڈینیٹس سے بنایا گیا ہے، عام طور پر، اس سے بہتر کنڈیشن نمبر رکھتا ہے۔ اس کا مطلب یہ ہے کہ حل ہم آہنگ مساوات کے حل کے طور پر اس کے مقابلے میں زیادہ اچھی طرح سے بیان کیا گیا ہے۔ ایک بار جب اس کا تعین کیا جاتا ہے اور مؤخر الذکر میں نئی شکل دی جاتی ہے تو اس کے مطابق دینے کے لیے ڈی نارملائز کیا جا سکتا ہے۔ عام طور پر، بنیادی میٹرکس کا یہ تخمینہ اس سے بہتر ہے جو غیر نارمل شدہ نقاط سے اندازہ لگا کر حاصل کیا جاتا۔ آٹھ پوائنٹس سے کم کا استعمال کرتے ہوئے ہر پوائنٹ جوڑی میں عنصر پر ایک محدود مساوات کے ساتھ حصہ ڈالتی ہے۔ چونکہ آزادی کی پانچ ڈگریاں ہیں اس لیے اس کا تعین کرنے کے لیے صرف پانچ پوائنٹ جوڑوں کے ساتھ کافی ہونا چاہیے۔ ڈیوڈ نیسٹر نے پانچ جوڑے والے پوائنٹس کے سیٹ سے ضروری میٹرکس کا اندازہ لگانے کے لیے ایک موثر حل پیش کیا، جسے پانچ نکاتی الگورتھم کہا جاتا ہے۔ ہارٹلی اور۔ ال۔ بعد میں نیسٹر کے الگورتھم پر مبنی ایک ترمیم شدہ اور زیادہ مستحکم پانچ نکاتی الگورتھم کی تجویز پیش کی۔ یہ بھی دیکھیں ضروری میٹرکس بنیادی میٹرکس ٹرائی فوکل ٹینسر حوالہ جات مزید پڑھنے کمپیوٹر وژن میں جیومیٹری