Розроблення алгоритмів зафарбовування

Зафарбовування – це зміна кольору масиву пікселів, що знаходяться поруч і мають однаковий колір, утворюючи замкнену область. Розробляючи алгоритми зафарбовування було розроблено та реалізовано 3 різні алгоритми: зафарбовування модифікованим методом «математичної хвилі», модифікований рекурсивний метод та порядкове зафарбовування.

Алгоритм мат. хвилі показано в лістингу 2.8.1.

int x= startX;
int y= startY;
//calculate mask
fillerArea.reset();
fillerArea.add(x, y, 0);
fillerArea.check(width, height);
mask [x][y]=1;
int start_color;
start_color = bitmap. getPixel(x,y);
bitmap. setPixel(x, y, color);
int added=0;
int counter=0;
while (cont){
//ride across the image
boolean condition=counter%2==0;
for (int cy = condition? fillerArea. top: fillerArea. bottom -1;
(condition? cy<fillerArea. bottom: cy>fillerArea. top) && cont; cy+= condition? 1: -1) {
for (int cx = condition? fillerArea. left: fillerArea. right -1;
(condition? cx<fillerArea. right: cx>fillerArea. left) && cont;
cx+= condition? 1: -1) {
if (mask [cx][cy]==1) { //detected
fillerArea.add(cx, cy, 0);
fillerArea.check(width, height);
if (cx-1 >= 0){ //valid pixel
if (mask [cx-1][cy]==0){ //empty space
synchronized (bitmap){
if (bitmap. getPixel(cx-1, cy) == start_color){ //valid color
mask [cx-1][cy]=1;
bitmap. setPixel(cx-1, cy, color);
added++;
}
}
}
}
if (cx+1 < width) { //valid pixel
if (mask [cx+1][cy]==0) { //empty space
synchronized (bitmap){
if (bitmap. getPixel(cx+1, cy) == start_color){ //valid color
mask [cx+1][cy]=1;
bitmap. setPixel(cx+1, cy, color);
added++;
}
}
}
}
if (cy-1 >= 0){
if (mask [cx][cy-1]==0) {
synchronized (bitmap){
if (bitmap. getPixel(cx, cy-1) == start_color) {
mask [cx][cy-1]=1;
bitmap. setPixel(cx, cy-1, color);
added++;
}
}
}
}
if (cy+1 < height) {
if (mask [cx][cy+1]==0) {
synchronized (bitmap){
if (bitmap. getPixel(cx, cy+1) == start_color) {
mask [cx][cy+1]=1;
bitmap. setPixel(cx, cy+1, color);
added++;
}
}
}
}
mask [cx][cy]=2;
}
}
}
counter++;
//stop if needed
if (added == 0)
cont = false;
added=0;
}

Лістинг 2.8.1 Алгоритм зафарбовування «математичною хвилею»

Для малюнка створюється бінарна маска, яка відображає область, яка має бути зафарбована. Суть алгоритму полягає в тому, що виконується певна кількість ітерацій на яких алгоритм шукає зони що мають бути зафарбованими та перевіряє на предмет необхідності зафарбовування сусідні пікселі. Якщо їх треба зафарбувати, вони помічаються для зафарбовування. Таким чином на наступній ітерації всі наступні сусідні пікселі також будуть перевірені на необхідність зафарбовування. Зупинити пошук варто тоді, коли на якійсь із ітерації для зафарбування не було помічено жодного пікселя. Далі задача просто зафарбувати новим кольором область, що помічена для фарбування.

Суть модифікації даного алгоритма полягає у тому, що напрямок руху циклу зафарбовування змінюється з кожною наступною ітерацією. Це доцільно тому, що під час кожного проходу зафарбовуються усі пікселі від вже помічених в напрямку руху циклу. Таким чином кількість ітерацій зафарбовування можна скоротити в багато разів. Зразок роботи алгоритма можна побачити на рисунку 2.8.1.

Рис. 2.8.1 Робота алгоритму зафарбовування «мат. хвиля»

Модифікований рекурсивний метод представлено в лістингу 2.8.2.

int x= startX;
int y= startY;
start_color = bitmap. getPixel(x,y);
int cx; //current position
int cy;
int counter = 0;
queue. add(new IntPoint(x,y));
while (! queue. isEmpty() && cont){
IntPoint cur = queue. poll();
synchronized (bitmap){
bitmap. setPixel(cur. x, cur. y, color);
cx = cur. x +1;
cy = cur. y;
if (cur. x < width -1 &&! queued [cx][cy] && check(start_color, bitmap. getPixel(cx, cy))){
queue. add(new IntPoint(cx, cy));
queued [cx][cy] = true;
}
cx = cur. x;
cy = cur. y +1;
if (cur. y < height -1 &&! queued [cx][cy] && check(start_color, bitmap. getPixel(cx, cy))){
queue. add(new IntPoint(cx, cy));
queued [cx][cy]= true;
}
cx = cur. x -1;
cy = cur. y;
if (cur. x > 0 &&! queued [cx][cy] && check(start_color, bitmap. getPixel(cx, cy))){
queue. add(new IntPoint(cx, cy));
queued [cx][cy]= true;
}
cx = cur. x;
cy = cur. y -1;
if (cur. y > 0 &&! queued [cx][cy] && check(start_color, bitmap. getPixel(cx, cy))){
queue. add(new IntPoint(cx, cy));
queued [cx][cy]= true;
}
counter++;
}
}

Лістинг 2.8.2 Модифікований рекурсивний алгоритм зафарбовування

Суть рекурсивного алгоритму зафарбовування полягає у тому, що в момент визначення точки початку зафарбовування викликається функція, яка зафарбовує цей піксель та перевіряє сусідні пікселі на відповідність кольору. Якщо вони такого ж кольору, функція викликає сама себе для кожного з таких пікселів. Алгоритм закінчиться сам тоді, коли жодна з викликаних функцій не викличе себе сама, тобто тоді, коли більше не буде чого зафарбовувати.

Головною проблемою цього алгоритму є переповнення стеку викликів при досить великих малюнках. Саме тому алгоритм був модифікований для використання внутрішньої черги. Коли функція знаходить піксель, що підлягає зафарбовуванню, вона вносить його в чергу, яку потім обробляє. Обробляючи чергу, шукаються все нові і нові пікселі, які також вносяться в чергу. Алгоритм закінчується тоді, коли черга закінчується. Результат роботи алгоритма при використанні черги можна бачити на рис. 2.8.2, а при використанні стеку – на рис. 2.8.3.

Рис. 2.8.2 Демонстрація роботи модифікованого рекурсивного алгоритма зафарбовування з використанням черги

Рис. 2.8.3 Демонстрація роботи модифікованого рекурсивного алгоритма зафарбовування з використанням стеку

Алгоритм зафарбовування по рядкам показано в лістингу 2.8.3.

int x=(int)((Point)params[0]). x;
int y=(int)((Point)params[0]). y;
start_color = bitmap. getPixel(x,y);
set(x, y);
queue. add(y);
int counter = 0;
while (! queue. isEmpty() && cont){
int cur = queue. poll();
step(cur);
counter ++;
} void set(int x, int y){
synchronized (bitmap){
bitmap. setPixel(x, y, color);
}
mask [x][y] = true;
} void step(int y){
for (int x = width -1; x > 0; x--){
if (mask [x][y]){
if (valid(x - 1, y)){
set(x - 1, y);
}
}
}
boolean validUp = false;
boolean validDown = false;
for (int x=0; x < width -1; x++){
if (mask [x][y]){
if (valid(x + 1, y)){
set(x+1, y);
}

if (y < height -1 && valid(x, y + 1)){
set(x, y+1);
if (!validDown){
queue. add(y+1);
validDown = true;
}
}

if (y > 1 && valid(x, y - 1)){
set(x, y - 1);
if (!validUp){
queue. add(y - 1);
validUp = true;
}
}
}
}
}

Лістинг 2.8.3. Алгоритм зафарбовування по рядкам

Даний алгоритм, як і попередній, має в собі в основі чергу, але таку, яка зберігає не пікселі, а рядки. Потрапляючи на рядок, функція заповнює його по горизонталі, та водночас шукає рядки для зафарбовування вище та нижче себе. Якщо знаходить, додає їх до черги. Роботу даного алгоритму можна бачити на рис. 2.8.4.

Рис. 2.8.4 Демонстрація роботи алгоритму зафарбовування по рядках

Дата добавления: 2015-08-09