In manual puzzling, one generally decides on the basis of a large number of features whether two pieces fit together or not (shape, color, pattern, etc.). In larger puzzles, this comparison is not done randomly within the total set of all puzzle pieces, but in smaller subsets with pieces that are “similar” with respect to certain features.
The digital puzzle methodology in our automated assistance systems.
The methodical approach of digital puzzling is structurally comparable to the manual approach of solving an “ordinary puzzle”. Accordingly, the puzzle workflow implemented in our automated assistance systems is divided into the following sub-processes:
- Feature calculation: Image processing and pattern recognition methods are used to automatically calculate a variety of characteristic features of the fragments.
- Clustering: Based on the fragment characteristics, the total set of all fragments is automatically grouped (“clustered”). Each cluster contains a reduced number of potential puzzle candidates with similar features compared to the total set.
- Matching: Within the clusters, the actual puzzling (“matching”) takes place by evaluating pairwise comparisons. In this process, the features of all pairings of a cluster are automatically compared for matching. This comparison is fuzzy, because usually even very accurate matching parts do not match 100% with respect to their features.
- The result of each comparison is a set of scores that quantify the degree of match of a pairing.
- If the scores of a pairing are within defined score ranges, the corresponding pairing is automatically classified as matching and otherwise as non-matching.
- Merging: Matching pairings are digitally glued (“merged”).
- The resulting partial reconstructions are perceived as new puzzle pieces in the subsequent process and automatically (further) puzzled within their clusters.
- All reconstructions identified (automatically or manually) as complete are grouped into a set of finished reconstructions.
- The sub-processes feature calculation, clustering, matching and merging are repeated automatically until either no more matching pairings are found during matching or all reconstructions of the cluster are marked as finished.