Şəkil Sıxılması
İkiölçülü şəkillərin sıxılması üçün strategiyalar, adətən, yüksək oxşarlığa malik bölgələrin tapılmasına əsaslanır. Bu məsələdə biz şəkilin iyerarxik parçalanmasına əsaslanan xüsusi bir yanaşmanı araşdırırıq. Sadəlik üçün biz aşağıdakı kimi bit xəritəli şəkilləri nəzərdən keçiririk:
Şəkil ağac kimi kodlanır, burada kök bütün şəkil bölgəsini təmsil edir. Əgər bir bölgə monoxromatikdirsə, o zaman həmin bölgə üçün düyün həmin bölgənin rəngini saxlayan yarpaqdır. Əks halda, bölgə mərkəzi ətrafında dörd hissəyə bölünür və yanaşma hər kvadranta təkrarlanır. Yarpaq olmayan düyün üçün onun dörd uşağı müvafiq olaraq yuxarı-sağ, yuxarı-sol, aşağı-sol, aşağı-sağ kvadrantları təmsil edir. Məsələn, yuxarıdakı şəkilin ağac kodlaması belədir.
Orijinal şəkil monoxromatik deyil, buna görə də dörd kvadrantı nəzərdən keçirdik. Yuxarı-sağ kvadrant monoxromatik ağdır, buna görə də kök düyünün ilk uşağı dəyəri 0 olan yarpaqdır. Yuxarı-sol kvadrant monoxromatik deyil, buna görə də o, dörd alt kvadranta bölünür, hər biri trivially monoxromatikdir. Bu, dəyəri 0, 0, 1, 0 olan yarpaq alt ağacını yaradır. Son iki kvadrant müvafiq olaraq 0 və 1 dəyərləri ilə monoxromatikdir.
Daha böyük bir nümunə olaraq, burada 8x8 şəkil və onun ağac kodlaması var.
İndiyə qədər biz itkisiz sıxılma sxemini təsvir etdik, lakin yanaşma aşağıdakı düzəlişlə itkilərlə sıxılma üçün istifadə edilə bilər. Monoxromatik bölgəyə çatana qədər parçalanmaya davam etmək əvəzinə, 75% kimi bir hədd istifadə olunur və bir bölgə hər hansı bir rəngin ən azı həmin faizinə malik olduqda yarpaq yaradılır. Məsələn, 75% həddindən istifadə edildikdə yuxarıdakı 8x8 şəkilin kodlaması belədir.
Diqqət yetirin ki, tam şəkilin yuxarı-sol kvadrantının 75%-i qaradır və buna görə də kökün ikinci uşağı 1-dir və tam şəkilin aşağı-sol kvadrantının 75%-dən çoxu ağdır və buna görə də kökün üçüncü uşağı 0-dır. Lakin, yuxarı-sağ kvadrantda nə ağ, nə də qara 75%-ə çatmır, buna görə də rekursiv parçalanma davam edir, lakin bu alt kvadrantların hər biri 75% həddinə çatır və yarpaqlara çevrilir. Əgər biz bu yeni itkilərlə kodlamaya əsaslanaraq şəkili açsaydıq, aşağıdakı nəticəni alardıq.
Sizin məqsədiniz, orijinal bit xəritəli şəkil və müəyyən bir hədd faizi verildikdə, bu itkilərlə sıxılma sxemindən yaranan şəkili müəyyən etməkdir.
Giriş verilənləri
Giriş bir sıra məlumat dəstlərindən ibarət olacaq, yalnız 0 olan bir sətr ilə tamamlanacaq. Hər bir məlumat dəsti W və T dəyərlərini ehtiva edən bir sətr ilə başlayır, burada W bit xəritəsinin eni, T isə hədd faizidir. Şəkillər həmişə kvadrat olacaq və 1 ≤ W ≤ 64 iki gücü olacaq. Hədd T 51 ≤ T ≤ 100 aralığında tam ədəd olacaq. W və T spesifikasiyasından sonra W əlavə sətr gəlir, hər biri yalnız 0 və 1 simvollarını ehtiva edən eni W olan bir sətirdir, şəkil bit xəritəsinin yuxarıdan aşağıya bir sıra təmsil edir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün "Image 1:" formasında bir başlanğıc sətri çap etməlisiniz, şəkilləri 1 ilə başlayaraq nömrələyin. Bundan sonra, hər biri yuxarıdan aşağıya bir sıra olaraq 0 və 1 simvollarından ibarət bir sətir olan W sətri gəlməlidir.