close

Вход

Забыли?

вход по аккаунту

?

Патент РФ 2335808

код для вставки
РОССИЙСКАЯ ФЕДЕРАЦИЯ
RU
(19)
(11)
2 335 808
(13)
C2
(51) МПК
G09G 5/28
(2006.01)
ФЕДЕРАЛЬНАЯ СЛУЖБА
ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ,
ПАТЕНТАМ И ТОВАРНЫМ ЗНАКАМ
(12)
ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ
(21), (22) За вка: 2004106719/09, 05.03.2004
(30) Конвенционный приоритет:
03.04.2003 US 10/406,517
(73) Патентообладатель(и):
МАЙКРОСОФТ КОРПОРЕЙШН (US)
(43) Дата публикации за вки: 10.08.2005
R U
(24) Дата начала отсчета срока действи патента:
05.03.2004
(72) Автор(ы):
ЛИНЬ Чжоучэнь (CN),
ВАН Цз нь (CN),
ЧЭНЬ Хайтао (CN)
(45) Опубликовано: 10.10.2008 Бюл. № 28
2 3 3 5 8 0 8
(56) Список документов, цитированных в отчете о
поиске: RU 2150146 С1, 27.05.2000. GB 2357021
А, 06.06.2001. US 6097400 А, 01.08.2000. KR
20020087832 А, 23.11.2002.
(57) Реферат:
Изобретение относитс к способам и
устройствам сглаживани изображений дл последующей
визуализации.
Технический
результат, заключающийс в возможности
сглаживани разнотипных
изображений,
достигаетс тем, что обеспечивают представление
кра линии, кривой или области в виде набора
пр молинейных отрезков. Затем совершают обход
упом нутых пр молинейных отрезков, чтобы
выполнить свертку упом нутых пр молинейных
отрезков,
аппроксимирующих
контуры
изображени , с заданной функцией фильтрации.
При этом сглаживающий фильтр стремитс сконцентрировать
спектральную
энергию
изображени в дискретизируемой области. 4 н. и 22
з.п. ф-лы, 24 ил.
R U
2 3 3 5 8 0 8
(54) ВЫСОКОКАЧЕСТВЕННОЕ СГЛАЖИВАНИЕ
Страница: 1
RU
C 2
C 2
Адрес дл переписки:
129090, Москва, ул. Б. Спасска , 25, стр.3,
ООО "Юридическа фирма Городисский и
Партнеры", пат.пов. Ю.Д.Кузнецову, рег.№ 595
C 2
C 2
2 3 3 5 8 0 8
2 3 3 5 8 0 8
R U
R U
Страница: 2
RUSSIAN FEDERATION
RU
(19)
(11)
2 335 808
(13)
C2
(51) Int. Cl.
G09G 5/28
(2006.01)
FEDERAL SERVICE
FOR INTELLECTUAL PROPERTY,
PATENTS AND TRADEMARKS
(12)
ABSTRACT OF INVENTION
(21), (22) Application: 2004106719/09, 05.03.2004
(72) Inventor(s):
LIN' Chzhouchehn' (CN),
VAN Tszjan' (CN),
ChEhN' Khajtao (CN)
(24) Effective date for property rights: 05.03.2004
(30) Priority:
03.04.2003 US 10/406,517
(43) Application published: 10.08.2005
(45) Date of publication: 10.10.2008 Bull. 28
2 3 3 5 8 0 8
R U
(57) Abstract:
FIELD: physics.
SUBSTANCE: edge of line, curve or area is
represented as set of straight segments. Then the
specified straight segments are bypassed to
provide convolution of the specified straight
segments approximating image contours of the
image
at
preset
filtration
function.
Thus
smoothing filter tends to concentrate image
spectral energy within discrete area.
EFFECT: possibility of heterogeneous images
smoothing.
Страница: 3
EN
26 cl, 24 dwg
C 2
C 2
(54) HIGH-PERFORMANCE SMOOTHING
2 3 3 5 8 0 8
Mail address:
129090, Moskva, ul. B. Spasskaja, 25, str.3,
OOO "Juridicheskaja firma Gorodisskij i
Partnery", pat.pov. Ju.D.Kuznetsovu, reg.№ 595
R U
(73) Proprietor(s):
MAJKROSOFT KORPOREJShN (US)
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
Область техники, к которой относитс изобретение
Насто щее изобретение относитс к способу сглаживани дл визуализации
изображений. Различные варианты осуществлени насто щего изобретени хорошо
применимы к визуализации плоскозатененных графических объектов, например шрифтов,
кривых и областей.
Предшествующий уровень техники
Вычислительна мощность современных компьютеров достигла очень высоких значений
и обеспечивает выполнение тыс ч вычислений в секунду. Вычислительные ресурсы такой
мощности часто используют дл отображени или визуализации изображений высокого
разрешени на экранах мониторов или телевизоров. Например, компьютеры используют
дл формировани реалистических изображений дл кинофильмов, сложной анимации дл игр и даже изображений, записанных в пам ть с фотокамер. Дл формировани упом нутых изображений компьютер может вычисл ть и строить линии, кривые и области.
Хот компьютер способен вычисл ть гладкие и непрерывные линии, кривые и области,
отображают эти линии, кривые и области по-прежнему на экране монитора или телевизора,
который представл ет изображени в виде совокупности дискретных элементов или
"пикселей".
Следовательно, гладкие линии, кривые или области, сформированные в компьютере,
фактически нельз отобразить или визуализировать так, как они сформированы. Вместо
этого они должны быть дискретизированы в дискретных точках, соответствующих
отдельным пиксел м. Однако, если частота характерных признаков линии, кривой или
области выше частоты дискретизации линии, кривой или области с целью формировани пикселей, то дискретизированные образы (данные изображени ) не будут точно
отображать исходные сформированные образы. Например, на фиг.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, способ сглаживани мог бы обеспечивать
Страница: 4
DE
RU 2 335 808 C2
5
10
15
20
представление некоторых пикселей 203, соответствующих пр мой линии 201, более
светлым оттенком. В соответствии с некоторыми способами сглаживани цвет или
интенсивность пиксел (т.е. значение пиксел ) присваивают в зависимости от степени
совмещени пиксел со сформированной линией, кривой или областью. Более того, в
соответствии с некоторыми из упом нутых способов сглаживани соответствующий
пиксель, возможно, даже не будет активирован, если степень совмещени данного пиксел со сформированной линией, кривой или областью не достаточна дл активации.
Разработано много различных способов определени значени , присваиваемого пикселю в
зависимости от его совмещени со сформированной линией, кривой или областью. В
соответствии с некоторыми способами значение пиксел определ ют путем делени на
несколько субпикселей, а затем определ ют, сколько субпикселей пересекаютс сформированной линией, кривой или областью. Например, пикселю, в котором
сформированна лини , крива или область пересекает только три субпиксел , может быть
присвоено меньшее значение, чем пикселю, в котором сформированна лини , крива или
область пересекает семь субпикселей. В соответствии с некоторыми способами
сглаживани каждому субпикселю дополнительно присваивают весовой коэффициент,
чтобы субпиксели, расположенные ближе к центру пиксел , сильнее вли ли на значение,
присваиваемое пикселю, чем субпиксели, расположенные дальше от центра пиксел .
В соответствии с другими способами сглаживани , значение пиксел определ ют по
общей степени совмещени пиксел со сформированной линией, кривой или областью. В
частности, данные способы состо т в том, что выполн ют свертку непрерывной весовой
функции, называемой "функцией фильтрации", с зоной одного или нескольких пикселей,
покрывающих сформированную линию, кривую или область. Общее уравнение свертки
имеет вид:
25
30
35
40
45
50
где
- дро свертки, а
- свертываема функци . В контексте способов
сглаживани свертываема функци вл етс функцией изображени , формирующей
линию, кривую или область, а дро свертки
вл етс функцией фильтрации,
котора умножаетс на значение пиксел . Произведение функции фильтрации и функции
изображени интегрируют по заданной зоне, называемой маской фильтрации. Операцию
свертки называют предфильтрацией, потому что высокочастотные характерные признаки
образов отфильтровывают перед их отображением.
Дл сглаживани ранее примен ли много разных функций фильтрации. Например, дл сглаживани широко примен ли пр моугольные функции, конические функции и гауссовы
функции. Некоторые функции фильтрации, например конические и гауссовы функции,
вл ютс двухмерными функци ми. При использовании этих функций высота функции
фильтрации измен ет весовое значение, перемножаемое со значением пиксел , в
зависимости от местоположени внутри пиксел . Так, двухмерна кругова функци или
функци вращени может обеспечивать большее весовое значение перекрытию пиксел сформированной линии, кривой или области в центре пиксел , чем перекрытию у кра пиксел .
Кроме разных функций фильтрации, разные способы сглаживани могут различатьс примен емыми масками фильтрации. Например, некоторые способы сглаживани могут
предусматривать применение квадратной маски фильтрации, покрывающей один или
несколько пикселей. Другие способы сглаживани могут предусматривать попеременное
применение круговой маски фильтрации с диаметром, равным одному, двум, трем,
четырем или более значени м ширины пиксел . На фиг.3 показана область 301, которую
визуализирует группа пикселей 303 с центром каждого пиксел в точке 303А. Данна фигура показывает также круговую свертку или маску 305 фильтрации с диаметром,
равным двукратной ширине пиксел 303. Как видно из данной фигуры, если маску 305
располагают по центру пиксел , то она будет достигать центра каждого непосредственно
примыкающего пиксел .
Страница: 5
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
Несмотр на разработку множества способов сглаживани , каждый из упом нутых
способов обычно может работать с образами только конкретного типа, дл которого
упом нутые способы были разработаны. Например, способы сглаживани , разработанные
дл визуализации небольших многоугольников, обычно не совсем подход т дл визуализации кривых или шрифтов. Аналогично способы сглаживани , предназначенные
дл визуализации кривых, не совсем пригодны дл визуализации многоугольников или
шрифтов, а способы сглаживани , предназначенные дл визуализации шрифтов, обычно
малопригодны дл визуализации многоугольников или кривых. В соответствии с
вышеизложенным, существует потребность в способе сглаживани , который будет
обеспечивать высококачественное сглаживание разнотипных образов.
Краткое изложение сущности изобретени Важное преимущество насто щего изобретени состоит в том, что различные варианты
осуществлени изобретени обеспечивают способ и устройство сглаживани , пригодные
дл сглаживани разнотипных изображений, включа шрифты, большие изображени и
очень мелкие изображени . В частности, некоторые варианты осуществлени изобретени обеспечивают способ представлени кра линии, кривой или области в виде набора
пр молинейных отрезков. В соответствии со способом сглаживани по насто щим
вариантам осуществлени затем совершают обход упом нутых пр молинейных отрезков,
чтобы выполнить свертку упом нутых пр молинейных отрезков, аппроксимирующих
контуры изображени , с заданной функцией фильтрации.
Другие варианты осуществлени насто щего изобретени относ тс к фильтру дл сглаживани краев линии, кривой или области, который можно применить, если край
представл етс набором пр молинейных отрезков. В соответствии с данными вариантами
осуществлени изобретени сглаживающий фильтр стремитс сконцентрировать
спектральную энергию изображени в дискретизированной зоне.
Перечень фигур чертежей
Фиг.1A и 1C представл ют контуры с разными пространственными частотами
характерных признаков.
Фиг.1B и 1D демонстрируют контуры, полученные посредством дискретизации контуров,
показанных соответственно на фиг.1A и 1C.
Фиг.2A представл ет вычисленную линию, наложенную на массив пикселей.
Фиг.2B и 2C демонстрируют активацию пикселей дл визуализации вычисленной линии,
изображенной на фиг.2A, с помощью разных способов визуализации.
Фиг.3 демонстрирует круговую маску фильтрации дл предфильтрации линии, кривой
или области с помощью способа сглаживани .
Фиг.4 демонстрирует вычислительное устройство дл реализации способа сглаживани в соответствии с различными вариантами осуществлени насто щего изобретени .
Фиг.5 демонстрирует систему сглаживани дл реализации способа сглаживани в
соответствии с различными вариантами осуществлени насто щего изобретени .
Фиг.6A и 6B демонстрируют этапы реализации способа сглаживани в соответствии с
различными вариантами осуществлени насто щего изобретени .
Фиг.7 демонстрирует пример контура, разделенного на пр молинейные отрезки по
способу сглаживани в соответствии с различными вариантами осуществлени насто щего
изобретени .
Фиг.9A и 9C демонстрируют примеры пр молинейных отрезков внутри круговой маски
фильтрации по способу сглаживани в соответствии с различными вариантами
осуществлени насто щего изобретени .
Фиг.8 и 10 демонстрируют эквивалентность зон, охваченных различными
пересекающимис пр молинейными отрезками и круговым фильтром, примен емым в
способе сглаживани в соответствии с различными вариантами осуществлени насто щего
изобретени .
Фиг.11 демонстрирует обобщенное вычисление площади, охваченной двум пересекающимис пр молинейными отрезками и круговым фильтром, примен емым в
Страница: 6
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
способе сглаживани в соответствии с различными вариантами осуществлени насто щего
изобретени .
Фиг.12 демонстрирует сечени круговых полиномиальных фильтров по варианту
осуществлени насто щего изобретени дл трех разных коэффициентов фильтрации M.
Фиг.13A-13D демонстрируют различные изображени , визуализируемые с помощью
способа сглаживани в соответствии с одним вариантом осуществлени насто щего
изобретени .
Подробное описание изобретени Введение
Способ сглаживани в соответствии с различными вариантами осуществлени изобретени обеспечивает получение фильтрованных образов посредством
предфильтрации исходных образов. Варианты осуществлени изобретени содержат две
составл ющие. Первой составл ющей вл етс функци фильтрации, примен ема дл взвешивани исходных образов. Из приведенного ниже подробного описани видно, что
функции фильтрации, используемые в разных вариантах осуществлени изобретени ,
стрем тс оптимально сконцентрировать спектральную энергию дискретизированных
образов в зоне, наход щейс в спектральной области, соответствующей интервалу вз ти выборок дискретизированных образов в пространственной области. Второй составл ющей
вл етс алгоритм визуализации, который примен ет функцию фильтрации к исходным
образам с целью их фильтрации. Ниже приведено подробное описание каждой из
упом нутых составл ющих.
Операционна среда
Специалистам в данной области техники очевидно, что способ сглаживани в
соответствии с различными вариантами осуществлени изобретени можно реализовать
аппаратными средствами, программными средствами, встроенными программными
средствами или с помощью комбинации перечисленных средств. Например, различные
варианты осуществлени изобретени можно реализовать с помощью функциональных
модулей, которые выполн ют операции способа сглаживани . Каждый из модулей можно
выполнить на аналоговых или цифровых электронных схемах. Специалистам в данной
области техники очевидно, однако, что модули можно также выполнить на
программируемых электронных схемах, запрограммированных исполн емыми командами
такого типа, которые примен ютс в обычных программируемых вычислительных
устройствах.
В частности, описание систем сглаживани в соответствии с различными вариантами
осуществлени изобретени можно дать в общей св зи с машиноисполн емыми
командами, например программными модул ми, исполн емыми одним или несколькими
программируемыми вычислительными устройствами. Обычно программные модули могут
содержать алгоритмы, программы, объекты, компоненты, структуры данных и т.д., которые
выполн ют конкретные задачи или реализуют конкретные абстрактные типы данных.
Обычно функции программных модулей можно сочетать или распредел ть в соответствии
с потребностью различных вариантов осуществлени .
Поскольку различные варианты осуществлени изобретени можно реализовать с
помощью программируемых вычислительных устройств, запрограммированных
соответствующим программным обеспечением, то дл более пон тного изложени изобретени , возможно, полезно дать краткое описание компонентов и принципа действи типичного программируемого вычислительного устройства (далее называемого просто
компьютером), в котором можно реализовать различные варианты осуществлени изобретени . На фиг.4 приведен пример вычислительного устройства 401,
обеспечивающего подход щую операционную среду, в которой можно реализовать
различные варианты осуществлени изобретени . Данна операционна среда вл етс всего лишь примером подход щей операционной среды и не может подразумевать никаких
ограничений в отношении объема применени и функциональных возможностей
изобретени . Другими общеизвестными вычислительными системами, средами и/или
Страница: 7
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
конфигураци ми, которые можно применить с насто щим изобретением, вл ютс , без
ограничени , персональные компьютеры, компьютеры-серверы, карманные и портативные
компьютеры, микропроцессорные системы, системы на базе микропроцессоров,
программируема бытова электронна аппаратура, сети персональных компьютеров,
миникомпьютеры, универсальные компьютеры, распределенные вычислительные среды,
которые содержат любые из вышеупом нутых систем или устройств, и т.п.
Вычислительное устройство 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 вывода дл вывода данных дл пользовател , например, на дисплей, громкоговоритель, принтер или тактильное
Страница: 8
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
устройство с обратной св зью. Например, устройство вывода 417 может содержать ЭЛТдисплей, плазменный дисплей, жидкокристаллический дисплей, дисплей на органическом
соединении или дисплей любого другого типа. Специалистам в данной области техники
очевидно, что дисплей каждого из упом нутых типов будет визуализировать изображени посредством активации дискретных элементов изображени . Другими компонентами
вычислительного устройства 401 могут быть каналы 419 св зи с другими устройствами,
компьютерами, сет ми и т.д. на основе либо проводных, либо беспроводных сред св зи.
Специалистам в данной области техники очевидно, что каналы 419 св зи вл ютс примером среды передачи данных. Все данные устройства и каналы общеизвестны в
рассматриваемой области техники и потому не рассмотрены подробно в данном описании.
Средства сглаживани Фиг.5 демонстрирует средство 501 сглаживани дл реализации способа сглаживани в
соответствии с различными вариантами осуществлени изобретени . Средство 501
сглаживани содержит хранилище 503 исходных образов, модуль 505 растрировани ,
буферный накопитель 507 и модуль 509 вычислени пр молинейных отрезков. Как следует
из нижеприведенного описани , хранилище 503 исходных образов содержит исходные
образы, подлежащие визуализации с использованием способа сглаживани в соответствии
с данным вариантом осуществлени изобретени . Исходные образы можно хранить в
любой подход щей форме, например в форме, по меньшей мере, одного математического
уравнени , описывающего подлежащую визуализации область, кривую или линию.
Например, если способ сглаживани используют дл визуализации пр мой линии, то
исходным образом может быть уравнение у=mx+с, где m обозначает наклон пр мой, а с
обозначает смещение пр мой.
Специалистам в данной области техники очевидно, что исходные образы могут
представл ть линию, кривую или область. Если исходный образ представл ет большую
область (например, область с шириной больше диаметра сглаживающей маски
фильтрации, используемой дл сглаживани области), то сглаживать потребуетс только
кра области. В частности, если образ представл ет большую область, то сглаживать
требуетс только те характерные признаки области, которые расположены по кра м
области. Следовательно, чтобы отличить область от соседних линий, кривых и областей,
необходимо четко визуализировать только кра большой области. Остальную часть
области, наход щуюс за пределами охватывающего диаметра сглаживающей маски
фильтрации, можно быстро и эффективно визуализировать непосредственно по исходному
образу, не подверга его сглаживающей фильтрации.
В соответствии с вышеизложенным, если исходный образ представл ет большую
область, то модуль 505 растрировани формирует исходное значение пиксел дл каждого
пиксел диспле . В частности, модуль 505 растрировани примен ет операцию
растрировани дл формировани исходных значений пикселей, соответствующих области,
определ емой исходным образом. Операци растрировани может быть, например,
операцией двухуровневого растрировани . Операци двухуровневого растрировани присваивает пикселю первое значение, если центр пиксел находитс внутри упом нутой
области, и присваивает пикселю второе значение, если центр пиксел находитс снаружи
области.
Следовательно, если область представл ет собой сплошную черную площадку, а
черный пиксель имеет значение, обозначаемое "1", то пиксел м с центрами внутри этой
области будет присвоено значение "1", а пиксел м с центрами снаружи области будет
присвоено значение "0". Однако следует отметить, что некоторые варианты осуществлени изобретени можно применить к пиксел м, у которых имеетс диапазон изменени значений, чтобы осуществл ть визуализацию в многоцветном или полутоновом режиме. В
таких вариантах осуществлени изобретени двухуровневое растрирование может
состо ть в том, что пиксел м с центрами внутри области будет присваиватьс любое
подход щее значение, соответствующее цвету или оттенку серого. Данные пиксел ,
сформированные модулем 505 растрировани , сохран ютс в буферном накопителе 507.
Страница: 9
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
Однако если исходный образ представл ет небольшую область либо линию, или кривую
небольшой толщины (т.е. линию или кривую с толщиной меньше диаметра сглаживающей
маски фильтрации), то работу модул 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
растрировани выполн ет операцию двухуровневого растрировани на исходном образе.
Например, если исходный образ описывает шрифт или многоугольник большой толщины,
Страница: 10
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
то модуль 505 растрировани примен ет операцию двухуровневого растрировани к
исходному образу. Модуль 505 растрировани присваивает первое значение таким
пиксел м, центры которых наход тс внутри кривой, линии или области, описанной
исходным образом, и присваивает второе значение таким пиксел м, центры которых
наход тс снаружи кривой, линии или области.
Например, если образ описывает многоугольную область сплошного черного тона, то
модуль 505 растрировани может присвоить значение "1" (т.е. самое глубокое темное
значение пиксел ) пиксел м с центрами внутри области и присвоить значение "0" (т.е.
самое светлое значение пиксел ) остальным пиксел м. Однако в других вариантах
осуществлени изобретени модуль 505 растрировани может присваивать другие
значени пиксел м с центром внутри области и пиксел м с центром снаружи области.
Например, если пиксель может представл ть разные цвета, то пиксел м с центрами внутри
области модуль 505 растрировани может присваивать значение, соответствующее цвету
области. Следовательно, в процессе операции двухуровневого растрировани модуль 505
растрировани формирует дл пикселей значени , соответствующие общей форме
больших линий, кривых и областей, отображаемых исходными образами.
В показанном варианте осуществлени ширина маски сглаживающего фильтра
приблизительно равна двум пиксел м. Например, если в сглаживающем фильтре
примен етс пр моугольна маска, то маска может покрывать площадку размером 2Ч2
пиксел . Если сглаживающий фильтр вл етс фигурой вращени , то радиус маски может
быть равен 1 пикселю. Указанные фильтры требуют обработки меньшего числа деталей
при свертке, чем фильтры большего размера, и позвол ют точно вычисл ть
соответствующие интегралы, что упрощает вычисление свертки. Однако во многих других
вариантах осуществлени изобретени могут примен тьс маски с меньшей или большей
площадью. Кроме того, в различных вариантах осуществлени изобретени можно
использовать как положительные, так и отрицательные лепестки.
После записи растрированного образа в буферный накопитель 507 на этапе 607
выполн етс фильтраци контуров линии, кривой или области, описанных исходным
образом. В частности, на этапе 609 модуль 511 свертки выполн ет обход пр молинейных
отрезков, сформированных модулем 509 вычислени пр молинейных отрезков, с целью
свертки контуров приближенного образа с заданной функцией фильтрации.
Следовательно, модуль 511 свертки выполн ет обход пр молинейных отрезков
приближенного образа, чтобы проинтегрировать область, ограниченную маской
фильтрации и пр молинейными отрезками, с функцией фильтрации. В некоторых
вариантах осуществлени изобретени значени свертки определ ютс поиском
предварительно вычисленных значений свертки в справочной таблице 513. Однако в
других вариантах осуществлени изобретени , значени свертки могут определ тьс вычислением свертки в реальном времени.
На этапе 611 фильтрованный образ вводитс в буферный накопитель 507 вместе с
растрированным образом. Затем фильтрованный образ и растрированный образ можно
визуализировать на этапе 613. В некоторых вариантах осуществлени изобретени фильтрованные и растрированные образы можно визуализировать группами,
соответствующими пр молинейным отрезкам, сформированным модулем 509 вычислени пр молинейных отрезков, чтобы последовательно осуществл ть визуализацию кривой,
линии или области. Однако в других вариантах осуществлени изобретени фильтрованный образ можно визуализировать в реальном времени, параллельно
фильтрации приближенного образа.
В соответствии с вышеизложенным дл приближенного образа, контуры которого
сформированы пр молинейными отрезками, свертку с функцией фильтрации вычислить
намного проще, чем дл исходного образа. Однако в некоторых случа х маска свертки
может охватывать, по меньшей мере, две вершины между разными пр молинейными
отрезками. В указанных случа х задача вычислени интеграла дл описанной зоны и,
следовательно, свертки может осложн тьс . В соответствии с вышеизложенным в
Страница: 11
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
различных вариантах осуществлени изобретени , чтобы получить свертку дл зон,
содержащих, по меньшей мере, две вершины пр молинейных отрезков, эти зоны дел т на
зоны меньшего размера, более удобные дл вычислений. Во-первых, зона с несколькими
вершинами делитс лини ми, исход щими из центра маски свертки и проход щими через
каждую вершину. Например, на фиг.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 свертки. В некоторых случа х вершина пересечени пр мой линии, исход щей из
центра маски свертки, с пр молинейным отрезком основной области интегрировани будет
совпадать с центром самой маски свертки, что осложнит задание границ основной области
Страница: 12
RU 2 335 808 C2
5
10
15
20
25
30
интегрировани . Однако если такое совпадение имеет место, то вершину можно немного
сместить от центра, чтобы облегчить задание границ основной области интегрировани .
Функци фильтрации
Хот вышеописанный способ визуализации можно применить с любой подход щей
функцией фильтрации, в различных вариантах осуществлени изобретени примен ют
функцию фильтрации, котора стремитс оптимально сконцентрировать спектральную
энергию дискретизированных образов в зоне, наход щейс в спектральной области и
соответствующей интервалу вз ти выборок дискретизированных образов в
пространственной области. В некоторых вариантах осуществлени изобретени функцию
фильтрации задают сфероидальной волновой функцией. Однако в других вариантах
осуществлени изобретени функцию фильтрации задают полиномом, который можно
проще вычислить дл разнообразных областей интегрировани .
Известно, что спектр дискретизированного непрерывного сигнала состоит из периодов
этого непрерывного сигнала. Следовательно, мерой ступенчатости при дискретизации
некоторой зоны может служить энерги спектра в пределах квадрата ?, где квадратна зона ? = [- ?, ?] Ч [- ?, ?] в спектральной области, где ? = ?/T, а T - интервал вз ти выборок дл дискретизированного образа в пространственной области. Дл определени обобщенной функции фильтрации, интервал Т вз ти выборок можно нормировать с
приведением к 1. Дл минимизации ступенчатости в сигнале функци фильтрации должна
оптимально сконцентрировать спектральную энергию данных, дискретизированных на
основе сигнала, в квадрате ?. Следует отметить, что в р де вариантов осуществлени функци фильтрации по насто щему изобретению не всегда может точно
сконцентрировать спектральную энергию данных, дискретизированных на основе сигнала,
в квадрате ?, но может стремитьс сконцентрировать спектральную энергию в
квадрате ?.
Дл кругового фильтра ? ? и конкретной квадратной области ?,
а дл обобщенного кругового фильтра ?,
где ? означает операцию свертки, [F(g)] означает Фурье-преобразование функции g, I
означает подлежащий сглаживанию образ, а h означает сглаживающий фильтр. То есть
представл ет собой Фурье-преобразование свертки образа
35
со сглаживающей функцией фильтрации. Следовательно, фильтр, который оптимально
концентрирует спектральную энергию данных, дискретизированных на основе изображени I, в квадрате ?, должен удовлетвор ть уравнению:
40
где
45
означает, что "h вл етс аргументом, который максимизирует
f(h)", т.е. максимизирует функцию от h.
Фурье-преобразование обладает следующим фундаментальным свойством:
[F(I?h)]=[F(I)]Ч[F(h)]. Кроме того, поскольку изображение I часто вл етс мелким
объектом, то [F(I)] близко к константе. В соответствии с вышеизложенным изображение I
на практике можно опустить как в числителе, так и в знаменателе, что дает выражение:
50
Следовательно, формула, определ юща сглаживающий фильтр, становитс фактически независимой от изображени I. Независимость от фактического значени Страница: 13
RU 2 335 808 C2
5
10
любого конкретного изображени I означает достижение преимущества, которое
заключаетс в пригодности сглаживающей функции h дл всех типов изображений.
Специалистам в данной области техники очевидно, что оптимальным решением этого
уравнени вл етс выт нута сфероидальна волнова функци нулевого пор дка,
котора не имеет решени в конечном виде. В соответствии с вышеизложенным требуетс найти полиномиальные фильтры, которые также максимизируют вышеприведенное
отношение. Например, дл кругового фильтра можно прин ть, что
где
. h определ ют каждый раз, когда даютс M и hk (k=
0,...,M). В соответствии с вышеизложенным вышеприведенное отношение требуетс выразить как функцию hk (k=0,...,M), чтобы можно было найти эти коэффициенты.
Следовательно,
15
20
25
30
35
Первое равенство может быть получено заменой h выражением
40
45
50
, как прин то
ранее. Второе равенство вытекает из фундаментального свойства комплексного числа:
где
означает норму a, а
вл етс числом, комплексно сопр женным a.
Третье равенство получено на основании свойства линейности Фурье-преобразовани , а
четвертое равенство получено путем обозначени выражени [F(r k)](? x,? y) через ?k.
П тое равенство следует из того, что ?k вл етс действительным числом, и потому
комплексно сопр женное число не имеет эффекта. Шестое равенство представл ет собой
всего лишь предыдущее равенство, переписанное в виде двойной суммы, а седьмое
равенство может быть получено с использованием свойства линейности интегрировани .
Восьмое равенство получено путем обозначени выражени через ?kl и
использованием такого же обозначени в знаменателе. ?kl не обеспечивает решени в
конечном виде, а ? kl обеспечивает.
Специалистам в данной области техники очевидно, что максимизаци отношени ? = ? ?/? эквивалентна максимизации ? ? с ограничением ?=1. Способ решени проблемы максимизации с использованием метода множителей Лагранжа даетс Страница: 14
RU 2 335 808 C2
выражени ми:
=0 и
5
10
15
20
Из вышеприведенной системы вытекает задача собственных векторов
-1
? ?h=?h,
где ? =(2?) 2(? kl), ?=(?kl), а h=(h0,h1,h2...hM) T. Чтобы максимизировать этот собственный
вектор, h следует выбирать как собственный вектор, который соответствует максимальному
собственному значению ? -1?. Следовательно, например, при M=3 и R=1 коэффициенты
имеют значени h0=0,56904256713865, h1=0,05056692464147, h2=0,91026906187835, h3=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)=
,
и(
25
30
35
40
45
50
=0.
R). При небольших R значение M=1 вл етс достаточным дл высокой
концентрации энергии. Если R=1, то оптимальными коэффициентами
вл ютс h0=0,68925230898772, h1=-0,56775692696317, которые обеспечивают
концентрацию энергии 93,01%.
На фиг.13A-13D показаны различные изображени , визуализируемые с помощью
кругового фильтра с радиусом R=1 в соответствии с различными вышеописанными
вариантами осуществлени изобретени . Как видно из данных изображений, модификации
способа сглаживани по разным вариантам осуществлени изобретени обеспечивают
высококачественное сглаживание разнотипных изображений, в том числе линейных
изображений, изображений, растрированных в шахматном пор дке, кривых Безье и
шрифтов TrueType.
Заключение
Хот насто щее изобретение описано на конкретных примерах предпочтительных на
данный момент вариантов осуществлени изобретени , специалистам в данной области
техники очевидна возможность многочисленных изменений и перестановок в
вышеописанных системах и способах, не выход щих за пределы сущности и объема
насто щего изобретени , определенных в прилагаемой формуле изобретени .
Формула изобретени 1. Способ визуализации изображени , содержащий этапы, на которых:
получают фактический образ дл контура, подлежащего визуализации;
определ ют приближенный образ дл одного или более пр молинейных отрезков,
которые аппроксимируют контур, подлежащий визуализации;
фильтруют пр молинейные отрезки посредством свертки приближенного образа с
фильтром, выполн емой таким образом, чтобы фильтр стремилс оптимально
сконцентрировать спектральную энергию дискретизированного образа в зоне, наход щейс в спектральной области, соответствующей интервалу вз ти выборок дискретизированного
образа в пространственной области, с целью формировани фильтрованного образа; и
визуализируют контур с использованием фильтрованного образа.
2. Способ по п.1, в котором фильтр вл етс функцией h, причем
Страница: 15
CL
RU 2 335 808 C2
5
10
15
где [F(h)] означает Фурье-преобразование h, a ? означает зону, наход щуюс в
спектральной области, соответствующей интервалу вз ти выборок дикретизированного
образа в пространственной области.
3. Способ по п.2, в котором зона ? =[- ?, ?]Ч[- ?, ?] в спектральной области,
где ?=?/T, а Т означает интервал вз ти выборок дл дискретизированного образа в
пространственной области.
4. Способ по п.2, в котором фильтр вл етс круговым фильтром h(f,?), заданным
уравнением
,
где r?[0,R].
5. Способ по п.4, в котором радиус маски кругового фильтра равен 1 пикселю.
6. Способ по п.2, в котором фильтр вл етс квадратным фильтром h(x), заданным
уравнением
,
20
25
30
35
40
45
50
где(|х|?R).
7. Способ по п.2, в котором размер маски квадратного фильтра равен 2 пиксел на 2
пиксел .
8. Способ по п.1, дополнительно содержащий этапы, на которых:
определ ют, превышает ли ширина приближенного образа ширину маски фильтра; и
если ширина приближенного образа превышает ширину маски фильтра, то фильтруют
кра приближенного образа.
9. Способ по п.8, дополнительно содержащий следующий этап, на котором растрируют
блоки приближенного образа, наход щиес за пределами ширины маски фильтра.
10. Способ по п.1, дополнительно содержащий следующие этапы, на которых:
определ ют, пересекаютс ли один или более пр молинейных отрезков внутри маски
фильтра; и
если один или более пр молинейных отрезков пересекаютс внутри маски фильтра, то
дел т область интегрировани , заданную маской фильтра и пересекающимис пр молинейными отрезками, на две или более зон без пересечений пр молинейных
отрезков, и фильтруют по отдельности каждую из двух или более зон.
11. Средство дл визуализации изображени , содержащее:
хранилище исходных образов, которое хранит исходные образы;
модуль определени пр молинейных отрезков, который определ ет данные
пр молинейных отрезков, аппроксимирующих контур исходного образа; и
модуль свертки, который вычисл ет свертку данных пр молинейных отрезков с
фильтром, чтобы получить фильтрованный образ.
12. Средство по п.11, дополнительно содержащее модуль растрировани , который
растрирует блоки данных пр молинейных отрезков, наход щихс за пределами ширины
маски фильтра от кра данных пр молинейных отрезков.
13. Средство по п.12, дополнительно содержащее буферный накопитель, который
хранит растрированные блоки данных пр молинейных отрезков.
14. Средство по п.11, дополнительно содержащее буферный накопитель, который
хранит фильтрованные образы.
15. Средство по п.11, дополнительно содержащее справочную таблицу интегралов,
котора хранит значени свертки образа с фильтром.
16. Способ визуализации изображени , содержащий этапы, на которых: получают
фактический образ дл контура, подлежащего визуализации; определ ют приближенный
Страница: 16
RU 2 335 808 C2
5
10
15
20
25
30
35
образ дл одного или более пр молинейных отрезков, которые аппроксимируют контур,
подлежащий визуализации; фильтруют пр молинейные отрезки посредством свертки
приближенного образа с фильтром; и
визуализируют контур с использованием фильтрованного образа.
17. Способ по п.16, дополнительно содержащий этапы, на которых:
определ ют, превышает ли ширина приближенного образа ширину маски фильтра; и
если ширина приближенного образа превышает ширину маски фильтра, то фильтруют
кра приближенного образа.
18. Способ по п.17, дополнительно содержащий этап, на котором растрируют блоки
приближенного образа, наход щиес за пределами ширины маски фильтра.
19. Способ по п.16, дополнительно содержащий этапы, на которых:
определ ют, пересекаютс ли один или более пр молинейных отрезков внутри маски
фильтра; и
если один или более пр молинейных отрезков пересекаютс внутри маски фильтра, то
дел т область интегрировани , заданную маской фильтра и пересекающимис пр молинейными отрезками, на две или более зон без пересечений пр молинейных
отрезков, и
фильтруют по отдельности каждую из двух или более зон.
20. Способ визуализации изображени , содержащий этапы, на которых: получают образ;
фильтруют образ посредством свертки образа с фильтром, выполн емой таким
образом, чтобы фильтр стремилс оптимально сконцентрировать спектральную энергию
дискретизированного образа в зоне, наход щейс в спектральной области,
соответствующей интервалу вз ти выборок дискретизированного образа в
пространственной области, с целью формировани фильтрованного образа; и
визуализируют фильтрованный образ.
21. Способ по п.20, в котором фильтр вл етс функцией h, где
,
где [F(h)] означает Фурье-преобразование h, a ? означает зону, наход щуюс в
спектральной области, соответствующей интервалу вз ти выборок дикретизированного
образа в пространственной области.
22. Способ по п.21, в котором зона ?=[- ?, ?]Ч[- ? , ? ] в спектральной области,
где ?=?/Т, а Т означает интервал вз ти выборок дл дискретизированного образа в
пространственной области.
23. Способ по п.20, в котором фильтр вл етс круговым фильтром h(r,?), заданным
уравнением
,
40
45
50
где r?[0,R].
24. Способ по п.23, в котором радиус маски кругового фильтра равен 1 пикселю.
25. Способ по п.20, в котором фильтр вл етс квадратным фильтром h(x), заданным
уравнением
,
где (|x|?R).
26. Способ по п.25, в котором размер маски пр моугольного фильтра равен 2 пиксел на 2 пиксел .
Страница: 17
RU 2 335 808 C2
Страница: 18
DR
RU 2 335 808 C2
Страница: 19
RU 2 335 808 C2
Страница: 20
RU 2 335 808 C2
Страница: 21
RU 2 335 808 C2
Страница: 22
RU 2 335 808 C2
Страница: 23
RU 2 335 808 C2
Страница: 24
RU 2 335 808 C2
Страница: 25
RU 2 335 808 C2
Страница: 26
?изовать
аппаратными средствами, программными средствами, встроенными программными
средствами или с помощью комбинации перечисленных средств. Например, различные
варианты осуществлени изобретени можно реализовать с помощью функциональных
модулей, которые выполн ют операции способа сглаживани . Каждый из модулей можно
выполнить на аналоговых или цифровых электронных схемах. Специалистам в данной
области техники очевидно, однако, что модули можно также выполнить на
программируемых электронных схемах, запрограммированных исполн емыми командами
такого типа, которые примен ютс в обычных программируемых вычислительных
устройствах.
В частности, описание систем сглаживани в соответствии с различными вариантами
осуществлени изобретени можно дать в общей св зи с машиноисполн емыми
командами, например программными модул ми, исполн емыми одним или несколькими
программируемыми вычислительными устройствами. Обычно программные модули могут
содержать алгоритмы, программы, объекты, компоненты, структуры данных и т.д., которые
выполн ют конкретные задачи или реализуют конкретные абстрактные типы данных.
Обычно функции программных модулей можно сочетать или распредел ть в соответствии
с потребностью различных вариантов осуществлени .
Поскольку различные варианты осуществлени изобретени можно реализовать с
помощью программируемых вычислительных устройств, запрограммированных
соответствующим программным обеспечением, то дл более пон тного изложени изобретени , возможно, полезно дать краткое описание компонентов и принципа действи типичного программируемого вычислительного устройства (далее называемого просто
компьютером), в котором можно реализовать различные варианты осуществлени изобретени . На фиг.4 приведен пример вычислительного устройства 401,
обеспечивающего подход щую операционную среду, в которой можно реализовать
различные варианты осуществлени изобретени . Данна операционна среда вл етс всего лишь примером подход щей операционной среды и не может подразумевать никаких
ограничений в отношении объема применени и функциональных возможностей
изобретени . Другими общеизвестными вычислительными системами, средами и/или
Страница: 7
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
конфигураци ми, которые можно применить с насто щим изобретением, вл ютс , без
ограничени , персональные компьютеры, компьютеры-серверы, карманные и портативные
компьютеры, микропроцессорные системы, системы на базе микропроцессоров,
программируема бытова электронна аппаратура, сети персональных компьютеров,
миникомпьютеры, универсальные компьютеры, распределенные вычислительные среды,
которые содержат любые из вышеупом нутых систем или устройств, и т.п.
Вычислительное устройство 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 вывода дл вывода данных дл пользовател , например, на дисплей, громкоговоритель, принтер или тактильное
Страница: 8
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
устройство с обратной св зью. Например, устройство вывода 417 может содержать ЭЛТдисплей, плазменный дисплей, жидкокристаллический дисплей, дисплей на органическом
соединении или дисплей любого другого типа. Специалистам в данной области техники
очевидно, что дисплей каждого из упом нутых типов будет визуализировать изображени посредством активации дискретных элементов изображени . Другими компонентами
вычислительного устройства 401 могут быть каналы 419 св зи с другими устройствами,
компьютерами, сет ми и т.д. на основе либо проводных, либо беспроводных сред св зи.
Специалистам в данной области техники очевидно, что каналы 419 св зи вл ютс примером среды передачи данных. Все данные устройства и каналы общеизвестны в
рассматриваемой области техники и потому не рассмотрены подробно в данном описании.
Средства сглаживани Фиг.5 демонстрирует средство 501 сглаживани дл реализации способа сглаживани в
соответствии с различными вариантами осуществлени изобретени . Средство 501
сглаживани содержит хранилище 503 исходных образов, модуль 505 растрировани ,
буферный накопитель 507 и модуль 509 вычислени пр молинейных отрезков. Как следует
из нижеприведенного описани , хранилище 503 исходных образов содержит исходные
образы, подлежащие визуализации с использованием способа сглаживани в соответствии
с данным вариантом осуществлени изобретени . Исходные образы можно хранить в
любой подход щей форме, например в форме, по меньшей мере, одного математического
уравнени , описывающего подлежащую визуализации область, кривую или линию.
Например, если способ сглаживани используют дл визуализации пр мой линии, то
исходным образом может быть уравнение у=mx+с, где m обозначает наклон пр мой, а с
обозначает смещение пр мой.
Специалистам в данной области техники очевидно, что исходные образы могут
представл ть линию, кривую или область. Если исходный образ представл ет большую
область (например, область с шириной больше диаметра сглаживающей маски
фильтрации, используемой дл сглаживани области), то сглаживать потребуетс только
кра области. В частности, если образ представл ет большую область, то сглаживать
требуетс только те характерные признаки области, которые расположены по кра м
области. Следовательно, чтобы отличить область от соседних линий, кривых и областей,
необходимо четко визуализировать только кра большой области. Остальную часть
области, наход щуюс за пределами охватывающего диаметра сглаживающей маски
фильтрации, можно быстро и эффективно визуализировать непосредственно по исходному
образу, не подверга его сглаживающей фильтрации.
В соответствии с вышеизложенным, если исходный образ представл ет большую
область, то модуль 505 растрировани формирует исходное значение пиксел дл каждого
пиксел диспле . В частности, модуль 505 растрировани примен ет операцию
растрировани дл формировани исходных значений пикселей, соответствующих области,
определ емой исходным образом. Операци растрировани может быть, например,
операцией двухуровневого растрировани . Операци двухуровневого растрировани присваивает пикселю первое значение, если центр пиксел находитс внутри упом нутой
области, и присваивает пикселю второе значение, если центр пиксел находитс снаружи
области.
Следовательно, если область представл ет собой сплошную черную площадку, а
черный пиксель имеет значение, обозначаемое "1", то пиксел м с центрами внутри этой
области будет присвоено значение "1", а пиксел м с центрами снаружи области будет
присвоено значение "0". Однако следует отметить, что некоторые варианты осуществлени изобретени можно применить к пиксел м, у которых имеетс диапазон изменени значений, чтобы осуществл ть визуализацию в многоцветном или полутоновом режиме. В
таких вариантах осуществлени изобретени двухуровневое растрирование может
состо ть в том, что пиксел м с центрами внутри области будет присваиватьс любое
подход щее значение, соответствующее цвету или оттенку серого. Данные пиксел ,
сформированные модулем 505 растрировани , сохран ютс в буферном накопителе 507.
Страница: 9
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
Однако если исходный образ представл ет небольшую область либо линию, или кривую
небольшой толщины (т.е. линию или кривую с толщиной меньше диаметра сглаживающей
маски фильтрации), то работу модул 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
растрировани выполн ет операцию двухуровневого растрировани на исходном образе.
Например, если исходный образ описывает шрифт или многоугольник большой толщины,
Страница: 10
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
то модуль 505 растрировани примен ет операцию двухуровневого растрировани к
исходному образу. Модуль 505 растрировани присваивает первое значение таким
пиксел м, центры которых наход тс внутри кривой, линии или области, описанной
исходным образом, и присваивает второе значение таким пиксел м, центры которых
наход тс снаружи кривой, линии или области.
Например, если образ описывает многоугольную область сплошного черного тона, то
модуль 505 растрировани может присвоить значение "1" (т.е. самое глубокое темное
значение пиксел ) пиксел м с центрами внутри области и присвоить значение "0" (т.е.
самое светлое значение пиксел ) остальным пиксел м. Однако в других вариантах
осуществлени изобретени модуль 505 растрировани может присваивать другие
значени пиксел м с центром внутри области и пиксел м с центром снаружи области.
Например, если пиксель может представл ть разные цвета, то пиксел м с центрами внутри
области модуль 505 растрировани может присваивать значение, соответствующее цвету
области. Следовательно, в процессе операции двухуровневого растрировани модуль 505
растрировани формирует дл пикселей значени , соответствующие общей форме
больших линий, кривых и областей, отображаемых исходными образами.
В показанном варианте осуществлени ширина маски сглаживающего фильтра
приблизительно равна двум пиксел м. Например, если в сглаживающем фильтре
примен етс пр моугольна маска, то маска может покрывать площадку размером 2Ч2
пиксел . Если сглаживающий фильтр вл етс фигурой вращени , то радиус маски может
быть равен 1 пикселю. Указанные фильтры требуют обработки меньшего числа деталей
при свертке, чем фильтры большего размера, и позвол ют точно вычисл ть
соответствующие интегралы, что упрощает вычисление свертки. Однако во многих других
вариантах осуществлени изобретени могут примен тьс маски с меньшей или большей
площадью. Кроме того, в различных вариантах осуществлени изобретени можно
использовать как положительные, так и отрицательные лепестки.
После записи растрированного образа в буферный накопитель 507 на этапе 607
выполн етс фильтраци контуров линии, кривой или области, описанных исходным
образом. В частности, на этапе 609 модуль 511 свертки выполн ет обход пр молинейных
отрезков, сформированных модулем 509 вычислени пр молинейных отрезков, с целью
свертки контуров приближенного образа с заданной функцией фильтрации.
Следовательно, модуль 511 свертки выполн ет обход пр молинейных отрезков
приближенного образа, чтобы проинтегрировать область, ограниченную маской
фильтрации и пр молинейными отрезками, с функцией фильтрации. В некоторых
вариантах осуществлени изобретени значени свертки определ ютс поиском
предварительно вычисленных значений свертки в справочной таблице 513. Однако в
других вариантах осуществлени изобретени , значени свертки могут определ тьс вычислением свертки в реальном времени.
На этапе 611 фильтрованный образ вводитс в буферный накопитель 507 вместе с
растрированным образом. Затем фильтрованный образ и растрированный образ можно
визуализировать на этапе 613. В некоторых вариантах осуществлени изобретени фильтрованные и растрированные образы можно визуализировать группами,
соответствующими пр молинейным отрезкам, сформированным модулем 509 вычислени пр молинейных отрезков, чтобы последовательно осуществл ть визуализацию кривой,
линии или области. Однако в других вариантах осуществлени изобретени фильтрованный образ можно визуализировать в реальном времени, параллельно
фильтрации приближенного образа.
В соответствии с вышеизложенным дл приближенного образа, контуры которого
сформированы пр молинейными отрезками, свертку с функцией фильтрации вычислить
намного проще, чем дл исходного образа. Однако в некоторых случа х маска свертки
может охватывать, по меньшей мере, две вершины между разными пр молинейными
отрезками. В указанных случа х задача вычислени интеграла дл описанной зоны и,
следовательно, свертки может осложн тьс . В соответствии с вышеизложенным в
Страница: 11
RU 2 335 808 C2
5
10
15
20
25
30
35
40
45
50
различных вариантах осуществлени изобретени , чтобы получить свертку дл зон,
содержащих, по меньшей мере, две вершины пр молинейных отрезков, эти зоны дел т на
зоны меньшего размера, более удобные дл вычислений. Во-первых, зона с несколькими
вершинами делитс лини ми, исход щими из центра маски свертки и проход щими через
каждую вершину. Например, на фиг.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. В другой м?
Документ
Категория
Без категории
Просмотров
1
Размер файла
755 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа