Бинаризация рукописного лабиринта
 

Имеется алгоритм декодирования маршрута проезда специфического лабиринта в набор токенов.
Правила обхода пути очень просты:

• Если ветка маршрута имеет один и более поворотов, она помечается синим цветом
• Если ветка маршрута имеет один и более тупиков, она помечается красным цветом
• Если ветка маршрута имеет хотя бы один поворот, она не может иметь более одного тупика

На матрице MxN жук благополучно проходит весь маршрут до конца, попутно составляя строку токенов (фигурки тетрамино и пентамино), что отображено в gif-анимации. Проблема только в одном: Жук может двигать по пути шириной в 1 пиксел. Следовательно, имеется редактор лабиринтов.

Вопрос: Какие фильтры следует применять, если лабиринт нарисован от руки маркером или мелом на доске под любым углом?:write:
Уточнения: В самом начале виден корявый лабиринт, нарисованый от руки в Paint. Потом он оквадрачивается в матрицу (всё прорисовал вручную, каждый кадр).:-?
Варианты: Пробовал классический FloodFill с составлением массива координат линий заливки - слишком много данных и не знаю, как систематизировать. Хотел применять алгоритм чтения QR-кода, но мне не нужны три ключевых квадрата на углах.:agree: Так же пытался пустить жука с "радаром", который двигается в направлении дальнего горизонта и составляет список поворотов, но не смог сформулировать в скрипте (js+canvas). А выгугленный алгоритм использует уже бинаризованый лабиринт с шагом в 1 пиксел.

Спасибо!

вероятно, Line fitting, или методы аппроксимации набора точек прямой

Что касается обхода лабиринта - отдельная тема. Я бегло посмотрел статью. На первый взгляд ни о чем :)
См. в сторону
1. Неинформированные методы поиска (в пространстве состояний)
2. Информированные методы поиска (в пространстве состояний)
3. Визуализация работы информированных методов поиска

---

Если интересно, почти все неинформированные методы я реализовал в рамках своего проекта
https://github.com/nervgh/recursive-iterator
http://javascript.ru/forum/project/5...-iterator.html

Информированные(й) в рамках форка (на скорую руку)
http://javascript.ru/forum/project/1...tml#post377012

Думаю, меня не совсем так поняли.:)
Нужно кривой лабиринт, нарисованый на бумаге и захваченый WebCamer'ой в режиме реального времени обойти. Мой "жук" его обходит только в случае, когда путь имеет ширину в 1 пиксел.
Тем самым, мне нужен фильтр, который не просто векторизирует растровую размазню 1:1, а просто составляет список координат горизонтальных и вертикальных коридоров.

Вот как на анимашке ниже:
Сначала - два варианта одного лабиринта от руки (кривой и ещё кривее), а потом ровные фиолетовые линии. В конце - многократный зум микроскопического лабиринта 14x10 пикселей.:dance:
Т.е. мне надо изображение 128x110 аккуратно уменьшить до 14x10, сохранив структуру маршрута для жука.
(построчная заливка и прочие методы не дают нужного результата)

Спасибо!:thanks:

ответ на этот вопрос в первом предложении моего предыдущего поста

Хм. Извиняюсь.
Я привык работать с растровыми изображениями (типа используя mmx/sse на ассемблере фильтровать кадры), а вот векторные алгоритмы - тёмное дело. Вот что выдаёт мой скрипт в окне FireFox. Некоторые линии прорисовываются дважды.

Алгоритм: Нахожу первую чёрную точку.

1. Используя Math sin/cos по всему радиусу определяю максимально длинную линию, запоминая её координаты
2. Разбиваю всю линию на массив отдельных точек и, как в пункте 1, по всему радиусу ищу максимум

Как видите, алгоритм до тупого прост. И, как правило, это его проблема, так как он один путь проходит несколько раз. Из массива линии потом удалять нельзя, надо удалять в самом процессе. Что сложно для меня и я не понимаю эту часть.

