Afullyautomatedgreedysquarejigsawpuzzlesolver资源-CSDN下载

需积分: 10 7 浏览量 2012-03-07 15:34:36 上传评论收藏 2.04MB PDF 举报

### 完全自动贪婪式方形拼图求解器的关键知识点 #### 一、研究背景与问题定义在方形拼图问题中，目标是通过一系列非重叠且无序的方形拼图块重构出完整的图像。该问题不仅是休闲娱乐中的常见挑战，同时也具有重要的科学价值，尤其是在生物学、分子学、考古学以及图像编辑等多个领域有着广泛的应用。 #### 二、现有工作与研究动机早期的计算机拼图求解器主要依赖于形状特征进行拼图匹配，如1964年Freeman和Garder提出的解决方案只能处理九个拼图块的问题。随着时间的发展，基于形状的求解器已经可以解决超过200个拼图块的情况。然而，这些方法通常需要关于拼图块位置的线索或对原始图像的部分先验知识，这限制了它们在实际应用中的灵活性和通用性。 #### 三、研究贡献本研究提出了一种全新的全自动贪婪式方形拼图求解器，其主要特点在于： 1. **无需任何先验信息**：与以往的方法不同，本方法假设没有关于拼图块位置的任何线索，也不需要关于原始图像或其简化版本（如低分辨率图像）的先验知识。 2. **结合智能放置与重新排列**：该求解器结合了基于信息的拼图块放置策略和拼图片段的重新排列算法，从而能够有效地找到最终解决方案。 3. **新的兼容性度量**：为更准确地预测两个给定拼图块是否相邻，研究者引入了新的兼容性度量标准。这些度量标准能够更好地反映拼图块之间的相似性和匹配程度。 4. **创新的评估方法**：开发了一种新颖的评估措施，能够在不依赖真实解的情况下评价拼图解决方案的质量。这种无监督的评估方法极大地扩展了该求解器的应用范围。 5. **超越现有技术水平**：通过整合上述贡献，该求解器能够解决比以往尝试过的更大的拼图问题，并在解决大尺寸拼图方面取得了超越现有技术水平的成果。 #### 四、关键技术细节 1. **全自动求解流程**：该求解器完全自动化运行，用户只需提供一组拼图块，而无需任何其他输入或干预。 2. **贪婪算法**：采用贪婪策略选择最有可能的拼图块进行放置，以逐步构建拼图的完整图像。 3. **兼容性度量**：通过分析拼图块边缘的颜色、纹理等特征来计算相邻拼图块的兼容性得分。 4. **质量评估**：开发了一套基于拼图内部一致性的评估体系，用于判断当前解决方案的合理性。 #### 五、结论与未来展望本文介绍的全自动贪婪式方形拼图求解器在多个方面实现了技术突破，不仅提高了拼图问题解决的效率和准确性，而且拓宽了其应用场景。未来的研究方向可能包括进一步优化兼容性度量方法、探索更多种类的拼图问题以及将该技术应用于更多的实际场景中。

资源推荐

资源详情

资源评论

A fully automated greedy square jigsaw puzzle solver

Dolev Pomeranz Michal Shemesh Ohad Ben-Shahar

[email protected] [email protected] [email protected]

Computer Science Department, Ben-Gurion University of The Negev, Beer Sheva, Israel

Abstract

In the square jigsaw puzzle problem one is required to re-

construct the complete image from a set of non-overlapping,

unordered, square puzzle parts. Here we propose a fully au-

tomatic solver for this problem, where unlike some previous

work, it assumes no clues regarding parts’ location and re-

quires no prior knowledge about the original image or its

simpliﬁed (e.g., lower resolution) versions. To do so, we

introduce a greedy solver which combines both informed

piece placement and rearrangement of puzzle segments to

ﬁnd the ﬁnal solution. Among our other contributions are

new compatibility metrics which better predict the chances

of two given parts to be neighbors, and a novel estima-

tion measure which evaluates the quality of puzzle solutions

without the need for ground-truth information. Incorporat-

ing these contributions, our approach facilitates solutions

that surpass state-of-the-art solvers on puzzles of size larger

than ever attempted before.

1. Introduction

The popular jigsaw puzzle problem exists for many cen-

turies, long before it was ﬁrst solved by a computer in

the 20th century. Given n jigsaw puzzle parts of an im-

age, it is required to reconstruct the complete image. Al-

though phrased as a game, this problem, which was proved

to be NP-complete [2, 7], serves a platform for many ap-

plications, e.g. in biological [14], molecular [22], text and

speech [12, 25], archaeological contexts [3, 10], and image

editing [4].

The traditional jigsaw puzzle problem assumes pieces of

various shapes, and indeed earlier computational work con-

sidered the problem in this form. The ﬁrst jigsaw solver

proposed by Freeman and Garder in 1964 [8] was designed

to solve apictorial puzzles and was able to handle nine-piece

problems. By the end of the century, shaped-based solvers

were already able to reconstruct puzzles of more than 200

pieces [9]. The use of appearance and chromatic informa-

tion began only three decades after the work of Freeman

and Garder (e.g., [11, 6, 21, 24, 23, 13, 15]).

A major building block in most appearance-based puzzle

solvers evaluate the similarity between two parts, and the

strategies for doing so typically divide into two groups. One

approach compares the appearance of the abutting bound-

aries while using a formal distance measure between these

two vectors (e.g., [11, 6, 21, 24, 13, 15]). Alternatively, it

was suggested to use the entire part and measure its statis-

tical properties in order to group similar parts together [15]

or as a means to deﬁne pairwise similarity measures [11].

Once the similarity between two parts is estimated, differ-

ent classes of algorithms are employed to solve the puz-

zle, and in particular, previous methods have used greedy

algorithms [7, 15], dynamic programming [1], genetic al-

gorithms [21] and approximation algorithms on graphical

models [5].

Recently, Cho et al. [5] presented a probabilistic solver

which achieves approximated puzzle reconstruction via a

graphical model and a probability function that is maxi-

mized via loopy belief propagation. Since they lack a local

evidence term required for their graphical model, they em-

ployed two strategies that exploit prior knowledge - either

a dense-and-noisy evidence which estimates the low reso-

lution image from a bag of parts, or a sparse-and-accurate

evidence which assumes that a few parts, called “anchor

patches”, are given by an oracle (e.g., a human observer)

at their correct location in the puzzle. While only semi-

automatic, their approach was seminal in its ability to han-

dle puzzles with over 400 pieces.

In this paper we challenge the state-of-the-art in jigsaw

puzzle solving in several ways. We suggest a computational

framework that can handle in reasonable time square jigsaw

puzzles of size larger than ever attempted before. How-

ever, we completely exclude the use of clues, oracles, or

human intervention, as well as any use of prior knowledge

about the original image or simpliﬁed (e.g., lower resolu-

tion) versions of it. Despite these signiﬁcant restrictions,

our approach achieves better than state-of-the-art perfor-

mance, and frequently succeeds in providing completely ac-

curate puzzle solutions.

Our puzzle solving framework is based on a greedy

solver, which works in several phases. First a compatibility

function is computed to measure the afﬁnity between two

neighboring parts (as often done in other solvers as well).

Then the solver solves three problems - the placement prob-

lem, the segmentation problem, and the shifting problem.

The placement module places all parts on the board in an in-

formed fashion, the segmentation module identiﬁes regions

which are likely to be assembled correctly, and the shift-

ing module relocates regions and parts to produce the ﬁnal

result.

Our main contribution is a fully automated solver which

uses no clues, hints, or other prior knowledge whatsoever.

In addition, our contributions also include the proposal of

new and better compatibility metrics, as well as the intro-

duction of the concept of an estimation metric which evalu-

ates the quality of a given solution without any reference to

the original, ground-truth image. As we show, these metrics

become a critical tool that facilitates self evaluation in case

when no clues or prior knowledge are available. In what fol-

lows we ﬁrst discuss these, as well as the rest of the metrics

involved in the solver.

2. Metrics

2.1. Compatibility Metrics

A compatibility metric is at the foundation of every jig-

saw solver. Given two puzzle parts x

, x

and a possible

spatial relation R between them, the compatibility function

predicts the likelihood that these two parts are indeed placed

as neighbors with relation R in the correct solution. With

R ∈ {l, r, u, d}, we use C(x

, x

, R) to denote the compat-

ibility that part x

is placed on either of the left, right, up,

or down side of part x

, respectively.

Optimally, one would wish to ﬁnd a metric C such that

C(x

, x

, R) = 1 iff part x

is located to the R side of x

in the original image and 0 otherwise. If such a function

exists, the jigsaw puzzle problem could be solved in poly-

nomial time by a greedy algorithm [7]. Motivated by the

above, we ﬁrst discuss how one can measure the accuracy

of a compatibility function and then seek a compatibility

function C which is as accurate and discriminative as pos-

sible.

Measuring Compatibility Accuracy: In order to compare

between compatibility metrics, we denote the classiﬁcation

criterion as the ratio between correct placements and the to-

tal number of possible placements. Similar to Cho et al. [5],

we deﬁne the correct placement of parts x

and x

accord-

ing to the compatibility metric C if part x

is in relation R

to part x

in the original image and if

∀x

∈ P arts, C(x

, x

, R) ≥ C(x

, x

, R) . (1)

Recently, Cho et al. [5] evaluated ﬁve compatibility met-

rics, among which the dissimilarity-based compatibility

metric showed to be the most discriminative. Inspired by

both the dissimilarity-based metric and the characteristics

of natural images, we propose two new types of compatibil-

ity metrics, which will be described shortly after we review

the dissimilarity-based compatibility metric.

Dissimilarity-based Compatibility: The dissimilarity be-

tween two parts x

, x

can be measured by summing up the

squared color differences of the pixels along the parts’ abut-

ting boundaries [5]. For example, if we represent each color

image part in normalized LAB space by a K ×K ×3 matrix

(where K is the part width/height in pixels) then the dissim-

ilarity between parts x

and x

, where x

is to the right of

, can be deﬁned as

D(x

, x

, r) =

k=1

d=1

(k, K, d) − x

(k, 1, d))

. (2)

We do emphasize that dissimilarity is not a distance mea-

sure, i.e., D(x

, x

, R) is not necessarily the same as (and

almost always different than) D(x

, x

, R).

Although the dissimilarity-based metric was shown to be

the most discriminative among the tested metrics in Cho et

al. [5], the observation that it is related to the L

norm of

the boundaries’ difference vector suggests that other norms

of the same difference vector could behave even better. In-

spired by the use of non Euclidean norms in image opera-

tions such as noise removal [19] or diffusion [20], and by

the observation that the L

norm penalizes large boundary

differences very severely even though such large differences

do exist in natural images, we evaluated other L

norms as

well. The average accuracy empirical results for the dis-

similarity metric based on various L

norms are shown in

Fig. 1 and indicate clearly that the L

is suboptimal, and

that the best results may be obtained with L

norms with

p ≈ 0.3. While this is outside the scope of this paper, an

interesting question that emerges from this data is why does

performance break down for small p values, and why does

p ≈ 0.3 appear to provide optimal performance (see the

Discussion and Future Work section).

0.5 1 1.5 2 2.5 3

0.2

0.4

0.6

0.8

X: 0.3

Y: 0.8648

p−Value

Clasification Accuracy

Figure 1. Comparing dissimilarity-based metrics using different

norms. For this test we used a database of 20 test images [5],

and analyzed each for the portion of correct part pairs that received

the highest compatibility score among other candidates. The plot

depicts the average classiﬁcation accuracy of 20 images and shows

how performance peaks at p ≈ 0.3, with a value of 86%.

)

Compatibility: As mentioned before, the optimal

剩余7页未读，继续阅读

评论收藏

内容反馈

azxzdxx

粉丝: 1

A fully automated greedy square jigsaw puzzle solver

greed-puzzle-solver

PuzzleSolver

Solver

Solver tool

Greedy algorithm

利用A*, greedy, Dijkstra, RRT算法，针对迷宫障碍物栅格地图，采用8连接方法，找一 条从起始点到目标点的无

GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE

Greedy Layer-Wise Training

论文研究-A Fast Greedy Algorithm for Outlier Mining.pdf

Greedy Function Approximation A Gradient Boosting Machine.pdf

greedy algorithm

Zolver：自动拼图解决方案

PuzzleSolver:解决难题

greedy_c源程序

Greedy算法经典问题的解答

Greedy Snake.zip

Greedy-Snake_贪吃蛇

GreedySnake.zip

[C++]Greedy Snake

Greedy Arithmetic

Greedy function approximation - A gradient boosting machine (1).pdf

GREEDY FUNCTION APPROXIMATION- A GRADING BOOSTING MACHINE.pdf

greedysnake贪吃蛇小游戏

Greedy Snake

Greedy-Snake.rar

计算机 贪心greedy算法 ppt

贪心法（The Greedy Method）ppt

GREEDY ALGORITHMS IN DATALOG

BFS, DFS, Dijkstra, Greedy Best First Search, A*五种路径规划算法Python实现

A Greedy, Graph-Based Algorithm

【Android】短信验证码输入框（80/100）

powebi同步切片器失效不可用

最新资源

利用A*, greedy, Dijkstra, RRT算法，针对迷宫障碍物栅格地图，采用8连接方法，找一条从起始点到目标点的无

计算机贪心greedy算法 ppt