Given a grid of cells, each of which is assigned a numerical value quantifying its suitability for a certain use, one problem in geographic information science concerns the selection of a region, i.e. a connected set of cells, with a specified size that maximizes the sum of all their values. This task can be cast as a combinatorial optimization problem called the maximum value region problem, and exact and heuristic methods exist for its solution. While those solutions are guaranteed to be feasible (if not optimal), they may not be desirable for practical use if they contain too narrow segments (down to the width of a single cell). In this paper, we present a new variation of the maximum value region problem—the maximum value wide region problem—that requires a region to be at least as wide as a specified width. We offer a heuristic method for its solution which models a region as a set of neighborhoods and test its performance through computational experiments. Results demonstrate that the method generates good feasible solutions in terms of connectedness, size, width, and value, but requires more computing time than methods for maximum value regions without minimum width requirements.

The least-cost path problem is a widely studied problems in geographic information science. In raster space, the problem is to find a path that accumulates the least amount of cost between two locations based on the assumptions that the path is a one-dimensional object (represented by a string of cells) and that the cost (per unit length) is measured on a quantitative scale. Efficient methods are available for solution of this problem when at least one of these assumptions is upheld. This is not the case when the path has a width and is a two-dimensional object called a corridor (represented by a swath of cells) and the cost (per unit area) is measured on an ordinal scale. In this paper, we propose one additional model that characterizes a least-cost corridor on an ordinal-scaled raster cost surface–or a least ordinal-scaled cost corridor for short–and show that it can be transformed into an instance of a multiobjective optimization problem known as the preferred path problem with a lexicographic preference relation and solved accordingly. The model is tested through computational experiments with artificial landscape data as well as real-world data. Results show that least ordinal-scaled cost corridors are guaranteed to contain smaller areas of higher cost than conventional least-cost corridors at the expense of more elongated and winding forms. The least ordinal-scaled cost corridor problem has computational complexity of O(n 2.5) in the worst case, resulting in a longer computational time than least-cost corridors. However, this difference is smaller in practice.

Optimal routing of a path with a constant width in a two-dimensional grid of cost-weighted square cells or pixels is a recent extension of the least-cost path problem, and models and solutions are available and ready to be integrated into raster-based geographic information systems. In this article we consider yet another variation of this problem in a three-dimensional grid of cost-weighted cubic cells or voxels, which is to find a tubular region of voxels with a constant width, referred to here as “corridor,” connecting two termini while accumulating the least amount of cost. We model a corridor as a sequence of sets of voxels, called “neighborhoods,” that are arranged in a 26-hedral form, design a heuristic method to find a sequence of such neighborhoods that sweeps the minimum cost-weighted volume, and test its performance with computer-generated random data. Results show that the method finds a low-cost, if not least-cost, corridor with a specified width in a three-dimensional cost grid and has a reasonable efficiency as its complexity is O(n2), where n is the number of voxels in the input cost grid and is independent of corridor width. A major drawback is that the corridor found may self-intersect, which often not only is an undesirable quality but also makes the estimation of its cost-weighted volume inaccurate.

Given a grid of cells, each of which is assigned a numerical value quantifying its utility (or cost) for a certain use, a popular type of problem in geographic information science is raster-based spatial optimization. Such problems commonly seek to find a set of cells that maximizes (or minimizes) that utility (or cost) while adhering to a given set of constraints. If the problem concerns the selection of a region, i.e., a connected set of cells, it is particularly useful in a range of planning fields that rely on geographic information science. With the increasing availability of high-resolution data on the Earth’s surface, it may no longer be sufficient to exclusively model such raster-based optimization problems on a cell-by-cell basis. Instead, the explicit consideration of width and subsequent modeling of spatial optimization problems may be considered.

The overall objective of this thesis is to integrate the “neighborhood” approach to modeling for width in raster grids into pertinent spatial optimization problems. The studies presented in this thesis focus on two common raster-based spatial optimization problems, the maximum value region problem and the least-cost path problem. Each study then models variations of those problems which incorporate a width larger than a cell, and designs, implements, and tests solution methods as follows. 

The raster-based maximum value region problem involves the selection a region with a specified size that maximizes (or minimizes) the sum of all their values. This task can be cast as a combinatorial optimization problem, and exact and heuristic methods exist for its solution. While solutions generated by these methods are guaranteed to be feasible (if not optimal), they may not be desirable for practical use if they contain too narrow segments (which can be as narrow as the width of a single cell). A new variation of the maximum value region problem—referred to here as the maximum value wide region problem—is presented that requires a region to be at least as wide as a specified width. A heuristic method for its solution is introduced and its performance is tested through computational experiments with randomly generated artificial landscape data. Results demonstrate that the method generates good feasible solutions in terms of all of connectedness, size, width, and value, but requires more computing time—which, in theory, grows linearly with grid size and quadratically with region size and region width—than other methods for maximum value regions without a minimum width requirement.

The raster-based least-cost path problem involves the selection of a region that connects two specified cells, a source and destination, and that minimizes the sum of all their values. It is one of the most widely studied problems in geographic information science, and itself is a variation of the optimal routing problem. In relation to width, optimal routing of a path with a constant width, i.e., a corridor, in a two-dimensional (2D) grid of cost-weighted square cells is a recent extension of the least-cost path problem, and models and solutions are available and ready to be integrated into raster-based geographic information systems (GIS). However, these solutions are reliant on the cost surface on which they are modeled, which have limitations in certain situations, including 1) a reliance on the assumption that the cost (per unit length) is measured on a quantitative scale, 2) a measured distortion when the cost-surface is constant, and 3) they are limited to optimal routing of paths in 2D.

In relation to the first limitation, one additional model is proposed that characterizes a least-cost corridor on an ordinal-scaled raster cost surface—or a least ordinal-scaled cost corridor for short—and shows that it can be transformed into an instance of a multiobjective optimization problem known as the preferred path problem with a lexicographic preference relation and solved accordingly. The model is tested through computational experiments with randomly generated artificial landscape data as well as real-world data. Results show that least ordinal-scaled cost corridors are guaranteed to contain smaller areas of higher cost than conventional least-cost corridors at the expense of more elongated and winding forms. The least ordinal-scaled cost corridor problem has a computational complexity of O(n2.5) in the worst case, resulting in a longer computational time than least-cost corridors. However, this difference is smaller in practice.

In relation to the second limitation, as is the case with conventional raster-based least-cost paths, the incremental orientations are limited to a fixed number of (typically eight cardinal) directions, and therefore, regardless of the grid resolution, least-cost corridors tend to deviate from those conceivable on the Euclidean plane. A method is proposed for solving the raster-based least-cost corridor problem with reduced distortion by adapting a distortion reduction technique originally designed for least-cost paths and applying it to an efficient but distortion-prone least-cost corridor algorithm. The proposed method is, in theory, guaranteed to generate no less accurate solutions than the existing one in polynomial time and, in practice, expected to generate more accurate solutions, as demonstrated experimentally using synthetic and real-world data.

In relation to the 2D limitation, with the increased availability of 3D data, one could consider yet another spatial optimization problem in a three-dimensional grid of cost-weighted cubic cells or voxels, which is to find a tubular region of voxels with a constant width, referred to here as “3D corridor,” connecting two termini while accumulating the least amount of cost. A 3D corridor is modeled as a sequence of sets of voxels, called “neighborhoods,” that are arranged in a 26-hedral form, a heuristic method is designed to find a sequence of such neighborhoods that sweeps the minimum cost-weighted volume, and its performance is tested with computer-generated random data. Results show that the method finds a low-cost, if not least-cost, corridor with a specified width in a three-dimensional cost grid and has a reasonable efficiency as its complexity is O(n2) where n is the number of voxels in the input cost grid and is independent of corridor width. A major drawback is that the corridor found may self-intersect, which is often not only an undesirable quality but makes the estimation of its cost-weighted volume inaccurate.

