In this thesis, attempts to recognize 3-D objects from range images are described. Objects are represented by surface patches obtained by segmenting image at depth or orientation discontinuity. Given model objects and a scene object, recognition process is defined as the process to find the best matching pairs between model surface patches (MSP's) and scene surface patches (SSP's). The best matching pairs are usually searched by sequential constrained tree search (SCTS) method. It is known to be effective for recognizing an isolated object, but less effective for object occluded by themselves and other objects. It is because many SSP's are not shown from current model object or seriously deformed by occlusion.
We observed that obtaining partial matching pairs may drastically reduce the number of candidate MSP's matchable to unexplored SSP's. It is because objects we are dealing are all rigid. If the partial matching pair is a part of a real solution path, a few MSP's becomes candidates of unexplored SSP's (As the depth is deeper, the number of candidates becomes one). Otherwise, i.e., if the partial matching pair is not a part of a real solution path, no candidate is available for the SSP's. To utilize these observation, we augment a forward checking mechanism to this SCTS. The forward checking operation checks geometric constraints between current partial matching pairs and unexplored possible pairs and drastically reduces the number of candidates MSP's matchable to unexplored SSP's. Furthermore, the number of unexplored SSP's having at least one candidate MSP's after forward checking yields powerful search termination criteria. As an alternative to the sequential search method, we also applied the optimal search algorithm ($A^*$) using a cost function which consists of the geometrical discrepancy of current matching pairs and that of the remaining one. The latter is approximated by the number of alive unexplored SSP's.
To verify advantages of the forward checking, we evaluated the performance of the matching algorithms using real range images. The experimental results demonstrated significant gains in computation. Comparing with other methods, our approach is particularly advantageous for the difficult problems in that model objects are very much similar to each other. Our method detects part in difference in advance and so reduces time to discriminate the similar objects. It is confirmed by an evaluation.
본 논문에서는 삼차원 물체 (3-D objects) 를 인식하기 위한 모델 기반 시스템을 제안하였다. 물체는 그 표면의 모서리 를 따라 작은 표면 조각 (surface patches)으로 분리된다. 각 물체는 표면 조각과 그들의 관계에 의해서 표현된다. 모델 물체와 입력 물체가 표면 조각들로 표현되었을 때, 삼차원 물체의 인식 문제는 최소의 정합값 (matching value)을 주는 모델 물체를 찾는 문제로 귀착된다. 모델 물체의 표면조각들 (MSP's) 과 입력 물체의 표면 조각들 (SSP's) 과의 정합쌍을 찾기 위해 일반적으로 순차적 (sequential) 제약 트리 탐색 이 사용된다. 이 방법은 단일 물체를 인식하기 위해서는 효율적이지만, 여러 물체가 겹쳐 있는 경우에는 비효율적이다. 왜냐하면 입력 물체의 어떤 표면 조각은 현재 고려 중인 모델의 표면 조작중에서 해당되는 것이 없기 때문이다.
견고한 (rigid) 물체에서는 표면 조각들간에는 다중 관계가 존재하므로 트리 탐색중에 생성된 부분적인 정합쌍을 최대로 활용하면 아직 처리하지 않은 입력 물체의 표면 조각에 해당하는 모델 물체의 표면조각의 수를 줄여 탐색공간을 축소할 수 있다. 현재의 탐색 경로가 실제의 해답 경로의 일부분이라면 탐색 이 깊어질 수록 아직 처리 하지않은 SSP에 해당하는 MSP의 수는 거의 하나 정도만 남겨된다. 반대로 현재의 탐색 경로가 실제의 해답 경로의 일부분이 아니라면 탐색 이 깊어질 수록 아직처리 하지 않은 SSP는 해당하는 MSP를 가지 못한다. 이러한 관찰을 최대로 활용하기 위해 선행 검사기능을 부여한 트리 탐색 기법을 개발하였다. 순차적인 것과 최적 탐색 방법인 $A^*$ 방법을 적용한 순서적인 (ordered) 두 가지 방법으로 구현하였다. 선행 검사는 현재의 탐색점에서 지금까지 생성된 정합쌍과 아직 처리하니 않은 가능한 쌍에 대해서 기하학적인 제약들을 검사하여 가능한 쌍을 미리 줄인다. 이렇게 함으로써 어떤 탐색점에서 탐색을 종료할 것인가를 결정해 주는 기준을 계산할 수 있다.
선행 탐색의 효율성을 증명하기 위해 가상의 이차원 점 패턴의 인식 문제와 실제의 거리 영상 (range image)을 사용한 삼차원 물체의 인식 문제에 대한 실험 결과를 제시하였다. 실험에서 선행 탐색이 매우 효율적이라는 것을 보였다. 특히 모델 물체가 비슷한 경우에 기존의 트리 탐색은 차이나는 부분을 알기 위해 많은 노드들을 생성해야 하지만 선행 탐색을 이용하면 그 차이를 미리 검사하기 때문에 다른 방법에 비해 매우 효율적임을 보였다.
