Способ и устройство распознавания категории объекта изображения

Способ и устройство распознавания категории объекта изображения

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

Настоящее изобретение включает в себя способ распознавания категории объекта изображения, содержащий следующие этапы:

этап (S1) извлечения признаков изображения, на котором извлекают точки признаков всех образцовых изображений в N известных категориях с помощью способа извлечения точек признаков и создают соответствие "известная категория - образцовое изображение - точка признака", где N - натуральное число больше 1, каждая категория содержит по меньшей мере одно образцовое изображение;

этап (S2) кластерного анализа, на котором выполняют кластерный анализ всех извлеченных точек признаков с использованием алгоритма кластеризации и разделяют точки признаков на N подмножеств;

этап (S3) определения категории объекта, на котором определяют категорию S_n объектов для каждого из подмножеств; и

этап (S4) сбора общих признаков, на котором собирают общие признаки среди изображений в каждой категории S_n объектов с помощью алгоритма поиска, где S_n - n-ая категория объектов, и n - положительное целое число не больше N.

После этапа S4 способ может дополнительно содержать этап S5 онлайнового распознавания и категоризации изображения, на котором распознают и автоматически категоризируют изображение, которое должно быть категоризировано, этап S5 онлайнового распознавания и категоризации изображения содержит этапы:

S502, на котором выполняют такую же обработку извлечения признаков изображения над изображением, которое должно быть категоризировано, как на этапе S1, чтобы извлечь точки признаков изображения, которое должно быть категоризировано;

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

S504, на котором приписывают изображение, которое должно быть категоризировано, к категории C_n объектов, имеющей наибольшее подобие.

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

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

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

блок определения для определения категории C_n объектов для каждого из подмножеств; и

блок сбора данных для сбора общих признаков среди изображений в каждой категории C_n объектов с помощью алгоритма поиска, где C_n - n-ая категория объектов, и n - положительное целое число не больше N.

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

этап извлечения на котором выполняют такую же обработку извлечения признаков изображения над изображением, которое должно быть категоризировано, как на этапе S1, чтобы извлечь визуальные признаки низкого уровня из изображения, которое должно быть категоризировано;

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

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

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

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

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

блок определения для определения категории C_n объектов для каждого из подмножеств; и

блок сбора данных для поиска общих признаков среди изображений в каждой категории C_n объектов с помощью алгоритма поиска, где C_n - n-ая категория объектов, и n - положительное целое число не больше N.

Варианты осуществления настоящего изобретения получили следующие положительные эффекты:

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

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

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

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

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

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

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

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

Фиг. 5 - подробная блок-схема последовательности операций этапа S3 в соответствии с одним вариантом осуществления настоящего изобретения.

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

Фиг. 7 - основная блок-схема последовательности операций онлайнового (вторая часть) способ распознавания категории изображения настоящего изобретения.

Фиг. 8 - блок-схема устройства распознавания категории объекта изображения настоящего изобретения.

Фиг. 9 - Конкретный пример офлайнового автоматического распознавания образов с помощью компьютера.

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

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

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

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

Специалисты в области техники могут с легкостью обеспечить подходящую программную среду для помощи в реализации настоящего изобретения посредством использования представленной здесь идеи и языков и инструментов программирования, таких как Java, Pascal, C++, C, язык для работы с базами данных, API, SDK, компилятор, программно-аппаратное обеспечение, микрокод и т.п.

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

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

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

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

Конкретные варианты реализации для каждой части будут описаны более подробно.

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

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

Сначала каждая конкретная категория (такая как телевизор, холодильник и т.д.) в множествах изображений для N (N - натуральное число больше 1) известных категорий была определена вручную или другими средствами, и каждая категория имеет свое собственное множество изображений. Каждое множество изображений включает в себя по меньшей мере одно образцовое изображение, посредством чего может быть установлено соответствие между каждой известной категорией и каждым множеством образцовых изображений или даже каждым изображением (в дальнейшем таблица соответствия "известная категория - множество образцовых изображений”).

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

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

ЭТАП ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ

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

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

Этап S001: пропорциональное масштабирование цветного изображения в соответствии с формулой (1.1):

(1.1),

где W, H представляют ширину и высоту исходного изображения перед масштабированием, W', H' представляют ширину и высоту пропорционально масштабированного изображения, scale представляет коэффициент масштабирования, и T - порог для пропорционального масштабирования. В настоящем изобретении в пикселях в качестве единицы измерения можно установить порог T ∈ [500, 800]. Посредством многократных экспериментов автор изобретения обнаружил, что когда порог находится в пределах этого диапазона, результат является оптимальным; особенно, когда T=600, изображение может быть масштабировано до подходящего размера, и не производится какое-либо влияние на дальнейшую обработку и распознавание изображения с улучшенной эффективностью вычисления.

Затем в соответствии с формулой (1.2) линейная интерполяция в направлении X применяется к исходному изображению, и затем выполняется линейная интерполяция в направлении Y в соответствии с формулой (1.3) для получения пропорционально масштабированного изображения:

(1.2)

(1.3),

где R₁ и R₂ представляют линейно интерполированные в направлении X пиксели, x, y, x₁, y₁, x₂, y₂ являются координатами пикселей в изображении, f(*, *) представляет значение цвета пикселей, Q₁₁=(x₁, y₁), Q₁₂=(x₁, y₂), Q₂₁=(x₂, y₁), Q₂₂=(x₂, y₂) представляют четыре точки в исходном изображении, которые участвуют в вычислении масштабирования, и P представляет линейно интерполированную в направлении Y точку. В настоящем варианте осуществления после линейной интерполяции в направлении Y получено пропорционально масштабированное изображение.

Этап S002: выполнение следующей обработки двусторонней фильтрации в соответствии с формулой (1.4) над пропорционально масштабированным на этапе S001 изображением:

(1.4),

где f(x) - входное изображение, h(x) - выходное изображение, с(ξ, x) измеряет степень геометрической близости между пороговым центром x и его смежной точкой ξ, s(f(ξ), f(x)) измеряет подобие яркости пикселей между пороговым центром x и его смежной точкой ξ, и k - нормализованный параметр. В гладкой области двусторонний фильтр воплощен как стандартный фильтр сетевой области, который отфильтровывает шум посредством процесса сглаживания, такого как удаление заметных изменчивых изолированных пикселей и т.д.

Затем выполняется операция удаления цветности над входным цветным изображением в соответствии с формулой (1.5). Этот этап может быть опущен, когда не используется алгоритм SIFT.

Y=0,299*R+0,587*G+0,114*B (1.5),

где Y представляет пиксельное значение текущего пикселя после преобразования, R представляет значение красного цвета текущего пикселя, G представляет значение зеленого цвета текущего пикселя, и B представляет значение синего цвета текущего пикселя.

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

ЭТАП S1 ИЗВЛЕЧЕНИЯ ПРИЗНАКА

После выборочной предварительной обработки изображения наступает этап S1 (см. фиг. 1 и фиг. 3): извлечение соответствующего описания признака каждого изображения в известном множестве образцовых изображений для каждой категории.

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

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

Этап S101: извлечение визуальных признаков низкого уровня из предварительно обработанного изображения. Например, извлечение визуальных признаков низкого уровня может быть выполнено с использованием алгоритма SIFT (масштабно-инвариантная трансформация признаков). Алгоритм SIFT выдвинут Д. Г. Лоу (D. G. Lowe) в 1999 году и усовершенствован и заключительно сформулирован в 2004 году. Работа была опубликована в IJCV: David G. Lowe, "Distinctive image features from scale-invariant key points", International Journal of Computer Vision, 60, 2 (2004), pp.91-110. Содержания этого документа полностью включено в настоящий документ посредством цитирования и ссылки.

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

Через извлечение визуальных признаков низкого уровня компьютер может извлечь (т.е. вычислить) каждую ключевую точку признака, имеющую известную характеристику, в каждом изображении и ее соответствующий дескриптор. Затем создается соответствие (см. таблицу 1) “известная категория - множество образцовых изображений - ключевая точка признака (т.е. дескриптор)” (этап S103) на основе ранее созданной таблицы соответствия “известная категория - множество образцовых изображений”. На основе соответствия (таблицы) компьютер может идентифицировать количества ключевых точек признаков, включенных в каждую категорию и даже в каждое образцовое изображение, и дескрипторы и соответствия между ними. Таблица соответствия также может создаваться одновременно с тем или после того, как вычислена каждая ключевая точка признака. Таким образом, этап S103 может быть выполнен параллельно с этапами S101 и/или этапом S102 или последовательно после них, и таблица соответствия может быть сохранена в соответствующей памяти согласно необходимости.

ТАБЛИЦА 1
Номер известной категории	Множество образцовых изображений	Ключевая точка признака (дескриптор)
C1	I11, I12, I13...	F111, F112, F113...
C2	I21, I22, I23...	F211, F212, F213...
C3	I31, I32, I33...	F311, F312, F313...
...	...	...
Cn	In1, In2, In3…	Fn11, Fn12, Fn13...

где C_n представляет n-ю категорию объектов, C₁, ..., C_n (n≤N); I_n1, ..., I_nj представляет j-ое изображение в n-й категории объектов (j - количество изображений в категории C_n объектов); F_nj1, ..., F_njf представляет f-ую ключевую точку признака SIFT в каждом изображении I_nj, причем f - натуральное число не меньше 1.

При этом другие способы извлечения признаков изображения могут использоваться в качестве схем, альтернативных алгоритму SIFT, например, алгоритм SURF или алгоритм PCA (анализ основных составляющих)-SIFT и т.д., и эти алгоритмы применимы к настоящему изобретению.

ЭТАП S2 КЛАСТЕРНОГО АНАЛИЗА

После извлечения признака каждого образцового изображения, т.е. визуального признака низкого уровня, наступает этап S2 кластерного анализа (см. фиг. 1). Все ключевые точки признаков (т.е. дескрипторы), извлеченные из всех множеств образцовых изображений для всех категорий подвергаются кластерному анализу, и строится древоподобная структура. Древоподобная структура может быть истолкована с использованием структуры k-дерева. Этап S2 может быть реализован с помощью следующего конкретного способа (см. фиг. 4).

Все ключевые точки признаков SIFT, включенные во все образцовые изображения для всех полученных категорий объектов, кластеризируются по предварительно заданному количеству кластеров (этап S201) с помощью алгоритма кластеризации. Процесс кластеризации извлекает главную общность среди каждой категории самонастраивающимся образом, в основном отличая различные категории. Может использоваться хорошо известный и используемый алгоритм кластеризации, например, метод k-средних (k-means). Информацию об алгоритме кластеризации k-средних можно найти в следующих документах: MacQueen, J. B., Some methods for classification and analysis of multivariate observations, in Proc. 5th Berkeley Symp. Mathematical Statistics and Probability, 1967, pp. 281-297. Подробное введение можно дополнительно найти на следующих веб-сайтах, и их содержание включено в настоящий документ посредством цитирования.

1. http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html

2. http://wenku.baidu.com/view/179d21a4f524ccbff1218482.html

Другие способы кластеризации также могут быть применены к настоящему изобретению при условии, что они могут категоризировать пространственно смежные данные в одну и ту же категорию. Альтернативные алгоритмы кластеризации включают в себя, но без ограничения: алгоритм k-modes, алгоритм k-Prototype, иерархический способ кластеризации, способ выборки с максимальным расстоянием, муравьиный алгоритм кластеризации, алгоритм нечеткой кластеризации и т.д.

В этом случае настоящее изобретение описывает процесс кластеризации с использованием алгоритма k-средних в качестве примера. Алгоритм k-средних категоризирует n объектов данных по k кластерам на основе предварительно установленного значения k. Объекты в одном и том же кластере имеют высокое подобие, тогда как объекты в разных кластерах имеют низкое подобие. Подобие кластеров вычисляется посредством "центрального объекта" (центра тяжести), полученное посредством средннго из объектов данных в каждом кластере. Например, в настоящем изобретении, когда известное и предварительно установленное количество категорий объектов равно N, диапазон k представляет собой k ∈ (1, N), или k меньше общего количества точек признаков, которые участвуют в кластеризации. В настоящем варианте осуществления выбрано, что k ∈ (1,10), и обычно k не больше 10. Выбор k может быть определен на основе оптимального значения, полученного опытным путем или через тесты в соответствии с фактическими потребностями.

Рабочий процесс алгоритма k-средних представляет собой следующее: сначала случайно выбираются k объектов в качестве начальных центров кластеризации из x объектов данных; остальные объекты данных распределяются по центрам кластеризации, наиболее подобным с ними (ближайшим в пространственном расстоянии), соответственно на основе их подобия (пространственных расстояний) с центрами кластеризации.

Конкретно для варианта осуществления настоящего изобретения множество дескрипторов всех ключевых точек признаков, извлеченных из всех изображений, подвергается кластерному анализу. При этом на начальной стадии кластеризации k-средних центры кластеризации сначала могут быть определены случайным образом. Например, когда выбрано, что k=2, случайным образом выбираются дескрипторы двух ключевых точек признаков в качестве начальных центров кластеризации. Посредством вычисления евклидова расстояния между дескрипторами ключевых точек признаков, которые недавно присоединились, и предварительно выбранными двумя начальными центрами кластеризации, дескрипторы ключевых точек признаков, которые недавно присоединились, приписываются к категории (т.е. к кластеру), которая имеет минимальное евклидово расстояние. Таким образом, например, через итерационный подход осуществляется обход всех точек признаков, пока все точки признаков или дескрипторы не будут вовлечены в кластеризацию, и в конечном счете все извлеченные ключевые признаки кластеризируются в два кластера вокруг двух начальных центров кластеризации. Затем средние значения (средние значения векторов дескрипторов) всех дескрипторов в каждом кластере повторно вычислены для этих двух кластеров, чтобы получить новый центр кластеризации. Затем вновь полученный центр кластеризации и предыдущий (смежный предыдущий) центр кластеризации сравниваются, чтобы вычислить разность (например, дисперсию) между ними. Когда разность равна нулю или достигает предварительно заданного порога, процесс кластеризации может быть закончен. Иначе новый центр кластеризации, определенный посредством текущей итерации, может использоваться в качестве начального центра кластеризации для следующей итерации, чтобы постоянно корректировать центр кластеризации. Упомянутый выше процесс итерации или кластеризации может повторяться, пока центр кластеризации не перестает изменяться или изменяется мало (т.е. удовлетворяет предварительно установленному порогу).

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

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

Древоподобная структура ключевых точек признаков (или дескрипторов), т.е. k-дерево, может строиться (этап S202) одновременно с выполнением алгоритма кластеризации или после него. Таким образом, функция кластерного анализа на этапе S2 может быть реализована посредством объединения этапов S201 и S202 в один этап или в один функциональный модуль в конкретном варианте осуществления.

Конкретно для одного варианта осуществления при k=2 (т.е. двоичное дерево) в качестве примера все визуальные признаки низкого уровня всех образцовых изображений категории объектов, т.е. из ключевых точек признаков SIFT в упомянутом выше варианте осуществления строится корневой узел n1 двоичного дерева, и упомянутый выше кластерный анализ выполняется над всеми ключевыми точками признаков в узле n1.

Множество кластеров, имеющее относительно большее количество ключевых точек признаков в узле n1 после кластеризации, служит в качестве левого дочернего узла n2 корневого узла n1, тогда как множество кластеров, имеющее относительно меньшее количество ключевых точек признаков в узле, служит в качестве правого дочернего узла n3 корневого узла n1. Остальное выполняется таким же образом, последующий кластерный анализ выполняется над узлами n2 и n3 соответственно, пока количество концевых узлов двоичного дерева не станет равно известному и предварительно установленному общему количеству N категорий объектов, т.е. заключительное количество концевых узлов должно быть равно N. Другими словами, все ключевые точки признаков всех изображений во всех категориях объектов разделены на N подмножеств.

При k=2, например, структурная диаграмма окончательно построенного двоичного дерева следующая:

В предположении, что каждый узел k-дерева, построенного на этапе S2, выражен следующим образом:

ni(C₁, I₁₁, F₁₁₁, ..., F_11f, f₁₁, ..., I_1j, F_1j1, ..., F_1jf, f_1j; ...;C_n, I_n1, F