Пиксель. История одной точки

Рисунок 2.5 – аналоговый, а рисунок 2.6 – цифровой. Вертикальные линии на втором называются отсчетами для аналоговой кривой – или выборкой. В случае доски с гвоздями для двумерной поверхности гвозди будут отсчетами соответствующей аналоговой поверхности. Замечательная теорема Котельникова гласит, что нам не нужна сама гладкая кривая для представления звука или сама гладкая поверхность для представления визуальной сцены. Нам нужны только отсчеты. Другими словами, на аналоговую бесконечность точек между отмеченными на первом рисунке черными зарубками можно не обращать внимания! Кажется, он говорит, что ничто может представлять нечто. Как такое возможно? Ответ кроется, конечно же, в слове «кажется».

Вы можете вообразить, что, если просто сделать очень-очень много отсчетов и разместить их достаточно близко друг к другу, они станут аналоговой звуковой кривой. У многих людей есть такое же интуитивное представление, что пиксели – какими бы они ни были, – расположенные достаточно близко друг к другу, станут соответствующей визуальной сценой. Но такое предположение ошибочно. Вы не можете достичь достаточно близкого расположения. Невозможно заставить цифровую бесконечность достичь плотности аналоговой бесконечности. Нельзя сосчитать неисчислимое. Но Котельников, кажется, говорит, что можно. Тогда как же это сделать?

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

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

Перейдем к сути замечательной идеи Котельникова: если вы делаете отсчеты некоей гладкой аналоговой кривой с удвоенной частотой самой высокой частоты волн Фурье из составляющей ее суммы, то вы всегда сможете точно восстановить обратно эту гладкую кривую, используя только сделанную выборку. Отсчеты дискретные, разрозненные, отделенные друг от друга – определенно не гладкие. Это первая часть его идеи, великая теорема отсчетов – та часть, в которой утверждается, что аналоговую гладкость можно заменить цифровой несвязностью. Во второй части рассказывается, как выполнить фактическое восстановление исходного аналогового сигнала из цифровых отсчетов.

Рис. 2.6

Котельников стоит на плечах гиганта Фурье. Частоты Фурье отражают скорость изменения аналогового изображения в поле зрения. Затем гениальная идея Котельникова подсказывает нам, как представить волны Фурье в цифровом виде. Удивительно, но для каждого цикла самой быстро меняющейся волны достаточно всего двух отсчетов. Нетрудно догадаться, почему именно двух: одно измерение для гребня волны, а второе – для впадины.

Пиксель

В цифровом мире у отсчетов Котельникова для визуального поля есть устоявшееся название. Мы называем их пикселями. Вот оно! Это и есть определение пикселя. Оно тесно связано как с Фурье, так и с Котельниковым. Отсчеты Котельникова – вот что делает Цифровой Свет возможным.

Пиксели – это не маленькие квадратики! Некоторых это изрядно удивит, потому что очень часто пиксели описывают именно так – настолько часто, что люди повсеместно отождествляют пиксели с плотно расположенными маленькими цветными квадратиками. Это, возможно, самое распространенное заблуждение зарождающейся цифровой эпохи, а слово «пикселизация» его только укрепило.

Рис. 2.7

На самом деле у пикселей нет формы. Это просто отсчеты, взятые в узлах регулярной сетки, – вспомните наш пример с гвоздями. Они представляют собой абстрактные точки нулевого размера, не имеющие длины, ширины и толщины. Они невидимы и бесцветны. Это просто число, кодирующее оттенок серого, или три числа, обозначающие три интенсивности цвета. Как мы увидим, именно восстановление аналогового из цифрового с использованием идеи Котельникова придает пикселям форму.

Самому слову «пиксель» пришлось побороться за право на существование. Пиксели поначалу назывались по-разному: например, точки, массивы точек, растровые элементы, точки изображения и элементы изображения. Последний вариант победил, но затем разгорелась битва за более короткий термин. В течение многих лет IBM и AT&T пытались сокращать «элемент изображения» (picture element) до pel. Но энергичное молодое сообщество середины 1960-х, занимавшееся обработкой изображений, одержало победу над усилиями гигантских корпораций, настояв на сокращении pixel. На самом деле для молодых гиков, работающих с компьютерной графикой, вроде меня, достигших совершеннолетия в те бурные годы, было делом чести обеспечить победу контркультуры «пикселя», свергнув «пел» Голубого Гиганта и Матушки Белл. Ричард Лайон, тщательно изучив историю словоупотребления, нашел самое раннее упоминание термина[2 - Голубой Гигант (Big Blue) – прозвище компании IBM. Матушка Белл (Ma Bell) – прозвище компании Bell Labs. – Прим. ред.]pixel в документе 1965 года за авторством Фреда Биллингсли из Лаборатории обработки изображений, входившей в Лабораторию реактивного движения Калифорнийского технологического института (рис. 2.8). А самое раннее публичное использование pel зарегистрировано в статье профессора Массачусетского технологического института Уильяма Шрайбера в 1967 году.

В 1970-х годах было выдано много патентов, содержащих как пиксель, так и пел, причем в количественном отношении преобладали патенты с использованием первого термина. Неудивительно, что большинство патентов той эпохи с термином «пел» принадлежали IBM или Bell Labs компании AT&T. Если бы Найквист или Шеннон использовали некий термин для обозначения пикселя – чего они не делали, – их выбор наверняка пал бы на pel, термин, принадлежащий Матушке Белл.

Пиксель напрямую связан с теоремой отсчетов; выборки и пиксели объединены еще с рождения. Как ни странно, в теории цифрового звука нет специального слова, такого как «пиксель», для обозначения элемента выборки, или «семпла», хотя цифровой звук существует благодаря все тому же трюку с использованием отсчетов Котельникова. К сожалению, применительно к аудио слово «семплирование» имеет другое значение. В хип-хопе, например, так называют заимствование фрагментов чужой музыки длительностью в несколько секунд, их соединение или смешение. Чтобы не возникало путаницы, для обозначения звукового отсчета я буду использовать специальное слово «соксель» (soxel), сокращение от sonic element (звуковой элемент).

Игры в имена

Весьма проблематично, что приоритет в открытии теоремы отсчетов в сегодняшних Соединенных Штатах приписывается Шеннону. Если оставить в стороне весь остальной мир, легко понять почему. Клод Шеннон – громкое имя в Америке. Теорему отсчетов он сформулировал в статье 1948 года «Математическая теория связи». В очень знаменитой классической статье 1949 года «Связь при наличии шума» он сформулировал и доказал теорему выборки в том виде, который сейчас используется во всем цифровом мире, а особенно применительно к Цифровому Свету. Его авторитет рос по мере того, как он получал различные престижные награды – например, национальную научную медаль США и медаль почета Института инженеров электротехники и электроники (IEEE). Он стал первым лауреатом премии, присуждаемой Группой теории информации IEEE и впоследствии названной в его честь. Он получил широкую известность на международном уровне и стал первым лауреатом премии Киото в области математики – награды не менее престижной, чем Нобелевская премия.

Рис. 2.8

Клод Элвуд Шеннон родился 30 апреля 1916 года в Петоски, штат Мичиган. Вырос он в соседнем городе Гейлорд, где, если верить слухам, из проволочной изгороди соорудил телеграфную линию между своим домом и домом друга. Еще он любил жонглировать, придумывать секретные коды и играть в шахматы. Он прослыл жизнерадостным гением со множеством интересов, выходивших далеко за пределы профессиональной деятельности. Он разъезжал на одноколесном велосипеде по залам Массачусетского технологического института, где получил докторскую степень по математике, а позднее и по коридорам Bell Labs, где разработал теорию информации. Еще он изобрел удивительную машину в коробке: если повернуть выключатель на боковой панели, из-под крышки появлялась механическая рука, которая возвращала его в исходное положение.[3 - Это устройство описано в книге фантаста Артура Кларка «Голос через океан». Писатель неоднократно бывал в гостях у Шеннона и искренне восхищался изобретением. См.: Кларк А. Голос через океан. М.: Связь, 1964. С. 172. – Прим. пер.]

Шеннон преуспел и в области криптографии. В 1945 году он написал засекреченный доклад «Математическая теория криптографии». Во время Второй мировой войны он проанализировал работу системы X-system, которая использовалась для безопасной голосовой радиосвязи между Франклином Д. Рузвельтом и Уинстоном Черчиллем. Шеннон математически доказал, что такую схему шифрования невозможно взломать. Шеннон также играл ключевую роль в изучении передачи данных в условиях помех, как, собственно, и называлась его статья 1949 года. Он показал, как отправлять цифровые сообщения по всей Солнечной системе, чтобы избежать искажений от воздействия космического шума. Именно благодаря идее Шеннона на вашем ноутбуке можно посмотреть видео, переданное с марсохода Curiosity. На фоне столь впечатляющего списка заслуг кажется вполне естественным, что имя Шеннона связано с теоремой отсчетов. Однако сама идея ему не принадлежала, о чем Шеннон не раз упоминал[4 - После снятия грифа секретности доклад был переработан в статью, опубликованную в 1949 году под названием «Теория связи в секретных системах» в Bell System Technical Journal. – Прим. пер.].

«Это общеизвестный в теории связи факт, – писал он в статье 1949 года. – Теорема была первоначально дана в других формах математиками, но, несмотря на ее очевидную важность, не приводилась в литературе по теории связи».

Но «в литературе по теории связи» теорема выборки приводилась – в нужной форме и с полным доказательством – задолго до публикации статьи Шеннона. Котельников сделал это еще в 1933 году, более чем на десять лет раньше. Почему Шеннон не упомянул его? Возможно, дело в том, что статья Котельникова вышла в малотиражном издании материалов российской конференции и Шеннон просто не знал о ней. Но, как мы увидим дальше, реальную причину определить почти невозможно. Он мог узнать о теореме Котельникова в контексте секретных разработок, результатами которых СССР и Соединенные Штаты обменивались во время Второй мировой войны. Но последующие ожесточенные разногласия между сверхдержавами, скорее всего, помешали бы Шеннону обнародовать такое знание или получить к нему доступ.

