r   e   k   l   a   m   a
r   e   k   l   a   m   a

Google chce patentu na uwolnione osiągnięcie polskiego matematyka

Strona główna AktualnościOPROGRAMOWANIE

Asymetryczne systemy liczbowe (ANS, Asymmetric Numeral Systems) to zbiór entropijnych kodowań, łączących ze sobą wysoki stopień kompresji z niewielkim kosztem przetwarzania. To osiągnięcie polskich matematyków zostało wykorzystane w bezstratnym kompresorze Zstandard Facebooka, wykorzystywanym przez Apple kompresorze LZFSE, oraz nowym kompresorze Google Draco. A teraz wygląda na to, że Google chce dla siebie na ANS uzyskać patent. Czy to pierwsza jaskółka ataków patentowych firm informatycznych na osiągnięcia matematyczne?

Czym jest kodowanie entropijne?

Kompresja danych składa się przynajmniej z dwóch etapów. W pierwszym poszukuje się możliwych do wykonania transformacji, które uproszczą te dane, np. wyszukanie powtarzających się sekwencji znaków. Drugi etap to poddanie przetransformowanego ciągu kodowaniu entropijnemu, uwzględniającemu stosunek ilości przenoszonej informacji do częstotliwości występowania danego ciągu. W uproszczeniu można powiedzieć, że znak o prawdopodobieństwie wystąpienia 1/2 niesie ze sobą 1 bit informacji, a znak o prawdopodobieństwie wystąpienia 1/256 już całe 8 bitów informacji.

W kodowaniu stosowane jest powszechnie tzw. kodowanie Huffmana, w którym znaki zapisywane są jako ciągi bitów – to rozwiązanie optymalne przy wykorzystaniu symboli, których prawdopodobieństwo da się wyrazić potęgą dwójki. Gdy jednak prawdopodobieństwa nie da się tak wyrazić, wówczas kodowanie Huffmana zawodzi – zawsze trzeba użyć przynajmniej 1 bit na zapisanie symbolu. Dlatego w takich sytuacjach sięga się po kodowanie arytmetyczne, które znacznie lepiej koduje ułamkowe bity, ale jego przetwarzanie wymaga znacznie większej mocy obliczeniowej.

r   e   k   l   a   m   a

W 2006 roku dr Jarosław Duda z Instytutu Informatyki i Matematyki Komputerowej Uniwersytetu Jagiellońskiego pokazał, że niekoniecznie trzeba wybierać między stopniem kompresji a kosztem obliczeń. Przedstawiona przez niego rodzina kodowań bazuje na asymetrycznych systemach liczbowych – uogólnieniach systemów pozycyjnych zapisu liczb (np. dziesiętnego czy szestnastkowego). Okazały się one równie efektywne jak kodowanie arytmetyczne i równie „tanie” obliczeniowo jak kodowanie Huffmana. Jak zapisywanie informacji w tych kodowaniach entropijnych działa – tego dowiecie się z ciekawego artykułu na Wikipedii.

Matematyka a internetowe wideo

Liczne systemy kodowania ANS (m.in. tANS, rANS, rABS i uABS) znalazły szybko zastosowanie w przemyśle komputerowym – dziś korzysta z nich nawet kilkanaście różnych koderów. Nic w tym dziwnego: entropiczne kodery są od 3 do 30 razy szybsze od kodowania Huffmana czy kodowania arytmetycznego. Szybko więc pojawili się zainteresowani opatentowaniem związanych z ANS technologii, licząc na to, że uzyskają patenty, zanim np. upowszechni się format wideo AV1, wolny i niezależny następca VP9, konkurent H.265/HEVC. Wykorzystuje on w fazie kodowania właśnie asymetryczne systemy liczbowe.

Pierwszą firmą, która taki patent próbowała uzyskać, był StoreLeap z Wielkiej Brytanii, dr Duda jednak zdołał zablokować proces przed brytyjskim urzędem patentowym. To jednak niewielka firma, niewielkie zagrożenie. Zupełnie inaczej wygląda sytuacja z Google, które stara się obecnie w Stanach Zjednoczonych i setce innych krajów (w tym Polsce) o patent na technologię kodowania wideo wykorzystującą ANS – i to mimo tego, że polski matematyk zrobił co mógł, by ANS umieścić w domenie publicznej.

Pomógł za darmo, niech nie przeszkadza

Teraz do amerykańskiego Urzędu Patentowego oraz Światowej Organizacji Własności Intelektualnej (WIPO) wpłynęła skarga dr Dudy, w której wskazuje, że Google w swoim wniosku patentowym wykorzystuje jego odkrycia – i to w pełnej tego świadomości: polski matematyk pomógł Google w implementowaniu ANS do ich kodera WebM. Podkreśla, że google’owy wniosek patentowy to jedynie przeróbka dobrze znanego, podręcznikowego wręcz sposobu kodowania współczynników przekształceń, reprezentujących bloki bitmapy w kompresji obrazu i wideo.

We wniosku Google powołuje się na dobrze znane podstawowe techniki ANS, wykorzystywane powszechnie w wielu publicznie dostępnych implementacjach. Co więcej, wniosek został tak sporządzony, by uzyskać patent nie tylko na jedno z kodowań, przy którym konkretnie pomagał dr Duda (rANS), ale by ograniczyć swobodne użycie innych wariantów ANS, szczególnie tANS. Oznacza to prawne kłopoty dla wszystkich istniejących dziś kompresorów obrazu, takich jak GST, jak i przyszłych zastosowań asymetrycznych systemów liczbowych.

Istnieje spora szansa na to, że polski matematyk utrze nosa amerykańskiej korporacji – International Searching Authority, jednostka WIPO odpowiedzialna za wyszukiwanie już opatentowanych rozwiązań, oceniła google’owy patent bardzo nisko, określając go jako bezpośrednie zastosowanie powszechnie znanych algorytmów. Najwyraźniej Google się trochę spóźniło: 10 lat temu te algorytmy nie były powszechnie znane. Wtedy jednak też Google wciąż pouczało, by nie być złym.

Dr Jarosław Duda zwraca uwagę w tym wszystkim na jedno: po tym, jak pomógł Google, mając nadzieję na dalszą formalną współpracę jego instytutu z korporacją, nastała cisza. Prawdopodobnie ze względu na ten wniosek patentowy.

© dobreprogramy
r   e   k   l   a   m   a
r   e   k   l   a   m   a

Komentarze

r   e   k   l   a   m   a
r   e   k   l   a   m   a
Czy wiesz, że używamy cookies (ciasteczek)? Dowiedz się więcej o celu ich używania i zmianach ustawień.
Korzystając ze strony i asystenta pobierania wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.