Как составить алгоритм получения изображения

Первое здание возможно так:

алг рисовать_фигуру()

нач

опустить перо

сместиться на вектор (0, 1)

сместиться на вектор (2, 0)

сместиться на вектор (-1, 2)

сместиться на вектор (1, 0)

сместиться на вектор (-1, 2)

сместиться на вектор (-1, -2)

сместиться на вектор (-1, 0)

сместиться на вектор (-1, -2)

сместиться на вектор (-1, 0)

сместиться на вектор (0, -1)

сместиться на вектор (1, 0)

поднять перо

кон

алг переместиться_между_фигурами()

нач

поднять перо

сместиться на вектор (6, 0)

кон

нач

рисовать_фигуру()

переместиться_между_фигурами()

рисовать_фигуру()

переместиться_между_фигурами()

рисовать_фигуру()

переместиться_между_фигурами()

рисовать_фигуру()

кон

Практическая работа №6. Построение графических изображений по заданному алгоритму

Понятие алгоритма

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

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

1.      Кулинарный рецепт (рис. 1);

2.      Инструкция по сборке машинки из деталей детского конструктора;
3.      Инструкция по использованию стиральной машины и т.д.

 Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Слово алгоритм происходит от имени Мухаммеда Аль Хорезми (рис. 2) (787–850), первым предложившего приемы выполнения арифметических операций с многозначными числами.

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

Каждый алгоритм создается в расчете на выполнение конкретным исполнителем.

Рассмотрим, какие действия хотел предпринять Волк в сказке «Красная Шапочка», чтобы достичь своей цели.

1.      Встретить Красную Шапочку.
2.      Спросить ее, куда она идет.
3.      Добежать до домика бабушки.
4.      Съесть бабушку.
5.      Лечь в бабушкину кровать.
6.      Дождаться прихода Красной Шапочки.
7.      Ответить на вопросы Красной Шапочки.
8.      Попытаться съесть Красную Шапочку.
Исполнителем данного алгоритма является Волк.

Рассмотрим еще один пример – необходимо выполнить алгоритм:

1.      Пройти по дну реки до противоположного берега 500 метров на 
глубине реки больше 3 метров.
2.      Выйти на противоположный берег.
Данный алгоритм может выполнить только определенный исполнитель.
Человек (без скафандра) не сможет выполнить данный алгоритм. 
Зато с таким алгоритмом легко справится специальный 
робот-проводник.

Исходя из этих примеров, можем определить следующее:

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

Примером таких исполнителей являются стиральная машина-автомат, автопилот спутника и т.д.

Представления алгоритма

Алгоритм может представляться в следующих формах:

• Устной;
• Письменной.

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

1. Высыпать в емкость содержимое пакетика.
2. Налить стакан горячей воды.
3. Тщательно перемешать.

Пример построения изображения по алгоритму

Теперь попробуем поставить себя на место исполнителя. Что получится в результате выполнения следующего алгоритма?

Шаг 1. Запустить графический редактор Paint.

1. Щелкнуть по кнопке Пуск.
2. В Главном меню выбрать команду Программы.
3. В появившемся подменю выбрать команду Стандартные.
4. В следующем подменю выбрать команду Графический редактор Paint.
   
   Шаг 2. Выберите любой основной цвет, установите указатель мыши на нужный цвет палитры и щелкните правой кнопкой мыши.

Шаг 3. Используя инструмент Прямоугольник с нажатой клавишей Shift, нарисуйте квадрат небольшого размера.

Шаг 4. С помощью инструмента Заливка закрасьте тем же цветом.

Шаг 5. С помощью инструмента Выделение прямоугольной области выделите квадрат.

Шаг 6. Скопируйте и разместите рядом с нарисованным квадратом справа. Измените цвет заливки.

Шаг 7. Снова выделите теперь уже два квадрата. Скопируйте и разместите снизу от уже имеющихся двух квадратов.

Шаг 8. Не снимая выделения, выполните следующие действия в меню: Рисунок – Отразить/Повернуть – отразить слева направо.

Шаг 9. С помощью инструмента Выделение прямоугольной области выделите квадрат, состоящий из 4 квадратов.

Шаг 10. Скопируйте и разместите рядом с имеющимся квадратом справа.

Шаг 11. Снова выделите теперь уже два квадрата. Скопируйте и разместите снизу от уже имеющихся квадратов.

Конструирование объемных фигур

Программа Paint позволяет делать различные композиции, чтобы их осуществить, необходимо следовать определенному алгоритму. 

Используя объемные фигуры (например, кубики), можно получать интересные объемные изображения.

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

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

Для рисования кубика сначала мы выбираем инструмент Прямоугольник. Затем строим квадрат.

Выделим квадрат, скопируем его и разместим следующим образом:

Соединим вершины квадратов с помощью инструмента Линия. Для удобства можно увеличить масштаб. Также необходимо убрать лишние линии с помощью инструмента Ластик.

Закрасим грани кубика.

Складывать конструкцию нужно начинать всегда с нижнего заднего ряда и слева направо. На рисунке (рис. 16) приведен пример построения такой конструкции.

Попробуйте самостоятельно создать композиции

Список рекомендованной литературы

1)      Босова Л.Л. Информатика и ИКТ: Учебник для 5 класса. – М.: БИНОМ. Лаборатория знаний, 2012

2)      Босова Л.Л. Информатика: Рабочая тетрадь для 5 класса. – М.: БИНОМ. Лаборатория знаний, 2010.

3)      Босова Л.Л., Босова А.Ю. Уроки информатики в 5-6 классах: Методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.

Рекомендованное домашнее задание

1)      §2.10 (Босова Л.Л. Информатика и ИКТ: Учебник для 5 класса.)

2)      Тренироваться на создании шахматной доски 6х6, 8х8.

3)      Создать любую из композиций объемных фигур. Сохранить в своей рабочей папке.

Did you find apk for android? You can find new Free Android Games and apps.

С появлением растровых дисплеев для обработки и отображения графики на компьютере необходимо разработать набор алгоритмов, совместимых с ним: алгоритмы растровой графики.

Содержание исследования алгоритма растровой графики

Алгоритм преобразования сканирования для сегмента прямой линии
 Алгоритм преобразования полигонального сканирования и заполнения области
 Алгоритм обрезки
 Алгоритм сглаживания
 Алгоритм гашения
1
2
3
4
5

Алгоритм преобразования сканирования для сегмента прямой линии

Математически на прямой бесконечно много точек. Но чтобы представить эту прямую линию на экране растрового монитора компьютера, используйте конечные точки для представления бесконечных точек.
      
      
Чтобы использовать эти дискретные пиксели для аппроксимации линии на растровом дисплее, необходимо знать координаты x, y этих пикселей.
Знайте координаты P0 и P1, а затем используйте уравнение прямой линии, чтобы найти координаты других точек.
Найдите уравнения прямой линии для P0 и P1: y = kx + b (уравнение угла наклона, k — наклон, точка пересечения b)
k=(y₁-y₀)/(x₁-x₀) (x₁!=x₀)
Есть только одно уравнение, но есть два неизвестных, поэтому сначала предположите одно. Предполагая, что x известен, то есть начиная с начальной точки x0 x и продвигаясь на один пиксель в направлении x (not long = 1), может быть вычислено соответствующее значение y. Поскольку координаты пикселей являются целыми числами, значение y необходимо округлить.

Как отсканировать целую точку в пиксель экрана?
Например, P (1,7,0,8) округляется до P (1,0), но 1,7 ближе к 2, а 1 из 0,8 ближе. Если вы округлите эти два числа до ( 1,0) Ошибка большая, поэтому ее обычно округляют до (2,1), что ближе к фактическому

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

Три известных распространенных алгоритма рисования прямых линий

Использование уравнения y = kx + b для рисования линии требует умножения и сложения. Мы все знаем, что компьютер выполняет операции сложения быстрее всех, поэтому мы заменим его на операции сложения.

1. Метод численного дифференцирования (DDA)
 2. Рисование средней точки
 3. Алгоритм Брезенхема
1
2
3

Метод DDA (цифровой дифференциальный анализатор)

Представьте очень важную идею в графическом мышлении.
      
точка (x_i+1,y_i+1) Удовлетворяет y_i+1=kx_i+1+ b — уравнение. Как упоминалось ранее, пиксель увеличивается на 1, поэтому y_i+1=kx_i+1+b=k(x_i+1)+b=kx_i+k+b=y_i+ k, поэтому y_i+1=y_i+ k, значение этой формулы таково: значение y текущего шага равно значению y предыдущего шага плюс наклон k, что превращает исходное умножение и сложение в сложение! Это значительно повышает эффективность.

Рисование линии средней точки

Здесь используется общее уравнение прямой: F (x, y) = 0; Ax + By + C = 0
      
Прямая линия делит плоскость на три части.

Для точек на прямой:F(x,y)=0
 Для точки над линией:F(x,y)>0
 Для точек ниже линии:F(x,y)<0
1
2
3

Делайте один шаг в направлении максимального смещения каждый раз, и идти или не идти в другом направлении не зависит от оценки члена ошибки средней точки.
Предположим: 0 <= | k | <= 1. Таким образом, каждый раз, когда вы добавляете 1 в направлении x и 1 в направлении y, вам необходимо определить, не изменится ли оно.
      
Зная точку P, следующая точка будет не чем иным, как Pu или Pd. Идеальная прямая и прямые Pu и Pd имеют пересечение Q, а прямые Pu и Pd имеют середину M.
Когда M ниже Q, Pu находится близко к линии и должен быть следующим пикселем
Когда M больше Q, Pd следует принимать в качестве следующей точки.
Если M находится в точке Q, то M так же близко, как Pu и Pd, поэтому вы можете взять любую точку

Как определить точку M, то есть подставить M в уравнение идеальной прямой:
F(x_m,y_m)=Ax_m+By_m+C
di=F(x_m,y_m)=F(x_i+1,y_i+0.5)=A(x_i+1)+B(y_i+0.5)+C

Когда d <0: M ниже точки Q, Pu должен перейти в
 Когда d> 0: M больше Q, следует брать Pd
 Когда д=0 часов: M на прямой линии, можно выбрать Pd или Pu
1
2
3

Алгоритм Брезенхема

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

Основная идея алгоритма Брезенхема
      
Идея этого алгоритма состоит в том, чтобы построить набор линий виртуальной сети через центры пикселей каждой строки и столбца и вычислить точку пересечения между прямой линией и каждой вертикальной линией сети в порядке от начальной точки до конечной точки линии, а затем в соответствии с ошибкой Знак термина определяет пиксель в столбце пикселей, ближайший к этому пересечению. На рисунке d — это расстояние между точкой пересечения и пикселем, которое в точности равно наклону прямой k.
      
Предполагая, что каждое приращение (декремент) x + 1, y равно 0 или 1, оно зависит от расстояния между фактической прямой линией и ближайшей точкой сетки решетки. Максимальная ошибка этого расстояния составляет 0,5. . Если d> 0,5, это близко к верхней точке, в противном случае близко к нижней точке.

Начальное значение члена ошибки dd0=0
d=d+k
Как только d> = 1, вычтите из него 1, чтобы обеспечить относительность d и от 0 до 1.

