Abstract

Measuring an array of variables is central to many systems, including imagers (array of pixels), spectrometers (array of spectral bands) and lighting systems. Each of the measurements, however, is prone to noise and potential sensor saturation. It is recognized by a growing number of methods that such problems can be reduced by multiplexing the measured variables. In each measurement, multiple variables (radiation channels) are mixed (multiplexed) by a code. Then, after data acquisition, the variables are decoupled computationally in post processing. Potential benefits of the use of multiplexing include increased signal-to-noise ratio and accommodation of scene dynamic range. However, existing multiplexing schemes, including Hadamard-based codes, are inhibited by fundamental limits set by sensor saturation and Poisson distributed photon noise, which is scene dependent. There is thus a need to find optimal codes that best increase the signal to noise ratio, while accounting for these effects. Hence, this paper deals with the pursuit of such optimal measurements that avoid saturation and account for the signal dependency of noise. The paper derives lower bounds on the mean square error of demultiplexed variables. This is useful for assessing the optimality of numerically-searched multiplexing codes, thus expediting the numerical search. Furthermore, the paper states the necessary conditions for attaining the lower bounds by a general code. We show that graph theory can be harnessed for finding such ideal codes, by the use of strongly regular graphs.

© 2007 Optical Society of America

1. Introduction

Often, there is a need to measure an array of variables. This occurs in two dimensional imaging [1] (array of pixels), spectrometry (array of wavelength bands) [27], tomography and coded aperture imaging (array of viewing directions) [812], and study of reflectance functions in computer vision (array of lighting directions) [1319] etc. The array can be high dimensional, if it includes several types of the mentioned domains, such as in hyperspectral imaging. The variables in the array are often measured sequentially. For example, in each measurement, the lighting direction, spectral band, or an aperture mask can change.

Each of the measurements is prone to noise. This measurement noise propagates to an error in the estimation of the desired array of variables. This problem is exacerbated by constraints on the system and the object. For example, according to Ref. [3], constrains on system weight, price and power consumption of infrared spectrometers may require the use of uncooled detectors, which are generally noisy. In another example, the radiating object may be wide and diffuse [4], making its coupling into a narrow slit of a spectrometer inefficient, thus yielding a low signal, relative to the noise. For a given acquisition time, however, noise can be efficiently reduced using multiplexing [27,9,1823]. Here, in each sequential measurement, multiple elements of the sought array (e.g., multiple spectral bands) are linearly weighted (multiplexed) and sensed simultaneously at a detector. In sequential measurements, the multiplex weighting changes. The set of weights is termed a multiplexing code. Once the measurements are done, computational demultiplexing derives the sought variable array.

This paper deals with pursuit of an optimal code, such that the noise in the sought variables is minimal. Common multiplexing codes are based on Hadamard matrices [9]. Their use was proposed in a wide range of fields, including very recent studies [3, 4, 18, 19, 24]. They are optimal if noise is independent of the signal and if no saturation effect is possible. Hence, they do not account for two fundamental effects: saturation and photon noise (the latter is signal-dependent). This can make multiplexing by Hadamard codes counterproductive [19, 24], and may be the reason for low benefits achieved in practice by Hadamard-based systems [3, 4, 18, 19, 24]. Moreover, for most sizes of the variable array, there are no Hadamard codes. In contrast, in this paper we deal with general codes, considering explicitly saturation and signal-dependent photon noise. We seek to maximize the estimation accuracy of the signal sources, by accounting for the sensor specifications and avoiding saturation.

Recent studies [20, 22, 23, 25, 26] considered some of these fundamental aspects. Ref. [20] derived an expression for the signal to noise ratio (SNR) in the presence of photon noise. It utilized this expression to examine the SNR yielded by pre-set cyclic codes. Ref. [23] considered photon-noise for devising binary, cyclic codes, for a small set of sizes of the sought variable array. To account for any array size, saturation and photo noise, Ref. [22] proposed efficient numerical optimization of the multiplexing code. However, numerical optimization as in Ref. [22] may stagnate at sub-optimal solutions, with no indication of how good they are relative to the elusive optimal solution.

We seek to properly understand the task of optimal multiplexing in general, and even point out solutions to the task. Thus, this paper performs a comprehensive theoretical analysis. First, it focuses on the search for optimal codes, under fixed radiant power, as on a saturation threshold. It derives fundamental lower bounds on the output noise (estimation error). These bounds indicates how well any general multiplexing code can potentially reduce the noise. Furthermore, we show that in order to attain a lower bound (ideal multiplexing), certain conditions should be satisfied by the multiplexing code. Hadamard codes are special cases of our analysis, hence this work significantly generalizes the known art. This has a major importance, as we explain a way to numerically optimize multiplexing codes under the influence of photo noise, beside saturation and detector noise.

In addition, an interesting relation is revealed to graph theory, a large mathematical field, typically distinct from that used in intensity noise analysis. We show that graph theory can be harnessed for finding ideal codes, by using strongly regular graphs.

2. Theoretical background

2.1. Multiplexing

As mentioned in Sec. 1, multiplexing is a general method used in different fields. In each field, the sought (demultiplexed) array of variables represents a different physical quantity. The same applies to the multiplexed measurements. Nevertheless, the mathematical treatment is equivalent in all the fields. To associate the variables and measurements with familiar quantities, we use the domain of lighting, which is employed in computer vision [1315,18] and in research done in computer graphics [16, 17, 19]. However, thanks to the equivalence of the algebra, analogies can be easily made to the other fields, such as spectrometry and hyperspectral imaging.

In the field of lighting, an object is viewed and measured from a fixed location. In each measurement, the object is irradiated from a different direction, by a radiation source. Under this irradiance, the object is imaged. Consider a setup of N radiation sources. Let i=(i 1, i 2, …, iN)t be the set of image irradiance values, at a certain pixel. Each element in i corresponds to irradiance by any individual source in this setup. Here t denotes transposition.

In general, several sources can be turned on in each measurement (multiplexing). Define an N×N multiplexing matrix W, referred to as a multiplexing code. Each element of its m’th row represents the normalized radiance of a source in the m’th measurement. The radiance of a source is normalized relative to its maximum value. Hence, an element value of 0 states that the source is completely off, while 1 indicates a fully activated source. The sequential measurements acquired at a detector are denoted by the vector a=(a 1,a 2,…,aN)t, given by

a=Wi+υ.

Here υ is the measurement noise. Any bias to this noise is assumed to be compensated for. Let the noise υ be uncorrelated in different measurements, and let its variance be σ2 a.

Once measurements have been acquired under multiplexed sources, those measurements are de-multiplexed computationally. This derives estimates for the irradiance values of the object under the individual radiation sources î. The best unbiased linear estimator in the sense of mean square error (MSE) for the irradiance corresponding to the individual-sources is

î=W1a.

The MSE of this estimator [9, 18] is

MSEî=σa2Ntrace[(WtW)1].

This is the expected noise variance of the recovered sources. In this paper we pursue the problem of finding a multiplexing code W that maximizes the SNR of î, or, equivalently, minimizes MSEî. Specifically, we seek a lower bound on Eq. (3) and derive conditions on W to attain this bound, hence minimizing MSEî.

2.2. Eigenvalues and singular values

In this section we briefly review elementary definitions and results from linear algebra that will later be used for our analysis.

Definition Let Λ={λf}Nf =1 be the set of the eigenvalues (EVs) of a matrix W. The multiplicity of λf∊Λ is the number of repetitions of the value λf in Λ.

Lemma 1. If R and Q are matrices such that RQ is a square matrix, then [27]

trace(RQ)=trace(QR).

Lemma 2. Let W be a non-singular N×N matrix. Its EVs are λ1≤ … ≤λN. Then (See for example Ref. [28])

i)

trace(W)=f=1Nλf.

ii) The EVs of W -1 are λ -1 N ≤ … ≤λ-1 1.

Definition Let µ 1 ≤ µ2 ≤ … ≤ µN be the EVs of W t W. Then, the singular values (SVs) of W, {ξf}Nf =1 are defined as

ξf=μf.

Note that if W is symmetric, then W t W=W 2 and

ξm=λmm.

Ref. [29] quotes the following theorem.

Theorem 1. (Weyl-Horn)

m=fNξmm=fNλmf{2,,N}

and

m=1Nξm=m=1N|λm|.

2.3. Strongly regular graphs

We now refer to some elementary definitions from graph theory. We will use them when seeking optimal solutions to the multiplexing problem. We quote some basic definitions from Ref. [30].

Consider a graph G=(V,E), where V is a set of N vertices. Here E is the set of edges connecting a pair of vertices.

Definition Two vertices p,q are said to be adjacent or neighbors if they are connected by an edge.

Definition The N×N adjacency matrix Ω of the graph G is composed of elements

ωp,q={1ifpandqareneighbors0otherwise

Definition The complement of a graph G is a graph where its adjacency matrix of Ω¯ , is composed of elements

ω̅p,q={1ifωp,q=0andpq0otherwise.

Definition If all the vertices of G have the same number of neighbors k, then G is k-regular. In this case

q=1Nωp,q=kp.

Definition A strongly regular graph (SRG) [31] with parameters (N;k;α;β) is a k-regular graph that has the following properties:

’ Any two adjacent vertices have exactly α common neighbors (neighbors of both vertices).

∙ Any two non-adjacent vertices have exactly β common neighbors.

For example, consider the graph in Fig. 1. The adjacent vertices 5 and 10 have no common neighbors and this relation also applies to all the other adjacent pairs in the graph. Hence, here α=0. Moreover, vertices 5 and 3 have a single common neighbor, 9, and so are all other analogous pairs. Hence, here β=1.

 

Fig. 1. An example of a strongly regular graph (Peterson) [31]. This graph has the parameters (N=10;k=3;α=0;β=1).

Download Full Size | PPT Slide | PDF

Theorem 2. The parameters (N;k;α;β) of a strongly regular graph satisfy [31] the constraint

k(kα1)=(Nk1)β.

In the following, we make use of a theorem due to Seidel [32]:

Theorem 3. Let G be an SRG with parameters (N;k;α;β). Its adjacency matrix Ω has generally three distinct EVs,

λ1Ω=(αβ)+Δ2
λ2Ω=(αβ)Δ2
λ3Ω=k,

where,

Δ(αβ)2+4(kβ).

The multiplicity of λ Ω 3 is 1.

From Eq. (10), Ω is symmetric. Thus, Eq. (7) applies to the SVs of Ω.

ξfΩ=λfΩf.

Since the EVs of Ω indicate its SVs, Theorem 3 can be applied to the SVs of Ω. In particular, the multiplicity of EVs in Theorem 3 generally applies to the SVs of Ω.

3. Optimal power-regulated multiplexing

3.1. Problem formulation

We now seek multiplexing codes that minimize MSEî under the constraint of a fixed irradiance of an object in each measurement. Such a constraint is desired to avoid saturation of the detector. In saturation, the number of electrons generated in the detector exceeds the capacity of the circuitry that translates it into gray levels. The property of a fixed power is useful for other reasons, such as curbing photon noise, as we shall detail later.

To better express the fixed irradiance constraint, we define the variable C. It is the effective number of radiation sources used in each measurement. This unit-less variable is equivalent to the total radiant power used in a measurement. For example, in Hadamard-based codes,

C=CHadN+12.

Fixing the scalar C is equivalent to restricting the power emitted jointly by all sources. Suppose that a multiplexing code W is suggested, such that the irradiance by all the sources exceeds the pre-set threshold. Then this code cannot be used: it yields to much radiation. For example, in a system where saturation occurs if C is greater than Csat=N/5, Hadamard multiplexing cannot be used, since C Had exceeds C sat in this case.

If W violates the fixed-power constraint, what can be done? A trivial way is to equally reduce the power of each of the sources. However, refs. [18, 22] proved that such a step should be avoided. A better solution is to modify W, such that its corresponding C would comply with the constraint. Such a modification, however, is not easy to accomplish. The reason is that current codes in the literature [9, 23] do not support multiplexing of an arbitrary number C out of N sources. Specifically, Hadamard codes are too limited: according to Eq. (19), these codes totally couple C to N. This raises the need to extend the set of multiplexing codes, to comply with a general constraint on the effective number of simultaneously activated sources C.

Power is fixed by setting

s=1Nwm,s=Cm{1,2,,N}.

Recall that each source can be activated with some portion of its maximum power, i.e.

0wm,s1m,s{1,2,,N}.

We use Eq. (3) to formulate a minimization task of MSEî. To simplify the analysis, we slightly modify the problem for the moment, and define the cost function

MSE˜MSEîσa2=1Ntrace[(WtW)1].

Minimizing MSE˜ is equivalent to minimizing MSEî, if σ2 a is constant. The influence of σ2 a will be discussed in Sec. 7.

The constraints for our problem are taken from Eqs. (20,21). Thus, the optimization problem is

minWMSE˜minW1Ntrace[(WtW)1]
s.t.s=1Nwm,sC=0m{1,,N}
wm,s0m,s{1,,N}
wm,s10m,s{1,,N}.

We shall now derive sufficient conditions for a matrix W to solve Eqs. (23,24,25,26).

3.2. Conditions for a global optimum

A numerical procedure has been tailored to the optimization problem (23) in Ref. [22]. It is preferable however, to reach a closed-form solution, if it exists. This is done by deriving sufficient conditions for the optimality of a given W. Such conditions allow us to identify an optimal solution to the problem, if a potential solution is encountered. Indeed, later on in Sec. 6 we show that these conditions are satisfied by matrices W originally developed in graph theory. We can also apply these conditions to verify if a matrix reached by numerical optimization is indeed the global optimum.

Our approach for deriving the optimality conditions is as follows: first, we find a tight lower bound on MSE˜. Then, we formulate a necessary and sufficient condition to attain this bound. Finally, we minimize the bound itself, with respect to the elements of W.

3.2.1. The cost as a function of singular values

First, we express Eq. (23) in terms of the SVs of W. Recall from definition 2.2 that µ 1 ≤ … ≤ µN are the EVs of W t W. Then using, Lemma 2,

MSE˜1Ntrace[(WtW)1]=1Nf=1N1μf,

Thus, in light of Eq. (6).

μfξf2f{1,,N}.

We show an implication of constraints (24,25,26) on the SVs of W. This will allow us to better streamline (24,25,26) into Eq. (27), forming a lower bound on MSE˜. To understand the connection between these constraints and the SVs of W, we cite the following theorem [33]:

Theorem 4. Let W be constrained by Eqs. (24,25,26). Then, C is an EV of W. Furthermore, let λf be an EV of W. Then, |λf|≤C. The proof is given in App. A.

Theorem 4 deals with the EVs of W. This has an implication to its corresponding SVs, which are used in (27). This implication stems from Theorem 1. Let us set f=N in Eq. (8). Then,

ξNλN.

Now, following Theorem 4,

λN=C.

Hence, using Eqs. (28,29,30)

μNξN2C2.

Eq. (31) constrains the largest SV of W. Therefore, we separate it from the rest of the SVs in Eq. (27). The advantage of this move will be clarified shortly. Thus we rewrite Eq. (27) as

MSE˜=1NμN+1Nf=1N11μf.
 

Fig. 2. MSE˜ as a function of {µf}Nf=1. Each green dot marks the vector μ that minimizes MSE˜, when S is fixed. The highlighted line marks the ideal value of S. The green dot along this line marks the global minimum of MSE˜. This global minimum is derived in closed form and is thus unaffected by local minima.

Download Full Size | PPT Slide | PDF

3.2.2. Optimality of the singular values

In this paper we seek the tight lower bound on MSEî. To achieve this, we have first expressed MSE˜ by Eq. (32), in terms of the SVs of W. Define the vector μ =(µ 1,µ 2, …,µN). We now seek to minimize Eq. (32) as a function of μ . Apparently, MSE˜ in Eq. (32) is reduced if we simply increase any single element of μ , µf, while the rest are constant. Can we do this arbitrarily? The answer is no. The reason is that Eqs. (24,25,26) bound the domain of W, hence bounding the domain of its SVs. Therefore, any µf cannot be arbitrarily increased; the elements of μ are mutually coupled. To express the coupling, we first use a normalization, by defining

Sf=1Nμf

and setting it to be a constant. Later we alleviate the need for this arbitrary normalization (see Fig. 2).

Now, we show that under the constraint S≡Const,

minμN{1NμN+1Nf=1N11μf}=1NC2+1Nf=1N11μf.

To understand this observation consider Fig. 3. The minimization in Eq. (34) is only over the value of µ N. Let µ N be decreased by some small quantity Δµ N. Then, to conserve S in Eq. (33), the value of at least one other µf should increase. An increase of µ f by Δµ N reduces MSE˜. The reason is that the change induced by this increase is

ΔMSE˜=MSE˜μfΔμN=1Nμf2ΔμN<0.

We seek the strongest reduction of MSE˜. Clearly, in Eq. (35), the reduction MSE˜ is strongest if µ f is the smallest element of the set {µf}N-1 f=1. The smallest element in this set is µ1. Overall, decreasing µN by ΔµN while increasing µ1 by ΔµN yields a net reduction of MSE˜ by

ΔMSE˜=ΔμNN(1μ121μN2)<0.

Thus, trading µN for µ1 delivers a net benefit in MSE˜.

 

Fig. 3. The curve 1/µ represents elements summed in Eq. (34). The black dashed lines mark a state of the SVs of W. If the largest squared-SV, µN, is reduces by Δµ N and in return the smallest squared-SV, µ 1, is increased by Δµ N, the sum in Eq. (34) is reduced.

Download Full Size | PPT Slide | PDF

Since a benefit stems from a reduction of µN, then µN should be as low as possible. From Eq. (31), the lowest possible value of µN is C 2. To conclude,

Corollary 1.In an optimal multiplexing code W, the largest SV satisfies

ξN=C

i.e.,

μN=C2.

This proves Eq. (34).

After determining µN, we turn to the other elements of μ . A trivial manipulation yields

1Nf=1N11μfN1N(1N1f=1N11μf).

The parentheses on the right hand side of (39) express the reciprocal harmonic mean of {µf}N-1 f=1. The inequality of means [34] states that:

1N1f=1N11μfN1f=1N1μf.

Using Eqs. (33,38) in Eq. (40) yields,

1N1f=1N11μfN1SC2.

Combining Eqs. (34,39,41) into (32) yields

MSE˜B,

while B is the lower bound of MSE˜, given by

B=1NC2+(N1)2N(SC2).

The lower bound B is constant as long as S is fixed. We wish that MSE˜ will actually attain this fixed lower bound. Equality in Eq. (42) is obtained if equality holds in (40). This occurs when {µf}N-1 f=1 are all equal. Therefore, using Eq. (6), the elements of the set {ξf}N-1 f=1 are also equal. We recap with the following corollary.

Corollary 2. An ideal multiplexing matrix W is such, that all its SVs (but the largest one) {ξf}N-1 f=1 are equal to each other. Its largest SV equals C.

Note that we refer to matrices that attain the lower bound B as ideal. It is not guaranteed however, that such matrices exist for all values of N andC. Matrices that minimize MSE˜ without reaching B are simply referred to as optimal.

3.2.3. The ideal variable S

We have shown in Sec. 3.2.2 that for a specific S, the MSE is minimized by matrices that comply with the terms in Corollary 2. We now relieve the constraint of an arbitrarily fixed S. Hence, S may vary (see Fig. 2). Furthermore, we derive the best value for S. This yields a condition on the elements of W. Following Lemma 1,

trace(WtW)=trace(WWt).

The diagonal elements of WW t are

(WWt)m,m=s=1N(wm,s)2.

Due to Eq. (21),

(wm,s)2wm,s.

From Eqs. (20,45,46),

(WWt)m,ms=1Nwm,s=C.

Following Lemma 2,

S=k=1Nμk=trace(WtW).

From Eqs. (44,47,48),

S=trace(WWt)=m=1N(WWt)m,mNC.

As indicated earlier in this section, S may vary. From Eq. (49) the domain of S is

0SNC.

Now it is possible to find the global optimum in this domain. From Eq. (43), B is minimized by using the largest S possible. Hence,

Sideal=NC.

Note that equality holds in (49) if and only if equality also holds in Eq. (46). Trivially, this happens if all elements of W are either 1’s or 0’s. In this case Eq. (49) yields Eq. (51), alleviating the need for an arbitrarily fixed S.

From Eqs. (43,49,51)

BBmin

where

Bmin(C)=[1NC2+(N1)2N(NCC2)].

Equality holds if wm,s∊{0,1}∀m, s. In other words, B reaches its lowest potential value B min(C), if S is given by Eq. (51).

Corollary 3. The lower bound B min of MSE˜ is achieved using binary multiplexing matrices W.

Combining Corollary 3 and Eq. (20) results in

Theorem 5. MSE˜ yields B min only if C∊ℤ +.

We now combine the results of Corollaries 2 and 3. From Eqs. (3,42,43,52,53),

MSEîσa2Bmin(C).

Theorem 6. Equality in Eq. (54) is obtained by a matrix W, if and only if this matrix complies with both Corollaries 2 and 3.

The result in Eqs. (53,54) is very useful. Being a tight bound, B min determines the behavior of MSEî as a function of both N and C. Furthermore, if W satisfies the optimality conditions, then σ2 a B min is exactly the expected value of MSEî. In Fig. 4 we illustrate the behavior of B min for a specific value of N and a range of values of C.

 

Fig. 4. The bound B min(C), for N=63. Here C varies from 1 to 63. The minimum of B min(C) is at C opt. There may exist C sat, above which saturation occurs, inhibiting multiplexing.

Download Full Size | PPT Slide | PDF

4. The case of a free variable C

Sec. 3 dealt with power-regulated multiplexing, i.e., a fixed C. It introduced the lower bound on MSEî for all pairs of {N,C}, via Eqs. (53,54). However, what happens if C is a free variable in the domain C∊[1,N]? For a given N, which value of C∊[1,N] minimizes MSEî? This is discussed in this section.

The variable MSEî is influenced by C through three mechanisms.

1. The parameterC affects the EVs of the optimal W. This effect is reflected in the presence of C in the term for the bound B min (see Eq. 53).

2. The parameter C may not be free to vary through all the domain [1,N] due to saturation. There may exist C sat such that ∀C>C sat, elements of the vector a (Eq. 1) become saturated. Such elements of a prevent the correct reconstruction of î by Eq. (2).

3. The parameterC may affect σa in Eq. (3). So far in this paper, there was no consideration of variations in σa with respect to C. We shall see in Sec. 7 that this is often not the case, e.g. due to photon noise.

This section accounts only for mechanism 1, when discussing the optimal value of C. The other mechanisms are discussed in later sections. This allows the current section to compare our results to prior codes that do not consider mechanisms 2 and 3 as well, specifically, Hadamard codes [9, 18].

4.1. Minimization of Bmin

Recalling Sec. 3.1, if C is free to vary, then optimal matrices W are based on the Hadamard matrices and are known as the S-matrices [9]. These matrices indeed comply with the conditions of Theorem 6. However, S-matrices exist only for a subset of the possible values of N.

Define the domain

Ψ{[1,N]+}.

In this domain, the value of the variable C that minimizes Eq. (53) is defined as

CoptfreeargminCΨBmin(C).

Generally, C free opt is not an integer. If it is not an integer, then it does not satisfy Theorem 5. Hence, this value does not correspond to a multiplexing matrix that meets the bound B min(C free opt). Nevertheless, Cfreeopt is important: it may imply an integerC (close to C free opt) that is associated with an ideal multiplexing matrix.

To find C opt, let us null the derivative of B min(C) (Eq. 53) with respect to C,

BminC2NC3(N1)2(N2C)N(NCC2)2=0.

Nulling Eq. (57) yields

Coptfree=N22N3±(N1)(N22N+9)4N8.

Apparently, Eq. (58) has two solutions. However, only one of them is in Ψ. Hence, C free opt is unique. To satisfy Theorem 5, only integer C can be used. Let us define

CoptintROUND(Coptfree)

as the integer value that is closest to C opt. Define the integer domain

Ψint{[1,N]+}.

We wish to know if C int opt satisfies

Coptint=argminCΨintBmin(C).

This is discussed next.

4.2. Consistency with Hadamard matrices

Now we show that C int opt degenerates to C Had. It can be shown that

CHadCoptfree=N1N2.N+1(N1)2+84.

From Eq. (62), it can be shown that

limN(CHadCoptfree)=0.5.

More generally, as shown in Fig. 5,

CHad>Coptfree>CHad0.5.

Applying Eq. (59) in Eq. (64),

Coptint=CHad,

for values of N that correspond to S matrices. This is consistent with Ref. [9], which proves the optimality of Hadamard based-codes. Hence, Eq. (61) indeed holds in these cases.

Let us interpret our results:

∙ Hadamard-based codes are special cases, which satisfy our analysis. Their value of MSE˜ attains B min(C Had).

Eq. (61) is satisfied by Hadamard-based codes.

∙ Our analysis generalizes theories that were previously developed for multiplexing. In particular, the analysis applies to cases (values of {N,C}) for which Hadamard-based codes do not exist.

We wish to clarify that optimal multiplexing codes do not necessitate an integer C. When the condition specified in Theorem 5 is not met, then BB min. Thus, for a non-integer C, no matrix W is ideal, but a certain W can still be optimal, i.e. minimizing MSE˜ within constraints (24,25,26).

 

Fig. 5. A semi-logarithmic plot of Eq. (62).

Download Full Size | PPT Slide | PDF

5. Saturation

From Sec. 4, recall mechanism 2 by which C influences MSEî. It is saturation. Due to saturation, C cannot exceed C sat. In this section we discuss seeking an optimal value of C, under the saturation constraint.

The unsaturated domain of C is

Ψsat={Ψ[1,Csat]},

where Ψ is defined in Eq. (55). We seek the value

Coptsat=argminCΨsatBmin(C).

Let us discuss two cases. First, suppose that C free optC sat, where C free opt is defined in Eq. (58). In this case, C free opt∊Ψsat. Since C free opt uniquely minimizes Eq. (53) in this domain, the optimal solution degenerates to that described in Sec. 4.1.

In the second case, C free opt>C sat, i.e, C free opt/∊Ψsat. Then, there is no value of C∊Ψsat at which the derivative of B min(C) is null. Hence, the global minimum of the function B min(C) is obtained at the constraint C sat. This is illustrated, for example, in Fig. 4. To conclude,

Coptsat={CoptfreeifCoptfreeCsatCsatotherwise.

6. Some ideal solutions

Sec. 3 derived a lower bound on MSE˜, which can be obtained by multiplexing. Sec. 3 also shows that in order to attain this bound, certain conditions should be satisfied by the multiplexing code. However, it is not obvious that such ideal codes exist. The familiar Hadamard-based S matrices are ideal codes. Their value of MSE˜ attains B min(C Had). Are there other matrices, that satisfy these optimality conditions, for other values of {N,C}? In the following, we show that indeed there is a class of such matrices.

6.1. Strongly regular graphs as a solution

The adjacency matrix Ω described in Theorem 3 can be used as the desired multiplex matrix W, sought in Sec. 3, as we now detail:

∙ Since Ω is an adjacency matrix, it is binary. Hence, it satisfies Corollary 3.

∙ The highest SV of the desired Wis C, with multiplicity which is generally 1 (See Corollary 2). Similarly, the highest SV of Ω is k, with the same multiplicity. Hence, we set k=C.

∙ Setting the parameters α=β in Eqs. (14,15) yields λ1Ω=λ2Ω=Δ2. Using Eq. (18), all SVs of Ω are equal to Δ2, except for the largest SV, which equals k. Namely,

ξ1Ω=Cβ
ξ2Ω=C.

Therefore, Ω satisfies the conditions of Corollary 2. To summarize,

Theorem 7. Let Ω be the adjacency matrix of a (N;C;α;α) strongly regular graph. Then, Ω is an ideal matrix W solving Eqs. (23,24,25,26).

Recall that an SRG is subject to a constraint given in Eq. (13) on the values of its parameters. If α=β as in Theorem 7, then Eq. (13) takes the following form

α=k(k1)(N1)=C(C1)(N1).

As an example, consider the (45; 12; 3;3) SRG, described in Refs. [3537]. This is a class of graphs, determined up to an isomorphism. The adjacency matrix of a representative of this class is shown as a binary image in Fig. 6. Note that the parameters of this graph satisfy Eq. (70). Additional examples for SRGs can be found in [36, 37].

6.2. Solutions from complement graphs

In Sec. 6.1 we have devised a set of solutions for the sought optimal W. Such a set may be derived indirectly from another set of SRGs. Refs. [31, 35] formalize the following theorem:

Theorem 8. A graphG is strongly regular with parameters (N;k;α;β) if and only if its complement Ḡ is also strongly regular, with parameters (N ;N-k-1;N-2k+β-2;N-2k+α).

Theorem 8 means that given an SRG, with some parameters (N; C̄;α^ ;α¯+2), there exists a complement SRG, G, with parameters (N;C;α;α). Here C=N-C̄-1 and α=N-2C̄+α¯. Hence, using Theorem 7, G is a solution for Eqs. (23,24,25,26).

6.3. A simulated example

To illustrate the use of an SRG in multiplexing, we describe a simulation of spectrometry. The vector i represents noiseless graylevel measurements, where each element of the array expresses the radiance in a narrow spectral band, as transmitted through the atmosphere. As “ground-truth” i, we took the data in [38]. These graylevel values are plotted in Fig. 7a.

 

Fig. 6. An example for an adjacency matrix of an SRG with parameters (45; 12; 3;3) developed by Ref. [35]. Here 1s and 0s are represented by white and black squares, respectively. Here α=β=3, hence this graph satisfies the conditions of Theorem 7.

Download Full Size | PPT Slide | PDF

We simulated noisy infrared measurements of these values. They were compounded by Gaussian white noise, having σa=8 graylevels independent of the signal, and quantized by an 8-bit camera, having a range of [0,255] graylevels. The resulting absolute error |î-i| for this trivial measurement process is plotted by a red line in Fig. 7b.

Then, we simulated spectral multiplexing based on an SRG. In this data, N=45. Thus, we used the adjacency matrix shown in Fig. 6 for multiplexing the spectral bands. Thus, in each measurement, 12 narrow spectral bands were simultaneously sensed. Then, noise and quantization were applied as in the standard acquisition process. There was no saturation in a: considering the values i plotted in Fig. 7a, all elements of a were lower than 255 graylevels. The measurements were then demultiplexed, yielding a less noisy estimate î. The resulting absolute error |î-i| of the demultiplexed values is plotted by a green line in Fig. 7b. Indeed, the noise is significantly reduced. Quantitatively, the noise reduction is as expected: empirically, MSEî is 6.96 squared-graylevels, when averaged over many such randomly noised simulations. This is consistent with the expected theoretical value of MSEî, obtained by Eqs. (53,54).

7. Photon noise

In this section, we discuss mechanism 3 by which C influences MSEî, as mentioned in Sec. 4. Here we deal with the presence of photon noise in the acquired measurements. Generally, photon noise inhibits the multiplexing gain. The variance of photon noise increases linearly with the acquired signal. Hence, an increase of radiance used in each measurement increases the noise. This effect degrades the multiplexing gain, sometimes even causing it to be counterproductive [22, 24].

7.1. The affine noise model

As in [22], we use the affine noise model. It exists in high grade detectors, which have a linear radiometric response. The noise can be divided into two components, signal-dependent and signal-independent. Regardless of the photon flux, signal-independent noise is created by dark current [24, 39, 40], amplifier noise and the quantizer in the sensor circuity [40]. Denote the gray-level variance of the signal-independent noise by κ2 gray.

 

Fig. 7. (a) Graylevel spectral radiance of light transmitted through the atmosphere [38]. It is used to simulate the ground truth i. (b) Absolute error values |î-i| of simulated estimates based either on trivial sensing (red plot) or on SRG-based multiplexing (green plot).

Download Full Size | PPT Slide | PDF

Fundamental signal-dependent noise is related to two random effects. The photon flux and the uncertainty of the photon-electron conversion process which occurs in the detector. Overall, the random number n photo electr of photo-generated electrons is Poisson distributed [39, 41, 42]. In this distribution, the variance of n photo electr is

VAR(nelectrphoto)=(nelectrphoto),

where 𝓔denotes expectation. This variance linearly increases with the measured electric signal n photo electr. The number of detected electrons n photo electr is proportional to the gray-level of the acquired pixel value a

a=nelectrphotoQelectr.

Here Q electr is the number of photo-generated electrons required to change a unit gray-level. Typically Q electr≫1. Combining Eqs. (71,72) yields a variance in gray levels

(nelectrphoto)Qelectr2=aQelectr.

Compounded with signal-independent noise, the total noise variance of the measured gray-level [24, 39] is

σa2=κgray2+aQelectr.

Now, consider a scenario in which each radiation source, s yields a similar image radiance, is. Following Eqs. (1) and (20), in each measurement the acquired value is

aisC.

Thus Eq. (74) can be rephrased as

σa2=κgray2+Cη2.

Here η2is/Q electr is the photon noise variance, induced by i s. Eq. (76) is an affine function of the number of active sources C. This was demonstrated experimentally in Ref. [22]. The parameters κ2 gray and η2 depend on the setup hardware. A way to calibrate them is described in Ref. [22].

7.2. Optimal multiplexing

In this section we describe how to derive an optimal value of C, termed C final opt, accounting for all the effects. These include the various noise mechanisms and saturation. In addition, the section describes an approach to obtain a multiplexing matrix W that corresponds to C final opt.

From Eqs. (3,22),

MSEî=σa2MSE˜.

Embedding the noise variance of Eq. (76) into Eq. (77) yields

MSEî=(κgray2+Cη2)MSE˜.

Ref. [22] suggested a minimization of the MSEî expression given in Eq. (78). It consists of the following steps.

1. Scan the range of C values from 1 to C sat opt, where C sat opt is defined in Eq. (68). For each value of C, perform the subsequent steps 2 and 3.

2. Find the matrix W(C) that optimizes MSE˜, defined in Eq. (22). This optimization is constrained by (24,25,26).

3. Based on W(C), calculate the expected multiplex gain MSEî(C) using Eqs. (22,78).

4. Let

Coptfinal=argminCMSEî(C).

5. The desired multiplexing code is W(C final opt).

Note that the result of this process is a truly optimal multiplexing matrix, accounting for both saturation and photon-noise. Furthermore, in step 1, there is no necessity for exhaustive search of MSEî (C) for all C∊[1,C sat opt]. The reason is that MSEî (C) is well behaved [22], hence one can incorporate efficient optimization procedures. The core of the process is step 2. In Ref. [22], this minimization was based on a numerical search of MSE˜, i.e., of Eqs. (23,24,25,26). However, Eq. (22) is not unimodal. Hence, it is difficult to guarantee that a global minimum of MSE˜ is numerically reached.

Following Secs. 3 and 6 above, we may simplify step 2 in two ways. The first way is to create ideal multiplexing codes W(C) using adjacency matrices of known SRGs having the proper parameters (see Sec. 6). In this way, step 2 avoids numerical search altogether. However, SRGs are not available for every {N,C} set. Thus, numerical optimization may still be needed. Nevertheless, there is a second, more general way by which step 2 is simplified: B min(C) can set the termination of a numerical search, as is explained in the following.

Any numerical optimization process is iterative. Hence, let the above mentioned step 2 encapsulate an iterative process. At the l’th iteration, there is a matrix W l that complies with Eqs. (24,25,26). Based on Eq. (22), a corresponding value MSE˜l is derived. At iteration l+1, the multiplexing matrix changes to W l +1, with a corresponding MSE˜l+1. The numerical optimization seeks, in general, to yield MSE˜l+1<MSE˜l, hence minimizing MSE˜ as the iterations progress. A numerical minimization of MSE˜ can be efficient using a gradient-based method [22]. This is done since the gradient of MSE˜ (with respect to the elements of W l) is given in closed-form (See [22]).

In iterative optimization, an important matter is to know when to terminate it, i.e., at which l does W l yield MSE˜l that is indeed close enough to its true optimum? Here the conditions and bounds we obtained in Sec. 3.2 come into play. Specifically, B min(C) can terminate the iterations. If at the l’th iteration MSE˜lBmin(C), then the iterations may stop: W l is as good as it can get. Hence, it can be set as W(C) in step 2 above.

8. Discussion

We derived several lower bounds on the estimation error, in conjunction with conditions required to attain them. The bound B given in Eq. (43) determines best feasible performance by any code for which the sum of SVs is arbitrarily fixed. Correspondingly, Corollary 2 states the structure of desired codes. A stronger bound is B min(C), given by Eq. (53), as it states the best conceivable performance of any code, whatever its SVs are. However, finding a code that attains B min(C) is more difficult, since such a code is constrained to satisfy Eqs. (48,51). Such a constraint can only be satisfied by binary codes (Corollary 3). This lead to an interesting link to graph theory, which is usually a field distinct from analysis of intensity noise. We showed that SRG have adjacency matrices that are ideal, in the sense that they attain B min(C).

An important contribution is the algorithm described in Sec. 7.2. It exploits the performance bounds derived in the paper for a practical task: validating and influencing a numerical search for optimal multiplexing codes. These codes can have any number of sources N, activated sources C, and be tailored to the characteristics of noise and saturation.

The analysis of general matrices W is helpful to subcases of such matrices, be they binary [3,4,912,26] and/or cyclic [8, 9, 20, 23]. Furthermore, the analysis may be extended to noise models [24] that are different than Eq. (76).

We believe that these results are important to the wide range of fields where the multiplexing principle is used. The results can help yield measurement devices for estimating an arbitrary number of sought variables, where the measurement apparatus is optimal under fundamental and practical limitations and effects.

A. Proof of Theorem 4

To make the paper self-contained, we prove Theorem 4. This derivation is a variation of a proof that appears in [33]. Define

WoffsetWCI.

Let w offset m,s be the elements of W offset. Following Eq. (20),

s=1Nwm,soffset=0m{1,2,,N}.

Hence, one of the EVs of W offset is 0. In other words, det(W offset)=0. By the definition in (80), this means that det(W-C I)=0, i.e., C is an EV of W. This proves the first part of Theorem 4. Suppose that u f=(uf 1,…,ufN)t is an eigenvector corresponding to λf. Without the loss of generality, we may normalize u f, such that

maxm{1,,N}umf=1.

Hence,

umf=1

for a certain m∊{1,…,N}. From Eqs. (21,82)

wm,sumf1m,s{1,,N}.

Eqs. (20,84) directly lead to a constraint on the absolute value of the s’th component of Wu f.

(Wuf)m=s=1Nwm,susfs=1Nwm,susfC.

In addition, u f is an eigenvector of W. Hence,

(Wuf)m=λfufm=λfumf.

From Eq. (83), Eq. (86) becomes

(Wuf)m=λf.

Using Eq. (87) in (85) yields

λfC.

This proves the second half of Theorem 4.

Acknowledgments

Yoav Schechner is a Landau Fellow - supported by the Taub Foundation, and an Alon Fellow. The work was supported by the Israeli Ministry of Science, Culture and Sport (Grant 3-3426). It was conducted in the Ollendorff Minerva Center. Minerva is funded through the BMBF.

References and links

1. D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006). [CrossRef]  

2. W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002). [CrossRef]  

3. C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express 15:5742–5753 (2007). [CrossRef]   [PubMed]  

4. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006). [CrossRef]  

5. Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002). [CrossRef]  

6. G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE volume 5111, pages 273–282 (2003). [CrossRef]  

7. J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE volume 2599, pages 285–293 (1996). [CrossRef]  

8. E. E. Fenimore and T. M. Cannon. “Coded aparture imaging with uniformly redundent arrays.” Appl. Opt. 17:337–347 (1978). [CrossRef]   [PubMed]  

9. M. Harwit and N. J. A. Sloane. Hadamard Transform Optics. Academic Press, New York (1979).

10. T. M. Palmieri. “Multiplex methods and advantages in X-ray astronomy.” Astrophysics and Space Science 28:277–287 (1974). [CrossRef]  

11. R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).

12. G. K. Skinner. “X-ray imaging with coded masks.” Scientific American 259:84–89 (1988). [CrossRef]   [PubMed]  

13. A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

14. O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007). [CrossRef]  

15. K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005). [CrossRef]  

16. M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

17. F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005).

18. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).

19. A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

20. A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A 14(5):1058–1065 (1997). [CrossRef]  

21. E. E. Fenimore. “Coded aperture imaging: predicted performance of uniformly redundant arrays.” Appl. Opt. 17:3562–3570 (1978). [CrossRef]   [PubMed]  

22. N. Ratner and Y. Y. Schechner. “Illumination multiplexing within fundamental limits.” In Proc. IEEE CVPR (2007).

23. A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. 44:2710–2719 (2005). [CrossRef]   [PubMed]  

24. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007). [CrossRef]  

25. V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis 28:830–839 (1992). [CrossRef]  

26. Y. A. Shutova. “Optimization of binary masks for Hadamard-transform optical spectrometers”. J. Opt. Technol. 67:50–53 (2000). [CrossRef]  

27. C. D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM (2000). [CrossRef]  

28. R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge, New York (1985).

29. M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis 37(3):1004–1020 (2000). [CrossRef]  

30. R. Diestel. Graph Theory. Springer, 3rd edition (2000).

31. P. J. Cameron and J. H. V. Lint. Designs, Graphs, Codes, and Their Links. Cambridge University Press, New York, NY, USA (1991). [CrossRef]  

32. J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. 1:281–289 (1968). [CrossRef]  

33. W. Haemers. “Matrix techniques for strongly regular graphs and related geometries.” Intensive Course on Finite Geometry and its Applications, University of Ghent (2000).

34. M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997). [CrossRef]  

35. K. Coolsaet and J. Degraer. “The strongly regular (45,12,3,3) graphs.” Elec. Journ. Combin13(1) (2006).

36. T. Spence. “Strongly Regular Graphs on at most 64 vertices” http://www.maths.gla.ac.uk/es/srgraphs.html

37. G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html

38. P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html

39. S. Ioué and K. R. Spring. Video Microscopy, 2nd ed.ch. 6,7,8, Plenum Press, New York. (1997).

40. C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

41. F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).

42. H. H. Barrett and W. Swindell. Radiological Imaging, volume 1. Academic press, New York (1981).

References

  • View by:
  • |
  • |
  • |

  1. D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
    [CrossRef]
  2. W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
    [CrossRef]
  3. C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express 15:5742–5753 (2007).
    [CrossRef] [PubMed]
  4. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
    [CrossRef]
  5. Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002).
    [CrossRef]
  6. G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE volume 5111, pages 273–282 (2003).
    [CrossRef]
  7. J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE volume 2599, pages 285–293 (1996).
    [CrossRef]
  8. E. E. Fenimore and T. M. Cannon. “Coded aparture imaging with uniformly redundent arrays.” Appl. Opt. 17:337–347 (1978).
    [CrossRef] [PubMed]
  9. M. Harwit and N. J. A. Sloane. Hadamard Transform Optics. Academic Press, New York (1979).
  10. T. M. Palmieri. “Multiplex methods and advantages in X-ray astronomy.” Astrophysics and Space Science 28:277–287 (1974).
    [CrossRef]
  11. R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).
  12. G. K. Skinner. “X-ray imaging with coded masks.” Scientific American 259:84–89 (1988).
    [CrossRef] [PubMed]
  13. A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).
  14. O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
    [CrossRef]
  15. K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005).
    [CrossRef]
  16. M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).
  17. F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005).
  18. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).
  19. A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).
  20. A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A 14(5):1058–1065 (1997).
    [CrossRef]
  21. E. E. Fenimore. “Coded aperture imaging: predicted performance of uniformly redundant arrays.” Appl. Opt. 17:3562–3570 (1978).
    [CrossRef] [PubMed]
  22. N. Ratner and Y. Y. Schechner. “Illumination multiplexing within fundamental limits.” In Proc. IEEE CVPR (2007).
  23. A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. 44:2710–2719 (2005).
    [CrossRef] [PubMed]
  24. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007).
    [CrossRef]
  25. V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis 28:830–839 (1992).
    [CrossRef]
  26. Y. A. Shutova. “Optimization of binary masks for Hadamard-transform optical spectrometers”. J. Opt. Technol. 67:50–53 (2000).
    [CrossRef]
  27. C. D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM (2000).
    [CrossRef]
  28. R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge, New York (1985).
  29. M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis 37(3):1004–1020 (2000).
    [CrossRef]
  30. R. Diestel. Graph Theory. Springer, 3rd edition (2000).
  31. P. J. Cameron and J. H. V. Lint. Designs, Graphs, Codes, and Their Links. Cambridge University Press, New York, NY, USA (1991).
    [CrossRef]
  32. J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. 1:281–289 (1968).
    [CrossRef]
  33. W. Haemers. “Matrix techniques for strongly regular graphs and related geometries.” Intensive Course on Finite Geometry and its Applications, University of Ghent (2000).
  34. M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
    [CrossRef]
  35. K. Coolsaet and J. Degraer. “The strongly regular (45,12,3,3) graphs.” Elec. Journ. Combin13(1) (2006).
  36. T. Spence. “Strongly Regular Graphs on at most 64 vertices” http://www.maths.gla.ac.uk/es/srgraphs.html
  37. G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html
  38. P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html
  39. S. Ioué and K. R. Spring. Video Microscopy, 2nd ed.ch. 6,7,8, Plenum Press, New York. (1997).
  40. C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).
  41. F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).
  42. H. H. Barrett and W. Swindell. Radiological Imaging, volume 1. Academic press, New York (1981).

2007 (3)

O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
[CrossRef]

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007).
[CrossRef]

C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express 15:5742–5753 (2007).
[CrossRef] [PubMed]

2006 (4)

C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

2005 (3)

K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005).
[CrossRef]

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. 44:2710–2719 (2005).
[CrossRef] [PubMed]

2004 (2)

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

2003 (2)

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).

G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE volume 5111, pages 273–282 (2003).
[CrossRef]

2002 (2)

Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002).
[CrossRef]

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

2000 (2)

Y. A. Shutova. “Optimization of binary masks for Hadamard-transform optical spectrometers”. J. Opt. Technol. 67:50–53 (2000).
[CrossRef]

M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis 37(3):1004–1020 (2000).
[CrossRef]

1997 (2)

M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
[CrossRef]

A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A 14(5):1058–1065 (1997).
[CrossRef]

1996 (1)

J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE volume 2599, pages 285–293 (1996).
[CrossRef]

1992 (1)

V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis 28:830–839 (1992).
[CrossRef]

1988 (1)

G. K. Skinner. “X-ray imaging with coded masks.” Scientific American 259:84–89 (1988).
[CrossRef] [PubMed]

1979 (1)

R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).

1978 (2)

1974 (1)

T. M. Palmieri. “Multiplex methods and advantages in X-ray astronomy.” Astrophysics and Space Science 28:277–287 (1974).
[CrossRef]

1968 (1)

J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. 1:281–289 (1968).
[CrossRef]

Alicacute, M.

M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
[CrossRef]

Alter, F.

F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).

Arndt-Jovin, D. J.

Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002).
[CrossRef]

Baraniuk, R. G.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Baron, D.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Barrett, H. H.

H. H. Barrett and W. Swindell. Radiological Imaging, volume 1. Academic press, New York (1981).

Belhumeur, P. N.

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007).
[CrossRef]

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).

F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005).

Bolas, M.

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

Brady, D. J.

C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express 15:5742–5753 (2007).
[CrossRef] [PubMed]

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

Bronstein, A. M.

A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

Bronstein, M. M.

A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

Busboom, A.

Cameron, P. J.

P. J. Cameron and J. H. V. Lint. Designs, Graphs, Codes, and Their Links. Cambridge University Press, New York, NY, USA (1991).
[CrossRef]

Cannon, T. M.

Chen, B.

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

Chu, M. T.

M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis 37(3):1004–1020 (2000).
[CrossRef]

Coifman, R. R.

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

Coolsaet, K.

K. Coolsaet and J. Degraer. “The strongly regular (45,12,3,3) graphs.” Elec. Journ. Combin13(1) (2006).

Cula, O. G.

O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
[CrossRef]

Dana, K. J.

O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
[CrossRef]

Debevec, P.

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Degraer, J.

K. Coolsaet and J. Degraer. “The strongly regular (45,12,3,3) graphs.” Elec. Journ. Combin13(1) (2006).

DeVerse, R. A.

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

Diestel, R.

R. Diestel. Graph Theory. Springer, 3rd edition (2000).

Duarte, M. F.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Elders-Boll, H.

Fateley, W. G.

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

Fenimore, E. E.

Fernandez, C.

Freeman, W. T.

C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

Gardner, A.

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Geballe, T.

P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html

Gehm, M. E.

C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express 15:5742–5753 (2007).
[CrossRef] [PubMed]

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

Geshwind, F. B.

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

Gordon, E.

A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

Guenther, B. D.

Haemers, W.

W. Haemers. “Matrix techniques for strongly regular graphs and related geometries.” Intensive Course on Finite Geometry and its Applications, University of Ghent (2000).

Hammaker, R. M.

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

Hanley, Q. S.

Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002).
[CrossRef]

Harwit, M.

M. Harwit and N. J. A. Sloane. Hadamard Transform Optics. Academic Press, New York (1979).

Hawkins, T.

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Ho, J.

K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005).
[CrossRef]

Horn, R. A.

R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge, New York (1985).

Horowitz, M.

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

Ioué, S.

S. Ioué and K. R. Spring. Video Microscopy, 2nd ed.ch. 6,7,8, Plenum Press, New York. (1997).

Johnson, C. R.

R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge, New York (1985).

Jovin, T. M.

Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002).
[CrossRef]

Kang, S. B.

C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

Kelly, K. F.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Kimmel, R.

A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

Kozlov, V. P.

V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis 28:830–839 (1992).
[CrossRef]

Kriegman, D. J.

K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005).
[CrossRef]

Laska, J. N.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Lee, K. C.

K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005).
[CrossRef]

Levoy, M.

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

Lint, J. H. V.

P. J. Cameron and J. H. V. Lint. Designs, Graphs, Codes, and Their Links. Cambridge University Press, New York, NY, USA (1991).
[CrossRef]

Liu, C.

C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

Matsushita, Y.

F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).

McCain, S. T.

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

McDowall, I.

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

Meyer, C. D.

C. D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM (2000).
[CrossRef]

Mond, B.

M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
[CrossRef]

Moreno-Noguer, F.

F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005).

Nayar, S. K.

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007).
[CrossRef]

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).

F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005).

Nitzsche, G.

G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE volume 5111, pages 273–282 (2003).
[CrossRef]

Pai, D. K.

O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
[CrossRef]

Palmieri, T. M.

T. M. Palmieri. “Multiplex methods and advantages in X-ray astronomy.” Astrophysics and Space Science 28:277–287 (1974).
[CrossRef]

Pecbreve aricacute, J.

M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
[CrossRef]

Pitsianis, N. P.

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

Potuluri, P.

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

Proctor, R. J.

R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).

Puxley, P.

P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html

Ratner, N.

N. Ratner and Y. Y. Schechner. “Illumination multiplexing within fundamental limits.” In Proc. IEEE CVPR (2007).

Riesenberg, R.

G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE volume 5111, pages 273–282 (2003).
[CrossRef]

Royle, G.

G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html

Sarvotham, S.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Schechner, Y. Y.

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007).
[CrossRef]

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).

N. Ratner and Y. Y. Schechner. “Illumination multiplexing within fundamental limits.” In Proc. IEEE CVPR (2007).

Schotten, H. D.

Sedunov, E. V.

V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis 28:830–839 (1992).
[CrossRef]

Seidel, J. J.

J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. 1:281–289 (1968).
[CrossRef]

Shutova, Y. A.

Skinner, G. K.

G. K. Skinner. “X-ray imaging with coded masks.” Scientific American 259:84–89 (1988).
[CrossRef] [PubMed]

R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).

Sloane, N. J. A.

M. Harwit and N. J. A. Sloane. Hadamard Transform Optics. Academic Press, New York (1979).

Spence, T.

T. Spence. “Strongly Regular Graphs on at most 64 vertices” http://www.maths.gla.ac.uk/es/srgraphs.html

Spring, K. R.

S. Ioué and K. R. Spring. Video Microscopy, 2nd ed.ch. 6,7,8, Plenum Press, New York. (1997).

Sullivan, M. E.

C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express 15:5742–5753 (2007).
[CrossRef] [PubMed]

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. 43:2965–2974 (2006).
[CrossRef]

Swindell, W.

H. H. Barrett and W. Swindell. Radiological Imaging, volume 1. Academic press, New York (1981).

Szeliski, R.

C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

Takhar, D.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Tang, X.

F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).

Tchou, C.

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Treado, P. J.

J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE volume 2599, pages 285–293 (1996).
[CrossRef]

Turner, J. F.

J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE volume 2599, pages 285–293 (1996).
[CrossRef]

Unger, J.

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Vaish, V.

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

Volenec, V.

M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
[CrossRef]

Wakin, M. B.

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

Wang, D.

O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
[CrossRef]

Wenger, A.

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Willmore, A. P.

R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).

Wuttig, A.

ACM TOG (2)

M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG 23:825–834 (2004).

A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG 24:756–764 (2005).

Appl. Opt. (4)

Appl. Spectrosc. (1)

Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. 56:63–84 (2002).
[CrossRef]

Astrophysics and Space Science (1)

T. M. Palmieri. “Multiplex methods and advantages in X-ray astronomy.” Astrophysics and Space Science 28:277–287 (1974).
[CrossRef]

Cybernetics and Systems Analysis (1)

V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis 28:830–839 (1992).
[CrossRef]

IEEE Trans. PAMI (3)

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI 29:1339–1354 (2007).
[CrossRef]

O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI 29:362–367 (2007).
[CrossRef]

K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI 27:684–698 (2005).
[CrossRef]

In Proc. CVPR (1)

C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR Vol. 1 pages 901–908 (2006).

In Proc. ECCV (1)

F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV Vol. 4, pages 267–280 (2006).

In Proc. IEEE ICCV (1)

Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV Vol. 2, pages 808–815 (2003).

In Proc. IEEE ICIP (1)

A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP Vol. 1, pages 87–90 (2004).

In Proc. SPIE (3)

G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE volume 5111, pages 273–282 (2003).
[CrossRef]

J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE volume 2599, pages 285–293 (1996).
[CrossRef]

D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE volume 6065 (2006).
[CrossRef]

J. Opt. Soc. Am. A (1)

J. Opt. Technol. (1)

Linear Algebra and its Applications (1)

M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications 264(1):55–62 (1997).
[CrossRef]

Linear Algebra Appl. (1)

J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. 1:281–289 (1968).
[CrossRef]

Opt. Express (1)

Royal Astronomical Society, Monthly Notices (1)

R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices 187:633–643 (1979).

Scientific American (1)

G. K. Skinner. “X-ray imaging with coded masks.” Scientific American 259:84–89 (1988).
[CrossRef] [PubMed]

SIAM J. on Numerical Analysis (1)

M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis 37(3):1004–1020 (2000).
[CrossRef]

Vib. Spectrosc. (1)

W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. 29:163–170 (2002).
[CrossRef]

Other (14)

N. Ratner and Y. Y. Schechner. “Illumination multiplexing within fundamental limits.” In Proc. IEEE CVPR (2007).

C. D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM (2000).
[CrossRef]

R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge, New York (1985).

M. Harwit and N. J. A. Sloane. Hadamard Transform Optics. Academic Press, New York (1979).

F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005).

R. Diestel. Graph Theory. Springer, 3rd edition (2000).

P. J. Cameron and J. H. V. Lint. Designs, Graphs, Codes, and Their Links. Cambridge University Press, New York, NY, USA (1991).
[CrossRef]

W. Haemers. “Matrix techniques for strongly regular graphs and related geometries.” Intensive Course on Finite Geometry and its Applications, University of Ghent (2000).

K. Coolsaet and J. Degraer. “The strongly regular (45,12,3,3) graphs.” Elec. Journ. Combin13(1) (2006).

T. Spence. “Strongly Regular Graphs on at most 64 vertices” http://www.maths.gla.ac.uk/es/srgraphs.html

G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html

P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html

S. Ioué and K. R. Spring. Video Microscopy, 2nd ed.ch. 6,7,8, Plenum Press, New York. (1997).

H. H. Barrett and W. Swindell. Radiological Imaging, volume 1. Academic press, New York (1981).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1.
Fig. 1.

An example of a strongly regular graph (Peterson) [31]. This graph has the parameters (N=10;k=3;α=0;β=1).

Fig. 2.
Fig. 2.

MSE ˜ as a function of {µf } N f =1. Each green dot marks the vector μ that minimizes MSE ˜ , when S is fixed. The highlighted line marks the ideal value of S. The green dot along this line marks the global minimum of MSE ˜ . This global minimum is derived in closed form and is thus unaffected by local minima.

Fig. 3.
Fig. 3.

The curve 1/µ represents elements summed in Eq. (34). The black dashed lines mark a state of the SVs of W. If the largest squared-SV, µ N , is reduces by Δµ N and in return the smallest squared-SV, µ 1, is increased by Δµ N , the sum in Eq. (34) is reduced.

Fig. 4.
Fig. 4.

The bound B min(C), for N=63. Here C varies from 1 to 63. The minimum of B min(C) is at C opt. There may exist C sat, above which saturation occurs, inhibiting multiplexing.

Fig. 5.
Fig. 5.

A semi-logarithmic plot of Eq. (62).

Fig. 6.
Fig. 6.

An example for an adjacency matrix of an SRG with parameters (45; 12; 3;3) developed by Ref. [35]. Here 1s and 0s are represented by white and black squares, respectively. Here α=β=3, hence this graph satisfies the conditions of Theorem 7.

Fig. 7.
Fig. 7.

(a) Graylevel spectral radiance of light transmitted through the atmosphere [38]. It is used to simulate the ground truth i. (b) Absolute error values |î-i| of simulated estimates based either on trivial sensing (red plot) or on SRG-based multiplexing (green plot).

Equations (89)

Equations on this page are rendered with MathJax. Learn more.

a = W i + υ .
i ̂ = W 1 a .
MSE i ̂ = σ a 2 N trace [ ( W t W ) 1 ] .
trace ( RQ ) = trace ( QR ) .
trace ( W ) = f = 1 N λ f .
ξ f = μ f .
ξ m = λ m m .
m = f N ξ m m = f N λ m f { 2 , , N }
m=1 N ξ m = m=1 N | λ m |.
ω p , q = { 1 if p and q are neighbors 0 otherwise
ω ̅ p , q = { 1 if ω p , q = 0 and p q 0 otherwise .
q = 1 N ω p , q = k p .
k ( k α 1 ) = ( N k 1 ) β .
λ 1 Ω = ( α β ) + Δ 2
λ 2 Ω = ( α β ) Δ 2
λ 3 Ω = k ,
Δ ( α β ) 2 + 4 ( k β ) .
ξ f Ω = λ f Ω f .
C = C Had N + 1 2 .
s = 1 N w m , s = C m { 1 , 2 , , N } .
0 w m , s 1 m , s { 1 , 2 , , N } .
MSE ˜ MSE i ̂ σ a 2 = 1 N trace [ ( W t W ) 1 ] .
min W MSE ˜ min W 1 N trace [ ( W t W ) 1 ]
s . t . s = 1 N w m , s C = 0 m { 1 , , N }
w m , s 0 m , s { 1 , , N }
w m , s 1 0 m , s { 1 , , N } .
MSE ˜ 1 N trace [ ( W t W ) 1 ] = 1 N f = 1 N 1 μ f ,
μ f ξ f 2 f { 1 , , N } .
ξ N λ N .
λ N = C .
μ N ξ N 2 C 2 .
MSE ˜ = 1 N μ N + 1 N f = 1 N 1 1 μ f .
S f = 1 N μ f
min μ N { 1 N μ N + 1 N f = 1 N 1 1 μ f } = 1 N C 2 + 1 N f = 1 N 1 1 μ f .
Δ MSE ˜ = MSE ˜ μ f Δ μ N = 1 N μ f 2 Δ μ N < 0 .
Δ MSE ˜ = Δ μ N N ( 1 μ 1 2 1 μ N 2 ) < 0 .
ξ N = C
μ N = C 2 .
1 N f = 1 N 1 1 μ f N 1 N ( 1 N 1 f = 1 N 1 1 μ f ) .
1 N 1 f = 1 N 1 1 μ f N 1 f = 1 N 1 μ f .
1 N 1 f = 1 N 1 1 μ f N 1 S C 2 .
MSE ˜ B ,
B = 1 N C 2 + ( N 1 ) 2 N ( S C 2 ) .
trace ( W t W ) = trace ( W W t ) .
( W W t ) m , m = s = 1 N ( w m , s ) 2 .
( w m , s ) 2 w m , s .
( W W t ) m , m s = 1 N w m , s = C .
S = k = 1 N μ k = trace ( W t W ) .
S = trace ( W W t ) = m = 1 N ( W W t ) m , m N C .
0 S N C .
S ideal = N C .
B B min
B min ( C ) = [ 1 N C 2 + ( N 1 ) 2 N ( N C C 2 ) ] .
MSE i ̂ σ a 2 B min ( C ) .
Ψ { [ 1 , N ] + } .
C opt free arg min C Ψ B min ( C ) .
B min C 2 N C 3 ( N 1 ) 2 ( N 2 C ) N ( N C C 2 ) 2 = 0 .
C opt free = N 2 2 N 3 ± ( N 1 ) ( N 2 2 N + 9 ) 4 N 8 .
C opt int ROUND ( C opt free )
Ψ int { [ 1 , N ] + } .
C opt int = arg min C Ψ int B min ( C ) .
C Had C opt free = N 1 N 2 . N + 1 ( N 1 ) 2 + 8 4 .
lim N ( C Had C opt free ) = 0.5 .
C Had > C opt free > C Had 0.5 .
C opt int = C Had ,
Ψ sat = { Ψ [ 1 , C sat ] } ,
C opt sat = arg min C Ψ sat B min ( C ) .
C opt sat = { C opt free if C opt free C sat C sat otherwise .
ξ 1 Ω = C β
ξ 2 Ω = C .
α = k ( k 1 ) ( N 1 ) = C ( C 1 ) ( N 1 ) .
VAR ( n electr photo ) = ( n electr photo ) ,
a = n electr photo Q electr .
( n electr photo ) Q electr 2 = a Q electr .
σ a 2 = κ gray 2 + a Q electr .
a i s C .
σ a 2 = κ gray 2 + C η 2 .
MSE i ̂ = σ a 2 MSE ˜ .
MSE i ̂ = ( κ gray 2 + C η 2 ) MSE ˜ .
C opt final = arg min C MSE i ̂ ( C ) .
W offset W C I .
s = 1 N w m , s offset = 0 m { 1 , 2 , , N } .
max m { 1 , , N } u m f = 1 .
u m f = 1
w m , s u m f 1 m , s { 1 , , N } .
( W u f ) m = s = 1 N w m , s u s f s = 1 N w m , s u s f C .
( W u f ) m = λ f u f m = λ f u m f .
( W u f ) m = λ f .
λ f C .

Metrics