JPH0352083A - Straight line approximation system - Google Patents
Straight line approximation systemInfo
- Publication number
- JPH0352083A JPH0352083A JP1188039A JP18803989A JPH0352083A JP H0352083 A JPH0352083 A JP H0352083A JP 1188039 A JP1188039 A JP 1188039A JP 18803989 A JP18803989 A JP 18803989A JP H0352083 A JPH0352083 A JP H0352083A
- Authority
- JP
- Japan
- Prior art keywords
- straight line
- parameters
- points
- parameter
- rho
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Landscapes
- Image Analysis (AREA)
- Image Processing (AREA)
Abstract
Description
【発明の詳細な説明】
〔概要〕
入力点から近似直線を算出する直線近似方式に関し、
入力点から取り出した２点のうちから予想直線に対する
平行成分が所定閾値以上かつ垂直或分が所定閾値以下の
２点について、あるいは予想直線からの距離が所定闇値
以下の１点もしくは２点について、ρ−θ空間の値を求
めて最大頻度のパラメータ（ρ、θ）を出力し、計算量
を少なくして高速に直線近似のパラメータを求めること
を目的とし、
入力点から取り出した任意の２点を結ぶ線分と予想直線
との間の平行威分が所定閾値以上かつ垂直或分が所定闇
値以下の組み合せを選択し、これら選択した２点を結ん
だ線分のパラメータ（ρ、θ）を計算するパラメータ計
算部を備え、このパラメータ計算部によって計算したパ
ラメータ（ρ、θ）についてρ−θ空間をメッシュ状に
分割した領域に加算することを繰り返し、最大頻度の領
域の座標（ρ、♂）を近似直線のパラメータ（ρ、θ〉
とするように構或する．また、人力点から取り出した任
意のｌ点乙予想直線との間の距離が所定閾値以下の点を
選択し、これら選択したうちの任意の１点を通る直線の
パラメータ（ρ、θ）、もしくはこれら選択したうちの
任息の２点を結んだ線分のパラメータ（ρ、θ）を計算
するパラメータ計算部を備え、このパラメータ計夏部に
よって計算したパラメータ（ρ、θ）についてρ一θ空
間をメッシュ状に分割した領域に加算することを繰り返
し、最大頻度の領域の座ｔ１（ρ、θ）を近似直線のパ
ラメータ（ρ、θ）とするように構成する．
〔産業上の利用分野〕
本発明ば、入力点から近似直線を算出するｉｉＩ線近似
方式に関するものである．画像処理装置において、画像
中の複数の点に直線近似した直線を求めることは、物体
の方向や境界を抽出するのに非常に重要な技術である。[Detailed Description of the Invention] [Summary] Regarding the linear approximation method for calculating an approximate straight line from an input point, a parallel component to the expected straight line from two points taken from the input point is greater than or equal to a predetermined threshold, and a perpendicular component is less than or equal to a predetermined threshold. For two points, or for one or two points whose distance from the predicted straight line is less than a predetermined dark value, calculate the values in the ρ-θ space and output the parameters (ρ, θ) with the highest frequency to reduce the amount of calculation. The purpose is to quickly obtain the parameters of a straight line approximation by It is equipped with a parameter calculation section that selects the following combinations and calculates the parameters (ρ, θ) of a line segment connecting these two selected points, and the parameters (ρ, θ) calculated by this parameter calculation section are ρ - θ. The space is divided into meshes, and the coordinates (ρ, ♂) of the area with the maximum frequency are determined by the parameters (ρ, θ〉) of the approximate straight line.
It is constructed so that In addition, select a point whose distance between arbitrary point B and the expected straight line extracted from the human power point is less than a predetermined threshold, and calculate the parameters (ρ, θ) of the straight line that passes through any one of these selected points, or It is equipped with a parameter calculation unit that calculates the parameters (ρ, θ) of a line segment connecting two arbitrary points among these selected points, and the parameters (ρ, θ) calculated by this parameter calculator are calculated in the ρ-θ space. is repeatedly added to the regions divided into meshes, and the locus t1 (ρ, θ) of the region with the maximum frequency is configured to be the parameter (ρ, θ) of the approximate straight line. [Industrial Application Field] The present invention relates to a line approximation method for calculating an approximate straight line from input points. In an image processing device, finding a straight line that approximates a plurality of points in an image is a very important technique for extracting the direction and boundary of an object.
入力画像は多くの雑音を含んでいるため、物体の方向や
境界を見い出すために、物体上の複数の点や境界上の複
数の点について迅速かつ正確に直線近似した直線を求め
ることが望まれている．
〔従来の技術と発明が解決しようこする課題〕従来、画
像中の複数の点の直線近似は、ハフ技術を用い、第４図
（イ）に示す構威により、直線のパラメータ（ρ、θ）
を求めるようにしていた。Since the input image contains a lot of noise, it is desirable to quickly and accurately find a straight line that approximates multiple points on the object or multiple points on the boundary in order to find the direction or boundary of the object. ing. [Problems to be solved by the prior art and the invention] Conventionally, linear approximation of multiple points in an image uses the Hough technique, and the straight line parameters (ρ, θ) are calculated using the configuration shown in FIG. )
I was trying to ask for it.
この際、第４図（ロ）に示すように、入力された各点か
ら下式（１１を満足するρおよびθを求め、これを第５
図（口）ρ−θ空間上の該当する分割領域の頻度に加算
する．
Ｘｃｏｓ （θ）＋Ｙｓｉｎ（θ）−ρ−−−＋１＋
ここで、ρは原点０から直線までの距離を表し、θは直
線がＹ軸となす角度を表す．
そして、最大頻度の座標（ρ、θ）を求め、これを直線
のパラメータ（ρ、θ）としていた．このため、各入力
点について式（１）からρおよびθの値をそれぞれ求め
る必要があり、計算量が多《なり、時間がかかり過ぎる
という問題があった．第４図および第５図を簡単に説明
する．第４図（イ）において、入力点格納部２１から取
り出した１つの点について、パラメータ計算部２２が上
式（１）によってρ−θ空間上の値を求め、パラメータ
格納部２３に格納する．パラメータ最大頻度計算部２４
は、最大頻度を持つ座標（ρ、θ）を検出し、これを結
果パラメータ格納部２５に格納する．この際、第４図（
ロ）に示すパラメータ計算部２２を構或する点データ制
御部２２一ｌが取り込んだ１つの点を１点一時格納部２
２−２に格納する．ｐ計算部２４−４がθ発生部２２−
３から順次通知されたθ値
θ＝ （ｎ／Ｎ）２π・・・・・・・・・・・Ｃ２）こ
こで、ｎ＝０、１、２・・・Ｎ
を式（１１に代入すると共に、ｔつの点の座標値（Ｘ、
Ｙ）を代入し、ρを全て求める．これらθおよびＰをバ
ラメーター時格納部２２−５に順次格納する．
次に、第５図を用いてパラメータについて説明する．こ
こで、パラメータの距離ρおよび角度θは、第５図（イ
）に示すように、画面上の中心点０からの距離ρおよび
角度θである．ガイドラインの方程式は、上述した式＋
１１によって表される．ここで、ガイドライン上の１つ
の点（Ｘ．．Ｙ）を通るパラメータ（ρ、θ）は、上式
＋１１を満たす曲線となる．
第５図（ロ）は、ρ一θ空間をメソシュ上に分割し、パ
ラメータ（ρ、θ〉を分割した領域に加算し、最大頻度
のパラメータ（ρ、θ〉をガイドラインのパラメータと
して検出する．
本発明は、入力点から取り出した２点のうちから予想直
線に対する千行成分が所定閾値以上かつ垂直或分が所定
閾値以下の２点について、あるいは予想直線からの距離
が所定閾値以下の１点もしくは２点について、ρ−θ空
間の値を求めて最大頻度のパラメータ（ρ、θ〉を出力
し、計算量を少なくして高速に直線近似のパラメータを
求めることを目的としている。At this time, as shown in Figure 4 (b), calculate ρ and θ that satisfy the following formula (11) from each input point,
Figure (mouth) Add to the frequency of the corresponding divided area on the ρ-θ space. Xcos(θ)+Ysin(θ)−ρ−−−+1+
Here, ρ represents the distance from the origin 0 to the straight line, and θ represents the angle that the straight line makes with the Y axis. Then, the coordinates (ρ, θ) of the maximum frequency were found, and these were used as the straight line parameters (ρ, θ). Therefore, it is necessary to calculate the values of ρ and θ from Equation (1) for each input point, which poses the problem of increasing the amount of calculation and taking too much time. Figures 4 and 5 will be briefly explained. In FIG. 4(a), the parameter calculation unit 22 calculates a value in the ρ-θ space using the above equation (1) for one point taken out from the input point storage unit 21, and stores it in the parameter storage unit 23. Parameter maximum frequency calculation unit 24
detects the coordinates (ρ, θ) with the maximum frequency and stores this in the result parameter storage unit 25. At this time, as shown in Figure 4 (
One point taken in by the point data control unit 22-l, which constitutes the parameter calculation unit 22 shown in b), is stored in one point temporary storage unit 2.
Store in 2-2. The p calculation unit 24-4 is the θ generation unit 22-
θ value θ = (n/N)2π...C2) Here, substituting n=0, 1, 2...N into equation (11) and the coordinate values of t points (X,
Y) and find all ρ. These θ and P are sequentially stored in the parameter storage unit 22-5. Next, the parameters will be explained using Fig. 5. Here, the distance ρ and angle θ of the parameters are the distance ρ and angle θ from the center point 0 on the screen, as shown in FIG. 5(a). The guideline equation is the above formula +
It is represented by 11. Here, the parameters (ρ, θ) passing through one point (X...Y) on the guideline form a curve that satisfies the above formula +11. In Figure 5 (b), the ρ-θ space is divided into meshes, the parameters (ρ, θ〉) are added to the divided regions, and the parameter (ρ, θ〉) with the highest frequency is detected as the guideline parameter. The present invention provides for two points extracted from an input point whose 1,000-row component with respect to the predicted straight line is greater than or equal to a predetermined threshold and whose perpendicular component is less than or equal to a predetermined threshold, or one point whose distance from the predicted straight line is less than or equal to a predetermined threshold. Alternatively, the purpose is to find the values in the ρ-θ space for two points and output the parameters (ρ, θ) with the highest frequency, thereby reducing the amount of calculation and quickly finding the linear approximation parameters.
第１図を参照して課題を解決する手段を説明する。 Means for solving the problem will be explained with reference to FIG.
第ｌ図において、パラメータ計算部２ば、入力点から取
り出した任意の２点を結ぶ線分ε予想直線との間の平行
成分が所定！ｉｍ以上かつ垂直成分が所定闇値以下の組
み合せを選択し、あるいは入力点から取り出した任意の
ｌ点と予想直線との間の距離が所定闇値以下の１つの点
もしくは２つの点を選択し、選択した１点を通る直線も
しくはこれら選択した２点を結んだ線分のパラメータ（
ρ、θ）を計算するものである．
パラメータ最大頻度計算部４は、パラメータ計算部２に
よって計罪したパラメータ（ρ、θ）についてρ−θ空
間をメッシュ状に分割した領域に加算することを繰り返
し、最大頻度の領域の座標（ρ、θ）をパラメータとし
て求めるものである．Ｃ作用〕
本発明は、第ｌ図に示すように、パラメータ計算部２が
人力点から取り出した任意の２点を結ぶ線分と予想直線
との間の平行成分が所定闇値以上かつ垂直威分が所定闇
値以下の組み合せを選択し、これら選択した２点を結ん
だ線分のパラメータ（ρ、θ）を計算し、パラメータ最
大頻度計算部番がこれら計算したパラメータ（ρ、θ）
をρ−θ空間でメソシエ状に分割した領域に加算するこ
とを繰り．返し、最大頻度のｖｉ域の座標（ρ、θ）を
求め、これを近似直線のパラメータ（ρ、θ）として出
力するようにしている．また、パラメータ計算部２が入
力点から取り出した任意の１点ε予想直線との間の距離
が所定閾値以下のｉつの点もしくは２つの点を選択し、
この１点を通る直線もしくはこれらの２点を結んだ線分
のパラメータ（ρ、θ）を計算し、パラメータ最大頻度
計算部４がこれら計算したパラメータ（ρ、θ）をρ−
θ空間でメッシュ状に分割した領域に加算することを繰
り返し、最大頻度の領域の座標（ρ、θ）を求め、これ
を近似直線のパラメータ（ρ、θ）として出力するよう
にしている．
従って、入力点から取り出した２点のうちから予想直線
に対する平行或分が所定閾値以上かつ垂直威分が所定闇
値以下の２点について、あるいは予想直線からの距離が
所定閾値以下の１点もしくは２点について、ρ−θ空間
の値を求めて最大頻度のパラメータ（ρ、θ）を出力す
ることにより、計夏量を少なくし、高速に直線近似する
ことが可能となる．
〔実施例〕
次に、第ｌ図から第３図を用いて本発明のｌ実施例の構
或および動作を順次詳細に説明する．ここで、予想直線
からの距離が所定閾値以下の１点について、このｌ点を
通る直線のパラメータ（ρ、θ）を求めるものの実施例
の構成ぱ、従来の第４図点データ制御部２２−１におい
て、予想直線からの距離による制限を加えるようにして
いるので、割愛する．
第ｌ図において、入力点格納部ｌは、カメラを用いて撮
影した画像中からガイドラインに対応ずる色（例えば白
色）などの特徴を持つ点の座標を格納したものである．
ここで、ガイドラインは、例えば無人自走車の走路を路
上に引いた線や、沿って走るべき腺であり、作業をしつ
つ移動する自走車の場合、作業済区域と未作業区域の境
界線、あるいは直前の作業済領域の線がガイドラインと
なる．具体的に言えば、無人芝刈機の場合には、芝刈済
区域と、未芝刈区域との境界線がガイドラインとなる．
パラメータ計算部２ば、２−１ないし２−６から構威さ
れ、入力点格納部１から取り出した任意の２点を結ぶ線
分と予想直線との間の平行或分が所定闇値以上かつ垂直
或分が所定閾値以下の組み合せを選択し、あるいは人力
点から取り出した任意の１点と予想直ｍ．＝の間の距離
が所定閾値以下の２つの点を選択し、これらの２点を結
んだ線分のパラメータ（ｐ，θ）を計算するものである
。In FIG. 1, the parameter calculation unit 2 determines that the parallel component between the line segment ε connecting any two points extracted from the input point and the expected straight line is predetermined! Select a combination whose vertical component is greater than or equal to im and less than a predetermined darkness value, or select one or two points where the distance between any l point taken from the input point and the predicted straight line is less than or equal to a predetermined darkness value. , the parameters of the straight line passing through one selected point or the line segment connecting these two selected points (
ρ, θ). The parameter maximum frequency calculation unit 4 repeatedly adds the parameters (ρ, θ) calculated by the parameter calculation unit 2 to the regions obtained by dividing the ρ-θ space into a mesh shape, and calculates the coordinates (ρ, θ) of the region of maximum frequency. θ) as a parameter. Effect C] As shown in FIG. Select the combinations where the minute is less than the predetermined darkness value, calculate the parameters (ρ, θ) of the line segment connecting these two selected points, and set the parameter maximum frequency calculation part number to the calculated parameters (ρ, θ).
is repeatedly added to regions divided into mesociete shapes in ρ-θ space. Then, the coordinates (ρ, θ) of the vi region with the maximum frequency are determined, and these are output as the parameters (ρ, θ) of the approximate straight line. In addition, the parameter calculation unit 2 selects i points or two points whose distance from the arbitrary point ε predicted straight line extracted from the input point is equal to or less than a predetermined threshold,
The parameters (ρ, θ) of the straight line passing through this one point or the line segment connecting these two points are calculated, and the parameter maximum frequency calculation unit 4 calculates these calculated parameters (ρ, θ) by ρ−
The coordinates (ρ, θ) of the region with the maximum frequency are obtained by repeating addition to the regions divided into meshes in the θ space, and these are output as the parameters (ρ, θ) of the approximate straight line. Therefore, among the two points extracted from the input point, two points whose parallel distance to the predicted straight line is above a predetermined threshold and whose perpendicular distance is below a predetermined threshold, or one point whose distance from the predicted straight line is below a predetermined threshold, or By finding the values in the ρ-θ space for two points and outputting the parameters (ρ, θ) with the highest frequency, it is possible to reduce the amount of summer and perform linear approximation at high speed. [Embodiment] Next, the structure and operation of an embodiment of the present invention will be explained in detail using FIGS. 1 to 3. Here, for a point whose distance from the expected straight line is less than a predetermined threshold, the parameters (ρ, θ) of a straight line passing through this l point are determined. 1, we add a restriction based on the distance from the predicted straight line, so we omit it. In FIG. 1, an input point storage section 1 stores the coordinates of points having characteristics such as color (for example, white) that correspond to the guideline from images taken using a camera.
Here, the guideline is, for example, a line drawn on the road for the unmanned self-propelled vehicle, or a line along which the unmanned self-propelled vehicle should run, and in the case of a self-propelled vehicle that moves while performing work, the boundary between the worked area and the unworked area. The line or the line of the previous worked area serves as a guideline. Specifically, in the case of an unmanned lawn mower, the boundary line between the mowed area and the unmowed area serves as a guideline. The parameter calculation unit 2 is configured from 2-1 to 2-6 and determines that the parallel distance between the line segment connecting any two points retrieved from the input point storage unit 1 and the predicted straight line is greater than or equal to a predetermined darkness value. Select a combination in which the vertical fraction is less than a predetermined threshold, or combine an arbitrary point taken from the human points with the predicted direct m. Two points where the distance between = is less than or equal to a predetermined threshold are selected, and parameters (p, θ) of a line segment connecting these two points are calculated.
パラメータ格納部３は、パラメータ計算部２によって計
算したパラメータを格納するものである．パラメータ最
大頻度計蒐部４は、パラメータ計算部２によって計算し
たパラメータ（ρ、θ）についてρ−θ空間でメッシュ
状に分割した領域に加算することを繰り返し、最大頻度
の領域の座標（ρ、θ）をパラメータとして求めるもの
である．結果パラメータ格納部５は、パラメータ最大頻
度計算部４によって算出した直線のパラメータを格納す
るものである。The parameter storage unit 3 stores parameters calculated by the parameter calculation unit 2. The parameter maximum frequency calculation unit 4 repeatedly adds the parameters (ρ, θ) calculated by the parameter calculation unit 2 to the regions divided into meshes in the ρ-θ space, and obtains the coordinates (ρ, θ) of the region with the maximum frequency. θ) as a parameter. The result parameter storage section 5 stores the straight line parameters calculated by the parameter maximum frequency calculation section 4.
次に、パラメータ計算部２の構成および動作を詳細に説
明する．
点データ＠御部２−１ば、入カデータから２つの点の座
標を取り込み、第１点一時格納部２−２および第２点一
時格納部２−３に格納するものである．この際、取り込
む２点のデータは、既述したように、｛１｝任意の２点
の予想直線に対する水平或分が所定閾値以上、かつ垂直
成分が所定閾値以下の２点について、あるいは（２）予
想直線に対する距離が所定閾値以下の２点について、第
１点一時格納部２−２および第２点一時格納部２−３に
格納するようにしている。Next, the configuration and operation of the parameter calculation section 2 will be explained in detail. The point data@control section 2-1 fetches the coordinates of two points from the input data and stores them in the first point temporary storage section 2-2 and the second point temporary storage section 2-3. At this time, the data of the two points to be imported are, as described above, {1} two points whose horizontal component with respect to the expected straight line of any two points is greater than or equal to a predetermined threshold, and whose vertical component is less than or equal to a predetermined threshold; ) Two points whose distance to the predicted straight line is less than or equal to a predetermined threshold are stored in the first point temporary storage section 2-2 and the second point temporary storage section 2-3.
θ計算部２−４は、２点の座［（Ｘｉ，Ｙｌ）、（Ｘ２
、Ｙ２）から下式（３）によってθを求めるものである
．
θ−ａｒｃｔａｎ （ＸＺ−ＸＩ）／ （Ｙ：’−Ｙ１
）・・・・・・・・・・・・・・・・・・・０）ρ計算
部２−５は、下式（４）によってρを求めるものである
。The θ calculation unit 2-4 calculates the two points [(Xi, Yl), (X2
, Y2) by the following equation (3). θ-arctan (XZ-XI)/ (Y:'-Y1
)・・・・・・・・・・・・・・・・・・0) The ρ calculation unit 2-5 calculates ρ using the following equation (4).
ρ＝ （Ｘｉ） ｃｏｓ （θ）＋（Ｙｌ）ｓｉ
ｎ（θ）・・ ・ ・ ・ ・ ・ ・ ・ ・ ・
・ ・ ・ ・ ・ ・ ・ ・ ・（４）パラメータ
ー時格納部２−６は、θ計算部２４およびρ計算部２−
５によってそれぞれ求めたθおよびρを格納するもので
ある。ρ= (Xi) cos (θ) + (Yl)si
n(θ) ・ ・ ・ ・ ・ ・ ・ ・ ・ ・
・ ・ ・ ・ ・ ・ ・ ・ ・ (4) The parameter time storage section 2-6 stores the θ calculation section 24 and the ρ calculation section 2-
.theta. and .rho., respectively, obtained by 5 are stored.
次に、第２図を用いて第１図構或の動作を詳細に説明す
る．
第２図において、［株］は、画像入力する。これば、カ
メラを用いてガイドラインを含む画像を取り込む．
０は、任意の２点を取り出し、予想直線に対する平行成
分および垂直或分を算出する．これは、左側に示すよう
に、任意の２点Ａ．．Ｂを結んだ線分について、予想直
線に対ずる平行或分および垂直成分を算出する．
Ｏば、平行成分≧閾値ｌ，かつ垂直威分５閾値２か否か
を判別する．ＹＥＳの場合には、パラメータ計算対象と
し、■を行う．Ｎｏの場合には、パラメータ計算対象か
ら外し、［相］を行う．■は、２点を結んだパラメータ
（ρ、θ）を算出する．これは、既述した式（３）、式
（４）によってθおよびρを算出する．
［相］は、全ての組み合せが終了か否かを判別する。Next, the operation of the structure in Figure 1 will be explained in detail using Figure 2. In FIG. 2, [stock] inputs an image. This will use a camera to capture an image containing the guideline. 0 takes any two points and calculates the parallel component and perpendicular component to the expected straight line. This means that any two points A. as shown on the left. ．． For the line segment connecting B, calculate the parallel and perpendicular components to the predicted straight line. If so, it is determined whether the parallel component≧threshold value 1 and the vertical component 5 threshold value 2. If YES, use the parameter calculation target and perform ■. If No, remove it from parameter calculation and perform [Phase]. ■Calculate the parameters (ρ, θ) connecting the two points. This calculates θ and ρ using equations (3) and (4) described above. [Phase] determines whether all combinations are completed.
ＹＥＳの場合には、＠を行う．ＮＯの場合には、■で次
の組み合せを選択し、■以降を操り返し行う．
■は、最大頻度を持つブロックを求める。これは、■で
求めたθおよびρについて、ρ−θ空間上の分割した領
域に頻度を加算し、最大頻度の座標を求め、これを代表
値（ρ３、θ０）とする。If YES, perform @. If NO, select the next combination with ■, and repeat the steps after ■. ■ Finds the block with the maximum frequency. This is done by adding the frequencies of θ and ρ obtained in ① to the divided regions on the ρ-θ space, finding the coordinates of the maximum frequency, and using this as the representative value (ρ3, θ0).
この際、最大頻度のブロックが複数存在する場合には、
その中心を代表値（ρ４、θｍ）とする。At this time, if there are multiple blocks with the maximum frequency,
Let the center be the representative value (ρ4, θm).
［相］は、結果出力する．これは、■で求めた代表値（
ρ１、θ０）を直線のパラメータとして出力する．
以上の処理によって、任意の２点を結んだ線分の予想直
線に対する平行或分が所定閾値以上かつ垂直或分が所定
閾値以下の２点についてのみ、パラメータ抽出・最大頻
度のパラメータ検出を行い、直線のパラメータ（ρ０、
θ０〉を求めるここにより、計算対象数を減らし、高速
に直線のパラメータを求めることが可能となる．
第３図を用いて第１図構成の動作を詳細に説明する．
第３図において、［相］は、画像入力する．これば、カ
メラを用いてガイドラインを含む画像を取り込む．
［相］は、任意の１点を取り出し、予想直線からの距離
を求める．これは、左側に示すように、任意の１点Ａか
ら予想直ＮＩＡまでの距離を求める．０は、距離≦Ｐｉ
｛ｆか否かを判別する．ｙＥｓの場合には、０でパラメ
ータ計算対象とし、［相］を行い。ＮＯの場合には、パ
ラメータ計算対象から外し、［相］を行う．
［相］は、終わりか否かを判別する．ＹＥＳの場合には
、■以降を行う．ＮＯの場合には、［相］で次の点を取
り出し、［相］以降を繰り返し行う．■は、任意の２点
を取り出す．これは、ＯＹＥＳ，ｏで計算対象とした点
のうちから任意の２点を取り出す．
［相］は、２点を結ぶ直線のパラメータ（ρ、θ）を算
出する．これば、既述した式（３）、式（４）によって
θおよびρを算出する．
Ｏば、全ての組み合せが終了か否かを判別する．ＹＥＳ
の場合には、［相］を行う．ＮＯの場合には、■で次の
組み合せを選び、■以降を繰り返し行う．［相］は、最
大頻度を持つブロンクを求める．これば、＠で算出した
直線のパラメータ（ρ、θ）について、ρ一θ空間上で
メッシュ状に分割した該当ブロンク（ｖｉ域）の頻度を
加算し、最大頻度のブロックの代表４１！ （ρ９、θ
８）を求める．０は、結果を出力する．
以上の処理によって、予想直線との距離が所定閾値以下
の点についてのみ、パラメータ計算・最大頻度のパラメ
ータ検出を行い、直線のパラメータ（ρ０、θ０）を求
めることにより、計算対象数を減らし、高速に直線のパ
ラメータを求めることが可能となる。[Phase] outputs the result. This is the representative value (
Output ρ1, θ0) as straight line parameters. Through the above processing, parameter extraction and maximum frequency parameter detection are performed only for two points whose parallel or perpendicular angle to the predicted straight line connecting any two points is greater than or equal to a predetermined threshold and whose perpendicular segment is less than or equal to a predetermined threshold. Straight line parameters (ρ0,
By calculating θ0〉, it is possible to reduce the number of calculation targets and quickly calculate the straight line parameters. The operation of the configuration shown in Figure 1 will be explained in detail using Figure 3. In Figure 3, [phase] inputs an image. This will use a camera to capture an image containing the guideline. [Phase] picks an arbitrary point and calculates the distance from the expected straight line. As shown on the left, this calculates the distance from an arbitrary point A to the predicted direct NIA. 0 is distance≦Pi
{Determine whether or not f. In the case of yEs, use 0 as the parameter calculation target and perform [phase]. If NO, remove it from the parameter calculation and perform [Phase]. [Phase] determines whether it is the end or not. If YES, perform steps from ■. If NO, take out the next point in [Phase] and repeat the steps after [Phase]. ■ Takes out two arbitrary points. This extracts any two points from among the points targeted for calculation in OYES, o. [Phase] calculates the parameters (ρ, θ) of the straight line connecting two points. Then, θ and ρ are calculated using equations (3) and (4) described above. If so, determine whether all combinations are completed. YES
In this case, perform [phase]. If NO, select the next combination using ■, and repeat steps after ■. [Phase] finds the bronch with the maximum frequency. This way, for the straight line parameters (ρ, θ) calculated in @, the frequency of the corresponding bronch (vi area) divided into meshes on the ρ-θ space is added, and the representative 41 of the block with the maximum frequency is calculated! (ρ9, θ
Find 8). 0 outputs the result. Through the above processing, parameter calculation and maximum frequency parameter detection are performed only for points whose distance from the predicted straight line is less than a predetermined threshold, and the parameters (ρ0, θ0) of the straight line are determined, reducing the number of calculation targets and increasing the speed of calculation. It becomes possible to find the parameters of the straight line.
＋１１ また、画像処理装置において、第２図を適用
する際に、予想直線をＹ軸方向にした場合、２点（Ｘｉ
、Ｙｌ）、（Ｘ２、Ｙ２）を結ぶ線分と予想直線である
Ｙ軸に対する平行成分は（Ｙｌ〜Ｙ２）、垂直成分は（
Ｘｉ，Ｘ２）となり、計算が極めて簡単となる．これは
、例えば無人自走車のカメラによって撮影した画像上の
ガイドラインがほぼＹ軸となることが多く、このときの
直線のパラメータを算出する際に、計算量を極めて少な
くすることができる．
（２） また、画像処理装置において、第３図を適用
する際に、予想直線をＹ軸方向にした場合、入力点から
取り出した点（Ｘｉ、Ｙｌ）と、予想直線であるＹ軸と
の距離は、Ｘｉとなり、計算が極めて簡単となる．これ
は、例えば無人自走車のカメラによって撮影した画像上
のガイドラインがほぼＹ軸となることが多く、このとき
の直線のパラメータを算出する際に、計算量を極めて少
なくすることができる．
〔発明の効果〕
以上説明したように、本発明によれば、入力点より取り
出した２点のうちから予想直線に対する千行或分が所定
閾値以上かつ垂直威分が所定閾値以下の２点について、
あるいは予想直線からの距離が所定閾値以下のｌ点もし
くは２点について、直線のパラメータ計算・最大頻度の
パラメータ検出を行う構成を採用しているため、計算量
を少なくし、直線近似した直線のパラメータを高速に算
出することができる．+11 In addition, in the image processing device, when applying Fig. 2, if the predicted straight line is set in the Y-axis direction, two points (Xi
, Yl), (X2, Y2) and the expected straight line, the parallel component to the Y axis is (Yl~Y2), and the perpendicular component is (
Xi, X2), which makes the calculation extremely simple. This is because, for example, the guideline on the image taken by the camera of an unmanned self-propelled vehicle is often approximately the Y axis, and when calculating the straight line parameters in this case, the amount of calculation can be extremely reduced. (2) In addition, in the image processing device, when applying Fig. 3, if the predicted straight line is set in the Y-axis direction, the point (Xi, Yl) extracted from the input point and the Y-axis, which is the predicted straight line, The distance is Xi, and calculation is extremely simple. This is because, for example, the guideline on the image taken by the camera of an unmanned self-propelled vehicle is often approximately the Y axis, and when calculating the straight line parameters in this case, the amount of calculation can be extremely reduced. [Effects of the Invention] As explained above, according to the present invention, out of the two points taken from the input points, the 1,000-line distance from the predicted straight line is greater than or equal to a predetermined threshold value, and the vertical strength is less than or equal to a predetermined threshold value. ,
Alternatively, since a configuration is adopted in which straight line parameter calculation and maximum frequency parameter detection are performed for l or 2 points whose distance from the predicted straight line is less than a predetermined threshold, the amount of calculation can be reduced and the parameters of the straight line approximated by the straight line can be calculated. can be calculated quickly.
第１図は本発明の１実施例構成図、第２図、第３図は本
発明の動作説明フローチャート、第４図は従来技術の構
成図、第５図はパラメータ説明図を示す．
図中、１ば入力点格納部、２ばパラメータ計算部、２−
１は点データ制御部、２−４はθ計算部、２−５はρ計
算部、３ばパラメータ格納部、４ばパラメータ最大頻度
計算部を表す．FIG. 1 is a block diagram of one embodiment of the present invention, FIGS. 2 and 3 are flowcharts explaining the operation of the present invention, FIG. 4 is a block diagram of a conventional technique, and FIG. 5 is a diagram explaining parameters. In the figure, 1 indicates an input point storage section, 2 indicates a parameter calculation section, and 2-
1 is a point data control section, 2-4 is a θ calculation section, 2-5 is a ρ calculation section, 3 is a parameter storage section, and 4 is a parameter maximum frequency calculation section.
Claims (2)
いて、 入力点から取り出した任意の２点を結ぶ線分と予想直線
との間の平行成分が所定閾値以上かつ垂直成分が所定閾
値以下の組み合せを選択し、これら選択した２点を結ん
だ線分のパラメータ（ρ、θ）を計算するパラメータ計
算部（２）を備え、このパラメータ計算部（２）によっ
て計算したパラメータ（ρ、θ）についてρ−θ空間を
メッシュ状に分割した領域に加算することを繰り返し、
最大頻度の領域の座標（ρ、θ）を近似直線のパラメー
タ（ρ、θ）とするように構成したことを特徴とする直
線近似方式。(1) In the linear approximation method that calculates an approximate straight line from input points, the parallel component between the line segment connecting any two points taken from the input point and the expected straight line is greater than or equal to a predetermined threshold, and the perpendicular component is less than or equal to a predetermined threshold. It is equipped with a parameter calculation unit (2) that selects a combination and calculates the parameters (ρ, θ) of a line segment connecting these two selected points, and the parameters (ρ, θ) calculated by this parameter calculation unit (2). Repeatedly adding the ρ-θ space to the area divided into meshes for
A straight line approximation method characterized in that the coordinates (ρ, θ) of the region of maximum frequency are configured to be the parameters (ρ, θ) of the approximate straight line.
いて、 入力点から取り出した任意の１点と予想直線との間の距
離が所定閾値以下の点を選択し、これら選択したうちの
任意の１点を通る直線のパラメータ（ρ、θ）、もしく
はこれら選択したうちの任意の２点を結んだ線分のパラ
メータ（ρ、θ）を計算するパラメータ計算部（２）を
備え、 このパラメータ計算部（２）によって計算したパラメー
タ（ρ、θ）についてρ−θ空間をメッシュ状に分割し
た領域に加算することを繰り返し、最大頻度の領域の座
標（ρ、θ）を近似直線のパラメータ（ρ、θ）とする
ように構成したことを特徴とする直線近似方式。(2) In the straight line approximation method that calculates an approximate straight line from input points, select points where the distance between any one point extracted from the input points and the predicted straight line is less than a predetermined threshold, and It is equipped with a parameter calculation unit (2) that calculates the parameters (ρ, θ) of a straight line passing through one point or the parameters (ρ, θ) of a line segment connecting any two points selected from these. The parameters (ρ, θ) calculated in part (2) are repeatedly added to the regions obtained by dividing the ρ-θ space into meshes, and the coordinates (ρ, θ) of the region with the maximum frequency are calculated using the parameters (ρ, θ) of the approximate straight line. , θ).
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1188039A JP2545610B2 (en) | 1989-07-20 | 1989-07-20 | Linear approximation method |
| US07/554,365 US5087969A (en) | 1989-07-20 | 1990-07-19 | Unmanned vehicle control system with guide line detection |
| DE69027633T DE69027633T2 (en) | 1989-07-20 | 1990-07-20 | Automatic vehicle guidance along guidance lines |
| EP90307947A EP0409642B1 (en) | 1989-07-20 | 1990-07-20 | Automatic guidance of vehicles along guide lines |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1188039A JP2545610B2 (en) | 1989-07-20 | 1989-07-20 | Linear approximation method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0352083A true JPH0352083A (en) | 1991-03-06 |
| JP2545610B2 JP2545610B2 (en) | 1996-10-23 |
Family
ID=16216604
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1188039A Expired - Lifetime JP2545610B2 (en) | 1989-07-20 | 1989-07-20 | Linear approximation method |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2545610B2 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5667127A (en) * | 1994-04-15 | 1997-09-16 | Hitachi Koki Co., Ltd. | Adjustment mechanism for adjusting depth at which pneumatic nailing machine drives nails into workpiece |
| JP2006307776A (en) * | 2005-04-28 | 2006-11-09 | Hideyuki Shimizu | Flushing device for inside of engine and its method |
-
1989
- 1989-07-20 JP JP1188039A patent/JP2545610B2/en not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5667127A (en) * | 1994-04-15 | 1997-09-16 | Hitachi Koki Co., Ltd. | Adjustment mechanism for adjusting depth at which pneumatic nailing machine drives nails into workpiece |
| JP2006307776A (en) * | 2005-04-28 | 2006-11-09 | Hideyuki Shimizu | Flushing device for inside of engine and its method |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2545610B2 (en) | 1996-10-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109191395B (en) | Image contrast enhancement method, device, device and storage medium | |
| JP6031554B2 (en) | Obstacle detection method and apparatus based on monocular camera | |
| CN108198141B (en) | Image processing method, device and computing device for realizing face-lifting special effect | |
| CN111488836A (en) | Face contour correction method, device, equipment and storage medium | |
| JP2012247364A (en) | Stereo camera apparatus, stereo camera system and program | |
| CN114777792B (en) | Path planning method, device, computer-readable medium, and electronic device | |
| CN115563732B (en) | Simulation optimization method and device for spraying trajectory based on virtual reality | |
| CN106408596B (en) | Edge-Based Local Stereo Matching Method | |
| CN111684462B (en) | An image matching method and vision system | |
| CN111105452A (en) | High and low resolution fusion stereo matching method based on binocular vision | |
| WO2021022643A1 (en) | Method and apparatus for detecting and tracking target in videos | |
| Babu et al. | An autonomous path finding robot using Q-learning | |
| CN112308897B (en) | Stereo matching method based on neighborhood information constraint and self-adaptive window | |
| CN103813056A (en) | Image stabilization method and device | |
| CN106447685B (en) | A kind of infrared track method | |
| CN106323190B (en) | The depth measurement method of customizable depth measurement range and the system of depth image | |
| CN105005381A (en) | Shake elimination method for virtual robot arm interaction | |
| CN103258318B (en) | A kind of image noise reduction disposal route and system | |
| TWI711005B (en) | Method for adjusting luminance of images and computer program product | |
| CN109934853B (en) | Correlation filtering tracking method based on response image confidence region adaptive feature fusion | |
| CN107680100A (en) | A kind of image detection and the method and apparatus of tracking concurrent collaborative work | |
| JP2021196977A (en) | Model generation device, method and program | |
| CN117437118A (en) | Image processing methods, devices and electronic equipment | |
| JP2545610B2 (en) | Linear approximation method | |
| Cao et al. | SiamIRPN: siamese visual tracking with improved region proposal networks |