Как повысить эффективность этого алгоритма сложения целых чисел?
Улучшение 1:Пусть e = d-0.5
e> 0, направление y увеличивается на 1; e <0, направление y не увеличивается
Когда e = 0, верхняя и нижняя точки растра могут отображаться по желанию

 eНачальный =-0.5  (оригиналdНачальное значение0.прямо сейчасe=d-0.5) 
   Каждый шаг имеетe=e+k
 if（e>0), тогда e = e-1 (гарантия 0<e<1）
1
2
3

Улучшение 2:
      
Шаги алгоритма:
      

Алгоритм Брезенхэма очень похож на алгоритм DDA, оба из которых добавляют наклон.
Но алгоритм DDA заключается в том, чтобы каждый раз находить новый y и затем округлять его для рисования; в то время как алгоритм Брезенхема оценивает знак, чтобы определить верхнюю и нижнюю точки. Следовательно, алгоритм концентрирует преимущества алгоритмов DDA и средней точки и имеет широкий спектр приложений.

резюме

Ядро проблем информатики — алгоритмы

Y=kx+b
1

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

Преобразование сканирования и заливка полигонов

Преобразование сканирования полигонов

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

(1) Выпуклый многоугольник
Линия между любыми двумя вершинами находится внутри многоугольника
(2) Вогнутый многоугольник
Связь между любыми двумя вершинами не находится в многоугольнике
(3) Многоугольник с внутренним кольцом.
Многоугольник содержит многоугольник

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

Это связано с двумя вопросами. Первый вопрос: если вы знаете границу, можете ли вы определить, какие пиксели находятся в многоугольнике?

Вторая проблема — узнать пиксели внутри многоугольника, а как найти границу многоугольника?
      
На приведенном выше рисунке пиксели внутри многоугольника известны, но границы многоугольника не могут быть получены.
Итак, второй вопрос касается не компьютерной графики, а проблемы распознавания графики.

Основная проблема растровой графики — преобразовать представление многоугольника с фиксированной точкой в ​​представление решетки. Это преобразование называется преобразованием сканирования полигона.
      

Алгоритм линии X-сканирования

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

Например, линия сканирования y = 3 пересекает границу многоугольника в 4 точках:
      
Поскольку все пиксели являются целыми числами, вот четыре точки (2,3), (4,3), (7,3), (9,3), которые определяют сканирование. В двух интервалах внутри многоугольника линия проходит от x = 2 до x = 4, от x = 7 до x = 9. Пиксели в этом интервале должны быть заполнены цветом.

Суть алгоритма состоит в том, чтобы расположить последовательность координат x пересечения в порядке возрастания x. Из этого вы можете получитьШаги алгоритма X-сканирования линииследующим образом:

Определите максимальное количество строк сканирования, занимаемых многоугольником, и получите минимальное и максимальное значения y вершин многоугольника.
 От y = ymin до y = ymax заполнять каждый раз одной строкой развертки
 Процесс заполнения строки развертки можно разделить на четыре этапа:
 A. Пересечение: вычислить пересечение линии сканирования и каждой стороны многоугольника.
 B. Сортировка: отсортируйте все пересечения в порядке возрастания.
C.Пары точек пересечения: первая и вторая, третья и четвертая (убедитесь, что количество пересечений четное).
D.Interval fill: установите для пикселей в этих пересекающихся интервалах цвет заливки, отличный от цвета фона.
1
2
3
4
5
6
7

Улучшение алгоритма преобразования полигональной развертки

Поскольку алгоритм линии X-сканирования должен быть пересечен, величина пересечения очень велика.
Важное значение алгоритма преобразования сканирования состоит в том, что он предлагается в графическом видеДве важные идеи:

Линия сканирования: при обработке графических изображений обработка по одной строке сканирования
 Дополнительное мышление
1
2

Рассмотрите возможность улучшения с трех сторон:

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

Чтобы избежать операции пересечения, необходимо ввести специальную структуру данных.
структура данных:
Таблица Active Edge (AET):Края, которые пересекают текущую линию сканирования, называются активными краями, и они сохраняются в связанном списке в порядке увеличения координаты x точки пересечения с линией сканирования.
      
На рисунке ребра P1, P4, P2 и P3 являются активными ребрами.
Содержимое узла (узел может быть представлен структурой в структуре данных)
      
Чтобы упростить создание и обновление активной таблицы ребер, необходимо создать новую таблицу ребер (NET) для хранения информации о ребрах многоугольника. Она разделена на 4 этапа:

Сначала создайте продольный связанный список.Длина связанного списка - это максимальное количество строк сканирования, занимаемых многоугольником. Каждый узел связанного списка называется корзиной, соответствующей каждой строке сканирования, покрытой многоугольником.
NETПовесьте ведро линии сканирования с таким же значением y на нижнем конце стороны. Другими словами, он хранится на краю, где линия сканирования появляется впервые.
1
2

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

Это удалено
 Если он не удален, второй - обновить свои данные.
 Посмотрите, приходит ли новая сторона, новая сторонаNET, Вы можете вставить сортировку для вставки.
1
2
3

Сводка алгоритма преобразования полигонального сканирования

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

Дополнительное мышление
 Связная мысль
 Создал специальную структуру данных
1
2
3

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

Алгоритм заполнения края

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

Метод заполнения забора

Забор — это прямая линия, которая проходит через вершины многоугольника и перпендикулярна линии сканирования. Он делит многоугольник на две половины. При работе с пересечением каждого края и линии сканирования пиксель между пересечением и забором должен быть дополнен.

Алгоритм пограничного маркера

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

Заполнение области

площадь—— Относится к фигуре с заливкой, представленной в виде точечной матрицы, которая представляет собой набор пикселей.
Заполнение областиЭто относится к процессу придания определенного цвета точке в области (часто называемой магазином семян) с последующим распространением этого цвета на всю область.
можно использовать областьПредставление внутренней точкис участиемГраничное представлениеДва представления

Внутренняя точка означает:Перечислить все пиксели внутри области, все пиксели внутри имеют одинаковый цвет, а граничные пиксели имеют цвет, отличный от внутренних пикселей.
Граничное представление:Перечислить все пиксели на границе, все пиксели на границе имеют одинаковый цвет, а внутренние пиксели имеют цвет, отличный от цвета граничных пикселей.
Алгоритм заполнения области требует, чтобы область была подключена, потому что только в связанной области можно распространить цвет начальной точки на другие точки в этой области.
Область можно разделить на область с 4-сторонним подключением и 8-стороннюю связанную область.

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

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

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

Используйте структуру стека для реализации простого алгоритма заполнения семян

Принцип алгоритма следующий:
Начальный пиксель помещается в стек, и следующие три шага повторяются, если стек не пуст:

Топ-пиксель поп
 Установите для всплывающих пикселей цвет заливки
 Проверьте четыре пикселя, прилегающих к пикселю стека, в порядке левого, верхнего, правого и нижнего. Если один из пикселей не находится на границе и для него не задан цвет заливки, то пиксель помещается в стек.
1
2
3

Недостатки алгоритма заполнения семян

Некоторые пиксели будут складываться несколько раз, что снижает эффективность алгоритма; структура стека занимает место
 Рекурсивное исполнение, алгоритм простой, но эффективность невысока. Каждый пиксель в области вводит рекурсию, ввод / вывод из стека, что требует много времени и памяти.
 Улучшить алгоритм, уменьшить количество рекурсий и повысить эффективность
1
2
3

Сводка преобразования полигонального сканирования и алгоритма заполнения области

Основная идея в другом

• Преобразование сканирования многоугольника относится к преобразованию представления вершины многоугольника в представление решетки.
• Заливка области изменяет только цвет заливки области и не меняет способ представления области

Различные базовые условия

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

Суть заливки области преобразования сканирования заключается в том, чтобы знать границу многоугольника.Есть много способов получить пиксель внутри многоугольника. Алгоритм сканирования линии заключается в использовании специальной структуры данных, чтобы избежать пересечения, а затем определять линии сканирования одну за другой.
Условие заполнения области более строгое, не только знает границу, но также знает точку в области, вы можете использовать четырехсвязную или восьмисвязную область для непрерывного расширения наружу

Сглаживание

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

Не в форме

Как показано на рисунке, когда мы рисуем изображение, мы используем конечные пиксели для приближения к бесконечной точке, поэтому это приведет к появлению наложений. «Пилообразный» — это форма «наложения спектров». Наложение спектров — неотъемлемое свойство решетчатого отображения. Причина явления наложения спектров — дискретная природа пикселей.Таким образом, алиасинг — неизбежный продукт цифровизации

Сглаживание

Лестница (пилообразная), созданная растровой графикой
 Когда графика содержит относительно небольшие объекты, эти объекты легко отбрасываются или игнорируются в статической графике.
 В последовательности анимации время от времени происходит мерцание
1
2
3

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

Вверху изображена прямоугольная волна с красными точками выборки. Ниже приведена форма сигнала, сформированная точками выборки, видно, что форма сигнала имеет наложения.

Технология сглаживания

Технология, используемая для уменьшения или устранения эффекта наложения спектров, называемая технологией сглаживания.
Поскольку явление сглаживания графики оказывает большое влияние на качество графики, почти все системы обработки графики должны выполнять обработку сглаживания для базовой графики.
Использование устройства отображения с более высоким разрешением помогает решить проблему наложения спектров, потому что пилообразный зуб можно уменьшить по сравнению с объектом. Метод сглаживания достигается при 4-кратном увеличении стоимости памяти и времени преобразования сканирования. Чтобы стабилизировать изображение на экране, электронная пушка должна бомбардировать все пиксели на экране не менее 1/24 секунды. Если количество пикселей удваивается, электронная пушка должна работать быстрее 4 раза. Но независимо от того, с точки зрения памяти или электронного оборудования, заплаченная цена слишком высока, поэтому этот метод не рекомендуется.

Технология сглаживания включает некоторую форму «размытия» для получения более плавного изображения.
Для черного прямоугольника на фоне Bose, смешав несколько серых пикселей около границы прямоугольника, можно смягчить резкое изменение цвета с черного на белый.
При наблюдении за этим изображением на расстоянии человеческий глаз может объединить эти мягко меняющиеся тени вместе, чтобы увидеть более гладкую границу. Как показано ниже
      

Два метода сглаживания:

Метод принятия невзвешенной площади
 Метод выборки взвешенной площади
1
2

Метод выборки невзвешенной площади
Вычислить цвет пикселя в соответствии с покрытием объекта. Покрытие означает долю области пикселя, покрываемую объектом.
Недостатки:

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

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

* Прямой отрезок рассматривается как длинный и узкий прямоугольник определенной ширины; когда отрезок прямой линии пересекает пиксель, вклад яркости пикселя определяется в соответствии с расстоянием между областью пересечения и центром пикселя.
* Доля сегмента прямой линии в яркости пикселя пропорциональна расстоянию между областью пересечения и центром пикселя.
* Установите весовую функцию (функцию Гаусса) между площадью области пересечения и расстоянием до центра пикселя, чтобы отразить вклад области пересечения в яркость всего пикселя.
* Используйте интеграл весовой функции, чтобы найти площадь области пересечения, и умножьте его на максимальное значение яркости, которое может установить пиксель, чтобы получить фактическое значение яркости пикселя.

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

делит пиксель на n = 3×3 субпикселя, таблица весов может быть принята как:

Схема взвешивания:Вес центрального пикселя в 4 раза больше веса углового субпикселя и в два раза больше веса других пикселей. Расчетная яркость каждой сетки из девяти субпикселей усредняется.
Затем найдите все субпиксели, центры которых попадают в сегмент прямой линии.
Наконец, вычислите сумму всех этих субпикселей до исходной яркости пикселей.

Эта статья воспроизводится по ссылке:http://blog.csdn.net/Silent_F/article/details/74279325

Пару слов о распознавании образов

Давно хотел написать общую статью, содержащую в себе самые основы Image Recognition, некий гайд по базовым методам, рассказывающий, когда их применять, какие задачи они решают, что возможно сделать вечером на коленке, а о чём лучше и не думать, не имея команды человек в 20.

Какие-то статьи по Optical Recognition я пишу давненько, так что пару раз в месяц мне пишут различные люди с вопросами по этой тематике. Иногда создаётся ощущение, что живёшь с ними в разных мирах. С одной стороны понимаешь, что человек скорее всего профессионал в смежной теме, но в методах оптического распознавания знает очень мало. И самое обидное, что он пытается применить метод из близрасположенной области знаний, который логичен, но в Image Recognition полностью не работает, но не понимает этого и сильно обижается, если ему начать рассказывать что-нибудь с самых основ. А учитывая, что рассказывать с основ — много времени, которого часто нет, становится всё ещё печальнее.

NB!

Обратите внимание, статья 2014 года. А сейчас 2021. С тех пор произошло пару революций в ComputerVision. Делает ли это приведенные тут методы неправильными? Нет. Но, скорее всего это не то что вы хотите использовать в качестве первой линии. Что использовать сегодня? Сложно сказать, очень много вариаций. Если хотите оставаться в курсе событий — советую читать мой канал (vk, telegram) про более новые методы/подходы.

Эта статья задумана для того, чтобы человек, который никогда не занимался методами распознавания изображений, смог в течении 10-15 минут создать у себя в голове некую базовую картину мира, соответствующую тематике, и понять в какую сторону ему копать. Многие методы, которые тут описаны, применимы к радиолокации и аудио-обработке.
Начну с пары принципов, которые мы всегда начинаем рассказывать потенциальному заказчику, или человеку, который хочет начать заниматься Optical Recognition:

• При решении задачи всегда идти от простейшего. Гораздо проще повесить на персону метку оранжевого цвета, чем следить за человеком, выделяя его каскадами. Гораздо проще взять камеру с большим разрешением, чем разрабатывать сверхразрешающий алгоритм.
• Строгая постановка задачи в методах оптического распознавания на порядки важнее, чем в задачах системного программирования: одно лишнее слово в ТЗ может добавить 50% работы.
• В задачах распознавания нет универсальных решений. Нельзя сделать алгоритм, который будет просто «распознавать любую надпись». Табличка на улице и лист текста — это принципиально разные объекты. Наверное, можно сделать общий алгоритм(вот хороший пример от гугла), но это будет требовать огромного труда большой команды и состоять из десятков различных подпрограмм.
• OpenCV — это библия, в которой есть множество методов, и с помощью которой можно решить 50% от объёма почти любой задачи, но OpenCV — это лишь малая часть того, что в реальности можно сделать. В одном исследовании в выводах было написано: «Задача не решается методами OpenCV, следовательно, она неразрешима». Старайтесь избегать такого, не лениться и трезво оценивать текущую задачу каждый раз с нуля, не используя OpenCV-шаблоны.

Очень сложно давать какой-то универсальный совет, или рассказать как создать какую-то структуру, вокруг которой можно строить решение произвольных задач компьютерного зрения. Цель этой статьи в структуризации того, что можно использовать. Я попробую разбить существующие методы на три группы. Первая группа это предварительная фильтрация и подготовка изображения. Вторая группа это логическая обработка результатов фильтрации. Третья группа это алгоритмы принятия решений на основе логической обработки. Границы между группами очень условные. Для решения задачи далеко не всегда нужно применять методы из всех групп, бывает достаточно двух, а иногда даже одного.

Список приведённых тут методов не полон. Предлагаю в комментариях добавлять критические методы, которые я не написал и приписывать каждому по 2-3 сопроводительных слова.

Часть 1. Фильтрация

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

Бинаризация по порогу, выбор области гистограммы

Самое просто преобразование — это бинаризация изображения по порогу. Для RGB изображения и изображения в градациях серого порогом является значение цвета. Встречаются идеальные задачи, в которых такого преобразования достаточно. Предположим, нужно автоматически выделить предметы на белом листе бумаги:


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

Бинаризация может дать очень интересные результаты при работе с гистограммами, в том числе в ситуации, если мы рассматриваем изображение не в RGB, а в HSV . Например, сегментировать интересующие цвета. На этом принципе можно построить как детектор метки так и детектор кожи человека.

Классическая фильтрация: Фурье, ФНЧ, ФВЧ

Классические методы фильтрации из радиолокации и обработки сигналов можно с успехом применять во множестве задач Pattern Recognition. Традиционным методом в радиолокации, который почти не используется в изображениях в чистом виде, является преобразование Фурье (конкретнее — БПФ ). Одно из немногих исключение, при которых используется одномерное преобразование Фурье, — компрессия изображений. Для анализа изображений одномерного преобразования обычно не хватает, нужно использовать куда более ресурсоёмкое двумерное преобразование.

Мало кто его в действительности рассчитывает, обычно, куда быстрее и проще использовать свёртку интересующей области с уже готовым фильтром, заточенным на высокие (ФВЧ) или низкие(ФНЧ) частоты. Такой метод, конечно, не позволяет сделать анализ спектра, но в конкретной задаче видеообработки обычно нужен не анализ, а результат.


Самые простые примеры фильтров, реализующих подчёркивание низких частот (фильтр Гаусса) и высоких частот (Фильтр Габора).
Для каждой точки изображения выбирается окно и перемножается с фильтром того же размера. Результатом такой свёртки является новое значение точки. При реализации ФНЧ и ФВЧ получаются изображения такого типа:

Вейвлеты

Но что если использовать для свёртки с сигналом некую произвольную характеристическую функцию? Тогда это будет называться «Вейвлет-преобразование». Это определение вейвлетов не является корректным, но традиционно сложилось, что во многих командах вейвлет-анализом называется поиск произвольного паттерна на изображении при помощи свёртки с моделью этого паттерна. Существует набор классических функций, используемых в вейвлет-анализе. К ним относятся вейвлет Хаара, вейвлет Морле, вейвлет мексиканская шляпа, и.т.д. Примитивы Хаара, про которые было несколько моих прошлых статей (1, 2), относятся к таким функциям для двумерного пространства.


Выше приведено 4 примера классических вейвлетов. 3х-мерный вейвлет Хаара, 2х-мерные вейвлет Мейера, вейвлет Мексиканская Шляпа, вейвлет Добеши. Хорошим примером использования расширеной трактовки вейвлетов является задачка поиска блика в глазу, для которой вейвлетом является сам блик:

Классические вейвлеты обычно используются для сжатия изображений, или для их классификации (будет описано ниже).

Корреляция

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

Фильтрации функций

Интересным классом фильтров является фильтрация функций. Это чисто математические фильтры, которые позволяют обнаружить простую математическую функцию на изображении (прямую, параболу, круг). Строится аккумулирующее изображение, в котором для каждой точки исходного изображения отрисовывается множество функций, её порождающих. Наиболее классическим преобразованием является преобразование Хафа для прямых. В этом преобразовании для каждой точки (x;y) отрисовывается множество точек (a;b) прямой y=ax+b, для которых верно равенство. Получаются красивые картинки:

(первый плюсег тому, кто первый найдёт подвох в картинке и таком определении и объяснит его, второй плюсег тому, кто первый скажет что тут изображено)
Преобразование Хафа позволяет находить любые параметризуемые функции. Например окружности. Есть модифицированное преобразование, которое позволяет искать любые фигуры. Это преобразование ужасно любят математики. Но вот при обработке изображений, оно, к сожалению, работает далеко не всегда. Очень медленная скорость работы, очень высокая чувствительность к качеству бинаризации. Даже в идеальных ситуациях я предпочитал обходиться другими методами.
Аналогом преобразования Хафа для прямых является преобразование Радона . Оно вычисляется через БПФ, что даёт выигрыш производительности в ситуации, когда точек очень много. К тому же его возможно применять к не бинаризованному изображению.

Фильтрации контуров

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

• Оператор Кэнни
• Оператор Собеля
• Оператор Лапласа
• Оператор Прюитт
• Оператор Робертса

Чаще всего используется именно Кэнни, который хорошо работает и реализация которого есть в OpenCV (Собель там тоже есть, но он хуже ищёт контуры).

Прочие фильтры

Сверху приведены фильтры, модификации которых помогают решить 80-90% задач. Но кроме них есть более редкие фильтры, используемые в локальных задачах. Таких фильтров десятки, я не буду приводить их все. Интересными являются итерационные фильтры (например активная модель внешнего вида), а так же риджлет и курвлет преобразования, являющиеся сплавом классической вейвлет фильтрации и анализом в поле радон-преобразования. Бимлет-преобразование красиво работает на границе вейвлет преобразования и логического анализа, позволяя выделить контуры:

Но эти преобразования весьма специфичны и заточены под редкие задачи.

Часть 2. Логическая обработка результатов фильтрации

Фильтрация даёт набор пригодных для обработки данных. Но зачастую нельзя просто взять и использовать эти данные без их обработки. В этом разделе будет несколько классических методов, позволяющих перейти от изображения к свойствам объектов, или к самим объектам.

Морфология

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

Контурный анализ

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

Если честно, то у меня ни разу ни получилось применить контурный анализ в реальных задачах. Уж слишком идеальные условия требуются. То граница не найдётся, то шумов слишком много. Но, если нужно что-то распознавать в идеальных условиях — то контурный анализ замечательный вариант. Очень быстро работает, красивая математика и понятная логика.

Особые точки

Особые точки это уникальные характеристики объекта, которые позволяют сопоставлять объект сам с собой или с похожими классами объектов. Существует несколько десятков способов позволяющих выделить такие точки. Некоторые способы выделяют особые точки в соседних кадрах, некоторые через большой промежуток времени и при смене освещения, некоторые позволяют найти особые точки, которые остаются таковыми даже при поворотах объекта. Начнём с методов, позволяющих найти особые точки, которые не такие стабильные, зато быстро рассчитываются, а потом пойдём по возрастанию сложности:
Первый класс. Особые точки, являющиеся стабильными на протяжении секунд. Такие точки служат для того, чтобы вести объект между соседними кадрами видео, или для сведения изображения с соседних камер. К таким точкам можно отнести локальные максимумы изображения, углы на изображении (лучший из детекторов, пожалуй, детектор Хариса), точки в которых достигается максимумы дисперсии, определённые градиенты и.т.д.
Второй класс. Особые точки, являющиеся стабильными при смене освещения и небольших движениях объекта. Такие точки служат в первую очередь для обучения и последующей классификации типов объектов. Например, классификатор пешехода или классификатор лица — это продукт системы, построенной именно на таких точках. Некоторые из ранее упомянутых вейвлетов могут являются базой для таких точек. Например, примитивы Хаара, поиск бликов, поиск прочих специфических функций. К таким точкам относятся точки, найденные методом гистограмм направленных градиентов (HOG).
Третий класс. Стабильные точки. Мне известно лишь про два метода, которые дают полную стабильность и про их модификации. Это SURF и SIFT. Они позволяют находить особые точки даже при повороте изображения. Расчёт таких точек осуществляется дольше по сравнению с остальными методами, но достаточно ограниченное время. К сожалению эти методы запатентованы. Хотя, в России патентовать алгоритмы низя, так что для внутреннего рынка пользуйтесь.

Часть 3. Обучение

ретья часть рассказа будет посвящена методам, которые не работают непосредственно с изображением, но которые позволяют принимать решения. В основном это различные методы машинного обучения и принятия решений. Недавно Яндыкс выложил на Хабр курс по этой тематике, там очень хорошая подборка. Вот тут оно есть в текстовой версии. Для серьёзного занятия тематикой настоятельно рекомендую посмотреть именно их. Тут я попробую обозначить несколько основных методов используемых именно в распознавании образов.
В 80% ситуаций суть обучения в задаче распознавания в следующем:
Имеется тестовая выборка, на которой есть несколько классов объектов. Пусть это будет наличие/отсутствие человека на фотографии. Для каждого изображения есть набор признаков, которые были выделены каким-нибудь признаком, будь то Хаар, HOG, SURF или какой-нибудь вейвлет. Алгоритм обучения должен построить такую модель, по которой он сумеет проанализировать новое изображение и принять решение, какой из объектов имеется на изображении.
Как это делается? Каждое из тестовых изображений — это точка в пространстве признаков. Её координаты это вес каждого из признаков на изображении. Пусть нашими признаками будут: «Наличие глаз», «Наличие носа», «Наличие двух рук», «Наличие ушей», и.т.д… Все эти признаки мы выделим существующими у нас детекторами, которые обучены на части тела, похожие на людские. Для человека в таком пространстве будет корректной точка [1;1;1;1;..]. Для обезьяны точка [1;0;1;0…] для лошади [1;0;0;0…]. Классификатор обучается по выборке примеров. Но не на всех фотографиях выделились руки, на других нет глаз, а на третьей у обезьяны из-за ошибки классификатора появился человеческий нос. Обучаемый классификатор человека автоматически разбивает пространство признаков таким образом, чтобы сказать: если первый признак лежит в диапазоне 0.5<x<1, второй 0.7<y<1, и.т.д., тогда это человек.
По существу цель классификатора — отрисовать в пространстве признаков области, характеристические для объектов классификации. Вот так будет выглядеть последовательное приближение к ответу для одного из классификаторов (AdaBoost) в двумерном пространстве:


Существует очень много классификаторов. Каждый из них лучше работает в какой-то своей задачке. Задача подбора классификатора к конкретной задаче это во многом искусство. Вот тут немножко красивых картинок на тему.

Простой случай, одномерное разделение

Разберём на примере самый простой случай классификации, когда пространство признака одномерное, а нам нужно разделить 2 класса. Ситуация встречается чаще, чем может представиться: например, когда нужно отличить два сигнала, или сравнить паттерн с образцом. Пусть у нас есть обучающая выборка. При этом получается изображение, где по оси X будет мера похожести, а по оси Y -количество событий с такой мерой. Когда искомый объект похож на себя — получается левая гауссиана. Когда не похож — правая. Значение X=0.4 разделяет выборки так, что ошибочное решение минимизирует вероятность принятия любого неправильного решения. Именно поиском такого разделителя и является задача классификации.

Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график — это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate ».

Что делать если измерений больше двух?

Алгоритмов много. Даже очень много. Если хотите подробно узнать про каждый из них читайте курс Воронцова, ссылка на который дана выше, и смотрите лекции Яндыкса. Сказать, какой из алгоритмов лучше для какой задачи часто заранее невозможно. Тут я попробую выделить основные, которые в 90% помогут новичку с первой задачей и реализацию которых на вашем языке программирования вы достоверно найдёте в интернете.
k-means (1, 2, 3 ) — один из самых простых алгоритмов обучения. Конечно, он в основном для кластеризации, но и обучить через него тоже можно. Работает в ситуации, когда группы объектов имеют неплохо разнесённый центр масс и не имеют большого пересечения.
AdaBoost (1, 2, 3) АдаБуста — один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.
SVM (1, 2, 3, 4 ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.

Ещё есть нейронные сети и регрессия. Но чтобы кратко их классифицировать и показать, чем они отличаются, нужна статья куда больше, чем эта.
________________________________________________
Надеюсь, у меня получилось сделать беглый обзор используемых методов без погружения в математику и описание. Может, кому-то это поможет. Хотя, конечно, статья неполна и нет ни слова ни о работе со стереоизображениями, ни о МНК с фильтром Калмана, ни об адаптивном байесовом подходе.
Если статья понравится, то попробую сделать вторую часть с подборкой примеров того, как решаются существующие задачки ImageRecognition.

И напоследок

Что почитать?
1) Когда-то мне очень понравилась книга «Цифровая обработка изображений» Б. Яне, которая написана просто и понятно, но в то же время приведена почти вся математика. Хороша для того, чтобы ознакомиться с существующими методами.
2) Классикой жанра является Р Гонсалес, Р. Вудс » Цифровая обработка изображений «. Почему-то она мне далась сложнее, чем первая. Сильно меньше математики, зато больше методов и картинок.
3) «Обработка и анализ изображений в задачах машинного зрения» — написана на базе курса, читаемого на одной из кафедр ФизТеха. Очень много методов и их подробного описания. Но на мой взгляд в книге есть два больших минуса: книга сильно ориентирована на пакет софта, который к ней прилагается, в книге слишком часто описание простого метода превращается в математические дебри, из которых сложно вынести структурную схему метода. Зато авторы сделали удобный сайт, где представлено почти всё содержание — wiki.technicalvision.ru
4) Почему-то мне кажется, что хорошая книжка, которая структурирует и увязывает картину мира, возникающую при занятии Image Recognition и Machine Learning — это «Об интеллекте» Джеффа Хокинса. Прямых методов там нет, но есть много мыслей на подумать, откуда прямые методы обработки изображений происходят. Когда вчитываешься, понимаешь, что методы работы человеческого мозга ты уже видел, но в задачах обработки видео.

