CN104537607A - Automatic efficient photo collage method based on binary tree and layer sequencing - Google Patents

Abstract

The invention discloses an automatic and efficient photo collage method based on a binary tree and layered sorting, comprising the following steps: step 1, rapidly splitting the canvas based on a binary tree segmentation algorithm; Mapping, from the leaf node to the root node, traverse each internal node of the binary tree from bottom to top until the width-to-height ratio of each internal node is determined; step 3, for layer-by-layer nodes, calculate according to their width-to-height ratio The results are sorted; step 4, calculate the size and placement of the canvas represented by the nodes from top to bottom; the above process, step 2 and step 3 are carried out alternately, step 2 calculates the proportion of internal nodes layer by layer, step 3 the proportion of each layer The calculation results are sorted until the calculation of all nodes is completed. The invention is suitable for computers and intelligent mobile platforms; it can be used for photo album collage; and at the same time, different collage results can be generated for the same photo set, so as to meet different needs to the greatest extent.

Description

An Automatic and Efficient Photo Collage Method Based on Binary Tree and Hierarchical Sorting

technical field

The image processing technology of the present invention particularly relates to an automatic and efficient photo collage method.

Background technique

In recent years, with the continuous popularization of digital products such as smart phones and high-definition cameras, photos have become one of the main carriers for people to record their lives. This intuitive record is suitable for both recall and sharing. At the same time, various photo-sharing websites have emerged in an endless stream, allowing people to share photos at any time. However, a large number of photos not only makes management difficult, but also makes sharing inconvenient. As an important means of photo processing, photo collage aims to collage multiple photos into one canvas, which can well solve the inconvenience caused by a large number of photos. However, manual collage is not only time-consuming, but also usually requires certain professional skills, and the collage results are not satisfactory. Because of this, automatic photo collage technology is getting more and more attention. The automatic tiling technique is faster in processing speed and does not require professional skills. Algorithms to solve this kind of problems have been proposed, but they all have certain deficiencies.

For example, photo collage algorithms in two-dimensional and three-dimensional spaces have been proposed. Literature [1] is a two-dimensional photo collage method AutoCollage proposed by Microsoft: first, filter the input photos according to the size of the photos, ignore the smaller photos, and then detect and extract the region of interest (ROI) of each photo, and extract Collage and smooth the area, the whole process is time-consuming. Literature [2] uses the Voronoi diagram-based method to divide the canvas, and then calculates and determines the importance of each photo, and then adjusts the size of the photo according to the importance, and at the same time crops the photo to fit the shape of the sub-region, processing The process is also very time-consuming. Literature [3] collages them into a psychedelic photo by extracting the objects in the photo. Literature [4] and [5] both use a binary tree-based algorithm to divide the canvas, the difference is that the former takes the relationship between the photos into account when making a collage, and needs to make multiple adjustments, which will bring Time-consuming, the latter does not consider the interrelationship between photos, and is very fast in speed, but the collage result is prone to cracks and other unsatisfactory situations. In the 3D field, the Connection Constrained 3DCollage in [6] and the [Structured Mechanical Collage] in [7] collage photos into 3D models, which can be applied to fields such as game development.

Predecessors have proposed some collage methods, but it is difficult to achieve a good balance between processing speed and collage quality. Among them, the method based on the extraction of the region of interest needs to identify the region of interest, the processing process is very time-consuming, and will cause information loss; the method based on the complete preservation of the content is faster, but the collage result is not ideal.

references:

[1] Rother C, Bordeaux L, Hamadi Y, et al. Autocollage. ACM Transactions on Graphics (TOG), 2006, 25(3): 847-852.

[2] Yu Z, Lu L, Guo Y, Fan RF, Liu MM, Wang WP. Content-aware photo collage using circlepacking. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2): 182-195.

[3] Goferman S, Tal A, Zelnik-Manor L. Puzzle-like collage. Computer Graphics Forum, 2010, 29(2): 459-468.

[4]Atkins C B. Blocked recursive image composition. In Proceedings of the 16th ACM international conference on Multimedia, 2008, pp.821-824.

[5] Wu Z, Aizawa K. PicWall: Photo collage on-the-fly. In Proceedings of Signal and Information Processing Association Annual Summit and Conference (APSIPA), 2013, pp.1-10.

[6] Huang Z, Wang J, Lau Rynson WH, Fu HB. Connection constrained 3D collage. In Proceedings of Computer Graphics International, 2014.

[7]Huang Z, Wang J, Fu HB, Lau Rynson WH.Structured mechanical collage.IEEE Transactions on Visualization and Computer Graphics,2014,20(7):1076-1082.

Contents of the invention

