Приклад реалізації методів обробки і розпізнавання зображень на Android

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

Існує багато статей про розпізнаванні тексту, про комп'ютерному зорі і про окремих алгоритмах розпізнавання. У цій же публікації демонструється спроба реалізації завдання, пов'язаного з перебуванням ключового слова на зображенні тексту, що може дозволити, наприклад, знайти необхідне місце для читання будь-якого тексту DjVu без розпізнавання самого тексту.

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

Завдання

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

Детально етапи створення Android програми тут описані не будуть, як і не буде представлено докладний теоретичний опис алгоритмів. При мінімальному тестовому інтерфейсі додатка основними цілями нижчеописаного є:

  • Ознайомлення з деякими методами обробки зображень та розпізнавання образів;
  • Ознайомлення з можливостями та складністю реалізації цих методів для Android.

Отримання зображення

Для отримання досліджуваного зображення створюємо Activity, в якій буде всього три елементи:

1. EditText — для введення ключового слова;
2. TextView — для відображення тексту, в якому необхідно знайти це слово;
3. Кнопка створення скріншота і переходу на інший екран.

! Весь код носить виключно демонстративний характер і не є правильною інструкцією до дії.

XML код для 1 і 2 пунктів
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/main_content_layout"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:background="#ddd"
android:orientation="vertical"
android:paddingBottom="@dimen/activity_vertical_margin"
android:paddingLeft="@dimen/activity_horizontal_margin"
android:paddingRight="@dimen/activity_horizontal_margin"
android:paddingTop="@dimen/activity_vertical_margin"
app:layout_behavior="@string/appbar_scrolling_view_behavior"
tools:context=".MainActivity"
tools:showIn="@layout/activity_main">

<EditText
android:layout_width="fill_parent"
android:layout_height="40dp"
android:singleLine="true"
android:textColor="#000" />

<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="@string/main_text"
android:textColor="#000"
android:ellipsize="end"/>
</LinearLayout>


Layout з кнопкою, який містить посилання на вищенаведений layout
<?xml version="1.0" encoding="utf-8"?>
<android.support.design.widget.CoordinatorLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:fitsSystemWindows="true"
tools:context=".MainActivity">

<android.support.design.widget.AppBarLayout
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:theme="@style/AppTheme.AppBarOverlay">

<android.support.v7.widget.Toolbar
android:id="@+id/toolbar"
android:layout_width="match_parent"
android:layout_height="?attr/actionBarSize"
android:background="?attr/colorPrimary"
app:popupTheme="@style/AppTheme.PopupOverlay" />

</android.support.design.widget.AppBarLayout>

<include layout="@layout/content_main" />

<android.support.design.widget.FloatingActionButton
android:id="@+id/fab"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_gravity="bottom|end"
android:layout_margin="@dimen/fab_margin"
android:src="@android:drawable/ic_menu_camera" />

</android.support.design.widget.CoordinatorLayout>


Приблизно так це буде виглядати:



Для пошуку, наприклад, введемо слово «dreams»:



Таким чином ми отримуємо одиночне ключове слово, після якого нижче текст. Варто звернути увагу на те, що ключове слово і текст мають різний розмір шрифту (для ускладнення завдання, скажімо так).

Натискаємо на кнопку і отримуємо скріншот області з ключовим словом і текстом.

Метод для отримання скріншота, що викликається по натисненню на кнопку
private void takeScreenshot() {
//Для унікальності файлів використовується поточний час
Date now = new Date();
//Форматування дати/часу за зразком
android.text.format.DateFormat.format("yyyy-MM-dd_hh:mm:ss", now);

try {
//Отримання шляхи для збереження зображень і готуємо файл
String path = Environment.getExternalStorageDirectory().toString() + "/" + now + ".jpg";
File imageFile = new File(path);

//Знаходження частини layout'a, в якій знаходиться ключове слово і текст
View v1 = findViewById(R. id.main_content_layout);

//Отримання зображення
v1.setDrawingCacheEnabled(true);
Bitmap bitmap = Bitmap.createBitmap(v1.getDrawingCache());
v1.setDrawingCacheEnabled(false);

//Збереження зображення у файл
FileOutputStream outputStream = new FileOutputStream(imageFile);
int quality = 100;
bitmap.compress(Bitmap.CompressFormat.PNG, quality, outputStream);
outputStream.flush();
outputStream.close();

//Перехід до наступного Activity
openScreenshotActivity(now);
} catch (Throwable e) {
e.printStackTrace();
}
}


Отриманий скріншот відкривається в новій Activity, де в NavigationDrawer зібрані функції послідовних дій. В реальному додатку деякі з операцій можуть бути об'єднані в одну для виключення зайвих проходів по зображенню.

Попередня обробка отриманого зображення

Для початку потрібно виконати переклад отриманого кольорового зображення в чорно-біле.

Переклад зображення з кольорового в чорно-біле
Для перекладу використовується схема RGB to YUV.

У нашому випадку необхідна лише інтенсивність (яскравість), а отримати її можна за форумуле:

Y = 0.299*R + 0.587*G + 0.114*B, де R,G,B червоний, зелений і синій канали відповідно.

Для роботи з кольорами, як не дивно, корисний клас Color і, зокрема, його статичні методи red, green і blue, в яких реалізовані операції з побитовыми зрушеннями для виділення потрібного колірного каналу з интового значення кольору пікселя.

Приклад коду, для перекладу кольорового пікселя у яскравість:

//Цикл обходу матриці кольорових пікселів pixels (size = кількість пікселів = width*height зображення)
for (int i = 0; i < size; i++) {
int color = pixels[i];

//отримуємо значення червоного каналу
int r = Color.red(color);

//отримуємо значення зеленого каналу
int g = Color.green(color);

//отримуємо значення синього каналу
int b = Color.blue(color);

//обчислюємо полутоновую яскравість за формулою переходу RGB to YUV
double luminance = (0.299 * r + 0.0 f + 0.587 * g + 0.0 f + 0.114 * b + 0.0 f);
}

Виконувати сегментацію на напівтоновому зображенні не на багато легше, ніж на кольоровому, тому наступним кроком необхідно півтонове зображення перевести в бінарне значення яскравостей пікселів мають лише два значення 0 і 1).

Бінаризація напівтонового зображення
В даній задачі для бінаризації досить елементарного порогового методу, з порогом за замовчуванням 128.

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

Для отримання бінарного значення яскравості виконується перевірка отриманої раніше напівтонові яскравості:

pixels[i] = luminance > threshold ? Color.WHITE : Color.BLACK;

Де threshold — поріг, Color.WHITE і Color.BLACK — константи для зручності, щоб не плутатися з 0 і 1.

Після зробленого перекладу в півтонове і подальшої бінаризації отримуємо наступний результат:



Так як ці два способи обробки зображення дуже близькі, вони об'єднані в один метод.

Приклад методу, що здійснює переклад в півтонове і бінаризацію зображення
/**
* imagePath - шлях до зображення
* threshold - поріг бінаризації
*/
public void binarizeByThreshold(String imagePath, int threshold) {
//Відкриваємо зображення на його шляху
Bitmap bitmap = BitmapFactory.decodeFile(imagePath);

//Отримуємо розміри зображення
int width = bitmap.getWidth();
int height = bitmap.getHeight();
int size = width * height;

//Отримуємо матрицю пікселів зображення
int[] pixels = new int[size];
bitmap.getPixels(pixels, 0, width, 0, 0, width, height);
bitmap.recycle();

//Проходимо по всіх пікселям в матриці, виконуючи переклад в півтонове зображення і бінаризацію по порогу
for (int i = 0; i < size; i++) {
int color = pixels[i];
int r = Color.red(color);
int g = Color.green(color);
int b = Color.blue(color);
double luminance = (0.299 * r + 0.0 f + 0.587 * g + 0.0 f + 0.114 * b + 0.0 f);
pixels[i] = luminance > threshold ? Color.WHITE : Color.BLACK;
}

Utils.saveBitmap(imagePath, width, height, pixels);
}


Сегментація

Для знаходження ключового слова необхідно після бінаризації виконати кілька етапів сегментації, які полягають у пошуку рядків у тексті, пошуку слів у рядках і віднесення знайдених слів до слів претендентам за кількістю букв (для звуження кола слів для розпізнавання).

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

«Inline» гістограма для наочності (ліворуч) виглядає, наприклад, так:



Метод для отримання гістограми рядків
public ArrayList<GystMember> getRowsGystogram(String imagePath) {
//Відкриття зображення, отримання його розмірів і матриці пікселів
Bitmap bitmap = BitmapFactory.decodeFile(imagePath);
int width = bitmap.getWidth();
int height = bitmap.getHeight();
int size = width * height;
int[] pixels = new int[size];
bitmap.getPixels(pixels, 0, width, 0, 0, width, height);
bitmap.recycle();

ArrayList<GystMember> gystogram = new ArrayList<>();

//Отримання гістограми
for (int x = 0; x < height; x++) {
gystogram.add(new GystMember(x));
for (int y = 0; y < width; y++) {
int color = pixels[y + x * width];
if (color == Color.BLACK) {
gystogram.get(x).add();
}
}
}
return gystogram;
}

/*Клас, який тут і в подальшому використовується для зручності складання гістограм у вигляді колекції*/
public class GystMember implements Serializable {
public int grayValue;
public int count;

public GystMember(int grayValue) {
this.grayValue = grayValue;
this.count = 0;
}

public void add() {
count++;
}
}



Для зручності відображення гістограми нормалізується.

Приклад нормалізації гістограми в onDraw кастомних View
if (mGystogram != null) {
float max = Integer.MIN_VALUE;
for (GystMember gystMember : mGystogram) {
if (gystMember.count > max) {
max = gystMember.count;
}
}
int pixelSize = getWidth();
int coef = (int) (max / pixelSize);
if (coef == 0){
coef = 1;
}
int y = 0;
for (GystMember gystMember : mGystogram) {
int value = gystMember.count;
canvas.drawLine(0, y, value / coef, y, mPaint);
y++;
}
}


Коли відомо розташування рядків на зображенні, можна переходити до пошуку слів.

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

Для початку як і для рядків, аналогічним чином будуємо гістограму всередині рядка (по суті була вертикальна, тепер горизонтальна), вона необхідна, щоб зрозуміти, де символи, а де білі проміжки.

Приклад отримання такої гістограми нижче і аналогічний попередньому.

Обробляючи цю гістограму можна отримати нову гістограму — проміжків між чорними пікселями, тобто, перша градація її буде кількістю «прогалин» шириною 1 піксель, друга градація кількість «прогалин» шириною 2 пікселя і так далі.

Приклад отримання гістограми проміжків
public ArrayList<GystMember> getSpacesInRowsGystogram(String imagePath, ArrayList<GystMember> rowsGystogram) {
//Завантаження зображення, отримання його розмірів і матриці пікселів
Bitmap bitmap = BitmapFactory.decodeFile(imagePath);
int width = bitmap.getWidth();
int height = bitmap.getHeight();
int size = width * height;
int[] pixels = new int[size];
bitmap.getPixels(pixels, 0, width, 0, 0, width, height);
bitmap.recycle();

//Для гістограми використовується той же GystMember, тільки трохи змінювати суть параметрів.
ArrayList<GystMember> oneRowGystogram = new ArrayList<>();
ArrayList<Integer> spaces = new ArrayList<>();
ArrayList<GystMember> spacesInRowsGystogram = new ArrayList<>();

int yStart = 0, yEnd = 0, yIter = -1;
boolean inLine = false;

//Послідовний обхід рядків
for (GystMember gystMember : rowsGystogram) {
yIter++;

//Якщо зустрічаємо чорні пікселі (мається на увазі в гістограмі), то "починаємо рядок"
if (gystMember.count > 0 && !inLine) {
inLine = true;
yStart = yIter;
} else if (gystMember.count == 0 && inLine) { //Коли зустрічаємо порожню градацію (немає чорних пікселів), "закінчуємо рядок"
inLine = false;
yEnd = yIter;

//Будуємо гістограму усередині рядка, аналогічно гістограмі рядків
for (int x = 0; x < width; x++) {
GystMember member = new GystMember(x);
for (int y = yStart; y < yEnd; y++) {
int color = pixels[x + y * width];
if (color == Color.BLACK) {
member.add();
}
}
oneRowGystogram.add(member);
}

int xStart = 0, xEnd = 0, xIter = -1;
boolean inRow = false;

//Горизонтальний обхід одного рядка
for (GystMember oneRowMember : oneRowGystogram) {
xIter++;

//Пошук символів аналогічний пошуку рядків
if (oneRowMember.count == 0 && !inRow) {
inRow = true;
xStart = xIter;
} else if ((oneRowMember.count > 0 || xIter == oneRowGystogram.size()-1) && inRow) {
inRow = false;
xEnd = xIter;

//Обчислюємо кількість пікселів між сусідніми символами і додаємо в список проміжків
int xValue = xEnd - xStart;
spaces.add(xValue);
}
}
}
}

//Сортуємо проміжки і збираємо гістограму проміжків
Collections.sort(spaces);
int lastSpace = -1;
GystMember gystMember = null;
for (Integer space : spaces) {
if (space > lastSpace) {
if (gystMember != null) {
spacesInRowsGystogram.add(gystMember);
}
gystMember = new GystMember(space);
}
gystMember.add();
lastSpace = space;
}

return spacesInRowsGystogram;
}


