Процессы управления и устойчивость

5. Оценки эффективности. Разработанная и представленная в

п.4 параллельная форма вычисления быстрого преобразования Фу-

рье обладает рядом полезных свойств:

• cбалансированность вычислительной нагрузки на процессоры

(все выделенные процессоры выполняют одно и то же количе-

ство арифметических операций);

• как следствие, полнота загрузки процессоров (выделенные для

работы процессоры не простаивают);

• малое межпроцессорное взаимодействие (обмен данными меж-

ду процессорами происходит всего один раз);

• простота программной реализации (алгоритм БПФ разбивает-

ся на серию таких же алгоритмов для каждого процессора).

Малость межпроцессорного взаимодействия особенно важна для

систем с распределённой памятью, в том числе, для вычислитель-

ных кластеров, где сильное снижение производительности происхо-

дит вследствие задержек на передачу сообщений.

Но тем не менее, приведённый алгоритм подходит и для про-

граммирования симметричных многопроцессорных систем с общей

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

номерно.

Литература

1. Демьянович Ю.К. Лекции по компьютерной алгебре. Системы

аналитических вычислений. СПб.: Изд-во СПбГУ, 1999. 103 с.

2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов:

Пер. с англ. М.: Мир, 1989. 448 с.

3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.:

БХВ-Петербург, 2004. 608 с.

449

Терехов И.А.

Санкт-Петербургский государственный университет

Алгоритм быстрого сегментирования

изображений невыровненного текста

Рекомендовано к публикации доцентом Мисеновым Б.А.

1. Введение. В задачах оптического распознавания символов

(OCR – optical character recognition) важным шагом является сег-

ментирование исходного изображения с целью выделения отдель-

ных частей текста, таких как строки, слова и символы. Если строки

не параллельны границам изображения и не выровнены вдоль пря-

мых, сегментация становится нетривиальной задачей. В данной ра-

боте предлагается алгоритм, позволяющий быстро сегментировать

текст в таких нетривиальных случаях.

2. Постановка задачи. Пусть изображение текста есть матрица

яркостей H = {h

i,j

}

m,n

i,j=1

, h

i,j

∈ [0, h

max

]. Считаем, что:

• H содержит только изображения текста и однородного фона;

• допускаются небольшие шумы случайного характера;

• текст темнее фона (имеет значение на последних шагах алго-

ритма);

• Γ – множество гладких кривых, вдоль которых проходят стро-

ки текста;

• существует прямая L такая, что любого γ ∈ Γ угол между её

направляющим вектором η(p) в точке p и прямой L мал (пред-

почтительно, не более десяти градусов) для всех p ∈ γ.

Назовем угол ϕ ∈ [0, π] между L и нижней границей изображения

"приблизительным углом поворотом текста". Решением задачи сег-

ментации строк будем считать нахождение множества кривых Γ.

Сегментированными словами (символами) будем считать части этих

кривых.

3. Нахождение угла поворота текста. На данном этапе опре-

деляется приблизительный угол поворота текста ϕ.

3.1. Контрастности по направлениям (КПН). Для каж-

дой пары соседних по горизонтали пикселей найдем модуль разности

450

их яркостей. Их сумму, умноженную на

√

2, назовем "горизонталь-

ной контрастностью":

a =

√

2(

m

i=1

n−1

j=1

|h

i,j

− h

i,j+1

|).

Аналогичным образом определим вертикальную и две диагональные

контрастности:

b =

√

2(

m−1

i=1

n

j=1

|h

i,j

− h

i+1,j

|),

c =

m−1

i=1

n−1

j=1

|h

i,j

− h

i+1,j+1

|,

d =

m−1

i=1

n−1

j=1

|h

i+1,j

− h

i,j+1

|.

Рис. 1. Контрастности по

направлениям

3.2. Зависимость КПН от

наклона прямых. Пусть есть изоб-

ражение прямой длины l c яркостью

вдоль оси h

line

, повернутой на угол α.

Фон изображения имеет яркость h

bg

.

Считаем l много больше толщины

прямой. Тогда a и b пропорциональны

числу строк и столбцов, через кото-

рые проходит прямая, соответствен-

но:

a ≈ 2l|h

line

− h

bg

|| sin α|,

b ≈ 2l|h

line

− h

bg

|| cos α|.

Отсюда следует

lim

l→∞

(a/b) = | tg α|.

(1)

Аналогичным образом получаем

lim

l→∞

(c/d) = | tg α + π/4|.

(2)

451

Нетрудно заметить, что способ сглаживания прямой не влияет на

результат, так как не имеет значения плавность изменения яркости

вдоль любого из направлений (рис. 1). Также для формул (1) и (2)

достаточно, чтобы выполнялось h

line

= h

bg

.

3.3. Влияние круглых пятен на КПН. Добавим к предыду-

щему изображению круглое пятно яркости h

round

= h

bg

достаточно

большого радиуса r, не касающееся прямой. Тогда все контрастности

увеличатся на величину Z = 4

√

2h

round

r. Формулы (1) и (2) можно

переписать в уточненном виде с учетом Z:

lim

l→∞,r→∞

a − Z

b − Z

= | tg α|,

lim

l→∞,r→∞

c − Z

d − Z

= | tg α +

π

4

|.

Считая l и r достаточно большими, составим системы для α и Z:







tg α =

a−Z

b−Z

,

tg (α +

π

4

) =

c−Z

d−Z

,

α ∈ [0,

π

4

),







tg α =

a−Z

b−Z

,

tg (α +

π

4

) = −

c−Z

d−Z

,

α ∈ [

π

4

,

π

2

),







tg α = −

a−Z

b−Z

,

tg (α +

π

4

) = −

c−Z

d−Z

,

α ∈ [

π

2

,

3π

4

),







tg α = −

a−Z

b−Z

,

tg (α +

π

4

) =

c−Z

d−Z

,

α ∈ [

3π

4

, π].

(3)

Кроме того, должно выполняться















a ≥ Z,

b ≥ Z,

c ≥ Z,

d ≥ Z.

(4)

Из каждой из этих систем можно получить квадратное уравнение

относительно Z. Например, для α ∈ [0,

π

4

) имеем

2Z

2

− 2(a + d)Z + ad + ac + bd − bc = 0,

Z =

a + d −

√

a

2

+ d

2

− 2ac − 2bd + 2bc

2

,

второй корень отбрасываем, так как он не удовлетворяет (4). Решив

все четыре системы, из получившихся пар корней (α

i

, Z

i

) выбираем

452

пару (α

∗

, Z

∗

) такую, что Z

∗

= min Z

i

. Стоит отметить, что если

пятно сглажено, формулы (4) будут достаточно точны для любых r.

3.4. Зависимость КПН от равномерных шумов. Нало-

жим на изображение случайный шум. Если он не является анизо-

тропным, его влияние на все контрастности по направлениям будет

примерно одинаковым. Если при m → ∞, n → ∞ обозначить влия-

ние шума за Z, будут верны все формулы предыдущего подраздела.

Таким образом, уравнения (3) не различают шумы и круглые пятна,

и найденное с их помощью значение α

∗

равно углу наклона прямой

на зашумленном изображении.

3.5. Влияние граничных точек прямых на КПН. До это-

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

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

длина отрезка l мала, а толщина его равна p. Тогда её границу можно

представить как два параллельных отрезка и две полуокружности,

соединяющих эти отрезки на концах. Это эквивалентно границам

части бесконечной прямой и одного круглого пятна радиуса p. Сле-

довательно, если найти значение α

∗

по формулам (3), то оно будет,

по крайней мере, близко к значению угла наклона отрезка.

3.6. Изменение КПН при добавлении прямых. Доба-

вим на изображение вторую прямую длины γl, повернутую на угол

(α + θ). Вывести величину изменения решения (α

∗

, Z

∗

) достаточно

сложно, однако множественные эксперименты дают следующие ре-

зультаты:

1. Если угол θ достаточно мал (по крайней мере, не более десяти

градусов), а γ близко к единице, то α

∗

≈ α + θ/2, а величина

Z

∗

a+b+c+d

достаточно мала;

2. Если γ = 1, то α

∗

смещается в сторону наклона большей из

прямых (α или α + θ);

3. Если θ ≈

π

2

, т.е. прямые почти перпендикулярны, и при этом γ

в несколько раз меньше единицы, то α

∗

≈ α, а Z

∗

велико;

4. Если θ ≈

π

2

и γ ≈ 1, то или α

∗

не выражает ничего полез-

ного (при этом Z близко к одной из контрастностей), или не

существует.

3.7. Обобщение свойств КПН. Пусть есть изображение

некоторого числа кривых (назовем их строками), приблизительный

453

угол поворота которых равен ϕ. При этом на изображении присут-

ствует шум, пятна и незначительное количество кривых c прибли-

зительным углом поворота (ϕ + π/2). Тогда в силу описанных выше

свойств найденное с помощью уравнений (3) α

∗

≈ ϕ.

3.8. MIP-уровни изображения текста. Пусть есть изоб-

ражение текста H, которое надо распознать. Обозначим H

0

≡ H,

m

0

≡ m, n

0

≡ n. Определим изображение H

k

из элементов h

k

i,j

раз-

мера [m

k

× n

k

] по следующему правилу:

h

k

i,j

= (h

k−1

2i,2j

+ h

k−1

2i+1,2j

+ h

k−1

2i,2j+1

+ h

k−1

2i+1,2j+1

)/4,

при этом m

k

≡ m

k−1

/2, n

k

≡ n

k−1

/2. Если размерности H

k−1

не

кратны двум, доопределим его, продублировав последнюю строку,

последний столбец и крайнюю угловую точку изображения. Таким

образом, все размерности матриц будут оставаться натуральными

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

название mipmaps (от лат. multum in parvo – многое в малом про-

странстве) и особенно широко применяются в визуализации трехмер-

ных объектов. Изображение H

k

есть mipmap k-го уровня. Так как

каждый последующий уровень представляет собой уменьшенную ко-

пию предыдущего, в определенный момент получим уровень H

s

, на

котором будут видны лишь строки текста шириной в 1-3 пикселя,

символы которых визуально сливаются. Найдя для него КПН и ре-

шив систему (3), получим (α

∗

s

, Z

∗

s

), где α

∗

≈ ϕ. Отметим также, что

для H

s

величина Z

∗

s

/(a

s

+ b

s

+ c

s

+ d

s

) будет минимальной, так как

меньшие уровни содержат большое количество штрихов, перпенди-

кулярных строкам (это штрихи символов строки), а в более высоких

уровнях строки текста будут сливаться в крупные блоки. Таким об-

разом, построив все mipmaps, найдя пары (α

∗

k

, Z

∗

k

) для каждого из

них и выбрав из них такую (α

∗

s

, Z

∗

s

), для которой Z

∗

s

/(a

s

+b

s

+c

s

+d

s

)

минимально, найдем приблизительный угол поворота текста и раз-

мер букв (2

s

) с точностью до порядка. Такой точности будет доста-

точно для дальнейшей работы алгоритма.

4. Выделение строк. На предыдущем шаге были получены ве-

личины α

∗

s

, Z

∗

s

и s. Разобъем изображение на полосы ширины 2

s

ω,

проходящие под углом (α

∗

s

+ π/2), где ω ∈ [3, 7] (оптимальная ве-

личина пока не известна, однако её можно будет вывести в буду-

щем на основе статистических данных). Часть каждой строки, по-

павшей в полосу, будет достаточно прямой в силу того, что полоса

454

узкая. По этой же причине проекции строк на перпендикулярные

им оси в большинстве случаев не будут перекрываться. Следова-

тельно, можно применить широко известный метод суммирования

яркостей по строкам пикселей [1]. В основе его лежит тот факт, что

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

чается от суммы яркостей вдоль строк текста, что позволяет опре-

делить положение параллельных друг другу строк. В силу малой

ширины каждой из полос, вместо пиксельных строк можно брать

несглаженные прямые, построенные, например, по алгоритму Бре-

зенхейма [2]. Множество "параллельных" брезенхеймовских прямых

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

горитм будет работать только с целочисленной арифметикой, что

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

кой "высоте" в системе координат каждой из полос располагаются

строки и межстрочные промежутки. Таким образом определим, что

в первой полосе строки имеют "высоты" (в системе координат по-

лосы) (y

0,1

, y

1,1

, . . . ), во второй – (y

0,2

, y

1,2

, . . . ), и так далее. По этим

точкам можно построить проходящие через них кривые Безъе, до-

статочно точно представляющие кривые γ ∈ Γ. Несложными алго-

ритмами можно восстановить "утерянные" точки и исключить лиш-

ние. Также можно применять дополнительное разбиение полос для

разрешения неоднозначностей.

Замечание 1. Даже если заранее известно, что строки прямые,

в разбиении на полосы всё равно есть смысл, так как это позволяет

значительно уточнить угол поворота текста.

Замечание 2. В связи с тем, что алгоритм суммирования по

строкам применяется для узких полос, полученные кривые следу-

ет экстраполировать в обоих направлениях примерно на половину

