Iniziamo con la funzione eraseMaxSquare(), funzione che semplicemente si occupa di eliminare la cornice principale dal vettore di rettangoli. Di seguito è mostrato il codice, la cui lettura è piuttosto facile e per questo non ci dilungheremo a descriverne il funzionamento.
static vector<vector<Point> > eraseMaxSquare(
const vector<vector<Point> > squares) {
vector<vector<Point> > newSquares;
for (unsigned int i = 0; i < squares.size(); i++) {
if (squares[i][0].x != 1 && squares[i][0].y != 1)
newSquares.push_back(squares[i]);
}
return newSquares;
}
Dopo aver eliminato la cornice dal vettore di rettangoli, andiamo ad eliminare i rettangoli annidati all'interno delle vignette. E' il caso dei narratori, o in generale di figure rettangolari comprese all'interno della scena. La funzione è eraseNestedSquares().
static vector<vector<Point> > eraseNestedSquares(
const vector<vector<Point> > squares, Mat& image) {
vector<vector<Point> > newSquares;
vector<int> nestedIndices;
for (unsigned int i = 0; i < squares.size(); i++) {
for (unsigned int j = i; j < squares.size(); j++) {
Point p1 = Point(squares[i][0].x, squares[i][0].y);
Point p2 = Point(squares[i][2].x, squares[i][2].y);
Point p3 = Point(squares[j][0].x, squares[i][0].y);
Point p4 = Point(squares[j][2].x, squares[j][2].y);
Rect ri = Rect(p1, p2);
Rect rj = Rect(p3, p4);
Rect rtest = ri & rj;
if (rtest.area() > 0 && i != j) {
if (!ri.area() - rj.area() >= 0)
nestedIndices.push_back(j);
else if (!ri.area() - rj.area() < 0)
nestedIndices.push_back(i);
}
}
}
cout << endl;
for (unsigned int i = 0; i < squares.size(); i++) {
bool found = false;
for (unsigned int j = 0; j < nestedIndices.size(); j++) {
if (nestedIndices[j] == i)
found = true;
}
if (!found) {
newSquares.push_back(squares[i]);
}
}
return newSquares;
}
Utilizzando "l'algebra dei Rect" di OpenCV, che è stata brevemente trattata in un precedente tutorial, viene scorso tutto il vettore e sono confrontati a coppia i rettangoli. Se l'intersezione tra i due è maggiore di zero, e non è effettuato un confronto tra un rettangolo e se stesso, allora il rettangolo con area minore è inserito nella lista dei rettangoli annidati che saranno eliminati dal vettore in seguito nel codice.
Veniamo adesso alla funzione più complicata del programma, addNotReveleadSquares(). Si basa sulla costruzione di una griglia di punti all'interno della pagina. Per ogni punto viene controllato se questo appartiene o meno ad un rettangolo del vettore squares. Se questo non appartiene, viene richiamata la funzione exploreRegion(), la quale a partire da quel punto esplora la pagina nelle quattro direzioni cardinali fino ad incontrare una vignetta già presente in squares o i bordi della pagina. Alla fine dell'esplorazione, è effettuato un test sull'area della nuova vignetta e se viene passato, questa è aggiunta al vettore di rettangoli.
static vector<vector<Point> > addNotReveleadSquares(
vector<vector<Point> > squares, Mat image) {
int width = image.cols;
int height = image.rows;
int den = 3;
int indexX[den];
int indexY[den];
int deltaX = width / (den);
int deltaY = height / (den);
indexX[0] = deltaX / 2;
indexY[0] = deltaY / 2;
for (unsigned int i = 1; i < den; i++) {
indexX[i] = indexX[i - 1] + deltaX;
indexY[i] = indexY[i - 1] + deltaY;
}
indexX[den - 1] = width - deltaX / 2;
indexY[den - 1] = height - deltaY / 2;
for (unsigned int i = 0; i < den; i++)
for (unsigned int j = 0; j < den; j++) {
Point pt = Point(indexX[i], indexY[j]);
unsigned int count = 0;
bool found = false;
while (count < squares.size()) {
if (pointPolygonTest(squares[count], pt, false) >= 0)
found = true;
count++;
}
if (!found) {
squares = exploreRegion(squares, pt, width, height);
}
}
return squares;
}
static vector<vector<Point> > exploreRegion(vector<vector<Point> > squares,
Point pt, int width, int height) {
int north = pt.y;
bool foundNorth = false;
int south = pt.y;
bool foundSouth = false;
int west = pt.x;
bool foundWest = false;
int east = pt.x;
bool foundEast = false;
int epsilon = 1;
double areas[squares.size()];
for (unsigned int a = 0; a < squares.size(); a++) {
areas[a] = contourArea(squares[a]);
}
double minArea = INT_MAX;
for (unsigned int a = 0; a < squares.size(); a++) {
if (areas[a] < minArea)
minArea = areas[a];
}
while (north > 0 && !foundNorth) {
north = north - epsilon;
Point pttest = Point(pt.x, north);
for (unsigned int i = 0; i < squares.size(); i++) {
if (pointPolygonTest(squares[i], pttest, false) >= 0)
foundNorth = true;
}
}
cout << endl;
while (south <= height && !foundSouth) {
south = south + epsilon;
Point pttest = Point(pt.x, south);
for (unsigned int i = 0; i < squares.size(); i++) {
if (pointPolygonTest(squares[i], pttest, false) >= 0)
foundSouth = true;
}
}
while (west > 0 && !foundWest) {
west = west - epsilon;
Point pttest = Point(west, pt.y);
for (unsigned int i = 0; i < squares.size(); i++) {
if (pointPolygonTest(squares[i], pttest, false) >= 0)
foundWest = true;
}
}
while (east <= width && !foundEast) {
east = east + epsilon;
Point pttest = Point(east, pt.y);
for (unsigned int i = 0; i < squares.size(); i++) {
if (pointPolygonTest(squares[i], pttest, false) >= 0)
foundEast = true;
}
}
Point p1 = Point(west, north);
Point p2 = Point(east, north);
Point p3 = Point(east, south);
Point p4 = Point(west, south);
vector<Point> newSquare;
newSquare.push_back(p1);
newSquare.push_back(p2);
newSquare.push_back(p3);
newSquare.push_back(p4);
if (contourArea(newSquare) > minArea / 4)
squares.push_back(newSquare);
return squares;
}
All'interno del codice vi sono due euristiche che richiederebbero un studio più approfondito. La prima riguarda la granularità della griglia, la seconda riguarda l'area della vignetta che è aggiunta. Per la prima, nell'esempio del codice è creata una griglia 3x3 all'interno della pagina, ma probabilmente dovrebbe essere ricercata una relazione tra la granularità della griglia ed il numero di rettangoli trovati fino a questo momento. Per la seconda, viene calcolata la vignetta con l'area più piccola e la nuova vignetta è aggiunta se ha un'area maggiore di un quarto dell'area più piccola. Questo serve ad evitare che nel vettore squares siano inseriti anche bordi o zone rettangolari all'interno del fumetto.
Per chiarire ulteriormente il funzionamento di questa funzione, vi consiglio di dare un'occhiata all'immagine seguente, tratta da un mio albo di Rat-Man di Leo Ortolani: i punti rossi sono i 9 punti definiti dalla griglia, mentre i rettangoli verdi sono quelli che sono già stati inseriti nel vettore fino a questo momento. Esiste un un solo punto che non appartiene a nessun rettangolo, quindi a partire da quello si fa avvia una ricerca nelle 4 direzioni.
Infine, una volta trovate tutte le vignette, queste devono essere riordinate all'interno del vettore per permetterne la giusta visualizzazione (all'interno di un modulo apposito non ancora perfezionato). Ecco quindi la funzione reorderSquares().
static vector<vector<Point> > reorderSquares(vector<vector<Point> > squares,
Mat image, bool isManga) {
vector<vector<Point> > reorderedSquares;
list<double> tmpDistances;
list<Point> tmpCentroids;
list<int> tmpIndices;
vector<double> permDistances;
vector<Point> permCentroids;
vector<int> permIndices;
for (unsigned int i = 0; i < squares.size(); i++) {
Point centroid = Point(
(squares[i][0].x + squares[i][1].x + squares[i][2].x
+ squares[i][3].x) / 4,
(squares[i][0].y + squares[i][1].y + squares[i][2].y
+ squares[i][3].y) / 4);
tmpIndices.push_back(i);
permCentroids.push_back(centroid);
permIndices.push_back(i);
if (isManga) {
tmpDistances.push_back(
(centroid.x - image.cols) * (centroid.x - image.cols)
+ centroid.y * centroid.y);
permDistances.push_back(
(centroid.x - image.cols) * (centroid.x - image.cols)
+ centroid.y * centroid.y);
} else {
tmpDistances.push_back(
centroid.x * centroid.x + centroid.y * centroid.y);
permDistances.push_back(
centroid.x * centroid.x + centroid.y * centroid.y);
}
}
int flags[permCentroids.size()];
for (unsigned int i = 0; i < permCentroids.size(); i++) {
flags[i] = 1;
}
for (unsigned int i = 0; i < permCentroids.size(); i++) {
vector<Point> cluster;
for (unsigned int j = 0; j < permCentroids.size(); j++) {
if (abs(permCentroids[i].y - permCentroids[j].y) < 10
&& flags[j] == 1) {
flags[j] = 0;
permCentroids[j].y = permCentroids[i].y;
}
}
}
for (unsigned int i = 0; i < permCentroids.size(); i++) {
tmpCentroids.push_back(permCentroids[i]);
}
list<Point> centroids;
list<int> indices;
list<double> distances;
bool done = false;
while (!done) {
double minDist = INT_MAX;
int minIndex = 0;
int count = 0;
std::list<double>::iterator eraseDoubleIterator = tmpDistances.begin();
std::list<Point>::iterator erasePointIterator = tmpCentroids.begin();
std::list<int>::iterator eraseIntIterator = tmpIndices.begin();
for (std::list<double>::iterator iterator = tmpDistances.begin(), end =
tmpDistances.end(); iterator != end; ++iterator) {
if (*iterator < minDist) {
minDist = *iterator;
minIndex = count;
eraseDoubleIterator = iterator;
}
count++;
}
distances.push_back(minDist);
std::list<Point>::iterator maxIterator = tmpCentroids.begin();
advance(maxIterator, minIndex);
std::vector<Point>::iterator ptIterator = permCentroids.begin();
for (unsigned int i = 0; i < permCentroids.size(); i++) {
if ((*ptIterator).x == (*maxIterator).x
&& (*ptIterator).y == (*maxIterator).y) {
centroids.push_back(*maxIterator);
indices.push_back(i);
}
advance(ptIterator, 1);
}
eraseDoubleIterator = tmpDistances.erase(eraseDoubleIterator);
advance(erasePointIterator, minIndex);
erasePointIterator = tmpCentroids.erase(erasePointIterator);
advance(eraseIntIterator, minIndex);
eraseIntIterator = tmpIndices.erase(eraseIntIterator);
if (tmpDistances.size() == 1) {
indices.push_back(*tmpIndices.begin());
centroids.push_back(*tmpCentroids.begin());
distances.push_back(*tmpDistances.begin());
done = true;
}
}
bool everythingOk = false;
if (true) {
while (!everythingOk) {
std::list<int>::iterator intIterator = indices.begin();
std::list<Point>::iterator pointIterator = centroids.begin();
unsigned int count = 0;
bool swap = false;
while (count < centroids.size() - 1) {
std::list<Point>::iterator postIterator = pointIterator;
std::list<int>::iterator postIntIterator = intIterator;
advance(postIterator, 1);
advance(postIntIterator, 1);
if ((*pointIterator).y > (*postIterator).y) {
Point tmpPt = *pointIterator;
*pointIterator = *postIterator;
*postIterator = tmpPt;
int tmpIndex = *intIterator;
*intIterator = *postIntIterator;
*postIntIterator = tmpIndex;
swap = true;
}
count++;
advance(pointIterator, 1);
advance(intIterator, 1);
advance(postIterator, 1);
advance(postIntIterator, 1);
}
cout << endl;
for (std::list<int>::iterator iterator = indices.begin(), end =
indices.end(); iterator != end; ++iterator) {
}
if (!swap) {
everythingOk = true;
}
}
}
for (std::list<int>::iterator iterator = indices.begin(), end =
indices.end(); iterator != end; ++iterator) {
reorderedSquares.push_back(squares[*iterator]);
}
return reorderedSquares;
}
L'idea di questa funzione è calcolare le distanze tra il baricentro di ogni rettangolo e l'angolo in alto a sinistra (o in alto a destra per i manga) e poi ordinarli per la distanza in maniera crescente. In caso di ambiguità tra queste, viene data importanza alla posizione dei centroidi. Il codice è lungo e tortuoso, e sicuramente di non facile lettura. Se avete proposte per risolvere questo problema (l'uso di specifiche strutture dati o una riorganizzazione del codice), commentate questo articolo.
Spero vi sia piaciuto questo speciale in due parti. Mi piacerebbe prima o poi trovare il modo di integrare queste funzionalità all'interno di un'applicazione vera e propria. Vedremo se a questo proposito uscirà mai sul sito una terza parte.