In order to overcome the above-mentioned prior art, the present invention proposes an automatic and efficient photo collage method based on binary tree and layered sorting, which can realize an automatic photo collage algorithm that takes into account both speed and effect, and the algorithm has high processing efficiency and low hardware requirements It is not high and can be implemented on different platforms, including smartphones and PCs.

The present invention proposes a kind of automatic high-efficiency photo collage method based on binary tree and layered sorting, and this method comprises the following steps:

Step 1. Quickly split the canvas based on the binary tree segmentation algorithm. The result of the segmentation is to generate a complete binary tree in the canvas area, in which the number of leaf nodes in the tree is equal to the number of photos. The internal nodes of the tree store the attributes of the canvas segmentation type and the segmentation type attribute Including horizontal or vertical two, and randomly generated;

Step 2: Input the photo, complete the mapping between the photo and the tree node, traverse each internal node of the binary tree from the leaf node to the root node, until the width-to-height ratio of each internal node is determined;

Step 3. Sorting the layer-by-layer nodes according to the calculation results of their width-to-height ratios;

Step 4. Calculate the size and placement of the canvas represented by the nodes from top to bottom;

In the above process, step 2 and step 3 are performed alternately, step 2 calculates the proportion of internal nodes layer by layer, and step 3 calculates the calculation results of each layer until the calculation of all nodes is completed.

The calculation of the aspect ratio of each internal node in the step 2 specifically includes the following processing:

When calculating the width-to-height ratio of a parent node from a child node, if the parent node split type is "V", then the left and right child nodes have the same height; if the parent node split type is "H", then the left and right child nodes have the same width. The calculation formula is as follows:

The split type of the parent node is 'V': Ar _parent ＝Ar _left +Ar _right

Parent node split type is 'H': 1/Ar _parent ＝1/Ar _left +1/Ar _right

Among them, Ar represents the width-to-height ratio of the area represented by the node, Ar _parent represents the width-to-height ratio of the area represented by the parent node, Ar _left and Ar _right represent the width-to-height ratio of the area represented by the left and right child nodes of the parent node, respectively;

For a leaf node, its width-to-height ratio is the width-to-height ratio of its corresponding photo, and the width-to-height ratio of an internal node is calculated based on its left and right child nodes.

The calculation result of the width-to-height ratio of each internal node needs to meet a preset condition. If the calculation result exceeds the preset ratio range, adjust the division type of the parent node and recalculate.

The calculation formula for calculating the size of the canvas in step 4 is as follows:

Parent node split type is 'V':

node.Height=node.Parent.Height

node.Width=node.Height×node.Ar

Parent node split type is 'H':

node.Width = node.Parent.Width

node.Height=node.Width/node.Ar

In the formula, node.Height and node.Width represent the width and height of the area represented by the current node, respectively, node.Parent.Height and node.Parent.Width represent the height and width of the parent node of the current node, respectively, and node.Ar represents the current node The aspect ratio of the represented area.

The calculation formula for calculating the placement position of the canvas in the step 4 is as follows:

The node is the left child node

node.Pox = node.Parent.Pox

node.Poy = node.Parent.Poy

The node is the right child node

Parent node split type is 'V'

node.Pox = node.Parent.Left.Pox + node.Parent.Left.Width

node.Poy = node.Parent.Poy

Parent node split type is 'H'

node.Pox = node.Parent.Pox

node.Poy=node.Parent.Poy+node.Parent.Left.Height

In the formula, node.Pox and node.Poy represent the coordinates of the upper left corner of the area represented by the current node, node.Parent.Pox and node.Parent.Poy represent the abscissa and ordinate of the upper left corner of the area represented by the parent node of the current node, node.Parent.Left.Pox represents the abscissa of the upper left corner of the area represented by the left child node of the parent node of the current node, node.Parent.Left.Width and node.Parent.Left.Height represent the left child of the parent node of the current node The width and height of the region represented by the node.

In the third step, after the sorting is completed, the corresponding relationship between the sorting layer and its child node layers is adjusted so that the mapping relationship is satisfied again.

Compared with the prior art, the present invention can be used in photo album collage, picture retrieval result display, video summary collage and other fields, and different results can be produced by setting different parameters. At the same time, for the same photo set, different collage results can be produced to meet different needs to the greatest extent.

Description of drawings

Figure 1 is a schematic diagram of the collage results when the number of photos is 20;

Figure 2 is a schematic diagram of the collage results when the number of photos is 100;

Fig. 3 is a flow chart of the best embodiment of the present invention.

Detailed ways

The present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments, but the implementation scope of the present invention is not limited thereto.

