10.14489/vkit.2015.04.pp.014-018

DOI: 10.14489/vkit.2015.04.pp.014-018

Каратеев С. Л., Костромов Н. А., Бекетова И. В., Визильтер Ю. В.
КОМПЛЕКСИРОВАНИЕ ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ N ГРАММ ПРИ РАСПОЗНАВАНИИ СИМВОЛЬНЫХ СТРОК В ВИДЕОПОТОКЕ
(с. 14-18)

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

Ключевые слова: распознавание символьной информации; коррекция ошибок; комплексирование информации; расстояние Левенштейна; N-граммы; генетический алгоритм.

Karateev S. L., Kostromov N. A., Beketova I. V., Vizilter Yu. V.
INFORMATION FUSION BASED ON N-GRAM TECHNIQUE FOR CORRECTION OF SEQUENCES OF AUTOMATICALLY RECOGNIZED SYMBOLS IN VIDEO
(pp. 14-18)

Abstract. The algorithm for symbolic information fusion is proposed for error correction in automatic reading of alphanumeric character sequences recognized independently from a sequence of video frames. The algorithm requires no prior knowledge about the message struc-ture, language and content. The genetic algorithm is applied to synthesize best symbol sequences from initially recognized symbol sequences taken from video. The first generation of hypotheses is created using the crossover of N-grams derived directly from initially recognized sequences. The each next generation is obtained by crossing of best symbol sequence hypotheses from the previous generation. The fitness function is determined as a combination of Levenshtein distance and probabilistic assessment of generated sequences. The algorithm is stopped in two cases: if the best solution is not changed in next generation or if the given maximal number of generations is reached. The special version of information fusion algorithm is proposed for the case of word sequence (sentence) reading. The evaluation of algorithm performance based on mathematical modeling is presented.

Keywords: Character recognition; Video processing; Error correction; Information fusion; Levenshtein distance; N-gramms; Genetic algorithm

+ - Информация об авторах (About the Authors) Click to collapse

Рус

С. Л. Каратеев, Н. А. Костромов, И. В. Бекетова, Ю. В. Визильтер (ФГУП «Государственный научно-исследовательский институт авиационных систем» ГНЦ РФ, Москва) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

S. L. Karateev, N. A. Kostromov, I. V. Beketova, Yu. V. Vizilter (State Research Institute of Aviation Systems State Scientific Center of Russian Federation, Moscow) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Ritika Mishra, Navjot Kaur. A Survey of Spelling Error Detection and Correction Techniques // International Journal of Computer Trends and Technology. 2013. V. 4, Is. 3. (372).
2. Шеннон К. Работы по теории информации и киберне-тике. М.: Издательство иностранной литературы, 1963. (275).
3. Выголов О. В., Визильтер Ю. В., Каратеев С. Л. Алгоритмы автоматического обнаружения и считывания номеров железнодорожных вагонов и цистерн // Вестник компьютерных и информационных технологий. 2013. № 10. С. 13 – 19.
4. Автоматическое распознавание железнодорожных номерных знаков на видеопоследовательностях / Ю. В. Визиль-тер и др. // Вестник компьютерных и информационных техно-логий. 2014. № 9. С. 3 – 9.
5. Гудков В. Ю., Гудкова Е. Ф. N-граммы в лингвистике // Вестник Челябинского государственного университета. 2011. № 24. С239).
6. Ukkonen E. Approximate String Matching with q-Grams and maximal matches // Theoretical Cоmputer Science. 1992. V. 92, Nо 1.
7. Формальный метод нечеткого поиска персональной информации / А. В. Бондаренко и др. // Препринты ИПМ им. М. В. Келдыша. 2009. № 64. 25 с.
8. URL: http://ru.wikipedia.org/wiki / Генетический алго-ритм.
9. URL: http://www.math.nsc.ru/AP/benchmarks/UFLP/ uflp_ga.html
10. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Докл. АН СССР. 1965. Т. 163, № 4.

Eng

1. Ritika Mishra, Navjot Kaur. (2013). A survey of spelling error detection and correction techniques. International Journal of Computer Trends and Technology, 4(3).
2. Shennon K. (1963). Work on information theory and cy-bernetics. Moscow: Izdatel'stvo inostrannoi literatury.
3. Vygolov O. V., Vizil'ter Iu. V., Karateev S. L. (2013). Al-gorithms for automatic detection and reading of railway wagon and tank numbers. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (10), pp. 13-19.
4. Gudkov V. Iu., Gudkova E. F. (2011). N-grams in linguis-tics. Vestnik Cheliabinskogo gosudarstvennogo universiteta, (24).
5. Ukkonen E. (1992). Approximate string matching with q-Grams and maximal matches. Theoretical Cоmputer Science, 92(1).
6. Bondarenko A. V., Vizil'ter Iu. V., Klyshinskii E. S., Silaev N. Zh., Maksimov V. Iu., Musaeva T. N. (2009). A formal method of fuzzy search for personal information. Preprints of IPM named after M. V. Keldysh, 64.
7. The genetic algorithm. Available at: http://ru.wikipedia. org/wiki/
8. Available at: http://www.math.nsc.ru/AP/benchmarks/UFLP/ uflp_ga.html
9. Levenshtein V. I. (1965). Binary codes with correction of deletions, insertions and substitutions of characters. Doklady Akademii Nauk SSSR, 163(4).

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

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

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2015.04.pp.014-018}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2015.04.pp.014-018}