|
|
A graphic tool for explaining ELBGELBG is a hard K-means vector quantization technique and derives directly from the simpler LBG algorithm. LBG, like many other traditional techniques, often, converges to a locally optimum quantizer, very far from an acceptable solution. In particular, the result obtained heavily depends on the initial conditions. ELBG, thanks to several improvements to LBG, is able to quickly escape from (or avoid) eventual bad local minima. The experimental results obtained show that ELBG is able to find better codebooks than previous works, that it is practically independent of the initial conditions and that the computational complexity is virtually the same as the simpler LBG algorithm. In this page, a Java applet illustrates how ELBG works. It shows how, iteration by iteration, the final codebook is obtained. In particular, it is possible to see the shifting of the badly positioned codewords, i.e. the mechanism allowing ELBG to escape from local minima. In the following, at first we briefly illustrate how this happens; after, the applet is inserted. For more details about ELBG, the reader is invited to look at the related papers:
It is possible to go directly to the applet. The applet can also be used for educational purposes for illustrating the basics of clustering and vector quantization. Local mimima and the shifting of the codewordsFor better explaining what we mean by "local minimum", let us examine Fig. 1. On the left side, part (a), we see that codeword number 4 generates an empty cell (i.e. no learning pattern is represented by it). By following the steps of the traditional LBG, it cannot move and will never represent any element. For this reason, we can say it is useless. The same authors of LBG, however, proposed some solutions to this problem such as the assigning of the codeword to a non-empty cell.
But, there is another problem that strongly limits the classical LBG and its solution appears a difficult task. Let us look at the right side, part (b), of Fig. 1. This configuration shows two clusters and three codewords. In the little cluster there are two codewords whereas, in the other, only one. The elements in the data set in the smaller cluster are all well approximated by the two related codewords. Instead, a lot of elements in the larger one are badly approximated by the related codeword. For this geometrical distribuition, it would be preferable that two codewords were inside the big cluster and only one in the other, but the LBG optimization algorithm, in this situation, does not permit the migration of a codeword from the little cluster to the big one becuase migrations happens only between contigous regions. This is a great limitation. To improve the performance of the LBG algorithm, we developed a criterion that identifies these situations and is able to find which codewords it is better to move and where they have to be placed, without any contiguity limitation (shifting of the codewords) At each iteration, several shiftings are performed; a shifting involves only local rearrangement of the codewords (three codewords at a time are considered). By avoiding the recalculation of the whole codebook after a single shifting, a lot of calculations are saved and the complexity of ELBG is, virtually, the same as LBG. The following pictures show how such migrations between non-contiguos regions (shiftings) happen.
The appletVery important: this applet uses Java Swing components. It is possible that your browser does not support such libraries. Quoting from Java official web site: "You can run Swing applets in any browser that has the appropriate version of
Java Plug-in
This is the first version of the applet. So, certainly, many bugs are present. Please, send any comments and/or suggestions to my e-mail address: gpatane@ai.unime.it |