Med tanke på ett rutnät av celler, som var och en tilldelas ett numeriskt värde som kvantifierar dess användbarhet (eller kostnad) för en viss användning, är en populär typ av problem inom geografisk informationsvetenskap (GIS) rasterbaserad rumslig optimering. Sådana problem försöker vanligtvis hitta en uppsättning celler som maximerar (eller minimerar) den nyttan (eller kostnaden) samtidigt som de följer en given uppsättning begränsningar. Om problemet gäller valet av en region, d.v.s. en ansluten uppsättning celler, är det särskilt användbart i en rad planeringsfält som förlitar sig på GIS. Med den ökande tillgängligheten av högupplösta data på jordens yta kanske det inte längre är tillräckligt att uteslutande modellera sådana rasterbaserade optimeringsproblem på cell-för-cell-basis. Istället kan det explicita övervägandet av bredd och efterföljande modellering av rumsliga optimeringsproblem övervägas.

Det övergripande syftet med denna avhandling är att integrera "grannskaps"-metoden för modellering för bredd i rasternät i relevanta rumsliga optimeringsproblem. Studierna som presenteras i denna avhandling fokuserar på två vanliga rasterbaserade rumsliga optimeringsproblem, maximivärdesregionproblemet och minstakostnadsvägproblemet. Varje studie modellerar sedan varianter av de problem som innehåller en bredd som är större än en cell, och designar, implementerar och testar lösningsmetoder enligt följande.

Det rasterbaserade maximivärdesregionproblemet involverar valet av en ansluten uppsättning celler, d.v.s. en region, med en specificerad storlek som maximerar (eller minimerar) summan av alla deras värden. Denna uppgift kan gjutas som ett kombinatoriskt optimeringsproblem, och det finns exakta och heuristiska metoder för att lösa det. Även om lösningar som genereras av dessa metoder garanterat är genomförbara (om de inte är optimala), kanske de inte är önskvärda för praktisk användning om de innehåller för smala segment (som kan vara lika smala som bredden på en enda cell). En ny variant av maximivärdesregionproblemet – här kallat maximivärdesbredregionproblemet – presenteras som kräver att en region är minst lika bred som en specificerad bredd. En heuristisk metod för dess lösning introduceras och dess prestanda testas genom beräkningsexperiment med slumpmässigt genererade artificiella landskapsdata. Resultaten visar att metoden genererar bra genomförbara lösningar när det gäller all koppling, storlek, bredd och värde, men kräver mer beräkningstid - som i teorin växer linjärt med rutnätsstorleken och kvadratiskt med regionstorlek och regionbredd - än andra metoder för regioner med maximalt värde utan krav på minsta bredd.

Det rasterbaserade minsta kostnadsvägproblemet involverar valet av en region som förbinder två specificerade celler, en källa och destination, och som minimerar summan av alla deras värden. Det är ett av de mest studerade problemen i GIS, och i sig är det en variant av det optimala routingproblemet. I förhållande till bredd är optimal routing av en bana med konstant bredd, det vill säga en korridor, i ett tvådimensionellt (2D) rutnät av kostnadsviktade kvadratceller en ny förlängning av problemet med minsta kostnadsväg, och modeller och lösningar är tillgängliga och redo att integreras i rasterbaserade geografiska informationssystem. Dessa lösningar är dock beroende av kostnadsytan som de är modellerade på, vilket har begränsningar i vissa situationer, inklusive 1) ett beroende av antagandet att kostnaden (per längdenhet) mäts på en kvantitativ skala, 2) en uppmätt distorsion när kostnadsytan är konstant, och 3) de är begränsade till optimal routing av vägar i 2D.

I förhållande till den första begränsningen föreslås ytterligare en modell som kännetecknar en lägsta kostnadskorridor på en ordinärt skalad rasterkostnadsyta – eller kort och gott en minst ordinärt skalad kostnadskorridor – och visar att den kan omvandlas till en instans av ett multiobjektivt optimeringsproblem känt som det föredragna vägproblemet med en lexikografisk preferensrelation och löst i enlighet därmed. Modellen testas genom beräkningsexperiment med slumpmässigt genererade artificiella landskapsdata såväl som verkliga data. Resultaten visar att kostnadskorridorer med minst ordinär skala garanterat innehåller mindre ytor med högre kostnad än konventionella minsta kostnadskorridorer på bekostnad av mer långsträckta och slingrande former. Det minst ordinala kostnadskorridorproblemet har en beräkningskomplexitet på O(n2.5) i värsta fall, vilket resulterar i en längre beräkningstid än lägsta kostnadskorridorer. Denna skillnad är dock mindre i praktiken.

I förhållande till den andra begränsningen, som är fallet med konventionella rasterbaserade lägsta kostnadsvägar, är de inkrementella orienteringarna begränsade till ett fast antal (typiskt åtta kardinal) riktningar, och därför, oavsett nätupplösning, lägsta kostnad korridorer tenderar att avvika från de tänkbara på det euklidiska planet. En metod föreslås för att lösa det rasterbaserade lägsta kostnadskorridorproblemet med reducerad distorsion genom att anpassa en distorsionsreduktionsteknik som ursprungligen utformades för lägsta kostnadsvägar och tillämpa den på en effektiv men distorsionsbenägen lägstakostnadskorridoralgoritm. Den föreslagna metoden är, i teorin, garanterad att generera inte mindre exakta lösningar än den befintliga i polynomtid och förväntas i praktiken generera mer exakta lösningar, vilket demonstrerats experimentellt med hjälp av syntetiska och verkliga data.

I förhållande till 2D-begränsningen, med den ökade tillgängligheten av 3D-data, skulle man kunna överväga ytterligare ett rumsligt optimeringsproblem i ett tredimensionellt rutnät av kostnadsviktade kubiska celler eller voxels, vilket är att hitta ett rörformigt område av voxlar med en konstant bredd, här kallad "3D-korridor", som förbinder två terminaler samtidigt som den ackumulerar minsta kostnad. En 3D-korridor är modellerad som en sekvens av uppsättningar av voxlar, kallade "kvarter", som är arrangerade i en 26-hedrisk form, en heuristisk metod är utformad för att hitta en sekvens av sådana stadsdelar som sveper den minsta kostnadsviktade volymen, och dess prestanda testas med datorgenererade slumpmässiga data. Resultat visar att metoden hittar en lågkostnads, om inte minst kostnadseffektiv, korridor med en specificerad bredd i ett tredimensionellt kostnadsnät och har en rimlig effektivitet då dess komplexitet är O(n2) där n är antalet voxlar i insatskostnadsnätet och är oberoende av korridorbredden. En stor nackdel är att korridoren som hittas kan skära sig själv, vilket ofta inte bara är en oönskad kvalitet utan gör uppskattningen av dess kostnadsviktade volym inexakt.

Given a grid of cells, each having a value indicating its cost per unit area, a variant of the least-cost path problem is to find a corridor of a specified width connecting two termini such that its cost-weighted area is minimized. A computationally efficient method exists for finding such corridors, but as is the case with conventional raster-based least-cost paths, their incremental orientations are limited to a fixed number of (typically eight orthogonal and diagonal) directions, and therefore, regardless of the grid resolution, they tend to deviate from those conceivable on the Euclidean plane. In this paper, we propose a method for solving the raster-based least-cost corridor problem with reduced distortion by adapting a distortion reduction technique originally designed for least-cost paths and applying it to an efficient but distortion-prone least-cost corridor algorithm. The proposed method is, in theory, guaranteed to generate no less accurate solutions than the existing one in polynomial time and, in practice, expected to generate more accurate solutions, as demonstrated experimentally using synthetic and real-world data.

Mixture tuned matched filtering (MTMF) image classification capitalizes on the increasing spectral and spatial resolutions of available hyperspectral image data to identify the presence, and potentially the abundance, of a given cover type or endmember. Previous studies using MTMF have relied on extensive user input to obtain a reliable classification. In this study, we expand the traditional MTMF classification by using a selection of supervised learning algorithms with rigorous cross-validation. Our approach removes the need for subjective user input to finalize the classification, ultimately enhancing replicability and reliability of the results. We illustrate this approach with an MTMF classification case study focused on leafy spurge (Euphorbia esula), an invasive forb in Western North America, using free 30-m hyperspectral data from the National Aeronautics and Space Administration's (NASA) Hyperion sensor. Our protocol shows for our data, a potential overall accuracy inflation between 18.4% and 30.8% without cross-validation and according to the supervised learning algorithm used. We propose this new protocol as a final step for the MTMF classification algorithm and suggest future researchers report a greater suite of accuracy statistics to affirm their classifications' underlying efficacies.