cvpr cvpr2013 cvpr2013-11 knowledge-graph by maker-knowledge-mining

11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles


Source: pdf

Author: Dror Sholomon, Omid David, Nathan S. Netanyahu

Abstract: In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.

Reference: text


Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 i l Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel Abstract In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. [sent-8, score-0.834]

2 We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. [sent-9, score-0.549]

3 The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. [sent-10, score-0.704]

4 We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers. [sent-12, score-0.788]

5 Introduction The problem domain of jigsaw puzzles is widely known to almost every human being from childhood. [sent-14, score-0.605]

6 Given n different non-overlapping pieces of an image, the player has to reconstruct the original image, taking advantage of both the shape and chromatic information of each piece. [sent-15, score-0.375]

7 [10] have noted, the jigsaw puzzle problem may and should be researched for the sole reason that it stirs pure interest. [sent-19, score-0.773]

8 (a)(b) (c)(d) Figure 1: Jigsaw puzzles before and after reassembly using our genetic algorithm-based solver. [sent-25, score-0.354]

9 We believe these puzzles, of 10,375 (a-b) and 22,834 pieces (c-d), to be the largest automatically solved to date. [sent-26, score-0.375]

10 [4] presented a probabilistic puzzle solver that could handle up to 432 pieces, given some a priori knowledge of the puzzle. [sent-29, score-0.568]

11 [17] introduced that year, for the first time, a fully automated square jigsaw puzzle solver that could handle puzzles of up to 3,000 pieces. [sent-33, score-1.174]

12 Gallagher [9] has advanced this even further by considering a more general variant of the problem, where neither piece orientation nor puzzle dimensions are known. [sent-34, score-0.866]

13 In its most basic form, every puzzle solver requires an estimation function to evaluate the compatibility of adjacent pieces and a strategy for placing the pieces (as accurately as possible). [sent-35, score-1.388]

14 Interestingly, despite the availability of puzzle solvers for 3,000- and 9,000-piece puzzles, there exists no image set, for the purpose of benchmark testing, containing puzzles with more then 805 pieces. [sent-46, score-0.834]

15 We assume that similarly to the case of the smaller images, the accuracy of current solvers on some large puzzles could be greatly increased by using more sophisticated algorithms. [sent-49, score-0.332]

16 In this paper we harness the powerful technique of genetic algorithms (GAs) [11] as a strategy for piece placement. [sent-50, score-0.445]

17 First and foremost, we present a significantly more accurate solver of the original jigsaw variant with known piece orientation and puzzle dimensions. [sent-54, score-1.243]

18 Our solver compromises neither speed nor size as it outperforms state-ofthe-art solvers, successfully tackling up to 22,834-piece size puzzles (more than twice the number of pieces ever attempted/reported) within a reasonable time frame. [sent-55, score-0.77]

19 Also, we share all of our results (on this benchmark and other public datasets) for future testing and comparative evaluation of jigsaw puzzle solvers. [sent-58, score-0.793]

20 Finally, we provide for the first time an effective GA-based puzzle solver, which should benefit research regarding the area of evolutionary computation (EC), in general, and the jigsaw puzzle problem, in particular. [sent-59, score-1.255]

21 As to the jigsaw puzzle problem, our proposed framework could prove useful for solving more advanced variants, such as puzzles with missing pieces, unknown piece orientation, and more. [sent-61, score-1.465]

22 The success of a GA is mainly dependent on choosing an appropriate chromosome representation, crossover operator, and fitness function. [sent-80, score-0.542]

23 The chromosome representation and crossover operator must allow the merge of two good solutions to an even better solution. [sent-81, score-0.498]

24 GA-based puzzle solver A basic GA framework for solving the jigsaw puzzle problem is given by the pseudocode of Algorithm 1. [sent-84, score-1.37]

25 In our case, a chromosome is an arrangement, or placement, of all the jigsaw puzzle pieces. [sent-86, score-0.983]

26 In every generation the entire population is evaluated using a fitness function (described below), and a new population is (re)produced by the selection of and crossover application to chromosome pairs. [sent-88, score-0.795]

27 The probability of selecting a certain chromosome by the method is directly proportionate to the value of its fitness function, as required. [sent-90, score-0.382]

28 The fitness function The fitness function (described below) is evaluated for all chromosomes for the purpose of selection. [sent-96, score-0.422]

29 In our GA, each chromosome represents a complete solution to the jigsaw puzzle problem (see Subsection 3. [sent-97, score-1.017]

30 The problem variant at hand assumes no knowledge whatsoever of the original image and thus, the correctness of the absolute location of puzzle pieces cannot be estimated in a simple manner. [sent-101, score-0.878]

31 We refer to a measure which predicts the likelihood of two pieces to be adjacent in the original image as compatibility. [sent-103, score-0.395]

32 Given two puzzle pieces xi, xj and a spatial relation between them R ∈ {l, r, u, d}, C(xi, xj , dR a) dpeantioatle rse tahtieo nco bmetpwaetiebnili tthye mof R R pi ∈ece { xj uw,hde}n, placed to the left, right, up or down side of piece xi, respectively. [sent-105, score-1.412]

33 The dissimilarity measure relies on the premise that adjacent jigsaw pieces in the original image tend to share similar colors along their abutting edges, and thus, the sum (over all neighboring pixels) of squared color differences (over all color bands) should be minimal. [sent-111, score-0.726]

34 Assuming pieces xi, xj are represented in normalized L*a*b* space by a K K 3 matrreisxe, nwtehder ine nKo rism tahleiz zheedig Lh*ta/w*ibd*th s poafc ae p biyec ae K K(in × ×pi Kxel ×s), 3 th meairdissimilarity where xj is to the right of xi, for example, is D(xi,xj,r) =? [sent-112, score-0.469]

35 Since every chromosome in every generation must be evaluated, a fitness function must be relatively computationally-inexpensive. [sent-123, score-0.436]

36 ×× Finally, the fitness function of a given chromosome is the sum of pairwise dissimilarities over all neighboring pieces (whose configuration is represented by the chromosome). [sent-126, score-0.733]

37 M ×)M Mc)or mreastproixn,d ws htoe ae single puzzle piece, we define its fitness as ? [sent-131, score-0.63]

38 1 Problem definition As noted above, given a puzzle (image) of (N M) pieces, aA sch norotemdo asboomvee may n be a preuzpzrelese (nitmedag e by) afn ( N(N × ×M )M p)i cmeas-, atrix ch, eoamcho entry mofa yw bheich re pcorersreenstpeodnd bsy t aon na ( Npiec ×e Mnum) bmear. [sent-154, score-0.502]

39 (A piece is assigned a number according to its initial location in the given puzzle. [sent-155, score-0.384]

40 A naive crossover operator with respect to the given representation will create a new child chromosome at random, such that each entry of the resulting matrix is the correspond- ing cell of the first or second parent. [sent-160, score-0.536]

41 This approach yields usually a child chromosome with duplicate and/or missing puzzle pieces, which makes of course an invalid solution to the problem. [sent-161, score-0.775]

42 Recall, crossover is applied to two chromosomes selected due to their high fitness values, where the fitness function used is an overall pairwise compatibility measure of adjacent puzzle pieces. [sent-164, score-1.137]

43 At best, the function rewards a correct placement of neighboring pieces next to each other, but it has no way of identifying the correct absolute location of a piece. [sent-165, score-0.529]

44 Since the population starts out from a random piece placement and then gradually improves, it is reasonable to assume that over the generations some correctly assembled puzzle segments will emerge. [sent-166, score-1.106]

45 the ability of 111777666977 (a) Parent1(b) Parent2(c) 10 Pieces(d) 70 Pieces (e) 180 Pieces(f) 258 Pieces(g) 304 Pieces(h) Child Figure 2: Illustration of crossover operation: Given (a) Parent1 and (b) Parent2, (c) (g) depict how a kernel of pieces is gradually grown until (h) a complete child. [sent-171, score-0.591]

46 Note the detection of parts of the tower in both parents, which are then shifted and merged to the complete tower; shifting of images during kernel growing is due to piece position independence. [sent-172, score-0.45]

47 two complete (different) arrangements of all puzzle pieces, the crossover operator constructs a child chromosome in a kernel-growing fashion, using both parents as ”consultants”. [sent-184, score-1.172]

48 The operator starts with a single piece and gradually joins other pieces at available boundaries. [sent-185, score-0.854]

49 New pieces may be joined only adjacently to existing pieces, so that the emerging image is always contiguous. [sent-186, score-0.375]

50 The operator keeps adding pieces from a bank of available pieces until there are no more pieces left. [sent-187, score-1.203]

51 Hence, every piece will appear exactly once in the resulting image. [sent-188, score-0.405]

52 Thus, by using every piece exactly once inside of a frame of the correct size, the operator is guaranteed of achieving a valid image. [sent-190, score-0.527]

53 A key trait of the kernel-growing technique is the fact that the final absolute location of every piece is determined only once the kernel reaches its final size and the child chromosome is complete. [sent-192, score-0.748]

54 Until that point, all pieces might be shifted, depending the kernel’s growth vector. [sent-193, score-0.398]

55 The first piece, for example, might eventually be located at the lowerleft corner of the image, should the kernel grow only to the up and to the right, after this piece was assigned. [sent-194, score-0.407]

56 Instead, the same first piece might ultimately be located at the center of the image, upper-right corner, or any other location. [sent-195, score-0.407]

57 This change in the absolute location of each piece is illustrated in Figure 2, especially between phase (f) and phase (g) of the kernel-growing process, as all pieces are shifted to the right due to insertion of new pieces on the left. [sent-196, score-1.277]

58 Now remains the question of which piece to select from the available pieces bank and where to locate it in the child. [sent-198, score-0.759]

59 a partial image, we can mark all the boundaries where a new piece might be placed. [sent-201, score-0.407]

60 A piece boundary is denoted by a pair (xi, R), consisting of the piece number and a spatial relation. [sent-202, score-0.788]

61 First, given all existing boundaries, the operator checks whether there exists a piece boundary for which both parents agree on a piece xj (meaning, both contain this piece in the spatial direction R of xi). [sent-204, score-1.487]

62 If such a piece exists, then it is placed in the correct location. [sent-205, score-0.428]

63 If the parents agree on two or more boundaries, one of them is chosen at random and the respective piece is assigned. [sent-206, score-0.558]

64 Obviously, an already used piece cannot be (re)assigned, so any such piece is ignored as if the parents did not agree on that particular boundary. [sent-207, score-0.942]

65 If there is no agreement between the parents on any piece at any boundary, the second phase begins. [sent-208, score-0.567]

66 [17]; two pieces are said to be best-buddies if each piece considers the other as its most compatible piece. [sent-210, score-0.796]

67 The pieces 111777667088 xi and xj are said to best-buddies if ∀xk ∈ Pieces, C(xi, , R1) ≥ C(xi, xk , R1) and ∀xp ∈ Pieces, C(xj , xi , R2) ≥ C(xj , xp, R2) xj (3) where Pieces is the set of all given image pieces and R1 and R2 are ”complementary” spatial relations (e. [sent-211, score-0.902]

68 In the second phase the operator checks whether one of the parents contains a piece xj in spatial relation R of xi which is also a best-buddy of xi in that relation. [sent-214, score-0.78]

69 As before, if multiple best-buddy pieces are available, one is chosen at random. [sent-216, score-0.375]

70 If a best-buddy piece is found but was already assigned, it is ignored and the search continues for other best-buddy pieces. [sent-217, score-0.384]

71 Finally, if no best-buddy piece exists, the operator randomly selects a boundary and assigns it the most compatible piece available. [sent-218, score-0.903]

72 To introduce mutation in the first and last phase the operator places, with low probability, an available piece at random, instead of the most compatible relevant piece available. [sent-219, score-0.969]

73 In summary, the operator uses repeatedly a three-phase procedure of piece selection and assignment, placing first agreed pieces, followed by best-buddy pieces and finally by the most compatible piece available (i. [sent-220, score-1.331]

74 The procedure returns to the first phase after every piece assignment due to the prospective creation of new boundaries. [sent-224, score-0.449]

75 – Algorithm 2 Crossover operator simplified 1: If any available boundary meets the criterion of Phase 1 (both parents agree on a piece), place the piece there and goto (1); otherwise continue. [sent-226, score-0.724]

76 2: If any available boundary meets the criterion of Phase 2 (one parent contains a best-buddy piece), place the piece there and goto (1); otherwise continue. [sent-227, score-0.514]

77 3: Randomly choose a boundary, place the most compatible available piece there and goto (1). [sent-228, score-0.467]

78 Here, since position independence of pieces is encouraged, the trait of interest is captured by a piece’s set of neighbors. [sent-232, score-0.438]

79 Correct puzzle segments correspond to a correct placement of pieces next to each other. [sent-233, score-0.969]

80 The notion that piece xi is in spatial relation R to piece xj is key to solving the jigsaw problem. [sent-234, score-1.164]

81 Taking into account the random nature of the first generation, the procedure must actively seek the better traits of piece relations. [sent-236, score-0.426]

82 Since a kernel-growing algorithm is used, some agreed pieces might ”prematurely” serve as most compatible pieces at another boundary and be subsequently disqualified for later use. [sent-240, score-0.872]

83 Another option might be to just choose the most compatible piece in a greedy manner, or check if a best-buddy piece is available. [sent-243, score-0.853]

84 Since piece placement in parents might be random and since even best-buddy pieces might not capture the correct match, we combine the two. [sent-244, score-1.033]

85 The fact that two pieces are both best-buddies and are adjacent at a parent is a good indication for the validity of this match. [sent-245, score-0.437]

86 The direct method has been repeatedly denounced [17] as being both less accurate and less meaningful due to its inability to cope with slightly shifted puzzle solutions. [sent-254, score-0.562]

87 Note that a piece arrangement scoring 100% according to one of the methods is, by defi- × nition, the full reconstruction of the original image and will also achieve a score of 100% when measured by the other method. [sent-256, score-0.402]

88 The population consists of 1000 111777667199 (a)(b)(c)(d) Figure 3: Shifted puzzle solutions. [sent-260, score-0.573]

89 The rest of the population is generated by the crossover operator described earlier with a mutation rate of 5%. [sent-266, score-0.395]

90 Our solver gains a significant improvement of up to 21% (for the 540-piece puzzle set); for some puzzles, the improvement was even 30%. [sent-281, score-0.568]

91 (Note that the latter two puzzle sizes have never been solved before. [sent-285, score-0.482]

92 and worst runs for puzzles with less than 22,834 pieces, and since this difference seemed to decrease for larger puzzles, we ran the GA only twice on each 22,834-piece puzzle. [sent-312, score-0.378]

93 The first row shows: (a) 5,015-piece puzzle and the best chromosome achieved by the GA in the (b) first, (c) second, and (d) last generation. [sent-315, score-0.692]

94 The accuracy of all puzzle solutions shown is 100%. [sent-317, score-0.508]

95 5 hours for solving a 9,600-pieces puzzle, although he allows also for piece rotation. [sent-342, score-0.399]

96 Discussion and future work In this paper we presented an automatic jigsaw puzzle solver, far more accurate than any existing solver and capable of reconstructing puzzles of up to 22,834 pieces (more than twice the number of pieces ever achieved). [sent-357, score-1.918]

97 We have achieved the first effective genetic algorithmbased solver, which appears to challenge state-of-the-art performance of other jigsaw puzzle solvers. [sent-359, score-0.834]

98 A fully automated greedy square jigsaw puzzle solver MATLAB code and images. [sent-474, score-0.906]

99 A 2s,se 6,m 7bly of puzzles using a genetic algorithm. [sent-498, score-0.354]

100 A puzzle solver and its application in speech descrambling. [sent-522, score-0.568]


similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('puzzle', 0.482), ('piece', 0.384), ('pieces', 0.375), ('puzzles', 0.293), ('jigsaw', 0.291), ('chromosome', 0.21), ('crossover', 0.184), ('ga', 0.181), ('fitness', 0.148), ('parents', 0.139), ('pomeranz', 0.136), ('chromosomes', 0.126), ('population', 0.091), ('solver', 0.086), ('operator', 0.078), ('child', 0.064), ('genetic', 0.061), ('trait', 0.048), ('shredded', 0.047), ('xj', 0.047), ('gas', 0.046), ('placement', 0.045), ('phase', 0.044), ('correct', 0.044), ('agreed', 0.042), ('generations', 0.042), ('mutation', 0.042), ('traits', 0.042), ('parent', 0.042), ('dissimilarity', 0.04), ('solvers', 0.039), ('cho', 0.037), ('compatible', 0.037), ('runs', 0.037), ('generation', 0.036), ('sholomon', 0.035), ('nathan', 0.035), ('agree', 0.035), ('shifted', 0.034), ('goto', 0.031), ('worst', 0.031), ('xi', 0.029), ('compatibility', 0.029), ('reproduction', 0.027), ('solutions', 0.026), ('greedy', 0.025), ('dror', 0.024), ('offspring', 0.024), ('offsprings', 0.024), ('piecespomeranz', 0.024), ('proportionate', 0.024), ('roulette', 0.024), ('segments', 0.023), ('might', 0.023), ('automated', 0.022), ('documents', 0.022), ('assembled', 0.022), ('supplied', 0.022), ('gallagher', 0.022), ('meets', 0.022), ('absolute', 0.021), ('every', 0.021), ('netanyahu', 0.021), ('shemesh', 0.021), ('noted', 0.02), ('benchmark', 0.02), ('boundary', 0.02), ('adjacent', 0.02), ('documented', 0.019), ('toyama', 0.019), ('solution', 0.019), ('copied', 0.018), ('placements', 0.018), ('arrangement', 0.018), ('goldberg', 0.017), ('terminated', 0.017), ('wheel', 0.017), ('passed', 0.017), ('gradually', 0.017), ('attempted', 0.017), ('repeatedly', 0.017), ('tower', 0.017), ('ran', 0.017), ('pi', 0.016), ('ever', 0.016), ('assembly', 0.016), ('checks', 0.016), ('year', 0.016), ('direct', 0.015), ('pages', 0.015), ('solving', 0.015), ('complete', 0.015), ('place', 0.015), ('independence', 0.015), ('issue', 0.015), ('sets', 0.015), ('inability', 0.014), ('pseudocode', 0.014), ('relation', 0.014), ('selection', 0.014)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999964 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles

Author: Dror Sholomon, Omid David, Nathan S. Netanyahu

Abstract: In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.

2 0.183634 52 cvpr-2013-Axially Symmetric 3D Pots Configuration System Using Axis of Symmetry and Break Curve

Author: Kilho Son, Eduardo B. Almeida, David B. Cooper

Abstract: Thispaper introduces a novel approachfor reassembling pot sherds found at archaeological excavation sites, for the purpose ofreconstructing claypots that had been made on a wheel. These pots and the sherds into which they have broken are axially symmetric. The reassembly process can be viewed as 3D puzzle solving or generalized cylinder learning from broken fragments. The estimation exploits both local and semi-global geometric structure, thus making it a fundamental problem of geometry estimation from noisy fragments in computer vision and pattern recognition. The data used are densely digitized 3D laser scans of each fragment’s outer surface. The proposed reassembly system is automatic and functions when the pile of available fragments is from one or multiple pots, and even when pieces are missing from any pot. The geometric structure used are curves on the pot along which the surface had broken and the silhouette of a pot with respect to an axis, called axisprofile curve (APC). For reassembling multiple pots with or without missing pieces, our algorithm estimates the APC from each fragment, then reassembles into configurations the ones having distinctive APC. Further growth of configurations is based on adding remaining fragments such that their APC and break curves are consistent with those of a configuration. The method is novel, more robust and handles the largest numbers of fragments to date.

3 0.13568354 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median

Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu

Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.

4 0.048271894 73 cvpr-2013-Bringing Semantics into Focus Using Visual Abstraction

Author: C. Lawrence Zitnick, Devi Parikh

Abstract: Relating visual information to its linguistic semantic meaning remains an open and challenging area of research. The semantic meaning of images depends on the presence of objects, their attributes and their relations to other objects. But precisely characterizing this dependence requires extracting complex visual information from an image, which is in general a difficult and yet unsolved problem. In this paper, we propose studying semantic information in abstract images created from collections of clip art. Abstract images provide several advantages. They allow for the direct study of how to infer high-level semantic information, since they remove the reliance on noisy low-level object, attribute and relation detectors, or the tedious hand-labeling of images. Importantly, abstract images also allow the ability to generate sets of semantically similar scenes. Finding analogous sets of semantically similar real images would be nearly impossible. We create 1,002 sets of 10 semantically similar abstract scenes with corresponding written descriptions. We thoroughly analyze this dataset to discover semantically important features, the relations of words to visual features and methods for measuring semantic similarity.

5 0.047022946 72 cvpr-2013-Boundary Detection Benchmarking: Beyond F-Measures

Author: Xiaodi Hou, Alan Yuille, Christof Koch

Abstract: For an ill-posed problem like boundary detection, human labeled datasets play a critical role. Compared with the active research on finding a better boundary detector to refresh the performance record, there is surprisingly little discussion on the boundary detection benchmark itself. The goal of this paper is to identify the potential pitfalls of today’s most popular boundary benchmark, BSDS 300. In the paper, we first introduce a psychophysical experiment to show that many of the “weak” boundary labels are unreliable and may contaminate the benchmark. Then we analyze the computation of f-measure and point out that the current benchmarking protocol encourages an algorithm to bias towards those problematic “weak” boundary labels. With this evidence, we focus on a new problem of detecting strong boundaries as one alternative. Finally, we assess the performances of 9 major algorithms on different ways of utilizing the dataset, suggesting new directions for improvements.

6 0.040577885 248 cvpr-2013-Learning Collections of Part Models for Object Recognition

7 0.036529645 349 cvpr-2013-Reconstructing Gas Flows Using Light-Path Approximation

8 0.036138292 114 cvpr-2013-Depth Acquisition from Density Modulated Binary Patterns

9 0.035457533 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential

10 0.034591071 103 cvpr-2013-Decoding Children's Social Behavior

11 0.03321581 26 cvpr-2013-A Statistical Model for Recreational Trails in Aerial Images

12 0.032152075 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision

13 0.032077894 391 cvpr-2013-Sensing and Recognizing Surface Textures Using a GelSight Sensor

14 0.031461302 340 cvpr-2013-Probabilistic Label Trees for Efficient Large Scale Image Classification

15 0.029503759 123 cvpr-2013-Detection of Manipulation Action Consequences (MAC)

16 0.028842585 373 cvpr-2013-SWIGS: A Swift Guided Sampling Method

17 0.026101269 218 cvpr-2013-Improving the Visual Comprehension of Point Sets

18 0.023896692 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus

19 0.023385119 386 cvpr-2013-Self-Paced Learning for Long-Term Tracking

20 0.022252334 143 cvpr-2013-Efficient Large-Scale Structured Learning


similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.069), (1, 0.01), (2, 0.0), (3, 0.003), (4, 0.021), (5, 0.002), (6, -0.005), (7, 0.0), (8, -0.018), (9, 0.0), (10, 0.001), (11, -0.001), (12, -0.017), (13, -0.021), (14, -0.03), (15, -0.004), (16, 0.014), (17, 0.017), (18, 0.023), (19, 0.006), (20, -0.023), (21, 0.025), (22, -0.016), (23, 0.004), (24, 0.037), (25, 0.004), (26, 0.013), (27, -0.021), (28, 0.012), (29, 0.028), (30, -0.003), (31, 0.0), (32, 0.019), (33, 0.001), (34, 0.04), (35, 0.025), (36, -0.001), (37, 0.024), (38, 0.023), (39, 0.017), (40, -0.022), (41, 0.019), (42, 0.005), (43, 0.097), (44, 0.015), (45, 0.037), (46, 0.017), (47, -0.054), (48, -0.02), (49, -0.04)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.85105354 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles

Author: Dror Sholomon, Omid David, Nathan S. Netanyahu

Abstract: In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.

2 0.67424345 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median

Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu

Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.

3 0.61189622 52 cvpr-2013-Axially Symmetric 3D Pots Configuration System Using Axis of Symmetry and Break Curve

Author: Kilho Son, Eduardo B. Almeida, David B. Cooper

Abstract: Thispaper introduces a novel approachfor reassembling pot sherds found at archaeological excavation sites, for the purpose ofreconstructing claypots that had been made on a wheel. These pots and the sherds into which they have broken are axially symmetric. The reassembly process can be viewed as 3D puzzle solving or generalized cylinder learning from broken fragments. The estimation exploits both local and semi-global geometric structure, thus making it a fundamental problem of geometry estimation from noisy fragments in computer vision and pattern recognition. The data used are densely digitized 3D laser scans of each fragment’s outer surface. The proposed reassembly system is automatic and functions when the pile of available fragments is from one or multiple pots, and even when pieces are missing from any pot. The geometric structure used are curves on the pot along which the surface had broken and the silhouette of a pot with respect to an axis, called axisprofile curve (APC). For reassembling multiple pots with or without missing pieces, our algorithm estimates the APC from each fragment, then reassembles into configurations the ones having distinctive APC. Further growth of configurations is based on adding remaining fragments such that their APC and break curves are consistent with those of a configuration. The method is novel, more robust and handles the largest numbers of fragments to date.

4 0.55593085 193 cvpr-2013-Graph Transduction Learning with Connectivity Constraints with Application to Multiple Foreground Cosegmentation

Author: Tianyang Ma, Longin Jan Latecki

Abstract: The proposed approach is based on standard graph transduction, semi-supervised learning (SSL) framework. Its key novelty is the integration of global connectivity constraints into this framework. Although connectivity leads to higher order constraints and their number is an exponential, finding the most violated connectivity constraint can be done efficiently in polynomial time. Moreover, each such constraint can be represented as a linear inequality. Based on this fact, we design a cutting-plane algorithm to solve the integrated problem. It iterates between solving a convex quadraticproblem of labelpropagation with linear inequality constraints, and finding the most violated constraint. We demonstrate the benefits of the proposed approach on a realistic and very challenging problem of cosegmentation of multiple foreground objects in photo collections in which the foreground objects are not present in all photos. The obtained results not only demonstrate performance boost induced by the connectivity constraints, but also show a significant improvement over the state-of-the-art methods.

5 0.54241633 72 cvpr-2013-Boundary Detection Benchmarking: Beyond F-Measures

Author: Xiaodi Hou, Alan Yuille, Christof Koch

Abstract: For an ill-posed problem like boundary detection, human labeled datasets play a critical role. Compared with the active research on finding a better boundary detector to refresh the performance record, there is surprisingly little discussion on the boundary detection benchmark itself. The goal of this paper is to identify the potential pitfalls of today’s most popular boundary benchmark, BSDS 300. In the paper, we first introduce a psychophysical experiment to show that many of the “weak” boundary labels are unreliable and may contaminate the benchmark. Then we analyze the computation of f-measure and point out that the current benchmarking protocol encourages an algorithm to bias towards those problematic “weak” boundary labels. With this evidence, we focus on a new problem of detecting strong boundaries as one alternative. Finally, we assess the performances of 9 major algorithms on different ways of utilizing the dataset, suggesting new directions for improvements.

6 0.53745025 106 cvpr-2013-Deformable Graph Matching

7 0.52486527 127 cvpr-2013-Discovering the Structure of a Planar Mirror System from Multiple Observations of a Single Point

8 0.48596185 240 cvpr-2013-Keypoints from Symmetries by Wave Propagation

9 0.48396218 214 cvpr-2013-Image Understanding from Experts' Eyes by Modeling Perceptual Skill of Diagnostic Reasoning Processes

10 0.48033151 350 cvpr-2013-Reconstructing Loopy Curvilinear Structures Using Integer Programming

11 0.47838777 80 cvpr-2013-Category Modeling from Just a Single Labeling: Use Depth Information to Guide the Learning of 2D Models

12 0.47817051 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs

13 0.47777894 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach

14 0.47652948 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus

15 0.45148608 103 cvpr-2013-Decoding Children's Social Behavior

16 0.4498049 218 cvpr-2013-Improving the Visual Comprehension of Point Sets

17 0.44466963 129 cvpr-2013-Discriminative Brain Effective Connectivity Analysis for Alzheimer's Disease: A Kernel Learning Approach upon Sparse Gaussian Bayesian Network

18 0.4418309 183 cvpr-2013-GRASP Recurring Patterns from a Single View

19 0.438728 416 cvpr-2013-Studying Relationships between Human Gaze, Description, and Computer Vision

20 0.43255353 351 cvpr-2013-Recovering Line-Networks in Images by Junction-Point Processes


similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(10, 0.105), (16, 0.021), (26, 0.037), (33, 0.186), (59, 0.384), (67, 0.043), (69, 0.04), (87, 0.055)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.74187672 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles

Author: Dror Sholomon, Omid David, Nathan S. Netanyahu

Abstract: In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.

2 0.65065205 276 cvpr-2013-MKPLS: Manifold Kernel Partial Least Squares for Lipreading and Speaker Identification

Author: Amr Bakry, Ahmed Elgammal

Abstract: Visual speech recognition is a challenging problem, due to confusion between visual speech features. The speaker identification problem is usually coupled with speech recognition. Moreover, speaker identification is important to several applications, such as automatic access control, biometrics, authentication, and personal privacy issues. In this paper, we propose a novel approach for lipreading and speaker identification. Wepropose a new approachfor manifold parameterization in a low-dimensional latent space, where each manifold is represented as a point in that space. We initially parameterize each instance manifold using a nonlinear mapping from a unified manifold representation. We then factorize the parameter space using Kernel Partial Least Squares (KPLS) to achieve a low-dimension manifold latent space. We use two-way projections to achieve two manifold latent spaces, one for the speech content and one for the speaker. We apply our approach on two public databases: AVLetters and OuluVS. We show the results for three different settings of lipreading: speaker independent, speaker dependent, and speaker semi-dependent. Our approach outperforms for the speaker semi-dependent setting by at least 15% of the baseline, and competes in the other two settings.

3 0.62778616 316 cvpr-2013-Optical Flow Estimation Using Laplacian Mesh Energy

Author: Wenbin Li, Darren Cosker, Matthew Brown, Rui Tang

Abstract: In this paper we present a novel non-rigid optical flow algorithm for dense image correspondence and non-rigid registration. The algorithm uses a unique Laplacian Mesh Energy term to encourage local smoothness whilst simultaneously preserving non-rigid deformation. Laplacian deformation approaches have become popular in graphics research as they enable mesh deformations to preserve local surface shape. In this work we propose a novel Laplacian Mesh Energy formula to ensure such sensible local deformations between image pairs. We express this wholly within the optical flow optimization, and show its application in a novel coarse-to-fine pyramidal approach. Our algorithm achieves the state-of-the-art performance in all trials on the Garg et al. dataset, and top tier performance on the Middlebury evaluation.

4 0.61583561 298 cvpr-2013-Multi-scale Curve Detection on Surfaces

Author: Michael Kolomenkin, Ilan Shimshoni, Ayellet Tal

Abstract: This paper extends to surfaces the multi-scale approach of edge detection on images. The common practice for detecting curves on surfaces requires the user to first select the scale of the features, apply an appropriate smoothing, and detect the edges on the smoothed surface. This approach suffers from two drawbacks. First, it relies on a hidden assumption that all the features on the surface are of the same scale. Second, manual user intervention is required. In this paper, we propose a general framework for automatically detecting the optimal scale for each point on the surface. We smooth the surface at each point according to this optimal scale and run the curve detection algorithm on the resulting surface. Our multi-scale algorithm solves the two disadvantages of the single-scale approach mentioned above. We demonstrate how to realize our approach on two commonly-used special cases: ridges & valleys and relief edges. In each case, the optimal scale is found in accordance with the mathematical definition of the curve.

5 0.61578298 112 cvpr-2013-Dense Segmentation-Aware Descriptors

Author: Eduard Trulls, Iasonas Kokkinos, Alberto Sanfeliu, Francesc Moreno-Noguer

Abstract: In this work we exploit segmentation to construct appearance descriptors that can robustly deal with occlusion and background changes. For this, we downplay measurements coming from areas that are unlikely to belong to the same region as the descriptor’s center, as suggested by soft segmentation masks. Our treatment is applicable to any image point, i.e. dense, and its computational overhead is in the order of a few seconds. We integrate this idea with Dense SIFT, and also with Dense Scale and Rotation Invariant Descriptors (SID), delivering descriptors that are densely computable, invariant to scaling and rotation, and robust to background changes. We apply our approach to standard benchmarks on large displacement motion estimation using SIFT-flow and widebaseline stereo, systematically demonstrating that the introduction of segmentation yields clear improvements.

6 0.56722414 456 cvpr-2013-Visual Place Recognition with Repetitive Structures

7 0.55934781 92 cvpr-2013-Constrained Clustering and Its Application to Face Clustering in Videos

8 0.5255034 52 cvpr-2013-Axially Symmetric 3D Pots Configuration System Using Axis of Symmetry and Break Curve

9 0.517398 297 cvpr-2013-Multi-resolution Shape Analysis via Non-Euclidean Wavelets: Applications to Mesh Segmentation and Surface Alignment Problems

10 0.51241016 248 cvpr-2013-Learning Collections of Part Models for Object Recognition

11 0.51062626 284 cvpr-2013-Mesh Based Semantic Modelling for Indoor and Outdoor Scenes

12 0.51039225 141 cvpr-2013-Efficient Computation of Shortest Path-Concavity for 3D Meshes

13 0.51001692 414 cvpr-2013-Structure Preserving Object Tracking

14 0.50851774 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking

15 0.50799805 325 cvpr-2013-Part Discovery from Partial Correspondence

16 0.50782174 408 cvpr-2013-Spatiotemporal Deformable Part Models for Action Detection

17 0.50763053 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation

18 0.5074563 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities

19 0.50625378 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases

20 0.50603759 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection