High School Research #00 | Getting Started: idea + some literature review + glossary

Tongyu Lu — Thu, 08 Oct 2020 05:17:54 +0000

What I want to do

I don't really know. Or, I didn't. Either way, I am looking at something but I'm still not so sure yet.

My current idea comes from some stuff I saw about detecting forgery in scientific publications by searching for duplicate images. After a bit of searching, I decided that for now, it'll just be "near-duplicate image detection", and I might come back to all the scientific publication forgery stuff later.

A bunch of previous literature & quick notes

All these are about detecting near-duplicate image forgery and image splicing. This is just a small part of it and definitely not all, but that's for today. I'm a bit too lazy to get this organized any better XD

https://ieeexplore.ieee.org/abstract/document/7916155
- 2017; Conceptual model; deals with many different data types
- Not very useful for my purpose
https://ieeexplore.ieee.org/abstract/document/4426397
- 2007; wavelets & log-polar mapping
https://ieeexplore.ieee.org/document/7388368
- 2015; efficiency of DWT (Discrete Wavelet Transform)
https://ieeexplore.ieee.org/document/7546585
- 2016; RIC-LBP + Synthetic Aperture Radar; "outperforms some of the state-of-the-art methods"
https://link.springer.com/article/10.1007%2Fs11277-020-07102-x
- 2020; "Image and Video Forensics: A Critical Survey" <- Might be useful
https://ieeexplore.ieee.org/document/5301325
- 2009; using SV features
https://ieeexplore.ieee.org/document/5957431
- 2011; "Eclosion Forgeries" (what's that?); Curvelet Image Enhancement + Edge Detection ("Canny operators")
https://ieeexplore.ieee.org/document/5946873
- 2011; same image search; color-dependent feature vectors + 1-D descriptors
https://ieeexplore.ieee.org/document/7389169
- 2015; Survey on block-based copy-move image forgery detection <- Could be useful
https://ieeexplore.ieee.org/document/5697444
- 2010; DWT + blocks + lexicographic sorting + phase correlation; robust & reduce time
https://ieeexplore.ieee.org/document/6274631
- 2012; Radon Transformation + phase correlation
https://ieeexplore.ieee.org/document/7823199
- 2016; Color histogram and moments (pixel-level); effective on multiple copy-move forgery attacks
https://ieeexplore.ieee.org/document/7049877
- 2015; Survey on image forgery detection techniques <- May be useful?

I marked "useful" on the surveys because they're generally a faster way to get to know about the big picture.

Some helpful glossary

I haven't got time to look them up yet; I will, and I will maintain a separate collection of annotated glossary that is regularly updated.

DCT Discrete Cosine Transform
PCA Principal Component Analysis
AWGN Additive White Gaussian Noise
Kd-tree
DWT Discrete Wavelet Transform
SVD Singular Value Decomposition
LPFFT Log-Polar Fast Fourier Transform
FMT Fourier Mellin Transform
Bloom filters
Zernike moments
UWT Undecimated Wavelet Transform
PCA EVD PCA Eigenvalue Decomposition
Zigzag scan
LBP Local Binary Patterns
Gaussian filter
Wiener filter
MLBP Multiresolution LBP
RANSAC Random Sample Consensus

Last change: tweaks on URLs; add series link

USACO 2014 December Gold 1

Tongyu Lu — Sun, 16 Aug 2020 09:27:22 +0000

↓ USACO 2014 December Gold 1 Problem Statement | TL;DR

Code attached at the bottom.

TL;DR problem statement

N (2<=N<=20) cows each has a height, a weight, and a strength (the max weight it can support on its shoulders).

You need to stack up a subset of these cows so that

each cow can support the weight on its shoulders
the total height reaches a provided constant H (1<=H<=1e9)

Following that, maximize the additional weight that the cow stack can still support, and output that number. If impossible, print impossible.

Computational resource limit: 1000ms, 128MB

Back to full problem statement

Analysis

N<=20 just gives you a sense of where this is going: to have some kind of optimized status value for each combination of cows, with the combination crammed down into 20 bits (because all combinations is also the independent presence/absence of all cows). We'll come back to this.

The key is the equivalence of one cow to a one-cow stack of cows, and viewing a stack of cows as composed of non-overlapping substacks. These substacks can be considered immutable to the big stack, and therefore have their own height, weight, and strength.

Of course, a stack is genuinely an array of cows. For a stack S, the height and weight are obvious, and the strength is the minimum of each cow's strength minus the weight above it.

For a stack AB formed of stack A on top of B, the numbers are as below:

height(AB) = height(A) + height(B)
weight(AB) = weight(A) + weight(B)
strength(AB) = min(strength(A), strength(B) - weight(A))

We can see that order doesn't matter until you look at the strength. In fact, for a particular set of cows, their order on a single stack matters only to the strength. We will call a stack of a set of cows optimal to the set if the stack strength is high as it can get to.

We join stacks to make bigger ones, and it's easy to see why we don't need to consider using suboptimal stacks as building blocks: the strength formula above tells us that an optimal stack won't do worse than a suboptimal one, and as far as joining stacks goes, we don't care about what actually make up the stacks save for that their sets don't overlap so no cows are used twice.

So, if you go over all combinations of optimal length-N and length-M stacks for which their sets don't overlap, you will get all optimal length-(N+M) stacks. And for every stack of height>=H that we get, we can update the result value.

I considered going from length 1 to 2 to 4 to 8 and so on, but found the number of stack-joining operations blowing up (each time about the square of the number of possible sets). What's wrong with this is that with each stack size, we actually trim off many suboptimal sets, but we skipped many of these steps when we jumped up the numbers.

What I eventually did was just adding 1 cow at a time. This limits the number of loops to 2^20*20 which is approx. 2e7, snuggly fitting into the time limit.

But how to store and look up the sets their optimal stack states? We cram the information of the presence of 20 cows into 20 bits, and there're just about 1e6 cow combinations possible. We could store a lot of data for each set this way, even more than we need.

To traverse all n-cow sets before going to (n+1)-cow sets, we use a queue similar to what we do in BFS (because I can't think of an elegant iterative way), starting from an empty set (0), and for each queue front, we examine the set plus another from any of the unused cows and push to the queue as we see fit.

Of course we could get this to run cleaner: obviously we can trim the unreachable sets. But another one not so obvious is that once the height gets to H, we update the max strength and throw away the set. Why? Well, if it's already height H, making the stack even higher is only going to decrease the strength.

At this point I realize that I made a mistake that actually made the second optimization obsolete. When you see it, it should have been fixed, but the problematic code is below. Pause here and see if you can see what's wrong. Well? I stop the stack only when it updates the max strength, causing sets that don't work as well to pass. This lets through about half of these sets. Pretty bad, huh?

if (dh[q[qf]] >= H && ds[q[qf]] > maxs) // If height is reached and strength is better
{
    maxs = ds[q[qf]];                   //     Update global valid max-strength
    continue;                           //     Any more added cows will not increase strength
}

The two lines above that, checking whether the in-queue element is reachable, is also redundant, because if the element is unreachable it will not be in queue. I commented them out but you can still see them.

This is my first post. I try to explain this problem as simply as possible. Please comment if you think I could have been more clear in some parts:)

Full source code

// guard.c
#include <stdio.h>
#include <string.h>

#define MAXN 20
#define MIN(a, b) ( (a < b) ? a : b )
#define MAX(a, b) ( (a > b) ? a : b )
#define INF64 0x7fffffffffffffff

typedef long long ll;

ll H, N;
ll h[MAXN], w[MAXN], s[MAXN];
ll dh[1<<MAXN], dw[1<<MAXN], ds[1<<MAXN];
ll maxs = -1;
int q[1<<MAXN], qf, qr;

FILE *f;

int main()
{
    int _0, s_prime;

    f = fopen("guard.in", "r");
    fscanf(f, "%lld%lld", &N, &H);
    for (_0 = 0; _0 < N; ++_0)
        fscanf(f, "%lld%lld%lld", h+_0, w+_0, s+_0);
    fclose(f);

    memset(ds, -1, sizeof(ds));
    ds[0] = INF64;

    for (qf = 0; qf <= qr; ++qf)                                                                                                             // Loop through compressed combination states with binary digit sum
    {
        // printf("ds[0x%x]=%lld\n", q[qf], ds[q[qf]]);                                                                                      // //     There. Debug print.
        // if (ds[q[qf]] < 0)                                                                                                                // //     If unreachable
        //     continue;                                                                                                                     // //         Ignore
        if (dh[q[qf]] >= H)                                                                                                                  //     If height is reached
        {
            if (ds[q[qf]] > maxs)                                                                                                            //         If strength is better
                maxs = ds[q[qf]];                                                                                                            //             Update global valid max-strength
            continue;                                                                                                                        //         Any more added cows will not increase strength
        }
        for (_0 = 0; _0 < N; ++_0)                                                                                                           //     Loop through possible add-1's
        {
            if (!(q[qf] & 1<<_0) && (s_prime = MAX( MIN(ds[q[qf]] - w[_0], s[_0]), MIN(s[_0] - dw[q[qf]], ds[q[qf]]) )) > ds[q[qf] | 1<<_0]) //         If added-one is unused AND strength is better
            {
                ds[q[qf] | 1<<_0] = s_prime;                                                                                                 //             Update strength, obviously
                if (!dh[q[qf] | 1<<_0])                                                                                                      //             If height-uncached (also weight-uncached and not-in-queue)
                {
                    dh[q[qf] | 1<<_0] = dh[q[qf]] + h[_0];                                                                                   //                 Cache height
                    dw[q[qf] | 1<<_0] = dw[q[qf]] + w[_0];                                                                                   //                 Cache weight
                    q[++qr] = q[qf] | 1<<_0;                                                                                                 //                 Push into queue
                }
            }
        }
    }

    f = fopen("guard.out", "w");
    if (maxs < 0)
        fputs("Mark is too tall\n", f);
    else
        fprintf(f, "%lld\n", maxs);
    fclose(f);
    return 0;
}

DEV Community: Tongyu Lu