Name
Abstract | ||
|---|---|---|
A binary matrix can be scanned by moving a fixed rectangular window (sub- matrix) across it, rather like examining it closely under a microscope. With each viewing, a convenient measurement is the number of 1s visible in the window, which might be thought of as the luminosity of the window. The rectangular scan of the binary matrix is then the collection of these luminosities presented in matrix form. We show that, at least in the technical case of a smooth m ×n binary matrix, it can be reconstructed from its rectangular scan in polynomial time in the parameters m and n, where the degree of the polynomial depends on the size of the window of inspection. For an arbitrary binary matrix, we then extend this result by determining the entries in its rectangular scan that preclude the smoothness of the matrix. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2006.10.030 | International Workshop on Combinatorial Image Analysis |
Keywords | Field | DocType |
binary matrix,technical case,computational complexity,fixed rectangular window,convenient measurement,arbitrary binary matrix,parameters m,projection,rectangular scan,matrix form,tomographical problem,discrete tomography,polynomial time,reconstruction algorithm,smoothmxn binary matrix | Discrete mathematics,Polynomial,Logical matrix,Mathematical analysis,Discrete tomography,Matrix (mathematics),Geometry,Time complexity,Block matrix,Mathematics,Binary number,Window function | Journal |
Volume | Issue | ISSN |
370 | 1-3 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-23942-1 | 6 | 0.58 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Frosini | 1 | 101 | 20.44 |
| Maurice Nivat | 2 | 1261 | 277.74 |