c# pdf reader text : Cut pages from pdf file Library application class asp.net windows .net ajax SzeliskiBook_20100903_draft77-part655

A.5 Iterative techniques
749
procedure SparseCholeskySolve(C;d):
1. Determine symbolicallythestructureof C, i.e., theadjacencygraph.
2. (Optional) Compute a reordering for the variables, taking into ac-
count any block structure inherent in the problem.
3. Determine the fill-in pattern for R and allocate the compressedstor-
age for R as well as storage for the permuted right hand side
^
d.
4. Copy the elements of C and d into R and
^
d, permuting the values
according to the computed ordering.
5. Perform the numerical factorization of R using AlgorithmA.1.
6. Solve the factored system (A.33), i.e.,
R
T
z=
^
d; Rx = z:
7. Return the solution x, after undoing the permutation.
Algorithm A.2 Sparse least squares using a sparse Cholesky decomposition of the matrix
C.
the case with image processing problems defined on pixel grids, since, even with the optimal
reordering (nested dissection) the amount of fill can still be large.
Apreferable approach to solvingsuch linear systems is to use iterative techniques, which
compute a series of estimates that converge to the final solution, e.g., by taking a series of
downhill steps in an energy function such as (A.29).
Alargenumber of iterativetechniques have been developed over the years, including such
well-known algorithms as successive overrelaxation and multi-grid. These are described in
specialized textbooks on iterative solution techniques (Axelsson1996;Saad2003) as well as
inmoregeneralbooks on numerical linear algebra and leastsquares techniques (Bj¨orck1996;
Golub and Van Loan 1996; Trefethen and Bau 1997; Nocedal and Wright 2006; Bj¨orck and
Dahlquist 2010).
A.5.1 Conjugate gradient
The iterative solution technique that often performs best is conjugate gradient descent, which
takes a series of downhill steps that are conjugate to each other with respect to the C matrix,
Cut pages from pdf file - remove PDF pages in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Provides Users with Mature Document Manipulating Function for Deleting PDF Pages
delete pages pdf document; delete blank page from pdf
Cut pages from pdf file - VB.NET PDF Page Delete Library: remove PDF pages in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
Visual Basic Sample Codes to Delete PDF Document Page in .NET
cut pages out of pdf file; delete page on pdf reader
750
Computer Vision: Algorithms and Applications (September 3, 2010 draft)
i.e., if the u and v descent directions satisfy u
T
Cv = 0. In practice, conjugate gradient
descent outperforms other kinds of gradient descent algorithm because its convergence rate
is proportional to the square root of the condition number of C instead of the condition
number itself.
9
Shewchuk(1994)providesaniceintroductiontothistopic,withclearintuitive
explanations of the reasoning behind the conjugate gradient algorithm and its performance.
AlgorithmA.3describes the conjugate gradient algorithm and its related least squares
counterpart, which can be used when the original set of least squares linear equations are
available in the form of Ax = b (A.28). While it is easy to convince yourself that the two
forms are mathematically equivalent, the least squares form is preferable if rounding errors
start to affect the results because of poor conditioning. It may also be preferable if, due to
the sparsity structure of A, multiplies with the original A matrix are faster or more space
efficient than multiplies with C.
Theconjugate gradientalgorithm starts by computing the currentresidualr
0
=d Cx
0
,
which is the direction of steepest descent of the energy function (A.28). It sets the original
descent direction p
0
= r
0
. Next, it multiplies the descent direction by the quadratic form
(Hessian) matrix C and combines this with the residual to estimate the optimal step size 
k
.
The solution vector x
k
and the residual vector r
k
are then updated using this step size. (No-
tice how the least squares variantof the conjugate gradient algorithm splits the multiplication
by the C = A
T
Amatrix across steps 4 and 8.) Finally, a new search direction is calculated
by first computing a factor  as the ratio of current to previous residual magnitudes. The
new search direction p
k+1
is then set tothe residual plus  times the old search direction p
k
,
which keeps the directions conjugate with respect to C.
It turns out that conjugate gradient descent can also be directly applied to non-quadratic
energy functions, e.g., those arising from non-linear least squares (AppendixA.3). Instead
of explicitly forming a local quadratic approximation C and then computing residuals r
k
,
non-linear conjugate gradient descentcomputes the gradient of the energy function E (A.45)
directlyinside each iterationanduses it to setthe searchdirection(NocedalandWright2006).
Since the quadratic approximation to the energy functionmay notexistor maybe inaccurate,
line search is often used to determine the step size 
k
.Furthermore, to compensate for errors
in finding the true function minimum, alternative formulas for 
k+1
such as Polak–Ribi`ere,
k+1
=
rE(x
k+1
)[rE(x
k+1
)  rE(x
k
)]
krE(x
k
)k2
(A.51)
are often used (NocedalandWright2006).
Theconditionnumber(C)istheratioofthelargestandsmallesteigenvaluesofC.Theactualconvergence
rate depends on theclustering ofthe eigenvalues, as discussed in thereferences cited in this section.
C# PDF Page Extract Library: copy, paste, cut PDF pages in C#.net
PDF Pages in C#.NET. Easy to Use C# Code to Extract PDF Pages, Copy Pages from One PDF File and Paste into Others in C#.NET Program.
delete page in pdf preview; delete page from pdf file online
VB.NET PDF Page Extract Library: copy, paste, cut PDF pages in vb.
VB.NET PDF - PDF File Pages Extraction Guide. Help to extract single or multiple pages from adobe PDF file and save into a new PDF file.
copy page from pdf; delete blank pages from pdf file
A.5 Iterative techniques
751
ConjugateGradient(C;d;x
0
)
1. r
0
=d   Cx
0
2. p
0
=r
0
3. for k = 0:::
4.
w
k
=Cp
k
5.
k
=kr
k
k
2
=(p
k
w
k
)
6.
x
k+1
=x
k
+
k
p
k
7.
r
k+1
=r
k
k
w
k
8.
9.
k+1
=kr
k+1
k
2
=kr
k
k
2
10.
p
k+1
=r
k+1
+
k
p
k
ConjugateGradientLS(A;b;x
0
)
1. q
0
=b   Ax
0
, r
0
=A
T
q
0
2. p
0
=r
0
3. for k = 0:::
4. v
k
=Ap
k
5. 
k
=kr
k
k
2
=kv
k
k
2
6. x
k+1
=x
k
+
k
p
k
7. q
k+1
=q
k
k
v
k
8. r
k+1
=A
T
q
k+1
9. 
k+1
=kr
k+1
k
2
=kr
k
k
2
10. p
k+1
=r
k+1
+
k
p
k
Algorithm A.3 Conjugate gradient and conjugate gradient least squares algorithms. The
algorithm is described in more detail in the text, but in brief, they choose descent directions
p
k
that are conjugate to each other with respect to C by computing a factor  by which to
discount the previous search direction p
k 1
.They then find the optimal step size  and take
adownhill step by an amount 
k
p
k
.
A.5.2 Preconditioning
As we mentioned previously, the rate of convergence of the conjugate gradient algorithm
is governed in large part by the condition number (C). Its effectiveness can therefore be
increased dramatically by reducing this number, e.g., by rescaling elements in x, which cor-
responds to rescalingrows and columns in C.
In general, preconditioning is usually thought of as a change of basis from the vector x to
anew vector
^x = Sx:
(A.52)
The corresponding linear system being solved then becomes
AS
1
^x = S
1
b or
^
A^x =
^
b;
(A.53)
C# PDF copy, paste image Library: copy, paste, cut PDF images in
PDF image cutting is similar to image deleting. So, in C# demo code below, we will explain how to cut image from PDF file page by using image deleting API.
delete pages from pdf in preview; cut pages from pdf reader
VB.NET PDF copy, paste image library: copy, paste, cut PDF images
PDF image cutting is similar to image deleting. So, below example explains how to cut image from PDF file page by using image deleting API.
add and delete pages in pdf; delete pages pdf
752
Computer Vision: Algorithms and Applications (September 3, 2010 draft)
with a correspondingleast squares energy (A.29) of the form
E
PLS
=^x
T
(S
T
CS
1
)^x  2^x
T
(S
T
d) + k
^
bk
2
:
(A.54)
The actual preconditioned matrix
^
C = S
T
CS
1
is usually not explicitly computed. In-
stead, AlgorithmA.3is extended to insert S
T
and S
T
operations at the appropriate places
(Bj¨orck1996;GolubandVanLoan1996;TrefethenandBau1997;Saad2003;Nocedaland
Wright 2006).
Agood preconditioner S is easyandcheaptocompute, but is alsoa decent approximation
to a square root of C, so that (S
T
CS
1
)is closer to 1. The simplest such choice is the
square root of the diagonal matrix S = D
1=2
,with D = diag(C). This has the advantage
that any scalar change in variables (e.g., using radians insteadof degrees for angular measure-
ments) has no effect onthe range of convergence of theiterativetechnique. For problems that
are naturally block-structured, e.g., for structure from motion, where 3D point positions or
6Dcamera poses are being estimated, a block diagonal preconditioner is oftena good choice.
Awide variety of more sophisticated preconditioners have been developed over the years
(Bj¨orck1996;GolubandVanLoan1996;TrefethenandBau1997;Saad2003;Nocedaland
Wright 2006),manyofwhichcanbedirectlyappliedtoproblemsincomputervision(Byr
¨
od
and øAstr¨om 2009; Jeong, Nist´er, Steedly et al. 2010; Agarwal, Snavely, Seitz et al. 2010).
Some of these are based on an incomplete Cholesky factorization of C, i.e., one in which the
amount of fill-in in R is strictly limited, e.g., to just the original non-zero elements in C.
10
Other preconditioners are based on a sparsified, e.g., tree-based or clustered, approximation
to C (Koutis2007;KoutisandMiller2008;Grady2008;Koutis,Miller,andTolliver2009),
since these are known to have efficient inversion properties.
For grid-based image-processing applications, parallel or hierarchical preconditioners
often perform extremely well (Yserentant1986;Szeliski1990b;Pentland1994;Saad2003;
Szeliski 2006b). TheseapproachesuseachangeofbasistransformationSthatresembles
the pyramidal or wavelet representations discussed in Section3.5, and are hence amenable
to parallel and GPU-based implementations. Coarser elements in the new representation
quickly converge to the low-frequencycomponents in the solution, while finer-level elements
encode the higher-frequency components. Some of the relationships between hierarchical
preconditioners, incomplete Cholesky factorization, and multigrid techniques are explored
bySaad (2003) andSzeliski(2006b).
10
If a complete Cholesky factorization C = R
T
Ris used, we get
^
C = R
T
CR
1
=I and all iterative
algorithms convergein a singlestep, thereby obviating theneed to usethem, but the complete factorization is often
too expensive. Notethat incompletefactorization can also benefit from reordering.
C# PDF File & Page Process Library SDK for C#.net, ASP.NET, MVC
Image: Copy, Paste, Cut Image in Page. Link: Edit Redact Text Content. Redact Images. Redact Pages. Annotation & Text. Add Text Box. Drawing Markups. PDF Print. Work
delete blank page in pdf; delete pages from pdf online
C# PDF Page Insert Library: insert pages into PDF file in C#.net
Add and Insert Blank Pages to PDF File in C#.NET. This C# demo explains how to insert empty pages to a specific location of current PDF file.
delete page on pdf document; delete pages from a pdf in preview
A.5 Iterative techniques
753
A.5.3 Multigrid
One other class of iterative techniques widelyusedin computer vision is multigrid techniques
(Briggs,Henson,andMcCormick2000;Trottenberg,Oosterlee,andSchuller2000), which
have been applied to problems such as surface interpolation (Terzopoulos1986a), optical
flow(Terzopoulos1986a;Bruhn,Weickert,Kohlbergeretal.2006), high dynamic range tone
mapping (Fattal,Lischinski,andWerman2002), colorization (Levin,Lischinski,andWeiss
2004),naturalimagematting(Levin, Lischinski, and Weiss 2008),andsegmentation(Grady
2008).
Themain idea behind multigridis toform coarser (lower-resolution) versions of the prob-
lems and use them to compute the low-frequency components of the solution. However,
unlike simple coarse-to-fine techniques, which use the coarse solutions to initialize the fine
solution, multigrid techniques onlycorrect the low-frequency component of the currentsolu-
tion and use multiple rounds of coarsening and refinement (in what are often called “V” and
“W” patterns of motion across the pyramid) to obtain rapid convergence.
Oncertain simple homogeneous problems (such as solving Poisson equations), multigrid
techniques can achieve optimal performance, i.e., computation times linear in the number
of variables. However, for more inhomogeneous problems or problems on irregular grids,
variants on these techniques, such as algebraic multigrid (AMG) approaches, which look at
the structure of C to derive coarse level problems, may be preferable. Saad (2003) has a
nice discussion of the relationship between multigrid and parallel preconditioners and on the
relative merits of using multigrid or conjugate gradient approaches.
VB.NET PDF Page Insert Library: insert pages into PDF file in vb.
Moreover, you may use the following VB.NET demo code to insert multiple pages of a PDF file to a PDFDocument object at user-defined position.
cut pages from pdf online; delete pages out of a pdf
C# PDF File Split Library: Split, seperate PDF into multiple files
note, PDF file will be divided from the previous page of your defined page number which starts from 0. For example, your original PDF file contains 4 pages.
delete page in pdf online; delete pages from pdf reader
754
Computer Vision: Algorithms and Applications (September 3, 2010 draft)
Appendix B
Bayesian modeling and inference
B.1 Estimation theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
B.1.1 Likelihoodfor multivariate Gaussian noise . . . . . . . . . . . . . . 757
B.2 Maximum likelihood estimation and least squares . . . . . . . . . . . . . . . 759
B.3 Robust statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760
B.4 Prior models and Bayesian inference . . . . . . . . . . . . . . . . . . . . . . 762
B.5 Markov random fields. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763
B.5.1 Gradient descent and simulated annealing . . . . . . . . . . . . . . . 765
B.5.2 Dynamic programming. . . . . . . . . . . . . . . . . . . . . . . . . 766
B.5.3 Belief propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
B.5.4 Graph cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770
B.5.5 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 773
B.6 Uncertainty estimation (error analysis). . . . . . . . . . . . . . . . . . . . . 775
756
Computer Vision: Algorithms and Applications (September 3, 2010 draft)
The following problem commonly recurs in this book: Given a number of measurements
(images, feature positions, etc.), estimate the values of some unknown structure or parameter
(camera positions, object shape, etc.). These kinds of problems are in general called inverse
problems because they involve estimating unknown model parameters instead of simulating
the forward formationequations.
1
Computer graphics is a classic forward modeling problem
(given some objects, cameras, and lighting, simulate the images that would result), while
computer vision problems are usually of the inverse kind(given one or more images, recover
the scene that gave rise to these images).
Given an instance of an inverse problem, there are, in general, several ways to proceed.
For instance, through clever (or sometimes straightforward) algebraic manipulation, a closed
form solutionfor theunknowns cansometimes bederived. Consider, for example, thecamera
matrix calibrationproblem (Section6.2.1): given an image of acalibrationpatternconsisting
of known 3Dpointpositions, compute the 34 camera matrix P that maps these points onto
the image plane.
In more detail, we can write this problem as (6.336.34)
x
i
=
p
00
X
i
+p
01
Y
i
+p
02
Z
i
+p
03
p
20
X
i
+p
21
Y
i
+p
22
Z
i
+p
23
(B.1)
y
i
=
p
10
X
i
+p
11
Y
i
+p
12
Z
i
+p
13
p
20
X
i
+p
21
Y
i
+p
22
Z
i
+p
23
;
(B.2)
where(x
i
;y
i
)is the featureposition of theithpointmeasured in the image plane, (X
i
;Y
i
;Z
i
)
is the corresponding 3D point position, and the p
ij
are the unknown entries of the camera
matrix P. Moving the denominator over to the left hand side, we end up with a set of
simultaneous linear equations,
x
i
(p
20
X
i
+p
21
Y
i
+p
22
Z
i
+p
23
) =
p
00
X
i
+p
01
Y
i
+p
02
Z
i
+p
03
;
(B.3)
y
i
(p
20
X
i
+p
21
Y
i
+p
22
Z
i
+p
23
) =
p
10
X
i
+p
11
Y
i
+p
12
Z
i
+p
13
;
(B.4)
which we can solve using linear least squares (AppendixA.2) to obtain anestimate of P.
The question then arises: is this set of equations the right ones to be solving? If the
measurements are totally noise-free or we do not care about getting the best possible answer,
then the answer is yes. However, in general, we cannot be sure that we have a reasonable
algorithm unless we make a model of the likely sources of error and devise an algorithm that
performs as well as possible given these potential errors.
Inmachinelearning,theseproblemsarecalledregressionproblems,becausewearetryingtoestimateacontin-
uous quantity from noisy inputs, as opposed to adiscreteclassification task (Bishop2006).
B.1 Estimation theory
757
B.1 Estimation theory
The study of suchinference problems from noisy data is often called estimation theory (Gelb
1974),anditsextensiontoproblemswhereweexplicitlychoosealossfunctioniscalledsta-
tistical decision theory (Berger1993;Hastie,Tibshirani,andFriedman2001;Bishop2006;
Robert 2007). Wefirststartbywritingdowntheforwardprocessthatleadsfromourun-
knowns (andknowns) toa set of noise-corrupted measurements. We thendevise analgorithm
that will give us an estimate (or setof estimates) that are both insensitive to the noise (as best
they can be) and also quantify the reliability of these estimates.
The specific equations above (B.1) are just a particular instance of a more general set of
measurement equations,
y
i
=f
i
(x) + n
i
:
(B.5)
Here, the y
i
are the noise-corrupted measurements, e.g., (x
i
;y
i
)in Equation (B.1), and x is
the unknown state vector.
2
Each measurement comes withits associated measurementmodel f
i
(x), which maps the
unknown into that particular measurement. An alternative formulation would be to have one
general function f(x;p
i
)and to use a per-measurement parameter vector p
i
to distinguish
betweendifferent measurements, e.g., (X
i
;Y
i
;Z
i
)in Equation (B.1). Note that the use of the
f
i
(x) form makes it straightforward to have measurements of different dimensions, which
becomes useful when we start adding in prior information (AppendixB.4).
Each measurement is also contaminated with some noise n
i
.In Equation (B.5), we have
indicated that n
i
is a zero-meannormal (Gaussian) random variable witha covariance matrix
i
. In general, the noise need not be Gaussian and, in fact, it is usually prudent to assume
that somemeasurements may be outliers. However, we defer this discussion to AppendixB.3,
after we have explored the simpler Gaussian noise case more fully. We also assume that the
noise vectors n
i
are independent. In the case where they are not (e.g., when some constant
gain or offset contaminates all of the pixels in a given image), we can add this effect as a
nuisance parameter to our state vector x and later estimate its value (and discard it, if so
desired).
B.1.1 Likelihood for multivariate Gaussian noise
Given all of the noisy measurements y = fy
i
g, we would like to infer a probability distribu-
tion on the unknownx vector. We can write the likelihood of having observed the fy
i
ggiven
aparticular value of x as
L= p(yjx) =
Y
i
p(y
i
jx) =
Y
i
p(y
i
jf
i
(x)) =
Y
i
p(n
i
):
(B.6)
2
In theKalman filtering literature(Gelb1974),itis morecommonto usez instead ofyto denotemeasurements.
758
Computer Vision: Algorithms and Applications (September 3, 2010 draft)
When each noise vector n
i
is a multivariate Gaussian with covariance 
i
,
n
i
N(0;
i
);
(B.7)
we can write this likelihood as
L =
Y
i
j2
i
j
1=2
exp
1
2
(y
i
f
i
(x))
T
1
i
(y
i
f
i
(x))
(B.8)
=
Y
i
j2
i
j
1=2
exp
1
2
ky
i
f
i
(x)k
2
1
i
;
where the matrix norm kxk
2
A
is a shorthand notation for x
T
Ax.
The norm ky
i
y
i
k
1
i
is oftencalledtheMahalanobis distance (5.26and14.14) andis
usedtomeasurethedistance between ameasurement and the meanof a multivariateGaussian
distribution. Contours of equal Mahalanobis distance are equi-probability contours. Note
that when the measurement covariance is isotropic (the same in all directions), i.e., when
i
=2
i
I, the likelihood can be written as
L=
Y
i
(2
2
i
)
N
i
=2
exp
1
22
i
ky
i
f
i
(x)k
2
;
(B.9)
where N
i
is the length of the ith measurement vector y
i
.
We can more easily visualize the structure of the covariance matrix and the correspond-
ing Mahalanobis distance if we first perform an eigenvalue or principal component analysis
(PCA) of the covariance matrix (A.6),
=  diag(
0
:::
N 1
)
T
:
(B.10)
Equal-probability contours of the corresponding multi-variate Gaussian, which are also equi-
distance contours in the Mahalanobis distance (Figure14.14), are multi-dimensional ellip-
soids whose axis directions are given by the columns of  (the eigenvectors) and whose
lengths are given by the 
j
=
p
j
(FigureA.1).
It is usually more convenienttoworkwith the negative log likelihood, whichwecan think
of as a cost or energy
E=   logL =
1
2
X
i
(y
i
f
i
(x))
T
1
i
(y
i
f
i
(x)) + k
(B.11)
=
1
2
X
i
ky
i
f
i
(x)k
2
1
i
+k;
(B.12)
where k =
P
i
logj2
i
jis a constant that depends on the measurement variances, but is
independent of x.
Documents you may be interested
Documents you may be interested