arrow
Return

Rectangle blanket problem: Binary integer linear programming formulation and solution algorithms

delete2019-08-01
delete3
delete
OA
AI
B
Barış Evrim Demiröz
İ
İ. Kuban Altınel *
L
Lale Akarun
DOI:10.1016/j.ejor.2019.02.004delete
deleteOriginal
deleteShare
deleteSave
View PDF
Abstract

Abstract

En 中文
A rectangle blanket is a set of non-overlapping axis-aligned rectangles, used to approximately represent the two-dimensional image of a shape. The use of a rectangle blanket is a widely considered strategy for speeding-up the computations in many computer vision applications. Since neither the rectangles nor the image have to be fully covered by the other, the blanket becomes more precise as the non-overlapping area of the image and the blanket decreases. In this work, we focus on the rectangle blanket problem, which involves the determination of an optimum blanket minimizing the non-overlapping area with a given image subject to an upper bound on the total number of rectangles the blanket can include. This problem has similarities with rectangle covering, rectangle partitioning and cutting/packing problems. The image replaces an irregular master object by an approximating set of smaller axis-aligned rectangles. The union of these rectangles, namely, the rectangle blanket, is neither restricted to remain entirely within the master object, nor required to cover the master object completely. We first develop a binary integer linear programming formulation of the problem. Then, we introduce four methods for its solution. The first one is a branch-and-price algorithm that computes an exact optimal solution. The second one is a new constrained simulated annealing heuristic. The last two are heuristics adopting ideas available in the literature for other computer vision related problems. Finally, we realize extensive computational tests and report results on the performances of these algorithms. Keywords: Integer programming Branch-and-price Computer vision Cutting /Packing Heuristics (C) 2019 Elsevier B.V. All rights reserved.
Keywords:
Integer programming
Branch-and-price
Computer vision
Cutting /Packing
Heuristics

Journal

European Journal of Operational Research cover
European Journal of Operational Research
IF:
6
Papers:
2.2W
Citations:
8.1W

Organization

B
Bogazici University
Scholars:
230
Papers: 94
Citations: 1.7K
Cited Papers

Cited Papers

Immunohistochemistry of Lung Cancer: Cell differentiation and Growth Properties
err1989-01-01
err0
PREAI
errYukio Shimosato; Setsuo Hirohashi; Takashi Nakajima; Masayuki Noguchi
errShare
errSave
errShare
errSave
errShare
errSave
errShare
errSave
The geometry of nesting problems: A tutorial
err2008-01-01
err179
PREAI
errBennell, Julia A.; Oliveira, Jose F.
errShare
errSave
Extracellular matrix (mesoglea) of Hydra vulgaris
err1991-12-01
err0
PREAI
errMichael P. Sarras; Michael E. Madden; Xiaoming Zhang; Sripad Gunwar; Jacquelyn K. Huff; Billy G. Hudson
errShare
errSave
researcher View more