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

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

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

### LineLocationのOpenLR
<dt>メイン処理の呼び出し</dt>
<dd>

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

```
decode(openlr, mapReader)
```
</dd>

(一部省略)

<dt>dereference_path

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

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

```
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

</dd>
<dt>nominate_candidates

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

```
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

</dd>
<dt>find_lines_close_to

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

```
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
```
</dd>
<dt>find_lines_close_to_query
</dt>
<dd>

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

</dd>
<dt>make_candidates

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

</dt>
<dd>

```
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値検証
</dd>

<dt>match_tail

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

<dd>

```
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

</dd>
<dt>handleCandidatePair

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

</dt>
<dd>

```
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
```
</dd>

<dt>get_candidate_route

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

</dt>
<dd>

```
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
```
</dd>

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