OpenLRのデコードロジックの裏側を調べてみた

はじめに

この記事では、openlr-dereferencer-pythonを実装してみたで説明したOpenLRのデコード処理の裏側がどのようになっているのかを解説します。上記記事で使用したコードと合わせてみると理解しやすいです。
個人的な調査なので、間違いがある可能性も高いですがその場合はご指摘いただけると幸いです。

本記事では初級者にも読みやすいコードに一部変更しております。実際のコードはご自身でご確認ください。また、ロジックの流れの大枠を理解するためにコメントの削除やコードの一部削除をしておりますがご容赦ください。
※全てのロジックを解説しているわけではありませんので、ご了承ください。

LineLocationのOpenLR

メイン処理の呼び出し

• openlr: デコードするOpenLR
• mapReader: MapReaderを実装したクラスインスタンス

decode(openlr, mapReader)

(一部省略)

dereference_path

始点のLRPに対して候補リストを生成する

• 戻値: Route型リスト
• 引数:
  • lrps: OpenLRに含まれるLocation Reference Point群
  • reader: MapReaderを実装したクラスインスタンス
  • config: デコードパラメータ(ここではデフォルト値を使用)
  • observer: 本記事では割愛

first_lrp = lrps[0]
first_candidates = list(nominate_candidates(first_lrp, reader, config, False))

linelocationpath = match_tail(first_lrp, first_candidates, lrps[1:], reader, config, observer)
return linelocationpath

呼び出し関数

• nominate_candidates
• match_tail

nominate_candidates

• 戻値: Candidate型
• 引数:
  • lrps: OpenLRに含まれるLocation Reference Point群
  • reader: MapReaderを実装したクラスインスタンス
  • config: デコードパラメータ(ここではデフォルト値を使用)
  • is_last_lrp: 最後のLRPの場合はTrue

targetLines = reader.find_lines_close_to(coords(lrp), config.search_radius)
retCandidates = []
for line in targetLines:
    tmp = make_candidates(lrp, line, config, is_last_lrp)
    retCandidates.append(tmp)
return retCandidates

呼び出し関数

• find_lines_close_to
• make_candidates

find_lines_close_to

• 戻値: MyLine型リスト
• 引数:
  • self: 割愛(クラス内関数の定義時に必要なパラメータ)
  • coord: LRPの緯度経度
  • dist: 検索対象半径(config.search_radius)

lon, lat = coord.lon, coord.lat
with self.connection.cursor() as cursor:
    cursor.execute(self.find_lines_close_to_query, (lon, lat, dist))
    retLines = []
    
    for (line_id, fow, _, frc, length, from_int, to_int, geom) in cursor:
        ls = LineString(wkb.loads(geom, hex=True))
        l = MyLine(self, line_id, FOW(fow), FRC(frc), length, from_int, to_int, ls)
        retLines.append(l)
    
    return retLines

find_lines_close_to_query

MyMapReaderのfind_lines_close_to_query変数を呼び出す
SQL文の中身は割愛

make_candidates

• 戻値: Candidate型
• 引数:
  • lrp: 対象のLRP
  • line: MapLineを実装したクラスインスタンス(find_lines_close_toの戻り値)
  • config: デコードパラメータ(ここではデフォルト値を使用)
  • is_last_lrp: 最後のLRPの場合はTrue

reloff = 0.0 # 割愛
candidate = Candidate(line, reloff)
bearing = compute_bearing(lrp, candidate, is_last_lrp, config.bear_dist)
bear_diff = angle_difference(bearing, lrp.bear)
if abs(bear_diff) > config.max_bear_deviation:
    return
candidate.score = score_lrp_candidate(lrp, candidate, config, is_last_lrp)
if candidate.score >= config.min_score:
    return candidate

呼び出し関数

• compute_bearing: bearingの計算
• angle_difference: LRPのbearingと計算したbearingの誤差
• score_lrp_candidate: candidateとLRP値検証

match_tail

• 戻値: Route型リスト
• 引数:
  • current: 対象のLRP
  • candidates: 対象LRPの候補リスト
  • tail: 対象LRP以降のLRPリスト
  • reader: MapReaderを実装したクラスインスタンス
  • config: デコードパラメータ(ここではデフォルト値を使用)

last_lrp = len(tail) == 1
minlen = (1 - config.max_dnp_deviation) * current.dnp - config.tolerated_dnp_dev
maxlen = (1 + config.max_dnp_deviation) * current.dnp + config.tolerated_dnp_dev
lfrc = config.tolerated_lfrc[current.lfrcnp]

next_lrp = tail[0]
next_candidates = list(nominate_candidates(next_lrp, reader, config, last_lrp))

pairs = list(product(candidates, next_candidates))
pairs.sort(key=lambda pair: (pair[0].score + pair[1].score), reverse=True)

for (c_from, c_to) in pairs:
    route = handleCandidatePair((current, next_lrp), (c_from, c_to), observer, lfrc, minlen, maxlen)
    if route is None:
        continue
    if last_lrp:
        return [route]
    try:
        return [route] + match_tail(next_lrp, [c_to], tail[1:], reader, config, observer)
    except LRDecodeError:
        continue

呼び出し関数

• handleCandidatePair
• match_tail

handleCandidatePair

• 戻値:Route型
• 引数:
  • lrps:[対象LRP, 次のLRP]
  • candidates:[from candidate, to candidate]
  • lowest_frc:候補探索の条件(FRCの最低値)
  • minlen:候補探索の条件(DNP)
  • maxlen:候補探索の条件(DNP)

current, next_lrp = lrps
source, dest = candidates
route = get_candidate_route(source, dest, lowest_frc, maxlen)
if not route:
    return None

length = route.length()
if length < minlen or length > maxlen:
    return None

return route

get_candidate_route

• 戻値:Route型
• 引数:
  • start:Candidate型
  • dest:Candidate型
  • lfrc:Lowest FRC(LRPより)
  • maxlen: DNP(LRPより)

if start.line.line_id == dest.line.line_id:
    return Route(start, [], dest)
    linefilter = lambda line: line.frc <= lfrc
    try:
        path = shortest_path(start.line.end_node, dest.line.start_node, linefilter, maxlen=maxlen)
        return Route(start, path, dest)
    except LRPathNotFoundError:
        return None

まとめ

デコードの結果に特に直結するのが、make_candidates関数内のscore_lrp_candidate関数です。ここで使用されるconfigの各パラメータを対象地図に合うように調整してください。