提出可变区域打包问题,解决图像生成中对象布局的高效排列。
Introducing Resizable Region Packing Problem in Image Generation, with a Heuristic Solution
- 设计贪心启发式算法,动态打包任意形状与位置的区域。
- 在真实合成异常检测数据集上验证,成功处理不同复杂度的打包实例。
- 适合需要可控布局的生成模型、合成数据生成场景使用。
计算机视觉中的图像数据生成长期以来比判别性任务更难解决,需在场景画布中合理放置合适大小的相关物体。现有方法主要分为基于图形和基于生成模型两类,二者背后均隐藏优化问题。本文提出一种新型实用的古典装箱问题变体——可变锚定区域打包(Resizable Anchored Region Packing, RARP)问题,推测其为NP-hard,并提供详细论证。作为首个解决方案,提出一种通用启发式算法,能高效打包任意数量、任意形状与位置的区域至图像画布,通过迭代贪心策略满足约束条件。该算法在大规模合成异常检测数据集生成中得到验证,每张图像的装箱参数差异显著,视觉检查及解正确性验证表明算法有效。随着生成模型在深度学习中的兴起,合成数据生成日益主流,我们预期该问题将在图像科学界受到重视。
原文摘要 · Abstract (English)
The problem of image data generation in computer vision has traditionally been a harder problem to solve, than discriminative problems. Such data generation entails placing relevant objects of appropriate sizes each, at meaningful location in a scene canvas. There have been two classes of popular approaches to such generation: graphics based, and generative models-based. Optimization problems are known to lurk in the background for both these classes of approaches. In this paper, we introduce a novel, practically useful manifestation of the classical Bin Packing problem in the context of generation of synthetic image data. We conjecture that the newly introduced problem, Resizable Anchored Region Packing(RARP) Problem, is NP-hard, and provide detailed arguments about our conjecture. As a first solution, we present a novel heuristic algorithm that is generic enough and therefore scales and packs arbitrary number of arbitrary-shaped regions at arbitrary locations, into an image canvas. The algorithm follows greedy approach to iteratively pack region pairs in a careful way, while obeying the optimization constraints. The algorithm is validated by an implementation that was used to generate a large-scale synthetic anomaly detection dataset, with highly varying degree of bin packing parameters per image sample i.e. RARP instance. Visual inspection of such data and checking of the correctness of each solution proves the effectiveness of our algorithm. With generative modeling being on rise in deep learning, and synthetic data generation poised to become mainstream, we expect that the newly introduced problem will be valued in the imaging scientific community.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。