Но эта прямая аналогия не работает в задачах, в которых баланс между метками сильно смещен в сторону какого-либо класса. Например, при выделении текста на тысячи фрагментов без текста приходится всего несколько текстовых. Как ни странно, но в таких задачах можно хороших результатов при достаточно высоком проценте правильно классифицированных фрагментов и весьма быстрой классификации. Ключевой момент, который следует осознать, состоит в том, что хоть и невозможно построить простой классификатор с очень низким процентом ошибок, но в некоторых случаях можно построить классификатор, который практически никогда не будет неверно классифицировать текстовые области. Например, удалось получить очень быстрый классификатор, верно определяющий все текстовые области, но при этом в 90% случаев ошибающийся на нетекстовых областях. Такой детектор может использоваться для предварительной фильтрации: если фрагмент помечен как “не текст”, то он сразу отбрасывается, а если фрагмент помечен как “текст”, то требуется дополнительная классификация. Из последовательности подобных классификаторов, каждый следующий сложнее, медленнее и точнее предыдущего, и строится каскад классификаторов. Увеличение количества стадий приводит к увеличению точности, так в своей работе Виола и Джонс использовали каскад из 38 стадий. В качестве классификаторов авторы использовали асимметричный AdaBoost.

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

где, k - коэффициент предпочтения положительных меток над отрицательными.



3.6 Реализация AdaBoost в библиотеке OpenCV

Реализация метода AdaBoost представлена в библиотеке OpenCV в виде класса CvBoost. Объявление конструктора этого класса представлено в листинге 3.1.

Листинг 3.1: Конструктор класса CvBoost

CvBoost :: CvBoost (

const Mat& trainData,

int tflag,

const Mat& responses,

const Mat& varIdx,

const Mat& sampleIdx,

const Mat& varType,

const Mat& missingDataMask = Mat(),

CvBoostParams params = CvBoostParams(),

Параметры:

· trainData -- матрица, содержащая обучающее множество.

· tflag -- указывает на то, что представляют собой векторы признаков: столбцы (tflag = CV_COL_SAMPLE) или строки (tflag = CV_ROW_SAMPLE) матрицы trainData.

· responses -- вектор, содержащий метки классов для векторов признаков обучающего множества. Количество элементов в векторе должно совпадать с количеством векторов признаков матрицы trainData. Для двуклассовой классификации, а другую, текущая реализация OpenCV не поддерживает, нужно указывать метки классов из множества {-1; 1}.

· varIdx -- вектор-маска, позволяющий при обучении пропускать какие-либо признаки. По умолчанию задан пустой матрицей, следовательно, используется весь вектор признаков.

· sampleIdx -- то же что и varIdx для векторов. Позволяет обучиться не на всем множестве, а лишь не некоторых векторах. По умолчанию используются все множество.

· varType -- вектор хранящий множество типов признаков. Каждый признак может быть либо категорийным (CV_VAR_CATEGORICAL), либо численным (CV_VAR_ORDERED, или то же самое CV_VAR_NUMERICAL). От этого зависит принцип построения разбиения в узлах деревьев. Количество элементов в векторе на единицу больше числа признаков. Последний элемент вектора означает тип выходного значения классификатора. Если вектор не задан, то все данные считаются категорийными.

· missingDataMask -- матрица того же размера что и trainData, ненулевые элементы которой обозначают отсутствующую информацию. По умолчанию используются все данные.

· CvBoostParams -- параметры обучения. Про них будет подробнее сказано ниже.

Листинг 3.2: Конструктор класса CvBoostParams.

CvBoostParams (

int boost_type,

int weak_count,

double weight_trim_rate,

int max_depth,

bool use_surrogates,

const float priors,

На листинге 3.2 представлен конструктор класса CvBoostParams, описывающего параметры обучения классификатора.

· boost_type -- определяет тип классификатора. Библиотека OpenCV позволяет выбирать из четырех алгоритмов бустинга:

– CvBoost::DISCRETE -- дискретный AdaBoost;

– CvBoost::REAL -- вещественный AdaBoost;

– CvBoost::LOGIT -- LogitBoost;

– CvBoost::GENTLE -- гладкий AdaBoost.

· weak_count -- определяет количество слабых классификаторов.

· weight_trim_rate -- устанавливает порог обрезания. Принимает значения на отрезке [0; 1]. Вектора с весами меньшими или равными 1-weight_trim_rate не участвуют в обучении следующего слабого классификатора. При установке параметра в 0 обрезание не используется.

· max_depth -- определяет максимальную высоту деревьев-классификаторов.

· use_surrogates -- флаг, указывающий на разрешение использования суррогатных разбиений. Суррогатные разбиения используются при работе с отсутствующими данными.

· priors -- ссылка на массив из переменных типа float, которые определяют предпочтение одного из классов. Например, при значениях 1, 10 второй класс предпочтительнее первого в 10 раз. Если параметр не задан (priors = 0), то веса будут рассчитываться по обычной схеме.

При использовании конструктора по умолчанию, устанавливаются следующие параметры:

· boost_type=CvBoost::REAL;

· weak_count = 100;

· weight_trim_rate = 0.95;

· max_depth = 1;

· use_surrogates = true;

· priors = 0;

Листинг 3.3: Метод predict класса CvBoost.

float CvBoost :: predict (

const cv :: Mat& sample ,

const cv :: Mat& missing=Mat ( ) ,

const cv :: Range& slice =Range : : all( ) ,

bool rawMode = false ,

bool returnSum = false

)

)

Для классификации вызывается метод predict (см. листинг 3.3). Единственный обязательный параметр этого метода -- вектор признаков sample, который и будет классифицироваться. Назначение остальных:

· missing -- вектор, отмечающий отсутствующие данные, аналогичен по принципу действия параметру missingDataMask конструктора класса. По умолчанию все данные считаются присутствующими и используются для классификации.

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

· rawMode -- недокументированный параметр, должен быть установлен в 0.

· returnSum -- флаг, указывающий на формат возвращаемого значения. Если установлен в 0, то будет возвращаться метка класса (-1 или 1), иначе сумма значений классификаторов.



Заключение

Разработанная система обучалась и тестировалась на наборах данных ICDAR 2011. Тестирование осуществлялось по методике, описанной в работе [7]. Все фрагменты прошедшие классификацию и помеченные как текст, составляли маску. В качестве истинных значений использовалась разметка набора данных. Далее рассчитывалась полнота и точность по следующим формулам:

где - количество пикселей классифицированных как текст;

- количество пикселей классифицированных как не текст;

- количество текстовых пикселей классифицированных как текст;

- количество нетекстовых пикселей классифицированных как не текст.

Рисунок 4.1. Изображение, на котором получен лучший результат.



Результаты работы классификатора на сегодняшний день составляют: точность - 29%, полнота - 88%. На рисунке 4.1 представлено изображение, на котором классификатор показал лучший результат. Данное изображение отличается достаточно хорошим контрастом между текстом и фоном, слабо размыто и легко читаемо.

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

Рисунок 4.2 Изображение, на котором получен худший результат

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

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



Список использованных источников

1. Borman Sean. The Expectation Maximization Algorithm A short tutorial. Retrieved April 27, 2014, from http://www.seanborman.com/publications.

2. Boureau, Y.L. & Bach, F. & LeCun, Y. (2010). Learning mid-level features for recognition. Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference, 2559-2566.

3. Breiman Leo. Random forests - random features: Tech. Rep.,1999. September.

4. Breiman L. & Friedman J. H. & Olshen R. A.. Classification and regression trees.Wadsworth Publishing Company, 1984.

5. Canny John. A Computational Approach to Edge Detection. IEEE Trans. Pattern Anal. Mach. Intell. 1986. Т. 8, № 6. С. 679-698.

6. Chen Xiangrong & Yuille Alan L. Detecting and reading text in natural scenes. Proceedings of the 2004 IEEE computer society conference on Computer vision and pattern recognition, 2004, 366-373.

7. Coates, A. & Carpenter, B. & Satheesh, S. (2011). Text Detection and Character Recognition in Scene Images with Unsupervised Feature Learning. Document Analysis and Recognition, ICDAR 2011 International Conference, 440-445.

8. Dempster A. P. & Laird N. M. & Rubin D. B. (1997) Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B. 1977. Т. 39. С. 1-38.

9. Epshtein, B. & Eyal, O. & Yonatan,W. (2013). Detecting Text in Natural Scenes with Stroke Width Transform. Retrieved April 27, 2014, from http://www.math.tau.ac.il/~turkel/imagepapers/text_detection.pdf

10. Friedman Jerome. Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics. 2000. Т. 29. С. 1189-1232.

11. Friedman Jerome & Hastie Trevor & Tibshirani Robert. Additive Logistic Regression: a Statistical View of Boosting.Annals of Statistics. 1998. Т. 28. с. 2000.

12. Fukunaga Keinosuke. Introduction to statistical pattern recognition. Computer Science and Scientific Computing. Second изд. Academic Press, 1990.

13. Gatos Basilios & Pratikakis Ioannis & Perantonis Stavros. Towards Text Recognition in Natural Scene Images.

14. Hyvarinen, A. & Oja, E. (2000). Independent component analysis: algorithms and applications. Neural Networks Oxford, 13(4-5), 411- 430.

15. Jung, K. & Kim, K. & Jain Anil, K. (2004). Text information extraction in images and video: a survey. Pattern Recognition, 37(5), 977-997.

16. Merino Carlos & Mirmehdi Majid. A framework towards real-time detection and tracking of text. Second International Workshop on Camera-Based Document Analysis and Recognition (CBDAR 2007). 2007. September. С. 10-17.

17. Pan Yi-Feng & Hou Xinwen & Liu Cheng-Lin. A Hybrid Approach to Detect and Localize Texts in Natural Scene Images. Trans. Img. Proc. Piscataway, NJ, USA, 2011. Т. 20, № 3.. 800-813.

18. Picard Rosalind, W. (2010). Decorrelating and then Whitening data. Retrieved April 27, 2014, from http://courses.media.mit.edu/2010fall/mas622j/whiten.pdf

19. Roubtsova Nadejda S. & Wijnhoven Rob G. J. & de With Peter H. N. Integrated text detection and recognition in natural images, 2012.

20. Schapire Robert E. & Freund Yoav, Experiments with a New Boosting Algorithm. ICML,Lorenza Saitta. Morgan Kaufmann, 1996. С. 148- 156.

21. Schapire Robert E. & Singer Yoram. Improved Boosting Algorithms Using Confidence-rated Predictions.Machine Learning. 1999. Т. 37, № 3. С. 297- 336.

22. Shahab Asif & Shafait Faisal & Dengel Andreas. ICDAR 2011 Robust Reading Competition Challenge 2: Reading Text in Scene Images. ICDAR. IEEE, 2011. С. 1491-1496.

23. Simon M. Lucas & Alex Panaretos & Luis Sosa. ICDAR 2003 Robust Reading Competitions, ICDAR. IEEE Computer Society, 2003, 682-687.

24. Sochman J.& Matas J. WaldBoost - learning for time constrained sequential detection. Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on. Т. 2. 2005. С. 150-156

25. Vapnik Vladimir N. The Nature of Statistical Learning Theory. Springer, 1995.

26. Vorontsov K.V. Support vector machine lections. Retrieved April 27, 2014, from: http://www.ccas.ru/voron/download/SVM.pdf

27. Tamura H. & Mori S. & Yamawaki T. Texture features corresponding to visual perception. IEEE Transactions on Systems, Man and Cybernetics. 1978. Т. 8, № 6.

28. Viola Paul & Jones Michael. Fast and Robust Classification using Asymmetric AdaBoost and a Detector Cascade. Advances in Neural Information Processing System 14. MIT Press, 2001. С. 1311-1318.

29. YouTube Press (2014). YouTube Official Statistics. Retrieved April 1, 2014, from http://www.youtube.com/yt/press/statistics.htm

Размещено на Allbest.ru