Способ и система для хранения и быстрого извлечения высотных отметок цифровых моделей местности для использования в системах определения местоположения

Изобретение относится к области цифровых моделей рельефа, в частности к формированию и осуществлению доступа к высотным отметкам для Цифровых моделей рельефа. Технический результат, заключающийся в эффективном хранении данных о высотных отметках, достигается за счет выполнения сжатия данных о высотных отметках из первой порции Цифровой модели рельефа (DEM), чтобы сформировать первые сжатые данные высотных отметок; сохранении первых сжатых данных высотных отметок в ячейке запоминающего устройства, указываемой первым индексом; и сохранении первого индекса. При чтении сжатых данных о модели рельефа выполняют этапы: определение местоположения первой сжатой порции Цифровой модели рельефа с использованием первого индекса; развертывание первой сжатой порции, чтобы извлечь первые данные о высотных отметках для одной точки дискреты в Цифровой модели рельефа. Цифровая модель рельефа имеет множество сжатых порций, которое включает первую сжатую порцию и первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция. 6 н. и 15 з.п. ф-лы, 16 ил.

 

Изобретение относится к комбинированным системам определения местоположения с помощью беспроводной связи, и более конкретно к хранению и извлечению (поиску) отметок превышения рельефа, или высотных отметок, в цифровых моделях рельефа местности.

Для выполнения определения местоположения в беспроводных сетях сотовой связи (например, сеть сотовой телефонной связи) в некоторых подходах выполняют триангуляцию, основанную на использовании информации об измерениях времени, которую посылают между каждой из нескольких базовых станций и подвижным мобильным устройством, таким как сотовый телефон. Один подход, имеющий название Расширенная трилатерация (трехстороннее измерение) по прямой линии связи (РТПЛС) или Усовершенствованная фиксация разности времен (прихода сигналов) (EOTD), измеряет на подвижном устройстве времена прихода сигналов, переданных от каждой из нескольких базовых станций. Эти значения времен передают на сетевой Элемент (ЭОМ) определения местоположения абонента (например, на сервер определения местоположения, или сервер местоположения), который вычисляет местоположения подвижного устройства, используя эти времена приема. Истинные времена («времена-дня») на этих базовых станциях скоординированы так, что в конкретный момент времени истинные времена, связанные со множественными базовыми станциями, находятся в пределах заданной ошибки (погрешности). Точные местоположения базовых станций и времена приема используют для определения местоположения подвижного устройства.

На фиг. 1 показан пример системы РТПЛС, в которой времена (TR1, TR2, и TR3) приема сигналов от базовых станций 101, 103, 105 сотовой связи измеряют на мобильном сотовом телефоне 111. Эти данные об измерении времени затем могут быть использованы, чтобы вычислить местоположение подвижного устройства. Такое вычисление может быть сделано непосредственно на подвижном устройстве, или на сервере местоположения, если информацию об измерении времени, полученную таким образом подвижным устройством, передают на сервер местоположения посредством линии связи. Обычно времена приемов передают на сервер 115 местоположения через одну из базовых станций сотовой связи (например, базовую станцию 101, или 103, или 105). Сервер 115 местоположения соединяют для приема данных от базовых станций посредством центра 113 коммутации мобильной связи. Центр 113 коммутации мобильной связи обеспечивает сигналы (например, передачу речевых сообщений) на Коммутируемую телефонную систему (PSTS) общего пользования наземной линии связи и от PSTS, так что сигналы могут быть переданы на мобильный телефон и от мобильного телефона на другие телефоны (например, телефоны наземной линии связи в PSTS или другие подвижные телефоны). В некоторых случаях сервер местоположения может также обмениваться информацией с центром коммутации подвижной связи через линию сотовой связи. Сервер местоположения может также управлять распространением сигналов от нескольких из базовых станций при определении относительного времени распространения этих сигналов.

В другом подходе, который назван Разность моментов времени прихода сигналов (TDOA), времена приема сигнала от подвижного устройства измеряют на нескольких базовых станциях. Фиг. 1 применима к такому случаю, если направления стрелок TR1, TR2 и TR3 изменены на противоположные. Такие данные об измерении времени затем могут быть переданы на сервер местоположения, чтобы вычислить местоположение подвижного устройства.

Следующий, третий, способ определения местоположения включает в себя использование в подвижном устройстве приемника, предназначенного для Глобальной спутниковой системы (GPS) США определения местоположения абонента сотовой связи или другой Спутниковой системы (ССОМ) определения местоположения, такой как российская (Глобальная навигационная спутниковая) система GLONASS и предложенная Европейским Союзом система Galileo, или комбинации спутников и станций-псевдоспутников. Станции-псевдоспутники являются наземными передатчиками, которые передают PN-код (псевдошумовой, ПШ) (подобный сигналу GPS), модулируемый на сигнале с несущей на полосе сверхвысоких частот, обычно синхронизируемом со временем ССОМ. Каждому передатчику может быть назначен уникальный PN-код, чтобы допустить идентификацию удаленным приемником. Станции-псевдоспутники являются полезными в ситуациях, в которых сигналы ССОМ от орбитального спутника могут быть недоступными, например в туннелях, шахтах, зданиях или других замкнутых пространствах. Термин "спутник", используемый в описании, подразумевает станцию-псевдоспутник или эквиваленты станций-псевдоспутников, и термин «GPS-сигналы», используемый в описании, подразумевает сигналы, подобные сигналам GPS, от станциий-псевдоспутников или эквивалентов станций-псевдоспутников. Такой способ, использующий приемник для ССОМ-сигналов, может быть полностью автономным или может использовать сеть сотовой связи для обеспечения вспомогательных (для помощи в установлении соединения) данных, или для совместного использования в вычислении местоположения. Примеры такого способа описаны в патентах США № 5841396; № 5945944; и № 5812087. Для краткости также способы здесь названы как способы "ССОМ". В практических недорогих вариантах осуществления и приемник сети подвижной сотовой связи, и ССОМ-приемник объединены в один конструктивный блок (корпус) и могут фактически совместно использовать общую электронную схему.

Комбинацию из либо РТПЛС, либо TDOA с системой ССОМ называют "комбинированной" системой.

В следующем способе определяют двустороннюю временную задержку (ДВЗ) для сигналов, которые посылают с базовой станции на подвижное устройство и затем возвращают. В подобном, но альтернативном, способе определяют двустороннюю временную задержку для сигналов, которые посылают от подвижного устройства на базовую станцию и затем возвращают. Каждую из этих двусторонних временных задержек делят на два, чтобы определить оценку односторонней временной задержки. Знание местоположения базовой станции, включая одностороннюю задержку, ограничивает местоположение подвижного устройства окружностью на поверхности Земли. Два таких измерения имеют затем результатом пересечение двух окружностей, которое в свою очередь ограничивает местоположение двумя точками на поверхности Земли. Третье измерение (даже угол прихода или сектор сотовой ячейки) разрешает неоднозначность.

Поддержку измерения высоты, или высотную поддержку, использовали в различных способах, предназначенных для определения местоположения подвижного устройства. Высотная поддержка обычно основана на псевдоизмерении высоты. Знание высоты для местоположения подвижного устройства ограничивает возможные местоположения подвижного устройства поверхностью сферы (или эллипсоида) с центром, помещенным в центр Земли. Такое знание может быть использовано, чтобы уменьшить количество независимых измерений, требуемых для определения местоположения подвижного устройства. Обычно оценка высоты может быть вручную подана оператором подвижного устройства, или может быть установлена на значение высоты из предыдущего трехмерного решения, или может быть установлена на заранее установленное значение, или может быть получена из картографической информации, такой как база топографических или геодезических данных, поддерживаемая на сервере местоположения.

В патенте США № 6061018, который включен в настоящее описание в качестве ссылки, описан способ, в котором оценку высоты определяют на основании информации объекта сотовой связи, который может быть узлом сотовой связи, имеющим передатчик при обмене информацией с подвижным устройством. В патенте США № 6061018 также описан способ определения условия измерений псевдодальностей от множества спутников ССОМ посредством сравнения высоты, вычисленной на основании измерений псевдодальности, с оценкой высоты.

Иногда таблицу данных о высоте, имеющих более низкое разрешение, сохраняют в оперативном запоминающем устройстве. Обычно картографическую информацию с высоким разрешением, такую как топографическая или геодезическая базы данных, сохраняют в одном или нескольких однородных, или плоских, файлах (неиндексированных) на сервере местоположения. Например, глобальная Цифровая модель рельефа (DEM), имеющая шаг сетки по горизонтали, соответствующий дуге в 30 секунд (приблизительно 1 километр), может быть получена из Геологической службы США в комплекте из пяти компакт-дисков КД-ПЗУ (CD-ROM). Файл DEM из Геологической службы США (http://edcdaac.usgs.gov/) поставляют в виде 16-битовых целых чисел со знаком в простом общем двоичном растровом формате. В данные изображения вложены ограниченный заголовок и иногда заключительные байты. Данные сохраняют в сквозном порядке строк (все данные для строки 1, за которыми следуют все данные для строки 2, и т.д.).

Иногда на Цифровую модель рельефа (DEM) также ссылаются, как на Цифровую модель (ЦММ) местности (земной поверхности).

Настоящее описание раскрывает способы и устройства для формирования сжатых и индексированных высотных отметок и осуществления доступа к сжатым и индексированным высотным отметкам Цифровых моделей рельефа.

В одном аспекте настоящего изобретения способ хранения данных о высотных отметках включает в себя: сжатие данных высотных отметок из первой (начальной) порции Цифровой модели рельефа (DEM), чтобы сформировать первые (начальные) сжатые данные высотных отметок; сохранение первых сжатых данных высотных отметок в ячейке запоминающего устройства, на которую указывает первый индекс; и сохранение первого индекса. В одном примере, соответствующем этому аспекту, данные высотных отметок из первой порции являются сжатыми посредством: вычитания опорной высоты из данных высотных отметок первой порции Цифровой модели рельефа (DEM), чтобы сформировать нормированные данные высотных отметок; масштабирование нормированных данных высотных отметок, чтобы сформировать масштабированные данные высотных отметок; и групповое кодирование (длины серий) масштабированных данных высотных отметок, чтобы сформировать первые сжатые данные высотных отметок. В одном примере параметры, требуемые для определения, находится или не находится местоположение в первой порции Цифровой модели рельефа, а также данные преобразования, задающие систему координат, используемую для представления данных высотных отметок из первой порции Цифровой модели рельефа, являются также сохраняемыми. В одном примере Цифровая модель рельефа разделена на множество областей; область Цифровой модели рельефа разделена на множество элементов «мозаичного» представления модели, или элементов модели, и профили в каждом из множества элементов модели, находящихся в области Цифровой модели рельефа, являются индивидуально сжатыми. Параметры, требуемые для определения, находится или не находится местоположение в одном из множества элементов модели, а также параметры, требуемые для определения, находится или не находится местоположение в одном из множества областей, являются также сохраняемыми.

В другом аспекте настоящего изобретения способ извлечения данных высотных отметок включает в себя: определение местоположения первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс; и развертывание сжатых данных первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты представления модели в Цифровой модели рельефа. Цифровая модель рельефа имеет множество сжатых порций, которое включает в себя первую сжатую порцию, и первый индекс, указывающий ячейку запоминающего устройства, в которой сохраняют первую сжатую порцию.

В одном примере в соответствии с этим аспектом развертывание первой сжатой порции осуществляют посредством: группового декодирования первой сжатой порции, чтобы сформировать масштабированные данные высотных отметок; обратного масштабирования масштабированных данных высотных отметок, чтобы сформировать нормированные данные высотных отметок; и сложения опорной высоты с нормированными данными высотных отметок, чтобы сформировать первые данные высотных отметок. В одном примере множество сжатых порций сохраняют в одном из: a) в файле, отображенном на память (MMF); b) оперативном запоминающем устройстве (ОЗУ, RAM); и c) в файле файловой системы в системе цифровой обработки; и множество сжатых порций являются порциями сжатых профилей в элементе модели Цифровой модели рельефа.

В одном примере, чтобы вычислить высотную отметку местоположения, идентифицируют область в множестве областей Цифровой модели рельефа; из множества элементов модели, находящихся в области, идентифицируют элемент модели, который содержит местоположение; идентифицируют профиль, который находится вблизи, или в окрестности, местоположения; и осуществляют развертывание по меньшей мере порции профиля, чтобы извлечь данные высотных отметок по меньшей мере для одной точки дискреты. Идентифицируют множество точек дискрет вблизи местоположения. После того как высотные отметки для множества точек дискрет извлечены из Цифровой модели рельефа, высотную отметку местоположения вычисляют на основании интерполяции, используя высотные отметки множества точек дискрет. Выполняют преобразование координат, чтобы позицию местоположения в горизонтальной плоскости выразить в системе координат, используемой Цифровой моделью рельефа. В вычислении высотной отметки местоположения выполняют преобразование координат так, чтобы высотная отметка местоположения была выражена в системе координат, используемой Элементом определения местоположения. Высотную отметку местоположения подают на Элемент определения местоположения, чтобы выполнить высотную поддержку в системе определения местоположения. В одном сценарии высотную отметку поставляют в реальном времени в ответ на запрос от Элемента определения местоположения; и высотную отметку поставляют, чтобы наполнить информацию для данных справочника базовой станции, которые в другом сценарии впоследствии используются Элементом определения местоположения для высотной поддержки.

Настоящее изобретение включает в себя устройства для осуществления этих способов, содержащие системы обработки данных, которые выполняют эти способы, и машиночитаемые носители, которые обеспечивают системам обработки данных выполнять эти способы.

Другие признаки настоящего изобретения будут очевидны из сопроводительных чертежей и из подробного описания, которые следуют ниже.

Настоящее изобретение проиллюстрировано посредством примера, а не ограничения, на сопроводительных чертежах, на которых одними и теми же ссылочными позициями обозначены сходные элементы.

Фиг. 1 - пример относящейся к предшествующему уровню техники сети сотовой связи, которая определяет местоположение подвижного устройства сотовой связи.

Фиг. 2 - пример сервера местоположения, который может быть использован с настоящим изобретением.

Фиг. 3 - способ использования Базы данных рельефа местности (БДРМ) для обеспечения информации о высотных точках местности, или информации о высотах, в реальном времени в течение навигационной обработки в Элементе (ЭОМ) определения местоположения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 4 - способ наполнения информации о высотах для справочника данных базовой станции, информация из которого может быть использована в течение навигационной обработки в Элементе (ЭОМ) определения местоположения для высотной поддержки, в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 5 - способ формирования Цифровых моделей рельефа в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 6 - примерная схема нумерации элементов модели в области.

Фиг. 7 - пример профиля данных высотных отметок местности.

Фиг. 8 - способ определения высотных отметок местности для местоположения на основании Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 9 - Обслуживающая подсистема поддержки высотных отметок в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 10 - представление данных элемента Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 11 - представление данных заголовка, предназначенного для сохранения порции Цифровой модели (DEM) рельефа, в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 12 - схема группового кодирования, которая может быть использована с настоящим изобретением.

Фиг. 13 - пример кодирования порции Цифровой модели (DEM) рельефа для хранения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 14 - способ кодирования порции Цифровой модели рельефа (DEM) для хранения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 15 - способ вычисления высотной отметки местоположения в соответствии с одним вариантом осуществления настоящего изобретения.

Фиг. 16 - один способ извлечения и декодирования порции Цифровой модели (DEM) рельефа для вычисления высотной отметки местоположения в соответствии с одним вариантом осуществления настоящего изобретения.

Нижеследующее описание и чертежи являются иллюстративными для изобретения и не должны рассматриваться в качестве ограничивающих настоящее изобретение. Многочисленные конкретные подробности описаны, чтобы предоставить полное понимание настоящего изобретения. Однако в некоторых примерах известные или обычные подробности не описаны, чтобы избежать внесения неясностей в описание настоящего изобретения.

По меньшей мере один вариант осуществления настоящего изобретения направлен на эффективное хранение данных о высотных отметках местности, или рельефе местности, в базе данных и на эффективное использование данных о рельефе местности из базы данных, чтобы обеспечить оценку высоты для местоположения.

На фиг. 2 показан пример системы обработки данных, которая может быть использована в качестве обслуживающей системы или сервера, в различных вариантах осуществления настоящего изобретения. Например, как описано в патенте США № 5841396, сервер может поставлять вспомогательные (поддерживающие) данные, например доплеровские (Doppler) или другие спутниковые вспомогательные данные, на приемник GPS в подвижной станции. В дополнение, или альтернативно, вычисление конечного местоположения может выполнять сервер местоположения, а не подвижная станция (после приема от подвижной станции данных псевдодальностей или других данных, посредством которых могут быть определены данные псевдодальности), и затем результаты определения конечного местоположения могут быть направлены на базовую станцию или на некоторую другую систему. Система обработки данных в качестве сервера местоположения обычно включает в себя устройства 212 связи, такие как модемы или сетевые интерфейсы. Сервер местоположения может быть соединен с некоторым количеством различных сетей через устройства 212 связи (например, модемы или другие сетевые интерфейсы). Такие сети включают в себя центр коммутации сотовой связи или множественные центры 225 коммутации сотовой связи, коммутаторы 223 наземных телефонных систем, базовые станции сотовой связи, другие источники 227 сигналов GPS или другие процессоры из других серверов 221 местоположения.

Множественные базовые станции сотовой связи обычно расположены, чтобы охватить географическую область зоной обслуживания радиосвязи, и эти различные базовые станции соединены по меньшей мере с одним центром коммутации подвижной связи, как известно из предшествующего уровня техники (например, см. фиг. 1). Таким образом, множество базовых станций может быть географически распределено и соединено вместе посредством центра коммутации подвижной связи. Сеть 220 может быть соединена с сетью из опорных GPS-приемников, которые обеспечивают дифференциальную информацию GPS и могут также обеспечивать данные об эфемеридах GPS для использования в вычислении местоположения подвижных систем. Сеть соединена посредством модема или другого интерфейса связи с процессором 203. Сеть 220 может быть соединена с другими компьютерами или сетевыми компонентами. Сеть 220 также может быть соединена с вычислительными системами, управляемыми операторами аварийных ситуаций, такими как Пункты ответственности за общественную безопасность, которые отвечают на телефонные вызовы (по номеру) 911. Различные примеры способов для использования сервера местоположения были описаны в многочисленных патентах США, например патенты США № 5841396; № 5874914; № 5812087; и № 6215442, которые включены в настоящее описание путем ссылок.

Сервер 201 местоположения, который является разновидностью системы обработки данных, включает в себя шину 202, которая соединена с микропроцессором 203, и ПЗУ 207 (ROM), и энергозависимым ОЗУ 205 (RAM), и энергонезависимым запоминающим устройством 206. Процессор 203 соединен со сверхоперативным запоминающим устройством, или кэшем 204, как показано в примере на фиг. 2. Шина 202 осуществляет межкомпонентное соединение этих различных компонентов вместе. Тогда как на фиг. 2 показано, что энергонезависимая память является локальным устройством, соединенным непосредственно с остальными компонентами в системе обработки данных, и настоящее изобретение может использовать энергонезависимое запоминающее устройство, которое является удаленным от системы, такое как сетевое запоминающее устройство, которое соединено с системой обработки данных посредством сетевого интерфейса, например модемом или сетевым интерфейсом Ethernet. Шина 202 может включать в себя одну или несколько шин, соединенных между собой посредством различных мостов, контроллеров и/или адаптеров, как известно в данном уровне техники. Во многих ситуациях сервер местоположения может выполнять свои операции автоматически без участия персонала. В некоторых схемах (проектах), в которых требуется взаимодействие с персоналом, контроллер 209 ввода/вывода может обмениваться информацией с дисплеями, клавиатурами и другими устройствами ввода/вывода.

Обратите внимание, что, тогда как на фиг. 2 проиллюстрированы различные компоненты системы обработки данных, не предусмотрено представление какой-либо конкретной архитектуры или способа межсоединения компонентов, поскольку такие подробности не входят в настоящее изобретение. Будет также отмечено, что сетевые компьютеры и другие системы обработки данных, которые имеют меньшее количество компонентов или возможно большее количество компонентов, также могут быть использованы с настоящим изобретением и могут действовать в качестве сервера местоположения или ЭОМ.

Из данного описания будет очевидно, что аспекты настоящего изобретения могут быть воплощены, по меньшей мере частично, в программном обеспечении. То есть способы могут быть выполнены в вычислительной системе или в другой системе обработки данных в ответ на исполнение ее процессором последовательностей команд, содержащихся на запоминающем устройстве таком, как ПЗУ 207, энергозависимое ОЗУ 205, энергонезависимое запоминающее устройство 206, кэш 204 или удаленное запоминающее устройство. В различных вариантах осуществления могут быть использованы аппаратные схемы в комбинации с командами программного обеспечения для того, чтобы осуществить настоящее изобретение. Таким образом, способы не являются ограниченными ни какой-либо конкретной комбинацией схемы аппаратного обеспечения и программного обеспечения, ни каким-либо конкретным источником для команд, исполняемых системой обработки данных. В дополнение по всему данному описанию различные функции и операции описаны, как исполняемые или вызываемые программой программного обеспечения, чтобы упростить описание. Однако специалисты в данной области техники признают, что подразумеваемое под такими выражениями является результатом функций от исполнения программы процессором, например процессором 203.

В некоторых вариантах осуществления способы настоящего изобретения могут быть выполнены на вычислительных системах, которые одновременно используются для других функций таких, как коммутация сотовой связи, служба передачи сообщений, и т.д. В таких случаях некоторые или все из средств аппаратного обеспечения по фиг. 2 были бы совместно используемы для нескольких функций.

Тогда как сохранение или извлечение данных высотных отметок местности из базы данных могут быть выполнены на сервере местоположения, эти операции также могут быть выполнены на других системах цифровой обработки, подобных проиллюстрированной на фиг. 2.

На фиг. 3 показан способ использования Базы (БДРМ) данных рельефа местности, чтобы обеспечить информацию о высотах местности в реальном времени в течение навигационной обработки в Элементе определения местоположения (ЭОМ) в соответствии с одним вариантом осуществления настоящего изобретения. База (БДРМ) 301 данных рельефа местности, сохраняемая в соответствии с настоящим изобретением (например, на запоминающем устройстве с произвольной выборкой (ОЗУ, RAM) или на жестком диске), обеспечивает доступ в реальном времени на линии 311 (шине) к серверу 305 местоположения для высотной поддержки. Сервер 305 местоположения может эффективно извлекать высоту для любого заданного местоположения в ходе выполнения определения местоположения подвижной станции.

В одном примере данные 303 справочника на базовой станции поставляют соответствующую горизонтальной плоскости оценку позиции узла сотовой связи на сервер местоположения, который может быть использован, чтобы получить начальную оценку высоты подвижной станции.

Сигналы 309 ССОМ, исходящие от базовых станций или спутников GPS (или других типов спутников ССОМ), принимают на подвижной станции. Сигнал 307 ССОМ, принятый на подвижной станции, используют, чтобы определить моменты времени прихода для сигналов ССОМ, исходящих от базовых станций или спутников ССОМ. Сервер 305 местоположения использует моменты времени прихода, чтобы определить местоположение подвижной станции.

В ходе выполнения многократного определения местоположения подвижной станции, лучшие оценки высоты подвижной станции могут быть извлечены из БДРМ 301, если сервер 305 местоположения определяет более точные координаты в горизонтальной плоскости для подвижной станции на основании времен-прихода (или псевдодальностей).

В другом примере позиция в горизонтальной плоскости, или позиция по горизонтали, определенная на основании времен-прихода, может быть использована для извлечения оценки высоты подвижной станции из БДРМ для того, чтобы определить состояние измерения момента времени прихода (или псевдодальности), используя способы, описанные в патенте США № 6061018.

Тогда как на фиг. 3 проиллюстрирован пример, в котором моменты времени прихода измеряют на мобильной станции, такой как система РТПЛС, система ССОМ или комбинированная система РТПЛС, будет оценено, что такой доступ в реальном времени к БДРМ также может быть использован в других системах определения местоположения, в которых моменты времени прихода измеряют на базовых станциях, например в системе TDOA, в которой моменты времени прихода сигнала от подвижной станции определяют на множестве базовых станций.

На фиг. 4 показан способ наполнения информации о высотах для данных справочника базовой станции, информация которого может быть использована в течение навигационной обработки в Элементе (ЭОМ) определения местоположения для высотной поддержки, в соответствии с одним вариантом осуществления настоящего изобретения. База 401 (БДРМ) данных рельефа местности, сохраняемая в соответствии с настоящим изобретением (например, на запоминающем устройстве с произвольным доступом (ОЗУ, RAM) или на жестком диске), обеспечивает автономный доступ по линии 411, чтобы наполнить информацию о высотах в справочнике данных, поддерживаемом на базовой станции. В одном примере программный модуль, называемый Вычислителем/Редактором (413) Справочника базовой станции, используют, чтобы вычислить оценку высоты местности для каждого из узлов сотовой связи, каталогизированных в справочнике данных, поддерживаемом на базовой станции. Оцененную высоту местности для каждого узла сотовой связи поддерживают на базовой станции, чтобы поставлять высотную поддержку на сервер 405 местоположения. Однако если используют подход автономного доступа, сервер местоположения не может получить лучшие оценки высоты подвижной станции, если более точные оценки позиции по горизонтали подвижной станции определяют на основании моментов времени прихода сигналов ССОМ, принятых на подвижной станции.

На фиг. 5 показан способ формирования Цифровых моделей рельефа в соответствии с одним вариантом осуществления настоящего изобретения. Область 501 из Цифровой модели рельефа покрыта множеством прямоугольных элементов модели (например, элементы 511, 512, 513 и 514 модели). Например, область 501 может быть США, или Кореей, или Японией. Когда для некоторого региона являются доступными Цифровые модели рельефа, имеющие различные разрешающие способности, используют иерархию элементов модели. Элемент модели на более низком уровне (слое) имеет более высокую разрешающую способность, и элемент модели на более высоком уровне имеет более низкую разрешающую способность. Элемент модели более высокого уровня имеет индикатор, который указывает, есть ли элементы модели более низкого уровня, которые моделируют тот же регион области. Например, элемент 511 модели и подэлементы 521, 522, 523, и 524 модели моделируют один и тот же регион области 501. Элемент 511 модели является элементом модели более высокого уровня; элементы 521, 522, 523, и 524 модели являются элементами модели более низкого уровня. Если высотная отметка местоположения не может быть определена на основании элемента модели более низкого уровня, то может быть использован элемент модели более высокого уровня, который содержит элемент модели более низкого уровня для того, чтобы определить с меньшей точностью высотную отметку местоположения.

Такая схема иерархической сетки дает возможность быстрого извлечения данных. Сначала идентифицируют область, которая содержит местоположение. Затем идентифицируют элемент модели высокого уровня, который содержит местоположение. Если есть элемент модели более низкого уровня, то осуществляют доступ к элементу модели более низкого уровня, который содержит местоположение. Элементы модели являются хэшированными по координатам в направлениях по широте и по долготе, так что элемент модели, содержащий заданное местоположение, может быть легко идентифицирован, исходя из координат в горизонтальной плоскости, соответствующих местоположению.

На фиг. 6 показана примерная схема для нумерации элементов модели. Такая схема может быть использована, чтобы отслеживать элементы модели более низкого уровня, находящиеся внутри элемента модели более высокого уровня, или элементов модели внутри области. Формируя прямоугольную сетку, элементы модели нумеруют по столбцам или по строкам, чтобы индексировать элементы модели так, чтобы индекс элемента модели мог быть легко определен из его индексов строки и столбца. Его индексы строки и столбца также могут быть легко определены из индекса элемента модели. В примере по фиг. 6 элементы модели пронумерованы от верхнего левого (Северо-западного) угла региона построчным способом. В предположении, что индексом столбца элемента модели является I, индексом строки элемента модели является J и количеством столбцов сетки является N, индекс элемента модели есть J*N+I. В предположении, что индексом элемента модели является М, индекс столбца I=mod(М,N), и индекс строки J=(M-I)/N. Поскольку индекс столбца и индекс строки элемента модели, который содержит заданное местоположение, могут быть вычислены из координат в горизонтальной плоскости, соответствующих местоположению, и позиции сетки, может быть легко идентифицирован элемент модели, который содержит местоположение.

На фиг. 7 показан пример профиля высотных отметок местности. Профиль формируют высотные отметки множества точек дискрет, находящиеся по линии развертки по широте (или по долготе) в элементе модели Цифровой модели рельефа. Интерполяция высотных отметок в точках дискрет обеспечивает высотную отметку для любой заданной точки на линии. Например, высота 703 представляет высотную отметку в точке Hn; и кривая 701 представляет модель рельефа для сегмента между точками Н₀ и H_n. Могут быть использованы различные схемы 1D-интерполяции (одномерной), чтобы формировать кривую 701.

На фиг. 8 показан способ определения высотной отметки местности для местоположения на основании Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения. Элемент модели в DEM содержит множество профилей. Например, профили P1, P2, P3 и P4 по фиг. 8 содержатся внутри отдельного элемента модели DEM. Высотная отметка местоположения может быть определена из высотных отметок точек дискрет вблизи местоположения.

Например, высотная отметка точки X по фиг. 8 может быть определена на основании интерполяции, используя высотные отметки в точках дискрет X1, X2, X3 и X4. В примере по фиг. 8 используют билинейную интерполяцию, чтобы вычислить высотную отметку для точки между двумя профилями и между двумя линиями точек дискрет (которые находятся в направлении, не являющемся параллельным линиям профилей). В одном варианте осуществления настоящего изобретения используют схему биквадратной интерполяции для определения высотной отметки местоположения, используя высотные отметки точек дискрет вблизи местоположения в элементе модели Цифровой модели рельефа.

Данные профиля для элемента модели обычно сохраняют в определенной для области системе координат. Например, координаты по горизонтали могут быть представлены в системе WGS84, или в системе NAD83, или в системе, определенной для Японии или Кореи; и система координат в вертикальной плоскости, или система вертикальных координат, может быть системой Среднего уровня (MSL) моря (например, NAD88 или NAD27), или системой Высота над эллипсоидом (ВНЭ). Следует отметить, что различные системы ВНЭ (например, система WGS84, система WGS72, система Clarke 1866, или система Bessel 1841) могут использовать различные модели эллипсоида (например, различные большие полуоси оси и коэффициенты сжатия (сплющивания)). Могут быть использованы таблицы уровней приведения (уровненных поверхностей для начала отсчета высот) для определения преобразований от разнообразных различных систем координат к одной системе координат (например, координат, используемых ЭОМ, таких как система WGS84).

На фиг. 9 показана Обслуживающая подсистема поддержки высотных отметок в соответствии с одним вариантом осуществления настоящего изобретения. Обслуживающая подсистема 901 поддержки высотных отметок содержит блок интерполятора, или интерполятор 910, геодезический компьютер 920, блок 930 управления цифровой моделью рельефа и блок управления доступом, или администратор 940 доступа к данным цифровой модели рельефа.

Интерполятор 910 содержит 1D-интерполятор 911 (в одном измерении) и 2D-интерполятор 913 (в двух измерениях), чтобы обеспечить интерполяцию 1D и 2D. В одном варианте осуществления настоящего изобретения 2D-интерполятор может исполнять билинейную интерполяцию, которую использует NGS (Национальная геодезическая служба) и NIMA (Национальное агентство картографии США) для интерполяции различных сеток данных. В другом варианте осуществления настоящего изобретения 2D-интерполятор также может выполнять биквадратную интерполяцию, чтобы вычислять высотную отметку местоположения, исходя из высотных отметок точек дискрет вблизи местоположения.

Геодезический компьютер 920 содержит блок 921 управления преобразованиями уровней приведения и картографический проектор 923. Геодезический компьютер 920 используют, чтобы исполнить преобразование координат местоположения, осуществляемое между одной системой координат (например, системой, используемой сервером местоположения) и другой системой координат (например, системой, используемой элементом модели DEM). Обычный способ Molodensky аналитического преобразования может быть использован для преобразования уровня приведения для Японии; способ, основанный на интерполяции NADCON, может быть использован, чтобы преобразовать данные DEM в представлении NAD27 США. Если система координат в горизонтальной плоскости, или система горизонтальных координат, для элемента модели DEM является системой WGS72, то чтобы выполнить преобразование, могут быть использованы преобразование Molodensky или S-преобразование с 7 параметрами. Геодезический компьютер 920 может также использовать другие преобразования, такие как 3D преобразование подобия (известное также как преобразование Bursa-Wolf).

Блок 930 управления DEM содержит область 931 элемента модели, которая дополнительно содержит элементы (933) модели DEM. Элементы модели DEM содержат данные высотных отметок, сохраняемые в ОЗУ, или в файле, отображенном на память (MMF), или в файлах на накопителе на дисках (например, на жестком диске, в постоянном запоминающем устройстве на компакт-диске (CD-ROM), в ПЗУ на универсальном цифровом диске (DVD-ROM), и т.д.). Блок управления DEM используют, чтобы сохранять и управлять иерархическим перечнем элементов модели.

Администратор 940 доступа к данным DEM содержит декодер 941 и кодер 943, чтобы обеспечить доступ к элементам модели для различных устройств хранения (например, жесткого диска или ОЗУ). Кодер 943 может преобразовывать модель DEM из плоского файла в индексированную и сжатую БДРМ, используя способ, описываемый ниже. Декодер 941 может декодировать модель DEM, кодированную в индексированной и сжатой БДРМ, для того, чтобы осуществлять доступ к данным высотных отметок, находящимся в базе данных.

На фиг. 10 показано представление данных элемента Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения. В соответствии с одним вариантом осуществления настоящего изобретения данные для различных профилей в элементе модели являются сжатыми с использованием схемы, описываемой ниже. Чтобы в пространстве хранения, показанном на фиг. 10, хранить профили в элементе модели, используют заголовок 1001 элемента модели, чтобы задать общие данные (метаданные) для элемента модели, который(ые) является(ются) необходимым для интерпретации DEM в элементе модели. Индексы 1011-1019 сохраняют после заголовка 1001 элемента модели, чтобы указать местоположения начальных точек данных для различных профилей. Например, индекс 1012 указывает на заголовок 1022 для профиля 1, который содержит метаданные, конкретные для интерпретации сжатых данных 1032 высотных отметок для профиля 1. Аналогично индекс 1019 указывает на заголовок 1029 для профиля n. В целом сжатые данные высотных отметок для различных профилей требуют пространств хранения, имеющих различные размеры. Из координат по горизонтали для данного местоположения, исходя из заголовка элемента модели, могут быть определены профили, которые содержат точки дискрет вблизи местоположения. К индексам для этих профилей может быть осуществлен доступ, чтобы определить местоположение заголовков профилей и сжатых данных высотных отметок для этих профилей. Индексы точек дискрет вблизи местоположения в профилях могут быть определены из заголовка элемента модели (и, в некоторых вариантах осуществления, из заголовка профилей).

На фиг. 11 показано представление данных заголовка для сохранения порции Цифровой модели (DEM) рельефа в соответствии с одним вариантом осуществления настоящего изобретения. Данные 1101 содержат тип записи и длину заголовка. Тип записи указывает, является ли данный заголовок заголовком профиля или заголовком элемента модели. Элементарная группа 1103 содержит индикаторы, указывающие тип данных, содержащихся в этом элементе модели, которыми могут быть DEM, Geoid, преобразования уровней приведения широты или долготы. Система 1105 горизонтальных координат задает систему координат, используемую для представления позиций по горизонтали для точек дискрет, которой может быть географическая система, система UTM (Universal Transverse Mercator, Универсальная (Всемирная) поперечно-цилиндрическая проекция Меркатора), и т.д. Система 1107 вертикальных координат задает систему координат, используемую для представления высотных отметок точек дискрет, которой могут быть местная (национальная) SL, MSL, или ВНЭ, и т.д. Единицы 1190 задают единицы, используемые в измерении координат по горизонтали и высотных отметок. Упорядочение 1111 профиля задает направление линий профиля (например, по направлению долготы или по направлению широты) и количество точек дискрет по обоим направлениям в элементе модели. Угловые точки 1113 задают позиции угловых точек элемента модели. Опорная точка 1115 определяет опорное (базисное) значение для высотных отметок, и широты и долготы для начальных точек профилей. Размер 1117 элемента модели задает размер элемента модели в направлении широты и в направлении долготы. Описание 1119 подэлемента модели указывает размер (количество) подэлементов модели, находящихся уровнем ниже элемента модели, если таковые существуют. Параметры 1121 сжатия включают в себя коэффициент масштабирования, используемый в кодировании данных высотных отметок, и индикатор, показывающий, являются или не являются данные высотных отметок кодированными по схеме группового кодирования. Подробности о коэффициенте масштабирования и групповом кодировании описаны ниже.

Из приведенного выше описания специалисту в данной области техники было бы очевидно, что может быть использовано различное представление данных заголовков для заголовков элементов модели или заголовков профиля. Заголовки элементов модели и заголовки профилей могут иметь различные форматы; заголовок элемента модели может иметь большее или меньшее количество элементарных групп данных, чем показано на фиг. 11; и заголовок профиля может иметь большее или меньшее количество элементарных групп данных, чем показано на фиг. 11. Например, заголовок элемента модели может дополнительно включать в себя строку, показывающую источник (исходную) DEM (например, на основании модели USGS или на основании модели NGS) или информацию об упорядочении байтов; между тем заголовок профиля может не иметь элементарных групп 1105 и 1107 для задания систем координат, поскольку все профили внутри элемента модели использовали одну и ту же систему координат.

На фиг. 12 показана схема Группового кодирования, которая может быть использована с настоящим изобретением. Строка символов (например, числа, представляющие высотные отметки) может быть разделена на части из непрерывных серий и последовательностей. Непрерывная серия является непрерывной повторяющейся строкой из конкретного символа. Последовательность является непрерывной неповторяющейся строкой символов. Например, строка символов между символами 1201 и 1202 является непрерывной серией; и строка символов между символами 1203 и 1204 является последовательностью. Непрерывная серия может быть кодирована числом, указывающим количество повторений символа, и непосредственно символом. Например, непрерывная серия между символами, соответствующими позициям 1201 и 1202, кодирована числом, соответствующим ссылочной позиции 1211, которое равно количеству повторений, вычтенному (вычитаемому за вычетом) из единицы, и символа, соответствующего ссылочной позиции 1212. Подобным образом последовательность может быть кодирована числом, указывающим длину строки неповторяющихся символов и строки из неповторяющихся символов. Например, последовательность между символами, соответствующими ссылочным позициям 1203 и 1204, представлена числом, соответствующим ссылочной позиции 1213, которое равно единице, вычтенной из количества символов между символами, соответствующими ссылочным позициям 1203 и 1204, и экземпляром символов (символов между ссылочными позициями 1217 и 1214). Подобным образом непрерывная серия между символами, соответствующими ссылочным позициям 1205 и 1206, кодирована числом, соответствующим ссылочным позициям 1215 и 1216. В примере согласно фиг. 12 непрерывная серия представлена отрицательным числом, предшествующим символу; и последовательность представлена неотрицательным числом, предшествующим строке символов. Таким образом, кодированные данные между ссылочными позициями 1211 и 1216 могут быть декодированы, чтобы восстановить исходную строку символов (между ссылочными позициями 1201 и 1206) в ходе выполнения декодирования.

На фиг. 13 проиллюстрирован пример кодирования порции Цифровой модели (DEM) рельефа для сохранения в соответствии с одним вариантом осуществления настоящего изобретения. Столбец 1303 представляет исходные данные высотных отметок для профиля DEM. Точка дискреты в строке 1351 содержит минимальное значение (количество) высотных отметок для этого профиля. Столбец 1305 представляет нормированные высотные отметки, которые получают вычитанием минимального значения из исходных данных, находящихся в столбце 1303. Столбец 1307 представляет масштабированные высотные отметки, которые получают делением нормированных высотных отметок, находящихся в столбце 1305, на коэффициент масштабирования (четыре). В одном варианте осуществления настоящего изобретения коэффициенты масштабирования являются такими, что деление целых чисел может быть выполнено посредством операций поразрядного сдвига в течение хода выполнения кодирования, и умножение целых чисел может быть выполнено посредством операций поразрядного сдвига в течение хода выполнения декодирования. В одном варианте осуществления настоящего изобретения при измерении высотных отметок в (единице измерения) метрах максимальным значением коэффициента масштабирования является 4 (то есть Младший значащий бит (LSB) масштабированной высотной отметки представляет 4 метра); при измерении высотной отметки в (единице) футах максимальным значением коэффициента масштабирования является 16 (то есть, LSB=16 футов). После процедур нормирования и масштабирования область значений данных масштабируемых высотных отметок может быть сокращена, так что масштабированные высотные отметки могут быть представлены целыми числами, которые требуют меньшего количества пространств хранения. В одном варианте осуществления настоящего изобретения исходные данные представлены 2-байтовыми целыми числами. После процедуры нормирования и масштабирования некоторые профили могут быть представлены посредством масштабированных и нормированных высотных отметок в формате 1-байтовых целых чисел. Масштабированные и нормированные высотные отметки в столбце 1307 могут быть дополнительно сжаты с использованием схемы группового кодирования. Например, масштабированные высотные отметки между строками 1351 и 1352 могут быть кодированы как последовательность (1311, 1312 и 1313); и таковые между строками 1353 и 1359 могут быть кодированы как непрерывная серия (1321 и 1322).

На фиг. 14 показан способ кодирования порции Цифровой модели (DEM) рельефа для сохранения в соответствии с одним вариантом осуществления настоящего изобретения. Операция 1401 загружает высотные отметки для профиля элемента модели DEM. Обычно данные высотных отметок считывают из плоского файла (неиндексированного), который содержит Цифровую модель рельефа области (например, США, или всего мира). Такой плоский файл является большим по размеру. Для эффективного хранения и осуществления доступа к Цифровой модели рельефа используют операции 1403-1411, чтобы сжимать данные и сохранять данные в одном или нескольких индексированных файлах. Операция 1403 формирует нормированные высотные отметки для профиля. Высотные отметки профиля нормализуют по отношению к опорному значению. В одном варианте осуществления настоящего изобретения нормированные высотные отметки формируют вычитанием из высотных отметок минимальной высотной отметки элемента модели DEM. В другом варианте осуществления высотные отметки нормируют по отношению к минимальной высотной отметке для профиля (или среднему превышению для профиля). Операция 1405 масштабирует нормированные высотные отметки, чтобы сформировать масштабированные высотные отметки. В одном варианте осуществления настоящего изобретения масштабированные высотные отметки требуют меньшего количества пространства хранения, чем высотные отметки, загружаемые из плоского файла, поскольку область значений данных сокращена после операций нормирования и масштабирования. Например, исходные данные высотных отметок для профиля, который представлен посредством 2-байтовых целых чисел, могут быть представлены посредством 1-байтовых масштабированных высотных отметок. Масштабированные высотные отметки кодирует операция 1407 (по схеме) группового кодирования, чтобы сформировать сжатые данные высотных отметок для профиля. Операция 1409 формирует индекс для доступа к сжатым данным высотных отметок в индексированном файле. В операции 1411 индекс и сжатые данные высотных отметок сохраняют в индексированном файле.

Операции 1401-1411 могут быть повторены, чтобы кодировать (сжать) множество профилей для элемента модели DEM и сохранить сжатые данные высотных отметок для профилей элемента модели в одном индексированном файле. В одном варианте осуществления сжатые данные высотных отметок для различных элементов Цифровой модели рельефа сохраняют в различных файлах. Для каждого из элементов модели используют отдельный индексированный файл. Альтернативно, множество элементов модели для сжатых данных высотных отметок могут быть сохранены в одном индексированном файле, при этом индексы для доступа к каждому из элементов модели сохраняют для осуществления быстрых доступов к индивидуальным элементам модели. Множество элементов модели для DEM, которая моделирует конкретную географическую область, могут быть объединены в качестве области DEM. DEM может иметь множество областей. Обычно данные высотных отметок для элементов модели DEM представляют в определенных для области системах координат.

Если доступно множество DEM с различными разрешающими способностями, то элементы модели из различных DEM объединяют в иерархии, как описано выше (см. фиг. 5). Индексированные файлы хранят индикаторы, связывающие элементы модели различных уровней в иерархии.

Сжатые и индексированные данные высотных отметок для одной или нескольких Цифровых моделей рельефа образуют Базу (БДРМ) данных рельефа местности.

На фиг. 15 показан способ вычисления высотной отметки для местоположения в соответствии с одним вариантом осуществления настоящего изобретения. После того, как операция 1501 принимает первые координаты по горизонтали для местоположения, измеренные в первой системе горизонтальных координат (например, в системе координат, используемой Элементом определения местоположения), операция 1503 преобразует первые координаты по горизонтали для местоположения во вторые координаты по горизонтали для местоположения, измеряемые во второй системе горизонтальных координат, используемой Базой данных рельефа местности (БДРМ). Обычный элемент определения местоположения использует систему WGS84 для задания позиции по горизонтали; и БДРМ обычно хранит профили, используя для различных областей определенные для области системы координат, такие как система Универсальной поперечно-цилиндрической проекции Меркатора (UTM), географическая система (широта, долгота), локальная система координат для региона (например, Государственная система плоскостных (проекционных) координат США), и т.д. Таким образом, преобразование в операции 1503 используют, чтобы сформировать координаты, которые могут быть использованы для поиска в БДРМ данных высотных отметок, находящихся вблизи местоположения, заданного посредством первых координат по горизонтали. Операция 1505 извлекает из Базы данных рельефа местности высотные отметки для множества точек, находящихся вблизи местоположения. После того, как операция 1507 интерполирует высотные отметки для множества точек, находящихся вблизи местоположения, чтобы вычислить первую высотную отметку местоположения, измеренную в первой системе вертикальных координат, используемой Базой данных рельефа местности, операция 1509 преобразует первую высотную отметку местоположения во вторую высотную отметку местоположения, измеренную во второй системе вертикальных координат (например, системе координат, используемой Элементом определения местоположения). Типичный Элемент определения местоположения использует систему Высоты над эллипсоидом (ВНЭ) для задания высотной отметки (высоты); и БДРМ обычно хранит профили, используя для различных областей (модели) системы координат, определенные для области, такие, как система Среднего уровня моря (MSL), система Местного (национального) Уровня над морем (Local SL), или система Высоты над эллипсоидом. В одном варианте осуществления настоящего изобретения точность оценки (стандартную ошибку) интерполированной высотной отметки местности также вычисляют в операции 1507. Операция 1511 осуществляет высотную поддержку, используя вторую высотную отметку местоположения. Альтернативно, чтобы осуществить высотную помощь, вторая высотная отметка местоположения может быть поставлена на Элемент определения местоположения. Вычисление второй высотной отметки для высотной поддержки может быть в виде доступа в реальном времени, как проиллюстрировано на фиг. 3, или в виде автономного доступа, как проиллюстрировано на фиг. 4. Различные способы высотной поддержки такие как описаны в патенте США № 6061018, могут быть использованы в настоящем изобретении.

В одном варианте осуществления настоящего изобретения область DEM, которая содержит местоположение, идентифицируют и извлекают, чтобы извлечь из Базы данных Рельефа местности высотные отметки для множества точек, находящихся вблизи местоположения. Затем идентифицируют и извлекают элемент модели DEM, который содержит местоположение. Исходя из заголовка элемента модели, идентифицируют и выбирают профили, содержащие точки вблизи местоположения. Исходя из заголовков профилей и заголовка элемента модели, идентифицируют точки вблизи местоположения. После того, как декодированы по меньшей мере порции сжатых профилей из Базы данных рельефа местности, могут быть найдены высотные отметки для множества точек, находящихся вблизи местоположения.

На фиг. 16 показан один способ декодирования порции Цифровой модели рельефа (DEM) для вычисления высотной отметки местоположения в соответствии с одним вариантом осуществления настоящего изобретения. Операция 1601 получает индекс для доступа к сжатым данным высотных отметок для профиля в элементе модели DEM. Элемент модели DEM может быть сохранен в файле(MMF), отображенным на память, или в ОЗУ, или в файле файловой системы в системе цифровой обработки (например, на накопителе на жестком диске, КД-ПЗУ (CD-ROM), или сетевом файле), и т.д. Например, согласно фиг. 10, после идентификации того, что профиль n содержит точки вблизи местоположения, получают индекс 1019 для профиля n для того, чтобы осуществить доступ к сжатым данным 1039 для профиля n.

Операция 1602 идентифицирует точки, которые находятся вблизи местоположения в профиле. В одном варианте осуществления настоящего изобретения используют индекс, чтобы извлечь заголовок профиля, исходя из которого вычисляют индексы точек дискрет в профиле, которые находятся вблизи местоположения. В другом варианте осуществления вычисляют индексы точек дискрет, находящихся вблизи местоположения, используя информацию в заголовке элемента модели. Альтернативно, вычисление индексов точек дискрет, находящихся вблизи местоположения, может включать в себя как заголовок элемента модели, так и заголовки профиля.

После того как операция 1603 извлечет сжатые данные высотных отметок для профиля, операция 1605 осуществляет групповое декодирование сжатых данных высотных отметок, чтобы сформировать масштабированные высотные отметки для точек, находящихся вблизи местоположения. В целом необходимо осуществить групповое декодирование порции сжатого профиля, чтобы получить масштабированные высотные отметки для точек вблизи местоположения. Операция 1607 обратно (инверсно) масштабирует высотные отметки, чтобы сформировать нормированные высотные отметки. Операция 1609 денормирует нормированные высотные отметки, чтобы восстановить высотные отметки для точек, находящихся вблизи местоположения. Опорную высотную отметку, которую вычитают из исходных данных высотных отметок в ходе выполнения декодирования, складывают обратно с нормированными высотными отметками, чтобы воспроизвести высотные отметки точек, находящихся вблизи местоположения. Операция 1610 вычисляет высотную отметку местоположения на основании интерполяции, используя высотные отметки точек вблизи местоположения. В одном варианте осуществления настоящего изобретения операции 1601-1609 повторяют для множества профилей вблизи местоположения, чтобы получить высотные отметки для множества точек во множестве профилей прежде, чем выполняют операцию 1610 вычисления высотных отметок местоположения, и используют биквадратную интерполяцию, чтобы вычислить высотную отметку местоположения.

Поскольку Базы данных рельефа местности в соответствии с различными вариантами осуществления настоящего изобретения хранят данные о высотных отметках в сжатом и индексированном формате, то требуется меньшее количество пространства хранения. Таким образом, сжатые данные высотных отметок из Цифровой модели (DEM) рельефа с высоким разрешением могут быть сохраняемы на носителях данных с более высокими скоростями доступа (например, ОЗУ или файле, отображенного на память) для осуществления высотной поддержки в реальном времени в ходе выполнения определения местоположения в комбинированной системе определения местоположения с помощью беспроводной связи.

Хотя настоящее изобретение проиллюстрировано с помощью примера, в котором каждый из профилей содержит данные высотных отметок для точек дискрет на единственной линии развертки, настоящее изобретение может быть также применено, если каждый из профилей содержит данные высотных отметок для точек дискрет на множестве линий развертки.

В данном описании изобретение было описано со ссылкой на конкретные варианты его осуществления. Будет очевидно, что в них могут быть сделаны различные изменения без выхода за рамки существа и объема изобретения, как сформулировано в нижеследующей формуле изобретения. Описание и чертежи должны, соответственно, рассматриваться предпочтительно в иллюстративном смысле.

1. Способ извлечения данных о высотных отметках, заключающийся в том, что:

определяют адрес ячейки памяти первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс, причем Цифровая модель рельефа содержит множество сжатых порций, которые являются порциями сжатых профилей в первом элементе Цифровой модели рельефа, при этом множество сжатых порций сохраняют в одном из: в файле (MMF), отображенном на память; оперативном запоминающем устройстве (ОЗУ, RAM) и в файле файловой системы в системе цифровой обработки; при этом множество сжатых порций включает в себя первую сжатую порцию, первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция;

осуществляют развертывание первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты в Цифровой модели рельефа;

идентифицируют первый элемент модели, причем первый элемент модели содержит первое местоположение и является одним элементом из множества элементов модели в области Цифровой модели рельефа; и

идентифицируют первый профиль, который находится вблизи первого местоположения, причем первая сжатая порция является порцией для первого профиля.

2. Способ по п.1, по которому развертывание первой сжатой порции заключается в том, что:

декодируют по схеме группового декодирования первую сжатую порцию, чтобы сформировать масштабированные данные высотных отметок;

осуществляют обратное масштабирование масштабированных данных высотных отметок, чтобы сформировать нормированные данные высотных отметок; и

осуществляют сложение опорной высотной отметки с нормированными данными высотных отметок, чтобы сформировать первые данные высотных отметок.

3. Способ по п.1, который также заключается в том, что:

идентифицируют множество точек дискрет вблизи первого местоположения;

извлекают из Цифровой модели рельефа высотные отметки для множества точек дискрет и

вычисляют высотные отметки для первого местоположения на основании интерполяции, используя высотные отметки множества точек дискрет.

4. Способ по п.3, который также заключается в том, что:

выполняют преобразование координат, чтобы выразить в системе координат, используемой Цифровой моделью рельефа, позицию по горизонтали для первого местоположения.

5. Способ по п.3, который также заключается в том, что:

поставляют высотную отметку первого местоположения на Элемент определения местоположения, чтобы осуществить высотную поддержку в системе определения местоположения.

6. Способ по п.5, по которому вычисление высотной отметки для первого местоположения заключается в том, что:

выполняют преобразование координат, такое, что высотная отметка для первого местоположения является выраженной в системе координат, используемой Элементом определения местоположения.

7. Машиночитаемый носитель, содержащий исполняемые компьютерной программой команды, которые при исполнении системой цифровой обработки побуждают систему к выполнению способа извлечения данных высотных отметок, при этом способ заключается в том, что:

определяют адрес ячейки памяти первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс, причем Цифровая модель рельефа содержит множество сжатых порций, которые являются порциями сжатых профилей в первом элементе Цифровой модели рельефа, при этом множество сжатых порций сохраняют в одном из: в файле (MMF), отображенном на память; оперативном запоминающем устройстве (ОЗУ, RAM) и в файле файловой системы в системе цифровой обработки; при этом множество сжатых порций включает в себя первую сжатую порцию, первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция;

осуществляют развертывание первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты в Цифровой модели рельефа;

идентифицируют первый элемент модели, причем первый элемент модели содержит первое местоположение и является одним элементом из множества элементов модели в области Цифровой модели рельефа; и идентифицируют первый профиль, который находится вблизи первого местоположения, причем первая сжатая порция является порцией для первого профиля.

8. Носитель по п.7, в котором развертывание первой сжатой порции заключается в том, что:

осуществляют групповое декодирование первой сжатой порции, чтобы сформировать масштабированные данные высотных отметок;

осуществляют обратное масштабирование масштабированных данных высотных отметок, чтобы сформировать нормированные данные высотных отметок; и

осуществляют сложение опорной высотной отметки с нормированными данными высотных отметок, чтобы сформировать первые данные высотных отметок.

9. Носитель по п.7, в котором также идентифицируют множество точек дискрет, находящихся вблизи первого местоположения;

извлекают из Цифровой модели рельефа высотные отметки для множества точек дискрет и

вычисляют высотные отметки для первого местоположения на основании интерполяции, используя высотные отметки множества точек дискрет.

10. Носитель по п.9, в котором также выполняют преобразования координат, чтобы позицию по горизонтали для первого местоположения выразить в системе координат, используемой Цифровой моделью рельефа.

11. Носитель по п.9, в котором также поставляют высотную отметку первого местоположения на Элемент определения местоположения, чтобы осуществить высотную поддержку в системе определения местоположения.

12. Носитель по п.11, в котором вычисление высотной отметки для первого местоположения заключается в том, что:

выполняют преобразование координат, такое, что высотная отметка первого местоположения является выраженной в системе координат, используемой Элементом определения местоположения.

13. Система цифровой обработки для извлечения данных высотных отметок, содержащая:

средство, предназначенное для определения адреса ячейки первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс, причем Цифровая модель рельефа содержит множество сжатых порций, которые являются порциями сжатых профилей в первом элементе Цифровой модели рельефа, при этом множество сжатых порций сохраняют в одном из: в файле (MMF), отображенном на память; оперативном запоминающем устройстве (ОЗУ, RAM) и в файле файловой системы в системе цифровой обработки; при этом множество сжатых порций включает в себя первую сжатую порцию, первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция;

средство, предназначенное для развертывания первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты в Цифровой модели рельефа;

средство для идентификации первого элемента модели, причем первый элемент модели содержит первое местоположение и является одним элементом из множества элементов модели в области Цифровой модели рельефа; и

средство для идентификации первого профиля, который находится вблизи первого местоположения, причем первая сжатая порция является порцией для первого профиля.

14. Система цифровой обработки по п.13, в которой средство для развертывания первой сжатой порции содержит:

средство для группового декодирования первой сжатой порции, чтобы сформировать масштабированные данные высотных отметок;

средство для обратного масштабирования масштабированных данных высотных отметок, чтобы сформировать нормированные данные высотных отметок; и

средство для сложения опорной высотной отметки с нормированными данными высотных отметок, чтобы сформировать первые данные высотных отметок.

15. Система цифровой обработки по п.13, которая также содержит:

средство для идентификации множества точек дискрет, находящихся вблизи первого местоположения;

средство для извлечения из Цифровой модели рельефа высотных отметок для множества точек дискрет и

средство для вычисления высотной отметки первого местоположения на основании интерполяции с использованием высотных отметок множества точек дискрет.

16. Система цифровой обработки по п.15, которая также содержит:

средство для выполнения преобразования координат, чтобы позицию по горизонтали для первого местоположения выразить в системе координат, используемой Цифровой моделью рельефа.

17. Система цифровой обработки по п.15, которая также содержит:

средство для поставки высотной отметки первого местоположения на Элемент определения местоположения, чтобы осуществить высотную поддержку в системе определения местоположения.

18. Система цифровой обработки по п.17, в которой средство для вычисления высотной отметки первого местоположения содержит:

средство для выполнения преобразования координат, такого, что высотная отметка первого местоположения является выраженной в системе координат, используемой Элементом определения местоположения.

19. Способ извлечения данных о высотных отметках, заключающийся в том, что:

определяют адрес ячейки памяти первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс, причем Цифровая модель рельефа содержит множество сжатых порций, которые являются порциями сжатых профилей в первом элементе Цифровой модели рельефа, при этом множество сжатых порций сохраняют в одном из: в файле (MMF), отображенном на память; оперативном запоминающем устройстве (ОЗУ, RAM) и в файле файловой системы в системе цифровой обработки; при этом множество сжатых порций включает в себя первую сжатую порцию, первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция;

осуществляют развертывание первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты в Цифровой модели рельефа;

идентифицируют первый элемент модели, причем первый элемент модели содержит первое местоположение и является одним элементом из множества элементов модели в области Цифровой модели рельефа;

идентифицируют первый профиль, который находится вблизи первого местоположения, причем первая сжатая порция является порцией для первого профиля; и

идентифицируют область, содержащую первое местоположение и являющуюся одной из множества областей Цифровой модели рельефа.

20. Машиночитаемый носитель, содержащий исполняемые компьютерной программой команды, которые при исполнении системой цифровой обработки побуждают систему к выполнению способа извлечения данных высотных отметок, при этом способ заключается в том, что:

определяют адрес ячейки памяти первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс, причем Цифровая модель рельефа содержит множество сжатых порций, которые являются порциями сжатых профилей в первом элементе Цифровой модели рельефа, при этом множество сжатых порций сохраняют в одном из: в файле (MMF), отображенном на память; оперативном запоминающем устройстве (ОЗУ, RAM) и в файле файловой системы в системе цифровой обработки; при этом множество сжатых порций включает в себя первую сжатую порцию, первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция;

осуществляют развертывание первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты в Цифровой модели рельефа;

идентифицируют первый элемент модели, причем первый элемент модели содержит первое местоположение и является одним элементом из множества элементов модели в области Цифровой модели рельефа;

идентифицируют первый профиль, который находится вблизи первого местоположения, причем первая сжатая порция является порцией для первого профиля; и

идентифицируют область, содержащую первое местоположение и являющуюся одной из множества областей Цифровой модели рельефа.

21. Система цифровой обработки для извлечения данных высотных отметок, содержащая:

средство, предназначенное для определения адреса ячейки памяти первой сжатой порции Цифровой модели (DEM) рельефа, используя первый индекс, причем Цифровая модель рельефа содержит множество сжатых порций, которые являются порциями сжатых профилей в первом элементе Цифровой модели рельефа, при этом множество сжатых порций сохраняют в одном из: в файле (MMF), отображенном на память; оперативном запоминающем устройстве (ОЗУ, RAM) и в файле файловой системы в системе цифровой обработки; при этом множество сжатых порций включает в себя первую сжатую порцию, первый индекс, указывающий на ячейку запоминающего устройства, в которой хранится первая сжатая порция;

средство, предназначенное для развертывания первой сжатой порции, чтобы извлечь первые данные высотных отметок по меньшей мере для одной точки дискреты в Цифровой модели рельефа;

средство для идентификации первого элемента модели, причем первый элемент модели содержит первое местоположение и является одним элементом из множества элементов модели в области Цифровой модели рельефа;

средство для идентификации первого профиля, который находится вблизи первого местоположения, причем первая сжатая порция является порцией для первого профиля; и

средство для идентификации области, содержащей первое местоположение и являющейся одной из множества областей Цифровой модели рельефа.