During Mine Warfare (MIW) operations, MIW analysts perform change detection by visually comparing historical sidescan sonar imagery (SSI) collected by a sidescan sonar with recently collected SSI in an attempt to identify objects (which might be explosive mines) placed at sea since the last time the area was surveyed. This dissertation presents a data structure and three algorithms, developed by the author, that are part of an automated change detection and classification (ACDC) system. MIW analysts at the Naval Oceanographic Office, to reduce the amount of time to perform change detection, are currently using ACDC. The dissertation introductory chapter gives background information on change detection, ACDC, and describes how SSI is produced from raw sonar data. Chapter 2 presents the author's Geospatial Bitmap (GB) data structure, which is capable of storing information geographically and is utilized by the three algorithms. This chapter shows that a GB data structure used in a polygon-smoothing algorithm ran between 1.3 – 48.4x faster than a sparse matrix data structure. Chapter 3 describes the GB clustering algorithm, which is the author's repeatable, order-independent method for clustering. Results from tests performed in this chapter show that the time to cluster a set of points is not affected by the distribution or the order of the points. In Chapter 4, the author presents his real-time computer-aided detection (CAD) algorithm that automatically detects mine-like objects on the seafloor in SSI. The author ran his GB-based CAD algorithm on real SSI data, and results of these tests indicate that his real-time CAD algorithm performs comparably to or better than other non-real-time CAD algorithms. The author presents his computer-aided search (CAS) algorithm in Chapter 5. CAS helps MIW analysts locate mine-like features that are geospatially close to previously detected features. A comparison between the CAS and a great circle distance algorithm shows that the CAS performs geospatial searching 1.75x faster on large data sets. Finally, the concluding chapter of this dissertation gives important details on how the completed ACDC system will function, and discusses the author's future research to develop additional algorithms and data structures for ACDC.

Providing unambiguous, succinct descriptions of routes for pedestrians to follow is very challenging. Route descriptions vary according to many things, such as route length and complexity, availability of easily identifiable landmarks, and personal preferences. It is well known that the inclusion of a variety of landmarks facilitates route following – either at key decision points, or as a confirmatory cue. Many of the existing solutions, however, behave like car navigation systems and do not include references to such landmarks. The broader ambition of this research is the automatic generation of route descriptions that cater specifically to the needs of the pedestrian. More specifically this research describes empirical evidence gathered to identify the information requirements for an automated pedestrian navigation system. The results of three experiments helped to identify the criteria that govern the relative saliency of features of interest within an urban environment. There are a large variety of features of interest (together with their descriptions) that can be used as directional aids within route descriptions (for example buildings, statues, monuments, hills, and roads). A set of variables were developed in order to measure the saliency of the different classes of features. The experiments revealed that the most important measures of saliency included name, size, age, and colour. This empirical work formed the basis of the development of a pedestrian navigation system that incorporated the automatic identification of features of interest using the City of Edinburgh as the study area. Additionally the system supported the calculation of the saliency of a feature of interest, the development of an intervisibility model for the route to be navigated to determine the best feature of interest to use at each decision point along the route. Finally, the pedestrian navigation system was evaluated against route descriptions gathered from a random set of individuals to see how efficiently the system reflected the more natural and richer route description that people typically generate. This work shows that modelling features of interest is the key to the automatic generation of route descriptions that can be readily understood and followed by pedestrians.