MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Обработка сигналов и изображений\ Image Processing Toolbox

И.М.Журавель "Краткий курс теории обработки изображений"

В оглавление книги \ К следующему разделу \ К предыдущему разделу

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

Существуют различные подходы к решению задачи распознавания объектов. В этом материале будут рассмотрены некоторые методы структурного распознавания. Суть структурного распознавания состоит в представлении интересующих объектов в виде символьных строк, деревьев, графов и других дескрипторов. Также важным моментом является формирование критериев распознавания на основе выбранного описания объектов.

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

Мера схожести символьных строк

Одна из таких мер была предложена Тзе и Янгом в 1981 году. Наиболее простую меру схожести строк можно представить в виде следующего аналитического выражения

где a, b – строки;
α – число совпадений между строками a и b.

Рассмотренная мера равна бесконечности при полном совпадении строк и равна нулю, когда таких совпадений не существует.

Далее рассмотрим задачу распознавания объектов на основе сопоставления строк.

Пример 1.

Считаем изображения трех различных объектов – круга (рис. 1), квадрата (рис. 2) и треугольника (рис. 3).

L=imread('im1.bmp');
L=L(:,:,1);
L=double(L)./255;
iptsetpref('ImshowBorder','tight');
figure, imshow(L);

Рис. 1. Изображение круга.

L=imread('im2.bmp');
L=L(:,:,1);
L=double(L)./255;
iptsetpref('ImshowBorder','tight');
figure, imshow(L);

Рис. 2. Изображение квадрата.

L=imread('im3.bmp');
L=L(:,:,1);
L=double(L)./255;
iptsetpref('ImshowBorder','tight');
figure, imshow(L);

Рис. 3. Изображение треугольника.

Чтобы продемонстрировать эффективность рассмотренной выше меры схожести для распознавания объектов, сначала границы представленных объектов необходимо приблизить ломаной линией с различными параметрами (различным размером ячейки приближения).

Приближение ломаной линией минимальной длины

Если речь идет о приближении, то сразу возникает вопрос о точности такого приближения. Наиболее точным приближение будет тогда, когда число отрезков ломаной и число точек границы будут совпадать. Однако на практике суть такого приближения состоит в том, чтобы с помощью наименьшего количества отрезков приблизить форму объекта так, чтобы она была узнаваема. Для этого можно использовать функцию minperpoly [1].

Сформируем результаты приближения контуров объектов функцией minperpoly с различной длиной ячейки (2, 5 и 11 пикселей).

Для первого объекта (круга)

cellsize=2;
[x,y]=minperpoly(L,cellsize);
L1=zeros(256);
figure, imshow(L1);
line([y;y(1)],[x;x(1)],'color',[1 1 1]);

Рис. 4. Приближение контура первого объекта (круга) с размером ячеек 2.

cellsize=5;
[x,y]=minperpoly(L,cellsize);
L1=zeros(256);
figure, imshow(L1);
line([y;y(1)],[x;x(1)],'color',[1 1 1]);

Рис. 5. Приближение контура первого объекта (круга) с размером ячеек 5.

cellsize=11;
[x,y]=minperpoly(L,cellsize);
L1=zeros(256);
figure, imshow(L1);
line([y;y(1)],[x;x(1)],'color',[1 1 1]);

Рис. 6. Приближение контура первого объекта (круга) с размером ячеек 11.

Аналогично приближаем контуры двух других объектов (квадрата и треугольника) с различным размером ячеек.

Рис. 7. Приближение контура второго объекта (квадрата) с размером ячеек 2.

Рис. 8. Приближение контура второго объекта (квадрата) с размером ячеек 5.

Рис. 9. Приближение контура второго объекта (квадрата) с размером ячеек 11.

Рис. 10. Приближение контура третьего объекта (треугольника) с размером ячеек 2.

Рис. 11. Приближение контура третьего объекта (треугольника) с размером ячеек 5.

Рис. 12. Приближение контура третьего объекта (треугольника) с размером ячеек 11.

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

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

Для этого будем использовать выражение, которое приведено в начале этого материала и реализовано в виде функции strsimilarity [1]:

L=imread('image1.bmp');
L=L(:,:,1);
L1=imread('image2.bmp');
L1=L1(:,:,1);
R1=strsimilarity(char(L(64,:)),char(L1(64,:)))
R2=strsimilarity(char(L(128,:)),char(L1(128,:)))
R3=strsimilarity(char(L(192,:)),char(L1(192,:)))

Представим полученные данные в виде таблиц.

Таблица 1. Вычисление меры схожести строк для изображения круга

  Изображение приближения контура круга с размером ячеек 5 (рис. 5) Изображение приближения контура круга с размером ячеек 11 (рис. 6) Номер строки
Изображение приближения контура круга с размером ячеек 2 (рис. 4)
127 20,3333 n=64
63 16,0667 n=128
2,0843 2,0843 n=192

Таблица 2. Вычисление меры схожести строк для изображения квадрата

  Изображение приближения контура квадрата с размером ячеек 5 (рис. 8) Изображение приближения контура квадрата с размером ячеек 11 (рис. 9) Номер строки
Изображение приближения контура квадрата с размером ячеек 2 (рис. 7)
84,3333 18,6923 n=64
127 24,6000 n=128
127 35,5714 n=192

Таблица 3. Вычисление меры схожести строк для изображения треугольника

  Изображение приближения контура треугольника с размером ячеек 5 (рис. 11) Изображение приближения контура треугольника с размером ячеек 11 (рис. 12) Номер строки
Изображение приближения контура треугольника с размером ячеек 2 (рис. 10)
127 9,6667 n=64
50,2000 127 n=128
225 17,2857 n=192

Таблица 4. Вычисление меры схожести строк для изображений из различных наборов, которые были приближены с размером ячейки 2

  Изображение приближения контура квадрата с размером ячеек 5 (рис. 7) Изображение приближения контура треугольника с размером ячеек 11 (рис. 10) Номер строки
Изображение приближения контура круга с размером ячеек 2 (рис. 4)
2,7647 2,3684 n=64
13,2222 1,9091 n=128
2,0118 3,0635 n=192

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

  Изображение приближения контура квадрата с размером ячеек 5 (рис. 8) Изображение приближения контура треугольника с размером ячеек 11 (рис. 10) Номер строки
Изображение приближения контура круга с размером ячеек 5 (рис. 5)
2,8209 2,3684 n=64
11,8000 2,1605 n=128
0,5422 0,7655 n=192

Таблица 6. Вычисление меры схожести строк для изображений из различных наборов, которые были приближены с размером ячейки 11

  Изображение приближения контура квадрата с размером ячеек 5 (рис. 9) Изображение приближения контура треугольника с размером ячеек 11 (рис. 12) Номер строки
Изображение приближения контура круга с размером ячеек 11 (рис. 6)
2,8209 1,9091 n=64
22,2727 2,4133 n=128
0,5901 0,9394 n=192

Проанализируем полученные данные. Из представленных в таблицах данных видно, что в большинстве случаев значение коэффициента схожести строк изображений в пределах одного набора (таблицы 1-3) значительно выше значений коэффициентов схожести строк изображений из различных наборов (таблицы 4-6). Это свойство лежит в основе рассматриваемого структурного распознавания объектов.

Пример 2.

Рассмотрим еще один пример структурного распознавания на основе сопоставления строк. Однако теперь к координатам точек приближенного контура (x,y) объекта будет добавлен некоторый шум.

x=x+p.*randn(length(x),1);
y=y+p.*randn(length(y),1);

где p = 1,3,7 – параметр, который устанавливает уровень зашумленности.

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

Рис. 13. Приближение контура круга с добавлением шумовой составляющей при p=1.

Рис. 14. Приближение контура круга с добавлением шумовой составляющей при p=3.

Рис. 15. Приближение контура круга с добавлением шумовой составляющей при p=7.

Рис. 16. Приближение контура квадрата с добавлением шумовой составляющей при p=1.

Рис. 17. Приближение контура квадрата с добавлением шумовой составляющей при p=3.

Рис. 18. Приближение контура квадрата с добавлением шумовой составляющей при p=7.

Рис. 19. Приближение контура треугольника с добавлением шумовой составляющей при p=1.

Рис. 20. Приближение контура треугольника с добавлением шумовой составляющей при p=3.

Рис. 21. Приближение контура треугольника с добавлением шумовой составляющей при p=7.

На основе полученных изображений вычисляется значение меры схожести строк соответствующих данных. Результаты проведенных вычислений представлены в таблицах 7-10.

Таблица 7. Вычисление меры схожести строк для изображений круга с различным уровнем наложенного шума.

  Изображение приближения контура круга с размером ячеек 8 и p=3 (рис. 14) Изображение приближения контура круга с размером ячеек 8 и p=7 (рис. 15) Номер строки
Изображение приближения контура круга с размером ячеек 8 и p=1 (рис. 13)
63 27,4444 n=74
255 27,4444 n=128
27,4444 12,4737 n=182

Таблица 8. Вычисление меры схожести строк для изображений квадрата с различным уровнем наложенного шума.

  Изображение приближения контура квадрата с размером ячеек 8 и p=3 (рис. 17) Изображение приближения контура квадрата с размером ячеек 8 и p=7 (рис. 18) Номер строки
Изображение приближения контура квадрата с размером ячеек 8 и p=1 (рис. 16)
35,5714 31 n=74
41,6667 35,5714 n=128
63 17,2857 n=182

Таблица 9. Вычисление меры схожести строк для изображений треугольника с различным уровнем наложенного шума.

  Изображение приближения контура треугольника с размером ячеек 8 и p=3 (рис. 20) Изображение приближения контура треугольника с размером ячеек 8 и p=7 (рис. 21) Номер строки
Изображение приближения контура треугольника с размером ячеек 8 и p=1 (рис. 19)
50,2000 10,1304 n=74
41,6667 16,0667 n=128
35,5714 84,3333 n=182

Таблица 10. Вычисление меры схожести строк для изображений разных объектов с одинаковым уровнем наложенного шума.

  Изображение приближения контура квадрата с размером ячеек 8 и p=7 (рис. 18) Изображение приближения контура треугольника с размером ячеек 8 и p=7 (рис. 21) Номер строки
Изображение приближения контура круга с размером ячеек 8 и p=7 (рис. 15)
3,3390 1,8132 n=74
11,8000 1,8764 n=128
6,1111 11,1905 n=182

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

Таким образом, для выбора (распознавания) нужного изображения объекта из базы данных поступают следующим образом. Необходимо иметь изображение объекта, который необходимо распознать – так называемый эталон. Далее вычисляют значение меры схожести строк изображения эталона и каждого изображения из базы. Максимальное значение меры схожести будет соответствовать максимально похожему на эталон объекту.

Программы, которые используются в материале.

1) Приближение границ объектов.

clear;
%Считывание исходного изображения
L=imread('im1.bmp');
%Использование одной цветовой составляющей

L=L(:,:,1);
L=double(L)./255;
iptsetpref('ImshowBorder','tight');

%Визуализация исходного изображения
figure, imshow(L);

%Приближение границ объектов ломаной минимальной длины
cellsize=7; %Размер ячейки
[x,y]=minperpoly(L,cellsize);
x=
L1=zeros(256);
figure, imshow(L1);

line([y;y(1)],[x;x(1)],'color',[1 1 1]);

2) Вычисление меры схожести.

clear;
%Считывание исходных данных
L=imread(im1.bmp');
L=L(:,:,1);
L1=imread('im2.bmp');
L1=L1(:,:,1);

%Вычисление меры схожести
R1=strsimilarity(char(L(74,:)),char(L1(74,:)))
R2=strsimilarity(char(L(128,:)),char(L1(128,:)))
R3=strsimilarity(char(L(182,:)),char(L1(182,:)))

Литература

  1. Rafael C. Gonsales, Richard E. Woods, Steven L. Eddins. Digital Image Processing using Matlab. Rafael

В оглавление книги \ К следующему разделу \ К предыдущему разделу


Поиск по сайту:

Система Orphus

Яндекс.Метрика