# Keyframes Global Map Establishing Method for Robot Localization through Content-Based Image Matching

Authors: Tianyang Cao; Haoyuan Cai; Dongming Fang; Hui Huang; Chang Liu
Journal: Journal of Robotics
 (2017)

---

## Abstract

Self-localization and mapping are important for indoor mobile robot. We report a robust algorithm for map building and subsequent localization especially suited for indoor floor-cleaning robots. Common methods, for example, SLAM, can easily be kidnapped by colliding or disturbed by similar objects. Therefore, keyframes global map establishing method for robot localization in multiple rooms and corridors is needed. Content-based image matching is the core of this method. It is designed for the situation, by establishing keyframes containing both floor and distorted wall images. Image distortion, caused by robot view angle and movement, is analyzed and deduced. And an image matching solution is presented, consisting of extraction of overlap regions of keyframes extraction and overlap region rebuild through subblocks matching. For improving accuracy, ceiling points detecting and mismatching subblocks checking methods are incorporated. This matching method can process environment video effectively. In experiments, less than 5% frames are extracted as keyframes to build global map, which have large space distance and overlap each other. Through this method, robot can localize itself by matching its real-time vision frames with our keyframes map. Even with many similar objects/background in the environment or kidnapping robot, robot localization is achieved with position RMSE <0.5 m.


---

## Body

## 1. Introduction

The ideal indoor mobile robot should store a global map of the entire indoor space for self-localization, especially in a building including multiple rooms and corridors [1]. It would be much better if this global map can be built by the robot itself during indoor environment studying and without the help of human [2].For this research field, SLAM (Simultaneous Localization and Mapping) is the commonly employed [3], especially the V-SLAM (Visual Simultaneous Localization and Mapping) [4, 5]. Many latest variants take advantage of new features or 3D information to build navigation map [6, 7], including ORB SLAM [8], dense SLAM [9, 10], semidense SLAM [11], LSD SLAM [12], and CV-SLAM [13, 14]. The CV-SLAM method is specially designed for indoor robot localization [15] and could make good use of ceiling features as navigation map through an upward-looking camera [16]. This technology has been used widely in the Roomba, a product of iRobot Inc. Similar methods are used in other models made by Dyson, SAMSUNG, and LG.However, the SLAM method is easy to be disturbed, and the most troublesome problems include kidnap problem and similar objects interference [17]. The kidnap problem occurs frequently when a robot is suddenly involved in a collision, kicked, or intentionally repositioned during operation. The robot cannot localize itself according to video information of previous moments [18]. The similar object interference refers to the fact that a robot is easy to be confused by similar features on similar objects in different places and error fixed itself to the wrong position. An indoor robot that looks mostly at ceilings of indoor space do not detect many features of significance. To make matters worse, there are usually many similar objects in the indoor environment (e.g., air condition outlets, ceiling lamps, and ceiling). Hence established methods are not sufficiently reliable for global indoor positioning.In order to solve these problems, this paper presents keyframes global map establishing method for robot localization through content-based image matching, involving both ceiling and wall regions. The robot could establish global map by itself and fix its position at any time without the need of its localization information of previous moments and cannot be kidnapped.Comparing with the common keyframes extraction method (e.g., according to the robot moving time or distance), our keyframes extracted according to image content would be more useful (image content mainly including the objects in the room and their layout and their color distribution). Problems related to losing keyframes or redundancy can be avoided, especially when robot is changing speed or turning suddenly [19, 20].In this paper, the keyframes global map establishing method is also based on a specially designed content-based image matching method, which can calculate images similarity exactly. The keyframes for each room and corridor can be extracted from robot environment studying video by image content matching. This matching method is designed to avert image distortion interference caused by robot view angle and movement. It is designed based on a distortion model, which is deduced to analyze the distortion features of ceiling and wall region (e.g., wall, door, window, and furniture). According to these features, two image processing methods, including overlap region extraction method and overlap region rebuild method through subblocks matching, are presented. We firstadjust the distortion of vision frames nearly consistent and then calculate the similarity between frames. In order to adjust distortion more exactly, ceiling points detecting method and mismatching subblocks checking method are incorporated. Through content-based image matching, this paper can take advantage of the information of different objects imaged in different room to extract keyframes for each room from robot vision.These keyframes have very large space distance, and the whole indoor environment could be described only by 10 s of keyframes. Keyframes overlap with each other, and their position relationship can be extracted. These keyframes and their global position would compose global map for indoor environment. This content-based image matching method can also be used for robot self-localization. When the robot is moving in rooms or corridors, for the real-time updated robot vision, the most similar keyframe for each robot vision frame can be chosen automatically from this global map and the robot can fix its position precisely.In the test, the experiment site is composed of two rooms (20-meter-square) and two corridors (11 m). The robot can move automatically in this site to study environment features, and a video about 9.5 min (1710 frames) long had been taken by robot vision during indoor environment studying. Through the map establishing method presented in this paper, 72 keyframes (less than 5% frames) are extracted from this video to build the map of experiment site. The robot can make good use of this map to localize itself in the whole building. It is able to draw robot trajectory exactly, even in the event of kidnapping, with position RMSE less than 0.4 m.The rest of this paper is organized as follows. Section2 describes the design of robot vision system and the distortion features of common indoor objects. In Section 3, we discuss content-based image matching method and the keyframes global map establishing method. In Sections 4 and 5, the experiment result and conclusion are presented and discussed.


## 2. Image Distortion Model and Feature Analysis for Common Indoor Objects

Content-based image matching with both ceilings and walls is one of the best ways for detecting keyframes and building global map, which can extract keyframes from environment video as efficiently as possible to describe the indoor environment and keep the connection between these frames. However, the main problem for content-based image matching is the image distortion. If two frames are taken in different view angle and position, the objects distortions in them are different, and image content similarity between the two frames is difficult to be calculated.Here we discuss the method for analyzing features of image content distortion through establishing a distortion model. An upward-looking camera (SY012HD wide angle camera, Weixinshijie Technology Co., Ltd, Shenzhen, China) is installed on the wheeled robot (Roomba, R1-L081A, Midea, Suzhou, China) as the robot vision sensor [21], as shown in Figure 1(a), the same as that carrying a CV-SLAM [22, 23].Figure 1
The relationship between wall and upward-looking camera. (a) Robot and camera. (b) Relationship between front wall and side wall and camera.
(a) (b)


### 2.1. The Features of Robot View Angle and Movement for Ceiling and Wall Region

The camera model, which can change the three-dimensional object in the real world to two-dimensional picture, is as follows [24, 25]: (1)zxy1=1dx0001dy0001f000f0001RTXYZ1,where(2)R=cos⁡R0-sin⁡R010sin⁡R0cos⁡R·1000cos⁡Psin⁡P0-sin⁡Pcos⁡P·cos⁡Hsin⁡H0-sin⁡Hcos⁡H0001is calculated through robot view angles of roll R, pitch P, and heading H. The term T=TxTyTz is calculated through robot movements Tx and Ty and ceiling height Tz, X,Y,Z are the coordinates of an object point in three-dimensional real world, and x,y are its corresponding points in the robot vision. The terms f, dx, and dy are the constant of the camera: f is the camera focus and dx and dy are the scale factors.There are two kinds of main indoor objects: ceiling and wall regions. The ceiling is parallel to the floor, and wall regions (e.g., wall, window, door, and furniture) are perpendicular to the floor. For the upward-looking camera on the robot, the view angles for them are different.When a robot is moving on the floor, its route parallels the ceiling, the heading (givenH) is the only robot view angle can be changed, and both roll and pitch are equal to 0.For the wall region, because they are fixed on the floor, the freedom of robot view angles is also very limited. We analyze each wall separately, by giving each wall an independent coordinate (front/back wall or side wall), as shown in Figure1(b), with the X-axis perpendicular to the wall, Y-axis parallel to the wall and floor, and Z-axis perpendicular to the floor. The heading H between a wall and the robot is the only view angle which can be changed. As wall is perpendicular to floor and ceiling, it can be seen as a part of ceiling with roll or pitch of 90 deg. For the front wall (or back) of robot, the pitch is 90 deg and roll is 0, as shown in Figure 1(b). For the left wall (or right wall) on the robot, the roll is 90 deg and pitch is 0, as shown in Figure 1(b).Because of the different view angles, ceiling and wall deform differently in the robot vision. In order to match precisely, this deformation should be revised before image content matching. According to (1), it can also be deduced that robot movement Tx,Ty and object position X,Y,Z can also contribute to image distortion. Therefore, bringing the robot view angle and movement and object position into (1), the distortion models of ceiling and wall region could be established, and their distortion features can be extracted.


### 2.2. Ceiling Distortion Model and Feature Extraction

Given the coordinate origin on the ceiling,Tx and Ty show robot movement, and Tz is ceiling height. The heading between ceiling and camera is H, and roll and pitch are 0. Therefore (1) can be transformed as follows: (3)zxy1=1dx0001dy0001f000f0001cos⁡Hsin⁡H0Tx-sin⁡Hcos⁡H0Ty001TzXYZ1.It can be simplified as follows:(4)x=fdxTz+ZXcos⁡H+Ysin⁡H+Tx,y=fdyTz+Z-Xsin⁡H+Ycos⁡H+Ty.The distortion of ceiling only includes rotation and translation, and the shape of ceiling is unchanged. As rotation and translation are affine transform, they can be revised by affine transform too. Through SURF (Speed Up Robust Features), the matched feature points in framesA and B are extracted [26, 27]. Bringing these points coordinate into (5), the heading differenceΔH and movement differences Δtx and Δty between these two frames could be resolved [28]: (5)xByB=cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHxAyA+ΔtxΔty.Two frames,A and B, can be adjusted to the same robot view angles and camera shooting position after rotation and translation according toΔH, Δtx, and Δty. Their overlap regions (containing the same objects in two frames) could be extracted. The image similarity would be obtained by comparing the similarity of their overlap regions.


### 2.3. Wall Distortion Model and Feature Extraction

For the front wall (P=90, R=0) and side wall (P=0, R=90), the heading difference is 90 deg (or −90 deg), but their image distortions are the same and can be deduced as follows.Given that the robot heading isH when it is taking frame A, for a point X,Y,Z on the front wall, its corresponding point xAw,yAw on frame A of robot vision is calculated as follows: (6)zxAwyAw1=1dx0001dy0001f000f00011000010-10cos⁡Hsin⁡H0-sin⁡Hcos⁡H0001TxTyTzXYZ1.And it can be simplified as follows:(7)xAw=fdxXcos⁡H+Ysin⁡H+TxXsin⁡H-Ycos⁡H+Tz,yBw=fdyZ+TyXsin⁡H-Ycos⁡H+Tz.For the pointXs,Ys,Zs on the side wall, its corresponding pointxAws,yAwson the frame A of robot vision is calculated as follows: (8)zxAwsyAws1=1dx0001dy0001f000f000100-1010100cos⁡Hsin⁡H0-sin⁡Hcos⁡H0001TxTyTzXsYsZs1.And it can be simplified as(9)xAws=fdx-Zs+TxXscos⁡H+Yssin⁡H+Tz,(10)yAws=fdy-Xssin⁡H+Yscos⁡H+TyXscos⁡H+Yssin⁡H+Tz.Comparing with (7), it means that the x-axis and y-axis terms are exchanged in (9) and (10). Accordingly, x, y are exchanged, and Tx, Ty are exchanged, too. The distortion feature of front wall in the robot vision is the same as that of side wall, and the distortion revise method for the front wall would be the same as that of side wall.Take the distortion of front wall for example. Given the robot heading and movement for frameA are H, tx, ty for frame B which would be marched with frame A, its parameters are H+ΔH, tx+Δtx, and ty+Δty. According to (8), the object point X,Y,Z on frame B is xBw,yBw and is calculated as follows: (11)xBw=fdxXcos⁡H+ΔH+Ysin⁡H+ΔH+Tx+ΔtxXsin⁡H+ΔH-Ycos⁡H+ΔH+Tz,(12)yBw=fdyZ+Ty+ΔtyXsin⁡H+ΔH-Ycos⁡H+ΔH+Tz.For the ceiling and wall region in framesA and B, the deformations of their ceiling images, including rotation and translation, can be adjusted similarly through (5). However, the wall region in frame A, after rotation and translation, would be transformed differently from that of frame B: (13)xAByAB=cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHfdxXcos⁡H+Ysin⁡H+TxXsin⁡H-Ycos⁡H+TzfdyZ+TyXsin⁡H-Ycos⁡H+Tz+ΔtxΔty,where xAB,yAB is point in frame A processed by (5) and can be simplified as (14)xAB=fdxXcos⁡Hcos⁡ΔH+Ysin⁡Hcos⁡ΔH+Txcos⁡ΔH+Zsin⁡ΔH+Tysin⁡ΔHXsin⁡H-Ycos⁡H+Tz+Δtx,yAB=fdy-Xcos⁡Hsin⁡ΔH-Ysin⁡Hsin⁡ΔH+Zcos⁡ΔH-Txsin⁡ΔH+Tycos⁡ΔHXsin⁡H-Ycos⁡H+Tz+Δty.If this point is translated by an amountSx,Sy, (15)Sx=cos⁡ΔHfdx-TxXsin⁡H-Ycos⁡H+Tz+sin⁡ΔHfdx-Xsin⁡H+Ycos⁡H-Z-TyXsin⁡H-Ycos⁡H+Tz+fdxΔtxXsin⁡H-Ycos⁡H+Tz-Δtx,Sy=sin⁡ΔHfdyXcos⁡H+Ysin⁡H+TxXsin⁡H-Ycos⁡H+Tz+cos⁡ΔHfdy-Z-TyXsin⁡H-Ycos⁡H+Tz+fdyΔty+Z+TyXsin⁡H-Ycos⁡H+Tz-Δty.The transform result is(16)xAB+Sx=fdxXcos⁡H+ΔH+Ysin⁡H+ΔH+Tx+ΔtxXsin⁡H-Ycos⁡H+TzyAB+Sy=fdyZ+Ty+ΔtyXsin⁡H-Ycos⁡H+Tz.Comparing with (10) and (11), the transformed frame A is much closer to frame B than the original frame A. The similarity between frames A and B can be calculated more exactly through matching with transformed frame A compared to original frame A.But there is still some difference between transformed frameA and frame B. On one hand, their denominators are different, which are Xsin⁡H-Ycos⁡H+Tz and Xsin⁡H+ΔH-Ycos⁡H+ΔH+Tz. On the other hand, some terms in (15) are unknown (e.g., point coordinate X,Y,Z in the room space), as the terms Sx,Sy cannot be calculated through the two equations. In order to neutralize these disadvantages, overlap region extraction method and subblock matching method would be presented, and Sx,Sy can be resolved through subblock matching. The term subblock is defined as follows. An image is divided into many small blocks which are equal sized, and these blocks are named as subblock in this paper. Equation (5) would also be accomplished through overlap region extraction method designed in this paper.If framesA and B contain the same image content, their transform results would be very similar after being processed by (5) and (15) and very useful for image matching and similarity analysis. For the same ceiling regions in frames A and B, the correlation coefficient between them would be very large. For the same wall regions in two frames, as containing the same objects, the number of correct matching subblocks would be also very large. This paper would combine them together to analyze the similarity between frames A and B.


## 2.1. The Features of Robot View Angle and Movement for Ceiling and Wall Region

The camera model, which can change the three-dimensional object in the real world to two-dimensional picture, is as follows [24, 25]: (1)zxy1=1dx0001dy0001f000f0001RTXYZ1,where(2)R=cos⁡R0-sin⁡R010sin⁡R0cos⁡R·1000cos⁡Psin⁡P0-sin⁡Pcos⁡P·cos⁡Hsin⁡H0-sin⁡Hcos⁡H0001is calculated through robot view angles of roll R, pitch P, and heading H. The term T=TxTyTz is calculated through robot movements Tx and Ty and ceiling height Tz, X,Y,Z are the coordinates of an object point in three-dimensional real world, and x,y are its corresponding points in the robot vision. The terms f, dx, and dy are the constant of the camera: f is the camera focus and dx and dy are the scale factors.There are two kinds of main indoor objects: ceiling and wall regions. The ceiling is parallel to the floor, and wall regions (e.g., wall, window, door, and furniture) are perpendicular to the floor. For the upward-looking camera on the robot, the view angles for them are different.When a robot is moving on the floor, its route parallels the ceiling, the heading (givenH) is the only robot view angle can be changed, and both roll and pitch are equal to 0.For the wall region, because they are fixed on the floor, the freedom of robot view angles is also very limited. We analyze each wall separately, by giving each wall an independent coordinate (front/back wall or side wall), as shown in Figure1(b), with the X-axis perpendicular to the wall, Y-axis parallel to the wall and floor, and Z-axis perpendicular to the floor. The heading H between a wall and the robot is the only view angle which can be changed. As wall is perpendicular to floor and ceiling, it can be seen as a part of ceiling with roll or pitch of 90 deg. For the front wall (or back) of robot, the pitch is 90 deg and roll is 0, as shown in Figure 1(b). For the left wall (or right wall) on the robot, the roll is 90 deg and pitch is 0, as shown in Figure 1(b).Because of the different view angles, ceiling and wall deform differently in the robot vision. In order to match precisely, this deformation should be revised before image content matching. According to (1), it can also be deduced that robot movement Tx,Ty and object position X,Y,Z can also contribute to image distortion. Therefore, bringing the robot view angle and movement and object position into (1), the distortion models of ceiling and wall region could be established, and their distortion features can be extracted.


## 2.2. Ceiling Distortion Model and Feature Extraction

Given the coordinate origin on the ceiling,Tx and Ty show robot movement, and Tz is ceiling height. The heading between ceiling and camera is H, and roll and pitch are 0. Therefore (1) can be transformed as follows: (3)zxy1=1dx0001dy0001f000f0001cos⁡Hsin⁡H0Tx-sin⁡Hcos⁡H0Ty001TzXYZ1.It can be simplified as follows:(4)x=fdxTz+ZXcos⁡H+Ysin⁡H+Tx,y=fdyTz+Z-Xsin⁡H+Ycos⁡H+Ty.The distortion of ceiling only includes rotation and translation, and the shape of ceiling is unchanged. As rotation and translation are affine transform, they can be revised by affine transform too. Through SURF (Speed Up Robust Features), the matched feature points in framesA and B are extracted [26, 27]. Bringing these points coordinate into (5), the heading differenceΔH and movement differences Δtx and Δty between these two frames could be resolved [28]: (5)xByB=cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHxAyA+ΔtxΔty.Two frames,A and B, can be adjusted to the same robot view angles and camera shooting position after rotation and translation according toΔH, Δtx, and Δty. Their overlap regions (containing the same objects in two frames) could be extracted. The image similarity would be obtained by comparing the similarity of their overlap regions.


## 2.3. Wall Distortion Model and Feature Extraction

For the front wall (P=90, R=0) and side wall (P=0, R=90), the heading difference is 90 deg (or −90 deg), but their image distortions are the same and can be deduced as follows.Given that the robot heading isH when it is taking frame A, for a point X,Y,Z on the front wall, its corresponding point xAw,yAw on frame A of robot vision is calculated as follows: (6)zxAwyAw1=1dx0001dy0001f000f00011000010-10cos⁡Hsin⁡H0-sin⁡Hcos⁡H0001TxTyTzXYZ1.And it can be simplified as follows:(7)xAw=fdxXcos⁡H+Ysin⁡H+TxXsin⁡H-Ycos⁡H+Tz,yBw=fdyZ+TyXsin⁡H-Ycos⁡H+Tz.For the pointXs,Ys,Zs on the side wall, its corresponding pointxAws,yAwson the frame A of robot vision is calculated as follows: (8)zxAwsyAws1=1dx0001dy0001f000f000100-1010100cos⁡Hsin⁡H0-sin⁡Hcos⁡H0001TxTyTzXsYsZs1.And it can be simplified as(9)xAws=fdx-Zs+TxXscos⁡H+Yssin⁡H+Tz,(10)yAws=fdy-Xssin⁡H+Yscos⁡H+TyXscos⁡H+Yssin⁡H+Tz.Comparing with (7), it means that the x-axis and y-axis terms are exchanged in (9) and (10). Accordingly, x, y are exchanged, and Tx, Ty are exchanged, too. The distortion feature of front wall in the robot vision is the same as that of side wall, and the distortion revise method for the front wall would be the same as that of side wall.Take the distortion of front wall for example. Given the robot heading and movement for frameA are H, tx, ty for frame B which would be marched with frame A, its parameters are H+ΔH, tx+Δtx, and ty+Δty. According to (8), the object point X,Y,Z on frame B is xBw,yBw and is calculated as follows: (11)xBw=fdxXcos⁡H+ΔH+Ysin⁡H+ΔH+Tx+ΔtxXsin⁡H+ΔH-Ycos⁡H+ΔH+Tz,(12)yBw=fdyZ+Ty+ΔtyXsin⁡H+ΔH-Ycos⁡H+ΔH+Tz.For the ceiling and wall region in framesA and B, the deformations of their ceiling images, including rotation and translation, can be adjusted similarly through (5). However, the wall region in frame A, after rotation and translation, would be transformed differently from that of frame B: (13)xAByAB=cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHfdxXcos⁡H+Ysin⁡H+TxXsin⁡H-Ycos⁡H+TzfdyZ+TyXsin⁡H-Ycos⁡H+Tz+ΔtxΔty,where xAB,yAB is point in frame A processed by (5) and can be simplified as (14)xAB=fdxXcos⁡Hcos⁡ΔH+Ysin⁡Hcos⁡ΔH+Txcos⁡ΔH+Zsin⁡ΔH+Tysin⁡ΔHXsin⁡H-Ycos⁡H+Tz+Δtx,yAB=fdy-Xcos⁡Hsin⁡ΔH-Ysin⁡Hsin⁡ΔH+Zcos⁡ΔH-Txsin⁡ΔH+Tycos⁡ΔHXsin⁡H-Ycos⁡H+Tz+Δty.If this point is translated by an amountSx,Sy, (15)Sx=cos⁡ΔHfdx-TxXsin⁡H-Ycos⁡H+Tz+sin⁡ΔHfdx-Xsin⁡H+Ycos⁡H-Z-TyXsin⁡H-Ycos⁡H+Tz+fdxΔtxXsin⁡H-Ycos⁡H+Tz-Δtx,Sy=sin⁡ΔHfdyXcos⁡H+Ysin⁡H+TxXsin⁡H-Ycos⁡H+Tz+cos⁡ΔHfdy-Z-TyXsin⁡H-Ycos⁡H+Tz+fdyΔty+Z+TyXsin⁡H-Ycos⁡H+Tz-Δty.The transform result is(16)xAB+Sx=fdxXcos⁡H+ΔH+Ysin⁡H+ΔH+Tx+ΔtxXsin⁡H-Ycos⁡H+TzyAB+Sy=fdyZ+Ty+ΔtyXsin⁡H-Ycos⁡H+Tz.Comparing with (10) and (11), the transformed frame A is much closer to frame B than the original frame A. The similarity between frames A and B can be calculated more exactly through matching with transformed frame A compared to original frame A.But there is still some difference between transformed frameA and frame B. On one hand, their denominators are different, which are Xsin⁡H-Ycos⁡H+Tz and Xsin⁡H+ΔH-Ycos⁡H+ΔH+Tz. On the other hand, some terms in (15) are unknown (e.g., point coordinate X,Y,Z in the room space), as the terms Sx,Sy cannot be calculated through the two equations. In order to neutralize these disadvantages, overlap region extraction method and subblock matching method would be presented, and Sx,Sy can be resolved through subblock matching. The term subblock is defined as follows. An image is divided into many small blocks which are equal sized, and these blocks are named as subblock in this paper. Equation (5) would also be accomplished through overlap region extraction method designed in this paper.If framesA and B contain the same image content, their transform results would be very similar after being processed by (5) and (15) and very useful for image matching and similarity analysis. For the same ceiling regions in frames A and B, the correlation coefficient between them would be very large. For the same wall regions in two frames, as containing the same objects, the number of correct matching subblocks would be also very large. This paper would combine them together to analyze the similarity between frames A and B.


## 3. Match Method Design

Content-based image matching method would be designed firstly and then the keyframes global map can be established through this matching method.


### 3.1. Content-Based Image Matching through Overlap Region Extraction and Subblocks Rebuild

The content-based image matching method is designed according to the features of image distortion and consists of three parts: image overlap region extraction, overlap region rebuild through subblock matching, and, lastly, image content similarity calculating, as shown in Figure2. For frames A and B, this method would adjust the distortion of frame A similar to that of frame B and then calculate their degree of similarity. In order to adjust more exactly, ceiling points detecting method is designed to improve the accuracy of overlap region extraction, and mismatched subblocks checking method is deigned to rebuilt the overlap region more exactly.Figure 2
The image processing of content-based image matching.


#### 3.1.1. Image Overlap Region Extraction

For framesA and B, which are taken by robot at different positions, only parts of them might overlap. Content-based image matching would focus on analyzing the image similarity in this overlap region.In order to extract this overlap region, framesA and B would be adjusted to the same view angle and camera shooting position according to their matched feature points extracted through the SURF method. If all the feature points are on the ceiling, the translation Δtx, Δty, and rotation ΔH between the two frames can be calculated directly according to (5). Through rotation and translation, the same objects in frames A and B would be adjusted to the same position, and this image processing progress is shown in Figure 3. The overlap regions can be extracted effectively from these two adjusted frames.Figure 3
The image processing of rotation and translation.The image procession result is shown in Figure4. The rotation and translation of frames A and B are shown in Figures 4(c) and 4(d), and the same objects are overlapped, as shown in Figure 4(e). The overlap region mask is the pixels covered by the two image, as shown in Figure 4(f). The overlap regions in frames A and B can be extracted through this mask.Figure 4
The overlap region extraction progress. (a) FrameA, (b) Frame B, (c) the translation result, (d) the rotation result, (e) the overlap between two frames, and (f) the overlap region mask.
(a) (b) (c) (d) (e) (f)If the feature points were extracted from wall regions, they would interfere with the calculation result ofΔtx, Δty, and ΔH. In order to delete the points not on the ceiling (including wall, furniture, window, and door), this paper designs ceiling points detecting method according the feature of ceiling, which are of equal height.For the ceiling pointsa and b, given that the origin of coordinate is on the ceiling and ceiling points Z=0, according to (4), the length of their connect lines in frames A and B (for points “a” and “b” in Figures 5(a) and 5(b), their connect line is “line ab”) can be calculated as follows: (17)dA,ab=xA,a-xA,b2+yA,a-yA,b21/2=fdxTz2Xacos⁡H+Yasin⁡H+Tx,A-Xbcos⁡H+Ybsin⁡H+Tx,A2-fdyTy2-Xasin⁡H+Ybcos⁡H+Ty,A--Xasin⁡H+Ybcos⁡H+Ty,A21/2=fdxTz2Xacos⁡H+Yasin⁡H-Xbcos⁡H-Ybsin⁡H2+fdyTy2-Xasin⁡H+Ybcos⁡H+Xasin⁡H-Ybcos⁡H21/2,dB,ab=xB,a-xB,b2+yB,a-yB,b21/2=fdxTz2Xacos⁡H+ΔH+Yasin⁡H+ΔH+Tx,B-Xbcos⁡H+ΔH+Ybsin⁡H+ΔH+Tx,B2-fdyTy2-Xasin⁡H+ΔH+Ybcos⁡H+ΔH+Ty,B--Xasin⁡H+ΔH+Ybcos⁡H+ΔH+Ty,B21/2=fdxTz2Xacos⁡H+Yasin⁡H-Xbcos⁡H-Ybsin⁡H2+fdyTy2-Xasin⁡H+Ybcos⁡H+Xasin⁡H-Ybcos⁡H21/2=dA,ab,where Xa,Ya,Za and Xb,Yb,Zb are the coordinates of points a and b in the real world, xA,a,yA,a and xA,b,yA,b are the coordinates of points a and b in frame A, and xB,a,yB,a and xB,b,yB,b are the coordinates of points a and b in frame B. Tx,A,Ty,A and Tx,B,Ty,B are the robot movement for frames A and B. As points a and b are equal in height, it can be deduced by (17) that dA,ab=dB,ab and the length of connect lines of the same ceiling points in the two images are unchanged, as shown in Figure 5.Figure 5
The connect lines on the ceiling. (a) The connect lines on the original ceiling. (b) The connect lines on the ceiling after rotation and translation.
(a) (b)However, if one of the feature pointsbw is on the wall (given height is Zbw) and not on the ceiling, its height would differ from that of ceiling (Tz). In this case, the length of the connect line is (18)dA,abw=xA,a-xA,bw2+yA,a-yA,bw21/2=fdxTzXacos⁡H+Yasin⁡H+Tx,A-fdxXbwcos⁡H+Ybwsin⁡H+Tx,AXbwsin⁡H-Ybwcos⁡H+Tz2+fdyTz-Xasin⁡H+Ybwcos⁡H+Ty,A-fdyZbw+Ty,AXasin⁡H-Ybwcos⁡H+Tz1/2,(19)dB,abw=xB,a-xB,bw2+yB,a-yB,bw21/2=fdxTzXacos⁡H+ΔH+Yasin⁡H+ΔH+Tx,B-fdxXbwcos⁡H+ΔH+Ybwsin⁡H+ΔH+Tx,BXbwsin⁡H+ΔH-Ybwcos⁡H+ΔH+Tz2+fdyTz-Xasin⁡H+ΔH+Ybwcos⁡H+ΔH+Ty,B-fdyZbw+Ty,BXasin⁡H+ΔH-Ybwcos⁡H+ΔH+Tz1/2≠dA,abw,where xA,bw,yA,bw and xB,bw,yB,bw are coordinates of wall pointbwin frames A and B and dA,abw and dB,abw are the length of connect lines abw in these two frames, asΔH is in the denominator of (19), and (18) and (19) are not equal, and dA,abw≠dB,abw. Therefore, the points on the wall can be deleted effectively by comparing the length of connect lines of feature points in the two frames, and the feature points on the ceiling can be reserved. The image process is shown in the Figure 6.Figure 6
The image processing of ceiling feature point detection (red points are the feature points). (a) Original feature points in frameA, (b) ceiling points detecting result in frame A, (c) original feature points in frame B, and (d) ceiling points detecting result in frame B.
(a) (b) (c) (d)Therefore the points on the ceiling can be extracted by comparing the length of their connect lines in framesA and B. And these points can make the calculating result of (5) more exact and extracting overlap regions more effective. In the overlap regions, as rotation and translation have been completed, the difference of ceiling image between frames A and B caused by robot rotation and translation can be deleted. However, for the wall image distortion difference between these two frames, the distortion adjustment would be completed in the next section.


#### 3.1.2. Overlap Region Rebuild through Subblocks Matching

For the points on the ceiling region, it is difficult to calculate the translation resultSx,Sy of each point in the wall directly through (15), as robot cannot measure each point coordinates X,Y,Z in the room through its monocular camera. This paper presents subblocks matching method to calculate the translation value.As the distorted object in the frame is still an entity in the image, the translation valuesSx,Sy of distorted object points in a small image region are nearly equal. Therefore this region can be translated as smaller units according to the average translation value Sx-,Sy- of this region. The overlap region in frame A can be divided into many small subblocks firstly and then match the overlap region in frame B through SAD method (Sum of Absolute Difference) to get the average translation value Sx-,Sy- of each block. Therefore the distortion of overlap region in frame A can be adjusted similar to that of frame B, as shown in Figure 7.Figure 7
The overlap region rebuilding process.The SAD matching method is as follows:(20)vi,j=argi∈1,Lj∈1,L⁡min⁡∑s=1M∑t=1NBLi+s-1,j+t-1-ATs,t,where AT is one of the subblocks in the overlap region in frame A, and size is M×N, and BL is the overlap region in frame B, and size is L×D. Traversal BL, the terms i,j, which can make (20) smallest, is the most suitable rebuild position of AT in BL. This i,j is the Sx¯,Sy¯ of subblock AT. Through this method, every subblock in frame A can find its rebuild position and get its translation Sx¯,Sy¯, and the rebuild overlap region of frame A is similar to that of frame B.Considering that there might be some mismatched subblocks, which are caused by similar objects and mismatched to wrong position, this paper presents mismatched subblocks checking method to check the wrongSx¯,Sy¯.AsSx¯,Sy¯ is the average of Sx,Sy of all the points in a subblock; the performance of Sx¯,Sy¯ is very similar to that of Sx,Sy. For Sx,Sy, (15) can changed into matrix from:(21)SxSy=fXsin⁡H-Ycos⁡H+Tz1dx001dycos⁡-Hsin⁡-H-sin⁡-Hcos⁡-HYXsin⁡ΔH-fXsin⁡H-Ycos⁡H+Tz1dx001dycos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHTxZ+Ty+fXsin⁡H-Ycos⁡H+Tz1dx001dyΔtxΔty+Ty+Z-ΔtxΔty.It can be seen from (21) that the translation Sx,Sy is constituted of two parts: the projection of heading differenceΔHproduced by the first and second term and the translation produced by the third and fourth term. The core of first term is cos⁡-Hsin⁡-H-sin⁡-Hcos⁡-HYXsin⁡ΔH, and it is the function of sin⁡ΔH, which is the projection ofΔH. The core of second term is cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHTxZ+Ty, the same as the rotation part in (5); it shows frame A rotating ΔH during overlap region extraction. So the subtraction result of the first two terms in (21) can extract the projection of heading difference ΔH between frame A and B and excludes the rotation caused by overlap region extraction. The core of third term is ΔtxΔty+Ty+Z; it is the translation difference between frames A and B caused by wall object height and robot movement difference between frames A and B. For the fourth term, the same as the translation part in (5), it shows frame A translation result during overlap region extraction. So the subtraction result of the last two terms in (21) can extract the translation difference between frames A and B and exclude the translation of overlap region extraction.Therefore the wrongSx¯,Sy¯ of mismatched subblocks can be picked out according to the rotation difference and translation difference between frames A and B after overlap region extraction, as f/Xsin⁡H-Ycos⁡H+Tz1/dx001/dy is the projection ratio between real world and camera image, and X,Y,Z can be substituted by its corresponding subblock coordinate x,y. The thresholds ΔPx,ΔPy for Sx¯,Sy¯ of subblock in x,y can be calculated by affine model: (22)ΔPxΔPy=cos⁡ΔHTsin⁡ΔHT-sin⁡ΔHTcos⁡ΔHTxy+ΔxTΔyT,where ΔHT, ΔxT, and ΔyT are the thresholds of rotation difference and translation difference between frames A and B after overlap region extraction. In order to delete the wrong mismatched subblocks effectively, ΔHT, ΔxT, and ΔyT are smaller than the maximums of rotation difference and translation difference.IfS¯x,S¯y of a subblock is larger than its threshold ΔPx,ΔPy, it can be deduced that this block is mismatched and should be deleted. Through mismatched block detection, the correct content-based image matching result can be gotten. The matching result for two similar frames is shown in Figure 8, and the matching result for the dissimilar frames is shown in Figure 9. This subblock matching method can match similar frames and evaluate their similarity effectively.Figure 8
The rebuild overlap region by two similar frames. (a) The overlap region in frameA, (b) the overlap region in frame B, and (c) the rebuild overlap region in frame A.
(a) (b) (c)Figure 9
The rebuild overlap region by two dissimilar frames. (a) FrameA, (b) frame B, (c) the overlap region in frame A, and (d) the rebuild overlap region in frame A.
(a) (b) (c) (d)


#### 3.1.3. Image Content Similarity Calculating

If the content of framesA and B is similar, the number of correct matched subblocks is very great, and the correlation coefficients between rebuild overlap region in frame A and overlap region in frame B are also very large [29, 30], and the similarity Sk between two frames is the product of subblock number and correlation coefficients: (23)SAB=Nk·∑x,yCAx,y-C¯ACBx,y-C¯B∑x,yCAx,y-C¯A2·∑x,yCBx,y-C¯B2,where Nk is the number of matched subblock, CAx,y is the pixel value in rebuild overlap region in frame A, CBx,y is the pixel value in overlap region in frame B, and C¯A and C¯B are the average image pixel value.


### 3.2. Keyframes Global Map Establishing through Content-Based Image Matching

Before establishing map, robot would move in the building automatically to take a video of indoor environment through its camera firstly. And then, through this content-based image matching method, robot can extract keyframes sequence from vision video to build global map of indoor environment by itself.The first keyframe is the first frame of vision video. And the other keyframes extraction progress is as follows:Step 1.
For theNth keyframe, its similarity with subsequent 50 frames video (about 17 seconds) is calculated by the robot.Step 2.
The max similarity in the subsequent 50 frames is found out firstly, and it is correspondent to the frame whose space position is nearest to theNth keyframe. And, then, the frame whose similarity is 50% of the max similarity can be extracted as the N+1th keyframe. If all the subsequent 50 frames are larger than 50% of the max similarity, the 50th frame is the N+1th keyframe. As there is 50% similarity between the N and N+1 keyframes, they can both interval long space distance and overlap each other.Repeating Steps1 and 2 and processing all the frames of indoor environment video, keyframes sequence can be extracted, as shown in Figure 10.Figure 10
The image processing of keyframes global establishing.This global map would be established by these keyframes, and consists of two parts: keyframes sequence and the global position of each keyframe. As the keyframes can partially overlap each other, extracting the feature points in the overlap region between neighboring keyframes and bringing them into (5), the relative position relationship of these keyframes, including heading difference HN+1,N and position difference xN+1,N, yN+1,N, would be resolved. Then, bringing these relation positions into (24), the global position of each keyframe can be gotten: (24)xN+1yN+1=cos⁡HN+1,Nsin⁡HN+1,N-sin⁡HN+1,Ncos⁡HN+1,NxN+1,NyN+1,N+xNyN,where xN,yN and xN+1,yN+1 are the global position of the Nth and N+1th keyframe.Through this content-based image matching method, the space distance between each keyframe could be very large, and the number of keyframes is very less. Robot would resolve its position quickly by matching with these keyframes. In the experiment, total 1710 frames are taken by the robot during indoor environment studying, and 72 keyframes are extracted by this method.Through this global map, the robot can localize itself in real-time, and the image processing of robot localization is shown in Figure11. When robot moving in the indoor environment to render service to human, this content-based image matching method could be used to match real-time robot vision frames with the keyframes sequence in the map and find out the most similar keyframe for each robot vision frame. The same as the global map establishing progress, feature points between robot vision and this keyframe can be extracted, and their relative position can be resolved through (5). And the global position of each robot vision frame, which is also the robot global position, can be resolved through (24), the same as resolving progress of the N+1th keyframe global position.Figure 11
The image processing of robot localization.


## 3.1. Content-Based Image Matching through Overlap Region Extraction and Subblocks Rebuild

The content-based image matching method is designed according to the features of image distortion and consists of three parts: image overlap region extraction, overlap region rebuild through subblock matching, and, lastly, image content similarity calculating, as shown in Figure2. For frames A and B, this method would adjust the distortion of frame A similar to that of frame B and then calculate their degree of similarity. In order to adjust more exactly, ceiling points detecting method is designed to improve the accuracy of overlap region extraction, and mismatched subblocks checking method is deigned to rebuilt the overlap region more exactly.Figure 2
The image processing of content-based image matching.


### 3.1.1. Image Overlap Region Extraction

For framesA and B, which are taken by robot at different positions, only parts of them might overlap. Content-based image matching would focus on analyzing the image similarity in this overlap region.In order to extract this overlap region, framesA and B would be adjusted to the same view angle and camera shooting position according to their matched feature points extracted through the SURF method. If all the feature points are on the ceiling, the translation Δtx, Δty, and rotation ΔH between the two frames can be calculated directly according to (5). Through rotation and translation, the same objects in frames A and B would be adjusted to the same position, and this image processing progress is shown in Figure 3. The overlap regions can be extracted effectively from these two adjusted frames.Figure 3
The image processing of rotation and translation.The image procession result is shown in Figure4. The rotation and translation of frames A and B are shown in Figures 4(c) and 4(d), and the same objects are overlapped, as shown in Figure 4(e). The overlap region mask is the pixels covered by the two image, as shown in Figure 4(f). The overlap regions in frames A and B can be extracted through this mask.Figure 4
The overlap region extraction progress. (a) FrameA, (b) Frame B, (c) the translation result, (d) the rotation result, (e) the overlap between two frames, and (f) the overlap region mask.
(a) (b) (c) (d) (e) (f)If the feature points were extracted from wall regions, they would interfere with the calculation result ofΔtx, Δty, and ΔH. In order to delete the points not on the ceiling (including wall, furniture, window, and door), this paper designs ceiling points detecting method according the feature of ceiling, which are of equal height.For the ceiling pointsa and b, given that the origin of coordinate is on the ceiling and ceiling points Z=0, according to (4), the length of their connect lines in frames A and B (for points “a” and “b” in Figures 5(a) and 5(b), their connect line is “line ab”) can be calculated as follows: (17)dA,ab=xA,a-xA,b2+yA,a-yA,b21/2=fdxTz2Xacos⁡H+Yasin⁡H+Tx,A-Xbcos⁡H+Ybsin⁡H+Tx,A2-fdyTy2-Xasin⁡H+Ybcos⁡H+Ty,A--Xasin⁡H+Ybcos⁡H+Ty,A21/2=fdxTz2Xacos⁡H+Yasin⁡H-Xbcos⁡H-Ybsin⁡H2+fdyTy2-Xasin⁡H+Ybcos⁡H+Xasin⁡H-Ybcos⁡H21/2,dB,ab=xB,a-xB,b2+yB,a-yB,b21/2=fdxTz2Xacos⁡H+ΔH+Yasin⁡H+ΔH+Tx,B-Xbcos⁡H+ΔH+Ybsin⁡H+ΔH+Tx,B2-fdyTy2-Xasin⁡H+ΔH+Ybcos⁡H+ΔH+Ty,B--Xasin⁡H+ΔH+Ybcos⁡H+ΔH+Ty,B21/2=fdxTz2Xacos⁡H+Yasin⁡H-Xbcos⁡H-Ybsin⁡H2+fdyTy2-Xasin⁡H+Ybcos⁡H+Xasin⁡H-Ybcos⁡H21/2=dA,ab,where Xa,Ya,Za and Xb,Yb,Zb are the coordinates of points a and b in the real world, xA,a,yA,a and xA,b,yA,b are the coordinates of points a and b in frame A, and xB,a,yB,a and xB,b,yB,b are the coordinates of points a and b in frame B. Tx,A,Ty,A and Tx,B,Ty,B are the robot movement for frames A and B. As points a and b are equal in height, it can be deduced by (17) that dA,ab=dB,ab and the length of connect lines of the same ceiling points in the two images are unchanged, as shown in Figure 5.Figure 5
The connect lines on the ceiling. (a) The connect lines on the original ceiling. (b) The connect lines on the ceiling after rotation and translation.
(a) (b)However, if one of the feature pointsbw is on the wall (given height is Zbw) and not on the ceiling, its height would differ from that of ceiling (Tz). In this case, the length of the connect line is (18)dA,abw=xA,a-xA,bw2+yA,a-yA,bw21/2=fdxTzXacos⁡H+Yasin⁡H+Tx,A-fdxXbwcos⁡H+Ybwsin⁡H+Tx,AXbwsin⁡H-Ybwcos⁡H+Tz2+fdyTz-Xasin⁡H+Ybwcos⁡H+Ty,A-fdyZbw+Ty,AXasin⁡H-Ybwcos⁡H+Tz1/2,(19)dB,abw=xB,a-xB,bw2+yB,a-yB,bw21/2=fdxTzXacos⁡H+ΔH+Yasin⁡H+ΔH+Tx,B-fdxXbwcos⁡H+ΔH+Ybwsin⁡H+ΔH+Tx,BXbwsin⁡H+ΔH-Ybwcos⁡H+ΔH+Tz2+fdyTz-Xasin⁡H+ΔH+Ybwcos⁡H+ΔH+Ty,B-fdyZbw+Ty,BXasin⁡H+ΔH-Ybwcos⁡H+ΔH+Tz1/2≠dA,abw,where xA,bw,yA,bw and xB,bw,yB,bw are coordinates of wall pointbwin frames A and B and dA,abw and dB,abw are the length of connect lines abw in these two frames, asΔH is in the denominator of (19), and (18) and (19) are not equal, and dA,abw≠dB,abw. Therefore, the points on the wall can be deleted effectively by comparing the length of connect lines of feature points in the two frames, and the feature points on the ceiling can be reserved. The image process is shown in the Figure 6.Figure 6
The image processing of ceiling feature point detection (red points are the feature points). (a) Original feature points in frameA, (b) ceiling points detecting result in frame A, (c) original feature points in frame B, and (d) ceiling points detecting result in frame B.
(a) (b) (c) (d)Therefore the points on the ceiling can be extracted by comparing the length of their connect lines in framesA and B. And these points can make the calculating result of (5) more exact and extracting overlap regions more effective. In the overlap regions, as rotation and translation have been completed, the difference of ceiling image between frames A and B caused by robot rotation and translation can be deleted. However, for the wall image distortion difference between these two frames, the distortion adjustment would be completed in the next section.


### 3.1.2. Overlap Region Rebuild through Subblocks Matching

For the points on the ceiling region, it is difficult to calculate the translation resultSx,Sy of each point in the wall directly through (15), as robot cannot measure each point coordinates X,Y,Z in the room through its monocular camera. This paper presents subblocks matching method to calculate the translation value.As the distorted object in the frame is still an entity in the image, the translation valuesSx,Sy of distorted object points in a small image region are nearly equal. Therefore this region can be translated as smaller units according to the average translation value Sx-,Sy- of this region. The overlap region in frame A can be divided into many small subblocks firstly and then match the overlap region in frame B through SAD method (Sum of Absolute Difference) to get the average translation value Sx-,Sy- of each block. Therefore the distortion of overlap region in frame A can be adjusted similar to that of frame B, as shown in Figure 7.Figure 7
The overlap region rebuilding process.The SAD matching method is as follows:(20)vi,j=argi∈1,Lj∈1,L⁡min⁡∑s=1M∑t=1NBLi+s-1,j+t-1-ATs,t,where AT is one of the subblocks in the overlap region in frame A, and size is M×N, and BL is the overlap region in frame B, and size is L×D. Traversal BL, the terms i,j, which can make (20) smallest, is the most suitable rebuild position of AT in BL. This i,j is the Sx¯,Sy¯ of subblock AT. Through this method, every subblock in frame A can find its rebuild position and get its translation Sx¯,Sy¯, and the rebuild overlap region of frame A is similar to that of frame B.Considering that there might be some mismatched subblocks, which are caused by similar objects and mismatched to wrong position, this paper presents mismatched subblocks checking method to check the wrongSx¯,Sy¯.AsSx¯,Sy¯ is the average of Sx,Sy of all the points in a subblock; the performance of Sx¯,Sy¯ is very similar to that of Sx,Sy. For Sx,Sy, (15) can changed into matrix from:(21)SxSy=fXsin⁡H-Ycos⁡H+Tz1dx001dycos⁡-Hsin⁡-H-sin⁡-Hcos⁡-HYXsin⁡ΔH-fXsin⁡H-Ycos⁡H+Tz1dx001dycos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHTxZ+Ty+fXsin⁡H-Ycos⁡H+Tz1dx001dyΔtxΔty+Ty+Z-ΔtxΔty.It can be seen from (21) that the translation Sx,Sy is constituted of two parts: the projection of heading differenceΔHproduced by the first and second term and the translation produced by the third and fourth term. The core of first term is cos⁡-Hsin⁡-H-sin⁡-Hcos⁡-HYXsin⁡ΔH, and it is the function of sin⁡ΔH, which is the projection ofΔH. The core of second term is cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHTxZ+Ty, the same as the rotation part in (5); it shows frame A rotating ΔH during overlap region extraction. So the subtraction result of the first two terms in (21) can extract the projection of heading difference ΔH between frame A and B and excludes the rotation caused by overlap region extraction. The core of third term is ΔtxΔty+Ty+Z; it is the translation difference between frames A and B caused by wall object height and robot movement difference between frames A and B. For the fourth term, the same as the translation part in (5), it shows frame A translation result during overlap region extraction. So the subtraction result of the last two terms in (21) can extract the translation difference between frames A and B and exclude the translation of overlap region extraction.Therefore the wrongSx¯,Sy¯ of mismatched subblocks can be picked out according to the rotation difference and translation difference between frames A and B after overlap region extraction, as f/Xsin⁡H-Ycos⁡H+Tz1/dx001/dy is the projection ratio between real world and camera image, and X,Y,Z can be substituted by its corresponding subblock coordinate x,y. The thresholds ΔPx,ΔPy for Sx¯,Sy¯ of subblock in x,y can be calculated by affine model: (22)ΔPxΔPy=cos⁡ΔHTsin⁡ΔHT-sin⁡ΔHTcos⁡ΔHTxy+ΔxTΔyT,where ΔHT, ΔxT, and ΔyT are the thresholds of rotation difference and translation difference between frames A and B after overlap region extraction. In order to delete the wrong mismatched subblocks effectively, ΔHT, ΔxT, and ΔyT are smaller than the maximums of rotation difference and translation difference.IfS¯x,S¯y of a subblock is larger than its threshold ΔPx,ΔPy, it can be deduced that this block is mismatched and should be deleted. Through mismatched block detection, the correct content-based image matching result can be gotten. The matching result for two similar frames is shown in Figure 8, and the matching result for the dissimilar frames is shown in Figure 9. This subblock matching method can match similar frames and evaluate their similarity effectively.Figure 8
The rebuild overlap region by two similar frames. (a) The overlap region in frameA, (b) the overlap region in frame B, and (c) the rebuild overlap region in frame A.
(a) (b) (c)Figure 9
The rebuild overlap region by two dissimilar frames. (a) FrameA, (b) frame B, (c) the overlap region in frame A, and (d) the rebuild overlap region in frame A.
(a) (b) (c) (d)


### 3.1.3. Image Content Similarity Calculating

If the content of framesA and B is similar, the number of correct matched subblocks is very great, and the correlation coefficients between rebuild overlap region in frame A and overlap region in frame B are also very large [29, 30], and the similarity Sk between two frames is the product of subblock number and correlation coefficients: (23)SAB=Nk·∑x,yCAx,y-C¯ACBx,y-C¯B∑x,yCAx,y-C¯A2·∑x,yCBx,y-C¯B2,where Nk is the number of matched subblock, CAx,y is the pixel value in rebuild overlap region in frame A, CBx,y is the pixel value in overlap region in frame B, and C¯A and C¯B are the average image pixel value.


## 3.1.1. Image Overlap Region Extraction

For framesA and B, which are taken by robot at different positions, only parts of them might overlap. Content-based image matching would focus on analyzing the image similarity in this overlap region.In order to extract this overlap region, framesA and B would be adjusted to the same view angle and camera shooting position according to their matched feature points extracted through the SURF method. If all the feature points are on the ceiling, the translation Δtx, Δty, and rotation ΔH between the two frames can be calculated directly according to (5). Through rotation and translation, the same objects in frames A and B would be adjusted to the same position, and this image processing progress is shown in Figure 3. The overlap regions can be extracted effectively from these two adjusted frames.Figure 3
The image processing of rotation and translation.The image procession result is shown in Figure4. The rotation and translation of frames A and B are shown in Figures 4(c) and 4(d), and the same objects are overlapped, as shown in Figure 4(e). The overlap region mask is the pixels covered by the two image, as shown in Figure 4(f). The overlap regions in frames A and B can be extracted through this mask.Figure 4
The overlap region extraction progress. (a) FrameA, (b) Frame B, (c) the translation result, (d) the rotation result, (e) the overlap between two frames, and (f) the overlap region mask.
(a) (b) (c) (d) (e) (f)If the feature points were extracted from wall regions, they would interfere with the calculation result ofΔtx, Δty, and ΔH. In order to delete the points not on the ceiling (including wall, furniture, window, and door), this paper designs ceiling points detecting method according the feature of ceiling, which are of equal height.For the ceiling pointsa and b, given that the origin of coordinate is on the ceiling and ceiling points Z=0, according to (4), the length of their connect lines in frames A and B (for points “a” and “b” in Figures 5(a) and 5(b), their connect line is “line ab”) can be calculated as follows: (17)dA,ab=xA,a-xA,b2+yA,a-yA,b21/2=fdxTz2Xacos⁡H+Yasin⁡H+Tx,A-Xbcos⁡H+Ybsin⁡H+Tx,A2-fdyTy2-Xasin⁡H+Ybcos⁡H+Ty,A--Xasin⁡H+Ybcos⁡H+Ty,A21/2=fdxTz2Xacos⁡H+Yasin⁡H-Xbcos⁡H-Ybsin⁡H2+fdyTy2-Xasin⁡H+Ybcos⁡H+Xasin⁡H-Ybcos⁡H21/2,dB,ab=xB,a-xB,b2+yB,a-yB,b21/2=fdxTz2Xacos⁡H+ΔH+Yasin⁡H+ΔH+Tx,B-Xbcos⁡H+ΔH+Ybsin⁡H+ΔH+Tx,B2-fdyTy2-Xasin⁡H+ΔH+Ybcos⁡H+ΔH+Ty,B--Xasin⁡H+ΔH+Ybcos⁡H+ΔH+Ty,B21/2=fdxTz2Xacos⁡H+Yasin⁡H-Xbcos⁡H-Ybsin⁡H2+fdyTy2-Xasin⁡H+Ybcos⁡H+Xasin⁡H-Ybcos⁡H21/2=dA,ab,where Xa,Ya,Za and Xb,Yb,Zb are the coordinates of points a and b in the real world, xA,a,yA,a and xA,b,yA,b are the coordinates of points a and b in frame A, and xB,a,yB,a and xB,b,yB,b are the coordinates of points a and b in frame B. Tx,A,Ty,A and Tx,B,Ty,B are the robot movement for frames A and B. As points a and b are equal in height, it can be deduced by (17) that dA,ab=dB,ab and the length of connect lines of the same ceiling points in the two images are unchanged, as shown in Figure 5.Figure 5
The connect lines on the ceiling. (a) The connect lines on the original ceiling. (b) The connect lines on the ceiling after rotation and translation.
(a) (b)However, if one of the feature pointsbw is on the wall (given height is Zbw) and not on the ceiling, its height would differ from that of ceiling (Tz). In this case, the length of the connect line is (18)dA,abw=xA,a-xA,bw2+yA,a-yA,bw21/2=fdxTzXacos⁡H+Yasin⁡H+Tx,A-fdxXbwcos⁡H+Ybwsin⁡H+Tx,AXbwsin⁡H-Ybwcos⁡H+Tz2+fdyTz-Xasin⁡H+Ybwcos⁡H+Ty,A-fdyZbw+Ty,AXasin⁡H-Ybwcos⁡H+Tz1/2,(19)dB,abw=xB,a-xB,bw2+yB,a-yB,bw21/2=fdxTzXacos⁡H+ΔH+Yasin⁡H+ΔH+Tx,B-fdxXbwcos⁡H+ΔH+Ybwsin⁡H+ΔH+Tx,BXbwsin⁡H+ΔH-Ybwcos⁡H+ΔH+Tz2+fdyTz-Xasin⁡H+ΔH+Ybwcos⁡H+ΔH+Ty,B-fdyZbw+Ty,BXasin⁡H+ΔH-Ybwcos⁡H+ΔH+Tz1/2≠dA,abw,where xA,bw,yA,bw and xB,bw,yB,bw are coordinates of wall pointbwin frames A and B and dA,abw and dB,abw are the length of connect lines abw in these two frames, asΔH is in the denominator of (19), and (18) and (19) are not equal, and dA,abw≠dB,abw. Therefore, the points on the wall can be deleted effectively by comparing the length of connect lines of feature points in the two frames, and the feature points on the ceiling can be reserved. The image process is shown in the Figure 6.Figure 6
The image processing of ceiling feature point detection (red points are the feature points). (a) Original feature points in frameA, (b) ceiling points detecting result in frame A, (c) original feature points in frame B, and (d) ceiling points detecting result in frame B.
(a) (b) (c) (d)Therefore the points on the ceiling can be extracted by comparing the length of their connect lines in framesA and B. And these points can make the calculating result of (5) more exact and extracting overlap regions more effective. In the overlap regions, as rotation and translation have been completed, the difference of ceiling image between frames A and B caused by robot rotation and translation can be deleted. However, for the wall image distortion difference between these two frames, the distortion adjustment would be completed in the next section.


## 3.1.2. Overlap Region Rebuild through Subblocks Matching

For the points on the ceiling region, it is difficult to calculate the translation resultSx,Sy of each point in the wall directly through (15), as robot cannot measure each point coordinates X,Y,Z in the room through its monocular camera. This paper presents subblocks matching method to calculate the translation value.As the distorted object in the frame is still an entity in the image, the translation valuesSx,Sy of distorted object points in a small image region are nearly equal. Therefore this region can be translated as smaller units according to the average translation value Sx-,Sy- of this region. The overlap region in frame A can be divided into many small subblocks firstly and then match the overlap region in frame B through SAD method (Sum of Absolute Difference) to get the average translation value Sx-,Sy- of each block. Therefore the distortion of overlap region in frame A can be adjusted similar to that of frame B, as shown in Figure 7.Figure 7
The overlap region rebuilding process.The SAD matching method is as follows:(20)vi,j=argi∈1,Lj∈1,L⁡min⁡∑s=1M∑t=1NBLi+s-1,j+t-1-ATs,t,where AT is one of the subblocks in the overlap region in frame A, and size is M×N, and BL is the overlap region in frame B, and size is L×D. Traversal BL, the terms i,j, which can make (20) smallest, is the most suitable rebuild position of AT in BL. This i,j is the Sx¯,Sy¯ of subblock AT. Through this method, every subblock in frame A can find its rebuild position and get its translation Sx¯,Sy¯, and the rebuild overlap region of frame A is similar to that of frame B.Considering that there might be some mismatched subblocks, which are caused by similar objects and mismatched to wrong position, this paper presents mismatched subblocks checking method to check the wrongSx¯,Sy¯.AsSx¯,Sy¯ is the average of Sx,Sy of all the points in a subblock; the performance of Sx¯,Sy¯ is very similar to that of Sx,Sy. For Sx,Sy, (15) can changed into matrix from:(21)SxSy=fXsin⁡H-Ycos⁡H+Tz1dx001dycos⁡-Hsin⁡-H-sin⁡-Hcos⁡-HYXsin⁡ΔH-fXsin⁡H-Ycos⁡H+Tz1dx001dycos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHTxZ+Ty+fXsin⁡H-Ycos⁡H+Tz1dx001dyΔtxΔty+Ty+Z-ΔtxΔty.It can be seen from (21) that the translation Sx,Sy is constituted of two parts: the projection of heading differenceΔHproduced by the first and second term and the translation produced by the third and fourth term. The core of first term is cos⁡-Hsin⁡-H-sin⁡-Hcos⁡-HYXsin⁡ΔH, and it is the function of sin⁡ΔH, which is the projection ofΔH. The core of second term is cos⁡ΔHsin⁡ΔH-sin⁡ΔHcos⁡ΔHTxZ+Ty, the same as the rotation part in (5); it shows frame A rotating ΔH during overlap region extraction. So the subtraction result of the first two terms in (21) can extract the projection of heading difference ΔH between frame A and B and excludes the rotation caused by overlap region extraction. The core of third term is ΔtxΔty+Ty+Z; it is the translation difference between frames A and B caused by wall object height and robot movement difference between frames A and B. For the fourth term, the same as the translation part in (5), it shows frame A translation result during overlap region extraction. So the subtraction result of the last two terms in (21) can extract the translation difference between frames A and B and exclude the translation of overlap region extraction.Therefore the wrongSx¯,Sy¯ of mismatched subblocks can be picked out according to the rotation difference and translation difference between frames A and B after overlap region extraction, as f/Xsin⁡H-Ycos⁡H+Tz1/dx001/dy is the projection ratio between real world and camera image, and X,Y,Z can be substituted by its corresponding subblock coordinate x,y. The thresholds ΔPx,ΔPy for Sx¯,Sy¯ of subblock in x,y can be calculated by affine model: (22)ΔPxΔPy=cos⁡ΔHTsin⁡ΔHT-sin⁡ΔHTcos⁡ΔHTxy+ΔxTΔyT,where ΔHT, ΔxT, and ΔyT are the thresholds of rotation difference and translation difference between frames A and B after overlap region extraction. In order to delete the wrong mismatched subblocks effectively, ΔHT, ΔxT, and ΔyT are smaller than the maximums of rotation difference and translation difference.IfS¯x,S¯y of a subblock is larger than its threshold ΔPx,ΔPy, it can be deduced that this block is mismatched and should be deleted. Through mismatched block detection, the correct content-based image matching result can be gotten. The matching result for two similar frames is shown in Figure 8, and the matching result for the dissimilar frames is shown in Figure 9. This subblock matching method can match similar frames and evaluate their similarity effectively.Figure 8
The rebuild overlap region by two similar frames. (a) The overlap region in frameA, (b) the overlap region in frame B, and (c) the rebuild overlap region in frame A.
(a) (b) (c)Figure 9
The rebuild overlap region by two dissimilar frames. (a) FrameA, (b) frame B, (c) the overlap region in frame A, and (d) the rebuild overlap region in frame A.
(a) (b) (c) (d)


## 3.1.3. Image Content Similarity Calculating

If the content of framesA and B is similar, the number of correct matched subblocks is very great, and the correlation coefficients between rebuild overlap region in frame A and overlap region in frame B are also very large [29, 30], and the similarity Sk between two frames is the product of subblock number and correlation coefficients: (23)SAB=Nk·∑x,yCAx,y-C¯ACBx,y-C¯B∑x,yCAx,y-C¯A2·∑x,yCBx,y-C¯B2,where Nk is the number of matched subblock, CAx,y is the pixel value in rebuild overlap region in frame A, CBx,y is the pixel value in overlap region in frame B, and C¯A and C¯B are the average image pixel value.


## 3.2. Keyframes Global Map Establishing through Content-Based Image Matching

Before establishing map, robot would move in the building automatically to take a video of indoor environment through its camera firstly. And then, through this content-based image matching method, robot can extract keyframes sequence from vision video to build global map of indoor environment by itself.The first keyframe is the first frame of vision video. And the other keyframes extraction progress is as follows:Step 1.
For theNth keyframe, its similarity with subsequent 50 frames video (about 17 seconds) is calculated by the robot.Step 2.
The max similarity in the subsequent 50 frames is found out firstly, and it is correspondent to the frame whose space position is nearest to theNth keyframe. And, then, the frame whose similarity is 50% of the max similarity can be extracted as the N+1th keyframe. If all the subsequent 50 frames are larger than 50% of the max similarity, the 50th frame is the N+1th keyframe. As there is 50% similarity between the N and N+1 keyframes, they can both interval long space distance and overlap each other.Repeating Steps1 and 2 and processing all the frames of indoor environment video, keyframes sequence can be extracted, as shown in Figure 10.Figure 10
The image processing of keyframes global establishing.This global map would be established by these keyframes, and consists of two parts: keyframes sequence and the global position of each keyframe. As the keyframes can partially overlap each other, extracting the feature points in the overlap region between neighboring keyframes and bringing them into (5), the relative position relationship of these keyframes, including heading difference HN+1,N and position difference xN+1,N, yN+1,N, would be resolved. Then, bringing these relation positions into (24), the global position of each keyframe can be gotten: (24)xN+1yN+1=cos⁡HN+1,Nsin⁡HN+1,N-sin⁡HN+1,Ncos⁡HN+1,NxN+1,NyN+1,N+xNyN,where xN,yN and xN+1,yN+1 are the global position of the Nth and N+1th keyframe.Through this content-based image matching method, the space distance between each keyframe could be very large, and the number of keyframes is very less. Robot would resolve its position quickly by matching with these keyframes. In the experiment, total 1710 frames are taken by the robot during indoor environment studying, and 72 keyframes are extracted by this method.Through this global map, the robot can localize itself in real-time, and the image processing of robot localization is shown in Figure11. When robot moving in the indoor environment to render service to human, this content-based image matching method could be used to match real-time robot vision frames with the keyframes sequence in the map and find out the most similar keyframe for each robot vision frame. The same as the global map establishing progress, feature points between robot vision and this keyframe can be extracted, and their relative position can be resolved through (5). And the global position of each robot vision frame, which is also the robot global position, can be resolved through (24), the same as resolving progress of the N+1th keyframe global position.Figure 11
The image processing of robot localization.


## 4. Results of Experiments

This keyframes global map establishing method for robot localization through content-based image matching had been tested, including two parts: map building and localization in large indoor environment and the test for robot localization under kidnap condition.


### 4.1. The Experiment of Map Building and Localization in Large Indoor Environment

The experiment site is composed of two rooms (20-meter-square) and two corridors (11 m). The experiment progress is shown in Figure12. During robot indoor environment studying, a video about 9.5-minute long (1710 frames) had been taken by robot vision during robot indoor environment studying.Figure 12
The experiment site. (a) The robot moving in the experiment site. (b) The ceiling in the robot vision.
(a) (b)Total 72 keyframes (less than 5%) are extracted by our method from these video frames to build map of experiment site. Their global position resolving result is shown in Figure13. The environment of the experiment site, including ceiling and wall region (wall, window, door, and furniture), can also be described by this keyframe sequence and their global position, and the position RMSE is less than 0.3 m, as shown in Figure 14.Figure 13
The global position relationship of keyframes sequence.Figure 14
Indoor environment described by keyframes sequence.The robot can make good use of this map to localize itself in the whole building and draw its route in the different room and corridor effectively, as shown in Figure15.Figure 15
The robot route resolved through keyframes global map and content-based image matching.In order to evaluate the localization precision of this map building method, the corners of tile floor are taken as ground signs, and the air conditioning port and ceiling lamp on the ceiling are taken as ceiling signs. And the localization RMSE between robot localization result and these signs is less than 0.5 m, as shown in Table1.Table 1
Position RMSE comparison (m).
Method in this paper ORB SLAM CV-SLAM Corridor 1 (left) 0.144 0.086 0.123 Corridor 2 (right) 0.159 0.117 0.245 Room 1 (left) 0.468 2.026 0.358 Room 2 (right) 0.483 2.665 0.546Table1 also shows the comparison between our method and ORB SLAM. The algorithm architecture of our method is similar to that of ORB SLAM, but this paper uses image content matching taking place of feature points matching. Through image content matching, the robot can pick up the keyframe from global map more precisely, which is most similar to its real-time robot vision, and is seldom disturbed by similar objects in the indoor environment. As the experiment site (Figure 14) includes four parts, two corridors and two rooms, the comparison between our method and ORB SLAM is also divided into four parts, as shown in Table 1.It can be seen from Figure14 that there are many similar objects in the experiment site, and this would be a serious test for our method and ORB SLAM.When robot is moving the in the two rooms, the experiment result of our method is better than that of ORB SLAM. This is due to the fact that there are many similar objects in the two rooms, such as the air condition outlet and ceiling lamps. The feature points on these similar objects in different rooms are easy to be error matched as the same points. If ORB SLAM needs to match all keyframes in the map, the robot can easily localize itself to wrong room (the distance between the two rooms is 12 m). But our method is able to take advantage of the image of dissimilar objects in different rooms, the interference caused by similar objects can be suppressed, and robot can fix its position precisely in these rooms and less error localized.While the robot is moving in the two corridors, as when there are fewer similar objects than that of rooms and ORB, the method can extract feature points more effectively, the experiment result of ORB SLAM is better than that of our method.Table1 also shows the comparison between our method and CV-SLAM. The difference is not significant under normal condition. However, compared with CV-SLAM method on commercial equipment, our method is immune to kidnapping events, because our method can build global map of indoor environment and make good use of this map to fix robot position at any time.


### 4.2. The Test for Robot Localization under Kidnap Condition

The kidnap problem for robot self-localization can be solved effectively by our method. In order to test robot in more complex kidnap condition, two adjoining rooms (20-meter-square and 10-meter-square) and the corridor (5 m) are chosen as experiment site. Through our method, 16 frames were extracted as keyframes to build the global map of these rooms and the corridor, with the position relationship of keyframes sequence shown in Figure16. The keyframes mosaic result is shown in Figure 17. The rooms and small corridor could restrict the field of robot camera, such that the robot cannot fix its position by watching the distant landmarks. It was kidnapped and suddenly put into a far-away place. In the test, the robot was frequently taken from one place to another place (2 or 3 m apart) by experimenters to achieve kidnap. Through matching with global map, the robot was still able to fix its position effectively, especially when the robot is suddenly moved from room to the corridor, as shown in Figure 17, and position RMSE is less than 0.4 m.Figure 16
The global position relationship of keyframes sequence; “∗” is the position of each keyframe.Figure 17
The global map for kidnap test described by keyframes sequence.


## 4.1. The Experiment of Map Building and Localization in Large Indoor Environment

The experiment site is composed of two rooms (20-meter-square) and two corridors (11 m). The experiment progress is shown in Figure12. During robot indoor environment studying, a video about 9.5-minute long (1710 frames) had been taken by robot vision during robot indoor environment studying.Figure 12
The experiment site. (a) The robot moving in the experiment site. (b) The ceiling in the robot vision.
(a) (b)Total 72 keyframes (less than 5%) are extracted by our method from these video frames to build map of experiment site. Their global position resolving result is shown in Figure13. The environment of the experiment site, including ceiling and wall region (wall, window, door, and furniture), can also be described by this keyframe sequence and their global position, and the position RMSE is less than 0.3 m, as shown in Figure 14.Figure 13
The global position relationship of keyframes sequence.Figure 14
Indoor environment described by keyframes sequence.The robot can make good use of this map to localize itself in the whole building and draw its route in the different room and corridor effectively, as shown in Figure15.Figure 15
The robot route resolved through keyframes global map and content-based image matching.In order to evaluate the localization precision of this map building method, the corners of tile floor are taken as ground signs, and the air conditioning port and ceiling lamp on the ceiling are taken as ceiling signs. And the localization RMSE between robot localization result and these signs is less than 0.5 m, as shown in Table1.Table 1
Position RMSE comparison (m).
Method in this paper ORB SLAM CV-SLAM Corridor 1 (left) 0.144 0.086 0.123 Corridor 2 (right) 0.159 0.117 0.245 Room 1 (left) 0.468 2.026 0.358 Room 2 (right) 0.483 2.665 0.546Table1 also shows the comparison between our method and ORB SLAM. The algorithm architecture of our method is similar to that of ORB SLAM, but this paper uses image content matching taking place of feature points matching. Through image content matching, the robot can pick up the keyframe from global map more precisely, which is most similar to its real-time robot vision, and is seldom disturbed by similar objects in the indoor environment. As the experiment site (Figure 14) includes four parts, two corridors and two rooms, the comparison between our method and ORB SLAM is also divided into four parts, as shown in Table 1.It can be seen from Figure14 that there are many similar objects in the experiment site, and this would be a serious test for our method and ORB SLAM.When robot is moving the in the two rooms, the experiment result of our method is better than that of ORB SLAM. This is due to the fact that there are many similar objects in the two rooms, such as the air condition outlet and ceiling lamps. The feature points on these similar objects in different rooms are easy to be error matched as the same points. If ORB SLAM needs to match all keyframes in the map, the robot can easily localize itself to wrong room (the distance between the two rooms is 12 m). But our method is able to take advantage of the image of dissimilar objects in different rooms, the interference caused by similar objects can be suppressed, and robot can fix its position precisely in these rooms and less error localized.While the robot is moving in the two corridors, as when there are fewer similar objects than that of rooms and ORB, the method can extract feature points more effectively, the experiment result of ORB SLAM is better than that of our method.Table1 also shows the comparison between our method and CV-SLAM. The difference is not significant under normal condition. However, compared with CV-SLAM method on commercial equipment, our method is immune to kidnapping events, because our method can build global map of indoor environment and make good use of this map to fix robot position at any time.


## 4.2. The Test for Robot Localization under Kidnap Condition

The kidnap problem for robot self-localization can be solved effectively by our method. In order to test robot in more complex kidnap condition, two adjoining rooms (20-meter-square and 10-meter-square) and the corridor (5 m) are chosen as experiment site. Through our method, 16 frames were extracted as keyframes to build the global map of these rooms and the corridor, with the position relationship of keyframes sequence shown in Figure16. The keyframes mosaic result is shown in Figure 17. The rooms and small corridor could restrict the field of robot camera, such that the robot cannot fix its position by watching the distant landmarks. It was kidnapped and suddenly put into a far-away place. In the test, the robot was frequently taken from one place to another place (2 or 3 m apart) by experimenters to achieve kidnap. Through matching with global map, the robot was still able to fix its position effectively, especially when the robot is suddenly moved from room to the corridor, as shown in Figure 17, and position RMSE is less than 0.4 m.Figure 16
The global position relationship of keyframes sequence; “∗” is the position of each keyframe.Figure 17
The global map for kidnap test described by keyframes sequence.


## 5. Conclusion

For the issue of robot localization and mapping in the indoor environment, this paper presents keyframes global map establishing method for robot localization through content-based image matching with ability to analyze distortion and overlapping of keyframes. Results show that common problems, such as kidnapping or disturbances by similar objects, can be resolved through the content-based image matching method presented in this paper, which is specially designed for indoor environment. In the test, the keyframes global map can be established by this method and describe the indoor environment effectively. Although there are many similar objects in the experiment site, the robot cannot be kidnapped and can localize itself accurately (Figure18), with the position RMSE being less than 0.5 m.Figure 18
The kidnap experiment; eight consecutive kidnaps were executed by experimenters, and sign “o” is the localization result for each kidnap position fix by the robot after landing.



---

*Source: 1646095-2017-01-11.xml*