Второе конкурсное задание для тех, кто намерен бороться за Национальную премию в области компьютерных аудиовизуальных искусств и технологий «Эвридика» («Мир ПК», №1/02, с.71).
Проблема распознавания образов уже десятки лет занимает умы исследователей. Ее разрешение позволит автоматизировать многие процессы, до сей поры подвластные лишь человеческому мозгу. Понятно, что если человек способен досконально описать, по какому принципу он объединяет отдельные объекты в образы, то он сможет передать это умение распознающей системе.
Рассмотрим одну из частных задач, связанных с распознаванием образов, — вычленение однородных фрагментов в растровом изображении. Ее решение важно, например, в процессе подготовки информации об изображении для последующего анализа статистическими или иными методами на более высоком уровне.
Следующее задание нашего конкурса таково: напишите программу, которая будет выделять однородные по цвету фрагменты из растрового изображения и сохранять их в виде контуров (координаты точек, совокупность которых описывает замкнутую область).
В результате обработки изображения нужно получить список объектов, содержащий характеристики выделенных фрагментов, — контуров, координат и цветовых параметров. Так, анализируя изображение лица, в идеале мы получим контурные очертания глаз, бровей, носа, зрачков, ресниц и т.д., причем выделяются все эти элементы независимо от того, входят ли одни из них в другие. В частности, контуры глаза и зрачка считаются разными элементами, однако их сопоставление — задача более высокого уровня.
Чтобы продемонстрировать результаты работы программы, следует вывести полученные контуры в окне приложения. Критерием качества ее алгоритма будет точность соблюдения контуров и число разнотипных изображений, обработанных корректно.
Если же такая задача покажется вам слишком сложной, ограничьтесь модернизацией заготовки программы, приведенной ниже.
Инструментарий
В качестве базовой платформы мы снова предлагаем язык Java. Он на редкость лаконичен: чтобы выполнить все подготовительные операции над изображением и вывести результат, достаточно написать пару десятков строк. Поэтому можно уделить больше внимания созданию алгоритма, но сначала несколько слов о принципах работы с изображениями в Java.
Что такое Java2D
Средства работы с изображениями в Java очень тесно интегрированы в пакет awt, представляющий собой набор базовых классов для приложений, использующих графический интерфейс. Эти средства можно условно разделить на две части. Первая состоит из классов Component, Graphics и Canvas, ответственных за отрисовку изображений; вторая предоставляет множество классов в виде пакета image для манипулирования полученными картинками.
Примечательно, что класс Component является фундаментом для всей системы окон в Java, и именно на этом уровне реализованы все средства, необходимые для работы с изображениями. Следовательно, в Java любой соответствующий элемент может работать с растровой графикой.
Пакет image предоставляет программистам дополнительные возможности, позволяющие более гибко манипулировать изображениями посредством классов и интерфейсов. Так, с помощью классов ImageObserver или MediaTracker разработчик сумеет, контролируя загрузку объектов из Интернета, выполнять какие-либо операции в то время, когда загружаются запрошенные изображения. Если же вы хотите создавать графические объекты, вычисляемые в процессе работы программы, то обратитесь к классу MemoryImageSource, способному создавать изображение из одномерного массива цветовых значений. Хорошим дополнением к нему будет еще один, класс PixelGrabber. С его помощью можно извлечь все цветовые значения пикселов из картинки в массив. Таким образом, эти классы позволяют реализовать замкнутый механизм обработки изображений, поскольку выполняют прямые и обратные операции. Кроме того, разработчики Java объединили эти возможности в классе ImageFilter. С его помощью вы легко реализуете динамическое взаимодействие между фильтрами изображений и основной программой, применив принцип подключаемых внешних модулей в растровых графических редакторах. При этом вам не придется вмешиваться в работу программы.
Массивы и коллекции
В процессе выполнения задания вы будете использовать массивы и коллекции, поэтому рассмотрим их подробнее.
Массивы в Java имеют несколько интересных особенностей. Одна из них — возможность работать с элементами многомерных массивов как с отдельными массивами, другая — определять размер массива с помощью свойства length. Если массив многомерный, то таким образом можно определить размеры подмассивов, например
int[][][] a = new int[5][7][9].
Здесь объявлен и создан экземпляр трехмерного массива. Чтобы определить размерность в каждом измерении, используем следующие команды:
int s1 = a.length // s1 равняется 5 int s2 = a[0].length // s2 равняется 7 int s3 = a[0][0].length // s3 равняется 9
Аналогично массивам присваиваются новые значения. Так, чтобы присвоить первому элементу массива значения двумерного массива, сделаем следующее:
int[][] b = new int[7][9]; ... // инициализация значений массива b a[0] = b;
Кроме того, чтобы выполнить операции поиска, сортировки, автозаполнения, сравнения и т.д. над стандартными массивами, можно использовать статические методы класса Arrays. Если проводить аналогию с С++, это подобно использованию внешних, глобальных функций, выполняющих операции над своими аргументами. Правда, в Java перед вызовом метода следует указать имя класса, а создавать сам этот класс нет необходимости.
Вот так одной строкой сортируется массив:
int[] a = new int[90]; ... // Заполнение массива данными Arrays.sort(a); // Сортировка значений массива по умолчанию
Также Java обладает значительным набором классов, реализованных в пакете java.util, для работы с коллекциями объектов. К сожалению, рамки этой статьи не позволяют мне подробно остановиться на данном вопросе, однако применение коллекций в приведенной ниже программе-заготовке нуждается в некотором пояснении.
Механизм работы коллекций Java базируется на нескольких интерфейсах, в основании которых — Collection. Он определяет возможности всех коллекций с помощью таких методов, как средства проверки и очистки состояния, добавление объекта или группы, проверка на их содержание в коллекции и т.д. Расширяют Collection интерфейсы List, Set и SortedSet.
Средства для работы с последовательностями объектов определяет List. Он же вводит такое понятие, как индекс элемента, определяющий доступ к объектам коллекции. Интерфейсы Set и SortedSet совместно реализуют те же средства, за исключением того, что объект с заданным значением нельзя вставлять в коллекцию дважды.
Классы, базирующиеся на List, Set и SortedSet, наделены способностью выполнять упрощенный последовательный перебор элементов при помощи интерфейсов Iterator или ListIterator (методы next(), previous(), remove() и др.). Еще один очень важный компонент коллекций — компаратор (механизм для сравнения двух уровней), определяющий метод сортировки в коллекциях и позволяющий реализовывать различные варианты сортировки сложных объектов, например по какому-либо полю данных.
Параллельно ветви Collection в Java существует Map — ветвь классов и интерфейсов для работы с картами отображения, особенность которых заключается в реализации механизма отображения ключей в данные. Функциональность карт отображений заложена в базовых интерфейсах Map и SortedMap, которые определяют основные методы работы со значениями посредством ключей.
Хотелось бы добавить, что в Java возможен импорт-экспорт данных одного вида коллекций в другой, а также налажено взаимодействие со стандартными массивами. Следовательно, можно выбирать наиболее подходящий вид коллекций и после обработки изображения получать данные в том виде, который будет наиболее удобен для последующих манипуляций.
Через тернии - к контурам
Нимало не смущаясь, вы можете различными способами подойти к решению нашей задачи. Правда, действительно успешных реализаций практически не существует, а если и есть сколько-нибудь близкие к ним, то они, как правило, закрыты и опять имеют в чем-то ограниченные возможности. Так что дерзайте! Со своей стороны предлагаю как минимум пару вариантов для начала. В одном можно сперва обработать исходную картинку общими фильтрами, отрегулировать контрастность, насыщенность и т.д. В итоге вы получите значительно упрощенное изображение с более четкими контурами. Во втором варианте попробуйте последовательно отыскать однородные области в изображении и отследите их границы. Поработайте с каждым из этих методов, скомбинируйте первый вариант со вторым — все в ваших руках.
В этом задании, как и в первом, я решил облегчить участь конкурсантов, для чего написал программу-заготовку, — она хотя и выполняет процесс распознавания, но делает это в несколько ограниченном объеме. Теперь у вас уже есть механизм подготовки изображения к анализу и выводу полученных результатов в отдельное окно, так что приложите все свои силы к решению основной задачи.
Давайте познакомимся с идеологией моей заготовки.
Шаг 1. Я решил сделать некий циклический алгоритм, который бы последовательно, по ячейкам, анализировал все изображение. Естественно, чем меньше будет ячейка, тем большее количество итераций мы должны будем произвести, но проще окажется сам алгоритм. Правда, при таком подходе из-за его примитивности нельзя выделить «общее из частного», поэтому я предварительно масштабировал изображение до минимальных размеров. С этого мы и начнем анализ картинки, по шагам увеличивая ее детализацию. Анализ каждой ячейки будет динамическим, т. е. при анализе четырех лежащих рядом пикселов проводится сравнение их с окружающими блоками предыдущей детализации.
В данном случае каждый шаг масштабирования сохраняется в коллекции, т.е. если изначально размер изображения был 200x200 пикселов, то в коллекции последовательно запишутся массивы пикселов для блоков размером 100x100, 50x50, 25x25, 12x12, 6x6, 3x3.
Подобный подход позволяет сначала определить основные объекты в изображении, а потом постепенно детализировать их контуры.
|
| Рис.1. Пример ячейки. Цифры определяют порядок следования пикселов и блоков в алгоритмах |
Шаг 2. Теперь определим пикселы с одинаковыми цветовыми характеристиками в матрице наименьшего разрешения и скомпонуем их в отдельные блоки. Чтобы хранить информацию о координатах, контуре, цвете и т.д., я выбрал класс Form. Не забудьте при создании нового блока инициализировать его экземпляр и поместить в коллекцию Forms.
Далее можно войти в основной цикл программы, где шаги 3 и 4 будут выполняться для каждого блока пикселов.
Шаг 3. Разобьем ячейки на зоны по цвету, чтобы при сравнении внешних блоков пикселов с внутренними не выполнять эту операцию для каждого из них заново.
Таким образом мы подготовились к анализу состояния зон и принятию решения о детализации координат объекта.
Шаг 4. При анализе цветовых составляющих пикселов определяются такие показатели, как:
- идентичность (оба цвета имеют близкие параметры);
- промежуточность (проверяемый цвет попадает в область между двумя другими);
- чужеродность (цвет имеет другие характеристики).
В зависимости от результата сравнения блоков пикселов можно либо детализировать координаты объектов, либо породить новый объект, если его цветовые характеристики будут сильно отличаться от соседних.
Исходный текст
Моя программа реализована в виде аплета. Для ее запуска откройте html-страницу с текстом вставки аплета и там же передайте ему в качестве параметра имя файла изображения. Полный исходный текст этой программы, а также все данные и файлы, необходимые для начала работы, вы найдете на сайте www.javastudio.h1.ru.
Вся программа содержится в файлах Discern.java и Form.java. В первом находится основной текст программы, во втором реализован класс Form, включающий данные о контурах и методы работы с ними.
Точкой входа в программу является метод init() класса Discern, с которого мы и начнем.
public void init(){
Image img;
int pixels[];
int w1, h1;
int hist[] = new int[256];
int max_hist = 0;
ArrayList Rasters = new ArrayList();
ArrayList Fantoms = new ArrayList();
Dimension d = getSize();
int w = d.width;
int h = d.height;
try{
/* С помощью метода getImage()
извлечем ссылку на изображение
из параметра img html-страницы */
img = getImage(getDocumentBase(),
getParameter(?img?));
MediaTracker t = new MediaTracker(this);
t.addImage(img, 0);
t.waitForID(0);
/* Теперь мы считываем размеры
изображения, чтобы создать массив,
в котором сохраним цветовые
характеристики */
iw = img.getWidth(null);
ih = img.getHeight(null);
pixels = new int[iw*ih];
/* В качестве параметра передаем
конструктору объекта типа PixelGrabber
пустой массив pixels и ссылку на объект
типа Image. Затем, вызвав метод
grabPixels(), поместим значения цветов
пикселов в массив. */
PixelGrabber pg = new PixelGrabber(img,
0, 0, iw, ih, pixels, 0, iw);
pg.grabPixels();
} catch (InterruptedException e) {};Используемые здесь классы работают со стандартной цветовой моделью. В ней все характеристики пиксела сосредоточены в одном значении типа int, т. е. в 32 битах хранятся значения прозрачности пиксела, интенсивности красной, зеленой и синей составляющей, по 8 бит на каждый из компонентов. Такой формат требует побитовых операций сдвига для получения и записи данных, поэтому я реализовал два метода для конвертации массива типа int в трехмерный массив - getRGB() и setRGB(). В результате мы получили в свое распоряжение массив, где доступ к каждому пикселу можно получить, указав его позицию по ширине и высоте, а составляющие цветов находятся в отдельных значениях типа int:
int[][][] BasWorkPix = getRGB(pixels, iw, ih);
Для хранения изображений с разным разрешением я выбрал экземпляр класса ArrayList - Rasters. В него сначала помещается базовая матрица, а затем в цикле вставляются уже измененные. Для масштабирования матриц я написал метод getDivPix(), суммирующий цветовые значения ячейки из четырех пикселов и создающий из них один:
Rasters.add(getDivPix(BasWorkPix));
for(int i = 0; i < 7; i++){
Rasters.add(getDivPix((int[][][])
Rasters.get(i)));
}Теперь мы имеем все данные, необходимые для того, чтобы начать анализ изображения.
Далее я привожу код для вывода отмасштабированных изображений в удобном для чтения формате:
int it = 6; int[] EndWorkPix = setRGB((int[][][]) Rasters.get(it), ((int[][][])Rasters.get(it)).length, ((int[][][]) Rasters.get(it))[0].length); img1 = createImage(new MemoryImage Source(((int[][][])Rasters.get(it)).length, ((int[][][])Rasters.get(it))[0].length, EndWorkPix, 0, ((int[][][])Rasters.get(it)).length));
Вставим вызовы методов анализа перед закрывающей скобкой метода init():
Analiz(); }
Нам осталось лишь добавить в код аплета пару строк для определения метода paint(), который и выведет в окне изображение с нужным разрешением:
public void paint(Graphics g){
g.drawImage(img1, 0, 0, null);
}Как вы, надеюсь, уже поняли, самое интересное в этой программе — методы подготовки данных и метод analiz(). Рассмотрим их.
|
| Рис. 2. Схема разбиения окружающих блоков на зоны |
Именно analiz() служит ядром программы, так как с его помощью исследуется состояние ячейки и на базе полученных выводов либо корректируются координаты имеющегося объекта, либо создается новый. В качестве параметров метод analiz() получает массив зон, массив с номером начального и конечного пиксела зоны (рис. 2), массив из четырех анализируемых пикселов и список объектов с описанием характеристик контуров. В этом методе сравниваются цвета внутренних и соприкасающихся с зоной пикселов.
public void analiz(int[][] zones, int[] nzone,
int[][] pixels, ArrayList Forms){
for(int i = 0; i < zones.length; i++){
for(int j = (nzone[i][0]+nzone[i][0]%2)/2;
j < nzone[i][1] - (nzone[i][1]/2-1)
-nzone[i][1]%2; j++){
if(isEqual(pixels[j], zones[i], border1){
Forms.insert(pixcoord, object);
}
else{
Forms.addForm(Form.create(pixcoord, object));
}
}
}
}Метод сравнения цвета пикселов весьма важен. Суть его заключается в выяснении, насколько отличаются друг от друга цвета каждой из составляющих RGB. Если разница в цвете меньше предельной, цвет считается идентичным. Кстати, улучшение именно этого метода весьма важно для решения всей проблемы распознавания образов.
public bool isEqual(int[] color1,
int[] color2, int border1){
int r, g, b, s;
r = Math.abs(color1[0] - color2[0]);
g = Math.abs(color1[1] - color2[1]);
b = Math.abs(color1[2] - color2[2]);
if(r < border1 & g < border1
& b < border1) { return true; }
return false;
}Метод isBlend() позволяет выяснить эквивалентность цветов в том случае, когда блок состоит из пикселов с цветами примыкающих зон. Значит, с его помощью можно будет определить, является ли цвет данного пиксела промежуточным значением между двумя другими пикселами разного цвета. Здесь уже простор для вашей фантазии ничто не ограничивает.
public bool isBlend(int[] color1, int[] color2,
int[] color3, int border2){
if(color2[0] > color1[0] &
color2[0] < color3[0]){
float a = Math.abs(color3[0]/color2[0]);
float b = Math.abs(color3[1]/color2[1]);
float c = Math.abs(color3[2]/color2[2]);
if( Math.abs(a - b) < border2 &
Math.abs(a - c) < border2 ) { return true; }
}
if(color2[0] < color1[0] & color2[0]
> color3[0]){
float a = Math.abs(color1[0]/color2[0]);
float b = Math.abs(color1[1]/color2[1]);
float c = Math.abs(color1[2]/color2[2]);
if( Math.abs(a - b) < border2 &
Math.abs(a - c) < border2 ) { return true; }
}
return false;
}Следующим методом мы определяем цветовые характеристики пикселов окружения и группируем их в однотипные зоны.
public ArrayList
getZones(int[] OutArray){
ArrayList Zones = new ArrayList();
int Num;
int [] Vec = new int[8];
ArrayList Vector = new ArrayList();
int[][] eqi = new int[8][8];
for(int i; i = 0; i++){
int[] eqj = new int[8];
for(int j; j = 0; j++){
if(isEqual(OutArray[i], OutArray[j],
Border1 |
isBlend(OutArray[i], OutArray[j],
OutArray[j+1], Border1 |
isBlend(OutArray[i], OutArray[j+1],
OutArray[j], Border1){
Num+=1;
}
else {
if(Num > 0){
if(Collection.binarySearch(Zones,
Vector, Comparator c){
Vec[j-Num] = Num;
Vector.add(Vec);
Vector.add(OutArray[j-1]);
Zones.add(Vector);
}
Num = 0;
}
}
}
}
}Чтобы было удобнее обрабатывать полученные результаты, сгенерируем в методе MakeOutArray() специальные массивы, где хранятся данные о зонах.
public int[] makeOutArray(int[][] array,
int hindex, int vindex){
int[] OutArray = new int[8];
OutArray[0] = array[hindex-1][vindex-1];
OutArray[1] = array[hindex][vindex-1];
OutArray[2] = array[hindex+1][vindex-1];
OutArray[3] = array[hindex-1][vindex];
OutArray[4] = array[hindex+1][vindex];
OutArray[5] = array[hindex-1][vindex+1];
OutArray[6] = array[hindex][vindex+1];
OutArray[7] = array[hindex+1][vindex+1];
return OutArray;
}Далее приведены методы приведения пикселов изображения к более удобному формату:
public int[] setRGB(int[][][]
WorkPix, int widt, int hegh){
int[] Pix = new int[widt*hegh];
int k;
for(int i = 0; i < widt; i++){
for(int j = 0; j < hegh; j++){
k = i + j * widt;
Pix[k] = (255 << 24 |
WorkPix[i][j][0] << 16 |
WorkPix[i][j][1] << 8 |
WorkPix[i][j][2]);
}
}
return Pix;
}
public int[][][] getRGB(int[] pix,
int widt, int hegh){
int[][][] baseimg = new
int[widt][hegh][3];
int k;
for(int i = 0; i < widt; i++){
for(int j = 0; j < hegh; j++){
k = i + j * widt;
baseimg[i][j][0] = pix[k]>>16 & 0xff;
baseimg[i][j][1] = pix[k]>>8 & 0xff;
baseimg[i][j][2] = pix[k] & 0xff;
}
}
return baseimg;
}Метод getDivPix масштабирует изображение. Нужно понять принцип его работы, чтобы решить задачу сравнения цветовых характеристик пикселов.
public int[][][] getDivPix(int[][][] WorkPix){
int[][][] DivPix = new int[WorkPix.length/2]
[WorkPix[0].length/2][3];
for(int i = 0; i < DivPix.length; i++){
for(int j = 0; j < DivPix[0].length; j++){
DivPix[i][j][0] = (WorkPix[i*2][j*2][0] +
WorkPix[i*2+1][j*2+1][0] +
WorkPix[i*2+1][j*2][0] + WorkPix[i*2][j*2+1]
[0])/4;
DivPix[i][j][1] = (WorkPix[i*2][j*2][1] +
WorkPix[i*2+1][j*2+1][1] +
WorkPix[i*2+1][j*2][1] + WorkPix[i*2][j*2+1]
[1])/4;
DivPix[i][j][2] = (WorkPix[i*2][j*2][2] +
WorkPix[i*2+1][j*2+1][2] +
WorkPix[i*2+1][j*2][2] + WorkPix[i*2][j*2+1]
[2])/4;
}
}
return DivPix;
}Заключение
Здесь приведены лишь ключевые фрагменты программы. Надеюсь, они помогут вам понять, как работает приложение. На все остальные вопросы даст ответ только полный исходный текст. Желаю удачи!
Виталий Галактионов, vit3d@mail.ru
