Как устроено сжатие с потерями

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

Часто сжа­тия без потерь недо­ста­точ­но. Сего­дня пого­во­рим о сжа­тии с потерями.

Чем отличается от сжатия без потерь

При таком сжа­тии мы теря­ем часть инфор­ма­ции. Но смысл алго­рит­мов сжа­тия в том, что­бы мы это­го не заме­ча­ли: сжа­тие долж­но про­ис­хо­дить так, что­бы всё важ­ное пере­да­лось, а неваж­ное — нет. 

Мож­но пред­ста­вить, что мы гово­рим с чело­ве­ком по теле­фо­ну. Его голос немно­го иска­жён, может пре­ры­вать­ся или немно­го сбо­ить. Но если мы смог­ли понять собе­сед­ни­ка, то нам доста­точ­но тако­го каче­ства. При этом мы можем не рас­слы­шать какие-то нюан­сы, не ощу­тить всю глу­би­ну баса или не оце­нить все оттен­ки инто­на­ций, но это нам и неваж­но. Раз­го­вор по теле­фо­ну — это при­мер пере­да­чи инфор­ма­ции с исполь­зо­ва­ни­ем сжа­тия с потерями. 

Сжатие фотографий

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

Из Вики­пе­дии: Цвет­ное изоб­ра­же­ние и его ком­по­нен­ты Y, CB и CR 

Эти слои наре­за­ют­ся на квад­ра­ты 8 × 8 пик­се­лей и коди­ру­ют­ся с помо­щью осо­бой мате­ма­ти­ки. Её смысл в том, что­бы понять: есть ли в этом квад­ра­те 8 × 8 что-то важ­ное. Если оно есть, то оно коди­ру­ет­ся и дан­ные сохра­ня­ют­ся. Если квад­рат более-менее одно­род­ный, то он запи­сы­ва­ет­ся как одно­род­ный, дан­ных мало. 

Эко­но­мия дан­ных про­ис­хо­дит как раз за счёт этой мате­ма­ти­ки: напри­мер, если в квад­рат 8 × 8 попал кусо­чек ясно­го неба, то там доста­точ­но ска­зать «весь кусок такого-то сине­го цве­та», и тогда нуж­но хра­нить немнож­ко дан­ных. А если на квад­рат при­шёл­ся какой-то угол или деталь, то дан­ных нуж­но сохра­нить больше. 

А если у вас кар­тин­ка наре­за­на отдель­но на яркость и отдель­но на цвет, вы эко­но­ми­те ещё боль­ше дан­ных: в слое с ярко­стью у вас будут все кон­траст­ные дета­ли, а в цве­то­вых сло­ях — плав­ные цве­то­вые пере­ли­вы. Плав­ные пере­ли­вы лег­че зако­ди­ро­вать, это будет неза­мет­но для глаза. 

Сжа­тие JPEG иде­аль­но под­хо­дит для фото­гра­фий, где раз­мер дета­лей намно­го боль­ше, чем раз­мер пикселей. 

Возь­мём стран­ное изоб­ра­же­ние вино­гра­да на ржа­вой тру­бе. Най­ди­те раз­ли­чия меж­ду дву­мя картинками:

Сле­ва — ори­ги­нал, спра­ва изоб­ра­же­ние сжа­то в 20 раз. Визу­аль­но раз­ни­цу заме­тить трудно.

Теперь сожмём ори­ги­нал в 415 раз: было 10 мега­байт, ста­ло 24 кило­бай­та. При этом мы всё рав­но пони­ма­ем, что на фото­гра­фии — вино­град с пло­да­ми на ржа­вой тру­бе. Наш мозг сгла­жи­ва­ет эти неров­но­сти и узна­ёт картинку.

Спра­ва уже вид­ны пик­се­ли и раз­мы­тость — это побоч­ные явле­ния силь­но­го сжатия.

Хуже все­го JPEG под­хо­дит для сжа­тия изоб­ра­же­ний, в кото­рых есть мел­кие дета­ли, ост­рые края и рез­кие кон­тра­сты. Осо­бен­но — если изоб­ра­же­ния мел­кие. Тогда алго­рит­мы JPEG созда­ют слиш­ком мно­го арте­фак­тов. Дизай­не­ры гово­рят, что кар­тин­ку заша­ка­ли­ло (от сло­ва «шакал»):

Убей­те меня 

Сжатие звука

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

Напри­мер, чело­ве­че­ское ухо в сред­нем вос­при­ни­ма­ет зву­ки часто­той от 20 герц до 20 кило­герц. 20 Гц — это супер­груд­ной бас, а 20 КГц — это супер­тон­кий писк. Что­бы зако­ди­ро­вать вол­ну с мак­си­маль­ной часто­той 20 КГц, на каж­дую секун­ду вам нуж­но 40 тысяч чисел раз­ме­ром 2 бай­та. Полу­ча­ет­ся, что секун­да несжа­то­го зву­ка будет зани­мать 80 килобайт.

Но содер­жа­тель­ная часть чело­ве­че­ско­го голо­са (та, в кото­рой заши­та вся инфор­ма­ция) закан­чи­ва­ет­ся на 4000 гер­цах. Если отре­зать у голо­са всё, что выше 4000 герц, вы запро­сто раз­ли­чи­те смысл слов и пой­мё­те инто­на­цию. Про­па­дёт лишь неко­то­рая «воз­душ­ность» зву­ка. Если нет цели сде­лать супер­кру­той звук, то алго­рит­мам нет смыс­ла коди­ро­вать диа­па­зон 4—20 КГц. 

Тогда из зву­ка отсе­ка­ет­ся лиш­няя инфор­ма­ция и коди­ру­ет­ся толь­ко диа­па­зон до 4 КГц. Для это­го коди­ро­ва­ния доста­точ­но 16 кило­байт в секун­ду. Это уже эко­но­мия в 5 раз!

Самая важ­ная часть голо­са вооб­ще бол­та­ет­ся в рай­оне 1000—2000 герц. Если отре­зать у голо­са всё от 2 до 20 КГц, то нам хва­тит 8 КБ в секун­ду, а это эко­но­мия в 10 раз по срав­не­нию с несжа­тым файлом. 

Срав­ни­те три вари­ан­та аудио: сна­ча­ла несжа­тый вари­ант, потом сжа­тый в 6 раз, нако­нец — в 160 раз:

При таком сжа­тии суще­ствен­но «съе­да­ют­ся» верх­ние часто­ты, но оно и понят­но: на их коди­ро­ва­ние ком­пью­те­ру нуж­но в несколь­ко раз боль­ше дан­ных, чем на коди­ро­ва­ние основ­ной инфор­ма­ци­он­ной нагруз­ки аудиофайла. 

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

Сжатие видео

Что­бы сжать видео, исполь­зу­ют ком­би­на­цию сжа­тия кар­ти­нок и зву­ка. И есть один допол­ни­тель­ный момент: сжа­тие толь­ко изме­ня­ю­щих­ся частей кад­ра. Как это работает: 

  1. В одной секун­де видео 25 кадров
  2. Если за секун­ду в кад­ре ниче­го осо­бо не про­изо­шло, то это будут 25 при­мер­но оди­на­ко­вых картинок
  3. Алго­рит­му нет смыс­ла коди­ро­вать каж­дую кар­тин­ку с нуля. Он возь­мёт одну кар­тин­ку как отправ­ную точ­ку, во всех сле­ду­ю­щих зако­ди­ру­ет толь­ко изме­не­ния по срав­не­нию с преды­ду­щим кадром
  4. В зави­си­мо­сти от того, насколь­ко мы хотим каче­ствен­ную кар­тин­ку на выхо­де, мы можем зада­вать сте­пень чув­стви­тель­но­сти алго­рит­ма: от «коди­руй, толь­ко если в кадр зале­тит раке­та» до «реа­ги­руй на мель­чай­шие изме­не­ния в кад­ре». Чем более чут­кий коди­ров­щик, тем боль­ше весит файл.

При­мер коди­ро­ва­ния одной и той же сце­ны с раз­ной чув­стви­тель­но­стью — на видео она отоб­ра­же­на в кило­би­тах в секун­ду. Чув­стви­тель­ность вли­я­ет на ито­го­вый раз­мер видеофайла:

Стримы и потоковое видео

В пото­ко­вом видео ситу­а­ция усу­губ­ля­ет­ся тем, что дан­ные нуж­но пере­да­вать мил­ли­о­нам людей как мож­но ско­рее. Поэто­му, поми­мо того что­бы сжи­мать видео, стри­мин­го­вые сер­ве­ра ещё и меня­ют его физи­че­ский раз­мер, то есть из боль­шой кар­тин­ки дела­ют маленькую.

Раз­ме­ры кад­ров в таких видео часто изме­ря­ют­ся в «стро­ках» — это те самые чис­ла воз­ле бук­вы p:

  • 144p — кадр состо­ит из 144 строк, то есть его высо­та — 144 пикселя
  • 480p — кадр высо­той 480 пикселей
  • 1080p — кадр высо­той 1080 пикселей

Соот­вет­ствен­но, чем выше кадр, тем он шире; тем боль­ше раз­мер изоб­ра­же­ния; тем боль­ше дета­лей в него влезает.

Самое низ­кое каче­ство, кото­рое есть в пото­ко­вом видео — 144p. Мут­ная кар­тин­ка и пик­се­ли, зато мож­но смот­реть даже с мед­лен­ным интернетом 
То же самое видео в фор­ма­те HD или 1080p — мож­но про­чи­тать даже мел­кие над­пи­си в интер­фей­се игры, запу­щен­ной на умных часах. Но для это­го нужен быст­рый интернет/img]

Бук­ва p в 1080p озна­ча­ет progressive — то есть коди­ру­ет­ся каж­дая стро­ка видео­фай­ла. А быва­ет ещё бук­ва i, кото­рая озна­ча­ет interlaced. Это зна­чит, что в одном кад­ре коди­ру­ют­ся каж­дые чёт­ные стро­ки, а в сле­ду­ю­щем — каж­дые нечёт­ные. Потом их объ­еди­ня­ют в одной кар­тин­ке, и если не знать, куда смот­реть, то мож­но не заме­тить подвоха.

Меж­строч­ное сжа­тие будет хоро­шо вид­но, если в кад­ре что-то дви­жет­ся. Вы заме­ти­те харак­тер­ные «полос­ки» и задво­е­ние изображения:

Маши­на кажет­ся раз­дво­ен­ной, пото­му что в одном кад­ре она была левее, в дру­гом — пра­вее, а потом эти два кад­ра соеди­ни­ли в одном, исполь­зуя черес­строч­ное кодирование 

И что нам с этим делать

Да ниче­го осо­бо. Радо­вать­ся, что в наше вре­мя мож­но смот­реть пото­ко­вое видео в пря­мом эфи­ре с теле­фо­на в раз­ре­ше­нии 1080p через сото­вую выш­ку, поль­зу­ясь рос­кош­ным сжа­ти­ем и широ­ко­по­лос­ным досту­пом в интернет.