A Parallel Architecture for Improving the Performance of the Kriging Algorithm

Year 2023, Volume: 15 Issue: 2, 463 - 471, 14.07.2023

Özgür Tamer , Ahmet Esat Genç

https://doi.org/10.29137/umagd.1165147

Abstract

Estimating missing data values by using interpolation algorithms is a well-known technique. Kriging is an optimized interpolation method based on regression against evaluated values from the surrounding observation points, weighted according to spatially varying values according to the covariance between these observation points. It has been widely used for estimating the missing geological data of the areas based on the measurements in close proximity. In this work we use the Kriging to recover the missing pixels of digital images. Even though Kriging is considered as successful on estimating the missing pixels, the algorithm has a high operation load, causing delays especially for live streaming videos. In this paper we propose a parallel architecture to improve the performance and reduce the operation time of the Kriging Algorithm for estimating the missing pixels. The proposed method can be applied on Field Programmable Gate Arrays (FPGA) and considerable performance improvement have been achieved depending on the number of logic blocks available inside the FPGA.

Keywords

Kriging algorithm, parallel architectures, interpolation, image reconstruction, FPGA

Kriging Algoritmasının Performansının İyileştirilmesi için Paralel bir Mimari

Abstract

Veri matrislerinde bulunan eksik değerlerin enterpolasyon algoritmaları kullanarak tahmin edilmesi yaygın olarak kullanılan bir yöntemdir. Bir enterpolasyon algoritması olan Kriging, bu gözlem noktaları arasındaki kovaryansa göre uzamsal olarak değişen değerlere göre ağırlıklandırılan, çevredeki gözlem noktalarından elde edilen değerlere karşı regresyona dayalı olarak optimize edilmesine dayanmaktadır. Özellikle Jeofizik alanında yakın çevredeki ölçümlere dayalı olarak alanların eksik jeolojik verilerinin tahmininde yaygın olarak kullanılmaktadır. Bu çalışmada, dijital görüntülerin eksik piksellerini kurtarmak için Kriging algoritması paralel bir mimari üzerinde kullanılmaktadır. Kriging, eksik pikselleri tahmin etmede başarılı olarak kabul edilse de, algoritmanın yüksek bir işlem yüküne sahip olması, özellikle canlı akışlı videolar için gecikmelere neden olmaktadır. Çalışmamızda ise, eksik pikselleri tahmin etmek için Kriging Algoritmasının performansını iyileştirmek ve çalışma süresini azaltmak için paralel bir mimari öneriyoruz. Önerilen yöntem, Alanda Programlanabilir Kapı Dizileri (FPGA) üzerinde uygulanabilmektedir ve FPGA içinde bulunan mantık bloklarının sayısına bağlı olarak önemli performans iyileştirmeleri sağlanmıştır.

Keywords

Kriging Algoritması, paralel mimariler, interpolasyon, görüntü tekrar inşası, FPGA

References

• Bayer, B. E. (1976). Color Imaging Array (Patent No. US3971065A).
• Bohling, G. (2005). Kriging. Kansas Geological Survey, October, 1–20. https://doi.org/10.2104/ag050010
• Bonaventura, L., Castruccio, S., Laboratorio, M. O. X., Matematica, D., & Milano, P. (2005). Random notes on kriging : an introduction to geostatistical interpolation for environmental applications.
• Chernetskiy, M., Tao, Y., & Muller, J.-P. (2019). 3D stereo reconstruction: high resolution satellite video. Https://Doi.Org/10.1117/12.2533226, 11155, 582–593. https://doi.org/10.1117/12.2533226
• Güvendik, C., Esat Genç, A., Tamer, Ö., & Nil, M. (2012). Improving the performance of Kriging based interpolation application with parallel processors | Kriging temelli̇ aradeǧerleme uygulamasinda paralel i̇şlemci̇ler i̇le başariminin i̇yi̇leş ti̇ri̇lmesi̇. 2012 20th Signal Processing and Communications Applications Conference, SIU 2012, Proceedings. https://doi.org/10.1109/SIU.2012.6204645
• Hagstrom, B. L., & Yfantis, E. A. (1994). Performance of Multi-Bus, Multi-Memory Systems Using Variable Miss Ratio. Int. Conf. on Computing and Information, 831–846.
• Han, R., Liu, X., Liao, S., Li, Y., Qi, Z., Fu, S., Li, Y., & Han, H. (2021). Adaptive image inpainting algorithm based on sample block by kriging pretreatment and facet model. Https://Doi.Org/10.1117/1.JEI.30.4.043021, 30(4), 043021. https://doi.org/10.1117/1.JEI.30.4.043021
• He, F., Fang, J., & Zou, W. (2011). An effective method for interpolation. Proceedings - 2011 19th International Conference on Geoinformatics, Geoinformatics 2011. https://doi.org/10.1109/GeoInformatics.2011.5980762
• Johnston, K., Ver Hoef, J. M., Krivoruchko, K., & Lucas, N. (2003). The principles of geostatistical analysis. Using ArcGIS Geostatistical Analyst, 49–80. Lagadapati, Y., Shirvaikar, M., & Dong, X. (2015). Fast semivariogram computation using FPGA architectures. Https://Doi.Org/10.1117/12.2077851, 9400, 40–49. https://doi.org/10.1117/12.2077851
• Li, M., & Dong, L. (2011). Visualization three-dimensional geological modeling using CUDA. Proceedings - 6th International Conference on Image and Graphics, ICIG 2011, 852–857. https://doi.org/10.1109/ICIG.2011.94
• Maciej Wielgosz Mauritz Panggabean, L. A. R. (2013). FPGA Architecture for Kriging Image Interpolation. International Journal of Advanced Computer Science and Applications(IJACSA), 4(12), 193–201. http://ijacsa.thesai.org/
• Miklós, P. (2004). Image interpolation techniques. 2nd Siberian-Hungarian Joint Symposium On Intelligent Systems. 2004., 1–6.
• Panagiotopoulou, A., & Anastassopoulos, V. (2007). Super-resolution image reconstruction employing Kriging interpolation technique. 2007 IWSSIP and EC-SIPMCS - Proc. 2007 14th Int. Workshop on Systems, Signals and Image Processing, and 6th EURASIP Conf. Focused on Speech and Image Processing, Multimedia Communications and Services, 144–147. https://doi.org/10.1109/IWSSIP.2007.4381174
• Panggabean, M., Tamer, O., & Rønningen, L. A. (2011). Parallel image transmission and compression using windowed kriging interpolation. 2010 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2010. https://doi.org/10.1109/ISSPIT.2010.5711801
• Rønningen, L. A., Panggabean, M., & Tamer, O. (2011). Toward futuristic near-natural collaborations on Distributed Multimedia Plays architecture. 2010 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2010. https://doi.org/10.1109/ISSPIT.2010.5711738
• Varatharajan, R., Vasanth, K., Gunasekaran, M., Priyan, M., & Gao, X. Z. (2018). An adaptive decision based kriging interpolation algorithm for the removal of high density salt and pepper noise in images. Computers & Electrical Engineering, 70, 447–461. https://doi.org/10.1016/J.COMPELECENG.2017.05.035
• Vaseghi, S. V. (2012). Interpolation. In Advanced Digital Signal Processing and Noise Reduction (Vol. 33, pp. 3–8). https://doi.org/10.1002/0470841621.ch10