Пиксель. История одной точки - Элви Рэй Смит

на графическом планшете при демонстрации Рави Шанкару. Это плавная, изящно изогнутая геометрическая кривая, проходящая через точки. Это догадка, что находится между ними, — при условии, что там находится нечто интересное и даже красивое. В противном случае соединение точек становится тривиальной задачей: просто проведите между ними отрезки прямых линий. Зигзагообразный результат не слишком приятен глазу.

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

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

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

Подход Уиттекера заключался в интерполяции. Свою точку зрения он отразил в книге, написанной в соавторстве с Джорджем Робинсоном:

Теорию интерполяции… в ее самом элементарном аспекте можно описать как науку о «чтении между строк математической таблицы».

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

Интерполировать означает поместить что-то между. Хочу подчеркнуть: это что-то специально создается, чтобы оказаться между. Если нам повезет, полученные данные действительно будут соответствовать реальному миру — например, температуре в 15:15 в кампусе Беркли. Показатели будут иметь такое же значение, как будто мы на самом деле провели измерения. Уиттекер мастерски владел интерполяцией или созданием данных между существующими данными.

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

Уиттекер придерживался противоположной точки зрения. Он начал с дискретных точек — отсчетов данных. Он стремился найти гладкую кривую, которая бы их соединила, и именно поэтому не пришел к обоснованию более сильной версии теоремы отсчетов, которую доказал Котельников (и — повторно — Клод Шеннон).

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

Интерполяционная теорема Уиттекера предлагает нам расширять каждую заданную точку с помощью расширителя — такого же, как идеальный разбрасыватель Котельникова. Затем результаты суммируются, чтобы получить интерполяцию, плавную кривую между точками данных. Такая кривая представляет собой сумму волн Фурье до самой высокой частоты, соответствующей используемому расширителю. Вспомните, что идеальный разбрасыватель колеблется так же часто, как и волна самой высокой частоты. Уиттекер начинает с дискретных данных, интерполирует гладкость между ними, затем находит нужные данные на кривой между исходными данными: от дискретного к гладкому и обратно к дискретному.

Несмотря на разные точки зрения, математически результаты Уиттекера и Котельникова эквивалентны. Просто один из них пошел от обратного. Так почему бы не отдать лавры за теорему отсчетов Уиттекеру? Причина заключается в том, что он не доказал более сложную форму теоремы Котельникова о дискретизации, так называемую полосовую вариацию, которая часто используется в современном мире. Мы использовали ее в главе о Тьюринге, когда описывали принцип работы вокодера, где звуковой сигнал, содержащий от 0 до 3000 циклов в секунду, разбивается на 10 полос шириной 300 циклов в секунду каждая (от 0 до 300, от 301 до 600 и так далее).

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

Сплайн для Рави Шанкара: выборка наоборот

На рисунке 6.3 изображены точки, полученные на планшете во время моей демонстрации технологии Рави Шанкару. Маленькая стрелка показывает направление движения стилуса. Планшет записал мой жест в виде значений координат через равные временные интервалы, так что, как вы можете заметить, я сначала рисовал быстро, затем замедлялся на поворотах и заканчивал снова быстро. Изображение справа — это то, что нам не нужно, соединение точек прямыми линиями. Это интерполяция тех же данных, но не очень приятная на вид — жесткая зигзагообразная «кривая». В старые недобрые времена люди думали, что компьютер на большее не способен. Они считали компьютеры грубыми и угловатыми — одним словом, механическими, — пока закон Мура не доказал обратное. В компьютерной графике линейная интерполяция — прямые линии между точками — не приветствуется.

Рис. 6.3

Мы научились делать намного лучше. Расположение каждой точки можно сопоставить с расстоянием до нее по вертикали от нижнего края планшета. Рисунок 6.4 демонстрирует график вертикального положения каждой точки. Это просто точки слева, расположенные по