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


Оглавление

Общее описание распознавания эллипса

Распознавание эллипсов основано на алгоритме из предыдущей статьи. На первом этапе строится распределение расстояний до точек линии в зависимости от угла (рисунок 1). Далее производится сглаживание полученных значений с использованием простого усреднения ближайших значений. После чего находится максимальное значение расстояния, оно выбирается в качестве угла поворота эллипса. Ширина и высота рассчитываются по четырем точкам расположенным на 0°, 90°, 180° и 270° относительно найденного угла поворота.

Полный код алгоритма доступен в этом репозитории, код относящийся к эллипсу находится в файле EllipseRecognizer.java, построение расстояния по точкам в файле ShapeHistogram.java.

Определение угла поворота эллипса

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

Код сг расстояний и сглаживания
// Постоение расстояния от центра до каждой точки фигуры.
double minimalAngle = 0.0;
double maximalAngle = 0.0;
double maximalDistance = 0.0;

for (Distance distance : distancies) {
	minimalAngle = Math.min(distance.angle, minimalAngle);
	maximalAngle = Math.max(distance.angle, maximalAngle);
	maximalDistance = Math.max(distance.distance, maximalDistance);
}

for (Distance distance : distancies) {
	distance.normalized = distance.distance / maximalDistance;
	distance.position = values.length * (distance.angle - minimalAngle) / (maximalAngle - minimalAngle);
}

// Пересчет расстояний в зависимости от угла относительно центра.

for (int index = 0; index < values.length; index += 1) {
	Distance dd = new Distance();
	dd.position = index;

	int found = Collections
			.binarySearch(distancies, dd, Comparator.comparingDouble((Distance d) -> d.position));

	if (found >= 0) {
		values[index] = distancies.get(found).normalized;
	} else {
		int point = -found - 1;
		Distance left = distancies.get(point - 1);
		Distance right = distancies.get(point);
		double factor = (index - left.position) / (left.position - right.position);

		values[index] = left.normalized + factor * (left.normalized - right.normalized);

		if (factor < 0.5) {
			indexes[index] = point - 1;
		} else {
			indexes[index] = point;
		}
	}
}
Код формирования ядра свертки
int size = dataSize / (2 * 5 + 1);
int center = (size / 2) | 1;
double values[] = new double[size];
double value = 1.0 / size;

for (int index = 0; index < size; index += 1) {
	values[index] = value;
}

return new Kernel(values, center);
Рисунок 1: График для эллипса.
Рисунок 1: График для эллипса.
Рисунок 2: Расстояния для эллипса.
Рисунок 2: Расстояния для эллипса.

Определение ширины и высоты эллипса

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

width=\frac{distance(\alpha) + distance(\alpha + \pi)}{2}width=\frac{distance(\alpha - \frac{\pi}{2}) + distance(\alpha + \frac{\pi}{2})}{2}

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

Код расчета параметров эллипса
int agnleIndex = 0;
double agnleValue = Double.MIN_VALUE;
double[] filtered = new double[values.length];

flatKernel.apply(values, filtered);

// Нахождение угла, соответствующего максимальному расстоянию.
for (int index = 0; index < filtered.length; index += 1) {
	double value = filtered[index];

	if (value > agnleValue) {
		agnleIndex = index;
		agnleValue = value;
	}
}

Distance widthA = distances.get(indexes[agnleIndex]);
Distance widthB = distances.get(indexes[(agnleIndex + indexes.length / 2) % indexes.length]);
Distance heightA = distances.get(indexes[(agnleIndex + 1 * indexes.length / 4) % indexes.length]);
Distance heightB = distances.get(indexes[(agnleIndex + 3 * indexes.length / 4) % indexes.length]);

// Расчет параметров эллипса по углу и четырем точкам.
ellipseWidth = (int) ((widthA.distance + widthB.distance) / 2.0);
ellipseHeight = (int) ((heightA.distance + heightB.distance) / 2.0);
ellipseAngle = 2.0 * Math.PI * agnleIndex / Algorithm.DATA_SIZE + Math.PI / 2.0;
Рисунок 3: Построенный эллипс и его параметры.
Рисунок 3: Построенный эллипс и его параметры.

Распознавание многоугольников

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

Что такое базовый отрезок

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

Полный алгоритм распознавания многоугольников доступен в файле PolylineRecognizer.java, в репозитории проекта.

Нахождение базового отрезка многоугольника

Пусть пользователь нарисовал фигуру. Выберем в качестве первой точки базового отрезка начальную точку данной фигуры. Далее найдем наиболее удаленную от нее точку фигуры и выберем ее в качестве второй точки базового отрезка (рисунок 4).

Код поиска точек базового отрезка
// Первая точка отрезка равна начальной точке фигуры.
pointIndexes.clear();
polygonPoints.clear();

pointIndexes.add(0);
polygonPoints.add(points.get(0));

int farIndex = 0;
double farDistance = Double.MIN_VALUE;

