Topological Numbering of Features on a Mesh (CC-88-18)
Mikhail J. Atallah, Susanne E. Hambrusch, Lynn TeWinkel · Purdue e-Pubs (Purdue University System) · 1988
Assume we are given an nXn binary image containing horizontally convex features; Le., for each feature, each of its row's pixels fann an interval on that row.In this paper we consider the problem of assigning topological numbers to such features; i.e., assign a number to every feature f so that all features to the left of f in the image have a smaller number assigned to them.This problem arises in solutions to the stereo matching problem.We present a parallel algorithm to solve the topological numbering problem in O(n) time on an nXn mesh of proces-SOI'S.The key idea of OUf solution is to create a tree from which the topological numbers can be obtained even though the tree does not uniquely represent the lito the left of' relationship of the features.