Methods For Fast Image Object Recognition In Robotics

Abstract

In Vision guided robotic operations, the rapid location and identification of image objects for assembly is essential. The image object data taken with a ccd camera may be in the form of a grey level, binary or colour image. This paper discusses our work on new speed up methods for object recognition in binary and grey level images. These are a coarse/fine stepping method and a sparse template technique. An extension of the coarse fine technique to give larger speedups is discussed. INTRODUCTION Searches for objects within images are extremely computationally expensive when scale, position and orientation of objects within the image is unknown. This paper reports results of a comprehensive coarse-fine object location program in which the criteria for coarse to fine switching have been investigated. These methods can speed up the column and row position search by a factor of 64. A matching error function is used to switch between coarse and fine search modes. Also a sparse template technique is used to give a further 64 fold speed up even more a for larger templates. This paper reports position search speed up times obtained on a number plate reading project. This work is of importance in vision guided assembly operations where machine vision techniques are used for locating parts and was first applied to a vehicle number plate location system. COARSE FINE COLUMN SEARCH By applying a reduced column search technique to object location in an image, a large reduction in computation may . be made. A basic approach is to move the template over the raster scan image, computing the mismatch function at each pixel location. Clearly if the matching calculations could be made at a reduced number of locations, ie a coarse search at say every fourth or fifth. pixel then a large speed up in the matching operation could be made. If a check is made by comparing the current matching error with the error calculation at the previous pixel position, then a decision can be made to move along say four or more columns, if the error is not moving towards a match. Alternatively, if the matching error is decreasing rapidly, from A to C in Fig 5, then the template pixel array will be moved along column by column after each calculation. Investigations showed that the template map may be moved along six columns for the coarse search and still find the matching position. A five to one speed up was obtained in this way. It is important to note that speedup factors are image dependent. COARSE FINE ROW SEARCH Similarly, a coarse fine (reduced) row search using a change in the image matching criterion between rows as a switch will give a speed up factor of the order of four or five to one assuming similar spatial changes in the vertical and horizontal directions of the image. This will be the case for images of uniform texture. More structured images of an industrial nature will not be so predictable. However matching error information is not as readily available in the case of the reduced row search. The matching error change method used was to save the lowest value of the matching error for the previous two rows and make a coarse fine search decision on the basis of this difference. An important point to consider in coarse fine searches is the dimensions of the template. A template four columns wide will have a much narrower correlation region than a 40 column wide template. Thus in certain cases for instance in the case of whole of image movement, where the template size is not fixed, it may be better to make the template longer (more columns) but not as wide, ie less rows if a coarse column search only is to be made. SPARSE TEMPLATES Matching error calculations may be speeded up by the use of sparse partial templates in which only say every fourth column and row brightness value of the template is checked against the image to be searched. A 16 times reduction in error calculations can be made in this way. For the case of noise-free images and templates, th