ABOUT SELECTION OF RESIDUE SYSTEM RANGE FOR IMAGE PROCESSING

Abstract

This work presents research concerned with selection of correct residue system dynamic range for image digital processing problems. We demonstrated incorrect grayscale image processing by using residue system unit sets {5,7,8} and {7,15,16} proposed by other authors, and concluded about their dynamic range insufficiency. We propose criterion for determination residue system dynamic range sufficiency depending on filter mask coefficients. It is shown that using of proposed criterion provides error-free grayscale image processing. We performed grayscale image processing by using residue system by MATLAB software. Analysis of results based on peak signal-to-noise ratio metric and image structural similarity index confirmed conclusions.

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

  1. Tan L., Jiang J. Digital Signal Processing, Second Edition: Fundamentals and Applications. Academic Press, 2013. - 876 p.
  2. Shin F.I. Image processing and pattern recognition: fundamentals and techniques. Wiley-IEEE Press, 2010. - 552 p.
  3. Shahana T. K., James R. K., Jose B. R., Jacob K. P., Sasi S. Performance Analysis of FIR Digital Filter Design: RNS Versus Traditional // ISCIT 2007 International Symposium on Communications and Information Technologies Proceedings, 2007. - P. 1-5. doi: 10.1109/ISCIT.2007.4391974.
  4. Cardarilli G. C., Nannarelli A., Re M. Residue number system for low-power DSP applications // Proc. 41st Asilomar Conf. Signals, Syst., Comput, 2007. - P. 1412-1416. doi: 10.1109/ACSSC.2007.4487461.
  5. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Макоха А.Н. Нейрокомпьютеры в остаточных классах. М.: Радиотехника, 2003. - 272 с.
  6. Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. Imperial College Press, 2007. - 296 p.
  7. Chervyakov N.I., Lyakhov P.A., Babenko M.G. Digital filtering of images in a residue number system using finite-field wavelets // Automatic Control and Computer Sciences. V.48, No.3, 2014. - P. 180-189.
  8. Ammar A., Kabbany A., Youssef M., Amam A. A secure image coding scheme using residue number system // Eighteenth National Radio Science Conference, 2001. - P. 339-405. doi: 10.1109/NRSC.2001.929397.
  9. Wang W., Swamy M. N., Ahmad M. O. RNS application for digital image processing // 4th IEEE International Workshop on System-on-Chip for Real-Time Applications, 2004. - P. 77-80. doi: 10.1109/IWSOC.2004.1319854.
  10. Taleshmekaeil D.K., Mohamamdzadeh H., Mousavi A. Using residue number system for edge detection in digital images processing // IEEE 3rd international conference on communication software and networks, 2011. -P. 249-253. doi: 10.1109/ICCSN.2011.6014044.
  11. Molahosseini A. S., Sorouri S., Zarandi A. A. Research Challenges in Next-Generation Residue Number System Architectures // The 7th International Conference on Computer Science & Education, 2012. - P. 1658-1661. doi: 10.1109/ICCSE.2012.6295382.
  12. Younes D., Steffan P. A comparative study on different moduli sets in residue number system // IEEE International Conference on Computer Systems and Industrial Informatics, 2012. - P. 1-6. doi: 10.1109/ICCSII.2012.6454344.
  13. Wang W., Swamy M. N., Ahmad M. O., Wang Y. A high-speed residue-to-binary converter for three-modul RNS and a scheme for its VLSI implementation // IEEE Trans. on Circuits and Systems-II: Analog and Digital Signal Processing. V.47, No.12, 2000. - P. 1576-1581. doi: 10.1109/82.899659.
  14. Taleshmekaeil D.K., Mousavi A. The use of residue number system for improving the digital image processing // IEEE 10th International Conference on Signal Processing, 2010. - P. 775-780.
  15. Younes D., Steffan P. Efficient image processing application using Residue Number System // 20th International Conference on Mixed Design of Integrated Circuits and Systems, 2013. - P. 20-22.
  16. Parhami B. Computer Arithmetic: Algorithms and Hardware Designs. New York, Oxford University Press, 2010. - 641 p.
  17. Meyer-Baese U. Digital Signal Processing with Field Programmable Gate Arrays. Springer-Verlag Berlin Heidelberg, 2001. - 422 p.
  18. Salomon D. Data Compression / Springer-Verlag London, 2007. - 1092 p.
  19. Huynh-Thu Q., Ghanbari M. Scope of validity of PSNR in image/video quality assessment // Electronics Letters. V.44, No.13, 2008. - P 800-801. doi: 10.1049/el:20080522.
  20. Wang Z. Image quality assessment: from error visibility to structural similarity // IEEE Transactions image processing. V.13, No.4, 2004. - P. 600-612. doi: 10.1109/TIP.2003.819861.

Statistics

Views

Abstract: 39

PDF (Russian): 9

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2016 Chervyakov N.I., Lyakhov P.A., Kalita D.I.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies