Actas de congresos
Solving Image Puzzles With A Simple Quadratic Programming Formulation
Registro en:
9780769548296
Brazilian Symposium Of Computer Graphic And Image Processing. , v. , n. , p. 63 - 70, 2012.
15301834
10.1109/SIBGRAPI.2012.18
2-s2.0-84872386451
Autor
Andalo F.A.
Taubin G.
Goldenstein S.
Institución
Resumen
We present a new formulation to automatically solve jigsaw puzzles considering only the information contained on the image. Our formulation maps the problem of solving a jigsaw puzzle to the maximization of a constrained quadratic function that can be solved by a numerical method. The proposed method is deterministic and it can handle arbitrary rectangular pieces. We tested the validity of the method to solve problems up to 3300 puzzle pieces, and we compared our results to the current state-of-the-art, obtaining superior accuracy. © 2012 IEEE.
63 70 Demaine, E., Demaine, M., Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity (2007) Graphs and Combinatorics, 23, pp. 195-208 Justino, E., Oliveira, L.S., Freitas, C., Reconstructing shredded documents through feature matching (2006) Forensic Science International, 160 (2-3), pp. 140-147. , DOI 10.1016/j.forsciint.2005.09.001, PII S0379073805004913 McBride, J., Kimia, B., Archaeological fragment reconstruction using curve-matching (2003) Conference on Computer Vision and Pattern Recognition Workshop. (CVPRW), 1, pp. 3-3 Freeman, H., Garder, L., Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition (1964) IEEE Transactions on Electronic Computers, (2), pp. 118-127 Goldberg, D., Malon, C., Bern, M., A global approach to automatic solution of jigsaw puzzles (2002) Proceedings of the Annual Symposium on Computational Geometry, pp. 82-87 Kosiba, D., Devaux, P., Balasubramanian, S., Gandhi, T., Kasturi, K., An automatic jigsaw puzzle solver (1994) Proceedings of the 12th International Conference on Pattern Recognition (IAPR), 1, pp. 616-618 Nielsen, T., Drewsen, P., Hansen, K., Solving jigsaw puzzles using image features (2008) Pattern Recognition Letters, 29 (14), pp. 1924-1933 Cho, T., Avidan, S., Freeman, W., A probabilistic image jigsaw puzzle solver (2010) Conference on Computer Vision and Pattern Recognition (CVPR), pp. 183-190 Pomeranz, D., Shemesh, M., Ben-Shahar, O., A fully automated greedy square jigsaw puzzle solver (2011) IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9-16 Seneta, E., (2006) Non-negative Matrices and Markov Chains, , Springer Verlag Rosen, J., The gradient projection method for nonlinear programming. Part I. linear constraints (1960) Journal of the Society for Industrial and Applied Mathematics, 8 (1), pp. 181-217