Motion estimation method for control on the basis of scene analysis in video compression systems

[0001] This application claims priority from U.S. Provisional Patent Application No. 60/347,400, entitled Motion Estimation Method for Control on the Basis of Scene Analysis in Video Compression Systems, filed Jan. 9, 2002.

[0002] The given invention relates to and integrates instruments for resolving the creation of control systems using motion estimation components on the basis of the dynamic analysis of the structure of images as scenes, the structures of which interact among themselves and with the medium.

[0003] The international committee Motion Picture Experts Group is concerned with the standardization of instruments for the compression and decompression of images. The standard determines the form of the presentation of the image code and the method of its reproduction. It covers the line format of television and monitor displays.

[0004] In accord with the MPEG standards, images are presented as matrices of layers of macro-units, each of which contains a specific number of parts of an image in the form of macro-blocks, each of which measures 1616 pixels. A series of compressed images is divided into two sub-sets. The first is a subset of reference images based on entropy coding, methods for quantization, and the coding of which methods of discrete cosine transformation are found in MPEG(2) and MPEG(4). The second subset contains frames in which temporal redundancy is removed by means of estimation and compensation of motion.

[0005] Images as functions of two variables belong to the class of functional spaces with characteristics, the approximation of which by trigonometric orthonormal functions has poor frequency localization. This means that quality high-degree compression of images on the basis of discrete-cosine transformation has limits in the range of non-high-degree compression.

[0006] Transient fragments of images are compressed using methods based on a discrete-cosine transformation. As a rule, this results in complex, difficult to remove distortions. Motion estimation procedures are used to attain high-quality compression to the desired degree, thereby yielding a good result if the reference images possess a high quality of compression. However, when using the discrete-cosine transformation, this is only attained in degrees of compression that are not very high (on the order of 20).

[0007] MPEG-4 encounters still greater problems in those cases where it is necessary to ensure a high degree of video compression (on the order of 200), which can be attained only by means of the active use of all motion estimation possibilities. Traditionally, such a degree of video compression for frames of 320256 pixels, for MPEG-4 at a level of quality for films with complex dynamics, it is not yet attainable.

[0008] There are several reasons for this. Frames with an interpolated format are distributed between two reference frames, that possess the formats intra and predicted respectively. Frames of the interpolated type are formed with the aid of the identification of blocks in the aforementioned frames that have minimal displacement in relation to the given block with minimal approximation error. MSE or PSNR usually are used as a measure of the degree of proximity of the blocks that generally do not adequately reflect the visual similitude of the blocks. The selection of approximating blocks is implemented on the basis of an additional criterion, whereby the entropy of vectors of displacement is minimal, which ensures a maximal degree of compression at the entropy encoding stage.

[0009] The congruence of the displacement of the blocks leads to an unbalancing of the visual images of adjacent blocks, and as a result to a greater number of unwanted artifacts. The latter, through transfer from frame to frame, leads to complete disruption of the images or of their individual fragments. In order to remove an accumulation of artifacts, re-encoding of blocks by the discrete-cosine transformation method is actively used in the MPEG-2 and MPEG-4. As a rule, re-encoding is implemented with rather significant errors.

[0010] The disclosed method for control of motion estimation is based on the use of wavelet technology for compression with a low level of loss of information upon recovery of the images. Inter-frame interaction in video films is calculated by means of examination of individual images as scenes with subsequent classification into scenarios resembling them. Per the character of the correlation relationship between frames of a scenario, the global model for control using motion estimation is determined. Different variants for models of control with inter-frame interaction are shown in FIG. 4.With the goal of effective analysis of scenes, is presented for presenting scenes in the form of graphs of the interaction of objects of scenes. An example of the graph is in FIG. 1. After the adjustment of the model parameters in accordance with the disclosure herein, the subsequent compression of the scenario images is implemented.

[0011] For each compressed image the level of information loss is determined according to its regenerated depiction. If it exceeds the established threshold, then a repeat encoding of the image is made with altered values for the parameters of adjustment of the model for control with motion estimation, and the situation is also possible where the entire model for control with motion estimation is altered.

[0012] At the end of the compression of the entire video the visual characteristic of the video and the average level of information loss are checked.

[0013] FIG. 1 is a graph showing the objects in the same video scene that have been assigned different variants of analysis for local control with inter-frame interaction.

[0014] FIG. 2 is a graph showing the blocks in a video scene.

[0015] FIG. 3 is a graph depicting the relationship between blocks in a video scene FIG. 4 depicts examples of different models for the global control of motion estimation.

[0016] FIG. 5 is a comparison of the MSE value of two image blocks from a video scene.

[0017] FIG. 6 depicts the method of isolating an object in a video scene as taught by the current invention.

[0018] FIG. 7 is a graph of the Correlation Coefficients for a video film.

[0019] FIG. 8 shows examples of simple objects of the approximating and approximable blocks and the correspondences between them.

[0020] FIG. 9 shows the approximating and approximated block matching in a video scene as taught by the current invention.

[0021] FIG. 10 is a video frame showing the distribution of blocks requiring re-encoding and consolidated blocks of re-encoding.

[0022] The invention will now be described in preferred embodiments by reference to the drawing figures where appropriate. Each film is interpreted as a special class of database, in which, with a given degree of adequacy and the necessary complete form of presentation, information about some part of the real or intellectual world is expressed. Such a type of database may be classified as multivariate. It possesses several functional values: the transfer of information to consumers in the form of a video film for leisure, the distribution of information or the deepening of knowledge in a particular area, and other functions. Elements of such databases may be developed as in the case of classic relational, object-oriented, network, distributed databases.

[0023] The development of Web technologies, the creation of an electronic business system, medical databases and aerocosmic information attest to the use of video in such aspects. Upon examination of video film from these points of view, the problem of video compression acquires additional peculiarities. In decoding it is important to obtain not only quality video film for viewing perception, but also acceptable losses of information that are not connected with those parts or fragments of frames which carry important information or new knowledge about the given subject range.

[0024] Such a point of view and the approaches and requirements deriving therefrom for compression and decoding procedures determine the necessity of creating video compression methods, which would to a maximum degree reflect the structure of the video, the dynamic of the change of the blocks of frames, their qualities and interconnections. This is desirable not only purely from a viewer's point of view, but also in the transmittal of a sequence of web sites along Internet channels, mobile video links, and in the creation of a system of electronic business on a real-time scale.

[0025] For the creation of a video compression and decoding system, in which rigorous demands are made, it is proposed to make a preliminary analysis of each video film based on the requirements placed on the compression and decoding procedure. The task of exploratory pre-processor analysis is to describe the structure of the video and the dynamics of change of individual qualities and components.

[0026] The structural analysis of the video films has a four-level hierarchical structure. A sequence of frames reflecting the dynamic of change of the isolated subject range is subject to one law, referred to herein as the local scenario. A sequence of local scenarios that form a video film, and the law of these scenarios replacing of each other, referred to herein as the global scenario. The dynamic of change of all parameters and the qualities of the objects of the subject range determine the local scenario. Different subject ranges may be connected with different scenarios. Therefore the global scenario reflects the dynamic of transition from one subject range to another, or the dynamic of transition of subject ranges from one state to another.

[0027] If one designates as the subject range of the real or intellectual world, some part of it that is isolated with the aid of a system of limitations that satisfy the given conditions. The object of a subject range would be those of its components that may be constructed from some sub-set of elementary objects with the aid of a given set of operations. The same subject range may be allocated to a set of objects by different methods. The choice of a method of presentation of the subject range in the form of a set of objects depends on the character of the use of the isolated objects in the analysis of the structure of the scenes and the dynamic of their change.

[0028] If one looks at a simpler model of scene analysis, based on a block ideology for separation of objects, and calls a rectangular block of any size an object of the subject range. Such a perspective on the objects may be explained by the fact that any block may be examined as a subject range, inserted into the subject range, connected with the given image (frame). Thus one can proceed from the assumption that any subject range itself is an object. The selected model of a subject range corresponds well with the methods disclosed herein for quality high-degree video compression based on wavelet compression methods and block analysis of structure, processing and calculation of inter-frame interactions, called motion estimation.

[0029] The degree and quality of video compression is determined by the degree and quality of the reference frames, made possible on the basis of wavelet methods of compression of static images and the degree and quality of compression of approximating images in a sequence between reference frames. The effectiveness of the compression algorithms for the images with estimation of inter-frame interaction is determined by the effectiveness of the system for control using motion estimation procedures on the basis of information that reflects the dynamic of change and interaction of the objects represented as blocks. One system for control of compression procedures on the basis of motion estimation is based on the use of a graph of the relationships between the blocks.

[0030] When constructing the graph, an object is called elementary if it cannot be broken down into simpler objects. In the given interpretation of the understanding of the object, pixels are elementary objects. Such elementary objects are described by their coordinates and are characterized by the values of the parameters in Y, U, and V.

[0031] Other characteristics of pixels also are possible. An empty set of pixels forms a trivial object. More complex objects are formed with the aid of several finite sets of operations, which determine the set of all objects in the given subject range model, and which may be constructed with the aid of several sets of elementary objects.

[0032] In the examined subject range model the following operations are used:

[0033] an operation of the product of objectsdetermines the object, consisting of all pixels common to them;

[0034] a quadratic sum operationis determined as an object, consisting of all pixels of a minimal rectangular block that includes the given objects;

[0035] an operation for the construction of an additional objectdetermines the object, which includes all pixels not belonging to the object's set of pixels.

[0036] The operations may be reduced in such a way that the objects will be separate rectangular blocks, a set of non-intersecting rectangular blocks, or the entire image, from which one or several non-intersecting blocks were removed. The first set of objects is a substantial development of the construction of motion estimation on the basis of a discrete-cosine transform approach.

[0037] Another system for controlling operations is an extension of the system using motion estimation with the principal distinction that complex objects may be a combination of non-intersecting objects. Loosening this condition allows the construction of an even more general conceptual approach to the control of motion estimation. The class of supplemental objects allows one to more adequately solve the problem of selection of an initial set of blocks, with which construction of an optimal approximation of the images can be started with blocks from the previous and subsequent images.

[0038] Construction of a graph of the interaction and relationships of the blocks allows one to effectively solve the class of motion estimation problems of how to create a method of selection of the initial set of blocks of an interpolated type of image, from which the process of approximation of the images can be started with minimal error. In general, such a selection is not determined uniquely. However the uncertainty of the selection may be significantly reduced if one succeeds in finding a maximal quantity of blocks, arranged in a block of minimal size, the approximation of which is combined with maximal error. Thus three events are possible:

[0039] 1. the size of the error is close to the level of the upper or lower threshold;

[0040] 2. the size of the error significantly exceeds the threshold level;

[0041] 3. there are several different values for the criterion of proximity for approximation of a block.

[0042] Analysis and isolation of these events is combined with the selection of the criterion for proximity of the approximating and approximated blocks. The criteria may have a simple single-criterion type of structure (i.e., the value of the criterion is determined by the values MSE on the pixel, PSNR on the pixel). However, the image brightness and color variety have different influence on the value of the integral criterion. Therefore, it becomes expedient to use criteria of the type:

[0043] where ₁, ₂, ₃ are weighted coefficients that determine the degree of importance of the inclusion of differences for Y, U, V per pixel. The coefficients may be determined by a method of selection using iteration procedures for multi-criteria optimization.

[0044] Integral criteria, which evaluate degrees of proximity of two blocks as objects of a scene, generally do not adequately reflect the given property. Therefore, dynamic values are used along with static values. On the basis of the dynamic approach an entire class of measurements of the proximity of two objects, presented as blocks, is constructed. For example, assume and * are two blocks, one of which is approximable, the other is obtained as a result of an approximation based on motion estimation. For the corresponding columns each of the blocks is calculated MSE (FIG. 9).

[0045] The sequence of sample values {overscore (m)}₁, . . . , {overscore (m)}_k are obtained. The proximity of blocks B_i B_i* will be greater, the lower the variance of the mathematical series is. One may use the statistics: $C=\left(\frac{1}{k}\underset{i=1}{\overset{k}{}}{m}_i\right){\stackrel{\_}{}}_m$

[0046] as a function of proximity. Other types of metrics yield a system of blocks embedded in each block per the particular law. (FIG. 9)

[0047] For each pair of corresponding blocks of the system of embedded blocks once calculates MSE (PSNR, SNR), and obtains the sequence of values ₁, . . . , _k. The mean and the variance of the obtained series give rise to yet another function of proximity of such a type: $=\left(\frac{1}{k}\underset{i=1}{\overset{k}{}}{}_i\right)\stackrel{\_}{{}_{}},$

[0048] reflecting the degree of proximity of the blocks. The given method creates a library of functions of the proximity of blocks. Each function reflects the particularity of the interaction of objects that belong to the given block of blocks of the subject realm. The necessity of building a set of functions of proximity of the approximated and approximable blocks is conditioned by the fact that any such function is an integral characteristic of the coefficients or squares of differences Y, U, V for corresponding pixels. The integral characteristic reflects the determined structural qualities of the image connected to the block.

[0049] By its size, one may form an opinion only about the degree of transfer of the structural quality from the approximated block to the approximable. On the strength of this it is necessary for any object represented as a block to isolate a set of all of its structural qualities, which describe it uniquely or with necessary completeness. The structural qualities describe the geometry of sub-objects, the relations between them, their mutual arrangement, light and shade, flashes and other artifacts arising from scene to scene.

[0050] To reflect the geometric qualities of the sub-objects, further splitting into more simple objects may be necessary. The inter-connection between the set of all objects belonging to one block is described by the sub-graph of the graph of inter-connections of all objects of the scene. Each element of such a sub-graph is placed in accord with a selection of criteria (proximity functions) that allow one to sufficiently precisely identify the proximity of the approximable and approximated blocks.

[0051] Each object, represented as a block, is described by a vector criterion for the evaluation of proximity to other blocks

[0052] where (i, j) are coordinates of the upper left pixel of the approximable block, (l_ki, l_kj) are coordinates of the upper left pixel of the approximated block for sub-object O_mknk, that belongs to the given object, represented by approximable block O_ij.

[0053] A sufficiently simple method for construction of a system of functions S_k is based on a block structure. Moreover, each object is examined as a minimal rectangular block, which contains the given object with the matrix assigned to it, which contains only 0 and 1. An element of the matrix is equal to one if the corresponding pixel does not belong to the object and Zero if it does belong. Then for the sub-object O_mpnp of object ij the function S₁ for the pixel-by-pixel comparison of the proximity of the blocks has the form: $S_1\left(i,j,l_{\mathrm{qi}},l_{\mathrm{qi}},O_{m_p{n}_p}\right)={\underset{l=1}{\overset{n}{}}\underset{s=1}{\overset{n}{}}a\left(i,j\right)\left(s,l\right){\left(x\left(i,j\right)\left(s,l\right)-\tilde{x}\left(l_i,q_i\right)\left(s,l\right)\right)}^2}^{1/2},$

[0054] where a(ij) is the matrix of object O(m_p, n_p) from 0 to 1.

[0055] The vector (s₁, . . . , s_k) is verified on the fulfillment of the condition (s₁<₁, . . . , s_k<_k), where limits for _i are given, proceeding from the requirements placed on the characteristic of approximation. The lower the error of approximation, the lower the values of the limits are. If all conditions are fulfilled for a block (l_qi, l_qj), then it is selected as an approximating block. If a condition is not fulfilled for some subset, then two approaches are possible:

[0056] A solution is adopted by group selection method (in this particular case by the polling method). Here it is proposed that all conditions have equal value. A positive solution is adopted in the situation where more than one half of the conditions are fulfilled. If nonetheless conditions do not have equal value, then a vector of weights (₁, . . . , _k) is selected empirically. A solution is obtained by means of summing the weights for those inequalities, which are fulfilled. If the sum of the weights is larger than the sum of the weights of the non-fulfilled inequalities, then a positive solution about the approximation is adopted.

[0057] In the event of a negative solution a review of all vectors (s₁, . . . , s_k) is made for different approximable blocks for all possible values of the vectors of displacement of the blocks. From the entire set of solutions the sub-set of quasi-optimal solutions is selected. Assume min S_i. Then the set of all approximable blocks for which min S_i-S_i1<_i is adopted to name the set of quasi-optimal solutions. The combination of quasi-optimal solutions relative to all criteria yields a full set of quasi-optimal solutions.

[0058] Multivariate integral criteria, as well as univariate criteria, do not guarantee that approximating blocks that correspond to the smallest values for the criterion of proximity of the blocks are not always the best approximating blocks. This event is conditioned as well upon the stochastic character of the criteria as well. A method was developed for seeking the best approximating block by means of analysis of the set of quasi-optimal solutions.

[0059] In the event that there is not one approximating block, for which this complete condition is met:

[0060] or a weaker condition, based on the principle of group selection, the method proposes the examination of two cases.

[0061] In the first case this complete condition is fulfilled:

[0062] or the weaker condition:

[0063] One may confirm that the block contains within itself sub-objects, which are poorly approximated by any other blocks from the preceding or following frames. In this case a method of re-coding such blocks is used. Either separate blocks of 1616 or groups of compactly distributed blocks, which are covered by a minimal block of either 3232 or 6464, are subject to re-encoding.

[0064] In the second case either this complete condition is fulfilled, by:

[0065] or the reduced condition:

[0066] resulting from the group selection procedure.

[0067] Analogous to the first case, one may confirm that the block contains sub-objects, which are poorly approximated by any other blocks. However unlike the first case, the difference is close to the limit level per the corresponding criterion. The characteristic of approximation may be substantially improved with the help of the procedure of quadratic splitting of blocks, which essentially isolates sub-blocks of the approximable block.

[0068] The developed method allows one to control with motion estimation procedures in such a way that the necessary degree of compression and the required level of quality of the visual perception of the image are simultaneously guaranteed.

[0069] The Method for control with motion estimation contains the following steps:

[0070] Step 1. A dynamic sequence of images is classified according to the degree of the correlation relationship between them on a subsequence with similar scenarios.

[0071] Step 2. A scenario (i) is selected from within the dynamic sequence of images.

[0072] Step 3. An image (j) is selected from within the scenario (i).

[0073] Step 4. A strategy for global control with motion estimation for a class subsequent of images that form one common scenario is selected.

[0074] Step 5. A local strategy for control with motion estimation for the current scenario (i) and image (j) is selected.

[0075] Step 6. The parameters for the local strategy of control with motion estimation and their adjustment in the process of encoding blocks of the current scenario (i) are set.

[0076] Step 7. Assume that i is the number of the current scenario and j is the number of the encoded (approximable) image (frame).

[0077] Step 8. A graph of the interconnections of the relationships of the objects of image j and scenario i is constructed.

[0078] Step 9. Block j and scenario i, are encoded in accord with the selected methods for global and local strategy of calculating the inter-frame interaction (motion estimation).

[0079] Step 10. If j is the number of the final image of scenario (i), the quality of the compression for the scenario (j) is then verified as follows:

[0080] If the quality satisfies the given condition, one can assume ii1 and j1, and move to step 3. If the quality does not satisfy the given condition, change the setting of parameters of global local strategies and transfer to step 6. If j is the number of the last image of the last scenario i one evaluates the quality of the compressed video through the entire system of controlled parameters: PSNR(MSE), the dispersion of PSNR(MSE) according to coefficients Y, U, V, an expert evaluation of the video quality, the bit rate et alia. If a function of such values satisfies the given requirements, then the work of the algorithm is confirmed, otherwise one reconstructs the parameters for the global and local strategies taking into consideration the results obtained.

[0081] Classification of the video film images:

[0082] If (F₁, . . . , F_n) is the sequence of all frames of a video film, and the dimension of the frame is in pixels. One can evaluate the relationship between adjacent frames by means of a correlation coefficient of the type $r\left(F_i,F_j\right)=\frac{1}{mn}\underset{j=1}{\overset{n}{}}\underset{i=1}{\overset{m}{}}\left(f_{\mathrm{ise}}-\stackrel{\_}{f_i}\right)\left(f_{\mathrm{ise}}-\stackrel{\_}{f_j}\right)/\sqrt{\stackrel{\_}{D_i}\stackrel{\_}{D_j}};$ $\mathrm{where}$ $\stackrel{\_}{D_i}=\frac{1}{mk}\underset{j=1}{\overset{n}{}}\underset{i=1}{\overset{m}{}}{\left(f_{\mathrm{ise}}-\stackrel{\_}{f_i}\right)}^2;$ $\stackrel{\_}{D_j}=\frac{1}{mk}\underset{j=1}{\overset{n}{}}\underset{i=1}{\overset{m}{}}{\left(f_{\mathrm{ise}}-\stackrel{\_}{f_j}\right)}^2;$

[0083] If the adjacent frames are strongly correlated between themselves, then r(F_i, F_j) takes on significance for such images, as a rule, within the limits 0.5r1. A real graph of the change of the correlation coefficient of the images of a test film Boat from the Panasonic company is shown in FIG. 7.

[0084] On the curve, two regions of relatively low values of r are visible, which split the entire set of video frames into three scenarios:

[0085] the boat with fishermen in front of harbor equipment;

[0086] the beach;

[0087] a pile of beach hats.

[0088] Thus, the regions of the minimum of the function r(F_i, F_i1) determine the simple splitting of the film into three scenarios. Instead of a correlation function an Euclidean metric, or any other, may be used. However, it has been found that the correlation coefficient is the most convenient evaluator of the degree of inter-frame interaction.

[0089] The selection of a global strategy for control with motion estimation procedures:

[0090] The strategy for control by inter-frame interaction is determined by the distance between the nearest reference frames. The distance may be fixed as well as variable. In the latter case it is customary to talk about the adaptive model for the arrangement of the reference frames. In the current invention such a model is not considered. With a fixed distance between reference frames, its size is determined by the values of the correlation coefficient r(F_i, F_j1). The value at which r(F_i, F_j1)>0.5 and r(F_i, F_j11)>0.5 is adopted as the optimal distance between reference frames. For control with evaluation of inter-frame interaction it is necessary to select a model for the coding (approximation) of the current frame on the basis of one or two reference frames and groups of consecutive previous encoded frames. The distance between the encoded frame and the number of the considered previous encoded frames is referred to herein as the depth of the encoding. The model of control is called two-sided if in the encoding of any frame the left and right reference frames are used, and one-sided if one of the reference frames is considered.

[0091] The depth of the encoding is determined by the depth of the strong correlation relationship between frames. Let r(F_i, F_j1)>, . . . , r(F_i, F_jk)>, but r(F_i, F_ik1)<, where < for any F_i between the given reference frames, and is the mean value of the correlation coefficient between frames, placed between the selected reference frames. In FIG. 4 examples of different models for the global control of motion estimation are shown.

[0092] The correct selection of a model for control with inter-frame interaction significantly influences the quality of compression of the images. When practicing the current invention, it is recommended that one select a model for global control of motion estimation within the limits of one scenario. Cases where it is necessary to implement a repeat encoding after compression of the video film, whereby separate models for global control are replaced by others, are not excluded. A high value for the correlation coefficient, dispersed at great depth to the right or the left of the central image between two reference frames may serve as the basis for adoption of such a solution.

[0093] A model for local control with inter-frame interaction:

[0094] With construction of a strategy for local control with motion, it is necessary to select initial blocks from which coding per the determined strategy starts. Selection of an initial block measuring 1616 or a group of blocks significantly influences the obtained results. To select a quantity of blocks covering that part of the image which is important for visual perception. For resolution of this task we construct a graph of the scene of the approximable image. In FIG. 1 different variants of analysis of the same scene are shown. From all possible descriptions of the structure of the scene the variant where the key object is presented in the form of an independent element, representing a minimal block is selected. In FIG. 6 a boat with fishermen is show, which is present in all frames of the first scenario.

[0095] It is important that when selecting the key object all elements present in it have the same spatial depth. Non-fulfillment of this condition, as a rule, leads to the formation of multiple artifacts. After construction of a graph of the scenes a local strategy for the control by motion estimation, which contains the following steps is used:

[0096] Step 1. Selection of an initial block, belonging to an isolated object, from which its approximation of the images, determinable by the global model of motion estimation with blocks, begins.

[0097] Step 2. A selection from the library of functions that determine the degree of proximity of the approximating and approximable blocks of a set of functions representing the vector sum of the character of the approximation.

[0098] Step 3. Selection of the optimal plan for review of the blocks through the vector of displacement (l_s, l_q) on the approximating image, and for each function S₁, . . . , S_k one can select a graph reflecting the dynamic of change of these functions in the process of the search for blocks that correspond to the quasi-optimal values.

[0099] Step 4. Selection of a procedure and conditions for re-encoding of separate blocks or groups of blocks.

[0100] Step 5. Selection of a procedure for quadratic splitting of the blocks.

[0101] Step 6. Selection of a function for removal of artifacts.

[0102] The setting of parameters for a local procedure for control with motion estimation:

[0103] The setting of parameters for a local strategy of motion estimation includes the selection of an initial coding object, a minimal block containing it and an initial block of 1616 pixels, from which the encoding process begins. Thus two approaches are possible. The selection of these elements is made by the operator, which controls the video conversion process and the quality of the regenerated images. A formal approach to the selection of these parameters is possible. For this the computing complexity of the dynamic of the change of scenes is evaluated on the basis of the complexity of the correlation matrix between all pairs of images of the given set. One can select an object possessing the greatest computing complexity of the dynamic of change, and in it analogously a block with the maximal computing complexity.

[0104] Any object may be broken down into simpler objects. From a theoretically plural point of view, objects of a block containing the given object are any connected subsets of pixels. In FIG. 8, examples of simple objects of the approximating and approximable blocks and the correspondences between them are shown. Such objects possess an independent value in two aspects. First, with their help it is easier detect the independently moving fragments of the foreground and background. This is manifested in the development of displacements of blocks of vertical or horizontal pixels, if a portion of them is connected with the foreground and a part with the background. Secondly, aggregates of such elementary object verification of the degree of proximity of the two blocks.

[0105] For this, a correspondence is established between the corresponding simple objects of the approximable and approximating blocks. For pairs placed in correspondence, the values of the function of proximity are calculated. A sequence of values m₁. . . . , m_k of the estimations of MSE or PSNR is obtained. If the dispersion D_m<, where >0 is of a sufficiently low value, then these objects practically correspond.

[0106] When the sequence m₁, . . . , m_k has a peak, then this speaks to the fact that, regardless of the proximal or corresponding values of MSE or PSNR, the given blocks contain objects which differ significantly. In FIG. 5(a) a block from a video scene is shown that includes the sea and a buoy, while in 5(b) only the sea is in the same place in the image, but the buoy is missing. In this case the difference MSE for these blocks is not very great. Methods for resolving the problem of artifacts, which hereby arise, and methods for their removal are not considered in this invention.

[0107] For systems of evaluating functions of proximity S₁, . . . , S_k the rule for decision making about the proximity for the blocks, that is acceptable for coding is selected.

[0108] If the best variant is selected for coding of the given block by means of its approximation with another block, then after this it is necessary to verify the consistency of the borders of the given block with adjacent blocks. A sufficiently simple model for verification of the consistency is shown in FIG. 8. If the functions of brightness U and V correspond to two adjacent columns of pixels, then the block is assumed to be consistent along its borders well as in its internal structure.

[0109] Selection of the approximating block is completed:

[0110] In the event of the non-correspondence of borders, the solution for the approximation (coding) may not be adopted. In such events the adoption of either procedures for the quadratic splitting of the block or the removal of the artifact resulting from the non-correspondence of the borders is necessary. The movement of parts of a block in different directions may be one such artifact. The quadratic splitting procedure permits one to sufficiently simply remove the given artifact.

[0111] A procedure for the re-encoding of blocks:

[0112] In the event that for all variants of the approximation of a given block with another all variants of the solution are significantly noted for a large side in relation to the line of transition, it is necessary to re-encode such a block. If in the vicinity of the given block other blocks are missing that require re-encoding, then the given block is re-encoded independently.

[0113] When blocks that require re-encoding form a compact group, then a minimal block that contains them is isolated. If the portion of blocks that require re-encoding is greater than 50%, then the separated minimal block is fully re-encoded. This guarantees an increase in the quality of the coding, including the removal of the block structure from the encoded image. In FIG. 10 an example is shown of the distribution of blocks requiring re-encoding and consolidated blocks of re-encoding. The re-encoding strategy requires careful control of the deposit of the re-encoded blocks into the bulk of the code of the approximable image. The covering by larger blocks must be fulfilled in such a way as to thereby minimize the length of code of the re-encoded blocks.

[0114] Procedure for quadratic splitting of blocks:

[0115] In U.S. Provisional Patent Application No. 60/347,343, entitled The Enhanced Aperture Problem Solving Method Using Displaced Center Quadtree Adaptive Partitioning, filed Jan. 9, 2002, one model for the quadratic splitting of blocks with the goal of significantly increasing the quality of approximation was proposed. The disclosure of that application is incorporated herein by reference.

[0116] If one examines the construction of quadratic splitting of more blocks in the case where re-encoding does not yield the necessary result. The method proposed in the referenced application may be generalized in the case of large blocks. By using the method introduced in this patent for each variant of splitting, the effectiveness of the use of each of them to improve the approximation quality of the separated block may be verified. In comparison with 1616 blocks the number of splitting variants is significantly larger. The exhaustive search for all variants and their analysis, from a computation point of view presents an NP-full problem. To reduce the number of variants in the set a method for analysis of the variants by means of the sequential transition from simple splitting variants to splitting variants with a complex structure is used.

[0117] The results of the encoding of complex test films from the Panasonic company show that in several cases, the splitting of large blocks into non-standard blocks is a serious alternative method for the full re-encoding of large blocks.

[0118] The methods disclosed in the current application can be executed or preformed in a computer, other microprocessors, programmable electronic devices or other electronic circuitry. The methods can be loaded into the above devices as software, hardware, or firmware. The given methods can be implemented and programmed as discrete operations or as a part of a larger video compression strategy.

[0119] The invention has applicability to the field of video compression. In compliance with the statute, the invention has been described in language more or less specific the method of practicing the invention. It is to be understood, however, that the invention is not limited to the specific method shown or described, since the means and construction shown or described comprise preferred forms of putting the invention into effect. The invention is, therefore, claimed in any of its forms or modifications within the legitimate and valid scope of the appended claims, appropriately interpreted in accordance with the doctrine of equivalents.