Image Processing Reference
In-Depth Information
the proportional factor
is less than 1, column j will be eliminated from the selection
process. This is due to the fact that if column j were selected, replacing it with
column i will always reduce tr[(H
T
H)
1
]. Therefore, column j can be removed from
the matrix. When S is small, a brute force search may
a
find the sample gray levels that
minimize tr[(H
T
H)
1
]. The calculation is to compute tr[(H
T
H)
1
] R
S
number of
times (assuming two or more samples may share the same gray level), where R is
the number of the rows in V that have survived pruning. When S is larger, an iterative
method such as Newton
-
Raphson or a genetic method may be applied. One simple
method is as follows:
a. Select an initial set of gray levels g(1), g(2), . . . , g(S).
b. For each iteration, perform steps c and d below.
c. For i
¼
1toS:
Calculate the change of tr[(H
T
H)
1
] with the replacement of g(i) with
g(i
1).
Calculate the change of tr[(H
T
H)
1
]
with the replacement of g(i) with
g(i
þ
1).
d. From the calculation in step c,
find the one that minimizes tr[(H
T
H)
1
].
The iteration ends when no replacement can make any improvement.
Otherwise, update the H matrix based on another set of S gray levels
and repeat step c until there are no more remaining sets of S gray levels to
select.
The calculation in step c can be substantial, especially when K (model rank) is large,
because inversion is computationally expensive for large matrices. However, we can
take advantage of the fact that, on each pass, only one vector in H is replaced, and
the calculation can therefore be simpli
ed. If U denotes the updated matrix of H
T
H
after g(i) is replaced by g(j), then
1
U
1
¼
H
T
H
h
(
i
)
h
(
i
)
T
þ
h
(
j
)
h
(
j
)
T
(
9
:
139
)
where h(i) is the ith column of V. Using the Woodbury identity twice, Equation
9.139 can be simpli
ed as
1
U
1
¼
W
1
W
1
h
(
j
)
h
(
j
)
T
W
1
þ
h
(
j
)
T
W
1
h
(
j
)
(
9
:
140
)
where
1
W
1
¼
H
T
H
h
(
i
)
h
(
i
)
T
h
i.
1
h
i
1
h
(
i
)
h
(
i
)
T
H
T
H
1
1
h
(
i
)
H
T
H
h
(
i
)
T
H
T
H
¼
(
9
:
141
)
Search WWH ::
Custom Search