ДЕТЕКТИРОВАНИЕ БАРКОДОВ НА ИЗОБРАЖЕНИЯХ

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

[0001] Настоящее изобретение в целом относится к обработке изображений, а более конкретно - к системам и способам обнаружения объектов, имеющихся на изображениях, включая обнаружение наличия баркодов на изображениях.

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

[0002] Коды, например, баркоды, в современную эпоху используются для множества задач. Баркод является оптическим машиночитаемым представлением данных. Множество баркодов представляют данные, варьируя ширину и расстояние между линиями, прямоугольниками, точками, шестиугольниками и другими геометрическими текстурами. Примеры кодов (обычно называемых в настоящем описании «баркодами») могут включать двухмерные матричные баркоды, Aztec Code, Color Construct Code, CrontoSign, CyberCode, d-touch, DataGlyphs, Data Matrix, Datastrip Code, Digimarc Barcode, DotCode, Dot Code А, цифровую бумагу, DWCode, EZcode, High Capacity Color Barcode, Han Xin Barcode HueCode, InterCode, MaxiCode, MMCC, NexCode, код Nintendo e-Reader#Dot, PDF417, Qode, QR-код, AR Code, ShotCode, Snapcode, также именуемый кодом Boo-R, SPARQCode, VOICEYE и пр. Баркоды могут наноситься на различные объекты или внутри них, в том числе на печатные документы, цифровые изображения и др. Для распознавания данных, представленных в виде баркода на изображении, необходимо сначала обнаружить наличие баркода на изображении.

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

[0003] В соответствии с одним или более вариантами реализации настоящего изобретения пример способа обнаружения баркодов может включать получение с помощью обрабатывающего устройства изображения для обнаружения баркодов на изображении, помещение множества патчей (image patches) на изображение поверх изображения, где множество патчей на изображении соответствует области пикселей; выявление из множества патчей на изображении подмножества патчей на изображении, перекрывающих один или более баркодов, связанных с изображением; объединение одного или более патчей на изображении из подмножества патчей на изображении, с образованием одной или более комбинированных патчей на изображении; и создание одной или более отдельных связных компонент с помощью одного или более комбинированных патчей на изображении, так что одна или более отдельных связных компонент определяются в качестве одного или более обнаруженных баркодов.

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

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

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

[0006] Настоящее изобретение иллюстрируется с помощью примеров, а не способом ограничения, и может быть лучше понято при рассмотрении приведенного ниже описания предпочтительных вариантов реализации в сочетании с чертежами, на которых:

[0007] На Фиг. 1 приведена схема компонентов верхнего уровня для примера архитектуры системы в соответствии с одним или более вариантами реализации настоящего изобретения.

[0008] На Фиг. 2 приведена блок-схема одного иллюстративного примера способа обнаружения баркодов на изображении в соответствии с одним или более вариантами реализации настоящего изобретения.

[0009] На Фиг. 3 приведена схема машинного обучения, использованная для классификации наложенных изображений в соответствии с одним или более вариантами реализации настоящего изобретения.

[0010] На Фиг. 4 приведены классифицированные патчи на изображении для обнаружения баркодов в соответствии с одним или более вариантами реализации настоящего изобретения.

[0011] На Фиг. 5 рассмотрены классифицированные патчи на изображении для обнаружения баркодов в соответствии с одним или более вариантами реализации настоящего изобретения.

[0012] На Фиг. 6А-6В изображены комбинированные патчи на изображении в соответствии с одним или более вариантами реализации настоящего изобретения.

[0013] На Фиг. 7А-7В показано уточнение границ комбинированных патчей на изображении в соответствии с одним или более вариантами реализации настоящего изобретения.

[0014] На Фиг. 8А-8В показаны изображения, бинаризованные с использованием морфологии, в соответствии с одним или более вариантами реализации настоящего изобретения.

[0015] На Фиг. 9А-9В показаны отдельные связные компоненты в соответствии с одним или более вариантами реализации настоящего изобретения.

[0016] На Фиг. 10 изображены примеры типов баркодов, которые могут быть обнаружены, в соответствии с одним или более вариантами реализации настоящего изобретения.

[0017] На Фиг. 11 представлена подробная схема компонентов примера вычислительной системы, внутри которой исполняются инструкции, которые вызывают выполнение вычислительной системой любого из одного или более способов, рассматриваемых в этом документе.

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

[0018] В настоящем документе описываются способы и системы обнаружения баркодов на изображениях.

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

[0020] Традиционно для обнаружения баркодов на изображении используются различные техники. К этим техникам могут относиться отслеживание штрихов, морфологические алгоритмы, вейвлет-преобразование, преобразование Хафа, анализ односвязных компонент и пр. Эти техники не всегда обеспечивают достаточную эффективность и точность обнаружения баркодов. Например, анализ связных компонент обычно может использоваться для анализа небольших областей изображений. Обнаружение баркодов на изображении с большой площадью может быть затруднительным, а в некоторых случаях - невозможным. Обнаружение баркодов может вызвать проблемы при наличии на одном изображении нескольких баркодов. Полные зоны баркодов могут не обнаруживаться с точностью, необходимой для точного распознавания баркодов. Если баркоды расположены близко друг к другу, может пострадать качество и(или) точность обнаружения баркодов.

[0021] Аспекты настоящего изобретения устраняют отмеченные выше и другие недостатки путем предоставления механизмов для обнаружения баркодов на изображении с использованием патчей на изображении. Этот механизм может автоматически обнаруживать наличие одного или более баркодов на изображении и выявлять области изображения, содержащие отдельные баркоды. Этот механизм может включать получение изображения, на котором выполняется обнаружение баркодов. Поверх изображения может быть помещено или наложено множество патчей. Под термином «патч изображения» (image patch) может подразумеваться область пикселей изображения. Патч изображения может включать контейнер, содержащий часть изображения. Обычно, но не всегда, эта часть изображения может быть прямоугольной или квадратной. Патчи на изображении могут покрывать все полученное изображение. Патчи на изображении могут классифицироваться для выявления потенциальных патчей на изображении, перекрывающих баркоды на полученном изображении. Предварительная классификация может выполняться путем выявления патчей на изображении, которые определенно не содержат даже части баркода. Остальные патчи на изображении (то есть патч, возможно содержащие некоторые части баркодов) могут быть классифицированы с помощью модели машинного обучения в ходе второго этапа классификации патчей, перекрывающихся с баркодами.

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

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

[0024] Как описано в настоящем документе, эта технология обеспечивает автоматическое обнаружение баркодов на самых разных изображениях. Эта технология обеспечивает меры для выявления баркодов на изображениях, которые кроме баркодов содержат и другие элементы. Эта технология позволяет отделять баркоды от других объектов изображения и точно выявлять области изображения, содержащие баркоды. Эта технология позволяет обнаруживать баркоды без ограничений по размеру изображения или количеству баркодов на изображении. Она позволяет обнаруживать и различать различные баркоды, даже если баркоды расположены на изображении в непосредственной близости друг от друга. Описанные в этом документе системы и способы позволяют использовать для обнаружения баркодов огромное количество различных типов изображений, повышая качество, точность, эффективность и полезность технологии обнаружения баркодов. Обработка изображений эффективно повышает качество распознавания изображений в части, касающейся обнаружения баркода на изображении. Качество распознавания изображений, обеспечиваемое системами и способами по настоящему изобретению, позволяет значительно увеличить точность оптического распознавания символов (OCR, Optical Character Recognition) по сравнению с различными стандартными способами.

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

[0026] На Фиг. 1 изображена схема компонентов верхнего уровня для примера системной архитектуры 100 в соответствии с одним или более вариантами реализации настоящего изобретения. Системная архитектура 100 включает вычислительные устройства 150, 160, 170 и 180, а также хранилище 120, подключенное к сети 130. Сеть 130 может быть общественной сетью (например, Интернет), частной сетью (например, локальная сеть (LAN) или распределенной сетью (WAN)), а также их комбинацией.

[0027] Изображение 140 может использоваться в качестве исходного изображения, которое анализируется на предмет наличия одного или более баркодов. В одном из примеров изображение 140 может быть цифровым изображением документа. Этот документ может быть печатным документом, электронным документом и т.д. Изображение 140 может содержать объекты 141, 142 и 143, представляющие собой, например, баркоды, текст, линии и пр. В одном из примеров объект 141 может быть бар ко дом. В некоторых вариантах реализации изобретения баркоды могут содержать один или более баркодов, показанных на Фиг. 10. В некоторых примерах изображение 140 может не содержать баркодов.

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

[0029] Различные вычислительные устройства могут предоставлять компоненты и модули для выполнения функциональности системы 100. Каждое из вычислительных устройств 150, 160, 170, 180 может быть настольным компьютером, портативным компьютером, смартфоном, планшетным компьютером, сервером, стоечным сервером, маршрутизатором, сканером, карманным персональным компьютером, мобильным телефоном, фотокамерой, видеокамерой, нетбуком, настольным компьютером, медиацентром или их сочетанием. В некоторых вариантах реализации изобретения вычислительные устройства могут быть и (или) включать одно или более вычислительных устройств 1100 с Фиг. 11.

[0030] Система 100 может включать систему совмещения 152, классификатор патчей 162, систему объединения патчей 172 и систему обработки связных компонент 182. В одном из примеров вычислительное устройство 150 может включать систему совмещения 152, которая в состоянии выполнять наложение (то есть накладывать) патчи на полученное изображение 140. Под термином «патч изображения» или «патч на изображении» (image patch) может подразумеваться область пикселей изображения. Патч на изображении может включать контейнер, содержащий часть изображения. Патчи на изображении могут покрывать все полученное изображение 140.

[0031] В одном из примеров вычислительное устройство 160 может включать классификатор патчей 162, который в состоянии классифицировать наложенные на изображение патчи, выявляя патчи, перекрывающиеся с одним или более баркодами, которые могут быть связаны с полученным изображением 140. Предварительная классификация может выполняться путем выявления наложенных на изображение патчей, которые определенно не содержат даже части баркода. Для предварительной классификации могут использоваться различные методы градиентного бустинга. Остальные патчи на изображении (то есть патчи, возможно содержащие некоторые части баркодов) могут быть классифицированы с помощью модели машинного обучения, с получением в результате итоговой классификации патчей (то есть подмножества наложенных на изображение патчей), перекрывающихся с баркодами на полученном изображении 140.

[0032] В одном из примеров вычислительное устройство 170 может содержать систему объединения патчей 172, которая может объединять два или более классифицированных подмножеств наложенных на изображение патчей, образуя одну или более комбинированных патчей на изображении. В результате объединения различных наборов патчей на изображении может быть получено несколько комбинированных патчей на изображении. Кроме того, система объединения патчей 172 или другой компонент внутри системы 100 может уточнять комбинированные патчи на изображении для выявления границ комбинированных патчей на изображении.

[0033] В одном из примеров вычислительное устройство 180 может содержать систему обработки связных компонент 182, которая в состоянии создавать одну или более отдельных (обособленных) связных компонент, используя одну или более комбинированных патчей на изображении. Кроме того, можно выполнить обрезку вдоль границ отдельной связной компоненты. Дополнительно система 182 обработки связных компонент или другой компонент системы 100 может выполнять другие классификации (например, с использованием алгоритмов машинного обучения, алгоритмов градиентного бустинга и пр.), чтобы определить, действительно ли область связной компоненты соответствует баркоду. Одна или более полученных отдельных связных компонент могут быть определены как один или более обнаруженных баркодов на исходном изображении.

[0034] Хранилище 120 может представлять собой постоянную память, которая в состоянии хранить изображение 140, объекты 141, 142, 143, а также различные структуры данных, используемые различными компонентами системы 100. Хранилище 120 может располагаться на одном или более запоминающих устройствах, таких как основная память, магнитные или оптические запоминающие устройства на основе дисков, лент или твердотельных накопителей, NAS, SAN и т.д. Несмотря на то что хранилище изображено отдельно от вычислительных устройств 150, 160, 170 и 180, в одной из реализаций изобретения хранилище 120 может быть частью одного из вычислительных устройств 150, 160, 170 и 180. В некоторых вариантах реализации хранилище 120 может представлять собой подключенный к сети файловый сервер, в то время как в других вариантах реализации изобретения хранилище содержимого 120 может представлять собой какой-либо другой тип энергонезависимого запоминающего устройства, например объектно-ориентированная база данных, реляционная база данных и т.д., которая может находиться на сервере или одной или более различных машинах, подключенных к нему через сеть 130.

[0035] Следует отметить, что в некоторых других реализациях функции вычислительных устройств 150, 160, 170 и 180 могут выполняться меньшим количеством машин. Например, в некоторых вариантах реализации вычислительные устройства 150 и 160 могут быть интегрированы в одно вычислительное устройство, а в некоторых других вариантах реализации вычислительные устройства 150, 160 и 170 могут быть интегрированы в одно вычислительное устройство. Кроме того, в некоторых вариантах реализации одно или более вычислительных устройств 150, 160, 170 и 180 могут быть интегрированы в полноценную платформу распознавания изображений.

[0036] Обычно функции, описанные в одной из реализаций как выполняемые полноценной платформой распознавания изображений, вычислительным устройством 150, вычислительным устройством 160, вычислительным устройством 170 и(или) вычислительным устройством 180, в других вариантах реализации также могут быть выполнены на клиентских машинах, если это целесообразно. Кроме того, функциональность, приписанная отдельному компоненту, может выполняться различными или несколькими компонентами, работающими совместно. Полноценная платформа распознавания изображений, вычислительное устройство 150, вычислительное устройство 160, вычислительное устройство 170 и(или) вычислительное устройство 180 также могут быть доступны в качестве услуги, поставляемой другим системам через соответствующий интерфейс прикладного программирования.

[0037] На Фиг. 2 приведена блок-схема одного иллюстративного примера способа 200 обнаружения баркодов на изображении в соответствии с одним или более вариантами реализации настоящего изобретения. Способ 200 и(или) каждая из его отдельно взятых функций, процедур, подпрограмм или операций могут осуществляться с помощью одного или более процессоров вычислительной системы (например, вычислительной системы 1100 на Фиг. 11), реализующей этот способ. В некоторых реализациях способ 200 может быть реализован в одном потоке обработки. Кроме того, способ 200 может выполняться, используя два или более потоков обработки, причем каждый поток выполняет одну или более отдельных функций, процедур, подпрограмм или операций способа. В качестве иллюстративного примера потоки обработки, реализующие способ 200, могут быть синхронизированы (например, с использованием семафоров, критических секций и(или) других механизмов синхронизации потоков). В качестве альтернативы реализующие способ 200 потоки обработки могут выполняться асинхронно по отношению друг к другу. Таким образом, несмотря на то, что Фиг. 2 и соответствующее описание содержат список операций для способа 200 в определенном порядке, в различных вариантах реализации способа как минимум некоторые из описанных операций могут выполняться параллельно и(или) в случайно выбранном порядке. В одном из вариантов реализации способ 200 может выполняться с помощью одного или более компонентов на Фиг. 1, например системы совмещения 152, классификатора патчей 162, системы объединения патчей 172, системы обработки связных компонент 182 и т.п.

[0038] На шаге 210 вычислительная система, реализующая способ, может получать изображение для поиска баркодов на изображении. Изображение может использоваться в качестве исходного изображения, которое анализируется на предмет наличия в нем одного или более баркодов. Например, полученное изображение может быть сравнимо с изображением 140 на Фиг. 1. Это изображение может быть получено различными способами, например, с мобильного телефона, сканера, по сети и пр. Изображение может содержать множество объектов. Некоторые из этих объектов могут содержать один или более типов баркодов. В некоторых примерах изображение может не содержать баркодов. В некоторых вариантах реализации изобретения изображение может дополнительно подвергаться предварительной обработке с использованием подходящего способа предварительной обработки, например, повышения локального контраста или преобразования в полутоновое (grayscale) изображение (то есть предварительная обработка создает полутоновое изображение), или их комбинации.