The best implementation process mainly has the following steps: quickly generate a canvas partition binary tree, calculate the proportion of internal nodes layer by layer from bottom to top, sort layer by layer according to the settlement results, and calculate the size and position of nodes from top to bottom. The flowchart is shown in Figure 3:

Step 1. Quickly generate a canvas partition binary tree.

In order to quickly split the canvas, this step needs to generate a complete binary tree. The number of leaf nodes of the tree is equal to the number of photos to be collaged. The internal nodes of the tree store the split type (H or V), where H represents the horizontal split canvas, and V Represents vertically splitting the canvas, and the split type is randomly determined by the program. After the binary tree is generated, the input photos are sorted according to the aspect ratio of the photos. After the sorting is completed, the photos are mapped to the leaf nodes of the binary tree, and a photo uniquely corresponds to a leaf node.

Step 2. Calculate the width-to-height ratio of internal nodes layer by layer from bottom to top.

After completing the photo mapping, it is necessary to traverse the nodes of the binary tree from bottom to top to determine the width-to-height ratio of each internal node. When calculating the width-to-height ratio of a parent node from a child node, if the split type of the parent node is "V", the height of the left and right child nodes is the same; if the split type of the parent node is "H", the width of the left and right child nodes is the same. From this, the calculation formula can be derived:

Parent node split type is 'V': Ar _parent = Ar _left + Ar _right (1)

Parent node split type is 'H': 1/Ar _parent ＝1/Ar _left +1/Ar _right (2)

Among them, Ar represents the width-to-height ratio of the area represented by the node, Ar _parent represents the width-to-height ratio of the area represented by the parent node, and Ar _left and Ar _right represent the width-to-height ratio of the area represented by the left and right child nodes of the parent node. For a leaf node, its width-to-height ratio is the width-to-height ratio of its corresponding photo, and the width-to-height ratio of an internal node is calculated based on its left and right child nodes.

At the same time, it is also necessary to ensure that the calculation results meet the preset conditions during the calculation process. If the calculation results exceed the preset ratio range, adjust the division type of the parent node and recalculate. After completing the calculation of each layer of nodes, go to step 3.

Step 3. Sort layer by layer according to settlement results

In this step, the calculation results of each layer are mainly sorted (decreasing sort by default). If there is no such process, in the collage result, the probability that there will be a large size difference between adjacent photos is very high, which will affect the aesthetics of the collage result. Sorting layer by layer can avoid this situation, and ensure that the size of adjacent photos in the collage result is similar, making the collage result more beautiful.

After the sorting is completed, the corresponding relationship between the parent and child nodes needs to be adjusted, because the sorting process will break the original node corresponding relationship. Of course, only the corresponding relationship between the sorting layer and its child node layer needs to be adjusted, and other layers do not need to be adjusted.

It should be noted that: step 2 and step 3 are performed alternately, step 2 calculates the proportion of internal nodes layer by layer, and step 3 calculates the calculation results of each layer until the calculation of all nodes is completed.

Step 4. Calculate the size and position of nodes from top to bottom

This step should be carried out after the first three steps are completed. Firstly, calculate the size of the canvas according to the preset canvas height H or width W, combined with the width-to-height ratio of the root node of the tree.

The formula for calculating the canvas size is as follows:

Parent node split type is 'V': (3)

node.Height=node.Parent.Height

node.Width=node.Height×node.Ar

Parent node split type is 'H': (4)

node.Width = node.Parent.Width

node.Height=node.Width/node.Ar

In the formula, node.Height and node.Width represent the width and height of the area represented by the current node, respectively, node.Parent.Height and node.Parent.Width represent the height and width of the parent node of the current node, respectively, and node.Ar represents the current node The aspect ratio of the represented area.

The formula for calculating position is as follows:

The node is the left child node (5)

node.Pox = node.Parent.Pox

node.Poy = node.Parent.Poy

The node is the right child node

Parent node split type is 'V' (6)

node.Pox = node.Parent.Left.Pox + node.Parent.Left.Width

node.Poy = node.Parent.Poy

Parent node split type is 'H' (7)

node.Pox = node.Parent.Pox

node.Poy=node.Parent.Poy+node.Parent.Left.Height

In the formula, node.Pox and node.Poy represent the coordinates of the upper left corner of the area represented by the current node, node.Parent.Pox and node.Parent.Poy represent the abscissa and ordinate of the upper left corner of the area represented by the parent node of the current node, node.Parent.Left.Pox represents the abscissa of the upper left corner of the area represented by the left child node of the parent node of the current node, node.Parent.Left.Width and node.Parent.Left.Height represent the left child of the parent node of the current node The width and height of the region represented by the node.

For each node, first calculate the size of its canvas according to the calculation formula, and then calculate its position. Calculated from left to right for each layer.

