Задание №7. Объём изображений и звука, хранение и передача

Размер изображения или длительность записи определяют, сколько данных нужно сохранить. Глубина кодирования задаёт, сколько бит приходится на один элемент, а скорость связи позволяет найти время передачи. В задании №7 эти связи используются в обе стороны: можно искать объём файла, число цветов, длительность записи или количество снимков, которые успеют передаться.

От параметров изображения к объёму

Растровое изображение состоит из сетки пикселей: для каждой точки хранится код её цвета. Если ширина равна W пикселям, а высота H, всего точек WH. Глубина цвета b показывает, сколько бит занимает код одного пикселя. При одинаковой длине кодов и без сжатия объём изображения в битах равен V=WHb.

Если вместо глубины дана палитра, сначала находится число бит на цвет. Например, для 1024 цветов достаточно 10 бит: 2^{10}=1024. Подстановка в формулу числа 1024 вместо глубины означала бы выделение 1024 бит каждому пикселю.

В этих расчётах 1\ \text{байт}=8\ \text{бит}, 1\ \text{Кбайт}=1024\ \text{байт}, 1\ \text{Мбайт}=1024^2\ \text{байт}. Поэтому перевод Кбайт в биты требует умножения на 8192. Заголовок файла и другие служебные данные учитываются только так, как указано в условии.

Сколько снимков можно передать

В задании EGE-07-0010 ↗ камера делает снимки размером 800\times600 пикселей с палитрой из 1024 цветов. Скорость передачи равна 1\,138\,688 бит/с, на пакет отведено не более 220 секунд. Требуется наибольшее число целых снимков в пакете.

Глубина цвета равна 10 бит. Поэтому один снимок содержит 800\cdot600\cdot10=4\,800\,000 бит. Скорость v означает объём, который передаётся за одну секунду. За время T канал пропускает vT бит; в данном случае это 1\,138\,688\cdot220=250\,511\,360 бит.

Деление пропускной способности за 220 секунд на объём одного снимка даёт 250\,511\,360/4\,800\,000\approx52{,}19. Это вместимость в снимках, а не допустимое дробное количество фотографий. Помещаются 52 снимка; округление до 53 превысило бы лимит.

Проверка границы сохраняет исходный смысл: 52\cdot4\,800\,000=249\,600\,000 бит укладываются в лимит, а 53\cdot4\,800\,000=254\,400\,000 бит уже нет. Ответ: 52.

Когда объём известен, а палитра неизвестна

В EGE-07-0028 ↗ изображение имеет размер 240\times2048 пикселей, а файл занимает не более 404 Кбайт без заголовка. Для поиска максимальной палитры сначала находится максимально допустимая целая глубина цвета:

b\leq\frac{404\cdot1024\cdot8}{240\cdot2048}=\frac{101}{15}\approx6{,}73.

Код каждого пикселя содержит целое число бит, поэтому подходит глубина 6, а не 7. Шесть бит различают 2^6=64 цвета. Для проверки: при 6 битах файл занимает 360 Кбайт, при 7 битах — 420 Кбайт. Ответ: 64. Число 6 здесь промежуточное: вопрос относится к цветам.

Звук: измерения, каналы и время

Цифровая запись хранит последовательность измерений звукового сигнала. Частота дискретизации f — число измерений в секунду в одном канале; глубина кодирования b — число бит на одно измерение. Пусть c — число каналов, а t — длительность записи в секундах. Тогда без сжатия и заголовка V=fbtc бит: сначала считаются измерения, затем биты во всех каналах. Для моно c=1, для стерео c=2, для квадро c=4.

В EGE-07-0001 ↗ стереозапись длится 2 минуты 20 секунд, то есть t=140 секунд. Частота равна 28 000 Гц, глубина — 8 бит. Объём в Кбайт:

\frac{28\,000\cdot8\cdot140\cdot2}{8\cdot1024}=7656{,}25.

Требуется наименьшее целое количество Кбайт, достаточное для хранения. 7656 Кбайт не хватит, поэтому ответ: 7657. Это округление вверх, хотя число снимков в предыдущем примере округлялось вниз.

Время записи и время передачи — разные величины. В EGE-07-0017 ↗ запись длится 120 секунд, имеет два канала, частоту 56 000 Гц и глубину 16 бит. Её объём равен 56\,000\cdot16\cdot120\cdot2=215\,040\,000 бит. При скорости 32 000 бит/с передача займёт T=V/v=6720 секунд. Медленный канал передаёт запись дольше, чем она звучит.

Обратная задача решается той же связью. В EGE-07-0132 ↗ известны 792 Мбайт, четыре канала, 96 кГц и 24 бита. Здесь 96\ \text{кГц}=96\,000\ \text{Гц}. Длительность в минутах равна 792\cdot1024^2\cdot8/(4\cdot96\,000\cdot24\cdot60)\approx12{,}015. Условие просит ближайшее целое число, поэтому ответ — 12.

Сжатие: от какого объёма взят процент

Объём до сжатия обозначается V_0, после сжатия — V_s. Формулировка определяет, какая величина принята за 100%.

• В EGE-07-0021 ↗ оригинал больше сжатого файла на 25%. Значит, V_0=1{,}25V_s. При лимите 80 Кбайт после сжатия исходные данные занимают не более 100 Кбайт. Для 480\times768 пикселей получается b\leq100\cdot8192/(480\cdot768)=20/9. Максимальная целая глубина — 2 бита, палитра — 4 цвета.
• В EGE-07-0026 ↗ объём уменьшается на 35% при сжатии. Остаётся 65% оригинала: V_s=0{,}65V_0, поэтому V_0=V_s/0{,}65. При 90 Кбайт и 192\times960 пикселях допустимо b\leq90\cdot8192/(0{,}65\cdot192\cdot960)=80/13. Это не более 6 целых бит, то есть 64 цвета.

Умножение на 1{,}35 во втором случае подменило бы базу процента: прибавлялись бы 35% сжатого файла вместо восстановления 35% исходного.

Повторное кодирование и экономия

При повторной записи того же звука его длительность сохраняется. Изменение объёма определяется частотой, глубиной кодирования и числом каналов. В задаче о повторной записи и передаче звука ↗ исходный файл передавался 18 секунд. При новой записи стерео заменяется моно, а глубина и частота удваиваются. Число каналов уменьшается вдвое, поэтому объём меняется в \tfrac12\cdot2\cdot2=2 раза.

При прежней скорости удвоенный объём передавался бы вдвое дольше. Но новый канал ещё и в 5 раз медленнее, что увеличивает время передачи в 5 раз. Оба множителя относятся к исходным 18 секундам: 18\cdot2\cdot5=180 секунд.

Если меняются изображения и требуется экономия, нужны оба объёма. В EGE-07-0002 ↗ исходный снимок имеет размер 3840\times2160 и палитру 2^{22} цветов; новый — 2560\times1440 при глубине 20 бит. Экономия на 140 снимках в Кбайт равна:

\frac{(3840\cdot2160\cdot22-2560\cdot1440\cdot20)\cdot140}{8192}=1\,858\,500.

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

Возможные ловушки

• Байты смешаны с битами. В EGE-07-0028 ↗ лимит дан в Кбайт, а глубина — в битах. Пропуск множителя 8 уменьшает допустимую глубину в восемь раз и меняет палитру ещё сильнее, поскольку число цветов равно степени двойки.
• Одно правило округления для любого вопроса. В EGE-07-0001 ↗ усечение оставляет недостаточно памяти; в EGE-07-0010 ↗ округление вверх добавляет снимок, который не успеет передаться. Требование «ближайшее целое» в EGE-07-0132 ↗ задаёт третье правило. Округление выполняется в конце, в единицах ответа.
• Стерео принято за один канал. В EGE-07-0017 ↗ частота относится к каждому из двух каналов. Потеря множителя 2 вдвое уменьшает и объём, и время передачи.
• Оригинал восстановлен прибавлением процента. В EGE-07-0026 ↗ после сжатия остаётся доля оригинала. Деление на эту долю восстанавливает исходный объём; прибавление того же процента к меньшему файлу даёт другую величину.
• Рост скорости увеличивает время. В EGE-07-0061 ↗ новый канал медленнее, поэтому время растёт. Вообще время пропорционально объёму и обратно пропорционально скорости: ускорение канала сокращает передачу при том же объёме.