English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this contribution we present a network-flow approach The application of known algorithms poses a problem because to the reconstruction of binary functions on planar or spatial lattices. the tilt range of the crystal is normally restricted, for several We develop a family of reconstruction algorithms which extends previreasons. The most important problem is the obstruction to the ous work by Slump and Gerbrands. q 1998 John Wiley & Sons, Inc. Int electron path produced by the case supporting the specimen (at J Imaging Syst Technol, 9, 147–154, 1998 high angles) , which in commercial instruments limits the tilt angle to around a {607 angle. Indeed, the maximum tilt angle influences the resolution of the reconstruction by limiting the I. PRELIMINARIES amount of Fourier space sampled [2,5] . In addition, a large numA binary tomography problem deals with the reconstruction of a ber of projections recorded with high precision (taken at increblack and white image from the knowledge of all parallel projecments of at most {0.17) are required, a condition that cannot be tions of that image along a set of directions. This problem has fulfilled in Schwander’s procedures, in which it is possible to been considered for over 20 years, with motivation coming measure projections only within a cone of 157. mainly from (biplane) angiography [1,2] and from industrial In mathematical terms, the binary tomography problem can imaging (e.g., of radioactive materials) . be modeled by considering the ordinary integer lattice Z d , where Recently, an important application of binary tomography was d ¢ 2. A binary function with finite support w :Z d r {0, 1} is proposed by Kisielowski et al. [3] and Schwander et al. [4] in known only by its line sums (projections) along any parallel line connection with the study of the atomic structure of crystal latin each of k given directions. The problem is to reconstruct the tices. Using transmission electron microscopy, Schwander develactual function w from these projection data. We say that a reconoped a technique (QUANTITEM) that measures the variation of struction wR is feasible if w and wR have the same projections the sample potential from general lattice images of structurally along any parallel line in each of the given k directions. perfect crystalline materials, requiring no knowledge of the image Within this framework, a pioneer work on binary tomography conditions. This technique, which can be applied to a wide range that considers all parallel projections along a small set of direcof materials—including semiconducting metallic elements and tions was written by Fishburn et al. [6] . They showed that some alloys—can be used to count approximately the number of atoms specific configurations, called additive sets, can be reconstructed in each atomic column of a crystal, in the case where the atoms from the knowledge of the line sums along any parallel line in reside on coherent lattices, with no compositional inhomogeneitonly two directions. In general, however, when a reduced number ies in the beam direction. Since the crystal can be tilted along of directions is considered, there is not uniqueness, which poses different zone axes, all column sums can be known along a small a threat to any effort of finding a good feasible solution, i.e., a set of directions. The goal is to reconstruct the atomic configurareconstruction close enough to the unknown configuration. Some tion of the crystal from knowledge of the approximate number significant contributions on this problem are due to Aharoni et of atoms in each atomic column along a small set of directions. al. [7] and Kuba [8]. As indicated elsewhere [3,4] , this knowledge may be used to On the other hand, from a computational point of view, the measure the chemical transition between two regions of known problem of finding feasible solutions is NP complete for k ¢ 3, composition in crystalline materials. In general, this research for most classes of sets appearing in applications. Nevertheless, opens the way for the study of a variety of important interfacial there are some algorithms available to find solutions in polynoreactions at the atomic level such as surface roughening during mial time under certain circumstances [9–11], on which we shall oxidation. Furthermore, the fact that this has been particularly comment succinctly in what follows. useful in producing an atomic level topographic map of an Si/ An interesting methodology was recently developed by FishSiO2 interface, as well as a microscopic map of an Si/GeSi/ burn et al. [9] . Here, the binary function w to be reconstructed Si quantum well in cross section, shows its importance to the from its projections is relaxed to be a ‘‘fuzzy set’’; i.e., it is development of the silicon technology necessary for electronic replaced by a function taking values in the interval [0, 1] . Under devices. this relaxation, the problem of finding a feasible solution can be treated as a linear programming problem for which there are wellCorrespondence to: P. Salzberg known efficient algorithms. However, if w01(1) is not additive, Contract grant sponsor: NIH-MBRS; Contract grant number: 5S-06GM then the solution produced by the LP algorithms is, in general, 081023 Contract grant sponsor: AT&T Foundation fuzzy (i.e., not binary) . Another interesting approach using this q 1998 John Wiley & Sons, Inc. CCC 0899–9457/98/020147-08 4491 / 8410$$4491 03-26-98 17:12:05 ista W: IST relaxation technique in conjunction with the EM algorithm, and for which actual reconstructions were exhibited, was presented in a discrete tomography workshop [11]. At this point, the following question arises: What can be done if the solution given by these algorithms is fuzzy? Obviously, this question extends to other algorithms in the following way: What can be done if the computer does not stop after a lengthy period of time? An answer to this question points to the search of approximate Figure 1. (a ) Elements of a binary tomography problem (grid data solutions. In this regard, an example is provided by the methodolare unknown). (b) How this problem is represented as a network flow ogies presented above (cf. [9] , pp. 59–60). We can construct a problem. Numbers above the source and sink arcs denote capacities. binary function from the fuzzy solution by breaking the lattice All other arcs have capacity 1. points whose linear program solution lies between 0 and 0.50 , and 0.5/ and 1, into 0 and 1, respectively. Now, a relevant question is, how good is this solution? Also within this framework, the first author [10] developed a III. PREVIOUS RESEARCH polynomial time algorithm to approximate a feasible solution by In a pioneer article, Slump and Gerbrands [12] introduced a means of a technique close to filtered backprojection and based network-flow approach to reconstruction of the left ventricle from on combinatorial properties of lines in the affine geometry two projections. They showed the equivalence of reconstructing AG(Fq , d) . This algorithm involves a maximum likelihood type a binary matrix from row and column sums, and that of finding of heuristic. the maximal flow in a directed network. Prior knowledge is introIn this contribution, we restate the tomography problem as a duced by means of their minimal cost-capacitated flow algorithm, network-flow problem and introduce a new promising algorithm which is a variant of Klein’s minimal cost-flow algorithm [13]. to find approximate solutions. Using this network-flow approach, Anstee [14] obtained very interesting theoretical results on similar grounds. In [12], the binary tomography problem is given in terms of II. THE BINARY TOMOGRAPHY PROBLEM an (unknown) (0, 1)-matrix of which the row and column sums are known. The tomographic problem consists of finding feasible We denote by V , Z d the finite domain of the (0, 1)-function solutions, i.e., (0, 1)-matrices with the same row and column w introduced above. In practice, V will be a square or cubic grid sums as the given (unknown) one. of points. We assume that V is endowed with a set of lines L, Figure 1 shows the conversion of the tomography problem induced by those lines in the Euclidean space R intersecting V. ( left) to a maximal network flow problem (right) , for a simple In what follows, L represents a given subset of L. The set of all 3 1 3 lattice on the plane. Arcs emerging from the source (s) lines parallel to a given one defines what we call a direction. As represent row sums. Analogously, arcs converging to the sink ( t) usual, directions will be described by their slope. Also, we use represent column sums. In both cases, we consider the capacity DL to denote the set of directions included in L. In this article, of those arcs as being the corresponding row and columns sums, we assume that with each direction in DL , L contains all parallel respectively. Now, each point of the planar grid (matrix) is reprelines of L in that direction. In this case, we refer to L as a full sented by an arc in the complete bipartite graph with left nodes set of lines. r1 , r2 , r3 , and right nodes c1 , c2 , c3 . These arcs are endowed with Now, the available information will be given in terms of the unit capacity. In a later work, Tso [15] discussed applications of line sums or projections, which for any given line L √ L are this kind of algorithm to automatic chromosome classification defined as w(L) Å (V>L w(v) . We refer to w(L) indistinctly, and to arterial reconstruction from two views. either as the weight of L (with respect to w) , or as the projection or line sum of w along L . IV. EXTENSION TO SEVERAL DIRECTIONS Finally, a natural way to assess the goodness or closeness of a reconstruction wR to w is by contrasting their line sums for every The network-flow model can be extended to consider other direcline in L. In this contribution, the norm \r\` arises in a natural tions, as well as to spatial lattices. way, and theref

Network flow model for binary tomography on lattices