на школьную страницу...

Обработка и кодирование черно-белых изображений

Магистерская диссертация В.Ю.Зуевой,
2010 г.

Научный руководитель С.И.Хашин

На сегодняшний день наиболее эффективный способ хранения двухцветных (черно-белых, black-white, b/w) изображений - сохранить их в формате png.

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

Разработанный нами алгоритм состоит из двух этапов:
1. Для данной точки на изображении находим среди «предыдущих» точек ту, область после которой наиболее «похожа» на область после данной точки. В выходной поток отправляем 4 числа: две координаты смещения и размеры по x и по y совпадающей области.
Опуская некоторые детали, на выходе 1-го этапа получаем поток из четверок целых чисел: (offset_x, offset_y, dx, dy).
2. Сжимаем полученный поток числе с помощью архиватора bzip2.

Работа выполнена на языке C++.

#include "hlib.h"
#include "iMatrix.h"
#include "vUtil.h"

//------------------------------------------------------------------------------
// В матрице a рассмотрим прямоугольники (x0..x0+dx-1,y0..y0+dy-1), (x1..x1+dx-1,y1..y1+dy-1)
// Будем из называеть СОВПАДАЮЩИМИ, если значения матрицы в соответствующих точках одинаковы.
// пара прямоугольников описывается шестью числами: (x0,y0),(x1,y1),(dx,dy)
//------------------------------------------------------------------------------
//
// Даны: матрица a, и совпадающие прямоугольники (x0,y0),(x1,y1),(dx,dy).
// Можно ли их расширить на 1 ВПРАВО?
bool Is_Expanded_Right(matr &a, int x0, int y0, int x1, int y1, int dx, int dy)
{
	int mx=a.Mx();
        if (y1==y0)
             {
             if((x1+dx==x0)||(x0+dx==mx))
             return false;
             }
        else {
                 if( (x0+dx==mx) || (x1+dx==mx) )
                 return false;
              }	// дошли до правого края, расширять некуда
        for( int i=0; imax_s )
         {
            dx=dx_;
            dy=dy_;
            max_s=s;
         };			// если площадь увеличилась, запоминим ее
    }

	return max_s;
}
//**********************************************************
/*
  Данная функция непосредственно обрабатывает считанное изображение,
  используя написанные ранее функции.
  Теперь проходим по всем элементам матрицы, и для всех точек, кроме данной,
  вычисляем максимальную площадь совпавшего прямоугольника.
  Сравнивая эти площади, выбираем наибольшую. При этом сохраняется
  не только значение площади, но и высота и длина полученного прямоугольника.

  Для данной функции используются следующие данные
  mx-ширина исходного изображения
  my-высота исходного изображения
  x и y - координаты данной точки(для окрестности которой ищется совпадение)
  &matrix-адрес переменной, в которой хранится информация о считанном изображении
  *x1 и *y1 - в эти переменные после обработки сохраняются координаты полученной точки
  *height и *width - высота и ширина полученной области, 
  полученные после обработки всего изображения
*/


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

Flag Counter