WEBVTT

00:00:07.226 --> 00:00:08.986
Здравствуйте, уважаемые студенты.

00:00:09.346 --> 00:00:12.905
Вашему вниманию предлагается лекция по
дисциплине «Компьютерная графика».

00:00:14.025 --> 00:00:16.705
Тема лекции — алгоритмические основы
компьютерной графики.

00:00:16.785 --> 00:00:21.184
Лекция четвёртая. Лекцию ведёт кандидат
технических наук, доцент кафедры

00:00:21.264 --> 00:00:24.504
информатики, математики и
естественно-научных дисциплин Черничук

00:00:24.544 --> 00:00:25.183
Игорь Владимирович

00:00:28.016 --> 00:00:34.179
План лекции: расстровые алгоритмы,
алгоритмы растеризации, методы устранения

00:00:34.339 --> 00:00:38.861
ступенчатости, методы обработки
изображений, цифровые фильтры изображений,

00:00:39.061 --> 00:00:40.942
преобразование расстровых изображений.

00:00:41.182 --> 00:00:44.783
Если успеем, поговорим немножко о
возможностях библиотеки Opengell.

00:00:48.205 --> 00:00:52.051
Растровые алгоритмы. Большинство
графических устройств являются растровыми,

00:00:52.091 --> 00:00:58.781
представляя изображение в виде
прямоугольной матрицы, сетки целочисленной

00:01:00.271 --> 00:01:04.193
Решётки, то есть пиксели растры, и
большинство графических библиотек содержат

00:01:04.233 --> 00:01:07.874
внутри себя достаточное количество
простейших растровых алгоритмов.

00:01:07.954 --> 00:01:13.356
Ну вот на рисунке 4.1 приведена как раз
система растровых алгоритмов.

00:01:14.156 --> 00:01:15.237
Классификация.

00:01:15.970 --> 00:01:17.329
Растровых алгоритмов.

00:01:18.368 --> 00:01:24.323
Растровые алгоритмы, соответственно,
делятся на алгоритмы растерризации,

00:01:24.443 --> 00:01:26.681
алгоритмы обработки растровых изображений.

00:01:26.761 --> 00:01:30.558
Алгоритмы растертизации, как видите,
алгоритмы перевода графических примитивов

00:01:30.638 --> 00:01:31.757
в растровую форму.

00:01:32.265 --> 00:01:35.664
И алгоритмы заполнения областей и
многоугольников.

00:01:35.984 --> 00:01:40.901
Алгоритмы обработки растовых изображений,
соответственно, это алгоритмы регулировки

00:01:40.981 --> 00:01:45.379
яркости и контрастности, масштабирования
изображений, геометрические

00:01:45.499 --> 00:01:47.738
преобразования, алгоритмы фильтрации.

00:01:50.113 --> 00:01:51.552
Алгоритмы растеризации.

00:01:51.712 --> 00:01:55.631
Прежде чем перейдём к непосредственному
рассмотрению возможности перевода

00:01:55.751 --> 00:02:00.310
математического описания объекта, то есть
линий и прочих примитивов, в растовую

00:02:00.350 --> 00:02:02.229
формулу, рассмотрим понятие связанности.

00:02:02.349 --> 00:02:05.108
Связность — это возможность соединения
двух пикселей.

00:02:06.724 --> 00:02:09.603
Растровые линией, то есть последовательным
набором пикселей.

00:02:09.723 --> 00:02:15.001
Возникает вопрос: когда пиксели,
соответственно, с координатами X.1, X X2.

00:02:15.041 --> 00:02:17.080
Reck-2 можно считать соседними.

00:02:17.320 --> 00:02:19.839
Для этого вводятся два понятия связности.

00:02:19.959 --> 00:02:21.798
Так называемая четырёхсвязность.

00:02:22.574 --> 00:02:28.967
Пиксели считаются соединёнными, если либо
их координаты X, либо их

00:02:29.087 --> 00:02:32.044
координаты егек отличаются на единицу.

00:02:32.203 --> 00:02:38.277
То есть модуль X I - X + модуль I

00:02:39.029 --> 00:02:42.670
Минус игрек и два, разность,
соответственно, по координатам не

00:02:42.790 --> 00:02:44.150
превышает единицы.

00:02:45.790 --> 00:02:47.551
Восьмисвязность, так называемая.

00:02:47.631 --> 00:02:52.472
Пиксели считаются соседними, если их X
координат и X координат отличаются не

00:02:52.632 --> 00:02:55.352
более чем на единицу. То есть тут в первом
случае было

00:02:56.185 --> 00:03:01.820
Как вы видите, либо, то есть или, во
втором случае, имеется в виду И.

00:03:02.620 --> 00:03:04.458
То есть в обязательном порядке.

00:03:07.016 --> 00:03:12.332
То есть, соответственно, модуль X1 минус
X2 — разность координат не превышает

00:03:12.452 --> 00:03:17.648
единицу и отдельно X1 минус игрек 2 тоже
не превышает единицу.

00:03:19.348 --> 00:03:23.791
Соответственно, на рисунке изображены
четырёхсвязные и восьмисвязные линии.

00:03:24.312 --> 00:03:29.996
Вот, как видите, на слайде рисунок 4.2 —
классификация растровых алгоритмов:

00:03:30.277 --> 00:03:32.638
четырёхсвязные и восьмисвязные линии.

00:03:32.758 --> 00:03:37.442
Ну, где-то там издали, соответственно, они
в какой-то степени сливаются.

00:03:38.260 --> 00:03:43.019
При переводе объектов в расстровое
представление существуют алгоритмы, как

00:03:43.259 --> 00:03:47.418
использующие четырёхсвязность, так и
использующие восьмисвязность.

00:03:49.818 --> 00:03:54.937
Значит, расстровое представление отрезка —
алгоритм Брезенхейма.

00:03:55.097 --> 00:03:59.496
Рассмотрим задачу построения расстрового
изображения отрезка, соединяющего точки.

00:04:00.158 --> 00:04:04.434
Соответственно, Аксa игрек XA и B X B
igрек-B.

00:04:04.514 --> 00:04:10.269
Для простоты будем считать, что,
соответственно, разность координат крек B,

00:04:10.349 --> 00:04:16.904
игрек-а икс Б икс-А, соответственно,
соотносится

00:04:17.104 --> 00:04:20.581
следующим образом, тогда отрезок
описывается следующим уравнением.

00:04:21.437 --> 00:04:27.724
Игрек равняется игрек a плюс игрек Б минус
игрек K делить на игрек-б минус игрек-ка,

00:04:28.044 --> 00:04:30.607
соответственно, икс минус икс А.

00:04:30.807 --> 00:04:34.331
Где икс принадлежит, соответственно,
отрезку X U X B.

00:04:34.851 --> 00:04:39.216
Или, соответственно, аналитическое
выражение прямой — игрек равняется K X +

00:04:40.803 --> 00:04:44.684
Отсюда получаем простейший алгоритм
расстрого представления отрезка.

00:04:45.525 --> 00:04:48.645
Так, ну вот мы его тут частями будем
рассматривать.

00:04:49.245 --> 00:04:55.767
Соответственно, сначала вводятся
переменные, соответственно, как

00:04:55.967 --> 00:04:57.807
видите, тут используется бит-мап.

00:04:59.878 --> 00:05:01.277
Класс бит-мап

00:05:06.471 --> 00:05:11.705
вычислений значений функции X равняется K
X + B, можно избежать, используя в цикле

00:05:11.865 --> 00:05:13.583
рекурентное соотношение.

00:05:13.903 --> 00:05:15.381
Так как при изменении X

00:05:16.028 --> 00:05:18.787
На единицу значение грек меняется на K.

00:05:19.466 --> 00:05:25.783
Соответственно Previte voit, как видите,
тут, соответственно,

00:05:26.263 --> 00:05:27.583
фрагмент кода.

00:05:27.783 --> 00:05:29.622
Но опять же с помощью бит-мап.

00:05:29.702 --> 00:05:32.101
Ну, тут, наверное, дам без комментариев.

00:05:33.000 --> 00:05:39.564
Соответственно, текст

00:05:39.724 --> 00:05:42.605
программы, видите на слайде, можете
сделать паузу.

00:05:44.406 --> 00:05:49.209
Приведённый простейшие пошаговый алгоритмы
построения отрезка имеет ряд недостатков.

00:05:49.289 --> 00:05:53.131
Выполняет операции над числами с плавающей
точкой, а желательно было бы работать с

00:05:53.172 --> 00:05:54.372
целочисленной арифметикой.

00:05:55.262 --> 00:05:58.664
На каждом шаге выполняется операция
округления, что также снижает

00:05:58.744 --> 00:06:03.347
быстродействие. Эти недостатки устранены
следующим алгоритмом Брюзинг Хейма.

00:06:03.427 --> 00:06:07.470
Как и в предыдущем случае, будем считать,
что тангенс угла наклона отрезка принимает

00:06:07.710 --> 00:06:09.871
значение в диапазоне от нуля до единицы.

00:06:10.231 --> 00:06:13.913
Рассмотрим, соответственно, и шаг
алгоритма, то есть рисунок 4—3.

00:06:15.023 --> 00:06:19.940
На этом этапе пиксель, соответственно, PIS
уже найден, как ближайший к реальному

00:06:20.060 --> 00:06:25.058
отрезку. Требуется определить, какой из
пикселей, соответственно, Т-ИТ или SIT,

00:06:25.298 --> 00:06:27.177
будет установлен следующим.

00:06:29.536 --> 00:06:31.215
Так, вот переводится рисунок.

00:06:32.090 --> 00:06:34.372
Третий шаг алгоритма Брезентейма.

00:06:34.412 --> 00:06:38.015
В алгоритме используется управляющая
переменная D.

00:06:38.576 --> 00:06:43.340
Соответственно, которая на каждом шаге
пропорциональна разности между S и T

00:06:43.541 --> 00:06:48.705
большое. Если, соответственно, S меньше Т
большое, то, соответственно, S и T ближе к

00:06:48.745 --> 00:06:50.667
отрезку, иначе выбираются Т и Т.

00:06:51.574 --> 00:06:57.016
Пусть изображаемый отрезок проходит из
точки, соответственно, X igrek в точку X2,

00:06:57.096 --> 00:07:02.458
grek 2. Исходя из начальных условий, точка
X gрек и Т ближе к началу координат.

00:07:02.698 --> 00:07:08.220
Тогда перенесём оба конца отрезка с
помощью преобразования, соответственно, T

00:07:08.940 --> 00:07:11.221
-x y -грек первое.

00:07:14.069 --> 00:07:19.432
Так, чтобы первый конец отрезка совпал с
началом координат.

00:07:19.552 --> 00:07:22.194
Начальной точкой отрезка стала точка.

00:07:22.394 --> 00:07:24.315
То есть 0-ноль с координатами.

00:07:24.475 --> 00:07:25.196
Конечной точкой

00:07:25.937 --> 00:07:28.019
Соответственно, D X D Y.

00:07:28.139 --> 00:07:33.262
Где, соответственно, Ds предполагается
разница X2 — X1, D Yex, соответственно,

00:07:34.583 --> 00:07:37.025
Dрек 2 -грек-1.

00:07:41.067 --> 00:07:43.108
Так, вот как показано на данном слайде.

00:07:46.857 --> 00:07:50.541
Уравнение прямой в данном случае будет
иметь следующий вид.

00:07:54.265 --> 00:07:57.108
Так, grek равняется X D geк D X.

00:07:57.188 --> 00:08:01.232
Обозначим координаты точки,
соответственно, P и минус первая после

00:08:01.552 --> 00:08:03.475
переноса через, соответственно.

00:08:03.947 --> 00:08:09.751
Р ку. Тогда, соответственно, S и T будет
равняться R +1, как видите, ку.

00:08:10.031 --> 00:08:12.673
И R1, +1.

00:08:13.114 --> 00:08:18.798
Для подобия треугольников на рисунке 4—4
можно записать, что, соответственно, D Y

00:08:18.958 --> 00:08:22.120
на D X равняется S + U делить на R +1.

00:08:22.240 --> 00:08:23.041
Выразим S.

00:08:23.965 --> 00:08:30.490
Соответствующим образом через D gрек D X T
можно представить как единица минус S.

00:08:30.570 --> 00:08:34.854
Используем, соответственно, предыдущую
формулу и найдём разницу S минус T.

00:08:35.254 --> 00:08:38.377
И вот таким образом получили следующее
выражение.

00:08:38.497 --> 00:08:40.458
Помножим левую-правую часть на D X

00:08:42.027 --> 00:08:48.987
Получили, соответственно, вот выражение
следующее: два: D - Cu D X + 2 D

00:08:49.107 --> 00:08:53.107
игрек минус DX. Величина D X
положительная, поэтому неравенство D X's S

00:08:53.267 --> 00:08:58.387
минус Т меньше нуля можно использовать в
качестве проверки при выборке S и T.

00:08:58.507 --> 00:09:01.747
Соответственно, обозначим как D X's S
минус Т, тогда

00:09:03.604 --> 00:09:10.129
Соответственно, Di равняется R Deк -u D X
+ 2 D

00:09:10.290 --> 00:09:11.731
игрек минус D X.

00:09:11.891 --> 00:09:18.496
Поскольку, соответственно, R у нас Dвое ку
игрек минус

00:09:18.576 --> 00:09:23.620
первое, то имеем Di равня 2 X e se D grex
V.

00:09:25.100 --> 00:09:28.419
Игрек минус первое, Дикс плюс два Дигрек
минус D X.

00:09:28.539 --> 00:09:33.417
И, соответственно, прибавляя к каждому
индексу найдём

00:09:35.657 --> 00:09:38.776
D игрек плюс первое.

00:09:39.801 --> 00:09:44.956
Так, как D, как 2 X: T geк - 2 geк, D X +
2 D игрек минус D X.

00:09:44.956 --> 00:09:48.872
И вычитая, соответственно, D игрек и Di
плюс первый, получаем следующее.

00:09:49.591 --> 00:09:54.026
Выражение для DI плюс первое минус DI.

00:09:54.506 --> 00:09:57.783
Известно, что, соответственно, что X & X

00:09:58.975 --> 00:10:00.935
Если говорить верьте, и минус первое равно
единице.

00:10:01.015 --> 00:10:06.854
Тогда, соответственно, разница Di плюс
первая минус DIT равня 2 D gк минус 2 D X

00:10:07.214 --> 00:10:10.494
в скобках игрек и минус игрек минус
первое.

00:10:10.894 --> 00:10:17.053
Отсюда, соответственно, выразим Di плюс
первое следующим образом.

00:10:18.208 --> 00:10:21.969
Таким образом, получили итеративную
формулу вычисления управляющего

00:10:22.049 --> 00:10:25.810
коэффициента D +1 по предыдущему значению
D и.

00:10:25.930 --> 00:10:29.211
С помощью управляющего коэффициента
выбирается следующий пиксель.

00:10:29.291 --> 00:10:32.451
То есть, соответственно, S IT или TIT.

00:10:32.971 --> 00:10:33.572
Если DI

00:10:34.600 --> 00:10:37.842
Больше равно тогда нулю, тогда выбирается
Титое.

00:10:38.163 --> 00:10:44.767
Игрек, игрек минус первое + 1, D I, D+
первое равно Титое +

00:10:44.967 --> 00:10:46.608
два, Ди игрек минус D X.

00:10:46.688 --> 00:10:50.090
Если Dite меньше нуля, то выбирается Ste.

00:10:50.974 --> 00:10:57.940
И соответственно, игрек и Т равняется
игрек и Т минус один и D+1

00:10:58.260 --> 00:11:00.182
равняется Ди плюс двак.

00:11:00.262 --> 00:11:05.827
Соответственно, начальное значение D-
игрек с учётом того, что начальная точка X

00:11:05.988 --> 00:11:07.589
нулевой, грек-нулёвое — это 0,0.

00:11:08.220 --> 00:11:12.138
Имеем следующее. D1 равняется 2 D Ig - D
X.

00:11:12.217 --> 00:11:16.575
Преимуществом алгоритмов является то, что
для работы алгоритма требуются минимальные

00:11:16.615 --> 00:11:21.053
арифметические возможности: сложение,
вычитание, сдвиг влево для умножения на

00:11:21.252 --> 00:11:24.930
два, что, конечно, технически намного
проще реализовать.

00:11:25.685 --> 00:11:28.728
Реализация этого алгоритма выглядит
следующим образом.

00:11:30.889 --> 00:11:31.970
Соответственно.

00:11:39.656 --> 00:11:41.097
Как видите, кусок кода.

00:11:43.079 --> 00:11:47.002
Используются математические функции, то
есть модуль.

00:11:52.085 --> 00:11:54.086
Так, и хвост алгоритма.

00:11:54.646 --> 00:11:58.568
Цикл X меньше X', то есть последнего.

00:11:59.256 --> 00:12:03.415
Если D игрек больше D X, то необходимо
будет использовать этот же алгоритм, но

00:12:03.495 --> 00:12:07.414
пошагово, увеличивая игрек на каждом шаге
вычислять икс.

00:12:13.333 --> 00:12:16.652
Следующий вопрос: расстровая развёртка
окружности.

00:12:17.211 --> 00:12:21.526
Существует несколько очень простых, но
неэффективных способов преобразования

00:12:21.646 --> 00:12:23.364
окружностей в расстровую формулу.

00:12:23.764 --> 00:12:27.879
Например, рассмотрим для простоты
окружность с центром в начале координат.

00:12:28.039 --> 00:12:31.875
Её уравнение, соответственно, записывается
как ик квадрат плюс игрек квадрат

00:12:31.995 --> 00:12:32.993
равняется R- квадрат.

00:12:34.035 --> 00:12:40.161
Соответственно, можно выразить игрек, как
видите, как + корень квадратный R в

00:12:40.201 --> 00:12:42.123
квадрате минус икс в квадрате.

00:12:42.403 --> 00:12:47.729
И чтобы изобразить четвёртую часть
окружности, будем изменять икс с единичным

00:12:47.809 --> 00:12:50.932
шагом от нуля до R и на каждом шаге
вычислять игрек.

00:12:51.815 --> 00:12:55.292
Вторым простым методом растровой развёртки
окружности является использование

00:12:55.412 --> 00:12:58.728
вычислений, соответственно, по
параметрическим формулам.

00:12:59.327 --> 00:13:06.000
X Reк, соответственно, икс равняется r
умножить на косинус aгрек умножить R равно

00:13:06.240 --> 00:13:07.199
на синус альфа.

00:13:08.325 --> 00:13:13.168
При этом, соответственно, по шагом
изменения угла от альфа от нуля до 90.

00:13:13.688 --> 00:13:19.052
Дляпрощения алгоритма растовой развёртки
стандартной окружности можно

00:13:19.412 --> 00:13:24.054
воспользоваться ещё симметрией
относительно координатных осей и прямых,

00:13:24.135 --> 00:13:26.656
соответственно, gрек плюс минус X.

00:13:27.428 --> 00:13:31.305
В случае, когда центр окружности не
совпадает с началом координат, эти прямые

00:13:31.424 --> 00:13:36.141
необходимо сдвинуть параллельно так, чтобы
они прошли через центр окружности.

00:13:36.420 --> 00:13:40.577
Тем самым достаточно построить расстровое
представление для одной восьмой части

00:13:40.817 --> 00:13:46.212
окружности, а все оставшиеся точки
получить, исходя из законов симметрии.

00:13:46.772 --> 00:13:48.570
Соответственно, рисунок 4—5.

00:13:52.193 --> 00:13:56.312
Рисунок 4—5 восьмисторонняя симметрия.

00:13:56.352 --> 00:13:59.512
То есть вот можно построить один сегмент,
всё остальное развернуть.

00:14:01.104 --> 00:14:06.825
Рассмотрим участок окружности из второго
актанта, то есть где X принадлежит от нуля

00:14:07.665 --> 00:14:09.385
R делить на корень из двух.

00:14:09.665 --> 00:14:13.386
Далее, соответственно, опишем алгоритм
полезен схемы для этого участка

00:14:13.466 --> 00:14:18.667
окружности. На каждом шаге алгоритм
выбирает точку P и T, соответственно, X, и

00:14:18.707 --> 00:14:21.027
Т игрек, которая является ближайшей.

00:14:21.575 --> 00:14:22.814
Истинной окружности.

00:14:23.134 --> 00:14:27.570
Идея алгоритма заключается в выборе
ближайшей точки при помощи управляющих

00:14:27.650 --> 00:14:31.647
переменных, значения которых можно
вычислять в пошаговом режиме с

00:14:31.727 --> 00:14:35.364
использованием небольшого числа сложений,
вычитаний и сдвигов.

00:14:36.043 --> 00:14:38.881
Рассмотрим небольшой участок сетки
пикселей.

00:14:39.647 --> 00:14:46.443
А также возможные способы, соответственно,
от A дохождение

00:14:47.322 --> 00:14:49.361
истинной окружности через сетку.

00:14:49.641 --> 00:14:51.280
Рисунок 4—6.

00:14:53.558 --> 00:14:58.595
Предположим, что точка P и мину-1 была
выбрана как ближайшая к окружности.

00:14:58.840 --> 00:15:00.602
При X равняется X -1.

00:15:00.682 --> 00:15:05.087
Теперь найдём, какая из точек,
соответственно, SIT или Т- и расположена

00:15:05.167 --> 00:15:10.733
ближе к окружности. При X равняется X -1 +
1.

00:15:11.333 --> 00:15:15.097
Так, как видите на рисунке, варианты
прохождения окружности через расстровую

00:15:15.137 --> 00:15:15.578
сетку.

00:15:18.060 --> 00:15:20.339
В нашем распоряжении.

00:15:21.018 --> 00:15:27.414
Заметим, что ошибка при выборе точки P
была равна, соответственно,

00:15:28.653 --> 00:15:34.729
D и T, соответственно, в соответствии с
формулой

00:15:35.498 --> 00:15:40.459
Окружности: X Es в квадрате плюс игрек в
квадрате минус Р в квадрате.

00:15:40.579 --> 00:15:46.260
Запишем выражение для ошибок, полученных
при выборе точки St или Т-и-е.

00:15:46.860 --> 00:15:52.501
Соответственно, ошибка вот по St равна
тому-то опять же X

00:15:55.624 --> 00:16:02.032
И минус первое плюс один в квадрате,
игрек: и минус первое в квадрате.

00:16:02.152 --> 00:16:05.516
Всё в скобках квадратных: минус R квадрат.

00:16:05.596 --> 00:16:10.242
Аналогично для D, то есть ошибки для Т и
Т.

00:16:13.146 --> 00:16:19.499
Получаем выражение. Если модуль ошибки для
S и Т больше, равен модулю ошибки для

00:16:19.659 --> 00:16:24.574
TIT, то Т иТ ближе к реальной окружности,
иначе выбирается С и Т.

00:16:24.973 --> 00:16:27.890
Введём, соответственно, параметр D мало и
Т как

00:16:28.920 --> 00:16:35.205
Разница модуль ошибки от D от SIT минус
модуль ошибки от

00:16:35.325 --> 00:16:40.249
TIT. Соответственно, Тие будет выбираться
при DIT больше или равно нулю.

00:16:40.409 --> 00:16:44.853
В противном случае будет выбираться,
соответственно, С и Т.

00:16:46.631 --> 00:16:52.268
Запускай алгебраические преобразования,
можно записать DIT и DI+ первое для разных

00:16:52.348 --> 00:16:54.867
вариантов выбора точки S и Т и Т.

00:16:55.267 --> 00:16:59.225
То есть, соответственно, D1 — это будет
как 3 минус 2 R.

00:17:00.904 --> 00:17:01.824
Если выбирается

00:17:08.406 --> 00:17:13.606
Если выбираться с ИТ, то есть когда Дита
меньше нуля, то, соответственно, «И плюс

00:17:13.686 --> 00:17:19.526
первое» будет DITE +4 X - 1 + 6.

00:17:19.846 --> 00:17:25.606
Если выбирается DIT, когда DIT больше,
равно нулю, то DI+ первое равно + четыре.

00:17:26.574 --> 00:17:29.256
Икс минус первый, игрек минус первая + 10.

00:17:29.376 --> 00:17:32.379
Существует модификация алгоритма Брэйд
Хейма для Эллипса

00:17:38.623 --> 00:17:39.824
«Кривые Безе».

00:17:40.064 --> 00:17:44.468
Кривые Безье были разработаны в
шестидесятых годах XX века, независимо

00:17:44.588 --> 00:17:45.949
друг от друга. Пьермье

00:17:47.045 --> 00:17:53.887
Из автомобилей строительной компании Рено
и поле де-Костелья, он же

00:17:54.447 --> 00:17:59.128
Костельжо из компании Ситройн, где
применялись для проектирования кузовов

00:17:59.288 --> 00:18:03.848
автомобилей. Благодаря простоте задания
манипуляции кривые безья нашли широкое

00:18:03.888 --> 00:18:07.009
применение в компьютерной графике для
представления гладких линий

00:18:08.137 --> 00:18:12.695
Вот мы у них в них уже говорили, что
построение кривых без е является решением

00:18:12.775 --> 00:18:16.533
задачи аппроксимации, то есть построение
кривой по узловым точкам.

00:18:16.813 --> 00:18:19.732
При этом кривая необязательно проходит
через данные точки.

00:18:19.812 --> 00:18:24.689
То есть, в случае кривых без е, кривая
проходит через первую и последнюю точку, а

00:18:24.769 --> 00:18:28.847
промежуточные точки играют роль рычагов,
задающих форму кривой.

00:18:29.552 --> 00:18:33.428
То есть кривая без Е — это параметрическая
кривая, задаваемая выражением.

00:18:33.948 --> 00:18:40.581
То есть, соответственно, БТ — сумма, PT в
пределах от нуля до

00:18:40.701 --> 00:18:45.377
единицы. Где, соответственно, П и Т?

00:18:45.617 --> 00:18:48.574
Функция, компоненты векторов опорных
вершин.

00:18:49.380 --> 00:18:54.981
Соответственно, BIT NAT — базисные функции
кривой Безе, называемые также полиномами

00:18:55.061 --> 00:19:01.343
Бернштейна. Соответственно, полиномы
Бернштейна Б определяются

00:19:02.464 --> 00:19:05.825
как вектор-столбец умноженный на Т и Т.

00:19:06.520 --> 00:19:09.677
Вот такое-то выражение, соответственно,

00:19:13.553 --> 00:19:20.387
Ni определяется следующим образом через
факториалы, где N

00:19:20.586 --> 00:19:23.663
— степень полиного, и, соответственно,
порядком.

00:19:24.053 --> 00:19:27.972
Опорные вершины. Наглядный метод
построения этих кривых, предложенных

00:19:28.092 --> 00:19:32.010
де-костелье, основан на разбиении
отрезков, соединяющих исходные точки в

00:19:32.050 --> 00:19:37.088
отношениях T, значение параметра, а затем
в рекурсивном повторении этого процесса

00:19:37.208 --> 00:19:38.567
для полученных отрезков.

00:19:38.687 --> 00:19:39.567
То есть P и T

00:19:40.629 --> 00:19:45.152
С верхним индексом Ж от определяется как
единица минус Т.

00:19:45.713 --> 00:19:52.557
Соответственно, П и Т с верхним индексом Ж
-1 от Т, плюс ТИ, Т с верхним индексом Ж

00:19:52.718 --> 00:19:55.319
минус 1, с низним Т п+1.

00:19:55.399 --> 00:19:55.720
Вот.

00:19:56.194 --> 00:19:58.312
Нижний индекс — номер опорной точки.

00:19:58.432 --> 00:20:00.510
Верхний индекс — уровень разбиения.

00:20:01.069 --> 00:20:06.424
Уравнение энного порядка задаётся,
соответственно, как pT, как p нулевое н от

00:20:06.584 --> 00:20:06.824
Т.

00:20:10.082 --> 00:20:12.844
Функция компонент векторов опорных вершин.

00:20:13.805 --> 00:20:17.087
Вид кривой зависит от количества опорных
точек.

00:20:17.167 --> 00:20:23.731
Наиболее часто используемые линейные,
квадратные, кубические и кривые

00:20:23.892 --> 00:20:24.852
четвёртого порядка.

00:20:38.297 --> 00:20:40.177
Линейные кривые. PN равно 1.

00:20:40.257 --> 00:20:42.816
Кривая представляет собой отрезок прямой
линии.

00:20:43.136 --> 00:20:46.975
Опорные точки Pn и P1 определяют его
начало и конец.

00:20:47.095 --> 00:20:53.694
Кривая задаётся уравнением,
соответственно, BT, то есть

00:20:53.814 --> 00:20:56.813
единица минус P- нулевое + T1.

00:20:57.703 --> 00:21:02.219
Вот где Т у нас в интервале от нуля до
единицы квадратные кривые.

00:21:02.299 --> 00:21:04.097
То есть квадратная кривая без E.

00:21:04.177 --> 00:21:09.932
Имеется в виду, что P равно двум, задаётся
третьей опорной тремя опорными точками.

00:21:10.052 --> 00:21:12.050
То есть П-ноль, П1 и П2.

00:21:12.250 --> 00:21:14.408
И, соответственно, следующим уравнением.

00:21:15.614 --> 00:21:22.052
Получается квадрат BT -T квадрат p
нулевое, плюс 2 T — единица минус Т1

00:21:22.971 --> 00:21:24.931
и плюс Т квадрат .

00:21:26.530 --> 00:21:31.048
Соответственно, принадлежит 01 интервалу
0.1.

00:21:31.168 --> 00:21:35.407
Данное уравнение можно получить с помощью
метода Decasteler следующим образом.

00:21:35.487 --> 00:21:37.006
Обозначим опорные точки как

00:21:37.809 --> 00:21:40.291
Соответственно, P и T от нуля до двух.

00:21:40.731 --> 00:21:46.015
Начало кривой положим в точке p0, Т равно
нулю, а конец в точке p2, Т равно 1.

00:21:46.255 --> 00:21:50.819
И для каждого Т, принадлежащего 0-1,
найдём точку.

00:21:51.419 --> 00:21:53.260
Соответственно, p02 — Т.

00:21:56.378 --> 00:22:03.215
Так, отсюда получаем P01 соответственно

00:22:05.933 --> 00:22:13.889
П11,

00:22:13.929 --> 00:22:14.449
P2.

00:22:15.828 --> 00:22:17.587
Т с верхним индексом 2.

00:22:17.827 --> 00:22:24.583
Так, единица минус То Т умножить на P1T и
соответственно

00:22:24.742 --> 00:22:27.181
равно следующему. Как видно по формуле.

00:22:27.221 --> 00:22:29.619
Таким образом получим кривую второго
порядка.

00:22:30.099 --> 00:22:34.216
Так, на рисунке 4—7, как видите, кривая
БИЕ с тремя опорными точками.