[0039] На шаге 220 вычислительная система может помещать (то есть накладывать) на изображение множество патчей изображения. Каждый из множества патчей на изображении может соответствовать области пикселей. Патч на изображении может включать контейнер, содержащий часть изображения. Обычно, но не всегда, эта часть изображения может быть прямоугольной или квадратной. Патчи на изображении могут покрывать все полученное изображение. В одном из примеров изображение может создаваться с размером 100 пикселей («рх») на 100 пикселей (также может называться «100×100 рх»). Изображение может быть разделено на контейнеры, содержащие более мелкие части изображения. Это изображение может быть разделено на 100 более мелких частей изображения. Каждая часть может содержать область размером 10×10 рх, или всего 100 рх на часть. Каждая часть может называться патчем на изображении. В одном из примеров для разделения изображения может использоваться сетка, в которой каждая ячейка сетки соответствует патчу на изображении. В одном из примеров вычислительная система может перекрывать (то есть «накладывать на») полученное изображение сеткой, содержащей патчи на изображении. В одном из примеров для разбиения на патчи может быть выбрано простое изображение. Например, изображение может содержать пиксели только одного цвета.

[0040] Патчи на изображении могут быть ассоциированы с шагом наложения патчей. Шаг наложения может соответствовать заданному размеру для каждого из множества патчей на изображении. Например, шаг наложения может иметь заданный размер по ширине и высоте сетки. Таким образом, если шаг патчей имеет размер, например, 48×48 рх, то шаг наложения для патчей на изображении признается равным 48 рх. Шаг наложения, выбираемый для патчей на изображении, может выбираться эмпирически, или в результате наблюдения, или экспериментов. Например, шаг наложения может выбираться с учетом размера стандартного, обычно используемого баркода. Например, шаг наложения 48 рх может выбираться с учетом стандартного баркода размером 60×60 рх. Шаг наложения (то есть размер патча) может выбираться таким образом, чтобы в патч помещалась только часть предполагаемого баркода, а не весь баркод целиком. Таким образом, патч может содержать как минимум одну часть баркода, а не весь баркод.

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

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

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

[0044] Например, на Фиг. 3 приведена схема (то есть модель) машинного обучения 300, используемая для классификации наложенных патчей на изображении. Эти схемы машинного обучения могут быть составлены, например, из одного уровня линейных или нелинейных операций (например, машина опорных векторов [SVM]) или могут представлять собой глубокую сеть, то есть модель машинного обучения, составленную из нескольких уровней линейных или нелинейных операций. Примерами глубоких сетей являются нейронные сети, включая сверточные нейронные сети, рекуррентные нейронные сети с одним или более скрытыми слоями, полносвязные нейронные сети и пр. Исходно модель машинного обучения можно обучить распознавать содержимое различных изображений с помощью обучающих данных. После обучения модели машинного обучения ее можно использовать для анализа новых изображений.

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

[0046] На Фиг. 3 приведен пример модели 300 машинного обучения, использующей сверточные нейронные сети («CNN»). Сверточная нейронная сеть может содержать слои вычислительных блоков для иерархической обработки визуальных данных и может передавать результаты работы одного слоя на следующий слой, извлекая определенный признак из исходных изображений. Каждый из слоев может называться сверточным слоем или слоем свертки. CNN может включать итеративную фильтрацию одного или более изображений с переходом изображений от одного слоя к следующему внутри CNN. Отфильтрованные изображения могут передаваться на каждый следующий слой. Каждый слой или набор слоев может быть предназначен для определенного типа функции (например, отдельной функции для фильтрации). Изображение, получаемое CNN в качестве исходного сигнала, может обрабатываться иерархически, начиная с первого (то есть входного) слоя, каждым из слоев. CNN может передавать результат работы одного из слоев дальше, в качестве исходных данных для следующего слоя, и получать с последнего слоя итоговый выходной сигнал.

[0047] Как показано на Фиг. 3, CNN 300 может содержать множество вычислительных блоков, собранных в виде сверточных слоев. CNN 300 может содержать входной слой 315, первый сверточный слой 325, второй сверточный слой 345, третий сверточный слой 365 и полносвязный слой 375. Каждый слой вычислительных блоков может получать исходные данные и отдавать результат. В одном из вариантов реализации входной слой 315 может получать исходные патчи 310 на изображении 310. В одном из примеров патчи 310 на изображении могут включать наложенные патчи на изображении, оставшиеся после исключения одного набора патчей в ходе предварительной классификации. Например, патчи 310 на изображении могут включать первый набор патчей на изображении из множества патчей на изображении, имеющих хотя бы некоторую вероятность перекрывания с одним или более баркодами, как обсуждалось со ссылкой на Фиг. 2. Патчи 310 на изображении могут включать пиксели, соответствующие частям одного или более баркодов, которые перекрываются с патчами на изображении, поскольку патчи на изображении перекрываются с полученным изображением, потенциально содержащим баркоды. Входной слой может использоваться для передачи исходных значений на следующий слой CNN. В связи с этим входной слой 315 может получать патчи на изображении в определенном формате и передавать эти значения в качестве результата входного слоя на следующие слои. Например, вычислительный блок входного слоя 315 может получать в качестве исходных данных один или более настраиваемых параметров, например, количество фильтров, количество каналов, настраиваемую матрицу систематической ошибки и пр. Входной слой может производить в качестве результата те же самые параметры и передавать их в качестве исходных данных на следующий слой.

[0048] Как показано на Фиг. 3, следующий слой может быть первым сверточным слоем 325. Первый сверточный слой 325 может получать входные параметры 320 (то есть результат работы входного слоя 315) в качестве исходных данных для первого сверточного слоя 325. Первый сверточный слой 325 может быть предназначен для выполнения определенных вычислений с использованием входных параметров 320. Например, первый сверточный слой 325 может включать вычислительных блок, который может являться слоем «ConvNdBackward», с функцией, которая использует прямой вызов и выполняет стандартные обратные вычисления. Вычислительный блок может включать различные компоненты, например, матрицы и другие переменные, используемые в вычислениях в сочетании с исходными параметрами 320. Эти компоненты могут включать пакетную матрицу нормализации (batch normalization matrix), пакетную матрицу нормализации bias (batch normalization bias matrix), слой пакетной нормализации (batch normalization), вычисление обратной функции, активацию слоя обратной функции (то есть, например, слой «LeakyReluBackward»), слой обратной передачи максимума (то есть обратного распространения, которое сохраняет индекс, дающий максимальное значение) и пр. Градиент обратного распространения может быть исходным градиентом при этом индексе. В результате вычислений, выполняемых первым сверточным слоем 325, могут быть получены выходные параметры 330.

[0049] Выходные параметры 330 могут быть переданы на следующий слой, второй сверточный слой 345, в качестве исходных параметров 340. Второй сверточный слой 345 может вычислять выходные параметры 350, которые могут быть переданы на третий сверточный слой 365 в качестве исходных параметров 360. Третий сверточный слой 365 может вычислять выходные параметры 370, которые могут быть переданы на полносвязный слой 375. Каждый из второго сверточного слоя 345 и третьего сверточного слоя 365 может содержать архитектуру, сходную с архитектурой, описанной для первого сверточного слоя 325, включая получение типов исходных параметров, наличие компонентов, включая матрицы и вычислительные слои блоков, и создание типов выходных параметров. Полносвязный слой 375 может получать выходные параметры 370 и выявлять два набора патчей на изображении. Первый набор может быть набором соответствующих патчей 380, который может включать патчи, классифицированные как имеющие отношение к баркодам. Второй набор может быть набором несоответствующих патчей 382, который может включать патчи, классифицированные как не имеющие отношение к баркодам. Первый набор, набор соответствующих патчей 380, может быть определен как подмножество патчей на изображении, перекрывающихся с одним или более баркодами, как описано на шаге 230 на Фиг. 2. Следует отметить, что в некоторых вариантах реализации изобретения классификация на шаге 230 может включать только один этап классификации, а не два этапа (то есть градиентный бустинг и CNN), как указано выше. В одном из примеров все перекрывающиеся патчи на изображении могут поступать в CNN 300 и классифицироваться как наборы соответствующих и несоответствующих патчей с помощью CNN 300.

[0050] Согласно Фиг. 2 на шаге 240 вычислительная система может объединять (осуществлять слияние) двух или более патчей на изображении из подмножества патчей изображения, создавая один или более комбинированных патчей на изображении. Например, на Фиг. 4 показаны классифицированные патчи на изображении, которые были определены как содержащие одну или более частей баркода, с патчами на изображении, перекрывающимися с баркодами до объединения патчей на изображении. В одном из примеров после получения изображения 140 на Фиг. 1, содержащего объект 141, который был классифицирован, подмножество патчей на изображении, перекрывающихся с объектом 141, было определено как патчи на изображении, перекрывающиеся с одним или более баркодами, ассоциированными с изображением 140. Стрелка 410 указывает на увеличенную версию объекта 141 на изображении 140 в области 420. Пример патчей на изображении может включать квадратную область 430, отмеченную внутри области 420 изображения 140. Область 420 содержит несколько патчей на изображении (например, патчи на изображении 430, 431, 432, 434 и т.п.), перекрывающихся с объектом 141, и эти патчи на изображении были классифицированы как принадлежащие к подмножеству патчей на изображении, перекрывающихся с одним или более баркодами или частями баркодов. На Фиг. 4 показаны патчи на изображении до объединения патчей. Аналогично, на Фиг. 5 показано изображение 500, которое содержит области, содержащие баркоды. Патчи на изображении, наложенные поверх изображения 500, были классифицированы для выявления подмножества патчей на изображении в каждой области изображения, которые перекрываются с одним или более баркодами, ассоциированными с изображением. Область изображения 510 является увеличенным вариантом одной из областей изображения для изображения 500. Область изображения 510 содержит подмножество патчей на изображении (то есть патчей 520, 522, 524, 526 и пр.), перекрывающихся с различными объектами в области изображения 510 и классифицированных как принадлежащие к подмножеству патчей на изображении, перекрывающихся с одним или более потенциальными баркодами или частями баркодов.

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

[0052] Применяя принцип соседства к патчам на изображении, вычислительная система может объединять две или более патчей на изображении, включая две или более патчей 430, 431, 432 и 434 на изображении 140 и две или более патчей 520, 522, 524 и 524 на области изображения 510, образуя одну или более комбинированных патчей на изображении. В одном из вариантов реализации вычислительная система выбирает для объединения первый патч на изображении и второй патч на изображении. Если первый и второй патчи на изображении имеют как минимум одну общую границу, эти первый и второй патчи на изображении объединяются (склеиваются). Все патчи на изображении в подмножестве рассматриваются одинаковым способом и объединяются при наличии у них хотя бы одной общей границы. Например, патч на изображении 430 и патч на изображении 431 имеют как минимум одну общую границу 440. Таким образом, патч на изображении 430 и патч на изображении 431 объединяются, образуя комбинированный патч на изображении.

[0053] В одном из вариантов реализации изобретения вычислительная система может рассматривать два патча на изображении как кандидаты на объединение и выявлять, существует ли у этих двух патчей на изображении хотя бы одна общая граница. При выявлении общего соседа один из патчей на изображении объединяется с общим соседом. Следует отметить, что общий соседний патч на изображении может не быть патчем на изображении, включенным в подмножество патчей на изображении, определенных как перекрывающиеся с одним или более баркодами. После индивидуального рассмотрения и объединения каждого рптча на изображении процесс итеративно повторяется для присоединения новообразованных комбинированных патчей на изображении. Например, патчи на изображении 432 и 434 по отдельности не имеют общих границ между патчами на изображении. Однако патчи 432 и 434 могут быть объединены через промежуточные патчи. Патч 432 может быть объединен с патчем справа от патча 432 по причине наличия общей границы. После объединения патчей и образования комбинированного патча, патч 432 и патч справа от нее, как комбинированный патч, будут иметь общую границу 441. В результате комбинированный патч, включающий патч 432 и патч справа от него, может быть объединен с патчем 434 и соседним с ним патчем 442, имеющим с ним общую границу 441. Патч на изображении 442 показан пунктирными линиями, поскольку этот патч не входит в подмножество патчей, которые определены как перекрывающиеся с баркодами.

[0054] Процесс выявления промежуточных патчей на изображении и их объединения может продолжаться до тех пор, пока продолжается объединение пар патчей на изображении. В конце процесса объединения патчей на изображении в области 420 изображения 140 образуется общий комбинированный патч на изображении. На Фиг. 6А показана общий комбинированный патч на изображении 610 после объединения двух или более патчей на изображении из подмножества патчей на изображении. На Фиг. 6А также показан второй комбинированный патч на изображении 620, который был получен в результате классификации патчей на изображении, наложенных на изображение 140, и объединения патчей на изображении по принципу соседства. В ходе этого процесса вычислительная система в состоянии выявить все области изображения 140, потенциально содержащие один или более баркодов. Аналогично, на Фиг. 6В показаны итоговые комбинированные патчи на изображении после объединения патчей на изображении с изображения 500. Например, объединение для области изображения 510 создает три комбинированных патча на изображении 630, 632 и 634.

[0055] В одном из вариантов реализации изобретения после объединения вычислительная система может также уточнить границы областей, содержащих потенциальные баркоды. Границы комбинированных патчей на изображении, содержащих потенциальные баркоды, могут пересекаться (то есть накладываться) на реальные баркоды таким образом, что некоторые части баркодов будут расположены вне границ комбинированных патчей на изображении. По этой причине границы может потребоваться уточнить, чтобы захватить баркоды целиком, без отсечения частей баркодов. Уточнение границ может включать выбор области, содержащей комбинированный патч на изображении, такой, чтобы эта область была на один шаг больше, чем комбинированный патч на изображении, по каждому из размеров комбинированного патча на изображении. После выбора области выбранная область может быть бинаризована. Может быть построена гистограмма ширины штрихов для выбранной области. Из гистограммы может быть выбрано максимальное значение ширины, это максимальное значение берется из самого высокого пика гистограммы.

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

[0056] Например, как показано на Фиг. 7А и 7В, могут быть уточнены границы комбинированного патча на изображении 610 изображения 140 и комбинированного патча на изображении 634 области изображения 510. На Фиг. 7А показано, что область, указанная пунктирной линией содержащая четыре границы комбинированного патча на изображении 610, расширяется в четырех направлениях в области, окружающей комбинированный патч на изображении 610. Результаты расширения в новую область с уточненными границами показаны сплошными линиями 720, в которые попадают и предыдущие границы комбинированного патча на изображении 610. Разница 710 между предыдущими границами патча на изображении 610 и новыми границами 720 могут составлять один шаг патча. Как описывалось на шаге 220 на Фиг. 2, шаг патча может соответствовать определенному размеру для каждого из множества патчей на изображении. В качестве размера шага патча для патчей на изображении (например, патч на изображении 430, приведенной на Фиг. 4), покрывающих изображение 140, может быть выбрано 48 рх (или другое подходящее значение). Таким образом, в примере с шагом патча 48 рх расширенная область с границами 720 может быть на 48 рх больше, чем комбинированный патч на изображении 610, в каждом из четырех направлений вдоль предыдущих границ сетки 610. Аналогично, область, окружающая комбинированный патч на изображении 634, расширяется на один шаг патча во всех направлениях до уточненных границ на Фиг. 7В.

[0057] После расширения границ область, охваченная новыми границами, может быть бинаризована, и с использованием бинаризованного изображения в охваченной области может быть построена гистограмма ширины штрихов. Например, Фиг. 8А и 8В иллюстрируют области 810 и 820, соответствующие областям, охваченным новыми границами 720 на Фиг. 7А и границами 730 на Фиг. 7В соответственно. Изображение 812 в области 810 и изображение 822 в области 820 представляют собой бинаризованные изображения, полученные из изображений, находившихся внутри границ 720 и 730 соответственно. Гистограмма ширины штрихов строится с использованием каждого бинаризованного изображения в каждой области. Ширина штрихов пикселя может быть определена через минимальное значение длины поля в каждом из направлений (горизонтальном, вертикальном и двух диагональных). Длина поля может быть определена количеством пикселей в четырех направлениях кромки пикселя. Значения ширины штриха в пикселях могут быть статистически представлены гистограммой ширины штрихов. Максимальное значение, соответствующее одной точке баркода, может быть взято из самого высокого пика гистограммы. После выбора максимального значения может быть выполнена бинарная морфология (binary morphology) с использованием операции замыкания (closing operation) с шириной выбранного максимального значения. Бинарная морфология представляет собой набор фундаментальных операций над бинаризованными изображениями. В частности, операция замыкания используется для устранения шума из изображений, устранения мелких пробелов из изображения. После выполнения морфологии некоторые белые пробелы в изображении в области 810 (или 820) могут быть заполнены. В частности, поскольку операция выполняется с шириной выбранного максимального значения, заполняемыми регионами (то есть пробелами) будут те, ширина которых соответствует ширине структурного морфологического элемента (например, максимального параметра ширины). Высота структурного элемента может быть вычислена из ширины и соотношения сторон баркода в области 810 или 820 (то есть с учетом высоты элемента баркода).

[0058] Согласно Фиг. 2 на шаге 250 вычислительная система может создавать (генерировать) одну или более отдельных (обособленных) связных компонент, используя одну или более комбинированных патчей на изображении. Например, Фиг. 9А и 9В иллюстрируют отдельные связные компоненты 910 и 920 соответственно. Отдельная связная компонента 910 (или 920) может быть сгенерирована с использованием комбинированного патча на изображении, полученного в результате объединения исходных патчей на изображении, наложенных на изображение. Отдельная (обособленная) связная компонента может быть порождена из бинаризованного изображения (например, изображения 812 на Фиг. 8А, изображения 822 на Фиг. 8В и пр.), полученного с использованием комбинированного патча на изображении. Для обнаружения связных областей в бинаризованном цифровом изображении может быть использован анализ связных компонент. При анализе связных компонент (также - «маркирование связных компонент», connected components labeling) производится сканирование изображения и группировка пикселей изображения в компоненты на основе связности пикселей. Связность пикселей может определяться исходя из значений интенсивности пикселей. В качестве связности используется 4-связность или 8-связность. В одном из примеров, если соседние пиксели имеют одинаковые значения интенсивности пикселей, то целевой пиксель и соседние с ним пиксели, имеющие одинаковые значения интенсивности, группируются в компоненту связности.

[0059] В одном из вариантов реализации минимальная компонента связности может быть определена как находящаяся в центре бинаризованного изображения 812 на Фиг. 8А. Размер минимальной компоненты связности может быть определен на основе полной области изображения баркода. Если минимальная компонента связности слишком велика, отдельная компонента связности 910 может захватить слишком большие области фона за действительными границами баркода. Если минимальная компонента связности слишком мала, части баркода могут не войти в отдельную компоненту связности 910. Таким образом, размер минимальной компоненты связности может быть определен так, чтобы он был связан с размером области баркода. В одном из примеров размер минимальной компоненты связности может быть определен как 1/8 от размера области баркода 810 или 820. После нахождения минимальной компоненты связности другие компоненты связности вокруг минимальной компоненты связности можно объединить с минимальной компонентой связности. После слияния всех компонент связности в бинаризованном изображении может быть получена одиночная (обособленная) компонента связности 910, как показано на Фиг. 9А.

[0060] Одна или более отдельных компонент связности, найденных на каждом полученном изображении (например, изображении 140, области изображения 510), могут быть идентифицированы как один или более обнаруженных баркодов. Для задания границ обнаруженного баркода может быть выполнена обрезка вдоль границ одного или более отдельных (обособленных) связных компонент. В одном из вариантов реализации может выполняться дополнительная постклассификация отдельных связных компонент для подтверждения соответствия обнаруженной области баркоду. В некоторых примерах постклассификация может выполняться с использованием модели машинного обучения, например, CNN. В некоторых примерах постклассификация может выполняться с использованием алгоритма градиентного бустинга на основе одного или более признаков из признаков растеризации полутонового изображения, признаков гистограммы ширины штрихов, алгоритма Хаара, масштабно-инвариантной трансформации признаков (SIFT), гистограммы направленных градиентов (HOG), бинарных устойчивых постоянных масштабируемых ключевых точек (BRISK) или робастных ускоренных признаков (SURF).

[0061] Обнаруженный баркод может быть передан на распознавание. На Фиг. 10 приведены примеры типов баркодов, которые могут быть обнаружены с использованием описанного в этом документе механизма обнаружения. Баркоды могут включать, помимо прочего, QR-код 1010, DataMatrix 1020 и 1050, ScanLife EZcode 1030, Microsoft Tag 1040, код Aztec 1060, MaxiCode 1070, Codablock 1080.

[0062] В некоторых примерах описанный выше механизм для обнаружения баркодов может выполняться несколько раз (например, три раза), каждый раз с разным разрешением. Разрешение может каждый раз изменяться вдвое. Например, разрешение может быть 1:1, затем 1:2 и затем 1:4 начиная с операции наложения патчей на изображении с разным разрешением. Таким образом, появляется возможность обнаружить все баркоды, имеющиеся на одном изображении, даже если размеры баркодов на изображении могут сильно различаться.

[0063] На Фиг. 11 представлена подробная схема компонентов примера вычислительной системы, внутри которой исполняются инструкции, которые вызывают выполнение вычислительной системой какого-либо одного или более способов, рассматриваемых в этом документе. Вычислительная система 1100 может быть соединена с другой вычислительной системой по локальной сети, корпоративной сети, сети экстранет или сети Интернет. Вычислительная система 1100 может работать в качестве сервера или клиента в сетевой среде «клиент/сервер» или в качестве однорангового вычислительного устройства в одноранговой (или распределенной) сетевой среде. Вычислительная система 1100 может быть представлена персональным компьютером (ПК), планшетным ПК, телевизионной приставкой (STB, set-top box), карманным ПК (PDA, Personal Digital Assistant), сотовым телефоном или любой вычислительной системой, способной выполнять набор команд (последовательно или иным образом), определяющих операции, которые должны быть выполнены этой вычислительной системой. Кроме того, несмотря на то что показана только одна вычислительная система, термин «вычислительная система» также может включать любую совокупность вычислительных систем, которые отдельно или совместно выполняют набор (или несколько наборов) команд для выполнения одной или более методик, обсуждаемых в настоящем документе.

[0064] Пример вычислительной системы 1100 включает процессор 1102, основное запоминающее устройство 1104 (например, постоянное запоминающее устройство (ROM, read-only memory) или динамическое оперативное запоминающее устройство (DRAM, dynamic random access memory)) и устройство хранения данных 1118, которые взаимодействуют друг с другом по шине 1130.

[0065] Процессор 1102 может быть представлен одним или более универсальными устройствами обработки данных, такими как микропроцессор, центральный процессор и т.п. В частности, процессор 1102 может представлять собой микропроцессор с полным набором команд (CISC, complex instruction set computing), микропроцессор с сокращенным набором команд (RISC, reduced instruction set computing), микропроцессор с командными словами сверхбольшой длины (VLIW, very long instruction word), процессор, реализующий другой набор команд или процессоры, реализующие комбинацию наборов команд. Процессор 1102 также может представлять собой одно или более устройств обработки специального назначения, такие как специализированная интегральная схема (ASIC, application specific integrated circuit), программируемая пользователем вентильная матрица (FPGA, field programmable gate array), процессор цифровых сигналов (DSP, digital signal processor), сетевой процессор или тому подобное. Процессор 1102 выполнен с возможностью исполнения инструкций 1126 для выполнения операций и функций способа 200 для обнаружения баркодов на изображении, как описано выше в этом документе.

[0066] Вычислительная система 1100 может дополнительно включать устройство сетевого интерфейса 1122, устройство визуального отображения 1110, устройство ввода символов 1112 (например, клавиатуру) и устройство ввода в виде сенсорного экрана 1114.

[0067] Устройство хранения данных 1118 может включать машиночитаемый носитель данных 1124, в котором хранится один или более наборов команд 1126, в которых реализован один или более способов или функций, описанных в данном варианте реализации изобретения. Инструкции 1126 во время выполнения их в вычислительной системе 1100 также могут находиться полностью или по меньшей мере частично в основном запоминающем устройстве 1104 и(или) в процессоре 1102, при этом основное запоминающее устройство 1104 и процессор 1102 также представляют собой машиночитаемый носитель данных. Команды 1126 также могут передаваться или приниматься по сети 1116 через устройство сетевого интерфейса 1122.

[0068] В отдельных вариантах осуществления инструкции 1126 могут включать инструкции способа 200 обнаружения баркодов на изображениях, как описано выше в этом документе. Хотя машиночитаемый носитель данных 1124 показан в примере на Фиг. 11 в виде одного носителя, термин «машиночитаемый носитель» следует понимать в широком смысле, подразумевающем один или более носителей (например, централизованную или распределенную базу данных и(или) соответствующие кэши и серверы), в которых хранится один или более наборов команд. Термин «машиночитаемый носитель данных» также следует рассматривать как термин, включающий любой носитель, который способен хранить, кодировать или переносить набор команд для выполнения машиной, который заставляет эту машину выполнять один или более способов, описанных в настоящем описании изобретения. Поэтому термин «машиночитаемый носитель данных» относится, помимо прочего, к твердотельным запоминающим устройствам, а также к оптическим и магнитным носителям.

[0069] Способы, компоненты и функции, описанные в этом документе, могут быть реализованы с помощью дискретных компонентов оборудования, либо они могут быть встроены в функции других компонентов оборудования, например, ASICS (специализированная заказная интегральная схема), FPGA (программируемая логическая интегральная схема), DSP (цифровой сигнальный процессор) или аналогичных устройств. Кроме того, способы, компоненты и функции могут быть реализованы с помощью модулей встроенного программного обеспечения или функциональных схем аппаратного обеспечения. Способы, компоненты и функции также могут быть реализованы с помощью любой комбинации аппаратного обеспечения и программных компонентов либо исключительно с помощью программного обеспечения.

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

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

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

[0073] Настоящее изобретение также относится к устройству для выполнения операций, описанных в настоящем документе. Такое устройство может быть специально сконструировано для требуемых целей, либо оно может представлять собой универсальный компьютер, который избирательно приводится в действие или дополнительно настраивается с помощью программы, хранящейся в памяти компьютера. Такая компьютерная программа может храниться на машиночитаемом носителе данных, например, помимо прочего, на диске любого типа, включая дискеты, оптические диски, CD-ROM и магнитно-оптические диски, постоянные запоминающие устройства (ПЗУ), оперативные запоминающие устройства (ОЗУ), СППЗУ, ЭППЗУ, магнитные или оптические карты и носители любого типа, подходящие для хранения электронной информации.

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