Apparatus and method for estimating position and orientation of mobile robot

0001The present invention relates to a mobile robot, and more particularly, to an apparatus and method for estimating the position and orientation of a mobile robot in dark environment or an environment with a severe change of illumination conditions.

0002There are generally four methods of estimating the position and orientation of a mobile robot by using artificial beacons. The first method uses reflecting objects and a vision system. An example of this method is disclosed in <patcit id="pcit0001" dnum="US5051906A"><text>U.S. Pat. No. 5,051,906</text></patcit>, wherein an automatic guided vehicle (AGV) travels along a hallway using retro-reflective stripes attached to the ceiling. The orientation and position of the AGV is determined when the AGV travels along a long axis of the hallway. The second method uses only reflectors. Examples of this method are disclosed in <patcit id="pcit0002" dnum="US5812267A"><text>U.S. Pat. No. 5,812,267</text></patcit> and <patcit id="pcit0003" dnum="US5467273A"><text>U.S. Pat. No. 5,467,273</text></patcit>. The third method uses a vision system and specific marks instead of reflectors. Examples of this method are disclosed in <patcit id="pcit0004" dnum="US5525883A"><text>U.S. Pat. No. 5,525,883</text></patcit>, <patcit id="pcit0005" dnum="US5911767A"><text>U.S. Pat. No. 5,911,767</text></patcit>, and <patcit id="pcit0006" dnum="US6496754B"><text>U.S. Pat. No. 6,496,754</text></patcit>. In <patcit id="pcit0007" dnum="US5911767A"><text>U.S. Pat. No. 5,911,767</text></patcit>, a mobile robot is localized by setting circles as coded signs and recognizing the coded signs. In particular, the robot's position and orientation are obtained using a ratio of two diameters of two concentric circles related to the coded signs discriminated from the environment. In <patcit id="pcit0008" dnum="US6496754B"><text>U.S. Pat. No. 6,496,754</text></patcit>, a location of a robot is detected using a base mark including two marks, and a shape of an obstacle is recognized using a laser beam. The fourth method uses a vision system and a light source instead of reflectors. An example of this method is disclosed in <patcit id="pcit0009" dnum="US4797557A"><text>U.S. Pat. No. 4,797,557</text></patcit>.

0003However, in the conventional methods described above, it is impossible to estimate the global position and orientation of a mobile robot in an entire environment wherein the mobile robot moves, and the accuracy of estimating the position and orientation varies according to a change of illumination condition. Accordingly, it is difficult to use the conventional methods in a general indoor environment such as a house.

0004Unites States Patent Number <patcit id="pcit0010" dnum="US4817000A"><text>4,817,000</text></patcit> presents an automatic guided vehicle system having an optical navigation section for determining vehicle position and bearing by scanning beacons distributed within a zone of travel of the vehicle.

0005According to an aspect of the present invention, there is provided a method of estimating a position and an orientation of a mobile robot according to claim 1. The method includes: (a) obtaining a ceiling image of a place in which the mobile robot travels; (b) detecting a retro-reflective artificial mark from the ceiling image, the retro-reflective artificial mark comprising a first mark and a second mark, each including a non-reflective portion and an infrared reflective portion; and (c) estimating a position and an orientation of the robot using a position of the artificial mark or encoder information according to whether detection of the artificial mark has succeeded or not. The artificial mark includes a first mark and a second mark composed of a non-reflective portion and an infrared reflective portion, respectively.

0006According to another aspect of the present invention, there is provided an apparatus for estimating a position and an orientation of a mobile robot according to claim 7. The apparatus includes: a ceiling image grabber adapted to obtain a ceiling image of a place in which the mobile robot travels; a mark detector adapted to detect a retro-reflective artificial mark from the ceiling image; and a position &amp; orientation estimator adapted to estimate a position and an orientation of the robot using a position of the artificial mark or encoder information according to whether detection of the artificial mark has succeeded or not. The artificial mark includes a first mark and a second mark composed of a non-reflective portion and an infrared reflective portion, respectively.

