private List < SequenceState < State , Observation , Path > > computeViterbiSequence ( List < TimeStep < State , Observation , Path > > timeSteps , int originalGpxEntriesCount , QueryGraph queryGraph ) { final HmmProbabilities probabilities = new HmmProbabilities ( measurementErrorSigma , transitionProbabilityBeta ) ; final ViterbiAlgorithm < State , Observation , Path > viterbi = new ViterbiAlgorithm <> ( ) ; logger . debug ( "\n=============== Paths ===============" ) ; int timeStepCounter = 0 ; TimeStep < State , Observation , Path > prevTimeStep = null ; int i = 1 ; for ( TimeStep < State , Observation , Path > timeStep : timeSteps ) { logger . debug ( "\nPaths to time step {}" , i ++ ) ; computeEmissionProbabilities ( timeStep , probabilities ) ; if ( prevTimeStep == null ) { viterbi . startWithInitialObservation ( timeStep . observation , timeStep . candidates , timeStep . emissionLogProbabilities ) ; } else { computeTransitionProbabilities ( prevTimeStep , timeStep , probabilities , queryGraph ) ; viterbi . nextStep ( timeStep . observation , timeStep . candidates , timeStep . emissionLogProbabilities , timeStep . transitionLogProbabilities , timeStep . roadPaths ) ; } if ( viterbi . isBroken ( ) ) { String likelyReasonStr = "" ; if ( prevTimeStep != null ) { Observation prevGPXE = prevTimeStep . observation ; Observation gpxe = timeStep . observation ; double dist = distanceCalc . calcDist ( prevGPXE . getPoint ( ) . lat , prevGPXE . getPoint ( ) . lon , gpxe . getPoint ( ) . lat , gpxe . getPoint ( ) . lon ) ; if ( dist > 2000 ) { likelyReasonStr = "Too long distance to previous measurement? " + Math . round ( dist ) + "m, " ; } } throw new IllegalArgumentException ( "Sequence is broken for submitted track at time step " + timeStepCounter + " (" + originalGpxEntriesCount + " points). " + likelyReasonStr + "observation:" + timeStep . observation + ", " + timeStep . candidates . size ( ) + " candidates: " + getSnappedCandidates ( timeStep . candidates ) + ". If a match is expected consider increasing max_visited_nodes." ) ; } timeStepCounter ++ ; prevTimeStep = timeStep ; } return viterbi . computeMostLikelySequence ( ) ; }
Computes the most likely candidate sequence for the GPX entries .