Open Access

ARTICLE

# Algorithm of Dynamic Programming for Optimization of the Global Matching between Two Contours Defined by Ordered Points

Francisco. P. M. Oliveira1, João Manuel R. S. Tavares1

FEUP – Faculdade de Engenharia da Universidade do Porto, INEGI – Instituto de Engenharia Mecânica eGestão Industrial, Portugal.Email:franciscopmo-liveira@yahoo.com.br, tavares@fe.up.pt

Computer Modeling in Engineering & Sciences 2008, 31(1), 1-12. https://doi.org/10.3970/cmes.2008.031.001

## Abstract

This paper presents a new assignment algorithm with order restriction. Our optimization algorithm was developed using dynamic programming. It was implemented and tested to determine the best global matching that preserves the order of the points that define two contours to be matched. In the experimental tests done, we used the affinity matrix obtained via the method proposed by Shapiro, based on geometric modeling and modal matching. \newline The proposed algorithm revealed an optimum performance, when compared with classic assignment algorithms: Hungarian Method, Simplex for Flow Problems and LAPm. Indeed, the quality of the matching improved when compared with these three algorithms, due to the disappearance of crossed matching, which is allowed by the conventional assignment algorithms. Moreover, the computational cost of this algorithm is much lower than the ones of other three, leading to enhanced execution times.

## Keywords

APA Style
Oliveira, F.P.M., Tavares, J.M.R.S. (2008). Algorithm of dynamic programming for optimization of the global matching between two contours defined by ordered points. Computer Modeling in Engineering & Sciences, 31(1), 1-12. https://doi.org/10.3970/cmes.2008.031.001
Vancouver Style
Oliveira FPM, Tavares JMRS. Algorithm of dynamic programming for optimization of the global matching between two contours defined by ordered points. Comput Model Eng Sci. 2008;31(1):1-12 https://doi.org/10.3970/cmes.2008.031.001
IEEE Style
F.P.M. Oliveira and J.M.R.S. Tavares, "Algorithm of Dynamic Programming for Optimization of the Global Matching between Two Contours Defined by Ordered Points," Comput. Model. Eng. Sci., vol. 31, no. 1, pp. 1-12. 2008. https://doi.org/10.3970/cmes.2008.031.001

View