JP3732717B2 - Angle feature amount calculation method, similar angle search method, and computer-readable recording medium - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
  The present invention is a method for calculating an angle feature that makes it possible to calculate an angle feature that is expressed in a form that is correct and more suitable for human senses, and that is applied to a multidimensional spatial index as it is.Law and, Similar angle search method to search the angle stored in the database using the calculation technology of the angle featureLaw andIts angular featuresUsed to realize the quantity calculation methodLograComputer-readable recordingsRecording media andUsed to implement a similar angle search methodLograA computer-readable record ofAnd recording media.
[0002]
When searching or classifying multimedia information such as images, texts, and CGs, it calculates the similarity of the positional relationship between multiple objects that are its components, and the similarity between straight line information that appears in the composition Need to be calculated.
[0003]
Against this backdrop, the construction of technology that expresses the similarity of angles with high accuracy is screamed.
[0004]
[Prior art]
In general, the angle can be expressed as a straight line passing through the origin or a point on the straight line. For example, 45 degrees is expressed as a straight line “y = x” or a straight line passing through the origin and the point (1, 1).
[0005]
The following two types have been used as methods for expressing the feature quantity called the angle.
[0006]
(1) A method of expressing an angle as a segmented area
FIG. 16 shows an example of this expression method.
[0007]
In the example of this figure, all directions are divided into eight equal parts and divided into 12 directions including the vertical and horizontal axes. If each direction region is called Da1, Db1, Dc1, Dc2, Dd1, Da2, Da3, Db2, Dc3, Dc4, Dd2, Da4, “Da1 to Da4”, “Db1 to Db2”, “ “Dc1 to Dc4” and “Dd1 to Dd2” are regarded as the same angle, and the four angles are represented by 1 to 4 to obtain an angle feature amount.
[0008]
For example, since the point P1 is in the direction of Dc1, the feature amount is expressed as 3, the feature amount is expressed as 1 because the point P2 is in the Da2 direction, the feature amount is expressed as 1 because the point P3 is in the Da1 direction, and the point P4 is expressed as Since the direction is Db1, the feature value is expressed as 2, and since the point P5 is in the Db1 direction, the feature value is expressed as 2.
[0009]
This representation is simple. However, this expression method has the following problems.
[0010]
That is, it is not known at all whether the points in the same angle region are the same angle, an extremely close angle, or a slightly separated angle. Also, the degree of difference cannot be expressed for points that have entered different angular regions. In addition, there are cases where a point entering a different angle region is closer than a point entering the same angle region.
[0011]
For example, in the example of FIG. 16, when expressing the closeness of the point P1, the point P3, and the point P5 with respect to the point P4, it is said that the point P1, the point P5, and the point P3 are close to the point P4 in this order. However, according to this expression method, the point P4 and the point P5 are at the same angle, the point P4 and the point P1 are separated as much as the point P5 and the point P1, and the point P4 and Only the information that the point P3 is separated from the point P3 by the same distance as the point P5 and the point P3 is obtained.
[0012]
(2) Method of expressing with angle
FIG. 17 shows an example of this expression method.
[0013]
For example, the base axis direction at which the angle is 0 is determined as the x-axis direction, and the angle feature amount is represented by degrees or radians.
[0014]
According to this expression method, there is a problem that a cross section occurs in the vicinity of an angle of 0 and an angle of 180 degrees instead of the problem as in the above expression method.
[0015]
For example, when the point P3 shown in FIG. 17 is 10 degrees, the point P1 is 80 degrees, and the point P2 is 170 degrees, according to this expression method, the similarity between the points P3 and P1 is
abs (angle of point P3−angle of point P1) = 70 degrees
However, abs () indicates an absolute value.
And the similarity between point P3 and point P2 is
abs (angle of point P3−angle of point P2) = 160 degrees
It becomes.
[0016]
From this point, according to this expression method, it becomes an inconvenient state that the angle of the point P1 is closer than the angle of the point P2 when viewed from the point P3.
[0017]
In order to solve this problem, there is a method of preparing a plurality of base axes.
[0018]
For example, in addition to the feature quantity obtained by setting the x-axis to an angle 0, the feature quantity obtained by setting the y-axis to an angle 0 is obtained, and the smaller one of these is used as the final feature quantity. There is also a method.
[0019]
According to this method, when the point P3 when the x-axis is the base axis is 10 degrees, the point P1 is 80 degrees, and the point P2 is 170 degrees, the point P3 when the y-axis is the base axis is 100 degrees, P1 is 170 degrees and point P2 is 80 degrees.
[0020]
Therefore, the similarity between point P3 and point P1 is
min [abs (the angle of the point P3 at the x base axis−the angle of the point P1 at the x base axis),
abs (angle of point P3 at y-axis-angle of point P1 at y-axis)]
= Min (70,70) = 70
And the similarity between point P3 and point P2 is
min [abs (the angle of the point P3 at the x base axis−the angle of the point P2 at the x base axis),
abs (angle of point P3 on y-axis-angle of point P2 on y-axis)]
= Min (160,20) = 20
It becomes.
[0021]
According to the method of preparing a plurality of base axes as described above, the angle of the point P2 is closer than the angle of the point P1 when viewed from the point P3. However, this expression method has the following problems.
[0022]
In other words, information based on the y-axis can be calculated from information based on the x-axis, and can be realized by defining a distance function including the calculation. However, since the distance function is not a geometric distance such as Manhattan distance or Euclidean distance, the multidimensional spatial index cannot be used, which causes a problem of slow search.
[0023]
The feature vector used in the image search is high-dimensional (k-dimensional) point data, and a multidimensional spatial index is used to speed up the similarity search.
[0024]
For example, in a multidimensional spatial index according to the k-d tree method, a coordinate axis is cyclically selected from k coordinate axes, and the number of point groups in which the value for the selected coordinate axis increases and the number of point groups decreases. Create a multidimensional spatial index by dividing the point data so that they are almost equal, and when the point data to be searched is given, follow the multidimensional spatial index to obtain the point data Realizes high-speed search for similar point data.
[0025]
FIG. 18 illustrates the procedure for creating this multidimensional spatial index using two-dimensional point data as a specific example.
[0026]
According to the method of preparing a plurality of basic axes as described above, the distance function is not a geometric distance due to the input of the min operation, and this makes the search slow because the multidimensional spatial index cannot be used. is there.
[0027]
In this case, the case where the x-axis is used as the base axis and the case where the y-axis is used as the base axis are managed as separate information in the database, and an index is applied to each of them, and the two results are integrated (the above-described min operation operation) However, if this method is used, there will be a difference in the method of features such as other colors and shapes due to the integration operation. Another problem will be that it becomes difficult to integrate with.
[0028]
Furthermore, as a human sensation, when comparing several angles, even if there is a slight straight line deviation, it feels the same angle, but as the angle goes away, the characteristic that the degree of disagreement suddenly increases (sensation is proportional) Characteristic). In addition, the horizontal line and the vertical line are more sensitive than the diagonal line, and the horizontal line and the vertical line have a characteristic that they are perceived as inconsistent even if they are within an allowable range that can be determined to be the same.
[0029]
It is desirable to reflect these feelings when calculating the similarity. However, even though the prior art method of expressing with an angle (method (2)) can be incorporated as a distance function for calculating the similarity, in other words, as a data distribution stored in the database, As a feature vector that is a target of a multidimensional spatial index, it is not possible to express a sense corresponding to the degree of angle separation.
[0030]
[Problems to be solved by the invention]
As described above, according to the prior art method of expressing an angle in a segmented area, there is a problem that a correct similarity cannot be obtained and a detailed similarity cannot be obtained.
[0031]
Then, when following the prior art method of expressing with an angle, if the process of eliminating the cross section of the angle is realized with a distance function, the problem that the index can not be used, and in order to solve this, If separate indexes are used for dividing information, there is a problem that special processing for integrating the results becomes necessary. Furthermore, this prior art method has a problem in that the degree of angle perception felt by humans cannot be expressed as data.
[0032]
The present invention has been made in view of such circumstances, and can correctly represent angles (that is, the order of similarity is not reversed), and can further represent angles that match human senses (that is, specific angles). It is possible to express the feature that the similarity decreases sharply when the angle leaves, and can be applied to a multidimensional spatial index as it is (that is, high-speed similarity search is possible). It is an object of the present invention to provide a new angle feature quantity calculation technique having the characteristic of becoming and a similar angle search technique using the angle feature quantity calculation technique.
[0033]
[Means for Solving the Problems]
  [1] Configuration of angle feature amount calculation method of the present invention
  [1-1] First configuration
  In order to achieve the above object, an angle feature amount calculation method of the present invention is an angle feature amount calculation apparatus including a mountain curve storage means, an input means, a conversion means, an intersection calculation means, a feature value calculation means, and an output means. When executed, (b) the input means receives the angle to be processed, and (b) the conversion means converts the angle received by the input means into a straight line passing through the origin or a point on a straight line passing through the origin. And (c) the intersection calculation means reads a mountain shape stored in the mountain curve storage means or a curve having a shape converted therefrom, and obtains an intersection between the read curve and the straight line converted by the conversion means, D) The feature amount calculating means calculates the coordinate value of the intersection obtained by the intersection calculating means or the distance between the intersection and the origin, and obtains the calculated value as the feature value of the angle received by the input means, (E) Output means And processes to output the characteristic quantity of the determined angle of the feature amount calculating means.
  [1-2] Second configuration
  In order to achieve the above object, an angular feature amount calculation method of the present invention includes an angle feature storage means, an input means, a conversion means, an intersection calculation means, a feature quantity calculation means, and an output means. When executed by the apparatus, (b) the input means receives the angle to be processed, and (b) the conversion means determines the angle received by the input means as a straight line passing through the origin or a point on a straight line passing through the origin. (C) The intersection calculation means reads a plurality of curves having a shape stored in the angle curve storage means or a shape to be converted therefrom, and each of the read curves and the straight line converted by the conversion means (D) The feature quantity calculating means calculates the coordinate values of the plurality of intersections obtained by the intersection calculating means or the distances between the intersections and the origin, and the calculated values are used as vector elements. Features Calculated as a feature amount of the angle received by the input unit Le, is (E) output means, for processing to output the characteristic quantity of the determined angle of the feature amount calculating means.
  [1-3] Third configuration
  In order to achieve the above object, an angle feature amount calculation method of the present invention includes an angle curve storage means, an input means, a conversion means, a rotation means, an intersection calculation means, a feature value calculation means, and an output means. When executed by the feature quantity calculation device, (b) the input means receives the angle to be processed, and (b) the conversion means uses the angle received by the input means as a straight line passing through the origin or a straight line passing through the origin. (C) The rotation means generates a plurality of feature amount calculation straight lines by rotating the straight lines converted by the conversion means by coordinate conversion, and (d) the intersection point calculation means stores the angle curve storage. A curve having a mountain shape stored in the means or a shape converted therefrom is read out, and an intersection point between the read curve and each feature quantity calculation line generated by the rotation means is obtained, and (e) the feature quantity calculation means is , Intersection calculation Calculate the coordinate values of the intersections obtained by the stage or the distance between the intersections and the origin, and obtain a feature vector having the calculated value as a vector element as a feature quantity of the angle received by the input means, (F) Processing is performed so that the output means outputs the feature quantity of the angle obtained by the feature quantity calculation means.
  [2] Configuration of similar angle search method of the present invention
  In order to achieve the above object, a similarity angle search method of the present invention includes a multidimensional spatial index storage means, a first feature vector calculation means, a second feature vector calculation means, a search means, and an output means. When executed by the angle search device, (a) the first feature vector calculation means calculates the angle feature vector stored in the database using the angle feature amount calculation method of the present invention, and the feature vector A multi-dimensional spatial index is created, and the created multi-dimensional spatial index is stored in the multi-dimensional spatial index storage means. (B) The second feature vector calculation means uses the angular feature quantity calculation method of the present invention. The search key angle feature vector is calculated, and (c) the search means uses the multidimensional spatial index stored in the multidimensional spatial index storage means to calculate the search key angle calculated by the second feature vector calculation means. The searching angle with a feature vector similar to the feature vector, (d) output means, for processing to output the search result of the search means.
  Next, the present invention configured as described above will be specifically described.
  Book configured in this wayIn the invention, the angle to be processed is converted into a straight line passing through the origin or a point on the straight line passing through the origin, and an intersection between the mountain or a curve having a shape converted from the angle and the converted straight line is obtained, and the coordinates of this intersection are obtained. Processing is performed so that the value or the distance between the intersection and the origin is calculated as an angular feature.
[0034]
At this time, curves are prepared for a plurality of angles, intersections between the respective curves and converted straight lines are obtained, and feature vectors having feature values calculated from these intersections as vector elements are calculated as angle feature values. There are things to do.
[0035]
In addition, a plurality of feature amount calculation straight lines are generated by rotating the converted straight lines by coordinate conversion, intersections between the curves and these feature amount calculation straight lines are obtained, and feature values calculated from these intersection points are calculated as vectors. A feature vector as an element may be calculated as an angle feature amount.
[0036]
Thus, in the present invention, an angle curve having an angle shape is prepared.
[0037]
This chevron curve is a non-monotonic curve, and has a shape with a minimum point at both ends and a maximum point at the center in the section used for angle calculation. Includes a curve (for example, a curve having a valley shape) converted from the mountain-shaped curve, and an approximate shape of the curve by a plurality of straight lines. For example, a circle, an ellipse, a sin or cos curve, a quadratic curve, a normal distribution curve, or the like corresponds to a mountain curve.
[0038]
In the present invention, when an angle to be processed is given, first, the angle is converted into a straight line passing through the origin or a point on a straight line passing through the origin.
[0039]
A straight line passing through the origin (0, 0) and the point (a, b) is
y = (b / a) x
And a straight line with an inclination θ passing through the origin (0, 0) is
y = xtan θ
And passes through the point (1, tan θ).
[0040]
That is, if the slope is expressed in m, the straight line passing through the origin is
y = mx
And the point is (x, mx).
[0041]
According to this formula, when an angle to be processed is given, first, the angle is converted into a straight line passing through the origin or a point on a straight line passing through the origin.
[0042]
Subsequently, the intersection of this straight line and the prepared Yamagata curve is obtained. For example, as shown in FIG. 1, an intersection point between a straight line defined by a point P1 converted from an angle to be processed and a mountain curve defined by an ellipse is obtained, and a point P2 converted from the angle to be processed is obtained. Is obtained, and the intersection point between the straight line defined by the point P3 converted from the angle to be processed and the mountain curve defined by the ellipse is obtained. .
[0043]
Subsequently, the coordinate value of this intersection or the distance between this intersection and the origin is calculated as an angle feature amount. For example, as shown in FIG. 1, the y-coordinate value of this intersection is calculated as an angle feature amount.
[0044]
The feature amount of the angle calculated in this way can correctly represent the angle as can be seen from the point P3, because the angle of the point P2 is closer than the angle of the point P1. Furthermore, it is possible to express an angle that matches a human sense by reacting strongly in the vicinity of a specific angle and expressing the feature that the degree of similarity decreases sharply as the angle leaves.
[0045]
As described above, the angle curve includes a curve that is converted from the angle curve by scaling, parallel movement, and rotation of coordinates.
[0046]
Now, as shown in Figure 2, the coordinate rotation formula
x ′ = x cos θ−y sin θ
y ′ = xsin θ + ycos θ
The angle curve may be obtained by rotating the angle curve using, and the coordinate value of this intersection point or the distance between this intersection point and the origin may be calculated as an angle feature amount. As shown in FIG. The intersection may be obtained by rotating, and the coordinate value of the intersection or the distance between the intersection and the origin may be calculated as the feature amount of the angle.
[0047]
The number of dimensions of the angle feature vector (the number of base axes) is not limited to one, and any number may be used as long as it is one or more. In general, it is sufficient to correspond to the four directions of the vertical direction, the horizontal direction, the diagonally upward direction, and the diagonally downward direction, but it may be five or more. At this time, the chevron curve is made more sharp. In addition, it is preferable to increase the angle curve.
[0048]
In order to increase the number of dimensions of the angle feature vector, as shown in FIG. 4, angle curves are prepared for a plurality of angles, and the intersection points of each angle curve and a straight line are obtained. A feature vector having a calculated feature value as a vector element is calculated as an angle feature amount, or a plurality of feature amount calculation straight lines are generated by rotating a straight line by coordinate transformation as shown in FIG. Intersections between the curve and these feature amount calculation straight lines are obtained, and feature vectors having feature values calculated from these intersections as vector elements are calculated as angle feature amounts.
[0049]
The angle feature vector calculated in this manner reacts to a plurality of inclinations. From this, it becomes possible to express the angle more in line with human senses.
[0050]
The angle feature amount calculated by the angle feature amount calculation technique of the present invention described above has a property as a geometric distance. From this, a multidimensional spatial index can be used.
[0051]
Therefore, the angle feature quantity calculation technique of the present invention is used to calculate the angle feature vectors stored in the database, and a multi-dimensional spatial index for these feature vectors is created. The similar angle of the present invention is used to calculate a feature vector of a search key angle and to search an angle having a feature vector similar to the calculated feature vector of the search key angle using the created multidimensional spatial index. Since the search technology can be constructed, an angle similar to the search key angle can be searched at high speed from the angles stored in the database.
[0052]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, the present invention will be described in detail according to embodiments.
[0053]
FIG. 6 illustrates an embodiment of the angle feature quantity calculation apparatus 1 including the present invention.
[0054]
An angle feature quantity calculation device 1 according to the present embodiment according to this embodiment includes an input unit 10 that inputs angle data to be processed input from an input device 2, and a straight line that passes through the origin or the origin of the angle input by the input unit 10. The input unit 10 includes a conversion unit 11 that converts the points into a straight line passing through the curve, a mountain-shaped curve storage unit 12 that stores a mountain-shaped curve, and a straight line that the conversion unit 11 converts and a mountain-shaped curve that the mountain-shaped curve storage unit 12 stores. The feature amount calculation unit 13 that calculates the feature amount of the angle that is input, the feature amount storage unit 14 that stores the angle feature amount calculated by the feature amount calculation unit 13, and the angle feature amount that the feature amount storage unit 14 stores. And an output unit 15 for outputting to the output device 3.
[0055]
Here, the function of the angle feature quantity calculation device 1 is specifically realized by a program, and this program is stored in an appropriate recording medium such as a portable medium memory, a semiconductor memory, or a hard disk that can be read by a computer. It can be stored on a medium.
[0056]
The chevron curve stored in the chevron curve storage unit 12 is a non-monotonous curve, and has a shape having a minimum point at both ends and a maximum point at the center in a section used for angle calculation. This includes a curve that is converted from this chevron curve by scaling, parallel movement, and rotation, and an approximation of the approximate shape by a plurality of straight lines.
[0057]
FIG. 7 illustrates an example of an angle curve stored in the angle curve storage unit 12.
[0058]
As shown in this figure, the mountain-shaped curve storage unit 12 uses, for example, an ellipse as a mountain-shaped curve.
(X²/ A²) + (Y²/ B²) = 1
Is stored, and a quadratic curve is stored as a mountain curve,
y = -a (x-1)²+1
And using the cosine function as a chevron curve,
y = cos x
Is memorized.
[0059]
Here, when preparing a mountain-shaped curve with respect to a some base axis, those mountain-shaped curves may differ. For example, because the human sense is more sensitive in the vertical and horizontal directions than in the diagonal direction, the distortion of the ellipse prepared in the vertical and horizontal directions is made larger than the distortion of the ellipse prepared in the diagonal direction. May be.
[0060]
In general, since the angle is point-symmetric, it may be considered in the range of 180 degrees. However, when dealing with an angle having a direction, the technical contents described below may be extended to a range of 360 degrees. That is, when the direction of the straight line is required, for example, the point on the opposite side of the intersection of the ellipse and the straight line may be used.
[0061]
FIG. 8 illustrates an embodiment of a processing flow executed by the angle feature quantity calculating apparatus 1 of the present invention configured as described above.
[0062]
Next, according to this processing flow, the angle feature amount calculation process executed by the angle feature amount calculation apparatus 1 of the present invention configured as described above will be described in detail.
[0063]
When the angle feature quantity calculation apparatus 1 of the present invention configured as described above is requested to calculate an angle feature quantity, first, as shown in the processing flow of FIG. Input the target angle data.
[0064]
Subsequently, in step 2, the input angle is converted into a straight line passing through the origin (or a point on a straight line passing through the origin). That is, if the slope defined by the input angle is expressed by m, the straight line passing through the origin is “y = mx”, and the point on the straight line is (x, mx). The input angle is converted into a straight line passing through the origin (or a point on a straight line passing through the origin).
[0065]
Subsequently, in step 3, an intersection between the converted straight line and the mountain curve stored in the mountain curve storage unit 12 is obtained, and the y-axis value (or the distance from the origin of the intersection) of the intersection is obtained as an angular feature amount. In the subsequent step 4, the calculated angular feature amount is output, and the process ends.
[0066]
In this way, when an ellipse is used as the angle curve, as shown in FIG. 1, the intersection of the straight line converted from the angle to be processed and the angle curve defined by the ellipse is obtained, and the intersection The y-axis value (or the distance from the origin of the intersection point) is calculated as the angle feature amount.
[0067]
The feature amount of the angle calculated in this way can express the angle correctly as described in FIG. 1, and further reacts strongly in the vicinity of a specific angle, and the degree of similarity decreases sharply when the angle leaves. Being able to express features makes it possible to express angles that match human sensations.
[0068]
FIG. 9 illustrates another embodiment of the angle feature quantity calculating apparatus 1 including the present invention.
[0069]
The angle feature amount calculation apparatus 1 according to the present embodiment according to this embodiment includes an input unit 10 described in FIG. 6, a conversion unit 11 described in FIG. 6, and a rotation matrix storage unit 16 that stores a rotation matrix of coordinate rotation. Using the rotation matrix stored in the rotation matrix storage unit 16, the line group generation unit 17 that generates a line group by rotating the straight line converted by the conversion unit 11, and the line group generated by the line group generation unit 17 Input from the input unit 10 from the straight line group storage unit 18 to be stored, the mountain curve storage unit 12 described in FIG. 6, the straight line group stored in the straight line group storage unit 18 and the mountain curve stored in the mountain curve storage unit 12. A feature amount calculation unit 13a that calculates the feature amount of the angle, a feature amount storage unit 14 that stores the angle feature amount calculated by the feature amount calculation unit 13a, and an angle feature amount that the feature amount storage unit 14 stores. Output unit 15 that outputs to 3 .
[0070]
Here, the function of the angle feature quantity calculation device 1 is specifically realized by a program, and this program is stored in an appropriate recording medium such as a portable medium memory, a semiconductor memory, or a hard disk that can be read by a computer. It can be stored on a medium.
[0071]
FIG. 10 shows an embodiment of a processing flow executed by the angle feature quantity calculating apparatus 1 of the present invention configured as described above.
[0072]
Next, according to this processing flow, the angle feature amount calculation process executed by the angle feature amount calculation apparatus 1 of the present invention configured as described above will be described in detail.
[0073]
When the angle feature amount calculation apparatus 1 of the present invention configured as described above receives an angle feature amount calculation request, first, as shown in the processing flow of FIG. Input the target angle data. Subsequently, in step 2, the input angle is converted into a straight line passing through the origin (or a point on a straight line passing through the origin).
[0074]
Subsequently, in step 3, using the rotation matrix stored in the rotation matrix storage unit 16, a straight line group (or point group) obtained by rotating the converted straight line (or point) is obtained.
[0075]
For example, four rotation matrices are prepared as a rotation matrix stored in the rotation matrix storage unit 16: a rotation matrix of 0 degree rotation, a rotation matrix of 45 degree rotation, a rotation matrix of 90 degree rotation, and a rotation matrix of 135 degree rotation. When rotating the point P1 (x, y) representing the angle shown in FIG. 5 using these four rotation matrices,
(1) In case of 0 degree rotation
x '= x, y' = y
(2) In case of 45 degree rotation
x ′ = (2^1/2/ 2) (xy), y '= (2^1/2/ 2) (x + y)
(3) In case of 90 degrees
x '=-y, y' = x
(4) In case of 135 degree rotation
x '=-(2^1/2/ 2) (x + y), y '= (2^1/2/ 2) (xy)
The four points (x ′, y ′) are obtained.
[0076]
At this time, the inclination m ′ of each straight line is obtained by “m ′ = y ′ / x ′ (except when x ′ = 0)”.
[0077]
Subsequently, when it is determined in step 4 whether or not all the straight lines (or points) in the straight line group (or point group) obtained in step 3 have been selected, and when it is determined that not all are selected, Proceeding to step 5, one unprocessed straight line (or a point on a straight line passing through the origin) is selected from the straight line group (or point group) obtained in step 3 in a prescribed order.
[0078]
Subsequently, in step 6, an intersection between the selected straight line (or a point on a straight line passing through the origin) and the mountain curve stored in the mountain curve storage unit 12 is obtained, and the y-axis value (or the intersection) of the intersection is obtained. The distance from the origin) is calculated as a feature value, and the process returns to step 4.
[0079]
For example, when the angle curve stored in the angle curve storage unit 12 is an ellipse,
(X²/ A²) + (Y²/ B²) = 1
And the straight line formula selected in step 5
y = m’x
To obtain the x-axis value of the intersection by substituting
(X²/ A²) + ((M'x)²/ B²) = 1
To obtain the x-coordinate value of the intersection point, the x-axis value / y-axis value of the intersection point
x = ab / (a²m^'2+ B²)^1/2
y = abs (m′x)
When calculating the y-axis value of the intersection as the feature value, the y-axis value is calculated as the feature value.
[0080]
When the angle curve stored in the angle curve storage unit 12 is a quadratic curve, the equation of the quadratic curve
y = -a (x-1)²+1
And the straight line formula selected in step 5
y = m’x
To obtain the x-axis value of the intersection by substituting
ax²− (2a−m ′) x + (a−1) = 0
To obtain the x-coordinate value of the intersection point, the x-axis value / y-axis value of the intersection point
x = [(2a−m ′) + ((2a−m ′)²-4a (a-1))^1/2] / 2a
y = abs (m′x)
When calculating the distance from the origin of the intersection as the feature value, the distance L
L = (x²+ Y²)^1/2
Is calculated.
[0081]
On the other hand, when it is determined in step 4 that all the straight lines (or points) in the straight line group (or point group) obtained in step 3 have been selected, the process proceeds to step 7 where the feature value calculated in step 6 is a vector. A feature vector as an element is created and output as a final angle feature amount, and the process ends.
[0082]
In this way, when the embodiment shown in FIG. 9 is followed, as shown in FIG. 5, the feature vector represented by the histogram of feature values obtained in the embodiment shown in FIG. It will be calculated as a quantity.
[0083]
The feature quantity of the angle calculated in this way can express the angle correctly, and further, it can express the feature that it reacts strongly in the vicinity of a specific angle, and the similarity decreases sharply as the angle goes away. It is possible to express the angle according to the sense. In addition, since it is possible to obtain the feature quantity of the angle that reacts to a plurality of inclinations, it is possible to express the angle in accordance with the human sense.
[0084]
FIG. 11 illustrates another embodiment of the angle feature quantity calculation apparatus 1 including the present invention.
[0085]
The angle feature quantity calculation apparatus 1 according to the present embodiment according to this embodiment includes an input unit 10 described with reference to FIG. 6, a conversion unit 11 described with reference to FIG. 6, a mountain curve storage unit 12 described with reference to FIG. The rotation matrix storage unit 16 described in the above and a mountain curve group generation unit that generates a mountain curve group by rotating the mountain curve stored in the mountain curve storage unit 12 using the rotation matrix stored in the rotation matrix storage unit 16 19, a mountain-shaped curve group storage unit 20 that stores the mountain-shaped curve group generated by the mountain-shaped curve group generation unit 19, and a straight line converted by the conversion unit 11 and a mountain-shaped curve group stored in the mountain-shaped curve group storage unit 20. A feature amount calculation unit 13b that calculates the feature amount of the angle input by the unit 10, a feature amount storage unit 14 that stores the angle feature amount calculated by the feature amount calculation unit 13b, and an angle feature that the feature amount storage unit 14 stores. Output to output device 3 And a 15.
[0086]
Here, the function of the angle feature quantity calculation device 1 is specifically realized by a program, and this program is stored in an appropriate recording medium such as a portable medium memory, a semiconductor memory, or a hard disk that can be read by a computer. It can be stored on a medium.
[0087]
FIG. 12 and FIG. 13 show an embodiment of a processing flow executed by the angle feature quantity calculating apparatus 1 of the present invention configured as described above.
[0088]
Next, according to this processing flow, the angle feature amount calculation process executed by the angle feature amount calculation apparatus 1 of the present invention configured as described above will be described in detail.
[0089]
When the angle feature quantity calculating apparatus 1 of the present invention configured as described above is requested to generate a mountain-shaped curve group, first, as shown in the processing flow of FIG. When it is determined whether or not all of the rotation matrices stored in the table have been selected and it is determined that they have not been selected, the process proceeds to step 2, and the prescribed order is selected from the rotation matrices stored in the rotation matrix storage unit 16. Select one unprocessed rotation matrix according to
[0090]
Subsequently, in step 3, a new chevron curve is generated by rotating the chevron curve stored in the chevron curve storage unit 12 using the selected rotation matrix, and the new chevron curve is stored in the chevron curve group storage unit 20. After storing, return to Step 1.
[0091]
Then, when it is determined in step 1 that all the rotation matrices stored in the rotation matrix storage unit 16 have been selected, the process ends.
[0092]
In this way, when there is a request for generating a mountain-shaped curve group, a mountain-shaped curve group is generated by rotating the mountain-shaped curve stored in the mountain-shaped curve storage unit 12 using the rotation matrix stored in the rotation matrix storage unit 16. Then, it is processed so as to be registered in the mountain-shaped curve group storage unit 20.
[0093]
On the other hand, when there is an angle feature amount calculation request, the angle feature amount calculation apparatus 1 of the present invention configured as described above firstly, in step 1, as shown in the processing flow of FIG. Input angle data to be processed. Subsequently, in step 2, the input angle is converted into a straight line passing through the origin (or a point on a straight line passing through the origin).
[0094]
Subsequently, in step 3, when it is determined whether or not all the chevron curves stored in the chevron curve group storage unit 20 are selected, and when it is determined that all the chevron curves are not selected, the process goes to step 4. Going forward, one unprocessed mountain curve is selected from the mountain curve group stored in the mountain curve group storage unit 20 according to a prescribed order.
[0095]
Subsequently, in step 5, the intersection of the selected chevron curve and the straight line converted in step 2 is obtained, and the y-axis value of the intersection (or the distance from the origin of the intersection) is calculated as a feature value. Return to Step 3.
[0096]
On the other hand, when it is determined in step 3 that all the chevron curves stored in the chevron curve group storage unit 20 have been selected, the process proceeds to step 6 where a feature vector having the feature value calculated in step 5 as a vector element is obtained. Create it, output it as the final angular feature, and end the process.
[0097]
In this way, in the embodiment shown in FIG. 9, the angle feature vector is obtained by rotating the straight line converted by the converter 11, whereas in the embodiment shown in FIG. As described above, the angle-shaped feature vector is obtained by rotating the angle curve.
[0098]
From this, if the angle curves are the same, the angle feature vector obtained in the embodiment of FIG. 11 is the same as the angle feature vector obtained in the embodiment of FIG.
[0099]
The angle feature vector calculated by the angle feature amount calculation technique of the present invention described above (the feature amount obtained in the embodiment of FIG. 6 can also be regarded as a one-dimensional feature vector) is a geometric distance. As a property. From this, a multidimensional spatial index can be used.
[0100]
Therefore, it is possible to construct a similar angle search device 30 having the present invention as shown in FIG.
[0101]
When searching or classifying multimedia information such as images, texts, and CGs, it calculates the similarity of the positional relationship between multiple objects that are its components, and the similarity between straight line information that appears in the composition Need to be calculated. In addition, it is required to calculate the similarity of the positional relationship between a plurality of points and areas on the map.
[0102]
The similar angle search device 30 according to the present invention realizes high speed execution of the similar angle search process required in such a case.
[0103]
The similar angle search device 30 of the present invention according to this embodiment includes a database 31, a first feature vector calculation unit 32, a database addition management unit 33, a multidimensional spatial index addition unit 34, and a second feature vector. A calculation unit 35, a database search management unit 36, a similarity calculation unit 37, a multidimensional spatial index search unit 38, and a similarity search result output unit 39 are provided.
[0104]
The database 31 includes a feature vector DB 310 for storing an angle feature vector calculated by the above-described angle feature amount calculation technique of the present invention while taking correspondence with the angle, and a feature vector stored in the feature vector DB 310. Multi-dimensional spatial index 311.
[0105]
When the angle data to be registered in the database 31 is given, the first feature vector calculation unit 32 calculates the feature vector of the angle according to the angle feature amount calculation technique of the present invention described above.
[0106]
The database addition management unit 33 additionally registers in the feature vector DB 310 the correspondence relationship between the feature vector calculated by the first feature vector calculation unit 32 and the angle of the registration target that is the calculation source. The multidimensional spatial index adding unit 34 additionally registers the feature vector calculated by the first feature vector calculating unit 32 in the multidimensional spatial index 311.
[0107]
When an angle serving as a search key is given, the second feature vector calculation unit 35 calculates a feature vector of the angle according to the angle feature amount calculation technique of the present invention described above.
[0108]
The database search management unit 36 controls the multidimensional spatial index search unit 38 and the similarity calculation unit 37 to search for the ones similar to the search key angle from the angles registered in the database 31.
[0109]
The similarity calculation unit 37 calculates the similarity between the feature vector searched by the multidimensional spatial index search unit 38 and the feature vector calculated by the second feature vector calculation unit 35. The multidimensional spatial index search unit 38 searches the feature vector similar to the feature vector calculated by the second feature vector calculation unit 35 by tracing the multidimensional spatial index 311.
[0110]
The similar search result output unit 39 outputs angle information similar to the search key angle searched by the database search management unit 36.
[0111]
Here, the function of the similar angle search device 30 is specifically realized by a program, and this program is stored in an appropriate recording medium such as a portable medium memory, a semiconductor memory, or a hard disk that can be read by a computer. Can be stored.
[0112]
FIG. 15 illustrates an embodiment of a processing flow executed by the similar angle search device 30 of the present invention configured as described above.
[0113]
Next, according to this processing flow, the calculation process of the angle feature amount executed by the similar angle search device 30 of the present invention configured as described above will be described in detail.
[0114]
When there is a request for registration of an angle (feature vector), the similar angle search device 30 of the present invention configured as described above first registers in step 1 as shown in the processing flow of FIG. Input the target angle data. Subsequently, in step 2, the feature vector of the input angle is calculated using the above-described angle feature amount calculation technique of the present invention.
[0115]
Subsequently, in step 3, the feature vector of the calculated angle is additionally registered in the feature vector DB 310 while taking correspondence with the angle. Subsequently, in step 4, by tracing the multidimensional spatial index 311 and obtaining and adding the leaf position of the calculated feature vector, the calculated feature vector is additionally registered in the multidimensional spatial index 311. The process ends.
[0116]
On the other hand, when the angle search request is issued, the similar angle search device 30 of the present invention configured as described above first searches in step 1 as shown in the processing flow of FIG. Enter the key angle data. Subsequently, in step 2, a feature vector of the input search key angle is calculated using the above-described angle feature amount calculation technique of the present invention.
[0117]
Subsequently, in step 3, by tracing the multidimensional spatial index 311 and searching for a plurality of feature vectors close to the calculated feature vector, the search key angle is selected from the angles registered in the feature vector DB 310. Search for similar angles.
[0118]
Subsequently, in step 4, by calculating the similarity between the searched feature vector and the feature vector of the search key angle calculated in step 2, between the search key angle and the angle searched in step 3. And the angles retrieved in step 3 are sorted in descending order of similarity. Subsequently, in step 5, the sorted angles are output as search results, and the process ends.
[0119]
In this manner, the similar angle search device 30 of the present invention uses the angle feature vector calculated by the angle feature amount calculation technique of the present invention, and implements a high-speed search using a multidimensional spatial index, Processing is performed so that an angle similar to the angle is searched with high accuracy.
[0120]
The feature quantity of the angle calculated by the present invention described above can be applied as a feature quantity for the following similarity search, search result structuring, class ring, and self-organization. That is, it can be applied as a feature amount for the inclination of a straight line in an image, the inclination between objects in the image, the direction between points or areas on a GIS (geographic information system or electronic map), and the like.
[0121]
And the feature quantity of the angle calculated by the present invention can be applied to the angle and direction between the objects in the 3D space and the CG by arranging the reference direction in three dimensions. In addition, it can be easily used for Internet services using azimuth, direction and angle.
[0122]
【The invention's effect】
As described above, according to the present invention, it is possible to obtain a feature value that reacts to a specific inclination. In that case, the degree of similarity according to the degree of separation from the specific inclination can also be adjusted. From this, it becomes possible to express the angle feature amount suitable for human senses.
[0123]
And according to this invention, it becomes possible to obtain | require the feature-value which reacts with respect to several inclination. For example, if the mountain curve is a vertically long ellipse, the feature amount is sensitive to the vertical direction. If the mountain curve is a horizontally long ellipse, the feature amount is sensitive to the horizontal direction. If the mountain curve is a 45 degree ellipse, the feature amount is 45 degrees. It becomes a feature quantity sensitive to the direction of. From now on, it is possible to express the angle feature amount that matches the human sense by creating a feature vector using these as vector elements.
[0124]
Since the feature amount of the angle calculated in the present invention makes it possible to express the inclination of the angle as a data distribution, according to the present invention, it is possible to apply a multidimensional spatial index so that high-speed similarity can be achieved. Search becomes possible.
[Brief description of the drawings]
FIG. 1 is an explanatory diagram of the present invention.
FIG. 2 is an explanatory diagram of the present invention.
FIG. 3 is an explanatory diagram of the present invention.
FIG. 4 is an explanatory diagram of the present invention.
FIG. 5 is an explanatory diagram of the present invention.
FIG. 6 is an example of an embodiment of an angle feature amount calculating apparatus according to the present invention.
FIG. 7 is an example of an embodiment of an angle curve.
FIG. 8 is an example of a processing flow executed by the angle feature amount calculation apparatus of the present invention.
FIG. 9 is another embodiment of an angle feature amount calculating apparatus according to the present invention.
FIG. 10 is an example of a processing flow executed by the angle feature quantity calculation apparatus of the present invention.
FIG. 11 is another example of an embodiment of the angle feature amount calculation apparatus of the present invention.
FIG. 12 is an example of a processing flow executed by the angle feature quantity calculation apparatus of the present invention.
FIG. 13 is an example of a processing flow executed by the angle feature quantity calculation apparatus of the present invention.
FIG. 14 is an example of an embodiment of a similar angle search device of the present invention.
FIG. 15 is an example of a processing flow executed by the similar angle search device of the present invention.
FIG. 16 is an explanatory diagram of a conventional technique.
FIG. 17 is an explanatory diagram of the prior art.
FIG. 18 is an explanatory diagram of a multidimensional spatial index.
[Explanation of symbols]
1 Angle feature quantity calculation device
2 input devices
3 Output device
10 Input section
11 Conversion unit
12 Yamagata curve storage
13 Feature amount calculator
14 Feature value storage
15 Output section

Claims (6)

Yamagata curve storage means, input means, converting means, the intersection calculation means, a square of feature calculation method performed by the angle characteristic calculation apparatus having a feature amount calculating means and the output means,
The input means receives an angle to be processed,
Said conversion means, said angle degrees, converted to a point on the straight line passing through the straight line or the origin through the origin,
The intersection calculating means, reads out the curve having a shape which is converted Yamagata stored or from it to the chevron curve storage means, obtain the intersection of the straight line and the readout curve,
The characteristic amount calculating means calculates the distance between the coordinate values or pre Symbol intersection before Symbol origin of the intersection determines the calculated value as a feature value of said angle,
An angle feature value calculation method , wherein the output means outputs the feature value of the angle obtained by the feature value calculation means . Yamagata curve storage means, input means, converting means, the intersection calculation means, a square of feature calculation method performed by the angle characteristic calculation apparatus having a feature amount calculating means and the output means,
The input means receives an angle to be processed,
Said conversion means, said angle degrees, converted to a point on the straight line passing through the straight line or the origin through the origin,
The intersection calculating means, the reading a plurality of curves having a shape to be converted stored Yamagata or from Yamagata curve storage means, obtain the intersection of the straight line and each curve thus read out,
The feature quantity calculating means, front SL angular distance is calculated, and the feature vector of the calculated value as the vector elements between the coordinate value or the plurality of intersection points and the previous SL origin of the plurality of intersection obtained by the feature amount,
An angle feature value calculation method , wherein the output means outputs the feature value of the angle obtained by the feature value calculation means . Yamagata curve storage means, input means, conversion means, rotation means, an intersection calculating means, a ANGLE feature calculation method performed by the angle characteristic calculation apparatus having a feature amount calculating means and the output means,
The input means receives an angle to be processed,
Said conversion means, said angle degrees, converted to a point on the straight line passing through the straight line or the origin through the origin,
The rotating means generates a plurality of feature amount calculation straight lines by rotating the straight lines by coordinate transformation ,
The intersection calculating means, the reading of the curve having a shape which is converted Yamagata stored or from Yamagata curve storage means, obtain the intersection of the the respective feature amount calculation linearly and the readout curve ,
The feature quantity calculating means, front SL angular distance is calculated, and the feature vector of the calculated value as the vector elements between the coordinate value or the plurality of intersection points and the previous SL origin of the plurality of intersection obtained by the feature amount,
An angle feature value calculation method , wherein the output means outputs the feature value of the angle obtained by the feature value calculation means . Multidimensional space index storage unit, the first feature vector calculating means, a second feature vector calculating means, retrieval means and class to be executed in a similar angle search apparatus comprising output means similar angle search method,
The first feature vector calculating means, using the angle feature amount calculating method according to any one of 請 Motomeko 1 to 3, to calculate a feature vector of angle stored in the database, for the feature vectors Creating a multidimensional spatial index and storing the multidimensional spatial index in the multidimensional spatial index storage means;
The second feature vector calculating means, using the angle feature amount calculating method according to any one of 請 Motomeko 1 to 3, to calculate a feature vector of the search key angles,
Said search means, using said multidimensional space index stored in said multidimensional space index storage unit, an angle with a feature vector similar to search the feature vector of the retrieval key angles,
The similarity angle search method , wherein the output means outputs the search result of the search means. A computer-readable recording medium recording a program for causing a computer to execute processing used to realize the angle feature amount calculation method according to any one of claims 1 to 3. A computer-readable recording medium recording a program for causing a computer to execute processing used to realize the similar angle search method according to claim 4.

Images