Browse Prior Art Database

Linear Scan Matching

IP.com Disclosure Number: IPCOM000091493D
Original Publication Date: 1968-Mar-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 2 page(s) / 55K

Publishing Venue

IBM

Related People

Gaffney, JE: AUTHOR [+2]

Abstract

In correlating two-dimensional search array 10 with a known library array 20, it is advantageous to match these arrays using their one-dimensional representation. If matched on a two-dimensional basis by superimposing arrays 10 and 20, then there are (2n-1)/2/ relative shifts in which at least one element from each array overlaps, including the completely overlapping case for two n x n element arrays. In the example n=2. With present techniques, decomposing these two arrays into one-dimensional patterns, yields only 2n/2/-1 relative shifts.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 70% of the total text.

Page 1 of 2

Linear Scan Matching

In correlating two-dimensional search array 10 with a known library array 20, it is advantageous to match these arrays using their one-dimensional representation. If matched on a two-dimensional basis by superimposing arrays 10 and 20, then there are (2n-1)/2/ relative shifts in which at least one element from each array overlaps, including the completely overlapping case for two n x n element arrays. In the example n=2. With present techniques, decomposing these two arrays into one-dimensional patterns, yields only 2n/2/-1 relative shifts.

The technique here yields the (2n-1)/2/ values of correlation usually possible only in two-dimension matching, while performing a one-dimensional matching operation. The drawing shows how the required (2x2-1)/2/ = 9 values of correlation can be obtained even though there are only seven relative values of shift in the one-dimensional case. Thus, there is a correlation of every point and exactly the same function is obtained as with a two-dimensional match.

Matches made with unblocked positions of array 10 are designated Level 1 values. Those made with blocked positions are labeled Level 2 values. Blocked positions are defined for upper array 10 moving relative to stationary lower array 20 as shown.

For movement to the right from complete overlap, blocked positions of the upper array are those elements to the right of row boundaries on the lower,array row corresponding to the original two-dimensional layout....