Problem Set #4: BMP Transform!

Ciele

  • Naučiť sa pracovať so štruktúrovanými údajovými typmi.
  • Naučiť sa používať štandardné prúdy vo svojom programe.
  • Prehĺbiť si znalosti dynamickej alokácie pamäte.
  • Naučiť sa pracovať s binárnymi súbormi.
  • Smerníková aritmetika
  • Zoznámiť sa s grafickým formátom BMP a s jeho štruktúrou.
  • Porozumieť malému a veľkému endiánu.
  • Naučiť sa pracovať s dátami kódovanými pomocou Base64.

Grafický formát BMP

BMP (BitMaP) je jednoduchý bezstratový formát pre ukladanie obrázkov. Je tu s nami už vyše 30 rokov (bol vytvorený okolo roku 1987) a v súčasnosti je už samozrejme prekonaný a nahradený inými formátmi. Počas svojej existencie sa dočkal 5 verzií a umožňuje ukladanie obrázkov ako v komprimovanej tak aj nekomprimovanej podobe. Bol veľmi obľúbený a používaný hlavne v OS Windows, nakoľko vznikol ako produkt spoločností IBM a Microsoft. Jedná sa o formát, ktorý bol síce veľmi často používaný, ale pritom medzi používateľmi veľmi nepopulárny, pretože dokázal niektoré obrázky tak skomprimovať, že boli po komprimácii väčšie ako pred ňou.

Súbor s obrázkom v tomto formáte pozostáva:

  • z hlavičky, ktorá obsahuje metadáta, ako napr. veľkosť súboru, rozmery
  • a z obrazových údajov, teda pixelov.

Vašou úlohou bude tentokrát vytvoriť program, ktorý bude vedieť pracovať s grafickým formátom BMP - bude vedieť načítavať a ukladať súbory tohto typu a vykonávať s nimi niekoľko transformácií. Konkrétne vytvoríte

  • modul BMP, v ktorom načítate a uložíte súbor vo formáte BMP,
  • modul transformations, v ktorom implementujete jednotlivé transformácie so súborom, a
  • súbor main.c, ktorý na základe parametrov príkazového riadku vykoná príslušné oprácie so súborom.

Podrobné informácie o formáte a jeho štruktúre nájdete napr. na Wikipedii alebo v seriáli na stránkach serveru root.cz. V tomto zadaní budete pracovať s 24-bitovou farebnou hĺbkou. To znamená, že pre vyjadrenie farby každého pixelu sú použité 3B. Hlavičku súboru nájdete zadefinovanú v hlavičkovom súbore bmp.h.

Base64

Grafický formát BMP je binárnym formátom. Keďže chceme binárne údaje reprezentovať zrozumiteľne vo výsledkoch Arény, budú kódované pomocou formátu Base64. Z takto zakódovaných údajov si môžete kedykoľvek vytvoriť pôvodný súbor pomocou nástroja base64. Napr. ak je stream v Aréne reprezentovaný takto:

FILE* stream = "Qk1WAAAAAAAAADYAAAAoAAAAAgAAAAQAAAABABgAAAAAACAAAAAjLgAAIy4AAAAAAAAAAAAA////AAAAAAD/AAAA/wAAAAD/AAAA/wAAAAAA/wAAAAA="; // base64 encoded stream

Vytvoriť z neho spätne súbor môžete týmto príkazom:

$ echo "Qk1WAAAAAAAAADYAAAAoAAAAAgAAAAQAAAABABgAAAAAACAAAAAjLgAAIy4AAAAAAAAAAAAA////AAAAAAD/AAAA/wAAAAD/AAAA/wAAAAAA/wAAAAA=" | base64 -d > file.bmp

Následne môžete pracovať so súborom, nad ktorým testy prebiehali.

Modul BMP

Tento modul obsahuje základné funkcie na načítanie/uloženie grafického formátu BMP zo/do súboru, ako aj štruktúrované typy, pomocou ktorých grafický formát BMP bude reprezentovaný.

Štruktúra bmp_header

Táto štruktúra reprezentuje hlavičku grafického formátu BMP. V pamäti zaberá 54 bytov. Význam jednotlivých položiek štruktúry ako aj ich prípustné hodnoty sa nachádzajú v hlavičkovom súbore bmp.h.

Štruktúra pixel

Štruktúra obsahuje tri položky reprezentujúce jeden pixel ako kombináciu farieb červená, zelená a modrá. Každá z nich má veľkosť 8 bitov, čo znamená, že jeden pixel bude reprezentovaný 24 bitmi.

Štruktúrovaný údajový typ struct bmp_image

Táto štruktúra reprezentuje BMP obrázok ako celok, ktorý sa skladá z

  • hlavičky (položka .header), a z
  • postupnosti pixelov (položka .data).

Dáta, a teda postupnosť pixelov, je reprezentovaná ako jednorozmerné pole pixelov, ktoré sú lineárne uložené v pamäti za sebou. To znamená, že počet prvkov tohto poľa je daný ako súčin výšky so šírkou obrázka.

Úloha #1: Načítanie BMP obrázku zo vstupného prúdu

Pre načítanie BMP súboru či už zo súboru alebo štandardného vstupu, bude potrebné použiť kompozíciu viacerých funkcií:

  1. Funkciu read_bmp_header(), ktorá načíta hlavičku BMP súboru. Hlavička sa nachádza na začiatku prúdu. Pri načítavaní sa musí v položke type nachádzať hodnota BM.
  2. Funkciu read_data(), ktorá načíta postupnosť pixelov reprezentujúcich obsah súboru.
  3. Funkciu read_bmp(), ktorá vráti referenciu na načítaný kompletný obrázok pozostávajúci z hlavičky a z dát.

V prípade, že prúd nebude otvorený (bude mať hodnotu NULL) alebo referencia na hlavičku nebude platná (bude mať hodnotu NULL), funkcia taktiež vráti hodnotu NULL.

V prípade, že funkcia read_bmp() nenačíta hlavičku, okrem toho, že vráti hodnotu NULL vypíše na štandardný chybový výstup správu:

Error: This is not a BMP file.

V prípade, že funkcia hlavičku síce načíta v poriadku, ale dáta nie, vráti hodnotu NULL a vypíše na štandardný chybový výstup správu:

Error: Corrupted BMP file.

Úloha #2: Zápis BMP súboru do výstupného prúdu

Pre zapísanie grafického formátu BMP do súboru vytvorte funkciu write_bmp(). V prípade, že zápis prebehne v poriadku, vráti hodnotu true, v opačnom prípade vráti hodnotu false.

Úloha #3: Uvoľnenie pamäte

Vytvorte funkciu free_bmp_image(), ktorý uvoľní obsadenú pamäť vyhradenú pre uchovanie BMP obrázku v pamäti.

Modul Transformations

V tomto module budú riešené základné úpravy obrázkov. Cieľom je podľa vzorového obrázka definovaného na vstupe vytvoriť nový, ktorý vznikne aplikáciou úprav.

Úloha #4: Horizontálne a vertikálne preklopenie obrázka

Vašou úlohou je vytvoriť dvojicu funkcií flip_horizontally() a flip_vertically(), ktoré obrázok horizontálne alebo vertikálne preklopia. Táto operácia vytvára zrkadlový obraz pôvodného obrázku podľa osi preklápania. Rozmery obrázku zostávajú po preklopení nezmenené.

Nasledujúca tabuľka ilustruje, ako bude vyzerať preklopený pôvodný obrázok pri volaní jednotlivých funkcií.

pôvodný obrázok flip_horizontally() flip_vertically()
originálny obrázok horizontálne preklopený obrázok vertikálne preklopený obrázok

Parametrom oboch funkcií je referencia na obrázok:

  • const struct bmp_image* image - Odkaz na štruktúru, ktorá predstavuje vzorový obrázok.

Funkcie vytvárajú nový obrázok, ktorý vznikne preklopením pôvodného. V prípade, že funkcia na vstupe dostane miesto odkazu na obrázok hodnotu NULL, funkcia hodnotu NULL aj vráti.

Výstupy funkcií sú ilustrované na nasledujúcich príkladoch:

flip_horizontally()

source image             new  image
+--------+--------+      +--------+--------+
| FF0000 | FFFFFF |  ->  | FFFFFF | FF0000 |
+--------+--------+      +--------+--------+
flip_vertically()

source image            new image
+--------+              +--------+
| 000000 |              | FFFFFF |
+--------+      ->      +--------+
| FFFFFF |              | 000000 |
+--------+              +--------+

Úloha #5: Otočenie obrázku o 90° vpravo a vľavo

Vašou úlohou je vytvoriť dvojicu funkcií rotate_right() a rotate_left(), ktoré vytvoria kópiu pôvodného obrázku otočeného o 90° vpravo alebo vľavo. Rozmery obrázku sa v tomto prípade vymenia.

Nasledujúca tabuľka ilustruje, ako bude vyzerať otočenie pôvodného obrázku pri volaní jednotlivých funkcií.

pôvodný obrázok rotate_right() rotate_left()
originálny obrázok obrázok otočený doprava obrázok otočený doľava

Parametrom oboch funkcií je referencia na obrázok:

  • const struct bmp_image* image - Odkaz na štruktúru, ktorá predstavuje vzorový obrázok.

Funkcie vytvárajú nový obrázok, ktorý vznikne preklopením pôvodného. V prípade, že funkcia na vstupe dostane miesto odkazu na obrázok hodnotu NULL, funkcia hodnotu NULL aj vráti.

Úloha #6: Vystrihnutie časti obrázka

Vašou úlohou je vytvoriť funkciu crop(), pomocou ktorej vystrihnete časť pôvodného obrázka. Túto časť funkcia vráti ako nový obrázok.

Funkcia má niekoľko parametrov:

  • image - referencia na obrázok, z ktorého časť chceme vystrihnúť
  • start_y - y-ová pozícia ľavého horného bodu na vystrihnutie
  • start_x - x-ová pozícia ľavého horného bodu na vystrihnutie
  • height - výška vystrihovaného obrázka v pixloch
  • width - šírka vystrihovaného obrázka v pixloch

Vystrihovaný obrázok sa musí nachádzať vo vnútri pôvodného obrázku a jeho veľkosť môže byť min 1x1.

Funkcia vráti nový obrázok, ktorý vznikne vystrihnutím obrázka o šírke danej parametrom width a výške danej parametrom height s počiatočným bodom na pozícii [start_y, start_x]. V prípade, že referencia na pôvodný obrázok neexistuje alebo sú jednotlivé parametre mimo rozsah, funkcia vráti hodnotu NULL.

Úloha #7: Zmena veľkosti obrázku

Vašou úlohou je vytvoriť funkciu scale(), ktorá proporcionálne zmenší alebo zväčší rozmer obrázku na základe mierky.

Funkcia má tieto parametre:

  • image - referencia na obrázok, ktorý má byť zmenšený/zväčšený
  • factor - mierka zväčšenia/zmenšenia, ktorá môže byť:
    • factor < 1 - obrázok bude zmenšený
    • factor = 1 - obrázok zostane bez zmien
    • factor > 1 - obrázok bude zväčšený

Novú šírku a výšku obrázka na základe zadanej hodnoty premennej factor vypočítate nasledovne:

\[ newwidth = width \cdot factor \]

\[ newheight = height \cdot factor \]

Výsledok zaokrúhlite pomocou funkcie round().

Pre určenie farby pixelu v novom obrázku, sa zvolí pixel z pôvodného obrázka, ktorý sa nachádza na podobnej pozícii. Medzi pozíciami pixelov v pôvodnom a novom obrázku platí nasledujúci vzťah (príklad pre pozíciu na osi x):

\[ \frac{newx}{newwidth} = \frac{x}{width} \]

Uveďme si teda príklad: nech pôvodná šírka obrázka je 3 a faktor má hodnotu 2.3. Novú šírku vypočítame takto:

\[ newwidth = width \cdot factor = 3 \cdot 2.3 = 6.9 \]

Po zaokrúhlení bude hodnota novej šírky 7.

Vzťah medzi pixlom v novom a starom obrázku je zobrazený v nasledujúcej tabuľke a na nasledujúcom obrázku.

newx medzivýsledok x
0 0 0
1 0.43 0
2 0.86 0
3 1.29 1
4 1.71 1
5 2.14 2
6 2.57 2
Príklad zmeny mierky

Funkcia vráti nový obrázok, ktorý vznikne zväčšením/zmenšením pôvodného obrázku na základe danej mierky. V prípade, že referencia na pôvodný obrázok neexistuje alebo sú jednotlivé parametre mimo rozsah, funkcia vráti hodnotu NULL.

Úloha #8: Výber farebnej zložky

Vašou úlohou je vytvoriť funkciu extract(), ktorá z pôvodného obrázku vytvorí jeho kópiu a tá bude obsahovať len zvolené farebné zložky pôvodných pixlov. To znamená, že ak sa bude extrakcia týkať červenej farby, vo výslednom obrázku sa nebudú v pixloch nachádzať zložky zelenej a modrej farby.

// extract red and blue colors
// pixel in the form of RRGGBB

source image             extracted image
+--------+--------+      +--------+--------+
| 112233 | FFFFFF |  ->  | 110033 | FF00FF |
+--------+--------+      +--------+--------+

Funkcia má tieto parametre:

  • image - referencia na zdrojový obrázok
  • colors_to_keep - reťazec, ktorý môže byť zložený len zo znakov r, g a b vzhľadom na to, ktorú farbu chcete z obrázku extrahovať; na poradí znakov v reťazci nezáleží!

Funkcia vráti nový obrázok, ktorý vznikne extrahovaním vybraných farebných zložiek z pôvodného obrázku. V prípade, že referencia na pôvodný obrázok alebo reťazec na výber farebnej zložky neexistuje alebo tento reťazec obsahuje iné znaky, ako sú dovolené, funkcia vráti hodnotu NULL.

Parametre príkazového riadku

Výstupom vášho riešenia bude spustiteľný program s názvom bmp, ktorý bude vykonávať transformácie nad BMP súbormi. Jednotlivé operácie budú vykonané na základe použitých prepínačov.

