KR102832441B1

KR102832441B1 - Method and computing device for apparatus for global localization of mobile robots

Info

Publication number: KR102832441B1
Application number: KR1020220105413A
Authority: KR
Inventors: 안수용
Original assignee: 한국전자통신연구원
Priority date: 2021-10-21
Filing date: 2022-08-23
Publication date: 2025-07-11
Anticipated expiration: 2042-08-23
Also published as: KR20230057944A

Abstract

모바일 로봇의 전역 위치인식을 위한 방법이 개시된다. 이 방법은 전역 지도 이미지로부터 분할된 각 쿼리 서브맵 이미지의 기하학적 및 구조적 특징을 정량화한 히스토그램 값과 데이터베이스에 저장된 서브맵 이미지들의 기하학적 및 구조적 특징을 정량화한 히스토그램 값을 비교하여 쿼리 서브맵 이미지와 가장 유사한 서브맵 이미지를 선정하고, 선정된 서브맵 이미지에 포함된 좌표 정보를 기반으로 모바일 로봇의 전역 위치인식을 수행함을 특징으로 한다.A method for global localization of a mobile robot is disclosed. The method is characterized by selecting a submap image most similar to a query submap image by comparing a histogram value quantifying geometrical and structural features of each query submap image segmented from a global map image with a histogram value quantifying geometrical and structural features of submap images stored in a database, and performing global localization of the mobile robot based on coordinate information included in the selected submap image.

Description

METHOD AND COMPUTING DEVICE FOR APPARATUS FOR GLOBAL LOCALIZATION OF MOBILE ROBOTS

본 발명은 모바일 로봇(mobile robots)의 전역 위치 인식(global localization) 기술에 관한 것이다.The present invention relates to a global localization technology for mobile robots.

모바일 로봇은 공간 안에서 자율적으로 이동하며, 안내(guidance), 배송(delivery), 감시(surveillance), 청소(cleaning) 등과 같은 높은 수준의 작업(high-level tasks)을 요하는 일을 처리하는 능력을 가진 로봇이다.Mobile robots are robots that can move autonomously within a space and perform high-level tasks such as guidance, delivery, surveillance, and cleaning.

모바일 로봇의 높은 레벨의 작업을 위해, 신뢰성 있는 자기 측위(self-positioning) 기술이 필수적이며, 이를 로봇공학(robotics) 분야에서는 '위치 인식(localization)'이라 한다.For high-level tasks of mobile robots, reliable self-positioning technology is essential, which is called 'localization' in the field of robotics.

위치인식(localization)은 크게 지역 위치인식(local localization)과 전역 위치인식(global localization)으로 나눌 수 있으며, 이중 전역 위치인식(global localization)은 지역 위치인식(local localization)과는 다르게 초기 위치에 대한 사전 지식 없이 로봇의 현재 위치를 찾을 수 있는 기술이다.Localization can be broadly divided into local localization and global localization. Unlike local localization, global localization is a technology that can find the current location of a robot without prior knowledge of the initial location.

전역 위치인식(global localization)은 맵 작성(map building)시에 사용된 센서 종류에 따라 여러 방법들이 있으며, 그 중 실내 주행 로봇을 위한 전역 위치인식(global localization)으로서 2차원 점유 격자 지도(2D occupancy grid map)를 이용하는 방법이 있다.There are several methods for global localization depending on the type of sensor used in map building. One of them is a method that uses a 2D occupancy grid map as global localization for indoor driving robots.

이 방법은 로봇에 탑재된 레이저 스캐너(Laser scanner)에 의해 획득된 누적된 2D 레이저 스캔 데이터를 2D 점유 격자 지도로 변환하고, 이 이미지에서 특징점을 추출하는 방법이다. 특징점 추출로 객체 인식(object recognition) 분야에서 널리 사용되는 SIFT(Scale Invariant Feature Transform) 알고리즘과 SURF(Speeded Up Robust Feature) 알고리즘이 활용될 수 있다.This method converts accumulated 2D laser scan data acquired by a laser scanner mounted on a robot into a 2D occupancy grid map and extracts feature points from this image. The SIFT (Scale Invariant Feature Transform) algorithm and SURF (Speeded Up Robust Feature) algorithm, which are widely used in the field of object recognition, can be utilized for feature point extraction.

이러한 접근 방법은 컴퓨터 비전에서 제안된 많은 알고리즘을 재사용할 수 있는 장점이 있지만 2D 점유 격자 지도를 생성하는 과정에서 센서 노이즈나 지도 작성 오류 등으로 인해 2D 점유 격자 지도와 실제 공간의 불일치가 발생할 수 있다.Although this approach has the advantage of being able to reuse many algorithms proposed in computer vision, there may be mismatches between the 2D occupancy grid map and the actual space due to sensor noise or map creation errors during the process of generating the 2D occupancy grid map.

상술한 문제점을 해결하기 위한 본 발명의 목적은, 모바일 로봇의 전역 위치 인식의 효율을 높이기 위해 2D 점유 격자 지도로부터 추출된 기하학적 특징 정보 및 구조적 특징 정보를 이용하여 모바일 로봇의 전역 위치인식(global localization)을 위한 방법 및 장치를 제공하는 데 있다.The purpose of the present invention to solve the above-described problems is to provide a method and device for global localization of a mobile robot by using geometric feature information and structural feature information extracted from a 2D occupancy grid map to increase the efficiency of global localization of the mobile robot.

상술한 목적을 달성하기 위한 본 발명의 일면에 따른 모바일 로봇의 전역 위치인식을 위한 방법은, 모바일 로봇 내에 탑재된 컴퓨팅 장치의 프로세서에 의해 수행되는 전역 위치인식을 위한 방법으로서, 전역 지도 이미지를 복수의 쿼리 서브맵 이미지들로 분할하는 단계; 각 쿼리 서브맵 이미지의 기하학적 특징을 나타내는 히스토그램 값을 계산하는 단계; 각 쿼리 서브맵 이미지의 구조적 특징 정보를 나타내는 반사 대칭 스코어를 계산하는 단계; 상기 히스토그램 값과 상기 반사 대칭 스코어를 기반으로 각 쿼리 서브맵 이미지와 데이터베이스에 저장된 서브맵 이미지들 사이의 서브맵 유사도를 계산하는 단계; 및 상기 서브맵 유사도를 기반으로 상기 쿼리 서브맵 이미지와 가장 유사한 서브맵 이미지를 선정하여, 상기 선정된 서브맵 이미지에 포함된 좌표 정보를 기반으로 상기 모바일 로봇의 전역 위치인식을 수행하는 단계를 포함할 수 있다.According to one aspect of the present invention for achieving the above-described object, a method for global localization of a mobile robot is provided, which is a method for global localization performed by a processor of a computing device mounted in a mobile robot, comprising: a step of dividing a global map image into a plurality of query sub-map images; a step of calculating a histogram value representing a geometric feature of each query sub-map image; a step of calculating a reflection symmetry score representing structural feature information of each query sub-map image; a step of calculating a sub-map similarity between each query sub-map image and sub-map images stored in a database based on the histogram value and the reflection symmetry score; and a step of selecting a sub-map image most similar to the query sub-map image based on the sub-map similarity and performing global localization of the mobile robot based on coordinate information included in the selected sub-map image.

실시 예에서, 상기 전역 지도 이미지를 복수의 쿼리 서브맵 이미지들로 분할하는 단계는, 상기 모바일 로봇에 탑재된 센서를 이용하여 상기 전역 지도 이미지를 생성하는 단계; 상기 전역 지도 이미지 상에서 상기 모바일 로봇의 이동 경로가 분기되는 포인트를 정의하는 정션 포인트(junction point)를 추출하는 단계; 및 상기 전역 지도 이미지를 상기 정션 포인트를 중심으로 일정한 반경을 갖는 상기 복수의 쿼리 서브맵 이미지들로 분할하는 단계를 포함할 수 있다.In an embodiment, the step of dividing the global map image into a plurality of query sub-map images may include the steps of: generating the global map image using a sensor mounted on the mobile robot; extracting a junction point defining a point at which a movement path of the mobile robot branches on the global map image; and dividing the global map image into the plurality of query sub-map images having a constant radius centered on the junction point.

실시 예에서, 상기 정션 포인트를 추출하는 단계는, 이미지 처리 기법을 기반으로 상기 전역 지도 이미지를 에지 지도 이미지(edge map image)로 변환하는 단계; 및 상기 에지 지도 이미지 내에서 중심 픽셀과 상기 중심 픽셀을 둘러싸는 In an embodiment, the step of extracting the junction point comprises: a step of converting the global map image into an edge map image based on an image processing technique; and a step of extracting a center pixel and an edge map image surrounding the center pixel within the edge map image.

의 주변 픽셀들로 이루어진 n×n 이미지 패치를 가정할 때, 상기 중심 픽셀의 픽셀값이 적어도 3개의 주변 픽셀들의 픽셀값과 다른 경우, 상기 중심 픽셀을 상기 정션 포인트로서 추출하는 단계를 포함할 수 있다.Assuming an n×n image patch consisting of peripheral pixels, the method may include a step of extracting the central pixel as the junction point if the pixel value of the central pixel is different from the pixel values of at least three peripheral pixels.

실시 예에서, 각 쿼리 서브맵 이미지의 기하학적 특징을 나타내는 히스토그램 값을 계산하는 단계는, 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 없는 경계 영역의 기하학적 특징을 나타내는 경계 히스토그램 값을 계산하는 단계; 및 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 있는 자유 공간 영역의 기하학적 특징을 나타내는 자유 공간 히스토그램 값을 계산하는 단계를 포함할 수 있다.In an embodiment, the step of calculating histogram values representing geometric features of each query sub-map image may include the step of calculating boundary histogram values representing geometric features of a boundary area in which the mobile robot cannot move in each query sub-map image; and the step of calculating free space histogram values representing geometric features of a free space area in which the mobile robot can move in each query sub-map image.

실시 예에서, 상기 경계 히스토그램 값을 계산하는 단계는, 이미지 처리 기법을 기반으로 각 쿼리 서브맵 이미지를 에지 지도 이미지로 변환하는 단계; 상기 에지 지도 이미지 내에서 상기 경계 영역을 형성하는 경계 포인트들을 샘플링 하는 단계; 상기 샘플링된 경계 포인트들을 쌍으로 구성하여 복수의 경계 포인트 쌍들을 생성하는 단계; 및 각 경계 포인트 쌍에 포함된 2개의 경계 포인트들 사이의 거리값을 기반으로 상기 경계 히스토그램 값을 계산하는 단계를 포함할 수 있다.In an embodiment, the step of calculating the boundary histogram value may include the steps of: converting each query sub-map image into an edge map image based on an image processing technique; sampling boundary points forming the boundary area within the edge map image; configuring the sampled boundary points into pairs to generate a plurality of boundary point pairs; and calculating the boundary histogram value based on a distance value between two boundary points included in each boundary point pair.

실시 예에서, 상기 자유 공간 히스토그램 값을 계산하는 단계는, 이미지 처리 기법을 기반으로 각 쿼리 서브맵 이미지를 에지 지도 이미지로 변환하는 단계와 상기 에지 지도 이미지 내에서 상기 자유 공간 영역을 형성하는 자유 공간 포인트들을 추출하는 단계; 상기 추출된 자유 공간 포인트들 중에서 최단 경로 거리(shortest path distance) 값을 갖는 2개의 자유 공간 포인트들을 쌍으로 구성하여 복수의 자유 공간 포인트 쌍들을 생성하는 단계; 및 각 자유 공간 포인트 쌍의 상기 최단 경로 거리 값을 기반으로 상기 자유 공간 히스토그램 값을 계산하는 단계를 포함할 수 있다.In an embodiment, the step of calculating the free-space histogram value may include the steps of: converting each query sub-map image into an edge map image based on an image processing technique; extracting free-space points forming the free-space area within the edge map image; generating a plurality of free-space point pairs by pairing two free-space points having a shortest path distance value among the extracted free-space points; and calculating the free-space histogram value based on the shortest path distance value of each free-space point pair.

실시 예에서, 상기 반사 대칭 스코어를 계산하는 단계는, 이미지 처리 기법을 기반으로 각 쿼리 서브맵 이미지를 에지 지도 이미지로 변환하는 단계; 상기 에지 지도 이미지에서 일정 길이를 갖는 선분들의 각도를 기반으로 반사 대칭축을 검출하는 단계; 이미지 블러드(image blurred) 기법을 기반으로 상기 에지 지도 이미지를 블러드 이미지로 변환하는 단계; 및 상기 블러드 이미지와 상기 검출된 반사 대칭축을 기준으로 반전(filp)된 블러드 이미지 사이의 유사도를 상기 반사 대칭 스코어로서 계산하는 단계를 포함할 수 있다.In an embodiment, the step of calculating the reflection symmetry score may include: a step of converting each query submap image into an edge map image based on an image processing technique; a step of detecting a reflection symmetry axis based on an angle of line segments having a predetermined length in the edge map image; a step of converting the edge map image into a blurred image based on an image blurred technique; and a step of calculating a similarity between the blurred image and a blurred image inverted (filtered) based on the detected reflection symmetry axis as the reflection symmetry score.

실시 예에서, 상기 반사 대칭축을 검출하는 단계와 상기 에지 지도 이미지를 블러드 이미지로 변환하는 단계 사이에 상기 검출된 반사 대칭축이 수직하게 정렬되도록 상기 에지 지도 이미지를 회전시키는 단계를 더 포함할 수 있다.In an embodiment, the method may further include a step of rotating the edge map image so that the detected reflection symmetry axis is vertically aligned between the step of detecting the reflection symmetry axis and the step of converting the edge map image into a blur image.

실시 예에서, 상기 서브맵 유사도를 계산하는 단계는, 각 쿼리 서브맵 이미지의 상기 히스토그램 값과 상기 데이터베이스에 저장된 서브맵 이미지들의 상기 기하학적 특징을 나타내는 히스토그램 값들 사이의 제1 차이값을 계산하는 단계; 각 쿼리 서브맵 이미지의 상기 반사 대칭 스코어와 상기 데이터베이스에 저장된 서브맵 이미지들의 구조적 특징을 나타내는 반사 대칭 스코어들 사이의 제2 차이값을 계산하는 단계; 및 상기 제1 및 제2 차이값을 기반으로 상기 서브맵 유사도를 계산하는 단계를 포함할 수 있다.In an embodiment, the step of calculating the submap similarity may include: calculating a first difference value between the histogram value of each query submap image and histogram values representing the geometric features of the submap images stored in the database; calculating a second difference value between the reflection symmetry score of each query submap image and reflection symmetry scores representing the structural features of the submap images stored in the database; and calculating the submap similarity based on the first and second difference values.

실시 예에서, 상기 제1 차이값을 계산하는 단계는, 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 없는 경계 영역의 상기 기하학적 특징을 나타내는 경계 히스토그램 값과 상기 서브맵 이미지들에서 상기 모바일 로봇이 이동할 수 없는 경계 영역의 상기 기하학적 특징을 나타내는 경계 히스토그램 값들 사이의 차이값을 계산하는 단계; 및 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 있는 자유 공간 영역의 상기 기하학적 특징을 나타내는 자유 공간 히스토그램 값과 상기 모바일 로봇이 이동할 수 있는 자유 공간 영역의 상기 기하학적 특징을 나타내는 자유 공간 히스토그램 값들 사이의 차이값을 계산하는 단계를 포함할 수 있다.In an embodiment, the step of calculating the first difference value may include: calculating a difference value between a boundary histogram value representing the geometric feature of a boundary area in which the mobile robot cannot move in each query sub-map image and boundary histogram values representing the geometric feature of a boundary area in which the mobile robot cannot move in each of the sub-map images; and calculating a difference value between a free-space histogram value representing the geometric feature of a free-space area in which the mobile robot can move in each query sub-map image and free-space histogram values representing the geometric feature of a free-space area in which the mobile robot can move.

본 발명의 다른 일면에 따른 모바일 로봇의 전역 위치인식을 위한 컴퓨팅 장치는, 점유 격자 지도 이미지를 복수의 쿼리 서브맵 이미지들로 분할하는 이미지 분할기; 각 쿼리 서브맵 이미지의 기하학적 특징을 나타내는 히스토그램 값을 계산하고, 각 쿼리 서브맵 이미지의 대칭 특징을 나타내는 반사 대칭 스코어를 계산하는 특징 추출기; 상기 히스토그램 값과 상기 반사 대칭 스코어를 기반으로 각 쿼리 서브맵 이미지와 데이터베이스에 저장된 서브맵 이미지들 사이의 유사도를 계산하는 서브맵 유사도 계산기; 및 상기 서브맵 유사도를 기반으로 상기 쿼리 서브맵 이미지와 가장 유사한 서브맵 이미지를 선정하여, 상기 선정된 서브맵 이미지에 포함된 좌표 정보를 기반으로 상기 로봇의 전역 위치인식을 수행하는 전역 위치인식 처리기를 포함할 수 있다.According to another aspect of the present invention, a computing device for global localization of a mobile robot may include an image segmenter for segmenting an occupied grid map image into a plurality of query sub-map images; a feature extractor for calculating a histogram value representing a geometric feature of each query sub-map image and a reflection symmetry score representing a symmetric feature of each query sub-map image; a sub-map similarity calculator for calculating a similarity between each query sub-map image and sub-map images stored in a database based on the histogram value and the reflection symmetry score; and a global localization processor for selecting a sub-map image most similar to the query sub-map image based on the sub-map similarity and performing global localization of the robot based on coordinate information included in the selected sub-map image.

실시 예에서, 상기 이미지 분할기는, 상기 점유 격자 지도 이미지 상에서 상기 모바일 로봇의 이동 경로가 분기되는 정션 포인트를 기준으로 상기 점유 격자 지도 이미지를 복수의 쿼리 서브맵 이미지들로 분할할 수 있다.In an embodiment, the image segmenter may segment the occupied grid map image into a plurality of query sub-map images based on junction points at which the movement path of the mobile robot branches on the occupied grid map image.

실시 예에서, 상기 특징 추출기는, 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 없는 경계 영역의 분포 특징을 정량화한 경계 히스토그램 값을 계산하는 제1 기하학적 특징 추출기; 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 있는 자유 공간 영역의 분포 특징을 정량화한 자유 공간 히스토그램 값을 계산하는 제2 기하학적 특징 추출기; 및 각 쿼리 서브맵 이미지의 대칭성을 정량화한 반사 대칭 스코어를 계산하는 구조적 특징 추출기를 포함할 수 있다.In an embodiment, the feature extractor may include a first geometric feature extractor that calculates a boundary histogram value that quantifies a distribution feature of a boundary area in which the mobile robot cannot move in each query sub-map image; a second geometric feature extractor that calculates a free space histogram value that quantifies a distribution feature of a free space area in which the mobile robot can move in each query sub-map image; and a structural feature extractor that calculates a reflection symmetry score that quantifies a symmetry of each query sub-map image.

실시 예에서, 상기 서브맵 유사도 계산기는, 각 쿼리 서브맵 이미지에서 경계 영역의 기하학적 특징을 정량화한 경계 히스토그램 값과 상기 데이터베이스에 저장된 서브맵 이미지에서 경계 영역의 기하학적 특징을 정량화한 경계 히스토그램 값의 차이값을 계산하는 제1 감산기; 각 쿼리 서브맵 이미지에서 자유 공간 영역의 기하학적 특징을 정량화한 자유공간 히스토그램 값과 상기 데이터베이스에 저장된 서브맵 이미지의 자유 공간 영역의 기하학적 특징을 정량화한 경계 히스토그램 값의 차이값을 계산하는 제2 감산기: 및 각 쿼리 서브맵 이미지의 대칭성을 정량화한 상기 반사 대칭 스코어와 상기 데이터베이스에 저장된 서브맵 이미지의 대칭성을 정량화한 반사 대칭 스코어의 차이값을 계산하는 제3 감산기를 포함할 수 있다.In an embodiment, the submap similarity calculator may include: a first subtractor that calculates a difference between a boundary histogram value that quantifies a geometric feature of a boundary region in each query submap image and a boundary histogram value that quantifies a geometric feature of a boundary region in submap images stored in the database; a second subtractor that calculates a difference between a free-space histogram value that quantifies a geometric feature of a free-space region in each query submap image and a boundary histogram value that quantifies a geometric feature of a free-space region in submap images stored in the database; and a third subtractor that calculates a difference between the reflection symmetry score that quantifies a symmetry of each query submap image and the reflection symmetry score that quantifies a symmetry of the submap images stored in the database.

실시 예에서, 상기 서브맵 유사도 계산기는, 상기 제1 내지 제3 감산기에 의해 계산된 차이값들을 연산하여 각 쿼리 서브맵 이미지와 상기 서브맵 이미지들 사이의 유사도를 계산할 수 있다.In an embodiment, the submap similarity calculator can calculate the similarity between each query submap image and the submap images by calculating the difference values calculated by the first to third subtractors.

실시 예에서, 상기 서브맵 유사도 계산기는, 상기 제1 감산기에 의해 계산된 차이값과 상기 제2 감산기에 의해 계산된 차이값을 합산하는 가산기를 더 포함하고, 상기 제3 감산기에 의해 계산된 차이값을 가중치로서 상기 가산기에 의해 합산된 값과 연산하여 각 쿼리 서브맵 이미지와 상기 서브맵 이미지들 사이의 유사도를 계산할 수 있다.In an embodiment, the submap similarity calculator further includes an adder that adds the difference value calculated by the first subtracter and the difference value calculated by the second subtracter, and calculates the similarity between each query submap image and the submap images by calculating the difference value calculated by the third subtracter and the value added by the adder as a weight.

본 발명의 또 다른 일면에 따른 모바일 로봇 내에 탑재된 컴퓨팅 장치의 프로세서에 의해 수행되는 전역 위치인식을 위한 방법은, 전역 지도 이미지로부터 분할된 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 없는 경계 영역의 분포 특징을 정량화한 경계 히스토그램 값을 계산하는 단계; 각 쿼리 서브맵 이미지에서 상기 모바일 로봇이 이동할 수 있는 자유 공간 영역의 분포 특징을 정량화한 자유 공간 히스토그램 값을 계산하는 단계; 각 쿼리 서브맵 이미지에서 추출된 대칭축을 기준으로 각 쿼리 서브맵 이미지의 대칭성을 정량화한 반사 대칭 스코어를 계산하는 단계; 각 쿼리 서브맵 이미지의 상기 경계 히스토그램 값, 상기 자유 공간 히스토그램 값 및 상기 반사 대칭 스코어와 데이터베이스로부터 입력된 서브맵 이미지들의 경계 히스토그램 값, 자유 공간 히스토그램 값 및 반사 대칭 스코어를 비교하여 상기 데이터베이스에 저장된 서브맵 이미지들 중에서 각 쿼리 서브맵 이미지와 가장 유사한 서브맵 이미지를 선정하는 단계; 및 상기 선정된 서브맵 이미지에 포함된 좌표 정보를 기반으로 상기 모바일 로봇의 전역 위치인식을 수행하는 단계를 포함할 수 있다.According to another aspect of the present invention, a method for global localization performed by a processor of a computing device mounted in a mobile robot may include: calculating a boundary histogram value quantifying a distribution characteristic of a boundary area in which the mobile robot cannot move in each query sub-map image segmented from a global map image; calculating a free space histogram value quantifying a distribution characteristic of a free space area in which the mobile robot can move in each query sub-map image; calculating a reflection symmetry score quantifying a symmetry of each query sub-map image based on a symmetry axis extracted from each query sub-map image; comparing the boundary histogram value, the free space histogram value, and the reflection symmetry score of each query sub-map image with the boundary histogram value, the free space histogram value, and the reflection symmetry score of sub-map images input from a database to select a sub-map image most similar to each query sub-map image among sub-map images stored in the database; and performing global localization of the mobile robot based on coordinate information included in the selected sub-map image.

실시 예에서, 상기 전역 지도 이미지는 2D 또는 3D 점유 격자 지도 이미지일 수 있다.In an embodiment, the global map image may be a 2D or 3D occupancy grid map image.

본 발명은 서브맵(submap)으로부터 추출된 기하학적 특징 정보 및 구조적 특징 정보(대칭성)를 기반으로 모바일 로봇의 전역 위치 인식(global localization) 방법을 제안한다. The present invention proposes a method for global localization of a mobile robot based on geometric feature information and structural feature information (symmetry) extracted from a submap.

이에 따라, 본 발명은 서브맵의 구조적 정보(structural information), 즉, 대칭 스코어(symmetry score)를 도입함에 따라, 실내 공간(indoor space)의 구조적 특징 정보(structural feature information)를 수치화(정량화)하여 서브맵(submap)의 매칭(matching) 성능을 향상시킬 수 있다.Accordingly, the present invention can improve the matching performance of a submap by quantifying structural feature information of an indoor space by introducing structural information of the submap, i.e., a symmetry score.

또한, 본 발명은 서브맵의 기하학적 특징 정보(geometric feature information)와 구조적 특징 정보(structural feature information)의 명시적 통합을 제공함에 따라 서브맵에 인가되는 노이즈에 대한 강건성을 확보할 수 있다.In addition, the present invention can secure robustness against noise applied to a submap by providing explicit integration of geometric feature information and structural feature information of a submap.

또한, 본 발명은 2D 점유 격자 지도(2D occupancy grid map)를 생성할 수 있는 모든 센서들(예: ultrasonic sensor, 2D/3D LiDAR, 3D depth camera)에 적용될 수 있다.Additionally, the present invention can be applied to all sensors capable of generating a 2D occupancy grid map (e.g., ultrasonic sensor, 2D/3D LiDAR, 3D depth camera).

또한, 본 발명은 실내 건물의 2차원 평면(2D floor plan) 지도에도 적용할 수 있기 때문에, 로봇을 통해 지도를 사전에 구축할 필요가 없다.In addition, since the present invention can be applied to a two-dimensional (2D) floor plan map of an indoor building, there is no need to construct a map in advance using a robot.

도 1은 본 발명의 실시 예에 따른 모바일 로봇의 전역 위치인식을 위한 방법을 설명하기 위한 흐름도이다.
도 2는 본 발명의 실시 예에 따른 전역 지도로 활용되는 2D 점유 격자 지도의 예를 보여주는 도면이다.
도 3은 본 발명의 실시 예에 따른 전역 지도로 활용되는 2D 점유 격자 지도를 복수의 서브맵들로 분할하는 과정을 상세히 설명하기 위한 흐름도이다.
도 4는 도 3의 S120에 의해 생성된 에지 지도 이미지를 보여주는 도면이다.
도 5는 도 4에 도시된 에지 지도 이미지 상에 도 3의 S130에 의해 추출된 후보 정션 포인트들과 S140에 의해 추출된 정션 포인트들을 함께 나타낸 도면이다.
도 6은 도 3의 S150에 의해 도 2의 2D 점유 격자 지도로부터 분할된 복수의 서브맵들의 예시도이다.
도 7은 본 발명의 실시 예에 따른 경계 영역의 기하학적 특징 정보에 대한 통계치 계산 과정을 상세히 설명하기 위한 흐름도이다.
도 8은 본 발명의 실시 예에 따른 경계 영역을 경계 포인트들로 나타낸 4개의 서브맵들의 예시도이다.
도 9는 도 8에 도시된 4개의 서브맵들의 경계 히스토그램을 나타내는 그래프이다.
도 10은 본 발명의 실시 예에 따른 자유 공간 영역의 기하학적 특징 정보에 대한 통계치 계산 과정을 상세히 설명하기 위한 흐름도이다.
도 11은 본 발명의 실시 예에 따른 자유 공간 영역을 자유 공간 포인트들로 나타낸 4개의 서브맵들의 예시도이다.
도 12는 도 11에 도시된 4개의 서브맵들의 자유 공간 히스토그램을 나타내는 그래프이다.
도 13은 본 발명의 실시 예에 따른 서로 다른 노이즈 레벨을 갖는 4개의 서브맵들의 예시도이다.
도 14는 도 13에 도시된 4개의 서브맵들의 자유 공간 히스토그램을 나타내는 그래프이다.
도 15는 본 발명의 실시 예에 따른 반사 대칭 스코어의 계산 과정을 상세히 설명하기 위한 흐름도이다.
도 16은 도 15의 각 단계에서 생성된 이미지의 예시도이다.
도 17은 본 발명의 실시 예에 따른 모바일 로봇의 전역 위치인식을 위한 기능 블록도이다.
도 18은 본 발명의 실시 예에 따른 전역 위치인식을 수행하기 위한 컴퓨팅 장치를 나타내는 블록도이다.FIG. 1 is a flowchart illustrating a method for global position recognition of a mobile robot according to an embodiment of the present invention.
FIG. 2 is a drawing showing an example of a 2D occupancy grid map utilized as a global map according to an embodiment of the present invention.
FIG. 3 is a flowchart for explaining in detail the process of dividing a 2D occupancy grid map utilized as a global map into multiple submaps according to an embodiment of the present invention.
FIG. 4 is a drawing showing an edge map image generated by S120 of FIG. 3.
FIG. 5 is a drawing showing candidate junction points extracted by S130 of FIG. 3 and junction points extracted by S140 together on the edge map image illustrated in FIG. 4.
FIG. 6 is an example diagram of multiple submaps segmented from the 2D occupancy grid map of FIG. 2 by S150 of FIG. 3.
FIG. 7 is a flowchart for explaining in detail a statistical calculation process for geometric feature information of a boundary area according to an embodiment of the present invention.
FIG. 8 is an example diagram of four submaps representing boundary areas with boundary points according to an embodiment of the present invention.
Figure 9 is a graph showing the boundary histograms of the four submaps shown in Figure 8.
FIG. 10 is a flowchart for explaining in detail a statistical calculation process for geometric feature information of a free space region according to an embodiment of the present invention.
FIG. 11 is an example diagram of four submaps representing a free space area as free space points according to an embodiment of the present invention.
Figure 12 is a graph showing the free space histograms of the four submaps shown in Figure 11.
FIG. 13 is an example diagram of four submaps having different noise levels according to an embodiment of the present invention.
Figure 14 is a graph showing the free space histograms of the four submaps shown in Figure 13.
FIG. 15 is a flowchart for explaining in detail the calculation process of a reflection symmetry score according to an embodiment of the present invention.
Figure 16 is an example of images generated at each step of Figure 15.
FIG. 17 is a functional block diagram for global position recognition of a mobile robot according to an embodiment of the present invention.
FIG. 18 is a block diagram illustrating a computing device for performing global position recognition according to an embodiment of the present invention.

본 발명에서는 전역 지도(global map)로부터 분할된 서브맵(submap)을 이용하여 모바일 로봇의 전역 위치인식 방법을 제안한다. 여기서, 전역 지도는 "2D 점유 격자 지도"일 수 있다. 본 문서에서 전역 지도는 '전역 지도 이미지'와 동일한 용어로 간주하고, 서브맵은 '서브맵 이미지'또는 '입력 서브맵 이미지'와 동일한 용어로 간주한다. 그리고 2D 점유 격자 지도 역시 '2D 점유 격자 지도 이미지'와 동일한 용어로 간주한다.In the present invention, a method for global localization of a mobile robot is proposed by using a submap segmented from a global map. Here, the global map may be a "2D occupancy grid map." In this document, the global map is considered to be the same term as a "global map image", and the submap is considered to be the same term as a "submap image" or an "input submap image". In addition, the 2D occupancy grid map is also considered to be the same term as a "2D occupancy grid map image".

본 발명에 따른 모바일 로봇의 전역 위치인식 방법은 이미지 내 특징점을 추출하는 방법과는 달리 서브맵(submap) 내에서 점유 및 비점유(occupied and unoccupied) 영역의 분포 특징(distribution features)을 나타내는 통계치(statistic)를 추출하는 과정을 포함한다. 여기서, 상기 추출된 통계치는 전역 기술자(global descriptor)로 정의된다.Unlike a method of extracting feature points within an image, a method for global localization of a mobile robot according to the present invention includes a process of extracting statistics representing distribution features of occupied and unoccupied areas within a submap. Here, the extracted statistics are defined as a global descriptor.

예를 들어, 본 발명은 서브맵(submap)을 경계(boundary) 영역(또는 상기 점유 영역)과 자유 공간(free space) 영역(또는 상기 비점유 영역)으로 나누고 각 영역의 분포 특징(distribution features)을 나타내는 히스토그램 형태의 데이터(이하, 히스토그램 데이터 또는 히스토그램 값)를 전역 기술자(global descriptor)로 생성한다. For example, the present invention divides a submap into a boundary area (or the occupied area) and a free space area (or the unoccupied area) and generates data in the form of a histogram (hereinafter, histogram data or histogram value) representing distribution features of each area as a global descriptor.

경계 영역의 분포 특징(distribution features)을 나타내는 전역 기술자와 자유 공간 영역의 분포 특징을 나타내는 전역 기술자는 서브맵의 "기하학적 특징 정보(geometric feature information)"로 활용할 수 있다.The global descriptor representing the distribution features of the boundary region and the global descriptor representing the distribution features of the free space region can be utilized as the “geometric feature information” of the submap.

또한 본 발명에 따른 모바일 로봇의 전역 위치인식 방법은 서브맵의 "구조적 특징(structural feature) 또는 대칭 특징(symmetrical feature)"을 수치화하기 위해 서브맵의 구조적 특징 정보를 나타내는 반사 대칭 스코어(reflection symmetry score)를 계산하는 과정을 포함한다. 여기서, 반사 대칭 스코어(reflection symmetry score)는 서브맵과 쿼리 서브맵 사이의 유사도(similarity score) 계산 시에 가중치(weighting factor)로 활용될 수 있다.In addition, the global localization method of a mobile robot according to the present invention includes a process of calculating a reflection symmetry score representing structural feature information of a submap to quantify the "structural feature or symmetrical feature" of the submap. Here, the reflection symmetry score can be utilized as a weighting factor when calculating a similarity score between a submap and a query submap.

이러한 본 발명에 따른 모바일 로봇의 전역 위치인식 방법은 서브맵(submap)의 구조적 특징 정보(structural feature information), 즉, 대칭 스코어(symmetry score)를 도입함에 따라, 실내 공간의 구조적 특징 정보를 수치화하여 서브맵(submap)의 매칭(matching) 성능을 향상시킬 수 있다. The global localization method of a mobile robot according to the present invention can improve the matching performance of a submap by digitizing the structural feature information of an indoor space by introducing structural feature information of a submap, that is, a symmetry score.

또한, 본 발명은 서브맵의 기하학적 특징 정보(geometric feature information)와 구조적 특징 정보(structural feature information)의 명시적 통합을 제공함에 따라 서브맵(submap)에 인가되는 노이즈에 대한 강건성을 확보할 수 있다. In addition, the present invention can secure robustness against noise applied to a submap by providing explicit integration of geometric feature information and structural feature information of a submap.

또한 본 발명은 2D 점유 격자 지도(2D occupancy grid map)를 생성할 수 있는 모든 센서들(예: ultrasonic sensor, 2D/3D LiDAR, 3D depth camera)에 적용될 수 있다.Additionally, the present invention can be applied to all sensors capable of generating a 2D occupancy grid map (e.g., ultrasonic sensor, 2D/3D LiDAR, 3D depth camera).

이하, 첨부한 도면들을 참조하여, 본 발명의 바람직한 실시예를 보다 상세하게 설명하고자 한다. 본 발명을 설명함에 있어 전체적인 이해를 용이하게 하기 위하여 도면상의 동일한 구성요소에 대해서는 동일한 참조부호를 사용하고 동일한 구성요소에 대해서 중복된 설명은 생략한다.Hereinafter, with reference to the attached drawings, a preferred embodiment of the present invention will be described in more detail. In order to facilitate an overall understanding in describing the present invention, the same reference numerals are used for the same components in the drawings, and redundant descriptions of the same components are omitted.

본 문서에서 사용하는 용어들은 단지 특정한 실시예를 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 출원에서, "포함하다" 또는 "가지다" 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.The terms used in this document are only used to describe specific embodiments and are not intended to limit the present invention. The singular expression includes the plural expression unless the context clearly indicates otherwise. In this application, it should be understood that the terms "comprise" or "have" and the like are intended to specify the presence of a feature, number, step, operation, component, part or combination thereof described in the specification, but do not exclude in advance the possibility of the presence or addition of one or more other features, numbers, steps, operations, components, parts or combinations thereof.

다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가지고 있다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥 상 가지는 의미와 일치하는 의미를 가진 것으로 해석되어야 하며, 본 출원에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Terms defined in commonly used dictionaries, such as those defined in common dictionaries, should be interpreted as having a meaning consistent with the meaning they have in the context of the relevant art, and will not be interpreted in an idealized or overly formal sense unless expressly defined in this application.

도 1은 본 발명의 실시 예에 따른 모바일 로봇의 전역 위치인식을 위한 방법을 설명하기 위한 흐름도이다.FIG. 1 is a flowchart illustrating a method for global position recognition of a mobile robot according to an embodiment of the present invention.

이하에서 설명하는 단계들(S100~S700)의 수행 주체는 모바일 로봇(또는 이동 로봇) 내에 탑재되거나 모바일 로봇의 외부에 배치된 컴퓨팅 장치일 일 수 있다. 상기 컴퓨팅 장치는 데이터 및 이미지 처리를 위한 연산을 수행하는 프로세서, 데이터 및 이미지 처리에 필요한 프로그램 명령어를 일시적으로 일시적으로 저장하거나, 상기 프로세서에 의해 처리된 중간 데이터 및 결과 데이터를 일시적으로 저장하거나, 상기 프로세서에 의해 실행되는 프로그램 또는 소프트웨어 모듈을 실행 공간을 제공하는 메모리, 상기 프로세서에 의해 처리된 중간 데이터 및 결과 데이터를 영구적으로 저장하거나, 상기 중간 데이터 및 결과 데이터를 데이터베이스 형태로 영구적으로 저장하는 저장 매체, 사용자 명령을 수신하고 상기 중간 데이터 및 결과 데이터를 시각적 또는 청각적 정보 형태로 출력하는 입/출력 인터페이스, 외부 장치와의 유선 또는 무선 통신을 지원하는 통신 모듈을 포함하도록 구성될 수 있다. 여기서, 프로세서는, 적어도 하나의 CPU(Central Processing Unit), 적어도 하나의 GPU(Graphic Processing Unit), 적어도 하나의 마이크로 컨트롤러 유닛(MCU: Micro Controller Unit), 적어도 하나의 시스템 온 칩(SoC: System on Chip) 및/또는 이들의 조합 중에서 적어도 하나를 포함하도록 구성된 하드웨어일 수 있다.The subject of the steps (S100 to S700) described below may be a computing device mounted in the mobile robot (or mobile robot) or placed outside the mobile robot. The computing device may be configured to include a processor that performs operations for data and image processing, a memory that temporarily stores program instructions required for data and image processing, temporarily stores intermediate data and result data processed by the processor, or provides an execution space for a program or software module executed by the processor, a storage medium that permanently stores the intermediate data and result data processed by the processor, or permanently stores the intermediate data and result data in the form of a database, an input/output interface that receives a user command and outputs the intermediate data and result data in the form of visual or auditory information, and a communication module that supports wired or wireless communication with an external device. Here, the processor may be hardware configured to include at least one of at least one Central Processing Unit (CPU), at least one Graphic Processing Unit (GPU), at least one Micro Controller Unit (MCU), at least one System on Chip (SoC), and/or a combination thereof.

