СПОСОБ АВТОМАТИЗИРОВАННОГО РАЗБИЕНИЯ НА ГРУППЫ УРОВНЕЙ ЯРКОСТИ ПИКСЕЛОВ РАСТРОВЫХ ИЗОБРАЖЕНИЙ ПО ЗНАЧЕНИЯМ ИХ ПОВТОРЯЕМОСТИ Российский патент 2007 года по МПК G06K9/00 G06K9/36 

Описание патента на изобретение RU2311680C1

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

Известны системы распознавания, например, при сканировании изображений, в которых пороги задаются вручную, например в системах сканирования фирмы EPSON [1]. Данные методы требуют обязательное участие человека в предварительном анализе изображения и не применимы в системах автоматического распознавания.

Наиболее близким по совокупности признаков является способ разбиения на группы (критерий развала на кучи), предложенный в работе [2]. Здесь рассмотрена некоторая числовая характеристика s, которая может принимать n различных значений si(i=1,...,n), имеющих значения повторяемости, задаваемые гистограммой Н={h1,...,hn}. Определен общий объем совокупности чисел

и ее дисперсия При помощи порогов совокупность чисел s разбита на кучи {s1,...,sN} из подряд стоящих значений чисел. Для каждой кучи su рассмотрен объем Qu и дисперсия σu2. Показатель кучности задан формулой

В качестве лучшего принимается разбиение с наименьшим значением показателя κ. При отсутствии ограничений для любой гистограммы Н глобальный минимум показателя κ=0 будет достигаться на тривиальном разбиении на кучи, при котором каждая куча состоит только из одного числа si. Однако такой глобальный минимум не дает конструктивной информации по разделению изображения. Поэтому предложено на область поиска наложить дополнительные ограничения: 1) вначале группы suн идет возрастание значений повторяемости, а в конце suк - их убывание, 2) объем каждой кучи не должен быть слишком малым (Qu/Q≥1/8), 3) число куч не должно быть больше 4 (N≤4).

Предложенный способ обладает следующими недостатками.

1. При возрастании N величина критерия κ как правило также возрастает. Это не позволяет сравнивать пороговые разбиения с различными значениями N. Данный критерий позволяет сравнивать между собой разбиения с одинаковыми количествами групп N.

2. В то же время для модельной гистограммы вида, показанного на Фиг.1, критерий κ без введения порога (N=1) и с введением одного порога (N=2), дающего искомое разделение, равен нулю. Т.е. рассмотренный критерий не всегда позволяет сравнивать разбиения с одинаковым числом порогов.

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

Поставленная задача достигается тем, что предложен способ автоматизированного разбиения на группы уровней яркости пикселов растровых изображений по значениям их повторяемости, заключающийся в том, что для заданного растрового изображения, у которого есть ряд уровней яркости пикселов, имеющих значения повторяемости и общий объем, вводится разбиение на группы подряд стоящих уровней яркости, причем вначале группы идет возрастание значений повторяемости, а в конце - их убывание, соотношение объема каждой группы к общему объему должно быть не менее 1/8 и число групп не должно быть больше 4, для каждой группы введен показатель качества, а для всего разбиения - обобщенный показатель качества, критерием оптимальности которого является минимум, согласно изобретению в качестве показателя качества группы принимается момент инерции значений повторяемости относительно медианы группы, для которой суммы повторяемостей слева и справа равны между собой, а обобщенный показатель качества всего разбиения на группы имеет вид:

где N - число групп,

- объем группы с номером u (u=1, ..., N),

{h1, ..., hn} - повторяемости, соответствующие уровням яркости пикселов {s1, ..., sn},

- показатель качества группы с номером u,

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

suм - медиана значений яркости в группе с номером u.

Рассмотрим для n уровней яркости пикселов si(i=1,...,n) гистограмму их повторяемости Н={h1,...,hn}. Как показали эксперименты, для фиксированной группы su частным критерием качества, наилучшим образом отражающим свойство "кучности", является не дисперсия, а момент инерции группы относительно ее медианы suм:

Для того чтобы объединить выбранные частные критерии в один общий, рассмотрим в качестве модельного равномерное распределение характеристики интенсивности h с большим числом значений, равномерно распределенным в интервале [0,1] (Фиг.2). В данной гистограмме критерий не должен выделять пороги, поскольку на самом деле их не существует.

При отсутствии деления гистограммы на группы общий момент инерции относительно медианы равен

где Q=h·1 - общий объем гистограммы.

При произвольном разбиении данной гистограммы на N групп, которые по оси s занимают отрезки длиной s1, s2,...,sN(s1+s2+...+sN=1), их моменты инерции будут равны

Значение общего суммарного критерия останется неизменным (до и после разбиения) в том случае, когда каждый частный критерий f(gu) будет включен в общую сумму с весовым коэффициентом 1/(su2).

Вводя в рассматриваемых задачах в коэффициенты вместо su величины объемов групп qu, получим обобщенный критерий следующего вида:

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

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

ИСХОДНЫЕ ДАННЫЕ.

Для некоторой числовой характеристики s задана гистограмма H, а также пороговое значение δ предельно малого относительного объема групп. Необходимо выяснить возможность порогового разделения гистограммы для заданной гистограммы. Если возможно, то найти такое число N групп в гистограмме и их состав, при котором достигает минимума обобщенный критерий при условии, что относительный объем групп не превышает δ и разделение групп производится в области локальных минимумов на гистограмме.

ПРЕДВАРИТЕЛЬНЫЕ ДЕЙСТВИЯ.

Вычисляется общий объем гистограммы Q и пороговое предельно малое значение объема группы Qпр=δ·Q.

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

ШАГ 1. Предварительный просмотр гистограммы. Выделение всех локальных минимумов на ней. Данные минимумы бывают одиночные (когда в точке минимума s=si выполняется условие hS(i-1)>hS i<hS(i+1)) и групповые, когда минимальное значение принимают несколько подряд стоящих значений гистрограммы. В обоих случаях возникает необходимость задания порогового значения относительно минимальных значений. Поскольку значение критерия меньше, когда состав групп более однороден по величине значений hS, то минимумы присоединяем к тем промежуточным группам значений, у которых более близкое среднее значение. В итоге создается линейный массив возможных порогов Р некоторой длины nm. Если локальных минимумов на гистограмме нет, то она считается неразделимой на группы. Выход из алгоритма с отрицательным ответом.

ШАГ 2. Расчет начального значения критерия при отсутствии порогов: Fнач=F(N=1). Это же значение присваиваем текущему минимальному значению критерия: Fmin=Fнач.

ШАГ 3. Перебор всех возможных вариантов порогов, вычисление значений критерия для них и выбор оптимального варианта.

3.1. Генерация возможных порогов. Поскольку для каждого возможного порога Рi есть две возможности - входить в набор или нет, то общее число нерассмотренных вариантов порогов равно (один вариант, в котором в набор не вошел ни один порог, рассмотрен на ШАГЕ 2). Кодируя каждый из вариантов числом от 1 до , вхождение каждого из порогов в выбранном варианте i находим, разлагая это число в двоичной системе в вектор длины nm. Те позиции j, на которых стоит 1, задают вхождение j-го порога в набор. Если стоит 0, то порог не входит в набор.

3.2. Проверка набора порогов по предельно малому объему группы Qпр. Каждый конкретный набор порогов задает на гистограмме некоторый набор групп. Объемы всех групп Qu проверяются на выполнение условия Qu>Qпр. Если хотя бы для одной из групп условие не выполнено, весь набор исключается из дальнейшего анализа.

3.3. Вычисление критерия. Проверка оптимальности пороговых порогов. Для выбранного набора групп s1, s2,...,sN вычисляется значение критерия F(s1, s2,...,sN). Если выполняется условие F(s1, s2,...,sN)<Fmin, то найдено более оптимальное разбиение на группы. В этом случае выполняем присваивание Fmin=F(s1, s2,...,sN) и запоминаем соответствующее пороговое разделение.

ШАГ 4. Итоговая проверка. Если после окончания перебора всех вариантов порогов выяснилось, что Fmin=Fнач, то это свидетельствует, что гистограмма плохо разделима на группы и введение порогов на ней нецелесообразно. Выход из алгоритма с отрицательным ответом.

Если Fmin<Fнач, то получено искомое оптимальное число групп N и разбиение множества значений на группы {s}.

Пример.

ИСХОДНЫЕ ДАННЫЕ. Для двухцветного растрового 16-цветного изображения (n=16) размером 20×80 получена гистограмма, показанная на Фиг.3, у которой

h0=14; h1=9; h2=9; h3=14; h4=13; h5=8; h6=11; h7=9; h8=12; h9=7; h10=7; h11=7; h12=10; h13=8; h14=10; h15=12.

Пороговое значение предельно малого относительного объема групп δ=0,15.

Необходимо выяснить возможность порогового разделения гистограммы для заданной гистограммы. Если возможно, то найти такое число N групп в гистограмме и их состав, при котором достигает минимума обобщенный критерий при условии, что относительный объем групп не превышает δ и разделение групп производится в области локальных минимумов на гистограмме.

ПРЕДВАРИТЕЛЬНЫЕ ДЕЙСТВИЯ.

Вычисляется: 1) общий объем гистограммы: Q=160, 2) пороговое предельно малое значение объема группы Qпр=δ·Q=0,15·160=24.

ШАГ 1. Выделены внутренние локальные минимумы гистограммы, которые задают начало возможных групп: 1, 6, 9, 13. Общее число их равно 4.

