در ریاضیات ، فراکتال ها زیر مجموعه های ویژه ای از فضای اقلیدسی هستند که دارای یک ساختار پیچیده و غالباً خودکشی هستند. بر خلاف اشکال معمولی ، طرح هایی که در قطعاتی از یک خط مستقیم با بزرگنمایی کافی انحطاط می شوند ، فراکتال ها ساختار پیچیده خود را در هر مقیاس حفظ می کنند.

همچنین ، معیارهای پذیرفته شده فضا همیشه برای فراکتال ها مناسب نیستند: 1 برای خطوط مستقیم ، 2 برای هواپیماها ، 3 برای فضای حجمی. برخی از فراکتال ها یک موقعیت متوسط را بین فضاها اشغال می کنند. به عنوان مثال ، یک زنجیره چند ضلعی ، که هر قطعه از آن همان زنجیره چند ضلعی است ، حاوی تعداد نامحدودی از پیوندها است ، یعنی نمی توان آن را به عنوان مجموع خطوط مستقیم توصیف کرد ، در عین حال هنوز نمی توان آن را دو نامیدشکل ابعادی با یک منطقه زیرا متریک دوم آن ناقص است.

خصوصیات غیرمعمول فراکتال ها ، یا به اصطلاح وابستگی های داخلی پیچیده آنها ، در ریاضیات ، فیزیک ، پردازش اطلاعات - الگوریتم های فشرده سازی و استاگووگرافی استفاده می شود. علاوه بر این ، فراکتال ها کاربردی در ART پیدا کرده اند زیرا ساختار غیر اصلی آنها بسیار زیبایی شناختی است.

تولید فراکتال

فراکتال ها ساختار پیچیده خود را در هر مقیاس حفظ می کنند ، یعنی آنها می توانند بی نهایت بزرگنمایی و تفصیل شوند. فضای دنیای واقعی محدودیت هایی دارد ، برخی از مقادیر قابل تفکیک اساسی: پیکسل هایی برای نمایش در مانیتور ، اتم ها و ذرات ابتدایی کوچکتر برای دنیای فیزیکی ، یا اگر بیشتر پیش برویم ، مقادیر قابل مقایسه با طول پلانک 10^(-35) ،که در آن نظریه های بدنی مدرن کار را متوقف می کنند. از این رو ، می توان نتیجه گرفت که تولید فراکتال های واقعی با یک ساختار بی نهایت پیچیده در دنیای واقعی غیرممکن است. هرگونه تجسم فراکتال با درجه خاصی از دقت انجام می شود.

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

انواع مختلفی از فراکتال ها و رویکردهای مربوط به تولید آنها وجود دارد. ما دو رویکرد محبوب را در نظر خواهیم گرفت-سیستم های عملکرد تکرار شده و یک الگوریتم فرار.

سیستم های عملکرد تکرار شده

فراکتال ها از نزدیک با سیستم های عملکرد تکرار شده ، که اغلب برای بازنمایی تحلیلی و نمودار استفاده می شوند ، ارتباط نزدیکی دارند. یکی از انواع توابع تکرار ، تحولات وابسته است.

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

، جایی که D فاصله بین نقاط است. x ، y - امتیاز ؛نقشه برداری جذاب.

دو زیرگروه فراکتال تولید شده توسط سیستم های عملکرد تکرار شده وجود دارد:

1. فراکتال ها از اشکال هندسی تشکیل شده اند که قطعاتی از آنها به صورت تکراری با اشکال مشابه با اندازه کوچکتر جایگزین می شوند. اینها شامل مثلث Sierpiński ، Koch Snowflake ، Menger Sponge و غیره است (شکل 1-3)

2. فراکتال های ساخته شده توسط نقاط مربوط به مقادیر توابع. بیشتر اوقات ، چنین فراکتال ها در هواپیما ساخته می شوند و از سیستم توابع زیر برای تنظیم فراکتال استفاده می شود

همه توابع f باید نقشه های انقباض باشد. یک نقطه اولیه انتخاب شده و توابع شرح داده شده توسط سیستم به طور مکرر روی آن اعمال می شود و هر عملکرد با احتمال از پیش تعیین شده PI استفاده می شود. تمام مقادیر به دست آمده در صفحه مختصات مشخص شده و یک فراکتال تشکیل می دهند.

بارنزلی سرخس

Basley Fe یکی از مشهورترین فراکتال ها است که توسط سیستم معادلات شرح داده شده است. نویسنده آن - مایکل بارنزلی - یکی از مشهورترین محققان خواص فراکتال است. وی همچنین پیشنهاد کرد که از برخی خصوصیات فراکتال برای فشرده سازی اطلاعات ، به ویژه تصاویر استفاده کنید. این رویکرد در بخش های زیر با جزئیات مورد بحث قرار گرفته است.

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

این سیستم به روش زیر نشان داده شده است (ضرایب ممکن است در منابع مختلف کمی متفاوت باشد):

که فراکتال زیر را تولید می کند (شکل 4):

تصویر نشان می دهد که شاخه های سرخس نسخه های کوچکتر از کل سرخس هستند.

الگوریتم زمان فرار

الگوریتم زمان فرار و فراکتال های تولید شده توسط آن از نزدیک با مفهوم رابطه عود ارتباط دارند. رابطه عود با فرمول نشان داده شده است

، یعنی عناصر بعدی دنباله بر اساس قبلی محاسبه می شوند. روابط تکراری یک مورد خاص از توابع بازگشتی هستند - زمانی که راه حل یک مشکل به حل همان مشکل برای داده های ورودی دیگر بستگی دارد. چنین الگوریتم هایی را می توان تنها در صورتی اجرا کرد که چنین داده های ورودی وجود داشته باشد که حل مسئله بدون بازگشت دیگری امکان پذیر است. در مورد رابطه عود، این بدان معنی است که برای محاسبه دنباله، تابع F و k اولین اعضای دنباله باید شناخته شود.

قابل محاسبه و غیره

الگوریتم زمان فرار اجازه می دهد تا رفتار سری ارائه شده توسط فرمول مکرر را تجسم کنید. معمولاً برای توابع یک متغیر پیچیده و توالی هایی از نوع استفاده می شود

اگرچه در حالت کلی، "عمق" اتصال مکرر محدود نیست.

ماهیت الگوریتم زمان فرار به شرح زیر است:

1) قطعه ای از صفحه مختصات به تصویر اختصاص داده می شود که هر پیکسل مربوط به یک نقطه روی آن است.

2) برای هر نقطه (این می تواند مقدار اولیه دنباله یا یکی از پارامترهای تابع باشد)، مشخص می شود که آیا دنباله مربوطه در تعداد محدودی از n مرحله خاصیتی را نشان می دهد یا خیر.

3) پیکسل ها با توجه به ویژگی های آشکار شده رنگ می شوند.

دقت تولید فراکتال به تعداد n تکرار بستگی دارد، زیرا ویژگی مورد نظر می تواند خود را هم در اولین و هم در یک میلیونیم یا بیشتر از عناصر آن نشان دهد. برای n کوچک، نمودار یک نمای تقریبی از فراکتال را نمایش می دهد. مرزها با افزایش n به تفصیل بیان می شوند.

الگوریتم زمان فرار دو تغییر دارد:

• دو رنگ (هر پیکسل در یکی از دو رنگ رنگ می شود، بسته به اینکه خاصیت شناسایی شده است یا خیر).
• چند رنگی (هر پیکسل در یکی از چندین رنگ رنگ می شود که نه تنها به تشخیص یک ویژگی بستگی دارد، بلکه در چند مرحله نیز مشخصه پیدا شده است).

معروف ترین فراکتال های زمان فرار، فراکتال های ماندلبرو و جولیا هستند. خاصیتی که فراکتال ها را تشکیل می دهد، رفتار یک سری بازگشتی با است

، موارد زیر ممکن است:

1. عناصر سری به یک مقدار خاص تمایل دارند (جذاب)

2. عناصر سری حول مقادیر متعدد حلقه می زنند

3. عناصر سری به بی نهایت تمایل دارند

4. رفتار آشفته است و با موارد توصیف شده مطابقت ندارد.

معمولاً نقاط بر اساس اینکه سری مربوطه مقدار محدودی را حفظ می کند (مورد 1-2) یا به بی نهایت (مورد 3) می رود تقسیم می شوند.

فراکتال ماندلبروت

Fractals Mandelbrot تجسم مجموعه Mandelbrot است - مجموعه ای از اعداد پیچیده C که سری مربوط به رابطه عود برای آن

با مقدار اولیه تمایل به بی نهایت ندارد

این مجموعه توسط FATOU در ابتدای قرن بیستم کشف شد ، سپس توسط Mandelbrot در دهه 70 مورد مطالعه و تجسم قرار گرفت ، هنگامی که رایانه های به اندازه کافی قدرتمند در دسترس قرار گرفتند. شکل 5 یک Fractal کلاسیک Mandelbrot را نشان می دهد ، شکل 6 یک نسخه بزرگنمایی از یکی از قطعات آن است. تمام فراکتال ها با استفاده از [2] تولید شدند.

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

با این حال ، این شرایط ممکن است برای عملکردهای ماهیت متفاوت متفاوت باشد.

نمودارهای 7-9 به اصطلاح فراکتال های چند بیت را به تصویر می کشند ، مجموعه های ماندلبروت آنها توسط یک تابع ارائه می شود

، جایی که K یک عدد صحیح مثبت است.

جولیا فراکتال

جولیا فراکتال ها با مجموعه های جولیا مطابقت دارد که از نزدیک با مجموعه های Mandelbrot ارتباط دارند. در مورد مجموعه Mandelbrot ، نقاط مورد تجزیه و تحلیل به عنوان پارامتر عملکرد F (z) استفاده می شوند و سری با مقدار شروع می شود

در مورد جولیا پارامترهای f (z) ثابت است و نکته مورد مطالعه C آغاز سریال است

این تفاوت منجر به ظهور فراکتال ها از یک نوع کاملاً متفاوت می شود. در حقیقت ، جولیا مجموعه تنها مرز بین مناطقی است که دارای رفتار مختلف هستند (سری تولید شده توسط عناصر برخی از مناطق دارای حد محدودی است ، در حالی که سری های تولید شده توسط عناصر دیگران - بی نهایت) ، در زمینه فراکتال ها ، آنها معمولاً از یک پر شده صحبت می کنندمجموعه جولیا ، که شامل مناطقی با رفتار پایدار است.

مجموعه کلاسیک جولیا ، به طور مشابه با مجموعه Mandelbrot ، با فرمول مطابقت دارد

، و اگر с1 متعلق به مجموعه Mandelbrot باشد ، مجموعه جولیا به هم وصل می شود. مجموعه Mandelbrot دامنه تعریف مجموعه جولیا است. فراکتال های "عجیب و غریب" هنگامی اتفاق می افتد که с1 در مرز مجموعه ماندلبروت قرار دارد (شکل 11-12).

همانطور که در مورد Mandelbrot ، جولیا فراکتال ها نیز توسط فرمول محدود نمی شوند

و می تواند برای یک عملکرد دلخواه تولید شود (شکل 13-14).

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

فشرده سازی فراکتال

تعدادی الگوریتم وجود دارد، به اصطلاح فشرده سازی تصویر فراکتال، که به طور مستقیم با مفهوم ریاضی یک فراکتال مرتبط نیست، اما منحصراً به شباهت مناطق تصویر می پردازد. این الگوریتم ها ارتباط نزدیکی با سیستم های توابع تکرار و مفهوم نقطه ثابت دارند. نقطه x برای تابع f ثابت است if

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

ایده اصلی الگوریتم های فشرده سازی فراکتال ارائه یک تصویر در قالب یک سیستم معادلات است که رابطه بین قطعات آن را توصیف می کند. علاوه بر این، هر قطعه از تصویر با یک تبدیل وابسته به قطعه دیگری از تصویر توصیف می شود.

تصویر به بلوک های محدوده و دامنه تقسیم می شود. به عنوان یک قاعده، اندازه بلوک های محدوده نصف بلوک های دامنه است، به عنوان مثال، بلوک های محدوده ۸×۸ پیکسل و بلوک های دامنه ۱۶×۱۶ هستند. بلوک های محدوده همپوشانی ندارند و تصویر را به طور کامل می پوشانند. بلوک های دامنه می توانند همپوشانی داشته باشند و شامل قطعاتی از چندین بلوک محدوده باشند.

بلوک های دامنه به اندازه بلوک های محدوده به سادگی با میانگین پیکسل های همسایه فشرده می شوند و یک کتاب کد را تشکیل می دهند. سپس، برای هر بلوک محدوده، ما باید یک بلوک دامنه را پیدا کنیم که می تواند با استفاده از یک تبدیل ساده افین به بلوک اصلی تبدیل شود.

به عنوان یک قاعده، بلوک ها به عنوان بردار نشان داده می شوند و از یک تبدیل نسبتا ساده از نوع زیر استفاده می کنند:

د - بلوک دامنه فشرده.

1 - بردار واحد مساوی طول بلوک محدوده.

یافتن یک بلوک دامنه اغلب غیرممکن است، تغییر شکل به شما امکان می دهد بلاک محدوده را به طور دقیق بازیابی کنید. بنابراین، بلوکی انتخاب می شود که بهترین تقریب را می دهد، یعنی چنین

، که در آن خطای بازسازی حداقل خواهد بود

نقص نقشه برداری و همچنین دقت محدود نمایش s و o منجر به تلفات فشرده سازی می شود.

برای هر جفت D ، R می توان مقادیر بهینه S و O را محاسبه کرد ، اما پیدا کردن بهینه D یک مشکل غیرقانونی است. در نسخه های اول الگوریتم ، جستجو با یک جستجوی ساده و بی پروا انجام شد که بسیار ناکارآمد بود. رویکردهای بی شماری وجود دارد که به شما امکان می دهد جستجو را بهینه کنید ، برخی از آنها در زیر مورد بحث قرار می گیرد.

در نتیجه ، هر بلوک دامنه RI با سه مقدار - (o ، s ، k) مطابقت دارد ، جایی که k تعداد بلوک دامنه انتخاب شده در کتاب کد است (در واقع مختصات آن در تصویر). تصویر فشرده شده مجموعه ای از سه ضرایب است.

رمزگشگر روابط بین بلوک های تصویر را می داند ، اما خود بلوک ها نیست ، همچنین قوانین تشکیل کتاب کد را می داند ، اما خود کتاب نیست. بنابراین ، بسیار مهم است که ضرایب K موقعیت بلوک دامنه را در تصویر تعیین کند ، و نه در کتاب کد ، که می تواند برای بهینه سازی جستجو مرتب شود.

الگوریتم بازیابی تصویر:

1. یک تصویر IMG دلخواه انتخاب شده است که همزمان با اندازه اصلی است (می تواند تک رنگ ، ساختار یافته یا سر و صدا باشد - این نتیجه را تحت تأثیر قرار نمی دهد).
2. تصویر به بلوک های دامنه و دامنه مشابه الگوریتم فشرده سازی تقسیم می شود.
3. یک کتاب کد از بلوک های دامنه ساخته شده است.
4. بلوک های دامنه تصویر با بلوک های K مربوطه از کتاب کد جایگزین می شوند که با استفاده از S و O تبدیل شده اند.
5. مراحل 3-4 تکرار می شوند تا زمانی که تصویر تغییر کند. این بدان معنی است که به یک نقطه ثابت رسیده است و تصویری یافت شده است که مطابق با سیستم معادلات است.

بهبودی معمولاً حدود 10 تکرار طول می کشد. چنین فرآیند رفع فشار غیرمعمول ، از حالت خودسرانه سیستم شروع می شود و منجر به همان نتیجه می شود ، به این دلیل که از تحولات استفاده شده قطعات بزرگی را به سمت های کوچکتر می کشد. در عین حال ، هر تکرار نه تنها بلوک های دامنه را تغییر می دهد ، و آنها را شبیه به تصویر اصلی می کند ، بلکه بلوک های دامنه ای را که در آن گنجانده شده است ، چنین اتصال پیچیده ای از کل تصویر به هر تکرار الگوریتم اجازه می دهد تا آن را به وجود آوردنزدیکتر به اصل.

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

1. گسترش کتاب کد به دلیل همپوشانی بیشتر بلوک های دامنه ، از جمله چرخش و بازتاب بلوک های دامنه.
2. استفاده از چندین بردار ویژگی متعامد متعامد و ضرایب O مربوطه به جای یک.
3. تغییر اندازه پویا از بلوک ها - ابتدا یک مسابقه برای بلوک های بزرگ یافت می شود ، در صورت عدم دستیابی به دقت لازم ، بلوک تقسیم می شود. در این حالت ، نه تنها از بلوک های مربع استفاده می شود ، بلکه بلوک های مستطیل یا چند ضلعی را نیز می توان استفاده کرد.
4. با استفاده از درختان جستجو
5. با استفاده از روشهای مختلف طبقه بندی.
6. رویکرد تقسیم و ادغام - بلوک های دامنه با خصوصیات مشابه در گروه ها ترکیب می شوند ، که تجزیه و تحلیل بیشتر را ساده می کند. نه تنها مربع ، بلکه از بلوک های مستطیل و مثلثی نیز می توان استفاده کرد.
7. شروع به جستجوی یک دامنه مناسب در نزدیکی بلوک دامنه کنید.

ایده های پشت فشرده سازی تصویر فراکتال با سایر رویکردهای رایج بسیار متفاوت است. تعدادی از الگوریتم های فشرده سازی فراکتال ثبت اختراع شدند که مانع از پذیرش گسترده آن شد.

علامت سنجی فراکتال

Steganography به مشکل مخفی کردن یک قطعه اطلاعات (stegomessage) در داخل دیگری (کانتینر) می پردازد. اصول فشرده سازی فراکتال نیز در استاگووگرافی ، از جمله علامت گذاری دیجیتال استفاده می شود.

تصویر به دو منطقه جداگانه تقسیم می شود - r و d. منطقه R به بلوک های دامنه ، منطقه D - به بلوک های دامنه تقسیم می شود. یک کتاب کد از بلوک های دامنه گردآوری می شود ، که سپس به دو نیمه تقسیم D0 ، D1 تقسیم می شود. در ساده ترین حالت ، D0 و D1 را می توان از قطعات تصویر غیر همپوشانی ، به عنوان مثال ، D0 از چهارم سمت چپ بالا و D1 از سمت راست پایین ساخته کرد. بسیار مهم است که D0 و D1 دارای همان بلوک ها نباشند.

داده ها در بلوک های محدوده ، یک بیت در هر بلوک تعبیه می شوند. هنگامی که اطلاعات تعبیه شده است ، بلوک دامنه بسته به بیت تعبیه شده با یک بلوک دامنه تبدیل شده از D0 یا D1 جایگزین می شود. ضرایب O و S برای تعبیه استفاده می شوند ، اما منتقل نمی شوند. برای یافتن بلوک دامنه بهینه ، می توان از همان روشها مانند فشرده سازی فراکتال استفاده کرد. با این حال ، استفاده از بهترین ها ، بلکه فقط یک بلوک قابل قبول از بلوک دامنه ، ناامن است ، زیرا ممکن است استگوگرام به درستی استخراج نشود.

هنگام استخراج یک استیجماژ ، تصویر به همان روشی که هنگام تعبیه به مناطقی تقسیم می شود ، یک کتاب کد ساخته شده و به دو قسمت تقسیم می شود. سپس ، برای هر بلوک دامنه ، یک بلوک دامنه بهینه جستجو می شود (اگر ظرف تحریف نشده باشد ، می توان بلوک دامنه را از بلوک دامنه بدون از دست دادن بدست آورد) ، اگر بلوک یافت شده متعلق به D0 باشد ، پس بیت صفر استخراج می شود، اگر متعلق به D1 باشد ، بیت پنهان 1 است.

الگوریتم های علامت گذاری فراکتال باید هم مشکلات مربوط به فشرده سازی فراکتال را حل کنند - بهینه سازی جستجو و کاهش اعوجاج و یک مورد جدید - ساخت کتابهای کد D 0 و D1. از یک طرف ، هر دو باید دارای انواع بلوک های دامنه باشند که بدون در نظر گرفتن پیام تعبیه شده ، امکان نمایش بلوک های محدوده با حداقل اعوجاج را فراهم می کنند. از طرف دیگر ، هر دو کتاب نباید کاملاً یکسان باشند و در برخی موارد بلوک های بسیار مشابه ، که باعث می شود استخراج غیرممکن شود.

مطالعه وابستگی شکل فراکتال جولیا به پارامترها

جولیا فراکتال کلاسیک با فرمول نشان داده شده است

و در واقع توسط پارامتر C تعیین می شود ، در حالی که فراکتال هایی با مقادیر C نزدیک شکل مشابهی دارند. تا حدودی یک استثناء مقادیر C واقع در مرز مجموعه Mandelbrot است که حتی یک تغییر جزئی منجر به تغییرات قابل توجه در فراکتال های جولیا می شود.

ما به طور تجربی تغییراتی را که در ظاهر جولیا فراکتال ها ظاهر می شوند ، هنگامی که پارامتر C تغییر می کند ، بررسی کرده ایم. برای این کار ، با استفاده از برنامه [2] ، نمونه بزرگی از جولیا فراکتال (حدود 15 هزار) تولید شد ، C با یک مرحله 0. 01 در محدوده نشان داده شده در جدول 1 تغییر یافت.

جدول 1. دامنه پارامترهای مورد استفاده جولیا فراکتال

مناطق منتخب تقریباً به طور کامل مجموعه Mandelbrot را پوشش می دهند.

منطقه نمایش به صورت عمودی [-1. 5 ؛1. 5] ، به صورت افقی [-1 ؛1] ، این برای نمایش مجموعه جولیا کافی است (شکل 15).