Apparatus which detects lines approximating an image by repeatedly narrowing an area of the image to be analyzed and increasing the resolution in the analyzed area

• US 5,555,555 A
• Filed: 01/19/1994
• Issued: 09/10/1996
• Est. Priority Date: 01/19/1993
• Status: Expired due to Term

• Current Assignee: Aisin Seiki Co., Ltd. (Aisin Corp.)
• Original Assignee: Aisin Seiki Co., Ltd. (Aisin Corp.)
• Inventors: Sato, Jun, Saiki, Mitsuyoshi
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/183,369
• Time in Patent Office: 965 Days
• Field of Search: 382/1, 382/22, 382/48, 382/104, 382/199, 382/291, 348/118, 348/119, 364/424.02, 364/460, 364/725, 364/731
• US Class Current: 382/104
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

Each of feature points (Xs, Ys) in X and Y orthogonal coordinate system of an image taken by a television camera is converted into a group of points (ρ, θ) of polar coordinate system. Memory includes addresses allotted to each one of polar coordinates (ρ, θ) for storing frequency data. Each time the feature point is converted, the frequency data at addresses corresponding to the converted points (ρ, θ) is incremented. A particular point (ρm, θm) where the stored frequency data is at maximum is picked out, and a rectilinear line corresponding to the particular point (ρm, θm) is determined to be a rectilinear line which approxiates a succession of feature points (Xs, Ys). In this manner, a method of detecting a rectilinear line appearing on a photographed image is provided. This processing operation is repeated in a plurality of runs for the same succession of feature points. However, during the conversion into the polar coordinates of an earlier run, the conversion takes place at a low density and covers an increased range of values of ρ and θ while during a later run, the conversion takes place at a higher density and in a narrowed range which is centered about the particular point (ρm, θm) which was obtained during the conversion into the polar coordinates of the previous run.

Claims

1. An apparatus for detecting a rectilinear line of an object comprising:

generating means for inputting an analog picture image of said object and generating image data which represents said picture image of said object in an X and Y orthogonal coordinate system;

determining means for determining a plurality of feature points (Xs, Ys), wherein said plurality of feature points (Xs, Ys) are defined by values and distributions of said image data on said picture image and wherein at least some of said plurality of feature points (Xs, Ys) correspond to said rectilinear line;

first converting means for respectively converting each of said plurality of feature points (Xs, Ys) into corresponding first groups of points (r1, t1), wherein said corresponding first groups of points (r1, t1) respectively represent curves in a first r1-t1 polar coordinate system having a first resolution and a first range;

first memory means for storing first frequency data, wherein addresses of said first memory means respectively relate to points of said first r1-t1 polar coordinate system;

first incrementing means for incrementing said first frequency data, wherein said first incrementing means increments said first frequency data stored at a first certain address of said first memory means for each instance that one point in one of said corresponding first groups of points (r1, t1) relates to said first certain address;

first selecting means for selecting a first particular point (rm1, tm1) in said first r1-t1 polar coordinate system, wherein said first particular point (rm1, tm1) corresponds to a first particular address of said first memory means at which said first frequency data represents a maximum value;

second converting means for respectively converting at least some of said plurality of feature points (Xs, Ys) into corresponding second groups of points (r2, t2), wherein said corresponding second groups of points (r2, t2) respectively represent curves in a second r2-t2 polar coordinate system having a second resolution and a second range, wherein said second r2-t2 polar coordinate system is centered about said first particular point (rm1, tm1), and wherein said second resolution is higher than said first resolution and said second range is narrower than said first range;

second memory means for storing second frequency data, wherein addresses of said second memory means respectively relate to points of said second r2-t2 polar coordinate system;

second incrementing means for incrementing said second frequency data, wherein said second incrementing means increments said second frequency data stored at a second certain address of said second memory means for each instance that one point in one of said corresponding second groups of points (r2, t2) relates to said second certain address;

second selecting means for selecting a second particular point (rm2, tm2) in said second r2-t2 polar coordinate system, wherein said second particular point (rm2, tm2) corresponds to a second particular address of said second memory means at which said second frequency data represents a maximum value; and

line determining means for determining said rectilinear line in said X and Y orthogonal coordinate system, wherein said rectilinear line is based at least partially on said second particular point (rm2, tm2) and approximates a succession of at least some of said plurality of feature points (Xs, Ys).

2. The apparatus for detecting a rectilinear line of an object as defined in claim 1,

wherein said corresponding first group of points (r1, t1) in said first r1-t1 polar coordinate system are related to a ρ

and θ

polar coordinate system having an origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following first equations;

space="preserve" listing-type="equation">ρ

=r1/d.sub.1 +c.sub.1,

space="preserve" listing-type="equation">θ

=a.sub.1 ·

t1+b.sub.1, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.1 ·

t1+b.sub.1)+(Ych-Ys)·

sin (a.sub.1 ·

t1+b.sub.1)

for t1=0, 1, 2, . . . , M;

wherein M equals a first positive integer;

wherein said corresponding second groups of points (r2, t2) in said second r2-t2 polar coordinate system are related to said ρ and

θ

polar coordinate system having said origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following second equations;

space="preserve" listing-type="equation">ρ

=r2/d.sub.2 +c.sub.2, and

space="preserve" listing-type="equation">θ

=a.sub.2 ·

t2+b.sub.2, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.2 ·

t2+b.sub.2)+(Ych-Ys)·

sin (a.sub.2 ·

t2+b.sub.2)

for t1=0, 1, 2, . . . , N;

wherein N equals a second positive integer; and

wherein a₁ is less than a₁, b₂ is closer to tm1 than b₁, c₂ is closer to rm1 than c₁, and d₂ is greater than d₁.

3. The apparatus for detecting a rectilinear line of an object as defined in claim 2, wherein said first positive integer equals said second positive integer.

4. The apparatus for detecting a rectilinear line of an object as defined in claim 1, further comprising:

third converting means for respectively converting at least some of said plurality of feature points (Xs, Ys) into corresponding third groups of points (r3, t3), wherein said corresponding third groups of points (r3, t3) respectively represent curves in a third r3-t3 polar coordinate system having a third resolution and a third range, wherein said third r3-t3 polar coordinate system is centered about said second particular point (rm2, tm2), and wherein said third resolution is higher than said second resolution and said third range is narrower than said second range;

third memory means for storing third frequency data, wherein addresses of said third memory means respectively relate to points of said third r3-t3 polar coordinate system;

third incrementing means for incrementing said third frequency data, wherein said third incrementing means increments said third frequency data stored at a third certain address of said third memory means for each instance that one point in one of said corresponding third groups of points (r3, t3) relates to said third certain address; and

third selecting means for selecting a third particular point (rm3, tm3) in said third r3-t3 polar coordinate system, wherein said third particular point (rm3, tm3) corresponds to a third particular address of said third memory means at which said third frequency data represents a maximum value,

wherein said line determining means determines said rectilinear line in said X and Y orthogonal coordinate system by determining that said rectilinear line corresponds to a succession of at least some of said plurality of feature points (Xs, Ys) which relate to said third particular point (rm3, tm3).

5. The apparatus for detecting a rectilinear line of an object as defined in claim 4,

wherein said corresponding first groups of points (r1, t1) in said first r1-t1 polar coordinate system are related to a ρ

and θ

polar coordinate system having an origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following first equations;

space="preserve" listing-type="equation">ρ

=r1/d.sub.1 +c.sub.1,

space="preserve" listing-type="equation">θ

=a.sub.1 ·

t1+b.sub.1, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.1 ·

t1+b.sub.1)+(Ych-Ys)·

sin (a.sub.1 ·

t1+b.sub.1)

for t1=0, 1, 2, . . . , M;

wherein M equals a first positive integer;

wherein said corresponding second groups of points (r2, t2) in said second r2-t2 polar coordinate system are related to said ρ and

θ

polar coordinate system having said origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following second equations;

space="preserve" listing-type="equation">ρ

=r2/d.sub.2 +c.sub.2,

space="preserve" listing-type="equation">θ

=a.sub.2 ·

t2+b.sub.2, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.2 ·

t2+b.sub.2)+(Ych-Ys)·

sin (a.sub.2 t2+b.sub.2)

for t2=0, 1, 2, . . . , N;

wherein N equals a second positive integer; and

wherein a₂ is less than a₁, b₂ is closer to tm1 than b₁, c₂ is closer to rm1 than c₁, and d₂ is greater than d₁.

6. The apparatus for detecting a rectilinear line of an object as defined in claim 5,

wherein said corresponding third groups of points (r3, t3) in said third r3-t3 polar coordinate system are related to said ρ

and θ

polar coordinate system having said origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following third equations;

space="preserve" listing-type="equation">ρ

=r3/d.sub.3 +c.sub.3,

space="preserve" listing-type="equation">θ

=a.sub.3 ·

t3+b.sub.3, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.3 t3+b.sub.3)+(Ych-Ys)·

sin (a.sub.3 ·

t3+b.sub.3)

for t3=0, 1, 2, . . . , X;

wherein X equals a third positive integer; and

wherein a₃ is less than a₂, b₃ is closer to tm2 than b₂, c₃ is closer to rm2 than c₃, and d₃ is greater than d₃.

7. The apparatus for detecting a rectilinear line of an object as defined in claim 6, wherein said first positive integer equals said second positive integer and said second positive integer equals said third positive integer.

8. The apparatus for detecting a rectilinear line of an object as defined in claim 6, wherein each of said plurality of feature points (Xs, Ys) is a point on said X and Y orthogonal coordinate system at which a derivative value of said image data is equal to or greater than a threshold value and wherein said derivative value is calculated in a given direction in said X and Y orthogonal coordinate system.

9. The apparatus for detecting a rectilinear line of an object as defined in claim 1, wherein each of said plurality of feature points (Xs, Ys) is a point on said X and Y orthogonal coordinate system at which a derivative value of said image data is equal to or greater than a threshold value and wherein said derivative value is calculated in a given direction in said X and Y orthogonal coordinate system.

10. The apparatus for detecting a rectilinear line of an object as defined in claim 1, wherein said generating means comprises a photographing unit mounted onboard a vehicle for taking said picture image of said object.

11. An apparatus for detecting a rectilinear line of an object comprising:

a photographing unit mounted onboard a vehicle for inputting an analog picture of a scene including a road surface located ahead of the vehicle and for obtaining image data in an X and Y orthogonal coordinate system which represents said analog picture;

first memory means for storing the image data;

calculating means for calculating a derivative value of said image data in said first memory means and for determining feature positions (Xs, Ys) in said X and Y orthogonal coordinate system, wherein said derivative value is calculated in a given direction in the X and Y orthogonal coordinate system and wherein said feature positions (Xs, Ys) are considered to be at positions of said image data where said derivative value is equal to or greater than a threshold value;

second memory means for storing said feature positions (Xs, Ys);

conversion means for respectively converting said feature positions (Xs, Ys) in said second memory means into corresponding groups of points (r, t) which represent curves in a r-t polar coordinate system;

third memory means for storing frequency data, wherein addresses of said third memory means respectively relate to points of said r-t polar coordinate system;

counting means for incrementing said frequency data, wherein said counting means increments said frequency data at a certain address of said third memory means for each instance that one point in one of said corresponding groups of points (r, t) relates to said certain address;

selection means for selecting a particular point (rm, tm) in said polar coordinate system, wherein said particular point (rm, tm) corresponds to a particular address of said third memory means at which said frequency data represents a maximum value;

determination means for determining a rectilinear line in said X and Y orthogonal coordinate system, wherein said rectilinear line corresponds to said particular point (rm, tm) in said r-t polar coordinate system and wherein said rectilinear line approximates a white line drawn on said road surface within said scene; and

repeating means for repeating said converting of said conversion means, said incrementing of said counting means, said selecting of the selecting means, and said determining of said determination means in for plurality of runs, wherein said r-t polar coordinate system has a first resolution and a first range during a previous run and a second resolution and a second range during a subsequent run, wherein said second resolution is greater thah said first resolution and said second range is narrower than said first range, and wherein, during said subsequent run, said r-t polar system is centered around said particular point (rm, tm) obtained during said previous run.

12. An apparatus for detecting a rectilinear line of an object as defined in claim 11, further comprising:

creating means for creating a feature point detecting window, wherein said feature point detecting window includes substantially all white lines on said road surface located ahead of said vehicle which are contained in said analog picture of said scene taken by said photographing unit and wherein said calculating means calculates said derivative values of said image data corresponding to said feature point detecting window.

13. An apparatus for detecting a rectilinear line of an object as defined in claim 12, wherein a position and an area of said feature point detecting window corresponding to a picture frame are constant.

14. The apparatus for detecting a rectilinear line of an object as defined in claim 11,

wherein said corresponding groups of points (r, t) obtained during said previous run are related to a ρ

and θ

polar coordinate system having an origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following first equations;

space="preserve" listing-type="equation">ρ

=r/d.sub.1 +c.sub.1,

space="preserve" listing-type="equation">θ

=a.sub.1 ·

t+b.sub.1, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.1 ·

+b.sub.1)+(Ych-Ys)·

sin (a.sub.1 ·

t+b.sub.1)

for t=0, 1, 2, . . . , M;

wherein M equals a first positive integer;

wherein said corresponding groups of points (r, t) obtained during said subsequent run are related to said ρ and

θ

polar coordinate system having said origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following second equations;

space="preserve" listing-type="equation">ρ

=r/d.sub.2 +c.sub.2,

space="preserve" listing-type="equation">θ

=a.sub.2 ·

t+b.sub.2, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.2 ·

t+b.sub.2)+(Ych-Ys)·

sin (a.sub.2 t+b.sub.2)

for t=0, 1, 2, . . . , N;

wherein N equals a second positive integer; and

wherein a₂ is less than a₁, b₂ is closer to tm obtained during said previous run than b₁, c₂ is closer to rm obtained during said previous run than c₁, and d₂ is greater than d₁.

15. The apparatus for detecting a rectilinear line of an object as defined in claim 14, wherein said first positive integer equals said second positive integer.

16. The apparatus for detecting a rectilinear line of an object as defined in to claim 14,

wherein said corresponding groups of points (r, t) obtained during second subsequent run are related to said ρ

and θ

polar coordinate system having said origin point (Xch, Ych) in said X and Y orthogonal coordinate system based on the following third equations;

space="preserve" listing-type="equation">ρ

=r/d.sub.3 +c.sub.3,

space="preserve" listing-type="equation">θ

=a.sub.3 ·

t+b.sub.3, and

space="preserve" listing-type="equation">ρ

=(Xs-Xch)·

cos (a.sub.3 t+b.sub.3)+(Ych-Ys)·

sin (a.sub.3 ·

t+b.sub.3)

for t=0, 1, 2, . . . ,X;

wherein X equals a third positive integer; and

wherein a₃ is less than a₂, b₃ is closer to tm obtained during said subsequent run than b₂, c₃ is closer to rm obtained during said subsequent run than c₃, and d₃ is greater than d₃.

17. The apparatus for detecting a rectilinear line of an object as defined in claim 16, wherein said first positive integer equals said second positive integer and said second positive integer equals said third positive integer.

18. The apparatus for detecting a rectilinear line of an object as defined in claim 16, further comprising:

creating means for creating a feature point detecting window, wherein said feature point detecting window includes substantially all white lines on said road surface located ahead of said vehicle which are contained in said picture of said scene taken by said photographing unit and wherein said calculating means calculates said derivative values of said image data corresponding to said feature point detecting window.

19. An apparatus for detecting a rectilinear line of an object as defined in claim 18, wherein a position and an area of said feature point detecting window corresponding to a picture frame are constant.

20. The apparatus for detecting a rectilinear line of an object as defined in claim 19, wherein said first positive integer equals said second positive integer and said second positive integer equals said third positive integer.