Kompresja danych - Data compression

W przetwarzaniu sygnału , kompresję danych , kodowania źródłowego lub redukcji szybkości transmisji bitów jest proces kodowania informacji z wykorzystaniem mniejszej liczby bitów niż w oryginalnej reprezentacji. Każda konkretna kompresja jest albo stratna, albo bezstratna . Kompresja bezstratna redukuje ilość bitów, identyfikując i eliminując nadmiarowość statystyczną . Żadne informacje nie są tracone w bezstratnej kompresji. Kompresja stratna zmniejsza ilość bitów, usuwając niepotrzebne lub mniej ważne informacje. Zazwyczaj urządzenie, które wykonuje kompresję danych, jest nazywane koderem, a urządzenie, które wykonuje odwrócenie procesu (dekompresja) jako dekoder.

Proces zmniejszania rozmiaru pliku danych jest często nazywany kompresją danych. W kontekście transmisji danych nazywa się to kodowaniem źródłowym; kodowanie wykonywane u źródła danych przed ich przechowywaniem lub przesyłaniem. Kodowania źródłowego nie należy mylić z kodowaniem kanałowym , służącym do wykrywania i korekcji błędów lub kodowania liniowego , czyli środkami do mapowania danych na sygnał.

Kompresja jest przydatna, ponieważ zmniejsza zasoby wymagane do przechowywania i przesyłania danych. Zasoby obliczeniowe są zużywane w procesach kompresji i dekompresji. Kompresja danych podlega kompromisowi złożoności czasoprzestrzennej . Na przykład schemat kompresji wideo może wymagać drogiego sprzętu, aby wideo było dekompresowane wystarczająco szybko, aby można je było oglądać podczas dekompresji, a opcja pełnej dekompresji wideo przed jego obejrzeniem może być niewygodna lub wymagać dodatkowej pamięci. Projektowanie schematów kompresji danych wymaga kompromisu między różnymi czynnikami, w tym stopniem kompresji, ilością wprowadzonych zniekształceń (przy użyciu stratnej kompresji danych ) oraz zasobami obliczeniowymi wymaganymi do kompresji i dekompresji danych

Bezstratny

Algorytmy bezstratnej kompresji danych zwykle wykorzystują redundancję statystyczną do reprezentowania danych bez utraty jakichkolwiek informacji , dzięki czemu proces jest odwracalny. Kompresja bezstratna jest możliwa, ponieważ większość rzeczywistych danych wykazuje redundancję statystyczną. Na przykład obraz może mieć obszary koloru, które nie zmieniają się w ciągu kilku pikseli; zamiast kodowania „czerwony piksel, czerwony piksel, ...” dane mogą być zakodowane jako „279 czerwonych pikseli”. To jest podstawowy przykład kodowania run-length ; istnieje wiele schematów zmniejszania rozmiaru pliku przez eliminację nadmiarowości.

W Lempel-Ziv (LZ) metody kompresji są jedną z najbardziej popularnych algorytmów przechowywania bezstratnej. DEFLATE jest odmianą LZ zoptymalizowaną pod kątem szybkości dekompresji i stopnia kompresji, ale kompresja może być powolna. W połowie lat 80., po pracach Terry'ego Welcha , algorytm Lempel-Ziv-Welch (LZW) szybko stał się metodą z wyboru dla większości systemów kompresji ogólnego przeznaczenia. LZW jest używany w obrazach GIF , programach takich jak PKZIP i urządzeniach sprzętowych, takich jak modemy. Metody LZ wykorzystują model kompresji oparty na tabeli, w którym wpisy tabeli są zastępowane powtarzającymi się ciągami danych. W przypadku większości metod LZ ta tabela jest generowana dynamicznie na podstawie wcześniejszych danych wejściowych. Sama tabela jest często zakodowana w formacie Huffmana . Kody oparte na gramatyce, takie jak ten, mogą niezwykle skutecznie kompresować wysoce powtarzalne dane wejściowe, na przykład zbiór danych biologicznych tego samego lub blisko spokrewnionego gatunku, ogromny zbiór dokumentów wersjonowanych, archiwa internetowe itp. Podstawowym zadaniem kodów opartych na gramatyce jest konstruowanie gramatyka bezkontekstowa wyprowadzająca pojedynczy ciąg. Inne praktyczne algorytmy kompresji gramatyki obejmują Sequitur i Re-Pair.

Najsilniejsze nowoczesne sprężarki bezstratne wykorzystują modele probabilistyczne , takie jak predykcja przez częściowe dopasowanie . W Transformata Burrowsa-Wheelera może być również postrzegana jako formę pośrednią modelowania statystycznego. W dalszym udoskonaleniu bezpośredniego wykorzystania modelowania probabilistycznego , szacunki statystyczne mogą być połączone z algorytmem zwanym kodowaniem arytmetycznym . Kodowanie arytmetyczne to bardziej nowoczesna technika kodowania, która wykorzystuje obliczenia matematyczne maszyny skończonej do wytworzenia ciągu zakodowanych bitów z serii symboli danych wejściowych. Może osiągnąć lepszą kompresję w porównaniu z innymi technikami, takimi jak lepiej znany algorytm Huffmana. Wykorzystuje stan pamięci wewnętrznej, aby uniknąć konieczności wykonywania mapowania jeden-do-jednego poszczególnych symboli wejściowych na odrębne reprezentacje, które używają całkowitej liczby bitów, i czyści pamięć wewnętrzną dopiero po zakodowaniu całego ciągu symboli danych . Kodowanie arytmetyczne stosuje się szczególnie dobrze do zadań adaptacyjnej kompresji danych, w których statystyki różnią się i są zależne od kontekstu, ponieważ można je łatwo połączyć z adaptacyjnym modelem rozkładu prawdopodobieństwa danych wejściowych. Wczesnym przykładem zastosowania kodowania arytmetycznego była opcjonalna (ale nie szeroko stosowana) funkcja standardu kodowania obrazów JPEG . Od tego czasu jest stosowany w różnych innych projektach, w tym H.263 , H.264/MPEG-4 AVC i HEVC do kodowania wideo.

Stratna

Pod koniec lat 80. obrazy cyfrowe stały się bardziej powszechne i pojawiły się standardy bezstratnej kompresji obrazu . Na początku lat 90. zaczęto szeroko stosować metody kompresji stratnej. W tych schematach akceptowana jest pewna utrata informacji, ponieważ usunięcie nieistotnych szczegółów może zaoszczędzić miejsce w pamięci. Istnieje odpowiedni kompromis między zachowaniem informacji a zmniejszeniem rozmiaru. Schematy stratnej kompresji danych są opracowywane na podstawie badań nad tym, jak ludzie postrzegają dane, o których mowa. Na przykład ludzkie oko jest bardziej wrażliwe na subtelne zmiany luminancji niż na zmiany koloru. Kompresja obrazu JPEG działa częściowo poprzez zaokrąglanie nieistotnych bitów informacji. Wiele popularnych formatów kompresji wykorzystuje te różnice percepcyjne, w tym psychoakustykę w przypadku dźwięku oraz psychowizualność w przypadku obrazów i wideo.

Większość form kompresji stratnej opiera się na kodowaniu transformacji , zwłaszcza dyskretnej transformacji kosinusowej (DCT). Została po raz pierwszy zaproponowana w 1972 roku przez Nasira Ahmeda , który następnie opracował działający algorytm wraz z T. Natarajanem i KR Rao w 1973 roku, przed wprowadzeniem go w styczniu 1974 roku. DCT jest najczęściej stosowaną metodą kompresji stratnej i jest wykorzystywana w formatach multimedialnych do obrazy (takie jak JPEG i HEIF ), wideo (takie jak MPEG , AVC i HEVC ) i audio (takie jak MP3 , AAC i Vorbis ).

Stratna kompresja obrazu jest stosowana w aparatach cyfrowych w celu zwiększenia pojemności pamięci. Podobnie, DVD , Blu-ray i strumieniowe wideo używają stratnych formatów kodowania wideo . Kompresja stratna jest szeroko stosowana w wideo.

W stratnej kompresji dźwięku stosuje się metody psychoakustyki w celu usunięcia niesłyszalnych (lub mniej słyszalnych) składników sygnału audio . Kompresja mowy ludzkiej jest często wykonywana przy użyciu jeszcze bardziej specjalistycznych technik; kodowanie mowy wyróżnia się jako odrębna dziedzina od ogólnej kompresji dźwięku. Kodowanie mowy jest używane w telefonii internetowej , na przykład kompresja audio jest używana do zgrywania płyt CD i jest dekodowana przez odtwarzacze audio.

Stratna kompresja może spowodować utratę generacji .

Teoria

Teoretyczną podstawę kompresji dostarcza teoria informacji , a dokładniej algorytmiczna teoria informacji dla kompresji bezstratnej oraz teoria prędkości i zniekształceń dla kompresji stratnej. Te obszary badań zostały zasadniczo stworzone przez Claude'a Shannona , który opublikował podstawowe artykuły na ten temat pod koniec lat 40. i na początku lat 50. XX wieku. Inne tematy związane z kompresją obejmują teorię kodowania i wnioskowanie statystyczne .

Nauczanie maszynowe

Istnieje ścisły związek między uczeniem maszynowym a kompresją. System, który przewiduje prawdopodobieństwa a posteriori sekwencji, biorąc pod uwagę całą jej historię, może być wykorzystany do optymalnej kompresji danych (poprzez użycie kodowania arytmetycznego na rozkładzie wyjściowym). Optymalny kompresor może być użyty do przewidywania (poprzez znalezienie symbolu, który kompresuje najlepiej, biorąc pod uwagę poprzednią historię). Ta równoważność została wykorzystana jako uzasadnienie wykorzystania kompresji danych jako punktu odniesienia dla „ogólnej inteligencji”.

Alternatywny widok może pokazywać algorytmy kompresji niejawnie mapujące ciągi znaków na niejawne wektory przestrzeni cech , a podobieństwo oparte na kompresji mierzy podobieństwo obliczeniowe w tych przestrzeniach cech. Dla każdego kompresora C(.) definiujemy powiązaną przestrzeń wektorów ℵ, tak że C(.) odwzorowuje łańcuch wejściowy x, odpowiada normie wektora ||~x||. Wyczerpujące badanie przestrzeni cech leżących u podstaw wszystkich algorytmów kompresji jest wykluczone przez przestrzeń; zamiast tego wektory cech wybierają zbadanie trzech reprezentatywnych metod kompresji bezstratnej: LZW, LZ77 i PPM.

Zgodnie z teorią AIXI , połączeniem bardziej bezpośrednio wyjaśnionym w Hutter Prize , najlepszą możliwą kompresją x jest najmniejsze możliwe oprogramowanie, które generuje x. Na przykład w tym modelu skompresowany rozmiar pliku zip obejmuje zarówno plik zip, jak i oprogramowanie do rozpakowywania, ponieważ nie można go rozpakować bez obu, ale może istnieć jeszcze mniejsza łączona forma.

Różnicowanie danych

Kompresja danych może być postrzegana jako szczególny przypadek różnicowania danych . Różnicowanie danych polega na tworzeniu różnicy przy danym źródle i celu, z łataniem odtwarzającym cel przy danym źródle i różnicy. Ponieważ nie ma oddzielnego źródła i celu w kompresji danych, można rozważyć kompresję danych jako różnicowanie danych z pustymi danymi źródłowymi, a skompresowany plik odpowiada różnicy od niczego. Jest to to samo, co rozważanie entropii bezwzględnej (odpowiadającej kompresji danych) jako szczególnego przypadku entropii względnej (odpowiadającej różnicowaniu danych) bez danych początkowych.

Termin kompresja różnicowa służy do podkreślenia połączenia różnicującego dane.

Zastosowania

Obraz

Entropia kodowanie powstała w 1940 roku wraz z wprowadzeniem Kodowanie Shannona-Fano , podstawą Huffman kodowania , który został opracowany w 1950 roku Transform kodowania sięga końca 1960 roku, wraz z wprowadzeniem szybkiej transformaty Fouriera (FFT) kodowania w 1968 roku, a Transformacja Hadamarda w 1969 roku.

Ważną techniką kompresji obrazu jest dyskretna transformata kosinusowa (DCT), technika opracowana na początku lat 70. XX wieku. DCT jest podstawą formatu JPEG , formatu kompresji stratnej , który został wprowadzony przez Joint Photographic Experts Group (JPEG) w 1992 roku. JPEG znacznie zmniejsza ilość danych wymaganych do przedstawienia obrazu kosztem stosunkowo niewielkiego obniżenia jakości obrazu i stał się najczęściej używanym formatem plików graficznych . Jego wysoce wydajny algorytm kompresji oparty na DCT był w dużej mierze odpowiedzialny za rozpowszechnienie cyfrowych obrazów i zdjęć cyfrowych .

Lempel–Ziv–Welch (LZW) to algorytm kompresji bezstratnej opracowany w 1984 roku. Używany jest w formacie GIF , wprowadzonym w 1987 roku. DEFLATE , algorytm kompresji bezstratnej określony w 1996 roku, jest używany w formacie Portable Network Graphics (PNG) .

Kompresja falkowa , czyli zastosowanie falek w kompresji obrazu, rozpoczęło się po opracowaniu kodowania DCT. Standard JPEG 2000 został wprowadzony w 2000 roku. W przeciwieństwie do algorytmu DCT używanego przez oryginalny format JPEG, JPEG 2000 zamiast tego wykorzystuje algorytmy dyskretnej transformacji falkowej (DWT). Technologia JPEG 2000, która obejmuje rozszerzenie Motion JPEG 2000 , została wybrana jako standard kodowania wideo dla kina cyfrowego w 2004 roku.

Audio

Kompresja danych audio, której nie należy mylić z kompresją zakresu dynamiki , może potencjalnie zmniejszyć przepustowość transmisji i wymagania dotyczące przechowywania danych audio. Algorytmy kompresji audio są zaimplementowane w oprogramowaniu jako kodeki audio . Zarówno w przypadku kompresji stratnej, jak i bezstratnej redundancja informacji jest redukowana przy użyciu metod takich jak kodowanie , kwantyzacja , dyskretna transformata kosinusowa i predykcja liniowa w celu zmniejszenia ilości informacji wykorzystywanych do reprezentowania nieskompresowanych danych.

Algorytmy stratnej kompresji dźwięku zapewniają wyższą kompresję i są używane w wielu aplikacjach audio, w tym w Vorbis i MP3 . Te algorytmy prawie wszystkie opierają się na psychoakustyce, aby wyeliminować lub zmniejszyć wierność mniej słyszalnych dźwięków, zmniejszając w ten sposób przestrzeń wymaganą do ich przechowywania lub przesyłania.

Akceptowalny kompromis między utratą jakości dźwięku a wielkością transmisji lub pamięci zależy od aplikacji. Na przykład jedna płyta kompaktowa (CD) o pojemności 640 MB zawiera około godziny nieskompresowanej muzyki w wysokiej wierności , mniej niż 2 godziny muzyki skompresowanej bezstratnie lub 7 godzin muzyki skompresowanej w formacie MP3 ze średnią szybkością transmisji bitów . Dyktafon cyfrowy może zwykle przechowywać około 200 godzin wyraźnie zrozumiałej mowy w 640 MB.

Bezstratna kompresja dźwięku tworzy reprezentację danych cyfrowych, które można zdekodować do dokładnego cyfrowego duplikatu oryginału. Współczynniki kompresji wynoszą około 50–60% oryginalnego rozmiaru, co jest podobne do współczynników ogólnej bezstratnej kompresji danych. Kodeki bezstratne wykorzystują dopasowanie krzywej lub predykcję liniową jako podstawę do szacowania sygnału. Parametry opisujące estymację i różnicę między estymacją a rzeczywistym sygnałem są kodowane oddzielnie.

Istnieje wiele bezstratnych formatów kompresji dźwięku. Zobacz listę bezstratnych kodeków dla wykazu. Niektóre formaty są powiązane z odrębnym systemem, takim jak Direct Stream Transfer , używany w Super Audio CD i Meridian Lossless Packing , używany w DVD-Audio , Dolby TrueHD , Blu-ray i HD DVD .

Niektóre formaty plików audio zawierają kombinację formatu stratnego i korekcji bezstratnej; pozwala to na usunięcie korekty w celu łatwego uzyskania pliku stratnego. Do takich formatów należą MPEG-4 SLS (Scalable to Lossless), WavPack i OptimFROG DualStream .

Gdy pliki audio mają być przetwarzane, przez dalszą kompresję lub edycję , pożądane jest, aby pracować z niezmienionym oryginałem (nieskompresowanym lub skompresowanym bezstratnie). Przetwarzanie pliku skompresowanego stratnie w jakimś celu zwykle daje końcowy wynik gorszy od utworzenia tego samego skompresowanego pliku z nieskompresowanego oryginału. Oprócz edycji lub miksowania dźwięku, bezstratna kompresja dźwięku jest często używana do przechowywania archiwalnego lub jako kopie wzorcowe.

Stratna kompresja dźwięku

Porównanie spektrogramów audio w formacie nieskompresowanym i kilku formatach stratnych. Stratne spektrogramy pokazują ograniczenie pasma wyższych częstotliwości, co jest powszechną techniką związaną ze stratną kompresją dźwięku.

Stratna kompresja dźwięku jest wykorzystywana w wielu aplikacjach. Oprócz samodzielnych aplikacji do odtwarzania plików w odtwarzaczach MP3 lub komputerach, strumienie audio skompresowane cyfrowo są wykorzystywane w większości płyt DVD wideo, telewizji cyfrowej, multimediów strumieniowych w Internecie , radiu satelitarnym i kablowym, a także coraz częściej w naziemnych transmisjach radiowych. Kompresja stratna zazwyczaj zapewnia znacznie większą kompresję niż kompresja bezstratna, odrzucając mniej krytyczne dane na podstawie optymalizacji psychoakustycznych .

Psychoakustyka uznaje, że nie wszystkie dane w strumieniu audio mogą być odbierane przez układ słuchowy człowieka . Większość kompresji stratnej zmniejsza nadmiarowość, najpierw identyfikując dźwięki nieistotne percepcyjnie, to znaczy dźwięki, które są bardzo trudne do usłyszenia. Typowe przykłady obejmują wysokie częstotliwości lub dźwięki, które pojawiają się w tym samym czasie, co głośniejsze dźwięki. Te nieistotne dźwięki są kodowane z mniejszą dokładnością lub wcale.

Ze względu na charakter algorytmów stratnej, jakość dźwięku cierpi na utratę generacji cyfrowego , gdy plik zostanie rozpakowany i rekompresji. To sprawia, że ​​kompresja stratna nie nadaje się do przechowywania wyników pośrednich w profesjonalnych zastosowaniach inżynierii dźwięku, takich jak edycja dźwięku i nagrywanie wielościeżkowe. Jednak formaty stratne, takie jak MP3, są bardzo popularne wśród użytkowników końcowych, ponieważ rozmiar pliku jest zmniejszony do 5-20% oryginalnego rozmiaru, a megabajt może pomieścić około minuty muzyki w odpowiedniej jakości.

Metody kodowania

Aby określić, które informacje w sygnale audio są percepcyjnie nieistotne, większość algorytmów kompresji stratnej wykorzystuje transformacje, takie jak zmodyfikowana dyskretna transformata kosinusowa (MDCT), do konwersji próbkowanych przebiegów w domenie czasu w domenę transformacji, zwykle w domenie częstotliwości . Po przekształceniu, częstotliwości składowe mogą być traktowane priorytetowo w zależności od tego, jak są słyszalne. Słyszalność składowych widmowych oceniana jest na podstawie bezwzględnego progu słyszenia i zasad maskowania jednoczesnego — zjawiska, w którym sygnał jest maskowany innym sygnałem oddzielonym częstotliwością — a w niektórych przypadkach maskowania czasowego — gdzie sygnał jest maskowany innym sygnałem oddzielone czasem. Kontury o jednakowej głośności mogą być również wykorzystywane do ważenia percepcyjnej ważności komponentów. Modele kombinacji ludzkiego ucha i mózgu zawierające takie efekty są często nazywane modelami psychoakustycznymi .

Inne typy kompresorów stratnych, takie jak liniowe kodowanie predykcyjne (LPC) używane z mową, są koderami opartymi na źródle. LPC wykorzystuje model ludzkiego traktu głosowego do analizy dźwięków mowy i wywnioskowania parametrów wykorzystywanych przez model do ich wytwarzania z chwili na chwilę. Te zmieniające się parametry są przesyłane lub przechowywane i wykorzystywane do sterowania innym modelem w dekoderze, który odtwarza dźwięk.

Stratne formaty są często używane do dystrybucji strumieniowego dźwięku lub komunikacji interaktywnej (np. w sieciach telefonii komórkowej). W takich aplikacjach dane muszą być dekompresowane w miarę przepływu danych, a nie po przesłaniu całego strumienia danych. Nie wszystkie kodeki audio mogą być używane do przesyłania strumieniowego.

Opóźnienie jest wprowadzane przez metody używane do kodowania i dekodowania danych. Niektóre kodeki analizują dłuższy segment danych, zwany ramką , aby zoptymalizować wydajność, a następnie kodują go w sposób, który wymaga jednoczesnego odkodowania większego segmentu danych. Nieodłączne opóźnienie algorytmu kodowania może być krytyczne; na przykład w przypadku dwukierunkowej transmisji danych, takiej jak rozmowa telefoniczna, znaczne opóźnienia mogą poważnie pogorszyć postrzeganą jakość.

W przeciwieństwie do szybkości kompresji, która jest proporcjonalna do liczby operacji wymaganych przez algorytm, tutaj opóźnienie odnosi się do liczby próbek, które muszą zostać przeanalizowane przed przetworzeniem bloku audio. W przypadku minimalnym opóźnienie wynosi zero próbek (np. jeśli koder/dekoder po prostu zmniejsza liczbę bitów wykorzystywanych do kwantyzacji sygnału). Algorytmy w dziedzinie czasu, takie jak LPC, również często mają niskie opóźnienia, stąd ich popularność w kodowaniu mowy w telefonii. Jednak w algorytmach takich jak MP3, aby wdrożyć model psychoakustyczny w domenie częstotliwości, trzeba przeanalizować dużą liczbę próbek, a opóźnienie jest rzędu 23 ms.

Kodowanie mowy

Kodowanie mowy jest ważną kategorią kompresji danych dźwiękowych. Modele percepcyjne używane do oceny, jakie aspekty mowy słyszy ludzkie ucho, różnią się zasadniczo od modeli używanych w przypadku muzyki. Zakres częstotliwości potrzebny do przekazania dźwięków ludzkiego głosu jest zwykle znacznie węższy niż w przypadku muzyki, a dźwięk jest zwykle mniej złożony. W rezultacie mowa może być kodowana z wysoką jakością przy stosunkowo niskiej przepływności.

Na ogół osiąga się to poprzez kombinację dwóch podejść:

  • Kodowanie tylko dźwięków, które można wydobyć pojedynczym ludzkim głosem.
  • Odrzucenie większej ilości danych w sygnale — zachowanie wystarczającej ilości do zrekonstruowania „zrozumiałego” głosu, a nie pełnego zakresu częstotliwości ludzkiego słuchu .

Najwcześniejsze algorytmy stosowane w kodowaniu mowy (i ogólnie kompresji danych audio) to algorytm A-law i algorytm μ-law .

Historia

Solidyne 922: Pierwsza na świecie komercyjna karta dźwiękowa z kompresją bitową audio do komputerów PC, 1990 r

Wczesne badania audio zostały przeprowadzone w Bell Labs . Tam w 1950 roku C. Chapin Cutler złożył patent na modulację różnicowego kodu impulsowego (DPCM). W 1973 roku Adaptive DPCM (ADPCM) został wprowadzony przez P. Cummiskeya, Nikila S. Jayanta i Jamesa L. Flanagana .

Kodowanie percepcyjne zostało po raz pierwszy zastosowane do kompresji kodowania mowy , z liniowym kodowaniem predykcyjnym (LPC). Początkowe koncepcje LPC sięgają prac Fumitada Itakura ( Nagoya University ) i Shuzo Saito ( Nippon Telegraph and Telephone ) w 1966 roku. W latach 70. Bishnu S. Atal i Manfred R. Schroeder z Bell Labs opracowali formę LPC o nazwie adaptacyjne kodowanie predykcyjne (APC), algorytm kodowania percepcyjnego, który wykorzystuje właściwości maskowania ludzkiego ucha, a następnie we wczesnych latach 80. XX w. pojawił się algorytm predykcji liniowej wzbudzonej kodem (CELP), który osiągnął znaczny współczynnik kompresji w swoim czasie. Kodowanie percepcyjne jest używane w nowoczesnych formatach kompresji dźwięku, takich jak MP3 i AAC .

Dyskretna transformata kosinusowa (DCT), opracowana przez Nasira Ahmeda , T. Natarajana i KR Rao w 1974 roku, stanowiła podstawę zmodyfikowanej dyskretnej transformacji kosinusowej (MDCT) stosowanej w nowoczesnych formatach kompresji dźwięku, takich jak MP3, Dolby Digital i AAC. MDCT został zaproponowany przez JP Princena, AW Johnsona i AB Bradleya w 1987 roku, po wcześniejszych pracach Princena i Bradleya w 1986 roku.

Oscar Bonello, profesor inżynierii na Uniwersytecie Buenos Aires, opracował pierwszy na świecie komercyjny system kompresji dźwięku do automatyzacji transmisji . W 1983 roku, korzystając z psychoakustycznej zasady maskowania pasm krytycznych, opublikowanej po raz pierwszy w 1967 roku, zaczął opracowywać praktyczną aplikację opartą na niedawno opracowanym komputerze IBM PC , a system automatyzacji transmisji został uruchomiony w 1987 roku pod nazwą Audicom . Dwadzieścia lat później prawie wszystkie radiostacje na świecie korzystały z podobnej technologii produkowanej przez szereg firm.

Kompendium literatury dla szerokiej gamy systemów kodowania audio zostało opublikowane w IEEE Journal on Selected Areas in Communications ( JSAC ) w lutym 1988. Chociaż istniało kilka artykułów sprzed tego czasu, ta kolekcja dokumentowała całą gamę gotowych, roboczych kodery audio, prawie wszystkie wykorzystujące techniki percepcyjne i pewnego rodzaju analizę częstotliwości oraz bezszumowe kodowanie zaplecza.

Wideo

Kompresja wideo to praktyczna implementacja kodowania źródłowego w teorii informacji. W praktyce większość kodeków wideo jest używana wraz z technikami kompresji dźwięku do przechowywania oddzielnych, ale uzupełniających się strumieni danych jako jednego połączonego pakietu przy użyciu tak zwanych formatów kontenerowych .

Nieskompresowane wideo wymaga bardzo dużej szybkości transmisji danych . Chociaż kodeki bezstratnej kompresji wideo działają przy współczynniku kompresji od 5 do 12, typowy wideo z kompresją stratną H.264 ma współczynnik kompresji od 20 do 200.

Dwie kluczowe techniki kompresji wideo stosowane w standardach kodowania wideo to dyskretna transformacja kosinusowa (DCT) i kompensacja ruchu (MC). Większość standardów kodowania wideo, takich jak formaty H.26x i MPEG , zwykle wykorzystuje kodowanie wideo DCT z kompensacją ruchu (kompensacja ruchu blokowego).

Teoria kodowania

Dane wideo mogą być reprezentowane jako seria klatek obrazu nieruchomego. Takie dane zwykle zawierają duże ilości nadmiarowości przestrzennej i czasowej . Algorytmy kompresji wideo próbują zredukować nadmiarowość i przechowywać informacje w bardziej zwarty sposób.

Większość formatów kompresji wideo i kodeków wykorzystuje nadmiarowość przestrzenną i czasową (np. poprzez kodowanie różnicowe z kompensacją ruchu ). Podobieństwa można zakodować, przechowując jedynie różnice między np. czasowo sąsiadującymi ramkami (kodowanie międzyramkowe) lub przestrzennie sąsiadującymi pikselami (kodowanie wewnątrzramkowe). Międzyramkowe sprężania (czasowy kodująca delta ) (Re) używa danych z jednego lub więcej wcześniejszych lub późniejszych ramkach w sekwencji przedstawienie aktualnej ramki. Z drugiej strony kodowanie wewnątrz-klatkowe wykorzystuje tylko dane z bieżącej klatki, co w rzeczywistości jest kompresją nieruchomego obrazu .

Do kodowania wideo formatów ramki wewnętrznej stosowane w kamerach wideo i edycji zatrudniać prostsze kompresji wykorzystuje tylko przewidywania wewnątrz ramy. Upraszcza to oprogramowanie do edycji wideo, ponieważ zapobiega sytuacji, w której ramka P lub B odnosi się do danych usuniętych przez edytującego.

Zwykle kompresja wideo dodatkowo wykorzystuje techniki kompresji stratnej , takie jak kwantyzacja, które redukują aspekty danych źródłowych, które są (mniej lub bardziej) nieistotne dla ludzkiej percepcji wzrokowej, wykorzystując percepcyjne cechy ludzkiego wzroku. Na przykład niewielkie różnice w kolorze są trudniejsze do zauważenia niż zmiany jasności. Algorytmy kompresji mogą uśredniać kolor w tych podobnych obszarach, aby zmniejszyć przestrzeń, w sposób podobny do tych stosowanych przy kompresji obrazu JPEG . Podobnie jak w przypadku każdej kompresji stratnej, istnieje kompromis między jakością wideo a szybkością transmisji , kosztem przetwarzania kompresji i dekompresji oraz wymaganiami systemowymi. Wysoce skompresowany film może zawierać widoczne lub rozpraszające artefakty .

Inne metody niż dominujące formaty transformacji oparte na DCT, takie jak kompresja fraktalna , poszukiwanie dopasowania i użycie dyskretnej transformacji falkowej (DWT), były przedmiotem niektórych badań, ale zazwyczaj nie są stosowane w produktach praktycznych (z wyjątkiem wykorzystanie kodowania falkowego jako koderów nieruchomych obrazów bez kompensacji ruchu). Zainteresowanie kompresją fraktalną wydaje się słabnąć, co wynika z ostatnich analiz teoretycznych wykazujących porównawczy brak skuteczności takich metod.

Kodowanie międzyramkowe

Kodowanie międzyklatkowe działa poprzez porównywanie każdej klatki w filmie z poprzednią. Poszczególne klatki sekwencji wideo są porównywane z jednej klatki do drugiej, a kodek kompresji wideo wysyła tylko różnice do ramki odniesienia. Jeśli ramka zawiera obszary, w których nic się nie poruszyło, system może po prostu wydać krótkie polecenie, które kopiuje tę część poprzedniej ramki do następnej. Jeśli sekcje klatki poruszają się w prosty sposób, kompresor może wyemitować (nieco dłuższe) polecenie, które mówi dekompresorowi, aby przesunął, obrócił, rozjaśnił lub przyciemnił kopię. To dłuższe polecenie nadal pozostaje znacznie krótsze niż kompresja wewnątrzramkowa. Zazwyczaj koder przesyła również sygnał pozostałości, który opisuje pozostałe, bardziej subtelne różnice w obrazie referencyjnym. Stosując kodowanie entropijne, te sygnały resztowe mają bardziej zwartą reprezentację niż pełny sygnał. W obszarach wideo o większym ruchu kompresja musi kodować więcej danych, aby nadążyć za większą liczbą zmieniających się pikseli. Często podczas eksplozji, płomieni, stad zwierząt i niektórych ujęć panoramicznych szczegóły o wysokiej częstotliwości prowadzą do obniżenia jakości lub zwiększenia zmiennej szybkości transmisji bitów .

Hybrydowe formaty transformacji oparte na blokach

Etapy przetwarzania typowego kodera wideo

Obecnie prawie wszystkie powszechnie stosowane metody kompresji wideo (np. te w standardach zatwierdzonych przez ITU-T lub ISO ) mają tę samą podstawową architekturę, która sięga H.261, która została znormalizowana w 1988 roku przez ITU-T. Opierają się one głównie na DCT, stosowanym do prostokątnych bloków sąsiednich pikseli i przewidywaniu czasowym za pomocą wektorów ruchu , a obecnie również na etapie filtrowania w pętli.

Na etapie predykcji stosuje się różne techniki deduplikacji i kodowania różnicowego, które pomagają w dekorelacji danych i opisaniu nowych danych na podstawie już przesłanych danych.

Następnie prostokątne bloki (resztek) danych pikseli są transformowane do domeny częstotliwości, aby ułatwić kierowanie nieistotnych informacji w kwantyzacji i dla pewnej redukcji nadmiarowości przestrzennej. Dyskretnej transformaty cosinus (DCT), który jest szeroko stosowany w związku z tym wprowadzono przez N. Ahmed , T. Natarajan i KR Rao 1974.

Na głównym etapie stratnego przetwarzania dane są skwantowane w celu zredukowania informacji, które są nieistotne dla ludzkiej percepcji wzrokowej.

W ostatnim etapie redundancja statystyczna jest w dużej mierze eliminowana przez koder entropijny, który często stosuje jakąś formę kodowania arytmetycznego.

W dodatkowym etapie filtrowania w pętli do zrekonstruowanego sygnału obrazu można zastosować różne filtry. Obliczając te filtry również w pętli kodowania, mogą one pomóc w kompresji, ponieważ można je zastosować do materiału referencyjnego, zanim zostanie on użyty w procesie przewidywania, i można nimi kierować przy użyciu oryginalnego sygnału. Najpopularniejszym przykładem są filtry odblokowujące, które rozmywają artefakty blokujące wynikające z nieciągłości kwantyzacji na granicach bloków transformacji.

Historia

W 1967 roku AH Robinson i C. Cherry zaproponowali schemat kompresji pasma kodowania długości przebiegu do transmisji analogowych sygnałów telewizyjnych. Dyskretna transformata kosinusowa (DCT), która jest podstawą współczesnej kompresji wideo, została wprowadzona przez Nasira Ahmeda , T. Natarajana i KR Rao w 1974 roku.

H.261 , który zadebiutował w 1988 roku, wprowadził komercyjnie rozpowszechnioną podstawową architekturę technologii kompresji wideo. Był to pierwszy format kodowania wideo oparty na kompresji DCT, który następnie stał się standardem dla wszystkich głównych formatów kodowania wideo, które nastąpiły później. H.261 został opracowany przez wiele firm, w tym Hitachi , PictureTel , NTT , BT i Toshiba .

Najpopularniejszymi standardami kodowania wideo stosowanymi w kodekach są standardy MPEG . MPEG-1 został opracowany przez Motion Picture Experts Group (MPEG) w 1991 roku i został zaprojektowany do kompresji wideo w jakości VHS . Jego następcą został w 1994 roku MPEG-2 / H.262 opracowany przez wiele firm, głównie Sony , Thomson i Mitsubishi Electric . MPEG-2 stał się standardowym formatem wideo dla telewizji cyfrowej DVD i SD . W 1999 roku pojawił się MPEG-4 / H.263 , który był dużym krokiem naprzód w dziedzinie technologii kompresji wideo. Został opracowany przez wiele firm, przede wszystkim Mitsubishi Electric, Hitachi i Panasonic .

Najczęściej używanym formatem kodowania wideo jest H.264/MPEG-4 AVC . Został opracowany w 2003 roku przez szereg organizacji, przede wszystkim Panasonic, Godo Kaisha IP Bridge i LG Electronics . Firma AVC wprowadziła na rynek nowoczesne algorytmy kodowania binarnego z adaptacją kontekstu (CABAC) i kodowania o zmiennej długości z adaptacją kontekstu (CAVLC). AVC jest głównym standardem kodowania wideo dla płyt Blu-ray i jest szeroko stosowany w witrynach do udostępniania wideo i serwisach internetowych do przesyłania strumieniowego, takich jak YouTube , Netflix , Vimeo i iTunes Store , w oprogramowaniu internetowym, takim jak Adobe Flash Player i Microsoft Silverlight oraz w różnych Transmisje HDTV w telewizji naziemnej i satelitarnej.

Genetyka

Algorytmy kompresji genetycznej to najnowsza generacja bezstratnych algorytmów, które kompresują dane (zwykle sekwencje nukleotydów) przy użyciu zarówno konwencjonalnych algorytmów kompresji, jak i algorytmów genetycznych dostosowanych do określonego typu danych. W 2012 roku zespół naukowców z Johns Hopkins University opublikował algorytm kompresji genetycznej, który nie wykorzystuje genomu referencyjnego do kompresji. HAPZIPPER został dostosowany do danych HapMap i osiąga ponad 20-krotną kompresję (zmniejszenie rozmiaru pliku o 95%), zapewniając od 2 do 4 razy lepszą kompresję w znacznie szybszym czasie niż wiodące narzędzia do kompresji ogólnego zastosowania. W tym celu Chanda, Elhaik i Bader wprowadzili kodowanie oparte na MAF (MAFE), które zmniejsza niejednorodność zbioru danych poprzez sortowanie SNP według ich mniejszej częstotliwości alleli, w ten sposób ujednolicając zbiór danych. Inne algorytmy w latach 2009 i 2013 (DNAZip i GenomeZip) mają współczynniki kompresji do 1200 razy, co pozwala na przechowywanie 6 miliardów diploidalnych ludzkich genomów par zasad w 2,5 megabajtach (w stosunku do genomu referencyjnego lub uśrednione dla wielu genomów). Aby uzyskać punkt odniesienia w kompresorach danych genetycznych/genomicznych, zobacz

Perspektywy i obecnie niewykorzystany potencjał

Szacuje się, że całkowita ilość danych przechowywanych na urządzeniach pamięci masowej na świecie może być dodatkowo skompresowana przy użyciu istniejących algorytmów kompresji z pozostałym średnim współczynnikiem 4,5:1. Szacuje się, że łączna zdolność technologiczna świata do przechowywania informacji zapewnia 1300 eksabajtów cyfr sprzętowych w 2007 r., ale gdy odpowiednia zawartość jest optymalnie skompresowana, stanowi to tylko 295 eksabajtów informacji Shannona .

Zobacz też

Bibliografia

Zewnętrzne linki