CN103093447A

Movatterモバイル変換

Info

Publication number: CN103093447A
Application number: CN2013100223293A
Authority: CN
Inventors: 郭延文; 余宗桥; 范荣斐
Original assignee: Nanjing University
Current assignee: Nanjing University
Priority date: 2013-01-18
Filing date: 2013-01-18
Publication date: 2013-05-08
Anticipated expiration: 2033-01-18
Also published as: CN103093447B

Abstract

本发明公开了一种计算机图片集中图片剪切拼接方法，包括以下步骤：步骤1，重要度评估；步骤2，展示面板子区域划分得到每幅图片的显示空间：选取与图片集中图片数量相同的一组圆，其中各个圆的初始半径之间的比例与所述每幅图片的重要度之间的比例相同，通过圆填充方法填充展示面板，填充完成后由圆的外切多边形划分得到展示面板子区域，从而确定每幅图片在展示面板上的显示空间Q_p；步骤3，显示参数优化：确定每幅图片的朝向角θ，摆放位置、缩放尺度；步骤4，无缝混合渲染。本发明包括以下优点：更能满足人们对人物照片的客观需求。本发明会通过人脸检测设置显示人脸为最高优先级，从而有效的避免了人脸被其他照片的显示区域遮挡的情况。

The invention discloses a method for cutting and splicing pictures in a computer picture collection, comprising the following steps: step 1, evaluating the importance; step 2, dividing the display panel into sub-regions to obtain the display space of each picture: selecting the same number of pictures as the pictures in the picture collection A group of circles, where the ratio between the initial radii of each circle is the same as the ratio between the importance of each picture, the display panel is filled by the circle filling method, and the display panel is obtained by dividing the circumscribed polygon of the circle after filling Sub-area, so as to determine the display space Q_p of each picture on the display panel; step 3, display parameter optimization: determine the orientation angle θ, placement position, and zoom scale of each picture; step 4, seamless mixed rendering. The present invention has the following advantages: it can better meet people's objective requirements for photos of people. The present invention sets the display of human faces as the highest priority through human face detection, thereby effectively avoiding the situation that human faces are blocked by display areas of other photos.

Description

Translated fromChinese

一种计算机图片集中图片剪切拼接方法A method for cutting and splicing pictures in a computer picture collection

技术领域technical field

本发明涉及一种计算机图片集中图片剪切拼接方法，属于计算机图像、多媒体信息技术等领域。The invention relates to a method for cutting and splicing pictures in a computer picture collection, belonging to the fields of computer graphics, multimedia information technology and the like.

背景技术Background technique

随着手持照相设备的日益普及，人们拍照更加方便，获取的图片更加丰富，继而对图片集自动管理技术的需求更加突显。作为一种重要的图片集摘要和展示技术，图片拼贴近年来正受到越来越多的重视。图片拼贴的主要目的在于提供一个紧致、丰富而美观的图片集摘要图。由于手动制作这样的拼贴摘要图需要用到一些专业的图片编辑技巧同时耗时颇多，自动化的拼贴摘要图生成技术近年来成为了一个研究热点。With the increasing popularity of hand-held camera devices, it is more convenient for people to take pictures, and the pictures they get are more abundant, and then the demand for automatic management technology of picture collections is more prominent. As an important image collection summarization and presentation technique, image collage has been receiving more and more attention in recent years. The main purpose of a photo collage is to provide a compact, rich and aesthetically pleasing summary of a photo collection. Since manual production of such a collage summary map requires some professional image editing skills and is time-consuming, automated collage summary map generation technology has become a research hotspot in recent years.

传统的图片拼贴方法一般基于构造一个优化框架，将拼贴结果的好坏以某种客观标准加以量化，此优化方程通常具有复杂的非线性形式。由于每张图片的状态决定于若干参数，总共可能产生成百上千个参数需要优化。在如此复杂的非线性优化方程中求解如此规模的优化解通常是低效的，同时也很容易陷入局部最优解。尽管一些提升求解效率的方法已先后被提出，但此类方法仍有其固有的局限性。一方面，每张图片的最优状态参数往往与其它若干图片的状态紧耦合，导致某张图片状态的更新全局性或局部地影响到其它图片，从而导致拼贴的可扩展性很差。另一方面，各张图片通常都统一对待，图片的缩放因子很少被当成重要的影响因素，而若把不同图片的重要度信息加入考虑，将能提供更好的图片集摘要，同时有助于用户根据自己的喜好控制最终的拼贴结果。Traditional image collage methods are generally based on constructing an optimization framework to quantify the quality of the collage results with some objective standard, and this optimization equation usually has a complex nonlinear form. Since the state of each picture depends on several parameters, there may be hundreds or thousands of parameters that need to be optimized. Solving an optimization solution of such scale in such a complex nonlinear optimization equation is usually inefficient, and it is also easy to get stuck in a local optimum. Although some methods to improve the solution efficiency have been proposed successively, such methods still have their inherent limitations. On the one hand, the optimal state parameters of each picture are often tightly coupled with the states of several other pictures, resulting in the update of the state of a certain picture globally or locally affecting other pictures, resulting in poor scalability of the collage. On the other hand, each picture is usually treated uniformly, and the zoom factor of the picture is rarely regarded as an important influencing factor. If the importance information of different pictures is taken into consideration, it will be able to provide a better summary of the picture collection, and at the same time help Allow users to control the final collage result according to their own preferences.

发明内容Contents of the invention

发明目的：本发明提供一种计算机中图片剪切拼接方法，可以突出各个图片中的人物主体，更完整地保留图片的核心信息。Purpose of the invention: The present invention provides a method for cutting and splicing pictures in a computer, which can highlight the main body of the characters in each picture and retain the core information of the pictures more completely.

技术方案：本发明公开了一种计算机中图片剪切拼接方法，其核心在于确定图片在最终合成的图片中的显示空间以及其显示内容，包括以下步骤：Technical solution: the invention discloses a method for cutting and splicing pictures in a computer, the core of which is to determine the display space and display content of the picture in the final synthesized picture, including the following steps:

步骤1，重要度评估：衡量图片集中每幅图片的颜色特征，通过统计图片中颜色的多样性获得每幅图片的颜色复杂度S_C；采用土方移动距离方法计算图片集中各个图片之间的EMD距离（EarthMover’s Distance，简称EMD距离），将每幅图片与其他图片的EMD距离最小值作为该图片与图片集中其他图片的相似度S_D，将S_C和S_D的加权和作为该图片的重要度S_I。Step 1, importance evaluation: measure the color characteristics of each picture in the picture set, and obtain the color complexity S_C of each picture by counting the diversity of colors in the picture; use the earthwork moving distance method to calculate the EMD between pictures in the picture set Distance (EarthMover's Distance, referred to as EMD distance), the minimum value of the EMD distance between each picture and other pictures is used as the similarity_SD between the picture and other pictures in the picture set, and the weighted sum of_SC and_SD is used as the important value of the picture Degree S_I .

步骤2，展示面板子区域划分得到每幅图片的显示空间：选取与图片集中图片数量相同的一组圆，其中各个圆的初始半径之间的比例与所述每幅图片的重要度之间的比例相同，通过圆填充方法（Circle Packing）填充展示面板，填充完成后由圆的外切多边形划分得到展示面板子区域，从而确定每幅图片在展示面板上的显示空间Q_p。Step 2: Divide the sub-regions of the display panel to obtain the display space of each picture: select a group of circles with the same number of pictures in the picture collection, and the ratio between the initial radii of the circles and the importance of each picture The proportions are the same, and the display panel is filled by the circle packing method (Circle Packing). After the filling is completed, the sub-area of the display panel is divided by the circumscribed polygon of the circle, so as to determine the display space Q_p of each picture on the display panel.

步骤3，显示参数优化：确定每幅图片的朝向角θ，摆放位置、缩放尺度，以使各幅图片在获得的有限的面板子区域空间内最大化地呈现其重要区域，获得图片在面板上的显示内容。首先在给定范围内设定每一幅图片的朝向角θ；计算每个图片的重要度图（Saliency Map），用于表示图片中像素的重要程度。将含有人脸图像的图片中人脸图像区域内每个像素的重要度值置为最大值；将每个图片中高于预设重要度阈值的像素组成连通区域，按照连通区域面积由大至小排序后，将面积排序前1/3的连通区域划分至一个多边形区域内，该多边形区域即是该图片的ROI区域Q_r（Region of Interest，简称ROI关注区域）。然后根据图片设定的朝向角θ、图片的ROI区域Q_r以及步骤2中确定的图片对应的显示空间Q_p，确定信息损失最小的图片摆放位置和缩放尺度。Step 3, display parameter optimization: determine the orientation angle θ of each picture, place it, and scale it, so that each picture can maximize its important area in the limited panel sub-area space obtained, and obtain the picture in the panel displayed on the screen. First, set the orientation angle θ of each picture within a given range; calculate the importance map (Saliency Map) of each picture, which is used to represent the importance of pixels in the picture. Set the importance value of each pixel in the face image area in the picture containing the face image to the maximum value; the pixels higher than the preset importance threshold in each picture form a connected area, and the area of the connected area is from large to small After sorting, divide thetop 1/3 of the connected areas into a polygonal area, and this polygonal area is the ROI area Q_r (Region of Interest, referred to as ROI area of interest) of the picture. Then, according to the orientation angle θ set by the picture, the ROI area Q_r of the picture, and the display space Q_p corresponding to the picture determined in step 2, determine the picture placement position and zoom scale with the least information loss.

步骤4，无缝混合渲染，基于概率混合模型对展示面板子区域之间的边界区域进行无缝混合渲染，从而完成计算机图片集中图片剪切拼接。Step 4, seamless mixed rendering, based on the probabilistic mixed model, performs seamless mixed rendering on the boundary area between the sub-areas of the display panel, so as to complete the cutting and splicing of the pictures in the computer picture collection.

步骤1中，通过图片的复杂度和辨识度来评判图片的重要性。Instep 1, the importance of the picture is judged by the complexity and recognition of the picture.

所述步骤1具体包括以下步骤：Describedstep 1 specifically comprises the following steps:

步骤11，为衡量图片的复杂度，本方法选取最简单的颜色特征加以衡量。本方法用HSV（H，Hue，色调通道；S，Saturation，饱和度；V，Value，亮度）颜色空间上的直方图统计信息定义颜色的复杂度。H通道上的颜色复杂度定义如下：Step 11, in order to measure the complexity of the picture, this method selects the simplest color feature to measure. This method uses the histogram statistics on the HSV (H, Hue, hue channel; S, Saturation, saturation; V, Value, brightness) color space to define the complexity of the color. The color complexity on the H channel is defined as follows:

${S S}_{c c}^{H h} = = 11 - - \frac{\sqrt{{Σ Σ}_{i i = = 11}^{{m m}^{H h}} {(({h h}_{i i}^{H h} - - \frac{11}{{m m}^{H h}}))}^{22}}}{{δ δ}_{max max}^{H h}} - - - - - - ((11));;$

其中m^H代表H通道上统计直方图的分区数，在本文实验中设为16；

定义为落在第i个分区内像素频数；为所有频数的最大范围，作为颜色复杂度S_C的归一化因子。如果图片的H通道为常量，即H通道的直方图只有一个分区有值，这时

定义为Among them, m^H represents the number of partitions of the statistical histogram on the H channel, which is set to 16 in this experiment;

Defined as the frequency of pixels falling in the i-th partition; is the maximum range of all frequencies, and is used as the normalization factor of the color complexity S_C . If the H channel of the picture is constant, that is, the histogram of the H channel has only one partition with a value, then

defined as

${δ δ}_{max max}^{H h} = = \sqrt{{((11 - - \frac{11}{{m m}^{H h}}))}^{22} + + \frac{{m m}^{H h} - - 11}{{(({m m}^{H h}))}^{22}}} - - - - - - ((22));;$

S通道上的复杂度值

采用以下公式计算:Complexity value on S channel

Calculated using the following formula:

${S S}_{c c}^{S S} = = 11 - - \frac{\sqrt{{Σ Σ}_{i i = = 11}^{{m m}^{S S}} {(({h h}_{i i}^{S S} - - \frac{11}{{m m}^{S S}}))}^{22}}}{{δ δ}_{max max}^{S S}} - - - - - - ((33));;$

其中m^S为S通道上统计直方图的分区数，在本文实验中设为16；

定义为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度的归一化因子；如果图片的S通道为常量，则定义为采用如下公式计算：Among them, m^S is the number of partitions of the statistical histogram on the S channel, which is set to 16 in this experiment;

Defined as the frequency of pixels falling in the i-th partition;

is the largest range of all frequencies, as color complexity The normalization factor of ; if the S channel of the picture is constant, then Defined as calculated using the following formula:

${δ δ}_{max max}^{S S} = = \sqrt{{((11 - - \frac{11}{{m m}^{S S}}))}^{22} + + \frac{{m m}^{S S} - - 11}{{(({m m}^{S S}))}^{22}}} - - - - - - ((44));;$

V通道上的复杂度值

采用以下公式计算:Complexity value on the V channel

Calculated using the following formula:

${S S}_{c c}^{V V} = = 11 - - \frac{\sqrt{{Σ Σ}_{i i = = 11}^{{m m}^{V V}} {(({h h}_{i i}^{V V} - - \frac{11}{{m m}^{V V}}))}^{22}}}{{δ δ}_{max max}^{V V}} - - - - - - ((55)),,$

其中m^V为V通道上统计直方图的分区数，在本文实验中设为16；

定义为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度

的归一化因子；如果图片的V通道为常量，则

定义为采用如下公式计算：Among them, m^V is the number of partitions of the statistical histogram on the V channel, which is set to 16 in this experiment;

Defined as the frequency of pixels falling in the i-th partition;

is the largest range of all frequencies, as color complexity

The normalization factor of ; if the V channel of the picture is constant, then

Defined as calculated using the following formula:

${δ δ}_{max max}^{V V} = = \sqrt{{((11 - - \frac{11}{{m m}^{V V}}))}^{22} + + \frac{{m m}^{V V} - - 11}{{(({m m}^{V V}))}^{22}}} - - - - - - ((66)),,$

最后的颜色复杂度即为：The final color complexity is:

${S S}_{C C} = = \frac{{S S}_{C C}^{H h} + + {S S}_{C C}^{S S} + + {S S}_{C C}^{V V}}{33} - - - - - - ((77));;$

步骤12，本方法采用土方移动距离（Earth Mover’s Distances，简称EMD距离，该度量的详细描述参见YOSSI RUBNER等发表于International Journal ofComputerVision的论文《The Earth Mover’s Distance as a Metric for Image Retrieval》）来计算图片之间的两两相似度。EMD距离用两幅图片在某一特征下的统计直方图的对齐代价E(G_I，G_I′，{f_ij})作为衡量图片相似程度的标准，该过程如下描述：Step 12, this method uses Earth Mover's Distances (EMD distance for short, for a detailed description of this measure, refer to the paper "The Earth Mover's Distance as a Metric for Image Retrieval" published by YOSSI RUBNER et al. in the International Journal of Computer Vision) to calculate the image pairwise similarity between them. The EMD distance uses the alignment cost E(G_I , G_I ′, {f_ij }) of the statistical histograms of two pictures under a certain feature as the standard to measure the similarity of the pictures. The process is described as follows:

最小化： $E (D_{I}, G_{I^{'}}, {f_{ij}}) = Σ_{i = 1}^{24} Σ_{j = 1}^{24} f_{ij} d_{ij},$ minimize: $E. ({D.}_{I}, G_{I^{'}}, {f_{ij}}) = Σ_{i = 1}^{twenty four} Σ_{j = 1}^{twenty four} f_{ij} d_{ij},$

满足前提：f_ij≥0其中i∈[1，24]，j∈[1，24]，Satisfy the premise: f_ij ≥ 0 where i∈[1, 24], j∈[1, 24],

$\underset{j}{Σ} = f_{ij} \leq g_{i}$ 其中i∈[1，24]， $\underset{j}{Σ} = f_{ij} \leq g_{i}$ where i ∈ [1, 24],

$\underset{i}{Σ} = f_{ij} \leq {g^{'}}_{i}$ 其中j∈[1，24]， $\underset{i}{Σ} = f_{ij} \leq {g^{'}}_{i}$ where j ∈ [1, 24],

${Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij} = = min min (({Σ Σ}_{i i = = 11}^{24 twenty four} {g g}_{i i},, {Σ Σ}_{j j = = 11}^{24 twenty four} {g g}^{' '}_{j j})),,$

其中G_I＝{g_i，i＝1，…，24}，G_I，＝{g′_j,j＝1，…，24}，where G_I ={g_i , i=1,...,24}, G_I ,={g'_j ,j=1,...,24},

EMD距离用两幅图片在一特征下的统计直方图的对齐代价作为衡量图片相似程度，EMD距离采用以下公式计算：The EMD distance uses the alignment cost of the statistical histogram of two pictures under a feature as a measure of the similarity of the pictures. The EMD distance is calculated using the following formula:

G_I＝{g_i，i＝1，…，24}，G_I，＝{g′_j，j＝1，…，24} (8)，G_I ={g_i , i=1,...,24}, G_I ,={g'_j , j=1,...,24} (8),

$EMD EMD (({G G}_{I I},, {G G}_{{I I}^{' '}})) = = \frac{{Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij} {d d}_{ij ij}}{{Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij}} - - - - - - ((99));;$

公式（8）中G_I和G_I，分别为图片I和图片I′对应的HSV颜色空间直方图特征向量，其中H通道分成16个子块，S通道和V通道都划分成4个子块，三个通道共同组成一个24维的颜色特征向量G_I和G_I′，其中的g_i和g′_j代表子通道中划分的子块。公式（9）计算获得图片I和图片I′的EMD距离，中f_ij表示g_i和g′_j两子块之间的流（flow），d_ij表示g_i和g′_j两子块之间的L1距离。G_I and G_I in formula (8) are the HSV color space histogram feature vectors corresponding to picture I and picture I′ respectively, where the H channel is divided into 16 sub-blocks, the S channel and V channel are divided into 4 sub-blocks, and the three channels together form a 24-dimensional color feature vector G_I and G_I ′, where g_i and g′_j represent sub-blocks divided in sub-channels. Formula (9) calculates the EMD distance between picture I and picture I′, where f_ij represents the flow between two sub-blocks g_i and g′_j , and d_ij represents the flow between two sub-blocks g_i and g′_j The L1 distance between them.

本方法应用快速EMD计算方法（该算法可参见Ofir Pele，Michael Werman发表于ICCV的论文《Fast and Robust Earth Mover’s Distances》）得到图片集中每一幅图片与图片集中其他图片间EMD距离并选取其中的最小值作为该图片的辨识度S_D。This method uses the fast EMD calculation method (for this algorithm, please refer to the paper "Fast and Robust Earth Mover's Distances" published by Ofir Pele and Michael Werman in ICCV) to obtain the EMD distance between each picture in the picture set and other pictures in the picture set, and select the The minimum value is taken as the recognition degree_SD of the picture.

步骤13，最后图片的重要度S_I定义为：Step 13, the importance S_I of the final picture is defined as:

S_I＝S_C+ωS_D （10）；S_I =S_C +ωS_D (10);

其中ω用于控制两者之间的影响权重，ω取值范围为0~1之间的实数，在本方法中ω均取0.3。Among them, ω is used to control the influence weight between the two, and the value range of ω is a real number between 0 and 1. In this method, ω takes 0.3.

步骤2中，利用步骤1中获得的每幅图片的重要度信息确定一系列半径与重要度信息相关联的圆，然后通过圆填充（Circle Packing）算法实现显示区域划分以确定图片在最终结果里的显示区域。圆填充算法的目标是针对一系列不同半径的圆，在允许均一缩放的条件下，将所有圆紧致的放入一特定形状的平面容器内，最后还可根据结果方便计算出包含每个单独圆的子区域划分。In step 2, use the importance information of each picture obtained instep 1 to determine a series of circles whose radii are associated with the importance information, and then use the circle packing (Circle Packing) algorithm to realize the display area division to determine the picture in the final result display area. The goal of the circle filling algorithm is to fit a series of circles with different radii into a plane container of a specific shape compactly under the condition of allowing uniform scaling, and finally, according to the result, it is convenient to calculate the number of circles containing each individual Circle subdivision.

步骤2具体包括以下步骤：Step 2 specifically includes the following steps:

步骤21，设定圆心的初始位置。对于给定的展示面板Ω和共有n幅图片的图片集，将展示面板中心置于一个二维右手坐标系（坐标系拥有X和Y两条坐标轴）的原点位置，然后在展示面板所在的坐标系范围内随机生成n个点作为圆心的初始位置，将圆心按照其X坐标的值由小到大进行排序，对于X坐标值相同的情况，Y坐标值小的圆心在前，由小到大对每个圆心分配一个标号i，i的取值范围为1～n的整数，圆心i对应圆C_i，圆的初始半径为R_i；Step 21, setting the initial position of the center of the circle. For a given display panel Ω and a picture set with a total of n pictures, place the center of the display panel at the origin of a two-dimensional right-handed coordinate system (the coordinate system has two coordinate axes, X and Y), and then place the display panel where Randomly generate n points within the scope of the coordinate system as the initial position of the center of the circle, and sort the centers according to their X coordinate values from small to large. Assign a label i to each center of the circle, the value of i is an integer ranging from 1 to n, the center i corresponds to the circle C_i , and the initial radius of the circle is R_i ;

步骤22，设定圆的初始半径R_i。将图片集内的图片分别与一个标号的圆所对应，其对应的复杂度为比较步骤11中圆心两两之间的距离后获得距离最近的两个圆心之间的距离D_min，则圆的初始半径R_i计算公式如下：Step 22, setting the initial radius R_i of the circle. Correspond the pictures in the picture set to a labeled circle respectively, and the corresponding complexity is After comparing the distances between the centers of the two circles in step 11, the distance D_min between the two nearest centers is obtained, and the calculation formula for the initial radius R_i of the circle is as follows:

${R R}_{i i} = = \{\begin{matrix} \frac{{D D.}_{min min}}{22},, & i i = = 11;; \\ \frac{{S S}_{I I}^{i i} * * {R R}_{11}}{{S S}_{I I}^{11}},, & 11 < < i i \leq \leq n no;; \end{matrix} - - - - - - ((1111));;$

其中

为标号为1的图片的复杂度，

为标号为i的图片的复杂度，R₁标号为1的圆的半径；in

is the complexity of the picture labeled 1,

is the complexity of the picture labeled i,_R1 is the radius of the circle labeled 1;

步骤23，圆填充方法对展示面板Ω区域进行圆填充。获得圆的初始圆心位置和初始半径后，在保证圆与圆之间不相交并且所有圆在展示面板Ω的区域内的前提下，对所有圆进行同比例放大，放大完成后，动态调整圆心位置，重复执行放大调整过程，直至无法继续放大时，停止该过程，并获得在展示面板Ω区域内圆的紧致排列。Step 23, the circle filling method performs circle filling on the Ω area of the display panel. After obtaining the initial center position and initial radius of the circle, under the premise that the circles do not intersect each other and all circles are within the area of the display panel Ω, all circles are enlarged in the same proportion. After the enlargement is completed, the position of the center of the circle is dynamically adjusted , the process of zooming in and adjusting is repeated until the process of zooming in cannot be continued, and the process is stopped, and a compact arrangement of circles in the region Ω of the display panel is obtained.

圆填充算法在步骤2中的主要作用就是在给定区域Ω中获得一个区域内圆都不重叠的紧致“布局”（Conguration）,其中圆填充算法具体描述如下：The main function of the circle filling algorithm in step 2 is to obtain a compact "conguration" in which circles do not overlap in a given area Ω. The circle filling algorithm is specifically described as follows:

对于一个给定展示面板

和n个与图片集中特定图片相对应圆

对应圆的半径是

圆填充算法在步骤。在算法初始化时，给定所有圆一个初始化缩放因子

k＝1，圆C_i变成kC_i，圆填充算法可以描述成以下一个优化问题：For a given display panel

And n circles corresponding to specific pictures in the picture set

The radius of the corresponding circle is

Circle filling algorithm in steps. When the algorithm is initialized, all circles are given an initial scaling factor

k=1, the circle C_i becomes kC_i , the circle filling algorithm can be described as the following optimization problem:

最大化：kMaximize: k

满足前提：

i∈{1，…，n}Satisfy the prerequisites:

i ∈ {1,...,n}

i，j∈{1，…，n}，i≠j.

i, j ∈ {1,...,n}, i≠j.

获得的圆心位置集合用X＝(x₁，…，x_n)表示，其中x_i表示圆C_i的圆心坐标。本方法将X称为一个“布局”，如果所有圆满足上面提到的两个约束，则这个称X为一个“有效布局”。The set of obtained circle center positions is represented by X=(x₁ , . . . , x_n ), where x_i represents the center coordinates of circle C_i . This method refers to X as a "layout", which is called a "valid layout" if all circles satisfy the two constraints mentioned above.

针对上述的优化过程，本方法采用一种基于权值图（Power diagram）的圆填充算法进行解决。For the above optimization process, this method uses a circle filling algorithm based on the weight diagram (Power diagram) to solve it.

权值图是一种带权沃罗诺伊图（Voronoi diagram，关于沃罗诺伊图的详细介绍可以参加Q Du等发表于SIAM的论文《Centroidalvoronoi tessellations:Applications andalgorithms》），

为一组不同的点，点x_i都有各自的一个权值ω_i≥0，i＝1，…，n。给定区域内点x到点x_i的权值距离（Power distance）d_ω(x，x_i)定义如下：The weight graph is a weighted Voronoi diagram (Voronoi diagram, for a detailed introduction to the Voronoi diagram, please refer to the paper "Centroidalvoronoi tessellations: Applications and algorithms" published by Q Du et al. in SIAM),

is a group of different points, each point x_i has its own weight ω_i ≥ 0, i=1, . . . , n. The weight distance (Power distance) d_ω (x, x_i ) from point x to point x_i in a given area is defined as follows:

d_ω(x，x_i)＝||x-x_i||²-ω_i （12）；d_ω (x, x_i ) = ||xx_i ||² -ω_i (12);

然后根据d_ω(x，x_i)来对进行区域划分，定义与点x_i相对应的区域Q(x_i)如下：Then according to d_ω (x, x_i ), the region is divided, and the area Q(x_i ) corresponding to point x_i is defined as follows:

所有的Q(x_i)集合构成的点集合X的一个权值图。A weight map of the point set X composed of all Q(_xi ) sets.

给定一个区域Ω_i表示Q(x_i)与Ω的交集：given a region Ω_i represents the intersection of Q(_xi ) and Ω:

Ω_i＝Q(x_i)∩Ω （14）；Ω_i = Q(x_i )∩Ω (14);

则所有Ω_i组成的集合构成了一个在区域Ω内的点集合X的一个权值图，其中Ω_i被称为与点x_i相对应的“小室”（Cell）。Then the set of all Ω_i constitutes a weight map of a point set X in the area Ω, where Ω_i is called the "cell" (Cell) corresponding to the point_xi .

应用到本方法中，权值为ω_i的点x_i表示以点x_i为圆心，

半径的圆，即ω_i＝R_i²。并且由于优化过程需要满足的前提为圆与圆不能重叠，所以，所有的圆都被包含于圆心x_i的“小室”Ω_i内，不能超出小室Ω_i的范围。Applied to this method, the point x_i with the weight of ω_i represents the point x_i as the center of the circle,

A circle of radius, ie ω_i =R_i² . And because the premise that the optimization process needs to satisfy is that circles cannot overlap, all circles are included in the "small room" Ω_i of the center x_i , and cannot exceed the range of the small room Ω_i .

为了计算沃罗诺伊图，本方法采用Lloyd的方法（该方法具体可参见S Lloyd等发表于IEEE Transactions on Information Theory的论文《Least squares quantization in PCM》）动态调整圆心的位置，直至获得最大的缩放因子k，根据缩放因子k来获得一个在给定区域内对于给定数目圆在保证圆之间的半径比的前提下的紧致排列，圆填充至此停止。In order to calculate the Voronoi diagram, this method uses Lloyd's method (for details, please refer to the paper "Least squares quantization in PCM" published by S Lloyd et al. in IEEE Transactions on Information Theory) to dynamically adjust the position of the center of the circle until the maximum Scaling factor k, according to the scaling factor k to obtain a compact arrangement for a given number of circles in a given area under the premise of ensuring the radius ratio between the circles, the circle filling stops here.

步骤24，展示面板的子区域划分，得到每幅图片的显示空间。根据步骤23获得的圆在展示面板Ω内的最终位置，在任意两个相邻圆之间设置一条两个相邻圆的圆心连线的垂直平分线，一个圆周围所有垂直平分线交错形成的封闭多边形构成了展示面板的子区域，其中包含圆C_i的多边形Q_p即是与其相关联的图片i所对应的显示空间。。Step 24, divide the sub-regions of the display panel to obtain the display space of each picture. According to the final position of the circle in the display panel Ω obtained instep 23, a vertical bisector of the line connecting the centers of two adjacent circles is set between any two adjacent circles, and all vertical bisectors around a circle are formed by interlacing The closed polygon constitutes the sub-area of the display panel, and the polygon Q_p containing the circle C_i is the display space corresponding to the picture i associated with it. .

步骤3，显示参数优化过程中，通过计算设定每幅图片的朝向角、摆放位置和缩放尺度使得每幅图片在步骤2中获得的显示空间内最大化地呈现其主要内容。步骤3具体包括以下步骤：Step 3, in the display parameter optimization process, set the orientation angle, placement position and zoom scale of each picture through calculation so that each picture can maximize its main content in the display space obtained in step 2. Step 3 specifically includes the following steps:

步骤31，设定图片朝向角。本方法赋予每幅图片一个随机的朝向角θ，θ满足[-θ_m,θ_m]范围内的平均分布，其中θ_m为最大允许偏转角，本方法设置θ_m为30°，从而使得图片展示具有视觉上的多样性，而不是单调死板。Step 31, setting the orientation angle of the picture. This method gives each picture a random orientation angle θ, θ satisfies the average distribution within the range of [-θ_m ,θ_m ], where θ_m is the maximum allowable deflection angle, and this method sets θ_m to 30°, so that the picture Displays are visually diverse, not monotonous.

步骤32，确定坐标和缩放尺寸。Step 32, determine the coordinates and scaling size.

首先，获得图片重要度图。通过程明明等提出的方法计算图片的重要度图（SaliencyMap）（该部分算法可以参见程明明等发表于CVPR的论文《Global Contrast based SalientRegionDetection》），借助重要度图中每个像素点对应的重要度值（Saliency）来反映每个像素的重要度，重要度值越大，表明该像素能够在最终拼接结果中显示的概率越大；为了保证人们通常更加敏感的人脸能得到充分显示，使用OpenCV中的人脸检测算法（该算法可参见PaulViola和MichaelJones发表于CVPR的《RapidObjectDetectionusingaBoostedCascadeofSimpleFeature》）检测人脸区域，将该区域内重要度图的重要度值置为最大。First, obtain the image importance map. Calculate the importance map (SaliencyMap) of the image through the method proposed by Cheng Mingming et al. (For this part of the algorithm, please refer to the paper "Global Contrast based SalientRegionDetection" published by Cheng Mingming et al. in CVPR), with the help of the importance of each pixel in the importance map Saliency value (Saliency) to reflect the importance of each pixel, the greater the importance value, the greater the probability that the pixel can be displayed in the final stitching result; in order to ensure that people's usually more sensitive faces can be fully displayed, use The face detection algorithm in OpenCV (for this algorithm, please refer to "Rapid Object Detection using a Boosted Cascade of Simple Feature" published by PaulViola and Michael Jones in CVPR) detects the face area, and sets the importance value of the importance map in the area to the maximum.

然后，获得图片ROI区域。对获得的重要度图基于阈值进行二值化处理，阈值为0~1之间的实数，本方法设定为0.618，然后经过侵蚀与扩张操作（侵蚀与扩张均属于形态学的基本处理手段，具体方法可参见JY Gil,R Kimmel发表于Pattern Analysis andMachine Intelligence的论文《Efficient dilation,erosion,opening,and closing algorithms》）获得若干个连通区域，按照连通区域面积由大至小排序后，通过Sklansky，J.提出的最小凸包算法（该部分方法可参见Sklansky，J.发表于Pattern Recognition Letters上的论文《Finding the Convex Hull of a Simple Polygon》）用一个凸多边形包围面积排序前三分之一的单连通区域，所得多边形Q_r即为图片ROI区域。Then, the image ROI area is obtained. The obtained importance map is binarized based on the threshold value. The threshold value is a real number between 0 and 1. This method is set to 0.618, and then undergoes erosion and expansion operations (both erosion and expansion belong to the basic processing methods of morphology. For specific methods, please refer to the paper "Efficient dilation, erosion, opening, and closing algorithms" published by JY Gil and R Kimmel in Pattern Analysis and Machine Intelligence) to obtain several connected regions, sort them according to the area of connected regions from large to small, and pass Sklansky, The minimum convex hull algorithm proposed by J. (for this part of the method, please refer to the paper "Finding the Convex Hull of a Simple Polygon" published by Sklansky, J. on Pattern Recognition Letters) uses a convex polygon to enclose the first third of the sorted area The single connected area, the obtained polygon Q_r is the image ROI area.

最后，确定图片坐标和缩放尺度。Q_r和Q_p分别表示图片ROI区域多边形和图片所对应的展示画板显示空间。首先，将Q_r的重心P_r于Q_p的中心位置，朝向角θ之前已经确定，该图片恰好完全覆盖展示空间时的缩放尺度即为缩放尺度的初始值。以P_r为原点构建平行于画板坐标系的笛卡尔坐标系O。然后，定义O中各象限内的信息丢失值S为在Q_r内但不在Q_p内的像素的重要度值的平均值。S_tl，S_tr，S_br和S_b1分别表示左上，右上，右下和左下四个象限内的信息丢失值。一个启发式的移动方向向量v由以下公式确定：Finally, determine the image coordinates and zoom scale. Q_r and Q_p represent the polygon of the ROI area of the picture and the display space of the display board corresponding to the picture, respectively. First, the center of gravity P_r of Q_r is placed at the center of Q_p , and the orientation angle θ has been determined before. The zoom scale when the picture just completely covers the display space is the initial value of the zoom scale. Construct a Cartesian coordinate system O parallel to the drawing board coordinate system with P_r as the origin. Then, define the information loss value S in each quadrant in O as the average value of the importance values of the pixels in_Qr but not in_Qp . S_tl , S_tr , S_br and S_b1 represent the information loss values in the upper left, upper right, lower right and lower left quadrants, respectively. A heuristic moving direction vector v is determined by the following formula:

v＝((S_tl+S_b1)-(S_tr+S_br)，(S_tl+S_tr)-(S_bl+S_br)) （15）；v=((S_tl +S_b1 )-(S_tr +S_br ), (S_tl +S_tr )-(S_bl +S_br )) (15);

将v归一化为单位向量

即为图片下一步在展示面板上的移动方向。的最大移动以P_r为中心构造高斯分布：normalize v to a unit vector

It is the moving direction of the picture on the display panel in the next step. The maximum movement of constructs a Gaussian distribution centered on_Pr :

$N N ((Pr PR + + \frac{r r}{22} \cdot \cdot \overset{^^}{v v},, r r)) - - - - - - ((1616));;$

其中r为每次图片的最大移动距离。据此分布取10个候选位置，并将图片移动到信息丢失值S最少的候选位置。在此新的位置上，将按照确定缩放尺度初始值的方法确定新的缩放尺度。Where r is the maximum moving distance of each picture. According to this distribution, take 10 candidate positions, and move the picture to the candidate position with the least information loss value S. At this new position, the new zoom scale will be determined in the same way as the initial value of the zoom scale.

以上搜索移动缩放步骤迭代进行若干次，当收敛或超过某一预定最大迭代次数限制（本方法设置为30次）后，停止迭代，此时信息损失值最小，图片坐标和缩放尺度确定完成。搜索算法保证了图片能够在有限的分配所得子区域上展示其主要信息。The above search, move and zoom steps are iterated several times, and when the convergence or exceeds a predetermined maximum number of iterations (this method is set to 30 times), the iteration is stopped. At this time, the information loss value is the smallest, and the image coordinates and zoom scale are determined. The search algorithm ensures that the image can display its main information on the limited allocated sub-areas.

步骤4具体包括以下步骤：Step 4 specifically includes the following steps:

对展示面板上的每一个像素点，均关联一组概率{Prob₁(p)，Prob₂(p)，…，Prob_n(p)}，其中n为图片总数，Prob_i(p)表示第i幅图片在该像素点处对应像素能够显示的概率。Q_pi和Q_ri分别第i幅图片对应的展示面板展示空间和其ROI区域。混合可以使得Q_ri中不在Q_pi中的部分也能得到一定程度上的展现，Prob_i(p)计算公式如下：For each pixel on the display panel, a set of probabilities {Prob₁ (p), Prob₂ (p), ..., Prob_n (p)} are associated, where n is the total number of pictures, and Prob_i (p) represents the The probability that the corresponding pixel of the i picture at the pixel point can be displayed. Q_pi and Q_ri are the display panel display space and its ROI area corresponding to the i-th picture, respectively. Mixing can make the parts of Q_ri that are not in Q_pi also be displayed to a certain extent. The calculation formula of_Probi (p) is as follows:

${Prob Prob}_{i i} ((p p)) = = \{\begin{matrix} 11 & p p &Element; &Element; {Q Q}_{pi p},, p p &Element; &Element; {Q Q}_{ri the ri} \\ {e e}^{\frac{- - d d ((p p,, {Q Q}_{ri the ri}))}{22 σ σ}} & p p &Element; &Element; {Q Q}_{pi p},, p p &NotElement; &NotElement; {Q Q}_{ri the ri} \\ {e e}^{\frac{- - d d ((p p,, {Q Q}_{pi p}))}{22 σ σ}} & p p &NotElement; &NotElement; {Q Q}_{pi p},, p p &Element; &Element; {Q Q}_{ri the ri} \\ 00 & p p &NotElement; &NotElement; {Q Q}_{pi p},, p p &NotElement; &NotElement; {Q Q}_{ri the ri} \end{matrix} - - - - - - ((1717));;$

其中，e为自然对数的底，值为2.71828……，d(p，Q_pi)表示点p到显示空间，Q_pi的最近欧式距离，d(p，Q_ri)表示点p到ROI区域Q_ri的最近欧式距离，σ为贡献率概率概率分布的标准差，计算得σ≈0.39894223。Among them, e is the base of natural logarithm, the value is 2.71828..., d(p, Q_pi ) indicates the closest Euclidean distance from point p to display space, Q_pi , d(p, Q_ri ) indicates point p to ROI area The nearest Euclidean distance of Q_ri , σ is the standard deviation of the probability distribution of the contribution rate, calculated as σ≈0.39894223.

展示面板每个像素点的关联概率用以上规则计算得到后，再平均的分发到其4邻域上，以使得邻近的像素具有接近的概率值再将每个像素的一组关联概率归一化，其后得到的概率图即作为混合操作的Alpha通道值用于最终拼贴图片的合成。After the association probability of each pixel of the display panel is calculated by the above rules, it is evenly distributed to its 4 neighbors, so that adjacent pixels have close probability values, and then a set of association probabilities of each pixel is normalized , the resulting probability map is used as the alpha channel value of the blending operation for the synthesis of the final collage image.

有益效果：本发明包括以下优点：Beneficial effect: the present invention comprises the following advantages:

(1)更灵活的显示区域支持。支持任意边界形状的拼贴结果，同时支持在拼贴结果上进行子图片的放缩、旋转和两两交换位置等个性化定制操作。(1) More flexible display area support. It supports collage results with arbitrary boundary shapes, and supports personalized customization operations such as scaling, rotating and exchanging positions of sub-pictures on the collage results.

(2)更高的可扩展性同时兼备低耦合性。这一特性得益于以下三个方面：首先，本文采用的子区域划分算法高效鲁棒，能够在平均1秒内处理30张以上图片的子区域划分。其次，每张图片的状态参数——位置、朝向角、缩放尺度和层次的优化互相关性弱，每个参数均可在一个独立的阶段优化求解。最后，每张图片的状态参数优化均于邻近图片的状态解耦合，从而可并行地进行。(2) Higher scalability and low coupling at the same time. This feature benefits from the following three aspects: First, the sub-region division algorithm used in this paper is efficient and robust, and can process sub-region division of more than 30 images within 1 second on average. Second, the state parameters of each image—position, orientation angle, zoom scale, and level—are weakly correlated with optimization, and each parameter can be optimally solved in an independent stage. Finally, the optimization of state parameters for each picture is decoupled from the states of neighboring pictures, so that it can be performed in parallel.

(3)较快的处理速度和更高的鲁棒性。得益于(2)中的低耦合性以及区域划分算法的高效性，本方法的速度不慢于已有方法的最快速度，快于大部分已有方法。同时，相比于微软的AutoCollage，本方法可以做任意数量的图片集拼接，而AutoCollage要求图片集的图片数量最少为7张图片。(3) Faster processing speed and higher robustness. Thanks to the low coupling in (2) and the high efficiency of the region division algorithm, the speed of this method is not slower than the fastest speed of the existing methods, and is faster than most of the existing methods. At the same time, compared with Microsoft's AutoCollage, this method can stitch any number of picture sets, and AutoCollage requires a minimum of 7 pictures in the picture set.

(4)更能满足人们对人物照片的客观需求。对于有人的图片，本发明会通过人脸检测设置显示人脸为最高优先级，从而有效的避免了人脸被其他照片的显示区域遮挡的情况，这也很大程度上避免了微软的AutoCollage中出现的人脸显示不全的情况；对于风景、物体、动物等无人的图片，本发明可以以较大的概率保证前景部分能得到显示，而前景部分很大程度会是照片内容的主要区域，从而获得很好的显示结果。(4) It can better meet people's objective needs for photos of people. For pictures with people, the present invention will display the human face as the highest priority through face detection, thereby effectively avoiding the situation that the human face is blocked by the display area of other photos, which also largely avoids Incomplete display of human faces occurs; for pictures without people such as landscapes, objects, animals, etc., the present invention can ensure that the foreground part can be displayed with a higher probability, and the foreground part will be the main area of the photo content to a large extent. Thus, a good display result can be obtained.

(5)更好的显示效果。本发明在图片排放的过程中，图片的朝向通过在一定角度范围内的随机选择朝向，因此最终的显示结果较现有的方法更加自然，同时角度范围的合理设定可以避免整个结果给人以杂乱的感觉。(5) Better display effect. In the process of displaying pictures in the present invention, the orientation of the pictures is randomly selected within a certain angle range, so the final display result is more natural than the existing method, and at the same time, the reasonable setting of the angle range can avoid the whole result giving people a false impression. messy feeling.

附图说明Description of drawings

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述或其他方面的优点将会变得更加清楚。The present invention will be further described below in conjunction with the accompanying drawings and specific embodiments, and the advantages of the above and other aspects of the present invention will become clearer.

图1为本发明方法的流程图。Fig. 1 is the flowchart of the method of the present invention.

图2为本发明中圆填充（Circle Packing）算法在一个矩形区域内划分5个区域的过程。Fig. 2 is the process of dividing five areas in a rectangular area by the Circle Packing algorithm in the present invention.

图3为本发明中显示区域优化的工作流程示意图。Fig. 3 is a schematic diagram of the workflow of display area optimization in the present invention.

图4为本发明方法实施的实例流程图。Fig. 4 is an example flowchart of the implementation of the method of the present invention.

图5用户调查的反馈结果图。Fig. 5 Feedback result map of user survey.

图6为动物图片集的实施例最终生成结果。Fig. 6 is the final generation result of the embodiment of the animal picture set.

图7为动画海报图片集的实施例最终生成结果。Fig. 7 is the final generation result of the embodiment of the animation poster picture set.

图8为小孩图片集的实施例最终生成结果。Fig. 8 is the final generation result of the embodiment of the children's picture set.

图9为花卉图片集的实施例最终生成结果。Fig. 9 is the final generation result of the embodiment of the flower picture set.

图10为菱形展示面板的实施例最终生成结果。Fig. 10 is the final generated result of the embodiment of the rhombus display panel.

图11为椭圆形展示面板的实施例最终生成结果。Fig. 11 is the final generated result of the embodiment of the elliptical display panel.

图12a为足球运动员图片集的AutoCollage最终生成结果。Figure 12a is the final AutoCollage generated result of the football player picture set.

图12b为足球运动员图片集的本实施例最终生成结果。Fig. 12b is the final generation result of this embodiment of the football player picture set.

图13a为玩偶图片集的AutoCollage最终生成结果。Figure 13a is the final AutoCollage generated result of the doll picture set.

图13b为玩偶图片集的本实施例最终生成结果。Fig. 13b is the final generation result of this embodiment of the doll picture set.

具体实施方式：Detailed ways:

本方法的流程如图1所示首先评估各幅图片的重要程度，然后将次重要度值映射为圆填充算法的输入参数——圆的初始半径值；然后根据圆填充算法得到区域的划分结果，图2中展示了一个已知初始半径比例的5个圆，逐步增大圆的缩放因子，在经过多次计算后获得一个缩放因子的最大值k，然后根据圆的外切多边形来获得展示面板的区域划分；使用一种启发式的搜索算法迭代进行搜索优化各幅图片在所分配到的显示空间内的显示参数，图3展示了一次搜索优化过程；最后是同无缝混合技术处理图片间的重叠算法，最终获得图片集拼贴展示结果。图4展示了一个拥有5幅图片的图片集进行剪切拼接的具体流程及每部操作完成后的子结果。The flow of this method is shown in Figure 1. First, evaluate the importance of each picture, and then map the secondary importance value to the input parameter of the circle filling algorithm - the initial radius value of the circle; then obtain the division result of the area according to the circle filling algorithm , Figure 2 shows 5 circles with a known initial radius ratio, gradually increase the scaling factor of the circle, obtain a maximum value k of the scaling factor after multiple calculations, and then obtain the display panel according to the circumscribed polygon of the circle area division; use a heuristic search algorithm to iteratively search and optimize the display parameters of each picture in the allocated display space, Figure 3 shows a search optimization process; finally process the image space with the seamless blending technology The overlapping algorithm finally obtains the collage display result of the picture collection. Figure 4 shows the specific process of cutting and splicing a picture set with 5 pictures and the sub-results after each operation is completed.

具体地说，如图1所示，本发明公开了一种计算机中图像剪切拼接方法：Specifically, as shown in Figure 1, the present invention discloses a method for cutting and splicing images in a computer:

步骤1，重要度评估：衡量图片集中每幅图片的颜色特征，通过统计图片中颜色的多样性获得每幅图片的颜色复杂度S_C；采用土方移动距离方法计算图片集中各个图片之间的EMD距离，将每幅图片与其他图片的EMD距离最小值作为该图片与图片集中其他图片的相似度S_D，将S_C和S_D的加权和作为该图片的重要度S_I；Step 1, importance evaluation: measure the color characteristics of each picture in the picture set, and obtain the color complexity S_C of each picture by counting the diversity of colors in the picture; use the earthwork moving distance method to calculate the EMD between pictures in the picture set Distance, the minimum value of the EMD distance between each picture and other pictures is taken as the similarity S_D between the picture and other pictures in the picture set, and the weighted sum of S_C and S_D is taken as the importance S_I of the picture;

步骤2，展示面板子区域划分得到每幅图片的显示空间：选取与图片集中图片数量相同的一组圆，其中各个圆的初始半径之间的比例与所述每幅图片的重要度之间的比例相同，通过圆填充方法填充展示面板，填充完成后由圆的外切多边形划分得到展示面板子区域，从而确定每幅图片在展示面板上的显示空间Q_p；Step 2: Divide the sub-regions of the display panel to obtain the display space of each picture: select a group of circles with the same number of pictures in the picture collection, and the ratio between the initial radii of the circles and the importance of each picture The ratio is the same, the display panel is filled by the circle filling method, and the sub-area of the display panel is obtained by dividing the circumscribed polygon of the circle after filling, so as to determine the display space Q_p of each picture on the display panel;

步骤3，显示参数优化：确定每幅图片的朝向角θ，摆放位置、缩放尺度；计算每个图片的重要度图，将含有人脸图像的图片中人脸图像区域内每个像素的重要度值置为最大值；将每个图片中高于预设重要度阈值的像素组成连通区域，按照连通区域面积由大至小排序后，将面积排序前1/3的连通区域划分至一个多边形区域内，该多边形区域即是该图片的ROI区域Q_r；Step 3, display parameter optimization: determine the orientation angle θ of each picture, the placement position, and the zoom scale; calculate the importance map of each picture, and calculate the importance of each pixel in the face image area in the picture containing the face image The degree value is set to the maximum value; the pixels higher than the preset importance threshold in each picture form a connected area, and after sorting the area of the connected area from large to small, divide the top 1/3 of the connected area into a polygonal area Inside, the polygonal area is the ROI area Q_r of the picture;

步骤1中，通过图片的复杂度和与其他图片的相似度来评判图片的重要性。Instep 1, the importance of a picture is judged by its complexity and similarity with other pictures.

步骤1具体包括以下步骤：Step 1 specifically includes the following steps:

步骤11，使用HSV颜色空间上的直方图统计信息定义颜色的复杂度，H通道上的颜色复杂度

采用如下公式计算：Step 11, use the histogram statistics on the HSV color space to define the complexity of the color, the color complexity on the H channel

Calculated using the following formula:

定义为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度S_C的归一化因子。如果图片的H通道为常量，即H通道的直方图只有一个分区有值，这时

Defined as the frequency of pixels falling in the i-th partition;

is the maximum range of all frequencies, and is used as the normalization factor of the color complexity S_C . If the H channel of the picture is constant, that is, the histogram of the H channel has only one partition with a value, then

defined as

S通道上的复杂度值采用以下公式计算:Complexity value on S channel Calculated using the following formula:

定义为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度

的归一化因子；如果图片的S通道为常量，则

定义为采用如下公式计算：Among them, m^S is the number of partitions of the statistical histogram on the S channel, which is set to 16 in this experiment;

Defined as the frequency of pixels falling in the i-th partition;

is the largest range of all frequencies, as color complexity

The normalization factor of ; if the S channel of the picture is constant, then

Defined as calculated using the following formula:

V通道上的复杂度值

采用以下公式计算:Complexity value on the V channel

Calculated using the following formula:

定义为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度

的归一化因子；如果图片的V通道为常量，则定义为采用如下公式计算：Among them, m^V is the number of partitions of the statistical histogram on the V channel, which is set to 16 in this experiment;

Defined as the frequency of pixels falling in the i-th partition;

is the largest range of all frequencies, as color complexity

The normalization factor of ; if the V channel of the picture is constant, then Defined as calculated using the following formula:

最后的颜色复杂度即为：The final color complexity is:

步骤12，EMD距离用两幅图片在一特征下的统计直方图的对齐代价作为衡量图片相似程度，EMD距离采用以下公式计算：Step 12, the EMD distance uses the alignment cost of the statistical histograms of two pictures under a feature as a measure of the similarity of the pictures, and the EMD distance is calculated using the following formula:

H_I＝{h_i，i＝1，…，24}，H_I，＝{h′_j,j＝1，…，24} (8)。H_I ={h_i , i=1,...,24}, H_I ,={h'_j ,j=1,...,24} (8).

$EMD EMD (({H h}_{I I},, {H h}_{{I I}^{' '}})) = = \frac{{Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij} {d d}_{ij ij}}{{Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij}} - - - - - - ((99)) . .$

公式(8)中H_I和H_I，分别为图片I和图片I′对应的HSV颜色空间直方图特征向量，其中H通道分成16个子块，S通道和V通道都划分成4个子块，三个通道共同组成一个24维的颜色特征向量H_I和H_I′，其中h_i和h′_j代表表示子通道中划分的子块，i为子块h_i的维度标号和j为子块h′_j中的维度标号；公式(9)计算获得图片I和图片I′的EMD距离，其中f_ij表示h_i和h′_j两子块之间的流，d_ij表示h_i和h′_j两子块之间的L1距离。H_I and H_I in formula (8) are the HSV color space histogram feature vectors corresponding to picture I and picture I′ respectively, where H channel is divided into 16 sub-blocks, S channel and V channel are divided into 4 sub-blocks, three channels together form a 24-dimensional color feature vector H_I and H_I ′, where h_i and h′_j represent the sub-blocks divided in the sub-channel, i is the dimension label of the sub-block h_i and j is the sub-block h ′ is the dimension label in_j ; formula (9) calculates the EMD distance between picture I and picture I′, where f_ij represents the flow between h_i and h′_j sub-blocks, d_ij represents h_i and h′_j The L1 distance between two subblocks.

根据得到两两图片间EMD距离，从中选取最小值作为一图片与图片集中其他图片之间的相似度S_D；According to the EMD distance obtained between two pictures, select the minimum value as the similarity S_D between a picture and other pictures in the picture collection;

步骤13，最后图片的重要度定义为：Step 13, the importance of the final picture is defined as:

S_I＝S_C+ωS_D (10)S_I =S_C +ωS_D (10)

ω相似度S_D用于控制两者之间的影响权重，ω取值0.3。The ω similarity S_D is used to control the influence weight between the two, and the value of ω is 0.3.

步骤2中，利用步骤1中获得的每幅图片的重要度信息确定一系列初始半径与重要度信息相关联的圆，然后通过圆填充算法实现显示区域划分。具体包括以下步骤：In step 2, the importance information of each picture obtained instep 1 is used to determine a series of circles whose initial radii are associated with the importance information, and then the display area is divided by a circle filling algorithm. Specifically include the following steps:

步骤21，设定圆心的初始位置。对于给定的展示面板Ω和共有n幅图片的图片集，将展示面板中心置于一个二维右手坐标系（坐标系拥有X和Y两条坐标轴）的原点位置，然后在展示面板所在的坐标系范围内随机生成n个点作为圆心的初始位置，将圆心按照其X坐标的值由小到大进行排序，对于X坐标值相同的情况，Y坐标值小的圆心在前，由小到大对每个圆心分配一个编号i，i的取值范围为1～n的整数，圆心i对应圆C_i，圆的初始半径用R_i表示。Step 21, setting the initial position of the center of the circle. For a given display panel Ω and a picture set with a total of n pictures, place the center of the display panel at the origin of a two-dimensional right-handed coordinate system (the coordinate system has two coordinate axes, X and Y), and then place the display panel where Randomly generate n points within the scope of the coordinate system as the initial position of the center of the circle, and sort the centers according to their X coordinate values from small to large. Assign a number i to each center of the circle, the value of i is an integer ranging from 1 to n, the center i corresponds to the circle C_i , and the initial radius of the circle is represented by R_i .

步骤22，设定圆的初始半径。将图片集内的图片分别与一个标号的圆所对应，其对应的复杂度为

如图4所示，图片1与C₁对应，图片2与C₂对应，图片3与C₃对应，图片4与C₄对应，图片5与C₅对应；比较步骤11中圆心两两之间的距离后获得距离最近的两个圆心之间的距离D_min，则圆的初始半径R_i计算公式如下：Step 22, set the initial radius of the circle. Correspond the pictures in the picture set to a labeled circle respectively, and the corresponding complexity is

As shown in Figure 4,picture 1 corresponds to C₁ , picture 2 corresponds to C₂ , picture 3 corresponds to C 3,picture 4 corresponds to C₄ , and picture₅ corresponds to C₅ ; in step 11, the center of the circle is compared After obtaining the distance D_min between the two nearest centers, the calculation formula of the initial radius R_i of the circle is as follows:

其中

为标号为1的图片的复杂度，

为标号为i的图片的复杂度；如图4中“半径与对应图片重要度相关的圆”标识的子区域所示：经过计算后获得图片1对应圆的半径初始值为0.762，图片2对应圆的半径初始值为0.801，图片3对应圆的半径初始值为0.823，图片4对应圆的半径初始值为0.824，图片5对应圆的半径初始值为0.713；in

is the complexity of the picture labeled 1,

is the complexity of the picture labeled i; as shown in the sub-region identified by the "circle whose radius is related to the importance of the corresponding picture" in Figure 4: after calculation, the initial value of the radius of the circle corresponding topicture 1 is 0.762, and the initial value of the circle corresponding to picture 2 is 0.762, and The initial value of the radius of the circle is 0.801, the initial value of the radius of the circle corresponding to picture 3 is 0.823, the initial value of the radius of the circle corresponding topicture 4 is 0.824, and the initial value of the radius of the circle corresponding topicture 5 is 0.713;

步骤23，圆填充方法对展示面板区域进行圆填充。如图2所示获得圆的初始圆心位置和初始半径后，在保证圆与圆之间不相交并且所有圆在展示面板的区域内的前提下，对所有圆进行同比例放大，放大完成后，动态调整圆心位置，重复执行放大调整过程，直至无法继续放大时，停止该过程，获得在展示面板区域内圆的紧致排列，此时对应的圆统一缩放因子k＝186.625，圆C₁~圆C₅的最终位置如图2所示。Step 23, the circle filling method performs circle filling on the display panel area. After obtaining the initial center position and initial radius of the circle as shown in Figure 2, under the premise of ensuring that the circles do not intersect each other and that all circles are within the area of the display panel, all circles are enlarged in the same proportion. After the enlargement is completed, Dynamically adjust the position of the center of the circle, and repeat the zoom-in adjustment process until the zoom-in is no longer possible, stop the process and obtain a compact arrangement of circles in the display panel area. At this time, the corresponding circle uniform scaling factor k=186.625, circle C₁ ~ circle The final position of C₅ is shown in Figure 2.

步骤24，展示面板的子区域划分，得到每幅图片的显示空间。根据步骤23获得的显示区域内圆的紧致排列结果，一个圆与其邻接圆之间的公切线可以构成该圆的外切多边形，针对圆与邻接圆之间不相切的情况，本方法选取与两个圆连线相垂直平分线来参与多边形的构成。所获得的多边形构成了展示面板的子区域划分，如图2中虚线划分所示，其中包含圆C_i的多边形Q_p即是与其相关联的图片所对应的显示空间。Step 24, divide the sub-regions of the display panel to obtain the display space of each picture. According to the result of compact arrangement of circles in the display area obtained instep 23, the common tangent between a circle and its adjacent circles can form the circumscribed polygon of the circle. For the non-tangent situation between the circle and the adjacent circles, this method selects The perpendicular bisector of the line connecting two circles participates in the formation of polygons. The obtained polygons constitute the sub-area division of the display panel, as shown by the dotted line division in FIG. 2 , wherein the polygon_Qp containing the circle C_i is the display space corresponding to the picture associated with it.

步骤3中，如图3所示确定图片朝向角、坐标和缩放尺度等显示参数，使每幅图片能在其对应的展示面板有限大小的显示区域内最大化的呈现其重要内容。In step 3, as shown in Figure 3, determine the display parameters such as the orientation angle, coordinates, and zoom scale of the picture, so that each picture can maximize its important content within the limited display area of its corresponding display panel.

如图3所示，步骤3具体包括以下步骤：As shown in Figure 3, step 3 specifically includes the following steps:

步骤31，设定图片朝向角。本方法赋予每幅图片一个随机的朝向角θ，θ满足[-θ_m,θ_m]范围内的平均分布，其中θ_m为最大允许偏转角，本方法设置θ_m为30°，如图3所示，图3中“设定图片朝向”一步中设定图片的朝向角θ设置为30°。Step 31, setting the orientation angle of the picture. This method gives each picture a random orientation angle θ, θ satisfies the average distribution within the range of [-θ_m ,θ_m ], where θ_m is the maximum allowable deflection angle, and this method sets θ_m to 30°, as shown in Figure 3 As shown in Figure 3, set the orientation angle θ of the image to 30° in the step of "Setting the orientation of the image".

首先，获得图片重要度图。如图4中“图片重要度计算”一步所示，通过程明明等提出的方法计算图片的重要度图，获得的图片对应重要度图如图4中“重要度图”子区域所示，然后使用OpenCV中的人脸检测算法检测人脸区域，将该区域内重要度图的重要度值置为最大。First, obtain the image importance map. As shown in the "image importance calculation" step in Figure 4, the importance map of the picture is calculated by the method proposed by Cheng Mingming et al. Use the face detection algorithm in OpenCV to detect the face area, and set the importance value of the importance map in the area to the maximum.

然后，获得图片ROI区域。对获得的重要度图基于阈值0.618进行二值化处理，然后经过侵蚀与扩张操作获得若干个连通区域，按照连通区域面积由大至小排序后，如图4中“计算ROI区域近似多边形”所示，通过Sklansky，J.提出的最小凸包算法用一个凸多边形包围面积排序前三分之一的单连通区域，所得多边形Q_r即为图片ROI区域，多边形如图4中“ROI区域”子区域内所示。Then, the image ROI area is obtained. Binarize the obtained importance map based on the threshold value of 0.618, and then obtain several connected regions through erosion and expansion operations, and sort them according to the area of the connected regions from large to small, as shown in "Calculation of ROI region approximation polygon" in Figure 4 As shown, through the minimum convex hull algorithm proposed by Sklansky, J., a convex polygon is used to enclose the first third of the singly connected regions in the sorted area, and the obtained polygon Q_r is the image ROI region. The polygon is shown in the "ROI region" subsection in Figure 4 shown in the area.

最后，确定图片坐标和缩放尺度。如图3所示Q_r和Q_p分别表示图片ROI区域多边形和图片所对应的展示画板显示空间。首先，将Q_r的重心P_r于Q_p的中心位置，朝向角θ之前已经确定，该图片恰好完全覆盖展示空间时的缩放尺度即为缩放尺度的初始值。以P_r为原点构建平行于画板坐标系的笛卡尔坐标系O。然后，定义O中各象限内的信息丢失值S为在Q_r内但不在Q_p内的像素的重要度值的平均值。S_tl，S_tr，S_br和S_b1分别表示左上，右上，右下和左下四个象限内的信息丢失值。一个启发式的移动方向向量v由以下公式确定：Finally, determine the image coordinates and zoom scale. As shown in FIG. 3 , Q_r and Q_p represent the polygon of the ROI region of the picture and the display space of the display board corresponding to the picture, respectively. First, the center of gravity P_r of Q_r is placed at the center of Q_p , and the orientation angle θ has been determined before. The zoom scale when the picture just completely covers the display space is the initial value of the zoom scale. Construct a Cartesian coordinate system O parallel to the drawing board coordinate system with P_r as the origin. Then, define the information loss value S in each quadrant in O as the average value of the importance values of the pixels in_Qr but not in_Qp . S_tl , S_tr , S_br and S_b1 represent the information loss values in the upper left, upper right, lower right and lower left quadrants, respectively. A heuristic moving direction vector v is determined by the following formula:

v＝((S_tl+S_b1)-(S_tr+S_br)，(S_tl+S_tr)-(S_bl+S_br)) （12）；v=((S_tl +S_b1 )-(S_tr +S_br ), (S_tl +S_tr )-(S_bl +S_br )) (12);

将v归一化为单位向量

即为图片下一步在展示面板上的移动方向。以P_r为中心构造高斯分布：normalize v to a unit vector

It is the moving direction of the picture on the display panel in the next step. Construct a Gaussian distribution centered on P_r :

$N N ((Pr PR + + \frac{r r}{22} \cdot &Center Dot; \overset{^^}{v v},, r r)) - - - - - - ((1313));;$

以上搜索移动缩放步骤迭代进行若干次，当收敛或超过某一预定最大迭代次数限制（本方法设置为30次）后，停止迭代，图片坐标和缩放尺度确定完成。The above steps of searching, moving and zooming are iterated several times, and when convergence or exceeding a predetermined maximum number of iterations (this method is set to 30 times), the iteration is stopped, and the image coordinates and zoom scale are determined.

步骤4中，如图4“基于重要度图信息的无缝混合渲染”一步所示，将图片的重要度信息结合进入混合过程，得到最终剪切拼接结果。InStep 4, as shown in Figure 4 "Seamless Blending and Rendering Based on Importance Map Information", the importance information of the picture is combined into the blending process to obtain the final cutting and stitching result.

${Prob Prob}_{i i} ((p p)) = = \{\begin{matrix} 11 & p p &Element; &Element; {Q Q}_{pi p},, p p &Element; &Element; {Q Q}_{ri the ri} \\ {e e}^{\frac{- - d d ((p p,, {Q Q}_{ri the ri}))}{22 σ σ}} & p p &Element; &Element; {Q Q}_{pi p},, p p &NotElement; &NotElement; {Q Q}_{ri the ri} \\ {e e}^{\frac{- - d d ((p p,, {Q Q}_{pi p}))}{22 σ σ}} & p p &NotElement; &NotElement; {Q Q}_{pi p},, p p &Element; &Element; {Q Q}_{ri the ri} \\ 00 & p p &NotElement; &NotElement; {Q Q}_{pi p},, p p &NotElement; &NotElement; {Q Q}_{ri the ri} \end{matrix} - - - - - - ((1414)) . .$

实施例Example

本实施例用于测试的硬件环境是：Intel-Core2Duo4.2GHz处理器，4G内存。软件环境是

Visual Studio2010和

Windows7专业版。测试图像来自于组内活动照片、网络上公开的动画电影海报以及其他的一些动物和花卉等照片。实验时根据大分类分成9组，分别是动物、玩偶、足球运动员、酒杯、动画海报、猫狗、小孩、花卉、灰衣女生。The hardware environment used for testing in this embodiment is: Intel-Core2Duo4.2GHz processor, 4G memory. The software environment is

Visual Studio 2010 and

Windows7 Professional Edition. The test images come from photos of activities in the group, animated movie posters published on the Internet, and other photos of animals and flowers. During the experiment, they were divided into 9 groups according to the major categories, namely animals, dolls, football players, wine glasses, animated posters, cats and dogs, children, flowers, and girls in gray clothes.

本实施例根据输入图片集的图片数量的不同，拼贴的时间消耗在几秒到几十秒不等，主要的计算时间消耗在人脸检测和重要度图计算部分。同时还将本方法的实验结果与Photo Gallery套件中的“自动拼贴”功能（AutoCollage）获得的结果进行了用户调查。124位计算机系的同学参与了双盲的用户调查，在没有其他外界干预的前提下靠自己的判断来选择更符合自己审美的结果。图5显示了用户调查的反馈结果，调查结果已经进行了归一化处理，用百分比来展示用户的偏好，左侧黑色柱体表示选择本实施例生成结果的用户占总人数的百分比，右侧白色柱体表示选择AutoCollage生成结果的用户占总人数的百分比。具体参见，动物（图6本实施例动物图片集的实施例最终生成结果示意图）、玩偶（图13a为玩偶图片集的AutoCollage最终生成结果示意图，图13b为玩偶图片集的本实施例最终生成结果示意图）、足球运动员（图12a为足球运动员图片集的AutoCollage最终生成结果示意图，图12b为足球运动员图片集的本实施例最终生成结果示意图）、酒杯、动画海报（图7本实施例动画海报图片集的实施例最终生成结果示意图、猫狗、小孩（图8为小孩图片集的实施例最终生成结果示意图）、花卉（图9为花卉图片集的实施例最终生成结果示意图）、灰衣女生；对应的结果比依次为：61.3%：38.7%，66.1%：33.9%，80.8%：19.2%，69.6%：30.4%，77.8%：22.2%，59.5%：40.5%，69.8%：30.2%，75.4%：24.6%，58.0%：42.0%。In this embodiment, depending on the number of pictures in the input picture set, the collage time consumption ranges from several seconds to tens of seconds, and the main calculation time is consumed in face detection and importance map calculation. At the same time, the experimental results of this method and the A user survey was conducted on the results obtained by the "Auto Collage" function (AutoCollage) in the Photo Gallery suite. 124 students from the Department of Computer Science participated in the double-blind user survey, relying on their own judgment to choose the result that is more in line with their own aesthetics without other external intervention. Figure 5 shows the feedback results of the user survey. The survey results have been normalized, and the user preferences are displayed in percentages. The black column on the left indicates the percentage of the total number of users who choose the results generated by this embodiment, and the right The white column indicates the percentage of users who choose AutoCollage to generate results. For details, see, animals (Figure 6 is a schematic diagram of the final generation result of the animal picture collection in this embodiment), dolls (Figure 13a is a schematic diagram of the final generation result of AutoCollage for the doll picture collection, and Figure 13b is the final generation result of the doll picture collection in this embodiment Schematic diagram), football player (Figure 12a is a schematic diagram of the final AutoCollage generated result of the football player picture collection, and Figure 12b is a schematic diagram of the final generated result of the football player picture collection in this embodiment), wine glasses, animated posters (Figure 7 is the animation poster picture of this embodiment Schematic diagram of the final generation result of the embodiment of the set, cats and dogs, children (Figure 8 is a schematic diagram of the final generation result of the embodiment of the child picture collection), flowers (Figure 9 is a schematic diagram of the final generation result of the embodiment of the flower picture collection), girls in gray clothes; The corresponding result ratios are: 61.3%: 38.7%, 66.1%: 33.9%, 80.8%: 19.2%, 69.6%: 30.4%, 77.8%: 22.2%, 59.5%: 40.5%, 69.8%: 30.2%, 75.4 %: 24.6%, 58.0%: 42.0%.

图5为用户调查结果用户调查结果显示，所有9组结果对于AutoCollage生成的结果都有不同程度的优势，第三组足球运动员的结果比较达到了80.8%比19.2%。两种方法最终获得的图片比对如图12a、图12b，以及图13a、图13b所示。用户调查的结果也表明了大部分用户倾向于选择本方法生成的图片集拼接结果。在用户的调查问卷上，还设置有“选择理由”这一条选答项，从回答该问题的用户意见来看，大部分选择本方法的理由都是集中在以下两个：Figure 5 shows the user survey results. The user survey results show that all 9 groups of results have different degrees of advantages over the results generated by AutoCollage, and the comparison of the results of the third group of football players reached 80.8% vs. 19.2%. The comparison of the pictures finally obtained by the two methods is shown in Fig. 12a, Fig. 12b, and Fig. 13a, Fig. 13b. The results of the user survey also show that most users tend to choose the splicing result of the image collection generated by this method. In the user questionnaire, there is also an optional answer item of "reason for choice". Judging from the opinions of users who answered this question, most of the reasons for choosing this method are concentrated in the following two:

1，本方法生成的图片排列错落有致，相对于AutoCollage生成结果死板的排列更加自然、随意，令人赏心悦目。这一点从图12a和图12b以及图13a和图13b的比较可以看出，AutoCollage的结果排布是每一行的子区域基本在同一条水平线上，而本方法的排布由于圆填充方法进行区域划分获得了更加灵活的区域排布；1. The arrangement of the pictures generated by this method is well arranged, which is more natural, random and pleasing to the eye than the rigid arrangement of the results generated by AutoCollage. This point can be seen from the comparison of Figure 12a and Figure 12b and Figure 13a and Figure 13b. The result of AutoCollage is that the sub-regions of each row are basically on the same horizontal line, and the arrangement of this method is due to the circle filling method. The division has obtained a more flexible area arrangement;

2，本方法生成的图片中人脸或者物体遮挡的情况均好于AutoCollage的生成结果。人脸的遮挡对比可以在图12a和图12b的例子中得以体现；2. The occlusion of faces or objects in the pictures generated by this method is better than that of AutoCollage. The occlusion comparison of human faces can be reflected in the examples in Figure 12a and Figure 12b;

图10和图11为在给定展示面板形状分别为菱形和椭圆形时，本实施例获得的最终结果，而AutoCollage仅支持三种尺寸下的矩形展示面板。Fig. 10 and Fig. 11 show the final results obtained in this embodiment when the given display panel shapes are rhombus and ellipse respectively, while AutoCollage only supports rectangular display panels in three sizes.

由于用户调查时无法让用户现场感受本方法与AutoCollage的图片集拼贴生成速度，本方法的处理速度优势和其他仅通过最后拼贴结果无法获得的优势也就没办法通过用户调查来获得体现。Since the user survey cannot allow users to experience the collage generation speed of this method and AutoCollage's photo collection on the spot, the processing speed advantage of this method and other advantages that cannot be obtained only through the final collage result cannot be reflected through user surveys.

Claims

Translated fromChinese

1.一种计算机图片集中图片剪切拼接方法，其特征在于，包括以下步骤：1. A method for cutting and splicing pictures in computer picture collection, is characterized in that, comprises the following steps:

步骤1，重要度评估：计算图片集中每幅图片的颜色特征，通过统计图片中颜色的多样性获得每幅图片的颜色复杂度S_C；采用土方移动距离方法计算图片集中各个图片之间的EMD距离，将每幅图片与其他图片的EMD距离最小值作为该图片与图片集中其他图片的相似度S_D，将S_C和S_D的加权和作为该图片的重要度S_I；Step 1, importance evaluation: Calculate the color features of each picture in the picture set, and obtain the color complexity S_C of each picture by counting the diversity of colors in the picture; use the earthwork moving distance method to calculate the EMD between pictures in the picture set Distance, the minimum value of the EMD distance between each picture and other pictures is taken as the similarity S_D between the picture and other pictures in the picture set, and the weighted sum of S_C and S_D is taken as the importance S_I of the picture;

步骤3，显示参数优化：确定每幅图片的朝向角θ，摆放位置、缩放尺度；首先在给定范围内设定每一幅图片的朝向角θ；计算每个图片的重要度图，将含有人脸图像的图片中人脸图像区域内每个像素的重要度值置为最大值；将每个图片中高于预设重要度阈值的像素组成连通区域，按照连通区域面积由大至小排序后，将面积排序前1/3的连通区域划分至一个多边形区域内，该多边形区域即是该图片的ROI区域Q_r；然后根据图片设定的朝向角θ、图片的ROI区域Q_r以及步骤2中确定的图片对应的显示空间Q_p，确定图片摆放位置和缩放尺度；Step 3, display parameter optimization: determine the orientation angle θ of each picture, place it, and scale it; first set the orientation angle θ of each picture within a given range; calculate the importance map of each picture, and set The importance value of each pixel in the face image area in the picture containing the face image is set to the maximum value; the pixels higher than the preset importance threshold in each picture form a connected area, and the area of the connected area is sorted from large to small Finally, the first 1/3 of the connected areas in the area sorting are divided into a polygonal area, and the polygonal area is the ROI area Q_r of the picture; then according to the orientation angle θ set by the picture, the ROI area Q_r of the picture and the steps The display space_Qp corresponding to the picture determined in 2, determine the picture placement position and zoom scale;

2.根据权利要求1所述的一种计算机中图片剪切拼接方法，其特征在于，所述步骤1具体包括以下步骤：2. a kind of picture cutting splicing method in the computer according to claim 1, is characterized in that, described step 1 specifically comprises the following steps:

Calculated using the following formula:

{S S}_{c c}^{H h} = = 11 - - \frac{\sqrt{{Σ Σ}_{i i = = 11}^{{m m}^{H h}} {(({h h}_{i i}^{H h} - - \frac{11}{{m m}^{H h}}))}^{22}}}{{δ δ}_{max max}^{H h}} - - - - - - ((11)),,

其中m^H为H通道上统计直方图的分区数；为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度

的归一化因子；如果图片的H通道为常量，即H通道的直方图只有一个分区有值，则

定义为采用如下公式计算：Where m^H is the number of partitions of the statistical histogram on the H channel; is the frequency of pixels falling in the i-th partition;

is the largest range of all frequencies, as color complexity

The normalization factor of ; if the H channel of the picture is constant, that is, only one partition of the histogram of the H channel has a value, then

Defined as calculated using the following formula:

{δ δ}_{max max}^{H h} = = \sqrt{{((11 - - \frac{11}{{m m}^{H h}}))}^{22} + + \frac{{m m}^{H h} - - 11}{{(({m m}^{H h}))}^{22}}} - - - - - - ((22)),,

S通道上的复杂度值

采用以下公式计算:Complexity value on S channel

Calculated using the following formula:

{S S}_{c c}^{S S} = = 11 - - \frac{\sqrt{{Σ Σ}_{i i = = 11}^{{m m}^{S S}} {(({h h}_{i i}^{S S} - - \frac{11}{{m m}^{S S}}))}^{22}}}{{δ δ}_{max max}^{S S}} - - - - - - ((33)),,

其中m^S为S通道上统计直方图的分区数；

为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度的归一化因子；如果图片的S通道为常量，则定义为采用如下公式计算：Where m^S is the partition number of the statistical histogram on the S channel;

is the frequency of pixels falling in the i-th partition;

{δ δ}_{max max}^{S S} = = \sqrt{{((11 - - \frac{11}{{m m}^{S S}}))}^{22} + + \frac{{m m}^{S S} - - 11}{{(({m m}^{S S}))}^{22}}} - - - - - - ((44)),,

V通道上的复杂度值采用以下公式计算:Complexity value on the V channel Calculated using the following formula:

{S S}_{c c}^{V V} = = 11 - - \frac{\sqrt{{Σ Σ}_{i i = = 11}^{{m m}^{V V}} {(({h h}_{i i}^{V V} - - \frac{11}{{m m}^{V V}}))}^{22}}}{{δ δ}_{max max}^{V V}} - - - - - - ((55)),,

其中m^V为V通道上统计直方图的分区数；

为落在第i个分区内像素频数；

为所有频数的最大范围，作为颜色复杂度的归一化因子；如果图片的V通道为常量，则

定义为采用如下公式计算：Where m^V is the partition number of the statistical histogram on the V channel;

is the frequency of pixels falling in the i-th partition;

is the largest range of all frequencies, as color complexity The normalization factor of ; if the V channel of the picture is constant, then

Defined as calculated using the following formula:

{δ δ}_{max max}^{V V} = = \sqrt{{((11 - - \frac{11}{{m m}^{V V}}))}^{22} + + \frac{{m m}^{V V} - - 11}{{(({m m}^{V V}))}^{22}}} - - - - - - ((66)),,

最终的颜色复杂度为：The final color complexity is:

{S S}_{C C} = = \frac{{S S}_{C C}^{H h} + + {S S}_{C C}^{S S} + + {S S}_{C C}^{V V}}{33} - - - - - - ((77));;

G_I＝{g_i，i＝1，…，24}，G_I，＝{g′_j，j＝1，…，24}(8)，G_I ={g_i , i=1,...,24}, G_I ,={g'_j , j=1,...,24} (8),

EMD EMD (({G G}_{I I},, {G G}_{{I I}^{' '}})) = = \frac{{Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij} {d d}_{ij ij}}{{Σ Σ}_{i i = = 11}^{24 twenty four} {Σ Σ}_{j j = = 11}^{24 twenty four} {f f}_{ij ij}} - - - - - - ((99)),,

公式(8)中G_I和G_I，分别为图片I和图片I′对应的HSV颜色空间直方图特征向量，其中H通道分成16个子块，S通道和V通道都划分成4个子块，三个通道共同组成一个24维的颜色特征向量G_I和G_I′，其中g_i和g′_j代表表示子通道中划分的子块，i为子块g_i的维度标号和j为子块g′_j中的维度标号；公式（9）计算获得图片I和图片I′的EMD距离，其中f_ij表示g_i和g′_j两子块之间的流，d_ij表示g_i和g′_j两子块之间的L1距离；G_I and G_I in formula (8) are the HSV color space histogram feature vectors corresponding to picture I and picture I′ respectively, where the H channel is divided into 16 sub-blocks, the S channel and V channel are divided into 4 sub-blocks, and the three The channels together form a 24-dimensional color feature vector G_I and G_I ′, where g_i and g′_j represent the sub-blocks divided in the sub-channel, i is the dimension label of the sub-block g_i and j is the sub-block g ′ is the dimension label in_j ; formula (9) calculates the EMD distance between picture I and picture I′, where f_ij represents the flow between two sub-blocks g_i and g′_j , and d_ij represents g_i and g′_j L1 distance between two sub-blocks;

根据两两图片间EMD距离，从中选取最小值作为一图片与图片集中其他图片之间的相似度S_D；According to the EMD distance between two pictures, select the minimum value as the similarity S_D between a picture and other pictures in the picture collection;

S_I＝S_C+ωS_D(10)，S_I =S_C +ωS_D (10),

ω相似度S_D用于控制两者之间的影响权重，ω取值范围为0~1之间的实数。The ω similarity S_D is used to control the influence weight between the two, and the value range of ω is a real number between 0 and 1.

3.根据权利要求2所述的一种计算机图片集中图片剪切拼接方法，其特征在于，步骤2中包括以下步骤：3. a kind of picture cutting stitching method in computer picture collection according to claim 2, is characterized in that, comprises the following steps in step 2:

步骤21，设定圆心的初始位置，对于给定的展示面板Ω和包括n幅图片的图片集，将展示面板中心置于一个二维右手坐标系的原点位置，坐标系拥有X、Y两条坐标轴，在展示面板Ω所在的坐标系范围内随机生成n个点作为圆心的初始位置，将圆心按照其X坐标的值由小到大进行排序，对于X坐标值相同的情况，Y坐标值小的圆心在前，由小到大对每个圆心分配一个编号i，i的取值范围为1～n的整数，圆心i对应圆C_i；Step 21. Set the initial position of the center of the circle. For a given display panel Ω and a picture set including n pictures, place the center of the display panel at the origin of a two-dimensional right-handed coordinate system, which has two coordinates X and Y Coordinate axis, randomly generate n points within the range of the coordinate system where the display panel Ω is located as the initial position of the circle center, and sort the circle centers according to their X coordinate values from small to large. For the same X coordinate value, the Y coordinate value The small center of the circle comes first, assign a number i to each circle center from small to large, the value of i is an integer ranging from 1 to n, and the center i corresponds to the circle C_i ;

步骤22，设定圆的初始半径R_i，将图片集内的图片分别与一个标号的圆所对应，图片i对应的复杂度为

比较步骤21中圆心两两之间的距离后获得距离最近的两个圆心之间的距离D_min，则标号为i圆的初始半径R_i计算公式如下：Step 22, set the initial radius R_i of the circle, and associate the pictures in the picture set with a labeled circle respectively, and the complexity corresponding to picture i is

After comparing the distances between the two centers of the circles in step 21, the distance D_min between the two nearest circle centers is obtained, then the calculation formula for the initial radius R_i of the circle labeled i is as follows:

{R R}_{i i} = = \{\begin{matrix} \frac{{D D.}_{min min}}{22},, & i i = = 11;; \\ \frac{{S S}_{I I}^{i i} * * {R R}_{11}}{{S S}_{I I}^{11}},, & 11 < < i i \leq \leq n no;; \end{matrix} - - - - - - ((1111)),,

其中

为标号为1的图片的复杂度，

为标号为i的图片的复杂度，R₁为标号为1的圆的半径；in

is the complexity of the picture labeled 1,

is the complexity of the picture labeled i, R₁ is the radius of the circle labeled 1;

步骤23，采用圆填充方法对展示面板Ω区域进行圆填充，获得圆的初始圆心位置和初始半径后，对所有圆进行同比例放大，约束条件为圆与圆之间不相交并且所有圆在展示面板的区域内，放大完成后，调整圆心位置，重复执行放大调整过程，直至无法继续放大时，停止该过程，获得圆在展示面板Ω区域内的最终位置；Step 23: Use the circle filling method to fill the Ω area of the display panel with a circle. After obtaining the initial center position and initial radius of the circle, scale up all the circles in the same proportion. The constraints are that circles do not intersect each other and all circles are displayed In the area of the panel, after the zoom-in is completed, adjust the position of the center of the circle, and repeat the zoom-in adjustment process until the zoom-in cannot continue, stop the process, and obtain the final position of the circle in the display panel Ω area;

步骤24，划分展示面板Ω的子区域，得到每幅图片的显示空间：根据步骤23获得的圆在展示面板Ω内的最终位置，在任意两个相邻圆之间设置一条两个相邻圆的圆心连线的垂直平分线，所有垂直平分线交错形成的封闭多边形构成了展示面板的子区域，其中包含圆C_i的多边形Q_p即是与其相关联的图片i所对应的显示空间。Step 24, divide the sub-regions of the display panel Ω to obtain the display space of each picture: according to the final position of the circle in the display panel Ω obtained in step 23, set a line between any two adjacent circles The perpendicular bisector of the line connecting the centers of the circles, and the closed polygon formed by interlacing all perpendicular bisectors constitute the sub-area of the display panel, and the polygon_Qp containing the circle C_i is the display space corresponding to the picture i associated with it.

4.根据权利要求3所述的一种计算机图片集中图片剪切拼接方法，其特征在于，步骤3包括以下步骤：4. a kind of computer picture collection picture cutting splicing method according to claim 3, is characterized in that, step 3 comprises the following steps:

步骤31，设定图片朝向角：为每幅图片设置一个随机的朝向角θ，θ取值范围[-θ_m,θ_m]，其中θ_m为最大允许偏转角；Step 31, set the picture orientation angle: set a random orientation angle θ for each picture, the value range of θ is [-θ_m , θ_m ], where θ_m is the maximum allowable deflection angle;

步骤32，确定坐标和缩放尺度：计算每个图片的重要度图，将含有人脸图像的图片中人脸图像区域内每个像素的重要度值置为最大值；将每个图片中高于预设重要度阈值的像素经过扩张和侵蚀操作组成连通区域，按照连通区域面积由大至小排序后，将面积排序前1/3的单连通区域划分至一个凸多边形区域内，该多边形区域即是该图片的ROI区域Q_r；交替地迭代寻找每幅图片最优化的坐标和缩放因子。Step 32, determine the coordinates and zoom scale: calculate the importance map of each picture, set the importance value of each pixel in the face image area in the picture containing the face image to the maximum value; The pixels with the importance threshold are expanded and eroded to form a connected area. After sorting the area of the connected area from large to small, divide the first 1/3 of the single connected area into a convex polygonal area. The polygonal area is The ROI area Q_r of the picture; alternately iteratively find the optimal coordinates and scaling factors of each picture.

5.根据权利要求4所述的一种计算机图片集中图片剪切拼接方法，其特征在于，步骤4中包括如下步骤：5. a kind of picture cutting stitching method in computer picture collection according to claim 4, is characterized in that, comprises the following steps in step 4:

对展示面板上的每一个像素点p，关联一组贡献率{Prob₁(p)，Prob₂(p)，….，Prob_n(p)}，其中n为图片总数，Prob_i(p)表示第i幅图片在该像素点处的贡献率，1≤i≤n；设Q_pi和Q_ri分别第i幅图片对应的显示空间和ROI区域；Prob_i(p)采用如下公式计算：For each pixel point p on the display panel, associate a set of contribution rates {Prob₁ (p), Prob₂ (p), ..., Prob_n (p)}, where n is the total number of pictures, Prob_i (p) Indicates the contribution rate of the i-th picture at the pixel point, 1≤i≤n; let Q_pi and Q_ri be the display space and ROI area corresponding to the i-th picture, respectively; Prob_i (p) is calculated by the following formula:

{Prob Prob}_{i i} ((p p)) = = \{\begin{matrix} 11 & p p &Element; &Element; {Q Q}_{pi p},, p p &Element; &Element; {Q Q}_{ri the ri} \\ {e e}^{\frac{- - d d ((p p,, {Q Q}_{ri the ri}))}{22 σ σ}} & p p &Element; &Element; {Q Q}_{pi p},, p p &NotElement; &NotElement; {Q Q}_{ri the ri} \\ {e e}^{\frac{- - d d ((p p,, {Q Q}_{pi p}))}{22 σ σ}} & p p &NotElement; &NotElement; {Q Q}_{pi p},, p p &Element; &Element; {Q Q}_{ri the ri} \\ 00 & p p &NotElement; &NotElement; {Q Q}_{pi p},, p p &NotElement; &NotElement; {Q Q}_{ri the ri} \end{matrix} - - - - - - ((1212)),,

其中，e为自然对数的底，值为2.71828……，d(p，Q_pi)表示点p到显示空间Q_pi的最近欧式距离，d(p，Q_ri)表示点p到ROI区域Qri的最近欧式距离，σ为贡献率概率概率分布的标准差；Among them, e is the base of natural logarithm, the value is 2.71828..., d(p, Q_pi ) represents the nearest Euclidean distance from point p to display space Q_pi , d(p, Q_ri ) represents point p to ROI area Qri The nearest Euclidean distance of , σ is the standard deviation of the probability distribution of the contribution rate probability;

将每个像素的贡献率Prob_i(p)平均的分发到其4邻域上，再将每个像素的一组贡献率归一化，将得到的概率图即作为无缝混合渲染的Alpha通道值。The contribution rate Prob_i (p) of each pixel is evenly distributed to its 4 neighbors, and then a set of contribution rates of each pixel is normalized, and the obtained probability map is used as an Alpha channel for seamless mixed rendering value.