Задачи

1.   Пусть дано множество из п точек {(*,-, (/,)}, і= 1, ..., п, на плоскости (X, Y), и мы хотим аппроксимировать точки кривой вида 2 /=іауфу(д:), где величины <fy(x),

/'= 1     d, представляют собой произвольные заданные функции, а коэффициенты

aj, j= 1  d, следует определить. Найдите общее решение для коэффициентов,

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

2.   а) Покажите, что для вещественной симметричной матрицы S функция v(Sv/vJv вектора ѵ минимальна (максимальна), если в качестве ѵ взят собственный вектор, относящийся к наименьшему (наибольшему) собственному значению матрицы S.

б)   Покажите для двумерного случая, что геометрическое место точек х, удовлетворяющих равенству xtSx=c, где с — положительная константа, представляет собой эллипс, оси которого совпадают с собственными векторами матрицы S.

3.   а) Покажите, что преобразование точки в кривую, которое переводит точку (*, у) на плоскости изображения в кривую p=;tcos Ѳ+г/sin Ѳ на плоскости парамет

ров, обладает следующим свойством: точки,' лежащие на одной кривой на плоскости параметров, соответствуют линиям, проходящим через одну точку на плоскости изображения.

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

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

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

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

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

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

б)   Распространите результат п. «а» на сети из произвольного числа связных компонент.

в)   Распространите результат п. «б» на сети с дырами.

7.   Покажите, что площадь произвольного многоугольника определяется формулой

где {xj, yj) — координаты j-й вершинымногоугольника, а суммирование начинается с произвольной вершины и продолжается по часовой стрелке вокруг многоугольника, пока снова не будет достигнута исходная вершина.

8.   Постройте алгоритм для отыскания выпуклой оболочки дискретного объекта.

9.   Постройте алгоритм для реализации гистерезисного сглаживания произвольного замкнутого контура.

10.  а) Начертите невыпуклый пятиугольник и нарисуйте приблизительно его скелет.

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

в)   Нарисуйте приблизительно объект, соответствующий каждому из скелетов п. «б».

П. Покажите, что угловая естественная функция 0(s), определенная в тексте, является периодической функцией с периодом L и нулевым средним.

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