Жёлтые и красные - соответственно вертикальные (север/юг) и горизонтальные (запад/восток) направляющие.
(есть, правда, идея учитывать ширину линии, чтобы ошибочно не проходить сквозь перекрёстки. но это пока довольно сложно мне)

В идеале (в бинарном массиве) формируется таблица декодирования (в матрице жук её формирует):

• ESWN (EAST + SOUTH + WEST + NORTH) (UpperCase - путь имеет повороты) - старт-кольцо
• wsn или wns (west + south + north или west + south + north) (LowerCase - путь имеет тупики) - фигурка ├ тетриса
• WN (WEST + NORTH) - фигурка └ тетриса
• N (NORTH) - фигурка │ тетриса
• WS - фигурка ┌
• NWS
• sw
• SE
• en
• SEN

В итоге получается "├└│┌⊓┤└┴⊔" в массиве 14x10.

Paguo-86PK, ok, я тебя понял. Моя ссылкабыла немного про другое.

Не знаю зачем тебе это надо, но задача любопытная :)

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

Описываю ниже свое понимание
Упрощенный вариант
1. определить размер кисти
2. выпрямить линии
3. сжать до "однопиксельных" размеров


Попытаюсь описать как
на примере конкретно взятой линии
- имеем точки, описывающие линию (A - начало, B - конец)
- строим вектор AB по этим точкам (выделено зеленым)
- помещаем его в двумерную координатную плоскость (x-y) так, как показано на рисунке
- т.о. теперь имеем три вектора OX, OY, AB
- ищем угол между векторами OX & AB
- ищем угол между векторами OY & AB
- сравниваем углы, какой меньше, в ту сторону и выпрямляем
- выпрямление происходит на длину вектора согласно шагу кисти

https://yadi.sk/d/K63ZmF-1iR4up

Ну, что, товарищи, кто
1. расставит на этом (original) безобразии опорные точки (pivot_points)
2. и представит его в виде векторов (линий)
? :)

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

Алгоритм - бета-вариант
 

Я это примерно и делаю.

Чтобы не быть голословным, в архиве - мой сырейщий алгоритм (работает лишь в Opera 12 и FireFox почему-то:blink: А chrome только с --disable-web-security) и gif-лабиринт, который выдаёт пачку дублирующих линий. Нужно, как в п.1, определить размер кисти и учитывать его.

(в gif'ке первый кадр я подправил так, чтобы чтение начиналось с нужной позиции: В идеале, чтение начинается с кольца (восток+юг+запад+север) и если в кадре лабиринт перевёрнут, алгоритм должен это учитывать. Но до этого пока очень далеко)

Paguo-86PK, вроде как запилил определение размеров указателя (кисти) и для примера нарисовал его розовым :)

Исходники тут.

Разумеется, писал не с нуля, поскреб по сусекам :D

Теперь надо этим маркером (указателем) пройти лабиринт, собирая опорные точки.

Спасибо за вклад
 

Спасибо:thanks:
Правда, что-то слишком сложно. И мне несколько неудобно за напряг (не думал, что Вы расписывать будете код):no:

Просто, меня заинтересовало наличие готовых решений в этой области (как, скажем, OpenCV).

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

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

P.S.: По идее, чтобы задумку выдать за свою и иметь полное право на неё, я должен справиться сам.
Повторяюсь: Думал, есть готовые библиотеки (типа OpenCV).

P.P.S.: Применение: На многих форумах задумку просто осмеяли и задаваться там проблемой распознавания как-то неудобно:haha:
Так как основное применение сообществом воспринимается дегенеративным.:stop:

Да нет, тут скорее желание убежать от сложнозадачи, даже поиска нужных компонентов OpenCV
Посколь имел опыт с попыткой добить нечто подобное, так что nerv_, на моих глазах совершил подвиг самонапряга, правда тут есть ещё пара тройка подобных личностей, могущих себя самоувлечь и помочь

на здоровье :)

мне кажется наоборот)

а может и не быть)

я не рассматривал задачу в таком контексте. Моя трактовка более простая.
коме того размер кисти вычисляется достаточно быстро

ну, прости :D

---

эм... подвиг есть не спорю, только не стоит его преувеличивать. Повторюсь, я поскреб по сусекам и, посути, надергал уже готовых модулей из своих проектов. Список всех приведен тут. Из них, под данную задачу с нуля я писал только Decoder & MatrixWalker, Rectangle, из которых последние два очевидные в своей реализации (думать не надо, только пиши).

Возвращаясь к теме
Лично мне проще:
- взять свой ранее написанный класс/модуль и подпилить его под себя (чем заново изобретать велосипед)
- писать на es6 с использованием классов и модулей, чем использовать процедурной подход. ООП позволяет сравнительно легко управлять сложностью приложения
а если ты посмотришь в index.js, то увидишь, что, по сути, у меня есть декодер, который всем заведует. Но, т.к. приложение не дописано, сейчас в нем не очень чисто :) В идеале (как-то так):

import Decoder from './modules/Decoder';


let {document} = window;
let image = document.getElementById('original');
let stage = document.getElementById('stage');


let decoder = new Decoder();

decoder.onDecodeComplete = function() {
    decoder.write(stage);
};

decoder.decode(image);

куда уж проще)

nerv_, на чем научился писать подобные штуки?)

Думаю, я слишком примитивно владею программированием, поэтому и кажется, что Ваш код сложен.

Для примера, набыдлокодил здесь эмулятор+дизассемблер+ассе мблер своего процессора, где можно оценить и мой стиль, и уровень владения.:write: (звук работает в Chrome)

По теме: Я подумал, что распознание лабиринта пересекается с OCR. По сути, в этом плане мои лабиринты очень правильные: Нет оторваных стенок, нет глухих комнат, и путь всегда один (в данной версии я в концепции не развивал проход лабиринта в двух и более маршрутах).:agree:

P.S.: Кстати, мою идею осмеяли, потому что я решил строить/читать лабиринты со скрытым смыслом.
Я взял Муна, Хангыль, принцип Пентамино и составил собственный алфавит, конвертируя слова в лабиринты. (В противовес QR-коду, который без смартфона чудовищно сложно глазами прочитать)
Гласные звуки - буквы корейского алфавита.
Согласные звуки - частично шрифт Муна и греческий алфавит.
Причём, парные глухие и звонкие согласные имеют одну фигурку.
Один лабиринт - одно слово.
Ниже - архив с подсказками и анимациями.

Для чего это надо?
Во-первых, такие лабиринты легко печатаются на 3D-принтере. Так как имеют "правильную" структуру: Нет оторваных стен и глухих комнат.
Во-вторых, при должном навыке человек может научиться читать лабиринты за час (собственная мама в роли подопытной прочитала стихи за 15 минут). Не говоря уже о машине.
В-третьих, тактильно лабиринты можно читать пальцами при должном навыке.

Ну как? И на этом форуме идею назовёте дегенератской?:D

Human Quick Response Labyrintic Text
 

Накoнец-то чуточку продвинулся в решении поставленной задачи.

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

<html>
<head>
<style>
body	{
	margin		:0px 0px 0px 0px;
	padding		:0px 0px 0px 0px;
}
</style>
<script>
var	hPprCnv;
var	hPprCtx;
var	hSrcCnv;
var	hSrcCtx;
var	hCtrCnv;
var	hCtrCtx;
var	hPrvCnv;
var	hPrvCtx;
var	hRslCnv;
var	hRslCtx;
var	vecs;
var	circle;
var	iStepFactor = 32;

