Matematika v robotice 16. CVSDM

28. listopadu 2013 v 5:37 | Petr |  Roboti a Matematika

Jestli vás zaujala zkratka CVSDM tak to znamená Continuously variable slope delta modulation. A jestli si myslíte, že jsem se zbláznil a opustil vidlácký způsob konstrukce a programování robotů - tak se velice pletete.
Nebudu začínat ultrazvukem, ale představte si, že byste chtěli to nejjednodušší, co si u robotů představuje každé 2 leté děcko - aby robot vydával nějaké "bojové pokřiky"
Takže trošku počítejme - představte si že budete chtít do robota naprogramovat 1 sekundu toho nejubožejšího zvuku. Takže berme, že vzorkovací frekvence bude 8KHz (pro rozsah alespoň do 4 KHz řečového pásma) a hloubka vzorkování bude 8 bitů. To máme 8 kilobyte / sec - při kvalitě zvuku, který se "vyrovná" nejubožejším hračkám od Vietnamce.

Takže vás okamžtě napadne, že je potřebná nějaká datová komprese. Začnete studovat běžné učebnicové algoritmy a zjistíte, že žádný není pro zvuk příliš vhodný. Co je vhodné je varianta FFT = DCT = JPEG = MP3 komprese, ale to je na naše matematické schopnosti i na ubohý výkon našeho procesoru zase příliš.

Takže první věc, která vás napadne - nebudu ukládat celý vzorek, ale jenom rozdíl oproti minulému vzorku - BINGO - vzhledem k tomu, že zvuky jsou většinou hladké sinusovky, bude nejčastější rodíl téměř 0, takže nemusíte ukládat celých 8 bitů rozdílu, protože (třeba) horní 4 bity jsou skoro vždycky 0, ale ukládáte jenom spodní 4 bity. Máte zvuk jenom o něco málo ubožejší než předtím, a přitom polovinu dat. Tak tomuhle se říká DELTA MODULATION.

Delta modulace má dvě drobné chybky
1. Komprese v poměru 1:2 není nic moc
2. U prudkých výkyvů zvuku se často vyskytuje "podtečení delta" - tedy rozdíl vzorků je více než vaše maximální hodnota delta.

Proto můžeme použít "expanzi delta" ve smyslu následující tabulky
Vyslaný kódHodnota delta
-3-64
-2-8
-1-1
00
11
28
364

Takže do databáze si uložíme 3bitové signed hodnoty a delta vybíráme z tabulky.

Postup jak se "surová data" třeba z WAW souboru kódují do podoby delta hodnot se nazývá Error Diffusion. Tedy při výpočtu odeslání "expandovaného delta" vznikne určitá chyba, která se přičte k hodnotě minulého vzorku aby se vzala do úvahy při výpočtu dalšího vzorku a nekumulovala se.

Příklad v Pseudokódu.
TRUE_ DELTA = CURRENT_X - LAST_X
SEND_DELTA = compress_delta (TRUE_DELTA)
ERROR_DELTA = TRUE_DELTA - expand_delta ( SEND_DELTA )
LAST_X = LAST_X + ERROR_DELTA

Jak jste jistě pochopili tak procedura COMPRESS_DELTA vezme skutečnou hodnotu delta a snaží se najít, která hodnota z pravého sloupce tabulky (tedy -64, -8, -1, 0, 1, 8, 64) je hodnotě delta nejbližší a podle toho vrací hodnotu -3 až +3.
Stejně tak je myslím jasné, že procedura EXPAND_DELTA bere hodnoty -3 až +3 a vrací -64, -8, -1, 0, 1, 8, 64.
Jasné ?

Stále máme ubohý zvuk, kompresi 3:8 a algoritmus jako hrom. Aby to bylo ještě horší když začnete studovat jaké hodnoty delta jsou vhodné zjistíte, že kolem toho je literatury jako hrom, protože to je oblíbené téma akadademiků. Nicméně od 70. let existuje metoda, která zajistí kompresi akustického signálu v poměru 1:8 tedy jeden vzorek kóduje se jedním bitem, nic se nemusí nastavovat a algoritmus si delta nastaví sám. Jistě tušíte, že to je to záhadné CVSDM.
Takže ukázka v pseudokódu:

ACCUMULATOR = 0
DELTA = 1

FOR I=0 TO SAMPLE_COUNT
IF SAMPLE > ACCUMULATOR THEN
BEGIN
send (1)
ACCUMULATOR = ACCUMULATOR + DELTA
END
ELSE
BEGIN
send (0)
ACCUMULATOR = ACCUMULATOR - DELTA
END
IF (last_3_send_bits = 0b111) or (last_3_send_bits = 0b000) THEN DELTA = DELTA * 2
ELSE DELTA = ( DELTA +1 ) div 2
ACCUMULATOR = ( 120 * ACCUMULATOR + 64 ) >> 7
NEXT I

Jasné ?
Předpokládám že ne zcela takže se to pokusím ještě popsat slovy. Hodnota ACCUMULATOR - de facto nese součet všech hodnot DELTA, které už byly odeslány. Nový vzorek se porovoná s hodnotou ACCUMULATORU a podle toho se pošle 1 - když je vzorek větší , nebo 0 když je menší a hodnota DELTA se podle toho k akumulátoru přičte / odečte.
Pak následuje záhadná část s úpravami hodnot delta. Pokud poslední 3 vzorky byly všechy menší nebo všechny větší než AKUMULATOR (to znamená že se odeslaly 3 x 1 nebo 3 x 0 za sebou)- znamená to, že hodnota DELTA je příliš malá - proto se zdvojnásobí, pokud nenastala ani jedna z těchno variant hodnota delta se zmenší na polovinu, ale ne na nulu, proto tam je to (DELTA +1) / 2.
Předposlední řádek je naprosto záhadná manipulace s hodnotou AKUMULÁTORU - jedná se o to, že pokud tento algoritmus použijeme pro přenos dat z jednoho místa do jiného a dojde k chybě přenosu - hodnota akumulátoru by se už nikdy nesrovnala - tento algoritmus se nazývá LEAKY ACCUMULATOR (prosakující akumulátor). Tedy hodnota akumulátoru se vlastně exponenciálně půměruje k nule aby se chyba přenosu postupně "vstřebala".

Dekódování je zrcadlovým obrazem kódování včetně leaky accumulatoru. Tedy udržujete hodnotu DELTA a přičítáte / odečítáte ji od hodnoty ACCUMULATORu a hodnota ACCUMULATORU je vlastně výstup celého kódování.

Jak vypadá originální a dekódovaný signál vidíte na obrázku - ty ostré "spajky" v dekódovaném signálu jsou situace kdy hodnota DELTA vzrostla až příliš - pokud vám vadí stačí prohnat výstup tím nejjednodušším exponenciláním průměrem. Zásadní výhoda CVSDM je v tom, že klidně můžete algoritmus beze změny použít i pro 16 bitové hodnoty - pozor na přetečení pracovních proměnných zejména při výpočtu LEAKY ACCUMULATORU. Hodnota DELTA se automaticky přizpůsobí. Navíc komprese 1:8 je dostatečná na to abyste si mohli dovolit samplovací frekvenci 16kHz a to je v signálu slyšet jako výrazné zlepšení zvuku.

Takže nakonec jsme došli k paradoxu ztrátových kompresí - ztrátově komprimovaný signál je někdy lepší než nekomprimovaný - alias na velikém vysoce komprimovaném JPEGu vidíme více než na maličkém GIFu.

Zbývá už jenom tradiční rada pro brunety - nepadnou vám ohnivě červené kozačky, které jsou v obchodě poslední - nic si z toho nedělejte - ve vedlejším regálu jsou černé důchodky a je jich tam spousta....
 

Buď první, kdo ohodnotí tento článek.

Komentáře

1 kolemjdoucí kolemjdoucí | 28. listopadu 2013 v 9:20

Pěkný, ale není lepší si koupit obvod, který je k tomu přímo určen? Nuvoton vyrábí obvody ChipCorder ISDxxxx, na které se vejde 20 - 60s záznamů. Stojí to stovku, a kupodivu je mají i GME, SOS a TME... Má to i adresovací vývody, takže procesor jen vybere, který bojový pokřik se zrovna přehraje... za stovku to nevyvinete, prosedíte u toho daleko víc času, a ještě vám to sežere prostředky daného MCU/CPU, takže budete muset dát větší. Chápu že je to problematika na zprogramování jistě zajímavá, ale v tomto případě se opravdu nevyplatí to dělat softwarově.

2 petr-kubac petr-kubac | 28. listopadu 2013 v 9:47

[1]: Bojový pokřik je příklad - osobně jsem tohle používal k předávání křivek ultrazvukové odrazivosti okolí robota - na to předpokládám čip není ?

3 kolemjdoucí kolemjdoucí | 28. listopadu 2013 v 10:29

[Smazaný komentář] A co ten druhý odstavec „do 4 KHz řečového pásma”? To nevypadá jako ultrazvuk...

Jinak tomu čipu je samozřejmě jedno, jestli přehrává nějaký „pokřik”, nebo frekvenci pro echolokátor. Jen to asi opravdu musí být slyšitelná frekvence, pochybuju že jeho vzorkování a filtry dovolí něco jiného.

4 petr-kubac petr-kubac | 28. listopadu 2013 v 11:50

[Smazaný komentář] Ó maminko ....¨
Vysvětluji polopatisticky - Procesor pískne na 40 KHz a digitalizuje odraz - tím naplní buffer o velikosti 32 kilobyte - pak tento buffer musí odeslat "centrálnímu počítači" který potřebuje data ze všech ultrazvuků aby mohl sestavit  "mapu překážek" tak zpracuje obálkovou křivku, která má stále 8 kilobyte - tak tuto obálkovou křivku kompresuje pomocí CVSDM a odešle po sběrnici do centrálního počítače ....

5 kolemjdoucí kolemjdoucí | 28. listopadu 2013 v 12:36

ó tatínku... musí pískat na čtyřiceti?

6 kolemjdoucí kolemjdoucí | 28. listopadu 2013 v 12:44

Jo, musí, už mi to došlo - to máte koupené ultrazvuky... jsem si celou dobu myslel, že kutíte něco vlastního

7 petr-kubac petr-kubac | 28. listopadu 2013 v 13:38

"Ultrazvuky" jako celé moduly jsem nikdy nepoužíval - ale ultrazvukové mikrofony a reproduktory používám komerční, protože upéct si vlastní piezokeramický reprák není tak snadné - princip ale není ve frekvenci pískání, ale v tom, že zatímco vaše integráky jsou určeny pro PŘEHRÁVÁNÍ zvuků - já jsem používal CVSDM pro KOMUNIKACI mezi procesory.

8 m.marianek m.marianek | 29. listopadu 2013 v 10:12

[5]: "ó tatínku... musí pískat na čtyřiceti?"

Ne synku, zrovna na čtyřiceti nemusí, ale musí to být dost vysoko (řádově desítky kHz) jinak ten ultrazvuk uvidí prd. Poměrně malého robota budou zajímat i poměrně malé předměty (překážky) na 34kHz je délka vlny 1cm. Tak proč nepoužít komerční komponentu na čtyřiceti, když je "za babku" a je na těch 40kHZ od výrobce "naladěná".

9 Petr G. Petr G. | 29. listopadu 2013 v 12:16

Nemělo být smyslem článku poradit čtenářům jak s minimem práce přenést maximum dat za minimum času? To jestli si u toho budete pískat jak netopýr už nikdo zkoumat nebude.

10 kolemjdoucí kolemjdoucí | 29. listopadu 2013 v 17:54

Ještě někdo si chce kopnout? No, tak jsem to na začátku blbě pochopil, což jsem tu i přiznal... a má bejt? Nebo mýlit se už není lidské (zřejmě po nějaké šikovné novele)?

11 Bystroushaak Bystroushaak | 30. listopadu 2013 v 1:46

Ten algoritmus se mi líbí. Jednoduché, pochopitelné a docela účinné. To se o moc věcech říct nedá :)

Komentáře jsou uzavřeny.


Aktuální články

Reklama