Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений
Показано, что сортировка может служить единой основой для автоматической идентификации нулей и экстремумов
 произвольной функции одной и более переменных в произвольно фиксированной части области определения. Нули полинома
 вычисляются с учетом кратности, включая случай характеристич...
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/1585 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений / Я.Е. Ромм, И.В. Заика, И.А. Тюшнякова // Проблеми програмування. — 2006. — N 2-3. — С. 708-717. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859991289509969920 |
|---|---|
| author | Ромм, Я.Е. Заика, И.В. Тюшнякова, И.А. |
| author_facet | Ромм, Я.Е. Заика, И.В. Тюшнякова, И.А. |
| citation_txt | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений / Я.Е. Ромм, И.В. Заика, И.А. Тюшнякова // Проблеми програмування. — 2006. — N 2-3. — С. 708-717. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| description | Показано, что сортировка может служить единой основой для автоматической идентификации нулей и экстремумов
произвольной функции одной и более переменных в произвольно фиксированной части области определения. Нули полинома
вычисляются с учетом кратности, включая случай характеристического полинома матрицы. Функция может задаваться
значениями на равномерной сетке. В частности, идентифицируются нули и экстремумы разностных решений обыкновенных
дифференциальных уравнений и уравнений в частных производных. Для оцифрованного изображения на плоскости как
дискретной функции двух переменных на сетке пиксельных элементов на этой основе строится вектор распознавания. Процесс
обработки использует лишь операции сравнения, что исключает накопление погрешности, влечет высокую точность локализации
экстремумов и устойчивость идентификации изображений.
It is shown that sorting can form a unique basis for automatic identification of zeroes and extremums of any function of one and more
variables in any way fixed раrt of definitional domain. Polynomials` zeroes are calculated with consideration of multiplicity, including a
case of a characteristic polynomial of a matrix. Function can be set by values on a analytical grid. In particular, zeroes and extremums of
difference solutions of the ordinary differential equations and the equations in partial derivatives are identified. For digitized image on a
plane as discrete function of two variables on a pixel elements’ grid on this basis the recognition vector is under construction.
Manufacturing process uses only comparison operations, which excludes error accumulation and implyies split-hair accuracy of
localization of extremums and stability of images identification.
|
| first_indexed | 2025-12-07T16:32:05Z |
| format | Article |
| fulltext |
Прикладне програмне забезпечення
© K. Georgiev, E. Donev, 2006
ISSN 1727-4907. Проблеми програмування. 2006. №2-3. Спеціальний випуск 708
УДК 681.3
ИДЕНТИФИКАЦИЯ ЭКСТРЕМУМОВ ФУНКЦИЙ
НА ОСНОВЕ СОРТИРОВКИ С ПРИЛОЖЕНИЕМ К
ВЫЧИСЛИТЕЛЬНЫМ СХЕМАМ АЛГЕБРЫ,
АНАЛИЗА И РАСПОЗНАВАНИЮ ИЗОБРАЖЕНИЙ
Я.Е. Ромм, И.В. Заика, И.А. Тюшнякова
Таганрогский государственный педагогический институт
347936, Таганрог, ул. Инициативная, 48
тел.: (863)(44) 60 1753; факс: (863)(44) 60 5397, Romm@list.ru
Показано, что сортировка может служить единой основой для автоматической идентификации нулей и экстремумов
произвольной функции одной и более переменных в произвольно фиксированной части области определения. Нули полинома
вычисляются с учетом кратности, включая случай характеристического полинома матрицы. Функция может задаваться
значениями на равномерной сетке. В частности, идентифицируются нули и экстремумы разностных решений обыкновенных
дифференциальных уравнений и уравнений в частных производных. Для оцифрованного изображения на плоскости как
дискретной функции двух переменных на сетке пиксельных элементов на этой основе строится вектор распознавания. Процесс
обработки использует лишь операции сравнения, что исключает накопление погрешности, влечет высокую точность локализации
экстремумов и устойчивость идентификации изображений.
It is shown that sorting can form a unique basis for automatic identification of zeroes and extremums of any function of one and more
variables in any way fixed раrt of definitional domain. Polynomials` zeroes are calculated with consideration of multiplicity, including a
case of a characteristic polynomial of a matrix. Function can be set by values on a analytical grid. In particular, zeroes and extremums of
difference solutions of the ordinary differential equations and the equations in partial derivatives are identified. For digitized image on a
plane as discrete function of two variables on a pixel elements’ grid on this basis the recognition vector is under construction.
Manufacturing process uses only comparison operations, which excludes error accumulation and implyies split-hair accuracy of
localization of extremums and stability of images identification.
Постановка вопроса
Цель сообщения – показать применимость сортировки в качестве единой основы для автоматической
идентификации всех нулей и экстремумов произвольной алгебраической и трансцендентной функции одной и
более переменных в произвольно фиксированной части области определения. Функция, в частности, может
быть задана дискретно, например, последовательностью отсчетов, значениями на равномерной сетке. В
последнем случае ставится задача идентифицировать все нули и экстремумы разностных решений
обыкновенных дифференциальных уравнений и уравнений в частных производных. Оцифрованное
изображение на плоскости представляет собой разновидность дискретной функции двух переменных на
равномерной сетке с длиной шага, равной стороне пикселя. Для такого изображения требуется на
рассматриваемой основе построить идентифицирующий вектор признаков.
Схема автоматической идентификации всех экстремумов и нулей функции на основе
сортировки
Пусть вначале требуется локализовать и приближенно вычислить все минимумы действительной
функции одной действительной переменной )(xfy = на промежутке ],[ )()0( Nxx в области ее определения. На
равномерной сетке Nxxh N /)0()( −= , hxx l
l
+= )0( , N,...,1,0=l , считываются значения функции и
запоминаются как элементы массива )(][ 1−= ixfiс , Ni ,...,2,1= . Элементы этого массива сортируются. Для
простоты описания используется сортировка подсчетом в модификации из [1, 2]. Массив С из N элементов,
располагается горизонтально сверху и вертикально слева от матрицы сравнений (МС). Например, для массива
)8,2,5,3,1(=C МС примет вид
1 3 5 2 8
1 0 + + + +
3 – 0 + – +
5 – – 0 – +
2 – + + 0 +
8 – – – – 0
Чтобы произвести вставку в отсортированный массив j -го элемента входного массива, достаточно
подсчитать число нулей и плюсов в j -м столбце над диагональю, включая диагональный элемент, и сложить
это число с числом плюсов ниже диагонали. Сумма накапливается в счетчик по k , значение k становится
Прикладне програмне забезпечення
709
адресом вставки: ][:][1 jckc = , при этом запоминается входной индекс вставленного элемента jke =:][
(обратный адрес). На выходе сортировки ][1 kс и ][ke имеют равный номер k . Оценки сложности и
параллелизм обсуждаются в [1, 3], программа в примере описана далее в процедуре SORT.
В качестве сортировки можно использовать любую сортировку со свойствами адресности и обратной
адресности, например, быструю сортировку ( ( )NNOT 2log= ) на основе слияния по МС [4]. Последняя
используется на практике во всех описываемых далее алгоритмах [1–4, 5, 6] для ускорения работы компьютера.
К выходу процедуры сортировки подсоединяется условный оператор, локализующий после
выполнения сортировки все минимумы среди этих значений [1, 2], – k:=1; while k<= n do begin FOR l := 1 TO
k-1 do if abs(e[k]-e[k-l]) <= eps0/h then goto 22; xk:= x0+e[k]*h;
22: k:=k+1; end.
Здесь n – число узлов, совпадающее с числом сортируемых элементов; h – шаг сетки; 0eps –
константа, равная радиусу 0eps -окрестности текущего узла, радиус выбирается априори таким образом, чтобы
не превысить половины числа узлов, отсчитываемых вдоль оси между ближайшими друг к другу минимумами
функции )(xfy = . Оператор для текущего узла ][ ke находит каждый узел [ ] hkex *0 + , такой что значение
функции в этом узле не больше значений в остальных узлах 0eps -окрестности. Значение локализованной
абсциссы точки минимума [ ] hkexxk *0: += дает привязку к локализуемой точке минимума, она фиксируется и
выполняется спуск к наименьшему значению в окрестности локализованной точки. Он осуществляется с
помощью выбора наименьшего значения в сужаемой окрестности c фиксированным числом элементов в сетке,
пока не будет достигнута требуемая точность. Более детально смысл этого условия обсуждается в [4–6]. Там
достаточно детально описан его перенос на случай функций двух и трех переменных. Условие локализации
максимумов в рамках данного метода задается операторами k:=1; while k<= n do begin FOR l := 1 TO n-k do if
abs(e[k]-e[k+l]) <= eps0/h then goto 222; xk:= x0+e[k]*h; 222: k:=k+1; end.
Инвариантность метода относительно длинны промежутка достигается путем смещения базового
промежутка с числом узлов N на расстояние, равное его длинне. Во избежание ложных экстремумов
отсекаются обе границы текущего промежутка, проверка границ на экстремумы производится с помощью
сортировки. Эта сортировка локализует экстремумы по ранее описанной схеме для элементов массива,
образуемых значениями исследуемой функции слева от правой границы и справа от левой границы. В
результате достигается инвариантность схемы относительно размеров промежутка, а в общем случае, – области
поиска экстремумов. По построению схема инвариантна относительно вида функции, на которую не
накладывается математических ограничений. Функция, в частности, может быть задана таблично, при этом
спуск окажется излишним и локализация экстремумов равносильна его идентификации. При этом удается
достигнуть высокой точности идентификации экстремумов. Например, все минимумы функции ( )xy sin= на
[ ]30,30− в результате работы программы, листинг которой представлен в [3], примут значения:
значения аргументов
-2.67035375557E+0001
-2.04203522486E+0001
……………………..
2.98451302089E+0001
значения минимумов
-1.00000000000000E+0000
-1.00000000000000E+0000
…………………
-1.00000000000000E+0000
Для локализации и вычисления нулей функции достаточно на вход сортировки подать абсолютные
величины ее значений на равномерной сетке )(][ 1−= ixfiс , ni ,...,2,1= , и искать минимумы выше
описанным способом. Та же программа [3] локализует и вычислит, например, все нули полинома
321 PPPP ××= , где
)7()002.6()001.6()5()4()3()99.2()1(1 −−−−−−−−= xxxxxxxxP ,
)15()14()13()12()11()976.10()9()23.8(2 −−−−−−−−= xxxxxxxxP ,
)23()12345.22()21()098.20()19()18()17()16(3 −−−−−−−= xxxxxxxP
в виде
значения аргументов
1.00000000000000000E+0000
3.00000000000000000E+0000
……………………..
2.21234500000000000E+0001
2.30000000000000000E+0001
значения нулей
0.00000000000000E+0000
0.00000000000000E+0000
………………………
0.00000000000000E+0000
0.00000000000000E+0000
Следует отметить, что изложенная схема вычисления нулей полинома достраивается до схемы
вычисления его нулей с учетом кратности [4–6].
Прикладне програмне забезпечення
710
Предложенная схема идентифицирует все нули и экстремумы функций общего вида, включая транс-
цендентные.
Без принципиальных затруднений схема переносится на случай вычисления нулей и экстремумов
функций двух и более переменных [3–6].
Идентификация нулей и экстремумов разностных решений дифференциальных
уравнений
По данной схеме можно идентифицировать все экстремумы разностного решения системы
обыкновенных дифференциальных уравнений. Для простоты рассматривается задача Коши для одного
уравнения
),,( yxf
dx
dy = 00 )( yxy = .
На промежутке [ ]nxx ,0 вычисляется разностное приближение, для определенности выбран метод Эйлера:
hyxfyy iiii ),(1 +=+ , hixx i += 0 , ni ...,,1,0= ,
n
xx
h
n 0−
= .
Разностные значения принимаются за элементы массива
1][ −= iyiс , ni ...,,2,1= ,
который сортируется. Присоединение условия локализации минимумов (максимумов) к программе сортировки
влечет устойчивую идентификацию экстремумов приближенного решения рассматриваемой задачи.
Инвариантность схемы относительно длины промежутка достигается вышеописанным способом (с исполь-
зованием сортировки и повторной локализации на границах смещаемого промежутка).
Для случая системы дифференциальных уравнений схема применяется к каждому уравнению в
отдельности. Детальное описание и другие примеры на случай системы приводятся в [3–5]. Для идентификации
нулей достаточно на вход сортировки подать абсолютные величины разностных значений решения.
Идентификация всех нулей и экстремумов разностных решений уравнений в частных
производных
Описанная схема переносится на случай идентификации всех нулей и экстремумов разностных
решений уравнений в частных производных. Пусть, например, рассматривается задача о свободных колебаниях
струны:
2
2
2
2
2
x
u
a
t
u
∂
∂=
∂
∂
, (1)
где краевые и начальные условия заданы соответственно в виде
,0,00 == == lxx uu (2)
)(0 x
t
u
t ψ=
∂
∂
= , (3)
).(0 xu t φ== (4)
Пусть задача определена в области ),0(),0( Tl × , для которой строится равномерная прямоугольная
сетка:
,ihxi = ,/ nlh = ;,...,1,0 ni = ,τjt j = ,/ mT=τ mj ,...,1,0= .
Обозначив j
iu значения сеточной функции, приходим к разностной схеме
2
112
2
11 22
h
uuu
a
uuu j
i
j
i
j
i
j
i
j
i
j
i +−
+− +−
=
+−
τ
. Пусть
2
2
2~
h
ay
τ= , тогда
,~)~22(~
11
11 j
i
j
i
j
i
j
i
j
i uyuyuyuu +−
−+ +−++−= (5)
где 1,...,2,1 −= ni ; .1...,,2,1 −= mj Дополнив (5) значениями на нулевом слое
0,...,,0 0
,1
0
11
0
1
0
0 ==== −− nnn uuuu φφ
и значениями 0,00 == j
n
j uu на границе в соответствии с условиями (2), (4) и аппроксимируя производную в
(3) для подсчета 1
iu на первом слое, получаем явную формулу второго порядка точности для вычисления
Прикладне програмне забезпечення
711
недостающих значений на первом слое: )(~
2
1
)~1( 11
1
+− φ+φ+φ−+ϕτ= iiiii yyu , .1,...,2,1 −= ni Пусть каким-
либо способом осуществлен процесс вычислений (5) при фиксированных n и m (или h и τ ), т.е. получена
таблица значений j
iu – приближенный каркас решения )( , ji txu . Известно [7], что условие 1~ <y (или
a
h<τ )
обеспечивает устойчивость схемы и сходимость решения 0)( , →− ji
j
i txuu при 0,0 →τ→h в условиях (2) –
(4).
Как только сформирована таблица значений j
iu , она интерпретируется как дискретная функция двух
переменных ji tx , , которая стандартно поступает на вход метода, и для нее без принципиальных затруднений
идентифицируются все искомые нули и экстремумы. Более детально схема описывается непосредственно
далее, затем приводится программный пример.
Для нахождения минимумов полученной сеточной функции выполняется проход в направлении оси
tO вдоль i -го столбца прямоугольной сетки, во время которого находится минимальное по строкам значение
j
i
mj
i
uic
≤≤
=
=
1
const
min][ , этот минимум заносится на вход сортировки как i -й элемент сортируемого одномерного
массива. К выходу процедуры подсоединяется оператор локализации минимума. Оператор идентифицирует
каждый узел hke *][ , в проекции 0eps – окрестности которого на OX нет узлов, доставляющих значения
элементов, предшествующие ]][[ kec в отсортированном массиве.
Значение локализованной абсциссы точки минимума hkexk *][:= дает привязку к локализуемой точке
двумерного минимума, оно фиксируется и аналогичным образом локализуется ордината tk , в которой
идентифицируется минимум значения сеточной функции (5).
Пример 1. Пусть дано уравнение (1) при 009.0=a с краевыми и начальными условиями (2) – (4) вида:
.0),sin(,0,0 000 =
∂
∂=== ==== ttlxx t
U
xUUU
Требуется найти все локальные минимумы в окрестностях радиуса π=0eps разностного решения
данного волнового уравнения в области ),0(),0( Tl × , где 40,40 == Tl и 2200,1100 == mn . Минимумы
идентифицирует следующая программа (Object Pascal, Delphi):
PROGRAM extrem;
{$APPTYPE CONSOLE}
uses SysUtils;
LABEL 22,23;
Const eps0=pi; n=1100; m=2200; n00=2500; h=40/(n); tau=40/(m); a=0.009;
TYPE vect=ARRAY [0..n00] OF extended;
vect1=ARRAY [0..n00] OF longint;
type matr=array[0..m,0..m] of extended;
VAR i,j,k,k1,r,nn0,xk,tk : longint; c1,c: vect; e, e1: vect1; x0,min: extended; u: matr;
Procedure uuu(Var u:matr);
var i,j:longint; fi,psi:vect; x,yy:extended;
begin
yy:=sqr(a)*(sqr(tau) / sqr(h)); x0:=0; u[0,0]:=0;u[n,0]:=0;
for i:=1 to n-1 do begin x:=(x0+i*h); u[i,0]:=sin(x);end;
fi[0]:=0;fi[n]:=0;
for i:=1 to n-1 do begin x:=x0+i*h; psi[i]:=0; fi[i]:=sin(x);
u[i,1]:=tau*psi[i]+(1-yy)*fi[i]+0.5*yy*(fi[i-1]+fi[i+1]);end;
for j:=1 to m do begin u[0,j]:=0;u[n,j]:=0;end;
for i:=1 to n-1 do for j:=1 to m-1 do begin
u[i,j+1]:=-u[i,j-1]+yy*u[i-1,j]+(2-2*yy)*u[i,j]+yy*u[i+1,j]; end;end;
function func( var i,j:integer):extended;
begin func:= {abs}(u[i,j]); end;
PROCEDURE mint {maxt} (VAR i,nn0:integer;var min {max}:extended);
var j:integer;
BEGIN nn0:=m;j:=1; min{max}:=func(i,j); FOR j:=1 TO nn0 DO
IF min > func(i,j) {max< func(i,j)}THEN BEGIN min:=func(i,j) {max:=func(i,j)}; END; END;
procedure SORT (var nn0: integer; var c: vect; var e: vect1);
var i,j,k:integer;
begin
FOR j := 1 TO nn0 do begin k:=0;
Прикладне програмне забезпечення
712
FOR i := 1 TO j do
IF c[j] - c[i] >= 0 THEN k:=k+1;
FOR i := j+1 TO nn0 do
IF c[j] - c[i] > 0 THEN k:=k+1; c1[k]:=c[j]; e[k] := j; end; end;
BEGIN
nn0:=n; uuu(u);
FOR i:=1 TO nn0 DO BEGIN mint (i,nn0,min);c[i]:=min; END;
SORT ( nn0, c, e);
k:=1; WHILE k<= nn0 DO BEGIN
FOR r := 1 TO k-1 DO IF abs(e[k]-e[k-r]) <= eps0/h THEN GOTO 23;
xk:= e[K]; nn0:=m;
FOR j:=1 TO nn0 DO c[j]:=func(xk,j);
SORT ( nn0, c, e1);
k1:=1; WHILE k1<= nn0 DO BEGIN
FOR r := 1 TO k1-1 DO IF abs(e1[k1]-e1[k1-r]) <=eps0/h THEN GOTO 22;
tk:= e1[K1];
writeln (' ', xk,' '); writeln (' ', tk,' ', func(xk,tk)); writeln;
22: k1:=k1+1; END;
23: k:=k+1; END; writeln; readln;
END.
Результат работы программы:
216
2095 -1.01E+0000
216
699 -1.00E+0000
………………………………
562
2096 -1.01E+0000
562
699 -1.00E+0000
Для идентификации всех нулей достаточно в той же программе на вход метода подать ||),( j
iujif =
(достаточно снять комментарий в подпрограмме func). Получится:
1100
1 0.00E+0000
994
350 1.54E-0007
994
1746 7.37E-0006
………………………………..
257
445 1.98E-0006
816
1740 4.04E-0006
354
331 5.15E-0006
Для идентификации локальных максимумов в окрестностях того же радиуса производится замена
оператора локализации минимума на оператор локализации максимума и замена процедуры поиска минимума
mint новой процедурой поиска максимума maxt:
PROCEDURE maxt (VAR i,nn0:integer;var max:extended);var j:integer;
begin nn0:=m; j:=1; max:=func(i,j); FOR j:=1 TO nn0 DO IF max< func(i,j) then begin max:=func(i,j); end;
end;
Видоизмененная таким образом программа extrem идентифицирует все максимумы разностного
решения рассматриваемого уравнения.
Результаты работы программы:
2200
2200 0.00E+0000
994
699 1.00E+0000
994
2096 1.01E+0000
………………………………
475
2095 1.01E+0000
648
699 1.00E+0000
648
2095 1.01E+0000
В общем случае, предложенная схема идентифицирует все локальные и глобальные экстремумы
разностных решений уравнений в частных производных второго порядка на прямоугольной сетке произвольной
размерности. Схема может быть перенесена на уравнения более высокого порядка.
Локализация и вычисление собственных значений матриц на основе сортировки
Собственные значения матрицы
=
nnnn
n
n
aaa
aaa
aaa
A
...
............
...
...
21
22221
11211
Прикладне програмне забезпечення
713
вычисляются по описанной схеме как нули характеристического полинома
)...()1(|| 1
1 n
nnn ppEA +++−=− −λλλ . Особенности этой схемы для случая комплексных нулей
полиномов детально описаны в [1-4], полный листинг программ с учетом случая кратных нулей дан в [6]. Его
коэффициенты предварительно определяются по методу Леверье [8]: решается система уравнений Ньютона:
kkkkk kppSpSpSS −=++++ −−− 112211 ... , где
______
..1 nk = , )( k
k ASpS = – след матрицы kA . Полином
)...()1()( 1
1 n
nnn
n ppP +++−= −λλλ ( Iyx +=λ ) задан своими коэффициентами, для формирования функции
),( yxf , которая подается на вход метода, необходимо выделить действительную и мнимую части
рассматриваемого полинома. Для этого используются специальные процедуры, реализуюшие комплексную
арифметику. В результате 22 )))((Im()))((Re(),( zPzPyxf nn += . В случае отсутствия процедур комплексной
арифметики для формирования входной функции можно использовать бином Ньютона степени ll Iyxz )( ⋅+= ,
коэффициенты бинома определяются по треугольнику Паскаля и приводятся подобные при действительной и
мнимой части [2, 4].
Если коэффициенты характеристического полинома вычислены достаточно точно, то предложенный
метод вычисления собственных значений матриц оказывается устойчивым в виду фактически верного (с
точностью до формата представления данных в языке Object Pascal) вычисления нулей полиномов.
Схему нахождения нулей характеристического полинома с учетом кратности можно дополнить до построения
полной нормальной жордановой формы матрицы [6].
Приложение метода к распознаванию плоских изображений
Описанная схема вычисления собственных значений матриц применяется для распознавания как
двуцветных, так и цветных плоских многосвязных изображений в каноническом расположении в декартовых
координатах. Излагаемый метод, в отличие от известных [9], исключает этап выделения ключевых признаков,
этап предобработки изображения включает в себя лишь укрупнение исходной матрицы (масштабирование),
после чего в качестве механизма классификации выступает схема вычисления собственных значений
оцифрованной матрицы пикселей, описанная выше.
Первоначально будем рассматривать входные изображения небольшого размера: 16х16, 32х32 или 64х64
пиксела. Модификация метода для изображений большего размера излагается в дальнейшем.
Распознавание двуцветного изображения. Рассмотрим класс изображений, каждый пиксел который
после оцифровки может принимать значение 0 или 1, т. е. изображение является черно-белым или любым
двуцветным. В данном классе изображений одним из типов объектов, распознавание которых представляет
практическую ценность, являются, в частности, лингвистические символы. Их распознавание может
использоваться для ускорения ввода в компьютер рукописного текста, иероглифов и любых символов. Суть
метода заключается в следующем.
Для оцифрованной квадратной матрицы пикселей плоского двухцветного изображения вычисляется
набор собственных значений с учетом кратности. В случае прямоугольного изображения матрица
достраивается до квадратной путем дописывания нулевых строк и столбцов. Вектор распознавания состоит из
диагональных клеток жордановой формы матрицы. Это влечет возможность квадратичного сжатия
изображения и определяет выбор эталонного вектора для его идентификации. Численный эксперимент показал,
что в качестве вектора распознавания на практике достаточно использовать вектор собственных значений
матрицы с учетом кратности, без построения клеток Жордана. На этом основании далее не учитываются
элементарные делители и инвариантные множители оцифрованной матрицы изображения.
Оговорок требует представление входной матрицы. Клетки изображения целесообразно укрупнить для
идентификации существенных деталей (рис. 1).
Клетка полагается закрашенной при условии, что число закрашенных в ней пикселей превосходит
некоторое априори заданное значение. Такой вариант укрупнения позволяет избавиться от случайных помех, но
не дает возможность однозначно идентифицировать конкретный фрагмент изображения с учетом каждого
пиксела. Возможен другой вариант укрупнения, учитывающий все детали изображения, он описан далее для
цветного изображения.
Укрупненная матрица B , нормируется для уменьшения значений следов ее степеней. Целесообразно
применить умножение траспонированной матрицы на исходную матрицу: CBBT =× . Это ускорит работу
программы, так как результатом произведения является положительно-определенная матрица C , имеющая
только действительные неотрицательные собственные значения [8], вследствие чего нахождение нулей
характеристического полинома матрицы C производится на основе программы вычисления действительных
нулей полиномов. Вектор распознавания строится из собственных значений матрицы C , упорядоченных по
неубыванию.
Прикладне програмне забезпечення
714
Видоизменение вектора распознавания, состоящего из собственных значений матрицы C , может быть
основано на взаимно однозначном соответствии нулей характеристического полинома его коэффициентам.
Коэффициенты, в свою очередь, однозначно определяются следами всех степеней матрицы в силу
единственности решений треугольной системы уравнений Ньютона. Отсюда вектор распознавания может
строиться по числовым значениям следов степеней этих матриц.
Таким образом, имеется возможность построения трех типов вектора распознавания (набор
собственных значений, набор коэффициентов характеристического полинома, набор следов степеней матриц) и
они эквивалентны. С точки зрения быстродействия, наиболее целесообразно использовать набор следов n
степеней исходной матрицы. Например, вектор распознавания, состоящий из следов, для символа,
изображенного на рис. 1.
(0.5, 0.12037037037037, 0.0366512345679012, 0.0118312757201646, 0.00387469516841945, 0.00127375344523193,
0.000419162717792286, 0.00013797674134256).
Длительность работы в случае матриц большого порядка может быть компенсирована параллелизмом метода,
основанного на алгоритме Ксанки [10] параллельного вычисления n степеней матрицы.
На основе описанного метода возможно распознавание произвольного геометрического места точек, в
том числе сочетаний букв и слов целиком. Как в данном, так и в ранее описанном классе задач возникает
следующая трудность. Так как подобные матрицы имеют одну и ту же жорданову форму [8], а, следовательно,
одинаковый набор собственных значений и следов степеней матриц, то различные изображения могут быть
идентифицированы с помощью описанной схемы как тождественные. Например, изображение сочетания букв
«ОС» и «СО» размерностью 32 х 32 пикселя после укрупнения представляется подобными матрицами (рис. 2).
Векторы распознавания для изображений совпадают: (0.96, 0.4096, 0.18432, 0.08388608, 0.0383778816,
0.017632854016, 0.0081335943168, 0.0037658273251328).
Идентификация изображений, представимых подобными матрицами. Для однозначной иденти-
фикации изображений, матрицы которых подобны, предлагается следующая модификация схемы
распознавания.
В дополнении к алгебраическому методу применяется вспомогательная схема идентификации
экстремумов (например, максимумов) дискретной функции двух переменных. Задается промежуток с
границами ],1[ np ],1[ np× (где np – размерность укрупненной матрицы B ) и строится равномерная
прямоугольная сетка с шагом 1=h . Функция задается в узлах этой сетки, причем jiBjif =),( . Максимумы
),( yxf находятся по вышеописанной (для уравнений в частных производных) схеме нахождения экстремумов
дискретно заданной функции двух переменных (с той оговоркой, что вычислять значения входной сеточной
функции не требуется).
а б
Рис. 1. Матрица пикселей символа «начало»: а – исходная; б – укрупненная
Прикладне програмне забезпечення
715
Следует принять во внимание, что схема идентификации экстремумов разностного решения уравнения
в частных производных, по существу, не отличается от рассматриваемой схемы идентификации экстремумов
плоского изображения. Более того, можно было бы ограничиться только этой схемой распознавания данных
изображений. Однако при этом идентифицирующие векторы имели бы различное число компонент, что
повлекло бы трудности при сравнении с эталонами. Напротив, кроме равенства числа компонент
идентифицирующих векторов, предложенная ранее схема идентификации на основе собственных значений
входной матрицы изображения с очевидностью обладает свойством сжатия 2N исходных элементов до
значения )(NO .
В результате вектор распознавания в общем случае строится как набор следов всех n степеней матрицы
и он дополняется отсортированным набором длин проекций радиус-векторов локализованных максимумов
функции ),( yxf , описывающей матрицу изображения. В частности, изображениям сочетания букв «ОС» и
«СО» соответствует различное число максимумов, что указывает на их различие при совпадении следов
степеней матрицы. Окрестность локализации при этом выбрана в виде 40 divnpeps = .
В качестве набора дополнительных идентификаторов изображения не обязательно использовать
длинны проекций радиус-векторов максимумов функции ),( yxf , в их роли могут выступать индексы
положения этих максимумов внутри матрицы, можно также рассматривать подстановки из индексов [1].
Следует отметить, что имеет место сходимость описанного метода, основанная на следующих
соображениях. При итеративном сужении окрестности локализации 0eps найдется определенная окрестность
радиуса 0eps , начиная с которой поиск экстремумов будет давать один и тот же результат. Это обуславли-
вается тем, что 0eps не превышает половины расстояния между проекциями соседних экстремумов.
Поскольку на вход метода может поступать любое геометрическое место точек, то описанный метод
применим для распознавания отпечатков пальцев. В отличие от известных [1], он не требует высокого качества
исходного изображения и выделения особых точек, минимально использует математический аппарат. С
помощью данного метода возможно гарантированное распознавание отпечатков пальцев в каноническом
расположении, т. е. без учета смещения и поворота пальца, изменения давления, изменения качества
поверхности кожи и т.д. Следует отметить, что все известные методы распознавания отпечатков пальцев также
зависят от этих факторов, т.е. качество изображения папиллярного узора пальца является одним из основных
критериев, от которого зависит распознавание и в конечном итоге идентификация человека. Хранение вектора
распознавания занимает небольшой объем памяти, поэтому для идентификации конкретного человека
возможно сравнение его отпечатка с набором нескольких эталонных, снятых под разными углами и с
различным давлением.
Для применения данного метода изображение отпечатка пальца, введенное в память какого-либо
считывающего устройства, сохраняется в виде цифрового эталона, размер которого совпадает с количеством
элементов вектора распознавания (дополненного при необходимости набором соответственных максимумов).
Поскольку эталоны отпечатков хранятся в памяти в виде цифровых векторов, это полностью исключает
возможность восстановления из них реального изображения отпечатков. К тому же фактическое изображение
отпечатка пальца при контакте со считывателем необязательно сохранять и запоминать, что немаловажно для
инфомационной безопасности.
Распознавание цветного изображения. Метод распознавания двуцветного изображения, вышеопи-
санный, можно распространить на цветное изображение. Рассмотрим класс изображений, состоящих из
ограниченного количества цветов, например восьмицветные изображения.
Оцифровка матрицы пикселей происходит следующим образом: каждому пикселю изображения
],[ jiam присваивается в зависимости от его окраски определенное число от 0 до 7. Один из возможных
вариантов укрупнения ячеек входной матрицы заключается в следующем. Будем подсчитывать сумму
а б
Рис. 2. Укрупненная матрица пикселей изображения: а – OC; б – CO
Прикладне програмне забезпечення
716
произведений элементов текущей ячейки (слева направо сверху вниз) и степеней
2
8...,8,8 10 hm ( hm –
числовой параметр, кратный n, и определяющий размер укрупнения ячеек матрицы). Таким образом, часть
исходного изображения до укрупнения, т.е. конкретная ячейка матрицы AM , представляется числом в
восьмерочной системе счисления; после укрупнения значение элемента матрицы B , соответствующее данной
ячейке, представляется тем же числом в десятичной системе счисления. Для фрагмента исходной матрицы и
4=hm получаем
=
............
.............
......
......
.......
...
............
...
...
...
...
2221
1211
5554535251
45
35
25
15
44434241
34333231
24232221
14131211
bb
bb
amamamamam
am
am
am
am
amamamam
amamamam
amamamam
amamamam
,
16
44
5
22
4
21
3
14
2
13
1
12
0
1111 8...888888 ⋅++⋅+⋅+⋅+⋅+⋅+⋅= amamamamamamamb ,
аналогично 11b определяются остальные элементы ijb в правой части равенства.
Вследствии единственности представления одного и того же числа в различных системах счисления,
можно утверждать, что только абсолютно идентичные части изображений будут представимы одним и тем же
числом. Остальные этапы распознавания изображения, включая нормирование укрупненной матрицы и
вычисление следов, аналогичны случаю двуцветного изображения. Вектором распознавания также служит
вектор, состоящий из числовых значений следов матриц.
Описанный метод возможно перенести на любое количество цветов, используя процесс сегментации.
Под сегментацией, в широком смысле, понимают преобразование полутоновых или цветных изображений в
изображение, имеющее меньшее число цветов или тонов, чем исходное [9]. Применение известных методов
сегментации позволит использовать описываемый метод для произвольных цветных изображений.
Следует отметить, что укрупнение ячеек оцифрованной матрицы изображения описанным способом
приведет к распознаванию изображений, идентифицирующихся до точного значения каждого пикселя.
Для избавления от случайных помех можно использовать второй вариант укрупнения ячеек исходной
матрицы, который заключается в определении доминирующего цвета путем подсчета числа пикселей каждого
цвета в текущей ячейке. Числовая характеристика получившегося цвета является элементом укрупненной
матрицы B , соответствующим текущей ячейке матрицы.
Распознавание изображений произвольного размера. В большинстве прикладных задач распозна-
ваемые объекты имеют большие общепринятые размеры, например, 512 х 512 пикселей. Матрицу произволь-
ного размера можно свести к матрице необходимого размера путем разбиения на клетки. Размер клетки
устанавливается на основании численного эксперимента в конкретной предметной области (как правило, это
4 х 4 или 2 х 2, – при необходимости недостающее количество строк или столбцов можно заполнить нулями).
Вся исходная клетка разбивается на вложенные друг в друга клетки такого же размера. Число вложений
неограниченно до момента точной идентификации всех элементов такой клетки. Схематически этот
итеративный процесс можно изобразить следующим образом (рис. 3).
Пример 2. Рассмотрим двуцветное изображение (64 х 64 пикселя) (рис. 4).
Рис. 3. Схема процесса укрупнения клеток матрицы изображения
Рис. 4. Иероглиф «Сотня»
Прикладне програмне забезпечення
717
Разобъем оцифрованную матрицу изображения (64х64) на клетки размерностью 4х4. Процесс
последовательного укрупнения клеток матрицы приведен далее.
(16х16)
0 0 0 0 0 0 0 0 0 57344 61440 61440 61440 61440 64512 0
0 34944 65520 65520 65520 65528 65535 65535 65535 65535 65535 65535 65535 65535 65535 0
0 204 255 255 255 255 255 51455 65535 65535 511 255 255 255 255 0
0 0 0 0 0 0 49152 65534 65535 4919 0 0 0 0 0 0
0 0 0 0 0 61120 65535 65535 65535 65281 65280 65280 65528 65535 4369 0
0 0 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 4369 0
0 0 65535 65535 0 0 0 0 0 0 0 0 61166 65535 4369 0
0 32768 65535 65535 0 0 0 0 0 0 0 0 61166 65535 4369 0
0 34952 65535 65535 0 57344 61440 61440 64512 65280 65280 65280 65518 65535 4369 0
0 34952 65535 65535 65532 65535 65535 4607 255 255 255 255 61183 65535 4369 0
0 34952 65535 65535 0 0 0 0 0 0 0 0 61166 65535 4369 0
0 34952 65535 65535 0 0 0 0 0 0 0 0 61166 65535 13073 0
0 34952 65535 65535 0 0 0 0 0 0 0 0 61166 65535 13107 0
0 34952 65535 65535 64512 65280 65280 65535 65535 65535 65535 65535 65535 14207 16 0
0 52424 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 32767 273 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(4х4)
1.459E+7 3.141E+9 3.767E+8 8.239E+6
3.704E+9 1.664E+7 1.671E+7 9.163E+8
3.741E+9 8.782E+6 1.04E+6 1.059E+9
2.427E+8 2.673E+8 2.674E+8 1.028E+7
Вектор распознавания, состоящий из следов степеней последней матрицы, имеет вид
(1.72411927354642, 1.84155825913441, 2.20477622051669, 2.76258275551884).
Заключение
Таким образом, сортировка может служить единой основой для автоматической идентификации нулей
и экстремумов произвольной функции одной и более переменных в произвольно фиксированной части области
определения. В частности, с использованием метода Леверье на этой основе вычисляются нули
характеристического полинома матрицы. Для нулей полиномов в общем случае учитывается их кратность.
Функция может быть задана значениями на равномерной сетке. В этом случае идентифицируются нули и
экстремумы разностных решений обыкновенных дифференциальных уравнений и уравнений в частных
производных. Для оцифрованного изображения на плоскости, рассматриваемого как разновидность дискретной
функции двух переменных на сетке пиксельных элементов, на той же основе строится вектор распознавания.
При этом входное изображение классифицируется как произвольное геометрическое место точек. Для подхода
в целом существенно, что процесс обработки использует только операции сравнения. Это исключает
накопление погрешности, влечет высокую точность локализации экстремумов и устойчивость идентификации
изображений.
1. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. I //
Кибернетика и системный анализ. – 2001. – № 4. – С. 142 – 159.
2. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. II // Там
же. – 2001. – № 5. – С. 81 – 101.
3. Ромм Я.Е., Заика И.В. Программная локализация экстремумов функций и разностных приближений решений дифференциальных
уравнений // Известия вузов. Северо-Кавказский регион. Технические науки. Спец. выпуск. «Математическое моделирование и
компьютерные технологии». – 2005. – С. 47 – 52.
4. Ромм Я.Е., Гуревич М.Ю., Белоконова С.С., Соловьева И.А. Вычисление нулей и полюсов функций на основе устойчивой адресной
сортировки с приложением к поиску и распознаванию // Проблемы программирования. – 2004. – № 2-3.– С. 462 – 472.
5. Ромм Я.Е., Заика И.В., Соловьева И.А. Метод программной оптимизации в приложении к математическим моделям экономики // В сб.:
«Проблемы регионального управления, экономики, права и инновационных процессов в образовании». Таганрог: 2005, Т. 2. –
С. 17–26.
6. Ромм Я.Е., Соловьёва И.А. Вычисление собственных значений матриц на основе сортировки с приложением к построению
нормальной жордановой формы ТГПИ. – Таганрог, 2005. – 32 с. Деп. В ВИНИТИ 17. 05. 2005, № 710-В2005.
7. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. – М.: Наука, 1977. – Т. .2. – 400 с.
8. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. – СПб: Лань, 2002. – 736 с.
9. Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. – М: Машиностроение, 1990. – 320 с.
10. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений. – В кн.: Теория сложности вычислений. I:
Записки научных семинаров ЛОМИ АН СССР. – Л., 1982. – 118. – С. 159 – 187.
|
| id | nasplib_isofts_kiev_ua-123456789-1585 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T16:32:05Z |
| publishDate | 2006 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Ромм, Я.Е. Заика, И.В. Тюшнякова, И.А. 2008-08-27T09:39:19Z 2008-08-27T09:39:19Z 2006 Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений / Я.Е. Ромм, И.В. Заика, И.А. Тюшнякова // Проблеми програмування. — 2006. — N 2-3. — С. 708-717. — Бібліогр.: 10 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1585 681.3 Показано, что сортировка может служить единой основой для автоматической идентификации нулей и экстремумов
 произвольной функции одной и более переменных в произвольно фиксированной части области определения. Нули полинома
 вычисляются с учетом кратности, включая случай характеристического полинома матрицы. Функция может задаваться
 значениями на равномерной сетке. В частности, идентифицируются нули и экстремумы разностных решений обыкновенных
 дифференциальных уравнений и уравнений в частных производных. Для оцифрованного изображения на плоскости как
 дискретной функции двух переменных на сетке пиксельных элементов на этой основе строится вектор распознавания. Процесс
 обработки использует лишь операции сравнения, что исключает накопление погрешности, влечет высокую точность локализации
 экстремумов и устойчивость идентификации изображений. It is shown that sorting can form a unique basis for automatic identification of zeroes and extremums of any function of one and more
 variables in any way fixed раrt of definitional domain. Polynomials` zeroes are calculated with consideration of multiplicity, including a
 case of a characteristic polynomial of a matrix. Function can be set by values on a analytical grid. In particular, zeroes and extremums of
 difference solutions of the ordinary differential equations and the equations in partial derivatives are identified. For digitized image on a
 plane as discrete function of two variables on a pixel elements’ grid on this basis the recognition vector is under construction.
 Manufacturing process uses only comparison operations, which excludes error accumulation and implyies split-hair accuracy of
 localization of extremums and stability of images identification. ru Інститут програмних систем НАН України Прикладне програмне забезпечення Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений Identification extremums of functions on the basis of sorting with the appendix to computing schemes of algebra, the analysis and to images recognition Article published earlier |
| spellingShingle | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений Ромм, Я.Е. Заика, И.В. Тюшнякова, И.А. Прикладне програмне забезпечення |
| title | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений |
| title_alt | Identification extremums of functions on the basis of sorting with the appendix to computing schemes of algebra, the analysis and to images recognition |
| title_full | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений |
| title_fullStr | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений |
| title_full_unstemmed | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений |
| title_short | Идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений |
| title_sort | идентификация экстремумов функции на основе сортировки с приложением вычислительным схемам алгебры, анализа и распознаванию изображений |
| topic | Прикладне програмне забезпечення |
| topic_facet | Прикладне програмне забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1585 |
| work_keys_str_mv | AT rommâe identifikaciâékstremumovfunkciinaosnovesortirovkispriloženiemvyčislitelʹnymshemamalgebryanalizairaspoznavaniûizobraženii AT zaikaiv identifikaciâékstremumovfunkciinaosnovesortirovkispriloženiemvyčislitelʹnymshemamalgebryanalizairaspoznavaniûizobraženii AT tûšnâkovaia identifikaciâékstremumovfunkciinaosnovesortirovkispriloženiemvyčislitelʹnymshemamalgebryanalizairaspoznavaniûizobraženii AT rommâe identificationextremumsoffunctionsonthebasisofsortingwiththeappendixtocomputingschemesofalgebratheanalysisandtoimagesrecognition AT zaikaiv identificationextremumsoffunctionsonthebasisofsortingwiththeappendixtocomputingschemesofalgebratheanalysisandtoimagesrecognition AT tûšnâkovaia identificationextremumsoffunctionsonthebasisofsortingwiththeappendixtocomputingschemesofalgebratheanalysisandtoimagesrecognition |