טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentWinberger Dov
SubjectOptimized Image Segmentation Based on Evolutionary
Algorithms for a General Evaluation Function
DepartmentDepartment of Civil and Environmental Engineering
Supervisors Professor Maxim Shoshany
Dr. Ophir Almog


Abstract

            The first stage in an object based image analysis algorithm is finding objects. This is usually done using a segmentation algorithm. Image segmentation is subjective, there is no such thing as “the best segmentation” but there are features that are desired in most segmentations. The final quality of the analysis is majorly dependent on the quality of the segmentation. In most image segmentation algorithms there are many parameters to adjust, and one cannot know in advanced what thresholds to set for outputting a good segmentation. A better segmentation will improve all image analysis algorithms that use a segmentation process as a primal stage.


The main problem this thesis focuses on is finding the best image segmentation for a given segmentation evaluation function. The idea is that a specialist in a certain field will find the best image segmentation for his desired features. The secondary problem addressed in this thesis is that of thoroughly testing a segmentation evaluation function.


The algorithm is based on evolutionary algorithms for searching the segmentation space for a good segmentation. The heart of the algorithm is its recombination algorithm that specifies how to create the next generation of segmentation maps. We showed a proof for the convergence of the algorithm.


We tested three segmentation evaluation functions, all based on minimizing intra segments variance and maximizing inter segments variance, in order to decide which one is better and are they preferred to the human eye over the initial population using a survey. The results showed that FRC ?function (by Rosenberger and Chehdi) was better most of the times over the other segmentation evaluation functions. Also, the results showed that the segmentation evaluation functions examined got better scores with regards to the initial population according to the survey (the human eye) for the synthetic images but got worse scores then the initial population for the real images. In addition, we reinforced empirically the general claim in evolutionary algorithms that the larger and diverse the initial population is, the better the result of the optimization algorithm.


Our algorithm has no parameters that affect the resulting segmentation, it can be applied to any type of image and can be used to investigate segmentation evaluation functions. The algorithm has low time and space efficiency and thus is not appropriate for real time systems.