Pattern Recognition

Pattern Recognition. From FOLDOC. "A branch of artificial intelligence concerned with the classification or description of observations. Pattern recognition aims to classify data (patterns) based on either a priori knowledge or on statistical information extracted from the patterns. The patterns to be classified are usually groups of measurements or observations, defining points in an appropriate multidimensional space."

How Do Post Office Machines Read Addresses? By Ben Mauk. LiveScience.com (August 16, 2007). "The United States Postal Service (USPS) began researching remote computer readers (RCRs) for handwritten addresses in 1983. At the time, the technology required to scan and understand a human scrawl simply did not exist. Not until Christmas of 1997 did the USPS and the University of Buffalo's Center for Excellence in Document Analysis and Recognition (CEDAR) deploy its first handwritten address-reading prototype.... Humans read and comprehend with an ease that belies the immense difficulty of computer pattern recognition (including patterns such as numbers and letters). It is one of the central problems in artificial intelligence. ... 'That Christmas alone we saved several thousand dollars for the post office,' Sargur Srihari told LiveScience. Srihari founded CEDAR and led the early research on large-scale RCRs. Today, the large majority of letters sent through the post office are read and sorted entirely by computer. According to Srihari, current reading success rates are above 90 percent."

• For more information about CEDAR, see this collection elsewhere on this page.

The Robot Shopkeeper - New customer behavior technology from NCorp gives a personal touch to online shopping. By Thomas K. Grose. TIME Europe: Digital Europe Start-Up of the Week (September 2, 2002). "In today's world of online shopping, call centers and impersonal supermarkets, that human touch is missing. But technology developed by a former Cambridge University researcher could help introduce old fashioned personal care into online shopping. Mike Lynch, who has a doctorate in pattern recognition, began developing algorithms to help identify patterns more than a decade ago. ... The basic technology is a form of Artificial Intelligence that 'gives computers the ability to recognize patterns the way humans can,' explains Nick Bidmead, NCorp chief executive."

The Pattern Recognition Files. A very comprehensive collection of pattern recognition resources from the Pattern Recognition Group at Delft University of Technology. Maintained by Bob Duin.

• Pattern Recognition Area Description
• Pattern Recognition Books
• Pattern Recognition Journals
• Pattern Recognition Research Area
• Pattern Recognition Research Groups (Europe and N/S America)
• Software and Hardware for Pattern Recognition and Image Processing Research
• ... and much, much more.

FVC2002: the Second International Fingerprint Verification Competition. Sponsored by the Biometric Systems Lab at the University of Bologna, the Pattern Recognition and Image Processing Laboratory at Michigan State University, and the U.S. National Biometric Test Center at San Jose State University.

• FVC2000 - information about the first competition
• FVC2004 - information about the Third International Fingerprint Verification Competition

Biometrics Research. From the Pattern Recognition and Image Processing Lab, Department of Computer Science and Engineering, Michigan State University. "Biometrics refers to the automatic identification of a person based on his/her physiological or behavioral characteristics. ... Various types of biometric systems are being used for real-time identification, the most popular are based on face recognition and fingerprint matching. However, there are other biometric systems that utilize iris and retinal scan, speech, facial thermograms, and hand geometry. A biometric system is essentially a pattern recognition system which makes a personal identification by determining the authenticity of a specific physiological or behavioral characteristic possessed by the user."

• Also see:
  • the MSU Pattern Recognition and Image Processing Lab
  • our collection of resources about biometrics

Readings Online:

Computer programs help flag insurance fraud before payment. By Julie Appleby. USA Today (November 7, 2006). "Computer sleuths trying to stop health care fraud say they have a new weapon: computer programs that can flag potential fraud even before medical claims are paid. ... Insurer Aetna says its new computer software helped it stop $89 million in payments before they reached medical providers last year. That compares with the $15 million in fraud repayments it was able to collect after the fact. ... While the software systems may differ, their main effort is to spot medical providers who vary from the norm. 'Pattern recognition is a growing field in health fraud detection,' says Malcolm Sparrow, a professor at Harvard's John F. Kennedy School of Government and author of License to Steal: How Fraud Bleeds America's Health Care System."

Imgae processing apparatus

There is an image processing apparatus such as a copying apparatus for processing an input image data. This apparatus comprises: an image scanner such as a CCD to digitally read out the image data from a document; a discriminating unit to discriminate whether the input image data is the halftone image data such as a photograph or single density image data such as characters or symbols; a magnification change unit to change the magnification of the image data; and a smoothing unit to smooth the image data in the case where the discriminating unit decides that the input image data is the halftone image data when the magnification change unit performs the magnification changing process. The discriminating unit executes the above discrimination on the basis of the density levels of or density difference between a target pixel and its peripheral pixels in the input image data. With this apparatus, the magnification of the halftone image can be smoothly changed.

image processing

• Algorithm development and implementation (connected component series, upslope area series)
• Image processing concepts (pad values in dilation and erosion)
• Things I wish I knew more about (Costas arrays)
• Software design decisions (whatever happened to isgray, bwlabeln)
• Software features you might not know about (bwselect, imclearborder)
• Random thoughts (classification of operations, image processing in movie plots)

Classification of operations

In image processing textbooks, you often see low-level image processing operations grouped into two categories:

• Point processes
• Neighborhood processes

In a point process, the value of each output pixel is a function of only the corresponding input pixel. Examples include adding a constant to all image pixels and gamma correction.

In a neighborhood process, the value of each output pixel is a function of the corresponding input pixel and a fixed set of neighborhood pixels around it. For example, filtering with a 3-by-3 filter is a neighborhood process. Each output pixel depends on the values of the corresponding input pixel, as well as that pixel's eight neighbors. Dilation is another example of a neighborhood process.

Here are two more types of operations that I've found to be common:

• Transforms
• Queue processes

Lots of operations have the word transform in them, such as Fourier transform, Hough transform, and geometric or spatial transform. But it's a little hard to define what makes something a transform. I think transforms tend to have these characteristics in common:

• They are invertible, or at least approximately invertible under certain conditions.
• The transform pairs involve different coordinate systems. For example, the Fourier transform involves a spatial and a frequency coordinate system, and the Radon transform involves a spatial and a rho-theta coordinate system. Even geometric transforms involve two different spatial coordinate systems.

I'm hoping to find a better term for queue processes, but that's the best I've come up with so far. A queue process works by "spreading out" in some fashion from a set of starting pixels. I use the word "queue" here because implementations often involve a queue data structure, like this:

% Initialize the queue
for each pixel p in image:
   if p satisfies some condition
       push p onto queue
   end if
end for

while queue not empty
   get next pixel k from queue
   record something about k in the output image
   for each neighbor pixel j of pixel k
       if j satisfies some condition
           push j onto queue
       end if
   end for



end while

"Flood filling," which many of you can probably visualize, can be implemented this way. There are several algorithms in the Image Processing Toolbox that use queues in this fashion, including morphological reconstruction (imreconstruct) and the watershed transform (watershed).