Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
1999-01-25
2002-08-20
Lee, Thomas D. (Department: 2724)
Image analysis
Image enhancement or restoration
Image filter
C382S260000
Reexamination Certificate
active
06438269
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for multi-step filtering a spatial object in a spatial database system; and, more particulary, to a method for multi-step refiltering a candidate object, which is filtered by minimum bounding rectangle (MBR), by employing a minimum maximum point (MMP) filter to improve a performance of spatial query processing performed in filtering and refinement steps.
DESCRIPTION OF THE PRIOR ART
A spatial database system has been generally used for a geographic information system (GIS) involved with managements of resources and facilities, e.g., territory, resources, electricity, telecommunication facility. The GIS has a plurality of data composed of spatial data and non-spatial data, and it consists essentially of millions of spatial objects. One of spatial objects includes geometrical characteristics of an object. The spatial characteristics consist essentially of simple figures, which are made up of points, lines, rectangles, polygons, and complex figures composed of these simple figures. The spatial object having these spatial characteristics is filtered and refined in association with requiry for spatial query during the spatial query processing. The spatial object is managed by a spatial index method, and spatial query processing is processed by using information of spatial index. However, the spatial object which the spatial index should manage is very irregular, and generally consists essentially of a plurality of points, so that the spatial object can not be used rawly as a key of the spatial index.
Therefore, as shown in
FIG. 1
, a conventional spatial query processing is achieved as follows: at step
10
, a minimum bounding rectangle (Minimum Bounding Rectangle:MBR) is extracted in regard to a spatial object; at step
11
, a spatial index is constructed by using the Minimum Bounding Rectangle of object extracted at step
10
as a key of the spatial index; at step
12
, a spatial query is required by a user in regard to a spatial index key constructed at step
11
; at step
13
, a candidate object satisfactory to the spatial query is selected by comparing the minimum bounding rectangle (MBR) of a domain object given from the spatial query required at step
12
with the Minimum Bounding Rectangle of the spatial object constructed at step
11
; at step
14
, it is decided whether a candidate object is selected or not at step
13
; at step
14
, if a candidate object satisfactory to the spatial query is not selected at step
13
, another object is filter-processed while comparing the Minimum Bounding Rectangle of the domain object on demand of the spatial query at step
12
with the Minimum Bounding Rectangle of the non-filter-processed spatial object among the spatial object constructed at step
11
, on the other hand, if the candidate object is selected at step
13
, at step
15
the object is refinement-processed by comparing a real shape of the selected candidate object with real shape of the domain object given at the spatial query at step
12
; at step
16
, it is decided whether the object matches the query condition or not; at step
16
, if the object does not match the query condition, it goes back to step
13
and steps
13
and
15
are executed repeatedly; and, if the object matches the query, at step
17
it is contained in the satisfied object set.
However, because a filtering ratio of the Minimum Bounding Rectangle at the spatial query processing is low, there may be a problem in that lots of data should be processed at the refinement step at which it takes much time to operate the complex object.
To solve the problem, the method of multi-step filtering is provided, in which the candidate object filtered by using the Minimum Bounding Rectangle is refiltered by using various spatial filters whose ratio is higher than that of the Minimum Bounding Rectangular.
Accordingly, there have been provided various spatial filters surrounding an object, such as a rotated minimum bounding rectangle (RMBR), a minimum bounding circle (MBC), a minimum bounding ellipse (MBE), a minimum bounding convexhull, a minimum bounding n-corner (n-C) which consists of n points, maximum enclosed rectangle (MER) and a maximum enclosed line (MEL) which is the maximum value on x and y axises of the object. However, there is a problem in that these various filters can be generated only in regard to a areal object. Not only the processing of the areal object but also the processing of a linear object is indispensable in spatial database, so the filter considering the linear object and the areal object is minimum maximum point (MMP) filter which exists on the border line of the spatial object and consists of two or four points which have the minimum or the maximum value on x/y axis. This Minimum Maximum Point filter has the low consumption cost for generating or managing the filter, has the small memory space for storage, and has the characteristics that it can be applied not only to the areal object but also to the linear object. However, the method of milti-step filtering by utilizing Minimum Maximum Point filter can be applied to each well-known spatial operator used at the spatial database system is not provided yet.
SUMMARY OF THE INVENTION
It is, therefore, a primary object of the invention to provide a method for multi-step filtering by utilizing minimum maximum point (MMP) filter in a spatial data base system.
In accordance with one aspect of the present invention, there is provided a method of multi-step filtering by utilizing MMP filter in the spatial database system in order to improve performance of spatial query processing by refiltering candidate objects, which are filtered by using a minimum bounding rectangles (MBRs) surrounding spatial objects during the filtering step at spatial query processing by filtering and refinement steps in spatial database system, by using spatial filter, i.e., MMP filter.
REFERENCES:
patent: 5642288 (1997-06-01), Leung et al.
patent: 6018592 (2000-01-01), Shinagawa et al.
Choe Sang Kyu
Kim Jang Su
Kim Mi Yeon
Lim Su Mi
Brinich Stephen
Korea & Telecom
Lee Thomas D.
Staas & Halsey , LLP
LandOfFree
Method for multi-step filtering spatious objects by... 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 for multi-step filtering spatious objects by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for multi-step filtering spatious objects by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2934408