FIELD OF INVENTION
[001] The present invention relates to object tracking and more particularly to a video object tracking using multi-path trajectory analysis.

BACKGROUND OF INVENTION
[002] Video object tracking is a well known method used in several computer vision-guided applications  such as security  monitoring  sports  traffic  healthcare  or any other application. However  different applications have different requirements. For example  in traffic monitoring applications  tracking vehicles moving on highway requires analyzing fast moving objects of rectangular shape. Whereas in sports  it is often necessary to track players and playing objects like football  tennis ball  basket ball  or any other object. In surveillance applications  often objects are of unknown shape and restrictions on the movement of objects may not be applied. In such cases  tracking methods need to be robust with respect to environmental noise.
[003] In an existing video object tracking method  a portion of an object is marked in first frame and this marked portion is tracked in consecutive frames. A corresponding point that matches with the marked portion of the first frame within the consecutive frames is determined by minimizing the matching distance based on matching criteria. The matching criteria can be determined using information such as Sum of Absolute Differences (SAD) or sum of squared differences or any other application specific information.
[004] In an existing block based object tracking method (single path tracking)  a block representing a portion of an object is marked or detected in the first frame. A best match of the marked portion in the next frame is selected based on the minimum SAD criteria. Similarly  in each consecutive frame  the best match of the marked portion is selected and the trajectory of the block is obtained following the minimum SAD criteria. The disadvantage of the single path tracking method is that  there exists certain error while detecting the best block at each and every frame using the minimum SAD criteria. This happens because of the similar color and pixel intensity of the neighboring blocks present within the frame and this error will be cumulatively added while detecting the trajectory of the object. Even  if the best block is selected at every consecutive frame using the existing methodology  an optimal solution may not be achieved. This is because of the fact that the existing methods depend heavily upon the success of the SAD or any other measure based inter-frame point correspondence technique. Such methods produce local maxima which may not achieve the global solution in all cases. Thus  the single path tracking method may not always achieve the optimal trajectory of the object being tracked.
[005] In light of the above discussion  there is a need for a video object tracking method that reduces the error while detecting the minimum SAD in the single path tracking (best match criteria) to obtain the optimal trajectory of the object in a video stream.

OBJECT OF INVENTION
[006] The principal object of the embodiments herein is to provide a method and system that provides a multi-path trajectory analysis for tracking objects in a video stream.
[007] Another object of the invention is to provide a method for switching between single path tracking mode and multi-path tracking mode for tracking objects in a video stream.

SUMMARY
[008] Accordingly the invention provides a method for obtaining trajectory of an object using multi-path tracking mode. The method includes marking a portion of the object in a frame of a video  obtaining consecutive frames in the video and tracking the marked portion of the object in consecutive frames by estimating sum of absolute difference. Further  the method includes comparing the sum of absolute difference to a sum of absolute difference threshold  switching between said multi-path tracking mode and single path tracking mode based on the sum of absolute difference threshold and obtaining trajectory of the marked portion by combining the single path tracking mode and multi-path tracking mode.
[009] In an embodiment  marking further includes dividing the frame into multiple blocks. In an embodiment  the method tracks the marked portion in the consecutive frame of the video when the sum of absolute difference of the multiple blocks is less than the threshold. Further  the tracking includes selecting a best block among the multiple blocks in the single path tracking mode.
[0010] Furthermore  the method switches to the multi-path tracking mode from the single path tracking mode when the sum of absolute difference of the plurality of blocks is greater than the threshold and assigns a level upon switching into the multi-path tracking mode. The multi-path tracking mode terminates to the single path tracking mode when said level reaches a maximum level.
[0011] In addition  the multi-path tracking mode further includes selecting possible blocks among multiple blocks for the marked portion in the consecutive frame and estimating the sum of absolute difference between the best possible blocks and the marked portion for selecting the best block.
[0012] Further  the method selects the best block for the marked portion among the best possible blocks based on minimum sum of absolute difference criteria. Furthermore  selecting the best block includes determining the sum of absolute difference of the best possible blocks. Furthermore  the method increments the level after selecting the best block for the marked portion in the consecutive frame. Moreover  obtaining the trajectory further includes combining tracked results of the single path tracking mode and multi-path tracking mode.
[0013] These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings. It should be understood  however  that the following descriptions  while indicating preferred embodiments and numerous specific details thereof  are given by way of illustration and not of limitation. Many changes and modifications may be made within the scope of the embodiments herein without departing from the spirit thereof  and the embodiments herein include all such modifications.

