Thread Subject: tikhonov regularization

hi,
i've got rather theoretical question. it's about tikhonov
regularization. i've got some data that are points (x,y) of
contours of some object (found in CT images, image(2) is
the continuation of an image(1)).
the thing i must do is correct these points, using tikhonov
regularization. but as in this moment this is totally
abstract for me, i read what i found on google.
but the problem is, that i'm not sure if i understand:
1. what is tikhonov regularization in general
2. how can i use it in my problem?

if any of You are more familiar with this subject, i would
be really gratefull for any
suggestions!

kind regards,
    misty

"misty m." <donotspam@smth.be> wrote in message
<g1dt4q$qvm$1@fred.mathworks.com>...
> hi,
> i've got rather theoretical question. it's about tikhonov
> regularization. i've got some data that are points (x,y) of
> contours of some object (found in CT images, image(2) is
> the continuation of an image(1)).
> the thing i must do is correct these points, using tikhonov
> regularization. but as in this moment this is totally
> abstract for me, i read what i found on google.
> but the problem is, that i'm not sure if i understand:
> 1. what is tikhonov regularization in general
> 2. how can i use it in my problem?
>
> if any of You are more familiar with this subject, i would
> be really gratefull for any
> suggestions!

I think this covers the topic fairly well:

http://en.wikipedia.org/wiki/Ridge_regression

I'm not sure I'd do a better job of it anyway.
I'd suggest reading it carefully, and if you
have specific questions, ask again.

In general, these regularizers are simply a way
to bias the result of a regression problem.
The bias chosen can be a variety of things.
You can bias the parameters towards zero,
much as the standard ridge regression does.
Or you can bias towards a smooth result, as
you will find in a smoothing spline, or my
own gridfit on the file exchange.

These biases all come down to a way of
imparting your own prior knowledge of the
system under study into that model. (I do
tend to think with a moderately Bayesian
point of view here.)

There are several ways one might think of
where a regularization might apply in such
a problem. You will need to be more specific
as to what correction you are looking for.

HTH,
John

ok, i'll try to be more specific.
the point is, that i do not understand the whole equation.
as i mentioned before, i've got some data taken from CT
images. this data are points of contours (x,y). for each
image i must look back on 10 images before and try to
minimalize the difference. looking on all these thikonov
equations (that i simply do not understand too well), i
think that the 'second part' of equation can be written as:

sum (from k=1:10) (x(k+1) - x(k)).^2

my questions are:

1. what is the first part, i mean: min(V(f(x),y)), (btw.
isn't y the same as f(x)?). i really do not know how to
understand the first part of equation (i hope the second
one is correct)

2. do i need to calculate it separately for x-points and y-
points?


sorry for my annoying questions..

i forgot to put 'lambda' in the second part of my equation:

lamba*(sum (from k=1:10) (x(k+1) - x(k)).^2)

so my third question is:
3.how to calculate lambda?

"misty m." <donotspam@smth.be> wrote in message
<g1e85b$da0$1@fred.mathworks.com>...
> ok, i'll try to be more specific.
> the point is, that i do not understand the whole equation.

What equation?

> as i mentioned before, i've got some data taken from CT
> images. this data are points of contours (x,y). for each
> image i must look back on 10 images before and try to
> minimalize the difference. looking on all these thikonov
> equations (that i simply do not understand too well), i
> think that the 'second part' of equation can be written as:
>
> sum (from k=1:10) (x(k+1) - x(k)).^2
>
> my questions are:
>
> 1. what is the first part, i mean: min(V(f(x),y)), (btw.
> isn't y the same as f(x)?). i really do not know how to
> understand the first part of equation (i hope the second
> one is correct)

The first part of what?

> 2. do i need to calculate it separately for x-points and y-
> points?

Sorry, but these are just semi-random
equation fragments. Without far more
context, this all means nothing to me.

John

i know my messages are quite messy:/
my problem is that i read and read about thikonov
regularization and still do not understand how to use it in
my problem.

> What equation?

i need an equation to count new points..
and these on wiki or other articles don't suit to my
problem.

i'll try to ask more clearly - how i can use thikonov
regularization in my problem (that can be described as
smoothing control points of contours)

"misty m." <donotspam@smth.be> wrote in message
<g1ep36$ru5$1@fred.mathworks.com>...


>
> i'll try to ask more clearly - how i can use thikonov
> regularization in my problem (that can be described as
> smoothing control points of contours)
>

You already answer to your own:

- control points of the contour : this is your model
- smoothing: this is the tikhonov regularization

All you need is writing down your model (control ->
contour), writing down the least-square distance of the
model to your data, then add the smoothing term (some sort
of norm on the control points). Minimizing the combined sum
(this can be done with a "\" operator when the model is linear).

Lambda is a parameter that allow to control the level of
smoothing.

Estimate lambda is always a tricky problem. There are many
methods, the most easy is L-curve, the most well-known is
cross-validation, and there is a bunch of exotic methods
that are used more or less successful depending on the problems.

Bruno

> All you need is writing down your model (control ->
> contour), writing down the least-square distance of the
> model to your data, then add the smoothing term (some sort
> of norm on the control points). Minimizing the combined
sum
> (this can be done with a "\" operator when the model is
linear).

i know that my another question probably is annoying, but
according to wikipedia, generalized tikhonov regularization:

 ||Ax - b||.^2 + || x-xo||.^2

what is that?? i understand that 'x' is my point in 'x-
axis' to which i want my point (xo) from another image be
closer.
but what is A? what is b??

should i do separate regularization for x-coefficients and
y-coefficients?

"misty m." <donotspam@smth.be> wrote in message
<g1gfqd$drv$1@fred.mathworks.com>...
> > All you need is writing down your model (control ->
> > contour), writing down the least-square distance of the
> > model to your data, then add the smoothing term (some sort
> > of norm on the control points). Minimizing the combined
> sum
> > (this can be done with a "\" operator when the model is
> linear).
>
> i know that my another question probably is annoying, but
> according to wikipedia, generalized tikhonov regularization:
>
> ||Ax - b||.^2 + || x-xo||.^2
>
> what is that?? i understand that 'x' is my point in 'x-
> axis' to which i want my point (xo) from another image be
> closer.
> but what is A? what is b??
>

x is your control points, b is your data, A is the matrix of
your model, x0 is a guess of control point (could be zero).

Bruno

> x is your control points, b is your data, A is the matrix
of
> your model, x0 is a guess of control point (could be
zero).
>


to be 100% sure:
let's say there are points (x,y) from the 1st image and 2nd
image, where 2nd one is the next CT scan, i mean 2nd one is
after the 1st and we want points from 2nd image to be close
to the points from the 1st image

x = control points - from my 2nd image? (so i need this
equation to be calculated twice - firstly for x-points and
then for y-points?)

b = data (all control points (x,y) from the second image?)

hmm, what is the difference between x and b? is it that for
example x has all x-points , and b has x-points and y-
points?

A = my model.. ? (control points (x,y) from the 1st image?)

x0 = (or y0?) - the point from the second picture that i'm
actually testing?

It looks like you have the data but do not know yet your
model. Before asking question about Tichkonov, you should
ask what is your control point and model. This we cannot
answer for you.

Bruno

as i want points from n-th image to be more similar to the
points (n-th -1 ) image, isn't (n-th -1) image my model?
(for the n-th image) ?

"misty m." <donotspam@smth.be> wrote in message
<g1gsbm$86a$1@fred.mathworks.com>...
> as i want points from n-th image to be more similar to the
> points (n-th -1 ) image, isn't (n-th -1) image my model?
>

Not to my mind. A model is a *function* that maps something
(control points) to something else. A model is not a
collection of data (numbers, points, ...). In the article
you have read, the model is the function that maps x -> A.x.

Bruno

my points are the contours of something that we can call
circle. so probably my model is the equation for the
cricle, isn't it?

my points are the contours of something that we can call
circle. so probably my model is the equation for the
cricle, isn't it?

my points are the contours of something that we can call
circle. so probably my model is the equation for the
cricle, isn't it?

"misty m." <donotspam@smth.be> wrote in message
<g1gu5q$n2v$1@fred.mathworks.com>...
> my points are the contours of something that we can call
> circle. so probably my model is the equation for the
> cricle, isn't it?
>

That sounds more plausible to me, yes.

If you want to understand model, tichkonov, etc.. a
classical example is using B-spline to *approximate* a
correction of noisy data.

Bruno

ok, it begins to be more clear to me. but can You also
explain me the difference between x and b?

x = control points x or control points y

b = data - all control points (x,y) ?

that is the thing that is still not too clear to me.

i was using splines, but actually didn't ever interested
too much on how it works. maybe You are right - this is the
best time to take a more particular look on them.

"misty m." <donotspam@smth.be> wrote in message
<g1gviq$702$1@fred.mathworks.com>...
> ok, it begins to be more clear to me. but can You also
> explain me the difference between x and b?
>
> x = control points x or control points y
>
> b = data - all control points (x,y) ?
>
> that is the thing that is still not too clear to me.
>
> i was using splines, but actually didn't ever interested
> too much on how it works. maybe You are right - this is the
> best time to take a more particular look on them.

x: control points, that are points that determine the shape
of your spline. For each set of positions of points there
correspond a unique spline. "Points" could be a understood
in a more abstract way: such as a linear coefficients of the
splines in "some" basis.

b: is data, something you obtain by meant of measuring from
different manner (e.g., points on the contour of an image
taken by a camera), and you want your model pass through it.

In the smoothing spline approximation problem, usually
number of control points are small (e.g., 20), number of
data is large (e.g., 500). If you increases the number of
control points, you will get a spline that oscillate
strongly due to noise in the data. You then need to add a
regularization term to limit the oscillation, and smooth
your spline curve, that's the Tichkonov role.

I think you are now ready to dig by yourself into it.

Bruno

thanks a lot for all Your replies and patience! You really
helped me a lot!

 kind regards,
         misty

hi,
i thought the whole thing over.
equation of ellipse (which is my model) is:

ax.^2 + bxy + cy.^2 + dx + ey + f = 0

ok,
so x(control points) is:
x = [x.^2, xy, y.^2, x,y,1]

am i correct?

A = [a,b,c,d,e,f]

d - my data


i have only data (x,y points through which i was my ellipse
to come), how can i get a,b,c,d,e,f coefficients??

kind regards,
     misty

"misty m." <donotspam@smth.be> wrote in message
<g1mbjq$2nd$1@fred.mathworks.com>...
> hi,
> i thought the whole thing over.
> equation of ellipse (which is my model) is:
>
> ax.^2 + bxy + cy.^2 + dx + ey + f = 0
>
> ok,
> so x(control points) is:
> x = [x.^2, xy, y.^2, x,y,1]
>
> am i correct?
>
> A = [a,b,c,d,e,f]
>
> d - my data
>

There are several routine in FEX, or alternatively in this
thread:

http://www.mathworks.com/matlabcentral/newsreader/view_thread/159497

Bruno