ИСПОЛЬЗОВАНИЕ ЯЗЫКА SQL ДЛЯ ЗАДАЧИ КЛАССИФИКАЦИИ В ПРОЦЕССЕ ОБНАРУЖЕНИЯ ЗНАНИЙ В БАЗАХ ДАННЫХ

Введение.

В настоящее время все большее распространение получают системы автоматического распознавания изображений (машинное зрение, распознавание лиц по фото и видео и т.п.). Несмотря на широкую коммерциализацию рынка программных продуктов распознавания, исследования в данной области не прекращаются, так как эффективность работы алгоритмов, реализующих распознавание изображений, далека от идеала. Одним из известных способов повышения скорости распознавания являются алгоритмы приближенного поиска ближайшего соседа (approximate nearest neighbor), которые возвращают эталоны, с большой вероятностью являющиеся ближайшим  (в смысле  расстояний Манхэттена,  Евклида и Хи-квадрат между анализируемыми признаками) соседом к входному изображению, но не требуют полного перебора всей базы данных эталонов [1].

Цель настоящей работы состоит в экспериментальном  исследовании повышения вычислительной эффективности систем обнаружения знаний в базах данных на основе реализации методов классификации в виде хранимых процедур SQL. Ставятся и решаются задачи реализации метода поиска ближайшего соседа в виде хранимых процедур SQL, которые реализуют классификацию изображений, для различных расстояний: Манхэттена, Евклида и Хи-квадрат, и проведения экспериментальных исследований с помощью тестового проекта распознавания изображений, который производит свою работу с данными базы лиц FERET.

Реализация алгоритмов приближенного поиска ближайших соседей в виде хранимых процедур SQL. Для решения задачи классификации в процессе обнаружения знаний в базах данных использовалась задача распознавания изображений методом поиска ближайшего соседа. Прежде всего, для входного изображения распознаваемого объекта X с высотой U и шириной V осуществляется предварительная обработка (нормирование по освещенности, эквализация гистограмм, медианная фильтрация и т.п.). Далее выполняется его сегментация на

Для хранения информации обо всех эталонах была использована модель «Entity-Attribute-Value» (EAV) [3], согласно которой признаки изображений хранятся в таблице, состоящей из трех атрибутов:

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

2)   Attribute - это номер атрибута (признака). Количество признаков соответствует количеству атрибутов.

3)   Value - это значение признака с номером Attribute для изображения с номером Entity.

Первичный ключй представляет собой пару Entity-Attribute. Для такой модели с помощью СУБД PostgreSQL была создана база данных, которая включает в себя три таблицы (Рисунок 1):

·   1-я таблица содержит в себе id или имя класса;

·   2-я таблица создана по модели EAV и содержит в себе id изображения-эталона, номера атрибутов и их значения;

·   3-я таблица аналогична 2ой таблице, но содержит в себе значения признаков тестовых изображений для проведения исследований.

Далее с помощью программы Eclipse значения признаков и имен классов были перенесены в созданную базу данных из файлов FERET.

Метод поиска ближайшего соседа реализован в виде хранимой процедуры SQL, для уменьшения времени работы классификации изображений. Далее в таблице 1 представлен пример хранимой процедуры SQL, которая реализует классификацию изображений для расстояния Манхеттена без эффекта выравнивания ( D = 0 ).

Результаты экспериментального исследования.

Для проведения данного исследования использовался проект на языке программирования C++ в Visual Studio 2010, который реализует тестовое распознавание изображений или, другими словами, он классифицирует изображение по его признакам. Программа считывает признаки тестового изображения и считывает признаки изображения-эталона, далее методом поиска ближайшего соседа находит ближайший класс из признаков эталона для тестируемого изображения, тем самым проект производит распознавание изображения.

 Для проведения эксперимента используется стандартная база данных фотографий лиц FERET, которая включает в себя изображения 2413 изображений лиц, представляющих собой 856 людей. Для данной работы использовались данные о 1288 людях. Часть данных изображений базы данных FERET была описана с помощью методики компонентных гистограмм HOG, которая была модифицирована специально для данной библиотеки. Таким образом, для данного исследования использовались файлы базы данных FERET, которые содержат информацию о классах и градиентах гистограмм.  Информация в этих файлах получена путем преобразования. При процессе распознавания изображений каждое из них разбито на квадратную сетку размером 10х10, в каждой клетке вычисляются ориентации градиента и далее высчитывается их гистограмма из 8-ми значений. Таким образом, у каждого изображения получается 800 значений признаков в векторе признаков, с которыми и оперирует метод поиска ближайшего соседа.

Экспериментальное исследование проводилось для двух видов классификаций изображений: с эффектом выравнивания (∆=1) и без него (∆=0). При ∆=0 выравнивания гистограмм при поиске ближайшего соседа не происходит, то есть сравниваются только 8 значений гистограммы тестового изображения с 8-ми значениями гистограммы изображения-эталона. При ∆=1 происходит выравнивание гистограмм, то есть с 8 признаками тестового изображения сравниваются 9 признаков изображения-эталона. Таким образом, получается более высокая точность распознавания.

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

Все основные результаты эксперимента представлены в Табл.2.

Заключение.

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

Благодарности.

Исследование выполнено в Национальном исследовательском университете «Высшая школа экономики» за счет средств гранта Российского научного фонда (проект № 14-41-00039).

Список литературы

1.     Muja M., Lowe D., Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration // Proc. of International Conference on Computer Vision Theory and Applications (VISAPP'09).– 2009.– 331-340

2.     Savchenko A.V. Nonlinear Transformation of the Distance Function in the Nearest Neighbor Image Recognition // In Proc. of Int. Conf. on Computational Modeling of Objects Presented in Images (CompIMAGE 2014), LNCS.– 2014.– Vol. 8641.– P.261-266.

3.     Wróblewski J., Stawicki S., Kryszkiewicz M. : SQL - Based KDD with Infobright’ s RDBMS: Attributes, Reducts, Trees; LNAI 8537, pp. 28–41 (2014).