ELSEVIER ISPRSJournalofPhotogrammetry& RemoteSensing52 (1997)122-131 PHOTOGRAMMETRY & REMOTESENSING Automatic aerotriangulation concept, realization and results L. Tang a,*, j. Braun b, R. Debitsch b a TechnicalConsulting and Software Developmentfor Photogrammetry,Remote Sensing and Geoinformatics, Riesstr. 65, 6.0G/332, D-80993 Munich, Germany bCarl Zeiss, D-73446 Oberkochen, Germany Accepted8 April1997 Abstract An automatic aerotriangulation system is described. Its design and development have been made to possibly meet every requirement from photogrammetric practice. The system consists of five components, i.e. block preparation, fully automatic tie point determination, semi-automatic control point measurement, interface to diverse block adjustment programs and block post-processing. A relational data base takes care of communications among individual components. The fully automatic tie point determination plays a key role in the whole system. Its realization follows the principle of image connection and thus exhausts the technical potential to reach the highest level of automation. Intensive operational tests were carded out using diverse image blocks with various configurations from photogrammetric practice. Different terrain types and ground covering as well as various camera focal lengths and image scales were considered. On average 200-500 tie points were determined per image. The achieved standard deviation of image coordinates amounts to 0.2-0.5 pixel. The computation time for the tie point determination is about 5 min per image. It was proven that automatic aerotriangulation provides higher reliability of results and much more economy to the photogrammetric practice than ever before. The system is now in daily operation in practice. Keywords: automatic aerotriangulation; digital photogrammetry; digital image matching; tie point; image connection 1. Introduction With the rapid development of digital technology, photogrammetry is entering a digital era. The most significant feature of digital photogrammetry is the high automation of individual processing procedures, e.g. automatic interior and relative orientation, automatic digital terrain or surface modelling and automatic orthoimage generation. This brings much more economy to the photogrammetric practice of today and leads, as a matter of fact, to a *Correspondingauthor. revolutionary change in the photogrammetric pro- duction. Aerotriangulation (AT) is an essential task in photogrammetry. The tie point selection, transfer and image coordinate measurement in the course of conventional AT require intensive interaction of a human operator and belong to the most laboured and timeconsuming work. Thus, an automatic AT or AAT is highly desirable in practice. Since the early nineties, research and development of algorithms for automating AT have been conducted at several institutions (e.g. Tsingas, 1992; Schenk and Toth, 1993; Ackermann and Tsingas, 1994). Today, AAT is one of 0924-2716/97/$17.00 1997ElsevierScienceB.V. All rightsreserved. PII S0924-27 16(97)00012-9 L. Tanget aL/ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 123 the highlights in the photogrammetric research and development (e.g. Ackermann, 1995; FiSrstner, 1995; Fritsch, 1995; Mayr, 1995; Schenk, 1995, 1996) and commercial products of this kind are becoming available on the market (e.g. Braun et al., 1996; Krzystek et al., 1996; Miller et al., 1996). PHODIS AT is such a commercial AAT system from the Carl Zeiss company (cf. Braun et al., 1996). Its design and development have been made to possibly meet every requirement from the photogrammetric practice (e.g. Tang, 1996). This paper deals with issues concerning the concept and realization of PHODIS AT. System components are described. Achieved results are presented and economic issues discussed. 2. Concept 2.1. AT steps AT aims to determine exterior orientation parameters of images of a photogrammetric block. It is usually realized by a block adjustment using tie points determined in the neighbouring images of the block. A conventional indoor AT procedure can consist of the following steps (cf. Fig. 1): I Blockpreparation 4' I Tiepointdetermination 4, I GCPacquisitioninimages I (Bundle)blockadjustment ~ '--'~Results~ Fig. 1.Flowchartofaerotriangulation. (1) Block preparation, where among others images are ordered according to the flight plan, camera data and ground control information (e.g. ground control points or GCPs) are collected. (2) ~e point determination, which includes (a) point selection, where distinct image points are chosen around standard positions, marked and assigned with unique names or number codes, (b) point transfer, where selected image points are transferred to the neighbouring images by means of e.g. a point transfer device, (c) measurement of image coordinates of tie points, which can be performed in mono or stereo mode on a comparator or an analytical plotter. (3) GCP acquisition in images, where GCPs are identified in the images with the help of given sketches and the measurement can be done in the same manner as that of tie points. (4) (Bundle) block adjustment, which is carried out by a computer program, using image coordinates of tie points, image and object coordinates of GCPs and camera data as input, and determines exterior orientation parameters of the images and object coordinates of the tie points. 2.2. Automation Obviously, the block preparation requires human knowledge and can hardly be automated. However, using e.g. Global Positioning System (GPS) techniques for the block flight may make this kind of work much easier. The block adjustment is a purely computational job and performed already without any human interaction. Since specific knowledge is needed to identify GCPs in images and GCP types and shapes can vary considerably, a full automation of the step of GCP acquisition in images is hardly realizable. However, the measurement of image coordinates can be overtaken by digital image matching techniques (e.g. Gtilch, 1995). In addition, the number of GCPs in a block is usually limited. Therefore, a semi-automatic acquisition is very helpful in practice. The tie point determination remains the most labour- and time-consuming work in the whole procedure. Since the determination of tie points in images is a kind of non-semantic processing, i.e. no specific features need to be recognized, a full automation of this step is possible. 124 L. Tanget al./ISPRS Journalof Photogrammetry&RemoteSensing52 (1997)122-131 In one word, automation in AT means a fully automatic tie point determination and a semi-automatic GCP acquisition in images. 2.3. Design issues Basic ideas for system design of PHODIS AT are (a) to exhaust the technical potential for reaching the highest level of automation in AT, and (b) to keep the system requirements to a very limit. In conception of the system, special attention was paid to the following aspects: * High reliability and robustness. This is the most important issue for any automatic procedure. Therefore, specific strategies are needed for algorithmically realizing the automation. * Easy operation. Only readily available information and data of a block can be required. Human interaction should be menu-driven. Automation means really a 'one-clicking' action. No specific parameters must be adjusted by users for automatic procedures. * Any block configuration. The system should be able to deal with any kind of block configuration which may occur in practice. * Any block size. Due to the huge amount of data of a possibly large block and the limited storage capacity of a computer, the processing can be carried out only piece by piece. The system should be capable of subdividing a block into small subblocks, handling them one after another and adjusting either the subblocks individually or the block as a whole. * Open interface to block adjustment programs. Since many kinds of commercial block adjustment program packages or user-owned programs are already in daily use of photogrammetric production, no special block adjustment program must be included in the system. Data exchange should be supported for popular commercial program packages and also open for any kinds of user-owned programs. * Data format for plotting systems. Exterior orientation parameters and/or tie points can be transformed into diverse data formats for digital, analytical and even analogue plotting systems. 3. System description Fig. 2 shows the system structure of PHODIS AT. Five procedures are involved in the system, i.e. block preparation, fully automatic tie point determination, semi-automatic GCP acquisition, (bundle) block adjustment and block post-processing. A relational data base holds all kinds of input information and data as well as results of an AT block, and supports the communication and the processing in the individual procedures. The core of the whole system is the procedure of fully automatic tie point determination. Comprehensive descriptions on PHODIS AT can be found in Braun et al. (1996). In the following, Blockpreparation 4' 4, Fully automatic tie point determination Semi- automatic GCP acquisition (Bundle)blockadjustment ~__._DATA BAS~.~ * Block information * Imageinformation * Cameradata * Interiororientation * GCPs * Tie points l~_~~Exterior orientation Fig.2. SystemstructureofPHODISAT. --~ Blockpost-processing I digital,analytical, I I analogue I k-- _ _ plottingsystems / L. Tang et al./ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 125 key features and new updates of individual system components are given. 3.1. Block preparation The system requires the following readily available inputs: (1) digital image data; (2) camera protocol; (3) approximate projection centres; (4) ground control information. Approximate projection centres can be derived either from the log file of a flight planning system (e.g. T-FLIGHT) or simply by reading the flight plan. GPS measurements, if available, can make this kind of estimation more precise, but are not necessarily required by the system. Based on these input data and using a special graphical editor, the block structure can be defined and generated. A block can consist of one or more normal and/or crossing strips and a strip of any number of images. For an AAT system, the image data amount is tremendous. A black-and-white aerial image scanned with a geometric resolution of 15 /zm and a radiometric one of 8 bits results in a data amount of about 240 Megabytes. Therefore, it is quite possible that in practice not all images of a block can directly be accessed by computer. In this case, the block must be subdivided into parts. A subblock editor serves to define subblocks in a block for independent processing. In order to guarantee a welltied block for adjustment, subblocks should overlap each other by at least two images in flight direction and one image strip across the flight direction. Before starting the automatic procedures, two basic operations must be carried out for each image in the subblock to be processed, i.e. image pyramid generation and establishment of the image-pixel coordinate relationship. The former is carried out autonomously and the latter can be performed by an integrated automatic or manual interior orientation procedure. A graphical block display helps to schematically visualize the block, define or select a subblock and optionally show the number, the icon or the interior orientation result of each image in the selected subblock. 3.2. Fully automatic tie point determination This procedure is supported by a coarse-to-fine image matching approach combining feature-based matching (FBM) and least squares matching (LSM) techniques. The approach is an extension of the one which is successfully used for automatic relative orientation in the digital plotter PHODIS ST from Carl Zeiss (Tang and Heipke, 1993, 1994, 1996; Tang et al., 1996). 3.2.1. Principle of image connection The realization of fully automatic tie point determination follows the principle of image connection (cf. Tang, 1996). Instead of concentrating on standard positions as usual by conventional methods, the whole area of an image is searched for possibly well-defined tie points. Two practical reasons support this principle. First, tie points evenly distributed over the whole area of an image intuitively present a stable geometric connection to its neighbouring images in the block. Second, the texture appearance on an image is hardly foreseeable and concentrating on certain small areas for good tie points is, therefore, not very realistic for a fully automatic process. As a matter of fact, the following evident advantages come with this principle: * Optimal use of information. Whatever an image looks like, tie points will be extracted from those areas where good texture exists. No prepositiouing is needed and no special analysis of image content is necessary. This leads to an optimal use of the information provided by the image and the best connection to the neighbouring images. * High reliability and robustness. The optimal use of information in an image also explores the best possibilities for connection. Locally poor texture will not affect the global connection. In addition, an efficient mechanism based on some global mathematical models (e.g. collinearity equations) can be incorporated to ensure the geometric consistency of the obtained tie points and, as a matter of fact, the reliability and robustness of the final results. * Global control. Global area image connection instead of local point transfer can lead to a very strong interior geometric stability of the block. The block distortion can also be compensated optimally. Thus, it can be expected that the number of GCPs 126 L. Tanget al./ ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 BlockFormation extract features connect right image connect previous strip updatetie point list + Point Tracking definewindows performLSM fillouttie point list startlevel I I t l // ',i / .... _ .... ,/,,. intermediate level ! s I , \ I I I I I I I I I I t l ..... | ' ; --,* ie pom,u~, ) t / destinationlevel t ~ , ~ ............ _~t Fig.3. Conceptoffullyautomatictie pointdetermination. for the block adjustment might be reduced to a very limit and even more labour-intensive work can be saved. * Easy operation. Precise initial exterior orientation parameters of images are not necessary, and neither are elevation models. Only the general block information (e.g. strips, neighbourhoods or approximate projection centres) is required to run the automatic process. 3.2.2. Approach In order to realize the principle of image connection and at the same time to speed up the procedure as much as possible from the practical point of view, a hierarchical image matching approach was developed based on image pyramid techniques. Fig. 3 shows the principle of fully automatic tie point determination in PHODIS AT. The image pyramids are divided into two parts by defining a so-called intermediate level. The upper part includes levels with small image sizes and lower resolution and the lower part the ones with increasing image sizes and higher resolution. Two steps are involved in the fully automatic procedure. The first step is called 'block formation', serving to connect images of the whole block together through the upper part of the pyramids till the intermediate level. The second step is called 'point tracking', aiming at achieving as high a measuring accuracy of each tie point as possible through the lower pyramid levels. The idea of introducing the intermediate level is to arrive at an optimal combination of the use of available information and the computational time. Thus, the intermediate level will be defined at that level, in which the tie point determination can still be carried out fast enough and from which enough tie points can be generated for a reliable point tracking. Block formation is achieved by connecting individual images with their neighbours in the block. FBM is used to determine conjugate points in image pairs. For each image, point features are first extracted by means of an interest operator. They are then matched according to certain geometric and radiometric criteria. For connecting the right image within a strip to the left one, the matched point pairs are used as observations in a robust bundle adjustment, in which relative orientation parameters and object coordinates of the points are determined and outliers are eliminated. The orientation parameters and the point object coordinates are then forwarded to the next lower pyramid level on which the matching procedure is repeated. For connecting an image of the previously processed neighbouring strip, due to the possibly very limited overlap, a robust affine transformation is performed to eliminate outliers in the matching. Tie points are administrated in a list, which is updated with new points during the course of block formation. Manifold tie points are obtained by checking those shared features of feature pairs in common images. The final result of the block formation is the tie point list generated at the intermediate level, in which a tie point is provided with a unique name, the number of tie images and a list of names of these tie images including the measurements of the image coordinates. In order to precisely measure the image coordinates of a point in the tie images, LSM is performed pair by pair in all combinations through the lower part of the pyramids. Around a given point pair at the intermediate level, a reference and a search window are defined. Six affine parameters and two radiometric ones are calculated between the two windows. For a convergent result, the cross correlation coefficient between the two windows is then computed. If the coefficient is larger than a threshold, the match is declared as successful. An interest operator is used in the reference window to find a proper point. L. Tanget al./ISPRS JournalofPhotogrammetry&RemoteSensing52 (1997)122-131 127 This point is then transformed to the search window via the afline parameters, defining the corresponding point there. These two points are mapped onto the next lower pyramid level and LSM repeats. At the end of point tracking, the tie point list is updated with image coordinate measurements in the original image resolution. Since the number of tie points in an image can be unnecessarily large for the block adjustment, the 2-fold tie points are tracked only selectively. As a result, the fully automatic procedure for tie point determination in PHODIS AT delivers those tie points which are evenly distributed over the whole area of each image and accurately measured in original images. With respect to the issue of implementation, no control parameters for matching need to be set by the user. Thus, this procedure can be considered an autonomous process. 3.3. Semi-automatic GCP acquisition In PHODIS AT, the measurement of GCP image coordinates can be carried out manually or semiautomatically. The semi-automatic GCP acquisition in images leaves the identification task to the human operator and the fine coordinate measurement to the LSM algorithm. The idea is that tie points evenly distributed over the whole area of an image are used to define local transformation parameters to the neighbouring images. Given a position in the image, the approximate corresponding positions in the neighbouring images can be calculated via the local transformation parameters. In this way, the human operator needs to identify and finely locate a GCP only in one reference image, and a hierarchical multi-image LSM algorithm then takes care of finding those correspondences in other images. Supposing that a GCP appears in six images, all six images have to be searched by the human operator for the GCE Thus, even more comfort is provided by PHODIS AT for this task after the automatic procedure of tie point determination. 3.4. (Bundle) block adjustment The block adjustment in PHODIS AT is open for any popular commercial program packages or user-owned programs. This intention is based on the fact that the photogrammetric practice is accustomed to its own block adjustment programs since decades and it is not necessary to convince anyone to use an unfamiliar program. Interfaces need to be created for data exchange between PHODIS AT and user-owned systems, which can even be started on any kind of computer platforms. 3.5. Block post-processing The block post-processing includes documentation of GCPs and new points (GCPs-to-be), and generation of model setup parameters for image orientation on digital, analytical and even analogue plotting systems. 4. Practical experiences and economic issues During the whole phase of development, PHODIS AT was intensively tested. New requirements and suggestions from various testsides considerably helped to improve and complete the functionality and performance of the system. In the following, we will briefly present our experiences with PHODIS AT and discuss some economic issues with respect to AAT. Table 1 shows the results obtained by using PHODIS AT. All the test blocks came from photogrammetric practice and present various terrain types (e.g. flat, hilly) and ground covering (e.g. snow/ice, urban or industrial areas, forestry). Images were taken by cameras with focal length ranging from 85 mm to 305 mm at scale factors of I : 3000 to 1 :72,000, and scanned in a resolution of 15, 20 and 28 /zm. On average 200-500 evenly distributed tie Table 1 Practicalresultsobtainedby usingPHODISAT Resolution Focallength Scalefactor o0 (/zm) (ram) (/zm) Antarctic 15 85 1:72000 7.7 Urban 15 305 1:4000 5.2 Hilly/forested 15 153 1:3000 5.1 Rural 20 153 1:5500 3.9 Industrial 28 153 1:3000 5.9 Poorcontrast 28 153 1:3000 6.0 128 L. Tang et al. I ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 ~i~ ~ I 7\ 7 / Fig. 4. Three examples of 3-fold tie points automatically determined by PHODIS AT in images of urban areas. points were determined per image, which guarantees a high reliability of the final result. The achieved standard deviation of image coordinates amounts to 0.2-0.5 pixel, a level of accuracy that a human operator can reach. The computation time for the tie point determination is about 5 min per image on a Silicon Graphics workstation with R4400 processor (200 MHz). Fig. 4 gives some typical examples of tie points automatically determined by PHODIS AT in images of urban areas. Fig. 5 shows the final distribution of tie points on a selected part of a strip of infrared images taken in a coastal area to demonstrate how well the principle of image connection for automatic tie point determination works in the case that no suitable texture can be found in the standard positions. Two examples of practical photogrammetric blocks with crossing flights are given in Fig. 6. Obviously, the connection of crossing strips with normal ones should not be restricted to any predefined positions on images. Again, the principle of image connection brings another evident advantage to make this kind of strip connection straightforward. Fig. 7 gives an example of a 6-fold tie point found L. Tanget al./ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 129 Fig. 5. The PHODISATtie pointdistributionon a selectedpartof a stripof infraredimagestakenin a coastalarea,wheretie pointsare markedby 'whiteplus' and darkhomogeneousareaspresentwatersurfaces. between a normal and a crossing strip of block (b) in Fig. 6. Table 2 presents an empirical time comparison between the analytical AT and PHODIS AT for processing a block consisting of 110 images scanned in 14/zm and 30 GCPs. The analytical AT needs 140 hours or about 18 days (8 h/day) of human work. On the contrary, only 2 days are needed when using PHODIS AT by the human operator and another two days by the computer, which do not necessarily belong to the standard cost accounting in general. This means that PHODIS AT is more economic than the analytical AT by a factor of 9. Using AAT brings not only a considerable time improvement but also more comfort for the human worker. The role a human operator plays is mainly to supervise or control individual procedures. The hardest work is then taken over by the computer. 5. Conclusions and outlook Commercial systems for AAT become available on the photogrammetric market. Their practical use brings much more economy and leads to a revolutionary change in the photogrammetric production. In the photogrammetric practice of today, which is still dominated by analytical or even analogue systems, AAT is ready to replace the conventional AT to directly provide image orientation to the analytical or analogue systems. With rapid advances of digital photogrammetry, the vision that a production chain can be built up which allows automatic image scanning, automatic aerotriangulation, automatic digital terrain or surface modelling and orthoimage generation, and even automated data acquisition for geographic information systems, is becoming reality (Tang, 1997). 130 L Tanget al./ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 Fig. 6. Two examples of practical photogrammetric blocks: (a) block with perpendicular crossing strips; (b) block with arbitrarily angular crossing strips. Table 2 Comparison between the analytical AT and PHODIS AT for a block of 110 images scanned in 14/xm, including 30 GCPs Analytical AT PHODIS AT procedure human (h) procedure human (h) computer (h) Scanning 2 18.4 Preparation, Preparation 2 11 tie point determination, 130 tie point determination 9.2 GCP acquisition GCP acquisition 3 Post-processing 10 Post-processing 8 Data backup 1 7 Total 140 Total 16 45.6 References Ackermann, E, 1995. Automatic aerotriangulation. Proceedings of 2nd Course in Digital Photogrammetry, Bonn. Ackermann, F., Tsingas, V., 1994. Automatic digital aerial triangulation. Proceedings ASPRS/ACSM Annual Convention, Reno, Vol. I, pp. 1-12. Braun, J., Tang, L., Debitsch, R., 1996. PHODIS AT -- an automated system for aerotriangulation. Int. Arch. Photogrannn. Remote Sensing 31 (B2), 32-37. L. Tang et al. / ISPRS Journal of Photogrammetry & Remote Sensing 52 (1997) 122-131 131 Fig. 7. An example of a 6-fold tie point found between a normal {4759, 4760, 4762} and a crossing strip {4737, 4736, 4735} of block (b) in Fig. 6. Frrstner, W., 1995. Matching strategies for point transfer. In: Fritsch, D., Hobbie, D. (Eds.), Photogrammetric Week '95. Wichmann, Karlsruhe, pp. 172-183. Fritsch, D., 1995. Introduction into digital aerotriangulation. In: Fritsch, D., Hobbie, D. (Eds.), Photogrammetric Week '95. Wichmann, Karlsruhe, pp. 165-171. G01ch, E., 1995. Automatic control point measurement. In: Fritsch, D., Hobbie, D. (Eds.), Photogranunetric Week '95. Wichmann, Karlsruhe, pp. 185-196. Krzystek, P., Heuchel, T., Hirt, U., Petran, E, 1996. An integral approach to automatic aerial triangulation and automatic DEM generation. Int. Arch. Photogramm. Remote Sensing 31 (B3), 405-414. Mayr, W., 1995. Aspects of Automatic Aerotriangulation. In: Fritsch, D., Hobbie, D. (Eds.), Photogrammetric Week '95. W1chmann, Karlsruhe, pp. 225-234. Miller, S.B., Paderes, EC., Walker, A.S., 1996. Automation in digital photogrammetric systems. Int. Arch. Photogramm. Remote Sensing 31 (B2), 250-255. Schenk, T, 1995. Zur automatischen Aerotriangulation. Z. Photogramm. Fernerkundung (ZPF) 63, 137-144. Schenk, T., 1996, Digital aerial triangulation. Int. Arch. Photogramm. Remote Sensing 31 (B3), 735-745. Schenk, T., Toth, C., 1993. Towards an automated aerial triangulation system. ASPRS/ACSM Annual Convention, Reno, pp. 652-660. Tang, L., 1996. Toward automatic aerotriangulation. Proceedings of Geoinformatics '96, Wuhan, Vol.One, pp. 433--440. Tang, L., 1997. Towards an automated photogrammetric system. Proceedings of GIS AM/FM ASIA'97 and Geoinformatics '97, Taipei, Taiwan, May 26-29, 1997. Tang, L., Heipke, C., 1993. An approach for automatic relative orientation. In: Griin, A., Kahmen, H. (Eds.), Optical 3-D Measurement Techniques, II. Wichmann, Karlsruhe, pp. 347-354. Tang, L., Heipke, C., 1994. An Automatic procedure for the relative orientation of aerial images. Proceedings of the 3rd International Colloquium of LIESMARS on Integration, Automation and Intelligence in Photogrammetry, Remote Sensing and GIS, pp. 49-58. Tang, L., Heipke, C., 1996. Automatic relative orientation of aerial images. Photogramm. Eng. Remote Sensing 62 (1), 47-55. Tang, L., Poth, Z., Ohlhof, T., Heipke, C., Batscheider, J., 1996. Automatic relative orientation -- realization and operational tests. Int. Arch. Photogramm. Remote Sensing 31 (B3), 843- 848. Tsingas, V., 1992. Automatisierung der Punkt0bertragung in der Aerotriangulation durch mehrfache digitale Bildzuordhung. Deutsche Geod~itische Kommission, Reihe C, Nr. 392, Miinchen.