Способ и устройство сжатия с использованием подхода на основе нейронной сети

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

 

Область техники, к которой относится изобретение

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

Уровень техники

Сжатие и сохранение объемных данных свойственны системам, используемым для 3D-моделирования, машинного распознавания образов и роботизированных применений. В уровне техники известны три основных подхода для сжатия и сохранения объемных данных: 1) воксельное представление в линейной памяти (RAM, флэш-память и т.д.); 2) сжатие данных без потерь с использованием иерархических структур данных; и 3) сжатие данных с потерями.

Воксельное представление в линейной памяти применяется, когда вычислительная эффективность систем имеет важное значение. В этом случае данные сохраняются в памяти без какой-либо модификации, т.е. в исходном виде. Воксель представляет собой один элемент или точку данных на регулярно разнесенной трехмерной сетке. Эта точка данных может состоять из одного компонента данных, например непрозрачность, или множества компонентов данных, например цвет вдобавок к непрозрачности. Воксель представляет только одну точку на этой сетке, а не объем; пространство между каждым вокселем не отображается в наборе данных, основанном на вокселях. Пример восксельного представления описан в документе US 8,587,583 B2. Недостаток воксельного представления состоит в том, что этот подход требует запоминающие устройства с большой емкостью в случае большого количества объемных данных. Кроме того, 3D-вид обычно содержит много пустого пространства, и «прямолинейное» воксельное представление может быть затратным с точки зрения использования ресурсов памяти.

Чтобы снизить затраты ресурсов памяти, можно сжимать объемные данные. Для сжатия данных без потерь используются различные иерархические структуры данных наподобие дерева данных. Пустые пространства кодируются с намного меньшим разрешением, чем пространства с объектами, и это снижает требуемый размер данных. Наиболее используемым типом такого подхода является дерево октантов - структура данных, в которой каждый внутренний узел имеет ровно восемь потомков. Каждый узел в дереве октантов подразделяет пространство, которое он характеризует, на восемь октантов. Пример сжатия данных без потерь описан в документе US 4,694,404 A. Этот подход имеет такой недостаток, что представление данных с использованием дерева октантов требует дополнительных вычислительных затрат для упаковки/распаковки данных.

Сжатие данных с потерями часто приводит к лучшим коэффициентам сжатия, чем сжатие данных без потерь, поскольку некоторые исходные данные могут быть отброшены. Для сжатия данных с потерями определяются либо доминирующие признаки исходных данных, либо их компактное представление в других базисах. Количество и тип отбрасываемой информации диктуются метрикой выбора в алгоритме сжатия. Пример схемы сжатия данных с потерями описан в документе US 2013/0159263 A1. Этот документ раскрывает способ, предусматривающий разреженное представление входного вектора данных b∈R^m, используя переполненный словарь базисных векторов A∈R^mxn. В частности, учитывая словарную матрицу с m<n, представляет интерес найти x∈Rⁿ так, чтобы Ax=b. Существует множество таких решений для x, и принцип состоит в том, чтобы выбрать решение, которое является самым «разреженным». Следует отметить, что пока x имеет высокую размерность, A может быть выбрано так, чтобы x имел очень мало ненулевых элементов, и, следовательно, x может быть сохранен эффективным образом. В документе US 2013/0159263 A1 распределенного алгоритма по Брегману используется для решения задачи оптимизации нахождения самого «разреженного» решения для x. Этот подход также требует значительных вычислительных затрат для обработки данных, в особенности для выполнения распределенного алгоритма по Брегману.

Другой способ нахождения решения для x основан на подходе с использованием нейронной сети, описанный в документе US 4,193,115 A. В этом случае для множества входных переменных предусмотрены управляющие функции, которые вычислены в отношении данных, хранящихся в памяти. Каждое значение управляющих функций распределяется по разным физическим адресам памяти, так что линейная сумма содержимого этих физических адресов определяет это значение. Используется алгоритм адресации, в котором входные переменные отображаются в набор значений промежуточного отображения. Устройство для выполнения промежуточного отображения содержит первый и второй счетчики, которые используются для адресации памяти, хранящей промежуточные переменные заданным образом. Тем не менее решение, предложенное в документе US 4,193,115 A, также требует значительных вычислительных затрат для сжатия данных.

Раскрытие изобретения

Задача настоящего изобретения заключается в устранении вышеупомянутых недостатков, присущих решениям, известным из уровня техники.

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

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

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

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

Краткое описание чертежей

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

Фиг. 1 иллюстрирует устройство сжатия данных в соответствии с одним примером варианта осуществления настоящего изобретения;

Фиг. 2 показывает объемное представление ассоциативной памяти, показанной на Фиг. 1;

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

Фиг. 4 показывает пример использования способа с Фиг. 3 относительно синусоидальной функции.

Осуществление изобретения

Различные варианты осуществления настоящего изобретения описаны далее более подробно со ссылкой на сопроводительные чертежи. Однако настоящее изобретение может быть реализовано во многих других формах и не должно восприниматься как ограниченное какой-либо конкретной структурой или функцией, представленной в нижеследующем описании. Напротив, эти варианты осуществления предоставлены для того, чтобы сделать описание настоящего изобретения подробным и полным. Исходя из настоящего описания специалисту в данной области техники будет очевидно, что объем настоящего изобретения охватывает любой вариант осуществления настоящего изобретения, который раскрыт в данном документе, вне зависимости от того, реализован ли этот вариант осуществления независимо или совместно с любым другим вариантом осуществления настоящего изобретения. Например, способ и устройство, раскрытые в данном документе, могут быть реализованы на практике посредством использования любого числа вариантов осуществления, представленных в данном документе. Кроме того, должно быть понятно, что любой вариант осуществления настоящего изобретения может быть реализован с использованием одного или более этапов или элементов, представленных в приложенной формуле изобретения.

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

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

Принцип функционирования CMAC обычно используется в задачах управления и распознавания. В отличие от этого, согласно настоящему изобретению, CMAC применяется для обеспечения сжатия объемных данных. Эта идея пришла в головы авторов при реализации алгоритмов реконструкции 3D данных, учитывая, что традиционное воксельное представление является слишком затратным по памяти, а использование деревьев октантов увеличивает вычислительные затраты и усложняет сами алгоритмы (так что эти алгоритмы не могут функционировать в режиме реального времени). Подход, предложенный в данном документе, является эффективным способом сжатия данных (не только двух- или трехмерных данных, но также данных бóльших размерностей) посредством использования малых вычислительных затрат по сравнению со способами, известными из уровня техники.

Фиг. 1 иллюстрирует устройство 100 сжатия данных, использующее подход на основе нейронной сети, в соответствии с одним примером варианта осуществления настоящего изобретения. Как показано, устройство 100 содержит контроллер 102 памяти, ассоциативную память 104, сумматор 106, вычитатель 108 и переключатель 110. Устройство 100 может функционировать в двух режимах, а именно: режиме обучения и режиме вывода. Следует отметить, что каждый из контроллера 102, сумматора 106, вычитателя 108 и переключателя 110 может быть реализован в виде одного или более процессоров.

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

Перед тем как устройство 100 начинает сжатие данных, пространство входных данных (например, являющееся трехмерным) разделяется на множество точек или элементов данных любых подходящих форм. Каждый элемент данных имеет координатный вектор X[n], задающий его положение в пространстве входных данных, и вектор V[n] объемных значений, определяющий его объемные значения в пространстве входных данных. В частности, объемные значения элементов данных представляют собой значения, характеризующие свойства элементов данных в пространстве входных данных. В качестве примера, эти свойства элементов данных могут включать в себя цвет, степень непрозрачности или их комбинацию.

В режиме обучения, когда элементы данных записываются в память 104, переключатель 110 находится в включенном состоянии. В этом случае контроллер 102 памяти вычисляет подходящие адреса памяти в памяти 104, используя вектора X[n] элементов данных. Другими словами, упомянутая адресация означает, что контроллер 102 памяти связывает элементы данных с соответствующими ячейками памяти 104. Каждая из ячеек памяти 104 хранит весовое значение. Далее память 104 выводит все весовые значения, которые соответствуют ячейкам, связанным с элементами данных. Сумматор 106 суммирует весовые значения для формирования весового вектора W[n] и предоставляет весовой вектор вычитателю 108. Вычитатель 108 вычитает весовой вектор из вектора V[n] для формирования сигнала ε[n] ошибки. Сигнал ошибки используется для регулировки требуемых весовых значений в ячейках памяти 104.

В частности, контроллер 102 памяти вычисляет адреса ячеек в памяти 104, используя базисный вектор A[n], получаемый с помощью следующей формулы:

(1)

где a_k[n] - k-ый элемент базисного вектора A[n] для n-го момента времени, µ_l - l-ое размерное значение ассоциативной памяти, N - размерность вектора X[n], ρ - параметр нейронной сети, x_j[n] - j-ый элемент вектора X[n], , M_i - размерное значение вдоль i-ой оси.

Кроме того, сигнал ошибки регулирует требуемые весовые значения ячеек в памяти 104 в соответствии с формулой:

(2)

В режиме вывода, когда элементы данных считываются из памяти 104, переключатель 110 находится в выключенном состоянии. В этом случае, в отличие от режима обучения, нет сигнала ошибки, передаваемого посредством обратной связи и регулирующего весовые коэффициенты ячеек в памяти 104, и сумма весовых значений, т.е. вектор W[n], используется для вычисления вектора сжатых объемных значений, который затем выводится.

Более конкретно, вектор X[n] поступает на вход контроллера 102 памяти, в котором выходной вектор A[n] вычисляется с использованием формулы (1). Используя вектор A[n], осуществляют связывание элементов данных с ячейками памяти 104. Память 104 выводит весовые значения ячеек сумматору 103. Сумматор 103 суммирует все весовые значения для формирования вектора W[n]. После этого сумматор 103 использует вектор W[n] для формирования вектора сжатых объемных значений следующим образом:

(3)

Фиг. 2 поясняет объемное представление памяти 104 на Фиг. 1 для примера трехмерных объемных данных. Если размерные значения для осей x, y, z равны M_x, M_y, M_z соответственно, тогда общий объем памяти равен M_x×M_y×M_z. Согласно подходу CMAC, соответствующая ассоциативная память может быть представлена в виде набора ρ трехмерных объемов с размерными значениями для осей x, y, z, равными µ_x=M_x/ρ, µ_y=M_y/ρ, µ_z=M_z/ρ соответственно. При этом общий объем ассоциативной памяти равен µ_x×µ_y×µ_z×ρ=(M_x/ρ)×(M_y/ρ)×(M_z/ρ)×ρ. Следовательно, для трехмерного случая мы имеем выигрыш по памяти в виде ρ². В общем случае для k-размерных объемных данных и параметра ρ нейронной сети, выигрыш по памяти равен ρ^k-1.

Фиг. 3 иллюстрирует способ 300 сжатия данных, использующий подход на основе нейронной сети, в соответствии с одним примером варианта осуществления настоящего изобретения. Способ 300 выполняется устройством 100, показанным на Фиг. 1. Способ содержит следующие этапы:

Этап 302: Пространство входных данных разделяется на элементы данных, как пояснено выше, т.е. каждый элемент данных обеспечивается векторами X[n] и V[n]. Такое разделение может выполняться одним или более внешними процессорами. В некоторых вариантах осуществления эти процессоры могут быть интегрированы в устройство 100.

Этап 304: Здесь, используя координатные векторы X[n], с помощью формулы (1) определяют адреса ячеек в ассоциативной памяти 104, с которыми должны быть связаны элементы данных.

Этап 306: Связывают элементы данных с ячейками в ассоциативной памяти 104 на основе определенных адресов.

Этап 308: Все весовые значения ячеек, связанных с элементами данных, суммируются сумматором 106 для получения весового вектора W[n].

Этап 310: Весовой вектор W[n] вычитают из вектора V[n] объемных значений для формирования сигнала ε[n] ошибки.

Этап 312: Здесь проверяют, является ли сигнал ошибки ненулевым. Если сигнал ошибки является ненулевым, способ переходит к этапу 314, и к этапу 316 в противном случае.

Этап 314: Определяют, что сигнал ошибки является ненулевым. Тогда сигнал ошибки предоставляют ассоциативной памяти 104 для регулировки весовых значений ячеек, связанных с элементами данных, на основе сигнала ошибки (в соответствии с формулой (2)).

Этап 316: Определяют, что сигнал ошибки является нулевым. Тогда вычисляют вектор сжатых объемных значений с помощью сумматора 106, используя формулу (3), и выводят его.

Следует отметить, что сигнал ошибки возникает, т.е. ε[n] не равно нулю, в случае каких-либо изменений вектора X[n]. Если вектор X[n] не изменяется (что соответствует неизмененному вектору V[n]), сигнал ошибки отсутствует, и режим обучения не требуется. Такие изменения могут включать в себя смену положения элемента данных, которая приводит к новому вектору X[n] и, следовательно, новому вектору V[n].

Фиг. 4а-е показывают результаты сжатия данных, например, для синусоидальной функции в соответствии со способом 300, выполняемым в устройстве 100. В частности, пример сжатия двумерных данных проиллюстрирован для случая параметра нейронной сети ρ=4. В действительности, имеется четырехслойная нейронная сеть (k - номер слоя). Когда k меняется с 1 до 4, можно видеть, как сжатые данные сохраняются или отображаются в каждом из слоев (Фиг. 4а-d). Каждый из слоев соответствует соответствующей одной или более ячейкам в памяти 104. Суммируя сжатые данные во всех слоях, можно получить функцию, близкую к исходной синусоидальной функции, показанной на Фиг.4е.

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

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

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

2. Способ по п. 1, в котором упомянутый этап определения содержит этап, на котором:
определяют адреса ячеек в ассоциативной памяти посредством использования базисного вектора А[n], полученного с помощью следующей формулы:

где a_k[n] - k-й элемент базисного вектора A[n] для n-го момента времени, µ_l - l-е размерное значение ассоциативной памяти, N - размерность координатного вектора X[n], ρ - параметр нейронной сети, x_j[n] - j-й элемент координатного вектора X[n],
, M_i - размерное значение вдоль i-й оси.

3. Способ по п. 1, в котором весовые значения ячеек, связанных с элементами данных, регулируют с использованием следующей формулы:
,
где W[n] - весовой вектор для n-го момента времени, X[n] - координатный вектор для n-го момента времени, V[n] - вектор объемных значений для n-го момента времени, A - базисный вектор.

4. Способ по п. 1, в котором вектор сжатых объемных значений вычисляют с использованием следующей формулы:
,
где w_i[n-1] - i-й элемент весового вектора W[n] для (n-1)-го момента времени.

5. Способ по п. 1, в котором свойства элементов данных включают в себя цвет, степень непрозрачности или их комбинацию.

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