RU2522044C1 - Apparatus for selecting object contours on textured background when processing digital images - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: apparatus includes a Laplacian matrix generating unit (4); a diagonal matrix unit (5); delay units (14), (15); a control unit (13), decimation units (1), (2), (3); multiplier units (6), (8), (11); a multiplier (9); an adder unit (7); an inverse matrix unit (10); a delay unit (16); a linear interpolation unit (12); a clock-pulse generator (17).

EFFECT: enabling selection of an object with an irregular contour on an arbitrary textured background of a digital image.

1 dwg

Description

The invention relates to the field of computer technology and can be used in digital television and photo systems, global positioning and surveillance systems.

A simplified mathematical image model I _z (x, y) is defined for a pixel z as a combination of a foreground image F _z and a background image B _z , separated by an alpha channel α _z

$$I_z={\alpha }_z{F}_z+\left(\mathrm{one}-{\alpha }_z\right)B_z,\left(\mathrm{one}\right)$$

where α _z can take any value on the interval (0, 1). For an image, all three values of α _z , F _z and B _z are unknown for each pixel in the image.

The main problem to be solved is the selection of an object with a complex outline on an arbitrary textured background.

Due to the imperfection of the photosensitive matrix of a digital camera and shooting errors, digital image processing software systems that implement from the simplest methods of scaling and color correction to filtering and retouching have gained widespread development. Modern cameras have already implemented the simplest methods of digital image processing in automatic mode. The tasks of morphological image analysis, segmentation, reconstruction require a deeper image analysis. One of the tasks of the secondary processing system, when a composition in a digital photograph is formed and cannot be reproduced again, is segmentation, contour analysis - a classification of the sets of points of objects. The purpose of their solution is to study the structural properties of the objects represented in the image, and their interaction.

Simplified ways to highlight the contours of an object in an image can be divided into the following groups.

1) Methods based on the solution of partial differential equations.

2) Methods based on the construction of a probability distribution density for a set of points of an object and background.

3) Methods based on a linear combination of foreground and background colors.

An analysis of the existing processing methods shows that the area of their use in conditions of a limited amount of information about the components of the processed process is extremely limited. The use of methods for distinguishing the contours of an object in an image based on the solution of partial differential equations leads to blurring of sharp changes in brightness and contours and requires a priori information to select the parameters of the methods and minimize the functional. The inability to distinguish complex contours of an object in an image without additional a priori information limits the scope of use of these methods, which are mainly applicable for highlighting smoothed contours of an object in an image. To use methods based on the construction of the probability distribution density for many points of the object and background, a priori information is required for the probability density distribution of the background color and the foreground object (deep segmentation). It should also be noted that the color distribution of the object and the background should not overlap. The application of methods based on a linear combination of foreground and background colors requires large computational costs due to the solution of large systems of linear equations.

A known method and system for extracting data about an image of a foreground object based on data on color and depth [patent No. 2426172, IPC G06K 9/34]. The invention relates to the field of recognition and segmentation of images, and, in particular, to a method and system for extracting a target object from a background image and an image of an object by creating a mask used to highlight the target object. The technical result is the creation of an improved method for extracting data about the image of an object using data about the depth of the image. The specified technical result is achieved by creating a scalar image of the difference in the image of the object and the background based on the difference in illumination, and in areas where the difference in illumination is below a predetermined threshold value, based on the color difference; initialize the mask according to the results obtained from the previous video frame, where the scalar image of the difference is less than a predetermined threshold, if these results are available, while the mask of the object is filled with zeros and ones, where one means that the corresponding pixel belongs to the object, and zero otherwise; Clustering a scalar image of the difference and depth data based on several clusters; create a mask for each pixel position of the video frame using the centers of gravity of the clusters of scalar difference and depth data for the current pixel position; compensate for background changes in the scene over time by updating the background image based on the use of the created mask and the difference image.

The features of the method and the analog system that match the features of the proposed technical solution are as follows: the selection of the target object from the background image.

The disadvantages of the known method and system: the use of two cameras leads to large computational costs when receiving the alpha channel of the selected object.

There is a method of isolating an object in an image based on the solution of Poisson matting for images [Patent USA No. 7636128]. The method is based on solving a system of Poisson equations with boundary conditions for an image segmented into three areas: foreground, background, unknown region separating the foreground and background. To find the alpha channel, they solve the Poisson equation of the form:

$${\alpha }^{\ast }=\arg \underset{\alpha }{\min }{\displaystyle \iint {}_{z\in \Omega }{\Vert \nabla {\alpha }_z-\frac{\mathrm{one}}{F_z-B_z}\nabla I_z\Vert }^{2}dz\left(2\right)}$$

with the Dirichlet boundary condition

$$\alpha {|\; |\; |{}_{\partial \Omega }=\overline{\alpha }|\; |\; |}_{\partial \Omega },\left(3\right)$$

. $${\overline{\alpha }|\; |\; |}_{\partial \Omega }=\{\begin{array}{l}\mathrm{one,}p\in {\Omega }_F\\ 0p\in {\Omega }_B\end{array}\left(\mathrm{four}\right)$$

.

The found solution of the system of Poisson equations is the alpha channel of the image, to refine which local filters are used, which allow you to manually correct the final result by solving local Poisson equations.

The features of the analogue method, coinciding with the features of the proposed technical solution, are as follows: the selection of the object from the background image.

The disadvantages of this method are: the use of local filters, manually correcting the final result by solving local Poisson equations, which does not allow to obtain an effective automated processing system.

A known method of selecting an object in an image based on the Bayesian method [Chuang Y., Curless B., Salesin D., Szeliski R. A Bayesian Approach to Digital Matting, Proc. of IEEE CVPR, 2001, pp. 264-271]. To use the Bayesian method, you need to segment the input image into three areas: foreground, background, and unknown region. The alpha channel is estimated by building the probability density for a set of points of an object and background [Ruzon M.A. and Tomasi C. Alpha estimation in natural images. In CVPR 2000, pp. 18-25]. A continuously sliding window is used, in which at each step pixels are processed along the border of an unknown region.

Color samples are formed in the vicinity of the processed pixel and are clustered. Each cluster is an undirected Gaussian. For each pair of color Gaussians of the object and background, the optimal values of F, B, and α are calculated.

The points that maximize the conditional probability P (F, B, α | C) are selected as F and B. To evaluate this probability, the Bayes formula is used:

$$P\left(F,B,\alpha |\; |\; |C\right)=\frac{P(C|\; |\; |F,B,\alpha )P(F)P(B)P(\alpha )}{P(C)},\left(5\right)$$

where P (C | F, B, α) is estimated through the distance between the color C and the mixture F, B with coefficient α (1); P (F), P (B) are estimated through the probability density for the Gaussian colors of the object and background; P (α) is ignored; P (C) - the constant relative to the maximization parameters is also ignored.

The features of the analogue method, coinciding with the features of the proposed technical solution, are as follows: the selection of the object from the background image.

The disadvantages of this method: the construction of the probability distribution density for many points of the object and background requires deep segmentation of the original image; unknown area should contain only mixed pixels.

A device for isolating the contours of objects in the image [patent No. 2362210, IPC G06K 9/36, G06K 9/62, A61B 5/04]. The invention relates to the field of pattern recognition and can be used in vision systems for solving problems of image preprocessing. The technical result is to increase the speed of selecting contours of objects in the image. An object-contour extraction device containing an image sensor, a frame and line-pulse extraction unit, an analog-to-digital converter, a generator, a digital signal processor, random access memory, a selector, a filtering unit, a spatial differentiation unit, a buffer memory of the filtering unit, a buffer memory of the unit are introduced spatial differentiation, interconnected as described in the claims. The increase in performance is achieved due to the hardware implementation of the filtering operation and spatial differentiation in the corresponding blocks of the device.

The features of the analog device, coinciding with the features of the claimed technical solution, are as follows: highlighting the contours of the object in the image.

The disadvantages of the known device are: the use of two image sensors leads to high computational costs when receiving the alpha channel of the selected object.

Closest to the invention are a method and apparatus for determining the alpha channel in canonical form (Closed form method and system for matting a foreground object in an image having a background) [Patent USA No. 7692664]. The method for classifying multiple points of an object and background in an image by determining the alpha channel in canonical form is based on the assumption that the colors of pixels in small fragments of images F and B lie approximately on one straight line in the RGB space (they are a linear combination of two colors), alpha channel α _z is considered linearly dependent on color in the local area of the image:

,

where c is the color channel

,

Using the four-dimensional linear model (6), we obtain the objective function for the color image:

The values of a and b can be excluded from (7):

$$J\left(\alpha \right)={\alpha }^{T}L\alpha ,\left(8\right)$$

where L is a matrix of size N × N, (i, j) -element of which is equal to:

$${\displaystyle \sum _{K|\; |\; |i,j\in w_k}\left({\delta }_{ij}-\frac{\mathrm{one}}{|\; |\; |w_k|\; |\; |}(\mathrm{one}+(I_i-{\mu }_k){({\Sigma }_k+\frac{\epsilon }{|\; |\; |w_k|\; |\; |}{I}_3)}^{-\mathrm{one}}(I_i-{\mu }_k))\right),\left(9\right)}$$

where Σ _k is the 3 × 3 covariance matrix, µ _k is the 3 × 1 vector of medium colors in the window;

w _k and I ₃ are the identical 3 × 3 matrix.

Consider a prototype device involves:

1) determination of the weight for all edges of neighboring pixels in the image;