// sharp
// Процедура бинарной резкости
CanvasRenderingContext2D.prototype.sharp =
function	() {
	var	imd = this.getImageData(0, 0, this.canvas.width, this.canvas.height);
	var	p = imd.data;
	var	i = p.length,
		r, g, b,
		x, y, z = 384;
	var	mask;
	while(i >= 4) {
		-- i;
		r = (p[-- i] >> 7) * 255; g = (p[-- i] >> 7) * 255; b = (p[-- i] >> 7) * 255;
		mask = z < r + g + b ? 255 : 0;
		p[i + 3] = 255, p[i + 2] = mask, p[i + 1] = mask, p[i + 0] = mask;
		if(mask)
			y = i >> 2;
	}
	x = y % this.canvas.width;
	y = (y - x) / this.canvas.width;
	this.putImageData(imd, 0, 0);
	return	{
		x	:x + 1,
		y	:y + 1
	}
}

// Процедура обнаружения границ
CanvasRenderingContext2D.prototype.findEdge =
function	() {
	var	w = this.canvas.width;
	var	j = i - w * 4 - 4;
	var	x, y, z = 384;
	var	r, g, b;
	var	k, m, r;
	var	dx, dy;
	var	minx = 1 << 30;
	var	miny = 1 << 30;
	var	maxx = 0;
	var	maxy = 0;
	var	mindy;
	var	maxdy;
	var	arr = [];
	var	corners = [];
	var	borders = [];
	var	tmp;
	var	lasta = "";
	var	lastx, lasty;
	//
	this.save();
	this.globalCompositeOperation = "difference";
	this.drawImage(this.canvas, 1, 1);
	this.restore();
	var	imd = this.getImageData(1, 1, this.canvas.width, this.canvas.height);
	var	buf = imd.data;
	var	i = imd.data.length;
	var	pixels = new Uint32Array(imd.data.buffer);
	var	j = pixels.length;
	var	fnd = -1;
	do {
		fnd = Array.prototype.indexOf.call(pixels, 0xFFFFFFFF, fnd + 1);
		if(fnd >= 0) {
			x = fnd % this.canvas.width,
			y = Math.floor(fnd / this.canvas.width);
			minx = Math.min(minx, x);
			miny = Math.min(miny, y);
			maxx = Math.min(maxx, x);
			maxy = Math.min(maxy, y);
			arr.push({
				x	:x,
				y	:y,
				a	:""
			});
		}
	} while(fnd >= 0);
	// Сортировка пикселей контура в цепочку
	for(i = 0; i < arr.length - 1; ++ i) {
		x = arr[i].x;
		y = arr[i].y;
		k = 0;
		for(j = i + 1; j < arr.length; ++ j) {
			dx = arr[j].x - x, dy = arr[j].y - y;
			r = Math.sqrt(dx * dx + dy * dy);
			if(k == 0 || m > r)
				m = r,
				k = j;
		}
		arr.splice(i + 1, 0, arr.splice(k, 1)[0]);
	}
	/*var	point = { x: arr[0].x, y: arr[0].y };
	arr.sort((a, b) => {
		var d = (a.x - point.x) ** 2 + (a.y - point.y) ** 2 - (b.x - point.x) ** 2 + (b.y - point.y) ** 2;
		point = { x: b.x, y: b.y};
		return d;
	});*/
	// Построение "маршрута" движения (векторной ориентации) линий контура
	for(i = 0; i < arr.length; ++ i) {
		var	east = 0;
		var	west = 0;
		var	south = 0;
		var	north = 0;
		for(j = 1; j <= iStepFactor; ++ j) {
			tmp = arr[j];
			dx = tmp.x - arr[0].x, dy = tmp.y - arr[0].y;
			if(Math.abs(dx) > Math.abs(dy)) {
				if(dx < 0)
					east ++;
				else
					west ++;
			} else
				if(dy < 0)
					south ++;
				else
					north ++;
		}
		var	max = Math.max(east, west, north, south);
		arr[0].a = max == east ? "E" : max == west ? "W" : max == north ? "N" : "S";
		if(lasta != arr[0].a) {
			corners.push({
				x	:arr[0].x,
				y	:arr[0].y,
				a	:lasta
			});
			if(lasta != "") {
				if(!(lasta == "E" || "W" == lasta))
					borders.push({
						x1	:lastx,
						y1	:lasty,
						x2	:arr[0].x,
						y2	:lasty
					});
				else
					borders.push({
						x1	:lastx,
						y1	:lasty,
						x2	:lastx,
						y2	:arr[0].y
					});
			}
			lastx = arr[0].x,
			lasty = arr[0].y;
		}
		lasta = arr[0].a;
		arr.push(arr.shift());
	}
	for(i = 0; i < corners.length - 1; ++ i) {
		x = corners[i].x;
		y = corners[i].y;
		for(j = i + 1; j < corners.length; ++ j) {
		}
	}
	//
	corners.push({
		x	:arr[0].x,
		y	:arr[0].y,
		a	:lasta
	});
	return {
		arr	:arr,
		corners	:corners,
		borders	:borders
	};
}

