JP2955761B2 - Image sampling method - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a method for sampling an image used in a sequential transmission system, and more particularly to a method capable of further reducing the time required for recognizing an image.

(Prior Art) In recent years, various image databases have been constructed due to improvements in image processing technology and an increase in demand for image media. Among these database systems, when transmitting a still image using a communication line having a relatively low transmission speed, etc., a long waiting time until the completion of image transmission puts a psychological burden on a receiver, so Various hierarchical coding methods and sequential transmission methods in consideration of search and transmission have been proposed. For example, in color image transmission, the ADCT method is recommended by the CCITT recommendation.

This hierarchical coding method for images is to sequentially reduce the amount of information from the original image in order to reduce the local redundancy of the image. For example, Yasuda and Takagi et al. Transmission and Display ”(Transactions of the Institute of Electronics, Information and Communication Engineers, 1980)
No. 4).

Briefly explaining this, first, as shown in FIG. 9, the original image 1 is divided into large blocks, and the average value density level of each block is quantized and coded to obtain a first stage image.
The image is transmitted as P1, and the images P2, P3,... Pn after the second stage are transmitted by dividing the block size into smaller ones.

FIG. 10 (a) is a diagram showing a method of creating a transmission image at each stage, called a pyramid structure, and FIG. 10 (b) is a side view thereof. In the figure, L1 is the lowermost layer of the pyramid, where the original image divided into ^2N * ^2N is placed as the first layer.
One new enlarged pixel is created from 2 ⁱ * 2 ⁱ pixels, for example, four pixels, in the first layer pixel L1, and a set of these is referred to as a second layer pixel L2. Next, from the four pixels in the second layer pixel L2, a newly enlarged third layer pixel is obtained.
Create L3. Thereafter, similarly, the size of the block is increased to obtain the pixel Li of the highest hierarchy, and this is transmitted as the first stage image. From the second stage onward, the images of the layers one by one lower than the highest layer Li are transmitted.

At this time, the first stage initial image Li represents the density value itself,
In general, data compression is performed from the image at the second stage by quantizing the density difference from the upper layer.

According to this method, the receiving side decodes in order from the largest block, sequentially adds the data of the finer blocks, and displays them on the monitor, so that a step-by-step display from a rough approximate screen to a finer precision screen is possible.

In addition, Endo and Yamazaki's “Sequential Reproduction and Coding of Facsimile Signals Suitable for Conversational Image Communication” (Transactions of the Institute of Electronics, Information and Communication Engineers, 1984, No.12) encodes pixels discretely, It has been proposed that the transmission be performed with a smaller coding interval. According to this, the receiving side performs an interpolation process on the transmission image discretely coded,
As in the above-described method, a step display from a coarse screen to a fine screen is enabled.

In these hierarchical coding methods as described above, the sampling interval is determined in accordance with the density distribution in the uniform or local quantity area, and the number of elements constituting the image is reduced.
The upper layer image is obtained. Therefore, if this image is transmitted sequentially from the upper layer, the image on the receiving side is initially blurred as a whole, and then the image that is sequentially detailed is displayed.
At the initial stage of transmission, it is possible to grasp the general state of the image. At this point, the unnecessary screen on the receiving side can be stopped by a command from the receiving side to the center, and the next image search can be started. it can. As a result, the psychological burden on the receiver is reduced and the transmission cost is reduced as compared with the ordinary line-sequential scanning in which the entire image is received only when the entire screen is received.

However, the hierarchical coding method as described above has the following disadvantages.

That is, since the upper layer image is obtained by reducing the redundancy of the image, it is difficult to apply the image to the image with less redundancy. In other words, when transmitting a fine image, it takes time to display a detailed image, and there is a disadvantage that it is not clearly recognizable until a precise image is sent, although it is shorter than line sequential scanning.

In addition, in a special-purpose database system that handles not only small images but also portraits of people and catalogs of products,
In many cases, a subject as an object is positioned near the center of an image. For this reason, the receiver tries to capture the characteristics of the image in the early stage image displayed in a short time by focusing on the edge portion where the density change is sharp near the center of the image. After all, it cannot be clearly recognized until the center is displayed in detail.

(Object of the Invention) The present invention provides a conventional image hierarchical coding as described above,
The purpose of the present invention is to eliminate the disadvantages of the sequential transmission method, and to provide a hierarchical coding method for images capable of recognizing images in a shorter time, and a sampling method for transmission. I do.

(Summary of the Invention) In order to achieve the above object, the present invention provides a so-called "slurry bowl-shaped" sampling method in which the sampling interval is closer to the center of the image instead of the conventional pyramid structure of the image by uniform sampling. Is adopted, the detail is sequentially refined with priority given to the center of the image.If the object is located near the center of the image, even if the transmission rate is the same as that of the conventional method, Thus, the receiver can recognize the image in a shorter time.

(Examples) Hereinafter, the present invention will be described in detail based on illustrated examples.

FIG. 1 shows transmission pixels at each stage in the present invention. The original image 1 is first divided into large blocks and transmitted as a first-stage image Q1.
2, Q3,..., Qn is the same as the conventional sequential transmission method in that the block size is reduced and transmitted. Thus, the present invention focuses on the fact that a subject in a database for images such as face photographs is often located near the center of the image, and the size of the block or the sampling interval near the center of the image is changed to the peripheral part. Characterized in that it is preferentially reduced prior to. This makes it possible for the receiver to recognize the image at an early stage, or to make the transmission time the same, that is, to improve the visual evaluation of the image expressed when the same amount of information is transmitted.

FIG. 2 is a diagram showing the principle of the sampling method according to the present invention. In the figure, L1 to Li correspond to each layer in the conventional pyramid structure, but in the present invention, unlike this, as shown in M1 to Mk in the figure, the sampling interval of each layer is set at the center of the image. The shape of the bowl is curved so that it is denser and rougher at the periphery.

First, a sampling procedure for obtaining a transmission pixel at each stage will be described.

First, the original image is divided into 2 ^N * 2 ^N blocks, placed at the bottom of the pyramid, and all 2 ^N * 2 ^N pixels are sampled.
That is, the original image is divided into the finest blocks and sampled.

Next, from the center of the image to the periphery,
Whether or not the pixel belongs to the pixel at the stage is checked based on a parameter set in advance as described later. If so, the pixel is stored as a first-stage pixel, and the process proceeds to the next pixel. If they do not belong to the pixel, a new enlarged pixel is created from 2 ⁱ * 2 ⁱ , for example, 4 pixels among the pixel and all the pixels located outside the pixel.

Each enlarged pixel Li (Xi, Yi) (Xi, Yi = 1, 2 .........)
2 ^Ni ) has a quadtree structure to four neighboring pixels in the immediately lower hierarchy _Li-1 as in the past, and is defined as follows.

Li (Xi, Yi) = ｛L _i-1 (2X _i-1 -1,2Y _i-1 -1) + L _i-1 (2X _i- 1,2Y _i-1 -1) + L _i-1 (2X _i-1 -1,2Y _i-1 ) + L _i-1 (2X _i-1 , 2Y _i-1 )｝ / 4 ... (1) where (Xi, Yi) is the number of pixels from the image origin. Coordinates. Xi is referred to as a distance in the X direction, Yi is referred to as a distance in the Y direction, and the number of pixels is hereinafter referred to as “distance”. However, it should be noted that even if the distances on the coordinates are the same, the pixel size differs depending on the hierarchy, so that the actual distance differs depending on the hierarchy. The mean of the formula (1) is therefore a pixel located at the coordinate (Xi, Yi) belonging to the Li hierarchy coordinates belong to the Li-1 hierarchy _{(2X i-1 -1,2Y i-} 1 -1 ), (2X _i-1 , 2Y _i-1 -1), (2X _{i-1
i-1 -1,2Y i-1)} , is that the average concentration of the four pixels positioned in _{(2X i-1, 2Y i} -1).

After newly creating a pixel enlarged in this way, it is checked whether or not the pixel belongs to the pixel of the first stage from the portion outward. If it belongs, the pixel is stored as a first-stage pixel, and if it does not belong, one new enlarged pixel is created. Thereafter, outer pixels are created in the same manner in the same manner, and when the outermost part of the image becomes the first stage pixel, sampling is completed. By the above procedure, an image Mk of the highest hierarchy to be transmitted as an initial image is obtained, and this image has large peripheral pixels and small central pixels.

By the way, the image of each layer after the second stage can be easily obtained by storing the lower image information when creating the image of the first stage. That is, the quadtree structure may be sequentially lowered based on each pixel belonging to the initial image Mk. At this time, each pixel that has finished descending to the level of the original image is not included in the following curved surface. Therefore, when the center of the image coincides with the original image, the image to be transmitted thereafter is only the peripheral portion excluding the center, and all the characters have a katakana-shaped "B" shape. For this reason, when the transmission is performed hierarchically from the upper image, the information transmitted in the latter half does not relate to the center of the image,
It will only serve to refine its periphery.

According to the above-described procedure, it is not necessary to find a pixel located higher than the Mk curved surface when creating an initial image. Therefore from Li
The processing amount can be reduced as compared with the case where Mk is obtained after obtaining all the pixels belonging to the Li ′ hierarchy, and this effect is more prominent near the center of the image closer to the original image.

 Next, the parameters described above will be described.

FIG. 3 shows an example of the above-mentioned mortar-shaped Mk curved surface. In the figure, B1 is the outermost pixel of the Mk curved surface, B2, B3 ... are the pixels whose distances from the outermost of the Mk curved surface are 2,3, ..., respectively, and Bm is the innermost pixel. Pixel. Where the outermost pixel
The layer of Li to which B1 belongs is determined, and the value of i at that time is defined as i '. A parameter representing the Mk surface is defined as a vector S, and its elements S1, S2,..., Sm are defined as follows in correspondence with B1, B2,.

First, pay attention to the outermost pixel B1 of the Mk curved surface. If the pixel is a block larger than the inner pixel B2, set S1 = 1, and if the pixel is a block of the same size, set S1.
= 0.

Next, attention is paid to the pixel B2 on the inner side, and it is checked whether or not the pixel is a block larger than the pixel B3 on the inner side. S2 = 1 if large, S2 = 0 if same
And This is sequentially repeated for the inner pixels, and the process is completed when Sm is obtained up to the center pixel.

For example, when the layer of Li to which B1 belongs is 4 as in the pyramid structure of 7 layers shown in FIG. 3, that is, i ′ = 4, the layer difference up to the lowest plane L1 is 3, so The number of 1 is at most three. In this example, the parameter indicating Mk is s = {1,0,0,1,0,0,1,0,0,0,0,0} (2), and based on this, k = Each surface M3, M2, M1 of 3,2,1 layer
Can be automatically determined. That is, the size of a pixel in an image to be transmitted at each stage can be determined.

Actually, the shape parameter vector S is converted for the sake of simplicity of sampling, and a vector S ′ is used which indicates to which layer of the pyramid structure the pixel of the Mk curved surface belongs by the number of layers. The elements of the vector S 'are S'1, S'2 ... S'm
And .., M of S ′ are different from the vector S and indicate the distance from the center of the curved surface.

For example, the Mk surface represented by the parameter S described above is 1,1,1,1,1,1,2,2,2,3,
Since there are three, three, four, and layers, S 'is expressed as follows.

S ′ = {1,1,1,1,1,1,1,2,2,2,3,3,3,4} (3) Then, the calculation procedure of the number of pixels to be transmitted for each stage Will be described.

First, a plane Li having a pyramid structure having the same block size as the outermost part of the pixel Mk curved surface at the stage to be calculated is prepared, and divided into groups of Li, j according to the distance j from the image center. As a result, the central portion is divided into squares, and the outside portion is divided into a plurality of katakana-shaped "B" -shaped groups. The number of pixels Nj belonging to the group whose distance from the image center is j
Is obtained by subtracting the total number of pixels of the square whose distance is j−1 from the total number of pixels of the square whose distance from the image center is j. Therefore, Nj = (2j) 2- {2- (j-1)} ² = 8j-4 (4). Since the outermost group belongs to the Mk surface, the number of pixels is calculated.

Then move to the inner group. If this belongs to the Mk surface, the number of pixels in this group is calculated and accumulated. If the group does not belong to the group, the group and the inside of the group are set as the plane _Lk-1 of the pyramid structure one level lower, and are again divided according to the distance from the center. In the same manner as above, check whether each group belongs to Mk, if it belongs, accumulate the number of pixels, if not, further as a plane L _k-2 of the pyramid structure one layer lower according to the distance from the center again To divide.

Hereinafter, the number of pixels on the inner side is sequentially accumulated, and when the accumulation is completed up to the center of the image or the innermost part of the stage, the total number is the number of transmitted pixels at that stage.

For example, in the above embodiment, the number of pixels to be transmitted as the initial image is 388, and the number of transmitted pixels in the third stage is 2176.

Finally, the conventional method is compared with the present sampling method. In FIG. 2, if Mk having the same number of pixels as Li is obtained, Li is located outside the intersection of Li and Mk, and Mk is located inside the intersection.
Is smaller in pixel size and has better image quality.

That is, under the condition of the same bit rate, the width of j inside the intersection can be made larger than the width of j where Mk is positioned higher than Li outside the intersection. Therefore, the Mk surface is
It is possible to allocate more pixels of the block below the Li plane to the center of the image, and the center is represented in more detail, and the image quality is improved.

Conversely, if the size of the central block is the same as that of the conventional block, the number of transmission pixels can be reduced without substantially changing the image quality.

The procedures of the sampling, the shape parameter conversion, and the calculation of the number of transmission pixels described above are summarized as follows. FIG. 5 to FIG. 7 are flowcharts showing each procedure.

<Sampling Procedure> Procedure 1: An original image L1 composed of ^2N * ^2N pixels is prepared, and divided into Li, j groups according to the distance j from the image center.

Step 2: The maximum value of j is set to j _m = 2 ^N−1, and i = 1, j = 1, and p = 1.

Step 3: p> p _m if the end, to step 4 otherwise.

Step 4: If i = S′p, since the sampling of the pixel of Li, j has been completed, the pixel is directly used as the output pixel. Otherwise, go to step 6.

Step 5: j = j + 1, p = p + 1 and proceed to step 4.

Step 6: For all L _i, j from j to j _m, a group of L _{i + 1, (j + 1) / 2} is generated by the operation of equation (1).

Step 7: Set i = i + 1, j = (j + 1) / 2, p = p + 1, j _m = j _m / 2, and go to step 3.

<Shape parameter vector Replacing> Step 1: p = 1, S ' = S1, S1 = i' to Step 2: p = p + 1 and to, p> p _m steps if to step 5. 3: If, S '= If 1, set i '= i'-1. Procedure 4: Set S' = Sp, Sp = i 'and go to step 2. Step 5: If S' = 1, set i '= i'-1. : p _m = p _m +1 as S _m = i 'to Step 7: the order regarding p of S Conversely, S' to <transmits pixel number calculation procedure> Step 1: layer number q = i 'image center J = 2 ^mq-1 Total number of pixels B = N _j ^Suffix p = 1

Step 2: p> p _m if the end. Otherwise, if Sp = 0, go to step 3 as j = j-1, B = B + Nj. If Sp = 1, go to step 3 as q = q-1, j = 2 * (j-1), B = B + Nj. Step 3: Go to step 2 with p = p + 1 As is clear from the above steps, if q = 1, the subsequent Sp must be 0.

FIG. 4 is a block diagram showing an embodiment of an apparatus for realizing the hierarchical encoding method according to the present invention.

In the figure, reference numeral 2 denotes a parameter setting unit which sets a parameter S for image sampling and converts S into S '. The sampling section 3 takes in and samples the original image 1 based on S or S 'set by the parameter setting section 2, and stores the result. The output of the sampling unit 3 is transmitted via the quantization unit 4 and the encoding unit 5. The above is the configuration of the transmitting side 6, but the receiving side 7 has the opposite configuration, so that the detailed description is omitted.

When various experiments were performed based on the method described above, extremely good results were obtained.

For example, the standard image database SIDBA GIRL (256 * 25
6 pixels, 8 bits) is a typical example of a face image, and an experiment using the present invention was performed on this image. First, the image is divided into blocks of 16 * 16,8 * 8,4 * 4,2 * 2 pixels for comparison, and the entire block is replaced with the average density value in each block. , 4096,16
It consists of 384 pixels. Similarly, according to the present method, i ′ is set so that the number of constituent pixels becomes almost the same 220,1036,3964,16204 pixels.
And S were set to create a curved surface. This curved surface is shown in FIG.

Comparing the two, when the number of pixels is 1024 or more, the image transmitted by the present invention has better image quality. This is because in the case of a face photograph, the point of interest of a person is inevitably concentrated on the face, and a slight blur at the edge of the image is not so noticeable. However, when the number of pixels is 256, the image quality is slightly inferior. This seems to be because when the details of the image cannot be grasped, the person tries to grasp the image from global features, that is, the average value of the whole image.

By the way, when the subject is not located at the center of the image, it takes time for the image to be clearly recognizable.In such a case, the portion where the size of the block is reduced is shifted from the center of the image, and the portion where the subject is located is located The above processing may be performed assuming that the center is the center. In this way, the transmission time can be reduced regardless of the position of the subject in the image.

The present invention is not limited to the above embodiment, but may be variously modified. For example, in the above-described embodiment, the original image is a square whose one side is a power of 2 for the sake of simplicity, but the present invention is not limited to this and may be of various sizes.

Also, an example is shown in which one new enlarged pixel is created from four pixels. However, if the subject and the background can be clearly distinguished, an enlarged pixel is created from as many as 16 or 64 pixels. You may. Considering this as an Mk curved surface, the slope of the curved surface, that is, the hierarchical difference, is increased at a portion that enters the subject region from the background region of the image. In other words, the transmission speed can be further increased by reducing the number of pixels in the background area that is not so related to the image identification.

In this case, the number of transmission pixels is calculated by q = q
It is necessary to execute the operations of -1 and j = 2 * (j-1) plural times according to the hierarchy difference.

Further, in the above-described embodiment, the parameter S is fixed as in Equation (3) for simplicity, but this may be adaptively changed according to the size of the subject in the image.

Of course, the procedure for converting the parameter S into S 'need not be limited to the above, and S' may be set in advance.

In the above embodiment, the case where the size of the block at the center of the image is smaller than that at the periphery of the image has been described. However, even when the sampling interval is reduced, the time required for recognizing the image similarly can be reduced. .

In addition, the present invention is applicable not only to the conventional hierarchical coding method but also to various coding methods.

(Effect of the Invention) As described above, in the present invention, the sampling interval is made closer at the center of the image, so that the vicinity of the center is displayed in more detail at the same bit rate as the conventional hierarchical coding. Therefore, it has a remarkable effect in recognizing an image in a short time, and is very effective particularly for an image database for a specific purpose such as a photograph of a human face.

[Brief description of the drawings]

FIG. 1 is a diagram showing transmission pixels at each stage in the present invention,
FIG. 2 is a diagram showing the principle of the sampling method according to the present invention, FIGS. 3 and 8 are diagrams showing an example of a sampling surface, FIG. 4 is a block diagram showing an embodiment of the present invention, FIG. 5 to 7 are flowcharts of sampling, parameter vector conversion, and calculation of the number of transmission pixels, respectively. FIG. 9 is a diagram showing transmission pixels at each stage in the related art, and FIG. 10 is a diagram illustrating the principle of the conventional sampling method. FIG. Q1 to Qn: first to n-th stage images, M1 to Mk: first to k-th hierarchical surface, B1 to Bm: pixels of the Mk surface, 1 ... original image, 2 ... parameter section, 3 ... ... Sampling unit, 4 ... Quantization unit, 5 ... Encoding unit, 6 ... Transmission side, 7 ... Reception side

Continuation of the front page (56) References JP-A-3-54971 (JP, A) JP-A-52-143712 (JP, A) Haruhiko Yasuda et al., "Stepwise Transmission and Display of Still Images by Hierarchical Coding""Transactions of the Institute of Electronics, Information and Communication Engineers, The Institute of Electronics, Information and Communication Engineers, Japan, April 25, 1980, J63-B, No. 4, p. 379-386 Toshiaki Endo et al., "Sequential Reproduction Coding Method of Facsimile Signals Suitable for Conversational Image Communication" Transactions of the Institute of Electronics, Communication and Engineers, IEICE, December 25, 1984, J67-B No. 12, p. 1462-1469 (58) Field surveyed (Int.Cl. ⁶ , DB name) H04N 1/41-1/419

Claims (3)

(57) [Claims] As an image at a first stage, an original image is divided into required blocks, and an average density level of each block is quantized.
In an image sampling method for transmitting an encoded image and transmitting an image in which the size of the block is sequentially reduced after the second step, the pixel density of a predetermined portion of the image becomes denser than other portions. A method for sampling an image, comprising sampling an image at each stage. 2. An image for transmitting an image obtained by discretely quantizing and encoding pixels of an original image as an image of a first stage, and transmitting an image in which sampling intervals are successively reduced after the second stage. The image sampling method according to claim 1, wherein the image is hierarchized in a pyramid shape, and the image at each stage is sampled so that a predetermined portion of the image has a higher pixel density than other portions. 3. An image sampling method according to claim 1, wherein the pixel density at the center of the image is made denser than at other portions.