Материал: Создание программного продукта для редактирования и сшивания топографических карт

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

Был проведен патентный поиск и найдено несколько патентов и заявка на изобретение на смежную тему.

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

Разработка алгоритма программы

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

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

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

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

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

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

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

Свойства модулей:

функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью);

автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);

эволюционируемость (развиваемость);

открытость для пользователей и разработчиков (для модернизации и использования);

корректность и надежность;

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

Свойства (преимущества) модульного проектирования алгоритмов:

возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;

возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов);

облегчение тестирования алгоритмов и обоснования их правильности;

упрощение проектирования и модификации алгоритмов;

уменьшение сложности разработки (проектирования) алгоритмов (или комплексов алгоритмов);

наблюдаемость вычислительного процесса при реализации алгоритмов.

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

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

Пример. Для задачи решения квадратного уравнения ax2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c - отличны от нуля; 3) D = b2 - 4ac < 0 и др.

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

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

Рисунок 2.1 - Алгоритм программы

Разработка схемы и структуры программы

Структурное программирование - методология разработки программного обеспечения <#"871354.files/image001.gif">Рисунок 2.3 - Картины в сравнении

Затем необходимо сформировать массив совпадений. Количество «ответов» в массиве будет равно количеству пикселей. Соответственно, если сравнивать каждую сторону первой картины с 4 сторонами второй картины, а так же все остальные стороны, получим массив совпадений из 16 строк. Примем обход сторон по часовой стрелке. Обход сторон представлен на рисунке 2.4.

Рисунок 2.4 - Порядок обхода пикселей

Соответственно массив совпадений будет выглядеть как набор булевских значений). Массив совпадений пикселей представлен на рисунке 2.5.

Рисунок 2.5 - Массив совпадений пикселей

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

Рисунок 2.6 - Схематичный массив совпадений пикселей

Данный массив содержит суммарное совпадение пикселей 2 картин. Исходя из рисунка, мы не можем сказать сразу, какая все же сторона наиболее совпадает. Соответственно мы должны выяснить максимальное число для 1 стороны и запомним этот результат. Ответом будет массив из 4 значений, который возвращает максимальное значение по каждой стороне и представлено на рисунок 2.7. Так же стоит отметить, что стороны кубика нумеруются с «1».

Рисунок 2.7 - Суммарный результат обработки массива

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

Рисунок 2.8 - Результат работы функции

Далее проанализируем код отдельно-взятых функций программы.

public int[] AnalisKubov(System.Drawing.Bitmap image1, System.Drawing.Bitmap image2, int percent)

Функция в качестве входящих параметров получает две «картины» или 2 объекта типа System.Drawing.Bitmap а так же процент совпадения сторон друг с другом. Под процентом совпадения сторон понимается отношения количества совпавших пикселей к общему количеству пикселей.

Color[][] im1 = new Color[4][]; // 1 массив[][] im2 = new Color[4][]; // 2 массив[0] = new Color[image1.Width];[1] = new Color[image1.Height];[2] = new Color[image1.Width];[3] = new Color[image1.Height];[0] = new Color[image2.Width];[1] = new Color[image2.Height];[2] = new Color[image2.Width];[3] = new Color[image2.Height];

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

for (int i = 0; i < im1.Length; i++)

{(int j = 0; j < im1[i].Length; j++)

{(i == 0) im1[0][j] = image1.GetPixel(j, 1);(i == 1) im1[1][j] = image1.GetPixel(image1.Width - 1, j);(i == 2) im1[2][j] = image1.GetPixel(j, image1.Height - 1);(i == 3) im1[3][j] = image1.GetPixel(1, j);

}

}(int i = 0; i < im2.Length; i++)

{(int j = 0; j < im2[i].Length; j++)

{(i == 0) im2[0][j] = image2.GetPixel(j, 1);(i == 1) im2[1][j] = image2.GetPixel(image2.Width - 1, j);(i == 2) im2[2][j] = image2.GetPixel(j, image2.Height - 1);(i == 3) im2[3][j] = image2.GetPixel(1, j);

}

}

В дальнейшем мы эти массивы заполняем . То есть получаем последний пиксель стороны картины с помощью функции GetPixel.

bool[][] res = new bool[16][];(int i = 0; i <= 15; i++)

{k = 0;(i <= 3) k = im1[0].Length;(i > 3 && i <= 7) k = im1[1].Length;(i > 7 && i <= 11) k = im1[2].Length;(i > 11 && i <= 15) k = im1[3].Length;[i] = new bool[k];

}

Результаты совпадений поместим в массив. Так как будет сравниваться 16 сторон, то полученный результат поместим в массив типа bool [16]. Размерность массива будет соответствовать размерности массива с пикселями.

m = 0; //переменная для счета количества проходов

for (int i = 0; i < im1.Length; i++) // проход по граням 1 кубика

{(int k = 0; k < im1.Length; k++) // проход по граням 2 кубика

{(im1[i].Length == im2[k].Length)

{(int j = 0; j < im1[i].Length; j++) // проход по пикселям

{(PixelAnalis(im1[i][j], im2[k][j], Percent)) res[m][j] = true;

}

}++;

}

}

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

= new int[4]; // этот массив - массив совпадений

int[] TempMass = new int[16];count = 0;(int i = 0; i <= 15; i++)

{(int j = 0; j < res[i].Length; j++)

{(res[i][j]) count++;

}[i] = count;= 0;

}

Здесь мы создаем временный массив TempMass, который будет содержать суммарную информацию сравнений сторон картин.

Далее заполним массив, состоящий из 4 элементов, каждый из которых соответствует стороне.

int[] Max = new int[4];(int i = 0; i <= 15; i++)

{(i <= 3)

{(TempMass[i] > Max[0])

{[0] = TempMass[i];(Max[0] > 0 & TempMass[i] > 0)

{((int)(((double)Max[0] / (double)res[i].Length) * 100) >= percent) MassRes[0] = i + 1;

};

} //1 сторона кубика

}((i > 3 & i <= 7))

{(TempMass[i] >= Max[1])

{[1] = TempMass[i];(Max[1] > 0 & TempMass[i] > 0)

{((int)(((double)Max[1] / (double)res[i].Length) * 100) >= percent) MassRes[1] = i - 3;

};

} //2 сторона кубика

}((i > 7 & i <= 11))

{(TempMass[i] >= Max[2])

{[2] = TempMass[i];(Max[2] > 0 & TempMass[i] > 0)

{((int)(((double)Max[2] / (double)res[i].Length) * 100) >= percent) MassRes[2] = i - 7;

};

}

//3 сторона кубика

}((i > 11 & i <= 15))

{(TempMass[i] >= Max[3])

{[3] = TempMass[i];(Max[3] > 0 & TempMass[i] > 0)

{((int)(((double)Max[3] / (double)res[i].Length) * 100) >= percent) MassRes[3] = i - 11;

};

}//4 сторона кубика

}

}

В данном коде мы сначала проверяем, какая из сторон учувствует в сравнении. Например, if (i <= 3) - это первая сторона. Значит, результат мы запишем в массив с нулевым индексом. Так же мы должны проверить, максимальное ли число мы записываем или нет. Это максимальное число мы держим во временном массиве Max. И элемент Max[0] соответствует 1 максимальному числу массива.

Так же этот массив мы используем для нахождения индекса элемента, с каким совпала соответствующая сторона картины (код ниже).

for (int i = 0; i < 4; i++)

{( Max[i] > maxtemp)

{= Max[i];

}

}(int i = 0; i < 4; i++)

{(Max[i] > (int) (((double)maxtemp) * (((double)Percent1) / 100)))

{ [l] = Max[i]; ++;

}

}

// ищем номера совпавших элементов

int j = 3;= 0;k=0;(int i = 0; i < TempMass.Length;i++ )

{((max1[k]> 0) & (max1[k] == TempMass[i])) // счетчик элементов массива max1

{(i <= 3) \

{

MassRes[0] = i + 1; TempMass1[0] = max1[k];

}(i > 3 && i <= 7)

{

MassRes[1] = i - 3;TempMass1[1] = max1[k];

}(i > 7 && i <= 11)

{ [2] = i - 7; TempMass1[2] = max1[k];

}

if (i > 11 && i <= 15)

{

MassRes[3] = i - 11; TempMass1[3] = max1[k];

} (k < 3) k++; // это заплатка, если неверно выставлены проценты

} (j == i) // счетчик сторон

{++;= j + 4;

}

}

Одной из проблем при поиске совпавших сторон является наличие нескольких совпадений. Однако, как показала практика, при наличии совпавших сторон более 1, их численное значение (количество совпавших пикселей) значительно меньше(на 30-40 процентов). Следовательно, найдя максимальное значение из всех совпавших сторон, мы можем «отсечь» лишние стороны, которые являются не более чем цифровым случайным совпадением.

Анализ массива картин

Существует некий массив наборов картин, которые необходимо сравнить. Сравнение полностью картин необходимость отсутствует. Достаточно сравнить их «края». Таким образом, можно обнаружить, какие из краев совпадают. Решить эту задачу можно 2 способами:

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

Б) все картины сравнивать по очереди, затем получить массив ответов сравнения картин (используется в этом дипломе).

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

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

Рисунок 2.9 - Последовательность действий при решении задачи сравнений картин

Получение массива совпадений есть последовательный перебор каждой картины в сравнении с остальными. Массив совпадений представлен на рисунке 2.10.

Рисунок 2.10 - Порядок сравнений картин

Возьмем для примера 4 картины. То есть, чтобы сравнить их, необходимо:

А) 1 сравнить с 2,3,4.

Б) 2 сравнить с 3 и 4.

В) 3 сравнить с 4.

В соответствии с этим, массив совпадений для 4 картин будет выглядеть следующим образом:

Рисунок 2.11 - Массив результатов совпадений сторон

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

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

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

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