Операции с изображением на уровне растра

Содержание
Растровая развертка
Принцип работы алгоритма Брезенхема
Алгоритм Сяоляня
Брезенхам для окружности
Растровая развертка эллипса

Видеоадаптер и буфер кадра
Буфер кадра – прямоугольный массив структур
1280
1024

Растровая и векторная графика. Понятие растра
Для представления графической информации на двумерной плоскости (например, экране монитора, странице книги и т.п.) в вычислительной технике применяются два основных подхода: растровый и векторный
При векторном подходе графическая информация описывается как совокупность неких абстрактных геометрических объектов, таких как прямые, отрезки, кривые, прямоугольники и т.п.
Растровая графика же оперирует изображениями в виде растров. Неформально можно сказать, что растр - это описание изображения на плоскости путем разбиения всей плоскости или ее части на одинаковые квадраты и присвоение каждому квадрату своего цветового (или иного, например, прозрачности, для последующего наложения изображений друг на друга) атрибута.
Если таких квадратов имеется конечное число, то получается, что непрерывная цветовая функция изображения приближенно представлена конечной совокупностью значений атрибутов.

Модель растра
Растр можно рассматривать как кусочно-постоянную аппроксимацию изображения, заданного как цветовая функция на плоскости.
Формально, введем следующие определения:
Растр (англ. raster) - отображение вида
где , , , ,
обозначает множество всех подмножеств ,
C - множество значений атрибутов (как правило, цвет).
f(i, j) - элемент растра, называемый пикселем (англ. pixel (от picture element)),
f(i, j) = (A(i, j),C(i, j)), где А - область пикселя, С - атрибут пикселя (как правило, цвет).
Чаще всего мы будем пользоваться следующими двумя видами атрибутов:
C(i, j) = I(i, j) - интенсивность (или яркость) пикселя;
C(i, j) = {R(i, j),G(i, j),B(i, j)} - цветовые атрибуты в цветовой модели RGB
, ,

Модели точка и квадрат
Aij может определяться двояко, в зависимости от того, с какой моделью мы хотим работать:
Aij := (i, j) - одна точка. - квадрат.
На реальных графических устройствах физически пиксели могут быть прямоугольниками, что иногда порождает дополнительные трудности.
В реальности, как правило, X и Y - ограниченные наборы неотрицательных целых чисел; такой растр называется прямоугольным.
Для него применимо понятие Аспектовое отношение (англ. aspect ratio) - отношение ширины к высоте растра (|X|/|Y|).
Чаще всего такое понятие употребляется в связи с физическими растрами (дисплеями, ПЗС-матрицами фотоаппаратов и т.д.) и записывается в виде простой дроби с ":", например "4:3".

Модель растра первого типа.

Модель растра 2 типа

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

Алгоритм Брезенхема растровой дискретизации отрезка
При построении растрового образа отрезка необходимо, прежде всего, установить критерии "хорошей" аппроксимации.
Первое требование состоит в том, что отрезок должен начинаться и кончаться в заданных точках и при этом выглядеть сплошным и прямым (при достаточно высоком разрешении дисплея этого можно добиться).
Кроме того, яркость вдоль отрезка должна быть одинаковой и не зависеть от наклона отрезка и его длины.
Алгоритм должен работать быстро. Для этого необходимо по возможности исключить операции с вещественными числами.
С целью ускорения работы алгоритма можно также реализовать его на аппаратном уровне.
В большинстве алгоритмов используется пошаговый метод изображения, т.е. для нахождения координат очередной точки растрового образа наращивается значение одной из координат на единицу растра и вычисляется приращение другой координаты.

Цепочный код
Для представления на экране растрового дисплея любой кривой единичной
толщины необходимо найти координаты близких к линии смежных точек на целочисленной сетке .
В дальнейшем будем считать, что на плоскости имеется квадратная сетка с шагом 1, причем узлы целочисленной решетки являются центрами соответствующих квадратных ячеек сетки.
Другими словами, узлы растра окружены «единичными» квадратными окрестностями «радиуса» 1/2.
Инициализации точки растра с координатами (i, j) соответствует закраска каким-либо цветом ее квадратной окрестности
Всякая точка на плоскости имеет четырех непосредственных соседей и восемь косвенных соседей.
Если точки являются непосредственными соседями, то их квадратные окрестности имеют общую сторону. Квадратные окрестности косвенных соседей имеют общую сторону или общую вершину.

Принцип работы алгоритма Брезенхема
Берётся отрезок и его начальная координата x.
К иксу в цикле прибавляем по единичке в сторону конца отрезка.
На каждом шаге вычисляется ошибка — расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки.
Если ошибка не превышает половину высоты ячейки, то она заполняется.

Простое объяснение
Сначала вычисляется угловой коэффициент (y1 — у0)/(x1 — x0). Значение ошибки в начальной точке отрезка (0,0) принимается равным нулю и первая ячейка заполняется.
На следующем шаге к ошибке прибавляется угловой коэффициент и анализируется её значение, если ошибка меньше 0.5, то заполняется ячейка (x0+1, у0), если больше, то заполняется ячейка (x0+1, у0+1) и из значения ошибки вычитается единица.
На картинке ниже жёлтым цветом показана линия до растеризации, зелёным и красным — расстояние до ближайших ячеек. Угловой коэффициент равняется одной шестой, на первом шаге ошибка становится равной угловому коэффициенту, что меньше 0.5, а значит ордината остаётся прежней..

Алгоритм Брезенхама (1/4)
Отрезок, соединяющий P(x1, y1) и Q(x2, y2)

Алгоритм Брезенхама (2/4)
F(x,y) = 0 -- точка на отрезке
F(x,y) < 0 -- точка выше
F(x,y) > 0 -- точка ниже
Точка P определена, тогда координаты срединной точки
и значение функции в этой точке

Алгоритм Брезенхама (3/4)
Если d < 0, то выбирается Е и
Если d ≥ 0, то выбирается NE
В начальной точке

Алгоритм Брезенхама (4/4)
Одна неприятность -- деление на 2
Чтобы избежать вещественной арифметики, сделаем преобразование =>
d0 = 10 - 7 = 3 > 0 (NE)
d1 = 3 - 4 = -1 < 0 (E)
d2 = -1 + 10 = 9 (NE)
d3 = 9 - 4 = 5 (NE)
d4 = 5 - 4 = 1 (NE)
d5 = 1 - 4 = -3 (E)
d6 = -3 + 10 = 7 (NE)

Алгоритм У Сяолиня
Для рисования сглаженных линий.
Он отличается тем, что на каждом шаге ведётся расчёт для двух ближайших к прямой пикселей, и они закрашиваются с разной интенсивностью, в зависимости от удаленности.
Точное пересечение середины пикселя даёт 100% интенсивности, если пиксель находится на расстоянии в 0.9 пикселя, то интенсивность будет 10%.
Иными словами, сто процентов интенсивности делится между пикселями, которые ограничивают векторную линию с двух сторон.

Алгоритм Брезенхема для генерации окружностей
Выбирается генерация по часовой стрелке с началом в точке x = 0, у = R.
Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Эти направления обозначены соответственно mH, mD, mV.
Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из

Описание алгоритма

Аппроксимация окружности
Неявное и явное представление
Параметрическое представление

Брезенхам для окружности (1/3)

Брезенхам для окружности (2/3)
Для точки P c коорд.
Для пиксела Е:
Для пиксела SE:

Брезенхам для окружности (3/3)
В начальной точке (0, R)
И опять нужно исключить вещественные операции.
Сделав замену h = d-1/4, получим h = 1-R.
Тогда необходимо сравнивать h с -1/4, но так как приращения d – целые числа, то сравнивать можно с нулем.

Растровая развертка Эллипса
Для построения растровой развертки эллипса с осями, параллельными осям координат, и радиусами воспользуемся каноническим уравнением
которое перепишем в виде
В отличие от окружности, для которой было достаточно построить одну восьмую ее часть, а затем воспользоваться свойствами симметрии, эллипс имеет только две оси симметрии, поэтому придется строить одну четверть всей фигуры. За основу возьмем дугу, лежащую между точками в первом квадранте координатной плоскости.

Нормаль и точка деления дуги

Схема перехода в первой и второй областях дуги эллипса

Вычисление параметров