İtkili sıxılma alqoritmlərinin nəzərdən keçirilməsi. Fraktal alqoritmlərin praktiki tətbiqi Fraktal metoddan istifadə etməklə təsvirin sıxılmasının qiymətləndirilməsi

Bununla belə, bəlkə də bu istiqamətdə işin kommersiya komponenti və nəticədə nəzərdən keçirilən alqoritmlərin qənaətbəxş təsvirlərinin olmaması səbəbindən təklif olunan dəyişikliklər ağlabatan nəticədən daha çox intuitiv və kortəbii improvizasiyaların nəticəsi kimi qəbul edilir. müəyyən bir sıra hesablama təcrübələri. Eyni zamanda, bu sahədə fəaliyyətə başlayan hər bir tədqiqatçı əsas alqoritmlərin hərtərəfli müqayisəli təhlilinə ehtiyac duyur.

Məqsədlər və məqsədlər

İşin məqsədi əsas alqoritmlərin müqayisəli təhlilini aparmaq, domen bloklarının seçilməsi xüsusiyyətlərini qurmaq və sıxılma səmərəliliyini artırmaq üçün onların yaxınlaşması üçün sınaq üsullarını qurmaqdır. Bu məqsədə domen bloklarının seçilməsi üsullarında və yaxınlaşma üsullarında dəyişikliklər vasitəsilə nail olunur.

İşin ideyası kodlaşdırma səmərəliliyini artırmaq üçün domen bloklarının seçilməsi üsullarının yeni modifikasiyalarını və onların dərəcə bloklarına yaxınlaşma üsullarını hazırlamaqdır.

Bu məqsədə çatmaq üçün magistr dissertasiyasında aşağıdakı vəzifələr qarşıya qoyulmuş və həll edilmişdir:

Ədəbiyyat mənbələrinin öyrənilməsi və itkili təsvirin sıxılma alqoritmlərinin nəzəri təhlilinin aparılması.
Fraktal təsvirlərin sıxılma alqoritmlərinin əməliyyat xüsusiyyətlərinin qurulması, onları həyata keçirən proqram təminatının hazırlanması.
Şəkillər toplusunun yaradılması, domen bloklarının seçilməsi və onların yaxınlaşmasının xüsusiyyətlərini müəyyən etmək üçün hesablama təcrübələrinin aparılması, nəticələrin müqayisəli təhlili, nəticənin çıxarılması.
Alqoritmin ayrı-ayrı mərhələlərinin modifikasiyası, onun yeni variantının formalaşdırılması.
Müvafiq proqram komponentlərinin hazırlanması, təcrübələrin aparılması, işin müqayisəli nəticələri.

Tədqiqatın mövzusu itkili görüntü sıxılma alqoritmləridir.

Tədqiqatın obyekti təsvirin sıxılması üçün fraktal alqoritmlərdir.

Tədqiqat metodlarına hesablama təcrübələrinin aparılması, nəticələrin müqayisəli təhlili, ədədi üsullar, riyazi yaxınlaşma üsulları, obyekt yönümlü proqramlaşdırma daxildir.

İddia edilən elmi yenilik

İşdə artıq aparılan və planlaşdırılan tədqiqatın elmi yeniliyi aşağıdakı kimi qəbul edilir:

Əsas fraktal sıxılma alqoritmlərini həyata keçirən və müqayisəli təhlil etməyə imkan verən proqram təminatı hazırlanmışdır.
Hesablama təcrübələri aparılıb, müqayisəli təhlil aparılıb, əsas alqoritmlərdə domen bloklarının seçilməsi xüsusiyyətləri müəyyən edilib.
Qeyri-xətti təsvir blokunun xəritələşdirilməsi modellərinin tətbiqinin təhlili.
Sıxılma səmərəliliyinin artırılmasına yönəlmiş alqoritmin yeni modifikasiyaları təklif olunur.

İş nəticələrinin təsviri

Tədqiqatların təsviri

Hazırkı mərhələdə fraktal təsvirin sıxılması üçün iki alqoritm - ədəbiyyatda yaxşı təsvir olunan əsas və FE alqoritmi üzərində tədqiqat aparılmışdır. Onları əsas olanlardan hesab etmək olar.

Əsas alqoritm şərti olaraq aşağıdakı mərhələləri əhatə edir.

Addım 1. f şəklində bir çox domen blokları müəyyən edilmişdir. Onlar üst-üstə düşə bilər və üst-üstə düşmənin miqdarı xüsusi təmin edilmiş parametrlə müəyyən edilir.

Addım 2. Şəkil üst-üstə düşməyən dərəcə bloklarına bölünür (R k). Onlar eyni ölçüdə olmaya bilər, çünki... dəyişən blok ölçüləri ilə dörd ağac metodundan istifadə edərək uyğunlaşan bölmələrdən istifadə olunur. Bu, təsvirin kiçik detalları olan hissələrini kiçik ölçülü dərəcə blokları ilə sıx doldurmağa imkan verir.

Addım 3. Hər bir sıralama bloku üçün domen blokları sıralanır. Bu halda, domenlərin oriyentasiyasında dəyişiklik təmin edilir (3 fırlanma variantı, əks olunan 2 fırlanma variantı, 2 əksetmə variantı və 8-ci seçim - dəyişmədən orijinal oriyentasiya). Hər bir oriyentasiya seçimi üçün domen sıralama blokunun ölçüsünə sıxılır və a ij və b ij çevrilmə əmsallarının optimal dəyərləri hesablanır.

ən kiçik kvadratlar üsulu və düsturu

transformasiya olunmuş sıxılmış i-ci domen blokunun w ij (D" ij) onun j-ci oriyentasiyasında R k dərəcə blokuna uyğunluğunu xarakterizə edən parametrin L(R k, D" ij) normallaşdırılmış qiymətini hesablayın. Burada r xy ∈ R k, d xy ∈ D" ij, D" ij sıralama blokunun ölçüsünə sıxılmış j-ci oriyentasiyada i-ci domen blokudur, N R k reytinqdəki piksellərin sayıdır. blok. Bu addımda alqoritm istifadəçi tərəfindən seçilən iki rejimdən birində işləyir: ən yaxşı domen axtaran və axtarmadan. Ən yaxşı domen üçün axtarış rejimində bütün domenlər hər dərəcə üçün çeşidlənir və i-ci domen və onun j-ci istiqaməti seçilir, L kij dəyəri bütün digərləri arasında minimaldır. Ən yaxşı domeni axtarmadan rejimdə domenlərin tam axtarışı i -ci domen və onun j -ci istiqaməti aşkar edilən kimi dayandırılır ki, onun L kij dəyəri müəyyən edilmiş icazə verilən xətanı keçməsin (məsələn, L kij ≤ 0,05). Hər iki rejimdə, bütün domen bloklarında axtarış etdikdən sonra L kij dəyərləri göstərilən icazə verilən xətanın dəyərindən çox olmayan heç kim tapılmadısa, o zaman sözügedən rütbə blokunun aşağıda olub-olmadığını yoxlamaq üçün yoxlama aparılır. dərəcə bölgüsünün icazə verilən maksimum səviyyəsi. Əgər belə deyilsə, onda bu sıralama bloku daha kiçik bloklara bölünür və alqoritmin bu addımı onlar üçün həyata keçirilir. Əgər belədirsə, onda bütün domenlərdən L kij dəyərinin digərləri arasında minimal olduğu domeni və onun oriyentasiya variantı D ij seçin və sözügedən rütbə blokunun bu domen tərəfindən əhatə olunduğunu hesab edin.

3-cü addım ən çox hesablama tələb edir, çünki hər bir sıra bloku üçün R k üçün alqoritm bütün (və ya bir çox, iş rejimindən asılı olaraq) domen blokları və onların oriyentasiya seçimləri vasitəsilə təkrarlanır, hər birində oriyentasiyanı dəyişdirmək və dəyişdirmək üçün çoxlu kompüter vaxtı tələb edən piksel-piksel əməliyyatları yerinə yetirir. çevrilmə əmsallarını tapın. Yaxşı sıxılma, dərəcə bloklarını dərindən bölməyə ehtiyac olmadan domen və dərəcə blokları arasında yaxşı uyğunluq tapmaq qabiliyyətindən asılıdır. Həddindən artıq dərin rütbə bölgüsü həddən artıq çox dərəcə ilə nəticələnir ki, bu da sıxılma nisbətini pisləşdirir, kifayət qədər dərin olmayan dərəcə bölməsi isə kodlanmış təsvirin keyfiyyətsizliyinə səbəb olur.

FE alqoritmi. Əsas alqoritmdə dərəcələrin domenlərlə müqayisəsi əhəmiyyətli hesablama resursları tələb edir. Onları azaltmaq üçün FE alqoritmi (İngiliscə Feature Extraction - xüsusiyyətləri vurğulamaqdan) domen və dərəcə bloklarını təsvir edən beş xüsusiyyəti müəyyən edir. Və ilkin olaraq, hesablamaların miqdarını əhəmiyyətli dərəcədə azaldan onların müqayisəsi aparılır. Bu xüsusiyyətlər aşağıdakılardır:

standart sapma;
asimmetriya;
piksellərarası kontrast;
piksel dəyərləri ilə mərkəzi pikselin dəyəri arasındakı fərqi xarakterizə edən beta əmsalı;
maksimum gradient—üfüqi və şaquli qradiyentlərin maksimumu.

Alqoritmin özü aşağıdakı mərhələləri əhatə edir.

Addım 1. Əsas alqoritmin 1-ci addımına bənzəyir.

Addım 2. Əsas alqoritmin 2-ci addımını tamamlayaraq, xarakterik vektorun dəyərləri hesablanır və hər bir domen bloku üçün saxlanılır.

Addım 3. Reytinq blokunu emal edərkən əvvəlcə onun xarakteristikalar vektorunu hesablayın, sonra düsturdan istifadə edərək verilmiş dərəcənin xarakteristikası vektoru ilə hər bir sahənin xarakteristikası vektoru arasındakı məsafələri hesablayın.

burada f j R və f j D müvafiq olaraq dərəcə və domen bloklarının j-ci xarakteristikalarıdır. Sonrakı tam müqayisə üçün xarakterik vektorlar arasındakı məsafələrin minimal dəyərləri ilə yalnız müəyyən edilmiş q faizi (məsələn, q = 2%) seçilir. Sonrakı hərəkətlər əsas alqoritmin 3-cü addımında yerinə yetirilənlərə bənzəyir, lakin fərqlə ki, domenləri sadalayarkən yalnız seçilmiş q% nəzərə alınır və onlardan ən yaxşısı seçilir.

Qeyd edək ki, domenlərin seçilməsi üçün bu prosedur seçiləcək domenlərin sayını əhəmiyyətli dərəcədə məhdudlaşdıran bir növ filtrdir.

Hazırlanmış proqram təminatının təsviri

Tədqiqatın aparılması üçün Microsoft .NET Framework 2.0 texnologiyası və Visual Studio 2005/2008 alət qabığından istifadə etməklə C# dilində xüsusi proqram təminatı hazırlanmışdır. O, rastr şəkillərini fraktallara kodlamağa və yuxarıda müzakirə olunan alqoritmlərdən istifadə edərək deşifrə etməyə imkan verir. İstifadəçi kodlaşdırılmış şəkillərin keyfiyyətinə nəzarət edən kodlaşdırma parametrlərini təyin edə bilər. Bundan əlavə, proqrama aşağıdakı analiz alətləri daxildir:

domenlərin və rütbələrin strukturunun həm xassələrinin dəyərləri ilə cədvəl şəklində, həm də vizual olaraq görüntüdə göstərilməsi;
orijinal və kodlaşdırılmış görüntü arasında orta piksel xətasının hesablanması;
kodlaşdırmada işlənmiş və istifadə olunan dərəcələrin və domenlərin sayının hesablanması;
kodlaşdırma və dekodlaşdırma vaxtının müəyyən edilməsi;
kodlanmış təsvirdə sıralama bloklarının şəbəkəsinin göstərilməsi;
müxtəlif fraktal sıxılma alqoritmlərindən istifadə edərək təsvirin kodlaşdırılması nəticələrinin avtomatlaşdırılmış təhlili.

Hazırlanmış proqram təminatının UML diaqramı aşağıda təqdim olunur (Şəkil 1):

Şəkil 1 - hazırlanmış proqram təminatının UML diaqramı

Şəkil 2 — Hazırlanmış proqram təminatının ekran formaları

Təcrübələr, nəticələr və nəticələr

Hazırlanmış proqram təminatından istifadə edərək, Şəkil 3-də təqdim olunan 256×256 piksel ölçülü təsadüfi seçilmiş təsvirdən istifadə etməklə bir sıra təcrübələr aparılmışdır. İlkin məlumatlar, parametrlər və eksperimental nəticələr Cədvəl 1-də göstərilmişdir. Şəkil 4-də deşifrə edilmiş nəzərdən keçirilən alqoritmlər tərəfindən əvvəlcədən kodlaşdırılmış görüntü.

Şəkil 3 - Orijinal şəkil

Şəkil 4 — Əsas (a) və FE- (b) fraktal təsvirin sıxılma alqoritmləri ilə kodlanmış təsvirin dekodlanmasının səkkiz təkrarının vizuallaşdırılması. Animasiya kadrlar arasında 50 ms gecikmə ilə 9 kadrdan ibarətdir; təkrar oynatmadan əvvəl gecikmə 400 ms-dir; oxutma dövrlərinin sayı 10 ilə məhdudlaşır.

Təcrübələrdə hər iki alqoritmdə kodlaşdırma vaxtı məhdud deyildi. Hər bir sonrakı təcrübə əvvəlkindən kodlanmış görüntünün keyfiyyətini təyin edən daha yüksək parametr dəyərləri ilə fərqlənir. Alqoritmlərin təsvirində məqsədi ətraflı açıqlanmayan bu parametrlərdən bəzilərini təsvir edək. Domen bölməsinin ilkin və maksimum səviyyələri, həmçinin domen sürüşmə əmsalı onların sayını, ölçüsünü və yerini tənzimləyir. Sürüşmə əmsalı qonşu domenlərin nə qədər üst-üstə düşdüyünü müəyyən edir (beləliklə, minimum 0 dəyəri ilə onlar heç bir şəkildə üst-üstə düşmür və maksimum dəyər 1 ilə üst-üstə düşür ki, tam olaraq bir piksel genişlikdə sahə tıxanmamış qalır). Domenlərin sayı yalnız bu parametrlərdən asılıdır. Rütbələrin bölünməsinin ilkin səviyyəsi onların ilkin minimum sayını və maksimum mümkün ölçüsünü, bölünmənin maksimum səviyyəsi isə onların maksimum icazə verilən sayını və minimum mümkün ölçüsünü müəyyən edir. Bu səviyyələr dörd ağac metodundan istifadə edərək rütbə bölgüsü səviyyələridir. Kodlaşdırmanın sonunda dərəcələrin sayı yalnız bu parametrlərdən deyil, həm də icazə verilən səhvdən asılıdır (alqoritmlərin təsvirinə baxın). Orta piksel xətası deşifrə edilmiş təsvirin orijinal təsvirdən nə qədər fərqləndiyini və düsturla müəyyən edildiyini göstərir.

burada p x,y, p" x,y orijinal və şifrəsi açılmış şəkillərin (x, y) nöqtəsindəki piksel dəyəridir, müvafiq olaraq I W, I H təsvirin eni və hündürlüyü (piksellə), N I-dir. Şəkildəki piksellərin sayı.

Qeyd edək ki, domenlərin sayını təyin edən parametrlər kodlaşdırma vaxtına və deşifrə olunmuş təsvirin keyfiyyətinə birbaşa təsir edir və sıxılma nisbətində əks olunmur. Sıraların sayını və ölçüsünü tənzimləyən parametrlər həm kodlaşdırma və dekodlaşdırma vaxtına, həm də deşifrə olunmuş təsvirin keyfiyyətinə təsir göstərir. Və dərəcələrin sayı sıxılma nisbətini unikal şəkildə müəyyənləşdirir.

Cədvəl 1 - Eksperimental nəticələr

Seçimlər	Təcrübə №
Seçimlər
FE alqoritmi
Domenlərin sayı
başlanğıc səviyyəli ev
maks. səviyyəli ev.
Kof. domen sürüşməsi
Rütbələrin sayı
Başlanğıc rütbə bölgüsü səviyyəsi

İcazə verilən daldırma
Ən yaxşı domeni axtarın
Çərşənbə. pix. xəta, %
Sıxılma nisbəti
Kodlaşdırma vaxtı, (s)
Deşifrə vaxtı, (s)
Əsas alqoritm
Domenlərin sayı
başlanğıc səviyyəli ev
maks. səviyyəli ev.
evin sürüşmə əmsalı
Rütbələrin sayı
Başlanğıc rütbə bölgüsü səviyyəsi
Maks. rütbə bölgüsü səviyyəsi
İcazə verilən daldırma
Ən yaxşı domeni axtarın
Çərşənbə. pix. xəta, %
Sıxılma nisbəti
Kodlaşdırma vaxtı, (s)
Deşifrə vaxtı, (s)

Əldə edilən nəticələr bizə aşağıdakı nəticələr çıxarmağa imkan verir:

FE alqoritmi, əsas alqoritmlə müqayisədə, eyni alqoritm parametrləri ilə şəkilləri onlarla dəfə az vaxtda sıxmağa imkan verir.
Alqoritmlərin orta piksel səhvləri fərqlidir. Parametrlərdən asılı olaraq fərq 5-16% aralığındadır.
Əsas alqoritmlə kodlaşdırma nəticəsində bütün hallarda orta hesabla 30-40% daha yüksək sıxılma əmsalı əldə edilir.
FE alqoritmindən istifadə edərkən şifrələnmiş təsvirin vizual keyfiyyəti nəzərəçarpacaq dərəcədə yaxşılaşır.
Bütün eksperimentlərdə əsas alqoritmdən istifadə edərkən, müxtəlif kodlaşdırma parametrləri altında kodlanmış təsvirin deşifrə müddəti daha az olur.

Onlardan bəziləri olduqca açıqdır. Həqiqətən, FE alqoritmində təsvir bloklarını müqayisə etmək əvəzinə, onların xarakterik vektorları müqayisə edilir ki, bu da təbii olaraq performansa təsir göstərir. Piksel xətaları və sıxılma nisbətlərindəki fərq, çox güman ki, FE alqoritmindən istifadə edərkən kodlaşdırmanın daha çox sayda kiçik ölçülü sıralarla nəticələnməsi ilə izah olunur ki, bu da daha yüksək təsvir detalını, yəni daha yaxşı vizual keyfiyyəti təmin edir. Bu nəticələr hər iki alqoritm tərəfindən dərəcələr şəbəkəsi ilə kodlanmış təsviri göstərən Şəkil 6 ilə təsdiqlənir. Qeyd etmək lazımdır ki, əsas alqoritm 5-16% daha pis təsvir keyfiyyəti yaratsa da, 30-40% daha yüksək sıxılma nisbətinə nail olur.

Güman etmək olar ki, müəyyən edilmiş fərqlərin səbəbi, FE alqoritmində, xüsusiyyətlərinin dəyərlərinə görə seçilmiş domenlərdə axtarış apararkən, sıralama blokuna uyğunluğun qəbul edilən məqbul səhvini təmin edən heç kimin olmamasıdır. bunun nəticəsində sıralama bloku blokun ölçüsünə görə daha kiçiklərə bölünür. Eyni zamanda, eyni rütbələr üçün əsas alqoritmlə kodlaşdırma zamanı belə domenlərin tapılması tamamilə mümkündür.

Bu fərziyyəni yoxlamaq üçün domen seçərkən hər iki alqoritmdə uyğunluqların sayını hesablamağa imkan verən əlavə proqram modulu hazırlanmışdır, yəni. hər iki alqoritmdə eyni domen eyni dərəcə üçün seçildikdə. Şəkil eyni qaldı. Kodlaşdırma parametrləri Cədvəl 1-in dördüncü təcrübəsində istifadə edilənlərə uyğundur, yeganə fərq əsas alqoritmin ən yaxşı domen axtarış rejimində işləməsidir. Bu o deməkdir ki, hər bir rütbə blokunu emal edərkən, icazə verilən xətaya çatdıqda dayanmadan bütün domen blokları axtarılır və həqiqətən ən yaxşısı seçilir. Bu, fikrimizcə, düzgün müqayisə aparmağa imkan verir.

Təcrübələr nəticəsində məlum olub ki, sıralama bloklarının 99,73%-i üçün FE alqoritmi digər domenləri seçib, yəni. - ən yaxşısı deyil. Beləliklə, ən azı bu təsvir üçün FE alqoritmində qəbul edilmiş domen seçimi prosedurunun müqayisə edilən blokların yaxınlığını tam əks etdirmədiyini iddia etmək olar.

Nəticə

Aparılan tədqiqat və təcrübələr nəticəsində aşağıdakı mülahizələr ortaya çıxır.

1. Ağlabatan görünür ki, sıxılmanın səmərəliliyi böyük ölçüdə mənbə şəklinin ilkin bölünməsindən asılıdır. Həqiqətən, uğurlu domenin daxil edilməməsi və ya onun səhvən silinməsi həm sıxılma nisbətinə, həm də dekodlaşdırma keyfiyyətinə təsir göstərir. Apriori olaraq, qonşu yaxın piksellər arasındakı fərqin təsadüfi seçilmiş bölgələrə nisbətən daha az diqqəti cəlb etməsi inandırıcı görünür. Bu səbəbdən, ilkin formalaşmış dəstdə saçaqlı domenlərin daxil edilməsi perspektivli görünür.

2. Hesablamanın həcmini əhəmiyyətli dərəcədə azaltmaq üçün sadələşdirilmiş meyarlar toplusunun tətbiqi ideyası cəlbedicidir, lakin əksər hallarda domenlərin dərəcələrlə müqayisəsi zamanı bu dəst optimal domeni müəyyən etməyə imkan vermir. Yəni bu dəst əsas meyara tam adekvat deyil. Buna görə də, bu dəst əvəzinə əsas meyardan istifadə etmək məqsədəuyğun görünür, lakin onu sözügedən domen dərəcə cütlərinin azaldılmış nüsxələrinə tətbiq edin.

3. Fraktal sıxılma üsullarının nəzəri əsaslarından birbaşa irəli gələn bir mülahizə də yaranır. Beləliklə, kollaj teoremindən belə nəticə çıxır ki, sıxılma xəritələri sisteminin atraktoru ilə orijinal təsvir arasındakı fərqin dərəcəsi ən azı yaradılan xəritələrin keyfiyyət xüsusiyyətləri ilə müəyyən edilir. Əsas alqoritmlərdə istifadə olunan ən sadə, kobud, xətti modellərdən daha mürəkkəb - qeyri-xətti modellərə keçərkən onların artmasını gözləmək təbiidir. Bu baxımdan, bu cür modellərdən istifadə etmək cəhdi aktual görünür.

İşin praktik əhəmiyyəti və müəllifin şəxsi töhfəsi iki əsas alqoritmi həyata keçirən və hər hansı bir təsvir üzərində həyata keçirilən alqoritmlərin işinin avtomatlaşdırılmış müqayisəli təhlilinə imkan verən hazırlanmış proqram təminatındadır. İrəli sürülən tapıntılar və təkliflər əsasında alqoritmin yeni modifikasiyalarının proqram təminatının tətbiqi işlənmə mərhələsindədir.

İşin ayrı-ayrı mərhələlərinin əsas müddəaları gənc alim və tələbələrin “İnformatika və kompüter texnologiyaları” III beynəlxalq elmi-texniki konfransında (Donetsk, DonNTU, 2007), tələbələrin, aspirantların və gənclərin IV beynəlxalq elmi konfransında təqdim edilmişdir. alimlər "Kompüter monitorinqi və informasiya texnologiyaları" (Donetsk, DonNTU, 2008).

Lifeng Xi, Liangbin Zhang. Təkmilləşdirilmiş genetik alqoritmə əsaslanan fraktal təsvirin sıxılmasının tədqiqi. Beynəlxalq Qeyri-xətti Elm Jurnalı. Cild 3, №. 2, 2007, səh. 116-124

M. Hassaballah, M.M. Makky, Youssef B. Mehdy. Sürətli Fraktal Şəklin Sıxılma Metoduna əsaslanan Entropiya. Kompüter Görmə və Təsvir Analizi üzrə Elektron Məktublar 5(1), 2005, səh. 30-40

P. M. Kronover. Dinamik sistemlərdə fraktallar və xaos. Nəzəriyyənin əsasları. - M.: Postmarket, 2000

Barnsley, Michael F., Sloan, Alan D., Iterated Systems, Inc. Təkrarlanan funksiya sistemi ilə təsvirin sıxılması üçün üsullar və aparatlar. Amerika Birləşmiş Ştatları Patenti 4941193, 10 iyul 1990-cı il

* — Bu avtoreferatı yazarkən magistr dissertasiyası hələ tamamlanmamışdı. Onun yekun işi 2008-ci il dekabrın 1-də baş tutacaq. Dissertasiyanın mətni və materialları bu tarixdən sonra müəllifdən və ya onun elmi rəhbərindən əldə oluna bilər.

Əslində, fraktal alqoritmlərin praktik tətbiqi bu məqalədə müzakirə olunacaq. Fraktal sənətə toxunmayacağıq, bu barədə əvvəlki məqalədə kifayət qədər ətraflı yazılmışdı.

Fraktal təsvirin sıxılması.

Fraktal alqoritmlərin ilk və açıq tətbiqi sözdə idi fraktal təsvirin sıxılması. Fraktal təsvirin sıxılması- tətbiqə əsaslanan itkili görüntü sıxılma alqoritmi təkrarlana bilən funksiya sistemlərişəkillərə. (Təkrarlanan funksiyalar sistemləri və ya sadəcə SIF, bir çoxölçülü çoxluğu digərinə uyğunlaşdıran müəyyən sabit funksiyalar sinfindən funksiyalar sistemidir.) Bu alqoritm bəzi hallarda çox yüksək sıxılma əldə etməyə imkan verməsi ilə məşhurdur. əmsallar (ən yaxşı nümunələr 1000 dəfəyə qədərdir (məqbul vizual keyfiyyətdə) təbii obyektlərin real fotoşəkilləri üçün, bu, prinsipcə digər görüntü sıxılma alqoritmləri üçün əlçatmazdır.

Metodun əsası fraktal kodlaşdırma- bu, təsvirdə özünə bənzəyən sahələrin aşkarlanmasıdır. Təkrarlanan funksiya sistemləri nəzəriyyəsinin təsvirin sıxılması probleminə tətbiqi mümkünlüyü ilk dəfə Maykl Barnsli və Alan Sloan tərəfindən tədqiq edilmişdir.

Michael Barnsley.

Onlar 1990 və 1991-ci illərdə öz ideyalarını patentləşdirdilər.Fraktal arxivləşdirmə, təkrarlanan funksiyalar sisteminin əmsallarından istifadə edərək, təsvirin daha yığcam formada təqdim edilməsinə əsaslanır. Bu prosesi ən aydın şəkildə Barnslinin özü “Fraktal təsvirin sıxılması” kitabında nümayiş etdirmişdir. Bu, orijinal şəklin təsvir olunduğu ekrandan və təsviri başqa ekrana proyeksiya edən linzalar sistemindən ibarət olan Fotokopiya Maşını konsepsiyasını təqdim etdi. Hər bir obyektiv orijinal təsvirin bir hissəsini proyeksiya edir. Linzaları tənzimləmək və onların xüsusiyyətlərini dəyişdirməklə, nəticədə yaranan təsvirə nəzarət edə bilərsiniz. Linzalara bir tələb qoyulur: onlar təsvirin proqnozlaşdırılan hissəsinin ölçüsünü azaltmalıdırlar. Bundan əlavə, onlar fraqmentin parlaqlığını dəyişdirə və dairələri deyil, ixtiyari sərhədi olan əraziləri layihələndirə bilərlər.

Maşının bir addımı orijinal təsvirdən proyeksiya yolu ilə yenisini qurmaqdır. Bildirilir ki, hansısa addımda imic dəyişməyi dayandıracaq. Bu, yalnız linzaların yerindən və xüsusiyyətlərindən asılı olacaq və orijinal təsvirdən asılı olmayacaq. Bu şəkil bu SIF-in sabit nöqtəsi və ya cəlbedicisi adlanır. Kolaj teoremi (fraktal sıxılma prinsiplərindən biri) hər bir SIF üçün tam olaraq bir sabit nöqtənin mövcudluğuna zəmanət verir. Obyektiv xəritələşdirmə sıxıcı olduğundan, hər bir obyektiv təsvirimizdə özünə bənzəyən bölgələri açıq şəkildə müəyyən edir. Öz-özünə bənzərlik sayəsində istənilən böyütmədə mürəkkəb təsvir strukturu əldə edirik.

SIF istifadə edərək əldə edilən ən məşhur iki görüntü Sierpinski üçbucağı və Barnsley qıjısıdır. Birincisi üç, ikincisi isə beş afin çevrilmə (yaxud bizim terminologiyamızda linzalar) ilə verilir. Hər bir transformasiya sözün həqiqi mənasında bir neçə baytla müəyyən edilir, halbuki onların köməyi ilə qurulan təsvir bir neçə meqabayt tuta bilər.

Barnsley qıjı (solda) və Sierpinski üçbucağı(sağda).

Arxivçinin necə işlədiyi və niyə bu qədər vaxt apardığı aydın olur. Əslində, fraktal sıxılma təsvirdə özünə bənzəyən sahələrin axtarışı və onlar üçün afin transformasiya parametrlərinin müəyyən edilməsidir.

Ən pis halda, optimallaşdırma alqoritmi istifadə edilmədikdə, müxtəlif ölçülü bütün mümkün təsvir fraqmentlərini sadalamaq və müqayisə etmək lazım gələcək. Diskretliyi nəzərə alaraq kiçik şəkillər üçün belə, sıralanmaq üçün astronomik sayda seçim əldə edirik. Hətta çevrilmə siniflərini kəskin şəkildə daraltmaq, məsələn, yalnız müəyyən bir neçə dəfə miqyaslaşdırmaqla, məqbul vaxta nail olmağa imkan verməyəcəkdir. Bundan əlavə, görüntü keyfiyyəti itirilir. Fraktal sıxılma sahəsində aparılan tədqiqatların böyük əksəriyyəti indi yüksək keyfiyyətli təsvir əldə etmək üçün tələb olunan arxivləşdirmə vaxtını azaltmağa yönəlib.

Fraktalların tibbdə tətbiqi.

Bu zaman fraktallar tibbdə tətbiq olunur və yəqin ki, tapacaqlar. İnsan orqanizminin özü çoxlu fraktala bənzər strukturlardan ibarətdir: qan dövranı sistemi, əzələlər, bronxlar və s.

İnsan bədənində fraktal kimi strukturların nümunələri: bronxlar, qan damarları, əzələlər.

Buna görə də alimlər maraqlanırdılar ki, fraktal alqoritmlərdən hər hansı bir xəstəliyin diaqnozu və ya müalicəsi üçün istifadə etmək mümkündürmü? Belə çıxır ki, mümkündür. Məsələn, elektrokardioqramları təhlil etmək üçün fraktallar nəzəriyyəsindən istifadə etmək olar. Son illərdə inkişaf etmiş ölkələrdə ürək-damar xəstəliklərinin diaqnostikası və müalicəsi üçün yeni laboratoriya və instrumental üsulların işlənib hazırlanmasında aşkar uğurlar əldə olunmasına baxmayaraq, onların artımı davam edir. Təxminən bir saat, bir gün və ya daha çox davam edən bioritmlərin dövrləri, xüsusən də ürək dərəcəsi, histoqramma və ya spektral analizin ənənəvi üsullarından istifadə etməklə öyrənilə bilər. Bununla belə, fraktal ölçüsün böyüklüyünün xronostrukturunun və ritmlərinin qiymətləndirilməsi, Hurst indeksləri homeostaz pozğunluqlarını və spesifik xəstəliklərin inkişafını daha erkən mərhələdə və daha dəqiq və məlumat məzmunu ilə mühakimə etməyə imkan verir.

Kardioqramma nümunəsi.

Fraktallardan tibbi rentgen görüntülərinin işlənməsi zamanı da istifadə oluna bilər (hələ uğurlu təcrübələr mərhələsindədir).

X-ray nümunəsi.

Fraktal alqoritmlərdən istifadə etməklə işlənmiş rentgen şəkilləri daha yaxşı təsvir və müvafiq olaraq daha yaxşı diaqnostika təmin edir!!

Tibbdə fraktalların aktiv şəkildə istifadə oluna biləcəyi başqa bir sahə qastroenterologiyadır. İndiyə qədər və tez-tez bu günə qədər, müxtəlif qalınlıqdakı zondların tətbiqi ehtiyacı ilə əlaqəli olan mədə-bağırsaq xəstəliklərinin diaqnostikası üçün zond metodlarından istifadə olunur ki, bu da həm xəstə, həm də tibb işçiləri üçün xoşagəlməzdir. Bundan əlavə, belə bir tədqiqat texnikası somatik ağır xəstələrdə, əməliyyatdan sonrakı erkən dövrdə xəstələrdə və s. Məhz bu səbəbdən, fizioloqların və klinisistlərin mədə və bağırsağın motor-evakuasiya fəaliyyətinin öyrənilməsinə, eləcə də təkcə keyfiyyətcə deyil, həm də adekvat şəkildə mümkün olan yeni metodların işlənib hazırlanmasına olan davamlı marağını izah edir. mədə-bağırsaq traktının müxtəlif hissələrinin motor fəaliyyətinin intensivliyini və xarakterini kəmiyyətcə qiymətləndirin. MEF-nin öyrənilməsi üçün əlavə üsullar kimi orqanların elektrik aktivliyinin ölçülməsinə əsaslanan üsullar istifadə olunur. Mədə-bağırsaq traktının orqanlarının bioelektrik fəaliyyətinin tədqiqi tibbdə elektroqastroenteroqrafiya adlanan yeni tədqiqat metodunun yaradılmasının əsasını qoydu. Elektroqastroenteroqrafiya mədə, onikibarmaq bağırsağın və mədə-bağırsaq traktının digər hissələrinin bioelektrik fəaliyyətini qiymətləndirməyə imkan verən tədqiqat metodudur.

Elektroqastroenteroqramma nümunəsi.

O, mədə-bağırsaq traktından elektrik potensialında dəyişikliklərin qeydə alınmasına, yəni elektroqastroenteroqrammanın (EGEG) aparılmasına əsaslanır. Orqanlardan alınan bioelektrik siqnallara fraktal analizin tətbiqi orqanların və mədə-bağırsaq traktının motor funksiyasını effektiv şəkildə mühakimə etməyə və müxtəlif xəstəlikləri uğurla diaqnoz etməyə imkan verir.

Amerika alimlərinin son kəşfini də qeyd etmək lazımdır ki, əgər fizikada adheziya (latınca adhaesio – yapışma) – bir-birinə bənzəməyən bərk və/və ya maye cisimlərin səthlərinin yapışması) normal və xərçəng hüceyrələri, bu xəritələrin fərqli fraktal ölçülərə sahib olduğu ortaya çıxacaq. Ola bilsin ki, gələcəkdə bu kəşf xərçəngin diaqnostikası və müalicəsi üçün yeni effektiv üsulların kəşfinə kömək edəcək.

Xərçəng və normal hüceyrə səthlərinin yapışma xəritələri

Fraktalların təbiət elmlərində tətbiqi.

Fraktalların təbiət elmlərində tətbiqi olduqca böyükdür. Hər şeyi təsvir etsəm, bütöv bir kitab kifayət etməzdi. Buna görə də ən maraqlı məqamlardan bəzilərinə diqqət yetirəcəyik.

Fraktallar geologiya və geofizikada tez-tez istifadə olunur. Heç kimə sirr deyil ki, adaların və qitələrin sahilləri müəyyən fraktal ölçüyə malikdir, hansının sahillərin uzunluğunu çox dəqiq hesablaya biləcəyini bilər.

Fraktal analiz həmçinin faydalı qazıntı yataqlarının axtarışına və işlənməsinə kömək edir, onların paylanması çox vaxt fraktal mexanizmə uyğun olaraq baş verir. Qırılma tektonikasının və seysmikliyin öyrənilməsi bəzən fraktal alqoritmlərdən istifadə etməklə də öyrənilir.

Geofizika maqnit sahəsinin anomaliyalarını öyrənmək, dalğaların və dalğaların elastik mühitlərdə yayılmasını öyrənmək, iqlimi və bir çox başqa şeyləri öyrənmək üçün fraktallardan və fraktal analizdən istifadə edir.

Fizikada fraktallardan daha geniş istifadə olunur. Məsələn, bərk cisimlər fizikasında fraktal alqoritmlər bərk, məsaməli, süngər cisimlərin və müxtəlif aeroqellərin xassələrini dəqiq təsvir etməyə və proqnozlaşdırmağa imkan verir. Bu, qeyri-adi və faydalı xüsusiyyətlərə malik yeni materialların yaradılmasına kömək edir.

Bərk cismə misal olaraq kristalları göstərmək olar.

Axınlarda turbulentliyin öyrənilməsi fraktallara çox yaxşı uyğunlaşır. Turbulent axınlar xaotikdir və buna görə də dəqiq modelləşdirmək çətindir. Və burada fraktal təmsilə keçid kömək edir ki, bu da mühəndislərin və fiziklərin işini xeyli asanlaşdırır, mürəkkəb sistemlərin dinamikasını daha yaxşı başa düşməyə imkan verir. Fraktallardan istifadə edərək alovları simulyasiya edə bilərsiniz. Məsaməli materiallar çox mürəkkəb həndəsə malik olduqlarına görə fraktal formada yaxşı təmsil olunurlar. Neft elmində istifadə olunur.

Turbulentlik.

Fraktalların telekommunikasiyada tətbiqi.

Telekommunikasiyada fraktallardan fraktal antenalar yaratmaq üçün istifadə olunur. Fraktal antenalar, həndəsələri ilə məlum həllərdən əsaslı şəkildə fərqlənən, elektrik cəhətdən kiçik antenaların (EMA) nisbətən yeni sinfidir. Əslində, antenaların ənənəvi təkamülü tam ölçülü obyektlərlə (xətt, dairə, ellips, paraboloid və s.) işləyən Evklid həndəsəsinə əsaslanırdı. Qəribə dərəcədə yığcam dizayna malik fraktal antenna kiçik forma faktorunda üstün genişzolaqlı performans təmin edir. Müxtəlif yerlərdə quraşdırıla və ya yerləşdirilə biləcək qədər yığcam, fraktal antenalar dəniz, hava nəqliyyat vasitələri və ya şəxsi cihazlar üçün istifadə olunur.Yuxarıdakı şəkil fraktal antenanın nümunəsidir.

Şəbəkə texnologiyaları sahəsində də müxtəlif növ şəbəkələr üzərindən ötürülən trafikin öz-özünə oxşarlığını göstərən bir çox tədqiqatlar aparılmışdır. Bu xüsusilə nitq, audio və video xidmətləri üçün doğrudur. Buna görə də, indi məlumatın daha səmərəli ötürülməsi üçün şəbəkələr üzərindən ötürülən trafikin fraktal sıxılma imkanlarının yaradılması və tədqiqatı aparılır.

Fraktallar vizuallaşdırma elementləri və xüsusi effektlər kimi.

Fraktallar gözəlliyi və sonsuzluğu ilə cəlb edir və valeh edir. Buna görə də (yalnız deyil) fraktallar çox vaxt müxtəlif növ vizuallaşdırmalar, video qurğular yaratmaq, kompüter qrafikasında xüsusi effektlər yaratmaq və s.

Oyunlardan başlayaq. Bu gün müxtəlif növ təbii mənzərələrin mövcud olduğu bir çox oyun (bəlkə də Minecraft-ın ən parlaq nümunəsi) bu və ya digər şəkildə fraktal alqoritmlərdən istifadə edir. Bu üsul özünü kifayət qədər effektiv şəkildə sübut etdi. Fakt budur ki, həqiqi təbii cisimlər əsaslı olaraq fraktal quruluşa malikdir. Bunu nəzərə alan proqramçılar fraktal alqoritmlər əsasında kompüter mənzərələrini yaratmağa cəhd etdilər. Gözəl təbiət mənzərələrini müşahidə edə biləcəyiniz bugünkü müxtəlif oyunlara baxaraq, onların uğurla uğur qazandıqları qənaətinə gələ bilərik. Bundan əlavə, fraktal alqoritmlər əsasında landşaftların və landşaftların yaradılması üçün çoxlu sayda proqramlar yaradılmışdır.

Fractal Landscapes proqramından istifadə edərək fraktal alqoritmlərə əsaslanan landşaft modelləşdirməsi.

Minecraft oyununun ekran görüntüsü.

Filmlər fraktallar olmadan edilə bilməz. Əslində kinoda müxtəlif fantastik mənzərələr yaratmaq üçün oyunlarda olduğu kimi eyni prinsipdən istifadə olunur. Həqiqətən, niyə hər dəfə yeni bir ağac və ya dağ yaratmaq, ona çox vaxt sərf etmək lazımdır, halbuki bütün bunları fraktal alqoritmlər üzərində işləyən kompüter proqramlarından istifadə edərək dəfələrlə daha sürətli etmək olar. Maraqlı fakt: Ridley Scott-un məşhur kosmik qorxu filmi Alien-də komandanın planetin səthinə endiyi epizodda gəmidəki monitor planetin səthinin şəklini şəbəkə şəklində ötürür. Bu, fraktal həndəsədən istifadə edərək yaradılmış görüntüdür. Fraktal həndəsə xüsusi effektlər rəssamlarına asanlıqla bulud, tüstü, alov, ulduzlu səma və s. kimi obyektləri yaratmağa imkan verir.

İndi bir az da fraktal animasiya mövzusuna toxunaq. Müxtəlif generatorlarda yaradılmış fraktal təsvirlər son dərəcə gözəldir. Fraktal animasiya haqqında nə deyə bilərik, bu, həqiqətən heyrətamiz mənzərədir. İlk növbədə, Elektrik qoyun resursunu qeyd etmək lazımdır. Elektrikli qoyun fraktal alov alqoritmi əsasında fraktal animasiya yaratmaq üçün paylanmış hesablamalardan istifadə edən resursdur (Scot Draves tərəfindən hazırlanmışdır). Sadəcə olaraq, kompüterinizdə fraktal animasiyanı hesablamaq və göstərmək üçün maşınınızdan istifadə edən proqram təminatı quraşdırılıb, eyni zamanda “canlı” divar kağızı şəklində hazır fraktal animasiyanı yükləyib sizə göstərir. Eyni zamanda, bu eyni divar kağızları kompüterdə müəyyən bir qovluqda saxlanılır və oradan çıxarıla bilər və sonra öz məqsədləriniz üçün, məsələn, video montajında istifadə edilə bilər (videoların uzunluğu bir az qısa olsa da) - 5 saniyə). Ancaq Apophysis proqramı və bunun üçün Apophymator skripti sizin ixtiyarınızda olmaqla, istədiyiniz müddətə asanlıqla öz animasiyanızı yarada bilərsiniz (xoşbəxtlikdən İnternetdə bu mövzuda çoxlu dərslər var), əsas odur ki, maşınınız güclüdür. yetər.

Elektrik qoyun animasiya ekran görüntüləri:

Fraktal animasiya tamaşasından VJ-lər də öz video dəstlərində uğurla istifadə edirlər. Belə video qurğular xüsusilə elektron musiqi ifaçılarının konsertlərində istifadə olunur. Bunun üçün VJing proqramlarından (məsələn, Resolume) istifadə olunur. Resolume proqramından fraktal animasiya nümunələri:

Fraktal animasiya fraktal generatorlarla birbaşa əlaqəli olmayan proqram tərtibatçıları tərəfindən vizual olaraq istifadə olunur. Məsələn, tanınmış Winamp pleyerinin dəstində fraktal elementlərin aydın göründüyü çoxlu sayda vizualizasiyalar (süd damcısı plagini) var (məsələn, cizgi Julia dəsti). Winamp pleyeri üçün süd damlası plaginindəki vizual görüntülərin skrinşotları:

Beləliklə, bu qısa icmalı apardıqdan sonra belə, bu gün fraktalların və fraktal alqoritmlərin nəhəng praktik tətbiqi haqqında əminliklə deyə bilərik. Fraktalların istifadə olunduğu sahələrin diapazonu çox genişdir. Və şübhəsiz ki, yaxın gələcəkdə fraktalların istifadə olunacağı sahələrin siyahısı genişlənəcək!!!

Orijinal məqaləni Compuart jurnalının mart sayında oxumaq olar.

1. Fraktallar və fraktal sıxılma metodunun tarixi

1992-ci ilin dekabrında, Miladdan bir qədər əvvəl Microsoft, Microsoft Encarta adlı yeni CD-ni buraxdı. O vaxtdan bəri heyvanlar, çiçəklər, ağaclar və mənzərəli yerlər haqqında məlumatların yer aldığı bu multimedia ensiklopediya CD-də ən populyar ensiklopediyaların siyahısından çıxmadı. Microsoftun son sorğusunda Encarta ən yaxın rəqibi Compton Multimedia Ensiklopediyasını geridə qoyaraq yenə birinci yeri tutdu. Bu populyarlığın səbəbi istifadə rahatlığı, məqalələrin yüksək keyfiyyəti və ən əsası çoxlu sayda materialdır. Diskdə 7 saatlıq səs, 100 animasiya videosu, təxminən 800 miqyaslı xəritə, həmçinin 7000 yüksək keyfiyyətli fotoşəkil var. Və bütün bunlar - bir diskdə! Nəzərinizə çatdıraq ki, sıxılmadan adi 650 MB-lıq CD-də ya 56 dəqiqəlik yüksək keyfiyyətli audio, ya da MPEG-1 formatında 320x200 təsvir ölçülü 1 saatlıq video və ya 640x480 ölçülü 700 tam rəngli təsvir ola bilər. Daha çox məlumatı yerləşdirmək üçün kifayət qədər səmərəli arxivləşdirmə alqoritmlərinə ehtiyac var. Video və audio üçün arxivləşdirmə üsulları üzərində dayanmayacağıq. Biz yeni perspektivli alqoritmdən - qrafik informasiyanın fraktal sıxılmasından danışacağıq.

Konsepsiyalar "fraktal" Və "fraktal həndəsə" (fraktus- fraqmentlərdən ibarət, lat.) riyaziyyatçı tərəfindən təklif edilmişdir B. Mandelbrot 1975-ci ildə qeyri-müntəzəm, lakin öz-özünə oxşar strukturları ifadə etmək üçün. Fraktal həndəsənin doğulması adətən 1977-ci ildə B. Mandelbrotun “Təbiətin fraktal həndəsəsi” kitabının nəşri ilə əlaqələndirilir. Kitabın əsas ideyalarından biri o idi ki, ənənəvi həndəsə (yəni xətlərdən və səthlərdən istifadə etməklə) təbii obyektləri təmsil etmək son dərəcə çətindir. Fraktal həndəsə onları çox sadə şəkildə müəyyən edir.

Mandelbrotun fraktal tərifi belədir: "Fraktal müəyyən mənada bütünə bənzəyən hissələrdən ibarət bir quruluşdur"

Fraktalların əsas xüsusiyyətlərindən biri özünə bənzəməsidir. Ən sadə halda, fraktalın kiçik bir hissəsi bütün fraktal haqqında məlumat ehtiva edir. Fraktallar, dinamik sistemlərin bu gözəl təsvirləri əvvəllər kompüter qrafikasında əsasən səmanın, yarpaqların, dağların və otların təsvirlərini yaratmaq üçün istifadə olunurdu. Təbii obyekti etibarlı surətdə təqlid edən gözəl və ən əsası, təsviri bir neçə əmsalla müəyyən etmək olar.

Fraktalların geniş çeşidi var. Fraktalların potensial olaraq ən faydalı növü iterativ funksiyalar sisteminə əsaslanan fraktallardır (Təkrarlanan Funksiya Sistemi - IFS). Metod IFS fraktal təsvirlərin qurulması ilə əlaqədar olaraq, onlar üzərində böyük bir mütəxəssis tərəfindən icad edilmişdir Michael Barnsley və Dövlət Texnologiya İnstitutundan olan həmkarları. Gürcüstan (Gürcüstan Texnologiya İnstitutu), təsvir elementlərinin öz-özünə oxşarlığına əsaslanır və şəklin özünün bir neçə kiçik fraqmenti ilə modelləşdirilməsindən ibarətdir. Xüsusi tənliklər sizə təsvir sahələrinin miqyasını köçürməyə, döndərməyə və dəyişməyə imkan verir; beləliklə, bu sahələr rəsmin qalan hissəsi üçün tikinti blokları kimi xidmət edir.

Ən heyrətamiz (və məşhur) biri IFS-şəkil, hər bir yarpaq əslində qıjının özünün miniatür versiyası olan qara qıjıdır (şəklə bax). Şəklin afin çevrilmə metodundan istifadə edərək kompüter tərəfindən yaradılmasına baxmayaraq, qıjı tam olaraq gerçək kimi görünür. Təbiətin bitkilərin və ağacların genetik quruluşunu kodlaşdırarkən, metoda yaxın bir şeydən istifadə etdiyi irəli sürülür. IFS-fraktallar.

IFS-fraktalların bir çox real və faydalı tətbiqi var: onlar böyük rastr şəkillərini normal ölçülərinin bir hissəsinə sıxmaq üçün istifadə edilə bilər. Bu ifadə teoremdən irəli gəlir Banach kontraktiv çevrilmələr haqqında (həmçinin kimi tanınır Kolaj teoremi) və Dövlət Texnologiya İnstitutunun elmi işçisinin əməyinin nəticəsidir. Gürcüstan Michael Barnsleyərazisində IFS. Bu qənaətlə silahlanaraq institutu tərk etdi, kəşfini patentləşdirdi və şirkəti qurdu Iterated Systems Incorporated. O, bir jurnalda əldə etdiyi nailiyyət haqqında dünyaya danışdı bayt 1988-ci ilin yanvar ayı üçün. Lakin tərs məsələnin həlli haqqında heç bir məlumat yox idi: verilmiş təsvirdən affin çevrilmələri necə tapmaq olar. O vaxta qədər bu problemin həlli üçün bir işarə belə yox idi. Məqalədə Barnsley Bir neçə real fraktal təsvir göstərildi, lakin onların hamısı əl ilə yaradılmışdır.

İdeal olaraq, hər hansı bir görüntü üçün affin çevrilmələr sistemini tapa bilmək istərdim (IFSM), təsvirin verilmiş dəqiqliklə təkrar istehsalı. Ancaq həll yolu bir qədər söz mövzusu deyildi. Onu ilk tapan tələbə oldu Barnsley, Arnaud Jacquin. Təklif olunan üsul adlanır "Bölünmüş Təkrarlanmış Funksiya Sistemi - PIFS". Bu sxemə görə, təsvirin ayrı-ayrı hissələri bütün təsvirə deyil, yalnız onun hissələrinə bənzəyir.

2. Fraktal sıxılmanın riyazi əsasları

Fraktal sıxılma üsulları məlumatı 10.000 dəfə sıxmağa imkan verir. Bütün məlum fraktal sıxılma proqramları 1992-ci ildə dissertasiyasını müdafiə edərkən praktiki fraktal sıxılma alqoritmini təsvir edən Barnsley əməkdaşı Cekvinin alqoritminə əsaslanır. İşin şübhəsiz üstünlüyü ondan ibarət idi ki, insanın sıxılma prosesinə müdaxiləsi tamamilə aradan qaldırıldı.

Fraktal verilənlərin sıxılma mexanizmini nəzərdən keçirək. Fraktal arxivləşdirmə, təkrarlanan funksiyalar sisteminin əmsallarından istifadə edərək, təsvirin daha yığcam formada təqdim edilməsinə əsaslanır. Arxivləşdirmə prosesinə nəzər salmazdan əvvəl gəlin IFS-in təsviri necə qurduğuna baxaq. Düzünü desək, IFS bir təsviri digərinə çevirən 3D affin çevrilmələr toplusudur. Üçölçülü fəzada nöqtələr (x koordinat, y koordinat, parlaqlıq) transformasiyaya məruz qalır. Bu prosesi ən aydın şəkildə Barnslinin özü “Fraktal təsvirin sıxılması” kitabında nümayiş etdirmişdir. Bu, orijinal şəklin təsvir olunduğu ekrandan və təsviri başqa ekrana proyeksiya edən linzalar sistemindən ibarət olan Fotokopiya Maşını konsepsiyasını təqdim etdi. Hər bir obyektiv orijinal təsvirin bir hissəsini proyeksiya edir. Linzaları tənzimləmək və onların xüsusiyyətlərini dəyişdirməklə, nəticədə yaranan təsvirə nəzarət edə bilərsiniz. Tələb linzalara qoyulur ki, onlar təsvirin proqnozlaşdırılan hissəsinin ölçüsünü azaltmalıdırlar. Bundan əlavə, onlar fraqmentin parlaqlığını dəyişdirə və dairələri deyil, ixtiyari sərhədi olan əraziləri layihələndirə bilərlər. Maşının bir addımı orijinal təsvirdən proyeksiya yolu ilə yenisini qurmaqdır. Bildirilir ki, hansısa addımda imic dəyişməyi dayandıracaq. Bu, yalnız linzaların yerindən və xüsusiyyətlərindən asılı olacaq və orijinal təsvirdən asılı olmayacaq. Bu şəkil verilmiş IFS-in sabit nöqtəsi və ya cəlbedicisi adlanır. Kolaj teoremi hər IFS üçün tam olaraq bir sabit nöqtənin olduğuna zəmanət verir. Obyektiv xəritələşdirmə sıxıcı olduğundan, hər bir obyektiv təsvirimizdə özünə bənzəyən bölgələri açıq şəkildə müəyyən edir. Öz-özünə bənzərlik sayəsində istənilən böyütmədə mürəkkəb təsvir strukturu əldə edirik. IFS istifadə edərək əldə edilən ən məşhur iki təsvir Sierpinski üçbucağı və Barnsley qıjısıdır.Birincisi üç, ikincisi isə içməli, afin çevrilmələr (yaxud bizim terminologiyamızda linzalar) tərəfindən verilir. Hər bir transformasiya sözün həqiqi mənasında bir neçə baytla müəyyən edilir, halbuki onların köməyi ilə qurulan təsvir bir neçə meqabayt tuta bilər. Arxivçinin necə işlədiyi və niyə bu qədər vaxt apardığı aydın olur. Əslində, fraktal sıxılma təsvirdə özünə bənzəyən sahələrin axtarışı və onlar üçün afin transformasiya parametrlərinin müəyyən edilməsidir. Ən pis halda, optimallaşdırma alqoritmi istifadə edilmədikdə, müxtəlif ölçülü bütün mümkün təsvir fraqmentlərini sadalamaq və müqayisə etmək lazım gələcək. Diskretliyi nəzərə alaraq kiçik şəkillər üçün belə, sıralanmaq üçün astronomik sayda seçim əldə edirik. Hətta çevrilmə siniflərini kəskin şəkildə daraltmaq, məsələn, yalnız müəyyən bir neçə dəfə miqyaslaşdırmaqla, məqbul vaxta nail olmağa imkan verməyəcəkdir. Bundan əlavə, görüntü keyfiyyəti itirilir. Fraktal sıxılma sahəsində aparılan tədqiqatların böyük əksəriyyəti indi yüksək keyfiyyətli təsvir əldə etmək üçün tələb olunan arxivləşdirmə vaxtını azaltmağa yönəlib.

