Image database key generation method

A method of generating a matching key for an image is disclosed. The matching key is substantially invariant to rotation, scale and translation. The method starts by forming a spatial domain representation of the image that is substantially invariant to translation of the image. Rotation and/or scaling in the spatial domain representation is next transformed into translation to form a transformed image. A representation of the transformed image is then formed that is substantially invariant to translation of the transformed image. The representation of the transformed image is the matching key for the image.

FIELD OF THE INVENTION

The current invention relates generally to creating databases of documents and, in particular, to generating keys for indexing of these databases that are robust to printing and scanning.

BACKGROUND

In most office environments, large numbers of documents are printed daily, and the task of organising and filing all of these documents, both physical and electronic versions, is becoming more difficult due to the increasing volume of such documents. A common problem experienced by users is finding the location of an electronic version of a document when the user only has a printed copy. Occasionally this problem is solved by printing some identifier on the printed copy of the document, with the identifier containing the information specifying where the electronic version of the document is stored. However, in certain circumstances such additional information cannot be added to the printed document, either for aesthetic or other reasons.

Another common problem is experienced when the user wishes to generate more copies of a printed document. Often this is simply achieved by photocopying the document. However, a photocopy of a document is generally not as accurate or as sharp as a print from the electronic version, especially where colour continuous tone images are concerned. Furthermore, for a large document, the process of scanning in the entire document, all of which may not be readily available in a condition suitable for copying, may take a considerable amount of time, which is undesirable. Accordingly, rather than photocopying the document, scanning a single page of the document and finding the electronic version of the document from which the single page was printed, and then reprinting the document from the retrieved electronic version of the document is a preferable method of obtaining new copies of the document.

A prior art method exists which involves generating a database of documents that have been printed. The database is indexed in such a way that the electronic files can be found from a scan of a document. Such databases can often be massive in size. Accordingly, a method of generating an indexing key which can be searched for in the database both efficiently and accurately is an important problem that must be solved to enable the desired functionality in a practical application.

One solution to this problem of image indexing key generation existing in the art is to perform block classification of the document that is scanned, identifying regions of the documents that are paragraphs of text and those regions that are images and graphics, and building a comparison function based on this classification. The downside to this method, and methods similar thereto, is that such methods are sensitive to variations in the printing and scanning process, and that such methods cannot properly distinguish between documents with very similar structural layout.

Another existing method of generating an image indexing key is to use a Fourier-Mellin invariant descriptor (FMID). A FMID is largely rotation, scale and translation (RST) invariant. That is, the FMID generated from an image is similar to the FMID generated from a rotated, scaled and/or translated version of that image.FIG. 1shows a flow diagram of this prior art method180of image key generation. In this method180, a key is generated from the input image received in step100by first applying a Fourier transform to the input image in step110. The complex magnitude of the result of step110is then calculated in step120. The complex magnitude is log-polar transformed in step130, and the Fourier transform of the result of the log-polar transform is performed in step140. The complex magnitude of the result of step140is calculated in step150. The image key, output in step170, is then calculated in step160by taking moments of the result of step150.

A drawback of the method180described with reference toFIG. 1is that, though the FMID is formally rotation, scale and translation invariant, it is not very discriminatory. In particular, the FMID does not distinguish well between images that are similar in their low spatial frequency structure, but differ in their high spatial frequency structure. This is a particular problem for discriminating between images of text documents that have a largely similar structural appearance, but differ in their textual content, as the textual content is represented by high spatial frequency phase structures in the image that do not survive the FMID generation process.

SUMMARY

According to a first aspect of the present invention, there is provided a method of generating a matching key for an image with said matching key being substantially invariant to rotation, scale and translation, said method comprising the steps of:

forming a spatial domain representation of said image that is substantially invariant to translation of said image;

transforming rotation and/or scaling in said spatial domain representation into translation to form a transformed image; and

forming a representation of said transformed image that is substantially invariant to translation of said transformed image, said representation of said transformed image being said matching key for said image.

According to a second aspect of the present invention, there is provided a method of generating a matching key for an image with said matching key being substantially invariant to rotation, scale and translation, said method comprising the steps of:

forming a multi-channel image of said image by applying an operator to said image, said operator being commutative within a constant to rotation and scale;

forming a representation of said multi-channel image that is substantially invariant to translation of said multi-channel image;

transforming rotation and/or scaling in said representation to translation to form a transformed image; and

forming a representation of said transformed image that is substantially invariant to translation of said transformed image, said representation of said transformed image being said matching key for said image.

According to another aspect of the present invention, there is provided a method of generating a matching key for an image, said method including the steps of:

forming a representation of said image that is substantially invariant to translation of said image by retaining translation invariant parts of the Fourier phase; and

using said representation as said matching key for said image.

According to another aspect of the present invention, there is provided a method of storing a document in a database, said method comprising the steps of:

creating one or more images of said document;

generating a matching key for each image of said document according to any one of the abovementioned methods;

storing said document and said matching keys in said database, wherein any one of said matching keys index said document.

According to another aspect of the present invention, there is provided an apparatus for implementing any one of the aforementioned methods.

According to yet another aspect of the present invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for implementing any one of the methods described above.

Other aspects of the invention are also disclosed.

DETAILED DESCRIPTION

It is to be noted that the discussions contained in the “Background” section relating to prior art methods relate to discussions of documents which form public knowledge through their respective publication. Such should not be interpreted as a representation by the present inventors or patent applicant that such documents in any way form part of the common general knowledge in the art.

To both explain the functioning of the invention and illustrate the advantage of the invention over the prior art, some theory of rotation scale and translation invariance based on the Fourier transform is now introduced. Throughout this section mathematical notation is used that is based on continuous function theory. This is for notational convenience only, and should not be considered limiting, as all calculations in the preferred embodiment of the invention are performed on sampled imaged data represented by finite precision arithmetic, and all Fourier transforms are performed using the discrete Fourier transform, and derivative operators may be performed using finite differences. It is also to be understood that there are a number of other mathematical notations and approaches that can be used to describe the same system, such as vector algebra, matrix algebra, and other equivalent algebraic systems, and that such notations and approaches are equivalent to those used here.

The Fourier transform of a two-dimensional function I(x,y) may be written as:

and the inverse Fourier transform of a two dimension function F(u,v) may be written as:

An image is said to be in the spatial domain in that a pixel in the image refers to an intensity at a particular spatial location of some coordinate system. The result of a Fourier transform is said to be in the Fourier domain (or the frequency domain) in that a value in the Fourier transform refers to an intensity at a particular frequency. An inverse Fourier transform applied to an image in the Fourier domain results in an image in the spatial domain.

If it is assumed that F(u,v) is the Fourier transform of image I(x,y), that is F(u,v)=ℑ[I](u,v), then the Fourier transform of image I2(x,y)=I(x+Δx,y+Δy), which is a version of image I(x,y) that has been translated by (Δx,Δy), may be related to the Fourier transform of image I(x,y) through:
ℑ[I2](u,v)=F(u,v)e2πiuΔxe2πivΔy.  (3)

This is the shift theorem of the Fourier transform that states that a translation in the spatial domain is equivalent to a linear phase shift in the Fourier domain.

The Fourier transform of a version of image I(x,y) that has been rotated by an angle, and scaled by scale factor s, that is I3(x,y)=I(s(x cos+y sin),s(−x sin+y cos)), is related to the Fourier transform F(u,v), by:

Equation (4) encapsulates the rotation and scale properties of the Fourier transform. It states that the Fourier transform of a rotated and scaled version of a two-dimensional function is the same as a scaled and rotated version of the Fourier transform of the two-dimensional function, up to a multiplicative constant. In particular, it states that the Fourier transform of the rotated and scaled version of the function is a rotated and scaled version of the Fourier transform. The scaling properties in the Fourier domain are opposite to those in the spatial domain—dilation in the spatial domain leads to contraction in the Fourier domain.

The rotation, scale and translation (RST) properties of the Fourier transform allow the construction of rotation, scale and translation invariant representations of an image. The Fourier-Mellin invariant descriptor (FMID) described in the “Background” section is such a RST invariant representation of an image. Given an image,
I4(x,y)=I(s(xcos+ysin)+Δx,s(−xsin+ycos)+Δy),  (5)
which is a rotated, scaled and translated version of image I(x,y), the Fourier transform of image I4(x,y) is related to the Fourier transform of image I(x,y) by,