Вийде приблизно щось таке:



Виходячи з логіки методу мод ми знаходимо два яскраво виражених піку (на зображенні вище вони очевидні), і все що знаходиться близько одного піку — відстані між символами всередині слова, біля другого — відстані між словами.

Маючи таку інформацію про «прогалини» та гістограму рядка можна виділити ділянки зображення, де знаходяться слова, а також порахувати скільки символів міститься в цих словах.

Повний код даного процесу дивись в исходниках.

Для візуальної оцінки роботи вищевикладеної сукупності алгоритмів слова в тексті забарвлюються в чередующееся кольору, а слова претенденти (нагадаю, ті, у яких кількість символів збігається з кількістю символом в ключовому слові) залишаються чорного кольору:



І так, на даному етапі є шматочки зображень (точніше координати цих шматочків), які містять ключове слово і слова претенденти на підставі кількості символів, можна спробувати знайти серед претендентів ключове слово.

Розпізнавання

Звертаю увагу, що тут під розпізнаванням мається на увазі розпізнавання ключового слова серед претендентів, при цьому про розпізнаванні з яких саме символів вони складаються мови не йде.

Для розпізнавання підбирається набір інформативних ознак: це може бути кількість кінцевих точок, вузлових точок, а також кількість пікселів з 3, 4 і 5 чорними пікселями-сусідами, та інші. Дослідним шляхом встановлено, що велика кількість ознак втрачає сенс, так як вони «перекривають» один одного.

На даному етапі зупинимося на кількості кінцевих точок, з урахуванням їх розташування (у верхній і нижній частині зображення — для кожної частини ознаки вважаються окремо).

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

Приклад формування структури з підрахованими ознаками
private void generateRecognizeMembers() {
mRecognizeMembers.clear();
for (PartImageMember pretendent : mPretendents) {
RecognizeMember recognizeMember = new RecognizeMember(pretendent);

int pretendentWidth = pretendent.endX - pretendent.startX;
int pretendentHeight = pretendent.endY - pretendent.startY;
int[][] workPixels = new int[pretendentWidth][pretendentHeight];

//Отримання матриці претендента з великої матриці всього зображення
for (int pY = pretendent.startY, py1 = 0; pY < pretendent.endY; pY++, py1++)
for (int pX = pretendent.startX, px1 = 0; pX < pretendent.endX; pX++, px1++) {
workPixels[px1][py1] = mImagePixels[pX + pY * mImageWidth];
}

int half = pretendentHeight / 2;
//Обхід згори вниз
for (int ly = 0; ly < pretendentHeight; ly++) {
//Обхід зліва направо
for (int lx = 0; lx < pretendentWidth; lx++) {
int currentColor = workPixels[lx][ly];

//При обчисленні характерних чисел нас цікавлять тільки пікселі об'єкта.
if (currentColor != Color.WHITE) {
//Заповнення матриці 3х3 сусідів кожного пікселя
int[][] pixelNeibours = Utils.fill3x3Matrix(pretendentWidth, pretendentHeight, workPixels, ly, lx);
int[] pixelsLine = Utils.getLineFromMatrixByCircle(pixelNeibours); 

//Підрахунок характерних чисел для визначення того, чи є піксель кінцевим
int A4 = getA4(pixelsLine);
int A8 = getA8(pixelsLine);
int B8 = getB8(pixelsLine);
int C8 = getC8(pixelsLine);
int Nc4 = A4 - C8;
int CN = A8 - B8;

recognizeMember.A4.add(A4);
recognizeMember.A8.add(A8);
recognizeMember.Cn.add(CN);

//При виконанні цих умов піксель вважається кінцевим
if (A8 == 1 && Nc4 == 1 && CN == 1) {
if (ly < half) {
recognizeMember.endsCount++;
} else {
recognizeMember.endsCount2++;
}
}
}
}
}
mRecognizeMembers.add(recognizeMember);
}
}

private int getA4(int[] pixelsLine) {
int result = 0;
for (int k = 1; k < 5; k++) {
result += pixelsLine[2 * k - 2];
}
return result;
}

private int getA8(int[] pixelsLine) {
int result = 0;
for (int k = 1; k < 9; k++) {
result += pixelsLine[k - 1];
}
return result;
}

private int getB8(int[] pixelsLine) {
int result = 0;
for (int k = 1; k < 9; k++) {
result += pixelsLine[k - 1] * pixelsLine[k];
}
return result;
}

private int getC8(int[] pixelsLine) {
int result = 0;
for (int k = 1; k < 5; k++) {
result += pixelsLine[2 * k - 2] * pixelsLine[2 * k - 1] * pixelsLine[2 * k];
}
return result;
}


Про всіх характерних числах типу A4, A8 і т. д. можна знайти інформацію додатково.

Код безпосередньо розпізнавання на основі евклідової відстані
private void recognize() {
//Підрахунок характерних чисел (описано вище)
generateRecognizeMembers();

mResultPartImageMembers.clear();
ArrayList<Double> keys = new ArrayList<>();

//Складання на підставі результатів відстаней
RecognizeMember firstMember = mRecognizeMembers.get(0);
mRecognizeMembers.remove(firstMember);
for (RecognizeMember recognizeMember : mRecognizeMembers) {
if (recognizeMember.getPretendent() != firstMember.getPretendent()) {
double keyR = firstMember.equalsR(recognizeMember);
recognizeMember.R = keyR;
keys.add(keyR);
}
}

//Сортування отриманих результатів
Collections.sort(mRecognizeMembers, new Comparator<RecognizeMember>() {
@Override
public int compare(RecognizeMember lhs, RecognizeMember rhs) {
return (int) Math.round(lhs.R - rhs.R);
}
});

//Приведення результатів до виду відповіді, враховуючи повторюваність (всі повтори включаються) і два перших сусіда
double firstKey = -1;
double secondKey = -1;
for (RecognizeMember member : mRecognizeMembers) {
double key = member.R;
if (firstKey == -1) {
firstKey = key;
mResultPartImageMembers.add(member.getPretendent());
} else if (key == firstKey) {
mResultPartImageMembers.add(member.getPretendent());
} else if (secondKey == -1) {
secondKey = key;
mResultPartImageMembers.add(member.getPretendent());
} else if (secondKey == key) {
mResultPartImageMembers.add(member.getPretendent());
}
}
}

<...>
//Обчислення евклідова відстань для кількості кінцевих точок у верхній і нижній(2) частини зображення
public double equalsR(RecognizeMember o) {
return Math.sqrt(Math.pow(this.endsCount - o.endsCount, 2)
+ Math.pow(this.endsCount2 - o.endsCount2, 2));
}
<...>


Враховуючи повторюваність слів і похибки, в результаті можна отримати 2-3 найближчих сусіда, серед яких буде знайдено ключове слово (на малюнку виділено червоним).



Також на малюнку видно, що серед червоних слів є шукане слово «dreams».

Для поліпшення якості розпізнавання можна спробувати підібрати інший поріг бінаризації, а також вибрати інші інформативні ознаки, додавши до них, наприклад, зонди.

Висновок

Поставлених цілей вдалося досягти, були випробувані деякі методи обробки і розпізнавання зображень, при цьому їх реалізація під Android не накладає ніяких додаткових складнощів, просто потрібно враховувати витрату пам'яті і не зберігати одночасно кілька великих Bitmap.

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

Опис усіх використовуваних алгоритмів, підрахунок характерних чисел і т. п. можна з легкістю знайти у відкритому доступі як на habrahabr, так і в численних підручниках і онлайн ресурсах.

Повністю проект доступний на GitHub

P. S.: Наведена реалізація алгоритмів не оптимальна, і потребує подальшого опрацювання і оптимізації, служить лише мінімально необхідним прикладом для ознайомлення, візуалізації та оцінки роботи вищеописаних методів на Android.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.