რა არის საფუძველი fractal შეკუმშვის ალგორითმისთვის? Fractal ინფორმაციის შეკუმშვის ალგორითმი

საკვანძო სიტყვები: ნერვული ქსელები; სურათის შეკუმშვა; მანქანათმცოდნეობა; fractals.

ანოტაცია

ამ ნაშრომში მოცემულია fractal გამოსახულების შეკუმშვის კოდირების დროის შემცირების მეთოდი. ეს მიდგომა აერთიანებს მახასიათებლის მოპოვებას დომენის კლასიფიკაციასთან, თვითორგანიზების ნერვული ქსელის გამოყენებით. აღნიშვნის მახასიათებლები ამცირებს დავალების მოცულობას და საშუალებას აძლევს ნერვულ ქსელს ისწავლონ დაშიფრული გარდა სხვა გამოსახულების შესახებ. კლასიფიკაციისთვის თვითორგანიზებული ნერვული ქსელი წარმოგიდგენთ კასეტური ტოპოლოგიის კონცეფციას და ასევე აღმოფხვრის მრავალი შესაფერისი სურათის კლასის წინასწარი დავალების აუცილებლობას. ქსელი ორგანიზებას უწევს სასწავლო პროცესში მიღებული გამოსახულების მახასიათებლების განაწილების შესაბამისად. ნაშრომში მოცემულია შედეგები, რომლებიც აჩვენებს, რომ კლასიფიკაციურ მიდგომას შეუძლია შეამციროს კოდირების დრო მასშტაბის ორი დავალებით, ამასთან, შენარჩუნდეს შედარებითი სიზუსტე და შეკუმშვის ეფექტურობა.

1. შესავალი

Fractal გამოსახულების კოდირება პერსპექტიული მიდგომაა გამოსახულების შეკუმშვის პროგრამებში, როგორიცაა ინტერნეტ – საიტები. ამასთან, ამ მიდგომაში კოდირების ეტაპისთვის საჭირო დრო იყო შემაფერხებელი დაბრკოლება მის პრაქტიკულ მეთოდად მიღებაზე. კოდირების პროცესი დომენის ბლოკების რუქაზე გამოსახულების ბლოკების რანგის შედგენას მოიცავს. თითოეული რანგის ბლოკისთვის, ალგორითმი ეძებს ასეთ დომენის ბლოკს და შესაბამის ტრანსფორმაციას, რაც უზრუნველყოფს რეიტინგული ბლოკის საუკეთესოდ მოთავსებას. დომენის ბლოკების კლასიფიკაციამ შეიძლება მნიშვნელოვნად დააჩქაროს კოდირება, ამცირებს იმ დომენების რაოდენობას, რომლებიც უნდა მოძებნოთ. უკვე გამოიკვლია თვითორგანიზების ნერვული ქსელების გამოყენება დომენების კლასიფიკაციისთვის. ეს ქსელები უზრუნველყოფს კლასიფიკაციის ძირითადი მიდგომების გაუმჯობესებას კლასის მტევნების ტოპოლოგიის განსაზღვრებით. ამ ნაშრომის ღვაწლი მოიცავს დომენების კლასიფიკაციას თვითორგანიზების ნერვული ქსელის გამოყენებით და მახასიათებლების განაწილებით, სურათების კიდევ უფრო სწრაფი კოდირების მიზნით. გამოსახულების მახასიათებლების მცირე ნაკრები, რომელთა გაზომვის ტონი და ტექსტურა გამოითვლება თითოეული დომენის და რანგის ბლოკისთვის. ამრიგად, თითოეულ ბლოკს აქვს მახასიათებლების ასოცირებული ვექტორი, რომლის ზომა არ არის დამოკიდებული ბლოკის ზომაზე. დახასიათება სასარგებლოა ორი მიზეზის გამო. ჯერ ერთი, დავალების მოცულობის შედეგად შემცირება ამცირებს დომენის ძებნის პროცესში საჭირო გამოთვლების რაოდენობას. მეორეც, ვინაიდან მახასიათებლები დამოუკიდებელია კონკრეტული დომენების სტრუქტურისაგან, შესაძლებელი გახდება თვითორგანიზების ქსელის მომზადება ერთ სურათზე და გამოიყენოს მიღებული ქსელი კლასიფიკაციისთვის სხვა სურათებში. ამრიგად, ქსელის ტრენინგის დრო არ არის კოდირების მთლიანი დროის ნაწილი. სურათების Fractal კოდირების დროის გაზომვები, როგორც წესი, გამოიხატება მზის ან Silicon Graphics სამუშაო სადგურზე მუშაობის დროს. აქ წარმოდგენილი მიდგომა უზრუნველყოფს შედარებით გაზომვებს Pentium 120 MHz კომპიუტერზე მუშაობის დროს.

2. სურათების ფრაკალური კოდირება

სურათების fractal კოდირება დაფუძნებულია შესამცირებელი ფუნქციების სისტემების თეორიაზე (შემდგომში შემოკლებით CIF, ინგლისური Iterated ფუნქციონირების სისტემიდან - IFS). CIF- ის თეორია ემყარება კომპრესიული რედუქციების თეორემას (შემდგომში შემოკლებით TOC, ინგლისური Contraction Mapping Theorem - CMT) კლასიკური ანალიზისაგან, რომელიც გამოიყენება fractal სურათების განმეორებით რეჟიმში მოსაწყობად. Fractal სურათი არის დაფიქსირებული წერტილი სურათის სივრცეში, რაც გარანტირებულია CBT– ით და ამ სურათს CIF მოზიდვა ეწოდება. ინვერსიული პრობლემა, რომელიც გადაწყდა სურათების ფრაგმალური კოდირებით, იწყება მოცემული სურათის გათვალისწინებით და CIF– ის გაანგარიშებით, რომელიც წარმოადგენს გამოსახულებას ახლოს მოცემულთან - მის მიმზიდველთან. Fractal გამოსახულების კოდი ჩვეულებრივ (თუმცა არა ყოველთვის) მოითხოვს უფრო ნაკლებ შენახვას, ვიდრე თავდაპირველი სურათი, რაც ამ მეთოდს ასახავს, \u200b\u200bროგორც შეკუმშვის მეთოდს. ემპირიული შედეგები აჩვენებს, რომ ხშირ შემთხვევაში ფრაზელის მეთოდი ისეთივე კარგია, როგორც JPEG, რომელიც დღეს ითვლება შეკუმშვის სტანდარტად.

Fractal გამოსახულების შეკუმშვა იყენებს CIF– ს სპეციფიკურ ტიპს, რომელსაც ეწოდება ტირაჟულად განზავებული ფუნქციების სისტემა (შემდგომში შემოკლებით CIFF, ინგლისურ დაყოფა დანაწევრებული ფუნქციების სისტემიდან - PIFS). ICCF შედგება მთლიანი მეტრული სივრცის X- ის, ქვე-დომენების ერთობლიობის D i ⊂ X, i \u003d 1, ..., n, და კომპრესიული გარდაქმნების ერთობლიობისაგან w i ~: D i → X, i \u003d 1, ..., n. ჩვენ გრეიდის მასშტაბის სურათებს განვიხილავთ, როგორც კვადრატულ ფართობზე განსაზღვრული ფაქტობრივი f (x, y) მნიშვნელობანი I 2 \u003d I × I. მოდით w i ~ (x, y) იყოს affine ტრანსფორმაცია I 2 → I 2 ისეთი, რომ

იმ პირობით, რომ w i ~ შექცევადია და (x, y) ∈ R i. მუდმივი წრე ვრთავთ ან ვიწროვებთ ფუნქციის მნიშვნელობათა მნიშვნელობათა დიაპაზონს და, ვინაიდან ჩვენ ვსაუბრობთ გრაფიკულ გამოსახულებებზე, ის აკონტროლებს კონტრასტს. ანალოგიურად, მუდმივი o i ზრდის ან ამცირებს რუხის მასშტაბის მნიშვნელობებს, ან აკონტროლებს სიკაშკაშეს. ტრანსფორმაციას w i ~ ეწოდება ტრანსფორმაციის სივრცითი კომპონენტი w i.

ძირითადი ალგორითმი შემდეგია. ჩვენ გავყავით გამოსახულება მართკუთხა რანგის არაგვერდზე, (R i). ბლოკები R i შეიძლება იყოს იგივე ზომის, მაგრამ უფრო ხშირად გარკვეული სახის დანაყოფი გამოიყენება ცვლადი ბლოკის ზომით, რაც შესაძლებელს გახდის მცირე ზომის ნაწილების მჭიდროდ შევსებას. აქ წარმოდგენილი შედეგები მოიპოვა აღწერილი quadtree დანაყოფის სქემის გამოყენებით. ჩვენ ვფარავთ გამოსახულებას დომენის ბლოკების თანმიმდევრობით, შესაძლოა, გადახურვაც. დომენები შეიძლება იყოს სხვადასხვა ზომის და, როგორც წესი, მათი რიცხვი ასობით და ათასშია. Affine ტრანსფორმაცია (2.1) არის სივრცითი შეკუმშვის ტრანსფორმაცია, თუ | det A i |

(2.3)

პატარა იყო ციფრული ციფრული გამოსახულებისთვის ინტეგრალი (2.3) შეიცვალა პიქსელებზე ჯამით. თუ საუკეთესო w i– ს მოძიების შემდეგ, რაოდენობა (2.3) კიდევ უფრო დიდია, ვიდრე წინასწარ განსაზღვრული შეცდომა, მაშინ ოთხკუთხედის დანაწევრების სქემა რანგს ანაწილებს ოთხ პატარა ოთხკუთხედად, ხოლო ოპტიმალური ტრანსფორმაციის ძიება მეორდება ამ პატარა ბლოკებისთვის. ეს პროცესი გრძელდება მანამ, სანამ მნიშვნელობა (2.3) არანაკლებ დაიშვება დასაშვები შეცდომით ან სანამ არ მოხდება ოთხი ხის წინასწარ განსაზღვრული მაქსიმალური სიღრმე. გამოსახულება გაშიფრულია იმეორებით, რომლითაც ხდება ტრანსფორმაციის W გამოსახულების გამოყენება, f

W (f) (x, y) \u003d w i (f) (x, y) for (x, y) ∈ R i

თუ ტრანსფორმაციები (w i) სწორად იქნა შერჩეული, მაშინ n iteration W 0n (f) ახლოს იქნება ორიგინალ სურათთან, n საკმარისი რაოდენობის მნიშვნელობისათვის. დაშიფვრის ეტაპი მოითხოვს მნიშვნელოვან გამოთვლებს დომენების დიდი რაოდენობის გამო, რომელთა შორის აუცილებელია თითოეული რანგის ბლოკის ძებნა, ასევე დომენის თითოეულ შედარებისას შესრულებული გამოთვლების გამო. ამ ნაშრომში, კოდირების ეტაპის გამოთვლითი საჭიროებების შემცირება წყდება ორი მიმართულებით. პირველ რიგში, დანერგულია თითოეული დომენის და რანგის ბლოკისთვის განსაზღვრული გამოსახულების მახასიათებლების კონცეფცია. შემდეგ პოტენციურად შესაფერისი დომენების შერჩევა შესაძლებელია ამ მახასიათებლების მცირე რაოდენობის მნიშვნელობებზე დაყრდნობით, ვიდრე თავად პიქსელების მნიშვნელობები. მეორეც, შემოთავაზებულია დომენის ბლოკების ორგანიზება ნეკნთა ტოპოლოგიაში, თვითორგანიზებული ნერვული ქსელის საშუალებით. ეს კიდევ უფრო ამცირებს კოდირების დროს, რაც ქსელს საშუალებას მისცემს სწრაფად განსაზღვროს ადგილმდებარეობა იმ დომენის ბლოკის მახასიათებლების სივრცეში, რომლებიც მსგავსია რანგის ბლოკებით.

3. მონიშნულის მახასიათებლები

სურათების fractal კოდირების პროცესის დაჩქარების ერთ-ერთი გზა არის მცირე რაოდენობის მახასიათებლების ხაზგასმა, რომლებიც აღწერს დომენისა და რანგის ბლოკებს. შემდეგ, დომენის და წოდების ბლოკების შედარება ემყარება ამ მახასიათებლებს და არა ინდივიდუალურ პიქსელებზე, რაც ამცირებს სამუშაოს რაოდენობას. ამ ნაშრომში გამოყენებულია ექვსი მახასიათებელი, რომლებიც აღწერს ტექსტურის განაწილებას და გამოსახულების კონტრასტს. მახასიათებლების შერჩევა თავისთავად უზრუნველყოფს კოდირების პროცესის მნიშვნელოვან დაჩქარებას.

შემდეგი ექვსი მახასიათებლები გამოიყენება: 1) სტანდარტული გადახრა, σ; 2) skewness, რომელიც წარმოადგენს პიქსელის მნიშვნელობებსა და კუბის ს ნორმალიზებულ ბლოკის საშუალო მნიშვნელობას შორის განსხვავების კუბების ჯამს; 3) ინტერსექსუალური კონტრასტი (მეზობლის კონტრასტი), რომელიც ზომავს სხვაობას მეზობელი პიქსელების მნიშვნელობებს შორის; 4) ბეტა (ბეტა), რომელიც აჩვენებს, თუ რამდენად განსხვავდება პიქსელის მნიშვნელობები ბლოკის ცენტრში მოცემული მნიშვნელობისაგან; 5) ჰორიზონტალური გრადიენტი (ჰორიზონტალური გრადიენტი), რომელიც ახასიათებს ჰორიზონტალურად ბლოკის პიქსელის მნიშვნელობების ცვლილებას; 6) ვერტიკალური გრადიენტი (ვერტიკალური გრადიენტი), რომელიც ახასიათებს ბლოკის პიქსელის მნიშვნელობების ცვლილებას მიმართულებით ზემოდან ქვემოდან. პიქსელის საშუალო მნიშვნელობა არ გამოიყენება როგორც დამახასიათებელი, რადგან კონტრასტი და სიკაშკაშე იცვლება დომენის და რანგის ბლოკების შედარების დროს. დამახასიათებელ სივრცეში დისტანცირების შედარებისას, მახასიათებლების ვექტორი ნორმალიზდება ისე, რომ მახასიათებლების ყველაზე დიდი ფასეულობები არ დომინირებს შედარებაში.

4. ნერვული ქსელების თვითორგანიზება

შემდეგი გაუმჯობესება, რაც შეიძლება გაკეთდეს, დომენებისა და რიგების კლასიფიკაციაა ამ მახასიათებლების საფუძველზე და რიგების შედარება მხოლოდ მსგავსი კლასების დომენებთან. აქ გამოყენებული დომენის კლასიფიკაციის სქემა ემყარება Kohonen თვითორგანიზაციის ნერვულ ქსელს. ამ ტიპის ქსელი შედგება კვანძის პოზიციების გრაფისგან. წონის ვექტორი უკავშირდება lattice– ის თითოეულ კვანძს, რომელსაც აქვს იგივე განზომილება, როგორც დამახასიათებელი ვექტორების განზომილება. აქ გამოყენებული მხატვრული ვექტორების განზომილებაა 6. და აქ გამოყენებული კვანძების ბადე შედგება 10 რიგისა და 10 სვეტისგან. თითოეული კვანძი წარმოადგენს გამოსახულების დომენის ბლოკების კლასს, ამიტომ ჩვენ ვცდილობთ შევინარჩუნოთ კვანძების საერთო რაოდენობა საკმაოდ მცირე. შეიძლება ჩაითვალოს კვანძების ორგანიზების სხვა გზები, მაგალითად, უფრო მაღალი განზომილებიანი მატრიცები.

სწავლის პროცესი დამოუკიდებლად ხდება, პიროვნების მხრიდან რაიმე კონტროლის გარეშე. წონის ვექტორების ქსელი ინიცირებულია შემთხვევითი მნიშვნელობებით. შემდეგ მახასიათებლების შეყვანის ვექტორი შედის ქსელში და ჩვენ ვეძებთ წონის ვექტორს, რომელიც ყველაზე ახლოსაა შეყვანის ვექტორთან. ანუ, ასე აღმოვაჩენთ

|| v - w i'j '|| ≤ || v - w ij || ყველასთვის, ჯ

სადაც v არის მახასიათებლების შეყვანის ვექტორი, და w არის წონის ვექტორი კვანძში ij. რგოლის მიმდებარე წონა შერჩეული წონის მქონე მე ვამაგრებ, რომ უფრო მეტად ემსგავსოს შეყვანის ვექტორს. ეს ადაპტაცია გამოიხატება ფორმულით

w ij new \u003d w ij old + ε · exp (α · || v - w ij ძველი || 2) · (v– w ij old)

სადაც ij არის კვანძების მაჩვენებლები, რომლებიც მე მეზობელთან არიან ”. სასწავლო პროცესის ყოველი ახალი განმეორებით მცირდება ამ სამეზობლო ზომა. პარამეტრი ε არის განმეორების ეტაპი, და α არის ამ ნაბიჯის საპირისპირო პროპორციული. წარმოდგენილი შედეგების პროგრამული უზრუნველყოფის პროგრამა მოცემულია.

ქსელის ტრენინგის დასრულებისთანავე, მოცემული გამოსახულების დომენის ბლოკები კლასიფიცირდება მახასიათებლების სივრცეში თითოეული მათგანის წონის ვექტორთან შესაბამისობით. როდესაც წოდებრივი ბლოკის მახასიათებლების ვექტორი შედის ქსელში, მას ასევე თანაბარია ქსელის წონის ვექტორი. შემდეგ წოდების ბლოკი შედარებულია დომენებთან, რომლებიც რუქაზე მოცემულია მოცემული წონის ვექტორთან, აგრეთვე დომენებთან, რომლებიც ქსელში მიმდებარე წონის ვექტორებთანაა გამოსახული. თვითორგანიზების ნერვულ ქსელზე დაფუძნებული კლასიფიკაციის უპირატესობა წარმოადგენს სურათების კლასების მიმდებარედ ორგანიზების იდეას, რაც უზრუნველყოფილია ქსელის ქსელის საშუალებით. კიდევ ერთი უპირატესობა ის არის, რომ გამოსახულების ტიპების ასეთი კლასტერირება ხდება სურათების კლასების წინასწარ განსაზღვრის აუცილებლობის გარეშე.

5. შედეგები

ცხრილი 1 წარმოგიდგენთ fractal გამოსახულების შეკუმშვის შედარების შედეგებს სამზე სხვადასხვა მეთოდები1 და 2. სურათებში ნაჩვენები სურათების მითითებით. ”ბაზის” მეთოდი წარმოადგენს ოთხი ხის დანაწევრების სტანდარტული მეთოდი, რომელიც განიხილება დომენის კლასიფიკაციის გარეშე. მნიშვნელობა "ოთხკუთხედი დონე" მიუთითებს ოთხი ხის მაქსიმალურ დასაშვებ სიღრმეზე. აქ დიდი რიცხვი იწვევს უფრო მცირე რანგის ბლოკებს, რაც იწვევს დეკოდირებული გამოსახულების უკეთეს ხარისხს, მაგრამ ამავდროულად უარეს შეკუმშვას. "შეცდომის ბარიერი" არის პარამეტრი, რომელიც აკონტროლებს წოდების ბლოკების დაყოფის პირობებს. შეცდომის მნიშვნელობები გამოითვლება საწყისი bitmap სურათის შედარების საშუალებით, 6 განმეორებით გამოყენებული დეკოდირებული გამოსახულების გამოყენებით (მეტი გამეორება წარმოქმნის ოდნავ მცირე შეცდომებს). "საშუალო შეცდომა,%" ("საშუალო შეცდომა") არის საშუალო შეცდომა პიქსელზე, ხოლო "PSNR" არის პიკი სიგნალი – ხმაურის კოეფიციენტი, რომელიც გამოითვლება როგორც. "FO" მეთოდი (მხოლოდ მახასიათებლების გათვალისწინებით) მხოლოდ მახასიათებლების საფუძველზე ადარებს დომენსა და რანგის ბლოკებს მე -3 ნაწილში განხილული ექვსი მახასიათებლის მიხედვით. ბოლო ("SO") მეთოდი კლასიფიკაციას უწევს დომინებს თვითორგანიზების ნერვული ქსელის გამოყენებით, მახასიათებლების გამოყოფასთან ერთად, როგორც ზემოთ განხილულია. თითოეულ შემთხვევაში, სულ 320 დომენის ბლოკი იყო გამოყენებული. დომენების უფრო მეტი რაოდენობა შეიძლება გამოიწვიოს კოდირების დროის გაზრდა და გარკვეულწილად, უკეთესი შეკუმშვის კოეფიციენტები.

შეკუმშვის კოეფიციენტები შეფასებულია საშუალოდ 4 ბაიტის თანაფარდობით თითოეული რანგის ბლოკისთვის ორიგინალი ბიტმპალის 66614 ბაიტი. SO მეთოდი მუშაობს დაახლოებით ორჯერ სწრაფად, ვიდრე FO მეთოდით და ასჯერ უფრო სწრაფად, ვიდრე ძირითადი მეთოდი ("ბლოკი დრო" გამოხატავს შესრულების დროის ზომას, რომელიც არ არის დამოკიდებული სურათის საბოლოო სიზუსტეზე; აქ მოცემული დროის მნიშვნელობები შეესაბამება Pentium 120MHz PC- ს). თვითორგანიზების ქსელმა ტრენინგი მიიღო ცალკე სურათში, განსხვავდება აქ წარმოდგენილი ორი სურათიდან, ამიტომ ტრენინგის დრო არ შედის ამ მეთოდის საერთო დროში. შეკუმშვის კოეფიციენტი და გაშიფრული გამოსახულების ხარისხი, როგორც დაჩქარებული მეთოდებით, ასევე ძირითადი მეთოდით, შედარებულია.

ცხრილი 1 - fractal გამოსახულების შეკუმშვის შედეგები დომენების თვითორგანიზებული კლასიფიკაციის გამოყენებით ("SO" მეთოდი), დომენების შედარება მხოლოდ მახასიათებლების საფუძველზე ("FO") და ძირითადი მეთოდი ("ბაზა")

	Სურათი	შეცდომა ბარიერი	ოთხკუთხედი დონე	ბლოკების რაოდენობა	დრო	დრო თითო ბლოკზე,	საშუალო შეცდომა,%		კოეფიციენტი. შეკუმშვა







(და)	(ბ)

სურათი 2 - (ა): ორიგინალური რასტრული სურათი "ფოთლები" (256 × 256, რუხი 256 გრადაცია); (ბ): გაშიფრული სურათი (6 იმერატი. კვადრატის ხეა 7, საშუალო პიქსელის შეცდომა 3.05%, შეკუმშვა 1.6: 1). დეტალების უფრო მაღალი დონე ამ სურათში იწვევს დაბალ შესრულებას.

6. დასკვნები

დახასიათების კომბინაცია თვითორგანიზების დომენის კლასიფიკაციასთან ნერვული ქსელი უზრუნველყოფს კოდირების მნიშვნელოვან აჩქარებას. სურათის კლასიფიკაცია, რომელიც დამყარებულია მცირე რაოდენობის მახასიათებლებზე, არა მხოლოდ ამცირებს გამოთვლის ხარისხს, არამედ საშუალებას აძლევს ქსელს ტრენინგი ჰქონდეს დაშიფრული გარდა სხვა გამოსახულების შესახებ, რითაც ამცირებს სწავლის დროს კოდირების მთლიანი დროისგან. თვითორგანიზების ქსელი ადგენს საკუთარი დომინანტური კლასების ნაკრების შექმნას, და ასევე განსაზღვრავს დომენის კლასების კლასტერულ ტოპოლოგიას.

ლიტერატურა

E. DeJesus, ”Walking, Talking Web”, ბაიტი, 1997 წლის იანვარი, 81-84.
Y. Fisher, ed., Fractal Image Compression, (New York: Springer-Verlag, 1995).
ა. ჟაკინი, ”გამოსახულების კოდირება დაფუძნებული კონტრაქტული გამოსახულების გარდაქმნების fractal თეორიაზე დაყრდნობით”, IEEE Trans. სურათი Proc. 1, 1992, 18-30.
ა. ბოგდან და ჰ. მეადოუზი, "კოჰონენის ნერვული ქსელი გამოსახულების კოდირებისთვის, კერამიკული ტრანსფორმაციის თეორიის საფუძველზე", Proc. SPIE 1766, 1992, 425-436.
რ. ჰამზაუი, "კოდექსის დალაგება თვითნორგანიზაციული რუქების მიხედვით, ფრაზელის გამოსახულების შეკუმშვისთვის", ნატო ASI Conf. Fractal გამოსახულების დაშიფვრის და ანალიზის შესახებ, 1995 წლის ივლისი.
M. Barnsley, Fractals Everywhere, 2nd ed. (ბოსტონი: Academic Press, 1993).
T. Kohonen, თვითორგანიზებისა და ასოციაციური მეხსიერება, (Springer-Verlag, 1989).
S. Welstead, ნერვული ქსელი და Fuzzy Logic პროგრამები C / C ++, (New York: John Wiley and Sons, 1994).

1. Fractals და fractal შეკუმშვის მეთოდის ისტორია

ცნებები ფრაგმალური და "ფრაკალური გეომეტრია" (fractus - ფრაგმენტებისგან. ლათ.) 1975 წელს შემოგვთავაზეს მათემატიკოსმა ბ. მანდელბროტმა, რომ მოხსენიებულიყო არარეგულარული, მაგრამ თვითნაკეთი სტრუქტურები. ფრაქტული გეომეტრიის დაბადებას უკავშირდება ბ. მანდელბროტის წიგნის 1977 წელს გამოქვეყნება "ბუნების ფრაგმენტული გეომეტრია", რომელიც აერთიანებს 1875-1925 წლებში მოღვაწე მეცნიერთა სამეცნიერო შედეგებს ერთ სისტემაში. ამ მხარეში (პოინკარე, ჯულია, კანტორ და ა.შ.).

Fractals- ის ერთ-ერთი მთავარი თვისებაა თვით-მსგავსება. უმარტივეს შემთხვევაში, ფრაზელის მცირე ნაწილი შეიცავს ინფორმაციას მთლიანი ფრაზელის შესახებ.

კომპიუტერული გრაფიკის თვალსაზრისით, ფრაზელიური გეომეტრია შეუცვლელია რთული არა ევკლიდური ობიექტების წარმოქმნაში, რომელთა გამოსახულებები ძალიან ჰგავს ბუნებრივებს, და როდესაც იგი საჭიროა მრავალი კოეფიციენტის გამოყენებით ძალიან რთული ფორმის ხაზების და ზედაპირების დაზუსტება.

მრავალფეროვანია fractals. პოტენციურად ყველაზე მეტად სასარგებლო ხედი fractals არის fractals საფუძველზე Iterated ფუნქციონირების სისტემა (IFS). IFS მეთოდი fractal ვიზუალიზაციისთვის, რომელიც გამოიგონეს მათმა დიდმა ექსპერტმა მაიკლ ბარნსლიმ და მისმა კოლეგებმა შეერთებული შტატების ტექნოლოგიური ინსტიტუტში. საქართველო (საქართველოს ტექნოლოგიის ინსტიტუტი), ემყარება გამოსახულების ელემენტების თვით-მსგავსებას და მოიცავს საკუთარი თავის რამდენიმე პატარა ფრაგმენტის სურათის მოდერაციას. სპეციალური განტოლებები საშუალებას გაძლევთ გადაიტანოთ, ბრუნოთ და გააფართოვოთ გამოსახულების სექციები; ამრიგად, ეს სექციები დანარჩენი სურათისთვის წარმოადგენს სამშენებლო ბლოკს.

IFS– ის ერთ – ერთი ყველაზე ნათელი (და ცნობილი) სურათია შავი გვიმრა, რომელშიც თითოეული ფოთოლი სინამდვილეში თავად გვიმრის მინიატურული ვერსიაა (იხ. სურ.). იმისდა მიუხედავად, რომ სურათი შეიქმნა კომპიუტერის მიერ ნათესაობის გარდაქმნების მეთოდის გამოყენებით, გვიმრა მთლიანად გამოიყურება ნამდვილი. გამოითქვა მოსაზრება, რომ ბუნება, მცენარეების და ხეების გენეტიკური სტრუქტურის კოდირებისას, იყენებს IFS- ფრაზეულ მეთოდთან ახლოს.

IFS fractals– ს აქვს ერთი ძალიან რეალური და სასარგებლო პროგრამა: მათი გამოყენება შესაძლებელია დიდი ზომის რასტერული სურათების შესაკრავად, მათი ნორმალური ზომის ფრაქციებად. ამ განცხადებიდან გამომდინარეობს ბანაკის კონტრაქციის გარდაქმნის თეორემა (ასევე ცნობილია როგორც კოლაჟის თეორემა) და არის PC– ის ტექნოლოგიური ინსტიტუტის მკვლევარის მუშაობის შედეგი. საქართველო მაიკლ ბარნსლი IFS- ის მხარეში. ამ დასკვნის შედეგად, მან დატოვა ინსტიტუტი, დააპატენტა მისი აღმოჩენა და დააფუძნა Iterated Systems Incorporated. მან მსოფლიოს მოუყვა 1988 წლის იანვარში ჟურნალ Byte- ში მიღწეული წარმატებების შესახებ. თუმცა, ინფორმაცია არ არსებობს ინვერსიული პრობლემის გადაჭრის შესახებ: როგორ მოვიძიოთ ამა თუ იმ გამოსახულების გავლენის გარდაქმნები. იმ დროისთვის ამ ამოცანას გამოსვლის მინიშნებაც კი არ ჰქონდა. ბარნსლის სტატიაში ნაჩვენებია რამდენიმე რეალისტური ფრაზელის სურათი, მაგრამ ისინი ყველა ხელით შეიქმნა.

იდეალურ შემთხვევაში, მსურდა შევძლო კოდის გარდაქმნის სისტემის (IFSM) პოვნა ნებისმიერი გამოსახულებისთვის, რომელიც ამუშავებს გამოსახულებას მოცემული სიზუსტით. თუმცა გამოსავალი ცოტა არ იყოს გამოირჩეოდა. ეს იყო ბარნსელის სტუდენტი, არნად ჟაკინი, რომელმაც პირველად იპოვა იგი. შემოთავაზებულ მეთოდს ეწოდება დანაწილებული იტრირებული ფუნქციონირების სისტემა (PIFS). ამ სქემის თანახმად, გამოსახულების ცალკეული ნაწილები არ არის მთლიანი გამოსახულების მსგავსი, არამედ მხოლოდ მისი ნაწილები.

2. Fractal შეკუმშვის მათემატიკური საფუძველი

ასე რომ, გაითვალისწინეთ მათემატიკური დასაბუთება ფრაქციული შეკუმშვის შესაძლებლობისთვის.

არსებობს რუქა, სადაც არის ყველა შესაძლო სურათის ნაკრები. უ არის რუქების გაერთიანება მე მე:

სად რ - სურათი, და დ მე - ზოგიერთი (შესაძლოა გადახურვის) სურათის არეალი დ. ყოველი გადაქცევა მე მე ითარგმნება დ მე ზე რ მე. Ამგვარად:

ლოგიკური იქნება გამოსახულების წარმოდგენა, როგორც ორი ცვლადის ფუნქცია ვ (x, y). ყველა ასეთი ფუნქციის სიმრავლეზე ჩვენ წარმოგიდგენთ მეტრს (სურათებს შორის მანძილი), მაგალითად, შემდეგნაირად:

ბანაკის თეორემის თანახმად, არსებობს რუქების გარკვეული კლასი, რისთვისაც არსებობს მუდმივი გ< 1 ისეთი, რომ ნებისმიერი სურათისთვის ვ და ზ უთანასწორობა ფლობს

ასეთ რუქებს უწოდებენ კომპრესიულიდა შემდეგი განცხადება მათთვის მართალია:

თუ რაიმე სურათზე F 0 ჩვენ განმეორებით დავიწყებთ რუკების გამოყენებას უ ისე, რომ რაღაც ზღუდავს, როდის მეუსასრულობისკენ მიისწრაფვის, ჩვენ მივიღებთ იგივე სურათს, მიუხედავად იმისა, რა სურათი მივიღეთ F 0:

ეს არის საბოლოო სურათი. ფ უწოდებენ მიმზიდველიან ფიქსირებული წერტილის რუქა W. ასევე ცნობილია, რომ თუ კონვერტაციაა მე მე კომპრესიულია, შემდეგ კი მათი კავშირი უ ასევე კომპრესიულია.

3. ტიპიური fractal შეკუმშვის სქემა

ზემოაღნიშნულიდან გამომდინარე, შეკუმშვის სქემა ასე გამოიყურება: სურათი რ დარტყმა ნაწილებად რ მემოუწოდა რანგის ადგილები. შემდეგი თითოეული ტერიტორიისთვის რ მე იპოვნეთ ტერიტორია დ მე და ტრანსფორმაცია მე მე შემდეგი, რომ შემდეგი პირობები მართალია:

დ მე უფრო დიდი ზომის რ მე.
w i (r i) აქვს იგივე ფორმა, ზომა და პოზიცია, როგორც რ მე.
კოეფიციენტი შენ გარდაქმნები მე მე უნდა იყოს ერთზე ნაკლები.
მნიშვნელობა უნდა იყოს რაც შეიძლება მცირე.

