代码之家 › 专栏 › 技术社区 › bramp Madhur Ahuja

多图像放置算法-拼贴算法

image algorithm

bramp Madhur Ahuja · 技术社区 · 14 年前

我正在创建一个应用程序来同时显示多个视频(比如2-10个视频)。我基本上是在寻找一种算法,可以帮助在屏幕上放置视频。我面临的问题是,每个视频可能有不同的纵横比,我显然需要调整视频的大小,使它们都适合屏幕。但我想调整大小和适合他们的方式,我最大限度地使用屏幕(并尽量减少纵横比失真)。此外,我希望用户能够增加一个或多个视频的大小,以便在屏幕上占用更多的空间。因此,该算法应该是稳定的,在这个意义上,扩大一个视频并不能使所有的位置跳跃。

我以一种语言不可知论的方式问这个问题,而我使用视频的事实是无关的,这个问题同样适用于静止图像。

那么有人知道放置算法吗?

这里有一个例子来帮助澄清。我有三个视频,大小如下。我希望第一个视频占屏幕的大约50%,最后两个视频占屏幕的大约25%。

(464, 336) 50%
(624, 480) 25%
(608, 336) 25%

我如何将它们放在屏幕上(1024x800)来实现这一点?我想我会先把屏幕分成两半,最适合上半部分的第一个视频。然后我会把下半部分分成两部分,尽我所能把剩下的两个视频都放进去。

提前谢谢

3 回复 | 直到 14 年前

Mr Fooz 14 年前

这是一个版本的箱子包装问题 http://en.wikipedia.org/wiki/Bin_packing_problem 这是NP难,所以你要选择一些合理的启发式。如果你不想在调整视频大小的时候跳来跳去,你需要留下一堆额外的死角,或者自动缩小其他的死角。

除非你有充分的理由允许,否则我建议要求纵横比保持不变。

建议:首先确定所有视频的高度,然后使用贪婪的先适配算法将其打包。初始高度将是总屏幕高度的整数部分。如果有人调整视频的大小,其他所有内容都会缩小到相同的分数值,然后移走以适应。

Dr. belisarius 14 年前

我认为A Treemap 是您可能需要的。

算法历史的良好描述

订购的Quantum Treemaps Algs,与您当前的SEACH更相关,
< h!

对算法历史的良好描述 here

有序量子树算法,与你当前的seach更相关, here

嗯!

nessence 14 年前

基于舍入的平方根+逻辑。如果sqrt的其余部分为<0.5,则向下取整结果,将结果用作行/列,并将1添加到行或列计数中;如果sqrt的其余部分为>=0.5,则向上取整结果,并将其用作行/列计数。

10 videos = 4x3 (3.16; rounded down, so add 1 row or col)
9 videos = 3x3 (3; abs)
8 videos = 3x3 (2.82; round up)
7 videos = 3x3 (2.64; round up)
6 videos = 3x2 (2.44; round down, so add 1 row or col)
5 videos = 3x2 (2.23; round down, so add 1 row or col)
4 videos = 2x2 (2; abs)
3 videos = 2x2 (1.73; round up)
2 videos = split screen in half vertically or horizontally (however you'd like)
1 video = full screen

现在,这将使所有的视频“方形”,并且,可能是最好的选择,因为你真的不能很容易地解释存在于那里的不同分辨率/比率(除非它对你是静态的)。

因此,根据显示分辨率与视频分辨率的比率,网格周围会有填充空间,因此您希望网格居中。也就是说,有一种选择是,将这个“填充”空间除以行数(或cols),并将其用作视频之间的缓冲区。

一旦你有了行/列的计数,并且假设所有的视频都是相同的大小,你只需将屏幕宽度除以列,高度除以行,你就有了你的视频尺寸。

然后,将视频平铺到屏幕上——显然,在同样的情况下,网格上的一些点可能是空的。您可以检测网格上空间覆盖的行和列,并将视频集中在特定行上。

如果你想“最大化”一段视频,那么提前确定“最大化”意味着多少空间。然后,在计算其他视频的大小之前,从屏幕分辨率中减去像素足迹。如果最大化意味着50%的屏幕,那么您将从网格中的视频数量中减去该视频,并从显示分辨率中减去50%的像素空间。