ИНФОРМАТИКА. 6 КЛАССА. БОСОВА Л.Л. ОГЛАВЛЕНИЕ

§ 18. Управление исполнителем Чертёжник

---

Знакомимся с Чертёжником

Ключевые слова:
• исполнитель Чертёжник
• абсолютное смещение
• относительное смещение
• вспомогательный алгоритм
• основной алгоритм
• цикл п раз

Исполнитель Чертёжник предназначен для построения рисунков на координатной плоскости.

При задании точек этой координатной плоскости, в отличие от того, как это принято в математике, координаты х и у разделяются запятой. Например, координаты выделенной на рис. 63 точки будут записаны так: (1, 1).

Чертёжник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остаётся след — отрезок от предыдущего положения пера до нового. При перемещении поднятого пера никакого следа на плоскости не остаётся. В начальном положении перо Чертёжника всегда поднято и находится в точке (0, 0).

По команде поднять перо Чертёжник поднимает перо. Если перо уже было поднято, Чертёжник игнорирует эту команду: он не меняет положение пера и не сообщает об отказе. Иначе говоря, каким бы ни было положение пера до команды поднять перо, после этой команды оно будет поднятым.

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

Рисунки Чертёжник выполняет с помощью команд сместиться в точку и сдвинуться на вектор.

По команде сместиться в точку (а, Ь) Чертёжник сдвигается в точку с координатами (а, Ь). На рисунке 64 показаны результаты выполнения команды сместиться в точку (2, 3) при различных положениях пера до этой команды. Видно, что, независимо от предыдущего положения, перо оказывается в точке (2, 3), но длина и направление отрезка, который при этом чертится, могут быть различны. Команду сместиться в точку называют командой абсолютного смещения.

Назовите координаты точек, в которых находился Чертёжник до выполнения команды сместиться в точку (2, 3) (см. рис. 64).

В каком случае в результате выполнения команды сместиться в точку (2, 3) из некотрого показанного на рис. 64 начального положения не будет прочерчен ни один отрезок?

Пусть перо Чертёжника находится в точке (х, у). По команде (а, Ь) Чертёжник отсчитывает а единиц вправо вдоль горизонтальной оси (оси абсцисс), Ъ единиц вверх вдоль вертикальной оси (оси ординат) и сдвигает перо в точку с координатами (х + а; у + Ъ). Таким образом, координаты, указанные в команде, отсчитываются не от начала координат, а относительно текущего положения пера Чертежника. Поэтому команду сместиться на вектор называют командой относительного смещения.

На рисунке 65 показаны результаты выполнения команды сместиться на вектор (2, 3) при различных положениях пера до этой команды. Из рисунка видно, что положение пера после этой команды зависит от его предыдущего положения, зато в результате получаются отрезки, длина и направление которых одинаковы.

В математике направленные отрезки называются векторами, отсюда и происходит название команды.

Назовите координаты точек, в которых находилось перо Чертёжника до выполнения команды сместиться на вектор (2, 3) и куда оно переместилось после выполнения этой команды.

Как будет выполняться команда сместиться на вектор (а, Ь) , если: 

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

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

Пример алгоритма управления Чертёжником

Изобразим с помощью Чертёжника треугольник, положение вершин которого на координатной плоскости определяется парами чисел (1, 1), (3, 5), (5, 2) (рис. 66).

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

сместиться в точку (1, 1) опустить перо

сместиться в точку (3, 5)

сместиться в точку (5, 2)

сместиться в точку (1, 1)?

Предложите другие варианты выполнения этого задания. При этом число команд не должно превышать пяти (есть пять других вариантов).

А теперь составим такой алгоритм управления Чертёжником, чтобы с его помощью в произвольном месте координатной плоскости можно было нарисовать прямоугольник со сторонами, параллельными координатным осям, длины которых равны 2 и 4 единицам.

Зафиксируем одну из вершин прямоугольника в точке (1, 1). Нужный рисунок на координатной плоскости может выглядеть, как показано на рис. 67.

Предложите другой вариант рисунка, удовлетворяющий заданным условиям: одна из вершин прямоугольника расположена в точке (1, 1), а длины его сторон равны 2 и 4 единицам. (Существуют ещё семь вариантов.)

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

сместиться в точку (1, 1)

опустить перо

сместиться в точку (1, 3)

сместиться в точку (5, 3)

сместиться в точку (5, 1)

сместиться в точку (1, 1)

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

Воспользуемся для рисования прямоугольника командой относительного смещения.

Пусть (х, у) — координаты вершины А прямоугольника ABCD (рис. 69).

Тогда координаты вершины В можно записать как (х, у + 2), вершины С — как (х + 4, у + 2), вершины D — как (х + 4, у) (см. рис. 69).

Чтобы изобразить отрезок АВ, воспользуемся командой сместиться на вектор (0, 2).

В результате Чертёжник сдвинет перо из точки с координатами (х, у) в точку с координатами (х + 0, у + 2).

По команде сместиться на вектор (4, 0) перо окажется в точке (х + 4, у + 2). Чтобы из этой точки перейти в точку (х + 4, у + 0), следует выполнить команду сместиться на вектор (0, -2). По команде сместиться на вектор (-4, 0) перо Чертёжника прочертит отрезок к точке А:

Если в качестве вершины А зафиксировать точку с координатами (1, 1), то программа будет выглядеть так:

сместиться в точку (l, 1)

опустить перо

сместиться на вектор(0, 2)

сместиться на вектор(4, 0)

сместиться на вектор(0, -2)