The FMID of image I4(x,y) is calculated by firstly taking the magnitude of the Fourier transform of the image I4(x,y) as follows:

The magnitude of the Fourier transform is a translation invariant, as it does not depend on a translation (Δx,Δy) of the image. Transforming the magnitude of the Fourier transform into log-polar coordinates through the coordinate transformation

This transforms the rotation and scale in the Fourier domain to a translation in the log-polar resampled domain. Finally the magnitude of the Fourier transform of the quantity in the log-polar resampled domain is taken to form the FMID as follows:

The FMID is independent of both the translation and the rotation, and depends only in absolute value on the scale. As such the FMID can be used as a matching key using cross correlation between two representations of a two-dimensional function, such as an image, that are related by a RST transform. In Equations (7) and (9) a Fourier domain translation invariant—the magnitude of the Fourier transform—is calculated.

As noted above, the FMID has a number of drawbacks when it is used as an invariant descriptor of an image. The reason for this is based on the fact that a large proportion of the visual content of an image, when transformed to the Fourier domain, is contained within the Fourier phase. This is evidenced by, when the Fourier magnitude of one image is combined with the Fourier phase of another image, the resulting image typically looks like the image from which the Fourier phase was taken. Given that the Fourier phase encodes a lot of the image content, the fact that the FMID removes all the Fourier phase of the input image by taking a magnitude and further removing the Fourier phase of the log-polar transform means that the FMID has discarded much of the information about the image that a human finds perceptually relevant.

This is of particular relevance for images of text documents, which consist largely of edges. Edges in the Fourier domain are characterised by what is known as coherent phase, where the phase of the frequency components that represent the edge have a particular relationship that ensures that each frequency component that is present in the edge lies at the position of the edge. Removing the Fourier phase from an edge destroys the edge, and thus removing the Fourier phase from an image of a text document destroys the ability to discriminate that image from that of other similar text documents based on fine text details. It is for these reasons that the FMID is not a good invariant descriptor for images of text documents.

To demonstrate that the discriminating power of descriptors based on the rotation, scale and shift properties of the Fourier transform may be improved beyond what the FMID provides, it is necessary to introduce the concept of translation invariant phase. This is the part of the Fourier phase that is invariant to translation. The translation invariant phase may be used in the generation of an invariant descriptor, either explicitly or implicitly, thereby enhancing its discrimination, particularly for images of text documents.

As noted above, the shift theorem of the Fourier transform states that a shift in the spatial domain is the same as multiplication by a linear phase factor in the Fourier domain. If the Fourier transform of image I(x,y) is written as F(u,v)=|F(u,v)|eiΨ(u,v), that is in terms of its Fourier magnitude |F(u,v)| and its Fourier phase Ψ(u,v), then the shift theorem may be written as:
ℑ[I2](u,v)=|F(u,v)|eiΨ(u,v)e2πiuΔxe2πivΔy.(10)

That is, the Fourier phase of the shifted image is
Ψ(u,v)+2π(uΔx+vΔy).  (11)

By then taking the Laplacian of the Fourier phase Ψ(u,v), the result is independent of the translation of the initial image I(x,y):

Equation (12) shows that the Laplacian of the Fourier phase is an invariant to translation. The Laplacian of the phase as used in Equation (12) is calculated modulo 2π because the Fourier phase Ψ(u,v) is limited to the range (0,2π). If the Laplacian of the Fourier phase Ψ(u,v) is retained in any step where the translation invariant is generated, then the discriminating power of the invariant descriptor that is generated is greatly enhanced.

Other operators acting on the Fourier transform also retain some of the translation invariant Fourier phase Ψ(u,v), such as the Laplacian of the logarithm of the Fourier transform, or operators such as:

where the logarithm of a complex number such as a Fourier transform element is defined as:
logF(u,v)=log |F(u,v)|+iΨ(u,v),   (15)
where Ψ(u,v)=Arg(F(u,v)).

As these operators also retain some of the translation invariant Fourier phase Ψ(u,v), using these operators in constructing the invariant descriptor will also enhance its discriminating power.