Beləliklə, fraktal sıxılmanın mümkünlüyünün riyazi əsaslandırılmasını nəzərdən keçirək.

Bütün mümkün şəkillərin toplusunun olduğu bir xəritə var. W Xəritəçəkmələrin birliyidir w i :

Belə xəritələr deyilir sıxıcı, və aşağıdakı ifadə onlar üçün doğrudur:

Əgər hansısa obraza F 0 Xəritəçəkməni yenidən tətbiq etməyə başlayacağıq W belə ki

Bu son görüntüdür Fçağırdı cəlbedici, və ya Xəritəçəkmənin sabit nöqtəsi W. Dönüşümlərin olduğu da məlumdur w i sıxıcıdır, sonra onların birləşməsi W həm də sıxıcıdır.

3. Tipik fraktal sıxılma sxemi

Yuxarıdakıları nəzərə alaraq, sıxılma sxemi belə görünür: şəkil R parçalara ayırmaq r i, çağırdı sıralama sahələri. Hər bir sahə üçün növbəti r i sahəsini tapın d i və transformasiya w i belə ki, aşağıdakı şərtlər yerinə yetirilir:

1. d iölçüsü daha böyükdür r i .

2. w i (r i ) ilə eyni forma, ölçü və mövqeyə malikdir r i .

3. Əmsal u transformasiya w i birdən az olmalıdır.

4. Dəyər mümkün qədər kiçik olmalıdır.

İlk üç şərt xəritələmə deməkdir w i sıxıcı olacaq. Və dördüncü şərtə görə kodlaşdırılmış şəkil R və onun obrazı W(R) bir-birinə bənzəyəcək. İdeal R=W(R). Bu, bizim imicimiz deməkdir R və sabit nöqtə olacaq W. Burada təsvirin müxtəlif hissələrinin oxşarlığından istifadə olunur (buna görə də adı - "fraktal sıxılma"). Məlum oldu ki, demək olar ki, bütün real şəkillərdə affin çevrilməyə qədər bir-birinə bənzər hissələr var.

Beləliklə, bir şəkil sıxışdırmaq üçün W lazımdır:

1. Şəkli sıralama sahələrinə bölün r i(bütün təsviri əhatə edən üst-üstə düşməyən sahələr).

2. Hər bir sıralama sahəsi üçün r i sahəni tapın d i(çağırılır domen) və göstərin w i, yuxarıda göstərilən xüsusiyyətlərlə.

3. Afin çevrilmələrin əmsallarını xatırlayın W, domen sahələrinin mövqeləri d i, həmçinin təsvirin domenlərə bölünməsi.

Müvafiq olaraq, təsviri açmaq üçün sizə lazım olacaq:

1. Bəzi (hər hansı) ilkin təsvir yaradın R 0 .

2. Ona bir neçə dəfə xəritəçəkmə tətbiq edin W(Birlik w i).

3. Ekrandan bəri W sıxıcı, sonra nəticədə kifayət qədər sayda iterasiyadan sonra şəkil cəlbediciyə gələcək və dəyişməyi dayandıracaq. Cazibədar bizim orijinal obrazımızdır. Dekompressiya tamamlandı.

Bu, yerləşdirmə zamanı onu bir neçə dəfə artırmağa imkan verir. Təbii obyektlərin təsvirləri böyüdüldükdə həqiqətən bu obyektlərə xas olan yeni detalların göründüyü nümunələr xüsusilə təsir edicidir (məsələn, qayanın fotoşəkili böyüdükdə yeni, daha kiçik pozuntular əldə etdikdə).

4. Sıxılma nisbətinin və hesablama xərclərinin qiymətləndirilməsi

Reytinq sahəsinin tam müəyyən edilməsi üçün məlumat ölçüsü düsturla hesablanır:

Harada Nb Və Mb- koordinatların hər birini saxlamaq üçün tələb olunan bitlərin sayı aşağıdakı düsturlardan istifadə etməklə hesablanır:

Harada V Və H- təsvirin şaquli və üfüqi ölçüləri, Ölçü- domen blokunun ölçüsü, addım- domen axtarışı addımı.

Transformasiyanı saxlamaq üçün T 3 bit tələb olunur.

Saxlama üçün U Və V Müvafiq olaraq 9 və 7 bit lazımdır.

Məsələn, 256x256 piksel ölçüsündə bir şəkil çəkək və domen sahəsini 4 piksel addımla araşdıracağıq.

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

Nb = Mb = CEIL (log 2 62) = 6

Z = 12 + 3 + 6 + 6 = 27

Sıxılma nisbəti S məbləğindədir

S = (8 * 8 * 8) / 27 = 19

Sıxılma nisbəti istədiyimiz qədər yüksək deyil, lakin sıxılma parametrləri optimaldan uzaqdır və nisbət əhəmiyyətli dərəcədə arta bilər.

İndi bu alqoritmin hesablama mürəkkəbliyini qiymətləndirək. Sıxılma mərhələsində bütün domen sahələrini sadalamalıyıq - 1024 ədəd, hər biri üçün - bütün dərəcə sahələri - 58.081 ədəd (1-ci addımda) və onların hər biri üçün, öz növbəsində, bütün 8 çevrilmə. Cəmi 1"024 x 58"081 x 8 = 475"799"552 hərəkətdir. Bununla belə, bu hərəkətlər əhəmiyyətsiz deyil və bir neçə matris əməliyyatını ehtiva edir ki, bu da öz növbəsində üzən nöqtəli ədədlərin vurma və bölmə əməliyyatlarını əhatə edir.

Təəssüf ki, hətta müasir kompüterdə (və bu, alqoritmini həyata keçirmək istədiyimiz maşın növüdür) yalnız 256 x 256 piksel ölçüsündə olan şəkli sıxmaq üçün qəbuledilməz dərəcədə uzun vaxt lazımdır. Aydındır ki, nəzərdən keçirilən alqoritmin optimallaşdırılması lazımdır.

Açar sözlər: neyron şəbəkələri; təsvirin sıxılması; maşın öyrənməsi; fraktallar.

annotasiya

Bu yazı fraktal təsvirin sıxılması üçün kodlaşdırma vaxtının azaldılması metodunu təqdim edir. Bu yanaşma, özünü təşkil edən neyron şəbəkəsindən istifadə edərək, xüsusiyyətlərin çıxarılmasını domen təsnifatı ilə birləşdirir. Xüsusiyyətlərin çıxarılması tapşırığın ölçüsünü azaldır və neyron şəbəkəyə kodlaşdırılandan fərqli bir görüntü üzərində məşq etməyə imkan verir. Təsnifat üçün özünü təşkil edən neyron şəbəkəsi klaster topologiyası konsepsiyasını təqdim edir və həmçinin bir çox uyğun görüntü siniflərinin apriori müəyyənləşdirilməsi ehtiyacını aradan qaldırır. Şəbəkə təlim prosesi zamanı əldə edilən təsvir xüsusiyyətlərinin paylanmasına uyğun olaraq özünü təşkil edir. Məqalədə təsnifat yanaşmasının müqayisəli dəqiqliyi və sıxılma səmərəliliyini qoruyarkən kodlaşdırma vaxtını iki böyüklük dərəcəsi ilə azalda biləcəyini göstərən nəticələr təqdim olunur.

1. Giriş

Fraktal təsvirin kodlaşdırılması İnternet saytları kimi təsvirin sıxılma tətbiqlərində perspektivli bir yanaşmadır. Bununla belə, bu yanaşmanın kodlaşdırma mərhələsi üçün vaxt tələbi onun praktiki metod kimi qəbul edilməsinə məhdudlaşdırıcı maneə olmuşdur. Kodlaşdırma prosesi domen bloklarını rütbəli şəkil bloklarına uyğunlaşdırmaqdır. Hər bir sıralama bloku üçün alqoritm sıralama blokuna ən yaxşı uyğunluğu təmin edəcək domen blokunu və müvafiq çevrilməni axtarır. Domen blokunun təsnifatı axtarılmalı olan domenlərin sayını azaltmaqla kodlaşdırmanı əhəmiyyətli dərəcədə sürətləndirə bilər. Domen təsnifatı məqsədi ilə özünü təşkil edən neyron şəbəkələrinin istifadəsi artıq tədqiq edilmişdir. Bu şəbəkələr sinif klasterlərinin topologiyasını müəyyən etməklə əsas təsnifat yanaşmaları üzərində təkmilləşdirməni təmin edir. Bu işin töhfəsi daha sürətli təsvir kodlamasını təmin etmək üçün özünü təşkil edən neyron şəbəkəsindən istifadə edərək domen təsnifatını xüsusiyyət çıxarılması ilə birləşdirməkdir. Hər bir domen və rütbə bloku üçün tonal və faktura keyfiyyətlərini ölçən kiçik təsvir xüsusiyyətləri dəsti hesablanır. Beləliklə, hər bir blokun ölçüsü blokun ölçüsündən asılı olmayan əlaqəli xarakteristikalar vektoru var. Xüsusiyyətlərin çıxarılması iki səbəbə görə faydalıdır. Birincisi, nəticədə problem ölçüsünün azalması domen axtarışı prosesində tələb olunan hesablamaların həcmini azaldır. İkincisi, xarakteristikalar konkret domenlərin strukturundan asılı olmadığından, bir şəkil üzərində özünü təşkil edən bir şəbəkə hazırlamaq və əldə edilən şəbəkədən digər şəkillərdə təsnifat üçün istifadə etmək mümkün olur. Beləliklə, şəbəkə təlim vaxtı ümumi kodlaşdırma vaxtının bir hissəsi deyil. Fraktal təsvirin kodlaşdırma vaxtının ölçülməsi adətən Günəş və ya Silicon Graphics iş stansiyasında icra vaxtı baxımından ifadə edilir. Burada təqdim olunan yanaşma Pentium 120 MHz kompüterdə yerinə yetirildikdə müqayisə edilə bilən ölçmələri təmin edir.

