Reconstructing hv-convex polyominoes from orthogonal projections

被引：69

作者：

Chrobak, M ^{[1
]}

Dürr, C

机构：

[1] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA

[2] Int Comp Sci Inst, Berkeley, CA 94704 USA

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 06期

基金：

美国国家科学基金会;

关键词：

combinatorial problems; discrete tomography; polyominoes;

D O I：

10.1016/S0020-0190(99)00025-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We address the problem of reconstructing a discrete 2D object, represented by a set of grid cells, from its orthogonal projections. We focus on objects called hv-convex polyominoes, which are connected objects with the property that the cells in each row and column are consecutive. The main result of this paper is a simple, O(mn min(m(2), n(2)))-time algorithm for reconstructing hv-convex polyominoes. (C) 1999 Elsevier Science B.V. kll rights reserved.

引用

页码：283 / 289

页数：7

共 38 条

[21] A fast algorithm for reconstructing hv-convex 8-connected but not 4-connected discrete sets
Balázs, P
Balogh, E
Kuba, A
DISCRETE GEOMETRY FOR COMPUTER IMAGERY, PROCEEDINGS, 2003, 2886 : 388 - 397
[22] Generation and empirical investigation of hv-convex discrete sets
Balazs, Peter
Image Analysis, Proceedings, 2007, 4522 : 344 - 353
[23] Optimization and reconstruction of hv-convex (0,1)-matrices
Dahl, G
Flatberg, T
DISCRETE APPLIED MATHEMATICS, 2005, 151 (1-3) : 93 - 105
[24] Reconstruction of 8-connected but not 4-connected hv-convex discrete sets
Balázs, P
Balogh, E
Kuba, A
DISCRETE APPLIED MATHEMATICS, 2005, 147 (2-3) : 149 - 168
[25] Reconstructing an alternate periodical binary matrix from its orthogonal projections
Costa, MC
Jarray, F
Picouleau, C
THEORETICAL COMPUTER SCIENCE, PROCEEDINGS, 2005, 3701 : 173 - 181
[26] Reconstructing h-convex binary images from its horizontal and vertical projections by simulated annealing
Patel, Divyesh
Srivastava, Tanuja
2015 EIGHTH INTERNATIONAL CONFERENCE ON CONTEMPORARY COMPUTING (IC3), 2015, : 117 - 121
[27] Reconstructing (h, v)-convex 2-dimensional patterns of objects from approximate horizontal and vertical projections
Boufkhad, Y
Dubois, O
Nivat, M
THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) : 1647 - 1664
[28] Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections
Balazs, Peter
DISCRETE APPLIED MATHEMATICS, 2013, 161 (15) : 2224 - 2235
[29] A decomposition technique for reconstructing discrete sets from four projections
Balazs, Peter
IMAGE AND VISION COMPUTING, 2007, 25 (10) : 1609 - 1619
[30] Reconstructing 3D-Structure from Microscopic Projections using Filters
Masilamani, V.
Krithivasan, Kamala
WMSCI 2008: 12TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL II, PROCEEDINGS, 2008, : 168 - 171

← 1 2 3 4 →