00:22:34.758 --> 00:22:41.244
Точки p01T, 1.1T лежат на кривых первого
порядка, то есть отрезках, соединяющих

00:22:41.324 --> 00:22:45.608
опорные точки P0 с П1 и П1 с П2
соответственно.

00:22:45.968 --> 00:22:51.654
Точки, образующие кривую без Е, то есть P0
второго порядка T лежат на отрезке,

00:22:51.694 --> 00:22:53.335
соединяющем P01T.

00:22:54.033 --> 00:22:58.552
С P11 пропорционально изменению параметров
Т.

00:22:58.952 --> 00:23:01.191
Так, вот как показано на рисунке 4—7

00:23:07.349 --> 00:23:09.748
кривая с тремя опорными точками.

00:23:13.969 --> 00:23:19.853
Кубические кривые. В геометрической форме
кубическая кривая без E N равна трём

00:23:20.053 --> 00:23:21.935
описывается следующим уравнением.

00:23:23.336 --> 00:23:27.819
Соответственно, ну вот тот же полином,
только уже третьего порядка.

00:23:28.619 --> 00:23:32.182
Для получения этой формулы используем
аналогичным образом метод Декостелье.

00:23:32.447 --> 00:23:34.448
То есть уже теперь для третьего порядка.

00:23:34.809 --> 00:23:39.691
Обозначим опорные точки, соответственно, Т
и Т от нуля до трёх.

00:23:39.811 --> 00:23:45.934
Начало кривой положим в отрезке P0, П
равно нулю и конец в точке 3, Т равно 1.

00:23:45.974 --> 00:23:49.977
И для каждого Т в интервале от нуля до
один найдём

00:23:50.756 --> 00:23:52.714
Точку p03 от T.

00:23:52.954 --> 00:23:59.945
И соответственно получаем, как видите,
p01, p1:1, p21,

00:24:00.025 --> 00:24:05.618
p02, p1.2.

00:24:05.698 --> 00:24:06.338
Ну и наконец

00:24:11.895 --> 00:24:17.008
По ноль с индексом 3х индексом.

00:24:17.208 --> 00:24:24.199
Таким образом получим кривую третьего
порядка, как показано на рисунке кривая

00:24:24.518 --> 00:24:26.715
БезЕ с четырьмя опорными точками.

00:24:30.632 --> 00:24:31.992
Четыре опорные точки.

00:24:32.231 --> 00:24:36.749
Соответственно, 0, 1, П2 и П3, заданные в
двух или трёхмерных пространстве,

00:24:36.789 --> 00:24:38.189
определяют форму кривой.

00:24:38.548 --> 00:24:44.346
Линия берёт начало из точки 0, направляясь
к П1 и заканчивается в точке 3, подходя к

00:24:44.386 --> 00:24:48.624
ней со стороны П2. То есть кривая не
проходит через точки 1 и П2, они

00:24:48.784 --> 00:24:50.543
используются для указания её направления.

00:24:51.045 --> 00:24:56.926
Длина отрезка между P0 и P1 определяет,
как скоро кривая повернёт к P3.

00:24:57.366 --> 00:25:00.727
Соответственно, в матричной форме
кубическая кривая Безе записывается

00:25:00.847 --> 00:25:02.327
следующим образом.

00:25:05.568 --> 00:25:06.648
То есть BT.

00:25:07.512 --> 00:25:14.279
Равня вектор столбец матрица MB умножить
на вектор, то есть вектор-строка,

00:25:14.319 --> 00:25:16.401
матрица MB умножить на вектор столбец.

00:25:16.481 --> 00:25:22.047
Где, соответственно, матрица MB называется
базисной матрицей без Е.

00:25:22.607 --> 00:25:24.569
Ну, в данном случае равно следующему.

00:25:35.358 --> 00:25:38.877
Сплайн безье. Кривые безье обладают рядом
свойств.

00:25:39.237 --> 00:25:42.956
Непрерывность заполнения сегмента между
начальной и конечной точками,

00:25:43.076 --> 00:25:46.755
инвариантность относительно финных
преобразований, как следствие, поворот

00:25:46.835 --> 00:25:51.073
вокруг точки, масштабирование, изменение
пропорции кривой безье.

00:25:51.942 --> 00:25:58.378
не нарушает её стабильности Кривая Безье
принадлежит выпуклой оболочке опорных

00:25:58.498 --> 00:26:02.854
точек То есть кривая всегда располагается
внутри фигуры, образованной линиями,

00:26:02.894 --> 00:26:04.373
соединяющими контрольные точки.

00:26:04.573 --> 00:26:06.732
Если все опорные точки лежат на одной
прямой

00:26:07.022 --> 00:26:10.944
То кривая Безье вырождается в отрезок,
соединяющий эти точки.

00:26:11.064 --> 00:26:12.665
Кривая Безье симметрична.

00:26:12.785 --> 00:26:18.388
То есть обмен местами между начальной и
конечной точками, изменение направления

00:26:18.548 --> 00:26:20.709
траектории не влияет на форму кривой.

00:26:21.190 --> 00:26:24.592
Степень многочлена, представляющая кривую
в аналитическом виде

00:26:25.376 --> 00:26:28.294
На единицу меньше, чем число опорных
точек.

00:26:28.814 --> 00:26:33.891
Одним из главных свойств, соответственно,
кубических кривых безье является

00:26:34.411 --> 00:26:36.570
возможность составления из них сплаинов.

00:26:36.690 --> 00:26:42.046
Понятие сплаина широко пришло из
машиностроения, где сплаи называет гибкую

00:26:42.086 --> 00:26:46.244
линейку, закрепив которую в нужных местах,
добивались плавной формы кривой.

00:26:46.790 --> 00:26:48.751
А затем чертили её по этой линейке.

00:26:48.831 --> 00:26:54.272
В математике под сплаином обычно понимают
кусочной функцию, совпадающую с функциями

00:26:54.432 --> 00:26:59.073
более простой природы: на каждом элементе
разбиения свои области определения.

00:26:59.314 --> 00:27:01.434
В случае с кривыми безе сплаин обычно

00:27:02.676 --> 00:27:05.037
Составляется из нескольких кубических
кривых.

00:27:05.157 --> 00:27:10.120
То есть, если точка PN является
стыковочной точкой, то для соблюдения

00:27:10.200 --> 00:27:15.563
условия гладкости кривой в ней необходимо,
чтобы выполнялись условия

00:27:16.203 --> 00:27:19.365
коленеарности, то есть соседними узловыми
точками.

00:27:20.245 --> 00:27:21.726
Рисунок 4,9.

00:27:25.936 --> 00:27:29.259
Соблюдение условий гладкости на стыке
кривых бесье

00:27:33.303 --> 00:27:38.147
Однако даже такие достаточно развитые
средства апроксимации кривыми бесье не

00:27:38.227 --> 00:27:41.911
позволяют построить окружность,
описываемую параметрически, например

00:27:43.440 --> 00:27:46.443
Икс равняется косинусу Т, и игрек
равняется синус Т.

00:27:46.563 --> 00:27:50.727
Так как синус и косинус для достаточно
хорошего приближения требует многочленов

00:27:50.927 --> 00:27:52.328
более высокой степени.

00:27:55.571 --> 00:27:57.053
Так, следующий вопрос.

00:27:57.854 --> 00:28:00.336
Закраска области, заданной цветом границы.

00:28:02.019 --> 00:28:05.579
Так, следующая задача — закраска области,
заданной цветом границы, как мы

00:28:05.619 --> 00:28:09.578
рассматриваем? Рассмотрим область,
ограниченную набором пикселей заданного

00:28:09.698 --> 00:28:14.498
цвета и точку X-грек, лежащую внутри этой
области.

00:28:14.818 --> 00:28:19.097
Задача заполнения области заданной цветом
в случае, когда эта область не является

00:28:19.497 --> 00:28:21.497
выпуклой, может оказаться довольно
сложной.

00:28:22.178 --> 00:28:26.018
Так, ну вот приведём простейший
рекурсивный алгоритм заполнения области.

00:28:26.498 --> 00:28:29.577
Определяем, соответственно, переменные.

00:28:32.137 --> 00:28:35.456
Соответственно, используем

00:28:40.656 --> 00:28:42.175
функцию Get Pixel.

00:28:42.941 --> 00:28:49.430
И таким образом, как видите, тут

00:28:49.591 --> 00:28:55.118
использовалась функция My Pixel Fil.

00:29:02.313 --> 00:29:08.557
Так, заметим, что корректное использование
метода get Pixel-1, то есть просто

00:29:08.717 --> 00:29:14.881
cat-Pixel. Возможно, если предварительно
объекты типа Graffics и Bitmap, связанные,

00:29:14.921 --> 00:29:17.403
инициализируются следующим образом, то
есть как

00:29:18.178 --> 00:29:24.982
New Bitmap, ссылка, собственно, на сам
класс, на сам объект и

00:29:25.222 --> 00:29:30.345
так далее. Этот алгоритм является слишком
неэффективным, так как для всякого уже

00:29:30.505 --> 00:29:34.267
отрисованного пикселя функция вызывает ещё
четыре раза.

00:29:34.347 --> 00:29:37.508
И, кроме того, этот алгоритм требует
слишком большого объёма стека.

00:29:38.038 --> 00:29:40.239
из-за большой глубины рекурсии.

00:29:40.639 --> 00:29:47.281
Поэтому для решения задачи закраски
области предпочтительнее

00:29:47.321 --> 00:29:51.163
алгоритмы способны обрабатывать сразу
целые группы пикселей, то есть

00:29:51.283 --> 00:29:52.723
использовать их связность.

00:29:53.033 --> 00:29:55.276
...или когерентность, так называемая.

00:29:55.516 --> 00:29:59.681
Если данный пиксель принадлежит области,
то, скорее всего, его ближайшие соседи

00:29:59.882 --> 00:30:01.644
также принадлежат данной области.

00:30:02.324 --> 00:30:06.609
Группой таких пикселей обычно выступает
полоса, определяемая правым пикселем для

00:30:06.730 --> 00:30:09.413
хранения правых определяющих пикселей.

00:30:10.140 --> 00:30:11.540
Используется стек.

00:30:12.180 --> 00:30:16.101
Словесно опишем улучшенный алгоритм,
использующий конгерентность пикселей.

00:30:16.221 --> 00:30:20.821
Сначала заполняется горизонтальная полоса
пикселей, содержащих начальную точку.

00:30:21.261 --> 00:30:26.941
Затем, чтобы найти самый правый пиксель
каждой строки справа налево, проверяется

00:30:27.101 --> 00:30:27.621
строка.

00:30:28.034 --> 00:30:31.757
Предыдущая по отношению к только что
заполненной полосе.

00:30:32.198 --> 00:30:35.600
Адреса найденных пикселей заносятся в
стек.

00:30:35.841 --> 00:30:40.084
То же самое выполняется и для строки,
следующей за последней заполненной

00:30:40.204 --> 00:30:45.128
полосой. Когда строка обработана таким
способом, в качестве новой начальной

00:30:45.208 --> 00:30:48.451
точки, используется пиксель, адрес
которого берётся из стека.

00:30:49.330 --> 00:30:53.046
Для него повторяется вся описанная
процедура.

00:30:53.366 --> 00:30:57.121
Соответственно, алгоритм заканчивает свою
работу, если стек пуст.

00:30:58.600 --> 00:31:00.837
Так, ну вот такой, собственно, алгоритм.

00:31:02.453 --> 00:31:03.892
Заполнение многоугольника.

00:31:04.012 --> 00:31:08.011
Часто возникает задача заполнения
многоугольников, заданных набором вершин.

00:31:08.131 --> 00:31:11.569
Задача заполнения многоугольников решается
в два этапа.

00:31:11.729 --> 00:31:15.968
Сначала проводится операция отсечения
многоугольника.

00:31:16.288 --> 00:31:20.406
Затем производится заполнение полученных
многоугольников.

00:31:21.336 --> 00:31:26.298
Этап отсечения необходим для определения
реальных областей многоугольника, которые

00:31:26.738 --> 00:31:28.219
будут выведены на экран.

00:31:28.379 --> 00:31:34.781
Это необходимо, если многоугольник больше
или выходит за пределы экрана или окна

00:31:34.861 --> 00:31:38.182
вывода. Отсечение многоугольников.

00:31:38.262 --> 00:31:39.743
Отсечение многоугольников часто

00:31:40.422 --> 00:31:44.661
Чаще всего приводится для отбрасывания
частей многоугольников, выходящих за

00:31:44.741 --> 00:31:49.300
границу прямоугольной области, которая
определяет экран или область окна.

00:31:49.500 --> 00:31:53.619
Однако отсечение может проводиться
относительно и другого многоугольника.

00:31:53.859 --> 00:31:56.018
При этом порождается новый многоугольник.

00:31:56.797 --> 00:31:59.236
Или несколько новых многоугольников.

00:31:59.356 --> 00:32:03.436
Рассмотрим алгоритм, соответственно
Сензерленда Хотмана.

00:32:03.796 --> 00:32:05.995
Соответственно, Сензерленд Холтман.

00:32:07.075 --> 00:32:11.315
В алгоритме используется стратегия
«Разделяй и властвуй», которая позволяет

00:32:11.595 --> 00:32:15.474
решение общей задачи свести к решению ряда
простых и похожих подзадач.

00:32:15.554 --> 00:32:16.754
Примером такой подзадачи

00:32:19.730 --> 00:32:24.206
Является отсечение многоугольника
относительно одной отсекающей границы.

00:32:24.366 --> 00:32:29.482
Последовательное решение четырёх таких
задач и может позволяет привести,

00:32:29.602 --> 00:32:32.680
собственно, отсечение относительно
прямоугольной области.

00:32:32.840 --> 00:32:35.078
Вот так. Как рисунок 4—10.

00:32:40.338 --> 00:32:42.817
Так, ну и соответственно
последовательность решения четырёх таких

00:32:42.897 --> 00:32:46.815
задач позволяет провести отсечение
относительно прямоугольной области.

00:32:47.495 --> 00:32:50.374
Рисунок — последовательность сечения
прямоугольника.

00:32:53.932 --> 00:32:57.890
На вход алгоритма поступает
последовательность вершин многоугольника,

00:32:58.010 --> 00:33:00.329
соответственно, B1, B2 и так далее, BN.

00:33:00.763 --> 00:33:05.759
Ребра многоугольника проходят,
соответственно, от VIT к I +.

00:33:05.879 --> 00:33:10.356
И, соответственно, потом от последней
вершины к первой, то есть от BN к В1.

00:33:10.635 --> 00:33:14.232
С помощью алгоритма производится отсечение
относительно ребра.

00:33:14.792 --> 00:33:18.789
И выводится другая последовательность
вершин, описывающих усечённый

00:33:18.988 --> 00:33:19.668
многоугольник.

00:33:20.585 --> 00:33:22.828
Алгоритм он ходит вокруг многоугольника.

00:33:22.908 --> 00:33:26.673
Соответственно, вот VN к 1 и обратно VN.

00:33:26.753 --> 00:33:32.921
Проверяя на каждом шаге соотносение между
последовательными вершинами и отсекающий

00:33:33.001 --> 00:33:35.524
границы. Необходимо проанализировать
четыре случая.

00:33:38.770 --> 00:33:41.372
Итак, рассмотрим изображение на рисунке
4.11.

00:33:41.533 --> 00:33:45.656
Ребро многоугольника, соединяющего вершину
S малую с вершиной p малое.

00:33:45.776 --> 00:33:49.379
В первом случае ребро полностью лежит
внутри отсекающей границы.

00:33:49.819 --> 00:33:52.942
К выходному списку добавляется вершина p.

00:33:53.703 --> 00:33:55.424
Во втором случае в качестве вершин

00:33:56.563 --> 00:33:58.604
Выводится точка пересечения i.

00:33:58.724 --> 00:34:04.127
Поскольку ребро пересекает границу, а
начальная точка была выведена при анализе

00:34:04.207 --> 00:34:10.171
первого случая, в третьем случае обе
вершины находятся за пределами границ.

00:34:11.011 --> 00:34:13.493
И ни одна из них не выводится.

00:34:14.191 --> 00:34:19.706
В четвёртом случае к выходному списку
добавляется и точка пересечения E и

00:34:19.905 --> 00:34:21.224
вершина P.

00:34:23.302 --> 00:34:27.418
Соответственно, как видите, рисунки, вот,
собственно, случаи

00:34:30.015 --> 00:34:31.414
показаны на данном слайде.

00:34:39.425 --> 00:34:44.500
При отсечении многоугольника, описанном
алгоритмом, возникает проблема, связанная

00:34:44.580 --> 00:34:49.055
с тем, что появляются рёбра, частично
совпадающие с границей окон.

00:34:51.885 --> 00:34:57.329
При отсечении, так, то есть лишение ребра
можно устранить, введя дополнительную

00:34:57.449 --> 00:35:02.011
обработку или воспользовавшись более
общим, более сложным алгоритмом Валера

00:35:02.051 --> 00:35:05.814
Азартена.

00:35:05.974 --> 00:35:07.375
Так, следующая задача.

00:35:08.237 --> 00:35:09.759
Заполнение многоугольников.

00:35:10.000 --> 00:35:14.125
Рассмотрим, каким образом можно заполнить
многоугольник, создаваемый замкнутой

00:35:14.285 --> 00:35:17.209
ломаной линией без самопересечений.

00:35:17.329 --> 00:35:21.774
Простейший способ закраски многоугольника
состоит в проверке принадлежности каждой

00:35:21.814 --> 00:35:23.176
точки этому многоугольнику.

00:35:23.908 --> 00:35:28.467
Более эффективный алгоритм использует тот
факт, что соседние пиксели, вероятно,

00:35:28.507 --> 00:35:33.747
имеют одинаковые характеристики, кроме
пикселей и граничных рёбер.

00:35:33.827 --> 00:35:39.066
Это свойство называется пространственной
когерентностью.

00:35:39.848 --> 00:35:41.288
...пространственной когерентностью.

00:35:41.368 --> 00:35:47.887
В случае с многоугольником когерентность
пикселей определяется вдоль сканирующей

00:35:47.927 --> 00:35:53.246
строки. Сканирующие строки обычно
изменяются от верха многоугольника до его

00:35:53.406 --> 00:35:58.766
низа. Характеристики пикселей изменяются
только тем, что ребро многоугольника

00:35:58.885 --> 00:35:59.845
пересекает строку.

00:36:00.584 --> 00:36:05.068
Эти пересечения делят сканирующую строку
на области закрашенных и незакрашенных

00:36:05.148 --> 00:36:09.752
пикселей. Рассмотрим, какие случаи могут
возникать при делении многоугольника на

00:36:09.832 --> 00:36:11.834
области сканирующей строкой.

00:36:15.437 --> 00:36:17.159
Так, соответственно, рисунок.

00:36:17.431 --> 00:36:21.595
Прохождение сканирующих строк по
многоугольнику.

00:36:31.044 --> 00:36:32.165
Простой случай.

00:36:32.467 --> 00:36:33.946
На примере сумма 412.

00:36:34.026 --> 00:36:37.423
Сканирующая строка чек равно 4 пересекает
многоугольник.

00:36:37.423 --> 00:36:39.342
При X равно 1, X равно шесть.

00:36:39.502 --> 00:36:46.218
Получается, соответственно, три области: X
меньше 1, X от 1 до 6 и X больше 8.

00:36:47.068 --> 00:36:51.589
Сканирующая строка грек равно шести
пересекает многоугольник при X равно 1, X

00:36:51.749 --> 00:36:54.030
равно два, кс равно пять и X равно шесть.

00:36:54.110 --> 00:36:55.951
И получается пять областей.

00:36:56.311 --> 00:37:01.833
Соответственно, X меньше 1, интервал — X
от 1 до 2.

00:37:02.393 --> 00:37:03.833
Соответственно, далее.

00:37:05.485 --> 00:37:10.280
От 2 до пяти, от пяти до шести и X больше
шести.

00:37:10.360 --> 00:37:13.317
В этом случае икс сортируется в порядке
возрастания.

00:37:13.437 --> 00:37:16.754
Далее список иксов рассматривается
попарно.

00:37:17.434 --> 00:37:21.150
Между парами точек пересечения
закрашиваются все пиксели.

00:37:21.190 --> 00:37:24.507
Для grek равно четыре закрашиваются
пиксели в интервале 16.

00:37:25.155 --> 00:37:29.119
Для igrek равно шести закрашиваются
пиксели в интервалах 1—2 и,

00:37:29.159 --> 00:37:30.760
соответственно, 5—6.

00:37:38.528 --> 00:37:40.971
Сканирующая строка проходит через вершину.

00:37:41.266 --> 00:37:45.859
Рисунок 4:13, например, со сканирующей
строкой Y.

00:37:45.939 --> 00:37:47.856
Так, ну давайте сначала посмотрим рисунок.

00:37:56.734 --> 00:38:01.011
Так, например, со сканирующей строкой
игрек равно трём, упорядочен список,

00:38:01.051 --> 00:38:03.449
соответственно, X получается как 2,2, 4.

00:38:03.609 --> 00:38:08.246
Вершина многоугольника была учтена дважды,
и поэтому закрашиваем интервал, получается

00:38:08.926 --> 00:38:10.525
неверным, то есть 2.2.

00:38:10.724 --> 00:38:15.042
Следовательно, при пересечении вершины с
сканирующей строкой она должна учитываться

00:38:15.161 --> 00:38:15.801
единожды.

00:38:16.219 --> 00:38:20.022
Из список по X в приведённом примере будет
2,4.

00:38:20.983 --> 00:38:24.826
Сканирующая строка проходит через
локальный минимум или максимум.

00:38:24.906 --> 00:38:28.349
Соответственно, вот смотри, рисунок 4.2
при р равно пять

00:38:36.557 --> 00:38:37.918
локальный минимум.

00:38:41.408 --> 00:38:45.168
В этом случае учитываются все пересечения
вершин сканирующейся строкой.

00:38:45.208 --> 00:38:51.926
На рисунке, соответственно, 12 404.12 при
равно 5, формируется список X 1

00:38:52.326 --> 00:38:54.805
4 6. Закрашиваем интервалы.

00:38:55.448 --> 00:38:57.047
Один, четыре, четыре, шесть.

00:38:57.247 --> 00:39:01.203
Условное нахождение локального минимума
или максимума определяется при

00:39:01.363 --> 00:39:05.439
рассмотрении концевых вершин для рёбер,
соединённых в вершине.

00:39:05.559 --> 00:39:11.154
Если у обоих концов координаты игрек
больше, соответственно, чем у вершины

00:39:11.314 --> 00:39:13.952
пересечения эта вершина есть локальный
минимум.

00:39:14.111 --> 00:39:16.709
Если меньше, то вершина пересечения
локальный максимум.

00:39:17.492 --> 00:39:21.612
Так, рисунок 4.13 — прохождение
сканирующей строки через вершину.

00:39:23.692 --> 00:39:30.332
Для ускорения работы алгоритма

00:39:30.452 --> 00:39:32.412
используется список активных рёбер.

00:39:32.532 --> 00:39:34.572
Сар, список активных рёбер.

00:39:34.772 --> 00:39:37.732
Этот список содержит те рёбра
многоугольника, которые

00:39:38.649 --> 00:39:40.529
Пересекают сканирующую строку.

00:39:40.690 --> 00:39:44.411
При пересечении очередной сканирующей
строки вершины многоугольника Иссар

00:39:45.332 --> 00:39:50.775
удаляются рёбра, которые находятся выше, и
добавляются концы, которые пересекает

00:39:51.135 --> 00:39:55.897
сканирующую строку. При работе алгоритма
находятся пересечение сканирующей строки.

00:39:56.422 --> 00:40:01.304
Только с рёбрами из то есть списка
активных рёбер.

00:40:04.906 --> 00:40:08.628
Так, соответственно, следующий вопрос:
методы устранения ступенчатости.

00:40:08.828 --> 00:40:12.790
Основная причина появления лестничного
эффекта заключается в том, что отрезки

00:40:12.870 --> 00:40:15.911
ребра многоугольника, световые границы и
прочее, имеют

00:40:16.854 --> 00:40:18.335
непрерывную природу.

00:40:18.415 --> 00:40:20.816
Тогда как расстровые устройства
дискретные.

00:40:20.936 --> 00:40:27.901
То есть вот лестничный эффект проявляется
первое: призуализации мелких деталей,

00:40:27.941 --> 00:40:32.224
при прорисовке рёбер и границ при анимации
мелких деталей.

00:40:32.304 --> 00:40:34.705
Опишем основные методы устранения
ступенчатости.

00:40:35.842 --> 00:40:37.723
Методы увеличения частоты выборки.

00:40:37.923 --> 00:40:41.364
Первый метод устранения ступенчатый связан
с увеличением частоты выборки.

00:40:41.444 --> 00:40:44.365
То есть увеличение частоты выборки
достигается с помощью увеличения

00:40:44.845 --> 00:40:46.086
разрешения растра.

00:40:46.166 --> 00:40:48.647
Таким образом, учитываются более мелкие
детали.

00:40:48.727 --> 00:40:51.648
Каждый пиксель делится на подпиксели.

00:40:53.072 --> 00:40:56.667
В процессе формирования растра более
высокого разрешения.

00:40:57.147 --> 00:41:01.462
Для получения атрибутов дисплейного
пикселя определяются атрибуты в центре

00:41:01.582 --> 00:41:04.498
каждого пикселя, которые потом
усредняются.

00:41:04.698 --> 00:41:08.694
Пиксели в этом случае распределяются
равномерно, и их атрибуты учитываются

00:41:08.813 --> 00:41:09.293
одинаково.

00:41:10.257 --> 00:41:14.933
Так вот, как рисунок: увеличение
разрешения в два раза, то есть был один

00:41:15.093 --> 00:41:18.410
пиксель, стал четыре. Увеличение
разрешения также в четыре раза.

00:41:18.610 --> 00:41:20.288
Ну, что приводит к следующему.

00:41:20.848 --> 00:41:25.364
В некоторой степени можно получить лучшие
результаты, если рассматривать больше под

00:41:25.524 --> 00:41:28.322
пикселей и учитывать их влияние с помощью
весов.

00:41:29.427 --> 00:41:35.710
При определении атрибутов, соответственно,
как показано на данном

00:41:35.790 --> 00:41:41.953
рисунке, числа обозначают относительно
веса каждого подпикселя.

00:41:50.637 --> 00:41:51.278
Следующее.

00:41:51.893 --> 00:41:55.249
Метод исполь на использовании полутонов.

00:41:55.689 --> 00:41:59.405
В этом эвристическом методе интенсивность
пикселя на ребре устанавливается

00:41:59.565 --> 00:42:03.520
пропорционально площади части пикселя,
находящегося внутри многоугольника.

00:42:03.760 --> 00:42:08.075
Вот как на рисунке 4:14 показана закраска
ребра.

00:42:09.195 --> 00:42:13.680
То есть граница такая может быть не очень
интенсивная получается.

00:42:15.402 --> 00:42:20.808
На рисунке предыдущем 4:14 проводится,
приводится многоугольник, ребро которого

00:42:21.169 --> 00:42:23.932
сгенерировано основным алгоритмом Брезинг
Хейма.

00:42:24.212 --> 00:42:25.374
Пиксели в этом ребре

00:42:26.677 --> 00:42:29.560
И внутренние пиксели многоугольника
полностью закрашены.

00:42:29.640 --> 00:42:33.283
Пиксели, находящиеся выше ребра,
закрашиваются с различной интенсивностью,

00:42:33.363 --> 00:42:37.327
которая пропорциональна площади пикселя,
попадающего внутрь прямоугольника.

00:42:40.129 --> 00:42:42.652
Следующий вопрос — методы обработки
изображения.

00:42:43.042 --> 00:42:46.480
Часто в компьютерной графике возникает
задача обработки изображений.

00:42:47.359 --> 00:42:51.957
Обработка, как правило, заключается в
положении на изображении, в наложении на

00:42:52.117 --> 00:42:53.876
изображение каких-либо эффектов.

00:42:53.956 --> 00:42:59.074
То есть это размытие, резкость,
деформация, шум и так далее, а также

00:42:59.154 --> 00:43:01.113
регулирование уровня яркости и контраста.

00:43:02.199 --> 00:43:05.676
Ну, прежде всего вопрос: яркость и
контраст.

00:43:06.435 --> 00:43:10.511
Яркость и контраст являются субъективными
характеристиками изображения,

00:43:10.591 --> 00:43:11.910
воспринимаемого человеком.

00:43:12.069 --> 00:43:17.224
Яркость брайтнес представляет собой
характеристику, определяющую то, насколько

00:43:17.384 --> 00:43:20.142
сильно цвета пикселей отличаются от
чёрного цвета.

00:43:20.757 --> 00:43:25.633
Например, если оцифрованная фотография
сделана в солнечную погоду, то её яркость

00:43:25.753 --> 00:43:30.390
будет значительной. С другой стороны, если
фотография сделана вечером или ночью, то

00:43:30.510 --> 00:43:31.789
её яркость будет невелика.

00:43:32.108 --> 00:43:36.225
В световом пространстве РЖБ яркость можно
рассматривать как средне-арифметическое,

00:43:36.265 --> 00:43:38.383
мю красного, зелёного, синего цветов.

00:43:39.297 --> 00:43:46.289
Координаты. В световых моделях, таких как
SSB или HSV, значение

00:43:46.449 --> 00:43:48.927
яркости указано напрямую.

00:43:49.126 --> 00:43:51.684
То есть, как специальный сигнал яркости.

00:43:52.523 --> 00:43:55.760
Контраст, контраст представляет собой
характеристику того

00:43:58.135 --> 00:44:01.572
Насколько большой разброс имеют цвета
пиксели изображения?

00:44:01.732 --> 00:44:05.528
Чем больше разброс имеет значение цветов
пикселей, тем больше контраст имеет

00:44:05.648 --> 00:44:09.764
изображение. По аналогии с терминами
теории вероятности можно отметить, что

00:44:09.964 --> 00:44:14.040
яркость представляет собой как бы
математическое ожидание значений выборки.

00:44:15.082 --> 00:44:17.722
А контраст, дисперсию значений выборки.

00:44:18.883 --> 00:44:22.843
Яркость и контраст могут рассматриваться
не только для всего изображения, но и для

00:44:22.963 --> 00:44:26.443
отдельных фрагментов. Таким образом
возникает понятие локальной яркости и

00:44:26.523 --> 00:44:27.803
локального контраста.

00:44:28.443 --> 00:44:31.564
Часто требуется изменить яркость или
контраст изображения.

00:44:31.644 --> 00:44:35.284
Рассмотрим функцию в области определения
значений, которой является значение

00:44:35.444 --> 00:44:36.524
цветовых компонентов.

00:44:37.279 --> 00:44:42.078
Модели РЖБ. Аргументом функции является
цвет пикселя исходного изображения.

00:44:44.757 --> 00:44:49.037
Значение функции представляет собой цвет
пикселя обработанного изображения.

00:44:49.197 --> 00:44:54.035
Для изменения яркости контраста функция
применяется для каждого пикселя

00:44:54.155 --> 00:44:54.715
изображения.

00:44:55.397 --> 00:44:59.395
Для нормализации выходных значений функции
они должны принадлежать, соответственно,

00:44:59.435 --> 00:45:01.075
отрезку от нуля до единицы.

00:45:01.275 --> 00:45:05.674
Как для каждого компонента модели RGB,
используется так называемая арифметика с

00:45:05.714 --> 00:45:10.672
насыщением. В арифметике с насыщением при
возникновении переполнений или заёмов

00:45:10.752 --> 00:45:11.232
фиксируется

00:45:11.974 --> 00:45:15.538
Наибольшее представимое или наименьшее
представимое значение соответственно.

00:45:15.698 --> 00:45:19.383
Например, если в результате преобразования
оказывается, что значение какого-либо

00:45:19.503 --> 00:45:23.668
компонента модели РЖБ меньше нуля, то
берётся значение ноль.

00:45:24.068 --> 00:45:27.392
На практике же каждый элемент матрицы
изображения, соответственно

00:45:28.619 --> 00:45:35.539
Цифры указанные на слайде, три семёрки,
216 цветами представляет

00:45:35.659 --> 00:45:40.418
собой 24 битное значение, где каждый
компонент модели РЖП представляется

00:45:40.658 --> 00:45:43.818
восьмью битами. Поэтому вместо интервала
0,1

00:45:45.110 --> 00:45:47.672
Используется интервал от нуля до 255.

00:45:48.112 --> 00:45:52.514
Если яркость и контраст изображения никак
не меняются в процессе преобразования, то

00:45:52.674 --> 00:45:56.116
функция имеет график, представленный на
рисунке 4.15А.

00:45:56.396 --> 00:46:00.958
Из рисунка видно, что функция в этом
случае просто передаёт на выход значение

00:46:01.078 --> 00:46:02.158
своего аргумента.

00:46:04.512 --> 00:46:05.991
Соответственно, рисунок.

00:46:12.464 --> 00:46:16.060
Яркость для рассматриваемой функции
представляет собой сдвиг прямой линии в

00:46:16.100 --> 00:46:19.657
вертикальном направлении. Яркость
изображения увеличивается пропорциональна

00:46:19.697 --> 00:46:21.934
сдвигу прямой. Если прямая сдвигается
вверх

00:46:22.461 --> 00:46:25.943
Соответственно, рисунок Б, яркость
изображения увеличивается.

00:46:26.023 --> 00:46:30.665
А если прямая сдвигается вниз, рисунок B,
соответственно, то уменьшается.

00:46:31.465 --> 00:46:37.628
Поскольку используемая арифметика с
насыщением, то при установке определённой

00:46:37.708 --> 00:46:41.269
яркости изображение либо полностью
окажется засвеченным, либо полностью

00:46:41.349 --> 00:46:41.990
затемнённым.

00:46:42.722 --> 00:46:46.039
Соответственно, при использовании
преобразования контраста прямая линия

00:46:46.079 --> 00:46:47.598
меняет свои свой наклон.

00:46:47.718 --> 00:46:52.395
При увеличении контраста изображения 416,
наклон прямой увеличивается.

00:46:53.234 --> 00:46:57.191
Соответственно, при уменьшении контраста
уменьшается.

00:46:57.791 --> 00:46:59.270
Рисунок 4—16 Б.

00:47:00.693 --> 00:47:04.210
При этом сдвиг прямой в горизонтальном
направлении означает, что помимо

00:47:04.330 --> 00:47:08.846
контраста, контраст, контраст изменяется и
яркость изображения.

00:47:09.605 --> 00:47:12.762
Так, ну вот иллюстрация графика
контрастности.

00:47:12.882 --> 00:47:16.718
Видите, в координатах от нуля до 25 по X и
по yку.

00:47:23.188 --> 00:47:27.507
Комбинация наклона и сдвига прямой
позволяет одновременно изменять и яркость,

00:47:27.507 --> 00:47:28.947
и контраст изображения.

00:47:29.387 --> 00:47:35.667
Например, на рисунке 4:17 представлен
график функции, усиливающий контраст и

00:47:35.747 --> 00:47:37.707
увеличивающий яркость изображения.

00:47:38.067 --> 00:47:38.667
Соответственно.

00:47:39.890 --> 00:47:42.530
Рисунок 417, увеличение яркости и
контрастности.

00:47:42.610 --> 00:47:47.131
Преобразование яркости контраста может
быть применено и к отдельным компонентам

00:47:47.251 --> 00:47:52.172
модели RGB. Например, к компоненту
красного цвета, тогда яркость и контраст

00:47:52.972 --> 00:47:55.333
будут изменяться только для красного
компонента.

00:47:55.413 --> 00:47:56.373
А для других компонентов

00:47:56.978 --> 00:47:58.336
Они останутся неизменными.

00:47:58.456 --> 00:48:02.532
Более того, можно задать различные
преобразования яркости, контраста

00:48:02.732 --> 00:48:06.249
одновременно для каждого компонента модели
РЖБ.

00:48:11.244 --> 00:48:12.642
Масштабирование изображения.

00:48:13.526 --> 00:48:17.527
Масштабирование изображения позволяет
сжать или растянуть его по горизонтали или

00:48:17.687 --> 00:48:21.888
вертикали. При этом изменяется ширина или
высота изображения.

00:48:22.288 --> 00:48:24.288
Для масштабирования задаются масштабные

00:48:29.793 --> 00:48:35.111
Коэффициенты — то, насколько нужно сжать,
растянуть изображение по горизонтали или

00:48:35.231 --> 00:48:40.149
вертикали. Масштабные коэффициенты могут
задаваться нормализованной, процентной или

00:48:40.988 --> 00:48:42.268
непосредственной форме.

00:48:42.348 --> 00:48:46.386
В нормализованной форме за единицу
принимается размер исходного изображения.

00:48:47.181 --> 00:48:50.338
Значение меньше единицы указывают на
сжатие изображения.

00:48:50.458 --> 00:48:52.536
Значение больше единицы — на растяжение.

00:48:52.896 --> 00:48:57.012
В процентной форме нормализованное
значение умножается на 100%.

00:48:57.292 --> 00:49:01.288
В непосредственной форме новые размеры по
горизонтали и вертикали задаются в виде

00:49:01.368 --> 00:49:03.925
количества пикселей по тому или другому
измерению.

00:49:04.647 --> 00:49:09.571
Возникает вопрос о том, каким образом
определять цвета при измерении размеров

00:49:09.771 --> 00:49:13.535
изображения? Существует два основных
подхода к этой проблеме.

00:49:13.655 --> 00:49:16.738
Цвет пикселя в масштабированном
изображении принимается равным цвету

00:49:16.818 --> 00:49:19.460
ближайшего к нему пикселя исходного
изображения.

00:49:20.141 --> 00:49:20.541
Два.

00:49:21.505 --> 00:49:22.745
Использование интерполяции.

00:49:22.825 --> 00:49:27.106
В этом случае цвет пикселя масштабируемого
изображения вычисляется как значение

00:49:27.266 --> 00:49:31.906
некоторой интерполирующей функции цветов
соседних пикселей в исходном изображении.

00:49:34.027 --> 00:49:38.507
При использовании белинейной интерполяции
цвет вычисляется как ближайший взвешенная

00:49:38.587 --> 00:49:41.348
сумма ближайших четырёх пикселей исходного
изображения.

00:49:42.598 --> 00:49:46.839
При увеличении или как взвешенная сумма
группа пикселей при уменьшении Первый

00:49:47.239 --> 00:49:51.960
подход достаточно прост, но не всегда даёт
приемлемое качество обрабатываемого

00:49:52.040 --> 00:49:57.481
изображения. Например, если новый размер
намного больше старого, то возникает

00:49:57.562 --> 00:49:59.242
блочная структура изображения.

00:49:59.322 --> 00:50:02.282
То есть каждый пиксель исходного
изображения соответствует квадратной

00:50:02.362 --> 00:50:04.163
области пикселя одного и того же цвета.

00:50:05.154 --> 00:50:06.394
В обратном изображении.

00:50:06.474 --> 00:50:09.674
Эта аномалия представлена, соответственно,
на рисунке 4—18.

00:50:09.914 --> 00:50:14.193
С другой стороны, если новый размер
намного меньше старого, то при

00:50:14.313 --> 00:50:17.473
масштабировании одному пикселю
обрабатываемого изображения соответствует

00:50:17.553 --> 00:50:19.433
группа пикселей исходного изображения.

00:50:19.513 --> 00:50:22.992
Причём в процессе масштабирования
фактически выбирается случайный пиксель

00:50:23.072 --> 00:50:23.552
этой группы.

00:50:29.697 --> 00:50:33.576
Так, вот пример некорректное увеличение.

00:50:42.333 --> 00:50:46.052
Подход, использующий интерполяцию,
позволяет достичь более высокого качества

00:50:46.132 --> 00:50:48.012
изображения на более сложной реализации.

00:50:48.092 --> 00:50:51.571
Обычно используется билинейная или
би-кубическая интерполяция.

00:50:52.370 --> 00:50:55.930
Бикубическая интерполяция позволяет
получить изображение с более высоким

00:50:56.010 --> 00:50:58.210
качеством, чем белинейная интерполяция.

00:50:58.250 --> 00:51:02.570
Однако следует заметить, что при
дальнейшем повышении порядка интерполяции

00:51:02.770 --> 00:51:06.010
качество получаемого изображения может
улучшаться незначительно.

00:51:06.530 --> 00:51:08.130
Приведём простейшую формулу.

00:51:09.037 --> 00:51:12.681
...которая позволяет определить ближайший
пиксель исходного изображения без

00:51:12.881 --> 00:51:14.442
использования интерполяции.

00:51:14.963 --> 00:51:20.849
Соответственно, здесь показывается CU
отжи,

00:51:21.170 --> 00:51:23.733
COLT, то есть старый, новый.

00:51:24.413 --> 00:51:26.175
Так, ну, соответственно, формулы...

00:51:27.173 --> 00:51:28.414
Непосредственно видны.

00:51:28.614 --> 00:51:34.180
Пример определяет размер изображения по
горизонтали, измеряемый в пикселе.

00:51:34.940 --> 00:51:38.504
Параметр S большой определяет размер по
вертикали.

00:51:38.784 --> 00:51:42.628
Параметры EJ определяют, соответственно,
строку или столбец матрицы изображения

00:51:42.788 --> 00:51:46.031
измеряются в пределах высоты и ширины
изображения, соответственно.

00:51:49.779 --> 00:51:51.137
Преобразование поворота.

00:51:52.096 --> 00:51:56.371
Преобразование поворота, так же как и при
рассмотренных плоских геометрических

00:51:56.411 --> 00:51:59.807
объектах, позволяет поворачивать исходное
изображение на заданный угол.

00:52:00.087 --> 00:52:02.484
Поворот осуществляется вокруг центра
изображения.

00:52:02.564 --> 00:52:05.720
При этом возможно два варианта поворота:
область изображения.

00:52:06.559 --> 00:52:12.399
Вышедшие за его границы при вороте при
повороте отсекаются, а незаполненные части

00:52:12.519 --> 00:52:14.519
заполняются каким-либо цветом.

00:52:15.479 --> 00:52:19.559
Рассчитывается новый размер изображения на
основе угла поворота таким образом, чтобы

00:52:19.759 --> 00:52:22.679
повёрнутое изображение целиком поместилось
в новые размеры.

00:52:23.208 --> 00:52:26.528
Незаполненные части изображения также
заполняются каким-либо цветом.

00:52:26.608 --> 00:52:31.167
В любом случае, для расчёта преобразования
поворота может быть использована следующая

00:52:31.247 --> 00:52:34.806
формула. Так, ну вот показано на слайде.

00:52:35.686 --> 00:52:38.765
Значит, есть у нас Volte, старое значение.

00:52:40.147 --> 00:52:42.628
Есть у нас новая C.

00:52:43.869 --> 00:52:48.311
Значит, в этой формуле параметр Ц
определяет цвет, которым заполняются

00:52:48.551 --> 00:52:50.672
пустые участки изображения.

00:52:53.634 --> 00:52:56.355
Параметр F определяет угол поворота.

00:52:59.507 --> 00:53:01.187
По часовой стрелке в радианах.

00:53:01.307 --> 00:53:04.867
Приведённая формула округляет
преобразованные координаты, однако можно

00:53:05.067 --> 00:53:09.307
использовать и блинейную интерполяцию,
когда цвет пикселя вычисляется как

00:53:09.427 --> 00:53:12.587
взвешенная сумма цветов четырёх соседних
пикселей.

00:53:15.427 --> 00:53:16.747
Цифровые фильтры изображения.

00:53:17.175 --> 00:53:20.815
Цифровые фильтры позволяют накладывать на
изображение различные эффекты.

00:53:20.895 --> 00:53:25.614
Например, размытие, резкость, деформацию,
шум и так далее.

00:53:25.774 --> 00:53:29.094
Цифровой фильтр представляет собой
алгоритм обработки изображения.

00:53:29.214 --> 00:53:33.214
Большая группа цифровых фильтров имеет
один и тот же алгоритм, но эффект

00:53:33.334 --> 00:53:33.894
накладывания

00:53:35.649 --> 00:53:39.090
Фильтром на изображение зависит от
коэффициентов, используемых в алгоритме.

00:53:39.130 --> 00:53:42.652
Фильтрация изображения является одной из
самых фундаментальных операций

00:53:42.732 --> 00:53:47.894
компьютерного зрения распознавания образов
и обработки изображений.

00:53:50.055 --> 00:53:52.096
Фактически, в той или иной фильтрации

00:53:54.643 --> 00:53:59.076
Начинается работа многих алгоритмов
обработки изображений.

00:54:01.033 --> 00:54:04.747
Линейные фильтры. Линейные фильтры
представляют собой семейство фильтров,

00:54:04.787 --> 00:54:06.944
имеющих очень простые математические
описания.

00:54:07.530 --> 00:54:10.611
Вместе с тем они позволяют добиться самых
разнообразных эффектов.

00:54:10.691 --> 00:54:14.893
Будем считать, что задано исходное
полутоновое изображение A и обозначим

00:54:15.093 --> 00:54:18.375
интенсивность его пикселей,
соответственно, как A от x ygrek.

00:54:18.655 --> 00:54:23.177
Линейный фильтр определяется вещественной
функцией F, заданной в Растре.

00:54:24.573 --> 00:54:26.931
Данная функция называется ядром фильтра.

00:54:27.011 --> 00:54:30.849
А сама фильтрация производится при помощи
операции дискретной свёртки.

00:54:31.169 --> 00:54:33.407
То есть, соответственно, взвешенного
суммирования.

00:54:33.727 --> 00:54:40.683
Как вот B от X-грек, как двойная сумма Fi
T умножить на A X + E-грек плюс J.

00:54:41.404 --> 00:54:43.565
Результатом служит изображение Б.

00:54:44.006 --> 00:54:47.247
В приведённой формуле не определены
пределы суммирования.

00:54:47.327 --> 00:54:53.531
Обычно ядро фильтра-фильтра отлично от
нуля, только в некоторой окрестности N.0.

00:54:53.691 --> 00:54:58.773
За пределами этой окрестности F — или в
точности равно нулю, или очень близко к

00:54:58.853 --> 00:54:59.093
нему.

00:54:59.494 --> 00:55:00.976
Так как можно ими пренебречь.

00:55:01.016 --> 00:55:04.981
Поэтому суммирование производится по всем
ИЖ, принадлежащим N большое.

00:55:05.342 --> 00:55:10.709
И значение каждого пикселя B от x
определяется пикселями изображения A,

00:55:10.829 --> 00:55:12.030
который лежит в окне N.

00:55:12.650 --> 00:55:14.969
То есть централизованным в точке X-грек.

00:55:15.048 --> 00:55:17.287
Обозначим это множество как N от x-грек.

00:55:17.367 --> 00:55:21.164
Ядро фильтра, заданное на прямоугольной
окрестности N, можно рассматривать как

00:55:21.324 --> 00:55:26.280
матрица M на N, M малое на N малое, где
длины сторон являются

00:55:27.517 --> 00:55:33.113
Нечётными числами. При задании ядра
матрицы M, соответственно, Кл, её следует

00:55:33.273 --> 00:55:39.509
центрировать, соответственно, как F от ежи
равно M

00:55:40.788 --> 00:55:42.507
с соответствующими индексами.

00:55:44.989 --> 00:55:48.905
Также нуждается в дополнительном пояснении
ситуации, когда Pixel X Y находится в

00:55:48.945 --> 00:55:50.464
окрестности краёв изображения.

00:55:50.584 --> 00:55:55.060
В этом случае, соответственно, A от X + S
E geк + S может соответствовать пикселю A,

00:55:55.060 --> 00:55:57.937
лежащему за границами изображения.

00:55:58.057 --> 00:56:00.894
Данную проблему можно разрешить
несколькими способами.

00:56:01.662 --> 00:56:04.543
Не проводить фильтрацию для таких
пикселей.

00:56:04.743 --> 00:56:09.385
Соответственно, обрезав изображение Б по
краям или закрасив их, к примеру, чёрным

00:56:09.465 --> 00:56:15.108
цветом, не включить соответствующий
пиксель суммирование, распределив его вес,

00:56:15.188 --> 00:56:18.389
соответственно, фотожи равномерно среди
других пикселей окрестностей.

00:56:19.475 --> 00:56:23.471
Так, соответственно, сноска, свёртка,
математическая операция двух функций F и

00:56:23.671 --> 00:56:28.746
Ж, порождающая третью функцию, которая
обычно может рассматриваться как

00:56:29.345 --> 00:56:32.342
модифицированная версия одной из
первоначальных.

00:56:35.100 --> 00:56:38.376
Доопределить значение пикселей за
границами изображения при помощи

00:56:38.496 --> 00:56:39.375
интерполяции.

00:56:39.995 --> 00:56:43.275
Экстраполяции, прошу прощения, и
доопределить значение пикселей за

00:56:43.355 --> 00:56:46.034
границами изображения при помощи
зеркального отражения.

00:56:46.354 --> 00:56:50.433
Выбор конкретного способа нужно
производить с учётом конкретного фильтра,

00:56:50.513 --> 00:56:52.273
в особенности конкретного приложения.

00:56:52.353 --> 00:56:55.512
Разработав общее определение линейных
фильтров, перейдём

00:56:56.556 --> 00:56:59.830
Соответственно, к примерам сглаживающие
фильтры.

00:57:00.309 --> 00:57:04.182
Результатом применения сглаживающего
фильтра является размытое изображение.

00:57:05.628 --> 00:57:07.626
Устранение резких цветных переходов.

00:57:07.706 --> 00:57:11.342
Простейший прямоугольный сглаживающий
фильтр радиуса Р задаётся с помощью

00:57:11.422 --> 00:57:16.696
матрицы размером 2R +1 на 2 R + 1, все
значения которые равны, соответственно,

00:57:16.736 --> 00:57:19.573
единице делить на 2 R + 1 в квадрате.

00:57:19.852 --> 00:57:23.369
А сумма по всем элементам матрицы равна
таким образом единице.

00:57:24.029 --> 00:57:28.472
При фильтрации с данным ядром значение
пикселя заменяется на усреднённое значение

00:57:28.552 --> 00:57:32.995
пикселя в квадрате со стороной 2 вокруг
него.

00:57:33.075 --> 00:57:36.317
То есть пример фильтрации при помощи
прямоугольного фильтра показан на данном

00:57:36.397 --> 00:57:40.800
рисунке. Так, вот ваш фильтр даёт такой
эффект.

00:57:41.775 --> 00:57:46.657
Значит, в этом случае на исходное
изображение рисунок 419А наложен

00:57:46.977 --> 00:57:49.298
прямоугольный фильтр 3 на 3 пикселя.

00:57:49.538 --> 00:57:52.579
Ядро фильтра в этом случае выглядит
следующим образом.

00:57:55.420 --> 00:57:56.821
Так, ядро фильтра M.

00:57:57.245 --> 00:58:00.960
Одна девятая. Результат фильтрации
приведён на изображении справа.

00:58:01.160 --> 00:58:02.798
Так, ну на данном рисунке был.

00:58:02.838 --> 00:58:08.711
Отметим, что сумма всех элементов ядра
фильтра даёт в результате единицу.

00:58:09.990 --> 00:58:13.266
Потому можно сказать, что при
использовании такого фильтра в целом

00:58:13.698 --> 00:58:15.298
Яркость всего изображения меняется.

00:58:15.338 --> 00:58:19.540
Однако вследствие усреднения значений
цветов пикселей, контрастность изображения

00:58:19.660 --> 00:58:22.581
уменьшается, что видно, соответственно, на
рисунке 4:19.

00:58:22.741 --> 00:58:26.503
Как видим, из приведённого примера,
сглаживающие фильтры могут применяться для

00:58:27.183 --> 00:58:30.784
устранения лестничного эффекта, а также
для шумоподавления.

00:58:43.588 --> 00:58:45.347
Контрастно повышающие фильтры.

00:58:45.707 --> 00:58:49.785
Если сглаживающий фильтр снижает локальную
контрастность изображения, размывая его,

00:58:49.865 --> 00:58:53.103
то контрастно повышающий фильтры
производят обратный эффект.

00:58:53.303 --> 00:58:58.661
Ядро контрастно повышающего фильтра имеет
значение больше единицы в точке 0,0 при

00:58:58.860 --> 00:59:01.019
общей сумме всех значений, равной единице.

00:59:01.219 --> 00:59:01.619
Например,

00:59:02.825 --> 00:59:06.741
Контрастно повышаемым фильтром является
фильтр с ядром, задаваемым Матрицей,

00:59:06.861 --> 00:59:09.618
соответственно, M либо Матрицей M2.

00:59:10.457 --> 00:59:13.174
Так, видите, с отрицательными
коэффициентами.

00:59:13.654 --> 00:59:17.929
Эффект повышения контраста достигается за
счёт того, что фильтр подчёркивает

00:59:19.145 --> 00:59:24.026
Разницу между интенсивностями соседних
пикселей, уделяя, удаляя эти интенсивности

00:59:24.266 --> 00:59:29.267
друг от друга. Этот эффект будет тем
сильнее, чем больше значение центрального

00:59:29.868 --> 00:59:33.188
члена ядра. Результат работы фильтра на
исходном изображении.

00:59:33.228 --> 00:59:34.628
Вот рисунок 4.20.

00:59:35.683 --> 00:59:42.247
Видите, там веточки для, соответственно,
матрицы M1 представлены на

00:59:42.367 --> 00:59:46.610
рисунке 420Б, на рисунке 42V.

00:59:57.635 --> 01:00:02.117
Характерным артефактом линейно
контрастирующей функции фильтрации

01:00:02.277 --> 01:00:06.518
являются заметные светлые и менее заметные
тёмные ореолы вокруг границ.

01:00:10.600 --> 01:00:14.561
Разностные фильтры. Разностные фильтры
часто используются для нахождения границ в

01:00:14.641 --> 01:00:16.802
изображениях, при этом используют
дифференциальный

01:00:18.478 --> 01:00:22.832
Оператор, вычисляющий приближённое
значение градиент яркости изображения.

01:00:22.951 --> 01:00:26.706
Результатом применения такого оператора в
каждой точке изображения является либо

01:00:26.786 --> 01:00:31.420
вектор градиента яркости в этой точке,
либо его норма.

01:00:32.019 --> 01:00:32.858
Так, сноска.

01:00:33.528 --> 01:00:37.245
Градиент — вектор, показывающий
направление наискорейшего возрастания

01:00:37.445 --> 01:00:41.481
некоторой величины, значение которой
меняется от одной точки пространства к

01:00:41.561 --> 01:00:48.474
другой. Результат показывает, насколько
резко или плавно

01:00:48.634 --> 01:00:50.792
меняется яркость изображения в каждой
точке.

01:00:50.872 --> 01:00:53.589
А значит, вероятность нахождения точки на
грани, а также

01:00:54.318 --> 01:00:58.674
Ориентацию границы. На практике вычисление
величины изменения яркости вероятности

01:00:59.074 --> 01:01:05.947
принадлежности границе надёжнее и проще в
интерпретации, чем расчёт направления.

01:01:06.266 --> 01:01:12.380
Если на изображении будет присутствовать
однотонная область или область с плавными

01:01:12.460 --> 01:01:13.299
переходами цветов

01:01:14.231 --> 01:01:18.427
То в результирующем изображении подобные
участки будут закрашены четырьмя чёрным

01:01:18.547 --> 01:01:24.862
цветом. Там, где имеются перепады, то есть
резкие переходы края, крутизна изменения

01:01:25.021 --> 01:01:29.098
яркости высока и в конечном изображении, в
таких местах появляются яркие

01:01:30.271 --> 01:01:37.116
Светлой линии. Градиент функции двух
переменных для каждой точки изображения,

01:01:37.196 --> 01:01:40.999
которая является функцией яркости, — это
двумерный вектор, компонентами которого

01:01:41.119 --> 01:01:44.562
являются производные яркости изображения
по горизонтали и по вертикали.

01:01:44.642 --> 01:01:47.845
В каждой точке изображения градиентный
вектор ориентирован на направление

01:01:48.045 --> 01:01:51.928
наибольшего увеличения яркости, а его
длина соответствует величине измерения.

01:01:52.246 --> 01:01:57.643
изменение яркости. Одним из способов
нахождения границ на изображении является

01:01:58.002 --> 01:02:03.999
реализация фильтра или оператора собеля
sobel, который позволяет найти неточное

01:02:04.079 --> 01:02:06.117
приближение градиента яркости изображения.

01:02:06.237 --> 01:02:08.396
Строго говоря, оператор использует ядра 3
на 3

01:02:08.933 --> 01:02:12.576
...с которыми сворачивает исходное
изображение для вычисления приближённых

01:02:12.696 --> 01:02:16.139
значений производных по горизонтали и по
вертикали.

01:02:16.499 --> 01:02:19.822
Формально в оператор Собеля определяется
следующим образом.

01:02:19.942 --> 01:02:21.943
Пусть A — исходное изображение.

01:02:22.303 --> 01:02:24.905
G X, G Y — два изображения, где точка.

01:02:25.066 --> 01:02:26.347
Каждая точка содержит

01:02:27.627 --> 01:02:29.865
Приближённые производные по X по игрек.

01:02:29.905 --> 01:02:31.943
Они вычисляются следующим образом.

01:02:33.022 --> 01:02:37.578
Соответственно, вычисляется же игрек,
вычисляется же икс.

01:02:37.858 --> 01:02:42.294
Где, соответственно, звёздочка обозначает
двухмерную операцию свёртки, операцию

01:02:42.374 --> 01:02:44.253
линейной фильтрации, рассмотренную ранее.

01:02:44.704 --> 01:02:49.028
Координата X здесь возрастает направо, а
егрек вниз.

01:02:49.268 --> 01:02:53.391
В каждой точке изображения приближённое
значение величины градианта можно

01:02:53.552 --> 01:02:56.714
вычислить, используя полученное
приближённое значение производных.

01:02:56.834 --> 01:02:59.677
То есть Ж равняется корень квадратный
квадрате X.

01:03:02.158 --> 01:03:07.159
Игрек, используя эту функцию, мы также
можем вычислить и направление градиента,

01:03:07.279 --> 01:03:12.279
как, соответственно, величины
произведения, то есть

01:03:15.480 --> 01:03:16.120
частного.

01:03:16.880 --> 01:03:18.760
Дробь J делить на Ж.

01:03:19.400 --> 01:03:25.121
Где, к примеру, угол p равен нулю для
вертикальной границы, которая тёмная

01:03:25.241 --> 01:03:30.281
сторона слева, операцию свёртки,
соответственно, можно использовать

01:03:30.401 --> 01:03:33.761
отдельно для нахождения вертикальных и
горизонтальных границ.

01:03:33.841 --> 01:03:37.521
На рисунке 4.2.1 приведён пример
применения свёртки Ж.

01:03:38.097 --> 01:03:42.457
421 B и Жрек 421B к исходному изображению.

01:03:42.537 --> 01:03:46.898
В случае совместного использования двух
операций можем получить результат,

01:03:47.018 --> 01:03:48.339
представленный на рисунке 4.

01:03:51.619 --> 01:03:53.260
Так, в отличие от сглаживающих

01:03:54.607 --> 01:03:59.172
Контраст контрастно повышающих фильтров,
не меняющих среднюю интенсивность

01:03:59.332 --> 01:04:01.895
изображения. Сумма элементов ядра равна
единице.

01:04:01.975 --> 01:04:05.178
В результате применения разностных
операторов получается, как правило,

01:04:05.258 --> 01:04:10.624
изображение со средним значением пикселя
близким к нулю, то есть сумма элементов

01:04:10.824 --> 01:04:11.665
ядра равна нулю.

01:04:12.026 --> 01:04:16.183
При этом пиксели со значением, близким к
нулю можно отображать белым цветом.

01:04:17.063 --> 01:04:20.900
Пиксели, значение яркости которых
получается больше некого порога, можно

01:04:21.060 --> 01:04:22.339
изображать чёрным цветом.

01:04:22.419 --> 01:04:26.777
Заметим, что выделение всех пикселей,
значение которых по модулю больше

01:04:27.176 --> 01:04:29.975
некоторого порога, является некоторой
нелинейной.

01:04:30.949 --> 01:04:33.786
Локальную операцию, которую можно
рассматривать как простейший пример

01:04:33.945 --> 01:04:35.344
нелинейной фильтрации.

01:04:35.703 --> 01:04:38.700
Так, ну вот пример использования оператора
Собеля.

01:04:42.295 --> 01:04:47.529
Кроме фильтра Собеля, можно использовать
оператор Пьюта.

01:04:47.706 --> 01:04:51.987
...или оператор Шар.

01:04:52.307 --> 01:04:56.228
Подобный алгоритм оператора Собеля, за
исключением использования других матриц.

01:04:56.308 --> 01:04:59.469
У алгоритмов нахождения границ существует
несколько недостатков.

01:04:59.549 --> 01:05:02.189
Главный из них — неопределённость в выборе
величины порога.

01:05:02.927 --> 01:05:06.566
Для разных частей изображения приемлемый
результат обычно получается при

01:05:06.686 --> 01:05:08.526
существенно разных пороговых значениях.

01:05:08.646 --> 01:05:12.285
Кроме того, разостные фильтры очень
чувствительны к шумам изображения.

01:05:14.045 --> 01:05:15.364
Нелинейные фильтры.

01:05:15.644 --> 01:05:19.244
Основное отличие нелинейного фильтра от
линейного заключается в том, что выход

01:05:19.403 --> 01:05:22.163
нелинейного фильтра формируется нелинейным
образом.

01:05:22.867 --> 01:05:24.508
А данных исходного изображения.

01:05:24.588 --> 01:05:29.672
Соответственно, линейные фильтры, несмотря
на разнообразные проводимые ими эффектов,

01:05:29.752 --> 01:05:36.556
не позволяют проделывать некоторые самые
естественные операции.

01:05:36.716 --> 01:05:39.718
Хорошим примером служит пороговая
фильтрация упомянутая выше.

01:05:39.798 --> 01:05:43.080
Результатом пороговой фильтрации служит
бинарное изображение, определяемое

01:05:43.200 --> 01:05:43.881
следующим образом.

01:05:44.613 --> 01:05:50.540
То есть B от x yк равно единице, если A от
X-грек больше некоторого гамма, но иначе.

01:05:50.700 --> 01:05:52.862
Величина гамма является пороговой
фильтрации.

01:05:52.942 --> 01:05:57.748
Пороговая фильтрация может быть
использована как предварительный этап

01:05:57.828 --> 01:06:00.311
обработки изображения перед его
векторизацией.

01:06:00.865 --> 01:06:04.748
Более сложным фильтром, нелинейным
фильтром, использующим окрестность

01:06:04.908 --> 01:06:07.590
пикселей, является медиана или медианный
фильтр.

01:06:07.950 --> 01:06:13.033
Здесь так же, как и в линейных фильтрах по
пикселям, предлагается окно.

01:06:13.153 --> 01:06:16.795
Передвигается окно, которое охватывает
пиксели, участвующие в формировании

01:06:16.875 --> 01:06:18.036
итоговой интенсивности.

01:06:18.763 --> 01:06:24.523
Значения внутри этого окна воспринимаются
как одномерный массив, который сортируется

01:06:24.603 --> 01:06:28.323
в порядке возрастания. Значение,
находящееся в середине отсортированного

01:06:28.443 --> 01:06:30.963
массива, поступает на выход фильтра.

01:06:31.043 --> 01:06:34.243
Таким образом, идианная фильтрация
способна эффективно справиться с

01:06:34.323 --> 01:06:38.683
импульсами, с импульсными помехами, то
есть когда помехи независимо воздействуют

01:06:38.723 --> 01:06:39.883
на отдельные пиксели.

01:06:40.365 --> 01:06:44.844
Примером таких помех служат,
соответственно, биты и горячие пиксели при

01:06:45.004 --> 01:06:46.204
цифровой съёмке.

01:06:46.404 --> 01:06:48.763
Снеговой шум и тому подобное.

01:06:48.843 --> 01:06:55.001
Например, на рисунке 4.23А — преимущество
медианной фильтрации, соответственно.

01:06:56.357 --> 01:07:02.402
Рисунок 4.3B перед линейной сглаживающей
фильтрацией, то есть рисунок 4.23B

01:07:02.682 --> 01:07:07.286
заключается в том, что интенсивность
пикселя шума будет заметно заменена

01:07:07.446 --> 01:07:12.410
интенсивностью фоновых фоновых пикселей, а
не будет перераспределена на соседние

01:07:12.570 --> 01:07:15.012
пиксели, как при использовании
сглаживающего фильтра.

01:07:19.570 --> 01:07:25.924
Так, ну вот иллюстрация, удаление шумов,
фильтрами, размытие и медианным фильтром.

01:07:26.923 --> 01:07:30.320
Так, ну захватим немножко следующий
раздел: преобразование растровых

01:07:30.480 --> 01:07:34.756
изображений. Векторизация с помощью
волнового алгоритма.

01:07:34.796 --> 01:07:38.472
Векторизация — преобразование изображений
из растрового представления в векторное.

01:07:38.552 --> 01:07:39.591
Векторизация — процесс

01:07:40.326 --> 01:07:44.043
Обратной растерация. Векторизация
проводится, как правило, в случае, если

01:07:44.242 --> 01:07:47.879
результат векторизации подлежит дальнейшей
обработке исключительно в программах

01:07:48.038 --> 01:07:51.395
векторной графики с целью повышения
качества изображения для создания

01:07:51.475 --> 01:07:55.550
изображения, пригодного для
масштабирования, без потери качества.

01:07:56.459 --> 01:08:00.140
Если дальнейшая обработка изображений
будет осуществляться на специфическом

01:08:00.220 --> 01:08:03.622
оборудовании, то есть плоттеры, станки с
ЧПО, различают следующие виды

01:08:03.822 --> 01:08:08.143
векторизации. Соответственно,
автоматическая векторизация, то есть

01:08:08.263 --> 01:08:12.064
перевод классовых изображений, чертежей,
сканированных копий, фотографий в

01:08:12.144 --> 01:08:14.665
электронный вид с помощью специального
программного обеспечения.

01:08:15.325 --> 01:08:19.206
Ручная векторизация, то есть перевод
бумажных чертежей в электронный вид,

01:08:19.286 --> 01:08:22.727
перечерчивание каждого документа вручную в
системах автоматизированного

01:08:22.847 --> 01:08:26.808
проектирования. Соответственно, одним из
алгоритмов для нахождения векторного

01:08:26.928 --> 01:08:30.449
представления из кастрового изображения,
то есть от сканируемого чертежа, является

01:08:30.770 --> 01:08:31.490
волновой алгоритм.

01:08:32.357 --> 01:08:35.961
На вход алгоритм поступает бинарное
растровое изображение, которое может быть

01:08:36.121 --> 01:08:38.804
получено из исходного путём пороговой
фильтрации.

01:08:39.325 --> 01:08:44.290
Под бинарным растровым изображением
понимается двухмерная матрица из четырёх:

01:08:44.370 --> 01:08:47.975
из чёрных и белых пикселей, в которых
объект задаётся заданными

01:08:49.660 --> 01:08:52.379
Задаётся чёрными пикселями, а фон — белыми
пикселями.

01:08:52.459 --> 01:08:55.418
Соответственно, на растовом изображении
могут присутствовать отрезки

01:09:01.136 --> 01:09:04.335
Соединения и пересечение отрезков, то есть
включение друг

01:09:05.775 --> 01:09:08.772
В изображении, в данном пособии не
рассматривается.

01:09:10.570 --> 01:09:12.528
То есть, как пример объекта

01:09:12.947 --> 01:09:16.710
Под изображением отрезка на растре будем
понимать такое множество чёрных точек

01:09:16.790 --> 01:09:20.913
растра, что можно провести отрезок прямой
B такой, что по обе стороны от этого

01:09:21.113 --> 01:09:23.635
отрезка будет лежать примерно равное
количество точек.

01:09:23.795 --> 01:09:27.197
Расстояние от отрезка до ближайшего
крайних точек изображения будет лежаться

01:09:27.317 --> 01:09:27.758
не более чем

01:09:28.810 --> 01:09:30.529
Наперёд заданную величину.

01:09:31.049 --> 01:09:36.688
Соответственно, при соседнем под
соединением отрезков будем понимать два

01:09:36.928 --> 01:09:43.567
отрезка такие, что, одна из вершин одного
отрезка лежит на другом отрезке, в этом

01:09:43.607 --> 01:09:46.247
случае они будут иметь одну общую точку.

01:09:46.327 --> 01:09:47.407
И один из отрезков будет

01:09:48.385 --> 01:09:50.143
Разделён, соответственно, на два.

01:09:51.581 --> 01:09:55.696
Пересекающие отрезки изображения будем
представлять в виде отрезков меньшей

01:09:55.736 --> 01:09:58.014
длины, имеющих одну общую вершину.

01:09:58.134 --> 01:09:59.892
То есть рисунок 51Б.

01:10:00.291 --> 01:10:03.408
Задачей алгоритма является построение
нагруженного графа.

01:10:03.589 --> 01:10:08.793
...которую нагрузка вершин, пара координат
X-грек к соответствующим узловым точкам

01:10:08.873 --> 01:10:12.915
изображения. За узловые точки будем
принимать точки соединения изображения

01:10:13.075 --> 01:10:14.556
линией, изображения.

01:10:14.596 --> 01:10:17.358
Толщиной линии будем считать её ширину в
пикселях.

01:10:17.838 --> 01:10:19.720
Алгоритм реализуется в два этапа.

01:10:20.818 --> 01:10:24.855
Соответственно, построение скелета
изображения с помощью сферической волны,

01:10:24.935 --> 01:10:26.734
оптимизация полученного скелета.

01:10:27.653 --> 01:10:31.930
До построения скелета с целью улучшения
качества изображения возможно применение

01:10:32.050 --> 01:10:35.247
различных фильтров. В частности,
желательно избавить изображение от

01:10:35.327 --> 01:10:36.247
случайного шума.

01:10:38.750 --> 01:10:40.630
Первый этап — построение скелета
изображения.

01:10:40.710 --> 01:10:44.231
Для построения скелета изображения на
объекте-отрезке выбирается начальная

01:10:44.671 --> 01:10:51.431
затравочная точка, от которой начинается
распространяться волна путём добавления

01:10:51.511 --> 01:10:54.791
пикселей. Сначала цитравочной точки, потом

01:10:55.362 --> 01:11:00.287
К уже добавленным волна генерируется по
определённым знакам, законам использующих

01:11:00.727 --> 01:11:03.851
четырёх или восьмисвязность пикселей.

01:11:03.931 --> 01:11:07.415
При четырёхсвязном растре распределение
идёт в форме ромба.

01:11:07.775 --> 01:11:11.699
Соответственно, при восьмисвязном в виде
квадрата, если

01:11:12.663 --> 01:11:17.976
Если попеременно использовать четырёх и
восьми связанное распространение, то форма

01:11:18.975 --> 01:11:21.092
волны будет близка к кругу.

01:11:21.492 --> 01:11:26.406
Рисунок B. При распространении сферической
сферической волны на отрезке прямой

01:11:26.566 --> 01:11:27.844
наблюдаются следующие эффекты.

01:11:28.875 --> 01:11:30.633
Не более чем 2 Н-шагов.

01:11:30.913 --> 01:11:35.827
Распространение волны приобретает
устойчивый характер вне зависимости от

01:11:35.947 --> 01:11:38.344
начальной точки распространения волны.

01:11:41.381 --> 01:11:45.057
Соответственно, N — ширина линии в
пикселях.

01:11:47.387 --> 01:11:50.504
Форма распространения волн на растровом
изображении.

01:11:51.344 --> 01:11:55.260
Так, далее рисунок 5.3 — распространение
волн на отрезке.

01:12:00.136 --> 01:12:04.212
При отличии формы отрезка от прямой,
распространение волны также предсказуемо,

01:12:04.252 --> 01:12:08.688
причём необходимо отметить хорошие хорошие
огибающие свойства сферической волны.

01:12:09.690 --> 01:12:13.452
Узловые точки определяются на каждой
генерации волны или через определённое

01:12:13.532 --> 01:12:14.733
количество генераций волн.

01:12:14.813 --> 01:12:19.055
В качестве узловой точки берётся центр
отрезка, образуемого крайними точками

01:12:19.215 --> 01:12:20.696
необходимой генерации волны.

01:12:21.096 --> 01:12:25.418
При достижении волной места соединения
двух или более отрезков наблюдается

01:12:25.579 --> 01:12:27.740
разделение волны на несколько дочерних
волн.

01:12:28.297 --> 01:12:31.499
...сохраняющих поведение материнской
волны.

01:12:31.699 --> 01:12:32.980
То есть рисунок 5—4.

01:12:33.140 --> 01:12:36.702
Момент разделения довольно просто
отслеживается путём анализа ширины в

01:12:36.782 --> 01:12:41.265
кавычках волн, то есть количество точек,
образующих очередную генерацию волны.

01:12:42.946 --> 01:12:47.389
Перед разделением наблюдения, увеличение
ширины волны, с дальнейшим разделение

01:12:47.509 --> 01:12:49.070
волны на две, иногда более...

01:12:49.897 --> 01:12:55.216
...дочерней волны. То есть рисунок
распространения волны на соседний и

01:12:55.336 --> 01:13:00.575
поперечный пересечение отрезков на
соединении и пересечении отрезков.

01:13:00.735 --> 01:13:06.054
Выявление мест увеличения ширины волны и
разделения волны на дочерние позволяет

01:13:06.174 --> 01:13:09.094
установить точку предполагаемого
соединения двух отрезков.

01:13:09.636 --> 01:13:14.353
Определение увеличения ширины волны
производится путём сравнения ширины

01:13:14.473 --> 01:13:20.749
очередной генерации волны и её среднего
значения за Nдущих, соответственно,

01:13:20.869 --> 01:13:22.748
генераций, заданных заранее.

01:13:22.828 --> 01:13:25.107
Причём мы получаем две крайние точки: A и
B

01:13:25.975 --> 01:13:27.256
Эктрассируемого отрезка.

01:13:27.376 --> 01:13:33.378
После разделения волны на две половины мы
получаем ещё две пары точек: CD, EF.

01:13:33.498 --> 01:13:34.898
Ну, вот как показано примерно на

01:13:34.938 --> 01:13:41.860
рисунке,

01:13:41.900 --> 01:13:46.422
ну и с помощью анализа этих отрезков ABC
D, можно оценить положение точки.

01:13:47.115 --> 01:13:50.953
Соединение отрезков. Первоначально
установим место соединения как центр массы

01:13:51.073 --> 01:13:52.353
этого многоугольника.

01:13:53.472 --> 01:13:57.950
Так, следующий вопрос. Вторая, второй этап
оптимизации скелета изображения.

01:13:58.430 --> 01:14:01.069
Полученный скелет изображения не является
оптимальным.

01:14:01.348 --> 01:14:02.468
Это связано прежде всего с

01:14:03.153 --> 01:14:06.433
С тем, что мы имеем дело с растовым
изображением.

01:14:06.633 --> 01:14:11.234
Значит, изображение имеет искажение тем
больше, тем меньше разрешение изображения,

01:14:11.314 --> 01:14:13.634
вот как на рисунке 5,6.

01:14:16.234 --> 01:14:18.515
Влияние разрешения на скелет изображения.

01:14:18.595 --> 01:14:20.035
Для уменьшения влияния искажений

01:14:20.568 --> 01:14:24.132
На получаемый скелет необходимо произвести
оптимизацию скелета, полученного

01:14:24.212 --> 01:14:29.177
отслеживанием пути сферической волны по
изображению объекта.

01:14:29.217 --> 01:14:32.621
В получаемом скелете возможно
представление одного отрезка некоторой

01:14:32.701 --> 01:14:33.903
последовательности в рёбер.

01:14:34.063 --> 01:14:34.904
Избавиться от этого

01:14:36.048 --> 01:14:40.404
Можно анализом последовательности рёбер,
оценивая отклонение получившейся линии от

01:14:40.524 --> 01:14:43.881
прямой. При этом точки, образующие
последовательность рёбер, должны

01:14:44.081 --> 01:14:48.117
отклоняться от коррелирующей прямой не
больше, чем на заранее заданную величину

01:14:49.116 --> 01:14:50.714
соизмеримую ширину линии.

01:14:50.754 --> 01:14:54.351
В случае, если отклонение находится в
допустимых пределах, необходимость и

01:14:54.391 --> 01:14:56.909
заменить соответствующую
последовательность рёбер на одно.

01:14:58.473 --> 01:15:01.475
Соответственно, рисунок 5—7 — оптимизация
отрезков.

