Разработка и реализация программного инструмента для оцифровки двумерного графика функции

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Математико-механический факультет Кафедра информатики Дипломная работа Разработка и реализация программного инструмента для оцифровки двумерного графика функции Заведующий кафедрой информатики д. ф.-м. н., профессор Косовский Н.К.

Научный руководитель:

д.т.н., профессор Сафонов В.О.

Введение

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

Одним из важных приложений цифровой обработки изображений в научных исследованиях является оцифровка графиков на бумажных носителях. Огромное количество научных данных (особенно экспериментальных) содержится в научной литературе. При проведении исследований у ученых часто возникает необходимость воспроизведения этих данных на своих графиках, например, для сравнения со своими аналогичными данными или для иллюстрации каких-либо эффектов. До широкого использования компьютеров ученые и специалисты вынуждены были вручную обрабатывать такие графики — с помощью карандаша и линейки «оцифровывать» различные графические зависимости и только затем переносить их на свои графики. Это была очень долгая и трудоемкая процедура, да и к тому же ненадежная, так как «человеческий фактор» часто приводил к ошибкам при обработке, особенно, при большом объеме работы. С появлением компьютеров этот процесс значительно упростился: теперь стало возможным отсканировать исследуемых график, переведя его в форму растрового изображения и затем, используя, различные прикладные программы, получать эти графические зависимости уже непосредственно в виде таблиц с соответствующим набором цифровых данных.

В интернете сейчас можно найти довольно много различных приложений для оцифровки графиков, как коммерческих, так и свободных. Это такие приложения, как ChartReader, Graph2Digit, Фемтоскан, Grafula, GSYS, CurveSnap, digitize, Engauge Digitizer, g3data, PCX2PRN, Plot Digitizer, SCaViS, WebPlotDigitizer, DataThief III, Dagra, Digitize Plot To Data, DigitizeIt, General graphics package ORIGIN, GetData Graph Digitizer, Graphics software FindGraph и т. д. Все эти программы имеют самый разный интерфейс, имеют свои плюсы и минусы, однако практически сводятся к достаточно простой последовательности операций: загрузка графического изображения, установка осей координат и их масштабов, ручная (с помощью мыши) фиксация дискретного набора точек, принадлежащих графику, и сохранение оцифрованных точке в файл на диск.

1. Постановка задачи В данной дипломной работе ставятся задачи:

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

2). Разработать удобную для использования программу на Java реализующую этот алгоритм. Программа должна обеспечивать следующие функции:

— чтение изображения с диска;

— привязка осей координат и определение масштабов по осям графика;

— оцифровка выбранного графика.

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

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

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

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

2.1 Градиентные операторы.

В работе отмечается, что существует два общих подхода обнаружения кромок, линий в цифровом изображении: дифференциальное детектирование и модельный подбор (fitting). Первый подход основан на обработке оригинального образа для получения дифференциального, где усилены пространственные изменения амплитуды яркости. Оператор дифференциального обнаружения используется для определения положений пикселов, где имеет место значительное изменение амплитуды. Второй подход основан на «подгонке» группы пикселов под модель кромки, линии или пятна. Если совпадение некоторых определяющих параметров достаточно близкое, то считается, что данная группа представляет собой кромку, линию или пятно. В результате обычно генерируется бинарная карта-индикатор, где указаны положения кромок, линий и пятен.

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

Если величина этого градиента достаточно велика (по сравнению с заданным порогом), то кромка считается присутствующей.

В дискретном случае градиент вычисляется следующим образом:

.

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

Угол наклона к оси X рассчитывается по формуле:

Наиболее простой способ расчета градиентов в дискретной области это использование односторонних разностей:

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

или Угол наклона:

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

Описанные выше простые градиентные операторы имеют один недостаток: они не способны достаточно точно детектировать кромки на сильно зашумленном изображении. Эта проблема может быть преодолена с помощью расширенных шаблонов. Например, R-оператор типа Prewitt 7×7 имеет вид:

Этот оператор называется Boxcar. Другой расширенный R-оператор (trancated pyramid operator) дает пониженный вес для точек, наиболее удаленных от центра шаблона:

Следующие весовые функции Гауссового типа используются для подавления шума. Обозначим через непрерывную Гауссову функцию со стандартным отклонением s.

Используя это обозначение Argyle оператор может быть записан, как дискретная версия непрерывного оператора (R-оператор):

.

где s и t — параметры распространения оператора. C-оператор записывается аналогично. Другой аналогичный оператор имеет вид (Macleod оператор):

Операторы Argyle и Macleod в отличие от Boxcar оператора дают пониженный вклад пикселов, удаленных от центра шаблона. Суммарный оператор (дифференциирование (G) и удаление шума (S)) можно записать в виде:

.

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

1. Хорошее детектирование. Отношение сигнал-шум (SNR — signal-to-noise-ratio) градиента максимизируется для получения низкой вероятности неудачи в определении кромки и низкой вероятности появления фальшивых точек.

2. Хорошая локализация. Точки кромки, детектируемые оператором, должны быть как можно ближе к центру кромки.

3. Единственный отклик. Должен иметься только единственный отклик, определяющий истинную кромку.

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

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

В работе отмечается, что детектор Кэнни удовлетворяет определенным критериям обнаружения и локализации кромок: хорошее отношение сигнал/шум, точная локализация и максимальное подавление ложных кромок. Он использует логическую обработку («немаксимальное подавление») для утоньшения линий, двухпороговый гистерезис для слежения за кромкой, и представляет универсальный алгоритм получения контурного изображения без учета вида и характеристик протяженности и направленности кромок, которые он выделяет.

Метод формирования оценок градиента в локальном окне позволяет получить оценки компонент градиента и вычислить оценки модуля и аргумента вектора градиента в каждой точке. Ряд методов использует вычисление оценок второй производной.

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

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

2.2 Алгоритмы предварительной обработки изображения.

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

Неодинаковость ширины линий относится к систематическим отклонениям. К случайным относятся незначительные выступы и впадины по длине линий, различные отростки и «хвостики» — так называемая «бахрома». Эти искажения также необходимо удалять при предварительной обработки. Другим видом случайных отклонений являются пустоты, то есть группы незачерненных пикселов внутри линии. В предельном случае, когда размер «пустоты» совпадает с шириной линии, возникает разрыв. Пустоты и разрывы — весьма нежелательные явления, поэтому в процессе предварительной обработки они должны заполняться.

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

Будем рассчитывать три последовательные строки:. Выделим в i-той строке произвольный пиксел, который обозначим через. Этот элемент имеет в выбранных строках восемь соседних пикселов, которые мы обозначим цифрами 0,1,…7 (см. рис. 1).

Рисунок 1. Нумерация элементов окна 3×3.

Основная идея процедуры утоньшения заключается в том, чтобы отыскать на изображении крайние сверху, снизу, справа и слева зачерненные пикселы, а затем вынести решение о возможности их удаления с соблюдением перечисленных выше условий. Естественно, элемент считать крайним сверху, если он и элемент 6 зачернены, а элемент 2 не зачернен. Формально эту процедуру можно выразить так: элемент является крайним сверху, если равна единице следующая булева функция, в которой символы переменных совпадают с номерами элементов на рис 1:

Далее, если данный пиксел является крайним сверху, то будем придавать ему значение 0 (будем стирать этот пиксел), если равна единице следующая функция:

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

Функция должна быть вычислена для каждого пиксела i-той строки, поэтому выражение (2) запишем в векторной форме:

Здесь — векторы, определяющие, соответственно, инверсию.

i-1 строки, i+1 строку в исходном изображении и т. д. — вектор, единичные компоненты которого определяют элементы i-той строки, значения которых необходимо сменить с 1 на 0.

Пиксел является крайним слева, если равна 1 функция. Этот пиксел подлежит стиранию, если функция равна 1. Следовательно,.

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

Процедура утоньшения состоит в последовательном преобразовании исходного изображения в новое изображение путем стирания сначала крайних сверху, затем крайних слева, далее крайних снизу и справа пикселов. Этот цикл повторяется до тех пор, пока на некотором цикле ни одна из функций (3) — (5) не обратится в 1. Отметим, что порядок стираний может быть и иным, например, можно начать со стирания крайних правых пискселов, затем крайне левых и т. д.

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

3.1 Основной алгоритм.

1) Предварительная обработка изображения.

Предварительная обработка изображения заключается в обязательном пункте а) и необязательном пункте б):

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

б) В применении алгоритма отношения линий как описано в пункте 3.2.

2)Определение графика.

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

Введем понятие радиус-квадрата. Радиус-квадрат радиуса r в точке (x, y) называется квадрат со стороной (2r+1) и центром в точке (x, y). Все координаты растрового изображения являются целыми неотрицательными числа (рис. 2).

Рисунок 2. Радиус-квадрат радиуса r.

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

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

Рисунок 3. Группы черных точек внутри радиуса-квадрата Если радиус больше некоторого значения, например, половины из наибольшего из измерений рассматриваемого изображения, то алгоритм считает невозможным определить путь. Здесь возможны варианты:

1) нет ни одной группы — в этом случае алгоритм заканчивается и считается, что нет пути из начальной точки в конечную точку.

2) есть одна группа — все точки периметра. Радиус радиус-квадрата увеличивается на 1 и алгоритм повторяется.

3) есть одна группа и количество элементов в ней больше (2r+1). В этом случае увеличиваем радиус на 1 и выполняем алгоритм заново. Такой выбор связан с тем, что на данном этапе важно определить толщину графика, но указанная ситуация указывает на то, что вы это еще невозможно сделать (см. рис. 4).

Рисунок 4. Одна группа внутри радиуса-квадрата с количеством элементов больше (2r+1).

4) есть одна группа, количество элементов в которой не превышает (2r+1). В этом случае применяем подпункт а2, после чего применяем след шаг к этой группе, задав ей предыдущую точку как начальную, и установив текущий рисунок, как начальный рисунок.

5)есть две группы, количество элементов в которых не превышает (2r+1) для каждого. В этом случае применяем подпункт а2, после чего применяем следующий шаг к обоим группам, задав им предыдущую точку, как начальную и установив текущий рисунок, как начальный рисунок. Иначе увеличиваем радиус на 1 и повторяем алгоритм.

6) групп больше чем 2. Считаем, что присутствует шум и увеличиваем радиус на 1 и повторяем алгоритм.

а2) Закрашивает точки белым в радиус-квадрате радиусом r-1.Это необходимо для идентификации уже пройденного участка.

б) Для группы имеем текущий рисунок. Для группы имеем предыдущую точку (pr).

Назовем шириной группы количество элементов в группе.

Теперь вычислим ширину группы (w) и радиус группы ® как.

(w div 2)+1. А также выберем среднюю в порядковом смысле точку (p) из группы.

Введем для этой группы путь trace который является упорядоченным списком точек. Добавим p в trace. Если в радиус-квадрате радиусом r в точке p есть конечная точка, то считаем, что путь для этой группы найден. Заканчиваем алгоритм и переходим к след пункту.

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

Закрашиваем точки белым в радиус-квадрате радиусом r-1 для текущего рисунка. Если это первая итерация алгоритма, то мы выбираем группу по наличию в ней такой точки x, что угол между вектором (pr;p) и (p;x) минимален, где x принадлежит объединению этих групп. Если таких групп несколько, то выбираем любую. Этот шаг необязательный, но позволяет сделать отступ на первом шаге во избежание возможных лишних ветвлений, так как предполагается, что в предыдущей точке могли быть пресечения. Здесь возможны варианты:

1) Если группа одна и ее ширина не превосходит w, то выберем среднюю в ней точку и добавим ее в trace. Также присвоим p значение этой точки. Обновляем значение радиуса r=(w div 2)+1 и повторяем алгоритм.

2)Если группа одна и ее ширина превосходит w, то увеличиваем r на 1 и повторяем алгоритм. Это делается потому, что увеличение ширины воспринимается как потенциальное пересечение, и требуется временное увеличение радиуса для получения большей информации (см. рис 5).

Рисунок 5. Обработка пересечения.

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

в)В итоге имеем набор путей (trace), для каждого из которых пути мы знаем, что он либо породил другие пути, либо нашел или не нашел конечную точку. Также знаем самые первые пути (их не более 2-х). Таким образом, мы можем сформировать единые пути, которые привели к искомой точке. Результатом определения графика как раз являются такие пути, если они существуют.

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

3.2 Альтернативный алгоритм.

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

Изменение касаются пунктов б) и в). Конечная точка не выбирается:

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

2) Определение графика.

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

б) Для группы имеем текущий рисунок. Для группы имеем предыдущую точку (pr). Назовем шириной группы количество элементов в группе. Теперь вычислим ширину (w) и радиус ® как (w div 2)+1. Выберем среднюю в порядковом смысле точку (p) из группы. Введем для этой группы путь trace, который является упорядоченным списком точек. Добавляем p в trace. Формируем группы тем же способом что и в предыдущем пункте. Если нет ни одной группы, то в этом случае алгоритм заканчивается и фиксируется trace для данной группы.

Закрашиваем точки белым в радиус-квадрате радиусом r-1 для текущего рисунка. Здесь возможны варианты:

1) Если группа одна и ее ширина не превосходит w, то выберем среднюю в ней точку и добавим ее в trace, также присвоим p значение этой точки. Обновляем значение радиуса r=(w div 2)+1 и затем повторяем алгоритм.

2) Если группа одна и ее ширина превосходит w, то увеличиваем r на 1 (так как потенциально имеем пересечение) и повторяем алгоритм.

3) Если групп больше одной, то считаем, что пересечение найдено. Выбираем группу по наименьшему отклонению от ширины, а если таких групп несколько, то из них выбираем по наименьшему отклонению вектора направления, т. е. по наличию в ней такой точки x такой, что угол между вектором (pr;p) и (p;x) минимален, где x принадлежит объединению этих групп. Если таких групп несколько, то выбирается любая группа.

Затем в ней выберем среднюю точку и добавим ее в trace. Затем присваиваем p значение этой точки и обновляем значение радиуса и ширины.

r=(w_new div 2)+1, w=w_new.

где w_new — ширина выбранной группы.

Повторяем алгоритм.

в) В итоге имеем 1 путь или 2 пути (trace) .Соединяя их, получаем общий путь. Результатом определения графика является общий путь.

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

3.3 Вспомогательный алгоритм.

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

1) Предварительная обработка изображения (пороговая фильтрация + утоньшение линий по необходимости).

2) Определение осей.

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

а) Присваиваем радиусу радиус-квадрата = 1.

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

1) Если количество групп меньше 2-х увеличиваем радиус на 1, повторяем алгоритм. Такое условие связано с тем, что оси могут быть неполными (см. рис. 6).

Рисунок 6. Возможные конфигурации координатных осей.

2) Если количество групп больше или равно 2-м, то для каждой группы сопоставляется наиболее подходящий вектор из 4-х направляющих, соответствующих модели входных данных по принципу наименьшего угла между (p;x) и K, где K-один из 4-х векторов, x — любая точка из группы. Причем двум группам не может соответствовать один вектор. Закрашиваем точки белым в радиус-квадрате радиусом r-1 для рисунка. Затем для каждой группы и соответствующему ей вектору применяется следующий шаг:

б) Имеем начальный вектор (v).

Вычислим ширину (w) и радиус ® как (w div 2)+1. Затем выберем среднюю в порядковом смысле точку (p) из группы. Введем переменную erase, которая будет разрешать или запрещать стирать точки.

Присвоим erase = true;

Формируем группы тем же способом что и в предыдущем пункте. Если групп больше чем 1, то присвоим erase=false, т. к возможны потенциальные пересечения.

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

1) Если ширина группы не превосходит w, то выберем среднюю в ней точку. Если erase=true, то закрашиваем точки в радиус-квадрате радиусом r-1. Присваиваем p значение этой точки и обновляем значение радиуса r=(w div 2)+1. Повторяем алгоритм, восстановив erase=true, если требуется.

2) Если ширина группы превосходит w, то увеличиваем r на 1 присвоим erase = false и повторяем алгоритм. Это делается из-за риска потерять утолщение, обусловленное пересекающимся графиком.

в) В итоге получаем изображение с частично стертыми осями.

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

4. Работа с приложением.

Для распознавания и оцифровки графика пользователь выполняет следующие действия:

1)Загружается изображение с помощью командного меню.

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

3)Установка осей координат щелчком мыши на начало координатной системы. При этом одновременно запускается вспомогательный алгоритм распознавания для частичного удаления осей координат и облегчения распознавания самого графика.

4)Установка масштаба. При выставлении масштаба требуется наличие осей координат, и указание двух точек сначала с ненулевой X координатой, затем с ненулевой Y координатой. По умолчанию масштаб равен масштабу изображения.

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

6)Если оцифровка прошла некорректно или требуется добавить точки, то можно воспользоваться ручным режимом. Для установки точки в ручном режиме нужно нажать кнопку Point.

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

4. Объекты в приложении и их отображение.

Приложение представляет объект стандартного класса JFrame с компонентами:

1)Область отображения. Область отображения является объектом пользовательского класса G_JPanel, наследуемого от стандартного класса JPanel и содержит в себе основную функциональность для рисования изображения и точек на экране.

2)Область увеличения. Область увеличения является объектом пользовательского класса Z_Jpanel. Область увеличения служит для отображения увеличенного изображения вокруг курсора для удобства пользователя.

3)Изображение. Изображение как объект определяется объектом image стандартного класса Image, имеющимся в библиотеке Java атрибутами ширины и длины image_w и image_h, соответственно. Изображение загружается пользователем с диска.

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

Программа позволяет сдвигать изображение. Положение изображение определяется переменными x_init, у_init, которые фиксируются после сдвига. Переменные x_drag, y_drag приобретают значения только во время сдвига до его фиксации, и осуществляют визуальную плавность сдвига.

Программа позволяет приближать/удалять изображение, ведя учет в целочисленной переменной zoom, значение которой формирует коэффициент приближения по формуле. Само по себе приближение вычисляется относительно центра изображения. Но, в зависимости от положения курсора мыши, также идет и перерасчет сдвига на области отображения для удобства пользователя.

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

4) Точка. Точка является объектом пользовательского класса G_Point и определяется: координатами в области отображения на момент ее установки (center), измерениями области отображения dim. width и dim. height, при которых она была установлена и полями multx=z*sx и multy=z*sy, где z — коэффициент приближения/удаления, а sx=dim.width/w, sy=dim.height/h — коэффициенты сжатия по x и y, соответственно. Здесье w, h — измерения.

Определение: набор значений {dim.width, dim. height, multx, multy} назовем условием.

Определение: приведенными координатами точки p (x, y) к условиям B={dw, dh, mx, my} в условиях A={dim.width, dim. height, multx, multy} называются такие координаты x', y' что.

x' = (x + dx — x_c)*zx+x_c.

y' = -(-(y + dy) + y_c)*zy+y_c,.

где.

dx = (dw — dim. width)/2;

dy = (dh — dim. height)/2;

double x_c = (dw)/2.

double y_c = (dh)/2.

double zx = mx/multx.

double zy = my/multy.

Отображение точки осуществляется через стандартные библиотеки Java. Определение координаты на области отображение производится путем пересчета координат точки, учитывая её условие при инициализации и условие, характерное для текущего состояния программы, т. е. вычисляются приведенные координаты точки в ее условиях к текущим условиям. Затем эти приведенные координаты смещаются на x_init, у_init. В итоге получаем координаты, необходимые для корректного отображения точки в области отображения. Такой подход пересчета координат относительно условия, в котором была поставлена точка, позволяет точно (по желанию пользователя) определять ее положение при приближении, что может быть важно при ручном выставлении точек и последующем вычислении их выходных координат. Код метода paint объекта точки:

public void paint (Graphics2D g2, Dimension dim, double mx, double my, Point shift) {.

double dx = (dim.width — (double)this.dim.width)/2;

double dy = (dim.height -(double)this.dim.height)/2;

double x_c = (dim.width)/2;

double y_c = (dim.height)/2;

double zx = mx/multx;

double zy = my/multy;

double z_x_ord = (center.x + dx — x_c)*zx+x_c;

double z_y_ord = -(-(center.y + dy) + y_c)*zy+y_c;

Point g_center = new Point ((int)(z_x_ord)+shift.x,(int)(z_y_ord)+shift.y);

Ellipse2D.Double circle = new Ellipse2D. Double (g_center.x — 2, g_center.y — 2, 4, 4); g2. fill (circle);

}.

Часть кода метода paintComponent (Graphics g) области отображения, осуществляющего отображение точек, хранимых в программе в списке points, имеет вид:

double z = pow (0.9, zoom);

Dimension dim = this. getSize ();

int w = (int)image_w;

int h = (int)image_h;

Graphics2D g2 = (Graphics2D)g;

if (w>dim.width || h>dim.height){.

for (ListIterator i = points. listIterator (); i. hasNext ();) {.

double sx = dim. width/(double)w;

double sy = dim. height/(double)h;

G_Point el = i. next ();

el.paint (g2,dim, sx*z, sy*z, new Point ((int)(- x_drag — x_init),(int)(- y_drag — y_init)));

}.

}else{.

for (ListIterator i = points. listIterator (); i. hasNext ();) {.

G_Point el = i. next ();

el.paint (g2,dim, z, z, new Point ((int)(- x_drag — x_init),(int)(- y_drag — y_init)));

}.

}.

5) Прямоугольные оси координат. Оси, как изображение, включают набор линий, отображающих оси и стрелки направления, и буквы «X» «Y».

Прямоугольные оси координат являются объектом xy_ord пользовательского класса Ord и определяются: центром пересечения осей center, измерениями области отображения dim. width и dim. height, (при которых она была установлена), точка с полями multx, multy, угол поворота angle осей относительно горизонтали экрана. Отображение осей производится по аналогии с отображением точки при помощи стандартных библиотек Java. Метод прорисовки paint () класса Org:

public void paint (Graphics2D g2, double length, Dimension dim, double mx, double my, Point shift){.

double dx = (dim.width — (double)this.dim.width)/2;

double dy = (dim.height -(double)this.dim.height)/2;

double x_c = (dim.width)/2;

double y_c = (dim.height)/2;

double zx = mx/multx;

double zy = my/multy;

double z_x_ord = (center.x + dx — x_c)*zx+x_c;

double z_y_ord = -(-(center.y + dy) + y_c)*zy+y_c;

Point g_center = new Point ((int)(z_x_ord)+shift.x,(int)(z_y_ord)+shift.y);

g2.drawLine ((int) (g_center.x — (int) (cos (angel*PI/180)*length)),.

(int) (g_center.y + (int) (sin (angel*PI/180)*length)),.

(int) (g_center.x + (int) (cos (angel*PI/180)*length)),.

(int) (g_center.y — (int) (sin (angel*PI/180)*length)));

g2.drawLine ((int) (g_center.x — (int) (cos (angel*PI/180+PI/2)*length)),.

(int) (g_center.y + (int) (sin (angel*PI/180+PI/2)*length)),.

(int) (g_center.x + (int) (cos (angel*PI/180+PI/2)*length)),.

(int) (g_center.y — (int) (sin (angel*PI/180+PI/2)*length)));

double d = min (dim.width, dim. height);

double xA = g_center.x — (int) (cos (angel*PI/180)*d/3);

double yA = g_center.y + (int) (sin (angel*PI/180)*d/3);

g2.drawLine ((int) (xA + (int) (cos (angel*PI/180+PI/8)*d/30)),.

(int) (yA — (int) (sin (angel*PI/180+PI/8)*d/30)),.

(int) (xA),.

(int) (yA));

g2.drawLine ((int) (xA + (int) (cos (angel*PI/180-PI/8)*d/30)),.

(int) (yA — (int) (sin (angel*PI/180-PI/8)*d/30)),.

(int) (xA),.

(int) (yA));

g2.setFont (new Font («Dialog», Font. PLAIN, (int)d/40));

g2.drawString («X», (int) (xA + (int) (cos (angel*PI/180+PI/2)*d/40)), (int) (yA — (int) (sin (angel*PI/180+PI/2)*d/40)));

xA = g_center.x — (int) (cos (angel*PI/180+PI/2)*d/3);

yA = g_center.y + (int) (sin (angel*PI/180+PI/2)*d/3);

g2.drawLine ((int) (xA + (int) (cos (angel*PI/180+PI/2+PI/8)*d/30)),.

(int) (yA — (int) (sin (angel*PI/180+PI/2+PI/8)*d/30)),.

(int) (xA),.

(int) (yA));

g2.drawLine ((int) (xA + (int) (cos (angel*PI/180+PI/2-PI/8)*d/30)),.

(int) (yA — (int) (sin (angel*PI/180+PI/2-PI/8)*d/30)),.

(int) (xA),.

(int) (yA));

g2.setFont (new Font («Dialog», Font. PLAIN, (int)d/40));

g2.drawString («Y», (int) (xA + (int) (cos (angel*PI/180+PI/2+PI/2)*d/40)), (int) (yA — (int) (sin (angel*PI/180+PI/2+PI/2)*d/40)));

}.

Часть кода метода paintComponent (Graphics g) области отображения осуществляющего отображение осей:

double z = pow (0.9, zoom);

Dimension dim = this. getSize ();

int w = (int)image_w;

int h = (int)image_h;

Graphics2D g2 = (Graphics2D)g;

if (w>dim.width || h>dim.height){.

if (xy_ord ≠ null) {.

double sx = dim. width/(double)w;

double sy = dim. height/(double)h;

xy_ord.paint (g2, max (dim.width + z*sx*abs (x_drag + x_init), dim. height + z*sy*abs (y_drag + y_init)),.

dim,.

sx*z,.

sy*z,.

new Point ((int)(- x_drag — x_init),(int)(- y_drag — y_init)));

}.

}else{.

if (xy_ord ≠ null) {.

xy_ord.paint (g2, max (dim.width + z*abs (x_drag + x_init), dim. height + z*abs (y_drag + y_init)),.

dim,.

z,.

z,.

new Point ((int)(- x_drag — x_init),(int)(- y_drag — y_init)));

}.

}.

//Motion render->

if (isOxyOn) {.

new Ord (new Point ((int)(p.x — x_drag),(int)(p.y — y_drag)), 1,1,180 + angel_ord*0.5,dim).

paint (g2, max (dim.width, dim. height), dim, 1,1,new Point (0,0));

}.

5. Генерация выходных данных.

Выходными данными является таблица координат точек графика относительно установленных осей координат и установленного масштаба. Выходные координаты для единичной точки определяются следующим образом. Как было указано ранее точка в приложении определяется как объект класса G_Point и определяется ее координатами в области отображения и условием, в котором она была создана. Оси координат также являются объектом класса Ord и определяются аналогичным образом. Сначала вычисляем приведенные координаты точки в её условие к условию осей координат. Затем находим проекции приведенных координат на обе оси и формируем компоненты выходных координат как соответствующие расстояния от координат, характеризующих оси (объект класса Ord) до ранее найденых проекций на эти оси с поправкой на выбраный масштаб. Реализацией в приложении является метод generateCords класса G_Point, возвращающий пару вещественных чисел, являющихся выходными координатами точки:

public List generateCords (Ord ord, double xStrain, double yStrain){.

double mx = ord. getMultX ();

double my = ord. getMultY ();

double dx = (ord.getDim ().width — dim. width)/2;

double dy = (ord.getDim ().heightdim.height)/2;

double x_c = (ord.getDim ().width)/2;

double y_c = (ord.getDim ().height)/2;

double zx = mx/multx;

double zy = my/multy;

double x1 = (center.x + dx — x_c)*zx+x_c;

double y1 = -(-(center.y + dy) + y_c)*zy+y_c;

double x0 = ord. getPoint ().x;

double y0 = ord. getPoint ().y;

double x0s = ord. getPoint ().x — (cos (ord.getAngel ()*PI/180));

double y0s = ord. getPoint ().y + (sin (ord.getAngel ()*PI/180));

double resultX = findPoj (x0, y0, x0s, y0s, x1, y1)*xStrain;

x0s = ord. getPoint ().x — (cos (ord.getAngel ()*PI/180+PI/2));

y0s = ord. getPoint ().y + (sin (ord.getAngel ()*PI/180+PI/2));

double resultY = findPoj (x0, y0, x0s, y0s, x1, y1)*yStrain;

List out = new ArrayList ();

out.add (0, resultX);

out.add (1, resultY);

return out;

}.

private double findPoj (double x0, double y0, double x0s, double y0s, double x1, double y1){.

try{.

double x =.

(x1*pow (x0,2)-y1*y0s*x0+y1*y0*x0+x0*pow (y0s, 2)-x0*y0*y0s-2*x1*x0s*x0- y1*y0*x0s+y1*y0s*x0s+x0s*pow (y0,2)+x1*pow (x0s, 2)-x0s*y0*y0s)/ (pow (y0,2)+pow (x0,2)+pow (x0s, 2)-2*x0s*x0+pow (y0s, 2)-2*y0*y0s);

double y =.

(2*y0*y1*y0s+y1*pow (y0,2)+y0*x1*x0+y1*pow (y0s, 2)+pow (x0s, 2)*y0+y0s*pow (x0,2) — x0s*x0*y0-y0s*x1*x0-x0s*x0*y0s-y0*x1*x0s+y0s*x1*x0s)/.

(pow (y0,2)+pow (x0,2)+pow (x0s, 2)-2*x0s*x0+pow (y0s, 2)-2*y0*y0s);

double out = sqrt (pow (x-x0,2)+pow (y-y0,2));

double s = 1;

if ((x0s-x0)*(x-x0)+(y0s-y0)*(y-y0)<0){.

s= -1;

}.

return out*s;

}catch (Exception e){.

System.out.println («error in G_Point.findProj»);

}.

return 0;

}.

6. Реализация основного алгоритма.

private void graphAction (){.

//p-current position of mouse after click.

Dimension dim = this. getSize ();

int dx = dim. width / 2 — image. getWidth (null) / 2;

int dy = dim. height / 2 — image. getHeight (null) / 2;

Point p_tmp = this. toInitCord (p);

Point pt = new Point (p_tmp.x — dx, p_tmp.y — dy);

BufferedImage bimage = new BufferedImage (image.getWidth (null), image. getHeight (null), BufferedImage. TYPE_INT_RGB);

// Draw the image on to the buffered image.

Graphics2D g2 = bimage. createGraphics ();

g2.drawImage (image, 0, 0, null);

g2.dispose ();

int defColour = -1;

if (isPtInBImg (bimage, pt. x, pt. y)){.

defColour = bimage. getRGB (pt.x, pt. y);

}.

if (defColour==-1){.

return;

}.

//checking for two points being initialized.

if (isGraphOn2 == false){.

isGraphOn2 = true;

g_p = new Point (p_tmp.x — dx, p_tmp.y — dy);

return;

}.

if (g_p ≠ null){.

pt_last = g_p;

}else{.

return;

}.

int radius = 1;

boolean exit = false;

ArrayList> packs = new ArrayList>();

while (radius.

packs = new ArrayList>();

ArrayList content = new ArrayList ();

boolean contentwrite = false;

Point pt_tmp = new Point (pt.x — radius, pt. y — radius);

for (int i=0;i<=8*radius-1;i++){.

double alpha = PI/2 * (i/(2*radius));

if (isPtInBImg (bimage, pt_tmp.x, pt_tmp.y) && defColour == bimage. getRGB (pt_tmp.x, pt_tmp.y)){.

content.add (pt_tmp);

contentwrite = true;

}.

else if (contentwrite){.

packs.add (content);

content = new ArrayList ();

contentwrite = false;

}.

pt_tmp = new Point (pt_tmp.x + (int)cos (alpha), pt_tmp.y + (int)sin (alpha));

}.

if (contentwrite){.

if (!packs.isEmpty () && (packs.get (0).get (0).x == pt. x — radius && packs. get (0).get (0).y == pt. y — radius)){.

content.addAll (0, packs. get (0));

packs.set (0,content);

contentwrite = false;

}else{.

packs.add (content);

contentwrite = false;

}.

}.

if (packs.size ()==2){.

exit = false;

break;

}else{.

if (packs.size ()==1 && packs. get (0).size ()<=radius*2+1){.

exit = false;

break;

}.

radius++;

}.

}.

if (exit){return;}.

List> out = new ArrayList ();

for (int i=0;i.

List> tmp = graphAction_step (bimage, packs. get (i).size (),.

packs.get (i).get (packs.get (i).size ()/2),.

pt,.

pt_last,.

defColour,.

dx,.

dy,.

0,.

false,.

tmp_ways);

if (tmp ≠ null){.

out.addAll (tmp);

}.

}.

//saving ways.

wPoints = out;

DefaultTableModel model = (DefaultTableModel) ways. getModel ();

model.setRowCount (0);

for (int i=0;i.

model.addRow (new Object[]{i+1});

}.

};

private List> graphAction_step (BufferedImage bimage, int w, Point pt, Point previous, Point pt_last, int defColour, int dx, int dy, int stack, boolean erase, List tmp_ways){.

List trace = new ArrayList ();

int radius_tmp=w;

int radius = radius_tmp/2+1;

int width = radius_tmp;

int iterations = 0;

while (pt ≠ null){.

if (abs (pt_last.x — pt. x)<=width && abs (pt_last.y — pt. y)<=width){.

trace.add (new Point (pt_last.x +dx, pt_last.y +dy));

List> end = new ArrayList ();

end.add (trace);

return end;

}.

List> packs = new ArrayList>();

ArrayList content = new ArrayList ();

boolean contentwrite = false;

Point pt_tmp = new Point (pt.x — radius, pt. y — radius);

for (int i=0;i<=8*radius-1;i++){.

double alpha = PI/2 * (i/(2*radius));

if (isPtInBImg (bimage, pt_tmp.x, pt_tmp.y) && defColour == bimage. getRGB (pt_tmp.x, pt_tmp.y)){.

content.add (pt_tmp);

contentwrite = true;

}.

else if (contentwrite){.

packs.add (content);

content = new ArrayList ();

contentwrite = false;

}.

pt_tmp = new Point (pt_tmp.x + (int)cos (alpha), pt_tmp.y + (int)sin (alpha));

}.

if (contentwrite){.

if (!packs.isEmpty () && (packs.get (0).get (0).x == pt. x — radius && packs. get (0).get (0).y == pt. y — radius)){.

content.addAll (0, packs. get (0));

packs.set (0,content);

contentwrite = false;

}else{.

packs.add (content);

contentwrite = false;

private boolean isPtInBImg (BufferedImage bimage, int x, int y) y<0.

}.

}.

if (packs.isEmpty ()){.

break;

}.

else.

{.

iterations++;

for (int i = 0;i.

for (int j = 0;j.

if (previous ≠null && packs. get (i).get (j).x == previous. x && packs. get (i).get (j).y == previous. y){.

packs.remove (i);

break;

}.

}.

}.

for (int i=-(radius-1);i<=(radius-1);i++){.

for (int j=-(radius-1);j<=(radius-1);j++){.

if (isPtInBImg (bimage, pt. x + i, pt. y + j)){.

bimage.setRGB (pt.x + i, pt. y + j, -1);

}.

}.

}.

if (iterations > 1 && packs. size ()>1){.

List> end = new ArrayList ();

for (int i=0;i.

BufferedImage b = new BufferedImage (bimage.getWidth (),.

bimage.getHeight (),.

BufferedImage.TYPE_INT_RGB);

Graphics2D g2 = b. createGraphics ();

g2.drawImage (bimage, null, 0,0);

g2.dispose ();

List> get = graphAction_step (b,.

packs.get (i).size (),.

packs.get (i).get (packs.get (i).size ()/2),.

pt, pt_last, defColour, dx, dy, stack+1,false, tmp_ways);

if (get ≠ null){.

List> out = new ArrayList ();

for (int j=0;j.

List trace_tmp = new ArrayList ();

trace_tmp.addAll (trace);

trace_tmp.addAll (get.get (j));

out.add (trace_tmp);

}.

end.addAll (out);

}.

}.

if (end.isEmpty ()){.

return null;

}.

return end;

}.

List> tmp;

if (iterations == 1 && previous ≠ null){.

tmp = getNextPoint_vectorAngelCriterion (packs, new Point (pt.x — previous. x, pt. y — previous. y),-2,pt);

if (tmp == null){.

tmp = new ArrayList ();

}.

}else{.

tmp = packs;

}.

if (!tmp.isEmpty ()){.

if (tmp.get (0).size ()>width){.

radius++;

iterations—;

}else{.

int best = (tmp.get (0).size ()-1)/2;

Point old_pt = pt;

//find the best point->

double s = -3;

int pVx = pt_last.x — pt. x;

int pVy = pt_last.y — pt. y;

double pL = sqrt (pow (pVx, 2) + pow (pVy, 2));

for (int j = 0;j.

Point middle = tmp. get (0).get (j);

int cVx = middle. x-pt.x;

int cVy = middle. y-pt.y;

double cL = sqrt (pow (cVx, 2) + pow (cVy, 2));

double s_tmp = ((double)pVx/pL)*((double)cVx/cL) +.

((double)pVy/pL)*((double)cVy/cL);

if (s_tmp>=s){.

s=s_tmp;

best = j;

}.

}.

// <-find the best point.

pt = tmp. get (0).get (best);

trace.add (new Point (old_pt.x +dx, old_pt.y +dy));

previous = old_pt;

}.

}else{.

pt = null;

}.

}.

}.

return null;

}.

private boolean isPtInBImg (BufferedImage bimage, int x, int y) x>(bimage.getWidth ()-1).

private Point toInitCord (Point in){.

in = new Point ((int)(in.x + x_init),(int)(in.y + y_init));

int w = (int)image_w;

int h = (int)image_h;

Dimension dim = this. getSize ();

double z = pow (0.9, zoom);

double sx = 1;

double sy = 1;

if (w>dim.width | h>dim.height){.

sx = dim. width/(double)w;

sy = dim. height/(double)h;

}.

double x_c = (dim.width)/2;

double y_c = (dim.height)/2;

double zx = 1/(z*sx);

double zy = 1/(z*sy);

double z_x_ord = (in.x — x_c)*zx+x_c;

double z_y_ord = -(-(in.y) + y_c)*zy+y_c;

Point out = new Point ((int)(z_x_ord),(int)(z_y_ord));

repaint ();

return out;

}.

private List> getNextPoint_vectorAngelCriterion (List> packs, Point vect, double minScal, Point pt){.

if (packs==null || packs. isEmpty ()){.

return null;

}.

List> result = null;

List> out = new ArrayList ();

if (vect ≠ null){.

double scalar = -2;

for (int i = 0;i.

double s = -3;

int pVx = vect. x;

int pVy = vect. y;

double pL = sqrt (pow (pVx, 2) + pow (pVy, 2));

//find the best point->

for (int j = 0;j.

Point middle = packs. get (i).get (j);

int cVx = middle. x-pt.x;

int cVy = middle. y-pt.y;

double cL = sqrt (pow (cVx, 2) + pow (cVy, 2));

double s_tmp = ((double)pVx/pL)*((double)cVx/cL) +.

((double)pVy/pL)*((double)cVy/cL);

if (s_tmp>=s){.

s=s_tmp;

}.

}.

// <-find the best point.

if (s>scalar && s>minScal){.

scalar = s;

out = new ArrayList ();

out.add (packs.get (i));

}.

}.

if (!out.isEmpty ()){.

result = out;

}.

}else{.

int d = 0;

List pack = new ArrayList ();

for (int i=0;i.

if (packs.get (i).size ()>d){.