var	vecmax	= 0;
var	vecidx	= 0;
var	paths	= [{len: []}];

var	car	= {
		x	:0,
		y	:100,
		dx	:1,
		dy	:1,
		dir	:0.0,
		cdx	:0,	// Counter by dx
		cdy	:0	// Counter by dy
	};
var	pen	= {
		x	:0,
		y	:100
	};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
var	lapping	= 0;
var	race	= [];
var	curdir	= "";
var	cntdir	= "";
var	waydir	= "";
var	lastdir	= "";

function  run() {
	var	colors = {
			"N"	:"red",
			"S"	:"magenta",
			"E"	:"blue",
			"W"	:"cyan"
		};
	pixels.unshift(pixels.pop());
	hRslCtx.clearRect(0, 0, hRslCnv.width, hRslCnv.height);
	hRslCtx.beginPath();
	var	x, y, nx, ny;
	for(i = 0; i < corners.length; ++ i) {
		nx = corners[i].x, ny = corners[i].y;
		if(corners[i].a == "E" ||  "W" == corners[i].a) {
			hRslCtx.lineTo(x, ny);
		} else {
			hRslCtx.lineTo(nx, y);
		}
		dx = nx - x, dy = ny - y;
		;
		x = nx, y = ny;
		if(i)
			hRslCtx.lineTo(x, y);
		else
			hRslCtx.moveTo(x, y);
	}
	hRslCtx.fillStyle = "grey brown red orange yellow green cyan blue magenta black".split(" ")[Math.floor(Math.random() * 10)];
	hRslCtx.fillStyle = "grey silver".split(" ")[Math.floor(Math.random() * 2)];
	hRslCtx.closePath();
	hRslCtx.fill();
	//hRslCtx.stroke();
	hRslCtx.beginPath();
	for(i = 0; i < borders.length; ++ i) {
		nx = borders[i].x1, ny = borders[i].y1;
		hRslCtx.moveTo(nx, ny);
		hRslCtx.lineTo(borders[i].x2, borders[i].y2);
	}
	hRslCtx.strokeStyle = "grey brown red orange yellow green cyan blue magenta black".split(" ")[Math.floor(Math.random() * 10)];
	hRslCtx.closePath();
	hRslCtx.lineWidth = 4;
	hRslCtx.stroke();
	return;
	////////////////////////////////////////////////////////////////////////////////
}

var	hqr;
var	pixels;
var	corners;
var	borders;

