ABOUT SELECTION OF RESIDUE SYSTEM RANGE FOR IMAGE PROCESSING

Full Text

Введение Необходимость использования цифровой обработки изображений возникает в самых разных областях деятельности человека, таких как: системы видеонаблюдения, медицина, техническая диагностика и многих других [1-2]. Приложения цифровой обработки сигналов, в частности изображений, должны быть энергоэффективными и обладать достаточно большой скоростью выполнения арифметических операций [3-4]. Наиболее перспективным способом повышения производительности систем цифровой обработки сигналов, является использование арифметики Системы Остаточных Классов (СОК) вместо традиционной двоичной арифметики [5]. Благодаря свойству отсутствия переносов и параллельному выполнению операций СОК может быть эффективно использована в приложениях с преобладающей долей операций сложения, вычитания и умножения [6]. Одним из таких приложений является цифровая обработка изображений [7]. Одной из первых работ, посвященных применению СОК в обработке изображений, была [8], где авторы уделили основное внимание концепции безопасности, в то время как параллелизм СОК был задействован в меньшей степени. Улучшенная структура шифрования целого изображения представлена в [9]. Эта схема содержит только стандартные блоки СОК, обеспечивая высокую скорость и низкое потребление энергии для защищенной обработки изображений. Особенности применения СОК для частной задачи определения контуров изображений описаны в [10]. Актуальным вопросом, возникающим при использовании СОК, является определение наиболее эффективного набора модулей для конкретного приложения. Выбор набора модулей играет важную роль в выполнении операций СОК, а также может повлиять на приложения, ее использующее [11-12]. В [13] предлагается использовать набор модулей СОК вида , который в настоящее время активно используется во многих приложениях СОК, в том числе и в цифровой обработке сигналов. В [14] предлагается использовать для обработки изображений специальный набор модулей при , что соответствует набору модулей . Авторами делается вывод о достаточности такого диапазона для фильтрации изображений. В [15] используется специальный набор модулей , который является частным случаем набора при . В данной статье будет показано, что применение этих наборов модулей может приводить к существенным ошибкам, искажающим изображение. Для устранения причин возникновения таких ошибок предлагается новый критерий выбора достаточного динамического диапазона СОК. Введение в СОК В СОК числа представляются в базисе взаимно-простых чисел, называемых модулями , , для . Произведение всех модулей СОК называется динамическим диапазоном системы. Любое целое число может быть единственным образом представлено в СОК в виде вектора , где [16]. Динамический диапазон СОК обычно делится на две примерно равные части, таким образом, чтобы примерно половина диапазона представляла положительные числа, а остальная часть диапазона - отрицательные. Таким образом, любое целое число, удовлетворяющее одному из двух соотношений: для нечетных M; (1) для четных M, (2) может быть представлено в СОК. Операции сложения, вычитания и умножения в СОК определяются формулами , (3) . (4) Равенства (3)-(4) показывают параллельную природу СОК, свободную от поразрядных переносов. Восстановление числа по остаткам основано на Китайской теореме об остатках (КТО) [6] , (5) где . Элемент означает мультипликативный обратный элемент для , по модулю . Пример 1. Рассмотрим пример перевода числа со знаком из СОК в ПСС. Пусть СОК задана набором модулей . Динамический диапазон СОК равен . Пусть в СОК задано число . По формуле (5) получаем . По формуле (2) динамический диапазон СОК М = 210 делится на 2 равные части: - для положительных чисел и - для отрицательных чисел. Найденное число попадает во вторую часть диапазона, соответствующую отрицательным числам. Тогда искомое число равно . В данном примере показан принцип преобразования числа из СОК в двоичную систему счисления с учетом его знака. Представление положительных и отрицательных чисел в СОК не изменяет количество чисел в диапазоне , а заменяет интервал представимых в СОК чисел на интервалы и для нечетных и четных , соответственно. Преимущества представления чисел в СОК могут быть сформулированы следующим образом [6]. 1. В СОК отсутствует распространение переноса между арифметическими блоками и числа большой размерности представляются в виде небольших остатков, что приводит к ускорению в обработке данных. 2. При представлении данных с использованием СОК, числа большой размерности кодируются в набор небольших остатков, соответственно уменьшается сложность арифметических устройств в каждом канале модуля, что облегчает и упрощает работу вычислительной системы. 3. СОК является непозиционной системой без отсутствия зависимости между своими арифметическими блоками, следовательно, ошибка в одном канале не распространяется на другие. Таким образом, облегчается процесс обнаружения и исправления ошибок. Несмотря на свои преимущества, СОК имеет ряд недостатков. Основным недостатком СОК является сложность выполнения операций определения знака, сравнения двух чисел, деления и некоторых других. Но все же, несмотря на указанные недостатки, модулярная арифметика может быть эффективно реализована в тех приложениях, где основная доля вычислений приходится на операции умножения в сочетании со сложением и вычитанием [17]. Как будет видно далее, цифровая обработка изображений является именно таким приложением. Особенности применения СОК в обработке изображений Как было сказано ранее, применение СОК является перспективным инструментом для повышения технических характеристик систем цифровой обработки изображений. В данной работе будут рассмотрены изображения в оттенках серого. В таком формате изображение представляет собой прямоугольный массив целых чисел (пикселей). Количество уровней серого являются целыми степенями 2, то есть пиксель представляет яркость или темноту [2]. Таким образом, чем больше число, кодирующее пиксель, тем ярче изображение в этой точке. В стандартных приложениях обработки изображений величины пикселей изображения в оттенках серого кодируются 8-битными числами и находятся в диапазоне причем обозначает черный цвет, белый цвет. Если в результате обработки изображения получается отрицательное число, то оно заменяется на (черный цвет). В случае получения числа, большего чем 255, оно заменяется на 255 (белый цвет). На рис. 1 схематически представлен принцип отображения чисел в цвет пикселя изображения в оттенках серого. Рис. 1. Зависимость цветности пикселя, представленного в оттенках серого, от величины кодового числа. Процесс фильтрации изображения сводится к выполнению операции свертки частей изображения с элементами маски фильтра, которая представляет собой квадратную матрицу коэффициентов фильтра. Пример 2. Предположим, что часть изображения в оттенках серого имеет следующие величины пикселей: . Пусть для обработки используется фильтр увеличения резкости [15]: . В двоичной системе счисления получим следующую величину пикселя после осуществления фильтрации: , где символ означает сумму произведений соответствующих элементов матрицы. Число -1020 получено как сумма произведений соответствующих элементов матриц. Так как отрицательные величины рассматриваются как 0, то в нашем случае -1020 это черный цвет. Как говорилось ранее, при использовании приложений цифровой обработки изображений особое внимание следует уделить выбору правильного набора модулей, который будет в достаточной мере давать динамический диапазон. В [14-15] предлагаются наборы модулей и , соответственно, и утверждается о достаточности их динамического диапазона при цифровой обработке изображений. На примере покажем, что это не всегда корректно. Пример 3. При использовании СОК с модулями , имеем следующий результат для значений из примера 2: . Диапазон СОК равен . Так как полученное число 100 попадает в первую половину диапазона , то оно является положительным в данной СОК, и поэтому в дальнейшем не меняется. Число 100 дает серый цвет обработанного изображения, что не совпадает с результатом, полученным в двоичной системе счисления. Очевидна разница между двумя системами счисления, а именно значения -1020 и 100, дающие разные цвета. Сравнение примеров 2 и 3 показывает, что набор модулей дает искаженный результат фильтрации изображения из-за недостаточного динамического диапазона. В работе [15] используется набор модулей (специальный набор модулей при ), который также считается авторами достаточным для фильтрации. Покажем на примере недостаточность динамического диапазона и для этого набора модулей. Пример 4. Пусть часть изображения в оттенках серого имеет следующие величины пикселей: . Используя тот же самый фильтр, получим в двоичной системе счисления: . Число и поэтому рассматривается как белый цвет в стандартных приложениях обработки изображений. При фильтрации в СОК, с набором модулей , имеем: . Диапазон СОК равен . Число 1275 попадает во вторую часть динамического диапазона СОК: . Поэтому окончательное восстановление числа дает в результате . Полученное отрицательное число дает черный цвет изображения, вместо белого цвета, что показывает некорректный результат фильтрации и при использовании набора модулей . Полученные результаты показывают важность выбора правильного набора модулей, обеспечивающего достаточный динамический диапазон. Использование недостаточного диапазона СОК может привести к неверному результату, поэтому следует использовать критерии определения переполнения. Мы предлагаем следующий критерий определения необходимого диапазона СОК: , (6) где - сумма положительных коэффициентов маски фильтра; - модуль суммы отрицательных коэффициентов маски фильтра. Практическую проверку предложенного критерия будем проводить на тех же типах фильтров, которые были рассмотрены в работах [14-15], а именно на фильтрах повышения резкости и определения контуров изображения. Данные типы фильтров весьма широко используются на практике при цифровой обработке изображений. В то же время матрицы масок таких фильтров имеют весьма удобный вид для работы в СОК, так как в качестве элементов содержат только целые числа [2]. В дальнейшей части работы мы будем использовать два фильтра повышения резкости: , и фильтр определения контуров изображения согласно [2]. Применение предложенного критерия для этих фильтров дает следующие требования к диапазону СОК. Для фильтра : . Для фильтра : . Для фильтра : . Для того, чтобы выполнить самое сильное из вышеперечисленных условий, а именно , нет возможности использовать трехмодульные наборы СОК со всеми модулями, имеющими удобный вид или и требующими не более 4 бит ( ) для представления данных. Необходимо либо использовать трехмодульные наборы с 5-битными модулями , либо увеличить количество модулей СОК до четырех, но при этом остаться в рамках 4-битного представления информации по модулям: . Второй вариант представляется более предпочтительным, так как введение дополнительного модуля увеличит параллельность обработки данных, при этом время выполнения операций сложения и умножения не будет увеличено, так как они будут по-прежнему выполняться в параллельном режиме над 4-битными числами вместо обработки 5-битных чисел в трехмодульных СОК. Поэтому, в дальнейшем, для реализации фильтрации изображений с использованием указанных масок мы будем использовать набор модулей . Все модули данного набора имеют удобный вид для практической реализации операций: , . Диапазон СОК равен и удовлетворяет предложенному критерию (6) для всех фильтров. Покажем корректность выбора этого набора модулей на примерах, использованных выше. Пример 5. Использование СОК с набором модулей для обработки данных из примера 4 дает следующий результат: . Число попадает в первую часть динамического диапазона СОК: и, следовательно, является положительным (в дальнейшем не изменяется). Значению соответствует белый цвет изображения, что в точности совпадает с результатом, полученным в двоичной системе счисления. Пример 6. Использование СОК с набором модулей для обработки данных из примера 2 дает следующий результат: Число попадает во вторую часть динамического диапазона СОК: , то есть является отрицательным числом. Окончательное значение величины числа получается путем вычитания из результата полного диапазона СОК и равно . Числу -1020 соответствует черный цвет в изображении в оттенках серого, что в точности совпадает с результатом, полученным в двоичной системе счисления. Моделирование цифровой обработки изображений в СОК В данном разделе будут описаны результаты моделирования цифровой обработки различных изображений с использованием разных фильтров и разных систем счисления. Для моделирования были использованы СОК с модулями , и , а также традиционная двоичная система счисления. В качестве фильтров использовались следующие маски. Фильтры повышения резкости: и . Фильтр определения контуров: . Далее по тексту эти фильтры будут обозначаться как фильтр-1, фильтр-2 и фильтр-3 соответственно. Все вычисления производились с использованием пакета прикладных программ MATLAB. На рис. 2 показаны результаты применения фильтра-1 к изображению «девушка». Оригинальное входное изображение в оттенках серого показано на рис. 2а. Выходное отфильтрованное изображение в двоичной системе счисления показано на рис. 2б. На рис 2в и рис. 2д показано изображение, обработанное указанным фильтром в СОК с модулями , и . Из рис. 2 видно крайне низкое качество обработки изображения в СОК . Данный факт объясняется слишком малым динамическим диапазоном такой СОК, что приводит к серьезным искажениям пикселей изображения. Результаты работы СОК и визуально неотличимы от изображения, обработанного в двоичной системе счисления. а) б) в) г) д) Рис. 2. Результат обработки фильтром-1 изображения «девушка»: а) исходное изображение, б) изображение, обработанное в двоичной системе счисления, в) изображение, обработанное в СОК , г) изображение, обработанное в СОК , д) изображение, обработанное в СОК . На рис. 3 показаны результаты применения фильтра-2 к изображению «дом». На рис. 3а показано оригинальное входное изображение в оттенках серого. Отфильтрованное изображение в двоичной системе счисления представлено на рис. 3б. Изображения, полученные в результате обработки указанным фильтром в СОК с наборами модулей , и показаны на рис. 3в и рис. 3д соответственно. Снова видно низкое качество обработки при использовании СОК с модулями . Результаты обработки в СОК с модулями и хорошего качества, однако изображение, обработанное в СОК не идентично изображению, полученному при использовании двоичной системы счисления. а) б) в) г) д) Рис. 3. Результат обработки фильтром-2 изображения «дом»: а) исходное изображение, б) изображение, обработанное в двоичной системе счисления, в) изображение, обработанное в СОК , г) изображение, обработанное в СОК , д) изображение, обработанное в СОК . Результаты применения фильтра-3 для обработки изображения «тюльпаны» представлены на рис. 4. На рис. 4а показано исходное изображение в оттенках серого. На рис. 4б представлен результат фильтрации изображения в двоичной системе счисления. Рис. 4в и рис. 4д показывают результаты фильтрации изображения в СОК с модулями , и . Визуально, изображения рис. 4в и рис. 4д не сильно отличаются от изображения рис. 4б, однако в действительности изображения рис. 4г и рис. 4д тождественны изображению рис. 4б, а изображение рис. 4в отличается от рис. 4б. Сравнивая результаты работы фильтров в разных СОК можно сделать вывод, что предложенные в работах [14-15] наборы модулей и , соответственно, могут давать искаженный результат обработки изображения. Это связанно с недостаточностью динамических диапазонов рассматриваемых СОК. Наихудший результат показывает СОК с модулями , так как даже визуально качество обработки в ней изображений фильтрами повышения резкости неприемлемо на практике. С другой стороны, обработка изображения фильтром выделения контуров в этих СОК показала достаточно неплохое визуальное качество. Для количественной оценки качества обработки изображений с использованием разных наборов модулей СОК были использованы две числовые характеристики. 1. PSNR, или пиковое отношение «сигнал-шум» между двумя изображениями (оригиналом и полученным изображением). Вычисляется данная характеристика по формуле , (7) где - средне-квадратическая ошибка сравнения качества восстановленного изображения; - максимальное колебание входного сигнала изображения. а) б) в) г) д) Рис. 4. Результат обработки фильтром-3 изображения «тюльпаны»: а) исходное изображение, б) изображение, обработанное в двоичной системе счисления, в) изображение, обработанное в СОК , г) изображение, обработанное в СОК , д) изображение, обработанное в СОК . Так как величина имеет логарифмическую природу, единицей ее измерения является децибел (Дб). Чем больше величина , тем лучше качество восстановленного изображения, для тождественно равных изображений . При исследовании алгоритмов сжатия и очистки от шума изображений в оттенках серого практически пригодной считается величина , изменяющаяся в пределах от 20 Дб до 50 Дб [18-19]. Для рассматриваемых нами случаев фильтрации в СОК с разными наборами модулей вычислялась величина между изображением, полученным при использовании традиционной двоичной системы счисления и изображением, полученным с использованием СОК. 2. SSIM, или индекс структурного сходства между двумя изображениями, определяется на основе полного сопоставления исходного и полученного изображений [20]. Данная характеристика вычисляется по формуле: , (8) где - среднее значение ; - среднее значение ; - дисперсия ; - дисперсия ; - ковариация и ; , - две переменных; - динамический диапазон пикселей; и константы. Величина SSIM находится в пределах между и , она равна для тождественно равных изображений. Для рассматриваемых нами случаев фильтрации в СОК с разными наборами модулей вычислялась величина между изображением, полученным при использовании традиционной двоичной системы счисления и изображением, полученным с использованием СОК. В таблице представлены результаты оценки качества обработанных изображений фильтрами (1-3) в СОК с использованием различных наборов модулей. Анализируя полученные результаты, можно сделать вывод, что набор модулей показывает абсолютно точный результат отфильтрованного изображения, во всех случаях совпадающий с результатом обработки в двоичной системе счисления. Таблица. Результаты моделирования обработки изображений в СОК с различными наборами модулей. Изображение Фильтр Модули СОК PSNR, Дб SSIM PSNR, Дб SSIM PSNR, Дб SSIM «Девушка» Фильтр-1 1.5188 0.1384 1 1 Фильтр-2 1.5304 0.1255 43.3496 0.9998 1 Фильтр-3 29.8721 0.9806 1 1 «Дом» Фильтр-1 4.3506 0.1010 1 1 Фильтр-2 4.1741 0.0535 23.2278 0.9879 1 Фильтр-3 27.6603 0.9683 1 1 «Тюльпаны» Фильтр-1 3.2489 0.0963 1 1 Фильтр-2 3.2068 0.0628 42.1221 0.9997 1 Фильтр-3 35.2163 0.9899 1 1 Набор модулей , предложенный в работе [14], дает приемлемый результат ( ) при использовании фильтра выделения контуров (фильтр-3) и плохой результат ( ) при использовании фильтра-1 и фильтра-2. Применение набора модулей не гарантирует корректной работы фильтров повышения резкости и может ограниченно применяться при выделении контуров изображения. Набор модулей из работы [15] не показал ошибок при фильтрации изображений фильтром-1 и фильтром-3. При использовании фильтра-2 качество изображения ухудшалось, но оставалось на приемлемом уровне ( ) для практического применения. Следует, однако, учесть, что возникновение ошибок при использовании СОК с модулями теоретически возможно (см. пример 4) и при фильтрации фильтром-1 и при фильтрации фильтром-3. Отсутствие ошибок в обработке данных изображений объясняется отсутствием резких переходов в значениях соседних пикселей от 0 до 255 и обратно, чего может и не случиться при обработке каких-либо других изображений. Заключение В статье проведен анализ работы наборов модулей СОК при цифровой фильтрации изображений в оттенках серого различными фильтрами. Показано, что ошибки фильтрации изображений в СОК возникают из-за недостаточного динамического диапазона системы. Использование предложенного критерия выбора динамического диапазона СОК позволяет устранить ошибки фильтрации, возникающие из-за переполнения динамического диапазона системы. Для рассмотренных фильтров повышения резкости и выделения контуров корректным оказался предложенный набор модулей , что было наглядно подтверждено при фильтрации конкретных изображений. Результаты обработки изображений предложенным набором модулей в точности совпали с результатами обработки в обычной двоичной системе счисления, в то время как предложенные другими исследователями наборы модулей и могут приводить к ошибкам. Использование масок фильтров с другими коэффициентами может потребовать выбора других модулей СОК, однако с практической точки зрения наиболее целесообразно использовать модули вида , и . При этом модуль вида необходимо выбирать максимально большим, так как такой вид модуля наиболее прост при практической реализации вычислений. Интересным направлением дальнейших исследований в области цифровой обработки изображений с применением фильтров в СОК является поиск наиболее эффективного количества модулей. В настоящее время наиболее широко применяются 3-х, 4-х и 5-ти модульные СОК в разных приложениях, однако вопрос о наиболее эффективном наборе модулей как в общем случае, так и для применения в цифровой обработке сигналов, остается открытым.

About the authors

Nikolay Ivanovich Chervyakov

North-Caucasus Federal University

Email: k-fmf-primath@stavsu.ru

Pavel Alekseyevich Lyakhov

North-Caucasus Federal University

Email: ljahov@mail.ru

Diana Ivanovna Kalita

North-Caucasus Federal University

Email: diana.kalita@mail.ru

References

Supplementary files