KR102114738B1 - Method for generating trimap automatically in alpha matte through unknown region detection and apparatus thereof - Google Patents

Abstract

The present invention relates to a method for automatically generating a trimap of an alpha matte through unknown area detection and a device thereof, and more particularly, to a method for improving the quality of an alpha matte by reducing the number of artifacts and calculation time of the alpha matte by combining image saliency, graph cut segmentation (lazy snapping) and fuzzy c-means (FCM) clustering to generate a trimap when performing image matting for accurately extracting a foreground and background from an input image. The method comprises: a foreground queue estimation step; a foreground segmentation step; and an unknown area detection step.

Description

Method and device for automatic generation of tri-map of alpha matte through detection of unknown area {METHOD FOR GENERATING TRIMAP AUTOMATICALLY IN ALPHA MATTE THROUGH UNKNOWN REGION DETECTION AND APPARATUS THEREOF}

The present invention relates to a method and apparatus for automatically generating a trimap of alpha matte through detection of an unknown area, and more particularly, when performing image matting that accurately extracts a foreground and a background from an input image, extrudes an image. By combining (image saliency), graph cut segmentation (lazy snapping), and fuzzy c-means (FCM) clustering to automatically generate a trimap, it reduces the number of artifacts and shortens the computation time of the alpha matte. A method and apparatus for improving the quality of an alpha matte.

Typically in the filmmaking industry, visual effects artists use chroma keying to synthesize one or more image objects (for example, an actor in the case of a movie) into another background image (for example, an environment similar to planet Mars). . However, the chroma keying requires a controlled constant color scene (green or blue), and the foreground extracted with the chroma keying may include artifacts, and the visual effect artist must manually correct it.

Accordingly, many researchers and developers in academia and industry are interested in image mating that can extract a foreground from an image with background, and are actively conducting research and development to secure technology for the image mating.

The image matting refers to accurately extracting the foreground and background of an image, and is one of the core processing steps of an image editing, video editing, and movie production application.

At this time, the image matting requires a trimap as an input, and a manually drawn trimap is required to generate a high quality alpha matte.

However, as described above, there is a problem in that it takes a lot of time for the user to manually create the trimap. For example, in the related art, a user draws a trimap by hand using a brush set, a paint tool, etc. provided by the software, and uses the trimap as an input for image matting, but each triapp has a short time (about 2 minutes) Given the working time of the degree), an experienced user can draw a trimap within a given time without difficulty, but for a beginner it is difficult to draw a trimap within a given time.

In order to solve the problem of manually creating such a trimap, an algorithm for automatically generating the trimap has been developed and used.

However, in the algorithm that automatically generates most of the currently used trimaps, depth information is required to divide the foreground object, and the depth information has a problem of limiting the practical applicability of the algorithm.

In addition, in order to create an unknown area, a dilation operation was conventionally used, but since the unknown area includes foreground and background pixels, the trimap generated by the expansion is not optimal and is not optimized. The alpha matte generated by the non-trimap has a problem in which a lot of artifacts that degrade the quality of the alpha matte (meaning that the alpha matte contains background pixels) are included.

Therefore, in the present invention, when generating a trimap for image matting that accurately extracts the foreground and background from the input image, the optimal trimap is automatically generated by combining image extrusion, graph cut segmentation, and FCM clustering to automatically generate the trimap. It is intended to propose a method for improving the quality by reducing the number of artifacts occurring in the boundary area of the alpha matte through an optimal trimap and by shortening the computation time of the alpha matte.

In particular, the present invention does not rely on depth information required to divide the foreground object by allowing the unknown region to include only pixels representing color mixing, not the foreground or background pixels, and detects the detection of the unknown region. To this end, we will use a clustering-based approach and propose a method to generate an optimal trimap fully automatically.

Next, the prior art existing in the technical field of the present invention will be briefly described, and then the technical matters to be differentiated from the prior art will be described.

First, Korean Registered Patent No. 116649 (2012.08.23.) Relates to border mating by dynamic programming, and is relatively continuous along the boundary of the extracted subject (for example, to limit color bleeding and / or artifacts). It relates to a border matting technique that produces transparency (or alpha values).

That is, the prior art describes a technique for providing more efficient and improved border matting to the extracted foreground image without requiring excessive user interaction.

Also, Korean Registered Patent No. 16,4801 (2016.05.26.) Relates to a matting method for extracting a foreground object and an apparatus for performing the same, extracting at least one pixel from an input image and a trimap, at least one non-local Extracting neighboring pixels to calculate a first processing cost value, extracting at least one local neighboring pixel to calculate a second processing cost value, and at least one based on the first processing cost value and the second processing cost value And performing mating on the input image by estimating the opacity value for each pixel of.

That is, the prior art extracts neighboring pixels generating each of the pixels constituting the input image and non-local relationships and local relationships to extract objects in the foreground, performs high-quality image matting, and provides image editing software for various purposes. It describes methods and apparatus that can be applied.

As a result of examining the prior arts above, the prior arts are configured to perform matting without excessively requiring user interaction, extracting neighboring pixels that generate non-local and local relationships with the pixels of the input image, and mating the image. However, the present invention does not perform image matting while reducing user intervention, as in the prior art, but creates a trimap for image matting without direct user intervention. As a technical feature for automatically generating an optimal trimap based on image extrusion, graph cut segmentation, and FCM clustering, there is no description or any suggestion in the prior art regarding the configuration related thereto, The technical differences of the present invention are obvious.

In particular, by making sure that the unknown area contains only pixels representing color mixing, not the foreground or background pixels, it does not rely on the depth information needed to segment the foreground object, and is fully automatic using a clustering-based approach for detection of the unknown area. The configuration for generating the optimal trimap is a characteristic technical configuration of the present invention which is not presented at all in the prior art.

The present invention was created to solve the above problems, and a method and apparatus capable of automatically generating a trimap without direct user intervention when performing image matting that accurately extracts the foreground and background from the input image It aims to provide.

Another object of the present invention is to provide a method and apparatus for automatically generating an optimal trimap by combining image extrusion, graph cut segmentation, and FCM clustering when generating an optimal trimap for image matting. Is done.

In addition, the present invention does not rely on the depth information required to divide the foreground object, so that the unknown area includes only pixels representing color mixing, not the foreground or background pixels, and uses a clustering-based approach for detection of the unknown area. Another object is to provide a method and apparatus capable of generating an optimal trimap completely automatically.

In addition, the present invention generates an alpha matte through an automatically generated optimal trimap, thereby reducing the number of artifacts so that the alpha matte does not include background pixel artifacts, and also shortening the computation time of the alpha matte. Another object is to provide a method and apparatus for improving the quality of the alpha matte.

A method for automatically generating a trimap of alpha matte through detection of an unknown region according to an embodiment of the present invention, in a trimap automatic generation device, uses a pixel-level extrusion map to set a foreground cue for the position of a foreground object in an input image. An estimating foreground queue; In the trimap automatic generation device, graph cut segmentation based on the foreground cue for the estimated position of the foreground object, the background cue generated by defining a corner region of the input image as a background seed, and a pre-computed oversegmented input image a foreground segmentation step of dividing a foreground object and a background from the input image by performing lazy snapping, and segmenting the divided foreground object; And in the trimap automatic generation device, using fuzzy c-means (FCM) clustering, an unknown region detection that generates a trimap by identifying mixed pixels including a foreground and a background color in a boundary region of the segmented foreground object It characterized in that it comprises a step.

In addition, the foreground cue estimating step includes: an image input step of receiving an input image for performing image matting in the trimap automatic generation device; A protrusion map generation step of dividing the received input image into a predetermined area and generating a protrusion map based on the divided region contrast, region background, and region property; A protrusion map quantization step of quantizing the generated protrusion map to generate a quantized protrusion map; A binarization step of generating a binarized projection map by binarizing the generated quantized projection map; And a foreground queue for outputting the eroded binary map to be used as a foreground queue for performing graph cut segmentation in the foreground segmentation step by eroding the binarized protrusion map and maintaining only the largest blob. And an output step.

In addition, the foreground segmentation step, in the trimap automatic generation device, receiving a foreground queue for the estimated position of the foreground object and providing a foreground queue as an input for graph cut segmentation; Defining a corner region of the input image as a background seed to generate a background queue, and providing a background queue to provide the generated background queue as an input for graph cut segmentation; An over-segment image providing step of over-segmenting the input image into a plurality of super pixels and providing the over-segmented input image as an input for graph cut segmentation; A graph cut segmentation step of dividing a foreground object and a background from the input image based on the foreground cue, a background cue, and an overdivided input image; And a foreground object segmentation step of segmenting the divided foreground object.

In addition, the detecting of the unknown area may include: an expansion step of expanding the boundary area of the segmented foreground object in the trimap automatic generation device; An ROI processing step of setting a boundary region of the expanded foreground object as an ROI (interest region) and dividing the set ROI into n 패치 n patches; A fuzzy c-average (FCM) clustering for each divided patch, and an unknown region generation step of generating an unknown region by identifying mixed pixels including a foreground and a background color for each patch based on the result of the execution; An image merging step of merging the images for each patch processed in the step of generating the unknown area into one image; And a trimap generation step of generating a trimap based on the merged image.

Further, in the foreground segmentation step, when the tri-cue automatic generation device defines and generates the background cue as a background seed of a corner region of the input image, the foreground object is located in the center of the input image, and the input image Characterized in that the corner is generated based on the assumption that it is likely to include a background cue.

In addition, in the detecting of the unknown area, the trimap auto-generation device divides the ROI extracted from the boundary area of the foreground object into a patch of size n ㅧ n, and performs fuzzy c-means (FCM) clustering for each divided patch. In the process, each patch is expressed as a lightness, a green-red component, and a blue-yellow component, but discarding the brightness and maintaining only the green-red component and the blue-yellow component to identify the mixed pixel.

In addition, the apparatus for automatically generating a tri-map of alpha matte through detection of an unknown area according to an embodiment of the present invention estimates a foreground queue for estimating a foreground queue for a position of a foreground object in an input image using a pixel-level protrusion map module; Graph cut segmentation (lazy snapping) is performed based on the foreground cue for the estimated position of the foreground object, the background cue generated by defining the corner region of the input image as a background seed, and the pre-calculated oversegmented input image. A foreground segmentation module for dividing the foreground object and the background from the input image and segmenting the divided foreground object; And a fuzzy c-means (FCM) clustering, an unknown area detection module for generating a trimap by identifying mixed pixels including a color of a foreground and a background in a boundary area of the segmented foreground object. do.

In addition, the foreground queue estimation module, an image input unit for receiving an input image for performing image matting; A protrusion map generator for dividing the received input image into a predetermined area, and generating a protrusion map based on the divided region contrast, region background, and region property; A protrusion map quantization unit to quantize the generated protrusion map to generate a quantized protrusion map; A projected map binarization unit that binarizes the generated quantized projected map to generate a binarized projected map; And a foreground queue for outputting the eroded binary map to be used as a foreground queue for performing graph cut segmentation in the foreground segmentation module by eroding the binarized protrusion map and maintaining only the largest blob. And an output unit.

In addition, the foreground segmentation module includes: a foreground queue providing unit that receives a foreground queue for a position of a foreground object estimated by the foreground queue estimation module and provides it as an input for graph cut segmentation; A background queue providing unit defining a corner area of the input image as a background seed to generate a background queue, and providing the generated background queue as an input for graph cut segmentation; An over-segmentation image providing unit for over-segmenting the input image into a plurality of super pixels, and providing the over-segmented input image as an input for graph cut segmentation; A graph cut segmentation unit dividing a foreground object and a background from the input image based on the foreground cue, a background cue, and an oversegment input image; And a foreground object segmentation unit for segmenting the divided foreground object.

In addition, the unknown area detection module includes: an expansion unit that expands a boundary area of the segmented foreground object; An ROI processing unit configured to set a boundary region of the expanded foreground object as an ROI (interest region), and divide the set ROI into n ㅧ n patches; A fuzzy c-average (FCM) clustering for each divided patch, and an unknown region generating unit for generating an unknown region by identifying mixed pixels including a foreground and a background color for each patch based on the result of the execution; An image merging unit that merges the images of each patch processed by the unknown region generating unit into a single image; And a trimap generator for generating a trimap based on the merged image.

In addition, when the foreground segmentation module generates the background cue by defining a corner region of the input image as a background seed, the foreground object is located in the center of the input image, and the corner of the input image includes a background queue. It is characterized by generating based on the assumption that the likelihood is high.

In addition, in the process of performing fuzzy c-mean (FCM) clustering for each patch divided by dividing the ROI extracted from the boundary area of the foreground object into a patch having an n ㅧ n size, the unknown area detection module Expressed as lightness, green-red component, and blue-yellow component, but discarding the brightness and maintaining only the green-red component and blue-yellow component to identify the mixed pixel.

As described above, according to a method and apparatus for automatically generating a trimap for alpha matte through detection of an unknown area of the present invention, when generating a trimap for image matting, it is optimal by combining image extrusion, graph cut segmentation, and FCM clustering By automatically generating a trimap of, it is possible to improve the quality by reducing the number of artifacts occurring in the boundary area of the alpha matte and shortening the computation time of the alpha matte.

In particular, by performing an image matting operation using the automatically generated optimal trimap, there is an effect that a film production related technician can easily perform a visual effect operation.

In addition, the present invention makes the optimal trimap fully automatic without relying on the depth information required to divide the foreground object by allowing the unknown area to include only the pixels of the foreground and background colors, not the foreground or background pixels. There is an effect that can be created.

1 is a conceptual diagram for explaining a process of automatically generating a trimap of alpha matte through detection of an unknown area according to an embodiment of the present invention.
FIG. 2 is a diagram showing in detail the configuration of an automatic generation device for trimap of alpha matte through detection of an unknown area according to an embodiment of the present invention.
3 is a diagram illustrating a pixel-level protrusion map applied to an apparatus for automatically generating a trimap according to an embodiment of the present invention.
4 is a view showing an example of a processing in the foreground queue estimation module according to an embodiment of the present invention.
5 is a diagram illustrating an effect of combining image extrusion in the foreground cue estimation module and graph cut segmentation in the foreground segmentation module according to an embodiment of the present invention.
FIG. 6 is a diagram illustrating mixed pixel identification in an unknown area detection module according to an embodiment of the present invention.
7 is a view showing a boundary area of a foreground object implemented in an unknown area detection module according to an embodiment of the present invention.
8 is a flowchart illustrating in detail an operation process of a method for automatically generating a trimap of alpha matte through detection of an unknown area according to an embodiment of the present invention.
9 is a flowchart illustrating in detail the operation process of estimating the foreground queue according to an embodiment of the present invention.
10 is a flowchart illustrating in detail the operation process of the step of performing foreground segmentation according to an embodiment of the present invention.
11 is a flowchart illustrating in detail the operation process of the step of detecting an unknown area according to an embodiment of the present invention.
12 is a diagram comparing a trimap automatically generated by the method of the present invention and a conventionally generated trimap in an alpha matting evaluation data set.
13 is a diagram comparing a trimap automatically generated by the method of the present invention and a conventionally generated trimap in an extruded object data set.
FIG. 14 is a diagram for explaining a qualitative comparison of an alpha matte generated through a trimap generated according to the method of the present invention and a trimap generated in an existing method.
15 and 16 are diagrams for comparing SAD (sum of absolute differences) values of alpha matte calculated with various trimaps in KNN mating and information flow mating.
17 is a diagram for comparing average SAD values of alpha matte calculated with various trimaps in KNN mating and information flow mating.
18 is a diagram for qualitatively verifying the effect of detecting an unknown area applied to the method of the present invention.
19 is a diagram for explaining time consumption for generating an optimal trimap in an alpha matting data set.
20 and 21 are diagrams for describing time consumption in the alpha matting data set and salient object data set for unknown area detection applied to the method of the present invention and patch-based trimming and edge-based trimming of the conventional method, respectively. It is a drawing.
22 and 23 are diagrams for describing time consumption for alpha matte calculation in an alpha matting data set using KNN matting and information flow matting, respectively.
24 is a diagram for explaining time consumption for alpha matte calculation in a protruding object data set using KNN mating and information flow mating.
25 is a view for explaining the effect of the number of super pixels on the foreground segmentation.
26 is a view for explaining the effect of the number of clusters (c), fuzzifier (m) and w _threshold on the unknown area of the trimap generated according to the method of the present invention.

Hereinafter, with reference to the accompanying drawings will be described in detail a preferred embodiment of the method and apparatus for automatically generating an alpha matte trimap through detection of an unknown area of the present invention. The same reference numerals in each drawing denote the same members. In addition, specific structural or functional descriptions of the embodiments of the present invention are exemplified for the purpose of describing the embodiments according to the present invention, and unless defined otherwise, all terms used herein, including technical or scientific terms. These have the same meaning as those generally understood by those of ordinary skill in the art. Terms such as those defined in a commonly used dictionary should be interpreted as having meanings consistent with meanings in the context of related technologies, and should not be interpreted as ideal or excessively formal meanings unless explicitly defined herein. It is desirable not to.

First, image matting referred to throughout the specification of the present invention is to accurately extract the foreground and background of the input image using a trimap as an input.

In addition, the trimap is composed of three areas of white, black, and gray, and is divided into a foreground area, a background area, and an unknown area, respectively. ), And the unknown area means the outline (that is, the boundary).

In addition, the alpha matte (alpha matte) is a result calculated by performing the image matting, and has an alpha value other than the RGB values of the three primary colors.

1 is a conceptual diagram for explaining a process of automatically generating a trimap of alpha matte through detection of an unknown area according to an embodiment of the present invention.

As shown in FIG. 1, the image editing system 1 of the present invention includes a trimap automatic generation device 100 and an image mating device 200.

The trimap automatic generation device 100 is an expert capable of automatically generating a trimap without direct user intervention when performing image matting in which the foreground and background are accurately extracted from the input image by the image matting device 200. It is a system and can be applied to professional and intelligent systems related to image search, automatic foreground / main object segmentation of images or videos.

In addition, the trimap automatic generation device 100 simply and effectively combines image extrusion, graph cut segmentation, and fuzzy c-means (FCM) clustering when generating an optimal trimap for image matting. The optimal trimap can be generated automatically.

At this time, the lazy snapping is an interactive graph cut-based segmentation technique requiring user input in the foreground and background scribble format, and in the present invention, instead of using the foreground scribble provided by the user, a salientity map is used. By using it as the input of lazy snapping as the foreground scribble, the foreground object is segmented. Also, in the present invention, the edge is used as a background scribble based on the assumption that most of the foreground objects are located in the center of the image.

In addition, the trimap auto-generation device 100 is configured to automatically divide the foreground object by including only pixels representing color mixing, not foreground or background pixels, in order to automatically generate an optimal trimap. Don't depend on the depth information you need. Also, for detection of an unknown region, a method of clustering a boundary region locally using fuzzy c-means (FCM) clustering is used.

Through this, according to the present invention, the alpha matte is included in the alpha matte by generating an alpha matte in the image matting device 200 through an optimal trimap automatically generated by the trimap automatic generation device 100. As well as reducing the number of artifacts, it is possible to improve the quality of the alpha matte by reducing the computation time of the alpha matte.

When the process of automatically generating a trimap of alpha mattes through detection of an unknown region in the trimap automatic generation device 100 is described, first, the trimap automatic generation device 100 is input to obtain a foreground cue. Use the projecting map of the image (①).

In addition, the trimap automatic generation device 100 segments the foreground object using the estimated foreground and background cues as input for graph cut segmentation (②).

In addition, after the segmentation of the foreground object, the trimap automatic generation device 100 performs a process of accurately finding an unknown area using fuzzy c-means (FCM) clustering to generate an optimal trimap (③).

Thereafter, an alpha matte is generated through an optimal trimap generated by the trimap automatic generation device 100 through the image matting device 200 (④).

Using the method of the present invention, a trimap is generated more quickly, and depth information for foreground segmentation is not required. In addition, the method of the present invention can operate directly on the RGB color image, and the optimal trimap can improve the alpha matte result by reducing the number of artifacts along the boundary area of the alpha matte.

FIG. 2 is a diagram showing in detail the configuration of an automatic generation device for trimap of alpha matte through detection of an unknown area according to an embodiment of the present invention.

As shown in FIG. 2, the trimap automatic generation device 100 includes a foreground queue estimation module 110, a foreground segmentation module 120, and an unknown area detection module 130.

The foreground queue estimation module 110 performs a function of estimating a foreground queue for a position of a foreground object in an input image using a pixel-level protrusion map.

At this time, the foreground queue estimation module 110 includes an image input unit 111, a projection map generation unit 112, a projection map quantization unit 113, a projection map binarization unit 114, a foreground queue output unit 115, and the like. It is configured by.

The image input unit 111 receives an input image for performing image matting and outputs it to the protrusion map generation unit 112.

The protrusion map generation unit 112 divides the input image provided from the image input unit 111 into a predetermined region, and the region contrast, region background, and region attribute for each divided region ( region property), and outputs the generated protrusion map to the protrusion map quantizer 113.

The protrusion map quantization unit 113 quantizes the protrusion map generated by the protrusion map generation unit 112 to generate a quantized protrusion map, and the generated quantized protrusion map to the protrusion map binarization unit 114 Output. In this case, the quantization refers to dividing the protrusion map into finite sections, and designating the divided sections using preset data.

The projected map binarization unit 114 binarizes the quantized projected map generated by the projected map quantization unit 113 to generate a binarized projected map, and the generated binarized projected map is the foreground queue output unit 115 ).

The foreground queue output unit 115 erodes the binarized projected map in the projected map binarization unit 114 to maintain only the largest blob (binary large object), and maintains the eroded binarized projected map. The foreground segmentation module 120 outputs it to be used as a foreground queue for performing graph cut segmentation.

At this time, the blob is used when dealing with multimedia data such as images and videos. Usually, the size of the data (Byte) and MIME (Multipurpose Internet Mail Extensions) type are found, or the data is divided into small blob objects for transmission and reception. Used for work.

The foreground segmentation module 120 defines a foreground queue for a position of a foreground object estimated by the foreground queue estimation module 110, a background queue generated by defining a corner region of the input image as a background seed, and a pre-calculated hyperminute Graph cut segmentation (lazy snapping) is performed based on an input image to be divided, a foreground object and a background are divided from the input image according to the performed graph cut segmentation, and the segmented foreground object is segmented to detect the unknown area ( 130).

At this time, the foreground segmentation module 120 includes a foreground queue providing unit 121, a background queue providing unit 122, an over-segmentation image providing unit 123, a graph cut segmentation unit 124, a foreground object segmentation unit 125, and the like. It is configured to include.

The foreground queue providing unit 121 receives the foreground queue for the position of the foreground object from the foreground queue estimation module 110, and inputs the foreground queue for the position of the foreground object to the graph cut segmentation unit 124 To provide.

The background queue providing unit 122 defines a corner region of the input image as a background seed to generate a background queue, and provides the generated background queue as an input of the graph cut segmentation unit 124.

At this time, when the background cue providing unit 122 creates the background cue by defining a corner region of the input image as a background seed, the foreground object is located in the center of the input image, and the corner of the input image is a background cue It is generated based on the assumption that it is highly likely to include.

The over-segmentation image providing unit 123 over-segments the input image into a plurality of super pixels (meaning a set of pixels having the same information), and the over-segmented input image of the graph cut segmentation unit 124 Provide it as input.

The graph cut segmentation unit 124 is a foreground queue received from the foreground queue providing unit 121, a background queue received from the background queue providing unit 122, and an excessive portion received from the over-segmentation image providing unit 123 Based on the input image to be performed, a function of dividing the foreground object and the background from the input image is performed.

The foreground object segmentation unit 125 segments the foreground object segmented by the graph cut segmentation unit 124 and outputs the segmented foreground object to the unknown area detection module 130.

The unknown area detection module 130 uses fuzzy c-means (FCM) clustering to check the mixed pixels including the color of the foreground and background in the boundary area of the foreground object segmented by the foreground segmentation module 120 to try. Performs the function of creating a map.

At this time, the unknown area detection module 130 includes an expansion unit 131, a region of interest (ROI) processing unit 132, an unknown area generation unit 133, an image merging unit 134, a trimap generation unit 135, etc. It is configured to include.

The expansion unit 131 expands only a portion of a boundary area of the foreground object segmented by the foreground segmentation module 120.

The ROI processing unit 132 sets the boundary area of the foreground object expanded through the expansion unit 131 as an ROI (interest region), and divides the set ROI into n ㅧ n patches, that is, a plurality of patches.

