I try to mimic this algorithm, developed in Python, that calculates geolocation based on seen Wifi stations positions, itself based on this idea.
This algorithm uses at first a Numpy function in order to calculate a basic weighted average of observed latitudes and longitudes. To minimize the impact of possible Wifi positions errors, it’s also use the “scipy.optimize.leastsq” method in order to calculate in an statistical way and if possible, a more precise position.
I want to implement the same behavior on the Java Android platform.
For all other calculations I successfully rely on org.apache.commons.math3. So for the least-squares problem I logically try to rely on https://commons.apache.org/proper/commons-math/userguide/leastsquares.html.
My problem, if I well understood, is that Scipy manage for me the complexity of Jacobian function definition and my poor mathematics skills doesn't allow me to define correctly the model of a LeastSquaresProblem. I tried some experimentations based on this example, that seems closed to what I need, but the results aren't good as I don't know how to deal with the "jacobian" parts.
As someone do for this post, could someone do the same thing for me and try to explain it in a simple way?
More details on how Python part is working :
The “scipy.optimize.leastsq” statement used is:
(lat, lon), cov_x, info, mesg, ier =
scipy.optimize.leastsq(func, initial, args=data, full_output=True)
Where data are: latitude/longitude/age in milliseconds/signal strength, for example: data = numpy.array([(43.48932915, 1.66561772, 1000, -20), (43.48849093, 1.6648176, 2000, -10), (43.48818612, 1.66615113, 3000, -50)])
Initial is calculated weighted average latitude/longitude, in this example: initial = 43.48864654, 1.66550075
Function is
def func(initial, data):
return numpy.array([
geographic distance((float(point[latitude]), float(point[longitude])), (initial[latitude], initial[longitude])).meters * min(math.sqrt(2000.0 / float(point[age])), 1.0) / math.pow(float(point[signal strength]), 2)
The result is: 43.4885401095, 1.6648660983
My experiments in Java, I've replaced data values and have changed the way "modelI" is calculated. I simplified signal strength and age values. But it's a fact, and results show, that it isn't sufficient.
double modelI = calculateVincentyDistance(o.getY(), o.getX(), center.getY(), center.getX())* Math.min(Math.sqrt(2000.0/1000.0), 1.0) / Math.pow(-10, 2);
I also going to try https://github.com/odinsbane/least-squares-in-java, but I'm not sure to use it correctly as I don't master the way it's work.
FYI, I use Vincenty distance calculation that for example can be replaced by Haversine or Euclidean.
Thank you for any help !
The code is not easy to port because SciPy provides a more generic Least-squares minimization interface while Apache Commons Math provides curve fitting. Still many optimization problems can be restated as curve fitting. In the Python code you minimize
F(current_point) = Sum{ (distance(known_point[i], current_point) * weight[i])^2 } -> min
Java curve fitting problem is a bit different:
F(current_point) = Sum{ (target_value[i] - model[i](current_point))^2 } -> min
So equivalent fitting problem can be created by assigning all target_values to 0 and making model[i] calculate weighted distance from current_point to known_point[i].
In a general case such problems have no exact solution using formula and some numerical optimization method is used. And here lies another difference: Java implementation explicitly requires you to provide means for the optimizer to calculate derivatives of the function being optimized. Python code seems to use some kind of differences differentiator if Dfun is not provided. You can do something like this in Java by hand or using FiniteDifferencesDifferentiator but for simple formulas it might be easier to code them explicitly using DerivativeStructure
static class PositionInfo {
public final double latitude;
public final double longitude;
public final int ageMs;
public final int strength;
public PositionInfo(double latitude, double longitude, int ageMs, int strength) {
this.latitude = latitude;
this.longitude = longitude;
this.ageMs = ageMs;
this.strength = strength;
}
public double getWeight() {
return Math.min(1.0, Math.sqrt(2000.0 / ageMs)) / (strength * strength);
}
}
static DerivativeStructure getWeightedEuclideanDistance(double tgtLat, double tgtLong, PositionInfo knownPos) {
DerivativeStructure varLat = new DerivativeStructure(2, 1, 0, tgtLat); // latitude is 0-th variable of 2 for derivatives up to 1
DerivativeStructure varLong = new DerivativeStructure(2, 1, 1, tgtLong); // longitude is 1-st variable of 2 for derivatives up to 1
DerivativeStructure latDif = varLat.subtract(knownPos.latitude);
DerivativeStructure longDif = varLong.subtract(knownPos.longitude);
DerivativeStructure latDif2 = latDif.pow(2);
DerivativeStructure longDif2 = longDif.pow(2);
DerivativeStructure dist2 = latDif2.add(longDif2);
DerivativeStructure dist = dist2.sqrt();
return dist.multiply(knownPos.getWeight());
}
// as in https://en.wikipedia.org/wiki/Haversine_formula
static DerivativeStructure getWeightedHaversineDistance(double tgtLat, double tgtLong, PositionInfo knownPos) {
DerivativeStructure varLat = new DerivativeStructure(2, 1, 0, tgtLat);
DerivativeStructure varLong = new DerivativeStructure(2, 1, 1, tgtLong);
DerivativeStructure varLatRad = varLat.toRadians();
DerivativeStructure varLongRad = varLong.toRadians();
DerivativeStructure latDifRad2 = varLat.subtract(knownPos.latitude).toRadians().divide(2);
DerivativeStructure longDifRad2 = varLong.subtract(knownPos.longitude).toRadians().divide(2);
DerivativeStructure sinLat2 = latDifRad2.sin().pow(2);
DerivativeStructure sinLong2 = longDifRad2.sin().pow(2);
DerivativeStructure summand2 = varLatRad.cos().multiply(varLongRad.cos()).multiply(sinLong2);
DerivativeStructure sum = sinLat2.add(summand2);
DerivativeStructure dist = sum.sqrt().asin();
return dist.multiply(knownPos.getWeight());
}
Using such preparation you may do something like this:
public static void main(String[] args) {
// latitude/longitude/age in milliseconds/signal strength
final PositionInfo[] data = new PositionInfo[]{
new PositionInfo(43.48932915, 1.66561772, 1000, -20),
new PositionInfo(43.48849093, 1.6648176, 2000, -10),
new PositionInfo(43.48818612, 1.66615113, 3000, -50)
};
double[] target = new double[data.length];
Arrays.fill(target, 0.0);
double[] start = new double[2];
for (PositionInfo row : data) {
start[0] += row.latitude;
start[1] += row.longitude;
}
start[0] /= data.length;
start[1] /= data.length;
MultivariateJacobianFunction distancesModel = new MultivariateJacobianFunction() {
@Override
public Pair<RealVector, RealMatrix> value(final RealVector point) {
double tgtLat = point.getEntry(0);
double tgtLong = point.getEntry(1);
RealVector value = new ArrayRealVector(data.length);
RealMatrix jacobian = new Array2DRowRealMatrix(data.length, 2);
for (int i = 0; i < data.length; i++) {
DerivativeStructure distance = getWeightedEuclideanDistance(tgtLat, tgtLong, data[i]);
//DerivativeStructure distance = getWeightedHaversineDistance(tgtLat, tgtLong, data[i]);
value.setEntry(i, distance.getValue());
jacobian.setEntry(i, 0, distance.getPartialDerivative(1, 0));
jacobian.setEntry(i, 1, distance.getPartialDerivative(0, 1));
}
return new Pair<RealVector, RealMatrix>(value, jacobian);
}
};
LeastSquaresProblem problem = new LeastSquaresBuilder()
.start(start)
.model(distancesModel)
.target(target)
.lazyEvaluation(false)
.maxEvaluations(1000)
.maxIterations(1000)
.build();
LeastSquaresOptimizer optimizer = new LevenbergMarquardtOptimizer().
withCostRelativeTolerance(1.0e-12).
withParameterRelativeTolerance(1.0e-12);
LeastSquaresOptimizer.Optimum optimum = optimizer.optimize(problem);
RealVector point = optimum.getPoint();
System.out.println("Start = " + Arrays.toString(start));
System.out.println("Solve = " + point);
}
P.S. the logic of the weight seems suspicious to me. In the question you reference the OP has some estimates for radius and then it is an obvious weight. Using reverse square of the signal strength which is measured in logarithmic dBm seems strange to me.