도 1을 참조하면, 먼저, 단계 S100에서, 전역 지도를 복수의 서브맵들(submaps)로 분할하는 과정이 수행된다. 여기서, 전역 지도(global map)는 모바일 로봇에 탑재된 2D 레이저 스캐너(laser scanner) 또는 2D 라이다(LiDAR)와 같은 센서를 이용하여 생성한 2D 또는 3D 점유 격자 지도(2D/3D Occupancy Grid Map)일 수 있다.Referring to FIG. 1, first, in step S100, a process of dividing a global map into a plurality of submaps is performed. Here, the global map may be a 2D or 3D occupancy grid map (2D/3D Occupancy Grid Map) generated using a sensor such as a 2D laser scanner or 2D LiDAR mounted on a mobile robot.

상기 S100에 이어 수행되는 단계들 S200, S300 및 S400들은 병렬적으로 또는 순차적으로 수행될 수 있다. 본 문서에서는 상기 단계들 S200, S300 및 S400들이 병렬적으로 동시에 수행되는 것으로 가정한다.Steps S200, S300 and S400 performed following the above S100 may be performed in parallel or sequentially. In this document, it is assumed that steps S200, S300 and S400 are performed simultaneously in parallel.

S200에서, 각 서브맵(submap) 내에서 경계(boundary) 영역(또는 점유(occupied) 영역)의 분포 특징(distribution features) 또는 기하학적 특징 정보(geometric feature information)의 제1 통계치(first statistic)를 계산하는 과정이 수행된다. 여기서, 제1 통계치는 경계 영역(또는 점유(occupied) 영역)의 기하학적 특징 정보(geometric feature information)를 수치화(digitizing 또는 quantifying)하여 획득한 경계 히스토그램서, 이 경계 히스토그램은 경계 영역의 기하학적 특징 정보를 나타내는 전역 기술자로 사용될 수 있다.In S200, a process of calculating a first statistic of distribution features or geometric feature information of a boundary area (or an occupied area) within each submap is performed. Here, the first statistic is a boundary histogram obtained by digitizing (or quantifying) geometric feature information of the boundary area (or the occupied area), and the boundary histogram can be used as a global descriptor representing the geometric feature information of the boundary area.

S200와 병렬적으로 수행되는 S300에서, 각 서브맵(submap) 내에서 자유 공간(free space) 영역(또는 비점유(unoccupied) 영역)의 분포 특징(distribution features) 또는 기하학적 특징 정보의 제2 통계치(second statistic)를 계산하는 과정이 수행된다. 여기서, 제2 통계치 역시 자유 공간(free space) 영역(또는 비점유(unoccupied) 영역)의 기하학적 특징 정보(geometric feature information)를 수치화(digitizing 또는 quantifying)하여 획득한 자유 공간 히스토그램으로서, 자유 공간 영역의 기하학적 특징 정보를 나타내는 전역 기술자로 사용된다.In S300, which is performed in parallel with S200, a process of calculating second statistics of distribution features or geometric feature information of a free space region (or an unoccupied region) within each submap is performed. Here, the second statistics are also obtained by digitizing (or quantifying) geometric feature information of a free space region (or an unoccupied region), as a free space histogram, and are used as a global descriptor representing geometric feature information of the free space region.

S200 및 S300과 병렬적으로 수행되는 S400에서, 각 서브맵(submap)의 구조적 특징 정보(structural feature information)에 대한 반사 대칭 스코어(reflection symmetry score)를 계산하는 과정이 수행된다.In S400, which is performed in parallel with S200 and S300, a process of calculating a reflection symmetry score for structural feature information of each submap is performed.

S200, S300 및 S400에 의해 각각 계산된 통계치들, 즉, 경계 히스토그램, 자유 히스토그램 및 반사 대칭 스코어는 실제 전역 위치인식을 수행하기 전 오프라인에서 계산되어 서브맵과 함께 데이터베이스에 저장된다. The statistics computed by S200, S300 and S400 respectively, i.e., boundary histogram, free histogram and reflection symmetry score, are computed offline before performing the actual global localization and stored in the database together with the submaps.

이어, S500에서, 상기 제1 통계치, 제2 통계치 및 상기 반사 대칭 스코어(reflection symmetry score)를 기반으로 데이터베이스에 저장된 서브맵들과 현재 입력되는 쿼리 서브맵(query submap) 사이의 유사도(similarity score)를 계산하는 과정이 수행된다. Next, in S500, a process of calculating a similarity score between the submaps stored in the database and the currently input query submap is performed based on the first statistic, the second statistic, and the reflection symmetry score.

이어, S600에서, 상기 계산된 유사도(similarity score)를 기반으로 데이터베이스에 저장된 서브맵들 중에서 쿼리 서브맵과 가장 유사한 서브맵을 선정하는 과정이 수행된다. 여기서, 서브맵과의 비교를 위해, 쿼리 서브맵에 대한 전술한 S200 내지 S400의 계산 과정들이 수행될 수 있다.Next, in S600, a process of selecting a submap most similar to the query submap among the submaps stored in the database based on the calculated similarity score is performed. Here, for comparison with the submap, the calculation processes of S200 to S400 described above may be performed for the query submap.

이어, S700에서, 가장 유사한 서브맵의 선정이 완료되면, 상기 선정된 서브맵에 포함된 좌표 정보를 기반으로 모바일 로봇의 전역 위치인식(global localization) 과정이 수행된다.Next, in S700, once the selection of the most similar submap is completed, the global localization process of the mobile robot is performed based on the coordinate information included in the selected submap.

S500과 S600은 서브맵을 데이터베이스에 저장된 모든 서브맵들 S_i과 비교하여 가장 잘 매칭되는 서브맵을 찾는(finding) 과정으로서 하나의 단계로 통합될 수 있다. S500 and S600 can be integrated into one step as a process of finding the best matching submap by comparing the submap with all submaps S _i stored in the database.

이하, 전술한 각 단계에 대해 상세히 설명하기로 한다.Below, each of the above steps will be explained in detail.

전역 지도(또는 2D 점유 격자 지도)를 복수의 서브맵들로 분할(partitioning) 과정(S100)Partitioning process of global map (or 2D occupancy grid map) into multiple submaps (S100)

도 2는 본 발명의 실시 예에 따른 전역 지도로 활용되는 2D 점유 격자 지도의 예를 보여주는 도면이다.FIG. 2 is a drawing showing an example of a 2D occupancy grid map utilized as a global map according to an embodiment of the present invention.

도 2를 참조하면, 본 발명의 실시 예에 따른 전역 지도로 활용되는 2D 점유 격자 지도(20)는 모바일 로봇 또는 이동 로봇에 탑재된 2D 레이저 스캐너(laser scanner)(또는 2D 라이다(LiDAR))에 의해 획득된 2D 레이저 스캔 데이터(2D laser scan data)를 기반으로 생성될 수 있다.Referring to FIG. 2, a 2D occupancy grid map (20) utilized as a global map according to an embodiment of the present invention may be generated based on 2D laser scan data acquired by a 2D laser scanner (or 2D LiDAR) mounted on a mobile robot or a moving robot.

2D 점유 격자 지도(20)에서 로봇의 위치를 알아내기 위해, 가장 최근에 생성한 서브맵과 2D 점유 격자 지도(20)을 비교해야 한다. 따라서 2D 점유 격자 지도(20)를 정해진 단위로 분할하는 과정이 필요하다. In order to find out the location of the robot in the 2D occupancy grid map (20), the most recently generated submap must be compared with the 2D occupancy grid map (20). Therefore, a process of dividing the 2D occupancy grid map (20) into fixed units is required.

2D 점유 격자 지도(20)를 균등한 간격(uniform interval)으로 분할할 수도 있으나, 이 경우 로봇이 위치할 수 없는 영역을 포함하는 서브맵이 생성될 수 있으므로, 이를 방지하기 위해, 본 발명의 실시 예에서는, 2D 점유 격자 지도(20) 상의 정션 포인트(junction point)를 기준으로 2D 점유 격자 지도(20)를 분할하여 복수의 서브맵들을 생성한다. 여기서, 정션 포인트는 2D 점유 격자 지도 상에서 로봇의 이동 경로가 분기되는 포인트를 의미할 수 있다.The 2D occupancy grid map (20) may be divided into uniform intervals, but in this case, a submap including an area where the robot cannot be positioned may be generated. To prevent this, in an embodiment of the present invention, the 2D occupancy grid map (20) is divided based on a junction point on the 2D occupancy grid map (20) to generate a plurality of submaps. Here, the junction point may mean a point where the robot's movement path branches off on the 2D occupancy grid map.

도 3은 본 발명의 실시 예에 따른 전역 지도로 활용되는 2D 점유 격자 지도를 복수의 서브맵들로 분할하는 과정을 설명하기 위한 흐름도이고, 도 4는 도 3의 S120에 의해 생성된 에지 지도 이미지를 보여주는 도면이고, 도 5는 도 4에 도시된 에지 지도 이미지 상에 도 3의 S130에 의해 추출된 후보 정션 포인트들과 S140에 의해 추출된 정션 포인트들을 나타낸 도면이다. 그리고, 도 6은 도 3의 S150에 의해 2D 점유 격자 지도로부터 분할된 복수의 서브맵들의 예시도이다.FIG. 3 is a flowchart illustrating a process of dividing a 2D occupancy grid map utilized as a global map according to an embodiment of the present invention into a plurality of submaps, FIG. 4 is a diagram showing an edge map image generated by S120 of FIG. 3, and FIG. 5 is a diagram showing candidate junction points extracted by S130 of FIG. 3 and junction points extracted by S140 on the edge map image illustrated in FIG. 4. And FIG. 6 is an example diagram of a plurality of submaps divided from a 2D occupancy grid map by S150 of FIG. 3.

도 3을 참조하면, 먼저 S110에서, 2D 점유 격자 지도(20) 상의 자유 공간(free space) 영역을 탐지하기 위해, 2D 점유 격자 지도(20)를 이진 스케일로 이루어진 이진화 지도(binary map) 이미지로 변환한 후, 이미지 처리 기술들(image processing technique) 중에 하나인 거리 변환(distance transform) 기법에 따라 이진화 지도 이미지를 거리 변환 이미지(distance transformed image 또는 distance transformed map image)로 변환한다.Referring to FIG. 3, first, in order to detect a free space area on a 2D occupancy grid map (20), in S110, the 2D occupancy grid map (20) is converted into a binary map image consisting of a binary scale, and then the binary map image is converted into a distance transformed image (or distance transformed map image) according to a distance transform technique, which is one of image processing techniques.

이어, S120에서, 거리 변환 이미지는 중요하지 않은 자유 공간 영역을 포함하므로 주 탐색 경로(main navigation path)만을 추출하기 위해, 상기 거리 변환 지도 이미지를 모폴로지 연산(morphological operation) 기법(예, erosion morphological operator)과 이미지 희석화(image thinning) 기법을 기반으로 1-픽셀 너비(1-pixel width)를 갖는 에지 지도 이미지(edge map image)(도 4의 40)로 변환한다.Next, in S120, since the distance transform image includes an unimportant free space region, in order to extract only the main navigation path, the distance transform map image is converted into an edge map image (40 in FIG. 4) with a 1-pixel width based on a morphological operation technique (e.g., erosion morphological operator) and an image thinning technique.

이어, S130에서, 에지 지도 이미지(도 4의 40)의 모든 0이 아닌 픽셀들(nonzero pixels)에서 정션 테스트(junction test)를 수행하여, 후보 정션 포인트들(candidate junction points)(도 5의 41, 42, 43, 44, 45, 46, ?? )을 추출한다. 여기서, 정션 테스트는, 예를 들면, 에지 지도 이미지(도 4의 40)에서 에지(경계)를 구성하는 모든 픽셀들을 중심 픽셀(41)로 구성한 3×3 이미지 패치들(image patch)(도 4의 A)를 추출한다. 이후, 3×3 이미지 패치(A) 내에서 상기 중심 픽셀(41)을 둘러싸는 주변 픽셀들(41A, 41B 및 41C) 중에서 적어도 3개의 주변 픽셀들의 픽셀값이 중심 픽셀(41)의 픽셀값과 다른 경우, 중심 픽셀(41)을 후보 정션 포인트로 추출한다. 도 4에서는 중심 픽셀(41)이 흰색 그레이 스케일이고, 주변 픽셀들(41A, 41B 및 41C)이 검은색 그레이 스케일로 구성된 3×3 이미지 패치(A)의 예를 나타낸 것으로, 이 경우에서 중심 픽셀(41)은 세 방향으로 분기된 후보 정션 포인트로 정의할 수 있다.Next, in S130, a junction test is performed on all nonzero pixels of the edge map image (40 in FIG. 4) to extract candidate junction points (41, 42, 43, 44, 45, 46, ?? in FIG. 5). Here, the junction test extracts, for example, 3×3 image patches (A in FIG. 4) that consist of all pixels constituting an edge (boundary) in the edge map image (40 in FIG. 4) as the center pixel (41). Thereafter, if the pixel values of at least three of the surrounding pixels (41A, 41B, and 41C) surrounding the central pixel (41) in the 3×3 image patch (A) are different from the pixel value of the central pixel (41), the central pixel (41) is extracted as a candidate junction point. FIG. 4 illustrates an example of a 3×3 image patch (A) in which the central pixel (41) is composed of a white gray scale and the surrounding pixels (41A, 41B, and 41C) are composed of a black gray scale. In this case, the central pixel (41) can be defined as a candidate junction point branching in three directions.