0007The present invention thus provides an apparatus and method for estimating a position and an orientation of a mobile robot in dark environment or an environment with a severe change of illumination conditions.

0008The present invention also provides a mobile robot employing the above method and apparatus.

0009According to another aspect of the present invention, there is provided a computer readable medium having recorded thereon a computer readable program for performing the method of the invention.

0010The above and other features and advantages of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIGS. 1A, 1B and 1C</figref> are examples of an artificial mark used in an embodiment of the present invention;</li><li><figref idref="f0002">FIG. 2</figref> is a block diagram of an apparatus for estimating a position and an orientation of a mobile robot according to an embodiment of the present invention;</li><li><figref idref="f0003">FIG. 3</figref> is a flowchart illustrating a method of estimating a position and an orientation of a mobile robot according to an embodiment of the present invention;</li><li><figref idref="f0004">FIG. 4</figref> is a flowchart illustrating operation 333 of <figref idref="f0003">FIG. 3</figref>;</li><li><figref idref="f0005">FIG. 5</figref> is a flowchart illustrating operation 342 of <figref idref="f0003">FIG. 3</figref>;</li><li><figref idref="f0006">FIGS. 6A and 6B</figref> are a ceiling image photographed in the daytime and a reverse ceiling image photographed in the nighttime;</li><li><figref idref="f0007">FIGS. 7A and 7B</figref> are ceiling images before and after compensating for an image distortion is performed;</li><li><figref idref="f0008">FIGS. 8A through 8C</figref> are ceiling images before and after a modeling procedure using an optical center is performed in a distortion compensation processing method;</li><li><figref idref="f0009">FIGS. 9A through 9C</figref> are ceiling images before and after an interpolating procedure is performed in a distortion compensation processing method;</li><li><figref idref="f0010">FIG. 10</figref> shows ceiling images before and after a pre-processing procedure is performed; and</li><li><figref idref="f0011">FIGS. 11A and 11B</figref> illustrate a method of calculating a position of a mobile robot from a position of a detected artificial mark.</li></ul>

0011Hereinafter, the present invention will now be described more fully with reference to the accompanying drawings, in which embodiments of the invention are shown.

0012<figref idref="f0001">FIG. 1A</figref> is an example of an artificial mark 100 used in an embodiment of the present invention. The artificial mark 100 includes a first retro-reflective mark 110 and a second retro-reflective mark 120. An outer portion 111 of the first mark 110 and an inner portion 123 of the second mark 120 are non-reflective portions covered with an arbitrary color, for example, a black color, and an inner portion 113 of the first mark 110 and an outer portion 121 of the second mark 120 are infrared reflective portions. In an embodiment of the present invention, the artificial mark is located near the center of a ceiling of a place in which a mobile robot travels to perform a predetermined work, but not limited thereto. Also, the first and second marks 110 and 120 have an 11 cm outside diameter and a 7 cm inside diameter, and a distance between the first mark 110 and the second mark 120 is preferably 70 cm, but not limited thereto. In an embodiment of the present invention, the first and second marks 110 and 120 are composed of circles apart from each other at a predetermined distance, but not limited thereto.

0013When the artificial mark 110 having the pattern as shown in <figref idref="f0001">FIG. 1A</figref> is used during the daytime, the artificial mark 110 is composed of the outer portion 111 of the first mark 110 and the inner portion 123 of the second mark 120 as shown in <figref idref="f0001">FIG. 1B</figref>. During the nighttime, the artificial mark 110 is composed of the inner portion 113 of the first mark 110 and the outer portion 121 of the second mark 120 as shown in <figref idref="f0001">FIG. 1C</figref>.

0014<figref idref="f0002">FIG. 2</figref> is a block diagram of an apparatus for estimating a position and an orientation of a mobile robot according to an embodiment of the present invention. Referring to <figref idref="f0002">FIG. 2</figref>, the apparatus includes a ceiling image grabber 210, an image lightness comparator 220, an image processor 230, a mark detector 240, an encoder information capturer 250, a position &amp; orientation estimator 260, a light controller 270, and a travel controller 280.

0015The ceiling image grabber 210 may be implemented by a wide-angle lens or a super-wide-angle lens such as a fisheye lens, and obtains a ceiling image of a place in which the mobile robot travels to perform a predetermined work.

0016The image lightness comparator 220 calculates an average intensity of the ceiling image by dividing a value of summing intensity of every pixels of the ceiling image by the number of all pixels, compares the calculated average intensity to a predetermined reference value, and determines whether a light of a current environment is dark or bright. Here, the reference value is, for example, set to 50 in the case of a 256-gray-scale, and it is determined that the light is bright when the average intensity is more than 50 and the light is dark when the average intensity is less than 50.

0017The image processor 230 does not perform if it is determined that the light is bright and reverses the ceiling image if it is determined that the light is dark, as a result of image lightness comparison performed by the image lightness comparator 220. <figref idref="f0006">FIG. 6A</figref> shows a ceiling image including an artificial mark photographed in the daytime, and <figref idref="f0006">FIG. 6B</figref> shows a reverse ceiling image of a ceiling image including an artificial mark 613 or 615 photographed in the nighttime.

0018The image processor 230 performs at least one of distortion compensation processing and pre-processing procedures on a non-processed or reversed image. Technology with respect to the distortion compensation processing is described in "<nplcit id="ncit0001" npl-type="b"><text>Camera Calibration: Three Dimensional Computer Vision" (Oliver Faugeras, MIT Press, 1993</text></nplcit>). This technology will now be described in detail with reference to <figref idref="f0007 f0008 f0009">FIGS. 7A through 9C</figref>.

0019<figref idref="f0007">FIG. 7A</figref> is a ceiling image before a distortion compensation processing procedure is performed, and <figref idref="f0007">FIG. 7B</figref> is the ceiling image after a distortion compensation processing procedure is performed. If an angle of a camera lens used for the ceiling image grabber 210 is getting wider, distortion of the ceiling image is getting severer. Accordingly, since the ceiling image is differently shown from an actual image, a distortion compensation processing procedure is necessary. In detail, a method of performing a modeling procedure by extracting an optical center 811 and using two ellipses 813 composed of the first and second marks 110 and 120 based on the optical center 811 as shown in <figref idref="f0008">FIG. 8A</figref> may be used. When the distortion compensation processing procedure is performed according to this method, if an error is generated when extracting the optical center 811, a slant image is obtained as shown in <figref idref="f0008">FIG. 8B</figref>, and if the optical center 811 is exactly extracted, a well compensated image is obtained as shown in <figref idref="f0008">FIG. 8C</figref>. Here, the optical center 811 is used to obtain a normal view of the ceiling and means a point through which all lights input to a camera pass and is projected on an image pickup device of the camera. A position of the optical center 811 is not changed even if the camera is rotated. When the modeling procedure is performed, a region 911 in which pixels disappear is generated as shown in <figref idref="f0009">FIG. 9A</figref>. The pixels that disappeared can be restored by an interpolation method. Here, a value of a pixel located in a nearest position to a pixel that disappeared according to a nearest neighbor method (N.N. method) is used as it is as shown in <figref idref="f0009">FIG. 9B</figref>, or a value obtained by averaging values of pixels near to a pixel to be interpolated is used as shown in <figref idref="f0009">FIG. 9C</figref>.

0020The image processor 230 performs a pre-processing procedure of the ceiling image for which the distortion compensation processing procedure is performed. In <figref idref="f0010">FIG. 10</figref>, a reference number 1010 shows the ceiling image before the pre-processing procedure is performed, and a reference number 1030 shows the ceiling image after the pre-processing procedure is performed. In a pre-processing method, contrast and/or exposure are adjusted using a predetermined constant α and a contrast characteristic graph G1. That is, when the exposure is adjusted by multiplying each pixel of the ceiling image by the constant α, and when the contrast is adjusted so that a dark portion becomes as it is or darker and a bright portion becomes brighter by applying the contrast characteristic graph G1 to the exposure-adjusted ceiling image, resolution of a specific pixel region, i.e., a pixel region including the first and second marks 110 and 120 of the artificial mark 100, is getting higher. However, resolution of the other pixel regions is relatively lower. A following image processing such as a mark detection can be easily performed by making lightness of the artificial mark 100 largely different from a surrounding environment as a pre-processing result.

0021The mark detector 240 detects a mark candidate point from the ceiling image distortion-compensation-processed and pre-processed by the image processor 230 and detects a position of the artificial mark 100 by filtering the mark candidate points.

0022The encoder information capturer 250 obtains information of a position and an orientation of the mobile robot from an encoder sensor (not shown) attached to a wheel of the mobile robot.

0023The position &amp; orientation estimator 260 estimates the position and the orientation of the mobile robot using the position of the artificial mark 100 detected by the mark detector 240 or the information provided by the encoder information capturer 250. That is, when the mark detector 240 has succeeded to positionally detect the artificial mark 100, the position of the artificial mark 100 is used to estimate the position and the orientation of the mobile robot, and when the mark detector 240 has failed to positionally detect the artificial mark 100, the position and orientation of the mobile robot is estimated using the encoder information.

0024If it is determined that outside light is in a dark state as a result of determination of the image lightness comparator 220, the light controller 270 turns on a light device (not shown) attached to the mobile robot or up a lightness of the light device, and if it is determined that outside light is in a bright state as a result of determination of the image lightness comparator 220, the light controller 270 turns off the light device attached to the mobile robot or reduces the lightness of the light device.

0025The motion controller 280 controls the mobile robot to travel along a pre-set or planned path using the position and orientation information of the mobile robot obtained by the position &amp; orientation estimator 260.

0026<figref idref="f0003">FIG. 3</figref> is a flowchart illustrating a method of estimating a position and an orientation of a mobile robot according to an embodiment of the present invention.

0027Referring to <figref idref="f0003">FIG. 3</figref>, a ceiling image of a place in which a mobile robot travels is obtained using a wide-angle or super wide-angle camera in operation 310.

0028A light state of a current environment is determined in operation 320. To do this, an average intensity of the ceiling image obtained in operation 310 is calculated in operation 321. It is determined whether the light is in a dark state or a bright state by comparing the calculated average intensity to a predetermined reference value in operation 322. That is, it is determined that the light is in the bright state if the average intensity is larger than the reference value, and the light is in the dark state if the average intensity is smaller than the reference value. When it is determined that the light is in the dark state, the ceiling image is reversed in operation 323.

0029An artificial mark is detected from the ceiling image in operation 330: To do this, it is determined whether a stored region-of-interest exists in operation 331. As a result of the determination, if the region-of-interest does not exist, the region-of-interest is set to an entire region of the ceiling image in operation 332, and the artificial mark is detected from the entire region of the ceiling image in operation 333. If the region-of-interest exists, the artificial mark is detected from the stored region-of-interest in operation 333.

0030A position and an orientation of the mobile robot are estimated according to a result of the artificial mark detection in operation 340. To do this, it is determined whether the artificial mark has been detected in operation 341. If the artificial mark has not been detected as a determination result in operation 341, the position and the orientation of the mobile robot are calculated using information provided from an encoder sensor in operation 342. If the artificial mark has been detected as a determination result in operation 341, the position and orientation of the mobile robot are calculated using the artificial mark in operation 343. A method of calculating the position and orientation of the mobile robot using the artificial mark will now be described with reference to <figref idref="f0011">FIGS. 11A and 11B</figref>.

0031Referring to <figref idref="f0011">FIG. 11A</figref>, d indicates a distance between the first mark 110 and the second mark 120, θ indicates an angle between a line obtained by expanding a center Lc of the artificial mark 100 toward the x-axis and a line connecting the first mark 110 and the second mark 120, that is, a slope angle of the artificial mark 100 against the x-axis, and Rp indicates a current position of the mobile robot.

0032A position and an orientation of the mobile robot can be estimated by performing shift, rotation, and flip processes with respect to the position of the artificial mark 100. Accordingly, the current position of the mobile robot in <figref idref="f0011">FIG. 11B</figref> is given by Equation 1.<maths id="math0001" num="[Equation 1]"><math display="block"><mrow><mfenced open="[" close="]"><mtable><mtr><mtd><mi>x</mi><mrow><mi>ʹ</mi></mrow></mtd></mtr><mtr><mtd><mi>y</mi><mrow><mrow><mi>ʹ</mi></mrow></mrow></mtd></mtr><mtr><mtd><mn>1</mn></mtd></mtr></mtable></mfenced><mo>=</mo><msub><mi>H</mi><mi mathvariant="italic">scale</mi></msub><mspace width="1em" /><msub><mi>H</mi><mi mathvariant="italic">flip</mi></msub><mo>⁢</mo><msub><mi>H</mi><mi mathvariant="italic">rotation</mi></msub><mo>⁢</mo><msub><mi>H</mi><mi mathvariant="italic">shift</mi></msub><mfenced open="[" close="]"><mtable><mtr><mtd><mi>x</mi></mtd></mtr><mtr><mtd><mi>y</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mrow></math><img file="EP1517210B1_D0001.tif" /></maths>

0033Here,<maths id="math0002" num=""><math display="inline"><mrow><mfenced open="[" close="]"><mtable><mtr><mtd><mi>x</mi><mrow><mi>ʹ</mi></mrow></mtd></mtr><mtr><mtd><mi>y</mi><mrow><mrow><mi>ʹ</mi></mrow></mrow></mtd></mtr><mtr><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mrow></math><img file="EP1517210B1_D0002.tif" /></maths> indicates a world coordinate point, and<maths id="math0003" num=""><math display="inline"><mrow><mfenced open="[" close="]"><mtable><mtr><mtd><mi>x</mi></mtd></mtr><mtr><mtd><mi>y</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mrow></math><img file="EP1517210B1_D0003.tif" /></maths> indicates a coordinate point of the mobile robot in a camera image.

0034The conversion functions H_shift, H_rotation, H_flip, and H_scale of Equation 1 can be represented as shown in Equation 2.<maths id="math0004" num="[Equation 2]"><math display="block"><mrow><mtable columnalign="left"><mtr><mtd><msub><mi>H</mi><mi mathvariant="italic">shift</mi></msub><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><msub><mi>t</mi><mi>x</mi></msub></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><msub><mi>t</mi><mi>y</mi></msub></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mtd></mtr><mtr><mtd><msub><mi>H</mi><mi mathvariant="italic">rotation</mi></msub><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mi mathvariant="normal">cos θ</mi></mtd><mtd><mo>-</mo><mi mathvariant="normal">sin θ</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mi mathvariant="normal">sin θ</mi></mtd><mtd><mi mathvariant="normal">cos θ</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mtd></mtr><mtr><mtd><msub><mi>H</mi><mi mathvariant="italic">flip</mi></msub><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mo>-</mo><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mtd></mtr><mtr><mtd><msub><mi>H</mi><mi mathvariant="italic">scale</mi></msub><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mi>s</mi></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>s</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></mtd></mtr></mtable></mrow></math><img file="EP1517210B1_D0004.tif" /></maths>

0035Here, (t_x, t_y) indicates a coordinate point of the center Lc of the artificial mark 100, θ indicates a slope angle of the artificial mark 100, and s indicates a value obtained by dividing an actual physical distance of the artificial mark 100 by an image distance of the artificial mark 100.

0036Traveling of the mobile robot is controlled by using the calculated position and orientation of the mobile robot in operation 344.

0037<figref idref="f0004">FIG. 4</figref> is a flowchart illustrating operation 333 of <figref idref="f0003">FIG. 3</figref>.

0038Referring to <figref idref="f0004">FIG. 4</figref>, a distortion compensation processing procedure as described using <figref idref="f0007">FIGS. 7A and 7B</figref>, <figref idref="f0008">8A through 8C</figref> and <figref idref="f0009">9A through 9C</figref> is performed with respect to the obtained ceiling image in operation 411. A pre-processing procedure as described in <figref idref="f0010">FIG. 10</figref> is performed with respect to the distortion-compensation-processed ceiling image in operation 412.

0039In operation 413, an intensity value of each pixel of the pre-processed ceiling image is compared to a predetermined reference value, and binarization is performed by applying "1" to a value of the pixel if the intensity value is larger than the reference value and applying "0" to the value of the pixel if the intensity value is smaller than the reference value. Contour matching is performed with respect to the binarized ceiling image in operation 414. A contour matching method of detecting a contour of a region separated by an artificial mark and comparing the contour to a contour of a stored artificial mark is described in "<nplcit id="ncit0002" npl-type="s"><text>Visual Pattern Recognition by Moment Invariants" (M. Hu. IRE Transactions on Information Theory, 8:2, pp. 179-187, 1962</text></nplcit>).

0040Candidate regions are extracted from the ceiling image using geometrical information of the artificial mark 100 in operation 415. Reliability values of the candidate regions are calculated by performing template matching with respect to the candidate regions in operation 416. A template matching method using normalized correlations is described in "<nplcit id="ncit0003" npl-type="s"><text>Digital Image Processing" (Rafael C. Gonzalez, Richard E. Woods, pp. 583-586, 1992</text></nplcit>). A reliability value (γ(s, t)) calculated by the template matching can be represented as shown in Equation 3.<maths id="math0005" num="[Equation 3]"><math display="block"><mrow><mi>γ</mi><mfenced separators=","><mi>s</mi><mi>t</mi></mfenced><mo>=</mo><mfrac><mrow><mstyle displaystyle="false"><mrow><mstyle displaystyle="true"><mrow><munder><mo>∑</mo><mrow><mi>x</mi></mrow></munder></mrow></mstyle><mrow><mstyle displaystyle="true"><mrow><munder><mo>∑</mo><mrow><mi>y</mi></mrow></munder></mrow></mstyle></mrow><mrow><mo>⌊</mo><mi>f</mi><mfenced separators=","><mi>x</mi><mi>y</mi></mfenced><mo>-</mo><mover><mrow><mi>f</mi></mrow><mrow><mo>‾</mo></mrow></mover><mfenced separators=","><mi>x</mi><mi>y</mi></mfenced><mo>⌋</mo></mrow><mrow><mo>⌊</mo><mi>w</mi><mo>⁢</mo><mfenced separators=""><mi>x</mi><mo>-</mo><mi>s</mi><mo>,</mo><mi>y</mi><mo>-</mo><mi>t</mi></mfenced><mo>-</mo><mover><mrow><mi>w</mi></mrow><mrow><mo>‾</mo></mrow></mover><mo>⌋</mo></mrow></mrow></mstyle></mrow><mrow><mfenced open="{" close="}"><mstyle displaystyle="false"><mrow><mstyle displaystyle="true"><mrow><munder><mo>∑</mo><mrow><mi>x</mi></mrow></munder></mrow></mstyle><mrow><mstyle displaystyle="true"><mrow><munder><mo>∑</mo><mrow><mi>y</mi></mrow></munder></mrow></mstyle></mrow><msup><mfenced open="[" close="]" separators=""><mi>f</mi><mfenced separators=","><mi>x</mi><mi>y</mi></mfenced><mo>-</mo><mover><mrow><mi>f</mi></mrow><mrow><mo>‾</mo></mrow></mover><mfenced separators=","><mi>x</mi><mi>y</mi></mfenced></mfenced><mrow><mn>2</mn></mrow></msup><mstyle displaystyle="true"><mrow><munder><mo>∑</mo><mrow><mi>x</mi></mrow></munder></mrow></mstyle><mrow><mstyle displaystyle="true"><mrow><munder><mo>∑</mo><mrow><mi>y</mi></mrow></munder></mrow></mstyle></mrow><msup><mfenced open="[" close="]" separators=""><mi>w</mi><mo>⁢</mo><mfenced separators=""><mi>x</mi><mo>-</mo><mi>s</mi><mo>,</mo><mi>y</mi><mo>-</mo><mi>t</mi></mfenced><mo>-</mo><mover><mrow><mi>w</mi></mrow><mrow><mo>‾</mo></mrow></mover></mfenced><mrow><mn>2</mn></mrow></msup></mrow></mstyle></mfenced></mrow></mfrac></mrow></math><img file="EP1517210B1_D0005.tif" /></maths>

0041Here, f indicates an input candidate region, <maths id="math0006" num=""><math display="inline"><mrow><mover><mrow><mi>f</mi></mrow><mrow><mo>‾</mo></mrow></mover></mrow></math><img file="EP1517210B1_D0006.tif" /></maths> indicates an average value of pixels included in the candidate region f(x, y) in a region matched to a current position of the artificial mark 100, w indicates an image of the artificial mark 100, i.e., a template image, and w indicates an average value of pixels included in the image w(x, y) of the artificial mark 100.

0042The largest reliability value among the reliability values of the candidate regions calculated as a template matching result is selected in operation 417. The selected reliability value is compared to a predetermined reference value in operation 418. As a comparison result, if the selected reliability value is larger than the reference value, it is determined that detection of the artificial mark 100 succeeds in operation 419, and if the selected reliability value is smaller than the reference value, it is determined that detection of the artificial mark 100 fails in operation 420.

0043<figref idref="f0005">FIG. 5</figref> is a flowchart illustrating operation 342 of <figref idref="f0003">FIG. 3</figref>.

0044Referring to <figref idref="f0005">FIG. 5</figref>, a current position (x, y) and orientation θ of the mobile robot is an input in operation 511. The numbers of pulses (N_L, N_R) output from encoder sensors (not shown) attached to left and right wheels of the mobile robot are inputs in operation 513.

0045A next position and a next orientation of the mobile robot is obtained using the input current position (x, y) and orientation θ of the mobile robot and the numbers of pulses (N_L, N_R) output from the encoder sensors in operation 515. To do this, a constant value c_m for converting the number of encoder pulses to a distance actually moved by the wheels is calculated as shown in Equation 4.<maths id="math0007" num="[Equation 4]"><math display="block"><mrow><msub><mi>c</mi><mi>m</mi></msub><mo>=</mo><mi mathvariant="normal">π</mi><mo>⁢</mo><msub><mi>D</mi><mi>n</mi></msub><mo>/</mo><mi>n</mi><mo>⁢</mo><msub><mi>C</mi><mi>e</mi></msub></mrow></math><img file="EP1517210B1_D0007.tif" /></maths>

0046Here, D_n indicates a diameter of the wheel, C_e indicates a resolution of the encoder, i.e., the number of encoder pulses per 1 revolution, and n indicates a gear ratio between a motor to which the encoder is installed and the wheel.

0047A traveling distance <i>ΔU</i>_{<i>L</i>/<i>R</i>,<i>i</i>} of each of left and right wheels actually moved by the number of encoder pulses is calculated as shown in Equation 5.<maths id="math0008" num="[Equation 5]"><math display="block"><mrow><mi mathvariant="normal">Δ</mi><mo>⁢</mo><msub><mrow><mi>U</mi></mrow><mrow><mi>L</mi><mo>/</mo><mi>R</mi><mo>,</mo><mi>i</mi></mrow></msub><mo>=</mo><msub><mi>c</mi><mi>m</mi></msub><mspace width="1em" /><mrow><msub><mrow><mi>N</mi></mrow><mrow><mi>L</mi><mo>/</mo><mi>R</mi><mo>,</mo><mi>i</mi></mrow></msub></mrow></mrow></math><img file="EP1517210B1_D0008.tif" /></maths>

0048Here, <i>N</i>_{<i>L</i>/<i>R,i</i>} indicates the number of pulses of encoder sensors attached to the left and right wheels of the mobile robot at a time i.

0049An average movement distance displacement Δ<i>U_i</i> the wheel center and a converted azimuth displacement Δθ<i>_i</i> can be represented as shown in Equation 6 and Equation 7.<maths id="math0009" num="[Equation 6]"><math display="block"><mrow><mi mathvariant="normal">Δ</mi><mrow><msub><mi>U</mi><mi>i</mi></msub></mrow><mo>=</mo><mfenced separators=""><mi mathvariant="normal">Δ</mi><mrow><msub><mi>U</mi><mi>R</mi></msub></mrow><mo>+</mo><mi mathvariant="normal">Δ</mi><mrow><msub><mi>U</mi><mi>L</mi></msub></mrow></mfenced><mo>/</mo><mn>2.</mn></mrow></math><img file="EP1517210B1_D0009.tif" /></maths><maths id="math0010" num="[Equation 7]"><math display="block"><mrow><mi mathvariant="normal">Δ</mi><mrow><msub><mi>θ</mi><mi>i</mi></msub></mrow><mo>=</mo><mfenced separators=""><mi mathvariant="normal">Δ</mi><mrow><msub><mi>U</mi><mi>R</mi></msub></mrow><mo>-</mo><mi mathvariant="normal">Δ</mi><mrow><msub><mi>U</mi><mi>L</mi></msub></mrow></mfenced><mo>/</mo><mi>b</mi></mrow></math><img file="EP1517210B1_D0010.tif" /></maths>

0050Here, b indicates a distance between the left wheel and the right wheel.

0051Updating of the position and the orientation of the mobile robot at a time i can be performed using Equation 8.<maths id="math0011" num="[Equation 8]"><math display="block"><mrow><mtable columnalign="left"><mtr><mtd><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi><mo>-</mo><mn mathvariant="italic">1</mn></mrow></msub><mo>+</mo><mi mathvariant="normal">Δ</mi><mo>⁢</mo><msub><mi>U</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">cosθ</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>y</mi></mrow><mrow><mi>i</mi><mo>-</mo><mn mathvariant="italic">1</mn></mrow></msub><mo>+</mo><mi mathvariant="normal">Δ</mi><mo>⁢</mo><msub><mi>U</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">sinθ</mi><mi>i</mi></msub></mtd></mtr><mtr><mtd><msub><mi mathvariant="normal">θ</mi><mi>i</mi></msub><mo>=</mo><msub><mrow><mi mathvariant="normal">θ</mi></mrow><mrow><mi>i</mi><mo>-</mo><mn mathvariant="italic">1</mn></mrow></msub><mo>+</mo><mi mathvariant="normal">Δ</mi><mo>⁢</mo><msub><mi mathvariant="normal">θ</mi><mi>i</mi></msub></mtd></mtr></mtable></mrow></math><img file="EP1517210B1_D0011.tif" /></maths>

0052The invention can also be embodied as computer readable codes on a computer readable recording medium. The computer readable recording medium is any data storage device that can store data which can be thereafter read by a computer system. Examples of the computer readable recording medium include read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, optical data storage devices, and carrier waves (such as data transmission through the Internet). The computer readable recording medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion. Also, functional programs, codes, and code segments for accomplishing the present invention can be easily construed by programmers skilled in the art to which the present invention pertains.

0053As described above, the position and orientation of a mobile robot can be estimated in a real time using an image processing procedure with less noise in an environment of a dark light or a severe light change. Also, the image processing procedure for mark detection can be simplified by installing a few number of artificial marks on a ceiling of a place in which the mobile robot travels and detecting the artificial marks using a pattern recognition method.

0054While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the scope of the present invention as defined by the following claims.