Blake, Andrew

2013-04-05T10:26:07Z

2013-04-05T10:26:07Z

1984

This thesis is concerned with problems of using computers to interpret scenes from television camera pictures. In particular, it tackles the problem of interpreting the picture in terms of lines and curves, rather like an artist's line drawing. This is very time consuming if done by a single, serial processor. However, if many processors were used simultaneously it could be done much more rapidly. In this thesis the task of line and curve extraction is expressed in terms of constraints, in a form that is susceptible to parallel computation. Iterative algorithms to perform this task have been designed and tested. They are proved to be convergent and to achieve the computation specified. Some previous work on the design of properly convergent, parallel algorithms has drawn on the mathematics of optimisation by relaxation. This thesis develops the use of these techniques for applying "continuity constraints" in line and curve description. First, the constraints are imposed "almost everywhere" on the grey-tone picture data, in two dimensions. Some "discontinuities" - places where the constraints are not satisfied - remain, and they form the lines and curves required for picture interpretation Secondly, a similar process is applied along each line or curve to segment it. Discontinuities in the angle of the tangent along the line or curve mark the positions of vertices. In each case the process is executed in parallel throughout the picture. It is shown that the specification of such a process as an optimisation problem is non-convex and this means that an optimal solution cannot necessarily be found in a reasonable time A method is developed for efficiently achieving a good sub-optimal solution. A parallel array processor is a large array of processor cells which can act simultaneously, throughout a picture. A software emulator of such a processor array was coded in C and a POP-2 based high level language, PARAPIC, to drive it was written and used to validate the parallel algorithms developed in the thesis It is argued that the scope, in a vision system, of parallel methods such as those exploited in this work is extensive. The implications for the design of hardware to perform low-level vision are discussed and it is suggested that a machine consisting of fewer, more powerful cells than in a parallel array processor would execute the parallel algorithms more efficiently.

http://hdl.handle.net/1842/6632

en

The University of Edinburgh

Blake,A and Ruttledge,H. (1980). CAP4 assembler and driver for a CLIP4 emulator. MIRU, Edinburgh University, Edinburgh.

Blake,A. (1981). Edge growing and relaxation, in parallel, Research memorandum MIP-R-134, MIRU, Edinburgh University, Edinburgh.

Blake,A. (1982). Fixed point solutions of recursive operations on boolean arrays. Cbmputer Journal, 25, 2, 231-233.

Blake,A. (1983a). Relaxation labelling - the principle of 'least disturbance'. Pattern Recognition Letters, 1, 385-391.

Blake,A. (1983b). The least disturbance principle and weak constraints. Pattern Recognition Letters, 1,393-399.

Zdrahal,Z. and Blake,A (1980). A simple emulator of a parallel processor: user guide. Machine Intelligence Research Unit, Edinburgh

Computer vision

line and curve extraction

parallel computation.

parallel algorithms

PARAPIC

POP-2

C computer language

parallel array processor

Parallel computation in low-level vision

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy