2025, issue 1, p. 32-42
Received 24.02.2025; Revised 09.03.2025; Accepted 25.03.2025
Published 28.03.2025; First Online 30.03.2025
https://doi.org/10.34229/2707-451X.25.1.3
Previous | FULL TEXT (in Ukrainian) | Next
Least Squares Method and Least Modules Method for Finding Defects in Regular Images
Volodymyr Zhydkov , Petro Stetsyuk
, Olha Khomiak *
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
The article describes methods based on method of least squares (LSM) and the method of least modules (LMM) to search for defects in regular images (regular 3D structures images). They correspond to the optimization problems of approximating the coefficients of a given matrix using matrix coefficients for a regular 3D structure according to the least squares criterion and the smallest modulus criterion. The difference (exceeding statistical average) between the coefficients of the given matrix and the coefficients of the found matrix marks the defect regions for a regular 3D structure.
Four optimization problems for finding the parameters of regular structures are formulated and their properties are formulated for the task. The first and second problems correspond to finding the best according to the criterion of least squares of regular and basic regular structures, and the third and fourth ‒ the best according to the criterion of smallest modules of regular and basic regular structures. Methods of calculating gradients of smooth functions (LSM) and subgradients of non-smooth functions (LMM) for all four problems are described. Codes of octave functions are provided, where the calculation of function values and its (sub)gradients is implemented using matrix-vector operations.
Also, the article provides sample test results of the application of r-algorithm to estimate the time of solving test problems on modern PCs for regular images of small sizes ‒ 400 pixels vertically and 600 pixels horizontally, and medium sizes ‒ 1000 and 1500 pixels. The first experiment is related to the restoration by means of MNC of the parameters of the basic regular structure without defects, the second experiment is related to the restoration by means of MNM of the parameters of the basic regular structure with defects in a small area (441 pixels). The developed programs can be used in dialog mode to analyze defects in regular images of small sizes (5 seconds) and medium sizes (40 seconds).
Keywords: regular 3D-structure, least squares method, least modulus method, r-algorithm.
Cite as: Zhydkov V., Stetsyuk P., Khomiak O. Least Squares Method and Least Modules Method for Finding Defects in Regular Images. Cybernetics and Computer Technologies. 2025. 1. P. 32–42. (in Ukrainian) https://doi.org/10.34229/2707-451X.25.1.3
References
1. Lobanov L.M., Pivtorak V.A., Kyjanets I.V., Savitsky V.V., Tkachuk G.I. Express control of quality and stressed state of welded structures using method of electron shearography and speckle-interferometry. The Paton Welding Journal, August, 2005. Р. 35–40.
2. Stetsyuk P.I., Savitsky V.V. On defects search in regular 3D-structures. International Scientific Technical Journal «Problems of Control and Informatics». 2018. 2. P. 33–48. (in Russian)
3. Stetsyuk P.I., Savitsky V.V., Zhydkov V.O. Optimization Problems for Regular Image Reconstruction. Book of Absracts of International Conference on Optimization and Equilibrium Problems, Dresden, July 31 – August 2, 2019. P. 45–46.
4. Stetsyuk P., Savitsky V., Zhydkov V. Finding defects in regular 3D structures. In “Non-smooth optimization methods in applied problems” / ed. P. Stetsyuk, M. Grygorak. Kyiv: LAZURITH POLYGRAPH, 2023. P. 230–257. (in Ukrainian)
5. NEOS Solver. https://neos-server.org/ (accessed: 17.02.2025)
6. SNOPT (Sparse Nonlinear OPTimizer) https://ccom.ucsd.edu/~optimizers/solvers/snopt/ (accessed: 17.02.2025)
7. Ipopt Documentation. https://coin-or.github.io/Ipopt/ (accessed: 17.02.2025)
8. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. http://www.gurobi.com/ (accessed: 17.02.2025)
9. CPLEX Optimizer. High-performance mathematical programming solver for linear programming, mixed-integer programming and quadratic programming. https://www.ibm.com/analytics/cplex-optimizer (accessed: 17.02.2025)
10. GNU Octave https://octave.org/ (accessed: 17.02.2025)
11. Shor N.Z. Methods of Minimization of Non-Differentiable Functions and their Applications. Kyiv: Naukova Dumka, 1979. (in Russian)
12. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. Amsterdam, Kluwer, 1998. 165 p. https://doi.org/10.1007/978-1-4757-6015-6
13. Stetsyuk P.I. Computer program "Octave program ralgb5a: r(α)-algorithm with adaptive step". Svidotstvo pro rejestratsiju avtorskogo prava na tvir 85010. Ukraine. Ministerstvo ekonomichnogo rozvytku I torgivli. Derzhavnyi department intelektualnoji vlasnosti. Data reiestratsii 29.01.2019. (in Ukrainian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next