Browse Prior Art Database

Algorithm for Fast Digital Image Registration

IP.com Disclosure Number: IPCOM000075485D
Original Publication Date: 1971-Sep-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 4 page(s) / 37K

Publishing Venue

IBM

Related People

Barnea, DI: AUTHOR [+2]

Abstract

This is an algorithm for providing high-speed registration of two digital images.

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 44% of the total text.

Page 1 of 4

Algorithm for Fast Digital Image Registration

This is an algorithm for providing high-speed registration of two digital images.

Any generation of correlation surfaces implies a fixed amount of computation per surface point. Thus each point usually receives the same treatment with respect to evaluation accuracy. However, precision is required only for relatively few points--those with high-correlation values. Therefore, a considerable processing time wastage is encountered in performing high-accuracy calculations for the vast majority of points.

This algorithm takes advantage of this observation. The amount of computational investment is small for strongly misregistered points and grows with the likelihood for correct registration. Although this algorithm applies to a general n-dimensional space, the example which is used herein is that of two- dimensional image registration. While rotational matching can be handled, only translational registration will be considered for the sake of simplicity.

Let us define S as an LxL array of digital picture elements S(i,j), 1</-i,j</-L which may assume one of K values (grey levels) 0,1,..K-1. S will be called "the search area". Also, W is defined to be an MxM image (with M less than L) where elements W(i,j) assume the same range of values as elements S(i,j). W--"the window"--is assumed to have a certain degree of similarity to a corresponding part in S. The problem at hand is to automatically find the point (i',j') indicative of the "best" translation fit of the window to a subimage of the search area. (See Fig. 1).

It is assumed that enough a priori information is known about the dislocation between the window and search area so that the parameters L and M may be selected with the virtual guarantee that, at registration, an entire window size subimage is wholly contained in the search area. (See Fig. 2.)

The above assumption immediately limits the search for registration to at most (L-M+1)/2/ points. Hereafter, each of these (L-M+1)/2/ points, indicative of a shift for the upper left corner of the window, will be called a reference point. That is, it is desired to find the reference point (i',j') such that W in some sense matches the subimage of S of size MxM with the upper left corner at (i',j'), (S i',j').

At each reference point, W is compared with S(M) by operating on the given data at all or fewer of the M/2/ windowing points. That is, given reference point i'',j'', W(i,j) is compared to S(M)i'',j,(i,j) = S(i,+i-1,j,+ j-1) for some or all of the points (i,j) in the range 1</-i,j</-M.

This class of algorithms apply sequential search techniques to the solution of the registration problem. In the following discussion the general idea will be introduced, then, some specific implementations will be cited.

Each of the class of these algorithms has four basic elements, and are listed as follows:

1

Page 2 of 4

1) A method O(1): 0(1) is an algorithm for ordering the (L-M+1)/2/ reference points. Th...