Browse Prior Art Database

Fast Gray Scale Pattern Matching Method and Apparatus Using Genetic Algorithm

IP.com Disclosure Number: IPCOM000118557D
Original Publication Date: 1997-Mar-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 34K

Publishing Venue

IBM

Related People

Nakano, H: AUTHOR

Abstract

Disclosed is a method for fast gray-scale pattern matching by using Genetic Algorithm (GA). In case of executing pattern matching using normalized correlation method, the calculation cost for rough matching is reduced to 1/6 by using a genetic algorithm.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 95% of the total text.

Fast Gray Scale Pattern Matching Method and Apparatus Using Genetic
Algorithm

      Disclosed is a method for fast gray-scale pattern matching by
using Genetic Algorithm (GA).  In case of executing pattern matching
using normalized correlation method, the calculation cost for rough
matching is reduced to 1/6 by using a genetic algorithm.

Assumption:
  Image size: 256 by 256, template size 48 by 48.

GA parameters used for normalized correlation:
   - Expression of each individuals:
  4 hexadecimal digits:  the first 2 digits indicate
  X coordinates (0-207), last 2 digits indicate Y coordinates
   (0-207).
   - Fitness:
   Fitness f is p(x,y), where p(x,y) indicates correlation
    value (0-255).
   - Elitism:

      The algorithm uses a process called "elitism" in which some of
the individuals with good fitness from the previous generation
replace some of the worst individuals in the current generation.

In this process, the population of individuals may not change.
  - Maximum generation: 300, elitism pressure: 0.01,
     probability of crossover: 1.0 probability of mutation: 0.01,
     population: 100

      Experimental result of the apparatus:  Nearly best fitness
appears at 23th generation.  The best fitness appears at 145th
generation.

      Benefit of this method:  By using conventional method, the
correlation value of all position (208 by 208) must be calculated to
locate best matching position.  In this case, the numbe...