ARTUS Preliminary Development by Barton S. Wells Frederick L. Beckner Final Report on Contract DAAH01-99-C-R077 Option I Cyberdynamics, Incorporated January 7, 2000 U.S. Army Aviation and Missile Command Redstone Arsenal, Alabama DISTRIBUTION STATEMENT A Approved for Public Release Distribution Unlimited 20000113 055 jmO QTTALIW BS^SBGEED 4 Form Approved REPORT DOCUMENTATION PAGE OMB No. 0704-0188 Public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 12D4, Arlington, VA 22202-4302, and to the Office of Management and Budget, Paperwork Reduction Project (07040188), Washington, DC 20503. 1. AGENCY USE ONLY (Leave blank) 2. REPORT DATE 3. REPORT TYPE AND DATES COVERED 7 Jan 00 Final 2 Aug 99 - 30 Nov 99 4. TITLE AND SUBTITLE 5. FUNDING NUMBERS ARTUS Preliminary Development C DAAH01-99-C-R077 6. AUTHOR(S) Barton S. Wells Frederick L. Beckner 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION Cyberdynamics Incorporated REPORT NUMBER 1860 Embarcadero Road, Ste. 155 CYB-OOOl Palo Alto, CA 94303-3362 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSORING/MONITORING U.S. Army Aviation & Missile Command AGENCY REPORT NUMBER AMSAM-AC-RD-A Redstone Arsenal, AL 35898-5200 11. SUPPLEMENTARY NOTES 12a. DISTRIBUTION AVAILABILITY STATEMENT 12b. DISTRIBUTION CODE Approved for Public Release; Distribution Unlimited 13. ABSTRACT /Maximum200 words) Work directed towards transitioning research conducted on the feasibility of an automatic rapid target updating system (ARTUS) to the implementation of system software is described. Implementation of one component of the ARTUS system, the ability to find features in terms of line intersections within infrared images, is performed. Methods of edge-detection, target filtering, line finding, segmentation of the lines, and segment intersection is implemented into a GUI-based software application. A new method of edge-detection is implemented using a Canny edge-detector combined with a second derivative gradient. An algorithm for filtering non-target data from target data in infrared images is created. Line finding is done using an algorithm taking the best lines from a histogram of all possible lines within an image. The lines are segmented using a technique searching for gaps in the lines, and then the intersections of these segments are found. This initial implementation of a portion of the ARTUS system is explained in this report. 14. SUBJECT TERMS 15. NUMBER OF PAGES Canny edge-detection, Gaussian, gradient, derivative, target filtering, line segments, line 21 segment intersection, line breaks, histogram. 16. PRICE CODE 17. SECURITY CLASSIFICATION 18. SECURITY CLASSIFICATION 19. SECURITY CLASSIFICATION 20. LIMITATION OF ABSTRACT OF REPORT OF THIS PAGE OF ABSTRACT UNCLASSIFIED UNCLASSIFIED UNCLASSIFIED UL Standard Form 298 (Rev. 2-89) (EG) Prescribed by ANSI Std. 239.18 Designed using Perform Pro, WHS/DIOR, Oct 94 Table of Contents Section 1: Overview 3 Section 2: Phase I Option Work 4 Section 3: Nearest-Neighbor Line Finding 5 Section 4: Improved Edge-Detection 6 Section 5: Filtering Non-Target Data 10 Section 6: Lines From Histogram 11 Section 7: Lines To Segments 15 Section 8: Finding Intersections 17 Section 9: Cube Applications 18 Section 10: Tank Applications 19 Section 11: Conclusions 20 References 21 ARTUS Preliminary Development Section 1: Overview This report contains results of a transition from a feasibility study to the development and implementation of an automatic rapid target updating system (ARTUS) for use with Army missile guidance systems based on 2D infrared target images. These systems operate by matching the infrared image from a guidance sensor with predicted infrared images derived from a database of CAD models of a number of different possible targets. Such a system can be adversely affected by externally carried objects such as fuel tanks, supply crates, etc, not contained in the CAD model. The adverse effects of such objects could be minimized if there were a way to rapidly modify the CAD model to reflect the presence of such objects based on images obtained from reconnaissance sensors, in effect tailoring the CAD model to match specific targets. Phase I of this contract dealt with studying the feasibility of developing such a software system, and developed a plan for the system and what algorithms would need to be developed to create software that could carry out these intended tasks. See the Phase I Final Report, on file at Cyberdynamics, Inc, and at the U.S. Army's Redstone Arsenal site in Alabama. Phase I Option, which this report summarizes, began the task of implementing the plans of Phase I. A major portion of the ARTUS system would be to identify features of the target in both the infrared image and the CAD model. The most common feature is the intersection of lines, and that is what the Phase I Option work focused on. Finding intersections of lines in both the infrared images and the rendered CAD models involves determining where there exists edges that can be extracted from the image, determining what lines are created by these edges and which points belong to which lines, reducing the lines to line segments, and determining which segments intersect within the image. Once the intersections are found, what type of intersection that is found needs to be determined. That is, how many line segments meet at the point of intersection? And, for each line segment, does the line segment cross the point or end at the point of intersection? Work on the location of line intersection features for the ARTUS system was performed during the Phase I option. Many methods were investigated, and a successful method to find line intersections was found and implemented into software. Section 2: Phase I Option Work The following is a list of the work accomplished during the Phase I Option. In this phase we: 1. Experimented with "nearest-neighbor" techniques of combining adjoining points to form lines. This technique, only partially successful on simple images, resulted in too many and too short of lines, as well as creating a very difficult data-handling problem. 2. Improved our edge-detection techniques on images to reduce the noise in the post edge-detected image. It was found that to find any lines within our detailed infrared images we needed to reduce the noise produced by the edge detection schemes that we had used to this point. We found that the Canny edge-detection scheme, along with our own second derivative analysis, proved to be very successful in reducing the noise associated with finding edges in the infrared image data that we had of tanks. 3. Created a filter to remove edge points not associated with the target of the image. Though the edge detector we now had worked very well, the result was the edge detection of the entire image. This was a problem because we did not want to find lines of objects that were not part of the target. We developed a filter that found the area of the target based on the detail, of the edge detection results, and removed any excess from those results. 4. Created a mathematical solution to determine the lines formed from the resulting points of an edge detection filter. Since other line-finding techniques were both poor and fairly random, we developed a technique to determine exactly what lines are within a distribution of points. By creating a histogram of the slope and y-intercept of the lines formed by joining every pair of points in the image that resulted from the edge detection, we could find the peaks of that histogram and therefore find the most prevalent lines in the point distribution. 5. Determined a method to reduce the lines to segments. Because the lines had no end points they would include isolated points or groups of points that were not associated with the main segment of each line. Many methods were tried and the result was an algorithm that allowed some small gaps in the lines, but not a large gap, nor a large number of small gaps. Gaps would occur because of the non-perfect distribution of points after the edge detection. 6. Applied these techniques to an image of a cube and to a CAD model of a cube. A cube was used to begin with because of the complicated nature of the tank images did not allow us to easily understand what was happening within our algorithms during early development. The cube provided an ideal environment to initially tune our algorithms, which we were successful at doing. 7. Applied these techniques to the images of a tank provided by the Army, and revised our techniques based on the problems that arose from these more complicated images. Moving from the cube to the tank demonstrated the difficulties with such detailed images. This was the impetus for developing improved edge detection schemes, a filter to remove edge detected points not associated with the main target of the image, and a method to reduce lines to segments, discussed in items 2, 3, and 5 of this section, respectively. Section 3: Nearest-Neighbor Line Finding A common technique for finding lines from a distribution of points, similar to that resulting from applying an edge detection mask to an image, is to start with a point, move to all of it's nearest neighbors. From there, determine if any lie along the line being created, and then do the same for each of the points included in that line. This technique, however, is always demonstrated using very few points, almost all of which fall within that line, and when looking for a line in a known direction. We were dealing with detailed images that, even with superb edge detection, create point distributions that are very complicated and full of indeterminate choices for the line finding algorithm. We also need to be able to find an undetermined number of lines that are in undetermined directions. To start the algorithm we would pick a point in the scene, look at the surrounding square of eight pixels for other points. If none were found, we would expand the square to look at the next biggest square of fourteen pixels for other points. If other points were found, the line-finding algorithm would start off in the direction of the found points, looking of a continuous series of points in that direction. Before knowing whether a line exists in a certain direction, however, it is impossible to know how large gaps may be within a line or how far from the line points may stray. Giving up on directions because gaps were found at the starting point caused lines to not be found or to be cut-off short. Allowing for too large of gaps caused large numbers of "noise" lines to be found. Following points that strayed from a line would cause the algorithm to not know what direction a line should be continue. Not selecting these points when they were part of the line would reduce the number of points in the line and might cause the line to stray off course in the opposite direction. A further problem to this method is that with undetermined lines, every point must be tried as the starting point for lines (a point may exist in multiple lines), causing the amount of time needed to complete such an algorithm with an image of any detail to become enormous. We determined that this method of line finding would not be successful for our use. Section 4: Improved Edge Detection A better edge detector was needed to handle the type of data we needed to evaluate. The edge detectors that had been used previously in Phase I, namely Prewitt, Sobel, and Kirsch detectors, worked well with many color photos but had limitations with the infrared data, such as large amounts of noise and broken edge lines. These detectors tended to have too much noise and too little of the actual edges detected, or broken edges when the edges were found. After trials with other options, it was found that the combination of the Canny Edge Detector, discussed by Hancock, Kittler, and Petrou (References 1 and 2), and our second-derivative edge detector (described in our Phase I Final Report) was exceptional in comparison with other detectors. The Canny edge detector takes the following steps: 1. The image data is smoothed by a two-dimensional Gaussian function of width specified by a user parameter. In practice, two-dimensional convolution with large Gaussians takes a long time, so that in practice we approximate this by two one dimensional Gaussians, one aligned with the x- axis, the other with the y axis. This produces two (rather than one) values at each pixel. The Gaussian function in one dimension is expressed as: G(x) = ,2cr2 42na 2. Assuming two-dimensional convolution at stage 1, the smoothed image data is differentiated with respect to the x and y directions. It is possible to compute the gradient of the smooth surface of the convolved image function in any direction from the known gradient in any two directions. Assuming the one-dimensional approximation at stage one, which we use, then the values in the x-smoothed image array are convolved with a first derivative of a one dimensional Gaussian of identical sigma aligned with y. Similarly, values in the y-smoothed image array are convolved with a first derivative of a one dimensional Gaussian of identical sigma aligned with x. Sigma is the user-set width of the Gaussian function. During the Phase I Option we used a sigma value of 1.0 for most operations. This width needs to be tested more extensively during Phase II to find an optimal level of performance. From the computed x and y gradient values, the magnitude and angle of the slope can be calculated from the hypotenuse and arctangent. The first derivative of the Gaussian function is expressed as: -X7 -X CM- ,2a' ■JlftCT3 3. Having found the rate of intensity change at each point in the image, edges must now be placed at the points of maxima, or rather non-maxima must be suppressed. A local maximum occurs at a peak in the gradient function, or alternatively where the derivative of the gradient function is set to zero. However, in this case we wish to suppress non-maxima perpendicular to the edge direction, rather than parallel to (along) the edge direction, since we expect continuity of edge strength along an extended contour. The second derivative of the Gaussian function is expressed as: „2 '-7 V2;r<7 Rather than perform an explicit differentiation perpendicular to each edge, another approximation is often used. Each pixel in turn forms the center of a nine-pixel neighborhood. By interpolation of the surrounding discrete grid values, the gradient magnitudes are calculated at the neighborhood boundary in both directions perpendicular to the center pixel, as shown in Figure 4.1, below. If the pixel under consideration is not greater than these two values (i.e. non-maximum), it is suppressed. a b c V \ d e A f h Figure 4.1: From central gradient value, interpolate gradient value at dot from gradient values at e, g, and h. Repeat in opposite direction. Suppress if non- maximum. 4. The thresholder used in the Canny operator uses a method called "hysteresis". Most thresholders used a single threshold limit, which means if the edge values fluctuate above and below this value the line will appear broken (commonly referred to as v'streaking'') . Hysteresis counters streaking by setting an upper and lower edge value limit. Considering a line segment, if a value lies above the upper threshold limit it is immediately accepted. If the value lies below the low threshold it is immediately rejected. Points which lie between the two limits are accepted if they are connected to pixels which exhibit strong response. The likelihood of streaking is reduced drastically since the line segment points must fluctuate above the upper limit and below the lower limit for streaking to occur. Figures 4-2, 4-3, and 4-4 show the results of thresholding the same tank image with Prewitt, Sobel, and Canny edge detectors, respectively. Notice the improved signal-to- noise and the reduced line-breaking in the Canny threshold image. Figure 4-2: Prewitt edge detection of tank image.