The invention has low requirements on the operating environment and can run on ordinary smart phones and PCs.

Smartphone: more than 1G memory configuration

Computer: more than 2G memory configuration

Although the present invention has been described above in conjunction with the drawings, the present invention is not limited to the above-mentioned specific embodiments, and the above-mentioned specific embodiments are only illustrative, rather than restrictive. Under the inspiration, many modifications can be made without departing from the gist of the present invention, and these all belong to the protection of the present invention.

Claims (5)

1., based on an automatical and efficient photo collage effect method for binary tree and layer sorting, it is characterized in that, the method comprises the following steps:

Step one, based on binary tree partitioning algorithm, Fast Segmentation is carried out to painting canvas, segmentation result canvas area is produced a complete binary tree, the leaf node quantity wherein set is equal with number of pictures, the internal node of tree preserves the attribute of painting canvas segmentation type, segmentation type attribute comprises laterally or longitudinally two kinds, and produces at random;

Step 2, input photo, complete the mapping between photo and tree node, by leaf node to root node, each internal node of level binary tree traversal from bottom to top, until determine the wide high proportion of each internal node;

Step 3, to node successively, the result of calculation according to its wide high proportion sorts;

The size of step 4, from top to bottom painting canvas representated by computing node and putting position;

Above-mentioned flow process, step 2 and step 3 hocket, and step 2 successively calculates the ratio of internal node, and the result of calculation of the every one deck of step 3 sorts, until complete the calculating of all nodes.

2., as claimed in claim 1 based on the automatical and efficient photo collage effect method of binary tree and layer sorting, it is characterized in that, the calculating of the wide high proportion of each internal node in described step 2, specifically comprises following process:

When calculating the wide high proportion of father node by child node, if father node segmentation type is " V ", then child nodes height in left and right is consistent; If father node segmentation type is " H ", then child nodes width in left and right is consistent, and computing formula is as follows:

Father node segmentation type is ' V ': Ar _parent=Ar _left+ Ar _right

Father node segmentation type is ' H ': 1/Ar _parent=1/Ar _left+ 1/Ar _right

Wherein, the wide high proportion in region representated by Ar representation node, Ar _parentrepresent the wide high proportion in region representated by father node, Ar _leftand Ar _rightrepresent the wide high proportion in region representated by the child nodes of father node left and right respectively;

Its wide high proportion leaf node is to the wide high proportion of photo corresponding to it, the wide high proportion of internal node calculates according to its left and right child node and obtains.

3. as claimed in claim 1 or 2 based on the automatical and efficient photo collage effect method of binary tree and layer sorting, it is characterized in that, the result of calculation of the wide high proportion of described each internal node need meet pre-conditioned, if result of calculation exceeds preset ratio scope, then adjust the segmentation type of father node, re-start calculating.

4., as claimed in claim 1 based on the automatical and efficient photo collage effect method of binary tree and layer sorting, it is characterized in that, the size of the calculating painting canvas of described step 4, its computing formula is as follows:

Father node segmentation type is ' V ':

node.Height＝node.Parent.Height

node.Width＝node.Height×node.Ar

Father node segmentation type is ' H ':

node.Width＝node.Parent.Width

node.Height＝node.Width/node.Ar

In formula, node.Height and node.Width represents width and the height in the region representated by present node respectively, node.Parent.Height and node.Parent.Width represents height and the width of present node father node respectively, and node.Ar represents the wide high proportion in region representated by present node.

The putting position of the calculating painting canvas of described step 4, its computing formula is as follows:

Node is left child nodes

node.Pox＝node.Parent.Pox

node.Poy＝node.Parent.Poy

Node is right child nodes

Father node segmentation type is ' V '

node.Pox＝node.Parent.Left.Pox+node.Parent.Left.Width

node.Poy＝node.Parent.Poy

Father node segmentation type is ' H '

node.Pox＝node.Parent.Pox

node.Poy＝node.Parent.Poy+node.Parent.Left.Height

In formula, node.Pox and node.Poy represents the coordinate in the upper left corner in the region representated by present node, node.Parent.Pox and node.Parent.Poy represents horizontal ordinate and the ordinate in the upper left corner, region representated by present node father node, the horizontal ordinate in the upper left corner in region representated by the left child nodes that node.Parent.Left.Pox represents the father node of present node, the width in region representated by the left child nodes that node.Parent.Left.Width and node.Parent.Left.Height represents present node father node and height.

5., as claimed in claim 1 based on the automatical and efficient photo collage effect method of binary tree and layer sorting, it is characterized in that, in described step 3, after sequence completes, the corresponding relation of adjustment sequence layer and its child node layer, makes it again meet mapping relations.