Control Systems and Computers, N2, 2018, Article 4
DOI: https://doi.org/10.15407/usim.2018.02.031
Upr. sist. maš., 2018, Issue 2 (274), pp. 31-41.
UDK 519.245
Ye.V. Vodolazskiy, Senior researcher, waterlaz@gmail.com,
S.A. Latiuk, Engineer-programmer of 1-st category, serhiylatyuk55@gmail.com,
International Research and Training Center for Information Technologies and Systems of the National Academy of
Sciences (NAS) of Ukraine and Ministry of Education and Science (MES) of Ukraine
BLOCKING MODIFICATION OF GIBBS SAMPLING FOR RECOGNITION OF HIDDEN MARKOV FIELDS
Introduction. This paper is dedicated to demonstration of the fact that blocking Gibbs sampling can be constructively implemented and applied to solve the image recognition tasks, in particular — for solving the labelling problems, to which some Computer Vision problems can be reduced. It’s known, that these problems are optimization problems with the big number of the discrete arguments. The specificity of these tasks lies in the fact that function, which we want to optimize is the sum of a large number of terms, each of which depends on a few arguments. Tasks of such type are NP-hard, and polynomially solvable subclasses include very small number of situations that can happen in practice. So, there is a need to explore approximate methods for solving such problems. One of these methods is Gibbs sampling. There is no sense to apply Gibbs sampling in all recognition tasks, but it can be used in situations with some special loss functions for the statistical estimation of some quantities.
Purpose of this paper is to demonstrate that blocking Gibbs sampling can be constructively implemented for solving image recognition problems. Secondly, we want to compare blocking modification with standard algorithm and find types of the textures, on which blocking modification will give better results. And, finally, we want to test validity of the proposed method for estimation of expectation.
Methods. Blocking modification of Gibbs sampling for image recognition is built on the principles of dynamic programming. Software that allows to generate images of the given texture, choose proper modification of Gibbs sampling for solving the problem and show graphs using Python and Cython.
Results. Blocking Gibbs sampling works better then standard realization, when images for recognition has so-called «monotonous» texture. In case of recognition the images with so-called «diagonal» texture (that very often arises in practice) blocking modification works not worse than standard method. It was also noticed that proposed method for estimation of expectation works a little better than the standard one.
Conclusion. Blocking Gibbs sampling can be applied for the solving image recognition tasks. It has constructive implementation which works in polynomial time. Asymptotically, one iteration of blocking Gibbs sampling is performing slower than one iteration of the standard Gibbs sampling algorithm. But in our experiments recognition at all (on «monotonous» textures) was performing faster with blocking algorithm. Due to this fact, we can conclude that blocking modification is able to take into consideration some additional information that allows to perform the recognition faster. So, it makes sense to do further research in this field.
Download full text! (In Russian).
Keywords: Gibbs sampling, Gibbs sampler, labelling problems, hidden Markov fields recognition.
REFERENCES
1. Geman, S., Geman, D., 1984. “Stochastic relaxation, gibbs distributions, and the bayesian restoration of images”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (6), pp. 721–741. https://doi.org/10.1109/TPAMI.1984.4767596
2. Schlesinger, M.I., 1976. “Syntactic analysis of two-dimensional visual signals in conditions of interference”. Cybernetics. 4. pp. 113-130.(In Russian).
3. Schlesinger, M.I., Flach, B., 2000. “Some solvable subclass of structural recognition problems”. Czech Pattern Recognition Workshop, Praha: Czech Pattern Recognition Society, Feb. 2000, pp. 55–62.
4. Schlesinger, M., Flach, B., 2002. “Analyzis of optimal labelling problems and their applications to image segmentation and binocular stereovision”. Proc. East-West-Vision 2002 (EWV’02). International Workshop and Project Festival on Computer Vision, Computer Graphics, New Media, pp. 55–60.
5. Schlesinger, M., Hlavac V., 2002. Ten Lectures on Statistical and Structural Pattern Recognition. Dordrecht: Computational Imaging and Vision Kluwer Academic Publishers, 522 p. https://doi.org/10.1007/978-94-017-3217-8
Received 06.07.2018
