Шестиугольная эффективная система координат

Шестиугольная эффективная система координат ( HECS ), ранее известная как адресация набора массивов ( ASA ), представляет собой систему координат для шестиугольных сеток , которая позволяет эффективно хранить и обрабатывать изображения с гексагональной выборкой в цифровых системах . HECS представляет гексагональную сетку как набор двух чередующихся прямоугольных подмассивов, к которым можно обращаться с помощью обычных целочисленных координат строк и столбцов и которые различаются одной двоичной координатой. Шестиугольная выборка является оптимальным подходом для с изотропным ограничением полосы пропускания. двумерных сигналов ^[1] выборки и его использование обеспечивает повышение эффективности на 13,4% по сравнению с прямоугольной выборкой. Система HECS позволяет использовать гексагональную выборку для приложений цифрового изображения , не требуя значительной дополнительной обработки для обработки гексагональной матрицы. ^[2]

Фон

Преимущества выборки по шестиугольной сетке вместо стандартной прямоугольной сетки для приложений цифрового изображения включают в себя: более эффективную выборку, постоянную связность, равноудаленные соседние пиксели , большее угловое разрешение и более высокую круговую симметрию. ^[3]^[4]^[5] Иногда несколько из этих преимуществ объединяются, тем самым увеличивая эффективность вычислений и хранения на 50% по сравнению с прямоугольной выборкой. ^[6] Исследователи показали ^[1]^[6]^[7] что гексагональная сетка является оптимальной решеткой дискретизации, и ее использование обеспечивает повышение эффективности дискретизации на 13,4% по сравнению с прямоугольной дискретизацией для двумерных сигналов с изотропно-ограниченной полосой пропускания. Несмотря на все эти преимущества гексагональной выборки по сравнению с прямоугольной, ее применение до внедрения HECS было ограничено из-за отсутствия эффективной системы координат . ^[8]

Шестиугольная эффективная система координат

Описание

Представление данных с гексагональной выборкой в виде пары прямоугольных массивов с использованием системы координат HECS.

Шестиугольная эффективная система координат (HECS) основана на идее представления шестиугольной сетки как набора двух прямоугольных массивов , которые можно индивидуально индексировать с использованием знакомых целочисленных индексов строк и столбцов. Массивы различаются по одной двоичной координате, так что полный адрес любой точки шестиугольной сетки однозначно представлен тремя координатами. ^[9]

(a,r,c)\in \{0,1\}\times \mathbb {Z} \times \mathbb {Z}

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

Ближайшие соседи

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

Преобразовать в декартову систему

Преобразование координат в HECS в их декартовы аналоги выполняется простым умножением матриц.

{\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}{\frac {1}{2}}&0&1\\{\frac {\sqrt {3}}{2}}&{\sqrt {3}}&0\end{bmatrix}}{\begin{bmatrix}a\\r\\c\end{bmatrix}}={\begin{bmatrix}{\frac {a}{2}}+c\\({\sqrt {3}})({\frac {a}{2}}+r)\end{bmatrix}}.

Операторы

Предварительные сведения

Пусть набор всех возможных адресов HECS будет ${\text{HECS}}=\{0,1\}\times \mathbb {Z} \times \mathbb {Z} .$

\mathbf {p} _{i}={\begin{bmatrix}a_{i}\\r_{i}\\c_{i}\end{bmatrix}}\in {\text{HECS}}.

\mathbf {p} ={\begin{bmatrix}a\\r\\c\end{bmatrix}}\in {\text{HECS}}.

k\in \mathbb {N} .

Добавление

Оператор двоичного сложения $({\text{HECS}},+)$ был определен как

\mathbf {p} _{1}+\mathbf {p} _{2}={\begin{bmatrix}a_{1}\oplus a_{2}\\r_{1}+r_{2}+(a_{1}\land a_{2})\\c_{1}+c_{2}+(a_{1}\land a_{2})\end{bmatrix}},

где $\oplus$ является логическим оператором XOR и $\land$ является логическим И. оператором

Отрицание

Унарный оператор отрицания $({\text{HECS}},-)$ был определен как

-\mathbf {p} ={\begin{bmatrix}a\\-r-a\\-c-a\end{bmatrix}}.

Вычитание

Бинарный оператор вычитания $({\text{HECS}},-)$ было определено путем объединения операций отрицания и сложения как

\mathbf {p} _{1}-\mathbf {p} _{2}=\mathbf {p} _{1}+(-\mathbf {p} _{2}).

Скалярное умножение

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

k\mathbf {p} ={\begin{bmatrix}(ak){\bmod {2}}\\kr+(a)\left\lfloor {\frac {k}{2}}\right\rfloor \\kc+(a)\left\lfloor {\frac {k}{2}}\right\rfloor \end{bmatrix}},

и

-k\mathbf {p} =k(-\mathbf {p} ).

Сепарабельное ядро Фурье

Шестиугольное дискретное преобразование Фурье (HDFT) было разработано Мерсеро. ^[6] и был преобразован в представление HECS компанией Rummelt. ^[2] Позволять $x(a,r,c)$ быть двумерным сигналом с шестиугольной выборкой и пусть оба массива имеют размер $n\times m$ . Позволять $X(b,s,d)$ быть Фурье преобразованием x. Уравнение HDFT для прямого преобразования имеет вид

X(b,s,d)=\sum _{a}\sum _{r}\sum _{c}x(a,r,c)\exp \left[-j\pi \left({\frac {(a+2c)(b+2d)}{2m}}+{\frac {(a+2r)(b+2s)}{n}}\right)\right]

Обратите внимание, что HECS-представление HDFT преодолевает «непреодолимую трудность» Мерсеро, поскольку оно представляет собой отделимое ядро, что привело к разработке гексагонального быстрого преобразования Фурье . ^[10]

Альтернативные схемы адресации

Было предпринято несколько попыток разработать эффективные системы координат для гексагональной сетки. Снайдер ^[4] описывает систему координат, основанную на неортогональных базисах, которая называется системой h2 . Ее ^[11] разработал интересную трехкоординатную систему, использующую наклонную плоскость в трехмерном пространстве. По разным причинам оба этих подхода требуют громоздких машинных представлений, что приводит к неэффективным операциям обработки изображений. ^[8] Обобщенная сбалансированная троичная система (GBT) основана на иерархии ячеек, где на каждом уровне каждая ячейка представляет собой совокупность ячеек предыдущего уровня. ^[12] В двумерных измерениях GBT можно использовать для адресации шестиугольной сетки, где каждая точка сетки адресуется строкой цифр по основанию 7, и каждая цифра указывает положение шестиугольника на этом уровне иерархии. ^[13] Использование GBT и слегка модифицированных версий GBT, таких как HIP. ^[14] и спиральная архитектура ^[15] В литературе имеется множество методов решения гексагональных сеток в двух измерениях. ^[5]^[14]^[15]^[16] Хотя эти подходы обладают некоторыми интересными математическими свойствами, они не являются удобными и эффективными для обработки изображений. ^[8]

Другие приложения для двумерной шестиугольной сетки

Хотя HECS был разработан в основном для цифровой обработки изображений с гексагональной выборкой, его преимущества распространяются и на другие приложения, такие как поиск кратчайшего пути и маршрутизация по кратчайшему пути между точками в гексагональных межсетевых сетях. ^[8] Для таких приложений были разработаны другие подходы к адресации. ^[17]^[18]^[19] но они страдают теми же недостатками, что и описанные выше. ^[8]

Ссылки

^ Jump up to: ^а ^б Петерсен, Дэниел П.; Миддлтон, Дэвид (декабрь 1962 г.). «Выборка и реконструкция функций с ограниченным волновым числом в N-мерных евклидовых пространствах» . Информация и контроль . 5 (4): 279–323. дои : 10.1016/S0019-9958(62)90633-2 .
^ Jump up to: ^а ^б Раммельт, Николай I. (2010). Адресация набора массивов: обеспечение эффективной обработки изображений с гексагональной выборкой (кандидатская диссертация). Университет Флориды.
^ Сянцзянь Хэ; Вэньцзин Цзя (27–28 августа 2005 г.). Шестиугольная структура для интеллектуального зрения . 2005 Международная конференция по информационным и коммуникационным технологиям. IEEE. стр. 52–64. дои : 10.1109/ICICT.2005.1598543 . hdl : 10453/2661 . ISBN 978-0-7803-9421-6 .
^ Jump up to: ^а ^б Снайдер, Уэсли Э.; Ци, Хайронг; Сандер, Уильям А. (21 мая 1999 г.). Хэнсон, Кеннет М. (ред.). Система координат для шестиугольных пикселей . Медицинская визуализация 1999: Обработка изображений. Том. 3661. ШПИОН . стр. 716–727. дои : 10.1117/12.348629 .
^ Jump up to: ^а ^б ван Россель, Ян В. (1988). «Преобразование декартовых координат из и в обобщенные сбалансированные троичные адреса» (PDF) . Фотограмметрическая техника и дистанционное зондирование . 54 : 1565–1570.
^ Jump up to: ^а ^б ^с Мерсеро, РМ (июнь 1979 г.). «Обработка двумерных сигналов с шестиугольной выборкой» . Труды IEEE . 67 (6): 930–949. дои : 10.1109/PROC.1979.11356 . ISSN 0018-9219 .
^ Витулли Р.; Дель Белло, У.; Армбрустер, П.; Баронти, С.; Сантурти, Л. (24–28 июня 2002 г.). Уменьшение эффектов псевдонимов за счет оптимизированных сеток выборки и влияния на цепочки получения изображений . Международный симпозиум IEEE по геонаукам и дистанционному зондированию (IGARSS). Том. 2. ИИЭР. стр. 979–981. дои : 10.1109/IGARSS.2002.1025749 . ISBN 978-0-7803-7536-9 .
^ Jump up to: ^а ^б ^с ^д ^и Раммельт, Николай I; Уилсон, Джозеф Н. (1 апреля 2011 г.). «Адресация набора массивов: технология эффективной обработки изображений с гексагональной выборкой» . Журнал электронных изображений . 20 (2): 023012–023012–11. Бибкод : 2011JEI....20b3012R . дои : 10.1117/1.3589306 . ISSN 1017-9909 .
^ Патент США 8797436 , Раммельт, Николас И., «Адресация набора массивов (ASA) для шестиугольно расположенных элементов выборки данных», выдан 5 августа 2014 г. В данную статью включен текст из этого источника, находящегося в свободном доступе .
^ Бердсонг, Джеймс Б.; Раммельт, Николай I. (25–28 сентября 2016 г.). Шестиугольное быстрое преобразование Фурье . Международная конференция IEEE по обработке изображений (ICIP). IEEE. стр. 1809–1812. дои : 10.1109/ICIP.2016.7532670 . ISBN 978-1-4673-9961-6 .
^ I. Her, «Симметричная система координат на гексагональной сетке для компьютерной графики и зрения», J. Mech. Дез. 115, 447–449 (1993)
^ Д. Лукас и Л. Гибсон, «Система иерархической адресации в евклидовом пространстве», Interactive Systems Corporation (1980).
^ Л. Гибсон и К. Ленцмайер, «Система извлечения иерархических шаблонов для изображений с гексагональной выборкой», Tech. Представитель, Заключительный отчет по контракту F49620-81-C-0039, Управление научных исследований ВВС США, Interactive Systems Corporation (1981)
^ Jump up to: ^а ^б Л. Миддлтон и Дж. Сивасвами, Обработка гексагональных изображений: практический подход (Springer, Лондон, 2005 г.)
^ Jump up to: ^а ^б П. Шеридан, «Спиральная архитектура для машинного зрения», доктор философии. диссертация, ун. технологий Сидней (1996)
^ А. Винс и X. Чжэн, «Вычисление дискретного преобразования Фурье на гексагональной решетке», J. Math. Imaging Vision 28, 125–133 (2007)
^ Карл, Дж.; Мёпо, Дж. Ф. (14–17 мая 2000 г.). Топологические свойства и алгоритмы оптимальной маршрутизации трехмерных гексагональных сетей . Четвертая международная конференция по высокопроизводительным вычислениям в Азиатско-Тихоокеанском регионе. Том. 1. ИИЭР. С. 116–121 т.1. дои : 10.1109/HPC.2000.846530 .
^ Гарсиа Носетти, Ф.; Стойменович И.; Цзинъюань Чжан (сентябрь 2002 г.). «Адресация и маршрутизация в шестиугольных сетях с приложениями для отслеживания мобильных пользователей и перемаршрутизации соединений в сотовых сетях» . Транзакции IEEE в параллельных и распределенных системах . 13 (9): 963–971. дои : 10.1109/TPDS.2002.1036069 . ISSN 1045-9219 .
^ М. Хе и В. Сяо, «Единая схема адресации для гексагональных и сотовых сетей с изоморфными графами Кэли», в Proc. 1-й Межд. Мультисим. по компьютерным и вычислительным наукам (IMSCCS '06), Vol. 1, стр. 363–368 (2006).

[Petersen62-1] Jump up to: ^а ^б Петерсен, Дэниел П.; Миддлтон, Дэвид (декабрь 1962 г.). «Выборка и реконструкция функций с ограниченным волновым числом в N-мерных евклидовых пространствах» . Информация и контроль . 5 (4): 279–323. дои : 10.1016/S0019-9958(62)90633-2 .

[Rummelt10-2] Jump up to: ^а ^б Раммельт, Николай I. (2010). Адресация набора массивов: обеспечение эффективной обработки изображений с гексагональной выборкой (кандидатская диссертация). Университет Флориды.

[He05-3] Сянцзянь Хэ; Вэньцзин Цзя (27–28 августа 2005 г.). Шестиугольная структура для интеллектуального зрения . 2005 Международная конференция по информационным и коммуникационным технологиям. IEEE. стр. 52–64. дои : 10.1109/ICICT.2005.1598543 . hdl : 10453/2661 . ISBN 978-0-7803-9421-6 .

[Snyder99-4] Jump up to: ^а ^б Снайдер, Уэсли Э.; Ци, Хайронг; Сандер, Уильям А. (21 мая 1999 г.). Хэнсон, Кеннет М. (ред.). Система координат для шестиугольных пикселей . Медицинская визуализация 1999: Обработка изображений. Том. 3661. ШПИОН . стр. 716–727. дои : 10.1117/12.348629 .

[vanRoessel88-5] Jump up to: ^а ^б ван Россель, Ян В. (1988). «Преобразование декартовых координат из и в обобщенные сбалансированные троичные адреса» (PDF) . Фотограмметрическая техника и дистанционное зондирование . 54 : 1565–1570.

[Mersereau79-6] Jump up to: ^а ^б ^с Мерсеро, РМ (июнь 1979 г.). «Обработка двумерных сигналов с шестиугольной выборкой» . Труды IEEE . 67 (6): 930–949. дои : 10.1109/PROC.1979.11356 . ISSN 0018-9219 .

[Vitulli02-7] Витулли Р.; Дель Белло, У.; Армбрустер, П.; Баронти, С.; Сантурти, Л. (24–28 июня 2002 г.). Уменьшение эффектов псевдонимов за счет оптимизированных сеток выборки и влияния на цепочки получения изображений . Международный симпозиум IEEE по геонаукам и дистанционному зондированию (IGARSS). Том. 2. ИИЭР. стр. 979–981. дои : 10.1109/IGARSS.2002.1025749 . ISBN 978-0-7803-7536-9 .

[Rummelt11-8] Jump up to: ^а ^б ^с ^д ^и Раммельт, Николай I; Уилсон, Джозеф Н. (1 апреля 2011 г.). «Адресация набора массивов: технология эффективной обработки изображений с гексагональной выборкой» . Журнал электронных изображений . 20 (2): 023012–023012–11. Бибкод : 2011JEI....20b3012R . дои : 10.1117/1.3589306 . ISSN 1017-9909 .

[patent-9] Патент США 8797436 , Раммельт, Николас И., «Адресация набора массивов (ASA) для шестиугольно расположенных элементов выборки данных», выдан 5 августа 2014 г. В данную статью включен текст из этого источника, находящегося в свободном доступе .

[Birdsong16-10] Бердсонг, Джеймс Б.; Раммельт, Николай I. (25–28 сентября 2016 г.). Шестиугольное быстрое преобразование Фурье . Международная конференция IEEE по обработке изображений (ICIP). IEEE. стр. 1809–1812. дои : 10.1109/ICIP.2016.7532670 . ISBN 978-1-4673-9961-6 .

[Her93-11] I. Her, «Симметричная система координат на гексагональной сетке для компьютерной графики и зрения», J. Mech. Дез. 115, 447–449 (1993)

[Lucas80-12] Д. Лукас и Л. Гибсон, «Система иерархической адресации в евклидовом пространстве», Interactive Systems Corporation (1980).

[Gibson81-13] Л. Гибсон и К. Ленцмайер, «Система извлечения иерархических шаблонов для изображений с гексагональной выборкой», Tech. Представитель, Заключительный отчет по контракту F49620-81-C-0039, Управление научных исследований ВВС США, Interactive Systems Corporation (1981)

[Middleton05-14] Jump up to: ^а ^б Л. Миддлтон и Дж. Сивасвами, Обработка гексагональных изображений: практический подход (Springer, Лондон, 2005 г.)

[Sheridan96-15] Jump up to: ^а ^б П. Шеридан, «Спиральная архитектура для машинного зрения», доктор философии. диссертация, ун. технологий Сидней (1996)

[Vince07-16] А. Винс и X. Чжэн, «Вычисление дискретного преобразования Фурье на гексагональной решетке», J. Math. Imaging Vision 28, 125–133 (2007)

[Carle00-17] Карл, Дж.; Мёпо, Дж. Ф. (14–17 мая 2000 г.). Топологические свойства и алгоритмы оптимальной маршрутизации трехмерных гексагональных сетей . Четвертая международная конференция по высокопроизводительным вычислениям в Азиатско-Тихоокеанском регионе. Том. 1. ИИЭР. С. 116–121 т.1. дои : 10.1109/HPC.2000.846530 .

[Nocetti02-18] Гарсиа Носетти, Ф.; Стойменович И.; Цзинъюань Чжан (сентябрь 2002 г.). «Адресация и маршрутизация в шестиугольных сетях с приложениями для отслеживания мобильных пользователей и перемаршрутизации соединений в сотовых сетях» . Транзакции IEEE в параллельных и распределенных системах . 13 (9): 963–971. дои : 10.1109/TPDS.2002.1036069 . ISSN 1045-9219 .

[He06-19] М. Хе и В. Сяо, «Единая схема адресации для гексагональных и сотовых сетей с изоморфными графами Кэли», в Proc. 1-й Межд. Мультисим. по компьютерным и вычислительным наукам (IMSCCS '06), Vol. 1, стр. 363–368 (2006).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

Фон