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

ფრაქტალის ალგორითმი

ფრაქტალური შეკუმშვის ისტორია

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

1981 წელს ჯონ ჰაჩინსონმა გამოაქვეყნა სტატია „ფრაქტალები და თვითმსგავსება“, სადაც წარმოდგენილი იყო ფრაქტალების აგების თეორია Iterated Function System (IFS) გამოყენებით. ოთხი წლის შემდეგ გამოჩნდა მაიკლ ბარნსლისა და სტეფან დემკოს სტატია, რომელიც წარმოადგენდა IFS-ის საკმაოდ თანმიმდევრულ თეორიას. 1987 წელს ბარნსლიმ დააარსა კომპანია Iterated Systems, რომლის ძირითადი საქმიანობაა ახალი ალგორითმებისა და პროგრამული უზრუნველყოფის შექმნა ფრაქტალების გამოყენებით. სულ რაღაც ერთი წლის შემდეგ, 1988 წელს, მან გამოუშვა თავისი მთავარი ნამუშევარი, Fractals Are Everywhere. IFS-ის აღწერის გარდა, მან გამოიღო შედეგი, რომელიც ახლა ცნობილია როგორც კოლაჟის თეორემა, რომელიც ემყარება ფრაქტალური შეკუმშვის იდეის მათემატიკურ საფუძველს.

პირველი სტატია ბარნსლის წარმატებების შესახებ შეკუმშვის სფეროში გამოჩნდა ჟურნალ BYTE-ში 1988 წლის იანვარში. მასში არ იყო აღწერილი, თუ როგორ უნდა გადაწყდეს შებრუნებული პრობლემა, მაგრამ აჩვენა რამდენიმე სურათი შეკუმშული 1:10,000 თანაფარდობით, რაც აბსოლუტურად განსაცვიფრებელი იყო. მაგრამ თითქმის მაშინვე აღინიშნა, რომ მიმზიდველი სახელების მიუხედავად ("ბნელი ტყე", "მონტერეს სანაპირო", "მზესუმზირის ველი") გამოსახულებები სინამდვილეში ხელოვნური ხასიათისა იყო. ამან გამოიწვია მრავალი სკეპტიკური კომენტარი, რაც ბარნსლის განცხადებამ გამოიწვია, რომ "საშუალო გამოსახულება მოითხოვს დაახლოებით 100 საათს მუშაობას მძლავრ ორმაპროცესორიან სამუშაო სადგურზე შეკუმშვისთვის და ადამიანის მონაწილეობით".

ახალი მეთოდისადმი დამოკიდებულება შეიცვალა 1992 წელს, როდესაც არნო ჯეკვინმა, ბარნსლის ერთ-ერთმა თანამშრომელმა, აღწერა პრაქტიკული ალგორითმი და გამოაქვეყნა დისერტაციის დაცვისას. ეს ალგორითმი უკიდურესად ნელი იყო და არ აცხადებდა 10000-ჯერ შეკუმშვას (სრული ფერადი 24-ბიტიანი გამოსახულების შეკუმშვა შეიძლებოდა მნიშვნელოვანი დანაკარგების გარეშე 1:8 - 1:50 თანაფარდობით); მაგრამ მისი უდავო უპირატესობა ის იყო, რომ ადამიანის ჩარევა მთლიანად აღმოიფხვრა. დღეს, ფრაქტალის შეკუმშვის ყველა ცნობილი პროგრამა ეფუძნება ჯეკვინის ალგორითმს. 1993 წელს გამოვიდა Iterated Systems-ის პირველი კომერციული პროდუქტი. მას საკმაოდ ბევრი პუბლიკაცია მიეძღვნა, მაგრამ კომერციულ წარმატებაზე საუბარი არ იყო, პროდუქტი საკმაოდ „უხეში“ იყო, კომპანიას არ გადაუდგა სარეკლამო ნაბიჯები და გაუჭირდა პროგრამის შეძენა.

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

მეთოდის იდეა

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

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

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

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

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

IFS-ის გამოყენებით მიღებული ორი ყველაზე ცნობილი სურათია "სიერპინსკის სამკუთხედი" და "ბარნსლის გვიმრა".

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

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

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

ფრაქტალის შეკუმშვის მათემატიკური საფუძველი

განმარტება.ტრანსფორმაცია w:R 2 –> R 2, წარმოდგენილია როგორც

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

განმარტება.ვთქვათ f:X –> X არის გარდაქმნა X სივრცეში. X-ის კუთვნილი x f წერტილი ისეთი, რომ f(x f)=x f ეწოდება გარდაქმნის ფიქსირებულ წერტილს (მიმზიდველს).

განმარტება.მოდით, f:X–>X მეტრულ სივრცეში (X, d) ეწოდოს შეკუმშვას, თუ არის რიცხვი s: 0<= s < 1, такое, что d(f(x),f(y)) <= s * d(x,y) длялюбых x,y принадлежащих X.

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

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

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

განმარტება.გამოსახულება არის ფუნქცია S, რომელიც განსაზღვრულია ერთეულ კვადრატზე და იღებს მნიშვნელობებს 0-დან 1-მდე ან S(x,y) ეკუთვნის ნებისმიერ x,y-ს.

სამგანზომილებიანი აფინური ტრანსფორმაცია w f:R 3 –> R 3 ჩაიწეროს როგორც

უფრო მეტიც, თუ ჩვენ განვმარტავთ S-ის მნიშვნელობას, როგორც შესაბამისი წერტილების სიკაშკაშეს, ის შემცირდება p-ჯერ (ტრანსფორმაცია უნდა იყოს შეკუმშული) და შეიცვლება q ცვლაში.

განმარტება.შეკუმშვის სამგანზომილებიანი აფინური გარდაქმნების W სასრულ კოლექციას w i განსაზღვრული D i დომენებზე ისე, რომ w i (D i) = R i და R i-ის გადაკვეთა R j-თან არის ცარიელი სიმრავლე, ეწოდება გამეორებადი ფუნქციის სისტემა (IFS).

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

ტიპიური ფრაქტალის შეკუმშვის სქემა

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

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

პირველი სამი პირობა ნიშნავს, რომ რუკის w i იქნება კონტრაქტი. და მეოთხე პირობის გამო, კოდირებული გამოსახულება R და მისი გამოსახულება W(R) ერთმანეთის მსგავსი იქნება. იდეალურად R = W(R). ეს ნიშნავს, რომ გამოსახულება R იქნება ფიქსირებული წერტილი W. სწორედ აქ გამოიყენება გამოსახულების სხვადასხვა ნაწილის მსგავსება. როგორც გაირკვა, თითქმის ყველა რეალური სურათი შეიცავს ნაწილებს, რომლებიც ერთმანეთის მსგავსია, აფინურ ტრანსფორმაციამდე.

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

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

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

განსხვავებები იწყება მაშინ, როდესაც განვიხილავთ ალგორითმების არქივის/არქივისთვის საჭირო დროს. ამრიგად, ფრაქტალის ალგორითმი შეკუმშულია ასობით და ათასობით ჯერ უფრო მეტხანს ვიდრე JPEG. სურათის ამოფუთვა, პირიქით, 5-10-ჯერ უფრო სწრაფად მოხდება. მაშასადამე, თუ გამოსახულება მხოლოდ ერთხელ იქნება შეკუმშული, მაგრამ გადაიცემა ქსელში და მრავალჯერ დეკომპრესირებულია, მაშინ უფრო მომგებიანია ფრაქტალური ალგორითმის გამოყენება.

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

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

ფრაქტალის ალგორითმის მახასიათებლები

შეკუმშვის კოეფიციენტები: 2-2000 (მომხმარებლის განსაზღვრა).

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

Სიმეტრია: 100-100000.

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

უკან

შინაარსამდე

წინ

