| 1 |
1
복수의 물체 파편을 스캔하여 각 물체 파편에 대한 3차원 형상 데이터를 생성하는 물체 파편의 형상 데이터 생성 장치;각 물체 파편에 대해 회전축 기반의 형상 특징을 추출하는 형상 특징 추출부를 포함하는 물체 파편의 형상 특징 추출 장치 - 상기 물체 파편의 형상 특징 추출 장치는: 상기 각 물체 파편의 3차원 형상 데이터에서 물체 파편의 외형을 도시하는 포인트 클라우드 데이터를 생성하는 포인트 클라우드 생성부; 상기 각 물체 파편의 회전축을 추정하는 회전축 추정부; 및 각 물체 파편의 포인트 클라우드 데이터를 추정된 회전축을 기준으로 정렬하여 포인트 클라우드 데이터의 좌표를 정의하고, 각 물체 파편에 대해 회전축 기반의 형상 특징을 추출하는 형상 특징 추출부를 포함함; 및 물체 파편을 가상으로 정합하기 위해 사용될, 물체의 복원 그래프를 각 물체 파편의 형상 특징에 기초하여 생성하는 물체 파편의 가상 정합 장치 - 상기 복원 그래프는 물체 파편에 대응한 노드를 포함함 - 를 포함하는 가상 정합 시스템
|
| 2 |
2
제1 항에 있어서, 상기 형상 특징 추출부는 상기 각 물체 파편의 추정된 회전축을 3차원 공간(x, y, z) 의 z축에 일치하도록 상기 포인트 클라우드 데이터를 정렬시키고, 상기 포인트 클라우드 데이터의 상기 3차원 공간내의 좌표를 하기 수학식 1과 같이 정의하며, 상기 포인트 클라우드 데이터의 각 포인트의 높이(H(p)), 거리(D(p)), 각도(T(p))를 하기 수학식 2와 같이 정의하는 것을 특징으로 하는 가상 정합 시스템
|
| 3 |
3
제2 항에 있어서, 상기 형상 특징 추출부는 상기 각 포인트의 높이(H(p)), 거리(D(p)), 각도(T(p))를 이용하여 상기 형상 특징을 하기 수학식 3과 같이 정의하는 것을 특징으로 하는 가상 정합 시스템
|
| 4 |
4
제1 항에 있어서, 상기 물체 파편의 가상 정합 장치는, 상기 회전축 기반의 형상 특징이 유사한 물체 파편을 먼저 선별하여 그룹화하는 것을 특징으로 하는 가상 정합 시스템
|
| 5 |
5
제4 항에 있어서, 상기 물체 파편 가상 정합 장치는 LCS(Longest common substring) 알고리즘을 이용하여 상기 물체 파편의 형상 특징의 비교하여 매칭되는 물체 파편을 선별하여 그룹화하는 것을 특징으로 하는 가상 정합 시스템
|
| 6 |
6
제4항에 있어서, 상기 물체 파편의 가상 정합 장치는, 상기 물체 파편에 대응한 복수의 노드를 갖고, 노드 사이를 연결하는 엣지를 포함한 초기 그래프를 생성하고, 상기 초기 그래프의 엣지는 상기 회전축 기반의 형상 특징이 유사한 물체 파편으로 이루어진 그룹에 포함된 물체 파편의 노드 사이를 연결하여 생성된 것을 특징으로 하는 가상 정합 시스템
|
| 7 |
7
제6항에 있어서, 상기 물체 파편의 가상 정합 장치는, 상기 초기 그래프에서 모든 사이클을 탐색하고 - 상기 사이클은 하나의 노드에서 시작하여 연결된 엣지를 따라 다시 시작한 노드로 돌아오는 경로임, 각 사이클 상의 노드에 대응한 물체 파편을 가상 정합하며, 각 사이클에 대해서, 물체 파편의 정합 결과를 검증하고, 그리고 상기 복원 그래프를 생성하기 위해, 검증을 통과하지 않은 사이클에 포함된 엣지를 상기 초기 그래프에서 가지치기하는 것을 특징으로 하는 가상 정합 시스템
|
| 8 |
8
제6항에 있어서, 상기 물체 파편의 가상 정합 장치는, 상기 초기 그래프 내 노드의 물체 파편에서 베이스 파편(base fragment)을 선택하고, 정합 중인 파편과 추가로 정합될 다음 물체 파편(next fragment)의 노드를 선택하며, 기존 정합 중인 물체 파편의 접합과 다른 물체 파편의 추가 정합을 검증하고, 그리고 상기 복원 그래프를 생성하기 위해, 검증을 통과하지 않은 물체 파편의 노드 사이를 연결한 엣지를 상기 초기 그래프에서 가지치기하는 것을 특징으로 하는 가상 정합 시스템
|
| 9 |
9
제8항에 있어서,상기 베이스 파편은 형상 특징, 면적, 및/또는 형상 특징 측면에서 정합 가능한 물체 파편의 수에 기초하여 선택되는 것을 특징으로 하는 가상 정합 시스템
|
| 10 |
10
제1항에 있어서, 상기 물체 파편 형상 데이터 생성 장치는 3차원 스캐너를 포함하여 상기 복수의 물체 파편을 여러 각도에서 센싱하고, 센싱된 정보를 취합하여 상기 각 물체 파편에 대한 3차원 형상 데이터를 생성하는 것을 특징으로 하는 물체 파편의 가상 정합 시스템
|
| 11 |
11
복수의 물체 파편을 스캔하여 각 물체 파편에 대한 3차원 형상 데이터를 생성하는 단계;상기 각 물체 파편의 3차원 형상 데이터에서 물체 파편의 외형을 도시하는 포인트 클라우드 데이터를 생성하는 단계; 상기 각 물체 파편의 회전축을 추정하는 단계; 각 물체 파편의 포인트 클라우드 데이터를 추정된 회전축을 기준으로 정렬하여 포인트 클라우드 데이터의 좌표를 정의하고, 각 물체 파편에 대해 회전축 기반의 형상 특징을 추출하는 단계; 및물체 파편을 가상으로 정합하기 위해 사용될, 물체의 복원 그래프를 각 물체 파편의 형상 특징에 기초하여 생성하는 단계를 포함하되, 상기 복원 그래프는 물체 파편에 대응한 노드를 포함하는 것을 특징으로 하는 복원 그래프 생성 방법
|
| 12 |
12
제11항에 있어서, 상기 각 물체 파편에 대해 회전축 기반의 형상 특징을 추출하는 단계는, 상기 회전축 기반의 형상 특징이 유사한 물체 파편을 먼저 선별하여 그룹화하는 단계를 포함하는 것을 특징으로 하는 복원 그래프 생성 방법
|
| 13 |
13
제12항에 있어서, 상기 복원 그래프를 생성하는 단계는, 상기 물체 파편에 대응한 복수의 노드를 갖고, 노드 사이를 연결하는 엣지를 포함한 초기 그래프를 생성하는 단계 - 상기 초기 그래프의 엣지는 상기 회전축 기반의 형상 특징이 유사한 물체 파편으로 이루어진 그룹에 포함된 물체 파편의 노드 사이를 연결하여 생성된 것임; 및상기 복원 그래프를 생성하기 위해, 상기 초기 그래프에서 일부 엣지를 가지치기하는 단계를 포함하는 것을 특징으로 하는 복원 그래프 생성 방법
|
| 14 |
14
제13항에 있어서, 상기 초기 그래프에서 일부 엣지를 가지치기하는 단계는, 상기 초기 그래프에서 모든 사이클을 탐색하는 단계 - 상기 사이클은 하나의 노드에서 시작하여 연결된 엣지를 따라 다시 시작한 노드로 돌아오는 경로임; 각 사이클 상의 노드에 대응한 물체 파편을 가상 정합하는 단계; 각 사이클에 대해서, 물체 파편의 정합 결과를 검증하는 단계; 및 상기 복원 그래프를 생성하기 위해, 검증을 통과하지 않은 사이클에 포함된 엣지를 상기 초기 그래프에서 가지치기하는 단계를 포함하는 것을 특징으로 하는 복원 그래프 생성 방법
|
| 15 |
15
제13항에 있어서, 상기 초기 그래프에서 일부 엣지를 가지치기하는 단계는,상기 초기 그래프 내 노드의 물체 파편에서 베이스 파편(base fragment)을 선택하는 단계; 정합 중인 파편과 추가로 정합될 다음 물체 파편(next fragment)의 노드를 선택하는 단계; 기존 정합 중인 물체 파편의 접합과 다른 물체 파편의 추가 정합을 검증하는 단계; 및 상기 복원 그래프를 생성하기 위해, 검증을 통과하지 않은 물체 파편의 노드 사이를 연결한 엣지를 상기 초기 그래프에서 가지치기하는 단계를 포함하는 것을 특징으로 하는 복원 그래프 생성 방법
|
| 16 |
16
제11항 내지 제15항 중 어느 하나의 항에 따른 복원 그래프 생성 방법을 수행하기 위한, 프로그램을 기록한 컴퓨터 판독가능 기록매체
|
| 17 |
17
하드웨어와 결합되어 제11항 내지 제15항 중 어느 하나의 항에 따른 복원 그래프 생성 방법을 실행하도록 매체에 저장된 컴퓨터 프로그램
|
