Image analysis – Image segmentation
Reexamination Certificate
1998-10-20
2001-05-08
Chang, Jon (Department: 2623)
Image analysis
Image segmentation
C382S199000, C382S203000, C382S225000, C382S241000
Reexamination Certificate
active
06229918
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for processing data, and in particular, a system and method for automatically detecting and tracking clusters of data points within a data set or data space with a radial spanning device.
2. Related Art
Automatic data detection and tracking of clusters of data points within a data space is becoming increasingly useful. Data space can be represented by data sets containing data points. Each data point can be represented by a single discrete value (one-dimensional) or by numerous values (multi-dimensional). Typically, each data set contains clusters of data points, each represented by similar or identical values. It is desirable to group this cluster of data points together within a class. For example, a data set containing health information might have data points represented by numerous health values, such as height, weight, body fat, blood pressure, pulse rate, etc. for males and females of all ages and of all ethnic origins. A typical search or query might require detection and tracking of clusters of data points having height-weight values for 20-year-old American males in the set of all conceivable height-weight pairs.
One way to find these data points would be to perform a digital database search. However, database searches do not detect and track clusters of data points, but instead typically only find and sort data values. Statistical sorting methods are used to track and group clusters of data points. However, these statistical methods are usually complex and require extensive memory and processing overhead.
In addition, automatic data detection and tracking is useful for image data. For instance, real-time vision-based systems typically use object tracking and object detection (also referred to as “blob tracking” and “blob detection”) systems to digitally detect and track objects within a data space, such as an image. The objects are typically nebulous collections of data points, such as image pixels, which satisfy some property and which often occupy a region or regions within the image.
Three methods commonly used to track blobs include moment computations, connected component analysis, and active contour models. With the moment computation method, some initial spatial filtering is assumed, where pixels outside of a given region are completely ignored. This process is sometimes referred to as windows-based tracking. In other words, “windows” force a restricted region of computation. Classification of pixels within a window can be used to compute position and approximate shape of the object by performing moment computations on the pixels in the window (the remaining pixels). For example, centroid and higher order moments can be computed. The centroid computation allows approximation of the position and the higher order moment computations aid in indicating the shape. Moment computations require O(n) operations and are frequently distracted by objects with similar attributes in the image.
In connected component analysis, pixels that are immediately adjacent to some seed pixel are tested for inclusion in a class. Pixels which fall into the class are added to the cluster and recursively analyzed for adjacency to other pixels and so on, until no other pixels are added to the cluster. Connected component analysis requires O(n) operations, where n is the number of pixels in the object. In addition, the morphological operations of dilation and erosion precede the analysis, and so the hidden coefficients can become large. Finally, connected component analysis is especially prone to being distracted by background pixels with similar properties.
The third method, active contour models, also referred to as snakes, in more efficient formulations requires between O({square root over (n)}) and O(n) operations, depending on the shape. This is because snakes only process pixels near the perimeter of an object. Snakes attempt to balance internal forces, which affect degree of curvature of the snakes, and image forces, which nudge the snakes toward image features such as edges. For object tracking, image forces would attract snakes toward boundaries between pixels that satisfy a class constraint and pixels that do not. Although snakes can be computed efficiently, they are known to be prone to distractions. In addition, in some cases (as, for example, when no high-frequency edges are detected), adaptations to make the snake work can require significant additional computation.
Therefore, what is needed is an effective and efficient technique for detecting and tracking clusters of data within a data space. What is also needed is a fast automatic data tracking technique that is robust to distractions and that can produce an approximate estimate of the characteristics of the clusters of data.
Whatever the merits of the above mentioned systems and methods, they do not achieve the benefits of the present invention.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention is embodied in a system and method for automatically detecting desired clusters of data points within a data set or data space with a radial spanning system and method. For example, the system and method detects and tracks clusters of data points within a data space.
The radial spanning system and method finds related data points or “blobs” of data defined by a cluster of data points. Given a probability density on data points for class inclusion and a seed point in the data set, the radial spanning system and method of the present invention finds an approximately, strongly connected cluster of data points of that class. The radial spanning system and method of the present invention finds “blobs” of data points defined by a cluster of data points having similar or identical values.
Specifically, exploratory spokes are traversed radially outward from the seed data point. Each spoke has a start point (seed point) and a final endpoint and is governed by forces based on underlying data points, class probability densities, internal expansion, and interspoke springs. The final endpoints of the spokes are considered perimeter data point endpoints and are connected to form a polygon that circumscribes the cluster of data points found. The radial spanning system and method is fast and robust. For example, for image applications, if n is the number of pixels in the cluster, the present invention performs O({square root over (n)}) operations for shapes with low eccentricities. Also, the radial spanning system and method of the present invention is relatively fast, and thus, would be valuable for data searching applications. In addition, the radial spanning system and method of the present invention has relatively high tolerance to distractions. Therefore, it is ideal for “blob tracking,” an activity typically performed in the real-time vision based systems as a means to quickly determine a region of interest within an image.
The foregoing and still further features and advantages of the present invention as well as a more complete understanding thereof will be made apparent from a study of the following detailed description of the invention in connection with the accompanying drawings and appended claims.
REFERENCES:
patent: 4739401 (1988-04-01), Sacks et al.
patent: 4802230 (1989-01-01), Horowitz
patent: 4901362 (1990-02-01), Terzian
patent: 4922915 (1990-05-01), Arnold et al.
patent: 5245674 (1993-09-01), Cass et al.
patent: 5604822 (1997-02-01), Pearson et al.
patent: 5748778 (1998-05-01), Ouoguchi
patent: 5995663 (1999-11-01), Itsuzaki et al.
Baroui et al. “Robust Segmentation of Echocardiographic Sequences Through Spatiotemporal Planning and by Knowledge-Based Local and Global Methods.” Computers in Cardiology 1998, pp. 453-456, Sep. 1998.
Chang Jon
DeFrank Edmond A.
Fischer Craig S.
Lyon, Harr & Defrank, LLP
Microsoft Corporation
LandOfFree
System and method for automatically detecting clusters of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for automatically detecting clusters of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for automatically detecting clusters of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2454650