2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Vaizdų glaudinimas

Taškai: 12

Pažvelkite į 4 × 4 juodų ir baltų langelių (pikselių) paveikslus:

Paveikslus galime aprašyti dvejetainiais skaitmenimis: „1“ – baltas langelis, „0“ – juodas langelis.

Taigi 4 × 4 dydžio vaizdui užrašyti reikia 16 skaitmenų. Šiuo glaudinimo metodu galime tai užrašyti taupiau, ypač nesudėtingais atvejais, pavyzdžiui:

Dvejetainiai skaitmenys išdėstomi lentele kaip pikseliai vaizduose.

Glaudinimo metodas taikomas skaitmenų lentelei, kol gaunamas rezultatas – eilutė:

Jei visi skaitmenys lentelėje lygūs 0, rezultatas yra „0“ (kairysis paveikslas). Jei visi skaitmenys lygūs 1, rezultatas yra „1“.

Kitais atvejais lentelė dalijama į keturias lygias dalis (kvadrantus). Glaudinimo metodas taikomas kiekvienai iš šių dalių atskirai, pradedama nuo kairiausios viršutinės ir einama pagal laikrodžio rodyklę. Rezultatai rašomi iš eilės suskliaudžiant ( ir ). Panagrinėkime vaizdus viduryje ir dešinėje.

Atkreipkime dėmesį, kad lentelė ar analizuojama jos dalis gali būti sudaroma ir iš vieno skaitmens. Šiuo atveju taikant metodą prireiks tik 1-ojo žingsnio.

Pateiktas 8 × 8 vaizdas – skaitmenų lentelė. Čia pritaikytas glaudinimo metodas.

Kuri eilutė nusako rezultatą?

A) (1110)

B) (11(1011)1)

C) (111(1(1101)11))

D) (111(1(1011)11))

Paaiškinimas

Kvadrantų medis yra medžio duomenų struktūra, kurios kiekvienas mazgas turi keturis pomazgius. Kvadrantų medžiai taikomi dvimatei erdvei dalyti į dalis, kurias patogu analizuoti ar apdoroti kartu. Jie taikomi glaudinant ir apdorojant grafinius vaizdus.

Kvadrantų medžio glaudinimas aprašytas čia:

https://en.wikipedia.org/wiki/Quadtree

Tinka tik tam tikro tipo paveikslams.

Raktiniai žodžiai: kvadrantų medžio metodas, pikselis, vaizdų glaudinimas

Atsakymas

Teisingas atsakymas yra D.