Dismiss
InnovationQ will be updated on Sunday, September 30, from 10am - noon ET. You may experience brief service interruptions during that time.
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

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...