2) the construction of the Laplace matrix L with weights;

3) solution of the equation:

$$\alpha =\arg \min {\alpha }^{T}L\alpha ,\left(10\right)$$

α _i = s _i , ∀i∈S, S is the group of selected pixels, s _i is the value of the selected pixels;

4) the solution of equation (1) for F and B with additional assumptions about the smoothness of F and B;

5) composition of the selected foreground object with the selected background.

The features of the prototype method, which coincide with the features of the proposed technical solution, are as follows: processing a two-dimensional digital signal, selecting an object with a complex contour on an arbitrary textured background.

The disadvantages of the known method and device that implements it are:

1. the requirement of two input images to start processing: the original image and the original image marked into two areas;

2. The requirement of large computational costs for processing sparse matrices.

The block diagram of a device that implements the considered algorithm contains an image storage unit, a weight unit, a Laplace matrix unit, a calculation unit, a composition unit, a display unit.

The proposed device for selecting the contours of objects on a textured background when processing digital images allows you to select an object with a complex contour on an arbitrary textured background. The device implements the following algorithm. At the first step, the original image I, on which an object is presented against an arbitrary background, a two-dimensional array M containing the markers of the background and the object to be selected, a two-dimensional array V containing the markers of the selected object only, are decimated at 2. In the second step, for the image mI with a reduced resolution and a two-dimensional array mM with reduced dimension, a sparse Laplace matrix L of dimension N × N is constructed

$$N=h\cdot w,\left(\mathrm{eleven}\right)$$

, $$\frac{w}{2}$$

формируется вектор-столбец b размерностью 1, $$\frac{h}{2}\cdot \frac{w}{2}$$

, с поэлементным возведением в квадрат. Полученный вектор-столбец b и диагональная матрица D умножаются на константу λ. На пятом шаге формируется разреженная матрица K:where h is the image height, w is the image width, (i, j) is the element of which is determined by the formula (9). In the third step, for a two-dimensional array M with reduced dimension, a diagonal matrix D is constructed, the diagonal elements of which are equal to unity for marked pixels and equal to 0 for all others. In the fourth step, from a two-dimensional mV array with a reduced dimension $$\frac{h}{2}$$

, $$\frac{w}{2}$$

a column vector b of dimension 1 is formed, $$\frac{h}{2}\cdot \frac{w}{2}$$

, with bitwise squaring. The resulting column vector b and the diagonal matrix D are multiplied by the constant λ. At the fifth step, a sparse matrix K is formed:

