Genetic Programming - Image Segmentation

Information about Genetic Programming - Image Segmentation

Published on December 22, 2009

Author: tarundhot

Source: authorstream.com

Content

Slide 1: GPIS: Genetic Programming based Image Segmentation with Applications to Biomedical Object Detection Master’s Thesis Defence Presentation 13 January 2009 Tarundeep Singh Dhot Dept of ECE, Concordia University, Montreal, Canada [email protected] Presentation Overview : Presentation Overview Slide 2/26 Image Segmentation : Image Segmentation Slide 3/26 Is separation of objects/regions of interest from the background and each other Foreground/background separation process Vital first step of any image analysis process Ill-defined problem – no general segmentation framework Examples of image segmentation Slide 4: A GP-based image segmentation tool The GP evolves segmentation algorithms from a pool of primitive operators Primitives: Low-level image analysis functions (arithmetic, spectral, morphological, etc) - 20 primitives used GP searches for most effective combinations of primitives Currently tested on two medical image databases WHAT IS GPIS ? Slide 4/26 Representation : Representation Slide 5/26 Linear chromosomal representation Chromosomes - programs [HIST, d1, 0, 0, 0] [SUBP, io1, d1, .2, 0] [DIL, io2, 0, 0, 4] [LAPL, io3, 0, -4, 0] Genes – image operators [Operator, Input 1, Input 2, Weight, Structuring Element/Filter Parameter] GPIS - Flowchart : GPIS - Flowchart Slide 6/26 Initialization : Initialization Slide 7/26 Initial population of programs is randomly generated Maximum length of program = 15 operators Fitness Function : Fitness Function Slide 8/26 where: FPR – False Positive Rate FNR – False Negative Rate Wp – Weight for False Positives, Wp ϵ [0, 0.5] Wn – Weight for False Negatives, Wn = 1 - Wp len = Length of the program β – Scaling factor for the length of a program, β ϵ [0.004, 0.008] Selection and Elitism : Selection and Elitism Elitism: 1% of best individuals in population Parent Selection: Tournament Selection Tournament window size, λ = 10% of population size Survivor Selection: Steady State (no injection) Fitness based (injection) Slide 9/26 Evolutionary Operators : Evolutionary Operators Slide 10/26 Crossover: One-point Mutations: Type A: Swap, Insert, Delete (Inter-genomic) Type B: Alter (Intra-genomic) Crossover: 1-point : [A1] [A2] [A3] [A4] [A5] [A6] [A7] [A1] [A2] [A3] [B6] [B7] [DIL, d1, 0, 0, 2] GENE [A], [B] = IMAGE OPERATOR [B1] [B2] [B3] [B4] [B5] [B6] [B1] [B2] [B3] [B4] [A4] [A5] [A6] [A7] Crossover: 1-point PARENT CHROMOSOMES OFFSPRING CHROMOSOMES Slide 11/26 Mutations: Swap, Insert, Delete, Alter : Mutations: Swap, Insert, Delete, Alter Slide 12/26 Injection : Injection Slide 13/26 Every 5 generations, randomly initialized programs injected into population Number of injected program = 20% of population size Injection used in order to maintain population diversity Termination : Termination Slide 14/26 Termination is based on a fitness threshold (95% - Db1 and 90% - Db2) Termination criteria: |current fitness – mean fitness(10 gen)| < 0.05 * highest fitness Experiments : Experiments Slide 15/26 Tested on 2 medical image databases (HeLa Cells, Liver Tissue Specimen) Database 1: Cell extraction Database 2: Nuclei extraction Tested for effectiveness and efficiency Results compared to a GA-based image segmentation tool GENIE Pro GENIE Pro : GENIE Pro Slide 16/26 GA based general purpose image segmentation/feature extraction software Manual highlighting to prepare ground truth (true, false and unknown pixels) GA evolves IP “pipelines” – sequence of IP functions for segmentation from a set of IP functions based on prepared ground truth Evolved programs are constructed by combining the fittest pipelines using a linear classifier (Fisher Discriminant) Results: Database 1 : Results: Database 1 Slide 17/26 Fitness = 97.38% 96.98% 97.12% 91.02% 86.44% Superimposed input-evolved image Results: Database 2 : Results: Database 2 Slide 18/26 Fitness = 92.12% Fitness = 93.29% Superimposed input-evolved image Results: Database 2 : Results: Database 2 Fitness = 87.14% Fitness = 89.44% Slide 19/26 Superimposed input-evolved image Results: : Results: Slide 20/26 (i) Effectiveness (ii) Efficiency Database 1: HeLa Cells Database 2: Liver Tissue Specimen Results: Evolved Programs : Results: Evolved Programs Slide 21/26 Database 1: HeLa Cells [GAUSS, d1, 0, 6, 0.8435] [AVER, io1, 0, 4, 0] [EROD, io2, 0, 0, 1] [AVER, io3, 0, 6, 0] [CLOP, io4, 0, 0, 1] [THRESH, io5, 0, 0.09022, 0] Fitness on validation set = 97.32%, Number of operators = 6 [DISK, d1, 0, 3, 0] [AVER, io1, 0, 6, 0] [CLOSE, io2, 0, 0, 2] [ADDP, io1, io2, 0, 0] [EROD, io3, 0, 1] [EROD, io4, 0, 1] [THRESH, io5, 0, 0.1264, 0] Fitness on validation set = 97.61%, Number of operators = 7 [LOWPASS, d1, 0, 32, 0.793] [AVER, io1, 0, 4, 0] [AVER, io2, 0, 3, 0] [ADJUST, io3, 0, .205, 0.517] [CLOSE, io4, 0, 0, 1] [THRESH, io5, 0, 0.9852, 0] Fitness on validation set = 91.89%, Number of operators = 6 [UNSHARP, d1, 0, 0.82, 0] [HIST, io4, 0, 0, 0] [LAPL, io1, 0, -8, 0] [DISK, io2, 0, 6, 0] [AVER, io3, 0, 6, 0] [HIST, io4, 0, 0, 0] [ADJUST, io5, 0, 0, 0.202] [OPEN, io6, 0, 0, 1] [EROD, io7, 0, 0, 1] [THRESH, io8, 0, 0.752, 0] Fitness on validation set = 92.17%, Number of operators = 10 Database 2: Liver Tissue Specimen Results: Structure of Evolved Program : Results: Structure of Evolved Program Slide 22/26 [GAUSS, d1, 0, 6, 0.8435] [AVER, io1, 0, 4, 0] [EROD, io2, 0, 0, 1] [AVER, io3, 0, 6, 0] [CLOP, io4, 0, 0, 1] [THRESH, io5, 0, 0.09022, 0] Evolved chromosome Gene structure of chromosome Fitness of program on validation set = 97.32% # Generation = 114, # Fitness evaluations = 10,532 Input Image Output Image d1 = input; h1 = fspecial(‘gaussian’, [6 6], 0.8435) ; io1 = imfilter(d1, h1); h2 = fspecial(‘average’, [4 4]); io2 = imfilter(io1,h2); SE1 = strel(‘disk’, 2); io3 = imerode(io2, SE1); h3 = fspecial(‘average’, [6 6]); io4 = imfilter(io3,h3); io5 = imclose(io4, SE1); output = im2bw(io5, 0.09022); MATLAB implementation Conclusions : Conclusions Slide 23/26 Experimental results show that the operator pool is sufficient for our databases Injection is a viable option to maintain diversity Mutation is desirable as it allows parameter tuning GP was able to learn complexity of the databases in use (less generations for convergence for Db1 as compared to Db2) GP showed high detection rates on both databases (Db1 = 97.98%, Db2 = 89.98%) Contributions : Contributions Slide 24/26 Simple approach and anyone with MATLAB can use it Open sourced code Requires no a priori information other than training images Relatively general approach based on results on the two databases Produces better results as compared to GENIE Pro Suggested Future Work : Suggested Future Work Slide 25/26 Inclusion of automatically defined functions Competitive co-evolution Addition of conditional jumps Slide 26: Comments/Questions Thank you!

Related presentations


Other presentations created by tarundhot