One of the most important tasks being solvable on the aircraft board is a task of imposition of real images and images synthesized according to the digital terrain map. Complex of auxiliary tasks and actual imposition task should be solved on a real time basis (with frequency 25 frames per second) and with strict requirements to accuracy of the heterogeneous image imposition. Traditional correlation-extremal methods of imposition ensure a necessary accuracy but require unacceptably high expenditures of computer time. The paper describes an algorithm of imposition based on affine transformations of the synthesized image to the plane of a real video image and also algorithms for solution of auxiliary tasks.
Widely known correlation-extremal methods of image imposition, as practice of their application shows, ensure enough good
quality of imposition [
Limiting values of errors in determination of navigation parameters set a corresponding parallelepiped in the 6-dimensional space of parameters. Within this parallelepiped, a grid with nodes is formed. A synthesized image is constructed by values of the vector of parameters at each node. This image is overlapped onto a real image; a value of the objective function being a measure of the imposition quality is calculated and stored. After enumeration of all nodes the objective function global extremum and vector of navigation parameters ν opt where this optimum is achieved are found.
Alternative method to impose images is reduced to a search of the same objects on a pair of heterogeneous images, their comparison, calculation of the geometrical transformation of one image to the plane of other one and imposition of images for representation to a pilot. Algorithms based on the geometrical transformation of the synthesized image to the plane of a real one require less computation efforts for their implementation than correlation-extremal methods and provide acceptable quality of image imposition. However, these methods are applied only in cases if contours of continuous presence objects (water objects, roads, large buildings etc.) are stably distinguished on the underlying surface. Besides, bottleneck of these methods is a search of
Image Processing, Geoinformation Technology and Information Security / А.I. Efimov, А.I. Novikov
key (corresponding) points onto a pair of imposed images by means of which transformation of the synthesized image is
constructed to the plane of a real one. Correctness of selection of key points determines a degree of precision of “imposed”
images, i.e. quality of image imposition [
Imposition algorithm considered below is based on analysis and comparison of contours on a pair of images. Its basis is
affine transformations of the synthesized image to the plane of a real video image. Affine transformations do not take into
consideration projective distortions which inevitably appear under aerial photography [
Although imposition of images is a final and very important procedure but possibility and quality of image imposition significantly depend on how successfully auxiliary tasks are solved. These tasks include tasks of detection of contours on images, enhancement of images, identification of contours and setting of one-to-one correspondence between contours on a pair of heterogeneous images, formation of a set of pairs of key points. 3.1. Imposition algorithm on the basis of transformation in the complex plane
For realization of the algorithm it is necessary to have contours of continuous presence objects both on a real image and on a responding synthesized image. Specific requirements are imposed on quality of contours used in the algorithm. They are considered below.
Algorithm is based on an affine transformation of points on the complex plane according to formula z(r) znр zk(s) , z x iy , where z (s) – a point on the synthesized image contour, z (r) – a result of transformation to the k k k real image plane, znр xпр iyпр – a complex number providing transformation of points of one image to the plane of other one. It is required to find a pair of corresponding (key) points on the first and second contours in order to determine a complex number znр .
Let’s D be some area on the image with boundary D . Suggested variant of the algorithm takes points belonging to ends of the area diameters as corresponding points. i.e. M1 , M 2 arg max Mi , M j . Such points are found for corresponding
Mi , M j D objects both on the real and responding synthesized images. Vectors a1 (x2 x1; y2 y1) and a1 (x2 x1 ; y2 y1 ) are placed in correspondence with found points M1x1, y1 and M 2 x2 , y2 on the real image and responding points M1x1 , y1 , on the synthesized one. Complex numbers z1 x2 x1 i y2 y1 and z1 x2 x1 iy2 y respond these vectors on the complex plane. Complex number znр executing transformation of all points of the virtual image to the plane of the real one is determined according to formula znр zr zr zs .
zs zs zs Algorithm for detection of points M1, M2 belonging to ends of the diameter is the following. Let’s take a random point M on ~ the contour, choose a direction of the contour tracing and a near point M is found in this direction where local maximum is realized M , M max M , M j ~
M j D (1) ~
Then point M is taken as initial one and here the following point is found for it where the local view maximum is achieved (1). After full contour tracing in the chosen direction a global maximum is separated from a set of local maximums and, as a consequence, unknown points M1, M2 are found. Large volume of experimental researches of the algorithm for determination of points M1, M2 belonging to ends of some contour diameter confirm its correctness. For search of points M1, M2 belonging to ends of the diameter of a certain contour it is required that the contour should be closed. Contours of the real image obtained as a result of the algorithm for separation of boundaries of brightness jump can contain breaks. On the basis of information from the digital terrain map we know a type of the object and in particular it is clear that contours of its boundaries should be closed. Algorithm for formation of contours and additional processing is described below. The algorithm is aimed at enhancement of the contour image and, in particular, removal of breaks of small length which contours should be closed.
Image Processing, Geoinformation Technology and Information Security / А.I. Efimov, А.I. Novikov
Quality of image imposition by means of the described algorithm depends on quality of separation of brightness jump
boundaries. As a rule, skeletons obtained as a result of separation of brightness jump boundaries contain a great number of short
lines. They significantly complicate a search of interested objects and determination of one-to-one correspondence between such
objects (between object contours) on real and responding virtual images. For elimination of these disadvantages the algorithm of
additional processing of contour images has been developed. It allows eliminating both closed and unclosed lines of short
length. The algorithm is described in [
After achievement of the enhanced image of boundaries (Fig.1c) it is necessary to obtain a description of contours as a connected set of points. This procedure is realized as following: 1) pixels of the bitmap black-and-white image obtained as a result of the previous processing is looked through; 2) if black pixel is found, it is taken as a start of the contour and marked by the current pixel for analysis; iterative execution of steps 3-4 starts. Black pixels previously included into content of some contour is removed from consideration. 3) pixels adjoining the current one are looked through according to the order shown in Figure 2. In the case of detection of a neighbor in positions 1-8 it is added to the contour and marked as current one; operation is repeated; 4) if there are no black pixels in positions 1-8, contour tracing is stopped and return to step 1 occurs; 5) if all pixels of the image are looked through, algorithm operation completes.
In practice, there are often cases when contour of the extended object contains insignificant breaks. For this purpose, operation of additional combination is applied to contour descriptions obtained by the above-mentioned approach if distance between end points (the beginning and the end) of a certain pair of contours does not exceed a threshold value (threshold val ue is accepted as 7 pixels). Operation of additional combination is addition of pixels of one contour to list of pixels of another contour if above-mentioned condition is met. It allows removing small breaks and increasing quality of following procedures of imposition.
Image Processing, Geoinformation Technology and Information Security / А.I. Efimov, А.I. Novikov
As a result, after processing of the whole image we have a set of connected contours. It is natural and logical to remove contours of short lengths, i.e. contours where a number of pixels is less that the threshold value (experimental researches have determined that for images having resolution 704×576 pixels, contour length should be more than 120 pixels). Finally, we obtain connected contours of long length corresponding to extended objects on the original image. In addition to checking for exceeding of the minimum threshold length, we examine satisfaction to a range of additional conditions (these values will be described below in details):
– coordinates x, y of the object «center of mass» should be located on some surrounding of even one of objects from the virtual map, otherwise correspondences are not found for the mentioned object that negatively influences on the final result of image imposition; – length d of the contour diameter should be not more than 2/3 of its length L; – width w of the contour is not less than 12 pixels.
Execution of mentioned conditions guarantee that only contours of extended closed objects which can be used for following imposition will be on images. 3.2. Automatic identification of contours and match making between them on real and virtual images
Digital terrain map contains information on object types which contours are reflected on the synthesized image. This information allows identifying corresponding objects on the synthesized image. Contour analog of the real image may not contain contours of some objects which, nevertheless, are present on the synthesized image. And otherwise contours can be present on the real image which contain specific distinctions from the corresponding contours on the synthesized image. Distinctions can be explained both by outdated state of the digital terrain map and disadvantages of algorithms of contour separation at all stages of the real image processing.
At the visual level, one-to-one correspondence between object contours is determined enough easily. Task to determine such correspondence by a computer in automatic mode is enough complicated. For solution of the present task we suggest the algorithm based on usage of some numerical characteristics. They are calculated for each contour on the real and synthesized images: - coordinates x, y of the object «center of mass»; - length L of the contour; - length d of the contour diameter; - width w of the contour.
Let’s designate Mir xir , yir , M sj xsj , ysj , i 1, I , j 1, J object centers of mass which contours are selected on real and synthesized images correspondingly. Here i - a number of the object on the real image and j - a number on the synthesized one. Coordinates of “centers of mass” are found as mean values according to the corresponding coordinate by all pixels of the contour. Matrix of distances between centers of mass of the size I J is constructed for a set of objects on real and virtual images, i.e.
M r , M s M r , M s ... M r , M Js 1 1 1 2 1 ... ... ... ... .
M Ir , M1s M Ir , M1s ... M Ir , M Js Distances are located in the Euclidean metric.
Analysis of correspondences between object centers of mass is based on enough really supposition that shift of the object on the synthesized image with regard to the object responding to it on the real image does not exceed a certain limiting value T. So, if in some line i0 of the distance table all distances are longer than this value then no object on the synthesized image corresponds with the object with number i0 on the real image. Correspondingly, if such situation has a place in j0 -column then no object on the real image corresponds with the object with number j0 on the synthesized image. Such objects will not further participate in the procedure for determination of correspondences between objects.
After removal of objects not having a corresponding object on other image from the matrix, procedure for determination of correspondences between objects begins. Let’s I1 , J1 be numbers of residual objects on real and synthesized objects correspondingly. For all residual objects, both on real and virtual images the following is calculated: - lengths Lri , Lsj , i 1, I1, j 1, J1 of contours; - lengths dir , d sj , i 1, I1, j 1, J1 of diameters;
Image Processing, Geoinformation Technology and Information Security / А.I. Efimov, А.I. Novikov - values of object width wr , wsj , i 1, I1, j 1, J1 .
i
In this algorithm, a contour length is considered as a number of pixels in the contour. Area width is considered as a length b of the vector b N1N2 with ends on the contour in its average part and orthogonal to the vector a – an area diameter.
After all numerical characteristics of all objects are found, a chain of computational procedures and comparisons is performed. Sequentially, in the cycle by i from 1 to the end of the real object list, objects are chosen and following actions are performed for each of them: 1) in the cycle by i execution of inequality M r , M sj T is checked. Objects j1, j2 ,... , jk which this inequality is i fulfilled for, participate in the following comparison, the rest ones – not;
2) by each of three parameters L, d , w for i - contour on the real image, the nearest “neighbor” is searched on the synthesized image (2) j1 arg mjin Li L j1 , Li L j2 ,..., Li L jk j2 arg mjin di d j1 , di d j2 ,..., di d jk j3 arg mjin wi w j1 , wi w j2 ,..., wi w jk
“neighbor” in each of three Nearest conditions in (2) should comply with inequality Li L j1 Li , di d j2 di , wi w j3 wi . Here 1,3 . These inequalities are based on suppositions that values of each of three parameters for corresponding objects on real and virtual images cannot differ more than 1 per unit.
If j j j j , then the decision is made that the object with number j on the virtual image corresponds to the 1 2 3 object with number i on the real image. Even if all values j, j , j are different then we make a decision that the responding 1 2 3 object on the virtual image is not found for the object with number j, j , j on the real image. 1 2 3
Object SI-0 SI -1 SI -2 SI -3 SI -4 SI -5 SI -6
RI -1 233 80 39 145 266 297 299
RI -2 196 130 82 63 208 253 259
However, control of determined correspondences by other parameters of objects according to algorithm (2) leaves only three correspondences for the final imposition that are: RI 0 SI 1 ; RI 1 SI 2 ; RI 2 SI 3 .
Now we can perform the final stage of processing – imposition of contours of the synthesized image on the real TV-image. Fig.4a shows a result of simple overlapping of the synthesized image on the real one. We can see significant discrepancies between contours which are expressed by the shift of the synthesized image in relation to the real one and by contour dimensions. Fig. 4b shows a final result of imposition performed according to the algorithm. At the visual level, we can estimate quality of imposition as satisfactory.
RI-0 187 42 152 234 371 408 411 a)
RI -3 376 307 200 134 35 62 69
b)
Imposition of each eighth frame of the video sequence responding to imagery within 4 sec of flight has been performed to
estimate algorithm efficiency. Results of imposition quality estimation by 13 pairs of real and synthesized by DTM frames from
this video sequence are shown in Table 2. Imposition quality estimation has been performed using index introduced in paper
[
Main idea of the suggested method is the following. Image is divided into square blocks (cells) of the specified size, e.g. 100х100 pixels. It provides a possibility to obtain not only integral estimation of imposition quality but also local estimations in each of separated square blocks. In each cell for all informative (other than background color) points of one of images, informative points of other image locating in certain square surrounding of size (2k 1) (2k 1) having its center in the processed informative point is searched. As a rule, k 1 or k 2 . Value k 1 is equal to thickening of the thin line in one pixel of the first contour up to two pixels, and k 2 – up to three pixels.
Sliding window of the chosen size ( 55 in the considered experiment) is moved along lines of the image. As soon as an informative point of the first image gets into the center of this surrounding then informative pixels of the second image getting into this surrounding and not marked at the previous stages are searched and marked. After scanning of the whole image is completed, in each square blocks a number of mi
marked points of the imposed (second) contour is calculated and we found a ratio of this number to the total number of informative points of the first contour M i , i.e. i mi an index of the imposition quality in i -block of the image and coefficient i M i i imposition quality. m
i . Let’s call coefficient i as
M i – an integral index of the whole contour
Image Processing, Geoinformation Technology and Information Security / А.I. Efimov, А.I. Novikov
Results of imposition quality estimation by 13 pairs of real and synthesized by DTM frames from this video sequence are shown in Table 2. Within processing of the first frame there was an imposition disruption because correspondence between contours on real and responding synthesized images could not be determined. Enhancement of the imposition quality was not achieved in two frames. Imposition quality increased within the range from 24% to 108% in 10 frames.
In paper [
Algorithm was also examined on real video sequences obtained from a TV camera consisting of OVS within long time interval. Fig.5 shows a diagram of quality estimation for 900 frames (36 sec flight). Estimation of mathematical expectation of the imposition quality in the mentioned video sequence was 0.27, estimated variance – 0.004. Research of influence of the scene nature on results of the imposition quality estimation has been performed. It determined that quality estimation of the imposition algorithm results based on transformation in the complex plane exceeds the index before imposition on the same fragments where we can separate and determine correspondence as minimum between two objects. For the frames where correspondence was not determined, quality estimation remains invariable.
Program-algorithm complex of the image imposition in aviation vision systems which constituent is an algorithm for the image imposition based on transformation in the complex plane contains the following main blocks: 1) block for registration of images obtained from a vision sensor (in the case of program realization on a bench – frame capture from the video sequence); 2) block for construction of a virtual image by the virtual terrain model; 3) block of pre-processing of real and virtual images; 4) block for imposition and removal of geometrical mismatch of real and virtual images between each other; 5) block for visualization of the imposition result.
Blocks 2, 3 and 4 are most important for the whole complex and complicated from the point of view of their construction.
Construction of the virtual terrain model is realized by the separate software module in the developed realization of the image imposition complex. Its main functions are positioning of the virtual camera according to specified position coordinates and construction of the image by the available digital map in format sxf. It is possible to receive a frame both in thin lines and with overlapped textures.
Block of preprocessing realizes auxiliary operations required for execution of the geometrical imposition: separation of boundaries, removal of low informative lines, obtaining of connected contours – for real images; removal of lines of short extension and obtaining of connected contours – for virtual images. Quality of preprocessing greatly determines effectiveness of the following imposition.
Key element of the program-algorithm complex for image imposition is a block of geometrical imposition. The algorithm of imposition based on transformation in the complex plane as enough fast and reliable approach is suggested to be applied as one of algorithms for removal of geometrical mismatch. High-speed performance of the algorithm of image imposition based on transformation in the complex plane is the following: total costs for preprocessing do not exceed 0.3 sec per frame, for procedures of imposition – 0.05 sec. Calculations are performed using a computer equipped with processor Intel i7-3630QM,
Image Processing, Geoinformation Technology and Information Security / А.I. Efimov, А.I. Novikov 2.40 GHz, random-access memory 8 Gb, realization of algorithms for preprocessing and algorithm for imposition is performed in the C ++ programming language. Circuit of the program-algorithm complex organization is shown in Fig.6.
As it was mentioned before, correlation-extremal methods of imposition provide the necessary accuracy but require
unacceptably high costs of computer time. Broken-linear transformations of the synthesized image to the plane of real video
image are vulnerable because of issues with search of a set of key point pairs in the automatic mode [
Considered algorithm can operate under large errors of navigation parameters only if similarity of contours of corresponding objects on real and synthesized images is saved.
Developed algorithm can be applied independently for imposition of images and it can be used in combined schemes with algorithms of a higher level for pre-imposition.