Further Examples of Inverse Problems

Problems of this kind are very common in the analysis of experimen- tal data in natural sciences. Experimentalists look at a discrete inverse problem in the following way. They perform an experiment from which they gain a set of measuring results, and they combine them in a Q- dimensional data vector d. These data are compared with a model of the observed process. The parameters of this model are given by a P- dimensional model vector p. Now we assume that the relationship be- tween the model and the data vector can be described as linear. It can then be expressed by a model matrix M and we obtain Eq. (17.73).

For image processing, inverse problems are also common. They do not only include the complete list of problems discussed in the introduc- tion of this chapter (Section 17.1) but also optimization of fi lters. In this book, least-squares optimized fi lters for interpolation (Section 10.6.6) and edge detection (Sections 12.3.5 and 12.5.5) are discussed.

17.7 Network Models‡                                                                                           469

U0n

                                                         

Un

 

Figure 17.9: Simple 1-D network for a 1-D smooth DVF; after Harris [62].

 

17.7 Network Models‡

In this section we discuss another method emerging from electrical engineering, the network model. It has the advantage of being a discrete model which directly corresponds to discrete imagery. This section follows the work of Harris [61, 62]. The study of network models has become popular since network structures can be implemented directly on such massive parallel computer systems as the Connection Machine at Massachusetts Institute of Technology (MIT) [62] or in analog VLSI circuits [123].

 

17.7.1 One-Dimensional Networks‡

First, we consider the simple 1-D case. The displacement corresponds to an electric tension. Continuity is forced by interconnecting neighboring pixels with electrical resistors. In this way, we build up a linear resistor chain as shown in Fig. 17.9. We can force the displacement at a pixel to a certain value by applying a potential at the corresponding pixel. If only one voltage source exists in the resistor chain, the whole network is put to the same constant voltage. If another potential is applied to a second node of the network and all interconnecting resistors are equal, we obtain a linear voltage change between the two points. In summary, the network of resistors forces continuity in the voltage, while application of a voltage at a certain node forces similarity.

There are diff erent types of boundary conditions. On the one hand, we can apply a certain voltage to the edge of the resistor chain and thus force a certain value of the displacement vector at the edge of the image. On the other hand, we can make no connection. This is equivalent to setting the fi rst-order spatial derivative to zero at the edge. The voltage at the edge is then equal to the voltage at the next connection to a voltage source.

In the elasticity models (Section 17.3.5) we did not set the displacements to the value resulting from the similarity constraint directly, but allowed for some fl ex- ibility by applying the displacement via a spring. In a similar manner we apply the voltage, U_0n, to the node n not directly but via the resistor S_n (Fig. 17.9). We set the resistance proportional to the uncertainty of the displacement vector.

The diff erence equation for the network model is given by the rule that the sum of all currents must cancel each other at every node of the network. Using the defi nitions given in Fig. 17.9, we obtain for the node n of the network

U n − U 0n + U n − U n − 1 + U n − U n + 1 = 0.                                    (17.74)

S_n                R                 R

470                                                                     17 Regularization and Modeling

 

Un-1                 Un                  Un+1

 

Figure 17.10: Discrete network model for a 1-D scalar feature with smooth fi rst- order derivatives; after Harris [62].

 

x

The two fractions on the right side constitute the second-order discrete diff er- entiation operator D2 (see Section 12.4.2). Thus Eq. (17.74) results in

 

1 (U S

1 ∂ 2U

− U₀) − R ∂ x2 = 0.                                         (17.75)

α 2

This equation is the 1-Dform of Eq. (17.22). For a better comparison, we rewrite this equation for the 1-Dcase:

 

(∂ _x

g)2 .f

∂ _tg

Σ +

∂ _xg −

∂ 2f

 

∂ x2 =

 

0.                          (17.76)

−

Now we can quantify the analogy between the displacement vectors and the network model. The application of the potential U₀ corresponds to the com- putation of the local velocity by (∂ _tg)/(∂ _xg). The similarity and smoothness terms are weighted with the reciprocal resistance (conductance) 1/S and 1/R instead of with the squared gradient (∂ _xg)2 and α 2.

 

17.7.2 Generalized Networks‡

Now we turn to the question of how to integrate the continuity of fi rst-order derivatives into the network model. Harris [61] used an active subtraction mod- ule which computes the diff erence of two signals. All three connections of the element serve as both inputs and outputs. At two arbitrary inputs we apply a voltage and obtain the corresponding output voltage at the third connection.

Such a module requires active electronic components [61]. Figure 17.10 shows how this subtraction module is integrated into the network. It computes the diff erence voltage between two neighboring nodes. These diff erences — and not the voltages themselves — are put into the resistor network.

In this way we obtain a network that keeps the fi rst derivative continuous. We can generalize this approach to obtain networks that keep higher-order deriva- tives continuous by adding several layers with subtraction modules (Fig. 17.11).

 

17.7.3 Discontinuities in Networks‡

Displacement vector fi elds show discontinuities at the edges of moving objects. Discontinuities can easily be implemented in the network model. In the simple network with zero-order continuity (Fig. 17.9), we just remove the connecting

17.7 Network Models‡                                                                                          471

Un-1           Un           Un+1

 

Figure 17.11: Generalized network for a 1-D DVF that keeps higher-order deriv- atives smooth; after Harris [62].

 

Un-1                      Un                      Un+1

 

Figure 17.12: Generalized 1-D network with a discontinuity in the DVF and its fi rst spatial derivative as indicated.

 

 

resistor between two neighboring nodes to produce a potential jump between these two nodes. In order to control the smoothness (Section 17.4), we can also think of a nonlinear network model with voltage-dependent resistors. We might suspect discontinuities at steep gradients in the velocity fi eld. If the resistance increases with the tension, we have a mechanism to produce implied disconti- nuities. These brief considerations illustrate the fl exibility and suggestiveness of network models.

Integration of discontinuities is more complex in a generalized network. Here we may place discontinuities at each level of the network, i. e., we may make either the DVF or any of its derivatives discontinuous by removing a resistor at the corresponding level. We need to remove all resistors of deeper-lying nodes that are connected to the point of discontinuity (Fig. 17.12). Otherwise, the higher-order derivatives stay continuous and cause the lower-order derivatives to become continuous.

472                                                                     17 Regularization and Modeling

 

R

Un-1                       Un                         Un+1

 

Figure 17.13: 1-D network with capacitors to simulate the convergence of itera- tive solutions.

 

17.7.4 Two-Dimensional Networks‡

The network model can also be used for higher-dimensional problems. For a 2-Dnetwork model with zero-order continuity, we build up a 2-Dmesh of resis- tors. The setup of generalized 2-Dnetwork models with higher-order continuity constraints is more complex. In each level we must consider the continuity of several partial derivatives. There are two fi rst-order spatial derivatives, a hor- izontal and a vertical one. For each of them, we need to build up a separate layer with subtraction modules as shown in Fig. 17.10, in order to observe the smoothness constraint. Further details can be found in Harris [62].

 

17.7.5 Multigrid Networks‡

One of the most important practical issues is fi nding the rate of convergence of iterative methods for solving large equation systems in order to model them with networks. The question arises of whether it is also possible to integrate this important aspect into the network model. Iteration introduces a time de- pendency into the system, which can be modeled by adding capacitors to the network (Fig. 17.13). The capacitors do not change at all the static properties of the network.

When we start the iteration, we know the displacement vectors only at some isolated points. Therefore we want to know how many iterations it takes to carry this information to distant points where we do not have any displacement information. To answer this question, we derive the diff erence equation for the resistor-capacitor chain as shown in Fig. 17.13. It is given by the rule that the sum of all currents fl owing into one node must be zero. In addition, we need to know that the current fl owing into a capacitor is proportional to its capacitance C and the temporal derivative of the voltage ∂ U/∂ t:

U n − 1 − U n + U n + 1 − U n − C ∂ U n = 0                                      (17.77)

R

or

∂ U_n

R              ∂ t

 

(∆ x)2 ∂ 2U_n

 

∂ t = RC

∂ x2 .                                       (17.78)

=

In the second equation, we have introduced ∆ x as the spatial distance between neighboring nodes in order to formulate a spatial derivative. Also, RC τ, the time constant of an individual resistor-capacitor circuit. Equation (17.78) is the discrete 1-Dformulation of one of the most important equations in natural sciences, the transport or diff usion equation, which we discussed in detail in Sections 5.2.1 and 17.5. Without explicitly solving Eq. (17.78), we can answer

17.8 Inverse Filtering                                                                     473

 

the question as to the time constant needed to smooth the displacement vector fi eld over a certain space scale. Let us assume a spatially varying potential with a wavelength λ decreasing exponentially with a time constant τ _λ that depends on the wavelength λ (compare Section 5.2.1):

U(x) = U₀(x) exp(− t/τ ) exp(ikx).                                      (17.79)

Introducing this equation into Eq. (17.78), we obtain

τ _λ =      τ   =       τ      λ 2.                             (17.80)

(∆ x k)2          4π 2(∆ x)2

With this result, we can answer the question as to the convergence time of the iteration. The convergence time goes with the square of the wavelength of the structure. Consequently, it takes four times longer to get gray values at double the distance into equilibrium. Let us arbitrarily assume that we need one iteration step to bring neighboring nodes into equilibrium. We then need 100 iteration steps to equilibrate nodes that are 10 pixels distant. If the potential is only known at isolated points, this approach converges too slowly to be useful.

Multigrid data structures, which we discussed in Chapter 5, are an effi cient tool to accelerate the convergence of the iteration. At the coarser levels of the pyramid, distant points come much closer together. In a pyramid with only six levels, the distances shrink by a factor of 32. Thus we can compute the large- scale structures of the DVF with a convergence rate that is about 1000 times faster than on the original image. We do not obtain any small-scale variations, but can use the coarse solution as the starting point for the iteration at the next fi ner level.

In this way, we can refi ne the solution from level to level and end up with a full-resolution solution at the lowest level of the pyramid. The computations at all the higher levels of the pyramid do not add a signifi cant overhead, as the number of pixels at all levels of the pyramid is only one third more than at the lowest level. The computation of the DVF of the taxi scene (Fig. 17.3) with this method is shown in Fig. 17.4.

 

Inverse Filtering

In this section, we study a special class of inverse problems and show the way to fast iterative solutions of huge inverse problems.

 

Image Restoration

No image formation system is perfect because of inherent physical lim- itations. Therefore, images are not identical to their original. As sci- entifi c applications always push the limits, there is a need to correct for limitations in the sharpness of images. Humans also make errors in operating imaging systems. Images blurred by a misadjustment in the focus, smeared by the motion of objects or the camera or a mechanically unstable optical system, or degraded by faulty or misused optical sys- tems are more common than we may think. A famous recent example

474                                                                     17 Regularization and Modeling

 

was the fl aw in the optics of the Hubble space telescope where an error in the test procedures for the main mirror resulted in a signifi cant resid- ual aberration of the telescope. The correction of known and unknown image degradation is called restoration.

The question arises whether, and if so, to what extent, the eff ects of degradation can be reversed. It is obvious, of course, that information that is no longer present at all in the degraded image cannot be retrieved. To make this point clear, let us assume the extreme case that only the mean gray value of an image is retained. Then, it will not be possible by any means to reconstruct its content. However, images contain a lot of redundant information. Thus, we can hope that a distortion only partially removes the information of interest even if we can no longer “see” it directly.

In Sections 7.6 and 9.2.1, we saw that generally any optical system including digitization can be regarded as a linear shift-invariant system and, thus, described to a good approximation by a point spread function and a transfer function.

The fi rst task is to determine and describe the image degradation as accurately as possible. This can be done by analyzing the image forma- tion system either theoretically or experimentally by using some suitable test images. If this is not possible, the degraded image remains the only source of information.

 

⇐ Предыдущая70717273747576777879Следующая ⇒

Поделиться: