Previous Entry Share Next Entry
2016-01

поток сознания на тему information theory

в описаниях всяческих навороченных способах кодирования и передачи информации (Reed-Solomon и прочие FEC, торрент, progressive JPEG, rateless/fountain коды, LZ4, PAQ и прочие подобные) часто не хватает важной штуки - graceful degradation, или, в каком-то смысле, latency.

в целом вот понятно, что shannon capacity канала можно достигать сколь угодно эффективно, но при этом выходит, что чем ближе код к этой самой капасити - тем больше процентов (пакетов? ну положим что у нас erasure) надо получить, чтобы хоть что-то увидеть.

и если для arbitrary bitstream'ов это еще как-то обьяснимо (ну надо нам найти точное решение уравнения, никуда не денемся), то для картинок, звука и прочего очень часто хочется всякого graceful degradation, ну, как у того же прогрессивного жпега или FLIF (новый лосслесс кодек для картинок, гуглится)

каких-то принципиальных причин, почему прогрессивка должна ухудшать битрейт - тоже не видно. ключевая проблема в том, что это надо глубоко смерживать два кодека, в смысле, компрессор и FEC.

и это, по-видимому, взрывает мозг дизайнерам кодеков (а в случае с видео есть еще и минимум два сценария, "гифка" и "авто-регулятор битрейта для стриминга"), из-за чего мы этого так до сих пор и не увидели, а жаль!

(это я раздумываю, как бы сделать так, чтобы видеостриминг при потерях пакетов деградировал по качеству, а не заикался, и что-то нифига не придумывается пока что, т.к. тут еще и битрейт экстремально низкий, увы)

This entry was originally posted at http://wizzard.dreamwidth.org/450177.html. It has comment count unavailable comments. Please comment there using OpenID.

  • 1
lyuden October 22nd, 2015
Разлагать всю картинку на фичи (например шахматная доска, круг в центре экрана и т.д.), ну например разлагать всю картинку в ряд Фурье. При потере нескольких фич общий смысл картинки останется, но пойдут разные глючные артефакты.

Вообще конечно для каждого фильма надо тренировать свою нейронную сеть чтобы она генерировала кадры и засылать ее вначале. Потом слать диффы того что выдает сеть и актуальных кадров. Какую то похожую фигню она нагенерирует, а если несколько диффов пропадет - ничего страшного. Диффы опять же быть маленькими ( помещаться в пакет) и влиять на весь экран сразу.

jakobz October 22nd, 2015
Так так видео-кодеки и работают - сохраняют разницу с предыдущим кадром. Основываясь на предыдущем кадре, кадре до него, и прочих фазах луны.

Когда в кино с торрентов, или телеке на цифровом канале вылетает битик - прекрасно все видно как оно работает.

lyuden October 23rd, 2015
Я фигню понаписал.

Я имел ввиду фичи не в 2D пространстве кадра а в 6 мерном пространстве X,Y,t,R,G,B. Кодеки то в основе насколько я понимаю имеют тот же JPEG который ограничивает артефакты тем, что разбивает кадр на мелкие квадратики.

Так квадратики можно делать не только в X,Y но и в X,t например ( и да это в некотором роде эквивалентно ключевым кадрам и прочему) И фичи тоже могут быть в этом пространстве. Собственно всякие алгоритмы поиска движения на видео такие фичи и ищут. И даже где то видел средства борьбы с артефактами типа тех что производит JPEG ибо это ломает алгоритмы.

Проблема с таким подходом в том что считать graceful degradation ибо это в общем и целом метрика сильно зависящая от устройстве человеческого зрения. Поэтому для каждого видеопотока это должно решаться видимо индивидуально, какой-нибудь насобаченной нейронной сетью которая сможет примерно сказать насколько этот способ кодирования хренов при потере пакетов.

Но это все не важно ибо хардварь то зафигачен и оптимизирован под MPEG, и поэтому MPEG и будет.

serbod October 23rd, 2015
Более того, кодеки с адаптивным битрейтом могут "авансом" выдать диффы для грядущего кадра. Беда в том, что если ключевой кадр битый, то по диффам картинку не восстановить.

Viktor Sovietov October 22nd, 2015
это фрактальную сжимачку надо...

jakobz October 22nd, 2015
Вообще, я тоже принципиальных каких-то проблем не вижу, как дилетант.

Т.е. задача примерно такая: взять 5-ти секундный кусок видео, и всякое про детали - засунуть назад. А всякое важное - вперед. Чтобы если человек не успел докачать - проиграть что есть, без деталей. Хотя думаю что тут примерно история такая: усираться надо дохера, а визуально - будет заметно дергание туда-сюда. Юзер скажет что-то типа "включите мне уже мои честные 320p, или выключите этот цирк совсем".

Можно levgem-а позвать попробовать - он шарит.