V nasledovnom výpise je uvedený príklad použitia, kedy dôjde k otočeniu vpravo obrázku saboteur.bmp a výstup bude uložený do súboru output.bmp:

$ bmp -i saboteur.bmp -o output.bmp -r

Použitie príkazu

Usage: bmp [OPTION]... [FILE]...
Simple BMP transformation tool.

With no FILE, read from standard input or write to standard output.

  -r            rotate image right
  -l            rotate image left
  -h            flip image horizontally
  -v            flip image vertically
  -c y,x,h,w    crop image from position [y,x] of giwen height and widht
  -s factor     scale image by factor
  -e string     extract colors
  -o file       write output to file 
  -i file       read input from the file    

Zreťazenie

Uvedenie vstupného a výstupného súboru nie je povinné. Ak nie je uvedený názov vstupného súboru, bude použitý štandardný vstupný kanál (stdin). Ak nie je uvedený názov výstupného súboru, bude použitý štandardný výstupný kanál (stdout). To umožní zreťaziť výstup jedného príkazu so vstupom ďalšieho príkazu pomocou rúr (z angl. pipe).

Táto funkcionalita je ilustrovaná na nasledujúcom príklade, kde je je vstupom obrázok s názvom saboteur.bmp, ten je otočený vpravo, následne otočený naspäť vľavo a uložený do súboru output.bmp. Každá operácia je oddelená pomocou rúry:

$ bmp -i saboteur.bmp | bmp -r | bmp -l | bmp -o output.bmp

Odovzdávanie projektu

Zadanie sa odovzdáva prostredníctvom systému na správu verzií Git na serveri git.kpi.fei.tuke.sk. Riešenie tejto úlohy odovzdáte ako súčasť vášho projektu s názvom prog-2021.

Štruktúra vášho projektu bude vyzerať nasledovne:

.
├── ps4/
│   ├── bmp.c
│   ├── bmp.h
│   ├── main.c
│   ├── Makefile
│   ├── transformations.c
│   └── transformations.h
└── README

kde význam súborov v priečinku ps4/ je nasledovný:

  • bmp.c, bmp.h - Zdrojový kód a hlavičkový súbor modulu BMP.
  • transformations.c, transformations.h - Zdrojový kód a hlavičkový súbor modulu Transformations.
  • main.c - Zdrojový kód obsahujúci funkciu main().
  • Makefile - Makefile súbor bude obsahovať minimálne tieto ciele:
    • bmp.o pre vygenerovanie modulu BMP,
    • transformations.o pre vygenerovanie modulu Transformations,
    • all pre vygenerovanie spustiteľného programu s menom bmp, a
    • clean pre odstránenie priebežne vytvorených objektových a spustiteľných súborov.

Do súboru README, ktorý sa nachádza priamo v priečinku prog-2021/, uveďte označenie vašej skupiny, ktorú navštevujete na cvičeniach (zistíte si ju na rozvrhovom portáli maisu) v tvare:

GROUP : X1

Ak ste opakujúci študent, uveďte v README skupinu v tvare:

GROUP : O<P>

kde <P> nahradíte písmenom paralelky, ktorá podľa rozvrhu zodpovedá vášmu študijnému programu (napr. A pre informatikov).

Kostra projektu

Z nasledujúceho odkazu si stiahnite súbor bmp.zip, ktorý obsahuje kostru projektu spolu s ukážkovými obrázkami vo formáte BMP, s ktorými môžete experimentovať. Tento balíček obsahuje nasledujúce súbory a priečinky:

  • bmp.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre modul BMP.
  • transformations.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre modul Transformations.
  • assets/ - priečinok s obrázkami vo formáte BMP, s ktorými môžete experimentovať

V prostredí OS Linux môžete pre stiahnutie použiť príkaz wget v tvare:

wget https://kurzy.kpi.fei.tuke.sk/pvjc/2021/download/bmp.zip

Hodnotenie a testovanie

Vaše hodnotenie sa bude odvíjať od výsledku testov, ktorými vaše zadanie úspešne prejde. Overovať sa bude:

  • Štruktúra vášho projektu (či sa v ňom nachádzajú všetky potrebné súbory).
  • Statická analýza vášho kódu pomocou nástroja cppcheck.
  • Kontrola únikov v pamäti pomocou nástroja valgrind
  • Prítomnosť globálnych premenných vo vašom kóde.
  • Funkčnosť vašej implementácie.

Váš kód sa bude prekladať prekladačom gcc s nasledovnými prepínačmi a knižnicami:

$ gcc -std=c11 -Werror -Wall -lm

Testovanie vašich riešení sa bude vykonávať automaticky každé 2 hodiny.

Vaše riešenia opäť prejdú kontrolou originality. Preto sa pri práci na vašom zadaní správajte podľa pravidiel etického kódexu! V prípade, že odovzdáte zadanie, ktoré nie je vaše, budete vylúčení z predmetu!