Automatic feature detection and side scan sonar overlap navigation via sonar image matching

• US 5,155,706 A
• Filed: 10/10/1991
• Issued: 10/13/1992
• Est. Priority Date: 10/10/1991
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: Westinghouse Electric Company LLC (Brookfield Asset Management Incorporated)
• Inventors: Oravec, James J., Haley, Paul H.
• Primary Examiner(s): Pihulic, Daniel T.
• Application Number:
  US07/774,428
• Time in Patent Office: 369 Days
• Field of Search: 367/7, 367/88, 367/11, 358/111, 358/112, 378/99
• US Class Current: 367/7
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01S 15/8902 Side-looking sonar
• CPC Class Codes: G01S 7/539 using analysis of echo signal for target characterisation; Target signature; Target cross-section
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction

Abstract

A method of locating objects in sonar images so that matching algorithms can be used to determine if the same objects appear in two images. Information from the matching algorithms can then be used to upgrade the position of the vehicle and objects recorded in the vehicle'"'"'s navigation system. Images are improved by normalizing brightness and contrast and then convolving the image with at least one filter. The image is normalized by dividing the image into vertical strips, creating a histogram to represent the grayness values for columns of pixels in each strip and applying an algorithm to each strip to change its grayness value.

Claims

1. A method for locating objects in sonar images and other images represented by a matrix of pixels each having a shade of gray within a known grayness range taken by a vehicle of a known vehicle height scanning across a scan width at known size comprised of the steps

a) normalizing brightness and contrast in the sonar image comprising the steps of

i) Dividing the image of into vertical strips each strip having a width w wherein the width w of each strip i expressed for each strip in terms of ##EQU5## wherein i is an integer from 0 to n;

and ##EQU6## ii) Creating a histogram for each strip, the histogram being a representation of grayness values for all columns of pixels within the strip

iii) Determining a sample mean μ

_k and a standard deviation σ

_k for each histogram created for each strip

iv) Computing a new mean M_k for each strip by solving the equation

space="preserve" listing-type="equation">M.sub.k =σ

.sub.k /0.5227

v) Computing a difference Δ

μ

_k between the new mean M_k and the sample mean μ

_k for each strip so that

space="preserve" listing-type="equation">Δ

μ

.sub.k =μ

.sub.k for k=1 to n

vi) Choosing a Y_k for each strip such that Y_k =(Y_k-1 +Y_k)/2 for k=1 to n and Y_o =Y_o ;

Y_n+1 =Y_n ;

m_o =m₁ ;

m_n+1 =m_n ;

Δ

μ

_o =Δ

μ

₁ ; and

Δ

μ

_n+1 =Δ

μ

_n

vii) Determining a grayness value for each pixel in each strip, adding Δ

μ

_k to each grayness value and then dividing that sum by m_k

b) Convolving the image with at least one low pass filter;

c) Displaying the filtered image.

2. The method of claim 1 wherein the filter has a substantially round configuration.

3. The method of claim 2 wherein the convolving is done by applying a sequence of filters a first filter having an area of known value and successive filters having areas about twice, about three times and about four times the area of the first filter.

4. The method of claim 1 also comprising the step of convolving the filtered image with a spatial differentiation filter comprised of a matrix having a single row and a number of columns equal to a number of columns in the low pass filter with which the image has been convolved.

5. The method of claim 4 wherein the filter is of the form [-1 0 . . . 0 1], if the image is to the left of the vehicle'"'"'s path.

6. The method of claim 4 wherein the filter is of the form [1 0 . . . 0 -1], if the image is to the right of the vehicle'"'"'s path.

7. The method of claim 1 also comprising the step of identifying those filters which yield a reasonable number of detections and selecting for convolving the image one of the identified filters which has a lowest frequency.

8. The method of claim 7 wherein the filter is selected by

a) solving for each filter under consideration the equation

9. The method of claim 1 also comprising the step of comparing the image after filtering with a second image to determine if the image matches the second image.

10. The method of claim 9 wherein the comparison is done visually.

11. The method of claim 9 wherein the comparison is done by computer using a matching algorithm.

12. A method for matching two images each comprised of points which points each have a valve corresponding to a grayness level comprising the steps of:

a) creating a first matrix {P} containing values p_i corresponding to a grayness level of all points in a first image;

b) creating a second matrix {Q} containing values q_j corresponding to a grayness level of all points in a second image;

c) creating a matrix {P_i, Q_j } of pairs of points from the first image and the second image;

d) assigning each pair of points in matrix {P_i, Q_j } a score determined by combining the grayness level of the points thereby creating a set of scores {S_k };

e) selecting and ranking those pairs of points having a score greater than a predetermined value to create a set of selected pairs {P_h, Q_k };

f) choosing a selected pair of points {p₁, q₁ } as a centroid;

g) finding another pair of points {p₂, q₂ } such that a distance between p₁ and p₂ is a minimum of all distances between points p_i in the set of selected pairs {P_h, Q_k };

h) determining a distance d between points q₁ and q₂ ;

i) calculating a value x from the equation x=d² /r² wherein r is a preselected factor;

j) determining a Δ

s from the equation ##EQU7## k) adding Δ

s to score corresponding to the selected pair of points (p_i, q_i);

l) choosing additional selected pairs of points;

m) repeating steps h thru k for each additional selected pairs of points thereby creating a set of new scores {S_m } for the chosen pairs of points;

n) selecting those scores from set {S_m } which are greater than a predetermined threshold and declaring a match among the pairs of points which corresponding to the selected scores;

o) creating a new set of {P_i, Q_m } pairs of points containing those pairs of points selected in step n;

p) selecting from set {P_i, Q_m } those pairs of points having a common translation to form a new set;

q) using the common translation to match other points in the first image with points in the second image; and

r) displaying the first image and the second image in a manner to allow a reader to see how the images match.

13. The method of claim 12 wherein the images are displayed side-by-side and a line is drawn between at least one point in the first image to a matching point in the second image;

14. The method of claim 12 wherein the images are displayed by overlaying at least a portion of the two images such that points in the first image are on top of matching points in the second image.

15. The method of claim 12 wherein the images are sonar images.

16. The method of claim 12 also comprising the step of calculating a new Δ

s after each score by averaging all values of Δ

s previously calculated.

17. The method of claim 12 also comprising the steps of

a) computing a translation needed to align points within the set {P_m, Q_n };

b) choosing a set of points {R} from the first images;

c) applying the translation computed in step a to the points in set {R}

d) selecting a set of points {S} from the second image;

e) creating a set of pairs of points {R_i, S_j } having close grayness levels;

f) choosing a pair of points (r₁, s₁) from {R_i, S_j } as a centroid;

g) finding another pair of points (r₂, s₂) from {R_i, S_j } such that a distance between r₁ and r₂ is a minimum of all distances between points r_i in the set {R_i, S_j };

h) determining a distance d between points r₁ and r₂

i) calculating a value x from the equation x=d2/r2 wherein r is a preselected factor;

j) determining a Δ

s from the equation ##EQU8## k) adding Δ

s to the score corresponding to the pair (p₁, q₁);

l) choosing additional pairs of points from the set {R_i, S_j };

m) choosing additional point pairs from set {R_i, S_j }

n) repeating steps h thru k for each additional selected pair of points thereby creating a set of new scores {S_m } for the chosen pair of points;

o) selecting those scores from set {S_m } which are greater than a predetermined threshold; and

p) identifying on at least one image at least one point among the pairs of points which correspond to the selected scores.

18. A method of side-scan navigation to determine position and course of a vehicle having a navigation system comprising the steps of

a) making at least two passes during which sonar is operated to create a selected sonar image and a second sonar image;

b) creating a first matrix {P} containing values P_i corresponding to a grayness level of all points in a first image;

c) creating a second matrix {Q} containing values q_j corresponding to a grayness level of all points in a second image;

d) creating a matrix {P_i, Q_j } of pairs of points from the first image and the second image;

e) selecting and ranking those pairs of points having a score greater than a predetermined value to create a set of selected pairs {P_h, Q_k };

f) choosing a selected pair of points {p₁, q₁ } as a centroid;

g) finding another pair of points {p₂, q₂ } such that a distance between p₁ and p₂ in the set of selected pairs {P_h, Q_k };

h) determining a distance d between points q₁ and q₂ ;

i) calculating a value x from the equation x=d² /r² wherein r is a preselected factor;

j) determining a Δ

s from the equation ##EQU9## k) adding Δ

s to score corresponding to the selected pair of points (p_i, q_i);

l) choosing additional selected pairs of points;

m) repeating steps h thru k for each additional selected pairs of points thereby creating a set of new scores {S_m } for the chosen pairs of points;

n) selecting those scores from set {S_m } which are greater than a predetermined threshold and declaring a match among the pairs of points which corresponding to the selected scores;

o) creating a new set of {P_n, Q_m } pairs of points containing those pairs of points selected in step n;

p) selecting from set {P_n, Q_m } those pairs of points having a common translation to form a new set;

q) using the common translation to match other points in the first image with points in the second image; and

r) updating positions of the vehicle and objects in the navigation system of the vehicle from the translation.

19. The method of claim 18 wherein state estimation techniques are used to update positions of the vehicle.