Operators that act on the Fourier phase Ψ(u,v) directly to produce translation invariant descriptors that contain some of the translation invariant Fourier phase Ψ(u,v) may be termed explicit methods of retaining the translation invariant Fourier phase. There are also implicit methods that may be used to retain some of the Fourier phase Ψ(u,v) information that would otherwise be discarded when constructing an invariant descriptor, such as the FMID. These implicit methods involve non-linearly filtering the image I(x,y) to move some of the invariant Fourier phase Ψ(u,v) out of the Fourier domain and embed it in the spatial domain in such a way that it becomes part of the Fourier magnitude after Fourier transforming. Such methods also increase the discriminating power of the invariant descriptor.

An example of such a non-linear filtering involves constructing a complex image C(x,y), that is an image with both a real and imaginary part, from the real valued image I(x,y). This may be done by convolving image I(x,y) with a complex kernel function k(x,y), and taking the phase of this convolution and combining it with image I(x,y). For instance, if a complex kernel function k(x,y) is used that has the Fourier transform K(u,v)=ℑ[k] of:

then constructing the complex image is given by

where * denotes convolution. This leads to a complex valued image C(x,y) that has some of the translation invariant phase Ψ(u,v) of the original image I(x,y) present in its complex phase in the spatial domain. Furthermore, because the kernel function k(x,y) used in the convolution operation has no preferential direction or scale, the invariant descriptors generated from the complex image C(x,y), rather than the original image I(x,y), are still invariant to rotation, and scale, up to a multiplicative complex constant. Likewise, as the same convolution kernel is used at each point in the image, the invariant descriptors derived from complex image C(x,y) will also remain translation invariant. Performing non-linear filtering with kernels that have no preferred direction or scale leads to an improvement in the discriminating power of the invariant descriptor.

Other complex kernel functions may be used in generating the complex valued image from the real valued image. Another such kernel function is the complex gradient k′(x,y), which has a Fourier transform K′=ℑ(k′) of:
K′(u,v)=u+iv.   (18)

Other non-linear operators may also be used in generating the complex valued image C(x,y) from the real valued image I(x,y). Another such non-linear operator is the energy operator, which may be described by:
E[I]=ID2I−(DI)2,   (19)

where D is the derivative operator defined by:

Another alternative non-linear operator that may be applied to produce the complex image C(x,y) is the uni-modular energy operator:
E′[I]=ID′2I−(D′I)2,   (21)

where D′ is the uni-modular derivative operator. The uni-modular derivative operator D′ may be described as an operation in the Fourier domain as follows:

Given the advantages demonstrated in retaining the translation invariant phase information, both explicitly and implicitly, in the RST invariant generation process, this improved RST invariant is used to generate an image key in a document database system described below.

In particular, the preferred embodiment of the invention is described in terms of an office workflow environment, such as that depicted inFIG. 2, where a user prints a document from a desktop computer210at one moment in time, with the document then being stored into a document database230via a network240. Then, at a later moment in time, further copies of the document are generated using a digital photocopier220also attached to the document database230via the network240. In the above the digital photocopier220acts as a networked printer and a scanner. Documents are indexed in the document database230by an image key generated using the improved RST invariant described above.

FIG. 3shows a flow diagram of a process300performed in the computer210that occurs when the user first prints the document.FIG. 2Bshows a schematic block diagram of the computer210wherein the process300may be implemented as software executing within the computer210. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer210from the computer readable medium, and then executed by the computer210. A computer readable medium having such software or computer program recorded on it is a computer program product.

The computer210is formed by a computer module211, input devices such as a keyboard212and mouse213, and output devices including a display device214. A Modulator-Demodulator (Modem) transceiver device215is used by the computer module211for communicating to and from the network240.

The computer module211typically includes at least one processor unit216, and a memory unit217. The module211also includes a number of input/output (I/O) interfaces including an video interface218that couples to the video display214, an I/O interface219for the keyboard212and mouse213, and an interface209for the modem215. A storage device208is also provided, and typically includes a hard disk drive, a floppy disk drive and a CD-ROM drive. The components208,209, and216to219of the computer module211typically communicate via an interconnected bus207and in a manner which results in a conventional mode of operation of the computer210known to those in the relevant art.

Referring again toFIG. 3, process300starts in step310where the computer210receives a print job. The print job is typically generated by the user using an application such as a word processing application. The print job is then in step320spooled to a printer driver. The printer driver passes the job on to the digital photocopier220for printing a hardcopy in step330.

The printer driver also generates an image of each page in the print job in step340. The luminance channel of each image is converted to an image key in step350. Hence, each page of the document has an associated key. Finally, in step360, these image keys and the print job are passed over the network240to the document database230for storage.

FIG. 4shows a flow diagram of a process400occurring when the user generates a further copy of the document. Process400is performed the digital photocopier220, an in particular performed through software executing within a processor of the photocopier220.FIG. 2Cshows a schematic block diagram of the digital photocopier220. The digital photocopier220is formed by a computer module231, a printer232for providing printed paper as output, a scanner233for receiving paper as input and digitising any images formed on the paper into an electronic format. The photocopier220is further formed by a user interface234and controls235. The user interface234typically includes a display for displaying information to the user in textual or graphical form, and a touch screen for receiving commands from the user.

The computer module231typically includes at least one processor unit236, a memory unit237, and a number of input/output (I/O) interfaces, including an I/O interface238for the user interface234and controls235, an I/O interface239for the printer232and scanner233, and an interface241for connecting the computer module231to the network240. The components236to239and241of the computer module231communicate via interconnected bus242in a manner known to those in the relevant art.

The software controlling the operation of the digital photocopier220is resident in the memory237, and manages the interaction with the scanner116and the printer115, the user interface117and communications over the network240.

Referring again toFIG. 4, process400starts in step410when the user places a page of the document on the digital photocopier220and requests via the user interface of the digital photocopier220that a new copy of the document from which the page was taken be generated. In step420the photocopier220performs a scan of the page presented by the user in step410, thereby generating an image of the page of the document. This image is converted to an image key in step430, with step430being identical to step350inFIG. 3. The image key is then looked up in the document database230in step440to identify a corresponding document. If a corresponding document is found in the database230, the print job is retrieved by the digital photocopier220over the network240and reprinted in step450.

The preferred embodiment of an image key generation process500used in steps350and430is now described in more detail with respect toFIG. 5where a flow diagram of the image key generation process500is shown. This process500receives an image501as input. It is assumed that in this image501the pixel values are single channel values represented in either fixed precision or floating-point arithmetic. This image501may be supplied by an image capture device, such as a scanner (or camera) of the photocopier220in the case of step430, may be generated as the result of a rasterization process of a page description language as in the case of step350, may be received over the network240, or have some other source. In step505the input image501is halved in size until either the width or height cannot be halved without making it smaller than a predetermined SIZE_LIM pixels, where the preferred value for SIZE_LIM is 512. Image halving methods are well known in the art, such as B-spline fitting followed by decimation. With the image reduced in size, the width of the image in pixels is labelled as M and the height of the image in pixels is labelled as N.

In step510the output of the image-halving step505is “hedged”. Hedging means that the image is multiplied by a windowing function that applies a unity function to the majority of the image, but smoothly transitions to zero at the boundaries of the image. The size of the hedge specifies the maximum distance from the boundaries of the image that pixels should be modified from their original values. The preferred hedging size is W=24 pixels. The hedging function used in this embodiment is specified in terms of the factor by which each pixel a distance of d from the boundary is to be multiplied by. This factor is given by:

The hedged image output from step510is used to generate a complex valued image in step515. That is, the image is processed in such a way that the image input to step515, which has real valued pixels only, is converted to an image with complex valued pixels. This complex valued image is used to generate a translation invariant in step540.

This translation invariant is then transformed in step580such that rotation and/or scale in the translation invariant is transformed into a translation. In the preferred implementation this transform is achieved through log-polar resampling.

In order to resample to the log-polar domain, it is necessary to specify a resolution within the log-polar domain. As the halved image is M pixels wide by N pixels high, the horizontal coordinate x varies between 0 and M−1, while the vertical y-coordinate varies between 0 and N−1, and the centre of the translation invariant representation of the image generated in step540is located at (cx,cy)=(floor(N/2), floor(M/2)). Log-polar resampling to an image having dimensions P pixels by Q pixels in log-polar space is performed relative to this centre. To avoid a singularity at the origin, it is necessary to ignore a disc of radius rminpixels around the centres of the translation invariant representation. While ignoring this disc, a point (x,y) in the log-polar plane is determined by interpolating the translation invariant image at the point (x,y) as follows:

denotes the maximum radius that the log-polar sampling of the translation invariant image extends to. Preferred values of the constants are rmin=0.124rmax, P=96, and Q=240.

The preferred interpolation method of log-polar resampling the translation invariant representation of the image is bicubic interpolation.

The log-polar resampled translation invariant of the image is hedged for vertical edges in step585. In this hedging step the same hedging function is used as in step510, but the hedging function is only applied to pixels within distance W2=7 pixels of the left and right boundaries of the log-polar resampled translation invariant.

The result of the hedging step585is used in step588to generate a further complex image, and a further translation invariant is generated in step592. This further translation invariant, which consists of a complex image of 96 by 240 elements, is used in step595to construct an output key599. The translation invariant generated in step592may be used as the document indexing key directly. However, the result of step592is a complex image 96 pixels wide by 240 pixels high. Also, this translation invariant image is Hermitian, so only the upper half of the image needs to be used to construct the key, but even this 96 pixel by 120 pixel image is 11520 elements in length, which makes it too long for many applications.

The key construction method used in step595is preferably to halve the upper half of the 96 by 240 complex image generated in step592until the image is 24 by 30 elements in size, and to store the phase of these elements in scan-wise order in a vector of 720 elements. Other methods of constructing a key from the invariant descriptor may involve using all of the elements of the upper half of the invariant as the key, or forming a multi-resolution representation of the invariant descriptor for use as a key, or selecting a subset of the invariant descriptor pixels for use as the key.

Referring again to step440inFIG. 4, two image keys, K(1)and K(2), may be compared through cross-correlation. The similarity of the two keys is given by

where Ki(1)is the i-th element of image key K(1). Two similar keys will have a correlation value of close to 1 while dissimilar keys will have a correlation value of close to 0.

FIG. 6shows a more detailed flow diagram of a first implementation of sub-steps515and588(FIG. 5) where a complex valued image is formed from the hedge input image,625, which is produced either in step512or570. In sub-step630the hedge input image625, which is denoted I(x,y), is convolved with a complex kernel function k. The convolution may be performed in the spatial domain or through the standard technique of multiplication in the Fourier domain.

The complex kernel function k used in sub-step630is that with a Fourier transform K=ℑ(k) given by Equation (16). An alternative complex kernel function k′ that may be used in sub-step630is one with a Fourier transform K′=ℑ(k′) given by Equation (18).

The result of the convolution ((I*k), where * denotes convolution,) is normalised in sub-step635to have unit magnitude,

Finally the normalised result of the convolution Γ is multiplied with the hedge input image I(x,y) in sub-step640to form the complex image Ī(x,y). The complex image Ī(x,y) has the same magnitude as the original image I(x,y), but each point in the complex image Ī(x,y) has an associated phase generated by the convolution in sub-step630. For the kernel functions k and k′, the associated phase encodes a quantity related to the gradient direction of the image I(x,y).

FIG. 7shows a more detailed flow diagram of a second (alternate) implementation of sub-steps515and588(FIG. 5) where the complex image Ī(x,y) is formed from the hedge image I(x,y). In sub-step730a non-linear operator is applied to the image I(x,y) to produce a complex image.

The non-linear operator applied in sub-step420is the energy operator, which may be described by Equation (19). An alternative non-linear operator that may be applied in sub-step420to produce the complex image is the uni-modular energy operator given by Equation (21).

Preferably, in sub-step735which follows sub-step730, the result of the non-linear operator applied to image I(x,y) is normalised to unit modulus, and the result of this normalisation is multiplied by the original hedged image I(x,y) in sub-step740to form the complex image Ī(x,y). Alternatively, the result of the non-linear operator applied to image I(x,y), hence the output of sub-step730, may be used as the complex image Ī(x,y).

FIG. 8shows a more detailed flow diagram of a first implementation of sub-steps540and592(FIG. 5) in which a translation invariant representation of the complex image845is generated. Sub-steps540and592receive as input the complex image Ī(x,y) formed in sub-step515. The complex image Ī(x,y) is first Fourier transformed in sub-step850thereby producing an image consisting of complex values. This image is separated in sub-step855into two separate images, those being a magnitude image containing the magnitudes of the complex values of the Fourier transform, and a phase image containing the phases of the complex values of the Fourier transform. In sub-step860a function is applied to the magnitude image, where in the preferred implementation the magnitude image is multiplied by a ramp function of the form:
ƒ(u,v)=√{square root over (u2+v2)},   (29)

to perform high-pass filtering of the magnitude image. Alternately, any function being commutative within a constant to rotation and scale may be applied to the magnitude part of the image, e.g.
T(ƒ(x,y))=cƒ(T(x,y))   (30)

where T represents a rotation and scale transformation, ƒ is a function, and c is a constant. In sub-step865an operator is applied to the phase image to take the second or higher derivative of the phase, which is a translation invariant. In the preferred implementation the Laplacian operator is used.

Sub-steps540and592continues to sub-step870where the modified magnitude image produced from sub-step860, and the result of taking the Laplacian of the phase image produced from sub-step865are combined through:
|F|+iA∇2φ,   (31)

wherein |F| is the modified magnitude of the Fourier transform of the complex image Ī(x,y), ∇2φ is the Laplacian of the phase image of the Fourier transform, and A is a scaling constant set to:
A=max(|F|)/π.   (32)

The scaling constant A ensures that the recombined Fourier magnitude and phase information are roughly of equal magnitude.

The result of combining the modified magnitude image and the result of taking the Laplacian of the phase image is then inverse Fourier transformed in sub-step875, thereby producing the representation T(x,y) that is translation invariant in the spatial domain.

FIG. 9shows a more detailed flow diagram of a second (alternate) implementation of sub-steps540and592(FIG. 5) in which a translation invariant representation of the complex image845is generated. In this alternate implementation the complex image Ī(x,y) is first Fourier transformed in sub-step950thereby producing an image consisting of complex values. This complex magnitude of this image is taken in step955and in the preferred implementation this magnitude image is multiplied by a ramp function in step960to perform high-pass filtering of the magnitude image. The result of the filtering step960is then inverse Fourier transformed in sub-step965, thereby producing the representation T(x,y) that is translation invariant in the spatial domain.

Other translation invariants of the Fourier magnitude and phase may be used in place of sub-steps860,865and955, such as:

the modulus squared of the Fourier magnitude;

the logarithm of the Fourier magnitude;

the Laplacian of the logarithm of the Fourier transform; or

operators such as those in Equations (13) and (14).

The preferred embodiment of the invention has been outlined above. As has been noted in the description, there are various optional parts of the processing and different implementations of several of the steps are possible. Which exact implementation and which combination of steps is chosen are dependent on the conditions under which the embodiment is operating. In particular, if the embodiment is operating in an environment of restricted computing resources, for example in an embedded processing system in the photocopier220as opposed to on the processor of the general purpose computer210or server, then it is preferable to use a configuration of the invention that requires less computing resources.

In a computing environment where computing resources are not restricted then it is preferable to use both the complex image generation step outlined inFIG. 6and the translation invariant generation step outlined inFIG. 8. In a computing environment where computing resources are limited it is preferable to use the complex image generation step outlined inFIG. 6and the translation invariant generation step outlined inFIG. 9. Other combinations of choices between the two complex image generation steps outlined inFIGS. 6 and 7and the two translation invariant generation steps inFIGS. 8 and 9may also be useful in other circumstances. Furthermore, different choices may be made for steps535and588and steps540and592depending on the requirements of the system. A further variation would be to exclude the complex image generation step from the procedure outlined inFIG. 5, instead using the hedged halved image as input to the translation invariant generation procedure. In itself this modified procedure substantially improves the discriminating properties of the invariant descriptor over the prior art, though not as much as using the full procedure outlined above.

The preferred embodiment of the invention outlined above operates on the luminance channel of the input image. It is also possible to form invariant descriptors from other channels of the input image, such as colour channels, or hue, and saturation channels.