README

关于

Jigsawlutioner 是一种基于每个拼图碎片拍摄的照片解决拼图的算法。

另请参阅

bywulf/jigsawlutioner-cli - 使用此算法的命令行工具
byWulf/jigsawlutioner-machine - 通过自动扫描和解决拼图来使用乐高机器

为什么

手动解决拼图应该是一种放松的休闲活动。但当桌子上堆满了黑色碎片，你只能通过尝试将每个侧面与所有其他侧面配对，在2小时内解决4个连接点，这已经不再有趣。这个算法不考虑颜色，只关注单个碎片边界的形状，因此能够精确地解决这个问题。

它是如何工作的

它解析碎片图像的边界并找到四个角。现在你有四个侧面。然后，这些侧面与其他所有碎片的每个侧面进行比较，并按匹配概率进行排名。有了这些信息，解决器会尝试将所有碎片尽可能好地连接在一起。它是可原谅的，这意味着不完美的边界不会阻止正确的解决方案，因为切割刀片总会留下一些痕迹。我们不是在一个完美的世界中，边界总是完美的，但这不是问题。

可解决拼图的制造商/形式

目前该算法仅支持标准矩形拼图。尽管它设计成能够解决所有类型的矩形拼图，但目前只有 Ravensburger 拼图能够正确解决。这是因为 Ravensburger 给每个侧面提供了非常好且独特的形状。其他制造商使用的侧面形状太相似或甚至相同，因此此算法不适用于它们。

功能

BorderFinder: 解析图像，提取拼图边界的边界，并返回一个描述边界的点数组
SideFinder: 分析边界点并确定每个4个角的位置。返回包含每个侧面边界的4个数组。
PieceAnalyzer: 标准化侧面点（将它们旋转水平，将它们压平并分为100个均匀分布的点），为每个侧面生成分类器（是否是空隙在内部或外部，是否在左边或右边等），并返回一个拼图对象。
SideMatcher: 返回两个侧面之间匹配的概率，它们可以配合得多好。
PuzzleSolver: 解决拼图，并返回一个矩阵，其中每个碎片应该放置的位置以及正确的旋转。

用法

PieceAnalyzer

你需要拼图碎片的超高分辨率图像。它应该宽度为1000像素，其边界应该清晰可见。最佳实践：在拍摄图像时使用背光，使其成为黑白图像，使边界真正突出。

如果您想获取一个背景透明的图像（例如，用于显示与其他部件连接的地方），也请指定它。最佳实践：在同一位置拍摄部件的两个图像。第一个图像使用背光以更好地检测边缘，另一个图像使用正常光照使彩色部件透明。您可以请求多个图像变为透明，并且这些图像的大小不必与原始图像相同（10倍缩小后的透明图像更适合向用户展示解决方案，而不是原始的高清图像）。

use Bywulf\Jigsawlutioner\Service\BorderFinder\ByWulfBorderFinder;
use Bywulf\Jigsawlutioner\Service\SideFinder\ByWulfSideFinder;
use Bywulf\Jigsawlutioner\Service\PieceAnalyzer;

$borderFinder = new ByWulfBorderFinder();
$sideFinder = new ByWulfSideFinder();

$pieceAnalyzer = new PieceAnalyzer($borderFinder, $sideFinder);

$image = imagecreatefromjpeg('piece_blackwhite.jpg');
$transparentImage = imagecreatefromjpeg('piece_color.jpg');

$piece = $pieceAnalyzer->getPieceFromImage(1, $image, new ByWulfBorderFinderContext(
    threshold: 0.65,
    transparentImages: [$transparentImage],
));

成功时返回一个 Piece 对象。失败时抛出 JigsawlutionerException 异常。

$piece 中最重要的数据是 $piece->getBorderPoints()（指定图像边缘的点）和四个 $piece->getSides() 对象。

每个 Side 对象具有以下数据

$side->getPoints()：边的归一化点列表。它们被减少到100个等距的柔和点，然后水平旋转。
$side->getStartPoint()/$side->getEndPoint()：该边在图像上的角点位置。
$side->getClassifiers()：每个边由分类器描述。这些是简单的数字，可以与其他边进行比较，以查看两个边匹配的程度。

我们目前有以下分类器（SideClassifierInterface）

DirectionClassifier：包含信息，如果该边是直的（拼图边缘）或者是否有nop（DirectionClassifier::NOP_OUTSIDE）或孔（DirectionClassifier::NOP_INSIDE）。
BigWidthClassifier：nop/孔的最宽点在哪里以及有多宽
SmallWidthClassifier：nop/孔的最窄点在哪里以及有多宽
CornerDistanceClassifier：边的两个端点之间的距离
DepthClassifier：nop/孔有多深
LineDistanceClassifier：我们观察起点/终点和nop/孔的最小点之间的点。我们忽略前20%和最后20%。然后我们观察剩余的点，并计算到两个端点之间直线的最小、最大和平均距离。

ByWulfSolver

当您解析完所有部件后，您可以开始解拼图。首先生成所有边之间所有可能性的匹配映射。然后求解器将寻找解决方案

use Bywulf\Jigsawlutioner\Service\SideMatcher\WeightedMatcher;
use Bywulf\Jigsawlutioner\Service\MatchingMapGenerator;
use Bywulf\Jigsawlutioner\Service\PuzzleSolver\ByWulfSolver;

$sideMatcher = new WeightedMatcher();
$matchingMapGenerator = new MatchingMapGenerator($sideMatcher);
$matchingMap = $matchingMapGenerator->getMatchingMap($pieces);

$solver = new ByWulfSolver();
$solution = $solver->findSolution($pieces, $matchingMap);

成功时返回一个 Solution 对象。失败时抛出 JigsawlutionerException 异常。

解决方案将包含多个 $solution->getGroups()。每个部件连接区域一个。

每个 Group 有一个 $group->getPlacements() 列表。每个部件一个放置。

每个 Placement 有以下信息

$placement->getPiece()：在此放置中描述的部件
$placement->getX() / $placement->getY()：部件在组图案中的位置。一个单位表示一个部件行/列。
$placement->getTopSideIndex()：指定指向组顶部的部件的边数组索引（因此该部件必须旋转，以便此边位于顶部）。

部件识别器

如果您想在已扫描部件列表中找到新扫描的部件，您可以使用 PieceRecognizer 服务。

use Bywulf\Jigsawlutioner\Service\PieceRecognizer;

// $existingPieces = [...];
// $newlyScannedPiece = new Piece(...);

$recognizer = new PieceRecognizer();
$piece = $recognizer->findExistingPiece($newlyScannedPiece, $existingPieces);

返回的 $piece 是正确设置索引的克隆 $newlyScannedPiece，并且其边已重新排序，以便新扫描部件的第一个边与现有部件的第一个边匹配。

bywulf / jigsawlutioner

维护者

详细信息