Point-sequence approximation method and apparatus

• US 20070040835A1
• Filed: 07/28/2006
• Published: 02/22/2007
• Est. Priority Date: 08/17/2005
• Status: Active Grant

• Current Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Original Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Inventors: Okuda, Masato, Satonaka, Hisashi, Hayasaka, Shoichi
• Granted Patent: US 7,778,740 B2
• Time in Patent Office: Days
• US Class Current: 345/442
• 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:

determining whether a proportion of a straight-line approximation region is high as compared to that of a curve approximation region;

if 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 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; and

performing 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.

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

it 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:

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

an evaluation device for, if 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 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; and

a straight-line approximation device for performing 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.

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:

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

evaluation means for, if 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 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; and

straight-line approximation means for performing 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.

16. A parking assist system for assisting movement of a vehicle to a desired parking position, comprising:

a point-sequence detecting device, which is installed in a vehicle, for detecting a distance between the vehicle and another parked vehicle, in the form of a point sequence;

a driving control system for performing driving control of the vehicle;

an automatic steering system for performing steering control of the vehicle;

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

an evaluation device for, if 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 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;

a straight-line approximation device for performing 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; and

a parking assist ECU for performing a parking assist by controlling the driving control system and the automatic steering control system based on the approximation straight line.

17. The parking assist system according to claim 16, further comprising an assist-mode changing switch for performing a mode change between a parallel-parking assist mode and a parking-in-garage assist mode,

wherein the determination device determines that the proportion of the straight-line approximation region is high when the assist-mode changing switch is in the position of the parallel-parking assist mode.

18. The parking assist system according to claim 16, wherein

the point-sequence detecting device is a sonar that periodically transmits ultrasonic waves, and detects the distance from the another vehicle, based on the time from the transmission of the ultrasonic wave to reception of a reflected wave thereof.