Regularising Ill-posed Discrete Optimisation: Quests with P Systems

• Autorzy: Nicolescu R. , Gimel’farb G. , Morris J. , Delmas P. , Gong R.

Identyfikatory

DOI

10.3233/FI-2014-1026

• Języki publikacji: EN

Abstrakty

EN

We propose a novel approach to justify and guide regularisation of an ill-posed one-dimensional global optimisation with multiple solutions using a massively parallel (P system) model of the solution space. Classical optimisation assumes a well-posed problem with a stable unique solution. Most of important practical problems are ill posed due to an unstable or non-unique global optimum and are regularised to get a unique best-suited solution. Whilst regularisation theory exists largely for unstable unique solutions, its recommendations are often routinely applied to inverse optical problems with essentially non-unique solutions, e.g. computer stereo vision or image segmentation, typically formulated in terms of global energy minimisation. In these cases the recommended regularisation becomes purely heuristic and does not guarantee a unique solution. As a result, classical optimisation algorithms: dynamic programming (DP) and belief propagation (BP) – meet with difficulties. Our recent concurrent propagation (CP), leaning upon the P systems paradigm, extends DP and BP to always detect whether the problem is ill posed or not and store in the ill-posed case an entire space of solutions that yield the same global optimum. This suggests a radically new path to proper regularisation: select the best-suited unique solution by exploring statistical and structural features of this space. We propose a P systems based implementation of CP and set out as a case study an application of CP to the image matching problem in stereo vision.

Słowa kluczowe

EN

concurrent propagation; ill-posed problems; regularisation; multiple solutions; stereo matching; P systems; membrane computing; parallel and distributed computing models; actor model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 465--483
• Opis fizyczny: Bibliogr. 42 poz., rys.

Twórcy

autor

Nicolescu R.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Gimel’farb G.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Morris J.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Delmas P.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

autor

Gong R.

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

Bibliografia

• [1] Agha, G.: Actors: A Model of Concurrent Computation in Distributed Systems, MIT Press, 1986.
• [2] Bellman, R.: The theory of dynamic programming, Bulletin Amer. Math. Soc., 60, 1954, 503–516.
• [3] Bellman, R.: Dynamic Programming, Princeton University Press, 1957.
• [4] Bellman, R., Dreyfus, S. E.: Applied Dynamic Programming, Technical Report R-352-PR, RAND, 1962.
• [5] Bishop, C. M.: Pattern Recognition and Machine Learning, Springer, 2006.
• [6] Bleyer, M., Gelautz, M.: Simple but Effective Tree Structures for Dynamic Programming-Based Stereo Matching, Proc. Third Intern. Conf. on Computer Vision Theory and Applications (VISAPP), Funchal, Madeira, Portugal, January 2008.
• [7] Cormen, T. H., Stein, C., Rivest, R. L., Leiserson, C. E.: Introduction to Algorithms, 2nd edition, McGraw-Hill Higher Education, 2001.
• [8] Denardo, E. V.: Dynamic Programming: Models and Applications, Dover Publications, 2003.
• [9] Dreyfus, S. E., Law, A. M.: The Art and Theory of Dynamic Programming, Academic Press, 1977.
• [10] Elnakib, A., Gimel’farb, G., Suri, J. S., El-Baz, A.: Medical image segmentation: A brief survey, in: Multi-Modality State-of-the-Art Med. Image Segmentation and Registration Methodologies (A. El-Baz, R. A. U, A. F. Laine, J. S. Suri, Eds.), vol. 2, Springer Science+Business Media, 2011, 1–39.
• [11] Evgeniou, T., Poggio, T., Pontil, M., Verri, A.: Regularization and statistical learning theory for data analysis, Computational Statistics & Data Analysis, 18, 2002, 421–432.
• [12] Felzenszwalb, P., Zabih, R.: Dynamic Programming and Graph Algorithms in Computer Vision, IEEE Trans. Pattern Analysis and Machine Intelligence, 33(4), 2011, 721–740.
• [13] Felzenszwalb, P. F., Huttenlocher, D. P.: Efficient belief propagation for early vision, Intern. J. Computer Vision, 70, 2006, 41–54.
• [14] Frey, B.: Graphical Models for Machine Learning and Digital Communication, MIT Press, 1998.
• [15] Gheorghe, M., Păun, G., Rozenberg, G., Salomaa, A., Verlan, S., Eds.: Membrane Computing - 12th International Conference (CMC), Fontainebleau, France, August 2011, Revised Selected Papers, vol. 7184 of LNCS, Springer, 2012, ISBN 978-3-642-28023-8.
• [16] Gimel’farb, G.: Stereo terrain reconstruction by dynamic programming, in: Handbook of Computer Vision and Applications (B. J¨ahne, H. Haußecker, P. Geibler, Eds.), vol. 2, Academic Press, 1999, 505–530.
• [17] Gimel’farb, G.: Probabilistic regularisation and symmetry in binocular dynamic programming stereo, Pattern Recognition Letters, 23(4), 2002, 431–442.
• [18] Gimel’farb, G., Delmas, P., Morris, J., Shorin, A.: Robust face matching under large occlusions, Proc. 14th Intern. Conf. on Image Analysis and Processing (ICIAP), Modena, Italy, September 2007.
• [19] Gimel’farb, G., Gong, R., Nicolescu, R., Delmas, P.: Concurrent propagation for solving ill-posed problems of global discrete optimization, Proc. 21st Intern. Conf. on Pattern Recognition (ICPR), IAPR, Tsukuba, Japan, November 2012.
• [20] Gimel’farb, G., Morris, J., Delmas, P., Liu, J.: Stereo vision: Concurrent matching vs. optimisation, Proc. Image and Vision Computing New Zealand Conf. (IVCNZ), Great Barrier Island, New Zealand, November 2006.
• [21] Gimel’farb, G., Nicolescu, R., Ragavan, S.: P systems in stereo matching, Proc. 14th Int. Conf. on Computer Analysis of Images and Patterns (CAIP), 2, Springer, Seville, Spain, August 2011.
• [22] Gimel’farb, G., Nicolescu, R., Ragavan, S.: P system implementation of dynamic programming stereo, J. Math. Imaging and Vision, [Online: 18 July 2012; DOI10.1007/s10851-012-0367-6].
• [23] Hu, T., Qi, B., Wu, T., Xu, X., He, H.: Stereo matching using weighted dynamic programming on a single direction four-connected tree, Computer Vision and Image Understanding, 116(8), 2012, 908–921, ISSN 1077-3142.
• [24] Kalarot, R., Morris, J.: Comparison of FPGA and GPU implementations of real-time stereo vision, Proc. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition Workshops (CVPRW), San Francisco, CA, USA, June 2010.
• [25] Middlebury Stereo Vision Page, http://vision.middlebury.edu/stereo/, 2013.
• [26] Nicolescu, R.: Parallel and Distributed Algorithms in P Systems, in: Gheorghe et al. [15], 35–50.
• [27] Nicolescu, R., Gimel’farb, G.: Introduction to Concurrent Propagation, Report CDMTCS, Centre for Discrete Mathematics and Theoretical Computer Science, The University of Auckland, Auckland, New Zealand, September 2013, (in preparation).
• [28] Ogawara, K.: Approximate belief propagation by hierarchical averaging of outgoing messages, 20th Intern. IAPR Conf. on Pattern Recognition (ICPR), Istanbul, Turkey, August 2010.
• [29] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, 1968.
• [30] Păun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing, Oxford University Press, Inc., 2010.
• [31] Riemersma, T.: Color metric (CompuPhaseAutomatiserung, Bussum, The Netherlands), http://www.compuphase.com/cmetric.htm, 2011.
• [32] Scharstein, D., Szeliski, R.: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms, Intern. J. Computer Vision, 47(1–3), 2002, 7–42.
• [33] Scharstein, D., Szeliski, R.: High-accuracy stereo depth maps using structured light, Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 1, Madison, WI, USA, June 2003.
• [34] Sniedovich, M.: Dynamic Programming: Foundations and Principles, CRC Press, 2009.
• [35] Sun, J., Li, Y., Kang, S. B., Shum, H.-Y.: Symmetric stereo matching for occlusion handling, IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR), 2, San Diego, CA, USA, June 2005.
• [36] Sun, J., Zheng, N., Shum, H.: Stereo matching using belief propagation, IEEE Trans. Pattern Analysis and Machine Intelligence,, 25(7), 2003, 787–800.
• [37] Tikhonov, A. N., Goncharsky, A. V., Stepanov, V. V., Yagola, A. G.: Numerical Methods for the Solution of Ill-Posed Problems, Kluwer Academic Publishers, 1995.
• [38] Waterman, M. S., Byers, T. H.: A dynamic programming algorithm to find all solutions in a neighborhood of the optimum, Math. BioSciences, 77, 1985, 179–188.
• [39] Wikipedia: General-purpose computing on graphics processing units — Wikipedia, The Free Encyclopedia, 2013, [Online; accessed 15-July-2013].
• [40] Wilf, H. S.: Generatingfunctionology, 3rd edition, A. K. Peters, Ltd., 2006.
• [41] Yang, Q., Wang, L., Ahuja, N.: A constant-space belief propagation algorithm for stereo matching, Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, USA, June 2010.
• [42] Yedidia, J. S., Freeman, W. T., Weiss, Y.: Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Trans. Information Theory, 51, 2005, 2282–2312.