Narzędzie Lokalizuj regiony identyfikuje najlepsze regiony w rastrze wejściowym, które spełniają określone wymagania dotyczące wielkości oraz ograniczenia przestrzenne. Regiony to grupy przylegających komórek zawierających tę samą wartość. W narzędziu można zdefiniować m.in. następujące wymagania i ograniczenia: łączne pole powierzchni do wybrania, liczba regionów, na które powinno być rozdzielone łączne pole powierzchni, kształt pożądanych regionów oraz minimalne i maksymalne odległości między regionami.
Narzędzie Lokalizuj regiony jest często używane razem z narzędziem Optymalne połączenia regionów w celu wybrania, a następnie połączenia najlepszych dostępnych regionów w najwydajniejszy sposób. Do przeprowadzenia tej analizy potrzebna jest najpierw powierzchnia przydatności, którą można utworzyć za pomocą innych narzędzi w tym zestawie. Następnie należy skorzystać z narzędzia Lokalizuj regiony do zidentyfikowania najlepszych dostępnych regionów. Na koniec użyj opcji Optymalne połączenia regionów, aby określić najmniej kosztowną sieć ścieżek między regionami. Więcej informacji na temat tworzenia modelu przydatności zawiera sekcja Informacje na temat analizy nakładania.
Przykładowe problemy rozwiązywane za pomocą narzędzia Lokalizuj regiony
Wykorzystanie powierzchni utworzonej na podstawie modelu przydatności do identyfikacji najlepszych regionów w następujących przypadkach:
- Najbardziej preferowane siedliska jeleni pod kątem ich ochrony. Potrzebnych jest osiem płatów siedlisk (regionów) do utrzymania żywotnej populacji, a każdy region musi mieć powierzchnię około 50 akrów. Aby wspierać możliwości rozrodu w obrębie stada, regiony powinny znajdować się wystarczająco blisko siebie, aby można je było połączyć korytarzami dla dzikich zwierząt.
- Najlepsze lokalizacje do pozyskiwania drewna. Aby pozyskiwanie drewna było opłacalne, obszary (regiony) muszą mieć powierzchnię co najmniej 250 akrów, a każdy region musi znajdować się w odległości jednej mili od drugiego.
- Idealna lokalizacja dla nowego centrum handlowego. Centrum handlowe wymaga najlepszych 60 akrów, jednak do celów budowlanych obszar musi być przylegający, a kształt placu budowy (regionu) powinien być jak najbardziej zwarty.
Grupowanie komórek w regiony
Istnieje sześć podstawowych sposobów tworzenia regionów z poszczególnych komórek w rastrze przydatności.
- Komórki są grupowane w jednym regionie.
- Komórki są grupowane w określonej liczbie regionów o równym polu powierzchni.
- Komórki są grupowane w określonej liczbie regionów o równym polu powierzchni z uwzględnieniem podanych ograniczeń dotyczących odległości między regionami.
- Komórki są grupowane w określonej liczbie regionów o różnej wielkości kontrolowanej przez wymagania w zakresie minimalnego i maksymalnego pola powierzchni regionów.
- Komórki są grupowane w określonej liczbie regionów o różnej wielkości kontrolowanej przez wymagania w zakresie minimalnego i maksymalnego pola powierzchni regionu, przy czym żadne dwa regiony nie mogą być od siebie oddalone o odległość mniejszą niż minimalna ani większą niż maksymalna.
- W sposób podobny jak w poprzedniej opcji, ale w procesie selekcji trzeba uwzględnić wcześniej istniejące regiony, które zostały już przydzielone w analizowanym obszarze.
Ogólny algorytm narzędzia Lokalizuj regiony
Dane wejściowe narzędzia Lokalizuj regiony są zawarte w rastrze wejściowym, w którym wyższe wartości reprezentują większą użyteczność. Narzędzie wybiera z tego rastra najlepsze regiony, które spełniają podane wymagania dotyczące regionów oraz ograniczenia przestrzenne.
Proces lokalizowania regionów z użyciem tego narzędzia przebiega w czterech etapach. Te cztery główne etapy wraz ze szczegółowym opisem są wymienione poniżej:
- Wyeliminowanie lokalizacji, które są uważane za nieprzydatne w procesie selekcji. Typowymi przykładami takich lokalizacji są zbiorniki wodne, istniejące budynki oraz obszary zbyt strome. Jest to etap przetwarzania wstępnego.
- Zdefiniowanie cech pożądanego regionu lub regionów. Przykładami tych cech są wielkość, kształt oraz orientacja. Ten etap jest realizowany przez skonfigurowanie parametrów w narzędziu.
- Zidentyfikowanie wszystkich regionów kandydujących z rastra wejściowego na podstawie określonego przez użytkownika kompromisu między utrzymaniem kształtu regionu, a maksymalizacją jego użyteczności. Ten etap jest realizowany za pomocą algorytmu wzrostu regionów zaimplementowanego w narzędziu.
- Wybór najlepszego regionu lub regionów spośród regionów kandydujących z użyciem zdefiniowanego przez użytkownika kryterium oceny. Na przykład wybierane są wyłącznie regiony z najwyższą wartością średnią. Ten etap jest realizowany w narzędziu przez zastosowanie algorytmu selekcji z użyciem podanej metody ewaluacji.
W podstawowym algorytmie identyfikowania regionów kandydujących stosowana jest technika sparametryzowanego wzrostu regionów (Parameterized Region-Growing — PRG), która traktuje każdą zidentyfikowaną komórkę jako potencjalne ziarno, z którego wyrasta region. Wybór przylegających komórek, które są dodawane do regionu, jest oparty na ocenie kompromisu między wkładem komórek w utrzymanie pożądanego kształtu regionu a użytecznością (przydatnością) wartości atrybutu w komórkach. Im wyższa wartość atrybutu, tym większa użyteczność. Potencjalne regiony kandydujące rosną do momentu, aż spełnione zostaną wymagania dotyczące powierzchni regionu. Ten proces wzrostu jest wykonywany dla każdego ziarna. Każdy region wynikowy jest uważany za kandydujący, co powoduje, że na tym etapie występuje wiele nakładających się regionów kandydujących. Na tym etapie nie jest przydzielana żadna komórka, a każda komórka może należeć do wielu regionów kandydujących.
W celu wyboru najlepszego regionu lub regionów algorytm selekcji ocenia każdy region kandydujący zidentyfikowany z użyciem techniki PRG pod kątem konfiguracji idealnej na podstawie następujących preferencji:
- Podane kryterium metody ewaluacji, na przykład najwyższa wartość średnia, najwyższa suma lub największa liczba krawędzi.
- Kryterium oceny międzyregionalnej zdefiniowane przez parametry Maksymalna odległość oraz Minimalna odległość.
Gdy pożądany jest wybór wielu regionów, parametr Metoda wyboru daje dodatkową kontrolę nad sposobem wyboru najlepszych regionów. Dostępne są metody COMBINATORIAL i SEQUENTIAL.
- Jeśli wybrana jest metoda COMBINATORIAL, oceniane są wszystkie możliwe kombinacje pożądanej liczby regionów. Jeśli na przykład parametr Liczba regionów jest skonfigurowany na wartość 8, a potencjalna liczba regionów utworzonych z użyciem techniki PRG to 150 000, do zidentyfikowania optymalnych ośmiu regionów na podstawie metody ewaluacji i ograniczeń przestrzennych w metodzie tej testowane są wszystkie kombinacje ośmiu regionów ze 150 000 regionów kandydujących. Istnieje możliwość, że pojedynczy najlepszy region nie zostanie wybrany, jeśli nie jest częścią optymalnej kombinacji ośmiu regionów.
- Jeśli wybrana jest metoda SEQUENTIAL, pierwszym wybranym regionem jest najlepszy region na podstawie metody ewaluacji, który spełnia ograniczenia przestrzenne. Drugim wybranym regionem jest kolejny po pierwszym najlepszy region na podstawie metody ewaluacji spełniający ograniczenia przestrzenne. Proces ten jest kontynuowany, aż liczba regionów jest równa wartości skonfigurowanej w parametrze Liczba regionów.
Regiony kandydujące mogą się nakładać, jednak komórka może być przydzielona tylko do jednego regionu. Gdy region zostanie wybrany, wszystkie pozostałe regiony kandydujące zawierające przydzieloną komórkę przestają być uwzględniane w procesie selekcji kolejnych regionów. Pozostałe komórki w obrębie tych regionów kandydujących wciąż mogą należeć do innych regionów kandydujących.
Rozmieszczanie ziaren
Aby skrócić czas przetwarzania, zamiast analizować wzrost regionów z każdej dostępnej lokalizacji komórki w rastrze wejściowym, można analizować wzrost regionów kandydujących z określonych zidentyfikowanych lokalizacji komórek nazywanych ziarnami. Liczbę ziaren dla wzrostu regionów można kontrolować za pomocą parametru Liczba ziaren wzrostu.
Podana liczba ziaren jest rozmieszczana w rastrze na podstawie rozkładu przestrzennego wartości użyteczności w rastrze wejściowym. Oznacza to, że więcej ziaren znajduje się w obszarach rastra wejściowego, w których wartości użyteczności są najwyższe. Przyjmuje się za bardziej prawdopodobne, że najlepsze regiony będą występować w obszarach, w których wartości użyteczności w rastrze wejściowym są najwyższe.
W celu zidentyfikowania konkretnych lokalizacji ziaren tworzony jest rozkład wszystkich komórek rastra wejściowego i ich wartości użyteczności. Komórki o wysokiej wartości użyteczności obejmują większą część rozkładu. Wartość identyfikująca lokalizację komórki, w której należy umieścić ziarno, jest wybierana losowo z tego rozkładu. Ponieważ komórki o wyższych wartościach użyteczności reprezentują większą część rozkładu, istnieje większe prawdopodobieństwo, że wybierane będą te lokalizacje.
Stosowana jest dodatkowa korekta, która zapewnia, że ziarna nie są zbyt blisko siebie, a rozkład liczby ziaren na danym obszarze jest proporcjonalny do łącznej użyteczności komórek w tym obszarze.
Przykład rozmieszczania ziaren
Dla uproszczenia przyjmijmy, że w rastrze są cztery komórki o wartościach użyteczności równych 1, 2, 3 i 4. Rozkład jest tworzony na podstawie tych czterech wartości. Suma wartości komórek jest równa 10. Wartości są następnie dostosowywane do skali od 0 do 1. Komórka o wartości użyteczności równej 1 wnosi do rozkładu wkład 10-procentowy (od 0 do 0,1 rozkładu), komórka o wartości równej 2 wnosi wkład 20-procentowy (od 0,1 do 0,3 rozkładu), komórka o wartości równej 3 wnosi wkład 30-procentowy (od 0,3 do 0,6 rozkładu), a komórka o wartości równej 4 wnosi wkład 40-procentowy (od 0,6 do 1 rozkładu). Wybierana jest wartość losowa z zakresu od 0 do 1. Istnieje 40-procentowa szansa, że ta wartość losowa przypadnie na zakres rozkładu od 0,6 do 1, co oznaczałoby umieszczenie ziarna w lokalizacji komórki o wartości 4, czyli komórki o najwyższej użyteczności.
Korekta rozdzielczości wzrostu regionu na podstawie wielkości pożądanych regionów
Oprócz użycia parametru Liczba ziaren wzrostu do skrócenia czasu przetwarzania można także poprawić wydajność za pomocą parametru Rozdzielczość wzrostu. Użycie parametru Rozdzielczość wzrostu pozwala zastosować technikę PRG do pośredniej wersji rastra wejściowego o mniejszej rozdzielczości. W tym przypadku po wybraniu pożądanych regionów spośród regionów kandydujących za pomocą rastra pośredniego regiony wynikowe są ponownie próbkowane z użyciem parametru Wielkość komórki w celu wygenerowania ostatecznego rastra wynikowego. Rozdzielczość rastra pośredniego jest określana przez liczbę komórek powiązanych z podaną wartością Rozdzielczość wzrostu.
W celu zapewnienia wystarczającej liczby komórek w każdym wynikowym regionie oraz ograniczenia zbędnego przetwarzania można zastosować drugą korektę do rozdzielczości i łącznej liczby komórek identyfikowanych przez każdą docelową wartość Rozdzielczość wzrostu rastra pośredniego. Na podstawie rozdzielczości określonej z użyciem wartości parametru Rozdzielczość wzrostu identyfikowana jest liczba komórek w regionie o średniej wielkości. Średnia wielkość regionu jest obliczana przez podzielenie pożądanego łącznego pola powierzchni przez podaną liczbę regionów. Aby zapewnić wystarczającą liczbę komórek w każdym wybranym regionie, gdy w regionie średniej wielkości jest zbyt mało komórek, zwiększa się rozdzielczość rastra pośredniego (zmniejsza się wielkość komórki, co powoduje zwiększenie liczby komórek). Aby ograniczyć zbędne przetwarzanie, gdy w regionie średniej wielkości jest zbyt wiele komórek, zmniejsza się rozdzielczość rastra pośredniego.
Progi określające, czy liczba komórek w regionie średniej wielkości jest zbyt mała, czy zbyt duża, są oparte na wybranej wartości parametru Rozdzielczość wzrostu. Jeśli na przykład wybrana jest opcja rozdzielczości LOW, a liczba komórek w regionie średniej wielkości jest zbyt mała, aby uzyskać rozsądne wyniki (w przypadku tej selekcji mniej niż 1800 komórek), rozdzielczość rastra pośredniego zostaje zwiększona tak, aby w regionie o średniej wielkości było co najmniej 1800 komórek. Zapewnia to, że jest dość komórek, aby wygenerować rozsądny region. Z drugiej strony w celu ograniczenia zbędnego przetwarzania, gdy w regionie o średniej wielkości jest więcej niż 5400 komórek, rozdzielczość rastra pośredniego w przypadku wyboru opcji rozdzielczości LOW zostaje zmniejszona tak, aby w regionie średniej wielkości było 5400 komórek.
Te same korekty można zastosować w przypadku wyboru opcji MEDIUM i HIGH w parametrze Rozdzielczość wzrostu, ale uzyskane progi mają inne wartości. W przypadku rozdzielczości MEDIUM dolny próg dla regionu o średniej wielkości to 3200 komórek, a górny limit to 9600 komórek. W przypadku rozdzielczości HIGH dolny próg dla regionu o średniej wielkości to 7200 komórek, a górny limit to 21 600 komórek.
W rezultacie tej drugiej korekty łączna liczba komórek dla pośredniego ponownie próbkowanego rastra, na którym wykonywana jest technika PRG, może być dla każdej podanej wartości parametru Rozdzielczość wzrostu niższa lub wyższa od docelowej liczby komórek.
Sposób określania regionów przy podanym minimalnym i maksymalnym polu powierzchni
Gdy podane są wartości parametrów Minimalne pole powierzchni regionu i Maksymalne pole powierzchni regionu, byłoby zbyt wiele kombinacji regionów do porównania, gdyby dla każdego ziarna sprawdzało się, czy każda możliwa wielkość regionu mieści się między podanymi wielkościami minimalną i maksymalną. Z tego względu dla każdego ziarna algorytm definiuje liczbę regionów o wielkości w zakresie od minimalnej do maksymalnej, które są tworzone przez proces PRG i uwzględniane w procesach selekcji COMBINATORIAL oraz SEQUENTIAL w celu zidentyfikowania najlepszych regionów.
Wszystkie wielkości regionów są generowane na podstawie minimalnej, maksymalnej i średniej wielkości regionu. W celu określenia średniej wielkości regionu algorytm dzieli łączne pole powierzchni przez podaną liczbę regionów. Średnia wielkość regionu to pierwsza wielkość regionu, która będzie generowana z każdego ziarna. Ogólnie rzecz biorąc, średnia wielkość regionu będzie bliżej podanej minimalnej albo maksymalnej wielkości obszaru. Tzn. jest to większa z dwóch odległości: Abs(maksimum – średnia) i Abs(minimum – średnia). Wartość ta jest nazywana LargerDist.
Do obliczenia interwału etapowego stosowanego przy definiowaniu wielkości regionów mieszczących się w zakresie od średniej wielkości regionu do większej odległości używany jest następujący wzór:
StepInterval = LargerDist/(N – 1)- gdzie N jest podaną liczbą regionów.
Począwszy od średniej wielkości regionu, wartość StepInterval jest kolejno dodawana lub odejmowana, aż do osiągnięcia wartości większej odległości. Ta sama wartość StepInterval jest kolejno dodawana lub odejmowana w przeciwnym kierunku, aż do osiągnięcia wartości mniejszej odległości.
Jeśli podczas tego etapu przetwarzania liczba wielkości regionów jest mniejsza niż 4, między poszczególnymi istniejącymi wartościami dodawane są dwie wielkości. Jeśli liczba wielkości jest mniejsza niż 7, ale większa niż 3, między poszczególnymi istniejącymi wartościami dodawana jest jedna wielkość. W rezultacie minimalna liczba wielkości regionów, które są tworzone z każdego ziarna, jest równa 7, a w zależności od podanej liczby regionów maksymalna liczba wielkości regionów może być równa 15.
Poniżej w tej sekcji przedstawiono przykłady ilustrujące użycie tych parametrów.
Gdy podane są wartości parametrów Minimalne pole powierzchni regionu i Maksymalne pole powierzchni regionu, podczas procesu selekcji COMBINATORIAL lub SEQUENTIAL wszystkie wielkości regionu są brane pod uwagę jako region kandydujący dla każdego ziarna i są testowane w celu zidentyfikowania najlepszych regionów.
Jeśli podana jest tylko wartość parametru Minimalne pole powierzchni regionu, a wartość parametru Maksymalne pole powierzchni regionu nie jest określona, maksymalne pole powierzchni jest określane na podstawie minimalnej wielkości pola powierzchni, łącznego pola powierzchni oraz podanej liczby regionów. Na przykład wartość parametru Minimalne pole powierzchni regionu może być skonfigurowana na 5 mil kwadratowych, łączne pole powierzchni na 50 mil kwadratowych, a liczba regionów na 5. Maksymalne możliwe pole powierzchni jest określane przez przyjęcie, że 4 regiony mają wielkość równą minimalnemu polu powierzchni — w tym przykładzie 5 mil kwadratowych — co daje łącznie 20 mil kwadratowych. Pozostaje 30 mil kwadratowych, co jest maksymalnym możliwym polem powierzchni i taka wartość zostanie przypisana. Podobna logika jest stosowana w przypadku, gdy podana jest tylko wartość parametru Maksymalne pole powierzchni regionu, ale minimalne pole powierzchni musi być większe niż 0.
Przykład 1
W tym przykładzie skonfigurowane są wartości następujących parametrów:
- Łączne pole powierzchni jest skonfigurowane na 300 mil kwadratowych
- Liczba regionów jest skonfigurowana na 6
- Minimalne pole powierzchni regionu jest skonfigurowane na 40 mil kwadratowych
- Maksymalne pole powierzchni regionu jest skonfigurowane na 100 mil kwadratowych
Pierwszą wielkością regionu, która zostanie utworzona przez technikę PRG, jest średnia wielkość regionu, która jest wyliczana przez podzielenie łącznego pola powierzchni przez liczbę regionów: 50 mil kwadratowych (300/6). Wartość parametru LargerDist jest równa 50 (LargerDist = Abs(100 – 50)). Wartość parametru StepInterval jest równa 10 (StepInterval = 50/(6 – 1)).
Druga wielkość regionu do utworzenia z każdego ziarna jest wyliczana przez dodanie wartości StepInterval do średniej wielkości regionu (10 + 50), co daje 60 mil kwadratowych. Proces ten jest kontynuowany przez dodawanie wartości StepInterval równej 10 do średniej wielkości regionu, aż osiągnięta zostanie wartość większej odległości. Prowadzi to do identyfikacji trzeciej, czwartej, piątej i szóstej wielkości regionu równych odpowiednio 70, 80, 90 i 100 mil kwadratowych. Na koniec wartość StepInterval jest iteracyjnie odejmowana od średniej wielkości regionu, aż do osiągnięcia wartości mniejszej odległości, co daje siódmą wielkość regionu do utworzenia, w tym przypadku 40 mil kwadratowych. W tym przykładzie liczba regionów, które zostaną utworzone z każdego ziarna, jest równa 7. Ich wielkości są równe 40, 50, 60, 70, 80, 90 i 100 mil kwadratowych.
Przykład 2
W tym przykładzie skonfigurowane są wartości następujących parametrów:
- Łączne pole powierzchni jest skonfigurowane na 100 mil kwadratowych
- Liczba regionów jest skonfigurowana na 4
- Minimalne pole powierzchni regionu jest skonfigurowane na 10 mil kwadratowych
- Maksymalne pole powierzchni regionu jest skonfigurowane na 60 mil kwadratowych
Pierwszą wielkością regionu, która zostanie utworzona przez technikę PRG, jest średnia wielkość regionu, która jest wyliczana przez podzielenie łącznego pola powierzchni przez liczbę regionów: 25 mil kwadratowych.
Wartość LargerDist jest równa 35 mil kwadratowych (Abs(60 – 25)). Wartość StepInterval jest równa 11,6667 (35/(4 – 1)). Iteracyjne dodawanie wartości 11,6667 do średniej wielkości regionu, aż do osiągnięcia wartości większej odległości, daje w wyniku wartości równe 36,6667, 48,3334 i 60. Odejmowanie wartości StepInterval od średniej wielkości regionu, aż do uzyskania różnicy równej wartości minimalnej lub od niej mniejszej, daje w wyniku wartość równą 13,3333. Jak dotąd liczba wielkości regionów jest równa 5. Wartości te to 13,3333, 25, 36,6667, 48,3334 i 60. Należy zwrócić uwagę, że wartość minimalna lub maksymalna prowadząca do uzyskania mniejszej odległości nie musi być jedną z wielkości regionu (w tym przykładzie 13,3333 – 11,6667 = 1,6666, czyli wartość mniejsza niż 10). Ponownie minimalna liczba wielkości regionów, które są tworzone z każdego ziarna, jest równa 7, a maksymalna liczba wielkości regionów jest równa 15. Ponieważ wartość 5 jest mniejsza niż wymagane minimum równe 7, między poszczególnymi 5 wielkościami regionów wstawiane są dodatkowe. W tym przykładzie liczba regionów, które zostaną utworzone z każdego ziarna, jest równa 9. Ich wielkości są równe 13,3333, 19,1667, 25, 30,8334, 36,6667, 42,5001, 48,3334, 54,1667 i 60 mil kwadratowych.
Odniesienia
Brooks, Christopher J. 1997. A parameterized region growing programme for site allocation on raster suitability maps. International Journal of Geographic Information Science, 11:4, 375–396.
Brooks, Christopher J. 1997. A genetic algorithm for location optimal sites on raster suitability maps. Transactions in GIS, tom 2, nr 3, str. 201–212.
Brooks, Christopher J. 1998. A genetic algorithm for designing optimal region configurations in GIS. Praca doktorska, University College, Uniwersytet Londyński, Londyn.
Brooks, Christopher J. 2001. A genetic algorithm for designing optimal patch configurations in GIS. International Journal of Geographic Information Science, tom 15, nr 6, 539–559.
Li, Xia i Anthony Gar-On Yeh, 2005. Integration of genetic algorithms and GIS for optimal location search, International Journal of Geographic Information Science, tom 19, nr 5, 581–601.