Apparatus and methods for object border tracking

• US 5,940,538 A
• Filed: 08/05/1996
• Issued: 08/17/1999
• Est. Priority Date: 08/04/1995
• Status: Expired due to Fees

• Current Assignee: Ehud Spiegel, Yosef Pastor
• Original Assignee: Ehud Spiegel, Yosef Pastor
• Inventors: Spiegel, Ehud, Pastor, Yosef
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/692,297
• Time in Patent Office: 1,107 Days
• Field of Search: 348/169, 348/384, 348/390, 348/403, 348/404, 348/407, 348/700, 348/170, 348/402, 348/413, 348/416, 348/699, 382/103, 382/209, 382/236, 382/278, 382/107, 382/199, 382/257, 364/516, 364/728.07, 345/473-475
• US Class Current: 382/236
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A tracking method including receiving a representation of an event including at least one dynamic object having a border and having at least one edge portion which is absent during at least a portion of the event and providing an ongoing indication of the location of the border of the object during the event. Apparatus for carrying out the method is also disclosed.

Claims

1. A method for tracking a border of a moving object through a sequence of images of the moving object including first and second images, the method comprising:

receiving the first image and an indication of a border of a moving object in the first image, the border comprising a multiplicity of border locations including border locations having locally distinctive features internal to the moving object and border locations having locally distinctive features external to the moving object;

selecting a plurality of special border locations to be tracked in the first image from among the multiplicity of border locations, wherein the plurality of special border locations are less than the total number of border locations, the selecting step including, for at least a portion of the border, preferring said border locations having at least one locally distinctive feature which is internal to the moving object and which is therefore generally conserved between images over said border locations having at least one locally distinctive feature which is external to the moving object;

tracking at least some of said plurality of special border locations from the first image to the second image; and

computing an estimated border in said second image based on an output of said tracking step and based on information characterizing said border in said first image; and

displaying said estimated border to a user.

2. A method according to claim 1 wherein at least one of said plurality of border locations comprises a location at which at least one border characteristic changes.

3. A method according to claim 2 wherein said border characteristic comprises at least one color adjacent to said border.

4. A method according to claim 1 wherein said tracking comprises disregarding a border location which, when tracked from said first image to said second image, is found to have moved differently from other adjacent border locations.

5. A method according to claim 4 wherein said disregarding step employs a relaxation technique to identify border locations which have moved differently from other adjacent border locations.

6. A method according to claim 1 wherein said computing step comprises projecting the border from the first image onto the second image such that each of said plurality of special border locations in said first image is transformed onto a corresponding one of the plurality of border locations in the second image and such that the configuration of the border in the first image, between special border locations, is preserved in the estimated border in said second image.

7. A method according to claim 6 wherein said projecting step comprises transforming a spline representation of the border in the first image such that each of said plurality of border locations in said first image is transformed onto a corresponding one of the plurality of border locations in the second image.

8. A method according to claim 6 wherein said projecting step comprises transforming a spline representation of the border in the first image such that each of said plurality of special border locations in said first image is transformed onto a corresponding one of the plurality of special border locations in the second image.

9. A method according to claim 1 and also comprising providing a first image seen from a first field of view and providing a second image seen from a different field of view.

10. A method according to claim 1 and also comprising providing first and second images each including at least one of a moving dynamic object and a dynamic background.

11. A method according to claim 1 and also including generating an effect which is applied differentially on different sides of said estimated border.

12. A method according to claim 11 wherein said effect is generated an displayed for an individual image before the effect is generated for a subsequent image.

13. A method according to claim 11 wherein said effect includes one of the following group of effects:

compositing;

retouching;

smoothing;

compression;

compositing;

painting;

blurring;

sharpening;

a filter operation; and

an effect which changes over time at different rates on different sides of said border.

14. A method according to claim 11 wherein said moving object is part of an event, said event includes a plurality of dynamic hotspot objects and said selecting, tracking, computing and displaying steps are performed for each of the plurality of dynamic hotspot objects during the event.

15. A method according to claim 14, the method also including the steps of:

using estimated borders of each of said hotspot objects to interpret a user'"'"'s selection of an individual one of said plurality of dynamic hotspot objects; and

displaying information regarding the individual dynamic hotspot object selected by the user.

16. A method according to claim 11 wherein said step of displaying said border comprises displaying a result of applying said effect without previously displaying a separate representation of said border.

17. A method according to claim 1 wherein said border is tracked over a sequence of images including the first and second images, and wherein the border includes at least one portion which is absent in at least one image within said sequence of images.

18. A method according to claim 1 and also comprising improving a first segment of said estimated border, corresponding to a second segment of the border of the first image, by:

identifying at least one edge adjacent to the first segment of said estimated border, said edge having adjacent colors which correspond to colors adjacent the second border segment; and

