FAKULTA INFORMAČNÍCH TECHNOLOGIÍ

ˇ ´ UCEN Í TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA INFORMACN ˇ ÍTACOV ˇ ´ ´ Í USTAV POC E´ GRAFIKY A MULTIMEDI FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA

´ SLUZBA ˇ WEBOVA - OBRAZOVE´ MOZAIKY

ˇ ´ BAKALA´ RSK A´ PRACE BACHELOR’S THESIS

´ AUTOR PRACE AUTHOR

BRNO 2009

ˇ VOJTECH BEIL

ˇ Í TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA INFORMACN ˇ ÍTACOV ˇ ´ ´ Í USTAV POC E´ GRAFIKY A MULTIMEDI FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA

´ SLUZBA ˇ WEBOVA - OBRAZOVE´ MOZAIKY WEB SERVICE - IMAGE MOSAICS

ˇ ´ BAKALA´ RSK A´ PRACE BACHELOR’S THESIS

´ AUTOR PRACE

ˇ VOJTECH BEIL

AUTHOR

´ VEDOUCÍ PRACE SUPERVISOR

BRNO 2009

ˇ Ing. MIROSLAV SVUB

Abstrakt Tato práce se zab´ yvá vytvoˇren´ım obrázkové mozaiky – tedy obrázku, kter´ y je sloˇzen z dalˇs´ıch tak, aby se z dálky jevil jako obrázek jin´ y. Dále se práce zab´ yv´ a moˇznost´ı pˇrenesen´ı takovéto programu jako webovou sluˇzbu.

Kl´ıˇ cov´ a slova mozaika, obrazová mozaika, JPEG, PNG, datov´ a struktura, knihovna, dynamicky linkovaná knihovna, DLL, C#, .NET, ASP.NET, sluˇzba, webov´ a sluˇzba, monitorov´ an´ı sluˇzby, datab´ aze, relaˇcn´ı databáze, SQL

Abstract This work describes creating mosaic images – images that from distace look like another image. It also explores posibility transfering that program as web service.

Keywords mosaic, images mosaics, JPEG, PNG, data structure, library, dynamic-link library, DLL, C#, .NET, ASP.NET, service, web service, service monitoring, database, relational database, SQL

Citace Vojtˇech Beil: Webová sluˇzba - obrazové mozaiky, bakal´ aˇrsk´ a práce, Brno, FIT VUT v Brnˇe, 2009

Webov´ a sluˇ zba - obrazov´ e mozaiky Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto bakaláˇrskou práci vypracoval samostatnˇe pod veden´ım pana Ing. Miˇ roslava Svuba Uvedl jsem vˇsechny literárn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal. ....................... Vojtˇech Beil 21. ledna 2009

c Vojtˇech Beil, 2009. ° Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysokém uˇcen´ı technickém v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorským z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonné, s výjimkou z´ akonem definovaných pˇr´ıpad˚ u.

Obsah ´ 1 Uvod

3

2 Teorie 2.1 Co je to obraz . . . . . . . . . . . . . 2.2 Manipulace obrazu . . . . . . . . . . 2.2.1 Zmenˇsen´ı, zvˇetˇsen´ı . . . . . . 2.3 Barevn´ y RGB model . . . . . . . . . 2.4 Podobnost dvou obraz˚ u . . . . . . . 2.4.1 Moˇznosti porovnán´ı . . . . . 2.4.2 Pr˚ umˇerná barva . . . . . . . 2.4.3 Nalezen´ı vhodn´ ych kandid´ at˚ u 2.5 Algoritmus . . . . . . . . . . . . . . 2.6 Webová sluˇzba . . . . . . . . . . . . 2.6.1 Rozdˇelen´ı webové sluˇzby . . . 2.7 Technologie . . . . . . . . . . . . . . 2.7.1 C# . . . . . . . . . . . . . . 2.7.2 .NET . . . . . . . . . . . . . 2.7.3 ASP.NET . . . . . . . . . . . 2.7.4 Relaˇcn´ı databáze, SQL . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

4 4 4 5 5 6 6 7 7 7 8 9 10 10 11 12 12

3 N´ avrh 3.1 Framework . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Seznam . . . . . . . . . . . . . . . . . . . . 3.1.2 Hash tabulka . . . . . . . . . . . . . . . . . 3.1.3 Seˇrazené pole . . . . . . . . . . . . . . . . . 3.2 Knihovny . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Dynamicky linkované knihovny . . . . . . . 3.2.2 Extern´ı knihovny . . . . . . . . . . . . . . . 3.3 Vyhledávac´ı sluˇzby . . . . . . . . . . . . . . . . . . 3.4 Knihovna pro vytvoˇren´ı mozaiky . . . . . . . . . . 3.5 Optimalizace rychlosti . . . . . . . . . . . . . . . . 3.5.1 Trojrozmˇern´ y hash . . . . . . . . . . . . . . 3.5.2 Pouˇzit´ı seˇrazeného pole s omezenou délkou 3.6 Optimalizace vyuˇzit´ı pamˇeti . . . . . . . . . . . . . 3.6.1 Droben´ı alokované pamˇeti . . . . . . . . . . 3.6.2 Vyuˇzit´ı hash tabulky . . . . . . . . . . . . . 3.7 C# tˇr´ıda . . . . . . . . . . . . . . . . . . . . . . . 3.8 Formatter . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

13 15 15 15 15 16 16 16 17 17 18 18 18 18 18 19 20 20

1

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

3.9

3.8.1 Návrh . . . . . . . . . . . 3.8.2 Konstrukce objektu . . . 3.8.3 Naˇcten´ı, uloˇzen´ı . . . . . 3.8.4 Moˇzná rozˇs´ıˇren´ı, pouˇzit´ı . Webová sluˇzba . . . . . . . . . . 3.9.1 ER diagram . . . . . . . . 3.9.2 Knihovna pro komunikaci 3.9.3 Uˇzivatelské rozhrann´ı . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

20 21 21 21 22 23 24 24

4 Implementace 4.1 Barevn´ y model, barevná hloubka . . . . 4.2 Optimalizace ukládán´ı obrázku . . . . . 4.3 Optimalizace alokace pamˇeti obrázku . . 4.4 Obrázky a vyrovnávac´ı pamˇet’ . . . . . . 4.5 Pouˇzité v´ yvojové nástroje . . . . . . . . 4.5.1 Visual Studio 2005 . . . . . . . . 4.5.2 SQL Server Management Studio 4.6 Pouˇzité technologie . . . . . . . . . . . . 4.7 Webová sluˇzba . . . . . . . . . . . . . . 4.7.1 Monitorován´ı sluˇzby . . . . . . . 4.8 Stahován´ı obrázk˚ u . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

26 26 26 26 27 27 27 28 28 28 29 29

5 V´ ysledky 5.1 Popis programu pro pˇr´ıkazovou ˇr´ adku 5.2 Popis webové sluˇzby . . . . . . . . . . 5.3 Ukázky v´ ystup˚ u . . . . . . . . . . . . 5.4 ASCII art . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

31 32 32 32 32

. . . . . . . . . .

36 36 36 36 36 37 37 37 37 38 39

. . . .

6 Z´ avˇ er 6.1 Moˇzná rozˇs´ıˇren´ı . . . . . . . . . . . . . . . . . 6.1.1 Podpora dalˇs´ıch grafick´ ych formát˚ u . 6.1.2 Pouˇzit´ı velk´ ych fotografi´ı a jejich ˇc´ ast´ı 6.1.3 Sd´ılen´ı pamˇeti . . . . . . . . . . . . . 6.1.4 Hash obrázk˚ u . . . . . . . . . . . . . . 6.1.5 Rozestavˇen´ı obrázk˚ u . . . . . . . . . . 6.1.6 Grafické uˇzivatelské rozhran´ı . . . . . 6.1.7 Zobrazen´ı velk´ ych obrázk˚ u online . . . 6.1.8 Rozˇs´ıˇren´ı webové sluˇzby . . . . . . . . 6.2 Závˇer . . . . . . . . . . . . . . . . . . . . . .

2

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

Kapitola 1

´ Uvod C´ılem této bakaláˇrské práce je vytvoˇrit aplikaci, která ze zadaného vstupn´ıho obrázku vytvoˇr´ı tzv. obrázkovou mozaiku, coˇz je obraz sloˇzen´ y z mnoha mal´ ych obrázk˚ u, pˇriˇcemˇz z dostateˇcné vzdálenosti je jej´ı jako celek. Kapitola Teorie pojednává a shrnuje pouˇzité postupy, technologie a algoritmy. Dalˇs´ı kapitola se zab´ yvá návrhem aplikace. Obsahuje návrh aplikace a poskytuje základn´ı pohled na jednotlivé ˇcásti systému. Navrhuje ideáln´ı pouˇzit´ı konkrétn´ıch algoritm˚ u a technologi´ı. Obsahuje téˇz popis, návrh a anal´ yzu webové sluˇzby. Zab´ yv´ a se komunikac´ı jednotliv´ ych ˇcást´ı vˇcetnˇe vytváˇren´ı knihoven, které mohou b´ yt vyuˇzity zvláˇst’ a které jsou pak dále pouˇz´ıvány dále v projektu. Zab´ yv´ a se téˇz pˇrenosem dat mezi základn´ımi stavebn´ımi kameny aplikace. Implementaˇcn´ı kapitola se zab´ yv´ a konkrétnˇe pouˇzit´ ymi postupy, algoritmy, pouˇzit´ım konkrétn´ıch datov´ ych struktur. Také obsahuje v´ yˇcet pouˇzit´ ych technologi´ı, program˚ u a v´ yvojov´ ych nástroj˚ u a jejich verz´ı. Pátá kapitola nadepsaná V´ ysledky“ ukazuje nˇekteré konkrétn´ı v´ ysledky práce. Ob” sahuje hlavnˇe ukázky obrázk˚ u a webového rozhran´ı. Posledn´ı závˇereˇcná kapitola shrnuje v´ ysledky bakal´ aˇrské práce. Velk´ a ˇc´ ast kapitoly je vˇenována zamyˇslen´ım nad dalˇs´ımi moˇzn´ ymi rozˇs´ıˇren´ımi. Samotn´ y závˇer shrnuje vlastn´ı postup pˇri vypracováván´ı, nastiˇ nuje nˇekter´ a technologick´ a rozhodnut´ı a zmiˇ nuje nejzaj´ımavˇejˇs´ı ˇcásti práce.

Obrázek 1.1: Pˇr´ıklad v´ ystupu bakal´ aˇrské práce

3

Kapitola 2

Teorie 2.1

Co je to obraz

Obraz je grafické vyjádˇren´ı, které se podobá nˇejakému pˇredmˇetu, fyzickému objektu ˇci osobˇe. Dvourozmˇerné vyjádˇren´ı m˚ uˇze b´ yt fotografie, obrazovka, plátno v kinˇe. Trojrozmˇerné vyjádˇren´ı je napˇr. socha, architektonické d´ılo. Obraz (dvourozmˇern´ y) je vˇetˇsinou zachyt´ av´ an pomoc´ı optického zaˇr´ızen´ı (fotoaparát, dalekohled). Obraz m˚ uˇze b´ yt natisknut, namalov´ an ˇci nakreslen.

2.2

Manipulace obrazu

Pˇri manipilaci obrazu závis´ı na jeho vyjádˇren´ı. Obraz (dvourozmˇern´ y) m˚ uˇze b´ yt definov´ an vektory (vektorová grafika) nebo jednotliv´ ymi pixely (rastrov´ a grafika). Ve vektorové grafice se uchováv´ a pouze obraz uloˇzen´ ych objekt˚ u, zat´ım co u vektorové grafiky lze vlastnosti uloˇzen´ ych objekt˚ u mˇenit. V´ yhodou vektorové grafiky je zobrazen´ı objekt˚ u stále hladké, zvˇetˇsen´ı rastrové grafiky je diskrétn´ı (zubaté), chybˇej´ıc´ı informaci o obrazu nen´ı odkud ˇcerpat. Obrazem m˚ uˇzeme manipulovat nˇekolika základn´ımi zp˚ usoby: • Zmenˇsen´ı, zvˇetˇsen´ı • Oˇrez obrazu • Rotace obrazu, otoˇcen´ı podle osy • Zkosen´ı, jiná transformace • Rozmazán´ı Dále pak s obrazem m˚ uˇzeme prov´ adˇet dalˇs´ı pokroˇcilé operace, napˇr. hledán´ı hran, OCR (Optical character recognition - rozpoznáv´ an´ı text˚ u), zmˇena barev a dalˇs´ı.

4

2.2.1

Zmenˇ sen´ı, zvˇ etˇ sen´ı

Pˇri zmˇenˇe velikosti obrazu máme k dispozici nˇekolik metod, napˇr (zdroj [12]): • interpolace nejbliˇzˇs´ım sousedem • bilineárn´ı interpolace • bikubická intepolace Bilineárn´ı interpolace vyuˇz´ıv´ a lineárn´ı interpolaci ve dvou osách. Pro v´ ypoˇcet jednoho bodu ve v´ ysledném obrázku je potˇreba znát barvy ˇctyˇr okoln´ıch pixel˚ u. Bikubická interpolace vyuˇz´ıv´ a polynomiáln´ı interpolaci tˇret´ıho stupnˇe. V´ ypoˇcet se provád´ı pomoc´ı kubického polynomu. Pro dvojrozmˇern´ y rast je pro spoˇc´ıt´ an´ı potˇreba znát ˇsestnáct pixel˚ u.

Originál

Nejbližší soused

Bilineární interpolace

Bikubická interpolace

Obrázek 2.1: Porovn´ an´ı interpolaˇcn´ıch metod

2.3

Barevn´ y RGB model zelená

červená

modrá

Obrázek 2.2: Pláˇst’ a model RGB krychle

5

barva ˇcervená ˇzlutá zelená azurová modrá fialová b´ılá ˇcerná

100 100 0 0 0 100 100 0

R % % % % % % % %

0 100 100 100 0 0 100 0

G % % % % % % % %

0 0 0 100 100 100 100 0

B % % % % % % % %

vlnov´ a délka 650 550 490 455 430 360

(nm) - 760 - 590 - 760 - 490 - 455 - 430

Tabulka 2.1: Barvy, intenzity sloˇzek a vlnov´ a délka ([13]) Barevn´ y RGB (Red – ˇcerven´ a, Green – zelená, Blue – modrá) model je aditivn´ı zp˚ usob m´ıchán´ı barev. Jde o m´ıchán´ı vyzaˇrovaného svˇetla. Nepotˇrebuje vnˇejˇs´ı svˇeteln´ y zdroj a zobrazuje tedy i ve tmˇe. Aditivn´ı zp˚ usob m´ıchán´ı barev je zp˚ usob, ve kterém se jednotlivé sloˇzky sˇc´ıtaj´ı a vytváˇr´ı svˇetlo vyˇsˇs´ı intenzity. Na obrázku 2.2 je zobrazen pláˇst’ RGB krychle (a). Pláˇst’, kde kaˇzd´ a prostorov´ a osa pˇredstavuje intenzitu jedné barevné sloˇzky v bodˇe [0, 0, 0] je barva ˇcern´ a, v bodˇe [1, 1, 1] b´ıl´ a. Prom´ıtnut´ı krychle do prostoru (b) zobrazuje model krychle, kde bod [0, 0, 0] je neviditeln´ y. Na tomto obrázku jsou naznaˇceny osy.

2.4 2.4.1

Podobnost dvou obraz˚ u Moˇ znosti porovn´ an´ı

Porovnán´ı dvou obrázk˚ u, zda se jedná o totoˇzné ˇci podobné, m˚ uˇze b´ yt obt´ıˇzné s pˇrihlédnut´ım k JPEG kompresi, zmˇenˇe velikosti, moˇznosti pˇrid´ an´ı nebo odstranˇen´ı okraj˚ u ˇci pˇrid´ an´ı textu ˇci loga k okraj˚ um obrázk˚ u (zdroj [11]). Techniky moˇzné k pouˇzit´ı k nalezen´ı podobn´ ych obrázk˚ u: • Hledán´ı podle barvy: pˇri hledán´ı je vhodné nalézt a odstranit zbyteˇcné okraje, sn´ıˇzit poˇcet barev v obrázku, pouˇzit´ı histogramu k identifikov´ an´ı nˇekolika barev ˇci barevn´ ych v´ yznamn´ ych region˚ u, podle kter´ ych se bude porovn´ avat podobnost dvou obraz˚ u. • Podle barevnosti ˇcást´ı: porovn´ a se pr˚ umˇern´ a barva nˇekolika (nebo vˇsech) ˇc´ ast´ı obrázku. • Nalezen´ı hran: Obrázky se zmenˇs´ı na stejnou velikost, provede se detekce hran a naleznou se kˇrivek. Poté se porovnaj´ı kˇrivky podle bl´ızkosti a podobnosti (napˇr. podle polohy, smˇeru, zakˇriven´ı, u ´hlu). • Provést rychlou Fourierovu transformaci (na ˇc´ asti obrázk˚ u) a porovnat podobnost (nˇekolika prvn´ıch) koeficient˚ u.

6

2.4.2

Pr˚ umˇ ern´ a barva

Pro urˇcen´ı pr˚ umˇerné barvy obrazu je pouˇzit vzorec: Pro obraz o rozmˇerech x × y s body (Rij , Gij , Bij ), kde Rij je intenzita ˇcervené sloˇzky (Gij , Bij zelené a modré) je pouˇzit vzorec:   y y y x X x X x X X X X 1  (δR , δG , δB ) = Rij , Gij , Bij  (2.1) x·y i=1 j=1

2.4.3

i=1 j=1

i=1 j=1

Nalezen´ı vhodn´ ych kandid´ at˚ u

Podobnost dvou obrázk˚ u s pr˚ umˇern´ ymi barvami α = (αR , αG , αB ) a β = (βR , βG , βB ) je dána rozd´ılem jejich pr˚ umˇern´ ych barev: p = (αR − βR )2 + (αG − βG )2 + (αB − βB )2

(2.2)

´ Ukolem algoritmu je nalézt pro vstupn´ı ˇctverec α takov´ y β, aby bylo toto ˇc´ıslo minimáln´ı.

2.5

Algoritmus Všechny obrázky (a)

(b)

Obrázek, ke kterému se vyhledává v databázi podobný

(c)

Nalezený obrázek

Obrázek 2.3: Základn´ı princip funkce algoritmu Pro vytvoˇren´ı mozaiky je d˚ uleˇzité, aby z vˇetˇs´ı vzdálenosti se podobala co nejbl´ıˇze p˚ uvodn´ı pˇredloze. V´ ysledn´ y obrázek by mˇel co nejbl´ıˇze zachovat p˚ uvodn´ı rozloˇzen´ı, p˚ uvodn´ı barevnost a v´ ybˇer mozaikov´ ych vloˇzen´ ych obrázk˚ u by se mˇel co nejv´ıce podobat pˇredloze. Základem algoritmu je pˇredpoklad, ˇze vstupn´ı obrázek se rozdˇel´ı do pravidelné (ˇctvercové) mˇr´ıˇzky o urˇcit´ ych rozmˇerech. K tˇemto vstupn´ım ˇctverc˚ um se pak pˇristupuje jednotlivˇe. Pro dan´ y ˇctverec se v databázi snaˇz´ı nalézt nejpodobnˇejˇs´ı obrázek, kter´ y by se nam´ısto vstupn´ıho ˇctverce vloˇzil. Nalezen´ y obrázek nemus´ı b´ yt vhodn´ ych rozmˇer˚ u a nemus´ı m´ıt vhodn´ y pomˇer stran. Vhodn´ y rozmˇer (velikost) lze odstranit zmenˇsen´ım nebo zvˇetˇsen´ım, nesprávn´ y pomˇer stran

7

oˇr´ıznut´ım (ˇci zmˇenou rozmˇer˚ u bez zachov´ an´ı pomˇeru stran). Dalˇs´ı moˇznost´ı jeˇstˇe m˚ uˇze b´ yt pokraˇcován´ı v hledán´ı a nalezen´ı obrázku, které také splˇ nuje velikostn´ı kritéria. Nejpˇresnˇejˇs´ı porovnán´ı dvou obraz˚ u (vstupn´ıho ˇctverce a hledaného obrázku) je pixel po pixelu, tato operace je ovˇsem velice nároˇcn´ a nehledˇe na poˇzadavky na vstupn´ı zaˇr´ızen´ı a pamˇet’. Protoˇze pro základn´ı nahrazen´ı je dostaˇcuj´ıc´ı nalézt pr˚ umˇernou barvu (vzorec 2.1) vstupn´ıho ˇctverce a nalézt nahrazuj´ıc´ı obrázek s pr˚ umˇernou barvou tak, aby rozd´ıl (vzorec 2.2) byl minimáln´ı. Pro zachován´ı hran a detail˚ u (protoˇze rozloˇzen´ı barev, hran a dalˇs´ıch informac´ı na obrázc´ıch m˚ uˇze b´ yt rozd´ılné a tud´ıˇz nalezen´ y obrázek nemus´ı zachov´ avat vˇernˇe pˇredlohu) m˚ uˇze b´ yt vstupn´ı ˇctverec rozdˇelen do dalˇs´ıch ˇctverc˚ u a pro jednotlivé ˇctverce v pˇredloze a v hledaném obrázku znovu provedeno hledán´ı. Obrázek 2.3 zobrazuje vlastn´ı fungov´ an´ı algoritmu. (a) Nejdˇr´ıve je nalezen seznam obrázk˚ u s podobnou pr˚ umˇernou barvou. Tyto obrázky jsou pak rozdˇeleny pravidelnou mˇr´ıˇzkou do menˇs´ıch ˇctverc˚ u (b) a podle pˇredlohy doch´ az´ı k porovn´ an´ı. T´ımto krokem je opˇet nalezen seznam kandidátn´ıch obrázk˚ u. Vˇsechny tyto informace lze pro urychlen´ı pˇrednaˇc´ıtat pˇredem z databáze. V posledn´ım bodˇe (c) je nalezen omezen´ y poˇcet kandid´ at˚ u, které se jiˇz podobaj´ı pˇredloze velmi bl´ızce, pro maximáln´ı pˇresnost nyn´ı doch´ az´ı k vlastn´ımu naˇcten´ı kandidátn´ıch obrázk˚ u a porovn´ an´ı pixel po pixelu. Nalezen´ y obrázek je pak vloˇzen do v´ ysledného obrázku na odpov´ıdaj´ıc´ı m´ısto.

2.6

Webov´ a sluˇ zba Klient

Server Prezentační služba

Klient

Databáze Klient Vykonná služba

Obrázek 2.4: Rozdˇelen´ı aplikace na aplikaci typu klient/server Sluˇzba World Wide Web nab´ız´ı moˇznost prezentovat informace, databáze, v´ ysledky v´ ypoˇct˚ u ovlivnˇen´ ych uˇzivatelem nebo ˇc´ımkoliv jin´ ym. Existuje mnoho druh˚ u webov´ ych sluˇzeb od tˇech nejjednoduˇsˇs´ıch aˇz po komplexn´ı. Pˇr´ıkladem webové sluˇzby m˚ uˇze b´ yt zobrazen´ı náhodného ˇc´ısla ˇci zobrazen´ı statistik z´ıskan´ ych od mnoha milión˚ u zkouman´ ych objekt˚ u. Pro pouˇz´ıván´ı webov´ ych sluˇzeb je potˇreba internetov´ y prohl´ıˇzeˇc, kter´ y je jiˇz dnes ale standardem pro naprostou vˇetˇsinu uˇzivatelk´ ych poˇc´ıtaˇc˚ u. Internetové prohl´ıˇzeˇce podporuj´ıc´ı r˚ uzn´ ych stupeˇ n webov´ ych technologi´ı disponuje nyn´ı stále v´ıce mobiln´ıch zaˇr´ızen´ı (telefon˚ u, PDA, ...) Webová sluˇzba je sluˇzba typu klient-server (bl´ıˇze popsáno napˇr. [3]), kdy uˇzivatel pos´ıl´ a na server poˇzadavky, server poˇzadavek zpracuje a poˇsle klientovi odpovˇed’. Komunikaˇcn´ım protokolem m˚ uˇze b´ yt napˇr´ıklad HTTP (viz. [5]).

8

2.6.1

Rozdˇ elen´ı webov´ e sluˇ zby

Nˇekteré webové sluˇzby mohou poskytovat v´ ysledky uˇzivatelsk´ ych dotaz˚ u v reálném ˇcase jiné poˇzadavky mohou b´ yt natolik ˇcasovˇe nároˇcné (nebo v´ ysledek m˚ uˇze b´ yt závisl´ y na vnejˇs´ıch neovlivniteln´ ych okolnostech) tak, ˇze pouze zprostˇredkov´ avaj´ı zobrazen´ı informac´ı z´ıskan´ ych z napˇr. extern´ıho zdroje. Ve své bakaláˇrské práci jsem zvolil pouˇzit´ı webové sluˇzby, která je rozdˇelena na dvˇe ˇcásti – prezentaˇcn´ı a v´ ykonnou: 1. Prezentaˇcn´ı – prezentuje v´ ysledky ˇcinnosti v´ ykonné ˇc´ asti, zobrazuje seznam poˇzadavk˚ u a jejich stav˚ u, umoˇzn ˇuje pˇrid´ avat nové u ´lohy. 2. V´ ykonná – zpracovává frontu poˇzadavk˚ u, kv˚ uli zat´ıˇzen´ı serveru, m˚ uˇze zpracov´ avat sluˇzba pouze jeden poˇzadavek. 2.6.1.1

Uˇ zivatelsk´ e rozhrann´ı

K pˇr´ıstupu k webov´ ym sluˇzbám je pouˇz´ıv´ an internetov´ y prohl´ıˇzeˇc, kter´ y zajiˇst’uje základn´ı uˇzivatelské rozhran´ı. Prezentaˇcn´ım prostˇredkem je jazyk HTML. HTML (HyperText Markup Langage) je znaˇckovac´ı jazyk pouˇz´ıvan´ y pro web. Popisuje strukturu textov´ ych informac´ı v dokumentu – oznaˇcen´ım u ´sek˚ u textu jako napis, odkaz nebo jako odstavec. 2.6.1.2

Sluˇ zba

Sluˇzba je v prostˇred´ı Windows ekvivalentn´ı v´ yznamu démona z prostˇred´ı Unix. V multitaskovém operaˇcn´ım systému je program (proces), kter´ y bˇeˇz´ı na pozad´ı a prov´ ad´ı ˇcinnost. Sluˇzba je vˇetˇsinou nastartována pˇri startu poˇc´ıtaˇce. Sluˇzba m˚ uˇze vykon´ avat v´ ypoˇcet na pozad´ı, m˚ uˇze zpˇr´ıstupˇ novat zaˇr´ızen´ı, m˚ uˇze ˇcekat na vnˇejˇs´ı podmˇet a na ten reagovat. Jako sluˇzba m˚ uˇze b´ yt implementov´ an napˇr. internetov´ y server, kter´ y naslouch´ a na socketu a v pˇr´ıpadˇe poˇzadavku jej zpracuje a poˇsle odpovˇed’. 2.6.1.3

Komunikace

Komunikace mezi uˇzivatelsk´ ym rozhrann´ım a sluˇzbou je otázka meziprocesové komunikace. Uˇzivatelské rozhrann´ı i sluˇzba bˇeˇz´ıc´ı na pozad´ı jsou aplikace (procesy), které si potˇrebuj´ı vymˇen ˇovat data. Meziprocesová komunikace je sada technik pro v´ ymˇenu dat mezi dvˇema nebo v´ıce procesech. Techniky m˚ uˇzeme rozdˇelit na metody: • zas´ılán´ı zpráv • synchronizace • sd´ılená pamˇet’ • volán´ı vzdálen´ ych procedur Komunikace mezi procesy m˚ uˇze b´ yt téˇz provedena pomoc´ı sd´ılené databáze (pamˇeti), ke které maj´ı oba procesy pˇr´ıstup. Komunikace pak prob´ıh´ a t´ım, ˇze prvn´ı proces provede u ´pravu (zápis, aktualizaci, smazán´ı) databáze (´ uprava jednoho ˇci v´ıce ˇr´ adk˚ u nebo celé 9

Proces 1a Proces 2a Proces 1b

Databáze Proces 2b

Proces 1c

Obrázek 2.5: Meziprocesov´ a komunikace pomoc´ı (relaˇcn´ı) databáze tabulky), druh´ y proces pak v dan´ ych intervalech (na vyˇz´ ad´ an´ı uˇzivatele, po urˇcité ˇcasové dobˇe) sleduje, zda neprobˇehla zmˇena v tabulce. V´ yhodami tohoto ˇreˇsen´ı je pak jednoduchost implementace (mnoho informaˇcn´ıch systém˚ u pouˇz´ıvá jako zdroj dat databázi), komunikace mezi procesy je moˇzn´ a i v pˇr´ıpadˇe, kdy jeden proces nen´ı spuˇstˇen. Nev´ yhodou je potˇreba ˇcastého dotazov´ an´ı na databázi, zda nedoˇslo k nˇejaké zmˇenˇe.

2.7 2.7.1

Technologie C#

C# je vysoce u ´rovˇ nov´ y objektovˇe orientovan´ y programovac´ı jazyk vyvinut´ y firmou Microsoft spoleˇcnˇe s platformou .NET Framework. C# nab´ız´ı automatick´ y garbage collector. Garbage collector je ˇc´ ast bˇehového prostˇred´ı, která má za u ´kol automaticky urˇcit, která ˇc´ ast pamˇeti nen´ı uˇz pouˇz´ıvan´ a, a uvolnit ji pro dalˇs´ı znovupouˇzit´ı. Jazyk má objektovˇe orientovanou syntaxi zaloˇzenou na jazyce C++, ale je téˇz velmi ovlivnˇen jazykem Java. Prvn´ı verze jazyka C# 1.0 byla vydaná v roce 2002 spoleˇcnˇe s .NET frameworkem 1.0. Dalˇs´ı verze 2.0 byla vydána v roce 2005. Spoleˇcnˇe s .NET frameworkem 2.0 pˇrin´ aˇs´ı nové vlastnosti jako ˇcásteˇcné a statické tˇr´ıdy, iterátory, anonymn´ı metody, nullovatelné typy a operátor koalescence (operátor ?? – dva otazn´ıky). Aktuálnˇe posledn´ı verze 3.0 vyˇsla v roce 2007 spoleˇcnˇe s Frameworkem 3.5. Tato nov´ a verze pˇrináˇs´ı LINQ, pomoc´ı ˇcehoˇz se lze ptát na objekty reprezentuj´ıc´ı databáze. Dále tato nová verze pˇrináˇs´ı jednoduˇsˇs´ı lambda v´ yrazy, anonymn´ı tˇr´ıdy a dalˇs´ı nové vlastnosti. Tyto zmˇeny nevyˇzaduj´ı zmˇenu podkladového CIL, takˇze s poˇzadovan´ ymi knihovnami mohou bˇeˇzet i na pˇredchoz´ım frameworku 2.0. 2.7.1.1

Tˇ r´ıdy

V objektovˇe orientovaném programov´ an´ı je tˇr´ıda základem vytváˇren´ı objekt˚ u. Tˇr´ıda definuje vlastnosti a metody. Vlastnosti mohou odliˇsovat jednotlivé objekty. Tˇr´ıda je jak´ ysi bal´ıˇcek metadat obsahuj´ıc´ı pravidla, podle kter´ ych jsou tvoˇreny objekty a jak se objekty chovaj´ı. Objekty jsou naz´ yv´ any instancemi tˇr´ıd. Jazyk C# nab´ız´ı jednoduchou dˇediˇcnost.

10

2.7.1.2

Atributy

[FormatterTable("Keyword")] public class Keyword : Formatter { [FormatterAttribute("Name", FormatterAttribute.FormatterSqlType.SQL STRING)] public string Name; [FormatterAttribute("Description", FormatterAttribute.FormatterSqlType.SQL STRING)] public string Description;

public Keyword() { } } V jazyce C# je moˇzné urˇcit´ ym entit´ am pˇriˇradit znaˇcky“ (atributy) ke specifikov´ an´ı ” dodateˇcn´ ych informac´ı. Tyto informace mohou b´ yt pak za bˇehu z´ısk´ any pomoc´ı tzv. reflexion. Atributy jsou systémové i uˇzivatelské. Programátor m˚ uˇze definovat vlastn´ı a ty pouˇz´ıvat. Ukázka zápisu atribut˚ u je k dispozici v u ´seku zdrojového kódu uvedeného v´ yˇse. Atributy mohou b´ yt pouˇzity k r˚ uzn´ ym u ´ˇcel˚ um. Jednou z moˇznost´ı je propojen´ı kódu C# s dynamicky linkovanou knihovnou DLL (pomoc´ı atributu DllImport). Pomoc´ı atribut˚ u MarshalAs lze téˇz specifikovat, jak´ ym zp˚ usobem bude s parametry funkc´ı naklád´ ano pˇri volán´ı funkc´ı z extern´ıch DLL knihoven.

2.7.2

.NET

Microsoft .NET Framework je soubor technologi´ı v softwarov´ ych produktech, kter´ y je dostupn´ y pro web, Windows i Pocket PC. Framework pokr´ yvá mnoho potˇreb pro programov´ an´ı napˇr. uˇzivatelské rozhrann´ı, pˇr´ıstup k dat˚ um, pˇripojován´ı k databáz´ım, kryptografie, v´ yvoj pro web, numerické algoritmy a s´ıt’ovou komunikaci. Programy napsané pomoc´ı .NET frameworku jsou spouˇstˇeny v Common Language Runtime (CLR) (zdroj citemsdn:clr), na kterém bˇeˇz´ı zvláˇstn´ı druh bytek´ odu. Zdrojov´ y kód m˚ uˇze b´ yt psán v C#, Visual Basicu .NET ˇci dalˇs´ıch a bˇehem kompilace je zkompilován do CIL kódu (Common Intermediate Language). Pˇri bˇehu programu je CIL kódu pˇreveden do nativn´ıho kódu operaˇcn´ıho systému. Pro urychlen´ı m˚ uˇze b´ yt pro urychlen´ı zkompilován do nativn´ıho kódu pˇred samotn´ ym bˇehem ve zvláˇstn´ım kroku. Tato technika umoˇzn ˇuje programátor˚ um ignorovat specifika procesoru, na kterém program bˇeˇz´ı.

11

Common Language Runtime obsahuje téˇz: • správu pamˇeti, • správu vláken, • správu v´ yjimek • garbage collection • zabezpeˇcen´ı

2.7.3

ASP.NET

ASP.NET je souˇcást .NET frameworku pro v´ yvoj webov´ ych aplikac´ı a sluˇzeb. ASP.NET je nástupcem technologie Active Server Pages (ASP). Programátor pˇri vytváˇren´ı ASP.NET stránek m˚ uˇze vyuˇz´ıvat kter´ ykoliv jazyk podporuj´ıc´ı CLR (viz. v´ yˇse). V´ yhodou tohoto ˇreˇsen´ı je rychlost, protoˇze aplikace zaloˇzené na ASP.NET jsou pˇrekompilovány do DLL soubor˚ u (naproti skriptovac´ım jazyk˚ um, které pˇri kaˇzdém pˇr´ıstupu znovu parsovány). ASP.NET umoˇzn ˇuje oddˇelen´ı kódu od vzhledu – pro kód i algoritmickou ˇc´ ast webu (napˇr. práci s databáz´ı, odchycen´ı událost´ı) existuj´ı oddˇelené zdrojové soubory. Stránky jsou skládány z ovládac´ıch prvk˚ u podobn´ ych ovl´ adac´ım prvk˚ um ve Windows. Tˇemto prvk˚ um lze nastavovat urˇcité vlastnosti ˇci zachyt´ avat události. Tyto webové ovládac´ı prvky samy generuj´ı HTML, které se pak vklád´ a do v´ ysledného HTML kódu. Událostmi ˇr´ızené programován´ı vyˇzaduje zachov´ an´ı stavu, jenˇze webov´ y protokol je sám o sobˇe bezstavov´ y, proto se tento problém ˇreˇs´ı pomoc´ı HTML (a JavaScriptu) pomoc´ı dvou základn´ıch technik (zdroj [9]): • ViewState – informace se uchov´ avaj´ı mezi poˇzadavky ve skrytém formul´ aˇrovém poli. Nev´ yhodou tohoto ˇreˇsen´ı je, ˇze se mezi serverem a klientem m˚ uˇze pˇren´ aˇset velké mnoˇzstv´ı dat. • SessionState – mezi serverem a klientem se pos´ıl´ a jedineˇcn´ y identifik´ ator (pomoc´ı skrytého formuláˇrového pole, souˇc´ ast´ı URL nebo jako cookie). Toto ˇreˇsen´ı zvyˇsuje nároky na v´ ykon serveru.

2.7.4

Relaˇ cn´ı datab´ aze, SQL

Relaˇcn´ı databáze je databáze zaloˇzen´ a relaˇcn´ım modelu (zdroj [14], [15]). Databáze je zjednoduˇsenˇe urˇcité u ´loˇziˇstˇe, kde se ukládaj´ı data. Databáze poskytuje rychlejˇs´ı pˇr´ıstup k dat˚ um neˇz soubory. Databáze téˇz umoˇzn ˇuje paraleln´ı pˇr´ıstup k dat˚ um od v´ıce uˇzivatel˚ u najednou. Základem databáze je tabulka obsahuj´ıc´ı data. Tabulka se sklád´ a ze sloupc˚ u a ˇr´ adk˚ u. Kaˇzd´ y sloupec v tabulce má jedineˇcn´ y název a urˇcit´ y datov´ y typ. Data se ukládaj´ı po ˇrádc´ıch (záznamech). Pro urychlen´ı pˇr´ıstupu k dat˚ um m˚ uˇzeme nad sloupcem (nebo v´ıce sloupci) definovat kl´ıˇc, kter´ y urychl´ı pˇr´ıstup k záznam˚ um podle zvolen´ ych sloupc˚ u. Záznamy mezi tabulkami jsou reprezentov´ any nevlastn´ımi kl´ıˇci, které napomáhaj´ı k udrˇzen´ı integrity databáze. S relaˇcn´ımi databázemi se manipuluje pomoc´ı jazyku SQL (Structured Query Language). 12

Kapitola 3

N´ avrh Na obrázku 3.1 je naznaˇcena základn´ı struktura projektu, dˇediˇcnosti, zdroj˚ u i toku dat. Návrh se ˇr´ıd´ı myˇslenkou, ˇze nejniˇzˇs´ı a v´ ypoˇcetnˇe nejnároˇcnˇejˇs´ı ˇc´ asti programu jsou co moˇzná nejv´ıce optimalizovány, ideálnˇe psané v programovac´ım jazyce s minimáln´ımi poˇzadavky na reˇzie (napˇr. kontroly meze pol´ı, kontroly pˇr´ıstupu do pamˇeti). Dalˇs´ı vrstvy jsou pak psány pomoc´ı vyˇsˇs´ıho programovac´ıho jazyka, kter´ y poskytuje mnoho doplˇ nkov´ ych sluˇzeb a pomoc´ı kterého je jednoduché a hlavnˇe rychlé naprogramovat uˇzivatelské rozhran´ı. Vstupem i výstupem práce programu je vˇzdy obrázek. V´ ysledkem této bakaláˇrské práce jsou knihovny: • Framework – knihovna datov´ ych struktur, optimalizovan´ a (minimáln´ı implementace) pro bakaláˇrskou práci • Mosaic.Lib.Static – knihovna pro vlastn´ı vytvoˇren´ı mozaiky a správu databáz´ı • Mosaic.Lib.Dynamic – .dll knihovna, která slouˇz´ı pro propojen´ı s C# kódem, správa databáz´ı je tu odstranˇena, pˇr´ıd´ any jsou moˇznosti pro spolupráci s C# pro pˇr´ımé vytváˇren´ı obrázku (takto lze doimplementovat podpora dalˇs´ıch formát˚ u, které zvládne .NET framework) • Mosaic.Class – C# tˇr´ıda pro práci s mozaikou, toto tˇr´ıda je univerz´ aln´ı a mˇela by b´ yt vyuˇzitelná pro jak´ ykoliv projekt (nejen takov´ y, kter´ y je váz´ an na webovou sluˇzbu ˇci GUI) • Formatter – tˇr´ıda pro propojen´ı objekt˚ u a databáze (s minimáln´ımi mˇenami lze tuto tˇr´ıdu pouˇz´ıvat napˇr. i pro ODBC a tedy i [skoro] libovolnou databázi) • Web.Library – knihovna pro spolupráci mezi webovou stránkou (Web.Application) a programem na pozad´ı (Web.Service) A dále pak tyto programy: • Mosaic.Console – program pro vytváˇren´ı mozaikov´ ych obrázk˚ u a správu databáz´ı, tento posledn´ı program je psán pˇrenositelnˇe, následuj´ıc´ı ˇc´ asti jsou jiˇz kv˚ uli pouˇzit´ ym technologi´ım vázány je urˇcitou platformu • Web.Application – informaˇcn´ı systém, kter´ y prezentuje práci sluˇzby bˇeˇz´ıc´ı na pozad´ı, pomoc´ı této webového informaˇcn´ıho systému lze poˇzadavky zadávat a zobrazovat 13

• Web.Service – program, kter´ y je navrˇzen tak, aby bˇeˇzel na pozad´ı a zpracov´ aval poˇzadavky zadané pˇres webovou sluˇzbu • Google Donwloader, Last.fm Downloader, ASCII Art Creator – programy pro z´ısk´ aván´ı databáze obrázk˚ u

Obrázek 3.1: Návrh struktury aplikace, knihoven, zdroj˚ u a toku dat

14

Pro vytvoˇren´ı obrázkové mozaiky jsou vˇzdy potˇreba tˇri vˇeci: • vstupn´ı obrázek – obrázek, kter´ y je pouˇzit jako pˇredloha vytvoˇrené mozaiky • databáze obrázk˚ u – pˇredzpracovan´ a databáze s informacemi o obrázc´ıch • obrázky – z obrázk˚ u se sklád´ a mozaika, obrázky nemus´ı b´ yt pˇredepsané velikosti, pˇri zpracován´ı se automaticky jejich velikost oprav´ı podle potˇreby

3.1

Framework

Protoˇze nˇekteré funkce a datové struktury se pouˇz´ıvaj´ı ˇcasto a na mnoha m´ıstech, rozhodnul jsem se nejdˇr´ıve vytvoˇrit knihovnu tˇechto funkc´ı a zcela ji osamostatnit od vlastn´ı implementace. V´ yhodou tohoto pˇr´ıstupu je znovupouˇzitelnost v dalˇs´ıch programech i projektech. Alternativou pouˇzit´ı této knihovny by bylo napˇr. pouˇzit´ı STL knihovny C++. Vˇetˇsina datov´ ych struktur je optimalizov´ ana pro nˇekolik základn´ıch operac´ı, vˇetˇsinou nen´ı potˇreba univerzálnost (napˇr´ıklad u seznam je implementov´ an tak, aby bylo rychlé pˇridáván´ı na konec). Tyta knihovna je napsaná pomoc´ı ISO C99. Knihovna nav´ıc od dále popsan´ ych datov´ ych struktur podporuje téˇz práci s libovolnˇe dlouh´ ymi ˇretˇezci, alokaci velkého mnoˇzstv´ı malé pamˇeti a neomezenˇe velké pole.

3.1.1

Seznam

Tˇr´ıda jednosmˇerného lineárn´ıho seznamu. Speciálnˇe upraven´ y linerán´ı seznam. Tento zvláˇstn´ı pˇr´ıpad je optimalizov´ an pro velmi ˇcasté pˇridáván´ı prvku na konec seznamu. V´ ysledkem je pak pˇridán´ı na konec seznamu se sloˇzitost´ı O(1).

3.1.2

Hash tabulka

Hashovac´ı tabulka je datová struktura, která sdruˇzuje kl´ıˇce (hashe) a hodnoty. Hodnota kl´ıˇce je vypoˇc´ıtána podle pravidla (hashovac´ı funkce) tak, aby: • byl kl´ıˇc co nejjednoznaˇcnˇeji urˇcen, • pravdˇepodobnost stejného kl´ıˇce v´ıce (r˚ uzn´ ym) poloˇzk´ am byla co nejniˇzˇs´ı, • rozptyl hodnot kl´ıˇc˚ u pro dvˇe bl´ızké poloˇzky byl co nejvyˇsˇs´ı Hashovac´ı tabulka je urˇcena pro rychlé vyhledáv´ an´ı v poli. Pomoc´ı hashovac´ı funkce pˇriˇrazujeme hodnotˇe kl´ıˇce ukazatel do datové struktury (pole). Hashovac´ı tabulka, kde kl´ıˇcem je ˇretˇezec. Velikost je volena jako prvoˇc´ıslo (kv˚ uli rovnomˇernému vyuˇzit´ı datové struktury). Sloˇzitost hledán´ı v této datové struktuˇre je O(n).

3.1.3

Seˇ razen´ e pole

Seˇrazené pole je datová struktura pˇri manipulaci s obsahem struktury (pˇrid´ av´ an´ı, odstran ˇován´ı poloˇzek) zachovává seˇrazenost pole. Vyhledáván´ı v této struktuˇre je ˇcastˇeji rychlejˇs´ı neˇz vyhledáv´ an´ı v neseˇrazeném poli. 15

3.2

Knihovny

Knihovna je soubor (kolekce) funkc´ı (metod, tˇr´ıd) pouˇz´ıvan´ ych pˇr´ı v´ yvoje software. Hlavn´ım v´ yznamem moˇznost modulárn´ıho pˇr´ıstupu k programov´ an´ı, kdy je jedna knihovna znovu vyuˇzitelná ve v´ıce projektech. Knihovny poskytuj´ı aplikaˇcn´ı programátorské rozhran´ı (API). Knihovny m˚ uˇzeme rozliˇsovat podle zp˚ usobu propojen´ı s programem: • statická knihovna • dynamická knihovna Statické knihovny jsou s programem spojov´ any bˇehem sestavov´ an´ı (linkov´ an´ı) programu. Do c´ılového programu se uloˇz´ı vˇsechen kód a data odkazovan´ y z programu a vˇsechna data odkazovaná v pouˇzitém kódu knihovny.

3.2.1

Dynamicky linkovan´ e knihovny

Dynamicky linkované knihovny (v prostˇred´ı Microsoft Windows soubory s pˇr´ıponou .dll ) jsou programové moduly obsahuj´ıc´ı kód, data a zdroje (zdroj [7]), jenˇz mohou b´ yt vyuˇzity dalˇs´ım modulem (aplikac´ı nebo dalˇs´ı dynamickou knihovnou). Pˇri sestavován´ı programu jsou do programu pouze um´ıstˇeny odkazy na symboly definované v dynamické knihovnˇe, pro vlastn´ı chod programu je potˇreba pak i dynamick´ a knihovna nainstalovaná ve stejném adresáˇri jako program nebo v systému (a samozˇrejmˇe dalˇs´ı knihovny, které knihovna m˚ uˇze vyuˇz´ıvat). Dynamick´ a knihovna lze naˇc´ıst do programu i aˇz bˇehem bˇehu programu. Dynamické knihovny jsou závislé na operaˇcn´ım systému. Typick´ a pˇr´ıpona dynamick´ ych knihoven v prostˇred´ı Windows je .dll, Unixov´ ych systémech pak .so. V´ yhodou pouˇzit´ı DLL knihovny je moˇznost mˇenit funkˇcnost program˚ u bez nutnosti mˇenit hlavn´ı program. Operaˇcn´ı systém m˚ uˇze optimalizovat vyuˇzit´ı pamˇeti t´ım, ˇze pokud vyuˇz´ıvá dynamickou knihovnu v´ıce proces˚ u najednou, m˚ uˇze b´ yt knihovna v pamˇeti sd´ılen´ a.

3.2.2 3.2.2.1

Extern´ı knihovny libjpeg

JPEG je ˇcasto pouˇz´ıvaná metoda komprese obrázk˚ u a fotografi´ı. Metoda je pouˇz´ıvan´ a ve v´ıce obrázkov´ ych formátech (napˇr´ıklad JPEG/Exif nebo JPEG/JFIF), tyto formáty nejsou vˇetˇsinou rozliˇsovány a jsou oznaˇcov´ any jednoduˇse jako JPEG. JPEG je standardizován jako norma ISO 10918-1. Standard obsahuje kompresi obrázku do datového proudu i formát uloˇzen´ı tohoto proudu do souboru. Implementaci pro práci a manipulaci s obrázky ve formátu JPEG vytvoˇrila skupina Independent JPEG Group [2].

16

3.2.2.2

libpng, zlib

PNG (Portable Network Graphics) je rastrov´ y formát souboru pro uloˇzen´ı obrázku. Tento formát byl vytvoˇren jako náhrada GIF1 (zdroj [16]). Oproti formátu GIF pˇrináˇs´ı PNG tyto v´ yhody: • alfa kanál – pr˚ uhlednost • gama korekce – multiplatformn´ı u ´prava svˇetlosti obrázku • podpora prokládán´ı – obrázek se m˚ uˇze zobrazovat postupnˇe (pˇri naˇc´ıt´ an´ı je obrázek stále detailnˇejˇs´ı) Knihovna libpng vyuˇz´ıvá bezztrátovou kompresi (pomoci knihovny zlib).

3.3

Vyhled´ avac´ı sluˇ zby

Vyhledávac´ı sluˇzby na Internetu pravidelnˇe proch´ az´ı WWW stránky a indexuj´ı obsah. Vyhledávac´ı sluˇzby jsou zamˇeˇreny hlavnˇe na indexov´ an´ı textu, ale vˇetˇsinou indexuj´ı i dalˇs´ı obsah. Napˇr´ıklad jsou to i obrázky. Mezi takovéto vyhledávac´ı sluˇzby patˇr´ı napˇr´ıklad: • Google Images – http://images.google.com/ • Yahoo! Image Search – http://images.search.yahoo.com/ • Live Search – http://www.live.com/?scope=images Indexován´ı prob´ıhá vˇetˇsinou podle alternativn´ıho popisu obrázku (parametr alt), URL obrázku, textu odkazu na obrázek, textu na stránce, kde je obrázek zobrazen. Mohou b´ yt pouˇzity i pokroˇcilejˇs´ı techniky rozpoznáv´ an´ı obsahu obrázk˚ u a fotografi´ı. V´ıce o z´ıskáván´ı obrázk˚ u z webov´ ych sluˇzeb lze nalézt v kapitole 4.8.

3.4

Knihovna pro vytvoˇ ren´ı mozaiky

Kv˚ uli moˇznosti jednoduch´ ych u ´prav, pouˇzitelnosti, rozˇsiˇritelnosti a moˇznosti znovuvyuˇzit´ı kódu je algoritmus a celá knihovna pro vytváˇren´ı mozaiky oddˇelena od zbytku kódu. Tento postup umoˇzn ˇuje vyuˇz´ıt knihovnu pro program pro pˇr´ıkazovou ˇr´ adku nebo pro vytvoˇren´ı DLL knihovny, která je pak zase pouˇz´ıv´ ana dále. Kv˚ uli d˚ uslednému oddˇelován´ı jednotliv´ ych logick´ ych modul˚ u bˇehem programov´ an´ı se tento postup velmi osvˇedˇcil. Pokud by napˇr´ıklad nˇekdo nyn´ı chtˇel vz´ıt knihovnu a vytvoˇrit GUI, staˇc´ı vz´ıt knihovnu a vyuˇz´ıvat pouze jejich sluˇzeb. Knihovna byla napsána tak, aby ˇz´ adné dalˇs´ı zásahy do vlastn´ıho kódu nebylo potˇreba prov´ adˇet. V´ıce o rozˇs´ıˇren´ıch lze nalézt v kapitole 6.1 Moˇzn´ a rozˇs´ıˇren´ı. 1

GIF - Graphics Interchange Format

17

3.5

Optimalizace rychlosti

Prap˚ uvodn´ı implementace programu obsahovala velmi málo optimalizac´ı. V této implementaci byl na optimalizaci brán velk´ y zˇretel, v´ ybˇer datov´ ych struktur i v´ ybˇer algoritm˚ u byl podˇr´ızen pamˇet’ové a rychlostn´ı optimalizaci. Protoˇze v prvn´ım stupni funkce algoritmu nen´ı tˇreba znát vlastn´ı obsah obrázku, staˇc´ı si pamatovat pouze nˇekolik základn´ıch hodnot (pr˚ umˇern´ a barva, pr˚ umˇern´ a barva submatic), staˇc´ı tyto informace naˇc´ıst z pˇredzpracované databáze. T´ımto se velmi redukuje nároˇcnost na pamˇet’, ale i k poˇzadovan´ ym informac´ım.

3.5.1

Trojrozmˇ ern´ y hash

Asi nejvˇetˇs´ı optimalizac´ı, která se velmi pozitivnˇe projevila právˇe na rychlosti algoritmu je pouˇzit´ı uloˇzen´ı pole seznam˚ u obrázk˚ u, které maj´ı zhruba podobnou barevnost. Pˇredstavit tento postup si lze jako rozkrájen´ı trojrozmˇerné RGB krychle (obrázek 2.2), kde kaˇzdá krychle obsahuje pouze barevnˇe podobné obrázky. Pokud by náhodou nebyl nalezen´ y kandid´ at, staˇc´ı hledat pouze v bl´ızkém okol´ı. Tento postup je také ukázal jako lepˇs´ı protoˇze algoritmus je v´ıce´ urovˇ nov´ y (obrázek 2.3) a pro pˇrestup z jedné u ´rovnˇe do druhé je potˇreba nalézt v´ıce kandid´ at˚ u. Hledán´ı pouze podle pr˚ umˇerné barvy má tu nev´ yhodu, ˇze pokud se hledá nejlepˇs´ı shoda, m˚ uˇze se nalézt kandidát, kter´ y je sice podle pr˚ umˇerné barvy bliˇzˇs´ı, ale napˇr´ıklad podle hran by se jednalo o naprosto nevyhovuj´ıc´ı obrázek.

3.5.2

Pouˇ zit´ı seˇ razen´ eho pole s omezenou d´ elkou

V posledn´ım kroku hledán´ı vhodného obrázku do mozaiky se pouˇz´ıv´ a porovn´ av´ an´ı pixel po pixelu. (Tato operace je také velmi nároˇcn´ a, proto se porovn´ av´ a pouze nˇekolik málo obrázk˚ u). Pro selekci z pˇredchoz´ıho kroku se pouˇz´ıv´ a seˇrazené pole s omezenou délkou, která automaticky ˇrad´ı nejlepˇs´ı kandid´ aty na zaˇc´ atek fronty a horˇs´ı automaticky vyˇrazuje. Odpadaj´ı tak problémy s pˇr´ıpadnou realokac´ı (pokud by bylo pouˇzito pole), ˇci pˇr´ıliˇsné pamˇet’ové nároky (pokud by byl pouˇzit seznam).

3.6

Optimalizace vyuˇ zit´ı pamˇ eti

Práce s pamˇet´ı je pˇri bˇehu tohoto programu zásadn´ı, protoˇze je navrˇzen tak, aby pracoval jako sluˇzba na pozad´ı bˇehu poˇc´ıtaˇce. Zvláˇstn´ı péˇce tedy byla vˇenov´ ana pamˇeti – tedy jej´ı alokaci a dealokaci a pokud moˇzno minimalizaci pamˇet’ov´ ych nárok˚ u, protoˇze program je navrˇzen tak, aby pracoval s des´ıtkami tis´ıc obrázk˚ u v databázi.

3.6.1

Droben´ı alokovan´ e pamˇ eti

Protoˇze bˇehem v´ ypoˇctu je potˇreba pˇristupovat a ˇc´ıst z mnoha soubor˚ u, o kter´ ych nen´ı pˇred spuˇstˇen´ım nic známo, a naˇc´ıtán´ı vˇsech je zase nemoˇzné z nedostatku pamˇeti, byla navrhnuta speciáln´ı struktura a postup pro alokaci pamˇeti. Vyuˇz´ıvá se toho, ˇze alokovat pamˇet’ je potˇreba velice ˇcasto, zat´ımco uvolnˇen´ı pamˇeti se provád´ı aˇz po skonˇcen´ı algoritmu. Myˇslenka je taková, ˇze se nejdˇr´ıve alokuje velk´ y pamˇet’ov´ y prostor, ze kterého se postupnˇe podle poˇzadavk˚ u pˇridˇeluj´ı pamˇet’ové bloky. 18

← další bloky

poslední blok

Alokovaná paměť

Přidělená adresa (ukazatel)

Požadavek na paměť

Ukazatel na konec

Volná paměť

Ukazatel na další blok

Nevyužitá paměť

Obrázek 3.2: Názorn´ y nakres fungov´ an´ı tˇr´ıdy allocator Schematické znároznen´ı tˇr´ıdy allocator je na obrázku 3.2. V´ yhody: • Operaˇcn´ı systémy vˇetˇsinou pˇridˇeluj´ı pamˇet’ v bloc´ıch. Tento pˇr´ıstup dovoluje alokovat i po bytech. • Pamˇet’ je lépe vyuˇzita pˇri alokaci velkého mnoˇzstv´ı mal´ ych u ´sek˚ u pamˇeti, nedoch´ az´ı k vytváˇren´ı ˇcást´ı pamˇeti, které z˚ ust´ avaj´ı nevyuˇzity. • Dealokace pamˇeti prob´ıhá v jednom kroku nen´ı potˇreba dealokovat vˇsechny pˇridˇelené bloky jednotlivˇe. Sniˇzuje se moˇznost memory leak˚ u2 . Nev´ yhody: • Na konci alokovaného velkého bloku m˚ uˇze vzniknout nepotˇrebn´ a pamˇet’. Alokace pamˇeti je ale navrˇzena tak, aby doch´ azelo k potˇrebˇe relativnˇe mal´ ych ˇc´ ast´ı pamˇeti. Pokud je alokovan´ y blok relativnˇe velk´ y, tato ztráta by mˇela b´ yt v porovn´ an´ı s cel´ ym blokem zanedbatelná. • Pˇri potˇrebˇe alokovat blok vˇetˇs´ı neˇz je cel´ y alokovan´ y blok. • Nelze dealokovat jednotliv´ y pˇridˇelen´ y blok nebo ho zvˇetˇsit.

3.6.2

Vyuˇ zit´ı hash tabulky

Kaˇzd´ y záznam, kter´ y pˇredstavuje obrázek má kromˇe barevn´ ych charakteristik pˇridˇeleno taktéˇz kl´ıˇcové slovo (m˚ uˇze se pouˇz´ıvat, napˇr´ıklad kdyˇz chceme vytvoˇrit obrázek auto z mnoha dalˇs´ıch aut). Protoˇze se kl´ıˇcová slova ˇcastokr´ at opakuj´ı, je kaˇzdé kl´ıˇcové slovo v pamˇeti uloˇzeno pouze jednou. V pracovn´ı pamˇeti je pak pouze um´ıstˇen odkaz na toto kl´ıˇcové slovo, ne samotná alokovaná pamˇet’. Pˇri naˇc´ıtán´ı databáze se v hashtabulce nalezne kl´ıˇcové slovo a do samotného záznamu v pamˇeti se uloˇz´ı pouze odkaz. 2

memory leak – ztr´ ata pamˇeti, kter´ a byla alokov´ ana a na kterou byl ztracen odkaz

19

3.7

C# tˇ r´ıda

Propojen´ı jazyk˚ u C# a C je provedeno pˇres dynamicky linkovanou knihovnu DLL (viz. 3.2.1). Tato knihovna sama o sobˇe nepˇrin´ aˇs´ı ˇz´ adnou dalˇs´ı funkˇcnost stará se pouze o vol´ an´ı funkc´ı z niˇzˇs´ıho programovac´ıho jazyka. Pˇri vytvoˇren´ı této tˇr´ıdy vzniká znovupouˇziteln´ a knihovna (tˇr´ıda), kterou lze pouˇz´ıt v dalˇs´ıch programech. Napˇr´ıklad by bylo moˇzné vytvoˇrit jednoduché grafické uˇzivatelské rozhrann´ı, program pro pˇr´ıkazov´ y ˇrádek ˇci sluˇzbu bˇeˇz´ıc´ı na pozad´ı. Z tˇechto moˇznost´ı je v této bakal´ aˇrské práci implementována sluˇzba, která spolupracuje s jednoduch´ ym webov´ ym uˇzivatelsk´ ym rozhran´ım. Dalˇs´ı v´ yhodou je moˇznost pˇridat dalˇs´ı funkˇcnost na u ´rovni .NET. Pˇr´ıkladem m˚ uˇze b´ yt podpora dalˇs´ıch grafick´ ych formát˚ u (napˇr. GIF) ne lepˇs´ı správa vstupn´ıch databáz´ı obrázk˚ u.

3.8

Formatter

Pro práci s databáz´ı existuje nˇekolik moˇznost´ı. Je moˇzné spojit se s databáz´ı, vloˇzit SQL dotaz a zpracovat vrácenou odpovˇed’. Tato tˇr´ıda se snaˇz´ı o trochu jin´ y pˇr´ıstup k databázi – snaˇz´ı se pˇr´ımo atributy tˇr´ıdy pˇriˇradit jednotliv´ ym sloupc˚ um tabulky. Jedna instance objektu pak zastupuje jeden ˇrádek tabulky. + Třída +

Atributy ID Name Price

Tabulka v databázi ID Name Price

Obrázek 3.3: Tˇr´ıda formatter – zobrazen´ı tabulky relaˇcn´ı databáze na objekt v C#

3.8.1

N´ avrh

Návrh tˇr´ıdy Formatter je svázán s moˇznost´ı jazyka C# pouˇz´ıvat a pˇriˇrazovat jednotliv´ ym ˇclen˚ um tˇr´ıd atributy (viz. 2.7.1.2). Tˇr´ıda se snaˇz´ı pˇred uˇzivatelem skr´ yt nutnost pouˇz´ıvat dotazovac´ı jazyk SQL databáze. Tˇr´ıda mus´ı m´ıt specifikováno, ke které tabulce se vztahuje. Atributy ˇclen˚ u tˇr´ıdy specifikuj´ı propojen´ı se sloupcem v databázi a typ, kter´ y se pouˇzije pro formátován´ı z ˇci do SQL dotaz˚ u. Dalˇs´ı v´ yhodou je dynamické generov´ an´ı SQL dotaz˚ u aˇz pˇri potˇrebˇe, aplikaˇcn´ı programátor jednoduˇse napˇr´ıklad specifikuje, ˇze potˇrebuje naˇc´ıst záznam s konkrétn´ım identifikaˇcn´ım ˇc´ıslem a formatter vygeneruje SQL pˇr´ıkaz, provede jej a v´ ysledek dotazu zpracuje a data pˇriˇrad´ı pˇr´ımo dat˚ um instanci objektu.

20

Formatter poskytuje základn´ı sluˇzby nad objekty (záznamy): • Naˇcten´ı – je nalezen ˇrádek v databázi a jeho hodnoty jsou pˇriˇrazeny instanci tˇr´ıdy. • Naˇcten´ı seznamu – podle SQL dotazu je vytvoˇren nov´ y seznam a obsahuje vˇsechny objekty, jenˇz zastupuj´ı záznamy v tabulce databáze • Vytvoˇren´ı – objekt je vytvoˇren, jeho hodnoty jsou inicializov´ any pomoc´ı konstruktoru. Pˇri pokusu o uloˇzen´ı je vygenerov´ an SQL dotaz INSERT. • Aktualizovat – objekt, kter´ y jiˇz byl z databáze naˇcten, je v databázi taktéˇz aktualizován. Pˇri uloˇzen´ı (aktualizaci) je vygenerov´ an UPDATE dotaz. Formatter poskytuje tuto základn´ı funkˇcnost: • Skr´ yvá vˇetˇsinu potˇreby pouˇz´ıvat SQL dotazy. • Zjednoduˇsuje pˇr´ıpadnou nutnost pˇridat nové prvky nebo nˇekteré odeb´ırat. SQL dotazy jsou generovány podle atribut˚ u v tˇr´ıdˇe. Odebrán´ı pˇrid´ an´ı automaticky zmˇen´ı dotazy. • Zruˇsen´ı nutnosti rozliˇsovat mezi t´ım, zda se jedná o vytvoˇren´ı nebo aktualizaci záznamu. Formatter zvol´ı operaci podle typu vytvoˇren´ı.

3.8.2

Konstrukce objektu

Kaˇzdá, která bude takto pouˇz´ıvána mus´ı b´ yt pˇredkem tˇr´ıdy Formatter. T´ımto zdˇed´ı metody pro naˇcten´ı a uloˇzen´ı (vloˇzen´ı a aktualizaci) a také nˇekolik doprovodn´ ych metod (napˇr. zjiˇstˇen´ı tabulky svázané s tˇr´ıdou). Dˇedˇen´ım od této tˇr´ıdy vzniká nutnost m´ıt v kaˇzdé tabulce m´ıt sloupec ID. Sloupec ID je typu GUID (viz. [4] nebo [6]), coˇz je unikátn´ı identifik´ ator, kter´ y by mˇel b´ yt celosvˇetovˇe jedineˇcn´ y.

3.8.3

Naˇ cten´ı, uloˇ zen´ı

Existuj´ı dva druhy ˇcten´ı dat z databáze. Prvn´ı moˇznost je naplnit daty jiˇz existuj´ıc´ı (nebo novˇe vytvoˇren´ y) jeden objekt, dalˇs´ı moˇznost´ı je naˇcten´ı v´ıce poloˇzek (SQL dotaz vrac´ı v´ıce záznam˚ u). Protoˇze obecnˇe m˚ uˇze b´ yt takov´ ych poloˇzek nekoneˇcnˇe, je vhodné pouˇz´ıt pro uloˇzen´ı v´ıce záznam˚ u lineárn´ı seznam. Uloˇzen´ı poloˇzky m˚ uˇze prob´ıhat jako vloˇzen´ı nové poloˇzky nebo aktualizace jiˇz existuj´ıc´ı. Formatter si stav objektu vnitˇrnˇe pamatuje a SQL dotaz generuje podle potˇreby. Aplikaˇcn´ı programátor nemus´ı mezi tˇemito dvˇema pˇr´ıpady rozliˇsovat, pro nˇej existuje pouze metoda pro uloˇzen´ı.

3.8.4

Moˇ zn´ a rozˇ s´ıˇ ren´ı, pouˇ zit´ı

Hlavn´ı v´ yhodou je moˇznost jednoduché manipulace s daty v tabulce relaˇcn´ı databáze.

21

Protoˇze kaˇzd´ y objekt mus´ı b´ yt sváz´ an s pˇripojen´ım k databázi, mus´ı b´ yt toto spojen´ı vytvoˇreni pˇri vytvoˇren´ı objektu. Je v´ıce moˇznost´ı: • Specifikovat spojen´ı pˇri kaˇzdém vytváˇren´ı zvláˇst’, napˇr´ıklad pˇred´ an´ı v konstruktoru objektu. • Provázat vytváˇren´ı objektu s konkrétn´ı konfiguraˇcn´ı tˇr´ıdou, kter´ y m˚ uˇze existovat ’ pouze v jedné instanci – tzv. singleton. Tato tˇr´ıda by zajiˇst ovala otevˇren´ı komunikace s SQL serverem a pˇri vytváˇren´ı objektu by nebylo nutné toto spojen´ı explicitnˇe zadávat. • Kombinace v´ yˇse uveden´ ych moˇznost´ı, implementovat obˇe varianty. Dalˇs´ı velkou v´ yhodou je jednoduchost a rychlost pouˇz´ıv´ an´ı. Nev´ yhodou to, ˇze sloˇzitˇejˇs´ı dotazy na databázi se mus´ı stále prov´ adˇet pomoc´ı p˚ uvodn´ıho programového rozhrann´ı. Moˇznost´ı rozˇs´ıˇren´ı by bylo moˇznost naˇc´ıt´ an´ı pˇr´ımo cel´ ych dalˇs´ıch entit, pokud objekt (tabulka) obsahuje referenci na dalˇs´ı objekt (tabulku). Napˇr. tabulka Osoba obsahuje vazbu do takulky Adresa. Moˇznost´ı by bylo upravit generátor SQL kódu tak, aby vˇsechna data byla pˇreˇctena jedn´ım SQL dotazem za pouˇzit´ı JOIN.

3.9

Webov´ a sluˇ zba

Webová sluˇzba je nadstavba nad C# knihovnou, která usnadˇ nuje vyuˇz´ıv´ an´ı sluˇzeb knihovny pomoc´ı uˇzivatelského rozhran´ı. Webová sluˇzba poskytuje rozhrann´ı pro komunikaci uˇzivatele a sluˇzby zajiˇst’uj´ıc´ı vytváˇren´ı mazaiky. Protoˇze vytvoˇren´ı obrázku je ˇcasovˇe a v´ ypoˇcetnˇe nároˇcn´ yu ´kol, kter´ y by mohl trvat do pozdˇejˇs´ı doby, neˇz by doˇslo k vyprˇsen´ı spojen´ı mezi serverem a klientem (timeout), byla webová sluˇzba rozdˇelena na dvˇe hlavn´ı ˇc´ asti - prezenˇcn´ı (uˇzivatelské rozhrann´ı) a v´ ykonnou (sluˇzbu pracuj´ıc´ı na pozad´ı). Prezenˇcn´ı ˇcást je informaˇcn´ı systém pro správu, zadáv´ an´ı a zobrazov´ an´ı poˇzadavk˚ u. Pomoc´ı jednoduchého grafického rozhrann´ı zpˇr´ıstupnˇeného pˇres webov´ y prohl´ıˇzeˇc m˚ uˇze uˇzivatel uˇzivatel procházet poˇzadavky a vlastn´ı pˇrid´ avat. Poˇzadavek má vlastnosti, které jsou nutné pro zpracov´ an´ı poˇzadavku. Napˇr´ıklad vstupn´ı soubor, kter´ y byl na server uˇzivatelem nahrán, ˇcas pˇrid´ an´ı, stav prov´ adˇen´ı, atd. Pˇri pˇridáván´ı poˇzadavku m˚ uˇze uˇzivatel specifikovat databázi (viz. 4.8 a 3.3), velikost vstupn´ıho a v´ ystupn´ıho ˇctverce a typ v´ ystupn´ıho obrázku (PNG nebo JPEG). Pˇri pˇridán´ı poˇzadavku je poˇzadavek zaˇrazen do fronty, kde ˇcek´ a, aˇz bude sluˇzbou pracuj´ıc´ı na pozad´ı vybrán a zpracov´ an. Sluˇzba na pozad´ı se dotazuje na dosud nezpracovan´ y poˇzadavek a v pˇr´ıpadˇe, ˇze takov´ y nalezne, oznaˇc´ı jej stavem zpracov´ av´ ano a spust´ı vytváˇren´ı mozaiky.

22

3.9.1

ER diagram

Job <>ID Name InputFile OutputFile ImageType Keywords Tile Size

Keyword 0..n

0..n

AddTime StartTime FinishTime Progress Finished Error

<>ID Name

Service <>ID LastReport Status

Obrázek 3.4: ER diagram webové sluˇzby

3.9.1.1

Job

´ Uloha (at’ jiˇz zpracovaná nebo zat´ım ve frontˇe) je u ´stˇredn´ı entitou informaˇcn´ıho systému. • Name – Pojmenován´ı poˇzadavku (popis toho co je na obrázku) • InputFile – vstupn´ı soubor na serveru • OutputFile – v´ ystupn´ı soubor na serveru • ImageType – typ v´ ystupn´ıho obrázku (m˚ uˇze b´ yt JPEG nebo PNG) • Keywords – kl´ıˇcová slova z nichˇz bude sloˇzena databáze, ze které se bude generovat mozaika • Tile – velikost vstupn´ıho ˇctverce • Size – velikost v´ ystupn´ıho ˇctverce • AddTime, StartTime, FinishTIme – ˇcasy vloˇzen´ı, poˇc´ atku a dokonˇcen´ı zpracov´ an´ı • Progress – Procentuáln´ı vyjádˇren´ı dokonˇcen´ı u ´lohy • Finished – pˇr´ıznak, zda je u ´loha dokonˇcena • Error – Pˇr´ıznak, zda pˇri zpracov´ an´ı poˇzadavku nedoˇslo k chybˇe 3.9.1.2

Keyword

Keyword – kl´ıˇcové slovo (název databáze). V tabulce jsou uloˇzena vˇsechna dostupná kl´ıˇcov´ a slova. Tato kl´ıˇcová slova byla pouˇzita jako dotaz na Google (viz. 4.8) nebo jinak vystihuj´ı skupinu (databázi) obrázk˚ u.

23

3.9.1.3

Service

Monitorován´ı sluˇzby (viz. 4.7.1) se prov´ ad´ı pomoc´ı zvláˇstn´ıho vlákna, které pˇri spuˇstˇen´ı sluˇzby zapisuje do této tabulky cyklicky datum a ˇcas aktualizace. Teoreticky by jedna tabulka mohla b´ yt vyuˇzita na monitorov´ an´ı v´ıce sluˇzeb, v tomto projektu je ovˇsem pouze jedna sluˇzba, takˇze v tabulce je vyuˇzit pouze jeden ˇr´ adek. Monitorovaná sluˇzba je identifikov´ an´ı pomoc´ı jedineˇcného GUID (viz. [4] nebo [6]). Toto GUID se mus´ı náhodnˇe zvolit a specifikovat v konfiguraci aplikace. Do sloupce LastReport se uklád´ a datum a ˇcas posledn´ıho ohláˇsen´ı sluˇzby a do Statusu se uklád´ a aktuáln´ı stav sluˇzby (sluˇzba ˇcek´ a na poˇzadavky nebo sluˇzba zpracov´ av´ a poˇzadavek). Pokud je posledn´ı ohláˇsen´ı sluˇzby starˇs´ı neˇz vhodnˇe zvolen´ y ˇcas, je sluˇzba povaˇzov´ ana jako nefunkˇcn´ı. Tento stav lze pak v webové ˇc´ asti zobrazit.

3.9.2

Knihovna pro komunikaci

Webové rozhrann´ı i sluˇzba pro proveden´ı poˇzadavk˚ u na pozad´ı pouˇz´ıv´ a pro komunikaci datab´ azi a tud´ıˇz mnoho ˇcást´ı projektu je spoleˇcn´ ych. Právˇe tyto spoleˇcné tˇr´ıdy a metody jsou um´ıstˇeny v dalˇs´ı knihovnˇe. Tˇemito spoleˇcn´ ymi ˇcástmi je napˇr´ıklad nav´ az´ an´ı spojen´ı s databáz´ı, pˇr´ıstup k obsahu datab´ aze, pˇr´ıstup k monitorovac´ı sluˇzbˇe, tˇr´ıdy (entity).

3.9.3

Uˇ zivatelsk´ e rozhrann´ı

Webové rozhrann´ı je uˇzivatelsky pˇr´ıvˇetiv´ a moˇznost zadáv´ an´ı a prohl´ıˇzen´ı poˇzadavk˚ u. Pouˇzit´ı webového rozhrann´ı je moˇzné odst´ınit uˇzivatele od pouˇzitého operaˇcn´ıho systému. Klient nen´ı limitován operaˇcn´ım systémem ani ˇz´ adn´ ymi dalˇs´ımi omezen´ımi plynouc´ı z pouˇzit´ı konkrétn´ıho hardware, operaˇcn´ıho systému ani dalˇs´ıch program˚ u. Jedin´ ymi poˇzadavky je m´ıt pˇristup k webové sluˇzbˇe (pˇres s´ıt’ Internet), webov´ y prohl´ıˇzeˇc a schopnost zobrazovat obrázky. Pro kompletn´ı funkˇcnost mus´ı jeho webov´ y prohl´ıˇzeˇc umˇet pos´ılat soubory. Ukázka webového rozhran´ı je na obrázku 4.2. Seznam úloh

Vložit novou úlohu

Úloha - podrobnosti

Obrázek 3.5: Struktura stránek a pˇrechod˚ u webové sluˇzby Uˇzivatelské prostˇred´ı dovoluje uˇzivateli zadávat poˇzadavky na zpracov´ an´ı. Zadán´ı poˇzadavku se provád´ı zvolen´ım souboru s obrázkem a zvolen´ım doprovodn´ ych parametr˚ u.

24

Jako dalˇs´ı parametry m˚ uˇze uˇzivatel zvolit: • Název – název poˇzadavku (uˇzivatelské oznaˇcen´ı) • Seznam kl´ıˇcov´ ych slov – urˇcuje tématiku a rozsáhlost pouˇzité databáze. • Formát v´ ystupn´ıho obrázku – lze zvolit formát v´ ystupn´ıho obrázku (viz. 4.2) • Vstupn´ı a v´ ystupn´ı velikost ˇctverce – algoritmus dokáˇze pracovat s r˚ uzn´ ymi vstupn´ımi velikostmi taktéˇz dokáˇze upravit vstupn´ı obrázek na poˇzadovanou velikost (zmˇena velikosti obrázku)

25

Kapitola 4

Implementace 4.1

Barevn´ y model, barevn´ a hloubka

Program internˇe pracuje v pouze jedné barevné hloubce vyuˇz´ıvaj´ıc´ı RGB model. Program pro ukládán´ı do intern´ı pamˇeti vyuˇz´ıv´ a na jeden pixel celkem 3 byty, pracuje tedy s barevnou hloubkou 24 bit˚ u. U soubor˚ u JPEG pˇredpokládá právˇe tento formát. PNG obrázky automaticky pomoci vnitˇrn´ıch filtr˚ u knihovny pˇrevád´ı na 24 bit˚ u, pˇr´ıpadnou pr˚ uhlednost´ı sloˇzku (alfa kan´ al) odstraˇ nuje.

4.2

Optimalizace ukl´ ad´ an´ı obr´ azku

Knihovny pro práci s PNG (viz. 3.2.2.2) a JPEG (viz. 3.2.2.1) dovoluj´ı vytváˇret obraz postupnˇe po jednotliv´ ych ˇrádc´ıch. V rámci optimalizace vyuˇzit´ı pamˇeti tento program vyuˇz´ıv´ a této moˇznosti a zapisuje obrázky postupnˇe. Pˇri zpracován´ı poˇzadavku je pamˇet’ pˇridˇelena pouze pro jeden v´ ysledn´ y obrazov´ y blok. V´ yhodou je n´ızká pamˇet’ová nároˇcnost – cel´ y v´ ysledn´ y obrázek, kter´ y je ˇcasto nav´ıc obrovsk´ y, nemus´ı b´ yt uchováván v pamˇeti, v nˇekter´ ych kraj´ıch pˇr´ıpadech by mohlo docházet aˇz ke swapován´ı a celkovému zpomalen´ı systému. Program dokáˇze vytvoˇrit tak velk´ y obrázek, kter´ y nemus´ı b´ yt ani klient schopen zobrazit (prohl´ıˇzeˇc jej odm´ıtne jako pˇr´ıliˇs velk´ y).

4.3

Optimalizace alokace pamˇ eti obr´ azku

Rastrov´ y obrázek lze brát jako dvourozmˇernou matici, a proto také intuitivnˇe je jednoduˇsˇs´ı implementovat vnitˇrn´ı uloˇzen´ı jako pole pol´ı (jako matici). Tento pˇr´ıstup má ovˇsem tu nev´ yhodu, ˇze pˇri alokaci obrázku doch´ az´ı k mnohonásobné alokaci, doch´ az´ı tedy k tˇr´ıˇstˇen´ı ’ pamˇeti a protoˇze operaˇcn´ı systém vˇetˇsinou pˇridˇeluje pamˇet po pevnˇe velk´ ych bloc´ıch, m˚ uˇze docházek k alokaci pamˇeti, která nakonec nebude vyuˇzita. Alokac´ı pˇresnˇe potˇrebné velikosti pole m˚ uˇze sice také doj´ıt k nevyuˇzit´ı pamˇeti, ovˇsem ˇrádovˇe menˇs´ı. Názorné proveden´ı alokace je zobrazeno na obrázku 4.1.

26

Začátek paměti Ukazatel na řádek Všechny ukazatele na řádky

Jeden blok paměti

Řádek obrázku č. 1 Řádek obrázku č. 2 ...

Poslední řádek obrázku

Obrázek 4.1: Schéma rozloˇzen´ı pamˇeti pro intern´ı uloˇzen´ı obrázku

4.4

Obr´ azky a vyrovn´ avac´ı pamˇ et’

Z´ıskán´ı informac´ı o obrázku je ˇcasovˇe nároˇcn´ a ˇcinnost. Pro z´ısk´ an´ı informac´ı, které jsou potˇreba k v´ ypoˇctu je potˇreba obrázek naˇc´ıst, proj´ıt pixel po pixelu a spoˇc´ıtat charakteristiky a vlastnosti obsahu obrázku. Pˇri velkém mnoˇzst´ı obrázk˚ u (des´ıtky tis´ıc) m˚ uˇze b´ yt pamˇet’ov´ a nároˇcnost obrovsk´ a a pro dneˇsn´ı systémy nesplnitelná. Proto pˇred vlastn´ım v´ ypoˇctem je potˇreba indexovat (pˇredzpracovat) obrázky. Pro kaˇzd´ y naˇcten´ y obrázek se zjiˇst’uje pr˚ umˇern´ a barva, pak se rozdˇel´ı na matici 4 × 4 a pro kaˇzdou matici se opˇet spoˇc´ıtá pr˚ umˇerná barva. Tato databáze se pak uloˇz´ı do textového souboru spoleˇcnˇe s cestou k souboru a kl´ıˇcov´ ym slovem. Taktováto databáze je pak pˇripravena pro pouˇzit´ı vytváˇren´ı mozaiky. Nutnost pouˇzit´ı vyrovnávac´ı pamˇeti vych´ az´ı z pouˇzitého algoritmu (popis ve zvláˇstn´ı kapitole 2.5).

4.5 4.5.1

Pouˇ zit´ e v´ yvojov´ e n´ astroje Visual Studio 2005

Microsoft Visual Studio je integrované v´ yvojové prostˇred´ı pro v´ yvoj aplikac´ı. M˚ uˇze b´ yt vyuˇzito pro v´ yvoj aplikac´ı pro konzoli, s grafick´ ym uˇzivatelsk´ ym prostˇred´ım, webov´ ych stránek, webov´ ych sluˇzeb. Je podporován v´ yvoj pomoc´ı nativn´ıch jazyk˚ u, ale i pomoc´ı tzv. managed code. Editor podporuje IntelliSense, které automaticky nab´ız´ı automatické dokonˇcov´ an´ı kódu. V dobˇe psan´ı programu existovala sice jiˇz novˇejˇs´ı verze .NET Frameworku (verze 3.5) i Visual Studia (verze 2008), ovˇsem tato starˇs´ı verze je naprosto dostaˇcuj´ıc´ı. 27

Technologie, nástroj C jpeglib libpng C# .NET Framework ASP.NET Microsoft SQL Server Microsoft IIS Server PHP XHTML CSS Javascript Last.fm API Subversion Apache

Verze, norma ISO C99 6b (Win) 1.2.28 2.0 2.0 2.0 9.0 7.0 5.2.5 1.0 1.0 1.5 2.0 1.5.2 2.2.9

Tabulka 4.1: Tabulka konkrétnˇe pouˇzit´ ych technologi´ı, nástroj˚ u a programovac´ıch jazyk˚ u

4.5.2

SQL Server Management Studio

Microsoft SQL Server Management Studio je nástroj distribuovan´ y spoleˇcnˇe s Microsoft SQL Server pro konfiguraci a správu vˇsech ˇc´ ast´ı SQL Serveru. Obsahuje editor skript˚ u ale i grafické uˇzivatelské nástroje pro správu. Pomoc´ı tohoto nástroje lze vytváˇret, mˇenit a prohl´ıˇzet databáze i tabulky (ale i mnoho dalˇs´ıho).

4.6

Pouˇ zit´ e technologie

Vlastn´ı hlavn´ı programová ˇcást je napsána v C, ale nadstavba je pro rychlejˇs´ı v´ yvoj napsána ve vyˇsˇs´ım programovac´ım jazyce. Kv˚ uli tomuto postupu pˇri programov´ an´ı muselo b´ yt vyuˇzito plno technologi´ı (tabulka 4.1). Jejich propojen´ı nen´ı natolik sloˇzité, aby to ˇcinilo neuskuteˇcniteln´ y problém. Vˇsechny pouˇzité technologie jsou otevˇrené a spolupracuj´ı spolu dobˇre, v pr˚ ubˇehu implementace nedocházelo ke konflikt˚ um ˇci vzájemné nekompatibilitˇe. Bˇehem implementace bylo (pro zálohu, moˇznost vracet staré verze a k dokumentaˇcn´ım u ´ˇcel˚ um) vyuˇz´ıváno Subversion. I kdyˇz je tento nástroj urˇcen hlavnˇe pro práci v´ıce programátor˚ u, jeho vyuˇzit´ı se velmi osvˇedˇcilo. Pouˇz´ıv´ an´ı Subversion umoˇzn ˇuje zobrazovat staré verze, vracet se k p˚ uvodn´ım, pˇri náhodné ztrátˇe souboru, adresáˇre ˇci ˇc´ asti kódu je k dispozici záloha.

4.7

Webov´ a sluˇ zba

