v teorie informace a zpracování signálu, Diskrétní univerzální oddělovač (VOLE) je odšumění schéma pro obnovení sekvencí přes konečnou abecedu, které byly poškozeny a kanál bez paměti. DUDE navrhli v roce 2005 Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú a Marcelo J. Weinberger.[1]
Přehled
Diskrétní univerzální oddělovač[1] (DUDE) je a odšumění schéma, které odhaduje neznámý signál
přes konečnou abecedu z hlučné verze
Zatímco většina odšumění schémata ve zpracování signálu a statistika pojednává o literatuře signály nad nekonečnou abecedou (zejména signály se skutečnou hodnotou), DUDE řeší případ nekonečné abecedy. Hlučná verze
Předpokládá se, že bude generován vysíláním
prostřednictvím známého kanál bez paměti.
Pro pevné délka kontextu parametr
, DUDE počítá výskyty všech řetězců délky
objevit se v
. Odhadovaná hodnota
je určena na základě oboustranné délky
kontext
z
, s přihlédnutím ke všem ostatním žetonům v
se stejným kontextem, stejně jako se používá známá kanálová matice a funkce ztráty.
Myšlenku, která je základem DUDE, lze nejlépe ilustrovat, když
je oblastizace náhodného vektoru
. Pokud je podmíněné rozdělení
, jmenovitě distribuce bezhlučného symbolu
podmíněno hlučným kontextem
byl k dispozici, optimální odhadovač
bude Bayesova odpověď na
Naštěstí, pokud je kanálová matice známá a nedegenerovaná, lze toto podmíněné rozdělení vyjádřit pomocí podmíněného rozdělení
, konkrétně distribuce hlučného symbolu
podmíněno jeho hlučným kontextem. Toto podmíněné rozdělení lze zase odhadnout z individuálně pozorovaného hlučného signálu
na základě Zákon velkých čísel, za předpokladu
je „dostatečně velký“.
Použití schématu DUDE s délkou kontextu
do sekvence délky
přes konečnou abecedu
vyžaduje
operace a vesmír
.
Za určitých předpokladů je DUDE univerzální schéma ve smyslu asymptotického výkonu a také optimální denoiser, který má Oracle přístup k neznámé sekvenci. Přesněji řečeno, předpokládejme, že výkon odšumování je měřen pomocí daného jednoznakového kritéria věrnosti, a zvažte režim, kde délka sekvence
má sklon k nekonečnu a délce kontextu
inklinuje k nekonečnu „ne příliš rychle“. Ve stochastickém prostředí, kde dvojnásobně nekonečná sekvence bezhlučná sekvence
je realizace stacionárního procesu
, DUDE asymptoticky provádí, v očekávání, stejně jako nejlepší denoiser, který má Oracle přístup k distribuci zdroje
. V jednosekvenčním nebo „polostochastickém“ nastavení s a pevný dvojnásobně nekonečná sekvence
, DUDE asymptoticky funguje stejně jako nejlepší „odposuvník“ s posuvným oknem, jmenovitě jakýkoli odrušovač, který určuje
z okna
, který má Oracle přístup k
.
Problém diskrétního odšumění
Popis blokového diagramu problému diskrétního odšumění
Nechat
být konečnou abecedou pevné, ale neznámé původní „nehlučné“ sekvence
. Sekvence se přivádí do a kanál bez paměti (DMC). DMC funguje na každém symbolu
nezávisle, produkující odpovídající náhodný symbol
v omezené abecedě
. DMC je znám a označuje se jako
-podle-
Markovova matice
, jejichž záznamy jsou
. Je vhodné psát
pro
-sloupec
. DMC vytváří náhodnou hlučnou sekvenci
. Konkrétní realizace tohoto náhodného vektoru bude označena
Oddělovač je funkce
který se pokouší obnovit bezhlučnou sekvenci
ze zkreslené verze
. Specifická odškrtnutá sekvence je označena
.Problém výběru oddělovače
je známý jako odhad signálu, filtrování nebo vyhlazení. Pro porovnání kandidátních denoizérů jsme vybrali jednoznakové kritérium věrnosti
(například Hammingova ztráta) a definujte ztrátu symbolu oddělovače
na
podle

Řazení prvků abecedy
podle
, kritérium věrnosti může být dáno a
-podle-
matice se sloupci formuláře

Schéma DUDE
Krok 1: Výpočet empirického rozdělení v každém kontextu
DUDE opravuje symboly podle jejich kontextu. Délka kontextu
použitý je tuningový parametr schématu. Pro
, definujte levý kontext souboru
-tý symbol v
podle
a odpovídající pravý kontext jako
. Dvoustranný kontext je kombinace
levého a pravého kontextu.
Prvním krokem schématu DUDE je výpočet empirického rozdělení symbolů v každém možném dvoustranném kontextu podél hlučné sekvence
. Formálně daný dvoustranný kontext
který se objeví jednou nebo vícekrát
určuje empirické rozdělení pravděpodobnosti
, jehož hodnota u symbolu
je
![begin {zarovnat}
mu left (z ^ n, l ^ k, r ^ k right) [z] =
frac { Velký |
left {k + 1 leq i leq n-k , , | , , (z_ {i-k}, ldots, z_ {i + k}) = l ^ k z r ^ k right }
Velký |}
{ Big |
left {k + 1 leq i leq nk , , | , , l ^ k (z ^ n, i) = l ^ k text {and} r ^ k (z ^ n, i ) = r ^ k vpravo }
Velký |} ,.
end {zarovnat}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9a275f7032bc033748f8590c8305dd0024ac4df)
Tedy první krok schématu DUDE s délkou kontextu
je skenovat vstupní šumovou sekvenci
jednou a uložte délku
empirický distribuční vektor
(nebo jeho nenormalizovaná verze, vektor počtu) pro každý dvoustranný kontext nalezený spolu
. Protože jich je nanejvýš
možné oboustranné kontexty
, tento krok vyžaduje
operace a skladování
.
Krok 2: Výpočet Bayesovy odpovědi na každý kontext
Označte sloupec kritéria věrnosti jedním symbolem
, odpovídající symbolu
tím, že
. Definujeme Bayesova odpověď na libovolný vektor
délky
s nezápornými položkami jako

Tato definice je motivována v Pozadí níže.
Druhým krokem schématu DUDE je výpočet pro každý oboustranný kontext
pozorováno v předchozím kroku
a pro každý symbol
pozorované v každém kontextu (konkrétně jakékoli
takhle
je podřetězec z
) Bayesova reakce na vektor
, jmenovitě

Všimněte si, že sekvence
a délka kontextu
jsou implicitní. Tady,
je
-sloupec
a pro vektory
a
,
označuje jejich produkt Schur (entrywise), definovaný
. Násobení matic je hodnoceno před produktem Schur, takže
znamená
.
Tento vzorec předpokládal, že kanálová matice
je čtverec (
) a invertibilní. Když
a
není invertibilní, za rozumného předpokladu, že má celou řadu, nahradíme
výše s Moore-Penroseovou pseudo-inverzí
a místo toho vypočítat

Mezipamětí inverzní nebo pseudo-inverzní
a hodnoty
pro příslušné páry
, tento krok vyžaduje
operace a
úložný prostor.
Krok 3: Odhad každého symbolu podle Bayesovy odpovědi na jeho kontext
Třetím a posledním krokem schématu DUDE je skenování
znovu a spočítejte skutečnou odšuměnou sekvenci
. Symbol zamlčen zvolený k nahrazení
je Bayesova reakce na oboustranný kontext symbolu, konkrétně

Tento krok vyžaduje
operace a použila datovou strukturu vytvořenou v předchozím kroku.
Stručně řečeno, celý DUDE vyžaduje
operace a
úložný prostor.
Vlastnosti asymptotické optimality
DUDE je navržen tak, aby byl univerzálně optimální, a to optimální (je to v jistém smyslu, za určitých předpokladů) bez ohledu na původní sekvenci
.
Nechat
označují sekvenci DUDE schémat, jak je popsáno výše, kde
používá délku kontextu
to je implicitní v notaci. Vyžadujeme to jen
a to
.
Pro stacionární zdroj
Označit podle
soubor všech
- blokovací oddělovače, jmenovitě všechny mapy
.
Nechat
být neznámým stacionárním zdrojem a
být distribuce odpovídající hlučné sekvence. Pak
![begin {zarovnat}
lim_ {n to infty} mathbf {E} left [L _ { hat {X} ^ n_ {DUDE}} left (X ^ n, Z ^ n right) right] =
lim_ {n to infty} min _ { hat {X} ^ n in mathcal {D} _n} mathbf {E} left [L _ { hat {X} ^ n} left (X ^ n, Z ^ n
dobře dobře],,
end {zarovnat}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8af3a118abb3dd8f4de01ab5558326285324914a)
a existují obě omezení. Pokud navíc zdroj
je tedy ergodický
![begin {zarovnat}
limsup_ {n to infty} L _ { hat {X} ^ n_ {DUDE}} left (X ^ n, Z ^ n right) =
lim_ {n to infty} min _ { hat {X} ^ n in mathcal {D} _n} mathbf {E} left [L _ { hat {X} ^ n} left (X ^ n, Z ^ n
right) right] ,, , text {téměř jistě} ,.
end {zarovnat}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b17916ff86ca0c60d8364b53e8ea52f7b1d4d75)
Pro individuální sekvenci
Označit podle
soubor všech
-blok
- oddělovače posuvných oken řádu, konkrétně všechny mapy
formuláře
s
libovolný.
Nechat
být neznámým tichým sledem stacionárního zdroje a
být distribuce odpovídající hlučné sekvence. Pak
![begin {zarovnat}
lim_ {n to infty}
vlevo, odjet[
L _ { hat {X} ^ n_ {DUDE}} vlevo (x ^ n, Z ^ n vpravo) -
min _ { hat {X} ^ n in mathcal {D} _ {n, k}} L _ { hat {X} ^ n} vlevo (x ^ n, Z ^ n vpravo)
right] = 0 ,, , text {téměř jistě} ,.
end {zarovnat}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0a3139c5d8a1845acd386a4e3fd095bfb07696)
Neasymptotický výkon
Nechat
označte DUDE na s délkou kontextu
definováno dne
-bloky. Pak existují explicitní konstanty
a
na kterých záleží
sám, tak pro každého
a jakékoli
my máme
![begin {zarovnat}
frac {A} { sqrt {n}} B ^ k , leq
mathbf {E} left [L _ { hat {X} ^ n_ {k}} left (x ^ n, Z ^ n right) -
min _ { hat {X} ^ n in mathcal {D} _ {n, k}} L _ { hat {X} ^ n} vlevo (x ^ n, Z ^ n vpravo)
right] leq sqrt {k} frac {C} { sqrt {n}} | mathcal {Z} | ^ {k} ,,
end {zarovnat}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46a3ec285a4d3e1fcaae77f6707852b28e48c37a)
kde
je hlučná sekvence odpovídající
(jehož náhodnost je dána samotným kanálem)[2].
Ve skutečnosti platí se stejnými konstantami
jak je uvedeno výše pro žádný
-denoizér bloku
.[1] Dolní mez důkaz vyžaduje, aby kanálová matice
být čtvercový a dvojice
splňuje určitý technický stav.
Pozadí
Abychom motivovali konkrétní definici DUDE pomocí Bayesovy odpovědi na konkrétní vektor, nyní najdeme optimální oddělovač v neuniverzálním případě, kde neznámá sekvence
je realizace náhodného vektoru
, jehož distribuce je známa.
Zvažte nejprve případ
. Od společné distribuce
je znám, vzhledem k pozorovanému hlučnému symbolu
, neznámý symbol
je distribuován podle známé distribuce
. Objednáním prvků z
, můžeme tuto podmíněnou distribuci popsat dne
pomocí vektoru pravděpodobnosti
indexováno
, jehož
- vstup je
. Zjevně očekávaná ztráta pro výběr odhadovaného symbolu
je
.
Definujte Bayesova obálka vektoru pravděpodobnosti
, popisující rozdělení pravděpodobnosti na
, jako minimální očekávaná ztráta
a Bayesova odpověď na
jako předpověď, která dosahuje tohoto minima,
. Všimněte si, že Bayesova reakce má neměnný rozsah v tom smyslu
pro
.
Pro případ
pak je optimální oddělovač
. Tento optimální oddělovač lze vyjádřit pomocí okrajového rozdělení
sám, následovně. Když je matice kanálu
je invertibilní, máme
kde
je
-tý sloupec
. To znamená, že optimální denoiser je dán ekvivalentně
. Když
a
není invertibilní, za rozumného předpokladu, že má celou řadu, můžeme nahradit
s jeho Moore-Penrose pseudo-inverzní a získat

Nyní se mění na svévolné
, optimální oddělovač
(s minimální očekávanou ztrátou) je tedy dána Bayesovou odpovědí na 

kde
je vektor indexovaný pomocí
, jehož
- vstup je
. Vektor podmíněné pravděpodobnosti
je těžké vypočítat. Derivace analogická případu
výše ukazuje, že optimální oddělovač připouští alternativní zastoupení, a to
, kde
je daný vektor a
je vektor pravděpodobnosti indexovaný pomocí
jehož
- vstup je
Znovu,
je nahrazen pseudo-inverzí if
není čtvercový nebo invertibilní.
Při distribuci
(a tedy z
) není k dispozici, DUDE nahradí neznámý vektor
s empirickým odhadem získaným podél hlučné sekvence
sám, jmenovitě s
. To vede k výše uvedené definici DUDE.
Zatímco konvergenční argumenty za výše uvedenými vlastnostmi optimality jsou více jemné, poznamenáváme, že výše uvedené v kombinaci sBirkhoffova erodická věta, stačí dokázat, že pro stacionární ergodický zdroj je DUDE s kontextovou délkou
je asymptoticky optimální vše
-denoizéry posuvného okna.
Rozšíření
Zde popsaný základní DUDE předpokládá signál s jednorozměrnou indexovou sadou přes konečnou abecedu, známý kanál bez paměti a délku kontextu, která je předem stanovena. Uvolnění každého z těchto předpokladů bylo postupně zvažováno.[3] Konkrétně:
Aplikace
Aplikace na potlačení obrazu
Rámec pro stupně šedi založený na DUDE potlačení obrazu[6] dosahuje nejmodernějšího odšumění pro šumové kanály impulzního typu (např. „sůl a pepř“ nebo „M-ary symetrický“ šum) a dobrý výkon na Gaussově kanálu (srovnatelný s Nemístní prostředky schéma potlačení obrazu na tomto kanálu). Odlišná varianta DUDE použitelná pro obrázky ve stupních šedi je uvedena v.[7]
Aplikace na dekódování kanálu nekomprimovaných zdrojů
DUDE vedl k univerzálním algoritmům pro dekódování kanálů nekomprimovaných zdrojů.[17]
Reference
- ^ A b C T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu 'a M. J. Weinberger. Univerzální diskrétní odšumění: Známý kanál. Transakce IEEE na informační teorii, 51 (1): 5–28, 2005.
- ^ K. Viswanathan a E. Ordentlich. Dolní limity diskrétního univerzálního odšumění. Transakce IEEE o teorii informací, 55 (3): 1374–1386, 2009.
- ^ Ordentlich, E .; Seroussi, G .; Verd´u; Weinberger, M. J .; Weissman, T. „Úvahy o DUDE“ (pdf).
- ^ A. Dembo a T. Weissman. Univerzální odšumění pro kanál konečných vstupů-obecných výstupů. IEEE Trans. Inf. Theory, 51 (4): 1507–1517, duben 2005.
- ^ K. Sivaramakrishnan a T. Weissman. Univerzální odšumění diskrétních signálů spojité amplitudy. V Proc. 2006 IEEE Intl. Symp. na Inform. Theory, (ISIT’06), Seattle, WA, USA, červenec 2006.
- ^ A b G. Motta, E. Ordentlich, I. Ramírez, G. Seroussi a M. Weinberger, „TheDUDE framework for Continuous tone image denoising,“ IEEE Transactions onImage Processing, 20, No. 1, leden 2011.
- ^ A b K. Sivaramakrishnan a T. Weissman. Univerzální odšumění signálů spojité amplitudy s aplikacemi na obrazy. V Proc. Mezinárodní konference IEEE o zpracování obrazu, Atlanta, GA, USA, říjen 2006, str. 2609–2612
- ^ C. D. Giurcaneanu a B. Yu. Efektivní algoritmy pro diskrétní univerzální potlačení šumu pro kanály s pamětí. V Proc. 2005 IEEE Intl. Symp. na Inform. Theory, (ISIT’05), Adelaide, Austrálie, září 2005.
- ^ R. Zhang a T. Weissman. Diskrétní potlačení šumu pro kanály s pamětí. Communicationsin Information and Systems (CIS), 5 (2): 257–288, 2005.
- ^ G. M. Gemelos, S. Sigurjonsson, T. Weissman. Univerzální diskrétní odšumování nejistoty podkanálu minimax. IEEE Trans. Inf. Theory, 52: 3476–3497, 2006.
- ^ G. M. Gemelos, S. Sigurjonsson a T. Weissman. Algoritmy pro diskrétní potlačení nejistoty podkanálu. IEEE Trans. Signal Process., 54 (6): 2263–2276, červen 2006.
- ^ E. Ordentlich, M. J. Weinberger a T. Weissman. Vícesměrné kontextové sady s aplikacemi pro univerzální odšumění a kompresi. V Proc. 2005 IEEE Intl. Symp. onInform. Theory, (ISIT’05), Adelaide, Austrálie, září 2005.
- ^ J. Yu a S. Verd´u. Schémata pro obousměrné modelování diskrétních stacionárních zdrojů. IEEETrans. Informovat. Theory, 52 (11): 4789–4807, 2006.
- ^ S. Chen, S. N. Diggavi, S. Dusad a S. Muthukrishnan. Efektivní algoritmy shody řetězců pro kombinatorické univerzální odšumění. V Proc. konference IEEE Data Compression Conference (DCC), Snowbird, Utah, březen 2005.
- ^ G. Gimel’farb. Adaptivní kontext pro diskrétní univerzální oddělovač. V Proc. Strukturální, syntaktické a statistické rozpoznávání vzorů, společné mezinárodní semináře IAPR, SSPR 2004 a SPR 2004, Lisabon, Portugalsko, 18. – 20. Srpna, str. 477–485
- ^ E. Ordentlich, G. Seroussi, S. Verd´u, M. J. Weinberger a T. Weissman. Univerzální oddělovač diskrétních obrazů a jeho aplikace na binární obrazy. V Proc. IEEE International Conferenceon Image Processing, Barcelona, Katalánsko, Španělsko, září 2003.
- ^ E. Ordentlich, G. Seroussi, S. Verdú a K. Viswanathan, „UniversalAlgorithms for Channel Decoding of Uncompressed Sources“, IEEE Trans.Information Theory, sv. 54, č. 5, s. 2243–2262, květen 2008