Программирование, 2022, № 3, стр. 59-69

1. МОДЕЛЬ ИСКАЖЕНИЯ ИЗОБРАЖЕНИЯ

Будем считать изображение идеальным, если оно было получено в идеальных условиях по освещению с использованием идеальных регистрирующих приборов, не вносящих никаких искажений. На самом деле таких изображений не бывает (если только это не смоделированное изображение компьютерной графики). Искажения на реальных изображениях можно описать следующей моделью [1, 2]:

где: $f(x,y)$ – идеальное изображение; $h(x,y)$ – искажающая функция, описывающая внешние влияния на процесс регистрации изображения; $n(x,y)$ – аддитивная составляющая, прибавленная к изображению в процессе регистрации и оцифровки (шумовая составляющая); $ \times $ – операция свертки; $g(x,y)$ – полученное в результате изображение.

Таким образом, негативными компонентами, проявившимися в процессе регистрации изображения, являются искажающая функция $h(x,y)$ и шумовая составляющая $n(x,y)$. Избавившись от них, можно получить изображение, близкое к идеалу. В реальных условиях обеспечить идеальность процесса съемки нельзя, поэтому встает задача разработки такого математического аппарата, который по известному изображению $g(x,y)$ подберет такой оператор, который нейтрализует негативный эффект от $h(x,y)$ и $n(x,y)$. Именно этот процесс называется восстановлением искаженных изображений.

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

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

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

где $\hat {f}(x,y)$ – приближение идеального изображения, полученное в результате восстановления; $R(I(x,y))$ – восстанавливающий оператор; $g(x,y)$ – искаженное изображение.

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

• “не слепая” деконволюция (ручное восстановление);

• “слепая” деконволюция (автоматическое восстановление);

• глубокое обучение (автоматическое восстановление).

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

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

Автоматическое восстановление изображений на данный момент представлено двумя классами методов: “слепая” деоконволюция и глубокое обучение. Первый класс методов представляет собой более точные методы, для которых характерно применение сложных математических моделей и высокая вычислительная сложность. Для второго класса методов характерна высокая зависимость получаемого результата от обучающей выборки. В последнее время наблюдается бурное развитие глубокого обучения и нейросетей. Однако, данные методы могут давать неточные результаты – “восстановить” те элементы на изображении, которых не было в оригинальном изображении [7]. Методы “слепой” деконволюции дают более точные результаты, что делает их наиболее предпочтительным выбором, особенно для сфер, в которых точность и правдоподобие является очень важным фактором. В следующем разделе будут более подробно рассмотрены методы восстановления изображений.

2. ОБЗОР МЕТОДОВ ВОССТАНОВЛЕНИЯ РАЗМЫТЫХ ИЗОБРАЖЕНИЙ

Ручное восстановление. Методы ручного восстановления (“не слепой” деконволюции) представляют собой восстанавливающие фильтры и алгоритмы, которые в качестве входных параметров принимают как размытое изображение, так и модель искажающей функции, заданной вручную со всеми ее параметрами. Методы “не слепой” деконволюции подразумевают, что искажающая функция известна полностью и вся задача сводится к применению одного из восстанавливающих фильтров или алгоритмов [8].

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

где $F(u,{v})$ – приближение четкого изображения; $H(u,{v})$ – искажающая функция; $G(u,{v})$ – результат искажения (размытое или смазанное изображение); ${{S}_{n}}(u,{v})$ – спектральная плотность шума; ${{S}_{f}}(u,{v})$ – спектральная плотность исходного изображения; $\frac{{{{S}_{n}}(u,{v})}}{{{{S}_{f}}(u,{v})}}$ – редко бывает известно, поэтому данное отношение заменяют на некоторую константу K.

Еще одним часто используемым методом является сглаживающая фильтрация методом наименьших квадратов со связью. Этот метод известен как “фильтрация по Тихонову” или “Тихоновская регуляризация” [9, 10]. В этом фильтре задача восстановления представляется в матричной форме и происходит оптимизация модели. Решение принимает вид:

где y – параметр регуляризации, а $P(u,{v})$ – Фурье-преобразование оператора Лапласа (матрицы 3 × 3).

Еще одним методом “слепой” деконволюции является метод Ричардсона–Люси. Этот метод использует подход максимального правдоподобия и является нелинейным и итерационным [9]. Для его работы необходимо задать еще один параметр – число итераций. В отличии от первых двух методов, которые используют образы Фурье [10] (работают преимущественно в частотной области), данный метод обрабатывает изображение в пространственной области:

где ${{f}_{k}}$ – приближение четкого изображения на итерации номер k; $h(x,y)$ – искажающая функция; k – номер итерации; $g(x,y)$ – результат искажения.

Метод Ричардсона–Люси широко используется в программах для обработки астрономических фотографий. Недостатком данного метода является очень большая вычислительная сложность.

“Слепая” деконволюция. Методы ручного восстановления позволяют восстанавливать изображение с достаточно хорошим результатом, но для этого требуется точно описать функцию искажения. Однако, в большинстве реальных ситуаций искажающую функцию либо очень сложно описать, либо она вовсе неизвестна. В таких ситуациях задача “слепой” деконволюции превращается в задачу “слепой” деконволюции, цель которой – поиск приближения четкого изображения и искажающей функции без наличия информации об искажающей функции [5, 6]. Задача в такой постановке становится на порядок сложнее. Во-первых, возрастает количество неизвестных переменных – к неизвестному приближению четкого изображения добавляется неизвестная искажающая функция. Во-вторых, с математической точки зрения задача имеет множество решений, поскольку существует бесчисленное множество пар изображения и искажающей функции, свертка которых давала бы наблюдаемое искаженное изображение. Таким образом, данную задачу можно назвать задачей с недостаточным количеством информации для ее решения.

Для решения данной задачи было предложено множество методов, использующих разные подходы. Некоторые методы поиска искажающей функции включают восстановление с помощью методов фильтрации, например, Giannakis и Heath [11] разработали последовательность фильтров с конечной импульсной характеристикой для непосредственного получения приближения четкого изображения и последовательность фильтров с конечной импульсной характеристикой для определения функции искажения. Hosseini и Plataniotis [12] также представили метод фильтрации с использованием фильтров конечной импульсной характеристики. Также были представлены множество методов, использующих метод Люси–Ричардсона [13], подход Total Variation [14], метод максимального правдоподобия [15] и др. Достаточно распространенным является пирамидальный подход, при котором строится пирамида разных разрешений искаженного изображения, и неизвестная искажающая функция восстанавливается постепенно – она уточняется в процессе оптимизации некоторой целевой функции на каждом уровне пирамиды от самого низкого разрешения (первого уровня пирамиды) до самого высокого разрешения (последнего уровня пирамиды) [1, 2, 6, 16].

Методы, основанные на теории линейных моделей. В теории линейных моделей искажение изображения понимается как процесс перехода четких границ в размытые. Подразумевается, что данный процесс линеен и размытие является самой весомой операцией в данном процессе. Также подразумевается, что четкое и размытое изображения – черно-белые и являются цифровыми. В целях математической реализации линейной модели, также подразумевается, что четкое и искаженное изображения – матрицы размером m × n и искажение (размытие) строк и столбцов изображения происходит отдельно. Для удобства последующего изложения, в данном разделе будут использоваться следующие обозначения: $F$ – матрица размера $m \times n$, представляющая четкое неискаженное изображение; $G$ – матрица размера $m \times n$, представляющая размытое изображение; $N$ – матрица размера $m \times n$, представляющая аддитивный шум; ${{A}^{{ - 1}}}$ – матрица, обратная матрице $A$; ${{A}^{{\text{т}}}}$ – транспонированная матрица A; ${{A}_{c}}$ – матрица размера n × n, представляющая размытие по столбцам; ${{A}_{r}}$ – матрица размера $m \times m$, представляющая размытие по строкам.

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

где ${{A}_{c}}F$ – размытие каждого столбца в четком изображении $F$; $FA_{r}^{{\text{т}}}$ – размытие каждой строки в четком изображении F.

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

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

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

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

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

Методы, основанные на стохастических моделях. Стохастические модели основаны на анализе функции плотности вероятности размытого изображения. Например, Xiao и другие [18] разработали алгоритм слепой деконволюции “Stochastic Random Walk Optimization Algorithm”, который основан на простом методе случайного поиска. В данном подходе промежуточное решение обновляется за счет получаемой цепочки случайных перемещений по пикселям в размытом изображении, после чего обновленное решение проверяется на соответствие цели. После проверки решается применять ли это обновление. Этот метод итеративно выполняет вышеописанный алгоритм для поиска неизвестной функции искажения, которая используется в алгоритме “не слепой” деконволюции для получения приближения четкого изображения. В данной работе был использован алгоритм “не слепой” деконволюции из предыдущей работы [19], посвященной стохастическому подходу эффективной “не слепой” деконволюции. Особенностью данного алгоритма является его простота.

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

где $\rho (f,h|g)$ – апостериорное распределение изображения, которое пропорционально функции правдоподобия $\rho (g|f,h)$ и априорным распределениям $\rho (f)$ и $\rho (h)$ изображения и функции искажения соответственно.

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

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

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

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

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

где: $\mathop {\max }\limits_{f,h} \rho (g|f,h)$ – максимальное правдоподобие; $\rho (f)$ и $\rho (h)$ – априорные распределения изображения и функции искажения соответственно.

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

где $\lambda {{\left\| {f \times h - g} \right\|}^{2}}$ представляет собой правдоподобие, которое одновременно является естественным ограничением, накладываемым на искомую искажающую функцию и приближение четкого изображения; ${{\left| {{{k}_{{x,i}}}(f)} \right|}^{\alpha }}$ и ${{\left| {{{k}_{{y,i}}}(f)} \right|}^{\alpha }}$ представляют собой горизонтальные и вертикальные производные пикселя $i$ приближения четкого изображения  f.

В данном выражении первое слагаемое является постоянным, а производные могут быть изменены, путем задания параметра α. Разные значения данного параметра подходят для разных видов изображений, например, для естественных изображений лучше всего подходят значения от 0.5 до 0.8 [24]. Также стоит отметить, что с ростом разрешения изображения количество неизвестных возрастает, и для данного метода более предпочтительным является размытое изображение, это может быть объяснено тем, что размытие оказывает два противоположных эффекта на значение правдоподобности: 1) оно делает изображение более сглаженным, что уменьшает значение правдоподобия; 2) размытие уменьшает дисперсию производных, что увеличивает значение правдоподобия [3]. И, в конце концов, самым предпочтительным результатом в соответствии с выражением выше будет являться изображение, не содержащее градиентов вовсе. Данная проблема характерна даже для ситуаций, в которых параметр $\alpha $ выбран достаточно точно для восстанавливаемого изображения, и использование производных более высокого порядка не оказывает положительного эффекта на результат [25, 26].

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

где

Если предположить, что шум и изображение нормально распределены с нулевым математическим ожиданием и дисперсиями ${{\delta }^{2}}$ и ${{\eta }^{2}}$: $f = N(0,{{\delta }^{2}})$ и $n = N(0,{{\eta }^{2}})$.

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

Было предложено множество модификаций данного подхода, например, Perrone и Favaro [27] показали как работает простая версия алгоритма, описанного выше, и описали его детали работы, и то, почему на них стоит заострять внимание. В результате они предложили свой метод, названный алгоритмом “Прогнозируемой чередующейся минимизации” (Projected Alternating Minimization (PAM)), который учитывает множество деталей, например, предположение о функции искажения, что улучшает поиск функции искажения на поздних стадиях алгоритма. Также авторы наглядно продемонстрировали, что использование оценки апостериорного максимума для поиска функции искажения и приближения четкого изображения приводит к попаданию в локальный минимум, поэтому в предложенном ими алгоритме было решено отказаться от данной идеи.

Также была представлена еще одна модификация – алгоритм ускоренной чередующейся минимизации (Accelerated Alternating Minimization Algorithm) [28], представленный Padcharoen и др. Данная модификация использует подход, называемый методом ускоренного проксимального градиента (Accelerated Proximal Gradient (APG)), который используется для увеличения скорости сходимости обычно медленного градиентного спуска.

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

где f – приближение четкого изображения; γ – размытое изображение; $\phi (f)$ – регуляризатор; $\lambda $ – параметр регуляризации.

От метода к методу $\phi (f)$ может варьироваться, но наиболее распространенным регуляризатором в методах, основанных на оценке апостериорного максимума, является ${{L}_{p}}$ – норма:

где $i$ и $j$ – индексы элемента матрицы.

Глубокое обучение. Сверточные нейронные сети нашли широкое применение в обработке изображений и компьютерном зрении. Автоматическое восстановление размытых и смазанных изображений не стало исключением. Как правило, восстановление размытых и смазанных изображений с помощью нейросетей нацелено не на поиск неизвестной функции искажения, а на улучшение визуального качества изображения. Но для справедливости стоит отметить, что существуют модели, которые ориентированы именно на поиск неизвестной искажающей функции [29]. Модели глубокого обучения для восстановления размытых и смазанных изображений широко используют в своей основе енкодеры и декодеры [30, 31] и генеративно-состязательные нейронные сети [32, 33].

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

Нейросетвые модели очень чувствительны к обучающей выборке. В качестве примера зависимости качества обучения модели от обучающей выборки стоит рассмотреть пример восстановления с помощью обученной модели DeblurGAN, при обучении которой в обучающей выборке отсутствовали зашумленные изображения (см. рис. 2).

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

3. ПРЕДЛАГАЕМОЕ РЕШЕНИЕ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

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

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

