659.7 TF2 좌표 변환 트리 (Transform Tree) 구조

1. 변환 트리의 개념

TF2에서 좌표 변환 트리(Transform Tree)는 로봇 시스템의 모든 좌표 프레임 간의 공간적 관계를 체계적으로 표현하는 자료 구조이다. 변환 트리는 그래프 이론(graph theory)에서의 유근 트리(rooted tree)로 모델링되며, 각 노드는 좌표 프레임을, 각 엣지는 두 프레임 간의 강체 변환(rigid body transformation)을 나타낸다.

변환 트리는 다음과 같은 형식적 정의를 가진다.

$\mathcal{T} = (V, E)$

여기서 $V = \{f_1, f_2, \ldots, f_n\}$ 는 좌표 프레임의 집합이고, $E = \{(f_i, f_j) \mid f_i \text{는 } f_j\text{의 부모 프레임}\}$ 은 프레임 간 변환의 집합이다. 각 엣지 $(f_i, f_j)$ 에는 부모 프레임 $f_i$ 에서 자식 프레임 $f_j$ 로의 시간 종속적 변환 ${}^{f_i}T_{f_j}(t)$ 가 부여된다.

2. 트리 구조의 특성

2.1 계층적 구조

변환 트리는 엄격한 계층적 구조를 따른다. 최상위에는 루트 프레임(root frame)이 위치하며, 모든 다른 프레임은 루트 프레임에서 하향으로 분기하는 경로를 통해 연결된다. 일반적인 이동 로봇 시스템에서 변환 트리의 계층 구조는 다음과 같다.

map (글로벌 참조 프레임)
 └── odom (오도메트리 프레임)
      └── base_link (로봇 본체 프레임)
           ├── base_footprint (지면 투영 프레임)
           ├── laser_frame (LiDAR 프레임)
           ├── camera_link (카메라 링크 프레임)
           │    └── camera_optical_frame (카메라 광학 프레임)
           ├── imu_link (IMU 프레임)
           └── arm_base_link (매니퓰레이터 기저 프레임)
                ├── link_1
                │    └── link_2
                │         └── link_3
                │              └── ...
                │                   └── ee_link (말단 장치 프레임)
                └── ...

2.2 유일 경로 보장

트리 구조의 핵심적인 특성은 임의의 두 노드 간의 경로가 유일하게 결정된다는 것이다. 이는 두 프레임 간의 좌표 변환이 항상 유일한 결과를 산출함을 보장한다. 그래프 이론에서 $n$ 개의 노드를 가진 트리는 정확히 $n-1$ 개의 엣지를 가지며, 임의의 두 노드 사이에 정확히 하나의 단순 경로(simple path)가 존재한다.

2.3 부모-자식 관계

트리의 각 엣지는 부모 프레임(parent frame)에서 자식 프레임(child frame)으로의 방향성을 가진다. 루트 프레임을 제외한 모든 프레임은 정확히 하나의 부모 프레임을 가지며, 하나의 프레임은 여러 자식 프레임을 가질 수 있다.

부모 프레임 $f_p$ 에서 자식 프레임 $f_c$ 로의 변환 ${}^{f_p}T_{f_c}$ 는 자식 프레임의 원점과 방향이 부모 프레임에서 어떻게 관측되는지를 기술한다. 즉, 자식 프레임에서 표현된 점 ${}^{f_c}p$ 를 부모 프레임에서의 좌표 ${}^{f_p}p$ 로 변환하는 관계는 다음과 같다.

${}^{f_p}p = {}^{f_p}T_{f_c} \cdot {}^{f_c}p$

3. 변환 체인과 경로 탐색

3.1 변환 체인의 합성

임의의 두 프레임 $f_a$ 와 $f_b$ 사이의 변환은 트리에서 두 프레임을 연결하는 경로 상의 모든 개별 변환을 합성하여 계산된다. 프레임 $f_a$ 에서 $f_b$ 까지의 경로가 $f_a \to f_1 \to f_2 \to \cdots \to f_b$ 일 때:

${}^{f_a}T_{f_b} = {}^{f_a}T_{f_1} \cdot {}^{f_1}T_{f_2} \cdot \cdots \cdot {}^{f_{k}}T_{f_b}$

경로의 방향이 엣지 방향과 반대인 경우(즉, 자식에서 부모로 이동하는 경우), 해당 변환의 역행렬이 사용된다.

${}^{f_c}T_{f_p} = \left({}^{f_p}T_{f_c}\right)^{-1}$

3.2 최저 공통 조상 (LCA)

임의의 두 프레임 $f_a$ 와 $f_b$ 사이의 변환을 계산하기 위해, TF2는 먼저 두 프레임의 최저 공통 조상(LCA, Lowest Common Ancestor)을 찾는다. LCA는 두 프레임의 공통 조상 중 트리에서 가장 깊은 노드이다.

LCA $f_{lca}$ 를 찾은 후, 변환은 다음과 같이 계산된다.

