Дипломная работа на тему Разработка автоматизированной веб-ориентированной системы составления каталога товаров при поиске по изображениям

ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ДИПЛОМНАЯ РАБОТА

Тема работы: “Разработка автоматизированной веб-ориентированной системы составления каталога товаров при поиске по изображениям”

студента Троепольского Алексея Сергеевича

Аннотация

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

Ключевой частью работы является построение алгоритма сравнения товаров по их изображениям. В основе алгоритма лежит SURF – метод, в ходе которого производится поиск особых точек на изображении и составляются их дескрипторы.

Апробация алгоритма проведена по данным нескольких магазинов.

Оглавление

  • Введение
  • 1. Обзор объекта и методов исследования
  • 1.1 Описание объекта исследования
  • 1.2 Описание привлекаемых методов
  • Метод SURF
  • Интегральное представление изображения
  • Вычисление матрицы Гессе
  • Достижение инвариантности относительно масштаба
  • Нахождение локального максимума гессиана
  • Нахождение ориентации особой точки
  • Вычисление дескриптора особой точки
  • Среда разработки и причины ее выбора
  • 2. Методика
  • 2.1 Методика получения информации с электронных ресурсов
  • 2.2 Сравнительный анализ метода SURF
  • 3. Программная реализация. Апробация методики
  • 3.1 Описание программного обеспечения
  • Заключение

Введение

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

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

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

В качестве объекта исследования рассматривается сеть магазинов aliexpress.

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

1. Обзор объекта и методов исследования

1.1 Описание объекта исследования

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

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

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

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

алгоритм дескриптор изображение программный

1.2 Описание привлекаемых методов

Метод SURF

SURF решает две задачи – поиск особых точек изображения и создание их дескрипторов, инвариантных к масштабу и вращению. Это значит, что описание ключевой точки будет одинаково, даже если образец изменит размер и будет повернут (здесь и далее мы будем говорить только о вращении в плоскости изображения). Кроме того, сам поиск ключевых точек тоже должен обладать инвариантностью. Так, что бы повернутый объект сцены имел тот же набор ключевых точек, что и образец.

Метод ищет особые точки с помощью матрицы Гессе. Детерминант матрицы Гессе (т. н. гессиан) достигает экстремума в точках максимального изменения градиента яркости. Он хорошо детектирует пятна, углы и края линий.

Гессиан инвариантен относительно вращения. Но не инвариантен масштабу. Поэтому SURF использует разномасштабные фильтры для нахождения гессианов.

Для каждой ключевой точки считается направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе.

Градиент в точке вычисляется с помощью фильтров Хаара.

После нахождения ключевых точек, SURF формирует их дескрипторы. Дескриптор представляет собой набор из 64 (либо 128) чисел для каждой ключевой точки. Эти числа отображают флуктуации градиента вокруг ключевой точки (что понимается под флуктуацией – рассмотрим ниже). Поскольку ключевая точка представляет собой максимум гессиана, то это гарантирует, что в окрестности точки должны быть участки с разными градиентами. Таким образом, обеспечивается дисперсия (различие) дескрипторов для разных ключевых точек.

Флуктуации градиента окрестностей ключевой точки считаются относительно направления градиента вокруг точки в целом (по всей окрестности ключевой точки). Таким образом, достигается инвариантность дескриптора относительно вращения. Размер же области, на которой считается дескриптор, определяется масштабом матрицы Гессе, что обеспечивает инвариантность относительно масштаба.

Флуктуации градиента также считаются с помощью фильтра Хаара.

Рис. 1 Схема работы метода SURF

Интегральное представление изображения

Для эффективного вычисления фильтров Гессе и Хаара – используется интегральное представление изображений.

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

Где I (i,j) – яркость пикселов исходного изображения.

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

Где ABCD – интересующий нас прямоугольник.

Вычисление матрицы Гессе

Обнаружение особых точек в SURF основано на вычислении детерминанта матрицы Гессе (гессиана).

Матрица Гессе для двумерной функции и ее детерминант определяется следующим образом:

Значение гессиана используется для нахождения локального минимума или максимума яркости изображения. В этих точках значение гессиана достигает экстремума.

