19 سپتامبر 2020

بسته نرم افزاری Primitives

بسته نرم افزاری Primitives

انیمیشنی که مشاهده می‌کنید، خروجی یک بسته نرم‌افزاری به نام Primitives است که به صورت متن‌باز در گیت‌هاب [+] در دسترس قرار دارد. کد این نرم‌افزار، با استفاده از زبان Go و توسط «مایکل فوگلمن» نوشته شده است.

خروجی این برنامه، می‌تواند به صورت رستری (فرمت PNG و JPG)، برداری (فرمت SVG) و یا انیمیشن (فرمت GIF) باشد. برای ساخت خروجی نیز، می‌توان مشخص کرد که شکل یا عنصر پایه (Primitive) چه باشد؛ خط، دایره، مستطیل، بیضی، مثلث، چندضلعی و حتی ترکیب همه این‌ها.

اما این نرم‌افزار چطور این کار را انجام می‌دهد؟ مسأله ما، یافتن یک نسخه تقریبی از تصویر ورودی است که در آن، از عناصر پایه مشخصی استفاده شده است. در واقع، این یک مسأله بهینه‌سازی است که البته پاسخ زیر-بهینه (sub-optimal) برای آن نیز، کار ما را راه می‌اندازد.

اما برای ساده‌تر کردن حل این مسأله بهینه‌سازی، یک ترفند جالب به کار رفته است. حل مسأله آن طور که هست، خیلی سخت است؛ اما می‌توان آن را تبدیل به یک فرایند بهینه‌سازی دنباله‌ای (Sequential Optimization) کرد. یعنی به جای حل یک مسأله بزرگ و سخت، چند مسأله ریز و متوالی را حل کنیم.

این تکنیک رایجی در حل مسائل بهینه‌سازی است و کاربردهای فراوانی در حوزه‌های مختلف دارد. در مورد این کاربرد خاص، مسأله اصلی به پیدا کردن فقط و فقط یک شکل یا عنصر پایه در هر مرحله، شکسته می‌شود. یعنی در هر مرحله، فقط یک عنصر افزوده می‌شود. البته پاسخ، غالبا زیر-بهینه خواهد بود.

مثلا فرض کنید که قصد داریم تصویری را فقط با دایره تخمین بزنیم. الگوریتم وقتی شروع به کار می‌کند، یک صفحه خالی دارد و بهترین دایره تنها را پیدا می‌کند که می‌تواند بهترین تقریب از تصویر را ارائه کند. محل، اندازه، زاویه، رنگ و شفافیت عناصر، متغیرهای تصمیم ما هستند. الگوریتم با تغییر این موارد، در فضای جواب به دنبال بهترین عنصری می‌گردد که می‌تواند اضافه کند و خطای تصویر تقریبی را کاهش دهد. تابع خطا نیز با معیارهایی مانند مجموع یا میانگین مربعات اختلاف رنگ، قابل محاسبه است.

در پروژه Primitive از الگوریتم‌های بهینه‌سازی ساده‌ای استفاده شده است و نتایج هم قابل قبولند؛ هم سرعت خوبی دارند و هم کیفیت پاسخ‌ها مطلوب است. در این برنامه نسخه تغییر یافته الگوریتم‌های تپه‌نوردی (Hill Climbing) و شبیه‌سازی تبرید (Simulated Annealing) به کار رفته‌اند.

الگوریتم بهینه‌سازی، در هر مرحله، بهترین شکل پایه جدیدی را که می‌تواند، پیدا می‌کند و به نتیجه بهینه‌سازی به دست آمده از مراحل قبل، اضافه می‌کند. به این ترتیب، به مرور و با افزوده شدن شکل‌های پایه به صورت متوالی، رفته رفته خطای تصویر اصلی و تصویر تقریبی، کاهش می‌یابد.

البته این فرایند کلا تصادفی است و پاسخ در دفعات مختلف اجرا، متفاوت خواهد بود. همین موضوع، می‌تواند به خلق تصاویر جالبی کمک کند. مثلا در تصویر زیر، نتیجه تقریب یک تصویر در دفعات مختلف، کمک کرده‌اند که چیزی شبیه انیمیشن استاتیک ایجاد شود.

اشتراک‌گذاری این مطلب:
  • facebook
  • twitter
  • gplus

با من در شبکه‌های اجتماعی همراه باشید:

دیدگاه خود را بیان کنید

دیدگاه‌ها