CN1222711A - A system and method for connecting images in a surrounding field image-based virtual environment - Google Patents

Abstract

A system and method for splicing adjacent images into a large panoramic annular field map for constructing a virtual environment from the panoramic field map, the method comprising the steps of warping or projecting the input image onto a particular digital model, and then finding useful vertical or horizontal edges individually from the first warped image and the second warped image through to the last image and recording the positions thereof, from which a set of possible corresponding solutions can be found. The best joint is quickly determined by utilizing correlation matching so as to connect two adjacent graphs together. Compared with the traditional method, the method has obvious improvement on speed and stability.

Description

Translated fromChinese

一种环场图像式虚拟 环境接图系统 和方法A surrounding image-based virtual environment connection system and method

本发明主要涉及一种接图工具，利用此接图工具，可很容易地构造出一个环场图像式虚拟环境。The present invention mainly relates to a map connection tool, which can easily construct a virtual environment of ring field image type by using the map connection tool.

在这个现实世界里，要呈现这个多采多姿的世界，图像是最好的工具。过去，在计算机世界里，主要用绘图的方式呈现现实世界的自然景观，一点一滴地用线条慢慢地把所要表现的场景绘制出来。而这种方式需花费许多人力及时间，而且需要特殊且昂贵的计算机设备才能实时地把想要表现的场景经由计算机展现出来，虽然互动性高但缺点多。因此，就有人想要用图像直接来构造虚拟环境。这种方式有许多好处，首先，所需要的计算机设备不需太昂贵，即使是个人计算机就可得到很逼真的效果。再者，构建一个虚拟世界所花的人力与所要构建的景物无关，不管背景多复杂，计算机所花的时间都一样。利用图像来构建一个虚拟世界，首先要利用照相机，把它固定在一个旋转轴上，然后对景物环场拍一圈，便可得到一系列的图像。为了消除照相机镜头扭曲(perspective distortion)的问题，在接图之前，必须把这些图像投影到某一个数学模型(圆柱型或球型)上；然后利用接图器把这些图接合起来以构成一张环场图像；利用这张图像便可构建出真实世界的一个虚拟世界。In this real world, images are the best tool to present this colorful world. In the past, in the computer world, the natural landscape of the real world was mainly presented by drawing, and the scene to be expressed was slowly drawn bit by bit with lines. However, this method takes a lot of manpower and time, and requires special and expensive computer equipment to display the desired scene through the computer in real time. Although it is highly interactive, it has many disadvantages. Therefore, some people want to use images to directly construct virtual environments. This method has many advantages. First, the required computer equipment does not need to be too expensive, and even a personal computer can obtain very realistic effects. Furthermore, the manpower spent on constructing a virtual world has nothing to do with the scene to be constructed, no matter how complex the background is, the time spent by the computer is the same. Using images to construct a virtual world, first use a camera, fix it on a rotation axis, and then take a circle around the scene to get a series of images. In order to eliminate the problem of camera lens distortion (perspective distortion), these images must be projected onto a certain mathematical model (cylindrical or spherical) before connecting the pictures; Surround field image; using this image, a virtual world of the real world can be constructed.

环场图像在实际中有许多应用，例如可应用在电影特技、电子游戏、虚拟购物或教育上。要构建这种环场图，最大的问题就是如何把由照相机拍下来的一系列图串成一张。一个很自然的方法是用手动的方式把这些图接在一起，可是这种方式不太便利，尤其当有很多的图像要接时，更是费时费力。因此利用计算机来自动接图是一种比较便捷的方式。Surround field images have many practical applications, such as movie special effects, video games, virtual shopping or education. To construct this kind of surrounding field map, the biggest problem is how to string together a series of pictures taken by the camera into one. A very natural way is to connect these pictures together manually, but this method is not convenient, especially when there are many pictures to be connected, it is time-consuming and labor-intensive. Therefore, it is a relatively convenient way to use a computer to automatically connect pictures.

在把这些图像接在一起之前，为了克服图像因镜头而扭曲的问题，输入的图像必须投影到某一个数学模型，这个数学模型可以是球型(spherical)或圆柱型(cylindrical)。在实际应用中，球型投影在数据存储时会碰到一些问题，因为在计算机世界里，如果图像接近矩形则比较容易存储。另一个问题是照相机不好安排，位置摆得稍微不适当，图像间就有很大的扭曲及差异，而这会造成接图的困难。基于上述理由，在构建虚拟世界中，最常用到的投影方式为圆柱面投影(cylindrical projection)。Before joining these images together, in order to overcome the problem of image distortion due to the lens, the input image must be projected to a certain mathematical model, which can be spherical or cylindrical. In practice, the spherical projection will encounter some problems in data storage, because in the computer world, if the image is close to a rectangle, it is easier to store. Another problem is that the camera is not well arranged. If the position is slightly inappropriate, there will be a lot of distortion and difference between the images, and this will cause difficulties in connecting the pictures. Based on the above reasons, in constructing the virtual world, the most commonly used projection method is cylindrical projection (cylindrical projection).