. $$K=\left(L+\lambda D\right)\left(12\right)$$

.

For the obtained sparse matrix K find the inverse matrix K ^-1 . At the sixth step, an alpha channel is formed for the image with a reduced size:

. $${\alpha }^{\ast }=K^{-\mathrm{one}}\cdot \lambda b\left(13\right)$$

.

In the seventh step, using the original image I, the reduced image mI, the alpha channel α ^{* of the} reduced image mI is interpolated 2 times based on linear coefficients according to formula (6).

The device for selecting the contours of objects on a textured background when processing digital images (Fig. 1) contains a decimation unit 1, a delay unit 14, a control unit 13, the inputs of which are the information input of the device. The output of the decimation unit 1 is connected to the first input of the Laplacian 4 matrix forming unit and the input of the delay unit 15. The first output of the control unit 13 is connected to the input of the decimation unit 2, the output of which is connected to the second input of the Laplacian 4 matrix forming unit and the input of the diagonal matrix unit 5. Second the output of the control unit 13 is connected to the input of the decimation unit 3, the output of which is connected to the first and second input of the multiplier unit 6. The output of the unit of the multiplier 6 is connected to the first input of the multiplier 9, the third output of the control unit 13 is connected is connected to the second input of the block of the multiplier 9 and the second input of the block of the multiplier 8. The output of the block of the diagonal matrix 5 is connected to the first input of the block of the multiplier 8, the output of which is connected to the second input of the block of the adder 7. The output of the block of the formation of the matrix Laplacian 4 is connected to the first input of the block of the adder 7 whose output is connected to the input of the inverse matrix unit 10, the output of which is connected to the first input of the multiplier unit 11. The output of the multiplier unit 9 is connected to the input of the delay unit 16, the output of which is connected to the second input of the multiplier 11, the output which is connected to a first input of a linear interpolation unit 12. The output of delay unit 14 is connected to the second input of the linear interpolation block 12 delays the output of unit 15 is connected to a third input of a linear interpolation unit 12, whose output is the data output device. The synchronization of the device is provided by the clock generator 17.