${}^{f_a}T_{f_b} = \left({}^{f_{lca}}T_{f_a}\right)^{-1} \cdot {}^{f_{lca}}T_{f_b}$

이때 ${}^{f_{lca}}T_{f_a}$ 와 ${}^{f_{lca}}T_{f_b}$ 는 각각 LCA에서 $f_a$ 와 $f_b$ 까지의 하향 경로를 합성한 변환이다.

3.3 경로 탐색 알고리즘

BufferCore의 내부 경로 탐색 알고리즘은 다음과 같은 단계로 수행된다.

조상 경로 추적: 소스 프레임에서 루트까지의 조상 경로와 타겟 프레임에서 루트까지의 조상 경로를 각각 추적한다.
LCA 식별: 두 조상 경로에서 처음으로 교차하는 노드를 LCA로 식별한다.
변환 계산: 소스 프레임에서 LCA까지의 역변환과 LCA에서 타겟 프레임까지의 순변환을 합성한다.

이 알고리즘의 시간 복잡도는 트리의 높이에 비례하는 $O(h)$ 이며, 여기서 $h$ 는 트리의 최대 깊이이다.

4. 변환 트리의 실제 예시

4.1 단순 이동 로봇

LiDAR와 카메라를 탑재한 단순 이동 로봇의 변환 트리는 다음과 같다.

map
 └── odom
      └── base_link
           ├── laser_frame
           └── camera_link
                └── camera_optical_frame

이 트리에서 laser_frame에서 camera_optical_frame으로의 변환을 조회하면, TF2는 다음 경로를 탐색한다.

LCA: base_link
변환: ${}^{\text{laser}}T_{\text{camera\_optical}} = \left({}^{\text{base\_link}}T_{\text{laser}}\right)^{-1} \cdot {}^{\text{base\_link}}T_{\text{camera\_link}} \cdot {}^{\text{camera\_link}}T_{\text{camera\_optical}}$

4.2 매니퓰레이터 탑재 이동 로봇

매니퓰레이터가 탑재된 이동 로봇의 변환 트리는 더 복잡한 구조를 가진다.

map
 └── odom
      └── base_link
           ├── laser_frame
           ├── camera_link
           │    └── camera_optical_frame
           └── arm_base_link
                └── shoulder_link
                     └── upper_arm_link
                          └── forearm_link
                               └── wrist_1_link
                                    └── wrist_2_link
                                         └── wrist_3_link
                                              └── ee_link
                                                   └── tool_frame

이 트리에서 camera_optical_frame에서 tool_frame으로의 변환은 base_link를 LCA로 하여 10개의 개별 변환을 합성해야 한다.

5. 변환 트리의 시간적 특성

변환 트리의 각 엣지에 부여된 변환은 시간의 함수이다. 동적 변환은 시간에 따라 변하며(예: 관절 각도, 오도메트리), 정적 변환은 시간에 무관하게 일정한 값을 유지한다(예: 센서 장착 위치).

BufferCore는 각 동적 변환에 대해 TimeCache를 유지하며, 이 캐시에는 일정 기간 동안의 변환 이력이 시간순으로 저장된다. 변환 조회 시 요청된 시간에 정확히 일치하는 데이터가 없으면, 전후 데이터를 이용하여 보간(interpolation)을 수행한다.

변환 체인의 합성에서, 모든 개별 변환은 동일한 시간에서 평가되어야 한다. 즉, 시간 $t$ 에서의 최종 변환은 다음과 같다.

${}^{f_a}T_{f_b}(t) = {}^{f_a}T_{f_1}(t) \cdot {}^{f_1}T_{f_2}(t) \cdot \cdots \cdot {}^{f_k}T_{f_b}(t)$

6. 변환 트리의 제약 조건 요약

변환 트리가 올바르게 작동하기 위해 다음과 같은 제약 조건이 반드시 충족되어야 한다.

제약 조건	설명
단일 루트	트리는 정확히 하나의 루트 노드를 가져야 한다
비순환성	트리에 순환(cycle)이 존재해서는 안 된다
단일 부모	루트를 제외한 모든 노드는 정확히 하나의 부모를 가진다
연결성	모든 노드는 루트에서 도달 가능해야 한다
유일 명명	각 프레임의 이름은 시스템 전체에서 유일해야 한다

이러한 제약 조건의 위반은 ConnectivityException 또는 LookupException 등의 예외를 발생시키며, 시스템의 올바른 작동을 방해한다.

참고 문헌 및 출처:

Foote, T., “tf: The transform library,” 2013 IEEE Conference on Technologies for Practical Robot Applications (TePRA), pp. 1-6, 2013.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms, 4th ed., MIT Press, 2022.
Open Robotics, “tf2 — ROS 2 Documentation,” ROS 2 Jazzy Jalisco, 2024.
REP 105, “Coordinate Frames for Mobile Platforms,” Open Robotics, 2010.