Eight-point algorithm
আট-পয়েন্ট অ্যালগরিদম হল একটি অ্যালগরিদম যা কম্পিউটার ভিশনে ব্যবহৃত হয় প্রয়োজনীয় ম্যাট্রিক্স বা স্টেরিও ক্যামেরা জুটির সাথে সম্পর্কিত মৌলিক ম্যাট্রিক্সকে সংশ্লিষ্ট চিত্র পয়েন্টগুলির একটি সেট থেকে অনুমান করতে। 1981 সালে ক্রিস্টোফার লঙ্গুয়েট-হিগিন্স অপরিহার্য ম্যাট্রিক্সের ক্ষেত্রে এটি চালু করেছিলেন। তত্ত্বগতভাবে, এই অ্যালগরিদমটি মৌলিক ম্যাট্রিক্সের জন্যও ব্যবহার করা যেতে পারে, তবে বাস্তবে 1997 সালে রিচার্ড হার্টলি দ্বারা বর্ণিত স্বাভাবিক আট-পয়েন্ট অ্যালগরিদমটি এই ক্ষেত্রে আরও উপযুক্ত। অ্যালগরিদমের নামটি এই সত্য থেকে উদ্ভূত হয়েছে যে এটি আটটি (বা তার বেশি) সংশ্লিষ্ট চিত্র বিন্দুর একটি সেট থেকে প্রয়োজনীয় ম্যাট্রিক্স বা মৌলিক ম্যাট্রিক্স অনুমান করে। যাইহোক, অ্যালগরিদমের বৈচিত্রগুলি আটটিরও কম পয়েন্টের জন্য ব্যবহার করা যেতে পারে। কপ্ল্যানারিটি সীমাবদ্ধতা একটি বীজগাণিতিক সমীকরণ দিয়ে দুটি ক্যামেরার এপিপোলার জ্যামিতি এবং স্থানের একটি বিন্দু প্রকাশ করতে পারে। লক্ষ্য করুন যে, বিন্দুটি যেখানেই থাকুক না কেন, ভেক্টরগুলি একই সমতলের অন্তর্গত। বাম চোখের রেফারেন্স ফ্রেমে বিন্দুর স্থানাঙ্ক কল করুন এবং ডান চোখের রেফারেন্স ফ্রেমে স্থানাঙ্ক কল করুন এবং দুটি রেফারেন্স ফ্রেমের মধ্যে ঘূর্ণন এবং অনুবাদ কল করুন। এটি দুটি রেফারেন্স ফ্রেমের স্থানাঙ্কের মধ্যে সম্পর্ক। নিম্নলিখিত সমীকরণটি সর্বদা ধরে রাখে কারণ যে ভেক্টর থেকে উৎপন্ন হয় তা উভয়ের জন্য অর্থোগোনাল এবংঃ কারণ, আমরা পাই। এর পরিবর্তে, আমরা দেখতে পাই যেটিকে একটি ম্যাট্রিক্স হিসাবে বিবেচনা করা যেতে পারে; লঙ্গুয়েট-হিগিনস এটিকে বোঝাতে প্রতীকটি ব্যবহার করেছিলেন। পণ্যটিকে প্রায়শই অপরিহার্য ম্যাট্রিক্স বলা হয় এবং এর সাথে চিহ্নিত করা হয়। ভেক্টরগুলি ভেক্টরগুলির সমান্তরাল এবং তাই আমরা যদি এই ভেক্টরগুলিকে প্রতিস্থাপন করি তবে কোপ্ল্যানারিটি সীমাবদ্ধতা বজায় থাকে। যদি আমরা বাম এবং ডান চিত্র সমতলে প্রজেকশনগুলির স্থানাঙ্কগুলি বলি, তবে কোপ্ল্যানারিটি সীমাবদ্ধতাকে বেসিক অ্যালগরিদম হিসাবে লেখা যেতে পারে মৌলিক আট-পয়েন্ট অ্যালগরিদম এখানে প্রয়োজনীয় ম্যাট্রিক্স অনুমানের ক্ষেত্রে বর্ণনা করা হয়েছে। এটি তিনটি ধাপ নিয়ে গঠিত। প্রথমে, এটি একটি সমজাতীয় রৈখিক সমীকরণ তৈরি করে, যেখানে সমাধানটি সরাসরি সম্পর্কিত, এবং তারপর সমীকরণটি সমাধান করে, এটি বিবেচনা করে যে এর সঠিক সমাধান নাও থাকতে পারে। পরিশেষে, ফলস্বরূপ ম্যাট্রিক্সের অভ্যন্তরীণ সীমাবদ্ধতাগুলি পরিচালিত হয়। প্রথম ধাপটি লঙ্গুয়েট-হিগিন্সের গবেষণাপত্রে বর্ণনা করা হয়েছে, দ্বিতীয় এবং তৃতীয় ধাপগুলি হল অনুমান তত্ত্বের মানক পদ্ধতি। অপরিহার্য ম্যাট্রিক্স দ্বারা সংজ্ঞায়িত সীমাবদ্ধতাটি স্বাভাবিক চিত্র স্থানাঙ্কে উপস্থাপিত সংশ্লিষ্ট চিত্র পয়েন্টগুলির জন্য। অ্যালগরিদম যে সমস্যার সমাধান করে তা হল মিলযুক্ত চিত্র বিন্দুর একটি সেট নির্ধারণ করা। বাস্তবে, ইমেজ পয়েন্টগুলির চিত্র স্থানাঙ্কগুলি গোলমাল দ্বারা প্রভাবিত হয় এবং সমাধানটিও অতিরিক্ত নির্ধারিত হতে পারে যার অর্থ হল যে সমস্ত পয়েন্টের জন্য উপরের সীমাবদ্ধতাকে ঠিক কোনটি সন্তুষ্ট করে তা খুঁজে পাওয়া সম্ভব নাও হতে পারে। অ্যালগরিদমের দ্বিতীয় ধাপে এই সমস্যাটির সমাধান করা হয়েছে। ধাপ 1: একটি সমজাতীয় রৈখিক সমীকরণ প্রণয়ন করা এবং এবং সীমাবদ্ধতার সাথে বা যেখানে এবং সেটিও পুনর্লিখন করা যেতে পারে, একটি 9-মাত্রিক ভেক্টরের আকারে অপরিহার্য ম্যাট্রিক্সকে উপস্থাপন করে এবং এই ভেক্টরটি অবশ্যই ভেক্টরের অর্থোগোনাল হতে হবে যা ম্যাট্রিক্সের ভেক্টর উপস্থাপনা হিসাবে দেখা যেতে পারে। সংশ্লিষ্ট চিত্র বিন্দুর প্রতিটি জোড়া একটি ভেক্টর তৈরি করে। 3ডি বিন্দুর একটি সেট দেওয়া হলে এটি ভেক্টরের একটি সেটের সাথে মিলে যায় এবং তাদের সকলকে ভেক্টরের জন্য সন্তুষ্ট করতে হবে। যথেষ্ট সংখ্যক (কমপক্ষে আটটি) রৈখিকভাবে স্বাধীন ভেক্টর দেওয়া হলে সহজবোধ্য উপায়ে নির্ধারণ করা সম্ভব। সমস্ত ভেক্টরকে একটি ম্যাট্রিক্সের কলাম হিসাবে সংগ্রহ করুন এবং এটি অবশ্যই এই ক্ষেত্রে হতে হবে যে এর অর্থ এটি একটি সমজাতীয় রৈখিক সমীকরণের সমাধান। পদক্ষেপ 2: সমীকরণটি সমাধান করা এই সমীকরণটি সমাধান করার একটি আদর্শ পদ্ধতি বোঝায় যে এটি একটি একক মানের সাথে সম্পর্কিত একটি সঠিক একক ভেক্টর যা শূন্যের সমান। তবে শর্ত থাকে যে এটি তৈরি করতে কমপক্ষে আটটি রৈখিকভাবে স্বাধীন ভেক্টর ব্যবহার করা হয় যার ফলে এই একক ভেক্টরটি অনন্য (স্কেলার গুণনকে উপেক্ষা করে) এবং ফলস্বরূপ, এবং তারপর নির্ধারণ করা যেতে পারে। যদি নির্মাণের জন্য আটটিরও বেশি সংশ্লিষ্ট বিন্দু ব্যবহার করা হয় তবে এটি সম্ভব যে এটির শূন্যের সমান কোনও একক মান নেই। এই ঘটনাটি বাস্তবে ঘটে যখন চিত্রের স্থানাঙ্কগুলি বিভিন্ন ধরনের গোলমাল দ্বারা প্রভাবিত হয়। এই পরিস্থিতি মোকাবেলা করার জন্য একটি সাধারণ পদ্ধতি হল এটিকে মোট সর্বনিম্ন বর্গ সমস্যা হিসাবে বর্ণনা করা; কোনটি কখন সর্বনিম্ন হয় তা খুঁজে বের করুন। এর সমাধান হল এর ক্ষুদ্রতম একক মানের সাথে সামঞ্জস্যপূর্ণ বাম একবচন ভেক্টর হিসাবে বেছে নেওয়া। একটি ম্যাট্রিক্সে এটির পুনর্বিন্যাস এই ধাপের ফলাফল দেয়, যা এখানে হিসাবে উল্লেখ করা হয়েছে। ধাপ 3: অভ্যন্তরীণ সীমাবদ্ধতা প্রয়োগ করা কোলাহলপূর্ণ চিত্র স্থানাঙ্ক নিয়ে কাজ করার আরেকটি পরিণতি হল যে ফলস্বরূপ ম্যাট্রিক্স অপরিহার্য ম্যাট্রিক্সের অভ্যন্তরীণ সীমাবদ্ধতা পূরণ করতে পারে না, অর্থাৎ, এর দুটি একক মান সমান এবং অ-শূন্য এবং অন্যটি শূন্য। প্রয়োগের উপর নির্ভর করে, অভ্যন্তরীণ সীমাবদ্ধতা থেকে ছোট বা বড় বিচ্যুতি একটি সমস্যা হতে পারে বা নাও হতে পারে। যদি এটি গুরুত্বপূর্ণ হয় যে আনুমানিক ম্যাট্রিক্স অভ্যন্তরীণ সীমাবদ্ধতাগুলি সন্তুষ্ট করে, তবে এটি র্যাঙ্ক 2-এর ম্যাট্রিক্স খুঁজে বের করে সম্পন্ন করা যেতে পারে যা দ্বিতীয় ধাপ থেকে প্রাপ্ত ম্যাট্রিক্সকে সর্বনিম্ন করে এবং ফ্রোবেনিয়াস ম্যাট্রিক্স আদর্শ ব্যবহার করা হয়। সমস্যার সমাধান প্রথমে একটি একক মান পচন গণনা করে দেওয়া হয়ঃ যেখানে অর্থোগোনাল ম্যাট্রিক্স এবং একটি তির্যক ম্যাট্রিক্স যা এর একক মান ধারণ করে। আদর্শ ক্ষেত্রে, এর তির্যক উপাদানগুলির মধ্যে একটি শূন্য হওয়া উচিত, বা অন্য দুটির তুলনায় কমপক্ষে ছোট হওয়া উচিত যা সমান হওয়া উচিত। যাই হোক না কেন, সেট করুন যেখানে যথাক্রমে বৃহত্তম এবং দ্বিতীয় বৃহত্তম একক মান রয়েছে। পরিশেষে, ম্যাট্রিক্স দ্বারা দেওয়া হয় অ্যালগরিদম দ্বারা প্রদত্ত প্রয়োজনীয় ম্যাট্রিক্সের ফলস্বরূপ অনুমান। সাধারণ অ্যালগরিদম মৌলিক আট-পয়েন্ট অ্যালগরিদম নীতিগতভাবে মৌলিক ম্যাট্রিক্স অনুমানের জন্যও ব্যবহার করা যেতে পারে। এর জন্য সংজ্ঞায়িত সীমাবদ্ধতা হল যেখানে সংশ্লিষ্ট চিত্র স্থানাঙ্কের সমজাতীয় উপস্থাপনা রয়েছে (প্রয়োজনীয় স্বাভাবিক নয়)। এর মানে হল যে অপরিহার্য ম্যাট্রিক্সের মতো একইভাবে একটি ম্যাট্রিক্স গঠন করা এবং সমীকরণটি সমাধান করা সম্ভব যার জন্য এটি একটি নতুন আকারের সংস্করণ। উপরে বর্ণিত পদ্ধতি অনুসরণ করে, আটটি ম্যাচিং পয়েন্টের একটি সেট থেকে নির্ধারণ করা সম্ভব। বাস্তবে, তবে, ফলস্বরূপ মৌলিক ম্যাট্রিক্স এপিপোলার সীমাবদ্ধতা নির্ধারণের জন্য কার্যকর নাও হতে পারে। অসুবিধা সমস্যাটি হল যে এর ফলে প্রায়শই খারাপ অবস্থা হয়। তত্ত্বগতভাবে, একটি একক মান শূন্যের সমান হওয়া উচিত এবং বাকিগুলি অ-শূন্য। বাস্তবে, তবে, কিছু অ-শূন্য একক মান বড়গুলির তুলনায় ছোট হতে পারে। যদি নির্মাণের জন্য আটটিরও বেশি সংশ্লিষ্ট বিন্দু ব্যবহার করা হয়, যেখানে স্থানাঙ্কগুলি কেবল প্রায় সঠিক হয়, তবে একটি সুনির্দিষ্ট একক মান নাও থাকতে পারে যা প্রায় শূন্য হিসাবে চিহ্নিত করা যেতে পারে। ফলস্বরূপ, সমীকরণের সমজাতীয় রৈখিক ব্যবস্থার সমাধান কার্যকর হওয়ার জন্য যথেষ্ট নির্ভুল নাও হতে পারে। কারণ হার্টলি তার 1997 সালের নিবন্ধে এই অনুমানের সমস্যাটি নিয়ে আলোচনা করেছেন। সমস্যাটির তাঁর বিশ্লেষণ দেখায় যে সমস্যাটি তাদের স্থানে সমজাতীয় চিত্র স্থানাঙ্কের দুর্বল বিতরণের কারণে ঘটে। 2ডি চিত্র স্থানাঙ্কের একটি সাধারণ সমজাতীয় উপস্থাপনা হল যেখানে উভয়ই একটি আধুনিক ডিজিটাল ক্যামেরার জন্য 0 থেকে 1000-2000 পরিসরে থাকে। এর মানে হল যে প্রথম দুটি স্থানাঙ্ক তৃতীয় স্থানাঙ্কের তুলনায় অনেক বড় পরিসরে পরিবর্তিত হয়। উপরন্তু, যদি চিত্রের যে বিন্দুগুলি নির্মাণের জন্য ব্যবহৃত হয় তা চিত্রের তুলনামূলকভাবে ছোট অঞ্চলে থাকে, উদাহরণস্বরূপ, আবার ভেক্টর সমস্ত বিন্দুর জন্য কমবেশি একই দিকে নির্দেশ করে। ফলস্বরূপ, একটি বড় একক মান থাকবে এবং অবশিষ্টগুলি ছোট হবে। এই সমস্যার সমাধান হিসাবে, হার্টলি প্রস্তাব করেছিলেন যে দুটি চিত্রের প্রত্যেকটির স্থানাঙ্ক ব্যবস্থাকে নিম্নলিখিত নীতি অনুসারে স্বাধীনভাবে একটি নতুন স্থানাঙ্ক ব্যবস্থায় রূপান্তরিত করা উচিত। নতুন স্থানাঙ্ক ব্যবস্থার উৎপত্তি চিত্র বিন্দুর কেন্দ্রবিন্দুতে (মাধ্যাকর্ষণ কেন্দ্র) কেন্দ্রীভূত হওয়া উচিত। এটি মূল উৎস থেকে নতুন উৎসের অনুবাদের মাধ্যমে সম্পন্ন করা হয়। অনুবাদের পরে স্থানাঙ্কগুলি সমানভাবে পরিমাপ করা হয় যাতে মূল থেকে বিন্দু পর্যন্ত দূরত্বের গড় সমান হয়। এই নীতির ফলে, সাধারণত, দুটি চিত্রের প্রত্যেকটির জন্য একটি স্বতন্ত্র সমন্বয় রূপান্তর ঘটে। ফলস্বরূপ, নতুন সমজাতীয় চিত্র স্থানাঙ্কগুলি পুরানো থেকে নতুন স্বাভাবিক চিত্র স্থানাঙ্কে রূপান্তর (অনুবাদ এবং স্কেলিং) কোথায় রয়েছে তার দ্বারা দেওয়া হয়। এই স্বাভাবিককরণ শুধুমাত্র চিত্র বিন্দুর উপর নির্ভরশীল যা একটি একক ছবিতে ব্যবহৃত হয় এবং সাধারণভাবে, একটি স্বাভাবিক ক্যামেরা দ্বারা উত্পাদিত স্বাভাবিক চিত্র স্থানাঙ্ক থেকে পৃথক। মৌলিক ম্যাট্রিক্সের উপর ভিত্তি করে এপিপোলার সীমাবদ্ধতা এখন কোথায় হিসাবে পুনর্লিখন করা যেতে পারে। এর অর্থ হল উপরে বর্ণিত মৌলিক আট-বিন্দু অ্যালগরিদম ব্যবহার করে রূপান্তরিত মৌলিক ম্যাট্রিক্স অনুমান করতে স্বাভাবিক সমজাতীয় চিত্র স্থানাঙ্ক ব্যবহার করা সম্ভব। স্বাভাবিককরণ রূপান্তরের উদ্দেশ্য হল সাধারণভাবে স্বাভাবিক চিত্র স্থানাঙ্ক থেকে নির্মিত ম্যাট্রিক্সের অবস্থার সংখ্যা আগের তুলনায় ভালো। এর মানে হল যে সমাধানটি সমজাতীয় সমীকরণের সমাধান হিসাবে আপেক্ষিকের চেয়ে বেশি সুনির্দিষ্ট। সাধারণভাবে, মৌলিক ম্যাট্রিক্সের এই অনুমানটি অ-স্বাভাবিক স্থানাঙ্ক থেকে অনুমান করে প্রাপ্ত হওয়ার চেয়ে আরও ভাল। আট পয়েন্টের কম ব্যবহার করে প্রতিটি পয়েন্ট জোড়া উপাদানটির উপর একটি সীমাবদ্ধ সমীকরণের সাথে অবদান রাখে। যেহেতু পাঁচটি ডিগ্রি অফ ফ্রিডম রয়েছে তাই এটি নির্ধারণ করার জন্য কেবল পাঁচটি পয়েন্ট জোড়ার সাথে যথেষ্ট হওয়া উচিত। ডেভিড নিস্টার পাঁচটি জোড়া পয়েন্টের সেট থেকে প্রয়োজনীয় ম্যাট্রিক্স অনুমান করার জন্য একটি কার্যকর সমাধানের প্রস্তাব করেছিলেন, যা পাঁচ-পয়েন্ট অ্যালগরিদম নামে পরিচিত। হার্টলি ও। আল। পরে সিস্টারের অ্যালগরিদমের উপর ভিত্তি করে একটি পরিবর্তিত এবং আরও স্থিতিশীল পাঁচ-পয়েন্ট অ্যালগরিদমের প্রস্তাব দেওয়া হয়। আরও দেখুন অপরিহার্য ম্যাট্রিক্স মৌলিক ম্যাট্রিক্স ট্রাইফোকাল টেনসর রেফারেন্স কম্পিউটার দৃষ্টিতে জ্যামিতি আরও পড়ুন