Просматривается номер   2018-S1
To the readers
About journal
Publication Ethics
Requirements for papers
Topics
Review Process
English (United Kingdom)Russian (CIS)
Data mining and image recognition
N.S. Skoryukina, A.N. Milovzorov, D.V. Polevoy, V.V. Arlazarov Paintings recognition in uncontrolled conditions using one-shot learning
A.E. Zhukovsky Methods for interframe integration of document detection results in a video stream of a mobile device
I.A. Kunina, E. I. Panfilova, M.A. Povolotskiy Zebra-crossing detection on road images using dynamic time warping
O.A. Slavin, V.L. Arlazarov Method for classifying recognized pages of administrative documents on the basis of text key points
O.O. Petrova, K.B. Bulatov Methods of machine-readable zone recognition results post-processing
A.E. Marchenko, E.I. Ershov, D.A. Shepelev, D.S. Sidorchuk, V.P. Bozhkova, D.P. Nikolaev Designing of language of description of observable properties of recognized objects in the absence of samples
Intellectual systems and technologies
E.E. Limonova, N.L. Rzhenev, A.V. Uskov, M.I. Neiman-zade Fast implementation of Hamming distance on VLIW-architectures on the example of Elbrus platform
V.V. Arlazarov, K.B. Bulatov, A.V. Uskov A model of object recognition system in video stream of a mobile device
A.A. Ivanova, S.A. Gladilin, A.E. Zhukovsky, E.L. Pliskin Database for the administrative accounting of scientific publications
A.S. Ingacheva, A.V. Sheshkus, T. S. Chernov, E.E. Limonova, V.V. Arlazarov X-ray computed tomography scanner – a new tool in recognition
N.O. Beshaposhnikov, A.G. Kushnirenko, A.A. Levin A method for auto-calibration of the educational robot control parameters using computer vision library OpenCV
Image and signal processing
A.E. Zhukovsky, E.E. Limonova, D.P. Nikolaev Exact implementation of common image processing algorithms using fully convolutional networks
V.E. Prun Reducing the influence of high-absorbing inclusions on CT reconstructions using algebraic reconstruction technique
B.I. Savelyev, I.B. Mamay, D.P. Nikolaev, V.L. Arlazarov, K.B. Bulatov, N.S. Skoryukina A method of projective transformations graph adjustment for panorama stitching problem for images of planar objects
D.V. Tropin, D.P. Nikolaev, D.G. Slugin The method of image alignment based on sharpness maximization
J.A. Shemiakina, A.E. Zhukovsky, I.A. Konovalenko, D.P. Nikolaev Algorithm for automatic framing of digital images under projective transformation
MACHINE LEARNING
A.V. Gayer, A.V. Sheshkus, Y.S. Chernyshova Augmentation on the fly for the neural networks learning
V.V. Arlazarov, D.P. Matalov, S.A. Usilin Localization of the seal on the identity document image using machine learning approach
A.E. Lynchenko, A.V.Sheshkus, V.L.Arlazarov Identity document classifiaction algorithm based on similarity metric robust to projective distortions
V.A. Malykh, V.A. Lyalin On Classification of Noisy Texts
Y.S. Chernyshova, M.A. Aliev, A.V. Sheshkus Optical font recognition of images captured with mobile devices and its application for detecting identity documents forgery
D.A. Ilin Fast words boundaries localization in text fields for low quality document images
D.E. Ivanov, D.V. Polevoy, D.L. Sholomov Selection of informative elements for the training of a lightweight convolutional neural network classifier in the conditions of a strong imbalance of the training sample
E.E. Limonova, N.L. Rzhenev, A.V. Uskov, M.I. Neiman-zade Fast implementation of Hamming distance on VLIW-architectures on the example of Elbrus platform

Abstract.

In this work we show fast implementation of Hamming Distance on Elbrus platform with VLIWarchitecture. We introduce and examine experimentally key features of Elbrus architecture such as availability of several arithmetic and logic units working in parallel, special features of memory access, presence of array prefetch buffer and other opportunities for parallel execution. These features allow us to significantly rise computational performance of Hamming distance computation. The implementation considering the characteristics appeared to be 11.5 times faster than the basic implementation for large enough arrays. Besides, considered techniques of improving computational performance for Elbrus processors are not specific for this algorithm and can be used for a number of other data processing methods.

Keywords:

Hamming distance, VLIW-architecture, Elbrus processor.

PP. 65-72.

DOI: 10.14357/20790279180507

References

