iBeacons의 삼각 측량 예제
저는 여러 개의 iBeacon을 사용하여 '거친'실내 위치 위치를 수행 할 가능성을 찾고 있습니다. 이 응용 프로그램은 일종의 '박물관'설정이며, 다른 개체와 개별 비콘에 대한 위치가있는 그리드를 형성하는 것이 더 쉬울 것입니다 (불가능하지는 않을 수도 있음).
여러 비콘을 사용하여 일종의 위치로 삼각 측량하는 예, 경험 또는 직접 작성하는 데 도움이되는 논리가 있습니까?
세 개의 비콘을 사용하여 정확한 위치를 얻기 위해 몇 가지 실험을 해왔습니다.
삼변 측량 결과
불행히도 결과는 품질면에서 매우 실망 스러웠습니다. 주로 두 가지 문제가있었습니다.
- 금속 및 신호에 영향을 미치는 기타 물체를 찾을 수있는 통제되지 않은 환경에서는 비콘의 수신 신호 강도가 너무 자주 변경되어 5 미터 미만의 오류 범위를 얻는 것이 불가능 해 보입니다.
- 사용자가 수신기 장치를 다루는 방식에 따라 판독 값도 많이 바뀔 수 있습니다. 사용자가 블루투스 안테나에 손을 대면 알고리즘의 입력 신호가 낮아 비콘이 장치에서 매우 멀리 떨어져 있어야합니다. 참조 이미지를 블루투스 안테나의 정확한 위치를 볼 수 있습니다.
가능한 해결책
이런 방식으로 내려가도록 적극적으로 낙담 한 Apple 엔지니어와 이야기를 나눈 후, 지금 사용하고 싶은 옵션은 무차별 대입입니다. X 미터마다 (X는 시스템에서 허용되는 최대 오류) 비콘을 설정하여 그리드에서 장치에 가장 가까운 비콘을 계산하고 다음을 가정하여 주어진 장치의 위치를이 비콘 그리드에서 추적 할 수 있습니다. 장치가 같은 위치에 있습니다.
삼변 측량 알고리즘
그러나 완성도를 위해 삼변 측량 알고리즘의 핵심 기능을 아래에서 공유합니다. 이 문서 의 단락 3 ( '알려진 3 가지 거리')을 기반으로합니다 .
- (CGPoint)getCoordinateWithBeaconA:(CGPoint)a beaconB:(CGPoint)b beaconC:(CGPoint)c distanceA:(CGFloat)dA distanceB:(CGFloat)dB distanceC:(CGFloat)dC {
CGFloat W, Z, x, y, y2;
W = dA*dA - dB*dB - a.x*a.x - a.y*a.y + b.x*b.x + b.y*b.y;
Z = dB*dB - dC*dC - b.x*b.x - b.y*b.y + c.x*c.x + c.y*c.y;
x = (W*(c.y-b.y) - Z*(b.y-a.y)) / (2 * ((b.x-a.x)*(c.y-b.y) - (c.x-b.x)*(b.y-a.y)));
y = (W - 2*x*(b.x-a.x)) / (2*(b.y-a.y));
//y2 is a second measure of y to mitigate errors
y2 = (Z - 2*x*(c.x-b.x)) / (2*(c.y-b.y));
y = (y + y2) / 2;
return CGPointMake(x, y);
}
다음은 trilateration / multilateration을 수행 할 오픈 소스 자바 라이브러리입니다 : https://github.com/lemmingapex/Trilateration
Apache Commons Math의 인기있는 비선형 최소 제곱 최적화 프로그램 인 Levenberg-Marquardt 알고리즘을 사용합니다.
double[][] positions = new double[][] { { 5.0, -6.0 }, { 13.0, -15.0 }, { 21.0, -3.0 }, { 12.42, -21.2 } };
double[] distances = new double[] { 8.06, 13.97, 23.32, 15.31 };
NonLinearLeastSquaresSolver solver = new NonLinearLeastSquaresSolver(new TrilaterationFunction(positions, distances), new LevenbergMarquardtOptimizer());
Optimum optimum = solver.solve();
// the answer
double[] calculatedPosition = optimum.getPoint().toArray();
// error and geometry information
RealVector standardDeviation = optimum.getSigma(0);
RealMatrix covarianceMatrix = optimum.getCovariances(0);
위키 백과 에있는 것과 같은 대부분의 학자적 사례 는 정확히 세 개의 원을 다루고 완벽하게 정확한 정보를 가정합니다. 이러한 상황은 정확한 답으로 훨씬 더 간단한 문제 공식화를 가능하게하며 일반적으로 실제 상황에서는 만족스럽지 않습니다.
측정 오류, 관심 영역 (타원) 또는 부피 (타원체)가 포함 된 거리가있는 R 2 또는 R 3 유클리드 공간의 문제는 일반적으로 점 대신 얻어집니다. 지역 대신 점 추정이 필요한 경우 면적 중심 또는 체적 중심을 사용해야합니다. R 2 공간은 고유 한 영역을 얻기 위해 최소한 3 개의 비 퇴화 지점과 거리가 필요합니다. 마찬가지로 R 3 공간은 고유 한 영역을 얻기 위해 적어도 4 개의 비 퇴화 지점과 거리가 필요합니다.
나는 이것을 조사했다. 삼변 측량을 원하는 용어입니다. (삼각 측량에서는 3 개의 알려진 지점으로부터의 각도가 있습니다. 삼각 측량에서는 3 개의 알려진 지점과의 거리가 있습니다.) Google을 사용하면 Wiki에서 하나를 포함하여 여러 기사를 찾을 수 있습니다. 3 개의 연립 방정식을 푸는 것이 포함됩니다. 제가 본 문서는 3D 삼변 측량을위한 것이 었습니다. Z 항만 놓을 수 있기 때문에 2D가 더 쉽습니다.
제가 찾은 것은 추상적 인 수학이었습니다. 일반 알고리즘을 특정 코드에 매핑하는 데 아직 시간이 걸리지 않았지만 언젠가는이를 다룰 계획입니다.
당신이 얻는 결과는 특히 빈 방을 제외한 모든 곳에서 매우 조잡 할 것입니다. 신호는 사람, 동상 또는 시선을 차단하는 모든 것이 거리 측정 값을 상당히 증가시킬 정도로 약합니다. 건설적인 간섭 (대부분 벽에서 발생)으로 인해 실제보다 훨씬 더 가깝게 읽을 수있는 건물의 장소도있을 수 있습니다.
iBeacon을 사용한 정확한 실내 위치 지정은 다음과 같은 이유로 어려울 것입니다.
- 이전 의견에서 지적했듯이 iBeacon 신호는 많이 변동하는 경향이 있습니다. 그 이유는 다중 경로 효과, 사람이 움직일 때 전화와 iBeacon 사이의 동적 물체 방해, 기타 2.4GHz 간섭 등이 있습니다. 따라서 이상적으로는 단일 패킷의 데이터를 신뢰하지 않고 대신 동일한 비콘에서 여러 패킷에 대해 평균을내는 것이 좋습니다. 전화 / 비콘 거리가 이러한 여러 패킷간에 너무 많이 변경되지 않아야합니다. 일반적인 BLE 패킷 (예 : StickNFind의 비콘)의 경우 10Hz 비콘 속도로 쉽게 설정할 수 있습니다. 그러나 iBeacon의 경우 어렵습니다.
- iBeacon의 비 커닝 주파수는 아마도 1Hz보다 높을 수 없습니다. 누군가가 그렇지 않다고 말하는 출처를 지적 할 수 있다면 기뻐할 것이지만 지금까지 본 모든 정보는이 주장을 확인합니다. 대부분의 iBeacon은 배터리로 작동하고 고주파수가 배터리 수명에 상당한 영향을 미치기 때문에 실제로 의미가 있습니다. 사람들의 평균 보행 속도가 5.3km (~ 1.5m / s)라는 점을 감안하면 보통 3 개의 비콘 패킷을 사용하여 평균화를하더라도 5m 이하의 정확도를 얻기 어려울 것입니다.
반면에 iBeacon 주파수를 10Hz 이상으로 늘릴 수 있다면 (가능한 것 같지 않음) 적절한 처리 방법을 사용하여 5m 이상의 정확도를 가질 수 있습니다. 첫째 , 삼변 측량과 같이 역 제곱 법칙을 기반으로하는 사소한 솔루션 은 실제로는 위의 이유 1로 인해 서로 다른 비콘에 대한 거리 / RSSI 관계가 종종 역 제곱 법칙에서 벗어나기 때문에 종종 잘 수행되지 않습니다. 그러나 RSSI가 특정 위치 (일반적으로 해당)의 특정 비콘에 대해 상대적으로 안정적인 한, 더 높은 정확도를 달성하기 위해 핑거 프린팅 이라는 접근 방식을 사용할 수 있습니다 . 핑거 프린팅에 사용되는 일반적인 방법은 kNN ( k-Nearest Neighbor )입니다.
업데이트 2014-04-24
일부 iBeacon은 Estimote가 기본적으로 5Hz를 사용하는 것처럼 1Hz 이상을 방송 할 수 있습니다 . 그러나이 링크 에 따르면 " 이것은 Apple 제한 사항입니다. IOS는 장치가 광고하는 빈도에 관계없이 매초마다 비콘 업데이트를 반환합니다. ". " 우리의 비콘은 훨씬 빠르게 브로드 캐스트 할 수 있으며 결과와 측정을 향상시킬 수 있습니다. "라는 또 다른 의견 (예상 Estimote 공급 업체) 이 있습니다 . 따라서 더 높은 iBeacon 주파수가 유익한지는 명확하지 않습니다.
당신이 나와 같은 사람이고 수학을 좋아하지 않는다면 "실내 위치 결정 SDK"에 대한 빠른 검색을 할 수 있습니다. 실내 포지셔닝을 서비스로 제공하는 회사가 많이 있습니다.
뻔뻔한 플러그 : 저는 indoo.rs 에서 일하며이 서비스를 추천 할 수 있습니다. 여기에는 "단지"실내 포지셔닝 외에도 라우팅 등이 포함됩니다.
장치에 대한 @Javier Chávarri삼변 측량 기능 이 필요한 경우 Android(시간 절약을 위해) :
public static Location getLocationWithTrilateration(Location beaconA, Location beaconB, Location beaconC, double distanceA, double distanceB, double distanceC){
double bAlat = beaconA.getLatitude();
double bAlong = beaconA.getLongitude();
double bBlat = beaconB.getLatitude();
double bBlong = beaconB.getLongitude();
double bClat = beaconC.getLatitude();
double bClong = beaconC.getLongitude();
double W, Z, foundBeaconLat, foundBeaconLong, foundBeaconLongFilter;
W = distanceA * distanceA - distanceB * distanceB - bAlat * bAlat - bAlong * bAlong + bBlat * bBlat + bBlong * bBlong;
Z = distanceB * distanceB - distanceC * distanceC - bBlat * bBlat - bBlong * bBlong + bClat * bClat + bClong * bClong;
foundBeaconLat = (W * (bClong - bBlong) - Z * (bBlong - bAlong)) / (2 * ((bBlat - bAlat) * (bClong - bBlong) - (bClat - bBlat) * (bBlong - bAlong)));
foundBeaconLong = (W - 2 * foundBeaconLat * (bBlat - bAlat)) / (2 * (bBlong - bAlong));
//`foundBeaconLongFilter` is a second measure of `foundBeaconLong` to mitigate errors
foundBeaconLongFilter = (Z - 2 * foundBeaconLat * (bClat - bBlat)) / (2 * (bClong - bBlong));
foundBeaconLong = (foundBeaconLong + foundBeaconLongFilter) / 2;
Location foundLocation = new Location("Location");
foundLocation.setLatitude(foundBeaconLat);
foundLocation.setLongitude(foundBeaconLong);
return foundLocation;
}
다음 알고리즘을 작성한 My Architect / Manager는
public static Location getLocationWithCenterOfGravity(Location beaconA, Location beaconB, Location beaconC, double distanceA, double distanceB, double distanceC) {
//Every meter there are approx 4.5 points
double METERS_IN_COORDINATE_UNITS_RATIO = 4.5;
//http://stackoverflow.com/a/524770/663941
//Find Center of Gravity
double cogX = (beaconA.getLatitude() + beaconB.getLatitude() + beaconC.getLatitude()) / 3;
double cogY = (beaconA.getLongitude() + beaconB.getLongitude() + beaconC.getLongitude()) / 3;
Location cog = new Location("Cog");
cog.setLatitude(cogX);
cog.setLongitude(cogY);
//Nearest Beacon
Location nearestBeacon;
double shortestDistanceInMeters;
if (distanceA < distanceB && distanceA < distanceC) {
nearestBeacon = beaconA;
shortestDistanceInMeters = distanceA;
} else if (distanceB < distanceC) {
nearestBeacon = beaconB;
shortestDistanceInMeters = distanceB;
} else {
nearestBeacon = beaconC;
shortestDistanceInMeters = distanceC;
}
//http://www.mathplanet.com/education/algebra-2/conic-sections/distance-between-two-points-and-the-midpoint
//Distance between nearest beacon and COG
double distanceToCog = Math.sqrt(Math.pow(cog.getLatitude() - nearestBeacon.getLatitude(),2)
+ Math.pow(cog.getLongitude() - nearestBeacon.getLongitude(),2));
//Convert shortest distance in meters into coordinates units.
double shortestDistanceInCoordinationUnits = shortestDistanceInMeters * METERS_IN_COORDINATE_UNITS_RATIO;
//http://math.stackexchange.com/questions/46527/coordinates-of-point-on-a-line-defined-by-two-other-points-with-a-known-distance?rq=1
//On the line between Nearest Beacon and COG find shortestDistance point apart from Nearest Beacon
double t = shortestDistanceInCoordinationUnits/distanceToCog;
Location pointsDiff = new Location("PointsDiff");
pointsDiff.setLatitude(cog.getLatitude() - nearestBeacon.getLatitude());
pointsDiff.setLongitude(cog.getLongitude() - nearestBeacon.getLongitude());
Location tTimesDiff = new Location("tTimesDiff");
tTimesDiff.setLatitude( pointsDiff.getLatitude() * t );
tTimesDiff.setLongitude(pointsDiff.getLongitude() * t);
//Add t times diff with nearestBeacon to find coordinates at a distance from nearest beacon in line to COG.
Location userLocation = new Location("UserLocation");
userLocation.setLatitude(nearestBeacon.getLatitude() + tTimesDiff.getLatitude());
userLocation.setLongitude(nearestBeacon.getLongitude() + tTimesDiff.getLongitude());
return userLocation;
}
- 삼각형의 무게 중심 계산 (비콘 3 개)
- 최단 거리 / 가장 가까운 비콘 계산
- 비콘과 무게 중심 사이의 거리 계산
- 최단 거리를 일정한 좌표 단위로 변환하여 정확도를 예측했습니다. 상수를 변경하여 테스트 할 수 있습니다.
- 거리 델타 계산
- 가장 가까운 비콘 x, y와 함께 델타를 추가합니다.
테스트 후 5 미터까지 정확하다는 것을 알았습니다.
우리가 그것을 구체화 할 수 있다면 당신의 테스트에 대해 의견을주십시오.
I've implemented a very simple Fingerprint algorithm for android 4.4, tested in a relative 'bad' environment:
- nearly 10 wifi AP nearby.
- several other Bluetooth signals nearby.
the accurate seems in 5-8 meters and depends on how I placed that 3 Ibeacon broadcaster. The algorithm is quite simple and I think you can implemented one by yourself, the steps are:
- load the indoor map.
- sampling with the map for all the pending positioning point.
- record all the sampling data, the data should include: map coordinate, position signals and their RSSI.
so when you start positioning, it's just a reverse of proceeding steps.
We are also trying to find the best way to precisely locate someone into a room using iBeacons. The thing is that the beacon signal power is not constant, and it is affected by other 2.4 Ghz signals, metal objects etc, so to achieve maximum precision it is necessary to calibrate each beacon individually, and once it has been set in the desired position. (and make some field test to see signal fluctuations when other Bluetooth devices are present). We have also some iBeacons from Estimote (the same of the Konrad Dzwinel's video), and they have already developed some tech demo of what can be done with the iBeacons. Within their App it is possible to see a Radar in which iBeacons are shown. Sometimes is pretty accurate, but sometimes it is not, (and seems phone movement is not being considered to calculate positions). Check the Demo in the video we made here: http://goo.gl/98hiza
Although in theory 3 iBeacons should be enough to achieve a good precision, maybe in real world situations more beacons are needed to ensure the precision you are looking for.
The thing that really helped me was this project on Code.Google.com: https://code.google.com/p/wsnlocalizationscala/ it contains lots of code, several trilateration algorithms, all written in C#. It's a big library, but not really meant to be used "out-of-the-box".
Please check the reference https://proximi.io/accurate-indoor-positioning-bluetooth-beacons/
Proximi SDK는 삼각 측량을 처리합니다. 이 SDK는 백그라운드에서 자동으로 비콘 위치 지정, 삼각 측량 및 필터링을위한 모든 로직을 처리하기위한 라이브러리를 제공합니다. 비콘 외에도 IndoorAtlas, Wi-Fi, GPS 및 셀룰러 위치를 결합 할 수 있습니다.
나는 Vishnu Prahbu의 솔루션이 매우 유용하다는 것을 알았습니다. 누구든지 필요하면 C #으로 포팅했습니다.
public static PointF GetLocationWithCenterOfGravity(PointF a, PointF b, PointF c, float dA, float dB, float dC)
{
//http://stackoverflow.com/questions/20332856/triangulate-example-for-ibeacons
var METERS_IN_COORDINATE_UNITS_RATIO = 1.0f;
//http://stackoverflow.com/a/524770/663941
//Find Center of Gravity
var cogX = (a.X + b.X + c.X) / 3;
var cogY = (a.Y + b.Y + c.Y) / 3;
var cog = new PointF(cogX,cogY);
//Nearest Beacon
PointF nearestBeacon;
float shortestDistanceInMeters;
if (dA < dB && dA < dC)
{
nearestBeacon = a;
shortestDistanceInMeters = dA;
}
else if (dB < dC)
{
nearestBeacon = b;
shortestDistanceInMeters = dB;
}
else
{
nearestBeacon = c;
shortestDistanceInMeters = dC;
}
//http://www.mathplanet.com/education/algebra-2/conic-sections/distance-between-two-points-and-the-midpoint
//Distance between nearest beacon and COG
var distanceToCog = (float)(Math.Sqrt(Math.Pow(cog.X - nearestBeacon.X, 2)
+ Math.Pow(cog.Y - nearestBeacon.Y, 2)));
//Convert shortest distance in meters into coordinates units.
var shortestDistanceInCoordinationUnits = shortestDistanceInMeters * METERS_IN_COORDINATE_UNITS_RATIO;
//http://math.stackexchange.com/questions/46527/coordinates-of-point-on-a-line-defined-by-two-other-points-with-a-known-distance?rq=1
//On the line between Nearest Beacon and COG find shortestDistance point apart from Nearest Beacon
var t = shortestDistanceInCoordinationUnits / distanceToCog;
var pointsDiff = new PointF(cog.X - nearestBeacon.X, cog.Y - nearestBeacon.Y);
var tTimesDiff = new PointF(pointsDiff.X * t, pointsDiff.Y * t);
//Add t times diff with nearestBeacon to find coordinates at a distance from nearest beacon in line to COG.
var userLocation = new PointF(nearestBeacon.X + tTimesDiff.X, nearestBeacon.Y + tTimesDiff.Y);
return userLocation;
}
대체 방정식
- (CGPoint)getCoordinateWithBeaconA:(CGPoint)a beaconB:(CGPoint)b beaconC:(CGPoint)c distanceA:(CGFloat)dA distanceB:(CGFloat)dB distanceC:(CGFloat)dC {
CGFloat x, y;
x = ( ( (pow(dA,2)-pow(dB,2)) + (pow(c.x,2)-pow(a.x,2)) + (pow(b.y,2)-pow(a.y,2)) ) * (2*c.y-2*b.y) - ( (pow(dB,2)-pow(dC,2)) + (pow(c.x,2)-pow(c.x,2)) + (pow(c.y,2)-pow(b.y,2)) ) *(2*b.y-2*a.y) ) / ( (2*b.x-2*c.x)*(2*b.y-2*a.y)-(2*a.x-2*b.x)*(2*c.y-2*b.y) );
y = ( (pow(dA,2)-pow(dB,2)) + (pow(c.x,2)-pow(a.x,2)) + (pow(b.y,2)-pow(a.y,2)) + x*(2*a.x-2*b.x)) / (2*b.y-2*a.y);
return CGPointMake(x, y);
}
참고 URL : https://stackoverflow.com/questions/20332856/triangulate-example-for-ibeacons
'IT TIP' 카테고리의 다른 글
| 어설 션이 실패 할 때 Python의 unittest에서 계속 (0) | 2020.10.24 |
|---|---|
| 마스터 이외의 브랜치에 대한 GitHub 기여자 그래프를 보는 방법은 무엇입니까? (0) | 2020.10.24 |
| IntelliJ에서 Maven 용 Java 버전을 변경하는 방법은 무엇입니까? (0) | 2020.10.23 |
| 이 문이 StackOverflowError를 발생시키지 않는 이유는 무엇입니까? (0) | 2020.10.23 |
| MySQL-삽입 오류 무시 : 중복 항목 (0) | 2020.10.23 |