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

Все приведённые отрывки кода, если явно не указано обратное, находятся в общем доступе.

Шумы находят широкое применение в разработке игр.
Примерами их использования являются:

1-мерные: звуковые эффекты и анимация хаотичных процессов (напр. дрожание камеры при взрывах)

2-мерные: текстуры, карты нормалей, ландшафт.

3-мерные: объёмные текстуры (которые дают возможность использовать пространственные координаты в качестве текстурных, в т. ч. и для динамических моделей), анимированные текстуры (3-я координата используется как время)

4-мерные: анимированные объёмные текстуры.

Рис. 1 . elevated by Rgba & TBC , 4k demo. Ландшафт и текстура сгенерированы с использованием процедурного шума.

Определения

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

(https://ru.wikipedia.org/wiki/Шум).

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

Последовательность независимых случайных величин (не обязательно равномерно распределённых) называется также дискретным белым шумом.

В дальнейшем в статье под случайными числами будут чаще всего пониматься, без явного указания на это, псевдослучайные числа, т. е. генерируемые детерминированным образом, но "выглядящие" как случайные, в частности с т. з. некоторого набора статистических тестов.
https://ru.wikipedia.org/wiki/Псевдослучайная_последовательность
https://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел

Источники шума

В программировании часто встречаются 2 объекта, связанных с генерацией шума:

1. Генератор случайных чисел (ГСЧ (англ. RNG - random number generator), или ГПСЧ - генератор псевдослучайных чисел; в данной статье под ГСЧ подразумевается именно ГПСЧ). При вызове ГСЧ выдаёт следующий элемент в последовательности (псевдо)случайных чисел.

2. Шумовая функция (англ. Noise function). Чистая функция, которая аргументу сопоставляет результат, ведущий себя, в некотором смысле, как шум. Аргумент может быть как дискретным, так и непрерывным, одно- или многомерным.
Для непрерывного случая чаще всего нас интересует когерентная шумовая функция:

Coherent noise is generated by a coherent-noise function, which has three important properties:
Passing in the same input value will always return the same output value.
A small change in the input value will produce a small change in the output value.
A large change in the input value will produce a random change in the output value.

An n-dimensional coherent-noise function requires an n-dimensional input value. Its output value is always a scalar.

Примером ГСЧ является функция rand стандартной библиотеки C. Для многих целей данная конкретная функция является неудачной, т. к. её состояние (определяющее следующий элемент) - невидимая глобальная переменная. Соответственно несколько использующих её подсистем будут влиять друг на друга.
Более удобными в этом смысле являются объекты генераторов, которые хранят своё состояние, например генераторы, определённые в заголовочном файле стандартной библиотеки C++ ( присутствует в стандартной библиотеке начиная с C++11).

Шумовую функцию от дискретного аргумента концептуально можно реализовать через ГСЧ, отбросив соответствующее количество начальных значений, например так:

float noise(int i) { std::minstd_rand rng(0); // Initialize RNG with the internal state of 0. rng.discard((unsigned long long)i); // Advance the internal state by i steps. return std::uniform_real_distribution(0.0f,1.0f)(rng); }

Но с практической точки зрения это не очень удачный код, т. к. вычисления слишком медленны, причём время работы зависит от аргумента.
Примечание : теоретически, n-й результат LCG (реализованного в minstd_rand) может быть вычислен за O(log n) действий (что, впрочем, тоже медленно), но ни одна из тестированных реализаций стандартной библиотеки этого не делала.

Поэтому обычно шумовые функции вычисляют с помощью явных формул.

Шумовыми функциями часто удобно оперировать на концептуальном уровне (т. к. они являются функциями в обычном математическом смысле ("чистыми функциями" в программистской терминологии), и манипуляции с ними можно проводить по обычным правилам). Для практических целей во многих случаях достаточно прямого использования ГСЧ для получения последовательных значений, т. е. лёгкое получение значения по аргументу (а иногда и вообще повторяемость) не требуется. Использование ГСЧ в подобных случаях может оказаться более эффективным.

"Цвета" шума

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

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

https://ru.wikipedia.org/wiki/Белый_шум
Назван он так по аналогии с белым светом, также содержащим цвета всех частот (оптического диапазона).
Непрерывный идеальный белый шум (для которого два значения нескоррелированы, если они не одновременны) физически некорректен, т. к. имеет бесконечную мощность. Для дискретного белого шума эта проблема отсутствует.

Также по аналогии с оптикой вводят розовый (с преобладанием низких частот) и синий (с преобладанием высоких частот). Часто используют более узкие определения: красным, розовым, синим и фиолетовым называют шумы со спектральными мощностями, зависящими от частоты как 1/f^2, 1/f, f, f^2 соответственно.
См. https://ru.wikipedia.org/wiki/Цвета_шума .

Одним из методов получения дискретного шума с заданными спектральными характеристиками является перемножение спектра дискретного белого шума и заданной спектральной огибающей (Fourier Spectral Synthesis):
Пусть - дискретный белый шум. Тогда шум с огибающей (в частотном пространстве) можно получить как

что выглядит как

где

Пример :

Рис. 2 . Слева направо - белый шум, его Фурье-образ (зелёным обозначена действительная часть, синим - мнимая), фильтр в частотном пространстве, действительная часть от обратного преобразования Фурье от произведения Фурье-образа белого шума и фильтра. Эффект затенения вызван асимметричностью фильтра (его величина близка к 0 для отрицательных частот).

Примечание : для дискретного случая может быть практичнее использование дискретного косинусного преобразования (англ. discrete cosine transform (DCT)).

Этот метод естественно обобщается на большее количество измерений.
В силу существования быстрого преобразования Фурье этот подход в некоторых случаях практичен по времени.

Примечание : Для дискретного белого шума с гауссовым распределением значений, его Фурье-преобразованием является также дискретный белый шум с гауссовым распределением значений (в частотном пространстве).

Примеры использования розового шума (в широком смысле слова) встречаются далее в статье.
Синий шум часто применяют в ситуациях, когда нужно получить случайно выглядящую регулярную структуру, а белый шум кажется слишком кластеризованным. Примеры: Poisson disk (http://devmag.org.za/2009/05/03/poisson-disk-sampling/ , https://www.jasondavies.com/poisson-disc/), random dithering и другие.

Категории процедурного шума

За обзором разных методов генерации процедурного шума читатель отсылается к
http://physbam.stanford.edu/cs448x/old/Procedural_Noise%282f%29Categories.html а также замечательной статье State of the Art in Procedural Noise Functions
Далее приводится сжатое изложение некоторых из них.

Один метод - Fourier Spectral Synthesis уже был рассмотрен выше.

Шумы на решётке (Lattice Noises) являются, возможно, наиболее популярными. В них задаются случайные значения в узлах решётки, исходя из которых находится значения в произвольных точках (т. е. строится непрерывная шумовая функция). Их наиболее известные классы:
1. Численный шум (value noise) - в каждом узле решётки задаётся (детерминированным образом) псевдослучайное число. Значением шумовой функции является интерполяция (чаще всего линейная или кубическая) между значениями в углах ячейки, куда попадает аргумент.

Рис. 3 . Двумерный численный шум. Слева - одна октава (с билинейной интерполяцией), справа - сумма 5 октав (с билинейной интерполяцией, и коэффициентом 0.73).

2. Градиентный шум (gradient noise) - в каждом узле решётки задаётся (детерминированным образом) псевдослучайный вектор (называемый градиентом). Значение шумовой функции получается исходя из значений в углах ячейки и направлений на эти узлы. Наиболее известным представителем является шум Перлина.

Рис. 4 . Двумерный срез трёхмерного шума Перлина.

Рис. 5 . Plasma fractal, сгенерированный Diamond-square algorithm.

Рис. 7 . Gabor Noise.

Рис. 8 . Примеры из Gabor Noise by Example .

Существуют разные способы генерации набора точек для шума Уорли. Jittered grid (регулярная сетка с детерминированным образом определённым случайным смещением вершин) является довольно популярной, но приводит к анизотропии. Уорли в статье использовал метод с разбиением пространства на кубы и генерации для куба случайных точек количеством, определяемым распределением Пуассона; метод похож на приведённый в подпункте Sparse Convolution Noise (см. ниже).

Рис. 9 . Ячеистая текстура (cellular texture).

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

Коэффициент носит разные названия. Библиотека libnoise использует термин Persistence, как и , где упоминается, что термин persistence в отношении шума был введён Бенуа Мандельбротом с обратным смыслом (т. е. ).
Коэффициент в libnoise назван Lacunarity, и в большинстве случаев выбирается равным 2.
См. .
Коэффициент чаще всего выбирают в диапазоне , хотя это и не обязательно.
Примечание : для случая ряд сходится для бесконечного количества октав, и каждая новая вносит всё меньшую поправку. Это не обязательно справедливо для производных, см. функцию Вейерштрасса .
Такой метод даёт розовый шум, который находит много применений.
Этот подход часто называют фрактальным броуновским движением (fractal Brownian motion) или сокращённо, fBm, даже в случаях когда он, строго говоря, не соответствует определению fBm.

Стационарным белым шумом называют стационарную случайную функцию Х (t ), спектральная плотность которой постоянна:

s x (ω )=s=const .

Найдем корреляционную функцию белого шума. Используя формулу (**) (см. § 3)

Приняв во внимание, что [см. § 6, соотношение (*)]

окончательно имеем

(**)

Таким образом, корреляционная функция стационарного белого шума пропорциональна дельта-функции; коэффициент пропорциональности 2πs называют интенсивностью стационарного белого шума .

Дельта-функция равна нулю при всех значениях τ≠0, поэтому и корреляционная функция k x (τ ) также равна нулю при этих же значениях τ [это видно из формулы (**)]. Равенство же нулю корреляционной функции стационарного белого шума означает некоррелированность любых двух его сечений-случайных величин Х (t 1) и Х (t 2 )(t 1 ≠t 2). Благодаря этой особенности белый шум находит широкое применение в теории случайных функций и ее приложениях. Однако эта же особенность указывает на то, что осуществить белый шум невозможно, так как в действительности при очень близких значениях t 1 и t 2 соответствующие случайные величины Х (t 1) и Х (t 2) в известной степени коррелированы.

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

Пример. Спектральная плотность стационарной случайной функции Х (t ) постоянна в диапазоне частот (- ω 0 , ω 0). а вне его равна нулю:

Найти: а) корреляционную функцию; б) дисперсию случайнойфункцииХ (t ).

Решение, а) Найдем искомую корреляционную функцию:

Итак,

б) Найдем искомую дисперсию:

D x =2s ω 0 .

§ 8. Преобразование стационарной случайной функции стационарной линейной динамической системой

Стационарной линейной динамической системой называют устройство, которое описывается линейным дифференциальным уравнением с постоянными коэффициентами вида

где Х (t )- входная стационарная случайная функция (воздействие, возмущение), Y (t )- выходная случайная функция (реакция, отклик).

Если динамическая система устойчива, то при достаточно больших значениях t , т. е. по окончании переходного процесса, функцию Y (t ) можно считать стационарной. Подчеркнем, что при дальнейшем изложении предполагается, что X (t ) и Y (t )- стационарные случайные функции.

Поставим перед собой задачу найти характеристики выходной функции по известным характеристикам входной функции.

Найдем математическое ожидание т y , зная т x , для чего приравняем математические ожидания левой и правой частей уравнения (*). Учитывая, что Х (t ) и Y (t )- стационарные случайные функции, а значит, математические ожидания производных этих функций равны нулю, получим

a n m y = b m m x

Отсюда искомое математическое ожидание

m y = b m m x / a n (**)

Пример 1. На вход линейной динамической системы, описываемой уравнением

Y ’(t )+2Y (t )=5X ’(t )+6X (t ).

Х (t ) с математическим ожиданием т x = 10. Найти математическое ожидание случайной функции Y (t ) на выходе системы в установившемся режиме (после затухания переходного процесса).

Решение. Используя формулу (**), получим

m y = b m m x / a n =(6/2)10=30.

Введем понятия передаточной функции и частотной характеристики, которые понадобятся далее. Предварительно запишем уравнение (*) в операторной форме, обозначив оператор дифференцирования черезр , - через р 2 и т. д. В итоге уравнение (*) примет вид

(a 0 p n +a 1 p n-l + ...+a n )Y (t )= (b 0 p m +b 1 p m-l + ...+b m )X (t ). (***)

«Решим»это уравнение относительно Y (t ):

(****)

Передаточной функцией линейной динамической системы называют отношение многочлена относительно р при Х (t ) к многочлену при Y (t ) в операторном уравнении (***):

Из соотношения (****) следует, что выходная и входная функции связаны равенством

Y (t )= Ф(р )Х (t ).

Частотной характеристикой линейной динамической системы называют функцию, которая получается заменой аргумента р в передаточной функции на аргумент i ω (ω -действительное число):

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

s y (ω )=s x (ω )|Ф(i ω )| 2 .

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

Зная же спектральную плотность выходной функции, можно найти ее корреляционную функцию [§ 3, формула (**)]:

а следовательно, и дисперсию:

Пример 2. На вход линейной стационарной динамической системы, описываемой уравнением

3Y ’(t )+Y (t )=4X "(t )+X(t ),

подается стационарная случайная функция Х (t ) с корреляционной функцией k x (τ)= 6e - τ . Найти дисперсию случайной функции Y (t ) на выходе системы в установившемся режиме.

Решение 1. Найдем спектральную плотность выходной функции. Используя решение примера 2 (см. § 4) при D =6 и α=2, получим

2. Найдем передаточную функцию, длячего напишем заданное уравнение в операторной форме:

(3р +1)Y(t )=(4р +1)Х (t ).

Следовательно, передаточная функция

3. Найдем частотную характеристику, для чего заменим в передаточной функции аргумент р на i ω ):

4. Найдем спектральную плотность выходной функции, длячегоумножим спектральную плотность входной функции на квадрат модуля частотной характеристики:

5. Найдем искомую дисперсию:

Представим подынтегральную функцию в виде суммы простейших дробей:

Выполнив интегрирование, получим искомую дисперсию:

D у = 96,4.

Задачи

1. Найти дисперсию стационарной случайной функции X (t ), зная ее спектральную плотность

Отв . D x = 6.

2. Найти спектральную плотность стационарнойслучайнойфункции Х (t ), знаяее корреляционную функцию

Отв .

3. Найти спектральную плотность стационарной случайной функции Х (t ), зная ее корреляционную функцию k x (τ)=5e -2| τ |.

Отв . s x (ω ) = 10/(π (4 + ω 2)).

4. Задана спектральная плотность s x (ω )=6/(π (1+ω 2)) стационарной случайной функции Х (t ). Найти нормированную спектральную плотность.

Отв . s x норм (ω )=1/(π (1 – ω 2)).

5. Найти корреляционную функцию стационарной случайной функции Х (t ), зная ее спектральную плотность

Отв .

6. Спектральная плотность стационарной случайной функции X (t ) постоянна в диапазоне частот (ω 1 ,ω 2), а вне его равна нулю:

Найти: а) корреляционную функцию; б) дисперсию; в) нормированную корреляционную функцию случайной функции Х (t ).

Отв . а)
, б)D x =s (ω 2 - ω 1 ) ,в)ρ x (τ )=

7. На вход линейной стационарной динамической системы, описываемой уравнением Y " (t )+ 3Y (t )= X " (t )+ 4X (t ), подается стационарная случайная функция Х (t ) с математическим ожиданием m x =6 и корреляционной функцией k x (τ )=5e -2 τ . Найти математическое ожидание и дисперсию случайной функцииY (t ) навыходе системы в установившемся режиме.

Отв . m y =8; D y =22/3.

8. На вход линейной стационарной динамической системы, описываемой уравнением

Y "(t )+ 5Y (t )+6Y (t )=X’(t )+X(t ),

подается стационарная случайная функция X (t ) с математическим ожиданием m х =4 и корреляционной функцией k x (t )=е - τ . Найти математическое ожидание и спектральную плотность случайной функции Y (t

Отв . m y =2/3; s y (ω )=1/.

9. На вход линейной стационарной динамической системы, описываемой уравнением

Y ```(t )+6Y ``(t )+11Y `(t )+6Y (t )=7X ""(t )+5X (t ),

подается стационарная случайная функция Х (t ) с известной корреляционной функцией k x (τ )=2e -| τ | (1+|τ|). Найти спектральную плотность случайной функции Y (t ) на выходе системы в установившемся режиме.

Указание. Разложить на линейные множители знаменатель передаточной функции: р 3 +бр 2 +11р +6=(р +1) (p +2)(p +3).

Отв . s y (ω )=4(49ω 6 +25)/(π(ω 2 +l) 3 (ω 2 +4)(ω 2 +9)).

10. На вход линейной стационарной динамической системы, описываемой уравнением Y " (t )+Y (t )=(t ), поступает случайная функция Х (t ) с постоянной спектральной плотностью S 0 (стационарный белый шум). Найти дисперсию случайной функции Y (t ) на выходе системы в установившемся режиме.

Отв . D =s 0 π .

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального...»

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

Кафедра информационных радиосистем

Функциональное моделирование радиосистем

Методические указания к лабораторным работам

для студентов специальности 210302 «Радиотехника» и 210601 «Радиоэлектронные системы и комплексы», а также по направлению 210400«Радиотехника»

всех форм обучения Часть 3 Нижний Новгород 2011 Составитель: А.В.Мякиньков УДК 621.325.5-181.4 Функциональное моделирование радиосистем: Метод. указания к лабораторным работам для студентов специальности 210302 «Радиотехника» и 210601 «Радиоэлектронные системы и комплексы», а также по направлению 210400«Радиотехника» всех форм обучения. Часть 3 / НГТУ; Сост.:

А.В.Мякиньков. Н.Новгород, 2011. - 16 с.

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

Научный редактор А.Г.Рындык Редактор Э.Б.Абросимова Подписано к печати _______. Формат 60 84 1/16.

Бумага газетная. Печать офсетная. Печ. л. 1,0.

Уч.-изд. л. ____. Тираж 200 экз. Заказ____.

Нижегородский государственный технический университет.

Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

© Нижегородский государственный технический университет, 2011

ОБЩИЕ ЗАМЕЧАНИЯ

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

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

1. О МОДЕЛИ БЕЛОГО ГАУССОВСКОГО ШУМА И ДИСКРЕТНОГО

БЕЛОГО ГАУССОВСКОГО ШУМА

Как известно, модель белого шума представляет собой математическую абстракцию в виде процесса, спектр которого на всех частотах равномерный и равен некоторой константе N0/2, а корреляционная функция представляет собой дельта-функцию с весом, который определяется указанной константой. Таким образом, белый шум имеет бесконечную дисперсию (мощность). Любой реальный процесс имеет конечную мощность, а, следовательно, его спектральная плотность мощности (СПМ) может быть только спадающей интегрируемой функцией частоты. Однако модель белого шума используется, если ширина спектра шума много больше, чем ширина полосы пропускания некоторого частотноизбирательного устройства.

Рассмотрим теперь модель дискретного белого гауссовского шума (ДБГШ).

Дискретный белый шум, в отличие от белого шума, имеет конечную мощность.

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

–  –  –

На рис.1 обозначено: МШУ – малошумящий усилитель, ПФ – полосовой фильтр, ФНЧ – фильтр нижних частот, АЦП – аналого-цифровой преобразователь, ГОС – генератор опорной частоты, ЦОС – блок цифровой обработки сигналов. Предположим, что собственный шум антенны и усилителя много больше ширины полосы пропускания ПФ, а амплитудно-частотные характеристики ПФ и ФНЧ идеально прямоугольные. На рис.2 показаны СПМ процессов в точках 1, 2, 3 и 4, а также корреляционная функция процесса в точке 4 (рис.1).

–  –  –

Задание: построить корреляционную функцию СП на выходе фильтра с заданной ИХ. Найти дисперсию и МО процесса на выходе фильтра в установившемся режиме при заданных МО и дисперсии на входе. Построить графики зависимости МО и дисперсии процесса на выходе фильтра, если при нулевых начальных условиях в момент времени t0 на входе начинает действовать реализация БГШ с заданными параметрами. Найти нормированный коэффициент взаимной корреляции значений процесса на выходе фильтра, взятых через заданный интервал времени.

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

–  –  –

Как известно , дисперсия процесса на выходе линейного фильтра при воздействии на входе белого шума со спектральной плотностью мощности N0/2 в установившемся стационарном режиме определяется из выражения N0 2 = Eh, (3) где Eh – энергия ИХ. Таким образом, корреляционная функция процесса на выходе фильтра по форме совпадает с автокорреляционной функцией ИХ фильтра и имеет максимум, определяемый величиной (3). На рис.4 показаны графики зависимости математического ожидания (МО) и дисперсии процесса на выходе фильтра от времени, построенные в предположении, что в нулевой момент времени на вход фильтра с нулевыми начальными условиями подали реализацию белого шума с МО m1 и СПМ N0/2.

–  –  –

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

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

–  –  –

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

Найдем также нормированный коэффициент взаимной корреляции между сечениями выходного процесса, взятыми через интервал времени t0. Пусть для определенности t0 = 0.35h. Нормированная корреляционная функция процесса на выходе фильтра получается нормированием корреляционной функции к дисперсии, и при нулевом временном сдвиге равна единице. Коэффициент взаимной корреляции сечений стационарного процесса tn и tk, взятых через интервал времени t0, равен значению нормированной корреляционной функции процесса при аргументе, равном этому сдвигу: rnk = r(t0). В нашем примере, с учетом треугольной формы корреляционной функции выходного процесса r(t0) = r(0.35h) = 1 – 0.35 = 0.75.

Рассмотрим процесс на выходе дискретного формирующего фильтра c прямоугольной ИХ, на входе которого действует ДБГШ. Вид ИХ фильтра и корреляционной функции выходного процесса показаны на рис.6.

–  –  –

Отметим, что сумма коэффициентов фильтра определяет коэффициент передачи на нулевой частоте, т.е. коэффициент передачи постоянной составляющей. В переходном режиме, длительность которого определяется длительностью ИХ, имеем неполную сумму k взвешенных отсчетов, поэтому МО в k-й момент k времени равно m 2 (k) = m1 h[n]. Поскольку в рассматриваемом примере все n =0 коэффициенты фильтра равны, то переходный процесс изменения МО имеет линейный характер.

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

z 1 z 1 z 1 x[n]

–  –  –

закон изменения дисперсии выходного процесса также имеет линейный характер.

Задание: рассчитать цифровой нерекурсивный фильтр для формирования реализации гауссовского процесса с заданной корреляционной функцией или заданной СПМ. Обеспечить нормирование мощности процесса на выходе фильтра к мощности процесса на входе.

В качестве примера рассмотрим проектирование формирующего фильтра для моделирования случайного процесса со спектральной плотностью мощности вида:

() W () = exp a2, (5) где a – параметр.

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

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

Поскольку функция (5) четная, то для вычисления действительной ИХ фильтра достаточно лишь вычислить ее действительный амплитудный спектр как квадратный корень функции (5) и взять обратное преобразование Фурье.

Используя таблицу преобразований Фурье, получаем, что автокорреляционная функция ИХ, будет иметь вид

–  –  –

() h(t) = a exp 2bt 2. (7) Функцию (7) будем рассматривать как ИХ аналогового фильтра-прототипа.

Параметр b в выражениях (6) и (7) определяет ширину корреляционной функции моделируемого процесса и, следовательно, ширину спектра процесса. Можно показать, что величина (1 – b) приближенно определяет коэффициент корреляции двух соседних отсчетов процесса. Для получения отсчетов ИХ цифрового формирующего фильтра можно воспользоваться различными способами. В описан способ вычисления коэффициентов фильтра методом разложения СПМ в ряд Фурье. Практически, этот способ сводится к методу частотного окна, который при практической реализации заключается в дискретизации отсчетов желаемой амплитудной характеристики и вычислению обратного дискретного преобразования Фурье (или, в частном случае четной функции, дискретного косинусного преобразования). При этом возможно последующее взвешивание ИХ весовым окном для уменьшения выбросов частотной характеристики полученного цифрового фильтра, которые вызваны влиянием так называемого эффекта Гиббса . Другим распространенным способом проектирования является метод окна во временной области. Этот метод оказывается еще более простым и удобным при проектировании нерекурсивных фильтров в случае, если известно аналитическое выражение для ИХ аналогового фильтра-прототипа. Метод сводится к взвешиванию ИХ фильтра-прототипа весовым окном ограниченной длительности и последующей дискретизацией в пределах этого окна. В рассматриваемом примере, используя описанный подход, получаем отсчеты ИХ цифрового нерекурсивного формирующего фильтра в виде () exp(n 2), где = 2bt2. Величина интервала h(n) = exp 2b(nt) = a a дискретизации t выбирается в соответствии с шириной полосы моделируемого процесса. Число коэффициентов фильтра выбирается исходя из требований точности аппроксимации требуемой частотной характеристики. Очевидно, что длительность окна должна быть выбрана таким образом, чтобы на краю окна значения ИХ были пренебрежимо малы. После получения вектора коэффициентов цифрового фильтра необходимо вычислить его частотную характеристику, а также квадрат модуля частотной характеристики и оценить точность аппроксимации заданной СПМ выходного процесса полученной функцией.

a Амплитудный множитель в (7) не имеет принципиального значения.

Однако по заданию нам необходимо выполнить условие нормирования мощности выходного процесса к мощности входного процесса. Это означает, что мощность (дисперсия) процесса на выходе фильтра должна быть равна мощности процесса на входе. Как было показано выше (см. пример 2.1), дисперсия процесса на N 1 выходе фильтра равна 2 = 1 h [ n]. Отсюда следует, что для обеспечения

–  –  –

Следует отметить, что рассмотренный пример является важным с точки зрения теории борьбы с пассивными помехами в радиолокации, где корреляционная функция вида (3) описывает свойства гауссовской пассивной помехи при дискретных значениях временного сдвига = nTП, где TП – период повторения импульсов. В этом случае величина R(TП) / 2 представляет собой коэффициент череспериодной корреляции пассивной помехи в импульсной радиолокационной системе.

Данный пример иллюстрирует модель другого важного частного случая пассивной помехи в радиолокации, а именно экспоненциальной помехи. Для расчета коэффициентов рекурсивного формирующего фильтра по заданной корреляционной функции процесса на выходе можно воспользоваться методом факторизации системной функции фильтра . Как известно , системная функция K(z) рекурсивного линейного фильтра с постоянными параметрами может быть представлена в виде N 1

–  –  –

Как следует из (16), коэффициент обратной связи b1 = = exp() равен коэффициенту корреляции двух соседних отсчетов процесса [n] на выходе фильтра. В соответствии с заданием, моделирование процесса с заданным коэффициентом корреляции между соседними отсчетами выходного процесса сводится к заданию соответствующего коэффициента обратной связи в схеме на рис.9.

–  –  –

Задачу предлагается решить самостоятельно.

Задание: на рис.11 показана функциональная схема, состоящая из генератора ДБГШ, цифрового фильтра нижних частот с ИХ, изображенной на том же рисунке, линий задержки на интервалы времени, равные длительности ИХ фильтра и половине этой длительности, сумматора, взаимно-корреляционного устройства, устройств оценивания среднеквадратических отклонений, а также устройств умножения и деления. Частота дискретизации в системе равна fS = 100 Гц, уровень СПМ ДБГШ равен N0/2 = 10-2 Дж/Гц. Число отсчетов ИХ фильтра N =

16. Необходимо найти дисперсию процесса в точках 1, 2 и 3 схемы, а также истинное значение параметра, оценка которого вычисляется в точке 4 схемы.

Оценка какого параметра вычисляется в точке 4?

–  –  –

СПИСОК ЛИТЕРАТУРЫ

1. Функциональное моделирование радиосистем: Метод. указания к лабораторным работам для студентов специальности 200700 всех форм обучения/ НГТУ; Сост.: А.В.Мякиньков, Е.Н.Приблудова. Н.Новгород, 2005.с.

2. Функциональное моделирование радиосистем: Метод. указания к лабораторным работам для студентов специальности 210302.65 всех форм обучения. Часть 2 / НГТУ; Сост.: А.В.Мякиньков, А.Б.Бляхман. Н.Новгород, 2006. - 16 с.

3. Информационные технологии в радиотехнических системах: Учебное пособие /

В.А.Васин, И.Б.Власов, Ю.М.Егоров [и др.]; под ред. И.Б. Федорова. – М.:

Издательство МГТУ им. Н.Э. Баумана, 2003. – 672 с.

4. Тихонов, В.И. Статистическая радиотехника / В.И.Тихонов. – М.: Радио и связь, 1982. – 624 с.

5. Горяинов, В.Т. Статистическая радиотехника: примеры и задачи. / В.Т.Горяинов, А.Г.Журавлев, В.В.Тихонов; под ред. В.И.Тихонова. – 2-е изд., перераб. и доп. – М.: Сов. радио, 1980. – 544 с.

6. Сергиенко, А.Б. Цифровая обработка сигналов / А.Б.Сергиенко. – СПб.: Питер, 2003. –

7. Невдяев, Л.М. Телекоммуникационные технологии. Англо-русский толковый словарь-справочник / Л.М.Невдяев; под ред. Ю.М.Горностаева. – Серия изданий «Связь и бизнес», М.: МЦНТИ – международный центр научной и технической информации, ООО «Мобильные коммуникации», 2002. – 592 с.

8. Лезин, Ю.С. Введение в теорию и технику радиотехнических систем / Ю.С.Лезин. – М.: Радио и связь, 1986. – 280 с.

9. Ширман, Я.Д. Теоретические основы радиолокации. Учебное пособие для вузов

А.В. Бойко, В.И. Корнилов Институт теоретической и прикладной механики им. С.А. Христиановича СО РАН, Новосиб...»

«ФГАОУВПО «Казанский (Приволжский) федеральный университет» Е.А.УТКИНА ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ СТАТИСТИКИ В СОЦИОЛОГИИ Казань 2012 Печатается по решению учебно-методической комиссии института математики и механики им.Лобачевского Казанского федерального университета УДК 303.4 Казань: КФУ, Уткина Е.А. Э...»

« виэсх р Ф|БЁ{9 !.€. €требков пРогРАммА вступитшльного эк3Амв,нА в АспиРАнтуРу по спшциАльности Ё...»

«I Всероссийский образовательный семинар по скалолазанию. Доклад. Особенности подготовки спортсменов-скалолазов в лазании на трудность.Подготовил: Гусак И.В. – Старший Тренер сборной Москвы, МС по скалолазани...»

«4. МАТЕМАТИКА, МАТЕМАТИКИ И ОБЩЕСТВО Богатый материал, отражающий новые подходы и умонастроения в философии математики последних лет, содержится в сборнике Математические миры: философские и социологические исследования матем...»

2017 www.сайт - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам , мы в течении 1-2 рабочих дней удалим его.

При исследовании динамики дискретных систем при случайных воздействиях, так же как и непрерывных систем, широко используется понятие „белого" шума. Дискретный во времени „белый" шум математически определяется как такой дискретный случайный процесс, спектральная плотность которого сохраняет постоянное значение на всех частотах:

Корреляционная функция такого процесса

Иначе дискретный во времени «белый» шум определяется как такой дискретный случайный процесс, в котором можно

пренебречь значениями корреляционной функции для Очевидно, что

где - дисперсия дискретного во времени „белого" шума.

Так как в большинстве случаев дискретный случайный процесс получается из соответствующего непрерывного случайного процесса дискретной выборкой, то всегда интересуются связью непрерывного и дискретного „белого" шума. В соответствии с формулой (XIV.92) уровень дискретного во времени „белого" шума равен произведению интервала дискретности на дисперсию дискретного процесса, которая равна дисперсии соответствующего непрерывного процесса. Нетрудно убедиться, что для „белых" шумов установить такую связь невозможно, так как дисперсия математического непрерывного „белого" шума равна бесконечности (см. гл. XIII).

Рис. XIV.16. Определение спектра непрерывного «белого» шума

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

Очевидно, что за уровень непрерывного „белого" шума в этом случае следует принимать значение спектральной плотности входного сигнала на нулевой частоте:

Физический дискретный „белый" шум по отношению к данной дискретной системе определяется как такой дискретный случайный процесс, спектральная плотность которого сохраняет постоянное значение в пределах полосы пропускания дискретной системы (рис. XIV. 17).

В данном случае формула (XIV.83) перепишется в виде

уровень дискретного „белого" шума. Учитывая формулы (XIV.7) и (XIV.4), выражение (XIV.95) можем переписать в виде

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

Рис. XIV.17. Кривые спектральной плотности дискретного входного сигнала и модуля частотной характеристики системы для случая физического дискретного «белого» шума

При графическом вычислении уровня дискретного „белого" шума используют следующую формулу:

Аналитически же это суммирование выполнить достаточно трудно.

При вычислении уровня дискретного „белого" шума, соответствующего непрерывному процессу, также можно применять следующую формулу:

Если известна корреляционная функция непрерывного процесса, то используют формулу

На вход непрерывной системы воздействует случайный процесс, который можно считать по отношению к данной системе „белым" шумом (рис. XIV. 18, а).

Рис. XIV.18. Кривые спектральной плотности входного сигнала и модуля частотной характеристики системы для случаев: а - непрерывные входной сигнал и система; б - дискретный входной сигнал и непрерывная система; в - дискретные входной сигнал и система

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

раньше, так как его кривая спектральной плотности шире, и смещенные кривые будут при более малом перекрываться (рис. XIV. 18, б). В данном случае на вход непрерывной системы воздействует дискретный „белый" шум. При дальнейшем увеличении интервала дискретности начинают перекрываться частотные характеристики системы (рис. XIV. 18, в), тогда входной сигнал и система - дискретны во времени.

• Перевод

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

Я начну с основ использования случайных чисел, а потом перейду к объяснению работы одномерных ландшафтов. Те же концепции работают для 2D (см. демо) и 3D. Попробуйте перемещать ползунок [в оригинале статьи], чтобы посмотреть, как единственный параметр может описывать различные типы шума:

GIF

Из этой статьи вы узнаете:

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

Кроме того, я проведу эксперименты с 2D-шумом, в том числе создам 3D-визуализацию двухмерной карты высот.

1. Почему полезна случайность?

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

Для отличающихся аспектов мы обычно используем генератор случайных чисел. Давайте создадим сверхпростой генератор карт: он будет генерировать линии по 20 блоков, и один из блоков будет содержать сундук с золотом. Давайте опишем несколько карт, которые нам нужны (значком «x» отмечено сокровище):

Карта 1 ........x........... карта 2 ...............x.... карта 3 .x.................. карта 4 ......x............. карта 5 ..............x.....
Заметьте, как много общего в этих картах: они все состоят из блоков, блоки находятся на одной линии, линия имеет длину 20 блоков, есть два типа блоков и ровно один сундук с сокровищем.

Но есть один отличающийся аспект - местонахождение блока. Он может находиться в любой позиции, от 0 (слева) до 19 (справа).

Мы можем использовать случайное число для выбора позиции этого блока. Проще всего будет использовать однородный выбор случайного числа из диапазона от 0 до 19. Это значит, что вероятность выбора любой позиции от 0 до 19 одинакова. В большинстве языков программирования есть функции для однородного генерирования случайных чисел. В Python это функция random.randint(0,19) , но в статье мы будем использовать запись random(0,19) . Вот пример кода на Python:

Def gen(): map = * 20 # создаём пустую карту pos = random.randint(0, 19) # выбираем точку map = 1 # помещаем туда сокровище return map for i in range(5): # создаём 5 разных карт print_chart(i, gen())
Но предположим, что нам нужно, чтобы на картах сундук с большей вероятностью находился слева. Для этого нам нужно неоднородный выбор случайных чисел. Существует много способов реализовать его. Один из них - выбрать случайное число однородным способом, а затем сместить его влево. Например, можно попробовать random(0,19)/2 . Вот код Python для этого:

Def gen(): map = * 20 pos = random.randint(0, 19) // 2 map = 1 return map for i in range(5): print_chart(i, gen())
Но на самом деле я хотел не совсем этого. Я хотел, чтобы сокровища иногда были справа, но более часто слева. Ещё один способ переместить сокровища влево - возвести число в квадрат, сделав что-то вроде sqr(random(0,19))/19 . Если оно равно нулю, то 0 в квадрате, поделённый на 20, равен 0. Если оно равно 19, то 19 в квадрате, поделённое на 19, будет равно 19. Но в промежутке, если число равно 10, то 10 в квадрате, поделённое на 19, равно 5. Мы сохранили диапазон от 0 до 19, но переместили промежуточные числа влево. Такое перераспределение само по себе является очень полезной техникой, в предыдущих проектах я использовал квадраты, квадратные корни и другие функции. (На этом сайте есть стандартные функции изменения формы, применяемые в анимациях. Наведите курсор на функцию, чтобы посмотреть демо.) Вот код Python использования возведения в квадрат:

Def gen(): map = * 20 pos = random.randint(0, 19) pos = int(pos * pos / 19) map = 1 return map for i in range(1, 6): print_chart(i, gen())
Ещё один способ перемещения объектов влево - сначала случайным образом выбрать предел диапазона случайных чисел, затем случайно выбрать число от 0 до предела диапазона. Если предел диапазона равен 19, то мы можем поместить число куда угодно. Если предел диапазона равен 10, то числа можно разместить только в левой части. Вот код Python:

Def gen(): map = * 20 limit = random.randint(0, 19) pos = random.randint(0, limit) map = 1 return map for i in range(5): print_chart(i, gen())
Существует много способов получения однородных случайных чисел и превращения их в неоднородные, имеющие нужные свойства. Как гейм-дизайнер, вы можете выбирать любое распределение случайных чисел. Я написал статью о том, как использовать случайные числа для определения урона в ролевых играх. Там есть разные примеры хитростей.

Подведём итог:

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

2. Что такое шум?

Шум - это серия случайных чисел, обычно расположенных на линии или в сетке.

При переключении на канал без сигнала на старых телевизорах мы видели на экране случайные чёрные и белые точки. Это шум (их открытого космоса!). При настройке на радиоканал без станции мы тоже слышим шум (не уверен, появляется ли он из космоса, или откуда-то ещё).

При обработке сигналов шум обычно является нежелательным аспектом. В шумной комнате сложнее услышать собеседника, чем в тихой. Аудиошум - это случайные числа, выстроенные в линию (1D). На зашумлённом изображении сложнее увидеть рисунок, чем на чётком. Графический шум - это случайные числа, расположенные в сетке (2D). Можно создавать шум в 3D, 4D, и так далее.

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

Давайте рассмотрим простой пример полезности шума. Допустим, у нас есть одномерная карта, которую мы сделали выше, но вместо одного сундука с сокровищем нам нужно создать ландшафт с долинами, холмами и горами. Давайте начнём с использования однородного выбора случайных чисел в каждой точке. Если random(1,3) равно 1, мы будем считать это долиной, если 2 - холмами, если 3 - горами. Я использовал случайные числа для создания карты высот: для каждой точки массива я сохранил высоту ландшафта. Вот код Python для создания ландшафта:

For i in range(5): random.seed(i) # даёт каждый раз одинаковые результаты print_chart(i, ) # примечание: я использую синтаксис генератора списков Python: # output = # это упрощённая запись такого кода: # output = # for x in def: # output.append(abc)
Хм, эти карты выглядят «слишком случайными» для наших целей. Возможно, нам нужны более обширные области долин или холмов, а горы не должны быть такими же частыми, как долины. Ранее мы видели, что однородный выбор случайных чисел нам может не совсем подойти, иногда нам требуется неоднородный выбор. Как решить эту проблему? Можно использовать какой-нибудь случайный выбор, в котором долин появляются чаще, чем горы:

For i in range(5): random.seed(i) print_chart(i, )
Это уменьшает количество гор, но не создаёт никаких интересных рисунков. Проблема такого неоднородного случайного выбора в том, что изменения происходят в каждой точке по отдельности, а нам нужно, чтобы случайный выбор в одной точке как-то был связан со случайными выбора в соседних точках. Это называется когерентностью.

И тут нам пригодятся функции шума. Они дают нам набор случайных чисел вместо одного числа за раз. Здесь нам нужна функция 1D-шума для создания последовательности. Давайте попробуем использовать функцию шума, изменяющую последовательность однородных случайных чисел. Есть разные способы сделать это, но мы используем минимум двух соседних чисел. Если исходный шум равен 1, 5, 2, то минимум (1, 5) равен 1, а минимум (5, 2) равен 2. Поэтому конечный шум будет равен 1, 2. Заметьте, что мы устранили высокую точку (5). Также заметьте, что в получившемся шуме на одно значение меньше по сравнению с исходным. Это значит, что при генерировании 60 случайных чисел на выходе будет только 59. Давайте применим эту функцию к первому набору карт:

Def adjacent_min(noise): output = for i in range(len(noise) - 1): output.append(min(noise[i], noise)) return output for i in range(5): random.seed(i) noise = print_chart(i, adjacent_min(noise))
По сравнению с предыдущими картами здесь получились области долин, холмов или гор. Горы чаще появляются рядом с холмами. И благодаря способу изменения шума (выбор минимума), долины чаще встречаются, чем горы. Если бы мы взяли максимум, то картина была бы противоположной. Если бы мы хотели, чтобы частыми не были ни долины, ни горы, мы выбрали бы вместо минимума или максимума среднее.

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

А давайте попробуем запустить её снова!

Def adjacent_min(noise): # так же как раньше output = for i in range(len(noise) - 1): output.append(min(noise[i], noise)) return output for i in range(5): random.seed(i) noise = print_chart(i, adjacent_min(adjacent_min(noise)))
Теперь карты стали ещё более сглаженными и в них ещё меньше гор. Думаю, мы слишком сгладили, потому что горы появляются с холмами не слишком часто. Поэтому наверно лучше вернуться в этом примере на один уровень сглаживания назад.

Это стандартный для процедурного генерирования процесс: вы пробуете что-нибудь, смотрите, выглядит ли это хорошо, если нет, возвращаетесь и пробуете что-нибудь другое.

Примечание: сглаживание в обработке сигналов называется фильтром нижних частот . Иногда он используется для устранения ненужного шума.

Подведём итог:

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

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

3. Создание шума

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

Примеры простых генераторов 1D/2D-шума:

1. Использовать случайные числа напрямую для вывода. Так мы поступили для долин/холмов/гор.
2. Использовать случайные числа в качестве параметров для синусов и косинусов, которые используются для вывода.
3. Использовать случайные числа как параметры для градиентов, которые используются для вывода. Этот принцип используется в шуме Перлина.

Вот некоторые стандартные способы модификации шума:

1. Применить фильтр для уменьшения или усиления определённых характеристик. Для долин/холмов/гор мы использовали сглаживание для уменьшения скачков, увеличения областей долин и создания гор рядом с холмами.
2. Добавить несколько функций шума одновременно, обычно со взвешенной суммой, чтобы можно было управлять влиянием каждой функции шума на конечный результат.
3. Интерполировать между значениями шума, полученными функцией шума, для генерирования сглаженных областей.

Существует очень много способов создания шума!

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

1. Как вы будете использовать шум?
2. Какие свойства вам требуются от функции шума в каждом конкретном случае?

4. Способы использования шума

Самый прямолинейный способ использования функции шума - использовать его напрямую как высоту. В примере выше я сгенерировал долины/холмы/горы, вызывая random(1,3) в каждой точке карты. Значение шума напрямую используется как высота.

Использование шума смещения средней точки (midpoint displacement noise) или шума Перлина - тоже примеры непосредственного использования.

Другой способ использования шума - использовать его как смещение от предыдущего значения. Например, если функция шума возвращает , то можно принять, что первая позиция равна 2, вторая равна 2 + -1 = 1, а третья равна 1 + 5 = 6. См. также «случайное блуждание» . Можно сделать обратное, и использовать разность между значениями шума. Это тоже можно воспринимать как модификацию функции шума.

Вместо использования шума для задания высот, можно использовать его для аудио.

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

Или можно использовать шум как графическую текстуру. Шум Перлина часто используется с этой целью.

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

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

В моём генераторе полигональных карт я применял различные способы использования шума, но ни в одном из них шум не использовался напрямую для определения высоты:

1. Структура графа проще всего, когда используется сетка квадратов или шестиугольников (на самом деле я начал с сетки шестиугольников). Каждый элемент сетки - это полигон. Я хотел добавить в сетку случайности. Это можно сделать, перемещая точки случайным образом. Но мне нужно было что-то более случайное. Я использовал генератор синего шума для размещения полигонов и диаграмму Вороного для из реконструирования. На это ушло бы намного больше времени, но, к счастью, у меня была библиотека (as3delaunay), которая всё сделала за меня. Но я начал с сетки, что намного проще, и именно с неё я и рекомендую начинать вам.
2. Береговая линия - это способ отделить сушу от воды. Я использовал два разных способа для её генерирования с помощью этого шума, но можно также попросить дизайнера нарисовать форму самому, и я продемонстрировал это с помощью квадратных и округлых форм. Радиальная форма береговой линии - это функция шума, использующая синусы и косинусы, отрисовывающая их в полярной форме. Форма береговой линии Перлина - это генератор шума, использующий шум Перлина и радиальный возврат в качестве порога. Здесь можно использовать любое количество функций шума.
3. Истоки рек располагаются случайным образом.
4. Границы между полигонами сменяются с прямых линий на зашумлённые линии. Это похоже на midpoint displacement, но я отмасштабировал их, чтобы они умещались в границы полигонов. Это чисто графический эффект, поэтому код находится в GUI (mapgen.as) вместо базового алгоритма (Map.as).

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

5. Частота шума

Частота - это самое важное свойство, которое нам интересно. Простейший способ понять её - посмотреть на синусоиды. Вот синусоида с низкой частотой, после неё идёт синусоида со средней частотой, а в конце расположена синусоида с высокой частотой:

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

Если у вас есть непрерывная функция, например, sin , которая создаёт шум, то увеличение частоты означает умножение входных данных на какой-нибудь коэффициент: sin(2*x) увеличит вдвое частоту sin(x) . Увеличение амплитуды означает умножение выходных данных на коэффициент: 2*sin(x) увеличит вдвое амплитуду sin(x) . В коде выше видно, что я изменил частоту, умножив входные данные на разные числа. Мы используем амплитуду в следующем разделе, при суммировании нескольких синусоид.

Изменение частоты

Изменение амплитуды

Всё вышесказанное относится к 1D, но то же самое происходит и в 2D. Посмотрите на рисунок 1 на этой странице . Вы видите примеры 2D-шума с большой длиной волны (низкой частотой) и малой длиной волны (высокой частотой).Заметьте, что чем выше частота, тем меньше отдельные фрагменты.

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

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

Print_chart(0, )
Обычно одновременно у вас будет множество частот, и правильных ответов о выборе нужной вам никто не даст. Спросите себя: какие частоты мне нужны? Разумеется, ответ зависит от того, как вы планируете их использовать.

6. Цвета шума

«Цвет» шума определяет типы частот, которые в нём содержатся.

На белый шум все частоты влияют одинаково. Мы уже работали с белым шумом, когда выбирали из 1, 2 и 3 для обозначения долин, холмов и гор. Вот 8 последовательностей белого шума:

For i in range(8): random.seed(i) print_chart(i, )
В красном шуме (также называемом броуновским) больше выделяются низкие частоты (имеют высокие амплитуды). Это значит, что в выходных данных будут более долгие холмы и долины. Генерировать красный шум можно усреднением соседних значений белого шума. Вот те же самые 8 примеров белого шума, но подвергнутые процессу усреднения:

Def smoother(noise): output = for i in range(len(noise) - 1): output.append(0.5 * (noise[i] + noise)) return output for i in range(8): random.seed(i) noise = print_chart(i, smoother(noise))
Если внимательно посмотреть на любой из этих восьми примеров, можно заметить, что они сглаженней соответствующего белого шума. Интервалы больших или малых значений более долгие.

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

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

Def rougher(noise): output = for i in range(len(noise) - 1): output.append(0.5 * (noise[i] - noise)) return output for i in range(8): random.seed(i) noise = print_chart(i, rougher(noise))
Если внимательно посмотреть на любой из восьми примеров, можно заметить, что они грубее соответствующего белого шума. В них меньше долгих интервалов больших/малых значений, и более короткие вариации.

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

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

Подведём итог:

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

7. Сочетание частот

В предыдущих разделах мы рассмотрели «частоты» шума и различные «цвета» шума. Белый шум означает наличие всех частот. В розовом и красном шуме низкие частоты сильнее высоких. В синем и фиолетовом высокие частоты сильнее низких.

Один из способов генерирования шума с нужными частотными характеристиками - найти способ генерирования шума с определёнными частотами, а затем скомбинировать их вместе. Например, предположим, что у нас есть функция шума noise , сгенерировавшая шум с определённой частотой freq . Тогда если вам нужно, чтобы частоты 1000 Гц были дважды сильнее частот 2000 Гц, а другие частоты отсутствовали, мы можем использовать noise(1000) + 0.5 * noise(2000) .

Нужно признать, что теперь sine выглядит довольно шумно, но ему легко придать частоту, поэтому давайте начнём с этого и посмотрим, как далеко мы сможем продвинуться.

Def noise(freq): phase = random.uniform(0, 2*math.pi) return for i in range(3): random.seed(i) print_chart(i, noise(1))
Вот и всё. Наш базовый строительный кирпичик - это синусоида, смещённая вбок на случайное значение (называемое фазой ). Единственная случайность здесь заключается в том, насколько мы её сместили.

Давайте скомбинируем несколько функций шума вместе. Я хочу скомбинировать 8 функций шума с частотами 1, 2, 4, 8, 16, 32 (в некоторых функциях шума степени двойки называются октавами). Я умножу каждую из этих функций шума на определённый коэффициент (см. массив amplitudes) и суммирую их. Мне нужен способ вычисления взвешенной суммы:

Def weighted_sum(amplitudes, noises): output = * mapsize # make an array of length mapsize for k in range(len(noises)): for x in range(mapsize): output[x] += amplitudes[k] * noises[k][x] return output
Теперь я могу использовать функцию noise и новую функцию weighted_sum:

Amplitudes = frequencies = for i in range(10): random.seed(i) noises = sum_of_noises = weighted_sum(amplitudes, noises) print_chart(i, sum_of_noises)
Даже несмотря на то, что мы начали с синусоид, которые совсем не выглядят шумными, их сочетание выглядит довольно шумным.

А если использовать в качестве весов? Так используется гораздо больше низких частот и совсем нет высоких:

А если бы я использовал в качестве весов ? Низкие частоты имели бы очень малый вес, а у высоких частот он был бы гораздо большим:

Всё, что мы здесь сделали - это взвешенная сумма функций шума на разных частотах, и это заняло меньше 15 строк кода. Мы можем генерировать широкий диапазон различных стилей шума.

Подведём итог:

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

8. Генерирование радуги

Теперь, когда мы можем генерировать шум, смешивая вместе шум с разной частотой, давайте снова рассмотрим цвет шума.

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

Спектр частот соотносится с нашими массивами frequencies и amplitudes из предыдущего раздела.

Ранее мы использовали частоты, являющиеся степенями двойки. Различные типы цветного шума имеют гораздо больше частот, поэтому нам нужем массив побольше. Для этого кода вместо степеней двойки (1, 2, 4, 8, 16, 32) я собираюсь использовать все целые частоты от 1 до 30. Вместо записи амплитуд вручную, я напишу функцию amplitude(f) , возвращающую амплитуду любой заданной частоты и создающую по этим данным массив amplitudes .

Мы снова можем использовать функции weighted_sum и noise , но теперь вместо небольшого набора частот у нас будет более длинный массив:

Frequencies = range(1, 31) # def random_ift(rows, amplitude): for i in range(rows): random.seed(i) amplitudes = noises = sum_of_noises = weighted_sum(amplitudes, noises) print_chart(i, sum_of_noises) random_ift(10, lambda f: 1)
В этом коде функция amplitude определяет форму. Если она всегда возвращает 1, то мы получим белый шум. Как же сгенерировать другие цвета шума? Я использую то же случайное начальное число (random seed), но применю для него другую функцию амплитуды:

8.1. Красный шум

random_ift(5, lambda f: 1/f/f)

8.2. Розовый шум

random_ift(5, lambda f: 1/f)

8.3. Белый шум

random_ift(5, lambda f: 1)

8.4. Синий шум

random_ift(5, lambda f: f)

8.5. Фиолетовый шум

random_ift(5, lambda f: f*f)

8.6. Цвета шума

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

• Красный шум - это f^-2
• Розовый шум - это f^-1
• Белый шум - это f^0
• Синий шум - это f^+1
• Фиолетовый шум - это f^+2

Попробуйте менять показатель степени [в оригинале статьи], чтобы увидеть, как шум из разделов 8.1-8.5 генерируется из одной базовой функции.

Подведём итог:

• Можно генерировать шум взвешенной суммой синусоид с различными частотами.
• Разные цвета шума имеют веса (амплитуды), соответствующие функции f^c.
• Изменяя показатель степени, из одного набора случайных чисел можно получать разные цвета шума.

9. Другие формы шума

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

То, что мы делали в предыдущем разделе, можно воспринимать как ряды Фурье . Основная мысль заключается в том, что любую непрерывную функцию можно представить как взвешенную сумму синусоид и косинусоид. В зависимости от выбранных весов меняется внешний вид окончательной функции. Преобразование Фурье связывает исходную функцию с её частотами. Обычно мы начинаем с исходных данных и получаем из них частоты/амплитуды. Это видно в музыкальных проигрывателях, показывающих «спектр» шума.

Прямое направление позволяет анализировать данные и получить частоты; обратное направление позволяет синтезировать данные из частот. В работе с шумом мы обычно занимаемся синтезом. Фактически, мы уже это делали. В предыдущем разделе мы выбрали частоты и амплитуды и сгенерировали шум.

Преобование Фурье имеет множество применений.

На этой странице есть объяснение того, как работает преобразование Фурье. Диаграммы на этой странице интерактивны - можно ввести силу каждой частоты, и страница покажет, как они комбинируются. Комбинируя синусоиды, можно получить множество интересных форм. Например, попробуйте ввести в поле Cycles input 0 -1 0.5 -0.3 0.25 -0.2 0.16 -0.14 и снять флажок Parts. Правда, похоже на гору? В приложении (Appendix) этой страницы есть версия, показывающая, как выглядят синусоиды в полярных координатах.

Один из примеров использования преобразования Фурье для генерирования карт см. в технике генерирования ландшафтов синтезом частот Пола Бёрка (Paul Bourke), которая сначала генерирует двухмерный белый шум, затем преобразует его в частоты с помощью преобразования Фурье, затем придаёт ему форму розового шума, а потом преобразует обратно с помощью обратного преобразования Фурье.

Мой небольшой опыт экспериментов с 2D показывает, что в нём всё не так прямолинейно, как в 1D. Если вы хотите посмотреть на мои незавершённые эксперименты, прокрутите к концу этой страницы и подвигайте ползунки .

10. Другие функции шума

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

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

• Полагаю, в midpoint displacement вместо синусоид используется пилообразный сигнал, а потом суммируются всё более и более высокие частоты с всё более и более низкими амплитудами. Думаю, что получается розовый шум. В результате мы видим заметные грани, которые возникают или из-за пилообразного сигнала (не такого сглаженного, как синусоиды), или из-за использования только частот, являющихся степенями двойки. Точно я не знаю.
• Diamond square - это вариация midpoint displacement, которая позволять скрыть грани, получаемые в midpoint displacement.
• Одна октава шума Перлина/симплекс-шума генерирует сглаженный шум с определённой частотой. Чтобы сделать шум розовым, обычно суммируются несколько октав шума Перлина.
• Мне кажется, что фрактальное броуновское движение (ФБД) тоже генерирует розовый шум суммированием нескольких функций шума.
• Алгоритм Восса-Маккартни выглядит похожим на midpoint displacement. Он суммирует несколько функций белого шума с разными частотами.
• Генерировать розовый шум напрямую можно вычислением обратного преобразования Фурье для нужных частот. Именно это делает пример в предыдущем разделе. Пол Бёрк (Paul Bourke) описывает его как синтез частот (Frequency Synthesis) и демонстрирует как оно выглядит для 2D-шума, генерирующего трёхмерные карты высот.

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

Я нашёл не так много способов генерирования синего шума.

• Для моего проекта генератора карт я использовал алгоритм Ллойда с диаграммами Вороного, чтобы сгенерировать нужный мне синий шум. У меня уже была библиотека, создающая диаграммы Вороного, поэтому было проще снова использовать её, чем реализовывать как отдельный этап.
• Ещё один способ генерирования синего шума - пятна Пуассона . Если в вашем проекте ещё не используется библиотека Вороного, то пятно Пуассона выглядит проще. См. также , описывающую использование пятна в играх.
• Рекурсивные плитки Вана тоже могут генерировать синий шум. Я пока ещё не изучал их, но надеюсь взяться за это в будущем.
• Может быть, получится также напрямую генерировать синий шум, вычисляя обратное преобразование Фурье из спектра частот синего шума, но я пока не пробовал.

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

11. Дополнительное чтение

Эта статья изначально была заметками для себя. При публикации я усовершенствовал диаграммы и добавил пару интерактивных. Я потратил на неё гораздо меньше времени, чем на другие свои статьи, но я экспериментировал с объяснением некоторых тем, надеясь, что это позволит мне охватить больше информации.
червей Перлина Добавить метки