Lokalizace osob v budově s

ˇ ´ Cesk e ´ vysoke ˇen´ı uc ´ technicke v Praze Fakulta elektrotechnick´ a Kybernetika a robotika

Bakal´ aˇrsk´ a pr´ ace

Lokalizace osob v budovˇ es vyuˇ zit´ım bezdr´ atov´ e technologie Jan Trejbal

Kvˇ eten 2015 Vedouc´ı pr´ ace: Ing. Karel Koˇsnar, Ph.D.

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra kybernetiky

ZADÁNÍ BAKALÁŘSKÉ PRÁCE Student:

Jan T r e j b a l

Studijní program:

Kybernetika a robotika (bakalářský)

Obor:

Robotika

Název tématu:

Lokalizace osob v budově s využitím bezdrátové technologie

Pokyny pro vypracování: 1. Seznamte se s metodami lokalizace za přítomnosti neurčitosti. 2. Naimplementujte vybranou metodu využívající skryté markovovské modely. 3. Proveďte experimentální ověření. 4. Vyhodnoťte kvalitu implementované metody.

Seznam odborné literatury: [1] Zahid F., Rosdiadee N., and Mahamod I., “Recent Advances in Wireless Indoor Localization Techniques and System,” Journal of Computer Networks and Communications, vol. 2013, Article ID 185138, 12 pages, 2013. doi:10.1155/2013/185138 [2] Arthi, R.; Murugan, K., "Localization in Wireless Sensor Networks by Hidden Markov Model," Advanced Computing (ICoAC), 2010 Second International Conference on , vol., no., pp.14,18, 14-16 Dec. 2010 doi: 10.1109/ICOAC.2010.5725355 [3] Ibrahim, M., and Moustafa Y.. "A hidden markov model for localization using low-end gsm cell phones."Communications (ICC), 2011 IEEE International Conference on. IEEE, 2011.

Vedoucí bakalářské práce: Ing. Karel Košnar, Ph.D. Platnost zadání: do konce letního semestru 2015/2016

L.S.

doc. Dr. Ing. Jan Kybic vedoucí katedry

prof. Ing. Pavel Ripka, CSc. děkan V Praze dne 20. 1. 2015

Prohl´ aˇsen´ı Prohlaˇsuji, ˇze jsem pˇredloˇzenou práci vypracoval samostatnˇe a ˇze jsem uvedl veˇskeré pouˇzité informaˇcn´ı zdroje v souladu s Metodick´ ym pokynem o dodrˇzován´ı etick´ ych princip˚ u pˇri pˇr´ıpravˇe vysokoˇskolsk´ ych závˇereˇcn´ ych prac´ı.

V Praze dne 20. 5. 2015

i

Podˇ ekov´ an´ı Rád bych podˇekoval Ing. Karlu Koˇsnarovi, Ph.D. za veden´ı této bakaláˇrské práce a za cenné rady, d´ıky kter´ ym jsem zdárnˇe dokonˇcil tuto bakaláˇrskou práci. Rád bych téˇz podˇekoval rodinˇe za podporu a trpˇelivost po dobu mého studia.

ii

Abstrakt Tato bakaláˇrská práce se zab´ yvá lokalizac´ı osob v budovˇe s vyuˇzit´ım bezdrátové technologie. Lokalizace je ˇreˇsena s vyuˇzit´ım skryt´ ych Markovsk´ ych model˚ u a porovnávána je s k-NN klasifikac´ı. Pro lokalizaci bylo v rámci práce napsáno nˇekolik program˚ u a aplikac´ı v jazyku C++ a PHP. V závˇeru je porovnáno nˇekolik konfigurac´ı aplikace a vyhodnocena nejvhodnˇejˇs´ı konfigurace. Kl´ıˇcová slova: Skryté Markovské modely, lokalizace, matlab, C++, PHP, relaˇcn´ı databáze

Abstract This thesis deals with the localization of people in buildings using wireless technology. Localization is solved using hidden Markov models and compares them with the k-NN classification. I wrote several programs and applications which were written in C++ and PHP. I compared several configuratios of applications and I evaluated the most appropriate configuration. Keywords: Hidden Markov models, localization, matlab, C++, PHP, relational database

iii

Obsah 1

´ Uvod

1

1.1 Definice u ´lohy . . 1.2 Metody lokalizace 1.2.1 Triangulace 1.2.2 K-NN . . .

2

3

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

3

2.1 Trénován´ı modelu . . . . . . . . . . . . . . . . . . . . . . 2.2 Pouˇzit´ı modelu . . . . . . . . . . . . . . . . . . . . . . . .

3 5

Jednotky IMA

6

Vys´ılaˇce . . . . Pˇrij´ımaˇce . . . ˇ ıd´ıc´ı jednotka R´ Zpracován´ı dat

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Implementace

6 6 7 7

10

4.1 Sbˇer dat . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Ukládán´ı informac´ı v pr˚ ubˇehu mˇeˇren´ı . . . . . . . . 4.1.1.1 Pˇripojen´ı k u ´loˇziˇsti . . . . . . . . . . . . . . 4.1.1.2 Pˇripojen´ı k ˇr´ıd´ıc´ı jednotce IMA . . . . . . . 4.1.1.3 Parsován´ı proudu dat z ˇr´ıd´ıc´ı jednotky . . . 4.1.2 Definován´ı fyzického prostˇred´ı . . . . . . . . . . . . 4.2 Uˇcen´ı a rozpoznáván´ı ze sebran´ ych dat . . . . . . . . . . 4.2.1 Pˇripojen´ı k u ´loˇziˇsti . . . . . . . . . . . . . . . . . . 4.2.2 Pˇripojen´ı k Matlabu . . . . . . . . . . . . . . . . . 4.2.3 Pˇripraven´ı dat pro trénován´ı a rozpoznáván´ı . . . . 4.2.3.1 Proˇciˇstˇen´ı dat . . . . . . . . . . . . . . . . 4.2.3.2 Kvantován´ı dat . . . . . . . . . . . . . . . . 4.2.3.3 Pˇrekódován´ı dat . . . . . . . . . . . . . . . 4.2.4 Vystavˇen´ı modelu z dat . . . . . . . . . . . . . . . . 4.2.5 Rozpoznán´ı nejpravdˇepodobnˇejˇs´ı sekvence stav˚ u z dat a natrénovaného modelu . . . . . . . . . . . . . 4.3 Jiná metoda uˇcen´ı a rozpoznáván´ı . . . . . . . . . . . . . 4.4 Export v´ ysledk˚ u . . . . . . . . . . . . . . . . . . . . . . .

5

1 1 1 1

Skryt´ e Markovsk´ e modely

3.1 3.2 3.3 3.4

4

. . . .

Experimenty

10 10 10 11 11 12 13 14 14 15 15 15 15 15 16 16 16

17

5.1 Sbˇer dat . . . . . . . . . . . . . . . . . . . . . . . . . . . iv

17

5.2 Trénován´ı a rozpoznáván´ı z dat . . . . . . . . . . . . . . .

18

6

V´ ysledky

22

7

Z´ avˇ er

26

Literatura

27

v

Seznam obr´ azk˚ u 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Ukázka pouˇzit´ı triangulace [1] . . . . . . . . . . . . . . . . Ukázka vyhodnocen´ı pomoc´ı k-NN . . . . . . . . . . . . . Ukázkové schéma tranzitivit HMM [2] . . . . . . . . . . . . Nákres struktury IMA . . . . . . . . . . . . . . . . . . . . Vys´ılaˇc IMA [3] . . . . . . . . . . . . . . . . . . . . . . . . Pˇrij´ımaˇc IMA [3] . . . . . . . . . . . . . . . . . . . . . . . Proud dat z ˇr´ıd´ıc´ı jednotky . . . . . . . . . . . . . . . . . . ER diagram . . . . . . . . . . . . . . . . . . . . . . . . . . Nastaven´ı mapy . . . . . . . . . . . . . . . . . . . . . . . . Aplikace pouˇz´ıvaná pˇri uˇcen´ı . . . . . . . . . . . . . . . . . Mapa s vyznaˇcen´ ymi pˇrij´ımaˇci . . . . . . . . . . . . . . . . Porovnán´ı 1. mˇeˇren´ı, uˇcen´ı nad 0x4e, rozpoznáván´ı nad 0x4a Porovnán´ı 1. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4e, rozpoznáván´ı nad 0x4a Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e - rozdˇeleno do skupin . . . . . . . . . . . . . . . . . . . . . Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e, 3 kvantily . . . . . . . . . . . . . . . . . . . . . . . . . . . Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e, 5 kvantil˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

2 2 4 6 7 8 9 11 13 14 17 22 22 23 23 24 24 25

Kapitola 1

´ Uvod 1.1

Definice u ´lohy

C´ılem mé bakaláˇrské práce je lokalizovat osoby v budovˇe s pˇresnost´ı na m´ıstnosti s vyuˇzit´ım v budovˇe rozm´ıstˇeného hardwaru. Mezi rozm´ıstˇen´ y hardware patˇr´ı pˇrij´ımaˇce a lokalizovanou osobou nesen´ y vys´ılaˇc. Lokalizovat osobu v budovˇe je nesnadné, pˇredevˇs´ım d´ıky interferenc´ım vznikaj´ıc´ım pr˚ uchodem signálu z nesen´ ych vys´ılaˇc˚ u skrz stˇeny k pˇrij´ımaˇc˚ um. Tento hardware lze pˇr´ıpadnˇe zamˇenit za WiFi access pointy a mobiln´ı telefony na nˇe pˇripojené. D´ıky ˇcemu lze sn´ıˇzit poˇrizovac´ı náklady vyuˇzit´ım existuj´ıc´ı infrastruktury.

1.2

Metody lokalizace

Mezi uvaˇzované metody lokalizace, ˇci klasifikace pro tuto bakaláˇrskou práci patˇr´ı napˇr. triangulace, k-NN klasifikace a skryté Markovské modely.

1.2.1

Triangulace

Lokalizace pomoc´ı triangulace vycház´ı z geometrie a z vlastnost´ı troj´ uheln´ıku. V této metodˇe se vyuˇz´ıvá znalosti vzdálenost´ı mezi znám´ ymi body, mezi znám´ ymi body zmˇeˇr´ıme u ´hly v bodˇe u kterého chceme urˇcit polohu, z tˇechto u ´hl˚ u lze vypoˇc´ıtat jednoduchou matematikou poloha, pro ilustraci nákres metody na obrázku 1, na kterém je zachycena triangulace pro stanoven´ı vzdálenosti lodi od pobˇreˇz´ı v které po zmˇeˇren´ı u ´hl˚ u staˇc´ı vyuˇz´ıt vzorec: d = l ∗ sin(α) ∗ sin(β) Pro lokalizaci osob v budovˇe tato metoda nen´ı vhodná. Mˇeˇren´ı u ´hl˚ u mezi znám´ ymi body v budovˇe je velice ˇspatnˇe realizovatelné. Pouˇzit´ı sil signál˚ u pˇrepoˇcten´ ych na vzdálenost by pouˇzit´ı metody umoˇznila, tato metoda by vˇsak ˇspatnˇe reagovala na r˚ uznˇe tlusté, nebo mokré stˇeny, které ovlivˇ nuj´ı signál jimi prostupuj´ıc´ı.

1.2.2

K-NN

Lokalizace (klasifikace) pomoc´ı k-NN1 [4] je bˇeˇznˇe uˇz´ıvanou metodou, d´ıky jej´ı jednoduchosti. V této metodˇe se urˇc´ı nejvhodnˇejˇs´ı kandidát pomoc´ı nejmenˇs´ı vzdálenosti od 1

Nearest Neighbour classification: Klasifikace podle nejbliˇzˇs´ıch soused˚ u

1/29

1.2 METODY LOKALIZACE

Obrázek 1: Ukázka pouˇzit´ı triangulace [1] ’k’ prvk˚ u. Z tohoto postupu plyne nutnost existence metody vyˇc´ısluj´ıc´ı vzdálenost mezi jednotliv´ ymi prvky. Náhled vyhodnocován´ı pomoc´ı k-NN je na obrázku 2, na kterém zelené koleˇcko znázorˇ nuje prvek, kter´ y chceme ohodnotit, ˇcervené a ˇcerné kruhy znázorˇ nuj´ı referenˇcn´ı vzorky. Pˇri pouˇzit´ı 1-NN znázorˇ nuje vyhodnocen´ı ˇzlut´ y kruh, jako ohodnocen´ı by byl zvolen ˇcerven´ y kruh. Pouˇzit´ı 3-NN znázornˇené zelen´ y kruhem oproti 1-NN vˇsak ohodnot´ı prvek jako ˇcern´ y. Tuto metodu lze vyuˇz´ıt, bohuˇzel vˇsak tato metoda nezohledˇ nuje reáln´ y pohyb osob budovou. Umoˇzn ˇuje tak napˇr´ıklad procházen´ı zd´ı budov, nebo skoky mezi patry bez pouˇzit´ı schodiˇstˇe.

Obrázek 2: Ukázka vyhodnocen´ı pomoc´ı k-NN

2/29

Kapitola 2

Skryt´ e Markovsk´ e modely Skryté Markovské modely (HMM) 2 jsou rozˇs´ıˇren´ım Markovsk´ ych model˚ u [5], v kter´ ych ˇretˇez stav˚ u nen´ı pˇr´ımo pozorovateln´ y. Oproti napˇr´ıklad triangulaci zm´ınˇené v sekci 1.2.1 a K-NN ze sekce 1.2.2 má HMM v´ yhodu ve specifikován´ı moˇzn´ ych pˇrechod˚ u mezi stavy (v naˇsem pˇr´ıpadˇe m´ıstnosti), respektive v moˇznosti jejich zamezen´ı viz obrázek 3 (tento graf lze popsat matic´ı tranzitivity) z kterého je zˇrejmé, ˇze neexistuje pˇrechod mezi π1 a π6 , ale ˇze existuje pˇrechod z π1 do π2 nebo π5 . Definován´ım pˇrechod˚ u mezi stavy, tak lze zamezit chybám zp˚ usoben´ ym interferenc´ı a následn´ ym ˇspatn´ ym urˇcen´ım stavu. Tyto chyby jsou automaticky eliminovány d´ıky absenci pˇr´ımého pˇrechodu mezi stavy (napˇr. pro pˇrechod z m´ıstnosti do m´ıstnosti je nutné vyuˇz´ıt chodbu). Jelikoˇz nemáme pˇr´ımou informaci o aktuáln´ım stavu (m´ıstnosti) nad pˇrechody mezi stavy vybudujeme dalˇs´ı matici (matice emisivity), která udává pravdˇepodobnost, s jakou dan´ y stav odpov´ıdá vektoru sil signál˚ u z pˇrij´ımaˇc˚ u. Matematick´ y model HMM pro náˇs pˇr´ıpad m˚ uˇzeme reprezentovat pomoc´ı S, V , T , E a O, kde: • S = {S1 , S2 , ..., SN } - Si jsou jednotlivé m´ıstnosti a N = |S| v S jsou tedy vˇsechny m´ıstnosti, • V = {v1 , v2 , ..., vM } - vi jsou jednotlivá pozorován´ı (upravené s´ıly signál˚ u) a M = |V | ve V jsou tedy vˇsechna z´ıskaná data, • T = {tij } je matice tranzitivit v které kaˇzd´ y prvek tij odpov´ıdá pravdˇepodobnosti pˇrechodu z Si do Sj , • E = {eij } je matice emisivit, v které i < N a j < Q kde Q je poˇcet vˇsech moˇzn´ ych pozorován´ı, eij pak odpov´ıdá pravdˇepodobnosti emise ze stavu do daného pozorován´ı a • O = {o1 , o2 , ..., oM } je pak hledaná sekvence m´ıstnost´ı.

2.1

Tr´ enov´ an´ı modelu

Pro trénován´ı modelu jsem si vybral interativn´ı metodu [6]. Trénován´ı pomoc´ı této metody lze zjednoduˇsenˇe popsat tˇemito kroky: 1. Odhad poˇcáteˇcn´ıch pravdˇepodobnost´ı - v základu rovnomˇerné. 2

Hidden Markov Model: Skryté Markovské modely

3/29

´ ´ Í MODELU 2.1 TRENOV AN

Obrázek 3: Ukázkové schéma tranzitivit HMM [2]

4/29

ˇ Í MODELU 2.2 POUZIT 2. Na základˇe emisivity a tranzitivity urˇcen´ı nejpravdˇepodobnˇejˇs´ı sekvence stav˚ uz vektor˚ u sil signál˚ u. 3. Odhad nov´ ych pravdˇepodobnost´ı na základˇe oˇcekávan´ ych a vypoˇcten´ ych sekvenc´ı stav˚ u. 4. Provád´ıme n iterac´ı 2. a 3. bodu algoritmu do doby, neˇz jsme spokojeni s odchylkou . Po dokonˇcen´ı trénován´ı máme pˇripraven model pro rozpoznáván´ı, tj. máme naplnˇeny S, T a E ze sekce 1.2.2. Pro u ´plnost zm´ın´ım existenci Baumova-Welchova algoritmu [7], ten jsem vˇsak v práci nevyuˇzil, lze ho vˇsak napˇr. vyuˇz´ıt pro dalˇs´ı zpˇresˇ nován´ı modelu.

2.2

Pouˇ zit´ı modelu

Pro nalezen´ı nejpravdˇepodobnˇejˇs´ı cesty na základˇe vektor˚ u sil signál˚ u a natrénovaného modelu jsem se rozhodl vyuˇz´ıt Viterbiho algoritmus [8], kter´ y je vhodn´ ym algoritmem, pro urˇcen´ı nejpravdˇepodobnˇejˇs´ı sekvence stav˚ u. Tento algoritmus se vyuˇz´ıvá napˇr´ıklad v GSM, CDMA, satelitn´ı komunikaci a dalˇs´ıch systémech vyuˇz´ıvaj´ıc´ıch digitáln´ı kódován´ı [9]. Do tohoto algoritmu vstupuj´ı data pˇripravená z trénován´ı, tj. S, T a E, dále pak seznam pozorován´ı V , v´ ystupem je pak hledaná sekvence O.

5/29

Kapitola 3

Jednotky IMA Pro pokusy mi byl umoˇznˇen pˇr´ıstup k jednotkám od firmy IMA3 , které obsahuj´ı ˇr´ıd´ıc´ı jednotku, pˇrij´ımaˇce a vys´ılaˇce. Nákres struktury hardwaru je na obrázku 4.

Obrázek 4: Nákres struktury IMA

3.1

Vys´ılaˇ ce

Vys´ılaˇce jsou pˇrenosné, zhruba o velikosti pageru. Na svém tˇele maj´ı um´ıstˇené tlaˇc´ıtko, po jeho stisku dojde k neprodlenému vyslán´ı signálu z vys´ılaˇce. Vys´ılaˇc je k nahlédnut´ı na obrázku 5. Vys´ılaˇce vys´ılaj´ı signál v pravideln´ ych intervalech ihned po zapnut´ı. Jeden z vys´ılaˇc˚ u byl v dobˇe testován´ı nastaven na pravidelné vys´ılán´ı signálu jednou za 1s, druh´ y 4x za stejnou dobu. Signál je vys´ılan´ y v pásmu 2,4GHz (tedy volné pásmo).

3.2

Pˇrij´ımaˇ ce

Pˇrij´ımaˇce jsou nepˇrenosné, o velikosti bˇeˇzného notebookového zdroje. Na svém tˇele maj´ı dva SMA konektory pro antény, konektor pro napájen´ı, vyp´ınaˇc a diodu indikuj´ıc´ı 3

Institut Mikroelektronick´ ych Aplikac´ı

6/29

´ Í DAT 3.4 ZPRACOVAN

Obrázek 5: Vys´ılaˇc IMA [3] zapnut´ı pˇrij´ımaˇce. Pˇrij´ımaˇc je k nahlédnut´ı na obrázku 6. Tyto pˇrij´ımaˇce se automaticky spoj´ı s ˇr´ıd´ıc´ı jednotkou, které pˇredávaj´ı sebraná data.

3.3

ˇ ıd´ıc´ı jednotka R´

ˇ ıd´ıc´ı jednotka je mikro PC, které má na svém tˇele napájec´ı konektor, s´ıt’ov´ R´ y konektor (RJ45) a USB konektor. Do USB konektoru je zapojen ZigBee pˇrij´ımaˇc, kter´ y sb´ırá data zaslaná z pˇrij´ımaˇc˚ u. Tato jednotka pˇrijatá data odes´ılá jako proud dat.

3.4

Zpracov´ an´ı dat

Zpracován´ı dat prob´ıhá v této sekvenci: • Vys´ılaˇc vyˇsle data (automaticky, nebo po stisku tlaˇc´ıtka), • vˇsechny pˇrij´ımaˇce v dosahu pˇrijmou vyslan´ y signál a ohodnot´ı jeho u ´roveˇ n, • ˇr´ıd´ıc´ı jednotka od pˇrij´ımaˇc˚ u obdrˇz´ı informaci o vys´ılaˇci, identifikátor vyslaného signálu (umoˇzn ˇuje spárovat pˇrijatá data z jednotliv´ ych pˇrij´ımaˇc˚ u) a s´ılu signálu, • ˇr´ıd´ıc´ı jednotka vys´ılá pˇrijatá data jako proud dat na TCP/IP portu 1112. Obsah proudu dat je k nahlédnut´ı na obrázku 7. Na tomto obrázku jsou vidˇet servisn´ı informace (oznaˇcené ’#’ v druhém sloupci), ty jsou pro u ´ˇcely mˇeˇren´ı nezaj´ımavé. 7/29


Obrázek 6: Pˇrij´ımaˇc IMA [3] Zaj´ımavé jsou data která maj´ı v druhém sloupci ’D’ v daném ˇrádku jsou obsaˇzená data jako: identifikátor pˇrij´ımaˇce (4. sloupec), identifikátor vys´ılaˇce (5. sloupec), identifikátor vyslaného signálu (6. sloupec), s´ılu signálu (7. sloupec) a informaci o stisku tlaˇc´ıtka (8. sloupec). Vˇsechna takto vyslaná data jsou v ˇsestnáctkové soustavˇe.

8/29


Obrázek 7: Proud dat z ˇr´ıd´ıc´ı jednotky

9/29

Kapitola 4

Implementace Pro potˇreby bakaláˇrské práce jsem implementoval programy v jazyce C++ a aplikaci v PHP. Prvn´ım programem byl program pro sbˇer dat, kter´ y byl vyv´ıjen zároveˇ n s aplikac´ı v PHP, které umoˇzn ˇuje vlastn´ı sbˇer dat. Druh´ y implementovan´ y program zpracovává sebraná data, z kter´ ych trénuje model a následnˇe rozpoznává nejpravdˇepodobnˇejˇs´ı sekvenci navˇst´ıven´ ych m´ıstnost´ı, kterou porovnává s referenˇcn´ı metodou k-NN.

4.1

Sbˇ er dat

Sbˇer dat má aplikace provádˇet pˇripojen´ım k ˇr´ıd´ıc´ı jednotce IMA popsané v sekci 3.3, následnˇe má tato data pˇreparsovat a uloˇzit pro dalˇs´ı pouˇzit´ı. Od toho se odv´ıj´ı jej´ı struktura:

4.1.1

Ukl´ ad´ an´ı informac´ı v pr˚ ubˇ ehu mˇ eˇ ren´ı

Program pro sbˇer dat4 je psán v jazyce C++ s maximáln´ı snahou vyuˇz´ıvat pˇrednosti OOP5 , jako jsou napˇr´ıklad rozhran´ı (interface)6 umoˇzn ˇuj´ıc´ı v navrˇzeném programu napˇr´ıklad snadno zmˇenit SQL u ´loˇziˇstˇe za u ´loˇziˇstˇe zcela jiného typu. Základn´ı funkce programu jsou: • Pˇripojen´ı k u ´loˇziˇsti, • pˇripojen´ı k ˇr´ıd´ıc´ı jednotce IMA 3.3, • parsován´ı proudu dat z ˇr´ıd´ıc´ı jednotky a • uloˇzen´ı v´ ysledk˚ u do u ´loˇziˇstˇe které jsou popsány v následuj´ıc´ıch sekc´ıch: 4.1.1.1

Pˇ ripojen´ı k u ´ loˇ ziˇ sti

Jako u ´loˇziˇstˇe jsem zvolil relaˇcn´ı databázi MySQL [10], konkrétnˇe jej´ı odnoˇz MariaDB [11], která je oproti MySQL od Oracle efektivnˇejˇs´ı. Databázi jsem zvolil InnoDB [12], která mimo jiné umoˇzn ˇuje vyuˇzit´ı transakˇcn´ıch operac´ı. Pro tuto databázi jsem implementoval SqlStorage jako rozhran´ı IStorage, ve kterém jsem vyuˇzil existuj´ıc´ı C++ knihovny pro MySQL[13]. V této implementaci jsem pouˇzil 4

K dispozici na pˇriloˇzeném CD a online na https://bitbucket.org/trejjam/ima Object-oriented programming: Objektovˇe orientované programován´ı 6 V jazyce C++ nejsou definované rozhran´ı (interface), jako napˇr. v PHP(PHP: Hypertext Preprocessor), tuto absenci obch´ az´ım pomoc´ı neimlementované (tj. pouze definované) tˇr´ıdy 5

10/29

ˇ DAT 4.1 SBER pˇredpˇripravené dotazy (prepared statements [14]), které mimo zlepˇsen´ı ˇcasov´ ych prodlev pˇrináˇs´ı i typovou kontrolu, pˇr´ıpadnˇe u ´pravu dat. Vzájemné vztahy tabulek databáze vyuˇz´ıvan´ ych touto implementac´ı jsou vyobra7 zeny pomoc´ı ER modelu na obrázku 8. Tento model popisuje jednoduchou relaci mezi tabulkou se sebran´ ymi daty a vys´ılaˇcem z kterého byla tato data odeslána.

Obrázek 8: ER diagram

4.1.1.2

Pˇ ripojen´ı k ˇ r´ıd´ıc´ı jednotce IMA

Pˇripojen´ı k ˇr´ıd´ıc´ı jednotce IMA se uskuteˇcn´ı na základˇe zadán´ı IP adresy a portu a ˇ ıd´ıc´ı jednotka takto vytvoˇren´ následném navázán´ı TCP/IP spojen´ı k jednotce. R´ ym spojen´ım zas´ılá do aplikace jednoduch´ y proud dat popsan´ ym v sekci 3.4. 4.1.1.3

Parsov´ an´ı proudu dat z ˇ r´ıd´ıc´ı jednotky

Proud dat z ˇr´ıd´ıc´ı jednotky 4.1.1.2 vstupuje do parseru, kter´ y má za u ´kol vybrat z dat uˇziteˇcné informace (kombinace ˇcasu, ID vys´ılaˇce, ID pˇrij´ımaˇce, . . . ). Prvn´ım krokem je rozdˇelen´ı dat podle oddˇelovaˇce (v tomto pˇr´ıpadˇe je to znak ’\n’ - odˇra´dkován´ı). Dalˇs´ım krokem je identifikace datov´ ych ˇrádk˚ u, ty jsou rozpoznatelné podle kl´ıˇcového znaku ’D’ v druhém sloupci. Posledn´ım krokem parsován´ı je pˇrevod jednotliv´ ych informac´ı na datové typy vhodné pro uchován´ı a dalˇs´ı zpracován´ı. Tyto datové typy jsem urˇcil následovnˇe: 7

Entity-relationship model: entitnˇe vztahov´ y model

11/29

ˇ DAT 4.1 SBER • ˇcas - double • ID pˇrij´ımaˇce - int • ID vys´ılaˇce - int • ID mˇeˇren´ı - int • s´ıla signálu - int • stisknuté tlaˇc´ıtko - int8 Informace z´ıskané z parseru jsou pˇredávány do popsané implementace rozhran´ı IStorage (tj. do SqlStorage) popsané v sekci 4.1.1.1, které je následnˇe ukládá do databáze pro pozdˇejˇs´ı vyuˇzit´ı. Zdrojové kódy jsou spravovány GIT repositáˇrem9 , pouˇzit´ ym pˇredevˇs´ım pro moˇznost verzován´ı, d´ıky jeho existenci je snadné spolupracovat na projektu s v´ıce u ´ˇcastn´ıky. Ostatn´ı zdrojové kódy a texty jsou také verzované z podobn´ ych d˚ uvod˚ u jako tento program.

4.1.2

Definov´ an´ı fyzick´ eho prostˇ red´ı

Pro pˇriˇrazen´ı namˇeˇren´ ych dat k reáln´ ym prostorám jsem vytvoˇril jednoduchou webo10 vou aplikaci . Pˇri jej´ımˇz vytváˇren´ı bylo myˇsleno na snadné vloˇzen´ı map budov a následné specifikován´ı m´ıstnost´ı, téˇz na pˇr´ıpadné budouc´ı zobrazován´ı pozice vys´ılaˇce (lokalizován´ı osoby). Aplikace je naprogramována v jazyce PHP s napojen´ım na stejnou MariaDB databázi jako aplikace popsaná v sekci 4.1.1, d´ıky tomuto propojen´ı lze snadno pˇriˇrazovat namˇeˇrená data k jednotliv´ ym m´ıstnostem. Jádrem aplikace je Nette Framework 2.3 [15] s moduly (extensions) dostupn´ ymi pˇres 11 Composer : • trejjam/authorization [16] - správa uˇzivatel˚ u a jejich rol´ı s napojen´ım na relaˇcn´ı databázi pro pohodlné nastavován´ı práv z administrace aplikace • kdyby/console [17] - knihovna pro snadné vytváˇren´ı konzolov´ ych pˇr´ıkaz˚ u v PHP pro Nette Framework Pˇri psan´ı aplikace byly vyuˇzity principy jako DI12 , DRY13 . Pro automatizován´ı pˇri v´ yvoji je pouˇzit Grunt14 . Nasazován´ı aplikace je ˇreˇseno pomoc´ı verzovac´ıho nástroje GIT a vzdáleného repositáˇre. 8

pro tlaˇc´ıtko by byl vhodnˇejˇs´ı boolean, avˇsak tento typ má slabou podporu v nˇekter´ ych datab´ azov´ ych systémech, proto jsem zvolil int 9 K dispozici na pˇriloˇzeném CD a online na https://bitbucket.org/trejjam/ima 10 K dispozici na pˇriloˇzeném CD a online na https://bitbucket.org/trejjam/ima-web 11 Bal´ıkovac´ı systém pro PHP 12 Dependency Injection 13 Don’t repeat yourself 14 http://gruntjs.com/

12/29

ˇ Í A ROZPOZNAV ´ AN ´ Í ZE SEBRANYCH ´ 4.2 UCEN DAT Aplikace umoˇzn ˇuje nahrán´ı obrázku mapy pomoc´ı standardn´ıho souborového dialogu. Na nahrané mapˇe následovnˇe umoˇzn ˇuje specifikován´ı jmen m´ıstnost´ı. M´ıstnosti, které existuj´ı v databázi je moˇzno namapovat na mapu pomoc´ı gesta drag & drop. Náhled aplikace je na obrázku 9, nastavené m´ıstnosti jsou oznaˇcené zelenou barvou, právˇe mapovaná m´ıstnost je oznaˇcena ˇcervenˇe.

Obrázek 9: Nastaven´ı mapy Pˇripravená mapa se specifikovan´ ymi m´ıstnostmi je vyuˇz´ıvána pˇri sbˇeru dat. A to tak, ˇze umoˇzn ˇuje uˇzivateli provádˇej´ıc´ımu mˇeˇren´ı jednoznaˇcnˇe urˇcit, v které m´ıstnosti se nacház´ı. Toto uˇzivatel provede napˇr´ıklad z mobiln´ıho telefonu, s pouˇzit´ım jeho webového prohl´ıˇzeˇce, kde specifikuje nesen´ y vys´ılaˇc (tag) a m´ıstnost v které se nacház´ı. Náhled pouˇzité aplikace je na obrázku 10. Z´ıskán´ım tˇechto informac´ı je schopen program popsan´ y v sekci 4.1.1 spojit pˇr´ıchoz´ı data s m´ıstnost´ı. Toto spojen´ı umoˇzn ˇuje budouc´ı operace s daty, napˇr´ıklad trénován´ı modelu.

4.2

Uˇ cen´ı a rozpozn´ av´ an´ı ze sebran´ ych dat

Pro uˇcen´ı jsem pˇripravil specializovanou aplikaci, která vyuˇz´ıvá data pˇripravená aplikac´ı popsanou v sekci 4.1.1. Tato aplikace15 je téˇz psaná v jazyce C++. Základn´ı funkcionality aplikace jsou: • Pˇripojen´ı k u ´loˇziˇsti, 15

K dispozici na pˇriloˇzeném CD a online na https://bitbucket.org/trejjam/imacomputing

13/29

ˇ Í A ROZPOZNAV ´ AN ´ Í ZE SEBRANYCH ´ 4.2 UCEN DAT

Obrázek 10: Aplikace pouˇz´ıvaná pˇri uˇcen´ı • pˇripojen´ı k Matlabu, • pˇripraven´ı dat pro trénován´ı a rozpoznáván´ı, • vystavˇen´ı modelu z dat, • rozpoznán´ı nejpravdˇepodobnˇejˇs´ı sekvence stav˚ u z dat a natrénovaného modelu a • export v´ ysledk˚ u.

4.2.1

Pˇ ripojen´ı k u ´ loˇ ziˇ sti

Pˇripojen´ı k u ´loˇziˇsti vyuˇz´ıvá stejnou knihovnu jako program pro sbˇer dat 4.1.1. Jen s t´ım rozd´ılem, ˇze do u ´loˇziˇstˇe nezapisuje. Po u ´spˇeˇsném pˇripojen´ı k u ´loˇziˇsti je tˇreba vybrat mˇeˇren´ı které bude pouˇzito pro trénován´ı a rozpoznáván´ı. Toho je doc´ıleno pomoc´ı klasického ˇra´dkového vstupu, pomoc´ı kterého lze zvolit jedno a v´ıce mˇeˇren´ı.

4.2.2

Pˇ ripojen´ı k Matlabu

Pro pˇripojen´ı do programu Matlab jsem vyuˇzil poskytovanou knihovnu [18], která umoˇzn ˇuje volat vlastn´ı pˇr´ıkazy automaticky z vlastn´ı aplikace, jako kdyby byli ruˇcnˇe zadávané do konzole Matlabu. P˚ uvodnˇe jsem chtˇel vyuˇz´ıt tohoto API 16 i pro pˇrenos dat mezi aplikac´ı a Matlabem, ale zde nejsp´ıˇse kv˚ uli neoptimáln´ımu nadefinován´ı typ˚ u pol´ı 16

Application Programming Interface: soubor funkc´ı, procedur, . . . pro komunikaci s aplikac´ı

14/29

ˇ Í A ROZPOZNAV ´ AN ´ Í ZE SEBRANYCH ´ 4.2 UCEN DAT docházelo k r˚ uzn´ y zmˇenám v datech. Proto jsem nakonec sáhl po ne zcela optimáln´ım ˇreˇsen´ı a to pˇrenáˇset data pˇres prostˇredn´ıka, kter´ ym se stalo nˇekolik textov´ ych soubor˚ u.

4.2.3

Pˇ ripraven´ı dat pro tr´ enov´ an´ı a rozpozn´ av´ an´ı

Sebraná data nejsou vhodná pro pˇr´ımé pouˇzit´ı v HMM, proto jsem data nejdˇr´ıve proˇcistil, kvantoval a pˇrekódoval, tyto u ´pravy jsou popsány v následuj´ıc´ıch sekc´ıch: 4.2.3.1

Proˇ ciˇ stˇ en´ı dat

Aby nevznikl pˇreuˇcen´ y model (tj. model, kter´ y d´ıky velkému mnoˇzstv´ı dat zpˇresn´ı své hodnoty tak, ˇze pˇri nasazen´ı nen´ı schopen správnˇe zpracovat/zaˇradit vˇetˇsinu dat) rozhodl jsem se sebraná data proˇcistit. Metodu ˇciˇstˇen´ı jsem zvolil tak, ˇze pouˇz´ıvám data s rozestupy ˇcasov´ ych znaˇcek od pˇredchoz´ı i následuj´ıc´ı ˇcasové znaˇcky namˇeˇren´ ych u ´daj˚ u. Tedy pro kaˇzd´ y pouˇzit´ y záznam plat´ı (s - ˇcasová znaˇcka záznamu; n - poˇcet záznam˚ u; i = 0, 1, (n-2); k = zvolen´ y rozestup): si <= (si+1 + k) <= (si+2 + k) 4.2.3.2

Kvantov´ an´ı dat

Protoˇze jsou data z ˇr´ıd´ıc´ı jednotky IMA 3.3 spojitá (s intervalem 0-255), rozhodl jsem se tato data pro snazˇs´ı implementaci HMM 1.2.2 kvantovat. Kvantily jsem stanovil objektivnˇe z namˇeˇren´ ych dat a to pomoc´ı vzorce (r - rozsah, q - poˇcet kvantil˚ u, d pˇrijatá data, round - zaokrouhlen´ı dol˚ u, o - pˇriˇrazen´ y kvantil): o = round(d/(r/q)) 4.2.3.3

Pˇ rek´ odov´ an´ı dat

Základn´ı pouˇzit´ı HMM je omezeno na skalárn´ı hodnoty, proto bylo tˇreba vektory sil signál˚ u zobrazit na skalárn´ı hodnotu. Pro toto zobrazen´ı (pˇrekódován´ı) jsem si stanovil podm´ınku, aby bylo prosté, tj. dva r˚ uzné vektory se nesm´ı zobrazit do stejného prvku. Pˇrekódován´ı jsem implementoval jako jednoduch´ y pˇrepoˇcet z n-kové soustavy (kde n je poˇcet kvantil˚ u) do des´ıtkové soustavy. Vezmeme-li si náhodn´ y vzorek ze ˇctyˇr pˇrij´ımaˇc˚ u o pˇeti kvantilech implementovan´ y pˇrepoˇcet vypadá následovnˇe: 0143(5) = 0 ∗ 53 + 1 ∗ 52 + 4 ∗ 51 + 3 ∗ 50 = 48(10)

4.2.4

Vystavˇ en´ı modelu z dat

Pˇri implementován´ı trénován´ı jsem vyuˇzil toho, ˇze iterativn´ı algoritmus 2.1 je implementovan´ y v Matlabu [19]. Jeho základn´ı volán´ı vypadá takto: [T RAN S, EM IS] = hmmestimate(seq, states) 15/29

´ ˚ 4.4 EXPORT VYSLEDK U Vstup do tohoto algoritmu jsou proˇciˇstˇená, kvantovaná a pˇrekódovaná data (postup zm´ınˇen v sekc´ıch 4.2.3.1, 4.2.3.2 a 4.2.3.3). V´ ystupem jsou pak hledané matice emisivity a tranzitivity. Pro pouˇzit´ı na testovan´ ych datech bylo tˇreba vyuˇz´ıt i volitelné parametry funkce: Prvn´ım parametrem je poˇcet symbol˚ u, protoˇze proˇciˇstˇená data mohou b´ yt ochuzena o nˇekteré symboly oproti dat˚ um urˇcen´ ym k rozpoznáván´ı, coˇz pˇri pˇr´ıpadné absenci a následném rozpoznáván´ı skonˇc´ı chybou. Druh´ ym parametrem je pˇredpˇripravená matice tranzitivit, kterou jsem pˇredvyplnil jedniˇckami na diagonále (tj. 100% pravdˇepodobnost pˇrechodu do stejného stavu) a to z d˚ uvodu velice podobného jako u prvn´ıho parametru. Zde vˇsak s vazbou na moˇznost chybˇej´ıc´ıch stav˚ u, které zp˚ usob´ı nulov´ y ˇra´dek v´ ysledné matice, coˇz vede k chybˇe pˇri rozpoznáván´ı. Tˇret´ım a posledn´ım parametrem je pˇredpˇripravená matice emisivit, kterou jsem pˇredvyplnil tak aby emisivity ze vˇsech stav˚ u byly stejné (tj. vˇsechny prvky matice maj´ı hodnotu 1/poˇcet symbol˚ u).

4.2.5

Rozpozn´ an´ı nejpravdˇ epodobnˇ ejˇ s´ı sekvence stav˚ uz dat a natr´ enovan´ eho modelu

Pro rozpoznáván´ı Viterbiho algoritmem popsan´ ym v sekci 2.2 jsem vyuˇzil funkce implementované v Matlabu [20]. Jej´ıˇz volán´ı vypadá takto: ST AT ES = hmmviterbi(seq, T RAN S, EM IS) Do této funkce pˇredávám proˇciˇstˇená, kvantovaná a pˇrekódovaná data (postup zm´ınˇen v sekc´ıch 4.2.3.1, 4.2.3.2 a 4.2.3.3), s jedinou u ´pravou oproti trénován´ı, kterou je zmˇena zdrojového vys´ılaˇce. V´ ystupem funkce je nejpravdˇepodobnˇejˇs´ı ˇretˇezec stav˚ u (m´ıstnost´ı), kter´ ymi se vys´ılaˇc pohyboval.

4.3

Jin´ a metoda uˇ cen´ı a rozpozn´ av´ an´ı

Jako referenˇcn´ı algoritmus jsem vybral k-NN 1.2.2, kter´ y je povaˇzován za dobrou referenˇcn´ı metodu klasifikace. Pro tuto metodu jsem implementoval trénován´ı a rozpoznáván´ı s vyuˇzit´ım algoritm˚ u dostupn´ ych v Matlabu.

4.4

Export v´ ysledk˚ u

V´ ysledky porovnán´ı u ´spˇeˇsnosti rozpoznán´ı HMM jejichˇz algoritmus je popsán v sekci 4.2.5 a KNN v sekci 4.3 se ukládaj´ı do jednoduchého souboru ve formátu CSV17 , kter´ y umoˇzn ˇuje jejich snadné budouc´ı pouˇzit´ı.

17

Comma-separated values: hodnoty oddˇelené ˇcárkami

16/29

Kapitola 5

Experimenty Pˇri provádˇen´ı experiment˚ u jsem vyuˇzil napsané aplikace a znalosti s´ıt’ové komunikace, které pˇriˇsli vhod napˇr. pˇri zpˇr´ıstupˇ nován´ı zaˇr´ızen´ı um´ıstˇené za NATem18 ze s´ıtˇe Internet

5.1

Sbˇ er dat

ˇ Sbˇer dat jsme provádˇeli v budovˇe E CVUT FEL na Karlovˇe námˇest´ı v bloku budovy smˇeˇruj´ıc´ı k budovˇe G. Pˇrij´ımaˇce popsané v sekci 3.2 jsme rozm´ıstili v 1. patˇre viz obrázek 11.

Obrázek 11: Mapa s vyznaˇcen´ ymi pˇrij´ımaˇci Pˇred vlastn´ım mˇeˇren´ım bylo nutné spojit, ˇci umoˇznit spojen´ı vˇsech zaˇr´ızen´ı, tj. jednotky IMA, sbˇerné zaˇr´ızen´ı (notebook) a mobiln´ı telefony. Stabiln´ı pˇr´ıstup mobiln´ıch telefon˚ u k notebooku, na kterém bˇeˇz´ı server s aplikac´ı, popsané v sekci 4.1.2, umoˇzn ˇuj´ıc´ı specifikován´ı m´ıstnosti, v které se subjekt provádˇej´ıc´ı mˇeˇren´ı nacház´ı, jsme vyˇreˇsili, pomoc´ı vlastn´ıho soukromého serveru s veˇrejnou IP, z kterého jsme vytvoˇrili reverzn´ı tunel pˇres SSH 19 , d´ıky ˇcemu byl notebook dostupn´ y, i v pˇr´ıpadˇe, kdy mobiln´ı telefony pˇreˇsli na mobiln´ı pˇripojen´ı (z d˚ uvodu nedokonalého wifi pokryt´ı) a nebyl-li tedy mobiln´ı telefon pˇr´ımo ve ˇskoln´ı s´ıti. Jednotky IMA popsané v kapitole 2.2 jsme s notebookem urˇcen´ ym pro bˇeh aplikace pˇripravené pro sbˇer dat, popsané v sekci 4.1.1, propojily pomoc´ı routeru nakon18 19

Network Address Translation: pˇreklad s´ıt’ov´ ych adres SSH: Secure Shell

17/29

´ ´ Í A ROZPOZNAV ´ AN ´ Í Z DAT 5.2 TRENOV AN figurovaného jako switch, kter´ y jsme pˇripojili do ˇskoln´ı s´ıtˇe, abychom zajistili stabiln´ı pˇripojen´ı k zm´ınˇenému veˇrejnému serveru. Do tohoto switche jsme pˇripojili notebook, kter´ ym jsme proskenovali zaˇr´ızen´ı viditelná v s´ıti, následnˇe jsme pˇripojili a spustili ˇr´ıd´ıc´ı jednotku IMA, znovu jsme proskenovali s´ıt’ a z rozd´ılu viditeln´ ych zaˇr´ızen´ı jsme identifikovali IP adresu ˇr´ıd´ıc´ı jednotky IMA, která je jedn´ım z parametr˚ u aplikace pro sbˇer dat. Propojen´ım jednotliv´ ych zaˇr´ızen´ı a spuˇstˇen´ım aplikac´ı jsme zajistili vˇse potˇrebné k sbˇeru dat, kter´ y prob´ıhal tak, ˇze jsme v mobiln´ım zaˇr´ızen´ı specifikovali nesen´ y vys´ılaˇc (tag) a pˇri pˇrechodu z m´ıstnosti do m´ıstnosti jsme tuto m´ıstnost oznaˇcovali ve webové aplikaci. Informace o m´ıstnosti z této aplikace mˇela k dispozici aplikace zpracovávaj´ıc´ı data z ˇr´ıd´ıc´ı jednotky IMA, která je pˇriˇrazovala k pˇrij´ıman´ ym dat˚ um z jednotky, ˇc´ımˇz jsme z´ıskali sekvenci vektor˚ u sil signál˚ u s informac´ı ke které m´ıstnosti tato data patˇr´ı. Sbˇery dat jsme provádˇeli s kolegou Richardem Bláhou, kter´ y má pro sebraná data vyuˇzit´ı v rámci vlastn´ı bakaláˇrské práce. Sbˇer jsme provádˇeli souˇcasnˇe s t´ım, ˇze kaˇzd´ y z nás nesl jeden vys´ılaˇc a pohyboval se nezávisle na druhém. V prvn´ım mˇeˇren´ı jsme namˇeˇrili pˇribliˇznˇe 11500 záznam˚ u, v druhém mˇeˇren´ı 34000. Pˇri druhém mˇeˇren´ı jsme rozˇs´ıˇrili sbˇer dat i na druhé patro bez zmˇeny rozm´ıstˇen´ı pˇrij´ımaˇc˚ u. Abychom zamezili vlastn´ımu vlivu na mˇeˇren´ı pˇri druhém mˇeˇren´ı jsme si vys´ılaˇce s kolegou vymˇenili.

5.2

Tr´ enov´ an´ı a rozpozn´ av´ an´ı z dat

Trénován´ı a rozpoznáván´ı nad sebran´ ymi daty jsem provádˇel s r˚ uzn´ ymi konfiguracemi rozd´ıl˚ u ˇcasov´ ych znaˇcek u dat urˇcen´ ych pro trénován´ı i rozpoznáván´ı, s poˇctem kvantil˚ u do kter´ ych byli klasifikovány s´ıly signál˚ u na pˇrij´ımaˇc´ıch a poˇcet k v k-NN algoritmu. Pro minimáln´ı rozd´ıl ˇcasov´ ych znaˇcek dat urˇcen´ ych pro trénován´ı jsem zvolil hodnoty 0s, 1,5s, 3s, 5s a 8s. Minimáln´ı rozd´ıl ˇcasov´ ych znaˇcek dat urˇcen´ ych pro rozpoznáván´ı jsem zvolil hodnoty 1,5s, 3s, 5s a 8s. Pouˇzité kvantily pro data jsem zvolil 3 a 5 kvantil˚ u. Referenˇcn´ı algoritmus jsem nastavoval na k rovno 1, 3 a 5ti. Následnˇe jsem spustit uˇcen´ı nad daty z prvn´ıho mˇeˇren´ı z jednoho vys´ılaˇce s rozpoznáván´ım z druhého vys´ılaˇce pro tato data jsem pouˇzil kombinace vˇsech zm´ınˇen´ ych parametr˚ u. Následnˇe jsem vymˇenil pˇrij´ımaˇce. Stejn´ y postup jsem zopakoval i pro druhé mˇeˇren´ı. Pouˇzité konfigurace jsou vypsány v následuj´ıc´ı tabulce:

18/29

´ ´ Í A ROZPOZNAV ´ AN ´ Í Z DAT 5.2 TRENOV AN i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

rozd´ıl ˇcasov´ ych znaˇcek rozd´ıl ˇcasov´ ych znaˇcek u dat pro rozpoznáván´ı u dat pro trénován´ı 0 1,5 0 1,5 0 1,5 0 1,5 0 1,5 0 1,5 0 3 0 3 0 3 0 3 0 3 0 3 0 5 0 5 0 5 0 5 0 5 0 5 0 8 0 8 0 8 0 8 0 8 0 8 1,5 1,5 1,5 1,5 1,5 1,5 1,5 1,5 1,5 1,5 1,5 1,5 1,5 3 1,5 3 1,5 3 1,5 3 1,5 3 1,5 3 1,5 5 1,5 5 1,5 5 1,5 5 1,5 5 1,5 5

poˇcet kvantil˚ u poˇcet k HMM u k-NN 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 19/29

´ ´ Í A ROZPOZNAV ´ AN ´ Í Z DAT 5.2 TRENOV AN i 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 20/29

rozd´ıl ˇcasov´ ych znaˇcek rozd´ıl ˇcasov´ ych znaˇcek u dat pro rozpoznáván´ı u dat pro trénován´ı 1,5 8 1,5 8 1,5 8 1,5 8 1,5 8 1,5 8 3 1,5 3 1,5 3 1,5 3 1,5 3 1,5 3 1,5 3 3 3 3 3 3 3 3 3 3 3 3 3 5 3 5 3 5 3 5 3 5 3 5 3 8 3 8 3 8 3 8 3 8 3 8 5 1,5 5 1,5 5 1,5 5 1,5 5 1,5 5 1,5 5 3 5 3 5 3 5 3 5 3 5 3

poˇcet kvantil˚ u poˇcet k HMM u k-NN 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1

´ ´ Í A ROZPOZNAV ´ AN ´ Í Z DAT 5.2 TRENOV AN i 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

rozd´ıl ˇcasov´ ych znaˇcek rozd´ıl ˇcasov´ ych znaˇcek u dat pro rozpoznáván´ı u dat pro trénován´ı 5 5 5 5 5 5 5 5 5 5 5 5 5 8 5 8 5 8 5 8 5 8 5 8 8 1,5 8 1,5 8 1,5 8 1,5 8 1,5 8 1,5 8 3 8 3 8 3 8 3 8 3 8 3 8 5 8 5 8 5 8 5 8 5 8 5 8 8 8 8 8 8 8 8 8 8 8 8

poˇcet kvantil˚ u poˇcet k HMM u k-NN 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1 5 5 3 5 5 3 3 3 5 1 3 1

Tyto v´ ypoˇcty byli pomˇernˇe ˇcasovˇe nároˇcné, jejich doba se bl´ıˇzila k 16h na procesoru i5-3317U.

21/29

Kapitola 6

V´ ysledky Kaˇzdé mˇeˇren´ı a roli vys´ılaˇce (jedna role pro trénován´ı a druhá pro rozpoznáván´ı) jsem vynesl do grafu, kter´ y znázorˇ nuje srovnán´ı pravdˇepodobnost´ı chybn´ ych rozpoznán´ı (v grafu jako e) mezi v´ ystupem referenˇcn´ıho algoritmu (k-NN) popsaného v sekci 4.3 a HMM ze sekce 4.2.5. Srovnán´ı jsem vynesl do grafu pro kaˇzdou konfiguraci (ˇc´ıslo konfigurace i v tabulce odpov´ıdá ose grafu i ) z tabulky vypsané v sekci 5.2. Srovnán´ı z prvn´ıho mˇeˇren´ı (tj. pouze jedno patro, 11500 záznam˚ u) s daty z vys´ılaˇce s oznaˇcen´ım 0x4e pouˇzit´ ymi pro trénován´ı a z vys´ılaˇce 0x4a pro rozpoznáván´ı, lze pozorovat na grafu 12, v´ ysledky po vymˇenˇe rol´ı vys´ılaˇc˚ u pak na grafu 13. 0,90 0,80 0,70 0,60

e

0,50 0,40 HMM KNN

0,30 0,20 0,10 0,00

i

Obrázek 12: Porovnán´ı 1. mˇeˇren´ı, uˇcen´ı nad 0x4e, rozpoznáván´ı nad 0x4a 0,50 0,45 0,40 0,35 0,30 e

0,25 0,20

HMM KNN

0,15 0,10 0,05 0,00

i

Obrázek 13: Porovnán´ı 1. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e U grafu 12 si nejsem jist z jakého d˚ uvodu je metoda HMM ve vˇsech konfigurac´ıch 22/29

´ 6.0 VYSLEDKY tak ˇspatná (tj. pr˚ umˇernˇe pˇribliˇznˇe 80% ne´ uspˇeˇsnost), pˇredpokládám, ˇze to m˚ uˇze b´ yt zp˚ usobeno ˇcast´ ym pohybem vys´ılaˇce na okraj´ıch mˇeˇritelného prostoru, ˇcehoˇz jsme se pˇri dalˇs´ım mˇeˇren´ı vyvarovali. Mysl´ım si proto, ˇze zaj´ımavˇejˇs´ı jsou porovnán´ı z druhého mˇeˇren´ı, která jsou na grafu 14 (data od vys´ılaˇce 0x4e pouˇzitá pro trénován´ı a data z vys´ılaˇce 0x4a pro rozpoznáván´ı) a na grafu 15 po vymˇenˇe rol´ı vys´ılaˇc˚ u. 0,80 0,70 0,60 0,50

e

0,40 HMM KNN

0,30 0,20 0,10 0,00

i

Obrázek 14: Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4e, rozpoznáván´ı nad 0x4a

0,80 0,70 0,60 0,50

e

0,40 HMM KNN

0,30 0,20 0,10 0,00

i

Obrázek 15: Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e Mezi zvolen´ ymi rolemi vys´ılaˇc˚ u u prvn´ıho a druhého mˇeˇren´ı vid´ım jistou korelaci (i pˇres zm´ınˇenou zmˇenu subjektu provádˇej´ıc´ıho mˇeˇren´ı v sekci 5.1), proto se budu dále zamˇeˇrovat na porovnán´ı zaloˇzené na uˇcen´ı z vys´ılaˇce 0x4a a rozpoznáván´ı z 0x4e. Z graf˚ u druhého mˇeˇren´ı soud´ım, ˇze lépe reflektuj´ı oˇcekávané v´ ysledky. S pˇrihlédnut´ım k pozorován´ı kvality v´ ysledk˚ u jednotliv´ ych mˇeˇren´ı a jejich závislosti na zvolen´ ych rol´ıch vys´ılaˇc˚ u jsem se dále zamˇeˇril na detailnˇejˇs´ı porovnán´ı v´ ysledk˚ u vynesen´ ych do grafu 15. V prvn´ım detailnˇejˇs´ım porovnán´ı jsem seˇradil v´ ysledky podle ˇcas˚ u minimáln´ıch odchylek mezi daty pouˇzit´ ymi pro rozpoznáván´ı, porovnán´ı jsem vynesl do grafu 16. Na tomto grafu je dobˇre vidˇet ovlivnˇen´ı rozd´ılu ˇcasov´ ych znaˇcek napˇr´ıˇc zmˇenou ostatn´ıch parametr˚ u. Nejlepˇs´ı v´ ysledek pro HMM m˚ uˇzeme pozorovat u rozd´ılu k=8s u 23/29

´ 6.0 VYSLEDKY 0,80 0,70 0,60

e

0,50 HMM HMM HMM HMM KNN

0,40 0,30 0,20

− − − −

k k k k

= 1,5s = 3s = 5s = 8s

0,10 0,00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 i

Obrázek 16: Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e - rozdˇeleno do skupin konfigurace 3, 13 a 23 (u kter´ ych d´ıky seˇrazen´ı v´ ysledk˚ u ˇc´ısla konfigurac´ı neodpov´ıdaj´ı ˇc´ısl˚ um konfigurac´ı v p˚ uvodn´ı tabulce, seˇrazená data jsou k dispozici na pˇriloˇzeném CD), tyto konfigurace maj´ı shodnˇe nastaven´ y rozd´ıl ˇcasov´ ych znaˇcek dat pro trénován´ı a to na 3s, coˇz v d˚ usledku znamená, ˇze pouˇzijeme pˇresnˇejˇs´ı data pro trénován´ı a ménˇe pˇresná pro rozpoznáván´ı, jako vedlejˇs´ı efekt pozitivnˇe ovlivn´ıme dobu v´ ypoˇctu a ˇcetnost pˇrepoˇc´ıtáván´ı. Kdyˇz prozkoumáme kˇrivku k=3s m˚ uˇzeme si povˇsimnout jisté korelace s k=8s (fázovˇe posunuté), z které vyvozuji vhodnost pouˇzit´ı velikosti ˇcasov´ ych rozd´ıl˚ uu trénován´ı a rozpoznáván´ı v pomˇeru pˇribliˇznˇe 1:3. Pro dalˇs´ı detailnˇejˇs´ı porovnán´ı jsem si vybral setˇr´ıdˇen´ı podle poˇctu kvantil˚ u pouˇzit´ ych pro HMM, porovnán´ı jsem vynesl do grafu 17 a 18 0,70 0,60 0,50

e

0,40 0,30

HMM KNN

0,20 0,10 0,00 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 i

Obrázek 17: Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e, 3 kvantily Na tˇechto porovnán´ıch mi pˇrijde zvláˇstn´ı opaˇcná tendence, která je dobˇre viditelná u konfigurac´ı (ˇc´ısla konfigurac´ı d´ıky seˇrazen´ı neodpov´ıdaj´ı ˇc´ısl˚ um konfigurac´ı v tabulce zm´ınˇené v sekci 5.2, seˇrazená data jsou k dispozici na pˇriloˇzeném CD) s ˇc´ıslem konfigurace vetˇs´ım neˇz 46 (tj. vˇsechny konfigurace s rozd´ılem ˇcasov´ ych znaˇcek vˇetˇs´ım neˇz 8s u dat pro rozpoznáván´ı). Porovnán´ı zaloˇzené na tˇrech kvantilech reaguje na r˚ ust rozd´ılu ˇcasov´ ych znaˇcek dat pro uˇcen´ı negativnˇe. Oproti tomu porovnán´ı s pˇeti kvantily reaguje 24/29

´ 6.0 VYSLEDKY 0,80 0,70 0,60 0,50

e

0,40 HMM KNN

0,30 0,20 0,10 0,00 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 i

Obrázek 18: Porovnán´ı 2. mˇeˇren´ı, uˇcen´ı nad 0x4a, rozpoznáván´ı nad 0x4e, 5 kvantil˚ u na r˚ ust rozd´ılu ˇcasov´ ych znaˇcek pozitivnˇe (do dosaˇzen´ı zm´ınˇené 1:3 hranice, po které se v´ ysledky zaˇcnou prudce zhorˇsovat).

25/29

Kapitola 7

Z´ avˇ er Pro tuto práci jsem napsal program pro sbˇer dat, webovou aplikaci pro identifikaci sebran´ ych dat a program pro trénován´ı model˚ u ze sebran´ ych dat (jak HMM, tak k-NN) a rozpoznáván´ı nejpravdˇepodobnˇejˇs´ı sekvence. Oba programy jsem napsal v jazyce C++, webovou aplikaci pak v jazyce PHP. Pˇri práci jsem si osvojil práci s poˇc´ıtaˇcovou s´ıt´ı a jej´ımi moˇznostmi, které jsem hojnˇe vyuˇzil pˇri sbˇeru dat. Celkovˇe jsme v pr˚ ubˇehu práce sebrali témˇeˇr 50000 záznam˚ u dat, nad kter´ ymi jsem provádˇel trénován´ı modelu a rozpoznáván´ı nejpravdˇepodobnˇejˇs´ıch posloupnost´ı m´ıstnost´ı. Z detailnˇejˇs´ıch porovnán´ı v´ ysledk˚ u ze sekce 5.2 vyvozuji jako vhodné pouˇz´ıt 5-ti kvantil˚ u pro u ´pravu dat z pˇrij´ımaˇc˚ u, dále selekci dat s minimáln´ım rozd´ılem ˇcasov´ ych znaˇcek 3s pro uˇcen´ı a 8s pro rozpoznáván´ı (pomˇer 3:8 je velice bl´ızko vyvozenému pomˇeru 1:3, kter´ y se ukázal jako vhodné kritérium pro urˇcen´ı minimáln´ıho rozd´ılu ˇcasov´ ych znaˇcek). Tato konfigurace 5 kvantil˚ u, 3s rozd´ıl ˇcasov´ ych znaˇcek dat pro uˇcen´ı a 8s rozd´ıl pro rozpoznáván´ı se ukázala jako nejlepˇs´ı pro HMM i referenˇcn´ı k-NN. Nejlepˇs´ı konfigurace HMM je ne´ uspˇeˇsná jen na 26% namˇeˇren´ ych datech, oproti k-NN jej´ıˇz nejlepˇs´ım v´ ysledkem je 49% ne´ uspˇeˇsnost. Pˇri vyhodnocován´ı byli vyhodnoceny jako chybné rozpoznán´ı v´ ysledky, které oznaˇcili za nejpravdˇepodobnˇejˇs´ı sousedn´ı m´ıstnost, coˇz v praxi pˇri snaze lokalizovat osobu v rozlehl´ ych areálech nemus´ı b´ yt povaˇzováno jako v´ yrazná komplikace. Pokraˇcován´ım projektu m˚ uˇze b´ yt napˇr. moˇznost upravit modelu, tak aby byl schopen vyuˇz´ıt spojitá data (v tomto projektu jsou data kvantována, d´ıky ˇcemu se ztrác´ı ˇca´st namˇeˇren´ ych informac´ı). Dalˇs´ı moˇzné rozˇs´ıˇren´ı je v oblasti automatizovaného opravován´ı modelu v závislosti na napojen´ı napˇr. k ˇcipov´ ym systém˚ um umoˇzn ˇuj´ıc´ım autorizované odemykán´ı dveˇr´ı. Moˇznou inovaci v uˇzivatelské ˇca´sti vid´ım v implementován´ı interaktivn´ıho zobrazován´ı aktuáln´ı pozice na mapˇe (tj. otoˇcen´ı funkce webové aplikace specializované pro sbˇer dat).

26/29

Literatura [1] Triangulace – wikipedie. http://cs.wikipedia.org/wiki/Triangulace. Naposledy navˇst´ıveno 19. 5. 2015. [2] M. Ibrahim; Y. Moustafa. A hidden markov model for localization using low-end gsm cell phones. http://arxiv.org/pdf/1010.3411.pdf. [3] Libor Urban´ık. Methods for people localization based on radio signals. [4] Tomáˇs Procházka Michal Houdek, Tomáˇs Svoboda. Klasifikace podle nejbliˇzˇs´ıch soused˚ u nearest neighbour classification [k-nn]. http://cmp.felk.cvut. cz/cmp/courses/recognition/zapis_prednasky/zapis_01/4/rpz4.pdf. Naposledy navˇst´ıveno 12. 5. 2015. [5] R. Arthi; K. Murugan. Localization in wireless sensor networks by hidden markov model. [6] CSc. Prof. Ing. Jan Nouza. Pokroˇcilé metody rozpoznáván´ı ˇreˇci. http://itakura. ite.tul.cz/jan/PMR/prednaska4.pdf. [7] Stephen Tu. Derivation of baum-welch algorithm for hidden markov models. http://www.cs.berkeley.edu/~stephentu/writeups/ hmm-baum-welch-derivation.pdf. Naposledy navˇst´ıveno 11. 2. 2015. [8] Václav Hlaváˇc. Rozpoznáván´ı s markovsk´ ymi modely. http://cmp.felk.cvut. cz/~hlavac/TeachPresCz/31Rozp/61MarkovianPR.pdf. Naposledy navˇst´ıveno 11. 5. 2015. [9] VOCAL Technologies. Viterbi algorithm in speech enhancement and hmm. http://www.vocal.com/echo-cancellation/ viterbi-algorithm-in-speech-enhancement-and-hmm/. Naposledy navˇst´ıveno 18. 5. 2015. [10] Oracle Corporation. Mysql. http://www.mysql.com/. Naposledy navˇst´ıveno 8. 2. 2015. [11] MariaDB Corporation. Mariadb. https://mariadb.com/. Naposledy navˇst´ıveno 8. 2. 2015. [12] Oracle Corporation. Mysql :: Mysql 5.0 reference manual :: 14.2 the innodb storage engine. http://dev.mysql.com/doc/refman/5.0/en/innodb-storage-engine. html. Naposledy navˇst´ıveno 8. 2. 2015. 27/29

[13] Oracle Corporation. Mysql :: Download connector/c++. http://dev.mysql.com/ downloads/connector/cpp/. Naposledy navˇst´ıveno 8. 2. 2015. [14] Oracle Corporation. Mysql :: Mysql connector/c++ developer guide :: 7.6 mysql connector/c++ complete example 2. http://dev.mysql.com/doc/ connector-cpp/en/connector-cpp-examples-complete-example-2.html. Naposledy navˇst´ıveno 10. 2. 2015. [15] Nette Foundation. Nette framework. http://nette.org/. Naposledy navˇst´ıveno 10. 2. 2015. [16] Jan Trejbal. Trejjam/authorization. https://github.com/Trejjam/ Authorization. Naposledy navˇst´ıveno 10. 2. 2015. [17] Filip Procházka. Kdyby/console. https://github.com/kdyby/console. Naposledy navˇst´ıveno 10. 2. 2015. [18] MathWorks. Matlab engine api for c, c++, and fortran matlab & simulink. http://www.mathworks.com/help/matlab/ calling-matlab-engine-from-c-c-and-fortran-programs.html. Naposledy navˇst´ıveno 11. 5. 2015. [19] MathWorks. Hidden markov model parameter estimates from emissions and states - matlab hmmestimate. http://www.mathworks.com/help/stats/hmmestimate. html. Naposledy navˇst´ıveno 7. 5. 2015. [20] MathWorks. Hidden markov model most probable state path - matlab hmmviterbi. http://www.mathworks.com/help/stats/hmmviterbi.html. Naposledy navˇst´ıveno 11. 5. 2015.

28/29

Obsah CD • Tato bakaláˇrská práce • Program pro sbˇer dat • Program pro provádˇen´ı v´ ypoˇct˚ u • Webová aplikace umoˇzn ˇuj´ıc´ı sbˇer dat • Namˇeˇrená data • Konfigurace pouˇzité v ˇcásti ”V´ ysledky”

Lokalizace osob v budově s

Recommend Documents