Thursday, September 27, 2012

Sampling Rate is Not Only about Pixels: How to compare the sampling rate between your camera and "single-pixel" camera

At the beginning, I'd like to make clear two terms: "Nyquist frequency" and "Nyquist rate".
Some of you may take them as the same thing, and even some textbooks did so. However, although they are quite similar, they are actually different.
Reference: http://en.wikipedia.org/wiki/Nyquist_frequency
Nyquist Frequency: A property of system. For a given system, sampling rate $f_s$ is fixed. The Nyquist frequency of the system is the allowed highest frequency of a signal that could be sampled without aliasing, which is $f_s / 2$.
Nyquist Rate: A property of signal. For a given band-limited or band-pass signal, bandwidth B is fixed. The Nyquist rate of the signal is the necessary lowest sampling frequency of a system that could sample the signal without aliasing, which is $2B$.

Then for an (imaging system, image signals), you can interpret the sampling rate is the number of pixels, the highest frequency of the image is the resolution of the image.
Then the Nyquist says here, for a imaging system, the number of pixels (sampling rate) is fixed, the highest allowed resolution of the pixel is determined by/proportional to the number of pixels. For different kinds of measure of resolution, the proportion factor differs.
Meanwhile, for an image signal, whose resolution (band-width) is fixed, the required pixels is then determined by/proportional to the resolution.

So the number of pixels is actually the number of samples a system takes for a given image.
Then does it mean "single-pixel" means the number of samples is 1? The answer is definitely no.
So how to interpret the "single"-pixel?

It's a little tricky, but still can be understood. The only thing you need to do is adding a time-axis.
The traditional imaging system in your cameras actually taking samples at one time, each sample is a pixel. So the total number of samples is (number of pixels in a unit of time) x (unit of time). Since the (unit of time) is 1 here, we usually ignore it.
For the "signal-pixel" camera, the number of samples is (number of pixels in a unit of time) x (unit of time). Here (the number of pixels in a unit of time) is 1, whereas the (unit of time) is not 1, which determines the number of samples.
Image sensors are silicon chips that capture and read light. So in traditional imaging system, we need thousands of image sensors, whereas in single pixel camera, we only use one image sensor to capture and read light.
That's the trade-off, number of pixels (image sensors) and unit of time (exposure time).

Therefore, improved interpretation of Nyquist sampling here is to consider the sampling rate being (number of pixels in a unit of time) x (unit of time), i.e., the product of space sampling and time sampling.

How to understand "Nyquist sample v.s. CS"?

In this blog, I will discuss from a communication system point of view about the Nyquist sample and CS theory. A communication system usually samples and processes a 1D signal. So here we are talk about 1D signal cases.

What does Nyquist say for 1D signal?

As shown in the figure, for a analog signal, we need to first sample it to digital signal, and then process it, and de-sample/reconstruct it into analogy signal again.
Therefore, the "process" part is called digital signal processing (DSP).
The Nyquist sampling happens in the "sampling" part, before DSP.
Then what does Nyquist say?
That is, given a signal with the highest frequency component being $f_m$. The sufficient condition for return from the digital signal $x[n]$ to $x(t)$ is that the sampling frequency $f_s$ is at least $2f_m$.
It should be noticed that this is only a sufficient, not necessary condition.
In certain cases, the condition is necessary, e.g., the signal is band-limited. If the whole limited band is occupied by the signal, or we don't know which portion of band the signal occupied, in other words, the only information we've got is the highest frequency of the signal,
(we call this kind of signal strict-sense band-limited signal), then the only way is to use Nyquist rate to sample the signal.
However, you may argue that, in practice, the signal may not band-limited, then what should we do?
The answer is making the signal band-limited before we sample it. This can be done using a LPF. And it is another story that how the band-limited signal approximates the real signal. Here we only focused on the already band-limited signal.
On the other hand, you may also ask that, if we have a band-pass signal, (of course, the band-pass signal is a band-limited signal, however, not strict sense band-limited signal), then can we have lower sampling frequency.
The answer is yes. To see the method, just think we move the band-pass signal to the base-band, and then it become a strict-sense band-limited signal. Then it is obvious how Nyquist rate works. Actually, we are given more information, i.e., the signal is band-passed from $f_L$ to $f_H$, thus we are able to sample the signal using frequency below $2f_H$.
In this case, we can call such sampling process under-sampling. However, it can be viewed as Nyquist sampling via some conversion.

• It should also be noticed that here the sampling is uniform sampling. If you are interested in this topic, you can review some references in non-uniform sampling.
• Also, when it comes to 2D signal, it is a little tricky to see the Nyquist sampling. It's beyond this blog.

What does CS say?

Before we go into CS, I'd like to a more complete communication system.
As you see in the figure, all "information" after the dash line are in format of bits stream. And if we ignore all imperfection of the system in between, e.g. we have perfect channel, perfect modulation scheme. Then the process after dash line is distortion free.
Then we move before the dash line, as we shown in last section, the sampling and de-sampling process can be distortion free.
Then how about the quantization? It brings distortion, and the precision of the quantizer determines the intensity of the distortion.
However, you can set all these asides to understand CS.

As shown in the figure, A/D converter actually is responsible for sampling and quantizationg, D/A converter does reverse things.
And source encoder is responsible for compression.
Then consider, if we can sub-sample the signal, then we may not need to compress the signal. Then the only question is how to reconstruct the signal. CS theory just asserts the signal can be recovered faithfully, if the signal is sparse in certain domain, which is highly incoherent with time domain. For instance, the frequency domain is incoherent with time domain.
The CS system can be imaging as following,

$x[n]$ is corresponding to $r[n]$, however, in the real system, we actually do not have $x[n]$. Instead, we have already compressed $p[n]$, which corresponds to $s[n]$.
From $r[n]$ to $r(t)$ is not a problem. Then how to get $r[n]$ from $s[n]$? That's where CS works.
And as you can see, the A/D (D/A) converter becomes A/I (I/A) converter.
The sampling requirement reduced, while the reconstruction is more powerful. This is another kind of asymmetry compared to traditional "source encoding".

How can CS be more powerful?
Say, what if the signal is sparse in time domain, or in a domain coherent with time domain? Then, according to the CS theory, we should not under-sample in time domain as shown before. We need to under-sample in a domain incoherent with the sparsity domain.
Then how to design it? The most beautiful part of CS is RIP. The RIP says if you design the "compression" part as under-sampling signal in a domain, while the under-sampled part of the domain satisfies RIP, then the signal can be reconstructed faithfully.
To my understanding, (and certainly you can have your own interpretation), a matrix satisfies RIP essentially is a subset of domain, i.e., only a few of basis of the domain, while the domain is incoherent with almost every other domain. That's the "university" of CS theory.
An example is Gaussian matrix, which is almost incoherent with either time domain or frequency domain.
It is a little tricky, but if you take into account the role of "overwhelming probability", it would be easier to understand the inner connection.
I didn't go into the mathematical part of these relationships. But if you look at them as a black box, such interpretation does help.

Then the problem is how to first transform the signal into $\Phi$ domain, to make the following under-sampling possible.
This is the story of A/I converter. I won't go into this topic. But intuitively speaking, it takes the help of convolution/integrator.

And again, for 2D signals, like imaging system, even high-dimensional signals, the Nyquist sample and CS can be interpreted in another way. And a most vivid example is the "single-pixel camera".
I will discuss the 2D signal sampling, especially the imaging systems, in future.

Wednesday, September 26, 2012

Purpose of this blog entry

Sparse representation (SR), compressed sensing (CS), single measurement vector (SMV),  multiple measurement vector (MMV), I was ever confused about these terms. They seems to be the same, however, the way they using to describe problems differs.In this blog, I aim to make clear the inner relationship among them, and the development of these theories.

The Big Picture

To my understanding, the following figure describes the relationship of them.
To see the inherent relationship, I'd rather like to break the CS into two kinds, 1st generation CS (CS1G) and 2nd generation CS (CS2G). The difference will be discussed later. Nevertheless, such notation is not used in current society. So please not be confused when reading papers.
In the paper, CS is referred to CS2G. And SMV is referred to CS1G.
The notion SMV is first mentioned in [10]. (And in [11], one measurement vectors is used to describe the SMV problem).
We will return to the big picture in the end of this blog.

SMV: SR and CS1G

The SMV model basically presents such problem: $y = \Phi x$
•  sparse representation: $y$ is viewed as a signal in reality, $\Phi$ is called an over-complete dictionary, $x$ is the sparse representation
•  we want to find a sparse representation of the signal using a dictionary, and we want the signal to be as sparse as possible
•  $\Phi \in R^{M \times N}$: if M < N, the dictionary is over-complete, if M = N, the dictionary is complete, if M > N, the dictionary is under-complete. The "complete" is viewed from the signal $y$. Simply speaking, if the length of the representation is larger than that of the signal, then the signal is "over-represented", and thus the dictionary is "over-complete".
•  2D DCT, DFT, etc., are sparse representation of the signal using a complete dictionary
•  In this blog, we consider sparse representation of the signal using an over-complete dictionary
• 1st generation compressed sensing:  $x$ is a sparse signal in itself, i.e., there are only a few non-zero entries in $x$, $\Phi$ is called measurement matrix, $y$ is called measurements
• we want to sample a sparse signal using less measurements than its length, in other words, compressing the signal.
• here we only want $\Phi$ to be over-complete in terms of $y$
• note that "$x$ is a sparse signal in itself " is the identity of CS1G. For CS2G, as we will discussed in next section, $x$ is a sparse signal in domain $\Psi$, which is a generation of CS1G
Therefore, SMV is actually a model of SR and CS1G, with each describes different applications.
And we can also view SR as the reconstruction step of CS1G. In other words, in a sampling-reconstruction system, CS1G is the sampling process, and SR is the reconstruction process, by taking the sample as the signal.
If you have this in mind, you then probably can have a better understanding of following references discussed in this section.

The problem discussed in [1] is that a signal can be reconstructed if certain requirements were met in both cases:
1. a signal is sparse in frequency domain, and under-sampled, in other words, missing samples, in time domain,
2. or a signal is sparse in time domain, and under-sampled in frequency domain
They are actually CS1G problems, i.e., sampling a sparse signal in itself, and reconstructing the signal by solving the $\ell_1$ minimization.
For the first case, $x$ is the frequency components of the signal, $\tilde{\Phi}$ is inverse DFT basis, i.e. $IDFT(x) = \tilde{\Phi} x$  and $\Phi = R\tilde{\Phi}$ is the measurement matrix, where $R$ is a selection matrix, selecting $M$ rows of $\tilde{\Phi}$, $y$ is under-sampled time domain signal.
For the second case, $x$ is the time domain signal, $\Phi = R \tilde{\Phi}$ is the measurement matrix, where $\tilde{\Phi}$ is the DFT basis, $y$ is under-sampled frequency domain signal.
Thus, by taking the frequency domain components (first case), and time domain components (second case) as the original signal, respectively, the problem discussed is essentially a CS1G problem.

I'd like to also mention the following principle proposed in [1], which, I think, is the basic of following theoretical results.
1. Classical Uncertainty Principle: a function $f$ and its Fourier transform $\hat{f}$ cannot both be highly concentrated. $\Delta t \cdot \Delta w \geq 1$
2. [1] show a more general principle holds: it is not necessary to suppose that $f$ and $\hat{f}$are concentrated on intervals; instead, they can be just concentrated on a measurable set. $|T| |W| \geq 1-\delta$. And it also applies to sequences. $N_t \cdot N_w \geq N$
1. CT principle: missing segments of a bandlimited function can be restored stably in the presence of noise if (total measurement of the missing segments) $\cdot$ (total bandwidth) < 1.
2. DT principle: a wideband signal can be reconstructed from narrow-band data, provided the wideband signal to be recovered is sparse or "impulsive"
Then I have an intuitive understanding on he SMV/SR/CS1G theory:
1. a signal cannot be both sparse in two incoherent basis
2. under-sample the signal in a non-sparse domain, and recover the signal in sparse domain
• then from the recovered sparse domain signal, we are able to get the original signal
And this is actually the CS2G theory, which do not require $x$ to be sparse in itself. We leave the discussion in next section.
[2]-[5] are a sub-group of researches, related to both CS1G and CS2G theory.
[2] actually discussed the SMV problem from SR's point of view. And it proposed more incoherent basis pairs besides (time, frequency). And these incoherent basis pairs are actually CS2G theory.
[3] improved the constrains related to the replacement of $\ell_0$ minimization with $\ell_1$ minimization in [2].
[4] proved that the condition in [3] is both sufficient and necessary, whereas [3] only proved the sufficiency.
[5] should be an extension of [2]. However, I didn't go into details.

[6] is about CS1G, and can be viewed as a direct extension of [1]. The problem discussed in the paper can be phrased as follows:
• a N-length discrete time signal $f$ is sparse in time domain, i.e., consists of a superposition of |T| spikes.
• sub-sample the signal in frequency domain, i.e., only sample |$\Omega$|  frequency components, instead of N.
• If |T| $\leq C_M \cdot (\log{N})^{-1} \cdot |\Omega|$, then the reconstruction can be exact with probability at least 1-O($N^{-M^}) • the reconstruction is via solving$\ell_1$minimization problem. See, it is almost the same with [1] in this sense. In addition, [6] shows that the min TV problem is actually the problem stated in the paper. CS2G As I stated before, 1. a signal cannot be both sparse in two incoherent basis 2. under-sample the signal in a non-sparse domain, and recover the signal in sparse domain The most classical CS theory is expressing this idea.$y = \Phi x = \Phi \Psi \theta$. To better understand the essence, we let ($\tilde{\Phi}, \Psi$) be a pair of incoherence basis,$\Phi = R \tilde{\Phi}^T$. Then, in$\tilde{\Phi}$domain,$x$can be expressed as$\gamma = \tilde{\Phi}^T x$, in$\Psi$domain,$x$can be expressed as$\theta = \Psi^T x$. So$y$is actually achieved by under-sample the signal in non-sparse domain, i.e.,$\tilde{\Phi}$domain. In other words,$y = R \gamma$. And the signal is reconstruct in sparse domain, i.e.,,$\Psi$domain. Then the CS1G is actually taking$\Psi$as identity basis. [7]-[9] are actually the theoretical foundation work on the CS2G theory, together with [2]-[5]. I didn't find the paper [7]. However, it is stated in [8] that [7] extended the result in [6], and showed the exact recovery holds for other synthesis/measurement pairs. And [8] describes these results, making reading [7] not so necessary. The results are shown as follows: • an N-length signal$f$is sparse in domain$\Phi$, i.e.,$\theta = \Phi f$has only a few nonzero entries. • sub-sample the signal in domain$\Psi$, i.e., only sample$|\Omega|$coefficients, instead of N • the reconstruction can be exact, via solving an$\ell_1$minimization problem. • the requirement of the exact reconstruction is about the incoherence between$\Phi$and$\Psi$. [8] extended the work of [6] and [7], showing that the signal compressible, not necessarily strict sparse, in certain domain can also be optimally reconstructed, i.e., the reconstruction error using K measurements is as good as the best K-term approximation, with overwhelming probability. [9] discussed the linear code corrupted by noise problem. However, the RIP condition is proposed in this paper, although it does not show the clear relationship between the decoding and CS. Besides, the Gaussian ensembles are proved to follow RIP with an overwhelming probability. On the other hand, it should be noticed that, if RIP is satisfied, the reconstruction is exact determinedly, whereas in [6] [7] [8], the reconstruction is with overwhelming probability. Then [13] [14] organized all related theoretical results and formulate the CS problem. And [12] gives a tutorial for CS theory, which I preferred to recommend for reading. MMV The only thing left is MMV. As is shown in the big picture, MMV is a direct extension of SMV, in a different way with the evolution from SMV to CS. [11] formulate the MMV problem. Similar to SMV, the MMV can be viewed as either a 2D sparse representation problem, or a 2D CS1G problem. [10], [15] give theoretical results on MMV, which is derived from those on SMV, i.e., [1]-[6]. Discussions 1. In this blog, I didn't discuss the development from noiseless to noisy case, which is also an interesting and important evolution. 2. In this blog, I didn't focus on the development from sparse signals to compressible signals. 3. In this blog, I only discussed the discrete-time situation. However, CS is actually can be, and should be addressed in analog signals, which is the meaning of "sensing". 4. Since I'm working on CS theory, my knowledge to SR, MMV is limited. Thus, the goal is to discern the CS with SR, SMV, MMV, instead of introducing SR, MMV, which I believe are far more complicated. 5. Return to the big picture, it is interesting to ask, can we extend MMV similar to the extension form SMV to CS? To the best of my knowledge, recent work of Duarte and Baranuik in [16] discussing the high-dimensional CS, where 2D CS is an special case. However, it differs with MMV in the reconstruction method, since it still solving the reconstruction problem in 1D. I would appreciate your help if you can share your opinions and references on this issue. 6. At last, I really hope this blog can smooth your perplexity when reading references where you don't know what SR, CS, SMV, MMV refer to. They are on the one hand synonyms and inherently similar, and on the other hand differ slightly from each other in terms of their representations and applications. By the help of this blog, you may have in mind what the reference is discussing when reading, at least, references given in the blog. [1] Uncertainty principles and signal recovery [2] Uncertainty principles and idea atomic decomposition [3] A generalized uncertainty principle and sparse representation [4] On sparse representation in pairs of bases [5] Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization [6] Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information [7] The role of sparsity and incoherence for exactly reconstructing a signal from limited measurements [8] Near-Optimal signal recovery from random projections: universal encoding strategies ? [9] Decoding by linear programming [10] Sparse representation for multiple measurement vectors (MMV) in an over-complete dictionary [11] Sparse solutions to linear inverse problems with multiple measurement vectors [12] An introduction to compressive sampling [13] Compressive sampling [14] Compressed sensing [15] Theoretical results on sparse representations of multiple-measurement vectors [16] Kronecker compressed sensing Monday, August 13, 2012 Use IEEE Xplore to do a field study Want to apply for a graduate program? Want to know who are productive researchers in this area? Here are some tips to help you do field study, by the help of IEEE Xplore. 1. Use advanced search Input key words of this area, e.g. compressed sensing. I suggest you use "OR" to add new filter words. Click search. 2. See filters on the left side Select "Publication Year" with certain range, e.g. 2007 - 2012 Click search again. Then you will see a list of authors on the left side bar. They are ordered by number of publications. You would definitely know those productive researchers in your area. Go to IEEE Xplore now and check it out~ Friday, August 10, 2012 Basic Understanding of Compressed Sensing Purpose of this blog entry During my research on CS, one problem is that I have read several papers related on CS, but different paper have different notations and explanations for CS. Besides, they also propose some new stuff in the paper. So it takes me time to get to know the inner connections among these gorgeous references. As a result, I'd like to give a summary, according to my understanding, for the very basics of CS. Hope it will help you in your research. What can CS do? Well, intuitively speaking, CS is a way to sample and compress signals. You can use CS as a method to transmit or store a signal. One most immediate benefit of CS is that it samples and compresses signals at one time, thus reduces the complexity of encoder. Why we need CS? In following scenarios, we may turn to CS. 1) require simple encoder 2) require less bandwidth 3) sample high frequency component of signals, which cannot be sampled using traditional ways, e.g. MRI. (Due to the limited knowledge of me, there are lots of scenarios omitted. If you have any suggestions, please be kindly inform me.) Of course, if you want, you can use CS in whatever scenario that requires sample/store/transmit a signal. And the CS theory provides ways to reconstruct the sampled signals. Signals Please be advised that, some definitions used in this blog entry may differ from that in some papers. I use my definitions here because according to my understanding, it's better and easier for you to understand the connections between papers. Let a signal$\mathbf{x} \in \mathbb{R}^N$has its projection on an orthonormal basis$\mathbf{\Psi} \in \mathbb{R}^{N \times N}$be$\mathbf{\theta} \in \mathbb{R}^N$, i.e.,$\mathbf{\theta} = \mathbf{\Psi}^T \mathbf{x}$. •$S$-sparse signal:$\mathbf{x}$is called$S$-sparse in$\mathbf{\Psi}$or has sparsity$S$in$\mathbf{\Psi}$if$\mathbf{\theta}$has only$S$nonzero entries. •$C$-compressible signal:$\mathbf{x}$is called$C$-compressible in$\mathbf{\Psi}$or has compressibility$C$in$\mathbf{\Psi}$if$\mathbf{\theta}$obeys a power law decay with an exponent of$-C-1/2$. • power law decay:$\mathbf{\theta}$obeys a power law decay if$|\theta|_{(i)} \leq R \cdot i^{-1/p}$, where$R > 0$is a constant,$0 < p < \infty$, and$|\theta|_{(i)}$is the$i$th largest magnitude entry, i.e.,$|\theta|_{(1)} \geq  |\theta|_{(2)} \geq \cdots \geq |\theta|_{(N)}$. Then$C = 1/p - 1/2$for compressible signals. Mostly,$C$-compressible signals consider only the case$0 < p < 1$, i.e.,$C > 1/2$. It should be noticed that$\mathbf{\theta}$is also an$S$-sparse or$C$-compressible in$\mathbf{\Psi} = \mathbf{I}$, where$\mathbf{I}$is an identity basis. Thus, to be precise, we need to consider/indicate in which basis the signal has what sparsity or compressibility. For example, a signal may have sparsity 10 in Fourier basis, but may have sparsity 20 in DCT basis. Some papers would not indicate the sparsity Best$J$-term approximation To approximate a signal$\mathbf{\theta}$, we can use the largest$J$terms (in magnitude) in it, i.e.,$\mathbf{\theta}_J$. Therefore, 1. if$\mathbf{\theta}$is$S$-sparse in$\mathbf{I}$, then the best$J$-term approximation would have an approximation error equal to 0 if$J \geq S$, i.e.,$\mathbf{\theta}_J = \mathbf{\theta}$. 2. if$\mathbf{\theta}$is$C$-compressible in$\mathbf{I}$, then the best$S$-term approximation would have an approximation error equal$||\mathbf{\theta} - \mathbf{\theta}_J||_1 \leq G_C \cdot R \cdot J^{-C+1/2}$and$||\mathbf{\theta} - \mathbf{\theta}_J||_2 \leq G_C \cdot R \cdot J^{-C}$, where$G_C$is a constant only depend on$C$. Meanwhile, we should indicate which basis does the best$J$-term approximation consider, e.g.,$\mathbf{\theta}_J$is the best$J$-term approximation in$\mathbf{I}$. Then, we also say a best$J$-term approximation of$\mathbf{x}$in$\mathbf{\Psi}$is$\mathbf{x}_J$, i.e.,$\mathbf{\theta}_J = \mathbf{\Psi}^T \mathbf{x}_J$is the best$J$-term approximation of$\mathbf{\theta = \Psi}^T  \mathbf{x}$in$\mathbf{I}$. Similarly, we need to consider two attributes when saying a best$J$-term approximation: 1)$J$and 2)$\mathbf{\Psi}$. Another thing should be noticed is that since$\mathbf{\Psi}$is an orthonormal basis,$||\mathbf{x} - \mathbf{x}_J||_2 = ||\mathbf{\theta} - \mathbf{\theta}_J||_2 \leq G_C \cdot R \cdot J^{-C}$, i.e., the MSE has a power law decay. With$J$increasing, the MSE would decrease. How CS works? Generally speaking, CS samples a signal$\mathbf{x}$using$\mathbf{y = \Phi x = \Phi \Psi \theta = A \theta}$. •$\mathbf{A} \in \mathbb{R}^{K \times N}$: sensing matrix,$\mathbf{A = \Phi \Psi}$. •$\mathbf{\Phi} \in \mathbb{R}^{K \times N}$: measurement matrix (I was ever confused the sensing matrix with measurement matrix...) In this way, the signal is compressed in$\mathbf{y} \in \mathbb{R}^K$. Reconstructing the signal from$\mathbf{y}$can be achieved by solving a convex optimization problem, i.e.,$\min ||\mathbf{\theta}||_1$s.t.$\mathbf{y = \Phi \theta}$by knowing$\mathbf{y}$and$\mathbf{\Phi}$, and then using$\mathbf{x = \Psi\theta}$to get$\mathbf{x}$back. In other words, you can solve$\min ||\mathbf{x}||_1$s.t.$\mathbf{y = A x}$by knowing$\mathbf{y}$and$\mathbf{A}$. They are equivalent. The foundation of CS theory is to prove that in this sample-reconstruct process, the information in$\mathbf{x}$can be preserved, and thus$\mathbf{x}$can be well reconstructed. In the following demonstration, I will not show you how the theory evolves, rather than how to prove the result. If you like, you can refer to papers I cite to see the details. And a tip for your reading is that please notice what the choice of$\mathbf{A, \Phi, \Psi}$in CS. At the very beginning, the idea of CS is presented in [1]. In that paper, it proved that for an$S$-sparse signal in Fourier basis, using CS, the reconstruction would be exact with an overwhelming probability at least$1 - O(N^{-\alpha})$provided that$K \geq G_\alpha S \log{N}$, where$G_\alpha > 0$is a constant only depend on the accuracy parameter$\alpha$. That is to say, for a given desired probability of success, a sufficient condition for exactly reconstruction is$K \geq G_\alpha S \log{N}$. It should be noticed that in some paper, it also gives a necessary condition with a similar result, please do not mix them up. The choice of$\mathbf{\Psi}$is Fourier basis. The choice of$\mathbf{A}$is a random selecting matrix, i.e., randomly selecting$K$elements from$\mathbf{\theta}$, e.g.$\mathbf{A}$= [0 1 0 0 0; 0 0 1 0 0] which extracts the second and third elements of$\mathbf{\theta}$. Thus$\mathbf{\Phi} = \mathbf{A \Psi}^T$can be generated accordingly. It can be seen that if a signal is$S$-sparse in another basis$\mathbf{\Psi}$, CS can still reconstruct it using this way to generate$\mathbf{A}$and$\mathbf{\Phi}$by knowing$\mathbf{\Psi}$. Furthermore, in [4],they extended these results and showed that exact reconstruction hold for other$(\mathbf{\Phi, \Psi})$pairs. Then in [2], it began to consider a$C$-compressible signal. It showed that using CS, the reconstruction is optimal with an overwhelming probability at least$1 - O(N^{-\rho / \alpha})$. By optimal, it means that it is generally impossible to obtain a higher accuracy from any set of$K$measurements whatsover. The reconstruction error obeys$||\hat{\mathbf{x}} - \mathbf{x}||_2 = ||\hat{\mathbf{\theta}} - \mathbf{\theta}||_2 \leq G_{C, \alpha} \cdot R \cdot (K / \log{N})^{-C}$, where$\hat{\mathbf{x}}$and$\hat{\mathbf{\theta}}$is the reconstructed signals,$G_{C, \alpha}$is a constant depending on$C$and$\alpha$. This indeed says that if one make$K = O(J\log{N})$measurements using CS, one still obtains a reconstruction error equally as good as using best$J$-term approximation. In other words, the following two cases have similar reconstruction error: 1) knowing everything about$\mathbf{\theta}$and selecting$J$largest entries of it, 2) reconstructing$\mathbf{\theta}$using$K = O(J\log{N})$measurements without any prior knowledge on it. In [2], the choice of$\mathbf{\Psi}$is can be any orthonormal basis and it provided three ways to generate$\mathbf{A}$: 1) Gaussian ensembles; 2) Binary ensembles; 3) Fourier ensembles. Before goes go, I'd like to introduce the so-called restricted isometry property (RIP). For each integer$k = 1, 2, \dots$, define the$k$-restricted isometry constant$\delta_k$of a matrix$\mathbf{A}$as the smallest number such that$(1-\delta_k)||\mathbf{\theta}||_2^2 \leq ||\mathbf{A \theta}||_2^2 \leq (1 + \delta_k) ||\mathbf{\theta}||_2^2$holds for all$S$-sparse signal vector$\mathbf{\theta}$in$I$with$S \leq k$. Therefore,$\mathbf{A}$should have more than one restricted isometry constant since we can choose any$k$. Usually, we say a matrix$\mathbf{A}$obeys RIP of order$S$if$\delta_S$is not too close to 1. Then a stronger result is introduced in [5] and [6] (and stated in [3]), which says that, if the$k$-restricted isometry constant$\delta_k$of$\mathbf{A}$satisfies certain constraints (with different$k$), e.g.$\delta_{2S} \leq \sqrt{2} - 1$(several other constraints are stated in [5] and [6]), then the reconstructed signal$\hat{\mathbf{\theta}}$obeys$||\hat{\mathbf{\theta}} - \mathbf{\theta}||_2 \leq G_0 \cdot ||\mathbf{\theta} - \mathbf{\theta}_S||_1 / \sqrt{S}$and$||\hat{\mathbf{\theta}} - \mathbf{\theta}||_1 \leq G_0 \cdot ||\mathbf{\theta} - \mathbf{\theta}_S||_1$for some constant$G_0$, where$\mathbf{\theta}_S$is the best$S$-term approximation of$\mathbf{\theta}$in$\mathbf{I}$. This is deterministic, without any probability of success. To go a step further, you will see that the result is in consistent with previous results. If you replace$||\mathbf{\theta} - \mathbf{\theta}_S||_1$using the result in "Best$J$-term approximation", you will see the magic. Then the question comes, how to generate a sensing matrix$\mathbf{A}$satisfies the requirement of RIP? How to generate sensing matrix$\mathbf{A}$? There are lots of ways to generate a sensing matrix$\mathbf{A}$. I'd rather let you refer section "RANDOM SENSING" in [3] for a review. Here I just want to talk about two most common ways: 1) from$\mathbf{A}$by sampling$N$column vectors uniformly at random on the unit sphere of$\mathbb{R}^K$; 2) from$\mathbf{A}$by sampling i.i.d. entries from the normal distribution with mean 0 and variance 1/K. With an overwhelming probability, these matrices obey the RIP constraints (e.g.$\delta_{2S} \leq \sqrt{2} - 1$) provided that$K \geq G \cdot S \log{(N/S)}$, where$G$is some constant depending on each instance. Another interesting property is that the RIP constraints can also hold for sensing matrix$\mathbf{A = \Phi \Psi}$where$\mathbf{\Psi}$is arbitrary orthonormal basis and$\mathbf{\Phi}$is an$K \times N$measurement matrix drawn randomly from a suitable distribution, e.g., with an overwhelming probability, provided that$K \geq G \cdot S \log{(N/S)}$,$\mathbf{A}$obeys the RIP constraints. This makes CS sampling easier, because we only need to generate a measurement matrix$\mathbf{\Phi}$without knowing$\mathbf{\Psi}$at the encoder side. A reading tree/graph for basic understanding of CS theory If you read papers from the top layer to bottom layer, you should have deeper and deeper understanding about CS theory. References [1] Robust Uncertainty Principles: Exact Signal Reconstruction From Highly Incomplete Frequency Information [2] Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? [3] An Introduction To Compressive Sensing [4] The Role of Sparsity and Incoherence for Exactly Reconstructing a Signal from Limited Measurement [5] Stable signal recovery from incomplete and inaccurate measurements [6] Compressed sensing and best k-term approximation Wednesday, July 25, 2012 IEEE Transaction Starter: How to Start Writing a IEEE transaction paper Here I want to show tasks that helps you get to know how to write a paper for IEEE transactions. 1. Visit "IEEE Author Digital Tool Box" http://www.ieee.org/publications_standards/publications/authors/authors_journals.html and Read "Instructions" for different Templates. You may need only read the instruction for the template you will use. Here we focus on the "Instruction Only" in the "Template fors Transactions" part. http://www.ieee.org/documents/TRANS-JOUR.pdf * In this step, you will have a basic knowledge on the rules of writing a paper in IEEE society, especially for transactions and journal. 2.1 For MS Word users, 2.1.1 please download "Template and Instructions on How to Create Your Paper". http://www.ieee.org/documents/TRANS-JOUR.doc 2.1.2 Please follows the instruction in the document to create your paper. 2.2 For Latex users, 2.2.1 You need to download "Transaction Style File", either "Unix LaTeX2e Transactions Style File", http://www.ieee.org/documents/IEEEtran.tar.gz or "WIN OR MAC LaTeX2e Transactions Style File". http://www.ieee.org/documents/IEEEtran.zip * The Bibiliography file is included in the file (under the directory of "bibtex"). 2.2.2 Read the "IEEEtran_HOWTO.pdf" to know how to use the style file. 2.2.3 Read the "IEEEtran_bst_HOWTO.pdf" under "bibtex" directory to know how to manage bibliography. After finish these simple tasks, you should have a basic knowledge on the technical issues for your paper. Monday, June 18, 2012 推荐一个GTD软件: doit.im 以前博主一直用mGSD（http://mgsd.tiddlyspot.com/#mGSD）来作GTD管理 mGSD是一个基于tiddlywiki的应用 基本GTD的功能都实现了 并且有着tiddlywiki的特点：单HTML文件 所以方便跨平台 也方便到处携带 对于有多台常用电脑的 我一般使用GitHub或者Windows Live Mesh进行同步管理 但是它有一个比较致命的弱点 也是tiddlywiki一直存在的问题 对于移动设备的支持 没有再ipad android phone上的app支持 所以博主最近发现一个免费的app： doit.im (http://doit.im/) 它可以在android和apple的移动设备上使用 也可以通过web使用 并且在GTD的功能方面 除了正常的功能外 还有 1. 收集箱功能 用于存储暂时无法归类的项目 2. 闹钟提醒功能 并可以设置多个提醒时间 3. 优先级功能 4. 过滤器 5. 与google calendar同步 这个功能对于博主这种google用户太有用了 但是还是有一些小缺点的 比如没有review机制等 但是根据官方的说法 9月份左右应该就会更新了 另外，对于windows桌面版，官方说法是还在开发，以前的版本仍能在http://support.doit.im/entries/21392588-doit-im-for-windows0-9-1 下载到，也能使用，据说有BUG。 再最后说一下，这个是国产的软件，而且个人觉得做的比较好的。听说最近也获得了投资，所以博主表示强烈支持。最近推出Pro收费，如果做得好的话，也会尝试使用的。 Wednesday, March 28, 2012 Windows 7无法休眠？ 昨天突然发现windows 7没法休眠了 症状是： 点休眠后屏幕会黑一下 然后就进入到了Login的画面了-。- 在网上搜了半天：“windows 7无法休眠”之类的 基本上都在说什么：更新驱动哇，设置power configuration之类的。。 都没用。。。 正在郁闷 于是用英文搜了一下 windows 7 cannot hibernate （休眠是Hibernate 睡眠是sleep 哈哈~） 终于眼睛一亮看到一个[Solved]GRUB + Windows 7 = Can't put windows to sleep/hibernate 特别是这个solved哇 真是救命稻草哇 链接如下：http://ubuntuforums.org/showthread.php?t=1341694 然后基本按照里面的步骤 就OK了 如果你的电脑也装了ubuntu之类的 应该就是这个问题没跑儿了 如果你只有windows... 那就另寻他法吧-。- 这里我把英文大概翻译一下~ 症状： 在装了Windows 7之后装Ubuntu双系统的机子（这个双系统的顺序也是有讲究了。。主要是看你是不是用GRUB引导系统），这个你就把GRUB装在了MBR上，这个就会导致Windows没法进入sleep or hibernate模式（这个屏幕会黑一下，然后直接回来）。用WIN7的DVD恢复这个MBR到原来的状态呢是可以解决的，但是会让你的GRUB又没法工作了... 实际问题： 要让sleep/hibernate工作，第一个windows的分区必须是标记为boot，即使里面装了GRUB。 解决方案： 在Ubuntu下， 使用gparted(如果没装的话 sudo apt-get install gparted。使用就是sudo gparted)。在你的boot driver（通常是/dev/sda)，确保第一个windows分区是标为boot的。然后重启就OK了 P.S. 这个帖子的回复也值得一看~ 一般用Thinkpad的同学常常会遇到这个问题，因为Thinkpad有个默认的分区SYSTEM_DRV在C盘之前。一般它是作为boot分区的。所以我们只要把Windows系统分区作为boot就好了。 这个故事告诉我们，掌握英文搜索能力很重要... Monday, March 26, 2012 jQuery中设置click事件的参数 (部分转自百度知道) 【问题】 原来html中onclick出发js方法可以传递参数 <a href="#" onClick="showFile('view');">aaaaa</a> <script>function showFile(fun){}</script> 但是 现在用jquery的click事件怎么传递这个参数？ <a href="#" id="fun">aaaaa</a>$("#fun").click(function () { });

1. jQuery的click事件不能直接传递参数，

function choose() {
//...
}

2. 可以把
$('#fun').click(function () { }); 看作一个function声明, 就相当于onclick的事件声明;$('#fun').click(function () {
function()(调用的方法)
});

3. 可以使用标签内的attr来获得关于此标签的参数
<a id="fun" testvalue='abc' href="#" onClick="showFile('view');">aaaaa</a>
$('#fun').click(function () { alert($(this).attr('testvalue'));
alert($(this).text()); alert($(this).attr('href'));
//......
});

jQuery获取input标签的值

<input id="p_folder"></input>
var p = document.getElementById("p_folder");
var pV = p.value;

var p = $('p_folder'); var pV = p.value； 将无法获取到标签内的值, 这是因为$("")是一个jQuery对象，而不是一个DOM element
value是DOM element的属性，对应jQuery的val
val():获得第一个匹配元素的当前值
val("val"):设置每一个匹配元素的值为val

Thursday, March 1, 2012

Some Ideas

* 这个还可以开发app平台 做一个app推荐菜谱 or 根据家里的菜规划要做的菜（对于一次买N天菜的人） 提醒菜过期...

Saturday, February 4, 2012

Enable Latex / Math Formula in Blogger

See http://irrep.blogspot.com/2011/07/mathjax-in-blogger-ii.html for the instruction.

It's awesome.

Saturday, January 28, 2012

Summary of Block Compressed Sensing on Image

Last article, I briefly introduce existing cs method on image. This article aims to summary how block cs worked on image.

Before I go on, I need to introduce something about measurement matrix.
Currently, there are several way to generate a measurement matrix. For a complete list of possible measurement matrix, please refer to  https://sites.google.com/site/igorcarron2/cs . Here I only discuss three of them:
• Random Fourier Ensemble: The signal is a discrete function f on Z/NZ, and the measurements are the Fourier coefficients at a randomly selected set Omega of frequencies of size M ( A is an M x N matrix.)
• Gaussian ensemble: A is an M x N matrix (M x N Gaussian variables).
• Bernoulli ensemble: A is an M x N matrix (M x N Bernoulli variables).
It should be noticed that for most of the case, the measurement matrix should be orthonormal.

For 1d signal, Gaussian ensemble is enough to reconstruct the signal[1]. However, for 2d image,  N can be fairly large, which makes the storage and computations of a Gaussian ensemble very difficult. Thus, [2] suggested to apply a partial random Fourier matrixFor sparse basis, it employed waveletBesides, it uses min tv instead of l1norm as recon strategy. However, I've found no simulation code available for [2].

Another possible way to solve the problem addressed before is to sample the image block by block. This is quite similar with what JPEG did. [3] gives out corresponding research. For measurement matrix, the paper uses i.i.d Gaussian ensembles. For sparse basis, it uses LT. The reconstruction is based on PoCS and Hard Thresholding . No simulation code available now. But you may refer to https://sites.google.com/site/igorcarron2/cscodes. There is a code called
Implemented from Fast compressive imaging using scrambled block Hadamard ensemble by Lu GanThong Do and Trac Tran. This is another algorithm proposed by the same author. It may help you.

To improve the performance of [3], [4] proposed to first decompose the coefficients into dense and sparse component. For dense component, it uses conventional encoding; for sparse component, it uses cs. For measurement matrix, it didn't clearly indicate in the paper. But from inference, it should use i.i.d Gaussian ensembles as in [3]. It still employs wavelet as sparse basis. The reconstruction is based on PoCS[2] and prediction by adaptive interpolation. The paper gives out the detailed reconstruction scheme. No simulation code available now.

After that, [5] gives some interesting simulation results. Here for measurement matrix, it should still use i.i.d Gaussian ensembles.But for sparse basis, it proposed to use Directional Transformation(CT and DDWT).The reconstruction is based on SPL. Simulation code is available at http://www.ece.msstate.edu/~fowler/BCSSPL/. Besides I am quite interested in analyzing the EXPERIMENTAL RESULTS part in this paper. It compares with several other methods.
1. To compare the effectiveness of CT and DDWT, it compares to BCS-SPL-DWT, BCS-SPL-DCT. The simulation code is not available now.
2. To compare SPL with TV, it compares with BCS-TV. The implementation is using l1-Magic(http://acm.caltech.edu/l1magic/). I have implemented the code at http://www.ualberta.ca/~hfang2/pub/Block CS-TV.zip .
3. To compare SPL with GPSR and SAMP, it uses the implementation provided by their respective authors(http://www.lx.it.pt/~mtf/GPSR/ http://thongdojhu.googlepages.com/samp_intro/ ).

The last one is [6]. It perform random permutation among blocks to achieve better performance. It uses DCT as sparse basis. For measurement matrix, it uses i.i.d Gaussian ensembles.It uses min l1-norm instead of min tv as reconstruction method. I recommend you use cvx_toolbox(http://cvxr.com/cvx/download/) for simulation.

Thanks a lot.

[1] Robust uncertainty principles: Exact signal reconstruction form highly incomplete frequency information
[2] Practical Signal Recovery from Random Projections
[3] Block Compressed Sensing of Natural Images
[4] Image Representation by Compressed Sensing
[5] Block compressed sensing of images using directional transforms
[6] Compressive Sampling With Coefficients Random Permutations for Image Compression

Wednesday, January 25, 2012

Compressed Sensing(压缩感知)用于图像的综述

CS最初由[1][2][3]提出。[1, 2]没有看，[3]中理论推导比较多。我建议读[4]作为入门。

1. 重建算法计算量大
2. 需要大量的存储空间来保存随机采样operator，即measurement matrix

05年的时候，在[6]中最初对2D图像信号进行了CS reconstruction并给出了其仿真结果，不过这篇文章只讨论了无噪的情况，而且没有给出有噪情况的分析。作者的主要方案是apply a partial random Fourier matrix in the wavelet domain。
06年[3]提出multiscale CS：different scales of wavelet coefficients are segregated and sampled with partial Fourier ensembles。

• if the underlying image is highly compressible or
• or if the SNR is sufficiently large

07年L. Gan基于[6]的理论提出了block compressed sensing[7]。这篇文章是我认为很多后续对图像压缩的研究的基础，非常建议一读。

08年MSRA的一帮人提出了将图像的coefficients进行分解[8]，对于dense的部分进行conventional encoding （变换编码），sparse的部分进行CS。

[7]和[8]都给出了PSNR效果，是很好的比照对象。

[14]是基于[6]的一个改进。除了算法部分，我推荐看一下Background这一部分，它比较完整的介绍了当前CS的一些算法。同时，这篇文章也对[6]进行了review，有助于理解[6]的算法。另外，这篇文章给出了不同CS算法下的PSNR，有比较系统的仿真结果，可供参考。

11年，[15]提出了基于[6]的另一种改进。作者对稀疏系数矩阵进行random permutation从而使稀疏度分布趋近一致，从而提高CS的性能。

08年T. Wan等人提出将cs应用于image fusion[10]，09年A. Divekar也作了类似的研究[11]。image fusion就是将从不同sensor对同一个场景的图像结合起来一发现其中的信息。有兴趣的同学可以看看这两篇文章，这里不多做解释。

09年开始，研究者开始考虑colored image，从而将CS从2D image转到了3D。[12]的作者提出使用Bayer Filter以及Joint Sparsity Model来exploit不同色彩信道之间的相关性。结果显示这种方法比普通的对各个信道独立进行CS效果更好。

08年，CS界的一位牛人J. Romberg使用noiselet概念（类似wavelet），并且使用min TV而不是min l1进行图像重建[13]。TV中的梯度运算可以促进smoothing，更加适合images。这也是大多数CS imaging的恢复算法。但是Noiselet用于稀疏基在图像方面的后续研究我还没有看到，有可能是我遗漏了。

[1] Roubust uncertainty principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
[2] Near optimal signal recovery from random projections: Universal Encoding Strategies?
[3] Compressed Sensing
[4] Introduction to compressed sampling
[5] Signal reconstruction from noisy random projections
[6] Practical Signal Recovery from Random Projections
[7] Block compressed sensing of natural images
[8] Image representation by compressed sensing
[9] Compressive Sampling VS. Conventional Imaging
[10]Compressive image fusion
[11]Image fusion by compressive sensing
[12]Compressive imaging of color images
[13]Imaging via Compressive Sampling
[14]Block compressed sensing of images using directional transforms
[15]Compressive Sampling with Coefficients Random Permutations for Image Compression

Tuesday, January 24, 2012

Apache2.2 + PHP5.3.3 Windows下的配置

1. Windows； Linux下的我没配过，所以不是很清楚。
2. Apache2.2；版本比较重要，不同的版本也有可能是不一样的配法~所以，如果是要配置其他版本的话，请换关键字搜索~~呵呵~
3.PHP5.3.3； 同样是版本的问题~

1. 首先，先要下Apache2.2。我下的是httpd-2.2.16-win32-x86-no_ssl.msi，安装到C:\Program Files里了
2. 然后，把PHP5.3.3也下下来，注意，要下php-5.3.3-Win32-VC6-x86.zip这个文件，不要有nts，也不要是VC9什么的。我一开始就下错了，然后缺文件之类的- -。

3. 装好Apache之后，可以打开Apache服务，然后访问localhost一下，看看是不是装好了。基本上这步不会出问题的。
4. 配置PHP。

1） 配置PHP5.3.3，打开php安装目录（C:\php）可以看到目录下有两个这样的文件 php.ini-development和php.ini-production，第一个是开发使用的配置文件，第二个是标准的生产环境的配置。
2）选择php.ini-development复制一份到同目录下，并改名为php.ini使用文本工具打开，查找extension_dir，可以看到两个，选择On windows:

！！这里一定要注意的是，不要只改了目录，而没有把分号去掉- -分号没去掉这句话是不起作用的。

<? phpinfo()?>放在Apache的访问的文件夹下（可以查看Apache22/conf/httpd.conf,搜索DocumentRoot），默认是Apache22/htdoc这个文件夹。然后访问localhost/index.php，可以看到

 Configuration File (php.ini) Path C:/Windows Loaded Configuration File C:/php/php.ini

 extension_dir C:/php/ext C:/php/ext

3)查找extension=php_，去掉
extension=php_curl.dll、extension=php_gd2.dll、extension=php_mbstring.dll、
extension=php_mysql.dll、extension=php_mysqli.dll、extension=php_pdo_mysql.dll、extension=php_xmlrpc.dll

4)复制php5ts.dll文件到WINDOWS/system32目录下，只有php-5.3.3-Win32-VC6-x86版本中才有php5ts.dll php-5.3.3-nts-Win32-VC6-x86版本是没有的。
5)复制libeay32.dll ssleay32.dll（C:/PHP）到C:/windows下。
（之所以有这一步，可能是因为类似的某个目录没有配好，默认在C：/windows下。但暂时我还不知道在哪配，所以也就只好默认了- -）

Wednesday, January 18, 2012

免费软件打造你的学术PC

1. Tiddlywiki + Git + Github
Tiddlywiki 是一款基于Html的单文件个人知识管理系统 十分容易上手

etc...

Git是一款版本管理软件 有过项目开发经验的同学都应该接触过这个软件

2. mGSD

mGSD算是tiddlywiki中发展很健全的一个例子 它完全实现了GTD的所有功能

3. Live Mesh

4. MindManager

5. Mendeley

6. Dropbox

7. Evernote

8. Vim

9. TexMaker
Latex编辑器 写paper的专业工具 在格式排版方面 比word好用很多

Saturday, January 14, 2012

1. Mendeley
2. Dropbox
3. SlideShark
4. 金山词霸
没啥好说的 查单词
5. Caculator++
免费的计算器软件
6. Evernote
很好用的云端记事本软件 可以和电脑 手机同步 我用它来记一些小事情 其他事情我使用mGSD 一款基于tiddlywiki的GTD工具 有机会下次介绍
7. pdf-notes
免费的看pdf的软件 并且可以作注释 功能很强大
8. CloudOn
编辑 查看office文档的软件
9. iNoteBook Lite
集合日历 日记 笔记 文档管理于一身的软件 有兴趣的朋友可以使用一下
10. PocketCloud
远程登录电脑软件 可以在任何地方登录你的电脑
11. WifiSendFree
12. Mindjet
13. Timeli
项目日程管理软件 用户界面友好
14. OfficeDrop
可以随时将纸质文档通过摄像头扫描保存为电子文档并上传到服务器保存
15. i-Clickr
一款控制电脑PPT播放的软件 这个软件是收费的 但是是坐presentation的绝对利器 可以设置timer提醒时间 可以看ppt的备注 控制PPT播放 进行涂鸦等等 所以花钱买or越狱装都是值得的

Monday, January 9, 2012

推荐两款文件夹同步软件Live Mesh和SyncToy

Windows Live Mesh 是Microsoft推出的功能 可以将文件夹同步到网络端 从而在不同的机器上同步 而且注册就有5G的免费空间 并且可以远程登录桌面 非常好用

WikiCFP : Call For Papers of Conferences , Workshops and Jounals

WikiCFP : Call For Papers of Conferences , Workshops and Jounals

Sunday, January 8, 2012

X10i Root 2.3.3教程

android 2.3.3

Root
1. 安装驱动
2. 设备管理器-> X10 （未知USB设备）-> 更新驱动 （选择文件夹 Flashtool -> drivers)
2. 打开X10FlashTool.exe
3. 手机设置 未知来源 （设置->应用程序）和 USB调试，保持唤醒（设置->应用程序->开发）
4. 连接手机
5. 等待Root图标亮起 点击ROOT
6. 期间会重启
7. 显示'root access allowed'，表示root成功

FAQ:
• Root图标不亮起是为什么？

• 刷机失败 启动时一直卡在开机画面

Thursday, January 5, 2012

The reason for using 8x8 as the block size in image processing

The DCT usually use 8x8 as the block size to be applied to images. This is a trade-off between computational complexity, compression speed and quality.

A lot of research work show that after 15 or 20 pixels, the relationship among them begins to reduce; that is to say, a group of similar pixels usually lasts for 15 to 20, after that, the amplitude would change.