匹配的拼图块
我没有什么有用的事情可做，正在玩这样的拼图游戏：
alt text http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg
我想知道是否可以制作一个程序来帮助我把它放在一起。
想象一下，我有一个小拼图，比如 4x3 的拼图，但小标签和空白不均匀 - 不同的拼图具有不同的高度、不同的形状和不同的大小。我要做的就是给所有这些碎片拍照，让程序分析它们并将它们的属性存储在某个地方。然后，当我拿起一块拼图时，我可以要求程序告诉我哪些拼图应该是它的“邻居” - 或者如果我必须填写一个空白，它会告诉我想要的拼图块如何看。
不幸的是，我从未在图像处理和模式识别方面做过任何事情，所以我想向您寻求一些指导 - 如何识别拼图块（基本上是带有标签和孔的正方形）<强>在图片中？
然后我可能需要旋转它，使其处于正确的位置，缩放到一定比例，然后测量每侧的制表符/空白，以及每侧的坡度（如果存在）。
我知道扫描/拍摄 1000 块拼图并使用它会太耗时，这只是一个我可以学到新东西的宠物项目。
I have nothing useful to do and was playing with jigsaw puzzle like this:
alt text http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg
and I was wondering if it'd be possible to make a program that assists me in putting it together.
Imagine that I have a small puzzle, like 4x3 pieces, but the little tabs and blanks are non-uniform - different pieces have these tabs in different height, of different shape, of different size. What I'd do is to take pictures of all of these pieces, let a program analyze them and store their attributes somewhere. Then, when I pick up a piece, I could ask the program to tell me which pieces should be its 'neighbours' - or if I have to fill in a blank, it'd tell me how does the wanted puzzle piece(s) look.
Unfortunately I've never did anything with image processing and pattern recognition, so I'd like to ask you for some pointers - how do I recognize a jigsaw piece (basically a square with tabs and holes) in a picture?
Then I'd probably need to rotate it so it's in the right position, scale to some proportion and then measure tab/blank on each side, and also each side's slope, if present.
I know that it would be too time consuming to scan/photograph 1000 pieces of puzzle and use it, this would be just a pet project where I'd learn something new.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
数据采集
（这称为色度键、蓝屏或背景颜色方法）
采集数据处理
Data acquisition
(This is known as Chroma Key, Blue Screen or Background Color method)
Acquisition data processing
退一步回到问题本身。构建拼图的问题可以很简单（P），也可以很困难（NP），具体取决于这些拼图是只适合一个邻居还是多个邻居。如果每条边只有一个适合，那么您只需找到每个块/边的邻居即可完成（O（#pieces*#sides））。如果某些块允许多次适合不同的邻居，那么，为了完成整个拼图，您可能需要回溯（因为您做出了错误的选择并且陷入了困境）。
然而，首先要解决的问题是如何表示棋子。如果您想表示任意形状，那么您可以使用透明度或蒙版来表示图块的哪些区域实际上是该块的一部分。如果您使用正方形，那么问题可能会更容易。在后一种情况下，您可以考虑正方形每边的最后一行像素，并将其与您在所有其他块中找到的最相似的像素行进行匹配。
尽管您使用的是方形瓷砖，但您可以使用第二种方法来实际帮助您解决真正的难题。真正的谜题通常是建立在 NxM 网格上的。当扫描盒子中的图像时，您将其分成相同的 NxM 方形瓷砖网格，然后让系统来解决这个问题。然后，问题是用系统内部的图块直观地映射您手中的实际波浪形部件（当它们很小且颜色均匀时）。但是，如果您在内部表示任意形状，则会遇到同样的问题。
A step back to the problem itself. The problem of building a puzzle can be easy (P) or hard (NP), depending of whether the pieces fit only one neighbour, or many. If there is only one fit for each edge, then you just find, for each piece/side its neighbour and you're done (O(#pieces*#sides)). If some pieces allow multiple fits into different neighbours, then, in order to complete the whole puzzle, you may need backtracking (because you made a wrong choice and you get stuck).
However, the first problem to solve is how to represent pieces. If you want to represent arbitrary shapes, then you can probably use transparency or masks to represent which areas of a tile are actually part of the piece. If you use square shapes then the problem may be easier. In the latter case, you can consider the last row of pixels on each side of the square and match it with the most similar row of pixels that you find across all other pieces.
You can use the second approach to actually help you solve a real puzzle, despite the fact that you use square tiles. Real puzzles are normally built upon a NxM grid of pieces. When scanning the image from the box, you split it into the same NxM grid of square tiles, and get the system to solve that. The problem is then to visually map the actual squiggly piece that you hold in your hand with a tile inside the system (when they are small and uniformly coloured). But you get the same problem if you represent arbitrary shapes internally.