Object boundary detection using a constrained viterbi search

• US 6,266,443 B1
• Filed: 12/22/1998
• Issued: 07/24/2001
• Est. Priority Date: 12/22/1998
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Lin, I-Jong, Vetro, Anthony, Sun, Huifang, Kung, Sun-Yuan
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/219,062
• Time in Patent Office: 945 Days
• Field of Search: 382/199, 382/200, 382/201, 382/202, 382/203, 382/107, 382/226, 382/227, 382/228
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling

Abstract

A method detects a boundary in a sequence of two-dimensional images where each image has multiple intensity value points. Filtering and motion analysis is applied on each image to produce motion enhanced images. Initial search parameters are determined from a dynamic snake model applied to the motion enhanced images. Each motion enhanced image is searched for a potential boundary using the search parameters. The potential boundary is projected into the motion enhanced image of a previous, current, and next image, and the search parameters of the previous, current, and next images are updated. The searching, projecting, and updating repeat until a predetermined level of convergence is reached.

Claims

1. A method for detecting a boundary in a two-dimensional image of intensity value points, comprising the steps of:

applying a convolutional kernel to the intensity value points of the image to produce an enhanced image;

supplying a boundary score function;

maximizing the boundary score function using a constrained Viterbi search to determine the boundary.

2. The method of claim 1 wherein the constrained Viterbi search follows intensity value points of a potential boundary in the image in only one angular direction, and wherein the boundary score function is maximized up to a last intensity value points linked to the potential boundary.

3. The method of claim 2 wherein the angular direction is increasing.

4. The method of claim 2 wherein the angular direction is decreasing.

5. The method of claim 2 further supplying the search parameters comprises:

estimating a center of the boundary;

estimating a radius of the boundary; and

estimating a first intensity value point on a potential boundary to locate an edge portion of the boundary.

6. The method of claim 5 wherein the maximizing and estimating steps are iteratively repeated until a termination condition is reached.

7. The method of claim 6 wherein the repeating terminates when the potential boundary converges.

8. The method of claim 6 wherein the repeating terminates after a predetermined number of iterations.

10. The method of claim 1 further including smoothing the final boundary.

11. The method of claim 1 further including segmenting a video object plane using the final boundary.

12. The method of claim 1 further including encoding the video object plane.

9. A method for detecting a boundary in a sequence of two-dimensional images, each image having a plurality of intensity value points, comprising the steps of:

filtering and motion analyzing each image to produce enhanced images;

determining initial search parameters from the enhanced images;

defining search constraints;

searching each enhanced image for a potential boundary using the search parameters, the search constraints, and a Viterbi search; and

projecting the potential boundary into the enhanced image of a previous, current, and next image;

updating the search parameters for the previous, current, and next image; and

repeating the constrained searching, projecting, and updating until the potential boundary converges on a final boundary.

13. A method of determining a boundary of an object included in an image, comprising:

predicting a boundary representing the object included in the image;

determining a reference point corresponding to the predicted boundary; and

determining the boundary of the object in the image based on the determined reference point and the predicted boundary.

14. A method according to claim 13, wherein the reference point is a predicted boundary center point of the predicted boundary.

15. A method according to claim 13, wherein:

determining the boundary includes determining a relationship between the predicted boundary and the determined reference point.

16. A method according to claim 13, segmenting the object based on the determined boundary to form a separate video object plane.

17. A method of determining a boundary of an object included in an image, the image being one of multiple images represented in multiple video frames, each of the multiple images including the object, comprising:

predicting boundaries, each representing the object included in a respective one of the multiple images;

determining reference points, each of the determined reference points corresponding to a respective one of the predicted boundaries; and

determining the boundary of the object in the image included in the multiple video frames, based on the determined reference points and the predicted boundaries.

18. A method according to claim 17, wherein predicting the boundaries includes:

partitioning each of the multiple video frames into blocks;

performing motion estimation on each of the blocks of each of the multiple video frames in relation to the blocks of a prior one of the multiple video frames and a subsequent one of the multiple video frames to derive motion field information for that one video frame; and

the predicted boundary representing the object included in the image in the one video frame is predicted based on the motion field information derived for that one video frame.

19. A method according to claim 18, wherein:

predicting boundaries further includes deriving a one-dimensional intensity map for the one video frame based on the motion field information derived for that one video frame.

20. A method according to claim 17, wherein the predicted boundaries are predicted third boundaries and predicting the predicted third boundaries includes:

predicting first boundaries, each of the predicted first boundaries representing the object included in the image in a respective one of the multiple video frames, and

predicting second boundaries, each of the predicted second boundaries being based on a first relationship between (i) each point along each of the predicted first boundaries and (ii) at least one of its corresponding reference point, other points along that predicted first boundary, and edges of the respective video frame having the image including the object represented by that predicted first boundary; and

each of the predicted third boundaries is based on a second relationship between (i) each of the predicted second boundaries and (ii) one or more of the other of the predicted second boundaries.

21. A method according to claim 20, wherein:

the one or more other predicted second boundaries are two other predicted second boundaries;

the video frame having the image including the object represented by one of the two other predicted second boundaries precedes the video frame having the image including the object represented by the predicted second boundary to which it is being related; and

the video frame having the image including the object represented by the other of the two other predicted second boundaries is subsequent to the video frame having the image including the object represented by the predicted second boundary to which it is being related.

22. A method according to claim 17, wherein determining the boundary includes:

determining mutually exclusive estimated boundaries based on a relationship between each of the predicted boundaries and the determined corresponding reference point; and

determining the boundary based on relationships between respective of the determined mutually exclusive estimated boundaries.

23. A method according to claim 22, wherein determining the boundary includes:

modifying each of the determined mutually exclusive estimated boundaries based on a radial function and angles to the determined corresponding reference point of points along that determined mutually exclusive estimated boundary;

determining the boundary based on relationships between respective of the modified mutually exclusive estimated boundaries.

24. A method of detecting a boundary of an object included in an image, comprising:

predicting a boundary of the object;

enhancing the predicted boundary;

establishing Viterbi search parameters corresponding to a radial function; and

performing a Viterbi search, constrained by the established Viterbi search parameters, on the enhanced predicted boundary to determine the boundary of the object.