ширины полосы, иначе некоторая часть информации будет утеряна.

5. Дальнейшая сегментация. После того, как строки выде-

лены, можно повторно применить алгоритм суммирования ярко-

стей [1], на этот раз введя криволинейную систему координат для

каждой строки из кривой и нормалей к ней. Для упрощения расче-

тов можно аппроксимировать кривую отрезками, и в каждом из них

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

6. Оценка эффективности алгоритма. В процессе нахожде-

ния угла ϕ были построены mipmaps, суммарно увеличившие объем

хранимой информации примерно на 33%. Их построение выполня-

455

ется за один проход по изображению и значительно ускоряется при

использовании технологии MMX. Нахождение КПН также можно

произвести за один проход по изображению, если считать его для

блоков пикселей [2 × 2] (содержащего информацию для 2-х слагае-

мых к a и b, и одного к c и d), параллельно используя эти блоки

для построения следующего mipmap. Такое упрощение слабо ска-

жется на результате вычислений. При рекурсивной организации ал-

горитма можно вообще не хранить mipmaps, что позволяет сегмен-

тировать изображения с минимальными затратами памяти. В любом

случае, нахождение КПН требует не более двух проходов и реализу-

ется с применением целочисленной арифметики. Решение уравнений

(3) производится один раз для каждого mipmap за крайне небольшое

конечное время.

Замечание 3. Нет смысла считать КПН как минимум для пер-

вых трех mip-уровней, так как если для одного из них Z

∗

/(a+b+c+d)

минимально, это означает, что символы текста имеют высоту по-

рядка восьми пикселей. Большинство алгоритмов распознавания всё

равно не работают с такими символами. Это замечание позволяет в

несколько раз сократить объем вычислений.

Дальнейшая сегментация происходит, опять же, за линейное вре-

мя, зависящее от эффективности реализации алгоритмов суммиро-

вания по строкам. Таким образом, время работы всего алгоритма

крайне мало.

Литература

1. Manmatha R., Srimal N. Scale space technique for word segmentation

in handwritten manuscripts // The Second Intern. Conf. on

scale-space theories computer vision (Scale Space 99), 1999.

P. 22–33.

2. Bresenham J.E. Algorithm for computer control of a digital plotter

// IBM Systems Journal, 1965. V. 4(1). P. 25–30.

456

Ярцев А.С.

Санкт-Петербургский государственный университет

Разработка системы управления

бизнес–процессами с использованием

Microsoft BizTalk Server 2004

Рекомендовано к публикации профессором Овсянниковым Д.А.

Введение. Разработка систем автоматизации началась уже дав-

но и затронула самые разнообразные области деятельности челове-

ка. Начиная от систем управления сложными устройствами, авто-

матизация постепенно пришла и в управление производством, скла-

дами, компаниями, управление финансовыми потоками и организа-

циями, управление персоналом и в другие отрасли. Таким образом,

автоматизация постепенно захватывает все больше и больше обла-

стей деятельности человека и организует в них электронную систему

[1], позволяющую любому сотруднику оперативно получать необхо-

димую ему для работы информацию и устранять рутинный труд,

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

Стандарт ГОСТ 34.003-90 «Информационная технология. Комплекс

стандартов на автоматизированные системы. Термины и определе-

ния» определяет термин «автоматизированная система» следую-

щим образом.

Автоматизированная система (АС) – система, состоящая из пер-

сонала и комплекса средств автоматизации его деятельности, реали-

зующая информационную технологию выполнения установленных

функций.

Примечания:

1. В зависимости от вида деятельности выделяют, например, сле-

дующие виды АС: автоматизированные системы управления (АСУ),

системы автоматизированного проектирования (САПР), автомати-

зированные системы научных исследований (АСНИ) и др.

2. В зависимости от вида управляемого объекта (процесса) АСУ

делят, например, на АСУ технологическими процессами (АСУТП),

АСУ предприятиями (АСУП) и т.д.

Понятие «установленные функции», по сути, являются опреде-

лением бизнес-процесса. Бизнес процесс – устойчивый информаци-

457

онный процесс (последовательность работ), относящийся к произ-

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

тированный на создание новой стоимости. Например, компания мо-

жет сознательно организовать информационный бизнес-процесс сво-

его основного производства. Бизнес-процесс включает в себя иерар-

хию взаимосвязанных функциональных действий, реализующих од-

ну или несколько бизнес-целей компании, в информационной системе

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: