Каков эффективный Алгоритм для Решения Загадки Jigshaw?
Трудность отслеживания:
- ошибки диапазона
- ошибки граничного условия
4 ответа
Решение подобных проблем может быть обманчиво сложным, особенно если не накладываются никакие ограничения на размер и сложность головоломки.
Вот мои мысли о подходе к написанию программы для решения такой головоломки.
Есть четыре ключевых элемента информации, которые вы можете использовать по отдельности или вместе в качестве ключей к решению головоломки:
- Информация о форме каждой из частей (как выглядят их края)
- Информация о цвете каждой из частей (смежные части обычно имеют плавные переходы).
- Информация об ориентации каждой части (где плоские и угловые края могут лежать)
- Общий размер и количество частей обеспечивают общие размеры головоломки
Итак, какую информацию будет предоставлять программа - давайте предположим, что каждая часть головоломки представляет собой небольшое прямоугольное изображение с прозрачностью информация, используемая для идентификации той части головоломки, которая представляет собой непрямоугольные края.
Исходя из этого, относительно легко идентифицировать четыре угловых части (в типичной головоломке). У них будет ровно два ребра с плоскими контурами (см. Контурную карту ниже).
Затем, Я собирал информацию о форме каждого из четырех краев части пазла. Эта информация может быть использована для построения матрицы смежности , указывающей, какие части подходят друг к другу.
Теперь мы можем сократить эту матрицу смежности, чтобы идентифицировать только те части, которые имеют плавные переходы цвета в их смежной конфигурации. Это несколько сложно, потому что для этого требуется уровень нечеткого соответствия - поскольку не каждая граница пиксель-пиксель обязательно будет иметь плавный переход цвета.
Используя четыре первоначально идентифицированных угловых элемента, теперь мы должны быть в состоянии восстановить размеры и положения всех частей головоломки.
Удобной структурой данных для представления форм краев может быть контурная карта - по сути, набор целых чисел, представляющих приращения расстояний от противоположной стороны изображения до последнего непрозрачного пикселя на каждой из четырех сторон кусок пазла. Соответствующие детали должны иметь контурные карты в зеркальном отображении.
Убедитесь, что вы просматриваете мужские / женские части детали - это сократит поиск вдвое.
I don't think that the human way would be that helpful for an implementation - a computer can look at all pieces many times a second and I see no (big) win by categorizing the pieces into corner, edge, and inner pieces, especially because there are only three categories and they have very different sizes.
Given a set of images of all pieces I would try to derive a simple descriptor for every piece or edge. The descriptor must contain information about the rough shape and the color of the piece respectively the four edges. Given a puzzle with 1000 pieces, there are 4000 edges and always two must be equal (ignoring the border of the puzzle). In consequence the descriptor must be able to distinguish 2000 edges requiring at least 11 bits.
Dividing one piece into a 3 x 3 check board pattern with nine fields will give three colors per edge - with eight bits per channel we already have 72 bits. I first tended to suggest to reduce the color resolution, but this seems not to be a good idea - for example a blue sky might really benefit from a high color resolution. Note that calculating the colors probably requires separating the piece from the background and trying to align the edges to the horizontal and vertical axises.
In very uniform areas like blue skies the color information will probably not be enough to find good matches and additional geometric information will be required. I would try to describe the shape of the edge by its curvature or a derived measure. Maybe sampled at ten to twenty points per edge. This probably again relies on background separation and edge alignment.
Finally the computer can do the easy part - compare all pairs of edge descriptors and find the best matches. This process should probably be controlled to become more local instead of simple best match first because when ever you have found a corner (Correct English word? I mean three pieces in a L-shape.) you have two edges constraining the piece to find and one can track back early if no good match can be found (indicating an error made before or a hard puzzle).
Предполагая, что вы не собираетесь заниматься какими-либо вещами, связанными с компьютерным зрением, это были бы очень маленькие вариации на поиск всего проблемного пространства, т.е. пробовать каждую деталь до тех пор, пока она не подходит, и повторять. Основная оптимизация заключалась бы в том, чтобы не пробовать один и тот же кусок в одном и том же месте, если вы знаете, что он не подходит. Боковые / угловые части составляют относительно немного частей и, вероятно, не могут рассматриваться в какой-либо крупной оптимизации.
Структура данных, вероятно, будет чем-то вроде хэш-матрицы, где вы можете быстро проверить, '