replacing said first segment of said estimated border with said edge.

19. A method according to claim 18 wherein said at least one edge adjacent to said first segment comprises a plurality of edges and said identifying step comprises selecting one of the plurality of edges so as to maximize a function of the following selection criteria:

closeness of the edge to the estimated borders and

similarity of the edge'"'"'s adjacent colors to the colors adjacent the second border segment.

20. A method according to claim 18 and also comprising:

operating an edge detector on a portion of the second image adjacent to at least a portion of said estimated border;

generating a data structure representing spatial relationships between edges detected by the edge detector; and

wherein said step of identifying at least one edge comprises comparing at least a portion of said estimated border to said data structure, thereby to select from among the edges in said data structure, edges which are adjacent to at least a portion of said estimated border, said edge having adjacent colors which correspond to colors adjacent the border portion in the first image.

21. A method according to claim 20 wherein said step of selecting a plurality of special border locations comprises searching said data structure for locally distinctive features which are generally conserved between images.

22. A method according to claim 1 and wherein said tracking step comprises searching for a plurality of locations in the second image which correspond respectively to the plurality of special border locations in the first image in that, for each special border location in the first image found to have a corresponding location in the second image, the locally distinctive feature possessed by the special border location in the first image is also possessed by the corresponding location in the second image.

23. A method according to claim 22 wherein, for at least one of said plurality of special border locations, said locally distinctive feature comprises a color junction adjacent the border and internal to the moving object.

24. A method according to claim 22 wherein, for at least one of said plurality of special border locations, said locally distinctive feature comprises a corner.

25. A method according to claim 1 wherein said border is tracked over a sequence i of images by repeatedly performing said selecting, tracking, computing and displaying steps wherein, for each repetition r, the first image comprises an image i-1 and the second image comprises an image i, and in the next repetition r+1, the first image comprises image i and the second image comprises image i+1.

26. A method according to claim 1 wherein said step of tracking comprises:

identifying candidate second image locations for each of the special border locations in the first image; and

selecting candidate second image locations corresponding respectively to at least some of said plurality of special border locations and characterized in that the relative arrangement of the selected candidate second image locations in the second image is locally similar to the relative arrangement of the special border locations in the first image.

27. A method according to claim 26 wherein said identifying step includes assigning an initial probability score to each candidate second image location, said score comprising an estimate of the probability that the candidate second image location corresponds to a particular special border location, and wherein said selecting step takes place at least partly in accordance with said scores.

28. A method according to claim 27 wherein said selecting step comprises employing a relaxation technique to perform disparity analysis iterations in order to discard some of said candidate second image locations until at most a single candidate second image location remains to correspond to each of the special border locations.

29. A method according to claim 26 wherein said selecting step comprises employing a relaxation technique to perform disparity analysis iterations in order to discard candidate second image locations until at most a single candidate second image location remains to correspond to each of the special border locations.

30. A method according to claim 1 and also comprising improving said estimated border based on external input.

31. A method according to claim 27 wherein said external input comprises human operator input.

32. A method according to claim 1 wherein said step of computing an estimated border comprises filling in an estimated border between first and second special border locations in the second image based on the configuration of the border in the first image between the first and second special border locations in the first image.

33. A method according to claim 1 and also comprising improving said estimated border by adjusting said estimated border to run through at least one edges adjacent the estimated border.

34. A method according to claim 33 wherein each of the edges is an interface between first and second colors, and

wherein a portion of the first image border interfaces between third and fourth colors, and

wherein a consideration in deciding whether or not to replace a portion of the estimated border, corresponding to said portion of the first image border, with a particular edge, is the extent of similarity between the first and third colors and the second and fourth colors.

35. A method according to claim 33 wherein said adjusting step comprises considering each special location along the border in turn, and for each individual special location, searching for a sequence of connected edges running between the individual special location and a special location adjacent thereto.

36. Apparatus for tracking a border of a moving object through a sequence of images of the moving object including first and second images, the apparatus comprising:

a border receiver operative to receive the first image and an indication of a border of a moving object in the first image, border comprising a multiplicity of border locations including border locations having locally distinctive features internal to the moving object and border locations having locally distinctive features external to the moving object;

a border selector operative to select a plurality of special border locations to be tracked in the first image from among the multiplicity of border locations, wherein the plurality of special border locations are less than the total number of border locations, the selecting step including, for at least a portion of the border, preferring said border locations having at least one locally distinctive feature which is internal to the moving object and which is therefore generally conserved between images over said border locations having at least one locally distinctive feature which is external to the moving object;

a border tracker operative to track at least some of said plurality of special border locations from the first image to the second image; and

border display apparatus operative to compute an estimated border in said second image based on an output of said tracking step and based on information characterizing said border in said first image; and

to display said estimated border to a user.