Способ автоматизированного анализа векторных изображений
METHOD OF AUTOMATED VECTOR IMAGE ANALYSIS

Область техники, к которой относится изобретение.
Изобретение относится к автоматизированному анализу векторных изображений и может быть использовано при разработке новых и совершенствовании существующих систем проверки векторных изображений на совпадение с эталонными векторными изображениями.
Уровень техники.
В настоящее время весьма остро стоит проблема так называемого перехвата данных. Такая проблема может встретиться в случае отслеживания документов, в т.ч. содержащих изображения, проходящих по сети компании, на предмет наличия в них конфиденциальной информации.
В настоящее время известно несколько систем или способов, позволяющих решить эту проблему.
Например, в патенте России №2420800 (приоритет от 30.06.2009, опубл. 10.06.2011) раскрыт способ поиска похожих по смысловому содержимому электронных документов, в котором задают правила формирования уникальных слов, взвешиваются уникальные слова и связи между ними, строят на основе этого семантическую сеть и сравнивают семантические сети документов. Этот способ достаточно трудоемок и пригоден лишь в ограниченной области.
Известен способ индексации и поиска цифровых изображений (патент на изобретение РФ №2510935, приоритет от 23.09.2011, опубл. 10.04.2014). Способ, описанный в данном патенте, подходит для поиска изображений определенной категории, в том числе цветовой, но при этом не подходит для задачи поиска конкретного изображения в обширной базе данных, где может присутствовать много изображений с одинаковыми преобладающими цветами. Так как автор патента ставил задачу поиска изображений, подходящих под некоторое описание, он сам указал в качестве недостатка некоторых других методов тот факт, что они могут классифицировать изображения с похожими преобладающими цветами как совершенно различные. В то же время изобретение решает задачу поиска конкретного изображения с поправкой на искажения, возникающие при его сохранении в разных форматах и разных масштабах. При такой постановке задачи недостатком становится именно невозможность различить изображения с похожими характеристиками.
Раскрытие изобретения.
Таким образом, существует потребность в расширении арсенала технических средств за счет создания сравнительно быстрого и универсального способа, который позволил бы выявлять в потоке данных векторные изображения, схожие с эталонными и который бы преодолевал недостатки известных решений.
Для решения этой задачи и получения указанного технического результата в изобретении предложен способ автоматизированного анализа векторных изображений, заключающийся в том, что:
1. Создают специализированную базу данных эталонных изображений, специализация которой заключается в том, что данные из эталонных изображений хранятся специальным образом. Для каждого хеш-значения, отражающего взаимное расположение двух примитивов из эталонного векторного изображения, создают записи вида:
<хеш> -> {список документов, в которых содержится этот хеш}
Для создания такой базы данных выполняют следующие шаги:
1) каждому эталонному изображению присваивают уникальный идентификатор;
2) каждый электронный файл эталонного векторного изображения преобразуют в заранее заданный формат, содержащий векторные примитивы (специально разработанный промежуточный формат, в который преобразуются векторные изображения из разных форматов, например dwg или cdw);
3) выбирают некоторое подмножество из множества пар примитивов изображения;
4) для каждой пары из выбранного подмножества вычисляют хеш-значение (подробнее описано ниже);
5) вычисляют хеш от какой-либо комбинации хеш-значений, полученных в п. 1.4 с помощью какой-либо хеш-функции;
6) вычисленный в п. 1.5 хэш добавляют в множество хеш-значений эталона;
7) проверяют условие остановки, если оно выполнено, переходят к следующему пункту, иначе возвращаются к п. 1.3;
8) обходят все подготовленные эталонные документы и хеш-значением и идентификаторами эталонных документов заполняют специализированную базу данных и сохраняют ее;
9) в отдельную таблицу базы данных для каждого эталонного изображения сохраняют минимальные пороги срабатывания.
2. Когда на анализ поступает файл, содержащий векторное изображение, то производят следующие действия:
1) изображение преобразуют в заранее заданный формат (специально разработанный промежуточный формат, в который преобразуются векторные изображения из разных форматов, например dwg или cdw);
2) выбирают некоторое подмножество из множества пар примитивов изображения;
3) для каждой пары из выбранного подмножества вычисляют хеш-значение (подробнее описано ниже);
4) вычисляют хеш от какой-либо комбинации хеш-значений, полученных в п. 2.3 с помощью хеш-функции;
5) проверяют условие остановки, если оно выполнено, переходят к следующему пункту, иначе возвращаются к п. 2.2;
6) производят поиск полученных в п. 2.4 хэш-значений базе данных, полученной в п. 1, и формируют список документов, в которых содержатся вычисленные хеш-значения и некоторый список факторов ранжирования для каждого такого документа;
7) на основе полученных факторов для каждого эталонного документа вычисляют степень совпадения с анализируемым документом по некоторому заранее заданному правилу (по формуле релевантности);
8) возвращают массив найденных идентификаторов эталонных документов, для которых был превышен порог релевантности.
3. Алгоритм вычисления хеш-значения для пар примитивов:
Пусть векторное изображение представлено в виде набора примитивов (отрезки, ломаные, дуги и т.д.),
Р - множество типов примитивов. Для каждой пары типов примитивов вводят функцию снятия отпечатка от пары примитивов:
f(T, Т) -> Н,
где Т - тип примитива (элемент множества Р),
Н - некоторое множество целых чисел (на практике - множество хеш-значений).
Физический смысл функций f - число, однозначно характеризующее взаимное расположение двух примитивов на векторном изображении. Функции должны быть устойчивы к повороту, сдвигу и масштабированию.
Изобретение может быть реализовано в любой вычислительной системе, например в персональном компьютере, на сервере и т.п.
Способ автоматизированного анализа векторных изображений по изобретению предназначен для осуществления так называемого копирайтного анализа (английский аналог - fingerprint detection), задачей которого является установление схожести векторных изображений с изображениям, переданным ранее в базу данных (библиотеку) в качестве эталонных.