PHP OCR - Ein simpler Weg zur Texterkennung

FragSalat
28. Dezember 2013
0 Kommentare
9.677 Mal gelesen

In diesem Artikel möchte ich euch einen Weg aufzeigen wie man ein simples PHP OCR Script entwickeln kann. OCR (Optical Character Recognition) heißt das man mit einem Algorithmus verschiedene Muster, zumeist Texte, in einem Dokument wie einem Bild oder PDF erkennt. Dieses PHP OCR Script ist eine sehr simple Methode und weißt in dieser Version eine hohe Fehlerquote bei der Erkennung auf.

Der Berg namens OCR

Genau wie beim Besteigen eines Berges trifft man bei der Entwicklung eines PHP OCR Scriptes auf viele Probleme, welche oft nicht so leicht zu lösen sind.

Ein paar dieser Probleme sind das Filtern der Charaktere aus dem Dokument, das erkennen des gefilterten Charakters, die Lernfähigkeit des PHP OCR Scriptes und vieles mehr.

Beim Filtern der Charaktere sind vor allem Rotation, Verzerrung und Farbwechsel problematisch.

Dieses PHP OCR Script behandelt lediglich das erkennen von einfachen Charakteren welche ohne Rotation, Verzerrung und vielen Farbwechseln dargestellt werden.

Der Weg zum Ziel

Es gibt viele Wege ein PHP OCR Script zu entwickeln.

Manche davon führen über Eigenvektoren und erfordern sehr gute Kenntnisse im Umgang mit Linearer Algebra.

Wir bedienen uns in diesem PHP OCR Script einfacher Logik und Schleifen um die Charaktere zu filtern und zu erkennen.

Funktion zum ermitteln und vergleichen von Farbwerten

PHP

/**
* Retrieve the rgba value from 1 pixel
*
* @param Resource $image The image resource
* @param Integer $x The x coordinate of the Pixel
* @param Integer $y The y coordinate of the Pixel
* @return Integer The color index
*/
function getColor($image, $x, $y) {
$color = imagecolorat($image, $x, $y);
return imagecolorsforindex($image, $color);
}
/**
* Helper function to comapre if two colors matches with a range
*
* @param Array<Integer> $color1 Rgba values of color
* @param Array<Integer> $color1 Rgba values of color
* @param Integer The range the colors can differ
* @return Boolean True if the colors matches
*/
function compareColor($color1, $color2, $range = 20) {
// Check if the parameters fulfill the requirements
if (empty($color1) || empty($color2)) {
return false;
}
// Check if the color1 is greater or equal to the color2
if ($color1['red'] >= ($color2['red'] + $range) &&
$color1['green'] >= ($color2['green'] + $range) &&
$color1['blue'] >= ($color2['blue'] + $range) &&
$color1['alpha'] >= ($color2['alpha'] + $range))
{
return false;
}
// Check if the color1 is less or equal to the color2
else if ($color1['red'] <= ($color2['red'] - $range) &&
$color1['green'] <= ($color2['green'] - $range) &&
$color1['blue'] <= ($color2['blue'] - $range) &&
$color1['alpha'] <= ($color2['alpha'] - $range))
{
return false;
}
else {
return true;
}
}

Alles anzeigen

Klassen zum festhalten der Koordinaten

PHP

/**
* Helper class to store x y Koordinates
*/
class Point {
public $x = null;
public $y = null;
public function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
}
/**
* Class to handle multiple points
*/
class Matrix {
public $points = [];
public $width = 0;
public $height = 0;
public $paddingLeft = 0;
public $paddingTop = 0;
/**
* Add a point object to the matrix
*
* @param Point $point
*/
public function add(Point $p) {
$this->points[] = $p;
// If the point exceed the current width increase the width
if ($p->x > $this->width) {
$this->width = $p->x;
}
// If the point exceed the current height increase the height
if ($p->y > $this->height) {
$this->height = $p->y;
}
}
/**
* Delete all points on a x coordinate
*
* @param Integer $x
*/
public function deleteColumn($x) {
foreach ($this->points as $index => $point) {
if ($point->x == $x)
unset($this->points[$index]);
}
}
/**
* Get the matrix without whitespace
*
* @return Matrix A new Matrix object
*/
public function getCleanMatrix() {
// Get the top and left padding to skip whitespace
$paddingTop = $this->getMinValue($this->points, 'y');
$paddingLeft = $this->getMinValue($this->points, 'x');
$points = [];
$width = $this->width - $paddingLeft;
$height = $this->height - $paddingTop;
// Update the x and y coordinates with the missing whitespace
foreach ($this->points as $point) {
$point->x -= $paddingLeft;
$point->y -= $paddingTop;
$points[] = $point;
}
// Create a matrix without whitespace :)
$matrix = new Matrix();
$matrix->width = $width;
$matrix->height = $height;
$matrix->paddingTop = $paddingTop;
$matrix->paddingLeft = $paddingLeft;
$matrix->points = $points;
return $matrix;
}
/**
* Helper function to get the minimum value of a property
*
* @param Array<Object> $array Objects to get the in value from
* @param String $property The property name on the objects
* @return Integer The minimum value
*/
private function getMinValue(array $array, $property) {
$min = 0;
foreach ($array as $element) {
if ($element->{$property} < $min || !$min)
$min = $element->{$property};
}
return $min;
}
}

Alles anzeigen

Charaktererkennung

Wir iterieren nun über die X und Y Achse, vergleichen den aktuellen Pixel mit den umliegenden Pixeln und erkennen, anhand der Unterschiede in den Farbwerten der Pixel, die Kanten der Charaktere.

Gehen wir davon aus das Kantenglättung genutzt wurde so müssen wir mittels compareColor() prüfen ob ein Farbwert mit Abweichung die Zielfarbe trifft.

Wenn ein Pixel sich vom Hintergrund unterscheidet gehen wir erst mal davon aus dass dieser zu einem Charakter gehören kann.

Um nur die Kanten eines Charakters zu vergleichen, prüfen wir ob der aktuelle Pixel sich zu den umliegenden Pixeln unterscheidet.

Wenn das zutrifft fügen wir die Koordinaten des Pixels in eine Matrix ein.

Wir erkennen ob das Ende eines Charakters erreicht ist, in dem wir die Streuung der Pixel auf der Vertikalen Y Achse überprüfen.

Dafür Summieren wir alle Farbwerte der Pixel auf dieser Achse und teilen diesen Wert durch die Höhe des Bildes.

Ist die Abweichung dieses Wertes kleiner als 0.7% des Farbwertes vom Hintergrund, so gehen wir davon aus dass wir das Ende eines Charakters erreicht haben.

Diese Methode sorgt dafür das sich Charaktere geringfügig überschneiden dürfen.

Somit erkennt das PHP OCR Script z.B. auch die Charaktere F und A (FA) welche sich auf der Y Achse überlagern.

Pixel der Charaktere in Matrizen einteilen

Matrix Vergleich

Nun haben wir die Pixel der Charaktere in Matrizen zerlegt.

Jetzt folgt das zuordnen der Charakter Matrizen zu den Werten.

Dafür vergleichen wir unsere Matrizen mit vordefinierten Matrizen.

Diese Matrizen stellen die Punkte auf den X und Y Achsen der Pixel unseres Musters dar und haben unterschiedlich hohe Werte auf den für sie passenden Koordinaten.

Matrix für den Buchstaben B

PHP

'B' => [
'pointAmount' => 1066,
'totalPoints' => 6313,
'matrix' => [
[0,1,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,1,0,0,0,0,0,0,0,0,0,],
[1,3,4,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,5,5,5,4,3,2,2,0,0,0,0,0,0,0,],
[2,4,6,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,7,6,5,4,2,1,0,0,0,0,0,],
[2,4,7,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,8,8,8,8,7,6,4,3,1,0,0,0,0,],
[2,4,7,8,9,9,9,9,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,8,8,6,5,3,1,0,0,0,],
[2,4,7,8,9,9,8,7,7,6,6,6,6,6,6,6,6,6,6,6,7,7,7,8,9,9,9,8,7,5,3,0,0,0,],
[2,4,7,8,9,9,7,6,4,3,3,3,3,3,3,3,3,3,3,3,4,5,5,6,7,8,9,9,8,6,4,2,0,0,],
[2,4,7,8,9,8,7,5,3,1,0,0,0,0,0,0,0,0,1,1,2,2,3,4,6,7,8,9,9,7,5,3,0,0,],
[2,4,7,8,9,8,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,4,6,8,9,9,8,6,4,2,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,5,7,8,9,8,7,5,2,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,6,8,9,9,7,5,3,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,6,8,9,9,8,6,3,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,8,9,9,8,6,3,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,6,8,9,9,8,5,3,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,6,8,9,8,7,5,2,0,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,7,8,9,8,6,4,2,0,],
[2,4,7,8,9,8,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,6,7,8,8,7,5,3,0,0,],
[2,4,7,8,9,8,7,4,2,1,0,0,0,0,0,0,0,0,0,0,1,2,2,4,5,7,8,8,8,6,4,2,0,0,],
[2,4,7,8,9,9,7,5,4,3,2,2,2,2,2,2,2,2,3,3,3,4,5,6,7,8,8,8,6,4,2,0,0,0,],
[2,4,7,8,9,9,8,7,6,5,5,5,5,5,5,5,5,5,5,5,6,6,7,8,8,8,8,6,5,3,1,0,0,0,],
[2,4,7,8,9,9,9,8,8,7,7,7,7,7,7,7,7,7,7,8,8,8,8,9,9,8,7,5,3,2,0,0,0,0,],
[2,4,7,8,9,9,9,9,9,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,8,7,5,4,2,0,0,0,0,],
[2,4,7,8,9,9,9,9,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,8,7,5,3,2,0,0,0,],
[2,4,7,8,9,9,8,8,7,7,6,6,6,6,6,6,6,6,6,7,7,7,7,8,8,8,8,8,7,6,4,2,0,0,],
[2,4,7,8,9,9,8,6,5,4,4,4,4,4,4,4,4,4,4,4,4,5,5,6,7,8,8,8,8,7,6,4,2,0,],
[2,4,7,8,9,8,7,5,3,2,2,1,1,1,1,1,1,1,2,2,2,2,3,4,5,6,7,8,9,8,7,6,3,1,],
[2,4,7,8,9,8,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,4,6,7,8,9,8,7,5,2,],
[2,4,7,8,9,8,6,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,6,8,9,9,8,6,3,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,5,7,8,9,8,7,4,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,6,8,9,9,7,5,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,6,8,9,9,8,6,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,8,9,9,8,6,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,6,8,9,9,8,6,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,6,8,9,9,8,5,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,4,7,8,9,8,7,5,],
[2,4,7,8,9,8,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,5,7,9,9,8,6,4,],
[2,4,7,8,9,8,7,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,5,7,8,9,9,8,5,3,],
[2,4,7,8,9,8,7,5,3,1,0,0,0,0,0,0,0,0,0,0,1,1,2,3,4,5,7,8,9,9,8,7,4,2,],
[2,4,7,8,9,9,7,6,4,3,3,3,3,3,3,3,3,3,3,3,3,4,4,5,6,7,8,9,9,8,7,5,3,1,],
[2,4,7,8,9,9,8,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,8,8,9,9,8,7,6,4,2,0,],
[2,4,7,8,9,9,9,9,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,8,8,7,6,4,2,0,0,],
[2,4,7,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,8,8,8,8,8,7,6,5,4,2,0,0,0,],
[2,4,6,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,7,7,6,5,4,3,2,0,0,0,0,],
[1,3,4,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,5,5,4,4,3,3,2,0,0,0,0,0,0,],
]
]

Alles anzeigen

Da unsere Matrizen höchst wahrscheinlich unterschiedliche Maße aufweisen, müssen wir diese in ein Verhältnis zu unseren im PHP OCR Script vordefinierten Matrizen setzen.

Nun prüfen wir den ins Verhältnis gesetzten Punkt und die umliegenden Punkte auf einen Treffer.

Von allen Pixeln nehmen wir nun den höchsten Wert und addieren diesen zu einer Variable welche den Treffer Wert des Charakters enthält.

Nachdem wir all unsere vordefinierten Matrizen verglichen haben ermitteln wir die Matrix mit dem höchsten Treffer wert.

Nun hat unser PHP OCR Script zu einer gewissen Wahrscheinlichkeit einen Charakter erkannt.

Matrizen mit vordefinierten Matrizen vergleichen

PHP

$character = [];
// Iterate through character matrices for matching
foreach ($characters as $index => $char) {
$matchedArray = [];
// Iterate through our letter matrices and compare them to our character matrix
foreach ($letters as $letter => $properties) {
$matrix = $properties['matrix'];
$matched = 0;
// Calculate the relation of charcter matrix size to the letter matrix size
$xRatio = (sizeof($matrix[0]) - 1) / $char->width;
$yRatio = (sizeof($matrix) - 1) / $char->height;
foreach ($char->points as $point) {
$x = ($point->x * $xRatio);
$y = ($point->y * $yRatio);
// Check each point and its surrounding for matching the pixel
$pointMatch = [];
if (isset($matrix[$y][$x]))
$pointMatch[] = $matrix[$y][$x];
if (isset($matrix[$y+1][$x]))
$pointMatch[] = $matrix[$y+1][$x];
if (isset($matrix[$y-1][$x]))
$pointMatch[] = $matrix[$y-1][$x];
if (isset($matrix[$y][$x+1]))
$pointMatch[] = $matrix[$y][$x+1];
if (isset($matrix[$y][$x-1]))
$pointMatch[] = $matrix[$y][$x-1];
if (isset($matrix[$y+1][$x+1]))
$pointMatch[] = $matrix[$y+1][$x+1];
if (isset($matrix[$y+1][$x-1]))
$pointMatch[] = $matrix[$y+1][$x-1];
if (isset($matrix[$y-1][$x+1]))
$pointMatch[] = $matrix[$y-1][$x+1];
if (isset($matrix[$y-1][$x-1]))
$pointMatch[] = $matrix[$y-1][$x-1];
// Get the highest matching of all surroinding pixels
$matched += max($pointMatch);
}
$matchedArray[$letter] = $matched;
}
// Sort the letters and get the best matching letter
arsort($matchedArray);
$letter = key($matchedArray);
$match = reset($matchedArray);
var_dump($letter, $match / (sizeof($char->points) / 100));
}

Alles anzeigen

Schlusswort zum PHP OCR Script

Nun habt ihr also einen einfachen aber recht Fehler anfälligen Weg kennen gelernt wie man ein PHP OCR Script entwickeln kann.

Ihr werdet mit dem Aktuellen PHP OCR Script Probleme bei dem Vergleich mit der vordefinierten Matrix für den Buchstaben I haben.

Dieser Buchstabe hat nämlich keinen Whitespace und trifft, durch das „ins Verhältnis setzen der Koordinaten“, jeden Punkt.

Man könnte das reduzieren in dem man die Anzahl der gefilterten Punkte, mit den zu vergleichenden Punkten, mit in den Vergleich einbezieht.

Wie man sieht habe ich in der Matrix für den Buchstaben B bereits die Anzahl der gesamten Punkte und der maximal treffbaren Punkte eingetragen.

Damit könnte man den Treffer Wert ins Verhältnis zur gefilterten Matrix setzen und somit diesen Wert noch verfeinern.

Facebook
Twitter
Google+
Reddit
WhatsApp
LinkedIn
Pinterest

PHP OCR - Ein simpler Weg zur Texterkennung

Der Berg namens OCR

Der Weg zum Ziel

Charaktererkennung

Matrix Vergleich

Schlusswort zum PHP OCR Script

Teilen

Kommentare

Stammtisch: Wir schaffen 8888 Seiten! (1000, 1337, 2222, 3333, 4444, 5555, 6666 & 7777 geschafft)

Escape Rooms: Unlocking Adventure and Creativity

Die StageTwo Stammuser

PC Booting: Fehlermeldung (Failure Predicted on SATA)

PC Aufrüsten

Stammtisch: Wir schaffen 8888 Seiten! (1000, 1337, 2222, 3333, 4444, 5555, 6666 & 7777 geschafft)

[LOL] Allgemeiner Diskussionsthread

Laberthread

Esro Diskussionsthread

Wrestle-Talk