Perkirakan pusat dan jari-jari bola dari titik-titik di permukaan

9

Jika kita mengasumsikan bahwa titik data kita disampel dari permukaan bola (dengan beberapa gangguan), bagaimana kita dapat memulihkan pusat bola itu?

Dalam pencarian saya, saya menemukan makalah tentang sesuatu yang diberi label "regresi bola", tetapi sepertinya tidak melakukan hal yang sama. Mungkin saya hanya tidak memahaminya.

Apakah ada rumus langsung, mirip dengan regresi linier, yang menemukan titik pusat bola dan jari-jari yang meminimalkan jarak kuadrat dari satu set titik data dari permukaan bola?


Edit 1:

Kita dapat mengasumsikan bahwa derau akan 2 atau 3 orde besarnya lebih kecil dari jari-jari bola dan Gaussian berbentuk bola yang seragam. Namun, sampel itu sendiri pasti tidak akan diambil secara seragam dari permukaan bola, tetapi kemungkinan akan dikelompokkan dalam beberapa tambalan di permukaan, kemungkinan semua dalam satu belahan bumi. Solusi yang berfungsi untuk data dalamR3 baik-baik saja, tetapi solusi umum untuk dimensi arbitrer juga bagus.


Edit 2:

Apa peluang saya mendapatkan jawaban yang masuk akal jika saya menggunakan regresi linier, y=Xβ+ϵ, dalam ruang 7 dimensi berpura-pura bahwa komponen kuadrat independen dari parameter lain:

X=[2x2y2z1111]β=[x0y0z0x02y02z02r2]y=x2+y2+z2

Paling-paling, saya kira metrik kesalahan saya akan sedikit aneh. Paling buruk solusinya bahkan tidak akan mendekati konsisten.
... atau itu konyol karena dengan empat kolom identik, kita mendapatkan matriks singular ketika kita mencoba melakukan regresi.


Edit 3:

Jadi, sepertinya ini adalah opsi saya:

  1. Optimasi numerik non-linear menggunakan beberapa fungsi biaya: f(x0,y0,z0,r|X)=12i=1n(r(xix0)2+(yiy0)2+(ziz0)2)2
  2. Hough-transform: diskritkan ruang yang masuk akal atau kemungkinan pusat dan jari-jari di sekitar titik data. Setiap titik memberikan suara untuk pusat-pusat potensial yang bisa menjadi bagian dari setiap diskritisasi radius tertentu. Kebanyakan suara menang. Ini mungkin baik-baik saja jika ada potensi jumlah bola yang tidak diketahui, tetapi dengan hanya satu itu solusi yang berantakan.
  3. Secara acak (atau sistematis) memilih grup dengan 4 poin dan secara analitik menghitung pusat . Tolak pengambilan sampel jika tidak dikondisikan (poin hampir co-planar). Tolak pencilan dan temukan pusat nilai tengah. Dari sana kita dapat menemukan radius rata-rata.

Adakah yang punya metode yang lebih baik?