Edited at 2015-10-22 09:48 pm (UTC)

wizzard0 October 22nd, 2015
ненене, у меня считай UDP, и пакеты проебываются, а не "файл не докачался"

jakobz October 22nd, 2015
Так видео так и стримится - считай у тебя UDP-пакет - это потенциально недокаченый кусок видоса.

То что битики в пакетах бьются - это отдельное.

Там, кстати, стопудово где-нибудь должна быть теория типа "сколько информации можно передать битиками, которые переворачиваются с такой-то вероятностью". Читал что-то про эволюцию модемов - там ад матана наворотили же, в свое время.

Но в любом случае, если думать инженерно, проблема не в том что так нельзя делать. Можно сделать цифровой канал, с какой-то предсказуемой вероятностью битых бит. А поверх этого канала сделать кодек. Кстати Audio CD вот - практический пример, там именно так и было.

Проблема в том, что вокруг этого канала все тоже станет инженерно сложно. Цифровой канал - отличная абстракция, даже если можно на 40% лучше выбить хитрожопой математикой - не отобьется.

thedeemon October 24th, 2015
Дык Клод Шеннон в 50-х как раз об этом всем и писал с формулами. О чем ТС и говорит.

jakobz October 22nd, 2015
Кстати, с тем что веб-страничка умеет грузиться потихоньку, дергаясь и конвульсируя - сейчас тоже ведь все борятся. Какими-нибудь там когнитивными анимациями, например. Ну или перформансом, у кого есть.

Т.е. современному юзеру надо application-feel, ему надо чтобы сначало было черное, потом сразу белое появилось, и в процессе глаза не ебло.

Короче даже для HTML идея progressive чото-там - обломалась.

sassa_nf October 22nd, 2015
ну тут-то вариант другой. Пришло изображение ногами вперед. Рид-Соломон задерживается. Если он не успевает до скольки-то милисекунд, показываем, что есть. Картинку не будем улучшать, т.к. через 40мс новую нужно рисовать. Никаких "дерганий" как с ХТМЛ не предвидится.

А теперь, допустим, задерживается больший кусок картинки, чем можно восстановить с помощью Рид-Соломона. Автор спрашивает: а разве что-то фундаментальное мешает кодировать так, чтобы можно было деградированную картинку показать?

И вот складывается впечатление, что нет, такого фундаментального ограничения нет.

jakobz October 22nd, 2015
Да куда уж лучше кодировать чем HTML, скажем если у картинок размеры прописаны. И вот оно открывается, начинает грузится. Вместо картинок даже можно руками фон поставить примерно в цвет картинки.

Что юзеры скажут? Они скажут идите в жопу. Нам надо крутилку на секунду, мы не хотим видеть визуализацию ваших мат-алгоритмов. И пойдут и отнесут деньги тому, кто им сделает 5G. А не тому, что придумает хитрожопый кодек для 3G.

sassa_nf October 22nd, 2015
наоборот. Была у нас тут эпоха аналогового телевидения. Мимо дома проезжает поезд - на экране пролетает снег. А теперь эпоха цифрового. Холодильник включается - изображение замирает, выпадает несколько квадратиков, по контурам лиц появляется мусор, а звук продолжает, как ни в чем не бывало.

Уж лучше бы просто снежок. Какбы, хотелось бы размазать дефект по чуть-чуть по всему экрану, а не сконцентрировать в несколько квадратиков и в пару секунд задержки анимации.

wizzard0 October 22nd, 2015
да, речь именно об этом.

jakobz October 22nd, 2015
В той же ситуации с холодильником - у тебя бы вообще ничего бы не ловило бы. Мы с батей намаялись с антеннами в свое время - чтобы поймать каналы от местной вышки нормально. И все дома в этих антеннах были.

А ща проволоку втыкаешь - и Full HD прилетает.

Так что не надо за аналог горевать.

wizzard0 October 22nd, 2015
> Так что не надо за аналог горевать.

надо отметить, что невзирая на всю продвинутость Viterbi декодеров, кодов Рида-Соломона и красоту OFDM/COFDM - чувствительность лучших представителей приемников DVB-T таки на 3-5 децибел хуже приемников PAL (если транслировать и там, и там SD, на HD еще ниже, понятное дело)

jakobz October 22nd, 2015
Ну тут спорить не буду. Просто помню что тогда все дома были в самодельных антеннах, при наличии общей на крыше. Сейчас - тупо провод втыкаешь, и на тебе HD.

Но нельзя отрицать что за 20 лет потенциально стало настолько же и в аналоге, как минимум на уровне металла. Хотя FM как глючило и терялось между холмами - так оно и.

wizzard0 October 22nd, 2015
> Хотя FM как глючило и терялось между холмами - так оно и.
ну так это законы физики, от них сложновато убежать.

кстати, про холмы. загоризонтная и подземная радиосвязь кстати сейчас стала доступнее и дешевле тоже ;) как ни странно из-за развития компов, которые могут хитровывернуто обработать радиосигнал, как нельзя было раньше

все равно недешево и громоздко, но скажем МЧС может себе позволить, а не только авианосцы с генштабом

sassa_nf October 22nd, 2015
Так я за аналогом и не скучаю, я описываю, чего бы хотелось от кодека. Рассеять мусор по-немножку лучше, чем вывалить в одном месте кирпич.

blackyblack October 24th, 2015
Надо короче гнать в параллель поток 240п и выбранный пользователем. Если пользовательский поток пропал, то переключаемся на fallback 240 и какой-никакой юзер экспирьенс обеспечим.

wizzard0 October 25th, 2015
Ну да, но хочется закодировать выбранный поток не просто так, а с использованием этого baseline.

wizzard0 October 22nd, 2015
5G, 3G, буржуи :) тут о 10-20 кбит речь идет вообще ;)

на 3G я просто закодировал бы два стрима, а тут пока что похоже на то, что надо изгаляться и транслировать изменения 3д модельки и перемещения камеры внутри оной...

jakobz October 22nd, 2015
Так я автору и отвечаю что нет - проблем нет. Есть CDDA - который пишет запасной битик и то и дело интерполирует на грязном сидюке. Есть вроде кодеки в телефонии - которые тоже примерное делают.

Проблем две:
- от этого очень сложно абстрагироваться. SSH поверх битых бит не сработает. HTTP - тоже.
- ценность для юзеров представляет не скорость открытия картинки, и какое-то математическое моргание. Им нужен внятный уровень связи. Скажем в жопе мира в лесу - можно потерпеть и ад сотоны, если нужно на одной страничке посмотреть расписание электричек. Но во всех других случаях я бы хотел видеть не абстрактные "палки". Я хочу видеть "тут можно смотреть ютуб". И если я вижу "можно смотреть ютуб" - у меня действительно пашет ютуб без лагов. Все эти полумеры типа "мы тебе покажем половину JPEG" - их проходили уже. Юзерам не надо половину JPEG, им надо либо всё, либо ничего.

Мы вообще - последние динозавры, которые воспринимают что в сайт, в котором еще не все вгрузилось, можно куда-то еще там нажимать.

wizzard0 October 22nd, 2015
> SSH поверх битых бит не сработает.
mosh вот работает :)

> Юзерам не надо половину JPEG, им надо либо всё, либо ничего.
угу, я даже знаю, про каких юзеров идет речь. тут вот надо чтобы хоть что-то было.

redreptiloid October 22nd, 2015
а почему не видно принципиальных причин ?
imho, навскидку интуитивно представить, если взять кубики (обычные детские) и выкладывать из них картинку то она займет в пространстве больший объем чем если кубики паковать плотно, из-за неявной информации хранящейся в "пустых местах". ну и "хоть какая то картинка+картинка в хорошем качестве" несут больше информации в кадре чем "картинка в хорошем качестве". цели оптимизации разные получаются.
я бы больше уделял внимание обработке на стороне передатчика, "векторизуя" картинку - позволит понимать суть фильма а отдельные детали передавая уже по указанию пользователя.

wizzard0 October 22nd, 2015
> а почему не видно принципиальных причин ?
скажем так, можно закодировать высокий битрейт (это то что есть), можно низкий избыточно + высокий, а хочется низкий избыточно + (высокий на базе низкого).

sab123 October 22nd, 2015
Так а что мешает самому вычесть низкий из высокого перед кодированием, и потом самому же сложить назад? Или при этом съедут какие-то важные свойства, влияющие на качество кодирования?

