JP2003051014A - Information processing apparatus and method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To enable accurate comparison between various physical quantities at the time of handwriting input, and realize accurate matching. A two-dimensional pattern including a sequence of coordinate points input by handwriting through a digitizer and a writing pressure at the time of inputting handwriting are acquired. The pattern represented by the two-dimensional pattern information is approximated by connecting a plurality of line segments, and is converted into a piecewise line segment curve. Then, the arc length along the piecewise line segment curve is equally divided to obtain a one-dimensional grid point sequence {s} along the curve.
(i)｝ is generated. The obtained pen pressure is converted into a function of the one-dimensional lattice point sequence, and a pen pressure distribution p (s (i)) is obtained. At the time of handwriting collation, a comparison between the pen pressure distribution and the standard pattern is taken into account.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an information processing apparatus and method, and more particularly, to an information processing apparatus and method suitable for performing individual collation based on a pattern written and input by a pattern matching process.

[0002]

2. Description of the Related Art Inquiring a person using a handwritten signature has formed a signature inquiry culture centered on the West.
On the other hand, even in the electronic information society, it is necessary to construct a similar inquiry system. Because of their necessity, for example, JP-A-10-171926 and JP-A-10-
40388 and Japanese Patent Laid-Open No. 5-324805 propose a signature verification system. The signature verification system described in these documents will be described below.

The technique described in the above document will be described with reference to FIG. A signature is input to the input device 3021 such as a digitizer using the electronic pen 3022. The input signature reads the position coordinates (xin, yin) of the electronic pen and the writing pressure pin at unit time intervals, converts these into electrical signals as time series data, and sends them to the data control unit 3023. The data control unit 3023 compares the input data with a standard pattern serving as an evaluation reference, and determines whether the signature is the person's signature.

As a method for detecting the difference between the standard pattern and the input pattern, a fuzzy method is used (Japanese Patent Laid-Open No. 5-324805) and a dynamic programming method is used (Japanese Patent Laid-Open Nos. 10-171926 and 10-40388). Is proposed.

Regarding the dynamic programming method, for example, "Handbook of Pattern Recognition and Ima
ge Processing ”TYYong / KS.Fu co-edited Academic Press 1
Described in 986.

In all of these methods, time-series data of discrete Cartesian coordinates x and y coordinate values obtained by a signature are directly subjected to pattern matching with standard time-series data of x and y coordinate values. It is indispensable to do this, and weighting such as writing pressure or weighting regarding the speed of time-series data is performed.

On the other hand, a curve like FIG.
It is called a curve that is immersive in a dimensional plane. That is, the data of the signature can be recognized as a curve that is fitted (immersed) on the two-dimensional surface.

[0008] It is a good idea to consider a signature character as a symbol or a geometric curve rather than a character because of its extreme omission, continuation characters, and collapsing characters. In view of the fact that the above authentication was established, it should be considered that there is a limit to the recognition method of handwritten characters as ordinary characters. Therefore, in the present application, the signature character is recognized from the viewpoint of classifying the curve, that is, the famous collation problem is replaced with the problem of similarity or congruence of the curve figure. Therefore, the curve obtained from the signature will be hereinafter referred to as a signature curve.

From this point of view, the conventional signature verification technique using the discretized Cartesian coordinate values is
As described in the section of "Problems to be Solved by the Invention" below, it can be understood that the same problem as in the method of classifying curves in xy coordinates occurs, and these are problems in matching. Can understand.

The invention of a method for classifying the shape of a curve is disclosed in Japanese Patent Laid-Open Nos. 5-197812 and 6-30946.
5, there is a series of figure shape learning recognition methods disclosed in JP-A-7-37095. Here, the invention described in these publications will be described as a conventional technique.

It is assumed that the dot row is given as {d [i] | i = 1, ..., N}. However, d [i] is an integer 2
Dimensional vector quantity, and dot row is d [i] = (x [i], y
It is a two-dimensional grid coordinate sequence of [i]). For simplification of explanation, it is assumed that the dot row is closed and the number i is also given modulo N as in the case of the publication. Therefore, it is assumed that d [i method N] is set. Also,
It is assumed that the dot rows are ordered along the connectivity of the curves. For the sake of simplicity, here, as a thinned curve, a whisker as shown in FIG. 14A and a beard as shown in FIG. Bend over resolution, double line as shown in (c),
It is assumed that there are no intersections as shown in (d). However, since the actual signature curve has numbers in time series and the locus shown by the white line can be reproduced within the range of dot resolution, there is no problem, but here we assume the above assumption for simplicity. I put it.

Next, Japanese Patent Laid-Open Nos. 5-197812 and 6-
What is called "curvature" in Japanese Patent Laid-Open No. 309465/1995 and Japanese Patent Laid-Open No. 7-37095 is defined. JP-A-6-3094
As clearly stated in 65, the "curvature" that the inventor calls is not a curvature having a mathematical meaning. In fact, the fact that this definition cannot give correct information because it contradicts the discussion of the congruence of figures is described in detail in the section "Problems to be solved and used by the invention". Therefore, in this specification, the curvature defined in the above literature will be referred to as pseudo curvature.

FIG. 15 is a diagram for explaining the definition of the pseudo curvature according to the above conventional technique. For pixel d [i],
Consider a pair of dots (two-dimensional vector) of (d [ik], d [i + k]). For a line segment determined by (d [ik], d [i + k]), draw a perpendicular line from d [i], and mark its height as B [k].
In addition, the length of the line segment determined by (d [ik], d [i + k]) is L
Write [i, k]. For k, natural numbers 1, 2, 3, ... Are carved, and B [k] is calculated each time. Parameter E given in advance
On the other hand, in the range where B [k] does not exceed E, the maximum k is searched.

At this time, two types of pseudo curvature are defined as follows according to FIG. 1. First pseudo-curvature (Japanese Patent Laid-Open No. 5-197812): The first pseudo-curvature is the angle θ [i] between the vector (d [i + k], d [i]) and the vector (d [ik], d [i]). Let it be the curvature. Also, the number of pixels i
{(I, θ [i]) | i = 1, ..., as the distribution function of
N} is called a first pseudo curvature function. 2. Second pseudo-curvature (Japanese Patent Laid-Open No. 6-309465, Japanese Patent Laid-Open No. 7-309465)
-37095): Three points (d [i + k], d [i], d [i on the curve
-k]) is determined and the radius of the circle is R [i], 1 / R [i] is the second pseudo curvature. In addition, {(i, 1 / R [i]) | i = as a distribution function of each pixel number i
1, ..., N} is called a second pseudo curvature function.

As shown below, the two pseudo curvatures defined as described above are not substantially invariant to the affine (congruent) transformation, respectively, and even in the limit of bringing the pixel resolution to zero. It happens when there is no limit. That is, they are not well-defined mathematically. Therefore, the obtained figure is not invariant to affine transformation or the like, and is an ambiguous quantity. It is Japanese Patent Laid-Open No. 5-197812 and Japanese Patent Laid-Open No. 6-199812 that attempts to compensate for this mathematical defect by using a neural network.
No. 309465 and Japanese Patent Laid-Open No. 7-37095.

The algorithm will be described with reference to FIG.
In step SS1, the memory and the like are initialized. For example, a curved figure is used as thinned data so that there is no pattern as shown in FIG. In step SS2, the above-mentioned first or second pseudo-curvature is calculated for the curve to calculate the pseudo-curvature distribution. In step SS3, the obtained pseudo curvature distribution is processed using a neural net to classify the curves.

As will be described in the section "Problems to be solved by the invention", the above-mentioned pseudo-curvature is mathematically unstable. Therefore, as shown in step SS3, the learning ability of the neural network etc. You have to do something. This is an important fact. According to the present invention described below, since there is no such mathematical defect, it is possible to classify a curved figure with a classical logic circuit.

[0018]

It is known that the classification of a curve fitted to a two-dimensional surface is defined by the Frenet-Sere relational expression. (Eg "A Treatis
e on the DifferentialGeometry of Curves and Surfac
es ", LPE Isenhart, Ginn and Company 1909). As shown in Fig. 17, the tangent angle to a curve is φ, and the length (arc length) of the curve determined from the natural measure of the two-dimensional plane is s. Then, the following relational expression can be defined.

[0019]

[Equation 1]

Where k = dφ / ds is the curvature, and 1
/ K is called the radius of curvature. This relational expression is called Frenet-Cele's relational expression.
It is the teaching of classical differential geometry that the local nature of a curve is completely determined.

It should be noted that the curvature k in the curve theory of classical differential geometry is an external curvature, and is a kind of what is called a connection according to the term of modern differential geometry. The curvature k is defined in one dimension, and has no direct relationship with the internal curvature called a curvature tensor that has no value unless it is two or more dimensions. The term "modern differential geometry" is, for example, "Geometry,
Topology and Physics "by M. Nakahara, Institute of Ph
Written in ysics publishing 1990. In addition, regarding the internal and external curvatures, in the case of a two-dimensional surface, "Gaussian surprise theorem"
It is related by the theorem.

When the display independent of the coordinates is adopted, the curvature called by the classical differential geometry is k = kds. This is a form of quantity in modern differential geometry terms.

As is well known, the distinction between one form (distribution function) and function (scalar function) is made by the difference in transformability with respect to coordinate transformation. In other words, when the arc length s is coordinate-transformed into s as a monotonically increasing infinite continuous differentiable function g (s), the (scalar) function is f (s) = f (g (s)).
On the other hand, one form (or distribution function) is f (s) ds ＝ f (g (s)) (ds
/ dg) converted to dg. Here (ds / dg) means Jacobian.

Therefore, the curvature is a distribution function in which the Jacobian must be taken into consideration for the coordinate transformation, and the arc length s
When the coordinate is transformed to s into a monotonically increasing function g (s),
If k (s) is not converted to (k (g (s)) (ds / dg)), mathematically meaningful results cannot be obtained.

However, Japanese Patent Laid-Open Publication No. Hei 5-19
7812, JP-A-6-309465, JP-A-7-370.
The pseudo-curvature defined in 95 does not consider the coordinate transformation from arc length to number of pixels. Actually, there is arbitrariness in converting a line segment into two-dimensional image data, and as shown in (a) and (b) of FIG. Not constant for length. That is,
The number of dots can be regarded as a function of the arc length, and when expressing a distribution function such as the curvature of classical differential geometry by the number of dots, the expression itself must be regarded as a coordinate conversion from the arc length. In particular, two-dimensional image data generally does not have the degree of freedom of rotation, and the degree of freedom of parallel movement equal to or smaller than the pixel size is lost. In other words, the number of dots is a function that changes with respect to the arc length s, which is the coordinate along the arc, and when expressing a curvature that is a form (distribution function), how to discriminate the integer coordinate system by the Jacobian It is important to give information about what you are choosing.

However, such consideration is not given to the solid curvature in the conventional technique.

Next, the affine transformation will be described. In the field of mathematics, what is called congruential transformation is studied in the field of affine geometry. For example, the congruence condition between figures defined on a two-dimensional plane means a condition under which two figures completely overlap each other after an appropriate equal-area affine transformation (translation and rotation). Also, the similarity corresponds to the equal-area affine transformation with the scaling transformation. This is simply called affine transformation here.

Therefore, it can be understood that the verification of the signature is almost equivalent to the similarity or congruence of the curved figure.
However, even for the same person, the curved figures obtained each time the signature is made are slightly different, and the respective signature curves do not always completely match in the affine transformation described above.
In other words, there are inherent human errors in the signature. However, it is also true that there is a system called signature on the assumption that the difference between them is minute.
In other words, it is natural to think that each element of the set of signature curves signed by the same person has a certain average curve that is invariant to the affine transformation, and fluctuates around it.

Since there is an error inherent in the act of performing the signature itself, it is necessary to minimize the error due to the processing system of the signature verification process. In other words, the processing algorithm is
It is essential that it is consistent or approximately consistent with the affine transformation.

However, the conventional signature handwriting verification method and apparatus (Japanese Patent Application Laid-Open Nos. 10-171926 and 10-40).
388, Japanese Patent Laid-Open No. 5-324805), since pattern matching using discrete Cartesian coordinates is performed, such an affine transformation is not invariant but causes various problems as described below. It was

