Direct linear transformation
ডাইরেক্ট লিনিয়ার ট্রান্সফর্মেশন (ডিএলটি) একটি অ্যালগরিদম যা সাদৃশ্য সম্পর্কের একটি সেট থেকে ভেরিয়েবলগুলির একটি সেট সমাধান করেঃ যেখানে এবং পরিচিত ভেক্টরগুলির জন্য, একটি অজানা স্কেলার গুণন পর্যন্ত সমতা বোঝায় এবং এটি একটি ম্যাট্রিক্স (বা রৈখিক রূপান্তর) যা সমাধান করার জন্য অজানা ধারণ করে। প্রজেক্টিভ জ্যামিতিতে এই ধরনের সম্পর্ক প্রায়শই দেখা যায়। ব্যবহারিক উদাহরণগুলির মধ্যে একটি দৃশ্যে থ্রিডি পয়েন্ট এবং একটি পিনহোল ক্যামেরার চিত্র সমতলে তাদের অভিক্ষেপ এবং হোমোগ্রাফির মধ্যে সম্পর্ক অন্তর্ভুক্ত রয়েছে। উদাহরণস্বরূপ, রৈখিক সমীকরণের একটি সাধারণ পদ্ধতি সমাধান করা যেতে পারে, উদাহরণস্বরূপ, এটি একটি ম্যাট্রিক্স সমীকরণ হিসাবে পুনর্লিখন করে যেখানে ম্যাট্রিক্স এবং তাদের নিজ নিজ কলামে ভেক্টর ধারণ করে। প্রদত্ত যে একটি অনন্য সমাধান বিদ্যমান, এটি সমাধান দ্বারা দেওয়া হয় যা সমীকরণগুলি শেষ বা কম নির্ধারিত হওয়ার ক্ষেত্রেও বর্ণনা করা যেতে পারে। যে বিষয়টি সরাসরি রৈখিক রূপান্তর সমস্যাটিকে উপরের স্ট্যান্ডার্ড কেস থেকে আলাদা করে তোলে তা হল সংজ্ঞায়িত সমীকরণের বাম এবং ডান দিকগুলি একটি অজানা গুণক দ্বারা পৃথক হতে পারে যা k-এর উপর নির্ভরশীল। ফলস্বরূপ, স্ট্যান্ডার্ড কেসের মতো গণনা করা যায় না। পরিবর্তে, সাদৃশ্য সম্পর্কগুলিকে যথাযথ রৈখিক সমজাতীয় সমীকরণ হিসাবে পুনর্লিখন করা হয় যা পরে একটি আদর্শ পদ্ধতিতে সমাধান করা যেতে পারে। সাদৃশ্য সমীকরণগুলিকে সমজাতীয় রৈখিক সমীকরণ হিসাবে পুনর্লিখন এবং মানক পদ্ধতি দ্বারা সেগুলি সমাধান করার সংমিশ্রণকে ডাইরেক্ট লিনিয়ার ট্রান্সফর্মেশন অ্যালগরিদম বা ডিএলটি অ্যালগরিদম হিসাবে উল্লেখ করা হয়। ডিএলটি-র জন্য ইভান সাদারল্যান্ডকে দায়ী করা হয়। উদাহরণ হিসেবে ধরা যাক। ধরা যাক এবং দুটি পরিচিত ভেক্টর হতে হবে, এবং আমরা ম্যাট্রিক্সটি এমনভাবে খুঁজে পেতে চাই যাতে সমীকরণ k-এর সাথে সম্পর্কিত অজানা স্কেলার ফ্যাক্টরটি কোথায়। অজানা স্কেলারগুলি থেকে মুক্তি পেতে এবং সমজাতীয় সমীকরণগুলি পেতে, অ্যান্টি-সিমেট্রিক ম্যাট্রিক্সকে সংজ্ঞায়িত করুন এবং সমীকরণের উভয় পক্ষকে বাম দিক থেকে গুণ করুন যেহেতু নিম্নলিখিত সমজাতীয় সমীকরণগুলি, যা আর অজানা স্কেলার ধারণ করে না, হাতে রয়েছে সমীকরণের এই সেট থেকে সমাধান করার জন্য, ভেক্টর এবং ম্যাট্রিক্সের উপাদানগুলি বিবেচনা করুনঃ, এবং এবং উপরের সমজাতীয় সমীকরণটি ম্যাট্রিক্স আকারে লেখা যেতে পারেঃ যেখানে এবং উভয়ই 6-মাত্রিক ভেক্টর হিসাবে সংজ্ঞায়িত এবং এখন পর্যন্ত, আমাদের 1 সমীকরণ এবং 6 অজানা রয়েছে। সমজাতীয় সমীকরণের একটি সেট ম্যাট্রিক্স আকারে লেখা যেতে পারে যেখানে একটি ম্যাট্রিক্স যা তার সারিতে পরিচিত ভেক্টর ধারণ করে। অজানা নির্ধারণ করা যেতে পারে, উদাহরণস্বরূপ, একটি একক মান পচন দ্বারা; একটি একক মানের সাথে সম্পর্কিত একটি ডান একক ভেক্টর যা শূন্যের সমান। একবার নির্ধারিত হয়ে গেলে, ম্যাট্রিক্সের উপাদানগুলি ভেক্টর থেকে পুনর্বিন্যস্ত হতে পারে। লক্ষ্য করুন যে এর স্কেলিং গুরুত্বপূর্ণ নয় (এটি অবশ্যই অ-শূন্য হতে হবে) কারণ সংজ্ঞায়িত সমীকরণগুলি ইতিমধ্যে অজানা স্কেলিংয়ের অনুমতি দেয়। বাস্তবে ভেক্টর এবং এতে শব্দ থাকতে পারে যার অর্থ হল সাদৃশ্য সমীকরণগুলি কেবল প্রায় বৈধ। ফলস্বরূপ, এমন কোনও ভেক্টর নাও থাকতে পারে যা সমজাতীয় সমীকরণটি সঠিকভাবে সমাধান করে। এই ক্ষেত্রে, মোট সর্বনিম্ন বর্গ সমাধানটি সঠিক একক ভেক্টর হিসাবে বেছে নিয়ে ব্যবহার করা যেতে পারে যা আরও সাধারণ ক্ষেত্রে ক্ষুদ্রতম একক মানের সাথে সামঞ্জস্যপূর্ণ। উপরের উদাহরণে রয়েছে এবং, তবে সাদৃশ্য সম্পর্কগুলিকে সমজাতীয় রৈখিক সমীকরণে পুনর্লিখন করার সাধারণ কৌশলটি উভয়ের জন্য নির্বিচারে মাত্রায় সাধারণীকরণ করা যেতে পারে এবং যদি এবং পূর্ববর্তী অভিব্যক্তিগুলি এখনও একটি সমীকরণের দিকে নিয়ে যেতে পারে যেখানে এখন প্রতিটি k অজানা উপাদানগুলিতে একটি সমীকরণ সরবরাহ করে এবং একসাথে এই সমীকরণগুলি পরিচিত ম্যাট্রিক্স এবং অজানা 2q-মাত্রিক ভেক্টরের জন্য লেখা যেতে পারে। এই ভেক্টরটি আগের মতো একইভাবে পাওয়া যেতে পারে। সবচেয়ে সাধারণ ক্ষেত্রে এবং। আগের তুলনায় প্রধান পার্থক্য হল যে ম্যাট্রিক্সটি এখন এবং অ্যান্টি-সিমেট্রিক। যখন এই ধরনের ম্যাট্রিক্সের স্থান আর এক-মাত্রিক থাকে না, তখন এটি মাত্রার হয়। এর অর্থ হল, k-এর প্রতিটি মান সমতুল্য ম্যাট্রিক্সের স্থানের জন্য এবং যেখানে একটি M-মাত্রিক ভিত্তি রয়েছে, সেই ধরনের M সমজাতীয় সমীকরণ প্রদান করে। উদাহরণ p = 3 এই ক্ষেত্রে যে p = 3 নিম্নলিখিত তিনটি ম্যাট্রিক্স বেছে নেওয়া যেতে পারে, এই বিশেষ ক্ষেত্রে, ভেক্টর ক্রস প্রোডাক্টের ম্যাট্রিক্স উপস্থাপনা কোথায় তার জন্য সমজাতীয় রৈখিক সমীকরণগুলি লেখা যেতে পারে। লক্ষ্য করুন যে এই শেষ সমীকরণটি ভেক্টর মূল্যবান; বাম দিকটি শূন্য উপাদান। k-এর প্রতিটি মান এর অজানা উপাদানগুলিতে তিনটি সমজাতীয় রৈখিক সমীকরণ প্রদান করে। তবে, যেহেতু র্যাঙ্ক = 2, তাই সর্বাধিক দুটি সমীকরণ রৈখিকভাবে স্বাধীন। বাস্তবে, অতএব, তিনটি ম্যাট্রিসের মধ্যে শুধুমাত্র দুটি ব্যবহার করা সাধারণ, উদাহরণস্বরূপ, m = 1,2 এর জন্য। যাইহোক, সমীকরণগুলির মধ্যে রৈখিক নির্ভরতা নির্ভরশীল, যার অর্থ দুর্ভাগ্যজনক ক্ষেত্রে এটি বেছে নেওয়া ভাল হত, উদাহরণস্বরূপ, m = 2,3। ফলস্বরূপ, সমীকরণের সংখ্যা যদি উদ্বেগের বিষয় না হয়, তবে ম্যাট্রিক্স তৈরি করার সময় তিনটি সমীকরণই ব্যবহার করা ভাল হতে পারে। ফলস্বরূপ সমজাতীয় রৈখিক সমীকরণগুলির মধ্যে রৈখিক নির্ভরতা পি> 2 ক্ষেত্রে একটি সাধারণ উদ্বেগের বিষয় এবং এটি হয় প্রতিসম ম্যাট্রিক্সের সেট হ্রাস করে বা রেফারেন্স নির্ধারণের জন্য প্রয়োজনের চেয়ে বড় হওয়ার অনুমতি দিয়ে মোকাবেলা করতে হবে বাহ্যিক লিঙ্ক হোমোগ্রাফি অনুমান ইলান ডুব্রোফস্কির দ্বারা (§ 2.1 স্কেচ "বেসিক ডিএলটি অ্যালগরিদম") একটি ডিএলটি সমাধানকারী যা কম্পিউটার ভিশন প্রজেক্টিভ জ্যামিতিতে সিয়াং-জেন (জনি) চিয়েন জ্যামিতির ম্যাটল্যাবের উপর ভিত্তি করে তৈরি।