Method and apparatus for measuring color-texture distance, and method and apparatus for sectioning image into plurality of regions using measured color-texture distance

• US 20020090133A1
• Filed: 10/22/2001
• Published: 07/11/2002
• Est. Priority Date: 11/13/2000
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Sushko, Dmitry V., Chochia, Pavel A., Lee, Seong-Deok, Kim, Chang-Yeong, Kim, Sang-Kyun, Miller, Boris M.
• Granted Patent: US 7,030,885 B2
• Time in Patent Office: Days
• US Class Current: 382/164
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

A method and apparatus for measuring a color-texture distance and a method and apparatus for sectioning an image into a plurality of regions using the measured color-texture distance are provided. The method of measuring a color-texture distance includes the steps of: assigning different degrees of importance to a brightness difference, a saturation difference, and a hue difference between two points in a color feature space constituted of color feature values of pixels in an image, and adding the brightness difference, the saturation difference, and the hue difference in proportion to the assigned degrees of importance to calculate a color distance between the two points; obtaining a texture distance between the two points using a difference between texture feature values of the two points and weighting coefficients applied to multi scales of a texture, in a texture feature space constituted of texture feature values for the pixels; and multiplying a color weight value and a texture weight value by the color distance and the texture distance, respectively, adding the multiplication results to each other, and obtaining the color-texture distance between the two points. The degrees of importance are determined on the basis that a hue is more important than a brightness or a saturation, a color becomes black as the brightness approaches an absolute value, and the hue has an arbitrary value as the saturation approaches the absolute value.

Claims

1. A method of measuring a color-texture distance, comprising the steps of:

(a) assigning different degrees of importance to a brightness difference, a saturation difference, and a hue difference between two points in a color feature space constituted of color feature values of pixels in an image and adding the brightness difference, the saturation difference, and the hue difference in proportion to the assigned degrees of importance to obtain a color distance between the two points;

(b) obtaining a texture distance between the two points using a difference between texture feature values of the two points and weighting coefficients applied to multi scales of a texture, in a texture feature space constituted of texture feature values for the pixels; and

(c) multiplying a color weight value and a texture weight value by the color distance and the texture distance, respectively, adding the multiplication results to each other, and obtaining the color-texture distance between the two points,

wherein the degrees of importance are determined on a basis that a hue is more important than a brightness or a saturation, a color becomes black as the brightness approaches an absolute value, and the hue has an arbitrary value as the saturation approaches the absolute value.

2. The method of claim 1, wherein, in step (a), the color distance D_BHS1(x, y), wherein x and y denote the two points in the color feature space, is computed according to the following equation:

D_BHS1(x, y)=W_B|B(x)−

B(y)|+F_H[min(S(x),S(y))](a{overscore (B)}+b){overscore (S)}|H(x)−

H(y)|+F_S({overscore (S)}){overscore (B)}|S(x)−

S(y)|

where B(o), H(o), and S(o) denote the brightness, the hue, and the saturation for a point o, respectively, wherein the point o refers to at least one of point x and y, {overscore (B)} and {overscore (S)} denote an average of B(x) and B(y) and an average of S(x) and S(y), respectively, W_B, a and b are constants, and F_S(j) and F_H(j) denote linear correction functions for the saturation and the hue, respectively.

3. The method of claim 2, wherein the linear correction function F_S(j) or F_H(j) is j if j is less than 1, and 1 if j is greater than or equal to 1.

4. The method of claim 1, wherein, in step (a), the color distance D_BHS2²(x, y), wherein x and y denote the two points in the color feature space, is computed according to the following equation:

D_BHS2²(x, y)=W_B[B(x)−

B(y)]²+W_HF_B[B(x),B(y)]F_S[S(x),S(y)][H(x)−

H(y)]²+W_SF_B[B(x),B(y)][S(x)−

S(y)]²

where B(o), H(o), and S(o) denote the brightness, the hue, the saturation for a point o, respectively, wherein the point o refers to at least one of point x and Y, W_B, W_H and W_S are constants, and F_S(·

, ·

) and F_B(·

, ·

) denote nonlinear correction functions for the saturation and the brightness, respectively.

5. The method of claim 2, wherein, in step (b), the texture distance D_t(x, y) is computed as expressed by the following equation:

6. The method of claim 5, further comprising the steps of:

(d) smoothing the input image a predetermined number of times and enhancing edges in the smoothed image;

(e) calculating the color feature values and the texture feature values on a pixel-by-pixel basis and returning to step (a);

(f) after step (c), comparing the color-texture distance with a first threshold value, segmenting the image into regions according to the comparison result, and generating an image graph from a fundamental region section map including information about the segmented regions of the image, based on a pyramidal recursive approach; and

(g) comparing the color-texture distance with a second threshold value, merging regions marked in the image graph according to the comparison result to generate a final image graph.

7. The method of claim 6, wherein the color-texture distance used in step (f) is determined using the predetermined color weight value w_c and the predetermined texture weight value w_t.

8. The method of claim 7, wherein the color-texture distance used in step (g) is determined using the color weight value w_c(u′

, v′

) and the texture weight value w_t(u′

, v′

), both of which vary depending on features of segmented regions u′ and

v′

.

9. The method of claim 8, wherein the features of the segmented regions includes a texture degree t(u′

, v′

), a size p(u′

, v′

) and a saturation s(u′

, v′

) for the segmented regions u′ and

v′

.

10. The method of claim 9, wherein the color weight value w_c(u′

, v′

) is computed as expressed by the following equation;

w_c(u′

, v′

)=ŵ

_c+ŵ

_t[1−

t(u′

, v′

)p(u′

, v′

)]s(u′

, v′

)

where ŵ

_c and ŵ

_t denote color and texture weighting constants, respectively,

11. The method of claim 10, wherein step (g) comprises the steps of:

(g1) merging the two segmented regions u′ and

v′

marked in the image graph according to the result of comparing the color-texture distance with the second threshold value;

(g2) comparing the second threshold value with the color-texture distance obtained with the color weight value w_c(u−

, v″

) and the texture weight value w_t(u″

, v″

) determined when the color weighting constant ŵ

_c is set to “

0” and

the color and texture distances calculated when W_H<

<

W_B, and W_S<

<

W_B, where u″ and

v″

denote two regions marked in the image graph in which the final result of merging the regions in step (g1) is reflected, and merging the two regions u″ and

v″

according to the comparison result; and

(g3) comparing the second threshold value with the color-texture distance calculated using the color weight value w_c(u′

″

, v′

″

) and the texture weight value w_t(u′

″

, v′

″

) determined when ŵ

<

<

ŵ

_t, where u″ and

v″

denote two regions marked in the image graph in which the final result of merging the regions in step (g2) is reflected, merging the two regions u′

″ and

v′

″

according to the comparison result, and generating the final image graph by reflecting the final result of merging the two regions,

wherein the second threshold value varies depending on sizes of the regions.

13. The apparatus of claim 12, wherein the color distance calculator computes the color distance D_BHS1(x, y), wherein x and y denote the two points in the color feature space, according to the following equation:

D_BHS1(x, y)=W_B|B(x)−

B(y)|+F_H[min(S(x), S(y))](a{overscore (B)}+b){overscore (S)}|H(x)−

H(y)|+F_S({overscore (S)}){overscore (B)}|S(x)−

S(y)|

where B(o), H(o), and S(o) denote the brightness, the hue, the saturation for a point o, respectively, wherein the point o refers to at least one of point x and y, {overscore (B)} and {overscore (S)} denote an average of B(x) and B(y) and an average of S(x) and S(y), respectively, W_B, a and b are constants, and F_S(j) and F_H(j) denote linear correction functions for the saturation and the hue, respectively.

14. The apparatus of claim 13, wherein the linear correction function F_S(j) or F_H(j) is j if j is less than 1, and 1 if j is greater than or equal to 1.

15. The apparatus of claim 12, wherein the color distance calculator computes the color distance D_BHS2²(x, y), wherein x and y denote the two points in the color feature space, according to the following equation:

D_BBHS2²(x, y)=W_B[B(x)−

B(y)]²+W_HF_B[B(x), B(y)]F_S[S(x), S(y)][H(x)−

H(y)]²+W_SF_B[B(x), B(y)][S(x)−

S(y)]²

where B(o), H(o), and S(o) denote the brightness, the hue, the saturation for a point o (the point o refers to either point x or y), respectively, W_B, W_H, and W_S are constants, and F_S(·

, ·

) and F_B(·

, ·

) denote nonlinear correction functions for the saturation and the brightness, respectively.

16. The apparatus of claim 13, wherein the texture distance calculator computes the texture distance D_t(x, y) according to the following equation:

17. An apparatus for sectioning an input image into a plurality of regions using the color-texture distance output from the color-texture distance generator of claim 16, the apparatus comprises:

an image preprocessor that smooths the input image a predetermined number of times, enhances edges in the smoothed image, and outputs the resulting image;

a feature value calculator that calculates the color feature values and the texture feature values from the image output from the image preprocessor for each pixel and outputs the calculated color and texture feature values to the apparatus for measuring a color-texture distance;

a main region section unit that compares the color-texture distance output from the color-texture distance generator with a first threshold value, segments the image into regions according to the comparison result, generates an image graph from a fundamental region division map including information about the segmented regions based on a pyramidal recursive approach, and outputs the generated image graph; and

an image graph simplification unit that compares the color-texture distance output from the color-texture distance generator with a second threshold value, simplifies the image graph according to the comparison result, and outputs a final image graph generated from the simplified image graph.

18. The apparatus of claim 17, wherein the color-texture distance generator multiplies the predetermined color weight value w_c by the color distance, multiplies the predetermined texture weight value w_t by the texture distance, adds the multiplication results to each other, and outputs the addition result to the main region section unit as the color-texture distance.

19. The apparatus of claim 18, wherein the color-texture distance generator multiplies the color weight value w_c(u′

, v′

) and the texture weight value w_t(u′

, v′

), both of which vary depending on a texture degree t(u′

, v′

), a size p(u′

, v′

) and a saturation s(u′

, v′

) for segmented regions u′ and

v′

, by the color and texture distances, respectively, adds the multiplication results, and outputs the addition result to the image graph simplification unit as the color-texture distance.

20. The apparatus of claim 19, wherein the color-texture distance generator comprises:

a color weight value calculator that computes the color weight value w_c(u′

, v′

) as expressed by the following equation;

w_c(u′

, v′

)=ŵ

_c+ŵ

_t[1−

t(u′

, v′

)p(u′

, v′

)]s(u′

, v′

)

where ŵ

_c and ŵ

_t denote color and texture weighting constants, respectively,

$t<br><br>\left(u^{\mathrm{\prime <br><br>}},v^{\mathrm{\prime <br><br>}}\right)=\frac{T<br><br>\left(u^{\mathrm{\prime <br><br>}}\right)+T<br><br>\left(v^{\mathrm{\prime <br><br>}}\right)}{2*T_{\max }},$

wherein T_max denotes a maximum of the texture degrees for the segmented regions u′ and

v′

,

$p<br><br>\left(u^{\mathrm{\prime <br><br>}},v^{\mathrm{\prime <br><br>}}\right)=F<br><br>\left[\frac{\min <br><br>\left[P<br><br>\left(u^{\mathrm{\prime <br><br>}}\right),P<br><br>\left(v^{\mathrm{\prime <br><br>}}\right)\right]}{P_o}\right],$

wherein P_o denotes a threshold value for the sizes of the segmented regions u′ and

v′

, and

$s<br><br>\left(u^{\mathrm{\prime <br><br>}},v^{\mathrm{\prime <br><br>}}\right)=0.5+0.5<br><br>F<br><br>\left[\frac{\max <br><br>\left[S<br><br>\left(u^{\mathrm{\prime <br><br>}}\right),S<br><br>\left(v^{\mathrm{\prime <br><br>}}\right)\right]}{S_o}\right],$

wherein S_o denotes a threshold value of saturation for the segmented regions u′ and

v′

; and

a texture weight value calculator that computes the texture weight value wt (u′

, v′

) as expressed by the following equation;

w_t(u′

, v′

)=[1−

s(u′

, v′

)](ŵ

_c+ŵ

_t)+ŵ

_ts(u′

, v′

)t(u′

, v′

)p(u′

, v′

).

21. The apparatus of claim 20, wherein the image graph simplification unit comprises:

a primary region merging portion that compares the color-texture distance with the second threshold value, merges the two segmented regions u′

an v′

marked in the image graph according to the comparison result, and outputs a first intermediate image graph generated by reflecting the final result of merging;

a secondary region merging portion that compares a first color-texture distance with the second threshold value, merges two regions u″ and

v″

marked in the first intermediate image graph according to the comparison result, and outputs a second intermediate image graph generated by reflecting the final result of merging; and

a tertiary region merging portion that compares a second color-texture distance with the second threshold value, merges two regions u′

″ and

v′

″

marked in the second intermediate image graph according to the comparison result, and outputs the final image graph generated by reflecting the final result of merging,

wherein the color-texture distance generator multiplies the color weight value w_c(u″

, v″

) calculated from the color weight value calculator and the texture weight value w_t(u″

, v″

) calculated from the texture weight value calculator when the color weighting constant ŵ

_c is set to “

0”

by the color and texture distances calculated from the color and texture distance calculators, respectively, when W_H<

<

W_B, and W_S<

<

W_B, adds the multiplication results, and outputs the addition result as the first color-texture distance,

wherein the color-texture distance generator multiplies the color weight value w_c(u′

″

, v′

″

) and the texture weight value w_t (u′

″

, v′

″

) output from the color weight value calculator and the texture weight value calculator, respectively, when ŵ

_t<

<

ŵ

_c, by the color and texture distances, respectively, adds the multiplication results, and outputs the addition result as the second color-texture distance; and

wherein the second threshold value varies depending on the sizes of the regions.

12. An apparatus for measuring a color-texture distance comprising:

a color distance calculator that assigns different degrees of importance to a brightness difference, a saturation difference, and a hue difference between two points in a color feature space constituted of color feature values for pixels in an image, adds the brightness difference, the saturation difference, and the hue difference in proportion to the assigned degrees of importance, and outputs the added result as a color distance between the two points;

a texture distance calculator that inputs texture feature values for the two points in a texture feature space constituted of texture feature values for the pixels in the image, detects a difference between the input texture feature values, calculates a texture distance between the two points from weighting coefficients applied to multiple scales of a texture and the detected difference, and outputs the calculated texture distance; and

a color-texture distance generator that multiplies a color weight value by the color distance output from the color distance calculator, multiplies a texture weight value by the texture distance output from the texture distance calculator, adds the multiplication results together, and outputs the addition result as a color-texture distance,

wherein the degrees of importance are determined on a basis that a hue is more important than a brightness or a saturation, a color becomes black as the brightness approaches an absolute value, and the hue has an arbitrary value as the saturation approaches the absolute value.