Point-sequence approximation method and apparatus

• US 7,778,740 B2
• Filed: 07/28/2006
• Issued: 08/17/2010
• Est. Priority Date: 08/17/2005
• Status: Expired due to Fees

• Current Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Original Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Inventors: Hayasaka, Shoichi, Okuda, Masato, Satonaka, Hisashi
• Primary Examiner(s): Beaulieu; Yonel
• Application Number:
  US11/494,543
• Publication Number:
  US 20070040835A1
• Time in Patent Office: 1,481 Days
• Field of Search: 701/41, 701/1, 342441-443
• US Class Current: 701/1
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18

Abstract

A point-sequence approximation apparatus determines whether a proportion of a straight-line approximation region is high as compared to that of a curve approximation region. In addition, if it is determined that the proportion of the straight-line approximation region is high as compared to that of the curve approximation region, the point-sequence approximation apparatus repeatedly performs random setting of a candidate of an approximation straight line, and evaluation of approximation accuracy of the candidate of the approximation straight line based on distances between the candidate of the approximation straight line and the points constituting the point sequence. Moreover, the point-sequence approximation apparatus performs straight-line approximation by using the candidate of the approximation straight line with the best result of evaluation of the approximation accuracy as an approximation straight line.

Claims

1. A point-sequence approximation method of approximating a point sequence constituted of a plurality of points by a line, comprising:

inputting point data from a sensor;

determining with a processor whether a proportion of a straight-line approximation region of the point data is high as compared to that of a curve approximation region;

when it is determined that the proportion of the straight-line approximation region is high as compared to that of the curve approximation region, repeatedly performing random setting of a candidate of an approximation straight line, and evaluating an approximation accuracy of the candidate of the approximation straight line based on distances between the candidate of the approximation straight line and the points constituting the point sequence; and

performing with the processor straight-line approximation using the candidate of the approximation straight line with the best result of evaluation of the approximation accuracy as an approximation straight line.

2. The point-sequence approximation method according to claim 1, further comprising:

detecting a sequence of points that have been excluded from the straight-line approximation using the approximation straight line, based on distances between the approximation straight line and the points constituting the point sequence, and then performing curve approximation of the sequence of points that have been excluded from the straight-line approximation.

3. The point-sequence approximation method according to claim 1, wherein,

in the step of determining whether the proportion of the straight-line approximation region is high, when the point sequence shows a detected position of a side of a vehicle, it is determined that the proportion of the straight-line approximation region is high as compared to that of the curve approximation region.

4. The point-sequence approximation method according to claim 1, further comprising:

detecting a border between the straight-line approximation region and the curve approximation region, based on the distances between the approximation straight line and the points constituting the point sequence.

9. The point-sequence approximation method according to claim 1, wherein,

in the step of determining whether a proportion of a straight-line approximation region is high as compared to that of a curve approximation region,

a candidate of the approximation straight line is set by using two points that are randomly selected from among the points constituting the point sequence,

distances between the set candidate of the approximation straight line and the points constituting the point sequence are calculated,

a number of such points that the obtained distances are within a predetermined threshold value is derived, and

when is determined that the proportion of the straight-line approximation region is high, provided that there is a candidate of the approximation straight line for which a proportion of such points that the distances from the candidate of the approximation straight line are within the predetermined threshold value to all the points constituting the point sequence is equal to or greater than a predetermined value.

10. The point-sequence approximation method according to claim 1, wherein,

when the candidate of the approximation straight line is randomly set, two points that are randomly selected from among the points constituting the point sequence are used to set the candidate of the approximation straight line.

11. The point-sequence approximation method according to claim 1, wherein

the evaluation of the approximation accuracy of the candidate of the approximation straight line is performed by calculating the distances between the set candidate of the approximation straight line and the points constituting the point sequence, and then deriving a number of such points that the obtained distances are within a predetermined threshold value.

5. A point-sequence approximation apparatus for approximating a point sequence constituted of a plurality of points by a line, comprising:

an input device for inputting point data from a sensor;

a determination device for determining whether a proportion of a straight-line approximation region of the point data is high as compared to that of a curve approximation region;

an evaluation device for, when it is determined that the proportion of the straight-line approximation region is high as compared to that of the curve approximation region, repeatedly performing random setting of a candidate of an approximation straight line, and evaluating approximation accuracy of the candidate of the approximation straight line based on distances between the candidate of the approximation straight line and the points constituting the point sequence; and

a straight-line approximation device for performing straight-line approximation using the candidate of the approximation straight line with the best result of evaluation of the approximation accuracy as an approximation straight line.

6. The point-sequence approximation apparatus according to claim 5, further comprising:

a curve approximation device for detecting a sequence of points that have been excluded from the straight-line approximation using the approximation straight line, based on distances between the approximation straight line and the points constituting the point sequence, and then performing curve approximation of the sequence of points that have been excluded from the straight-line approximation.

7. The point-sequence approximation apparatus according to claim 5, wherein,

when the point sequence shows a detected position of a side of a vehicle, the determination device determines that the proportion of the straight-line approximation region is high as compared to that of the curve approximation region.

8. The point-sequence approximation apparatus according to claim 5, further comprising:

a border detecting device for detecting a border between the straight-line approximation region and the curve approximation region, based on the distances between the approximation straight line and the points constituting the point sequence.

12. The point-sequence approximation apparatus according to claim 5, wherein,

the determination device sets a candidate of the approximation straight line by using two points that are randomly selected from among the points constituting the point sequence, calculates distances between the set candidate of the approximation straight line to the points constituting the point sequence, derives a number of such points that the obtained distances are within a predetermined threshold value, and determines that the proportion of the straight-line approximation region is high, provided that there is a candidate of the approximation straight line for which a proportion of such points that the distances from the candidate of the approximation straight line are within the predetermined threshold value to all the points constituting the point sequence is equal to or greater than a predetermined value.

13. The point-sequence approximation apparatus according to claim 5, wherein

the evaluation device sets the candidate of the approximation straight line by using two points that are randomly selected from among the points constituting the point sequence.

14. The point-sequence approximation apparatus according to claim 5, wherein

the evaluation device performs the evaluation of the approximation accuracy of the candidate of the approximation straight line by calculating the distances between the set candidate of the approximation straight line and the points constituting the point sequence, and then deriving a number of such points that the obtained distances are within a predetermined threshold value.

15. A point-sequence approximation apparatus for approximating a point sequence constituted of a plurality of points by a line, comprising:

input means for inputting point data from a sensor;

determination means for determining whether a proportion of a straight-line approximation region of the point data is high as compared to that of a curve approximation region;

evaluation means for, when it is determined that the proportion of the straight-line approximation region is high as compared to that of the curve approximation region, repeatedly performing random setting of a candidate of an approximation straight line, and evaluating approximation accuracy of the candidate of the approximation straight line based on distances between the candidate of the approximation straight line and the points constituting the point sequence; and

straight-line approximation means for performing straight-line approximation using the candidate of the approximation straight line with the best result of evaluation of the approximation accuracy as an approximation straight line.