Apparatus and method for extracting object based on feature matching between segmented regions in images

• US 6,990,233 B2
• Filed: 01/18/2002
• Issued: 01/24/2006
• Est. Priority Date: 01/20/2001
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Chang-yeong, Park, Du-sik, Kim, Sang-Kyun, Kim, Ji-yeon
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US10/050,547
• Publication Number:
  US 20020136449A1
• Time in Patent Office: 1,467 Days
• Field of Search: 382/164, 382/171, 382/173, 382/190, 382/209, 382/219, 382/305
• US Class Current: 382/164
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching
• CPC Class Codes: G06V 10/759 Region-based matching

Abstract

An apparatus and method for extracting object based on feature matching between segmented regions in images are provided. The apparatus includes an image input unit for receiving a query image including an object and an object extraction target image from which the object included in the query image is to be extracted; an object position determination unit for determining a position of the object in the object extraction target image using pixel based color feature matching; an image segmentation unit for segmenting each of the query image and the object extraction target image into a plurality of regions using image features including color or texture; and an object region determination unit for performing matching between the segmented regions in the query image and the segmented regions in the determined position of the object in the object extraction target image using color or texture features and determining a final object region using similarity in spatial adjacency between matching regions obtained as a result of the matching. Accordingly, an image region of a particular object can be automatically extracted from an object extraction target image. Therefore, the apparatus can be applied to video editors, video authoring tool, object based video encoder, interactive video authoring tool, and the like.

Claims

1. An apparatus for extracting an object from an image, comprising:

an image input unit for receiving a query image including an object and an object extraction target image from which the object included in the query image is to be extracted;

an object position determination unit for determining a position of the object in the object extraction target image using pixel based color feature matching;

an image segmentation unit for segmenting each of the query image and the object extraction target image into a plurality of regions using image features including color or texture; and

an object region determination unit for performing matching between the segmented regions in the query image and the segmented regions in the determined position of the object in the object extraction target image using color or texture features and determining a final object region using similarity in spatial adjacency between matching regions obtained as a result of the matching.

2. An apparatus for extracting an object from an image, comprising:

an image input unit for receiving a guery image including an object and an object extraction target image from which the object included in the guery image is to be extracted;

an object position determination unit for determining a position of the object in the object extraction target image using pixel based color feature matching;

an image segmentation unit for segmenting each of the guery image and the object extraction target image into a plurality of regions using image features including color or texture; and

an object region determination unit for performing matching between the segmented regions in the guery image and the segmented regions in the determined position of the object in the object extraction target image using color or texture features and determining a final object region using similarity in spatial adjacency between matching regions obtained as a result of the matching, wherein the object position determination unit comprises;

a color histogram calculator for calculating color histograms with respect to the query image and the object extraction target image;

an image projector for replacing the pixel values with respect to the query image and the object extraction target image with ratio histograms; and

a candidate object position determiner for determining candidate object positions in the object extraction target image having the ratio histogram.

3. The apparatus of claim 2, wherein the color histogram calculator calculates the number of pixels in a quantized color space with respect to each of the query image and the object extraction target image.

4. The apparatus of claim 2, wherein the candidate object position determiner performs convolution on the value of a mask determined based on a minimum bounding box surrounding the object included in the query image and the object extraction target image having the ratio histogram, calculates color distance differences between pixels with respect to which the resulting values of the convolution is no less than a predetermined threshold in the object extraction target image, and determines pixels as candidate object positions according to the average of color distance differences obtained with respect to each of the pixels in increasing order of the average.

5. The apparatus of claim 2, wherein the image segmentation unit segments the query image and the object extraction target image into regions using the image features including color or texture.

6. The apparatus of claim 2, wherein the object region determination unit comprises:

a region matching unit for performing region matching with respect to the segmented regions of the query image and segmented regions corresponding to the object position in the object extraction target image using image features including at least color and texture and determining whether the object extraction target image includes an object according to the result of region matching;

an adjacency matrix calculator for calculating a spatial adjacency matrix with respect to the segmented query image and calculating a spatial adjacency matrix with respect to an image resulting from the region matching on the segmented object extraction target image which is determined as having the object;

a correspondence region detector for detecting correspondence regions between the query image and the object extraction target image using the adjacency matrixes calculated by the adjacency matrix calculator; and

a similarity calculator for calculating the similarity between the query image and the object extraction target image based on the correspondence regions and determining a final object region.

7. The apparatus of claim 6, wherein the region matching unit detects a segmented region, which includes a pixel at the determined position of the object and meets a mask determined based on a region surrounding the object in the query image, in the segmented object extraction target image, calculates a similarity distance between each detected region and each of the segmented regions of the query image, and determined whether the object extraction target image includes the object.

8. The apparatus of claim 6, wherein the adjacency matrix calculator assigns label numbers to the segmented regions of the query image and to segmented regions including the object of the query image in the object extraction target image and forms adjacency matrixes in which each element has a first value when corresponding regions are adjacent and has a second value when they are not adjacent, the adjacency matrixes showing information about how adjacent the segmented regions assigned the label numbers are in the query image and the object extraction target image, respectively.

9. The apparatus of claim 6, wherein the correspondence region detector forms a comparison matrix using the adjacency matrixes in different manners according to whether the number of the segmented regions in the query image is greater or less than the number of segmented region in the object extraction target image to show the correspondence regions between the query image and the object extraction target image.

10. The apparatus of claim 6, wherein the correspondence region detector forms a comparison matrix using the adjacency matrixes and using only segmented regions, which have most similar image features to the segmented regions having label numbers in the query image, in the object extraction target image to show the correspondence regions between the query image and the object extraction target image.

11. The apparatus of claim 10, wherein the correspondence region detector determines the segmented regions having the most similar image features to the segmented regions of the query image in the object extraction target image using a distance matrix and reconstructs the comparison matrix according to the correspondence regions between the query image and the object extraction target image.

12. The apparatus of claim 11, wherein the distance matrix has the label numbers of the query image as row values and has the label numbers of the object extraction target image as column values, and each element in the distance matrix is a distance between a region assigned one of the label numbers in the query image and a region assigned one of the label numbers in the object extraction target image.

13. The apparatus of claim 8, wherein the similarity calculator calculates the similarity by dividing the number of elements having the first value in an upper triangular matrix by the number of all elements in the upper triangular matrix in the comparison matrix.

14. A method of extracting an object from an image, comprising the steps of:

(a) receiving a query image including an object and an object extraction target image from which the object included in the query image is to be extracted;

(b) determining a position of the object in the object extraction target image using pixel based color feature matching;

(c) segmenting the query image and the object extraction target image into a plurality of regions using image features including color or texture; and

(d) performing matching between the segmented regions in the query image and the segmented regions in the determined position of the object in the object extraction target image using color or texture features and determining a final object region using similarity in spatial adjacency between matching regions obtained as a result of the matching.

32. A computer readable recording medium on which a program for executing the method of claim 14 in a computer is recorded.

15. A method of extracting an object from an image, comprising the steps of:

(a) receiving a query image including an object and an object extraction target image from which the object included in the query image is to be extracted;

(b) determining a position of the object in the object extraction target image using pixel based color feature matching;

(c) calculating color histograms with respect to the query image and the object extraction target image;

(d) replacing the color histograms with respect to the query image and the object extraction target image with ratio histograms;

(e) determining candidate object positions in the object extraction target image having the ratio histogram;

(f) segmenting the query image and the object extraction target image into a plurality of regions using image features including color or texture; and

(g) performing matching between the segmented regions in the guery image and the segmented regions in the determined position of the object in the object extraction target image using color or texture features and determining a final object region using similarity in spatial adjacency between matching regions obtained as a result of the matching.

16. The method of claim 15, wherein the step (c) comprises calculating the number of pixels at each bin in a quantized color space with respect to each of the query image and the object extraction target image.

17. The method of claim 16, wherein the step (d) comprises calculating the ratio histogram by dividing the number of pixels in each bin with respect to the query image by the number of pixels in all bins with respect to the query image.

18. The method of claim 16, wherein the step (d) comprises defining the ratio histogram as a ratio of the number of pixels in each bin with respect to the query image to the number of pixels in each bin with respect to the object extraction target image.

19. The method of claim 15, wherein the step (e) comprises the steps of:

(e1) performing convolution on the value of a mask determined based on a minimum bounding box surrounding the object included in the query image and the object extraction target image having the ratio histogram,

(e2) calculating color distance differences between pixels with respect to which the resulting values of the convolution is no less than a predetermined threshold in the object extraction target image; and

(e3) determining pixels as candidate object positions according to the average of color distance differences obtained with respect to each of the pixels in increasing order of the average.

20. The method of claim 19, wherein the mask at a pixel (x_p, y_p) is a circle defined by $\begin{array}{c}\end{array}$

W={255,(x-xp)2+(y-yp)2≤

W⁢

⁢

R0,o⁢

⁢

t⁢

⁢

h⁢

⁢

e⁢

⁢

r⁢

⁢

w⁢

⁢

i⁢

⁢

s⁢

⁢

e⁢

W⁢

⁢

R=α

⁡

(b⁢

⁢

s+(b⁢

⁢

l-b⁢

⁢

s)⁢

b⁢

⁢

sb⁢

⁢

l),

bl indicates the length of the longer side of the bounding box, bs indicates the length of the shorter side of the bounding box, and α

indicates a variable for adjusting the size of the mask.

21. The method of claim 19, wherein the average color distance difference is defined by ${\mathrm{AD}}_{\mathrm{pixelcolor}}=\frac{1}{N}$

∑

i=1N⁢

(Rq-Rd)2+(Gq-Gd)2+(Bq-Bd)2,

N indicates the number of valid pixels within the bounding box, q indicates the query image, and d indicates the object extraction target image.

22. The method of claim 15, wherein the step (g) comprises the steps of:

(g1) performing region matching with respect to the segmented regions of the query image and segmented regions corresponding to the object position in the object extraction target image using image features including color or texture and determining whether the object extraction target image includes an object according to the result of region matching;

(g2) calculating a spatial adjacency matrix with respect to the segmented query image and calculating a spatial adjacency matrix with respect to an image resulting from the region matching on the segmented object extraction target image which is determined as having the object;

(g3) detecting correspondence regions between the query image and the object extraction target image using the adjacency matrixes calculated in step (g2); and

(g4) calculating the similarity between the query image and the object extraction target image based on the correspondence regions and determining a final object region.

23. The method of claim 22, wherein the step (g1) comprises the steps of:

(g1-1) detecting a segmented region, which includes a pixel at the determined position of the object and meets a mask determined based on a region surrounding the object in the query image, in the segmented object extraction target image; and

(g1-2) calculating a distance difference in color or texture between each detected region and each of the segmented regions of the query image to determine whether the object extraction target image includes the object.

24. The method of claim 23, wherein the distance difference in color or texture is defined as a distance between two regions in a space of an image feature including color or texture, the distance between two regions is calculated from $D_{\mathrm{CT}}$

(x,y)=wc⁢

Dc⁡

(x,y)+wt⁢

Dt⁡

(x,y)wc+wt,

D_c(x,y) and D_t(x,y) indicate a distance between two regions x and y in a color space and a distance between the two regions x and y in a texture space, respectively, and w_c and w_t indicate weight coefficients, respectively, applied to the respective distances.

25. The method of claim 22, wherein the step (g2) comprises assigning label numbers to the segmented regions of the query image and to segmented regions including the object of the query image in the object extraction target image and forming adjacency matrixes in which each element has a first value when corresponding regions are adjacent and has a second value when they are not adjacent, the adjacency matrixes showing information about how adjacent the segmented regions assigned the label numbers are in the query image and the object extraction target image, respectively.

26. The method of claim 22, wherein the step (g3) comprises forming a comparison matrix using the adjacency matrixes in different manners according to whether the number of the segmented regions in the query image is greater or less than the number of segmented region in the object extraction target image to show the correspondence regions between the query image and the object extraction target image.

27. The method of claim 22, wherein the step (g3) comprises forming a comparison matrix using the adjacency matrixes and using only segmented regions, which have most similar image features to the segmented regions having label numbers in the query image, in the object extraction target image to show the correspondence regions between the query image and the object extraction target image.

28. The method of claim 22, wherein the step (g3) comprises determining the segmented regions having the most similar image features to the segmented regions of the query image in the object extraction target image using a distance matrix and reconstructing the comparison matrix according to the correspondence regions between the query image and the object extraction target image.

29. The method of claim 28, wherein the distance matrix has the label numbers of the query image as row values and has the label numbers of the object extraction target image as column values, and each element in the distance matrix is a distance between a region assigned one of the label numbers in the query image and a region assigned one of the label numbers in the object extraction target image.

30. The method of claim 22, wherein when each element in the adjacency matrixes has a first value when corresponding regions are adjacent and has a second value when they are not adjacent, the step (g4) comprises calculating the similarity by dividing the number of elements having the first value in an upper triangular matrix by the number of all elements in the upper triangular matrix in the comparison matrix.

31. The method of claim 27, wherein the step (d4), the similarity is calculated from $S=\frac{E_u}{M_u},$

and when each element in the adjacency matrixes has a first value when corresponding regions are adjacent and has a second value when they are not adjacent, E_u indicates the number of elements having the first value in an upper triangular matrix of the comparison matrix, and M_u indicates the number of all elements in the upper triangular matrix.