M.Sc Thesis

M.Sc StudentLifshits Michael
SubjectVision-Based Navigation on Microscopic Images
DepartmentDepartment of Computer Science
Supervisor PROF. Ehud Rivlin


Navigation algorithm in the most general meaning is a reliable way to figure out where you are, to help guide you to where you are going, and to get you back home again. In this thesis we solve the problem of Navigation on microscopic images. Navigation has already found and has a great potential for wide application in many industrial and military related areas, as well as in human health support. Our algorithm for navigation is general and independent of application semantics. It may be applied in numerous and very different areas that make use of microscopic imagery. This research originated from a requirement in semiconductor manufacturing field, therefore we experimented with typical images from this field. In addition, we employed the same algorithm in another field - diagnostic pathology in medicine. The algorithm is fast enough for in-line microscopy and exhibits high tolerance to visual changes (scaling, rotation, translation and partial feature obliteration).

We formulate the navigation in terms of model-based object recognition and apply geometric hashing to achieve rapid and precise matching on the map. There are some intrinsic drawbacks associated with geometric hashing technique. Most significant are the non-uniform distribution of entries in the hash space and high sensitivity to noise. In this thesis we address both problems and propose the following solutions: (a) redistribute the entries in the hash space so that counting for errors would be more straightforward and (b) reduce the number of models being involved in navigation by utilizing the Quadtree structure.

Additionally, we implement Oracle-based system that makes use of wafer layout data along with the microscopic images to construct the wafer map and perform navigation tasks. The system facilitates the manipulation, examination and experimentation utilizing the advantages of modern database.