Synthesis of vision algorithms based on state-space search

Computer vision is a task of information processing which can be modeled as a canonical sequence of subtasks: preprocessing, labeling, grouping, extracting and matching. A complete vision algorithm can be constructed by synthesizing individual operators performing the subtasks. Two problems in this synthesis are the selecting of operators at each step and the coordination between operators. The former has been studied extensively, but little has been done about the latter. This dissertation presents the state-space search method as a coordination scheme for vision algorithms. The approach regards the input image as the start state, image operators as search operators, models recognized by the system as goal states; and the state space consists of start state, goal states and intermediate states. In addition to these components, an algorithm graph is included in the state-space search model. An algorithm graph of a vision problem acts as a specification of the problem and part of a move generator of the search routine. The first contribution made in this dissertation is a new methodology for the design of cost functions based on information distortion. This method reflects the fact that the output of an image recognition process should present what the input presents; the only difference between the input and the output is that they represent the information in different ways. Therefore, information distortion should be used to measure the cost of a path. The second contribution of this dissertation is the development of a parallel search algorithm. The computational costs of state-space search can be reduced by parallelizing the search. A parallel search algorithm V$\sp\*$ is presented in this dissertation. The V$\sp\*$ algorithm is special in that it provides multiple levels of parallelism. An empirical study is presented which shows what performance improvements can be obtained with the V$\sp\*$ algorithm. By modeling vision problems as state-space search problems, this dissertation improves two critical aspects of vision algorithms: (1) generality, and (2) ease of developing algorithms for new applications.