#include "stdafx.h"
#include <string>
#include "opencv2\core\core.hpp"
#include "opencv2\highgui\highgui.hpp"
#include "opencv2\imgproc\imgproc.hpp"
#include <iostream>
#include <vector>
#include <chrono>
#include <random>

#include <boost\numeric\ublas\matrix.hpp>
#include <boost\numeric\ublas\vector.hpp>
#include <boost\numeric\ublas\lu.hpp>
#include <boost\numeric\bindings\traits\ublas_matrix.hpp>
#include <boost\numeric\bindings\traits\ublas_vector.hpp>

#include <fstream>
#include <iomanip>
#include <stdlib.h>

namespace ublas = boost::numeric::ublas;	// пространство имён для библиотеки для работы с векторной алгеброй

typedef ublas::vector<int> HVector;			// переобозначаем тип для того, чтобы было удобней записывать
typedef ublas::matrix<int, ublas::column_major> HMatrix;	// аналогично

using namespace std;

int bigWidth = 520;		// ширина номера с оконтовкой по государственному образцу
int bigHeight = 112;	// высота --//--
int croppedWidth = 480;	// ширина номера без оконтовки по государственному образцу
int croppedHeight = 76; // высота --//--
int fontBig = 76;		// высота шрифта цифры по гос. образцу
int fontSmall = 58;		// высота шрифта буквы по гос. образцу

int SQUARE_SIZE = 50;	// размер вектора признаков для гистограммы чёрного цвета
int SUBS_SIZE = 50;		// размер вектора признаков для "похожести символа"

cv::Mat toBW(cv::Mat image); // преобразовать изображение к черно-белому формату

int inner_product(HVector x, HVector y); // скалярное произведение векторов
HMatrix outer_product(HVector x, HVector y); // векторное произведение
HVector transpose(HVector x);	// транспонирование вектора
HMatrix transpose(HMatrix m);	// транспонирование матрицы
HVector getColumn(HMatrix m, int k); // взять k-ый столбец матрицы
HMatrix zerosDiagonal(HMatrix m); // обнулить диагональ у матрицы
HMatrix learn(HVector x);	// выучить вектор x и вернуть соответсвующую этому вектору матрицу весов
void learnAll();	// выучить все данные образы и заполнить матрицы весов weights_letters и weights_numbers
HVector BWToHVector(cv::Mat gray, vector<cv::Mat> patterns); // взять вектор признаков чёрно-белого изображения


bool equals(HVector x, HVector y);	// проверить на равенство два вектора
int closestHVector(HVector v, vector<HVector> patterns); // найти среди набора векторов patterns, вектор расстояние Хэмминга до которого от вектора v минимально
int dist(HVector v1, HVector v2); // расстояние Хэмминга
HVector apply(HMatrix w, HVector x); // пропустить вектор v через нейронную сеть, заданную матрицей весов w
HVector applyVector(HMatrix w, HVector x); // распознать вектор по матрице весов
vector<int> getRandomOrder(int n); // взять случайную перестановку чисел (1..n)

void process(string filename);	// распознать номер на изображении filename

double blackArea(cv::Mat bw);	// посчитать площадь чёрной области на изображении
vector<int> calcSubs(cv::Mat bw, vector<cv::Mat> patterns);	// посчитать вектор признаков для "похожести символа"
vector<int> calcHist(cv::Mat bw);	// посчитать вектор признаков для гистограммы чёрного

void doLetter(string filename);	// сохранить букву в базу
void doNumber(string filename); // сохранить цифру в базу

HMatrix weights_letters(SQUARE_SIZE * 2 + SUBS_SIZE, SQUARE_SIZE * 2 + SUBS_SIZE); // матрица весов для сети, распознающей буквы и цифры соответственно
HMatrix weights_numbers(SQUARE_SIZE * 2 + SUBS_SIZE, SQUARE_SIZE * 2 + SUBS_SIZE); 
vector<cv::Mat> images_letters = vector<cv::Mat>();	// изображения букв
vector<cv::Mat> images_numbers = vector<cv::Mat>(); // изображения цифр
vector<HVector> etalon_letters = vector<HVector>(); // вектора признаков для букв
vector<HVector> etalon_numbers = vector<HVector>(); // вектора признаков для цифр
vector<string> names_letters = vector<string>();	// имена файлов с буквами
vector<string> names_numbers = vector<string>();	// имена файлов с цифрами
cv::Mat prepare(cv::Mat image);						// подготовить изображение символа для извлечения вектора признаков

int getGrayColor(cv::Mat image, int x, int y);	// вернуть число от 0 до 255 цвет точки (x, y) на изображении image в градациях серого

void doLetter(string filename) {
	names_letters.push_back(filename);	// сохраняем имя файла

	cv::Mat img = cv::imread(filename);	// считываем изображение из файла
	images_letters.push_back(prepare(img));	// сохраняем изображение
}
void doNumber(string filename) {
	names_numbers.push_back(filename);

	cv::Mat img = cv::imread(filename);
	images_numbers.push_back(prepare(img));
}
void learnAll() {
	bool initFlag = false;	// флаг, сохранили ли мы уже хотя бы один образов в матрицу весов
	for (cv::Mat i : images_letters) {	// проходим по всем буквам
		HVector v = BWToHVector(i, images_letters); // для каждой буквы извлекаем вектор признаков
		etalon_letters.push_back(v);	// сохраняем вектор признаков

		if (initFlag) {	// если мы ещё не выучили ни одного образа, то инициализируем нашу матрицу весов
			weights_letters += learn(v);
		}
		else { // иначе в уже инициализированную матрицу сохраняем новый выученный образ
			weights_letters = learn(v);
			initFlag = true;
		}
		weights_letters = zerosDiagonal(weights_letters); // обнуляем диагональ
	}

	initFlag = false;
	for (cv::Mat i : images_numbers) {
		HVector v = BWToHVector(i, images_numbers);
		etalon_numbers.push_back(v);

		if (initFlag) {
			weights_numbers += learn(v);
		}
		else {
			weights_numbers = learn(v);
			initFlag = true;
		}
		weights_numbers = zerosDiagonal(weights_numbers);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	string letters = "./letters.txt"; // файл, содержащий список эталонных букв
	string numbers = "./numbers.txt"; // файл, содержащий список эталонных цифр

	fstream F;	// новый входной поток
	F.open(letters);	// открываем файл
	while (!F.eof()) {	// пока не конец файла, считываем строку и добавляем новую картинку в базу
		string l;
		F >> l;
		doLetter(l);
	}
	F.close();
	F.open(numbers);
	while (!F.eof()) {
		string l;
		F >> l;
		doNumber(l);
	}
	F.close();

	learnAll();	// учим сети letters и numbers на изображениях, сохранённых в базе

	process("03.png");	// распознаем номер на этой картинке
	cv::waitKey();	// ожидаем нажатия клавиши
	cv::destroyAllWindows();	// уничтожаем все созданные в процессе окна
	return 0;
}

cv::Mat prepare(cv::Mat image) {
	cv::Mat res = toBW(image);	// сначала приведём изображение к черно-белому виду
	cv::Mat square = cv::Mat(SQUARE_SIZE, SQUARE_SIZE, res.type());	// создадим новое изображение нужного размера || означает, что 
	cv::resize(res, square, cv::Size(SQUARE_SIZE, SQUARE_SIZE));	// сохраним на ч/б изображение в созданное    ||	изменим размер нашего изображения
	return square;
}

cv::Mat toBW(cv::Mat image) {
	cv::Mat gray(image);	// создадим новое изображение, как копию image
	if (gray.type() != CV_8UC1) { // ксли оно не в градациях серого
		cvtColor(gray, gray, CV_BGR2GRAY); // переведём его в градации серого
	}
	threshold(gray, gray, 128, 255, cv::THRESH_BINARY);	// выполним проговое преобразование: все пиксели, цвет которых больше 128, переведём в 255 (255 - белый, 0 - чёрный)
	return gray;
}
HMatrix outer_product(HVector x, HVector y) {
	return ublas::outer_prod(x, y); // используем функцию из библиотеки
}
HVector transpose(HVector x) {
	return ublas::trans(x);
}
HMatrix transpose(HMatrix m) {
	return ublas::trans(m);
}
HVector getColumn(HMatrix m, int k) {
	return ublas::column(m, k);
}
HMatrix zerosDiagonal(HMatrix m) {
	HMatrix result(m);
	for (int i = 0; i < m.size1(); i++) {
		m.at_element(i, i) = 0;
	}
	return m;
}
HMatrix learn(HVector x) {
	HMatrix result(outer_product(transpose(x), x)); // выучить образ - посчитать матрицу M = x * transpose(x)
	return result;
}
int signum(int x) {	// знак числа
	return (x > 0) ? 1 : -1;
}
HVector BWToHVector(cv::Mat square, vector<cv::Mat> patterns) {
	vector<int> subs = calcSubs(square, patterns); // сначала посчитаем вектор признаков "похожести"
	vector<int> hist = calcHist(square);	// затем, вектор признаков гистограммы чёрного
	HVector result = HVector(subs.size() + hist.size());	// припишем один вектор к другому и получим конечный вектор признаков
	for (int i = 0; i < subs.size(); i++) {
		result[i] = subs[i];
	}
	for (int i = 0; i < hist.size(); i++) {
		result[subs.size() + i] = hist[i];
	}
	return result;
}

double blackArea(cv::Mat bw) {
	int area = 0;
	for (int x = 0; x < bw.cols; x++) {		// посчитаем количество чёрных пикселов на изображении
		for (int y = 0; y < bw.rows; y++) {
			if (getGrayColor(bw, x, y) == 0) {
				area += 1;
			}
		}
	}
	return 1. * area / (bw.cols * bw.rows);	// вернём отношение чёрных пикселов к общему количеству пикселов
}
int indexMax(vector<double> v) {	// возвращает индекс максимального элемента в массиве
	int ind = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] > v[ind]) {
			ind = i;
		}
	}
	return ind;
}

