Các thuật toán qui hoạch động song song để nhận dạng ảnh dựa trên đường biên

Abstract

The dynamic programming is an important procedure for speed understanding and  image recognition. In this paper, the application of dynamic programming to recognize the shape basing on its contour is recalled, then the parallenlism of this process is analyzed and exploited. Some parallel dynamic programming algorithms for evaluating the smallest value of the minimum intersegment distance path in a data table are designed in detail on several  kinds of  the  specialized paralled computer, such as 2D Systolic Array, 1D   Systolic Array and an associative computer of  the SIMD type. Their computation complexities are respectively estimated as O(k), O(k) and O(kw) while the cost of  sequential version is O(mn), where k= max(2n,m), m is the number of  segments of  a contour to be recognized, n gives the number of segments of the  sample contour and w ia the bit-width of the used associative fields.