基于二叉树及分层排序的自动高效照片拼贴方法

摘要

本发明公开了一种基于二叉树及分层排序的自动高效照片拼贴方法，包括以下步骤：步骤一、基于二叉树分割算法对画布进行快速分割；步骤二、输入照片，完成照片与树节点之间的映射，由叶节点至根节点，自下而上层次遍历二叉树的每个内部节点，直至确定每个内部节点的宽高比例；步骤三、对逐层的节点，依据其宽高比例的计算结果进行排序；步骤四、自上而下计算节点所代表画布的尺寸和摆放位置；上述流程，步骤二和步骤三交替进行，步骤二逐层计算内部节点的比例，步骤三每一层的计算结果进行排序，直至完成所有节点的计算。本发明适用于电脑和智能移动平台；可以用于相册拼贴；同时对于同一照片集，可以产生不一样的拼贴结果，最大限度满足不同的需求。

说明书

技术领域

本发明图片处理技术，特别是涉及一种自动高效的照片拼贴方法。

背景技术

近年来，随着智能手机、高清相机等数码产品的不断普及，照片已经成为人们记录 生活的主要载体之一。这种直观的记录，既适合回忆，也适合分享。与此同时，各种照 片分享网站也层出不穷，使得人们可以随时分享照片。然而，大量的照片不但使管理 变得困难，也使分享变得不便。照片拼贴作为一种重要的照片处理手段，旨在将多张 照片拼贴在一张画布中，可以很好的解决大量照片所带来的不便。然而，手动拼贴不但 耗时，而且通常需要一定的专业技能，拼贴结果也不尽如人意。正因如此，自动照片拼 贴技术越来越受到人们的关注。自动拼贴技术在处理速度上更快，而且不需要专业技能。 已经有人提出解决此类问题的算法，但都有一定的不足之处。

例如，目前已经有人提出的二维和三维空间下的照片拼贴算法。文献[1]是微软提出 的一种二维照片拼贴方法AutoCollage：首先根据照片大小对输入照片进行筛选，忽略 较小的照片，然后检测提取每张照片的感兴趣区域(ROI)，对提取的区域进行拼贴和 平滑处理，整个过程比较耗时。文献[2]采用基于Voronoi图的方法对画布进行分割，然 后计算确定每张照片的重要性，再根据重要性的不同调整照片尺寸，同时还要对照片进 行裁剪以适应子区域的形状，处理过程同样非常耗时。文献[3]通过提取照片中的对象， 将其拼贴成一幅具有迷幻色彩的照片。文献[4]和[5]均采用基于二叉树的算法对画布进 行分割，不同之处在于前者在进行拼贴时将照片之间的关系考虑在内，需要进行多次调 整，由此会带来时耗，后者不考虑照片之间的相互关系，在速度上非常快，但拼贴结果 存在容易出现裂缝等不理想的情况。在三维领域中，文献[6]的Connection Constrained 3D  Collage和文献[7]的[Structured Mechanical Collage将照片拼贴为三维模型，可以应用于 游戏开发等领域。

前人提出了一些拼贴方法，但都难以在处理速度和拼贴质量之间取得较好的平衡。 其中基于感兴趣区域提取的方法，由于需要进行感兴趣区域识别，处理过程十分耗时， 且会造成信息丢失；基于内容完全保留的方法处理速度较快，但是拼贴结果不够理想。

参考文献：

[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 circle  packing.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 ofthe 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 ProcessingAssociationAnnual Summit and Conference(APSIPA),2013,pp. 1-10.

[6]Huang Z,Wang J,Lau Rynson WH,Fu HB.Connection constrained 3D collage.In  Proceedings ofComputer 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.

发明内容

为了克服上述现有技术，本发明提出了一种基于二叉树及分层排序的自动高效照片 拼贴方法，能够实现一种兼顾速度和效果的自动照片拼贴算法，算法处理效率高而且对 硬件要求不高，可以在不同的平台上实现，包括智能手机和PC。

本发明提出了一种基于二叉树及分层排序的自动高效照片拼贴方法，该方法包括以 下步骤：

步骤一、基于二叉树分割算法对画布进行快速分割，分割结果是将画布区域产生一 棵完全二叉树，其中树的叶子节点数量与照片数量相等，树的内部节点保存画布分割类 型的属性，分割类型属性包括横向或者纵向两种，并且随机产生；

步骤二、输入照片，完成照片与树节点之间的映射，由叶节点至根节点，自下而上 层次遍历二叉树的每个内部节点，直至确定每个内部节点的宽高比例；

步骤三、对逐层的节点，依据其宽高比例的计算结果进行排序；

步骤四、自上而下计算节点所代表画布的尺寸和摆放位置；

上述流程，步骤二和步骤三交替进行，步骤二逐层计算内部节点的比例，步骤三 每一层的计算结果进行排序，直至完成所有节点的计算。

所述步骤二中每个内部节点的宽高比例的计算，具体包括以下处理：

由子节点计算父节点的宽高比例时，若父节点分割类型为“V”，则左右孩子节 点高度一致；若父节点分割类型为“H”，则左右孩子节点宽度一致，计算公式如下：

父节点分割类型为’V’：Ar_parent＝Ar_left+Ar_right

父节点分割类型为‘H’：1/Ar_parent＝1/Ar_left+1/Ar_right

其中，Ar代表节点所代表区域的宽高比例，Ar_parent表示父节点所代表区域的宽 高比例，Ar_left和Ar_right分别表示父节点左右孩子节点所代表区域的宽高比例；

对叶子节点来说其宽高比例即为其所对应照片的宽高比例，内部节点的宽高比 例根据其左右子节点计算而得。

所述每个内部节点的宽高比例的计算结果需满足预设条件，如果计算结果超出预 设比例范围，则调整父节点的分割类型，重新进行计算。

所述步骤四的计算画布的尺寸，其计算公式如下：

父节点分割类型为‘V’：

node.Height＝node.Parent.Height

node.Width＝node.Height×node.Ar

父节点分割类型为‘H’：

node.Width＝node.Parent.Width

node.Height＝node.Width/node.Ar

式中node.Height和node.Width分别表示当前节点所代表的区域的宽度和高度， node.Parent.Height和node.Parent.Width分别表示当前节点父节点的高度和宽度， node.Ar表示当前节点所代表区域的宽高比例。

所述步骤四的计算画布的摆放位置，其计算公式如下：

节点为左孩子节点

node.Pox＝node.Parent.Pox

node.Poy＝node.Parent.Poy

节点为右孩子节点

父节点分割类型为‘V’

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

node.Poy＝node.Parent.Poy

父节点分割类型为‘H’

node.Pox＝node.Parent.Pox

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

式中node.Pox和node.Poy表示当前节点所代表的区域的左上角的坐标， node.Parent.Pox和node.Parent.Poy代表当前节点父节点所代表区域左上角的横坐标 和纵坐标，node.Parent.Left.Pox代表当前节点的父节点的左孩子节点所代表区域的左 上角的横坐标，node.Parent.Left.Width和node.Parent.Left.Height代表当前节点父节点 的左孩子节点所代表区域的宽度和高度。

所述步骤三中，在排序完成后，调整排序层和其子节点层的对应关系，使其重 新满足映射关系。

与现有技术相比，本发明可以用于相册拼贴、图片检索结果显示、视频摘要拼贴等 领域，通过设置不同的参数，可以产生不一样的结果。同时对于同一照片集，可以产生 不一样的拼贴结果，最大限度满足不同的需求。

附图说明

图1为照片数量为20时的拼贴结果示意图；

图2为照片数量为100时的拼贴结果示意图；

图3为本发明的最佳实施方式流程图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明，但本发明的实施范围并 不局限于此。

最佳实施流程主要有以下几个步骤：快速产生画布分割二叉树、自下而上逐层 计算内部节点的比例、根据结算结果逐层排序、自上而下计算节点的大小及位置。 流程图如图3所示：

步骤1、快速产生画布分割二叉树。

为了对画布进行快速分割，本步骤需要产生一棵完全二叉树，树的叶子节点个 数与待拼贴照片数量相等，树的内部节点存储分割类型(H或V)，H代表横向分割 画布，V代表纵向分割画布，分割类型由程序随机决定。在二叉树产生后，对输入的 照片根据照片宽高比例进行排序。排序完成后，将照片映射到二叉树的叶子节点上， 一张照片唯一对应一个叶子节点。

步骤2、自下而上逐层计算内部节点的宽高比例。

在完成照片映射后，需要自下而上层次遍历二叉树的节点，确定每个内部节点 的宽高比例。由子节点计算父节点的宽高比例时，若父节点分割类型为“V”，则左 右孩子节点高度一致；若父节点分割类型为“H”，则左右孩子节点宽度一致。由此 可以导出一下计算公式：

父节点分割类型为’V’：Ar_parent＝Ar_left+Ar_right            (1)

父节点分割类型为‘H’：1/Ar_parent＝1/Ar_left+1/Ar_right         (2)

其中，Ar代表节点所代表区域的宽高比例，Ar_parent表示父节点所代表区域的宽 高比例，Ar_left和Ar_right分别表示父节点左右孩子节点所代表区域的宽高比例。对叶子 节点来说其宽高比例即为其所对应照片的宽高比例，内部节点的宽高比例根据其左 右子节点计算而得。

同时，在计算过程中还要确保计算结果满足预设条件，如果计算结果超出预设 比例范围，则调整父节点的分割类型，重新进行计算。在完成每一层节点计算后， 进入步骤3。

步骤3、根据结算结果逐层排序

在本步骤中主要是对每一层的计算结果进行排序(默认为递减排序)。如果没 有该过程，则在拼贴结果中，相邻照片之间出现大小悬殊这种情况的概率非常大， 影响拼贴结果的美观性。进行逐层排序可以避免这种情况的出现，保证拼贴结果中 相邻照片之间大小相近，使得拼贴结果更加美观。

在排序完成后，需要调整父子节点之间的对应关系，因为排序的过程会打破原 有的节点对应关系，当然只是需要调整排序层和其子节点层的对应关系，其他层不 需要调整。

需要注意的是：步骤2和步骤3交替进行，步骤2逐层计算内部节点的比例， 步骤3每一层的计算结果进行排序，直至完成所有节点的计算。

步骤4、自上而下计算节点的大小及位置

该步骤要在前三步完成后进行。首先根据预设画布高度H或者宽度W，结合树 根节点的宽高比例计算取得画布的大小。

计算画布大小的公式如下：

父节点分割类型为‘V’：                          (3)

node.Height＝node.Parent.Height

node.Width＝node.Height×node.Ar

父节点分割类型为‘H’：                           (4)

node.Width＝node.Parent.Width

node.Height＝node.Width/node.Ar

式中node.Height和node.Width分别表示当前节点所代表的区域的宽度和高度， node.Parent.Height和node.Parent.Width分别表示当前节点父节点的高度和宽度， node.Ar表示当前节点所代表区域的宽高比例。

计算位置的公式如下：

节点为左孩子节点                     (5)

node.Pox＝node.Parent.Pox

node.Poy＝node.Parent.Poy

节点为右孩子节点

父节点分割类型为‘V’                      (6)

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

node.Poy＝node.Parent.Poy

父节点分割类型为‘H’                     (7)

node.Pox＝node.Parent.Pox

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

式中node.Pox和node.Poy表示当前节点所代表的区域的左上角的坐标， node.Parent.Pox和node.Parent.Poy代表当前节点父节点所代表区域左上角的横坐标 和纵坐标，node.Parent.Left.Pox代表当前节点的父节点的左孩子节点所代表区域的左 上角的横坐标，node.Parent.Left.Width和node.Parent.Left.Height代表当前节点父节点 的左孩子节点所代表区域的宽度和高度。

对于每个节点来说，首先根据计算公式计算其画布的大小，而后计算其位置。 对于每一层来说自左向右计算。

本发明对运行环境的要求不高，可以运行在普通智能手机和PC上。

智能手机：1G内存以上配置

电脑：2G内存以上配置

尽管上面结合图对本发明进行了描述，但是本发明并不局限于上述的具体实施 方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术 人员在本发明的启示下，在不脱离本发明宗旨的情况下，还可以作出很多变形，这 些均属于本发明的保护之内。