We proposed a novel rotation-invariant feature based passive ranging algorithm to estimate the distance of an imaged non-cooperation target to camera. This improved algorithm avoids sometimes occurrence of physically unreasonable results in solving the existing quartic equation, such as the happening of complex or negative value. This method uses three matched points in two adjacent frames of an image sequence to extract depth-dependent line features of the target. With this line features combination of the observer’s displacement and imaging directions, a quadratic equation was build to estimate the distance. Analysis shows that the proposed new passive ranging equation would be solvable when the observer is with non-zero displacement in adjacent sampling instances. Our reduced-model experiment also demonstrates that the proposed algorithm is not only simple and feasible but also with a relative ranging error no more than 4 per cent in most cases.

Keywords:    Invariants Scramjet,  depth cues,   feature representation,  passive ranging, imaging geometry  

Although stereo vision could find the depth information of an imaged object¹, but the motion stereo depth measurement² scheme is more attractive for its simplicity in construction. As we know, from industrial robot³ to air-launched weapons⁴, motion stereo has been widely used. It is characterized by using monocular imaging system and being mounted on a maneuvering platform.

In motion stereo, feature extraction and feature matching are problems that must be solved⁵. These features include points³⁶⁷⁸⁹, lines or edges⁵¹⁰¹¹, and regions¹² or colours¹³. Among these three kinds of features, regions or colours are less applied than two former, lines and edges have got the most applications. This is because the lines are easier to extract from contour images and their characterization, by means of polygonal approximation, and are more reliable than points feature in the presence of noise¹¹. In general, edges come from edge-based methods⁵, straight lines may come from either edge-based methods or two unique feature points.

In the past few decades, linearity features which include straight lines and edges have been used in image distortion correcting⁵, 3D image matching¹⁴, target tracking⁷¹¹, range finding⁸¹⁵, vision based navigating guide¹⁶¹⁷, robot simultaneous localization and mapping (SLAM)⁹¹⁸, pose estimation¹⁹²⁰, and so on. Among these application, passive ranging based on motion stereo is very important, which can be seen in⁵⁸²¹, and so on. Feature lines are wire poles or street trees in background, but in most cases, feature lines are in the target itself⁵⁸²¹. A new method is proposed for non-cooperate aircraft ranging in this study.

2.1  Existing Ranging Model

In this study, authors take the geography coordinates o-xyz as the host coordinates, in which the north, the west and the upper direction are assigned as the positive direction for x, y and z axis respectively. It is a reasonable assumption since that the state of our measurement platform on which the camera is fixed could be known from other detection system, such as the GPS and other inboard sensors, the information includes the azimuth, pitching, radial distance to point o, velocity, acceleration, and the attitude.

The platform itself also constitutes a coordinates O-XYZ, i.e. the platform coordinates. If we take an aircraft as the platform, then the nose head, right wing, and engine- room top are the positive directions of Y, X, and Z-axis respectively. The air- borne measurement-platform in the geography coordinate is shown in Fig. 1.

At the n-th sampling time, the point O in o-xyz coordinates is O(x_n, y_n, z_n). Suppose the moving target in the measurement-platform coordinates is expressed as (r_n, α_n, β_n) in a spherical form. Here, α_n and β_n are the azimuth and pitching from camera to the target, and the sightline of camera to the target in the geography coordinates could be expressed as the direction vector (l_n, m_n, n_n) as below:

$\left(\begin{array}{l}{l}_n\\ m_n\\ n_n\end{array}\right)=\left(\begin{array}{ccc}{t}_{11}^n& t_{12}^n& t_{13}^n\\ t_{21}^n& t_{22}^n& t_{23}^n\\ t_{31}^n& t_{32}^n& t_{33}^n\end{array}\right)\left(\begin{array}{l}\cos {\alpha }_n\cos {\beta }_n\\ \sin {\alpha }_n\cos {\beta }_n\\ \sin {\beta }_n\end{array}\right)$            (1)

Here,$\left(\begin{array}{ccc}{t}_{11}^n& t_{12}^n& t_{13}^n\\ t_{21}^n& t_{22}^n& t_{23}^n\\ t_{31}^n& t_{32}^n& t_{33}^n\end{array}\right)$ is the transposed matrix of the direction vector for X, Y, and Z-axis in o-xyz coordinates.

Suppose that there exists a one-dimension scale x0 in the target, which is invariable to the rotation of the camera in two adjacent sampling times. Let’s call the scale’s projection on the camera focal plane the target’s characteristic linearity. Under normal condition both the target and the measurement-platform are in moving. Figure 2 illustrates the recursive ranging model based on characteristic linearity.

Figure 2. shows T and S are the Target and Surveyor (camera) respectively. The subscript n or (n+1) represent the sampling time. Therefore, T_nT_n+1, S_nS_n+1 is the moving trace of the target and the platform between the n-th and (n+1)-th sampling time, while φ_n and φ_n+1 are the angles of the target’s trace to the camera’s sightline at each sampling time.

Assume that the focuses of optical system in the camera to be f_n and f_n+1 at the n-th and (n+1)-th sampling time, and length of the characteristic linearity in camera focal-plane to be L_n and L_n+1. Obviously, L_n or L_n+1 belong to a kind of depth-depended line features. According to the geometry imaging principle, the Eqn. below could be concluded.

$\frac{r_{n+1}}{r_n}=\frac{f_{n+1}}{f_n}\frac{L_n}{L_{n+1}}\frac{\sin {\phi }_{n+1}}{\sin {\phi }_n}$             (2)

2.2   Existing Algorithm

Based on Eqn. (2), the following recursion passive ranging Eqn. is derived¹⁵:
$C_4{r}_{n+1}^4+C_3{r}_{n+1}^3+C_2{r}_{n+1}^2+C_1{r}_{n+1}+C_0=0$            (3)

where
$C_4=H[1-{(l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)}^2]$            (4)

$\begin{array}{c}{C}_3=2H\{l_{n+1}(x_{n+1}-x_n)+m_{n+1}(y_{n+1}-y_n)+\\ n_{n+1}(z_{n+1}-z_n)-(l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)\\ [l_n(x_{n+1}-x_n)+m_n(y_{n+1}-y_n)+n_n(z_{n+1}-z_n)]\}\end{array}$            (5)

$\begin{array}{c}{C}_2=H\{[l_n(x_{n+1}-x_n)+m_n(y_{n+1}-y_n)+\\ n_n(z_{n+1}-z_n){]}^2+{(}^{x_{n+1}}+\\ {(}^{y_{n+1}}+{(}^{z_{n+1}}\}\end{array}$            (6)

$C_1=0$            (7)

$C_0=k_2{r}_n^2+k_1{r}_n^{}+k_0$            (8)

$H={(\frac{f_n}{f_{n+1}})}^2{(\frac{L_{n+1}}{L_n})}^2\frac{1}{r_n^2}$            (9)

and,
$k_2={(l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)}^2-1$            (10)

$\begin{array}{c}{k}_1=2\{l_n(x_{n+1}-x_n)+m_n(y_{n+1}-y_n)+n_n(z_{n+1}-z_n)-\\ (l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)[l_{n+1}(x_{n+1}-x_n)+\\ m_{n+1}(y_{n+1}-y_n)+n_{n+1}(z_{n+1}-z_n)]\}\end{array}$            (11)

$\begin{array}{c}{k_0=[l_{n+1}(x_{n+1}-x_n)+m_{n+1}(y_{n+1}-y_n)+n_{n+1}(z_{n+1}-z_n)]}^2-\\ {{(x}_{n+1}-x_n)}^2-{(y_{n+1}-y_n)}^2-{(z_{n+1}-z_n)}^2\end{array}$             (12)

In the distance estimating Eqn. (3), each n-th distance from a target to the camera, r_n, could be obtained if the initial distance information r₀ is known, as through Radar or Lidar.

Nevertheless it is more attractive for passive ranging without initial distance. To our knowledge, when we have known some certain length x₀ on target, the distance difference between two sampling time could be got as below

$\Delta =r_{n+\text{1}}-r_n=f{x}_{\text{0}}\frac{L_n-L_{n+\text{1}}}{L_{n+\text{1}}\cdot L_n}$            (13)

Substitute Eqn. (13) into Eqn. (3), we obtain a nonlinear Eqn. (14) as below¹⁵

$D_4{r}_n^4+D_3{r}_n^3+D_2{r}_n^2+D_1{r}_n+D_0=0$            (14)

where

$D_4=C_4$            (15)

$D_3=4C_4\Delta +C_3$            (16)

$D_2=6C_4{\Delta }^2+3C_3\Delta +C_2+k_2$           (17)

$D_1=4C_4{\Delta }^3+3C_3{\Delta }^2+2C_2\Delta +C_1+k_1$           (18)

$D_0=C_4{\Delta }^4+C_3{\Delta }^3+C_2{\Delta }^2+C_1\Delta +k_0$            (19)

Equation (14) is essentially a 4-order nonlinear eqnuation on rn. By solving Eqn. (14), r_n could be obtained, consequently by r_n+1 = r_n + Δ Up to now, a passive distance finding scheme without initial distance has been achieved.

Compared with Eqn. (3), the initial distance r0 is no longer needed in Eqn. (14). It is particularly convenient in practical application. According to FU¹⁵, et al. the errors result from reduced-model experiment using Eqn. (14) is much close to 4%. Because of introduction of variable Δ, it is not valid in passive ranging to non-cooperation target. In addition, there sometimes exists occurrence of pathological solution to the current quartic Eqn. (14). This problem needs to be overcome.

A factor worthy to be pointed out is that the ranging algorithm need only two frames of image in Eqn. (3) or Eqn. (14), this merit is beneficial to prevent ranging error diffusion. As we know, Eqn. (3) and Eqn. (14) use not only the image information but also the imaging directions, that is, there exists some redundancy information in it. This redundancy information is favorable for the associated algorithm to be improved.

Multiplying r_n² to both sides of Eqn. (3), we get Eqn. (20) as below:

$C_4{r}_n^2{r}_{n+1}^4+C_3{r}_n^2{r}_{n+1}^3+C_2{r}_n^2{r}_{n+1}^2+C_1{r}_n^2{r}_{n+1}+C_0{r}_n^2=0$            (20)

Let
$\{\begin{array}{l}{C}_{40}=C_4{r}_n^2\\ C_{30}=C_3{r}_n^2\\ C_{20}=C_2{r}_n^2\\ C_{10}=C_1{r}_n^2=0(\because C_1=0)\\ C_{00}=C_0{r}_n^2=k_2{r}_n^4+k_1{r}_n^3+k_0{r}_n^2\end{array}$            (21)

The Eqn. (20) is turned into the Eqn. as below:
$C_{40}{r}_{n+1}^4+C_{30}{r}_{n+1}^3+C_{20}{r}_{n+1}^2+k_2{r}_n^4+k_1{r}_n^3+k_0{r}_n^2=0$            (22)

Substitute the distance ratio in adjacent sampling times, ρ=r_n/r_n+1 into Eqn. (22), we can get Eqn. (23) as below:
$(C_{40}+k_2{\rho }^4)r_{n+1}^4+(C_{30}+k_1{\rho }^3)r_{n+1}^3+(C_{20}+k_0{\rho }^2)r_{n+1}^2=0$            (23)

After reduction of Eqn. (23), we get Eqn. (24):
$A_2{r}_{n+1}^4+A_1{r}_{n+1}^3+A_0{r}_{n+1}^2=0$            (24)

Since the target’s distance rn+1≠0, Eqn. (24) is re-written as Eqn. (25):
$A_2{r}_{n+1}^2+A_1{r}_{n+1}^{}+A_0=0$           (25)

From Eqn. (3) through Eqn. (12) and Eqn. (21), the coefficients of ranging Eqn. are determined as below
$A_2=({\rho }^4-H^{\prime })[{(l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)}^2-1]$           (26)

$\begin{array}{c}{A}_1=2H^{\prime }\{l_{n+1}(x_{n+1}-x_n)+m_{n+1}(y_{n+1}-y_n)+\\ n_{n+1}(z_{n+1}-z_n)-(l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)\\ [l_n(x_{n+1}-x_n)+m_n(y_{n+1}-y_n)+n_n(z_{n+1}-z_n)]\}+\\ 2{\rho }^3\{l_n(x_{n+1}-x_n)+m_n(y_{n+1}-y_n)+n_n(z_{n+1}-z_n)-\\ (l_{n+1}{l}_n+m_{n+1}{m}_n+n_{n+1}{n}_n)\cdot [l_{n+1}(x_{n+1}-x_n)+\\ m_{n+1}(y_{n+1}-y_n)+n_{n+1}\cdot (z_{n+1}-z_n)]\}\end{array}$           (27)

$\begin{array}{c}{A}_1=H^{\prime }\{[l_n(x_{n+1}-x_n)+m_n(y_{n+1}-y_n)+\\ {n_n(z_{n+1}-z_n)]}^2+{(x_{n+1}-x_n)}^2+{(y_{n+1}-y_n)}^2+\\ {(z_{n+1}-z_n)}^2\}+{\rho }^2\{[l_{n+1}(x_{n+1}-x_n)+\\ {m_{n+1}(y_{n+1}-y_n)+n_{n+1}(z_{n+1}-z_n)]}^2-{(x_{n+1}-x_n)}^2-\\ {(y_{n+1}-y_n)}^2-{(z_{n+1}-z_n)}^2\}\end{array}$            (28)

$H^{\prime }=H{r}_n^2={\left(\frac{f_n}{f_{n+1}}\right)}^2{\left(\frac{L_{n+1}}{L_n}\right)}^2$           (29)

In Eqn. (26) through Eqn. (28), ρ=r_n/r_n+1=L_n+1/L_n, it is an approximation of Eqn. (2) in a smaller sampling interval. On L_n+1 or L_n, detailed process is demonstrated as below.

Let points A, B, C and A', B', C' be the matched points respectively in two adjacent frames. We would determine the line segment feature from these points, A, B and C for example, as shown in Fig. 3 A circumcircle for points A, B and C with the center named O' could be determined; we take MN, diameter of the circumcircle of triangle ABC, as our characteristic linearity. With this improvement, the characteristic linearity could be obtained more easily than that in Fu¹⁵, et al.

In this method, it needs only three matched points for extracting the line features, while three points is the least number in image matching. In order to obtain at least three matched points, an effective approach is adjusting the image contrast in certain range before image matching. Equations (25), (14), and (3) are homologous equations, but the former has lower orders, so its ranging error should be no more than of the latter’s.

As for the distance estimation Eqn. (25), it will always have solution provided that the observer has non-zero displacement in adjacent sampling times, i.e. the target’s distance can always be estimable. This could be satisfied by continuous observer maneuver. Even if the distance difference δ is zero, the discriminant of a quadratic equation, A₁² − 4A₂A₀, is still greater than zero, that is the Eqn. (25) can be solved.

So far, our method does not need prior knowledge about the target, so it is quite suitable for non-cooperation target ranging. Figure 4 is the flow chart of our method for application. It has been found in our experiment that the step of ‘contrast adjustment in target and its adjacent region’ is indeed necessary for image matching and characteristic linearity extraction. Building a quadratic equation is our main improvement.

To verify the passive ranging algorithm based on Eqn. (25), we conducted reduced-model experiments with a ratio of 1:2300. As space is limited, here in Fig. 5 we only present the 16 frames of image with even numbers in the sequence. The photographing conditions and measurement results are shown in Table 1. It can be seen in Fig. 5, that there occurs a great change in the target. Even so, the ranging error is acceptable.

All the pictures in this paper were taken by a Sony ExwavePRO CCD with 768 x 576 pixels, the aircraft in pictures is a F16 model with length of 24 cm, and background removing has been done before this experiment. In natural scenario work, we us a moving target tracking technology from Visionlab23, so the contour detection and background removing become easy. Moreover, in our method only 3 matched points are required, it is the least requirement in imaging tracking.

In this experiment, the aircraft is moving in an arc shaped path and the surveyor is moving in a straight line, it can be seen in the image sequence that there is a significant change in the target’s attitude. In Table 1, relative error of target’s distance estimation is less than ±4 % in most cases, the biggest relative error is 7.81 %, and such errors can meet the demand of practical application.

As for static observer, ranging Eqn. (14) can still be used to estimate the distance. The results fully show that our improved algorithm is able to adapt to changes in target’s attitude. As a control, another group of pictures named sequence B are given in Fig. 6, and the ranging errors are shown in Table 2. In Fig. 6, only the frames with odd numbers are present. Experimental study shows that Table 2 has less error than that in Table 1, due to the less change in the target’s attitude in Fig. 6. In most cases, experimental errors are between Table 1and Table 2.

We proposed an algorithm for non-cooperation target passive ranging, in which distance estimation is turned into solving a quadratic equation after utilizing target’s imaging features and the camera positions. In contrast with the former algorithm of solving a quartic Eqn. (15), the new algorithm of solving a quadratic equation avoids pathological solutions, such as the complex solution, negative solutions, etc. Hence the new algorithm shows much more worth in practical application than the former ones. Theoretical analysis indicates that the new algorithm always has solution provided that the platform of observer has non-zero displacement in adjacent sampling times. The proposed algorithm is also examined by indoor reduced mode experiments which show that it can be implemented in practical passive ranging and the relative ranging error is less than ±4% in most cases. We also demonstrated that the distance estimation would be in much simpler mathematical form for moving observer.

This work was supported by both the National Natural Science Foundation of China under Grant No. 60872136 and by Natural Science Basic Research Plan in Shaanxi Province of China (Program No. 2011JM8002). The authors would like to thank the anonymous reviewers for their valuable advice toward the improvement of this article.

1. Reilly, J.P.; Klein, T. & Ilver, H. Design and demonstration of an infrared passive ranging. John Hopkings APL Technical Digest, 1999, 20(2), 1854-1859.

2. Suhr, J.K.; Jung, H.G.; Bae, K.H. & Kim, J.H. Monocular motion stereo-based free parking space detection apparatus and method. US Patent 8134479, 13 March 2012.

3. Olson, C.F. & Abi-Rached, H. Wide-baseline stereo vision for terrain mapping. Machine Vision Appl, 2010, 21(5), 713-725.[Full text via CrossRef]

4. Hewson, R. Taurus KEPD 350 (KEPD 150). Jane’s Air-Launched Weapons (Air-to-surface Missiles-Stand-off and Cruise). 24 April, 2012. (Accessed on 12 September, 2012).

5. Lepetit, V. & Fua, P. Monocular Model-Based 3D Tracking of Rigid Objects: A Survey. Foundations Trends Comput. Graphics Vision, 2005, 1(1), 1-89.[Full text via CrossRef]

6. Tuytelaars, T. & Mikolajczyk, K. Local invariant feature detectors: a survey. Foundations Trends Comp. Graphics Vision, 2008, 3(3), 177-280.[Full text via CrossRef]

7. Yilmaz, A.; Javed, O. & Shah, M. Object Tracking: A survey. ACM Computing Surveys, 2006, 38(4), pp. 1-45. [Full text via CrossRef]

8. Newcombe R. A.; Davison A. J. & Izadi S. Kinect Fusion: Real-time dense surface mapping and tracking. In the IEEE International Symposium on Mixed and Augmented Reality(ISMAR’11), Basel, Switzeland, October 2011, pp.127-136.[Full text via CrossRef]

9. Zhang, Z.; Huang, Y.; Li, C. & Kang, Y. Monocular Vision Simultaneous Localization and Mapping using SURF. In 7th World Congress on Intelligent Control and Automation (WCICA’ 2008), Chongqing, China, June 2008, pp. 1651-1656. [Full text via CrossRef]

10. Baker, P. & Kamgar-Parsi, B. Using shorelines for autonomous air vehicle guidance. Comp. Vision Image Understanding, 2010, 114(6), 723-729.[Full text via CrossRef]

11. Le, M. H. & Jo, K. H.. Building detection and 3D reconstruction from two-view of monocular camera. In Computational Collective Intelligence. Technologies and Applications, Berlin Heidelberg. September 2011, pp.428-437.[Full text via CrossRef]

12. Cannons, K. & Wildes, R. P. A Unifying Theoretical Framework for Region Tracking, York University Technical Report, CSE-2013-04, February 8, 2013.

. Xiong, T. & Debrunner, C. Stochastic car tracking with line-and colour-based features. IEEE Trans. Intell. Transp. Syst., 2004, 5(4), 324-328.[Full text via CrossRef]

14. Zhang, Y.; Wang, Y. & Qu, H. Rotation and Scaling Invariant Feature Lines for Image Matching. In the 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, Jilin, China, August 2011, pp.1135-1138.[Full text via CrossRef]

15. FU, X.; LIU, S. & LI, E. A real time image sequence procession algorithm for target ranging. In the Proceeding SPIE 6279: High-Speed Photography and Photonics, September, Xi’an, China, Nov 2006. Part 2, p. 62793A.

16. Troiani, C. & Martinelli, A. Vision-aided inertial navigation using virtual features. In the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), October 2012, pp. 4828-4834.[Full text via CrossRef]

17. Priyanka, D.D. & Dhok, G.P. Analysis of distance measurement system of leading vehicle. Inter. J. Instrumentation Control Sys., 2012, 2(1), 11-23.[Full text via CrossRef]

18. Smith, P.; Reid, I. & Davison, A. Real-Time Monocular SLAM with Straight Lines. In the Proceeding of 2nd International Symposium on Visual Computing, Edinburgh, GB, November 2006. pp. 1-10.[Full text via CrossRef]

19. Rosten, E. & Drummond, T. Fusing points and lines for high performance tracking. In Proceedings of the 10th IEEE International Conference on Computer Vision, Beijing, China, October 2005, 2, pp. 1508-1515.[Full text via CrossRef]

20. Ansar, A. & Daniilidis, K. Linear pose estimation from points or lines. IEEE Trans. Pattern Anal. Mach. Intell., 2003, 25(4), 1-12.

21. Von Gioi, R. G.; Jakubowicz, J.; Morel, J. M. & Randall, G. LSD: A fast line segment detector with a false detection control. IEEE Trans. Pattern Anal. Mach. Intell., 2010, 32(4), 722-732.[Full text via CrossRef]

22. Gong, J.; Fan, G.; Yu, L.; Havlicek, J. P. & Chen, D. Joint view-identity manifold for target tracking and recognition. In the 19th IEEE International Conference on Image Processing (ICIP), Orlando FL, USA, September 2012, pp.1357-1360.[Full text via CrossRef]

23. VisionLab VCL + Source code 4.5, URL:http://visionlab-vcl-source-code.en.softonic.com/.