Image analysis – Applications – Target tracking or detecting
Reexamination Certificate
1999-11-08
2003-08-26
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Applications
Target tracking or detecting
C382S295000, C345S589000, C348S169000
Reexamination Certificate
active
06611609
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to methods of data structure characterization, indexing, storage and retrieval; and more particularly comprises a method which pre-selects pixels in data structures which have associated therewith significant intensity and/or color gradient(s) with respect to surrounding pixels, in, for instance, “X” and/or “Y” and/or “Z” direction(s), then utilizes said pre-selected pixels in data structure characterizing spatial first and second central moment calculations. Data structure characterizing vector(s) are constructed from frequency-of-occurance integer counts of said pre-selected pixels, as well as spatial data structure first central moment values, and non-degenerate parameter(s) determined from second central moment dependent Eigenvalues. Multiple data structure characterizing vector(s) can be constructed, each utilizing pixels which have associated therewith intensity and/or color gradient(s) within specific ranges.
BACKGROUND
A Co-pending Parent patent application Ser. No. 09/287,961, describes a related method of data structure characterization, indexing, storage and retrieval. Said method comprises calculation and use of a translation, rotation and scaling invariant index which results from concatenating a series of Eigenvalue calculation mediated non-degenerate index elements, determined at a plurality of hierarchical data structure depth levels. The methodology taught in said 961 Application, while providing valuable and previously unreported utility, can, however, be somewhat computationally intensive in that all pixels in a data structure are typically utilized. At the outset it is disclosed that the present invention provides methodology which can reduce said computational intensive aspect of that associated with the 961 Application invention, by performance of a frequency-of-occurance-based pre-selection of pixels in a data structure which have associated therewith significant intensity and/or color gradients with respect to surrounding, (typically first neighbor), pixels. Said pixel pre-selection methodology, which requires calculation with complexity on the order of “O(n)”, can be applied to reduce the number of pixels utilized in calculating spatially based first central moment values and non-degenerate parameters determined from second central moment values, which spatially based first central moment values, and non-degenerate parameters determined from second central moment values are calculated, for instance, as in the 961 Application methodology, (which 961 Application methodology, again, typically, though not necessarily, involves utilization of all pixels in a data structure, and requires calculation complexity on the order of “O(n
2
)” in the absence of the benefit of the present invention pixel pre-selection methodology).
As described in the 961 Parent Application, data structures, such as two dimensional picture graphic pixel arrays, are being generated at an ever increasing rate. For instance, algorithm generated and scanned computer screen images, X-ray, CT, MRI and NASA satellite, space telescope and solar explorer systems generate thousands of images every day. To make optimum use of said images however, convenient methods of data characterization, indexing, storage and retrieval are required. For example, a medical doctor might obtain an X-ray image of a patient's chest but has to rely on “diagnostic art” to arrive at a diagnosis. Were it possible to determine an index which characterizes said X-ray image and also enable easy storage and retrieval thereof, it would be possible to compare said index to a catalog of indices of various X-ray images which are known to be associated with various healthy or pathologic conditions. Thus diagnosis could be moved toward the very desirable goal of being objectively definite in a mathematical sense.
Continuing, it must be understood that conventional data are stored as text, with organization being in terms of alphebetic and numerical value fields. Examples are business product, customer lists, sales data etc. To retrieve such data a user must issue a query in text format, similar to what is done in natural languages. It is, however, essentially impossible to use such an approach to store and retrieve the contents of most data structures, (two dimensional picture graphic data images for example), because there is no convenient manageable way to describe such data structures in terms of said alphabetic and numerical value fields. Data Structures are instead typically stored in the form of compressed digital files of hundreds of thousands of binary numbers, and said storage technique does not facilitate easy data structure indexing, characterization, storage and retrieval. And, while it is possible to describe a data structure with a text Index, to examine the data structure data still requires that the data associated with said index be retrieved. It is also possible to assign an arbitrary serial number to a data structure to facilitate data storage and retrieval, but under this approach the serial number provides no insight to the data, and again, to examine data structure, requires accessing the data per se.
A preferred approach to the characterization of data structures, which provides an index for use in storage and retrieval thereof, is to base the index on features in the data structure. To arrive at such an index, however, is typically computationally complex, requiring hundreds of thousands of calculations. That is, determination of said index must typically be extracted from a data structure “off-line”. Characteristic indices so determined are called “structure indices”, and ideally render a concise description, not only of a structure color and intensity content on a row and column basis, but also of the nature and shape of objects therein. A problem arises, however, in that many data structure features can not be easily described. Geometric shapes in a data structures, for example, can require a combination of text annotation and numeric values and often the result is not at all concise.
Relevant considerations in developing an approach to extracting “image indices” from a data image or data structure include:
1. Uniqueness—different images/data structures should have different associated indices, (i.e. an image index should be non-degenerate);
2. Universality—image/data structure indices must be extractable from essentially any kind of image to be characterized, stored and retrieved by use thereof;
3. Computation—image/data structure indices must be easily computed from any data structure to be characterized, stored and retrieved by use thereof, and computation complexity should be kept to a minimum possible;
4. Conciseness—image/data strucutre indices must concise and easy to store;
5. Invariance—descriptive features in an image/data structure must tolerate change of scale, rotation and translation transformations, image object position shifting, calibration of color and pixel intensity and return essentially unchanged image indices;
6. Noise resistant—random noise entry to image/data structure should not significantly change the image index extracted therefrom.
Previous attempts at extracting an index for an image/data structure have focused on use of:
pixel intensity and color distributions, (see an article titled “Query By Image And Video Content: The QBIC System”), IEEE Trans. on Computers, (September 1995));
pixel texture patterns (see a book titled “Digital Image Processing”, Gonzales, Addison-Wesley Pub. (1992)); and
edge and boundary-line shapes, (see a book titled “Digital Image Processing And Computer Vision”, Schalkoff, John Wiley & Sons, (1989)),
etc. as the basis of approach. These techniques are mainly based on the calculation of the statistics of a data image in a pixel arrangement. Said techniques often lack universality in that they work when applied to a certain type of data image, but not when applied to other types of data images. Moreover, many previous approaches are not image transformation invariant and do not tolera
Mehta Bhavesh M.
Patel Kanji
The Board of Regents of the University of Nebraska
Welch James D.
LandOfFree
Method of tracking changes in a multi-dimensional data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of tracking changes in a multi-dimensional data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of tracking changes in a multi-dimensional data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3122484