ПАРАЛЛЕЛЬНЫЕ  ВЫЧИСЛЕНИЯ  В  ОБРАБОТКЕ  ИЗОБРАЖЕНИЙ

Игилманов  Айбек  Амангельдиевич

студент  1-курса,  инженерно-технологический  факультет

ЗКИТУ, 
Республика  Казахстан,  г.  Уральск

E-mail: 

Ташенова  Динара  Кизатоллиевна

научный  руководитель,  преподаватель,  инженерно-технологический  факультет  ЗКИТУ, 
Республика  Казахстан,  г.  Уральск

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

Сжатие  изображения  это  –  применение  алгоритмов  сжатия  к  цифровым  изображениям.  В  результате  сжатия  уменьшается  размер  изображения,  соответственно  и  объем  памяти  необходимый  для  его  хранения,  а  скорость  передачи  изображений  увеличивается.  Основой  методов  сжатия  цифровых  изображений  является  применение  объемных  операций  к  матрице,  в  которой  хранятся  начальные  значения  пикселей  изображения.  При  выполнении  эти  операции  занимают  много  времени,  отсюда  возникает  необходимость  увеличения  скорости  обработки  изображения  в  реальном  времени  [2,  c.  56].

Увеличение  производительности  вычислительных  средств  развивается  в  двух  направлениях:  первое  –  увеличение  производительности  элементной  базы,  второе  –  параллельное  выполнение  вычислительных  операций  [1,  c.  33].  В  связи  с  развитием  промышленных  технологий  бесконечно  увеличивать  производительность  элементной  базы  невозможно,  к  тому  же  передовые  технологии  дорогостоящее  удовольствие,  поэтому  обостряется  важность  и  автуальность  второго  направления.  Сегодня  параллельные  вычисления  являются  основной  темой  технологий  программирования.  Применение  параллельных  вычислений  для  повышения  скорости  обработки  цифровых  изображений  является  единственно  верным  решением.  Актуальность  темы  определяется  тем,  что  цифровые  изображения  требуют  большого  объема  памяти  компьютера,  а  их  обработка  –  много  времени.  Возникает  необходимость  их  сжатия.  Сравнительно  одним  из  новых  и  эффективных  методов  технологии  сжатия  является  метод  вейвлетов.

С  математической  точки  зрения  изображения  в  градациях  серого  можно  задать  как  функцию    зависящего  от  переменных    и  .  Функция  изображения    определяется  в  прямоугольной  области  на  плоскости.  Значения  оттенка  серого  положительные  реальные  числа.  Компьютерное  отображение  изображения  в  градациях  серого  это  –  двумерный  массив  из  положительных  чисел.  Каждый  элемент  массива  соответствует  пикселю  изображения  и  принимает  значения  из  ограниченного  диапазона.  Этот  диапазон  задается  в  виде  значений  256  оттенков  серого.  В  дальнейшем  процесс  сжатия  определяется  применением  операций  преобразования,  упрощения  и  кодирования  к  элементам  массива  [3,  c.  154].

Задача  сжатия  состоит  из  двух  частей:  кодирование  и  декодирование.  Кодирование  преобразует  начальные  значения  массива  так,  чтобы  уменьшить  объем  необходимый  для  её  храниения.  Декодирование  восстанавливает  начальные  значения  массива  из  закодированного.  Коэффициенты  полученные  в  результате  вейвлет-преборазований  далее  сортируются:  определенные  большие  %  коэффициентов  сохраняются,  оставшиеся    %  коэффициентов  обнуляются.  Потребуется  время,  чтобы  определить  какие  коэффициенты  можно  обнулять,  а  какие  оставлять.  С  увеличением  количества  коэффициентов  увеличивается  и  время  необходимое  для  определения  ненужных  коэффициентов  [3,  c.  178].

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

Рисунок  1.  Деление  матрицы  на  параллельные  блоки  во  время  децимации

Виртуальная  топология  это  –  программная  реализация  связи  между  виртуальными  компьютерами  в  физической  системе.  Существуют  два  вида  топологии  в  MPI:  топология  декарта  и  топология  графа.  В  задаче  удобно  использовать  топологию  декарта.  Потому  что  она  задается  в  виде  проямоугольного  тора,  удобного  для  реализации  блоков  [1,  c.  78]. 

Сначала  построим  топологию,  чтобы  разделить  матрицу  на  блоки:

void  Topologia()

{ int  DimSize[2]  =  {GridSize,  GridSize};

  int  Periodic[2]  =  {0,0};

  int  SubDims[2];

  MPI_Cart_create(MPI_COMM_WORLD,  2,  DimSize,  Periodic,  0,  &GridComm);

  MPI_Cart_coords(GridComm,  Rank,  2,  GridCoords);

  SubDims[0]  =  0;

  SubDims[1]  =  1;

  MPI_Cart_sub(GridComm,  SubDims,  &RowComm);

  SubDims[0]  =  1;

  SubDims[1]  =  0;

  MPI_Cart_sub(GridComm,  SubDims,  &ColComm);

}

где,  DimSize  –  двумерная  топология  декарта  размером  .  Она  делится  на  несколько  внутренних  SubDims  тора.  Внутренние  торы  объединяются  по  коммуникатору.  Каждому  тору  вручается  блок  матрицы:

void  ArrayToBlocks()

{ MPI_Type_vector(BlockSize,BlockSize,MatrSize,MPI_INT,&MPI_BLOCK);

  MPI_Type_commit(&MPI_BLOCK);

  if  (Rank  ==  0)

  for  (int  r=0;  r  <  ProcCount;  r++)

  {          int  c[2];

           MPI_Cart_coords(GridComm,  r,  2,  c);

           MPI_Send(A+c[0]*MatrSize*BlockSize+c[1]*BlockSize,  1,  MPI_BLOCK,  r,  0,  GridComm);

  }

MPI_Status  s;

MPI_Recv(A1,  BlockSize*BlockSize,  MPI_INT,  0,  0,  GridComm,  &s);

}

Далее  каждый  процесс,  кроме  нулевого,  применяет  кодирование  к  своему  блоку.  После  децимации  каждый  блока  посылается  на  основной  и  все  блоки  объединяются:

void  BlocksToArray()

{ MPI_Send(C1,  BlockSize*BlockSize,  MPI_INT,  0,  0,  GridComm);

  if  (Rank  ==  0)

  {

  MPI_Status  s;

  for  (int  r=  0;  r  <  ProcCount;  r++)

  {

           int  c  [2];

           MPI_Cart_coords(GridComm,  r,  2,  c);

           MPI_Recv(C+c[0]*MatrSize*BlockSize+c[1]*BlockSize,  1,  MPI_BLOCK,  r,  0,  GridComm,  &s);

  }

}

}

Теперь  рассмотрим  время  выполнения  параллельного  алгоритма.  Время  обработки  каждого  блока  одним  процессом  ,  также  время  для  децимации  и  кодирования.  Если  кодовый  словарь  состоит  из  L  слов,  тогда  время  для  квантования  .  Значит  параллельный  метод  намного  сэкономит  время,  соответственно  повысит  эффективность.

Заключение

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

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

Список  литературы:

1. Акжалова  А.Ж.  Параллельные  вычисления.  А.:  Қазақ  Университеті,  2007.  –  160  стр. 
2. Воробьев  В.И.,  Грибунин  В.Г.  Теория  и  практика  вейвлет-преобразования.  СПб.:  ВУС,  1999.  –  208  стр. 
3. Дьяконов  В.П.  Вейвлеты.  От  теории  к  практике.  М.:  СОЛОН-Р,  2002.  –  448  стр.
4. Корнеев  В.Д.  Параллельное  программирование  в  MPI.  М.:  Институт  компьютерных  исследований,  2003.  –  304  стр.
5. Уэлстид  С.  Фракталы  и  вейвлеты  для  сжатия  изображений  в  действии.  М.:  Триумф,  2003.  –  320  стр.