პირველი სამი პირობა ნიშნავს, რომ რუკების შედგენა მე მე იქნება კომპრესიული. და მეოთხე პირობის თანახმად, დაშიფრული სურათი რ და მისი სურათი W (R) ერთმანეთის მსგავსი იქნება. მშვენივრად R \u003d W (R). და ეს ნიშნავს ჩვენს იმიჯს რ და იქნება განსაზღვრული წერტილი უ. ეს არის სადაც გამოსახულების სხვადასხვა ნაწილების ხედვა (აქედან გამომდინარე - სახელი - ე.წ. "Fractal შეკუმშვა") როგორც გაირკვა, თითქმის ყველა რეალური სურათი შეიცავს მსგავს ნაწილებს, ზუსტია გადასაცემი ტრანსფორმაციისთვის.

ამრიგად, გამოსახულების შეკუმშვისთვის უ აუცილებელია:

გამოსახულების რანგის დაყოფა რ მე (დაასახელეთ ტერიტორიები, რომლებიც მოიცავს მთელ სურათს).
თითოეული რანგის ადგილისთვის რ მე იპოვნეთ ტერიტორია დ მე (მოუწოდა დომენი), და რუქა მე მეზემოთ ჩამოთვლილი თვისებებით.
დამახსოვრება გავლენის გადაქცევის ფაქტორები უდომენის ადგილმდებარეობის დებულებები დ მე, ასევე გამოსახულების დომენებად დაყოფა.

შესაბამისად, გამოსახულების დეკომპრესიისთვის აუცილებელია:

შექმენით რამდენიმე (ნებისმიერი) საწყისი სურათი რ 0.
გაიმეორეთ რუკები მასზე უ (ასოციაცია მე მე).
რუქაზე უ კომპრესიული, შედეგად, საკმარისი რაოდენობის გამეორების შემდეგ, გამოსახულება მოვა მიმზიდველთან და შეაჩერებს ცვლილებას. მიმზიდველი არის ჩვენი ორიგინალური სურათი. დეკომპრესია დასრულებულია.

სურათი მიეცით M x N წერტილები (სად მ და ნ მრავლობითი 8), ნაცრისფერი 256 გრადუსი. რანგი და დომენის დომენები მიიღება კვადრატში. ჩვენ დავყოფთ თავდაპირველ გამოსახულებას 8 x 8 წერტილის ზომის რანგებად. ჩვენ ვეძიებთ დომენის დომენებს 16 x 16 წერტილის ზომით ყველა შესაძლო პოზიციის დათვლისას. არსებობს მხოლოდ 8 affine გარდაქმნა, რომელიც კვადრატად გარდაიქმნება კვადრატად (ბრუნვები 0 °, 90 °, 180 °, 270 °, სარკის ანარეკლი ცენტრალურ ჰორიზონტალურ, ცენტრალურ ვერტიკალთან შედარებით, ძირითადი და მეორადი დიაგონალებისგან). ეს რჩება მხოლოდ ფერების გადაქცევის კოეფიციენტების პოვნა. მაგრამ მნიშვნელობები შენ და v (კონტრასტი და სიკაშკაშე) ადვილად შეიძლება ნახოთ ანალიტიკურად.

თუ პიქსელის ფერის მნიშვნელობების ორი რიგი არსებობს a 1, a 2, ..., N (დომენის დომენი) და b 1, b 2, ..., b N (რანგის არეალი), მაშინ შესაძლებელია მინიმუმამდე დაიყვანოთ პიქსელების ფერის სტანდარტული გადახრა, რაც გამოსახულების განსხვავების მეტრიკის ვარიანტია:

ამისათვის საკმარისია ნაწილობრივი წარმოებულების განტოლება რ მიერ შენ და v ნულამდე, და გადაწყვიტეთ განტოლება შენ და v. მიიღება შემდეგი გამონათქვამები:

ხოლო თუ

მაშ, რა მონაცემები უნდა იყოს შენახული, როგორც შედეგი. რანგის უბნებში რანგირების ბადე მუდმივია ყველა სურათისთვის; მისი შენახვა არ არის საჭირო. რჩება რანგი სფეროების პოზიცია (ზედა მარცხენა კუთხე), კონვერტაციის ნომერი და სიკაშკაშის და კონტრასტის კოეფიციენტები.

4. შეკუმშვის რაციონის და გამოთვლითი ხარჯების შეფასება

წოდების არეალის სრული განსაზღვრისთვის მონაცემთა ზომა გამოითვლება ფორმულით:

სად X - დომენის ქვედა მარცხენა კუთხის კოორდინატების შესანახად საჭირო ბიტების რაოდენობა, ტ - ბიტების ტრანსფორმაციის ტიპის შესანახად საჭირო ბიტინების რაოდენობა, უ და ვ - კონტრასტისა და სიკაშკაშის კოეფიციენტების შესანახად.

სად ნბ და მბ - თითოეული კოორდინატის შესანახად საჭირო ბიტის რაოდენობა გამოითვლება შემდეგი ფორმულით:

Აქ ჭერი - დამრგვალების ფუნქცია მაქსიმალურ რიცხვზე, მგ და ნდ - ჰორიზონტალურად და ვერტიკალურად ჯდება დომენების რაოდენობა, რომლებიც გამოითვლება ფორმულებით:

სად ვ და თ - ვერტიკალური და ჰორიზონტალური გამოსახულების ზომები, ზომა - დომენის ბლოკის ზომა, ნაბიჯი - ნაბიჯი დომენის არეალის მოსაძებნად.

კონვერტაციის შესანახად ტ 3 ბიტი იყო საჭირო.

შენახვისთვის უ და ვ შესაბამისად საჭიროა 9 და 7 ბიტი.

მაგალითად, გადავიღოთ სურათი 256 x 256 პიქსელით, ჩვენ განვსაზღვრავთ დომენის არეალს 4 პიქსელის ნაბიჯით.

Nd \u003d Md \u003d (256 - 8 + 1) / 4 \u003d 62

Nb \u003d Mb \u003d CEIL (ჟურნ. 2 62) \u003d 6

Z \u003d 12 + 3 + 6 + 6 \u003d 27

შეკუმშვის რაციონი ს ქმნის

S \u003d (8 * 8 * 8) / 27 \u003d 19

შეკუმშვის კოეფიციენტი არ არის ისეთი დიდი, როგორც ჩვენ გვსურს, მაგრამ შეკუმშვის პარამეტრი შორს არის ოპტიმალურიდან, და რაციონი შეიძლება მნიშვნელოვნად გაიზარდოს.

ახლა მოდით შევაფასოთ ამ ალგორითმის გამოთვლითი სირთულე. შეკუმშვის ეტაპზე, ჩვენ უნდა დავასახელოთ ყველა დომენის დომენი - 1.024 ცალი, თითოეული - ყველა რანგის დომენის - 58,081 ცალი (1-ლი ეტაპზე), და თითოეული მათგანისთვის, თავის მხრივ, ყველა 8 გარდაქმნა. მთლიანობაში, მიღებულია 1,024 x 58,081 x 8 \u003d 475,799,552 მოქმედება. უფრო მეტიც, ეს მოქმედებები არ არის ტრივიალური და მოიცავს რამდენიმე მატრიცულ ოპერაციას, რაც, თავის მხრივ, მოიცავს მცურავი წერტილების რიცხვების გამრავლებისა და გაყოფის ოპერაციებს.

სამწუხაროდ, თანამედროვე კომპიუტერიდანაც კი (კერძოდ, ასეთი აპარატებისთვის მე მინდოდა ალგორითმის განხორციელება), დაუშვებლად დიდი დრო დასჭირდებოდა გამოსახულების შეკუმშვას, რომლის ზომა მხოლოდ 256 x 256 პიქსელი იყო. ცხადია, რომ განხილულ ალგორითმს ოპტიმიზაცია სჭირდება.

5. შეკუმშვის ალგორითმის ოპტიმიზაცია

ალგორითმის ოპტიმიზაცია საჭიროა რამდენიმე მიმართულებით: სიჩქარით, სურათის ხარისხით, შეკუმშვის კოეფიციენტში.

შემდეგი ზომების მიღება შეიძლება განხორციელდეს გამოთვლითი ხარჯების შემცირების მიზნით:

დაათვალიერეთ დომენის არეალი არ არის სრული, მაგრამ რამდენიმე ნაბიჯით. ეს ასევე გაზრდის შეკუმშვის კოეფიციენტს, მაგრამ გავლენას მოახდენს გამოსახულების ხარისხზე.
ეძებს არა საუკეთესო დომენის, არამედ ზოგის დაკმაყოფილებისთვის ე. მიუხედავად იმისა, რომ ამან შეიძლება მნიშვნელოვნად გაზარდოს შეკუმშვის სიჩქარე, მაგრამ ასეთ ტექნიკას ასევე შეუძლია მნიშვნელოვნად შეამციროს შედეგად მიღებული გამოსახულების ხარისხი. ამ შემთხვევაში, ხარისხი დიდწილად დამოკიდებულია მეტრიკის ადეკვატურობაზე, სურათებს შორის განსხვავების შესახებ.
დომენის ძებნისას, ის არ არის დომენი, რომელიც გარდაიქმნება, მაგრამ არის რანგი. ამისათვის მოსახერხებელია შენახვის 8 ვარიანტის განთავსება სხვადასხვა ტრანსფორმაციებით. ამ შემთხვევაში, ინვერსიული ტრანსფორმაცია უნდა დაიწეროს შედეგად ფაილში. ყველა გარდა ორი გარდაქმნისა, გარდაქმნა თავისთავად საპირისპიროა. 90 ° და 270 ° ბრუნვისთვის, თქვენ უნდა ჩაწეროთ როტაცია, შესაბამისად, 270 ° და 90 °. ეს მნიშვნელოვნად შეამცირებს გამოთვლის ხარჯებს, მაგრამ ასევე მნიშვნელოვნად გაზრდის ხარჯებს. შემთხვევითი წვდომის მეხსიერება.
დომენის ძებნის მიზნით, შეგიძლიათ გამოიყენოთ არა უხეში ძალა, მაგრამ ნებისმიერი პირობითი არაწრფივი გლობალური ოპტიმიზაციის ალგორითმი, მაგალითად, annealing სიმულაციის ალგორითმი ან გენეტიკური ალგორითმი. ამ შემთხვევაში, იქნება მხოლოდ სამი ცვლადი პარამეტრი (დომენის რეგიონის კოორდინატები და affine ტრანსფორმაციის ნომერი), ხოლო დომენის დომენის root- საშუალო-კვადრატული გადახრა ერთი რანგიდან იქნება ობიექტური ფუნქცია.

ხარისხის გაუმჯობესების მიზნით: დომენის რეგიონის გამოვლენის შემთხვევაში, რომელიც აკმაყოფილებს მოცემულობას ე, რანგირების ადგილი შეიძლება დაიყოს 4 ქვედემოდში და თითოეული მათგანისთვის მოძებნოთ დომენი. ეს შეიძლება გაკეთდეს კიდევ უფრო რეკურსიულად, სანამ არ მიიღწევა გარკვეული მინიმალური ზომა ან ერთი პიქსელი. მაგრამ ეს გაზრდის გამოთვლების ხარჯებს და შეამცირებს შეკუმშვის კოეფიციენტს.