JCooper
sumber
Perhatikan bahwa kedua bentuk pertanyaan Anda tidak setara: itu tidak selalu berarti bahwa meminimalkan jumlah kuadrat jarak dari permukaan memberikan perkiraan terbaik kecuali asumsi kuat dibuat tentang sifat gangguan. Oleh karena itu akan membantu untuk mengetahui lebih banyak tentang bagaimana gangguan terjadi (dan seberapa besar mereka dapat dibandingkan dengan ukuran bola). Juga: berapa banyak dimensi bola Anda?
whuber
@whuber saya bermaksud mendefinisikan yang paling cocok sebagai yang meminimalkan jarak jumlah-kuadrat dari data dari titik terdekat di permukaan bola. Saya tidak banyak berpikir tentang asumsi yang menyertainya. Saya mengharapkan kesalahan kecil yang proporsional; jadi mungkin metrik yang tepat tidak terlalu penting, meskipun saya ingin tahu apa fungsi yang diminimalkan. Saya telah menambahkan lebih banyak informasi tentang suara ke pertanyaan.
JCooper
@ Max Saya memang melihat itu. Tapi itu situs untuk produk komersial kotak hitam. Ini adalah formula yang sebenarnya saya tertarik. Ini mulai terlihat seperti tidak ada solusi bentuk tertutup dan saya harus menggunakan pendekatan numerik sebagai gantinya (yang saya anggap juga dilakukan oleh perangkat lunak nlReg).
JCooper
sepertinya ini bisa menjadi masalah minimisasi langsung dengan fungsi tujuan nonlinear (yang Anda sebutkan di atas). jika kesalahan dianggap gaussian, Anda hanya perlu menghitung parameter distribusi kesalahan setelah Anda menemukan pusat bola meminimalkan fungsi tujuan. sunting: saya membiarkan halaman terbuka terlalu lama dan tidak melihat komentar Anda. kami memiliki ide yang sama.
Diasumsikan normal
2
Edit 3: Diberikan (x0,y0,z0), rmudah ditemukan. Untuk memperoleh(x0,y0,z0), Metode Newton harus konvergen dengan cepat dari beberapa nilai awal yang masuk akal yang diperoleh seperti pada (3).
whuber

Jawaban:

3

Berikut adalah beberapa Rkode yang menunjukkan satu pendekatan menggunakan kuadrat terkecil:

# set parameters

mu.x <- 8
mu.y <- 13
mu.z <- 20
mu.r <- 5
sigma <- 0.5

# create data
tmp <- matrix(rnorm(300), ncol=3)
tmp <- tmp/apply(tmp,1,function(x) sqrt(sum(x^2)))

r <- rnorm(100, mu.r, sigma)

tmp2 <- tmp*r

x <- tmp2[,1] + mu.x
y <- tmp2[,2] + mu.y
z <- tmp2[,3] + mu.z


# function to minimize
tmpfun <- function(pars) {
    x.center <- pars[1]
    y.center <- pars[2]
    z.center <- pars[3]
    rhat <- pars[4]

    r <- sqrt( (x-x.center)^2 + (y-y.center)^2 + (z-z.center)^2 )
    sum( (r-rhat)^2 )
}

# run optim
out <- optim( c(mean(x),mean(y),mean(z),diff(range(x))/2), tmpfun )
out


# now try a hemisphere (harder problem)

tmp <- matrix(rnorm(300), ncol=3)
tmp[,1] <- abs(tmp[,1])
tmp <- tmp/apply(tmp,1,function(x) sqrt(sum(x^2)))

r <- rnorm(100, mu.r, sigma)

tmp2 <- tmp*r

x <- tmp2[,1] + mu.x
y <- tmp2[,2] + mu.y
z <- tmp2[,3] + mu.z

out <- optim( c(mean(x),mean(y),mean(z),diff(range(y))/2), tmpfun )
out

Jika Anda tidak menggunakan Rmaka Anda masih bisa mengikuti logika dan traslate ke bahasa lain.

Secara teknis parameter jari-jari harus dibatasi oleh 0, tetapi jika variabilitasnya relatif kecil terhadap jari-jari yang sebenarnya maka metode yang tidak terikat harus bekerja dengan baik, atau optim memiliki opsi untuk melakukan optimasi yang dibatasi, (atau Anda bisa melakukan nilai absolut dari jari-jari dalam fungsi untuk meminimalkan).

Greg Snow
sumber
+1 Ini sangat keren. Untuk alasan yang egois, saya ingin melihat suntingan yang (1) menjelaskan mengapa pusat massa dari titik sampel adalah perkiraan bias dari pusat bola yang sebenarnya, dan (2) komentar atau dua ditambahkan ke kode yang menjelaskan logika dari fungsi minimisasi, sebagai solusi untuk menghindari bias menggunakan centroid.
Alexis