соответствующие кусочки головоломки

Question

У меня нет ничего полезного, и я играл в такую ​​головоломку:

альтернативный текст http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg

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

Представьте, что у меня есть небольшая головоломка, например, 4х3, но маленькие вкладки и заготовки неоднородны - разные части имеют эти вкладки разной высоты, разной формы,разного размера.Что бы я сделал, чтобы сфотографировать все эти части, позволить программе проанализировать их и хранить их атрибуты где-нибудь.Затем, когда я возьму кусок, я мог бы попросить программу сказать мне, какие части должны быть ее «соседями» - или, если мне нужно будет заполнить пробел, она скажет мне, как создаются нужные кусочки головоломки.смотреть.

К сожалению, я никогда ничего не делал с обработкой изображений и распознаванием образов, поэтому я хотел бы спросить вас о некоторых указателях - как мне распознать кусок головоломки (в основном квадрат свкладки и отверстия) на картинке ?

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

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

Answer 1

Сбор данных

(Этот метод называется «Хроматический ключ», «Синий экран» или «Цвет фона»)

1. Найдите хорошо освещенную комнату, с наименьшим разбросом освещения по комнате.
2. Найдите цвет (оттенок), который редко используется во всей головоломке / картинке.
3. Получите цветную бумагу того же цвета.
4. Поместите столько кусочков головоломки на цветную бумагу, сколько она поместится.
   • Вы можете разбить пазлы на группы и использовать их как подсказку для компьютера.
   • Убедитесь, что части не перекрываются и не касаются друг друга.
   • Пока не беспокойтесь об ориентации.
5. Сделайте снимок и загрузите его на компьютер.
   • Может потребоваться калибровка цвета, поскольку фон Chroma Key может нарушить встроенный цветовой баланс цифровой камеры.

Обработка данных сбора

1. Получить программное обеспечение для компьютерного зрения
   • OpenCV, MATLAB, C ++, Java, библиотека изображений Python и т. Д.
2. Выполните подключенный компонент по цвету хроматического ключа на изображении.
   • Запросите контуры отверстий подключенного компонента, которые представляют собой кусочки головоломки.
3. Исправление ошибок в обнаруженном списке.
4. Выберите индексный словарь (см. Пост Иры Бакстер) и измерьте кусочки.
   • Если части прямоугольные, сначала найдите углы.
   • Если фигуры имеют четырехслойный оттиск, длина сторон (измеряемая от угла к углу) также является ценной подписью.
   • Поиск "Shape Context" на SO или Google или здесь .
   • Наконец, получите цветовую гистограмму куска, чтобы вы могли запросить кусочки по цвету позже.
5. Чтобы сделать их доступными для поиска, поместите их в базу данных, чтобы можно было запрашивать фрагменты с любыми комбинациями словаря индексации.

Answer 2

Шаг назад к самой проблеме.Задача построения головоломки может быть простой (P) или сложной (NP), в зависимости от того, подходят ли кусочки только одному соседу или нескольким.Если для каждого ребра есть только одна подгонка, то вы просто находите для каждой фигуры / стороны ее соседа, и все готово (O (# штук * # сторон)).Если некоторые куски допускают множественное совпадение с разными соседями, то для завершения всей головоломки вам может потребоваться возврат (так как вы сделали неправильный выбор и застряли).

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

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