შეკუმშვის რაციონის გასაზრდელად შესაძლებელია მონოფონიური ბლოკების იდენტიფიცირება. მყარი ბლოკი ჩვენ მოვუწოდებთ რანგის რეგიონს, რომელშიც სტანდარტული გადახრა eigenvalue– სგან არ აღემატება გარკვეულობას ე ”. ამ შემთხვევაში, მხოლოდ წერტილის საშუალო სიკაშკაშე ჩაიწერება გამომავალი ფაილში, ამის გამო მიიღწევა 1 – დან 64 – მდე შეკუმშვა (8 – ე ზომების რანგის უბნებისათვის).

6. განხორციელება

ამ სტატიაში აღწერილია მხოლოდ fractal შეკუმშვის ალგორითმის უმარტივესი ვერსია. მაიკლ ბარნსლნი და ალან სლოანი იპოვა ამ პრობლემის გადასაჭრელად მეთოდი, რომელიც ვრცელდება რასტრული გამოსახულების ნებისმიერი ფორმით, მაშინაც კი, თუ მასში თვითმყოფადობის აშკარა ელემენტები შესამჩნევი არაა. ამ მეთოდის ყველა დეტალი არ გახმაურებულა, მაგრამ ის ფაქტი, რომ Microsoft Encarta პაკეტი იყენებს Barnsley შეკუმშვის ბიბლიოთეკას, იძლევა საკმარის მტკიცებულებებს მისი ეფექტურობისა და ზოგადი მიმართულების სასარგებლოდ ყველა სახის სურათზე.

ერთადერთი, რაც Barnsley-Sloan მეთოდის შესახებ ვიცით არის ის, რომ სტანდარტული დამუშავების ტექნიკის გამოყენებით (სხვათა შორის, ამ საიტზე ასევე შეგიძლიათ იპოვოთ მრავალი მათგანის აღწერა), როგორიცაა ტექსტურული ცვალებადობის ხაზგასმა და ანალიზი, გამოსახულება იყოფა არარეგულარული ფორმის სეგმენტებად . შემდეგ ხორციელდება გარდაქმნების მთელი რიგი, რომელიც განსაზღვრავს გამოსახულებას, როგორც ამ სეგმენტების გაერთიანებას, ხოლო გარდაქმნებზე იწერება როგორც IFS– ის ნაკრები. იერენტული პროცესის საშუალებით, რომელიც გამოყენებულია გვიმრის გამოსახულების გასაშენებლად, გამოსახულების რეკონსტრუქცია ხდება საოცარი სიზუსტით. Affine გარდაქმნების რაოდენობა არ არის დაფიქსირებული 8; ზოგიერთ დაშიფრულ სურათს შეუძლია გამოიყენოს 100 ან მეტი ნათესაობის კონვერსია.

მე, თავის მხრივ, შემიძლია წარმოგიდგინოთ განხორციელების ვარიანტი ზემოთ აღწერილი ალგორითმისთვის, რომელიც არ განსხვავდება სიჩქარითა და მაღალი ხარისხით, მაგრამ ამის მიუხედავად, ეს შეიძლება მარტივი კვლევის საშუალებად იქცეს. .Rar არქივი, რომელიც ხელმისაწვდომია ჩამოტვირთვა, ასევე შეიცავს წყაროს კოდი.

თქვენ შეგიძლიათ იპოვოთ უფრო მოწინავე განხორციელება ვებსაიტზე.

Fractals არის გასაოცარი მათემატიკური ობიექტები, captivating მათი სიმარტივის და მდიდარი შესაძლებლობების მშენებლობის რთული ბუნების მხოლოდ რამდენიმე კოეფიციენტი და მარტივი განმეორებითი სქემა.
ეს არის შესაძლებლობები, რომელთა საშუალებითაც შესაძლებელია მათი გამოყენება გამოსახულების შეკუმშვისთვის, განსაკუთრებით ბუნების ფოტოებისთვის და სხვა რთული თვით-მსგავსი სურათებისთვის.
ამ სტატიაში შევეცდები მოკლედ ვუპასუხო მარტივ კითხვას: "როგორ კეთდება ეს?"

დასაწყისისთვის, თქვენ ჯერ კიდევ უფრო ღრმად უნდა ჩასხდეთ მათემატიკას და დანერგოთ რამდენიმე განმარტება.
შემდეგი იქნება სასარგებლო:

მეტრიკი არის სივრცეში განსაზღვრული ფუნქცია, რომელიც ბრუნდება მანძილი ამ სივრცის ორ წერტილს შორის. მაგალითად, ჩვეულებრივი ევკლიდური მეტრიკა. თუ კოსმოსური მეტრია მოცემული, მას მეტრიკა ეწოდება. მეტრმა უნდა დააკმაყოფილოს გარკვეული პირობები, მაგრამ ჩვენ ღრმად არ წავა.
შეკუმშვის რუქა (ტრანსფორმაცია) არის ფუნქცია მეტრულ სივრცეში, რომელიც ერთნაირად ამცირებს მანძილს სივრცეში ორ წერტილს შორის. მაგალითად, y \u003d 0.5x.

შეკუმშვის რუქებს მნიშვნელოვანი ქონება გააჩნია. თუ ჩვენ რაიმე წერტილს მივიღებთ და დავიწყებთ iteratively გამოყენებას იგივე შეკუმშვის რუკა მასზე: f (f (f (f ... f (x))), მაშინ შედეგი ყოველთვის იქნება იგივე წერტილი. რაც უფრო მეტჯერ მივმართავთ, უფრო ზუსტად ვხვდებით ამ აზრს. Მან დარეკა ფიქსირებული წერტილი და თითოეული კომპრესიული რუქისთვის ის არსებობს და მხოლოდ ერთი.

რამდენიმე affine შეკუმშვის რუქა ქმნის განმეორებითი ფუნქციების სისტემას (CIF). სინამდვილეში, CIF არის გამრავლების მანქანა. იგი იღებს თავდაპირველ გამოსახულებას, ამახინჯებს მას, მოძრაობს მას და ა.შ. რამდენჯერმე.
მაგალითად, CIF– ს დახმარებით, Sierpinski სამკუთხედი აგებულია სამი ფუნქციისაგან:

ორიგინალი სამკუთხედი მრავლდება სამჯერ, მცირდება და გადადის. ა.შ. თუ ამ გზას გავაგრძელებთ უსასრულობამდე, მივიღებთ ცნობილ ფრაკალს, რომლის ფართობია 0 და განზომილება 1.585.

თუ CIF– ში შედის ფუნქციები კომპრესიული, მაშინ თავად CIF– ს აქვს გარკვეული წერტილი. მაგრამ ეს "წერტილი" აღარ იქნება N- განზომილებიან სივრცეში ნაცნობი წერტილი, მაგრამ ასეთი წერტილების ერთობლიობა, ანუ გამოსახულება. ჰქვია მიმზიდველი CIF CIF– სთვის ზემოთ, სიერაპსკის სამკუთხედი მიმზიდველი იქნება.

აქ ჩვენ შემდეგ ეტაპზე გადავდივართ - გამოსახულების სივრცე. ამ სივრცეში:

სივრცის წერტილი არის გამოსახულება.
წერტილებს შორის მანძილი გვიჩვენებს, თუ რამდენად მსგავსია სურათები ერთმანეთთან, რამდენად “ახლოს” (ბუნებრივია, თუ ამას დაყენებთ).
შეკუმშვის რუქა ხდის ნებისმიერი ორი სურათის უფრო მსგავსი (მოცემული მეტრიკის მნიშვნელობით).

CIF– ს მიღება, მიმზიდველი პოვნა ადვილია. ნებისმიერ შემთხვევაში, კომპიუტერი გქონდეთ ხელთ. შეგიძლიათ მიიღოთ აბსოლუტურად ნებისმიერი საწყისი სურათი და დაიწყოთ მასზე CIF– ის გამოყენება. მაგალითი იგივე სამკუთხედით, მაგრამ უკვე აშენებულია კვადრატი:

გამოდის, რომ საკმაოდ რთული ფიგურის ასაშენებლად, 18 კოეფიციენტი დაგვჭირდა. მოგება, როგორც ამბობენ, აშკარაა.
ახლა რომ ვიცოდეთ როგორ გადავწყვიტოთ ინვერსიული პრობლემა - მოზიდვა, CIF აშენება ... მაშინ საკმარისია თქვენი კატის ფოტოების მსგავსი მოზიდვის სურათი გადაიღოთ და შეგიძლიათ საკმაოდ მომგებიანი კოდირება.

აქ, ფაქტობრივად, პრობლემები იწყება. თვითნებური გამოსახულებები, განსხვავებით fractals- სგან, არ არის თვითნაკეთი, ამიტომ ამ ამოცანის ასე მარტივად გადაწყვეტა არ ხდება. როგორ გავაკეთოთ ეს გამოიგონეს 1992 წელს არნოლდ ჟაკინი, მაშინ როდესაც იგი იყო კურსდამთავრებული სტუდენტი მაიკლ ბარნსლი, რომელიც ითვლება ფრაქტიური კომპრესიის მამა.

ჩვენ გვჭირდება თვით-მსგავსება - სხვაგვარად, რომ გავლენის გარდაქმნები, შეზღუდული შესაძლებლობებით, ვერ შეძლებენ სურათების რეალობასთან მიახლოებას. და თუ ეს არ არის ნაწილსა და მთლიანს შორის, მაშინ შეგიძლიათ მოძებნოთ ნაწილსა და ნაწილს შორის. როგორც ჩანს, ჟაკინი დაახლოებით იგივე მიზეზით ასაბუთებდა.

კოდირების გამარტივებული სქემა ასე გამოიყურება:

სურათი იყოფა მცირე, არამეტყველ კვადრატულ არეალებად, რომელსაც წოდებრივი ბლოკები ეწოდება. სინამდვილეში, ის იყოფა კვადრატებად. იხილეთ სურათი ქვემოთ.
ოთხჯერ დიდი რანგის - დომენის ბლოკების ყველა შესაძლო გადახურვის ბლოკის აუზი შენდება.
თითოეული რანგის ბლოკისთვის, ჩვენ თავის მხრივ "ვცდილობთ" დომენის ბლოკებს და ვეძებთ ტრანსფორმაციას, რაც დომენის ბლოკს ქმნის ყველაზე მეტად მსგავსი რანგის მიხედვით.
კონვერტაციის დომენის ბლოკის წყვილი, რომელიც იდეალთან ახლოს მივიდა, რუქების ბლოკშია განთავსებული. კონვერტაციის კოეფიციენტები და დომენის ბლოკის კოორდინატები ინახება კოდირებულ სურათში. ჩვენ არ გვჭირდება დომენის ბლოკის შინაარსი - გახსოვთ, არ გვავიწყდება, რა დასაწყისიდან დავიწყოთ.

სურათზე, რანგის ბლოკი აღინიშნება ყვითლად, შესაბამისი დომენი ერთი წითლად. ნაჩვენებია აგრეთვე კონვერტაციის ეტაპები და შედეგი.

ოპტიმალური ტრანსფორმაციის მიღწევა ცალკე საკითხია, მაგრამ ეს არ არის დიდი საქმე. მაგრამ მიკროსქემის კიდევ ერთი ნაკლი ჩანს შეუიარაღებელი თვალით. შეგიძლიათ გამოთვალოთ რამდენი 32 32 დომენი შეიცავს ორი მეგაპიქსელის გამოსახულებას. თითოეული რანგის ბლოკის მათი ამომწურავი ძებნა ამ ტიპის შეკუმშვის მთავარი პრობლემაა - დაშიფვრას ძალიან დიდი დრო სჭირდება. რა თქმა უნდა, ისინი ამით იბრძვიან სხვადასხვა ხრიკების გამოყენებით, როგორიცაა ძებნის არეალის შემცირება ან დომენის ბლოკების წინასწარი კლასიფიკაცია. ხარისხთან სხვადასხვა დაზიანებით.

დეკოდირება მარტივია და საკმაოდ სწრაფიც. ჩვენ ვიღებთ ნებისმიერ სურათს, ვყოფთ მას რანგირებად ადგილებს და თანმიმდევრულად ვცვლით მათ პატივისცემის შედეგებით. კონვერტაცია დომენის არეალი (რასაც იგი შეიცავს ამ წუთში). რამდენიმე გამეორების შემდეგ, თავდაპირველი სურათი თავისთავად გამოიყურება:

ალბათ საკმარისია ინფორმაციის შემოღება. დაინტერესებულ პირებს შეუძლიათ წაიკითხონ შესაბამისი სტატიები

1992 წლის დეკემბერში, შობამდე, Microsoft- მა გამოუშვა ახალი Microsoft Encarta CD. მას შემდეგ, ამ მულტიმედიურ ენციკლოპედიაში, რომელიც შეიცავს ინფორმაციას ცხოველების, ყვავილების, ხეების და სცენური ლაქების შესახებ, CD-ROM- ზე ყველაზე პოპულარული ენციკლოპედიების სია არ დაუტოვებიათ. ბოლო გამოკითხვაში, Microsoft Encarta- მა კვლავ დაიკავა პირველი ადგილი, მისი უახლოესი კონკურენტის, Compton Multimedia Encyclopedia. ამ პოპულარობის მიზეზი მდგომარეობს იმაში გამოყენებადობა , მაღალი ხარისხის სტატიები და, რაც მთავარია, დიდი რაოდენობით მასალებში. დისკი შეიცავს 7 საათის ბგერას, 100 ანიმაციურ ვიდეოს, დაახლოებით 800 მასშტაბურ რუქას, ასევე 7000 მაღალი ხარისხის ფოტოს. და ეს ყველაფერი - ერთ დისკზე! შეგახსენებთ, რომ ჩვეულებრივი 650 MB კომპაქტური დისკი შეკუმშვის გარეშე შეიძლება შეიცავდეს ან მაღალი ხარისხის ხმის 56 წუთს, ან 1 საათის ვიდეო რეზოლუციას 320x200 რეზოლუციით MPEG-1 ფორმატით, ან 700 სრული ფერადი სურათი 640x480 ზომის. მეტი ინფორმაციის მოსათავსებლად საჭიროა საარქივო საკმარისად ეფექტური ალგორითმები. ჩვენ არ შევჩერდებით ვიდეო და ხმის დაარქივების მეთოდებზე, ჩვენ განვიხილავთ გრაფიკული ინფორმაციის fractal შეკუმშვის ისტორიას. ფრაქტული გეომეტრიის დაბადებას ჩვეულებრივ უკავშირდება 1977 წელს ბ. მანდელბროტის წიგნის Fractal Geometry of Nature ბუნების გამოქვეყნება. წიგნის ერთ-ერთი მთავარი იდეა ის იყო, რომ ტრადიციული გეომეტრიის (ანუ ხაზებისა და ზედაპირების გამოყენებით) გამოყენებით, ძალიან რთულია ბუნებრივი ობიექტების წარმოდგენა. Fractal გეომეტრია განსაზღვრავს მათ ძალიან მარტივად. 1981 წელს ჯონ ჰატინსონმა გამოაქვეყნა სტატია სახელწოდებით Fractals and self-მსგავსება, რომელშიც წარმოდგენილია ფრაგმენტების აგების თეორია Iterated ფუნქციონირების სისტემის (IFS) გამოყენებით. ოთხი წლის შემდეგ, გამოქვეყნდა სტატია მაიკლ ბარნსლისა და სტეფან დემკოს მიერ, რომელმაც უკვე გააკეთა საკმაოდ კარგად გაწონასწორებული IFS თეორია. 1987 წელს, ბარნსლიმ დააარსა Iterated Systems, კომპანია, რომლის ძირითადი საქმიანობაა ახალი ალგორითმების და პროგრამული უზრუნველყოფის შექმნა ფრაქსალების გამოყენებით. სულ რაღაც ერთი წლის შემდეგ, 1988 წელს, მან გამოუშვა ფუნდამენტური ნაშრომი Fractals ყველგან. IFS- ის აღწერის გარდა, მან მიიღო შედეგი, რომელიც დღეს ცნობილია როგორც კოლაჟის თეორემა, რომელიც ემყარება ფრაგმენტული შეკუმშვის იდეის მათემატიკურ საფუძველს. თუ fractal მათემატიკის გამოყენებით სურათების მშენებლობას შეიძლება პირდაპირ დავალებად ვუწოდოთ, მაშინ გამოსახულების მშენებლობა IFS არის შებრუნებული პრობლემა. დიდი ხნის განმავლობაში ითვლებოდა უხსნად. პირველი სტატია ბარნსლის კომპრესიაში წარმატების შესახებ გამოქვეყნდა ჟურნალ BYTE- ში 1988 წლის იანვარში. მასში არ იყო აღწერილი ინვერსიული პრობლემის გადაჭრა, მაგრამ რამდენიმე სურათი შეკუმშული იყო 1: 10000 თანაფარდობით, რაც აბსოლუტურად განსაცვიფრებელი იყო. მაგრამ თითქმის მაშინვე აღინიშნა, რომ მიუხედავად მიმზიდველი სახელებისა ("ბნელი ტყე", "მონტერის სანაპირო", "მზესუმზირა ველი"), ეს სურათები ფაქტობრივად ხელოვნური ხასიათისა იყო. ამან გამოიწვია უამრავი სკეპტიკური შენიშვნა, რომელიც გაამწვავა ბარნსელის მიერ ნათქვამმა, რომ ”საშუალო სურათის გაკეთება მოითხოვს დაახლოებით 100 საათის განმავლობაში მუშაობას მძლავრი ორმაგი პროცესორის სამუშაო სადგურზე შეკუმშვისთვის და პირის მონაწილეობით”. როდესაც ინფორმაცია 1991 წელს fractal შეკუმშვის შესაძლებლობების შესახებ პირველად გამოქვეყნდა, ამან ძალიან ბევრი ხმაური გამოიწვია. მაიკლ ბარნსლი, ალგორითმის ერთ-ერთი შემქმნელი, ირწმუნებოდა, რომ შემუშავდა მეთოდი ორიგინალ სურათთან ფრაქტული კოეფიციენტების მაქსიმალურად მოსაძიებლად. Fractals, დინამიური სისტემების ეს მშვენიერი გამოსახულებები, ადრე გამოყენებული იყო კომპიუტერულ გრაფიკაში, ძირითადად, ცის, ფოთლების, მთების, ბალახის სურათების მოსაწყობად. ბუნებრივი და, რაც მთავარია, საიმედოდ მიბაძვა ბუნებრივი ობიექტის სურათს, შეიძლება დაზუსტდეს მხოლოდ რამდენიმე ფაქტორი. გასაკვირი არაა, რომ კომპრესიაში ფრაქტალების გამოყენების იდეა უფრო ადრე წარმოიშვა, მაგრამ შესაბამისი ალგორითმის აგება თითქმის შეუძლებელი იყო, რომელიც კოეფიციენტებს შეარჩევს მისაღები დროში. ასე რომ, 1991 წელს აღმოაჩინეს ასეთი ალგორითმი. გარდა ამისა, ახალი ტექნოლოგიების არაერთი უნიკალური შესაძლებლობა გამოცხადდა მის შემდგომ სტატიებში. ასე რომ, fractal Archiver საშუალებას იძლევა, მაგალითად, როდესაც შეფუთვისას, თვითნებურად შეცვალოთ გამოსახულების გარჩევადობა (ზომა) მარცვლეულის ეფექტის გარეშე. უფრო მეტიც, იგი decompresses ბევრად უფრო სწრაფად, ვიდრე უახლოესი კონკურენტი, JPEG, და არა მხოლოდ სტატიკური გრაფიკა, არამედ ვიდეო. როგორც მაგალითად, პროგრამა ნაჩვენები იქნა i386 / 33 MHz პროცესორით მოწყობილობაზე, ფერადი ვიდეო ფილმის სიხშირით, 20 ჩარჩო წამში, ყოველგვარი ტექნიკის მხარდაჭერის გარეშე. JPEG– სგან განსხვავებით, ალგორითმი თავდაპირველად შეიცავდა ზარალის ხარისხის გაკონტროლების შესაძლებლობას ისეთ სფეროებში, რომლებსაც აქვთ მაქსიმალური ხარისხის დაკარგვა. ზოგადად სურათების შეკუმშვის კოეფიციენტი დაახლოებით იგივეა, რაც JPEG– სთვის, მაგრამ ზოგიერთ რეალურ სურათში 10,000 (!) ჯერ შეკუმშვა მოხდა. 1992 წელს, არნად ჯეკვინმა, ბარნსლის ერთ-ერთმა თანამშრომელმა, აღწერა პრაქტიკული ალგორითმი და გამოაქვეყნა ის დისერტაციის დაცვის დროს. ეს ალგორითმი უკიდურესად ნელი იყო და არ ითვალისწინებდა შეკუმშვას 10,000 ჯერ (სრული ფერადი 24-ბიტური სურათი მისი დახმარებით შეიძლება შეკუმშოს მნიშვნელოვანი დანაკარგების გარეშე, თანაფარდობით 1: 8 - 1:50); მაგრამ უდავო უპირატესობა ის იყო, რომ ადამიანის ჩარევა მთლიანად გამოირიცხა. დღეს, ყველა ცნობილი Fractal შეკუმშვის პროგრამა ემყარება ჯეკვინის ალგორითმს. 1993 წელს Iterated Systems– მა გამოუშვა თავისი პირველი კომერციული პროდუქტი. მას უამრავი პუბლიკაცია მიეძღვნა, მაგრამ კომერციული წარმატების შესახებ საუბარი არ ყოფილა, პროდუქტი საკმარისად "ნედლეული" იყო, კომპანიამ არ გადადგა რაიმე სარეკლამო ნაბიჯი, და რთული იყო პროგრამის შეძენა. 1994 წელს Yuval Fisher– მა უზრუნველყო კვლევითი პროგრამის წყაროს კოდი, რომელშიც გამოყენებულია გამოსახულების დაშლა ოთხკუთხედ ხეზე და განხორციელდა ძებნის ოპტიმიზაციის ალგორითმები. მოგვიანებით, კიდევ რამდენიმე კვლევითი პროექტი გამოჩნდა, რომლებმაც Fisher პროგრამა გამოიყენეს, როგორც პროგრამის საწყის ვერსიად. 1995 წლის ივლისში ტროტჰეიმში (შვედეთი) ჩატარდა პირველი სასკოლო-კონფერენცია, რომელიც მიეძღვნა ფრაქტოზულ შეკუმშვას. ამრიგად, ფრაგმენტული შეკუმშვის სფეროში მრავალი მნიშვნელოვანი მოვლენა მოხდა ბოლო სამი წლის განმავლობაში: ალგორითმი ახლახან იწყებს განვითარებას. როგორც უკვე აღვნიშნეთ, Fractal შეკუმშვის ალგორითმის მინუსი არის დიდი კოდირების დრო. ამ პრობლემის მოგვარება 1999 წელს შემოთავაზებულ იქნა D.S. Vatolin- ს თავის სტატიაში "DCT- ის გამოყენებით, რომ დააჩქაროს ფრაგმალური გამოსახულების შეკუმშვა." ნაშრომში განხილულია დისკრეტული კოსინეტიკური ტრანსფორმაციის (DCT) გამოყენება, რათა დააჩქაროს ფრაგმენტული გამოსახულების შეკუმშვის ალგორითმის მოქმედება. DCT გამოიყენება ბლოკის მთლიანი ნაკრების 256 კლასში დანაწევრებისთვის, რაც საშუალებას გაძლევთ ალგორითმის თითქმის 100-ჯერ დაჩქარება, სურათის ხარისხის მიღებით დანაკარგებით. სხვა ნამუშევრებისგან განსხვავებით, ამ სტატიაში დეტალურად არის აღწერილი შემუშავებული ალგორითმი და მიღებული შედეგები.

მეთოდის იდეა

Fractal შეკუმშვა ემყარება იმ ფაქტს, რომ გამოსახულება ჩვენ უფრო კომპაქტურ ფორმას წარმოვადგენთ - Iterated ფუნქციონირების სისტემის კოეფიციენტების გამოყენებით (შემდგომში (IFS)). სანამ თვითონ დაათვალიერებთ საარქივო პროცესს, გადავხედოთ, თუ როგორ ქმნის IFS გამოსახულებას, ანუ დეკომპრესიის პროცესს.

მკაცრად რომ ვთქვათ, IFS არის სამგანზომილებიანი მიჯნური გარდაქმნების ერთობლიობა, ჩვენს შემთხვევაში, ერთი გამოსახულების სხვაზე თარგმნა. სამგანზომილებიან სივრცეში წერტილები გარდაიქმნება (კოორდინატი, y_coordinate, სიკაშკაშე).

ეს აშკარად აჩვენა ამ პროცესმა M. F. Barnsley წიგნში. „ფოტოკოპირების აპარატის“ კონცეფცია დაინერგა, რომელიც მოიცავს ეკრანს, რომელზეც გამოსახულია ორიგინალი სურათი, და ლინზების სისტემა, რომელიც გამოსახულებას ასრულებს სხვა ეკრანზე (სურათი 2.2):

Enses ლინზებს შეუძლიათ დაპროექტონ გამოსახულების ნაწილი თვითნებური ფორმაზე
ნებისმიერი სხვა ადგილი ახალი სურათის მიხედვით;

უბნები რომელშიცპროგნოზირებული სურათები არ არის კვეთა;
ობიექტივი შეუძლია შეცვალოს სიკაშკაშე და შეამციროს კონტრასტი;

May შეიძლება ობიექტივი შეიხვიე და გადატრიალდითქვენი სურათის ფრაგმენტი;

■ ობიექტივი უნდა მასშტაბი(და მხოლოდ ამცირებს) მისი გამოსახულების ფრაგმენტი.

წყარო

/ სურათი

შედეგად მიღებული სურათი

სურ. 2.2. Barnsley მანქანა

ლინზების მოწყობით და მათი მახასიათებლების შეცვლით, ჩვენ შეგვიძლია გავაკონტროლოთ შედეგად მიღებული სურათი. აპარატის ექსპლუატაციის ერთი განმეორება არის ის, რომ ახალი აშენებულია ორიგინალი გამოსახულებისგან დიზაინის გამოყენებით, რის შემდეგაც ახალი მიიღება როგორც წყარო. ამტკიცებენ, რომ გამეორების დროს ვიღებთ გამოსახულებას, რომელიც შეწყვეტს ცვლილებას. ეს დამოკიდებული იქნება მხოლოდ ლინზების ადგილმდებარეობასა და მახასიათებლებზე და ეს დამოკიდებული არ იქნება თავდაპირველ სურათზე. ამ სურათს ჰქვია ფიქსირებული წერტილიან მიმზიდველიმოცემული IFS. შესაბამისი თეორია იძლევა გარანტირებულს ზუსტად ერთ ფიქსირებულ წერტილს თითოეული IFS- სთვის.

იმის გამო, რომ ლინზების რუქა კონუსურია, თითოეული ობიექტივი პირდაპირ განსაზღვრავს თვითნაირიტერიტორიები ჩვენს სურათში. თვით-მსგავსების წყალობით, ვიღებთ სურათის რთულ სტრუქტურას ნებისმიერ გადიდებაში. ამრიგად, ინტუიციურად აშკარაა, რომ ის განუსაზღვრელი ფუნქციების სისტემას განსაზღვრავს fractal(არა მკაცრად - თვითნაკეთი მათემატიკური ობიექტი).

ყველაზე ცნობილია IFS– ით მიღებული ორი სურათი: სიერპინსკის სამკუთხედი(ნახ. 2.3) და გვიმრა ბარნსლი(სურათი 2.4).

სიერპინსკის სამკუთხედი განისაზღვრება სამით, ხოლო ბარნსლის გვიმრა - ოთხით affine გარდაქმნები(ან ჩვენი ტერმინოლოგიით "ლინზები"). თითოეული კონვერტაცია დაშიფრულია სიტყვასიტყვით წაკითხული ბაიტით, ხოლო მათი დახმარებით აშენებულ სურათს შეუძლია მიიღოს რამდენიმე მეგაბაიტი.

სურ. 2.3. სიერპინსკის სამკუთხედი სურათი 2.4. გვიმრა ბარნსლი

სავარჯიშო.სურათზე მიუთითეთ 4 ადგილი, რომელთა ერთობლიობა მოიცავს მთელ სურათს და თითოეული მათგანი მსგავსი იქნება მთელ სურათზე (ნუ დაივიწყებთ გვიმრის ღეროს).

ზემოთქმულიდან ირკვევა, თუ როგორ მუშაობს არქივი და რატომ სჭირდება ამდენი დრო. სინამდვილეში, fractal შეკუმშვა არის თვითმმართველობის მსგავსი ტერიტორიების ძიება სურათში და ადინების ტრანსფორმაციის პარამეტრების განსაზღვრა მათთვის (ნახ. 2.5).

სურ. 2.5. თვითნაკეთი გამოსახულების უბნები

უარეს შემთხვევაში, თუ ოპტიმიზაციის ალგორითმი არ გამოიყენება, იგი მოითხოვს სხვადასხვა ზომის ყველა შესაძლო გამოსახულების ფრაგმენტების დათვლას და შედარებას. მცირე ზომის სურათების გათვალისწინებითაც კი, მხედველობაში გვაქვს მიღებული, ვიღებთ ასტრონომიულ რაოდენობას, რომელიც უნდა მოძებნოთ. უფრო მეტიც, გარდაქმნების კლასების მკვეთრი შევიწროებაც, მაგალითად, ამის გამო

მხოლოდ გარკვეული დროის განრიგი არ იწვევს დროში შესამჩნევ მოგებას. გარდა ამისა, დაკარგულია სურათის ხარისხი. Fractal შეკუმშვის სფეროში შესწავლილი უმეტესი ნაწილი ახლა მიზნად ისახავს მაღალი ხარისხის სურათების მისაღებად საჭირო საარქივო დროის შემცირებას.

განმარტებაგადაქცევა w: R 1-\u003e L 2, წარმოდგენილია როგორც სად a, b, c, d, e, f-რეალური რიცხვები და (x y) e y g -მოუწოდა ორ განზომილებიანი affine ტრანსფორმაცია.

განმარტება გადაქცევა შ: L 3 - »D 3, წარმოდგენილი სახით

w (x) \u003d w

სად a, b, c, d, e, f, p, q, r, s, t, u-რეალური რიცხვები და (დს.) z) eR 3ეწოდება სამგანზომილებიანი affine ტრანსფორმაცია.

განმარტება მოდით f: X -\u003e X იყოს ტრანსფორმაცია X სივრცეში.

Წერტილი x f eX,ისეთივე როგორც ვ (x ვ) \u003d x ვ,მოუწოდა ფიქსირებული წერტილი (მიმზიდველი)გარდაქმნები.

განმარტება ტრანსფორმაცია f: X -\u003e X მეტრულ სივრცეში

(X, დ) ეწოდება კომპრესიულითუ არსებობს რიცხვი S: 0 ს< 1 ასეთი

d (f (x), f (y)) V *, yeX.

კომენტარი. ფორმალურად, ჩვენ შეგვიძლია გამოვიყენოთ ნებისმიერი კომპრესიული რუქა fractal შეკუმშვაში, მაგრამ ფაქტობრივად გამოიყენება მხოლოდ სამგანზომილებიანი affine გარდაქმნები, რომლებიც კოეფიციენტებზე საკმარისად ძლიერი შეზღუდვებით არიან.

თეორემა. (შეკუმშვის ტრანსფორმაციის შესახებ.) მოდით f:X -\u003e X - შეკუმშვის გარდაქმნა სრულ მეტრულ სივრცეში (X, დ). შემდეგ არის ზუსტად ერთი ფიქსირებული წერტილი x fე X ამ ტრანსფორმაციისთვის და xeX ნებისმიერი წერტილის თანმიმდევრობა \\ f "(x): n= 0,1,2...} თან ახლავს x ვ.

ამ თეორემის უფრო ზოგადი განცხადება გარანტიას გვაძლევს თანხვედრაში.

განმარტება გამოსახულებაფუნქცია S განისაზღვრება, განისაზღვრება ერთეულის მოედანზე და იღებს მნიშვნელობებს 0-დან 1 ან S– მდე (xo0eVx.\u003e e.

მოდით სამგანზომილებიანი affine ტრანსფორმაცია w: R 3-> რ 3, დაწერილი Y ფორმაში და კომპაქტურ ქვესათაურზე.\u003e. კარტესიანის მოედანი

x (ჩვენ ვიყენებთ სპეციალური ტიპის ტრანსფორმაციის მატრიცას, რომ შემცირდეს განმარტებით დომენის განზომილება რ 3ადრე რ 2).შემდეგ იგი გადაეცემა ზედაპირის ნაწილს სa ფართობზე, რომელიც მდებარეობს ცვლაში (ეჯ)და როტაცია მოცემული მატრიქსით r. უფრო მეტიც, თუ ინტერპრეტაციას უკეთებს ფუნქციის 5 (x :, ^) ე მნიშვნელობებს

შესაბამისი წერტილების სიკაშკაშე, იგი შემცირდება რჯერ (ტრანსფორმაცია უნდა იყოს კომპრესიული) და ცვლაში გადასვლა ქ.

განმარტებასაბოლოო მოსახლეობა უკომპრესიული სამგანზომილებიანი affine გარდაქმნები W ტიდენტიფიცირებულია ტერიტორიებზე დ ტისეთი, რომ w, (Ј\u003e,) \u003d რდა ჯ? .. r \\ Rj \u003d
V / * ჯეწოდება განმეორებითი ფუნქციების სისტემა (IFS).

განუმეორებელი ფუნქციების სისტემა ცალსახად არის დაკავშირებული ფიქსირებულ წერტილ-სურათთან. ამრიგად, შეკუმშვის პროცესი არის სისტემის კოეფიციენტების მოსაძებნად, ხოლო დეკომპრესიული პროცესი არის სისტემის განმეორება, სანამ გამოსახულების სტაბილიზაცია მოხდება (ფიქსირებული წერტილი IFS). პრაქტიკაში, 7-16 გამეორება საკმარისია. ტერიტორიები რ მეშემდგომში მოხსენიებული იქნება რანგითდა ტერიტორიები დ, დომენი(სურათი 2.6).

ალგორითმის შენობა

როგორც ზემოთ უკვე ნათელია, რომ ფრაგმენტული ალგორითმის მიერ შეკუმშვის მთავარი ამოცანაა შესაბამისი აფსიური გარდაქმნების პოვნა. ხშირ შემთხვევაში, ჩვენ შეგვიძლია თარგმნოთ გამოსახულების არეალები ნებისმიერი ზომის და ფორმის, მაგრამ ამ შემთხვევაში ჩვენ ვიღებთ ასტრონომიულ რაოდენობას სხვადასხვა ფრაგმენტებისგან, რომელთა დამუშავებაა, რომელთა დამუშავება შეუძლებელია ამ მომენტში, თუნდაც სუპერკომპიუტერზე.

ატ ალგორითმის სასწავლო ვერსია,ქვემოთ მოცემულია შემდეგი ტერიტორიები:

1. ყველა სფერო არის კვადრატი, რომელზეც გამოსახულების მხარეები პარალელურად მდებარეობს.ეს შეზღუდვა საკმაოდ მკაცრია. სინამდვილეში, ჩვენ ვაპირებთ, რომ მიახლოებით გეომეტრიული ფორმების მთელი სახეობა მივაახლოთ მხოლოდ კვადრატებით.

2. დომენის დონის რანჟირების ზომაზე შემცირებისას, ზუსტად 2 ჯერ(იხ. სურათი 2.6). ეს მნიშვნელოვნად ამარტივებს როგორც კომპრესორს, ასევე დეკომპრესორს, რადგან მცირე ტერიტორიების მასშტაბის დავალება არა ტრივიალურია.

3. დომენის ყველა ბლოკი არის კვადრატი და აქვს ფიქსირებული ზომა.ერთიანი ქსელის მქონე სურათი იყოფა დომენის ბლოკების სიმრავლეზე.

4. დომენის დომენები აღებულია "მეშვეობით წერტილი"მე და Y, რომელიც დაუყოვნებლივ ამცირებს ძიებას 4 ჯერ.

5. დომენის დომენის რუბრიკის როტაციის დროს გადაცემისას შესაძლებელია მხოლოდ O, 90, 180 ან 270 ° ტემპერატურაზე.ნებადართულია სარკეობა. შესაძლო კონვერტაციის საერთო რაოდენობა (ცარიელი ითვლება) არის 8.

6. ხორციელდება სკალირება (შეკუმშვა) ვერტიკალურად (სიკაშკაშე) რამდენჯერმე მითითებული ნომერი -0.75.

ეს შეზღუდვები საშუალებას გაძლევთ: 1. შექმნათ ალგორითმი, რომელიც მოითხოვს შედარებით მცირე რაოდენობის ოპერაციებს, თუნდაც საკმარისად დიდ სურათებზე.

7. ფაილში ჩასაწერად მონაცემების წარდგენა ძალიან კომპაქტურია. ჩვენ გვჭირდება ყოველი ბმულის ტრანსფორმაცია IFS– ში:

♦ ორი რიცხვი დომენის ბლოკის კომპენსაციის დასადგენად. თუ შეყვანის გამოსახულებებს 512x512 შევზღუდავთ, მაშინ თითოეული ნომრის 8 ბიტი საკმარისი იქნება.

♦ სამი ბიტი, რომ მიუთითოთ სიმეტრიის კონვერსია დომენის ბლოკის რანგის გადაცემისას.

9 7-9 ბიტი, რათა თარგმნის დროს შეცვალოთ სიკაშკაშე.

ბლოკის ზომის ინფორმაციის შენახვა შესაძლებელია ფაილის სათაურში. ამრიგად, 4 ბაიტიზე ნაკლები გავატარეთ ერთ ადლაინზე გადაკეთებაზე. ბლოკის ზომიდან გამომდინარე, შეგიძლიათ გამოთვალოთ რამდენი ბლოკი იქნება გამოსახულებაში. ამრიგად, ჩვენ შეგვიძლია მივიღოთ კომპრესიის დონის შეფასება.

მაგალითად, ფაილისთვის grayscale 256 ფერებში 512x512 პიქსელი, რომლის ბლოკის ზომაა 8 პიქსელი, adine გარდაქმნები იქნება 4096 (512 / 8-512 / 8). თითოეულს დასჭირდება 3.5 ბაიტი. ამრიგად, თუ წყაროს ფაილმა დაიკავა 262144 (512-512) ბაიტი (სათაურის გარდა), მაშინ კოეფიციენტებთან ერთად ფაილი დაიკავებს 14336 ბაიტს. შეკუმშვის კოეფიციენტი 18 ჯერ. ამავე დროს, ჩვენ არ გავითვალისწინებთ იმას, რომ კოეფიციენტებთან ერთად ფაილს ასევე შეიძლება ჰქონდეს ზედმეტი და შეკუმშვა დანაკარგების გარეშე, მაგალითად, LZW გამოყენებით.

შემოთავაზებული შეზღუდვების უარყოფითი ასპექტები:

1. რადგან ყველა სფერო არის კვადრატი, შეუძლებელია გამოიყენოთ ობიექტების მსგავსება, რომლებიც კვადრატს ძალიან შორს აქვთ ფორმაში (რომლებიც რეალურ სურათებში საკმაოდ ხშირია.)

2. ანალოგიურად, ჩვენ არ შეგვიძლია გამოვიყენოთ ობიექტების მსგავსება სურათში, მსგავსების კოეფიციენტი, რომელთა შორის ძალიან განსხვავდება ეს ორი.

3. ალგორითმს არ შეუძლია ისარგებლოს სურათში მოცემული ობიექტების მსგავსებით, რომლის კუთხეც არ არის მრავლობითი 90 °.

ეს არის საფასური შეკუმშვის სიჩქარედა ფაილში შეფუთვის კოეფიციენტების შემსუბუქების მიზნით.

შეფუთვის ალგორითმი შემცირდება ყველა დომენის ბლოკის აღრიცხვით და თითოეული შესაბამისი რანგის ბლოკის შერჩევაში. ქვემოთ მოცემულია ამ ალგორითმის დიაგრამა.

(ყველა დიაპაზონის ბლოკისთვის) (

min_distance \u003d მაქსიმალური წინააღმდეგობა;

R ^ j \u003d image-\u003e CopyBlock (i, j);

for (ყველა დომენის ბლოკში) (// ბრუნვით და უარყოფით.

მიმდინარე \u003d KoopflMHaTH ტექნიკური. გარდაქმნები;

D \u003d image-\u003e CopyBlock (მიმდინარე);

current_distance \u003d R_jj.L2distance (D); თუ (ამჟამინდელი_გადადგომა< min_distance) {

// თუ საუკეთესო შანსები უარესია: min_distance \u003d current_distance; საუკეთესო \u003d მიმდინარე; } }

// შემდეგი დომენის ბლოკი Save_Coefficients_to_file (საუკეთესო);

// შემდეგი დიაპაზონის ბლოკი

როგორც ზემოაღნიშნული ალგორითმიდან ჩანს, თითოეული რანგის ბლოკისთვის, ჩვენ ვამოწმებთ მას ყველა შესაძლო დომენის ბლოკთან (მათ შორის, რომლებმაც გაიარეს სიმეტრიული კონვერსია), ჩვენ ვპოულობთ ვარიანტს ყველაზე მცირე ზომით ლ 2(ყველაზე მცირე სტანდარტული გადახრა) და შეინახეთ ამ კონვერტაციის კოეფიციენტები ფაილში. კოეფიციენტებია (1) ნაპოვნი ბლოკის კოორდინატები, (2) რიცხვი 0-დან 7-მდე, რაც ახასიათებს სიმეტრიის ტრანსფორმაციას (როტაცია, ბლოკის ასახვა) და (3) ამ წყვილის ბლოკებისთვის სიკაშკაშის ცვლა. სიკაშკაშის ცვლა გამოითვლება როგორც b for r-, j -წოდების ბლოკის პიქსელის მნიშვნელობები (TO),ა მომაკვდავს- დომენის ბლოკის პიქსელის მნიშვნელობები (დ)უფრო მეტიც, ღონისძიება განიხილება, როგორც

rf (tf, D) \u003d £ ((,,;, + S-0.754,) 2.

ჩვენ არ გამოვთვლით კვადრატულ ფესვს ლ 2ზომები გვაქვს და არ ვყოფთ მას, რადგან ეს ტრანსფორმაციები ერთფეროვანია და ხელს არ შეგშლის ექსტრემის პოვნა, თუმცა თითოეული ბლოკისთვის ჩვენ შეგვიძლია კიდევ ორი \u200b\u200bოპერაციის შესრულება.

ჩვენ გამოვთვლით ჩვენთვის საჭირო ოპერაციების რაოდენობას, რომ კომპრესირება მოახდინოთ გამოსახულების რუხი მასშტაბის 256 ფერებში 512x512 პიქსელებით, ბლოკის ზომით 8 პიქსელი:

ოპერაციების რაოდენობა

4096 (=512/8-512/8)

492032 (=(512/2-8)* (512/2-8)*8)

\u003e 3 * 64 ოპერაცია "+"

> 2*64 ოპერაციები ""

\u003e 3 * 128.983.236.608 ოპერაციები "+"

\u003e 2 * 128.983.236.608 ოპერაციები ""

ამრიგად, ჩვენ შევძელით კომპრესიის ალგორითმის ოპერაციების რაოდენობა, სრულად გამოთვლილ მნიშვნელობებამდე.

გამოსახულების დეკომპრესიის ალგორითმის სქემა

Fractal შეკუმშვის ალგორითმის დეკომპრესია უკიდურესად მარტივია. აუცილებელია ჩატარდეს სამგანზომილებიანი affine გარდაქმნების რამდენიმე გამეორება, რომელთა კოეფიციენტები მიღებულია შეკუმშვის ეტაპზე.

აბსოლუტურად ნებისმიერი სურათი (მაგალითად, აბსოლუტურად შავი) შეიძლება იქნას აღებული, როგორც საწყისი, რადგან შესაბამისი მათემატიკური აპარატურა გვაძლევს გარანტიას IFS- ის განმეორების დროს მიღებული სურათების თანმიმდევრულობის გადახედვაზე ჯერ კიდევ სურათზე (ორიგინალთან ახლოს). ჩვეულებრივ, 16 გამეორება საკმარისია ამისათვის.

წაიკითხეთ ფაილიდან ყველა ბლოკის კოეფიციენტი; შექმენით სასურველი ზომის შავი სურათი; სანამ (სურათი არ გახდება) (

(ყველა დიაპაზონისთვის (R)) (

D \u003d image-\u003e CopyBlock (D_coord_for_R); (ყოველი პიქსელი) }