118 Algorithms of Landmark Robot Navigation Basing on Monocular Image Processing Vasyl Koval Department of Information Computing Systems and Control, Ternopil National Economic University, UKRAINE, Ternopil, 8 Chekhova str., email: vko@tneu.edu.ua Abstract: The application of mobile robots is very Typically, the technical vision system is used by MR during important in environments that are dangerous or navigation. There are three strategic levels for reaching target inappropriate for human life. One of the problems arising point of movement by MR and they include: a) corresponding for the mobile robot when targeting point within the indoor to the far, b) middle and d) near navigation. To be capable of application during navigation is the provision of its providing such navigational levels, it is significant to develop localization. In this paper, the developments of the some algorithms and tools that could support robot to estimate algorithms that provide and enable mobile robot to its position or localize at the operating environment. position itself within the indoor environment by using one video camera and a landmark template is presented. II. PROBLEM FORMULATION Keywords: mobile robot, robot navigation, navigation One of the core task for robot’s navigation is the algorithm, mobile robot localization, landmark- determination of the MR position and orientation (often navigation, indoor mobile robot navigation. referred to as the pose) in its environment. The basic principles of landmark-based and map-based positioning also apply to I. INTRODUCTION the vision-based positioning or localization, which relies on One of the most popular application for mobile robots (MR) optical sensors in contrast to ultrasound, dead-reckoning and is providing navigations in environments in which humans inertial sensors. can’t be present or environments that are dangerous to Most localization techniques provide absolute or relative human’s health [1,2]. The interaction of MR with the operating position and/or the orientation of sensors. Techniques vary environment is provided by the application of a number of substantially, depending on the sensors, their geometric sensors for the perception of it, actuators (effectors) for models and the representation of the environment [7,8]. influencing the environment and a control system that allows The geometric information about the environment can be robot to perform purposeful and useful actions. By analyzing given in the form of landmarks, object models and maps in two the indoor application of mobile robots, it is possible to or three dimensions. A vision sensor should capture image conclude that its activities in the environment can be features or regions that match the landmarks or maps. considered as a cyclic system. The MR positioning means finding of the position and the Within the main loop, MR executes the procedures for the orientation of a robot platform globally in the environment. perception of the environment state, process the received Usually for this purpose of various types of range, finders are information and determines actions that changes its position in used. Finders have large numbers of drawbacks, the main one the environment according to the fixed purpose. Thereafter, among them is that the finder can focus only on the MR analyze changes and the information about the new configuration of the working area and the problem of environment state obtained is send to the control system. Due localization (determining coordinates) is solved with errors. to these processes being executed, a new loop of mobile robot Moreover, the traditional navigating systems usually use activities is organized till the purpose will be reached [3]. odometers for positioning of wheeled platform in an The actual problem is the creation of mobile robots that are environment. They determine the path traversed by each of the capable of independently navigating and autonomously wheels of robot. As a result, such approach leads to performing the assigned tasks. At the same time in most cases, accumulated errors. Therefore, the practical problem is to humans provide remote control for the MR [4]. Such state is create tools and algorithms that allow mobile robot to provide determined by the inability of the robot to make independent positioning for movement to the target. decisions and as a result, it provides number of shortcomings Therefore, the ideal sensor for solving the distinct problems and increases the probability of erroneous actions. In addition, listed above is the video camera from the vision system of the it is usually problematic for people to correctly assess the robot. The proof of this statement may be human visual situation on a telemetry data basis and implementation of system. In this scientific report, the main attention focuses on adequate control. These shortcomings can be avoided if the the approaches that use photometric vision sensors, i.e., MR control by humans will be carried out at the level of goal cameras for MR positioning. setting, but not at the level of the task execution for individual In robotics, it is possible to find the implementation of stereo movements. In this case, the robot must independently (or with cameras for similar applications. Two or sometimes three minimal human impact) perform the assigned tasks. [5,6]. cameras and special image processing techniques are used to reconstruct the robot’s environment [9]. Stereo image ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 119 processing has its drawbacks. The main one among them is landmark to image. As part of the robot localization, one of the finding the correspondence between two stereo images that is practical task is the identification of landmark on the image very complicated. Moreover, the authors of these methods from the video camera. often simplify the process by creating artificial landmarks, including the usage of different kinds of structured lights, etc. At the same time, in nature there are many organisms that have successfully provided orientation in the environment by using only one video-sensor. This fact creates prerequisites for research methods for analog behavior in technical systems. To address practical issues of the task definition, we will consider some of the environment in which mobile robot operates at industry (Fig. 1) [10]. Fig.2. Geometric interpretation of the task definition Thus, the input data for the developed algorithm and software units are color RGB images obtained by the robot’s video camera. For the solution of the task that is given above, Fig.1. The operating environment of mobile robot at industry [10] the following restrictions and assumptions are considered: - a preliminary calibration of the camera was done. Due to In that environment, it is quite difficult to localize robot. the result of the video camera calibration, its position is Moreover, MR needs to determine its position independently fixed onboard of the mobile robot platform and does not for provision of the navigational goal, subsequently, to deliver change during operation; the goods or perform other necessary operations. - MR provides movement in a straight and flat horizontal Based on the above mentioned practical needs, it is surface like a floor, which practically represents a proposed that the development of algorithms and software homogeneous coating (laminate flooring, linoleum, units use one camera and image processing technique to easily construction coupler); solve the task of positioning the mobile robot in the - there are no overhanging objects that could cause a environment during the movement to the target. collision with a mobile robot in the environment; - a landmark template exist in the environment with III. IDEA OF THE PROPOSED ALGORITHM known parameters and it is visible for mobile robot; - within presented restrictions, the operating three- The idea of the Proposed Algorithm is to study and solve dimensional model of the environment that is presented problems. Let us consider the technology that is taken from on Fig. 2 is considered. nature when organisms are oriented in space through various The expected output of the algorithm is the selected segment beacons (example: the sun). For this purpose, one of the of the landmark template at the image plane, which is used to possible solution of the previously mentioned task is proposed calculate the trajectory of mobile robot movement to the target to fix a landmark on the ceiling of the technological point. environment where the mobile robot operates. In a situation Thus, to achieve this task, it is proposed to use the video wherein, the coordinates of landmark are known, there is a camera as an effective passive sensor. By using this, the mobile need for algorithms and software units of the image processing robot will provide the proper positioning in the environment that will determine the robot’s position in the environment. on the way to the target point. Thus, the following geometric interpretation is proposed to solve this task (Fig. 2). According to Fig. 2, a special situation is proposed, when on the base of the mobile robot platform the IV. GENERALIZED ALGORITHM OF MOBILE ROBOT video camera is fixed and directed vertically upward. Thus, the NAVIGATION BASED ON MONOCULAR IMAGE location of mobile robot platform determines by the position In general cases, the navigation of MR to the target is of video camera. The camera is located at some distance from provided by using image processing from one camera. The the ceiling OM (Fig. 2). Any point located on the ceiling is robot navigation consists in analyzing of the current robot projected through the center of the camera lens (point O o location and local targets that follow to global position. These Fig.2) to the sensor panel (plane ABDC on the Fig. 2). For local targets can be displayed as a line or landmarks localization of the mobile robot in the environment, the representing a sequence of intermediate links that should landmark template is fixed on the ceiling and has coordinates follow the robot. Sometimes, there is a situation wherein the known as (X2, Y2). To perform the movement of the mobile robot has only one global target to achieve. In this case, the robot to its target, it is necessary to find its location in the movement of mobile robot must be ensured, taking into environment (it is necessary to search the coordinates of points consideration the possible local obstacles or static architectural (X1, Y1) and the angle "Alfa") basing on the projections of ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 120 designs of the environment. Local movement to the target may 9. Based on the coordinates of the target and the position of be provided by one of the known methods that are based on the MR at the manipulating environment, it performs the local or global navigation [11, 18]. Within this scientific work, procedure for defining the direction of movement. the local movements of mobile robots are not considered, but 10. Providing the MR maneuvering, based on the necessary it considers the algorithm by which the robot determines its parameters of acceleration for the MR motors. As a result, position for predicting the direction of movement to the target the movement of the robot’s platform provides changes to as a subtask of robot navigation. its position in the environment (its coordinates). For simplicity in the consideration of the above presented 11. Return to step two. principles of robot navigation, let consider the robot The flowchart of generalized algorithm is given on Fig. 3. environment as grid-based model. In this environment, the coordinates of the target point are given, which represents the goal of the robot movement. The ultimate purpose of a robot navigation is to build a direction (trajectory) of movement to the global target point and to generate the control commands, which defines the required acceleration of MR wheels for maneuvering. The navigation task is completed when the robot is within a certain range with respect to the point of global goal. For the provision of the above presented way of robot navigation, unlike existing known local methods of navigation [12-15], it is proposed to take the appropriate decisions for the direction of MR movement at each step in a loop. Thus, the decision to bypass obstacles and direction taken at each iteration of a loop depends on the location of the landmark on the image of the robot’s camera. The main processes provided by mobile robot for navigation to its target can be presented by generalized algorithm and it consist of the following: 1. At the first step, there’s an execution of the image processing procedures that initialize values for algorithms and provide camera calibration procedure. 2. At the second step of the algorithm, the position of the mobile robot platform (coordinates of its center point) and the target position are determined. The vector of the length between the point of the robot’s position and the point of the target’s position is determined (the distance to the target). 3. If the position of the mobile robot is within a certain radius delta (the concrete value is specified during the Fig.3. Generalized algorithm of mobile robot navigation initialization procedure) from the target point, then it stops working and take a decision of reaching the goal of movement. In this case, the algorithm of mobile robot V. LANDMARK TEMPLATE DETECTION ON THE movement is finish. This moment represents the stop- IMAGE PLANE point for the MR navigation algorithm. During navigation, the MR estimate its location and position Otherwise, the following sequence of steps are executed: in the environment based on the landmark position. The last 4. Gathering of the video-frame from the robot’s video- one, it is possible to receive based on image processing from camera. one robot’s video-camera. It means that the orientation of the 5. It performs the segmentation of landmark template on the given landmark of the images allows determination of the image received previously from the video-frame. position of the robot’s platform and as a result it provides Thereafter, the coordinates of the central point of the smooth navigation. landmark template are calculated at the local coordinate In accordance to the list of steps presented above in the system of the image. generalized algorithm, one of the first process of robot 6. It provides calculations of the directional angle of the navigation is to capture a video frame from video camera. Mobile Robot’s position relative to the placement of Performances of these steps can take place using existing and landmark template that is segmented on the image from known possible approaches. At the same time, it is necessary the video-camera. to design the methods that can detect landmark template on 7. It is performing the procedure of calculating the distance video-image. To identify the landmark template for mobile from the position of mobile robot to the central point of robot navigation, it is proposed that algorithm is used to the landmark template. perform the following procedures (Fig. 4): 8. It Performs the procedure of the MR positioning at the manipulating environment. ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 121 The RGB-image that receives from color video camera Let consider the implementation of algorithm for landmark represents input for algorithm execution. The algorithm template detection on the image plane (Fig. 4) as the most mentioned above selects some areas of pixels on the image important part for landmark robot navigation. (image segment) that belongs to possible landmark template All the processes done were formalized mathematically for that are selected. Thereafter, it is applying the procedure of the investigation and implementation of the algorithms rejecting all other than landmark template segments by using mentioned above. Also, it was designed specific graphical the various metrics. As the result of the algorithm, the image representation of the landmark template (Fig. 6a). The shape segment of pixels that respond to landmark template is of landmark allows unique identification among other objects selected. of the image, and to determine angular orientation on the global environment map. Additionally, the three metrics for guaranteeing the selection of landmark template among the other segments on the image plane were suggested: - the number of pixels in the segment; - the distance between the most remoted pixels in the segment; - the presence and number of holes in the segment. To investigate and demonstrate algorithm, a special situation of landmark location on the ceiling of MR environment was taken (Fig. 6a). As it could be seen on the image captured by the video-camera, there exist additional object (lighting lamp). Such object could be located at the range of the camera’s vision and needs to be removed as unwished for processing. Median filter with 3x3 matrix operation were applied to each image pixel on Fig. 6a. According to the algorithm of landmark detection, the following values of thresholds were selected for red, green and blue colors: R_Tresh=75±28, G_Tresh=95±10, B_Tresh=133±10. The result of image thresholding presents Fig.4. The algorithm for landmark template detection on the image on Fig.6b. plane VI. ALGORITHM IMPLEMENTATION The above designed algorithms for robot navigation was explored by using Mat-lab software. The implementation of all processes that provide MR navigation to its target is currently a) c) d) under development. The conceptual interest of researches consists of obtaining the stable segmentation of landmark template for MR pose estimation in the environment. During researches, many navigation procedures could be implemented by the application of specific functions that are appropriate for the MR configurations individually, depending on the type of b) robot. For example, it could be possible to use ARIA environment for robots from ActivMedia Robotics Company Fig.6. Results of image processing: a) the input image; b) the results [19, 20] (Fig. 5). of thresholding in the red, green and blue spectrums; c) result of labeling of segmented image (there are 58 objects indicated by different colors); d) the result after applying metrics The initial image was binarized by combining of the segmented images on Fig.6b. During the processing of the neighbor-segmented pixels at the initial image, 58 segments were selected as candidates to be landmark template for MR navigation (Fig.6c). Thereafter the following values were experimentally selected for proposed metrics: the number of pixels in the segment (2200-3120); the distance between the most remoted pixels in the segment (150±10); the presence and number of holes in the segment (3 holes). The result of applying mentioned metrics in the proposed Fig.5. One video-camera application for navigation of mobile robot algorithm of detecting the landmark template on the image is Pioneer P3-DX (potential application) [21] shown on Fig.6d. As it was expected, only one segment among ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 122 the plurality of image objects were selected. It includes 2436 Tracking Using Geometric Constraints”, Robotics and pixels and three holes. The distance between the most remoted Autonomous Systems 44, 2003, pp. 21-53. points is 147. [8] Betke Margrit, Gurvits Leonid “Mobile robot localization Experimental studies have shown the usage of a sufficient using landmarks”, IEEE Transaction on robotics and metric for identifying landmark template at 200 different automation, Vol 13, No. 2, April 1997, pp.251-263. locations at the environment. [9] H. Roth, A. Sachenko, V. Koval, O. Adamiv, V. Kapura, The actual representation of the algorithm scenarios will be "Evaluation of Camera Calibration Methods for Computer demonstrated during the presentation. Vision System of Autonomous Mobile Robot”, Proceedings of International Conference "Modern VII. SUMMARY AND CONCLUSION Information and Electronic Technologies” (MIET-2009), In this paper, algorithms of mobile robot movements were Odessa (Ukraine), 2009, p. 29. developed and experimentally investigated by using a one [10] “Are Robots About to Take Over E-commerce video camera. This practical task was reached by applying Warehouses?”, 2018, http://www.airindknows.com/are- localization techniques using landmark template detection. robots-about-to-take-over-e-commerce-warehouses/. The generalized algorithm that allows mobile robot to move [11] Jian, Y., “Comparison of Optimal Solutions to Real time to the target was developed based on reading from one video Path Planning for a Mobile Vehicle “, by Y. Jian, Q. camera and image processing procedures. Zhihua, W. Jing, C. Kevin, IEEE Transactions on Systems, The graphic template of landmark was designed, which Man and Cybernetics, Part A, System and Humans, Vol. allows the MR to identify its position as the image among other 40, 2010, pp. 721–725. objects and allows it to determine angular orientation on a [12] Ersson T., Hu X., “Path Planning and Navigation of global environment of mobile robot. Mobile Robots in Unknown Environments”, IEEE Journ. The algorithm for landmark template segmentation was of Robotics and Automation,.# 6, 2010, pp. 212–228. designed based on the image processing that allows the MR to [13] J.L. Guzmán, M. Berenguel, F. Rodríguez, and S. identify its position on the image plane. By knowledge of the Dormido, “MRIT: Mobile Robotics Interactive Tool” position of landmark template in the environment, it is possible [electronic resource], 2018, http://aer.ual.es/mrit/. to localize mobile robot. [14] O. Adamiv, V. Koval, V. Dorosh, G. Sapozhnyk, V. The experimental studies of the proposed algorithm of Kapura, "Mobile Robot Navigation Method for landmark template detection on the video images have shown Environment with Dynamical Obstacles”, Proceedings of the stability on each algorithm step and provided a selection of the IEEE Fifth International Workshop on Intelligent Data one segment among the plurality of image objects. Acquisition and Advanced Computing Systems: Technology and Applications, 21-23 September 2009, REFERENCES Rende (Cosenza), Italy, pp. 515-518. [1] Robla-Gómez S., Becerra V., “Working Together. A [15] Chernonozhkyn, V.A., “Local Area Navigating System Review on Safe Human-Robot Collaboration in Industrial for ground mobile robots”, Scientific and Technical Environments”, IEEE Access (Vol. 5), November 14, Journal YTMO St. Petersburg State University, 2008, 2017, pp. 26754–26773. №57, pp. 13-22. [2] Baudoin Y., Habib M., “Using Robots in Hazardous [16] Oleh Adamiv, Vasyl Koval, Arunas Lipnickas, Viktor Environments”, 1st Edition, Woodhead Publishing, 2010, Kapura, “Local navigation method for improvement of P. 692. mobile robot movement”, Proceedings of the 3rd [3] Evans, J., PatrUn, P., Smith, B., Lane, D.M., “Design and International Conference Mechatronic Systems and Evaluation of a Reactive and Deliberative Collision Materials (MSM 2007), Kaunas (Lithuania), 2007, pp. Avoidance and Escape Architecture for Autonomous 245- 246. Robots”, Autonomous Robot Vol. 24, 2008, pp. 247–266. [17] William Benn and Stanislao Lauria, “Robot Navigation [4] Goebel S, Jubeh R, Raesch S-L & Zuendorf. A. “Using Control Based on Monocular Images: An Image the Android Platform to control Robots”, In Proceedings Processing Algorithm for Obstacle Avoidance of 2nd International Conference on Robotics in Education Decisions”, Hindawi Publishing Corporation (RiE 2011). Vienna, Austria, September 2011, pp. 135- Mathematical Problems in Engineering, Volume 2012, 142. P.14. [5] Siegwart, Roland, Nourbakhsh, Illah Reza, “Introduction [18] Olivier Koch, Matthew R. Walter. “Ground Robot to Autonomous Mobile Robots (Intelligent Robotics and Navigation using Uncalibrated Cameras”, In Proc. IEEE Autonomous Agents series)” / Siegwart, Roland, International Conference on Robotics and Automation Nourbakhsh, Illah Reza, Scaramuzza, MIT Press; 2nd (ICRA), May 2010, pp. 2423-2430. Revised edition, 2011, P.453 [19] Adept Mobile robots, 2014,: http://www.activmedia.com/. [6] Siciliano Bruno, Khatib Oussama “Springer handbook of [20] “AmigoBot Operations Manual, revision 4.3”, 2018, robotics”, Springer International Publishing, 2016, P. http://robots.mobilerobots.com/wiki/Manuals. 2227. [21] “Mobile robotics platforms”, 2018, [7] Arras, K.O., Castellanos, J.A., Schilt, M., Siegwart, R., https://raweb.inria.fr/rapportsactivite/RA2015/lagadic/ui “Feature-based Multi-hypothesis Localization and d51.html. ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic