Лекции по "Компьютерной графике"

Здесь 12 кадров от I до I фрейма. Это основано на требовании произвольного доступа, согласно которому начальная точка  должна повторяться каждые 0.4 секунды. Соотношение P и B основано на опыте.

Чтобы декодер мог работать, необходимо, чтобы первый P-фрейм в потоке встретился до первого B, поэтому сжатый поток выглядит так:

0 x x 3 1 2 6 4 5 ...

где числа - это номера кадров. xx может не быть ничем, если это начало последовательности, или B-фреймы -2 и -1, если это фрагмент из середины потока.

Сначала необходимо раскодировать I-фрейм, затем P, затем, имея их оба в памяти, раскодировать B. Во время декодирования P показывается I-фрейм, B показываются сразу, а раскодированный P показывается во время декодирования следующего. 

Алгоритм  Фрактальной упаковки. 

Он основан  на том, что в изображении присутствуют похожие фрагменты, причем в отличии  от RLE или LZW алгоритмов, которые хорошо работают только с полностью идентичными фрагментами, он может упаковывать и довольно сильно отличающиеся по размеру, яркости и расположению части изображения. 

Фрактальная архивация  основана на том, что мы представляем изображение в более компактной форме — с помощью коэффициентов системы итерируемых функций (Iterated Function System — далее по тексту как IFS). Прежде, чем рассматривать сам процесс архивации, разберем, как IFS строит изображение, т.е. процесс декомпрессии.

Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований, в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

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

• Линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения.
• Области, в которые проецируются изображения, не пересекаются.
• Линза может менять яркость и уменьшать контрастность.
• Линза может зеркально отражать и поворачивать свой фрагмент изображения.
• Линза должна масштабировать (уменьшать)свой фрагмент изображения.

Расставляя линзы  и меняя их характеристики, мы можем  управлять получаемым изображением. Одна итерация работы Машины заключается  в том, что по исходному изображению  с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций мы получим изображение, которое перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется “неподвижной точкой” или аттрактором данной IFS. Соответствующая теория гарантирует наличие ровно одной неподвижной точки для каждой IFS.

Поскольку отображение  линз является сжимающим, каждая линза  в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Таким образом, интуитивно понятно, что система итерируемых функций задает фрактал (нестрого — самоподобный математический объект).

Наиболее известны два изображения, полученных с помощью IFS: “треугольник Серпинского” и “папоротник Барнсли”. “Треугольник Серпинского” задается тремя, а “папоротник Барнсли” четырьмя аффинными преобразованиями (или, в нашей терминологии, “линзами”). Каждое преобразование кодируется буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.  
 
 

Лекция 19 

Классы  изображений и  переходы между ними  

Классы  изображений:

1. Тоновые и цветные изображения.
2. Двухуровневые или представленные в нескольких цветах изображения.
3. Непрерывные кривые и линии.
4. Точки и многоугольники.

 
 
 

 
 
 
 
 
 

Преобразования  изображений:

1->2 –  Сегментация изображений. Выделяются  области приблизительно одной  яркости и цвета. Возможно выделение  текстуры.

2->3 –  Построение контура, прореживание – граф, остов области.

3->4 –  Сегментация кривых. Отыскание критических  точек контура (углов многоугольника).

4->3 –  Интерполирование – проведение  гладкой кривой через множество  точек, аппроксимация - проведение  гладкой кривой вблизи множества точек.

3->2 –  Заливка областей.

2->1 –  Сглаживание – фильтры и зашумление. 

Сегментация изображений 

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

 
 
 
 
 
 

 
 

Построение  контура 

Соседние к  данному пикселы можно разделить  на н-соседей – имеют общую сторону и к-соседей – касаются углом. Соответственно и контур может быть как к-контуром (8-ми связным), в него входят пикселы области имеющие по крайней мере одного н-соседа, расположенного вне данной области. Так и н-контуром (4-х связным), в него входят пикселы области имеющие любого соседа (н или к), расположенного вне данной области. 

 
 
 
 
 
 
 
 
 
 

Контуры кодируются с помощью кодов направления, сначала записываются абсолютные координаты начала контура, а затем коды определяющие положение следующего пиксела в контуре. 

 
 

Для данной фигуры (начиная с пиксела с 2-ой штриховкой) это будет (0,0,0,7,5,5,4,4,4,2,2,1). Это потребует 12*3=48 бит.

Если  применять дифференциальные коды, то можно немного сократить размеры  памяти для хранения контура. Дифференциальные - это не само направление, а его  отличие от предыдущего (начальное  направление можно взять постоянным, например, 0-ое). Это тоже 8 кодов 0,+1,-1,+2,-2,+3,-3,+4) . За счет того, что обычно направление сохраняется или изменяется несильно, то имеет смысл использовать коды с переменной длиной 0 – 0, +1 – 100, -1 – 101,+2 – 1100,-2  – 1101,+3 – 1110,-3 – 11110,+4 – 11111. 

Построение  скелета (остова) области 

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

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

 
 
 
 
 

Но может  быть случай, когда такая проверка недостаточна, такое происходит если остается линия в шириной в 2 пиксела. Т.к. пикселы обоих сторон такой  линии являются пикселами контура и не удовлетворяют вышеприведенному условию, они будут удалены и от линии ничего не останется, хотя должен быть остов, проходящий точно по ее центру.

 
 
 
 

Для правильной обработки таких случаев следует  проверять еще две комбинации пикселов.  

 
 
 
 
 
 
 

Сегментация кривых 

После того, как определены контуры они  аппроксимируются отрезками прямых или кривых. Критерием близости аппроксимирующей кривой к точкам контура можно  выразить через расстояние e_i от i-ой точки контура до кривой.

Судить  можно по максимальной ошибке E_max=max|e_i|, либо по суммарной квадратичной ошибке . Если ошибка больше некоторого значения - значит аппроксимация неудовлетворительна.

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

Интерполирование 

Обычное построение отрезков или кривых (сплайны).  

Заливка областей 

Обычная заливка (с затравкой) или через  определение попадания точки  в многоугольник.  

Сглаживание 

Применяют различные фильтры для получения  более реалистичных изображений, например, фильтр уменьшения резкости. Обычно применяют т.н. линейные фильтры. При этом цвет пиксела смешивают с цветами соседних пикселов в некоторой окрестности M. Коэффициенты, на которые умножаются яркости пикселов определяются функцией h=h(x,y,i,j), если она не зависит от положения пиксела h=h(i,j), то фильтр называют пространственно инвариантным. Функцию h при этом можно представить в виде матрицы.

- пространственно инвариантный  фильтр. 
 

 - размывание (уменьшение резкости) 

 - увеличение резкости (контраста) 

 - определение границ 

 - тиснение, здесь имеет смысл добавлять половину максимальной яркости (128), для получения нормального изображения 
 
 
 
 
 
 

Лекция 20 

Распознавание образов  

Понятие образа

Образ, класс — группировка объединяющая (выделяющая) определенный набор объектов по некоторому признаку.

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