A device for selecting the contours of objects on a textured background when processing digital images works as follows. At the same time, at the input of the decimation unit 1, the delay unit 14 and the control unit 13, the original image is received, which shows an object on an arbitrary background. Using the control unit 13 sets two two-dimensional array. The first array contains markers of the background and the selected object, the size of which corresponds to the size of one of the channels of the processed image (luminance or one of the color channels). An array of markers is a matrix containing values of two types. The first type of values refers to background markers and is located in array elements whose coordinates correspond to the coordinate area of the background pixels in the original image. The second type of values refers to the markers of the object and is located in the array elements whose coordinates correspond to the coordinates of the pixels of the object in the original image. Background and object markers only partially mark the corresponding areas of the original image. The remaining values of the elements of the marker array are equal to zero (unmarked areas). The second array contains only markers of an object whose size corresponds to the size of one of the channels of the processed image (luminance or one of the color channels). An array of markers is a matrix containing values related to the markers of the object and located in the elements of the array, the coordinates of which correspond to the coordinate region of the pixels of the background in the original image. Object markers only partially mark the corresponding area of the original image. The remaining values of the elements of the marker array are equal to zero (unmarked areas). An array containing the markers of the background and the selected object comes from the first output of the control unit 13 to the input of the decimation unit 2. An array containing the markers of the allocated object comes from the second output of the control unit 13 to the input of the decimation unit 3, in which the dimension of the array containing markers of the selected object twice. In decimation unit 2, the dimension of the array containing the background markers and the selected object is reduced by half. In the decimation unit 1, the resolution of the original image is reduced by half. At the same time, the first input of the Laplacian 4 matrix-forming unit and the input of the delay unit 15 are fed with a twice-reduced original image from the output of the decimation unit 1. At the second input of the Laplacian 4 matrix-forming unit, a twice-reduced array containing the background and selected object markers from the output is supplied decimation block 2. In the block of formation of the Laplacian matrix 4, a sparse Laplacian matrix is formed. At the input of the block of the diagonal matrix 5, a half-reduced array containing the markers of the selected object from the output of the decimation block 2 is fed, at the output of which, from the twice-reduced array containing the background markers and the selected object, a sparse diagonal matrix is formed. At the same time, the diagonal matrix from the output of the block of the diagonal matrix 5 is fed to the first input of the block of the multiplier 8, and the constant value from the third output of the control block 13 is fed to the second input. The result of the multiplication from the output of the block of the multiplier 8 goes to the second input of the block of the adder 7, the first input of which the sparse Laplacian matrix arrives from the output of the block forming the Laplacian matrix 4. In the adder block 7, the matrix summation of the Laplacian matrix and the diagonal matrix occurs. The result of the summation from the output of the adder block 7 is fed to the input of the inverse matrix block 10, where the input matrix of values is inverted. At the inputs of the block of the multiplier 6 is fed a half-reduced array containing the markers of the selected object from the output of the decimation block 3, at the output of which a vector is formed, each element of which is squared. The result of multiplication from the output of the block of the multiplier 6 is fed to the first input of the block of the multiplier 9, the second input of which is supplied with a constant value from the third output of the control unit 13. The result of the multiplication from the output of the block of the multiplier 9 is input to the block of the delay 16, from the output of which goes to the second input block of the multiplier 11, the first input of which receives the inverse matrix from the output of the block of the inverse matrix 10. The delay value of the delay block 16 is set in such a way as to ensure the synchronism of data from the output of the block of the mind scissors 9 and the output of the inverse matrix block 10. In the block of the multiplier 11, matrix multiplication of the sparse matrix by the column vector of the marker values is performed. At the same time, the result of multiplication (the alpha channel of the original image halved twice) from the output of the block of the multiplier 11 is supplied to the first input of the linear interpolation unit 12. The original image from the output of the delay unit 14 is fed to the second input of the linear interpolation unit 12, to the third input of which the reduced twice the original image from the output of the delay unit 15. The delay value of the delay units 14 and 15 is set in such a way as to ensure the synchronization of the data at the first, second and third inputs of the line block full interpolation 12. In the linear interpolation block, the resolution of the image of the alpha channel, which is a mask for selecting an object with a complex contour against an arbitrary textured background, is doubled by interpolation based on linear coefficients. The output of the linear interpolation unit 12 is the information output of the device. The synchronization of the device is provided by the clock generator 17.

The technical result is the selection of an object with a complex contour on an arbitrary textured background.

Claims (1)

A device for isolating the contours of objects on a textured background during digital image processing, comprising a Laplacian matrix forming unit (4), a diagonal matrix unit (5), characterized in by,what the information input of the device is a delay unit (14), a control unit (13), a decimation unit (1), the output of which is connected to the first input of the Laplacian matrix forming unit (4) and the input of the delay unit (15); the first output of the control unit (13) is connected to the input of the decimation unit (2), the output of which is connected to the second input of the Laplacian matrix forming unit (4) and the input of the diagonal matrix unit (5), the second output of the control unit (13) is connected to the input of the decimation unit (3), the output of which is connected to the first and second input of the multiplier unit (6), the output of which is connected to the first input of the multiplier (9); the third output of the control unit (13) is connected to the second input of the multiplier unit (9) and the second input of the multiplier unit (8); the output of the diagonal matrix block (5) is connected to the first input of the multiplier block (8), the output of which is connected to the second input of the adder block (7); the output of the Laplacian matrix generation block (4) is connected to the first input of the adder block (7), the output of which is connected to the input of the inverse matrix block (10), the output of which is connected to the first input of the multiplier block (11); the output of the multiplier unit (9) is connected to the input of the delay unit (16), the output of which is connected to the second input of the multiplier (11), the output of which is connected to the first input of the linear interpolation unit (12); the output of the delay unit (14) is connected to the second input of the linear interpolation unit (12), the output of the delay unit (15) is connected to the third input of the linear interpolation unit (12), the output of which is the information output of the device, the synchronization of the device is provided by the clock generator (17 )