이어, S140에서, 후보 정션 포인트들을 밀도 기반의 클러스터링 기법(Density-based spatial clustering)을 이용하여 군집화(clustering)하여 군집화 된 후보 정션 포인트들(도 5의 41~46)을 대표하는 정션 포인트들(junction points)(도 5의 50, 51, 52, ?? )을 추출한다.Next, in S140, candidate junction points are clustered using a density-based spatial clustering technique, and junction points (50, 51, 52, ?? in FIG. 5) representing the clustered candidate junction points (41 to 46 in FIG. 5) are extracted.

이어, S150에서, 2D 점유 격자 지도(20)는 각 정션 포인트를 중심으로 일정한 반경 r을 갖는 복수의 서브맵 이미지들의 합으로 표현할 수 있으며, 이 경우, 2D 점유 격자 지도(20)를 상기 추출된 각 정션 포인트를 중심 포인트로 하는 복수의 서브맵들로 분할한다. 도 6에는 S110 내지 S150을 거쳐 도 2의 2D 점유 격자 지도(20)를 12개로 분할한 서브맵 이미지들(SM1 ~ SM12)의 예가 나타난다.Next, in S150, the 2D occupancy grid map (20) can be expressed as a sum of multiple sub-map images having a constant radius r centered on each junction point, and in this case, the 2D occupancy grid map (20) is divided into multiple sub-maps with each extracted junction point as a center point. Fig. 6 shows examples of sub-map images (SM1 to SM12) obtained by dividing the 2D occupancy grid map (20) of Fig. 2 into 12 through S110 to S150.

경계 영역의 기하학적 특징 정보에 대한 통계치 계산(S200)Calculating statistics on geometric features of boundary areas (S200)

경계(boundary) 영역의 기하학적 특징 정보(geometric feature information)는 서브맵(submap) 내에서 경계 영역, 즉, 점유(occupied) 영역을 형성하는 픽셀들의 분포 특징(distribution features)을 의미하며, 통계치는 점유(occupied) 영역을 형성하는 픽셀들의 분포 특징(distribution features)을 히스토그램으로 변환한 데이터 또는 값을 의미한다.The geometric feature information of the boundary area refers to the distribution features of the pixels forming the boundary area, i.e., the occupied area, within the submap, and the statistics refer to the data or values converted into a histogram of the distribution features of the pixels forming the occupied area.

경계 영역은 서브맵 내에서 볼 수 있는 전반적인 외곽 라인을 의미한다. 이는 서브맵을 분별하게 하는 주요한 특징이 된다. 본 발명의 실시 예에서는 서브맵 내에서 볼 수 있는 경계 영역의 기하학적 특징 또는 분포 특징이 수치화된 통계치를 계산하기 위해 아래의 과정들을 수행한다.The boundary area refers to the overall outer line that can be seen within the submap. This is a key feature that distinguishes the submap. In an embodiment of the present invention, the following processes are performed to calculate numerical statistics of geometrical features or distributional features of the boundary area that can be seen within the submap.

도 7은 본 발명의 실시 예에 따른 경계 영역의 기하학적 특징 정보에 대한 통계치 계산 과정을 상세히 설명하기 위한 흐름도이다.FIG. 7 is a flowchart for explaining in detail a statistical calculation process for geometric feature information of a boundary area according to an embodiment of the present invention.

도 7을 참조하면, 먼저, S210에서, 다양한 이미지 처리 기법을 기반으로 서브맵 이미지(또는 쿼리 서브맵 이미지)를 이진화 서브맵 이미지(binary submap image)로 변환하는 과정이 수행된다. 서브맵의 각 픽셀값은 점유(occupancy) 정도를 나타낸다. 서브맵 내부의 애매모호한 픽셀들을 제거하고 명확하게 점유된(occupied) 픽셀들만을 고려하기 위해, inverse-binary thresholding 알고리즘을 기반으로 서브맵 이미지를 이진화 서브맵 이미지 로 변환한다. 여기서, 의 위 첨자 B는 Binary의 약자를 의미하고, 아래 첨자 i는 i번째 이진화 서브맵 이미지를 의미한다.Referring to Fig. 7, first, in S210, a process of converting a submap image (or a query submap image) into a binary submap image is performed based on various image processing techniques. Each pixel value of the submap indicates the degree of occupancy. In order to remove ambiguous pixels within the submap and consider only clearly occupied pixels, the submap image is converted into a binary submap image based on an inverse-binary thresholding algorithm. Convert to . Here, The superscript B stands for Binary, and the subscript i stands for the ith binarized submap image.

이어, S220에서, 다양한 이미지 처리 기법을 기반으로 이진화 서브맵 이미지 를 에지 지도 이미지 로 변환하는 과정이 수행된다. 여기서, 의 위 첨자 E는 Edge의 약자를 의미한다. 매핑(mapping) 과정에서 센서 노이즈 또는 매핑 오차로 인하여 벽과 같은 구조물은 밀집된 점유(occupied) 영역으로 표현할 수 있다. 이진화 서브맵 이미지 를 에지 지도 이미지 로 변환하기 위해, 이미지 희석화(image thinning) 기법이 활용될 수 있다. 예를 들면, 이진화 서브맵 이미지 는 이미지 희석화(image thinning) 기법으로, 를 한 픽셀 너비(1-pixel width)를 가지는 에지 지도 이미지 로 변환될 수 있다.Next, in S220, the binarized submap image is generated based on various image processing techniques. Edge map image The process of converting to is performed. Here, The superscript E stands for Edge. During the mapping process, structures such as walls can be represented as densely occupied areas due to sensor noise or mapping errors. Binarized submap image Edge map image To convert to, image thinning techniques can be utilized. For example, binarized submap images is an image thinning technique, An edge map image with a 1-pixel width can be converted into .

이어, S230에서, 에지 지도 이미지 내에서 상기 경계 영역을 형성하는 경계 포인트들(boundary points)(또는 에지 포인트들(edge points))을 샘플링 하는 과정이 수행된다. 경계 포인트들은 에지 지도 이미지 내에서 영이 아닌 픽셀들(nonzero pixels)의 집합을 의미한다. 본 발명의 실시 예에서는 균등 샘플링(uniform sampling) 기법을 기반으로 경계 포인트들을 샘플링 한다. 이러한 균등 샘플링 기법에 의해 경계 포인트들의 수가 감소되어, 계산량을 줄일 수 있다.Next, in S230, Edge Map Image A process of sampling boundary points (or edge points) forming the above boundary area is performed. The boundary points are an edge map image. It refers to a set of nonzero pixels within. In an embodiment of the present invention, boundary points are sampled based on a uniform sampling technique. The number of boundary points is reduced by this uniform sampling technique, thereby reducing the amount of calculation.

이어, S240에서, 샘플링된 경계 포인트들을 2개씩 쌍으로 구성하여 복수의 경계 포인트 쌍들을 생성한 후, 각 경계 포인트 쌍에 포함된 2개의 경계 포인트들 사이의 거리값을 빈(bin)으로 하는 경계 히스토그램 값 (1D 히스토그램 )을 계산하는 과정이 수행된다. 여기서, 빈(bin)은 히스토그램의 한 구간을 의미한다. Next, in S240, the sampled boundary points are paired in pairs of two to generate multiple boundary point pairs, and then the boundary histogram values (1D histogram) are generated by using the distance values between the two boundary points included in each boundary point pair as bins. ) is performed. Here, bin means one section of the histogram.

도 8은 본 발명의 실시 예에 따른 경계 영역을 경계 포인트들로 나타낸 4개의 서브맵들의 예시도이고, 도 9는 도 8에 도시된 4개의 서브맵들의 경계 히스토그램을 나타내는 그래프이다.FIG. 8 is an example diagram of four submaps representing boundary areas as boundary points according to an embodiment of the present invention, and FIG. 9 is a graph representing boundary histograms of the four submaps illustrated in FIG. 8.

도 8 및 9를 참조하면, 참조번호 80이 가리키는 서브맵 3의 히스토그램과 다른 서브맵들(81, 82 및 83)의 히스토그램은 확연히 차이가 난다. 하지만 참조 번호 81이 가리키는 서브맵 24와 참조 번호 82가 가리키는 서브맵 39는 다른 경계 형상(boundary shape)을 가짐에도 불구하고 비슷한 변화 양상을 보인다. Referring to FIGS. 8 and 9, the histogram of submap 3 indicated by reference number 80 is clearly different from the histograms of other submaps (81, 82, and 83). However, submap 24 indicated by reference number 81 and submap 39 indicated by reference number 82 show similar change patterns despite having different boundary shapes.

이것은 경계 포인트들(경계 영역)의 분포 특징 또는 기하학적 특징을 나타내는 하나의 히스토그램 인자로는 모든 서브맵을 구분하는데 한계가 있음을 의미한다. 즉, 모든 서브맵을 구분하는데 있어서 경계 영역의 기하학적 특징 정보뿐만 아니라 아래에서 설명하는 자유 공간(free space) 영역의 기하학적 특징 정보를 함께 고려해야 함을 의미한다.This means that there is a limit to distinguishing all submaps with a single histogram factor representing the distribution characteristics or geometric characteristics of boundary points (boundary area). In other words, in distinguishing all submaps, it is necessary to consider not only the geometric characteristic information of the boundary area but also the geometric characteristic information of the free space area described below.

자유 공간 영역의 기하학적 특징 정보에 대한 통계치 계산(S300)Calculating statistics on geometric features of free space domains (S300)

서브맵 상의 자유 공간(free space) 영역은 모바일 로봇이 실제로 이동할 수 있는 영역 또는 경로를 의미한다. 이것은 서브맵의 내부 구조를 알 수 있는 유용한 기하학적 특징 정보를 제공한다. 이 기하학적 특징 정보를 전술한 경계 영역의 기하학적 특징 정보와 융합하면 서브맵 매칭 성능(submap matching performance)을 높일 수 있다. 본 발명의 실시 예는 아래와 같은 과정들을 수행하여 자유 공간 영역의 기하학적 특징 정보 또는 분포 특징(distribution)을 수치화한 통계치, 즉, 히스토그램을 생성한다.The free space area on the submap refers to an area or path where the mobile robot can actually move. This provides useful geometric feature information that can identify the internal structure of the submap. By fusing this geometric feature information with the geometric feature information of the aforementioned boundary area, the submap matching performance can be improved. An embodiment of the present invention generates a statistical value, i.e., a histogram, that quantifies the geometric feature information or distribution feature of the free space area by performing the following processes.

도 10은 본 발명의 실시 예에 따른 자유 공간 영역의 기하학적 특징 정보에 대한 통계치 계산 과정을 상세히 설명하기 위한 흐름도이다.FIG. 10 is a flowchart for explaining in detail a statistical calculation process for geometric feature information of a free space region according to an embodiment of the present invention.

도 10을 참조하면, 먼저, S310에서, 다양한 이미지 처리 기법을 기반으로 서브맵 이미지(또는 쿼리 서브맵 이미지)에서 이진화 서브맵 이미지로 변환하는 과정이 수행된다. S310은 도 1의 S110과 S120을 포함한다. Referring to Fig. 10, first, in S310, a process of converting a submap image (or a query submap image) into a binarized submap image based on various image processing techniques is performed. S310 includes S110 and S120 of Fig. 1.

이어, S320에서, 다양한 이미지 처리 기법을 기반으로 이진화 서브맵 이미지를 에지 지도 이미지로 변환하는 과정이 수행된다. S320은 도 1의 S130과 거의 동일하다. Next, in S320, a process of converting a binarized submap image into an edge map image based on various image processing techniques is performed. S320 is almost identical to S130 of Fig. 1.

이어, S330에서, 에지 지도 이미지 내에서 자유 공간 영역을 형성하는 자유 공간 포인트들 을 추출(샘플링)하는 과정이 수행된다. S330은 도 1의 S130과 거의 유사하다. 다만, 자유 공간 포인트들은 에지 지도 이미지 내에서 0이 아닌 픽셀들(nonzero pixels)이 아니라 O인 픽셀들(zero pixels)의 집합을 의미하는 점에서 S330과 도 1의 S130 간에 차이가 있다.Next, in S330, free space points forming a free space region within the edge map image A process of extracting (sampling) is performed. S330 is almost similar to S130 of Fig. 1. However, there is a difference between S330 and S130 of Fig. 1 in that free space points mean a set of zero pixels rather than nonzero pixels in the edge map image.

이어, S340에서, 상기 추출(샘플링)된 자유 공간 포인트들 중에서 상기 자유 공간 포인트들 사이의 최단 경로 거리(shortest path distance) 값을 계산하는 과정이 수행된다. 자유 공간 포인트들을 이용하여 가시성 그래프(visibility graph)를 구성함으로써 임의의 자유 공간 포인트 m으로부터 다른 임의의 자유 공간 포인트 n으로 연결되는 최단거리 경로를 구할 수 있다. 가시성 그래프(visibility graph)는 인접 행렬(adjacency matrix) A = [a_mn]로 표현될 수 있으며, 인접 행렬의 각 엘리먼트(element) a_mn은 자유 공간 포인트들 사이의 유클리드 거리(Euclidean distance)가 된다. 자유 공간 포인트 m에서 자유 공간 포인트 n의 직선 경로 상에 점유 픽셀(occupied pixel)이 존재하면 a_mn는 무한대의 값을 가진다. 최단 경로 거리 값을 구하기 위해 다익스트라(Dijkstra) 알고리즘이 이용될 수 있다.Next, in S340, a process of calculating a shortest path distance value between the free space points among the extracted (sampled) free space points is performed. By constructing a visibility graph using the free space points, a shortest path connecting an arbitrary free space point m to another arbitrary free space point n can be obtained. The visibility graph can be expressed as an adjacency matrix A = [a _mn ], and each element a _mn of the adjacency matrix becomes a Euclidean distance between the free space points. If an occupied pixel exists on the straight line path from the free space point m to the free space point n, a _mn has an infinite value. The Dijkstra algorithm can be used to obtain the shortest path distance value.

