Image analysis – Learning systems – Neural networks
Reexamination Certificate
2001-12-05
2003-08-19
Ahmed, Samir (Department: 2623)
Image analysis
Learning systems
Neural networks
C382S233000, C382S244000
Reexamination Certificate
active
06608924
ABSTRACT:
BACKGROUND OF THE INVENTION
My invention relates to compressing and decompressing data (acoustic and still/moving images). More precisely, the invention is directed to the still document image data compression utilizing the adaptive vector quantization theory (AVQ) and its implementation as reflected in the Kohonnen Self Organizing Feature Map (KSOFM) neural model and the Adaptive Resonance Theorem (ART). My work is in the same direction of the well known Wavelet and JPEG image compression techniques with the major difference in the make of the lookup tables, i.e., codebooks. The formation of the lookup tables in my model is carried out via the training of hybrid SOFM&ART neural models, with some modification. The main motivation of my invention is the poor performance (and sometimes the inability to perform at all) of the aforementioned peer techniques in some image domains (e.g., document image compression), as we experimentally discovered. For contrast, in some document image domains, my model compression engine performs exceptionally well, both in the compression ratio and the image quality compared to Wavelet & JPEG. For some very complex documents with complicated colors charts writings, and backgrounds, Wavelet (represented by the state of the art commercial product, DjVu Solo) failed to compress/decompress the document correctly, while maintaining a competitive compression ratio. Their recovered decompressed documents lost the original colors and/or text is distorted, in some places. The DjVu applies the character recognition approach in compressing documents, a feature which caused such deficiency in the compression performance. In the same document domain, my model is able to recover correctly “all” documents that the peer technique could not recover. Even though another Wavelet commercial product, MrSID, was able to recover such images correctly, as pictures instead of documents, my technique performed much better in compression ratio for the same (or better) visual quality.
My model, as well as Wavelet/JPEG, utilizes the vector quantization (VQ) approach. The VQ mechanism clusters the input subunit vectors (k-dimension) via the mapping of all similar (based on some error difference) into one representative vector called centroid. A difference measure between vectors X and Y is the squared error ∥X−Y∥
2
, Euclidian distance. All obtained centroids are stored in a simple lookup table (codebook) which is to be used at the encoding/decoding phases. The manufacturing mechanism and the nature of the generated codebook is the key distinction of our work.
Based on the VQ approach, a new hybrid neural model (CD) that combines some features of the well known neural models: KSOFM and ART. The CD model follows the main theme of both models and adds its own modifications to exact details of their learning mechanisms. The Kohonnen SOFM is an unsupervised neural model implementation of the AVQ theorem. It uses a set of neurons each of which is connected to the input training vector via a set of weights connections called neuron weight vectors (NWVs). The NWVs are initialized to some random small values (or some pre-known values) then with each introduction of a training vector X, the closest NWV to X (based on their Euclidean distance, ED) will be declared a winner and brought closer to X (and for that matter, all similar vectors to X). Not only the winner NWV will be updated, but also all of its neighborhood vectors with decreasing values. The training of the SOFM engine is unsupervised and theoretically terminates at centroid conversion time, i.e., when the movement of all centroids is virtually zero, for two consecutive training epochs. The above stopping condition results in a training time complexity of Q(N
2
), where N is the input/centroid vector length.
The other clustering neural model is the ART. Even though SOFM and ART share the same goal (AVQ), yet their training is totally different. In ART, upon receiving an input subunit, a quick scan to the existing set of centroids will result in the formation of a possible winners set of centroids, PWC, of the input subunit. Among the PWC members, the input subunit will be more accurately (pixel-by-pixel) matched to each member centroid; and the closest match is announced the winning centroid. A failure to identify a subunit membership, to some class (under some matching constraints), forces the addition of a new centroid with the subunit value, as the only member in a newly formed class.
In our unsupervised clustering CD model, the centroids codebook table is initially empty. As the training progresses, we apply the ART philosophy: “if there is no true winner centroid for a subunit, add the subunit as a new centroid in the codebook”. The decision of a true winner centroid, for an input subunit, is made in two phases. We initially construct a PWC set (stated above) of centroids that have the number of pixel differences, with the input subunit, less than some tight threshold, T
1
. Then, comparing the input subunit with each member in the PSC set, we add up the pixels' error differences (pixel by pixel) to obtain a mean error value, ME. The centroid with the minimal ME is announced the true winner of the input subunit, i.e., its representative, given that the computed ME does not exceed some threshold, T
2
. Only the true winner centroid value is updated, using the input subunit. Otherwise, if there is no true winner for the input subunit (based on T
1
&T
2
above), the input subunit is to be added to the codebook, as its own new centroid. Thus, in deciding the true winner, we follow the sole of the ART. But, in the process of updating the winning centroid, we follow the mechanism of SOFM “winner-takes-all”. The winning centroid only will be moved closer to the input subunit, by updating its value to be the average of all of its class members with the newly added subunit. Thus, we can say that our CD model is a mixture of a simplified SOFM and ART models, gaining the training speed/simplicity of SOFM and the ART elasticity/accuracy.
SUMMARY OF THE INVENTION
We present a direct classification (DC) model for pictorial document or acoustic data compression which is based on the adaptive vector quantization theory (AVQ). We deploy a quantization mechanism that utilizes some concepts of the SOFM and ART neural net models. Starting with an empty synaptic weight vectors (code book), a very simplified ART approach is adopted by the DC model to build up the codebook table. Then, the training and the updating of the centroids in the codebook is based on some of the KSOFM rules. Simply, the DC model divides the input data (e.g., document image) into N same size (n
2
gray/colored pixels) subunits. Then, divide the N subunits into L equal size regions, each of s subunits (s=N/L), grouping all same index i
k
(0<=k<=(s−1) subunits in all regions into a “run
i(k)
” of size L subunits. Notice that, selection of subunit i
k
from a given region, when constructing a run, is in any order, yet is consistent over all regions per each run. The concatenation of run
1
through runs
L−1
forms the total input domain of subunits. For some input domains, e.g., pictorial images, the construction of the regions and the selection of subunit per a region is done for one subunit selection only (total L subunits) to initialize the L centroids in the codebook. Then, after codebook initialization, the input subunits domain is just the remaining N-L subunits scanned sequentially, with no regional divisions. Then, the DC model clusters the input domain into classes of similar subunits (close orientation vectors); each class will have a vector representative, called a centroid. The mechanism incrementally constructs a codebook of centroids to be placed in the DC neurons synaptic weight vectors. Each centroid will have a limited size (size=TrainSetMax) subset out of all classified subunits (SCS), that will be the only contributing subunits in its training. The reason we restrict the centroid updating
Ahmed Samir
Becker R W
New Mexico Technical Research Foundation
R W Becker & Associates
LandOfFree
Neural network model for compressing/decompressing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Neural network model for compressing/decompressing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Neural network model for compressing/decompressing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3111602