1992 წლის დეკემბერში, შობის წინ, Microsoft-მა გამოუშვა თავისი ახალი CD, Microsoft Encarta. მას შემდეგ ეს მულტიმედიური ენციკლოპედია, რომელიც შეიცავს ინფორმაციას ცხოველების, ყვავილების, ხეების და თვალწარმტაცი ადგილების შესახებ, არ დაუტოვებია ყველაზე პოპულარული ენციკლოპედიების სიები CD-ზე. Microsoft-ის ბოლო გამოკითხვაში, Encarta-მ კვლავ დაიკავა პირველი ადგილი და აჯობა თავის უახლოეს კონკურენტს, Compton Multimedia Encyclopedia-ს. ამ პოპულარობის მიზეზი მდგომარეობს გამოყენების სიმარტივეში, სტატიების მაღალ ხარისხში და, რაც მთავარია, მასალების დიდ რაოდენობაში. დისკი შეიცავს 7 საათის ხმას, 100 ანიმაციურ ვიდეოს, დაახლოებით 800 მასშტაბირებადი რუკას, ასევე 7000 მაღალი ხარისხის ფოტოს. და ეს ყველაფერი - ერთ დისკზე! შეგახსენებთ, რომ ჩვეულებრივი 650 MB CD შეკუმშვის გარეშე შეიძლება შეიცავდეს ან 56 წუთს მაღალი ხარისხის აუდიოს, ან 1 საათის ვიდეო გარჩევადობით 320x200 გარჩევადობით MPEG-1 ფორმატში, ან 700 სრულ ფერად სურათს 640x480.

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

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

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

ასე რომ, 1991 წელს ასეთი ალგორითმი იქნა ნაპოვნი. გარდა ამისა, მის შემდგომ სტატიებში გამოცხადდა ახალი ტექნოლოგიის მრავალი უნიკალური შესაძლებლობები. ამრიგად, ფრაქტალის არქივატორი საშუალებას გაძლევთ, მაგალითად, გახსნისას, თვითნებურად შეცვალოთ გამოსახულების გარჩევადობა (ზომა) მარცვლოვანი ეფექტის გამოჩენის გარეშე. უფრო მეტიც, ის დეკომპრესირდება ბევრად უფრო სწრაფად, ვიდრე მისი უახლოესი კონკურენტი JPEG და არა მხოლოდ სტატიკური გრაფიკა, არამედ ვიდეოც. მაგალითად, მოცემულია პროგრამა, რომელიც აჩვენებდა ფერად ვიდეო ფილმს 20 კადრი წამში სიხშირით i386/33 MHz პროცესორის მქონე მანქანაზე, ყოველგვარი ტექნიკის მხარდაჭერის გარეშე. JPEG- სგან განსხვავებით, ალგორითმი თავდაპირველად მოიცავს შესაძლებლობას, რომ გააკონტროლოს ზარალის ხარისხი მაქსიმალური ხარისხის დაკარგვით. ზოგადად სურათების შეკუმშვის კოეფიციენტი დაახლოებით იგივეა, რაც JPEG, მაგრამ ზოგიერთ რეალურ სურათზე მიღწეულია 10000 (!) ჯერ შეკუმშვა.

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

ფრაქტალური შეკუმშვის ისტორია

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

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

სულ რაღაც ერთი წლის შემდეგ, 1988 წელს, მან გამოუშვა თავისი მთავარი ნამუშევარი, Fractals Are Everywhere. IFS-ის აღწერის გარდა, მან გამოიღო შედეგი, რომელიც ახლა ცნობილია როგორც კოლაჟის თეორემა, რომელიც ემყარება ფრაქტალური შეკუმშვის იდეის მათემატიკურ საფუძველს.

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

პირველი სტატია ბარნსლის წარმატებების შესახებ შეკუმშვის სფეროში გამოჩნდა Byte Magazine- ში 1988 წლის იანვარში. მასში არ იყო აღწერილი, თუ როგორ უნდა გადაწყდეს შებრუნებული პრობლემა, მაგრამ აჩვენა რამდენიმე სურათი შეკუმშული 1:10,000 თანაფარდობით, რაც აბსოლუტურად განსაცვიფრებელი იყო. მაგრამ თითქმის მაშინვე აღინიშნა, რომ მიმზიდველი სახელების მიუხედავად ("ბნელი ტყე", "მონტერეს სანაპირო", "მზესუმზირის ველი") გამოსახულებები სინამდვილეში ხელოვნური ხასიათისა იყო. ამან გამოიწვია მრავალი სკეპტიკური კომენტარი, რაც ბარნსლის განცხადებამ გამოიწვია, რომ "საშუალო გამოსახულება მოითხოვს დაახლოებით 100 საათს მუშაობას მძლავრ ორმაპროცესორიან სამუშაო სადგურზე შეკუმშვისთვის და ადამიანის მონაწილეობით".

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

იდეა

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

მკაცრად რომ ვთქვათ, IFS არის 3D აფინური ტრანსფორმაციების ნაკრები, რომელიც გარდაქმნის ერთ სურათს მეორეში. წერტილები სამგანზომილებიან სივრცეში (x კოორდინატი, y კოორდინატი, სიკაშკაშე) განიცდის ტრანსფორმაციას.

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

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

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

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

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

დანაკარგების შეფასება და მათი დარეგულირების გზები

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

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

სკალირების პარამეტრები

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

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

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

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

შედარება JPEG-თან

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

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

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

ფრაქტალური გამოსახულების შეკუმშვა.

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

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

მაიკლ ბარნსლი.

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

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

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

ბარნსლის გვიმრა (მარცხნივ) და სიერპინსკის სამკუთხედი(მარჯვნივ).

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

ფრაქტალების გამოყენება მედიცინაში.

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

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

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

კარდიოგრაფიის მაგალითი.

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

რენტგენის მაგალითი.

ფრაქტალის ალგორითმების გამოყენებით დამუშავებული რენტგენის გამოსახულებები იძლევა უკეთეს სურათს და შესაბამისად უკეთ დიაგნოზს!!

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

ელექტროგასტროენტეროგრამის მაგალითი.

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

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

კიბოს და ნორმალური უჯრედის ზედაპირების ადჰეზიური რუქები

ფრაქტალების გამოყენება საბუნებისმეტყველო მეცნიერებებში.

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

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

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

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

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

მყარის მაგალითია კრისტალები.

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

ტურბულენტობა.

ფრაქტალების გამოყენება ტელეკომუნიკაციებში.

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

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

Fractals, როგორც ვიზუალიზაციისა და სპეციალური ეფექტების ელემენტები.

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

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

ლანდშაფტის მოდელირება ფრაქტალის ალგორითმებზე დაყრდნობით Fractal Landscapes პროგრამის გამოყენებით.

თამაშის სკრინშოტი Minecraft.

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

ახლა მოდით შევეხოთ fractal ანიმაციის თემას. სხვადასხვა გენერატორში შექმნილი ფრაგმენტული სურათები ძალიან ლამაზია. რა შეგვიძლია ვთქვათ fractal ანიმაციაზე, ეს ნამდვილად საოცარი სანახაობაა. უპირველეს ყოვლისა, ღირს აღინიშნოს ელექტრო ცხვრის რესურსი. ელექტრო ცხვარი არის რესურსი, რომელიც იყენებს განაწილებულ გამოთვლებს ფრაქტალური ანიმაციის შესაქმნელად, რომელიც დაფუძნებულია ფრაქტალური ფლეიმის ალგორითმზე (შემუშავებული Scot Draves-ის მიერ). მარტივად რომ ვთქვათ, თქვენს კომპიუტერში დაინსტალირებულია პროგრამული უზრუნველყოფა, რომელიც იყენებს თქვენს აპარატს ფრაქტალის ანიმაციის გამოსათვლელად და რენდერისთვის, ამავდროულად ჩამოტვირთავს და გაჩვენებთ დასრულებულ ფრაქტალ ანიმაციას ეგრეთ წოდებული „ცოცხალი“ ფონის სახით. ამავდროულად, იგივე ფონები ინახება კომპიუტერში გარკვეულ საქაღალდეში და მათი ამოღება შესაძლებელია იქიდან და შემდეგ თქვენი მიზნებისთვის გამოყენება, მაგალითად, ვიდეო რედაქტირებისას (თუმცა ვიდეოების სიგრძე ცოტა ხანმოკლეა. - 5 წამი). მაგრამ თქვენ გაქვთ Apophysis პროგრამა და მისთვის Apophymator სკრიპტი, შეგიძლიათ მარტივად შექმნათ თქვენი საკუთარი ანიმაცია (საბედნიეროდ, ამ თემაზე ბევრი გაკვეთილია ინტერნეტში), სანამ გნებავთ, მთავარია, რომ თქვენი მანქანა ძლიერია. საკმარისი.

ელექტრო ცხვრის ანიმაციის ეკრანის ანაბეჭდები:

ფრაქტალის ანიმაციის სპექტაკლი ასევე წარმატებით გამოიყენება VJ-ების მიერ მათ ვიდეო სეტებში. ასეთი ვიდეო ინსტალაციები განსაკუთრებით ხშირად გამოიყენება ელექტრონული მუსიკის შემსრულებლების კონცერტებზე. ამისთვის გამოიყენება ე.წ. VJing პროგრამები (მაგალითად Resolume). ფრაქტალური ანიმაციის ანიმაციის მაგალითები Resolume პროგრამიდან:

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

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

ორიგინალური სტატიის წაკითხვა შეგიძლიათ ჟურნალ Compuart-ის მარტის ნომერში.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ბრინჯი. 1.10. IFS-ის გამოყენებით წარმოქმნილი გვიმრის სურათი

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

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

f: X 1  X 2 თუ ის გარდაქმნის X 1 სივრცეს X 2 სივრცედ.

ტრანსფორმაციას f: X 1  X 2 მეტრულ სივრცეში (X,d) ეწოდება შეკუმშვა, თუ არსებობს მუდმივი ს, 0წმ<1 такая что:

d(f(x 1),f(x2))  sd(x1,x2),

სადაც d(x 1,x 2) არის მანძილი x 1 წერტილიდან x 2 წერტილამდე X სივრცეში.

მუდმივ s-ს ეწოდება შეკუმშვის კოეფიციენტი f.

ბრინჯი. 1.11. შეკუმშვის რუკა R 2 სივრცეში წერტილებისთვის

ნახაზი 1.11 გვიჩვენებს შეკუმშვის რუკების მაგალითს (R 2 ,d 2 ), რომელიც გამოიყენება R 2-ის წერტილების ნაკრებისთვის. აქ ეს ტრანსფორმაცია არაერთხელ იქნა გამოყენებული: ჯერ f(x) გამოითვალა x წერტილისთვის, შემდეგ კი ტრანსფორმაცია f გამოიყენებოდა ტრანსფორმაციის შედეგზე: f(f(x)). ტრანსფორმაციის ასეთ თანმიმდევრულ, განმეორებით გამოყენებას იტერაციები ეწოდება და აღინიშნება როგორც: f on, ე.ი. f(f(…f(x)…)), სადაც f გამოიყენება n-ჯერ.

შეკუმშვის რუკის თეორემა : მოდით f: X 1 X 2 იყოს შეკუმშვის რუკა სრულ მეტრულ სივრცეზე. მაშინ f-ს აქვს ერთი და მხოლოდ ერთი ფიქსირებული წერტილი x f X და X-დან ნებისმიერი x-ისთვის მიმდევრობა (f on (x):n=1,2,…) კონვერგირდება x f-ზე. ეს თეორემა საფუძვლად უდევს ფრაქტალური გამოსახულების შეკუმშვის ყველა მიდგომას.

მოდით (w 1 , w 2 ,…,w n ) იყოს შეკუმშვის გამოსახულებების სასრული ნაკრები სივრცეში (X,d) შეკუმშვის კოეფიციენტებით s 1 ,s 2 ,…,s n , 0s<1. Определим отображение W, воздействующее на компактные множества точек B из Х:

W(B)=w 1 (B) w 2 (B)… w n (B)=U N n=1 (B) (1.21)

ამრიგად, W ასრულებს რუკებს მოცემულ სივრცეში შეკუმშვის კოეფიციენტებიდან s, სადაც s=max(s 1,s 2,…,s n).

განმეორებითი ფუნქციის სისტემა (IFS) შედგება სრული მეტრული სივრცისგან (X,d) და შეკუმშვის გამოსახულებების სასრული ნაკრებისაგან w n: XX შეკუმშვის კოეფიციენტებით s n . ამრიგად, IFS შეიძლება აღვნიშნოთ შემდეგნაირად: (X,w n:n=1,2,..,N), ან თუ გავითვალისწინებთ წერტილების სივრცეს R 2-ში, მაშინ უბრალოდ (w n).

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