// Найдем максимально удаленную точку от первой.
for (int index = 0; index < points.size(); index += 1) {
	Point point = points.get(index);
	double dstance = Math.pow(point.x - polygonPoints.get(0).x, 2.0)
			+ Math.pow(point.y - polygonPoints.get(0).y, 2.0);

	if (farDistance < dstance) {
		farIndex = index;
		farDistance = dstance;
	}
}

// Выберем ее второй точкой отрезка. Будем считать, что точек больше одной.
pointIndexes.add(farIndex);
polygonPoints.add(points.get(farIndex));
Рисунок 4: Фигура, нарисованная пользователем.
Рисунок 4: Фигура, нарисованная пользователем.

Распознавание многоугольника

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

  1. Для каждого сегмента найти расстояние до каждой точки, расположенной между точек сегмента;

  2. Если максимальное расстояние меньше порога — завершить многоугольник;

  3. Выбрать сегмент с наибольшим максимальным расстоянием;

  4. Разбить выбранный сегмент на два, используя самую удаленную точку;

  5. Если число итераций достигло максимального — завершить многоугольник.

Код добавления точек в многоугольник
// Итеративно пробуем добавлять по одной точке в многоугольник.
for (int iteration = 0; iteration < N_ITERATIONS; iteration += 1) {
	double maxDistance = Double.MIN_VALUE;
	int bestIndex = 0;
	int bestPoint = 0;

  // Найдем точку максимально удаленную от сегиента и соответствубщий сегмент.
	for (int indexIndex = 0; indexIndex < pointIndexes.size(); indexIndex += 1) {
		int fromIndex = pointIndexes.get(indexIndex);
		int toIndex = pointIndexes.get((indexIndex + 1) % pointIndexes.size());
		Point pointA = points.get(fromIndex);
		Point pointB = points.get(toIndex);
		Function<Point, Double> callback;

		if (pointA.x == pointB.x) {
			callback = (point) -> (double) Math.abs(pointA.y - point.y);
		} else if (pointA.y == pointB.y) {
			callback = (point) -> (double) Math.abs(pointA.x - point.x);
		} else {
			double a = (double) (pointA.y - pointB.y) / (pointA.x - pointB.x);
			double b = pointA.y - a * pointA.x;
			double a21 = a * a + 1;

			callback = (point) -> Math.sqrt(Math.pow(b + a * point.x - point.y, 2.0) / a21);
		}

		while (fromIndex != toIndex) {
			Point point = points.get(fromIndex);
			double distance = callback.apply(point);

			if (maxDistance < distance) {
				maxDistance = distance;
				bestIndex = fromIndex;
				bestPoint = indexIndex;
			}

			fromIndex = (fromIndex + 1) % points.size();
		}
	}

	int fromIndex = pointIndexes.get(bestPoint);
	int toIndex = pointIndexes.get((bestPoint + 1) % pointIndexes.size());
	Point pointA = points.get(fromIndex);
	Point pointB = points.get(toIndex);

  // Если максимально расстояние до точки меньше порога - завершить построение.
	if (maxDistance < MAX_DISTANCE
			* Math.sqrt(Math.pow(pointA.y - pointB.y, 2.0) + Math.pow(pointA.x - pointB.x, 2.0))) {
		break;
	}

  // Найденная точка добавляется в многоугольник между точками соответствующего сегмента.
	pointIndexes.add(bestPoint + 1, bestIndex);
	polygonPoints.add(bestPoint + 1, points.get(bestIndex));
}
Пошаговая работа алгоритма в картинках

Выбор распознанной фигуры

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

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

Код расчета для многоугольников
double mse = 0.0;

for (int indexIndex = 0; indexIndex < pointIndexes.size(); indexIndex += 1) {
	int fromIndex = pointIndexes.get(indexIndex);
	int toIndex = pointIndexes.get((indexIndex + 1) % pointIndexes.size());
	Point pointA = points.get(fromIndex);
	Point pointB = points.get(toIndex);
	Function<Point, Double> callback;

	if (pointA.x == pointB.x) {
		callback = (point) -> (double) Math.abs(pointA.y - point.y);
	} else if (pointA.y == pointB.y) {
		callback = (point) -> (double) Math.abs(pointA.x - point.x);
	} else {
		double a = (double) (pointA.y - pointB.y) / (pointA.x - pointB.x);
		double b = pointA.y - a * pointA.x;
		double a21 = a * a + 1;

		callback = (point) -> Math.sqrt(Math.pow(b + a * point.x - point.y, 2.0) / a21);
	}

	while (fromIndex != toIndex) {
		Point point = points.get(fromIndex);
		mse += callback.apply(point);

		fromIndex = (fromIndex + 1) % points.size();
	}
}

mse /= points.size();

return mse;
Код расчета для эллипса
double mse = 0.0;

for (Point point : points) {
	double dx = (point.x - centerX) * Math.cos(ellipseAngle) - (point.y - centerY) * Math.sin(ellipseAngle);
	double dy = (point.x - centerX) * Math.sin(ellipseAngle) + (point.y - centerY) * Math.cos(ellipseAngle);
	double distance = Math.sqrt(Math.pow(dx / ellipseWidth, 2.0) + Math.pow(dy / ellipseHeight, 2.0));
	double delta = Math.pow(distance - 1.0, 2.0) * (Math.pow(dx, 2.0) + Math.pow(dy, 2.0));

	mse += delta;
}

mse /= points.size();

return mse;

Проблемы описанных алгоритмов

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

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

Примеры фигур с пересечением и двойной гранью
Фигура с двойной гранью.
Фигура с двойной гранью.
Фигура с пересечением.
Фигура с пересечением.

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

Заключение

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

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

Комментарии (6)


  1. csl
    06.01.2022 22:45

    Есть ли особая причина использовать index += 1 ? Находится под катом "Код сг расстояний и сглаживания"

    Лучше ли будет применить ++index (обсуждение в 2015 году постфиксной и префиксной записи инкремента/декремента https://stackoverflow.com/a/4706225/214296 [хоть там и C++ в тегах])?


    1. SnakeSolid Автор
      07.01.2022 07:31
      +2

      Возможно это имело значение встарых версиях java. Сейчас подобные конструкции компилируются в одинаковый байткод (ссылка на пример в godbolt), так что это скорее вопрос удобства восприятия, чем скорости работы. У меня в коде причина использования += чисто субъективная, связана она с тем, что я пишу не только на java.

      Код класса с различными инкрементами
      public class Test {
        public static void increment1() {
              for (int index = 0 ; index < 10; index += 1) {}
        }
      
        public static void increment2() {
              for (int index = 0 ; index < 10; index++) {}
        }
      
        public static void increment3() {
              for (int index = 0 ; index < 10; ++index) {}
        }
      }
      Полученный байт код
      public static void increment1();
        Code:
           0: iconst_0
           1: istore_0
           2: iload_0
           3: bipush        10
           5: if_icmpge     14
           8: iinc          0, 1
          11: goto          2
          14: return
      
      public static void increment2();
        Code:
           0: iconst_0
           1: istore_0
           2: iload_0
           3: bipush        10
           5: if_icmpge     14
           8: iinc          0, 1
          11: goto          2
          14: return
      
      public static void increment3();
        Code:
           0: iconst_0
           1: istore_0
           2: iload_0
           3: bipush        10
           5: if_icmpge     14
           8: iinc          0, 1
          11: goto          2
          14: return
      Версия java
      $ java -version
      openjdk version "11.0.13" 2021-10-19
      OpenJDK Runtime Environment (build 11.0.13+8-post-Debian-1deb10u1)
      OpenJDK 64-Bit Server VM (build 11.0.13+8-post-Debian-1deb10u1, mixed mode, sharing)


    1. FGV
      07.01.2022 11:03
      +1

      а в чем разница?

      там же вывод приводится:

      Because (1) and (4) are decoupled, either pre- or post-increment can be used.

      т.е. до лампочки что пре, что пост, что выражение.


  1. nin-jin
    08.01.2022 14:32
    +1

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

    Я думаю лучше делать это линейным алгоритмом: идём по точкам, вычисляя углы между соседними отрезками. Если угол (от развёрнутого угла) больше порога, то детектируем поворот. Если сумма углов до поворота меньше порога, то аппроксимируем прямой. Таким образом шероховатые линии будут выпрямляться, а дуги будут оставаться дугами (хотя их тоже можно аппроксимировать кривыми безье, только отслеживая уже не углы, а изменения углов).


    1. SnakeSolid Автор
      08.01.2022 15:43

      Я старался чтобы ни один алгоритм не выполнялся с квадратичной сложностью. Если я правильно посчитал, то общая сложность для всех фигур — N * log(N), плюс несколько одиночных проходов по всем точкам, плюс константа зависящая от размера внутренного массива, сейчас это 1024, но его можно уменьшить.

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

      Мой расчет сложности

      Для всех фигур выполняется преобразование масива точек в массив из 1024 чисел. Преобразование состоит из следующих стадий:

      • расчет центра фигуры (один проход по всем точкам);

      • расчет расстояния до каждой точки фигуры (тоже один проход);

      • сортировка точек по расстоянию (N * log(N) от числа точек);

      • заполнение массива расстояний по углам с использованием двоичного поиска (1024 * log(N));

      В общей сложности на подготовку нужно N * log(N). Далее для каждый алгоритм идет своим путем:

      • эллипс — сглаживает данные (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;

      • многоугольник — строит корреляцию с ядром (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;

      • ломанная линия — единственный алгоритм проходящий по всем точкам несколько раз, максимальное число проходов равно максимальному точек в линии. Итого N * const.

      В общем случае в худшем случае, сокращая константы будет N * log(N). Далее нужно посчитать отклонение от рисунка пользователя для каждой фигуры.

      • эллипс — один проход по всем точкам пользователя. Итого - N;

      • многоугольник и ломанная линия — проход по всем точкам, нарисованным пользователем. Итого - N.

      В конечном счете, без сокращения, получается: N * log(N) + 5 N + 1024 log(N) + несколько проходов по фиксированному массиву с расстояниями.


    1. SnakeSolid Автор
      08.01.2022 16:58

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

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

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