Содержание к диссертации
Введение
2. Выбор направления исследований, анализ математического содержания задач цифровой обработки изображений, требования к аппаратурно-ориентированным алгоритмам 13
2.1. Анализ требований, предъявляемых к алгоритмам, ориентированным на аппаратную реализацию
2.2. Классификация задач цифровой обработки изображений и анализ математического содержания унитарных преобразований, применяющихся при их решении 41
2.3. Анализ методов вычислений и определение критериев оценки разрабатываемых алгоритмов 68
2.4. Дискретные линейные "преобразования в качестве альтернативного подхода при аппаратурной реализации ДКП 73
2.5. Выбор аппаратурных методов для реализации типовых вычислительных процедур ДК
2.6. Выводы 85
3. Разработка и исследование аппаратурно-ориентированных алгоритмов дискретных косинусных преобразований 86
3.1. Синтез алгоритмов типовых процедур реализации ДКП.
3.2 Разработка алгоритмов ДКП, оптимизированных под операции ЦОИ функционирующих в жестких временных ограничениях 101
3.3. Методика оценки погрешностей обработки изображений вносимых вычислительной структурой обобщенной линейной фильтрации
3.3.1. Методика оценки погрешностей дискретизации и восстановления непрерывных изображений. 111
3.3.2. Погрешности при квантовании непрерывных изображений по уровню и временной дискретизации 116
3.3.3. Модели равномерной временной дискретизации, учитывающие способ получения цифрового эквивалента непрерывного изображения 127
3.4. Методика анализа погрешностей ДКП построенного на базе типовых и модифицированных процедур ДЛП. 131
3.5. Выводы 144
4. Вопросы реализации и анализа основных параметров разработанных алгоритмов
4.1. Варианты реализации вычислительных структур, использующих разработанные алгоритмы. Параметры аппаратурных реализаций алгоритмов ДКП 145
4.2. Характеристики типовых схем, применяемых при построении аппаратурных блоков ДКП 153
4.3. Сравнительный анализ основных показателей алгоритмов ДКП, разработанных на основе типовыхи модифицированных вычислительных процедур ДЛП.. 164
4.4. Выводы 191
5. Заключение 194
Список использованных источников 196
Приложение -. 203
Документы, подтверждающие внедрение результатов диссертации
- Классификация задач цифровой обработки изображений и анализ математического содержания унитарных преобразований, применяющихся при их решении
- Разработка алгоритмов ДКП, оптимизированных под операции ЦОИ функционирующих в жестких временных ограничениях
- Модели равномерной временной дискретизации, учитывающие способ получения цифрового эквивалента непрерывного изображения
- Характеристики типовых схем, применяемых при построении аппаратурных блоков ДКП
Классификация задач цифровой обработки изображений и анализ математического содержания унитарных преобразований, применяющихся при их решении
В отличие от системы с зональным кодированием, пороговое кодирование устанавливает единую шкалу квантования для всех спектральных коэффициентов. Важным моментом в процессе порогового кодирования является точное указание позиций значащих коэффициентов, прошедших пороговый отбор. Для этого проще всего указывать количество исключенных коэффициентов, разделяющих соседние значащие коэффициенты. В этом случае алгоритм кодирования длин серий можно представить в следующем виде.
Первому элементу каждой строки ставится в соответствие слово, определенную часть которого занимает маркер старта содержащий только нули или единицы.
Второе и последующие кодовые слова представляют в виде объединения двух двоичных чисел, одно из которых содержит значение коэффициента,. а второе указывает количество исключенных коэффициентов, отделяющих данный значащий коэффициент от предыдущего 3. Б том случае, если в пределах установленной максимальной длины серии не будет обнаружен очередной значащий коэффициент, то обеим частям кодового слова присваивается значения все единицы или нули, чтобы указать переполнение.
По сравнению с зональным кодированием, пороговое кодирование дает лучшие результаты по критериям среднеквадратической ошибки и коэффициента сжатия, что объясняется его адаптивным характером. Однако непосредственное применение этого подхода без учета особенностей цифрового канала передачи данных не эффективно, так как длина получаемых с его помощью блоков различна. Предложим способ, позволяющий повысить эффективность передачи сжатой видеоинформации за счет перераспределения коэффициентов между пакетами передачи. Учитывая влияние размера блока обработки ДКП на величину среднеквадратической ошибки /32/, устанавливаем его минимальный размер в виде матрицы 8x8 элементов. Таким образом, при вычислении ДКП исходного изображения не превышающего 2048x2048 элементов будет получена матрица блоков не более 256x256 по 64 значения. В третьем пункте типовой процедуры порогового кодирования заметно дублирование маркера переполнения серии этот факт можно использовать для передачи полезной информации. Так как первый элемент обработанного блока изображения всегда содержит среднее значение всех элементов блока, то для реального кадра максимальное количество исключенных коэффициентов не превысит 63, для чего необходимо зарезервировать шесть двоичных разрядов. Для отличия стартовой позиции, в поле количества исключенных элементов дополнительно резервируется старший седьмой разряд. В этом случае пакеты для входного буфера модема формируются следующим алгоритмом кодирования. 1. В кодовом слове первого элемента строки блоков, устанавливаем седьмой бит в единицу, а отведенные разряды для указания количества исключенных коэффициентов обнуляем. 2. Второе и последующие кодовые слова также как в классической схеме кодирования, представляют в виде объединения двух двоичных чисел, одно из которых содержит значение коэффициента, а второе указывает количество исключенных коэффициентов, отделяющих данный значащий коэффициент от предыдущего. Полученные кодовые слова, по мере поступления, накапливаются в буферной памяти общим объемом в три и более блоков. Седьмой бит служебного поля синхронизации обнуляется. 3. Если в пределах блока не будет обнаружен очередной значащий коэффициент, тогда необходимо установить седьмой бит служебного поля в единицу, а в позицию, отведенную под указание количества исключенных коэффициентов, занести номер блока в строке. Разряды, отведенные на передачу значения коэффициента ДКП, распределяются следующим образом: два бита дополняют шесть разрядов отведенных под указатель номера блока в строке; восемь бит на указатель строки в текущем кадре; один бит принадлежности к текущему или предыдущему кадру. 4. Если за время передачи предыдущего пакета по цифровой линии связи в буфере модема или сетевого адаптера формируется недостаточное количество данных, тогда в зависимости от числа недостающих слов из буфера кодировщика переноситься дополнительный блок. 5. При приближении количества накопленной в буферной памяти кодировщика информации к размеру пакета она передается в первую очередь, а текущая помещается на ее место. Размер буферной памяти ограничивается снизу размером пакета, а сверху максимально допустимым временем межблочной задержки. Несмотря на то, что использование указанного алгоритма увеличивает аппаратурную сложность системы, но в целом этот недостаток компенсируется эффективным использованием канала передачи данных.
Разработка алгоритмов ДКП, оптимизированных под операции ЦОИ функционирующих в жестких временных ограничениях
Известно множество приложений, применяющих . цифровую обработку дискретных изображений в режиме "реального" времени. В таком случае подразумевают такую работу вычислительного устройства, при которой через определенные промежутки времени выполняется три основных цикла: выдача готового решения предыдущего такта обработки; прием новых исходных данных; собственно такт обработки.
Необходимость решения задач в режиме "реального" времени предъявляет высокие требования к производительности вычислительных систем. Уровень этих требований определяется сложностью поиска решения задач и значением t.
Алгоритмы реставрации и улучшения изображений, алгоритмы анализа изображений, осуществляющие распознавание образов, и другие алгоритмы ЦОИ требуют решения от нескольких задач до нескольких тысяч задач в секунду в зависимости от используемого алгоритма, поставленных целей и необходимой точности решения. При обработке изображений повышенной сложности, размерность обрабатываемых матриц доходит до 104-105 и выше. Известен также целый ряд проблем, не требующих нахождения решения задач в "реальном" режиме времени, но связанных с обработкой матриц большого размера. Примерами таких задач могут служить задачи мультипликации, геологоразведки, метеорологии, полиграфии и другие, для которых характерно предварительное накопление больших объемов информации с последующей ее обработкой. Оценка требований к производительности вычислительных систем для решения указанных задач, а также для решения задач ЦОИ в режиме "реального" времени приведена в таблице 2.1. Представленные в таблице 2.1 данные, получены для размерностей обрабатываемых изображений порядка 1024x1024 и разрядности операндов равной 32, на основе операционной сложности методов ЦОИ, рассмотренных в разделе 2.2.1 и оценок, приведенных в /1/. Как видно из таблицы 2.1, для решения задач анализа и кодирования изображений различными методами, необходимо обеспечить производительность вычислительных устройств в диапазоне 1,4 1010 - 1,4 1014 операций с плавающей запятой в секунду. Большинство универсальных ЭВМ общего назначения по причине существования технологических ограничений не в состоянии обеспечить указанную производительность. Низкая скорость выполнения преобразований создает неудобства и обходится сравнительно дорого, но может устраивать специалистов, занимающихся разработкой и отладкой . новых алгоритмов и методов обработки изображений. К сожалению,, такие затраты времени на вычисление неприменимы в большинстве возможных прикладных приложениях. Использование параллельных и конвейерных специализированных вычислительных систем, может помочь при решении данной проблемы. Подобные системы отображают алгоритм решения задачи непосредственно на уровне аппаратной структуры. Рассмотрим процесс решения задачи на универсальной ЭВМ и с применением указанного подхода, показанного на рис. 2.8. На первым этапе решения поставленной прикладной задачи на универсальной ЭВМ составляется её описание на естественном языке. Далее выполняется математическая формулировка задачи (постановка задачи) и выбор соответствующих типовых подзадач. Затем осуществляется выбор типовых вычислительных процедур реализующих необходимые подзадачи и отображение алгоритма на структуру вычислительной системы. На конечном этапе происходит выполнение алгоритма на имеющейся вычислительной структуре. Арифметико-логическое устройство универсальных ЭВМ выполняет, как правило, лишь элементарные операции типа сложения и сдвига, а более сложные организуются на микропрограммном уровне, т.е. посредством выполнения встроенных подпрограмм. При таком подходе, выбор типовых подзадач, процедур и отображение алгоритма на структуру вычислительной системы осуществляется на этапе программирования. Нетрудно предположить, что время решения задачи на такой ЭВМ непосредственно зависит от длины программы и её структуры. Можно заметить, что укрупнение математической функции выполняемой аппаратно, уменьшает длину программы и количество выборок инструкций из памяти, и как следствие уменьшает время решения и увеличивает производительность. В настоящее время, в связи с увеличением степени интеграции, ярко выраженной тенденцией удешевления производства СБИС с и уменьшением времени переключения транзисторов перспективным направлением является разработка специализированных СБИС, реализующих более крупные математические задачи. Осуществляется переход от аппаратурной реализации элементарных операций (сложения, сдвига) к аппаратурной реализации макроопераций {вращения, отражения, и даже таких крупных, как ДКП).
Под аппаратурной реализацией понимается одномоментное выполнение алгоритма без возможности его дробления со стороны программиста. Аппаратурная реализация алгоритма может рассматриваться как структурное программирование вычислительного процесса. При этом программа представляет собой граф соединений аппаратных модулей из заданного набора. Отображение алгоритма на структуру вычислительной системы в отличие от универсальных ЭВМ осуществляется на этапе проектирования системы.
Такое структурное программирование является альтернативой традиционному процедурному программированию, при котором определяется последовательность во времени действий и состояний в одном процессоре.
Модели равномерной временной дискретизации, учитывающие способ получения цифрового эквивалента непрерывного изображения
Время выполнения одной итерации алгоритма (2.5.3) при аппаратурной реализации приближается к времени выполнения одного сложения.
Алгоритмы ДЛП удовлетворяют большинству требований, перечисленных в разделе 2.4. Точность вычислений в методах ДЛП линейно зависит от разрядности операндов и достигается увеличением числа итераций. Численная устойчивость гарантируется ортогональностью выполняемых преобразований. В этом отношении блоки, построенные на известных алгоритмах ДЛП вращений, предпочтительнее традиционных процессорных элементов, включающих быстрые умножители, делители и сумматоры. Если, например, рассмотреть матрицу оператора ДКП /1/, то при реализации преобразования с использованием стандартных умножителей как обычной процедуры умножения матрицы на вектор, мы имеем дело с 4-мя числовыми параметрами, а в случае реализации в виде ДЛП в силу особенностей метода фактически имеется один числовой параметр - угол а, что предпочтительнее из соображений численной устойчивости /8/. Сходимость известных методов ДЛП линейная, а для некоторых - квадратичная. Алгоритмы ДЛП имеют направленные регулярные графы, о чем свидетельствуют выражения (2.5.1-2.5.3). Эти алгоритмы рекурсивны, каждая итерация выполняется в алгоритмах ДЛП за одинаковое время. Данные в алгоритмах ДЛП последовательно передаются с этапа на этап. В ДЛП методах обеспечивается побитовая рекурсия, они позволяют на каждой итерации получать очередной разряд (цифру) результата, поэтому такие методы получили название - "цифра за цифрой". Указанные свойства делают методы ДЛП пригодными для организации конвейеров как при параллельной обработке всех разрядов числа, так и при последовательной обработке по битам.
Два основных режима алгоритмов ДЛП, режим вращения (или режим применения преобразования) и векторизации, аналогичные соответствующим режимам CORDIC, позволяют параллельно обрабатывать ведущие столбцы (те, в которых на данном шаге обнуляются соответствующие компоненты) и остальные столбцы матриц, для которых ищутся необходимые разложения. В отличие от обычных методов выполнения типовых преобразований, для методов ДЛП не требуется предварительного вычисления параметра (или параметров) преобразования, поскольку в режиме векторизации одновременно осуществляется и расчет параметра, и само преобразование. Выполняемое на /-той итерации алгоритма элементарное преобразование задается направлениями (знаками Ъ,ц так как остальные параметры в матрицах AL фиксированы), которые могут непосредственно передаваться из блоков, выполняющих векторизацию в главных столбцах, блокам, выполняющим то же элементарное преобразование в режиме вращения (применения преобразования) для остальных столбцов. Эта особенность алгоритмов ДЛП делает их пригодными для параллельных систем, как в случае реализации каждой итерации алгоритма на отдельной ступени конвейера/ так и в случае реализаций всех итераций на одной аппаратуре (последовательная реализация).
Алгоритмы ДЛП имеют ограниченный набор операций, который фактически сводится к операциям сложения, вычитания, сдвига, определения и изменения знака. Исключением является процедура масштабирования (нормализации), которая может выполняться для векторов в целом или даже для всей преобразованной матрицы в зависимости от реализуемого метода ЛА. Известны варианты реализации ДЛП без масштабирования /16/.
Методы ДЛП пригодны не только для выполнения типовых ортогональных процедур, но также и для выполнения операций умножения, деления, извлечения квадратного корня (линейная функция CORDIC). При этом указанные операции выполняются медленнее, чем на специализированных аппаратных умножителях, однако, если в системе требуется выполнять и базовые унитарные преобразования, и вычислять тригонометрические функции, и выполнять умножение/деление, -блоки ДЛП являются наиболее универсальным вариантом для-выполнения всего набора процедур.
Таким образом, итерационные методы ДЛП позволяют строить специализированные устройства с достаточно высоким быстродействием и умеренными аппаратными затратами и обеспечивают при этом требуемую точность. Они в достаточной степени отвечают приведенным ранее требованиям и могут быть использованы для реализации необходимых вычислительных процедур.
К настоящему времени известно большое число основных алгоритмов ДЛП и их модификаций для выполнения типовых ортогональных преобразований и некоторых унитарных преобразований /4,5,6,9/.
Вместе с тем, применение ДЛП подхода для выполнения ДКП преобразований изображений, описанных в разделе 2.2.2, еще недостаточно изучено. В данной работе рассматриваются вопросы построения алгоритмов ДЛП оптимизированных для выполнения процедуры ДКП, предлагаются варианты организации вычислительных процедур, проводится сравнительный анализ различных вариантов.
Характеристики типовых схем, применяемых при построении аппаратурных блоков ДКП
Б общем случае аналоговые сигналы от видеокамер являются нестационарными функциями времени. Однако на интервалах времени, достаточно продолжительных (кадрах), эти функции могут рассматриваться как квазистационарные или приводимые к стационарным путем получения центрированного случайного процесса.
В качестве моделей помех обычно используют стационарные случайные процессы /17/. Анализ физики воздействия мешающих факторов на процесс аналого-цифрового преобразования позволяет во многих практических случаях считать помеху X{t) аддитивной и некоррелированной с сигналом x(t). В этом случае на вход АЦП поступает сумма случайных процессов x(t) + A(t) и Дхг(г) = 0.
В дальнейшем будем принимать, что случайные процессы и помехи заданы своими корреляционными функциями. При преобразовании случайных величин известными считаются законы распределения.
Довольно часто при обработке реальных изображений, встречаются кадры видеоинформации со значительными отклонениями спектральных плотностей от ранее принятых. В таких случаях будем использовать «случайные» модели. При случайных моделях преобразуемых сигналов возникает вопрос определения диапазона изменения этого сигнала. Под диапазоном будем понимать интервал изменения преобразуемой величины х от хтЬ до хтш при условии, что вероятность попадания х в этот интервал не менее заданной: где % выбирают из условия выполнения неравенства (3.3.б). Так при нормальном распределении преобразуемый параметр с вероятностью 0,997 расположен в интервале, равном При равномерной плотности вероятности преобразуемый сигнал с вероятностью, равной 1, расположен в интервале yll2-jDx при треугольном законе - 4bijl\ . Для оценки предельных характеристик тракта аналого-цифрового преобразования входные сигналы могут быть заданы детерминированными функциями времени, например линейной функцией, соответствующей максимальной скорости изменения входного сигнала. При заданном максимальном ускорении преобразуемого параметра входной сигнал может быть принят параболическим. Максимальная скорость и ускорение, как правило, могут быть получены при анализе источника видеоизображения, генерирующего данный сигнал. Процесс преобразования непрерывного изображения в дискретное осуществляется с конечной точностью, определяемой методическими и инструментальными погрешностями /20/. Минимизация инструментальных погрешностей связанна с развитием в области полупроводниковой электроники и технологии приборостроения. .. Идеальная операция квантования описывается статической характеристикой нелинейного элемента НЭ, на вход которого подключен аналоговый сигнал хет, а на выходе получаем квантованный хвых (рис. 3.3.1,а). Погрешность квантования Если нелинейный элемент округляет видеосигнал хт в соответствии с характеристиками, приведенными на рис. 3.3.1,6 и в, то максимальная погрешность квантования равна q - шагу квантования по уровню. В том случае, когда округление реализуется нелинейным элементом, имеющим характеристику, симметричную относительно оси ординат (3.3.1,г), максимальное значение погрешности определяется величиной q/2. Эту характеристику можно принять за базовую, так как она уменьшает вдвое максимальную методическую погрешность и может быть получена из первых двух путем подачи на вход НЭ постоянного смещения, равного соответственно ±q/2. Погрешность квантования по уровню для базовой характеристики НЭ функционально связана с входной величиной в соответствии с рис. . ,г следующим образом : где к номер интервала квантования. Рассмотренные характеристики НЭ имеют постоянный шаг квантования по уровню. В общем случае это необязательно. При использовании АЦП как измерителя случайных величин сумма погрешностей квантования и инструментальной полностью определяет точность преобразования. Здесь под измеряемой величиной понимают неизвестный сигнал, значение которого не изменяется во время измерения. Это конечно идеализация. Однако если измеряемый сигнал изменяется достаточно медленно по сравнению со временем преобразования, то его можно принять постоянным. Для обеспечения постоянства сигнала во время преобразования в ряде случаев используются устройства выборки и хранения (УВХ), основная функция которых - выбор мгновенного значения входного сигнала (стробирование) и его хранение его в течение времени преобразования. Если длительностью стробирующего импульса можно пренебречь, то временная дискретизация является квазимгновенной. В том случае, когда требуется учесть время выборки, УВХ может быть представлен запоминающим интегратором, сигнал на выходе которого определяется средним значением преобразуемой функции за время стробирования. Если АЦП видеоакселератора используется совместно с системой автоматического управления видеокамеры, то возникает задача оценки точности преобразования случайной функции. Пусть входной сигнал X it) через отрезки времени Т преобразован в цифровой эквивалент {рис. 3.3.2). На выходе АЦП получаем последовательность ординат случайного процесса.