参考图2，圆柱面投影数学模型可详细描述如下：矩形PQRS用来表示图像平面10，矩形pqrs用来表示假设的圆柱平面12(cylindrical plane)，镜轴中心为O,PQRS将被投影到pqrs，图像平面10外切圆柱平面12，图像平面10中心点为O′，镜头长度为f，圆柱平面的半径为d。假设P(x,y)为图像平面10上的一点，而P(u,v)为P(x,y)在圆柱平面12上的对应点，参考图2，坐标(u,v)可表示如下：$u=d\∠O^{\′}\mathrm{OB}=d{\tan }^{-1}\frac{\stackrel{-}{O^{\′}B}}{\stackrel{-}{{\mathrm{OO}}^{\′}}}=d\mathrm{ta}{n}^{-1}\frac{x}{f},---\left(1\right)$和$v=d\frac{\stackrel{-}{\mathrm{PB}}}{\stackrel{-}{\mathrm{OB}}}=d\frac{y}{\sqrt{x^2+f^2}}---\left(2\right)$事实上，半径d等于f，因此方程式(1)和(2)可改写如下：$u=f{\tan }^{-1}\frac{x}{f},---\left(3\right)$和$v=f\frac{y}{\sqrt{x^2+f^2}}---\left(4\right)$以方程式(3)和(4)为基础，可把照相机摄得的图像投影到某一个圆柱平面，再利用本发明的接图器，便可把输入的图像接成一张完整的环场图像。Referring to Figure 2, the mathematical model of cylindrical projection can be described in detail as follows: the rectangle PQRS is used to represent theimage plane 10, the rectangle pqrs is used to represent the hypothetical cylindrical plane 12 (cylindrical plane), the center of the mirror axis is O, and PQRS will be projected to pqrs , theimage plane 10 circumscribes thecylindrical plane 12, the center point of theimage plane 10 is O', the length of the lens is f, and the radius of the cylindrical plane is d. Assuming that P(x,y) is a point on theimage plane 10, and P(u,v) is the corresponding point of P(x,y) on thecylindrical plane 12, referring to Figure 2, the coordinates (u,v) can be expressed as follows:$u=d\∠o^{\′}\mathrm{OB}=d{\mathrm{the\; tan}}^{-1}\frac{\stackrel{-}{o^{\′}B}}{\stackrel{-}{{\mathrm{OO}}^{\′}}}=d\mathrm{ta}{\mathrm{no}}^{-1}\frac{x}{f},---\left(1\right)$ and$v=d\frac{\stackrel{-}{\mathrm{PB}}}{\stackrel{-}{\mathrm{OB}}}=d\frac{\mathrm{the\; y}}{\sqrt{x^2+f^2}}---\left(2\right)$ In fact, the radius d is equal to f, so equations (1) and (2) can be rewritten as follows:$u=f{\mathrm{the\; tan}}^{-1}\frac{x}{f},---\left(3\right)$ and$v=f\frac{\mathrm{the\; y}}{\sqrt{x^2+f^2}}---\left(4\right)$ Based on the equations (3) and (4), the image captured by the camera can be projected onto a certain cylindrical plane, and then the input image can be connected into a complete ring field image by using the image connector of the present invention.

本发明的主要目的在于提供一种智能型接图器，利用这个接图器可把由照相机摄得的一系列图像极有效地接在一起，从而构成一张完整的环场图像。本发明主要是利用图像边(edges)的信息，把一系列不同的图像接起来。本发明还提出一种方法，其利用图像边的信息，找出一系列可能的对应解(matching solutions)，再由这些可能的解，利用相关性匹配(correlation matching)确定出最后最佳的解，利用此最佳解，便可把相邻不同的图像接合起来。由于这一组可能解的数目很少，能以极有效的方式把最后解找出来。The main purpose of the present invention is to provide an intelligent image splicer, by which a series of images captured by the camera can be efficiently spliced together to form a complete image of the surrounding field. The present invention mainly connects a series of different images by utilizing the information of image edges. The present invention also proposes a method, which uses the information of the image edge to find a series of possible corresponding solutions (matching solutions), and then uses correlation matching to determine the final best solution from these possible solutions , using this optimal solution, different adjacent images can be spliced together. Since the number of possible solutions in this set is small, the final solution can be found in an extremely efficient manner.

在本发明中，当把两张图像接合在一起时，首先需要把它们投影到某一个圆柱面上，这就是所谓的扭曲(warping)运算，接着从这两张已扭曲过的图像，个别寻找边(edges)的信息，并把这些边的位置记录下来。利用这些边的位置，可以得到一组可能的对应点解。然后从这组解中，可以很有效地利用相关性匹配找到最终解。当找到最终解以后，由于这两张图像的亮度不一致，必须做所谓的混合(blending)运算，即利用一张图像上的一点的亮度以及它在另一张图像上对应点的亮度，根据它们离边界的距离进行加权平均，从而在两张图像变成一张后，在接缝处的亮度显得很平滑。In the present invention, when joining two images together, they first need to be projected onto a certain cylindrical surface, which is the so-called warping operation, and then from the two warped images, find edge information, and record the positions of these edges. Using the positions of these edges, a set of possible corresponding point solutions can be obtained. Then from this set of solutions, correlation matching can be used very efficiently to find the final solution. When the final solution is found, since the brightness of the two images is inconsistent, a so-called blending operation must be performed, that is, using the brightness of a point on one image and the brightness of its corresponding point on the other image, according to their The distance from the border is weighted, so that after two images become one, the brightness at the seam appears smooth.

本发明的特点在于，当检测一张图像的垂直边(vertical edges)时，可利用图像中每一列(column)像素(pixels)梯度值(gradient intensity value)的总和来确定，即对图像中每一列的每一像素分别计算它的梯度值；然后对这一列的像素所有梯度值加以总和平均，此平均值再跟一个预先设定的阈值加以比较；如果这个平均值比阈值大，则这一列有一垂直边的存在；对每一列都作这种运算，就可把所有的垂直边找出。The feature of the present invention is that when detecting the vertical edges of an image, it can be determined by using the sum of the gradient intensity values of each column (column) pixel (pixels) in the image, that is, for each image in the image Each pixel in a column calculates its gradient value separately; then all the gradient values of the pixels in this column are summed and averaged, and the average value is compared with a preset threshold value; if the average value is greater than the threshold value, this column There is a vertical edge; by doing this operation for each column, all vertical edges can be found.

类似地，当寻找一张图像的水平边(horizontal edges)时，可利用图像每一行(row)像素梯度值的总和来决定，即对图像中每一行的每一像素分别计算它的梯度值；然后对这一行的像素所有梯度值加以总和平均，此平均值再跟一个预先设定的阈值加以比较；如果这个平均值比阈值大，则这一行可视为有一水平边的存在；对每一行都作这种运算，就可把所有的水平边找出。Similarly, when looking for the horizontal edges (horizontal edges) of an image, it can be determined by the sum of the gradient values of pixels in each row (row) of the image, that is, its gradient value is calculated separately for each pixel in each row in the image; Then all the gradient values of the pixels in this row are summed and averaged, and the average value is compared with a preset threshold value; if the average value is greater than the threshold value, then this row can be regarded as the existence of a horizontal edge; for each row Doing this kind of operation all the horizontal edges can be found out.

利用垂直边，可推测出所需要的对应解(matching solutions)在x轴上可能的坐标；通常，利用所谓的位移函数(offset function)来产生这组可能的解。它的定义如下：$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$其中：P_a(i)表示在第a张扭曲图像(warped image)中第i条垂直边的位置；Using the vertical edges, the possible coordinates on the x-axis of the required matching solutions can be inferred; usually, a so-called offset function is used to generate this set of possible solutions. It is defined as follows:$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$ Among them: P_a (i) represents the position of the i-th vertical edge in the a warped image (warped image);

  P_b(j)表示在第b张扭曲图像中第j条垂直边的位置；P_b (j) represents the position of the jth vertical edge in the b distorted image;

  N_b表示在第b张扭曲图像中垂直边的数目；和N_b denotes the number of vertical edges in the b-th warped image; and

  k为使用者定义的一个变量。假设N_p表示所有在第a张扭曲图像中其位移函数d(i,k)值小于一个预定的阈值(threshold)T₀的垂直边的边数，由这些其d(i,k)值小于一个预定的阈值T₀的垂直边，可以得到d(i,k)的一个平均值A(k)。如果A(k)值小于一个预定阈值(threshold)T₁，而且N_p大于另一个预定的阈值(threshold)T₂，那么k位置就可视为一个可能的对应解在x方向上的坐标。给出不同k值，就可找出所有可能的对应解在x方向上的坐标。k is a variable defined by the user. Suppose N_p represents the number of vertical sides whose displacement function d(i,k) value is less than a predetermined threshold (threshold) T₀ in the a-th distorted image, and these d(i,k) values are less than An average value A(k) of d(i,k) can be obtained from the vertical side of a predetermined threshold T₀ . If the value of A(k) is less than a predetermined threshold (threshold) T₁ , and N_p is greater than another predetermined threshold (threshold) T₂ , then the position k can be regarded as the coordinate of a possible corresponding solution in the x direction. Given different values of k, the coordinates of all possible corresponding solutions in the x direction can be found.

根据本发明的另一方面，本发明提供一种用来有效地把输入的图像接成一张环场图的完整系统，该系统包含一个边缘检测器(edge detector)，用来检测第a张图像的垂直或水平边以及在第b张图像中对应的垂直或水平边，此边缘检测器同时记录这些垂直边或水平边的位置。该系统还包括一存储器，用来存储这些垂直或水平边的位置数据，以使进一步处理。该系统同时包含一个可能解产生器(hypothesis generator)和最佳解选择器(optimum hypothesisselector)，可能解产生器主要用来从存储于存储器中的垂直或水平边的位置来产生一系列可能的对应解，而最佳解选择器则用来从这一组可能的解利用相关性匹配来选择出最佳的解。According to another aspect of the present invention, the present invention provides a complete system for efficiently concatenating input images into a ring field image, the system includes an edge detector for detecting the ath image and the corresponding vertical or horizontal edge in the b-th image, the edge detector simultaneously records the positions of these vertical or horizontal edges. The system also includes a memory for storing the position data of these vertical or horizontal edges for further processing. The system also includes a possible solution generator (hypothesis generator) and an optimal solution selector (optimum hypothesis selector). The possible solution generator is mainly used to generate a series of possible correspondences from the vertical or horizontal edge positions stored in the memory. solution, and the best solution selector is used to select the best solution from this set of possible solutions by correlation matching.

具体地讲，该系统利用存储器来记录图像数据，该系统包含一个混合引擎(blending engine)，用来平滑图像间亮度的差异。两张图像接合起来时，必有共同的重叠区域(common overlapping area)。因为照相情况的不同，此两张图像共同的重叠区域亮度必然不同，可从一张图像取出一点像素来，同时在另一张图像取出其对应的像素，根据它们离边界的距离来进行加权平均，从而使得两张图像在共同重叠的区域的亮度非常平滑。在该系统中，边缘检测器(edge detector)、可能解产生器(hypothesis selector)、最佳解选择器(optimalhypothesis selector)都可包含在一个微处理器中。另外，可以利用外部的存储器(像硬盘)来记录扭曲过的图像(warped images)。Specifically, the system utilizes memory to record image data, and the system includes a blending engine to smooth out differences in brightness between images. When two images are combined, there must be a common overlapping area. Because of the different photographing conditions, the brightness of the common overlapping area of the two images must be different. A pixel can be taken from one image, and the corresponding pixel can be taken from the other image at the same time, and the weighted average can be carried out according to their distance from the boundary. , so that the brightness of the two images in the overlapping area is very smooth. In this system, an edge detector (edge detector), a possible solution generator (hypothesis selector), and an optimal solution selector (optimalhypothesis selector) can all be included in a microprocessor. In addition, an external memory (like a hard disk) can be used to record warped images.

本发明还提供一种预测要被接图的可能解的方法。它基本上利用图像中的垂直或水平边的信息来预测这组可能的解。由于推测准确，这组解的数目很小，因此搜寻的范围被大大地减少，因而可很快找出最终解。在寻找最终解的时候，利用所谓的相关性匹配来得到最终解。因为相关性匹配花费时间较多，本发明提供一个用来事先去掉不必要的相关性匹配的裁剪方法(pruningmethod)。该裁剪方法的原理是，如果当前相关性匹配的值小于一个事先定义的值，则没必要进行更进一步的匹配，因此可事先去掉一些不必要的匹配。这种裁剪方法可减少很多相关性匹配的计算，因此大大提高了接图的效率。与传统的方法比较，本发明不仅在效率方面而且在可靠性方面都有了明显的改善，这主要是因为可事先预测可能的对应解，由于推测准确并且这组解的集合很小，可很快地找出最佳解。The present invention also provides a method of predicting possible solutions to a graph to be spliced. It basically uses information about vertical or horizontal edges in the image to predict the set of possible solutions. Due to the accurate guessing, the number of solutions in this group is very small, so the search range is greatly reduced, so the final solution can be found out quickly. When searching for the final solution, the so-called correlation matching is used to obtain the final solution. Because correlation matching takes more time, the present invention provides a pruning method for removing unnecessary correlation matching in advance. The principle of this pruning method is that if the current correlation matching value is less than a pre-defined value, there is no need to perform further matching, so some unnecessary matching can be removed in advance. This cropping method can reduce a lot of correlation matching calculations, thus greatly improving the efficiency of image joining. Compared with traditional methods, the present invention has obvious improvement not only in terms of efficiency but also in terms of reliability. This is mainly because the possible corresponding solutions can be predicted in advance. quickly find the best solution.

本发明可应用到许多方面，例如虚拟环境、导游系统、电子游戏、地理信息系统、电影特技等。The present invention can be applied to many aspects, such as virtual environments, tour guide systems, electronic games, geographic information systems, movie special effects, etc.

通过参照附图对本发明的详细描述，本发明的目的、特征和优点将变得更加明显，附图中：Objects, features and advantages of the present invention will become more apparent by describing the present invention in detail with reference to the accompanying drawings, in which:

图l表示利用图像来产生虚拟环境的系统分析图；Figure 1 represents a system analysis diagram for generating a virtual environment using an image;

图2是用来说明圆柱投影的几何图；Figure 2 is a geometric diagram used to illustrate cylindrical projection;

图3是实现本发明的方法的系统示意图；Fig. 3 is a schematic diagram of a system realizing the method of the present invention;

图4A和4B以一个实例来说明图3系统的运行；Fig. 4 A and 4B illustrate the operation of Fig. 3 system with an example;

图5用来解释混合(blending)技术如何平滑两张图像之间的亮度；和Figure 5 is used to explain how the blending technique smoothes the brightness between two images; and

图6一个实现图3方法的计算机结构。FIG. 6 is a computer structure for implementing the method in FIG. 3 .

图3表示整个的接图系统20，其主要原理是利用边的信息(edgeinformation)来确定最后的最佳解。首先，利用边缘检测器22从图像中得到垂直边及水平边的位置。得到这些位置以后，利用可能解产生器24得到一系列可能解。接着，利用最佳解选择器26对这组可能解中的每一个解做最后的确认，从而有效地找出最后解。然后利用这最终解，个别地把相邻的图像接合在一起。为了消除个别图像间亮度的不连续性，可利用混合引擎28来解决这种亮度不连续性的问题。Fig. 3 shows the wholegraph connection system 20, the main principle of which is to use edge information to determine the final optimal solution. First, theedge detector 22 is used to obtain the positions of the vertical and horizontal edges from the image. After these positions are obtained, apossible solution generator 24 is used to obtain a series of possible solutions. Next, thebest solution selector 26 is used to make a final confirmation on each solution in the group of possible solutions, so as to effectively find the final solution. Using this final solution, adjacent images are then stitched together individually. In order to eliminate discontinuities in brightness between individual images, the blendingengine 28 may be utilized to resolve such brightness discontinuities.

在该接图系统中，边缘检测器仅使用垂直边和水平边来事先预测相邻图像之间可能的对应解。假设g_x(p)代表一张图像中的一点像素p(i,j)在x方向上的梯度值，它的明确表示式为g_x(p(i,j))=｜I(p(i+l,j))-I(p(i-l,j))｜，其中I(p)为像素p在图像中的亮度值。当检测垂直边时，边缘检测器对在同一列的像素累积它们的梯度值。如果这个累积值大于一个事先定义的阈值，则认定这一列中存有一个垂直边，并利用标记来记录这个垂直边的存在。在检测完所有的列以后，可得到所有垂直边的位置。可用相同的方法来寻找水平边的位置。In this graph-joining system, edge detectors use only vertical and horizontal edges to predict possible correspondence solutions between adjacent images in advance. Suppose g_x (p) represents the gradient value of a pixel p(i,j) in an image in the x direction, and its explicit expression is g_x (p(i,j))=|I(p( i+l,j))-I(p(il,j))|, where I(p) is the brightness value of pixel p in the image. When detecting vertical edges, the edge detector accumulates their gradient values for pixels in the same column. If the cumulative value is greater than a pre-defined threshold, then a vertical edge is assumed to exist in the column, and a flag is used to record the presence of the vertical edge. After detecting all columns, the positions of all vertical edges can be obtained. The same method can be used to find the position of the horizontal edge.

参考图4A和图4B，举一个例子来说明。假设个别的图像I_a和I_b要接合在一起，可利用边缘检测从I_a中得到如下垂直边：(100,y)、(115,y)、(180,y)、(200,y)、(310,y)、(325,y)、(360,y)、(390,y)和(470,y),也可从I_b中得到如下垂直边：(20,y)、(35,y)、(100,y)、(120,y)、(230,y)、(245,y)、(280,y)、(310,y)和(390,y)。由这些垂直边，可只利用它们在x方向上的坐标来得到两组坐标值，即P_a=(100,115,180,200,310,325,360,390,470)和P_b=(20,35,100,120,230,245,280,310,390)。因为这些垂直边彼此对应，P_a和P_b满足下列关系：P_a(i)=P_b(j)+d_x，其中i与j一一对应，d_x是P_a和P_b之间的偏差(offset)。很明显，d_x便是这两张相邻图像在x方向上的对应解(matchedsolution)。但是在某种情况下，由于存在噪声，可能找不到或找错在I_a和I_b的某些垂直边，这造成P_a和P_b之间不再是一一对应的关系。因此在本发明中，提出一种可能解产生器，用于从这些垂直边的信息找出在x方向上的可能对应解。Referring to FIG. 4A and FIG. 4B , an example is given for illustration. Assuming that individual images I_a and I_b are to be joined together, edge detection can be used to obtain the following vertical edges from I_a : (100, y), (115, y), (180, y), (200, y) , (310, y), (325, y), (360, y), (390, y) and (470, y), the following vertical sides can also be obtained from I_b : (20, y), (35 ,y), (100,y), (120,y), (230,y), (245,y), (280,y), (310,y) and (390,y). From these vertical sides, only their coordinates in the x direction can be used to obtain two sets of coordinate values, that is, P_a = (100, 115, 180, 200, 310, 325, 360, 390, 470) and P_b = (20, 35, 100, 120, 230, 245, 280, 310, 390). Because these vertical sides correspond to each other, P_a and P_b satisfy the following relationship: P_a (i)=P_b (j)+d_x , where i corresponds to j one-to-one, and d_x is the distance between P_a and P_b deviation (offset). Obviously, d_x is the corresponding solution (matched solution) of these two adjacent images in the x direction. However, in some cases, due to the existence of noise, some vertical edges between I_a and I_b may not be found or found incorrectly, which results in no one-to-one correspondence between P_a and P_b . Therefore, in the present invention, a possible solution generator is proposed for finding possible corresponding solutions in the x direction from the information of these vertical sides.

假设N_a和N_b分别记录P_a和P_b中的元素数目，且令位移函数$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|$。给定一个值k，则可能解产生器计算在P_a集合中其d(i,k)小于一个事先预定的阈值T₀的元素数目。假设这个数目为N_p，另外还假设这些满足条件的元素的d(i,k)的平均值为A(k)，如果A(k)小于第二个事先预定的阈值T₁，且N_p大于第三个阈值T₂，则这个位置k被视为一个可能对应解在X方向上的坐标值。提供不同的k，就有一组可能对应解产生。注意，这个可能解只是在x方向上的可能坐标值，令该可能解的集合为S_x。在这个求解过程中，三个预先设定的阈值T₀,T₁,T₂均由实验所得，且对所有的图像都一样。Assume that Na and_{N brecord} the number of elements in P_a and P_b respectively, and let the displacement function$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|$ . Given a value k, the possible solution generator counts the number of elements in the set P_a whose d(i,k) is less than a predetermined threshold T₀ . Assume that this number is N_p , and also assume that the average value of d(i,k) of these elements satisfying the condition is A(k), if A(k) is smaller than the second predetermined threshold T₁ , and N_p is greater than the third threshold T₂ , then this position k is regarded as a coordinate value in the X direction of a possible corresponding solution. Provide different k, there is a set of possible corresponding solutions generated. Note that this possible solution is only possible coordinate values in the x direction, let the set of possible solutions be S_x . In this solving process, the three preset thresholds T₀ , T₁ , and T₂ are obtained from experiments, and are the same for all images.

在水平边上也可用相同的方式。利用水平边，可以求出可能的对应解在y方向上的坐标。假设这些可能的y坐标构成一个集合S_x。因为S_x和S_y这个集合的元素不多，最终解可由最佳解选择器很快地得到。The same method can also be used on horizontal edges. Using the horizontal edges, the coordinates of the possible corresponding solutions in the y direction can be found. Suppose these possible y-coordinates form a set S_x . Because the set of S_x and S_y has few elements, the final solution can be obtained quickly by the optimal solution selector.

最佳解选择器主要用来从S_x和S_y两集合的并集{S=(x,y)｜x∈S_x,y∈S_y}中确定出最佳解。最佳解选择器主要利用相关性匹配来确定最佳解。在相关性匹配的方法中，比较常用的估价函数(measure function)有两个，一个是平均绝对差MAE(mean absolute error)，另一个是正则互相关(normalizedcross-correlation)，可参照L.G.Broum的论文。它们的定义分别如下：$D(p;q)=\frac{1}{{(2M+1)}^2}\underset{x,y=-M}{\overset{x,y-M}{\mathrm{\Σ}}}|I_1(x+p_x,y+p_y)-I_2(x+q_x,y+q_y)|$和$C(p;q)=\frac{1}{{\mathrm{\σ}}_1{\mathrm{\σ}}_2{(2M+1)}^2}\underset{x,y=-M}{\overset{x,y=M}{\mathrm{\Σ}}}\[I_1(x+p_x,y+p_y)-u_1\]\[I_2(x+q_x,y+q_y)-u_2\]$The best solution selector is mainly used to determine the best solution from the union of two sets of S_x and S_y {S=(x,y)|x∈S_x , y∈S_y }. The best solution selector mainly uses correlation matching to determine the best solution. In the correlation matching method, there are two commonly used measure functions, one is the mean absolute error (MAE) (mean absolute error), and the other is the normalized cross-correlation (normalized cross-correlation). Please refer to LG Broum's paper . Their definitions are as follows:$\mathrm{D.}(p;q)=\frac{1}{{(2m+1)}^2}\underset{x,\mathrm{the\; y}=-m}{\overset{x,\mathrm{the\; y}-m}{\mathrm{\Σ}}}|I_1(x+p_x,\mathrm{the\; y}+p_{\mathrm{the\; y}})-I_2(x+q_x,\mathrm{the\; y}+q_{\mathrm{the\; y}})|$ and$C(p;q)=\frac{1}{{\mathrm{\σ}}_1{\mathrm{\σ}}_2{(2m+1)}^2}\underset{x,\mathrm{the\; y}=-m}{\overset{x,\mathrm{the\; y}=m}{\mathrm{\Σ}}}\[I_1(x+p_x,\mathrm{the\; y}+p_{\mathrm{the\; y}})-u_1\]\[I_2(x+q_x,\mathrm{the\; y}+q_{\mathrm{the\; y}})-u_2\]$

其中u_i和σ_i为图像I_i的平均值及变化量。(2M+1)²表示匹配视窗的面积。虽然这两个估价函数都适用于确定最佳解，但当速度不是最重要的参考量时，正则互相关匹配是一个比较好的选择，因为它能容忍亮度的差异，但是，如果速度是一个很重要的参考量，则平均绝对误差估价函数是一个比较好的选择。Among them, u_i and σ_i are the average value and variation of image I_i . (2M+1)² represents the area of the matching window. Although both evaluation functions are suitable for determining the best solution, regularized cross-correlation matching is a better choice when speed is not the most important reference, because it can tolerate differences in brightness. However, if speed is a A very important reference quantity, the mean absolute error evaluation function is a better choice.

通常，计算平均绝对误差(MAE)所花费的时间很多，因此，在本发明中，提出一种裁剪技术(pruning technique)，用来加速MAE的计算。首先利用一个矩阵(matrix)来记录在累积计算前一个MAE时MAE的暂时值，用这个矩阵来当做阈值。如果目前的MAE值小于它所对应的阈值(存在于矩阵中)，则没有必要进一步累积计算MAE值。采用这种裁剪技术，就可避免许多不必要的相关性计算，因此明显改善了匹配的效率，也可很快地算出最佳解。Usually, it takes a lot of time to calculate the mean absolute error (MAE). Therefore, in the present invention, a pruning technique is proposed to speed up the calculation of MAE. First, a matrix is used to record the temporary value of MAE when the previous MAE is accumulated and calculated, and this matrix is used as a threshold. If the current MAE value is less than its corresponding threshold value (present in the matrix), there is no need to further accumulate MAE values. By adopting this clipping technique, many unnecessary correlation calculations can be avoided, so the efficiency of matching is obviously improved, and the best solution can be calculated quickly.

一旦找到最佳解以后，就可把相邻的两张图像接合起来。可是相邻的两张图像可能有亮度不一致的情况，因此，必须利用所谓的混合技术(blendingtechnique)来消除亮度不一致的问题。参照图5，假设P_i为在图像I_a上的一点，q_i为p_i在I_b上的对应点，l_a及l_b为I_a及I_b的个别边缘线，d_a为p_i到l_a的距离，d_b为q_i到l_b的距离，如果r_i为p_i和q_i在合成图像I上的对应点，则利用p_i和q_i，可利用下列的式子得到r_i的亮度：$I\left(r_i\right)=\frac{d_a^t{I}_a\left(p_i\right)+d_d^t{I}_b\left(q_i\right)}{d_a^t+d_b^t},\·\·\·\·\·\·\·\·\·\·\left(7\right)$其中t代表指数，其为一个可调整的参数。利用式(7)，就可得到最后合成的图像。Once the best solution is found, the two adjacent images can be joined together. However, two adjacent images may have inconsistencies in brightness, so a so-called blending technique must be used to eliminate the problem of inconsistency in brightness. Referring to Figure 5, assume that P_i is a point on the image I_a , q_i is the corresponding point of p_i on I_b , la_and l_b are the individual edge lines of I_a and I_b , and d_a is p_i The distance to l_a , d_b is the distance from q_i to l_b , if r_i is the corresponding point of p_i and q_i on the synthetic image I, then using p_i and q_i , the following formula can be used to get The brightness of r_i :$I\left(r_i\right)=\frac{d_a^t{I}_a\left(p_i\right)+d_d^t{I}_b\left(q_i\right)}{d_a^t+d_b^t},\·\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\left(7\right)$ Where t represents an index, which is an adjustable parameter. Using formula (7), the final synthesized image can be obtained.

图6是本发明的硬件结构，利用这个结构可以实时地把输入的图像接在一起。输入设备32可以是数码照相机或扫描器，由输入设备可以得到一系列的图像。这些图像可存储在外部存储设备32如硬盘或直接送到微处理器的随机存储器上(RAM)，微处理器包括扭曲图像(warpmg images)、边缘检测(edgedetection)、产生可能的解(hypothesis generation)等功能。暂时得到的数据可放到微处理器的RAM上，以提高接图的速度。一旦接图的工作完成，便可以把这些结果直接显示到屏幕上，这些功能可用一般的个人计算机来完成。Fig. 6 is the hardware structure of the present invention, and the input images can be connected together in real time by utilizing this structure. Theinput device 32 can be a digital camera or a scanner, and a series of images can be obtained from the input device. These images can be stored in anexternal storage device 32 such as a hard disk or directly sent to the random access memory (RAM) of the microprocessor. The microprocessor includes warp images (warpmg images), edge detection (edge detection), and possible solutions (hypothesis generation ) and other functions. Temporarily obtained data can be placed on the RAM of the microprocessor to improve the speed of connecting pictures. Once the work of drawing is completed, the results can be directly displayed on the screen, and these functions can be completed by ordinary personal computers.

以上所图示及说明的为本发明的一优选实施例。根据本发明所覆盖的范围及精神，本发明还可以做多种的变化。What has been illustrated and described above is a preferred embodiment of the present invention. According to the scope and spirit covered by the present invention, various changes can be made in the present invention.

Claims (18)

Translated fromChinese

1．一种把一第一图像和一第二图像图形接合在一起的方法，该方法至少包括如下步骤：1. A method for graphically joining a first image and a second image, the method at least includes the following steps:将第一图像和第二图像扭曲到一代表全景环场图像的数学模型；warping the first image and the second image to a mathematical model representing the panoramic surround image;检测出扭曲过的第一图像的一第一垂直或水平边，以及对应的扭曲过的第二图像的一第二垂直或水平边；detecting a first vertical or horizontal edge of the warped first image and a corresponding second vertical or horizontal edge of the warped second image;从这些检测出来的第一和第二边记录它们的数据及位置坐标；record their data and position coordinates from these detected first and second edges;从这些第一和第二边的数据及位置坐标找出一组可能的对应解；以及finding a set of possible corresponding solutions from the data and position coordinates of these first and second sides; and利用这些可能的对应解确定出一最佳的接合点对应解，以将两张图像接合起来。Using these possible corresponding solutions, an optimal joint point corresponding solution is determined to join the two images.2．如权利要求1所述的图像接图方法，其中数学模型由代表全景环场图像的多个像素所构成，所述方法在确定最佳的接合点并把两张图像接起来后，还至少包含一步骤：把扭曲过的第一图像和扭曲过的第二图像进行混合，从而使得两张图像接合部分的像素亮度相差不多。2. The image splicing method according to claim 1, wherein the mathematical model is composed of a plurality of pixels representing a panoramic image, and after the method determines the best splicing point and connects the two images, at least comprising Step 1: Mix the distorted first image and the distorted second image, so that the brightness of the pixels in the junction of the two images is similar.3．如权利要求1或2所述的图像接图方法，其中分别检测每一扭曲过的第一和第二图像的第一和第二边的数据的步骤至少包含：3. The image splicing method according to claim 1 or 2, wherein the step of detecting the data of the first and second sides of each distorted first and second image respectively comprises at least:检测各个所述第一和第二图像的一垂直边，其中还包含如下步骤：Detecting a vertical edge of each of the first and second images, further comprising the steps of:对于各个第一和第二图像，沿着每一列计算每一像素的梯度值；For each of the first and second images, calculating a gradient value for each pixel along each column;沿着每一列累积每一个像素的梯度值；以及Accumulate the gradient value of each pixel along each column; and将所述累积值与一事先预定的阈值做比较。The accumulated value is compared with a predetermined threshold.4．如权利要求1或2所述的图像接图方法，其中分别检测每一扭曲过的第一和第二图像的第一和第二边的数据的步骤至少包含：4. The image splicing method according to claim 1 or 2, wherein the step of detecting the data of the first and second sides of each distorted first and second image respectively comprises at least:检测各个所述第一和第二图像的水平边，其中包含如下步骤：Detecting horizontal edges of each of the first and second images, comprising the steps of:对于各个第一图像和第二图像，沿着每一行计算每一像素的梯度值；For each of the first image and the second image, calculating a gradient value for each pixel along each row;沿着每一行累积每一像素的梯度值；以及Accumulate the gradient value of each pixel along each row; and将所述累积值与一事先预定的阈值做比较。The accumulated value is compared with a predetermined threshold.5．如权利要求1或2所述的图像接图方法，其中找出一组可能的对应解的步骤包含如下步骤：5. The image connection method according to claim 1 or 2, wherein the step of finding a set of possible corresponding solutions comprises the following steps:根据下列公式计算位移函数：$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$其中：P_a(i)表示在扭曲过的第一图像中第i条垂直边的位置；Calculate the displacement function according to the following formula:$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$ Where: P_a (i) represents the position of the ith vertical edge in the warped first image;  P_b(j)表示在扭曲过的第二图像中第j条垂直边的位置；P_b (j) represents the position of the jth vertical edge in the warped second image;  N_b表示在扭曲过的第二图像中垂直边的数目；_Nb represents the number of vertical edges in the warped second image;  k为使用者定义的一个变量；k is a variable defined by the user;计算在P_a这个集合中其位移函数d(i,k)值小于一个事先预定的阈值T₀的元素数目，假设共有N_p个元素满足这个条件；Calculate the number of elements whose displacement function d(i,k) value is less than a predetermined threshold T₀ in the set P_a , assuming that there are a total of N_p elements satisfying this condition;对所述满足条件的N_p个元素，计算它们的d(i,k)的平均值；For the_Np elements satisfying the condition, calculate the average value of their d(i,k);根据所述平均值和N_p检验一位置k，确定它是否为一可能的对应解，如果一位置k为一可能的对应解，则其必须满足下列条件：Check a position k according to said average value and_Np , determine whether it is a possible corresponding solution, if a position k is a possible corresponding solution, then it must meet the following conditions:平均值必须小于第二事先预定的阈值T₁，且N_p必须大于第三事先预定的阈值T₂。The average value must be smaller than a second predetermined threshold T₁ and N_p must be greater than a third predetermined threshold T₂ .6．如权利要求3所述的图像接图方法，其中找出一组可能的对应解的步骤包含如下步骤：6. The image connection method according to claim 3, wherein the step of finding a set of possible corresponding solutions comprises the following steps:根据下列公式计算位移函数：$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$其中：P_a(i)表示在扭曲过的第一图像中第i条垂直边的位置；Calculate the displacement function according to the following formula:$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$ Where: P_a (i) represents the position of the ith vertical edge in the warped first image;  P_b(j)表示在扭曲过后的第二图像中第j条垂直边的位置；P_b (j) represents the position of the jth vertical edge in the warped second image;  N_b表示在扭曲过的第二图像中垂直边的数目；_Nb represents the number of vertical edges in the warped second image;  k为使用者定义的一个变量；k is a variable defined by the user;计算在P_a这个集合中其位移函数d(i,k)值小于一事先预定的阈值T₀的元素数目，假设共有N_p个元素满足这个条件；Calculate the number of elements whose displacement function d(i,k) value is less than a predetermined threshold T₀ in the set P_a , assuming that there are N_p elements in total meeting this condition;对于所述满足条件的N_p个元素，计算它们的d(i,k)的平均值；For the_Np elements satisfying the condition, calculate the average value of their d(i,k);根据所述平均值和N_p，确定一可能的对应解的位置k，所述位置k满足下列条件：According to the average value and N_p , determine a possible corresponding solution position k, the position k satisfies the following conditions:平均值必须小于一第二事先预定的阈值T₁，且N_p必须大于一第三事先预定的阈值T₂。The average value must be smaller than a second predetermined threshold T₁ and_Np must be greater than a third predetermined threshold T₂ .7．如权利要求4所述的图像接图方法，其中找出一组可能的对应解的步骤包含如下步骤：根据下列公式计算位移函数：$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$其中：P_a(i)表示在扭曲过的第一图像中第i条垂直边的位置；7. The image splicing method according to claim 4, wherein the step of finding a set of possible corresponding solutions comprises the steps of: calculating the displacement function according to the following formula:$d(i,k)=\underset{l\≤j\≤N_b}{\min }|P_a\left(i\right)-k-P_b\left(j\right)|,$ Where: P_a (i) represents the position of the ith vertical edge in the warped first image;  P_b(j)表示在扭曲过的第二图像中第j条水平边的位置；P_b (j) represents the position of the jth horizontal edge in the warped second image;  N_b表示在扭曲过的第二图像中水平边的数目；N_b represents the number of horizontal edges in the warped second image;  k为使用者定义的一个变量；k is a variable defined by the user;计算在P_a这个集合中其位移函数d(i,k)值小于一个事先预定的阈值T₀的元素数目，假设共有N_p个元素满足这个条件；Calculate the number of elements whose displacement function d(i,k) value is less than a predetermined threshold T₀ in the set P_a , assuming that there are a total of N_p elements satisfying this condition;对于所述满足条件的N_p个元素，计算它们的d(i,k)的平均值；For the_Np elements satisfying the condition, calculate the average value of their d(i,k);根据所述平均值和N_p，确定一可能的对应解的位置k，所述位置k满足下列条件：According to the average value and N_p , determine a possible corresponding solution position k, the position k satisfies the following conditions:平均值必须小于第二事先预定的阈值T₁，且N_p必须大于一第三事先预定的阈值T₂。The average value must be smaller than a second predetermined threshold T₁ and N_p must be greater than a third predetermined threshold T₂ .8．如权利要求1或2所述的图像接图方法，其中用平均绝对误差相关匹配的技术从可能的解中确定最佳解。8. The method of image splicing according to claim 1 or 2, wherein the technique of mean absolute error correlation matching is used to determine the best solution from possible solutions.9．如权利要求6所述的图像接图方法，其中用平均绝对误差相关匹配的技术从可能的解中确定出最佳解。9. The image splicing method according to claim 6, wherein the technique of mean absolute error correlation matching is used to determine the best solution from possible solutions.10．如权利要求7所述的图像接图方法，其中用平均绝对误差相关匹配的技术从可能的解中确定最佳解。10. The image splicing method according to claim 7, wherein the technique of mean absolute error correlation matching is used to determine the best solution from possible solutions.11．如权利要求1或2所述的图像接图方法，其中用正则互相关匹配的技术从可能的解中决定出最佳解。11. The image splicing method according to claim 1 or 2, wherein the best solution is determined from the possible solutions by the technique of canonical cross-correlation matching.12．如权利要求6所述的图像接图方法，其中用正则互相关匹配的技术从可能的解中确定最佳解。12. The image splicing method according to claim 6, wherein the best solution is determined from possible solutions by using the technology of canonical cross-correlation matching.13．如权利要求7所述的图像接图方法，其中用正则互相关匹配的技术从可能的解中决定出最佳解。13. The image splicing method as claimed in claim 7, wherein the best solution is determined from possible solutions by the technique of canonical cross-correlation matching.14．一种图像接图系统，用于将由多个像素构成的代表全景环场图像的数学模型中的一第一图像和一第二图像接合在一起，所述系统至少包含：14. An image splicing system for splicing together a first image and a second image in a mathematical model representing a panoramic surround field image composed of a plurality of pixels, the system at least includes:一边缘检测器，用于检测出扭曲过的第一图像的一第一垂直或水平边、以及对应的扭曲过第二图像的一第二垂直或水平边，并记录所述检测出的边的位置，从而得到有关边位置数据的集合；an edge detector for detecting a first vertical or horizontal edge of the distorted first image and a corresponding second vertical or horizontal edge of the distorted second image, and recording the detected edges position, so as to obtain the collection of relevant edge position data;一存储器，用来记录检测出的垂直边或水平边的位置数据的集合；A memory, used to record the collection of position data of the detected vertical edge or horizontal edge;一可能解产生器，用来从第一和第二垂直边或水平边的位置数据中产生一组可能的对应解；以及a possible solution generator for generating a set of possible corresponding solutions from the position data of the first and second vertical or horizontal edges; and一最佳解选择器，用来从所述一组可能解的集合中确定一最佳解。A best solution selector is used to determine a best solution from the set of possible solutions.15．如权利要求14所述的图像接图系统，其中所述存储器还用来存储代表扭曲过的第一和第二图像的像素，所述系统还包含一混合引擎，其利用存储器中的数据把扭曲过的第一和第二图像接合成一张大的环场图像，所述混合引擎系用于：15. The image splicing system of claim 14, wherein said memory is also used to store pixels representing the warped first and second images, said system further comprising a blending engine that uses data in the memory to transform the warped The processed first and second images are merged into one large surround image, the blending engine is used to:对扭曲过的第一和第二图像进混合操作，从而使两张图像接合部分的像素亮度相差不多。A blending operation is performed on the distorted first and second images, so that the brightness of the pixels in the joining portion of the two images is almost the same.16．如权利要求14所述的图像接图系统，其中还包含一微处理器，所述微处理器包含：16. The image splicing system according to claim 14, further comprising a microprocessor, said microprocessor comprising:所述边缘检测器、所述解产生器，以及所述最佳解选择器。The edge detector, the solution generator, and the best solution selector.17．如权利要求15所述的图像接图系统，其中还包含一微处理器，所述微处理器包含：17. The image connection system according to claim 15, further comprising a microprocessor, said microprocessor comprising:所述边缘检测器、所述解产生器、所述最佳解选择器以及所述混合引擎。The edge detector, the solution generator, the best solution selector, and the mixing engine.18．如权利要求14所述的图像接图系统，其中所述系统还包含一外部存储器，用于存储所有扭曲过的图像。18. The image splicing system as claimed in claim 14, wherein said system further comprises an external memory for storing all warped images.

Images