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

Оглавление

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

Распознавание эллипсов основано на алгоритме из предыдущей статьи. На первом этапе строится распределение расстояний до точек линии в зависимости от угла (рисунок 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: График для эллипса.
Рисунок 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: Построенный эллипс и его параметры.

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

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

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

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

Полный алгоритм распознавания многоугольников доступен в файле 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: Фигура, нарисованная пользователем.

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

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

  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 за идею различения фигур среднеквадратичному отклонению и концепцию алгоритма кусочно-линейной аппроксимации.