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

2. Отсчеты Котельникова: нечто из ничего

Это – глухая, совершенно недостоверная, никем не подтвержденная легенда, которую нет-нет да и услышишь в лагерях: что где-то в этом же Архипелаге есть крохотные райские острова. Никто их не видел, никто там не был, а кто был – молчит, не высказывается. На тех островах, говорят, текут молочные реки в кисельных берегах, ниже как сметаной и яйцами там не кормят; там чистенько, говорят, всегда тепло, работа умственная и сто раз секретная. И вот на те-то райские острова (в арестантском просторечии – шарашки) я на полсрока и попал. Им-то я и обязан, что остался жив…

– Александр Солженицын. «Архипелаг ГУЛАГ»

Человек, который изобрел пиксель и начал цифровую революцию, был председателем Верховного Совета РСФСР. Не в одно и то же время, но все-таки это один и тот же человек. Звали его Владимир Котельников. В 2003 году, когда ему исполнилось 95 лет, другой Владимир – Путин – вручил ему в Кремле орден «За заслуги перед Отечеством» I степени. Ранее Котельников получил и множество советских наград, в том числе шесть орденов Ленина, две Сталинские премии, две звезды Героя Социалистического Труда. Он пережил Октябрьскую революцию 1917 года, а также все репрессии и войны, которые с тех пор составляют историю современной России. Он едва избежал ГУЛАГа – а точнее, тех самых «райских островов» внутри него, где трудился Солженицын, – поскольку находился под защитой влиятельной жены одного из самых кровавых приспешников Сталина. Он поделился с американцами информацией о первом советском искусственном спутнике Земли и составил карту Венеры с помощью цифровых изображений – пикселей, полученных из космоса.

Заслуги Котельникова, что вполне ожидаемо для вдохновителя Великой цифровой конвергенции, отмечены и в Америке: в 2000 году он награжден медалью Александра Грэма Белла. Тем не менее его имя мало кому известно в Штатах. За ним редко признают одно из величайших открытий ХХ века – теорему выборки, идею, лежащую в основе всего мира цифровых медиа. Лавры первооткрывателя обычно достаются Клоду Шеннону, известному американскому инженеру и математику, хотя Шеннон никогда на них не претендовал.

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

Великая идея Котельникова, напрямую ведущая к пикселю, вплетена в поразительно параллельные судьбы малоизвестного Котельникова и знаменитого Шеннона.

Разбрасыватель

Идея состоит в следующем: цифровое может достаточно точно представлять аналоговое. Дискретное, прерывистое и импульсное может точно представлять гладкое, непрерывное и плавно изогнутое. Прерывистая последовательность может точно представлять последовательную непрерывность. Возможно, сейчас вас это не удивляет, но я надеюсь все-таки удивить вас, потому что оказывается, что мы можем отбросить поразительное – фактически бесконечное – количество информации, практически ничего не теряя. Эта ключевая идея сделала возможным Цифровой Свет (а также цифровой звук). Эта фундаментальная истина лежала в основе Великой цифровой конвергенции и, следовательно, всего современного мира.

Подобно тому как волна – это форма, представляющая частоты Фурье, существует форма, представляющая отсчеты, или выборки, Котельникова (см. рис. 2.1). Вскоре мы увидим, что это тесно связано с «формой» пикселя. Математики называют это «каменной стеной» или sinc-фильтром, а инженеры – реконструкционным или восстанавливающим фильтром. Поскольку оба названия не вполне понятны, я буду называть эту прекрасную форму «разбрасывателем». Вскоре вы поймете почему.

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

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

Впервые я узнал об этой замечательной идее в начале 1960-х на электротехническом факультете. Нам рассказывали, что ее выдвинул Гарри Найквист, американский инженер и настоящий герой для нас, инженеров-электронщиков. Он работал в легендарной «Лаборатории Белла» (Bell Labs) в AT&T – мы все мечтали трудоустроиться туда. Но в конце 1960-х, когда я учился в Стэнфорде, информатика наконец-то стала отдельной дисциплиной и автором великой идеи начали называть Клода Шеннона, нашего нового героя во всем, что касалось цифровых технологий. Он первым использовал слово «бит» в печати. И он тоже работал там в качестве младшего коллеги Найквиста.