ШАГ 2. Начальное значение критерия при отсутствии порогов: Fнач=F(N=1)=0,141392. Это же значение присваиваем текущему минимальному значению критерия: Fmin=Fнач.

ШАГ 3. Перебор всех возможных вариантов порогов, вычисление значений критерия для них и выбор оптимального варианта.

Вариант 1000, значение критерия: F=0,146384>Fmin.

Вариант 0100, значение критерия: F=0,144421>Fmin.

Вариант 1100, значение критерия: F=0,14888>Fmin.

Вариант 0010, значение критерия: F=0,131995<Fmin, Fmin=0,131995.

Вариант 1010, значение критерия: F=0,134505>Fmin.

Вариант 0110, значение критерия: F=0,128107<Fmin, Fmin=0,128107.

Вариант 0001, значение критерия: F=0,133057>Fmin.

Вариант 1001, значение критерия: F=0,132206>Fmin.

Вариант 0101, значение критерия: F=0,140083>Fmin.

Вариант 1101, значение критерия: F=0,144533>Fmin.

У вариантов 0011, 1011, 0111, 1111 есть группы с объемом, меньшим Qпр, поэтому они не анализируются.

В итоге оптимальным принят вариант 0110 со значением критерия F=0,128107. Пороговые значения 5,5 и 11,5. При этом N=3, s1={0,1,2,3,4,5}, s2={6,7,8,9,10,11}, s3={12,13,14,15}.

Похожие патенты RU2311680C1

название год авторы номер документа
СПОСОБ ПОДАВЛЕНИЯ НЕРАВНОМЕРНОСТИ РАСПРЕДЕЛЕНИЯ ЯРКОСТИ ИЗОБРАЖЕНИЙ ПРИ ПОЛУЧЕНИИ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ МЕДИЦИНСКИХ МИКРОПРЕПАРАТОВ 2008
  • Никитаев Валентин Григорьевич
  • Проничев Александр Николаевич
  • Комаров Владимир Владимирович
  • Чистов Кирилл Сергеевич
  • Филиппов Антон Александрович
RU2390842C1
СПОСОБ АВТОМАТИЧЕСКОЙ СЕГМЕНТАЦИИ ПОЛУТОНОВЫХ СЛОЖНОСТРУКТУРИРОВАННЫХ РАСТРОВЫХ ИЗОБРАЖЕНИЙ 2014
  • Томакова Римма Александровна
  • Филист Сергей Алексеевич
  • Кореневский Николай Алексеевич
  • Шаталова Ольга Владимировна
  • Курочкин Александр Геннадьевич
RU2580074C1
СПОСОБ АВТОМАТИЧЕСКОЙ СЕГМЕНТАЦИИ ПОЛУТОНОВОГО ИЗОБРАЖЕНИЯ ПО ФОРМЕ ЯРКОСТНОЙ ГИСТОГРАММЫ 1998
  • Мадонов А.Е.
  • Белоконь С.П.
RU2148858C1
СПОСОБ СЕГМЕНТАЦИИ СЛОЖНОСТРУКТУРИРОВАННЫХ РАСТРОВЫХ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ СОСТАВНЫХ МОРФОЛОГИЧЕСКИХ ОПЕРАТОРОВ 2012
  • Томакова Римма Александровна
  • Филист Сергей Алексеевич
  • Кореневский Николай Алексеевич
  • Шаталова Ольга Владимировна
RU2510897C2
СПОСОБ РАСПОЗНАВАНИЯ КОНТЕНТА СЖАТЫХ НЕПОДВИЖНЫХ ГРАФИЧЕСКИХ СООБЩЕНИЙ В ФОРМАТЕ JPEG 2018
  • Иванов Владимир Алексеевич
  • Скурнович Алексей Валентинович
  • Ревякин Андрей Михайлович
RU2680358C1
КОМПЛЕКСНАЯ КОРРЕЛЯЦИОННО-ЭКСТРЕМАЛЬНАЯ НАВИГАЦИОННАЯ СИСТЕМА 2013
  • Джанджгава Гиви Ивлианович
  • Лещук Олег Григорьевич
  • Сазонова Татьяна Владимировна
  • Симкин Николай Васильевич
  • Шелагурова Марина Сергеевна
RU2525601C1
ОПРЕДЕЛЕНИЕ НАПРАВЛЕНИЯ СТРОК ТЕКСТА 2016
  • Загайнов Иван Германович
  • Рыбкин Владимир Юрьевич
RU2633182C1
СПОСОБ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ИМПУЛЬСНОГО ШУМА ПРИ ОБРАБОТКЕ ИЗОБРАЖЕНИЙ И УСТРОЙСТВО, ЕГО РЕАЛИЗУЮЩЕЕ 2010
  • Марчук Владимир Иванович
  • Воронин Вячеслав Владимирович
  • Шерстобитов Александр Иванович
  • Франц Владимир Александрович
  • Франкова Кристина Николаевна
  • Даниленко Ирина Николаевна
RU2449355C2
Способ автоматической сегментации флюорограмм грудной клетки больных пневмонией 2016
  • Дураков Игорь Владимирович
  • Кудрявцев Павел Сергеевич
  • Кузьмин Александр Алексеевич
  • Филист Сергей Алексеевич
  • Шаталова Ольга Владимировна
RU2629629C1
Устройство сегментации изображений 2018
  • Семенищев Евгений Александрович
  • Воронин Вячеслав Владимирович
  • Толстова Ирина Владимировна
  • Чернышов Дмитрий Юрьевич
  • Гапон Николай Валерьевич
  • Сизякин Роман Алексеевич
  • Письменскова Марина Михайловна
RU2695980C1

Иллюстрации к изобретению RU 2 311 680 C1

Реферат патента 2007 года СПОСОБ АВТОМАТИЗИРОВАННОГО РАЗБИЕНИЯ НА ГРУППЫ УРОВНЕЙ ЯРКОСТИ ПИКСЕЛОВ РАСТРОВЫХ ИЗОБРАЖЕНИЙ ПО ЗНАЧЕНИЯМ ИХ ПОВТОРЯЕМОСТИ

Изобретение относится к распознаванию растровых изображений и предназначено для увеличения эффективности определения пороговых значений яркости пикселов либо характеристик, производных от них для заданных матриц растровых изображений. Технический результат - увеличение эффективности определения пороговых значений яркости пикселов достигается тем, что для заданного растрового изображения, у которого есть ряд уровней яркости пикселов, имеющих значения повторяемости и общий объем, вводится разбиение на группы подряд стоящих уровней яркости, причем в качестве показателя качества группы принимается момент инерции значений повторяемости относительно медианы группы, для которой суммы повторяемостей слева и справа равны между собой. Данный критерий позволяет эффективно выделять как оптимальное число N групп в гистограмме, так и состав групп в тех случаях, когда характер гистограммы позволяет сделать это. 3 ил.

Формула изобретения RU 2 311 680 C1

Способ автоматизированного разбиения на группы уровней яркости пикселов растровых изображений по значениям их повторяемости, заключающийся в том, что для заданного растрового изображения, у которого есть ряд уровней яркости пикселов, имеющих значения повторяемости и общий объем, вводится разбиение на группы подряд стоящих уровней яркости, причем вначале группы идет возрастание значений повторяемости, а в конце - их убывание, соотношение объема каждой группы к общему объему должно быть не менее 1/8 и число групп не должно быть больше 4, для каждой группы введен показатель качества, а для всего разбиения - обобщенный показатель качества, критерием оптимальности которого является минимум, отличающийся тем, что в качестве показателя качества группы принимается момент инерции значений повторяемости относительно медианы группы, для которой суммы повторяемостей слева и справа равны между собой, а обобщенный показатель качества всего разбиения на группы имеет вид:

где N - число групп уровней яркости пикселов,

s1, s2,...,sN, - группы уровней яркости пикселов,

- объем группы с номером u (u=1,...,N),

{h1,...,hn} - повторяемости, соответствующие уровням яркости пикселов {s1,...,sn},

- показатель качества группы с номером u,

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

suм - медиана значений яркости в группе с номером u.

Документы, цитированные в отчете о поиске Патент 2007 года RU2311680C1

СПОСОБ АНАЛИЗА РАСТРОВОГО ИЗОБРАЖЕНИЯ 2002
  • Анисимович К.В.
  • Терещенко В.В.
  • Рыбкин В.Ю.
  • Внучков Д.Н.
RU2251151C2
СПОСОБ МНОГОЭТАПНОГО АНАЛИЗА ИНФОРМАЦИИ РАСТРОВОГО ИЗОБРАЖЕНИЯ 2002
  • Анисимович К.В.
  • Терещенко В.В.
  • Рыбкин В.Ю.
  • Внучков Д.Н.
RU2234734C1
Аналоговый перемножитель 1976
  • Тарасов Виктор Петрович
  • Степаненко Игорь Павлович
  • Алексенко Андрей Геннадьевич
  • Тимонтеев Валерий Николаевич
  • Заика Владислав Васильевич
  • Ткаченко Владимир Александрович
  • Ламбин Владимир Иванович
SU602955A1
US 6792142 В1, 14.09.2004
US 5761344 А, 02.06.1998.

RU 2 311 680 C1

Авторы

Гданский Николай Иванович

Мальцевский Владислав Васильевич

Марченко Юлия Андреевна

Даты

2007-11-27Публикация

2006-05-19Подача