Linux Certif

Toute la documentation sur la certification Linux LPI

libpuzzle

BSD mandoc

NAME

puzzle_init_cvec puzzle_init_dvec puzzle_fill_dvec_from_file puzzle_fill_cvec_from_file puzzle_fill_cvec_from_dvec puzzle_free_cvec puzzle_free_dvec puzzle_init_compressed_cvec puzzle_free_compressed_cvec puzzle_compress_cvec puzzle_uncompress_cvec puzzle_vector_normalized_distance - compute comparable signatures of bitmap images.

SYNOPSIS

Fd #include <puzzle.h> Ft int Fn puzzle_init_context PuzzleContext *context Ft int Fn puzzle_free_context PuzzleContext *context Ft int Fn puzzle_init_cvec PuzzleContext *context PuzzleCvec *cvec Ft int Fn puzzle_init_dvec PuzzleContext *context PuzzleDvec *cvec Ft void Fn puzzle_fill_dvec_from_file PuzzleContext *context PuzzleDvec * dvec const char *file Ft void Fn puzzle_fill_cvec_from_file PuzzleContext *context PuzzleCvec * cvec const char *file Ft void Fn puzzle_fill_cvec_from_dvec PuzzleContext *context PuzzleCvec * cvec const PuzzleDvec *dvec Ft void Fn puzzle_free_cvec PuzzleContext *context PuzzleCvec *cvec Ft void Fn puzzle_free_dvec PuzzleContext *context PuzzleDvec *cvec Ft void Fn puzzle_init_compressed_cvec PuzzleContext *context PuzzleCompressedCvec * compressed_cvec Ft void Fn puzzle_free_compressed_cvec PuzzleContext *context PuzzleCompressedCvec * compressed_cvec Ft int Fn puzzle_compress_cvec PuzzleContext *context PuzzleCompressedCvec * compressed_cvec const PuzzleCvec * cvec Ft int Fn puzzle_uncompress_cvec PuzzleContext *context PuzzleCompressedCvec * compressed_cvec PuzzleCvec * const cvec Ft double Fn puzzle_vector_normalized_distance PuzzleContext *context const PuzzleCvec * cvec1 const PuzzleCvec * cvec2, const int fix_for_texts

DESCRIPTION

The Puzzle library computes a signature out of a bitmap picture. Signatures are comparable and similar pictures have similar signatures.

After a picture has been loaded and uncompressed, featureless parts of the image are skipped (autocrop), unless that step has been explicitely disabled, see puzzle_set3

LIBPUZZLE CONTEXT

Every public function requires a PuzzleContext object, that stores every required tunables.

Any application using libpuzzle should initialize a PuzzleContext object with Fn puzzle_init_context and free it after use with Fn puzzle_free_context

 PuzzleContext context;
 
 puzzle_init_context(&context);
  ...
 puzzle_free_context(&context);
 

DVEC AND CVEC VECTORS

The next step is to divide the cropped image into a grid and to compute the average intensity of soft-edged pixels in every block. The result is a PuzzleDvec object.

PuzzleDvec objects should be initialized before use, with Fn puzzle_init_dvec and freed after use with Fn puzzle_free_dvec

The PuzzleDvec structure has two important fields: vec is the pointer to the first element of the array containing the average intensities, and sizeof_compressed_vec is the number of elements.

PuzzleDvec objects are not comparable, so what you usually want is to transform these objects into PuzzleCvec objects.

A PuzzleCvec object is a vector with relationships between adjacent blocks from a PuzzleDvec object.

The Fn puzzle_fill_cvec_from_dvec fills a PuzzleCvec object from a PuzzleDvec object.

But just like the other structure, PuzzleCvec objects must be initialized and freed with Fn puzzle_init_cvec and Fn puzzle_free_cvec

PuzzleCvec objects have a vector whoose first element is in the vec field, and the number of elements is in the sizeof_vec field

LOADING PICTURES

PuzzleDvec and PuzzleCvec objects can be computed from a bitmap picture file, with Fn puzzle_fill_dvec_from_file and Fn puzzle_fill_cvec_from_file

GIF , PNG and JPEG files formats are currently supported and automatically recognized.

Here's a simple example that creates a PuzzleCvec objects out of a file.

 PuzzleContext context;
 PuzzleCvec cvec;
 
 puzzle_init_context(&context);
 puzzle_init_cvec(&context, &cvec);
 puzzle_fill_cvec_from_file(&context, &cvec, "test-picture.jpg");
  ...
 puzzle_free_cvec(&context, &cvec);
 puzzle_free_context(&context);
 

COMPARING VECTORS

In order to check whether two pictures are similar, you need to compare their PuzzleCvec signatures, using Fn puzzle_vector_normalized_distance

That function returns a distance, between 0.0 and 1.0. The lesser, the nearer.

Tests on common pictures show that a normalized distance of 0.6 (also defined as PUZZLE_CVEC_SIMILARITY_THRESHOLD ) means that both pictures are visually similar.

If that threshold is not right for your set of pictures, you can experiment with PUZZLE_CVEC_SIMILARITY_HIGH_THRESHOLD , PUZZLE_CVEC_SIMILARITY_LOW_THRESHOLD and PUZZLE_CVEC_SIMILARITY_LOWER_THRESHOLD or with your own value.

If the Fa fix_for_texts of Fn puzzle_vector_normalized_distance is 1 , a fix is applied to the computation in order to deal with bitmap pictures that contain text. That fix is recommended, as it allows using the same threshold for that kind of picture as for generic pictures.

If Fa fix_for_texts is 0 , that special way of computing the normalized distance is disabled.

 PuzzleContext context;
 PuzzleCvec cvec1, cvec2;
 double d;
 
 puzzle_init_context(&context);
 puzzle_init_cvec(&context, &cvec1);
 puzzle_init_cvec(&context, &cvec2);
 puzzle_fill_cvec_from_file(&context, &cvec1, "test-picture-1.jpg");
 puzzle_fill_cvec_from_file(&context, &cvec2, "test-picture-2.jpg");
 d = puzzle_vector_normalized_distance(&context, &cvec1, &cvec2, 1);
 if (d < PUZZLE_CVEC_SIMILARITY_THRESHOLD) {
   puts("Pictures are similar");
 }
 puzzle_free_cvec(&context, &cvec2);
 puzzle_free_cvec(&context, &cvec1);
 puzzle_free_context(&context);
 

CVEC COMPRESSION

In order to reduce storage needs, PuzzleCvec objects can be compressed to 1/3 of their original size.

PuzzleCompressedCvec structures hold the compressed data. Before and after use, these structures have to be passed to Fn puzzle_init_compressed_cvec and Fn puzzle_free_compressed_cvec

Fn puzzle_compress_cvec compresses a PuzzleCvec object into a PuzzleCompressedCvec object.

And Fn puzzle_uncompress_cvec uncompresses a PuzzleCompressedCvec object into a PuzzleCvec object.

 PuzzleContext context;
 PuzzleCvec cvec;
 PuzzleCompressedCvec c_cvec;
  ...
 puzzle_init_compressed_cvec(&context, &c_cvec);
 puzzle_compress_cvec(&context, &c_cvec, &cvec);
  ...
 puzzle_free_compressed_cvec(&context, &c_cvec); 
 

The PuzzleCompressedCvec structure has two important fields: vec that is a pointer to the first element of the compressed data, and sizeof_compressed_vec that contains the number of elements.

RETURN VALUE

Functions return 0 on success, and -1 if something went wrong.

AUTHORS

Nf Frank DENIS libpuzzle at pureftpd dot org Fi  

ACKNOWLEDGMENTS

Nf Xerox Research Center H. CHI WONG Marschall BERN David GOLDBERG Sameh SCHAFIK Fi  

SEE ALSO

puzzle_set3 puzzle-diff8