The unknown area generation unit 133 performs fuzzy c-average (FCM) clustering for each patch divided by n ㅧ n by the ROI processing unit 132, and the foreground and background colors for each patch based on the results Check the mixed pixels including the unknown area. That is, as a result of performing fuzzy c-mean (FCM) color clustering for each patch, a threshold value (w _threshold) used in classifying mixed pixels in all partial membership cluster scores w for each patch pixel 0.8), and as a result of the determination, if all the partial membership cluster scores w for pixels for each patch are less than a _threshold (w _threshold ), it is identified as an unknown area.

At this time, in the process of performing the fuzzy c-means (FCM) clustering for each patch divided by dividing the ROI extracted from the boundary region of the foreground object into a patch of n ㅧ n size, the unknown region generating unit 133 The patch can be configured to identify the mixed pixels by expressing the lightness, green-red component, and blue-yellow component, but discarding the brightness and keeping only the green-red component and blue-yellow component.

The image merging unit 134 merges and outputs the images for each patch processed by the unknown region generating unit 133 into a single image.

The trimap generating unit 135 generates a trimap based on the image merged by the image merging unit 134, and outputs the generated trimap to the image matting apparatus 200 to generate an alpha matte. .

Next, a trimap automatic generation process performed through the trimap automatic generation device 100 of the present invention configured as described above will be described in more detail with reference to FIGS. 3 to 7.

3 is a diagram illustrating a pixel-level protrusion map applied to an apparatus for automatically generating a trimap according to an embodiment of the present invention, and FIG. 4 is an example of processing in a foreground queue estimation module according to an embodiment of the present invention 5 is a view showing an effect of combining image extrusion in the foreground cue estimation module and graph cut segmentation in the foreground segmentation module, and FIG. 6 is an embodiment of the present invention. FIG. 7 is a diagram for describing mixed pixel identification in an unknown area detection module, and FIG. 7 is a view illustrating a boundary area of a foreground object implemented in an unknown area detection module according to an embodiment of the present invention.

First, in the present invention, it is assumed that there is a single salient object in the input image. If there are multiple projecting objects in the input image, the selection of the projecting object is relative to all users, so user preferences should be considered.

In order to automatically generate an optimal trimap, the trimap automatic generation device 100 should roughly locate the expected foreground object through the foreground queue estimation module 110.

The foreground cue estimation module 110 uses a pixel-level protrusion map to estimate the foreground cue. In short, the goal of image extrusion is to find the extrusion object in the input image, and the pixel-level extrusion map is the most prominent white and black pixel, respectively, as shown in FIG. 3 (b) in the input image of FIG. 3 (a). It is a gray image representing a pixel.

The present invention uses a DRFI (Differentiative Regional Feature Integration) based image extrusion approach. This approach formalizes object detection as a regression problem. The image is divided into M level (M = 3 in the present invention) segmentation set through multi-level segmentation, using graph-based image segmentation. Each divided region is represented by three functions: region contrast, region background, and region property. The area contrast feature provides a high overhang score for areas that differ from other areas. The difference area is likely to be a salient area. A pseudo-background region is extracted from the region background feature. The background score is then calculated for each region with reference to the pseudo-background region. The third feature, the area attribute feature, considers shape and geometric features. The shape feature describes the color distribution and texture of the area. The background generally has a uniform color distribution. Geometric features include the size and location of the area. The protruding objects are usually near the center, while the background is usually scattered over the entire image. Each feature extracted to compute the extrude map is mapped to the exaggeration score by an arbitrary forest regressor. Finally, all the extruded maps are combined to create a single extruded map.

When the protrusion map is generated as shown in FIG. 4 (b) from the input image shown in FIG. 4 (a), the foreground queue estimation module 110 calculates the protrusion _map called S _map , and the calculated The S _map is quantized to generate a quantized protrusion map S _qmap as shown in FIG. _4C . Then, the quantified protrusion map S _qmap is binarized to generate a binarized protrusion map S _bmap as shown in FIG. _4D . The binarized extruded map S _bmap often creates incomplete extruded objects. This is because the gray scale S _qmap is binarized by calculating a threshold based on the image histogram. In order to solve this problem, the present invention combines image extrusion and graph cut segmentation. Specifically, the binarized protrusion map is used as a lazy snapping input of the foreground segmentation module 120. Through this, lazy snapping can be performed completely automatically without scribble provided by the user in order to perform segmentation. In the present invention, the binarized extruded map S _bmap is eroded and only the largest blob is maintained, thereby minimizing the risk of obtaining a background object labeled as foreground in graph cut segmentation. The eroded S _bmap is used as a foreground cue F _cue (Fig. 4 (e)) for lazy snapping to recover the foreground area lost during the binarization process.

As described above, when the foreground cue F _cue is generated through the foreground cue estimation module 110, the trimap automatic generation device 100 views the foreground through the foreground cue F _cue and lazy snapping through the foreground segmentation module 120. Segmentation must be performed. The lazy snapping is a graph cut-based segmentation strategy, and graph cut image segmentation may be raised as a binary label problem. Formulate the image as graph G = (V, E). Where V is the set of all nodes (image pixels) and E is the set of edges (adjacent pixels) connecting adjacent nodes. The goal of the graph cut is to label each node iεV with 1 (foreground) or 0 (background). The label X = {x _i } can be obtained by minimizing the energy function E (X) as in Equation 1 below.

[Equation 1]

및

까지의 최소 거리는 각각 다음의 수학식 2와 같이 계산된다.Where E ₁ (x _i ) represents the likelihood energy and E ₂ (x _i , x _j ) is the prior energy. E ₁ represents the color similarity of the node and indicates whether it belongs to the foreground or the background. The initial foreground F and background B seeds are clustered using k-means clustering. Foreground and background clusters in color C (i) for each node i

And

The minimum distance to is calculated by Equation 2 below.

[Equation 2]

는 노드 i와

사이의 거리이며,

는 노드 i와

사이의 거리이다. E₁(x_i)은 다음의 수학식 3과 같이 정의된다.here

Node i and

Is the distance between

Node i and

Is the distance between. E ₁ (x _i ) is defined as in Equation 3 below.

[Equation 3]

Here, U denotes a known area for identifying the label. The first two equations in Equation 3 represent user scribables, and the third equation displays pixels of a color similar to the foreground or background. E ₂ (x _i , x _j ) is defined as a color gradient function between two nodes i and j, as in Equation 4.

[Equation 4]

및

는 노드 i와 j 사이의 RGB 색상 차이이다. E₂는 단순히 페널티 항이며, 두 노드의 색상이 비슷할수록 E₂ 값이 커진다. E₂ 값이 클수록 가장자리가 객체 경계에 있을 가능성이 적음을 나타낸다.here

And

Is the RGB color difference between nodes i and j. E ₂ is simply a penalty term, and the more similar the colors of the two nodes, the larger the value of E ₂ . The larger the E ₂ value, the less likely the edge is at the object boundary.

To speed up the segmentation process and eliminate the need to work on all pixels, the lazy snapping improves efficiency by calculating graph cuts from precomputed oversegmented input images. The conventional lazy snapping algorithm uses watershed segmentation, but in the present invention, a simple linear iterative clustering (SLIC) method is used to over-segment an image into n _sp superpixels. In the present invention, the graph is as shown in Equation 5 below.

[Equation 5]

및

는 각각

및

로 변경된다.

는 색 C(i_sp)와

사이의 거리인 반면, B_sp는 색 C(i_sp)와

사이의 거리를 나타낸다(수학식 7 참조). C(i_sp),

및

는 수학적으로 다음의 수학식 6과 같이 정의된다.Where V _sp is the set of n _sp super pixels, and E _sp is the set of edges connecting these super pixels. Also, E ₁ is similar except that C (i) now corresponds to C (i _sp ), which represents the average color of the super pixel i _sp .

And

Each

And

Is changed to

With color C (i _sp )

B _sp is the color C (i _sp )

It represents the distance between them (see Equation 7). C (i _sp ),

And

Is mathematically defined as in Equation 6 below.

[Equation 6]

[Equation 7]

는 i_sp의 각 n번째 픽셀의 색상이다. E₂의 경우, C_ij라는 용어는 수학식 8에 나타낸 바와 같이 두 개의 슈퍼 픽셀 i_sp와 j_sp 사이의 평균 색차

를 나타낸다.Where i _sp is the super pixel, n is the number of pixels in i _sp ,

Is the color of each nth pixel of i _sp . For E ₂ , the term C _ij is the average color difference between the two superpixels i _sp and j _sp , as shown in Equation 8.

Indicates.

[Equation 8]

As the foreground seed F required to calculate E (X), the F _cue obtained through the foreground queue estimation module 110 is used. However, the lazy snapping requires the user to provide foreground and background seeds to perform graph cut segmentation. Therefore, to calculate the lazy snapping, it is necessary to automatically provide a background scribble. In this step, the upper, left and right corner regions C of the input image are defined as the background seed B. This assumption is based on the observation that most foreground objects are centered in the image, and the corners are likely to contain background cues. In some cases, the background queue and the foreground queue may overlap each other, which may confuse the lazy snapping algorithm. To solve this, the following equation (9) is applied while the background queue B _F is generated.

[Equation 9]

x, y∈C represent pixel coordinates. In short, if each pixel of S _bmap has a value of 1, the criterion will assign a value of 0 to a pixel of B _F. In case of overlap, the foreground cue pixel is given priority over the background cue pixel. These automatically generated foreground cues and background cues are used as inputs for lazy snapping to minimize the energy function E (X), resulting in foreground segmentation. Since we assume one object of interest, we take the largest blob in the foreground segmentation and call it S _F. FIG. 5 shows the effect of combining the image extrusion and the graph cut segment. FIG. 5 (a) is the input image, (b) the extrusion map S _map , (c) the foreground cue F _cue , and (d) the foreground segmentation. S _F is shown respectively.

As described above, after the foreground object and the background are segmented through graph snap segmentation in the foreground segmentation module 120, and the segmented foreground object is segmented, the trimap automatic generation device 100 may not know the The gray area (ie, the unknown area) must be accurately detected in the trimap through the area detection module 130.

The optimal trimap is a trimap in which gray areas cover only pixels with color mixing. These pixels are referred to as mixed pixels, which include the colors of the foreground and background. The optimal trimap allows you to create a high quality alpha matte. However, drawing the optimal trimap manually is cumbersome and unrealistic. Conversely, most trimap auto-generation methods use simple morphological operations (eg, dilation) to create an unknown region. However, unknown areas created by morphologically-based work are not optimal because they also include foreground and background pixels, which can cause artifacts in the output alpha matte.

In the present invention, in order to generate an optimal trimap in the unknown area detection module 130, it is necessary to identify pixels with color mixing (ie, mixed pixels). Fuzzy c-means (FCM) clustering is used along with color as a feature to find such mixed pixels. The fuzzy c-mean (FCM) clustering is a soft clustering technique in which the membership score of each cluster is assigned to each data point (ie pixel). This membership score indicates the degree to which pixels belong to each cluster. The basic idea of the present invention is to find the mixed pixels by analyzing the membership score assigned by the fuzzy c-means (FCM) clustering algorithm. Intuitively, mixed pixels are assigned similar membership scores in each cluster, but pixels without color mixing are assigned a higher membership score in one of the clusters. FIG. 6 is a view showing an intuition for the unknown area, FIG. 6 (a) is an ROI _FCM (the boundary area of S _F ), (b) is an enlarged view of the purple box of (a), and (c) is (b) ), (D), (e), and (f) of the blue box in (c) indicate enlarged views of the green, red, and yellow boxes in (c), respectively. It should be noted that the color mixing in FIG. 7 (e) includes the color of the background as well as the foreground. 7 (d) and 7 (f) show pixels from the foreground and background, respectively. Based on this intuition, it is possible to classify the mixed pixels and create an exact unknown area for the trimap.

를 c개의 퍼지 클러스터로 분할한다. 다음의 수학식 10과 같은 글로벌 휴리스틱 비용 함수(global heuristic cost function)를 최소화하려고 시도한다.The fuzzy c-means (FCM) clustering algorithm is based on a similarity metric n data points

Is divided into c fuzzy clusters. Attempts to minimize the global heuristic cost function as shown in Equation 10 below.

[Equation 10]

는 데이터 포인트 x_i가 클러스터 c_j에 속하는 정도를 나타내는 멤버십 스코어이고, m은 클러스터 퍼지의 양을 결정하는 퍼지화기(fuzzifier)이고, n은 데이터 포인트의 수이며, c는 클러스터의 수이다. m은 fuzzier 클러스터에 해당하고 m = 0은 J_FCM을 제곱합 오차 기준과 동일하게 만든다. 수학적으로

는 다음의 수학식 11과 같이 정의된다.here,

Is a membership score indicating the degree to which the data point x _i belongs to the cluster c _j , m is a fuzzifier that determines the amount of cluster fuzzy, n is the number of data points, and c is the number of clusters. m corresponds to the fuzzier cluster and m = 0 makes J _FCM equal to the sum of squared error criteria. Mathematically

Is defined as Equation 11 below.

[Equation 11]

FCM is implemented locally only in the boundary area of the foreground object. In the present invention, this boundary region is called ROI _FCM . The ROI _FCM (equivalent to X) is mathematically defined as in Equation 12 below.

[Equation 12]

은 팽창 연산,

는 침식 연산이다. ROI_FCM의 예가 도 7에 나타나 있다. ROI_FCM을 nㅧn 크기의 여러 패치 p로 나눈다. 각각의 패치 p는 CIELAB 색 공간으로 변환되어 명도(L), 녹색-적색 성분(A) 및 청-황색 성분(B)으로 색을 표현한다. 특징으로 색상만 필요하기 때문에 L 채널을 버리고, A 및 B 색상 채널만 유지한다. 계산 시간을 단축하기 위해 0이 아닌 픽셀을 포함하는 패치에만 FCM을 적용한다. 패치 p_x의 각 i번째 픽셀은 다음의 수학식 13과 14의 기준에 따라 혼합 픽셀로 분류된다.Where S _F is the final foreground segmentation, I is the input color image, SE ₁ and SE ₂ are structuring elements,

Silver expansion operation,

Is an erosion operation. An example of ROI _FCM is shown in FIG. 7. Divide the ROI _FCM into several patch p of size n ㅧ n. Each patch p is converted into a CIELAB color space to express colors with lightness (L), green-red component (A), and blue-yellow component (B). Since only the color is required as a feature, the L channel is discarded, and only the A and B color channels are maintained. To shorten the computation time, FCM is applied only to patches containing non-zero pixels. Each i-th pixel of the patch p _x is classified as a mixed pixel according to the following equations (13) and (14).

[Equation 13]

[Equation 14]

는 w_i의 최대값, w_threshold 값은 혼합 픽셀을 분류하는 데 사용되는 임계 값 멤버십 스코어이다. 마지막으로 모든 패치 p에 상기 퍼지 c-평균(FCM) 클러스터링을 적용한 후 패치가 단일 이미지로 병합되어 최종 최적의 트라이맵이 된다. 상기 퍼지 c-평균(FCM) 클러스터링은 이러한 파라미터에 민감하며 이러한 파라미터의 효과는 다음의 실험 결과에서 보다 구체적으로 설명하기로 한다.Where p _x (i) is the i-th pixel of the patch p _x , p _SF (i) is the pixel intensity of the i-th pixel of the patch p _SF having the same position as p _x in S _F , and w _i is the i-th of p _x A set of all partial membership cluster scores for pixels,

Is the maximum value of w _i , and the w _threshold value is the threshold membership score used to classify the mixed pixels. Finally, after applying the fuzzy c-means (FCM) clustering to all the patches p, the patches are merged into a single image to become the final optimal trimap. The fuzzy c-means (FCM) clustering is sensitive to these parameters and the effect of these parameters will be described in more detail in the following experimental results.

Next, an embodiment of a method for automatically generating a trimap of alpha matte through detection of an unknown region according to the present invention configured as described above will be described in detail with reference to FIGS. 8 to 11. At this time, each step according to the method of the present invention can be changed in order by the environment or those skilled in the art.

8 is a flowchart illustrating in detail an operation process of a method for automatically generating a trimap of alpha mattes through detection of an unknown area according to an embodiment of the present invention, and FIGS. 9 to 11 are steps of estimating the foreground queue of FIG. 8. , It is a flow chart showing in detail the operation process of the step of performing foreground segmentation and the step of sensing the unknown area.

As shown in FIG. 8, in order to automatically generate an optimal trimap, the trimap automatic generation apparatus 100 estimates a foreground cue for a position of a foreground object in an input image using a pixel-level protrusion map Performs the foreground queue estimation step (S100).

When the foreground cue estimation step of the step S100 is described in detail with reference to FIG. 9, the foreground cue estimation module 110 of the trimap automatic generation device 100 inputs an image provided with an input image for performing image matting Step S110 is performed.

In addition, the foreground queue estimation module 110 divides the input image provided through the step S110 into a predetermined region, and the region contrast, region background, and region attribute for each divided region. A step of generating a protrusion map for generating a protrusion map (S _map ) based on the property is performed (S120).

After generating the protrusion map through the step S120, the foreground queue estimation module 110 performs a protrusion map quantization step to quantize the generated protrusion map to generate a quantized protrusion map (S _qmap ) (S130). In this example, the projected map binarization step of generating the binarized projected map (S _bmap ) by binarizing the generated quantized projected map is performed (S140).

In addition, the foreground queue estimation module 110 erodes the binarized protrusion map to maintain only the largest blob, and the eroded binarized protrusion map is graph cut segmented in the foreground segmentation step (S200). A foreground cue output step of outputting it to be used as a foreground cue (F _cue ) for performing S is performed (S150).

After estimating the foreground cue through the step S100, the trimap automatic generation device 100 defines a foreground cue for the estimated position of the foreground object and a background cue created by defining a corner region of the input image as a background seed. And performing a foreground segmentation step of segmenting the foreground object and the background from the input image by performing graph cut segmentation (lazy snapping) based on the pre-calculated over-segmented input image (S200). .

In detail, the foreground cue estimation step of step S200 will be described with reference to FIG. 10. The foreground segmentation module 120 of the trimap automatic generation device 100 may include a foreground queue for the position of the foreground object estimated in step S100. Takes the input and performs the foreground cue provision step provided as input for graph cut segmentation.

At the same time, the foreground segmentation module 120 generates a background cue by defining a corner region of the input image as a background seed, and then provides a background cue providing the created background cue as an input for graph cut segmentation. After the input image is over-segmented into a plurality of super pixels, an over-segment image providing step of providing the over-segmented input image as an input for graph cut segmentation is performed (S210).

At this time, when the foreground segmentation module 120 generates the background cue by defining a corner region of the input image as a background seed in step S210, the foreground object is located in the center of the input image, and the corner of the input image is generated. Is created based on the assumption that it is likely to include a background queue.

In addition, the foreground segmentation module 120 performs a graph cut segmentation step of dividing the foreground object and the background from the input image by referring to the foreground queue, the background queue, and the hyper-segmented input image received through step S210 (S220). ).

In addition, the foreground segmentation module 120 segments the foreground object divided through the step S220, and outputs the segmentation data S _F of the foreground object to the unknown area detection module 130 (S230).

After performing the foreground segmentation through the step S200, the trimap automatic generation device 100 uses the fuzzy c-means (FCM) clustering, and the foreground from the boundary area of the foreground object segmented through the step S200. An unknown area detection step of generating a trimap is performed by checking the mixed pixels including the color of the background (S300).

When the unknowing area detection step of step S300 is described in detail with reference to FIG. 11, the unknown area detection module 130 of the trimap automatic generation device 100 displays the boundary area of the segmented foreground object S _F. After performing the expanding expansion step (S310), after setting the boundary area of the expanded foreground object as an ROI (interest region), performing an ROI processing step of dividing the set ROI into n ㅧ n patches (S320). ).

In addition, the unknown area detection module 130 performs fuzzy c-average (FCM) clustering for each patch divided by n ㅧ n patches through the step S320, and the foreground and background of each patch is based on the result of the performed. An unknown area generation step of generating an unknown area by checking a mixed pixel including a color is performed (S330). For example, the unknown area detection module 130 performs fuzzy c-mean (FCM) color clustering for each patch, and all partial membership cluster scores (w) for each patch pixel are used to classify the mixed pixels. It is determined whether it is less than a threshold value (w _threshold , which is set to 0.8 in the present invention), and as a result of the determination, if all the partial membership cluster scores w for each pixel of each patch are less than the threshold value w _threshold , the area is unknown. To identify.

On the other hand, in the process of performing the fuzzy c-mean (FCM) clustering for each patch divided by dividing the ROI extracted from the boundary area of the foreground object into a patch of n ㅧ n size, and the unknown area detection module 130 The patch of is expressed as lightness, green-red component, and blue-yellow component, but discards the brightness and checks the mixed pixels by maintaining only the green-red component and blue-yellow component.

In addition, the unknown area detection module 130 performs an image merging step of merging the images of each patch processed in step S330 into a single image (S340), and generates a trimap based on the merged image. The generating step is performed (S350).

Next, the experimental results of the automatic generation device of the tri-map of the alpha matte through the detection of the unknown area according to an embodiment of the present invention configured as described above will be described in detail with reference to FIGS. 12 to 26.

For the performance evaluation of the trimap automatic generation device 100 of the present invention, the algorithm for the alpha matte evaluation and the extrusion object data set was tested. The alpha matte data set consists of 27 images. In the case of the extruded object data set, most of the images in this data set are composed of several objects, but the present invention selects an image containing only a single extruded object because it is assumed that the image contains a single extruded object. A total of 174 images were selected from the extruded object data set. The method is quantitatively evaluated using the Sum of Absolute Difference (SAD) error scheme. The mathematical equation of SAD is as shown in Equation 15 below.

[Equation 15]

은 계산된 이미지, x 및 y는 픽셀 좌표, W는 이미지의 너비, H는 이미지의 높이를 나타낸다.Where I is the GT (Ground Truth) image,

Is the calculated image, x and y are pixel coordinates, W is the width of the image, and H is the height of the image.

12 and 13 are views comparing a trimap automatically generated by the method of the present invention and a conventionally generated trimap in the alpha matting evaluation data set and the extruded object data set, respectively. The input image, (b) is the optimal trimap generated in the present invention, (c) is the expanded trimap of the present invention, and (d) is the manually generated trimap. As shown in FIGS. 12 and 13, it can be confirmed that the trimap generated by the present invention is almost as accurate as the manually generated trimap.

Meanwhile, the effect of detecting the unknown area in reducing the artifacts of the alpha matte based on the result of calculating the alpha matte using four different trimaps is as follows.

The first trimap is an extension-based trimap (f in FIG. 14), and an unknown region is generated by an expansion operation. This extension-based trimap is identical to that created by the extension-based previous method that uses extensions to create an unknown region. It was not possible to implement it directly because the source code was not available and there was no personal data set used in this method, but for comparison it is assumed that the foreground segmented in this way is identical to the present invention. To create an unknown area, the boundary of the foreground segmentation is expanded as mentioned in this method. This assumption is fair because this experiment focuses on demonstrating the importance and effectiveness of detecting unknown areas rather than the importance of foreground segmentation. In the present invention, edge-based trimming is applied to an extension-based trimap to generate a second trimap (e of FIG. 14), and a third trimap (d of FIG. 14) is generated by applying patch-based trimming. The fourth trimap is an optimal trimap (c in FIG. 14) using an unknown area detection method applied to the present invention.

To calculate the alpha matte, KNN mating was used in FIG. 14 (a), and information-flow mating was used in FIG. 14 (b). Basically, information flow mating uses trimap trimming in the algorithm. However, this default option is disabled to demonstrate that unknowing area detection is more effective in reducing artifacts than patch-based trimming. The alpha matte calculated with these four trimaps was compared quantitatively and qualitatively.

14 is a view for explaining a qualitative comparison of the alpha matte generated through the trimap generated according to the method of the present invention and the trimap generated in the conventional method, a is an input image, b is a ground truth (GT) Alpha matte, c is an optimal trimap generated by the method of the present invention, d is a trimap for patch-based trimming, e is a trimap for edge-based trimming, and f is an extension-based trimap.

FIG. 14 shows that the alpha matte calculated with the optimal trimap of the present invention contains fewer artifacts and has better performance than the alpha matte generated with other trimaps. The evaluation of the present invention clearly shows that the use of an optimal trimap for alpha matte calculations can significantly improve artifacts by significantly reducing artifacts than results obtained by conventional methods. The red and green windows in FIG. 14 visualize artifacts in alpha matte. FIG. 14 shows that the alpha matte by the previous method assigns an alpha value greater than 0 to a background pixel. Ideally, the background pixel should be assigned an alpha value of 0 in the alpha matte. Alpha matte improves alpha matte by significantly reducing this false alpha value assignment.