wizzard0 October 23rd, 2015
мнэ... оно не так просто делается, как кажется :(

ну т.е. вычитать надо на непонятно каком уровне, одними квантизаторами нынче не обойдешься :(

pound_sterling October 22nd, 2015
имхо
решение такой проблемы - это прорыв, научное достижение как теория относительности,
потому что поток информации (видео, аудио, графику, текст и тд)
нужно будет научиться резать
не поперек а вдоль.

Сейчас же поток режут на кадры/файлы,
теряя кадр/файл теряешь все,
а нужно будет резать на слои,
например для видео это бекграунд, второстепенные темы/актеры, основная тема/актер, отдельные элементы интерьера,
и если прерывается один слой - второстепенная тема к примеру,
то видеопоток не исчезает полностью, а "замораживается" состояние одного его элемента,
то есть в итоге мы можем видеть результат действия (взрыв в видео-потоке),
не наблюдая начального действия (размещения бомбы/выстрела/столкновения)
или выпадение любого слоя не разрушающего весь поток.

...

wizzard0 October 22nd, 2015
да, что-то в таком духе. его не делают еще и потому, что обычно кодек работает поверх надежного канала, который доставляет таки все биты, и кусочки из него не пропадают просто так.

sab123 October 22nd, 2015
Ну, сермяжное решение через избыточность может быть таким:

Перевести картинку в низкое разрешение/битрейт. Закодировать. Условно говоря, положить в сторону. Теперь вычесть эту картинку из полной. Закодировать отдельно. Взять положенную в сторону картинку в низком разрешении и присобачить каждый ее пакет к скажем трем или десяти пакетам высокого разрешения. Эти сборные пакеты послать. Ну или не присобачивать, а просто посылать данные низкого разрешения отдельно во многих экземплярах. На приемной стороне раскодировать обе части и сложить. Показать полученное.

В самом сермяжном случае можно даже пропустить сложение-вычитание, а просто посылать две копии данных - одна в низком разрешении и нескольких экземплярах, вторая - в высоком разрешении.

Если есть возможность пометить разный приоритет у пакетов, то можно уменьшить избыточность, посылая данные низкого разрешения в отдельных пакетах с более высоким приоритетом (и потому меньшим шансом потери).

wizzard0 October 22nd, 2015
тут надо учитывать, что baseline, который мы пытаемся обогнать - это h.263/h.265, state of the art видеокодеки :)

и надо не только обогнать, а еще и втрамбовать картинку, которая не хуже чем если просто уменьшить битрейт и накрутить сверху избыточный кодек, на котором таки никогда не будет ничего выпадать :)

sab123 October 22nd, 2015
Избыточность - это заведомые потери. С ней "не хуже" не получится. Тут заведомый компромисс - отдается часть качества за надежность. А чтоб отдавать меньше качества, можно например не тупо посылать три копии, а какой-нибудь хэмминговый код.

Кстати, пример из жизни: в скайповом видеочате замечательное качество изображения, но работает он только на приличных каналах. Как только качество канала падает, все погибает. В гугловом хэнгауте качество видео безобразное, но он продолжает работать на таких каналах, где в скайпе загибается не только видео, но и звук.

sergey_cheban October 22nd, 2015
Как вариант: кодируем ч/б изображение с большой избыточностью, а цветность - с маленькой. При увеличении уровня шума изображение деградирует до ч/б.
Но вообще-то в таких ситуациях обратная связь рулит: она позволяет при снижении качества канала перенастроить кодек на более низкую скорость, а оставшиеся биты пустить на избыточность.

wizzard0 October 22nd, 2015
а вот нету обратной связи, увы.

livejournal October 23rd, 2015
Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal для Украины. Подробнее о рейтинге читайте в Справке.

justy_tylor October 23rd, 2015
Я пока не очень проснулся, но поймал мысль: а какова вероятность того, что именно дропнутся хвосты первого кадра, но дойдёт голова второго?

wizzard0 October 23rd, 2015
ну вот голову мы можем закодировать с большей избыточностью

serbod October 23rd, 2015
Простое решение - каждый кадр представить как N частей размером не более MTU (1200 байт, например), при этом каждая часть содержит каждый N-ый пиксель кадра. Получив даже один пакет кадра, уже имеем картинку размером с иконку, растянув ее на весь экран. И чем больше пакетов получим, тем подробнее будет кадр.


thedeemon October 24th, 2015
Качество говно будет. Ибо намеренно теряется использование корреляций между близкими точками, а она дает львиную долю всего сжатия. А если корреляции использовать, то теряется независимость блоков, потеря одного отразится на внешнем виде других.

murkt October 23rd, 2015
Привет, прочти вот этот пост x264: the best low-latency video streaming platform in the world, может он натолкнёт тебя на нужные мысли. Цитата для затравки:

Without keyframes, it’s feasible to make every frame capped to the same size. With each frame split into packet-sized slices and the image constantly being refreshed by the magic intra refresh column, packet loss resilience skyrocketed, with a videoconference being “watchable” at losses as absurd as 25%.

No longer does 200ms seem out of reach. If anything, it’s now far more than we need. Because with –tune zerolatency, single-frame VBV, and intra refresh, x264 can achieve end-to-end latency (not including transport) of under 10 milliseconds for an 800×600 video stream.

wizzard0 October 23rd, 2015
Пост хороший, да.

Видео, правда, совсем другое, но мысли появились. Спасибо :)

murkt October 23rd, 2015
Ага, там прямо практика, а не размышления "ну может быть так". Интернет архив - чудо что такое, я помнил про этот пост, а самого блога уже нет в живых :( Хотя весной вроде ещё был, если судить по постам на реддите.

thedeemon October 24th, 2015

wizzard0 October 25th, 2015
Нууууууу, скажем так, гораздо ближе вот это - https://en.wikipedia.org/wiki/Hierarchical_modulation, но то что это именно так называется - я не знал, так что спасибо за ссылку :)

  • 1
?

Log in

No account? Create an account