высококачественное сглаживание

Формула изобретения

1. Способ визуализации изображения, содержащий этапы, на которых:

получают фактический образ для контура, подлежащего визуализации;

определяют приближенный образ для одного или более прямолинейных отрезков, которые аппроксимируют контур, подлежащий визуализации;

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

визуализируют контур с использованием фильтрованного образа.

2. Способ по п.1, в котором фильтр является функцией h, причем

где [F(h)] означает Фурье-преобразование h, a означает зону, находящуюся в спектральной области, соответствующей интервалу взятия выборок дикретизированного образа в пространственной области.

3. Способ по п.2, в котором зона =[- , ]×[- , ] в спектральной области, где = /T, а Т означает интервал взятия выборок для дискретизированного образа в пространственной области.

4. Способ по п.2, в котором фильтр является круговым фильтром h(f, ), заданным уравнением

,

где r [0,R].

5. Способ по п.4, в котором радиус маски кругового фильтра равен 1 пикселю.

6. Способ по п.2, в котором фильтр является квадратным фильтром h(x), заданным уравнением

,

где(|х| R).

7. Способ по п.2, в котором размер маски квадратного фильтра равен 2 пикселя на 2 пикселя.

8. Способ по п.1, дополнительно содержащий этапы, на которых:

определяют, превышает ли ширина приближенного образа ширину маски фильтра; и

если ширина приближенного образа превышает ширину маски фильтра, то фильтруют края приближенного образа.

9. Способ по п.8, дополнительно содержащий следующий этап, на котором растрируют блоки приближенного образа, находящиеся за пределами ширины маски фильтра.

10. Способ по п.1, дополнительно содержащий следующие этапы, на которых:

определяют, пересекаются ли один или более прямолинейных отрезков внутри маски фильтра; и

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

11. Средство для визуализации изображения, содержащее:

хранилище исходных образов, которое хранит исходные образы;

модуль определения прямолинейных отрезков, который определяет данные прямолинейных отрезков, аппроксимирующих контур исходного образа; и

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

12. Средство по п.11, дополнительно содержащее модуль растрирования, который растрирует блоки данных прямолинейных отрезков, находящихся за пределами ширины маски фильтра от края данных прямолинейных отрезков.

13. Средство по п.12, дополнительно содержащее буферный накопитель, который хранит растрированные блоки данных прямолинейных отрезков.

14. Средство по п.11, дополнительно содержащее буферный накопитель, который хранит фильтрованные образы.

15. Средство по п.11, дополнительно содержащее справочную таблицу интегралов, которая хранит значения свертки образа с фильтром.

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

визуализируют контур с использованием фильтрованного образа.

17. Способ по п.16, дополнительно содержащий этапы, на которых:

определяют, превышает ли ширина приближенного образа ширину маски фильтра; и

если ширина приближенного образа превышает ширину маски фильтра, то фильтруют края приближенного образа.

18. Способ по п.17, дополнительно содержащий этап, на котором растрируют блоки приближенного образа, находящиеся за пределами ширины маски фильтра.

19. Способ по п.16, дополнительно содержащий этапы, на которых:

определяют, пересекаются ли один или более прямолинейных отрезков внутри маски фильтра; и

если один или более прямолинейных отрезков пересекаются внутри маски фильтра, то

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

фильтруют по отдельности каждую из двух или более зон.

20. Способ визуализации изображения, содержащий этапы, на которых: получают образ;

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

21. Способ по п.20, в котором фильтр является функцией h, где

,

где [F(h)] означает Фурье-преобразование h, a означает зону, находящуюся в спектральной области, соответствующей интервалу взятия выборок дикретизированного образа в пространственной области.

22. Способ по п.21, в котором зона =[- , ]×[- , ] в спектральной области, где = /Т, а Т означает интервал взятия выборок для дискретизированного образа в пространственной области.

23. Способ по п.20, в котором фильтр является круговым фильтром h(r, ), заданным уравнением

,

где r [0,R].

24. Способ по п.23, в котором радиус маски кругового фильтра равен 1 пикселю.

25. Способ по п.20, в котором фильтр является квадратным фильтром h(x), заданным уравнением

,

где (|x| R).

26. Способ по п.25, в котором размер маски прямоугольного фильтра равен 2 пикселя на 2 пикселя.

Описание изобретения к патенту

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

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

Следовательно, гладкие линии, кривые или области, сформированные в компьютере, фактически нельзя отобразить или визуализировать так, как они сформированы. Вместо этого они должны быть дискретизированы в дискретных точках, соответствующих отдельным пикселям. Однако, если частота характерных признаков линии, кривой или области выше частоты дискретизации линии, кривой или области с целью формирования пикселей, то дискретизированные образы (данные изображения) не будут точно отображать исходные сформированные образы. Например, на фиг.1А и 1С показаны два разных контура 101 и 103, которые могут быть сформированы в компьютере. Как видно из данных фигур, характерные признаки контура 101 расположены чаще характерных признаков контура 103. Дискретизацию контуров 101 и 103 выполняют в дискретных точках 105 и в результате получают соответствующие дискретизированные контуры 107 и 109, представленные соответственно на фиг.1В и 1D.

Так как пространственная частота взятия выборок 105 контура 103 составляет менее половины пространственной частоты расположения характерных признаков контура 103, то характерные признаки дискретизированного контура 109 расположены с частотой, значительно отличающейся от пространственной частоты исходного контура 105. В результате дискретизированный контур 109 идентичен дискретизированному контуру 107, несмотря на очевидное существенное отличие исходного контура 101 от исходного контура 103. Чтобы точно осуществить дискретизацию линии, кривой или области, пространственная частота взятия выборок должна более чем вдвое превышать пространственную частоту характерных признаков дискретизируемой линии, кривой или области. Однако частота взятия ограничена числом доступных пикселей (или "разрешением") соответствующего отображающего устройства.

Упомянутая проблема ступенчатой формы контуров изображений графически показана на фиг.2A и 2B. Как видно из фиг.2A, компьютер может сформировать прямую линию 201 с заданной шириной и заданным направлением или наклоном. Сформированная прямая линия 201 будет рассчитана так, что ей соответствуют конкретные пиксели 203 дисплея 205. Как видно из фиг.2B, если активировать каждый пиксель 203а, соответствующий прямой линии 201, то линия 207, отображаемая дисплеем, будет намного толще, чем сформированная прямая линия 201. Более того, визуализированная линия 207 будет представляться слишком ступенчатой с точки зрения наблюдателя, совершенно не такой, как гладкая сформированная прямая линия 201.

Для решения упомянутой проблемы разработаны различные способы сглаживания, которые должны контролировать вид пикселей, соответствующих линии, кривой или области, чтобы края линии, кривой или области представлялись менее резкими для наблюдателя. Например, как показано на фиг.3, способ сглаживания мог бы обеспечивать представление некоторых пикселей 203, соответствующих прямой линии 201, более светлым оттенком. В соответствии с некоторыми способами сглаживания цвет или интенсивность пикселя (т.е. значение пикселя) присваивают в зависимости от степени совмещения пикселя со сформированной линией, кривой или областью. Более того, в соответствии с некоторыми из упомянутых способов сглаживания соответствующий пиксель, возможно, даже не будет активирован, если степень совмещения данного пикселя со сформированной линией, кривой или областью не достаточна для активации. Разработано много различных способов определения значения, присваиваемого пикселю в зависимости от его совмещения со сформированной линией, кривой или областью. В соответствии с некоторыми способами значение пикселя определяют путем деления на несколько субпикселей, а затем определяют, сколько субпикселей пересекаются сформированной линией, кривой или областью. Например, пикселю, в котором сформированная линия, кривая или область пересекает только три субпикселя, может быть присвоено меньшее значение, чем пикселю, в котором сформированная линия, кривая или область пересекает семь субпикселей. В соответствии с некоторыми способами сглаживания каждому субпикселю дополнительно присваивают весовой коэффициент, чтобы субпиксели, расположенные ближе к центру пикселя, сильнее влияли на значение, присваиваемое пикселю, чем субпиксели, расположенные дальше от центра пикселя.

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

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

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

Кроме разных функций фильтрации, разные способы сглаживания могут различаться применяемыми масками фильтрации. Например, некоторые способы сглаживания могут предусматривать применение квадратной маски фильтрации, покрывающей один или несколько пикселей. Другие способы сглаживания могут предусматривать попеременное применение круговой маски фильтрации с диаметром, равным одному, двум, трем, четырем или более значениям ширины пикселя. На фиг.3 показана область 301, которую визуализирует группа пикселей 303 с центром каждого пикселя в точке 303А. Данная фигура показывает также круговую свертку или маску 305 фильтрации с диаметром, равным двукратной ширине пикселя 303. Как видно из данной фигуры, если маску 305 располагают по центру пикселя, то она будет достигать центра каждого непосредственно примыкающего пикселя.

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

Краткое изложение сущности изобретения

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

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

Перечень фигур чертежей

Фиг.1A и 1C представляют контуры с разными пространственными частотами характерных признаков.

Фиг.1B и 1D демонстрируют контуры, полученные посредством дискретизации контуров, показанных соответственно на фиг.1A и 1C.

Фиг.2A представляет вычисленную линию, наложенную на массив пикселей.

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

Фиг.3 демонстрирует круговую маску фильтрации для предфильтрации линии, кривой или области с помощью способа сглаживания.

Фиг.4 демонстрирует вычислительное устройство для реализации способа сглаживания в соответствии с различными вариантами осуществления настоящего изобретения.

Фиг.5 демонстрирует систему сглаживания для реализации способа сглаживания в соответствии с различными вариантами осуществления настоящего изобретения.

Фиг.6A и 6B демонстрируют этапы реализации способа сглаживания в соответствии с различными вариантами осуществления настоящего изобретения.

Фиг.7 демонстрирует пример контура, разделенного на прямолинейные отрезки по способу сглаживания в соответствии с различными вариантами осуществления настоящего изобретения.

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

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

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

Фиг.12 демонстрирует сечения круговых полиномиальных фильтров по варианту осуществления настоящего изобретения для трех разных коэффициентов фильтрации M.

Фиг.13A-13D демонстрируют различные изображения, визуализируемые с помощью способа сглаживания в соответствии с одним вариантом осуществления настоящего изобретения.

Подробное описание изобретения

Введение

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

Операционная среда

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

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

Поскольку различные варианты осуществления изобретения можно реализовать с помощью программируемых вычислительных устройств, запрограммированных соответствующим программным обеспечением, то для более понятного изложения изобретения, возможно, полезно дать краткое описание компонентов и принципа действия типичного программируемого вычислительного устройства (далее называемого просто компьютером), в котором можно реализовать различные варианты осуществления изобретения. На фиг.4 приведен пример вычислительного устройства 401, обеспечивающего подходящую операционную среду, в которой можно реализовать различные варианты осуществления изобретения. Данная операционная среда является всего лишь примером подходящей операционной среды и не может подразумевать никаких ограничений в отношении объема применения и функциональных возможностей изобретения. Другими общеизвестными вычислительными системами, средами и/или конфигурациями, которые можно применить с настоящим изобретением, являются, без ограничения, персональные компьютеры, компьютеры-серверы, карманные и портативные компьютеры, микропроцессорные системы, системы на базе микропроцессоров, программируемая бытовая электронная аппаратура, сети персональных компьютеров, миникомпьютеры, универсальные компьютеры, распределенные вычислительные среды, которые содержат любые из вышеупомянутых систем или устройств, и т.п.

Вычислительное устройство 401 обычно содержит, по меньшей мере, какой-либо тип машиночитаемого носителя данных. Машиночитаемым носителем данных может быть любой имеющийся носитель данных, к которому вычислительное устройство 401 может осуществить доступ. Например, без каких-либо ограничений, машиночитаемый носитель может содержать компьютерное запоминающее устройство и среду передачи данных. Компьютерное запоминающее устройство содержит энергозависимые и энергонезависимые, съемные и несъемные носители, выполненные любым способом или по любой технологии хранения информации типа машиночитаемых команд, структур данных, программных модулей или других данных. Компьютерное запоминающее устройство содержит, без ограничений, оперативные запоминающие устройства (ОЗУ, RAM), постоянные запоминающие устройства (ПЗУ, ROM), электрически стираемые программируемые постоянные запоминающие устройства (ЭСППЗУ, EEPROM), флэш-память или запоминающие устройства, выполненные по другой технологии, ПЗУ на компакт-дисках (диски CD-ROM), цифровые универсальные диски (диски DVD) или другие оптические носители, магнитные кассеты, магнитные пленки, накопители на магнитных дисках или другие магнитные запоминающие устройства, перфорированные носители, голографическое запоминающее устройство или любое другое запоминающее устройство, которое можно использовать для хранения необходимой информации и к которому вычислительное устройство 401 может осуществлять доступ.

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

Как видно из фиг.4, вычислительное устройство 401 в базовой конфигурации обычно содержит процессорное устройство 403 и системную память 405. В зависимости от точной конфигурации и типа вычислительного устройства 401 системная память 405 может содержать энергозависимую память 407 (например, ОЗУ), энергонезависимую память 409 (например, ПЗУ, флэш-память и т.д.) или некоторую комбинацию двух упомянутых типов памяти. Кроме того, вычислительное устройство 401 может содержать запоминающие устройства (ЗУ) большого объема, например съемное ЗУ 411, несъемное ЗУ 413 или некоторую комбинацию двух данных типов ЗУ. ЗУ большого объема могут быть любым устройством, которое может извлекать сохраненную информацию, например, магнитным или оптическим дисками или лентами, перфорированными носителями или голографическим запоминающим устройством. Специалистам в данной области техники очевидно, что системная память 405 и ЗУ 411 и 413 большого объема приведены как примеры компьютерных запоминающих устройств.

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

Средства сглаживания

Фиг.5 демонстрирует средство 501 сглаживания для реализации способа сглаживания в соответствии с различными вариантами осуществления изобретения. Средство 501 сглаживания содержит хранилище 503 исходных образов, модуль 505 растрирования, буферный накопитель 507 и модуль 509 вычисления прямолинейных отрезков. Как следует из нижеприведенного описания, хранилище 503 исходных образов содержит исходные образы, подлежащие визуализации с использованием способа сглаживания в соответствии с данным вариантом осуществления изобретения. Исходные образы можно хранить в любой подходящей форме, например в форме, по меньшей мере, одного математического уравнения, описывающего подлежащую визуализации область, кривую или линию. Например, если способ сглаживания используют для визуализации прямой линии, то исходным образом может быть уравнение у=mx+с, где m обозначает наклон прямой, а с обозначает смещение прямой.

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

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

Следовательно, если область представляет собой сплошную черную площадку, а черный пиксель имеет значение, обозначаемое "1", то пикселям с центрами внутри этой области будет присвоено значение "1", а пикселям с центрами снаружи области будет присвоено значение "0". Однако следует отметить, что некоторые варианты осуществления изобретения можно применить к пикселям, у которых имеется диапазон изменения значений, чтобы осуществлять визуализацию в многоцветном или полутоновом режиме. В таких вариантах осуществления изобретения двухуровневое растрирование может состоять в том, что пикселям с центрами внутри области будет присваиваться любое подходящее значение, соответствующее цвету или оттенку серого. Данные пикселя, сформированные модулем 505 растрирования, сохраняются в буферном накопителе 507. Однако если исходный образ представляет небольшую область либо линию, или кривую небольшой толщины (т.е. линию или кривую с толщиной меньше диаметра сглаживающей маски фильтрации), то работу модуля 505 растрирования можно опустить.

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

Средство 501 сглаживания содержит также модуль 511 свертки. Как следует из нижеприведенного описания, модуль 511 свертки выполняет свертку сглаживающей функции фильтрации с зоной или "областью интегрирования", заданной маской фильтрации и прямолинейными отрезками, сформированными модулем 509 вычисления прямолинейных отрезков, чтобы получить фильтрованный образ. В некоторых вариантах осуществления изобретения модуль 511 свертки может непосредственно вычислять свертку функции фильтрации с областью интегрирования. Однако в других вариантах осуществления изобретения модуль 511 свертки может определять свертку функции фильтрации с областью интегрирования посредством поиска значений свертки в справочной таблице 513. Следовательно, средство 501 сглаживания может дополнительно содержать справочную таблицу 513, на которую указывает штриховая линия на фиг.5.

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

Алгоритм визуализации

Ниже, со ссылками на фиг.6A и 6B, приведено подробное описание алгоритма визуализации в соответствии с различными вариантами осуществления изобретения. Как показано на этапе 601, исходный образ, принимаемый средством 501 сглаживания, вводят в хранилище 503 исходных образов. Затем, на этапе 603, модуль 509 определения прямолинейных отрезков формирует приближенный образ, соответствующий исходному образу. В частности, модуль 509 определения прямолинейных отрезков формирует прямолинейные отрезки, аппроксимирующие контуры линий, кривых или областей, представленных исходными входными данными.

Для формирования прямолинейных отрезков, аппроксимирующих линии, кривые или области, представленные исходными образами, можно использовать любой из множества общеизвестных способов. Например, если исходный образ определяет кривые Безье (что возможно при визуализации символов шрифта TrueType), то для получения прямолинейных отрезков, аппроксимирующих кривые Безье, можно применить алгоритм де Кастеля (de Casteljau). Таким образом, как показано на фиг.7, модуль 509 вычисления прямолинейных отрезков может сформировать набор прямолинейных отрезков 701-705, соответствующих криволинейному контуру.

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

Например, если образ описывает многоугольную область сплошного черного тона, то модуль 505 растрирования может присвоить значение "1" (т.е. самое глубокое темное значение пикселя) пикселям с центрами внутри области и присвоить значение "0" (т.е. самое светлое значение пикселя) остальным пикселям. Однако в других вариантах осуществления изобретения модуль 505 растрирования может присваивать другие значения пикселям с центром внутри области и пикселям с центром снаружи области. Например, если пиксель может представлять разные цвета, то пикселям с центрами внутри области модуль 505 растрирования может присваивать значение, соответствующее цвету области. Следовательно, в процессе операции двухуровневого растрирования модуль 505 растрирования формирует для пикселей значения, соответствующие общей форме больших линий, кривых и областей, отображаемых исходными образами.

В показанном варианте осуществления ширина маски сглаживающего фильтра приблизительно равна двум пикселям. Например, если в сглаживающем фильтре применяется прямоугольная маска, то маска может покрывать площадку размером 2×2 пикселя. Если сглаживающий фильтр является фигурой вращения, то радиус маски может быть равен 1 пикселю. Указанные фильтры требуют обработки меньшего числа деталей при свертке, чем фильтры большего размера, и позволяют точно вычислять соответствующие интегралы, что упрощает вычисление свертки. Однако во многих других вариантах осуществления изобретения могут применяться маски с меньшей или большей площадью. Кроме того, в различных вариантах осуществления изобретения можно использовать как положительные, так и отрицательные лепестки.

После записи растрированного образа в буферный накопитель 507 на этапе 607 выполняется фильтрация контуров линии, кривой или области, описанных исходным образом. В частности, на этапе 609 модуль 511 свертки выполняет обход прямолинейных отрезков, сформированных модулем 509 вычисления прямолинейных отрезков, с целью свертки контуров приближенного образа с заданной функцией фильтрации. Следовательно, модуль 511 свертки выполняет обход прямолинейных отрезков приближенного образа, чтобы проинтегрировать область, ограниченную маской фильтрации и прямолинейными отрезками, с функцией фильтрации. В некоторых вариантах осуществления изобретения значения свертки определяются поиском предварительно вычисленных значений свертки в справочной таблице 513. Однако в других вариантах осуществления изобретения, значения свертки могут определяться вычислением свертки в реальном времени.

На этапе 611 фильтрованный образ вводится в буферный накопитель 507 вместе с растрированным образом. Затем фильтрованный образ и растрированный образ можно визуализировать на этапе 613. В некоторых вариантах осуществления изобретения фильтрованные и растрированные образы можно визуализировать группами, соответствующими прямолинейным отрезкам, сформированным модулем 509 вычисления прямолинейных отрезков, чтобы последовательно осуществлять визуализацию кривой, линии или области. Однако в других вариантах осуществления изобретения фильтрованный образ можно визуализировать в реальном времени, параллельно фильтрации приближенного образа.

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

Первая зона меньшего размера ограничена круговой маской 801 свертки, первым прямолинейным отрезком 803 и прямой линией 809, исходящей из центра маски 801 свертки и проходящей через вершину прямолинейного отрезка 803 и прямолинейного отрезка 805. Вторая зона меньшего размера ограничена круговой маской 801 свертки, прямой линией 809, исходящей из центра маски 801 свертки и проходящей через вершину прямолинейного отрезка 803 и прямолинейного отрезка 805, и прямой линией 811, исходящей из центра маски 801 свертки и проходящей через вершину прямолинейного отрезка 805 и прямолинейного отрезка 807. Третья зона меньшего размера ограничена круговой маской 801 свертки, прямой линией 811, исходящей из центра маски 801 свертки и проходящей через вершину прямолинейного отрезка 805 и прямолинейного отрезка 807, и прямолинейным отрезком 807.

Вышеописанный способ деления зон с несколькими вершинами дает зоны трех основных видов. Во-первых, зона без вершины не подлежит делению и остается ограниченной маской свертки и одним прямолинейным отрезком. Например, как видно из фиг.9A, зона первого вида может быть ограничена круговой маской 801 свертки и одним прямолинейным отрезком 901. В другой модификации зона может быть ограничена прямолинейным отрезком и только одной прямой линией, исходящей из центра маски свертки. Поэтому, как видно из фиг.9B, зона может быть ограничена маской 801 свертки, прямолинейным отрезком 903 и одной прямой линией 905, исходящей из центра маски 801 свертки. И, наконец, зона может быть ограничена прямолинейным отрезком и двумя прямыми линиями, исходящими из центра маски свертки. Например, как показано на фиг.9C, зона может быть ограничена маской 801 свертки, прямолинейным отрезком 907, первой прямой линией 909, исходящей из центра маски 801 свертки, и второй прямой линией 911, исходящей из центра маски 801 свертки.

Однако в соответствии с разными вариантами осуществления изобретения зону третьего вида, показанную на фиг.9C, можно разделить дополнительно, чтобы упростить вычисление свертки. В частности, как видно из фиг.10, зону, ограниченную маской 801 свертки, прямолинейным отрезком 1001 и двумя прямыми линиями 1003 и 1005, исходящими из центра маски 801 свертки, можно сформировать вычитанием зоны, ограниченной маской 801 свертки, прямолинейным отрезком 1007 и прямой линией 1005, исходящей из центра маски 801 свертки, из зоны, ограниченной маской 801 свертки, прямолинейным отрезком 1001 и прямой линией 1003. Следовательно, в соответствии с разными вариантами осуществления изобретения область интегрирования, заключенную внутри маски свертки, можно определить суммированием или вычитанием одной из основных областей интегрирования.

Как показано на фиг.11, указанную основную область интегрирования можно задать двумя переменными: расстоянием d от центра маски 801 свертки до прямолинейного отрезка и расстоянием t между точкой пересечения прямолинейного отрезка с маской 801 свертки и точкой пересечения прямолинейного отрезка с прямой линией, исходящей из центра маски 801 свертки. Если маска 801 свертки является круговой маской, то задание границ основной области интегрирования включает третью переменную , которая представляет собой полярный угол поворота прямой линии, исходящей из центра маски 801 свертки. В некоторых случаях вершина пересечения прямой линии, исходящей из центра маски свертки, с прямолинейным отрезком основной области интегрирования будет совпадать с центром самой маски свертки, что осложнит задание границ основной области интегрирования. Однако если такое совпадение имеет место, то вершину можно немного сместить от центра, чтобы облегчить задание границ основной области интегрирования.

Функция фильтрации

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

Известно, что спектр дискретизированного непрерывного сигнала состоит из периодов этого непрерывного сигнала. Следовательно, мерой ступенчатости при дискретизации некоторой зоны может служить энергия спектра в пределах квадрата , где квадратная зона = [- , ] × [- , ] в спектральной области, где = /T, а T - интервал взятия выборок для дискретизированного образа в пространственной области. Для определения обобщенной функции фильтрации, интервал Т взятия выборок можно нормировать с приведением к 1. Для минимизации ступенчатости в сигнале функция фильтрации должна оптимально сконцентрировать спектральную энергию данных, дискретизированных на основе сигнала, в квадрате . Следует отметить, что в ряде вариантов осуществления функция фильтрации по настоящему изобретению не всегда может точно сконцентрировать спектральную энергию данных, дискретизированных на основе сигнала, в квадрате , но может стремиться сконцентрировать спектральную энергию в квадрате .

Для кругового фильтра и конкретной квадратной области ,

а для обобщенного кругового фильтра ,

где означает операцию свертки, [F(g)] означает Фурье-преобразование функции g, I означает подлежащий сглаживанию образ, а h означает сглаживающий фильтр. То есть представляет собой Фурье-преобразование свертки образа со сглаживающей функцией фильтрации. Следовательно, фильтр, который оптимально концентрирует спектральную энергию данных, дискретизированных на основе изображения I, в квадрате , должен удовлетворять уравнению:

где означает, что "h является аргументом, который максимизирует f(h)", т.е. максимизирует функцию от h.

Фурье-преобразование обладает следующим фундаментальным свойством:

[F(I h)]=[F(I)]×[F(h)]. Кроме того, поскольку изображение I часто является мелким объектом, то [F(I)] близко к константе. В соответствии с вышеизложенным изображение I на практике можно опустить как в числителе, так и в знаменателе, что дает выражение:

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

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

где . h определяют каждый раз, когда даются M и h _k (k=0,...,M). В соответствии с вышеизложенным вышеприведенное отношение требуется выразить как функцию h_k (k=0,...,M), чтобы можно было найти эти коэффициенты. Следовательно,

Первое равенство может быть получено заменой h выражением , как принято ранее. Второе равенство вытекает из фундаментального свойства комплексного числа: где означает норму a, а является числом, комплексно сопряженным a. Третье равенство получено на основании свойства линейности Фурье-преобразования, а четвертое равенство получено путем обозначения выражения [F(r ^k)]( _x, _y) через _k. Пятое равенство следует из того, что _k является действительным числом, и потому комплексно сопряженное число не имеет эффекта. Шестое равенство представляет собой всего лишь предыдущее равенство, переписанное в виде двойной суммы, а седьмое равенство может быть получено с использованием свойства линейности интегрирования. Восьмое равенство получено путем обозначения выражения через _kl и использованием такого же обозначения в знаменателе. _kl не обеспечивает решения в конечном виде, а _kl обеспечивает.

Специалистам в данной области техники очевидно, что максимизация отношения = / эквивалентна максимизации с ограничением =1. Способ решения проблемы максимизации с использованием метода множителей Лагранжа дается выражениями:

=0 и =0.

Из вышеприведенной системы вытекает задача собственных векторов

^-1 h= h,

где =(2 )²( _kl), =( _kl), а h=(h ₀,h₁,h_2...h _M)^T. Чтобы максимизировать этот собственный вектор, h следует выбирать как собственный вектор, который соответствует максимальному собственному значению ^-1 . Следовательно, например, при M=3 и R=1 коэффициенты имеют значения h₀=0,56904256713865, h ₁=0,05056692464147, h₂=-0,91026906187835, h₃=0,42672641722501, которые обеспечивают концентрацию энергии на уровне 93,8%. На фиг.12 показано центральное сечение вышеописанного кругового фильтра при R=1, где кривая 1201 соответствует M=1, кривая 1203 соответствует M=2, а кривая 1205 соответствует M 3. Таким образом, можно видеть, что использование M=3 обеспечивает высокую концентрацию энергии.

В вариантах осуществления изобретения с использованием сглаживающих фильтров с прямоугольными масками функция h фильтрации имеет аналогичный вид. Полагая h(x,y)=h(x)h(y),

где

h(x)= ,

и ( R). При небольших R значение M=1 является достаточным для высокой концентрации энергии. Если R=1, то оптимальными коэффициентами являются h₀=0,68925230898772, h ₁=-0,56775692696317, которые обеспечивают концентрацию энергии 93,01%.

На фиг.13A-13D показаны различные изображения, визуализируемые с помощью кругового фильтра с радиусом R=1 в соответствии с различными вышеописанными вариантами осуществления изобретения. Как видно из данных изображений, модификации способа сглаживания по разным вариантам осуществления изобретения обеспечивают высококачественное сглаживание разнотипных изображений, в том числе линейных изображений, изображений, растрированных в шахматном порядке, кривых Безье и шрифтов TrueType.

Заключение

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