15 and 16 are diagrams for comparing SAD (sum of absolute differences) values of alpha matte calculated by various trimaps in KNN mating and information flow mating. For quantitative comparison, GT alpha mat And SAD error between alpha matte calculated with 4 different trimaps. The alpha matte calculated using the optimal trimap achieves the lowest average SAD value of 10,784 for KNN mating (FIG. 15), and an average SAD of 10,730 for information flow mating (FIG. 16) in the alpha matting evaluation data set. To achieve the value. This lowest average SAD value means that the alpha matte generated using the optimal trimap is closest to the GT alpha matte compared to other alpha mattes. The average SAD value of the alpha matte calculated using other trimaps is all greater than 11,410. The expansion-based trimap had the highest SAD score of 13,082 in information flow mating. 17 is a view for comparing the average SAD value of the alpha matte calculated with various trimaps in KNN mating and information flow mating, where the SAD score of the present invention is the best for the extruded object data set in both KNN mating and information flow mating. Verify that it is low.

To further verify the effect of detecting the unknown area, the four trimaps are compared qualitatively with reference to FIG. 18. 18 is a diagram for qualitatively verifying the effect of detecting an unknown area applied to the method of the present invention, (a) is an input image, (b) is an optimal trimap generated by the method of the present invention, (c ) Is a trimap of patch-based trimming, (d) is a trimap of edge-based trimming, and (e) is a trimap of extension-based methods. Referring to FIG. 18, it can be seen that the trimap having the unknown area detection is superior in the trimap trimming. It should be noted that the red and green windows of FIG. 18 above show that other unknown area detection methods are actually background pixels, but more pixels are allocated as unknown. The method applied in the present invention is better for assigning the correct label as seen in FIG. 18 above. It should be noted that edge-based trimming causes the unknown area to shrink too much, making the alpha matte worse as shown in FIG. 14 above. In general, if there are too many unknown pixels, artifacts are created in the alpha matte, and if there are few unknown pixels, finer details are lost in the alpha matte to further refine. The method of the present invention creates an optimal trimap that can reduce artifacts while maintaining fine detail in alpha matte.

Meanwhile, the results of evaluating the time spent for generating the trimap, the time spent for detecting the unknown area, and the time taken for calculating the alpha matte using various trimaps are as follows.

First, when an evaluation result of time consumption for generating a trimap is described with reference to FIG. 19, FIG. 19 is a diagram for explaining time consumption for generating an optimal trimap in an alpha matting data set, which is scaled. Time consumption of the original image (70% of the original size) and the original size image was measured. This was done to see the effect of image size on the trimap calculation time. As can be seen from FIG. 19, when the image size is 427 ㅧ 548 (average image size of resized data), it takes 13.96 seconds (average time), and the image size is 609 ㅧ 783 (average image size of original size data). In the case of 35.7 seconds. For the extruded object data set, it takes an average of about 5.49 seconds when the image size is 374 크기 328 (average image size of the extruded object data set). This time is considerably less compared to drawing a trimap manually. It should be remembered that manually drawing a trimap of the exact unknown area can take several minutes even for experienced users. Most of the time of the algorithm proposed in the present invention is used for calculating a salientity map using DRFI. Faster extrusion map calculations lead to much faster trimap generation.

Second, to explain the time consumption for the detection of the unknown area, FIGS. 20 and 21 are alpha matting data sets and extrusion object data for patch-based trimming and edge-based trimming, which are applied to the method of the present invention. It is a figure for explaining each time consumption in a set.

As shown in FIG. 20, in the case of the alpha matte data set, the unknown area detection algorithm proposed in the present invention takes about 4.98 seconds for the average process of the unknown area, the existing patch-based trimming takes an average of 14.44 seconds, and edge-based trimming The average calculation time is the fastest with 4.42 seconds. However, fast calculation results in a decrease in alpha matte quality. It can be seen from FIG. 14 that the alpha matte calculated by edge-based trimming includes many artifacts. Also, higher SAD error values are obtained as shown in FIGS. 15 to 17 above. The present invention is as fast as edge-based trimming and is much better at reducing the artifacts seen in FIGS. 14 and 19. In addition, the present invention is significantly faster than patch-based trimming and produces a much better alpha matte.

In the case of the extruded object data set (FIG. 21), the unknown area detection algorithm proposed in the present invention uses an average of about 2.06 seconds, while patch-based trimming takes an average of 5.50 seconds. Edge-based trimming has the fastest average calculation time of 1.17 seconds. As mentioned earlier, even though edge-based trimming is slightly faster, the alpha matte contains a lot of artifacts.

Third, explaining the time consumption for alpha matte calculation using various trimaps, FIGS. 22 and 23 illustrate time consumption for alpha matte calculation in the alpha matting data set using KNN matting and information flow matting, respectively. As a drawing to show, using the optimal trimap of the present invention shows that the alpha matte calculation time can be reduced in the alpha matting data set when two different image matting algorithms are used. The KNN mating algorithm uses an average of 6.07 seconds (FIG. 22), but information flow mating requires an average of 11.99 (FIG. 23) to calculate the alpha matte using an optimal trimap. The optimal trimap of the present invention is the fastest in KNN mating and the second fastest in information flow mating. Trimap by edge-based trimming is the fastest for information flow mating. This is due to the fact that the information flow matting calculates the unknown area processing which increases / decreases the calculation time according to the number of unknown pixels. Edge based trimming trims the unknown area, greatly reducing the number of unknown pixels. However, slightly faster speeds and extreme trimap trimming lower the alpha matte quality (see Figures 14 and 19). The alpha matte calculated with the expansion-based trimap takes the longest time since it contains more unknown pixels compared to the trimmed trimap. The more unknown pixels in the trimap, the longer it takes to calculate the alpha matte. The results for the extruded object data set are shown in FIG. 24.

On the other hand, in the present invention, before calculating the graph cut segmentation, the image was _{oversegmented} with n _sp number of super pixels. Super-pixel segmentation was calculated to reduce the computational time required to segment the foreground object. However, there is a trade-off between faster graph cut calculations and foreground segmentation accuracy. When the value of n _sp is low, the segmentation process speeds up, but abstraction / generalization of image color occurs. This over-abstraction contributes to inaccurate segmentation, especially in parts of the image with small holes.

25 is a diagram for explaining the effect of the number of super pixels on foreground segmentation, and it is necessary to note how a smaller n _sp value can segment portions from the background. Higher _sp values improve segmentation, but increase computation time. In the experimental evaluation of the present invention, n _sp = 3000 showed a good balance between the segmentation result and the calculation time.

In addition, the fuzzy c-means (FCM) algorithm applied to the present invention requires two parameters (c and m) to cluster data points. The unknown area created by this clustering is parameter sensitive. In addition, the w _threshold value parameter required for the classification of the unknown pixels affects the unknown region. 26 is a view for explaining the effect of the number of clusters (c), fuzzifier (m) and w _threshold on the unknown area of the trimap generated according to the method of the present invention, the unknown area of the optimal trimap of the present invention The effects of various parameters on were analyzed and can be summarized as follows.

First, with respect to the number of clusters c, the higher the value of c, the more unknown pixels are generated. This is because when the value of c increases, c partial membership scores are allocated to each data point. Because of this, individual membership values are too small, so more pixels are classified as unknown. When c is low, the number of unknown pixels is reduced.

Second, with respect to Fuzzifier (m), m determines the amount of purge between clusters. As m increases, purge increases, which corresponds to an unknown pixel. More fuzzier clusters are created due to increased fuzzy between clusters. This simply means that the data points have almost the same membership value for each cluster. Therefore, more pixels are classified as unknown. If m is reduced, hard clustering occurs.

Whereas in connection with the first three, w _threshold, which is classified as a high w _threshold values are more pixels Unknown, low w _threshold value means that the classification as a less-pixel Unknown.

Increasing the number of unknown pixels has the same effect as the extension-based trimap. This is because the greater the number of unknown pixels, the more likely that some of the pixels will cover the foreground or background pixels. Conversely, a small number of unknown pixels negatively affects the output alpha matte. When there are fewer unknown pixels, fine details (such as hair) are ignored on the border of the foreground object, creating an alpha matte similar to hard partitioning. Find the sweet spot (best situation) that reduces the impact of conditions and results on the optimal trimap. In the experimental results of the present invention, c = 3, m = 5 and w _threshold = 0.8 were set, and optimal results were calculated from these values.

As described above, since the present invention automatically generates an optimal trimap by combining image extrusion, graph cut segmentation, and FCM clustering when generating a trimap for image matting, the number of artifacts occurring in the boundary region of the alpha matte It is possible to improve the quality by reducing and shortening the calculation time of the alpha matte. In particular, an image matting operation can be performed using an optimal trimap that is automatically generated, so that a movie production technician can easily perform a visual effect operation.

In addition, the present invention makes the optimal trimap fully automatic without relying on the depth information required to divide the foreground object, by allowing the unknown area to include only the pixels of the foreground and background colors, not the foreground or background pixels. Can be created.

As described above, the present invention has been described with reference to the embodiment shown in the drawings, but this is only exemplary, and those skilled in the art to which the art pertains have various modifications and other equivalent embodiments You will understand that it is possible. Therefore, the technical protection scope of the present invention should be determined by the following claims.

1: Video editing system 100: Trimap automatic generation device
110: foreground queue estimation module 111: image input unit
112: protrusion map generation unit 113: protrusion map quantization unit
114: extrusion map binarization unit 115: foreground queue output unit
120: foreground segmentation module 121: foreground queue providing unit
122: Background cue providing unit 123: Oversegment image providing unit
124: graph cut segmentation unit 125: foreground object segmentation unit
130: unknown area detection module 131: expansion unit
132: ROI processing unit 133: unknown area generation unit
134: image merger 135: trimap generator
200: image matting device

Claims (12)

In the trimap automatic generation apparatus, a foreground cue estimation step of estimating a foreground cue for a position of a foreground object in an input image using a pixel-level protrusion map;
In the trimap automatic generation device, graph cut segmentation based on the foreground cue for the estimated position of the foreground object, the background cue generated by defining a corner region of the input image as a background seed, and a pre-computed oversegmented input image a foreground segmentation step of dividing a foreground object and a background from the input image by performing lazy snapping, and segmenting the divided foreground object; And
In the trimap automatic generation device, using fuzzy c-means (FCM) clustering, an unknown region detection step of generating a trimap by identifying mixed pixels including a foreground and a background color in a boundary region of the segmented foreground object ;
The foreground segmentation step,
Based on the assumption that when the background cue is created by defining a corner region of the input image as a background seed, the foreground object is located in the center of the input image, and a corner of the input image is likely to include a background cue. Automatic generation method of the trimap, characterized in that to generate. The method according to claim 1,
The foreground queue estimation step,
An image input step of receiving an input image for performing image matting in the trimap automatic generation device;
A protrusion map generation step of dividing the received input image into a predetermined area and generating a protrusion map based on the divided region contrast, region background, and region property;
A quantization of the projected map to generate a quantized projected map by quantizing the generated projected map;
A binarization map binarization step of binarizing the generated quantized projection map to generate a binarized projection map; And
Eroding the generated binarized extruded map, maintaining only the largest blob, and outputting the eroded binarized extruded map to be used as a foreground queue for performing graph cut segmentation in the foreground segmentation step Automated generation of a trimap, comprising: outputting a foreground queue. The method according to claim 1,
The foreground segmentation step,
In the apparatus for automatically generating a trimap, a foreground queue providing step of receiving a foreground queue for a position of a foreground object estimated in the foreground queue estimation step and providing it as an input for graph cut segmentation;
Defining a corner region of the input image as a background seed to generate a background queue, and providing a background queue to provide the generated background queue as an input for graph cut segmentation;
An over-segment image providing step of over-segmenting the input image into a plurality of super pixels and providing an input image over-segmented into the plurality of super pixels as an input for graph cut segmentation;
A graph cut segmentation step of dividing a foreground object and a background from the input image based on the foreground cue, a background cue, and an overdivided input image; And
And a segmentation of the foreground object for segmenting the segmented foreground object. The method according to claim 1,
The step of detecting the unknown area,
In the trimap automatic generation device, the expansion step of expanding the boundary area of the foreground object segmented in the foreground segmentation step;
An ROI processing step of setting a boundary region of the expanded foreground object as an ROI (interest region), and dividing the set ROI into patches of nxn;
A fuzzy c-average (FCM) clustering for each divided patch, and an unknown region generation step of generating an unknown region by identifying mixed pixels including a foreground and a background color for each patch based on the result of the execution;
An image merging step of merging the images for each patch processed in the step of generating the unknown area into one image; And
Trimap generation step of generating a trimap based on the merged image; Trimap automatic generation method comprising a. delete The method according to claim 4,
The step of detecting the unknown area,
In the trimap automatic generation apparatus, in the process of dividing the ROI extracted from the boundary region of the foreground object into nxn-sized patches and performing fuzzy c-mean (FCM) clustering for each divided patch,
Each patch is expressed as a lightness, green-red component, and blue-yellow component, but discarding the brightness and maintaining only the green-red component and blue-yellow component to check the mixed pixels, the trimap auto-generation method. A foreground cue estimation module for estimating a foreground cue for a position of a foreground object in an input image using a pixel-level protrusion map;
Graph cut segmentation (lazy snapping) is performed based on the foreground cue for the estimated position of the foreground object, the background cue generated by defining the corner region of the input image as a background seed, and the pre-calculated oversegmented input image. A foreground segmentation module for dividing the foreground object and the background from the input image and segmenting the divided foreground object; And
Includes a fuzzy c-means (FCM) clustering, an unknown area detection module that generates a trimap by identifying mixed pixels including a color of a foreground and a background in a boundary area of the segmented foreground object.
The foreground segmentation module,
Based on the assumption that when the background cue is created by defining a corner region of the input image as a background seed, the foreground object is located in the center of the input image, and a corner of the input image is likely to include a background cue. Trimap automatic generation device, characterized in that to generate. The method according to claim 7,
The foreground queue estimation module,
An image input unit provided with an input image for performing image matting;
A protrusion map generator for dividing the received input image into a predetermined area, and generating a protrusion map based on the divided region contrast, region background, and region property;
A protrusion map quantization unit to quantize the generated protrusion map to generate a quantized protrusion map;
A projected map binarization unit that binarizes the generated quantized projected map to generate a binarized projected map; And
Eroding the generated binarized extrusion map, maintaining only the largest blob, and outputting the eroded binarized extrusion map to be used as a foreground queue for performing graph cut segmentation in the foreground segmentation module Automatic output device for generating a trimap, comprising: a foreground cue output unit. The method according to claim 7,
The foreground segmentation module,
A foreground queue providing unit that receives a foreground queue for a position of a foreground object estimated by the foreground queue estimation module and provides it as an input for graph cut segmentation;
A background queue providing unit defining a corner area of the input image as a background seed to generate a background queue, and providing the generated background queue as an input for graph cut segmentation;
An over-segmentation image providing unit configured to over-segment the input image into a plurality of super pixels, and to provide an input image over-segmented into the plurality of super pixels as an input for graph cut segmentation;
A graph cut segmentation unit dividing a foreground object and a background from the input image based on the foreground cue, a background cue, and an oversegment input image; And
And a foreground object segmentation unit for segmenting the divided foreground object. The method according to claim 7,
The unknown area detection module,
An expansion unit that expands a boundary area of the foreground object segmented by the foreground segmentation module;
An ROI processing unit configured to set a boundary region of the expanded foreground object as an ROI (interest region), and divide the set ROI into patches of nxn;
A fuzzy c-average (FCM) clustering for each divided patch, and an unknown region generating unit for generating an unknown region by identifying mixed pixels including a foreground and a background color for each patch based on the result of the execution;
An image merging unit that merges the images of each patch processed by the unknown region generating unit into a single image; And
Trimap generating unit for generating a trimap based on the merged image; Trimap automatic generation device comprising a. delete The method according to claim 10,
The unknown area detection module,
In the process of dividing the ROI extracted from the boundary region of the foreground object into nxn-sized patches and performing fuzzy c-means (FCM) clustering for each divided patch,
Each patch is expressed as a lightness, green-red component, and blue-yellow component, but discards the brightness and keeps only the green-red component and blue-yellow component to check the mixed pixels, thereby generating a trimap automatic generation device.

Images