vector<int> calcSubs(cv::Mat square, vector<cv::Mat> patterns) { // вектор признаков для "похожести"
	vector<double> subs = vector<double>();
	for (cv::Mat i : patterns) {	// проходим по всем изображениям из patterns
		cv::Mat s;						
		cv::subtract(i, square, s);	// считаем разницу нашего изображения и изображения из patterns (разница изображений = попиксельная разница, тоже изображение)
									// если изображения одинаковые, то разница изображений будет полностью чёрной картинкой
		subs.push_back(blackArea(s));	// сохраним для каждой разницы площадь чёрного на ней
	}
	int size = subs.size();
	vector<int> ranges = vector<int>(size);	// сохраним в ranges номер по возрастанию для каждого элемента из subs
	for (int i = 0; i < size; i++) {		// например subs = [0.234, 0.7, 1.0, 0.0, 0.6],
		int ind = indexMax(subs);			// тогда ranges будет равно [4, 2, 5, 1, 3]
		ranges[ind] = size - i;				// чем больше элемент ranges[k], тем сильнее наше изображение похоже на patterns[k]
		subs[ind] = -subs[ind];
	}
	for (int i = 0; i < size; i++) {							// нормируем ranges согласно SUBS_SIZE
		ranges[i] = (int)(1. * ranges[i] / size * SUBS_SIZE);	// в результате нормировки: max(ranges) -> SUBS_SIZE, min(ranges) -> 0
	}
	int sgn = 1;
	vector<int> result = vector<int>();
	for (int i : ranges) {				// теперь составим вектор признака "похожести"
		for (int j = 0; j < i; j++) {	// для каждого ranges[k], запишем в результат (sgn) ranges[k] раз
			result.push_back(sgn);
		}
		sgn = -sgn;						// при этом будем чередовать знак

		// например, ranges = [4, 2, 5, 1, 3] тогда result = [1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1]
		//													 | ranges[0] | [1]  |     [2]      |[3] |  [4]  |

	}
	return result;
}
vector<int> calcHist(cv::Mat square) {
	int max = 255 * SQUARE_SIZE;
	int min = 0;

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

	vector<int> h0 = vector<int>();	// гистограмма по вертикалям
	for (int x = 0; x < SQUARE_SIZE; x++) {	// пробегаем по всей ширине
		int sum = 0;
		for (int y = 0; y < SQUARE_SIZE; y++) {	// пробегаем по всей высоте
			sum += getGrayColor(square, x, y);	// считаем сумму цвета на вертикали
		}
		// чем чернее будет полоса, тем ближе sum к нулю
		h0.push_back(signum((int)(1. * (sum - min) / (max - min) * 2 - 1)));	// нормируем, сохраняем
	}

	vector<int> h1 = vector<int>();
	for (int y = 0; y < SQUARE_SIZE; y++) {
		int sum = 0;
		for (int x = 0; x < SQUARE_SIZE; x++) {
			sum += getGrayColor(square, x, y);
		}
		h1.push_back(signum((int)(1. * (sum - min) / (max - min) * 2 - 1)));
	}

	vector<int> hist = vector<int>();
	hist.insert(hist.end(), h0.begin(), h0.end()); // припишем гистограмму горизонталей к гистограмме вертикалей и вернём это
	hist.insert(hist.end(), h1.begin(), h1.end()); 
	return hist;
}

int getGrayColor(cv::Mat gray, int x, int y) {
	cv::Scalar color = gray.at<uchar>(cv::Point(x, y));
	return color.val[0];
}


vector<int> getRandomOrder(int n) {
	vector<int> order = vector<int>();
	for (int i = 0; i < n; i++) {
		order.push_back(i);
	}
	unsigned seed = chrono::system_clock::now().time_since_epoch().count();
	shuffle(order.begin(), order.end(), default_random_engine(seed));
	return order;
}
HVector applyVector(HMatrix w, HVector x) {
	int n = x.size();
	vector<int> order = getRandomOrder(n);	// возьмём случайны порядок обхода нейронов
	HVector result(x);
	for (int i = 0; i < n; i++) {	// пройдемся по этому порядку и посчитаем выходной вектор
		HVector column = getColumn(w, order[i]);
		result[order[i]] = signum(inner_product(result, column));
	}
	return result;
}
HVector apply(HMatrix w, HVector x) {
	HVector result(x);
	while (true) {	// будем пропускать вектор через сеть до тех пор, пока она не придёт к устойчивому состоянию
		HVector temp = applyVector(w, result);
		if (equals(temp, result)) {
			break;
		}
		result = temp;
	}
	return result;
}
int dist(HVector v1, HVector v2) {
	int res = 0;
	for (int i = 0; i < v1.size(); i++) {
		if (v1[i] != v2[i]) {
			res++;
		}
	}
	return res;
}
int closestHVector(HVector v, vector<HVector> patterns) {
	int mini = 0;
	for (int i = 1; i < patterns.size(); i++) {
		if (dist(patterns[i], v) < dist(patterns[mini], v)) {
			mini = i;
		}
	}
	return mini;
}
bool equals(HVector x, HVector y) {
	return ublas::norm_1(x - y) == 0;
}
int inner_product(HVector x, HVector y) {
	return ublas::inner_prod(x, y);
}

vector<cv::Mat> toMiddleConnected(cv::Mat left);	// функция ищет на изображении все компоненты связности чёрного цвета, пересекающие среднюю горизонтальную линию
cv::Mat standartize(cv::Mat gray);	// приведение изображения к стандартному размеру
cv::Mat cropStandart(cv::Mat standart);	// обрезка оконтовки на стадартизированном изображении
cv::Mat toBorder(cv::Mat gray);	// удать белую границу по краям изображения

void process(string filename) {
	cv::Mat image = cv::imread(filename);	// открываем изображение
	cv::namedWindow("original");	// создаём окно
	cv::imshow("original", image);	// показываем изображение

	cv::Mat bw = toBW(image);	// приводим к ч/б
	cv::namedWindow("bw");
	cv::imshow("bw", bw);

	cv::Mat bordered = toBorder(bw); // обрезаем белые края
	cv::namedWindow("bordered");
	cv::imshow("bordered", bordered);

	cv::Mat standart = standartize(bordered); // приводим к стандартному изображению
	cv::namedWindow("standart");
	cv::imshow("standart", standart);

	cv::Mat cropped = cropStandart(standart);	// обрезаем оконтовку
	cv::namedWindow("cropped");
	cv::imshow("cropped", cropped);

	vector<cv::Mat> pieces = toMiddleConnected(cropped); // берём компоненты связности чёрного цвета
	for (int i = 0; i < pieces.size(); i++) {
		cv::Mat tmp = prepare(pieces[i]);	// для каждой компоненты приводим её к виду для распознавания

		string wname = "PieceN";	// имя окна
		wname.push_back((char)('0' + i));
		cv::namedWindow(wname); // покажем нашу компоненту
		cv::imshow(wname, tmp);
		// предположим, что наша компонента буква, попробуем её распознать
		HVector x = BWToHVector(tmp, images_letters); // извлечём вектор признаков
		HVector res = apply(weights_letters, x);	// пропустим через сеть
		int k = closestHVector(res, etalon_letters); // найдем ближайший вектор из базы к получившемуся состоянию сети
		
		int dot = names_letters[k].rfind("."); // узнаем имя найденного вектора
		cout << names_letters[k].substr(dot - 1, 1) << " -- "; // выведем наше предположение о том, что это за буква

		x = BWToHVector(tmp, images_numbers);	// теперь предположим, что это цифра и сделаем то же самое
		res = apply(weights_numbers, x);
		k = closestHVector(res, etalon_numbers);
		dot = names_letters[k].rfind(".");
		cout << names_numbers[k].substr(dot - 1, 1) << endl;
	}
}

cv::Mat toBorder(cv::Mat gray) {
	cv::Mat copy(gray);
	int left = copy.cols;
	int right = 0;
	int top = copy.rows;
	int bottom = 0;
	// ищем самый левый/верхний/правый/нижний чёрные пиксели на изображении
	// по этим точкам состовляем прямоугольник и обрезаем его
	for (int x = 0; x < copy.cols; x++) {
		for (int y = 0; y < copy.rows; y++) {
			cv::Scalar color = copy.at<uchar>(cv::Point(x, y));
			if (color.val[0] != 0) {
				continue;
			}
			if (x < left) {
				left = x;
			}
			if (x > right) {
				right = x;
			}
			if (y < top) {
				top = y;
			}
			if (y > bottom) {
				bottom = y;
			}
		}
	}
	cv::Mat cropped(copy(cv::Rect(cv::Rect(left, top, right - left, bottom - top))));
	threshold(cropped, cropped, 128, 255, cv::THRESH_BINARY);
	return cropped;
}
cv::Mat standartize(cv::Mat gray) {
	if (gray.rows * gray.cols == 0) {
		return gray;
	}
	// здесь просто изменяем размер
	cv::Mat standart = cv::Mat(bigHeight, bigWidth, gray.type());
	resize(gray, standart, standart.size());
	threshold(standart, standart, 128, 255, cv::THRESH_BINARY);
	return standart;
}
cv::Mat cropStandart(cv::Mat standart) {
	// обрезаем по заданным значениям
	cv::Rect roi = cv::Rect(bigWidth / 2 - croppedWidth / 2, bigHeight / 2 - croppedHeight / 2,
		croppedWidth, croppedHeight);
	cv::Mat cropped = standart(roi);
	threshold(cropped, cropped, 128, 255, cv::THRESH_BINARY);
	return cropped;
}
vector<cv::Mat> toMiddleConnected(cv::Mat left) {
	cv::Mat copy(left);
	int currentColor = 10;
	vector<int> connectedColors = vector<int>();
	int y = left.rows / 2;
	for (int x = 0; x < copy.cols; x++) {					// пройдем по всей средней горизонтали изображения
		int color = getGrayColor(copy, x, y);				// узнаем цвет текущего пикселя
		if (color == 0) {									// если он чёрный, то используем стандартную функцию floodFill(как заливка в обычном пэинте)
			currentColor += 10;								//		и закрасим каждую чёрную область в уникальный цвет
			connectedColors.push_back(currentColor);		//		все уникальные цвета сохраним в connectedColors
			floodFill(copy, cv::Point(x, y), currentColor);
		}
	}
	for (int x = 0; x < copy.cols; x++) {					// всё, что на изображении осталось чёрным - есть пиксели не принадлежащие ни одной
		for (int y = 0; y < copy.rows; y++) {				//		из интересующих нас компонент
			int color = getGrayColor(copy, x, y);			//
			if (color == 0) {								//
				copy.at<uchar>(cv::Point(x, y)) = 255;		//		сделаем их белыми
			}
		}
	}
	vector<cv::Mat> pieces = vector<cv::Mat>();
	for (int c : connectedColors) {							// теперь для каждого уникального цвета c:
		cv::Mat p;											//		создадим копию нашего раскрашенного изображения
		copy.copyTo(p);										//		и оставим на нем только пиксели этого цвета c
		for (int x = 0; x < p.cols; x++) {					//			причём переведём их в чёрный цвет
			for (int y = 0; y < p.rows; y++) {				//		а все остальные сделаем белыми
				int color = getGrayColor(p, x, y);			//		затем с помощью toBorder обрежем белые края
				if (color != c) {							//
					p.at<uchar>(cv::Point(x, y)) = 255;		// таким образом мы получим какое-то количество маленьких изображений
				}											//	в каждом из которых будет только одна компонента
				else {										//
					p.at<uchar>(cv::Point(x, y)) = 0;		//
				}
			}
		}
		p = toBorder(p);
		pieces.push_back(p);
	}
	return pieces;
}