function main() {
	hPprCnv = document.getElementById("Paper");
	hSrcCnv = document.getElementById("Source");
	hCtrCnv = document.getElementById("Contour");
	hPrvCnv = document.getElementById("Preview");
	hRslCnv = document.getElementById("Result");
	hSrcCnv.setAttribute('crossOrigin', '');
	hPprCtx = hPprCnv.getContext("2d");
	hCtrCtx = hCtrCnv.getContext("2d");
	hSrcCtx = hSrcCnv.getContext("2d");
	hPrvCtx = hPrvCnv.getContext("2d");
	hRslCtx = hRslCnv.getContext("2d");
	hPprCtx.fillStyle = "#FF00000";
	hPprCtx.fillRect(0, 0, hPprCnv.width, hPprCnv.height);
	hSrcCtx.fillStyle = "#FF000000";
	hPrvCtx.fillStyle = "#CCCCCC";
	hSrcCtx.fillRect(0, 0, hSrcCnv.width, hSrcCnv.height);
	hPprCnv.addEventListener("mousemove",
		function(e) {
			x = e.offsetX;
			y = e.offsetY;
			if(e.buttons == 1) {
				hPprCtx.fillStyle = "white";
				hPprCtx.fillRect(x, y, 16, 16);
				hSrcCtx.drawImage(hPprCnv, 0, 0);
				localStorage.draftImage = hPprCnv.toDataURL();
				Start();
			}
		}
	);
	hPprCnv.addEventListener("mouseup",
		function(e) {
			hSrcCtx.drawImage(hPprCnv, 0, 0);
			localStorage.draftImage = hPprCnv.toDataURL();
			Start();
		}
	);
	hSrcCnv.addEventListener("mousemove",
		function(e) {
			x = e.offsetX;
			y = e.offsetY;
			if(e.buttons == 1) {
				hSrcCtx.fillStyle = "white";
				hSrcCtx.fillRect(x, y, 16, 16);
			}
		}
	);
	if(localStorage.draftImage) {
		var	im = new Image();
		im.src = localStorage.draftImage;
		im.addEventListener("load", function(e) {
				hPprCtx.drawImage(e.target, 0, 0);
			}
		);
	}
}
function loadDefault() {
	hSrcCtx.drawImage(document.getElementsByTagName("img")[0], 0, 0, hSrcCnv.width, hSrcCnv.height);
	setTimeout('Start(); hSrcCnv.style.qdisplay="none"; setInterval("run(); run(); run();", 1);', 1000);
}
function Start() {
	vecs = [hSrcCtx.sharp()];
	car.x = vecs[0].x;
	car.y = vecs[0].y;
	pen.x = car.x;
	pen.y = car.y;
	tmp = hSrcCtx.findEdge();
	pixels = tmp.arr;
	corners = tmp.corners;
	borders = tmp.borders;
	car.x = pixels[0].x;
	car.y = pixels[0].y;
	lapping = 0;
	race = [];
	waydir = "";
	curdir = "";
	cntdir = 0;
}
function Clear() {
	hSrcCtx.fillStyle="black";
	hSrcCtx.fillRect(0, 0, hSrcCnv.width, hSrcCnv.height);
	hPprCtx.fillStyle = "black";
	hPprCtx.fillRect(0, 0, hPprCnv.width, hPprCnv.height);

}
</script>
<style>
img,
canvas#Source,
canvas#Contour,
canvas#Preview	{
	display	:none;
}
</style>
</head>
<body onload='main()'>
<button onclick='hqr.Bug()' style=display:none>Step</button>
<button onclick='Clear()'>Clear</button>
<button onclick='Start()' style=display:none>Start</button><hr />
<canvas id='Paper' width='320' height='240'></canvas><canvas id='Source' width='320' height='240'></canvas>
<canvas id='Contour' width='320' height='240' style='display:none'></canvas><canvas id='Preview' width='320' height='240'></canvas>
<canvas id='Result' width='320' height='240'></canvas>
<img style=display:none title='animanu.gif' src1='https://i.imgur.com/oZBA50h.png' src='https://i.imgur.com/NDa8KXn.gif' crossorigin = '' onload='setTimeout(loadDefault, 100)' /></img>
<div style=display:none>
<pre id='log'>---</pre>
<pre id='Log'></pre>
</div>
</body>
</html>