Method of hashing vector data based on multi-scale curvature for vector content authentication

Abstract

The present invention relates to a method of hashing a perceptual vector model based on a multi-scale curvature. According to a first aspect, there is provided a method of hashing a perceptual vector model based on a multi-scale curvature including: generating a multi-dimensional feature coefficient matrix, and obtaining a multi-dimensional intermediate hash coefficient matrix; and obtaining a final binary hash matrix, and enabling the multi-dimensional binary hash matrix to be hierarchically authenticated. In addition, according to a second aspect, there is provided a method of hashing a perceptual vector model based on a multi-scale curvature including: generating a hash by using a hash function; and authenticating a vector model. In addition, an error detection probability for an object attack can be lower by about 2×10.sup.−5˜2.8×10.sup.−2, and a uniqueness probability is raised by about 0.014. In addition, an entropy can be raised by about 0.875˜2.149.

Claims

1. A method of protecting a digital model comprising a vector model from being tampered or copied, the method comprising: performing rectangular tiling by dividing the vector model into a plurality of rectangular tiles; and generating a hash for a tile among the plurality of rectangular tiles by using a hash function hash(M.R)=(H.θ) based on a multi-scale curvature, wherein M represents the vector model, R represents a random key, H represents a binary hash, and θ represents a parameter, wherein the hash is generated by: re-sampling objects within the tile; calculating a multi curvature for each scale; and generating the binary hash H by using a Lloyd-Max quantizer and a multi-scale curvature hash coefficient based on the key.

2. A method of authenticating a digital model comprising a vector model by using the hash generated according to claim 1, the method comprising: extracting a hash H′ by using a hash extraction function Dehash(M′.R.θ)=H′, wherein M′ represents the vector model to be authenticated, R represents the random key, and θ represents the parameter; and authenticating the digital model by comparing the H′ with the H.

3. The method of claim 1, wherein the performing rectangular tiling includes: generating M={Mj} obtained by dividing the vector model M having a NH×NV size into a rectangular tile having a Nh×Nv size; and generating M.sub.j={p.sub.i}.sub.i=1.sup.|M.sup.j.sup.| by extracting polygon and polyline objects among objects belonging to a number of layers within the divided tile, wherein when an entire size of the vector model M is NH×NV, and a ratio scale is 1/RS, the NH×NV size and an actual size of NH×NV is calculated as
(NH×RS×10.sup.−5)×(NV×RS×10.sup.−5)=NH×NV×RS.sup.2×10.sup.−10[km.sup.2]N.sub.H×N.sub.V×RS.sup.2×10.sup.−10[km.sup.2].

4. The method of claim 1, wherein, during the re-sampling objects, the objects are re-sampled in a same sampling interval, and re-sampled virtual vertices are generated, when an original object p={v.sub.i}.sub.i=1.sup.p is provided, a sample vertex for the same sampling interval δ is {circumflex over (p)}={v.sub.k}, when a sample vertex v.sub.k is between and v.sub.i−1, the sample vertex v.sub.k becomes v.sub.k=v.sub.k−1+Δd.sub.k, ∥Δd.sub.k∥=δ, v.sub.k=(x.sub.k,y.sub.k)=(x.sub.k−1+Δd.sub.x,y.sub.k−1+Δd.sub.y); f(x.sub.k)=y.sub.k by a cubic curve polynomial (cubic polynomial curve) expression corresponding to left/right four vertices {v.sub.k−2.Math.v.sub.k−1.Math.v.sub.i.Math.v.sub.i−1} which are two previous resampled vertices {v.sub.k−2.Math.v.sub.k−1} and two ensuing original vertices {v.sub.i.Math.v.sub.i−1}, herein, the sample vertex v.sub.k corresponding to two previous re-sampled vertices{v.sub.k−2.Math.v.sub.k−1} and two ensuing original vertices {v.sub.i.Math.v.sub.i+1} is represented as v.sub.k−2<v.sub.k−1<v.sub.k<v.sub.i<v.sub.i+1, and as a boarder tile of an object end point, when the sample vertex v.sub.k is before a last original vertex v.sub.n, that is v.sub.k−2<v.sub.k−1<v.sub.k<v.sub.n, or after, that is v.sub.k−2<v.sub.k−1<v.sub.n<v.sub.k, the sample vertex v.sub.k is determined by quadratic curve C.sub.k(v.sub.k): f(x)=a.sub.0+a.sub.1x+a.sub.2x.sup.2+a.sub.3x.sup.3 modeling that corresponds to three vertices of {v.sub.k−2.Math.v.sub.k−1.Math.v.sub.n}.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a view showing a process of generating a hash based on a multi-scale curvature (FIG. 1a), and authenticating a vector model by extracting a hash (FIG. 1b) which are purposed in a multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(2) FIG. 2 is a view showing an example of performing rectangular tiling and separating a layer within the tile, and a vector map having a transverse Mercator (TM) coordinate system in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(3) FIG. 3 is a view showing re-sampling of an arbitrary object in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(4) FIG. 4 is a view showing an example of a threshold variable l′ required when determining a primary object in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(5) FIG. 5 is a view showing re-sampling is performed when a spatial scale is s=1 and an interval is δ, and when a spatial scale is s=¼ and an interval is 4δ in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(6) FIG. 6 is a view showing a process of generating an intermediate hash matrix having a size obtained by using an object curvature energy for scales×curvatures×objects and partial exponential bell polynomials, and generating a binary hash matrix of m bits by using a Llyoyd-Max quantizer in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(7) FIG. 7 is a view showing a process of generating an intermediate hash coefficient by using a number of group coefficients of object curvature energies and a random coefficient in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

(8) FIG. 8 is a view showing an ROC curve of a hash authentication threshold in the multi-scale curvature based perceptual vector model hashing method according to an embodiment of the present invention.

DETAILED DESCRIPTION

(9) Hereinafter, an exemplary embodiment of the present disclosure will be described with reference to the accompanying drawings. In the following description, the same elements will be designated by the same reference numerals although they are shown in different drawings. Further, in the following description of the present disclosure, a detailed description of known functions and configurations incorporated herein will be omitted when it may make the subject matter of the present disclosure rather unclear.

(10) In the present invention, when any component “transmits” data or a signal to another component, the component may directly transmit the data or the signal to the other component, or may mean that data or signal may be transmitted to other components via at least one other component.

(11) A method for hashing a perceptual vector model based on a multi-scale curvature purposes a method of hashing a vector model based on a multi-scale curvature which provides a hierarchical authentication and has excellent robust, uniqueness, and security performances. Main features of the purposed vector model hashing methods are as follows.

(12) 1) Re-sampled object curvature action energy: a method purposed in the present invention generates a hash based on a multi-scale curvature action energy of a radius curvature, a turning angle curvature, and Gaussian curvature, and which is invariant for a rigid motion, and robust against shape deformation. Object re-sampling is robust against changes in a number of vertices such as vector model simplification, vertex interpolation, etc.

(13) 2) Random key based scale-curvature multi-dimensional hash authentication: a method purposed in the present invention generates a multi-dimensional hash based on a curvature action energy on a spatial scale, and authenticates a model by hash comparison for each dimension. Herein, an arbitrary hash coefficient is calculated by performing randomized mapping curvature action energy for each scale with a random coefficient by using partial exponential bell polynomials. Randomized mapping of the curvature action energy increases both security and uniqueness performances. The multi-dimensional hash enables hierarchical authentication in a scale and a curvature type according to a security level of public and private vector.

(14) Meanwhile, main symbols used in the present invention are as follows.

(15) 1) A Vector model M is configured with a number M of polylines and polygon objects p,

(16) 2) an object p is configured with a number |p| of vertices, that is p={v.sub.i}.sub.i=1.sup.p, a curve p that is v.sub.l−1v.sub.l is a group of line segments, and

(17) 3) the entire length of the object p is ∥p∥, and a number of vertices which are elements of the object is |p|.

(18) 4) A re-sampled object of p is {circumflex over (p)}, and a curvature for each vertex on a spatial scale s is t.sup.s. An average curvature energy per unit length of {circumflex over (p)}.sub.s is υ[{circumflex over (p)}.sub.s].

(19) 5) When a vector model M and a random coefficient R are provided, by a hash function hash(M.R)=(H.θ), a binary hash H and a parameter θ are generated. When a transmitted vector model M′, a parameter θ, and a random coefficient R are provided, by Dehash(M′.R.θ)=H′, a binary hash H is extracted.

(20) FIG. 1 is a view showing a process generating a hash based on a multi-scale (FIG. 1a) purposed in the present invention, and a process of authenticating a vector model by using a hash extraction process (FIG. 1b). Referring to FIG. 1, a method of hashing a perceptual vector based on multi-scale curvatures purposed in the present invention shows a process of authenticating a vector model by using generating a hash by a hash function hash(M.R)=(H.θ) based on a multi-scale curvature, and by using a hash extraction function Dehash(M′.R.θ)=H′. The purposed hash function is configured with: performing rectangular tiling, re-sampling object within the tile, calculating a multi-scale curvature for each scale, and generating a binary hash by using a key based multi-scale curvature hash coefficient and a Lloyd-Max quantizer.

(21) Then, rectangular tiling will be described in detail.

(22) First, when performing rectangular tiling, a vector map that is a vector model M with high capacity and accuracy includes main information for each tile such as roads, mountains, parks, buildings, etc., and is represented in a number of objects. Accordingly, in the vector model M, it is effective to authenticate the vector model M based on a hash for each tile.

(23) In the purposed method, the vector model M having a NH×NV size is divided in rectangular N.sub.H×N.sub.V tiles which are M={M.sub.j}, and polygon and polyline objects belonging to a number of layers within the divided tile are extracted, M.sub.j={p.sub.i}.sub.i=1.sup.|M.sup.j.sup.|. Herein, when the entire size of the vector model M is NH×NV, and a ratio scale is 1/RS, actual areas of NH×NV and N.sub.H×N.sub.V are as Formula 1 below.
(NH×RS×10.sup.−5)×(NV×RS×10.sup.−5)=NH×NV×RS.sup.2×10.sup.−10[km.sup.2]
N.sub.h×N.sub.v×RS.sup.2×10.sup.−10 [km.sup.2]  [formula 1]

(24) For example, in a vector map in which ratio scales are 1/10,000, and 1/100,000, the divided tiles respectively have an area of N.sub.HN.sub.V10.sup.−2[km.sup.2],N.sub.HN.sub.V[km.sup.2]. FIG. 2 is a view showing an example of performing rectangular tiling and separating into layers within the divided tile in a vector map having a transverse Mercator (TM) coordinate system.

(25) Hereinafter, generating a hash of the divided tile M.sub.j={p.sub.i}.sub.i=1.sup.M.sup.j will be described.

(26) First, object sampling will be described. FIG. 3 is a view illustrating re-sampling of an arbitrary object.

(27) While a geometric shape of the vector model is maintained, a number of vertices may be changed by polyline and polygon simplification or interpolation, or may be changed in positions by vertex random sampling. In the purposed method, for robustness of a hash, in generating and extracting a hash, objects are resampled in the same interval δ, and re-sampled virtual vertices are generated.

(28) When an original object p={v.sub.i}.sub.i=1.sup.p is provided, a sample vertex for sampling in the same interval δ is {circumflex over (p)}={v.sub.k}. When a sample vertex v.sub.k is between v.sub.i−1 and v.sub.i, as shown in FIG. 3, by a cubic curve polynomial expression (cubic polynomial curve) C.sub.k(v.sub.k):f(x)=a.sub.0+a.sub.1x+a.sub.2x.sup.2+a.sub.3x.sup.3 corresponding to four vertices {v.sub.k−2.Math.v.sub.k−1.Math.v.sub.i.Math.v.sub.i−1} which are two previous resampled vertices {v.sub.k−2.Math.v.sub.k−1} and two ensuing original vertices {v.sub.i.Math.v.sub.i−1}, v.sub.k may be as Formula 2 below.

(29) $\begin{array}{cc}{v}_k=v_{k-1}+\Delta d_k,.Math.\Delta d_k.Math.=\delta ,v_k=\left(x_k,y_k\right)=\left(x_{k-1}+\Delta d_x,y_{k-1}+\Delta d_y\right);f\left(x_k\right)=y_k& \left[\mathrm{Formula}2\right]\end{array}$

(30) Herein, v.sub.k corresponding to two previous re-sampled vertices {v.sub.k−2.Math.v.sub.k−1} and two ensuing original vertices {v.sub.i.Math.v.sub.i+1} is represented as v.sub.k−2<v.sub.k−1<v.sub.k<v.sub.i<v.sub.i+1. As a boarder tile of an object end point, when v.sub.k is before the last original vertex v.sub.n, that is v.sub.k−2<v.sub.k−1<v.sub.k<v.sub.n, or after, that is v.sub.k−2<v.sub.k−1<v.sub.n<v.sub.k, v.sub.k is determined by quadratic curve C.sub.k(v.sub.k):f(x)=a.sub.0+a.sub.1x+a.sub.2x.sup.2+a.sub.3x.sup.3 modeling that corresponds to three vertices of {v.sub.k−2.Math.v.sub.k−1.Math.v.sub.n}.

(31) Describing a cubic polynomial coefficient, parameters of a cubic curve are determined by a cubic polynomial regression model. In other words, in Formula 3 below which is a cubic polynomial expression, when a coefficient vector is A and a random error vector is E, a response vector T may be represented as Formula 4 below.

(32) $\begin{array}{cc}{C}_k\left(v_k\right);y=f\left(x\right),y_k=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+{\mathrm{.Math.}}_k\mathrm{for}\left\{v_{k-2},v_{k-1},v_i,v_{i+1}\right\}& \left[\mathrm{Formula}3\right]\\ Y=\mathrm{XA}+E,\left[\begin{array}{c}{y}_{k-2}\\ y_{k-1}\\ y_i\\ y_{i+1}\end{array}\right]=\left[\begin{array}{cccc}1& x_{k-2}& {x_{k-2}}^2& {x_{k-2}}^3\\ 1& x_{k-1}& {x_{k-1}}^2& {x_{k-1}}^3\\ 1& x_i& {x_i}^2& {x_i}^3\\ 1& x_{i+1}& {x_{i+1}}^2& {x_{i+1}}^3\end{array}\right]\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\end{array}\right]+\left[\begin{array}{c}{ϵ}_0\\ {ϵ}_1\\ {ϵ}_2\\ {ϵ}_3\end{array}\right]& \left[\mathrm{Formula}4\right]\end{array}$

(33) Polynomial regression coefficients estimated by using an ordinary least squares estimation are as Formula 5 below.
Â=(X.sup.TX).sup.−1X.sup.TY  [Formula 5]

(34) Then, describing a sampling interval δ, the sampling interval is determined by a length distribution of main objects p* having high ranking lengths among the entire objects.

(35) Setting an object length as a probability variable L=∥p*∥, when a maximum length is L.sub.max=max{∥p*∥}, a cumulative distribution function of L is F.sub.L(l)=Pr(L≤l), and an inverse function thereof is F.sub.L.sup.−1(Pr(L≤i))=l. Herein, a variable l′ corresponding to an inflection point F.sub.l″(l′)=0 of F.sub.l(l) may be calculated as Formula 6 below.
l′=F″.sub.L.sup.−1(0)  [Formula 6]

(36) Herein, the main objects P* are objects corresponding to ∥p*∥≥l′, and the primary objects have a ratio of 1−F.sub.l(l′)=1−Pr(L≤l′)=Pr(l′<L≤L.sub.max.) FIG. 4 is a view showing an example of a threshold variable of l′ required when determining a main object.

(37) In other words, FIG. 4 is a view showing a graph of a threshold variable setting example required when determining a main object on a cumulative distribution of vector model objects.

(38) When a group of main objects p* is P*, an average length ∥P*∥ of p* is as Formula 7 below.

(39) $\begin{array}{cc}.Math.\stackrel{\_}{P^{*}}.Math.=\frac{1}{.Math.\stackrel{\_}{P^{*}}.Math.}\underset{i=1}{\overset{.Math.p^{*}.Math.}{.Math.}}.Math.p_i^{*}.Math.,\mathrm{where}.Math.p^{*}.Math.=\underset{i=1}{\overset{.Math.p^{*}.Math.}{.Math.}}.Math.v_i-v_{i-1}.Math.& \left[\mathrm{Formula}7\right]\end{array}$

(40) |P*| is cardinality of a group P*, and represents a number of main objects p* which are elements. The sampling interval δ is determined by Formula 8 below by providing a minimum length min{∥v.sub.lv.sub.l−1∥∀p*∈P*} as ½ among all segments of main objects, and an average length of the main objects

(41) $\begin{array}{cc}\delta =\frac{\min \left\{.Math.\stackrel{\_}{v_l{v}_{l-1}}.Math.\forall p^{*}\in P^{*}\right\}}{2.Math.{\stackrel{\_}{P}}^{*}.Math.}& \left[\mathrm{Formula}8\right]\end{array}$

(42) A final re-sampled object is {circumflex over (p)}={v.sub.k|k∈[1.|{circumflex over (p)}|]}, a length thereof ∥{circumflex over (p)}∥ is as Formula 9 below, and a number of vertices of re-sampled objects is as Formula 10 below.

(43) $\begin{array}{cc}.Math.p.Math.=\underset{i=1}{\overset{.Math.p.Math.}{.Math.}}.Math.v_i-v_{i-1}.Math.<.Math.\hat{p}.Math.=\underset{k=1}{\overset{.Math.\hat{p}.Math.}{.Math.}}.Math.v_k-v_{k-1}.Math.& \left[\mathrm{Formula}9\right]\\ .Math.\hat{p}.Math.=.Math.\frac{.Math.p.Math.}{\delta }.Math.& \left[\mathrm{Formula}10\right]\end{array}$

(44) Then, a multi-scale curvature and curvature energy will be described, a multi-scale curvature is a sampling interval

(45) $\frac{\delta }{s}$
for each spatial scale s in a re-sampled object {circumflex over (p)}={v.sub.k|k∈[1.|{circumflex over (p)}|]}, and the re-sampled object is defined as Formula 11 below.
{circumflex over (p)}.sup.s={v.sub.k/s|k∈[1.Math.n.sub.s]} where n.sub.s=[|{circumflex over (p)}.sup.s|×s] s∈[1,½,⅓,¼, . . . ]   [Formula 11]

(46) As shown FIG. 5, in a spatial scale of s=1, re-sampling is performed in an interval δ, when s=¼, re-sampling is performed in a 4δ interval. In other words, when the spatial scale s becomes large, the object is precisely represented, and when s becomes small, the object is proximately represented.

(47) In the purposed method, for all vertices of a re-sampled object {circumflex over (p)}.sup.s for each scale, a multi-scale curvature [τ.sub.g.sup.s(k).Math.τ.sub.o.sup.s(k)k.Math.τ.sub.a.sup.s(k)] of a Gaussian curvature τ.sub.g.sup.s(k), a radius curvature τ.sub.g.sup.s(k), and a turning angle curvature τ.sub.a.sup.s(k) may be calculated by Formulas 12 to 14 below.

(48) $\begin{array}{cc}{\tau }_g^s\left(k\right)=\frac{\begin{array}{c}{\left({\hat{p}}^s\star \left(G_{\sigma }^{\prime }\right)\right)}_x\left(k\right){\left({\hat{p}}^s\star G_{\sigma }^{″}\right)}_y\left(k\right)-\\ {\left({\hat{p}}^s\star G_{\sigma }^{″}\right)}_x\left(k\right){\left({\hat{p}}^s\star G_{\sigma }^{\prime }\right)}_y\left(k\right)\end{array}}{{.Math.{\left({\hat{p}}^s\star G_{\sigma }^{\prime }\right)}_x\left(k\right).Math.}^3}\mathrm{where}{G}_{\sigma =1}\left[\frac{3}{11},\frac{5}{11},\frac{3}{11}\right]& \left[\mathrm{Formula}12\right]\\ {\tau }_r^s\left(k\right)=\frac{1}{{\gamma }^2\left(k\right)}& \left[\mathrm{Formula}13\right]\end{array}$
where y(k) is the radius of circumcircle on (v.sub.k/s−1v.sub.k/s,v.sub.k/s+1)

(49) $\begin{array}{cc}{\Gamma }_a^s\left(k\right)=.Math.\frac{2.Math.\angle \left(\stackrel{.fwdarw.}{v_{k-1}{v}_k,}\stackrel{.fwdarw.}{v_k{v}_{k+1}}\right).Math.}{.Math.\stackrel{.fwdarw.}{v_{k-1}{v}_k}.Math.+.Math.\stackrel{.fwdarw.}{v_k{v}_{k+1}}.Math.}.Math.\mathrm{where}\text{.Math.}.Math.\angle \left(\stackrel{.fwdarw.}{v_{k-1}{v}_k,}\stackrel{.fwdarw.}{v_k{v}_{k+1}}\right).Math.={\cos }^{-1}.Math.\frac{\stackrel{.fwdarw.}{v_{k-1}{v}_k}}{.Math.\stackrel{.fwdarw.}{v_{k-1}{v}_k}.Math.},\frac{\stackrel{.fwdarw.}{v_k{v}_{k+1}}}{.Math.\stackrel{.fwdarw.}{v_k{v}_{k+1}}.Math.}.Math.& \left[\mathrm{Formula}14\right]\end{array}$

(50) Then, the curvature energy will be described. An re-sampled object of an arbitrary object {circumflex over (p)}.sub.l for each scale is {circumflex over (p)}.sub.l={circumflex over (p)}.sub.l.sup.1.Math.{circumflex over (p)}.sub.l.sup.1/2.Math.{circumflex over (p)}.sub.l.sup.1/3.Math.{circumflex over (p)}.sub.l.sup.1/4, and curvature energyv[{circumflex over (p)}.sub.i.sup.s] per unit length thereof is defined as Formula 15 below.

(51) $\begin{array}{cc}\psi \left[{\hat{p}}_i^s\right]=\frac{1}{.Math.{\hat{p}}_i^s.Math.}\underset{k=1}{\overset{n_s}{.Math.}}{\tau }^2\left(\frac{k}{s}\right).Math.v_{k/s}-v_{k/s-1}.Math.,\mathrm{where}.Math.{\hat{p}}_i^s.Math.=\underset{k=1}{\overset{n_s}{.Math.}}.Math.v_{k/s}-v_{k/s-1}.Math.,\mathrm{for}s\in [1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\mathrm{.Math.}]& \left[\mathrm{Formula}15\right]\end{array}$

(52) Herein,

(53) 0$\tau \left(\frac{k}{s}\right)$
represents a curvature at a position

(54) $\frac{k}{s}.$

(55) In the present invention, a curvature energy ψ[{circumflex over (p)}.sub.i.sup.s] for each scale is simply marked as ψ.sub.i.sup.s. An average curvature energy ψ.sub.i for each curvature and scale or an object {circumflex over (p)}.sub.i is represented as a matrix having a scales×curvatures size as Formula 16 below.

(56) $\begin{array}{cc}{\hat{p}}_i.fwdarw.{\psi }_i=\left[\begin{array}{ccc}{v}_{g,i}^1& v_{o,i}^1& v_{a,i}^1\\ v_{g,i}^{1/2}& v_{o,i}^{1/2}& v_{a,i}^{1/2}\\ v_{g,i}^{1/3}& v_{o,i}^{1/3}& v_{a,i}^{1/3}\\ v_{g,i}^{1/4}& v_{o,i}^{1/4}& v_{a,i}^{1/4}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right]& \left[\mathrm{Formula}16\right]\end{array}$

(57) In the present invention, a scale s is defined as a scale of s ∈ scales=1.Math.½.Math.⅓.Math.¼. . . . . Multi-scale curvatures of a Gaussian curvature, a radius curvature, a turning angle are simply marked as curvature=[g, a, o].

(58) Then, an intermediate hash matrix based on a curvature energy will be described.

(59) First, curvature energy clustering will be described. A curvature energy ψ of unit per length for each scale and curvature of all re-sampled objects M.sub.j={{circumflex over (p)}.sub.l}.sub.i=1.sup.|M.sup.j.sup.|within the divided tile M.sub.j is a matrix having a scales×curvatures×M.sub.j size as Formula 7 below.
ψ={ψ}.sub.i=1.sup.|M.sup.j.sup.| where ψ.sub.i={ψ.sub.curvature,i.sup.s|∀s∈[1,½,⅓, . . . ], curvature ∈[g,o,a]},   [Formula 17]
where g: Direct Gaussian Curvature, o: Curvature Radius, a: Turning Angle Curvature

(60) In the purposed method, as an intermediate hash of the divided tile M.sub.j, as shown in FIG. 6, by using a curvature energy matrix having a scales×curvatures×|M.sub.j| size, an intermediate matrix (hash matrix) having a scales×curvatures size is defined.

(61) In other words, FIG. 6 is a view showing a process of generating an intermediate hash matrix having a size obtained by an object curvature energy for each scales×curvatures×objects and partial exponential bell polynomials, and generating a binary hash matrix of m bits by using a Llyoyd-Max quantizer.

(62) Meanwhile, when an object curvature energy ψ.sub.curvature.sup.s for an arbitrary scale s and a curvature type curvature is as Formula 18 below, object curvature energies are clustered in a number of groups based on Gaussian mixture model (GMM)—expectation maximization (EM).
ψ.sub.curvature.sup.s={ψ.sub.curvature,1.sup.s,ψ.sub.curvature,2.sup.s, . . . ,ψ.sub.curvature,|M.sub.j.sub.|.sup.s}  [Formula 18]

(63) In other words, after randomly selecting a number N.sub.B of initial variables θ.sub.n.sup.(0)=(ω.sub.n.sup.(0).Math.μ.sub.n.sup.(0).Math.Σ.sub.n.sup.(0)), n∈[1, N.sub.B], a number N.sub.B of groups based on GMM is obtained by calculating a variable θ.sub.n=(ω.sub.n.Math.μ.sub.n.Math.Σ.sub.n), n∈[1, N.sub.B] having a maximum log-likelihood of ψ.sub.curvature.sup.3 by applying E-step and M-step.

(64) $\begin{array}{cc}{G}_{\mathrm{curvature}.k}^s=\left\{{\psi }_{\mathrm{curvature},i}^s:\mathrm{Pr}\left({\psi }_{\mathrm{curvature},i}^s.Math.{\varphi }_k\right)>\left({\psi }_{\mathrm{curvature},i}^s.Math.{\varphi }_{k^{\prime }}\right),\forall k^{\prime }\ne k,\mathrm{and},k^{\prime }\in \left[1,N_B\right]\right\}& \left[\mathrm{Formula}19\right]\end{array}$

(65) Herein, a parameter group θ.sub.curvature.sup.s={θ.sub.curvature,k.sup.s=(ω.sub.curvature,k.sup.sμ.sub.curvature,k.sup.sΣ.sub.curvature,k.sup.s))|k∈[1.Math.N.sub.B]}, is information required for extracting a hash with a random coefficient key.

(66) An intermediate hash matrix will be described. Similar to a number of object curvature energies for a scale and for each curvature type, a hash key R having a scale×curvature×N.sub.B size with random coefficient is obtained by Formula 20 below.

(67) $\begin{array}{cc}R=\left\{r_{\mathrm{curvature}}^s.Math.\forall s\in [1,\frac{1}{2},\frac{1}{3},\mathrm{.Math.}],\mathrm{curvature}\in \left[g,o,a\right]\right\}\mathrm{where}{r}_{\mathrm{curvature}}^s=\left\{r_{\mathrm{curvature}}^s.Math.k\in \left[1,N_B\right]\right\}& \left[\mathrm{Formula}20\right]\end{array}$

(68) A group coefficient b.sub.curvature,k.sup.s of an arbitrary group G.sub.curvature,k.sup.s is defined as Formula 21 below by the product of an average curvature energy μ.sub.curvature,i.sup.s and a random coefficient r.sub.curvature,k.sup.s thereof as shown in FIG. 7.

(69) Meanwhile, FIG. 7 is a view showing a process of generating an intermediate hash coefficient by using a number of groups of object curvature energies and a random coefficient.
b.sub.curvature,k.sup.s=r.sub.curvature,k.sup.s×μ.sub.curvature,k.sup.s for k∈[1,N.sub.B]  [Formula 21]

(70) An intermediate hash coefficient h′.sub.curvature.sup.s curvature on an arbitrary scale and a curvature (s,curvature) is obtained by using partial exponential bell polynomials of a group coefficient {b.sub.curvature,k.sup.s}.sub.k=1.sup.N.sup.B of an average curvature energy, which is B.sub.n,m(b.sub.1,b.sub.2, . . . ,b.sub.N.sub.B). In other words, h′.sub.curvature.sup.s may be simply defined as Formula 22 below.

(71) $\begin{array}{cc}{h}_{\mathrm{curvature}}^{\prime s}=B_{n,m}\left(b_{\mathrm{curvature},1}^s,b_{\mathrm{curvature},2}^s,\mathrm{.Math.},b_{\mathrm{curvature},N_B}^s\right)=.Math.\frac{n!}{j_1!j_2!\mathrm{.Math.}{j}_{n-m+1}!}{\left(\frac{b_{\mathrm{curvature},1}^s}{1!}\right)}^{j_1}{\left(\frac{b_{\mathrm{curvature},k}^s}{2!}\right)}^{j_2}\mathrm{.Math.}{\left(\frac{b_{\mathrm{curvature},k}^s}{\left(n-m+1!\right)}\right)}^{j_{n-m+1}}& \left[\mathrm{Formula}22\right]\end{array}$

(72) In addition, when n−m−1=N.sub.B, h′.sub.curvature.sup.s may be schematically represented as Formula 23 below.

(73) $\begin{array}{cc}{h}_{\mathrm{curvature}}^{\prime s}=n!.Math.\left(\underset{k=1}{\overset{N_B}{.Math.}}\frac{1}{j_k!}{\left(\frac{b_{\mathrm{curvature},k}^s}{k!}\right)}^{j_k}\right)& \left[\mathrm{Formula}23\right]\end{array}$

(74) Herein, in the summation term, j.sub.1,j.sub.2, . . . ,j.sub.N.sub.B are negative integers satisfying two conditions of Formula 24 below.
j.sub.1+j.sub.2+ . . . +j.sub.N.sub.B=m
j.sub.1+2j.sub.2+3j.sub.3+ . . . +N.sub.BjN.sub.B=n  [Formula 24]

(75) In the purposed method, n set as n=N.sub.B+1,m=2, and a group coefficient is set to be N.sub.B=10. Herein, partial exponential bell polynomials B.sub.11,2(b.sub.1,b.sub.2, . . . ,b.sub.N.sub.B) are as Formula 25 below.

(76) $\begin{array}{cc}{B}_{11,2}\left(b_1,b_2,\mathrm{.Math.},b_{10}\right)=.Math.\frac{11!}{j_1!j_2!\mathrm{.Math.}{j}_{10}!}{\left(\frac{b_1}{1!}\right)}^{j_1}{\left(\frac{b_2}{2!}\right)}^{j_2}\mathrm{.Math.}{\left(\frac{b_{10}}{10!}\right)}^{j_{10}}=11!\left(\frac{b_1}{1!}\frac{b_{10}}{10!}+\frac{b_2}{2!}\frac{b_9}{9!}+\frac{b_3}{3!}\frac{b_8}{8!}+\frac{b_4}{4!}\frac{b_7}{7!}+\frac{b_5}{5!}\frac{b_6}{6!}\right)=11b_1{b}_{10}+55b_2{b}_9+165b_3{b}_8+330b_4{b}_7+462b_5{b}_6& \left[\mathrm{Formula}25\right]\end{array}$

(77) By the above polynomial expression, an intermediate hash matrix {acute over (H)} having a scales×curvatures size for all scales and curvature types is obtained as Formula 26 below.

(78) $\begin{array}{cc}{H}^{\prime }=\left[\begin{array}{ccc}{h}_g^{\prime 1}& h_0^{\prime 1}& h_a^{\prime 1}\\ h_g^{\prime 1/2}& h_0^{\prime 1/2}& h_a^{\prime 1/2}\\ h_g^{\prime 1/3}& h_0^{\prime 1/3}& h_a^{\prime 1/3}\\ h_g^{\prime 1/4}& h_0^{\prime 1/4}& h_a^{\prime 1/4}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\end{array}\right]& \left[\mathrm{Formula}26\right]\end{array}$

(79) Then, a binary hash matrix based on a Lloyd-Max quantizer will be described.

(80) A real number type coefficient {acute over (h)}.sub.curvature.sup.3 of an intermediate hash matrix {acute over (H)} is binarized to a hash coefficient h.sub.curvatrure.sup.s having mbit by using an mbit=(2.sup.m−level) Lloyd−Max Quantizer.

(81) Herein, two variables of the Lloyd-Max quantizer which are bin boundaries L and a replacement value (replacement value) z=({grave over (˜)}.sub.1.Math.{grave over (˜)}.sub.2.Math. . . . .Math.{grave over (˜)}.sub.2y) are determined by a test model and sample intermediate hash matrices {{acute over (H)}.sup.(t)}.sub.t=1.sup.1000 for 1000 keys.

(82) When a coefficient group h.sub.curvature.sup.s={h.sub.curvature.sup.s(t)}.sub.t=1.sup.1000 on an arbitrary (s,curvature) of the sample intermediate hash matrix {{acute over (H)}.sup.(t)}.sub.t=1.sup.1000 is provided, Bin boundaries L are L=(L.sub.1,L.sub.2, . . . ,L.sub.2.sub.m.sub.−1); min({acute over (h)}.sub.curvature.sup.s)<L.sub.1<L.sub.2< . . . L.sub.2.sub.m.sub.−1<max({acute over (h)}.sub.curvature.sup.s), and a quantization function for L is as Formula 27 below.
q({acute over (h)}.sub.curvature.sup.s)z.sub.j, for {acute over (h)}.sub.curvature.sup.s∈[L.sub.j,L.sub.j+1]  [Formula 27]

(83) Herein, in order to minimize a quantization error E(L,z), L and z are obtained by Formula 28 below.

(84) $\begin{array}{cc}E\left(L,z\right)=\underset{i=1}{\overset{2^m}{.Math.}}{.Math.q\left(h_{\mathrm{curvature}}^{\prime s}\right)-h_{\mathrm{curvature}}^{\prime s}.Math.}^2=\underset{j=1}{\overset{2^m}{.Math.}}\underset{h_{\mathrm{curvature}}^{\prime s}\in \left[L_j,L_{j+1}\right]}{.Math.}{\left(h_{\mathrm{curvature}}^{\prime s}-z_j\right)}^2& \left[\mathrm{Formula}28\right]\end{array}$

(85) In other words, in order to be a partial derivative for E(L,z) being 0, L and z are calculated as Formulas 29 and 30 below, then, the above calculation is repeatedly performed until there are no changes in L.sub.1.sup.new and L.sub.2.sub.m.sub.+1.sup.new compared to a previous result.

(86) 0$\begin{array}{cc}\frac{\delta E}{\delta z_j}=\underset{h_{\mathrm{curvature}}^{\prime s}\in \left[L_j,L_{j+1}\right]}{.Math.}2\left(h_{\mathrm{curvature}}^{\prime s}-z_j\right)=Q{z}_j^{\mathrm{new}}=\mathrm{average}\left\{h_{\mathrm{curvature}}^{\prime s}.Math.h_{\mathrm{curvature}}^{\prime s}\in \left[L_j,L_{j+1}\right]\right\}& \left[\mathrm{Formula}29\right]\\ \frac{\delta E}{\delta L_j}=0,L_j^{\mathrm{new}}=\frac{1}{2}\left(z_{j-1}^{\mathrm{new}}+z_j^{\mathrm{new}}\right),j=2,3,\mathrm{.Math.},2^m& \left[\mathrm{Formula}30\right]\end{array}$

(87) After obtaining a quantization parameter Q=(L.sub.curvature.sup.sz.sub.curvature.sup.s) for all scales and curvatures by the above process, a final binary hash matrix H is generated by using mbit quantizer for the intermediate hash matrix {acute over (H)} having a Q=(L.sub.curvature.sup.s, Z.sub.curvature.sup.s)size as the Formula 31 below.
Q({acute over (H)})=H, where q({acute over (h)}.sub.curvature.sup.sL.sub.curvature.sup.sz.sub.curvature.sup.s)=h.sub.curvature.sup.s  [Formula 31]

(88) Then, a hash authentication will be described.

(89) A hash data base HDB of vector model is configured as Table 1 below with quantization parameter Q.sub.nj and hashes H.sub.nj which are generated when a vector model M.sub.n, and a random key R.sub.nj are provided while generating a hash. In (M.sub.i,R.sub.ij,Q.sub.ij,H.sub.ij), a random key R.sub.ij is generated by a user, and is combined with a model M.sub.i so that a parameter and a hash are generated.

(90) TABLE-US-00001 TABLE 1 Parameter matrix Vector model Key matrix (mbit quantization) Hash matrix M.sub.1 R.sub.11 Q.sub.11 = (L.sub.11, z.sub.11) H.sub.11 R.sub.12 Q.sub.12 = (L.sub.12, z.sub.12) H.sub.12 . . . . . . . . . M.sub.2 R.sub.21 Q.sub.21 = (L.sub.21, z.sub.21) H.sub.21 R.sub.22 Q.sub.11 = (L.sub.22, z.sub.22) H.sub.22 . . . . . . . . . . . . . . . . . . . . . M.sub.n R.sub.n1 Q.sub.n1 = (L.sub.n1, z.sub.n1) H.sub.n1 R.sub.n2 Q.sub.n2 = (L.sub.n2, z.sub.n2) H.sub.n2 . . . . . . . . .

(91) In authenticating an arbitrary model M.sub.n and a user key R.sub.nj, a quantization parameter Q.sub.nj and a hash H.sub.ij for M.sub.n and R.sub.nj are found from an HDB, and a hash H.sub.nj=Hash(M.sub.n,Q.sub.nj:R.sub.nj) is extracted by using the parameter Q.sub.nj.

(92) When a normalized Hamming distance difference between the extracted hash H′.sub.nj and a primitive hash H.sub.nj is d(H.sub.nj,H′.sub.nj)<th, M.sub.n and K.sub.nj are authenticated. The normalized Hamming distance difference is as Formula 32 below.

(93) $\begin{array}{cc}d\left(H,H^{\prime }\right)=\frac{1}{\mathrm{scales}\times \mathrm{curvatures}}\underset{s=1}{\overset{\mathrm{scales}}{.Math.}}\underset{\mathrm{curvatures}=g,o,a}{\overset{}{.Math.}}.Math.h_{\mathrm{curvature}}^s-h_{\mathrm{curvature}}^{\prime s}.Math.& \left[\mathrm{Formula}32\right]\end{array}$

(94) Then, an authentication threshold th will be described.

(95) A threshold is determined by using a hypothesis experiment based on a receiver operation characteristic (ROC). In the hypothesis experiment, a normalized Hamming distance difference between hashes generated by 1000 keys on a vector data model and hashes extracted from attacked models thereof, and a true positive rate (TP) and a false positive rate (FP) are respectively measured by adjusting a threshold th having a range of [0, 0.5] in a unit of 0.05. A TP probability TP is a probability where a hash H′ of an attacked model M′ is authenticated to an original model M.sub.k, and a probability FP is a probability wherein the hash H′ of the attacked model M′ is authenticated to another model M.sub.k (Refer to Formula 33 below).
p.sub.TP=Pr[d(H,H′)<th]
p.sub.FP=Pr[d(H.sub.k,H′)<th]  [formula 33]

(96) An ROC that is an experiment result is as shown in FIG. 8, and a curve shown in FIG. 8, it is checked that TP is about 0.95 and FP is about 0.04 when a threshold th is 0.15 which means that the highest TP may be obtained in a low FP. Accordingly, in the present invention, a hash authentication threshold is determined as 0.15.

(97) In other words, FIG. 8 is a view showing an ROC curve of a hash authentication threshold.

(98) In the present invention, in order to perform hierarchical authentication and to prevent a copy of a vector model such as vector map with high accuracy, and design drawing, a vector model hashing based on a multi-scale curvature including robustness, uniqueness, and security performances is purposed. In the purposed hashing, by using representative curvatures which are a radius curvature, a turning angle curvature, and a Gaussian curvature, a multi-dimensional feature matrix based on a multi-scale curve action energy distribution of all polylines and polygon objects is generated. The multi-scale curvature action energy distribution is strong on a rigid motion and a form deformation, thus robustness against various attacks and uniqueness for a model are obtained.

(99) From the multi-dimensional feature coefficients, a multi-dimensional intermediate hash coefficient matrix is obtained by performing randomized mapping for a random coefficient with partial exponential bell polynomials.

(100) In addition, from a real number type intermediate hash coefficient matrix, a final binary hash matrix is obtained by using a Lloyd-Max quantizer.

(101) Herein, security and uniqueness performances for randomized mapping of a curvature action energy are required.

(102) For a multi-dimensional hash, a hierarchical authentication in a scale and a curvature type according to a security level of public and private vector models is possible.

(103) From the experiment result, it is checked that the purposed hashing is robust against an object attack such as object simplification, removing, copying, breaking, etc., and a security thereof is ensured since hash uniqueness for three types which are, a model-key, a key, and a model are excellent, and the purposed hashing has a higher differential entropy by about 0.875 to 1.149 than that of a conventional method.

(104) The present invention may be implemented as computer-readable code on a computer-readable recording medium. The computer-readable recording medium includes all types of storage devices in which computer system-readable data is stored.

(105) Examples of the computer-readable recording medium include Read Only Memory (ROM), Random Access Memory (RAM), Compact Disk-Read Only Memory (CD-ROM), magnetic tape, a floppy disk, and an optical data storage device. Furthermore, the computer-readable recording medium may be implemented as carrier waves (for example, in the case of transmission over the Internet).

(106) Moreover, the computer-readable medium may be distributed across computer systems connected via a network, so that computer-readable code can be stored and executed in a distributed manner. Furthermore, functional programs, codes, and code segments to implement the disclosed embodiments may be easily deduced by programmers skilled in the art thereof.

(107) Although the invention has been shown and described with respect to the preferred embodiments, and specific terms have been used, the preferred embodiments and specific terms are used in their general meaning only in order to easily describe the technical content of the present invention and to facilitate the understanding of the present invention, and are not intended to limit the scope of the present invention. It will be understood by those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention as defined in the following claims.