01:15:06.797 --> 01:15:10.959
Кроме оптимизации отрезков приводится
оптимизация точек соединения отрезков.

01:15:11.039 --> 01:15:14.440
Наиболее часто встречается искажение, это
как рисунок 5.

01:15:18.080 --> 01:15:21.604
Исправляется с помощью анализа,
приложенных к выделенной точке A,

01:15:21.724 --> 01:15:27.290
отрезков, Б1 C1, AB2, B2, Ц2, AB3.

01:15:28.754 --> 01:15:34.120
Б 33. Оно заключается в поиске такой пары
отрезков, соответственно, CS, B X, Bex C

01:15:34.600 --> 01:15:41.088
и, соответственно, Б1, Б2,2, Б 33, что,
соответственно, C, BS Bex

01:15:41.168 --> 01:15:42.290
Crex максимально.

01:15:43.344 --> 01:15:44.744
Коррелирует с прямой.

01:15:44.904 --> 01:15:50.224
То есть тогда необходимо точку A
переместить в точку пересечения прямых C и

01:15:50.344 --> 01:15:56.863
Creк, соответственно AC, затем удалить из
графа точки Б1, Б2 и Б3.

01:15:57.383 --> 01:15:59.903
Так, рисунок оптимизации точек соединения.

01:16:04.657 --> 01:16:11.261
Другим вариантом искажения является случай
соединения трёх отрезков в одной точке.

01:16:11.341 --> 01:16:14.783
В этом случае невозможно нахождение пары
отрезков, коррелируемых прямой.

01:16:14.943 --> 01:16:20.306
Точка A должна быть перемещена в центр
треугольника, образуемая прямыми прямыми

01:16:20.426 --> 01:16:26.150
B1C2, Б 33, а затем точки Б1, Б2, Б3
необходимо удалить из графа.

01:16:28.130 --> 01:16:31.012
Так, соответственно, оптимизация точек
соединения.

01:16:31.852 --> 01:16:33.053
Второй вариант.

01:16:35.534 --> 01:16:37.214
Сегментация изображения.

01:16:37.535 --> 01:16:42.417
Сегментация — это процесс разбиения
изображения на непересекающиеся области,

01:16:42.457 --> 01:16:46.258
сегменты, покрывающие все изображения
однородные по некоторому признаку.

01:16:46.929 --> 01:16:52.048
Все пиксели в сегменте похожи на некоторые
характеристики по некоторой характеристике

01:16:52.168 --> 01:16:53.408
или вычисленному свойству.

01:16:53.488 --> 01:16:56.047
Например, по цвету, яркости или текстуре.

01:16:56.127 --> 01:17:01.446
Соединения соседние сегменты значительно
отличаются по этой характеристике.

01:17:01.566 --> 01:17:06.245
Цель сегментации заключается в упрощении
или изменении представления изображения.

01:17:06.989 --> 01:17:09.191
Чтобы было его проще и легче
анализировать.

01:17:09.351 --> 01:17:14.034
Сегментация и выделение границ объектов
играют важную роль в системах

01:17:14.115 --> 01:17:19.038
компьютерного зрения и применяются для
задач распознавания сцен и выделения, то

01:17:19.078 --> 01:17:20.359
есть определения объектов.

01:17:20.679 --> 01:17:22.481
Методы сегментации можно разделить

01:17:23.166 --> 01:17:27.362
На два класса: автоматические, не
требующие взаимодействия с использованием

01:17:27.882 --> 01:17:31.399
и интерактивные, использующие
пользовательский ввод непосредственно в

01:17:31.479 --> 01:17:36.075
процессе работы. Например, к интерактивной
сегментации можно отнести алгоритм

01:17:36.115 --> 01:17:40.032
инструмента «Волшебная палочка»,
реализованный во многих растровых

01:17:40.072 --> 01:17:40.552
редакторах.

01:17:41.509 --> 01:17:45.027
Далее рассмотрим только автоматический
метод задачи автоматической сегментации

01:17:45.666 --> 01:17:47.585
делятся, соответственно, на два класса.

01:17:47.825 --> 01:17:53.341
Выделение областей изображения с
известными свойствами, разбиение

01:17:53.501 --> 01:17:53.981
изображения

01:17:55.245 --> 01:17:56.566
На однородные области.

01:17:56.686 --> 01:18:00.449
Между этими двумя поставленными
постановками задачи есть принципиальная

01:18:00.489 --> 01:18:03.891
разница. В первом случае задача
сегментации состоит в поиске определённых

01:18:03.971 --> 01:18:04.491
областей.

01:18:05.168 --> 01:18:07.207
О которых имеется априорная информация.

01:18:07.287 --> 01:18:11.884
Например, мы знаем цвет формы областей или
интересующие нас области представляют

01:18:11.964 --> 01:18:14.163
собой изображение известного объекта.

01:18:14.403 --> 01:18:18.321
Методы этой группы узкоспециализированные
для каждой конкретной задачи.

01:18:18.361 --> 01:18:21.320
Сегментация в такой постановке
используется в основном в задачах

01:18:21.439 --> 01:18:22.159
машинного зрения.

01:18:22.735 --> 01:18:25.337
Анализ сцен, поиск объектов на
изображение.

01:18:25.738 --> 01:18:29.781
Во втором случае никакая априорная
информация о свойствах областей не

01:18:29.861 --> 01:18:33.304
используется, зато на само разбвиение
изображения накладывается некоторое

01:18:33.385 --> 01:18:36.948
условие. Например, все области должны быть
однородны по цвету и текстуре.

01:18:37.467 --> 01:18:41.187
Так как при такой постановке задачи
сегментации не используется априорная

01:18:41.267 --> 01:18:45.308
информация об изображённых изображённых
объектах, то методы этой группы

01:18:45.828 --> 01:18:49.629
универсальны и применимы к любым
изображениям.

01:18:49.749 --> 01:18:54.070
В основном сегментация в этой постановке
применяется на начальном этапе.

01:18:54.245 --> 01:18:58.005
...при решении задачи. Для того чтобы
получить представление изображения в более

01:18:58.245 --> 01:19:05.045
удобном виде для дальнейшей работы Так, ну
конечно, арсенал алгоритми

01:19:05.325 --> 01:19:09.325
алгоритмов компьютерной графики довольно
большой.

01:19:10.166 --> 01:19:13.882
Имеются методы, основанные на
кластеризации и прочие методы.

01:19:14.442 --> 01:19:18.118
У нас, к сожалению, нет возможности всех,
конечно, их рассмотреть.

01:19:19.837 --> 01:19:23.793
Говоря об алгоритмах, нельзя не упомянуть
о наличии библиотеки OpenGL.

01:19:24.643 --> 01:19:28.563
То есть, вот в конце лекции библиотека
OpenGel на данный момент Windows.

01:19:28.603 --> 01:19:31.244
Существует два стандарта для работы с
трёхмерной графикой.

01:19:31.324 --> 01:19:36.045
Прежде всего OpenGL, являющийся стандартом
де-факто для всех графических рабочих

01:19:36.085 --> 01:19:39.925
станций и Direct 3D — стандарт,
предложенный фирмой Microsoft.

01:19:40.860 --> 01:19:43.181
Далее будет рассмотрено с нами только Apen
Gel.

01:19:43.301 --> 01:19:47.982
Существенным достоинством ОпенГэль
является его широкая распространённость.

01:19:48.062 --> 01:19:52.384
Он является стандартом в виде графических
рабочих станций: станции Sun, Silicon

01:19:52.624 --> 01:19:54.625
Graffics и так далее.

01:19:54.785 --> 01:19:58.946
В основу стандарта была положена
библиотека IRGL, разработанная фирмой

01:20:01.171 --> 01:20:07.096
Opengell представляет собой программный
интерфейс графическому оборудованию, хотя

01:20:07.216 --> 01:20:10.138
существует чисто программной реализации
Openjall.

01:20:10.218 --> 01:20:15.222
Интерфейс рассчитан, насчитывает около 120
различных команд, которые программисты

01:20:15.262 --> 01:20:17.624
используют для задания объектов и операций
над ними.

01:20:18.210 --> 01:20:22.889
необходимых для написания интерактивных
трёхмерных приложений, конечно, мы их

01:20:22.929 --> 01:20:25.368
подробно рассматривать не будем, но только
в общем.

01:20:25.448 --> 01:20:29.847
Опенжил был разработан как эффективный
аппаратно-независимый интерфейс, пригодный

01:20:30.007 --> 01:20:33.285
для реализации на различных аппаратных
платформах.

01:20:33.365 --> 01:20:37.164
Поэтому пенджил не включает в себя никаких
специализированных команд для работы с

01:20:37.204 --> 01:20:39.403
окнами или ввода информации от
пользователя.

01:20:39.939 --> 01:20:45.932
Опенжель позволяет создавать объекты из
геометрических примитивов: точки, линии,

01:20:47.010 --> 01:20:49.327
грани битого изображения.

01:20:49.487 --> 01:20:54.201
Второе, располагать объекты в трёхмерном
пространстве и выбирать способ и параметр

01:20:54.281 --> 01:20:55.080
проецирования.

01:20:55.538 --> 01:20:57.657
Третье — вычислять цвет всех объектов.

01:20:57.736 --> 01:21:03.173
Цвет может быть как явно задан, так и
вычисляться с учётом источников цвета,

01:21:03.293 --> 01:21:05.292
параметров освещения текстур.

01:21:05.492 --> 01:21:09.609
Переводить математическое описание
объектов и связанная с ними информация о

01:21:09.689 --> 01:21:11.128
цвете изображения на экране.

01:21:11.502 --> 01:21:15.222
При этом OpenG может осуществлять
дополнительные операции.

01:21:15.342 --> 01:21:18.782
Такие как удаление независимых фрагментов
изображения.

01:21:18.982 --> 01:21:21.822
Команда Apengell реализована как модель
клиент-сервер.

01:21:21.902 --> 01:21:23.502
Приложение выступает в роли клиента

01:21:24.506 --> 01:21:28.628
Оно вырабатывает команды, а сервер
Opengell инициирует выполнение их.

01:21:28.708 --> 01:21:33.191
Сам сервер может находиться как на том же
компьютере, на котором находится клиент,

01:21:33.231 --> 01:21:39.674
так и на другом. Openga представляет собой
универсальную графическую библиотеку,

01:21:39.794 --> 01:21:42.195
которая может быть реализована в любой
оконной среде.

01:21:43.541 --> 01:21:47.297
Подставляется, соответственно, в составе
операционной системы Windows, начиная с

01:21:47.377 --> 01:21:52.772
версии MoSR2 в виде DLL-файлов
динамических библиотек, то есть OpenGL

01:21:52.972 --> 01:21:55.890
32DL, Glow 32L.

01:21:56.009 --> 01:21:59.087
Первая из этих библиотек и есть,
собственно, набор функций OpenGL.

01:21:59.166 --> 01:22:00.885
Вторая содержит дополнительный набор
функций

01:22:01.755 --> 01:22:07.961
упрощающих кодирование, но построенных и
выполненных с подключением Open GL-32,

01:22:08.001 --> 01:22:11.485
является надстройкой. То, что эти
библиотеки поставляются в состав

01:22:11.565 --> 01:22:15.488
операционной системы, значительно упрощает
распределение разработанных приложений.

01:22:15.769 --> 01:22:18.171
То, что OpenGL распространяется в виде

01:22:18.930 --> 01:22:22.127
Динамических библиотек упрощает доступ к
его функциям.

01:22:22.207 --> 01:22:28.363
Для работы OpenGel Windows используется
понятие контекстовоспроизведения, то есть

01:22:29.722 --> 01:22:34.159
рентинг-контекст, который связывает
OpenGel с оконной системой Windows.

01:22:34.279 --> 01:22:38.276
Если обычный контекст-устройства, то есть
device-контекст, содержит информацию,

01:22:38.316 --> 01:22:40.075
относящуюся к графическим компонентам

01:22:40.673 --> 01:22:45.511
Если, то, соответственно, контекст
воспроизведения содержит информацию,

01:22:45.551 --> 01:22:47.110
относящуюся к Openg.

01:22:47.350 --> 01:22:51.507
Таким образом, чтобы начать работать
непосредственно с компонентами Openj.

01:22:52.532 --> 01:22:56.092
Приложение должно создать как минимум один
контекст воспроизведения, сделать его

01:22:56.251 --> 01:22:59.931
текущим. Перед созданием контекста
воспроизведения необходимо установить

01:23:00.011 --> 01:23:03.970
формат пикселей. Для установления формата
пикселей используется функция Windows GT

01:23:04.170 --> 01:23:10.169
и, соответственно, чувсел-формат с
соответствующим набором параметров, как

01:23:10.289 --> 01:23:15.128
видите, выбирающий наиболее подходящий
формат, исходя из информации переданных в

01:23:15.168 --> 01:23:17.967
полях структуры. Вот этот самый
пиксель-формат.

01:23:20.101 --> 01:23:24.379
Дискриптор. После того, как найден
подходящий формат пикселей, следует

01:23:24.619 --> 01:23:29.376
установить его в контексте устройства при
помощи функции Bull, то есть логическая

01:23:29.496 --> 01:23:32.814
функция Sat Pixel Format с
соответствующими параметрами.

01:23:33.093 --> 01:23:37.571
Для работы с контекстным воспроизведения в
Windows существуют функции, соответственно

01:23:40.513 --> 01:23:47.361
VGLIT контекст и, соответственно, функции
тоже Buller VL и mack курент.

01:23:47.521 --> 01:23:52.487
Первый из них создаёт новое контекстное
воспроизведение, который подходит для

01:23:52.687 --> 01:23:54.850
рисования на устройстве с заданным
контекстом.

01:23:55.341 --> 01:23:58.859
Вторая функция устанавливает текущий
контекст воспроизведения.

01:24:00.259 --> 01:24:04.097
По окончании работы с OTL, созданный
контекст воспроизведения в бате,

01:24:04.137 --> 01:24:09.214
необходимо удалить. Для этого существуют
соответствующие функции-контекст.

01:24:09.374 --> 01:24:13.372
Текущий контекст воспроизведения можно
узнать при помощи функции, соответственно.

01:24:16.244 --> 01:24:19.885
При помощи open Gel можно создавать
анимации, при этом для изображения

01:24:19.965 --> 01:24:23.366
используется режим работы с двумя
буферами, когда содержимое в одном из них

01:24:23.446 --> 01:24:25.607
показывается, в другом осуществляется
построение.

01:24:25.967 --> 01:24:29.048
После окончания построения
специализированная команда меняет буферы

01:24:29.168 --> 01:24:32.048
местами, по аналогии, соответственно, с
двухстраничным режимом работы.

01:24:32.820 --> 01:24:36.336
Для использования двойной буферизации
необходимо установить флаг.

01:24:36.696 --> 01:24:42.849
Соответственно, PDouble буфер при задании
формата пикселей применить команду Swab

01:24:42.928 --> 01:24:44.567
Buffers, поменять буферы.

01:24:44.646 --> 01:24:46.245
То есть меняющие буферы местами.

01:24:46.285 --> 01:24:48.282
По умолчанию вывод происходит.

01:24:49.487 --> 01:24:50.885
В невидимый буфер.

01:24:52.043 --> 01:24:55.439
Так, ну вот, к сожалению, время нашей
лекции истекло.

01:24:55.838 --> 01:25:00.552
Общее введение в алгоритмы компьютерной
графики, я думаю, вы получили.

01:25:00.752 --> 01:25:01.590
Спасибо за внимание.

