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

• ∆E and ∆E

S

: This is used as a human visuality measure that

measures the color difference. ∆E

S

is ∆E calculation with S-

CIELAB that is a spatial extension of CIELAB, designed for

computer displays [16]. Standard D65 was used as a light sorce

in the calculations. Human can not separate two colors from each

other, if ∆E is below 1.

The error measures are calculated as follows:

MSD =

1

k

k

i=1

n

j=1

(I

j,i

− I

∗

j,i

)

2

,

(4)

PSNR = 10 log

10

255

2

MSE

,

(5)

∆E =

1

k

k

i=1

∆L

∗2

i

+ ∆a

∗2

i

+ ∆b

∗2

i

,

(6)

where I

j,i

is the channel value of original image, I

∗

j,i

is the channel value

of reconstructed image and MSE is the mean squared error. Also ∆L

∗

i

,

∆a

∗

i

and ∆b

∗

i

are differences of the CIE L

∗

a

∗

b

∗

color coordinates which

can be calculated from I

i

and I

∗

i

[2].

The compression ratio (CR) is calculated as follows:

CR =

size of original image (bytes)

size of compressed image (bytes)

.

(7)

The average results and compression ratios of the whole database

with different subsampling schemes are shown in tables 1 and 2. Here,

three eigenimages were used. In 3 × 3 blocks, center, upper-left corner

or average value of the block is used. In table 3, the ∆E error with

different amount (m) of eigenimages are shown with different 3 × 3

block subsampling schemes. Scheme 4:2:0 with 3 eigenimages is shown

as reference. Some examples of theoretical time required for transferring

the image over a network is shown in table 4.

271

Table 1. Average results of FOREST database.

Scheme

MSD

PSNR

∆E

∆E

S

CR

4:4:4

12.44

41.39

1.53

1.01

13.3

4:2:2

17.28

37.94

2.97

1.31

19.9

4:2:0

21.76

35.87

4.23

1.71

26.5

4:1:1

23.57

34.97

4.73

2.15

26.5

3 × 3 (corner)

26.80

34.08

5.62

2.50

32.4

3 × 3 (center)

23.90

35.17

4.82

2.02

32.4

3 × 3 (average)

21.18

36.60

4.14

1.47

32.4

Table 2. Average results of CORAL database.

Scheme

MSD

PSNR

∆E

∆E

S

CR

4:4:4

18.81

37.72

3.00

2.15

13.3

4:2:2

22.49

35.58

3.79

2.29

19.9

4:2:0

25.59

34.18

4.38

2.50

26.5

4:1:1

27.16

33.44

4.63

2.69

26.5

3 × 3 (corner)

29.04

32.89

4.96

2.83

32.4

3 × 3 (center)

27.42

33.53

4.73

2.66

32.4

3 × 3 (average)

24.96

34.72

4.20

2.33

32.4

Table 3. Average ∆E results of FOREST database.

Scheme

∆E

∆E

S

CR

4:2:0, m = 3

4.23

1.71

26.5

3 × 3, m = 3 (center)

4.82

2.02

32.4

3 × 3, m = 4 (center)

4.67

1.81

29.7

3 × 3, m = 5 (center)

4.61

1.73

27.3

3 × 3, m = 3 (average)

4.14

1.47

32.4

3 × 3, m = 4 (average)

3.96

1.16

29.7

3 × 3, m = 5 (average)

3.91

1.04

27.3

Table 4. Examples of theoretical time required for transferring images.

Format

Size

56000 bps

128000 bps

512000 bps

Orig. image

1

655360 B

1.5 min

41.0 s

10.2 s

4:4:4

1,3

49272 B

7 s

3.1 s

0.8 s

4:2:0

1,3

24696 B

3.5 s

1.5 s

0.4 s

Orig. image

2

63963136 B

2.5 h

1.1 h

16.7 min

4:4:4

2,3

3145911 B

7.5 min

3.3 min

49 s

4:2:0

2,3

1573047 B

3.7 min

1.6 min

25 s

1

128 x 128 pixels, 40 channels

2

1024 x 1024 pixels, 61 channels

3

3 eigenimages

272

4. Conclusions. The spectral compression alone done with PCA

reduces the image size significantly, keeping the image quality high and

giving small error values. Adequate results can be achieved already with

3. . . 5 eigenimages. The advantage of the compression can be clearly seen

in table 4. The errors in Coral database are higher, because there is more

variety in the hues.

The errors are quite equal with 3 × 3 block center and 4:1:1 scheme.

However, the compression ratio is better in 3 × 3 scheme, questioning

the need of 4:1:1 scheme. Using average values gives a lot of benefits

for the compression. The scheme 3 × 3 (average) with 5 eigenimages

gives approximately the same compression ratio as 4:2:0 scheme with 3

eigenimages (27.3 and 26.5, respectively). However, the errors are lower

in 3×3 block size sceme than in 4:2:0 scheme. Average ∆E

S

is 1.04 in 3×3

average scheme and 1.71 in 4:2:0 scheme. In addition, the average of a

block may smooth the image more, since the new values are combinations

of several original values. Therefore, more research has to be done for

finding optimal number of eigenimages and optimal subsampling scheme.

References

1. Ajito T., Obi T., Yamaguchi M., Ohyama N. Six-primary color

projection display for expanded color gamut reproduction // Proc.

Intern. Symp. on multispectral imaging and color reproduction //

Chiba, Japan, October 21 – 22, 1999. P. 135–138.

2. Wyszecki G., Stiles W. Color science: consepts and methods,

quantitative data and formulae, 2nd ed. New York: Wiley, 1982.

3. MacDonald L., Luo M. Colour image science. England, John Wiley

& Sons, Ltd., 2002.

4. Hauta-Kasari M., Parkkinen J.P., Jaaskelainen T., Lenz R. Spectral

based analysis of color images // Proc. 8th Congress of the

international colour association, AIC Color 97, Kyoto, Japan, May

25 – 30, 1997. V. II. P. 548–551.

5. MacDonald L., Westland S., Shaw J. Colour image reproduction:

Spectral vs spatial // Proc. Intern. Symp. on multispectral imaging

and color reproduction, Chiba, Japan, October 21 – 22, 1999.

P. 81–91.

273

6. Hauta-Kasari M., Lehtonen J., Parkkinen J.P., Jaaskelainen T.

Representation of spectral images in data communications // 9th

Congress of the international colour association, AIC Color 01

Rochester, Rochester, NY, USA, June 24 – 29, 2001 // Proc. of SPIE

4421, 2002. P. 500–503.

7. K¨onig F., Praefcke W. Multispectral image encoding // Proc. IEEE

Intern. Conf. on image processing, ICIP, Kobe, Japan, October 24 –

28, 1999. V. 3. P. 123–126.

8. Parkkinen J.P., Hallikainen J., Jaaskelainen T. Characteristic spectra

of munsell colors // Journal of the Optical Society of America A,

1989. V. 6, № 2. P. 318–322.

9. Maloney L. Evaluation of linear models of surface spectral reflectance

with small numbers of parameters // Journal of the Optical Society

of America A, 1986. V. 3, № 10. P. 1673–1683.

10. Hyv¨arinen A., Karhunen J. Oja E. Independent component analysis.

John Wiley & Sons., 2001.

11. Wachtler T., Lee T.-W., Sejnowski T. Chromatic structure of natural

scenes // Journal of the Optical Society of America A, 2001. V. 18,

№ 1. P. 65–77.

12. Kaiser P., Boynton R. Human color vision, 2nd ed. Washington D.C.:

Optical Society of America, 1996.

13. Wu C., Irwin J. Emerging multimedia computer communication

technologies. New Jersey: Prentice – Hall, Inc., 1998.

14. Hauta-Kasari M., Lehtonen J., Parkkinen J.P., Jaaskelainen T.

Image format for spectral image browsing // Journal of Imaging

Science & Technology, accepted for publication.

15. Chiao C.-C., Cronin T., Osorio D. Color signals in natural scenes:

characteristics of reflectance spectra and effects of natural illuminants

// Journal of the Optical Society of America A, 2000. V. 17, № 2.

P. 218–224.

16. Zhang X., Wandell B. A spatial extension of CIELAB for digital

color image reproduction // Proc. Society for Information Display

Symposium Technical Digest, SID, 1996. V. 27. P. 731–734.

274

Абрамова А. С., Абрамов Е. С.

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

Параллельное программирование

с использованием технологии OpenMP

Технология OpenMP — это стандарт, созданный группой произ-

водителей программного и аппаратного обеспечения OpenMP ARB.

Целью создания такого стандарта было упростить построение мно-

гопоточных приложений, разработка которых становится все более

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

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

функций и переменных окружения.

Технология OpenMP предназначена для создания параллельных

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

как параллелизм по данным, так и функциональный параллелизм

[1].

Для тестирования и отработки методов программирования с ис-

пользованием OpenMP был выбран проект по созданию обучающей

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

принадлежит проф. С. Н. Андрианову.

Рис. 1. Физическая модель задачи

В качестве физической модели системы управления пучком

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

четырех магнитных линз. Схема этой последовательности представ-

лена на рис. 1, где R

j

, j = 1, 4 — операторы, описывающие управля-

ющие линзы и промежутки между ними; E — источник частиц; T —

мишень.

Математическая модель системы основана на использовании

матричных операций. Оператор эволюции, описывающий влияние

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

риц: R

tot

= R

9

× R

8

× . . . × R

1

. Начальные данные для этого опера-

тора эволюции формируются в виде матрицы M

0

, столбцы которой

состоят из фазовых координат частиц пучка (x, x , y, y )

T

. Конечное

состояние пучка описывается соотношением M

res

= R

tot

× M

0

.

275

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

портрет изменяется. Задачей обучающей системы является проде-

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

параметров линз R

2j

, j = 1, 4 и свободных промежутков L

i

, i = 1, 9.

Требования к модели. Моделирующая программа должна по-

казывать вид фазового портрета пучка в начальной и конечной точ-

ках его траектории. Для того, чтобы модель была адекватна ре-

альности, необходимо смоделировать движение достаточно большого

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

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

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

Чтобы связь между изменением параметров системы и изменением

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

чтобы визуализация результатов работы программы происходила за

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

Эти, на первый взгляд, противоречивые требования можно вы-

полнить при помощи технологии OpenMP, использовав в полной ме-

ре возможности двухпроцессорных машин.

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

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

ными операциями между параллельными потоками. Однако, относи-

тельно нетрудоемкие операции работы с матрицами нецелесообраз-

но производить в нескольких потоках. В нашем случае матрицы R

i

имеют размерность [4 × 4], их всего девять, поэтому для вычисления

общей матрицы эволюции системы нет необходимости задействовать

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

ставимое со временем умножения. Исходя из этого, основной акцент

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

ражения M

res

= R

tot

× M

0

и алгоритма визуализации.

Проблемы, типичные для систем с общей памятью. Из-

вестно, что параллельная работа нескольких потоков с общей па-

мятью чревата специфичными проблемами, такими, как data race

(гонки за памятью) и deadlock (остановки).

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

начинают одновременно записывать и считывать из одного и того же

участка памяти. Обычно это приводит к замедлению работы про-

граммы. Эту проблему можно решать либо изменяя алгоритм ра-

276

боты программы, либо применяя специальные предложения, допол-

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

ность [2].

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

ние матриц R

tot

размерности 4 × 4 и M

0

размерности 4 × N , где

N = 100000 — число частиц.

Рассмотрим простой алгоритм умножения матриц:

for (int i=0; i

tot

.dimY; i++)

for(int j=0; j

0

.dimY; j++)

{

for (int k=0; k

tot

.dimX; k++)

M

res

.M[i][j] += R

tot

.M[i][k]*M

0

.M[k][j];

}

При использовании директив OpenMP код будет выглядеть так:

for (int i=0; i

tot

.dimY; i++) {

#pragma omp parallel for

for (int j=0; j

0

.dimY; j++) {

for (int k=0; k

tot

.dimX; k++)

M

res

.M[i][j] += R

tot

.M[i][k]*M

0

.M[k][j];

}

}

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

ко потоков (в зависимости от числа процессоров системы), которые

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

го после директивы pragma omp parallel for. Счетчики цикла ста-

новятся локальными для каждого потока. Ограничители счетчиков

цикла должны быть общими, иначе невозможно будет разделить ите-

рации цикла между потоками.

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

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

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

и усыплять потоки между итерациями внешнего цикла. В нашем

случае есть возможность избавиться от него:

#pragma omp parallel for shared(M

0

.dimY, R

tot

.dimX)

for (int j=0; j0

.dimY; j++)

for (int k=0; k

tot

.dimX; k++) {

M

res

.M[0][j] += R

tot

.M[0][k]*M

0

.M[k][j];

M

res

.M[1][j] += R

tot

.M[1][k]*M

0

.M[k][j];

277

M

res

.M[2][j] += R

tot

.M[2][k]*M

0

.M[k][j];

M

res

.M[3][j] += R

tot

.M[3][k]*M

0

.M[k][j];

}

Теперь потоки работают непрерывно, но остается еще проблема

одновременного обращения (data race) к памяти. Оба потока одно-

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

(R

tot

), что замедляет работу программы. Поэтому нужно разделить

между потоками не только витки цикла, но и участки памяти, с ко-

торыми они работают. Чтобы избежать подобных ситуаций мы ис-

пользовали ленточный алгоритм разбиения матриц:

#pragma omp parallel sections {

#pragma omp section {

for (int j=0; j

0

.dimY/2; j++) {

for (int k=0; k

tot

.dimX; k++) {

M

res

.M[0][j] += R

tot

.M[0][k]*M

0

.M[k][j];

M

res

.M[1][j] += R

tot

.M[1][k]*M

0

.M[k][j];

} } }

#pragma omp section {

for (int j=M

0

.dimY/2; j

0

.dimY; j++) {

for (int k=0; k

tot

.dimX; k++) {

M

res

.M[2][j] += R

tot

.M[2][k]*M

0

.M[k][j];

M

res

.M[3][j] += R

tot

.M[3][k]*M

0

.M[k][j];

} } }

}

#pragma omp parallel sections {

#pragma omp section {

for (int j=0; j

0

.dimY/2; j++) {

for (int k=0; k

tot

.dimX; k++) {

M

res

.M[2][j] += R

tot

.M[2][k]*M

0

.M[k][j];

M

res

.M[3][j] += R

tot

.M[3][k]*M

0

.M[k][j];

} } }

#pragma omp section {

for (int j=M

0

.dimY/2; j

0

.dimY; j++) {

for (int k=0; k

tot

.dimX; k++) {

M

res

.M[0][j] += M[0][k]*M

0

.M[k][j];

M

res

.M[1][j] += M[1][k]*M

0

.M[k][j];

} } }

}

278

В результате применения такого алгоритма производительность

работы функции умножения увеличивается в 1,5 раза.

Еще одним ресурсоемким участком кода является визуализация

пучка частиц. В процессе работы для каждой частицы рассчитается

её положение на экране и цвет. Цикл, отвечающий за это также мож-

но разделить для работы в двух потоках, что и было реализовано. В

результате время работы программы уменьшилось на 20%.

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

что простое применение средств OpenMP не всегда приводит к уве-

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

эффективности работы параллельной программы на SMP-системах,

как и для программ, работающих на системах с распределенной па-

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

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

Стандарт OpenMP можно использовать в связке с другими тех-

нологиями параллельного программирования, такими как MPI. В

дальнейшем работу построенной программной модели предполага-

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

чтобы визуализация проходила на одной машине, а расчет эволю-

ции пучка — на нескольких других.

Литература

1. OpenMP

official

site:

Frequently

asked

questions.

—

http://www.openmp.org/drupal/node/view/11 .

2. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений

для многопроцессорных вычислительных систем. Н. Новгород:

Изд-во ННГУ, 2000. 121 с.

3. М. Кузьминский. OpenMP: средства распараллеливания для мно-

гопроцессорных систем // Открытые системы, 1998. № 3.

279

Бабкин Д.Ю.

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

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

в растровых изображениях

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

Введение. Существует много различных компьютерных редак-

торов, позволяющих обрабатывать графические изображения и вы-

делять из них текст, распознавать его с целью дальнейшей обработки

в текстовом редакторе [1, 2]. Но алгоритмы, которые применяются

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

ственно, неизвестны.

С целью нахождения этих или альтернативных алгоритмов на

факультете ПМ-ПУ при поддержке компании Digital Design был со-

здан проект "Открытый код: распознавание графических изобра-

жений"[3]. "Открытый код" означает, что построенные алгоритмы

будут общедоступны в сети Интернет для ознакомления и использо-

вания без извлечения финансовой выгоды. Общей задачей проекта

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

ных букв из графических изображений и их распознавание.

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

щие только текст. Но алгоритм не работал, если в изображении при-

сутствовали элементы не текста (рисунки, графики и т.п.). Таким

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

изображения с текстом от всего другого. Алгоритм по решению этой

задачи описан в этой статье.

Постановка задачи. Любое изображение, хранимое в памяти

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

костей пикселов. Яркость отдельного пиксела представлена RGB-

моделью (red-green-blue), в которой любой цвет представляет собой

смесь трех базовых цветов: красного, зеленого и синего. Для удоб-

ства будем считать, что изображение — это матрица, элементами

которой являются вектора размерности 3, задающие яркость отдель-

ного пиксела. Пусть дана матрица изображения V

[w×h]

, где w— число

столбцов, h — число строк. Ее элементы a

ij

имеют вид

280

a

ij

=





r

ij

g

ij

b

ij



 ,

где r

ij

— красная составляющая яркости пиксела, g

ij

— зеленая, b

ij

— синяя, r

ij

, g

ij

, b

ij

— целые числа, лежащие в промежутке [0, 255].

Теперь перейдем непосредственно к алгоритму.

Разбиение изображения на черный и белый цвета. Для на-

чала необходимо сделать изображение черно–белым. Делается это из

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

но, так как цветовые характеристики текста не всегда отличаются от

характеристик рисунка и т.п., к тому же, гораздо удобнее работать

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

Сначала делаем изображение в серых тонах. Пиксел принимает

какой-либо оттенок серого цвета, когда красная, зеленая и синяя его

составляющие равны, т.е. в нашем случае такой элемент матрицы

будет иметь вид





k

ij

k

ij

k

ij



 ,

где 0 ≤ k

ij

≤ 255 — целое число.

Для этого каждый элемент матрицы V преобразуем следующим

образом. Находим новую составляющую k

ij

, которая заменит старые

r

ij

, g

ij

, b

ij

, по формуле

k

ij

= (0, 33r

ij

+ 0, 56g

ij

+ 0, 11b

ij

) ,

и подставляем ее на места трех составляющих в этом элементе мат-

рицы

a

ij

=





k

ij

k

ij

k

ij



 .

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

котором серый цвет – это синий, красный и зеленый в соотношении

11%, 33% и 56%, соответственно. Далее для удобства будем считать,

что элементами нашей матрицы являются не вектора a

ij

, а целые

числа k

ij

.

281

Теперь делаем изображение только в черном и белом цвете. Для

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

p =

w−1

j=0

h−1

i=0

k

ij

wh

.

Теперь все элементы матрицы, яркость k

ij

которых меньше порога

(средней яркости p), делаем черными, остальные — белыми, то есть

k

ij

=

0,

если k

ij

< p

255, если k

ij

≥ p

,

где i = 0, h − 1, j = 0, w − 1.

Использование средней яркости в качестве порога позволяет

убрать лишний шум на изображении, в то же время, не теряя нуж-

ной информации.

Перевод изображения в черные и белые полосы. Для даль-

нейшей работы следует убрать белые поля с левой и с правой сторон

изображения (рис.1).

Рис. 1. Удаление белых полей с

краев изображения

Алгоритм

этот

следующий.

Просто перебираем элементы мат-

рицы, начиная с первого, идем вер-

тикально вниз, если не находим

черный пиксел до конца столб-

ца, то удаляем этот столбец, и

так далее. Когда находим черный

пиксел, переходим к последнему

столбцу и там делаем то же самое.

Разбиваем

изображение

на

столбики

одинаковой

ширины

(рис. 2). Ширину можно задать

любую, желательно не меньше 20

пикселей. Далее будем работать с

каждым столбиком отдельно. Для

чего это делается? Алгоритм ис-

пользует усреднение яркости по-

строчно, а из-за этого при работе

сразу со всем изображением могут

282

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

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

конец абзаца. Если будем работать со всем изображением, то алго-

ритм может пропустить неполные строки. Еще бывает, например,

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

изображение на столбики, можно почти исключить помехи при на-

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

нии яркостей.

Рис. 2. Разбиение

изображения на столбики

Таким образом наша матрица яркостей

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

ты, что и начальная, и одинаковой меж-

ду собой ширины. Рассмотрим одну из та-

ких подматриц. Так как далее будем ра-

ботать только с подматрицей (далее мат-

рица), обозначим ее тоже через V . Ее вы-

сота останется равной h, а ширину обозна-

чим опять же через w. В этой матрице для

каждой строки считаем среднюю яркость

s

i

=

w−1

j=0

k

ij

w

.

Далее в каждой строке присваиваем

всем элементам значение средней яркости,

т.е. k

ij

= s

i

, i = 0, h − 1, j = 0, w − 1.

Теперь эту матрицу разбиваем на квад-

ратные подматрицы размерности w × w и

к каждой квадратной подматрице приме-

няем метод преобразования в черные и бе-

лые цвета, описанный выше. Это проделывается в каждом квадрате

отдельно, так как в методе разбиения на черно–белое можно найти

среднюю яркость и опираться в разделении на нее. Если это делать

во всем столбике (матрице) сразу, то наличие в нем областей с не

текстом (рисунки, графики и т.п.) может привести к дефектам строк

текста.

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

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

щины. Очевидно, в областях изображения, где был текст, черные

283

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

вертикали будет наблюдаться периодичность. В других областях пе-

риодичности не будет с большой вероятностью.

Для более точного определения границ текста можно будет ме-

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

тот же алгоритм несколько раз.

Нахождение областей с текстом. Опять работаем отдельно

с каждым столбиком. Считаем количество черных полос с одинако-

вой толщиной и записываем их в массив. Визуально же это можно

представить в виде графика, где на оси x располагаются толщины,

начиная с единицы; на оси y — количество полосок данной толщины

(рис. 3). Таким образом, каждый столбец на графике соответствует

Рис. 3. График количества полос в зависимости от толщины

определенной толщине полосок, и высота его соответствует количе-

ству полосок данной толщины. Применяя этот метод к изображени-

ям, содержащим текст, выясняется, что на графике появляется ярко

выраженная мода (максимум по оси y). Она соответствует толщине

полос, которые являются строками текста. Как ищем моду? Ведь

строки текста одинакового шрифта после проведения выше описан-

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

связано с наличием заглавных букв и букв "б", "р", "у", "ф", кото-

рые "вылезают" над строкой или под ней. Как правило, толщина

не будет отличаться более чем на 1/10 от средней высоты строки

текста. В связи с этим, предлагается искать моду по формуле:

x

∗

= max

x

x+z

x−z

y,

284

где y — это количество полос толщиной x.

Параметр z предлагается взять следующий: z =

x

10

. Таким об-

разом, мода может быть не обязательно максимальным числом.

Далее, чтобы определить местонахождение текста на изображе-

нии, можно сделать следующее. Ищем в столбике (матрице) место-

нахождение полос с толщиной, равной x

∗

±

x

∗

10

. Сравниваем рассто-

яния между этими полосами: если они получаются близкими друг к

другу (в смысле расстояния), значит можно считать область от пер-

вой такой полосы до последней областью с текстом. Если очередное

расстояние оказалось значительно больше предыдущих, значит, это

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

— это не важно).

Выводы. Таким образом, с помощью этого алгоритма можно

отделить участки изображения, содержащие текст, от участков, не

содержащих его. Для более точного нахождения границ текста мож-

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

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

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

текста.

Вышеописанный алгоритм подходит, если в изображении присут-

ствует только текст одного размера шрифта, т.е. можно найти только

строки с текстом с таким размером шрифта, которого больше всего

присутствует в изображении. Решением этой проблемы может быть

поиск не одной моды, а нескольких.

Литература

1. Дунаев А.А., Лобив И.В., Мехонцев Д.Ю. и др. Алгоритмы быст-

рого поиска фрагментов фотографических изображений // Со-

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

2002. С. 88–109.

2. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состоя-

ние проблемы распознавания. М.: Радио и связь, 1985. 160 с.

3. http://ocr.apmath.spbu.ru. Проект "Открытый код — распознава-

ние текстовых изображений".

285

Богдановский А.Е.

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

Семантический анализ текстов

на английском языке

Рекомендовано к публикации профессором Тузовым В.А.

Введение. Текст на естественном языке является записью алго-

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

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

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

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

либо текст на другом языке [1–4]. Предложение, как часть алгорит-

ма, является записью последовательных выполнимых действий по

созданию структуры, которая зависит от конкретной задачи.

Семантический анализ. Исходя из функционального подхо-

да, семантический анализ является псевдовыполнением функций,

результатом которого является текст на семантическом языке. Се-

мантический язык позволяет формализовать описание алгоритма,

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

выполнения этого алгоритма. При семантическом анализе определя-

ются формализованные значения слов – элементы будущей семанти-

ческой структуры.

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

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

шений действительности.

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

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

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

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

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

ми для множества объектов действительности, входящих в понятие.

Формальным аналогом понятия является предикат.

Значением слова является объект действительности или более уз-

кое понятие – подмножество объектов, входящих в понятие. Опре-

деление значения слова является процессом уточнения понятия. По-

этому слово представляет собой функцию, которая вычисляет по-

нятие. Результат вычисления функции определяется аргументами.

286

Значение слова определяется контекстом предложения, в котором

оно употреблено.

Возникает вопрос: сколько значений может быть у одного слова?

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

слова. Потенциально возможное число значений слова огромно. В

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

абстракции элементов, образующих предложение. При этом не стоит

уменьшать влияние грамматической формы слова на его значение.

Значение слова также может зависеть от внешних обстоятельств

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

ключительно семантическое значение, отделенное от прагматики.

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

туру, отражающую независимую семантику предложения. Поэтому

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

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

ствующего семантики предложения. Для большинства случаев до-

статочно вычислить значение слова для класса слов, что является

естественным для сегодняшней лингвистической традиции.

центр острова;

центр города;

центр страны.

В данных примерах слову центр соответствуют один и тот же

предикат. Будет вычислено одно и то же семантическое значение.

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

ние слова, которое является аргументом. А оно, в свою очередь, тоже

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

сивным.

Семантика лексем описывается предикатом, составленным из ба-

зисных понятий и базисных семантических функций, которые опи-

сывают связь между понятиями.

ЦЕНТРОБАНК

Rel(БАНК(Z1),ЦЕНТР),

где БАНК и ЦЕНТР – базисные понятия, Rel(X, Y ) – базисная функ-

ция, которую можно перевести как "БАНК имеет какое-то отноше-

ние к ЦЕНТРу ".

Заменяя переменную Z1 на определенный аргумент, можно уточ-

нить значение слова ЦЕНТРОБАНК :

ЦЕНТРОБАНК РОССИИ Rel(БАНК(Род(РОССИЯ)), ЦЕНТР).

Все базисные понятия лексемы образуют иерархическую систему

семантических классов:

287

МАТЕРИЯ

$12

ПОСЕЛЕНИЕ $123

ГОРОД

$12314

БАНК

$123410

ЦЕНТРОБАНК $12341000

Базисные функции также представлены иерархической системой

от наиболее абстрактных к более конкретным. Базисные понятия

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

нению с базисными функциями.

В ходе семантического анализа всегда одно слово выступает в

роли функции, а другое – в роли его аргумента. Результатом ана-

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

семантического анализа является вычисление грамматического типа

слова-аргумента и выбор лексемы-функции, соответствующей аргу-

менту. Например, в выражении центр города родительный падеж

существительного ГОРОД является грамматическим типом @Род

слова ГОРОД. @Род(ГОРОД$12314)

Поэтому, чтобы анализатор использовал лексему ГОРОД в ка-

честве аргумента функции, в функцию ЦЕНТР$12/05(Z1) вносится

информация о грамматических типах.

ЦЕНТР$12/05($123 !Род)

Это означает, что в качестве аргумента функции может быть лю-

бая лексема из класса ПОСЕЛЕНИЕ $123 с грамматическим типом

@Род.

Грамматический тип вырабатывается также и при взаимодей-

ствии существительного с предлогом. Например, выражение в центр

города вырабатывает тип @Куда предлога В, который может взаи-

модействовать с лексемой ПОЕХАТЬ:

Куда(В(Вин(ЦЕНТР$12/05(Род(ГОРОД$12314)))))

ПОЕХАТЬ P erf Incep_M ov(НЕЧТО$1 ∼!Куда).

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

тельного. Семантическая формула выражения Исторический центр

города выглядит следующим образом:

Им(ЦЕНТР(*КАКОЙ (Им(ИСТОРИЧЕСКИЙ)),Род(ГОРОД))).

Анализатор автоматически использует прилагательное ИСТО-

РИЧЕСКИЙ в качестве аргумента существительного ЦЕНТР, вы-

рабатывая при этом связь типа *@КАКОЙ. Знак * указывает, что

это синтаксическая связь. Для образования синтаксических связей

288

функция не имеет явно описанных аргументов. Так же в описании

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

тических связей. Например, для образования связей на основе грам-

матического типа @Когда @Где.

Так, при анализе предложения Оружие опасно использовать в

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

фразу в центре города, которая вырабатывает тип @Где. В описании

лексемы ОПАСНО нет аргумента типа @Где:

Oper00(Z1 :!Инфин (Z2 :!Дат),ОПАСНОСТЬ$1301222(Z3 :!Дат

\!Для)).

Но образуется связь с аргументом @Где(В ЦЕНТРЕ ГОРОДА):

Oper00(Инфин(ИСПОЛЬЗОВАТЬ),ОПАСНОСТЬ(),Где(В ЦЕН-

ТРЕ ГОРОДА)).

Пропущенные аргументы образуют стандартные синтаксические

связи и семантические связи места и времени (каждое событие про-

исходит в определенном месте и времени).

Процесс построения семантической формулы английского пред-

ложения при наличии семантического представления лексем англий-

ских слов и соответствующего алгоритма образования синтаксиче-

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

цесса построения семантической формулы русского предложения.

Вычисление значения английского слова. Английскому сло-

ву centre соответствует несколько значений.

Hotel Carlton is in the centre of Prague.

She is currently working at the Centre of Astrobiology in Madrid.

He’s always at the centre of attention.

Принцип описания лексем в английском семантическом словаре

не отличаются от описания лексем русских слов.

CENTRE $12/05(ПОСЕЛЕНИЕ$123 ∼!Of ) //середина

CENTRE $1234(НЕЧТО$1 !Of ) //учреждение

CENTRE $15112(P erf Caus(#, IncepLoc(СОБЫТИЕ$11 ∼!Of )))

При семантическом анализе выражения the hotel located in the

centre of the town предлог of со словом T OW N $12314 выраба-

тывает грамматический тип @Of . Аргумент T OW N $12314 ∼ @Of

позволяет вычислить лексему CEN T RE$12/05() слова centre, соот-

ветствующую семантики выражения the centre of the town. Семанти-

ка выражения the centre of the town будет представлена формулой

CEN T RE$12/05(OF (T OW N $12314)). Полученная формула высту-

289

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

вырабатываемого предлогом in. Аргумент CEN T RE$12/05 позво-

ляет предлогу in выработать грамматический тип @Где для слова

centre. Семантическая формула, соответствующая данному выраже-

нию, имеет вид:

HOTEL(LOCATE(@Где IN(CENTRE$12/05(@Of OF(TOWN$12314))))).

Семантический анализ выражения at the centre of events позво-

ляет вычислить значение слова centre как лексему

CEN T RE$15112(P erf Caus(#, IncepLoc($11 ∼!Of )))

и выработать предлогу at грамматический тип @At. Семантическая

формула имеет вид: @AtAT (CEN T RE$15112(@Of OF (EV EN T $11))).

Семантический анализ выражения a party at the leisure centre

(праздник в центре досуга) вычисляет лексему CEN T RE$1234() и

предлог at вырабатывает тип @Где:

@Где AT (CEN T RE$1234(LEISU RE$15308)).

Семантический анализ английских текстов. Для построе-

ния семантической формулы английского предложения можно ис-

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

дет "понимать" английские грамматические типы, синтаксические

и семантические связи. Поэтому для организации перевода с одного

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

семантические и синтаксические). Базисные понятия и базисные се-

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

Они не нуждаются в переводе.

Перевод лексем. Главное преобразование семантических функ-

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

соответствующие "традиции" употребления (синтагматике) и грам-

матическим типам английского языка.

Рассмотрим описание лексем, соответствующих слову FALL.

The apple fell from the tree; we fell on our knees before her; to fall

from a train onto the line; to fall flat on the ground; to fall with a plump.

УПАСТЬ N%∼ПАДЕНИЕ$15428(СУБЪЕКТ:!Им,

ОТКУДА:НЕЧТО$1∼!from, КУДА:НЕЧТО$1∼!Куда\!on)

Some painful moments may fall to her lot; the hardest work fell to

her share; it fell to me to break the news to her.

ВЫПАДАТЬ N%∼СУДЬБА$112(ДОЛЯ$12/013141∼!to,

КОМУ:!to, !Инфин)

A child’s first teeth fall; his hair is falling; snow fell.

290

ВЫПАДАТЬ N%∼ВЫПАДЕНИЕ$15428(СНЕГ$122156\

ЗУБ$104113\ВОЛОС$10412∼!Им, НЕЧТО$1∼!Откуда)

ПОПАДАТЬ N%∼МЕСТОНАХОЖДЕНИЕ$12/2(!Им,

ЗАПАДНЯ$121312\РУКА$1043∼!into)

Rivers that fall into the sea.

ВПАДАТЬ N%∼ВПАДЕНИЕ$154201(РЕКА$122426∼!Им,

МОРЕ$12101∼!Куда)

To fall into disgrace; to fall into a reverie; to fall into rage.

ВПАДАТЬ N%∼ПСИХИКА$13(ЧЕЛОВЕК$1241∼!Им,

ПСИХИКА$13∼!Куда)

The wind fell; the flames rose and fell; here his voice fell.

ЗАТИХАТЬ N%∼ТИХИЙ$12/00601(ЗВУК$12/006\ВЕТЕР$12211

\ПЛАМЯ$12/01312∼!Им)

ПАДАТЬ N%∼ОСВЕЩЕНИЕ$12/007(СВЕТ$12/007∼!Им,

НЕЧТО$1∼!Куда\!on)

ПОПАДАТЬ N%∼ЗАВИСИМОСТЬ$131263(!Им,

ЗАВИСИМОСТЬ$1126∼!under)

ПРИХОДИТЬСЯ N%∼ВРЕМЯ$160(СОБЫТИЕ$11\

ДЕЙСТВИЕ$15∼!Им, СОБЫТИЕ$11\ВРЕМЯ$16∼!on)

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

ции функций, отражающих семантику конкретного предложения.

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

ством семантической однозначности.

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

точное семантическое значение слов, образующих предложение. Точ-

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

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

чение.

Вычисление семантико-грамматических типов. Значение

слова в предложении во многом зависит от его грамматической фор-

мы. Семантико-грамматический тип (СГТ) слова отражает принад-

лежность слова к семантическому классу и грамматическую форму.

Например, в выражении the centre of the town СГТ слова town опре-

деляется как $12314 ∼!Of (словосочетание с предлогом of ).

В английском языке СГТ слова определяется его предложной

формой. Семантика падежной формы может быть свободной и за-

висимой от синтаксиса. Все зависимые падежные формы описаны в

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

291

ные формы способны вырабатывать свой обобщенный СГТ. К обоб-

щенному грамматическому типу относятся такие типы, как @Где,

@Куда, @Откуда, @Когда, @КакДолго. При семантическом анализе

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

лексем.

Покажем зависимость СГТ @Когда от предлога и класса.

AT

ВОЗРАСТ$12411/07

at the age of seventy-six.

AT

ВРЕМЯ$1613

I miss playing football at dinner time; at 3.00.

IN

ВОЙНА$153032

in the Yemeni civil war.

IN

ОТСУТСТВИЕ$11012 in his absence.

IN

ВРЕМЯ$16

in January; in the beginning; once in ten years.

IN

ПОГОДА$1221

to go out in the rain; in good weather.

ON

ВОСКРЕСЕНЬЕ$1602 on Sunday.

СГТ в зависимости от английской падежной формы, которая

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

ную форму для данного семантического класса.

@Где

at the university

в университете

!at =!вПред

at/on the equator на экваторе

!at/on =!наПред

at/in a school

в школе

!at/in =!вПред

at the top

на вершине

!at =!наПред

in the town

в городе

!in =!вПред

in the list

в списке

!in =!вПред

on the Internet

в Интернет

!on =!вПред

on the floor

на полу

!on =!наПред

near the equator

у экватора

!near =!уРод

near the top

у вершины

!near =!уРод

Перевод на английский язык несвободных СГТ зависит от семан-

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

этим СГТ.

LOOK$10001(НЕЧТО$1∼!At)

GOGGLE$10001(!At)

STARE$1/28(НЕЧТО$1∼!At)

LAUGH$13124(НЕЧТО$1∼!At)

MOCK$13124(НЕЧТО$1∼!At)

СМОТРЕТЬ$10001(НЕЧТО$1∼!Куда)

ТАРАЩИТЬ$10001(!наВин)

292

УСТАВИТЬСЯ$1/28(НЕЧТО$1∼!Куда\!наВин)

СМЕЯТЬСЯ$13124(НЕЧТО$1∼!Над)

НАСМЕХАТЬСЯ$13124(НЕЧТО$1∼!Над)

Так, в классе $10001@At соответствует @Куда\@наВин. В классе

$13124@At – @Над.

Использование русского анализатора для английских текстов

невозможно без вычисления СГТ грамматических конструкций. На-

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

ления определений и определяемого слова. Так, выражению fashion

centre соответствует русское центр моды. Но в обоих случаях вычис-

ляется одинаковый грамматический тип @Род слова мода/fashion,

так как в роли определения слова centre выступает существительное

fashion.

Важно, что в конструкции to made him cough слову cough будет

соответствовать СГТ @Инфин, а не @Вин, как в to hear him cough.

Заключение. В каждом языке используются свои синтаксиче-

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

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

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

на семантическом описании лексем и вычислении семантико-грамма-

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

точном семантическом словаре может удовлетворять условиям дву-

стороннего перевода с одного естественного языка на другой.

Литература

1. Апресян Ю.Д. Избранные труды. Т. 1. Лексическая семантика.

Синонимические средства языка. М.: "Языки русской культуры",

Изд-во "Восточная литература" РАН, 1995. 442 с.

2. Золотова Г. А. Синтаксический словарь: Репертуар элементарных

единиц русского синтаксиса. М.: Эдиториал УРСС, 2001. 440 с.

3. Падучева Е.В. Динамические модели в семантике лексики. М.:

Языки славянской культуры, 2004. 608 с.

4. Тузов В. А. Компьютерная семантика русского языка. СПб.: Изд-

во СПбГУ, 2004. 400с.

293

Братчиков И.Л., Осолодкин А.С.

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

Специальные средства для разработки

Web-приложений

В настоящее время современные Web-приложения играют очень

большую роль не только в Интернете, но также и в локальных и

корпоративных сетях. Поэтому проблема быстрой и эффективной

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

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

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

только профессиональные системные программисты, но и широкий

круг пользователей сетей различного назначения. В основу разрабо-

танного продукта легли такие технологии как AJAX (Asynchronous

JavaScript + XML) и основные принципы Web 2.0.

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

го создания Web-приложений — OWADE (online Web application

developement environment). Основная идея разработки заключалась

в стремлении освободить программиста от программирования ру-

тинных операций, таких как наполнение интерфейса данными, со-

хранение изменений и построение интерактивных элементов управ-

ления (контролов). Всю эту работу за него должна делать система

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

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

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

Глобально система состоит из двух частей, реализующих два язы-

ка пользователей: язык разметки страницы (WIML – Web interface

markup language) и язык разметки базы данных (DBML – data base

markup language). Оба языка основаны на XML, что предоставляет

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

Язык разметки Web-интерфейсов представляет собой набор «ком-

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

ные и расширенные (интерактивные) элементы управления. Ко вто-

рому – стандартные элементы разметки: box (бокс), vbox (верти-

кальный бокс), hbox (горизонтальный бокс), а также элементы grid

294

(сетка), spacer (пустой элемент), label (метка) и прочие. Примера-

ми первого типа являются объекты: listbox (список), tree (дерево),

tabbox (панель кнопок), calendar (календарь) и еще около 20-ти раз-

личных элементов. У каждого компонента есть набор стандартных

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

позволяют настроить функциональность и внешний вид контролов.

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

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

атрибут class. Значением будет имя CSS класса, который должен

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

/>

tabwidth="300" id="capt_1"/>

datasource="test_Campaigns" datanavigator="cmpNav"

type="checkbox" height="400">

295

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

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