Video image searching method and apparatus

A video image searching method and apparatus that partially restores a picture according to a determined image restoring ratio, in order to reduce the searching time required compared to complete restoration of the picture as in conventional video image search. In the image searching method and apparatus, a dominant image element is extracted using a fractal image compression method, so that the image is partially restored, to thereby effectively search for the video image.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of Korean Application No. 97-76417, filed Dec. 29, 1997 in the Korean Patent Office, the disclosure of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a video image searching method and apparatus, and more particularly, to a video image searching method and apparatus in which a dominant image element is extracted by a fractal video image compression method and the video image is partially restored.

2. Description of the Related Art

In a fractal video image compression method that assumes a video image is comprised of fixed points of various equations, a target video image is divided into non-overlapping range blocks. In addition, the target video image is divided into domain blocks which are larger than the range blocks and allowed to overlap, and a search for a transform linear equation corresponding to the fixed points is performed. In this way, rather than compressing the image data itself, the fractal video image compression method compresses the image made up by the transform linear equation. A conventional fractal video image compression circuit and method, as disclosed in U.S. Pat. Nos. 5,384,867 and 5,430,812, includes a controller which receives image data to process the image data into blocks, such as range blocks and domain blocks, and supplies the processed data to a plurality of transform circuits and feed circuits. Each transform circuit receives data from the controller and a feed circuit, and compares blocks through a parallel process to generate a fractal transform value in which the image data is expressed in a compressed form.

It is difficult, using conventional methods, to completely search for the video image using a video image data base, and therefore, in order to determine whether the video image data retrieved from the data base is appropriate for the desired image, it is necessary to use more video image data than the video image for which the search is to be made. As a result, the video image data retrieved from the video image data base must be restored into images, and pictures which are not necessarily required to determine whether the retrieved video image is appropriate for the desired video image are restored, which unnecessarily consumes a significant amount of time. Furthermore, adopting the complete restoration causes a considerable loss of time since it takes time for the retrieved video image data to be restored into a complete video image.

SUMMARY OF THE INVENTION

To solve the above problems, it is an object of the present invention to provide a video image searching method in which a video image is partially restored according to a predetermined video image restoring ratio, to thereby reduce the amount of searching time.

It is a further object of the present invention to provide a video image searching apparatus for performing the video image searching method.

Accordingly, objects of the invention are achieved by a method of searching for a video image from a plurality of image data stored in a data base that includes searching and retrieving from the data base one of the stored image data similar to the image, partially restoring the one retrieved image data, and comparing and evaluating the partially restored one retrieved image data with the image.

In a preferred embodiment, the method includes determining an image restoring ratio of retrieved video image data, and extracting a dominant image element from the video image. The extracting step includes compressing the video image through transform linear equations, determining a frequency of generation of fixed points of the linear equations according to values of decision elements of a matrix in an equation from which the fixed points are generated, and extracting the dominant image element according to a desired probability. In the preferred embodiment, the one retrieved image data corresponds to the extracted dominant image element according to the determined image restoring ratio.

Further objects of the invention are achieved by an apparatus for searching for an image in which an image restoring ratio determination unit determines an image restoring ratio, and an image element extracting unit partially restores the image. An image restoring unit partially restores image data corresponding to the partially restored image, according to the image restoring ratio, and a comparing unit compares the restored image data and the image.

In the preferred embodiment, the image element extracting unit includes a compression unit that compresses the image using a transform linear equation, and a determining unit that determines a frequency of generation of fixed points of the transform linear equation according to values of decision elements of a matrix in an equation from which the fixed points are generated. An extracting unit extracts the partially restored image according to a desired probability such that the frequency of generation of the fixed points corresponds to the probability.

Further objects of the invention are achieved by an apparatus for searching for an image in which an image restoring ratio determination unit determines an image restoring ratio, and a dominant image element extracting unit extracts a dominant image element from the image, using fractal image compression. A search unit retrieves image data from an image data base corresponding to the extracted dominant image element. An image restoring unit partially restores the retrieved image data from the search unit according to the image restoring ratio, and a comparing unit compares the restored image data and the image.

In the preferred embodiment, the dominant image element extracting unit includes a compression unit that compresses the image using a transform linear equation, and a determining unit that determines a frequency of generation of fixed points of the transform linear equation, according to values of decision elements of a matrix in an equation from which the fixed points are generated. An extracting unit extracts the dominant image element according to a desired probability, such that the frequency of generation of the fixed points corresponds to the probability.

Further objects of the invention are achieved by an apparatus for searching an image from a plurality of image data stored in a data base that includes a search unit to search and retrieve from the data base one of the stored image data similar to the image. A restoring unit partially restores the one retrieved image data, and a comparator compares the partially restored one retrieved image data with the image.

DESCRIPTION OF THE PREFERRED EMBODIMENT

As shown in FIG. 1 , an image f is divided into a number of range blocks that includes R 1 , R 2 , . . . , Ri, . . . , Rn that are to be coded into a fractal image. At this time, image f R 1 U R 2 U . . . U Rn, and if i j, Ri Rj 0. Thus, the range blocks cover the image without overlapping. Also, image f is divided into domain blocks D 1 , D 2 , . . . , Dj, . . . , Dm, which are greater in size than each of the range blocks, and which may overlap. In a fractal compression method according to a preferred embodiment of the present invention, the video images are compressed into transform linear equations by searching for a domain block closest to each of the range blocks Ri through a transform linear equation. That is, given an arbitrary range block Ri, there is a search for a domain block Dj and an Affine transform linear equation Wi corresponding to the range block Ri, so that Ri Wi (Dj), where Wi indicates the Affine transform linear equation as shown in Equation 1. In Equation 1, a i , b i , c i , d i , e i , f i and s i are elements of the matrixes. W i ( ) = ( a i b i 0 c i d i 0 0 0 s i ) ( ) + ( e i f i 0 ) ( 1 )

In Equation 1, the decision element of a 3 3 matrix determines the probability. That is, if W 1 , W 2 , . . . , Wm are each substituted for Wi in Equation 1 to form a transform linear equation of an image, and if A 1 , A 2 , . . . , Am indicates a 3 3 matrix of each of the equations and A i indicates the decision element of each matrix, the probability of the transform linear equation W i is A i k = 1 m A k .

That is, when W i is used, rather than regenerating the whole image, A i k = 1 m A k

of the whole image is regenerated, making the frequency of generation of fixed points correspond to, or equal to the probability. In this way, since there is no need to completely restore an image, the image is restored by the determined restoring ratio to compare the video images, thereby reducing the amount of searching time. As a result, less time is wasted compared to the conventional art which requires time to completely restore the retrieved image. In a preferred embodiment of the present invention, the probability is related to each element of the Affine transform linear equation, and the restoring ratio is the total probability, which includes various Affine transform equations.

As illustrated in FIG. 2 , an image searching apparatus according to a preferred embodiment of the present invention includes a function of controlling a restoring ratio according to a partial picture restoring method, to thereby shorten the total searching time. In FIG. 2 , an image restoring ratio determiner 10 determines an image restoring ratio of the retrieved video image data, to partially restore the image. A dominant image element extractor 20 extracts a dominant image element from an image to be searched for, using a fractal image compression method. Here, the extraction of the dominant image element means the partial restoration of the image, to a degree capable of being used to search for the image. A search unit 30 searches for data similar to the extracted image compressed data, from a video image data base 60 . An image restoring unit 40 partially restores the video image data retrieved from the data base 60 , according to the predetermined image restoring ratio. A comparing and evaluating unit 50 compares the restored image with the image to be searched for and evaluates the images to generate a result of the video image search.

If the result is not a desired search result, the image restoring ratio is reset by the image restoring ratio determiner 10 , and then the video image search is performed again. The dominant image element extractor 20 includes a compression unit for compressing the video image using linear equations, a determining unit for determining the frequency of generation of fixed points of the equations according to the values of the decision elements of the matrix in an equation from which the fixed points are generated, and an extracting unit for extracting a dominant image element according to a desired probability. The frequency of generation of the fixed points is equal to the desired probability.

In FIG. 3 , a method for searching for a video image according to the present invention includes the steps of determining an image restoring ratio of retrieved video image data (step S 30 ), extracting a dominant image element of an image to be searched for, using a fractal image compression method (step S 32 ), searching for data similar to the extracted image compressed data in a video image data base (step S 34 ), partially restoring a video image of the retrieved video image data according to the determined image restoring ratio (step S 36 ) and comparing and evaluating the partially restored video image and the video image to be searched for (step S 38 ). If the result of comparing and evaluating the video images in step S 38 is not good, the process returns to step S 30 to increase the restoring ratio. The comparing and evaluating of the images in step S 38 may be performed either visually by a user, or according to a method that makes use of artificial intelligence.

In a preferred embodiment of the present invention, the extracting of a dominant image element in step S 32 includes the substeps of compressing the video image using transform linear equations (S 320 ), deciding the frequency of generation of fixed points of the equations according to the values of decision elements of the matrix in an equation from which the fixed points are generated (S 322 ) and extracting the dominant image elements based upon a desired probability (S 324 ).

As described above, in the method and apparatus for searching for a video image according to the present invention, the searching time of the video image is shortened by partially restoring the picture according to a determined image restoring ratio, thereby reducing the time to completely restore a picture that is necessary in the conventional art. That is, in a preferred embodiment of the present invention, the dominant image element is extracted using a fractal image compression method so that the image is partially restored, to thereby effectively search for the video image.