Genetic Algorithms and Image UnderstandingResourcesGenetic AlgorithmsGeneral Problem to be SolvedWhat Is a Genetic Algorithm?Survival Of the FittestPopulation PoolGenetic OperatorsFeature PreservationAn Example - ReproductionAn Example - CrossoverGA’s in Image SegmentationGA method for image segmentationPowerPoint PresentationEvolution of Segmentation SystemThe project: Implementation in DSP / FPGAGenetic Algorithmsand Image UnderstandingSam ClantonComputer Integrated Surgery IIMarch 14, 2001Resources•Bhanu, Bir and Lee, Sunkee. Genetic Learning for Adaptive Image Segmentation. Kluwer Academic Publishers, 1994•Goldberg, David. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley Longman, 1989.Genetic Algorithms•Optimization Problems•Adaptive Systems•Speed-Critical ApplicationsAre Useful For…General Problem to be Solved•The k-armed bandit problemPicture: GoldbergHow do we maximize our winnings?GA’s are good for multiple, many-armed bandits.What Is a Genetic Algorithm?•Operates on principle of survival of the fittest•“Population Pool” of Parameters•Genetic Operators - Reproduction, Crossover, and MutationSurvival Of the Fittest•Analogous to survival in biological system•Fitness Function•Optimization == Finding most fit parameter set for a particular problemSelk(an elk) ~ Ability to run away (elk, lions, tigers)Ability to run away (herd, lions, tigers)Spset(a pset) ~ Ability to perform task(pset, input)Ability to perform task(population, input)Population Pool24, 32, 76, 134, 43, 6, 17• “Surviving” parameter sets are kept around• Individuals are extracted and applied when input resembles past input for that individual.• Genetic operators add new individuals to pool• Individuals can be dropped when they appear uselessGenetic Operators•Affect survival of particular schema Schema - string representation of a feature•Reproduction f(H) / favg•Crossover 1 - pc * L(H) / L(total)•Mutation 1 - L(H) * pmFeature Preservation•Overall Equationm(H, t+1) = m(H, t) * F(H)/favgReproduction* (1 - pc L(H) / L(tot)Crossover- L(H) * pm )MutationAn Example - ReproductionString Initial PopX val F(x) = x * x Pselect (fitness/ total fitness)Exp. Count(fitness / avg fitness)Actual Count (roulette)1 01101 13 169 .14 .58 12 11000 24 576 .49 1.97 23 01000 8 64 .06 .22 04 10011 19 361 .31 1.23 1Sum 1170Avg 293Max 576An Example - CrossoverString Pop. Pool (w/Crossover)Mate Crossover SiteNew Pop. PoolX value F(x)1 0110|1 2 4 01100 12 1442 01100|0 1 4 11001 25 6253 11|000 4 2 11011 27 7294 10|011 3 2 10000 16 256Sum 1754Avg 439Max 739GA’s in Image Segmentation•Optimization problem•“Twiddling Knobs” Approach•Relationship to “Many k-armed bandit” problemFigure: Bhanu, LeeGA method for image segmentationFigure: Bhanu, LeeImages differ in characteristics such as brightness, saturation, skewness, entropy, etc.Use these values as inputs to genetic algorithmFigure: Bhanu, LeeImage AnalysisEvolution of Segmentation SystemFigure: Bhanu, Lee`The project: Implementation in DSP / FPGAImage CaptureImage ProcessorGeneticoptimizer CollatorMemoryOutputEdge