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

Аналогично  записывается уравнение i-го A-элемента:

,

Здесь сигнал y_k может быть непрерывным, но чаще всего он принимает только два значения: 0 или 1. Сигналы от S-элементов подаются на входы А-элементов с постоянными весами равными единице, но каждый А-элемент связан только с группой случайно выбранных S-элементов. Предположим, что требуется обучить перцептрон различать два образа V₁ и V₂. Разделение объектов на два образа можно провести и с помощью только одного R-элемента. Тогда объекту образа V₁ должна соответствовать положительная реакция R-элемента, а объектам образа V₂ — отрицательная.

Перцептрон  обучается путем предъявления обучающей  последовательности изображений объектов, принадлежащих образам V₁ и V₂. В процессе обучения изменяются веса v_i А-элементов. В частности, если применяется система подкрепления с коррекцией ошибок, прежде всего учитывается правильность решения, принимаемого перцептроном. Если решение правильно, то веса связей всех сработавших А-элементов, ведущих к R-элементу, выдавшему правильное решение, увеличиваются, а веса несработавших А-элементов остаются неизменными. Можно оставлять неизменными веса сработавших А-элементов, но уменьшать веса несработавших. В некоторых случаях веса сработавших связей увеличивают, а несработавших — уменьшают. После процесса обучения перцептрон сам, без учителя, начинает классифицировать новые объекты.

Если  перцептрон действует по описанной  схеме и в нем допускаются  лишь связи, идущие от бинарных S-элементов  к A-элементам и от A-элементов к единственному R-элементу, то такой перцептрон принято называть элементарным a-перцептроном. Обычно классификация C(W) задается учителем. Перцептрон должен выработать в процессе обучения классификацию, задуманную учителем.

Распознавание графических образов

 
 

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

Например, при распознавании текста, вначале  текст сканируется (исходные данные), затем изображение сегментируется на 2 уровня яркости, разделяется на отдельные абзацы, строки  символов и отдельные символы (получаем признаки символа в виде изображения отдельного символа или его контура/скелета), потом по этим признакам определяются сами символы. В качестве признаков могут использоваться как значения яркости пикселей (1 или 2 классы), так и параметры контуров и остовов (3 или 4 класс). В пером случае – значение яркости пикселов сразу подают на S-элементы персептрона (символ при этом необходимо предварительно отмасштабировать). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Лекция 21 

Аппроксимация кривых и поверхностей сплайнами  
 

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

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

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

Два из наиболее общих типов сплайнов - кривые Безье (Bezier curves) и В-сплайны (B-spline curves). Типичным примером сплайнов являются также неоднородные рациональные B-сплайны (Non-Uniform Rational B-Spline - NURBS). Можно строить достаточно гладкие кривые и поверхности с использованием полиномов. В случае кривой общей формулой полинома p-ой степени будет , в случае поверхности . Достаточная гладкость кривых достигается при непрерывности первых двух производных, поэтому наиболее часто используются полиномы третьей степени.  

Сплайн-функции  одной переменной 

Допустим, что мы хотим построить кривую y=y(x), проходящую через последовательность контрольных точек сетки (x₀,y₀), (x_i,y_i), ..., (x_n,y_n) с x₀<x₁<...<x_n. Точки x₀ и x_n называются граничными узлами сетки, а x_{1 …} x_n-1 - внутренними узлами. Функция S(x), заданная на отрезке [x₀,x_n], называется сплайном степени p, если:

1. на каждом интервале [x_i,x_i+1], i=0,1,n-1, эта функция должна быть многочленом заданной степени p>=2, т.е.
2. S(x) непрерывна и имеет p-1 непрерывных производных на всем интервале [x₀,x_n].

 

Для задания  сплайна на каждом интервале требуется определить (p+1) коэффициентов, всего потребуется n(p+1) чисел. Условия непрерывности функции и ее p-1 производных на всех внутренних (n-1) узлах, дают p(n-1) уравнений, оставшиеся (n(p+1)-p(n-1))=n+p уравнений, необходимых для полного задания сплайна определяются пользователем. Например, можно потребовать, чтобы кривая проходила точно через узлы сетки (интерполяционный сплайн), что дает еще (n+1) уравнений. Оставшиеся (p-1) уравнений можно задать в виде младших производных сплайна на граничных узлах отрезка. Если требуется построить сглаживающую кривую (т.е. проходящую не точно через узлы, а где-то поблизости от них), дополнительные уравнения строят исходя из условий близости, которые можно определять по-разному.

        Например, требуется  построить интерполирующий кубический сплайн, по 4-м узлам.

       Нужно получить 3*4=12 коэффициентов (по 4 на каждый из 3-х интервалов), т.е. 12 составить 12 уравнений. Полиномы в интервалах будут  иметь вид:  
 

 

       Условия непрерывности сплайна задаются как:

        , для i=0,…,n-2

       

       Условия непрерывности первой производной:

        , для i=0,…,n-2

       

       Условия непрерывности второй производной:

        , для i=0,…,n-2

       

       Условия прохождения сплайна через узлы сетки:

        , для i=0,…,n

       

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

        , ,

        ,

Основные  недостатки такого подхода:

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

 

B-Сплайны 

Чтобы избавиться от первого недостатка применяют  B-сплайны (базовые или фундаментальных), кроме того, эти сплайны требуют хранения меньшего кол-ва коэффициентов (n+p-1) вместо n(p+1), что значительно снижает требования к памяти. B-сплайн 0-ой степени это ступенчатая функция.

, для более высоких степеней  она вычисляется по рекуррентной  функции:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Наиболее часто  используются кубические B-сплайны, его функция для сетки с постоянными интервалами h: 

, где   

Сплайн-функция  является суммой B-сплайнов с некоторыми коэффициентами.

n+2 коэффициента вычисляются из системы: 
 
 
 
 
 

 

Кривые  Безье 

Сплайны позволяют работать не только с функциями  y=y(x), но задать функцию параметрически, например, с помощью кривых Безье. Если задан массив точек P={P_i(x_i,y_i,z_i), i=0,1,…n}, то кривая Безье степени n имеет следующий вид:

, 0<=t<=1, где - многочлен Бернштейна. 

Свойства  кривых Безье:

1. Гладкие
2. Начинаются в P₀ и заканчиваются в P_n, при этом касаются в этих точках отрезков P₀P₁ и      P_n-1P_n.
3. Лежит в выпуклой оболочке точек.
4. Ее степень зависит от кол-ва точек.
5. При изменении одной из точек изменяется вся кривая.

 
 
 
 
 
 
 
 

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

 
 
 
 
 
 

В-сплайновые кривые  

Можно задать кривую параметрически и при помощи B-сплайнов. Элементарная B-сплайновая кубическая кривая строится по 4-м точкам , P₁, P₂, P₃, следующим образом .

Где n_k(t) – функциональные весовые множители.

, , ,

Касательные в концевых точках параллельны отрезкам P₀P₂ и P₁P₃ соответственно.

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

, i=1,2,…n-2 

Такие кривые обладают очень важным свойством – изменение одной из точек не влечет за собой изменение всей кривой, а влияет только на соседние 4 сегмента.

Чтобы иметь возможность стыковать  различные B-сплайновые кривые и задавать кривые вроде окружностей и эллипсов используются рациональные B-сплайны. Они отличаются от обычных весовыми коэффициентами w_k. Если все множители равны между собой – это обычный B-сплайн, но варьируя их можно точно (вплоть до 2-ой производной) стыковать различные кривые. 

 
 

Рациональные В-сплайновые поверхности

 

 
 
 
 
 
 
 
 
 
 
 
 

Лекция 22 

Устройства  ввода и вывода графической информации  
 

Все устройства можно поделить на два класса: векторные  и растровые. Векторные работают с координатами точек, а растровые  – с изображениями, разбитыми  на отдельные пикселы.

Мониторы

 

       ЭЛТ. Физический принцип – остаточное свечение люминофора после воздействия на него пучка электронов. Электронно-лучевая трубка (ЭЛТ) состоит из электронной пушки, испускающей луч электронов, отклоняющей системы, которая этот луч направляет в нужное место экрана, и люминофора, который светится при попадании на него луча электронов. Мониторы бывают как растровые, так и векторные. В растровых луч пробегает на каждом кадре всю поверхность экрана сверху вниз построчно справа налево. В векторных – обводит на каждом кадре все примитивы на экране. Недостатки растровых – малые разрешение и частота кадров (1024х768 100 Hz) из-за малой скорости поступления информации с видеокарты. У векторных, таких недостатков нет, его обычное разрешение 2048х2048, но на них сложно выводить закрашенные области и фотографии, т.к. в этом случае они работают практически в растровом режиме, закрашивая примитив строчка за строчкой.