Шеннон и Котельников (рис. 2.9) были лидерами в сфере цифровой связи в своих странах, особенно если дело касалось преодоления помех или шифрования. Оба удостоились высших государственных и научных наград. И оба сформулировали и доказали теорему выборки в том виде, в каком она используется сегодня.

Нельзя не задаться вопросом, оказал ли один влияние на другого. Любопытно, что Шеннон, младший из них, с отставанием на несколько лет повторял интеллектуальные достижения Котельникова, но я не нашел никаких доказательств, что Шеннон знал о засекреченных работах Котельникова. В любом случае не удивительно, что русские называют эту великую идею теоремой отсчетов Котельникова. А разве американцы не должны?

Разбрасывай и складывай

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

Вот как аналоговое восстанавливается из цифрового. Распределите каждый пиксель в пространстве с помощью «разбрасывателя», ключевой формы этой главы. Сложите результаты. Вот и все. Теорема отсчетов утверждает, что этот процесс «разбрасывания» и сложения полученных результатов точно воспроизводит недостающие бесконечности между пикселями! Как и в случае с другими великими математическими теоремами, такие выводы вовсе не очевидны. Мы должны верить математике.

Здесь нам снова поможет пример с волной, но для простоты мы возьмем только два центральных сокселя (рис. 2.10). (Чуть позже от них мы перейдем к пикселям.) Напомню, что соксель – это отсчет для кривой, изображающей аналоговый звук, а ее высота над нулевой линией обозначает его громкость. Таким образом, высота сокселя представляет собой громкость звуковой волны только в той точке, где сделан этот отсчет. Соксель справа будет менее громким, чем тот, что слева.

Рис. 2.9

Сначала мы разберемся с левым сокселем при помощи «разбрасывателя», изображенного на рисунке 2.1. Напомню, что его колебания той же частоты, что и у волны Фурье с самой высокой частотой исходного фрагмента. Его максимальная амплитуда на центральном выступе соответствует максимальной громкости. Для выполнения операции «разбрасывания» заменим левый соксель копией разбрасывателя (рис. 2.11). Я люблю говорить, что это «разбрасывание» превращает соксель из отсутствия формы (ничего) в показанную на рисунке форму (нечто). Его самая высокая точка – вершина центрального горба – имеет ту же громкость, что и соксель, который он заменяет. Два сокселя показаны пунктиром. В частности, из рисунка видно, что высота разбрасывателя – его максимальная громкость – соответствует высоте левого сокселя. В нашем примере она составляет 80 % от полной громкости. Представьте, что у вас есть переключатель для ее регулирования.

Теперь поместите еще одну копию разбрасывателя над правым сокселем (рис. 2.12) и поворачивайте переключатель, пока его максимальная громкость не совпадет с громкостью этого сокселя, в нашем случае 50 % от полной громкости, – таким образом будет «разбросан» второй соксель.

А вот результат (рис. 2.13) сложения двух «разбросанных» сокселей. В каждой горизонтальной позиции возьмите высоты расположенных там сокселей (светло-серые), измеренные от линии нулевой громкости, и сложите их вместе, чтобы получить точку на жирной кривой.

Рис. 2.10

Я до сих пор обходил стороной физическую реальность. Описанный в этой главе разбрасыватель не существует в реальном мире. Он бесконечно широк. Его колебания уходят влево и вправо до бесконечности. Очевидно, в действительности такое невозможно, поэтому реальные разбрасыватели лишь приближенно соответствуют идеальному.

Особенно часто используется кубический разбрасыватель, отличающийся практичностью и удивительной точностью (рис. 2.14). Обратите внимание, насколько он похож на среднюю часть идеального разбрасывателя, включая наличие двух отрицательных лепестков (ниже линии нулевой громкости). Кубический разбрасыватель равен нулю везде, кроме двух отсчетов слева и двух справа от центрального отсчета – того, который «разбрасывается» им самим. Другими словами, он имеет конечную ширину, поэтому может существовать в реальном мире.

Рис. 2.11

Рис. 2.12

Рис. 2.13

До сих пор я описывал одномерное разбрасывание. Амплитуда звуковых волн изменяется только в одном измерении (во времени), поэтому приведенные выше иллюстрации подходят для сокселей, но не для пикселей. Разбрасыватель для пикселей должен работать в двух измерениях, поскольку изображения простираются (в пространстве) в двух измерениях – горизонтальном и вертикальном. Разбрасыватель пикселей должен «разбросать» каждый гвоздь (пиксель) из нашей воображаемой доски с гвоздями так, чтобы каждый «разбросанный» пиксель внес свой вклад в двумерную поверхность, которую мы увидим. Можете считать предыдущие иллюстрации точными чертежами поперечного сечения разбрасывателя пикселей в горизонтальном измерении, а в вертикальном измерении оно будет точно таким же. Но можно сделать нагляднее.