Anti-counterfeit pattern detector and method

An anti-counterfeit detector and method for identifying whether a platen image portion to be photocopied contains one or several pre-selected monetary note patterns. The detection is performed in a rotation and shift invariant manner. Specifically, the pattern can be of any orientation and at any location of the image. Moreover, it can be embedded in any complicated image background.

BACKGROUND OF THE INVENTION 
The present invention relates to an anti-counterfeit detector and method 
for identifying whether an image to be photocopied contains one or several 
pre-selected monetary note patterns. 
Preventing color copiers from being misused for counterfeiting has 
currently drawn more and more attention. In determining whether a color 
copier is being used for counterfeiting, a detector compares a known 
currency image with an image being copied. A problem arises in that it is 
difficult to detect the patterns in a rotation and shift invariant manner. 
Specifically, the pattern could be of any orientation and at any location 
on the image. The orientation and the location of the note can be 
relatively simple to obtain in the case of a single note with a plain 
background. However, it is difficult to obtain orientation and location if 
multiple notes are involved and/or the notes are embedded in some 
complicated image background. 
SUMMARY OF THE INVENTION 
It is therefore an object of the present invention to provide an 
anti-counterfeit pattern detector that detects patterns in a rotation and 
shift invariant manner. 
It is a further object of the present invention to provide greater accuracy 
and lower analysis time for the currency detection and orientation 
detection process. 
The present invention achieves these and other objects and advantages by 
providing a memory for storing a plurality of templates, each of the 
plurality of templates comprising at least one predetermined anchor point; 
examining structure for examining a portion of the image to be photocopied 
and for determining whether the portion contains a detected anchor point; 
orientation determining structure for determining an orientation of the 
detected anchor point; and matching structure for comparing the plurality 
of templates to the portion in accordance with the orientation of the 
detected anchor point. 
A method is also disclosed.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
The following detailed description of preferred embodiments is applicable 
to numerous detection and imaging systems as would be contemplated by 
those of ordinary skill. 
The invention will be described with general reference to FIG. 3. 
In order to detect whether a color copier is being used for counterfeiting, 
the detector 1 is first trained off-line with example notes. A template is 
created by an initial sampling of currencies (hereinafter template) 
suspected of being photocopied and counterfeited. Conventional sampling is 
preferably performed in a low resolution. 
The training includes sampling the templates and selecting one or several 
anchor points. Only those pixels on relatively straight edges, preferably 
long straight edges, are qualified to be anchor points. Anchor points are 
used to determine the edge orientation of the unknown document or 
documents and orient the template accordingly (discussed below). There is 
no set limit as to the number of possible anchor points in each template. 
The greater the number of preselected anchor points, the higher the 
detection accuracy, but the more time of analysis. 
One-dollar bills may be sampled at 16 dpi and 32 dpi, respectively. That 
resolution is sufficient to make a positive determination of the presence 
of currency when the template is compared with the image being 
photocopied. The template is stored in a computer memory 26 (FIG. 2) for 
future image comparison with the unknown document. 
The detecting of currency notes placed on a platen will now be described. A 
digital color copier contains functionally a scanning part 20 and a 
printing part 28 as indicated in FIG. 2. The currency detector 1 is placed 
in parallel to the normal video pass 30. A data processor (CPU) 22 
performs the functions of the detector 1. 
When an image of the platen (platen image) containing the unknown document 
is scanned by the scanning part of the copier, the signal is also sent to 
the detector 1. The image is sampled using conventional means and at the 
resolution of the template (FIG. 3, step S1), and stored into the image 
buffer 21. 
The information of a scanned color image is typically organized into three 
or four channels. The most commonly used sets of channels, or color 
spaces, are RGB and CIELAB. In RGB, three channels carry red (R), green 
(G), and blue (B) signals, respectively, while in CIELAB, L* channel 
represents luminance information, and a* and b* channels represent 
chromanance information. If RGB space is used, all three channels will be 
sampled at the same resolution of 16 dpi or 32 dpi. If L*a*b* space is 
used, a* and b* channels are sampled at a resolution that is half of that 
of the L* channel. Specifically, L* is sampled at 16 dpi or 32 dpi, and a* 
and b* are sampled at 8 dpi or 16 dpi. 
After sampling, the color image of the platen is smoothed (FIG. 3, step 
S2). The process of smoothing entails the averaging of the value of pixels 
within a given area and reassigning the averaged value to the center 
pixel. For example, a block area of 3.times.3 pixels may contain pixels of 
different value. An average value is obtained for the nine pixels, and is 
assigned to the center pixel. The reassigned value produces a new version 
of the platen image providing less prominent fine texture patterns that 
could otherwise confuse edge detection and orientation estimation (see 
below). 
The smoothed platen image is examined block by block, with a typical block 
size of 8.times.8 pixels. The blocks can be overlapping. Each block is 
examined by the data processor 22 (FIG. 2) to see if it possibly contains 
a pixel intensity orientation that corresponds to a preselected anchor 
point on the template. The "quiet blocks" containing little pixel 
variation, can be initially discarded as an edge is not present within the 
block (FIG. 3, step S3). For remaining blocks, the orientation of the 
edges contained in the block is estimated. The edge strength and 
orientation estimation is only performed on one of the color channels of 
the smoothed scanned image. In RGB space it is on G channel, and in CIELAB 
space it is on L* channel. 
The currency images often contain many fine textures that could be mistaken 
as edges. It is therefore very important to reduce the influence of 
texture during the edge strength and orientation estimation. The edge 
strength at a pixel (x,y) is quantified by the following formula: 
EQU f(x,y)=.vertline.d.sub.V .vertline..sup.3 (x,y)+.vertline.d.sub.H 
.vertline..sup.3 (x,y) (1) 
where d.sub.V and d.sub.H are differences in intensity of neighboring 
pixels of the smoothed image in the vertical and horizontal directions, 
respectively. The formula emphasizes strong differences, which typically 
characterize edges, more than the weak differences, which usually 
represent the texture. 
The edge strength of the block is determined by the following equation: 
EQU W=.SIGMA.f(x,y) (2) 
where the summation is over the 8.times.8 pixel block. 
The determined edge strength W is measured against a pre-chosen threshold. 
(FIG. 3, step S4). A block with weighted edge strength in excess of the 
threshold contains a major edge. If the edge strength does not exceed the 
pre-chosen threshold, the block is discarded, and a subsequent block is 
examined (FIG. 3, step S5). 
If it is determined that a block contains an edge, before it can be 
compared (matched) with the stored templates, the orientation of the edge 
must be determined (FIG. 3, step S6). 
Estimation of edge orientation (FIG. 3, step S6) will now be described with 
reference to FIG. 4. For the detector to properly determine 
counterfeiting, orientation estimation must be reliable and relatively 
accurate. In the present invention, a method based on second order moments 
is utilized, which is accurate and robust to noise. 
First, a candidate for the anchor point is found by calculating 
EQU x.sub.0 =[.SIGMA.f(x,y)x]/W 
and 
EQU y.sub.0 =[.SIGMA.f(x,y)y]/W (3) 
where the summations are over the 8.times.8 block (FIG. 4, step S100). The 
orientation of the edge is then evaluated using the following equation 
(FIG. 4, step S103): 
EQU .phi.=.theta.+0.5.pi., if .epsilon.&gt;0.5; 
EQU .theta., otherwise, (4) 
where 
EQU .theta.=0.5 tan.sup.-1 [2M.sub.xy /(M.sub.x M.sub.y)] (5) 
and M.sub.x, M.sub.y and M.sub.xy refer to second order moments defined as 
(FIG. 4, step S101): 
EQU M.sub.x =.SIGMA.f(x,y)(x-x.sub.0).sup.2 
EQU M.sub.y =.SIGMA.f(x,y)(y-y.sub.0).sup.2 
and 
EQU M.sub.xy =.SIGMA.f(x,y)(x-x.sub.0)(y-y.sub.0) (6) 
The summation spans a circular area centered at (x.sub.0,y.sub.0) with a 
diameter of 8 pixels. .epsilon. is defined as (FIG. 4, step S102): 
EQU .epsilon.=(M.sub.x sin.sup.2 .theta.+M.sub.y cos.sup.2 .theta.+2M.sub.xy 
sin .theta. cos .theta.)/(M.sub.x +M.sub.y) (7) 
where .epsilon. ranges from 0 to 1. 
Once the orientation is determined, comparison between the unknown document 
portion and the templates can be performed (FIG. 3, step S7). The 
templates are first rotated before matching in accordance with the 
determined orientation so that the axis of the anchor point aligns with 
the major direction of the block. The rotation is performed in a 
conventional manner by: 
EQU x'=x cos .phi.+y sin .phi. 
and 
EQU y'=-x sin .phi.+y cos .phi. (8) 
where (x, y) and (x', y') are the coordinates of a pixel before and after 
rotation, respectively and .phi. is the determined angle. 
Known image comparison means can be employed to compare the block with the 
anchor points on the templates. By way of example, FIG. 1A illustrates a 
template 2 containing a pre-chosen anchor point 4 with a known orientation 
6. FIG. 1B discloses a scanned document 8 contained within a platen image 
containing an active block 10 with determined orientation 12. The 
orientation of template 2 is adjusted to match the orientation of unknown 
document 10. This is illustrated in FIG. 1C. Finally, template 2 is 
matched with document 8, as is illustrated in FIG. 1D. 
The following equation may be used in matching: 
##EQU1## 
where v(x,y) and t(x,y) are intensity values at (x,y) in the smoothed 
platen image and template image respectively, and the summation is over 
the size of the template. The matching is performed on all three channels. 
The value of r ranges from -1 to 1, wherein 1 indicates a perfect match. A 
positive match is declared if r is greater than a preset threshold. 
Should currency be discovered from a positive match between the template 
and the unknown document (FIG. 3, step S8), the photocopier or printer 28 
may be deactivated or the portion of the platen image containing the 
unknown document may be deleted from the final printed image (FIG. 3, step 
S9), and the operation is terminated (FIG. 3, step S11). If no currency is 
discovered and there are more blocks to be examined, the operation returns 
to step S4 for the next block (FIG. 3, step S10); otherwise, the operation 
is terminated (FIG. 3, step S11). 
As counterfeiting is generally an irregular occurrence, the probability of 
a negative matching result is far greater than that of a positive one. To 
save computation, the matching is performed hierarchically, from several 
points to the entire template and from a low resolution to a high 
resolution. (The "high resolution" is a relative term. It is typically 
about 16 pixels per inch.) This enables an abort of a test if a mismatch 
is perceived at an early stage. In most cases, fairly reliable results can 
be obtained at low resolutions. High resolution is merely used for final 
verification. 
The edge orientation estimation also provides an estimated translation 
along the normal direction. Furthermore, template matching at low 
resolution is insensitive to small shifts. As a result, no translation 
compensation is necessary at low resolution. Should a high resolution 
matching be necessary, which is likely seldom, either a translation shift 
is estimated or the matching is performed for several different 
translations. 
Applying more anchor points can increase the detection reliability. Roughly 
speaking, the miss detection rate is p.sup.n for n anchor points, where p 
is the miss detection rate for a single anchor point. 
While this invention has been described in conjunction with specific 
embodiments thereof, it is evident that many alternatives, modifications 
and variations will be apparent to those skilled in the art. Accordingly, 
the preferred embodiments of the invention as set forth herein are 
intended to be illustrative, not limiting. Various changes may be made 
without departing from the spirit and scope of the invention as defined in 
the following claims. 
For example, if the currency to be detected are limited to a relatively 
small set, for example, U.S. dollars only, more sophisticated anchor 
points such as corner points can be used to increase the efficiency of the 
process. Other variations include different template matching techniques, 
different edge orientation estimation methods, and different schemes for 
combination of anchor points. Such variations may effect reliability, 
complexity, speed, and the constraints on the patterns to be detected.