Furthermore, it is very difficult to request that two curved figures coincide with each other except for the degree of freedom of affine transformation, for a figure described as an actual drawn curve. Must be considered. A "line" in a digitizer has a thickness and is not a mathematically exact line. That is, the input device 302 such as the digitizer in FIG.
1 has a resolution determined by the hardware, and FIG.
When a curved figure is expressed as two-dimensional image data as shown in (a) and (b), the figure strongly depends on the expression method due to the quantization error.

However, this dependency appears to represent a strict figure when viewed by human eyes when the characteristic size of the curved figure is sufficiently large compared to the size of the pixel of the image data. It is of a degree. On this illusion,
We generally deal with image data.

However, such a feeling can be easily applied to a mathematical quantity (for example, pseudo curvature in this case, information of grid data determined from Cartesian coordinates in evaluating similarity), and mathematically strict If you make a definition without gender, you lose logicality and rationality.

In mathematics, for some objects A and B,
In order to define how close A and B are, it is necessary to introduce a topology. Even in the current problem, some kind of topology (topology) must be introduced to make the comparison. At this time, the phase must be a weak phase (topology) that solves the problem that the actual "line" has a thickness and the problem of quantization error, discretization error, such as the degree of bending. Further, when finally determining the identity (congruency) of the figures, the algorithm must be invariant or approximately invariant to the affine transformation.

This requirement is met by the pseudo-curvature and x of the conventional example.
The conventional signature verification method of processing with the y coordinate sequence is not satisfied. For example, as shown in FIG. 19, it is immediately understood that the pseudo-curvature formed in the conventional example is not invariant to affine transformation, particularly rotation.

As shown in FIG. 19 (a), when the straight line forming the line figure is aligned with the pixel grid, the dot number and the arc length are linked by linear conversion in which the magnification is multiplied. However, when a straight line is slanted as shown in FIG. 19B, the pixels for expressing it become jagged, and the ratio between the number of pixels and the length required for expression may not be constant. As shown in FIG. 19B, in actuality, in order to express a nearly straight line of √2 (pixels) having an angle of 45 degrees, three pixels are required as pixels, and the number of pixels and the length are reduced. A difference of about twice may appear.

Reflecting this, the graph of the above-described conventional example with the pseudo curvature distribution function (whether the first or the second is taken) is as shown in FIG. 20 with respect to FIG. Figure 2
At 0, the horizontal axis is the arc length s (the number of pixels), the vertical axis is the tangent angle (pseudo-curvature), the thick line corresponds to the pixel direction of FIG. 19A, and the thin curve is shown in FIG. This is the case when it is peeled in the oblique direction of b). The pseudo-curvature function greatly changes its appearance with respect to the transformation called rotation.

Conversely, with respect to the graph of the same number of pixels and the pseudo curvature, the completely different figures are recognized as the same figure by changing the rotation direction and the like.

In order to correct these inconsistencies, a conventional example (JP-A-10-171926, JP-A-10-4038).
8, JP-A-5-324805) adopts a correction method using a neural network. However, it is generally difficult to reproduce mathematically reasonable information from something that is not mathematically well defined.

Further, in Japanese Patent Laid-Open Nos. 5-324805, 10-171926, and 10-40388, corrections are made by using a fuzzy method or a dynamic programming method. However, these errors include corrections due to poor mathematical definition, which reduces the reliability of signature verification.

The present invention has been made in view of the above problems of the prior art, and an object of the present invention is to appropriately compare various physical quantities at the time of inputting a handwriting and realize accurate collation. It is also an object of the present invention to reduce the influence of discretization error, which is approximately invariant to the affine transformation, and to enable more accurate pattern matching for writing input.

[0042]

An information processing apparatus according to the present invention for achieving the above object has the following configuration.
That is, two-dimensional pattern information including a sequence of coordinate points handwritten via a coordinate input device, an acquisition means for acquiring physical information at the time of handwriting input, and a plurality of patterns represented by the two-dimensional pattern information. First conversion means for approximating the segmented line segment curve by approximating it by connecting line segments, and dividing the arc length along the segmental line segment curve into equal parts along the curve.
Generating means for generating a three-dimensional lattice point sequence; second converting means for converting the physical information acquired by the obtaining means into a function of the one-dimensional lattice point sequence to generate a physical value distribution; the pattern information and the And a collating unit that collates the information input by handwriting based on the physical value distribution.

Further, in the information processing method according to the present invention for achieving the above-mentioned object, the two-dimensional pattern information including the coordinate point sequence written and input through the coordinate input device and the physical information at the time of the writing and input are written. An acquisition step of acquiring; a first conversion step of approximating the pattern represented by the two-dimensional pattern information by connecting a plurality of line segments into a piecewise line segment curve; A generation step of equally dividing the arc length to generate a one-dimensional grid point sequence along the curve, and a physical value distribution by converting the physical information acquired in the acquisition step into a function of the one-dimensional grid point series. A second conversion step to generate,
And a collating step of collating the information written and input based on the pattern information and the physical value distribution.

[0044]

Preferred embodiments of the present invention will be described below with reference to the accompanying drawings.

<First Embodiment> FIG. 1 is a diagram showing an example of a dot row after the signature handwriting targeted in the present embodiment is digitized by a digitizer. As shown in Figure 1,
A digitizer writes a signature written with a fine brush to a N-dot array A = {(x [i], y in a two-dimensional integer lattice.
[i]), i = 1, ..., N}.

The data used is taken in at minute time intervals. On average, two dot rows are captured at intervals such that they are adjacent as a figure. At this time, there is a portion where the same pixel is overlapped in the slow speed portion.

Further, a portion which is not written by one stroke is also adopted as one row of dot as time series data. Figure 2
FIG. 4 is an explanatory diagram of a dot row of the processing of this embodiment for a signature. In other words, the signature characters are generally considered to be a set of curves that are not connected to each other as shown in FIG. 2A, but what is defined here is that the non-connected parts are arranged in chronological order. , Which is effectively a single stroke (Fig. 2
(B)) is adopted. This adopted curve is called a signature curve.

As a conversion taking into consideration that the original figure and the figure represented by the two-dimensional pixel match in the modulo pixel resolution, the pixel is divided into the segmental line segment figure as shown in FIG. 3A (a). Information below resolution is ignored and the original figure is restored. At that time, a cut-off parameter for up to what resolution is taken in is introduced, and conversion to a segmental line segment figure is performed as described later with reference to FIG. Since the original figure is defined by the point sequence A, it can be approximately defined as a figure that is invariant to the affine transformation. This is converted into a line segment sequence B as described later in detail. The line segment sequence B is obtained by appropriately thinning out the data of the point sequence A. Thus, the sequence of dots shown in FIG. 1 becomes a sequence of line segments as shown in FIG.

Further, since the arc length can be well defined in the piecewise line segment figure, the angle function φ of the tangent angle to the arc length s
(S) etc. can be well defined. Therefore, after calculating the total arc length for the obtained line segment data, it is divided by a constant natural number M to form a point sequence {s (i)} of equal width with respect to the arc length. By this, the arc length is standardized, and the one that is invariant to the similarity transformation is handled.

The tangent angle φ is not invariant to the rotational degree of freedom of the affine transformation. Therefore, it is made invariable by converting this into a relative value unique to the figure. Specifically, as the reference point of φ (s (i)), the inclination of the line segment connecting the start point of the point sequence and the end point of the point sequence is set to zero.

Further, by utilizing the correspondence between the vertices of the line segments given as a function of time from the start of the signature and the time, {s (i) | i = 1, The time {t (s (i)) | i = 1, ..., M} at each point where the start time is zero is calculated by converting the time from the signature start time with…, M} by linear interpolation or the like. , Store in memory. By using the correspondence between this time and the arc length, the writing pressure time series data of the fine brush at the time of signature {p (ti) | i =
1, ..., N} is a function {p (s (i)) | i = 1, ..., Of arc length {s (i)}
Convert to M} and store. Also, if necessary, the Euler angle components {(α (ti), β (t
i), γ (ti)) | i = 1, ..., N} can be measured by a small gyro or optical means, and the time-series data of the angle change of arc length {s (i)} Function {(θ (s (i)), ψ (s (i))) |
It may be converted into i = 1, ..., M} and stored. Also, using the time {t (s (i))} passing through each point from the start of the signature, the velocity at each vertex {s (i)} is {u (s (i)) | i = 1,
,, M} is defined and stored.

By the above procedure, the point sequence is converted into the line segment sequence, and the time series data can be converted into the geometric data called the arc length. This is a geometrical parameter,
The signature is obtained by taking in geometrical information as visual information and correcting it. Depending on the progress of the signature, the speed of the brush may change or interruption may occur for a short period of time.

Therefore, it is rational to employ geometric data, which is the amount of information to be corrected, as a reference parameter for signature verification. Therefore, the arc length is adopted as a reference parameter when matching the signature data.

It should be noted here that the effect of the Jacobian pointed out in the prior art need not be considered in the piecewise line segment figure. That is, it is assumed that a piecewise line segment figure as shown in FIG. 3A (a) is considered for the point sequence in FIG. 1 and points on the corresponding line segment are given to the points on the point sequence. In that case, starting from a certain point on the line segment sequence, when tracing the line segment sequence, the correspondence of how many point sequences exist for the corresponding line segment is as shown in FIG. 4A. . What can be seen from FIG. 4A is that the graph is not a straight line. Therefore, if the pixel number is the argument of curvature, the Jacobian must be taken into consideration.

Considering the change amount of a plurality of physical quantities related to a signature with the arc length as a parameter. This is (a) of FIG. 4B. Here, the writing pressure recorded as time series data {p
(t _i ) | i = 1, ..., N} converted as a function of the vertex sequence (arc length) {s (i)} {p (s (i)) | i = 1, ..., M} ( FIG. 4B (b)) and the progress rate of the signature {u (s (i)) | i = 1, ..., M}
(FIG. 4B (c)) and the amount of change in the tangent angle at each vertex as shown below were adopted as a function of the vertex sequence (arc length) {s (i)}. However, when there is no corresponding sampling point, linear interpolation is performed. By the above procedure, the sequence of points was converted into a sequence of line segments, and the time series data could be converted into geometric data called arc length. Arc length is a geometrical parameter.
The signature is performed while taking in geometric information as visual information and correcting it, and the speed of the brush may change significantly (stop) or may be interrupted for a short period depending on the progress of the signature. , Converting to geometrical parameters is very good for managing data as visual information.

The contact angle will be described below for a while.

As shown in FIG. 3A (b), the horizontal axis is the arc length,
If the vertical axis is the angle of the corresponding portion, the feature of the figure can be expressed as a step (Heaviside) function. At this time, there is a degree of freedom of parallel movement in the tangent angle φ in the modulus 2π. This means the degree of freedom of where to set the angle to zero when measuring the tangent angle, and corresponds to the degree of freedom of rotation in the affine transformation. In this embodiment, the direction of a straight line connecting the start point and the end point of the signature curve is adopted as the reference angle of zero angle.

As shown in FIG. 3B, the tangent angle distribution of FIG. 3A (b) is obtained by determining the tangent angle of each of the line segments a to j with the parallel line as an angle of zero, and the length according to the arc length of these line segments. As a step function with.

In FIG. 3A (b), the correspondence between the arc length and the tangent angle is expressed as a continuous one. However, on a computer, the figure is drawn along the arc length by about 1 pixel length or more. Divide into equal parts, calculate the angle distribution on the divided one-dimensional grid points on the arc, and see the correspondence between the two. This is shown in the graph of FIG. 3A (c). Here, the discretized angular distribution is described as φ (s (i)). However, the total number of divisions M is a constant value.

Further, in this embodiment, as the signature distribution function, the tangent angle distribution, the writing pressure distribution, the signature progressing speed, etc. (φ (s (i)), p (s ( i)), u (s (i)))
, The average value of about 10 signatures is used as the standard distribution,
This may be stored in a storage device in the collating device in advance, or an IC
It is acquired through a card or computer network and stored in the memory of the matching device. Then, the standard distribution existing in the memory and the standard distribution directly calculated from the input data as described above are compared to obtain the collation of the person.

That is, the signature matching apparatus of the present embodiment uses the information such as the standard distribution to perform pattern matching that incorporates, for example, a normal pattern matching method or a dynamic programming method, and compares it with a standard signature curve. It will evaluate the equivalence of signatures.