2. Təsvirlərin fraktal kodlaşdırılması

Şəkillərin fraktal kodlaşdırılması təkrarlanan funksiya sistemləri nəzəriyyəsinə (bundan sonra IFS kimi qısaldılacaq, İngilis İterated Function System - IFS) əsaslanır. CIF nəzəriyyəsi fraktal təsvirləri iterativ şəkildə qurmaq üçün istifadə edilən klassik analizdən alınan büzülmə xəritəçəkmə teoreminə (bundan sonra TOC kimi qısaldılacaq, İngilis Daralma Xəritəçəkmə Teoremindən - CMT) əsaslanır. Fraktal şəkil TOS tərəfindən təmin edilən təsvir məkanında sabit nöqtədir və bu görüntü CIF cəlbedicisi adlanır. Fraktal təsvirin kodlaşdırılması ilə həll olunan tərs məsələ verilmiş təsvirin nəzərdən keçirilməsi və verilmiş birinə - onun cəlbedicisinə yaxın təsviri təmsil edən SIF-in hesablanması ilə başlayır. Fraktal şəkil kodu adətən (həmişə olmasa da) orijinal təsvirdən daha az yaddaş sahəsi tələb edir ki, bu da onu sıxılma texnikasına çevirir. Empirik nəticələr göstərir ki, bir çox hallarda fraktal metod bu gün sıxılma standartı hesab edilən JPEG qədər yaxşıdır.

Fraktal təsvirin sıxılması, bölünmüş təkrarlanan funksiya sistemi (PIFS) adlanan xüsusi bir PIF növündən istifadə edir. CICF tam X metrik fəzasından, D i ⊂ X, i = 1,...,n subdomenləri dəstindən və w i ~ : D i → X, i = 1,... daralma çevrilmələri dəstindən ibarətdir. ,n. Biz boz rəngli şəkilləri I 2 = I×I kvadrat bölgəsində müəyyən edilmiş f(x, y) real qiymətlərinin funksiyaları hesab edirik. w i ~ (x, y) affin çevrilmə I 2 → I 2 olsun ki,

bir şərtlə ki, w i ~ tərsinə çevrilsin və (x,y) ∈ R i olsun. s i sabiti f funksiyasının dəyər diapazonunu genişləndirir və ya daraldır və boz rəngli şəkillərdən bəhs etdiyimiz üçün kontrastı idarə edir. Eynilə, o i sabiti boz rəngin dəyərlərini artırır və ya azaldır və ya parlaqlığı idarə edir. w i ~ çevrilməsi w i çevrilməsinin məkan komponenti adlanır.

Əsas alqoritm aşağıdakı kimi yerinə yetirilir. Şəkili üst-üstə düşməyən düzbucaqlı rütbəli bloklara (Ri) bölürük. Bloklar R i eyni ölçüdə ola bilər, lakin daha tez-tez dəyişən blok ölçüsü ilə bir növ bölmə istifadə olunur ki, bu da təsvirin kiçik detalları olan hissələrini kiçik dərəcə blokları ilə sıx doldurmağa imkan verir. Burada təqdim olunan nəticələr -də təsvir olunan dörd ağaclı bölmə sxemindən istifadə etməklə əldə edilmişdir. Şəkili domen bloklarının ardıcıllığı ilə əhatə edirik, ehtimal ki, üst-üstə düşür. Domenlər müxtəlif ölçülərdə ola bilər və adətən yüzlərlə və minlərlə olur. Afin transformasiyası (2.1) |det A i | olarsa, məkan müqavilə transformasiyasıdır

(2.3)

balaca idi. Rəqəmləşdirilmiş şəkillər üçün inteqral (2.3) piksellər üzərində cəmləmə ilə əvəz olunur. Əgər ən yaxşı w i tapdıqdan sonra dəyər (2.3) hələ də əvvəlcədən müəyyən edilmiş xətadan böyükdürsə, o zaman dörd ağacın bölmə sxemi rütbəni daha dörd kiçik düzbucaqlıya bölür və optimal çevrilmənin tapılması prosesi bu kiçik bloklar üçün təkrarlanır. Bu proses (2.3) dəyəri icazə verilən xətadan az olana və ya əvvəlcədən müəyyən edilmiş maksimum dörd ağacın dərinliyinə çatana qədər davam edir. Şəkil, W çevirməsinin f şəklinə təkrarlanması ilə deşifrə edilir, burada

(x,y) ∈ R i üçün W(f)(x,y) = w i (f)(x,y)

Əgər transformasiyalar (wi) düzgün seçilibsə, onda W 0n (f) iterasiyası n-in kifayət qədər dəyəri üçün orijinal təsvirə yaxın olacaq. Kodlaşdırma addımı hər bir dərəcə bloku üçün axtarılmalı olan domenlərin çoxluğuna, həmçinin domenin dərəcə ilə müqayisəsi zamanı tələb olunan hesablamalara görə hesablama baxımından intensivdir. Bu işdə kodlaşdırma mərhələsinin hesablama tələblərinin azaldılması iki yolla həll edilir. Əvvəlcə hər bir domen və rütbə bloku üçün müəyyən edilmiş təsvir xüsusiyyətləri anlayışı təqdim edilir. Potensial uyğun domenlər daha sonra piksellərin öz dəyərlərindən daha az sayda bu xüsusiyyətlərin dəyərlərinə əsasən seçilə bilər. İkincisi, özünü təşkil edən neyron şəbəkəsindən istifadə edərək domen bloklarının klaster topologiyasına təşkil edilməsi təklif olunur. Bu, şəbəkəyə rütbəli bloklara oxşar olan domen bloklarını xüsusiyyət məkanında tez tapmağa imkan verməklə kodlaşdırma vaxtını daha da azaldır.

3. Xüsusiyyətlərin çıxarılması

Şəkillərin fraktal kodlaşdırılması prosesini sürətləndirməyin bir yolu domen və rütbə bloklarını təsvir edən az sayda xarakteristikaları təcrid etməkdir. Sonra domen və rütbə bloklarının müqayisəsi işin həcmini azaldan fərdi piksellər üzrə deyil, bu xüsusiyyətlər əsasında aparılır. Bu işdə təsvirin faktura və kontrast paylanmasını təsvir edən altı xüsusiyyətdən istifadə edilmişdir. Xüsusiyyətlərin çıxarılmasının özü kodlaşdırma prosesini əhəmiyyətli dərəcədə sürətləndirir.

Burada aşağıdakı altı xüsusiyyətdən istifadə olunur: 1) standart kənarlaşma, σ; 2) σ kubu ilə normallaşdırılan piksel dəyərləri ilə blokun orta dəyəri arasındakı fərqlərin kublarının cəmi olan asimmetriya (çarpıqlıq); 3) qonşu piksellərin dəyərləri arasındakı fərqi ölçən piksellərarası kontrast (qonşu kontrastı); 4) piksel dəyərlərinin blokun mərkəzindəki dəyərdən nə qədər fərqləndiyini göstərən beta; 5) blok piksel qiymətlərinin üfüqi dəyişməsini xarakterizə edən üfüqi qradiyent; 6) blok piksel dəyərlərinin yuxarıdan aşağıya dəyişməsini xarakterizə edən şaquli gradient. Domen və dərəcə blokları arasında uyğunluq prosesi zamanı kontrast və parlaqlıq dəyişdiyi üçün orta piksel dəyəri xüsusiyyət kimi istifadə edilmir. Xüsusiyyət məkanında məsafələri müqayisə edərkən, böyük xüsusiyyət dəyərlərinin müqayisədə üstünlük təşkil etməməsini təmin etmək üçün xüsusiyyət vektoru normallaşdırılır.

4. Özünü təşkil edən neyron şəbəkələri

Ediləcək növbəti təkmilləşdirmə domenləri və dərəcələri bu xüsusiyyətlərə əsasən təsnif etmək və dərəcələri yalnız oxşar siniflərin domenləri ilə müqayisə etməkdir. Burada istifadə olunan domen təsnifatı sxemi özünü təşkil edən Kohonen neyron şəbəkəsinə əsaslanır. Bu tip şəbəkə qovşaq mövqelərinin şəbəkəsindən ibarətdir. Hər bir qəfəs nodu xarakterik vektorların ölçüsü ilə eyni ölçüyə malik olan çəki vektoru ilə əlaqələndirilir. Burada istifadə olunan xüsusiyyət vektorlarının ölçüsü 6-dır. Burada istifadə olunan qovşaq şəbəkəsi isə 10 sətir və 10 sütundan ibarətdir. Hər bir qovşaq bir şəkil domen blokları sinfini təmsil edir, ona görə də biz qovşaqların ümumi sayını kifayət qədər kiçik saxlamağı hədəfləyirik. Daha yüksək ölçülü matrislər kimi qovşaqların təşkilinin digər yolları nəzərdən keçirilə bilər.

Öyrənmə prosesi müstəqil şəkildə, heç bir insanın nəzarəti olmadan baş verir. Çəki vektor şəbəkəsi təsadüfi qiymətlərlə işə salınır. Sonra şəbəkə giriş xüsusiyyət vektorunu alır və biz giriş vektoruna ən yaxın olan çəki vektorunu tapırıq. Yəni biz i’j’ belə tapırıq

||v – w i’j’ || ≤ ||v – w ij || hamısı üçün i, j

burada v giriş xüsusiyyət vektoru və w ij qovşağında çəki vektorudur. Şəbəkədə seçilmiş w i’j çəkisinə bitişik çəkilər giriş vektoruna daha çox bənzəmək üçün uyğunlaşdırılmışdır. Bu uyğunlaşma düsturla ifadə edilir

w ij yeni = w ij köhnə + ε·exp(α·||v–w ij köhnə || 2)·(v– w ij köhnə)

burada ij i’j qovşağının qonşuluğunda olan qovşaqların indeksləridir. Bu məhəllənin ölçüsü öyrənmə prosesinin hər yeni iterasiyası ilə azalır. ε parametri iterasiya pilləsidir və α bu addımla tərs mütənasibdir. Təqdim olunan nəticələrin proqram təminatının tətbiqi bənddə verilmişdir.

Şəbəkə öyrədildikdən sonra verilmiş təsvir üçün domen blokları onların hər birinə xüsusiyyət məkanında ona ən yaxın olan çəki vektorunu təyin etməklə təsnif edilir. Reytinq blokunun xarakteristikası vektoru şəbəkəyə daxil olduqda, o, həm də şəbəkənin çəki vektoru ilə əlaqələndirilir. Sonra sıralama bloku bu çəki vektoru ilə əlaqəli olan domenlərlə, həmçinin şəbəkə qəfəsindəki bitişik çəki vektorları ilə əlaqəli domenlərlə müqayisə edilir. Özünü təşkil edən neyron şəbəkəsinə əsaslanan təsnifatın üstünlüyü, şəbəkə qəfəsləri ilə təmin edilən görüntü siniflərinin bitişik olanlara təşkili ideyasındadır. Digər bir üstünlük ondan ibarətdir ki, şəkil növlərinin bu qruplaşması şəkil siniflərini əvvəlcədən təyin etməyə ehtiyac olmadan baş verir.

5. Nəticələr

Cədvəl 1 Şəkil 1 və 2-də göstərilən şəkillərə tətbiq edilən üç müxtəlif üsuldan istifadə edərək fraktal təsvirin sıxılmasının müqayisəsinin nəticələrini təqdim edir. "Baza" metodu domen təsnifatı olmadan - -da müzakirə edilən standart dördlü ağac bölmə üsuludur. “Dörd ağacın səviyyəsi” dəyəri dörd ağacın icazə verilən maksimum dərinliyini göstərir. Burada böyük bir rəqəm daha kiçik rütbəli bloklara gətirib çıxarır ki, bu da deşifr edilmiş təsvirin daha keyfiyyətli olmasına, eyni zamanda daha pis sıxılmaya səbəb olur. “Səhv həddi” dərəcə bloklarının dördlü ağacın növbəti yüksək səviyyəsinin daha kiçik bloklarına bölünməsi şərtini idarə edən parametrdir. Səhv dəyərləri orijinal bitmapı 6 iterasiyadan istifadə edərək deşifrə edilmiş təsvirlə müqayisə etməklə hesablanır (daha çox iterasiya bir qədər kiçik xətalar yaradar). "Orta xəta" piksel başına orta xətadır, "PSNR" isə -də olduğu kimi hesablanmış pik siqnal-küy nisbətidir. "FO" (yalnız funksiyalar üçün) metodu Bölmə 3-də müzakirə edilən altı xüsusiyyət əsasında domen və dərəcə bloklarını müqayisə edir. Yekun üsul ("SO") yuxarıda müzakirə edildiyi kimi özünü təşkil edən funksiyaları çıxaran neyron şəbəkədən istifadə edərək domenləri təsnif edir. Hər bir halda ümumilikdə 320 domen blokundan istifadə edilib. Daha çox domen daha uzun kodlaşdırma vaxtlarına və müəyyən dərəcədə daha yaxşı sıxılma nisbətlərinə səbəb olacaqdır.

Sıxılma əmsalları hər bir sıra bloku üçün orta hesabla 4 baytın orijinal bitmapın 66614 baytına nisbəti ilə qiymətləndirilir. SO metodu FO metodundan təxminən iki dəfə və baza metodundan yüz dəfə sürətlidir (“blok başına vaxt” yekun təsvirin dəqiqliyindən asılı olmayan icra vaxtının ölçüsünü ifadə edir; burada verilən vaxtlar Pentium üçündir. 120MHz kompüter). Özünü təşkil edən şəbəkə burada təqdim olunan iki şəkildən fərqli bir şəkil üzərində ayrıca məşq edilmişdir, ona görə də məşq vaxtı bu metod üçün ümumi vaxta daxil edilmir. Həm sürətləndirilmiş üsullarla, həm də əsas üsulla deşifrə edilmiş təsvirin sıxılma dərəcəsi və keyfiyyəti müqayisə edilə bilər.

Cədvəl 1 - Özünü təşkil edən domen təsnifatından (“SO” metodu) istifadə edərək fraktal təsvirin sıxılmasının nəticələri, yalnız xüsusiyyətlərə əsaslanan domenlərin müqayisəsi (“FO”) və əsas metod (“Baza”)

	Şəkil	Xəta həddi	Dörd ağac səviyyəsi	Blokların sayı	Vaxt, (s)	Blok başına vaxt, (s)	Orta xəta, %		Kof. sıxılma







(A)	(b)

Şəkil 2 - (a): Orijinal rastr təsviri “Yarpaqlar” (256×256, 256 boz rəng); (b): Deşifrə edilmiş şəkil (6 iterasiya, dörd ağac səviyyəsi 7, orta piksel xətası 3,05%, sıxılma 1,6:1). Bu təsvirdə yüksək səviyyəli təfərrüatlar daha yavaş performansla nəticələnir

6. Nəticələr

Özünü təşkil edən neyron şəbəkəsi ilə funksiyaların çıxarılmasını domen təsnifatı ilə birləşdirmək kodlaşdırmanın əhəmiyyətli sürətini təmin edir. Şəklin az sayda xüsusiyyətə görə təsnifləşdirilməsi nəinki hesablamaların həcmini azaldır, həm də şəbəkəyə kodlaşdırılandan başqa bir şəkil üzərində təlim keçməyə imkan verir, beləliklə, ümumi kodlaşdırma vaxtından məşq vaxtını aradan qaldırır. Özünü təşkil edən şəbəkə özünün təmsilçi domen sinifləri dəstini yaradır və həmçinin domen siniflərinin klaster topologiyasını müəyyən edir.

Ədəbiyyat

E. DeJesus, “Walking, Talking Web,” Bayt, Yanvar, 1997, 81-84.
Y. Fisher, red., Fractal Image Compression, (Nyu York: Springer-Verlag, 1995).
A. Jacquin, “Image coded based on a fractal theory of iterated contractive image transformations”, IEEE Trans. Şəkil Proc. 1, 1992, 18-30.
A. Bogdan və H. Meadows, “İterasiya çevrilmə nəzəriyyəsinə əsaslanan təsvirin kodlaşdırılması üçün Kohonen neyron şəbəkəsi”, Proc. SPIE 1766, 1992, 425-436.
R. Hamzaoui, “Fraktal təsvirin sıxılması üçün öz-özünə təşkil edilən xəritələr vasitəsilə kod kitabçası qruplaşması,” NATO ASI Conf. Fraktal təsvirin kodlaşdırılması və təhlili haqqında, iyul, 1995-ci il.
M. Barnsley, Fractals Everywhere, 2-ci nəşr. (Boston: Academic Press, 1993).
T. Kohonen, Özünü Təşkilat və Assosiativ Yaddaş, (Springer-Verlag, 1989).
S. Welstead, Neural Network and Fuzzy Logic Applications in C/C++, (New York: John Wiley and Sons, 1994).

Vektor kvantlaşdırması ilə rəqəmsal siqnalın N nümunələri qrupu eyni vaxtda kodlanır ( N-ölçülü vektor). Bir ölçülü siqnal vəziyyətində vektorlar qruplar ola bilər N ardıcıl saymalar. Şəkil vəziyyətində vektorlar bir neçə üfüqi və şaquli bitişik təsvir elementlərinin blokları ola bilər. Şəkildə. Şəkil 5.54-də vektor kvantlaşdırmasından istifadə edən informasiyanın ötürülməsi sisteminin blok-sxemi göstərilir.

Vektor kvantlaşdırılmasının mənası aşağıdakı kimidir. Siqnalda baş verənlərin dəsti N-ölçülü vektorlara bölünür L alt çoxluqlar ki, hər bir alt çoxluğa daxil olan vektorlar bir-birindən az fərqlənsin. Hər alt çoxluqda həmin alt çoxluqdakı bütün vektorları təmsil etmək üçün bir istinad vektoru seçilir. Bütün istinad vektorları kod kitabçasına yazılır və onların hər birinə xüsusi kod sözü verilir.

Rəqəmsal giriş x(n) kodlayıcı girişinə gəlir. Kodlaşdırma proseduru ondan ibarətdir ki, kod kitabçasındakı hər bir N ölçülü vektor üçün ona ən yaxın istinad vektoru var, onun kodu kodlayıcının çıxışına göndərilir. Beləliklə, hər bir qrup üçün N- giriş siqnalı nümunələri x(n) bir kod sözü ötürülür u(k).

Alınan kod sözünə uyğun olaraq dekoderdə u(k)(bar siqnalın rabitə kanalına gəldiyini göstərir) istinad vektoru kod kitabından oxunur və bir qrupa çevrilir. Nçıxış siqnal nümunələri y(n). Kod kitabçası kodlaşdırılan siqnalın xüsusiyyətlərindən asılı olaraq dəyişə bilər.

Vektor kvantlaması itkili sıxılma üsuludur və real qruplar olduğundan N giriş siqnalı nümunələri X(n)çıxış siqnalında y(n) istinadlar ilə əvəz olunur N- ölçülü vektorlar. Vektor kvantlaşdırmasının üstünlüklərindən biri kod kitabından yalnız istinad vektorunun oxunması əməliyyatını yerinə yetirən dekoderin sadəliyidir.

Eyni zamanda, kodlaşdırılan birinə ən yaxın istinad vektorunun kodlayıcıda axtarışı böyük miqdarda hesablamalar tələb edir. Kvadrat kvantlaşdırma xətasının minimum dəyərinə çatdıqda kod kitabçasından ən yaxın istinad vektoru oxunur E :

E= S (a j -b j) 2 ,

Harada a j- giriş vektorunun elementləri; b j– istinad vektorunun elementləri.

Vektor kvantlaşdırmasına yaxın fraktal təsvir kodlamasıdır, burada orijinal təsvirin özündən kəsilmiş bloklar kod kitabçası elementləri kimi istifadə olunur.

Fraktal sıxılma üsulları vektor kvantlaşdırmasının modifikasiyası hesab edilə bilər, burada orijinal təsvirin özündən müxtəlif yollarla kəsilmiş bloklar kod kitabçası elementləri kimi istifadə olunur. Kodlanmış təsvirin bloklarını çevirmək mümkündür, bu blokların istinad bloklarına (fırlanmalar, güzgü əksləri) oxşar olmasına imkan verir. Vektor kvantlaşdırılması və fraktal kodlaşdırma televiziyada istifadə edilə bilər, məlumatın əhəmiyyətli dərəcədə sıxılmasını təmin edir.

Bununla belə, kodlaşdırmada iştirak edən böyük hesablamalar rəqəmsal televiziya sistemlərində bu üsulların istifadəsinə mane olur.

Nəzarət sualları

1. Rəngli təsvir blokları JPEG standartına uyğun olaraq hansı ardıcıllıqla kodlanır?

2. Nə üçün DCT əmsallarının kvantlaşdırılması təsvirin özünün kvantlaşdırılmasından daha az nəzərə çarpan təhriflər yaradır?

3. JPEG standartı sıxılma dərəcəsinə necə nəzarət edir?

4. Dəyişən uzunluqlu kod sözlərlə kodlaşdırmanın mahiyyəti nədir?

5. “Hibrid kodlaşdırma” termini MPEG-1, MPEG-2 standartlarına münasibətdə nə deməkdir?

6. Nə üçün MPEG-1, MPEG-2 kodlaşdırmadan əvvəl çərçivələr GOP-da yenidən təşkil edilir?

7. MPEG-1, MPEG-2-də çərçivə və sahə kodlaşdırma rejimləri arasında fərq nədir?

8. Nə üçün B-çərçivələr ən yüksək sıxılma dərəcəsinə nail oldular?

9. MPEG-2 kodlayıcıda bufer yaddaşın məqsədi nədir?

10. Ölçeklenebilirlik nədir?

11. MPEG-2 səviyyələri və profilləri hansılardır?

12. MPEG-2 nəqliyyat axınından müxtəlif televiziya proqramlarının məlumatları necə çıxarılır?

Kateqoriyalar

Redaktor seçimi