3
$\begingroup$

I work with python and images of tables (taken from above). My aim is to take a photo of a random table and then find the most similar tables to it in my database. Obviously, the main feature which distinguishes the tables are their shape (square, rectangular, round, oval) but there are also other details.

For now, I am just running a PCA and a KNN on rgb images of tables to find the most similar tables in the database for each of the tables of the database.

The problem is that when I increase the number of rgb images of tables e.g. from 400 to 500 the processing time significantly increases. My final goal is to run this program with 2000 or even 4000 table images so I need a more efficient machine learning algorithm for my task.

Can you recommend me another more efficient machine learning algorithm for this task?

$\endgroup$
3
  • $\begingroup$ What kind of features are you using? Are you using the raw RGB values? $\endgroup$
    – kedarps
    Jan 30, 2018 at 10:04
  • $\begingroup$ Do you use any libraries for this, if so which? What resolution do your pictures have? It might be that it's not necessarily the algorithms but their use that is inefficient in this situation. $\endgroup$
    – deemel
    Jan 30, 2018 at 10:08
  • $\begingroup$ Thank you both for your responses. I am using raw rgb images and the scikit in python. I have also tried it with grayscale or even binary images but I think that I lose some valuable information in these ways. $\endgroup$
    – Outcast
    Jan 30, 2018 at 16:21

2 Answers 2

3
$\begingroup$

It depends on a lot of parameters. Calling $h$ the height, $w$ the width of the image and $n_{channels}$ then number of channels, probably 3, then we define $p=h*w*n_{channels}$.

The PCA step has a complexity of $O(np^2+p^3)$ for training and O($np$) for predictions. Calling $p'$ the number of principal components you keep, running a (naive) $k$ Nearest Neighbours search on the points will have a complexity of $O(p'n)$.

So increasing the training size by 20% should increase the time taken by 20%, which I find a little puzzling (unless you run into memory issue and other things happen).

Besides, if you want to make your method faster, based on the definition of $p$ you may note that the size of the image is critical. Dividing $w$ and $h$ by two may divide the time taken by the PCA by $(2*2)^2=16$.

Regarding the kNN step, it is worth noting that there are many smart implementation relying on quadtrees (in R SearchTrees, per example) that significantly decrease the prediction time.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. Yes, I had in my mind the computational complexities of both of these algorithms. Finally, I must find a way to reduce my data or upgrade my hardware because even other machine learning algorithms like SMV or CNNs require even more computational resources. $\endgroup$
    – Outcast
    Jan 30, 2018 at 16:24
2
$\begingroup$

Try a faster KNN library. Some suggestions:
https://github.com/spotify/annoy
https://github.com/FALCONN-LIB/FALCONN

Comparisons:
https://github.com/erikbern/ann-benchmarks
https://erikbern.com/2016/06/02/approximate-nearest-news.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.