이어, S350에서, 상기 최단 경로 거리값을 갖는 2개의 자유 공간 포인트들을 자유 공간 포인트 쌍으로 구성하고, 자유 공간 포인트 쌍의 상기 최단 경로 거리값을 빈(bin)으로 하는 자유공간 히스토그램 값(1D 히스토그램 )을 계산하는 과정이 수행된다. 여기서, 의 위 첨자 f는 free space(자유 공간)의 약자를 의미한다.Next, in S350, two free space points having the shortest path distance values are configured as free space point pairs, and free space histogram values (1D histogram) with the shortest path distance values of the free space point pairs as bins are generated. ) is calculated. Here, The superscript f stands for free space.

도 11은 본 발명의 실시 예에 따른 자유 공간 영역을 자유 공간 포인트(84)들로 나타낸 4개의 서브맵들의 예시도이고, 도 12는 도 11에 도시된 4개의 서브맵들의 자유 공간 히스토그램을 나타내는 그래프이다.FIG. 11 is an example diagram of four submaps representing a free space area according to an embodiment of the present invention as free space points (84), and FIG. 12 is a graph representing a free space histogram of the four submaps illustrated in FIG. 11.

도 11에 도시된 서브맵들(80, 81, 82 및 83)은 도 8에 도시된 서브맵들(80, 81, 82, 83)과 동일하다. 다만, 도 11에 도시된 서브맵들(80, 81, 82 및 83)은 도 8에 도시된 서브맵들(80, 81, 82, 83)을 일정각도로 회전시킨 것들이다.The submaps (80, 81, 82, and 83) illustrated in Fig. 11 are identical to the submaps (80, 81, 82, and 83) illustrated in Fig. 8. However, the submaps (80, 81, 82, and 83) illustrated in Fig. 11 are obtained by rotating the submaps (80, 81, 82, and 83) illustrated in Fig. 8 by a certain angle.

참조 번호 81이 가리키는 서브맵 24와 참조 번호 82가 가리키는 서브맵 39는 도 9에 도시된 경계 히스토그램 상에서는 구별이 어렵지만, 자유 공간 히스토그램(free space histogram) 상에서는 도 12에 도시된 바와 같이 조금 더 두드러진 차이를 확인할 수 있다.Submap 24 pointed to by reference number 81 and submap 39 pointed to by reference number 82 are difficult to distinguish on the boundary histogram shown in Fig. 9, but a slightly more prominent difference can be confirmed on the free space histogram, as shown in Fig. 12.

하지만 자유 공간 히스토그램(free space histogram)은 경계 히스토그램(boundary histogram)과는 달리 서브맵 3과 서브맵 24의 히스토그램 변화 경향성은 유사하다. 이것은 경계 히스토그램(boundary histogram)과 자유 공간 히스토그램(free space histogram)은 상호 보완적인 특징을 나타내며, 두 히스토그램의 조합을 통하여 장소(place)를 구분하는 성능을 높일 수 있음을 의미한다.However, unlike the boundary histogram, the free space histogram shows similar histogram changes in submap 3 and submap 24. This means that the boundary histogram and the free space histogram have complementary characteristics, and the performance of distinguishing places can be improved by combining the two histograms.

도 13은 본 발명의 실시 예에 따른 서로 다른 노이즈 레벨을 갖는 4개의 서브맵들의 예시도이고, 도 14는 도 13에 도시된 4개의 서브맵들의 자유 공간 히스토그램을 나타내는 그래프이다.FIG. 13 is an example diagram of four submaps having different noise levels according to an embodiment of the present invention, and FIG. 14 is a graph showing free space histograms of the four submaps illustrated in FIG. 13.

도 13 및 14를 참조하면, 노이즈에 대한 자유 공간 히스토그램(free space histogram)의 견고성을 확인하기 위해, 서브맵들(91, 92, 93)에는 매핑 과정에서 존재하지 않는 Nr개의 가상 장애물(94)이 무작위로 배치된다. 서브맵의 노이즈 레벨은 가상 장애물의 개수에 따라 결정된다. 가상 장애물(94)의 추가는 자유 공간 포인트(84)들의 분포 특징을 나타내는 히스토그램을 변경시킨다. 그러나 이것은 최단 경로 거리에 큰 영향을 미치지 않는다. 따라서 히스토그램의 변화 정도는 미미하다.Referring to FIGS. 13 and 14, in order to verify the robustness of the free space histogram to noise, Nr virtual obstacles (94) that do not exist in the mapping process are randomly placed in the submaps (91, 92, 93). The noise level of the submap is determined according to the number of virtual obstacles. The addition of the virtual obstacles (94) changes the histogram representing the distribution characteristics of the free space points (84). However, this does not significantly affect the shortest path distance. Therefore, the degree of change in the histogram is minimal.

반사 대칭 스코어(Reflection symmetry score) 계산(S400)Calculating the reflection symmetry score (S400)

위에서 설명한 경계 및 자유 공간 히스토그램은 서브맵의 기하학적 모양을 수량화(정량화)한 데이터인 반면, 반사 대칭 스코어는 서브맵의 전체 구조적 모양 또는 대칭성(symmetry)을 수량화(정량화)한 데이터 또는 값일 수 있다. While the boundary and free space histograms described above are data that quantify (quantify) the geometric shape of the submap, the reflection symmetry score can be data or values that quantify (quantify) the overall structural shape or symmetry of the submap.

대칭 유형에는 회전, 반사, 변환 및 glide 반사가 있다. 이 중 반사 대칭은 실내 구조에서 볼 수 있는 가장 일반적인 대칭 유형이다. 본 발명의 실시 예에서는 아래의 과정들을 통해 반사 대칭 스코어(reflection symmetry score)를 서브맵 이미지로부터 계산하고, 계산된 반사 대칭 스코어는 서브맵 유사도(submap similarity score) 계산(도 1의 S500) 시에 가중치(weight)로 활용된다.Symmetry types include rotation, reflection, translation, and glide reflection. Among these, reflection symmetry is the most common type of symmetry seen in indoor structures. In an embodiment of the present invention, a reflection symmetry score is calculated from a submap image through the following processes, and the calculated reflection symmetry score is used as a weight when calculating a submap similarity score (S500 in FIG. 1).

도 15는 본 발명의 실시 예에 따른 서브맵의 구조적 특징 정보에 대한 반사 대칭 스코어의 계산 과정을 상세히 설명하기 위한 흐름도이고, 도 16은 도 15의 각 단계에서 생성된 이미지의 예시도이다.FIG. 15 is a flowchart for explaining in detail the calculation process of a reflection symmetry score for structural feature information of a submap according to an embodiment of the present invention, and FIG. 16 is an example diagram of an image generated at each step of FIG. 15.

도 15 및 16을 참조하면, 먼저, S410에서, 다양한 이미지 처리 기법을 기반으로 서브맵 이미지(10)를 에지 지도 이미지로 변환하는 과정이 수행된다. S410은, 예를 들면, 도 7의 S210의 수행 과정과 동일하게 서브맵 이미지(10)를 이진화 서브맵 이미지(binary submap image)로 변환한 후, 도 7의 S220과 동일하게 이진화 서브맵 이미지 를 에지 지도 이미지 (11)로 변환하는 과정을 포함할 수 있다. Referring to FIGS. 15 and 16, first, in S410, a process of converting a submap image (10) into an edge map image based on various image processing techniques is performed. For example, in S410, the submap image (10) is converted into a binary submap image in the same manner as the process of S210 of FIG. 7, and then, in the same manner as S220 of FIG. 7, the binary submap image Edge map image (11) may include a process of converting to (11).

이어, S420에서, 에지 지도 이미지 (11)에서 추출된 일정 길이의 선분들(line segments)의 각도를 기반으로 두 개의 대칭축(α 및 β)을 검출하는 과정이 수행된다. 일정 길이 이상의 선분들(line segments)을 추출하기 위해, 예를 들면, 확률적 허프 변환(Probabilistic Hough Transform) 알고리즘이 이용될 수 있다. 건물의 실내 구조는 대부분 직사각형이기 때문에, 보트(Vote) 알고리즘을 기반으로 상기 추출된 선분들의 각도들을 보팅(voting)하는 방식으로 두 개의 대칭축(axes of symmetry) (α, β)이 검출될 수 있다.Next, in S420, edge map image (11) A process of detecting two axes of symmetry (α and β) is performed based on the angles of line segments of a certain length extracted from. In order to extract line segments of a certain length or longer, for example, a probabilistic Hough Transform algorithm can be used. Since the interior structure of a building is mostly rectangular, two axes of symmetry (α, β) can be detected by voting on the angles of the extracted line segments based on a vote algorithm.

이어, S430에서, 상기 검출된 2개의 반사 대칭축들 (α, β)을 수직하게 정렬되도록 회전된 에지 지도 이미지 를 가우시안-블러드(Gaussian-blurred) 이미지 (13)로 변환한 후, 상기 가우시안-블러드 이미지 (13)에서 0이 아닌 모든 픽셀들(u, v)의 위치에 대응하는 반전(flip)된 가우시안-블러드 이미지 의 픽셀들 의 평균 강도 를 반사 대칭 스코어로서 계산하는 과정이 수행된다. 즉, 반사 대칭 스코어의 계산은 상기 가우시안-블러드 이미지와 상기 대칭축 (α, β)을 기준으로 반전된 가우시안-블러드 이미지 사이의 유사도를 계산하는 과정일 수 있다.Next, in S430, the edge map image is rotated so that the two detected reflection symmetry axes (α, β) are aligned vertically. Gaussian-blurred image After converting to (13), the Gaussian-Blood image (13) Flipped Gaussian-blood image corresponding to the positions of all non-zero pixels (u, v) The pixels of The average intensity of A process of calculating a reflection symmetry score is performed. That is, the calculation of the reflection symmetry score may be a process of calculating the similarity between the Gaussian-blood image and an inverted Gaussian-blood image based on the symmetry axis (α, β).

대칭축 α에 대한 상기 반사 대칭 스코어 는 아래의 수학식으로 나타낼 수 있다.The above reflection symmetry score for the symmetry axis α can be expressed by the mathematical formula below.

반전(flip)된 가우시안-블러드 이미지 는, 예를 들면, 상기 가우시안-블러드 이미지 (13)를 상기 반사 대칭축을 기준으로 반전시킨 이미지일 수 있다. 에지 지도 이미지(11)를 가우시안-블러드 이미지로 변환하기 위해, 이미지 처리 분야에서 활용되는 다양한 이미지 블러드 기법들이 이용될 수 있다. 상기 회전된 에지 지도 이미지 (11)는 상기 2개의 반사 대칭축들 (α, β) 중에서 어느 하나의 대칭축이 수직하게 정렬되도록 상기 에지 지도 이미지 (11)를 회전시킨 이미지일 수 있다. 한편, 대칭축 β에 대한 반사 대칭 스코어(reflection symmetry score) 도 위와 같은 방법으로 계산할 수 있다.Flipped Gaussian-Blood image For example, the Gaussian-blood image (13) may be an image inverted based on the above reflection symmetry axis. In order to convert the edge map image (11) into a Gaussian-blood image, various image blur techniques utilized in the field of image processing may be used. The rotated edge map image (11) The edge map image is aligned so that one of the two reflection symmetry axes (α, β) is vertically aligned. (11) may be a rotated image. Meanwhile, the reflection symmetry score for the symmetry axis β It can also be calculated in the same way as above.

서브맵 유사도 계산(S500)Submap similarity calculation (S500)

위에서 구한 3가지의 통계치들, 즉, 경계 히스토그램, 자유 공간 히스토그램 및 반사 대칭 스코어는 실제 전역 위치 인식을 수행하기 전에 오프라인에서 계산된 후 입력 서브맵들 S _i 과 함께 데이터베이스에 저장된다. 이후, 로봇의 주행 과정에서 쿼리 서브맵 S _q 이 생성되면, 아래의 수학식 2에 따라 매칭 스코어(matching score)를 계산하고, 계산된 매칭 스코어의 역을 서브맵 유사도(similarity score: )로서 계산하는 과정이 수행된다.The three statistics obtained above, i.e., boundary histogram, free space histogram and reflection symmetry score, are calculated offline before performing the actual global localization and then stored in the database together with the input submaps S _i . Afterwards, when the query submap S _q is generated during the robot's driving process, the matching score is calculated according to the following mathematical expression 2, and the inverse of the calculated matching score is the submap similarity score: ) is calculated as follows.

서브맵 유사도(similarity score: ) 계산이 완료되면, 이를 기반으로 데이터베이스에 저장된 서브맵들 S_i 중에서 쿼리 서브맵 S _q 과 가장 잘 매칭되는 서브맵을 선정한다(S700).Submap similarity score: ) When the calculation is completed, the submap that best matches the query submap S _q is selected from among the submaps S _i stored in the database based on this (S700).

여기서, S 및 m(S_q, S_i)는 쿼리 서브맵 S _q 과 데이터베이스에 저장된 입력 서브맵 S _i 사이의 유사도(similarity score)이고, 와 는 서브맵 S_i의 대칭축 α와 β에 의한 반사 대칭 스코어를 각각 나타내고, 와 는 쿼리 서브맵 S_q의 대칭축 α와 β에 의한 반사 대칭 스코어를 각각 나타낸다. 즉, 는 대칭축 α를 기준으로 구분되는 좌측 서브맵과 우측 서브맵 사이의 유사한 정도를 나타내는 스코어이고, 는 대칭축 β를 기준으로 구분되는 좌측 서브맵과 우측 서브맵 사이의 유사한 정도를 나타내는 스코어이다. 유사하게, 는 대칭축 α를 기준으로 좌측 쿼리 서브맵과 우측 쿼리 서브맵 사이의 유사한 정도는 나타내는 스코어이고, 는 대칭축 β를 기준으로 좌측 쿼리 서브맵과 우측 쿼리 서브맵 사이의 유사한 정도는 나타내는 스코어이다. Ω()는 쿼리 서브맵 S_q과 서브맵 S_i 사이의 구조적 특징의 유사성을 계산하는 함수로서, 는 로 나타낼 수 있다. 여기서, 는 대칭축 α에 의한 쿼리 서브맵 S _q 의 반사 대칭 스코어 와 대칭축 α에 의한 서브맵 S _i 의 반사 대칭 스코어 사이의 차이값을 계산하는 식이고, 는 대칭축 β에 의한 쿼리 서브맵 S _q 의 반사 대칭 스코어 와 대칭축 β에 의한 서브맵 S _i 의 반사 대칭 스코어 사이의 차이값을 계산하는 식이다. 따라서, 쿼리 서브맵 S_q과 서브맵 S_i 사이의 구조적 특징의 유사성은 상기 차이값 과 상기 차이값 의 곱으로 계산할 수 있다.Here, S and m(S _q , S _i ) are the similarity scores between the query submap S _q and the input submap S _i stored in the database. and represents the reflection symmetry score along the symmetry axes α and β of the submap S _i , respectively. and represents the reflection symmetry score along the symmetry axes α and β of the query submap S _q , respectively. That is, is a score indicating the degree of similarity between the left and right submaps separated by the symmetry axis α . is a score indicating the degree of similarity between the left and right submaps, which are distinguished based on the symmetry axis β . Similarly, is a score indicating the degree of similarity between the left query submap and the right query submap based on the symmetry axis α . is a score indicating the degree of similarity between the left query submap and the right query submap based on the symmetry axis β . Ω() is a function that calculates the similarity of structural features between the query submap S _q and the submap S _i . Is can be expressed as . Here, is the reflection symmetry score of the query submap S _q along the symmetry axis α. The reflection symmetry score of the submap S _i along the symmetry axis α This is a formula for calculating the difference between is the reflection symmetry score of the query submap S _q along the symmetry axis β . The reflection symmetry score of the submap S _i along the symmetry axis β It is a formula for calculating the difference between the query submap S _q and the submap S i . Therefore, the similarity of the structural features between the query submap S q and the submap S _i is the difference value. and the above difference value It can be calculated by multiplying .

와 은 입력 서브맵 S_i의 경계 히스토그램과 자유 공간 히스토그램(값)을 각각 나타내고, 와 는 쿼리 서브맵 S_q의 경계 히스토그램(값)과 자유공간 히스토그램(값)을 각각 나타낸다. w_b는쿼리 서브맵 S_q의 경계 히스토그램(값)과 서브맵 S_i의 경계 히스토그램(값) 사이의 매칭 가중치를 나타내고, w_f는 쿼리 서브맵 S_q의 자유 공간 히스토그램(값)과 서브맵 S_i의 자유 공간 히스토그램(값) 사이의 매칭 가중치를 나타낸다. 그리고, Ω()는 쿼리 서브맵과 데이터베이스에 저장된 입력 서브맵 사이의 구조적 특징 정보의 유사도를 계산하는 함수이다. and represents the boundary histogram and free space histogram (value) of the input submap S _i , respectively. and represents the boundary histogram (value) and the free space histogram (value) of the query submap S _q , respectively. w _b represents the matching weight between the boundary histogram (value) of the query submap S _q and the boundary histogram (value) of the submap S _i , and w _f represents the matching weight between the free space histogram (value) of the query submap S _q and the free space histogram (value) of the submap S _i . In addition, Ω() is a function that calculates the similarity of structural feature information between the query submap and the input submap stored in the database.

도 17은 본 발명의 실시 예에 따른 모바일 로봇의 전역 위치인식을 위한 기능 블록도이다.FIG. 17 is a functional block diagram for global position recognition of a mobile robot according to an embodiment of the present invention.

도 17을 참조하면, 본 발명의 실시 예에 따른 전역 위치인식을 위한 장치는 이미지 분할기(100), 제1 기하학적 특징 추출기(200), 제2 기하학적 특징 추출기(300), 구조적 특징 추출기(400), 서브맵 유사도 계산기(500), 전역 위치인식 처리기(600) 및 데이터베이스(700)을 포함한다.Referring to FIG. 17, a device for global localization according to an embodiment of the present invention includes an image segmenter (100), a first geometric feature extractor (200), a second geometric feature extractor (300), a structural feature extractor (400), a submap similarity calculator (500), a global localization processor (600), and a database (700).

위의 구성들(100 ~ 700)은 설명의 이해를 돕기 위해 기능 단위로 구분한 것일 뿐, 본 발명을 제한하고자 하는 의도는 아니며, 다양하게 변경될 수 있다. 예를 들면, 위의 구성들 중 일부 구성들은 하나의 구성들로 통합되거나, 위의 구성들 중 어느 하나의 구성은 세부적인 기능 단위로 복수의 구성들로 분리될 수 있다. 예를 들면, 제1 기하학적 특징 추출기(200), 제2 기하학적 특징 추출기(300) 및 구조적 특징 추출기(400)은 '특징 추출기'라는 명칭으로 하나의 구성으로 통합될 수 있다. 또한 각 구성은 하드웨어 모듈 또는 소프트웨어 모듈로 구현되거나 이들의 조합으로 구현될 수 있다. 여기서, 하드웨어 모듈은 적어도 하나의 CPU, GUP 및/또는 MCU 등으로 구현된 프로세서를 포함하는 반도체 칩으로 구현될 수 있고, 소프트웨어 모듈은 프로세서에 의해 실행되는 알고리즘, 프로그램 등으로 구현될 수 있다.The above configurations (100 to 700) are only divided into functional units to help understanding the explanation, and are not intended to limit the present invention, and may be variously changed. For example, some of the above configurations may be integrated into one configuration, or any one of the above configurations may be separated into multiple configurations as detailed functional units. For example, the first geometric feature extractor (200), the second geometric feature extractor (300), and the structural feature extractor (400) may be integrated into one configuration under the name of 'feature extractor'. In addition, each configuration may be implemented as a hardware module or a software module, or may be implemented as a combination of these. Here, the hardware module may be implemented as a semiconductor chip including a processor implemented as at least one CPU, GUP, and/or MCU, and the software module may be implemented as an algorithm, a program, etc. executed by the processor.

각 구성에 대해 상세히 설명하면, 먼저, 이미지 분할기(100)는 전역 지도 이미지를 복수의 쿼리 서브맵 이미지들로 분할한다. 이를 위해, 이미지 분할기(100)는, 예를 들면, 도 1 또는 도 3의 S100에 따라 수행되는 과정들을 처리할 수 있다. 여기서, 전역 지도 이미지는 2D 또는 3D 점유 격자 지도 이미지일 수 있다.To describe each configuration in detail, first, the image segmenter (100) segments the global map image into a plurality of query sub-map images. To this end, the image segmenter (100) may process processes performed according to S100 of FIG. 1 or FIG. 3, for example. Here, the global map image may be a 2D or 3D occupancy grid map image.

제1 기하학적 특징 추출기(200)는 각 쿼리 서브맵 이미지 S _q 의 제1 기하학 적 특징을 추출한다. 이를 위해, 제1 기하학적 특징 추출기(200)는, 예를 들면, 도 1 또는 도 7의 S200에 따라 수행되는 과정들을 처리할 수 있다. 여기서, 제1 기하학적 특징은 각 쿼리 서브맵 이미지 S _q 에 포함된 경계 영역의 분포 특징을 수치(정량)화한 경계 히스토그램(값)일 수 있다. 경계 영역은 로봇이 이동할 수 없는 영역일 수 있다.The first geometric feature extractor (200) extracts the first geometric feature of each query sub-map image S _q . To this end, the first geometric feature extractor (200) may process processes performed according to, for example, S200 of FIG. 1 or FIG. 7. Here, the first geometric feature may be a boundary histogram (value) that numerically (quantitatively) quantifies the distribution characteristics of a boundary area included in each query sub-map image S _q . The boundary area may be an area in which the robot cannot move.

제2 기하학적 특징 추출기(300)는 각 쿼리 서브맵 이미지 S _q 의 제2 기하학 적 특징을 추출한다. 이를 위해, 제2 기하학적 특징 추출기(300)는, 예를 들면, 도 1 또는 도 10의 S300에 따라 수행되는 과정들을 처리할 수 있다. 여기서, 제2 기하학적 특징은 각 쿼리 서브맵 이미지 S _q 에 포함된 자유 공간 영역의 분포 특징을 수치(정량)화한 자유 공간 히스토그램(값)일 수 있다. 자유 공간 영역은 로봇이 이동할 수 있는 영역(또는 경로)일 수 있다.The second geometric feature extractor (300) extracts the second geometric feature of each query sub-map image S _q . To this end, the second geometric feature extractor (300) may process processes performed according to S300 of FIG. 1 or FIG. 10 , for example. Here, the second geometric feature may be a free space histogram (value) that numerically (quantitatively) quantifies the distribution features of a free space area included in each query sub-map image S _q . The free space area may be an area (or path) in which a robot can move.

구조적 특징 추출기(400)는 각 쿼리 서브맵 이미지 S _q 의 구조적 특징을 추출한다. 이를 위해, 구조적 특징 추출기(400)는, 예를 들면, 도 1 및 15의 S400에 따라 수행되는 과정들을 처리할 수 있다. 여기서, 구조적 특징은 쿼리 서브맵 S _q 의 전체 구조적 모양을 수량화(정량화)한 반사 대칭 스코어 일 수 있다.The structural feature extractor (400) extracts structural features of each query submap image S _q . To this end, the structural feature extractor (400) may process processes performed according to S400 of FIGS. 1 and 15 , for example. Here, the structural feature may be a reflection symmetry score that quantifies (quantifies) the overall structural shape of the query submap S _q .

반사 대칭 스코어를 계산하기 위해, 구조적 특징 추출기(400)는, 예를 들면, 3개의 감산기들(501, 503 및 505), 가산기(507), 곱셈기(509) 및 역수 계산기(511)를 포함할 수 있다.To compute the reflection symmetry score, the structural feature extractor (400) may include, for example, three subtractors (501, 503 and 505), an adder (507), a multiplier (509) and a reciprocal calculator (511).

제1 감산기(501)는 제1 기하학적 특징 추출기(200)에 의해 추출된(계산된) 쿼리 서브맵 S _q 의 경계 히스토그램값 과 데이터베이스(700)에 사전에 저장된 입력 서브맵 S _i 의경계 히스토그램값 의 차이값 을 계산한다. 이때, 차이값 에는 매칭 가중치 w _b 가 적용될 수 있다.The first subtractor (501) extracts (calculates) the boundary histogram values of the query submap S _q extracted (calculated) by the first geometric feature extractor (200). and the input submap S _i previously stored in the database (700).Boundary histogram values The difference between Calculate the difference value. Matching weights w _b can be applied.

제2 감산기(503)는 제2 기하학적 특징 추출기(300)에 의해 추출된(계산된) 쿼리 서브맵 S _q 의 자유공간 히스토그램값 과 데이터베이스(700)에 사전에 저장된 입력 서브맵 S _i 의자유공간 히스토그램값 의 차이값 을 계산한다. 이때, 차이값 에는 매칭 가중치 w _f 가 적용될 수 있다.The second subtractor (503) extracts (calculates) the free space histogram value of the query submap S _q extracted (calculated) by the second geometric feature extractor (300). and the input submap S _i previously stored in the database (700).Free space histogram values The difference between Calculate the difference value. Matching weights w _f can be applied.

제3 감산기(505)는 구조적 특징 추출기(400)에 의해 추출된(계산된) 쿼리 서브맵 S _q 의 대칭축 (α 및 β)에 의한 반사 대칭 스코어 와 데이터베이스(700)에 사전에 저장된 입력 서브맵 S _i 의 대칭축 (α 및 β)에 의한 반사 대칭 스코어 의 차이값 을 계산한다. The third subtractor (505) calculates the reflection symmetry score by the symmetry axes (α and β) of the query submap S _q extracted (calculated) by the structural feature extractor (400). and the reflection symmetry score by the symmetry axes (α and β) of the input submap S _i previously stored in the database (700). The difference between Calculate .

