Abstract:
A multi-core multi-thread based Kanade-Lucas-Tomasi (KLT) feature tracking method includes subdividing an input image into regions and allocating a core to each region; extracting KLT features for each region in parallel and in real time; and tracking the extracted features in the input image. Said extracting the features is carried out based on single-region/multi-thread/single-core architecture, while said tracking the features is carried out based on multi-feature/multi-thread/single-core architecture.

Description:
CROSS-REFERENCE(S) TO RELATED APPLICATION(S) 
       [0001]    The present invention claims priority of Korean Patent Application No. 10-2008-0111806, filed on Nov. 11, 2008, and Korean Patent Application No. 10-2009-0024051, filed on Mar. 20, 2009, which are incorporated herein by reference. 
       FIELD OF THE INVENTION 
       [0002]    The present invention relates to a multi-core multi-thread based KLT (Kanade-Lucas-Tomasi) feature tracking method and apparatus; and, more particularly, a method and apparatus that performs subdivision of a high-resolution input image into regions, allocation of a core to each region, real-time KLT feature extraction for each region in parallel and tracking the extracted features. 
       BACKGROUND OF THE INVENTION 
       [0003]    As well known in the art, image processing includes real-time data extraction from complicated scenes. For example, various kinds of differences on an image recorded by a video camera are identified and tracked. 
         [0004]    Camera tracking systems cannot operate in real time, if real-time tracking operation and real-time feature tracking on a two-dimensional image which is an input of the tracking operation are not supported. 
         [0005]    Researches for real-time operation of the camera tracking systems by using disclosed algorithms for feature tracking on two-dimensional images have been made so that the real-time operation is insured to some extent. 
         [0006]    However, the conventional camera tracking systems cannot track a large number of features in real time, and thus cannot fully support two-dimensional feature tracking. 
       SUMMARY OF THE INVENTION 
       [0007]    In view of the above, the present invention provides a multi-core multi-thread based KLT feature tracking method and apparatus that performs subdivision of a high-resolution input image into regions, allocation of a core to each region, real-time KLT feature extraction for each region in parallel and tracking the extracted features. 
         [0008]    In accordance with an aspect of the present invention, there is provided a multi-core multi-thread based Kanade-Lucas-Tomasi (KLT) feature tracking method including: 
         [0009]    subdividing an input image into regions and allocating a core to each region; 
         [0010]    extracting KLT features for each region in parallel and in real time; and 
         [0011]    tracking the extracted features in the input image. 
         [0012]    Said extracting the features for each region may include: applying Gaussian smoothing on the region; extracting horizontal and vertical gradients from the Gaussian-smoothed region; calculating moments and eigenvalues from the extracted gradients; and selecting a specific number of features by sorting the calculated eigenvalues in order of magnitudes thereof. 
         [0013]    Said tracking the extracted features may include calculating moments of the extracted features in the input image by using gradients thereof; and estimating displacements of the extracted features in the input image by using the calculated moments, wherein the input image is iteratively sub-sampled to generate a sub-sampled image for each iteration and the sub-sampled images along with the input image form an input image pyramid, in which the input image having the highest pixel resolution serves as a bottom level and the last sub-sampled image having the lowest pixel resolution serves as a top level; wherein said calculating the moments and said estimating the displacement are repeated from the top level of the input image pyramid to the bottom level thereof; and wherein the moments are calculated by using the gradients at a previous level. 
         [0014]    Preferably, said estimating the displacement uses Newton-Raphson estimation. 
         [0015]    Preferably, said extracting the features is carried out based on single-region/multi-thread/single-core architecture. 
         [0016]    Preferably, said tracking the features is carried out based on multi-feature/multi-thread/single-core architecture. 
         [0017]    In accordance with another aspect of the present invention, there is provided a multi-core multi-thread based Kanade-Lucas-Tomasi (KLT) feature tracking apparatus including: 
         [0018]    a subdivision/allocation unit for subdividing an input image into regions and allocating a core to each region; 
         [0019]    a feature extraction unit for extracting KLT features for each region in parallel and in real time; and 
         [0020]    a tracking unit for tracking the extracted features in the input image. 
         [0021]    The feature extraction unit may include a Gaussian smoothing unit for applying Gaussian smoothing on the region; a gradient extraction unit for extracting horizontal and vertical gradients from the Gaussian-smoothed region; an eigenvalue calculation unit for calculating moments and eigenvalues from the extracted gradients; and a feature selection unit for selecting a specific number of features by sorting the calculated eigenvalues in order of magnitudes thereof. 
         [0022]    The tracking unit may include a moment calculation unit for calculating moments of the extracted features in the input image by using gradients thereof; and a displacement estimation unit for estimating displacements of the extracted features in the input image by using the calculated moments, wherein the input image is iteratively sub-sampled to generate a sub-sampled image for each iteration and the sub-sampled images along with the input image form an input image pyramid, in which the input image having the highest pixel resolution serves as a bottom level and the last sub-sampled image having the lowest pixel resolution serves as a top level; wherein calculation of the moments and estimation of the displacement are repeated from the top level of the input image pyramid to the bottom level thereof; and wherein the moments are calculated by using the gradients at a previous level. 
         [0023]    Preferably, the displacement estimation unit uses Newton-Raphson estimation. 
         [0024]    Preferably, the feature extraction unit has single-region/multi-thread/single-core architecture. 
         [0025]    Preferably, the feature tracking unit has multi-feature/multi-thread/single-core architecture. 
         [0026]    According to the present invention, a high-resolution input image is subdivided into regions, a core is allocated to each region, KLT features for each region are extracted in parallel and in real time, and feature tracking for the extracted features are performed. Therefore, a large number of features can be tracked in real time and two-dimensional feature tracking can be fully supported. 
         [0027]    The method and apparatus of the present invention may perform KLT tracking algorithm on an input image having a pixel resolution of 1024×768 and a frame rate of 30 FPS (Frames per Second) within 0.033 second. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0028]    The above features of the present invention will become apparent from the following description of embodiments, given in conjunction with the accompanying drawings, in which: 
           [0029]      FIG. 1  illustrates a block diagram of multi-core multi-thread based KLT feature tracking apparatus in accordance with an embodiment of the present invention; 
           [0030]      FIG. 2  illustrates a block diagram of the KLT feature extraction unit in  FIG. 1 ; 
           [0031]      FIG. 3  illustrates a block diagram of the tracking unit in  FIG. 1 ; 
           [0032]      FIGS. 4A and 4B  illustrate a flowchart of a multi-core multi-thread based KLT feature tracking method performed by the apparatus of  FIG. 1 ; 
           [0033]      FIG. 5  illustrates an exemplary view of image subdivision and feature extraction procedures in the method of  FIGS. 4A and 4B ; and 
           [0034]      FIG. 6  illustrates an exemplary view of feature tracking procedure in the method of  FIGS. 4A and 4B . 
       
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
       [0035]    Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings, which form a part hereof. 
         [0036]      FIG. 1  illustrates a block diagram of multi-core multi-thread based KLT feature tracking apparatus in accordance with an embodiment of the present invention. The multi-core multi-thread based KLT feature tracking apparatus may include a subdivision/allocation unit  10 , a KLT feature extraction unit  20  and a tracking unit  30 . 
         [0037]    The subdivision/allocation unit  10  subdivides a high-resolution input image into regions as many as the number of cores of the apparatus, and allocates a core to each region such that each region can be processed simultaneously in parallel. The subdivision/allocation unit  10  provides the image subdivided into the regions assigned with the cores to the KLT feature extraction unit  20 . 
         [0038]    The KLT feature extraction unit  20  is a block to extract KLT features of each region in parallel and in real time. As shown in  FIG. 2 , the KLT feature extraction unit  20  may include a Gaussian smoothing unit  21 , a gradient extraction unit  23 , an eigenvalue calculation unit  25  and a feature selection unit  27 . 
         [0039]    The Gaussian smoothing unit  21  applies Gaussian smoothing to each region of the image received from the subdivision/allocation unit  10 , and provides the Gaussian-smoothed image to the gradient extraction unit  23 . 
         [0040]    The gradient extraction unit  23  extracts horizontal and vertical gradients from each region of the Gaussian-smoothed image received from the Gaussian smoothing unit  21 , and provides thus extracted horizontal and vertical gradients to the eigenvalue calculation unit  25  and to the tracking unit  30 . 
         [0041]    The eigenvalue calculation unit  25  calculates moments and eigenvalues from the gradients received from the gradient extraction unit  23 , and provides the calculated eigenvalues to the feature selection unit  27 . 
         [0042]    The feature selection unit  27  sorts the eigenvalues received from the eigenvalue calculation unit  25  in an order of magnitudes thereof to select an appropriate number of features for each region, and provides the selected features to the tracking unit  30 . 
         [0043]    The tracking unit  30  is a block to track features. As shown in  FIG. 3 , the tracking unit  30  may include a moment calculation unit  31  and a displacement estimation unit  33 . 
         [0044]    The moment calculation unit  31  calculates moments of the features received from the feature selection unit  27  by using the gradients received from the gradient extraction unit  23 . The moment calculation unit  31  provides the calculated moments to the displacement estimation unit  33 . 
         [0045]    The displacement estimation unit  33  estimates displacements. To be specific, the displacement estimation unit  33  calculates initial estimated displacements by using the moments received from the moment calculation unit  31 , and based thereon, performs Newton-Raphson estimation on displacements between frames around location of the features. In the Newton-Raphson estimation, the input image is iteratively sub-sampled to generate a sub-sampled image for each iteration and the sub-sampled images along with the input image form an input image pyramid. In the Newton-Raphson estimation, the input image having the highest pixel resolution serves as a bottom level and the last sub-sampled image having the lowest pixel resolution serves as a top level. The Newton-Raphson estimation completes displacement estimation when it reaches the bottom level of the input image pyramid. 
         [0046]    Below, a multi-core multi-thread based KLT feature tracking method according to the present invention will be described. 
         [0047]      FIGS. 4A and 4B  illustrate a flowchart of a multi-core multi-thread based KLT feature tracking method performed by the apparatus of  FIG. 1 . 
         [0048]    First, the subdivision/allocation unit  10  subdivides a high-resolution input image into regions as many as the number of cores of the apparatus, and allocates a core to each region such that each region can be processed simultaneously in parallel (step S 401 ). The subdivision/allocation unit  10  provides the image subdivided into the regions assigned with the cores to the Gaussian smoothing unit  21  of the KLT feature extraction unit  20  (step S 403 ). 
         [0049]      FIG. 5  illustrates an exemplary view of image subdivision and feature extraction procedures in the method of  FIGS. 4A and 4B . 
         [0050]    The feature tracking apparatus has, e.g., sixteen cores C 1  to C 16  as shown in  FIG. 5 . A core allocated to each region performs multiple convolutions via multiple threads. Such single-region/multi-thread/single-core architecture allows a real-time process for each frame. Further, features extracted in a current step of a tracking algorithm and feature locations thereof are used as input in a next step. 
         [0051]    Referring back to  FIG. 4A , the Gaussian smoothing unit  21  applies Gaussian smoothing to each region of the image received from the subdivision/allocation unit  10  (step S 405 ), and provides the Gaussian-smoothed image to the gradient extraction unit  23  (step S 407 ). 
         [0052]    The gradient extraction unit  23  extracts horizontal and vertical gradients from the Gaussian-smoothed image received from the Gaussian smoothing unit  21  (S 409 ), and provides thus extracted horizontal and vertical gradients to the moment calculation unit  31  of the tracking unit  30  (step S 411 ). Further, the gradient extraction unit  23  provides the extracted horizontal and vertical gradients to the eigenvalue calculation unit  25  (step S 413 ). 
         [0053]    The eigenvalue calculation unit  25  calculates moments and eigenvalues from the gradients received from the gradient extraction unit  23  (step S 415 ), and provides the calculated eigenvalues to the feature selection unit  27  (step S 417 ). 
         [0054]    The feature selection unit  27  sorts the eigenvalues received from the eigenvalue calculation unit  25  in an order of magnitudes thereof to select an appropriate number of features for each region (step S 419 ), and provides the selected features to the moment calculation unit  31  of the tracking unit  30  (step S 421 ). 
         [0055]    The moment calculation unit  31  calculates moments of the features received from the feature selection unit  27  by using the gradients received from the gradient extraction unit  23  (step S 423 ). The moment calculation unit  31  provides the calculated moments to the displacement estimation unit  33  (step S 425 ). 
         [0056]    The displacement estimation unit  33  estimates displacements. To be specific, the displacement estimation unit  33  calculates initial estimated displacements by using the moments received from the moment calculation unit  31  (step S 427 ), and based thereon, repeats the Newton-Raphson estimation on displacements between frames around location of the features until it reaches the bottom level of the input image pyramid, thereby completing displacement estimation (step S 429 ). 
         [0057]      FIG. 6  illustrates an exemplary view of feature tracking procedure in the method of  FIGS. 4A and 4B . The feature tracking procedure is based on multi-feature/multi-thread/single-core architecture. In  FIG. 6 , reference symbols C 14   1 - 1  to C 14   1 - 6  represent threads in the fourteenth core of the feature tracking apparatus, and small points in a circle S 1  represent features whose displacements are to be estimated. 
         [0058]    Displacement estimation of the features is started at the top level of the input image pyramid. In a box S 2 , eighteen moments are calculated to obtain a 6×6 matrix S. In a box S 3 , differences in brightness between frames are calculated to obtain a 6×1 vector b. An estimated displacement matrix x is obtained from a linear algebra equation S·x=b. Solutions of the box S 3  and S·x=b are calculated until displacements in the matrix x converge, and thus converged displacements are determined as initial estimated locations at the next level of the input image pyramid. At the next level, initial estimated locations at the following level of the input image pyramid are determined through an identical procedure. Such procedure is repeated until it reaches the bottom level of the input image pyramid, thereby completing the displacement estimation. 
         [0059]    In the displacement estimation, calculation of the differences in brightness between frames in regions around the features needs to be repeated, and the moments of the features extracted during the feature extraction are required. Further, inverse operation of a matrix using the Gauss elimination is necessary to calculate a solution for a linear algebra equation, e.g., S·x=b. In order to reduce load for the above-describe calculation, the multi-feature/multi-thread/single-core architecture in the single-region/multi-thread/single-core architecture selected for the feature extraction is adopted. In the multi-feature/multi-thread/single-core architecture, multiple features are corresponded with single core and multiple threads are used for displacement estimation of the respective features. 
         [0060]    While the invention has been shown and described with respect to the embodiments, it will be understood by those skilled in the art that various changes and modification may be made without departing from the scope of the invention as defined in the following claims.