5.3. Генерирование псевдослучайных чисел

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

Обычный способ получения таких последовательностей состоит в том, что сначала с помощью достаточно простых алгоритмов генерируют независимые псевдослучайные числа с равномерным распределением, а затем их подвергают линейным и нелинейным преобразованиям для получения заданных статистических свойств [7, 8, 15, 28]. Наиболее часто требуется обеспечить гауссов закон распределения чисел и заданную функцию их корреляции или заданный энергетический спектр.

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

Для получения последовательностей псевдослучайных чисел с равномерным распределением чаще всего используется так называемый конгруентный метод [28], в соответствии с которым каждое следующее число в последовательности получается из предыдущего с помощью простого соотношения

где — некоторые константы.

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

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

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

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

сумма достаточно большого количества независимых случайных величин имеет распределение, приближающееся (с ростом количества складываемых чисел) к гауссову. Нормализующее линейное преобразование чисел с равномерным распределением удобно выполнять с помощью дискретного преобразования Фурье, реализуемого алгоритмами БПФ [43]. Рассмотрим этот метод подробнее.

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

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

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

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

В [43] показано также, что корреляционная функция действительной и мнимой частей преобразованной последовательности

пропорциональна дискретному преобразованию Фурье набора коэффициентов

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

Рис. 5.1.

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

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

В частности, для того чтобы гауссовы последовательности имели нулевое среднее, достаточно положить

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

Описанный метод имеет ряд преимуществ перед другими методами генерирования гауссовых последовательностей [7, 8, 15]. Он обеспечивает при равных затратах машинного времени существенно лучшее приближение к нормальному закону распределения и значительно экономнее использует исходную последовательность независимых чисел: на выработку одного гауссова числа затрачивается ровно одно число исходной последовательности чисел с равномерным распределением. Последнее особенно важно при обработке изображений и моделировании, когда приходится формировать массивы объемом в миллионы отсчетов, не допуская повторений.