Person tracking method and apparatus using robot

[0001] This application claims the benefit of Korean Patent Application No. 2004-0066396, filed on Aug. 23, 2004, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to a person tracking method and apparatus using a robot, and more particularly to a method and an apparatus for detecting a person from an input image and tracking the motion of the detected person using a robot.

[0004] 2. Description of Related Art

[0005] Recently, a robot has been spotlighted as a system to replace humans for simple tasks in a home or in a place hard to access in person. Currently, the function of the robot is only to perform simple repeated tasks. A prerequisite for performing more intelligent works is an interaction with the person who employs the robot. For smooth interaction, the robot needs to be able to locate and track the user so that it stays in the vicinity of the user.

[0006] One way a robot can locate and track a user is by face detection. Most existing face detecting devices locate a person indoors or outdoors using a method of storing a background image and then detecting motion of the person using a difference image obtained by subtracting the background image from the input image, or a method of tracking the location of the person using only shape information. The method using the difference image between the input image and the background image is very efficient in a case of using a fixed camera, but not for a continuously moving camera arranged in a robot, because the background image continuously changes. On the other hand, the method using the shape information of the person takes a long time to locate the person by matching a plurality of model images, similar to a person shape, to the whole input image.

[0007] An aspect of the present invention provides a method and apparatus for detecting a person using a skin color from an input image and tracking the detected person.

[0008] According to an aspect of the present invention, there is provided a person tracking method including detecting a person in a first window of a current input image using a skin color of the person; and setting a plurality of second windows in a next input image, correlating the first window and the second windows and tracking the detected person in the next input image using the correlated results.

[0009] According to another aspect of the present invention, there is provided a person tracking apparatus including: an image input unit which outputs continuous images; a person detecting unit which detects a person from a current input image in a first window using a skin color of the person; and a tracking unit which sets a plurality of second windows in a next input image following the current input image, correlates the first window and the second windows and tracks the detected person in the next input image using the correlated results.

[0010] According to another aspect of the present invention, there is provided a computer-readable storage medium encoded with processing instructions for causing a processor to perform a person tracking method including: detecting a person in a first window of a current input image using a skin color of the person; and setting a plurality of second windows in a next input image, correlating the first window and the second windows and tracking the detected person in the next input image using the correlated results.

[0011] According to another aspect of the present invention, there is provided a robot, including: an image input unit receiving an image and outputting a captured image; a person detecting unit detecting a person in the captured image using a skin color of the person; a tracking object determining unit selecting a detected person in the captured image as a tracking object; and a tracking unit moving the robot a location near the observation object and tracking the observation object at the location.

[0012] Additional and/or other aspects and advantages of the present invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention

[0026] Reference will now be made in detail to embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below in order to explain the present invention by referring to the figures.

[0027] FIG. 1 is a block diagram of a person tracking apparatus according to an embodiment of the present invention. The person tracking apparatus includes an image input unit 13, a person detecting unit 10, a tracking object determining unit 11 and a tracking unit 12.

[0028] The image input unit 13 outputs an image captured by a photographing arrangement (not shown), and can be any type of camera which can photograph a moving person. The person detecting unit 10 detects the person using a skin color of the person from the image input from the image input unit 13. When multiple persons are detected in the person detecting unit 10, the tracking object determining unit 11 determines (i.e., selects) one of the detected persons, for example, a detected person who is the nearest to the centroid of the detected persons in the image as a tracking object. If the tracking object is determined, the robot approaches to a certain distance from the tracking object using the location and distance information of the tracking object.

[0029] The operation of the person tracking apparatus illustrated in FIG. 1 will now be described in detail with reference to the flowchart in FIG. 2.

[0030] First, the person detecting unit 10 detects the person from the input image (operation 20). FIG. 3 is a detailed flowchart illustrating the person detecting operation 20. Referring to FIG. 3, first, color information of the input image is converted (operation 30). The color information conversion is to reduce the effect of the illumination included in the input image and emphasize skin color regions. RGB (Red, Green, and Blue) colors of the input image are converted into a normalized rgb domain as shown by equation (1).

[0031] $\begin{array}{cc}r=\frac{R}{R+G+B},g=\frac{G}{R+G+B},b=\frac{B}{R+G+B}& \left(1\right)\end{array}$

[0032] FIG. 4A illustrates an input image and FIG. 4B illustrates the input image with RGB colors normalized.

[0033] Next, Gaussian modeling is performed as shown by equation (2) on an rgb image using averages (m_r, m_g) of colors r and g and standard deviations (σ_r, σ_g) of a plurality of skin color models. Regions where the modeled values are greater than a specified threshold value, for example 240, are detected as candidate regions for the skin color (operation 31).

[0034] $\begin{array}{cc}\begin{array}{c}Z\left(x,y\right)=G\left(r\left(x,y\right),g\left(x,y\right)\right)\\ =\frac{1}{2\pi {\sigma }_r{\sigma }_g}\exp \left[-\frac{1}{2}\left\{{\left(\frac{r\left(x,y\right)-m_r}{{\sigma }_r}\right)}^2+{\left(\frac{g\left(x,y\right)-m_g}{{\sigma }_g}\right)}^2\right\}\right]\}\end{array}& \left(2\right)\end{array}$

[0035] FIG. 4C illustrates regions that are detected as candidate regions from the input image. The image is binarized so that the candidate regions are expressed by white and other regions are expressed by black.

[0036] In operations 32 and 33, a gray image and an edge image for the input image are obtained, respectively. The edge image can be obtained by the Sobel edge detecting method or the Canny edge detecting method.

[0037] The regions corresponding to the candidate regions detected in operation 31 are extracted from the gray image and the edge image, and are normalized using the centroid and size information of the candidate regions (operation 34).

[0038] FIG. 5A illustrates an example of the first normalization for a candidate region on the basis of a centroid 50 of the candidate region. Each candidate region is normalized so that its height is greater than its width after obtaining a square of size of a×a centered around the centroid 50. For example, the candidate region is normalized by (2×a) respectively in left and right sides from the centroide 50, totally 2×(2×a) in width, and (2×a) upward and (3.5×a) downward from the centroid 50, totally 2×a+3.5×a in height. Here, a may be the square root of the size information, that is, √{square root over (size)}.

[0039] A second normalization is performed for each skin color region that is subject to the primary normalization. The second normalization is performed through bilinear interpolation. FIGS. 5B, 5C and 5D illustrate examples of the secondly normalized images.

[0040] Next, the normalized gray images are used to determine whether any of the candidate regions includes the person (operation 35). The determination is performed by applying an SVM (Support Vector Machine) to the normalized gray images. This process is described in more detail. First, a Mahalanobis distance for the normalized gray image is obtained in a block unit, each block having a size of p×q.

[0041] The average of the pixel values of each block can be obtained using equation (3).

[0042] $\begin{array}{cc}{\stackrel{\_}{x}}_l=\frac{1}{\mathrm{pq}}\sum _{\left(x,t\right)\in X_t}{x}_{s,t}& \left(3\right)\end{array}$
Here, p and q respectively denote the number of horizontal and vertical pixels for each block, x_i denotes the average of pixel values in a block, and x_s,t denotes a pixel value included in the block.

[0043] On the other hand, a variance of each block can be expressed as equation (4).

[0044] $\begin{array}{cc}\sum _i=\frac{1}{\mathrm{pq}}\sum _{\left(x,t\right)\in X_t}\left(x_{s,t}-{\stackrel{\_}{x}}_l\right){\left(x_{s,t}-{\stackrel{\_}{x}}_l\right)}^T& \left(4\right)\end{array}$
Here, T denotes a transpose.

[0045] Using the average and the variance of each block, the Mahalanobis distance d_(i,j) and Mahalanobis distance map D can be obtained using equations (5) and (6), respectively.

[0046] $\begin{array}{cc}{d}_{\left(i,j\right)}={\left({\stackrel{\_}{x}}_i-{\stackrel{\_}{x}}_j\right)}^T{\left(\sum _i+\sum _j\right)}^{-1}\left({\stackrel{\_}{x}}_i-{\stackrel{\_}{x}}_j\right)& \left(5\right)\\ D=\left[\begin{array}{cccc}0& d_{\left(1,2\right)}& \dots & d_{\left(1,\mathrm{MN}\right)}\\ d_{\left(2,1\right)}& 0& \dots & d_{\left(2,\mathrm{MN}\right)}\\ ⋮& ⋮& ⋮& ⋮\\ d_{\left(\mathrm{MN},1\right)}& d_{\left(\mathrm{MN},2\right)}& \dots & 0\end{array}\right]& \left(6\right)\end{array}$

[0047] Here, M and N respectively denote the number of the horizontal and vertical blocks for the normalized gray image. If a region having a size of 30×40 in the normalized gray image is divided into blocks having a size of 5×5, the Mahalanobis distance map D becomes a 48×48 matrix.

[0048] FIGS. 6A, 6B and 6C respectively show Mahalanobis distance maps for FIGS. 5B, 5C and 5D. As shown in FIGS. 6A, 6B and 6C, the gray image corresponding to the face of the person shows symmetry centered around a diagonal line from the top left corner to the bottom right corner. However, the gray image without the face of the person is not symmetrical.

[0049] Because an SVM can be trained in advance to recognize the facial image of a person, the SVM is trained to determine whether an image is the facial image of the person by obtaining the Mahalanobis distance map according to equation (6) for the image normalized on the basis of each skin color region.

[0050] Accordingly, by applying the Mahalanobis distance map obtained from the normalized gray image for the input image to the SVM, it is determined whether the image contains the person's face.

[0051] Similarity between a normalized edge image and a model image of the person is determined through obtaining a Hausdorff distance (operation 36). Here, the model image of the person means the edge image for at least one model image. One or more of the edge images of the model images may be stored where the model images contain persons facing a front side, a specified angled left side and right side.

[0052] The Hausdorff distance is obtained by calculating the Euclidean distances between every feature point of the model image and one feature point in the edge image and between one feature point of the edge image and every feature point in the model image are obtained as the following. That is, if the edge image A is composed of m feature points (pixels) and the model image B is composed of n feature points (pixels), the Hausdorff distance H(A, B) can be expressed by equation (7).

Here,

[0053] $\begin{array}{cc}H\left(A,B\right)=\max \left(h\left(A,B\right),h\left(B,A\right)\right)h\left(A,B\right)=\underset{a\in A}{\max }\underset{b\in B}{\min }a-bA=\left\{a_1,\dots ,a_m\right\}B=\left\{b_1,\dots ,b_n\right\}.& \left(7\right)\end{array}$

[0054] In detail, h(A, B) is obtained by selecting the maximum value from the minimum values for m feature points (pixels) of the input edge image A where each of the minimum values is the minimum among Euclidean distances between a feature point (pixel) of the input edge image A and every feature points (pixels) of the model image B. On the contrary, h(B, A) is obtained by selecting the maximum value from the minimum values for n feature points (pixels) of the model image B where each of the minimum values is the minimum among Euclidean distances between a feature point (pixel) of the model image B and every feature points of the input edge image A. H(A, B) is determined as the maximum of h(A, B) and h(B, A). From the value of H(A, B), it can be known that how much the input edge image mismatches with the model image. The Hausdorff distances between the input model image and every model image, for example, the front model image, the left model image and the right model image are calculated, and the maximum value among the Hausdorff distances is output as a final Hausdorff distance. The final Hausdorff distance H(A, B) is compared with a specified threshold value. If the Hausdorff distance H(A, B) is less than the threshold value, the corresponding candidate region is determined to contain the person, otherwise the corresponding candidate region is determined to be the background.

[0055] Using the SVM of operation 35 and the Hausdorff distance calculating result of operation 36, the persons in the input image are finally detected (operation 37).

[0056] FIGS. 7A through 7D schematically exemplifies a process of detecting the persons from an input image. The color information of the input image of FIG. 7A is converted, and person candidate regions illustrated in FIG. 7B are detected from the converted color information. Also, a gray image and an edge image of FIG. 7C are obtained from the input image of FIG. 7A. In the gray image and the edge image, the normalized images having a size of 30×40 pixels are obtained for each of the detected person candidate regions. It is determined whether each of the normalized gray images contains a person using a Mahalanobis distance map and SVM. The Hausdorff distances between the normalized edge images and the model images for the front, left and right sides of the face are obtained, and compared with a threshold value to determine whether each of the normalized edge images contains a person's face. FIG. 7D illustrates the detected multiple persons.

[0057] Returning to FIG. 2, when multiple persons are detected in the input image (operation 21), the tracked object determining unit 11 of FIG. 1 determines a tracking object as follows (operation 22). First, a center value for the horizontal axis of the input image is determined. For example, if the input image has a size of 320×240, the center pixel of the horizontal axis is 160. Next, a location and an amplitude of the centroid for the detected persons are obtained. The location and the amplitude of the centroid can be obtained by averaging locations of the skin color pixels of FIG. 7B corresponding to the detected persons by the number of the skin color pixels. A person who is closest to the obtained location of the centroid in the horizontal axis of the image is determined to be an observation object. For example, among the detected persons of FIG. 7D, the person represented by a reference numeral 70 may be the observation object.

[0058] When the observation object is determined, the robot is moved to a certain location in the vicinity of the observation object (operation 23) and begins to track the observation object at that location (operation 24). The tracking is performed using a particle filter method as illustrated in FIG. 8.

[0059] In the tracking of the present embodiment, a location of a person for a specified measurement value can be expressed by a probability. If a sample set at time t is expressed by {s_t⁽ⁿ⁾, n=1, . . . , N} and a weight, a state density, of a sample is expressed by π_t⁽ⁿ⁾, the weighted sample set for posterior p(x_t−1|Z_t−1) at time (t−1) can be expressed by {(s_t−1⁽ⁿ⁾, π_t−1⁽ⁿ⁾), n=1, . . . , N} in operation 80. Here, Z_t−1 is a feature value measured at time (t−1). In operation 81, N samplings are performed from {s_t−1⁽ⁿ⁾} to generate {ś_t⁽ⁿ⁾} and the generated samples undergo drift. The sampling is performed with reference to π_t−1⁽ⁿ⁾. That is, several samplings are performed on a sample having a high weight, and samplings may be not performed on a sample having a relatively low weight.

[0060] The drift is determined according to a specified dynamics reflecting a conditional density function p(x_t|x_t−1=ś_t⁽ⁿ⁾) so that a new state of the sample is directly influenced by the previous state. The drifted samples are diffused in operation 82 so that the sample set {s_t⁽ⁿ⁾} at time t is generated. The sample value is determined by a weighted sum of a vector of the standard normal random variates and the drifted sample.

[0061] The weights of the samples are determined by each of observation densities p(z_t|x_t) at each sample location as equation (8) (operation 83).

[0062] $\begin{array}{cc}{\pi }_t^{\left(n\right)}=p\left(z_t|x_t=8_t^{\left(n\right)}\right)\sum _n{\pi }_t^{\left(n\right)}=1& \left(8\right)\end{array}$

[0063] According to the above-mentioned process, in operation 84, the weighted sample set {(s_t⁽ⁿ⁾, π_t⁽ⁿ⁾)} at time t is obtained.

[0064] In the present embodiment, the similarity based on color histogram is used as an observation feature. The similarity will be described in detail.

[0065] The similarity is determined by a correlation between an image m₁ of a normalization window at time (t−1) and an image m₂ of a normalization window determined by centering around each sample at time t. FIG. 9A illustrates the normalization window image at time (t−1) and FIG. 9B illustrates the normalization window image obtained by centering around each sample. The similarity between the images of FIG. 9A and FIG. 9B is calculated, and a position of a sample of the window image having a maximum similarity is determined to be a tracking location in a current frame. The similarity is determined by equation (9). The size of the normalized image is (2n+1)×(2m+1).

[0066] $\begin{array}{cc}\mathrm{likehood}\left(m_1,m_2\right)=\frac{\begin{array}{c}\sum _{i=-n}^n\sum _{i=-m}^m\left[I_1\left(u_1+i,v_1+j\right)-\stackrel{\_}{I_1\left(u_1,v_1\right)}\right]\times \\ \left[I_2\left(u_2+i,v_2+j\right)-\stackrel{\_}{I_2\left(u_2,v_2\right)}\right]\end{array}}{\left(2n+1\right)\left(2m+1\right)\sqrt{{\sigma }^2\left(I_1\right)\times {\sigma }^2\left(I_2\right)}}& \left(9\right)\end{array}$

[0067] Here, I₁ and I₂ are color histograms of m₁ and m₂, respectively, and (u₁,v₁) and (u₂,v₂) are central pixel locations of m₁ and m₂, respectively.

[0068] In equation 9, an average color histogram I_k(u, v) of m₁ and m₂ and the variance thereof σ(I_k) are calculated using equation (10).

[0069] $\begin{array}{cc}\stackrel{\_}{I_k\left(u,v\right)}=\sum _{i=-n}^n\sum _{j=-m}^m{I}_k\left(u+i,v+j\right)/\left[\left(2n+1\right)\left(2m+1\right)\right]\sigma \left(I_k\right)=\sqrt{\frac{\sum _{i=-n}^n\sum _{j=-m}^m{I}_k^2\left(u,v\right)}{\left(2n+1\right)\times \left(2m+1\right)}-\stackrel{\_}{I_k\left(u,v\right)}}& \left(10\right)\end{array}$

[0070] Next, a CDF of the current sample is obtained and operations 80 through 84 for the next frame are repeated.

[0071] Parts (a)-(h) of FIG. 10 illustrate a process of tracking a person who walks to and sits on a chair. As shown in FIG. 10, the person tracking is performed well.

[0072] The above-described embodiments of the present invention can also be embodied as computer-readable code on a computer-readable storage medium. A computer-readable storage medium is any data storage device that can store data which can be thereafter read by a computer system. Examples of a computer-readable storage 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 storage medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.

[0073] According to the above-described embodiments of the present invention, a person can be detected and tracked, regardless of the facing direction of the person, by detecting persons from an image using the skin color and shape information of the persons, determining a tracking object, and tracking the tracking object using the color histogram information.

[0074] Furthermore, using the correlation between the normalized image of the previous frame and the normalized images centered around each sample, a motion of the person can easily be detected.

[0075] The above-described embodiments of the present invention can continuously track and monitor a determined person. Accordingly, since pictures can be taken continuously while tracking the specified specific person, the present invention can be applied to an unmanned camera of a broadcasting station.

[0076] Moreover, the intelligence of household electric appliances can be accomplished using the location and distance information of the person.

[0077] Although a few embodiments of the present invention have been shown and described, the present invention is not limited to the described embodiments. Instead, it would be appreciated by those skilled in the art that changes may be made to these embodiments without departing from the principles and spirit of the invention, the scope of which is defined by the claims and their equivalents.