가산기(507)는 제1 감산기(501)로부터의 차이값 과 제2 감산기(503)로부터의 차이값 을 합산한다.The adder (507) adds the difference value from the first subtracter (501). and the difference value from the second subtractor (503) Add up.

곱셈기(507)는 가산기(507)의 출력과 제3 감산기(505)의 출력에 대한 곱셈 연산을 수행하여 획득한 매칭 스코어 m(S _q , S _i )를 출력한다.The multiplier (507) performs a multiplication operation on the output of the adder (507) and the output of the third subtracter (505) to output the matching score m(S _q , S _i ) .

역수 계산기(511)는 매칭 스코어 m(S _q , S _i )의 역수를 쿼리 서브맵 S _q 과 입력 서브맵 S _i 사이의 서브맵 유사도 ρ로서 계산한다.The reciprocal calculator (511) calculates the reciprocal of the matching score m(S _q , S _i ) as the submap similarity ρ between the query submap S _q and the input submap S _i .

전역 위치인식 처리기(600)는 상기 서브맵 유사도 ρ를 기반으로 쿼리 서브맵 S _q 과 가장 유사한 입력 서브맵 S _i 을 선정하고, 상기 선정된 입력 서브맵 S _i 에 포함된 좌표 정보를 기반으로 모바일 로봇의 전역 위치인식 과정을 수행한다. 전역 위치인식 처리기(600)는 도 1의 S600 및 S700에 따른 과정들을 처리할 수 있다.The global position recognition processor (600) selects an input submap S _i that is most similar to the query submap S _q based on the submap similarity ρ , and performs a global position recognition process of the mobile robot based on the coordinate information included in the selected input submap S _i . The global position recognition processor (600) can process processes according to S600 and S700 of FIG. 1.

데이터베이스(700)에는 서브맵 S _i 별로 사전에 계산된 경계 영역 히스토그램 , 자유공간 히스토그램 및 반사 대칭 스코어 가 저장된다. 데이터베이스(700)는 비휘발성 저장매체에 저장될 수 있다.The database (700) contains a pre-computed boundary area histogram for each submap S _i. , free space histogram and reflection symmetry score is stored. The database (700) may be stored in a non-volatile storage medium.

도 18은 본 발명의 실시 예에 따른 전역 위치인식을 수행하기 위한 컴퓨팅 장치를 나타내는 블록도이다.FIG. 18 is a block diagram illustrating a computing device for performing global position recognition according to an embodiment of the present invention.

도 18을 참조하면, 컴퓨팅 장치(1300)는, 로봇 내에 탑재되거나 로봇과 통신하는 외부 장치에 탑재될 수 있다. 컴퓨팅 장치(1300)는 버스(1370)를 통해 통신하는 프로세서(1310), 메모리(1330), 입력 인터페이스 장치(1350), 출력 인터페이스 장치(1360), 및 저장 장치(1340) 중 적어도 하나를 포함할 수 있다. 또한 휴대용 컴퓨터(1300)는 네트워크에 결합된 통신 장치(1320)를 포함할 수 있다. Referring to FIG. 18, the computing device (1300) may be mounted within the robot or may be mounted on an external device that communicates with the robot. The computing device (1300) may include at least one of a processor (1310), a memory (1330), an input interface device (1350), an output interface device (1360), and a storage device (1340) that communicates via a bus (1370). In addition, the portable computer (1300) may include a communication device (1320) coupled to a network.

프로세서(1310)는 적어도 하나의 CPU, 적어도 하나의 GPU 및 적어도 하나의 MCU를 포함하며, 메모리(1330) 또는 저장 장치(1340)에 저장된 명령을 실행하는 반도체 장치일 수 있다. 또한, 프로세서(1310)는 도 1 내지 17에 도시된 구성들 및/또는 과정들을 제어하거나, 처리하거나 연산할 수 있다. 특히 프로세서(1310)는 이미지를 처리하는데 충분한 성능을 보유한 고성능의 CPU 및 GPU를 포함할 수 있다.The processor (1310) may be a semiconductor device that includes at least one CPU, at least one GPU, and at least one MCU, and executes instructions stored in a memory (1330) or a storage device (1340). In addition, the processor (1310) may control, process, or calculate the configurations and/or processes illustrated in FIGS. 1 to 17. In particular, the processor (1310) may include a high-performance CPU and GPU that have sufficient performance to process images.

메모리(1330) 및 저장 장치(1340)는 다양한 형태의 휘발성 또는 비휘발성 저장 매체를 포함할 수 있다. 예를 들어, 메모리는 ROM(read only memory) 및 RAM(random access memory)를 포함할 수 있다. 예를 들어, 저장 장치(1340)는 하드디스크일 수 있다. 저장 장치(1340)에는 도 17에 도시된 데이터베이스(700)가 저장될 수 있다.The memory (1330) and the storage device (1340) may include various forms of volatile or nonvolatile storage media. For example, the memory may include a read only memory (ROM) and a random access memory (RAM). For example, the storage device (1340) may be a hard disk. The database (700) illustrated in FIG. 17 may be stored in the storage device (1340).

통신 장치(1320)는 유선 또는/및 무선 통신을 지원하는 통신 모듈일 수 있다. 통신 장치(1320)에 의해, 프로세서(1310)에서 처리한 데이터 및 이미지들은 외부 장치로 송신될 수 있다. The communication device (1320) may be a communication module that supports wired and/or wireless communication. Data and images processed by the processor (1310) may be transmitted to an external device by the communication device (1320).

입력 인터페이스 장치(1350)는 버튼, 마우스, 키보드, 터치 기능을 갖는 표시부로 구현될 수 있다.The input interface device (1350) can be implemented as a display unit having a button, mouse, keyboard, or touch function.

출력 인터페이스 장치(1360)은 프로세서(1310)에 의해 처리된 중간 데이터 및 결과 데이터를 시각적 및/또는 청각적인 형태의 정보로 출력할 수 있다. 결과 데이터는 전역 위치인식을 수행하여 최종적으로 획득한 로봇의 위치 정보일 수 있다.The output interface device (1360) can output intermediate data and result data processed by the processor (1310) as information in visual and/or auditory form. The result data can be location information of the robot finally acquired by performing global location recognition.

이상에서 본 발명의 실시 예에 대하여 상세하게 설명하였지만 본 발명의 권리 범위는 이에 한정되는 것은 아니고 다음의 청구범위에서 정의하고 있는 본 발명의 기본 개념을 이용한 당업자의 여러 변형 및 개량 형태 또한 본 발명의 권리 범위에 속하는 것이다.Although the embodiments of the present invention have been described in detail above, the scope of the rights of the present invention is not limited thereto, and various modifications and improvements made by those skilled in the art using the basic concept of the present invention defined in the following claims also fall within the scope of the rights of the present invention.

Claims

A method for global position recognition performed by a processor of a computing device mounted in a mobile robot,
A step of dividing a global map image into multiple query submap images;
A step of computing histogram values representing geometric features of each query submap image;
A step of calculating a reflection symmetry score representing structural feature information of each query submap image;
A step of calculating submap similarity between each query submap image and submap images stored in a database based on the histogram value and the reflection symmetry score; and
A step of selecting a submap image most similar to the query submap image based on the submap similarity and performing global position recognition of the mobile robot based on coordinate information included in the selected submap image is included.
The steps of calculating the above reflection symmetry score are:
A step of converting each query submap image into an edge map image based on an image processing technique;
A step of detecting a reflection symmetry axis based on the angle of line segments having a certain length in the above edge map image;
A step of rotating the edge map image so that the detected reflection symmetry axis is aligned vertically;
A step of converting the edge map image into a blurred image based on an image blurred technique; and
A step of calculating the similarity between the blood image and the blood image inverted (filp) based on the detected reflection symmetry axis as the reflection symmetry score.
A method for global localization of a mobile robot including a .

In paragraph 1,
The step of dividing the above global map image into multiple query submap images is:
A step of generating the global map image using a sensor mounted on the mobile robot;
A step of extracting a junction point defining a point at which the movement path of the mobile robot branches on the global map image; and
A step of dividing the above global map image into a plurality of query submap images having a constant radius centered on the above junction point.
A method for global localization of a mobile robot including a .

In paragraph 2,
The step of extracting the above junction points is:
A step of converting the global map image into an edge map image based on an image processing technique; and
The center pixel and the surrounding pixels within the above edge map image
Assuming an n×n image patch consisting of peripheral pixels, a step of extracting the central pixel as the junction point if the pixel value of the central pixel is different from the pixel values of at least three peripheral pixels.
A method for global localization of a mobile robot including a .

In paragraph 1,
The step of calculating histogram values representing the geometric features of each query submap image is:
A step of calculating a boundary histogram value representing the geometric features of a boundary area in which the mobile robot cannot move in each query submap image; and
A step of calculating free space histogram values representing geometric features of the free space area in which the mobile robot can move in each query submap image.
A method for global localization of a mobile robot including a .

In Article 4,
The steps for calculating the above boundary histogram values are:
A step of converting each query submap image into an edge map image based on an image processing technique;
A step of sampling boundary points forming the boundary area within the edge map image;
A step of generating a plurality of pairs of boundary points by configuring the sampled boundary points into pairs; and
A step of calculating the boundary histogram value based on the distance value between two boundary points included in each boundary point pair.
A method for global localization of a mobile robot including a .

In Article 4,
The steps for calculating the above free space histogram values are:
A step of converting each query submap image into an edge map image based on an image processing technique;
A step of extracting free space points forming the free space region within the edge map image;
A step of generating multiple pairs of free space points by pairing two free space points having a shortest path distance value among the extracted free space points; and
A step of calculating the free space histogram value based on the shortest path distance value of each free space point pair.
A method for global localization of a mobile robot including a .

delete

In paragraph 1,
The step of calculating the above submap similarity is:
A step of calculating a first difference value between the histogram value of each query submap image and the histogram values representing the geometric features of the submap images stored in the database;
A step of calculating a second difference between the reflection symmetry score of each query submap image and the reflection symmetry scores representing the structural features of the submap images stored in the database; and
A step of calculating the submap similarity based on the first and second difference values.
A method for global localization of a mobile robot including a .

In Article 9,
The step of calculating the first difference value is:
A step of calculating a difference between a boundary histogram value representing the geometric feature of the boundary area in which the mobile robot cannot move in each query submap image and boundary histogram values representing the geometric feature of the boundary area in which the mobile robot cannot move in the submap images; and
A step of calculating a difference between free space histogram values representing the geometric features of the free space area in which the mobile robot can move and free space histogram values representing the geometric features of the free space area in which the mobile robot can move in each query submap image.
A method for global localization of a mobile robot including a .

As a computing device for global position recognition of a robot,
An image segmenter that segments an occupancy grid map image into multiple query submap images;
A feature extractor for calculating histogram values representing geometric features of each query submap image and calculating a reflection symmetry score representing symmetry features of each query submap image;
A submap similarity calculator that calculates the similarity between each query submap image and submap images stored in a database based on the histogram value and the reflection symmetry score; and
Based on the submap similarity, a submap image most similar to the query submap image is selected, and a global location recognition processor is included that performs global location recognition of the robot based on coordinate information included in the selected submap image.
The above feature extractor,
A computing device for global localization of a mobile robot, comprising: a reflection symmetry axis detected based on angles of line segments having a certain length in an edge map image converted from each query submap image based on an image processing technique; a second edge map image rotated so that the detected reflection symmetry axis is aligned vertically; and a third edge map image blurred based on an image blurred technique, wherein the similarity between the blur image and a blur image inverted based on the detected reflection symmetry axis is calculated as the reflection symmetry score.

In Article 11,
The above image segmenter,
A computing device for global localization of a mobile robot, wherein the occupancy grid map image is divided into a plurality of query sub-map images based on junction points at which the movement path of the mobile robot branches on the occupancy grid map image.

In Article 11,
The above feature extractor,
A first geometric feature extractor for calculating a boundary histogram value that quantifies the distribution characteristics of a boundary area in which the mobile robot cannot move in each query submap image;
A second geometric feature extractor for calculating a free space histogram value that quantifies the distribution characteristics of the free space area in which the mobile robot can move in each query submap image; and
A structural feature extractor that computes a reflection symmetry score that quantifies the symmetry of each query submap image.
A computing device for global position recognition of a mobile robot including a .

In Article 11,
The above submap similarity calculator is,
A first subtractor that calculates the difference between the boundary histogram value quantifying the geometric features of the boundary area in each query submap image and the boundary histogram value quantifying the geometric features of the boundary area in the submap image stored in the database.
A second subtractor for calculating the difference between the free space histogram value quantifying the geometric features of the free space region in each query submap image and the boundary histogram value quantifying the geometric features of the free space region of the submap image stored in the database; and
A third subtractor that calculates the difference between the reflection symmetry score quantifying the symmetry of each query submap image and the reflection symmetry score quantifying the symmetry of the submap image stored in the database.
A computing device for global position recognition of a mobile robot including a .

In Article 14,
The above submap similarity calculator is,
A computing device for global localization of a mobile robot, which calculates the similarity between each query submap image and the submap images by calculating the difference values calculated by the first to third subtractors.

In Article 14,
The above submap similarity calculator is,
Further comprising an adder that adds the difference value calculated by the first subtracter and the difference value calculated by the second subtracter,
A computing device for global localization of a mobile robot, wherein the similarity between each query submap image and the submap images is calculated by calculating the difference value calculated by the third subtractor and the value added by the adder as a weight.

delete