# A Multi-Stage Method for Logo Detection in Scanned Official Documents Based on Image Processing
## 3 Materials and Methods
### Computation of Regions of Interest (ROIs)  
The next step of the process involves using a heuristic based on human observation, derived from the characteristics of official documents, to compute regions of interest where a logo is expected to be placed with higher probability. If the logo is not in this region, it will not be detected. Given the nature of official documents, where the central part is dedicated to textual information, we can certainly expect the logo to not be placed close to the central part.  
In order to accurately extract an upper and lower region from the document and, at the same time, keep a high probability for those regions to contain a logo, we apply an algorithm  
Figure 3: Logotype-detection algorithm. (**a**) Original image. (**b**) Image after bilateral filtering. (**c**) Image after opening morphological operation.  
for the classical longest increasing run problem, with the additional restriction that we only consider runs of consecutive integers. We should distinguish between the longest increasing subsequence, where the elements need not be consecutive, and the longest increasing run, where the elements must be consecutive. In our problem, the numbers in the sequence are the row numbers of those rows in the image that contain background pixels exclusively, and the longest increasing run is the biggest block of consecutive rows exclusively formed by background pixels. Our idea is that, as logos are meant to be noticeable, logo and non-logo elements in a document are separated by big blocks of background pixels.  
The longest increasing consecutive run problem is a well-studied problem in computer science and can be formally defined as follows:  
**Definition 1**.: _The longest increasing consecutive run of a sequence \(s_{1},s_{2},\ldots,s_{m}\) of \(m\) integers is a subsequence \(s_{i},s_{i+1},\ldots,s_{i+k-1}\) of \(k\) elements, where \(k\leq n\) and \(s_{i+1}-s_{i}=1\ \forall i\in[0,k]\)._  
The solution to this problem, applied to the particular context of logo spatial identification, is defined in Algorithm 1.  
```
1:functionExtractROI (Image)
2: vector \(V\leftarrow\) empty
3:for all row in Image do
4:if\(numForegroundPixels(row)<=0.01*row.length\)then
5: Store \(row.index\) in vector \(V\)
6:\(currentBlockSize\gets 0\)
7:\(maxBockSize\gets 0\)
8:for\(index\gets 2\) to \(V.length\)do
9:if\(V(index)-1==V(index-1)\)then
10:\(currentBlockSize\gets currentBlockSize+1\)
11:else
12:\(currentBlockSize=0\)
13:if\(maxBockSize<currentBlockSize\)then
14:\(maxBockSize\gets currentBlockSize\)
15:\(maxBlockStart\leftarrow index-maxBockSize\)
16:return\(maxBlockStart\)
```  
**Algorithm 1** Longest increasing consecutive run algorithm to extract ROIs  
The algorithm works as follows:  
The \(ExtractRoi\) (\(Image\)) algorithm receives an image from which it extracts the largest block of consecutive rows with a number of black pixels greater than 1%. To do this, it stores in vector \(V\) the index of all the rows that meet this property (lines 2 to 5) and, then, goes through said vector \(V\) measuring the size of the blocks, \(currentBlockSize\), and selecting the largest, \(maxBlockSize\), returning the index where said block \(maxBlockStart\) begins (lines 6 to 16).  
We apply this algorithm to both the upper half and lower half of the document. The output is, thus, a pair of \(y\)-coordinates (one from each half of the document) that delimit the upper and lower regions where a logo is expected to be found with the most probability. A representative image, from the set of images analyzed, is displayed in Figure 4. It shows, delimited with blue lines, once the proposed procedure has been applied, those regions in a document from the test set.