. (18)
При распараллеливании вычислительного процесса МКР по элементам сетки будет работать итерационная схема в соответствии с выражением (17), при реализации каждой итерации циклическими переборами (по элементам сетки) будет работать итерационная схема (18).
Завершение итерационного процесса можно производить по критерию невязки, вычисляемой как сумма разностей всех значений элементов (без граничных условий) для соседних итераций и :
, (19)
где: и - соответственно размеры изображения.
5. Повышение эффективности сжатия с учётом специфики цифрового сигнала
Как уже было отмечено, многообразие цифровых сигналов очень велико, как велико и разнообразие методов сжатия. При сжатии с потерями различны требования, предъявляемые к допустимой потере информации. Значительным фактором успешного сжатия цифровых сигналов является выбор наиболее подходящего способа. Сжатие на базе анализа дифференциальной структуры может быть наиболее эффективно применено к сигналам (в частности к изображениям), содержащим значительные поля градиентных переходов амплитуды и достаточно контрастные (с точки зрения изменения амплитуды) границы таких полей. К сигналам подобного вида можно отнести изображения с чёткими границами объектов и значительными областями градиентного или однотонного наполнения. Примером изображений подобного вида могут быть:
- высококонтрастные фотографии технических или иных объектов, содержащие контрастные контуры и однотонные или градиентные поля;
- некоторые виды высококонтрастных космических фотографий, в том числе фотографий поверхности планет;
- картографические изображения;
- рисованные изображения с контрастными границами объектов;
- текстурные изображения;
- некоторые виды изображений, синтезируемые с помощью машинной графики и др.
Исследования сжатия изображений с помощью анализа дифференциальной структуры позволили определить дополнительные преобразования, применение которых способствует эффективности сжатия.
При выборе в качестве анализирующего уравнения - уравнение Пуассона (5), (6), которое может способствовать формированию более компактного паттерна по сравнению с уравнением Лапласа, необходимо определить его правую часть. В качестве правой части можно использовать матрицу определённых значений, сформированную по исходному изображению, разделённому на области, например, пикселей. Значения матрицы могут быть получены выбором минимальной амплитуды из поля (), такой подход в большинстве случаев, позволит корректировать плотность распределения значений амплитуд в паттерне таким образом, что к нему можно более эффективно применять статистическое сжатие.
В случае сжатия фотоизображений, возможно, применять специальную обработку для удаления из исходного изображения шума возникающего, например, в результате дефектов ПЗС-матрицы (сокращение от прибор с зарядовой связью).
Формирование копии изображения в результате операции свертка с функцией рассеяния точки (ФРТ) и последующее использование этой копии для анализа дифференциальной структуры, при этом в паттерн сохраняются в качестве граничных условий элементы исходного изображения. Использование свёртки при сжатии в некоторых случаях позволяет повысить визуальное качество восстановленного сигнала. Низкочастотная фильтрация изображения позволяет исключить из паттерна случайный шум, например, свойственный цифровым фотографиям. Отрицательной стороной применения низкочастотных фильтров, является возможная потеря полезной информации из области высоких частот, например, мелких деталей изображения. В некоторых случаях может быть полезным применение высокочастотных фильтров подчёркивающих границы объектов на изображении. Практические исследования показали, что для реальных целей повышения эффективности сжатия с помощью свёртки необходимо использовать функции рассеяния точки размером или .
Использование, для анализа дифференциальной структуры, производных высших порядков и различных шаблонов дифференцирования так же позволяет в некоторых случаях повысить эффективность сжатия. Выбор вида дифференциального уравнения в значительной мере зависит от особенностей изображения. Эксперименты показали, что изображения, полученные в результате фотографирования, отображения реальных и многих синтезированных объектов хорошо анализируются с помощью производных второго порядка, для них хорошо работают уравнения Лапласа и Пуассона.
На изображении (рис. 5) приведён пример потери полезной информации о форме сигнала в области, где мало значение второй производной. Наиболее уязвимы с точки зрения потери информации области, где происходит плавное изменение функции сигнала, особенно критичным это может быть для областей, где меняется знак первой производной. Противодействовать потери такой информации может включение в паттерн локальных минимумов и максимумов сигнала.
Рис. 5. Потеря информации о сигнале при малых значениях второй производной. На изображении обозначены: a.) - исходный сигнал ; b.) - вторая производная ; c.) - паттерн ; d.) - восстановленный сигнал .
Ниже приведен код фрагмента программы для формирования паттерна (листинг 2). По сравнению с программой (листинг 1) в код (листинг 2) добавлена свёртка, в качестве примера задана ФРТ называемая «скользящего среднего» подавляющая высокие частоты сигнала, в том числе случайные шумы и усиливающая сигнал до 9 раз. Размер квадратной матрицы ФРТ в данном примере хранится в константе psfxy. При практической реализации для большей функциональности ФРТ с размером psfxy можно динамически изменять (например, передавать в качестве параметра), что позволит задавать для различных типов сигналов различные ФРТ и формировать наилучший паттерн с точки зрения минимизации размера сжатого паттерна при максимуме качества восстановленного сигнала. Для цифровых фотографий содержащих контрастные объекты и однотонные поля, с присутствием случайных шумов, достаточно хорошие результаты формирования паттерна и последующего сжатия показала приведённая в программе (листинг 2) ФРТ «скользящего среднего». Обратим внимание, что в паттерн копируются не результаты свёртки изображения, а элементы исходного изображения, что позволяет оставить больше исходной информации и получить более качественный результат при восстановлении. Свёртка с заданной ФРТ производит размытие полей и границ, что в свою очередь позволяет учесть в паттерне не только элементы самих границ, но и более удалённые от границ элементы. На цифровых фотографиях и подобных им цифровых сигналах, значения элементов изображения, образующие границы объектов, могут иметь значительные отличия от значений элементов внутри или снаружи границы, поэтому в качестве граничных элементов необходимо выбирать элементы вблизи границ, близкие по значениям к элементам ограниченной области. В примере (листинг 2) в результате свёртки значения элементов результата свёртки могут существенно превышать (до девяти раз) значения элементов исходного сигнала. Нормирование динамического диапазона или использование не целочисленных коэффициентов ФРТ будет увеличивать время вычисления, более эффективным, с точки зрения скорости вычислений, является изменение значений -критериев (delLo, delAv, delHi) до соответствующей величины с учётом коэффициентов матрицы ФРТ.
Листинг 2. Фрагмент программы формирования паттерна с предварительной свёрткой полноцветного изображения (C++).
//====================================================
...
// цветовая палитра
// покомпонентное представление, в скобках указаны компоненты
// палитр (RGB) и (YCbCr) соответственно
struct ColorSpace {
uchar byteLo; // компонента младший байт (Lower) (R) (Y)
uchar byteAv; // компонента средний байт (Average) (G) (Cb)
uchar byteHi; // компонента старший байт (Hight) (B) (Cr)
};
// структура для сохранения цветов в виде int
struct IImage {
int iLo; // компонента младший "байт" (Lower) (R) (Y)
int iAv; // компонента средний "байт" (Average) (G) (Cb)
int iHi; // компонента старший "байт" (Hight) (B) (Cr)
};
...
uint jmax=Xsize-1; // размер изображения по X минус единица
uint imax=Ysize-1; // размер изображения по Y минус единица
uint ix, iy, tix, tiy, nzero; // счётчики
const int psfxy=3; // размеры функции рассеяния точки ФРТ
// матрица ФРТ (PSF - point spread function)
int pulse[psfxy][psfxy]={{1, 1, 1},
{1, 1, 1},
{1, 1, 1}};
// выделяем память для образца копии изображения
IImage** itemp2d=new IImage*[imax+psfxy];
for (unsigned int i=0; i<imax+psfxy; i++){
itemp2d[i]=new IImage[jmax+psfxy];
memset(itemp2d[i], 0, sizeof(IImage)* (jmax+psfxy));
}
// производим 2D быструю свёртку в целочисленной арифметике
for (int iyd=0; iyd<(int)Ysize; iyd++){
for (int ixd=0; ixd<(int)Xsize; ixd++){
// проход по импульсу
for (int iyp=0; iyp<psfxy; iyp++){
iy=iyd+iyp;
for (int ixp=0; ixp<psfxy; ixp++){
ix=ixd+ixp;
itemp2d[iy][ix].iLo+=pulse[iyp][ixp]*(int)data[iyd][ixd].byteLo;
itemp2d[iy][ix].iAv+=pulse[iyp][ixp]*(int)data[iyd][ixd].byteAv;
itemp2d[iy][ix].iHi+=pulse[iyp][ixp]*(int)data[iyd][ixd].byteHi;
}
}
}
}
// формируем паттерн
// копируем угловые точки с заменой нулей на единицы
swap(pattern[0][0], data[0][0]);
swap(pattern[0][jmax], data[0][jmax]);
swap(pattern[imax][0], data[imax][0]);
swap(pattern[imax][jmax], data[imax][jmax]);
for (iy=1; iy<imax; iy++){
// координата по y для массива результат свёртки itemp2d
tiy=iy+(psfxy>>1);
// копируем крайние столбцы
// с заменой нулей на единицы
swap(pattern[iy][0], data[iy][0]);
swap(pattern[iy][jmax], data[iy][jmax]);
for (ix=1; ix<jmax; ix++){
// координата по x для массива результат свёртки itemp2d
tix=ix+(psfxy>>1);
if (iy==1){
// на первом проходе копируем крайние строки
// с заменой нулей на единицы
swap(pattern[0][ix], data[0][ix]);
swap(pattern[imax][ix], data[imax][ix]);
}
int tLo=abs(itemp2d[tiy-1][tix].iLo+itemp2d[tiy+1][tix].iLo+
itemp2d[tiy][tix-1].iLo+itemp2d[tiy][tix+1].iLo-
(itemp2d[tiy][tix].iLo<<2));
int tAv=abs(itemp2d[tiy-1][tix].iAv+itemp2d[tiy+1][tix].iAv+
itemp2d[tiy][tix-1].iAv+itemp2d[tiy][tix+1].iAv-
(itemp2d[tiy][tix].iAv<<2));
int tHi=abs(itemp2d[tiy-1][tix].iHi+itemp2d[tiy+1][tix].iHi+
itemp2d[tiy][tix-1].iHi+itemp2d[tiy][tix+1].iHi-
(itemp2d[tiy][tix].iHi<<2));
// обработка внутренних элементов
// сравнение с ?-критериями по каждому цветовому каналу
if ((tLo<=delLo && tAv<=delAv && tHi<=delHi)){
// установка признака исключения элемента из паттерна
// (не являются краевыми условиями)
pattern[iy][ix].byteLo=0;
pattern[iy][ix].byteAv=0;
pattern[iy][ix].byteHi=0;
nzero+=3; // счётчик исключённых из паттерна элементов
} else {
// элементы паттерна с нулевыми значениями, корректировка
if (!pattern[iy][ix].byteLo){
pattern[iy][ix].byteLo=1;
}
if (!pattern[iy][ix].byteAv){
pattern[iy][ix].byteAv=1;
}
if (!pattern[iy][ix].byteHi){
pattern[iy][ix].byteHi=1;
}
}
}
}
// чистим память
if (itemp2d && sizeY()){
for (ix=0; ix<imax+psfxy; ix++)
delete[]itemp2d[ix];
delete[]itemp2d;
itemp2d=0;
}
...
// Функция swap
// копирование точки (в трёхцветной палитре с заменой нулей на единицы)
inline void swap(ColorSpace& receiver, ColorSpace& source){
// делаем проверку и при необходимости заменяем нули единицей
receiver=source; // копируем
if (!receiver.byteLo){
receiver.byteLo=1;
}
if (!receiver.byteAv){
receiver.byteAv=1;
}
if (!receiver.byteHi){
receiver.byteHi=1;
}
}
...
//=====================================================
6. Вычислительная оптимизация МКР на базе отыскания промежуточного решения
дифференциальный цифровой сигнал сжатие
При восстановлении сжатых данных немаловажным фактором является скорость. МКР достаточно медленный итерационный способ решения дифференциальных уравнений, следовательно, значительное время может быть затрачено для решения многомерных задач. Поэтому существенным вопросом является оптимизация вычислений.
Известен способ сокращения времени вычислений МКР для мягких дифференциальных уравнений [12] в некоторой области с краевыми (граничными для физических областей и начальными для времени) условиями в областях , сущность которого состоит в укрупнении шага сетки в области . При этом происходит потеря точности решения вплоть до того, что оно становится непригодным. Например, в основной задаче электростатики могут быть рассмотрены электрические заряды, описанные единственной точкой. При укрупнении сетки такие граничные условия могут быть потеряны, что принципиально меняет сущность промежуточного решения. При формировании паттерна могут возникать краевые условия, например, в виде уединённой точки. Таким образом, для наших задач потеря точности в результате укрупнения сетки так же актуальна.
По этой причине обычным является решение, содержащее несколько последовательно применяемых сеток. Первоначально применяется самая крупная сетка , позволяющая получить приближение решения. Затем решение уточняют, последовательно применяя сетки с меньшим шагом . Общее число различных сеток обычно составляет 2-3. Шаг сетки может быть различным в разных направлениях и областях сетки . Таким образом, ускорение процедуры сходимости к решению задачи с заданной точностью происходит за счет более быстрого формирования некоторого промежуточного решения в области , что является прямым следствием теоремы о сходимости разностного решения [13]. При этом каждое уточнение решения является итерационным, имеющим вычислительную сложность
, (20)
где: - размерность рассматриваемой задачи; - число узлов сетки в каждом направлении; - число итераций, обеспечивающее заданную точность на данном этапе. В многомерных задачах величина (20) может быть очень велика даже при разреженной сетке.
Указанную задачу нахождения промежуточного (приближённого) решения в области можно решить путем аппроксимации значений уравнения (8). Аппроксимацию можно производить различными функциями, в зависимости от физической сущности задачи, например, многочленом вида:
, (21)
где - коэффициенты многочлена; - переменная, вдоль которой происходит аппроксимация.
В общем случае, если линии сетки не параллельны координатным осям, образующим пространство , то может не совпадать с набором переменных исходной задачи. В этом случае необходимо учитывать поворот системы координат, в которых рассмотрен аргумент , относительно исходной системы координат. В случае -мерной () задачи, аппроксимирование необходимо производить последовательно для всех линий, образующих сетку в каждом направлении, с последующей оценкой средних значений для каждого узла сетки. Среднее значение узла сетки вычисляется как среднее значение аппроксимации в точках линий сетки, принадлежащих данному узлу. В определенном смысле можно говорить, что для нахождения некоторого промежуточного решения задача МКР разбивается на множество одномерных задач МКЭ, число которых равно числу линий сетки МКР.
Возможно совместное применение способа укрупнения сетки и предлагаемого способа, ведь даже для укрупненной сетки процесс ускорения сходимости остается актуальным. В общем случае применение предложенного способа ускорения сходимости должно производиться с учетом физической сущности процессов и условий каждой конкретной задачи. При укрупнении сетки используются не все граничные условия, а только их часть, поэтому можно также использовать некоторые усредненные граничные условия. В этом случае, фактически для получения новых граничных условий, будет применен предложенный способ, но в локальной области.
Промежуточное решение, полученное предлагаемым способом [14,15], в некоторых случаях (в зависимости от особенностей граничных условий), может быть «не очень» гладким. На практике возможно применение некоторых дополнительных действий, повышающих гладкость. Например, при аппроксимации возможен учет (с некоторыми весовыми коэффициентами) значений в соседних узлах, не вошедших в качестве значения или аргумента в функцию аппроксимации, применяемую к данной линии сетки.