Graph-Cut RANSAC for GNSS Outlier Detection in Urban Environments

In urban environments, Global Navigation Satellite System (GNSS) signals are frequently blocked or reflected by high-rise buildings, and the resulting non-line-of-sight (NLOS) and multipath measurements introduce large positioning errors. Random Sample Consensus (RANSAC) removes such measurements using no information other than the measurements themselves. It retains the minimal subset of satellites whose solution is supported by the largest number of the remaining measurements. The procedure assumes that correct measurements outnumber faulty ones and that faulty ones are mutually independent. In a street canyon the second assumption fails: buildings in a repeating pattern reflect several satellites alike, so their errors bias the position in a common direction and the subset with the highest consensus may be an erroneous one. This paper provides RANSAC with information on which satellites are likely to be affected in a correlated manner. Every pair of satellites is joined by an edge whose weight is large when the two are close together in the sky and their carrier-to-noise density ratios (C/N0) are similar, because such a pair is likely to be disturbed by the same structure. A candidate subset that separates a strongly connected pair is charged a penalty proportional to the weight of the broken edge, and the penalty is subtracted from the score by which the subsets are compared. The residual test that classifies each measurement is unchanged, so the graph affects only which subset is selected. The method was evaluated with multi-constellation (GPS, Galileo, and BeiDou) measurements collected in Seoul, South Korea, in a static test on Yeouidae-ro and a dynamic vehicle test on Teheran-ro. Compared with conventional RANSAC, the horizontal root-mean-square (RMS) error fell from 7.334 m to 3.384 m in the static test and from 10.114 m to 5.179 m in the dynamic test, with comparable reductions in the vertical component.