What We Need Around Here Is More Aliasing

Не странно ли, когда вы обращаетесь по какому-либо поводу, вы "вписываете в анкету" или "вычеркиваите из анкеты"? Если цыпленок "костистый", то что значит, что он "некостистый"? Если "горючим" называют то, что может вспыхнуть, тогда что такое "негорючее"? Если вы хотите что-то создать из листа металла, вы говорите "выштамповать". Если вы хотите что-то разрушить, вы тоже говорите "выштамповать". (И есть люди, которые хотят программировать компьютеры по-английски!)

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

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

Некоторые основополагающие знания (Some basic knowledge)

Чтобы разобраться с алиасингом, нужно начать с трех основополагающих математических понятий: преобразование Фурье, свертка, и теорема свертки. Разбираться будем на интуитивном уровне, пытаясь объяснять, в основном, с помощью картинок, а не уравнений. (Конечно, я люблю алгебру, но в этой области, алгебра может сделать вещи более мудреными, чем они есть на самом деле.) Дополнительную информацию вы можете найти в любой книге по обработке сигналов. Свои же предпочтения я отдаю книге "Transmission and Display of Pictorial Information" by D.E. Pearson, Halsted Press, John Wiley and Sons, New York, 1975.

Преобразование Фурье (Fourier transform)

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

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

Если входная картинка симметрична относительно начала координат, то мнимая часть ПФ равна нулю. В этом случае я буду изображать действительную часть ПФ, которая может иметь и отрицательные значения, а не только амплитуду.

Имейте в виду, что в Фурье-преобразовании нет новой информации; это просто иной взгляд на существующую функцию.

Свертка (Convolution)

На вход свертки подается две функции, и на выходе генерируется третья функция. Это в некотором роде скользящее взвешенное среднее первой функции, когда вторая функция задает веса. Опуская некоторые детали, можно сказать, что выходная функция формируется следующим образом: две функции перемножаются, а результат интегрируется. Изобразите полученное число на графике при x = 0. Продвиньте весовую функцию по x вправо. Умножьте и проинтегрируйте снова; изобразите это число на графике в x. Повторите эти операции для всех x, которые вы хотите отобразить на графике. Посмотрите на свертки на рис. 1, чтобы получить ощущение этого процесса.

Теорема свертки (The convolution theorem)

Свертки интересны еще и тем, как они взаимодействуют с преобразованиями Фурье. Предположим, вы умножаете две функции, чтобы получить новую функцию. Как будут выглядеть их ПФы? Оказывается, если вы произведете свертку ПФов первоначальных функций, вы получите ПФ третьей функции. Симметрично, если вы произведете свертку двух функций, чтобы получить третью, вы можете умножить их ПФы, чтобы получить ПФ третьей. Умножение в пространственной области становится сверткой в частотной области, и наоборот. Своего рода логарифмы, для которых умножение обычных чисел становится сложением в "логарифмической области". (Вы помните, что такое логарифмы, не так ли? Их-то и используют для того, чтобы сделать логарифмические линейки.)

Что при этом должно происходить с картинками? (What does this have to do with pictures?)

Давайте посмотрим на процесс изготовления изображения всего-то в одном измерении, вдоль единственной 16-пиксельной строки развертки. Я поведу рассказ так, чтобы провести параллель между пространственными функциями на рис. 1 и ПФами этих функций на рис. 2. Горизонтальная шкала ПФов задана в единицах период/пиксел. Квадратики посередине показывают, как комбинируются функции. Буква "Х" обозначает умножение, а буква "С" -- свертку.

Прежде всего, несколько слов о производстве картинок. Чтобы получить приблизительно непрерывный график, я произвел 8-кратную супердискретизацию (дискретизацию с повышенной частотой) функций, получив в итоге 128 отсчетов. Нельзя сказать, что это безумно много, поскольку хотелось представить импульсные функции, которые выглядят как высокие узкие треугольные импульсы. А также, при прямом ПФ 128-ми отсчетов амплитуды графики получаются в 8 раз больше. Поэтому все они промасштабированы с коэффициентом одна восьмая.

Но вернемся к картинкам и начнем с некоторой непрерывной интенсивности как функции от х - PICT. В этой функции есть резкие края, некоторые гладкие области, а также некоторые очень детализированные области. В ПФ этой функции есть игла на частоте 0 (она представляет среднюю интенсивность по всей строке) и хвосты с меньшими амплитудами для более высоких частот. Отметим всплеск в ПФ при 1.6 период / пиксел, который появился из-за детализированной области в исходном изображении.

Далее, измерим интенсивность в центре каждого пиксела. Само измерение сводится к умножению PICT на функцию COMB, в результате чего получается SPICT. Напомню, при умножении пространственных функций предполагается свертка частотных функций. ПФ от COMB оказывается еще одной гребенкой, зубцы которой отстоят один от другого на 1 период / пиксел. Итак, если судить о дискретизации в частотной области, то все что мы сделали - произвели свертку исходного ПФ с некой функцией-гребенкой. В сущности, это то же самое, что и суммирование полного набора копий ПФ, сдвинутых на 1 период / пиксел одна относительно другой. Поскольку исходная частотная функция растянута довольно далеко как в положительном, так и в отрицательном направлении, ее копии будут накладываться одна на другую. Именно поэтому и возникает "алиасинг". Высокие частоты сдвинутой копии накладываются на низкие частоты центральной копии.

И теперь мы попытаемся вывести строку развертки на экран ЭЛТ. Этот процесс называется "реконструкцией". Каждый пиксел передается через ЦАП в течение одного пиксельного интервала. Дискретная функция превращается из серии всплесков в ступенчатую функцию. Функционально это можно интерпретировать как свертку дискретного изображения с прямоугольным ядром, BOX, шириной в один пиксел. (Я изобразил ступеньки, центрированные относительно пиксела, чтобы проще было сравнивать с исходной картинкой. На самом деле они должны быть сдвинуты на полшага вправо.) В частотной области это интерпретируется как умножение дискретного ПФ на ПФ прямоугольного ядра (BOX). Таким образом, дополнительные копии спектров сужаются, но кое-что от них все же остается. Вспомните: все эти штучки выше .5 п/п и ниже -.5 п/п казались важной информацией, на самом же деле таковой не являются. Все это обычные математические дебри, оставшиеся в наследство от повторяющегося частотного процесса дискретизации. Частота .5 называется частотой Найквиста.

И, наконец, пятно на ЭЛТ само по себе имеет приблизительно Гауссово распределение интенсивности. При развертке по экрану происходит свертка электронного луча с выходом ЦАП. В частотной области это означает умножение гауссиана на соответствующий ПФ (уж так получается, еще на один гауссиан).

Сравнивая верхние и нижние графики, вы, наверное, заметили, какие искажения в картинках произошли как в пространственной, так и в частотной областях. Резкие края расплылись. Область с высокочастотными всплесками стала совершенно непохожей на себя. В ПФ высокие частоты исчезли, и появились какие-то дополнительные всплески на низкой частоте, вызванные алиасингом.

Обработка сигналов (The signal-processing solution)

В мире обработки сигналов нам скажут, что делать с алиасингом. Убейте его в зародыше, прежде чем он начнет размножаться. Проследите по рис. 3 (пространственная область) и по рис. 4 (частотная область).

Поскольку аккуратно представить высокие частоты невозможно, и поскольку они все равно к нам вернутся как призраки, замаскировавшись под низкие частоты, избавляться от них следует еще до дискретизации. Понятно, как это можно сделать в частотной области. Просто умножить ПФ картинки на нуль для всех частот за пределами .5 периодов на пиксел. Как это выразится в пространственной области? Проведите свертку исходной картинки с обратным ПФ прямоугольной функции, т.е. с функцией (sin x) / x. Что интересно, в наших представлениях эта конкретная функция всегда связывалась со шляпой. Результатом будет размытое изображение, в котором нет частот выше, чем .5 период / пиксел.

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

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

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

Так … просто. Проблема решена. Можно "снимать шинель, идти домой". Или еще нельзя?

Так что же в этой картинке плохо? (What's wrong with this picture?)

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