The signature verification apparatus according to the first embodiment will be described in more detail below.

FIG. 5 is a view showing the outer appearance of the signature verification apparatus according to this embodiment. As shown in FIG. 5, the signature verification apparatus includes a main body 111, a digitizer 114, and a card 115.
It is composed by. Further, FIG. 6 is a block diagram showing a device configuration of the signature verification apparatus shown in FIG.

In FIG. 5 and FIG. 6, 111 is a main body of the signature verification apparatus, and 114 is a digitizer. The digitizer is composed of a fine-pointed pen 113 and a writing table 112. The writing table 112 includes a sensing unit and an A / D converter (not shown) assembled in a two-dimensional grid, and changes the position where pressure is applied with the tip of the pen 113 into a digital signal in a time series manner to the main body 111. I am sending it to. Further, the pen 113 has a function of detecting writing pressure, monitors writing pressure in time series, and sends an analog signal to the writing table 112. In the A / D converter in the writing table 112, the analog signal of the writing pressure is synchronized with the digital signal of the pen position, converted into a digitized signal, and sent to the main body 111.

The entire device as described above is called a digitizer 114, and a signature character is used by this device to generate a time-series digital signal A.
= {(X [i], y [i]) | i = 1, ..., N}. At this time, the writing pressure time series data of the fine brush at the time of signature {p (t _i ) | i = 1,
,, N} is collected and saved as time series data. Also,
Since the recording time intervals of these time-series data are predetermined constant intervals and are synchronized with each other, the elapsed time at the sampling point is also recorded at the same time.

Further, the main body 111 includes the parameter input section 1
17, a monitor 118 for displaying a control process and a result parameter input instruction, and a standard data reading unit 11 for reading standard data 115 stored in a card or the like.
6, RAM 121, ROM 122, and control operation unit 120
And a standard data storage unit 123. The ROM 122 stores a control program for control, which will be described later with reference to the flowchart, and the control calculation unit 120 executes the control program.

In this embodiment, the signature character is restored from the digital signal obtained by signing the digitizer,
Considering it as a curve, the physical quantity associated with the signature is compared with reference data according to the arc length of the curve.

As described above, the actual signature character is as shown in FIG.
Although it is composed of separate curves as shown in (a), since it is given in time series, it can be regarded as a single stroke as shown in FIG. 2 (b). It can be reduced to a classification problem.

These line segments are shown in FIG.
Sampling of evenly spaced time on a two-dimensional lattice as in (c), N point sequence A = {(x [i],
y [i]) | i = 1, ..., N} is reduced to time series data. i
Corresponds to the progress of time. In addition, the data is taken in at minute time intervals, and the distance between adjacent dot rows ｜ (x [i], y [i]) − (x [i-1], y [i-1] ) | Is taken in at a time interval such that it becomes 1 dot or less. At this time, there is a portion where the same pixel is overlapped in the slow speed portion. Signed characters are generally considered to be a collection of curves that are not connected to each other except at intersections, but what is defined here is that the unconnected parts also follow the time series,
Effectively one-stroke writing is used. This adopted curve is called the signature curve as described above.

At the time of digitization, the writing pressure time-series data {p (t _i ) | i = 1, ..., N} of a fine brush at the time of signature is sampled at equal intervals as shown in FIG. 4B (a). Collect it. If necessary, use Euler angle components {(α (t _i ), β (t _i ), γ (t _i )) | i = 1, ..., N} for small gyro or optical Alternatively, time series data of the angle change may be collected beforehand.

In this embodiment, signature verification is performed by classifying and comparing the physical quantities collected as described above.

Even in writing to the digitizer, problems such as tilt, enlargement / reduction, parallel movement, etc., such as the affine conversion, which is pointed out as a problem of the conventional example, are routinely performed. It is an object of the present embodiment to provide a signature verification method and a signature verification device that are invariant to such conversion. In fact, the data obtained in FIG.
With the data obtained in (d), although the figure is slightly tilted and only enlarged, various problems as pointed out in the problems of the conventional example are included, and xy-coordinates are included. It becomes impossible to deal with by pattern matching by.

In the first place, the signature is made in time series by changing and changing the font of the signature written by the person who makes the signature, while obtaining visual information. In other words, it should be considered as a feedback system. Generally, at the time of signature, depending on the visual information, you can change the holding of the pen at a certain point,
It should be considered that there is a gap. In that case, the elapsed time is not always a good parameter for the signature. On the other hand, the information to be captured as visual information is information as an affine figure of a font written by a person who makes a signature. In other words, it recognizes the difference between your standard signature and the signature you are currently writing, and changes the next operation accordingly. At that time, the recognized difference is a deviation from the similarity of the figures. Therefore, the parameters that characterize the signature curve must be able to more accurately represent the affine geometrical properties. In the conventional signature verification method and the like, since the viewpoint of affine geometry is lacking, the information is distorted by various unnatural conversions. In the present invention, the arc length, which is a parameter for comparing physical quantities, is invariant to affine transformation. That is, the most natural amount is used in the signature. Therefore, unnecessary conversion is not required. The process flow of this embodiment will be described with reference to the flowchart of FIG.

Initialization is performed in step S0. In this initialization, an IC card or the like is read by the standard data reading unit 116.
The standard data 115 obtained by reading the standard data 115 or the standard data read from the standard data storage unit 112
Load it on M121. At this time, the standard data storage unit 112 may be a hard disk or the like inside the apparatus, or a storage device such as a hard disk at a remote place where data is stored through a computer network.

Next, in step S1, when a signature is input by the input person, the handwriting is digitized by a digitizer, and writing pressure data is collected.
Transfer the data to the arithmetic unit. Next, in step S2,
Converts dot data into segmental line segment data. That is, the point sequence shown in FIG. 1 is converted into line segment data as shown in FIG. 3A (a). The converted data is the RAM of FIG.
It is stored on 121.

As a result, the error at the time of conversion into two-dimensional image data is reduced, and the affine property of the original figure is approximately restored. In addition, by dividing the line into 2
Measures derived from the natural measure of the dimensional plane can be defined on the line segment, freeing the Jacobian problem described in the "Problems to be solved by the invention" section.

Here, the method adopted in the above-described line segmentation in step S2 will be described as follows. In this embodiment, the one described in JP-A-1-295376 is used.

The vertex sequence of the line segment sequence is represented as a subset B = {(Vx [i], Vy [i]) | i = 1, ..., R} of the coordinate point sequence A.
Here, how to extract the subset B from the point sequence A is
This is the problem of line segmentation of point sequences. The threshold value vtxth0 is set in advance.
Is set to a constant value.

From the above assumption, both ends of the corresponding curve of the coordinate point sequence A may be already known. The line segmentation process will be described below with reference to the flowchart of FIG. 8 and the specific example shown in FIG.

First, the outline of the line segmentation process will be described with reference to FIG. As shown in FIG. 9A, first, both ends of the pattern are connected by line segments. This is called a line segment of hierarchy 1. The distance r [i] (i = 1, ..., From the coordinate point (the entire pattern at this point) in the area sandwiched from the line segment by the ends of the line segment.
N). The maximum value of the obtained distance r [i] is vtx
If it is smaller than th0, no further line segmentation is performed, and the line segment of layer 1 connecting both ends is determined as the line segment sequence to be obtained.

FIG. 9A shows the case where the maximum distance is larger than vtxth0, and the point 1021 is the point having the maximum distance. In this case, the point 1021 is set as one of the new apex sequences, as shown in FIG. 9B. As a result, the hierarchy is raised by one and the obtained point sequence is used as the vertex sequence of the hierarchy 2.

The above operation is repeated on each line segment as follows. Let the current hierarchy be K (> 1). Attention is paid to one line segment in the line segment sequence of the hierarchy K. Let r [i] (i = j1, ..., j2) be the distance from the line segment of the subsequence of the coordinate point sequence A in the region sandwiched by the ends of the line segment, and let r [i] (i =
j1, ..., j2) is obtained. If the maximum one of the calculated distances (maximum distance d) is smaller than vtxth0, the line segment is made a part of the line segment sequence to be obtained. At this time, it is assumed that the corresponding line segment has converged for the hierarchy K, and the hierarchy is changed from K to K +.
Even if the number is increased to 1, the corresponding portion of the line segment sequence does not change.

If the maximum distance d is larger than vtxth0, the point having the maximum value is set as one of the vertex rows in the next hierarchy K + 1. This operation is performed for all unconverged line segments in the same layer, and after performing all line segments on layer K, the layer is moved up from K to K + 1.

By repeating such an operation, if the hierarchy is deep enough, the coordinate points are finally finite, so that all the line segments converge, that is, all the point sequences correspond to vtxth0 from the corresponding line segment. The sequence of line segments can be configured to be at a smaller distance.

By the method as described above, a line segment sequence (piecewise line segment curve) as shown in FIG. 9D is obtained with respect to FIG. 9A. This piecewise line segment curve is an ordered figure in a two-dimensional plane composed of a time-series dot row in a two-dimensional integer lattice obtained by the digitizer 114, and is divided into a plurality of lines with a resolution larger than the pixel resolution of the digitizer 114. It is obtained by dividing into minutes. FIG. 8 is a flow chart showing the above processing. The line segmentation process in a general case will be described with reference to FIG.

First, at the same time as the start of step S101, initialization is performed. That is, the layer K is set to 1, and both ends of the curve are set to both ends of the line segment of the layer 1. Next, step S10
In step 2, it is checked whether or not the i-th line segment of interest exceeds the final line segment of the line segment sequence of the hierarchy K.

If the i-th line segment is not the final line segment of the line segment sequence of the hierarchy K, the maximum value of the distance from the line segment of the corresponding coordinate point in the line segment is calculated in step S103. Then, in step S104, if the maximum distance d of the line segment is larger than vtxth0, the process proceeds to step S105, and the i-th line segment is divided at the place having the maximum distance d to divide into two line segments. If the maximum distance d of the line segment is smaller than vtxth0 in step S104, the process directly proceeds to the next line segment. That is, the line segment is treated as converged.

In step S106, the process moves to the next line segment in the line segment sequence in the same hierarchy K. Here, step S102 is performed again.
Then, it is checked whether or not the ith line segment of interest is the last line segment of the line segment sequence of the hierarchy K. The above steps S103 to S106 are repeated until the final line segment of the line segment row of the hierarchy K is repeated.

If the maximum distance d is smaller than vtxth0 in all the line segments in step S108, step S109
Then, the order is changed and the process goes to the end of step S110.
If all the line segments have not converged in step S108, the hierarchy is raised by one in step S107 and the process proceeds to step S102. The above process is repeated, and finally all converge and end.

In the above process, vtxth0 can also be used as a parameter for determining the resolution, and the resolution can be changed rationally. The parameters can be changed by using the parameter input unit 117 shown in FIG.

Further, the line segment sequence thus obtained is considered to approximately represent the original figure as described above, and it is considered that the affine degrees of freedom lost when the line pattern was replaced with the two-dimensional image data. Is reproduced approximately again.

In fact, when the straight line shown in FIG. 10 (a) is aligned with the pixel grid and the straight line is slanted as shown in FIG. 10 (b), the same tangent angle distribution is obtained. There is. That is, as shown in FIG. 11, it can be seen that the affineness is approximately restored. In FIG. 11, the horizontal axis is the arc length, the vertical axis is the tangent angle, the thick line corresponds to the pixel direction in FIG. 10A, and the thin curve is drawn in the diagonal direction in FIG. 10B. This is the case. For the transformation of rotation,
Unlike the pseudo-curvature function of, the relationship between the tangent angle and the arc length gives almost the same distribution.

Returning to FIG. 7, in step S3, the line segment is equally divided along the arc length from the end. The number of divisions is a predetermined number M, and the total arc length is equally divided into M pieces.

In step S4, the writing pressure time-series data {p (ti) | i of the fine brush at the time of signature as shown in FIG. 4B (a).
= 1, ..., N} is a function {p (s (i))} of arc length {s (i)} (Fig. 4B
(B)) and stored in the RAM 121. Also,
The speed at each vertex {s (i)} is defined as {u (s (i))} ((c) in FIG. 4) from the time of passing each point from the start time of the signature and stored in the RAM 121. To do.

Next, in step S5, the tangent angle distribution is calculated. First, a straight line defined by the start and end points of the signature curve is selected and used as the reference angle. With this direction as the angle of zero, the tangent angle at each division point is determined. The tangent angle φ is the curvature dφ / ds
Since it is the amount of integration by the arc length of, even if it is a non-differentiable curve, the non-differentiable point can be defined if the velocity is zero.
At least it can be defined in the sense of hyperfunction theory.

The contact angle distribution, the writing pressure distribution, and the signature progress velocity distribution (φ [i], obtained by the above steps S4 and S5)
p [i], u [i]) = (φ (s (i)), p (s (i)), u (s (i)))
Is taken as a function of arc length.

In step S6, this is shown in FIG.
The tangential angle distribution, the writing pressure distribution, the standardized signature progression speed (φ _ref [i], p _ref [i], u _ref [as a function of the arc length, which is the standard pattern as shown by the bold line in (d)]. i]). How to compare

[0098]

[Equation 2] S is calculated as, and determined from the value of S. Here, c is a speed normalizing factor, the maximum speed is standardized to be 1, and δv is the minimum evaluation speed. Anything smaller than this is regarded as an evaluation value because the signature is temporarily suspended. Not adopted. Further, α, β, and γ are weights of the respective evaluation values, and depending on the case, two of them may be set to zero.

If necessary, some standard patterns may be prepared and the shape may be classified by determining which one is the closest.

Thereafter, the end display and the matching result are displayed on the monitor 118 of FIGS. If the matching result is greater than or equal to the threshold value, the signature is the same as the standard signature and the same person is determined.

As a method of creating the standard signature angle distribution as the standard pattern, the standard signature angle distribution may be obtained by averaging several signatures of the above-mentioned angle distribution at each point. In the present embodiment, such a function is configured by using the device described in FIGS. 5 and 6, and a standard pattern is created.

As described above, according to the above-described embodiment, the arc length of the curve can be defined mathematically skillfully and can be a good parameter for describing the system when the signature character is viewed as geometric information. I understand.

Further, a conventional example (Japanese Patent Laid-Open No. 5-324805,
(JP-A-10-171926, JP-A-10-40388)
In the above, the time axis was adopted as the reference parameter, and various physical quantities were compared as time series data. However, when a signature is changed, if the pen is held at some point or there is a gap, the elapsed time is always good for the signature. It cannot be a parameter. Therefore, various corrections were required when it was used as a reference parameter for signature verification. On the other hand, according to the present embodiment, since the standardized arc length of the input handwriting is used, a physical quantity such as writing pressure can be obtained as a good parameter. In other words, the signature is usually performed in a bright place, which is important in the act of signing with visual information, and changes in physical quantities such as writing speed and writing pressure when correcting the font of the signature by visual information can also be verified by the person. It is very important for us. The present invention takes such importance into consideration. A method that does not consider feedback by visual information at the time of signature, for example, a method that employs time as a comparison parameter cannot completely eliminate the error caused by the matching algorithm. In fact, in expressing a curve, if you use inappropriate parameters such as the number of pixels, you cannot reflect the characteristics of the system,
It has been described in "Problems to be solved by the invention" that the processing is completely artificial. Similarly, in comparing a certain object, if the symmetry of the system, that is, the convertibility and the invariance to the conversion are insufficiently considered, a completely meaningless process is performed. In the present embodiment, in consideration of the characteristic of the signature that the person who performs the signature himself or herself takes in a character or curve that is written over time as visual information through his or her own eyes, and signs while correcting with that information, this is the basis for the correction. It uses parameters that are affine invariant and consistent (more accurately, approximately consistent).

According to the present embodiment, it is possible to provide a signature verification apparatus that is invariant (more accurately, approximately invariant) to the affine transformation and is less affected by discretization error. In addition, the physical quantity is compared using the arc length as a parameter, which is consistent with the characteristic of the signature that the signature is provided with feedback by visual information, thereby reducing the error from the verification system when verifying the signature. I am able to do it.

Further, an object of the present invention is to supply a storage medium storing a program code of software for realizing the functions of the above-described embodiment to a system or apparatus, and to supply a computer (or CPU) of the system or apparatus.
It is needless to say that it can be achieved by reading and executing the program code stored in the storage medium.

In this case, the program code itself read from the storage medium realizes the functions of the above-described embodiments, and the storage medium storing the program code constitutes the present invention.

As a storage medium for supplying the program code, for example, a floppy disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a CD
-R, magnetic tape, non-volatile memory card, ROM, etc. can be used.

Further, by executing the program code read by the computer, not only the functions of the above-described embodiment are realized, but also the OS (operating system) running on the computer based on the instruction of the program code. It is needless to say that this also includes a case where the above) performs a part or all of the actual processing and the processing realizes the functions of the above-described embodiments.

Further, after the program code read from the storage medium is written in the memory provided in the function expansion board inserted into the computer or the function expansion unit connected to the computer, based on the instruction of the program code, It goes without saying that a case where the CPU or the like included in the function expansion board or the function expansion unit performs some or all of the actual processing and the processing realizes the functions of the above-described embodiments is also included.

[0110]

As described above, according to the present invention,
Various physical quantities at the time of handwriting input can be appropriately compared, and accurate collation can be realized. Further, it is approximately invariant to the affine transformation, the influence of the discretization error is reduced, and the pattern matching with respect to the handwriting input can be performed more accurately.

[Brief description of drawings]

FIG. 1 is a diagram showing an example of a dot row after digitizing a signature handwriting targeted in the present embodiment by a digitizer.

FIG. 2 is an explanatory diagram of a dot row of processing of the present embodiment for a signature.

FIG. 3A is a diagram illustrating a process of the first embodiment for the input data shown in FIG.

FIG. 3B is a diagram illustrating the tangent angle distribution shown in FIG. 3A.

FIG. 4A is a diagram showing a correspondence between an arc length along a line segment and the number of point sequences corresponding to the line segment.

FIG. 4B is a diagram illustrating a change amount of a plurality of physical quantities related to a signature with an arc length as a parameter.

FIG. 5 is a diagram showing an appearance of the signature verification apparatus according to the present embodiment.

6 is a block diagram showing a device configuration of the signature verification apparatus shown in FIG.

FIG. 7 is a flowchart showing a signature verification procedure in the signature verification device of the first exemplary embodiment.

FIG. 8 is a flowchart illustrating a procedure of line segmentation processing according to the first embodiment.

FIG. 9 is a diagram illustrating line segmentation processing according to the first embodiment.

FIG. 10 is an explanatory diagram showing the effect of the curve classification method used in the present embodiment.

FIG. 11 is an explanatory diagram showing the effect of the curve classification method used in the present embodiment.

FIG. 12 is a diagram showing a schematic configuration of a general signature verification apparatus.

FIG. 13 is a diagram showing an example of a curve fitted to a two-dimensional surface.

FIG. 14 is an explanatory diagram of a method of classifying curves according to a conventional technique.

FIG. 15 is a diagram illustrating the definition of curvature in the conventional technique.

FIG. 16 is a flowchart illustrating a conventional method of classifying curves.

FIG. 17 is a diagram illustrating a contact angle.

FIG. 18 is a diagram illustrating uncertainty of dots representing the same line segment.

FIG. 19 is a diagram illustrating a problem in the conventional technique.

FIG. 20 is a diagram illustrating a problem in the conventional technique.

   ─────────────────────────────────────────────────── ─── Continued front page    F term (reference) 5B043 AA09 BA06 DA07 EA05 GA05                       GA13                 5B057 CA02 CA06 CB02 CB06 CB12                       CB16 CC01 CF05 DB02 DB05                       DB08 DC03 DC34                 5B068 AA05 BD02 BD13 BD17 BE06                       CC19

Claims (16)

[Claims] 1. Two-dimensional pattern information including a sequence of coordinate points handwritten by a coordinate input device, an acquisition unit for acquiring physical information at the time of the handwriting input, and a pattern represented by the two-dimensional pattern information. And a one-dimensional lattice point along the curve by dividing the arc length along the segmental line segment curve into equal parts Generating means for generating a sequence; second converting means for converting the physical information acquired by the acquiring means into a function of the one-dimensional grid point sequence to generate a physical value distribution; the pattern information and the physical value distribution An information processing apparatus, comprising: a collating unit that collates information written and input based on the above. 2. The generating means divides the arc length along the piecewise line segment curve into equal parts so that the number of pre-division points becomes a predetermined number, thereby forming a one-dimensional grid point sequence along the curve. The information processing apparatus according to claim 1, wherein the information processing apparatus is generated. 3. An angle between a line passing through the start point and the end point of the handwritten pattern and the piecewise line segment is obtained for each grid point of the one-dimensional grid point sequence, and the tangent angle of the piecewise line segment is determined. The tangential angle distribution generating means for generating a distribution is further provided, and the collating means collates information input by handwriting based on the tangential angle distribution and the physical value distribution. The information processing device described. 4. The acquisition unit acquires the physical information in association with time, and the second conversion unit acquires the physical information based on a writing time corresponding to each grid point on the one-dimensional grid point sequence. The information processing apparatus according to claim 1 or 2, wherein the physical information is converted into a function of the one-dimensional lattice point sequence to obtain a physical value distribution by extracting the. 5. The physical information includes a writing pressure at the time of inputting the writing, and the second conversion unit converts the writing pressure into a function of the one-dimensional lattice point sequence to generate a physical value distribution. The information processing apparatus according to claim 1, further comprising: 6. The physical information includes an inclination of an input pen at the time of the handwriting input, and the second conversion unit converts the inclination into a function of the one-dimensional grid point sequence to generate a physical value distribution. The information processing apparatus according to any one of claims 1 to 5, further comprising: 7. The physical information includes an input time of each point of the coordinate point sequence, and the second conversion means is an input pen passing through each point of the one-dimensional grid point based on the input time. The information processing apparatus according to claim 1, further comprising obtaining a velocity distribution as the physical value distribution. 8. Two-dimensional pattern information including a sequence of coordinate points handwritten through a coordinate input device, an acquisition step of acquiring physical information at the time of the handwriting input, and a pattern represented by the two-dimensional pattern information. Is approximated by connecting a plurality of line segments into a piecewise line segment curve, and a one-dimensional grid point along the curve is obtained by equally dividing the arc length along the piecewise line segment curve. A generation step of generating a column, a second conversion step of converting the physical information acquired in the acquisition step into a function of the one-dimensional grid point sequence to generate a physical value distribution, the pattern information and the physical value distribution An information processing method comprising: a collating step of collating information written and input based on the above. 9. The generating step divides an arc length along the piecewise line segment curve into equal parts so that the number of predivision points becomes a predetermined number, thereby forming a one-dimensional grid point sequence along the curve. The information processing method according to claim 8, which is generated. 10. The angle between the segmental line segment and a straight line passing through the start point and the end point of the handwritten pattern is determined for each lattice point of the one-dimensional lattice point sequence, and the tangent angle of the segmental line segment is determined. The method according to claim 8 or 9, further comprising a tangential distribution generating step of generating a distribution, wherein the collating step collates information input by handwriting based on the tangential distribution and the physical value distribution. Information processing method described. 11. The acquisition step acquires the physical information in association with time, and the second conversion step acquires the physical information based on a writing time corresponding to each grid point on the one-dimensional grid point sequence. The information processing method according to claim 8 or 9, wherein the physical information is converted into a function of the one-dimensional lattice point sequence to obtain a physical value distribution by extracting the. 12. The physical information includes writing pressure when the writing is input, and the second converting step converts the writing pressure into a function of the one-dimensional grid point sequence to generate a physical value distribution. The information processing method according to claim 8, further comprising: 13. The physical information includes a tilt of an input pen at the time of the handwriting input, and the second converting step converts the tilt into a function of the one-dimensional grid point sequence to generate a physical value distribution. The information processing method according to claim 8, further comprising: 14. The physical information includes an input time of each point of the coordinate point sequence, and the second conversion step is based on the input time of an input pen passing through each point of the one-dimensional grid point. The information processing method according to claim 8, further comprising obtaining a velocity distribution as the physical value distribution. 15. A storage medium for storing a control program for causing a computer to execute the information processing method according to claim 8. 16. A control program for causing a computer to execute the information processing method according to claim 8. Description: