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

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

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

фиг.2 представляет собой блок-схему устройства для формирования дескрипторов признаков в соответствии с вариантами осуществления настоящего изобретения;

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

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

фиг.5а и 5b представляют совместное распределение градиентов x, y для большого количества ячеек и кривые контуров совместного распределения градиентов x, y, соответственно;

фиг.6a-6d представляют распределение градиентов x, y для четырех различных отдельных ячеек, которые объединены потенциально с распределениями других ячеек, так чтобы включать совместное распределение градиентов x, y, показанное на фиг.5а;

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

фиг.8 изображает рабочие характеристики приемника для аппроксимаций, обеспечиваемых четырьмя различными конфигурациями столбцов гистограммы, показанными на фиг 7a-7d, в соответствии с вариантами осуществления настоящего изобретения, в сравнении с аппроксимацией, полученной посредством масштабно-инвариантного преобразования признаков (SIFT, scale invariant feature transform).

фиг.9а представляет распределение градиентов для ячейки, а фиг.9b изображает гистограммы градиентов для распределения, показанного на фиг.9а, в несжатой форме, и последующее древовидное кодирование по методу Гаджи и Хаффмана в соответствии с вариантами осуществления настоящего изобретения.

фиг.10 представляет изображение деревьев Гаджи и деревьев Хаффмана, которые могут быть сформированы с четырьмя листьями;

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

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

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

На фиг.1 изображена система, в которой возможно эффективное применение вариантов осуществления настоящего изобретения. Как показано на чертеже, система включает один или более терминалов 10 связи, которые могут осуществлять связь друг с другом и с различными сетевыми объектами по сети 12. Несмотря на то что в настоящем описании варианты осуществления терминала связи проиллюстрированы и описаны для примера, варианты осуществления настоящего изобретения могут быть применены и в других типах терминалов, например, персональных цифровых помощниках (portable digital assistants, PDA), пейджерах, мобильных телевизорах, мобильных телефонах, игровых устройствах, портативных компьютерах, фотоаппаратах, видеомагнитофонах, аудио/видеоплеерах, радиоприемниках, устройствах глобальной системы позиционирования (global position system, GPS) или любой комбинации выше перечисленного, а также в других типах голосовых или текстовых систем связи. Кроме того, варианты осуществления настоящего изобретения могут применяться в терминалах связи, не являющихся мобильными. Дополнительно, упомянутая сеть может быть проводной или беспроводной сетью любого типа, сконфигурированной для поддержки связи между различными терминалами связи и различными сетевыми объектами. Например, сеть может включать набор различных узлов, устройств или функций, таких как сервер 14 приложений, которые могут быть связаны друг с другом посредством соответствующих проводных и/или беспроводных интерфейсов. В некоторых вариантах осуществления изобретения, но не обязательно, сеть может быть способна поддерживать связь в соответствии с одним или более протоколами связи первого поколения (first generation, 1G), второго поколения (second generation, 2G), поколения 2.5G, третьего поколения (third-generation, 3G), поколения 3.5G, поколения 3.9G, четвертого поколения (fourth-generation, 4G), долгосрочной эволюции (long-term evolution, LTE) и/или им аналогичными. В соответствии с одним из вариантов осуществления настоящего изобретения терминал 10 связи может захватывать изображение, например, изображение мемориальной церкви на изображении, показанном на фиг.1. В соответствии с дальнейшим описанием, терминал связи в этом варианте осуществления изобретения может затем формировать и сжать набор дескрипторов признаков, представляющих различные признаки в этом изображении. Затем, терминал связи может передать сжатые дескрипторы признаков по сети 12 в сетевой объект, например, сервер 14 приложений, как показано на фиг.1. Сервер в данном варианте осуществления изобретения может затем сравнить сжатые дескрипторы признаков изображения, захваченного устройством связи, с базой данных сжатых дескрипторов признаков, представляющих различные заранее заданные признаки. Затем, сервер может идентифицировать заранее заданные признаки, которые имеют дескрипторы признаков, наиболее сходные с дескрипторами признаков изображения, захваченного терминалом связи,и, если дескрипторы признаков сходны в достаточной степени, сервер может идентифицировать, что признаки в изображении, например, здания, ориентиры и т.п., те же самые, что и заранее заданные признаки, хранимые в базе данных. Затем сервер может осуществить связь с терминалом связи для предоставления информации, идентифицирующей признак(-и) в изображении и, в некоторых случаях, может предоставлять дополнительную информацию, связанную с этим признаком(-ами), например, его название, адрес, историческую информацию, маркетинговую информацию и т.п.

Хотя терминал 10 связи может быть сконфигурирован различными способами, один из примеров терминала связи, допускающий эффективное применение настоящего изобретения, изображен в виде блок-схемы на фиг.2, иллюстрирующей мобильную станцию 20. Несмотря на то что в настоящем описании для примера проиллюстрирован и рассмотрен один из вариантов осуществления терминала связи, варианты осуществления настоящего изобретения могут быть применены и в терминалах других типов, например, персональных цифровых помощниках (PDA), пейджерах, мобильных телевизорах, игровых устройствах, компьютерах любых типов (например, портативных или мобильных компьютерах), фотоаппаратах, аудио/видеоплеерах, радиоприемниках, устройствах глобальной системы позиционирования (GPS) или любой комбинации вышеперечисленного. В соответствии с описанием, терминал связи может включать различные средства для выполнения одной или более функций согласно вариантам осуществления настоящего изобретения, включая показанные и рассмотренные более подробно в настоящем описании. Однако следует понимать, что терминал связи может включать альтернативные средства для выполнения одной или более аналогичных функций, не выходя за пределы объема настоящего изобретения.

Мобильная станция 20 проиллюстрированного варианта осуществления изобретения может включать антенну 32 (или множество антенн), функционально связанную с передатчиком 34 и приемником 36. Мобильная станция может также включать устройство, например процессор 40, который подает сигналы в передатчик и принимает сигналы от приемника. Упомянутые сигналы могут включать информации сигнализации в соответствии со стандартом радиоинтерфейса применяемой сотовой системы, и/или данные, соответствующие речи абонента, принимаемым данным или данным, формируемым абонентом. Для этого мобильная станция может быть способна работать с одним или более стандартами радиоинтерфейса, протоколами связи, типами модуляции и типами доступа. Например, мобильная станция может быть способна работать в соответствии с любым количеством протоколов связи первого, второго, третьего и/или четвертого поколения и/или аналогичными им. Например, мобильный терминал может быть способен работать в соответствии с протоколами беспроводной связи второго поколения (2G) IS-136, глобальной системы мобильной связи (Global System for Mobile communications, GSM) и IS-95, или с протоколами беспроводной связи третьего поколения (3G), такими как универсальная система мобильной связи (Universal Mobile Telecommunications System, UMTS), множественный доступ с кодовым разделением 2000 (Code Division Multiple Access 2000, CDMA 2000), широкополосный множественный доступ с кодовым разделением (Wideband Code Division Multiple Access, WCDMA), синхронный множественный доступ с кодовым и временным разделением (Time Division-Syncronous Code Division Multiple Access, TD-SCDMA), с таким протоколом беспроводной связи 3.9G как E-UTRAN (evolved-UMTS terrestrial radio access network, эволюционированная наземная сеть радиодоступа системы UMTS), с протоколами проводной связи четвертого поколения (4G) или им подобными.

Понятно, что упомянутое устройство, например процессор 40, может включать электронные схемы, реализующие, помимо прочего, звуковые и логические функции мобильной станции 20. Процессор может быть реализован различными путями. Например, процессор может быть выполнен в виде различных процессорных средств, например процессорного элемента, сопроцессора, контроллера, или различных других процессорных устройств, включая интегральные схемы, например специализированную интегральную схему (ASIC, Application Specific Integrated Circuit) или программируемую вентильную матрицу (FPGA, Field Programmable Gate Array), аппаратный ускоритель и/или аналогичные устройства. В одном из примеров осуществления изобретения процессор может быть сконфигурирован для выполнения инструкций, хранящихся в запоминающем устройстве или иным образом доступных для процессора. По существу, процессор может быть сконфигурирован для выполнения процедур (или по меньшей мере их части), рассмотренных далее более подробно в отношении фиг.4 и 12. Процессор может также включать функциональные возможности для сверточного кодирования и перемежения сообщений и данных перед модуляцией и передачей. Процессор может также включать внутренний голосовой кодер, а также внутренний модем данных.

Мобильная станция 20 может также содержать пользовательский интерфейс, включающий устройство вывода, например, наушник или громкоговоритель 44, вызывное устройство 42, микрофон 46, дисплей 48, а также интерфейс пользовательского ввода, которые могут быть соединены с процессором 40. Интерфейс пользовательского ввода, который позволяет мобильной станции принимать данные, может включать любое из ряда устройств, позволяющих мобильной станции принимать данные, например клавиатуру 50, сенсорный дисплей (не показан) или другие устройства ввода. В вариантах осуществления изобретения, включающих клавиатуру, она может включать цифровые клавиши (0-9) и связанные с ними клавиши (#, *), а также другие аппаратные и программируемые клавиши, используемые для управления мобильным терминалом 10. Альтернативно, клавиатура может иметь стандартную раскладку QWERTY. Клавиатура может также включать различные программируемые клавиши с соответствующими функциями. Дополнительно, или альтернативно, мобильная станция может включать интерфейсное устройство, такое как джойстик, или другой интерфейс пользовательского ввода. Мобильная станция может также включать аккумуляторную батарею 54, например вибрирующий батарейный блок для питания различных схем, используемых для управления мобильной станцией, а также, опционально, для обеспечения механической вибрации в качестве обнаруживаемого выходного сигнала.

Мобильная станция 20 может также включать модуль идентификации пользователя (user identity module, UIM) 58, который в общем случае называют смарт-картой. Модуль UIM может быть запоминающим устройством со встроенным процессором. UIM может включать, например, модуль идентификации абонента (subscriber identity module, SIM), универсальную карту на интегральных схемах (universal integrated circuit card, UICC), универсальный модуль идентификации абонента (universal subscriber identity module, USIM), съемный модуль идентификации пользователя (removable user identity module, R-UIM) или любую другую смарт-карту. Модуль UIM может хранить элементы информации, касающиеся мобильного абонента. В дополнение к модулю UIM мобильная станция может быть оснащена памятью. Например, мобильная станция может включать энергозависимую память 60, например, энергозависимую оперативную память (Random Access Memory, RAM), включающую область кэш для временного хранения данных. Мобильная станция может также включать другую, энергонезависимую, память 62, которая может быть встроенной и/или съемной. Энергонезависимая память может дополнительно или альтернативно включать электрически стираемую программируемую постоянную память (electrically erasable programmable read only memory, EEPROM), флеш-память или аналогичную. Память может хранить любое количество блоков информации и данных, которые могут быть использованы мобильной станцией для реализации ее функций. К примеру, память может включать идентификатор, например код международного идентификации мобильного оборудования (international mobile equipment identification, IMEI), способный осуществить уникальную идентификацию мобильной станции.

Тогда как терминал связи, один из примеров которого изображен на фиг.2, может формировать сжатые представления одного или более дескрипторов признаков в соответствии с вариантами осуществления настоящего изобретения, в сетевом объекте, например, в сервере 14 приложений или аналогичном ему устройстве, связанном с терминалом связи, могут также применяться варианты осуществления настоящего изобретения для идентификации признака(-ов) в изображении на основе анализа сжатых представлений упомянутых дескрипторов признаков. Например, на фиг.3 показана блок-схема сетевого объекта 68, способного функционировать в качестве сервера 14, или аналогичного ему устройства, в соответствии с одним из вариантов осуществления настоящего изобретения. Сетевой объект может включать различные средства для выполнения одной или более функций в соответствии с вариантами осуществления настоящего изобретения, включая более подробно проиллюстрированные и рассмотренные в настоящем описании функции. Однако следует понимать, что сетевой объект может включать альтернативные средства для выполнения одной или более подобных функций, не выходя за пределы объема настоящего изобретения.

Как показано на чертеже, сетевой объект 68 может включать средства, например, процессор 70 для выполнения различных функций сетевого объекта или управления ими. Процессор может быть реализован множеством различных способов. Например, процессор может быть выполнен в виде различных процессорных средств, таких как процессорный элемент, сопроцессор, контроллер, или различные другие процессорные устройства, включая, к примеру, ASIC, FPGA, аппаратный ускоритель и/или аналогичные устройства. В одном из примеров осуществления изобретения процессор может быть сконфигурирован для выполнения инструкций, хранящихся в памяти или иным образом доступных для процессора. По существу, процессор может быть сконфигурирован для выполнения процедур или по меньшей мере их части, рассмотренных далее более подробно в отношении фиг.12.

В одном из вариантов осуществления изобретения процессор 70 может быть связан или включать память 72, например, энергозависимую или энергонезависимую память, хранящую контент, данные и т.п. Например, память может хранить контент, переданный, от сетевого объекта и/или принимаемый им. Также, например, память может хранить программные приложения, инструкции и т.п., необходимые для выполнения процессором инструкций, связанных с функционированием сетевого объекта 68 в соответствии с вариантами осуществления настоящего изобретения. В частности, память может хранить программные приложения, инструкции и т.п., необходимые для выполнения процессором операций, описанных выше, а также далее по тексту в отношении фиг.12, для идентификации признака(-ов) в изображении на основе анализа сжатых представлений дескрипторов признаков.

В дополнение к памяти 72 процессор 70 может быть также соединен по меньшей мере с одним интерфейсом или другими средствами для передачи и/или приема данных, контента и т.п. С этой целью интерфейс(-ы) может включать по меньшей мере один интерфейс 74 связи или другие средства для передачи и/или приема данных, контента и т.п., например, между сетевым объектом 68 и терминалом 10 связи и/или между сетевым объектом и остальной сетью 12.

При функционировании, как показано на фиг.4, для представления признаков в изображении с помощью соответствующих дескрипторов признаков, терминал 10 связи и, в одном из вариантов осуществления изобретения, процессор 40 терминала связи, могут разделять изображение на множество участков, например, канонических участков, вокруг точки, представляющей интерес. См. операцию 80. Каждый участок может затем быть нормализован для обеспечения инвариантности при афинных изменениях яркости, например, посредством нормализации среднего и среднеквадратического отклонения пиксельных значений соответствующего участка для компенсации при афинном преобразовании al+b пиксельных яркостей I. См. операцию 82. Затем каждый участок может быть размыт или сглажен, например, в соответствии со сглаживанием по Гауссу с параметром сглаживания σ, например, равным 2.7 пикселей в одном из вариантов осуществления изобретения. Каждый участок может быть затем разделен на множество более мелких ячеек. См. операцию 84. В соответствии с последующим описанием, упомянутые ячейки могут быть различных размеров с применением методов масштабно-инвариантого преобразования признаков (scale invariant feature transform, SIFT) и ускоренного надежного обнаружения признаков (speeded up robust features, SURF), использующих конфигурации с квадратной сеткой 4×4, в то время как методы гистограммы положения и ориентации градиентов (gradient location and orientation histogram. GLOH) используют конфигурацию с большой полярной сеткой.

После разделения участков на более мелкие ячейки процессор 40 терминала связи 10 может определить градиенты x и y в каждой ячейке, например, с использованием центрированной производной маски [-1, 0, 1]. См. операцию 86 на фиг.4. Градиенты могут быть определены различным образом. Например, градиенты могут быть определены с помощью методов SIFT, в которых ориентацию градиентов внутри каждой ячейки квантуют в восемь битов, а значения градиентов по каждому направлению суммируют. Альтернативно, градиенты могут быть определены в соответствии с методом SURF, где дескриптор SURF включает ∑dx, ∑dy, ∑|dx| и ∑|dy| для каждой ячейки, в отличие от квантования градиентов в SIFT, где применяют бинирование (распределение по столбцам гистограммы) градиентов вдоль угловых направлений. Также градиенты могут быть определены в соответствии с методами GLOH.

Несмотря на то что градиенты могут отличаться, в зависимости от изображения и метода их определения, совместное распределение градиентов x, y для большого количества ячеек в одном из примеров изображено на фиг.5, а кривые контуров этого совместного распределения градиентов x, y показаны на фиг.5b. Совместное распределение градиентов x, y на фиг.5 включает индивидуальные распределения множества ячеек, четыре из которых изображены на фиг.6a-6d для иллюстрации возможных отличий между ними. Совместное распределение градиентов x, y в соответствующей ячейке, например, одной из изображенных на фиг.6a-6d, может быть определено как P_Dx, _Dy (D_X, D_Y), где N - количество пикселей в ячейке. Градиенты затем могут квантоваться, как показано в блоке 88 на фиг.4. В некоторых вариантах осуществления изобретения, однако, градиенты в ячейке, перед квантованием и окончательным определением соответствующих дескрипторов признаков, могут быть взвешены с помощью окна Гаусса.

Для квантования градиентов, они могут быть назначены соответствующему столбцу гистограммы (бину) из множества столбцов гистограммы. Перед такой процедурой назначения, однако, может быть выбрана конфигурация столбцов гистограммы, для точного и эффективного представления совместного распределения градиентов x, y. См. операции 90 и 92, показанные на фиг.4. Для выбора конфигурации столбцов гистограммы, определяемой количеством столбцов гистограммы и положением x, y столбцов гистограммы, для должного и эффективного представления совместного распределения градиентов x, y, совместное распределение градиентов x, y, например, изображенное на фиг.5А, рассматривают как градиентную пару x, y, идентифицированную как наиболее вероятную, совместно с асимметрией распределения. По отношению к совместному распределению градиентов x, y на фиг.5а градиентная пара x, y в точке (0,0) имеет наибольшую вероятность, при этом распределение имеет асимметрию (вытянуто) вдоль оси y. Для аппроксимации распределения градиентов может быть задано множество столбцов гистограммы, при этом некоторые примеры конфигурации столбцов гистограммы изображены на фиг.7а-7е. В одном из вариантов осуществления изобретения конфигурации столбцов гистограммы включают столбец гистограммы, находящийся в положении, имеющем наибольшую вероятность, и вытянуты в том же направлении или ориентации, что и само распределение. Например, каждый из примеров конфигурации столбцов гистограммы, изображенный на фиг.7а-7е, имеет столбец гистограммы в точке (0,0), при этом конфигурация либо симметрична, либо слегка вытянута в направлении оси у, при этом столбцы гистограммы равномерно распределены в интервале 0-360º. Для квантования градиентов градиентную пару dx, dy для каждого пикселя в ячейке назначают ближайшему столбцу гистограммы.

Для повышения эффективности процедуры квантования желательно иметь относительно небольшое количество столбцов гистограммы. Однако также нужно иметь достаточное количество столбцов гистограммы, так чтобы результирующая аппроксимация совместного распределения градиентов x, y имела достаточную точность. Для примера, но не ограничения, проведено сравнение точности, полученной с помощью четырех различных конфигураций столбцов гистограммы, изображенных на фиг.7a-7d, имеющих 3, 5, 7 и 9 столбцов гистограммы, соответственно, в сочетании с аппроксимацией совместного распределения градиентов x, y на фиг.5а, в единицах рабочих характеристик приемника путем сравнения частоты правильных положительных решений и ложных положительных решений для каждой из четырех различных конфигураций столбцов гистограммы с конфигурацией, предлагаемой SIFT. В соответствии с фиг.8, аппроксимация с использованием пяти столбцов гистограммы, показанных на фиг.7b, может, в одном примере сценария, по существу соответствовать характеристикам SIFT, а аппроксимация совместного распределения градиентов x, y с помощью 7 столбцов гистограммы, показанных на фиг.7 с, соответственно, может предложить улучшенные, в сравнении с SIFT, характеристики, хотя и несколько менее эффективна, по сравнению с конфигурацией для пяти столбцов на фиг.7b.

На основе квантования, терминал 10 связи и, в одном из вариантов осуществления изобретения, процессор 40 терминала связи могут формировать множество дескрипторов признаков , где i, значение которого находится в интервале от 1 до К, задано как индекс участка изображения, для которого вычисляют дескриптор, а К - количество участков, обнаруженных в изображении. См. блок 94 на фиг.4. В одном из вариантов осуществления изобретения каждый дескриптор признаков для соответствующей ячейки может быть определен таким образом, чтобы выражаться через распределение градиентов по множеству столбцов гистограммы и включать это распределение, например, с помощью вероятностного распределения. В одном из вариантов осуществления изобретения множество дескрипторов признаков может быть определено как: , где , …, представляют распределения градиентов в ячейках 1 … n дескриптора i. Размерность каждого дескриптора может быть задана как n×В, где n - количество ячеек, а В - количество столбцов гистограммы.

Может быть предпочтительным определение дескрипторов признаков непосредственно через распределения градиентов, например вероятностные распределения. В этом отношении, путем представления информации о градиентах в виде распределения вероятностей для каждой ячейки, статистика базового распределения градиентов может быть эффективно использована путем избирательного помещения центров столбцов гистограммы, в соответствии с предыдущим описанием, на основе положения градиента x, y, имеющего наибольшую вероятность, и на основе асимметрии совместного распределения градиентов x, y. Дополнительно, распределения вероятностей могут сравниваться более эффективно с использованием таких мер расстояний, как дивергенция Кульбака-Лейблера (Kullback-Leiblier, KL) и экскаваторная дистанция (Earth Mover's Distance, EMD), по сравнению с нормой L-2. Кроме того, распределения вероятностей могут быть эффективно сжаты с формированием дескрипторов, имеющих малую битовую скорость передачи, в соответствии с последующим описанием.

После определения распределения градиентов и вычисления дескрипторов признаков, терминал 10 связи и, в одном из вариантов осуществления изобретения, процессор 40 терминала связи может сжимать эти дескрипторы признаков, состоящие из распределений градиентов в соответствующих ячейках. См. операцию 96 на фиг.4. Например, распределения градиентов (и, в свою очередь, дескрипторы признаков, состоящие из распределений градиентов) могут быть сжаты с помощью древовидного кодирования, например, древовидного кодирования по методу Гаджи (Gagie) или по методу Хаффмана (Huffman), в соответствии с описанием в статье Т.Гаджи "Сжатие вероятностных распределений" (T.Gagie, "Compressing Probability Distributions"), Inf. Process. Lett., Vol.97, №4, с.133-37 (2006). Для рассмотрения этих подходов древовидного кодирования, обозначим исходное распределение как Р=p₁, p₂, …, p_n, a сжатое распределение вероятностей с потерей качества, заданное в том же пространстве выборок, как Q=q₁, q₂, …, q_n. В вариантах осуществления изобретения, применяющих кодирование с помощью деревьев Хаффмана, Р сжимают путем построения дерева Хаффмана на основе этого распределения и хранения кодов Хаффмана каждого символа, это гарантирует, что дивергенция D Кульбака-Лейблера между двумя распределениями (Р и Q) D (P||Q)<1, и потребует количество битов, равное O(nlogn). Если для хранения глубины каждого символа в дереве Хаффмана используют коды, с фиксированной длиной, то дерево Хаффмана может храниться в (n-1)[log(n-1)] битах. Альтернативно, если используют кодирование с помощью деревьев Гаджи, распределение Q может быть построено так, что D(p||Q)<log₂(2+2^3-k), при этом Q может храниться ровно в kn-2 битах.

Различия между древовидным кодированием Гаджи и Хаффмана можно понять, рассмотрев сами деревья Гаджи и Хаффмана. В этом отношении, деревья Гаджи являются упорядоченными, и, следовательно, само дерево хранит информацию всего распределения Р. С другой стороны, деревья Хаффмана не упорядочены как вероятности символов, которые сортируют в процессе построения дерева. Таким образом, дерево Хаффмана дает меньшее D(P||Q) чем 1, но требует большего количества битов, равного (n-1)[log(n-1)], по сравнению с 2n - 2 битами для деревьев Гаджи.

В отношении сжатия распределений градиентов в каждой ячейке, битовая скорость передачи увеличивается как для деревьев Гаджи, так и для деревьев Хаффмана с ростом количества столбцов гистограммы, при этом также улучшаются характеристики дескриптора признаков. В качестве примера, но не ограничения, распределение градиентов одной из ячеек изображено на фиг.9а. Далее следует квантование с использованием пяти столбцов гистограммы, в соответствии с конфигурацией на фиг.7b, a результирующая гистограмма изображена на фиг.9b. Эту гистограмму затем независимо сжимают с использованием как деревьев Хаффмана, так и деревьев Гаджи, при этом результирующие распределения показаны на фиг.9b. Для одного и того же исходного распределения Р и результирующего сжатого распределения Q, схемы кодирования деревьями Гаджи (сверху) и Хаффмана (снизу) показаны ниже:

Р	S	С	Дерево Гаджи	Q
0.8281	0.4141	0		0.500
0.0000	0.8281	11010	0.125
0.0312	0.8438	11011	0.125
0.0625	0.8906	1110	0.125
0.0781	0.9609	1111	0.125

Р	Sort(P)	Дерево Хаффмана	С	Q
0.8281	0.0000