We were discussing Signature verification methods. We reviewed the stages involved with Signature verification. Then we also enumerated the feature extraction techniques. After that, we compared online and offline verification techniques. We also discussed the limitations of image processing and the adaptations for video processing.Then we proceeded to discussing image embedding in general.
Today we continue our discussion of Convolutional Neural Network (CNN) in image and object embedding in a shared space.
The purpose of the embedding is to map an image to a point in the embedding space so that it is close to a point attributed to a 3D model of a similar object. A large amount of training data consisting of images synthesized from 3D shapes is used to train the CNN.
In order to play up the latent objects in images, similar objects were often used in dissimilar images. The dissimilarity was based on viewpoint, lighting, background differences, partial hiding and so on. 3D object representations do not suffer from these dissimilarities and are therefore much easier to establish similarity.
Images and 3D shapes share the embedded space. In that space, both can be measured as if their 3D form was directly available. This embedded space is plotted with each object given a co-ordinate comprising of the dimension reduced form of the distances between the underlying shape and the entire set.  This way two neighboring points in the embedded space are likely to represent similar shapes, as they agree to a similar extent, on their similarities with all the other shapes.

#codingexercise
A step array is an array of integer where each element has a difference of atmost k with its neighbor. Given a key x, we need to find the index value of k if multiple element exist return the index of any  occurrence of key.
Input : arr[] = {4, 5, 6, 7, 6}
           k = 1
           x = 6
Output : 2

int GetIndex(List<int> A, int x, int k)
{
int i = 0;
while (i < A.Length)
{
if (A[i] == x)
   return i;
i = i + Math.Max(1, Math.Abs(A[i]-x)/k);
}
return -1;
}

We were discussing Signature verification methods. We reviewed the stages involved with Signature verification. Then we also enumerated the feature extraction techniques. After that, we compared online and offline verification techniques. We also discussed the limitations of image processing and the adaptations for video processing. Today let us discuss image embedding in general.
In this case, we discuss CNN Image Purification techniques from the Li et al paper on Joint Embeddings. CNN stands for Convolutional Neural Network.It purifies images by muting distracting factor The purpose of the embedding is to map an image to a point in the embedding space so that it is close to a point attributed to a 3D model of a similar object. A large amount of training data consisting of images synthesized from 3D shapes is used to train the CNN.
In order to play up the latent objects in images, similar objects were often used in dissimilar images. The dissimilarity was based on viewpoint, lighting, background differences, partial hiding and so on. 3D object representations do not suffer from these dissimilarities and are therefore much easier to establish similarity.
Images and 3D shapes share the embedded space. In that space, both can be measured as if their 3D form was directly available. This embedded space is plotted with each object given a co-ordinate comprising of the dimension reduced form of the distances between the underlying shape and the entire set.  This way two neighboring points in the embedded space are likely to represent similar shapes, as they agree to a similar extent, on their similarities with all the other shapes.
A set of ground truth co-ordinates in the embedding space is required. A large amount of images to train the CNN is also required. Another alternative for obtaining the necessary links between images and their embeddings is to manually link images to similar 3D models. But since this is time-consuming and error prone, the image training set is synthesized based on rendering a rather modest set of annotated shapes from the ShapeNet
This technique of embedding is a novel attempt to correlate 3D shapes and 2D images. The deep embedding is capable of  purifying these images  and interlinking the two domains based on their shared object content This linking then supports querying that was not possible before.
#codingexercise
Minimum removals from array to make max – min <= K
A.sort();
int count = 0;
int i = 0;
int j = A.Length -1;
int GetRemovals(List<int>sorted, int K, int i, int j)
{
if (i >= j) return 0;
if (A[j]-A[i]) <= K) return 0;
return 1 + Math.min(GetRemovals(sorted, K,  i+1, j),
                                  GetRemovals(sorted, K,  i, j -1));
}
if (count  >= A.Length-1) return -1;
1 4 6 8
N = 4
K = 5

We were discussing Signature verification methods. We reviewed the stages involved with Signature verification. Then we also enumerated the feature extraction techniques. After that, we compared online and offline verification techniques. Yesterday we discussed the limitations of image processing and the adaptations for video processing. Today we continue with the discussion on relevant improvements for signature processing.

Unlike earlier, when image processing was confined to research labs and industrial automations, there are now software libraries, packages and applications available. Moreover, services for image processing are no longer restricted in compute and storage because they can now be hosted in the cloud. Many cloud providers now also provide libraries for image processing. For example, Microsoft and Google both provide image processing libraries. Perhaps Clarifai has a dedicated offering in this discipline.

The reason I bring out these companies is that this area of study also benefits from a multidisciplinary approach. For example, Microsoft's machine learning algorithms and R-package covered earlier in this post may also be relevant to image processing after images are transformed to a vector space model. Similarly Google's application of word2vec to perform word embeddings may provide insight into object embedding in images. Clarifai provides an api library and makes image processing just as commercial to develop as it is fun to experiment in Matlab.

Signature processing benefits incredibly with the right choice of algorithms. We don't need to perform edge segmentation since the data may already be smoothed and made clear in the preprocessing step. Gaussian smoothing helps in this regard because it adjusts the value of the current pixel based on the values of the surrounding pixels. After the pre-processing, the offline verification of signature becomes straightforward as we rely on a choice of algorithms from the previously covered list to perform this verification. If we have the luxury of performing these comparisions simultaneously, we can then perform a collaborative filtering of the given sample as a valid or invalid in a serverless computing paradigm. This is a break from the previously mentioned software for signature verification.

Technically this does not seem impossible but as we fine tune the algorithm and user acceptance may determine the success of such a venture. Signatures unlike passwords are handwritings. They are susceptible to the mood and circumstance. Since the input may change each time, the verification has to give such latitude to the user.

We were discussing Signature verification methods. We reviewed the stages involved with Signature verification yesterday. We also enumerated the feature extraction techniques. Then we compared online and offline verification techniques.

One of the reasons offline image processing is preferred is that good image processing algorithms are often computationally expensive and require more time than say network roundtrip for packets. This makes it costly to include as an interactive web page analysis widget.  Time taken to execute image processing algorithms have taken even eight seconds. That is why image processing finds it difficult to keep up with the frame rate of a video. However, significant advances have been made that improve processing for streaming of images to be processed. For example, Active contour model can help track movement of object in images for a frame rate that matches the rate used for video. Signatures are considered a lot simpler to work with in image processing. They are generally small sized, binary color and easy to capture and process.  As long as the image processing can tell apart a real signature from forged specimens, an image processor can work in the backend for a signature pad widget in the front-end.

We talked about the acceptance criteria for an image processing technique that is largely measured by the precision and recall. By training the processor on a signature dataset, these processors become highly effective in determining even forged from real specimens. Today we will take a closer look at how this verification is done. Since we read how classifiers work in text processing to convert the document into a vector space model and then classify the document based on euclidean distance between feature vectors, the signature verification should also be familiar. The features extracted from the image as described in the previous posts is transformed into the vector space and then compared with the master. If the euclidean distance is within tolerance threshold, the signature is accepted. Since the image processor is already trained and tested on a variety of images and measured with precision and recall, it is reliable to convert the given specimen into a representative feature vector. This concludes the signature verification technique.


#codingexercise

We were discussing combinations with duplicates and that too in a greedy manner. instead of enumerating combinations to the whole length, we can leverage stars and bars theorem to be more efficient. With this theorem, we already know the number of combinations that can exist with duplicates and therefore do not enumerate them but directly count them towards the goal such as the price of the accessories shopped. The theorem mentioned used a binomial coefficient.

We were discussing Signature verification methods. We reviewed the stages involved with Signature verification yesterday. We also enumerated the feature extraction techniques. Now let us proceed to comparing online and offline verification techniques.

An offline signature processing algorithm requires all the information before the algorithm starts. This gives us opportunity to perform all the pre-processing required to normalize the dataset for the algorithm to work effectively. The online algorithm might work on the data while the data is being made available. The processor may reside as close to the sensing device as necessary to make this happened. In the offline case, the processor may even be in a backend system of the office. The image recognition for handwritten signatures has traditionally been offline processing. Even as such, it has been more optical based and not magnetic based.  With the list of features compared between the two in the online and offline systems, we see the difference in what can be used online. Online techniques have been said to be more accurate because the system is getting the data as the user feeds it. Offline comparision can eliminate the quirks of the device on which the data is being submitted and can work effectively across a variety of devices and vendors. Online processing helps standalone processors that can be mobile and may have its own local database.

