АДАПТИВНЫЙ ДВУМЕРНЫЙ СПОСОБ РАЗМНОЖЕНИЯ ОЦЕНОК И УСТРОЙСТВО, ЕГО РЕАЛИЗУЮЩЕЕ Российский патент 2012 года по МПК G06F17/17 

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

В общем случае, упрощенная математическая модель двумерного сигнала (изображения) представляет собой двумерную дискретную последовательность Y_i,j, , вида:

где S_i,j - низкочастотная, медленно меняющаяся полезная составляющая;

η_i,j - аддитивная шумовая составляющая, распределенная по гауссовскому закону с нулевым математическим ожиданием и постоянной дисперсией;

N - количество строк, М - количество столбцов двумерного массива изображения.

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

Подобная задача может возникнуть: 1) в работе приемо-передающих устройств дальней или космической связи; 2) в радиотехнике при обработке сигналов; 3) в системах цифровой обработки изображений.

Известен способ скользящего среднего [Гонсалес Р. Цифровая обработка изображений/ Р.Гонсалес, Р.Вудс. - М.: Техносфера. - 2005. - 1072 с.]. Для его использования достаточно одной реализации Y_i,j, , исходного процесса.

Для исходного изображения определяется размер маски сглаживающего фильтра m, т.е. натуральное число m<N. Способ скользящего среднего предполагает запоминание исходного изображения Y_i,j, определение размера маски фильтра m (ширины «скользящего окна»), для которого производится вычисление среднего арифметического, , замену центрального из значений Y_i,j, найденным средним , сдвиг «скользящего окна» на одно значение вправо, вычисление среднего арифметического выбранных значений реализации, и так до тех пор, пока маска фильтра не переместится по всему изображению.

Ширину "окна" выбирают нечетной, т.к. сглаженное значение рассчитывается для центрального значения.

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

Недостатками известного устройства являются:

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

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

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

- если ширина "окна" сглаживания равна 2р+1, то первые р и последние р значений исходной реализации результатов измерений не подвергаются обработке;

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

В качестве нелинейных фильтров используются фильтры, основанные на порядковых статистиках [Гонсалес Р. Цифровая обработка изображений/ Р.Гонсалес, Р.Вудс. - М.: Техносфера. - 2005. - 1072 с.]. Отклик такого фильтра определяется предварительным упорядочиванием (ранжированием) значений пикселей, покрываемых маской фильтра, и последующим выбором значения, находящегося на определенной позиции упорядоченной последовательности (т.е. имеющего определенный ранг). Фильтрация сводится к замещению исходного значения (в центре маски) на полученное значение отклика фильтра. Наиболее известен медианный фильтр, который заменяет центральное значение маски фильтра на значение медианы распределения всех значений результатов измерений, принадлежащих области маски фильтра. Чтобы выполнить медианную фильтрацию для элемента изображения, необходимо сначала упорядочить по возрастанию значения пикселей внутри маски, затем найти значение медианы и присвоить полученное значение обрабатываемому элементу.

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

Недостатками известного устройства являются:

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

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

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

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

- медианная фильтрация является нелинейным способом обработки;

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

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

Известен способ наименьших квадратов и устройство для кусочно-линейной аппроксимации [Бендат Дж., Пирсол А. Прикладной анализ случайных данных: Пер. с англ. - М.: Мир, 1989. - 540 с., авторское свидетельство №1624479]. Для использования данного способа достаточно одной одномерной реализации Y₁, Y₂,…, Y_N исходного процесса.

Способ наименьших квадратов позволяет для результатов измерений Y₁, Y₂,…, Y_N исходного процесса получить оценку, минимизируя целевую функцию вида:

.

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

.

Дифференцируя выражение по а и b и приравнивая к нулю, получаем систему линейных уравнений:

.

Решением системы является:

,

.

При оценке сумма квадратов отклонений значений оценки от значений реализации измерений является минимальной.

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

Недостатками известного способа являются:

- при использовании данного способа необходима априорная информация о функции полезного сигнала;

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

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

- ограниченность способа наименьших квадратов к распараллеливанию и построению системы многоканальной обработки.

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

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

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

Наиболее близким к изобретению является способ выделения тренда путем размножения оценок его единственной исходной реализации (РАЗОЦ) и устройство для его осуществления (патент №2207622, МПК 7 G06F 17/18).

Рассматриваемое устройство-прототип предполагает: 1) запоминание входной реализации у₁, у₂,…, у_n; 2) разбиение входной реализации на подынтервалы случайными числами, имеющими равномерный закон распределения; 3) проверку условия, что подынтервалы включают не менее L значений исходной реализации, если условие не выполняется, то заново генерируются случайные числа разбиения; 4) нахождение на каждом подынтервале входной реализации оценок коэффициентов аппроксимирующего полинома а+bt+ct²с помощью метода наименьших квадратов; 5) повторение процедур, описанных в пунктах 2-4 К раз; 6) нахождение сглаживающей функции как среднего арифметического "кусочно-квадратичных" аппроксимирующих функций в каждый момент времени.

Устройство для выделения тренда методом размножения оценок его единственной исходной реализации (РАЗОЦ) содержит блок хранения результатов измерений, коммутаторы, генератор случайных чисел, блок устранения связанных значений, блок ранжирования, регистр хранения выборки случайных чисел, блоки аппроксимации, регистры хранения оценок, арифметическое суммирующее устройство, блок хранения оценки полезной составляющей, генератор тактовых импульсов.

Недостатками известного устройства-прототипа являются:

- невозможность реализации известного способа РАЗОЦ в реальном масштабе времени и большие вычислительные затраты;

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

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

- для использования способа размножения необходимо запоминать всю входную реализацию.

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

Упрощенная математическая модель входного двумерного сигнала представляется в соответствии с выражением (1).

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

Например, сумма числа инверсий для направления 5 равна:

,

,

где i=const, j=const; Y_i,j - текущее значение пикселя изображения с координатами (i,j); Y_i+l,j, l=i+1…d - последующие значения пикселей изображения по j-му столбцу (движение в направлении 5), d≤R, R - максимальная длина интервала квазистационарности.

Количество сочетаний, для которых вычисляется сумма инверсий, составляет:

.

Первая альтернатива (убывающий сигнал) принимается, если:

Правило для принятия второй альтернативы (возрастающий сигнал) имеет вид:

.

Гипотеза о стационарности сигнала принимается, если с₂≤τ_d≤c₁, где α - априорно задаваемое значение ошибки первого рода.

По полученным границам интервалов для каждого из восьми секторов, образованных направлениями 1-2, 2-3, 3-4, 5-6, 7-8, 8-1, формируются области квазистационарности. Для этого используется линейная интерполяция границ смежных интервалов уравнением прямой, проходящей через две точки:

, ,

где (i₁,j₁) - координаты границы направления h, (i₂,j₂) - координаты границы направления h+1.

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

Значения пикселей, попавшие между всеми направлениями и интерполирующими прямыми проходящими через границы интервалов квазистационарности, объединяются в одну область Ω и аппроксимируются поверхностью первого порядка вида где ω_i,j, значения бинарной маски, которая принимает значения, равные:

, , .

Значения коэффициентов А, В и С определяются с помощью двумерного способа наименьших квадратов [Патент №2362207 Российская Федерация, С2, МПК G06F 17/17. 2007127727/09; заяв. 19.07.2007; опубл. 20.07.2009, Бюл. №20], для нахождения которых минимизируется целевая функция вида:

Дифференцируя выражение (2) по А, В и С и приравнивая к нулю, получаем систему линейных уравнений:

Решением системы (3) является:

Процедура получения области Ω и вычисление оценки повторяется для каждого значения пикселя Y_i,j, при этом формируется весовая функция W_i,j, значения которой равны количеству размноженных оценок для каждого пикселя.

Результирующая оценка изображения определяется как среднее арифметическое размноженных адаптивных оценок:

, .

Алгоритм (фиг.2) состоит из следующих этапов:

- записываются значения входного двумерного сигнала Y_i,j, , ;

- задаются параметры способа: значение вероятности ошибки первого рода α и максимальная длина интервала квазистационарности R;

- вычисляется случайная величина и пороговые значения и ;

- проверяется гипотеза о стационарности сигнала с₂≤τ_d≤с₁, при выполнении которой происходит формирование бинарной маски ω_i,j, ;

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

- данная процедура повторяется для всех значений пикселей исходного изображения Y_i,j, , , в результате чего получается набор оценок ;

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

Устройство для обработки изображений на основе адаптивного двумерного способа размножения оценок (фиг.3) содержит блок хранения входной реализации 1, вход которого является информационным входом устройства, выход которого подключен к первому входу поэлементного умножителя 4 и первому входу блока определения участков квазистационарности 2, к выходу которого подключен вход блока формирования маски 3, к выходу которого подключен второй вход поэлементного умножителя 4, к выходу которого подключен вход блока аппроксимации 5, к выходу которого подключен первый вход блока хранения оценок 6, к выходу которого подключен первый вход блока усреднения оценок 7, выход которого подключен к входу блока хранения оценки полезной составляющей 8, чей выход является информационным выходом устройства; выход счетчика текущей строки 9.1 подключен ко второму входу блока определения участков квазистационарности 2 и входу блока задержки 9.2, к выходу которого подключены четвертый вход поэлементного умножителя 4 и вход блока задержки 9.3, к выходу которого подключен второй вход блока хранения оценок 6 и первый вход генератора сигнала усреднения 9.7, к выходу которого подключен второй вход блока усреднения оценок 7; выход счетчика текущего столбца 9.4 подключен к третьему входу блока определения участков квазистационарности 2 и входу блока задержки 9.5, к выходу которого подключены третий вход поэлементного умножителя 4 и вход блока задержки 9.6, к выходу которого подключены третий вход блока хранения оценок 6 и второй вход генератора сигнала усреднения 9.7; синхронность работы устройства обеспечивается генератором тактовых импульсов 10.

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

Устройство для обработки изображений на основе двумерного способа размножения оценок работает следующим образом. В блок хранения входной реализации 1 записывается исходный двумерный сигнал. Блоки счетчика текущей строки 9.1 и счетчика текущего столбца 9.4 формируют координаты пикселя, обрабатываемого в данный момент времени. Координаты поступают на вход блока определения участков квазистационарности 2. Происходит выборка значений пикселей, близких к выбранному, из блока хранения входной реализации 1 и определение координат пикселей, принадлежащих области близкой яркости. Полученные координаты передаются на блок формирования маски 3, где формируется маска фиксированного размера, содержащая «0» в местах с координатами пикселей, не принадлежащих полученной области, и «1» для принадлежащих. Центр маски соответствует текущему выбранному пикселю, координаты которого являются координатами маски. Полученная маска подается на поэлементный умножитель 4, где путем поэлементного умножения пикселей исходного изображения на маску с учетом ее координат выделяется область, поступающая дальше на блок аппроксимации 5. Оценка, полученная путем аппроксимации поверхностью первого порядка способом наименьших квадратов, запоминается в блоке хранения оценок 6, в котором кроме самой оценки запоминаются и ее координаты, поступившие со счетчиков номера строки 9.1 и столбца 9.4 через блок задержки. Последовательно выполняется перебор всех пикселей изображения, полученные оценки запоминаются в блоке хранения оценок 6. По окончании перебора блок генерации сигнала усреднения 9.7 подает на блок усреднения оценок 7 сигнал, после чего сохраненные в блоке 6 оценки усредняются, и в блоке хранения оценки полезной составляющей 8 запоминается полученная оценка полезной составляющей. Синхронность работы устройства обеспечивается генератором тактовых импульсов 10.

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

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

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

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