Но это американская версия событий, и здесь вступает в действие закон Стиглера: «Никакое научное открытие не было названо в честь первооткрывателя». (Сам Стиглер, кстати, считал, что этот закон открыт Робертом Мертоном.) Так что в России, безо всяких колебаний, лавры первооткрывателя всегда отдают Котельникову. В Японии эти заслуги приписывают Исао Сомея. В Англии – сэру Эдмунду Уиттекеру. В Германии – Герберту Раабе. Впрочем, если на то пошло, Найквист родился в Швеции. И только Шеннон – истинный американец, родившийся в Мичигане. Можно ли считать желание приписать ему лавры первооткрывателя проявлением нездорового патриотизма? Все вышеперечисленные сформулировали свои версии этой идеи раньше Шеннона, кроме Сомея – он опоздал на несколько месяцев. Получается, что чести дать свое имя теории – во всяком случае, в Соединенных Штатах – удостоился человек, сформулировавший ее практически последним.

Несмотря на всю путаницу с именованием, факты говорят сами за себя: великую идею – в том виде, в котором она используется в Цифровом Свете, – впервые четко, ясно и обстоятельно изложил и доказал Котельников в 1933 году. Нам на Западе трудно поверить, что такая фундаментальная идея появилась в худшие дни сталинской России. Во время холодной войны нас учили, что советская наука если не фальшивка, как биология Лысенко, то в лучшем случае основана на украденных идеях или раздута пропагандой. Придется смириться, что авторство Котельникова неоспоримо.

Рис. 2.1

Происхождение, работы и карьера

Владимир Александрович Котельников родился в 1908 году в Казани, старинном городе на Волге примерно в 500 милях к востоку от Москвы. Трудно представить ученого со столь же безупречной математической родословной. Его прапрапрадед Семен Котельников учился у Леонарда Эйлера, одного из величайших математиков всех времен. Часть математического аппарата, который использовал Фурье, – это прямое наследие Эйлера. В 1757 году Семен Котельников стал одним из первых академиков Санкт-Петербургской академии наук, основанной Петром Великим и ныне именуемой Российской академией наук.

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

Рис. 2.2

Рис. 2.3

Неудивительно, что отец Владимира, Александр Петрович Котельников, тоже окончил Казанский университет и тоже занимал пост декана физико-математического факультета. Но, что важно для нас, история Владимира Котельникова по-настоящему началась, когда Александр Петрович решил покинуть Казань и переехать с семьей в Киев, получив новую преподавательскую должность.

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

Следующими двумя стали Октябрьская революция 1917 года и последовавшая за ней Гражданская война между красными и белыми. Россия изменилась. Молодой Владимир тоже, но причиной тому были не войны. Посреди всего этого хаоса он впервые услышал радиопередачу.

«Как это устроено?» – спросил он отца.

«Ты этого пока не поймешь».

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

«Велик был и страшен год по Рождестве Христовом 1918, от начала же революции второй». Так начинается роман «Белая гвардия» Михаила Булгакова – повествование об ужасах, разрушениях и анархии, царивших в Киеве в годы Гражданской войны. Во второй раз Котельниковы выбрали неудачный момент, чтобы переехать туда. Им пришлось пережить весь описанный Булгаковым кошмар. Профессор варил мыло, а дети распускали занавески на нитки; денег не хватало, работы не было.

В 1924 году Александр Петрович перевез семью в Москву. Он получил профессорскую должность в Московском высшем техническом училище (МВТУ), старейшей высшей технической школе в России. МВТУ подверглось серьезным трансформациям в 1930 году, когда разделилось на пять самостоятельных учебных заведений. Одно из них – Московский энергетический институт (МЭИ) – стало одним из ведущих технических университетов мира. Можете считать его московским аналогом Массачусетского технологического института.

Владимир Котельников был одним из первых выпускников МЭИ. Сначала его туда не принимали из-за происхождения – он не был выходцем из рабоче-крестьянской среды, – но вскоре критерии изменились и ему удалось туда поступить. В 1931 году Котельников закончил МЭИ, получив диплом инженера-электрика по специальности «Радио». Он проработает в своей альма-матер следующие 75 лет.

Через некоторое время случился его annus mirabilis. В 1932 году аспирант Котельников самостоятельно, без всякой посторонней помощи, написал две статьи, каждой из которых было достаточно, чтобы открыть ему путь на инженерный олимп. Одна из них – «Теория нелинейных фильтров с делением частоты пополам» – не касается темы нашего исследования. Однако в другой содержалась интересующая нас великая идея – теорема отсчетов. Завершая обучение в аспирантуре, Котельников представил свои работы в ноябре ученому совету факультета, а в следующем году опубликовал под неприметным названием «О пропускной способности „эфира“ и проволоки в электросвязи».

Когда он представлял эту работу преподавателям МЭИ, один из них сказал: «Все вроде верно, но больше похоже на научную фантастику». Нечто из ничего. Тем не менее они одобрили статью, дав старт его академической карьере.

В 1933 году, продолжая преподавать в МЭИ, Котельников поступил на работу в НИИ связи Народного комиссариата связи (НИИС НКС). Связь на войне имеет первостепенное значение, поэтому неудивительно, что, захватив власть в октябре 1917 года, большевики в первый же день создали Народный комиссариат почт и телеграфов РСФСР, впоследствии преобразованный в НКС. Котельников, начав с должности инженера, со временем стал начальником собственной лаборатории связи, а впоследствии и целого института. Он всегда одной ногой стоял в академической башне из слоновой кости, а другой – в реальном мире политики и войн.

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

Цифровые и аналоговые бесконечности

Не будем стесняться слова бесконечность. На самом деле существует много разных видов бесконечности, но нам нужны только две: цифровая и аналоговая. Знакомая диаграмма (рис. 2.4) с секундной стрелкой часов поможет прояснить разницу.

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

Рис. 2.4

Второй вид бесконечности – аналоговая бесконечность – не так прост. Рассмотрим две последовательные точки на волне. Сколько точек находится между этими точками? Ответ: их так много, что даже не сосчитать. Аналоговая бесконечность больше цифровой бесконечности, как бы странно это ни звучало. Математик Георг Кантор доказал, что это именно так, и вот как он это сделал.

Между любыми двумя точками на волне всегда есть еще одна точка. Теперь подумайте об этой средней точке и левой из двух исходных. Есть ли между ними еще одна точка? Конечно есть. Теперь повторите рассуждение для этой точки и левой из двух исходных. И так до бесконечности. Вы никогда не разделите отрезок между точками на такие мелкие части, чтобы дальнейшее деление стало невозможным. Другими словами, вы никогда не доберетесь до места, откуда получится сосчитать все точки. Математики предпочитают называть это неисчисляемой бесконечностью, но я буду придерживаться термина «аналоговая бесконечность». Оба понятия уместны: у непрерывных вещей аналоговое, или бесчисленное, множество частей, а количество частей у дискретных вещей исчисляется цифровой, или счетной, бесконечностью. По большому счету цифровое уступает аналоговому, даже если вы использовали очень много точек для представления гладкой кривой. Но великая идея Котельникова, похоже, заключается в том, что цифровое – вот так сюрприз! – эквивалентно аналоговому. При переходе на цифровые технологии ничего не теряется. Дискретный цифровой объект может быть точным представлением гладкого аналогового объекта.

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

Рис. 2.5

Рисунок 2.6 – это то, что вы получите, если удалите все точки на гладкой кривой, кроме тех, что отмечены черными зарубками. Между ними у нас есть только прямая линия нулевой громкости или нулевого уровня яркости. Нетрудно представить, как будет выглядеть двумерная версия. Представьте доску с гвоздями, забитыми на равных расстояниях по горизонтали и вертикали. Их высота варьируется в зависимости от яркости соответствующей гладкой поверхности – визуальной сцены. Везде, кроме мест, где расположены гвозди, высота поверхности будет нулевой.

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

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

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

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

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

Рис. 2.6

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

Пиксель

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

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

Рис. 2.7

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

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

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

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