RU2329535C2 - Method of automatic photograph framing - Google Patents

Abstract

FIELD: digital photography.

SUBSTANCE: automatic photograph framing method is suggested. In case of the album orientation of the image, the image horizontal line uniformity analysis is performed, whereas in case of the portrait orientation of the image, the image vertical line uniformity analysis is performed. The analysis is based on the line fragment clustering with the use of their texture attributes. Based on the analysis results, the number g(i) of different clusters including rectangular fragments covering the line, is determined. The g(i) number is used for estimating uniformity of the image line. Based on this estimation, the preliminary location of the image cutting frame is defined for the image. Then, the location of faces on the image is defined, and the position of the frame is corrected by finding the maximal y-coordinate y_t and the minimal y-coordinate y_b of the rectangles circumscribed around the defined faces with consecutive straightening of the image cutting frame with the centre of the vertical interval with its ends at the points y_t and y_b.

EFFECT: creating the modernized method of intellectual framing and cutting of digital images to be used in automatic devices of image processing and printing.

6 cl, 14 dwg

Description

The claimed invention relates to the field of digital photography and may find application in the design of automatic devices for printing high-quality digital photographs.

Currently, two main approaches are widely used to solve the problem of cropping photographs, not related to the analysis of its content. The first approach is to crop the upper and lower edges of the photo in a ratio of 50% to 50%, or 20% to 80%, respectively. This means that if the height of the photograph should be reduced by 1 cm, then horizontal and vertical stripes with a height of 5 and 5 mm, or 2 and 8 mm, respectively, will be cut off from above and below. In many cases, this approach does not crop important objects in the photograph located in the center of the picture. However, in those frequent cases where the subject, such as a person, is close to the edge of the photograph, this approach may result in cropping of parts of the face, head, or other parts of the person.

Another well-known approach is not to crop the photo, but to print it on a sheet, indenting left and right. The disadvantage here is that the area of the sheet of photo paper is not fully used.

Less well-known are the so-called intellectual cropping or cropping methods, in particular photographs. These methods are designed to change the aspect ratio of the image sides, i.e. the ratio of its width to height, by cropping the bottom and / or top, as well as the left and / or right side of the image. The term “intelligent” means that cropping a photograph is based on an analysis of its contents in order to exclude cropping of important objects captured in the photograph.

The need to change the aspect ratio of a photograph arises, for example, for users of digital cameras who want to print their digital photographs: ordinary digital photographs have an aspect ratio of 4: 3, whereas standard sheets of photo paper in automatic printing laboratories have an aspect ratio of 3: 2.

The main problem in the task of automatic cropping is to identify and segment the main object or objects in the image. Theoretical methods for determining the main object can be divided into two categories. Methods based on processing pixels separate individual pixels or small groups of pixels, which, as a rule, correspond to parts of objects captured in a photograph. Such methods include, for example, edge extraction methods. Methods based on the processing of regions select regions corresponding to entire semantically significant objects in the image.

To date, the theory of automatic trimming has been studied only superficially. The authors are not aware of image processing software packages in which the photo cropping function would clearly be based on highlighting the main objects of shooting.

Partial use of the smart method of cropping and cropping digital images is found in some recent publications. For example, program XV (see www.trilon.com/xv [1]) has the function of automatic cropping of images, which works as follows.

- Select the boundary lines and columns of the image, in particular, the upper and lower rows, the extreme columns on the left and right.

- Determine the brightness variations in the selected rows and columns. In grayscale images, completely uniform rows and columns are cropped. In color images, rows and columns with low spatial and spectral correlation are cropped.

- The two previous operations are repeated as many times as necessary.

Thus, the program removes relatively uniform areas along the edges of the image. It does not determine the content of the image as a whole. In practice, dark edges of scanned images resulting from inaccurate alignment of the original before scanning are effectively removed. Often, unsatisfactory results are obtained due to insufficient analysis of the contents of the scene.

In the application for US patent No. 59978519 [2] describes a method of cropping images based on the difference in intensity levels. A typical image contains both areas of uniform intensity and color, and areas where the intensity and color change significantly. For example, a portrait usually contains sharp brightness transitions from the main subject to the background. In the described method, the image size is reduced, and the image is divided into non-overlapping blocks. For each block, the mean and variance of the intensity are calculated. Based on the dispersion distribution in the blocks, a threshold is selected and all blocks with a dispersion above the threshold are marked as areas of interest. Areas of interest are then cut out with a bounding box.

It should be noted that this method is effective only when the original images contain both areas where the intensity levels are constant, and areas where the intensity levels vary significantly. It is expected that the effectiveness of the method will be comparable to [1]. The difference between [1] and [2] is that [1] analyzes the uniformity of the image line by line, while [2] analyzes the image block by block. Both methods, however, do not work well with images that have a heterogeneous background.

The smart cropping feature of Microsoft Digital Image Suite 2006 [3] has the ability to detect faces in portraits or family photographs. The program offers some cropping option, after which the user can select the desired aspect ratio from the list of standard print formats. In addition, the user can set the image size in pixels.

In the work of V. D. Gesu et al. in "Local operators to detect regions of interest," Pattem Recognition Letters, vol. 18, pp.1077-1081, 1997 [4] to measure local central moments and local radial symmetry, use the discrete momentum transformation (PDM) and the discrete symmetry transformation ( DPS). To exclude cases of trivial symmetry, the choice of an inhomogeneous region is necessary. The DPS operator acts as a detector of sharp boundaries, and the DPS operator acts as a detector of symmetric regions. The results of the two operators are combined using the logical AND operation. Morphological operations are used to dilate the contour map generated by the PDM operator.

In R. Milanese in "Detecting salient regions in an image: From biology to implementation", PhD thesis. University of Geneva, Switzerland, 1993 [5] developed a numerical model of visual attention, which combines knowledge of the human visual system with computer vision methods. The model consists of three main levels. First, based on the original image, multidimensional feature maps are created (orientation, curvature, color contrast, etc.). Then, using a derivative Gaussian model that identifies areas of interest on each feature map, “visibility” maps are constructed. Finally, the constructed maps are combined using the nonlinear relaxation method.

In the work of Q. Huang et al. in "Foreground / background segmentation of color images by integration of multiple cues," in Proc. IEEE Int. Conf. Image Process., 1995 [6] considered automatic segmentation of color images in the foreground and background using a multi-level segmentation scheme, including color clustering, automatic segmentation based on the principle of minimum description length (MDO), highlighting foreground / background by analyzing borders and joint segmentation based on boundaries and areas. The MAO-based segmentation algorithm is used to further group regions after the initial color clustering.

In T.F.Syeda-Mahmood in "Data and model-driven selection using color regions," Int. J. Comput. Vision, vol.21, no.1, pp.9-36, 1997 [7] proposed a method for selecting areas using color segmentation and measuring the importance of the area. A set of 220 basic color categories is converted to a color conversion table form. Pixels belonging to one of the color categories are grouped by analysis of connected components and then combined into the corresponding color categories. To determine the total importance of an area, two types of importance measures are used - absolute and relative - which are combined using heuristically selected weights. The absolute importance of an area includes color saturation, brightness, and size, while the relative importance includes color contrast and the aspect ratio between the area in question and its surroundings.

In general, almost all existing cropping methods are designed for certain types of images: photographs of people against a relatively simple background; museum photographs, in which the distinguished subject is in the center of the image with a uniform background; images of model scenes with several main objects of various colors and shapes. Some of these methods were not originally intended for processing arbitrary images, while the effectiveness of other methods developed using too general principles is shown only in simple images.

US patent No. 6282317 [8] describes a method for detecting the main object in the image. The method includes obtaining a digital image; extracting areas of arbitrary shape and size corresponding to the objects present in the image; grouping areas into larger areas corresponding to physically connected objects; extracting for each area at least one structurally distinguishable feature and at least one semantically distinguishable feature; an estimate for each selected area of the probability that this area corresponds to the main object.

US patent No. 665450 [9] describes a method of cropping digital images, which includes entering a trusted image map, the value at each point of which describes the importance of information at the corresponding point in the image; selection of scaling factor and cropping window; clustering areas of the trust card to determine areas of the background, secondary areas, and areas of the main object; positioning the cropping window in the region of the main object so that the sum of the confidence values inside the window is maximum; and crop the image to the borders of the crop window.

U.S. Patent Application Laid-Open No. 2002/0191861 [10] describes automatic and semi-automatic image cropping, and in particular, an apparatus and method for using an electronic camera to capture and crop images. An electronic device for cropping images includes image processing means, in particular, an electronic processor and programmable equipment and / or image processing software. The device identifies the features of the image composition and for each highlighted feature finds in a certain way a similar feature from among the predefined features stored in the device. Then one or more predefined compositional rules associated with the stored features are selected. A device determines one or more suitable framing boundaries by applying one or more selected compositional rules.

Solution [10] is the closest of all known solutions to the claimed invention and is selected as a prototype. In the analysis of the disadvantages of the prototype, the main focus was on the compositional composition of the frame. As you know, in the compositional composition of the frame, the photographer identifies the main objects, taking into account and determining the following factors:

- the location of objects within the frame,

- color, tone and texture contrast between the main objects and the background,

- lighting of the main objects.

If the photographer skillfully uses these factors, independent experts in most cases agree on which of the objects captured in the photograph are the main ones. This allows us to hope that, in principle, it is possible to create an automatic system for detecting the main objects in a photograph, which would use only the information available in the photograph, without taking into account the information about the objects and shooting conditions that the photographer had.

An analysis of the photographic image database containing more than 2000 images showed that more than 70% of photographs contain an image of a person, and approximately the same percentage of images contain faces of a rather large size (see S. Li, A.Jain "Handbook of Face Recognition", 2005 [eleven]). Therefore, in identifying the image of the main objects, an algorithm is useful that could effectively detect human faces. Although facial recognition studies were started a long time ago, until recently, this task has not received much attention. Over the past ten years, more attention has been paid to face recognition; there is an increase in the number and variety of face detection methods. The problem is that in this image of arbitrary size to determine the faces and their location. This problem is very difficult due to the fact that people can have different sizes and orientations. In addition, factors such as lighting conditions, the variability of form and facial expressions, the presence of additional objects or colors (glasses, cosmetics, beard) complicate the situation.

The literature describes a large number of methods for detecting faces. A comprehensive review of existing methods is given in [11]. According to this review, methods for detecting faces can be divided mainly into two categories: methods based on the analysis of the face as a whole, and methods based on the analysis of individual structural elements of the face. The methods of the last group reveal individual features of the face and then compare these features with the model of the face, while the methods of the first group are based on the analysis of the intensity of the writers. Methods based on the analysis of individual structural elements need a priori information about the face (head shape, shape and position of the eyes and mouth, complexion, texture and three-dimensional model of the face). On the contrary, methods based on the analysis of the face as a whole do not need any prior knowledge. It is known that these methods are better suited for detecting faces not from the front view, as well as for analyzing complex scenes. However, when processing simple scenes, methods based on the analysis of individual structural elements give better results.

The problem to which the invention is directed, is to develop an improved method of intelligent cropping and cropping of digital images, suitable for use in automatic processing and printing devices.

The technical result is achieved due to the fact that in the inventive method of automatically cropping photographs

- analysis of the homogeneity of horizontal, mainly in the case of landscape orientation of the image, and vertical, mainly in the case of portrait orientation, image strips based on the clustering of fragments of strips using their texture features;

- face detection;

- Correction of the position of the cropping lines taking into account information about the faces detected in the image.

Uniformity analysis is proposed to be performed in parallel with face detection. The method is applicable to both color and monochrome images in landscape or portrait orientation.

Distinctive features of the proposed method are the use of clustering image areas to assess the uniformity of the image strips and determine the position of the cropping lines, as well as an improved method for detecting faces to adjust the cropping lines.

The essence of the claimed invention is set forth below with the involvement of graphic materials.

Figure 1. The interaction scheme of the main components of the system that implements the inventive method.

Figure 2. The block diagram of the implementation of the proposed method of cropping.

