A Fast Algorithm for Reconstructing hv-Convex Binary Images from Their Horizontal Projection

被引：0

作者：

Hantos, Norbert ^{[1
]}

Balazs, Peter ^{[2
]}

机构：

[1] Eotvos Lorand Univ, Dept Algorithms & Their Applicat, H-1117 Budapest, Hungary

[2] Univ Szeged, Dept Image Proc & Comp Graph, H-6720 Szeged, Hungary

来源：

ADVANCES IN VISUAL COMPUTING (ISVC 2014), PT II | 2014年 / 8888卷

关键词：

discrete tomography; reconstruction; connectedness; hv-convexity; polynomial-time algorithm; DISCRETE SETS; ORTHOGONAL PROJECTIONS; VERTICAL PROJECTIONS; POLYOMINOES;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The reconstruction of certain types of binary images from their projections is a frequently studied problem in combinatorial image processing. hv-convex images with fixed projections play an important role in discrete tomography. In this paper, we provide a fast polynomialtime algorithm for reconstructing canonical hv-convex images with given number of 4-connected components and with minimal number of columns satisfying a prescribed horizontal projection. We show that the method gives a solution that is always 8-connected. We also explain how the algorithm can be modified to obtain solutions with any given number of columns, and also with non-connected components.

引用

页码：789 / 798

页数：10

共 23 条

[1] Random Generation of hv-Convex Polyominoes with Given Horizontal Projection
Hantos, Norbert
Balazs, Peter
FUNDAMENTA INFORMATICAE, 2014, 135 (1-2) : 103 - 115
[2] An Empirical Study of Reconstructing hv-Convex Binary Matrices from Horizontal and Vertical Projections
Ozsvar, Zoltan
Balazs, Peter
ACTA CYBERNETICA, 2013, 21 (01): : 149 - 163
[3] Reconstructing hv-convex polyominoes from orthogonal projections
Chrobak, M
Dürr, C
INFORMATION PROCESSING LETTERS, 1999, 69 (06) : 283 - 289
[4] On the Ambiguity of Reconstructing hv-Convex Binary Matrices with Decomposable Configurations
Balazs, Peter
ACTA CYBERNETICA, 2008, 18 (03): : 367 - 377
[5] 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
[6] Approximating hv-convex binary matrices and images from discrete projections
Jarray, Fethi
Costa, Marie-Christine
Picouleau, Christophe
DISCRETE GEOMETRY FOR COMPUTER IMAGERY, PROCEEDINGS, 2008, 4992 : 413 - +
[7] Reconstruction of Canonical hv-Convex Discrete Sets from Horizontal and Vertical Projections
Balazs, Peter
COMBINATORIAL IMAGE ANALYSIS, PROCEEDINGS, 2009, 5852 : 280 - 288
[8] Comparison of algorithms for reconstructing hv-convex discrete sets
Balogh, E
Kuba, A
Dévényi, C
Del Lungo, A
LINEAR ALGEBRA AND ITS APPLICATIONS, 2001, 339 : 23 - 35
[9] Reconstructing hv-convex multi-coloured polyominoes
Bains, Adam
Biedl, Therese
THEORETICAL COMPUTER SCIENCE, 2010, 411 (34-36) : 3123 - 3128
[10] Reconstruction of hv-convex binary matrices from their absorbed projections
Kuba, A
Nagy, A
Balogh, E
DISCRETE APPLIED MATHEMATICS, 2004, 139 (1-3) : 137 - 148

← 1 2 3 →