1. Ray, J., & Koopman, P. (2006, June). Efficient high Hamming distance CRCs for embedded networks. In Dependable Systems and Networks, 2006. DSN 2006. International Conference on (pp. 3-12). IEEE.
2. Hamming, R.W. (1950). Error detecting and error correcting codes. Bell Labs Technical Journal, 29(2), 147-160.
3. Rigas, I., Economou, G. and Fotopoulos, S. (2015). Efficient modeling of visual saliency based on local sparse representation and the use of hamming distance. Computer Vision and Image Understanding, 134, 33-45.
4. Revathy, S. and Ramasethu, M.L. (2016). Face and IRIS recognition in a video sequence using DBPNN and adaptive Hamming Distance.
5. Fakhfakh, S., Tmar, M. and Mahdi, W. (2015). Image Retrieval Based on Using Hamming Distance. Procedia Computer Science, 73, 320-327.
6. Li, W., & Packard, N. (1990). The structure of the elementary cellular automata rule space. Complex systems, 4(3), 281-297.
7. Souza, J.W.G., Pereira, H.B.B., Santos, A.A.B., Senna, V., & Moret, M.A. (2014). A new proposal for analyzing combustion process stability based on the Hamming distance. Physica A: Statistical Mechanics and its Applications, 413, 301-306.
8. Ghani, R. (2000, June). Using error-correcting codes for text classification. In ICML (pp. 303-310).
9. Ruan, Y., Xue, X., Liu, H., Tan, J., & Li, X. (2017). Quantum Algorithm for K-Nearest Neighbors Classification Based on the Metric of Hamming Distance. International Journal of Theoretical Physics, 56(11), 3496-3507.
10. Norouzi, M., Fleet, D.J., & Salakhutdinov, R.R. (2012). Hamming distance metric learning. In Advances in neural information processing systems (pp. 1061-1069).
11. Xin, H., Greth, J., Emmons, J., Pekhimenko, G., Kingsford, C., Alkan, C., & Mutlu, O. (2015). Shifted Hamming distance: a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping. Bioinformatics, 31(10), 1553-1560.
12. Sood, S., & Loguinov, D. (2011, October). Probabilistic near-duplicate detection using simhash. In Proceedings of the 20th ACM international conference on Information and knowledge management (pp. 1117-1126). ACM.
13. Kaiser, M., Pilz, S., Porrmann, F., Hagemeyer, J., & Porrmann, M. (2018). Accelerating Hamming Distance Comparisons for Locality Sensitive Hashing (LSH) using FPGAs. In 12th CeBiTec Symposium-Big Data in Medicine and Biotechnology-Abstract Book(Vol. 12).
14. E. Kuznetsova et al. Viola-Jones based hybrid framework for real-time object detection in multispectral images. In Proceedings of ICMV 2015, SPIE, vol. 9875, publ. code 98750N, pp. 1-6, 2015, DOI: 10.1117/12.2228707.
15. N. Skoryukina et al. Real Time Rectangular Document Detection on Mobile Devices. In Proceedings ICMV 2014, SPIE, 2015, vol. 9445, publ. code 94452A, pp. 1-6, 2015, DOI: 10.1117/12.2181377.
16. N. Skoryukina et al. Snapscreen: TV-stream frame search with projectively distorted and noisy query. Proc. SPIE 10341, ICMV 2016, 10341 ed., Antanas Verikas, Ed., Ninth International Conference on Machine Vision, 2017, vol. 10341, ISBN 978-15-10611-32-0, publ. code 103410Y, pp. 1-5, 2017, DOI: 10.1117/12.2268735.
17. N.A. Bocharov et al. Optimization for the Elbrus computing architecture of the modified method of Viola and Jones. Trudy ISA RAN, vol. 67, no 4, pp. 10-21, 2017.
18. Limonova E.E., Bocharov N.A., Paramonov N.B., Bogdanov D.S., Arlazarov V.V., Slavin O.A., Nikolaev D.P. Recognition system efficiency evaluation on VLIW architecture on the example of Elbrus platform // Programming and Computer Software (in print)
19. Hirvola, T. (2016). Bit-parallel approximate string matching under Hamming distance.
20. Muła, W., Kurz, N., & Lemire, D. (2017). Faster population counts using AVX2 instructions. The Computer Journal, 61(1), 111-120.
21. Kim A.K., Bychkov I.N. Russian Technologies “Elbrus” for personal computers, servers and supercomputers // Modern Information Technologies and IT Education, Moscow: Foundation for the Promotion of Internet Media, IT Education, Human Capacity “League of Internet Media”, 2014, No. 10. 39-50.
22. Kim A.K., Perekatov V.I., Ermakov S.G. Microprocessors and computing systems of the Elbrus family. – SPb: Peter, 2013. – 272 С.
23. Porpodas, V., & Jones, T.M. (2015, October). Throttling automatic vectorization: When less is more. In Parallel Architecture and Compilation (PACT), 2015 International Conference on (pp. 432-444). IEEE.
 
     
2024-74-1
2023-73-4
2023-73-3
2023-73-2

© ФИЦ ИУ РАН 2008-2018. Создание сайта "РосИнтернет технологии".