Seyrek Genelleştirilmiş Ofset Polinom Eğrisinin Prony Algoritması ile Oluşturulması

Year 2021, , 553 - 556, 31.12.2021

Ali Çalışkan , Vahide Bulut , Selcan Kocabas

https://doi.org/10.31590/ejosat.1041047

Abstract

Bilgisayar donanımındaki teknolojik gelişmeler, bilim adamlarının bilimsel hesaplama ile ele aldığı sorunların boyutunu ve karmaşıklığını büyük ölçüde genişletmesine izin vermiştir. Seyrek polinomlar, hemen hemen her bilgisayar uygulamasında bulunmakta olup sıfır katsayılı polinomlar pratik ortamlarda sıklıkla ortaya çıkmaktadır. Son yıllarda, güç temelinden farklı terim temeli kullanılarak seyrek bir polinomun interpolasyonu için çeşitli algoritmalar tasarlanmıştır. Prony'nin 18. yüzyıldaki klasik sayısal tekniği Ben-Or ve Tiwari tarafından yeniden keşfedilerek yaklaşık 200 yıl sonra bilgisayar alanına uyarlanmıştır.
Pratik hayatta seyrek polinomların karşımıza çıktığı durumalara baktığımızda bunlar arasında görüntü netleştirme ve ses dalgalarının ayarlanması gibi problemler yer almaktadır. Fotoğraf işleme, onu gerçeğine yakın bir hale getirme son yıllarda büyük ilerlemeler kaydederken günümüzde orman, gün batımı, gökkuşağı gibi manzaraların dijital görüntüleri benzeri görülmemiş bir gerçekçilikle sentezlenebilmektedir. Bununla birlikte, kamera merceği ve ses dalgaları ile ilgili fenomenleri simüle etmek hala zorlu bir problem olmaya devam etmektedir.
Yapılacak olan çalışmada, merceklerin odak bulanıklığı, sapmalarının ve ses dalgalarının ayarlanmasında kullanılan seyrek polinomlara geometrik bir perspektiften yaklaşılarak seyrek genelleştirilmiş ofset eğrileri bulunacaktır. Bu seyrek genelleştirilmiş ofset polinom eğrisi, Prony algoritması ile eğrinin değerleri kullanılarak yeniden elde edilecektir. Orijinal seyrek polinom ile seyrek genelleştirilimiş ofset polinom eğrisi ile arasındaki ilişki incelenecektir. Böylece bu eğriler kullanılarak kamera mercek ve ses dalgalarının ince ayarlarının yapılmasına bilgisayar destekli geometrik tasarım ve hesaplama yöntemleriyle katkıda bulunulacaktır.

Keywords

Seyrek Polinomlar, Prony Algoritması, Seyrek Genelleştirilmiş Ofset Polinom Eğrisi

Forming The Sparse Generalized Offset Polynomial Curve by Prony Algorithm

Abstract

Technological advances in computer hardware have allowed scientists to greatly expand the size and complexity of the problems they tackle with scientific computing. Sparse polynomials are found in almost every computer application, and zero coefficient polynomials occur frequently in practical settings. In recent years, various algorithms have been designed for the interpolation of a sparse polynomial using a different term basis than the power basis. Prony's classical numerical technique in the 18th century was rediscovered by Ben-Or and Tiwari and adapted to the computer field nearly 200 years later.
When we look at the situations where sparse polynomials are encountered in practical life, these include problems such as image sharpening and sound waves adjustment. While photo processing and making it close to the real thing have made great progress in recent years, digital images of landscapes such as forests, sunsets and rainbows can be synthesized with unprecedented realism. However, simulating the phenomena associated with the camera lens and sound waves still remains a challenging problem.
In the work to be done, sparse generalized offset curves will be found by approaching the sparse polynomials used in the adjustment of lens blur, aberration and sound waves from a geometric perspective. This sparse generalized offset polynomial curve will be reconstructed using the values of the curve with the Prony algorithm. The relationship between the original sparse polynomial and the sparse generalized offset polynomial curve will be examined. Thus, by using these curves, computer aided geometric design and calculation methods will contribute to fine-tuning the camera lens and sound waves.

Keywords

Sparse Polynomials, Prony Algorithm, Sparse Generalized Offset Polynomial Curve

References

• Asadi M., Brandt A., Moir R.H.C, Maza M.M., (2019). Algorithms and Data Structures for Sparse Polynomial Arithmetic, Mathematics, 7, 441
• Roche D.S., (2018). What Can (and Can’t) we Do with Sparse Polynomials?. ISSAC ’18, July 16
• Comer M.T., Kaltofen E.L.,Pernet C., (2012). Sparse Polynomial Interpolation and Berlekamp/Massey Algorithms That Correct Outlier Errors in Input Values, ISSAC’12, July 22–25
• Patrikalakis N.M., (2003). Computational Geometry, 13.472J/1.128J/2.158J/16.940J
• Zheng Q., Zheng C., (2017). Adaptive Sparse Polynomial Regression For Camera Lens Simulation, Vis Comput 33:715–724 DOI 10.1007/s00371-017-1402-9
• Giesbrecht M., Labahna G., Lee W., (2009). Symbolic–Numeric Sparse Interpolation of Multivariate Polynomials, Journal of Symbolic Computation 44 (2009) 943–959
• İmamoğlu E., Kaltofen E.L., (2021). A Note on Sparse Polynomial Interpolation in Dickson Polynomial Basis, ACM Communications in Computer Algebra
• Chen X., Lin Q., (2014). Properties of Generalized Offset Curves and Surfaces, Journal of Applied Mathematics, Article ID 124240
• Kunis S., Peter T., Römer T., Ohe U., (2016). A Multivariate Generalization of Prony’s Method, Linear Algebra and its Applications, 490, 31-47
• Kaltofen E.L., Lee W.S., Yang Z., (2011). Fast Estimates of Hankel Matrix Condition Numbers and Numeric Sparse Interpolation, SNC 2011, June 7–9
• Kaltofen E.L., Pernet C., (2021). Sparse Polynomial Interpolation Codes and Their Decoding Beyond Half The Minimal Distance, CCF-1115772, HPAC ANR-11-BS02- 013
• İmamoğlu E., (2021). Sparse Polynomial Interpolation with Bernstein Polynomials, Turk J Math, 45
• Imamoglu E., Kaltofen E. L., (2021). A Note on Sparse Polynomial Interpolation in Dickson Polynomial Basis, ACM Communications in Computer Algebra
• Schrade E., Hanika J., Dachsbacher C., (2016). Sparse High-Degree Polynomials for Wide-Angle Lenses, Eurographics Symposium Volume 35, Number 4
• Barthélemy Q., Larue A., Mars J., (2015). Color Sparse Representations for Image Processing: Review, Models, and Prospects, HAL Id: hal-01187517
• Huang L., Jia J., Yu B., Chun B., Maniatis P., Naik M., (2010). Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression, Advances in Neural Information Processing Systems 23
• Mairal J., Bach F., Ponce J., (2014). Sparse Modeling for Image and Vision Processing, Foundations and Trends in Computer Graphics and Vision, OI: 10.1561/0600000058
• Bulut V., Çalışkan A., (2015). The Exchange Variations of Offset Curves and Surfaces, Results in Mathematics