Method and apparatus for merging related image segments

• US 7,295,711 B1
• Filed: 10/23/2003
• Issued: 11/13/2007
• Est. Priority Date: 10/23/2002
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Prakash, Adityo, Chen, John S., Ratner, Edward R., Fleisher, Michael, Ahuja, Sachin, Horn, Gavin B.
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): CUNNINGHAM, GREGORY F
• Application Number:
  US10/692,466
• Time in Patent Office: 1,482 Days
• Field of Search: 345/622, 345/629, 345/630, 345/631, 345/FOR.216, 375/250, 382/164, 382/171, 382173-180, 382/225, 716/2
• US Class Current: 382/225
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/543 using regions

Abstract

One embodiment of the invention relates to a method of merging segments to form supersegments in an image. The image consists of a plurality of segments that are constituent portions of the image. At least one candidate segment(s) and at least one neighboring segment(s) for each candidate segment are identified. An error statistic for each pair, consisting of a candidate segment and a corresponding neighboring segment, is computed. A neighboring segment is determined that results in a smallest error statistic for a given candidate segment. A determination is also made as to whether the smallest error statistic is sufficiently small to merit merging of the corresponding pair of segments. The corresponding pair of segments is merged to create one supersegment. The supersegment is a new segment including all pixels formerly contained in one of the two segments that were merged.

Claims

1. A method of video encoding or decoding including merging segments to form supersegments in an image, wherein said image consists of a plurality of segments that are constituent portions of the image, the method of video encoding or decoding comprising:

identifying at least one candidate segment(s);

identifying at least one neighboring segment(s) for each candidate segment;

computing an error statistic for each pair, wherein each pair consists of a candidate segment and a corresponding neighboring segment;

determining a neighboring segment that results in a smallest error statistic for a given candidate segment;

determining whether said smallest error statistic is sufficiently small so as to be less than a threshold value so as to merit merging of the corresponding pair of segments; and

merging said corresponding pair of segments to create one supersegment if said smallest error statistic is less than the threshold value, wherein a supersegment is a new segment comprising all pixels formerly contained in one of the two segments that were merged,

wherein said error statistic is computed using one or more merging parameters selected from the group consisting of a difference in mean color between the two segments, a difference in color variance between the two segments, a measure of a color gradient along a common boundary between the two segments, a length of the common boundary, a total boundary length of the candidate segment, an area of the candidate segment, and an area of the neighboring segment.

2. The method of claim 1, wherein the error statistic for a pair consisting of a candidate segment and a neighboring segment is set above the threshold value if the common boundary between the segments is smaller than a cutoff percentage of the total boundary length of the candidate segment.

4. The method of claim 1, wherein the threshold value varies according to the area of the candidate segment.

6. The method of claim 1, wherein multiple neighboring segments are merged with a candidate segment wherein each of the neighboring segment'"'"'s error statistic is below the threshold value.

9. The method of claim 1, wherein said error statistic is calculated in a neighborhood of the common boundary between the candidate segment and the neighboring segment.

10. The method of claim 9, wherein said neighborhood of the common boundary consists of a fixed number of pixels on either side of and perpendicular to each boundary edge.

11. The method of claim 9, wherein said error statistics are calculated during a raster-scan through an array of pixels and stored in a table, and wherein said error statistics are updated whenever two or more segments are merged to form a supersegment to correct the values for the new supersegment and its neighboring segments,

whereby merging decisions for a plurality of candidate segments may be made by referring to the data contained in said table.

3. A method of video encoding or decoding including merging segments to form supersegments in an image, wherein said image consists of a plurality of segments that are constituent portions of the image, the method of video encoding or decoding comprising:

identifying at least one candidate segment(s);

identifying at least one neighboring segment(s) for each candidate segment;

computing an error statistic for each pair, wherein each pair consists of a candidate segment and a corresponding neighboring segment;

determining a neighboring segment that results in a smallest error statistic for a given candidate segment;

determining whether said smallest error statistic is sufficiently small so as to be less than a threshold value so as to merit merging of the corresponding pair of segments; and

merging said corresponding pair of segments to create one supersegment if said smallest error statistic is less than the threshold value, wherein a supersegment is a new segment comprising all pixels formerly contained in one of the two segments that were merged,

wherein the error statistic for a pair consisting of a candidate segment and a neighboring segment is set above the threshold value if the area of the neighboring segment is smaller than the area of the candidate segment.

5. A method of merging segments to form supersegments in an image, wherein said image consists of a plurality of segments that are constituent portions of the image, the method comprising:

identifying at least one candidate segment(s);

identifying at least one neighboring segment(s) for each candidate segment;

computing an error statistic for each pair, wherein each pair consists of a candidate segment and a corresponding neighboring segment;

determining a neighboring segment that results in a smallest error statistic for a given candidate segment;

determining whether said smallest error statistic is sufficiently small to merit merging of the corresponding pair of segments;

merging said corresponding pair of segments to create one supersegment if said smallest error statistic is sufficiently small to merit said merging, wherein a supersegment is a new segment comprising all pixels formerly contained in one of the two segments that were merged; and

using a tiebreak criterion in the case when more than one neighboring segment is sufficiently close to the minimum error statistic, said tiebreak criterion selecting the one of said neighboring segments that has smallest area.

7. A method of video encoding or decoding including merging segments to form supersegments in an image, wherein said image consists of a plurality of segments that are constituent portions of the image, the method of video encoding or decoding comprising:

identifying at least one candidate segment(s);

identifying at least one neighboring segment(s) for each candidate segment;

computing an error statistic for each pair, wherein each pair consists of a candidate segment and a corresponding neighboring segment;

determining a neighboring segment that results in a smallest error statistic for a given candidate segment;

determining whether said smallest error statistic is sufficiently small so as to be less than a threshold value so as to merit merging of the corresponding pair of segments; and

merging said corresponding pair of segments to create one supersegment if said smallest error statistic is less than the threshold value, wherein a supersegment is a new segment comprising all pixels formerly contained in one of the two segments that were merged,

wherein the error statistic E for a pair of segments is computed according to the formula E=Δ

c·

Δ

G, wherein Δ

G is a measure of the gradient along the boundary between the segments and Δ

c is a measure of the difference in mean color and color variance between the segments.

8. The method of claim 7, wherein:

Δ

c=Δ

m_yΔ

v_y+Δ

m_uΔ

v_u+Δ

m_vΔ

v_v, wherein Δ

m is a measure of the difference between the mean intensity values for the candidate and neighboring segments, wherein Δ

v is a measure of the difference between the variances of intensity values for the candidate and neighboring segments, and wherein the subscripts y, u, v denote the Y, U, and V color components, respectively;

G=w_yg_y+w_ug_u+w_vg_v, wherein each of g_y, g_u, and g_v are local color gradients (in the Y, U, and V color components) at a single boundary edge and w_y, w_u, and w_v are weights; and

Δ

G is found by taking the medians of the G values at every n consecutive edges of the common boundary and then taking the mean of this collection of median values.

12. A method of merging segments to form supersegments in an image, wherein said image consists of a plurality of segments that are constituent portions of the image, the method comprising:

identifying at least one candidate segment(s);

identifying at least one neighboring segment(s) for each candidate segment;

computing an error statistic for each pair, wherein each pair consists of a candidate segment and a corresponding neighboring segment;

determining a neighboring segment that results in a smallest error statistic for a given candidate segment;

determining whether said smallest error statistic is sufficiently small to merit merging of the corresponding pair of segments; and

merging said corresponding pair of segments to create one supersegment if said smallest error statistic is sufficiently small to merit said merging, wherein a supersegment is a new segment comprising all pixels formerly contained in one of the two segments that were merged,

wherein said error statistic is calculated using only the pixels in the neighboring segment which lie within an extended bounded box around the candidate segment.

13. An apparatus for video encoding or decoding including means for merging segments to form supersegments in an image, wherein said image consists of a plurality of segments that are constituent portions of the image, the apparatus comprising:

means to identify at least one candidate segment(s);

means to identify at least one neighboring segment(s) for each candidate segment;

means to compute an error statistic for each pair, wherein each pair consists of a candidate segment and a corresponding neighboring segment;

means to determine a neighboring segment that results in a smallest error statistic for a given candidate segment;

means to determine whether said smallest error statistic is sufficiently small to merit merging of the corresponding pair of segments; and

means to merge said corresponding pair of segments to create one supersegment if said smallest error statistic is sufficiently small to merit said merging, wherein a supersegment is a new segment comprising all pixels formerly contained in one of the two segments that were merged, and wherein said error statistic is computed using one or more merging parameters selected from the group consisting of a difference in mean color between the two segments, a difference in color variance between the two segments, a measure of a color gradient along a common boundary between the two segments, a length of the common boundary, a total length of a boundary of the candidate segment, an area of the candidate segment, and an area of the neighboring segment.

14. The apparatus of claim 13, wherein the apparatus is embodied in a computer that includes a CPU and memory and a specifically-designed application program.

15. The apparatus of claim 13, wherein the apparatus is embodied in a specifically-designed hardware device, including both processing and memory circuitry.