Webová sluˇzba je implementována v ASP.NET bez pouˇzit´ı Web Server Controls. Webov´ a sluˇzba je napsána pomoc´ı XHTML, CSS (kask´ adové styly) a Javascriptu (Javascript slouˇz´ı pouze k doplˇ nkov´ ym funkc´ım, pro vlastn´ı bˇeh nen´ı nutn´ y). Webová sluˇzba je napsána minimalisticky tak, aby fungovala ve vˇetˇsinˇe prohl´ıˇzeˇc˚ u. K zobrazen´ı stránek nen´ı potˇreba podpora Javascriptu ani CSS. Stránky tak lze prohl´ıˇzet 28

↑Zobrazení detailu úlohy zpracování, úloha je hotová → Vložení nové úlohy - zadání všech potřebných parametrů ↓ Detail úlohy, která je zpracovávaná Monitorování služby: ? zelená vlajka - služba je připravena zpracovávat zadané požadavky ? modrá vlajka - služba pracuje ? červená vlajka - služba nepracuje, není spuštěna, došlo k chybě

Obrázek 4.2: Webov´ a sluˇzba v akci a pouˇz´ıvat i na zaˇr´ızen´ ych, které nemaj´ı velk´ y“ internetov´ y prohl´ıˇzeˇc. Takov´ ymito zaˇr´ıze” n´ımi jsou napˇr´ıklad telefony, PDA, komunik´ atory.

4.7.1

Monitorov´ an´ı sluˇ zby

Informace o stavu provádˇen´ı poˇzadavku se uklád´ a do databáze. Fungován´ı pracuje na pˇredpokladu, ˇze pokud bˇeˇz´ı program na zpracov´ an´ı poˇzadavk˚ u, je sluˇzba dostupná. Sluˇzba pro zpracován´ı bˇeˇz´ı ve dvou oddˇelen´ ych vláknech. Jedno se stará a vlastn´ı zpracováván´ı, druhé periodicky zapisuje stav druhého vlákna s ˇcasov´ ym u ´dajem do databáze. V pˇr´ıpadˇe ukonˇcen´ı sluˇzby, skonˇc´ı také druhé vlákno, k ˇz´ adnému zápisu jiˇz nedojde a klientsk´ y program podle doby posledn´ıho zápisu zjist´ı, ˇze sluˇzba nen´ı funkˇcn´ı.

4.8

Stahov´ an´ı obr´ azk˚ u

Pro práci algoritmu je potˇreba v ideáln´ım pˇr´ıpadˇe nˇekolik tis´ıc r˚ uzn´ ych obrázk˚ u v databázi, ze kter´ ych se vytváˇr´ı v´ ysledná mozaika. Pro názorné pouˇzit´ı programu je idáln´ı pouˇz´ıt obrázky aut pˇri vytváˇren´ı obrázku auta. Protoˇze ruˇcn´ı zaˇrazován´ı obrázk˚ u by bylo ˇcasovˇe velice nároˇcné, vznikl nápad vytvoˇrit

29

jednoduch´ y program (skript), kter´ y bude automaticky z indexovac´ıch sluˇzeb (viz. 3.3) stahovat obrázky a automaticky je zaˇrazovat (pˇriˇrazovat tagy) do skupin. Google nab´ız´ı moˇznost vyhledávat obrázky podle vloˇzeného kl´ıˇcového slova (textu). Tuto sluˇzbu nab´ız´ı ale i dalˇs´ı vyhledávac´ı (indexovac´ı) internetové sluˇzby. Experimentován´ım s v´ıce sluˇzbami, jsem zjistil, ˇze vˇetˇsina sluˇzeb omezuje zobrazen´ı (nalezen´ı) asi na tis´ıc obrázk˚ u. Takto velk´ a databáze je podle mnou proveden´ ych experiment˚ u k rozumnému v´ ysledku nedostateˇcn´ a. Naˇstˇest´ı nˇekteré sluˇzby dávaj´ı moˇznost vyhledat obrázky r˚ uzn´ ych velikost´ı, ˇc´ımˇz lze z´ıskat v´ıce v´ıce obrázk˚ u z jednoho dotazu. Nakonec pro stahován´ı obrázk˚ u (a vytváˇren´ı databáze) vybral jako zdroj Google a jeho sluˇzbu Image Search. Samotn´ y skript je naprogramov´ an pomoc´ı PHP. (Vyuˇz´ıv´ a se toho, ˇze PHP m˚ uˇze fungovat jako interpret.) Na poˇzadovan´ y dotaz skript nalezne pomoc´ı sluˇzby obrázky a jejich miniatury uloˇz´ı do jednoho adresáˇre, kter´ y je pak pˇripraven pro indexov´ an´ı. K bakaláˇrské práci je téˇz pˇriloˇzen skript, kter´ y dokáˇze pomoc´ı Last.fm API nalézt pro konkrétn´ıho uˇzivatele jeho nejposlouchanˇejˇs´ı skupiny a stáhnout k nim obrázky alb. Tyto staˇzené obrázky pak lze pouˇz´ıt pro vytvoˇren´ı databáze.

30

Kapitola 5

V´ ysledky Cel´ y plánovan´ y systém se podaˇrilo zdárnˇe implementovat. Webová ˇcást i sluˇzba zpracovávaj´ıc´ı poˇzadavky je funkˇcn´ı a stabiln´ı. V´ ysledné obrázky jsou si vˇernˇe podobné. Pˇri vzdálenˇejˇs´ım pohledu na obrázek, je p˚ uvodn´ı pˇredloha dobˇre rozpoznatelná. Barevnost vybran´ ych obrázk˚ u odpov´ıd´ a pˇredloze. Vybran´ y obrázek pˇri pohledu z dálky sedne do v´ ysledného obrázku. Hrany se algoritmus snaˇz´ı zachov´ avat. Pˇri pˇribl´ıˇzen´ı je vidˇet, ˇze pokud nˇekudy vedl ostr´ y, barevnˇe v´ yrazn´ y pˇrechod, algoritmus se snaˇz´ı nalézt obrázek s velmi podobn´ ym pˇrechodem. V´ ykon programu je v rámci moˇznost´ı rychl´ y – vytváˇren´ı pr˚ umˇerné mozaiky trvá v ˇr´ adu des´ıtek sekund maximálnˇe nˇekolik minut. T´ımto se potvrdil p˚ uvodn´ı pˇredpoklad, ˇze mozaiku nen´ı moˇzné vytváˇret za bˇehu, ale je nutné rozdˇelit zadáv´ an´ı a vytváˇren´ı do oddˇelen´ ych ˇcást´ı. Program zvládá databázi nˇekolika des´ıtek tis´ıc obrázk˚ u v databázi. Programu neˇcin´ı problém vytvoˇrit opravdu velkou mozaiku (napˇr. vˇetˇs´ı neˇz 7000 × 5000 pixel˚ u). U vˇetˇs´ıch obrázk˚ u vzniká sp´ıˇse problém s jejich následn´ ym zobrazen´ım. Na druhou stranu algoritmus sice relativnˇe dobˇre zvlád´ a hrany, ale jemné postupné pˇrechody ve vˇetˇsinˇe pˇr´ıpad˚ u p˚ usob´ı problémy a ve v´ ysledném obrázku se takov´ yto pˇrechod zv´ yrazn´ı. V´ ykon je sice relativnˇe dostateˇcn´ y pro testované databáze o obrázky, návrh algoritm˚ u pro v´ ybˇer mozaiky zp˚ usobuje lineárn´ı nároˇcnost vytváˇren´ı mozaiky. Pˇri pouˇzit´ı o ˇr´ ad vˇetˇs´ı databáze (miliony obrázk˚ u) by zpomalen´ı bylo citelné. V programu existuje nˇekolik konstantn´ıch parametr˚ u, které ovlivˇ nuj´ı v´ yslednou mozaiku, uˇzitetel nemá moˇznost jejich hodnotu mˇenit. Tyto hodnoty jsou experimenty nastaveny kompromisnˇe tak, aby v´ ypoˇcet nebyl pˇr´ıliˇs dlouh´ y a aby byl dostateˇcnˇe kvalitn´ı. V´ ybˇer obrázku, kter´ y bude pouˇzit do mozaiky, se sklád´ a ze tˇr´ı u ´rovn´ı. Mezi kaˇzdou u ´rovn´ı je definován poˇcet obrázk˚ u, které jsou zaˇrazeny i do dalˇs´ı u ´rovnˇe. Zvˇetˇsen´ım tˇechto hodnot by mohlo k velkému nár˚ ustu nároˇcnosti. Dalˇs´ı konstantou je penalizace za pouˇzit´ı obrázku. Snahou samozˇrejmˇe je, aby se obrázky vedle sebe co nejménˇe opakovaly, proto je pˇri pouˇzit´ı obrázku pˇripoˇctena penalizace, která mu zhorˇs´ı v´ ybˇer v následuj´ıc´ıch kroc´ıch. M˚ uˇze se ale stát, ˇze obrázek je nejlepˇs´ı kandid´ at a vloˇzen´ı jiného by pokazilo celkov´ y dojem z mozaiky. Z tohoto d˚ uvodu je penalizace nastavena pˇres mnoho pokus˚ u pevnˇe. Asi nejvˇetˇs´ı slabinou pˇri vytváˇren´ı mozaiky je databáze obrázk˚ u. Ideáln´ı vytváˇren´ı databáze je ruˇcnˇe nebo z obrázk˚ u, kde je zaruˇceno, ˇze obrázek opravdu obsahuje poˇzadovanou tématiku. Napˇr. pˇri hledán´ı aut by bylo ideáln´ı, aby na kaˇzdém obrázku bylo auto, ovˇsem vyhledávac´ı sluˇzby nab´ıdnou obrázky vzhledovˇe ne zcela odpov´ıdaj´ıc´ı této pˇredstavˇe. 31

5.1

Popis programu pro pˇ r´ıkazovou ˇ r´ adku

Program pro pˇr´ıkazovou ˇrádku je nejbl´ıˇze implementaci vlastn´ıho algoritmu a tud´ıˇz poskytuje nejv´ıce moˇznost´ı práce s mozaikou i databázemi obrázk˚ u. Nápovˇeda ke vˇsem parametr˚ um programu se z´ısk´ av´ a pˇr´ıkazem: Mosaic.Console.exe --help Vytvoˇren´ı souboru auta.db z adresáˇre auta a nastaven´ı kl´ıˇcového slova na car : Mosaic.Console.exe --keyword car --lookup auta --load_files --save_db auta.db Vytvoˇren´ı mozaiky z obrázku male auto.png s databáz´ı ze souboru auta.db jako JPEG do souboru velke auto.jpg se vstupn´ı velikost´ı 16 × 16 pixel˚ u a v´ ystupn´ı velikost´ı vloˇzen´ ych obrázk˚ u 32 × 32 pixel˚ u: Mosaic.Console.exe --input male_auto.png --output velke_auto.jpg --jpeg --load_db auta.db --tile 16 --size 32

5.2

Popis webov´ e sluˇ zby

5.3

Uk´ azky v´ ystup˚ u

Ke shodnocen´ı v´ ysledku bakaláˇrské práce pˇrikl´ ad´ am dvˇe v´ ysledné mozaiky (obrázky 5.1 a 5.2).

5.4

ASCII art

Jedna z moˇzn´ ych vyuˇzit´ı této bakal´ aˇrské práce je moˇznost pouˇz´ıvat ji k tvoˇren´ı ASCII artu (skládán´ı p´ısmen a znak˚ u tak, aby z vˇetˇs´ı dálky p˚ usobil v´ ysledek jako obrázek). Pokud se jako vstupn´ı databáze pouˇzij´ı obrázky tvoˇrené p´ısmeny je pomoc´ı programu moˇzné vygenerovat ASCII art. S vhodnou databáz´ı je dokonce moˇzné vygenerovat barevnou verzi. Ukázka za pouˇzit´ı ˇcernob´ılé databáze je na obrázku 5.3.

32

↑ Vstupní obrázek → Výstupní obrázek vstupní dlaždice 8 × 8 pixelů, výstup 32 × 32, použity obrázky nalezené pomocí Google pro dotaz “face” ↓ Tentýž výstup s detailem tváře

Obrázek 5.1: Pˇr´ıklad vstupu a v´ ystupu

33

↑ →

↓

Obrázek 5.2: Porshe Cayman

34

↑ Vstupní obrázek - Les v Soběšicích → Výstupní obrázek - ukázka ASCII artu ↓ Detail části obrázku lesa - obrázek zobrazuje část kmene a využití velké části znaků

Obrázek 5.3: Dalˇs´ı z moˇznost´ı vyuˇzit´ı – ASCII art

35

Kapitola 6

Z´ avˇ er 6.1

Moˇ zn´ a rozˇ s´ıˇ ren´ı

Na závˇer uvedu nˇekolik dalˇs´ıch moˇznost´ı na dalˇs´ı vylepˇsen´ı a rozˇs´ıˇren´ı. Tyto nápady vznikly pˇri implementaci a jejich zaˇclenˇen´ı by bylo nároˇcné a vyˇzadovalo by mnoho zmˇen do jiˇz zpracovan´ ych postup˚ u. Dalˇs´ı moˇzn´ a rozˇs´ıˇren´ı jdou mimo rozsah a zadán´ı této bakal´ aˇrské práce.

6.1.1

Podpora dalˇ s´ıch grafick´ ych form´ at˚ u

Aktuáln´ı implementace podporuje ˇcten´ı a zápis pouze do dvou r˚ uzn´ ych formát˚ u – JPEG a PNG. Tyto dva formáty byly vybrány, protoˇze vˇetˇsina obrázk˚ u je dostupn´ ych právˇe v tˇechto formátech, dovoluj´ı postupn´ y zápis do souboru (v pamˇeti nemus´ı b´ yt uchov´ an cel´ y obrázek), existuje volnˇe ˇsiˇritelná implementace a pouˇzit´ı v projektech je jednoduché. Dalˇs´ım rozˇs´ıˇren´ım by mohla b´ yt podpora ˇcten´ı i zápisu dalˇs´ıch rastrov´ ych obrázk˚ u – napˇr. GIF, BMP nebo TIFF.

6.1.2

Pouˇ zit´ı velk´ ych fotografi´ı a jejich ˇ c´ ast´ı

Jako rozˇs´ıˇren´ı by také mohlo b´ yt doprogramov´ ano naˇcten´ı velké fotografie a jej´ı rozˇrezn´ an´ı na menˇs´ı. Problémem je v´ ybˇer obrázk˚ u s dostateˇcnˇe v´ yrazn´ ymi jednotliv´ ymi ˇc´ astmi. ˇ asteˇcnˇe v aplikaci podpora pro rozˇrez´ C´ av´ an´ı existuje, jej´ı pouˇzit´ı a zdokumentov´ an´ı naráˇz´ı na problém nesluˇcitelnosti s aktuáln´ım rozvrˇzen´ım databáze a s vnitˇrn´ımi pochody, které se staraj´ı o cachován´ı obrázk˚ u. Toto rozˇs´ıˇren´ı se sp´ıˇse ukázalo jako vhodn´ y test pro správnou funkˇcnost algoritmu, kdy byl proveden pokus o sestaven´ı obrázku z jeho vlastn´ıch ˇc´ ast´ı. Poˇctem u ´spˇeˇsn´ ych um´ıstˇen´ım ˇcásti na p˚ uvodn´ı m´ısto lze mˇeˇrit správnost a pˇresnost algoritmu.

6.1.3

Sd´ılen´ı pamˇ eti

Naˇcten´ı databáze do pamˇeti z disku je relativnˇe v´ ykonovˇe nároˇcn´ a operace, nav´ıc v aktuáln´ı implementaci je tato struktura vytváˇrena pro kaˇzdé zpracov´ an´ı vytváˇrena zvláˇst’. Toto implementaˇcn´ı rozhodnut´ı bylo zvoleno kv˚ uli tomu, ˇze je moˇzné pouˇz´ıvat r˚ uzné datab´ aze obrázk˚ u pˇri vytváˇren´ı. Nav´ıc by mohl vzniknout problém pˇri cachov´ an´ı (aktuálnˇe to znamená naˇcten´ı a zmˇena velikosti na poˇzadované rozmˇery – tyto hodnoty se mohou mezi poˇzadavky mˇenit, musel by b´ yt zvolen jin´ y pˇr´ıstup pˇri implementaci).

36

Návrh zlepˇsen´ı je takov´ y, ˇze tato databáze v pamˇeti by mohla b´ yt stabiln´ı, nemˇela by se vytváˇret znovu pˇri kaˇzdém poˇzadavku, a pokud by program bˇeˇzel jako sluˇzba, mohla by tato pamˇet’ b´ yt vyuˇz´ıvána opakovanˇe.

6.1.4

Hash obr´ azk˚ u

Aktuáln´ı implementace je sice rychl´ a, ale vyhledáv´ an´ı podobn´ ych obrázk˚ u by pˇri nárustech databáze mohlo vést k problém˚ um s rychlost´ı. K vyˇreˇsen´ı tohoto problému by mohlo b´ yt vyuˇzit´ı obrázkového hashe (viz. zdroj [17]). Hash obrázk˚ u by mˇel m´ıt takové vlastnosti, ˇze vzhledovˇe podobné obrázky by mˇely m´ıt taktéˇz podobné hashe. A naopak rozd´ılné obrázky by hash mˇely m´ıt co nejv´ıce rozd´ılné. Pˇri hledán´ı podobn´ ych obrázk˚ u by se mohlo hledat podle hash˚ u a pˇri pouˇzit´ı správn´ ych algoritm˚ u, by mohlo doj´ıt k urychlen´ı hledán´ı.

6.1.5

Rozestavˇ en´ı obr´ azk˚ u

(a)

(b)

Obrázek 6.1: Moˇznost pouˇz´ıt i jiné rozestavˇen´ı dlaˇzdic Aktuáln´ı implementace poˇc´ıt´ a se ˇctvercov´ ym rozestavˇen´ım mozaiky. Jako rozˇs´ıˇren´ı do budoucna by v´ yslená mozaika mohla b´ yt sklád´ ana z jin´ ych tvar˚ u, které lze uspoˇr´ adat do pravidelné mˇr´ıˇzky. Na obrázku 6.1 je provedeno visuáln´ı porovn´ an´ı rozm´ıstˇen´ı stejn´ ych barev do pravidelné ˇctvercové a ˇsesti´ uheln´ıkové mˇr´ıˇzky.

6.1.6

Grafick´ e uˇ zivatelsk´ e rozhran´ı

Moˇzn´ ym rozˇs´ıˇren´ım by mohlo b´ yt samostatné uˇzivatelské rozhran´ı nezávislé na SQL databázi. Moˇzn´ y vzhled je uveden na obrázku 6.2. Vytvoˇren´ı uˇzivatelského rozhran´ı je d´ıky modularitˇe projektu moˇzné vystavˇet na Mosaic.Lib.Static (v pˇr´ıpadˇe pouˇzit´ı C/C++ nebo i jiného jazyka, kter´ y je moˇzn´ y propojit s moduly psan´ ymi v jazyce C) nebo Mosaic.Class pro .NET platformu (architektura Win32, v pˇr´ıpadˇe portován´ı Mosaic.Lib.Dynamic i dalˇs´ı).

6.1.7

Zobrazen´ı velk´ ych obr´ azk˚ u online

Pro webovou sluˇzbu je moˇzné pouˇz´ıt prohl´ıˇzeˇc velk´ ych obrázk˚ u. Uˇzivatel pak m˚ uˇze plynule procházet obrázkem, zvˇetˇsovat a zmenˇsovat a pˇritom jsou k nˇemu ze serveru pˇren´ aˇsena pouze data minimálnˇe nutná pro zobrazen´ı. Takov´ ymto projektem je napˇr´ıklad IIPImage http://iipimage.sourceforge.net/

37

Obrázek 6.2: Moˇzn´ y vzhled uˇzivatelského rozhrann´ı

6.1.8

Rozˇ s´ıˇ ren´ı webov´ e sluˇ zby

Aktuáln´ı implementace webové sluˇzby nepˇrin´ aˇs´ı ˇz´ adn´ y mechanismus zabezpeˇcen´ı ˇci uˇzivatelsk´ ych u ´ˇct˚ u. Pˇri implementaci by bylo moˇzné pˇridat moˇznost zvolen´ı veˇrejné nebo neveˇrejné mozaiky nebo moˇznost zas´ıl´ an´ı informace o zpracov´ an´ı mozaiky na email. V pˇr´ıpadˇe opravdového nasazen´ı by bylo potˇreba vytvoˇrit zabezpeˇcenou administraci, kde by bylo moˇzné poˇzadavky upravovat a mazat. Taktéˇz by mˇelo b´ yt moˇzné spravovat bˇeh samotné sluˇzby – moˇznost pozastavit, resetovat a znovu spustit.

38

6.2

Z´ avˇ er

P˚ uvodn´ı návrh se podaˇrilo u ´spˇeˇsnˇe implementovat. Pˇred vlastn´ım zadán´ım práce jsem mˇel k dispozici základn´ı pro osobn´ı potˇreby napsanou implementaci algoritmu, takˇze jsem mˇel z ˇceho vych´ azet a plno zkuˇsenost´ı jsem jiˇz z´ıskal dˇr´ıve. Mohl jsem se tedy soustˇredit na rozˇsiˇrov´ an´ı a zlepˇsov´ an´ı. Opravdu velkou v´ yzvou byly vˇsechny pouˇzité optimalizace, p˚ uvodn´ı implementace byla napsána narychlo a nikdy se nepoˇc´ıtalo s t´ım, ˇze by mohla bˇeˇzet jako sluˇzba (tedy s minimáln´ı pamˇet’ovou nároˇcnost´ı a bez memory leak˚ u). Pouˇzit´ı vˇetˇsiny algoritm˚ u bylo znovu zváˇzeno a vˇetˇsinou byly algoritmy nahrazeny jin´ ymi nebo pˇreps´ any. Dalˇs´ım velk´ ym u ´kolem bylo tento p˚ uvodnˇe v jazyce C psan´ y program zprovoznit tak, aby fungoval a spolupracoval s kódem pro .NET framework. K tomuto byla pouˇzita jako mezistupeˇ n .dll knihovna. Následné spojen´ı s databáz´ı a zapracov´ an´ı jako jednoduch´ y informaˇcn´ı systém bylo jiˇz d´ıky pouˇzit´ ym technologi´ım relativnˇe jednoduché. P˚ uvodnˇe jsem zvaˇzoval m´ısto pouˇzit´ı Microsoft Internet Information Services (IIS) moˇznost spolupráce s Apache serverem a naprogramován´ı webové sluˇzby v PHP. Nakonec jsem se rozhodnul pro tuto variantu hlavnˇe kv˚ uli osobn´ımu zájmu o .NET platformu. Dalˇs´ı velmi zaj´ımavou ˇcást´ı je Formatter (kapitola 3.8), kter´ y velmi zjednoduˇsil moˇznost práce s databáz´ı. Moˇzná k ˇcasu v´ yvoje a testov´ an´ı se jedná o zbyteˇcnˇe sloˇzit´ y nástroj. Jeho znovuvyuˇzitelnost je ovˇsem z mého pohledu velk´ a a zjednoduˇsuje k základn´ım operac´ım nad relaˇcn´ı databáz´ı. V závˇeru jsem se pokusil jeˇstˇe naznaˇcit moˇzn´ a dalˇs´ı vylepˇsen´ı a cesty, kudy by dalˇs´ı v´ yvoj mohl pokraˇcovat. Vytváˇren´ı mozaiky je velice zaj´ımavou ˇcinnost´ı a mnoho lid´ı obrázkové mozaiky fascinuj´ı.

39

Literatura [1] Troelsen, A.: C# a .NET 2.0 profesion´ alnˇe. 1. vydán´ı, Brno: ZONER Press, 2006, 1198 s, ISBN 80-86815-42-0 [2] IJG.ORG: Independent JPEG Group. [online], [cit. 2008-11-27], http://www.ijg.org/ [3] The Client Server Architecture. [online], [cit. 2009-01-10], http: //www.webdevelopersnotes.com/basics/client_server_architecture.php3 [4] Leach P., Microsoft, Mealling M, Refactored Networks, LLC, Salz E, DataPowe Technology Inc: RFC 4122: A Universally Unique IDentifier (UUID) URN Namespace [online]. [ˇcervenec 2005], [cit. 2008-12-15], [online], http://www.ietf.org/rfc/rfc4122.txt [5] Fieldng R., UC Irvine, Gettys J., Compaq/W3C, Mogul J., Frystyk H., W3C/MIT, Masinter L., Xerox, Leach P., Microsoft, Berners-Lee T.: RFC 2116: Hypertext Transfer Protocol – HTTP/1.1, [ˇcerven 1999], [cit. 2008-12-26], [online], http://www.ietf.org/rfc/rfc2616.txt [6] Microsoft Corporation: MSDN: Guid Structure (System). [online], [cit. 2008-12-15], http://msdn.microsoft.com/en-us/library/system.guid.aspx [7] Microsoft Corporation: Dynamic-Link Libraries. [online], [cit. 2008-12-18], http://msdn.microsoft.com/en-us/library/ms682589.aspx [8] Microsoft Corporation: Common Language Runtime. [online], [cit 2008-01-04], http://msdn.microsoft.com/en-us/library/8bs2ecf4.aspx [9] Microsoft Corporation: ASP.NET State Management. [online], [cit 2008-01-05], http://msdn.microsoft.com/en-us/library/y5y3c2c5(VS.80).aspx [10] ECMA-334: C# Language Specification [online], 4th edition, [cit. 2009-01-03], http://www.ecma-international.org/publications/standards/Ecma-334.htm [11] Thyssen, Anthony: Hints, Tips and Notes on bulk sorting of images [online], [cit. 2008-01-06], http://www.cit.gu.edu.au/~anthony/info/graphics/image_comparing [12] Tezaur, Radka: Co se dˇeje, kdyˇz se obr´ azky zmenˇsuj´ı a zvˇetˇsuj´ı [online]. 2001-12-10, [cit. 2009-01-08] http://www.paladix.cz/clanky/ co-se-deje-kdyz-se-obrazky-zmensuji-a-zvetsuji.html

40

[13] Barvy: Vlnové délky [online]. [cit. 2009-01-08] http://barvy.xf.cz/teorie/vlnove-delky ˇ ak, Karel: Historie relaˇcn´ıch datab´ [14] Z´ az´ı [online], 2001-10-19, [cit 2008-01-08], http://www.root.cz/clanky/historie-relacnich-databazi/ [15] Horváth, Tomáˇs: Teoretický u ´vod do relaˇcn´ıch datab´ az´ı [online], 2007-11-08, [cit. 2008-01-09], http://programujte.com/index.php?akce=clanek&cl= 2007110801-teoreticky-uvod-do-relacnich-databazi [16] Reolofs, Greg: Into to PNG Featurs [online], 2008-01-30, [cit. 2009-01-10], http://www.libpng.org/pub/png/pngintro.html [17] Johnson M.: Image Hashing. [online], [cit. 2008-01-12], http://www.eecs.berkeley.edu/~mjohnson/abstracts/hashing.htm

41

Pˇ r´ılohy Pˇ riloˇ zen´ e DVD Na pˇriloˇzeném DVD se nacház´ı: • Zdrojové soubory – kompletn´ı zdrojové soubory ke vˇsem modul˚ um v jazyce C, C#, PHP, SQL skripty na vytvoˇren´ı databáze, zkompilované verze pouˇzit´ ych knihoven (libpng, jpeglib) • Kompilovaná verze – binárn´ı spustitelné verze program˚ u (program pro pˇr´ıkazovou ˇrádku, sluˇzba, webov´ y projekt pro IIS), nav´ıc je k dispozici jednoduché GUI • Databáze obrázk˚ u – pˇredpˇripravené databáze s motivy: auta, pˇr´ıroda, tváˇre, ovoce, albumarty, fonty pro ASCII art (ˇcernob´ıl´ y i barevn´ y) • Ukázky vstupu i v´ ystupu – vˇsechny vstupn´ı i v´ ysledné obrázky pouˇzité v této bakaláˇrské práci, dále pak i dalˇs´ı, vˇse v p˚ uvodn´ım vysokém rozliˇsen´ı • Prezentaˇcn´ı video – ukázka funkˇcnosti bakal´ aˇrské práce: vloˇzen´ı poˇzadavku, zobrazen´ı pr˚ ubˇehu v´ ypoˇctu a v´ ysledného obrázku • Video – moˇzné vyuˇzit´ı této bakal´ aˇrské práce vytvoˇrené pomoc´ı programu Video.Animator

42

FAKULTA INFORMAČNÍCH TECHNOLOGIÍ

Recommend Documents