Figure 3. Illustration for step 201 of the inventive framing method.

Figure 4. A block diagram of step 201 of the inventive framing method.

Figure 5. Block diagram of a face detector used.

6. Illustration for step 503 of the face detection technique.

7. Flow chart for checking Eyes and Mouth conditions.

Fig. 8. The illustration for step 703 for checking the Eye and Mouth condition.

Fig.9. The illustration for step 705 for checking the Eye and Mouth condition.

Figure 10. Illustration of the correction of the position of the cropping frame based on information about the faces detected in the image.

11-14. Examples of images cropped using the proposed method of cropping.

Figure 1 shows the main components of a system that implements the inventive method. A processor 101 controls the operation of the system and executes program code stored in the memory 104. The image to be processed is also stored in the memory 104.

After cropping, the image is transmitted to the display device 106. Using the input device 102, the user of the system accepts or rejects the received crop photo option. The cropped image is transmitted to the printing device 105. Data is exchanged using the data bus 103.

. Для этого необходимо разместить на исходном изображении размера 4l×3l пикселов (где l - некоторое целое число) рамку обрезки высотой

.The block diagram of the described method is presented in figure 2. Step 201 of the circuit is illustrated in FIG. 3. To change the aspect ratio of an image from 4: 3 to 3: 2, you must reduce its height by

. For this, it is necessary to place a cropping frame with a height of 4l × 3l pixels (where l is an integer)

.

3, the cropped frame centered vertically in the image is shown by dashed horizontal lines A, D. Dotted line B shows the upper edge of the frame at its extreme lower position in the image, line C the lower edge of the frame at its extreme upper position.

A block diagram of step 201 is shown in FIG. 4. At step 401, the specified color image is converted to monochrome with 256 brightness levels and is divided into P × Q adjacent rectangular fragments (shown by gray lines in FIG. 3).

At 402, texture attributes are computed for each rectangular fragment. In a preferred embodiment of the method, the following six features are used:

- average brightness;

- brightness variance σ ² ;

;-

;

, где h₁ есть доля пикселов фрагмента, имеющих яркость не более 128, h₂=1-h₁.-

, where h ₁ is the fraction of the pixels of the fragment having a brightness of not more than 128, h ₂ = 1-h ₁ .

- e = -h ₁ log ₂ h ₁ -h ₂ log ₂ h ₂ ;

-

At step 403, P · Q clustering of rectangular image fragments into k clusters is performed according to the calculated features. In a preferred embodiment of the method, a tree clustering algorithm is used. Thus, groups of fragments having similar texture features are distinguished.

At step 404, for each row i of the image, the number g (i) of the various clusters into which the rectangular fragments covering this row fell is calculated (FIG. 3). This number is an estimate of the uniformity of the image line. Lines with small g values are considered more homogeneous, and lines with high g values are considered less homogeneous and contain more information about the scene.

At steps 406, 408, 410 and 411, the preliminary position of the cropping frame is calculated in accordance with conditions 405, 407, 409.

The numbers P, Q, and k are tuning parameters of the method. In experiments with images of size 1024 × 768 pixels, the following parameters gave the best results: P = 32, Q = 32, k = 50.

In step 202 of the flowchart of FIG. 2, face detection is performed. There are a large number of face detection algorithms that can be used in this step. In a preferred embodiment of the method, a face detection algorithm is used that operates in accordance with the flowchart shown in FIG. 5 (see Commonly-assigned RU Laid-Open Patent Application "Method for automatic face detection in ready-for-print digital images" by A.Shakenov [12]). At step 501, faces are detected using a cascade of classifiers using Haar signs. Many rectangular fragments of various sizes are constructed corresponding to the detected faces. Each fragment of this set is further tested for the fulfillment of three conditions: “Size”, “Skin”, “Eyes and mouth”.

At step 502, the “Size” conditions are checked. A fragment of width w and height h pixels of an image of width v and height u of pixels satisfies this condition if one of the two inequalities holds:

,At step 503, the condition “Skin” is checked. A fragment satisfies this condition if the inequality holds:

,

where N is the number of all pixels of the subregion of the fragment shown in FIG. 6 in gray, and N _s is the number of pixels of this subregion, which in the RGB color space have the value of the red component, which exceeds the value of the green and blue components, and is five times smaller value than the blue component.

At step 504, the condition “Eyes and mouth” is checked in accordance with the flowchart shown in FIG. 7. At step 701, according to the rule described above, skin pixels are extracted. In step 702, an ellipse is described using the least squares method around the selected pixels. In the following steps, only the area inside this ellipse is considered.

At step 703, the eyes and mouth are filtered by reconciliation with the mask shown in FIG. The mask has a size of R ₁ × R ₂ , where R ₁ = 0.09h, R ₂ = 0.02w. At step 704, the image obtained after filtering is binarized by the threshold t = m + 2σ, where m is the average brightness of the resulting image, and σ is the standard deviation of the brightness.

At step 705, the isolation of the connected components occurs. In the areas corresponding to circles A, B and C shown in Fig. 9, one of the selected components with the maximum area is selected.

Finally, at step 706, the following conditions are checked:

- each circle must contain one component,

- x - the coordinate of the center of the component lying in the circle C should belong to the segment [x _A + 0,2D, x _B -0,2D], where X _A and X _B - x are the coordinates of the components lying in the circles A and B, accordingly, a D is the distance between these components.

The condition “Eyes and mouth” is considered fulfilled if the last two conditions are met.

Continue the consideration of the flowchart in figure 2. If faces were found in step 202, in the last step 204, the position of the cropping frame is adjusted. This adjustment can be performed, for example, in the following way (Figure 10).

- Find the minimum y-coordinate y _t and the maximum y-coordinate for _b rectangles described around the detected faces.

- The center of the cropping frame is aligned to the center of the vertical line with the ends at points y _t and y _b .

To conclude this section, we make a few comments.

- It follows from the flowchart of FIG. 2 that the face detection procedure can be applied to the input image in parallel with the procedure performed at step 201. In addition, the described flowchart can use the detection procedures for other semantically significant objects to prevent cropping of parts of the human bodies, monuments, etc.

- For the framing method implemented in the printer firmware, a runtime of about one minute is acceptable, since currently printing a single color page takes about one minute. Thus, while one photograph is being printed, the printer processor can crop the next photograph.

In the described embodiment of the invention, various modifications, additions and substitutions are possible without changing the scope and meaning of the invention, which is described by the attached claims.

11 shows examples of images cropped in the described manner.

The method can be implemented in image processing software packages, in the embedded software of printers, digital cameras and other devices connected to digital image printing devices.

When implementing the method in the software embedded in printers with an LCD display, the user can be added the ability to change the position of the cropping frame with the keys "up", "down".

Claims (6)

1. The method of automatic cropping of photographs, which consists in the fact that in the case of landscape orientation of the image analyze the uniformity of the horizontal lines of the image, and in the case of portrait orientation analyze the uniformity of the vertical lines of the image, the analysis is carried out on the basis of clustering of fragments of lines using their texture features ; the result of the analysis determines the number g (i) of various clusters that have rectangular fragments covering this row, the number g (i) is used to assess the uniformity of the image line, and the preliminary position of the cropping frame for the photos is determined by the results of the estimates, then detecting faces in the image and adjusting the position of the frame by finding the maximum y-coordinate at _t and the minimum y-coordinate at _b rectangles described around the detected faces and the subsequent alignment of the cropping frame with the center of the vertical line with the ends at points y _t and y _b . 2. The method according to claim 1, in which the tree clustering method is used. 3. The method according to claim 1, in which the method of clustering k-nearest neighbors is used. 4. The method according to claim 1, in which the following texture features are used: average brightness; variance of brightness σ ² ;

where h ₁ is the fraction of the pixels of the fragment having a brightness of not more than 128, h ₂ = 1-h ₁ . e = -h ₁ log ₂ h ₁ -h ₂ log ₂ h ₂ ;

5. The method according to claim 4, in which additional texture features based on the Fourier transform are used. 6. The method according to claim 1, wherein a procedure for detecting other semantically significant objects is used.

Images