იყოს ორობითი გამოსახულება LR 2 და იყოს შეკუმშვის გამოსახულებები ისეთი, რომ: U N n =1 w n (L)

საფარი L თითქმის ზუსტად. ჩვენ შეგვიძლია მივიჩნიოთ ასეთი w n (L) L-ის შემცირებულ ასლად. შემდეგ კოლაჟის თეორემა ამბობს, რომ მიმზიდველი A (IFS მიმზიდველი არის გამოსახულება, რომელიც არის IFS-ის ერთადერთი ფიქსირებული წერტილი) სისტემის (w n) ახლოს არის L-თან. "კოლაჟი" არის რეგიონების ნაკრები wn(L) .

ვინაიდან მიმზიდველი A არის უსასრულო რაოდენობის IFS გამეორების შედეგი, ის არსებითად ფრაქტალია.

ბრინჯი. 1.12. კოლაჟის თეორემის ილუსტრაცია.

(ა) ორიგინალური სურათი და გამოსახულების ოთხი ფრაგმენტი;

ბ) მიმზიდველი გამოსახულება

კოლაჟის თეორემის პრაქტიკაში გამოსაყენებლად აუცილებელია ავირჩიოთ ტრანსფორმაციები, რომლებიც იქნება კომპრესიული რუკები. ერთ-ერთი ასეთი ტრანსფორმაციაა აფინური ტრანსფორმაციები: T: R 2 R 2:

(1.23)

სადაც a, b, c, d, e, f R. აფინურ ტრანსფორმაციებს შეუძლიათ შეასრულონ ბრუნვა, ტრანსლაცია და მასშტაბირება.

ნ ნახაზი 1.13 გვიჩვენებს აფინური ტრანსფორმაციის მოქმედებას R2-ის წერტილების სიმრავლეზე.

ბრინჯი. 1.13. აფინური ტრანსფორმაციის ზემოქმედება წერტილებზე R 2 სივრცეში

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

არსებობს ორი ალგორითმი მიმზიდველი გამოსახულების შესაქმნელად IFS-ის გამოყენებით. ერთი მათგანი არის შეკუმშვის რუკის თეორემის პირდაპირი გამოყენება, მეორე კი ეგრეთ წოდებული „ქაოსის თამაშის“ გამოყენება.

დეტერმინისტული ალგორითმი გამოსახულების ასაგებად, რომელიც არის IFS მიმზიდველი ნებისმიერი საწყისი სურათისთვის ბიყენებს შეკუმშვის რუკების თეორემას. ალგორითმი აყალიბებს A n გამოსახულების თანმიმდევრობას W=(w 1 ,w 2 ,…,w n ) IFS რუკების განმეორებით გამოყენებით:

A n =W (B) (1.24)

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

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

ბრინჯი. 1.14. დეტერმინისტული ალგორითმი გამოიყენება გვიმრის IFS-ზე.

სურათის ნახვა A n შემდეგ: ა) 2, ბ) 3, გ) 10, დ) 30 გამეორება.

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

ბრინჯი. 1.15. დომენის ბლოკების რუკტირება რანჟირების ბლოკებზე

ფრაქტალური გამოსახულების შეკუმშვით

ფრაქტალური გამოსახულების კოდირების ძირითადი ალგორითმი შესრულებულია შემდეგნაირად (სურათი 1.15):

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

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

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

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

ასეთი ალგორითმის ბლოკ-სქემა წარმოდგენილია ნახ.1.16.

ამჟამად ცნობილია ასეთი ალგორითმის შემდეგი სახეობები.

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

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

ტიპი 1:
,

ტიპი 2:
,

ტიპი 3:
.

ცხადია, რომ ნებისმიერი ბლოკი, შესაბამისი აფინური ტრანსფორმაციის გამოყენებით კვადრატიდან კვადრატამდე, შეიძლება შემცირდეს ერთ-ერთი მითითებული ტიპის შესაბამის ფორმამდე. მას შემდეგ რაც დავაფიქსირეთ სამი ძირითადი კლასი, ბლოკები კლასიფიცირდება მათი დისპერსიის მიხედვით. ამრიგად, 24 ქვეკლასე ჩნდება სამ კლასში თითოეულში, სულ 72 კლასისთვის. R- ბლოკთან ახლოს D- ბლოკის ძებნა ხორციელდება შესაბამისი კლასის დათვლებით.

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

GA– ს გამოყენებისას ოპტიმალური გადაწყვეტილებების მოსაძებნად, თითოეული ელემენტი x ოპტიმიზაციის სივრცის x უნდა იყოს წარმოდგენილი, როგორც ვექტორი ბორობითი ანბანის n სიმბოლოები a = (0,1), სადაც b = a n. ასევე აუცილებელია, რომ ოპტიმიზაციის სივრცე X შედგება ელემენტების საბოლოო რაოდენობისგან.

პოპულაცია P = (χ 1, χ 2,…, χM) ზომის M ითვლება სივრცის ვექტორად B M, რომლის კოორდინატებს უწოდებენ ამ პოპულაციის ინდივიდების გენოტიპებს.

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

GA- ს დასადგენად, თქვენ უნდა მიუთითოთ კროსვორდის ოპერატორი ჯვარი:ბ ბ
ბ B და მუტაციის ოპერატორი მუტ:ბ
ბ .

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

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

ბრინჯი. 1.16. ფრაქტალური გამოსახულების კოდირების ძირითადი საფეხურების ბლოკ-სქემა

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

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

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

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

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

სადაც ქვედა ნაწილში ჯამის ნიშნის ქვეშ არის ევკლიდური მანძილი თავდაპირველ და ტრანსფორმირებულ ბლოკებს შორის. ეს ფუნქცია აკმაყოფილებს GA-ს მოთხოვნებს (არაუარყოფითი) და ადეკვატურია რულეტის შერჩევის ოპერატორისთვის, რომელშიც თითოეული ინდივიდუალური
პოპულაციები  ტმომავალი ინდივიდის ჩამოყალიბებისას მშობელი აღმოჩნდება
პოპულაციები  t+1ალბათობით

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

ამ ალგორითმის მუტაციის ოპერატორი სტანდარტულია და გადაკვეთის ოპერატორი შეცვლილია შემდეგნაირად:

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

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

ალგორითმი 1.

ალგორითმი 2.

გამოსახულების აღდგენის ალგორითმი:

იქმნება ორი ერთი და იგივე ზომის A და B სურათი. სურათების ზომა შეიძლება არ იყოს ორიგინალური სურათის ზომის ტოლი. A და B უბნების თავდაპირველ ნახატს მნიშვნელობა არ აქვს. ეს შეიძლება იყოს შემთხვევითი მონაცემები.

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

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

პროცედურები 2 და 3 მეორდება მანამ, სანამ A და B გამოსახულებები გაურკვეველი გახდება.

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

Fractal მეთოდის უპირატესობებში შედის:

შეკუმშვის მაღალი კოეფიციენტები.

საპირისპირო კონვერტაციის მაღალი სიჩქარე.

გამოსახულების შემდგომი სტრუქტურული ანალიზის შესაძლებლობა.

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

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

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

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

ამჟამად, სურათის შეკუმშვის საკმაოდ ბევრი ალგორითმია. მონაცემთა შეკუმშვის ნებისმიერი მეთოდის საფუძველია წყაროს ინფორმაციის ბუნებრივი სიჭარბის გამოყენება. გამოსახულების შეკუმშვა ხორციელდება გამოსახულების სივრცულ ან სიხშირის დომენებში. სივრცითი გამოსახულების შეკუმშვის ყველაზე ნათელი მაგალითებია PCX და GIF ალგორითმები, ხოლო სიხშირის შეკუმშვის ალგორითმები არის JPEG.

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

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

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

ყველაზე მნიშვნელოვანი სიხშირის კოეფიციენტების შერჩევა.

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

რამდენი დრო სჭირდება რეგისტრირებულ წერილს?

როგორ შეავსოთ თქვენი ბილაინის ანგარიში MTS-ით?

რა უნდა გააკეთოს, თუ დანამატი არ იტვირთება Google Chrome-ში მოდული არ იხსნება

გასაღებები მძღოლის გამაძლიერებლისთვის 4