Пирамидальный подход. Предлагаемый алгоритм основан на пирамидальном подходе, который нашел широкое применение в методах “слепой” деконволюции [1, 2, 6, 13, 16]. Пирамидальный подход заключается в постепенном уточнении ядра от самого маленького размера до максимального размера, задаваемого пользователем. Процесс поиска ядра свертки (функции искажения) начинается, как правило, с разрешения 3 × 3 или 5 × 5. При этом в процессе оптимизации ядра определенного размера используется искаженное изображение не исходных размеров, а уменьшенного размера. Для данной цели строится пирамида искаженных изображений разных размеров. Каждое такое изображение соответствует определенному размеру ядра свертки. Перемещение по пирамиде дает возможность уточнять ядро на каждом шаге, а не подбирать его заново, что значительно экономит время и ресурсы при работе алгоритма.

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

Генетический алгоритм. Генетические алгоритмы оперируют понятием особи – точка в пространстве поиска, которой в данном случае является ядро, то есть квадратная матрица. В классической постановке с каждой координатой точки пространства поиска принято работать в закодированном виде. В данном случае особь будет представлять из себя хромосому – последовательность генов [35]. Однако, в предлагаемом алгоритме было решено отказаться от данной идеи и работать с фенотипом особи – то есть в незакодированном виде. При этом предлагается работать с незакодированными параметрами особи как с генами. В связи с этим стоит обозначить, что далее для удобства изложения особь будет называться ядром, а незакодированный параметр особи будет обозначаться пикселом. Также стоит упомянуть, что область определения яркости пикселов ядер представляет собой отрезок [0; 1]. Все обрабатываемые изображения нормализованы от 0 до 1.

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

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

Мутация. Искомое ядро свертки, как правило, представляют из себя изображение, большая часть пикселей которого имеет яркость 0. При этом только небольшое количество пикселей в центре изображения имеет яркость больше нуля. В ходе экспериментов выяснилось, что классические операторы мутации, такие как инвертирование бита, мутация обменом, или мутация обращением [35] не производят положительного эффекта на процесс оптимизации, так как мутации в данном случае происходят по всему ядру, и количество “полезных” мутаций значительно сокращается. Это проявляется в первую очередь в изменении пикселей по краям ядра, которые в большинстве случаев должны быть равны нулю. Данная мутация уводит процесс оптимизации в сторону и увеличивает время работы алгоритма. В процессе исследования было выявлено, что если мутации происходят возле найденной на предыдущей итерации функции искажения (пикселей с высокими значениями), то количество “полезных” мутаций становится гораздо больше. Исходя из данных наблюдений, было решено производить мутации вблизи пикселей с высокими значениями. В предложенном алгоритме высоким значением является значение из отрезка [0.1; 1.0]. Таким образом, количество пикселей для мутации сильно сокращается.

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

Так как ранее было упомянуто, что работа с особями ведется в незакодированном виде, то операция инвертирования в данном случае теряет смысл. Также стоит отметить, что изменение значения на значение противоположного края отрезка области определения в данном случае не эффективно, так как большинство реальных функций искажения не представляют из себя бинарные изображения и могут иметь промежуточные значения яркости. Поэтому в качестве операций мутации в алгоритме выступает случайное положительное или отрицательное изменение значения пикселя на случайное значение из области определения (вещественное число от 0 до 1). При этом вероятность положительной мутации задается отдельно, и, как показали эксперименты, оптимальным значением данной вероятности являются значения из отрезка [0.5, 0.9].

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

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

Алгоритм и результаты его работы. Рассмотрим общий алгоритм оптимизации с использованием генетических алгоритмов. Блок-схема предлагаемого алгоритма представлена на рис. 4.

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

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

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

где I – оцениваемое изображение разрешения $m \times n$; $i$, $j$ – координаты пиксела; $DFT(I)$ – образ Фурье изображения I, полученный с помощью дискретного преобразования Фурье; $g(x,y)$ – результат искажения (размытое или смазанное изображение).

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

где $Orig$ – четкое изображение; $Res$ – результат восстановления.

Для проверки поставленных гипотез был проведен ряд экспериментов над изображениями, разными по характеру исполнения и деталей. Каждое изображение было искажено разными функциями, от простых, до более сложных. Все эксперименты выполнялись со следующими значениями параметров: вероятность скрещивания: 0.1; размер турнира: 2; максимальный размер ядра: 23; вероятность мутации: 0.1; вероятность положительного изменения значения пикселя при мутации: 0.5; количество популяций, в течении которых не происходит увеличения целевой функции (критерий останова): 15.

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

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

4. ВЫВОДЫ

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

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