Обеспечение распознавания почтовых индексов в реальном времени

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

где - производительность АЛСМ.

Так, при ПО за час с.

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

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

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

Организация процесса распознавания ПИ существенно зависит от принятой формы представления его цифр.

На рис. 5.19наведено основные формы представления цифр ПИ ( а -стилизовани; б - нормализованы с отдельными ограничивающими рамками для каждой цифры; в - нормализованы с примыкающими ограничивающими рамками для каждой цифры; г - нормализованы с единственной ограничивающей рамки для всех цифр ПИ; д - ненормализованное цифры ПИ).

Формы представления цифр ПИ

Рисунок 5.19 - Формы представления цифр ПИ

Основными направлениями решения задачи обеспечения распознавания ПИ в реальном времени являются:

- Существенное повышение производительности однопроцессорной ЭВМ;

- Применение многопроцессорных ЭВМ.

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

Варианты организации процесса распознавания цифр ПИ при использовании однопроцессорной ЭВМ

Рисунок 5.20 - Варианты организации процесса распознавания цифр ПИ при использовании однопроцессорной ЭВМ

В варианте а при длине трафарета 5 мм и промежутка между цифрами 4 мм время считывания одной цифры составляет мс, а время распознавания одной цифры мс.

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

На рис. 5.21 приведены основные варианты организации процесса распознавания цифр ПИ при использовании пяти процессорной ЭВМ ( а - распознавание при применении отдельных ограничительных рамок для каждой цифры ПИ; б - распознавание при применении единой ограничительной рамки для всех цифр ПИ).

Варианты организации процесса распознавания цифр ПИ при использовании пьятипроцесорнои ЭВМ

Рисунок 5.21 - Варианты организации процесса распознавания цифр ПИ при использовании пьятипроцесорнои ЭВМ

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

На рис. 5.22 приведены варианты организации многопроцессорного распознавания цифр ПИ на адресных ярлыках посылок ( а - каждый из процессоров распознает одну стилизованную или нормализованную цифру; б - каждый из процессоров распознает один сегмент одной стилизованной цифры).

Варианты организации многопроцессорного распознавания цифр ПИ на адресных ярлыках посылок

Рисунок 5.22 - Варианты организации многопроцессорного распознавания цифр ПИ на адресных ярлыках посылок

Как следует из рис. 5.22, количество процессоров в варианте а составляет 15, а в варианте б - 105. Почти во столько же раз возрастает время, может быть выделен для распознавания ПИ по сравнению с тем, что может быть выделен для распознавания ПИ при использовании однопроцессорной ЭВМ.

То, что каждый из процессоров многопроцессорной ЭВМ работает по одной и той же программой, делает целесообразным применение для распознавания цифр ПИ вычислительных систем с параллельными процессорами синхронно выполняют одни и те же операции.

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

Управление выполнением операций параллельными процессорами осуществляется центральным процессором.

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

Активные процессоры воспринимают все команды центрального процессора (в том числе команды перевода их в пассивные процессоры), а пассивные процессоры - только команду перевода их в активные процессоры.

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

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

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

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

На рис. 5.23 приведен пример графа безцикловои программы.

Пример графа безцикловои программы

Рисунок 5.23 - Пример графа безцикловои программы

Граф программы содержит 16 ветвей (дуг), которые разветвляются и соединяются в 10 точках (вершинах).

В табл. 5.18 приведены три варианта порядке прохождения ветвей программы графа рис. 5.23 в соответствии с приведенным правила, в каждом из которых каждая из проходит только один раз.

Таблица 5.18 - Варианты порядке прохождения ветвей программы

№ п / п

Вариант прохождения ветвей

программы

1

2

3

1

1

1

1

2

2

2

2

3

3

4

4

4

4

5

3

5

5

6

7

6

6

3

10

7

7

7

8

8

8

8

6

9

9

9

9

10

10

10

12

11

11

12

14

12

12

14

5

13

13

11

13

14

14

13

11

15

15

15

15

16

16

16

16

Структурный алгоритм управления параллельными процессорами по варианту 1 табл. 5.18 включает следующие команды:

1. Формирование группы процессоров G1.

2. Перевод группы процессоров G 1 в активный режим.

3. Прохождение ветви 1 программы.

4. Перевод группы процессоров G 1 в пассивный режим.

5. Формирование из группы процессоров G 1 групп процессоров G 2, G3.

6. Перевод группы процессоров G 2 в активный режим.

7. Прохождение ветви 2 программы.

8. Перевод группы процессоров G 2 в пассивный режим.

9. Перевод группы процессоров G3 в активный режим.

10. Прохождение ветви 3 программы.

11. Перевод группы процессоров G3 в пассивный режим.

12. Формирование из группы процессоров G2 групп процессоров G4, G5, G6.

13. Перевод группы процессоров G4 в активный режим.

14. Прохождение ветви 4 программы.

15. Перевод группы процессоров G4 в пассивный режим.

16. Перевод группы процессоров G5 в активный режим.

17. Прохождение ветви 5 программы.

18. Перевод группы процессоров G 5 в пассивный режим.

19. Перевод группы процессоров G 6 в активный режим.

20. Прохождение ветви 6 программы.

21. Перевод группы процессоров G6 в пассивный режим.

22. Формирование из группы процессоров G3 групп процессоров G7, G8, G9.

23. Перевод группы процессоров G 7 в активный режим.

24. Прохождение ветви 7 программы.

25. Перевод группы процессоров G7 в пассивный режим.

26. Перевод группы процессоров G8 в активный режим.

27. Прохождение ветви 8 программы.

28. Перевод группы процессоров G8 в пассивный режим.

29. Перевод группы процессоров G 9 в активный режим.

30. Прохождение ветви 9 программы.

31. Перевод группы процессоров G 9 в пассивный режим.

32. Формирование из групп процессоров G4, G7 групп процессоров G 10 , G 11.

33. Перевод группы процессоров G10 в активный режим.

34. Прохождение ветви 10 программы.

35. Перевод группы процессоров G10 y пассивный режим.

36. Перевод группы процессоров G11 в активный режим.

37. Прохождение ветви 11 программы.

38. Перевод группы процессоров G 11 в пассивный режим.

39. Формирование 3 групп процессоров G 6 , Gg групп процессоров G12, G13.

40. Перевод группы процессоров G12 в активный режим.

41. Прохождение ветви 12 программы.

42. Перевод группы процессоров G12 y пассивный режим.

43. Перевод группы процессоров G13 в активный режим.

44. Прохождение ветви 13 программы.

45. Перевод группы процессоров G13 в пассивный режим.

46. Формирование из групп процессоров G8, G10, G12 группы процессоров G

47. Перевод группы процессоров G14 в активный режим.

48. Прохождение ветви 14 программы.

49. Перевод группы процессоров G14 в пассивный режим.

50. Формирование из групп процессоров G5, G11, G13 группы процессоров G

51. Перевод группы процессоров G15 в активный режим.

52. Прохождение ветви 15 программы.

53. Перевод группы процессоров G15 в пассивный режим.

54. Формирование из групп процессоров G14, G15 группы процессоров G16.

55. Перевод группы процессоров G16 в активный режим.

56. Прохождение ветви 16 программы.

57. Перевод группы процессоров G16 пассивный режим.

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

Поделиться материалом

Содержание