BRIEF DESCRIPTION OF FIGURES
[0014] This invention is illustrated in the accompanying drawings  throughout which like reference letters indicate corresponding parts in the various figures. The embodiments herein will be better understood from the following description with reference to the drawings  in which:
[0015] FIG. 1 illustrates a video frame with an object spanned in different blocks and feature point marked;
[0016] FIG. 2 illustrates a position of the moving object in different frames assuming that the object is moving with unknown velocity and acceleration;
[0017] FIG. 3 illustrates the feature point selection and object tracking using minimum SAD criteria;
[0018] FIG. 4 illustrates estimation of SAD and inter-frame block association;
[0019] FIG. 5 illustrates a single path tracking method;
[0020] FIG. 6 illustrates a flow diagram describing a method for tracking object using multi-path tracking  in accordance with various embodiments of the present invention;
[0021] FIG. 7 illustrates a flow diagram describing a method for the multi-path tracking  in accordance with various embodiments of the present invention;
[0022] FIG. 8 illustrates a tree representation of the object tracking  in accordance with various embodiments of the present invention; and
[0023] FIG. 9 illustrates a computing environment implementing the application  in accordance with various embodiments of the present invention.

DETAILED DESCRIPTION OF INVENTION
[0024] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description.
[0025] The embodiments described herein achieve a method and system for video object tracking using a multi-path analysis. The marked point (feature point) is tracked in consecutive frames using both single path tracking and multi-path tracking modes. The method considers multiple neighboring blocks of the feature point being tracked while obtaining the trajectory of the object. The method provides a Sum of Absolute Differences (SAD) threshold (T) and select only K number of neighboring blocks when SAD with all of the neighboring blocks of the block representing the feature point is higher than T.
[0026] The method includes switching between the single path tracking mode and the multi-path tracking mode based on the threshold (T). The method includes entering the multi-path tracking mode from the single path tracking mode based on the threshold (T). The method assigns a level (L) to define the maximum depth of the multi-path mode. Further  the method terminates the multi-path tracking mode when L reaches a maximum allowable level (Lmax) or the SAD value becomes less than the threshold (T). Finally  the trajectory of the object is obtained by combining the tracking results of the single path tracking mode and the multi-path tracking mode.
[0027] Referring now to the drawings  and more particularly to FIGS. 1 through 9  where similar reference characters denote corresponding features consistently throughout the figures  there are shown preferred embodiments.
[0028] FIG. 1 illustrates a video frame with an object spanned in different blocks and feature point marked. FIG. 1 includes a video frame having multiple blocks  a moving object  and a marked block M. The marked block M represents the feature point which is tracked in consecutive frames. In an embodiment  it is assumed that the moving object can span over multiple blocks of rectangular size. For example  as shown in the FIG. 1  the moving object can span over the multiple blocks (such as N1  N2  N3  N4  M  N5  N6  N7  N8  N9  and N10).
[0029] FIG. 2 illustrates a position of the moving object in different frames assuming that the object is moving with unknown velocity and acceleration. As depicted in the FIG. 2  the object in the current frame with marked block M (feature point) is tracked in the next consecutive frames  assuming that the moving object is of fixed size (rigid). It is assumed that the neighboring blocks of M (for example  N1  N2  … N10) have similar color  intensity  and texture characteristics  which closely matches with the block M. Thus  it is difficult to track the movement of the feature point (block M) in the consecutive frames using single path mode.
[0030] FIG. 3 illustrates the feature point selection and the object tracking using minimum SAD criteria. In the existing method of object tracking  a block representing a part of an object is marked in the first frame by a user. In an example  the best block among the multiple blocks is selected based on the minimum SAD criteria in the next frame. Similarly  in each consecutive frame  the best block among the blocks is selected based on the minimum SAD criteria. The hierarchical representation can be in the form of a tree  which is formed during the selection of the best block for each consecutive frame (as shown in FIG. 3). The highlighted circles represent the trajectory of the block  which can be selected or marked by the user in the first frame.
[0031] FIG. 4 illustrates an estimation of the SAD and inter-frame block association. As depicted in the FIG. 4  a block B represents a portion of the object being tracked in a frame ‘i"". The SAD can be estimated between the block B and neighboring blocks inside a predefined window. The SAD is computed using equation 1  where X {BLOCK1  BLOCK2.....BLOCKM} and each block is of the dimension n1 X n2.

[0032] There exist Kalman filter based trajectory refinement methods that use predefined motion model to correct the measurement error in the SAD. At each consecutive frame  the measurement is updated by using the filter. Those methods usually explore single path. However  there may be situations when the Kalman filter based single path analysis may fail. For example  as explained in FIG. 1  if the neighboring blocks include similar statistics  then the single path analysis may not achieve an optimal trajectory. In such situations  instead of following local maxima  a better estimation following global or semi-global maxima can be suggested.
[0033] FIG. 5 illustrates a single path tracking method. Three exemplary consecutive frames namely frame 0  frame 1  and frame 2 of a video stream are shown in the FIG. 5. In an example  a user marks a block B0 in the frame 0 which needs to be tracked in the next consecutive frames by using the minimum SAD based criteria. The single path tracking method tracks the marked object as described below.
[0034] As shown in FIG. 5  the best match for the block B0 is searched in the next frame. In a typical scenario  single path tracking method may select the block B1 as the best choice according to the minimum SAD criterion and the block B2 may not be selected as only one output is considered. In this case  it may be possible that in the next frame  the SAD estimated between the blocks B3 and B0 becomes lowest among all. However  as B2 is ignored in the previous frame  the method does not consider B3 in the computation of the final path. In an example  though the B0 does not include the global optimal SAD  B4 gets selected as it is linked through B1. Further  the block B3 may move outside the search window due to fast movement of the object. In such situations  there is no scope to compute SAD between the block B1 and B3 in the second frame. Thus  the best match criteria may not always achieve the optimal trajectory.
[0035] FIG. 6 illustrates a flow diagram describing a method 600 for tracking object using multi-path tracking  in accordance with various embodiments of the present invention. In an embodiment  at step 602  a video stream is obtained by the user. In an example  the video stream described herein can include multiple image frames with one or more objects. The object can appear in each of the image frames of the video stream. The object can include different scale and/or orientation in each of the image frames. The image frames of the video stream may be obtained by using a video camera and such image frames may be stored for analysis and tracking of the object.
[0036] At step 602  the first frame of the video stream is extracted and the object is identified. In an embodiment  the object is identified manually by a user. In another embodiment  the object is identified automatically using an object detection technique and a portion of object in the first frame of the video stream is marked. This marked portion is considered as a feature point which is tracked in the successive frames of the video stream.
[0037] At step 606  the marked area or the portion of the object is divided into rectangular blocks of equal sizes. The marked portion in the identified object is divided into object segments. For example  the identified object is divided into overlapping object segments to maintain coherence between the adjacent object segments.
[0038] At step 608  the trajectory of each independent block is tracked using multi-path tracking technique. At step 610  the results of each individual block tracked are combined to obtain the trajectory of the marked portion in the first frame of the video stream. The various steps described with respect to FIG. 6 may be performed in the order presented  in a different order  or simultaneously. Further  in some embodiments  some steps listed in the FIG. 6 may be omitted or added without deviating from the scope of invention.
[0039] FIG. 7 illustrates a flow diagram describing a method 700 for the multi-path tracking  in accordance with various embodiments of the present invention. In an example  let the point P denotes the center of the block representing a marked portion of the object to be tracked in the first frame of the video and Lmax denotes the maximum permissible level in multi-path tracking mode (MPT). At step 702  the method 700 includes selecting a point (P) of the object that is to be tracked in the successive frames of the video stream. At step 704  the method 700 includes obtaining the consecutive frame of the video stream and estimating the SAD by comparing the point (P) with all of the neighboring blocks (Q).
[0040] At step 706  the method 700 includes determining whether SAD (P  Q) < T for all of the neighboring blocks of marked portion (P) in the consecutive frame. In response to determining ( that the SAD is less than the threshold (T) for all of the neighboring blocks in the consecutive frame of the video stream)  at step 708  the method 700 includes selecting the best neighboring block (Q) that has minimum SAD in the consecutive frame by using the single path tracking.
[0041] At step 710  if the SAD (P  Q) > T  the method 700 includes selecting the K best blocks (which are neighboring nodes of a node) before entering into MPT mode. Further  the MPT level (L) is assigned to zero during the initial phase of the MPT mode  which indicates the current depth of the tree inside the MPT mode.
[0042] At step 712  during the MPT mode execution  the method 700 includes obtaining the consecutive frame of the video stream  selecting  all the K*K blocks  and increasing the level (L). Further  at step 714  the method 700 includes determining whether the SAD < T for any of the K*K blocks. In response to determining that the SAD < T for any of the K*K blocks  the method 700 includes selecting the best block based on the minimum SAD shown at step 716. If the SAD > T for all the K*K blocks  then the MPT mode is repeated by incrementing the level (L). Further  at step 718  the method 700 includes determining whether the number of levels (L) in the MPT has reached a threshold value (Lmax) defined by the user. If the level (L) < Lmax  then the MPT mode is repeated.
[0043] At step 722  the method 700 includes selecting the K best blocks based on the minimum SAD from the K*K blocks. Further  the method 700 includes repeating the step 712 for continuing in the multi-path mode. Once the level (L) reaches the threshold level (Lmax) defined by the user  the method 700 includes switching to the single point tracking mode and selecting the best block based on the minimum SAD shown in step 720. The various steps described with respect to the FIG. 7 may be performed in the order presented  in a different order  or simultaneously. Further  in some embodiments  some of the steps listed in the FIG. 7 may be omitted or added without departing from the scope of invention.
[0044] In the MPT mode  the system and method assigns an initial level (L) zero and increments the level (L) in consecutive frames. The execution of the multi-path tracking method is explained with an example herein.
[0045] Consider an object with a center P  which is marked by the user for tracking in the consecutive frames of a video stream. Let Lmax denotes the highest permissible level in the multi-path tracking mode. Initially  the next frame of the video stream is obtained and the surrounding window of the object is searched for a probable matching. Further  whether the SAD of the block P with neighboring blocks (Q) is less than a threshold value (T) is determined. This threshold (T) can be defined by the user empirically. If the (SAD < T)  then the best neighboring blocks among Q blocks by SAD criteria is obtained using single path tracking. In an embodiment  the SAD criteria is same as finding the SAD between the blocks and repeating the same steps until the condition (SAD < T) holds true. Once the method finds that the (SAD < T) is not true  then the method can enter into the multi-path tracking mode for obtaining the trajectory of the object.
[0046] In the multi-path mode  assume a level (L) is assigned to zero and a parameter "K" is defined  which represents the number of nodes to be searched for obtaining the best possible match and these "K" nodes represent the neighboring nodes of the node reached in the single path tracking mode. Let S = {S1  S2 ...SK} represents the set of K best possible nodes that are the neighboring nodes of a node  which are reached in the single path tracking mode. Further  obtain the next frame of the video stream and initiate a search around the K locations corresponding to the blocks in S. For every element of the set S  the K best possibilities are selected from the list of its nested nodes. Thus  a set of K2 possible locations are found. This set can be represented by Mij= [{M11  M12..  M1K}  {M21  M22 ..M2K} ...{MK1  MK2 ...MKK}.
[0047] Then determine whether the SAD (Si  Mij) < T for any 1= i < k and 1 < j < K. if this condition is true  then select the Mij  which include minimum SAD with its parent Si and switch to the single path tracking.
[0048] Further  if level (L) is less than the Lmax  (defined empirically by the user)  select K best blocks (according to the minimum SAD criteria) from the list Mij and increment "L" value for repeating the multi-path tracking mode. Once the level (L) reaches the Lmax (defined empirically by the user)  then switch to the single point tracking mode.
[0049] FIG. 8 illustrates a tree representation of the object tracking  in accordance with various embodiments of the present invention. As depicted in the FIG. 8  the movement of the object is tracked by using both the single path tracking mode and multi-path tracking mode for obtaining the trajectory of the object in consecutive frames of a video stream. FIG. 8 shows the trajectory of the marked object in a frame 0. The trajectory of the object is obtained by tracking the movement of the object from the frame 0 to frame 8 using the single path tracking and multi-path tracking modes.
[0050] When the SAD is less than the threshold value (T) (which is defined by the user)  then the method follows the single path tracking mode. Further  when SAD is greater than the threshold value (T)  method enters into the multi-path tracking mode and increments the level (L) accordingly to obtain the trajectory of the object. The method includes switching between these two modes depending on the parameters. These parameters can be the maximum allowable level (Lmax) and the SAD threshold (T).
[0051] Once the maximum allowable level (Lmax) in the MPT mode is reached  the method automatically switches back to the single path tracking mode. Further  when the SAD is less than the threshold (T)  the method executes single path tracking mode and when the SAD crosses the threshold limit (T)  the method automatically switches into the multi-path tracking mode. The maximum allowable level (Lmax) and the SAD threshold (T) are defined and can be customized by the user based on the tracking requirements.
[0052] In an embodiment  the multi-path tracking method can be used in various mobile based applications. For example  this method can be applied to augmented reality applications where motion based analysis is required to fetch the data of a moving object. Similarly  the method can be applied in mobile healthcare where doctors and physicians can use such efficient tracking methodology to track movement of interesting objects. Even in remote or home surveillance using mobile devices  these fast and accurate tracking methods can be used.
[0053] The computational performance of the multi-path tracking method is described herein. An estimation of approximate number of nodes being processed during a complete execution of the disclosed method has been carried out. Let  a video stream includes N number of frames and the level of MPT is Lmax. In the worst case scenario  the tracking method may run in the MPT mode during the entire duration of the video stream. Thus  there will be a maximum of N/Lmax (N >> Lmax) number of calls to the MPT function. Assuming that each of the MPT is explored up to its fullest level Lmax  in such a scenario  total number of nodes being processed is estimated to be N/Lmax * (KLmax-1 – 1)/ (K-1)  which runs in O (NKLmax-1) time  where K is the number of paths being explored inside the MPT. If the method runs in the single path mode for the entire duration of the video stream  then only N number of nodes needs to be processed.
[0054] FIG. 9 illustrates a computing environment implementing the application  as disclosed in an embodiment herein. As depicted  the computing environment comprises at least one processing unit that is equipped with a control unit and an Arithmetic Logic Unit (ALU)  a memory  a storage unit  plurality of networking devices  and a plurality Input output (I/O) devices. The processing unit is responsible for processing the instructions of the algorithm. The processing unit receives commands from the control unit in order to perform its processing. Further  any logical and arithmetic operations involved in the execution of the instructions are computed with the help of the ALU. Processing unit can support more than one thread.
[0055] The overall computing environment can be composed of multiple homogeneous and/or heterogeneous cores  multiple GPUs of different kinds  special media and other accelerators. The processing unit is responsible for processing the instructions of the algorithm. The processing unit receives commands from the control unit in order to perform its processing. Further  any logical and arithmetic operations involved in the execution of the instructions are computed with the help of the ALU. Further  the plurality of process units may be located on a single chip or over multiple chips.
[0056] The instructions and codes required for the implementation are stored in either the memory unit or the storage or both. At the time of execution  the instructions may be fetched from the corresponding memory and/or storage  and executed by the processing unit.
[0057] In case of any hardware implementations various networking devices or external I/O devices may be connected to the computing environment to support the implementation through the networking unit and the I/O device unit.
[0058] The embodiments disclosed herein can be implemented through at least one software program running on at least one hardware device and performing network management functions to control the elements. The elements shown in Fig. 9 include blocks which can be at least one of a hardware device  or a combination of hardware device and software module.
[0059] The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can  by applying current knowledge  readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept  and  therefore  such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore  while the embodiments herein have been described in terms of preferred embodiments  those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the embodiments as described herein.

CLAIMS
What is claimed is:
1. A method for obtaining trajectory of an object using multi-path tracking mode  the method comprising:
marking a portion of said object in a frame of a video;
obtaining consecutive frames in said video;
tracking said marked portion of said object in said consecutive frames  by estimating sum of absolute difference;
comparing said sum of absolute difference to a sum of absolute difference threshold;
switching between said multi-path tracking mode and single path tracking mode based on said sum of absolute difference threshold; and
obtaining trajectory of said marked portion by combining said single path tracking mode and multi-path tracking mode.
2. The method of claim 1  wherein said marking further comprises dividing said frame into a plurality of blocks.
3. The method of claim 1  wherein said method tracks said marked portion in said consecutive frame of said video  when said sum of absolute difference of said plurality of blocks is less than said threshold.
4. The method of claim 1  wherein said tracking further comprises selecting a best block among said plurality of blocks in said single path tracking mode.
5. The method of claim 1  wherein said method switches to said multi-path tracking mode from said single path tracking mode when said sum of absolute difference of said plurality of blocks is greater than said threshold and assigns a level upon switching into said multi-path tracking mode  wherein said multi-path tracking mode terminates to said single path tracking mode when said level reaches a maximum level.
6. The method of claim 1  wherein said method in said multi-path tracking mode further comprises selecting possible blocks among said plurality of blocks for said marked portion in said consecutive frame and estimating said sum of absolute difference between said best possible blocks and said marked portion for selecting said best block.
7. The method of claim 6  wherein said method selects said best block for said marked portion among said best possible blocks based on minimum sum of absolute difference criteria.
8. The method of claim 7  wherein selecting said best block further comprises determining said sum of absolute difference of said best possible blocks are less than said threshold level.
9. The method of claim 8  wherein said method increments said level after selecting said best block for said marked portion in said consecutive frame.
10. The method of claim 1  wherein obtaining said trajectory further comprises combining tracked results of said single path tracking mode and multi-path tracking mode.