На картинке видно, что особые точки (очерченные цветными кругами) представляют собой локальные экстремумы яркости изображения. Мелкие точки не распознаны как особые, из-за порогового отсечения по величине гессиана.

Рис. 2. На рисунке показаны концы отрезка, распознанные как ключевые точки, с помощью матрицы Гессе.

Теоретически, вычисление матрицы Гессе сводится к нахождению Лапласиана Гауссиан. По сути, элементы матрицы Гессе вычисляются как свертка (сумма произведений) пикселов изображения на фильтры, изображенные на рисунке:

На рисунке изображены дискретизированные фильтры для нахождения четырех элементов матрицы Гессе (четвертый – совпадает с третьим, поскольку матрица Гессе симметрична). Фильтры имеют пространственный масштаб 9×9 пикселов. Темные участки соответствуют отрицательным значениям фильтра, светлые – положительным.

Однако SURF не использует лапласиан гауссианы в том виде, который изображен на рисунке. Во-первых, по утверждению авторов, дискретизированный лапласиан гауссианы имеет довольно большой разброс значения детерминанта, при вращении образца (напомним, что в идеале гессиан должен быть инвариантен к вращению). Особенно детерминант “проседает” в районе поворота на 45 граудсов. А во-вторых, и это главное, фильтр для лапласиана гауссианы имеет непрерывный характер. Почти все пикселы фильтра имеют разные величины яркости. А это не позволяет эффективно использовать такой мощный механизм расчёта, как интегральную матрицу изображения.

Поэтому SURF использует бинаризованную аппроксимацию лапласиана гауссиан (авторы назвали его Fast-Hessian):

На рисунке изображены фильтры, используемые для нахождения матрицы Гессе в SURF. Белые области соответствуют значению +1, черные – 2 (на третьем фильтре – 1), серые – нулевые. Пространственный масштаб – 9×9 пикселов. Этот фильтр более устойчив к вращению, и его можно эффективно вычислить с помощью интегральной матрицы.

Таким образом, в SURF, гессиан вычисляется так:

Где Dxx, Dyy, Dxy – свертки по фильтрам, изображенным на рисунке вверху. Коэффициент 0.9 имеет теоретическое обоснование, и корректирует приближенный характер вычислений.

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

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

Кроме того, свойства гессиана таковы, что он достигает максимума, как в точке белого пятна на черном фоне, так и черного пятна на белом фоне. Таким образом, метод обнаруживает и темные, и светлые особенности изображения.

Метод распознает как светлые точки на темном фоне, так и темные точки на светлом фоне.

Достижение инвариантности относительно масштаба

Как уже отмечалось, гессиан не инвариантен относительно масштаба. Это значит, что для одного и того же пиксела, гессиан может меняться при изменении масштаба фильтра. Решение этой проблемы только одно – перебирать различные масштабы фильтров и поочередно их применять к данному пикселу.

Из соображений симметрии и дискретизации, размер фильтра Fast-Hessian не может принимать произвольные значения. Допустимые размеры этого фильтра таковы (начиная с минимального): 9, 15, 21, 27 и так далее, с шагом 6. Однако, на практике, постепенно увеличивать размер фильтра на 6 – не выгодно, потому что для крупных масштабов шаг 6 оказывается слишком мелким, а фильтры – избыточными. Поэтому (и по некоторым другим причинам), SURF разбивает все множество масштабов на так называемые октавы. Каждая октава покрывает определенный интервал масштабов, и имеет свой характерный размер фильтра.

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

Рис. 3. Рисунок показывает две ключевые точки разного масштаба в одной точке изображения.

Если мы будем искать максимум среди всех гессианов, по всем масштабам, то мы бы нашли только один из максимумов, в то время как их может быть несколько. Один – в одном масштабе, другой – в другом.

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

На рисунке показаны первые три октавы метода SURF. Цифры в прямоугольниках показывают размер фильтра Fast-Hessian. Логарифмическая шкала снизу – показывает масштабы, покрываемые октавами.

Шаг размера фильтра в первой октаве – составляет 6, во второй – 12, в третьей – 24 и так далее.

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

Теоретически, масштабы бесконечны, однако в реальных изображениях, они вполне конечны, и основная масса сосредоточена в интервале от 1 до 10 (по данным авторов метода). Для покрытия этого диапазона достаточно четырех октав. Плюс добавляется одна или две октавы для покрытия больших масштабов. Итого, используется 5-6 октав. Теоретически, этого вполне достаточно для покрытия всевозможных масштабов на изображении 1024×768 пикселов.

Нахождение локального максимума гессиана

Для нахождения локального максимума гессиана, используется так называемый метод соседних точек 3x3x3.

Его смысл понятен из рисунка ниже:

Пиксел, помеченный крестиком считается локальным максимумом, если его гессиан больше чем у любого его соседа в его масштабе, а также больше любого из соседей масштабом меньше и масштабом больше (всего 26 соседей).

Исходя из такого определения локального максимума, понятно, что октава должна содержать не менее трех фильтров, иначе мы не сможем определить факт нахождения локального максимума гессиана внутри октавы.

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

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

Поэтому, несмотря на то, что октава содержит четыре фильтра, на самом деле каждая октава (кроме первой) считает только два характерных для нее размера, два других – всегда можно взять из предыдущих октав. Первая же октава вынуждена считать все четыре своих фильтра.

Итак, после нахождения максимального гессиана методом соседних точек 3x3x3, мы нашли пиксел, в котором этот максимум достигается. Однако, поскольку, октава перебирает не все точки изображения, то истинный максимум может не совпадать с найденным пикселом, а лежать где-то рядом, в соседних пикселах.

Для нахождения точки истинного максимума, используется интерполирование найденных гессианов куба 3x3x3 квадратичной функцией. Далее, вычисляется производная (методом конечных разностей соседних точек). Если она близка к нулю – мы в точке истинного максимума. Если производная велика – сдвигаемся в сторону ее уменьшения, и повторяем итерацию, до тех пор пока производная не станет меньше заданного порога. Если в процессе итераций мы отходим от начальной точки слишком далеко, то это считается ложным максимумом, и точка больше не считается особой.

Нахождение ориентации особой точки

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

Сначала, вычисляются точечные градиенты в пикселах, соседних с особой точкой. Для рассмотрения берутся пикселы в окружности радиуса 6s вокруг особой точки. Где s – масштаб особой точки. Для первой октавы берутся точки из окрестности радиусом 12.

Для вычисления градиента, используется фильтр Хаара. Размер фильтра берется равным 4s, где s – масштаб особой точки. Вид фильтров Хаара показан на картинке:

Рис. 4. Фильтры Хаара. Черные области имеют значения – 1, белые +1.

Фильтры Хаара дают точечное значение перепада яркости по оси X и Y соответственно. Поскольку фильтры Хаара имеют прямоугольную форму, их значения легко считаются с помощью интегральной матрицы. Для расчёта одного фильтра произвольного размера требуется всего 6 операций.

Значения вейвлета Хаара dX и dY для каждой точки умножаются на вес и запоминаются в массиве. Вес определяется как значение гауссианы с центром в особой точке и сигмой равной 2s. Взвешивание на гауссиане необходимо для отсечения случайных помех на далеких от особой точки расстояниях.

Далее, все найденные значения dX и dY, условно наносятся в виде точек на плоскость, как показано на рисунке:

Рис. 5. На рисунке показаны все найденные градиенты в виде точек в пространстве dXdY.

Далее, берется угловое окно (показано серым на рисунке) размером р/3, и вращается вокруг центра координат. Выбирается такое положение окна, при котором длина суммарного вектора для попавших в окно точек – максимальна. Вычисленный таким образом вектор нормируется и принимается как приоритетное направление в области особой точки.

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

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

Вычисление дескриптора особой точки

Дескриптор представляют собой массив из 64 (в расширенной версии 128) чисел, позволяющих идентифицировать особую точку. Дескрипторы одной и той же особой точки на образце и на сцене должны примерно совпадать. Метод расчета дескриптора таков, что он не зависит от вращения и масштаба.

Для вычисления дескриптора, вокруг особой точки формируется прямоугольная область, имеющая размер 20s, где s – масштаб в котором была найдена особая точка. Для первой октавы, область имеет размер 40×40 пикселов. Квадрат ориентируется вдоль приоритетного направления, вычисленного для особой точки.

Дескриптор считается как описание градиента для 16 квадрантов вокруг особой точки.

Далее, квадрат разбивается на 16 более мелких квадрантов, как показано на рисунке. В каждом квадранте берется регулярная сетка 5×5 и для точки сетки ищется градиент, с помощью фильтра Хаара. Размер фильтра Хаара берется равным 2s, и для первой октавы составляет 4×4.

Следует отметить, что при расчёте фильтра Хаара, изображение не поворачивается, фильтр считается в обычных координатах изображения. А вот полученные координаты градиента (dX,dY) поворачиваются на угол, соответствующий ориентации квадрата.

Итого, для вычисления дескриптора особой точки, нужно вычислить 25 фильтров Хаара, в каждом из 16 квадрантов. Итого, 400 фильтров Хаара. Учитывая, что на фильтр нужно 6 операций, выходит, что дескриптор обойдется минимум в 2400 операций.

После нахождения 25 точечных градиента квадранта, вычисляются четыре величины, которые собственно и являются компонентами дескриптора:

Две из них есть просто суммарный градиент по квадранту, а две других – сумма модулей точечных градиентов.

Рис. 6. На рисунке показано поведение этих величин для разных участков изображений

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

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

Плюс к дескриптору, для описания точки используется знак следа матрицы Гессе, то есть величина sign (Dxx+Dyy). Для светлых точек на темном фоне, след отрицателен, для темных точек на светлом фоне – положителен. Таким образом, SURF различает светлые и темные пятна.

На картинке показаны особые точки изображения. Зеленая линия показывает характерное направление для особой точки. Синий цвет окружности показывает положительный след матрицы Гессе, красный – отрицательный след.

Среда разработки и причины ее выбора

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

Разработка модулей, а также пользовательского интерфейса приложения будет осуществляться на языке программирования C# в среде разработки Microsoft Visual Studio 2011 beta. Это одна из самых мощных и систем, позволяющая на самом современном уровне создавать как отдельные прикладные программы Windows, так и разветвленные комплексы, предназначенные для работы в корпоративных сетях и в Интернет. Пользовательский интерфейс этой среды служит для организации взаимодействия с программистом и включает в себя ряд окон, содержащих различные элементы управления. С помощью средств интегрированной среды разработчику удобно проектировать интерфейсную часть приложения, а также писать программный код и связывать его с элементами управления. В интегрированной среде разработки проходят все этапы создания приложения, включая отладку.

Microsoft Visual Studio 2011 – это комбинация нескольких важнейших технологий:

1. высокопроизводительный компилятор в машинный код;

2. объектно-ориентированная модель компонент;

3. визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов.

Разработка приложений в Microsoft Visual Studio 2011 осуществляется с применением объектно-ориентированного программирования (ООП) и визуального программирования. ООП и визуальное программирование позволяют создавать прикладные программы самого разного назначения. Это позволяет разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды разработки. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует.

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

Хранение информации будет осуществляться при помощи СУБД MS SQL Server 2008. Эта система отталкивается от концепции платформы данных Майкрософт: она упрощает управление любыми данными в любом месте и в любой момент времени. Она позволяет хранить в базах данных информацию, полученную из структурированных, полуструктурированных и неструктурированных источников, таких как изображения и музыка. В SQL Server 2008 имеется большой набор интегрированных служб, расширяющих возможности использования данных: вы можете составлять запросы, выполнять поиск, проводить синхронизацию, делать отчеты, анализировать данные. Все данные хранятся на основных серверах, входящих в состав центра обработки данных. К ним осуществляется доступ с настольных компьютеров и мобильных устройств. Таким образом, существует полный контроль над данными независимо от того, где я их сохранил. Так же система SQL Server 2008 позволяет обращаться к данным из любого приложения, разработанного с применением технологий Microsoft.net и Visual Studio, а также в пределах сервисно-ориентированной архитектуры и бизнес-процессов – через Microsoft BizTalk Server. Сотрудники, отвечающие за сбор и анализ информации, могут работать с данными, не покидая привычных приложений, которыми они пользуются каждый день, например приложений выпуска 2007 системы Microsoft Office. SQL Server 2008 позволяет создать надежную, производительную, интеллектуальную платформу, отвечающую всем требованиям по работе с данными.

2. Методика

2.1 Методика получения информации с электронных ресурсов

В связи с отсутствием на рассматриваемом сайте API функций для получения информации необходимо загружать страницы товарных позиций и извлекать информацию непосредственно со страницы, для этого необходим программный доступ к элементам страницы. Также необходимо учесть, что часть информации на странице подгружаются с сайта с помощью технологии Ajax, при выполнении определенных скриптов. В связи с этим обычных Http запросов будет недостаточно, необходимо обеспечить выполнение этих скриптов на странице. Учитывая все вышесказанные факты в качестве объекта, получающего страницу с сайта, был выбран WebBrowser, поставляемый вместе с Visual Studio.

Для удобства разработки был написан модуль расширений для WebBrowser и элементов DOM (HtmlElement) позволяющие дожидаться загрузки документа, загрузки определенных элементов DOM с определенными значениями id,class, tagName, позволяют делать выборку из непосредственных вложенных элементов и в каскадном режиме элементов, определять их классы.

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

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

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

Применение метода SURF для поиска групп одинаковых товаров.

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

Метод SURF состоит из двух этапов.

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

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

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

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

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

2.2 Сравнительный анализ метода SURF

Метод SURF отличается от других подобных методов быстротой исполнения и качеством. Он обеспечивает инвариантность относительно масштабирования, небольшого поворота, потере качества и остается эффективным при наличии шумов.

Мною был реализован метод на языке C#, что позволяет обеспечить оптимизацию кода под архитектуру процессора, на которой исполняется данный метод.

Для достаточно большого изображения с разрешением 1024Ч768 и большим количеством особых точек (около 1000) метод обрабатывает изображение около 2х секунд.

Подобная реализация библиотеки, реализованная на языке C++ и скачанная с сайта sourceforge.com, производит эти вычисления в 2 раза дольше.

В связи с этим можно считать выбор данного метода и его реализации удачным.

3. Программная реализация. Апробация методики

3.1 Описание программного обеспечения

Для обработки данных была разработана программа на языке программирования C#, в среде программирования Microsoft Visual Studio 2011 Ultimate Edition beta. Для хранения данных была использована СУБД MS SQL Server 2008 Express Edition.

Программа обрабатывает информацию следующего вида:

1. Страница, с данными о товарной позиции.

1.1 Название товара.

1.2 Ссылка на товар

1.3 Категория товара

1.4 Цена товара

1.5 Цена доставки

1.6 Параметры товара

1.7 Форм-фактор посылки.

1.8 Главное изображение

1.9 Все остальные изображения.

1.10 Отзывы, оставленные покупателями

1.11 Полная информация о покупателях.

2. Главное изображение товара при составлении дескрипторов особых точек для последующего сравнения.

Результатами работы приложения является:

1. Заполненная база данных о товарах.

2. Составленные группы одинаковых товаров.

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

На следующем рисунке представлена структурная схема приложения:

Рисунок 1. Структурная схема приложения

На рисунке 2 представлена структура работы приложения.

Рис. 3. Структура работы приложения

Основные модули, описывающие работу приложения.

1. Program – главный модуль приложения, отвечающий за его запуск.

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

3. BrowserExtentionмодуль, содержащий расширения для работы с браузером.

4. Parser – модуль, отвечающий за парс товаров

5. CompareWorker – модуль, отвечающий за разбиение товаров на группы.

6. SURF – модуль, отвечающий за реализацию метода SURF.

7. StringCompareмодуль, отвечающий за реализацию метода нечеткого сравнения строк

8. DBWorkerмодуль, отвечающий за работу с базой данных

9. UIмодуль отвечающий за пользовательский интерфейс

10. Logerмодуль, отвечающий за запись лога.

11. SettingsWorkerкласс для чтения и записи настроек программы.

Описание классов.

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

Класс Shop содержит поля для представления магазина.

Класс Product содержит поля для представления товара.

Класс ProductImage содержит поля для представления изображения товара.

Класс Category содержит поля для представления категории товаров.

Класс SubCategory содержит поля для представления подкатегории товара.

Класс MarketUser содержит поля для представления покупателя.

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

Класс ProductInfoForCompare содержит поля и методы для сравнения товаров.

Класс IdenticalProductGroup инкапсулирует в себе данные для построения группы одинаковых товаров.

Класс DBWorker предназначен для работы с базой данных.

Класс ShopValidater предназначен для выявления существующих магазинов.

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

Класс ShopParser предназначен для асинхронного извлечения товарных позиций из магазина.

Класс ParseSession предназначен для запоминания и управления данными о процессе парса, для возможности продолжения его в случае отключения электроэнергии или в других нештатных ситуациях.

Класс AliExpressParser, содержащий объекты классов ParallelShopValidater, ShopParser, DBWorker предназначен для инициализации и управления этими объектами.

Класс FindWorker предназначен для поиска товаров в базе по изображениям.

Приведем структуру класса Shop:

class Shop

{

int id; // идентификатор магазина

bool startParse=false; // флаг начала парса

bool endParse = false; // флагокончания парса

List<SubCategory> subCategories; // подкатегории

магазина, определенные сайтом

List<SubCategory> categoriesInShop; // подкатегории

магазина, придуманные саммим сайтом

List<Product> products; // коллекция товаров магазина

}

Приведем структуру класса Product

class Product

{

int id; // идентификатор товара

int subCategoryId; // айди подкатегории товара

int categoryIdInShop; // айди подкатегории товара,

определнной магазином

int shopId; // айди магазина

float price; // цена

float dostavkaPrice; // цена доставки

float totalPrice; // общая цена

string name; // имя товара

string url; // ссылка на товар

string structurePath; // логический путь к товару на сайте

string itemSpecifics; // список основных

характеристик товара

string description; // другие характеристики товара

string html; // хтмл страницы

string mainImagePath; // путь к главной картинки

List<ProductImage> images; // картинки товара

List<Feedback> feedbacks; // отзывы о товаре

List<MarketUser> buyers; // покупатели, оставившие отзывы

}

Приведем структуру класса SubCategory

class SubCategory

{

string name = “”; // название категории

int id = 0; // идентификатор категории

string url = “”; // ссылка на категорию

}

Приведем структуру класса MarketUser:

class MarketUser

{

int newId; // айди

int id; // идентификатор покупателя

string name; // имя покупателя

string country; // страна покупателя

}

Приведем структуру класса MarketUser:

class Feedback

{

int newId;

int id; // идентификатор

int userId; // идентификатор покупателя

int productId; // идентификатор товара

int mark; // оценка

string coment; // текст коментария

int quantity; // количество купленного

}

Приведем структуру класса ProductImage

class ProductImage

{

public int id; // идентификатор изображения

public int productId; // идентификатор товара

public string path=””; // путь

public string url=””; // ссылка на изобржение

}

Приведем структуру класса ProductInfoForCompare

class ProductInfoForCompare

{

int productId; // идентификатор товара

int shopId; // идентификатор магазина

int subCategoryId; // идентификатор категории

string name=””; // имя товара

string imagePath = “”; // путь к картинки

Bitmap image=null; // изображение

float [] [] descriptors = null; // дескрипторы изображения

bool findGroup = false;

}

Приведем структуру класса IdenticalProductGroup

class IdenticalProductGroup

{

int id; // идентификатор группы

int subCategoryId; // категория группы

bool validated; // флаг проверки группы при составлении

групп одинаковых товаров

List<ProductInfoForCompare> products; // товары группы

List<ProductInfoForCompare> etalonProducts;

// эталонные товары группы

List<ProductInfoForCompare> newEtalonProducts; // новые

эталонные товары группы

}

Описание интерфейса работы программы.

При запуска программы появляется главное окно приложения:

Рис. 7. Главное окно приложения

Приведем описание интерфейса

1. Вкладка “Парс” позволяет производить парс магазинов сайта.

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

Возможны 2 варианта: задание диапазона и задание через список.

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

После ввода всех данных и нажати кнопки “Запуск” начинается процесс проверки магазинов а затем парс магазинов. Прогресс выполнения задач показывается компонентами ProgressBar. Также отображается сколько магазинов найдено.

2. Вкладка “Группировка” позволяет разбить товары в базе на группы одинаковых.

Для начала необходимо определить необходимые для этого настройки:

a) Точность сравнения для одной точки – максимальная величина разности дескрипторов двух точек, при которой они считаются одинаковыми.

b) Процент удачного сравнения – минимальный процент совпавших точек 2х изображений, при котором они считаются одинаковыми.

c) Количество эталонов в группе – каждая группа одинаковости содержит некоторое количество эталонных товаров, которые её определяют, этот параметр ограничивает их максимальное количество.

После нажатия на кнопку “Запуск” начинается процедура составления дескрипторов и группировка товаров. Т.к. процедура длинная на форме предусмотрены 2 элемента ProgressBar отображающие ход работы.

3. Вкладка “Обзор” позволяет просмотреть созданные группы.

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

В таблице снизу появляются группы одинаковости для этой категории. В таблице только один столбец – id этой группы.

Справа от неё появляется таблица товаров, принадлежащих выбранной группе и соответственно изображение, выбранного товара.

4. Вкладка “Поиск” позволяет производить поиск в базе по изображениям.

Для начала можно изменить настройки поиска, развернув соответствующую панель “Настройки”.

Здесь можно выбрать:

§ точность при поточечном сравнении, т.е. максимальную разность особых точек, при которой они считаются одинаковыми.

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

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

Далее нужно выбрать изображение, дубликаты которого мы будем искать в базе. Его можно выбрать, нажав кнопку “Обзор” и выбрав соответствующий файл в открывшемся окне OpenFileDialog.

Выбранное изображение отобразится на экране.

Затем следует выбрать категорию или несколько категорий, в которых будет производиться поиск дубликатов.

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

Для уменьшения времени, поиск можно производить в несколько потоков.

Процесс поиска отображается элементов ProgressBar, который появляется на время поиска.

Поиск можно остановить в любой момент времени, нажав на кнопку “Стоп”.

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

Апробация методики

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

Парс магазинов осуществлялся в 5 потоков. На парс каждой товарной позиции уходило около 6и секунд. В итоге на парс ушло полтора часа. Все магазины распарсились успешно. Было выявлено 875 товарных позиций.

Составление дескрипторов изображения осуществлялось в 4 потока, т.е. одновременно обрабатывалось 4 изображения по 1,1 секунды каждая.

В результате были сформированы группы одинаковых товаров.

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

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

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

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

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

Подобное поведение, что предсказуемо, наблюдалось и в отношении параметра “процент удачного сравнения”. Его оптимальной величиной является 0.7, что также видно на диаграмме.

Заключение

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

Также был проведен анализ объекта исследования и привлекаемых для решения поставленной задачи методов.

Алгоритм получения каталога товаров был реализован на языке C#. Работоспособность данного алгоритма проверялась с помощью данного программного продукта.

Апробация методики проводилась на фактических данных нескольких электронных магазинов этой сети.

Список использованной литературы

1. Пименов В.Ю. Вычислительно-эффективный метод поиска нечетких дубликатов в коллекции изображений. 2009-19с.

2. Википедия Гессиан функции http://ru. wikipedia.org/wiki/Гессиан_функции.

3. Хабрахабр Интегральное представление изображений http://habrahabr.ru/post/102919/.

4. Хабрахабр Обнаружение устойчивых признаков изображения: метод SURF http://habrahabr.ru/post/103107/

5. Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool Speeded-Up Robust Features (SURF) 2008 – 14с

6. Лабор В.В. Си Шарп: Создание приложений для Windows – Ми.: Харвест, 2003. – 384с.

7. Фролов А.В., Фролов Г.В. Язык С# Самоучитель, 2003. – 557с.

8. Эндрю Троелсен Язык программирования C# 2010 и платформа.net 4.0 5е издание. 2011. – 1392с.

Поделиться статьёй
Поделиться в telegram
Поделиться в whatsapp
Поделиться в vk
Поделиться в facebook
Поделиться в twitter
Леонид Федотов
Леонид Федотов
Окончил НИУ ВШЭ факультет компьютерных наук. Сам являюсь кандидатом наук. По специальности работаю 13 лет, за это время создал 8 научных статей и 2 диссертации. В компании подрабатываю в свободное от работы время уже более 5 лет. Нравится помогать школьникам и студентам в решении контрольных работ и написании курсовых проектов. Люблю свою профессию за то, что это направление с каждым годом становится все более востребованным и актуальным.

Ещё статьи

Нет времени делать работу? Закажите!
Вид работы
Тема
Email

Отправляя форму, вы соглашаетесь с политикой конфиденциальности и обработкой ваших персональных данных.