OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

3次元の近似直線

  • すぐに回答を!
  • 質問No.190632
  • 閲覧数2144
  • ありがとう数4
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 100% (2/2)

こんにちは。2次元で実験データなどの点列から近似直線を求めるのは、最小二乗法の基本問題ですが、3次元の点群から直線の方程式(x-x0)/a=(y-y0)/b=(z-z0)/cを求めるにはどんなアルゴリズムを使いますか?スマートな方法があれば教えていただけたら幸いです。よろしくお願いします。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル14

ベストアンサー率 57% (1014/1775)

3次元空間の曲面ではなく、直線に乗ると仰るのだから、
(1) x, y, zのどれかを与えて、残りの2つを推定する問題。
(2) <x[i],y[i],z[i]>と直線との距離d[i]の二乗和が最小になる直線を求める問題。
と分類すべきでしょう。

(1)の場合は、たとえばzを与えてx,yを求めたいのであれば、
・zからxを求める問題。
・zからyを求める問題。
の二つを別々に解けばおしまいです。
それぞれの解は(x=Az+B, yは任意)という平面と、(y=Cz+D, xは任意)という平面を定めますから、この二つの平面の交線が、求める直線ということですね。

(2)の場合はやっかいです。
[1]ちょっと手抜きしながらも、まともにやってみましょう。
(i) 直線をどう表すか。
ご質問の式を見ると、この直線はx軸、y軸、z軸のどれとも平行でも垂直でもないことが仮定されています。
ですから、zをパラメータとして
x=az+c
y=bz+d
と書いても良いでしょう。a,b,c,dが決められれば良い訳です。
(ii) 点<p,q,r>と直線との最短距離を求める。
直線上の任意の点<az+c,bz+d, z>と点<p,q,r>の距離をdとすると
d^2 = (az+c-p)^2+(bz+d-q)^2+(z-r)^2
= (az)^2+2az(c-p)+(c-p)^2+(bz)^2+2bz(d-q)+(d-q)^2+z^2-2rz+r^2
です。これが最小になるzを求めると、
0=∂(d^2)/∂z = 2(az+c-p)a+2(bz+d-q)b+2(z-r)
ゆえに
z=(ap+bq+r-ac-bd)/(a^2+b^2+1)
であって、このときの最短距離h(p,q,r)は
h(p,q,r)^2 = (ap+bq+r-ac-bd)^2/(a^2+b^2+1)+2(ap+bq+r-ac-bd)(ac-ap+bd-bq-r)/(a^2+b^2+1)+(c-p)^2+(d-q)^2+r^2
わあ、とんでもないですね。
(iii) じゃあ、直線を求めるには?
S=Σ(h(x[i],y[i],z[i]))^2  (i=1,2,...,N)
を最小化するには
∂S/∂a = 0
∂S/∂b = 0
∂S/∂c = 0
∂S/∂d = 0
を解く必要があります。言い換えれば
∂(h(x[i],y[i],z[i]))/∂a
∂(h(x[i],y[i],z[i]))/∂b
∂(h(x[i],y[i],z[i]))/∂c
∂(h(x[i],y[i],z[i]))/∂d
を求めておいて
Σh(x[i],y[i],z[i]) (∂(h(x[i],y[i],z[i]))/∂a)=0
Σh(x[i],y[i],z[i]) (∂(h(x[i],y[i],z[i]))/∂b)=0
Σh(x[i],y[i],z[i]) (∂(h(x[i],y[i],z[i]))/∂c)=0
Σh(x[i],y[i],z[i]) (∂(h(x[i],y[i],z[i]))/∂d)=0
という連立方程式を解くことになります。
これがa,b,c,dについて非線形である(一次式でない)ことは言うまでもありません。一筋縄では行かず、反復計算で徐々に収束させていくしかありません。

[2]手抜き
もうすこし手抜きの方法を考えてみましょう。
この座標系を回転・平行移動した座標系をX-Y-Zとします。そして、求めたい直線がZ軸と一致するようにしたとします。回転と平行移動は行列を使って
X = R x + p
Y     y   q
Z     z   r
と表せます。Rは3×3の行列で Rの転置をR'とすると RR' = R' R = 単位行列
となる行列です。各点<x[i],y[i],z[i]>をこの変換で<X[i],Y[i],Z[i]>に写したとすると、
直線、すなわちZ軸との最短距離はX[i]^2 + Y[i]^2ですから、他のどんな回転・平行移動の仕方に比べても
U=Σ(X[i]^2 + Y[i]^2)  (i=1,2,....,N)
が最小になっている筈で、しかも
S=U
です。
 さて、UはZ[i]の値とは無関係ですからZ[i]を求める必要はない。さらに座標系をZ軸の周りで回転してもUは変化しません。従って、
X = R x + p
Y     y   q
      z
R =P(α)Q(β)
P(α)=cosα  0  -sinα
       0   1    0
Q(β)= 1  0     0
      0 cosβ -sinβ
      0 sinβ  cosβ
とすれば良いのです。展開すれば
X[i] = x[i]cosα-y[i]sinαsinβ-z[i]sinαcosβ+p
Y[i] = y[i]cosβ-z[i]sinβ+q
ですね。
ここでα、β、p、qを決めたい訳です。

 始めに(1)の問題を解けば、α、β、p、qの大体の値を求めることができます。これを使ってU(α,β,p,q)を計算します。
 それから、U(α,β,p,q)が小さくなるようにα、β、p、qをちょっとずつ改良して行けば良いでしょう。これには微小な角度Δα、Δβを使って、
P(Δα)=cosΔα  0  -sinΔα
        0    1    0
      sinΔα  0   cosΔα
Q(Δβ)= 1  0      0
       0 cosΔβ -sinΔβ
       0 sinΔβ  cosΔβ
を作り、P(α)、Q(α)にそれぞれ掛け算すれば良い。
P(α+Δα)=P(Δα)P(α)
Q(β+Δβ)=Q(Δβ)Q(β)
だからです。さらにここで、Δα、Δβは微小だから、
cosΔα≒1、cosΔβ≒1、sinΔα≒Δα、sinΔβ≒Δβ
(Δα)^2≒0、(Δβ)^2≒0、ΔαΔβ≒0
という近似をしても構わないでしょう。
この近似を利用すると計算は一層簡単になり、Uを最小にするようにΔα、Δβ、p、qを求める問題は線形最小二乗法(一次式の最小二乗法)になってしまい、簡単に解けます。
それを解いてから、真面目にP(α)、Q(α)を計算しなおし、また線形最小二乗法を解く。これを収束するまで繰り返せば良いのです。

なお、stomachmanは計算間違いの常習犯ですから、チェックは慎重に。
お礼コメント
lovetheearth

お礼率 100% (2/2)

ありがとうございました。非常に理解しやすく、活用することができました。また、内容も大変興味深いので、仕事の合間を見つけて非線形最小二乗法も勉強しようと思います。今後とも、よろしくお願いいたします。よいお年をお迎えください。
投稿日時 - 2001-12-28 10:57:07
-PR-
-PR-

その他の回答 (全1件)

  • 回答No.1
レベル14

ベストアンサー率 57% (1014/1775)

求めた直線の式をどう使う積もりなのかによって、やり方は違います。 用途に適した「近似」がどういうものであるか、をまず検討しなくてはなりません。さらに、たとえば「近似」を最小二乗の意味であると決めたとしても、まだ話は決まりません。 2次元の場合でも、話は単純ではないんです。 (1)「データ<x[i],y[i]> (i=1,2,....,N)から f(x) = a x + b と ...続きを読む
求めた直線の式をどう使う積もりなのかによって、やり方は違います。

用途に適した「近似」がどういうものであるか、をまず検討しなくてはなりません。さらに、たとえば「近似」を最小二乗の意味であると決めたとしても、まだ話は決まりません。

2次元の場合でも、話は単純ではないんです。
(1)「データ<x[i],y[i]> (i=1,2,....,N)から
f(x) = a x + b
というモデルについて、
Σ(f(x[i])-y[i])^2
が最小になるようにa,bを決める。」
というのが典型的な最小二乗法の問題で、こうして求めた
f(x) = a x + b
は、測定値xからyの値を推定するのに用いる式です。

しかしこれを
(y-b)/a
と変形して測定値yからxを推定するのに使ったら誤りなんです。それがやりたければ
(2)「データ<x[i],y[i]> (i=1,2,....,N)から
g(y) = A y + B
というモデルについて、
Σ(g(x[i])-y[i])^2
が最小になるようにA,Bを決める。」
という問題を解かなくてはなりません。そうやって求めたA,Bは
A y + B ≠(y-b)/a
なんです。

(3) 2次元平面に点<x[i],y[i]> (i=1,2,....,N)が打ってある。これらのなるべく近くを通る直線を求めよ。
という問題ですと、これまた別の話になります。(1),(2)の場合にはx軸、y軸を何倍に引き延ばそうとa,b,A,Bの値に変化はありませんが、(3)ではそうは行かない。
x=αt+x0
y=βt+y0
という直線と、各点との距離を小さくしたい。ですから、
点<x[i],y[i]>とこの直線の距離をd[i]とすれば
d[i]^2 = (αt[i]+x0-x[i])^2+(βt[i]+y0-y[i])^2
ここにt[i] = (α(x[i]-x0)+β(y[i]-y0))/ (α^2+β^2)
です。よって、
Σ(d[i]^2)
を最小にするα,β,x0,y0(たとえばα≧0, (α^2+β^2)=1, x0 y0 = 0という条件を追加すると一意的に決まります)を求める問題です。

かくて、ご質問は3次元の場合ですけど、どう使うのかを明示して戴かないと答は出ません。
お礼コメント
lovetheearth

お礼率 100% (2/2)

丁寧なご説明ありがとうございます。(1)と(2)、(3)混同して考えてました。確かにそれぞれの解は異なりますよね。そうすると、3次元の場合では、x、yからzを推定する場合と、同様にx、yを推定する場合、各点からなるべく近くを通る直線を求める場合に分類されるわけですね。今回の私の求めたいのは、最後の問題(3)です。よろしくお願いします。もしご面倒でなければ、最初の問題の場合も教えていただけると非常に嬉しいです。すみませんが、お世話になります。
投稿日時 - 2001-12-27 02:25:14

このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