сместиться на вектор(-4, 0)?

Для того чтобы нарисовать прямоугольник в другом месте координатной плоскости, например в точке с координатами (5, 5), достаточно изменить в этой программе только первую строку:

сместиться в точку (5, 5)

С помощью команды абсолютного смещения рисунок «привязывается» к строго определенным точкам координатной плоскости. Она используется чаще всего для установки начального положения пера Чертёжника.

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

Чертёжник учится, или Использование вспомогательных алгоритмов

Чертёжник может рисовать любые фигуры из отрезков, например цифры почтового индекса. Как известно, каждая такая цифра вписана в прямоугольник (рис. 70).

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

Алгоритм рисования цифры 0 может иметь вид:
опустить перо
сместиться на вектор (0, 2)
сместиться на вектор (1, 0)
сместиться на вектор (0, -2)
сместиться на вектор (-1, 0)
поднять перо
сместиться на вектор (2, 0)

Для чего нужна последняя команда?

Для рисования цифры 6 можно использовать алгоритм:
сместиться на вектор (1, 2) опустить перо
сместиться на вектор (-1, -1)
сместиться на вектор (1, 0)
сместиться на вектор (0, -1)
сместиться на вектор (-1, 0)
сместиться на вектор (0, 1)
поднять перо
сместиться на вектор (2, -1)

Для чего нужна первая команда? Для чего нужна последняя команда?

А теперь представьте, что для Чертёжника необходимо разработать алгоритм рисования почтового индекса города Красноярска — 660000.

Самый простой вариант — составить очень длинный алгоритм, в котором дважды повторить рисование цифры 6 и четырежды — цифры 0.

Но есть и другой способ. Оказывается, Чертёжник может «запомнить», как рисуется та или иная цифра. Для этого алгоритм рисования цифр 0 и 6 нужно оформить в виде вспомогательного алгоритма.

Вспомогательный алгоритм

Вспомогательный алгоритм рисования цифры 0 будет выглядеть так:
алг цифра_0
нач
     опустить перо
     сместиться на вектор (0, 2)
     сместиться на вектор (1, 0)
     сместиться на вектор (0, -2)
     сместиться на вектор (-1, 0)
     поднять перо
     сместиться на вектор (2, 0)
кон

Строка алг цифра_О называется заголовком алгоритма. Имя алгоритма — цифра О. Алгоритм рисования буквы помещается чуть правее между служебными словами нач и кон.

Вспомогательный алгоритм рисования цифры 6 оформите самостоятельно.

Приказ на выполнение вспомогательного алгоритма записывается в основном алгоритме.

В среде КуМир основной алгоритм для изображения индекса 660000 будет выглядеть так:
использовать Чертежник
алг индекс Красноярска
нач
     цифра_6
     цифра_6
     цифра_0
     цифра_0
     цифра_0
     цифра_0
кон

К какому типу алгоритмов относится этот основной алгоритм?

Цикл ПОВТОРИТЬ n РАЗ

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

Например, программу рисования ряда из пяти ромбов (рис. 71) с помощью конструкции повторения можно записать так:
использовать Чертежник
алг ряд ромбов
нач
     сместиться в точку (1,2)
     нц 5 раз
          опустить перо
          сместиться на вектор (1, 2)
          сместиться на вектор (1, -2)
          сместиться на вектор (-1, -2)
          сместиться на вектор (-1, 2)
          поднять перо
          сместиться на вектор (3, 0)
     кц
кон

Рисование ромба можно оформить в виде вспомогательного алгоритма:
алг ромб
нач
     сместиться на вектор (1, 2)
     сместиться на вектор (1, -2)
     сместиться на вектор (-1, -2)
     сместиться на вектор (-1, 2)
кон

Тогда основной алгоритм будет выглядеть так:
использовать Чертежник
алг ряд ромбов_1
нач
     сместиться в точку (1,2)
     нц 5 раз
          опустить перо
          ромб
          поднять перо
          сместиться на вектор (3, 0)
     кц
кон

В общем виде конструкция повторения записывается так:

нц <число повторений> раз

<тело цикла>

кц

Служебные слова нц и кц пишутся одно под другим. Чуть правее между ними записывается повторяющаяся последовательность команд (тело цикла). Число повторений — произвольное целое число. Именно столько раз при выполнении алгоритма будут повторены команды, образующие тело цикла.

Предложите вариант решения задачи о почтовом индексе Красноярска с использованием конструкции повторения.

Можно ли обойтись без вспомогательного алгоритма в следующих ситуациях (рис. 72)?

Вопросы и задания

1. Охарактеризуйте исполнителя Чертёжник.

2. Составьте для Чертёжника алгоритм рисования прямоугольника со сторонами, параллельными осям координат, если известны координаты его двух вершин: (2, 1) и (7, 5).

3. Составьте алгоритм управления Чертёжником, в результате выполнения которого в произвольном месте координатной плоскости будет нарисован квадрат, длина стороны которого равна 2 единицам.

4. Составьте алгоритм управления Чертёжником, в результате выполнения которого в произвольном месте координатной плоскости будет нарисован прямоугольник, длины сторон которого равны 3 и 4 единицам.

5. Составьте алгоритм рисования изображенных ниже фигур так, чтобы в процессе рисования перо не отрывалось от бумаги и ни одна линия не проводилась дважды.

6. Оформите вспомогательные алгоритмы для рисования букв «М», «И», «Р». Составьте алгоритмы рисования слов «МИР», «РИМ», «МИМ».

7. Разработайте вспомогательный алгоритм рисования домика. На его основе составьте основной алгоритм рисования улицы из пяти домиков.

8. Составьте алгоритмы управления Чертёжником, после исполнения которых будут получены следующие рисунки

9. Составьте алгоритмы управления Чертёжником, после исполнения которых будут получены следующие рисунки

10. Придумайте свои задачи для Чертёжника.

---

§ 17. Типы алгоритмов

§ 18. Управление исполнителем Чертёжник

---