The acceptance criteria for an image processing technique is largely measured by the precision and recall.  Precision in this case is the ratio that explains number of selected items that are relevant. It is the ration of the true positives to all that were selected by the image processor for this image. A true positive is one that improves the feature matching. A false positive doesn’t but shows up in match threshold.  Recall on the other hand is a metric that determines how many relevant items are selected. It is the ratio of the true positives to all those that would have improved the feature matching from the global set feature matches including ones that the processor did not select. Together precision and recall yields a different metric called F-score which gives the effectiveness of retrieval with respect to a given image. By training the processor on a signature dataset, these processors become highly effective in determining even forged from real specimens.

#codingexercise

We were discussing combinations with duplicates and that too in a greedy manner. instead of enumerating combinations to the whole length, we can leverage stars and bars theorem to be more effecient.

We were discussing Signature verification methods. We reviewed the stages involved with Signature verification yesterday. Let us continue to list and compare online and offline verification techniques.

The feature extraction techniques involved include:
1) using an SVM classifier to extract random transform and fractal dimension
2) using neural network to extract curvlet transform, Hough transform
3) using Euclidean distance and least square error classifier for point density and spatial frequency
4) using statistical analysis techniques and chi-square test
5) using feature vector correlation for projection and local point density
6) using svm for Radon transformation
7) using learning techniques
8) using neural network for directional features

Online signature feature extraction also include:
1) signing time
2) signature width and height
3) number of pen-ups and pen-downs
4) total signature length and
5) velocity of pen

Feature extraction depends on pre-processing. Images may need to be loaded, resized, thinned, rotated and cropped.

grayscale is made into binary image with the use of threshold as
(mu1 +mu2) / 2

#codingexercise
We were discussing a coding exercise as shown below:
A person wants to buy L items from her favorite store such that a subset of N items must contain D distinct items.  the items range from 1 to A in price. Determine the maximum amount of money the person can spend.

We discussed a technique for building the combinations in a greedy manner by choosing the highest priced items first. We also discussed an alternate way to enumerate all possible combinations and select only the ones that match the criteria and return the one that has the maximum purchase.
Another way to reduce enumerations of unnecessary combinations would be to use the enumerations only from combinations with repetitions instead of exhaustive combinations.

We were discussing Signature verification methods. Let us review the stages involved with Signature verification. We will also compare online and offline verification techniques afterwards.
The first stage for the image processing is the image acquisition. This is a crucial stage of any recognition system as the quality of image may considerably affect the subsequent stages. Moreover the devices capturing the image may wear over time since this is touch based technique. Therefore, the consistency of image quality over time is also an important factor.
The second stage for the image processing is the pre-processing that removes noise and may even introduce normalization.  Some pre-processing steps may also involve resizing, binary color conversion and cleaning, rotation, thinning and cropping.  Binary image that highlights only the signature may be achieved by determining the extremes of gray values and finding the mid point between them as the threshold. For example, if mu1 and mu2 are the gray values for both groups of pixels, the threshold may be set as ( mu1 + mu2 ) /2
The third stage of the image processing is the feature extraction. This is a critical stage for the signature verification because the type and quality of feature may make the verification accurate, predictable and consistent. While both online and offline verification techniques may vary in feature extraction, both may also involve common techniques. Feature extraction is generally termed global or local depending on the features extracted.
The last stage of the image processing is the signature verification. This may be the Euclidean distance computed in the feature space. If the distance is less than a threshold, the signature may be considered as verified.

#codingexercise
We were discussing a coding exercise as shown below:
A person wants to buy L items from her favorite store such that a subset of N items must contain D distinct items.  the items range from 1 to A in price. Determine the maximum amount of money the person can spend.

Since the price has to be maximized, the algorithm has to be greedy in its strategy to select the next item. when we can no longer purchase the highest priced item because it violates the given restriction, we make the subsequent selection  from the next lower priced item. we determine the threshold from the range 1 to n/d. The rest is recursive combination as shown earlier.
Another way to do this would be to enumerate all possible combinations and select only the ones that match the criteria and return the one that has the maximum purchase.